Randy Smith
University of Wisconsin--Madison
USA

Cristian Estan
University of Wisconsin--Madison
USA

Somesh Jha
University of Wisconsin--Madison
USA

Network Intrusion Detection Systems (NIDS) have become crucial to
securing modern networks. To be effective, a NIDS must be able to
counter evasion attempts and operate at or near wire-speed. Failure
to do so allows malicious packets to slip through a NIDS undetected.
We explore NIDS evasion through algorithmic complexity attacks. We
present a highly effective attack against Snort, the most popular open
source NIDS, and we provide a practical algorithmic solution that
successfully thwarts the attack. This attack, termed the
backtracking attack, exploits the behavior of rule matching,
yielding packet inspection times that are up to 1.5 million
times slower than the processing time of benign packets. Our analysis
shows that this attack is applicable to many rules, potentially
rendering vulnerable the many networks protected by Snort (estimated
to be in the tens of thousands). Our countermeasure to this attack
confines the inspection time to within one order of magnitude of
benign packets. Our experimental results using a live system show
that an attacker needs only 4.0 kbps of bandwidth to perpetually
disable an unmodified NIDS, whereas all intrusions are detected when
our countermeasure is used.

Keywords: algorithmic complexity intrusion detection

Read Paper (in PDF)