Practical Type Inference: High-Throughput Recovery of Real-World Structures and Function Signatures

Lukas Seidel, Sam Thomas, Konrad Rieck

TL;DR

XTRIDE is a high-speed type recovery system that identifies data structures and function signatures in "stripped" binaries (code missing its original metadata). By refining n-gram matching techniques and introducing calibrated confidence scores, it achieves state-of-the-art accuracy while running up to 2,300x faster than existing methods, making it the first practical choice for large-scale, automated security pipelines.

What Problem Does This Paper Address?

When software is compiled, much of the "human-readable" information—like variable names and complex data structure (struct) definitions—is discarded to save space and hinder reverse engineering. For security researchers analyzing malware or looking for vulnerabilities, "recovering" these types is essential for making sense of decompiled code.

Existing solutions face a "trilemma" of speed, accuracy, and usability. Traditional constraint-solving methods are painfully slow (taking minutes per binary). Modern machine learning approaches, like Large Language Models (LLMs), offer high semantic accuracy but are computationally expensive and prone to "hallucinating" layouts. Furthermore, most tools don't tell the user how sure they are about a prediction, leading to a "garbage in, garbage out" problem where one wrong type guess propagates through the entire decompiler output.

Methods

XTRIDE builds on the foundation of n-gram matching. It treats decompiled code like text, looking at the "neighborhood" (context) of a variable—specifically the $n$ tokens to its left and right.

The authors introduce several key innovations to make this approach "production-ready":

  • Bitness Separation: It maintains separate databases for 32-bit and 64-bit binaries. This is crucial because pointer sizes and memory alignment differ between architectures, which fundamentally changes how structures look in assembly.
  • Calibrated Confidence Scores: Using a technique called isotonic regression, XTRIDE transforms raw matching scores into actual probabilities. A user can tell the tool, "Only apply types you are 90% sure about," which is vital for automated workflows.
  • Optimized Training & Storage: By carefully selecting a subset of n-gram sizes (e.g., 2, 4, 8, 12, 48 tokens) and using high-performance Rust implementation with memory-mapped I/O, they drastically reduced the memory footprint and lookup time.
  • Function Signature Recovery: The authors extended the n-gram logic to identify entire functions based on their calling contexts, helping researchers quickly label known library functions in unknown firmware.

Datasets

The researchers evaluated XTRIDE using:

  • DIRT Dataset: A standard large-scale benchmark containing thousands of binaries compiled from open-source C/C++ projects.
  • Real-World Binaries: Common utilities like coreutils, wget, grep, and lighttpd to test how well the tool handles complex, user-defined structures.
  • ARM Embedded Firmware: A specialized dataset used to test the tool's ability to recover function signatures in "bare-metal" environments where symbols are almost always missing.

Key Insights and Ideas

  • Grounded Inference vs. Synthesis: Unlike LLM-based tools that try to "invent" a structure layout from scratch, XTRIDE uses a closed vocabulary. It looks for a match against real-world types it has seen before. This means if XTRIDE identifies a struct as sockaddr, the layout is guaranteed to be correct because it’s pulling from a real definition, not a guess.
  • The "Speed as a Feature" Philosophy: The authors argue that a tool that takes 8 seconds per function (like some LLM approaches) is useless for a firmware image with 50,000 functions. By hitting 0.04 ms per function, XTRIDE moves type recovery from a "batch job" to a real-time feature.
  • Sparsity Management: One of the "aha" moments in the paper is that you don't need a massive ensemble of 16 different n-gram databases. A few well-chosen, non-overlapping context lengths provide better accuracy with significantly less memory overhead.

Key Results

  • Accuracy: XTRIDE achieved 90.15% overall accuracy on the DIRT benchmark, a 5.09 percentage point improvement over the previous state-of-the-art (STRIDE).
  • Speed: It is 70x to 2,300x faster than competing struct recovery tools. In practical terms, it can process roughly 3,000 functions per second.
  • Struct Fidelity: It achieved the highest ratio of "fully-correct" struct layouts because its predictions are grounded in real-world type definitions.
  • Reliability: The calibrated confidence scores proved highly effective; by setting a high threshold, the tool could maintain near-perfect precision while only abstaining from the most ambiguous cases.

Limitations and Future Work

The primary limitation is the closed vocabulary nature of the system. Because XTRIDE relies on matching known patterns, it cannot accurately identify a completely novel, proprietary data structure it hasn't seen in its training set. It is best suited for environments with recurring components, such as standard libraries, Linux kernels, or common firmware stacks.

Future work could involve "hybridizing" the approach—using XTRIDE's speed for the 90% of code that uses standard types and reserving expensive LLM or constraint-solving analysis for the remaining 10% of unique, high-value structures.

Summary updated

Abstract

The recovery of types from stripped binaries is a key to exact decompilation, yet its practical realization suffers. For composite structures in particular, both layout and semantic fidelity are required to enable end-to-end reconstruction. Many existing approaches either synthesize layouts or infer names post-hoc, which weakens downstream usability. This is further aggravated by an excessive runtime overhead that is especially prohibitive in automated environments. We present XTRIDE, an improved n-gram-based approach that focuses on practicality: highly optimized throughput and actionable confidence scores allow for deployment in automated pipelines. When compared to the state of the art in struct recovery, our method achieves comparable performance while being between 70 and 2300 times faster. As our inference is grounded in real-world types, we achieve the highest ratio of fully-correct struct layouts. With an optimized training regimen, our model outperforms the current state of the art on the DIRT dataset by 5.09 percentage points, achieving 90.15% type inference accuracy overall. Furthermore, we show that n-gram-based type prediction generalizes to function signature recovery: conducting a case study on embedded firmware, we show that this efficient approach to function similarity can assist in typical reverse engineering tasks.
BibTeX
@misc{seidel2026practical,
  author = {Lukas Seidel and Sam Thomas and Konrad Rieck},
  title = {{Practical Type Inference: High-Throughput Recovery of Real-World Structures and Function Signatures}},
  year = {2026},
  eprint = {2603.08225},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2603.08225},
}
Figure