论文部分内容阅读
深度包检测技术在网络安全应用中发挥着重要作用。随着入侵特征的不断复杂化，正则表达式由于其强大的表达能力逐渐成为深度包检测系统描述入侵特征的主要语言，正则表达式匹配也逐步成为了网络安全领域的研究热点。网络带宽的爆炸增长和网络入侵特征的不断复杂化给深度包检测带来了巨大的压力，正则表达式匹配需要在有限的内存资源下进行线速的高效匹配。 传统的基于非确定化有限自动机(Non-deterministic Finite Automaton，NFA)的正则表达式匹配技术由于其需要在匹配过程中多次访问内存的缺点已经无法满足深度包检测的实时性要求。越来越多的网络安全应用开始采纳基于确定化有限自动机(Deterministic Finite Automaton，DFA)的正则表达式匹配技术，但是DFA会遇到状态膨胀的问题。NFA状态的部分确定化技术可以生成一个状态空间和匹配效率介于NFA与DFA之间的复合自动机。复合自动机兼有NFA内存消耗小和DFA高效匹配效率的优点，因此吸引了国内外很多学者的关注。由于无法找到NFA部分确定化的准确位置，现有的复合自动机只在一部分正则表达式下面有着良好的匹配效率。本文以NFA状态关系为入口，研究一种的新的NFA部分确定化技术。本文的贡献主要有以下几个方面: 1.研究NFA状态关系的获取技术。基于NFA状态所代表的语言集合，采用了三个变量将NFA的状态关系分为等价、包含、被包含、互斥和相交等五种关系;提出了一个通过有限自动机(Finite Automaton，FA)的活跃状态集来准确计算状态关系的算法，并给出了一个高效的获取所有活跃状态集的方法。实验结果证明，该方法不仅能准确地得到状态关系，而且其空间占用和时间消耗仅是已有方法的1/256和15％左右。 2.研究基于NFA状态关系的NFA部分确定化技术。基于获得的NFA状态相交关系，提出了一个获取NFA导致状态膨胀的状态—毒瘤状态的方法;基于子集构造法，提出了一个新的复合自动机(Excl-deterministic Finite Automata，EFA)的构造方法。实验结果证明，EFA有着近似于DFA的匹配效率同时状态规模只有DFA的1/10左右。 3.研究EFA的优化技术。提出了基于状态分组的的优化技术，通过将具有相交关系的NFA状态尽量分到不同的状态组来尽量降低EFA的状态规模;提出了基于i-DFA的优化技术，采用i-DFA的存储结构存储EFA，保证EFA的匹配过程中同时最多只有i个活跃状态。