Theory and Techniques for Automated Generation of Vulnerability-Based Signatures

Abstract—In this paper, we explore the problem of creating vulnerability signatures. A vulnerability signature is based on a program vulnerability and is not specific to any particular exploit. The advantage of vulnerability signatures is that their quality can be guaranteed. In particular, we create vulnerability signatures from the vulnerable program itself, such that they are guaranteed to have zero false positives by construction. We show how to automate signature creation for vulnerabilities that can be detected by a runtime monitor. There is no one right signature representation for a vulnerability. We introduce a formalism and way of thinking about vulnerability signature generation that is analysis centric instead of representation specific. In particular, a signature can be represented in many ways, from using regular expression to using a full Turing-complete language. Previous systems have mostly focused on a particular point in the design space. We show how to approximate the language of a vulnerability in many different language classes, each of which has unique properties and benefits, by performing analysis on the program binary and vulnerability. Our approach also considers multiple-path vulnerabilities. A multiple-path vulnerability is a vulnerability that can be exploited through several different code paths. For example, a Web server may have a vulnerability in a URL handling routine that is called for many different types of requests. We demonstrate techniques that can create signatures that cover multiple paths an exploit may take. We have had to develop new algorithms to cope with the problem where enumerating vulnerable paths leads to an exponential explosion. We develop a new approach that captures the logical semantics of multiple vulnerable program paths in Oðn2Þ space (where n is the size of the program) instead of exponential. We provide a formal definition of a vulnerability signature and investigate th