基于WM算法的多模式匹配改进算法WMN

１２８　２００７，４３（１５）　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　

基于ＷＭ算法的多模式匹配改进算法ＷＭＮ　

袁世忠　，曹　曼　，王燕燕　

ＹＵＡＮ　Ｓｈｉ－ｚｈｏｎｇ　，ＣＡＯ　Ｍｉｎ　，ＷＡＮＧ　Ｙａｎ—ｙａｎ。　

１．上海大学计算机工程与科学学院．上海２０００７２　

２．中原工学院数理系，郑州４５０００７　

１．Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ＆Ｓｃｉｅｎｃｅ，Ｓｈａｎｇｈａｉ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ　２０００７２．Ｃｈｉｎａ　

２．Ｃｏｌｌｅｇｅ　ｏｆ　Ｓｃｉｅｎｃｅ，Ｚｈｏｎｇｙｕａｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，Ｚｈｅｎｇｚｈｏｕ　４５０００７，Ｃｈｉｎａ　

ＹＵＡＮＳｈｉ—ｚｈｏｎｇ．ＣＡＯ　Ｍｉｎ，ＷＡＮＧ　Ｙａｎ—ｙａｎ．Ｉｍｐｒｏｖｅｄ　ｐａｔｔｅｒｎ　ｍａｔｃｈｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ＷＭ．Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ，２００７，４３（１５）：１２８－１３０．　

Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｉｎｔｒｕｓｉｏｎ　ｄｅｔｅｃｔｉｏｎ　ｓｙｓｔｅｍ　ａｌｗａｙｓ　ｓｐｅｎｄｓ　ｓｏｍｅ　ｔｉｍｅ　ｏｎ　ｐａｔｔｅｒｎ　ｍａｔｃｈｉｎｇ，ｔｈｕｓ　ｓｐｅｅｄｉｎｇ　ｐａｔｔｅｒｎ　ｍａｔｃｈｉｎｇ　ａｌｇｏｒｉｔｈｍ　

ｉｓ　ａ　ｓｉｇｎｉｆｉｃａｎｔ　ｒｅｓｅａｒｃｈ．Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｅｓｅｎｔｓ　ａｎ　ｉｍｐｒｏｖｅｄ　ｐａｔｔｅｒｎ　ｍａｔｃｈｉｎｇ　ａｌｇｏｒｉｔｈｍ，ｃａｌｌｅｄ　ＷＭＮ，ｉｎ　ｗｈｉｃｈ　ｔｈｅ　ｄｕｐｌｉｃａｔｅ　

ｆｕｎｃｔｉｏｎｓ　ｉｎ　ｒｅｌａｔｅｄ　ｔａｂｌｅｓ　ａｒｅ　ｅｌｉｍｉｎａｔｅｄ　ａｎｄ　ｔｈｅ　ｎｅｘｔ　ｃｈａｒａｃｔｅｒ　ｉｎ　ａ　ｔｅｘｔ　ｗｉｎｄｏｗ　ｉｓ　ｕｓｅｄ　ｔｏ　ｄｅｔｅｒｍｉｎｅ　ｔｈｅ　ｄｉｓｔａｎｃｅ　ｏｆ　ｒｉｇｈｔ　ｓｈｉｆｔ　

ｏｆ　ｔｈｅ　ｔｅｘｔ　ｗｉｎｄｏｗ．Ｔｈｅ　ｐｅｒｆｏｒｍａｎｃｅ　ｔｅｓｔｉｎｇ　ｓｈｏｗｓ　ｔｈａｔ　ｔｈｅ　ｐｒｅｓｅｎｔｅｄ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｍｏｒｅ　ｅｆｆｉｃｉｅｎｔ．　

Ｋｅｙ　ｗｏｒｄｓ：ｐａｔｔｅｒｎ　ｍａｔｃｈｉｎｇ；ＷＭ　ａｌｇｏｒｉｔｈｍ；ＷＭＮ　ａｌｇｏｒｉｔｈｍ　

摘要：入侵检测系统中有部分时间用来进行模式匹配，因此提高模式匹配算法的处理速度具有重要的意义　从两个方面改进了　

目前公认效率较高的多模式匹配算法ＷＭ，设计出ＷＭＮ算法，并对该算法进行了性能测试和分析。实验证明该文提出的ＷＭＮ算　

法能够有效提高模式匹配的处理速度。　

关键词：模式匹配算法；ＷＭ算法：ＷＭＮ算法　

文章编号：１００２—８３３ｌ（２００７）ｌ５—０１２８—０３　文献标识码：Ａ　中图分类号：ＴＰ３ｌ１．５　

Ｉ　简介　

近年来随着高速网络技术的快速发展．入侵检测系统…如　何在高速网络环境下实时有效地正常工作已成为一个研究重　

点。目前大多数基于特征的模式匹配技术的入侵检测系统　艮　

难处理１００　Ｍｐｂｓ网络满负荷时的数据量，而ｌ　０００　Ｍｂｐｓ更是　

难以达到的目标。　

本文以面向高速网络环境下基于特征模式匹配技术的入　

侵检测系统为研究目标，设计了一种高效的多模式匹配算法，　

并用实验证明了改进算法的高效性。　

２　ＷＭＮ算法　

２．１　相关定义　

为描述方便引入下述定义：　定义ｌ　Ｔ（ｔｅｘｔ）为待匹配的主串，标识为ｙ［Ｏ，ｌ，…，ｎ—ｌ】，长　

度为，Ｊ　ｎ。　定义２　Ｐ（ｐａｔｔｅｒｎ）为待匹配的模式串，标识为ｘ［０，ｌ，…，　

ｍ—ｌ１，长度为，Ｊ　ｍ。　

定义３对　进行扫描时需要用的窗口ｗｉｎｄｏｗ大小为ｍ。　

定义４将ｗｉｎｄｏｗ和　一端对齐，比较ｗｉｎｄｏｗ中和Ｐ中　的字符称为尝试（ａｔｔｅｍｐｔ）。　

定义５在　中发现一个和Ｐ完全匹配或不匹配时．窗口　

右移值为ｓ　ｅ。　

定义６对于给定的Ｔ＝ｙ［０，ｌ，…，ｎ—ｌ１和Ｐ＝ｘ［０，ｌ，…，ｍ—　

ｌ１，在　中寻找所有出现的Ｐ的过程称为模式匹配。　

２．２模式匹配算法简介　

根据在匹配过程中同时匹配的模式串个数，模式串匹配算　

法可分为单模式匹配算法和多模式匹配算法。　

最早的单模式串匹配算法是Ｂｒｕｔｅ—Ｆｏｒｃｅ（ＢＦ）算法．该算　

法从主串　的第一个字符开始和模式串Ｐ中的第一个字符比　

较，若相等，则逐个比较后续字符，否则从　的下一个字符开始　

再重新和Ｐ的第一个字符比较；其最坏情况下的时间复杂度为　

Ｏ（ｍ／ｔ），且在　中出现多个与Ｐ部分匹配子串的情况下．　的　

指针需要经常回溯，算法的效率很低。１９７０年，Ｃｏｏｋ　Ｓ．Ａ在理　

论上证明了模式串匹配问题可以在Ｏ（ｍ＋ｎ）时间内解决，随后　

Ｋｎｕｔｈ　Ｄ．Ｅ和Ｐｒａｔｔ　Ｖ．Ｒ仿照Ｃｏｏｋ的证明构造了一个算法．与　

此同时，Ｍｏｒｒｉｓ　Ｊ．Ｈ在研究正文处理时也独立地得到与前述两　人本质上相同的算法，这两个算法称为Ｋｎｕｔｈ—Ｍｏｒｒｉｓ—Ｐｒａｔｔ算　

法（简称ＫＭＰ算法）［３１。ＫＭＰ算法利用已匹配成功部分的信息，　

基金项目：上海市教委自然科学基金（ｔｈｅ　Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ　ｏｆ　Ｓｈａｎｇｈａｉ　Ｍｕｎｉｃｉｐａｌ　Ｅｄｕｃａｔｉｏｎ　Ｃｏｍｍｉｓｓｉｏｎ　ｏｆ　Ｃｈｉｎａ　ｕｎｄｅｒ　Ｇｉａｎｔ　Ｎｏ　

０５ＪＣ０５０５１）；上海市教委Ｅ研究院一上海高校网格项目（“ＳＥＣ　Ｅ—Ｉｎｓｔｉｔｕｔｅ：ＳｈａｒＩｓｈａｉ　Ｈｉｇｈ　Ｉｎｓｔｉｔｕｔｉｏｎｓ　Ｇｒｉｄ”Ｐｒｏｊｅｃｔ　ｕｎｄｅｒ　Ｇｒａｎｔ　Ｎｏ　

２００３１２）。　．　作者简介：袁世忠，男，副教授，研究方向为软件工程，分布式计算，网络入侵；曹曼，女，副教授，研究方向为分布式计算，面向对象技术，网格计算　王燕燕，女，副教授，研究方向为分布式计算，算法设计。

　维普资讯 http://www.cqvip.com 袁世忠，曹　雯，王燕燕：基于ＷＭ算法的多模式匹配改进算法ＷＭＮ　２００７，４３（１５）　１２９　

可以使Ｐ向前推进若干个而不只是一个字符，避免了重复比　

较。同时也实现了　指针的无回溯；ＫＭＰ算法需要进行预处理　

计算一个ｓｈｉｆｔ表．用来确定发生不匹配时需要跳跃的距离；其　

搜索阶段最坏情况下的时间复杂度为Ｏ（ｍｎ）。１９７７年，Ｂｏｙｅｒ　Ｒ．Ｓ和Ｍｏｏｒｅ　Ｊ．Ｓ设计了一个新的串匹配算法Ｂｏｙｅｒ—Ｍｏｏｒｅ算　

法（简称ＢＭ算法）　，它是目前最常用、效率较高的算法之一。　

ＢＭ算法的基本思想是先对Ｐ进行预处理．计算两个偏移函　

数：Ｂａｄｃｈａｒ（ｃｈａｒ　ｃｈ）和ＧｏｏｄＳｕｆｆｉｘ（Ｓｔｒｉｎｇ　ｓｔｒ），然后将　和Ｐ　

对齐．从右往左进行匹配，当　字符与Ｐ字符不匹配时，根据　

函数Ｂａｄｃｈａｒ（ｃｈａｒ　ｃｈ）和ＧｏｏｄＳｕｆｆｉｘ（Ｓｔｒｉｎｇ　ｓｔｒ）计算出偏移　

值，取两者中的较大者作为　指针的右移量。在ＢＭ算法的基　

础上。又派生出许多算法，例如Ｂｏｙｅｒ—Ｍｏｏｒｅ—Ｈｏｒｓｐｏｏｌ算法１５１，　

该算法仅采用Ｂａｄｃｈａｒ（ｃｈａｒ　ｃｈ）来确定右移值。１９８０年，Ｋａｒｐ　

和Ｒａｂｉｎ合作从截然不同于ＫＭＰ算法和ＢＭ算法的途径研究　

出一种基于数值计算的新算法．称为Ｋａｒｐ—Ｒａｂｉｎ算法［６１（简称　

ＫＲ算法）。１９９０年，Ｓｕｎｄａｙ　Ｄ．Ｍ提出了Ｑｕｉｃｋ　Ｓｅａｒｃｈ算法ｆ７】　

（简称ＱＳ算法），该算法实质上是ＢＭ算法的简化，在实际应　

用中是一种简洁高效的算法。　

多模式串匹配算法中一个经典算法是由Ａｈｏ　Ａ．Ｖ和　

Ｃｏｒａｓｉｃｋ　Ｍ．Ｊ提出的ＤＦＳＡ（Ｄｅｔｅｒｍｉｎｉｓｔｉｃ　Ｆｉｎｉｔｅ　Ｓｔａｔｅ　Ａｕｔｏｍａ—　

ｔａ）算法［８１。简称为ＡＣ算法，该算法通过构造有限自动机来进行　

匹配。构造有限自动机的过程就是将多模式匹配问题转化为单　

模式匹配问题．因此，完全可以在有限自动机构造完毕之后应　

用现有的快速单模式匹配算法来加快匹配速度。Ｓｕｎ　Ｗｕ和　

Ｕｄｉ　Ｍａｎｂｅｒ近年在ＢＭ算法的框架下派生出又一经典的多模　

式匹配算法，称为ＷＭ算法［９１。为进一步提高多关键字匹配的　

效率．多种改进算法被提出。Ｎ．Ｔｕｃｋｔ　０１改变ＡＣ算法中的数据结　

构．提出一种压缩指针的方法来消除ＡＣ算法中内存消耗严重　

的问题。王永成…】基于ＡＣ等算法，结合单模式匹配的ＱＳ算法　

思想．提高了算法效率。张鑫ｌＩ　于ＷＭ算法，通过引入“精确的　

不良字符转移”和“弱化良好后缀转移”来提高算法性能。　

本文在分析ＷＭ算法设计不够完善的基础上，结合ＱＳ算　

法思想。利用字符间的位置信息，设计了一种更加高效的多关　

键字匹配算法——ＷＭＮ（ＷＭ　ｕｓｉｎｇ　Ｎｅｘｔ　ｃｈａｒａｃｔｅｒ）算法。　

２＿３　ＷＭＮ算法　

２－３．１　ＷＭＮ算法思想　ＷＭ算法采用字符块技术，增大了主串和模式串不匹配的　

可能性．从而增加了直接跳跃的机会：它使用前缀表进一步过　

滤不匹配的模式串，使算法获得了较高的运行效率。因此．在现　

有的多关键字匹配算法中，使用块字符、Ｈａｓｈ技术和前缀特征　

表技术的ＷＭ算法通常被认为具有最高的效率。但对ＷＭ算　

法进行仔细分析之后，发现其还有设计不完善、需要改进的地　

方，包括：　

（１）ＨＡＳＨ表和ＳＨＩＦＴ表的功能有重合部分。ＳＨＩＦＴ表取　值为０时对应的ＨＡＳＨ表项非空．而ＨＡＳＨ表中值为０的项　

对应的ＳＨＩＦＴ表项值大于０。ＨＡＳＨ表和ＳＨＩＦＴＩ’表都可以用　

来判断某个模式串是否需要进一步匹配，这使得空间利用率　

不高。　

（２）由于采用ＳＨＩｆＴｒ表值是否为Ｏ作为该模式串是否需　

要进一步匹配的判断条件。因此，当这个表项值为０时，无论匹　

配成功与否，匹配窗口的跳跃距离只能为１。这种情况较多时，　该策略会在较大程度上影响算法的效率。此时．应该在所有模　式串的前ｍｉｎｌｅｎ一１（ｍｉｎｌｅｎ为所有模式串的最短长度）个连续　

字符中寻找与该字符块相同的子串，实际安全的跳跃距离为１　

到ｍｉｎｌｅｎ—Ｂ＋Ｉ（Ｂ为字符块的长度）。　

（３）正文当前窗口的最右边一个字符块不出现在任何模式　

串中时．跳跃距离等于ｍｍｌｅｎ—Ｂ＋Ｉ是安全的，但也是保守的，　

使得算法不够高效．在模式串长度较短时对效率的影响更加明　

显。当这个字符块不出现在任何模式串中．并且所有模式串的　

前缀和该字符块的后缀没有重叠部分时，最大的安全跳跃距离　

可达到ｍｉｎｌｅｎ　针对以上不足之处．从两方面对ＷＭ算法进行改进：（１）　

使用ＨＡＳＨ表作为进一步匹配的人口，而ＳＨＩｆＴｒ表仅用来提　

供跳跃值。（２）利用当前窗口的下一个字符来辅助计算跳跃距　

离。由于每次尝试以后的跳跃距离至少为１，故下一次尝试中　

一定包含当前窗口的下一个字符。因此在计算跳跃距离时可以　

利用该字符带来的信息。将该字符与当前窗口的最后Ｂ一１个　

字符一起作为长度为曰的字符块考虑．同原来的字符块一起　

来计算跳跃距离，以获得最大跳跃值。　

ＷＭＮ算法基于上述思想，继承了ＷＭ算法的字符块技　

术、散列技术以及前缀表的思想，考虑当前窗口的下一字符，利　

用两个字符块来计算跳跃距离．以在每次尝试之后获得尽量大