Computer Science ETDs


Sunny Fugate

Publication Date



During the last three decades, the designers of computer IDSs have been continuously challenged with performance bottlenecks and scalability issues. The number of threats is enormous. The performance of ID systems depends primarily on the quantity of input data and complexity of detected patterns. During noisy attacks, system load tends to increase proportional to increasing data rates, making ID systems vulnerable to flooding and denial-of-service attacks. Unfortunately, the number, type, and sophistication of threats is quickly increasing, outpacing our ability to detect them. The more we try to detect, the more computing and economic resources must be reserved solely for the task of detection, whittling away at what remains for performing useful computations. This dissertation describes methods for assessing the current scaling performance of signature-based IDSs and presents models for speculatively bootstrapping better IDS performance. Using measurements of the coverage and scaling performance of a modern signature-based IDS in the context of an anticipatory model, arguments are presented that maintaining compact, low-coverage signature-sets does not provide optimal protection for modern heterogeneous computing environments. The primary contribution is an analysis of how mechanisms of anticipatory bias can be used to achieve performance improvements. To support the theoretical models, two principal approaches have been implemented. The first uses a combination of anticipation and feedback in an attempt to decrease per-signature costs by (counter-intuitively) increasing system coverage. The approach uses learned sequence statistics to make predictions of future events. Each prediction above a chosen threshold is used to decrease per-stream detection cost by shunting traffic to smaller detectors (at the risk of increased error rates). The new approach promises decreasing per-signature costs as new detection signatures are added. The design and performance of a prototype anticipatory IDS, 'Packet Wrangler', demonstrates the feasibility of the basic approach. The second approach applies primarily to improving the performance of IDSs when under stress. When overburdened, an IDS will drop input data (often arbitrarily). A probabilistic signature activation approach is described which improves error rates by decreasing the total amount of input data lost by probabilistically dropping signature activations based on learned event statistics and system load. A theoretical analysis is presented which shows that a policy which drops signatures instead of packets can outperform the default policy of dropping packets in terms of total error rates. A rudimentary prototype based on the Snort IDS, 'Probabilistic Flowbits', is described. Experimental results are then given which show substantially decreased error rates while simultaneously decreasing system overhead. In conclusion, a case is made for expanding IDS coverage and implementation fast-feedback and anticipatory optimizations. It can be argued that these extensions are both necessary and sufficient for long-term scalability, but oddly absent from existing systems.




intrusion detection, performance optimization, speculative optimization

Document Type


Degree Name

Computer Science

Level of Degree


Department Name

Department of Computer Science

First Advisor

Luger, George

First Committee Member (Chair)

Crandall, Jedidiah

Second Committee Member

Hayes, Thomas

Third Committee Member

LorRaine, Duffy

Fourth Committee Member

Caudell, Thomas

Project Sponsors

Office of Naval Research; Space and Naval Warfare Systems Center, Pacific; Naval Postgraduate School; American Society for Engineering Education