A High Throughput Pattern Matching Using Byte Filtered Bit_Split Algorithm

Abstract

The phenomenal growth of the Internet in the last decade and society's increasing dependence on it has brought along, a flood of security attacks on the networking and computing infrastructure. Intrusion Detection Systems (IDSs) have become widely recognized as powerful tools for identifying, deterring and deflecting malicious attacks over the network. Essential to almost every intrusion detection system is the ability to search through packets and identify content that matches known attacks. Network Intrusion Detection and Prevention Systems have emerged as one of the most effective ways of providing security to those connected to the network, and at the heart of almost every modern intrusion detection system is a pattern matching algorithm. Pattern matching relies on deterministic finite automata (DFA) to search for predefined patterns. Here modifications to the Aho-Corasick pattern-matching algorithm are proposed that drastically reduce the amount of memory required and improve its performance. For Snort rule sets, the new algorithm achieves 30% of memory reduction compared with the traditional Aho–Corasick algorithm. In addition, we can gain further reduction in memory by integrating our approach to the bit-split algorithm which is the state-of-the-art memory-based approach.