PaperlayerView exact revision on arXiv

Source-linked AI summary

Neural Machine Translation Inspired Binary Code Similarity Comparison beyond Function Pairs

Fei Zuo, Xiaopeng Li, Patrick Young, Lannan Luo, Qiang Zeng, Zhexin Zhang

arXiv:1808.04706v2cs.SEcs.CLcs.CRcs.PL

TL;DR

The paper addresses cross-architecture basic-block semantic comparison and code containment beyond function pairs. It adapts NMT-style embeddings and LSTMs into INNEREYE, which reportedly outperforms existing approaches on basic-block comparison and handles containment case studies effectively.

  • Problem

    The paper asks whether semantically similar basic blocks and contained code components can be identified across different ISAs, extending analysis beyond function pairs.

  • Method

    INNEREYE uses instruction embeddings and LSTM-based cross-architecture basic-block comparison, then applies it to path- and component-level containment analysis.

  • Results

    INNEREYE-BB reportedly outperforms existing approaches in accuracy, efficiency, and scalability, while INNEREYE-CC successfully resolves cross-architecture code-similarity case studies.

  • Takeaways & Limitations

    The research demonstrates that NLP methodologies can be adapted to large-scale cross-architecture binary code similarity analysis.

Abstract

from arXiv · show

Binary code analysis allows analyzing binary code without having access to the corresponding source code. A binary, after disassembly, is expressed in an assembly language. This inspires us to approach binary analysis by leveraging ideas and techniques from Natural Language Processing (NLP), a rich area focused on processing text of various natural languages. We notice that binary code analysis and NLP share a lot of analogical topics, such as semantics extraction, summarization, and classification. This work utilizes these ideas to address two important code similarity comparison problems. (I) Given a pair of basic blocks for different instruction set architectures (ISAs), determining whether their semantics is similar or not; and (II) given a piece of code of interest, determining if it is contained in another piece of assembly code for a different ISA. The solutions to these two problems have many applications, such as cross-architecture vulnerability discovery and code plagiarism detection. We implement a prototype system INNEREYE and perform a comprehensive evaluation. A comparison between our approach and existing approaches to Problem I shows that our system outperforms them in terms of accuracy, efficiency and scalability. And the case studies utilizing the system demonstrate that our solution to Problem II is effective. Moreover, this research showcases how to apply ideas and techniques from NLP to large-scale binary code analysis.

I. INTRODUCTION

The paper applies NLP-inspired neural methods to cross-architecture binary similarity, addressing both basic-block semantic comparison and code containment 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.

II. RELATED WORK

Prior binary-similarity systems largely target mono-architecture analysis or cross-architecture function equivalence, leaving cross-architecture containment beyond function pairs insufficiently addressed.

  • 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.
  • 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.
  • 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.
  • 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.
  • 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.

IV. INSTRUCTION EMBEDDING GENERATION

The instruction-embedding stage adapts skip-gram word embeddings to assembly instructions, learning contextual vectors that support neural basic-block representation.

  • 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.
  • IV. INSTRUCTION EMBEDDING GENERATION: 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.
  • 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.
  • A. Background: Word Embedding: 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.
  • A. Background: Word Embedding: 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.
  • A. Background: Word Embedding: 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.
  • A. Background: Word Embedding: 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.
  • A. Background: Word Embedding: 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.

B. Challenges

Instruction embeddings address two challenges in applying NLP techniques to binary code: instruction streams must represent blocks, and preprocessing must reduce out-of-vocabulary cases.

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

D. Training Instruction Embedding Model

The model learns instruction representations and uses a Siamese LSTM architecture to encode cross-architecture basic blocks, including variable-length sequences, for similarity comparison.

  • D. Training Instruction Embedding Model: Instruction embeddings are learned with skip-gram negative sampling from architecture-specific BISs generated from functions.
  • D. Training Instruction Embedding Model: The instruction embedding matrix W ∈R^de×V stores one vector per instruction in the architecture-specific vocabulary.
  • V. BLOCK EMBEDDING GENERATION: Simply summing instruction embeddings cannot handle cross-architecture differences because equivalent instructions may have very different embeddings.
  • 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.
  • 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.
  • B. Cross-lingual Basic-block Embedding Model Architecture: Each LSTM processes instruction embeddings sequentially and outputs a final hidden-state representation of the basic block.
  • B. Cross-lingual Basic-block Embedding Model Architecture: The model accepts blocks with different and example-dependent sequence lengths, updating memory, input, forget, and output components at each step.
  • B. Cross-lingual Basic-block Embedding Model Architecture: Training uses SGD on labeled block pairs, and convergence of AUC terminates training; similarity is measured from the resulting block embeddings.

C. Challenges

Learning block embeddings requires labeled similar and dissimilar pairs, but establishing basic-block ground truth is difficult and model hyperparameters require examination.

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

D. Building Dataset

The dataset pairs equivalent blocks through shared compiler-generated identifiers and constructs dissimilar examples using same-architecture n-gram similarity thresholds.

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

VI. PATH/CODE COMPONENT SIMILARITY COMPARISON

INNEREYE addresses cross-architecture code-component containment by combining cross-lingual basic-block embeddings with path-based similarity comparison. It searches candidate target paths and aggregates their similarity into a component score.

  • 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.
  • 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.
  • Path Similarity Comparison: 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.
  • 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.
  • 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.
  • 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.

VII. EVALUATION

The evaluation examines INNEREYE across accuracy, efficiency, scalability, preprocessing, embedding quality, and cross-architecture code-component search. It uses cross-architecture basic-block datasets and reports low post-preprocessing OOV rates.

  • 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.
  • 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.
  • 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.
  • 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.
  • Out-Of-Vocabulary Instructions: 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.
  • Out-Of-Vocabulary Instructions: The authors state that preprocessing provides good instruction coverage and make the trained model publicly available for reuse.

D. Qualitative Analysis of Instruction Embeddings

The embedding analysis finds architecture-specific clustering alongside semantic relationships across ISAs. Accuracy experiments show INNEREYE-BB outperforming a manually selected-feature SVM on the reported testing subsets.

  • 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.
  • D. Qualitative Analysis of Instruction Embeddings: The x86 instruction MOVZBL EXC,<TAG>[RCX+0] is close to neighboring mov-family instructions in the embedding space.
  • D. Qualitative Analysis of Instruction Embeddings: Analogical tests compare eight x86 instructions with similar ARM counterparts using cosine distances between instruction embeddings.
  • 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.
  • E. Accuracy of INNEREYE-BB: 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.
  • E. Accuracy of INNEREYE-BB: 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.
  • E. Accuracy of INNEREYE-BB: 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.

F. Hyperparameter Selection for INNEREYE-BB

Hyperparameter experiments assess training duration, embedding dimensions, network depth, and recurrent-unit type. The reported choices balance accuracy against computational cost.

  • 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.
  • 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.
  • Embedding Dimensions: 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.
  • 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.
  • Network Hidden Unit Types: LSTM and GRU outperform basic RNN, with LSTM producing the highest AUC values.

G. Efficiency of INNEREYE-BB

INNEREYE-BB achieves practical training and testing efficiency, substantially outperforming symbolic execution in block-comparison speed while supporting effective code-component searches.

  • 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.
  • Training Time: 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.
  • 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.
  • Testing Time: 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.
  • 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.

VIII. DISCUSSION

The discussion highlights INNEREYE’s broader contribution to binary analysis while identifying compiler diversity and obfuscation as unevaluated boundaries.

  • 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.
  • Limitations: 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.
  • 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.
  • 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.
Loading 1808.04706v2…