面向网络入侵检测的正则表达式DFA优化技术研究

发布时间：2017-06-03 08:15

  本文关键词：面向网络入侵检测的正则表达式DFA优化技术研究，由笔耕文化传播整理发布。

【摘要】：近些年,随着网络的迅猛发展,网络逐渐大众化,特别是近两年,网络的速度不断增快,很多网络程序不断开发出来。伴随多种多样的网络程序的出现,也出现了更多的针对网络应用层的攻击。2013年,知名度高、用户数量庞大的支付宝和财付通均遭遇了黑客攻击,引发了人们对网络安全防范的重视。以往,利用防火墙抵抗入侵是最为普遍的入侵防御手段。这种方式应用在内网与外网之间,进行防御,对网络数据进行检测。但是,面对多样和多方面的新型网络攻击,防火墙技术并不能进行有效的防御和抵抗,容易导致拥塞或者溢出,而且如果网络入侵是通过合法端口而进行的也很难进行有效的防御,对待内部主动发起连接的入侵一般很难防御等缺点。因此,近年来,主要应用于应用层上的网络入侵检测方式由此产生。近年来,网络安全领域的研究人员越来越多的将研究方向集中在如何提高深度包检测的效率。正则表达式由于其敏捷性与适应性慢慢地代替了原有的匹配方式因而被广泛地应用于各种入侵检测系统中。正则表达式匹配分为基于确定性的正则表达式匹配和基于非确定性的正则表达式匹配。两相比较,DFA匹配速度更快,但需要占用更大的空间,NFA可以节省空间,但匹配的速度却不尽人意。但是,由于NFA的匹配是不确定的,因此结果也可能的多种情况同时存在,匹配效率会大大降低,DFA的匹配是确定的,其结果也是唯一的,而在现实的网络世界中,匹配效率是十分关键的,因此,DFA由于其高效率的匹配过程而得到了广泛的应用,但是由于DFA的匹配与NFA不同,DFA是确定化的匹配,因此,DFA在匹配过程中需要包含全部的可能性,因此DFA状态转移图中的每一个结点均包含了全部可能的状态转移边。另外由于正则表达式的长度限制会使DFA的状态数量呈指数增长,导致状态爆炸,同时对存储空间的需求也会增加。本文深入分析了DFA算法的原理,得出了该算法的优点与缺点,根据该算法的缺点分析了优化的方向,设计高性能的正则表达式压缩算法,在上述前期工作的基础上,着重研究了DDFA算法,并且编程实现了DDFA算法,并通过对规则集的实验比较了DDFA算法与DFA算法之间的异同,并且通过实验发现了该算法存在着匹配效率较低的缺点,随后,本文将DFA算法所具备的优点与DDFA算法所具备的优点融合在了一起,设计并实现了一种基于DFA的正则表达式优化算法,对DFA进行了有效的压缩,同时也尽可能地保证了算法的匹配效率不会下降太多。最后,我们通过实验验证了该算法的匹配效率,该算法对空间的占用情况,该算法的运行时间,并分别与DFA算法进行了对比,得出最后的结论。
【关键词】：网络入侵检测 正则表达式 DFA优化技术
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP393.08
【目录】：

• 摘要4-6
• Abstract6-11
• 第1章 绪论11-15
• 1.1 研究背景11-12
• 1.2 国内外研究现状12-13
• 1.3 论文主要工作13-14
• 1.4 论文组织结构14-15
• 第2章 正则表达式15-22
• 2.1 概述15
• 2.2 正则表达式15-16
• 2.3 自动机16-17
• 2.4 非确定性有限自动机17-19
• 2.5 确定性有限自动机19-20
• 2.6 NFA与DFA的对比20-21
• 2.7 本章小结21-22
• 第3章 入侵检测系统22-27
• 3.1 入侵检测系统22-25
• 3.1.1 入侵检测系统结构22-23
• 3.1.2 入侵检测系统原理23-25
• 3.2 Snort25-26
• 3.3 Bro26
• 3.4 本章小结26-27
• 第4章 基于延迟匹配的正则表达式匹配算法27-38
• 4.1 DFA不足的分析27
• 4.2 DFA优化方法27-30
• 4.3 算法流程图30-32
• 4.4 算法描述32
• 4.5 实验与结果分析32-37
• 4.5.1 状态转移图实验32-34
• 4.5.2 算法的压缩性能测试34-37
• 4.6 本章小结37-38
• 第5章 DFA压缩算法38-52
• 5.1 引言38
• 5.2 正则表达式压缩算法38-44
• 5.2.1 算法背景与设计思想38-40
• 5.2.2 算法流程40-43
• 5.2.3 算法描述43-44
• 5.3 系统结构设计与实现44-48
• 5.3.1 正则表达式转NFA模块45-48
• 5.3.2 NFA转换DFA模块48
• 5.3.3 DFA优化压缩模块48
• 5.4 实验与结果48-51
• 5.4.1 实验环境48-49
• 5.4.2 实验一：算法匹配效果测试49-50
• 5.4.3 实验二：算法空间压缩性能测试50-51
• 5.4.4 实验三：算法运行时间测试51
• 5.5 本章小结51-52
• 第6章 总结与展望52-54
• 6.1 本文工作总结52
• 6.2 展望52-54
• 参考文献54-56
• 作者简介及在学期间取得的科研成果56-57
• 致谢57

【相似文献】

中国期刊全文数据库 前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];解放军信息工程大学;2014年

4 邵翔宇;正则表达式匹配存储优化技术研究[D];解放军信息工程大学;2015年

5 历博源;面向网络入侵检测的正则表达式DFA优化技术研究[D];吉林大学;2016年

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

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

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

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

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

  本文关键词：面向网络入侵检测的正则表达式DFA优化技术研究，由笔耕文化传播整理发布。

，

本文编号：417622