Neural Machine Translation Inspired Binary Code Similarity Comparison beyond Function Pairs

Motivation

• Binary analysis is often necessary when source code is unavailable, particularly for vulnerability discovery across diverse hardware architectures.Code reuse can spread one source-level vulnerability across many IoT devices, while obtaining their source code is often unlikely.Source: §I · p. 1

Code Containment

• The work extends basic-block comparison to cross-architecture containment, targeting code components that may comprise part of a function or multiple functions.This addresses cases where plagiarism or other reused code is not an entire function.Source: §I · pp. 1–2

Research Problems

• The paper defines Problem I as deciding whether basic blocks from different ISAs have similar semantics, and Problem II as detecting whether code is contained across ISAs.Problem I is treated as a core subtask, whereas Problem II is presented as new.Source: §I · pp. 1–2

Approach

• The authors map instructions to words and basic blocks to sentences, using an NMT-inspired cross-assembly neural model to learn semantic representations.The model uses embeddings and LSTM-based processing to capture instruction information and dependencies automatically.Source: §I · p. 2

Modeling Assumption

• The method treats executed function behavior as path-dependent rather than as an arbitrary straight-line instruction sequence.Compiler-scrambled paths can preserve function semantics, motivating path-aware treatment.Source: §I · p. 2

Evaluation

• INNEREYE-BB is evaluated for accuracy, efficiency, and scalability, while INNEREYE-CC is demonstrated through cross-architecture code-similarity case studies.The authors report large-margin improvements for INNEREYE-BB and successful containment-oriented case studies for INNEREYE-CC.Source: §I · p. 2

Mono-architecture Solutions

• Existing plagiarism and clone-detection methods include string-, token-, tree-, PDG-, and dynamic-birthmark-based approaches, with several relying on source code or a single architecture.These categories include API, system-call, function-call, instruction, and core-value birthmarks.Source: A. Traditional Code Similarity… · p. 3

Cross-architecture Solutions

• Cross-architecture systems such as Multi-MH, Multi-k-MH, discovRE, Genius, Gemini, and BinGo compare functions or use expensive CFG-oriented processing.The cited approaches employ fuzzing, CFG matching, pre-filtering, learned vectors, selective inlining, or partial traces.Source: A. Traditional Code Similarity… · p. 3, B. Machine Learning-based Code… · p. 3

Research Gap

• The paper claims to fill the combined gap of binary analysis, different architectures, and code containment, which prior systems do not jointly satisfy.It presents cross-architecture binary similarity comparison beyond function pairs as the target capability.Source: B. Machine Learning-based Code… · p. 3

Problem Scope

• The paper distinguishes code containment from function equivalence because a queried component may be part of a function or span multiple functions.Function-equivalence search is too limited when stolen code is inserted into other code.Source: §III · pp. 3–4

Proposed Architecture

• The proposed system examines semantics at basic-block, CFG-path, and code-component layers, storing block embeddings in an LSH database for online search.Multiple path pairs are combined into a component-level similarity score.Source: §III · pp. 3–4

IV. INSTRUCTION EMBEDDING GENERATION

• An instruction consists of an opcode and zero or more operands, and the paper represents each instruction with an instruction embedding.This transfers the NLP notion of word embeddings to assembly instructions.Source: §IV · p. 4
• The notation distinguishes functions, basic blocks, matrices, vectors, and individual instructions using capitalization and type-specific formatting.These conventions identify the objects used in the embedding equations.Source: §IV · p. 4

A. Background: Word Embedding

• Word embeddings represent contextual semantic meaning in a high-dimensional space, placing words with similar contexts near one another.The paper uses this contextual representation as the conceptual basis for instruction embeddings.Source: A. Background: Word Embedding · p. 4
• Skip-gram trains embeddings from words appearing within a sliding context window around a current word.The paper illustrates a window covering words before and after the current word.Source: A. Background: Word Embedding · pp. 4–5
• Assembly syntax in the paper follows Intel order: op dst, src(s).Operands are written after the opcode, with the destination preceding the source operands.Source: A. Background: Word Embedding · p. 4
• The skip-gram softmax uses the current word embedding to predict whether a candidate word occurs in its context.Context words receive a target probability of 1, and non-context words receive 0.Source: A. Background: Word Embedding · p. 5
• Training over a sequence maximizes a log-likelihood objective with stochastic gradient descent, but direct normalization is computationally expensive.The denominator sums over words in the context, motivating approximations.Source: A. Background: Word Embedding · p. 5
• The system adopts skip-gram with negative sampling to reduce training cost and obtain meaningful vectors for similar words.The passage also notes that skip-gram training is unsupervised and scalable to very large word streams.Source: A. Background: Word Embedding · p. 5

• Instruction embedding models must be trained from scratch because reusable natural-language embedding models do not apply directly to instructions.Source: B. Challenges · p. 5
• Out-of-vocabulary failures are especially challenging because instructions frequently contain constants, offsets, labels, and strings.Source: B. Challenges · p. 5
• A block-level instruction stream, or BIS, represents a basic block as its ordered list of instructions.Source: C. Building Training Dataset · p. 5
• The instruction-embedding training process uses BISs generated from functions, with each square in a BIS representing one instruction.Source: C. Building Training Dataset · p. 5, Figure 3 · p. 5
• Preprocessing replaces numeric constants with 0, strings with <STR>, function names with FOO, and other symbol constants with <TAG>.Source: C. Building Training Dataset · p. 5
• Applying the same preprocessing before embedding substantially reduces OOV cases, leaving very few during later testing after sufficient training data is collected.Source: C. Building Training Dataset · p. 5

D. Training Instruction Embedding Model

• Instruction embeddings are learned with skip-gram negative sampling from architecture-specific BISs generated from functions.Source: D. Training Instruction Embedding Model · p. 5
• The instruction embedding matrix W ∈R^de×V stores one vector per instruction in the architecture-specific vocabulary.Source: D. Training Instruction Embedding Model · p. 5

V. BLOCK EMBEDDING GENERATION

• Simply summing instruction embeddings cannot handle cross-architecture differences because equivalent instructions may have very different embeddings.Source: §V · p. 6

A. Background: LSTM in NLP

• LSTM is used to encode instruction sequences because it is designed to capture long-term dependencies, while basic blocks usually contain fewer than 500 instructions.Source: A. Background: LSTM in NLP · p. 6

B. Cross-lingual Basic-block Embedding Model Architecture

• The cross-lingual block model uses identical LSTMs in a Siamese architecture to compare basic blocks from different ISAs.Source: B. Cross-lingual Basic-block Embedding… · p. 6
• Each LSTM processes instruction embeddings sequentially and outputs a final hidden-state representation of the basic block.Source: B. Cross-lingual Basic-block Embedding… · pp. 6–7
• The model accepts blocks with different and example-dependent sequence lengths, updating memory, input, forget, and output components at each step.Source: B. Cross-lingual Basic-block Embedding… · p. 6
• Training uses SGD on labeled block pairs, and convergence of AUC terminates training; similarity is measured from the resulting block embeddings.Source: B. Cross-lingual Basic-block Embedding… · p. 7

• Basic-block ground truth is challenging because blocks lack names that can directly establish similarity labels.Source: C. Challenges · p. 7
• NMT hyperparameters cannot be assumed to transfer directly, so their values must be comprehensively examined for this model.Source: C. Challenges · p. 7

• Blocks compiled from the same source code for different ISAs are treated as equivalent training pairs.Source: 1) Generating Similar Basic-Block Pairs · p. 7
• LLVM backends are modified with a basic-block boundary annotator that marks block boundaries and assigns unique IDs across generated assembly blocks.Source: 1) Generating Similar Basic-Block Pairs · p. 7
• Sampling blocks with the same ID across architectures creates labeled similar pairs, producing a large collection after repeated sampling.Source: 1) Generating Similar Basic-Block Pairs · p. 7
• Different block IDs do not guarantee dissimilarity because independently identified blocks may still be semantically equivalent.Source: 2) Generating Dissimilar Basic-Block… · p. 7
• Same-architecture n-gram similarity at a common optimization level is used to identify blocks with low textual similarity.Source: 2) Generating Dissimilar Basic-Block… · p. 7
• An ARM block paired by ID with an x86 block is contrasted with another x86 block judged dissimilar by the n-gram procedure.Source: 2) Generating Dissimilar Basic-Block… · p. 7
• The dissimilar-pair procedure uses n = 4 and labels pairs dissimilar when their similarity score is smaller than 0.5.Source: 2) Generating Dissimilar Basic-Block… · p. 7

• Cross-architecture containment is harder than function-pair comparison because a critical component may be embedded inside a function.Existing work either targets one architecture or compares complete function pairs.Source: §VI · p. 7, B. Component Similarity Comparison · p. 8

Path Similarity Comparison

• The method decomposes query code into linearly independent paths and compares each against target-program paths using LCS over semantically equivalent basic blocks.Query paths are generated after unrolling each loop once and applying depth-first search.Source: §VI · p. 7, A. Path Similarity Comparison · p. 8
• For each query path, the highest LCS-based similarity across target paths becomes its path similarity score.The score uses the longest common subsequence of semantically equivalent basic blocks.Source: A. Path Similarity Comparison · p. 8

Starting-Block Identification

• Starting-block discovery searches target basic-block embeddings with locality-sensitive hashing and iteratively tests query blocks as possible starts.This addresses the unknown insertion location of the query component.Source: B. Component Similarity Comparison · p. 8

Component Similarity Score

• The final component similarity score is a path-length-weighted average of the individual path similarity scores.This combines evidence from multiple query paths.Source: B. Component Similarity Comparison · p. 8

Summary

• Integrating the embedding model with the existing path-comparison approach yields an effective and efficient cross-architecture component-similarity solution.The authors also identify benefits for systems that rely on basic-block similarity.Source: B. Component Similarity Comparison · p. 8

• INNEREYE is evaluated for accuracy, efficiency, and scalability, including basic-block similarity and cross-architecture code-component search.The evaluation covers Problem I and realistic Problem II applications.Source: §VII · p. 8

Experimental Setup

• The implementation uses word2vec instruction embeddings and a Keras model with TensorFlow as backend.The path-selection setup requires selected linearly independent paths to cover at least 80% of query basic blocks.Source: A. Experimental Settings · p. 8

Dataset

• Dataset I contains cross-architecture basic-block pairs labeled with similarity ground truth, compiled from x86-64 and ARM programs at optimization levels O1–O3.The dataset includes 437,104 x86 basic blocks and 393,529 ARM basic blocks.Source: B. Dataset · pp. 8–9

Out-Of-Vocabulary Instructions

• Preprocessing is evaluated for its effects on vocabulary growth and unseen instructions during later embedding generation.The vocabulary-growth analysis uses 6,115,665 basic blocks and 39,067,830 instructions.Source: C. Evaluation on Out-Of-Vocabulary… · p. 9
• 3.7% of later instructions are unseen after preprocessing, compared with 90% without preprocessing.The evaluation assigns a zero vector to an out-of-vocabulary instruction.Source: C. Evaluation on Out-Of-Vocabulary… · p. 9
• The authors state that preprocessing provides good instruction coverage and make the trained model publicly available for reuse.Source: C. Evaluation on Out-Of-Vocabulary… · p. 9

D. Qualitative Analysis of Instruction Embeddings

• t-SNE visualizations show x86 and ARM instructions clustering by architecture, indicating architecture introduces substantial syntactic variation.This architecture effect helps explain why cross-architecture detection is harder than single-architecture detection.Source: D. Qualitative Analysis of Instruction… · p. 9, Figure 9 · p. 10
• The x86 instruction MOVZBL EXC,<TAG>[RCX+0] is close to neighboring mov-family instructions in the embedding space.Source: D. Qualitative Analysis of Instruction… · p. 9
• Analogical tests compare eight x86 instructions with similar ARM counterparts using cosine distances between instruction embeddings.Source: D. Qualitative Analysis of Instruction… · pp. 9–10

E. Accuracy of INNEREYE-BB

• The ROC curves for the four testing datasets remain close to the left and top borders, indicating good accuracy for the base models.The evaluations use Dataset I and disjoint training, validation, and testing basic blocks.Source: E. Accuracy of INNEREYE-BB · p. 10, 2) Results · p. 10
• INNEREYE-BB also reports ROC results for large blocks with more than 20 instructions and small blocks with fewer than 5 instructions.The O3 subsets contain 221 large-block pairs and 2,409 small-block pairs.Source: E. Accuracy of INNEREYE-BB · p. 10
• INNEREYE-BB achieves higher AUC values than the SVM classifier using six manually selected block features.The feature-based representation loses instruction semantics and dependency information.Source: 3) Comparison with Manually Selected… · pp. 10–11
• Examples show INNEREYE-BB correctly classifying similar and dissimilar block pairs that the statistical feature-based SVM misclassifies.The cited examples are presented in Tables II and III.Source: 3) Comparison with Manually Selected… · p. 11

Number of Epochs

• AUC stabilizes and loss becomes nearly stable after epoch 20, indicating rapid attainment of good performance.The model was evaluated every 10 epochs during 200-epoch training.Source: 1) Number of Epochs · p. 11

Embedding Dimensions

• Instruction embedding dimensions above 100 have similar AUC values, so dimension 100 is selected as a computational trade-off.Higher dimensions increase training time.Source: 2) Embedding Dimensions · p. 11
• Block embedding dimensions of 10, 30, and 50 perform similarly, so dimension 50 is selected as a computational trade-off.Higher dimensions increase computational costs.Source: 2) Embedding Dimensions · p. 11

Network Depth

• Two- and three-layer LSTMs outperform a single-layer network, while their AUC values are close to each other.The authors choose network depth 2 because additional layers increase complexity without significant performance gains.Source: 3) Network Depth · pp. 11–12

Network Hidden Unit Types

• LSTM and GRU outperform basic RNN, with LSTM producing the highest AUC values.Source: 4) Network Hidden Unit Types · p. 12

Training Time

• Training time grows linearly with epochs and training samples, while more complex LSTM networks require more time per epoch.The study reports linear dependence on epochs and corpus or sample size, with deeper LSTMs taking longer per epoch.Source: 1) Training Time · p. 13
• Five and a half hours trains four two-layer models for 20 epochs, whereas single-layer models take about 40 minutes each and retain good performance.The four-model estimate uses the reported per-epoch times and 20 training epochs.Source: 1) Training Time · p. 13

Testing Time

• Network depth is the major contributor to testing computation time, while embedding dimension is also varied in the evaluation.Figure 14 examines testing time across network layers and block-embedding dimensions.Source: 2) Testing Time · p. 13, Figure 14 · p. 13
• 3700x to 140000x faster than symbolic execution, with an average speedup as high as 8000x, INNEREYE-BB markedly reduces block-comparison time.The comparison used 1,000 randomly selected block pairs.Source: 2) Testing Time · p. 13

Code Component Similarity Comparison

• INNEREYE identifies reused cross-architecture components effectively, including a 91% match completed within 2 seconds versus nearly one hour for CoP.The thttpd/sthttpd case study reports low scores below 4% for independently developed programs, while cryptographic searches found confirmed reuse.Source: H. Code Component Similarity Comparison · p. 13, 2) Cryptographic Function Detection · p. 14

Limitations

• The model was trained only on LLVM-compiled binaries, so performance on binaries produced by diverse compilers remains unevaluated.The authors state that compiler agnosticism is expected but reserved verification for future work.Source: §VIII · p. 14
• The study evaluated architectural and compilation-setting variation but did not evaluate code obfuscation at the basic-block level.The authors identify obfuscation handling without expensive symbolic execution as future work.Source: §VIII · p. 14

Broader Impact

• The block embedding model can benefit prior systems that rely on basic-block comparison or representation by providing precise and efficient block information.The discussion explicitly connects the model to several prior systems.Source: §VIII · p. 14

Contributions

• INNEREYE-BB uses instruction word embeddings and LSTM encoding to support cross-architecture basic-block comparison without manually selected features.INNEREYE-CC extends this capability to cross-architecture code containment.Source: §IX · p. 14