PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey of Binary Code Similarity

Irfan Ul Haq, Juan Caballero

arXiv:1909.11424v1cs.CR

TL;DR

Binary code similarity supports important analyses when source code is unavailable, but compilation and other transformations can substantially alter binary representations. This paper conducts the first systematic survey of the area, analyzing 61 approaches across applications, characteristics, implementations, and evaluations, and summarizes its evolution and remaining challenges. The survey finds a shift from binary diffing to search and from single-architecture to cross-architecture approaches, while identifying comparability and small-code limitations.

  • Problem

    Binary code similarity is difficult because compilation can change binaries despite unchanged source, and the research area had not been systematically surveyed.

  • Method

    The paper systematically identifies and systematizes 61 binary code similarity approaches across applications, approach characteristics, implementations, and evaluation benchmarks and methodologies.

  • Results

    The survey documents evolution from binary code diffing to binary code search and from single-architecture to cross-architecture approaches.

  • Takeaways & Limitations

    The survey provides comparative tables for understanding approaches and identifies open challenges alongside application scenarios such as binary code search engines and the Internet of Things.

  • Takeaways & Limitations

    Varied datasets and evaluation methodologies, plus missing source code, make fair comparison of approaches difficult.

Abstract

from arXiv · show

Binary code similarity approaches compare two or more pieces of binary code to identify their similarities and differences. The ability to compare binary code enables many real-world applications on scenarios where source code may not be available such as patch analysis, bug search, and malware detection and analysis. Over the past 20 years numerous binary code similarity approaches have been proposed, but the research area has not yet been systematically analyzed. This paper presents a first survey of binary code similarity. It analyzes 61 binary code similarity approaches, which are systematized on four aspects: (1) the applications they enable, (2) their approach characteristics, (3) how the approaches are implemented, and (4) the benchmarks and methodologies used to evaluate them. In addition, the survey discusses the scope and origins of the area, its evolution over the past two decades, and the challenges that lie ahead.

I. INTRODUCTION

Binary code similarity supports applications when source code is unavailable, but compilation can produce substantially different binaries from unchanged source code. This first survey identifies and systematizes 61 approaches while tracing the field’s evolution and open challenges.

  • Motivation: Binary code similarity compares binary-code pieces such as basic blocks, functions, or whole programs for applications including bug search, malware analysis, patch analysis, and software theft detection.These applications address settings involving COTS, legacy, and malware programs whose source code may be unavailable.
  • Challenges: Compilation can erase semantic cues and change binaries through different compilers, optimization levels, operating systems, and CPU architectures, even when source code is unchanged.Lost information includes function and variable names, comments, and data-structure definitions.
  • Research gap: The area lacked a systematic survey despite numerous approaches proposed over the past 20 years.Previous surveys addressed related topics such as obfuscation, type inference, and dynamic malware analysis rather than binary code similarity itself.
  • Survey contribution: The survey systematizes 61 approaches by applications, approach characteristics, implementation, and evaluation benchmarks and methodologies.Its tables compare dimensions including granularity, representation, analysis type, scalability techniques, platforms, architectures, release status, datasets, and robustness evaluation.
  • Evolution and outlook: The field evolved from binary code diffing toward binary code search and from single-architecture toward cross-architecture approaches.The survey characterizes the field as active, discusses open technical challenges, and identifies application scenarios involving search engines and the Internet of Things.

A. Compilation Process

Binary similarity must distinguish semantically related code despite compilation and transformation changes that alter syntax, structure, or architecture. Approaches therefore vary in comparison type, granularity, input cardinality, robustness, and computational cost.

  • Compilation variability: The compilation pipeline can produce different but semantically equivalent binaries from identical source through compiler, optimization, target-platform, and optional obfuscation transformations.Source and binary transformations are typically semantics-preserving and may be applied before or after compilation.
  • Comparison dimensions: Binary similarity approaches compare identical, similar, or equivalent code at granularities including instructions, basic blocks, functions, and whole programs.They may compare one-to-one, one-to-many, or many-to-many inputs; one-to-one approaches commonly perform binary code diffing across program versions.
  • Comparison type: Identical code has the same syntax, whereas equivalent code has the same semantics and may use different syntax or instruction sets.Exact equivalence is undecidable for arbitrary programs and, in practice, is expensive enough to restrict analysis to small code pieces.
  • Robustness and cost: Syntactic similarity is cheapest but least robust, structural similarity occupies a middle ground, and semantic similarity is more robust but very expensive.Structural methods can tolerate syntactic transformations but remain sensitive to changes such as inlining or removal of unused parameters.
  • Granularity: Finer-grained comparisons can support coarser-grained judgments, but finer-grained similarity cannot establish coarser-grained identity or equivalence.For example, identical basic blocks can support several function-level judgments, while similar basic blocks alone cannot establish function-level identity or equivalence.

III. SCOPE & PAPER SELECTION

The survey restricts its scope to research approaches that compare binary code and applies explicit exclusions and publication criteria. A systematic search and screening process yielded 61 works across a multidisciplinary venue set.

  • Scope boundaries: The survey excludes source-dependent, bytecode, exclusively behavioral, and raw-byte sequence approaches from its binary-code similarity scope.Some byte-level techniques, such as fuzzy hashing, are still examined when used within analyzed approaches.
  • Inclusion criteria: It limits coverage to peer-reviewed papers and academic technical reports that propose a new binary-code similarity approach or technique.Works merely applying off-the-shelf tools are excluded, and the unit of analysis is the research work rather than the tool.
  • Paper selection: The selection process examined 20 years of publications in 14 top security and software-engineering venues, supplemented by searches for relevant work elsewhere.Each candidate paper was read to determine whether it satisfied the stated scope constraints.
  • Selected corpus: 61 research works from 37 venues were selected, spanning computer security, software engineering, systems, and machine learning.Most appeared in computer security venues, with 36 papers across 20 venues; software engineering contributed 13 papers across 8 venues.

IV. APPLICATIONS

Binary code similarity supports applications ranging from patch analysis and bug search to malware analysis. The survey traces the field from executable differencing in 1999 through broader semantic, structural, search, and cross-architecture approaches.

  • Application coverage: 36 of the 61 analyzed works demonstrate at least one application, while 23 provide generic capabilities usable across applications.Applications include binary diffing, code search, and binary clone detection.
  • Applications: Bug search finds reused vulnerable code in large repositories and is described as the most popular application.Code reuse can place the same code in multiple programs or multiple parts of one program.
  • Applications: Patch analysis compares consecutive or nearby program versions to identify changes, generate compact updates, and analyze security patches.This is especially useful for proprietary programs whose vendors do not disclose patch details.
  • Origins: 1999 marked the first identified binary code similarity approaches, including EXEDIFF for compressing differences between executable versions.EXEDIFF reconstructed compilation-related secondary changes at patch time to reduce patch size.
  • Evolution: The first decade after 1999 produced only 7 approaches, but expanded the field from syntax to semantics, from diffing to clustering and search, and into malware applications.Influential works included graph-based diffing, semantic malware-variant detection, and malware search.
  • Evolution: 52 approaches appeared during 2010–2019, with emphasis on binary code search, cross-architecture search since 2015, and machine learning in later years.Reducing search granularity to functions enabled applications such as clone detection and bug search.

VI. APPROACHES

The survey systematizes binary code similarity approaches by describing their approach-characteristic dimensions and organizing the results for comparison.

  • Approach characteristics: The approach-systematization section describes the approach-characteristic columns in Table I.The table is intended to support systematic reading and comparison of the surveyed approaches.

A. Comparison Type

The survey distinguishes how inputs are compared from the finer-grained comparisons performed internally. Across 61 approaches, similarity and one-to-many search dominate, while finer granularities commonly support coarser inputs.

  • Input comparison: The 61 approaches compare inputs for similarity rather than identicalness or full equivalence, which is undecidable in general.The survey classifies input comparison as one-to-one, one-to-many, or many-to-many.
  • Input comparison: 30 approaches are one-to-many, compared with 21 one-to-one and 10 many-to-many approaches.The survey attributes one-to-many dominance to interest in binary code search during the last decade.
  • Approach comparison: Most approaches use similarity: 42 approaches use similarity, 5 equivalence, and 2 identical comparison.Twelve approaches use multiple comparison types at different granularities.
  • Granularity: Function is the most common input granularity with 26 approaches, followed by whole program with 25 and related basic blocks with 4.Function granularity is preferred for binary code search, whereas whole-program granularity is common for diffing and clustering.
  • Granularity: 47 of 61 approaches use finer approach granularities to compare coarser input granularities.The most common approach granularities are function, used by 30 approaches, and basic block, used by 20.

C. Syntactic Similarity

The survey covers syntactic, semantic, and structural similarity techniques. These range from instruction-sequence comparison to graph-based and symbolic representations, with efficiency and exactness shaping design choices.

  • Syntactic similarity: Syntactic approaches compare instruction sequences, often after normalizing mnemonics, opcodes, or operands.Sequences commonly consist of consecutive instructions within a function.
  • Syntactic similarity: Fixed-size instruction sequences use a sliding window defined by window size and stride; stride one produces n-grams.Seven surveyed works use n-grams, including IDEA, MBC, RENDEZVOUS, MUTANTX-S, EXPOSÉ, ILINE, and KAM1N0.
  • Syntactic similarity: Hashing, embedding, and alignment are the most common methods for comparing instruction sequences.Hashing is used by 6 approaches, embeddings by 5 approaches for n-gram sequences, and alignment by 3 approaches.
  • Semantic similarity: Semantic similarity compares code effects, typically represented as changes to register and memory state, and is computed by 26 approaches.Most semantic approaches operate at basic-block granularity.
  • Semantic similarity: Input-output testing can establish non-equivalence with certainty but can only provide likely equivalence because testing all possible inputs is impractical.Confidence in likely equivalence depends on the fraction of inputs tested.
  • Semantic similarity: Eleven approaches use symbolic formulas, comparing them with theorem provers, semantic hashes, or graph similarity.Semantic hashes are efficient but can distinguish equivalent formulas after normalization, for example when symbolic terms are reordered.
  • Structural similarity: Structural similarity uses graph representations such as CFGs, ICFGs, and callgraphs; 27 approaches use structural methods.Most structural approaches address graph matching through filtering and approximate algorithms because subgraph and maximum-common-subgraph isomorphism are NP-complete.
  • Structural similarity: Other structural methods model graph similarity as optimization, compare execution paths, or embed graphs as real-valued feature vectors.Optimization-based methods find low-cost mappings between CFGs, while path and embedding methods reduce graphs to alternative comparison representations.

F. Feature-Based Similarity

Feature-based similarity represents binary code with vectors or feature sets, while embeddings learn real-valued representations from data. These approaches support syntactic, semantic, and structural comparison at multiple granularities.

  • Feature-based similarity: 28 approaches represent binary code as feature vectors or feature sets whose similarity reflects syntactic, semantic, or structural properties.Features may be Boolean, numeric, or categorical.
  • Feature-based similarity: Eight recent approaches learn real-valued embeddings from training data for automatic feature extraction and efficient similarity computation.Unlike manually selected and encoded features, embeddings do not reveal what has been learned.
  • Embeddings: GENIUS, VULSEEKER, and GEMINI build graph embeddings for function-level ACFGs annotated with selected basic-block features.GENIUS uses clustering and graph edit distance to compute its embedding.
  • Embeddings: αDIFF computes a function embedding directly from raw-byte sequences using a convolutional network.
  • Machine learning: Machine learning is used to generate embeddings, cluster similar code, or classify whether code pieces derive from the same source.The survey identifies these as three distinct uses of machine learning in binary code similarity.

G. Hashing

Hashing compares binary code through compact fixed-size representations, with locality-sensitive hashing approximating nearest-neighbor search for efficiency. Fuzzy hashes can also reflect executable data similarity and may be fragile to code-only changes.

  • Hashing: Hashes map arbitrary-size data to fixed-size values that are compact to store and efficient to compute and compare.Cryptographic hashes identify identical inputs, whereas locality-sensitive hashes target similar inputs.
  • Locality-sensitive hashing: Locality-sensitive hashing increases collision probability for similar inputs and is used to boost binary code search performance.OM approaches use LSH to index pieces of binary code.
  • Fuzzy hashing: None of the 61 surveyed approaches use popular fuzzy hashes such as ssdeep, tlsh, sdhash, or mrsh-v2.The survey discusses them because they are often applied to executable files.
  • Fuzzy hashing: Fuzzy hashes may capture executable-data similarity in addition to binary-code similarity.This makes whole-executable similarity different from similarity computed only on code sections.
  • Cross-architecture similarity: Sixteen surveyed approaches support cross-architecture comparison, enabling comparisons across architectures such as x86, ARM, and MIPS.These approaches compute semantic similarity because instruction syntax differs across architectures.

I. Type of Analysis

The surveyed approaches predominantly use static analysis and frequently incorporate dataflow analysis, instruction normalization, and reusable binary-analysis platforms. Implementations vary in supported architectures, languages, distribution, and openness.

  • Static and dynamic analysis: 51 approaches use only static analysis, 4 use only dynamic analysis, and 6 combine both.Dynamic analysis runs code on selected inputs or analyzes execution traces.
  • Static and dynamic analysis: Dynamic analysis provides runtime addresses, operand values, and control-flow targets, and can handle some obfuscations without disassembly.The survey reports applications in malware unpacking, trace analysis, and runtime-value collection.
  • Dataflow analysis: 19 approaches use dataflow analysis, including 16 that use symbolic execution to extract formulas for semantic similarity.SPAIN uses taint analysis for vulnerability and patch patterns, while IBINHUNT combines taint filtering with symbolic execution.
  • Normalization: 33 approaches normalize instructions to tolerate syntactic differences such as changed registers, operands, or compiler-introduced no-op equivalents.Normalization includes operand removal, operand normalization, and ignoring semantically irrelevant code.
  • Implementation platforms: All 61 approaches build on previously available binary-analysis platforms or tools for capabilities such as disassembly, control-flow graphs, or instruction monitoring.IDA is the most popular static platform, supporting 42 approaches.
  • Architectures: x86/x86-64 is supported by 59 approaches, followed by ARM by 16 and MIPS by 10.The survey identifies 16 cross-architecture approaches and 9 approaches supporting firmware.
  • Availability: Only 12 of the 61 approaches are open source, and 4 of those 12 released only part of their source code.The remaining approaches were not released, although their underlying platforms may be open source.

VIII. EVALUATIONS

Evaluations rely mostly on custom datasets and often use relatively small executable collections, although several approaches evaluate at million-function scale. Malware coverage is common, but packed malware is rarely included.

  • Evaluation methodology: Table IV summarizes each approach's datasets and evaluation methodology, including executable, function, and firmware-related dataset measures.
  • Datasets: Most approaches use custom datasets, while Coreutils is the only popular benchmark, used by 18 approaches.ReadyNAS and DD-WRT are openly available firmware datasets used by firmware-oriented approaches.
  • Dataset size: Over half of the approaches evaluate on fewer than 100 executables; 7 use fewer than 1K, 8 fewer than 10K, and 8 more than 10K.
  • Program composition: 37 approaches evaluate only benign programs, 8 only malware, and 16 both benign and malicious programs.This distribution shows that malware analysis is a frequent evaluation setting.
  • Malware datasets: Only 5 of the 24 approaches evaluated on malware use packed malware samples.Those approaches first unpack the samples with custom or generic unpackers before computing similarity.
  • Large-scale evaluation: GENIUS evaluates on 420M functions extracted from 8,126 firmwares, whereas prior approaches evaluated on at most 0.5M functions.Five other approaches also evaluate on more than 1M functions.

B. Methodology

The survey compares how binary code similarity approaches are evaluated, including robustness, accuracy, performance, and comparisons with prior work. It also identifies methodological inconsistencies and open challenges limiting fair comparison and broader deployment.

  • Evaluation methodology: 34 approaches evaluate robustness, while 27 do not; cross-optimization is most common, followed by cross-compiler, cross-architecture, and obfuscation testing.The corresponding counts are 23, 19, 16, and 13 approaches, respectively.
  • Evaluation methodology: 49 approaches quantitatively evaluate accuracy with ground truth, 12 use qualitative case studies, and two propose application-specific metrics.Standard metrics include true positives, false positives, precision, and recall; ILINE and KS2017 use novel metrics.
  • Evaluation methodology: 33 approaches compare with prior work, but comparisons are hindered by unavailable source code, differing inputs and granularities, and inconsistent metrics or methodologies.Only six approaches compare results on the same prior dataset, while reimplementation is often required.
  • Evaluation methodology: Function-search accuracy is especially sensitive to top-k values and unspecified similarity thresholds, which can make reported results difficult to compare.For example, 98% precision at top 10 is materially weaker than 98% precision at top 3, and some methods always return a repository match.
  • Evaluation methodology: 49 of 61 approaches measure runtime performance, typically end-to-end, while four report asymptotic complexity.The approaches reporting asymptotic complexity are BMM2006, SWPQS2006, ILINE, and MOCKINGBIRD.
  • Open challenges: The survey argues that open datasets and independent validation under common experimental conditions would improve approach comparison.The recommendation responds to varied datasets, evaluation methodologies, and the absence of source code for many approaches.

X. CONCLUSION

Over two decades, binary code similarity evolved from diffing toward search, structural and semantic analysis, broader robustness, scalability, and learned features. This first survey systematizes 61 approaches across four dimensions, summarizes their advantages and limitations, and identifies remaining challenges.

  • Conclusion: Binary code similarity evolved from binary code diffing to binary code search and from syntactic toward structural and semantic similarity.The field also expanded across code granularities and robustness settings.
  • Conclusion: The survey systematizes 61 approaches across applications, approach characteristics, implementation, and evaluation benchmarks and methodologies.It presents the results in accessible tables and discusses advantages and limitations.
  • Conclusion: The survey identifies remaining open challenges and concludes that binary code similarity has a bright future.The conclusion frames the area as active despite its previous lack of systematic analysis.

APPENDIX

Table V compares the binary analysis platforms used to implement binary code similarity approaches, including their analysis capabilities and supported environments.

  • Table V lists the platforms used to implement binary code similarity approaches and notes additions beyond earlier type-inference work.
  • The comparison covers intermediate representations, static or dynamic analysis, supported architectures and operating systems, and release format.
  • Among 17 platforms, 12 support static analysis and 7 support dynamic analysis, with substantial variation in static-analysis functionality.Static platforms range from disassemblers and decompilers to tools for control-flow graphs, call graphs, IR simplification, and data-flow propagation.
Loading 1909.11424v1…