A Cross-Architecture Instruction Embedding Model for Natural Language Processing-Inspired Binary Code Analysis

I Introduction

When the source code of programs is not available, binary code analysis becomes indispensable for a variety of important tasks, such as plagiarism detection , malware classification , and vulnerability discovery . Increasingly, software is cross-compiled for various architectures. For example, hardware vendors often use the same code base to compile firmware for different devices that operate on varying architectures (e.g., x86 and ARM): this could cause a single vulnerability at source-code level to spread across binaries across diverse devices. As a result, cross-architecture binary code analysis has become an emerging problem that draws great attention . Analysis of binaries across instruction set architectures (ISAs), however, is non-trivial: binaries of varying ISAs differ greatly in instruction sets; calling conventions; general- and special- purpose CPU register usages; and memory addressing modes.

A binary, after being disassembled, is expressed in an assembly language. Given this insight, binary code analysis can be approached by borrowing ideas and techniques of Natural Language Processing (NLP)—a rich area focused on processing texts from various natural languages . In many NLP tasks, words are first often converted into word embeddings (i.e., high-dimensional vectors) to facilitate further processing . A word’s embedding is able to capture the contextual semantic meaning of the word; thus, words that have similar contexts have embeddings that appear close together in the high-dimensional space .

We regard instructions as words in NLP-inspired binary code analysis, and thus aim to represent instructions as embeddings as well. To facilitate cross-architecture binary code analysis, our goal is that similar instructions, regardless of their architectures, have embeddings that are close in the high dimensional space. Specifically, we aim to learn semantic features for each instruction, such that instructions in one architecture with similar semantics are assigned similar vector representations (the mono-architecture objective); and additionally, instructions across different architectures with similar semantics have similar vector representations (the cross-architecture objective). We call such vector representations cross-architecture instruction embeddings.

Why Cross-Architecture Instruction Embeddings? The cross-architecture instruction embeddings capture semantic relations of instructions across architectures, and keep invariant among tasks. Thus, it has many potential applications to cross-architecture binary code analysis. Take the search of semantically equivalent functions as an example. Given a function in x86 that contains, for instance, the Heartbleed function, by searching for functions similar to it from a large database of functions of varying architectures, more vulnerability instances may be found. This question has gained intense research interest . A core subtask involved is the comparison of basic blocks across architectures. We will show how the proposed technique can be applied to resolving this subtask.

Moreover, many deep learning based NLP techniques take word embedding as inputs. Following the idea of NLP-inspired binary code analysis, the proposed instruction embedding model can be applied to, e.g., classifying binaries across architectures by feeding the instruction embeddings of the binaries into classic neural network structures that are used for classifying texts in NLP .

Our Approach. We propose to learn the cross-architecture instruction embedding through a joint learning approach. Specifically, our joint model utilizes both the context concurrence information present in the instruction sequences from the same architecture, and the semantically-equivalent signals exhibited in the instruction sequence pairs from different architectures. By jointly learning these two types of information, our model can achieve both the mono-architecture and cross-architecture objectives, and generate high-quality cross-architecture instruction embeddings that capture not only the semantics of instructions within an architecture, but also their semantic relationships across architectures.

We have implemented the novel cross-architecture instruction embedding model, and conducted a series of experiments to evaluate the quality of the learned instruction embeddings. Moreover, as a showcase, we apply the model to resolving one of the most fundamental problems for binary code similarity comparison, that is, semantics-based basic block similarity comparison. Our solution achieves AUC = 0.90. Recent work uses several manually selected statistic features (such as the number of instructions and the number of constants) of a basic block to represent it. However, a SVM classifier based on such features only achieves AUC = 0.85 for the same task. The trained models, datasets, and evaluation results are publicly available.https://github.com/nlp-code-analysis/cross-arch-instr-model

We summarize our contributions as follows:

To the best of our knowledge, this is the first work on building a uniform cross-architecture instruction embedding model that tolerates the significant syntactic differences across architectures.

We propose an effective joint learning approach to training the model, which makes use of both the information in the instruction sequences from the same architecture, and the semantically-equivalent signals exhibited in the instruction sequence pairs from different architectures.

We implement model, and the evaluation demonstrates the good quality of the learned instruction embeddings. Moreover, we apply the model to cross-architecture basic block similarity comparison and the solution outperforms the statistic feature based approach.

This research successfully demonstrates that it is promising to adapt NLP ideas and techniques to binary code analysis tasks. Just like word embeddings are critical for many NLP tasks, the proposed instruction embedding model can substantially facilitate NLP-inspired cross-architecture binary code analysis.

II Related Work

We expect the proposed model can be naturally applied to binary code similarity comparison. Existing binary code analysis techniques for code similarity comparison can be roughly divided into two classes: traditional approaches and machine learning-based ones.

Traditional approaches. Most traditional approaches work on a single architecture. First, static plagiarism detection or clone detection includes string-based , AST-based , token-based , and PDG-based . Source code-based approaches are inapplicable for closed-source software. Symbolic execution of binary code has been enabled by tools such as BitBlaze and BAP ; it is very accurate in extracting code semantics , but it is very computationally expensive and unscalable.

Recent works have applied traditional approaches to addressing the cross-architecture scenario . Multi-MH and Multi-k-MH are the first two methods for comparing functions of different ISAs. But their fuzzing-based basic-block similarity comparison and graph (i.e., CFG) matching-based algorithms are very expensive. discovRE boosts CFG-based matching process, but is still expensive. Both Esh and its successor use data-flow slices of basic blocks as the basic comparable unit. Esh uses SMT solver to verify function similarity, which makes it unscalable. In , binaries are lifted to IR for creating function-centric signatures.

Machine learning based approaches. Machine learning, including deep learning, has been applied to code analysis . Lee et al. propose Instruction2vec for converting assembly instructions to vector representations ; but their instruction embedding model can only work on a single architecture. Asm2Vec produces a numeric vector for each function, but can only work on a single architecture. We instead build a cross-architecture instruction embedding model which works for varying architectures.

A few works target cross-architecture binary code analysis . Some exploit the statistical aspects of code, rather than its semantics. For example, Genius and Gemini use some manually selected statistical features (e.g., the number of constants) to represent basic blocks, but they ignore the meaning of instructions and the dependency between them, resulting in significant loss of semantic information. INNEREYE-BB uses LSTM to encode each basic block into an embedding, but it needs to train a separate instruction embedding model for each architecture. Instead, we build a uniform cross-architecture instruction embedding model that tolerates the syntactic differences across architectures.

Summary. To the best of our knowledge, ours is the first work to learn cross-architecture instruction embeddings that capture semantic features invariant to specific tasks. Such instruction embeddings can be adopted to a variety of important code analysis tasks, and help us scale to more architectures.

III Background

Many NLP models applying deep learning techniques have been proposed to learn high-quality word embeddings, with Mikolov’s skip-gram (SG) and Continuous Bag Of Words (CBOW) gaining a lot of traction due to their relatively low memory use, and overall increased efficiency.

The SG model takes each word as the input and predicts the context corresponding to the word, while the CBOW model takes the context of each word as the input and predicts the word corresponding to the context. During training, a sliding window is applied on a text. Each model starts with a random vector for each word, and then gets trained when going over each sliding window. After the model is trained, the embeddings of each word become meaningful, yielding similar vectors for similar words. Due to their simplicity, both models can achieve very good performances on various semantic tasks, and can be trained on a desktop computer at billions of words per hour.

III-B Multilingual Word Embeddings

A wide variety of multilingual NLP tasks, including machine translation , entity clustering , and multilingual document classification , have motivated recent work in training multilingual word representations where similar-meaning words in different human languages are embedded close together in the same high-dimensional space.

Different approaches have been proposed to training multilingual word embeddings. For example, one category of approaches is based on multilingual mapping, where word embeddings are first trained on each language independently and a mapping is then learned to transform word embeddings from one language to another . Another category attempts to jointly learn multilingual word embeddings from scratch . Our cross-architecture instruction embedding model adapts the technique proposed in .

IV Cross-Architecture Instruction Embedding Model

In light of the idea of NLP-inspired binary code analysis, we regard instructions as words. An instruction includes an opcode (specifying the instruction operation) and zero or more operands (specifying registers, memory locations, or literal data). For example, mov ebp, esp is an instruction where mov is an opcode and both ebp and esp are operands. Note that the assembly code in this paper adopts the Intel syntax.

Our goal in building the instructions model is to achieve both the mono-architecture and cross-architecture objectives. That is, we want the learned cross-architecture instruction embeddings not only to preserve the clustering properties mono-architecturally (instructions in one architecture with similar semantics are close together in the vector space), but also exhibit the semantic relationships across different architectures (instructions across architectures with similar semantics are close together).

IV-B System Overview

Our proposed cross-architecture instruction embedding model adapts the joint learning approach in , consisting of a mono-architecture component and a multi-architecture component. The mono-architecture component utilizes the context concurrence information present in the input instruction sequences from the same architecture (Section IV-C); and the multi-architecture component learns the semantically-equivalent signals exhibited in the equivalent instruction sequence pairs from varying architectures (Section IV-D).

An instruction sequence in our work is a basic block, as we regard instructions as words and basic blocks as sentences. Note that we do not consider a function as a sentence, as a function cannot be treated as a straight-line sequence: when a function is invoked, its instructions are not executed sequentially.

Handling out-of-vocabulary (OOV) instructions. The issue of OOV words is a well-known problem in NLP, and it exacerbates significantly in our case as constants, address offsets, labels, and strings are frequently used in instructions. To address it, instructions are preprocessed using the following rules: (1) Numerical constant values are replaced with 0, and the minus signs are preserved. (2) String literals are replaced with . (3) Function names are replaced with FOO. (4) Other symbol constants are replaced with .

Joint objective function. Below is our joint objective function:

In this equation, each mono-architecture component, Mono${}_{a_{i}}$ ($\forall i\in\{1,...N\}$) aims to capture the clustering property of the corresponding architecture $a_{i}$, where $J(\texttt{Mono}_{a_{i}})$ is the objective function of Mono${}_{a_{i}}$. Each multi-architecture component, Multi${}_{<a_{i},a_{j}>}$ ($\forall i,j\in\{1,...N\}$, $i\neq j$), is used to learn the semantic relationships across architectures, where $J(\texttt{Multi}_{<a_{i},a_{j}>})$ is the objective function of Multi${}_{<a_{i},a_{j}>}$. The $\gamma$ and $\beta$ hyperparameters balance out the influence of the mono-architecture components over the multi-architecture one.

Specifically, if there are only two architectures, e.g., x86 and ARM, the joint objective function becomes:

IV-C Mono-Architecture Component

Any word embedding model can be a candidate to be selected to build the mono-architecture component . Based on our experiment, we adopt the CBOW model as implemented in word2vec , which achieves better performance than the skip-gram model.

The CBOW model predicts a current instruction based on its context. During training, a sliding window with size $n$ is employed on an instruction sequence. The context of a current instruction $e_{t}$ is defined as $n$ instructions before and after $e_{t}$ within the corresponding sliding window. The CBOW model contains three layers. The input layer corresponds to the context. The hidden layer corresponds to the projection of each instruction from the input layer into the weight matrix, which is then projected into the third output layer. The final step is the comparison between the output and the current instruction in order to correct its vector representation based on the back propagation of the error gradient. Thus, the objective of the CBOW model is to maximize the following equation:

where $T$ is the length of the instruction sequence, and $n$ the size of the sliding window.

After the model is trained on many sliding windows, similar instructions tend to have embeddings that appear close together in the high-dimensional vector space.

IV-D Multi-Architecture Component

We adopt the CBOW model to build our multi-architecture component. Our cross-architecture instruction embedding model is extended from the CBOW model as implemented in word2vec, and is effective in learning instruction representations both mono-architecturally and multi-architecturally.

Figure 1 shows how our cross-architecture instruction embedding model works. The input is a pair of semantically-equivalent basic blocks, each of which is a sequence of instructions: the instruction sequence of the basic block compiled for x86 is {callq foo; moveq [rip+],rax; testq rax,rax; je }, and the instruction sequence of the block compiled for ARM is {bl foo; str r0,[r7]; cmp r0,0; beq }. Note that the instruction sequences may be of different lengths, and the lengths can vary from example to example; both can be easily handled by the model.

To predict instructions cross-architecturally rather than only mono-architecturally as in the standard CBOW model (Section IV-C), we use the contexts in one architecture to predict the instructions in another architecture. For example, if we know that the instruction moveq [rip+],rax in x86 has the same meaning as the instruction str r0,[r7] in ARM, we can simply substitute str r0,[r7] and use the surrounding instructions—such as bl foo and cmp r0,0—to predict moveq [rip+],rax. Therefore, given an alignment link between an instruction $e_{1}$ in one architecture and an instruction $e_{2}$ in another architecture, our cross-architecture model uses the neighbors of the instruction $e_{2}$ to predict the instruction $e_{1}$, and vice versa. Then, $J(\texttt{Multi}_{<a_{i},a_{j}>})$ in Equation 1, where $a_{i}$ and $a_{j}$ represent two different architectures, is also the objective function in Equation 3.

The challenge here is how to find the alignment links between instructions. There are two solutions. (1) A simple way is to assume linear alignments between instructions across architectures. That is, each instruction in one sequence $M$ at position $i$ is aligned to the instruction in another sequence $N$ at position $i\times|N|/|M|$, where $|M|$ and $|N|$ are the length of the corresponding sequences. (2) Another way is to determine the alignment links based on the opcode contained in each instruction. For example, from the opcode references of x86 and ARM , we can find that moveq from x86 and str from ARM can be used to store data in registers; thus, it is reasonable to align an instruction containing moveq with another instruction containing str. Then, a dynamic programming algorithm similar to the solution to finding the Longest Common Subsequence can be used to determine the best alignment between two sequences.

We adopt the first solution in our current implementation. Our preliminary results show that the model has good performance. We plan to explore the second solution to further improve the model as future work.

V Evaluation

This section presents our evaluation results. We first describe the dataset used in our evaluation (Section V-A) and discuss how the model is trained (Section V-B). We then conduct three different tasks to evaluate the quality of the learned model: (1) the mono-architecture instruction similarity task (Section V-C); (2) the cross-architecture instruction similarity task (Section V-D); and (3) as a concrete application, the cross-architecture basic-block similarity comparison task (Section V-E).

We train our model using basic blocks that are open-sourced by our prior workhttps://nmt4binaries.github.io , consisting of 202,252 semantically similar basic-block pairs. This dataset is prepared using OpenSSL (v1.1.1-pre1) and four popular Linux packages, including coreutils (v8.29), findutils (v4.6.0), diffutils (v3.6), and binutils (v2.30). Each program is compiled by two architectures (x86-64 and ARM) and clang (v6.0.0) with three different compiler optimization levels (O1-O3).

Two basic blocks of different ISAs compiled from the same piece of source code are considered as equivalent. To collect such ground truth, we modify the backends of various architectures in the LLVM compiler to add the basic-block boundary annotator, which annotates a unique ID for each block so that all blocks compiled from the same piece of source code, regardless of architecture, will obtain the same ID.

V-B Model Training

We use the following settings to train our cross-architecture instruction modelSee for more details on the parameters.: the instruction embedding dimension of 200, the sliding window size of 5, a subsampling rate of 1$e$-5, negative sampling with 30 samples, and the learning rate of 0.05. The model is trained for 10 epochs and the learning rate is decayed to 0 once training is done. We set the hyperparameters in Equation 1 to 1 for $\gamma$ and 4 for $\beta$.

V-C Mono-Architecture Instruction Similarity Task

Instruction Similarity Test. Unlike the case of word embedding models—which have many existing word-aligned corpora to evaluate the quality of word embeddings—we do not have such data. We thus create a set of manually-labeled instruction pairs from the same architecture to test the instruction embeddings. We consider a pair of instructions to be similar if they contain the same opcode, and a pair of instructions with different opcodes to be dissimilar; but a few exceptions exist—for example, in x86, cmp and test are different opcodes but are semantically similar, and thus instructions containing them tend to have similar embeddings. We randomly select 50 similar instruction pairs and 50 dissimilar ones, which are assigned with labels 1 and -1, respectively.

We then measure the similarity of two instructions based on their cosine similarity. Figure 4 shows the ROC curves and AUC values for ARM and x86: the AUC for ARM and x86 are around 0.828 and 0.749, respectively. It is worth noting that the accuracy of the monolingual word similarity test for the multilingual word embedding models are around 0.51 .

Nearest Neighbor Instructions. We then randomly select four ARM instructions, and search for the top two similar ARM instructions using cosine similarity. The result is shown in Table I. We omit the result for x86 due to space limits. It can be observed that the learned cross-architecture instruction embeddings still preserve the clustering property mono-architecturally. For example, our embeddings find very relevant neighbor instructions for the instruction ADD r1,r0,r7, such as ADD r1,r0,r5 and ADD r1,r0,r6.

V-D Cross-Architecture Instruction Similarity Task

Instruction Similarity Test. Similar to the previous experiment, we create a set of manually-labeled cross-architecture instruction pairs. We first determine the similar and dissimilar opcode pairs for different ISAs based on our prior knowledge and experience, and then select a set of similar and dissimilar instruction pairs based on whether their contained opcodes are (dis)similar or not. We then measure the similarity of two instructions using cosine similarity. Figure 4 shows the ROC result. Our model achieves AUC = 0.723 on this test.

Nearest Neighbor Instructions. We next randomly select six ARM instructions, and search for the top two similar x86 instructions for each ARM instruction based on their cosine similarity. The result is shown in Table II. We can see that similar instructions of different ISAs have embeddings close to each other, as predicted. For example, our embeddings find very relevant neighbor x86 instructions for the ARM instruction LDR r0,[r5+0], such as MOVL [rbp],eax and MOVL [r14+0],eax; both LDR from ARM and MOV from x86 can be used to load register from memory. Thus, the cross-architecture instruction embeddings successfully capture semantics of instructions across architectures.

Cross-Architecture Instruction Embedding Visualization. We next use t-SNE , a useful tool for visualizing high-dimensional vectors, to plot all the cross-architecture instruction embeddings in a two-dimensional space (due to space limits, we omit it here). A quick inspection shows that the instructions of different ISAs overlap together. Our prior work learns the mono-architecture instruction embeddings, where the instruction embeddings are architecture-specific (i.e., separate instruction embedding models need to be trained for each architecture), and the embeddings of different ISAs exist in different vector spaces (see Figure 9 in ). Instead, this work establishes a cross-architecture instruction embedding model, which learns embeddings in the same vector space.

We then visualize the embeddings of a set of similar instruction pairs. To this end, we randomly pick five x86 instructions; and for each x86 instruction, we select its similar counterpart from ARM based on our prior knowledge. We use t-SNE to plot their embeddings, as shown in Figure 5. It can be observed that most x86 and ARM instructions with similar meanings appear nearby: for example, the two similar x86 and ARM instructions, SUBQ RSP,0 and SUB SP,SP,0, are close together in the vector space.

Therefore, our cross-architecture instruction embeddings capture not only instruction semantics, but also semantic relationships across different architectures.

V-E Cross-Architecture Basic-Block Similarity Comparison Task

We next conduct the cross-architecture basic-block similarity comparison task to evaluate the quality of the learned model. We divide the dataset which contains 202,252 similar basic-block pairs into two parts: 90% of them are used for training; 10% of them and another 20,000 dissimilar block pairs (selected from the dataset open-sourced by our prior work ) for testing. Note that we only need similar block pairs for training; and for testing both similar and dissimilar pairs are used.

To measure the similarity of two basic blocks, we first compose all the instruction embeddings for each basic block, and then use the cosine similarity of the two composed embeddings to measure the basic block similarity. For simplicity, we use the sum of all the instruction embeddings of a basic block to represent it. This simple summation has proven to be a successful way of obtaining sentence or document embeddings that can be used as features in specific tasks such as answer sentence selection .

Figure 4 shows the ROC curve evaluated on the testing dataset; and our model achieves AUC = 0.90. Recent work looks at the statistical information of a basic block, and uses several manually selected features (such as the number of instructions and constants) of a basic block to represent it. But such an approach causes significant loss of information about the instructions being used and their dependencies. As a result, the statistics-based representation is efficient but inaccurate—a SVM classifier based on such features can only achieve AUC = 0.85 according to our prior work .

Therefore, our model, capturing the meaning of instructions and the dependency between them, can provide more precise basic-block representation and efficient comparison. It is worth mentioning that many prior systems built on basic-block comparison can benefit from our model.

VI Future Work

Improvements. Currently, heuristics are used to decide parameter values; e.g., the window size is set as 20. We will investigate the stability of the cross-architecture instruction embedding model with respect to different hyperparameters—including the sliding window size, the number of epochs, and the instruction embedding dimension.

Two solutions are proposed in Section IV-D to find the alignment links between instructions. We have tried the first simple solution, and plan to explore the second one to attest how important alignment information is in learning cross-architecture instruction embeddings.

The sliding window based on program paths can reflect the context information of instructions more precisely and may generate better instruction embeddings. We plan to explore dynamic analysis to generate a set of semantically-equivalent paths from two programs compiled for different architectures, and use them for training. We will evaluate the model trained on paths in terms of accuracy and efficiency.

Applications. A prominent application of cross-architecture instruction embeddings (similar to multilingual word embeddings) is that the induced instruction embeddings enable us to transfer a classifier trained on one architecture to another without any adaptation. We plan to investigate the transferability by applying our model to the cross-architecture program/function classification problem. For example, we will train a classifier using the code compiled for x86, and check whether it can directly work on ARM.

Moreover, we plan to apply our model to other important code analysis tasks, such as cross-architecture bug search, and compare our model to recent approaches .

VII Conclusion

To the best of our knowledge, this is the first work that aims to learn cross-architecture instruction embeddings that tolerate the syntactic differences of instructions across architectures and capture their important semantic features. We adopt a joint learning approach to building the instruction embedding model, such that instructions with similar semantics, regardless of their architectures, have embeddings close together in the vector space. Our instruction similarity tests and cross-architecture basic-block similarity comparison task demonstrate the good quality of the learned instruction embeddings. The proposed model may be applied to many cross-architecture binary code analysis tasks, such as vulnerability finding, malware detection, and plagiarism detection.

References