一种基于分类存储的空间高效Aho-Corasick算法

汪泓才 李训根

(杭州电子科技大学电子信息学院 浙江 杭州 310018)

一种基于分类存储的空间高效Aho-Corasick算法

汪泓才 李训根

(杭州电子科技大学电子信息学院 浙江 杭州 310018)

针对经典Aho-Corasick算法存在空间开销大，存储效率低的问题，提出一种改进的空间高效Aho-Corasick算法。新算法在预处理阶段根据状态转移函数、输出函数的不同特性，灵活选择不同的方式存储状态结点，实现对Aho-Corasick算法状态机的压缩。实验表明，新算法与经典Aho-Corasick算法、Bitmapped AC算法相比，以匹配阶段较小的时间性能为代价，极大幅度地压缩状态机的存储空间。

AC算法 模式匹配 空间高效

0 引 言

Aho-Corasick(简称AC)算法是一种经典的多模式匹配算法，有着良好的时间复杂度，在许多领域得到了广泛应用。AC算法的一个典型应用就是误用入侵检测。误用入侵检测，指的是通过监视网络或计算机内部的流量数据，根据预先设定好的规则库，用模式匹配算法深度检测流量数据，判断数据是否为恶意数据。入侵检测系统的规则库通常比较庞大。Snort是一个被广泛使用的入侵检测系统，它的规则库就多达3 000余条。使用AC算法去匹配如此大量的规则库，需要大量的空间开销，更难以用硬件直接实现。基于这种状况，本文提出了一种分类存储的AC算法，旨在降低算法的空间开销。

1 AC算法介绍

AC算法分为预处理与匹配两个阶段，它在预处理阶段构建一个有限状态自动机，然后在匹配阶段用状态间的转移操作取代字符比较操作，减少不必要的字符比较操作[1]。

预处理的对象是模式串集合，目的是构造有穷状态自动机。在构造的状态机中，每个状态结点都有三个功能函数，分别是转移函数goto、输出函数output与失效函数failure[2]。如有模式串集合P={every, job, enjoy}，可以构建图1所示的状态机。

图1 {every, job, enjoy}构建的状态机

在图1中，实线箭头代表的转移函数。转移函数goto(src, c)= tar表示在状态src输入字符c，就转移到状态tar。在这里，状态tar被称为状态src的转移状态。例如，当前状态是图1中的“state8”，输入字符“o”，则当前状态更新为“state9”。

图1中的虚线箭头代表的是失效函数。失效函数处理匹配过程中使用转移函数失败的情况。若状态tar与状态src满足failure(src)= tar，即状态tar是状态src的供给状态，则表示如果在状态src输入某个字符后无对应的转移函数，就更新状态为tar。例如，当前状态是图1中的“state8”，输入字符“a”，无法使用转移函数更新状态，就必须使用失效函数更新状态为“state11”。还需说明的是，在状态机的构建中，状态的默认供给状态为初始状态。为了简洁起见，图1没有绘制这种默认的供给关系。

输出函数output(s)={pattern}则意味着在状态s匹配到了模式串pattern。

AC算法匹配阶段的实现高效而简洁，具体逻辑为：从状态机的初始状态出发，依次读入被搜索文本的字符，根据读入的字符，选择使用转移函数或失效函数更新状态，如果使用了转移函数更新为新的状态，还需要检查新的状态是否有输出，若有，则输出的模式串就是被匹配的。

AC算法时间复杂度较低，即使同时匹配大量的模式串，搜索阶段的时间开销也比较稳定。另一方面，AC算法的空间开销与模式串的总长度呈非线性正比的关系，这就使得在一些模式串总长度较长的场景，状态机的空间占用过大[3]。

2 AC算法的存储效率及其改进

在AC算法的状态机中，每个状态节点都需要存储转移函数、失效函数与输出函数的信息。转移函数的信息可以用表格保存，这张表格称为转移表。表1是图1中“state1”的转移表。在这张转移表中，字符“n”与“v”的ASCII值为110与118，对应在转移表中编号为110与118的项存储goto(state1, “n”)与goto(state1, “v”)的值。对于“state1”，输入除“n”与“v”以外的其他字符，都不存在相应的转移函数，对应转移表中其余项的值为一个特殊的无效值，用以表示使用转移函数失败。在表1中，这个无效值为“0”。

表1 “state1”的转移表

转移表通常用指针数组实现。在32位机中，存储一张规模为256的转移表需要使用1 024个字节。而在实际应用中，这张转移表通常只有少数的几个有效值。过多的无效值占据了大量的空间，造成了AC算法状态机存储效率低下。为了解决这一问题，已有大量的工作尝试通过压缩转移函数信息以提高AC算法的存储效率。

2.1 基于稀疏向量压缩的改进

基于稀疏向量压缩的思想，Norton提出了Banded-Row AC算法[4]。Banded-Row AC算法在AC算法的基础上，压缩了转移表中首尾的无效值。Banded-Row格式的转移表可以使用向量表示，“state1”对应的Banded-Row格式向量为{9, 110, state7, 0, 0, 0, 0, 0, 0, 0, state2}。这个向量分为三部分解读。从第三个元素开始的内容，即“state7, 0, 0, 0, 0, 0, 0, 0, state2”，被称为一个的“有效元素带”。向量的第一个元素“9”表示这个“带”的长度为9。向量第二个元素“110”表示这个“带”首个元素在转移表的第110项。按这种规则构造的Banded-Row格式向量用于替代转移表，能够显著降低存储需求。

Banded-Row AC算法能够压缩表中首尾的无效值，但是，每个Banded-row格式的向量只有一个“带”，无法压缩“带”中间的无效值。Sparse-Bands AC算法解决了这一问题。Sparse-Bands格式的向量与Banded-Row格式的向量相似，但前者在构造时还加入一个策略：当“带”中间连续的无效值个数超过指定的阈值，这个“带”将被分成前后两个“带”。这就压缩了转移表中间的无效值。

徐红等提出的双重压缩AC算法，在Sparse-Bands AC的基础上做了进一步的改进[5]。双重压缩AC算法将状态机所有N个状态的转移表视为一张N×256的矩阵。将矩阵中的全为0的列删除，记入其对应的字符为未用字符，然后再对各行进行Sparse-Bands格式压缩。在匹配时，每次使用转移函数，需判断输入字符是否为未用字符，若是，则使用转移函数失败。

基于稀疏向量压缩改进的算法相对于AC算法，存储效率都有着明显的提高，但在匹配阶段，每次用到转移函数，都需要额外的计算[6]。

2.2 位图AC算法

同样基于降低存储开销这一目的，Tuck等提出了位图AC(BitmappedAC)算法[7]。图2给出了位图AC中状态的存储结构。位图AC的状态节点引入了位图用以判断输入字符是否存在有效的转移函数值，引入了结构数组用以存储有效的转移字符及对应的状态结点地址。在位图中，每一个位的值由转移表中每一项的值一一映射得到。若转移表中第k项为一个有效值，则位图的第k位为“1”；否则，位图的第k位为“0”。在匹配阶段使用转移函数，先检查输入字符对应位的位图值是否为“1”。若是“1”，则从结构数组中读取下一个状态；若是“0”，则接下来调用失效函数。

图2 位图AC状态机中状态的存储结构

位图的引入降低了算法的存储需求，提高了cache性能[8]，同时保持了转移表随机访问的特性，在空间性能与时间性能之间取得了平衡。

3 基于分类存储的AC算法

无论是AC算法，还是众多基于AC提高存储效率的改进算法，都使用了单一的方式存储状态结点。本文介绍一种分类存储状态结点的AC算法。该算法根据状态机不同特性，灵活选择不同的方式存储状态结点。尤为可贵的是，新算法不但能基于经典的AC算法改进，还能应用于Banded-RowAC、位图AC等多种改进算法上，实现在这些算法的基础上进一步提高空间存储效率。

3.1 存储方式

在AC状态机中，大量的状态节点没有转移状态或者只有一个转移状态。对于这类状态结点，如果直接存储有效的转移字符及对应转移状态的地址，能够进一步降低状态机的空间需求。

基于这种朴素的想法，新算法根据状态的转移函数有效值个数是否大于1这一条件，将状态分为两类。第一类状态是转移函数的有效值至少有2个的状态，这一类状态依旧采取原有的转移表或位图等方式存储转移函数的信息。第二类状态是转移函数有效值最多只有一个状态，采用直接存储有效的转移字符nextChar与对应转移状态nextNode的方式记录转移函数信息。同时，将nextChar为“0”作为转移函数有效值个数为0的标志。图3展示了使用分类存储后AC算法状态存储结构的变化。为了能够在匹配阶段识别状态结点的存储方式，还引入占用一个字节大小的标识符flag。

图3 使用分类存储后AC算法状态存储结构的变化

使用图3展示的存储结构，每次使用转移函数或失效函数更新为新的状态，都必须读取标识符检查状态的存储类型，存在额外的时间开销。为了降低这一部分时间开销，新算法还采用了两个措施。

措施一是将原先的两种存储方式根据输出函数值是否是空值，进一步细分为四种，若输出函数值是空值，则不再存储这一个空值。图4展示了这四种存储结构。措施一的引入保证了在匹配阶段更新为第三类或第四类状态时，可以直接通过读取标识符判断输出函数为空值，减少使用输出函数的次数。

图4 采用措施一后状态存储结构的变化

措施二是供给状态只能为第一类或第三类状态。只有满足转移函数有效值个数不超过一个且不是供给状态的状态，才能归为第二类或第四类状态。这就保证了在匹配阶段，使用失效函数更新为新状态时，新状态只可能为第一类或第三类状态，无需重新读取标志符识别当前状态转移函数的存储方式。表2展示了采用措施二后四类状态的使用条件。

表2 四类状态的使用条件

上述两个措施降低了使用分类存储在匹配阶段额外的时间开销。相比于原算法，新算法在每次使用转移函数到新状态后，多了检查存储类型这一操作，但对于大多数无输出的状态，不再需要调用输出函数。

分类存储同样可以应用于Banded-RowAC、Sparse-BandsAC、位图AC等多种改进的AC算法上。要将新算法应用于这些改进的AC算法，只需要调整新算法中第一类与第三类状态的转移函数存储方式。如将分类存储应用于位图AC算法上，就将第一类与第三类状态中的转移表替换为相应的位图和结构数组，其余的存储结构均保持不变。

3.2 预处理与匹配

新算法的状态机可以在原有算法状态机的基础上构建。遍历原有算法状态机所有的状态结点，根据表2所示的使用条件，重新建立相应类型的状态结点，即可得到新算法的状态机。

在匹配阶段，从状态机的初始状态出发，依次读入被搜索文本的字符。每次使用转移函数更新状态后，先检查标识符，决定是否需要调用输出函数以及如何调用转移函数。转移函数的使用有两种方式，一是使用相应原算法的转移方式，如转移表，Banded-Row向量，位图等；二是直接读取nextChar，并尝试转移到nextNode。每次使用失效函数更新状态后，不需要检查标识符，直接尝试使用转移函数，若成功则转移到下一状态，若失败则再次使用失效函数更新到下一状态。

4 实验与分析

为了证明基于分类存储的AC算法在空间开销方面的优势，在同一台计算机上进行实验。实验的对象共有四个，分别是经典AC算法、基于分类存储的AC算法、位图AC算法、基于分类存储的位图AC算法。将实验对象分为2组进行对比，第一组是经典AC算法与基于分类存储的AC算法，第二组是位图AC算法与基于分类存储的位图AC算法。实验从状态机的存储开销与匹配阶段时间开销两方面评估算法的性能。实验的所有算法均用C++实现，在windows10运行，配置为Intel(R)Core(TM)i7 4700HQ2.4GHzCPU，8GB内存。

实验的第一部分是测试状态机的存储空间大小。使用四种算法预处理Snort2.9规则集中的3348条模式串，分别建立状态机。图5展示了四种算法建立的状态机的存储空间。状态机的存储空间为构造完状态机后使用内存与未构造状态机前使用内存之差。实验结果显示，在经典AC算法与位图AC算法上使用分类存储，状态机的空间仅为原来的14.9%与36.7%。

图5 状态机存储开销的对比

实验的第二部分是测试四种算法的匹配速度。被匹配的文本是来源于互联网的10MB英文文本。直接使用实验一中的4个状态机对文本各进行5次匹配，取平均值为最终的测试数据。四种状态机匹配用时如图6所示。使用分类存储后的AC算法与位图AC算法，匹配阶段用时平均增加8.3%和7.9%。

图6 匹配阶段时间开销的对比

实验结果表明，基于分类存储的AC算法相对于经典AC算法，以匹配阶段用时增加8.3%的代价，将状态机的空间开销减少为原来的14.9%。即使是在空间高效的位图AC算法上使用分类存储，依旧能以匹配阶段用时增加7.9%的代价，将状态机的空间开销减少为原来的36.7%。

5 结 语

基于分类存储的AC算法，与前人的位图AC，Banded-RowAC等算法的目的相同，都旨在于提高状态机的存储效率。但相比这些算法，基于分类存储的AC算法的优势在于它的第一类状态与第三类状态能灵活选用转移表，位图或Banded-Row向量等方式存储转移函数的信息，实现在这些算法的基础上进一步降低存储开销。但是，在当前实现的算法中，分类存储的方式还比较简单，选用存储方式的条件也是固定的，还可以进一步引入其他的存储方式，并系统性地调整选取不同存储方式的条件，评估不同方式下的时间性能与空间性能。这将是下一步工作的方向。

[1] Aho A V,Corasick M J.Efficient string matching:an aid to bibliographic search[J].Communications of the ACM,1975,18(6):333-340.

[2] Navarro G,Raffinot M.Flexible pattern matching in strings:practical on-line search algorithms for texts and biological sequences[M].New York,NY,USA:Cambridge University Press,2002:221.

[3] 王培凤,李莉.基于Aho-Corasick算法的多模式匹配算法研究[J].计算机应用研究,2011,28(4):1251-1253,1259.

[4] Norton M.Optimizing pattern matching for intrusion detection[R].Columbia,MD,USA:Sourcefire Inc,2004.

[5] 徐红,秦志光.一种面向入侵检测的改进AC算法[J].微电子学与计算机,2010,27(11):109-112.

[6] 董世博,李训根,殷珍珍.一种改进的字符串多模式匹配算法[J].计算机工程与应用,2013,49(8):133-137.

[7] Tuck N,Sherwood T,Calder B,et al.Deterministic memory-efficient string matching algorithms for intrusion detection[C]//Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies.IEEE,2004:2628-2639.

[8] Wen Y,Chen Z,Ma G,et al.SECOMPAX:a bitmap index compression algorithm[C]//Computer Communication and Networks (ICCCN),2014 23rd International Conference on.IEEE,2014:1-7.

A SPACE-EFFICIENT AHO-CORASICK ALGORITHM BASED ON CLASSIFICATION STORAGE

Wang Hongcai Li Xungen

(SchoolofElectronicsandInformation,HangzhouDianziUniversity,Hangzhou310018,Zhejiang,China)

Aiming at the problem that the classical Aho-Corasick algorithm has large space overhead and low storage efficiency, an improved space-efficient Aho-Corasick algorithm is proposed. In the preprocessing stage, the new algorithm chooses different storage state nodes flexibly according to the different characteristics of the state transfer function and the output function, and achieves the compression of the Aho-Corasick algorithm state machine. Experiments show that compared with the classical Aho-Corasick algorithm and Bitmapped AC algorithm, the new algorithm can greatly reduce the storage space of the state machine at the cost of matching small time performance.

Aho-Corasick algorithm Pattern matching Space-efficient

2016-04-05。汪泓才，硕士生，主研领域：模式匹配。李训根，副教授。

TP301

A

10.3969/j.issn.1000-386x.2017.05.048