Towards automatic generation of vulnerability-based signatures

By David Brumley, James Newsome, Dawn Song, Hao Wang, Somesh Jha. IEEE Symposium on Security and Privacy, 2006

315 citations recorded by the source corpus.

In this paper we explore the problem of creating vulnerability signatures. A vulnerability signature matches all exploits of a given vulnerability, even polymorphic or metamorphic variants. Our 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. We show 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. We provide a formal definition of a vulnerability signature and investigate the computational complexity of creating and matching vulnerability signatures. We also systematically explore the design space of vulnerability signatures. We identify 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. We propose new data-flow analysis and novel adoption of existing techniques such as constraint solving for automatically generating vulnerability signatures. We have built a prototype system to test our techniques. Our experiments show that we can automatically generate a vulnerability signature using a single exploit which is of much higher quality than previous exploit-based signatures. In addition, our techniques have several other security applications, and thus may be of independent interest

Subfields: Artificial Intelligence, Software, Signal Processing

View Paper: https://www.semanticscholar.org/paper/5fd6a58ec6867fee4d8e381cbf2f1fec0bb5ad35

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Software

In Signal Processing

Citations in the corpus

Machine learning in adversarial environments (2010, background): “Although it has been shown that intrusion detection systems that are difficult to spoof and that use “vulnerability signatures” can be created for malware that exploits known software vulnerabilities, these systems are often impractical and far too complex to protect large networks (Brumley et al. 2”
Limits of Learning-based Signature Generation with Adversaries (2008, background): “Signature generation algorithms that use semantic information have taken many different directions; some examples to point at directions are [4, 8, 12, 19, 31].”
Baggy Bounds Checking: An Efficient and Backwards-Compatible Defense against Out-of-Bounds Errors (2009, methodology): “Some systems provide probabilistic protection from memory errors [5].”
Exploring Multiple Execution Paths for Malware Analysis (2007, background): “A number of test input generation systems [6, 15, 16]”
EXE: automatically generating inputs of death (2006, background): “…Coverity;Das etal.2002;Flanagan et al.2002;Bush et al.2000;Wagner et al. 2000], and statically solving constraints to generate inputs that would cause execution to reach a speci.cprogrampoint orpath[Boyer et al. 1975;Gotlieb et al. 1998; Ball 2004; Ball et al. 2001; Brumley et al. 2006].”
On the infeasibility of modeling polymorphic shellcode (2007, background): “[7] supply an initial exploration of some of the theoretical foundations of vulnerability–based signatures .”
KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs (2008, unknown): “Many recent tools are based on symbolic execution [11, 14–16,20–22,24, 26, 27,36].”
BitBlaze: A New Approach to Computer Security via Binary Analysis (2008, methodology): “We have designed and developed novel techniques to automatically generate accurate input-based filters based on information about the vulnerability instead of the exploits, and thus generating filters that have zero false positives and can be effective against different variants of the exploits [11,”
Paragraph: Thwarting Signature Learning by Training Maliciously (2006, unknown): “Recent research proposes performing automated semantic analysis of collected worm samples, by monitoring the execution of a vulnerable server as it gets compromised [3,5,2,25,10].”
All You Ever Wanted to Know about Dynamic Taint Analysis and Forward Symbolic Execution (but Might Have Been Afraid to Ask) (2010, background): “One approach to handling system-level calls is to create summaries of their side effects [12, 16, 18].”