资源描述：
《基于特征值的多模式匹配算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、基于特征值的多模式匹配算法1!【摘要】高速网是当今网络发展的必然趋势，采用现行匹配算法的入侵检测系统(IDs)很难在高速网屮冇效地运行。本文主耍从特征值的多模式匹配算法、模式库的组织和逻辑实现这三个方面來大幅度地提高系统检测速率，完全适应于高速网络的入侵检测。【关键词】入侵检测特征值模式匹配多模式匹配1.引言入侵检测是对网络或系统进行监视，发现各种攻击的企图，行为或攻击结果,采取相应的响应措施以保护系统资源的机密性、完整性和可用性。根据入侵检测系统对数据分析方法的不同，可将其分为两大类：异常入侵检测和误用入侵检测。误用入侵检测…是当前的主流，它的核心是规则库的组织和模式匹配算法。但随着网络
2、速度的迅速提高，规则库的日益增大，误用入侵检测暴露出其致命缺陷：检测速率太低，在一个满负荷的100M以太网上，将不得不丢掉30%—75%的网络数据包［2J,这将漏掉对许多可疑数据包的检测，严重影响了系统检测的准确性。2.基于特征值匹配算法的思想在入侵检测系统中，字符串匹配消耗了大量的系统资源(主要是CPU资源)，严重制约着系统检测速率的捉高。当前常用的匹配算法主要冇：KMP算法BM算法等。这些算法都有一个共同特点：一次性准确匹配。它们的思想是在数据包中对模式字符串直接匹配，若不匹配则根据某种启发式策略跳过一定量字符后接着匹配。在实际高速网络中未发牛带宽类型攻击的情况下，真正的入侵数据包只占
3、网络总流量的较少一部分。系统资源的消耗主要不是在对入侵数据包的检测，而是对止常数据包的穷举匹配。针对这一实际的情况，木文提出了基于特征值的快速匹配算法。定义1特征值：一个字符串经过某种简单运算而得到的一个值，这个值称为该字符串的特征值，用丁标志。一般而言，字符串和特征值可能存在多对一的关系，即一个字符串冇冃仅冇一个特征值，而多个字符串以一定概率对应于同〜特征值。我们的口的就是选择合适的简单运算，尽可能的降低不同字符串对应相同特征值的概率。基丁•特征值匹配算法的基本思想是：把数据包屮字符串的特征值与等长模式字符吊的特征值相比较，若不等则两个串肯定不匹配若相等则两个字符串以极大概率匹配，需要进
4、行第二次匹配确认。简单地说，就是采取两次匹配的方法，首先过滤掉大量肯定不匹配的字符串，接着进行第二次准确匹配。第一次匹配算法要求简单，由硕件直接实现，以减轻CPU的负担，而月.要能过滤掉绝大多数止常数据包。首次匹配是关键所在，这里主要详细探讨基于特征值的第一次匹配算法。设模式字符串S二｛Si,S2,S3,…,S」，长度为m,特征值为门数据包字符串P=｛PbP2,-,Pb｝,长度为n。首先求出数据包中长为n的字符串｛PbP2,-,Pb｝的特征值，然后与模式字符串的特征值T相比较，若相等则进行第二次匹配，否则两个字符申肯定不匹配，数据包字符申P往右平移一个字符继续匹配心,匕,…,P边鳥平移后的
5、特征值可以由平移前的值经过简单运算得到，这一过程支持硬件实现。为了提高系统的并行度，可以采用分组匹配的方法。首先把数据包分成rn/mn个组，每组长度为ni，然后用硕件同时计算各组的特征值，把特征值与模式字符申的特征值相比较，若相等则进行第二次匹配，否则同时往右平移一个字符继续匹配，总共只需平移m次便可完成整个匹配计算过程。1.特征值的计算方法特征值的计算方法有多种，但它们应符合以下儿点要求：（1）计算简单，能由硕件电路直接实现，以减轻CPU负担。（2）能过滤掉大量的正常数据包，也就是说，和同一特征值对应的字符审应较少。（3）平移后的特征值可以由平移前的特征值经过简单运算得出，以减少特征值的
6、计算次数。定义2位向量：在一个字符串屮，取每个字符相同位上的比特按字符顺序构成的二进制串称为位向量。任何一个长为m的字符串有且仅有8个长为Be/的位向量，例如字符串“GOOD”中各个字符的ASCII码为｛01000111、01001111、01001111、01000100｝,取每个字符的最低位构成的位向量为｛1110｝。该字符串共有8个长为4的位向量，分别是｛0000、1111、0000、0000、0110、1111、1110、1110｝o根据位向量求出的特征值称为位特征值，用t.标志。8个位特征值组成该字符串的特征值T,T=[t7>t6>t5>t4>t3>t2、b、t0]定义3过滤率：
7、第一次匹配过滤的正常数据包量与总流量的比值称为过滤率，一般要求第一次匹配的过滤率越高越好。当网络中没有入侵包时，准确匹配算法的过滤率是100%。异或求值法字符串中各个字符通过异或即可得到该字符串的异或特征值。为不失一般性，设字符串为｛sbS2,SJ,则该字符串的特征值｛Si㊉S2㊉S3…㊉3｝,共8个比特。例如，模式字符串“CMD”中各字符对应的ASCII码为｛01000011、01010111、01001101｝,它的
