Shai Rubin
University of Wisconsin, Madison
USA

Somesh Jha
University of Wisconsin, Madison
USA

Barton Miller
University of Wisconsin, Madison
USA

A common way to elude a signature-based NIDS is to transform an
attack instance that the NIDS recognizes into another instance
that it fails to recognize. For example, to avoid matching the
attack payload to a NIDS signature, attackers split the payload
into several TCP packets or hide it between benign messages. We
observe that different attack instances can be derived from each
other using simple transformations. We model these
transformations as inference rules in a natural-deduction system.
Starting from an exemplary attack instance, we use an inference
engine to automatically generate all possible instances derived by
a set of rules. The result is a simple yet powerful tool capable
of both generating attack instances for NIDS testing and
determining whether a given sequence of packets is an attack.



In several testing phases using different sets of rules, our tool
exposed serious vulnerabilities in Snort---a widely deployed NIDS.
Attackers acquainted with these vulnerabilities would have been
able to construct instances that elude Snort for any TCP-based
attack, any Web-CGI attack, and any attack whose signature is a
certain type of regular expression.

Keywords: NIDS, Testing, Attack Generation, Attack Analysis

Read Paper (in PDF)