一种基于关键字词频特征的多模式匹配方法

摘要

本发明提供一种基于关键字词频特征的多模式匹配方法，首先从已知的信息数据库中提取关键字并统计出现频率作为其词频信息，其次采用构造含有关键字词频信息的二叉树完成其中的模式串匹配，在字符匹配过程中若出现字符不相等，则与该不匹配字符所在节点的兄弟节点所含字符进行匹配。其利用信息来源的模式的关键字词频信息构造基于字典树的二叉树完成其中的模式串的匹配，并与AC算法进行了比较。传统的AC算法需要维护三张表，并且在模式匹配过程中会频繁访问这三张表；本发明的一种基于关键字词频特征的多模式匹配方法更多的利用了模式本身的词频信息，并不需要维护过多的信息，这就大大减少了系统的内存消耗。

说明书

技术领域

本发明涉及计算机网络安全技术领域，具体涉及一种基于关键字词频特征的多模式匹配 方法。

背景技术

入侵检测系统(IDS，IntrusionDetectionSystem)是一种对网络传输进行即时监视， 在发现可疑传输时发出警报或者采取主动反应措施的网络安全设备。它与其他网络安全设备 的不同之处便在于，IDS是一种积极主动的安全防护技术。IDS以信息来源的不同和检测方法 的差异分为几类：根据信息来源可分为基于主机IDS和基于网络的IDS，根据检测方法又可 分为异常入侵检测和误用入侵检测。

误用入侵检测系统中常用的检测方法有：模式匹配法、专家系统法、基于状态转移分析 的检测法。其中模式匹配法常常被用于入侵检测技术中，它通过把收集到的信息与网络入侵 和系统误用模式数据库中的已知信息进行比较，从而对违背安全策略的行为进行发现。模式 匹配法可以显著地减少系统负担，有较高的检测率和准确率。

Aho-Corasick算法在1975年产生于贝尔实验室，是著名的多模匹配算法之一。 Aho-Corasick算法对应的数据结构是Aho-Corasick自动机，简称AC自动机。AC算法的特点 是可以保证对于给定的长度为n的文本，和模式集合P{p1,p2,...pm}，在O(n)时间复杂度内， 找到文本中的所有目标模式，而与模式集合的规模m无关。

但是AC算法在模式匹配的过程中预处理时间较长，并且因其需维护goto表、fail表和 output表导致内存消耗巨大，算法性能仍然有待提高。

发明内容

为了克服现有技术的不足，本发明提供一种基于关键字词频特征的多模式匹配方法，它 能解决现有技术在模式匹配的过程中预处理时间过长及占用较大内存等问题。

本发明采用的基于关键字词频特征的多模式匹配方法，首先从已知的信息数据库中提取 关键字并统计出现频率作为其词频信息，其次采用构造含有关键字词频信息的二叉树完成其 中的模式串匹配，在字符匹配过程中若出现字符不相等，则与该不匹配字符所在节点的兄弟 节点所含字符进行匹配。

本发明利用信息来源的模式的关键字词频信息构造基于字典树的二叉树完成其中的模式 串的匹配，并与AC算法进行了比较。传统的AC算法需要维护三张表，并且在模式匹配过程 中会频繁访问这三张表；本发明的一种基于关键字词频特征的多模式匹配方法更多的利用了 模式本身的词频信息，并不需要维护过多的信息，这就大大减少了系统的内存消耗。

本发明采用的具体技术方案是：

一种基于关键字词频特征的多模式匹配方法，包括以下步骤：

S21初始化二叉树；

S22输入待匹配模式串后开始匹配；

S23若匹配成功则判断该节点是否含有模式串结束标志，若是则输出模式串，若否则判 断匹配成功节点的左分支节点是否存在，若是则将指针指向其左分支节点并返回S22，若否 则结束匹配；若匹配失败则判断匹配失败节点的右分支节点是否存在，若是则将指针指向其 右分支节点并返回S22，若否则结束匹配；

S24判断指针移动后是否超出待匹配模式串串尾，若否则返回S22，若是则结束匹配。

进一步的，所述二叉树的初始化包括以下步骤：

A)假设有定义在字符集Σ上的模式串集合K＝{s₁,s₂,s₃,…,s_n}(s₁,s₂,s₃,…s_k…,s_n表示从已 知数据库中提取的模式串，n表示模式串数量，其取值范围与计算机性能相关),用K中的模 式串生成二叉树,并记第i层的左起第j个节点为a_ij，其中i，j＝0,1,2，……，将同一模式中的 字符所在节点标记为f_k，并将终结字符节点标记为o_k，其中k表示模式串集合中的第k个字 符串，k＝1,2，……，n；

B)统计模式串s_k出现的频率p_k，并将频率p_k作为模式串s_k的词频加入含有o_k标记的节 点；

C)设匹配一个字符的计算力是c，二叉树中最左分支由底向上的第一个分支节点为A， 从A到输出其下m个分支中所有模式分别需要匹配节点l_m次(含匹配A)，m为A分支个数， 由左向右对应模式s_k，s_k+1，……，s_k+m-1；计算期望E_m1＝c*l_k*p_k+c*l_k+1*p_k+1+……+c*l_k+m-1*p_k+m-1(c表示计算力，l_k表示对应匹配模式s_k所需匹配节点次数，p_k表示s_k所携带该模式词频信 息)，然后交换分支计算E_m2，……，直至计算出E_A＝min{E_m1，E_m2，……}，此时由右向左 对应模式s’_k，s’_k+1，……，s’_k+m-1；

D)由左向右由底向上依次找出A之外的所有节点并按上述方式进行二叉树的重构，当根 节点计算完毕并交换分支后，即得到最终的二叉树。

进一步地，步骤C中所述最左分支包含根节点、根节点的左分支节点以及该左分支节点 的左分支节点和其后左分支节点。

进一步的，所述步骤A的二叉树的生成规则为：根据模式串集合的初始词频信息将模式 串按词频由高到低顺序排列，并依次插入二叉树，同时将模式串信息加入模式串末位字符节 点中，并在该末位字符节点设置模式串结束标志；首次插入的模式串中，后插入的字符节点 作为先插入的字符节点的左分支节点；若两模式串前缀相同，则将后插入的模式串的首个不 相同节点作为先插入的模式串的首个不相同节点的右分支节点插入。

有益效果：本发明采用一种基于关键字词频特征的多模式匹配方法，完成模式串的匹配， 由于未构造AC算法中的失效函数表，并且采用单字符信息节点替换AC算法中的字符数组节 点，冗余节点大大减少，从而大大降低了入侵检测系统的内存消耗；本发明的一种基于关键 字词频特征的多模式匹配方法用途广泛，可应用在搜索、网络入侵检测、敏感URL检测和过 滤等方面。

附图说明

图1是本发明实施例1的匹配过程流程图；

图2是本发明实施例1的初始化字典树示意图；

图3(a)是本发明实施例1的计算节点1交换分支前的期望示意图；

图3(b)是本发明实施例1的计算节点1交换分支后的期望示意图；

图4(a)是本发明实施例1的计算节点0交换分支前的期望示意图；

图4(b)是本发明实施例1的计算节点0交换分支后的期望示意图；

图5是本发明实施例2使用本发明的匹配方法和基于传统AC算法的匹配方法所收集的数 据项；

图6是本发明实施例2使用本发明的匹配方法和基于传统AC算法的匹配方法对模式串进 行匹配的预处理时间对比图；

图7是本发明实施例2使用本发明的匹配方法和基于传统AC算法的匹配方法对模式串进 行匹配的匹配时间对比图；

图8是本发明实施例2使用本发明的匹配方法和基于传统AC算法的匹配方法对模式串进 行匹配的内存占用对比图；

具体实施方式

为使本发明的上述特征和优点能更明显易懂，下文特举实施例，并配合所附图作详细说 明如下。

下面结合附图和具体实施方式对本发明作进一步的详细说明。

实施例1：

如图1所示可以清楚了解本发明的一种基于关键字词频特征的多模式匹配方法的匹配过 程：

S21初始化二叉树；

S22输入待匹配模式串后开始匹配；

S23若匹配成功则判断该节点是否含有模式串结束标志，若是则输出模式串，若否则判 断匹配成功节点的左分支节点是否存在，若是则将指针指向其左分支节点并返回S22，若否 则结束匹配；若匹配失败则判断匹配失败节点的右分支节点是否存在，若是则将指针指向其 右分支节点并返回S22，若否则结束匹配；

S24判断指针移动后是否超出待匹配模式串串尾，若否则返回S22，若是则结束匹配。

进一步的，所述二叉树的初始化规则包括以下步骤：

A)假设有定义在字符集Σ上的模式串集合K＝{s₁,s₂,s₃,…,s_n},用K中的模式串生成二叉 树,并记第i层的左起第j个节点为a_ij，其中i，j＝0,1,2，……，将同一模式中的字符所在节点 进行标记f_k，并对终结字符节点进行标记o_k，k＝1,2，……，n；

B)统计s_k出现的频率p_k，并将参数p_k作为s_k的词频加入含有o_k标记的节点；

C)设匹配一个字符的计算力是1，由左向右由底向上的第一个分支节点为S，从S到输 出其下所有模式分别需要匹配l_m次(含匹配S)，m为S分支个数，由左向右对应模式s_k， s_k+1，……，s_k+m-1；计算期望E_m1＝l_k·p_k+(l_k+1+1)·p_k+1+……+(l_k+m-1+m-1)·p_k+m-1，然后交换分 支计算E_m2，……，直至计算出E_A＝min{E_m1，Em2，……}，此时由左向右对应模式s’_k， s’_k+1，……，s’_k+m-1；

D)由左向右由底向上依次找出A之外的所有节点并按上述方式重构二叉树，当根节点 计算完毕并交换分支后，即得到最终的二叉树。

进一步的，所述步骤A的二叉树的生成规则为：根据模式串集合的初始词频信息将模式 串按词频由高到低顺序排列，并依次插入二叉树；首次插入的模式串中，后插入的字符节点 作为先插入的字符节点的左孩子节点；若两模式串前缀相同，则将后插入的模式串的首个不 相同节点作为先插入的模式串的首个不相同节点的右孩子节点插入。

下面以一实际的模式串集合进行说明，对应模式集{he，she，his，hers}在一个已知字 符集中提取该模式集中各个模式串的词频信息，构造一个字典树，并在终结状态节点3、7、 8、9分别引入所提取词频信息0.1、0.3、0.5、0.1(该词频函数依据本发明预期效果设定)， 如图2。

自下而上寻找并计算第一个有分支的节点，即计算分支节点1。假设达到一个节点的计 算力为1，即只要比较一个字符就要消耗1个单位的计算力，这里的计算力可以是消耗的内 存或时间。如图3(a)，在当前的分支结构下，输出he需要2个计算力(到达节点1需要先 匹配h)，输出hers需要2个计算力(指定输出he后指针停留在节点3，所以只需再匹配rs 即可输出hers)，输出his需要4个计算力(这里假设是在最优情况下消耗的计算力，即匹配 i时根据前序遍历无法到达节点3，但本次失配也消耗了1个计算力，之后继续匹配节点4和 7)，故输出匹配模式的期望E₁＝l₁·p₁+(l₂+1)·p₂+(l₃+2)·p₃＝2*0.1+2*0.1+4*0.3＝1.6；若 交换左右分支，依上述规则计算可得到期望为E₁’＝1.4。显然E₁’＜E₁，这说明交换后开销更 低，所以应当将左右分支交换，得到图3(b)。

新的结构如图4(a)，同理，再计算分支节点0的期望E₀＝3.4，交换左右分支，期望E₀’＝3.3， 说明依然应当交换，如图4(b)。

也可计算出原自动机的匹配期望E＝3.6，显然图4(b)所示二叉树的期望值最小，即在 该词频下的理论匹配效率最高。则图4(b)即为引入词频特征后的最优二叉树。

实施例2：

本实施例所采集的数据特征，如图5：

1)相同模式串个数及长度的模式集20组；

2)能够完全匹配的模式比例分别为1‰、1％、2％、3％、4％、5％、6％、7％、8％、9％、10％、 20％、30％、40％、50％、60％、70％、80％、90％、100％；

3)完全匹配的模式中词频最高模式出现频率为50％；

对上述20组模式集分别采用AC算法和本发明的方法进行匹配并进行相关测试，测试项 包括AC算法和本发明的方法PROB的预处理时间(图6，横坐标表示模式数量)、匹配时间(图 7，横坐标表示词频最高模式所占比例)和内存占用(图8，横坐标表示模式数量)的对比。

从图6、图7、图8中可以看出，本发明在控制匹配时间增幅的同时减少了预处理时间， 并大大降低了系统的内存占用，提高了系统的性能。