劉凱

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

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

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2014）34-8117-02

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

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

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

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

2 單模式匹配算法研究與改進

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

2.1 單模式匹配算法（BM）

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

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

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

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

2.2 BM算法改進

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

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

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

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

2.3 算法性能比較

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

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

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

3 結(jié)論

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

參考文獻：

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

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

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

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

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

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

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

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

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

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2014）34-8117-02

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

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

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

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

2 單模式匹配算法研究與改進

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

2.1 單模式匹配算法（BM）

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

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

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

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

2.2 BM算法改進

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

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

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

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

2.3 算法性能比較

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

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

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

3 結(jié)論

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

參考文獻：

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

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

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

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

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

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

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

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

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

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2014）34-8117-02

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

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

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

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

2 單模式匹配算法研究與改進

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

2.1 單模式匹配算法（BM）

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

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

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

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

2.2 BM算法改進

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

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

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

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

2.3 算法性能比較

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

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

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

3 結(jié)論

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

參考文獻：

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

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

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

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

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

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

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