PaperlayerView exact revision on arXiv

Source-linked AI summary

Trex: Learning Execution Semantics from Micro-Traces for Binary Similarity

Kexin Pei, Zhou Xuan, Junfeng Yang, Suman Jana, Baishakhi Ray

arXiv:2012.08680v3cs.CRcs.LGcs.SE

TL;DR

Binary function matching is difficult when architecture, optimization, and obfuscation change code, while existing approaches may not learn execution semantics. TREX learns approximate semantics from micro-traces and transfers that knowledge to matching; it reports gains over state-of-the-art tools across all three settings.

  • Problem

    Binary functions can differ across architectures, optimizations, and obfuscations, while learning-based approaches train on static code without observing execution semantics.

    Source: §I · p. 1

  • Method

    TREX pretrains a hierarchical Transformer on micro-traces to learn approximate execution semantics, then transfers that knowledge to match semantically similar functions.

    Source: §I · pp. 2–3

  • Results

    TREX outperforms state-of-the-art tools by 7.8%, 7%, and 14.3% in cross-architecture, optimization, and obfuscation function matching, respectively.

    Source: §I · p. 3

  • Takeaways & Limitations

    In 180 real-world firmware images, TREX helped uncover 16 CVEs not disclosed in previous studies.

    Source: §I · p. 3

Abstract

from arXiv · show

Detecting semantically similar functions -- a crucial analysis capability with broad real-world security usages including vulnerability detection, malware lineage, and forensics -- requires understanding function behaviors and intentions. This task is challenging as semantically similar functions can be implemented differently, run on different architectures, and compiled with diverse compiler optimizations or obfuscations. Most existing approaches match functions based on syntactic features without understanding the functions' execution semantics. We present Trex, a transfer-learning-based framework, to automate learning execution semantics explicitly from functions' micro-traces and transfer the learned knowledge to match semantically similar functions. Our key insight is that these traces can be used to teach an ML model the execution semantics of different sequences of instructions. We thus train the model to learn execution semantics from the functions' micro-traces, without any manual labeling effort. We then develop a novel neural architecture to learn execution semantics from micro-traces, and we finetune the pretrained model to match semantically similar functions. We evaluate Trex on 1,472,066 function binaries from 13 popular software projects. These functions are from different architectures and compiled with various optimizations and obfuscations. Trex outperforms the state-of-the-art systems by 7.8%, 7.2%, and 14.3% in cross-architecture, optimization, and obfuscation function matching, respectively. Ablation studies show that the pretraining significantly boosts the function matching performance, underscoring the importance of learning execution semantics.

I. INTRODUCTION

TREX addresses the difficulty of matching functions when compilation removes high-level information and architecture, optimization, or obfuscation changes their code. It learns approximate execution semantics from micro-traces, then transfers that knowledge to function matching.

I. INTRODUCTION

  • Binary matching is difficult when compilation removes high-level information and functions differ across architectures, optimizations, or obfuscations.Semantic function similarity has security uses including vulnerability detection, malware lineage, and forensics.Source: §I · p. 1
  • TREX pretrains on under-constrained micro-traces to learn instruction effects, then transfers that knowledge to match semantically similar functions without executing them during matching.The traces may contain infeasible states but still encode precise effects of individual instructions.Source: §I · p. 2
  • Masked language modeling predicts randomly masked instructions or values from micro-trace context, providing self-supervised training without manual labels.The micro-traces contain aligned instructions and corresponding program-state values.Source: §I · p. 2
  • TREX’s hierarchical Transformer models micro-trace values and long-range dependencies, supporting roughly 170× longer sequences and running 8× faster than existing neural architectures.The architecture is designed to learn approximate execution semantics from micro-traces.Source: §I · pp. 2–3
  • 7.8%, 7%, and 14.3% are TREX’s reported gains over state-of-the-art tools for cross-architecture, optimization, and obfuscation matching, respectively.The evaluation covers 1,472,066 functions from 13 projects and reports up to 8× faster runtime and 16 previously undisclosed CVEs found in firmware images.Source: §I · p. 3

II. OVERVIEW

The overview illustrates why syntax alone misses equivalence across architectures, compiler optimizations, and instruction substitution. It then explains how masked prediction on micro-traces can teach execution effects that help the model compare functions.

A. Challenging Cases

  • Cross-architecture, cross-optimization, and obfuscation cases require recognizing equivalent behavior despite different instructions, stack addresses, or arithmetic sequences.The examples include x86 versus ARM operations, equivalent stack locations, and instruction substitution.Source: A. Challenging Cases · p. 3

B. Pretraining Masked LM on Micro-traces

  • Masked LM trains on micro-traces by hiding random parts and predicting them from context, without manual labels.Self-supervision allows training and improvement using functions found in the wild, where other traces may expose instructions absent from one function’s trace.Source: B. Pretraining Masked LM on Micro-traces · p. 3
  • Predicting masked registers, values, and opcodes can reveal instruction effects and contextual constraints, such as mov assigning esp to ebp.The model recovers values associated with add, xor, and sub; randomized masking across code blocks and program states is intended to capture composite instruction-sequence effects.Source: B. Pretraining Masked LM on Micro-traces · p. 4

III. THREAT MODEL

TREX assumes stripped binaries can be disassembled and excludes packed binaries and virtualization-based obfuscation. Its methodology extends micro-execution across architectures and uses a micro-tracing procedure to produce function traces.

III. THREAT MODEL

  • The threat model assumes no source or debug symbols, but requires readily disassembled binaries and excludes packed binaries and virtualization-based obfuscation.Functions from the same source are treated as similar across architectures, compilers, optimizations, and obfuscation transforms.Source: §III · pp. 4–5

A. Micro-tracing Semantics

  • TREX extends micro-execution to x64, ARM, and MIPS and introduces a low-level IR to explain how it abstracts architectural assembly syntax.The implementation uses real assembly instructions, tokenized as model input; the IR is for discussing the tracing implementation.Source: A. Micro-tracing Semantics · p. 5, Figure 3 · p. 5
  • Micro-tracing initializes stack and code memory, randomizes ordinary registers, and executes instructions while mapping memory on demand.It skips invalid jumps and calls, skips nops, and stops at a return, completion, or timeout.Source: A. Micro-tracing Semantics · p. 5

B. Input Representation

TREX represents micro-traces as aligned code, value, position, and architecture sequences, then uses masked prediction to learn approximate execution semantics without labels.

B. Input Representation

  • The five input sequences encode assembly tokens, dynamic trace values, instruction and operand positions, and the input architecture.Instruction-position tokens are shared within an instruction, while opcode/operand-position tokens distinguish locations inside it.Source: B. Input Representation · pp. 5–6
  • Numeric literals are replaced by a special num token in the code sequence, while micro-trace values use byte-value encoding with a bi-LSTM.This reduces the code vocabulary and lets the value encoder represent dependencies between bytes.Source: B. Input Representation · p. 6

C. Pretraining with Micro-traces

  • Masked language modeling randomly masks code and value tokens and trains the model to predict both, without requiring additional labels.The value-prediction loss covers each of the eight bytes of a micro-trace value.Source: C. Pretraining with Micro-traces · pp. 6–7, Figure 4 · p. 6
  • Random masking windows can include neighboring tokens, while self-attention contextualizes token embeddings that encode approximate execution semantics for later matching.The learned contextual embeddings support code prediction during pretraining and function matching during finetuning.Source: C. Pretraining with Micro-traces · p. 7

D. Finetuning for Function Similarity

For finetuning, TREX processes each function’s static code with the pretrained model, then learns function embeddings from paired functions using a cosine-embedding objective.

D. Finetuning for Function Similarity

  • TREX feeds each function’s static code to the pretrained model and obtains an embedding sequence from its last self-attention layer.The two sequences correspond to the two functions in a pair.Source: D. Finetuning for Function Similarity · p. 7
  • A two-layer MLP transforms the average token embedding for each function into a function embedding.The output dimension can be chosen smaller than the token-embedding dimension to support efficient large-scale searching.Source: D. Finetuning for Function Similarity · p. 7
  • Finetuning minimizes cosine embedding loss: similar pairs use 1 − cosine similarity, while dissimilar pairs incur loss above margin ξ.The ground-truth pair label indicates whether the functions are similar or dissimilar.Source: D. Finetuning for Function Similarity · p. 7
  • After finetuning, TREX measures function similarity by the cosine similarity between the two function-embedding vectors.The function embedding is produced by applying the finetuned MLP and pretrained model to the function’s static code.Source: D. Finetuning for Function Similarity · p. 7

V. IMPLEMENTATION AND EXPERIMENTAL SETUP

The evaluation uses binaries from 13 open-source projects across architectures and compiler settings, with separate setup choices for pretraining, finetuning, and baseline comparisons.

V. IMPLEMENTATION AND EXPERIMENTAL SETUP

  • The dataset covers 13 projects compiled for four architectures and four optimization levels, with five obfuscation strategies evaluated on x64.The function-count table is scoped by project, architecture, optimization level, and obfuscation.Source: §V · pp. 7–8, Table I · p. 8
  • Micro-tracing runs each function three times with different register and memory initializations, then adds a dummy trace for pretraining.Each run has a 30-second timeout; the dummy trace encourages prediction from code context alone.Source: §V · p. 8
  • TREX is compared with SAFE and Gemini for cross-architecture matching, and with Asm2Vec and Blex for cross-optimization and obfuscation comparisons.Some baselines are compared using their reported results because trained models or usable implementations were unavailable.Source: §V · p. 8
  • AUC is the primary accuracy metric; Precision@1 and number of matched functions are also used when baseline systems require them.AUC evaluates the ROC curve across thresholds, avoiding dependence on a single similarity-score threshold.Source: §V · pp. 8–9
  • Pretraining excludes the project used for finetuning and evaluation, making the test setup more challenging than label-agnostic pretraining that could include those functions.The model retains the weights with the best validation perplexity for finetuning.Source: §V · p. 9
  • Finetuning uses 50,000 random function pairs per project, with 10% for training and nonduplicated functions across training and testing.Similar and dissimilar pairs are kept at roughly a 1:5 ratio.Source: §V · p. 9
  • The authors leave a more thorough study of TREX hyperparameters for future work, noting that no principled search method is currently available.Most hyperparameters are held fixed throughout the evaluation unless explicitly stated otherwise.Source: §V · p. 9

VI. EVALUATION

The evaluation is organized around accuracy across binary transformations, comparison with state-of-the-art systems, speed, and the contribution of micro-trace pretraining.

VI. EVALUATION

  • The evaluation asks how accurately TREX matches functions across architectures, optimizations, and obfuscations, and how it compares with state-of-the-art systems.These are the first two stated research questions.Source: §VI · p. 9
  • A separate research question asks how TREX’s speed compares with other tools.The evaluation treats runtime as distinct from matching accuracy.Source: §VI · p. 9
  • The evaluation also asks how much pretraining on micro-traces improves function-matching accuracy.This is posed as an ablation-oriented research question.Source: §VI · p. 9

A. RQ1: Accuracy

TREX achieves high AUC across combined architecture, optimization, and obfuscation shifts, and outperforms comparison systems across the reported cross-architecture, cross-optimization, and cross-obfuscation evaluations.

A. RQ1: Accuracy

  • Across projects, TREX achieves >0.958 AUC, reaching 0.995 in the most challenging setting with architecture, optimization, and obfuscation differences.Cross-optimization matching performs best; cross-architecture AUC is 0.001 lower, while obfuscation AUC is 0.026 lower than cross-optimization AUC.Source: A. RQ1: Accuracy · pp. 9–10

B. RQ2: Baseline Comparison

C. RQ3: Execution Time

TREX reduces the runtime of function parsing and embedding generation relative to SAFE and Gemini in the evaluated projects.

C. RQ3: Execution Time

  • The runtime evaluation measures binary parsing and embedding generation, but excludes one-time training and matching time.The evaluation uses x64 functions compiled with O3 from Binutils, Putty, Findutils, and Diffutils.Source: C. RQ3: Execution Time · p. 11
  • Up to 8× faster: TREX generates function embeddings faster than SAFE and Gemini.Figure 8 also compares parsing and embedding-generation runtime across four projects with different function counts; TREX is more efficient in both procedures.Source: C. RQ3: Execution Time · pp. 11–12

D. RQ4: Ablation Study

Pretraining substantially improves matching, and micro-traces add further gains; TREX also finds confirmed vulnerabilities in recent firmware images.

D. RQ4: Ablation Study

  • 15.7% on average: model AUC drops when TREX is not pretrained.Pretraining with 33% of the functions yields AUC only 1% below pretraining with all functions.Source: D. RQ4: Ablation Study · p. 12
  • 7.2%: AUC decreases when pretraining omits micro-traces, yet remains 0.88 in the combined architecture, optimization, and obfuscation setting.This decrease is smaller than the 15.7% drop without pretraining; the no-micro-trace model is 0.035 below SAFE.Source: Figure 10 · p. 12, D. RQ4: Ablation Study · p. 12
  • Testing PPL falls to about 2.1, corresponding to roughly 0.48 average confidence on masked tokens versus 0.004 for random guessing.The testing set samples 10,000 functions from the pretraining projects.Source: D. RQ4: Ablation Study · pp. 12–13, Figure 11 · p. 12

VII. CASE STUDIES

  • The firmware collection covers 180 images from 22 vendors, mostly WLAN routers, with the remainder including solar panels and smart cameras.It includes 127 MIPS 32-bit images and 53 ARM 32-bit images; 169 are 2020 models.Source: §VII · p. 13
  • TREX confirmed all 16 studied CVEs in four latest-version firmware models from Ubiquiti, TP-Link, NETGEAR, and Linksys.The search compiled vulnerable functions for MIPS and ARM at O3, retrieved top-10 matches, and manually verified them.Source: §VII · p. 13, Table V · p. 13

VIII. RELATED WORK

Prior binary-similarity work relies on static features or structures, or on dynamic features, while learning-based methods use static code representations. TREX instead learns approximate execution semantics from micro-traces and proposes transfer to other binary-analysis tasks.

A. Binary Similarity

  • TREX contrasts with static feature and structure matching, hand-coded dynamic features, and static-code embedding methods by learning approximate execution semantics from micro-traces.The related-work discussion also identifies heavyweight graph construction and limited long-range modeling as issues in some learning-based approaches.Source: A. Binary Similarity · p. 14

B. Learning Program Representations

  • XDA uses transfer learning to recover function and instruction boundaries from static raw bytes, without the execution-semantics knowledge targeted by TREX.The paper notes that learned program representations can support applications beyond function similarity.Source: B. Learning Program Representations · p. 14

IX. CONCLUSION

  • TREX pretrains on function micro-traces to learn approximate execution semantics, then transfers that knowledge to match semantically similar functions across architectures, optimizations, and obfuscations.The conclusion identifies decompilation as a possible future application of the learned semantics.Source: §IX · p. 14

APPENDIX

The appendix describes TREX’s attention-based architecture and hyperparameters, then reports experiments on cross-project generalization, byte-sequence encoding, and firmware vulnerability search.

A. Detailed Model Architecture

  • TREX’s self-attention layers use query, key, and value embeddings to compute attention-weighted updates, then combine the heads through a feedforward network with skip connections.The final-layer embeddings encode execution semantics for instructions and the overall function, and are used to predict masked codes and values.Source: A. Detailed Model Architecture · pp. 16–17

B. TREX Hyperparameters

  • The architecture uses 12 self-attention layers with 8 heads each, 768-dimensional embeddings, and a 3072-unit hidden layer in the attention MLP.Pretraining uses a maximum input length and effective batch size of 512, with learning rate 5×10^-4.Source: B. TREX Hyperparameters · p. 17

C. More Experiments

  • TREX’s AUC drops by less than 2% when finetuning and testing use different projects, indicating generalization to unseen function pairs across projects.The evaluation uses Binutils, Coreutils, and OpenSSL, with function pairs spanning architectures, optimizations, and obfuscations.Source: C. More Experiments · p. 17, Table VII · p. 17
  • Bi-LSTM byte-sequence combination achieves lower validation PPL than an MLP or summation, indicating it helps TREX learn approximate execution semantics.The comparison tests masked-token prediction using 10,000 function binaries.Source: C. More Experiments · p. 17
  • 24.3% lower error rate on average and 25.3% lower error rate in cross-architecture search: TREX outperforms SAFE in firmware function search.The search compares compiled OpenSSL functions against embedded OpenSSL libraries in NETGEAR R7000 firmware; the figure reports top-1/3/5/10 error for same-architecture and x64-to-ARM searches.Source: C. More Experiments · pp. 17–18, Figure 12 · p. 18

D. Probing Learned Execution Semantics

Masked-token predictions illustrate how TREX can use instruction effects and surrounding code patterns to infer arithmetic operations, register values, and stack-related constants.

D. Probing Learned Execution Semantics

  • In the arithmetic trace, predicting masked register and opcode values draws on relationships among subtraction, addition, and later register values.The model predicts the masked rax with 96% confidence and the masked add opcode with 98% confidence.Source: D. Probing Learned Execution Semantics · p. 18
  • In a function epilogue, the model predicts the masked stack-pointer constant 0x20 with 99% confidence, consistent with its decrement in the prologue and local-variable size.The example suggests pretraining captures common prologue and epilogue idioms beyond individual instruction semantics.Source: D. Probing Learned Execution Semantics · p. 18, Figure 14 · p. 18

Related papers

Loading 2012.08680v3…