入侵检测中一种新的多模式匹配算法摘要：基于模式匹配的检测方法是目前入侵检测系统的一种重要方法，因此作为模式匹配方法核心的字符串匹配算法直接影响入侵检测系统的性能和效率。在AC算法和Wu-Manber算法的研究基础上，提出了一种新的多模式匹配算法――AC-WM。该算法能够增加字符跳转距离，比较稳定地减少匹配过程中字符比较的次数，提高匹配的速度和效率。关键词：入侵检测；多模式匹配；AC算法；Wu-Manber算法；AC-WM算法：TP393.08文献标志码：A：1001-3695(2008)08-2474-03NewmultiplepatternsmatchingalgorithminintrusiondetectionLIGeng??a,b??,HAN激n??a,b??,XIELi??a,b??(a.Dept.ofComputerScienceTechnology,b.StateKeyLaboratoryforNovelSoftwareTechnology,Nan激ngUniversity,Nan激ng210093,China)Abstract:Thedetectionmethodbasedonpatternsmatchingisanimportantmethodinintrusiondetectionsystem,andthekeyofthisistheefficiencyofstringmatchingwhichinfluencestheefficiencyofdetectiondirectly.Thispaperanalyzedsomemultiplepatternsmatchingalgorithms,suchasACalgorithmandWu-Manberalgorithm,andthenpresentedanewmultiplepatternsmatchingalgorithmnamedAC-WM.AC-WMalgorithmcanincreasethejumpingdistanceofcharactersanddecreasethecomparisoninmatchingprocess.Inthiscase,itimprovesthematchingefficiency.Keywords:intrusiondetection;multiplepatternsmatching;ACalgorithm;Wu-Manberalgorithm;AC-WMalgorithm随着网络技术的发展，网络环境变得越来越复杂，对于网络安全来说，单纯的防火墙技术暴露出明显的不足和弱点，如无法解决安全后门问题；不能阻止网络内部攻击；不能提供实时入侵检测能力；对于病毒束手无策等。入侵检测系统是继防火墙和信息加密等安全保障技术之后出现的新一代网络安全防护系统，能够有效地弥补上述安全系统的不足。它通过对计算机网络或计算机系统中的若干关键点收集信息并对其进行分析，实时地发现网络或系统中是否有违反安全策略的行为和被攻击的迹象，并采取相应措施以避免攻击的发展或尽量减少攻击造成的危害。按照所采用的检测技术，入侵检测系统可以分为误用检测系统和异常检测系统。误用检测系统使用模式匹配的方法来发现入侵行为，是目前入侵检测系统的主流。所以，作为模式匹配方法核心的字符串匹配算法直接影响入侵检测系统的性能和效率。字符串匹配算法分为单模式匹配算法和多模式匹配算法两大类。经典的单模式匹配算法包括Knuth-Morris-Patt算法(KMP算法)[1]、Boyer-Moore算法(BM算法)[2]和QuickSearch算法[3]等。经典的多模式匹配算法包括AC算法[4]和Wu-Manber快速字符串匹配算法[5,6]等。本文主要讨论在入侵检测系统中广泛应用的多模式匹配算法。1多模式匹配算法分析1.1Aho-Corasick算法[4](AC算法)Aho-Corasick算法是同时搜索多个模式的经典匹配算法。它在进行匹配之前先对模式串集合进行预处理，形成树型有限状态自动机，然后只需对文本串扫描一次就可以找出与其匹配的所有模式串。AC算法在预处理阶段生成三个函数：goto（转移）函数、failure（失效）函数和output（输出）函数。匹配过程从有限状态自动机的初始状态出发，每取出文本串中的一个字符，利用goto函数和failure函数进入下一状态；当某个状态的output函数不为空时输出其值，表示在文本串中匹配到该模式串。对多模式串的匹配而言，AC算法比KMP、BM等单模式匹配算法高效得多。但是AC算法在对文本串进行搜索时没有跳跃，而是按顺序输入字符，无法跳过不必要的比较，因此在模式数目不是非常多的实际搜索过程中，AC算法性能不佳。1.2Wu-Manber算法[5,7~9]Wu-Manber快速字符串匹配算法采用了BM算法进行跳跃的思想和hash散列的方法，在实际应用中，是大规模多模式匹配最快的算法之一。Wu-Manber算法将文本串以??B??个字符长度分块，称该??B??个字符为一个块字符，??B??为块字符的长度，??B??通常取2或3。首先对模式集进行预处理，在预处理阶段构造三个表，即shift表、hash表和prefix表。匹配过程从文本串text的第??m-B+1??个字符处开始（??m??是模式...