Abstract
Intrusion Detection Systems (IDSs) have been widely used for identifying and blocking all kinds of known network attacks. Almost every intrusion detection system has an ability to characterize attack behaviors through comparing contents of packet with all known attack patterns. The core of these intelligent systems is multi-pattern matching algorithms. Time and space efficient algorithms are therefore very important for intrusion detection systems. There are many algorithms for multi-pattern matching. The oldest Aho-Corasick scheme exploits a finite state machine to trace matching patterns. On the other hand, Wu-Manber uses shift table and hash table to achieve two-phase searching. When the shift table finds suspicious payload, it searches the collision chain in the hash table for further verification. FNP is specifically designed for short patterns. When the patterns are short, it can find them very fast. All these algorithms have the same characteristic. In a single octet comparion, they can only eliminate patterns with the same offset. They cannot eliminate patterns with different offsets. The disadvantage limits the efficacy of per-octet comparions, rendering a great deal of redundant work. In the thesis, we propose a new algorithm to address such drawback. Our design allows every octet comparion to eliminate as many patterns with the same and different offsets as possible. The algorithm is based on comparison tree and uses (pattern, offset) pair instead of only pattern itself to find possible matching patterns. Every tree node has a position value which can tell you where octet comparison should be made next. The experimental evaluations substantiate that the proposed algorithm outperforms current state-of-the-art schemes by a wide margin.