Improved call graph comparison using simulated annealing

March 2011

Improved call graph comparison using simulated annealing

Authors:

K. Orestis, Joris Kinable, H. Mahmoudi, and K. Mustonen

Abstract:

The amount of suspicious binary executables submitted to Anti-Virus (AV) companies are in the order of tens of thousands per day. Current hash-based signature methods are easy to deceive and are inefficient for identifying known malware that have undergone minor changes. Examining malware executables using their call graphs view is a suitable approach for overcoming the weaknesses of hash-based signatures. Unfortunately, many operations on graphs are of high computational complexity. One of these is the Graph Edit Distance (GED) between pairs of graphs, which seems a natural choice for static comparison of malware. We demonstrate how Simulated Annealing can be used to approximate the graph edit distance of call graphs, while outperforming previous approaches both in execution time and solution quality. Additionally, we experiment with opcode mnemonic vectors to reduce the problem size and examine how Simulated Annealing is affected.
@conference{Orestis-2011-7299,
author = {K. Orestis And Joris Kinable And H. Mahmoudi And K. Mustonen},
title = {Improved call graph comparison using simulated annealing},
booktitle = {Proceedings of ACM Symposium on Applied Computing (SAC '11)},
year = {2011},
month = {March},
pages = {1516 - 1523},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.