From Heuristics to Transformers: A Comprehensive Survey of Type Inference from Stripped Binaries

Technical Summary: From Heuristics to Transformers: A Comprehensive Survey of Type Inference from Stripped Binaries

Problem Statement
The recovery of high-level type information from stripped binaries—executables lacking symbol tables and debugging information (e.g., DWARF)—remains a fundamental challenge in software reverse engineering, vulnerability analysis, and decompilation. Compilation is a lossy transformation where high-level abstractions like data types are stripped away, leaving a "semantic desert" of raw assembly instructions. In stripped binaries, this loss is exacerbated by the removal of debugging metadata. Consequently, distinguishing pointers from integers, identifying complex data structures (arrays, structs, unions), and understanding control flow become inherently difficult. This asymmetry between source code intent and machine code reality hinders automated security applications, such as Control-Flow Integrity (CFI), which rely on precise type signatures to mitigate attacks like Return-Oriented Programming (ROP).

Methodological Evolution
The survey traces the evolution of Binary Type Inference (BTI) through three distinct paradigms, analyzing how the field has shifted from manual rule-based systems to data-driven deep learning architectures:

1. Heuristic and Constraint-Solving Era: Early approaches relied on manual expert knowledge and rule-based "duck typing" (e.g., if a variable is used as an index, it is a pointer). Tools like IDA Pro and Ghidra utilize these heuristics. Later, systems like BinSub and Retypd formalized BTI as a constraint satisfaction problem over a type lattice. These algebraic methods use symbolic logic to derive "principal types" based on instruction behavior (e.g., mov eax, [ebx+8] implies ebx is a pointer). While formally sound, these methods are brittle, struggling with aggressive compiler optimizations (e.g., Frame Pointer Omission) and "orphan variables" lacking sufficient data flow constraints.
2. Sequential Neural Models: Inspired by Natural Language Processing (NLP), this wave treats assembly instructions as textual sequences. Systems like BITY (using SVMs), EKLAVYA (using RNNs), and CATI (using CNNs) map opcodes and operands into vector spaces to capture local usage contexts (Variable Usage Context - VUC). While these models improve robustness on sparse data, they suffer from the vanishing gradient problem and struggle to capture long-range dependencies within large functions.
3. Structural and Transformer-Based Architectures: The current state-of-the-art leverages Graph Neural Networks (GNNs) and Transformers. Models like TYGR construct Data-Flow Graphs (DFGs) to capture topological dependencies, allowing for the propagation of structural features (e.g., dereference patterns) across the graph. SeeType utilizes Transformer architectures with Self-Attention mechanisms to model global dependencies simultaneously, overcoming the sequential limitations of RNNs. These approaches also introduce "Numeric-Aware Tokenization," treating specific offsets (e.g., 0x8, 0x10) as explicit structural hints rather than generic tokens, significantly aiding layout recovery.

Key Contributions

• Unified Taxonomy: The paper provides a comprehensive categorization of BTI methodologies, mapping the transition from algebraic subtyping to sequential NLP models and finally to structural GNNs and Transformers.
• Anatomical Analysis: It deconstructs the BTI pipeline into four foundational components: Variable Identification (handling registers, stack offsets, and heap), Intermediate Representation (IR) Lifting (e.g., VEX, LLVM-IR), Feature Extraction (data-flow, contextual, and structural features), and the Type Resolution Engine (logical solvers vs. probabilistic models).
• Critical Challenge Identification: The survey synthesizes four primary obstacles facing modern BTI:
  • Semantics Loss under Optimization: Aggressive compiler optimizations (e.g., -O3, FPO) distort program anatomy, reordering instructions and reusing registers, which breaks heuristic assumptions.
  • Numeric Literacy Gap: Traditional models often mask numerical values, blinding the system to critical structural clues embedded in offsets.
  • Topological Ambiguity: Complex types (structs vs. unions) often exhibit topological overlap in binary form, making fine-grained member reconstruction difficult without inter-procedural analysis.
  • Dataset Integrity: The prevalence of duplicate functions in standard datasets leads to models that "memorize" rather than generalize, inflating accuracy metrics.
• Future Roadmap: The authors propose three high-impact research directions:
  1. Binary Foundation Models: Developing self-supervised models pre-trained on billions of lines of unlabeled assembly to learn a "universal assembly grammar," enabling zero-shot inference across architectures.
  2. Neuro-Symbolic Integration: Combining the statistical intuition of neural generators (e.g., SeeType) with the formal verification of symbolic logic engines (e.g., BinSub) to ensure outputs are both statistically probable and logically consistent.
  3. Automated Structure Synthesis: Moving beyond classification to generative prediction of complete header files, accounting for alignment, padding, and nested pointers.

Results and Performance
The paper notes that while deep learning has significantly raised the accuracy ceiling for type inference, particularly in reconstructing fine-grained struct types, no single approach is perfect.

• Constraint Solvers offer high verifiable accuracy when constraints are complete but fail on sparse data.
• Sequential Models improve robustness but struggle with long-range dependencies.
• GNNs and Transformers achieve state-of-the-art results by capturing global data-flow shapes and long-range dependencies. However, they incur higher computational costs and still face challenges in reconstructing the internal tree of nested members and offsets.
• Generative Capabilities: The paper highlights a case study where an LLM (GPT-5) successfully reconstructed readable C code from assembly, demonstrating a "generative leap" in grouping memory accesses and inferring struct definitions, though it remains prone to hallucinations and lacks formal correctness guarantees.

Significance
The paper positions itself as a critical bridge between the "black-box" intuition of modern neural networks and the rigorous logic of traditional program analysis. It argues that the future of binary type inference lies not in choosing one paradigm over another, but in neuro-symbolic integration. By combining the coverage of neural models for "orphan variables" with the formal correctness of algebraic solvers, the field can move toward fully automated reconstruction of high-level intent. This evolution is presented as essential for advancing autonomous security systems, enabling analysts to navigate the semantic ambiguity of optimized, stripped binaries with unprecedented clarity.