Vulnerability-Based Signature Generation Paper Appeared at Oakland 2006
Posted 30 May 2006
The paper Towards automatic generation of vulnerability-based
signatures, co-authored by David Brumley, James Newsome, Dawn
Song, Hao Wang, and Somesh Jha appeared at the 2006 IEEE Symposium on
Security and Privacy, which was held May 21–24, 2006 in
Oakland, California.
This paper explores the problem of creating vulnerability signatures. A vulnerability signature matches all exploits of a given vulnerability, even polymorphic or metamorphic variants. This work departs from previous approaches by focusing on the semantics of the program and vulnerability exercised by a sample exploit instead of the semantics or syntax of the exploit itself. It shows that the semantics of a vulnerability define a language which contains all and only those inputs that exploit the vulnerability. A vulnerability signature is a representation (e.g., a regular expression) of the vulnerability language. Unlike exploit based signatures whose error rate can only be empirically measured for known test cases, the quality of a vulnerability signature can be formally quantified for all possible inputs.
The paper provides a formal definition of a vulnerability signature and investigates the computational complexity of creating and matching vulnerability signatures. It also systematically explores the design space of vulnerability signatures. It identifies three central issues in vulnerability-signature creation: how a vulnerability signature represents the set of inputs that may exercise a vulnerability, the vulnerability coverage (i.e., number of vulnerable program paths) that is subject to our analysis during signature creation, and how a vulnerability signature is then created for a given representation and coverage.
The authors propose new data-flow analysis and novel adoption of existing techniques such as constraint solving for automatically generating vulnerability signatures. They have built a prototype system to test their techniques. Their experiments show that they can automatically generate a vulnerability signature using a single exploit which is of much higher quality than previous exploit-based signatures. In addition, their techniques have several other security applications and thus may be of independent interest.
