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

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

通信学报 ›› 2013, Vol. 34 ›› Issue (10): 183-190.doi: 10.3969/j.issn.1000-436x.2013.10.021

• 学术通信 • 上一篇

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

贺炜,郭云飞,扈红超

国家数字交换系统工程技术研究中心，河南郑州450002

出版日期:2013-10-25 发布日期:2017-08-10
基金资助:
国家科技支撑计划基金资助项目;国家科技支撑计划基金资助项目;国家高技术研究发展计划（“863”计划）基金资助项目;国家高技术研究发展计划（“863”计划）基金资助项目;国家高技术研究发展计划（“863”计划）基金资助项目

States constrain-based algorithm for large scale regular expression matching

Wei HE,Yun-fei GUO,Hong-chao HU

National Digital Switching System Engineering Technological R＆D Center,Zhengzhou 450002,China

Online:2013-10-25 Published:2017-08-10
Supported by:
The National Science ＆ Technology Pillar Program;The National Science ＆ Technology Pillar Program;The National High Technology Research and Development Program of China (863 Program);The National High Technology Research and Development Program of China (863 Program);The National High Technology Research and Development Program of China (863 Program)

摘要/Abstract

摘要：

通过观察不确定有限自动机NFA到确定性有限自动机DFA的转化过程，分析内存增长的原因，提出了一种基于状态间约束关系的正则表达式匹配算法 Group²-DFA。Group²-DFA 通过两级分组，利用状态间的约束关系，将原始NFA转化为NFA和DFA的混合结构。实验表明，在保持一定处理速率的前提下，Group²-DFA能够有效地减少内存占用。在300条规则下，Group²-DFA吞吐率能够达到1Gbps，并且减少约75%的状态数。

关键词: 正则表达式, 状态爆炸, 自动机转化, 状态约束

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

贺炜,郭云飞,扈红超. 基于状态约束的大规模正则表达式匹配算法[J]. 通信学报, 2013, 34(10): 183-190.

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.

图/表 11

图1

图2

图3

图4

图5

表1

图6

图7

表2

图8

图9

参考文献 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.

正则表达式数目	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

在线阅读

PDF下载

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 11

参考文献 17

相关文章 13

Metrics

推荐阅读 0

[1]	宫阳阳,刘勤让,杨镇西,邵翔宇,邢池强,焦慧娟,彭志彬. 基于多维有限自动机的DFA改进算法[J]. 通信学报, 2015, 36(5): 174-186.
[2]	丁麟轩，黄昆，张大方. 基于TCAM的低能耗正则表达式匹配算法[J]. 通信学报, 2014, 35(8): 20-168.
[3]	丁麟轩,黄昆,张大方. 基于TCAM的低能耗正则表达式匹配算法[J]. 通信学报, 2014, 35(8): 162-168.
[4]	陈曙晖,徐成成. 基于两级存储的正则表达式匹配技术[J]. 通信学报, 2014, 35(6): 47-55.
[5]	陈曙晖，徐成成. 基于两级存储的正则表达式匹配技术[J]. 通信学报, 2014, 35(6): 7-55.
[6]	敬茂华，杨义先，汪韬，辛阳. 新颖的正则NFA引擎构造方法[J]. 通信学报, 2014, 35(10): 12-106.
[7]	敬茂华,杨义先,汪韬,辛阳. 新颖的正则NFA引擎构造方法[J]. 通信学报, 2014, 35(10): 98-106.
[8]	乔登科1,2，王卿3，柳厅文1,2，孙永1,2，郭莉1,2. 基于状态分组的高效i-DFA构造技术[J]. 通信学报, 2013, 34(8): 14-109.
[9]	乔登科,王卿,柳厅文,孙永,郭莉. 基于状态分组的高效i-DFA构造技术[J]. 通信学报, 2013, 34(8): 102-109.
[10]	唐勇,诸葛建伟,陈曙晖,卢锡城. 蠕虫正则表达式特征自动提取技术研究[J]. 通信学报, 2013, 34(3): 141-147.
[11]	贺炜，郭云飞，扈红超. 基于状态约束的大规模正则表达式匹配算法[J]. 通信学报, 2013, 34(10): 21-190.
[12]	郑天明,王韬,郭世泽,李华,赵新杰. 改进的空间协议识别算法[J]. 通信学报, 2012, 33(5): 183-190.
[13]	杨毅夫,刘燕兵,刘萍,郭牧怡,郭莉. 正则表达式的DFA压缩算法[J]. 通信学报, 2009, 30(10A): 36-42.