GRAPH THEORETICAL ALGORITHMS FOR CONTROL FLOW GRAPH COMPARISON

摘要

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.