Fine-Grained Parallel Regular Expression Matching for Deep Packet Inspection

Regular expression matching plays an important role in many critical network applications. Deterministic finite automata (DFA) is an effective way to implement regular expression matching, however, DFAs’ inherent sequential state transition makes them impractical for high-speed backbone networks. In this paper, a novel fine-grained parallel DFA, called LBDFA (Loopback DFA), is proposed to improve the matching performance of DFAs. The method is based on the observation that most transitions occur among a small number of states while other states are rarely accessed. Furthermore, the frequently traversed states, called Loopback states in this paper, usually remain unchanged for a large number of consecutive input characters in the process of state transitions. Therefore a remarkable improvement can be achieved by parallelizing the consecutive state transitions on Loopback states. A Bloom filter is employed to eliminate the temporary deviation in transitions in order to further improve the parallelism of LBDFAs. Experimental results on rule sets from L7-filter and Snort show that the LBDFA can meet the demand of regular expression matching for backbone networks with bandwidth of more than 10Gbps.