一種BM算法改進的研究*

朱俚治

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

?

一種BM算法改進的研究*

朱俚治

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

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

關鍵詞MMTD; 決策系統; 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引言

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

BM算法是由Boyer和Moore提出的,該算法是一種字符串匹配算法,在入侵檢測的模式匹配中有著較多的應用。入侵檢測中模式匹配技術是一種重要的檢測技術,誤用檢測就是通過模式匹配技術來發現已知的和未知的網絡攻擊行為。因此如何選擇模式匹配算法作為入侵檢測技術中的匹配算法是相當重要的,可以減少誤用檢測的漏警率和誤警率。

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

2BM算法的介紹

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

1) 匹配自右向左進行;

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

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

3MMTD算法技術簡介

3.1中介真值程度度量知識簡介

圖1中介真值程度度量一維函數圖

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

1) 如果數軸上數值點的位置逐步接近P,則事物A所具有P的屬性逐步增強。

3.2中介真值程度度量中的距離比率函數

在中介真值程度度量的方法中,數軸上某數值點通過距離比率函數來計算事物所具有屬性的強弱。

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

1) 當αF+εF

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

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

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

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

4MMTD在字符串匹配上的應用

4.1度量公式

函數:

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

1) 如果函數

2) 如果函數

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

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

根據本節中的分析討論,在本文中可以使用中介的思想對字符串的匹配進行描述和分析:

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

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

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

4.2中介對用戶行為的描述

根據4.1節中的分析討論,以下可以使用中介的思想對字符串的匹配過程進行描述和分析。

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

2) 距離比率函數

圖2中介真值程度度量一維函數的應用

相對于P的距離比率函數

通過距離比率函數hT(x)對y值的計算,如果有：

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

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

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

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

1) 兩個屬性值相同的字符串,長度可能不相同,此時字符串的匹配不成功。

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

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

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

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

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

結論:當兩個字符串相互匹配時，只有當兩個字符串的屬性值相同并且字符的長度也相同,此時字符串的匹配是成功的。

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

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

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

4.4根據MMTD算法對字符串的匹配分析和描述的結論

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

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

5粗糙集的決策系統

在實際應用中存在一大類任務:給定一組有特征描述的樣本和樣本的類別,需要通過一個學習算法從該組樣本中學習一個分類函數,實現從特征到分類的映射。粗糙集理論中稱該數據集為信息系統[3~4]。

6決策系統在度量實例匹配上的應用

由于決策條件屬性的屬性值的不同,因此能夠產生不同的決策屬性的屬性值,事實上正是由于不同的決策屬性的屬性值,才產生了不同的決策結果,這些不同的決策結果能夠將不同屬性的樣例進行有效的分類。條件屬性的屬性值決策規則的內涵是決策系統做出決策結果的重要決定因數。

6.1決策系統的參數設定:

1) 域:

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

2) 屬性集:

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

3) 值域:

V={Y,N}

6.2決策函數

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

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

6.3字符對象屬性的匹配決策表

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

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

圖3　決策表應用示意圖

說明: 1) 當字符串中的某個字符時,其屬性值為Y。

2) 當字符的匹配值為1時,其屬性值為Y,否則其屬性值為N。

3) 當字符匹配成功時,其屬性值為Y,否則其屬性值為N。

6.4決策規則

決策規則:

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

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

7改進BM算法

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

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

2) 匹配自右向左進行;

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

4) 使用粗糙集中的決策系統對匹配是否成功做出決策;

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

8結語

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

參 考 文 獻

[1] 洪龍,肖奚安,朱梧槚.中介真值程度的度量及其應用(Ⅰ)[J].計算機學報,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] 朱梧槚,肖奚安.數學基礎與模糊數學基礎[J].自然雜志,1980,7:723-726.

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

[3] 胡清華,于達仁.應用粗糙集計算[M].北京:科學出版書,2012,6.

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

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

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

[5] Tom M.Mitchell.機器學習[M].北京:機械工業出版社,2013.

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

[6] 孫文靜,錢華.改進BM算法及其在網絡入侵檢測中的應用[J].計算機科學,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].計算機應用研究,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] 楊薇薇,廖翔.一種改進的BM模式匹配算法[J].計算機應用,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] 閔聯營,趙婷婷.BM算法的研究與改進[J].武漢理工大學學報,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].計算機工程與設計,2007,28(1):29-31.

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

中圖分類號TP301.6

DOI:10.3969/j.issn.1672-9722.2016.02.005

作者簡介:朱俚治,男,工程師,研究方向:計算機科學與技術。

基金項目:北京航空航天大學軟件開發環境國家重點實驗室開放基金項目(編號:SKLSDE-2013KF-02)資助。

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