Neural Network-based Graph Embedding for Cross-Platform Binary Code Similarity Detection

By Xiaojun Xu, Chang Liu, Qian Feng, Heng Yin, Le Song, Dawn Song. 2017

700 citations recorded by the source corpus.

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.

Subfields: Information Systems, Software, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Information Systems

In Software

In Signal Processing

Citations in the corpus

Attention-based Graph Neural Network for Semi-supervised Learning (2018, methodology): “GNNs have been successfully applied in diverse applications such as molecular activation prediction [19], community detection [9], matrix completion [6], combinatorial optimization [14, 34], and detecting similar binary codes [44].”
LEMNA: Explaining Deep Learning based Security Applications (2018, methodology): “So far, researchers have successfully applied deep neural networks to train classifiers for malware classification [2, 16, 21, 48, 68], binary reverse-engineering [15, 52, 71] and network intrusion detection [24, 62], which all achieved an exceptionally high accuracy.”
Asm2Vec: Boosting Static Representation Robustness for Binary Clone Search against Code Obfuscation and Compiler Optimization (2019, neutral): “[35] proposes a graph convolution approach.”
Neural Code Comprehension: A Learnable Representation of Code Semantics (2018, methodology): “As for representing the context of a token, which is necessary for training embeddings, some works rely on lexicographical locality [2, 18, 20], whereas others exploit the structural nature of code, using Data Flow Graphs [4], Control Flow Graphs [51, 53, 64], Abstract Syntax Trees (ASTs) [12, 30], ”
Graph Matching Networks for Learning the Similarity of Graph Structured Objects (2019, methodology): “Xu et al. (2017) in particular proposed an embedding method based on graph neural networks, starting from some hand selected feature vectors for each node.”
Log2vec: A Heterogeneous Graph Embedding Based Approach for Detecting Cyber Threats within Enterprise (2019, methodology): “utilize this kind of graph embedding to compute the similarity of two binary functions from different platforms [59].”
Graph-based Security and Privacy Analytics via Collective Classification with Joint Weight Learning and Propagation (2018, background): “We note that some security problems [42]–[44] can be modeled as graph analytics other than collective classiﬁcation.”
Superion: Grammar-Aware Greybox Fuzzing (2018, positive): “Another thread of work focuses on improving the efﬁciency of fuzzing, e.g., seed selection [56], seed scheduling [9, 66], parameter tuning [10, 35], directed fuzzing [8, 12, 13] to reproduce crashes or assess potential bugs found by vulnerable code matching [11, 68], and operating primitives [67].”
Combining Graph Neural Networks With Expert Knowledge for Smart Contract Vulnerability Detection (2021, background): “Recently, [34], [35], [46], [47] attempt to applyGNNs to program analysis issues.”
CSI NN: Reverse Engineering of Neural Network Architectures Through Electromagnetic Side Channel (2019, background): “Machine learning, and more recently deep learning, have become hard to ignore for research in distinct areas, such as image recognition [25], robotics [21], natural language processing [47], and also security [53, 26] mainly due to its unquestionable practicality and effectiveness.”
NL2Type: Inferring JavaScript Function Types from Natural Language Information (2019, background): “Embeddings can be learned, e.g., from a graph representation of code [51], by randomly walking a control-ﬂow graph [52], by walking an abstract syntax tree [53], or from program executions [54].”