Computer Science Department
School of Computer Science, Carnegie Mellon University


Towards Practical Automatic Generation of
Multipath Vulnerability Signatures

David Brumley, Zhenkai Liang, James Newsome, Dawn Song

April 2007

This paper was originally submitted to CCS 2007 and is currently in draft form.
Please contact the authors for later versions.


Keywords: Vulnerability signature, ternary signature, multi-path signature, error-free signature

Signature-based defense systems are one of the most popular architectures for defending against exploits of vulnerabilities. At the heart of a signature-based defense system is the signature generation mechanism. Since manual signature generation tends to be slow and error-prone, we need automatic signature generation techniques.

In this paper, we present the first practical approach for automatically creating vulnerability signatures which recognize different exploit variants of a vulnerability regardless of the execution path they take. Vulnerability signatures are based on the semantics of the vulnerability in the program itself, thus are more accurate than other types of signatures. A key limitation of previous vulnerability signature generation approaches is that they were only able to demonstrate signature generation for a single program path that an exploit may take to exploit a vulnerability. However, there may be multiple program paths which an exploit can take to the vulnerability, resulting in unacceptably many false negatives if only one path is covered by the signature. We address this shortcoming by presenting and implementing techniques for automatically generating practical vulnerability signatures which cover multiple paths. By covering multiple paths, our signatures have lower false negatives than previous approaches, while still guaranteeing zero false positives.

21 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by