特征匹配技术,是计算机科学中一个重要的基础研究领域。当前已被广泛应用于各种网络入侵检测与防御,防病毒以及反垃圾邮件等安全系统中。然而,随着网络攻击的隐蔽性越来越强、种类越来越多,安全系统中特征也越来越复杂,特征集的规模也变得越来越大,这对基于匹配技术的安全系统提出了巨大的挑战。面向网络安全的高性能特征匹配成了一个至关重要的研究领域。本文以安全系统中使用的特征为研究对象,针对网络安全的应用环境,提出了一系列高效的匹配算法。本文的主要贡献包括:提出了一种基于数据感知的串匹配模型。现有的一些经典算法虽然已经达到或接近了理论最优值的上限,但在实际的应用中,各种匹配算法的效率却可能由于很多因素而出现不同程度的退化,特别是待处理数据的特性。基于数据感知的串匹配考虑到了网络环境的局部性对算法性能的影响,因而使用一组而不是单一的算法来完成对输入数据的处理。它通过在匹配过程中对输入数据进行实时分析的结果和算法自身的特性来动态地选择最合适的匹配算法。同时,还提出了一种基于遍历深度统计的决策方法和基于序贯概率比的决策优化方法。这种方法的效率优于单独应用任何一种单一匹配算法,并且可以抵御算法攻击。提出了一种基于转换表共享的DFA内存缩减方法。DFA是目前进行正则表达式匹配最有效的方法之一,但是其高效性是建立在占用大量内存空间来描述每一种“可能性”的基础上。转换表共享首先将DFA状态按照是否拥有相同转换目标项进行分组,然后让每个组内的所有状态共享一个转换表并去除所有的重复项。同时还提出了一个高效的状态分组算法,本算法与同类算法相比,具有更低的时间复杂度和空间复杂度,更加适合在特征集需要动态变化的应用中使用。提出了一种基于猜测-验证的正则表达式匹配方法。DFA内存缩减方法虽然可以消减掉DFA中90%以上的转换边,但却无法彻底解决DFA的空间占用问题。因为DFA的内存是随状态数目呈平方级甚至指数级的增长,而冗余消除只是线性的缩减。基于猜测-验证的匹配方法首先使用DFA对正则表达式中的子特征进行搜索,完成特征存在性的猜测;在猜测到有可能匹配某个特征后,再使用NFA进行验证。这种方法从网络安全检测的行为特点出发,既充分利用了DFA的高效性,减少了对相对较慢的验证过程的调用,又借助NFA避免了内存消耗过于巨大。这种方法可以在大大减少内存需求的情况下,实现大规模正则表达式的高速匹配。综合精确字符串和正则表达式的特点,提出了一种新的规则表示形式–字符串表达式并给出了对应的匹配方法。字符串表达式可以描述多个精确字符串之间的逻辑关系与空间位置关系,从而满足安全系统对复杂特征的描述需求。匹配使用二维结构来完成,首先用经典串匹配算法进行字符串的存在性验证,然后将其结果作为输入,驱动以表达式中字符串为“字符”的扩展有限状态自动机(XFA),完成逻辑关系的验证。基于XFA的匹配方法的空间效率和时间效率都接近其所使用的多模精确串匹配算法。