多模式匹配加密算法

2022-10-28

拼写检查、语言翻译、数据压缩、搜索引擎、网络入侵检测、计算机病毒特征码匹配等都会用到多模式匹配加密算法，可谓应用之广。那么我们今天就给大家介绍一下多模式匹配加密算法。

一、多模式匹配

所谓多模式匹配，就是在文本串T[1，…，n]中一次匹配多个模式串P1,P2,…，Pk，其中k为模式串的个数。k=1时，即为单模式匹配。模式串Pj的长度为mj,即Pj[1，…，mj]（1≤j≤k），minlen是最短模式串的长度，即minlen=min{mj|（1≤j≤q）}。多模式匹配比多个模式串逐个进行传统单模式匹配加密算法的速度要快得多。

二、常见多模式匹配加密算法

1、AC加密算法

采用AC加密算法进行匹配需先对模式串集合进行预处理，形成树型有限状态自动机，然后只需对文本串扫描1次就可找出与其匹配的所有模式串。 AC加密算法在预处理阶段生成3个函数：goto（转移）函数、failure（失效）函数和output（输出）函数。

匹配过程从有限状态自动机的初始状态出发，每取出文本串中的一个字符，利用goto函数和failure函数进入下一状态；当某个状态的output函数不为空时输出其值，表示在文本串中匹配到该模式串。

AC加密算法在对文本串进行搜索时无跳跃，而是按顺序输入字符，无法跳过不必要的比较，因此在模式数目不是非常多的实际搜索过程中，AC加密算法性能不佳。AC极爱算法模式匹配的时间复杂度是O（n），而且与模式集中模式串的个数和每个模式串的长度无关，无论模式串P是否出现在T中，T中的每个字符都必须输入状态机中，所以无论是最好情况还是最坏情况，AC加密算法模式匹配的时间复杂度都是O（n），包括预处理时间在内AC加密算法的总时间复杂度是O（M+n），其中M为所有模式串的长度总和。

2、WM加密算法

WM快速字符串匹配加密算法采用BM加密算法进行跳跃的思想和hash散列方法，在实际应用中，是大规模多模式匹配最快的加密算法之一。WM加密算法将文本串以B个字符长度分块，称该B个字符为1个块字符，B为块字符的长度，B通常取2或3。首先对模式集进行预处理，在预处理阶段构造3个表，即shift表、hash表和prefix表。匹配过程从文本串text的第（m-B+1）（m是模式集中模式串的最小长度）个字符处开始，每次计算当前块字符的hash值h，通过shift[h]的值决定是否向后跳跃；当shift[h]的值为0时，将hash[h]链表中的每一个模式串从后向前与text比较，如果未达到text末尾，则将text向后移动1个字符继续比较。

WM加密算法的优点：

是字符跳跃距离大，使用shift表可以跳过那些不可能成功的匹配入口，匹配入口点少，从而减少字符比较次数。因此实际应用中，WM加密算法的效率一般比AC加密算法高。

WM加密算法的缺点：

WM加密算法在每个匹配入口点处，要逐个比较hash[h]表中每一个模式，在模式集数目较大时，算法性能明显下降。

WM加密算法在模式匹配中采用启发式搜索策略进行字符跳跃，匹配的时间复杂度平均情况是O（Bn/m），实际应用中B≤m，所以WM加密算法模式匹配的时间复杂度低于AC加密算法。

3、ExB加密算法

ExB加密算法是一个基于排除的字符串匹配加密算法，该加密算法能很快排除数据包负载中不包含匹配模式串的数据包。

ExB加密算法原理：

假设要检测字符串A中是否包含子串s，如果s中至少有1个字符不包含在A中，则s就不是A的1个子串。为了减少错误匹配的概率，将该算法扩充到字符对，匹配过程不仅检测s中每个字符是否出现在A中，还检测每一字符对中的字符出现的顺序是否正确。为了快速判定给定的字符c是否属于字符串A，该加密算法采用出现图的方法。对于A中出现的字符c在出现图中的相应位置采用二进制值标记，“1”表示c属于A，“0”表示c不属于A。对于每个新数据包，出现图都要进行一次大开销清零工作。为了减少这种开销，采用每个数据包的序列号取代二进制值来标记出现图中的相应位置，这样出现图就无需对每一个新数据包都进行清零。

ExB加密算法算法可分为预处理和搜索两个阶段。预处理阶段的时间复杂度与数据包负载的大小成线性关系，搜索阶段的时间复杂度与所有模式中的长度和成线性关系。由于在多数数据集中，入侵数据包毕竟是少数。另外，据统计仅有1.6%的数据包需要用标准的字符串匹配算法进一步确定该入侵特征串是否在数据包中，因此调用标准串匹配算法的概率很小，所以在实际应用中，该加密算法的效率高于其他应用于入侵检测中的匹配加密算法。

三、多模式加密算法性能测试和结果分析

测试环境：CPU是In-telPentiumE22002.2G，内存1G，硬盘160G，操作系统Win-dows2003，加密算法实现环境是VisualC++6.0。利用入侵检测训练数据集，选取1天的流量数据（容量约160MB的Tcp-dump文件）作为测试数据集。入侵检测系统分别采用AC加密算法、WM加密算法和ExB加密算法作为模式匹配检测引擎，测试这3种情况下平均模式匹配时间与模式数目的变化关系，对比情况如表所示。

由上表可知，模式数小于20个时ExB加密算法最优，模式数在50～100时AC加密算法的匹配效率更好，当模式数大于100时，WM加密算法性能更好。

随着网络应用的发展和网络带宽的增加，必须提高网络入侵检测系统的处理性能。而目前的网络入侵检测系统多是基于特征匹配的系统，这类系统中的关键运算是模式匹配，因此提高模式匹配加密算法的效率是提高这类系统检测能力的关键。

小知识之Hash：

Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。