Improved Call Graph Comparison Using Simulated Annealing.

Reference:

Orestis Kostakis, Joris Kinable, Hamed Mahmoudi, and Kimmo Mustonen. Improved call graph comparison using simulated annealing.. In Proceedings of 26th ACM Symposium On Applied Computing, pages 1516–1523, 2011.

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.

Suggested BibTeX entry:

@inproceedings{KKMM2011,
    author = {Orestis Kostakis and Joris Kinable and Hamed Mahmoudi and Kimmo Mustonen},
    booktitle = {Proceedings of 26th ACM Symposium On Applied Computing},
    pages = {1516-1523},
    title = {Improved Call Graph Comparison Using Simulated Annealing.},
    year = {2011},
}