BINALIGNER: Aligning Binary Code for Cross-Compilation Environment Diffing

BINALIGNER: Aligning Binary Code for Cross-Compilation Environment Diffing

Speakers: Yiran Zhu

Conference: NDSS Symposium

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

Overview

Binary diffing -- identifying corresponding code regions between two binaries compiled from related source -- is essential for vulnerability detection, patch verification, plagiarism detection, and malware analysis. Existing approaches match at the basic block (node) level, losing structural semantics when compiler optimizations split, merge, reorder, or unroll blocks. This talk presents BinAligner, which performs binary diffing at the subgraph level, using iterative anchor-based subgraph expansion with condition relaxation policies to handle compiler-induced structural changes, and Struc2Vec Siamese networks with contrastive learning to distinguish aligned from misaligned subgraph pairs.

BinAligner outperforms state-of-the-art approaches (InnerDiff with InnerEye embeddings, SigmaDiff with Gemini embeddings) across cross-architecture, cross-compiler, cross-optimization, and cross-version scenarios, and correctly identifies all vulnerable and patched code regions in practical vulnerability analysis experiments.

Background

▶ Watch: Binary diffing vs similarity: why alignment matters (0:00)

Binary code similarity determines whether two functions are similar as a whole (typically via embedding comparison). Binary diffing goes further: it identifies which specific portions of code are similar or different, requiring alignment of code regions. This is critical for determining whether a known vulnerability exists in a differently compiled binary, whether a security patch has been applied, or whether code has been plagiarized.

The fundamental challenge is that the same source code produces very different control flow graphs (CFGs) under different compilation environments. Different architectures (x86 vs ARM), compiler versions (GCC 9 vs GCC 12), and optimization levels (O0 vs O3) can split basic blocks into multiple blocks, merge blocks, reorder independent blocks, or unroll loops. Node-level matching loses this structural context entirely.

Key Findings

▶ Watch: BinAligner overview: anchor nodes, expansion, Siamese learning (4:00)

• Outperforms all baselines (InnerDiff, SigmaDiff) in cross-architecture, cross-compiler, cross-optimization, and cross-version binary diffing
• Architecture-agnostic by relying on basic block statistical features rather than instruction-level semantics
• 100% accuracy on vulnerability/patch detection: BinAligner correctly identifies all vulnerable and patched code regions across cross-compilation scenarios
• Two condition relaxation policies effectively handle the four main compiler-induced structural changes: block splitting, merging, loop unrolling, and block reordering
• Siamese network generalizes across datasets: Training on CoreUtils with one compiler version and testing on different versions produces strong results
• Subgraph-level matching preserves topological structure lost in node-level approaches

Technical Deep Dive

▶ Watch: Iterative subgraph expansion with anchor and chain nodes (10:00)

BinAligner operates in three steps:

Step 1 - Subgraph Pair Identification: Starting from anchor nodes (entry, exit, and branch nodes with in/out degree not equal to 1), the algorithm identifies corresponding pairs across the two CFGs. Non-anchor nodes (chain nodes with in-degree = out-degree = 1) represent sequential code between structural points.

Step 2 - Iterative Expansion with Condition Relaxation: Two policies handle compiler transformations:

• Policy 1 (Block splitting/merging/unrolling): From matched anchor nodes, the algorithm follows successors and predecessors to find other anchor nodes with matching in/out degrees. Chain nodes between anchors are included regardless of count -- handling cases where optimizations split one block into three or merge three blocks into one.
• Policy 2 (Block reordering): Extends subgraph boundaries to include additional anchor nodes that may have been reordered by the compiler, along with their connecting chain nodes.

This iterative process continues until no unmatched anchor nodes remain.

Step 3 - Siamese Network Learning: Subgraph pairs are represented using basic block statistical features (call count, branch count, arithmetic operation count, etc.) and fed into a Struc2Vec-based Siamese network with contrastive loss. The network learns to place aligned subgraph pairs close in embedding space and misaligned pairs far apart, producing a similarity matrix for final alignment decisions.

Demo / Proof of Concept

▶ Watch: Cross-architecture results outperforming all baselines (12:00)

Evaluation uses CoreUtils, Diffutils, Findutils, and OpenSSL (libssl, libcrypto) datasets across extensive compilation environments (multiple compilers, versions, optimization levels, architectures, and source code versions). BinAligner correctly identifies all vulnerable and patched code regions in cross-compilation vulnerability analysis experiments, demonstrated through confusion matrices showing perfect classification.

The approach also generalizes: training on one compiler version and testing on different versions produces strong F1 scores, demonstrating that the Siamese network learns to recognize structural transformations (splitting, merging, reordering) rather than memorizing specific compilation patterns.

Defensive Implications

▶ Watch: Cross-version generalization and practical deployment (16:00)

• Vulnerability propagation detection: Organizations can determine whether a known vulnerability in one binary exists in differently compiled versions across their infrastructure
• Patch verification: Security teams can verify that patches have been correctly applied across binaries compiled for different architectures or with different compilers
• Supply chain analysis: Binary diffing enables comparing vendor-provided binaries against known-good reference builds to detect unauthorized modifications
• Firmware analysis: Cross-architecture support (x86, ARM, MIPS) enables analysis of IoT device firmware compiled for various embedded platforms

Key Takeaways

• Subgraph-level binary diffing preserves structural semantics lost in node-level matching
• Two condition relaxation policies handle block splitting, merging, unrolling, and reordering from compiler optimizations
• Architecture-agnostic design using basic block statistics enables cross-architecture diffing
• 100% accuracy on vulnerability and patch detection across cross-compilation scenarios
• Siamese network with contrastive learning generalizes across compilation environments
• Future work: using intermediate representation instead of machine instructions for richer cross-architecture semantics

About the Speaker(s)

The presentation was delivered on behalf of researchers from Jiangnan University (who could not attend due to visa issues). The speaker demonstrated strong command of both the binary analysis fundamentals and the machine learning methodology, engaging with technical questions about compiler-inserted code impact from audience members at Sungkyunkwan University.