Proactive Detection of Computer Worms Using Model Checking

Johannes Kinder, Stefan Katzenbeisser, Christian Schallhart, Helmut Veith

Research output: Contribution to journalArticlepeer-review

61 Downloads (Pure)


Although recent estimates are speaking of 200,000 different viruses, worms, and Trojan horses, the majority of them are variants of previously existing malware. As these variants mostly differ in their binary representation rather than their functionality, they can be recognized by analyzing the program behavior, even though they are not covered by the signature databases of current anti-virus tools. Proactive malware detectors mitigate this risk by detection procedures which use a single signature to detect whole classes of functionally related malware without signature updates. It is evident that the quality of proactive detection procedures depends on their ability to analyze the semantics of the binary.

In this paper, we propose the use of model checking---a well established software verification technique---for proactive malware detection. We describe a tool which extracts an annotated control flow graph from the binary and automatically verifies it against a formal malware specification. To this end, we introduce the new specification language CTPL, which balances the high expressive power needed for malware signatures with efficient model checking algorithms. Our experiments demonstrate that our technique indeed is able to recognize variants of existing malware with a low risk of false positives.
Original languageEnglish
Pages (from-to)424-438
JournalIEEE Transactions on Dependable and Secure Computing
Issue number4
Early online date19 Nov 2008
Publication statusPublished - Oct 2010


  • Invasive software
  • model checking

Cite this