Introduction
Reverse-engineering "stripped" binaries—executables devoid of debugging information and symbol tables—presents a significant hurdle for security researchers and software engineers. While low-level details like control-flow graphs can often be recovered, reconstructing the high-level object-oriented (OO) structure remains a complex challenge. Lego is a novel tool designed to bridge this gap by reconstructing C++ class hierarchies and composition relationships directly from machine code using dynamic analysis.
Methodology: Reconstructing the OO Structure
Lego operates in two distinct phases, leveraging dynamic binary instrumentation via the Pin framework to monitor program execution.
Phase 1: Computing Object-Traces
The first phase involves executing the binary with various test inputs to record "object-traces." Lego identifies objects by monitoring the "this-pointer" idiom, assuming the first argument to a class method is a pointer to the object instance. To handle memory reuse and compiler optimizations, Lego employs "address versioning" to distinguish between different objects that occupy the same memory address at different times.
As shown in Figure 1, these traces capture the sequence of method calls (C) and returns (R). The core innovation lies in identifying the "finalizer idiom"—the sequence of destructor returns at the end of an object's lifetime. In C++, a derived class's destructor automatically calls its base class's destructor, creating a predictable "return-only suffix" in the trace.
Phase 2: Inferring the Hierarchy
In the second phase, Lego uses these finalizer suffixes as "fingerprints" to reconstruct the class hierarchy. These fingerprints are inserted into a trie data structure.
In this trie (Figure 2), each node represents a recovered class, and the edges represent inheritance relationships. For instance, if the destructor for a Bus class calls the destructor for a Vehicle class, the Bus node (node 3) will be a child of the Vehicle node (node 1) in the trie. Lego also detects composition ("has-a" relationships) by identifying when a class's finalizer calls the finalizer of a non-ancestor class.
Evaluation and Key Results
The effectiveness of Lego was evaluated using ten open-source C++ applications, including TinyXML, Astyle, and p7zip. By comparing the recovered structures against ground truth derived from unstripped versions of the programs, the researchers demonstrated high accuracy:
- Precision: Average of 88%
- Recall: Average of 86.7%
The tool proved robust against various compiler optimizations and multiple destructor versions. While dynamic instrumentation introduces overhead (2x to 15x slowdown), the subsequent hierarchy analysis is extremely efficient, typically completing in under a second.
Insights and Limitations
The primary insight behind Lego is that the destructor chain provides a reliable map of an object's inheritance lineage. By focusing on dynamic behavior rather than static code, Lego avoids the pitfalls of indirect jumps and pointer aliasing that often plague static analysis tools.
However, Lego's dynamic nature also introduces limitations:
- Code Coverage: It can only recover classes and methods executed during the test runs.
- Language Specificity: The "finalizer idiom" is central; languages with non-deterministic garbage collection (like D) break this logic.
- Inlining: Aggressive compiler inlining can hide methods from instrumentation.
Future work aims to integrate concolic execution to improve code coverage and broaden the tool's applicability to a wider range of software.
Summary updated