基于并行字符索引的多步长正则表达式匹配算法

发布时间：2017-07-17 06:01

  本文关键词：基于并行字符索引的多步长正则表达式匹配算法

  更多相关文章： 正则表达式匹配 三态内容可寻址存储器 并行字符索引 分块存储 低能耗

【摘要】：深度包检测(deep packet inspection,DPI)是网络入侵检测与防御系统(network intrusion detection and prevention system,NIDPS)的核心.基于三态内容可寻址存储器(ternary content addressable memory,TCAM)的正则表达式匹配算法提高了数据包的处理速度,成为DPI技术的一个重要研究方向.TCAM具有查找速度快、存储空间小等特性,且能耗与存储空间成正比.由于DFA的存储空间开销比较大,且存储空间大小随着DFA步长数的增加而指数倍增,基于TCAM的DFA面临高能耗的问题,特别是多步长DFA.提出一种基于并行字符索引的多步长正则表达式匹配算法(multi-stride parallel character-indexed DFA,PCIDFA),对确定型有限自动机(deterministic finite automaton,DFA)构造并行字符索引,通过比特位图取交集,减少匹配时激活的TCAM块数,显著降低TCAM能耗.实验结果表明:与多步长DFA相比,多步长PCIDFA在TCAM能耗上减少了99.8%以上,在TCAM存储空间开销上减少了48.5%~65.3%,在吞吐量上提高了1.9~2.6倍.
【作者单位】： 湖南大学信息科学与工程学院;中国科学院计算技术研究所;
【关键词】： 正则表达式匹配 三态内容可寻址存储器 并行字符索引 分块存储 低能耗
【基金】：国家“九七三”重点基础研究发展计划基金项目(2012CB315805) 国家自然科学基金项目(61173167,61100171)
【分类号】：TP393.08
【正文快照】： 开销上减少了48.5%~65.3%,在吞吐量上提高了1.9~2.6倍.随着网络应用的日益增多,网络安全面临着越来越严峻的挑战.网络入侵检测与防御系统(networkintrusion detection and prevention system,NIDPS)是网络安全防御的主要手段,它通过实时监测网络流量,检查和阻止网络攻击[1].深

【相似文献】

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

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

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

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

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

5 马永萍;;正则表达式及其应用[J];电脑编程技巧与维护;2012年04期

6 侯秀红;董峰;;Visual Basic 6.0中正则表达式的应用[J];郑州轻工业学院学报;2005年04期

7 杨树林;;正则表达式在网络教学系统中的应用[J];北京印刷学院学报;2005年04期

8 黄晓春;孟岩;;理解正则表达式(下)[J];程序员;2007年06期

9 魏蓉;王文忠;仲兰芬;;正则表达式在现代汉语语法处理中的应用[J];阴山学刊(自然科学版);2007年04期

10 李丽莉;李娅;周琪云;;正则表达式在网络信息监控分析系统中的应用[J];信息技术;2008年04期

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

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

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

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

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

5 李佳;魏更宇;胡楠;王枞;杨义先;;基于特征自生成的畸形SIP信令检测算法[A];2010通信理论与技术新发展——第十五届全国青年通信学术会议论文集（下册）[C];2010年

6 周小甲;周庆利;;中文病历文本中时间信息自动标注[A];2011年浙江省医学会医学工程学分会第九届学术年会论文汇编[C];2011年

7 周小甲;周庆利;;中文病历文本中时间信息自动标注[A];浙江生物医学工程学会第九届年会论文汇编[C];2011年

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

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

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

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

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

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

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

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

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

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

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

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

8 金军航;面向深度包检测的存储高效的正则表达式匹配算法研究[D];湖南大学;2010年

9 王焕云;面向深度数据包检测的正则表达式匹配算法研究[D];湖南大学;2012年

10 蒋俐峗;基于多步投机的正则表达式匹配算法的研究[D];湖南大学;2011年

，

本文编号：552199