一種BM算法改進(jìn)的研究*

朱俚治

(南京航空航天大學(xué)信息中心　南京　210016)

?

一種BM算法改進(jìn)的研究*

朱俚治

(南京航空航天大學(xué)信息中心南京210016)

摘要在當(dāng)今的互聯(lián)網(wǎng)中黑客攻擊事件頻頻發(fā)生,為了阻止黑客攻擊網(wǎng)絡(luò)事件的發(fā)生從而保證網(wǎng)絡(luò)的安全性,需要能夠檢測(cè)出網(wǎng)絡(luò)用戶行為的某種算法。在入侵檢測(cè)技術(shù)中,模式匹配算法是一種重要的檢測(cè)算法,該種算法能夠檢測(cè)已知和未知的網(wǎng)絡(luò)攻擊行為。目前模式匹配算法有多種,其中字符串匹配算法也屬于一種模式匹配算法,字符串匹配算法在入侵檢測(cè)中有著廣泛的應(yīng)用。經(jīng)典的字符串匹配算法有BM算法和KMP算法,論文為了提高和改進(jìn)BM算法在字符匹配時(shí)的速度,將MMTD算法和粗糙集中的決策系統(tǒng)在BM算法中進(jìn)行應(yīng)用,這是論文的創(chuàng)新點(diǎn)。論文改進(jìn)BM算法的思路是首先使用MMTD算法對(duì)字符串的屬性值進(jìn)行衡量,然后再使用決策系統(tǒng)對(duì)該字符串中字符匹配是否成功做出決策。論文提出的算法在一定程度上能夠提高BM算法的匹配速度。

關(guān)鍵詞MMTD; 決策系統(tǒng); BM算法

Study on the Improvement of BM Algorithm

ZHU Lizhi

(Information Center, Nanjing University of Aeronautics and Astronautics, Nanjing210016)

AbstractIn today’s internet hacker attacks occur frequently, in order to prevent hacker attacks, network event occurs so as to ensure the security of the network. Therefore, it is necessary to detect a algorithm of network user behavior. In intrusion detection, pattern matching algorithm is an important detection algorithm, which can detect known and unknown network attacks. At present, there are many kinds of pattern matching algorithms, and the string matching algorithm is a pattern matching algorithm, and the string matching algorithm has a wide application in intrusion detection. Classical string matching algorithm includes KMP algorithm and BM algorithm, in order to improve the speed of BM algorithm in the character matching speed. Therefore, the MMTD algorithm and rough set decision system are used in the BM algorithm, which is the innovation of this paper. In this paper, the MMTD algorithm is used to measure the attribute value of the string, and then the decision system is used to make a decision on whether the string is successful or not. The algorithm proposed in this paper can improve the matching speed of BM algorithm to a certain extent.

Key WordsMMTD, decision system, BM algorithm

Class NumberTP301.6

1引言

當(dāng)今模式匹配算法有很多,其中最著名的兩個(gè)是KMP算法和BM算法。這兩種算法具有較高匹配效率,在最壞情況下均具有線性的搜索時(shí)間[6~8]。在算法的匹配速度方面BM算法比KMP算法具有更快的速度和更高的字符匹配效率[6~8]。字符串匹配算法具有更快的匹配速度是人們重點(diǎn)研究的方向之一。BM改進(jìn)算法都是以改進(jìn)算法的匹配速度為目標(biāo)。

BM算法是由Boyer和Moore提出的,該算法是一種字符串匹配算法,在入侵檢測(cè)的模式匹配中有著較多的應(yīng)用。入侵檢測(cè)中模式匹配技術(shù)是一種重要的檢測(cè)技術(shù),誤用檢測(cè)就是通過(guò)模式匹配技術(shù)來(lái)發(fā)現(xiàn)已知的和未知的網(wǎng)絡(luò)攻擊行為。因此如何選擇模式匹配算法作為入侵檢測(cè)技術(shù)中的匹配算法是相當(dāng)重要的,可以減少誤用檢測(cè)的漏警率和誤警率。

在BM算法中具有較高的字符匹配速度,本文為了近一步提高BM算法的字符匹配速度和匹配效率,本文將MMTD算法在BM算法中進(jìn)行首次的應(yīng)用,這是本文的創(chuàng)新點(diǎn)之一。在本文提出的改進(jìn)算法之中,首先使用了MMTD算法對(duì)字符串的屬性值進(jìn)行衡量。如果字符串的屬性值匹配成功,則再進(jìn)行字符串中的字符匹配。如果字符串的屬性值匹配不成功,則不再進(jìn)行字符的匹配。通過(guò)字符串屬性的匹配之后,再進(jìn)行字符的匹配,可以縮小字符串匹配的范圍,提高BM算法在字符串匹配時(shí)的速度和效率。在本文中將粗糙集中的決策系統(tǒng)在BM算法中進(jìn)行應(yīng)用,這也是本文的創(chuàng)新點(diǎn)之一。

2BM算法的介紹

BM算法的具體匹配是從P的右端向左進(jìn)行,進(jìn)行中考察比較并考慮文本中可能出現(xiàn)的字符在模式中的位置,該算法的基本思想是[6~10]:

1) 匹配自右向左進(jìn)行;

2) 若匹配失敗發(fā)生在Pj≠Ti,且Ti不出現(xiàn)在模式T中,則將模式右移直到P1位于匹配失敗位Ti的右邊第一位(即Ti+1位),若T1在P中有若干地方出現(xiàn),則應(yīng)選擇j=max{K|Pk=Ti};

3) 若模式P后面K位和文本T中一致的部分有一部分在T中其他地方出現(xiàn),則可以將T向右移,直接使這部分對(duì)齊,且要求一致部分盡可能的大。

3MMTD算法技術(shù)簡(jiǎn)介

3.1中介真值程度度量知識(shí)簡(jiǎn)介

圖1中介真值程度度量一維函數(shù)圖

對(duì)數(shù)軸y=f(x)表示的含義有以下說(shuō)明[1~2]:

1) 如果數(shù)軸上數(shù)值點(diǎn)的位置逐步接近P,則事物A所具有P的屬性逐步增強(qiáng)。

3.2中介真值程度度量中的距離比率函數(shù)

在中介真值程度度量的方法中,數(shù)軸上某數(shù)值點(diǎn)通過(guò)距離比率函數(shù)來(lái)計(jì)算事物所具有屬性的強(qiáng)弱。

定理1給定y=f(x)∈f(X),ξ(h(y))=h(y),則有[1~2]：

1) 當(dāng)αF+εF

2) 當(dāng)y>αT+εT時(shí),gT(x)>1;當(dāng)y<αF-εF時(shí),gF(x)>1;

3) 當(dāng)y<αF-εF時(shí),gT(x)<0;當(dāng)y>αT+εT時(shí),gF(x)<0;

4)gT(x)+gF(x)=1。

(1)相對(duì)于P的距離比率函數(shù)[1~2]

4MMTD在字符串匹配上的應(yīng)用

4.1度量公式

函數(shù):

說(shuō)明:函數(shù)y=f(x)的含義是需要匹配的字符串偏離被匹配字符串的程度。

1) 如果函數(shù)

2) 如果函數(shù)

討論: 1) 如果函數(shù)y=f(x)的值越小,則需要匹配的字符串屬性值偏離被匹配的字符串的程度越小,那么字符串的相似程度就越高。這時(shí)字符串匹配程度部分好部分差,那么需要匹配的字符串可以向某個(gè)方向進(jìn)行搜索匹配。

2) 如果函數(shù)y=f(x)的值越大,則需要匹配的字符串屬性值偏離被匹配的字符串的程度就越大。如果偏離值越大,那么字符串的相似程度就越差。

根據(jù)本節(jié)中的分析討論,在本文中可以使用中介的思想對(duì)字符串的匹配進(jìn)行描述和分析:

結(jié)論: 1) 如果偏離函數(shù)y=f(x)值為0,則表示字符串的屬性值匹配成功,匹配程度好。

2) 如果偏離函數(shù)y=f(x)值不為0,偏離值越小,則表示字符串屬性值的匹配程度部分好部分差。

3) 如果偏離函數(shù)y=f(x)值不為0,偏離值越大,則表示字符串屬性值的匹配程度就越差。

4.2中介對(duì)用戶行為的描述

根據(jù)4.1節(jié)中的分析討論,以下可以使用中介的思想對(duì)字符串的匹配過(guò)程進(jìn)行描述和分析。

1) 中介邏輯對(duì)字符串的匹配

2) 距離比率函數(shù)

圖2中介真值程度度量一維函數(shù)的應(yīng)用

相對(duì)于P的距離比率函數(shù)

通過(guò)距離比率函數(shù)hT(x)對(duì)y值的計(jì)算,如果有：

(1)若函數(shù)hT(x)=1,y值落在區(qū)域(αl-εl,αl+εl),則代表匹配程度好。

(2)若函數(shù)hT(x)=0,y值落在區(qū)域(αr-εr,αr+εr),則代表匹配程度差。

4.3字符串匹配的討論和分析

在字符串的匹配過(guò)程中如果匹配成功,那么這兩個(gè)字符串的屬性值之和必然相等。

1) 兩個(gè)屬性值相同的字符串,長(zhǎng)度可能不相同,此時(shí)字符串的匹配不成功。

分析:現(xiàn)在存在兩個(gè)需要匹配的字符串A與B,字符串A中含有字符a與b,其屬性值分別為8和3。

字符串B中含有字符c、d、e,其屬性值分別為4、5、2。

從上面可以知道字符串的屬性值之和是相等的,但這時(shí)字符串的匹配是不成功的。

2) 長(zhǎng)度相同的字符串,字符串的屬性值未必相同。

3) 如果兩個(gè)字符串的屬性值不相同,但長(zhǎng)度相同,那么在某個(gè)字符串中必定有某個(gè)字符的屬性值不同。

結(jié)論:當(dāng)兩個(gè)字符串相互匹配時(shí)，只有當(dāng)兩個(gè)字符串的屬性值相同并且字符的長(zhǎng)度也相同,此時(shí)字符串的匹配是成功的。

1) 字符串的匹配如果是成功的,那么這兩個(gè)字符串的屬性值之和是相等的。

2) 字符串的匹配如果不成功,那么這兩個(gè)字符串的屬性值之和一定不相等。

3) 如果兩個(gè)匹配的字符串屬性值相等,這兩個(gè)字符串匹配不一定成功。

4.4根據(jù)MMTD算法對(duì)字符串的匹配分析和描述的結(jié)論

1) 如果字符串的屬性值匹配成功,則使用粗糙集中的決策系統(tǒng)進(jìn)行該字符串中的字符進(jìn)行匹配。

2) 如果字符串的屬性值匹配不成功,則無(wú)需進(jìn)行該字符串中的字符匹配。

5粗糙集的決策系統(tǒng)

在實(shí)際應(yīng)用中存在一大類任務(wù):給定一組有特征描述的樣本和樣本的類別,需要通過(guò)一個(gè)學(xué)習(xí)算法從該組樣本中學(xué)習(xí)一個(gè)分類函數(shù),實(shí)現(xiàn)從特征到分類的映射。粗糙集理論中稱該數(shù)據(jù)集為信息系統(tǒng)[3~4]。

6決策系統(tǒng)在度量實(shí)例匹配上的應(yīng)用

由于決策條件屬性的屬性值的不同,因此能夠產(chǎn)生不同的決策屬性的屬性值,事實(shí)上正是由于不同的決策屬性的屬性值,才產(chǎn)生了不同的決策結(jié)果,這些不同的決策結(jié)果能夠?qū)⒉煌瑢傩缘臉永M(jìn)行有效的分類。條件屬性的屬性值決策規(guī)則的內(nèi)涵是決策系統(tǒng)做出決策結(jié)果的重要決定因數(shù)。

6.1決策系統(tǒng)的參數(shù)設(shè)定:

1) 域:

U={x1,x2,x3,…,xn},其中x1,x2,x3,…,xn分別表示等待匹配的每個(gè)字符。

2) 屬性集:

A={a1,a2,a3},其中a1表示字符串中某個(gè)字符的屬性值,a2表示字符的匹配值,a3表示字符的匹配是否成功。

3) 值域:

V={Y,N}

6.2決策函數(shù)

1) 如果f(x)=1,那么由決策系統(tǒng)做出決策的這次字符匹配是成功的,決策屬性值為Y。

2) 如果f(x)≠1,那么由決策系統(tǒng)做出決策的這次字符匹配是不成功的,決策屬性值為N,則將模式右移直到P1位于匹配失敗位Ti的右邊第一位(即Ti+1位)。

6.3字符對(duì)象屬性的匹配決策表

在一個(gè)決策系統(tǒng)中如果把每一條樣例的條件屬性值部分作為規(guī)則的前件,把決策屬性值部分作為規(guī)則的后件,那么每一條樣例都可以看成一條規(guī)則[3~4]。在決策系統(tǒng)中每一條樣例都對(duì)應(yīng)著一條具體的決策規(guī)則。在以下的決策表中可將決策屬性分為條件屬性和決策屬性[3~4]。信息系統(tǒng)中的屬性集合可以分成兩部分,一部分為條件屬性集合,另一部分為決策屬性,這種信息系統(tǒng)通常稱為決策系統(tǒng)或決策表[3~4]。

在以下的系統(tǒng)決策表中,條件屬性是: 1)a1表示某個(gè)字符的屬性值。 2)a2表示字符的匹配值。決策屬性:a3表示字符的匹配是否成功。

圖3　決策表應(yīng)用示意圖

說(shuō)明: 1) 當(dāng)字符串中的某個(gè)字符時(shí),其屬性值為Y。

2) 當(dāng)字符的匹配值為1時(shí),其屬性值為Y,否則其屬性值為N。

3) 當(dāng)字符匹配成功時(shí),其屬性值為Y,否則其屬性值為N。

6.4決策規(guī)則

決策規(guī)則:

1) (某個(gè)字符,Y)∧(字符的匹配值,Y)?(字符的匹配,Y)。

2) (某個(gè)字符,Y)∧(字符的匹配值,N)?(字符的匹配,N)。

7改進(jìn)BM算法

改進(jìn)BM算法的具體匹配是從P的右端向左進(jìn)行,進(jìn)行中考察比較并考慮文本中可能出現(xiàn)的字符在模式中的位置,該算法的基本思想是:

1) 使用MMTD算法對(duì)字符串屬性值的匹配程度好與壞做出衡量;

2) 匹配自右向左進(jìn)行;

3) 若匹配失敗發(fā)生在Pj≠Ti,且Ti不出現(xiàn)在模式T中,則將模式右移直到P1位于匹配失敗位Ti的右邊第一位(即Ti+1位),若T1在P中有若干地方出現(xiàn)在,則應(yīng)選擇j=max{K|Pk=Ti};

4) 使用粗糙集中的決策系統(tǒng)對(duì)匹配是否成功做出決策;

5) 若模式P后面K位和文本T中一致的部分,有一部分在T中其他地方出現(xiàn),則可以將T向右移,直接使這部分對(duì)齊,且要求一致部分盡可能的大。

8結(jié)語(yǔ)

BM算法和KMP算法是兩種經(jīng)典的字符串匹配算法,BM算法有多種改進(jìn)型算法[6~10],改進(jìn)算法具有更快的字符匹配速度,因此BM算法是一種有效和實(shí)用性強(qiáng)的算法,同時(shí)也是一種高效的智能性算法。本文的作者在查閱了BM算法和一些字符串匹配算法之后,提出將MMTD算法和粗糙集中決策系統(tǒng)與BM相互結(jié)合在一起,形成一種改進(jìn)型BM算法。本文提出的改進(jìn)型BM算法具有一定的智能性,在某種程度上可以提高BM算法在字符匹配時(shí)的速度和效率,將MMTD算法和決策系統(tǒng)在BM算法中進(jìn)行應(yīng)用是本文的創(chuàng)新點(diǎn)。

參 考 文 獻(xiàn)

[1] 洪龍,肖奚安,朱梧槚.中介真值程度的度量及其應(yīng)用(Ⅰ)[J].計(jì)算機(jī)學(xué)報(bào),2006(12):2186-2193.

HONG Long, XIAO Xi’an, ZHU Wujia. Intermediary true value measurement and its application level (Ⅰ)[J]. Chinese Journal of Computers,2006(12):2186-2193.

[2] 朱梧槚,肖奚安.數(shù)學(xué)基礎(chǔ)與模糊數(shù)學(xué)基礎(chǔ)[J].自然雜志,1980,7:723-726.

ZHU Wujia, XIAO Xi’an. With fuzzy mathematics[J]. Journal Nature Mathematical Foundation,1980,7:723-726.

[3] 胡清華,于達(dá)仁.應(yīng)用粗糙集計(jì)算[M].北京:科學(xué)出版書(shū),2012,6.

HU Qinghua, YU Daren. Application of rough set calculation of[M]. Beijing: Scientific Publishing Books,2012,6.

[4] 陳德剛.模糊粗糙集理論與方法[M].北京:科學(xué)出版社,2013,11.

CHEN Degang. The theory and method of fuzzy rough set[M]. Beijing: Science Press,2013,11.

[5] Tom M.Mitchell.機(jī)器學(xué)習(xí)[M].北京:機(jī)械工業(yè)出版社,2013.

Tom M.Mitchell. Machine learning[M]. Beijing: Machinery Industry Press,2013.

[6] 孫文靜,錢(qián)華.改進(jìn)BM算法及其在網(wǎng)絡(luò)入侵檢測(cè)中的應(yīng)用[J].計(jì)算機(jī)科學(xué),2013,40(12):174-176.

SUN Wenjing, QIAN Hua. The improved BM algorithm and its application in computer science [J]. Computer Science,2013,40(12):174-176.

[7] 李洋,王康,謝萍,等.BM模式匹配改進(jìn)算法[J].計(jì)算機(jī)應(yīng)用研究,2004,21(4):58-59.

LI Yang, WANG Kang, XIE Ping. The Improving Algorithm of BM[J]. Application Research of Computers,2004,21(4):58-59.

[8] 楊薇薇,廖翔.一種改進(jìn)的BM模式匹配算法[J].計(jì)算機(jī)應(yīng)用,2006,26(2):318-319.

YANG Weiwei, LIAO Xiang. Improved pattern matching algorithm of BM[J]. Journal of Computer Applications,2006,26(2):318-319.

[9] 閔聯(lián)營(yíng),趙婷婷.BM算法的研究與改進(jìn)[J].武漢理工大學(xué)學(xué)報(bào),2006,30(3):528-530.

MIN Lianying, ZHAO Tingting. Research and improvement of BM[J]. Journal of Wuhan University of Technology,2006,30:528-530.

[10] 巫喜紅,凌捷.BM模式匹配算法剖析[J].計(jì)算機(jī)工程與設(shè)計(jì),2007,28(1):29-31.

MIN Xihong, LING Jie. Anatomy of BM pattern matching algorithm[J]. Computer Engineering and Design,2006,30:528-530.

中圖分類號(hào)TP301.6

DOI:10.3969/j.issn.1672-9722.2016.02.005

作者簡(jiǎn)介:朱俚治,男,工程師,研究方向:計(jì)算機(jī)科學(xué)與技術(shù)。

基金項(xiàng)目:北京航空航天大學(xué)軟件開(kāi)發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金項(xiàng)目(編號(hào):SKLSDE-2013KF-02)資助。

*收稿日期:2015年8月10日,修回日期:2015年9月24日