Graph Theoretical Algorithms for Control Flow Graph Comparison

Sergej Alekseev, Adam Kajrys, and Andreas Karoly


Control flow graph comparison, graph isomorphism


This paper presents graph theoretical algorithms to compare control flow graphs of program code based on graph transformation and decomposition into connected components. The essential idea is to transform graphs into reduced graphs and to calculate an isomorphic correspondence. We also show some experimental results to illustrate the effectiveness of our algorithms in terms of detected structural differences in graphs that are compared. The presented algorithms in this paper have been implemented in the Dr. Garbage tool suite and are available for download under the Apache Open Source license.

Important Links:

Go Back