一种新的应用于数据流关联分析的多模式匹配算法

王瑞莹，邱 亮

(1.哈尔滨友盛科技有限公司，黑龙江哈尔滨150090;2.联通系统集成有限公司 黑龙江省分公司，黑龙江 哈尔滨150090;3.东北电力大学信息工程学院，吉林吉林132012)

随着电力企业信息化工作的不断深入，国家电网公司“SGl86”工程的实施，电力企业的信息化程度得到了空前的提升，为了确保电网业务数据的安全以及信息系统安全稳定的运行，电力企业先后在网络边界和信息内网部署了防病毒系统、防火墙、入侵检测系统、漏洞扫描系统等安全设备。但是这些安全系统都只能阻止单一的安全威胁，彼此之间缺乏有效而统一的管理调度机制，导致各个安全设备的效能难以得到充分地发挥［1］。此外，这些设备产生的海量日志事件中，可能隐含了新的更严重的安全事件，因此必须采用有效的分析手段对这些海量日志信息进行处理，以减少误报、避免重复报警、发现新的安全事件。基于数据流技术的安全事件关联分析引擎则可以达到这个目的。

本文主要对基于数据流技术的安全事件关联分析引擎中的模式匹配算法进行研究。

1 基于数据流技术的关联分析引擎

基于数据流技术的关联分析引擎将经过归一化处理后的海量日志信息形成的数据流在内存中采用基于滑动窗口模型的关联分析算法进行关联规则挖掘，然后利用多模式匹配算法将得到的关联规则与规则库中规则进行匹配，以便实时地发现异常行为，为后续告警响应及安全风险分析等提供依据。

为满足数据流关联分析实时、高速的要求，关联分析引擎不仅要有高效的数据流关联分析算法，还要有高效、快速的模式匹配算法。Aho-Corasick算法(AC算法)和Wu-Manber(WM算法)算法是两种经典的高效多模式匹配算法。

图1 基于数据流技术的关联分析引擎结构

2 多模式匹配算法

2.1 AC 算法

AC算法是基于有限自动机的多模式匹配算法，在进行匹配之前先对模式串集合进行预处理，形成树型有限状态自动机，然后只需对文本串扫描一次就可以找出与其匹配的所有模式串。

AC算法在预处理阶段生成三个函数:转移函数g，失效函数f和输出函数output。转移函数g(s，a)指出在当前状态为s、输入字符a时自动机进入的下一状态;如输入字符不为a，则产生一个失效消息fail。失效函数f(s)表明当转移函数g(s，a)=fail时自动机应该进入的下一状态。输出函数output(s)记录了自动机进入每个状态时发生匹配的模式子集(可能为空)，用于在匹配过程中输出发生匹配的模式。

匹配过程从初始状态开始，依次读取文本T的一个字符，根据当前状态和当前输入字符，利用转移函数g和失效函数f进入下一状态。当某个状态的输出函数output不为空时输出其值，表示在文本T中找到该模式串，匹配成功［2］。

AC算法由于在对文本串进行匹配时完全按照顺序输入字符，无法跳过不必要的比较，因此在模式串数目不是很多的情况下性能并不是很好。

2.2WM 算法

Wu-Manber算法采用BM算法进行跳跃的思想和hash散列的方法。算法包括预处理和查找两个阶段。

在预处理阶段，将针对模式集合建立3个表shift表、hash表和prefix表。其中，shift表存储的是初次匹配字符串X时模式移动的距离。当shift表中对应的值为0时，初次匹配成功，再使用hash表和prefix表来验证这些模式是否真的匹配［3］。

首先需要计算模式集合中最短模式的长度，记为m，在初次匹配时只考虑每个模式的前m个字符。将文本串以B个字符长度分块，每次尝试匹配时，都比较一个“块”，即比较B个字符，根据这B个字符的匹配情况来决定模式的移动距离。比如，当文本中由B个字符组成的字符串X不在任何一个模式中出现时，模式集合可以安全地向后移动m-b+1个字符的距离。Wu-Manber算法用B个字符组成的字符块X来代替单个字符，降低了字符块在模式串中出现的概率，使匹配入口点减少，从而字符比较的次数减少，是一种效率比较高的多模式匹配算法。但是该算法未能充分利用匹配过程中不匹配时的有用信息［4］，跳过一些不匹配字符，因而还有改进之处。

3AC-WMN算法

根据以上分析，借鉴袁世忠等人提出的WMN算法思想，提出一种新的多模式匹配算法——AC-WMN算法，该算法利用改进的Wu-Manber算法的启发式搜索策略产生字符跳跃，增加尽可能多的位移，获得最大步长，同时应用AC算法的有限状态自动机构造模式树，匹配过程中移动模式树，减少规则匹配次数［5］。AC-WMN算法仍包括预处理和匹配两个阶段。

3.1AC-WMN算法的预处理

3.1.1 构造位移表

在预处理阶段，同样生成前缀索引Prefix表、后缀索引Hash表及跳跃距离Shift表。Prefix表和Hash表的计算方法与原WM算法相同。

将文本串以B个字符长度分块，通过一个散列函数将字符块映射为一个整数，并将该整数作为Hash表和Shift表的索引值。设模式串的最小长度为m，构造位移表时将所有模式串以最后一个字符对齐，在预处理阶段只考虑每个模式串的最后m个字符。

对于所有可能的字符块B，按照下列规则生成 Shift跳跃表［6］:

(1)如果字符块B不出现在任何模式串中，则Shift［h］=m-B+1，其中h为字符块B的散列值。

(2)如果字符块B出现在某些模式串中，且在所有模式串中最右的非最后一个字符块的结束位置为q，则Shift［h］=m-q，若字符块B仅在某些模式串的最后一个字符块的位置处，则Shift［h］=m-B+1。

3.1.2 构造有限状态自动机

有限状态自动机的构造借鉴王永成提出的反向跳跃自动机思想［7］，把模式串集合转换成反向有限自动机，从模式串集的右端向左逆向匹配。

转移函数g和输出函数output按照如下方法生成:初始状态为0;然后依次取出模式集中的每一个模式串执行如下操作:

从模式串的最后一个字符开始从后向前，逐个取出模式串的每个字符，从状态0出发，由当前状态和新取出的字符决定下一状态。如果下一状态不为空，则将下一状态赋为当前状态;否则，添加一个标号比已有状态标号大1的新状态，并用一条矢线从当前状态指向新加入的状态，并将新加入的状态赋为当前状态。每处理完一个模式串，将该模式串加入到当前状态的output函数中［8］。

对于模式集{they，she，his，hers}，图 2 显示了有限状态自动机的转移函数g。表2显示了output函数。

表 2 (they，she，his，hers)output的函数

图 2 (they，she，his，hers)goto 的函数

3.2 AC-WMN算法的匹配过程

AC-WMN算法的匹配过程如下:

步骤1使用当前窗口的最后B个字符计算散列值h1，使用当前窗口的最后B-1个字符和当前窗口的下一个字符(从右向左)计算散列值h2。

步骤2如果 Hash［h1］表项为空，若 Shift［h1］-1≥Shift［h2］，则窗口向左跳跃Shift［h1］并转步骤1，否则，窗口向左跳跃Shift［h2］并转步骤1;否则，转步骤3。

步骤3计算当前匹配窗口后缀的散列值rear_hash。

步骤4对于Hash［h1］指向的列表中的每个指针，检查Hash［h1］指向的模式串最右的B个字符的哈希值是否等于rear_hash，如果相等，则转至步骤5，否则转至步骤6。

步骤5利用有限状态自动机进行字符串比较。从T的当前字符开始，从后向前逐个取出T的每个字符，从状态0出发，根据转移函数g进入下一状态;当某个状态的output函数不为空时输出其值，表示在文本串中找到该模式串。

步骤6如果Shift［h1］- 1≥Shift［h2］，则窗口向左跳跃Shift［h1］并转步骤1，如果Shift［h1］-1＜Shift［h2］，则窗口向左跳跃Shift［h2］，然后转步骤1，直至扫描完全部文本。

下面是AC-WMN算法匹配过程的程序伪代码:

4 实验及结果分析

实验选取1 301 560B的英文文本，测试在不同模式串长度下，算法的性能，因此每组内模式串的长度是一致的。在实验中，每组分别取1到7个模式串，形成模式串集合进行查找，这些比较是为了测试在相同模式串长度但不同模式串数目下算法的性能。实验在CPU2.0GHz，2G内存，Windows XP下进行，算法用C++实现。实验结果如表3所示。

表3 不同算法的模式串查找时间

5 结束语

对电力企业信息内网安全事件进行关联分析能有效地管理各种异构安全设备及其产生的海量安全事件。模式匹配是实现安全事件关联分析的关键技术之一。因此提高模式匹配的效率是提高关联分析系统检测能力的关键。本文提出AC-WMN算法将改进的Wu-Manber算法的启发式搜索技术和AC算法的有限状态自动机相结合进行同时匹配。实验结果表明，AC-WMN算法能够显著提高模式匹配的效率。

［1］吴庆，胥光辉，张晶晶.安全事件关联分析系统的研究与设计［J］.军事通信技术，2007，28(01):26-29.

［2］高朝勤，陈元琰，黎芸.入侵检测中一种节约内存的多模式匹配算法［J］.计算机工程与应用，2009，45(11):107-110.

［3］王艳秋，兰巨龙.基于Wu-Manber的快速跳跃多模式匹配算法［J］.四川大学学报(工程科学版)，2007，39(1):58-61.

［4］杨东红，徐恪，崔勇.改进的Wu-Manber多模式匹配算法［J］.清华大学学报(自然科学版)，2006，46(04):555-558.

［5］宋明秋，张国权，邓贵仕.IDS中新的快速多模式匹配算法及其设计［J］.计算机工程与应用，2005，21(10):158-162.

［6］袁世忠，曹旻，王燕燕.基于WM算法的多模式匹配改进算法WMN［J］.计算机工程与应用，2007，43(15):128-130.