Fool Me If You Can: On the Robustness of Binary Code Similarity Detection Models against Semantics-preserving Transformations

1. Problem Statement

Binary Code Similarity Detection (BCSD) is a critical task in cybersecurity, used for malware detection, vulnerability discovery, and plagiarism detection. It involves determining if two binary code snippets (without source code) are semantically similar. While deep learning (DL) models have significantly improved BCSD performance, their robustness against adversarial attacks remains underexplored.

The core challenge addressed in this paper is that unlike natural language or images, machine instructions have unique constraints:

• Semantic Equivalence: Different instruction sequences (e.g., mov rax, 0 vs. xor rax, rax) can perform identical functions.
• Strict Semantics: Unlike text, where minor typos might be tolerated, binary code requires exact precision; a single-bit error can cause program failure.
• Adversarial Gap: Existing studies often focus on single transformation types or narrow model sets. There is a lack of comprehensive evaluation on how diverse, semantics-preserving transformations (obfuscation and diversification) affect state-of-the-art BCSD models.

The authors ask: Can an adversary manipulate binary code to fool BCSD models into misclassifying similar code as dissimilar (False Negatives) or dissimilar code as similar (False Positives), while preserving the program's original functionality?

2. Methodology: The asmFooler System

The authors introduce asmFooler, a system designed to evaluate BCSD robustness through two main components:

A. Generating Binary Variants (Adversarial Samples)

The system applies eight distinct semantics-preserving transformations to 620 baseline binaries (from coreutils, binutils, nginx, SPEC2006, etc.), generating 9,565 adversarial variants. These transformations are categorized into:

1. Code Diversification (FN-Triggering): Techniques that alter the code's footprint to evade detection while keeping functionality.
   • In-place Code Randomization: Instruction substitution, intra-basic-block reordering, register preservation reordering, and register reassignment (adapted for 64-bit ELF).
   • Inter-Basic-Block Reordering: Relocating basic blocks within a function.
2. Code Obfuscation (FN-Triggering): Techniques designed to confuse analysis.
   • Semantic NOP Implantation: Inserting instruction sequences that cancel each other out (e.g., push rax followed later by pop rax) using a context-free grammar.
   • Junk Code Insertion: Adding unreachable dead code at the function entry.
   • LLVM-based Obfuscation: Using Obfuscator-LLVM to apply instruction substitution, bogus control flow, and control flow flattening.

B. Evaluating Robustness

The authors evaluate six state-of-the-art BCSD models:

• Graph-based: Genius, Gemini (use Control Flow Graphs).
• Embedding-based: Asm2Vec, SAFE (use instruction embeddings/random walks).
• Transformer-based: Trex, BinShot (use BERT-like architectures).

The evaluation focuses on two attack goals:

1. False Negative (FN) Triggering: Making similar code appear dissimilar (evasion).
2. False Positive (FP) Triggering: Making dissimilar code appear similar (poisoning/misclassification).
   • FP Strategy: The authors developed a greedy sampling algorithm to prepend adversarial instruction prefixes to a victim function. The algorithm iteratively selects instructions from a target distribution that maximize the similarity score with a specific target function, stopping when a similarity threshold is met or the budget is reached.

C. Explainable AI (XAI) Analysis

To understand why models fail, the authors use SHAP (Shapley Additive Explanations) and Saliency Maps to visualize how perturbations shift the model's attention and decision boundaries.

3. Key Contributions

1. asmFooler System: A comprehensive framework for generating and evaluating adversarial binary variants using eight diverse semantics-preserving transformations.
2. Large-Scale Dataset: A corpus of 9,565 transformed binaries derived from 620 baseline samples, covering diverse architectures and optimization levels.
3. Comprehensive Evaluation: Testing against six representative BCSD models (Graph, Embedding, and Transformer-based) to identify specific architectural vulnerabilities.
4. FP-Triggering Mechanism: A novel greedy sampling strategy to induce False Positives with minimal instruction overhead.
5. Insights into Robustness: Detailed analysis linking model architecture and preprocessing pipelines to their susceptibility to specific transformations.

4. Key Results and Findings

A. Model Robustness Depends on the Pipeline

• Feature Dependency: Robustness is dictated by how the model captures semantics.
  • Graph-based models (Genius, Gemini): Highly robust against instruction reordering and semantic NOPs (which preserve the Control Flow Graph structure) but highly vulnerable to Control Flow Flattening and Bogus Control Flow, which disrupt the CFG.
  • Embedding/Sequence models (Asm2Vec, Trex, BinShot): More vulnerable to instruction reordering and basic block shuffling. However, Asm2Vec showed surprising resilience to junk code insertion due to its random-walk mechanism, which naturally skips dead code paths.
  • BinShot: Surprisingly robust against LLVM-based obfuscation (CFG perturbations) but highly susceptible to basic block reordering, suggesting it relies heavily on static instruction sequences rather than dynamic execution traces.

B. The "Transformation Budget" Constraint

The effectiveness of attacks is bounded by the model's input constraints (e.g., max token/instruction limits).

• FN Attacks: Successful against most models with minimal overhead.
• FP Attacks: Highly effective. The greedy sampling strategy achieved up to 100% success rate in triggering False Positives.
  • Minimal Perturbation: On average, only 14.75 additional instructions (approx. 57 bytes) were needed to fool the target model.

C. Transferability

• FP-triggering perturbations crafted for BinShot transferred effectively to other models, particularly those with similar architectures (e.g., Trex, another BERT-based model).
• Models relying on CFGs (Genius, Gemini) were more resilient to transferred attacks than instruction-sequence-based models.

D. XAI Insights

• SHAP Analysis: After FP-triggering, Shapley values for instructions converged near zero, indicating the model's decision boundary was blurred, making the dissimilar functions appear similar.
• Saliency Maps: The introduction of adversarial prefixes reduced the saliency (importance) of critical original instructions, effectively "distracting" the model's attention mechanism.

5. Significance and Implications

• Vulnerability of MLaaS: The findings suggest that Binary Code Similarity Detection as a Service (BCSD-as-a-Service) is vulnerable to relatively simple, semantics-preserving obfuscations.
• Design Guidelines: To build robust BCSD models, developers must:
  • Combine static features (CFGs) with dynamic features (execution traces) to resist both CFG manipulation and instruction reordering.
  • Be aware that "minimal" perturbations can be devastating.
• Future Defenses: The paper suggests that adversarial training using diverse semantics-preserving transformations and hybrid feature extraction (static + dynamic) are necessary paths forward to improve model resilience.

In conclusion, the paper demonstrates that current deep learning models for binary analysis are fragile. While they excel at detecting similarity in clean code, they can be easily misled by adversaries who understand the specific architectural biases of the model, often with very low-cost code modifications.