基于决策树剪枝的模式匹配方法

摘要

本发明提出一种基于决策树剪枝的模式匹配方法，其结合决策树剪枝方法的简化AC算法，包括自动机的生成、自动机的简化、计算失败指针、存储后缀表与匹配的执行等步骤。本发明将传统自动机类型模式匹配算法拆分为两个步骤：匹配可能的判定与匹配确认。通过简化自动机判别文本串与模式集中模式串有无匹配的可能，再进行匹配的确认。在保证速度的前提下，本发明提出的简化方法相比传统自动机类型模式匹配算法内存消耗减少35％‑40％。此外，本发明通过决策树剪枝方法可有效减小自动机规模，删除对分类判定无用的节点，有效降低传统自动机类型模式匹配的内存消耗。

说明书

技术领域

本发明涉及信息安全技术领域，具体涉及一种基于决策树剪枝(Decision Tree Pruning)的模式匹配方法。

背景技术

模式匹配算法广泛应用于入侵检测、信息检索、模式识别、基因匹配等众多领域。性能稳定的模式匹配算法是网络入侵检测系统的“倍增器”。基于自动机的模式匹配算法具备性能稳定的特点，其中以AC算法为代表。由于AC算法拥有线性最差时间复杂度，柔性高，可容忍短模式，可抵抗复杂度攻击，因此是目前首选的在线匹配算法之一。

然而，随着对模式匹配性能需求的增加，基于自动机类的模式匹配算法成为高性能模式匹配体系结构设计的基础。但此类算法生成的DFSA规模较大，特别对于大规模模式集(10万以上模式集)生成自动机的规模需要大量的内存存储，这大大阻碍了自动机类匹配算法的应用。

发明内容

本发明所要解决的技术问题是针对现有基于自动机的模式匹配算法需要大量的内存存储的问题，提供一种基于决策树剪枝的模式匹配方法。

为解决上述问题，本发明是通过以下技术方案实现的：

基于决策树剪枝的模式匹配方法，包括如下步骤：

步骤A.即根据自动机生成规则，将模式集中的模式串依次添加到自动机中；

步骤B.在自动机生成过程中，每一个模式串添加完成，即将此模式串添加到当前节点的输出表中；

步骤C.对生成的自动机进行剪枝，去除对分类来说属于非必要的节点，减少自动机节点数量，简化自动机；在对自动机进行剪枝的过程中，生成后缀表；

步骤D.计算自动机各节点的状态深度，其中节点的状态深度为该节点距根节点的最短路径长度；

步骤E.根据节点状态深度，计算出各节点的失败指针；

步骤F.依次取出文本串中字符输入自动机，完成模式匹配。

上述步骤C的过程具体为：

步骤C1.对自动机的各个分支进行逐个遍历；

步骤C2.当从根节点遍历至终端叶子节点的过程中，仅存在终端叶子节点这一个输出节点，即输出节点为1个时，则从终端叶子节点开始向上回溯至最后一个单分枝节点，将该单分枝节点的剪枝标志位置为1，修剪掉该单分枝节点之后的枝叶，并将该单分枝节点的后续枝叶包含的后缀以字符串的形式存储于后缀表；

步骤C3.当从根节点遍历至终端叶子节点的过程中，存在除终端叶子节点这一个输出节点之外的其他输出节点，即输出节点为2个以上时，则从终端叶子节点开始向上回溯至倒数第二个输出节点，将该倒数第二个输出节点的剪枝标志位置为1，修剪掉该倒数第二个输出节点之后的枝叶，并将该倒数第二个输出节点的后续枝叶包含的后缀以字符串的形式存储于后缀表。

上述步骤E的过程具体为：

步骤E1.将自动机的根节点的失败指针(失败指针为节点匹配失败后的跳转方向指针)指向根节点；

步骤E2.将自动机中状态深度为1的节点的失败指针也指向根节点；

步骤E3.对于自动机中状态深度大于或等于2的节点s，若其父节点r经过字符a能够到达节点s即Goto(r,a)＝s，则先将节点s的当前状态指向父节点r的失败状态，直至节点s的当前状态经过字符a存在下一跳节点t时，将节点s的失败指针指向节点t。

上述步骤F的过程具体为：

步骤F1.在执行阶段搜索过程中，自根节点开始，依次取出文本串中的字符，根据转移表Goto和失败表Fail确定下一状态节点。

步骤F2.检查状态节点输出标志位q.danger：

如节点输出标志位q.danger＝1，则输出栈中字符串；

如节点输出标志位q.danger＝0，则不进行输出。

步骤F3.继续检查节点剪枝标志位q.suffix。

如标志位q.suffix＝1，则转向后缀存储位置指针q.suffix.pointer指针指向的后缀继续进行匹配判定，完成完整的字符串判定：如成功则输出栈中字符串和对应后缀作为完整的规则，并返回相应的叶子节点q；如不成功则应直接返回至相应的叶子节点q，再根据失败函数进行跳转，继续搜索。

如节点剪枝标志位q.suffix＝0，则继续根据转移表Goto与失败表Fail来确定下一状态节点。

本发明提出一种结合决策树剪枝(Pruning)方法的简化AC(Aho-Corasick)算法，包括自动机的生成、自动机的简化、计算失败指针、存储后缀表与匹配的执行。本发明通过决策树剪枝方法可有效减小自动机规模，删除对分类判定无用的节点，有效降低传统自动机类型模式匹配的内存消耗。本发明在具体实现时，将传统自动机类型模式匹配算法拆分为两个步骤：匹配可能的判定与匹配确认。通过简化自动机判别文本串与模式集中模式串有无匹配的可能，再进行匹配的确认。在保证速度的前提下，本发明提出的简化方法相比传统自动机类型模式匹配算法内存消耗减少35％-40％。

与现有技术相比，本发明具有如下特点：

1.本发明是基于决策树剪枝的AC改进算法，通过应用决策树剪枝方法可有效降低基于DFSA的AC算法的自动机规模，去除对锁定模式集中模式串无用的节点，减少节点数量；

2.本发明在简化自动机规模，去除冗余节点的同时，达到降低AC算法内存消耗的目的，这一方法可应用到绝大多数自动机类型的模式匹配算法中，改善自动机类型模式匹配算法的空间复杂度；

3.本发明虽然引入了决策树剪枝方法，但传统AC算法的很多实现方法只需稍加修正依然适用，并不需要添加过多额外的计算，且实验表明在匹配速度与原AC算法基本持平的前提下，实现了内存空间节省35％-40％。

附图说明

图1为简化前的自动机；

图2为简化后的自动机；

图3为简化前节点的状态深度；

图4为简化后节点的状态深度；

图5为简化前节点的失败指针；

图6为简化后节点的失败指针。

具体实施方式

为了使本发明的技术方案及优点更加清楚明白，结合附图及实施例，对本发明做进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。

一种基于决策树剪枝的模式匹配方法，具体步骤为：

本实施例输入的文本串为T，模式集K{his,the,there,who}，其中T为由任意字符组成的文本串，K中K_i为模式串。

阶段I：生成自动机。

步骤1，根据AC算法的自动机的生成规则，即Goto函数，将模式集中的模式串依次添加到自动机中，生成如图1所示的自动机。同时，自动机生成过程中，每一个模式串添加完成，即将此模式串添加到当前节点的输出表中。

自动机生成的具体步骤为：

步骤1-1.若模式集中模式串的个数n≤0，返回错误；当前模式串i＝0。

步骤1-2.若当前模式串i≤模式集中模式串的个数n；取模式串p_i，令s＝0(s为当前状态指针)；否则生成结束。

步骤1-3.取出模式串p_i的下一个字符c；若字符c，存在则s＝Goto(s,c)，否则跳转步骤1-2。

步骤1-4.若当前状态s≠-1(-1代表状态为空)，跳转至步骤1-3。

步骤1-5.Goto(s,c)＝newstate(newstate为生成新状态)，跳转至步骤1-3。

输出表的具体步骤为：

步骤1-6.计算Goto函数时，当一个模式串完成加入自动机操作后，应将该模式串加入到最后一个状态的输出表中。

步骤1-7.计算Fail函数(Fail函数为失败跳转函数)时，当r＝Fail(s)时，将r的输出表中所包含的模式串添加到状态s的输出表中。

步骤2，根据下述规则简化自动机，简化后的自动机如附图2所示。

规则一：在逐个分支遍历的过程中，如遍历至终端叶子节点z，则向上回溯至最后一个单分枝节点a，将此节点标志位suffix(suffix为节点剪枝标志位)置1，并剪除节点a之后的枝叶，将a节点后续枝叶包含的后缀以字符串的形式存储于后缀表。

规则二：如从根节点遍历至终端叶子节点的过程中不止存在一个输出节点，如整个分支在向上回溯的过程中自底向上分别对应1,2...m，共m个输出节点，则只可修剪掉输出节点2之后的枝叶，此时输出节点2标志位suffix置1，并剪除输出节点2之后的枝叶，将输出节点2后续枝叶包含的后缀以字符串的形式存储于后缀表。

步骤2-1，从根节点开始逐位遍历经节点1、2至终端叶子节点3，向上回溯至最后一个单分支节点1，将节点1的剪枝标志位suffix置1，因节点1是非输出节点，故节点输出标志位danger(danger为节点输出标志位)置0，并将其后的枝叶包含的后缀is，以字符串的形式存储于后缀表。

步骤2-2，继续遍历，经节点4、5、6、7至终端叶子节点8，向上回溯至节点6，因节点6为输出，将节点6的剪枝标志位suffix置1，因节点6是输出节点，故节点输出标志位danger置1，并将其后的枝叶包含的后缀re，以字符串的形式存储于后缀表。

步骤2-3，继续遍历，经9、1根节点至终端叶子节点11，向上回溯至最后一个单分支节点9，将节点9的剪枝标志位suffix置1，因节点9为非输出节点，故节点输出标志位danger置0，并将其后的枝叶包含的后缀ho，以字符串的形式存储于后缀表；剪枝完成。

步骤3，上述简化过程中修剪掉的枝叶中所包含的后缀以字符串的形式存储于后缀表。表1所示为通过简化规则生成的后缀表。

表1

节点169后缀isreho

步骤4，计算自动机的状态深度。由于本发明对自动机进行了修剪，因此，只需计算修剪后剩余的每个节点的状态深度。图3为简化前节点的状态深度；图4为简化后节点的状态深度。

步骤4-1.根节点的状态深度为0。

步骤4-2.若节点a状态深度为d，那么其左子节点状态深度为d+1，右子节点状态深度为d。

步骤5，计算自动机的失败指针。图5为简化前节点的失败指针；图6为简化后节点的失败指针。

步骤5-1.根节点失败指针指向根节点。

步骤5-2.深度为1的节点，其失败指针也指向根节点。

步骤5-3.深度大于或等于2的节点s，若其父节点r经过字符a能够到达节点s即Goto(r,a)＝s，则先将节点s的当前状态指向父节点r的失败状态，直至节点s的当前状态经过字符a存在下一跳节点t时，将节点s的失败指针指向节点t。

阶段II：执行匹配。

步骤6，执行阶段在搜索过程中，自根节点开始，依次取出文本串中的字符，确定下一状态节点。

步骤7，检查状态节点标志位q.danger是否为真：如为真，则输出栈中字符串；如为假，则不进行输出。

步骤8，检查q.suffix是否为真。

步骤8-1.如果为真，则转向后缀存储位置指针q.suffix.pointer指针指向的后缀继续比对，完成完整的字符串比对：如成功则输出栈中字符串和对应后缀作为完整的规则，并返回相应的叶子节点q；如不成功则应直接返回至相应的叶子节点q，再根据failstate跳转，继续搜索。

步骤8-2.如q.suffix为假则继续根据Goto函数与失败指针来确定下一状态节点。

本发明基于决策树剪枝的AC改进算法，包括自动机的生成、自动机的简化、计算失败指针、存储后缀表与匹配的执行。本发明在具体实现时，将传统自动机类型模式匹配算法拆分为两个步骤：匹配可能的判定与匹配确认。通过简化自动机判别文本串与模式集中模式串有无匹配的可能，再进行匹配的确认。在保持原有的匹配速度的前提下，有效减少自动机节点数量，去除自动机中冗余节点，达到简化自动机规模，降低模式匹配算法的内存消耗的目的。本发明可以针对绝大多数自动机类型的匹配算法进行简化。