Improved DFA algorithm based on multi-dimensional finite automata

ONGYang-yang G; IUQin-rang L; ANGZhen-xi Y; HAOXiang-yu S; INGChi-qiang X; IAOHui-juan J; ENGZhi-bin P

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

您当前的位置：

首页 >

文章列表页 >

Improved DFA algorithm based on multi-dimensional finite automata

Academic communication | 更新时间：2024-06-05

- Improved DFA algorithm based on multi-dimensional finite automata
- Journal on Communications Vol. 36, Issue 5, Pages: 174-186(2015)
- 作者机构：
  
  1. 国家数字交换系统工程技术研究中心，河南郑州 450002
  2. 中国石油大学化工学院，山东青岛266555
- 作者简介：
- 基金信息：
  
  The National High Technology Research and Development Program of China (863 Program)(2011AA01A103);TheNationalHighTechnologyResearchandDevelopmentProgramofChina(863Program)(2011AA01A101);The National Basic Research Program of China (973 Program)(2012CB315901);The National Basic Research Program of China (973 Program)(2013CB329104);The National Key Technology R＆D Program of China(2011BAH19B01)
- DOI：10.11959/j.issn.1000-436x.2015101
  CLC： TP393
- Online First：2015-05，
  
  Published：25 May 2015
- 稿件说明：
移动端阅览
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：

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 .

Views

1767

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

States constrain-based algorithm for large scale regular expression matching

Novel NFA engine construction method of regular expressions

Regular expression matching technology with two-stage memory

Efficient i-DFA construction algorithm based on state grouping

Automatic generating regular expression signatures for real network worms

Related Author

Hong-chao HU

Yun-fei GUO

Wei HE

Yang XIN

Tao WANG

Yi-xian YANG

Mao-hua JING

Cheng-cheng XU

Related Institution

National Digital Switching System Engineering Technological R＆D Center

School of Computer and Communication Engineering,Northeastern University at Qinhuangdao

College of Information Science and Engineering,Northeastern University

Beijing Engineering Lab for Cloud Security

Information Security Center,Beijing University of Posts and Telecommunications

AI问答

⁰