ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development

Previous Articles     Next Articles

Fine-Grained Parallel Regular Expression Matching for Deep Packet Inspection

Liu Xingkui1,2, Shao Zongyou3,4, Liu Xinchun4, and Sun Ninghui1   

  1. 1(High Performance Computer Research Center, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190) 2(University of Chinese Academy of Sciences, Beijing 100049) 3(School of Information Engineering, University of Science and Technology Beijing, Beijing 100083) 4(Sugon Company, Beijing 100094)
  • Online:2014-05-15

Abstract: 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.

Key words: regular expression, deterministic finite automata (DFA), deep packet inspection, loopback state, FPGA