面向深度包检测的DFA细粒度并行匹配方法  

Fine-Grained Parallel Regular Expression Matching for Deep Packet Inspection

作　　者：刘兴奎[1,2] 邵宗有[3,4] 刘新春 孙凝晖[1] 

机构地区：[1]中国科学院计算技术研究所高性能计算机研究中心北京100190 [2]中国科学院大学北京100049 [3]北京科技大学信息工程学院北京100083 [4]曙光信息产业北京有限公司北京100094

出　　处：《计算机研究与发展》2014年第5期1061-1070,共10页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(61070026)

摘　　要：确定性有限自动机(DFA)是实现正则表达式匹配的一种有效手段,但DFA的状态跳转是串行的,导致匹配速度慢、难以满足高速骨干网环境深度包检测(DPI)的性能需求.提出了一种称为LBDFA(Loopback DFA)的细粒度并行化状态跳转方法,通过将在Loopback状态上的连续跳转并行化,提高了匹配速度.此外,利用Bloom filter消除该并行跳转中的临时偏离现象,进一步提高了并行潜力.在L7-filter以及Snort规则集上的测试结果表明,LBDFA能够满足10Gbps以上的正则表达式匹配需求.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 lOGbps.

关 键 词：正则表达式 确定性有限自动机 深度包检测 回环状态 FPGA 

分 类 号：TP391.4[自动化与计算机技术—计算机应用技术]