论文部分内容阅读
传统深度包检测技术通过精确字符串对病毒进行描述,这种方法效率很低,已经无法适用于流量极大的互联网数据流。正则表达式具有简单、高效、表达能力强的特点,特别适合应用于深度包检测中。在实际使用中可以将多条正则表达式合并生成一个DF A引擎,实现一次匹配多条正则表达式的目的,提高匹配效率。但是当多条正则表达式解析为一个DFA引擎时,存在“状态爆炸”的问题。理论上,在最糟糕的情况下,这种现象会使DFA状态数呈指数增长,导致普通硬件平台无法生成DFA。研究表明,对正则表达式进行合理的分组是解决该问题的一个有效方法,所以将能引起“状态爆炸”的正则表达式分到不同组,将没有引起“状态爆炸”的正则表达式分到相同组可以有效避免该问题。分组的目标是在尽可能短的时间内得到各组DFA总状态数最少、分组数最少、各组状态数标准差最小的结果。然而,现有的分组算法存在分组时间过长、各组状态数标准差偏大、DFA状态数偏大的问题,分组结果并不理想。研究发现,目前大多数正则表达式分组算法需要不断生成DFA引擎以判断是否发生了“状态爆炸”,这个过程导致了算法的分组时间较长。在第2章中,为了提高分组效率,本文改进了已有的正则表达式DFA状态数预估公式并且提出了基于正则表达式预估膨胀率的分组算法(GRE-EER),该算法根据预估公式求得正则表达式间的预估膨胀率并且用其来指导分组,不需生成DFA引擎,可以较大地提高分组效率并且得到初步的分组结果;为了得到准确的分组结果,提出基于正则表达式真实膨胀率的分组算法(G RE-RER)。GRE-RER根据正则表达式间的真实膨胀率来指导分组,可以得到准确的分组结果;为了尽可能减小DFA存储空间,加入局部优化算法。在实际使用中,为了高效率地得到分组结果,将GRE-EER、GRE-RER与局部优化算法相互结合,提出GREEER-RER策略。为了使算法具有全局搜索能力,本文在第3章中将模拟退火算法和GRE-EER-RER相结合,提出基于模拟退火算法的正则表达式分组算法(GRE-SAA)。在该算法中模拟退火算法负责在全局范围内搜索最优解,不断生成新解使用GRE-EER进行分组,其分组结果满足一定条件再对该解使用GRE-RER进行分组。为使GRE-SAA适用于大规模规则集,对其进行了改进,提出了适用于大规模规则集的GRE-SAA算法。实验结果表明,GRE-SAA对小规模、中等规模和大规模规则集均有很好的分组能力,在DFA状态总数、各组状态数标准差以及分组时间等方面均优于其他全局搜索算法。为进一步提高算法的收敛能力和搜索能力,本文将模拟退火算法、遗传算法和GR E-EER-RER相结合,提出基于遗传模拟退火算法的正则表达式分组算法(GRE-GASA)。设计实验将其与GRE-SAA进行对比分析。实验结果表明,对于小规模和中等规模规则集,该算法收敛能力以及分组结果优于GRE-SAA,但是分组效率不及GRE-SAA。故在对分组效率要求不高的情况下,建议使用GRE-GASA,否则建议使用GRE-SAA。最后为使GRE-GASA适用于大规模规则集,对其进行改进并且设计实验与其他算法进行对比分析。实验结果表明对于大规模规则集,GRE-GASA与GRE-SAA的分组结果差不多,均优于Becchi算法。