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

2011-07-09姚保峰

湖南工程学院学报（自然科学版） 2011年3期

姚保峰,王磊

(蚌埠学院计算机科学与技术系,安徽233000)

0 引言

随着Internet的快速发展,网络的安全问题显得日益突出.网络入侵已经对现有的计算机网络安全构成了巨大威胁.因此,针对网络入侵行为的入侵检测系统逐渐成为当前研究的重点.目前最常见的入侵检测系统是基于特征的入侵检测系统,这种系统基于模式匹配技术,就是通过提取已有攻击信息的特征编码成模式,然后将审计信息与该模式进行匹配,从中发现是否存在攻击行为.因而制约这种入侵检测系统性能的主要因素之一就是模式匹配算法的效率.

首先引入模式匹配算法的概念[1].模式匹配算法是指对文本串 T的一次扫描,只能处理一个模式串P,并且在匹配过程中不允许存在误配字符,即模式串P[1,…,m]中的所有字符必须和文本串 T的子串T[i,…,i+m-1](0≤i≤n-m+1)中的字符一一对应.本文首先对现有的几种典型模式匹配算法进行分析,并针对其中最优的BMH算法进行改进,最后进行仿真实验和结果分析.

1 典型算法

BF算法[2]是最简单,最直观的模式匹配算法,具体方法是从文本串的第1个字符起与模式串的第1个字符比较,若相等,则逐个比较后续字符,否则,从文本串第2个字符起重新和模式串第1个字符比较.此算法的特点是简单且容易理解,但是计算复杂度大,效率低.

KMP算法[3]的基本思想是若某趟匹配过程中文本串T中的字符T[i]和模式串P中的字符P[j]不匹配,而前j-1个字符已经匹配.此时只需右移P,T不动,即指针 i不回溯,让 P[k]与 T[i]继续比较.移动后重新开始比较的位置k仅与P有关,而与目标串(即文本串T还未进行匹配的串)无关,而k可事先确定.若令 next(j)=k,则next函数可以定义为:

KMP算法将模式串向右滑动可以提高匹配算法的效率,但相对比较复杂,且经实验证明,在部分情况下效率甚至比BF低.

BM算法[4]的基本思想是先将模式串P与文本串T左对齐.匹配从P的最右端字符开始,判断P[m]与T[m]是否匹配,如果匹配成功,则继续判断P[m-1]与T[m-1]是否匹配,循环继续下去,直到P中的字符全部匹配成功或者是有不匹配的字符出现.算法采用好后缀规则和坏字符规则分别计算划动距离并取两者的最小值.BM算法在实际的模式匹配中,跳过了很多无用的字符,这种跳跃式的比较方式,使BM算法获得了极高的效率,特别是在大字符集上进行字符串的模式匹配时.在实际的应用中,BM 算法的效率比KMP算法高出3～5倍.

BMH算法[5]只采用了BM算法的坏字符移动规则,并且将失配情况与偏移量的计算独立,不关心文本串中哪个字符造成了失配,只考虑用与模式串最右端对齐的文本字符来决定偏移量,平均情况下提高了匹配速度.

2 改进的BMH算法

改进的BMH算法采用坏字符移动规则,当发生失配时,则用与模式串P最右端对齐的文本字符及其下一字符来共同计算偏移量,即偏移量函数是取文本串 T中的每两个连续字符进行计算.设c1和c2是T中的两个连续字符,m是模式串P的长度,则偏移量函数dist可以表示为:

根据上述基本思想,我们取模式串P的最后一位字符对应的文本字符T[i]及其下一字符 T[i+1]作为一个子串.当子串在模式串P中出现时,则模式串P右移,使得该子串与它在模式串P中最右端的出现位置对齐,如图1所示;否则,当子串不在模式串P中出现时,模式串P可以右移最大值m,如图2所示.

根据改进算法偏移量函数的定义,需要每次取两个字符来计算文本串中子串的偏移量.因此,我们需要定义一个二维数组作为偏移量数组.在数组初始化时,首先将二维数组的值全部置为m;然后再根据坏字符移动规则计算文本串T中每个子串的偏移量.具体算法描述如下:

void get_dist(char p[],int m,int dist[][N])

{

int n,i,j=0;

for(i=0;i＜N;i++)

for(j=0;j＜N;j++)

dist[i][j]=m;

for(i=0;i＜m-1;i++)

dist[p[i]][p[i+1]]=m-i-1;

}

int search_BM(char t[],char p[],int dist[][N])

{

int n,m,k,sp=0;

n=strlen(t);

m=strlen(p);

if(m＞n)return-1;

k=m-1;

while(k＜n)

{

int j=m-1;

int i=k;

while(j＞=0&&t[i]==p[j])

{i--;j--;}

if(j==-1)

return i+1;

else

k=k+dist[t[k]][t[k+1]];

}

return-1;

}

3 算法分析

从BMH算法的匹配过程可以看出,BMH算法在比较时每次只取T中的一个字符和P中的一个字符进行比较,当发生失配时,以P中最后一个字符P[m]对应的文本串字符 T[i]的偏移量作为P的移动距离.这种情况下,只有当T[i]不在P中出现时,模式串才能获得最大移动距离m.从概率论的角度考虑,两个连续字符出现在模式串中的概率应远远低于一个字符出现的概率,因此,改进的BMH算法以两个连续字符计算偏移量作为P的移动距离,模式串获得最大移动距离m的概率也大的多,这样显然可以获得更高的匹配速度.

不能够取更多的连续字符(如三个)去计算偏移量的原因在于,两个连续字符出现在模式串中的几率已经很低了,采用更多的字符并不能够得到明显的几率变化,却会导致每次取字符时间的大幅增加,因而是得不偿失的.

4 算法性能测试

本实验使用的计算机硬件平台为AMD Athlon64×2 3600+处理器,2G内存,软件平台为Window s XP操作系统,VC++6.0集成开发环境.在此环境下分别对BMH和改进的BMH算法进行测试,测试程序与算法均使用C语言编写,用同一主程序分别调用这两种算法,匹配算法中使用C语言的时间函数进行高精度计时,以便显示比较结果.

随机抽取十份文本文件,分别用BMH算法和改进的BMH算法进行算法性能测试,结果如下表1所示.