A Method to Evaluate CFG Comparison Algorithms

Control-Flow Graph (CFG) similarity is a core technique in many areas, including malware detection and software plagiarism detection. While many algorithms have been proposed in the literature, their relative strengths and weaknesses have not been previously studied. Moreover, it is not even clear h...

Full description

Saved in:
Bibliographic Details
Main Authors: Chan, Patrick P. F., Collberg, Christian
Format: Conference Proceeding
Language:English
Subjects:
Accuracy
Algorithm design and analysis
Approximation algorithms
Benchmark testing
Malware
Software
Software algorithms
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Control-Flow Graph (CFG) similarity is a core technique in many areas, including malware detection and software plagiarism detection. While many algorithms have been proposed in the literature, their relative strengths and weaknesses have not been previously studied. Moreover, it is not even clear how to perform such an evaluation. In this paper we therefore propose the first methodology for evaluating CFG similarity algorithms with respect to accuracy and efficiency. At the heart of our methodology is a technique to automatically generate benchmark graphs, CFGs of known edit distances. We show the result of applying our methodology to four popular algorithms. Our results show that an algorithm proposed by Hu et al. is most efficient both in terms of running time and accuracy.
ISSN:1550-6002
2332-662X
DOI:10.1109/QSIC.2014.28