SRD-DFA: Achieving Sub-rule Distinguishing with Extended DFA Structure

Deep packet inspection (DPI) relies highly on regular expression due to its power of description, generalization and flexibility. In DPI, packet payload is compared against a large number of rules written in regular expression. To achieve high throughput, multiple regular expressions are combined and compiled into one DFA, which leads to two problems: a) State explosion; b) Sub-rule distinguishing in the combined rule set. While the first problem has been extensively studied in the recent years, we did not find any literature which formally discusses the second problem in detail. We formulate it and propose sub-rule distinguishable DFA (SRD-DFA), an extended DFA structure, and develop techniques to distinguish sub-rules from multiple regular expressions upon this structure. SRD-DFA can achieve the same throughput as minimized DFA, since it only incurs little extra memory consumption without extra run-time computation. Experimental results under the L7-filter rule set and a subset of Snort rule set demonstrate that our approach achieves 8 to 14 times higher throughput than the DFA without rule combination, while only introducing less than 8.4% overhead of state increase compared to the minimized DFA after rule combination. SRD-DFA can be easily used with advanced DFA compression algorithms to achieve much less memory consumption.