Chopping binary executables: Object file recovery and Modular Decomposition

Chariton Karamitas (Android Security Researcher · CENSUS)

RE//verse 2026 · Day 2 · Coral Ballroom A

Overview

In the realm of binary analysis, a persistent challenge is the identification and separation of individual components within a stripped executable. Modern software is rarely monolithic; it's composed of numerous modules, libraries, and runtime components, often linked together from various object files. Understanding these constituent parts is crucial for tasks like reverse engineering, vulnerability research, and binary diffing. Chariton Karamitas, an Android Security Researcher at CENSUS and a PhD student, addresses this fundamental problem in his RE//verse talk, "Chopping binary executables: Object file recovery and Modular Decomposition."

Watch on YouTube

Visual summary for Chopping binary executables: Object file recovery and Modular Decomposition by Chariton Karamitas
Visual summary for Chopping binary executables: Object file recovery and Modular Decomposition by Chariton Karamitas

Key moments

  1. 0:00 Introduction: Decomposing binary executables
  2. 3:50 Introducing 'Recover' for object file structure
  3. 7:50 Impact of Link Time Optimizations (LTO)
  4. 20:30 Demonstrating 'Recover' in IDA Pro
  5. 23:30 Real-world validation: Recovering FFmpeg object files
  6. 28:50 Introduction to Modular Decomposition technique
  7. 37:00 Modular Decomposition: Advantages and the 'prime module' problem
  8. 44:00 Q&A: Real-world accuracy for binary diffing

Chopping binary executables: Object file recovery and Modular Decomposition

Speakers: Chariton Karamitas (Android Security Researcher, CENSUS)

Conference: RE//verse

YouTube: https://www.youtube.com/watch?v=o0boA1N6JV0

Overview

In the realm of binary analysis, a persistent challenge is the identification and separation of individual components within a stripped executable. Modern software is rarely monolithic; it's composed of numerous modules, libraries, and runtime components, often linked together from various object files. Understanding these constituent parts is crucial for tasks like reverse engineering, vulnerability research, and binary diffing. Chariton Karamitas, an Android Security Researcher at CENSUS and a PhD student, addresses this fundamental problem in his RE//verse talk, "Chopping binary executables: Object file recovery and Modular Decomposition."

Karamitas introduces two novel techniques designed to decompose stripped binaries into meaningful, isolated components, enabling more targeted and efficient analysis. The first, implemented in a tool called recover, focuses on reconstructing the approximate object file structure of an executable. The second technique leverages Modular Decomposition, a graph-theoretic algorithm, to partition a program's function call graph into a unique hierarchy of modules. These approaches, particularly when combined, offer a powerful "divide and conquer" strategy, promising to enhance the performance and accuracy of binary diffing and provide deeper insights into software architecture.

This research is particularly relevant given the increasing complexity and closed-source nature of many software ecosystems, such as Android, where vendors often ship proprietary, stripped components. The ability to automatically identify these internal boundaries and structures in binaries without debug symbols or source code is a significant advancement for security researchers and reverse engineers striving to understand and secure complex software.

Background

▶ Watch: Introduction: Decomposing binary executables (0:00)

Chariton Karamitas's research stems from his professional experience as an Android security researcher since 2015. He frequently encountered the challenge of binary diffing—comparing different versions of closed-source components to identify similarities, differences, and potential patches or vulnerabilities. This exposure inspired him to pursue a PhD focusing on binary diffing, where he observed a growing trend towards machine learning-based approaches in the late 2010s. However, Karamitas sought a more traditional, graph-theoretic solution, aiming to improve diffing performance and accuracy by first decomposing binaries into smaller, manageable components.

The core problem addressed is that most binaries are stripped, meaning they lack debug symbols that would otherwise delineate compilation units (object files). Without this information, functions from different source files are often intermingled in the final executable, making it difficult to analyze them in their original semantic groups. Prior work on this problem includes:

  • Unlinker (2016): A thesis that proposed algorithms for discovering compile units but suffered from a significant limitation: it required the number of compiler units to be known in advance.
  • The Link (2024): A more recent work that used limited assembly patterns, applicable only to specific GCC versions and compile-time options.
  • Binstruct (2025): Another recent paper, interestingly appearing in the literature shortly after Karamitas submitted his own work in 2023.

A key factor influencing the layout of functions and data in an executable is Link Time Optimizations (LTO). When LTO is enabled, the linker can perform sophisticated optimizations across compilation unit boundaries. One such optimization is hot/cold splitting, where the linker separates frequently executed (hot) functions from rarely executed (cold) functions. Traditionally, a linker concatenates the text segments of object files in order, followed by data segments. With hot/cold splitting, the linker might first concatenate all "cold" parts of functions, then all "hot" parts, and finally the data segments. This reordering can obscure the original object file boundaries, making recovery more challenging. Karamitas notes that his recover tool, when encountering hot/cold splitting, treats these separated parts as distinct object files, which is a pragmatic approach given the difficulty of re-associating them without additional information.

Key Findings

▶ Watch: Impact of Link Time Optimizations (LTO) (7:50)

The central contributions of this research are two distinct, yet complementary, techniques for decomposing stripped binary executables:

  1. Object File Recovery using recover: The recover tool is designed to reconstruct the approximate object file structure of a stripped binary. By analyzing the Augmented Function Call Graph (AFCG)—which incorporates both control flow and data flow dependencies, along with memory layout information—recover identifies groups of functions that likely originated from the same object file. This allows researchers to segment a large, monolithic binary into semantically related components, even when the original compilation boundaries have been obscured by linking processes and optimizations. A significant finding demonstrated by Karamitas is recover's ability to achieve high accuracy, exemplified by its performance on an FFmpeg binary where it was 5% off from the ground truth.
  1. Modular Decomposition for Hierarchical Graph Partitioning: This technique applies Modular Decomposition, a graph-theoretic algorithm, to partition the program's function call graph into a hierarchy of modules. A module is defined as a set of nodes where all nodes within the module have the same neighborhood outside the module, effectively making them "indistinguishable" from an external perspective. The resulting hierarchy, visualized as an MD tree, is uniquely determined by the graph (up to isomorphism). This uniqueness is a powerful property for binary diffing, as similar programs will yield similar MD trees, providing a robust structural comparison metric that is resilient to certain compiler optimizations. While recover focuses on semantic grouping based on compilation units, Modular Decomposition offers a different, purely graph-structural partitioning that can reveal inherent architectural properties.

Both techniques aim to facilitate a "divide and conquer" approach to binary analysis, particularly for binary diffing. By breaking down complex binaries into smaller, more manageable components or hierarchical structures, the analysis can be performed more efficiently and accurately on these individual parts, and then synthesized to form a larger, more comprehensive understanding of the entire program.

Technical Deep Dive

▶ Watch: Real-world validation: Recovering FFmpeg object files (23:30)

The technical core of Karamitas's work lies in the sophisticated graph construction and algorithmic approaches employed by both recover and the Modular Decomposition framework.

Object File Recovery with recover

The primary goal of recover is to answer two questions for a stripped binary: how many object files are present, and what are their sizes? This is conceptualized by modeling the program as a bit vector where each bit corresponds to a function, and a set bit indicates the beginning of a new object file.

The process begins by constructing a series of graphs:

  1. Function Call Graph (FCG): The standard graph representing control flow, where vertices are functions and edges represent calls.
  2. Data Flow Graph (DFG): A graph where vertices are data elements and edges connect data elements that refer to each other (e.g., a struct instance pointing to other elements).
  3. Program and Data Graph (PDG): This is a union of the FCG and DFG, augmented with additional edges. Edges are added from data elements to functions (e.g., a vtable containing function pointers) and from functions to data elements (e.g., a function accessing a global variable).
  4. Augmented Function Call Graph (AFCG): The PDG serves as an intermediate step to create the AFCG. If two functions are indirectly connected via a series of data elements in the PDG (e.g., Function A accesses a vtable, which points to Function B), a direct edge is added between Function A and Function B in the AFCG. Additionally, sequence edges are added, connecting functions that are laid out contiguously in memory, provided no segment boundary is crossed. An experimental feature called density edges also adds connections between functions called within a window of a calling function's body, sorted by address, assuming proximity implies relatedness.

Once the AFCG is built, recover employs a two-stage approach:

Initial Estimation Algorithms (Four Variants):

  1. Articulation Points Method (Hopcroft-Tarjan Algorithm): This algorithm identifies articulation points (or cut vertices) in the AFCG—nodes whose removal increases the number of connected components. These are considered "bottlenecks" that expose internal functionality of an object file to others. The total number of object files is arbitrarily assumed to be a linear function of the number of articulation points. Each articulation point then marks the beginning of a potential new compile unit. Two variants exist: one using partial sequence edges (those that don't disconnect the graph) and one discarding all sequence edges.
  2. Agglomerative Algorithm: This is a bottom-up approach. It starts by assigning each function to its own compile unit. It then iteratively attempts to merge adjacent functions into a single compile unit. A merge is considered successful if the resulting compile unit graph (where vertices are compile units and edges represent calls between them) has fewer non-tree edges than before the merge. This heuristic is inspired by software engineering principles from the 1960s, suggesting that well-designed modules ideally form a tree-like dependency structure. Again, two variants are implemented: with partial sequence edges and without.

Optimization Algorithm (Newman Modularity):

The initial estimation is then refined using an optimization algorithm based on Newman Modularity. Newman Modularity is a clustering quality function that measures the density of edges within clusters compared to edges connecting different clusters.

The algorithm works iteratively:

  • It takes an initial segmentation (estimated compile units) and treats them as communities.
  • For each pair of adjacent estimated compile units, it explores all possible ways to shift the boundary between them or introduce a new compile unit.
  • For each combination, it calculates the Newman Modularity score.
  • The segmentation with the highest modularity score is selected as the locally optimal solution.
  • This process is repeated, adding modified compile units back to a worklist for re-evaluation until convergence.

Modular Decomposition

Modular Decomposition is a distinct graph partitioning technique. A module is formally defined as a set of nodes M in a graph G such that every node v outside M is either connected to all nodes in M or to none of them. In essence, all nodes within a module are "indistinguishable" to any node outside the module.

Modules can be classified into three types:

  • Series Modules: Comprise vertices that are all connected to each other (e.g., nodes A, B, C, D where each is connected to the others).
  • Parallel Modules: Consist of vertices that are completely disconnected from each other (e.g., nodes F, G, H where no internal connections exist).
  • Prime Modules: Modules that are neither series nor parallel.

The most compelling aspect of Modular Decomposition is that it produces a unique hierarchical structure, known as an MD tree, for any given graph (up to isomorphism). This tree-like representation captures the intrinsic structural properties of the graph. The root of an MD tree is typically a parallel module. Children of a parallel module are independent, while children of a series module are connected.

Algorithms for Modular Decomposition have evolved from quartic to linear complexity. Karamitas utilizes a state-of-the-art C++ implementation by a German student (2023), which he ported to Python and submitted as a pull request to the NetworkX library. While MD trees offer strong theoretical properties and resilience to some compiler optimizations, a practical limitation observed by Karamitas is the prevalence of prime modules containing the bulk of program functions in real-world binaries. These prime modules offer less insight into the relationships between their children compared to series or parallel modules.

The application of both recover and Modular Decomposition provides a multi-faceted approach to understanding binary structure, each offering unique perspectives valuable for subsequent analysis, especially in the context of binary diffing.

Demo / Proof of Concept

▶ Watch: Introduction to Modular Decomposition technique (28:50)

Chariton Karamitas demonstrated recover using an IDA Pro plugin, showcasing its practical application on a stripped binary of the shred utility compiled for ARM 64 with O3 optimizations. The demonstration involved a clear, step-by-step process:

  1. Graph Export: The plugin first extracts the necessary graph data (FCG, DFG, etc.) from the IDA database.
  2. Analysis: The user selects an initial estimation method (e.g., the articulation points method without sequence edges, chosen as a wise default) and an optimization method (e.g., fast brute force, genetic, or brute force).
  3. Result Visualization: After analysis, the plugin loads the recovered compile units into a simple UI. Karamitas highlighted compile unit number 17, which contained 33 functions. Crucially, even though the binary was stripped, these functions all shared a common prefix, target_ar_, strongly suggesting they belonged to the same original object file. This validates recover's ability to group semantically related functions.

To further illustrate the results, Karamitas modified an existing IDA plugin called Function+ (found on GitHub) to group functions based on recover's output, presenting them as a file system tree. This visual representation intuitively showed the recovered object file structure, with CU17 again standing out as a distinct branch.

A compelling anecdote highlighted recover's accuracy:

  • Karamitas initially tested recover on a stripped FFmpeg binary compiled for Android, which returned 2,100 compile units.
  • Lacking ground truth, he reverse-engineered the binary to identify its original configure command line and library versions, revealing it was built with Android NDK R15C.
  • He then reproduced the build environment using NDK25 (a newer version) and recompiled FFmpeg. Running recover on this new binary yielded 1,500 compile units. This discrepancy suggested an issue.
  • Upon rebuilding FFmpeg with the original NDK R15C, recover reported 2,000 compile units. This was merely 5% off from the original binary's estimate, demonstrating remarkable accuracy. The difference in NDK25's output was attributed to its default behavior of not performing hot/cold splitting, which NDK R15C did. This anecdote not only validated recover but also underscored the impact of compiler and linker options on binary structure.

For Modular Decomposition, Karamitas presented visualizations of MD trees for the shred binary compiled under different conditions:

  • AMD 64 GCC O1 vs. ARM 64 Clang 11 O3.
  • Coreutils 8.30 GCC 7 O for AMD 64.

Despite significant differences in architecture, compiler, and optimization levels, the MD trees showed striking visual similarities, demonstrating their stability and resilience. He zoomed in to explain the properties of parallel (blue), series (green), and prime (red) modules, noting that children of parallel modules are independent, while children of series modules are connected. Acknowledging a limitation, he pointed out that a single prime module often contained the vast majority (e.g., 75% for objdump) of program functions, offering limited insight into their internal relationships.

Finally, Karamitas showcased the performance of the Modular Decomposition algorithm, running it on objdump (a binary with over 2,000 functions). The analysis completed within 1 to 2 seconds, demonstrating its efficiency even for large executables.

Defensive Implications

▶ Watch: Q&A: Real-world accuracy for binary diffing (44:00)

The techniques presented by Chariton Karamitas offer several significant implications for defenders and security practitioners:

  1. Enhanced Component Identification: For large, stripped binaries, recover provides a crucial capability to automatically identify and delineate the boundaries of individual object files. This is invaluable when dealing with proprietary or closed-source software, such as Android vendor components or embedded firmware, where understanding the internal modularity is essential for focused analysis. Defenders can use this to understand which parts of a binary correspond to specific functionalities or third-party libraries.
  1. Targeted Reverse Engineering and Re-engineering: Once object files are recovered, defenders can isolate specific components for deeper analysis. As Karamitas noted, if a proprietary cryptographic algorithm is identified, recover can help extract all related functions, facilitating re-engineering or the development of custom cracks. This can also apply to identifying and extracting specific drivers, network stacks, or other critical modules for security auditing.
  1. High-Level Software Architecture Modeling: By representing each recovered object file as a node in a graph and adding edges based on inter-object file calls, defenders can construct a higher-level model of a software's architecture. This abstract view can help in understanding dependencies, identifying choke points, or pinpointing areas of high complexity that might warrant further scrutiny for vulnerabilities.
  1. Improved Patch Analysis and Vulnerability Research: The "divide and conquer" approach significantly streamlines binary diffing. Instead of diffing entire binaries, defenders can focus on diffing individual, semantically grouped object files. Karamitas provided an example of diffing two Windows kernel versions (before and after a patch) where recover helped pinpoint the exact compile unit containing the modified functions related to a specific CVE. This makes vulnerability analysis more efficient by narrowing down the scope of changes.
  1. Resilience to Compiler Optimizations: While recover acknowledges limitations like hot/cold splitting (treating separated parts as distinct units), the MD tree from Modular Decomposition is shown to be remarkably stable and resilient to various compiler optimizations and even different compilers/architectures. This stability provides a robust baseline for comparing program structure, even in the face of aggressive compiler transformations.

However, it's important to acknowledge limitations. The speaker mentioned BOLT (Binary Optimization and Layout Tool), a profiling-guided link-time optimizer used by large corporations. BOLT can reorder and intermix functions from different object files based on profiling information, making object file recovery significantly more challenging, if not impossible. Fortunately, such highly optimized binaries are rarely distributed to the general public.

Overall, these techniques equip defenders with powerful tools to dissect and comprehend complex, stripped binaries, enabling more efficient and accurate security assessments and vulnerability discovery.

Key Takeaways

  • Component Identification is Crucial: Decomposing stripped binaries into their constituent object files or structural modules is fundamental for effective binary analysis, reverse engineering, and diffing.
  • recover for Object File Structure: The recover tool offers a robust method for approximating object file boundaries by leveraging sophisticated graph analysis (FCG, DFG, PDG, AFCG) and algorithms based on articulation points and Newman Modularity, achieving high accuracy even with linker optimizations like hot/cold splitting.
  • Modular Decomposition for Unique Structural Insight: Modular Decomposition provides a graph-theoretic approach to partition programs into a unique, hierarchical MD tree. This structural representation is stable across different compilers and optimization levels, making it valuable for resilient binary diffing.
  • "Divide and Conquer" for Efficiency: Both recover and Modular Decomposition enable a "divide and conquer" strategy, allowing security researchers to analyze smaller, more semantically coherent components, improving the speed and accuracy of tasks like binary diffing and patch analysis.
  • Practical Applications Beyond Diffing: The research has broader implications, including extracting proprietary code, modeling software architecture, and simplifying targeted reverse engineering efforts in complex, closed-source ecosystems like Android.
  • Continuous Development and Availability: The recover tool is available on GitHub and was submitted to the IDA Pro plugin contest, with upcoming support for Binary Ninja. The Modular Decomposition implementation has been contributed to NetworkX, highlighting the speaker's commitment to open-source contributions.

About the Speaker(s)

Chariton Karamitas, also known as Huku or Hari, is an Android Security Researcher at CENSUS, where he has specialized in vulnerability research since 2015. He is known for his contributions to the security community, including articles published in Phrack. Beyond his professional role, Karamitas is currently a PhD student focusing on binary diffing, with his thesis expected in May 2026. His academic pursuit is driven by his extensive practical experience in analyzing fragmented Android ecosystems and the need for more effective, graph-theoretic approaches to understanding and comparing complex binary executables.

Reviews

Dr. Zero (Offensive Security Researcher) — SOLID

Chariton Karamitas brought actual graph theory to the binary diffing knife fight. While the rest of the industry is slapping LLMs onto Ghidra, he built a deterministic pipeline to reconstruct object boundaries in stripped binaries. It's hard, tedious work that makes hunting 1-days in Android vendor blobs significantly less miserable.

Heather Calloway (CISO) — SOLID

This is deep reverse-engineering research aimed squarely at threat intel and forensic analysts. Karamitas provides a new mathematical approach to tearing apart stripped, proprietary binaries to figure out what they actually contain. It won't reach your boardroom, but it gives your technical teams a faster way to interrogate black-box vendor software.

→ Top-rated talks at RE//verse 2026

All talks from RE//verse 2026