Bypassing Space Explosion in Regular Expression Matching for Network Intrusion Detection and Prevention Systems.
Jignesh Patel, Alex X. Liu, Eric K. Torng · 2012
Network intrusion detection and prevention systems commonly use regular expression (RE) signatures to represent individual security threats. While the corresponding DFA for any one RE is typically small, the DFA that corresponds to the entire set of REs is usually too large to be constructed or deployed. To address this issue, a variety of alternative automata implementations that compress the size of the final automaton have been proposed such as XFA and DFA. The resulting final automata are typically much smaller than the corresponding DFA. However, the previously proposed automata construction algorithms do suffer from some drawbacks. First, most employ a “Union then Minimize” framework where the automata for each RE are first joined before minimization occurs. This leads to an expensive NFA to DFA subset construction on a relatively large NFA. Second, most construct the corresponding large DFA as an intermediate step. In some cases, this DFA is so large that the final automaton cannot be constructed even though the final automaton is small enough to be deployed. In this paper, we propose a “Minimize then Union” framework for constructing compact alternative automata focusing on the DFA. We show that we can construct an almost optimal final DFA with small intermediate parsers. The key to our approach is a space and time efficient routine for merging two compact DFA into a compact DFA. In our experiments, our algorithm runs up to 302 times faster and uses 1390 times less memory than previous algorithms. For example, we are able to construct a DFA with over 80,000,000 states using only 1GB of main memory in only 77 minutes.