基于分布式存储的正则表达式匹配算法设计与实现

发布时间：2018-08-06 16:53

【摘要】：深度包检测(Deep Packet Inspection,DPI)是一种先进的包过滤技术,广泛应用于防火墙中。基于正则表达式的模式匹配算法已成为实现DPI的重要方法之一,传统的正则表达式匹配算法的时间复杂度较高,不能实时进行网络安全的防护。为了提高正则表达式匹配算法的实时性,提出一种基于分布式存储的正则表达式匹配并行算法,该算法通过对数据进行步长计数,采用分布式存储,实现了并行处理。实验分析表明,与传统的串行算法相比,该算法匹配速度至少提高5倍,能够有效降低算法时间复杂度,提高匹配效率。
[Abstract]:Depth packet Inspection (Deep Packet) is an advanced packet filtering technology, which is widely used in firewalls. Pattern matching algorithm based on regular expression has become one of the important methods to implement DPI. The traditional regular expression matching algorithm has high time complexity and can not protect network security in real time. In order to improve the real-time performance of the regular expression matching algorithm, a parallel algorithm for regular expression matching based on distributed storage is proposed. The algorithm realizes parallel processing by counting the step size of the data and using distributed storage. The experimental results show that the matching speed of the algorithm is at least 5 times faster than that of the traditional serial algorithm, which can effectively reduce the time complexity of the algorithm and improve the matching efficiency.
【作者单位】： 西安邮电大学电子工程学院微电子学系;西安电子科技大学微电子学院;
【基金】：国家自然科学基金项目(60976020) 陕西省教育厅科研计划项目(11JK1063,2010JK833)资助
【分类号】：TP393.08

【参考文献】

相关期刊论文 前4条

1 刘俊超;赵国鸿;陈曙晖;;一种用于深度报文检测的DFA状态表压缩方法[J];计算机工程与应用;2008年22期

2 姚远;刘鹏;单征;田双鹏;;面向存储的正则表达式匹配算法综述[J];计算机应用;2009年12期

3 邓凯元;姜磊;;正则表达式匹配引擎性能分析[J];计算机与现代化;2011年07期

4 杨毅夫;刘燕兵;刘萍;郭牧怡;郭莉;;正则表达式的DFA压缩算法[J];通信学报;2009年S1期

相关硕士学位论文 前2条

1 刘胤;深度包检测技术的研究与设计[D];贵州大学;2008年

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

【共引文献】

相关期刊论文 前8条

1 唐球;姜磊;谭建龙;刘金刚;;基于FPGA的正则表达式匹配算法综述[J];计算机应用;2011年11期

2 邓凯元;姜磊;;正则表达式匹配引擎性能分析[J];计算机与现代化;2011年07期

3 朱霖;;深度包检测系统(DPI)在江苏有线网络中的应用[J];江苏科技信息;2012年05期

4 魏德志;洪联系;林丽娜;吴旭;;一种改进的XFA在深度包检测中的应用[J];计算机工程与应用;2012年34期

5 乔磊;李存华;仲兆满;王俊;刘冬冬;;基于规则的人物信息抽取算法的研究[J];南京师大学报(自然科学版);2012年04期

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

7 邱冰;;面向中文语料库的模式检索研究[J];微计算机信息;2012年07期

8 唐球;姜磊;谭建龙;刘金刚;;FPGA实现的正则表达式匹配性能分析[J];小型微型计算机系统;2012年11期

相关硕士学位论文 前10条

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

2 张辉;面向网络流识别的正则表达式匹配技术研究[D];首都师范大学;2011年

3 罗青林;适合应用层协议分类的多正则表达式匹配方法研究[D];首都师范大学;2011年

4 田健;IDS中VLDC模式匹配算法的研究与应用[D];吉林大学;2011年

5 任宝虎;天清汉马USG上网行为管理子系统中协议识别技术的研究和应用[D];北京交通大学;2011年

6 张昌运;基于Windows API的VB编程题自动评分系统的研究与实现[D];大连海事大学;2011年

7 董苹苹;即时通文件传输审计系统的研究与实现[D];中南大学;2011年

8 陈钧君;交通运输行业信息专网改造的设计与实现[D];大连海事大学;2011年

9 张乾;Linux环境下基于正则表达式的DDoS防御算法研究及实现[D];重庆大学;2009年

10 赵文豪;基于SOPC的入侵检测系统的设计与实现[D];电子科技大学;2010年

【二级参考文献】

相关期刊论文 前7条

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

2 陈亮;龚俭;徐选;;基于特征串的应用层协议识别[J];计算机工程与应用;2006年24期

3 郝克刚,段振华,李新;论回溯自动机[J];计算机学报;1990年05期

4 姚远;刘鹏;单征;田双鹏;;面向存储的正则表达式匹配算法综述[J];计算机应用;2009年12期

5 黄昆;张大方;谢高岗;金军航;;一种面向深度数据包检测的紧凑型正则表达式匹配算法[J];中国科学:信息科学;2010年02期

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

7 徐乾;鄂跃鹏;葛敬国;钱华林;;深度包检测中一种高效的正则表达式压缩算法[J];软件学报;2009年08期

相关博士学位论文 前1条

1 黄建;入侵检测系统中字符串匹配算法与实现[D];华中科技大学;2008年

【相似文献】

相关期刊论文 前10条

1 余平;胡玲;;深度包检测消息传递技术[J];内江师范学院学报;2010年08期

2 丁晶;陈晓岚;吴萍;;基于正则表达式的深度包检测算法[J];计算机应用;2007年09期

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

4 范新龙;张华;;探讨编程管理网络设备[J];电脑编程技巧与维护;2010年20期

5 叶文晖,梁里宁;在ASP.NET中利用正则表达式实现模式验证[J];电脑知识与技术;2005年24期

6 刘小波,谢芊,李留英;应用正则表达式在ASP.NET中实现优化的输入验证方法[J];现代图书情报技术;2005年10期

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

8 张瑞;高岭;田密;;基于JS和正则表达式的客户端数据验证方法研究[J];延安大学学报(自然科学版);2008年01期

9 陈艳军;;利用正则表达式开发动态网页[J];数字技术与应用;2010年02期

10 赵书慧;;正则表达式在JSP登录页面中的应用[J];才智;2011年10期

相关会议论文 前10条

1 侯整风;张谷原;;一种基于中文的多模式匹配算法[A];2011中国仪器仪表与测控技术大会论文集[C];2011年

2 王艳秋;兰巨龙;;基于Wu-Manber的快速跳跃多模式匹配算法[A];第四届中国软件工程大会论文集[C];2007年

3 梁兴开;赵泽茂;黄亮;;Web应用中的ReDoS检测方法研究[A];浙江省电子学会2011学术年会论文集[C];2011年

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

5 余刘琅;汪彩萍;程克勤;;基于Snort的检测SQL注入和跨站脚本攻击的正则表达式的探讨[A];中国仪器仪表学会第九届青年学术会议论文集[C];2007年

6 姜继忱;陈钢;;P2P之路——缔造“分布式对等”的Internet3.0[A];全面建设小康社会：中国科技工作者的历史责任——中国科协2003年学术年会论文集（下）[C];2003年

7 万志涛;章恒;张若渊;;基于多核处理器的深度包检测的实现和性能评估[A];中国通信学会信息通信网络技术委员会2009年年会论文集（上册）[C];2009年

8 阮卫挺;马兆丰;;高速网络下的恶意流量检测研究[A];2010年全国通信安全学术会议论文集[C];2010年

9 房友园;齐璇;;Web服务互操作标准符合性测试框架设计与实现[A];全国第20届计算机技术与应用学术会议(CACIS·2009)暨全国第1届安全关键技术与应用学术会议论文集（下册）[C];2009年

10 刘东升;;基于Mobile Agent的分布式ID3挖掘模型[A];2005年全国开放式分布与并行计算学术会议论文集[C];2005年

相关重要报纸文章 前10条

1 ;在论坛中自动显示超链接[N];计算机世界;2006年

2 李梅;存储2.0,基于Web的存储迎面而来[N];计算机世界;2007年

3 ;网络存储[N];中国计算机报;2002年

4 ;软件组[N];计算机世界;2004年

5 仰一凡、王哲;应用校园网生存和发展之本[N];中国计算机报;2002年

6 ;基于IP的存储网络协议[N];人民邮电;2001年

7 美国Watchfire公司战略研究总监 Danny ALLAN;应用扫描:从源头加固Web应用安全[N];中国计算机报;2007年

8 宋义江;广电视频点播系统设计[N];计算机世界;2004年

9 吴征;让Google为动态页面的站点服务[N];计算机世界;2004年

10 本报记者 潘永花;构建网络时代的存储环境[N];网络世界;2000年

相关博士学位论文 前10条

1 侯孟书;基于P2P的分布式存储及其相关技术研究[D];电子科技大学;2005年

2 郭渊博;容忍入侵的理论与方法及其应用研究[D];西安电子科技大学;2005年

3 陈曙晖;基于内容分析的高速网络协议识别技术研究[D];国防科学技术大学;2007年

4 马新新;非结构化对等网信任和信誉机制研究[D];电子科技大学;2009年

5 黄昆;高性能内容过滤与分发技术研究[D];湖南大学;2009年

6 胡燕;基于Web信息抽取的专业知识获取方法研究[D];武汉理工大学;2007年

7 孔宁;物联网资源寻址关键技术研究[D];中国科学院研究生院（计算机网络信息中心）;2008年

8 AMNEH AHMAD ABDELRAHMAN OBEID;Wormhole-Route网中的一种基于路径的多发射简易策略[D];吉林大学;2009年

9 邓林;网络信息安全防护理论与方法的研究[D];合肥工业大学;2009年

10 张宝军;网络入侵检测若干技术研究[D];浙江大学;2010年

相关硕士学位论文 前10条

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

2 刘胤;深度包检测技术的研究与设计[D];贵州大学;2008年

3 田健;IDS中VLDC模式匹配算法的研究与应用[D];吉林大学;2011年

4 丁雪艳;非标准模式匹配算法及其在深度包检测中的应用[D];吉林大学;2012年

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

6 刘子乾;基于攻击模式的系统漏洞检测工具的设计与实现[D];天津大学;2008年

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

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

9 杨琨;反垃圾邮件技术研究及应用[D];四川大学;2005年

10 王琳琳;基于HTML Parser的Web信息提取技术[D];北京邮电大学;2007年

，

本文编号：2168357