Lune

ASE2021Top-tier venue

Binary Diffing as a Network Alignment Problem via Belief Propagation

Elie Mengin, Fabrice Rossi

Abstract

In this paper, we address the problem of finding a correspondence, or matching, between the functions of two programs in binary form, which is one of the most common task in binary diffing. We introduce a new formulation of this problem as a particular instance of a graph edit problem over the call graphs of the programs. In this formulation, the quality of a mapping is evaluated simultaneously with respect to both function content and call graph similarities. We show that this formulation is equivalent to a network alignment problem. We propose a solving strategy for this problem based on max-product belief propagation. Finally, we implement a prototype of our method, called QBinDiff, and propose an extensive evaluation which shows that our approach outperforms state of the art diffing tools.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

  • DeepBinDiff: Learning Program-Wide Code Representations for Binary Diffing cites Asm2Vec: Boosting Static Representation Robustness for Binary Clone Search against Code Obfuscation and Compiler Optimization
  • DeepBinDiff: Learning Program-Wide Code Representations for Binary Diffing cites Neural Network-based Graph Embedding for Cross-Platform Binary Code Similarity Detection
  • Asm2Vec: Boosting Static Representation Robustness for Binary Clone Search against Code Obfuscation and Compiler Optimization cites Neural Network-based Graph Embedding for Cross-Platform Binary Code Similarity Detection
Builds onCited byLeft to right by year; the more cited, the higher.

Builds on3

  1. Neural Network-based Graph Embedding for Cross-Platform Binary Code Similarity DetectionXiaojun Xu, Chang Liu, Qian Feng, Heng Yin et al.CCS 2017 · 682 citations
  2. Asm2Vec: Boosting Static Representation Robustness for Binary Clone Search against Code Obfuscation and Compiler OptimizationSteven H. H. Ding, Benjamin C. M. Fung, Philippe CharlandS&P 2019 · 447 citations
  3. DeepBinDiff: Learning Program-Wide Code Representations for Binary DiffingYue Duan, Xuezixiang Li, Jinghan Wang, Heng YinNDSS 2020

Related papers

  1. BINALIGNER: Aligning Binary Code for Cross-Compilation Environment DiffingYiran Zhu, Tong Tang, Jie Wan, Ziqi Yang et al.NDSS 2026 · 1 citation
  2. Towards Generative Graph Matching for Graph Edit Distance ComputationWei Huang, Hanchen Wang, Dong Wen, Wenjie Zhang et al.ICML 2026
  3. Cross-Inlining Binary Function Similarity DetectionAng Jia, Ming Fan, Xi Xu, Wuxia Jin et al.ICSE 2024 · 11 citations
  4. REVDECODE: Enhancing Binary Function Matching with Context-Aware Graph Representations and Relevance DecodingTongwei Ren, Ronghan Che, Guin Gilman, Lorenzo De Carli et al.USENIX Security 2025
  5. SigmaDiff: Semantics-Aware Deep Graph Matching for Pseudocode DiffingLian Gao, Yu Qu, Sheng Yu, Yue Duan et al.NDSS 2024
Dusk over the sea between two cliffs drawn in fine vertical lines