基于snort的入侵检测系统的研究(14)

4 基于改进匹配算法的snort的设计

4.1 snort的匹配算法及缺陷

4.1.1 BM 算法

BM算法[15]是入侵检测系统中应用最广泛的一种单模式匹配算法。Snort 2.0以前的版本主要采用BM算法进行数据包和规则的内容模式的匹配。2.0及以后的版本中BM算法应用的较少，但它是现行版本中多模式匹配算法的基础。

BM算法的基本思想是字符从右到左进行比较，模式串从左到右移动。假设模式串P=p0p1 pm-1,文本串T=t0t1 tn-1。开始时使p0与t0对齐，判断pm-1与tm-1是否相等，如果相等则向左移动判断pm-2与tm-2是否相等，直到全部匹配成功或发现有不匹配的情况出现。当出现不匹配时，BM算法采用坏字符规则和好后缀规则计算模式串右移的距离。右移的距离由两条规则中较大的值决定。对于P在T中位置i处的尝试，也就是比较模式串P=p0p1 pm-1与T中子titi+1ti+m-1是否相等。若前m-j-1次比较成功完成，而在第m-j次比较时出现不匹配，即ti+j+1ti+j+2 ti+m-1=pj+1pj+2 pm-1=u并且ti+j=a，pj=b（a≠b）。在这种情况下根据坏字符和好字符规则如下：

① 坏字符规则：在 p0p1 pj-1中自右向左查找字符 t

i+j出现的第一个位置，若找到则使 ti+j与该字符对齐，若没有找到则将 P 移动到 ti+j后的第一个位置对齐，既使 p0与 ti+j+1对齐，继续匹配。

②好后缀规则：从 pj处开始从右到左查找 u 串，若能找到 u 串并且其前一字符不是 a，则将 P 移动到该 u 串与 T 中已匹配的 u 串对齐的位置。若没有找到这样的 u 串，则在 T 中 u 的后缀中查找与 P 的前缀相同的最长子串 v，若存在这样的串 v，移动 P 使 T 的后缀 v 与 P 的前缀 v 对齐。如果这样的u 串与 v 串均未找到，将 P 右移 m 个字符。即使 p0与 ti+m对齐，继续匹配。BM算法匹配过程如图4-1所示：

尽管 BM 算法在单模式匹配中执行效率较高，但是 Snort 在检测入侵时数据包需要与上千条规则进行匹配，此时需重复多遍执行 BM 算法，制约了系统运行速率。而且BM算法主要利用了正文串的信息 ，对模式串的信息使用的很少，其实模式串的内容信息还可以进行挖掘，如果利用的好，可以在一定程度上提升算法的效率。

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新高等教育基于snort的入侵检测系统的研究(14)全文阅读和word下载服务。