基于状态约束的大规模正则表达式匹配算法

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

Abstract

Abstract:

By analysis of state explosion in deterministic finite automata DFA,a novel algorithm Group²-DFA based on state constrains was proposed to reduce the memory usage.With the state constrains,states in NFA were classified into several groups.Group²-DFA introduces two-level classification and merges NFA and DFA together to a hybrid FA construction.The experiments show that Group²-DFA can reduce memory usage efficiently and keep high throughput with a small increase of memory reading time.With 300 regex rules,Group²-DFA can cut 75% states and achieve 1Gbps throughput.

Key words: regular expression, state explosion, automata convert, state constrains

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.

Figures/Tables 11

References 17

[1]	JIANG L , TAN J , LIU Y . ClusterFA:a memory-efficient DFA struc-ture for network intrusion detection[A]. Proceedings of the 7th ACM Symposium on Computer and Communications Security Information[C]. New York,USA, 2012. 65-66.
[2]	BECCHI M , CROWLEY P . Efficient regular expression evaluation:theory to practice[A]. Proceedings of the 4th ACM/IEEE Symposium on Architectures for Networking and Communications Systems[C]. Colorado:ACM, 2008. 50-59.
[3]	YANG Y H E , JIANG W , PRASANNA V K . Compact architecture for high-throughput regular expression matching on FPGA[A]. Pro-ceedings of the 4th ACM/IEEE Symposium on Architectures for Net-working and Communications Systems[C]. San Jose,California,USA, 2008. 30-39.
[4]	ZHENG K , ZHANG X , CAI Z ,et al. Scalable NIDS via negative pattern matching and exclusive pattern matching[A]. Proceedings IEEE International Conference on Computer Communications,Joint Conference of the IEEE Computer and Communications Societies[C]. San Dieg, 2010. 1-9.
[5]	李奇越 . 网络内容分析中基于硬件的字符串匹配算法的研究[D]. 合肥 :中国科技大学, 2008. LI Q Y . String Matching Algorithm Research based on Hardware in Network,Content Analysis[D]. Hefei:University of Science and Tech-nology of China, 2008.
[6]	LIN C H , HUANG C T , JIANG C P ,et al. Optimization of regular expression pattern matching circuits on FPGA[A]. Proceedings of De-sign,Automation and Test in Europe[C]. Germany, 2006. 1-6.
[7]	LE H , PRASANNA V . A memory-efficient and modular approach for large-scale string pattern matching[J]. IEEE Transactions on Comput-ers, 2013,62(5): 844-857.
[8]	BECCHI M , CROWLEY P . A hybrid finite automaton for practical deep packet inspection[A]. Proceedings of ACM CoNEXT Conference[C]. New York,USA, 2007. 1-12.
[9]	YU F , CHEN Z , DIAO Y ,et al. Fast and memory-efficient regular expression matching for deep packet inspection[A]. ACM/IEEE Sym-posium on Architecture for Networking and Communications System[C]. San Jose,California,USA, 2006. 93-102.
[10]	PASETTO D , PETRINI F , AGARWAL V . Tools for very fast regular expression matching[J]. Computer, 2010,43(3): 50-58.
[11]	QI Y , WANG K , FONG J ,et al. FEACAN:front-end acceleration for content-aware network processing[A]. Proceedings of 30th IEEE In-ternational Conference on Computer Communications,Joint Confe-rence of the IEEE Computer and Communications Societies[C]. Shanghai,China, 2011. 2114-2122.
[12]	LIU T , YANG Y , LIU Y ,et al. An efficient regular expressions compression algorithm from a new perspective[A]. Proceedi s of 30th IEEE International Conference on Computer Communications,Joint Conference of the IEEE Computer and Communications Societies[C]. Shanghai,China, 2011. 2129-2137.
[13]	ANTONELLO R , FERNANDES S , SADOK D ,et al. Deterministic finite automaton for scalable traffic identification:the power of com-pressing by range[A]. Network Operations and Managemen Sympo-sium (NOMS)[C]. Piscataway:IEEE, 2012. 155-162.
[14]	WOODS L , TEUBNER J , ALONSO G . Complex event detection at wire speed with FPGAs[J]. The VLDB Endowment, 2010,3(1-2): 660-669.
[15]	YANG Y H E , PRASANNA V K . Space-time tradeoff in regular expression matching with semi-deterministic finite automata[A]. Pro-ceedings of 30th IEEE International Conference on Comp Com-munications,Joint Conference of the IEEE Computer and Communi-cations Societies[C]. Shanghai,China, 2011. 1853-1861.
[16]	Sourcefire,SNORT[EB/OL]. , 2012.
[17]	International computer science institute,bro intrusion detection system[EB/OL]. , 2012.

Metrics

Recommended 0

No Suggested Reading articles found!

正则表达式数目	NFA状态数	single-DFA数量
16	418	15
20	524	18
24	571	21
34	882	33
217	2 130	59
300	11 145	133

算法	snort24	snort34	bro217	dotstar300
NFA	571	882	2 130	11 145
DFA	8 334	9 753	6 532	＞100 000
Group²-DFA	1 743	2 356	2 974	3 341

States constrain-based algorithm for large scale regular expression matching

RichHTML

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

Figures/Tables 11

References 17

Related Articles 13

Metrics

Recommended 0

[1]	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.
[2]	. Low-power TCAM for regular expression matching [J]. Journal on Communications, 2014, 35(8): 20-168.
[3]	Lin-xuan DING,Kun HUANG,Da-fang ZHANG. Low-power TCAM for regular expression matching [J]. Journal on Communications, 2014, 35(8): 162-168.
[4]	Shu-hui CHEN,Cheng-cheng XU. Regular expression matching technology with two-stage memory [J]. Journal on Communications, 2014, 35(6): 47-55.
[5]	. Regular expression matching technology with two-stage memory [J]. Journal on Communications, 2014, 35(6): 7-55.
[6]	. Novel NFA engine construction method of regular expressions [J]. Journal on Communications, 2014, 35(10): 12-106.
[7]	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.
[8]	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.
[9]	. Efficient i-DFA construction algorithm based on state grouping [J]. Journal on Communications, 2013, 34(8): 14-109.
[10]	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.
[11]	. States constrain-based algorithm for large scale regular expression matching [J]. Journal on Communications, 2013, 34(10): 21-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]	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.