Fast Cross-Platform Binary Code Similarity Detection Framework Based on CFGs Taking Advantage of NLP and Inductive GNN

Jinxue Peng, Yong Wang, Jingfeng Xue, Zhenyan LiuChinese 2024 · DOI

Abstract

Cross-platform binary code similarity detection aims at detecting whether two or more pieces of binary code are similar or not. Existing approaches that combine control flow graphs (CFGs)-based function representation and graph convolutional network (GCN)-based similarity analysis are the best-performing ones. Due to a large amount of convolutional computation and the loss of structural information, the use of convolution networks will inevitably bring problems such as high overhead and sometimes inaccuracy. To address these issues, we propose a fast cross-platform binary code similarity detection framework that takes advantage of natural language processing (NLP) and inductive graph neural network (GNN) for basic blocks embedding and function representation respectively by simulating extracting structural features and temporal features. GNN's node-centric and small batch is a suitable training way for large CFGs, it can greatly reduce computational overhead. Various NLP basic block embedding models and GNNs are evaluated. Experimental results show that the scheme with long short term memory (LSTM) for basic blocks embedding and inductive learning-based GraphSAGE(GAE) for function representation outperforms the state-of-the-art works. In our framework, we can take only 45% overhead. Improve efficiency significantly with a small performance trade-off.

Introduction

Binary code similarity detection (BCSD) is a critical component in modern cybersecurity, facilitating malware identification, vulnerability discovery, and software patch analysis. The primary challenge in BCSD is that source code manifests differently across various architectures (e.g., x86 vs. ARM) and optimization levels. While current state-of-the-art solutions utilize Control Flow Graphs (CFGs) and Graph Convolutional Networks (GCNs), they often suffer from high computational overhead due to their transductive nature and potential information loss regarding instruction sequences.

Methodology

The proposed framework addresses these limitations through a four-phase approach designed for speed and structural integrity:

  1. Pre-processing: Binaries are disassembled into instruction sequences and CFGs using Radare2. Memory and immediate addresses are standardized to minimize noise.
  2. Basic Block Embedding: Assembly instructions are treated as a language. The framework employs Long Short-Term Memory (LSTM) networks to capture the temporal features—the specific sequential order of instructions—within basic blocks.
  3. Function Representation: The framework utilizes an Inductive Graph Neural Network (specifically GraphSAGE, referred to as GAE in this study). Unlike transductive GCNs, inductive learning uses neighbor sampling and mini-batches, allowing the model to generate embeddings for unseen nodes without full-graph retraining.
  4. Invalid Node Filtering: A custom algorithm prunes padding nodes used for data normalization, ensuring the GNN focuses only on meaningful data.
The proposed framework architecture from binary code to similarity value.

Experimental Setup

The framework was evaluated using the Restricted Compiler Dataset, featuring open-source libraries like OpenSSL, binutils, and curl. Code was compiled for AMD64 using multiple compilers (gcc-3.4, gcc-5.0, clang3.9) and all four standard optimization levels (O0-O3). The evaluation focused on two subsets: Dataset A (~56k blocks) and Dataset B (~25k blocks).

Results and Discussion

Experimental results demonstrate that the shift to inductive learning is the primary driver of efficiency. The framework requires only 45% of the time overhead compared to the state-of-the-art baseline (Massarelli et al.), representing a 55% reduction in computational cost.

Running time comparison showing the efficiency of the proposed configurations against the baseline.

Key findings include:

  • Temporal Logic: LSTM outperformed CodeBERT for basic block embedding, suggesting that the strict sequential relationship of assembly instructions is more critical for similarity detection than high-level semantic clustering.
  • Performance Trade-off: The LSTM + GAE configuration achieved an F1-score between 83.2% and 83.5%. While slightly lower than the baseline's 87%, the massive efficiency gains make it more viable for real-world, large-scale deployments.
  • Hyperparameters: Optimal performance was achieved with a sampling depth of 2 layers and 25 neighbors per node.

Conclusion

By combining NLP-based temporal feature extraction with inductive GNNs, this framework significantly improves the efficiency of cross-platform binary similarity detection. Future work will explore the integration of Function Call Graphs (FCGs) to capture higher-level semantic interactions and enhance resilience against code obfuscation.

Summary updated

Abstract

Cross-platform binary code similarity detection aims at detecting whether two or more pieces of binary code are similar or not. Existing approaches that combine control flow graphs (CFGs)-based function representation and graph convolutional network (GCN)-based similarity analysis are the best-performing ones. Due to a large amount of convolutional computation and the loss of structural information, the use of convolution networks will inevitably bring problems such as high overhead and sometimes inaccuracy. To address these issues, we propose a fast cross-platform binary code similarity detection framework that takes advantage of natural language processing (NLP) and inductive graph neural network (GNN) for basic blocks embedding and function representation respectively by simulating extracting structural features and temporal features. GNN's node-centric and small batch is a suitable training way for large CFGs, it can greatly reduce computational overhead. Various NLP basic block embedding models and GNNs are evaluated. Experimental results show that the scheme with long short term memory (LSTM) for basic blocks embedding and inductive learning-based GraphSAGE(GAE) for function representation outperforms the state-of-the-art works. In our framework, we can take only 45% overhead. Improve efficiency significantly with a small performance trade-off.
BibTeX
@inproceedings{peng2024fast,
  author = {Jinxue Peng and Yong Wang and Jingfeng Xue and Zhenyan Liu},
  title = {{Fast Cross-Platform Binary Code Similarity Detection Framework Based on CFGs Taking Advantage of NLP and Inductive GNN}},
  booktitle = {Chinese},
  year = {2024},
  doi = {10.23919/cje.2022.00.228},
}
Figure