论文部分内容阅读
深度包检测技术以其强大的识别能力,现已被广泛应用于各种网络安全设备。然而随着网络带宽的爆炸式增长,如何在大流量网络环境中对数据包实现高速、准确的识别,已引起广大学者的关注。正则表达式以其强大的语言表达能力现已成为规则特征的主要描述方式,通过对正则表达式的匹配实现数据包的识别。目前,正则表达式主要通过不确定性有限自动机(Non-deterministic Finite Automata,简称NFA)、确定性有限自动机(Deterministic Finite Automata,简称DFA)实现,NFA占用空间小,但匹配时间长,DFA的匹配时间短,但存在状态爆炸隐患,导致计算机物理内存不能满足需求,所以两者都不能同时满足实际应用需求。相比较而言,DFA更适合高速网络流量识别,所以近几年的研究焦点主要集中在如何减少DFA的状态数目。本文针对上述问题,以高性能的正则表达式匹配引擎为主要的研究对象,深入分析了DFA状态爆炸原因。提出:先对正则表达式集分组,减少正则表达式之间的冲突所引起的状态数增加,然后将每一组正则表达式进行联合编译生成组合DFA,最后再对各组生成的组合DFA进行状态压缩。在此基础上,结合实际项目,详细阐述了深度包检测的具体实现。本文主要完成了以下内容:第一,深入研究了不同类型正则表达式的DFA结构特征,分析了单个DFA和组合DFA状态爆炸的原因;第二,针对组合DFA的状态爆炸问题。在前人的工作基础上,改进了一种近似比为1/(1-1/6))的正则表达式分组算法,经模拟测试表明,改进后的分组算法在分组效率上优于改进前,具有一定的适用性;第三,根据DFA状态间的相似度,提取状态转移表中的公共状态,将公共状态形成的状态转移表与提取公共状态后的原状态转移表分开存储,实现对状态的压缩。公共状态的提取属于聚类问题,然而传统的聚类方法普遍存在聚类时间过长,对此,本文采用并实现了一种基于最大生成树的层次聚类算法。第四,实现了改进后的正则表达式分组算法和基于最大生成树的公共状态提取算法,并通过实验证明基于上述算法的先分组后压缩的设计方案在处理大规模模式匹配方面的优越性。第五,以实际项目为背景,结合作者的工作内容,详细阐述了深度包检测方法在高速网络流量识别系统中的具体实现,并通过实际测试,给出系统的性能表现。