Thesis
Rule hashing for efficient packet classification in network intrusion detection
Washington State University
Master of Science (MS), Washington State University
2007
Handle:
https://hdl.handle.net/2376/102242
Abstract
An intrusion detection system (IDS) spends the majority of CPU time in packet classification to search for rules that match each packet. A common approach is to build a graph such as rule trees or finite automata for a given rule set, and traverse it using a packet as an input string. Because of the increasing number of security threats and vulnerabilities, the number of rules often exceeds thousands requiring more than hundreds of megabytes of memory. Exploring such a huge graph becomes a major bottleneck in high-speed networks since each packet incurs many memory accesses with little locality. In this thesis, we propose rule hashing for fast packet classification in intrusion detection systems. The rule hashing, combined with hierarchical rule trees, saves memory by minimizing the number of redundant nodes in the graph, and thus improves response times in finding matching rules. We implement our algorithm in Snort, a popular open-source intrusion detection system, and compare the performance of our algorithm with that of Snort's detection engine using real packet traces. Experiments show that our implementation handles more packets than Snort does while consuming an order of magnitude less memory.
Metrics
7 File views/ downloads
13 Record Views
Details
- Title
- Rule hashing for efficient packet classification in network intrusion detection
- Creators
- Atsushi Yoshioka
- Contributors
- Min Sik Kim (Degree Supervisor)
- Awarding Institution
- Washington State University
- Academic Unit
- Electrical Engineering and Computer Science, School of
- Theses and Dissertations
- Master of Science (MS), Washington State University
- Publisher
- Washington State University; Pullman, Wash. :
- Identifiers
- 99900525284101842
- Language
- English
- Resource Type
- Thesis