A Memory Efficient DFA Using Compression and Pattern Segmentation

AbstractThe role of network security systems such as network intrusion detection system (NIDS) has become more important. The regular expression (a.k.a. regex) matching algorithm used for inspecting the payloads of packets is one of the most intensive tasks in NIDS. When multiple regular expressions are processed together, the corresponding Deterministic Finite Automata (DFA) becomes so complicated and needs a large amount of memory. In this paper, we propose a memory efficient parallel compatible DFA algorithm that uses the techniques of compression and pattern segmentation to reduce the memory usage. Extended from PFAC (Parallel Failureless-AC) algorithm4, the proposed compressed and segmented DFA (CSDFA) needs less numbers of states and transitions than δFA. Without considering the leading symbols “.*” in the regular expressions, the transition table can be compressed very efficiently by the run-length encoding. The number of transitions in CSDFA is about a half of the transitions needed in δFA, and uses only 74% of the memory consumed by δFA. Based on our experiments, the throughput of the proposed CSDFA is also much better than δFA