新颖的正则NFA引擎构造方法

doi:10.3969/j.issn.1000-436x.2014.10.012

摘要/Abstract

摘要：

提出了一种新颖的正则NFA引擎构造方法——PFA构造法。PFA构造法包括3个主要算法：预处理算法、解析树编码算法和基止状态的规模更小的NFA，称其为NFA_p。NFA_p的规模与正则于编码树的NFA构造算法。采用PFA构造法能够构造出只含表达式组的长度线性相关有，较Thompson自动机、一个开始状态和一个终后跟自动机、位置自动机以及部分派生自动机的规模都要小，是Thompson NFA的1/3，比已经接近最优的后跟自动机构造法所获得的NFA还要小。

关键词: 深度分组检测, 模式匹配, 正则表达式, 有穷自动机, 构造算法

Abstract:

A novel method for constructing smaller non-deterministic finite automata (NFA) engine from given regular expressions named PFA was proposed.There are three main algorithms in PFA,the pretreatment algorithm,the coding parser tree algorithm and the NFA construction algorithm based on the coded binary tree.The smaller NFA named NFA_p with only one start state and one final state can be obtained by using PFA construction method.NFA_phave linear size in terms of the size of given regular expressions.It is the smallest NFA comparing with current methods like Thompson NFA,follow automata,position automata and partial derivatives automata.The size of NFA_pis one third of Thompson’s and it is smaller than the size of follow automata whose size has nearly closed to optimal.

Key words: deep packet inspection, pattern matching, regular expression, finite automata, construction algorithm

敬茂华,杨义先,汪韬,辛阳. 新颖的正则NFA引擎构造方法[J]. 通信学报, 2014, 35(10): 98-106.

Mao-hua JING,Yi-xian YANG,Tao WANG,Yang XIN. Novel NFA engine construction method of regular expressions[J]. Journal on Communications, 2014, 35(10): 98-106.

图/表 12

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

表1

现有的5种基本的构造法对比情况"

构造法	典型实例的size	一般情况下的size	算法时间复杂度
Thompson自动机	8+14=22	O (6\|r\|)	Θ (r)
后跟自动机	4+8=12	$\frac{3}{2} r \| + \frac{5}{2}$	O(n(log n) ²)
位置自动机	7+22=29	$O (n^{2})$	$O (n^{3})$
部分派生自动机	4+11=15	$‖ r ‖ + 1$	$O ({\| r \|}^{2} {‖ r ‖}^{3})$
PFA	3+7=10	理论上O(2\|r\|)，实际上小于后跟自动机	$O (n^{2})$

表1

参考文献 33

[1]	JIANG T , RAVIKUMAR B . Minimal NFA problems are hard[J]. SIAM Journal on Computing, 1993,22(6): 1117-1141.
[2]	ROESCH M . Snort:lightweight intrusion detection for networks[A]. Proceeding of LISA99,13th Sytems Administration Conference[C]. Seattle,USA, 1999. 229-238.
[3]	PAXSON V . Bro:a system for detecting network intruders in real-time[J]. Computer networks, 1999,31(23): 2435-2463.
[4]	LEVANDOSKI J , SOMMER E , STRAIT M . Application layer packet classifier for Linux［EB/OL］． . 2008．
[5]	WANG H , PU S , KNEZEK G ,et al. A modular NFA architecture for regular expression matching[A]. Proceedings of the 18th Annual ACM/SIGDA International Symposium on Field Programmable Gate arrays[C]. ACM, 2010. 209-218.
[6]	YAMAGAKI N , SIDHU R , KAMIYA S . High-speed regular expression matching engine using multi-character NFA[A]. Field Programmable Logic and Applications,FPL 2008[C]. 2008. 131-136.
[7]	NAKAHARA H , SASAO T , MATSUURA M . A regular expression matching using non-deterministic finite automaton[A]. Formal Methods and Models for Codesign (MEMOCODE),2010 8th IEEE/ACM International Conference on IEEE[C]. 2010. 73-76.
[8]	TAN F . Algorithm for constructing the simplified DFA of regular expressions[J]. Journal of Beijing University of Aeronautics and Astronautics, 1998,24(4): 495-498.
[9]	NAVARRO G , RAFFINOT M . Compact DFA representation for fast regular expression search[M]. Algorithm Engineering. Springer Berlin Heidelberg, 2001.
[10]	张伟, 薛一波, 嵩天等 . 一种支持多正则表达式匹配的硬件结构[J]. 清华大学学报, 2009,49(10): 132-135. ZHANG W , XUE Y B , XIAO T ,et al. Multiple regular expression matching hardware architecture[J]. Journal of Tsinghua University (Science and Technology), 2009,49(10): 132-135.
[11]	张树壮, 罗浩, 方滨兴 ,等. 面向网络安全的正则表达式匹配技术[J]. 软件学报, 2011,22(8): 1838-1853. ZHANG S Z , LUO H , FANG B X ,et al. Regular expressions matching for network security[J]. Journal of Software, 2011,22(8): 1838-1854.
[12]	THOMPSON K . Programming techniques:regular expression search algorithm[J]. Communications of the ACM, 1968,11(6): 419-422.
[13]	GLUSHKOV V M . The abstract theory of automata[J]. Russian Mathematical Surveys, 1961,16(5): 1-53.
[14]	GARCíA P,LóPEZ D , RUIZ J ,et al. From regular expressions to smaller NFAs[J]. Theoretical Computer Science, 2011,412(41): 5802-5807.
[15]	SIPPU S , SOISALON S E . Parsing Theory:I:Languages and Parsing[M]. New York: SpringerPress, 1988.
[16]	GLUSHKOV V M . The abstract theory of automata[J]. Russian Mathematical Surveys, 1961,16(5): 1-53.
[17]	MCNAUGHTON R , YAMADA H . Regular expressions and state graphs for automata[J]. Electronic Computers, 1960,(1): 39-47.
[18]	ANTIMIROV V . Partial derivatives of regular expressions and finite automaton constructions[J]. Theoretical Computer Science, 1996,155(2): 291-319.
[19]	ILIE L , YU S . Follow automata[J]. Information and Computation, 2003,186(1): 140-162.
[20]	KUMAR S , CHANDRASEKARAN B , TURNER J ,et al. Curing regular expressions matching algorithms from insomnia,amnesia,and acalculia[A]. Proceedings of the 3rd ACM/IEEE Symposium on Architecture for Networking and Communications Systems[C]. ACM, 2007. 155-164.
[21]	BECCHI M , CROWLEY P . A hybrid finite automaton for practical deep packet inspection[A]. Proceedings of the 2007 ACM CoNEXT Conference[C]. ACM, 2007:1.
[22]	SMITH R , ESTAN C , JHA S . XFA:faster signature matching with extended automata[A]. Security and Privacy,SP 2008[C]. 2008. 187-201.
[23]	KUMAR S , DHARMAPURIKAR S , YU F ,et al. Algorithms to accelerate multiple regular expressions matching for deep packet inspection[A]. ACM SIGCOMM Computer Communication Review[C]. ACM, 2006,36(4): 339-350.
[24]	BECCHI M , CADAMBI S . Memory-efficient regular expression search using state merging[A]. INFOCOM 2007,26th IEEE International Conference on Computer Communications[C]. 2007.10641072.
[25]	ZHANG J , ZHANG D , HUANG K . A regular expression matching algorithm using transition merging[A]. 15th IEEE Pacific Rim International Symposium on IEEE[C]. 2009. 242-246.
[26]	FICARA D , GIORDANO S , PROCISSI G ,et al. An improved DFA for fast regular expression matching[J]. ACM SIGCOMM Computer Communication Review, 2008,38(5): 29-40.
[27]	YU F , CHEN Z , DIAO Y ,et al. Fast and memory-efficient regular expression matching for deep packet inspection[A]. Architecture for Networking and Communications systems,ANCS 2006[C]. 2006. 93-102.
[28]	FICARA D , GIORDANO S , PROCISSI G ,et al. An improved DFA for fast regular expression matching[J]. ACM SIGCOMM Computer Communication Review, 2008,38(5): 29-40.
[29]	SMITH R , ESTAN C , JHA S . XFA:faster signature matching with extended automata[A]. Security and privacy,SP 2008[C]. 2000. 187-201.
[30]	杨毅夫, 刘燕兵, 刘萍等 . 正则表达式的 DFA 压缩算法[J]. 通信学报, 2009,30(10): 36-41. YANG Y F , LIU Y B , LIU P ,et al. Effective algorithm of compressing regular expression’s DFA[J]. Journal on Communications, 2009,30(10): 36-41.
[31]	柳厅文, 孙永, 卜东波 ,等. 正则表达式分组的 1/(1-1/k)-近似算法[J]. 软件学报, 2012,23(9): 2261-2272. LIU T W , SUN Y , BU D B ,et al. 1/(1-1/k)-optimal algorithm for regular expression grouping[J]. Journal of Software, 2012,23(9): 2261-2272.
[32]	KAMALA K . Introduction To Formal Languages,Automata Theory And Computation[M]. Pearson Education India, 2009.
[33]	BRüGGEMANN K A . Regular expressions into finite automata[J]. Theoretical Computer Science, 1993,120(2): 197-213.