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