基于BM算法的匹配算法的改进

对SNORT的原有规则匹配算法BM算法改进,利用规则树实现了BM算法的多模式匹配功能,在跳跃方面主要依靠于最短模式串与规则树首字符重复出现间隔距离双重控制,在首字符不匹配的情况下,移动模式串的最大距离就是前缀树中最短模式串长度,在整个匹配过程中,最大移动距离是由该前缀树中最短模式串的长度决定;而首字符匹配时,最大移动距离是由规则树首字符重复出现间隔距离决定。     

一种改进的BM算法性能分析

BM是一种基于坏符号和好后缀规则的字符匹配算法,从右向左进行字符匹配,虽然算法简单易懂,但是有一些比较是多余的,导致效率不高,因此提出一种改进的BM算法,实验数据表明,随着文本串长度的增加,模式串和文本串的比较次数以及模式串的移动次数都明显降低,算法的效率得到提高。     

Snort中字符匹配算法的分析及优化研究

分析了Snort中使用的字符串匹配BM算法, 在此基础上,着重对BM算法中字符串的比较次数和字符移动距离进行分析,通过增加遇到字符不匹配时字符串的移动距离来减少字符的比较次数,达到提高BM算法效率的目的.实验表明,优化后的算法比原算法的效率高7%左右.     

基于混合策略的单模式匹配算法

结合后缀有限自动机和正向有限自动机的优点,提出了两个单模式匹配算法.算法中,无论是后缀自动机还是正向有限自动机,只要扫描到的模式前缀长度R>0或者超过模式长度的1/2时,使用正向有限自动机继续向右进行扫描;否则都滑动m-R个字符,使用后缀自动机反向扫描模式串的前缀.两个算法的最差、最好时间复杂度分别为O(n)和O(n/m).结果表明,在短模式的情况下,两个算法的平均时间复杂度均好于RF和LDM,在小字符集长模式或大字符集短模式的情况下它们的平均性能好于BM.     

一种改进的Wu-Manber多模式串匹配算法

在分析Wu—Manber算法的基础上，结合QS算法思想，设计了一种改进的多模式串匹配算法：QWM（quick Wu—Manber）．算法充分利用紧邻当前窗口之后的B字符块，使算法的最大移动距离由原来的（m—B＋1）增大至（m＋B），平均移动距离也得到很大提高．同时对QWM算法和Wu-Manber算法进行了实验对比，无论模式串数量和最小长度怎么变化，性能都有较大提升．实验表明，改进的算法在对英文文本进行扫描时有4％～13％的提高．     

IBM算法及其在Snort系统下的实现

入侵检测系统匹配算法是影响检测效率的关键,为进一步提高系统性能和检测效率,对Snort系统采用的BM算法进行了改进,提出了IBM算法.该算法以两个字符为单位计算右移量,增大了文本串的滑动距离,有效地减少了匹配次数;将IBM算法应用于Snort,并在Windows平台下实现了基于改进算法的Snort系统.实验结果表明,该系统能够有效地检测各种攻击,与原系统相比检测效率有了明显的提高.     

BM模式匹配算法的研究与改进

本文在分析传统模式匹配BF算法、KMP算法和BM算法的基础上,提出对BM算法的改进.主要针对BM算法中模式串向右滑动距离进行改进,BM算法和改进后的BM算法在同等条件下,分别调用各自算法的滑动距离函数,实验结果可以看出改进后的BM算法查找效率、查找次数等均优于BM算法.     

单模跳跃算法的分析与改进

为改进串匹配的效率,通过引入有效载荷,对Horspool算法进行了分析。在字符集较小而模式串长度较大时,跳跃距离受字符集大小限制严重。结合好后缀思想,提出了基于好后缀的Horspool算法GsHor:比较窗口内对应末位字符相同的情况下使用好后缀距离移动窗口;结合Quick Search思想,提出了基于坏字符块的Horspool算法BcbHor。实验表明:字符集大小为4时,GsHor算法的比较次数比Horspool算法减小18%以上,BcbHor算法至少减少42.4%。     

一种改进的Sunday模式匹配算法

字符匹配效率是很多计算机应用系统的性能瓶颈,研究设计高效的匹配算法有助于提高相应系统的应用性能。在分析典型Sunday匹配算法的基础上,对其进行了较为有效的改进。改进算法在字符串匹配前先计算模式串的倒序特征值,也就是以此计算出模式串的最后s个字符在本模式串中倒序除自己以外的下一次出现的位置。每一次字符匹配都采用倒序匹配并利用这种匹配的结果,匹配结果结合倒序特征值可以直接决定特征串的下一次位移数。在进行完一次字符匹配后,采用增加一个遍历字符的Sunday算法来遍历模式串以计算下一次位移数,以此尽可能地排除无效匹配。实验结果表明改进算法的效率比Sunday算法有一定提高。     

一种快速的单模式匹配算法

在分析了BM算法以及一些重要的改进算法的基础上,提出一种新的改进算法—Y_BMHS 算法.该算法利用辅助的二维数组,考虑了文本串后间隔的两位字符和模式串首字符的唯一性,使 得最大位移提升到m+3,出现概率也显著提高,加快了匹配速度.实验证明Y_BMHS算法比BM、 BMH、BMHS等算法有更好的性能.