Attack Generation for NIDS Testing Using Natural Deduction

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 between the attack payload and the NIDS signature, attackers split the payload into several TCP packets, change it syntactically while preserving its semantics, or hide it between benign messages. We study attackers' ability to find attack instances that elude a NIDS and our ability to recognize such instances. We observe that different instances of a given attack can be derived from each other using simple transformations that change either the attack transport mechanism or its payload. We model these transformations as inference rules in a formal natural deduction system. Starting from an exemplary attack instance, we use an inference engine to automatically generate all possible instances derived from a particular collection 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. During 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.

Download this report (PDF)

Return to tech report index