The Research On Time And Space Efficient Regular Expression Matching Algorithm

Network intrusion detection and prevention systems (NIDS/NIPS) are important methods of network security defense. They check each packet header and payload (that is the packet content) to identify and block suspicious network behavior through real-time monitoring of network traffic. The core of the NIDS/NIPS is deep packet inspection (DPI), which process each packet with a predefined set of signatures using the matching algorithm. DPI technology not only used in NIDS/NIPS, but also applies to the application layer packet classification, P2P traffic identification, content-based traffic management.Because of the superior expressive power and the flexibility of the regular expression matching algorithm, traditional string matching engines have been replaced by the regular expression matching algorithm. Regular expression matching algorithm uses finite automata to express multiple signatures. There are two categories of finite automata:nondeterministic finite automata (NFA) and deterministic finite automata (DFA). NFA has the advantages of efficient storge; however there are disadvantages of NFA, such as slow matching procedure. DFA has the advantages of high speed matching procedure, but for many signatures, their combination DFA bear an explosion in the state space. So the crucial issue of regular expression matching algorithm is how to design time and space efficient finite automata.At the beginning, we introduce a transition merging algorithm in this paper. In the algorithm several transitions in the finite automata which is based on the state merging DFA are merged together based on the priority. So that the memory costed by DFA has been reduced. The experiments show that compared to the state merging algorithm, the transition merging algorithm reduces the memory consumption by 15%～31%, and reduces the memory consumption by 25%～42% compared to the traditional DFA. At the same time, the transition merging algorithm ensures the matching speed.Secondly, this paper presents a novel regular expression algorithm with Smart Finite Automata (SFA) based on the extended finite automata (XFA) algorithm. In the SFA, branching transitions are augmented with extra check instruments and the backward transitions in XFA are eliminated to avoid unnecessary state transitions. Experimental results show that compared with the XFA, the SFA reduces 44.1% memory consumption as well 69.1% memory accesses, thus the time/space efficiency of regular expression matching has improved.