Source-linked AI summary
Neural Network-based Graph Embedding for Cross-Platform Binary Code Similarity Detection
Xiaojun Xu, Chang Liu, Qian Feng, Heng Yin, Le Song, Dawn Song
TL;DR
Cross-platform binary code similarity detection must identify similar functions across platforms for security applications, while existing graph-matching approaches are inefficient and difficult to adapt. Gemini uses neural graph embeddings and Siamese learning for similarity detection, outperforming prior approaches in accuracy and efficiency; in real-world evaluation, it identified 25 more vulnerable firmware images than Genius among top-50 results.
Problem
Cross-platform binary code similarity detection seeks to find semantically similar functions across platforms, but existing pairwise graph-matching approaches are inefficient and may reduce search accuracy.
Method
Gemini converts control-flow graphs with node attributes into embeddings using graph embedding networks combined in a Siamese architecture, with cosine distance measuring function similarity.
Results
25 more vulnerable firmware images than Genius were identified on average among top-50 results, while Gemini also outperformed state-of-the-art approaches in similarity accuracy, embedding generation time, and training time.
Takeaways & Limitations
Gemini's efficient retraining enables practical adaptation to new application scenarios and improves similarity-detection quality with additional supervision.
Takeaways & Limitations
Pairwise graph-matching baselines face codebook-size and search-accuracy constraints, including expensive codebook generation and unreliable pre-filtering.
Abstract
from arXiv · showhide
The problem of cross-platform binary code similarity detection aims at detecting whether two binary functions coming from different platforms are similar or not. It has many security applications, including plagiarism detection, malware detection, vulnerability search, etc. Existing approaches rely on approximate graph matching algorithms, which are inevitably slow and sometimes inaccurate, and hard to adapt to a new task. To address these issues, in this work, we propose a novel neural network-based approach to compute the embedding, i.e., a numeric vector, based on the control flow graph of each binary function, then the similarity detection can be done efficiently by measuring the distance between the embeddings for two functions. We implement a prototype called Gemini. Our extensive evaluation shows that Gemini outperforms the state-of-the-art approaches by large margins with respect to similarity detection accuracy. Further, Gemini can speed up prior art's embedding generation time by 3 to 4 orders of magnitude and reduce the required training time from more than 1 week down to 30 minutes to 10 hours. Our real world case studies demonstrate that Gemini can identify significantly more vulnerable firmware images than the state-of-the-art, i.e., Genius. Our research showcases a successful application of deep learning on computer security problems.
1 INTRODUCTION
Cross-platform binary code similarity detection is important for security applications, but graph-matching approaches are difficult to adapt and inefficient. Gemini addresses these issues with neural graph embeddings and achieves higher accuracy, faster embedding generation, shorter training, and better vulnerability search results.
- Motivation: 80.4% of vendor-issued firmware is released with multiple known vulnerabilities, underscoring the importance of cross-platform similarity detection for firmware vulnerability search.Vulnerabilities can spread across devices with diverse hardware architectures and software platforms.
- Limitations of Existing Approaches: Graph-matching approaches use manually designed similarity functions that cannot fit both plagiarism detection and vulnerability search scenarios.Small instruction differences may be treated differently depending on the application.
- Limitations of Existing Approaches: Graph-matching approaches are inevitably inefficient because their runtime is bounded by super-linear graph-matching algorithms.This limits the efficiency of similarity detection as graph size increases.
- Approach: Gemini converts control-flow graphs into embeddings with a graph embedding network combined with a Siamese architecture trained end-to-end for similarity detection.The architecture learns embeddings that are close for similar functions and farther apart for dissimilar functions.
- Training and Adaptation: Gemini’s task-independent model is trained on functions compiled from identical source code across platforms and compiler optimization levels, then can be retrained for task-specific supervision.Each retraining phase can be completed within 30 minutes, enabling adaptation to new application scenarios.
2 BINARY CODE SIMILARITY DETECTION
Cross-platform binary code similarity detection seeks to find semantically equivalent or similar functions across binary platforms, supporting security applications such as vulnerability search and plagiarism detection. Existing graph-matching and codebook-based methods face efficiency, adaptability, and accuracy limitations, motivating neural-network embeddings.
- 2.1 Motivation Problem: Cross-Platform Binary Code Search: The task searches a target corpus for binary functions similar or semantically equivalent to a query function across platforms.The query and corpus functions may come from different hardware architectures and software platforms.
- 2.1 Motivation Problem: Cross-Platform Binary Code Search: Cross-platform binary code search supports security applications including firmware vulnerability search and binary-code plagiarism detection.
- 2.1 Motivation Problem: Cross-Platform Binary Code Search: Effective similarity detection must operate directly on binaries, tolerate cross-platform syntax variation, and capture intrinsic function characteristics.
- 2.2 Existing Techniques: Graph matching is expensive because feature extraction and matching must be performed for binary-function comparisons.Pewny et al. use input-output pairs for basic blocks, while discovRE uses lighter syntax features and pre-filtering.
- 2.2 Existing Techniques: Codebook-based graph embedding is limited by costly codebook generation, codebook-size overhead, and approximate bipartite matching quality.The codebook’s scale constrains graph-encoding fidelity, while matching may not produce optimal results.
- 2.3 Neural Network-based Embedding Generation: The proposed neural network transforms attributed control-flow graphs into embeddings, enabling similarity computation through learned embedding distances rather than graph matching.The approach can be retrained with additional supervision to adapt to new tasks or scenarios.
- 2.3 Neural Network-based Embedding Generation: Neural-network embedding improves efficiency through cheap, parallelizable computation and avoids requiring inter-block attributes.The paper contrasts this with Genius, which performs bipartite matching against each codebook ACFG.
- 2.3 Neural Network-based Embedding Generation: Neural-network offline training avoids Genius’s quadratic distance-matrix construction and more than one week of codebook-generation time.
3 NEURAL NETWORK-BASED MODEL FOR EMBEDDING GENERATION
Gemini learns graph embeddings for binary functions so similarity can be measured between vectors rather than by fixed graph matching, while supporting task-specific adaptation through retraining.
- Solution overview: The model maps each function’s attributed control-flow graph to a vector embedding that captures information for similarity detection.Vertex embeddings are aggregated into a graph-level embedding.
- Solution overview: Existing graph embedding networks do not apply directly because code similarity is not a classification problem, requiring a novel training approach.The Siamese design trains embeddings by differentiating pairs of input graphs using similarity labels.
- Training and adaptation: A default policy enables large-scale pre-training from equivalent functions compiled across platforms and optimization levels, followed by task-specific retraining with limited expert labels.Newly added task-specific pairs can be sampled more often during a few additional training epochs.
- Graph embedding network: The graph-level embedding aggregates the p-dimensional vertex embeddings, using summation in this work while leaving other aggregation functions for future work.The network first computes one feature vector for each graph vertex, then combines them into the function embedding.
- Graph embedding network: Structure2vec recursively propagates vertex features through graph topology, producing vertex representations that incorporate graph characteristics and long-range feature interactions.Updates occur synchronously across vertices for several iterations.
- Overall architecture: Gemini uses a Siamese architecture with two identical Structure2vec networks whose shared parameters produce embeddings compared by cosine distance.Each network receives an ACFG and outputs its embedding; the networks remain identical during training.
4 EVALUATION
Gemini achieves strong accuracy across similarity detection, efficiency, hyperparameter, and real-world retraining evaluations. It substantially outperforms Genius while reducing extraction, embedding-generation, and training costs.
- Accuracy: Gemini significantly outperforms BGM and Genius on both large-graph and small-graph similarity testing subsets.The evaluation reports consistent observations across the two graph-size subsets.
- Hyperparameters: An embedding depth of 2 produces the largest AUC, while additional layers provide little further benefit.Structure2vec can be viewed as using embedding depth 1.
- Hyperparameters: An embedding size of 64 offers a performance-efficiency trade-off because sizes no smaller than 64 have similar ROC curves, while larger sizes cost more time.Even embedding size 16 remains more effective than Genius and BGM.
- Hyperparameters: 5 iterations suffice for strong graph information propagation, because graphs in the evaluated large-graph subset contain more than 10 vertices.The best performance occurs when the iteration count T is 5 or larger.
- Efficiency: 2400× to 16000× faster embedding generation is achieved by Gemini CPU compared with Genius multi-threaded, with an average speedup as high as 7000×.Gemini avoids expensive graph matching and reduces computation to the number of graph edges; sparse ACFGs make this nearly linear in graph size.
- Real-world evaluation: Over 80% top-50 accuracy and more than 25 additional vulnerable firmware images on average demonstrate the value of task-specific retraining.Retraining uses inspected top-K results as additional supervision and can be repeated for only a few iterations.
5 RELATED WORK
Related work spans raw binary features, graph matching, graph embeddings, and learning-based bug search. The paper positions Gemini against methods limited by expensive matching, fixed similarity functions, or difficulty incorporating additional supervision.
- Raw feature based bug search: Raw-feature methods match binary sequences or mnemonics without understanding code semantics and cannot tolerate opcode reordering.N-grams and N-perms are cited as early approaches in this category.
- Raw feature based bug search: Graph-isomorphism, symbolic-execution, and theorem-proving approaches are expensive for cross-architecture binary bug search.The cited systems include BinDiff, BinSlayer, BinHunt, and iBinHunt.
- Raw feature based bug search: MinHash and pre-filtering reduce some matching costs, but prior approaches remain too expensive at large scale or can produce many false negatives.The passage contrasts Pewny et al., DiscovRE, and other large-scale search approaches.
- Graph embedding: Graph embedding may represent either nodes or an entire graph; Gemini adopts whole-graph embedding for downstream analysis.Whole-graph embeddings map a graph to a vector used with machine-learning methods.
- Graph embedding: Kernel methods use fixed structural functions or graphical-model distributions, whereas Structure2vec provides the embedding-generation model used in this paper.The related work distinguishes subtree, subgraph, Weisfeiler-Lehman, Fisher, and probability-product kernels.
6 CONCLUSION
Gemini applies deep learning to binary code similarity detection and substantially outperforms prior approaches across reported evaluation dimensions. Its case studies also show practical gains in vulnerability discovery.
- Gemini outperforms state-of-the-art approaches by large margins in similarity detection accuracy, embedding generation time, and overall training time.
- Using retraining, Gemini identifies significantly more vulnerable firmware images than the state-of-the-art system Genius.
- The study showcases a successful application of deep learning to computer security problems.