基于遗传算法的正则表达式规则分组优化

发布时间：2017-11-17 00:05

  本文关键词：基于遗传算法的正则表达式规则分组优化

  更多相关文章： 自适应遗传算法 局部优化 深度包检测 正则表达式 分组算法

【摘要】：随着互联网技术的迅速发展,新的网络应用和服务不断出现。随之,网络带宽迅速扩大,致使待检测规则集的规模越来越庞大和复杂。因而功能强大的正则表达式成为描述规则的新一代工具,并成功的应用于深度包检测技术中。然而,在某种情况下,多条正则表达式生成合并DFA时会出现状态膨胀问题,导致巨大的存储空间消耗甚至无法生成。通过对正则表达式集合进行分组是解决这一问题的主要方法。目前,已有不少研究者对分组算法进行了研究并提出了解决方案,但分组结果并不理想,不能有效解决DFA空间消耗过大的问题,有待进一步优化。首先,本文介绍了正则表达式分组的研究背景与意义以及国内外研究现状。其次,本文介绍了最近邻优化算法,通过定义DFA状态矩阵并按最近邻原则进行排序,然后采用从前往后局部优化搜索策略来解决正则表达式分组问题;概括性地阐述了遗传算法的基本思想及在各个领域的应用。为解决正则表达式匹配问题,提出一种基于正态自适应遗传优化的改进正则表达式分组算法REG-NAGA。根据迭代次数和适应度集中程度两个因素的侧重不同,利用正态函数自适应地改变交叉概率Pc和变异概率Pm,采取最优保存策略保证最优个体不被大的Pc和Pm破坏,另外,结合Becchi算法以及局部寻优算法来进一步优化。最后,本文分别从snort、L7-filter这两个开源系统中随机抽取若干条正则表达式作为测试集,并以Becchi开源的正则表达式匹配引擎为工具生成的DFA作为实验数据,对算法进行仿真。本文实现了用于求解正则表达式分组问题的最近邻优化算法和基于正态自适应遗传优化的改进正则表达式分组算法REG-NAGA。仿真结果表明,REG-NAGA算法能在全局范围内搜索到更好的解,能有效减少状态总数,降低正则表达式匹配的空间复杂度。
【学位授予单位】：深圳大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP393.08;TP18

【参考文献】

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

1 刘荷花;崔超;陈晶;;一种改进的遗传算法求解旅行商问题[J];北京理工大学学报;2013年04期

2 张树壮;罗浩;方滨兴;云晓春;;一种面向网络安全检测的高性能正则表达式匹配算法[J];计算机学报;2010年10期

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

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

5 吴虎胜;张凤鸣;赵法栋;;利用自适应混合遗传算法求解平车装载问题[J];铁道学报;2013年12期

6 蔡良伟;刘思麒;李霞;李军;;基于蚁群优化的正则表达式分组算法[J];深圳大学学报(理工版);2014年03期

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

1 位二伟;二倍体自适应遗传算法在函数优化中的应用[D];重庆大学;2012年

，

本文编号：1194109