A DFA With Extended Character-Set for Fast Deep Packet Inspection
Deep Packet Inspection (DPI), based on regular expressions, is expressive, compact, and efficient in specifying attack signatures. The authors focus on their implementations based on general-purpose processors that are cost-effective and flexible to update. In this paper, they propose a novel solution, called Deterministic Finite Automata with Extended Character-set (DFA/EC), which can significantly decrease the number of states through slightly extending the character-set. Different from existing state reduction algorithms, the solution requires only a single memory access for each byte in the traffic payload, which is the minimum. They perform experiments with the Snort rule-sets. Results show that, compared to DFA, a DFA/EC can be over four orders of magnitude smaller, has smaller memory bandwidth, and runs faster.