基于入侵检测系统snort的BM模式匹配算法研究与改进

大专

38计算机安全2009.2

学术技术

1引言

随着互联网技术的飞速发展对计算机网络的攻击已经

变成了严重的问题。 作为主要安全防范手段的防范

火墙在许多方面还存在弱点。 入侵检测系统(IDS ) [1]

能够自动监视网络数据流和主机日志等，迅速发现

攻击提供对可疑事件的检测和响应，从而导致入侵检测地

位被强调。 关于最常见的入侵监视系统snort，经

经过实验发现，模式匹配是入侵监测系统的瓶颈[4]。

如何提高入侵检测算法的模式匹配速度已成为当今的学术

行业研究的热点课题。 本文关于单模式匹配时的模式匹配

运用算法，进行调查分析，结果表明英语文章中出现了大量的词根词

拼写的特点，提出了改进的思想。 经过数学期望值的论证

及根据实验数据数据确认[1]，可知确实提高了模式匹配

的效率提高了入侵检测系统的功能。

2 BM算法及分析

B o y - M o e o r算法是一种有名的单模式匹配计算

法，之后几乎所有的入侵检测模式匹配算法都在其中

在基础上发展起来了。 该算法的基本原理是：先对模式

串p进行预处理，计算两个偏移函数：badchar(Charch )

和Goodsuffix (； 然后，将图案列和文本从右向左对齐

进行匹配； 如果文本字符和模式字符不匹配，则根据函数

badchar(Charch )和Goodsuffix )计算偏移值，两者中

的大的一方作为shift的值，将图案p向右移动shift文字，

接着进行从右到左的匹配，如果匹配成功，则输出。 B M算法

分为预处理阶段和检索阶段。

(1)预处理阶段：预处理阶段主要为计算

badchar(Charch )和Goodsuffix )这两个偏移函数的值。

badchar(charch )函数计算字符集中的每个字符对

来修改选定线条的属性。 在某个字符在模式p中出现了多次情况下

在最右边的位置确定偏移，公式表示为：

Goodsuffix ) )后缀移动。 移动是相对于图案的子列进行的。

在模式预处理的过程中，算法发现p中含有字符.

子字符串。 用t查找此子字符串的下一个出现位置。 把p

移动到该位置，将部分字符串与t的对应部分字符串对齐[2]。

)2)在搜索阶段：模式p和文本t不一致情况下

使用不好的文字移动和好的后缀的移动函数计算跳跃值，取两者之间

的较大值[3]。

基于入侵检测系统snort的

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

王浩1、周晓峰2

(1)河南大学计算机与信息工程学院，河南开封475004； 2 .黄河水利职业技术学院，河南开封475004 )

摘要：首先分析了入侵检测系统中最常见的B M模式匹配算法，并在此基础上提出了改进B M模式匹配算法，经过

统计分析表明，针对英语文章具有词根、词缀的特点，该算法有效地减少了这种情况下的匹配时间，提高了匹配效率。

关键词： snort； BM模式匹配算法； 入侵检测系统

researchandimprovementofbmpatternmatchingalgorithmbasedinstrusion

检测系统停止

王昊1

、周小峰2

(1. departmentofcomputerscienceandtechnologycollege，Henan university，Kaifeng，Henan 475004，China；

2.yellowriverconservancytechnicalinstitute，Kaifeng，Henan 475004，China )

abstract 3360 weanalysedthemostwidelyusedbmpatternmatchingalgorithmoninstrusiondectionsystematthebegining，and then，animprovimproving

patternmatchingalgorithmwasgiven.onanalyzingthepostfixprofileofenglishthesis，theimprovedalgorithmreducedthematchingtime

arised the efficiency of it。

Key words: snort； BM pattern matching algorithm； ins trusion检测系统

2009.2计算机安全39

学术技术

BM算法的主要程序代码如下。

教学资源库

计算BadChar和GoodSuf； //预处理

int j=0；

while(j=n-m ) )。

a t t e m p t s；//计算尝试次数for (inti=m-1；

i=0pat[i]==txt[i j]； I----)

if(I==-1 )//匹配成功

j=GoodSuf[0]；

记录一致信息；

else

j=max(goodsuf[I]，bad char [ y [ I j ] )-m1i )；

end if

end for

end while

B M算法是目前实际应用中最常用、效率高的单一

模式匹配算法之一。 其特点是采用由后往前的比较方式，

然后采用好后缀和坏文字两种启发方式进行智能启发跳跃

跳跃B M算法的空间复杂度为o(m)，其预处理阶段的

时间复杂度为o(m)，在最佳情况下为BM算法的时间

复杂度可以达到o(n/m )。

3一种改进的BM算法

通过研究B M算法，在进行模式匹配时，

有这样的情况。

例如，如果匹配英语字符串conscientious，则

如果模式列delicious一致，就会发生这种情况。

图1 BM算法的匹配过程

因为英语字大多带有后缀，所以如图1所示

ious，13日到10日一致后，发现9日的一致失败了

因此，如果匹配到13号，就可以马上转移到某个合适的位

不是按顺序的12号、11号放。 那么，怎样找到这个一致呢

合适的位置是？ 是本文的主要工作。

在图1中，第一次进行匹配，直接匹配第9位、马

匹配失败了。 查一下不好的文字表，跳到第13位进行第二次匹配

好的，对准13号的位置，然后对准12号、11号、10号。 那么匹配

4个后发现9号对位不成功。 怎样才能减少呢

12号、11号、10号不必要的匹配减少，匹配效率提高

怎么样？ 完全随机时，12位出现任意字符x

(x 字符集) )的概率全部为q。 但是根据实践统计

英语单词中经常出现后缀，u出现在第12位的概率必须明确

明显高于其他文字。 因此，13日达成一致后，就不应该在

不是对准12号，而是对准对应的首字母的位置(5号)，

检查的效率大幅提高。

算法的主要思想流程如图2所示。

图2算法流程

模式匹配引擎改进的主要步骤如下。

比根

i=0；

u=0；

shift=m；

while i=n-m do

j=m -i；

if i=0 and p[j]==t[i j] do

j=j-1；

endif

end while

if j0

=j-1；

then

输出(I 1；

高等职业教育是什么学历

shift=goodsuffix(0；

u=m-shift；

else

v=m-i-j；

shift=u -v；

shift=max(badchar(t[Ij] )-m 1 j，goodsufix(j )，turbo

_shift；

if(shift==goodshift(j ) )

40计算机安全2009.2

学术技术

u=min(m-shift )、

Ifturbo==shift{badchar(t(Ij )一m r j ) ) ) ) ) ) ) ) ) ) Ifturbo==shift{badchar(t(Ij )一m r j ) ) ) )

shift=max{shift，u}

endif

4改进算法分析

分析该算法，第一个字符匹配成功后，分析第二个字符

从出现文字的数学期望入手，比较算法改进前后，得出第二点

字符的数学期望值，进一步改进的算法比原算法更现实

在际模式匹配中，确实提高了匹配的效率。 在BM算法中，

在12号地址中任意一个字符x(x字符集)的概要

率为q，这是随机出现的，所以每个字符大概都是

率均相同，为q，数学期望值为q。

BM算法：

E1=xdisT1(x ) q，) x是指针I处

指文字)

从统计上看，在改进算法中，第二比较的文字是

是对应模式列的第一个字符，是匹配成功的概率

匹配互补必须远远小于不成功的概率，相应的数学期望。

因此，理论上，从比较算法开始，前后第二个字符的

从数学期望值的观点来看，确实提高了匹配的效率。

5试验结果

测试数据由麻省理工学院林肯研究所开发

“D A R P A1999入侵检测数据集”。 此数据集包含封面

介绍了P r o b e、D o S、R2L、U2R和Data等5类58种典型

型攻击方式是目前最全面的攻击测试数据集。 一样的

时，作为研究领域公认且广泛使用的基准评价数据集，

D A R P A 1999评估数据集是新提出的入侵检测算法及其

他的算法之间的比较提供了可能性。

递增规则以检测数据。 先把五十个不成文的句子

此检测规则用于检测数据，然后每次添加10条文本检测

规则。 从图3中可以看出，性能得到了一定程度的改善，B M算法

与改进BM算法的执行时间之比为1.1-1.26。

图3试验结果

参考文献：

[1]李洋、王康、谢萍. BM模式匹配改进算法[J] .计算机可

研究，2004，21 (4) : 58 - 59。

[2]BOYER RS，Moore js.afaststringsearchingalgorithm [ j ]

. Communications of the ACM，1977，20 (10 ) : 762 - 772。

[3] horspoolrn.practicalfastsearchinginstrings [ j ].software -

Practice and Experience，1980，10 (6) : 501 - 506

[4]杨薇薇，廖翔.一种改进的BM模式匹配算法计算机

2006、26(2)用：317-319。

作者简介：王浩(1983-)，男，河南大学计算机与信息工

程学院研究生，研究方向：网络安全、入侵检测等周晓峰

(1979-)，男，黄河水利职业技术学院，助教，研究方向：

密码学、高等数学研究与教学等。

受理日期： 2008-06-27

的验证，其阈值在0.01 ~ 0.02之间应该可以获得理想的效果

水果。 具体的尺寸由图像的性质决定，在纹理复杂的图像中

如果阈值设定得较大，在背景和图像都很平滑的图像中，我们会

Roberts运算符本身适合于设置较小的阈值

为了有陡峭边缘的图像而决定。 在有噪声的图像中

中，如果不进一步增大该阈值，则无法获得理想的效果。 例如，有噪声时

的woman图中选择的阈值为0.1。 其实，我们

如果只对原始图像嵌入水印，并进行嵌入区域选择

此时，如果该阈值大大超过0.02，则该图像为否定的

不是原创的作品。

参考文献：

[1]李秀艳.一种基于奇异值分解和HVS的数字水印算法，大

海事大学硕士学位论文2004.03

[2]靳中鑫.数字图像信息处理，国防工业出版社，2003 6-7.

[3]王炳锡，陈琦，邓峰森.数字水印技术，西安电子科技大学

学习出版社，2003.11，18-2226-55。

[4]基于频率、陈健.奇异值分解的抗几何失真数字水印

算法，中国影像图形学报，2004.09，4 ) :507-512。 陈二雷，研

研究生，助教，山东工商学院计算机科学与技术学院。

受理日期： 2008-09-18

(接第37页)