Bypassing space explosion in high-speed regular expression matching

摘要: Network intrusion detection and prevention systems commonly use regular expression (RE) signatures to represent individual security threats. While the corresponding deterministic finite state automata (DFA) for any one RE is typically small, DFA that corresponds entire set of REs usually too large be constructed or deployed. To address this issue, a variety alternative implementations compress size final automaton have been proposed such as extended (XFA) delayed input (D2 FA). The resulting are much smaller than DFA. However, previously construction algorithms do suffer from some drawbacks. First, most employ "Union then Minimize" framework where each first joined before minimization occurs. This leads an expensive nondeterministic (NFA) subset on relatively NFA. Second, construct intermediate step. In cases, so cannot even though small enough paper, we propose "Minimize Union" constructing compact focusing D2 FA. We show can almost optimal FA with parsers. key our approach space-and time-efficient routine merging two into experiments, algorithm runs average 155 times faster uses 1500 less memory previous algorithms. For example, able over 80 000 states using only 1 GB main in 77 min.