Polygraph: Automatically generating signatures for polymorphic worms

It is widely believed that content-signature-based intru-sion detection systems (IDSes) are easily evaded by poly-morphic worms, which vary their payload on every infec-tion attempt. In this paper, we present Polygraph, a sig-nature generation system that successfully produces signa-tures that match polymorphic worms. Polygraph gener-ates signatures that consist of multiple disjoint content sub-strings. In doing so, Polygraph leverages our insight that for a real-world exploit to function properly, multiple in-variant substrings must often be present in all variants of a payload; these substrings typically correspond to proto-col framing, return addresses, and in some cases, poorly obfuscated code. We contribute a definition of the poly-morphic signature generation problem; propose classes of signature suited for matching polymorphic worm payloads; and present algorithms for automatic generation of signa-tures in these classes. Our evaluation of these algorithms on a range of polymorphic worms demonstrates that Polygraph produces signatures for polymorphic worms that exhibit low false negatives and false positives. 1