多模式匹配算法的性能分析

孙友仓

（西安石油大学 计算机学院，陕西 西安 710065）

多模式匹配算法的性能分析

孙友仓

（西安石油大学 计算机学院，陕西 西安 710065）

多模式匹配算法效率直接影响入侵检测系统的性能和效率。在分析研究经典的AC算法、WM算法和ExB算法的基础上,通过上机实验测试这些算法的模式匹配时间,为改进多模式匹配算法提供有益的借鉴。

多模式匹配；AC算法；WM算法；ExB算法

多模式匹配算法在很多领域都有重要应用,如拼写检查、语言翻译、数据压缩、搜索引擎、网络入侵检测、计算机病毒特征码匹配等[1]。研究高效的多模式匹配算法具有非常重要的理论和现实意义。

所谓多模式匹配，就是在文本串T[1，…，n]中一次匹配多个模式串P1,P2,…，Pk，其中k为模式串的个数。k=1时，即为单模式匹配。模式串 Pj的长度为mj,即 Pj[1，…，mj]（1≤j≤k），minlen是最短模式串的长度，即minlen=min{mj|（1≤j≤q）}。多模式匹配比多个模式串逐个进行传统单模式匹配的速度快得多。

1 多模式匹配算法

1.1 AC算法

采用AC算法进行匹配需先对模式串集合进行预处理，形成树型有限状态自动机，然后只需对文本串扫描1次就可找出与其匹配的所有模式串[2]。

AC算法在预处理阶段生成3个函数：goto（转移）函数、failure（失效）函数和output（输出）函数。匹配过程从有限状态自动机的初始状态出发，每取出文本串中的一个字符，利用goto函数和failure函数进入下一状态；当某个状态的output函数不为空时输出其值，表示在文本串中匹配到该模式串[3-4]。

AC算法在对文本串进行搜索时无跳跃，而是按顺序输入字符，无法跳过不必要的比较，因此在模式数目不是非常多的实际搜索过程中，AC算法性能不佳。AC算法模式匹配的时间复杂度是O（n），而且与模式集中模式串的个数和每个模式串的长度无关，无论模式串P是否出现在T中，T中的每个字符都必须输入状态机中，所以无论是最好情况还是最坏情况，AC算法模式匹配的时间复杂度都是O（n），包括预处理时间在内AC算法的总时间复杂度是O（M+n），其中M为所有模式串的长度总和。

1.2 WM算法

WM快速字符串匹配算法采用BM算法进行跳跃的思想和hash散列方法，在实际应用中，是大规模多模式匹配最快的算法之一[5]。WM算法将文本串以B个字符长度分块，称该B个字符为1个块字符，B为块字符的长度，B通常取2或3。首先对模式集进行预处理，在预处理阶段构造3个表，即shift表、hash表和prefix表。匹配过程从文本串text的第（m-B+1）（m是模式集中模式串的最小长度）个字符处开始，每次计算当前块字符的hash值h，通过shift[h]的值决定是否向后跳跃；当shift[h]的值为0时，将hash[h]链表中的每一个模式串从后向前与text比较，如果未达到text末尾，则将text向后移动1个字符继续比较。

WM算法的主要优点是字符跳跃距离大，使用shift表可以跳过那些不可能成功的匹配入口，匹配入口点少，从而减少字符比较次数。因此实际应用中，WM算法的效率一般比AC算法高。但WM算法在每个匹配入口点处，要逐个比较hash[h]表中每一个模式，在模式集数目较大时，算法性能明显下降。

WM算法在模式匹配中采用启发式搜索策略进行字符跳跃，匹配的时间复杂度平均情况是O（Bn/m），实际应用中B≤m，所以WM算法模式匹配的时间复杂度低于AC算法。

1.3 ExB算法

ExB 算法是一个基于排除的字符串匹配算法，该算法能很快排除数据包负载中不包含匹配模式串的数据包[6]。其思想是：假设要检测字符串A中是否包含子串s，如果s中至少有1个字符不包含在A中，则s就不是A的1个子串。为了减少错误匹配的概率，将该算法扩充到字符对，匹配过程不仅检测s中每个字符是否出现在A中，还检测每一字符对中的字符出现的顺序是否正确。为了快速判定给定的字符c是否属于字符串A，该算法采用出现图的方法。对于A中出现的字符c在出现图中的相应位置采用二进制值标记，“1”表示c属于A，“0”表示c不属于A。对于每个新数据包，出现图都要进行一次大开销清零工作。为了减少这种开销，采用每个数据包的序列号取代二进制值来标记出现图中的相应位置，这样出现图就无需对每一个新数据包都进行清零。

该算法可分为预处理和搜索两个阶段。预处理阶段的时间复杂度与数据包负载的大小成线性关系，搜索阶段的时间复杂度与所有模式中的长度和成线性关系。由于在多数数据集中，入侵数据包毕竟是少数。另外，据统计仅有1.6%的数据包需要用标准的字符串匹配算法进一步确定该入侵特征串是否在数据包中,因此调用标准串匹配算法的概率很小，所以在实际应用中，该算法的效率高于其他应用于入侵检测中的匹配算法。

2 算法性能测试和结果分析

对多模式匹配算法进行模拟测试。测试环境：CPU是Intel Pentium E2200 2.2 G，内存1 G，硬盘160 G，操作系统Windows 2003，算法实现环境是Visual C++6.0。利用入侵检测训练数据集[7]，选取1天的流量数据（容量约160 MB的Tcpdump文件）作为测试数据集。入侵检测系统分别采用AC算法、WM算法和ExB算法作为模式匹配检测引擎,测试这3种情况下平均模式匹配时间与模式数目的变化关系，对比情况如表1所示。

由表1可知，模式数小于20个时ExB算法最优，模式数在50～100时AC算法的匹配效率更好，当模式数大于100时，WM算法性能更好。测试结果与理论分析基本吻合。

?

3 结束语

随着网络应用的发展和网络带宽的增加，必须提高网络入侵检测系统的处理性能。而目前的网络入侵检测系统多是基于特征匹配的系统，这类系统中的关键运算是模式匹配，因此提高模式匹配的效率是提高这类系统检测能力的关键。本文对已有的多模式匹配算法进行性能分析，为今后改进多模式匹配算法提供有益的借鉴。

[1]唐 谦，张大方.入侵检测中模式匹配算法的性能分析[J].计算机工程与应用,2005（17）：136-138.

[2]Aho A V,Corasickm J.Efficient string matching:an aid to bibliographic search[J].Communications of the ACM,1975,18（6）：333-340.

[3]李 庚，韩 进，谢 立.入侵检测中一种新的多模式匹配算法[J].计算机应用研究,2008，25（8）：2474-2476.

[4]赵念强，鞠时光.入侵检测系统中模式匹配算法的研究[J].微计算机信息,2005,21（8-3）：22-24.

[5]WU Sun,Manber U.Fast algorithm for multi-pattern sear ching[R].Tucson:Department of computer science university of arizona,1994.

[6]李红霞，王新生，王建东.一种应用于入侵检测的基于排除的模式匹配算法[J].电子技术应用,2006（1）:41-43.

[7]Graf IL，Ippmann R，Cunningham R，et al.Results of DARPA 1998 offline intrusion detection evaluation[EB/OL].1998.http://ideval.ll.mit.edu/results-html-dir.

Performance analysis of multiple pattern matching algorithm

SUN You-cang
（School of Computer Science,Xi＇an Shiyou University，Xi＇an710065,China）

The multiple pattern matching algorithm directly impacts on intrusion detection system performance and efficiency.On the basis of reseaching and analysing the classic AC algorithm,WM algorithm and ExB algorithm,the pattern matching time of these algorithms are tested through hands-on experiment.It provides helpful reference for improving the multiple pattern matching algorithm.

multiple pattern matching;AC algorithm;WM algorithm;ExB algorithm

TP393.08

A

1674－6236（2010）01-0017-02

2009-08-16 稿件编号：200908029

孙友仓（1967—），男，陕西白水人，副教授。研究方向：网络安全与应用。