Recovery of Class Hierarchies and Composition Relationships from Machine Code

Venkatesh Srinivasan, Thomas W. Reps

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.

Object traces for various classes, highlighting the 'finalizer idiom' (underlined destructor returns) used for fingerprinting.

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.

A trie representing the recovered class hierarchy, where nodes correspond to classes and paths represent inheritance.

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

Abstract

We present a reverse-engineering tool, called Lego, which recovers class hierarchies and composition relationships from stripped binaries. Lego takes a stripped binary as input, and uses information obtained from dynamic analysis to (i) group the functions in the binary into classes, and (ii) identify inheritance and composition relationships between the inferred classes. The software artifacts recovered by Lego can be subsequently used to understand the object-oriented design of software systems that lack documentation and source code, e.g., to enable interoperability. Our experiments show that the class hierarchies recovered by Lego have a high degree of agreement—measured in terms of precision and recall—with the hierarchy defined in the source code.
BibTeX
@inproceedings{srinivasan2014recovery,
  author = {Venkatesh Srinivasan and Thomas W. Reps},
  title = {{Recovery of Class Hierarchies and Composition Relationships from Machine Code}},
  booktitle = {CC},
  year = {2014},
  doi = {10.1007/978-3-642-54807-9\_4},
}
Figure