Snort入侵檢測(cè)中模式匹配算法的研究和改進(jìn)

劉凱

摘要：入侵檢測(cè)系統(tǒng)Snort是一種常用的入侵檢測(cè)軟件，該文其分析系統(tǒng)的檢測(cè)引擎及其采用的模式匹配算法尤其是BM算法進(jìn)行了深入的分析和討論，在分析的基礎(chǔ)中對(duì)BM算法進(jìn)行改進(jìn)，使用一種新的模式匹配算法，以減少匹配時(shí)間，提高匹配效率，達(dá)到提高算法的平均性能和較少資源消耗的目的。

關(guān)鍵詞：入侵檢測(cè)；模式匹配；算法

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）34-8117-02

入侵檢測(cè)系統(tǒng)（Intrusion detection system，簡(jiǎn)稱“IDS”）[1]是一種對(duì)網(wǎng)絡(luò)傳輸進(jìn)行即時(shí)監(jiān)控，在發(fā)現(xiàn)可以傳輸數(shù)據(jù)時(shí)發(fā)出警報(bào)或者采取主動(dòng)反應(yīng)措施的網(wǎng)絡(luò)安全設(shè)備。

1 入侵檢測(cè)系統(tǒng)Snort

Snort[2]入侵檢測(cè)是一個(gè)基于Libpcap的輕量級(jí)入侵檢測(cè)系統(tǒng)軟件，是從著名的tcpdump軟件發(fā)展而來的。它是個(gè)基于Libpcap包的網(wǎng)絡(luò)監(jiān)視軟件，是一個(gè)十分有效的網(wǎng)絡(luò)入侵監(jiān)測(cè)系統(tǒng)。Snort入侵檢測(cè)系統(tǒng)基本由四部分組成：嗅探器，預(yù)處理器，檢測(cè)引擎，日志報(bào)警[3]。如圖1所示。

其中檢測(cè)引擎， 是 Snort 的核心部件， 主要功能是規(guī)則分析和特征檢測(cè)。當(dāng)數(shù)據(jù)包從預(yù)處理器送過來后， 檢測(cè)引擎依據(jù)預(yù)先設(shè)置的規(guī)則檢查數(shù)據(jù)包，使用某種模式匹配算法 一旦發(fā)現(xiàn)數(shù)據(jù)包中的內(nèi)容和某條規(guī)則相匹配， 就通知報(bào)警模塊。

2 單模式匹配算法研究與改進(jìn)

為了提高入侵檢測(cè)系統(tǒng)的準(zhǔn)確率，減少誤報(bào)率，在實(shí)際的入侵檢測(cè)系統(tǒng)中一般大都采用精確的模式串匹配算法。模式匹配問題分為單模式匹配算法和多模式匹配算法[4]。該文主要對(duì)單模式匹配算法（BM）進(jìn)行研究和改進(jìn)。

2.1 單模式匹配算法（BM）

僅一次在文本串中查找一個(gè)模式串出現(xiàn)的過程，稱為單模式匹配，相應(yīng)的算法稱為單模式匹配算法。目前比較常見的單模式匹配算法有KMP（Knuth-Morris-Pratt）算法，BM 算法，BMH 算法等。其中， BM 算法由于使用了啟發(fā)式搜索，采用從右向左的比較方式， 使用好后綴和壞字符來決定模式串移動(dòng)的距離，通常同時(shí)使用兩個(gè)來加快查找速度。能夠在搜索過程中跳過大部分文本，從而使執(zhí)行效率得到很大的提高，因而在 IDS 中運(yùn)用最為廣泛。

Boyer-Moore算法（簡(jiǎn)稱為BM算法）[5]是一個(gè)著名的字符串匹配算法，它把被匹配的字符串模板與匹配字符串自左向右對(duì)齊，并從字符串的最后一個(gè)字符開始自右向左進(jìn)行比較。BM算法并不是對(duì)每個(gè)字符依次進(jìn)行比較，當(dāng)出現(xiàn)不匹配的字符時(shí)，它使用兩步啟發(fā)式搜索過程來決定字符串向右移動(dòng)多少個(gè)字符繼續(xù)與文本串進(jìn)行比較，從而減少比較次數(shù)。

其中：n>m，需要從T中查找出與P完全匹配的子串，并返回該子串在正文串的首字母的位置。

BM算法采用從右向左比較 的方法，同時(shí)應(yīng)用到了兩種啟發(fā)式規(guī)則，即壞字符規(guī)則 和好后綴規(guī)則 ，來決定向右跳躍的距離。 BM算法的基本流程： 設(shè)文本串T，模式串為P。首先將T與P進(jìn)行左對(duì)齊，然后進(jìn)行從右向左比較 。若是某趟比較不匹配時(shí)，BM算法就采用兩條啟發(fā)式規(guī)則，即壞字符規(guī)則 和好后綴規(guī)則 ，來計(jì)算模式串向右移動(dòng)的距離，直到整個(gè)匹配過程的結(jié)束。

2.2 BM算法改進(jìn)

盡管BM算法是擁有高效，考慮全面，簡(jiǎn)便易懂等優(yōu)點(diǎn)，但是由于其使用了兩個(gè)數(shù)組，預(yù)處理時(shí)間較大，匹配次數(shù)較多，造成許多重復(fù)、不必要的比較，還是存在很多需要改進(jìn)的地方。

通過對(duì)BM算法的分析，我們可以發(fā)現(xiàn)，原算法雖然是用到了兩種啟發(fā)式規(guī)則，即壞字符規(guī)則和好后綴規(guī)則。但是，在算法的分析中我們看到，當(dāng)進(jìn)行字符或者字符串匹配時(shí)，大多數(shù)匹配都用到的規(guī)則是壞字符規(guī)則。因此我們可以只用壞字符規(guī)則，通過移動(dòng)量和規(guī)定字符這兩個(gè)方面對(duì)BM算法進(jìn)行一些改進(jìn)。

根據(jù)改進(jìn)算法的思想，可以對(duì)BM算法進(jìn)行如下改進(jìn)。由文本串和模式串最后一個(gè)位置對(duì)應(yīng)的字符的下一個(gè)字符做啟發(fā)向右滑動(dòng)。其作用在于在每次匹配失敗后，把模式向右滑動(dòng)的距離變大，減少了模式匹配中一些不必要的和重復(fù)的比較，縮短了模式匹配的時(shí)間。

首先，對(duì)模式串和文本串進(jìn)行分析，將文本串中文本串與模式串最后一個(gè)位置對(duì)應(yīng)的字符的下一個(gè)字符（假設(shè)為x）與模式串進(jìn)行匹配。當(dāng)字符x在模式串中不存在時(shí)，那么顯然從x開始的m個(gè)文本不可能與模式串 匹配成功，所以直接跳過，移動(dòng)距離為模式串長(zhǎng)度+1。當(dāng)x在模式串中出現(xiàn)，并且x的前一位字符也存在于模式串中。移動(dòng)模式串使字符對(duì)齊，計(jì)算偏移量。利用原BM算法進(jìn)行匹配。當(dāng)x在模式串中出現(xiàn)，但是x的前一位字符不存在于模式串中，計(jì)算移動(dòng)模式串使字符x對(duì)齊時(shí)的偏移量和原BM算法中字符不存在模式串中時(shí)的偏移量，進(jìn)行比較，取兩者中的偏移量大的進(jìn)行匹配。

2.3 算法性能比較

分別對(duì)BM算法和改進(jìn)后的BM算法進(jìn)行性能測(cè)試，用同一主程序分別調(diào)用BM算法和改進(jìn)后的BM算法進(jìn)行匹配測(cè)試，匹配算法實(shí)驗(yàn)中均插入CPU內(nèi)部時(shí)間戳進(jìn)行高精度計(jì)時(shí)，同時(shí)統(tǒng)計(jì)兩種算法在匹配時(shí)模式串向右移動(dòng)的次數(shù)。

初始條件：文本串：whiccmnxmxammm 模式串： emam

下圖是分別用BM算法和改進(jìn)后的BM算法對(duì)文本串和模式串進(jìn)行匹配后所得到的數(shù)據(jù)。

3 結(jié)論

本文以目前最著名、最活躍的、基于誤用檢測(cè)的Snort為基礎(chǔ)，針對(duì)目前應(yīng)用最廣泛的模式匹配算法BM算法的缺陷進(jìn)行改進(jìn)。但由于各個(gè)方面的局限性，該文研究還有不足和待改進(jìn)的地方?？傊?，網(wǎng)絡(luò)安全是技術(shù)問題，也是管理的問題。只有提高使用者的安全意識(shí)，合理使用網(wǎng)絡(luò)及安全工具，才能達(dá)到網(wǎng)絡(luò)的真正安全。

參考文獻(xiàn)：

[1] 蔣建春，馮登國(guó).網(wǎng)絡(luò)入侵檢測(cè)原理與技術(shù)[M].北京：國(guó)防工業(yè)出版社，2001.

[2] Brian Caswell，Jay Beale C Foster，Jeffrey Posluns.snort2.0入侵檢測(cè)[M].宋勁松，譯.北京：國(guó)防出版社，2004.

[3] Jack Koziol.Snort入侵檢測(cè)實(shí)用解決方案[M].吳薄峰，許誠(chéng)，譯.北京：機(jī)械工業(yè)出版社，2005.

[4] 李曉芳，姚遠(yuǎn).入侵檢測(cè)工具Snort的研究與使用[J].計(jì)算機(jī)應(yīng)用與軟件，2006，23（3）：123-124.

[5] 胡大輝，劉乃齊.高效的snort規(guī)則匹配機(jī)制[J].微計(jì)算機(jī)信息，2006（2）.

[6] 2009年中國(guó)互聯(lián)網(wǎng)網(wǎng)絡(luò)安全報(bào)告[R].北京：電子工業(yè)出版社，2010.

[7] 楊薇薇，廖翔.一種改進(jìn)的BM模式匹配算法[J].計(jì)算機(jī)應(yīng)用，2006（2）：64-65.endprint

摘要：入侵檢測(cè)系統(tǒng)Snort是一種常用的入侵檢測(cè)軟件，該文其分析系統(tǒng)的檢測(cè)引擎及其采用的模式匹配算法尤其是BM算法進(jìn)行了深入的分析和討論，在分析的基礎(chǔ)中對(duì)BM算法進(jìn)行改進(jìn)，使用一種新的模式匹配算法，以減少匹配時(shí)間，提高匹配效率，達(dá)到提高算法的平均性能和較少資源消耗的目的。

關(guān)鍵詞：入侵檢測(cè)；模式匹配；算法

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）34-8117-02

入侵檢測(cè)系統(tǒng)（Intrusion detection system，簡(jiǎn)稱“IDS”）[1]是一種對(duì)網(wǎng)絡(luò)傳輸進(jìn)行即時(shí)監(jiān)控，在發(fā)現(xiàn)可以傳輸數(shù)據(jù)時(shí)發(fā)出警報(bào)或者采取主動(dòng)反應(yīng)措施的網(wǎng)絡(luò)安全設(shè)備。

1 入侵檢測(cè)系統(tǒng)Snort

Snort[2]入侵檢測(cè)是一個(gè)基于Libpcap的輕量級(jí)入侵檢測(cè)系統(tǒng)軟件，是從著名的tcpdump軟件發(fā)展而來的。它是個(gè)基于Libpcap包的網(wǎng)絡(luò)監(jiān)視軟件，是一個(gè)十分有效的網(wǎng)絡(luò)入侵監(jiān)測(cè)系統(tǒng)。Snort入侵檢測(cè)系統(tǒng)基本由四部分組成：嗅探器，預(yù)處理器，檢測(cè)引擎，日志報(bào)警[3]。如圖1所示。

其中檢測(cè)引擎， 是 Snort 的核心部件， 主要功能是規(guī)則分析和特征檢測(cè)。當(dāng)數(shù)據(jù)包從預(yù)處理器送過來后， 檢測(cè)引擎依據(jù)預(yù)先設(shè)置的規(guī)則檢查數(shù)據(jù)包，使用某種模式匹配算法 一旦發(fā)現(xiàn)數(shù)據(jù)包中的內(nèi)容和某條規(guī)則相匹配， 就通知報(bào)警模塊。

2 單模式匹配算法研究與改進(jìn)

為了提高入侵檢測(cè)系統(tǒng)的準(zhǔn)確率，減少誤報(bào)率，在實(shí)際的入侵檢測(cè)系統(tǒng)中一般大都采用精確的模式串匹配算法。模式匹配問題分為單模式匹配算法和多模式匹配算法[4]。該文主要對(duì)單模式匹配算法（BM）進(jìn)行研究和改進(jìn)。

2.1 單模式匹配算法（BM）

僅一次在文本串中查找一個(gè)模式串出現(xiàn)的過程，稱為單模式匹配，相應(yīng)的算法稱為單模式匹配算法。目前比較常見的單模式匹配算法有KMP（Knuth-Morris-Pratt）算法，BM 算法，BMH 算法等。其中， BM 算法由于使用了啟發(fā)式搜索，采用從右向左的比較方式， 使用好后綴和壞字符來決定模式串移動(dòng)的距離，通常同時(shí)使用兩個(gè)來加快查找速度。能夠在搜索過程中跳過大部分文本，從而使執(zhí)行效率得到很大的提高，因而在 IDS 中運(yùn)用最為廣泛。

Boyer-Moore算法（簡(jiǎn)稱為BM算法）[5]是一個(gè)著名的字符串匹配算法，它把被匹配的字符串模板與匹配字符串自左向右對(duì)齊，并從字符串的最后一個(gè)字符開始自右向左進(jìn)行比較。BM算法并不是對(duì)每個(gè)字符依次進(jìn)行比較，當(dāng)出現(xiàn)不匹配的字符時(shí)，它使用兩步啟發(fā)式搜索過程來決定字符串向右移動(dòng)多少個(gè)字符繼續(xù)與文本串進(jìn)行比較，從而減少比較次數(shù)。

其中：n>m，需要從T中查找出與P完全匹配的子串，并返回該子串在正文串的首字母的位置。

BM算法采用從右向左比較 的方法，同時(shí)應(yīng)用到了兩種啟發(fā)式規(guī)則，即壞字符規(guī)則 和好后綴規(guī)則 ，來決定向右跳躍的距離。 BM算法的基本流程： 設(shè)文本串T，模式串為P。首先將T與P進(jìn)行左對(duì)齊，然后進(jìn)行從右向左比較 。若是某趟比較不匹配時(shí)，BM算法就采用兩條啟發(fā)式規(guī)則，即壞字符規(guī)則 和好后綴規(guī)則 ，來計(jì)算模式串向右移動(dòng)的距離，直到整個(gè)匹配過程的結(jié)束。

2.2 BM算法改進(jìn)

盡管BM算法是擁有高效，考慮全面，簡(jiǎn)便易懂等優(yōu)點(diǎn)，但是由于其使用了兩個(gè)數(shù)組，預(yù)處理時(shí)間較大，匹配次數(shù)較多，造成許多重復(fù)、不必要的比較，還是存在很多需要改進(jìn)的地方。

通過對(duì)BM算法的分析，我們可以發(fā)現(xiàn)，原算法雖然是用到了兩種啟發(fā)式規(guī)則，即壞字符規(guī)則和好后綴規(guī)則。但是，在算法的分析中我們看到，當(dāng)進(jìn)行字符或者字符串匹配時(shí)，大多數(shù)匹配都用到的規(guī)則是壞字符規(guī)則。因此我們可以只用壞字符規(guī)則，通過移動(dòng)量和規(guī)定字符這兩個(gè)方面對(duì)BM算法進(jìn)行一些改進(jìn)。

根據(jù)改進(jìn)算法的思想，可以對(duì)BM算法進(jìn)行如下改進(jìn)。由文本串和模式串最后一個(gè)位置對(duì)應(yīng)的字符的下一個(gè)字符做啟發(fā)向右滑動(dòng)。其作用在于在每次匹配失敗后，把模式向右滑動(dòng)的距離變大，減少了模式匹配中一些不必要的和重復(fù)的比較，縮短了模式匹配的時(shí)間。

首先，對(duì)模式串和文本串進(jìn)行分析，將文本串中文本串與模式串最后一個(gè)位置對(duì)應(yīng)的字符的下一個(gè)字符（假設(shè)為x）與模式串進(jìn)行匹配。當(dāng)字符x在模式串中不存在時(shí)，那么顯然從x開始的m個(gè)文本不可能與模式串 匹配成功，所以直接跳過，移動(dòng)距離為模式串長(zhǎng)度+1。當(dāng)x在模式串中出現(xiàn)，并且x的前一位字符也存在于模式串中。移動(dòng)模式串使字符對(duì)齊，計(jì)算偏移量。利用原BM算法進(jìn)行匹配。當(dāng)x在模式串中出現(xiàn)，但是x的前一位字符不存在于模式串中，計(jì)算移動(dòng)模式串使字符x對(duì)齊時(shí)的偏移量和原BM算法中字符不存在模式串中時(shí)的偏移量，進(jìn)行比較，取兩者中的偏移量大的進(jìn)行匹配。

2.3 算法性能比較

分別對(duì)BM算法和改進(jìn)后的BM算法進(jìn)行性能測(cè)試，用同一主程序分別調(diào)用BM算法和改進(jìn)后的BM算法進(jìn)行匹配測(cè)試，匹配算法實(shí)驗(yàn)中均插入CPU內(nèi)部時(shí)間戳進(jìn)行高精度計(jì)時(shí)，同時(shí)統(tǒng)計(jì)兩種算法在匹配時(shí)模式串向右移動(dòng)的次數(shù)。

初始條件：文本串：whiccmnxmxammm 模式串： emam

下圖是分別用BM算法和改進(jìn)后的BM算法對(duì)文本串和模式串進(jìn)行匹配后所得到的數(shù)據(jù)。

3 結(jié)論

本文以目前最著名、最活躍的、基于誤用檢測(cè)的Snort為基礎(chǔ)，針對(duì)目前應(yīng)用最廣泛的模式匹配算法BM算法的缺陷進(jìn)行改進(jìn)。但由于各個(gè)方面的局限性，該文研究還有不足和待改進(jìn)的地方?？傊W(wǎng)絡(luò)安全是技術(shù)問題，也是管理的問題。只有提高使用者的安全意識(shí)，合理使用網(wǎng)絡(luò)及安全工具，才能達(dá)到網(wǎng)絡(luò)的真正安全。

參考文獻(xiàn)：

[1] 蔣建春，馮登國(guó).網(wǎng)絡(luò)入侵檢測(cè)原理與技術(shù)[M].北京：國(guó)防工業(yè)出版社，2001.

[2] Brian Caswell，Jay Beale C Foster，Jeffrey Posluns.snort2.0入侵檢測(cè)[M].宋勁松，譯.北京：國(guó)防出版社，2004.

[3] Jack Koziol.Snort入侵檢測(cè)實(shí)用解決方案[M].吳薄峰，許誠(chéng)，譯.北京：機(jī)械工業(yè)出版社，2005.

[4] 李曉芳，姚遠(yuǎn).入侵檢測(cè)工具Snort的研究與使用[J].計(jì)算機(jī)應(yīng)用與軟件，2006，23（3）：123-124.

[5] 胡大輝，劉乃齊.高效的snort規(guī)則匹配機(jī)制[J].微計(jì)算機(jī)信息，2006（2）.

[6] 2009年中國(guó)互聯(lián)網(wǎng)網(wǎng)絡(luò)安全報(bào)告[R].北京：電子工業(yè)出版社，2010.

[7] 楊薇薇，廖翔.一種改進(jìn)的BM模式匹配算法[J].計(jì)算機(jī)應(yīng)用，2006（2）：64-65.endprint

摘要：入侵檢測(cè)系統(tǒng)Snort是一種常用的入侵檢測(cè)軟件，該文其分析系統(tǒng)的檢測(cè)引擎及其采用的模式匹配算法尤其是BM算法進(jìn)行了深入的分析和討論，在分析的基礎(chǔ)中對(duì)BM算法進(jìn)行改進(jìn)，使用一種新的模式匹配算法，以減少匹配時(shí)間，提高匹配效率，達(dá)到提高算法的平均性能和較少資源消耗的目的。

關(guān)鍵詞：入侵檢測(cè)；模式匹配；算法

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）34-8117-02

入侵檢測(cè)系統(tǒng)（Intrusion detection system，簡(jiǎn)稱“IDS”）[1]是一種對(duì)網(wǎng)絡(luò)傳輸進(jìn)行即時(shí)監(jiān)控，在發(fā)現(xiàn)可以傳輸數(shù)據(jù)時(shí)發(fā)出警報(bào)或者采取主動(dòng)反應(yīng)措施的網(wǎng)絡(luò)安全設(shè)備。

1 入侵檢測(cè)系統(tǒng)Snort

Snort[2]入侵檢測(cè)是一個(gè)基于Libpcap的輕量級(jí)入侵檢測(cè)系統(tǒng)軟件，是從著名的tcpdump軟件發(fā)展而來的。它是個(gè)基于Libpcap包的網(wǎng)絡(luò)監(jiān)視軟件，是一個(gè)十分有效的網(wǎng)絡(luò)入侵監(jiān)測(cè)系統(tǒng)。Snort入侵檢測(cè)系統(tǒng)基本由四部分組成：嗅探器，預(yù)處理器，檢測(cè)引擎，日志報(bào)警[3]。如圖1所示。

其中檢測(cè)引擎， 是 Snort 的核心部件， 主要功能是規(guī)則分析和特征檢測(cè)。當(dāng)數(shù)據(jù)包從預(yù)處理器送過來后， 檢測(cè)引擎依據(jù)預(yù)先設(shè)置的規(guī)則檢查數(shù)據(jù)包，使用某種模式匹配算法 一旦發(fā)現(xiàn)數(shù)據(jù)包中的內(nèi)容和某條規(guī)則相匹配， 就通知報(bào)警模塊。

2 單模式匹配算法研究與改進(jìn)

為了提高入侵檢測(cè)系統(tǒng)的準(zhǔn)確率，減少誤報(bào)率，在實(shí)際的入侵檢測(cè)系統(tǒng)中一般大都采用精確的模式串匹配算法。模式匹配問題分為單模式匹配算法和多模式匹配算法[4]。該文主要對(duì)單模式匹配算法（BM）進(jìn)行研究和改進(jìn)。

2.1 單模式匹配算法（BM）

僅一次在文本串中查找一個(gè)模式串出現(xiàn)的過程，稱為單模式匹配，相應(yīng)的算法稱為單模式匹配算法。目前比較常見的單模式匹配算法有KMP（Knuth-Morris-Pratt）算法，BM 算法，BMH 算法等。其中， BM 算法由于使用了啟發(fā)式搜索，采用從右向左的比較方式， 使用好后綴和壞字符來決定模式串移動(dòng)的距離，通常同時(shí)使用兩個(gè)來加快查找速度。能夠在搜索過程中跳過大部分文本，從而使執(zhí)行效率得到很大的提高，因而在 IDS 中運(yùn)用最為廣泛。

Boyer-Moore算法（簡(jiǎn)稱為BM算法）[5]是一個(gè)著名的字符串匹配算法，它把被匹配的字符串模板與匹配字符串自左向右對(duì)齊，并從字符串的最后一個(gè)字符開始自右向左進(jìn)行比較。BM算法并不是對(duì)每個(gè)字符依次進(jìn)行比較，當(dāng)出現(xiàn)不匹配的字符時(shí)，它使用兩步啟發(fā)式搜索過程來決定字符串向右移動(dòng)多少個(gè)字符繼續(xù)與文本串進(jìn)行比較，從而減少比較次數(shù)。

其中：n>m，需要從T中查找出與P完全匹配的子串，并返回該子串在正文串的首字母的位置。

BM算法采用從右向左比較 的方法，同時(shí)應(yīng)用到了兩種啟發(fā)式規(guī)則，即壞字符規(guī)則 和好后綴規(guī)則 ，來決定向右跳躍的距離。 BM算法的基本流程： 設(shè)文本串T，模式串為P。首先將T與P進(jìn)行左對(duì)齊，然后進(jìn)行從右向左比較 。若是某趟比較不匹配時(shí)，BM算法就采用兩條啟發(fā)式規(guī)則，即壞字符規(guī)則 和好后綴規(guī)則 ，來計(jì)算模式串向右移動(dòng)的距離，直到整個(gè)匹配過程的結(jié)束。

2.2 BM算法改進(jìn)

盡管BM算法是擁有高效，考慮全面，簡(jiǎn)便易懂等優(yōu)點(diǎn)，但是由于其使用了兩個(gè)數(shù)組，預(yù)處理時(shí)間較大，匹配次數(shù)較多，造成許多重復(fù)、不必要的比較，還是存在很多需要改進(jìn)的地方。

通過對(duì)BM算法的分析，我們可以發(fā)現(xiàn)，原算法雖然是用到了兩種啟發(fā)式規(guī)則，即壞字符規(guī)則和好后綴規(guī)則。但是，在算法的分析中我們看到，當(dāng)進(jìn)行字符或者字符串匹配時(shí)，大多數(shù)匹配都用到的規(guī)則是壞字符規(guī)則。因此我們可以只用壞字符規(guī)則，通過移動(dòng)量和規(guī)定字符這兩個(gè)方面對(duì)BM算法進(jìn)行一些改進(jìn)。

根據(jù)改進(jìn)算法的思想，可以對(duì)BM算法進(jìn)行如下改進(jìn)。由文本串和模式串最后一個(gè)位置對(duì)應(yīng)的字符的下一個(gè)字符做啟發(fā)向右滑動(dòng)。其作用在于在每次匹配失敗后，把模式向右滑動(dòng)的距離變大，減少了模式匹配中一些不必要的和重復(fù)的比較，縮短了模式匹配的時(shí)間。

首先，對(duì)模式串和文本串進(jìn)行分析，將文本串中文本串與模式串最后一個(gè)位置對(duì)應(yīng)的字符的下一個(gè)字符（假設(shè)為x）與模式串進(jìn)行匹配。當(dāng)字符x在模式串中不存在時(shí)，那么顯然從x開始的m個(gè)文本不可能與模式串 匹配成功，所以直接跳過，移動(dòng)距離為模式串長(zhǎng)度+1。當(dāng)x在模式串中出現(xiàn)，并且x的前一位字符也存在于模式串中。移動(dòng)模式串使字符對(duì)齊，計(jì)算偏移量。利用原BM算法進(jìn)行匹配。當(dāng)x在模式串中出現(xiàn)，但是x的前一位字符不存在于模式串中，計(jì)算移動(dòng)模式串使字符x對(duì)齊時(shí)的偏移量和原BM算法中字符不存在模式串中時(shí)的偏移量，進(jìn)行比較，取兩者中的偏移量大的進(jìn)行匹配。

2.3 算法性能比較

分別對(duì)BM算法和改進(jìn)后的BM算法進(jìn)行性能測(cè)試，用同一主程序分別調(diào)用BM算法和改進(jìn)后的BM算法進(jìn)行匹配測(cè)試，匹配算法實(shí)驗(yàn)中均插入CPU內(nèi)部時(shí)間戳進(jìn)行高精度計(jì)時(shí)，同時(shí)統(tǒng)計(jì)兩種算法在匹配時(shí)模式串向右移動(dòng)的次數(shù)。

初始條件：文本串：whiccmnxmxammm 模式串： emam

下圖是分別用BM算法和改進(jìn)后的BM算法對(duì)文本串和模式串進(jìn)行匹配后所得到的數(shù)據(jù)。

3 結(jié)論

本文以目前最著名、最活躍的、基于誤用檢測(cè)的Snort為基礎(chǔ)，針對(duì)目前應(yīng)用最廣泛的模式匹配算法BM算法的缺陷進(jìn)行改進(jìn)。但由于各個(gè)方面的局限性，該文研究還有不足和待改進(jìn)的地方?？傊?，網(wǎng)絡(luò)安全是技術(shù)問題，也是管理的問題。只有提高使用者的安全意識(shí)，合理使用網(wǎng)絡(luò)及安全工具，才能達(dá)到網(wǎng)絡(luò)的真正安全。

參考文獻(xiàn)：

[1] 蔣建春，馮登國(guó).網(wǎng)絡(luò)入侵檢測(cè)原理與技術(shù)[M].北京：國(guó)防工業(yè)出版社，2001.

[2] Brian Caswell，Jay Beale C Foster，Jeffrey Posluns.snort2.0入侵檢測(cè)[M].宋勁松，譯.北京：國(guó)防出版社，2004.

[3] Jack Koziol.Snort入侵檢測(cè)實(shí)用解決方案[M].吳薄峰，許誠(chéng)，譯.北京：機(jī)械工業(yè)出版社，2005.

[4] 李曉芳，姚遠(yuǎn).入侵檢測(cè)工具Snort的研究與使用[J].計(jì)算機(jī)應(yīng)用與軟件，2006，23（3）：123-124.

[5] 胡大輝，劉乃齊.高效的snort規(guī)則匹配機(jī)制[J].微計(jì)算機(jī)信息，2006（2）.

[6] 2009年中國(guó)互聯(lián)網(wǎng)網(wǎng)絡(luò)安全報(bào)告[R].北京：電子工業(yè)出版社，2010.

[7] 楊薇薇，廖翔.一種改進(jìn)的BM模式匹配算法[J].計(jì)算機(jī)應(yīng)用，2006（2）：64-65.endprint