基于混合蛙跳算法优化的正则表达式分组研究

发布时间：2018-04-18 06:46

本文选题：深度包检测 + 网络安全　；参考：《深圳大学》2017年硕士论文

【摘要】：随着信息化社会的不断发展,网络资源共享日趋多样性。在网络不断发展的过程中,网络安全问题成为一项严峻的挑战,因此,对网络安全检测技术的要求越来越高。正则表达式匹配技术以其快速、准确和高效的特点广泛应用于网络内容安全领域,如深度包检测。为了提高匹配效率,正则表达式通常使用确定型有限自动机(deterministic finite automaton,DFA)进行模式匹配。但当规则数量增加时,DFA状态数目迅速膨胀,可能产生超高空间复杂度。采用对正则表达式规则进行分组是解决DFA的状态膨胀导致的巨大空间消耗,实现正则表达式高性能匹配的重要方法。然而现存的一些分组方案未能达到最优的分组结果。本文首先介绍了正则表达式分组问题的研究背景与意义,并简单总结了当前国内外对正则表达式分组问题的研究现状。接着,本文详细描述了混合蛙跳算法的基本原理,以及结合Becchi算法提出了基于混合蛙跳算法的正则表达式分组算法(shuffled frog leaping algorithm for regular expression grouping,SFLA-GRE)。该算法通过重新定义青蛙个体位置信息和改进个体更新公式,并引入群体更新策略,以及结合Becchi算法对正则表达式规则集进行分组优化。通过采用从Linux应用层协议分类器L7-filter和开源的入侵检测系统Snort中随机抽取的正则表达式测试集,然后通过Becchi开源的正则表达式匹配引擎工具生成相应的DFA作为实验数据对算法进行仿真来说明SFLA-GRE算法可进一步优化正则表达式的分组,能提高匹配效率。本文最后尝试将混合蛙跳算法和改进的蚁群算法结合,提出了混合蛙跳与蚁群正则表达式分组算法(grouping regular expressions with SFLA and ACO,SFLA-ACO-GRE);以及在混合蛙跳算法中融入量子计算思想并提出改进的量子混合蛙跳正则表达式分组算法(quantum shuffled frog leaping algorithm for grouping regular expression,QSFLA-GRE),并通过实验仿真来说明这两种算法在求解正则表达式分组问题上具有一定的优化能力。
[Abstract]:With the continuous development of information society, network resource sharing is becoming more and more diverse.In the process of continuous development of network, network security has become a severe challenge. Therefore, the requirement of network security detection technology is becoming higher and higher.The regular expression matching technology is widely used in the field of network content security, such as depth packet detection, because of its fast, accurate and efficient characteristics.In order to improve the matching efficiency, regular expressions usually use deterministic finite automata (DFAs) to match patterns.However, when the number of rules increases, the number of DFA states expands rapidly, which may result in ultra-high space complexity.Grouping regular expression rules is an important method to solve the huge space consumption caused by state expansion of DFA and to realize high performance matching of regular expressions.However, some existing packet schemes fail to achieve optimal packet results.This paper first introduces the research background and significance of the regular expression grouping problem, and summarizes the current research situation of the regular expression grouping problem at home and abroad.Then, the basic principle of hybrid leapfrogging algorithm is described in detail, and a regular expression grouping algorithm based on hybrid leapfrog algorithm is proposed in this paper, which is combined with Becchi algorithm. The proposed regular expression grouping algorithm is shuffled frog leaping algorithm for regular expression grouping and SFLA-GREA.The algorithm redefines the individual location information and improves the individual update formula, and introduces the group update strategy, and combines Becchi algorithm to optimize the regular expression rule set.By using the regular expression test set randomly extracted from the Linux application layer protocol classifier L7-filter and the open source intrusion detection system (Snort),Then the corresponding DFA is generated by the Becchi open source regular expression matching engine to simulate the algorithm to show that the SFLA-GRE algorithm can further optimize the grouping of regular expressions and improve the matching efficiency.In the end of this paper, we try to combine the hybrid leapfrog algorithm with the improved ant colony algorithm.In this paper, a hybrid regular expressions with SFLA and ACOSFLA-ACO-GREA algorithm is proposed, and the quantum computation idea is incorporated into the hybrid leapfrog algorithm and an improved quantum hybrid shuffled frog leaping algorithm algorithm is proposed.For grouping regular expression (QSFLA-GREA), and the experimental results show that the two algorithms have certain optimization ability in solving the regular expression grouping problem.
【学位授予单位】：深圳大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP393.08;TP18

【相似文献】