刘卫国，胡勇刚

(中南大学 信息科学与工程学院，湖南 长沙，410083)

目前，大多数网络入侵检测系统(Network intrusion detection system，NIDS)的检测引擎采用的是模式匹配技术。测试结果表明，系统用于模式匹配的时间占到NIDS整个处理时间的30%，在网络流量密集情况下达 80%[1]。因此，通过改进模式匹配算法能有效地提高系统的检测速度。模式匹配算法包括单模式匹配算法和多模式匹配算法，常见的单模式匹配算法有 Knuth-Morris-Patt(KMP)算法[2]和 Boyer-Moore(BM)算法[3]等。其中，BM算法应用较广泛, 其检测速度比KMP算法速度快3～5 倍，但在模式集规模较大时，BM 算法的效率难以满足实际要求。多模式匹配算法包括 Aho-Corasick(AC)算法[4]和 Wu-Manber(WM)算法[5]等。AC算法是在 KMP算法的基础上采用有限状态机原理构造模式树，在模式数目较多时能获得较高的查找效率，但通常构造模式树会占用大量的存储空间。WM算法主要基于字符跳跃思想和Hash散列技术，能大大提高匹配速度。近年来，很多研究者通过改进 WM 算法以获得更高的查找效率。Yang等[6]结合QS算法思想[7]提出了QWM算法，在查找阶段利用文本的前缀匹配信息判断是否进行匹配操作，并扩大窗口的最大滑动距离，改进后的算法比WM算法查找时间更少。Choi等[8]通过增加最短模式串长度提出L+1-MWM算法，可以得到更长的滑动距离；当最短模式串长度小于5时，该算法比WM算法平均查找时间减少38.87%。但改进后的算法在大规模模式集情况下，也像WM算法那样无法避免在哈希表中出现长度过长的模式链表，为此，研究者们通过减少在Hash表中的链表查找时间来提高匹配速度。……