基于多维有限自动机的DFA改进算法

doi:10.11959/j.issn.1000-436x.2015101

摘要/Abstract

摘要：

多个正则表达式规则编译成一个DFA(deter minister finite automata)时，会产生状态爆炸、存储急剧增加的现象。针对最严重的状态爆炸问题，从信息论的角度给出了解释，并提出多维数学模型，将冗余状态分为0维状态和1维状态，通过前者按照维度压缩，后者动态构建的方法将空间复杂度降到理论下界，并在此基础上提出多维有限自动机(MFA,multi-dimensional finite automata)。实验表明，MFA构造时间比XFA略少，比DFA、STT冗余压缩算法和Hybrid-FA降低了2～3个数量级；存储空间比XFA略高，比DFA、STT冗余压缩算法、mDFA、Hybrid-FA降低了1～2个数量级；匹配时间比DFA、Hybrid-FA略多，但是比XFA略少，比STT冗余压缩算法和mDFA降低了1～2个数量级。

关键词: 正则表达式, DFA, 有限自动机, 状态爆炸

Abstract:

Compiling multiple regular expression signatures into a combined DFA can blowup in state and storage space.Explanations from the prospective of information theory and multi-dimensional mathematical model were proposed fo-cusing on the most serious state explosion.Redundancy states were divided into zero-dimensional ones and one-dimensional ones.The former were compressed by dimension,and the later were dynamically built.The space com-plexity of the model came to the theoretical lower bound by the above methods.Then the multi-dimensional finite auto-mata (MFA) was proposed with the model.Experiments show that,the construction time taken by MFA is slightly less than XFA and is 2～3 orders of magnitude lower than DFA,STT redundancy compression algorithms and Hybrid-FA; the memory space of MFA is slightly higher than XFA,but is 1～2 orders of magnitude lower than DFA,STT redundancy compression algorithms,mDFA and Hybrid-FA; in the aspect of matching time,MFA ranks after DFA and Hybrid-FA,but ranks before XFA,and it achieves 1～2 orders of magnitude lower than that of STT redundancy compression algo-rithms and mDFA.

Key words: regular expression, DFA, finite automata, state explosion

宫阳阳,刘勤让,杨镇西,邵翔宇,邢池强,焦慧娟,彭志彬. 基于多维有限自动机的DFA改进算法[J]. 通信学报, 2015, 36(5): 174-186.

ONGYang-yang G,IUQin-rang L,ANGZhen-xi Y,HAOXiang-yu S,INGChi-qiang X,IAOHui-juan J,ENGZhi-bin P. Improved DFA algorithm based on multi-dimensional finite automata[J]. Journal on Communications, 2015, 36(5): 174-186.

图/表 20

图1

图2

图3

图4

表1

表2

表3

图5

图6

表4

图7

图8

图9

图10

表5

表6

图11

表7

图12

表8

参考文献 22

[1]	HOPCROFT J E , ULLMANJ D . Introduction to Automata Theory,Languages and Computation2nd Edition[M]. US: Addison Wesley, 2001.
[2]	YU F , CHEN Z F , DIAO Y L , et al. Fast and memory-efficient regular expression matching for deep packet inspection[A]. Proceedings of the IEEE/ACM Symposium on Architectures for Networking and Communications Systems[C]. San Jose,Canada, 2006. 93-102.
[3]	徐乾，鄂跃鹏，葛敬国等．深度包检测中一种高效的正则表达式压缩算法[J]．软件学报， 2009,20(8):2214-2226. XU Q , E Y P , GE J G , et al. Efficient regular expression compression algorithm for deep packet inspection[J]. Journal of Software, 2009,20(8):2214-2226.
[4]	BECCHI M , CROWLEY P . A hybrid finite automaton for practical deep packet inspection[A]. Proceedings of the 2007 ACM CoNEXT conference[C]. New York,USA, 2007. 1.
[5]	张树壮，罗浩，方滨兴等．一种面向网络安全检测的高性能正则表达式匹配算法[J]．计算机学报， 2010,33(10):1976-1986. ZHANG S Z , LUO H , FANG B X , et al. An efficient regular expression matching algorithm for network security inspection[J]. Chinese Journal of Computers, 2010,33(10):1976-1986.
[6]	乔登科，王卿，柳厅文等．基于状态分组的高效i-DFA构造技术[J]．通信学报， 2013,34(8):102-109. QIAO D K , WANG Q , LIU T W , et al. Efficient i-DFA construction algorithm based on state grouping[J]. Journal on Communications, 2013,34(8):102-109.
[7]	贺炜，郭云飞，扈红超．基于状态约束的大规模正则表达式匹配算法[J]．通信学报， 2013,34(10):183-190. HE W , GUO Y F , HU H C . States constrain-based algorithm for large scale regular expression matching[J]. Journal on Communications, 2013,34(10):183-190.
[8]	YANG Y H E , PRASANNA V K . Space-time tradeoff in regular expression matching with semi-deterministic finite automata[A]. INFOCOM,2011 Proceedings IEEE[C]. Shanghai,China, 2011. 1853-1861.
[9]	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]. Orlando,USA, 2007. 155-164.
[10]	SMITH R , ESTAN C , JHA S , et al. Deflating the big bang:fast and scalable deep packet inspection with extended finite automata[A]. SIGCOMM '08 Proceedings of the ACM SIGCOMM 2008 conference on Data communication[C]. Seattle,USA, 2008. 207-218.
[11]	张大方，张洁坤，黄昆．一种基于智能有限自动机的正则表达式匹配算法[J]．电子学报， 2012,40(8):1617-1623. ZHANG D F , ZHANG J K , HUANG K . A regular expression matching algorithm with smart finite automaton[J]. Acta Electronica Sinica, 2012,40(8):1617-1623.
[12]	KUMAR S , DHARMAPURIKAR S , YU F , et al. Algorithms to accelerate multiple regular expressions matching for deep packet inspection[A]. Proceedings of the 2006 Conference on Applications,Technologies,Architectures,and Protocols for Computer Communications[C]. Pisa,Italy, 2006. 339-350.
[13]	BECCHI M , CADAMBI S . Memory-efficient regular expression search using state merging[A]. INFOCOM 2007,the 26th IEEE International Conference on Computer Communications[C]. Anchorage,USA, 2007. 1064-1072.
[14]	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.
[15]	FICARA D , DI PIETRO A , GIORDANO S , et al. Differential encoding of DFA for fast regular expression matching[J]. IEEE/ACM Transactions on Networking, 2011,19(3): 683-694.
[16]	QI Y , WANG K , FONG J , et al. Feacan:front-end acceleration for content-aware network processing[A]. IEEE/ACM Transactions on Networking[C]. Shanghai,China, 2011. 2114-2122.
[17]	LIU T , YANG Y , LIU Y , et al. An efficient regular expressions compression algorithm from a new perspective[A]. INFOCOM2011 Proceedings IEEE[C]. Shanghai,China, 2011. 2129-2137.
[18]	张树壮，罗浩，方滨兴．面向网络安全的正则表达式匹配技术[J]．软件学报， 2011,22(8):1838-1853. ZHANG S Z , LUO H , FANG B X . Regular expressions matching for network security[J]. Journal of Software, 2011,22(8):1838-1853.
[19]	MCNAUGHTON R , YAMADA H . Regular expressions and state graphs for automata[J]. IRE Transactions on Electronic Computers, 1960,(1): 39-47.
[20]	Snortrules-snapshot-2956[EB/OL]. , 2014.
[21]	L7-protocols-2009-05-28[EB/OL]. , 2014.
[22]	Regular expression processor[EB/OL]. , 2014.

规则集	snort-snapshot-2 946	L7-filter protocol
规则数目	29 822	114
正则表达式	24 119	114
“.*”出现次数	3 064	62
含“.*”规则数	1291	47
比例	4.3%	41.2%

编号	规则
1	/.ab.cd/
2	/.ef.gh/
3	/.ij.kl/
4	/.mn.op/
5	/.qr.st/
6	/.uv.wx/
7	/.yz.12/
8	/.34.56/

规则数目		状态数目		P
规则数目	NFA		DFA	P
1	7		5	n/a
2	12		16	1.33
3	17		44	2.58
4	22		112	5.09
5	27		272	10.1
6	32		640	20.0
7	37		1 472	39.8
8	42		3 328	79.2

m	DFA状态数
1	5
2	16
3	44
4	112
5	272
6	640
7	1472
8	3328

算法	时间复杂度	状态/存储空间复杂度
NFA	O (m)	O (m)
DFA	O (1)	≥O (m)
MFA	O (1)/O(c)	O (m)/O(cm)