# Binary Diffing as a Network Alignment Problem via Belief Propagation

arXiv: https://arxiv.org/abs/2112.15337 · HTML: https://mlsanity.com/paper/2112.15337/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 36 references that are in the map.
- First posted on arXiv 31 Dec 2021.

## Builds on (most cited first, 4 of 4)

- [Graph Matching Networks for Learning the Similarity of Graph Structured Objects](https://mlsanity.com/paper/1904.12787/) (2019)
- [Graph Matching: Relax at Your Own Risk](https://mlsanity.com/paper/1405.3133/) (2014)
- [A Survey of Binary Code Similarity](https://mlsanity.com/paper/1909.11424/) (2019)
- [A Cross-Architecture Instruction Embedding Model for Natural Language Processing-Inspired Binary Code Analysis](https://mlsanity.com/paper/1812.09652/) (2018)

## Abstract (arXiv)

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.