Enhancing Semantic-Aware Binary Diffing with High-Confidence Dynamic Instruction Alignment

Enhancing Semantic-Aware Binary Diffing with High-Confidence Dynamic Instruction Alignment

Speakers: Chengfeng Ye

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=cdarKPDoy8M

Overview

Chengfeng Ye presents a technique for improving binary diffing accuracy by using dynamic forced execution to identify high-confidence instruction alignments (anchor points) between two binary versions. Binary diffing -- locating similar and different parts between two binaries -- is essential for vulnerability analysis, allowing researchers to understand patches and identify the underlying bugs. Modern binary diffing tools like DeepBinDiff and SigmaDiff use a "neighborhood consensus" approach where confidently matched instructions (anchor points) guide the matching of remaining instructions. The key finding: by identifying 24% more anchor points with equivalent or higher accuracy, the technique improves the F1 score of existing tools by 3 to 40 percentage points across cross-version, cross-optimization, cross-compiler, cross-architecture, and cross-obfuscation scenarios, with only 1.6-3.2% additional runtime overhead.

Background

▶ Watch: Binary diffing for vulnerability analysis: BinDiff and Diaphora (0:30)

Binary diffing compares two versions of a binary to identify what changed -- typically used for analyzing security patches to understand vulnerabilities without source code access. Tools like BinDiff, Diaphora, DeepBinDiff, and SigmaDiff operate at basic block or pseudo-code level to highlight modifications. For example, BinDiff can show changed basic blocks, and Diaphora can locate changed branch conditions revealing privilege escalation vulnerabilities.

Modern tools use neighborhood consensus: first match a small set of instructions with high confidence (anchor points), then use those anchors to guide matching of remaining instructions. DeepBinDiff performs greedy matching expanding from anchor points, while SigmaDiff uses anchor points as labeled data to fine-tune graph matching models. Both tools' accuracy improves directly with the number and quality of anchor points.

Existing anchor point detection methods are limited. Syntactic matching (matching by constant string references or external library calls) applies to only a small fraction of instructions. Symbolic expression matching is vulnerable to compiler optimizations that change computation order. Symbolic execution (theorem prover-based equivalence checking) is accurate but prohibitively expensive -- prior work reported requiring hours for small binaries.

Key Findings

▶ Watch: Limitations of syntactic matching and symbolic execution (4:00)

24% more anchor points identified: The dynamic forced execution approach detects 24% more instruction alignments usable as anchor points, with equivalent or higher accuracy compared to existing methods.

3-40 percentage point F1 improvement: When integrated with DeepBinDiff and SigmaDiff, the additional anchor points improve F1 scores across all tested scenarios, with improvements ranging from a few percentage points to 40 percentage points.

Minimal overhead: The technique adds only 3.2% runtime overhead for SigmaDiff and 1.6% for DeepBinDiff, making it practical for integration into existing workflows.

Robust across transformations: Results hold across cross-version (same project, different versions), cross-optimization (O2 to O3), cross-compiler (GCC to Clang), cross-architecture (ARM32 to x86-64), and cross-obfuscation (LLVM obfuscator) scenarios.

80-90% of instructions have small value sets: The static analysis estimates that over 80-90% of instructions have only one possible runtime value, making them highly amenable to the prioritized sampling strategy.

Technical Deep Dive

▶ Watch: Path explosion solved by prioritized sampling for small value sets (8:00)

Dynamic forced execution initializes function parameters with simplified values and emulates execution within the control flow graph, computing concrete values at each instruction. For example, if a function takes parameters Q=32 and S=12, instruction I3 computing Q+S yields the concrete value 44. These runtime values serve as robust features for matching because compiler optimizations are semantic-preserving -- they cannot change the computed values, only the instruction ordering.

Two challenges arise. First, path explosion: the number of paths grows exponentially with program size, making exhaustive exploration infeasible. The researchers observe that instructions with smaller value sets (fewer possible runtime values across all paths) are statistically more likely to match correctly with limited sampling. A lightweight abstract interpretation estimates each instruction's value set size, and a prioritized path sampling strategy allocates sampling budget to paths covering instructions with the smallest value sets first.

Second, ambiguous matching: multiple instructions may share overlapping runtime values (especially low-entropy values like 0 or -1 used in branch conditions and error codes). To resolve this, the researchers propose reduced CFG isomorphism. When multiple instructions share values, the technique constructs reduced control flow graphs containing only the ambiguous nodes and performs subgraph isomorphism on these small graphs. This is efficient because the reduced graphs are small (despite isomorphism being NP-hard in general) and resilient to transformations in other code regions (inlined callees, split basic blocks, duplicated blocks) because those transformed nodes do not appear in the reduced graph.

The implementation lifts binaries to LLVM IR using the LLVM framework, then extends DeepBinDiff and SigmaDiff to use the detected instruction alignments as anchor points. The publicly available artifact enables reproduction.

Demo / Proof of Concept

▶ Watch: Reduced CFG isomorphism for resolving ambiguous matches (10:00)

Evaluation covers five scenarios: cross-version (same project, different versions), cross-optimization (O2 vs O3), cross-compiler (GCC vs Clang), cross-architecture (ARM32 vs Intel x86-64), and cross-obfuscation (LLVM obfuscator with different obfuscation passes). The F1 score improvements range from a few percentage points to 40 percentage points. API calls during forced execution are modeled using a hash function over the call name and argument runtime values to produce return values, avoiding the need to emulate complex external behavior. The artifact is publicly available for reproducibility.

Defensive Implications

▶ Watch: Q&A: comparison with BinDiff and API call emulation strategy (14:00)

Better binary diffing directly benefits vulnerability analysis and patch analysis workflows. Security teams analyzing vendor patches to understand fixed vulnerabilities rely on binary diffing accuracy. The ability to handle cross-compiler, cross-architecture, and cross-obfuscation scenarios is particularly valuable for analyzing firmware updates (often cross-architecture) and malware variants (often obfuscated). The minimal runtime overhead (1.6-3.2%) means this can be integrated into existing analysis pipelines without significant performance impact.

Key Takeaways

• Dynamic forced execution provides compiler-optimization-robust instruction matching by using runtime values rather than syntactic features
• 24% more anchor points detected with equivalent accuracy, improving F1 scores by 3-40 percentage points
• Prioritized path sampling exploits the finding that 80-90% of instructions have only one possible runtime value
• Reduced CFG isomorphism efficiently resolves ambiguous matches without being affected by transformations in other code regions
• Only 1.6-3.2% additional runtime overhead for integration with existing tools
• Works across cross-version, cross-compiler, cross-architecture, and cross-obfuscation scenarios
• Publicly available artifact built on LLVM framework

About the Speaker(s)

Chengfeng Ye is a researcher specializing in binary analysis and reverse engineering. The work extends the state of the art in binary diffing by combining dynamic analysis with existing graph-matching approaches to provide higher-confidence instruction alignment for vulnerability and patch analysis.