FUSION: Measuring Binary Function Similarity with Code-Specific Embedding and Order-Sensitive GNN

Hao Gao, Tong Zhang, Songqiang Chen, Lina Wang, Fajiang YuSymmetry 2022 · DOI

TL;DR

This paper introduces FUSION, a novel method for measuring binary function similarity. FUSION improves upon existing techniques by using code-specific pre-training tasks for language models to better understand assembly code semantics and an order-sensitive graph neural network to capture the control flow graph's structure more effectively. This leads to more accurate and efficient binary similarity detection, crucial for tasks like vulnerability analysis and malware detection.

What Problem Does This Paper Address?

Accurately determining the similarity between binary functions is a critical challenge in software security. When source code is compiled into machine code, valuable semantic information like function names, comments, and variable declarations is lost. Existing deep learning-based methods often rely on pre-trained language models (PTLMs) to embed assembly code instructions and graph neural networks (GNNs) to process control flow graphs (CFGs). However, these methods tend to treat assembly code as generic text, ignoring its unique code-specific features, and often fail to fully leverage the directional information within CFGs. This can lead to suboptimal performance in identifying similar binary functions, impacting the effectiveness of security tools.

Methods

FUSION tackles these limitations with two core innovations:

  • Code-Specific Pre-training Tasks (PTTs) for PTLMs: Instead of using standard PTLMs trained on natural language, FUSION adapts them using specialized PTTs. Crucially, it treats entire basic blocks (groups of sequential instructions) as the semantic unit, rather than individual instructions. This allows the PTLM to learn more nuanced semantic embeddings by considering a larger context. Two PTTs are introduced:
  • Masked Language Model (MLM): Adapted to mask tokens within a basic block and predict them, leveraging the block's internal context.
  • Neighboring Block Prediction (NBP): A novel task that predicts the adjacency of basic blocks within a CFG, considering both one-step and two-step neighbors, to better capture structural relationships.
  • Order-Sensitive Graph Neural Network (GNN): FUSION employs an enhanced GNN (based on GraphSAGE) that explicitly accounts for the direction of edges in the CFG. This is achieved by separately processing incoming and outgoing edges for each node (basic block) and using an attention mechanism to weigh the importance of different nodes in the CFG for the overall function representation. This approach captures the sequential and conditional flow of execution more accurately than traditional order-insensitive GNNs.

Datasets

The paper uses a large-scale dataset derived from a recent binary function set for similarity measurements, comprising over 1.5 million binary functions from 14 common libraries and applications compiled with various optimization levels (O0-O3) using GCC. The dataset was prepared by removing duplicate functions and creating similar pairs (from the same source code but different attributes) and dissimilar pairs in a 1:5 ratio. For evaluation, three distinct setups were used: XO (same compiler, different optimization), XC (different compiler versions), and XM (any binary from the same source code).

Key Insights and Ideas

  • Basic Blocks as Semantic Units: Treating basic blocks, rather than individual instructions, as the fundamental unit for semantic embedding significantly improves the PTLM's ability to capture code semantics. This is a key departure from prior work that often treated assembly instructions like natural language sentences.
  • Order Matters in CFGs: Explicitly incorporating the directionality of edges in the CFG is crucial for accurate function representation. FUSION's order-sensitive GNN demonstrates that this structural information is vital and can be captured efficiently.
  • Balancing Performance and Efficiency: FUSION achieves state-of-the-art performance while maintaining competitive efficiency, suggesting that its novel techniques do not introduce prohibitive computational overhead.

Key Results

FUSION significantly outperforms two state-of-the-art baselines (SAFE and PALMTREE) across three different evaluation setups (XO, XC, XM). The average AUC (Area Under the ROC Curve) improvements range from 3.19% to 10.01%. Specifically, FUSION shows stable performance across all datasets and projects, while baselines are less effective in certain setups. Ablation studies confirm that both the code-specific PTTs and the order-sensitive GNN contribute to FUSION's superior performance. In terms of efficiency, FUSION is comparable to the baselines, demonstrating a good balance between accuracy and speed.

Limitations and Future Work

The authors acknowledge that while FUSION shows promising results, further evaluation on more diverse datasets is warranted. They also suggest exploring the application of FUSION to downstream tasks in system security research, such as vulnerability detection and malware analysis. The paper also notes that while FUSION is efficient, SAFE is slightly faster, though at the cost of significantly lower performance.

Summary updated

BibTeX
@article{gao2022fusion,
  author = {Hao Gao and Tong Zhang and Songqiang Chen and Lina Wang and Fajiang Yu},
  title = {{FUSION: Measuring Binary Function Similarity with Code-Specific Embedding and Order-Sensitive GNN}},
  journal = {Symmetry},
  year = {2022},
  doi = {10.3390/sym14122549},
}
Figure