vSim: Semantics-Aware Value Extraction for Efficient Binary Code Similarity Analysis

vSim: Semantics-Aware Value Extraction for Efficient Binary Code Similarity Analysis

Speakers: Huaijin Wang

Conference: NDSS Symposium

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

Overview

Binary code similarity analysis -- searching a database for functions similar to a given binary -- is fundamental for vulnerability detection, malware classification, and patch analysis. This talk presents vSim, a value-based approach that identifies semantics-aware values by filtering noise (memory addresses, architecture-specific artifacts) and normalizing/concretizing symbolic values for efficient comparison. Unlike ML-based approaches that lack interpretability and robustness to unseen compilation environments, or prior value-based approaches that include semantic-irrelevant noise or miss important intermediate values, vSim captures the "Goldilocks" set of values that reflect program semantics.

vSim uses unbounded symbolic execution for value extraction, concretization (sampling concrete inputs) instead of expensive theorem proving for comparison, and fingerprint propagation to handle function inlining. Results show vSim outperforms baselines including jTrans, CLAP, and GMN across cross-architecture, cross-optimization, and cross-compiler scenarios, achieving scalability comparable to ML-based embedding approaches without requiring training data.

Background

▶ Watch: Binary code similarity: the search problem and its applications (0:00)

Binary code similarity approaches fall into three categories. ML-based approaches learn embeddings from compiled binaries, but are not robust to unseen compiler versions/flags and lack interpretability. Program state approaches collect all values (symbolic or concrete) through analysis, but are corrupted by semantically irrelevant values like memory addresses that differ across architectures. Selective value approaches extract only function parameters and return values, missing important intermediate computations that reflect program semantics.

vSim targets the ideal middle ground: extracting values that are semantically meaningful (reflecting program behavior) while filtering architecture-specific noise (memory addresses, pointer sizes, calling conventions).

Key Findings

▶ Watch: Inaccurate semantics: memory address noise across architectures (4:00)

• Outperforms ML baselines (jTrans, GMN) and value-based baselines (BinSim) across cross-architecture, cross-optimization, and cross-compiler scenarios
• Comparable scalability to ML embedding approaches despite not using machine learning
• No training data required: Unlike ML approaches, vSim works with unseen compilers and optimization levels without retraining
• Handles function inlining through fingerprint propagation, a challenge that prior value-based approaches fail on
• Successful 1-day vulnerability detection using value similarity to identify known vulnerable functions in differently compiled binaries
• Concretization outperforms theorem proving for value comparison: sampling concrete inputs is faster and more scalable than SMT solvers

Technical Deep Dive

▶ Watch: Concretization: sampling inputs instead of theorem proving (8:00)

vSim's pipeline: disassemble binary, extract values via unbounded symbolic execution, filter semantically irrelevant values (memory addresses), normalize across architectures, concretize by sampling inputs, generate fingerprints, compute Jaccard similarity.

Value Filtering: Removes architecture-dependent artifacts (pointer sizes differ between 32-bit and 64-bit), memory addresses, and calling convention artifacts. Retains values reflecting computational semantics (arithmetic operations, conditional checks, function call arguments).

Concretization: Instead of using theorem provers (sound but slow) to check symbolic formula equivalence, vSim samples concrete input values, executes symbolic formulas, and compares concrete results. For example, 3*x and 2*x' + x' produce identical concrete values when given the same inputs, confirming semantic equivalence efficiently.

Fingerprint Propagation for Inlining: When function f2 calls f1, separate fingerprints are generated. If f1 is inlined into f2, the fingerprints are unified, producing a single combined signature that correctly represents the inlined code's semantics.

Demo / Proof of Concept

▶ Watch: Fingerprint propagation for handling function inlining (10:00)

Evaluation covers GCC and Clang compilers with multiple optimization levels across different architectures. vSim achieves higher MRR and recall than most baselines in cross-optimization and cross-compiler scenarios. The 1-day vulnerability detection application successfully identifies known vulnerable functions in differently compiled binaries. Scalability testing shows vSim's comparison time is comparable to ML embedding cosine similarity.

Defensive Implications

▶ Watch: 1-day vulnerability detection application (14:00)

• Vulnerability propagation detection without ML training: Security teams can identify known vulnerabilities across differently compiled binaries without maintaining training pipelines
• Compiler-agnostic analysis: Works across unseen compilation environments, critical for firmware analysis where compiler details are unknown
• Interpretable results: Unlike ML embeddings, the value-based similarity provides explainable justification for similarity decisions

Key Takeaways

• Semantics-aware value extraction filters architecture-specific noise while preserving meaningful intermediate computations
• Concretization (concrete input sampling) replaces expensive theorem proving for value comparison
• Fingerprint propagation handles function inlining, a major challenge for binary similarity
• No ML training required, making vSim robust to unseen compilation environments
• Obfuscation resilience is explicitly acknowledged as a limitation and future work

About the Speaker(s)

Huaijin Wang presented joint work with a former postdoc (unable to attend due to visa issues). The presentation demonstrated deep understanding of both the binary analysis and program analysis aspects of the work.