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

跳过尽可能多的字符以进行下一轮的匹配，且降低了匹配次数。不考虑算法的预处理过程，主要以匹配过程中所需的匹配次数作为算法的时耗。改进的Sunday算法在最坏的情况下所需的字符比较次数小于2N。这是因为，假设匹配至T[i]时，head_string匹配成功，则T[i]之前的(i-1)个字符最多比较(i-I)次，而其后得(N-i+1)个正文字符每个字符最多会比较2次，1次是匹配foot_string时进行的，1次是foot_string匹配失败后，重新匹配head_string时进行的。

4.2.2 模式匹配过程

确定首字符串head_string后，我们也就得到了尾字符串foot_string，foot_string=P-headstring，接着就可以应用Sunday算法进行模式匹配了。匹配过程如图4-4所示：

假设模式串P为{America}，文本串为{He is from Amersfoort, he likes America}，根据确定首字

符串的算法可知，head_string=Amer，foot_string=ica。匹配流程图如图4-5所示：

在第三次移动时，出现首字符串Amer匹配的情况，此时用尾字符串ica进行相应位置到字符匹配，发现匹配失败，于是首字符串移动到尾字符串匹配失败的地方进行下一轮匹配。利用Sunday算法进行第八次移动时，又发生了首字符串匹配的情况，而此时尾字符串也与相应位置的字符匹配成功，至此模式匹配成功。

图4-4 模式匹配过程

图4-5 模式匹配流程图

4.3改进匹配算法的snort实现

我们把改进的 Sunday 算法应用到 snort 系统，首先设文本串为 T(k)，长度为n；模式串为 P，长度为 o，真首子串为 H(j),长度 m，尾子串 F(i),长度为 o-m。算法流程如图4-6所示：

根据流程图，改进的Sunday 算法使每一次匹配不成功后都能跳过尽可能多的字符以进行下一轮的匹配，且降低了匹配次数。从而大大提高了snort处理数据包的速度。

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