Binary Code Reuse Detection for Reverse Engineering and Malware Analysis

He HuangSpectrum 2015

Abstract

Code reuse detection is a fundamental challenge in reverse engineering, particularly when dealing with compiled binaries where source code is unavailable. Traditional techniques often fail due to compiler-induced variations in assembly code and control flow structures. This paper introduces BinSequence, a tool designed to identify similar functions across large-scale binary repositories. By employing a multi-stage pipeline—including instruction normalization, locality-sensitive hashing (LSH) for filtering, and a novel fuzzy matching algorithm based on longest execution paths—BinSequence achieves over 93% accuracy. Experimental results demonstrate that the tool can search through millions of functions in seconds, proving effective for real-world applications such as patch analysis, malware lineage tracking, and vulnerability discovery.

Introduction

Reverse engineering is a time-critical task. Whether analyzing a zero-day exploit, a new malware strain, or a security patch, analysts must quickly identify which components of a binary are known and which are novel. However, binary code reuse detection is significantly more complex than source code comparison. Compilers can transform the same logic into vastly different assembly sequences based on optimization levels, target architectures, or versioning.

Existing tools often struggle with the trade-off between accuracy and scalability. Graph-isomorphism approaches are computationally expensive and sensitive to control flow graph (CFG) perturbations, while simple heuristic matches often yield high false-positive rates. BinSequence addresses these challenges by combining high-performance filtering with a "fuzzy" structural matching algorithm that prioritizes the most significant execution paths.

Methodology

BinSequence utilizes a four-stage process to identify function similarity:

1. Normalization

To mitigate minor compiler variations, such as register reassignment, BinSequence normalizes instructions. Registers are replaced with a generic REG token, and immediate values are categorized as either OFFSET (memory addresses) or CONSTANT (fixed values). This ensures that the underlying logic is preserved while ignoring superficial differences.

2. Scalable Filtering

Comparing a target function against a repository of millions is computationally prohibitive. BinSequence employs a two-stage filter:

  • Basic Block Count Filter: Quickly discards functions with significantly different structural complexity.
  • Fingerprint Similarity Filter: Uses Minhashing and Locality-Sensitive Hashing (LSH) on normalized instruction sets. This allows the system to retrieve a small "candidate set" of syntactically similar functions in sub-second time.

3. Fuzzy Matching

Once a candidate set is identified, BinSequence performs a deep structural comparison:

  • The "Skeleton" Strategy: The algorithm identifies the longest execution path in the target function and uses a modified Longest Common Subsequence (LCS) algorithm to find the best-matching path in the candidate. This path serves as a robust anchor, or skeleton, for the match.
  • Neighborhood Exploration: Starting from the matched path, the tool greedily explores adjacent basic blocks. When multiple neighbors are potential matches, it employs the Hungarian algorithm to find the optimal mapping that maximizes instruction-level similarity.

4. Similarity Scoring

A final similarity score is calculated based on the ratio of matched instructions relative to the total instruction count of both functions, providing a normalized metric for ranking results.

Experimental Results

Accuracy and Performance

BinSequence was evaluated against industry-standard tools, including BinDiff, Diaphora, and PatchDiff2. In head-to-head comparisons using the zlib and libpng datasets, BinSequence achieved an accuracy of 93.75%, surpassing BinDiff’s 90.28%.

To test scalability, the tool was tasked with searching for functions within a repository of 2,055,584 functions (approximately 1GB of Windows system DLLs). BinSequence successfully returned high-quality matches in 0.9 to 2.9 seconds per query, demonstrating its readiness for enterprise-scale analysis.

Real-World Case Studies

  • Patch Analysis: The tool was used to analyze the HTTP.sys (MS15-034) "Ghost" vulnerability. BinSequence accurately identified the specific basic blocks modified by the patch, allowing analysts to quickly pinpoint the vulnerability's root cause.
  • Malware Analysis: By comparing the Zeus and Citadel malware families, BinSequence confirmed that Citadel reused approximately 67% of the Zeus code base with a 1.0 similarity score, effectively mapping the evolution of the malware.
  • Bug Search: In a search across Firefox versions (v33 to v40), BinSequence successfully identified a known vulnerability (CVE-2015-4485) that had been propagated through code sharing.

Discussion and Limitations

While BinSequence is highly effective, certain challenges remain. Function inlining can obscure reuse by embedding small functions into larger ones, potentially breaking the path-based matching logic. Additionally, the tool currently lacks semantic equivalence awareness; for example, it treats mov eax, 0 and xor eax, eax as distinct instructions despite their identical effect. Finally, advanced obfuscation techniques like control flow flattening can disrupt the structural matching process by artificially altering the CFG.

Conclusion

BinSequence represents a significant advancement in binary code reuse detection. By combining efficient LSH-based filtering with a resilient fuzzy matching algorithm centered on execution paths, it provides reverse engineers with a tool that is both highly accurate and capable of handling modern, large-scale software repositories. Future work will focus on incorporating semantic instruction grouping and improving resilience to aggressive code obfuscation.

Summary updated

Abstract

Code reuse detection is a key technique in reverse engineering. However, existing source code similarity comparison techniques are not applicable to binary code. Moreover, compilers have made this problem even more difficult due to the fact that different assembly code and control flow structures can be generated by the compilers even when implementing the same functionality. To address this problem, we present a fuzzy matching approach to compare two functions. We first obtain our initial mapping between basic blocks by leveraging the concept of longest common subsequence on the basic block level and execution path level. Then, we extend the achieved mapping using neighborhood exploration. To make our approach applicable to large data sets, we designed an effective filtering process using Minhashing and locality-sensitive hashing.
\nBased on the approach proposed in this thesis, we implemented a tool named BinSequence. We conducted extensive experiments to test BinSequence in terms of performance, accuracy, and scalability. Our results suggest that, given a large assembly code repository with millions of functions, BinSequence is efficient and can attain high quality similarity ranking of assembly functions with an accuracy above 90% within seconds.
\nWe also present several practical use cases including patch analysis, malware analysis, and bug search. In the use case for patch analysis, we utilized BinSequence to compare the unpatched and patched versions of the same binary, to reveal the vulnerability information and the details of the patch. For this use case, a Windows system driver (HTTP.sys) which contains a recently published critical vulnerability is used. For the malware analysis use case, we utilized BinSequence to identify reused components or already analyzed parts in malware so that the human analyst can focus on those new functionality to save time and effort. In this use case, two infamous malware, Zeus and Citadel, are analyzed. Finally, in the bug search use case, we utilized BinSequence to identify vulnerable functions in software caused by copying and pasting or sharing buggy source code. In this case, we succeeded in using BinSequence to identify a bug from Firefox. Together, these use cases demonstrate that our tool is both efficient and effective when applied to real-world scenarios.
\nWe also compared BinSequence with three state of the art tools: Diaphora, PatchDiff2 and BinDiff. Experiment results show that BinSequence can achieve the best accuracy when compared with these tools.
BibTeX
@inproceedings{huang2015binary,
  author = {He Huang},
  title = {{Binary Code Reuse Detection for Reverse Engineering and Malware Analysis}},
  booktitle = {Spectrum},
  year = {2015},
}
Figure