多模式匹配算法研究和优化

曹为政 葛蒙蒙

摘 要： 模式匹配在网络安全领域有着重要的应用，随着网络环境的日益复杂，模式集合也随之增加。如何高效处理千万模式集下的字符串匹配成为网络安全的瓶颈之一。本文针对多模式匹配算法AC算法和WM算法进行了研究，采用了新型基于层次扫描和子节点数目搜索的双数组AC算法；从hash函数的选取和模式串的Tree树存储对WM算法进行了优化。能有效减少系统的内存占用，提高匹配效率。

关键词： AC算法；WM算法；多模式匹配；信息安全；哈希函数

Abstract：Pattern matching has important applications in the field of network security. With the increasingly complex network environment the collection of patterns has also increased. How to efficiently handle string matching in the tens of millions of patterns becomes a bottleneck in network security. In this paper AC algorithm and WM algorithm which are the multi-pattern matching algorithm are studied and a double-array AC algorithm based on hierarchical scan and subnode number search are proposed. The WM algorithm is optimized from the hash function selection and Tree tree storage of the pattern string. The research could effectively reduce the system's memory footprint and improve the matching efficiency.

Key words： AC algorithm；WM algorithm；multipattern matching； information security；hash function

引言

隨着互联网的飞速发展，网络安全已经吸引了业界的高度关注。 “现今网络环境下，所有网络数据流量总和仅仅是当前近十个月的网络数据量[1]”。当今时代每天的信息数据量更是呈现爆炸式的增长，能够快速高效地对网络数据流量进行处理是当前信息安全的重点研究方向。以字符串为代表的模式匹配是处理此类问题的核心，字符串匹配算法研究也随即成为网络安全领域的热点项目内容。

字符串匹配是指从众多模式集合中找到符合特定规则的字符串或者模式集[2]。在现今庞大的网络数据流量和不断增多的模式集合情况下，对字符串匹配算法的匹配时间、内存占用空间都提出了更高的要求。针对骨干路由节点，设计需要的模式集合更是高达几十万、甚至百万，为了满足实时处理的需求，算法就要在千万集合下也能稳定高效地展开运行、并输出结果。基于此，本文拟对传统的多模式匹配算法AC[3]算法和WM[4]算法进行研究，同时结合不同的模式特征，对算法提出了一定的优化与改进，从而使得算法在时间、空间和稳定性上均获提高。

1 字符串匹配算法原理

1.1 多模式字符串匹配概念

1.2.1 算法原理

1.2.1.1 算法原理分析

AC算法由3个部分构成，分别是：goto表、fail表和output表。其中，goto表是模式集合P中所有模式构成的自动转移状态机。fail表是记录跳转到的状态不接受输入的字符时，下一个要跳转的状态。output表记录当跳转到一个可输出状态时，需要输出的模式集合。下面，关于各表的功能阐析可详述如下。

（1）goto表。goto表是模式集合P中所有模式构造的状态转移自动机。构造时，由goto函数依次读入模式集合中的每一个模式，并把这个模式添加到AC算法的Tree状结构中。如果Tree中不包含该模式的分支，则创建该分支。最后把该模式的最后一个字符状态标记为终止状态。

（2）fail表。fail表记录当状态机处在某个状态D，此时输入的字符s没有状态接受时，下一个应该跳转的状态。实际构造思路是，对于状态D，已经匹配的模式前缀为pi，对于pi的所有后缀，计算其能跳转到的最终状态，深度最大的那个状态就是fail表中D所对应的状态。

（3）output表。output表记录当到达终止状态时，所有包含的模式集合。每一个状态都会有一个output表，在初始化goto表时，每一个添加成功的字符串的最后一个字符状态都会添加一个output。在构造fail表的过程中，当某一状态的失效状态是终止状态时，该状态也会添加其失效状态为output。

1.2.1.2 算法原理示例

以模式集合P={he，s he，hi s，he r s}构建自动机，研究推得，AC算法goto表构建流程步骤可见如下。

步骤一 如图1所示，将模式he加入goto表。

步骤二 如图2所示，将模式s he加入goto表。

步骤三 如图3所示，将模式hi s加入goto表。

步骤四 如图4所示，将模式he r s加入goto表。

1.2.1.3 扫描过程

输入文本p，依次读入文本的字符，按照状态机进行状态跳转，当状态失效时，则遵照fail表发生跳转，以此类推直至扫描到最后一个字符的状态，再根据output表将匹配到的模式来发送输出。本次研究示例中的fail表和output表内容可分见表1、表2。

1.2.3 算法总结

综上分析可知，AC算法具有匹配速度快，扫描速度稳定，对模式集合没有要求，算法性能和模式集合无关的特点。缺点是算法的空间复杂度呈指数级增长，在大规模模式集的情况下，过大的内存开销会成为算法运行的瓶颈。

1.3 基于后缀的WM匹配算法

WM（Wu-Manber）算法，是基于后缀扫描的跳跃算法，利用了BM坏字符的思想。算法将建立一个扫描窗口，窗口的大小为模式集合中最短字符串的长度，在扫描窗口内进行最大距离的跳转。WM算法关键的数据结构为3个表，分别是：后缀Hash表、Shift表、Prefix表。

1.3.1 算法原理

算法预处理阶段，需要根据模式集合建立后缀Hash表、Shift表、Prefix表三个数据结构，详情即如图2所示。

由图5可知，各表的功能阐析可如下论述：

（1）后缀Hash表。所有模式集合以最短长度对齐后，Hash表存储着所有B长度字符块的Hash值大小。

（2）Shift表。记录当字符块不匹配时，跳转的距离是多少。研究仅对所有模式集合的前m个字符构建Shift表，m为所有模式的最短长度。在B的选取中，通常选择2或者3。在构建Shift表的过程中，如果字符块s未出现在模式集的任何一部分子串中，则Shift〖JB（[〗s〖JB）]〗=m-B+1；如果字符块s出现在模式集的子串中，则选择s在模式集合中最靠右的位置。

（3）Prefix表。即前缀表，因为在大模式集合下，后缀Hash计算时容易产生冲突，为了加快扫描速度，利用Prefix表记录模式串的前几个字符的哈希值，能有效避免相同后缀Hash值的集合过大，提高扫描效率。

至此，研究给出算法扫描过程为：计算模式集合最短长度m，设定扫描窗口。计算后缀字符B的Hash值h。在Hash表中查找h。如果未查找到，则跳跃m-B+1个字符，若找到，则查阅表Shift。如果跳转距离为正数，则直接跳转相应的距离；如果跳转距离为0，则计算前缀的Hash值，找到Prefix中相应的项，再进行完全扫描，判断模式是否命中。

1.3.2 算法分析

WM算法通过计算Hash值，对于不能匹配的坏字符块进行跳跃匹配，提高了扫描效率。在WM算法中，一般假设字符表中每个字符出现的概率是相同的，计算一个B块Hash值的时间复杂度为O（B）。当存在一个匹配时，檢查整个模式的时间复杂度为O（m），整个扫描过程的时间复杂度为O（BN/m）。

1.3.3 算法总结

综合前述分析发现，WM算法的内存占用很小，且内存开销稳定。WM算法在匹配情况较为少见的时候，扫描速度非常快，但是当模式集合中有大量的短模式集时，就会大大降低跳转效率，因此WM算法不适合较短的模式集合。

2 改进算法研究

2.1 AC算法的DAT实现和优化

双数组树算法（Double Array Tree，DAT）是一种有穷自动机，基于trie的搜索算法，其复杂度和文本的长度有关，最佳时间复杂度为O（1），最坏为O（n），其中n为文本的长度。利用双数组来实现AC算法，能有效减少稀疏矩阵引起的空间浪费，也可以复用未标记的空间来存储新的状态。

DAT由2个数组组成，分别是：base数组和check数组。2个数组大小和元素位置一一对应。base数组中的下标对应自动机中的状态值，数组数据关联了状态转移的状态值；check数组记录了当前状态的父节点。i为base数组和check数组的下标，base[i]=check[i]=0时，表示这个节点还未使用；base[i]为负数时，表示此节点为终止状态。

2.1.1 DAT算法构造过程

（1）初始化root节点，其下标为0，则base[0] = 1 check[0] = 0。

（2）对于子节点s，当节点s存在子节点时，寻找到一个k值使得check[k+ci]=0，0

（3）在check数组中，使check[t]=s。

（4）遍历所有节点，直到所有节点均加入到数组中。

在构造了双数组后，接着要构造fail函数和output函数。构造fail函数和KMP算法中的回溯思想类似，在求取当前状态的fail值时，其前一个状态（父节点）的fail值必须先行求得。首先，令tree树中的第一层节点的fail值都为0，并依次送入队列，这相当于初始化。然后，依次取出每一个节点m，计算m的所有子节点n的fail值，如果节点n还有子节点，则将节点n存入队列，直到队列为空。

2.1.2 DAT算法扫描过程

在双数组、fail函数、output函数构建过后，就可以对文本序列进行扫描。对于当前状态s，读入字符c，如果check[base[s]+c]=s，则状态s接收字符c，跳转到下一个状态t=base[s]+c；否则说明状态s不接收字符c，需要跳转到状态s的失效状态，直到字符c被接收或者跳转到根状态。

通过双数组的方式实现了AC算法，在保证高效扫描的同时，也极大地压缩地状态内存，其最大时间复杂度仍为O（n），这里的n为文本序列的长度。

2.1.3 DAT算法优化

DAT算法能有效减少传统AC算法tree树实现过程中稀疏矩阵带来的内存开销，用base数组来记录其跳转状态，check数组记录其父节点的状态。但是在生成双数组的过程中，仍会产生部分空间浪费，在构造时就会涉及到数组数据的局部调整，从而占用过多的时间。本次研究主要从初始化时间和内存占用方面展开设计优化。

通常的双数组构造都是采用基于深度优先或者广度优先的搜索方法，这种方法容易导致数组数据冲突，会生出更大的内存占用和数组调整的时间开销。为此，本文将采用基于层次遍历的方法构造双数组，并优先将子节点个数多的节点加入到数组中，如图6所示，从而减少在构造base数组中产生的冲突。优化后的DAT算法构造步骤可表述如下。

（1）将所有模式集合按照字典序列从小到大循序排列。

（2）初始化节点列表，把第一层所有节点加入到列表。

（3）选择子节点最多的节点，计算其base表值、子节点的check表值，然后将其所有子节点加入到列表中。

（4）重复（3）直到列表为空。

（5）构建fail表和output表。

2.2 WM算法优化

WM算法是基于后缀扫描的跳跃算法，主要包括利用hash函数对字符串扫描和对冲突字符串的完全扫描。这里主要将针对这2部分内容提供设计优化。研究可得过程内容如下。

2.2.1 hash函数选取

针对不同规模的数据，不同的hash函数产生冲突的大小也不一致[8]。在这里，研究选取了5种常用的hash函数DJBHash[9]、APHash[9]、JSHash[9]、RSHash[9]和PJWHash[10]，并对其进行了数据冲突对比。

测试过程为：3次随机产生1 000万的模式集合，记录每种hash方法产生的冲突个数测试结果如图7所示。通过对比发现APHash算法冲突最小。同时，关于APHash算法，进一步研发得到如下执行代码：

输入：待计算字符串

输出：哈希值

方法：通过移位异或操作计算

unsigned int APHash（char*str）{

unsigned int hash=0 ；

int i ；

for（i=0；*str；i++）{

if（（i&1）==0）{

hash^=（（hash<<7）^（*str++）^（hash>>3））；

}else{

hash^=（～（（hash<<11）^（*str++）^（hash>>5）））；

}

}

return（hash % M）；

}

2.2.2 采用tree存储冲突模式串

在完全扫描冲突模式的过程中，以往就是采用链表的形式来存储冲突的模式集合，在千万模式集合下，冲突的模式串会比较多，此时的扫描时间复杂度为O（M*l），其中M为冲突模式个数，l为模式的长度。显而易见，时间花费较为可观。

本次研究采用了tree树来存储冲突的模式字符串，采用树来存储后，只需扫描一遍就能确定命中的字符串，其时间复杂度为O（l），其中l为冲突模式串长度。

3 实验结果分析

3.1 实验环境

系统环境为：centos 7；硬件平台为：X86_64；系统内存为：16 G。

3.2 实验分析

测试时，将AC算法和优化后的DAT算法同时处理2万～12万的模式集合，从而比较2种算法的匹配速度。测试结果如表3所示。由表3可以看到优化后的DAC算法效率大约是AC算法的2～3倍，提升效果相当明显。

同时，也测试了优化后WM算法的性能情况。测试数据集从50万增长到500万。测试结果见表4。由表4可以看到初始化时间基本小于10 s，即使数据规模达到500万时，其预处理时间也不超过15 s。在匹配扫描时，扫描时间更是大大提高，整体时间均小于15 us。研究可知即使针对千万模式集合匹配，优化后的WM算法也具有良好效果。

4 结束语

本文对多模式匹配算法AC算法和WM算法进行了研究，分析了其原理和优缺点。并针对算法特点提出了基于层次遍历和子节点数目搜索的双数组算法，对AC算法进行了优化；针对WM算法的哈希和模式存储方面也实现了相关优化。从而使得多模式匹配算法在空间利用和匹配效率方面均已获得了改良与提高。

参考文献

[1] GRAY J. What next？A few remaining problems in information technology[Z]. Atlanta：ACM FCRC，1998.

[2] 张丽霞，陈莉 . 一种改进的模式匹配算法[J]. 微计算机信息 2008，24（30） ：68-70.

[3] AHO A V CORASICK M J. Efficient string matching： An aid to bibliographic search[J]. Communications of the ACM 1975，18（6）：333-340.

[4] WU S MANBER U. A fast algorithm for multipattern searching[R]. Tucson AZ：University of Arizona 1994.

[5] YAO A C. The complexity of pattern matching for a random string[J]. SIAM Journal of Computing 1979 8（3）： 368-387.

[6] NAVARRO G FREDRIKSSON K. Average complexity of exact and approximate multiple string matching[J]. Theoretical Computer Science 2004 321（2-3）：283-290.

[7] 劉燕兵. 串匹配算法优化技术的研究[D]. 北京：中国科学院（计算技术研究所） 2006.

[8] 张鑫，谭建龙，程学旗. 一种改进的WuManber多关键词匹配算法[J]. 计算机应用 2003 23（7）： 29-31.

[9] DUAN Fei ZHENG Yan. Analysis of duplicated Web pages identification methods in search engine[C]//2010 2nd international Workshop on Database Technology and Applications. Wuhan China： IEEE，2010：1-5.

[10]LITTLE M C SHRIVASTAVA S K，SPERIS N A. Using bloom filters to speedup name lookup in distributed systems[J]. The Computer Journal 2002 45（6）： 645-652.