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

基于特征值的多模式匹配算法 【摘要】 高速网是当今网络发展的必然趋势，采用现行匹配算法的入侵检测系统(IDs)很难在高速网中有效地运行。本文主要从特征值的多模式匹配算法、模式库的组织和逻辑实现这三个方面来大幅度地提高系统检测速率，完全适应于高速网络的入侵检测。 【关键词】入侵检测 特征值 模式匹配 多模式匹配 引言 入侵检测是对网络或系统进行监视，发现各种攻击的企图，行为或攻击结果，采取相应的响应措施以保护系统资源的机密性、完整性和可用性。根据入侵检测系统对数据分析方法的不同，可将其分为两大类：异常入侵检测和误用入侵检测。误用入侵检测?是当前的主流，它的核心是规则库的组织和模式匹配算法。但随着网络速度的迅速提高，规则库的日益增大，误用入侵检测暴露出其致命缺陷：检测速率太低，在一个满负荷的lOOM 以太网上，将不得不丢掉30％一75％ 的网络数据包[2J，这将漏掉对许多可疑数据包的检测，严重影响了系统检测的准确性。 基于特征值匹配算法的思想 在入侵检测系统中，字符串匹配消耗了大量的系统资源(主要是CPU资源)，严重制约着系统检测速率的提高。当前常用的匹配算法主要有：KMP算法 BM 算法等。这些算法都有一个共同特点：一次性准确匹配。它们的思想是在数据包中对模式字符串直接匹配，若不匹配则根据某种启发式策略跳过一定量字符后接着匹配。 在实际高速网络中未发生带宽类型攻击的情况下，真正的入侵数据包只占网络总流量的较少一部分。系统资源的消耗主要不是在对入侵数据包的检测，而是对正常数据包的穷举匹配。针对这一实际的情况，本文提出了基于特征值的快速匹配算法。 定义1 特征值：一个字符串经过某种简单运算而得到的一个值，这个值称为该字符串的特征值，用T标志。一般而言，字符串和特征值可能存在多对一的关系，即一个字符串有且仅有一个特征值，而多个字符串以一定概率对应于同～特征值。我们的目的就是选择合适的简单运算，尽可能的降低不同字符串对应相同特征值的概率。基于特征值匹配算法的基本思想是：把数据包中字符串的特征值与等长模式字符串的特征值相比较，若不等则两个串肯定不匹配若相等则两个字符串以极大概率匹配，需要进行第二次匹配确认。简单地说，就是采取两次匹配的方法，首先过滤掉大量肯定不匹配的字符串，接着进行第二次准确匹配。第一次匹配算法要求简单，由硬件直接实现，以减轻CPU 的负担， 而且要能过滤掉绝大多数正常数据包。首次匹配是关键所在，这里主要详细探讨基于特征值的第一次匹配算法。 设模式字符串 S={S1,S2,S3,…,Sm},长度为m，特征值为r。数据包字符串P={P1,P2,…,Pm}，长度为n。首先求出数据包中长为n的字符串{P1,P2,…,Pm}的特征值，然后与模式字符串的特征值T相比较，若相等则进行第二次匹配，否则两个字符串肯定不匹配，数据包字符串P往右平移一个字符继续匹配{P2,P3,…,Pm+1}。平移后的特征值可以由平移前的值经过简单运算得到，这一过程支持硬件实现。 为了提高系统的并行度，可以采用分组匹配的方法。首先把数据包分成┌n/m┐个组，每组长度为m，然后用硬件同时计算各组的特征值，把特征值与模式字符串的特征值相比较，若相等则进行第二次匹配，否则同时往右平移一个字符继续匹配，总共只需平移m次便可完成整个匹配计算过程。 特征值的计算方法 特征值的计算方法有多种，但它们应符合以下几点要求：(1)计算简单，能由硬件电路直接实现，以减轻CPU负担。(2)能过滤掉大量的正常数据包，也就是说，和同一特征值对应的字符串应较少。(3)平移后的特征值可以由平移前的特征值经过简单运算得出，以减少特征值的计算次数。 定义2 位向量：在一个字符串中，取每个字符相同位上的比特按字符顺序构成的二进制串称为位向量。任何一个长为m的字符串有且仅有8个长为Be／的位向量，例如字符串“GOOD”中各个字符的ASCII码为0100111101000100}，取每个字符的最低位构成的位向量为{l110}。该字符串共有8个长为4的位向量，分别是{0000、l1l1、0000、0000、0110、l1l1、l110、l110}。根据位向量求出的特征值称为位特征值，用t．标志。8个位特征值组成该字符串的特征值T,T=[t7、t6、t5、t4、t3、t2、t1、t0] 定义3 过滤率：第一次匹配过滤的正常数据包量与总流量的比值称为过滤率，一般要求第一次匹配的过滤率越高越好。当网络中没有入侵包时，准确匹配算法的过滤率是100%。 异或求值法 字符串中各个字符通过异或即可得到该字符串的异或特征值。为不失一般性，设字符串为{S1,S2,…,Sm}，则该字符串的特征值 { S1⊕S2⊕S3…⊕Sm }，共8个比特。例如，模式字符串“CMD