基于人工鱼群算法的正则表达式分组研究

发布时间：2021-07-06 01:50

　　面对日益复杂的网络攻击,传统基于精准字符串的模式匹配不能胜任复杂多变的网络环境,正则表达式以其灵活,高效,表达能力强的特点迅速成为高速网络环境中匹配引擎用于描述规则的语言,在网络安全领域有着重要的应用。深度包检测技术中采用正则表达式描述网络协议。采用正则表达式描述“某种规则”十分高效、简洁,多条正则表达式描述的规则可以合并生成一个DFA引擎,可以实现一次扫描完成对所有的规则的匹配。但基于DFA正则表达式匹配引擎存在“状态膨胀”的问题,不同的正则表达式合并后,在理论最糟糕的情况下,会导致合并后的匹配引擎状态数呈指数增长,造成巨大的内存空间占用,以至于普通的电脑硬件平台难以完成大规模规则的模式匹配工作。降低DFA的存储空间需求是实现正则表达式高效率匹配亟待解决的问题,对正则表达式进行合理的分组是解决DFA的状态膨胀的重要方式。然而现有的分组算法所求的分组结果并不理想,未能在分组数和总状态数上找到一个恰当的平衡点,未能实现分组数和总状态数的双重最优。首先,本文分析了当前正则表达式分组的研究现状和现有分组算法的不足,随后,在第2章中,针对当前分组策略的不足,创新性的提出了两种新的分组策略,即最... 

【文章来源】：深圳大学广东省

【文章页数】：75 页

【学位级别】：硕士

【部分图文】：

NFA状态转化图

基于人工鱼群算法的正则表达式分组研究求是实现正则表达式高速匹配广泛应用 2-1时间复杂度OODFA 和 NFA 的存储消耗和处理复杂度对一条正则表达式 m 条正则表达内存消耗 时间复杂度 (n2) O(n) O(n2m) (1) O(∑2) O(1)

组算法和 Becchi 分组算法[21]进行比较，表 2-2 所示的是规则集选取于入侵rt 的分组结果对比。为了进一步说明本文提出的最小冲突分组算法的有效合在选取方面，我们从大规模正则表达式集合中抽取了 15 组规则集合，算法进行仿真实验，规则条数从 N=4 条开始到 N=110 条，在表 2-3 和 2-4则集选取于 L7-filter 的分组情况。表 2-2 snort 规则集合分组结果对比规则集合 N= 4 10 16 23 40不分组(状态数/组数) 76/1 3461/1 5867/1 8204/1 19019/1Becchi(状态数/组数) 30/3 335/5 509/5 698/5 1744/5GREMC(状态数/组数) 30/3 308/5 454/5 628/6 1432/5


本文编号：3267273