Improved call graph comparison using simulated annealing

O. Kostakis, J. Kinable, H. Mahmoudi, K. Mustonen

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

26 Citations (Scopus)


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.

Original languageEnglish
Title of host publication26th Annual ACM Symposium on Applied Computing, SAC 2011
Place of PublicationNew York
PublisherAssociation for Computing Machinery, Inc
Number of pages8
ISBN (Print)978-1-4503-0113-8
Publication statusPublished - 2011
Externally publishedYes
Event26th ACM Symposium on Applied Computing (SAC 2011) - Tunghai University, TaiChung, Taiwan
Duration: 21 Mar 201124 Mar 2011
Conference number: 26


Conference26th ACM Symposium on Applied Computing (SAC 2011)
Abbreviated titleSAC 2011


  • call graph
  • graph edit distance
  • malware
  • simulated annealing
  • static analysis

Fingerprint Dive into the research topics of 'Improved call graph comparison using simulated annealing'. Together they form a unique fingerprint.

Cite this