TY - GEN
T1 - A method to evaluate CFG comparison algorithms
AU - Chan, Patrick P.F.
AU - Collberg, Christian
N1 - Publisher Copyright:
© 2014 IEEE.
PY - 2014/11/14
Y1 - 2014/11/14
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84912095604&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84912095604&partnerID=8YFLogxK
U2 - 10.1109/QSIC.2014.28
DO - 10.1109/QSIC.2014.28
M3 - Conference contribution
AN - SCOPUS:84912095604
T3 - Proceedings - International Conference on Quality Software
SP - 95
EP - 104
BT - Proceedings - International Conference on Quality Software
PB - IEEE Computer Society
T2 - 14th International Conference on Quality Software, QSIC 2014
Y2 - 2 October 2014 through 3 October 2014
ER -