基于Snort的BM模式匹配算法的改進

姚鑫洋 古春生

摘要：近些年來，很多國家工控系統(tǒng)都遭受到了網(wǎng)絡安全攻擊，造成了巨大的經(jīng)濟損失。網(wǎng)絡入侵檢測系統(tǒng)（ NIDS）是網(wǎng)絡安全的重要組成部分之一，開源入侵檢測軟件通過活躍的社區(qū)和研究者們不斷更新來應對這快速發(fā)展的網(wǎng)絡環(huán)境。文章介紹了BoVer-Moore字符串匹配算法，并提出一種改進的BM算法，并基于Snon入侵檢測系統(tǒng)實現(xiàn)并驗證改進算法，實驗表明改進的算法提高了模式匹配效率。

關(guān)鍵詞：入侵檢測：BM算法：Snort

中圖分類號：TP393. 08

文獻標志碼：A

0 引言

隨著互聯(lián)網(wǎng)技術(shù)在工業(yè)控制系統(tǒng)（ICS）中的廣泛應用．工控系統(tǒng)被網(wǎng)絡攻擊的次數(shù)也越來越多，攻擊手段如病毒、木馬等通常會導致系統(tǒng)出現(xiàn)故障，國家一旦重要的工控系統(tǒng)出現(xiàn)損傷，影響將是巨大的。全球近些年來發(fā)生了多起工控安全事件，其中有幾起非常嚴重，如2015年烏克蘭電網(wǎng)遭“Black Energy”病毒攻擊，2017年“WannaCry”勒索病毒攻擊全球公共設施．2021年美國最大油管被黑客組織“Darkside”網(wǎng)絡攻擊并遭到勒索，這幾起安全事件都對其國家造成了巨大的經(jīng)濟損失，也警示大家需要重視-廠-控網(wǎng)絡安全問題。在網(wǎng)絡安全防護體系中，入侵檢測系統(tǒng)是繼防火墻后的另一道防線，入侵檢測的主要功能是對網(wǎng)絡和系統(tǒng)中的異常行為與攻擊進行監(jiān)測與報警。

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

入侵檢測指的是檢測計算機網(wǎng)絡中未授權(quán)的訪問。入侵一般是由其他計算機發(fā)起的，來攻擊網(wǎng)絡中的其他設備。入侵檢測系統(tǒng)（IDS）通過監(jiān)測網(wǎng)絡流量來檢測入侵行為，對未授權(quán)行為進行報警，將報警信息記錄至系統(tǒng)日志，便于后期的分析及對攻擊行為的防范[1]。

1.1入侵檢測技術(shù)

入侵檢測技術(shù)分為兩種：一是誤用入侵檢測技術(shù)，通過將入侵行為與數(shù)據(jù)庫中存儲的已知行為進行比較，當入侵行為與已知行為相匹配時，即被認定為入侵。但隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，網(wǎng)絡攻擊方式越來越多樣、數(shù)據(jù)庫不能夠及時更新等問題，導致其漏報率很高。二是異常入侵檢測技術(shù)，通過建立正常行為作為模型，尋找與之偏離的異常行為。相較于誤用入侵檢測技術(shù)，異常入侵檢測漏報率低，可以檢測出之前沒有過的入侵行為，但互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，正常行為的模型跟不上發(fā)展的速度，因此誤報率較高。雖然容易誤報，但是幾乎所有入侵行為都能被檢測到，異常入侵檢測技術(shù)的安全性大大提高。其中異常入侵檢測方法有以下3種：基于統(tǒng)計的方法、基于知識的方法、基于機器學習的方法。

1.2

Snort

Snorc是一種開源入侵檢測系統(tǒng)，主要由嗅探器、預處理器、檢測引擎和輸出模塊4個部分組成。它有3種工作方式，嗅探器模式，包記錄器模式和網(wǎng)絡入侵系統(tǒng)模式，其中入侵檢測系統(tǒng)模式最為常用。Snort通過基于規(guī)則來對系統(tǒng)進行檢測，將事先設定好的規(guī)則與監(jiān)測的流量或數(shù)據(jù)包比較，來確定是否為攻擊行為[2]。Snort規(guī)則由規(guī)則頭部和規(guī)則選項組成，規(guī)則頭部包括動作、協(xié)議、地址和端口、方向、目的地。動作：在規(guī)則觸發(fā)時，Snorc應該進行的操作；協(xié)議：告訴Snort應用的協(xié)議，如IP協(xié)議、ICMP協(xié)議等；地址和端口：指定發(fā)送的地址和端口；方向：分為單向和雙向：目的地：與地址和端口相似，但表示的為接收端。規(guī)則選項：含有一個報警信息和包的哪個部分被用來產(chǎn)生這個信息。Snort將處理過的數(shù)據(jù)包和定義好的規(guī)則進行匹配，原理是在數(shù)據(jù)包查找是否存在攻擊行為的特征，這一過程被稱作模式匹配，模式匹配算法是Snort的核心算法，匹配算法的性能決定入侵檢測的效率，入侵檢測效率越高，系統(tǒng)的安全性就越高。

2 匹配算法

入侵檢測中匹配算法分為單模式匹配算法和多模式匹配算法。單模式匹配算法是一個模式串和一個主串進行匹配，常見的單模式匹配算法有BF、KMP、BM等算法。多模式匹配算法是多個模式串和主串進行匹配，常見的多模式匹配算法有AC算法和Trie樹算法等[3]。本文對Snort入侵檢測系統(tǒng)中規(guī)則匹配所用的BM算法進行了分析并改進，改進后的算法能夠提高Snort匹配效率。

2.1

BM算法

BM算法采用從有到左的匹配方式，通過壞字符規(guī)則和好后綴規(guī)則確定移動距離[4]。首先，將T（文本串）與P（模式串）左側(cè)對齊，然后從右向左依次匹配進行比較，當出現(xiàn)不匹配的情況，通過壞字符和好后綴規(guī)則計算模式字符串向右移動的距離，直到匹配過程結(jié)束[5-6]。

2.1.1 壞字符規(guī)則

模式串P和文本串T從右至左匹配過程中，如果發(fā)現(xiàn)P的第一個字符和T的第一個字符x不匹配，將根據(jù)字符x是否出現(xiàn)在模式串P中進行討論，如圖1所示。如果出現(xiàn)，將模式串P中最靠近壞字符的第一個字符x與文本串x對齊。如果沒有出現(xiàn)，則直接向右移動，移動距離等于模式串長度。

2.1.2好后綴規(guī)則

當模式串P和文本串T從右向左依次進行匹配，匹配失敗時，有部分字符匹配成功．這些匹配成功的字符被稱作好后綴。這時對模式串P進行檢索，如果P中存在和好后綴相同的字符，則將這些字符和好后綴對齊。如果P中沒有和好后綴相同的字符，則找到和好后綴相同的最長前綴，使最長前綴與好后綴對齊，如果沒有出現(xiàn)任何相同的字符，則移動距離為模式串P本身的長度。

2.2 改進BM算法

BM算法的匹配過程：將模式串P與目標串T左邊對齊，從右邊開始匹配，匹配成功則繼續(xù)向左移動，若匹配失敗則調(diào)用好后綴規(guī)則和壞字符規(guī)則，選擇最長的移動距離來當作模式串的移動距離[7-8]。移動距離越長，匹配次數(shù)越少，檢測效率越高。在此基礎上，提出了一種改進的BM算法，改進前后算法移動如表1-2所示，移動距離分兩種情況。

（1）當調(diào)用好后綴規(guī)則時，為文本串T中的下一個字符添加判斷，判斷下一個字符串是否存在于目標串P中，如果從左到有的n個連續(xù)字符不匹配，則移動距離為n+1。

（2）當調(diào)用壞字符規(guī)則時，如果文本串T的下一個字符不存在目標串P中，則移動距離為n+1．如果下一個字符存在目標串中，則使用原本的壞字符規(guī)則來決定移動距離。

3 實驗及分析

3.1 實驗環(huán)境

實驗操作系統(tǒng)為Ubuntu 18. 04．Inter（ R） Core（TM）雙核CPU2. 30 CJHz．內(nèi)存4 GB，硬盤容量100 CB.Snort版本2.9.20．數(shù)據(jù)集DARPA1999。

實驗過程為：通過Snort的入侵檢測模式對數(shù)據(jù)集進行讀取，得到讀取時間，改變規(guī)則數(shù)目再進行讀取，記錄下時間。在mslring．c文件中將優(yōu)化后的算法替換原有的BM算法，對Snort重新進行編譯，規(guī)則數(shù)目和數(shù)據(jù)集與原保持一致，再進行讀取并記錄下時間。

3.2 實驗結(jié)果

如圖1所示，實驗中數(shù)據(jù)集個數(shù)分別為546、1526和2 100，原算法檢測時間為12. 251 s、43. 319 s和52. 298 s，改進算法檢測時間分別為9.499 s、40. 481 s和49. 955 s。實驗結(jié)果表明，改進后的算法和原算法匹配耗費時間比較有所減少，基于DARPA1999數(shù)據(jù)集，得出優(yōu)化后算法的效率提升約為6%。通過增大每次字符串比較失敗后的移動距離，能夠有效提高匹配速度，從而提升Snort入侵檢測系統(tǒng)的性能。

4 結(jié)語

隨著互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，智能家居、智能汽車不斷地普及，人們生活已離不開網(wǎng)絡，一旦網(wǎng)絡遭到攻擊，人們的生活乃至生命都會受到威脅，因此網(wǎng)絡安全需要得到大家的重視。Snorc作為開源網(wǎng)絡入侵檢測系統(tǒng)，為提高網(wǎng)絡安全做出了巨大的貢獻。匹配算法多種多樣且應用廣泛，提高匹配速度意味著提高軟件或系統(tǒng)的效率，讓它們來應對這快速發(fā)展的網(wǎng)絡。本文對Snort中BM算法進行了研究與改進，通過提高移動距離，來減少匹配次數(shù)。在Snort入侵檢測系統(tǒng)下測試，證明可以提高其規(guī)則匹配速度，提升入侵檢測效率。

參考文獻

[1]冷峰，張翠玲，陳聞宇，等．從Snorc規(guī)則的協(xié)議信息分析攻擊[J]．計算機應用，2022（ S1）：173-177.

[2]劉金龍，劉鵬，裴帥，等．基于關(guān)聯(lián)規(guī)則的網(wǎng)絡異常檢測系統(tǒng)設計與實現(xiàn)[J]．信息技術(shù)與網(wǎng)絡安全，2020（ 11）：14-22．

[3]薛芳，林麗．計算機網(wǎng)絡入侵檢測系統(tǒng)的多模式匹配算 法 [ J ] . 計算機系統(tǒng)應用 . 2021 （ 4） ： 210-215 .

[4] OJUGO A A， OYEMADE D A. Boyer Moore string-match framework for a hybrid short message service spamfiltering technique [ J ] . Intemational Journal of ArtificialIntelligence， 2021（ 3） ： 519.

[5] OJUCJO A， EBOKA A O. Signature-based malwaredetection using approximate Boyer Moore string matching{algorithm [ J ] . Internalional Journal of MathematicalSciences and Computing， 2019（ 3） ： 49-62.

[6] MELICHAR B. On modification of Boyer - Moore -horspool ' s algorithm for tree pattern matching inlinearisecl trees [ J ] . Theoretical Computer Scieru-.e ， 2020（ 830） ： 60-90.

[7]MAHAJAN A， CUPTA A， SHARMA L S.Performance evaluation of different pattern matchingalgorithms of snort [ J ] . Intemational Journal of AdvancedNenvorking and Applications， 2018（2） ： 3776-3781.

[8]jUAN L I， LINA Y. HAODAN R， et al. Researchand Improvemenr of BM Pattern Matching Algorithm[ C] 2020 International Con～erence on Artific-.ialIntelligence and Compurer Engineering

（ ICAICE ） .IEEE ， 2020 ： 204-210.