一种针对DFA状态爆炸的正则表达式匹配方法

doi:10.19678/j.issn.1000-3428.0049992

计算机工程 ›› 2019, Vol. 45 ›› Issue (4): 148-156. doi: 10.19678/j.issn.1000-3428.0049992

一种针对DFA状态爆炸的正则表达式匹配方法

王翔^1,2,3,卢毓海^2,3,马伟^2,3,刘燕兵^2,3

1.中国科学院大学网络空间安全学院,北京 100049; 2.中国科学院信息工程研究所,北京 100093; 3.信息内容安全技术国家工程实验室,北京 100093

收稿日期:2018-01-08 出版日期:2019-04-15 发布日期:2019-04-15
作者简介:王翔(1993—),男,硕士研究生,主研方向为模式匹配、内容过滤;卢毓海,博士研究生;马伟、刘燕兵,副研究员。
基金资助:
国家重点研发计划(2016YFB0800303);中国科学院信息工程研究所基础前沿项目(Y7Z0351101)。

A Regular Expression Matching Method for DFA State Explosion

WANG Xiang^1,2,3,LU Yuhai^2,3,MA Wei^2,3,LIU Yanbing^2,3

1.School of Cyber Security,University of Chinese Academy of Sciences,Beijing 100049,China; 2.Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100093,China; 3.National Engineering Laboratory for Information Security Technologies,Beijing 100093,China

Received:2018-01-08 Online:2019-04-15 Published:2019-04-15

摘要/Abstract

摘要：

针对基于确定有限状态自动机的匹配引擎在大规模、复杂规则下会出现状态爆炸的问题,提出正则表达式子串抽取算法。通过将子串抽取算法应用于DFA状态爆炸场景,设计基于子串抽取的正则匹配引擎。实验结果表明,该算法在单个规则上运行时间可达10 ms量级,抽取率高达99%,同时匹配引擎具有较好的稳定性和可拓展性,且匹配速度优于相关开源匹配引擎。

关键词: 正则表达式, 确定有限自动机, 状态爆炸, 子串抽取, 匹配引擎

Abstract:

Aiming at the problem that the Deterministic Finite Automation(DFA)-based matching engine will explode under large-scale and complex rules,a regular expression substring extraction algorithm is proposed.A substring extraction based regular matching engine is designed by applying the substring extraction algorithm to the DFA state explosion scenario.Experimental results show that the algorithm can run on a single rule up to 10 ms,and the decimation rate is as high as 99%.At the same time,the matching engine has better stability and scalability,and the matching speed is better than the related open source matching engine.

Key words: regular expression, Deterministic Finite Automaton(DFA), state explosion, substring extraction, matching engine

中图分类号:

TP39

王翔,卢毓海,马伟,刘燕兵. 一种针对DFA状态爆炸的正则表达式匹配方法[J]. 计算机工程, 2019, 45(4): 148-156.

WANG Xiang,LU Yuhai,MA Wei,LIU Yanbing. A Regular Expression Matching Method for DFA State Explosion[J]. Computer Engineering, 2019, 45(4): 148-156.

http://www.ecice06.com/CN/Y2019/V45/I4/148

参考文献

［1］褚衍杰,李云照,魏强.一种改进的多模式匹配算法［J］.西安电子科技大学学报(自然科学版),2014(6):174-180.
［2］赵毅,朱鹏,迟学斌,等.浅析高性能计算应用的需求与发展［J］.计算机研究与发展,2007,44(10):1640-1646.
［3］XU C,CHEN S,SU J,et al.A survey on regular expression matching for deep packet inspection:applications,algorithms,and hardware platforms［J］.IEEE Communications Surveys and Tutorials,2016,18(4):2991-3029.
［4］刘燕兵.高性能正则表达式匹配技术研究［D］.北京:中国科学院大学,2012.
［5］BECCHI M,CADAMBI S.Memory-efficient regular expression search using state merging［C］//Proceedings of the 26th IEEE International Conference on Computer Communications.Washington D.C.,USA:IEEE Press,2007:1064-1072.
［6］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.
［7］FICARA D,PIETRO A D,GIORDANO S,et al.Differential encoding of DFAs for fast regular expression matching［J］.IEEE/ACM Transactions on Networking,2011,19(3):683-694.
［8］KONG S,SMITH R,ESTAN C.Efficient signature matching with multiple alphabet compression tables［C］//Proceedings of the 4th International Conference on Security and Privacy in Communication Networks.New York,USA:ACM Press,2008.
［9］LIU Y,GUO L,LIU P,et al.Compressing regular expressions’ DFA table by matrix decomposition［C］//Proceedings of the 15th International Conference on Implementation and Application of Automata.Berlin,Germany:Springer,2010:282-289.
［10］SMITH R,ESTAN C,JHA S.XFA:faster signature matching with extended automata［C］//Proceedings of IEEE Symposium on Security and Privacy.Washington D.C.,USA:IEEE Computer Society,2008:187-201.
［11］SMITH R D.Toward robust network payload inspection［D］.Madison,USA:University of Wisconsin at Madison,2009.
［12］YANG Y E,PRASANNA V K.Space-time tradeoff in regular expression matching with semi-deterministic finite automata［C］//Proceedings of IEEE International Conference on Computer Communications.Washington D.C.,USA:IEEE Press,2011:1853-1861.
［13］MAJUMDER A,RASTOGI R,VANAMA S.Scalable regular expression matching on data streams［C］//Proceedings of ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press,2008:161-172.
［14］ROHRER J,ATASU K,LUNTEREN J,et al.Memory-efficient distribution of regular expressions for fast deep packet inspection［C］//Proceedings of the 7th IEEE/ACM International Conference on Hardware/Software Codesign and System Synthesis.New York,USA:ACM Press,2009:147-154.
［15］WATSON B W.A new regular grammar pattern matching algorithm［J］.Theoretical Computer Science,1996,299(1/2/3):364-377.
［16］NAVARRO G.NR-grep:a fast and flexible pattern-matching tool［J］.Practice and Experience,2001,31(13):1265-1312.
［17］YANG X,QIU T,WANG B,et al.Negative factor:improving regular-expression matching in strings［J］.ACM Transactions on Database Systems,2016,40(4).

[1]	杨嘉佳,姜腊林,姜磊,戴琼,谭建龙. 基于簇聚类和游程编码的正则表达式压缩算法[J]. 计算机工程, 2014, 40(8): 282-287,292.
[2]	魏强, 李云照, 褚衍杰. 基于图划分的正则表达式分组算法[J]. 计算机工程, 2012, 38(18): 137-139.
[3]	李莲春, 周金治. 网络音视频语义信息抽取系统[J]. 计算机工程, 2011, 37(13): 269-271.
[4]	叶文晨, 汪敏, 陈云寰, 张之远. 一种联合DPI和DFI的网络流量检测方法[J]. 计算机工程, 2011, 37(10): 102-104.
[5]	陈建明, 刘松, 李志蜀, 丁革建. 基于形式化监控的可信软件构造模型[J]. 计算机工程, 2011, 37(01): 65-68.
[6]	郭牧怡;刘萍;谭建龙;郭莉. 基于文件标题特征的网络视频去重研究[J]. 计算机工程, 2010, 36(9): 227-229,.
[7]	田里. NIDS中正则表达式匹配电路的改进与优化[J]. 计算机工程, 2010, 36(3): 136-138.
[8]	金军航, 张大方, 黄昆. 高性能正则表达式匹配算法评估[J]. 计算机工程, 2010, 36(19): 269-271.
[9]	刘鹏, 姚远, 邰铭, 张铮. 一种高效匹配PCRE的扩展自动机[J]. 计算机工程, 2010, 36(12): 39-42.
[10]	宋友;梁士兴;黄璐;. 通用文本处理方法的研究与设计[J]. 计算机工程, 2010, 36(06): 1-4.
[11]	董敏;毕盛;齐德昱. 基于正则表达式的测试数据自动生成技术[J]. 计算机工程, 2009, 35(16): 29-31.
[12]	刘扬;何华灿. 基于匹配引擎覆盖网络的网格资源发现模型[J]. 计算机工程, 2008, 34(2): 154-156.
[13]	国德峰;汪更生;宋毅. 一种基于贝叶斯网络的匹配引擎设计[J]. 计算机工程, 2008, 34(17): 211-213.
[14]	王功明;吴华瑞;赵春江;杨宝祝. 正则表达式在电子政务客户端校验中的应用[J]. 计算机工程, 2007, 33(09): 269-271.
[15]	肖健宇;张德运;陈海诠;董皓. 用于克服程序状态空间爆炸的条件化预处理[J]. 计算机工程, 2006, 32(19): 51-53.

选择文件类型/文献管理软件名称

选择包含的内容

一种针对DFA状态爆炸的正则表达式匹配方法

A Regular Expression Matching Method for DFA State Explosion

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

一种针对DFA状态爆炸的正则表达式匹配方法

A Regular Expression Matching Method for DFA State Explosion

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价