全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...
电子学报  2012 

一种基于智能有限自动机的正则表达式匹配算法

DOI: 10.3969/j.issn.0372-2112.2012.08.019, PP. 1617-1624

Keywords: 深度数据包检测,正则表达式匹配,确定型有限自动机,扩展有限自动机,智能有限自动机

Full-Text   Cite this paper   Add to My Lib

Abstract:

本文提出了一种基于智能有限自动机(SmartFiniteAutomaton,SFA)的正则表达式匹配算法,在XFA的分支迁移边上增加额外的判断操作指令,消除XFA的回退迁移边,避免不必要的状态迁移操作.实验结果表明,SFA提高了正则表达式匹配的时空效率,与XFA相比,在存储空间开销上减少了44.1%,在存储器访问次数上减少了69.1%.

References

[1]  V Paxson,K Asanovic,S Dharmapurikar,et al.Rethinking hardware support for network analysis and intrusion prevention.Proceedings of USENIX Workshop on Hot Topics in Security 2006.Vancouver:USENIX Press,2006.
[2]  R Smith,C Estan,S Jha,et al.Deflating the big bang:Fast and scalable deep packet inspection with extended finite automata.Proceedings of ACM SIGCOMM 2008.Seattle:ACM Press,2008.
[3]  B Commentz-Walter.A string matching algorithm fast on the average.Proceedings of 6th Colloquium on Automata,Languages and Programming.London:Springer-Verlag Press,1979.
[4]  S Kumar,S Dharmapurikar,F Yu,et al.Algorithms to accelerate multiple regular expressions matching for deep packet inspection.Proceedings of ACM SIGCOMM 2006.Pisa:ACM Press,2006.
[5]  J Zhang,D Zhang,K Huang.A regular expression matching algorithm using transition merging.Proceedings of IEEE PRDC.Shanghai:IEEE Press,2009.242-246.
[6]  F Yu,Z Chen,Y Diao,et al.Fast and memory-efficient regular expression matching for deep packet inspection.Proceedings of ACM/IEEE ANCS 2006.San Jose:ACM Press,2006.
[7]  S Kumar,B Chandrasekaran,J Turner.Curing regular expressions matching algorithms from insomnia,amnesia,and acalculia.Proceedings of ACM/IEE ANCS 2007.Orlando:IEEE Press,2007.155-164.
[8]  黄昆,张大方,谢高岗,金军航.一种面向深度数据包检测的紧凑型正则表达式匹配算法[J].中国科学:信息科学,2010,40(2):356-370. Huang Kun,Zhang Da-fang,Xie Gao-gang,Jin Jun-hang.A compact regular expression matching algorithm for deep packet inspection[J].SCIENCE CHINA Information Sciences,2010,40(2):356-370.(in Chinese)
[9]  M Roesch.Snort-lightweight intrusion detection for networks.Proceedings of LISA 1999.Seattle:USENIX Press,1999.
[10]  V Paxson.Bro:A system for detecting network intruders in real-time[J].Computer Networks,1999,31(23-24):2435-2463.
[11]  R Smith,C Estan,S Jha.XFA:Faster signature matching with extended automata.Proceedings of IEEE Symposium on Security and Privacy 2008.Oakland:IEEE Press,2008.
[12]  A V Aho,M J Corasick.Efficient string matching:An aid to bibliographic search.Communications of the ACM,1975,18(6):333-340.
[13]  S Kumar,J Turner,J Williams.Advanced algorithms for fast and scalable deep packet inspection.Proceedings of ACM/IEEE ANCS 2006.San Jose:ACM Press,2006.
[14]  M Becchi,S Cadambi.Memory-efficient regular expression search using state merging.Proceedings of IEEE INFOCOM 2007.Anchorage:IEEE Press,2007.

Full-Text

Contact Us

[email protected]

QQ:3279437679

WhatsApp +8615387084133