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

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

Abstract

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

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.

Figures/Tables 20

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

规则集	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)

Improved DFA algorithm based on multi-dimensional finite automata

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 20

References 22

Related Articles 14

Metrics

Recommended 0

规则数目	NFA		DFA		MFA		DFA vs MFA
规则数目	状态数	存储/KB	状态数	存储/KB	状态数(动态状态数)	存储(辅助变量)/KB	状态压缩率/%	存储压缩率/%
2	12	0.779	16	6.455	10(2)	6.077(0.014)	37.50	5.86
3	17	1.040	44	14.667	15(2)	9.039(0.021)	65.91	38.37
4	22	1.301	112	31.997	20(2)	12.047(0.028)	82.14	62.35
5	27	1.562	272	69.841	25(2)	15.032(0.035)	90.81	78.48
6	32	1.823	640	149.419	30(2)	18.030(0.042)	95.31	87.93
7	37	2.084	1 472	324.355	35(2)	21.063(0.049)	97.62	93.51
8	42	2.345	3 328	684.086	40(2)	24.052(0.056)	98.80	96.48
9	47	2.606	7 424	1 480.794	45(2)	27.029(0.063)	99.39	98.17
10	52	2.867	15 872	2 560.307	50(2)	30.057(0.070)	99.68	99.05

自动机类型	预处理时间	存储	自动机数目	匹配时间/(s·GB^?1)	是否支持全部规则集
DFA	35 min	16.1 GB	n/a	13.8	Y
STT(state merging+D2FA)	7.5 h	789 MB	n/a	220.8	Y
MFA	16 s	10.4 MB	n/a	57.9	N
XFA	90 s	4.64 MB	n/a	80.1	N
Hybrid-FA	11.5 h	7.35 GB	n/a	19.4	Y
mDFA	n/a	47.1 MB	6	231
	n/a	26.4 MB	14	541
	n/a	20.4 MB	37	1 429	Y
	n/a	9.3 MB	56	2 163
	n/a	7.0 MB	72	2 781

[1]	Lin-xuan DING,Kun HUANG,Da-fang ZHANG. Low-power TCAM for regular expression matching [J]. Journal on Communications, 2014, 35(8): 162-168.
[2]	. Low-power TCAM for regular expression matching [J]. Journal on Communications, 2014, 35(8): 20-168.
[3]	Shu-hui CHEN,Cheng-cheng XU. Regular expression matching technology with two-stage memory [J]. Journal on Communications, 2014, 35(6): 47-55.
[4]	. Regular expression matching technology with two-stage memory [J]. Journal on Communications, 2014, 35(6): 7-55.
[5]	. Novel NFA engine construction method of regular expressions [J]. Journal on Communications, 2014, 35(10): 12-106.
[6]	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.
[7]	Deng-ke QIAO,Qing WANG,Ting-wen LIU,Yong SUN,Li GUO. Efficient i-DFA construction algorithm based on state grouping [J]. Journal on Communications, 2013, 34(8): 102-109.
[8]	. Efficient i-DFA construction algorithm based on state grouping [J]. Journal on Communications, 2013, 34(8): 14-109.
[9]	Yong TANG,Jian-wei ZHUGE,Shu-hui CHEN,Xi-cheng LU. Automatic generating regular expression signatures for real network worms [J]. Journal on Communications, 2013, 34(3): 141-147.
[10]	. States constrain-based algorithm for large scale regular expression matching [J]. Journal on Communications, 2013, 34(10): 21-190.
[11]	Wei HE,Yun-fei GUO,Hong-chao HU. States constrain-based algorithm for large scale regular expression matching [J]. Journal on Communications, 2013, 34(10): 183-190.
[12]	Tian-ming ZHENG,Tao WANG,Shi-ze GUO,Hua LI,Xin-jie ZHAO. Improved space protocol identification algorithm [J]. Journal on Communications, 2012, 33(5): 183-190.
[13]	Zhao-xin ZHANG,Yue-jin DU,Bin LI,Hong-li ZHANG. Self-defence model of SIP proxy server for against DoS attack [J]. Journal on Communications, 2009, 30(4): 93-99.
[14]	Yi-fu YANG,Yan-bing LIU,Ping LIU,Mu-yi GUO,Li GUO. Effective algorithm of compressing regular expressions’DFA [J]. Journal on Communications, 2009, 30(10A): 36-42.

规则集	DFA	Hybrid-FA
规则集	状态数	head size	tail size	tails	border size
MFA规则	15634	11704	0	0	0
snort24	23346	12314	42	1	108