Binary Diffing as a Network Alignment Problem via Belief Propagation
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.
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 on3
- 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
- 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
- DeepBinDiff: Learning Program-Wide Code Representations for Binary DiffingYue Duan, Xuezixiang Li, Jinghan Wang, Heng YinNDSS 2020
Related papers
- BINALIGNER: Aligning Binary Code for Cross-Compilation Environment DiffingYiran Zhu, Tong Tang, Jie Wan, Ziqi Yang et al.NDSS 2026 · 1 citation
- Towards Generative Graph Matching for Graph Edit Distance ComputationWei Huang, Hanchen Wang, Dong Wen, Wenjie Zhang et al.ICML 2026
- Cross-Inlining Binary Function Similarity DetectionAng Jia, Ming Fan, Xi Xu, Wuxia Jin et al.ICSE 2024 · 11 citations
- 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
- SigmaDiff: Semantics-Aware Deep Graph Matching for Pseudocode DiffingLian Gao, Yu Qu, Sheng Yu, Yue Duan et al.NDSS 2024
