姚保峰,王 磊

(蚌埠學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系,安徽233000)

0 引 言

隨著Internet的快速發(fā)展,網(wǎng)絡(luò)的安全問(wèn)題顯得日益突出.網(wǎng)絡(luò)入侵已經(jīng)對(duì)現(xiàn)有的計(jì)算機(jī)網(wǎng)絡(luò)安全構(gòu)成了巨大威脅.因此,針對(duì)網(wǎng)絡(luò)入侵行為的入侵檢測(cè)系統(tǒng)逐漸成為當(dāng)前研究的重點(diǎn).目前最常見(jiàn)的入侵檢測(cè)系統(tǒng)是基于特征的入侵檢測(cè)系統(tǒng),這種系統(tǒng)基于模式匹配技術(shù),就是通過(guò)提取已有攻擊信息的特征編碼成模式,然后將審計(jì)信息與該模式進(jìn)行匹配,從中發(fā)現(xiàn)是否存在攻擊行為.因而制約這種入侵檢測(cè)系統(tǒng)性能的主要因素之一就是模式匹配算法的效率.

首先引入模式匹配算法的概念[1].模式匹配算法是指對(duì)文本串 T的一次掃描,只能處理一個(gè)模式串P,并且在匹配過(guò)程中不允許存在誤配字符,即模式串P[1,…,m]中的所有字符必須和文本串 T的子串T[i,…,i+m-1](0≤i≤n-m+1)中的字符一一對(duì)應(yīng).本文首先對(duì)現(xiàn)有的幾種典型模式匹配算法進(jìn)行分析,并針對(duì)其中最優(yōu)的BMH算法進(jìn)行改進(jìn),最后進(jìn)行仿真實(shí)驗(yàn)和結(jié)果分析.

1 典型算法

BF算法[2]是最簡(jiǎn)單,最直觀的模式匹配算法,具體方法是從文本串的第1個(gè)字符起與模式串的第1個(gè)字符比較,若相等,則逐個(gè)比較后續(xù)字符,否則,從文本串第2個(gè)字符起重新和模式串第1個(gè)字符比較.此算法的特點(diǎn)是簡(jiǎn)單且容易理解,但是計(jì)算復(fù)雜度大,效率低.

KMP算法[3]的基本思想是若某趟匹配過(guò)程中文本串T中的字符T[i]和模式串P中的字符P[j]不匹配,而前j-1個(gè)字符已經(jīng)匹配.此時(shí)只需右移P,T不動(dòng),即指針 i不回溯,讓 P[k]與 T[i]繼續(xù)比較.移動(dòng)后重新開始比較的位置k僅與P有關(guān),而與目標(biāo)串(即文本串T還未進(jìn)行匹配的串)無(wú)關(guān),而k可事先確定.若令 next(j)=k,則next函數(shù)可以定義為:

KMP算法將模式串向右滑動(dòng)可以提高匹配算法的效率,但相對(duì)比較復(fù)雜,且經(jīng)實(shí)驗(yàn)證明,在部分情況下效率甚至比BF低.

BM算法[4]的基本思想是先將模式串P與文本串T左對(duì)齊.匹配從P的最右端字符開始,判斷P[m]與T[m]是否匹配,如果匹配成功,則繼續(xù)判斷P[m-1]與T[m-1]是否匹配,循環(huán)繼續(xù)下去,直到P中的字符全部匹配成功或者是有不匹配的字符出現(xiàn).算法采用好后綴規(guī)則和壞字符規(guī)則分別計(jì)算劃動(dòng)距離并取兩者的最小值.BM算法在實(shí)際的模式匹配中,跳過(guò)了很多無(wú)用的字符,這種跳躍式的比較方式,使BM算法獲得了極高的效率,特別是在大字符集上進(jìn)行字符串的模式匹配時(shí).在實(shí)際的應(yīng)用中,BM 算法的效率比KMP算法高出3～5倍.

BMH算法[5]只采用了BM算法的壞字符移動(dòng)規(guī)則,并且將失配情況與偏移量的計(jì)算獨(dú)立,不關(guān)心文本串中哪個(gè)字符造成了失配,只考慮用與模式串最右端對(duì)齊的文本字符來(lái)決定偏移量,平均情況下提高了匹配速度.

2 改進(jìn)的BMH算法

改進(jìn)的BMH算法采用壞字符移動(dòng)規(guī)則,當(dāng)發(fā)生失配時(shí),則用與模式串P最右端對(duì)齊的文本字符及其下一字符來(lái)共同計(jì)算偏移量,即偏移量函數(shù)是取文本串 T中的每?jī)蓚€(gè)連續(xù)字符進(jìn)行計(jì)算.設(shè)c1和c2是T中的兩個(gè)連續(xù)字符,m是模式串P的長(zhǎng)度,則偏移量函數(shù)dist可以表示為:

根據(jù)上述基本思想,我們?nèi)∧Ｊ酱甈的最后一位字符對(duì)應(yīng)的文本字符T[i]及其下一字符 T[i+1]作為一個(gè)子串.當(dāng)子串在模式串P中出現(xiàn)時(shí),則模式串P右移,使得該子串與它在模式串P中最右端的出現(xiàn)位置對(duì)齊,如圖1所示;否則,當(dāng)子串不在模式串P中出現(xiàn)時(shí),模式串P可以右移最大值m,如圖2所示.

根據(jù)改進(jìn)算法偏移量函數(shù)的定義,需要每次取兩個(gè)字符來(lái)計(jì)算文本串中子串的偏移量.因此,我們需要定義一個(gè)二維數(shù)組作為偏移量數(shù)組.在數(shù)組初始化時(shí),首先將二維數(shù)組的值全部置為m;然后再根據(jù)壞字符移動(dòng)規(guī)則計(jì)算文本串T中每個(gè)子串的偏移量.具體算法描述如下:

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算法的匹配過(guò)程可以看出,BMH算法在比較時(shí)每次只取T中的一個(gè)字符和P中的一個(gè)字符進(jìn)行比較,當(dāng)發(fā)生失配時(shí),以P中最后一個(gè)字符P[m]對(duì)應(yīng)的文本串字符 T[i]的偏移量作為P的移動(dòng)距離.這種情況下,只有當(dāng)T[i]不在P中出現(xiàn)時(shí),模式串才能獲得最大移動(dòng)距離m.從概率論的角度考慮,兩個(gè)連續(xù)字符出現(xiàn)在模式串中的概率應(yīng)遠(yuǎn)遠(yuǎn)低于一個(gè)字符出現(xiàn)的概率,因此,改進(jìn)的BMH算法以兩個(gè)連續(xù)字符計(jì)算偏移量作為P的移動(dòng)距離,模式串獲得最大移動(dòng)距離m的概率也大的多,這樣顯然可以獲得更高的匹配速度.

不能夠取更多的連續(xù)字符(如三個(gè))去計(jì)算偏移量的原因在于,兩個(gè)連續(xù)字符出現(xiàn)在模式串中的幾率已經(jīng)很低了,采用更多的字符并不能夠得到明顯的幾率變化,卻會(huì)導(dǎo)致每次取字符時(shí)間的大幅增加,因而是得不償失的.

4 算法性能測(cè)試

本實(shí)驗(yàn)使用的計(jì)算機(jī)硬件平臺(tái)為AMD Athlon64×2 3600+處理器,2G內(nèi)存,軟件平臺(tái)為Window s XP操作系統(tǒng),VC++6.0集成開發(fā)環(huán)境.在此環(huán)境下分別對(duì)BMH和改進(jìn)的BMH算法進(jìn)行測(cè)試,測(cè)試程序與算法均使用C語(yǔ)言編寫,用同一主程序分別調(diào)用這兩種算法,匹配算法中使用C語(yǔ)言的時(shí)間函數(shù)進(jìn)行高精度計(jì)時(shí),以便顯示比較結(jié)果.

隨機(jī)抽取十份文本文件,分別用BMH算法和改進(jìn)的BMH算法進(jìn)行算法性能測(cè)試,結(jié)果如下表1所示.

表1 兩種匹配算法性能測(cè)試情況

從圖3和圖4可以看出,IBMH算法無(wú)論是在完成匹配時(shí)模式串的右移次數(shù)上,還是在匹配中消耗的時(shí)間上,都具有一定的優(yōu)勢(shì).

5 結(jié)束語(yǔ)

改進(jìn)的BMH算法取文本串中的兩個(gè)連續(xù)字符計(jì)算偏移量,使模式串以最大移動(dòng)量右移的幾率得到增加.實(shí)驗(yàn)結(jié)果表明,該算法能夠有效的減少字符串匹配的次數(shù),提高了模式匹配的速度.

[1]曾慧惠,袁世忠,胡 鵬.入侵檢測(cè)系統(tǒng)中高效模式匹配算法的研究[J].計(jì)算機(jī)應(yīng)用與軟件,2008,25(4):226-227.

[2]周延森,汪永好.王 磊.入侵檢測(cè)系統(tǒng)模式匹配算法研究[J].計(jì)算機(jī)工程與設(shè)計(jì).2008,29(7):1652-1654,1683.

[3]張國(guó)平,徐汶東.字符串模式匹配算法的改進(jìn)[J].計(jì)算機(jī)工程與設(shè)計(jì),2007,(10):4881-4884.

[4]Boyer RS,Moore J S.A Fast String Searching Algorithm[J].Communications of ACM,1977,20(10):762-772.

[5]Horspool R N.Practical Fast Searching in Strings[J].Software-practics&Experience,1990(10):501-506.