Binary Diffing as a Network Alignment Problem via Belief Propagation
This addresses binary diffing for software analysis, offering improved accuracy over existing methods.
The paper tackles the problem of matching functions between two binary programs by formulating it as a network alignment problem using call graphs, and their prototype QBinDiff outperforms state-of-the-art diffing tools.
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.