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

宫阳阳; 刘勤让; 杨镇西; 邵翔宇; 邢池强; 焦慧娟; 彭志彬

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

您当前的位置：

首页 >

文章列表页 >

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

学术通信 | 更新时间：2024-06-05

- 基于多维有限自动机的DFA改进算法
- Improved DFA algorithm based on multi-dimensional finite automata
- 通信学报 2015年36卷第5期页码：174-186
- 作者机构：
  
  1. 国家数字交换系统工程技术研究中心，河南郑州 450002
  2. 中国石油大学化工学院，山东青岛266555
- 作者简介：
  
  [ "宫阳阳（1988-），男，河南濮阳人，国家数字交换系统工程技术研究中心硕士生，主要研究方向为宽带信息网络及系统级芯片设计。" ]
  [ "刘勤让（1975-），男，河南睢县人，博士，国家数字交换系统工程技术研究中心研究员、硕士生导师，主要研究方向为宽带信息网络及系统级芯片设计。" ]
  [ "杨镇西（1971-），男，山东郓城人，博士，国家数字交换系统工程技术研究中心副研究员，主要研究方向为系统级芯片设计。" ]
  [ "邵翔宇（1992-），男，河南清丰人，国家数字交换系统工程技术研究中心硕士生，主要研究方向为宽带信息网络及系统级芯片设计。" ]
  [ "邢池强（1989-），男，河南邢台人，国家数字交换系统工程技术研究中心硕士生，主要研究方向为宽带信息网络。" ]
  [ "焦慧娟（1989-），女，山东菏泽人，中国石油大学硕士生，主要研究方向为有限元分析。" ]
  [ "彭志彬（1988-），男，河南濮阳人，国家数字交换系统工程技术研究中心硕士生，主要研究方向为模式识别及数据挖掘。" ]
- 基金信息：
  
  国家高技术研究发展计划（“863”计划）基金资助项目(2011AA01A103);国家高技术研究发展计划(“863”计划)基金资助项目(2011AA01A101);国家重点基础研究发展计划（“973”计划）基金资助项目(2012CB315901);国家重点基础研究发展计划（“973计划）基金资助项目(2013CB329104);国家科技支撑计划基金资助项目(2011BAH19B01)
- DOI：10.11959/j.issn.1000-436x.2015101
  中图分类号： TP393
- 网络出版日期：2015-05，
  
  纸质出版日期：2015-05-25
- 稿件说明：
移动端阅览
宫阳阳, 刘勤让, 杨镇西, 等. 基于多维有限自动机的DFA改进算法[J]. 通信学报, 2015,36(5):174-186.

ONGYang-yang G, IUQin-rang L, ANGZhen-xi Y, et al. Improved DFA algorithm based on multi-dimensional finite automata[J]. Journal on communications, 2015, 36(5): 174-186.
宫阳阳, 刘勤让, 杨镇西, 等. 基于多维有限自动机的DFA改进算法[J]. 通信学报, 2015,36(5):174-186. DOI： 10.11959/j.issn.1000-436x.2015101.

ONGYang-yang G, IUQin-rang L, ANGZhen-xi Y, et al. Improved DFA algorithm based on multi-dimensional finite automata[J]. Journal on communications, 2015, 36(5): 174-186. DOI： 10.11959/j.issn.1000-436x.2015101.

摘要

多个正则表达式规则编译成一个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个数量级。

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.

关键词

Keywords

references

HOPCROFT J E , ULLMANJ D . Introduction to Automata Theory,Languages and Computation 2nd Edition [M ] . US : Addison Wesley , 2001 .

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 .

徐乾，鄂跃鹏，葛敬国等．深度包检测中一种高效的正则表达式压缩算法 [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 .

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 .

张树壮，罗浩，方滨兴等．一种面向网络安全检测的高性能正则表达式匹配算法 [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 .

乔登科，王卿，柳厅文等．基于状态分组的高效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 .

贺炜，郭云飞，扈红超．基于状态约束的大规模正则表达式匹配算法 [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 .

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 .

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 .

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 .

张大方，张洁坤，黄昆．一种基于智能有限自动机的正则表达式匹配算法 [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 .

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 .

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 .

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 .

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 .

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 .

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 .

张树壮，罗浩，方滨兴．面向网络安全的正则表达式匹配技术 [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 .

MCNAUGHTON R , YAMADA H . Regular expressions and state graphs for automata [J ] . IRE Transactions on Electronic Computers , 1960 ,( 1 ): 39 - 47 .

Snortrules-snapshot-2956 [EB/OL ] . http://www.snort.org/snort-rules/? http://www.snort.org/snort-rules/? , 2014 .

L7-protocols-2009-05-28 [EB/OL ] . http://l7-filter.clearfoundation.com/downloads/start http://l7-filter.clearfoundation.com/downloads/start , 2014 .

Regular expression processor [EB/OL ] . http://regex.wustl.edu/index.php/Main_Page http://regex.wustl.edu/index.php/Main_Page , 2014 .

浏览量

1269

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

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

新颖的正则NFA引擎构造方法

基于两级存储的正则表达式匹配技术

基于状态分组的高效i-DFA构造技术

蠕虫正则表达式特征自动提取技术研究