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