导　　师： 蔡良伟

授予学位： 硕士

作　　者： (）;

机构地区： 深圳大学

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

关 键 词： 正则表达式 智能算法 深度包检测 人工鱼群算法 分组算法 网络安全

领　　域： []