一种高效的正则表达式匹配方法

发布时间：2017-09-16 00:13

  本文关键词：一种高效的正则表达式匹配方法

  更多相关文章： 深度包检测 正则表达式 子集分割 有限自动机 混合自动机

【摘要】：为实现网络安全检测中大规模正则表达式的匹配,分析了在从非确定型有限自动机(NFA)到确定型有限自动机(DFA)的子集构造过程中导致状态爆炸性增长的原因,并提出了一种高效的正则表达式匹配方法。这种方法通过将部分DFA状态转变成受限的NFA状态来消除状态数量的剧烈增长,并会形成一种DFA状态与受限的NFA状态交替出现的有限自动机,称为DNFA。DNFA将DFA与NFA结合在一起,实现匹配速度与内存空间占用的平衡,其多层结构也更加适合复杂正则表达式规则。实验结果表明,上述方法可以在大大减少内存需求的情况下,实现正则表达式的高效匹配。
【作者单位】： 北京邮电大学网络技术研究院;
【关键词】： 深度包检测 正则表达式 子集分割 有限自动机 混合自动机
【基金】：科技支撑计划(2012BAH37B02,2012BAH42B02) 863计划(2012AA03001) 242计划(2013A012,2013A133)资助项目
【分类号】：TP393.08
【正文快照】： 0引言 述,因此,越来越多的正则表达式被应用到网络安全的各个方面,例如Linux应用层协议分类器(Linux当今,深度包检测技术巳被广泛应用于网络安 Application Protocol Classifier,L7[4]),开源的人侵检全的各个方面,例如人侵检测系统(intrusion detec- 测系统Snort[5]、Bro[6],

【参考文献】

中国期刊全文数据库 前1条

1 陈曙晖;苏金树;范慧萍;侯婕;;一种基于深度报文检测的FSM状态表压缩技术[J];计算机研究与发展;2008年08期

【共引文献】

中国期刊全文数据库 前10条

1 丁麟轩;黄昆;张大方;;基于并行字符索引的多步长正则表达式匹配算法[J];计算机研究与发展;2015年03期

2 徐成成;陈曙晖;;NetMagic平台上正则表达式匹配技术实现[J];小型微型计算机系统;2015年02期

3 陈曙晖;徐成成;;基于两级存储的正则表达式匹配技术[J];通信学报;2014年06期

4 张树壮;吴志刚;罗浩;;一种高效的正则表达式匹配方法[J];高技术通讯;2014年06期

5 马珂;;试论MD5算法的安全分析及破解[J];现代妇女(下旬);2014年05期

6 杨雨;胡亚娟;林萍;;正则表达式在英语语调统计分析中的应用研究[J];平顶山学院学报;2013年05期

7 肖明明;余顺争;;基于文法推断的协议逆向工程[J];计算机研究与发展;2013年10期

8 马珂;;U保证MD5算法的安全分析及破解[J];中国-东盟博览;2013年03期

9 郑天明;王韬;郭世泽;李华;赵新杰;;改进的空间协议识别算法[J];通信学报;2012年05期

10 张树壮;罗浩;方滨兴;;面向网络安全的正则表达式匹配技术[J];软件学报;2011年08期

【二级参考文献】

中国期刊全文数据库 前2条

1 李伟男;鄂跃鹏;葛敬国;钱华林;;多模式匹配算法及硬件实现[J];软件学报;2006年12期

2 王永成,沈州,许一震;改进的多模式匹配算法[J];计算机研究与发展;2002年01期

【相似文献】

中国期刊全文数据库 前10条

1 王甲春;;正则表达式的五个良好习惯[J];中文信息;2003年11期

2 白红哲,马立勇;基于正则表达式的话务报告处理软件的实现[J];通信管理与技术;2005年02期

3 孟岩;;一夫当关——《精通正则表达式》书评[J];程序员;2007年08期

4 ;新书上架[J];程序员;2007年10期

5 路个的;;请个伙伴,助你成长为正则表达式高手[J];电脑爱好者;2008年23期

6 余晟;;正则表达式随笔[J];程序员;2008年03期

7 余晟;;正则表达式随笔(续)[J];程序员;2008年09期

8 周健锋;;正则表达式的强大功能[J];电脑知识与技术;2009年16期

9 夏阳阳;李建华;;新疆勘探生产经营管理系统中正则表达式的应用[J];办公自动化;2009年20期

10 李国晶;王景强;;浅析正则表达式[J];科技资讯;2010年04期

中国重要会议论文全文数据库 前4条

1 管杰裕;;正则表达式在气象信息处理中的应用[A];2005年广西气象学会学术年会论文集[C];2005年

2 刘琪;牛文静;;正则表达式在恶意代码动态分析中的应用[A];2009通信理论与技术新发展——第十四届全国青年通信学术会议论文集[C];2009年

3 王辉;丁明君;杨进;;正则表达式在企业信息管理开发中的应用[A];2010年MIS/S&A学术交流会议论文集（中国造船工程学会学术论文集）[C];2010年

4 田珂;赵国鸿;;利用TCAM与正则表达式对邮件协议进行二次识别的思想研究[A];第十六届计算机工程与工艺年会暨第二届微处理器技术论坛论文集[C];2012年

中国重要报纸全文数据库 前1条

1 彭福祥 张钧;ASP.NET基本数值处理技巧[N];计算机世界;2006年

中国博士学位论文全文数据库 前1条

1 彭坤杨;基于TCAM的高速可扩展的正则表达式匹配技术[D];中国科学技术大学;2013年

中国硕士学位论文全文数据库 前10条

1 韩家宝;图数据搜索引擎Trinity中正则表达式匹配子系统的设计与实现[D];哈尔滨工业大学;2015年

2 徐成成;基于两级存储的正则表达式匹配技术研究[D];国防科学技术大学;2013年

3 李哲夫;正则表达式在电信业务处理中的应用研究[D];暨南大学;2008年

4 范慧萍;基于正则表达式的协议识别研究与实现[D];国防科学技术大学;2007年

5 段海生;基于正则表达式的深度包压缩算法研究[D];西安电子科技大学;2010年

6 姜英杰;支持正则表达式的文本匹配优化算法[D];东北大学;2012年

7 张洁坤;时空高效的正则表达式匹配算法研究[D];湖南大学;2010年

8 张娜;基于正则表达式的深度包检测研究[D];华东师范大学;2007年

9 刘鹏;面向存储的正则表达式匹配算法研究[D];解放军信息工程大学;2010年

10 刘俊超;基于正则表达式的应用层协议识别技术研究[D];国防科学技术大学;2008年

，

本文编号：859734