基于特征值的多模式匹配算法

1、基于特征值的多模式匹配算法【摘要】 高速网是当今网络发展的必然趋势，采用现行匹配算法的入侵检测系统(IDs)很难在高速网中有效地运行。本文主要从特征值的多模式匹配算法、模式库的组织和逻辑实现这三个方面来大幅度地提高系统检测速率，完全适应于高速网络的入侵检测。【关键词】入侵检测 特征值 模式匹配 多模式匹配1. 引言入侵检测是对网络或系统进行监视，发现各种攻击的企图，行为或攻击结果，采取相应的响应措施以保护系统资源的机密性、完整性和可用性。根据入侵检测系统对数据分析方法的不同，可将其分为两大类：异常入侵检测和误用入侵检测。误用入侵检测是当前的主流，它的核心是规则库的组织和模式匹配算法。但随着网络

2、速度的迅速提高，规则库的日益增大，误用入侵检测暴露出其致命缺陷：检测速率太低，在一个满负荷的lOOM 以太网上，将不得不丢掉30一75 的网络数据包2J，这将漏掉对许多可疑数据包的检测，严重影响了系统检测的准确性。2. 基于特征值匹配算法的思想在入侵检测系统中，字符串匹配消耗了大量的系统资源(主要是CPU资源)，严重制约着系统检测速率的提高。当前常用的匹配算法主要有：KMP算法 BM 算法等。这些算法都有一个共同特点：一次性准确匹配。它们的思想是在数据包中对模式字符串直接匹配，若不匹配则根据某种启发式策略跳过一定量字符后接着匹配。在实际高速网络中未发生带宽类型攻击的情况下，真正的入侵数据包只占

3、网络总流量的较少一部分。系统资源的消耗主要不是在对入侵数据包的检测，而是对正常数据包的穷举匹配。针对这一实际的情况，本文提出了基于特征值的快速匹配算法。定义1 特征值：一个字符串经过某种简单运算而得到的一个值，这个值称为该字符串的特征值，用T标志。一般而言，字符串和特征值可能存在多对一的关系，即一个字符串有且仅有一个特征值，而多个字符串以一定概率对应于同特征值。我们的目的就是选择合适的简单运算，尽可能的降低不同字符串对应相同特征值的概率。基于特征值匹配算法的基本思想是：把数据包中字符串的特征值与等长模式字符串的特征值相比较，若不等则两个串肯定不匹配若相等则两个字符串以极大概率匹配，需要进行第二

4、次匹配确认。简单地说，就是采取两次匹配的方法，首先过滤掉大量肯定不匹配的字符串，接着进行第二次准确匹配。第一次匹配算法要求简单，由硬件直接实现，以减轻CPU 的负担， 而且要能过滤掉绝大多数正常数据包。首次匹配是关键所在，这里主要详细探讨基于特征值的第一次匹配算法。设模式字符串 S=S1,S2,S3,Sm,长度为m，特征值为r。数据包字符串P=P1,P2,Pm，长度为n。首先求出数据包中长为n的字符串P1,P2,Pm的特征值，然后与模式字符串的特征值T相比较，若相等则进行第二次匹配，否则两个字符串肯定不匹配，数据包字符串P往右平移一个字符继续匹配P2,P3,Pm+1。平移后的特征值可以由平移前

5、的值经过简单运算得到，这一过程支持硬件实现。为了提高系统的并行度，可以采用分组匹配的方法。首先把数据包分成n/m个组，每组长度为m，然后用硬件同时计算各组的特征值，把特征值与模式字符串的特征值相比较，若相等则进行第二次匹配，否则同时往右平移一个字符继续匹配，总共只需平移m次便可完成整个匹配计算过程。3. 特征值的计算方法特征值的计算方法有多种，但它们应符合以下几点要求：(1)计算简单，能由硬件电路直接实现，以减轻CPU负担。(2)能过滤掉大量的正常数据包，也就是说，和同一特征值对应的字符串应较少。(3)平移后的特征值可以由平移前的特征值经过简单运算得出，以减少特征值的计算次数。定义2 位向量：

6、在一个字符串中，取每个字符相同位上的比特按字符顺序构成的二进制串称为位向量。任何一个长为m的字符串有且仅有8个长为Be的位向量，例如字符串“GOOD”中各个字符的ASCII码为、，取每个字符的最低位构成的位向量为l110。该字符串共有8个长为4的位向量，分别是0000、l1l1、0000、0000、0110、l1l1、l110、l110。根据位向量求出的特征值称为位特征值，用t标志。8个位特征值组成该字符串的特征值T,T=t7、t6、t5、t4、t3、t2、t1、t0定义3 过滤率：第一次匹配过滤的正常数据包量与总流量的比值称为过滤率，一般要求第一次匹配的过滤率越高越好。当网络中没有入侵包时，

7、准确匹配算法的过滤率是100%。异或求值法字符串中各个字符通过异或即可得到该字符串的异或特征值。为不失一般性，设字符串为S1,S2,Sm，则该字符串的特征值 S1S2S3Sm ，共8个比特。例如，模式字符串“CMD ”中各字符对应的ASCII码为、01010l11、，它的特征值 T=CMD= 。按所有代码出现的概率相同计算，则位向量中“1 的个数为奇数和偶数的概率是相同的， 即一个位特征值的过滤率为50%。各个位特征值之间相互独立，8个位特征值的过滤率为1-(1/2)8=99.61%。也就是说，需要第二次匹配的可疑数据包是总流量的0.39%。实验结果表明，其平均过滤率为99.8%，可以采用简单

8、的异或逻辑来实现，如图1所示T的初始值为0。图表 1 异或求值图平移前的特征值与移入和移出的字符异或便可得出平移后的特征值。例如： 字符串“P O W E R ”中匹配“PING 时,首先求出“POWE”的特征值T1=POWE=0000 l101。它与“PING 的特征值0001 0000不匹配，分组往右平移一个字符，变成“0WER ”。该分组的特征值由T1PR两次异或得出等于0000 11l1，与0001 0000也不相等， 由此得知字符串“P0WER” 中不包含模式串“PING”，匹配结束。当模式串长为m时，第一次求特征值需要进行（m-1）次异或运算，平移后的特征值只需2次异或运算。4.

9、基于特征值的多模式匹配算法Aho及Corasick于1975年提出一种基于有限状态自动机的多模式匹配算法(AC算法)，该算法允许同时并行搜索多个字符串，搜索的时间为O(n)，建立自动机的时间与模式字符串的长度成线性关系。现在常用的算法是AC算法和BM算法相结合而形成的ACBM算法，它是将不同的规则放置在一棵模式树上，然后对这棵模式树采用BM 算法进行检索。基于特征值的多模式匹配算法的思想是：将模式库中的规则按其长度分组，在组内再按特征值排序并建立索引，组内特征值相同的规则通过链表的形式链接在同一特征值索引上。通过第一次匹配，找到可疑字符串对应的特征值索引，接着进行第二次准确匹配，将可疑字符串与

10、规则比较。4.1模式库的组织整个模式库构成一个树形结构，模式字符串的长度用L表示(假定Max(L)=m)，初始化时间与模式库的大小成线性关系。整个模式库的组织如图2所示。图表 2模式库的组织架构42多特征值计算逻辑实现为了加快处理速度，采用移位寄存器和异或逻辑来同时求出不同长度字符串的特征值。其逻辑实现如图3所示(为了表达的简便，设规则库中字符串的最大长度为7)。图表 3异或多模求值设输入的字符串P=“abcdefghijklmn”，依次输入移位寄存器R7R0，所有寄存器中的初始值都为0。第一个节拍时，字符a移入D7，经过异或逻辑后存入R7内。第二个节拍时，字符b移入D 与R 中的a，异或后再

11、存入R7，内；字符a移入D6，经过异或逻辑后存入R6内。第7个节拍时，D7D1中保存着“gfedcba”；R7中保存着gfdecba的值，R6中保存着fedcba的值，其余类推。第8个节拍时，字符a移入D0再返回来与各特征值异或，清除a字符；此时R7中保存着 hgfedcba 的值，R6中保存着gfedcba 的值，其余类推。以后每移一个字符便可同时得出各种长度字符串的异或特征值，再与模式库中相同长度模式字符串的特征值相匹配，即R7中的字符串特征值与模式库中L=7的分支匹配，R6的字符串特征值与模式库中L=6的分支匹配等等。43匹配过程的处理为了提高匹配速度，采用直接地址映射的方法来完成对模式

12、特征值的查找过程。在模式库初始化时，给每一种长度的规则分支分配256字节的存储空间，每个存储单元中保存着一个指针，该指针指向模式特征值等于其偏移地址的规则。如果没有模式特征值和其偏移地址相等，则指针为空；若有多个规则和其偏移相等，则其它规则依次链接在指针指向的第一个规则后面，形成一个链表结构。当特征值计算电路得出某一长度字符串的特征值后，直接找到偏移地址是字符串特征值的存储单元，若该存储单元指针为空，则表明该字符串与模式库不匹配；否则和指针指向的规则进行第二次匹配。在Snort规则库中抽出100个规则形成模式库结构，指针非空的存储单元占总存储空间的2.07%，对应于同一存储单元的规则占0.19

13、%。从特征值的计算至找到对应长度模式特征值的时间非常短，基本可以忽略。在多模式匹配中，也可采用模3方法计算特征值，其过滤率为99.985%，逻辑实现与异或逻辑实现相似。如果采用模5方法计算特征值，其过滤率可达99.99974%，但实现比较复杂，数据的延时也会增加，成为处理的瓶颈， 因此需要多个逻辑并行处理。5. 对比实验为了测试算法的实际性能，在网络中随机捕获150M数据，模式字符串来自Snort入侵检测系统中的规则，对于基于特征值的多模式匹配算法，统计了程序模拟的执行时间、异或逻辑实现时间。从特征值的计算至找到对应长度模式特征值的时间非常短，基本可以忽略，算法的耗时主要是在第二次匹配上，具体时间如表1所示。表1中的数据表明，BM算法的处理时间随着模式串的增多而线性增长，比其它算法耗时多很多。AC算法在多模式匹配中非常有效，但在高速网中仍然无法满足。随着模式库中规则的增多，各种算法的处理时间也都会有所增加，但特征值算法对其不是很敏感。6. 结语基于特征值匹配算法的实质是采用二次匹配的思想，完成改变了现