一種基于BM 的入侵檢測優化匹配算法

李俊濤

（中共青海省委黨校，青海西寧810001）

隨著計算機網絡的迅速發展，新一代互聯網技術正全方位融入到人們的生活中，各類網絡購物、移動支付、在線政務等應用和服務發展迅猛。互聯網不斷改變著人類生活的方式，也不斷制造著各類木馬和病毒，網絡攻擊事件頻發，無不表明網絡威脅的存在。如何保證互聯網的安全，減少其負面影響，已成為一個重要話題。當前網絡安全的防御策略主要是構建包括防火墻、安全網關、訪問控制、入侵檢測等的多層次防御體系，從而提高網絡的安全性[1]。其中防火墻采用阻隔數據流量來規避威脅，入侵檢測則是主動防御，主動檢測目標網絡中的流量，對數據包進行深度分析檢測，如發現危險行為立刻報警，最大程度地提高了系統的安全性。

1 入侵檢測系統

入侵檢測的關鍵技術是對網絡流量、系統狀態和系統資源進行監控，如發現異常則進行示警，從而避免入侵行為對系統造成損害[2]。其核心思想來源于安全審計理論，首先對用戶和系統行為的可信度進行評定，以結果作為依據，來識別非法入侵行為，從而幫助管理人員來制定相應的安全策略和防范措施，確保系統的完整性、保密性和可用性[3]。

1980 年James P.Anderson 在一份報告中首次提出入侵檢測這一概念，他將未經授權故意試圖訪問信息導致系統不安全的行為闡述為入侵[4]。1987 年Dorothy E.Denning 在統計實現的基礎上，給出了一種抽象的入侵檢測模型IDES，主要由系統主體、檢測對象、特征代碼、異常活動、檢測規則、審計記錄6 部分組成[3]。后續又有學者在IDES 模型的基礎上作了進一步的改進，將檢測的重心偏向網絡數據流量方面，得到了另一種檢測系統NSM，它側重于對網絡數據流量的主動查找，探尋可疑行為，規避危險行為。

入侵檢測技術按照不同的檢查原理通常劃為基于異常的入侵檢測和基于特征的誤用檢測兩類[5]。第一類是異常檢測，它利用數據挖掘的原理，通過觀察正常的網絡流量，統計和歸納出一種特征規律并不斷更新。當系統資源的使用狀況或者用戶行為和這種特征規律相偏離時，判斷可能出現了入侵行為。它的優點在于可以抽象正常的行為，從而辨別出異常行為，其檢測方式不受經驗的限制，可以檢測出未知的攻擊，常見的算法有KNN 和Neural network 等。但是在實際的使用過程中，異常檢測效率并不高，而且耗時過長，容易出現漏報和誤報，使用上存在一定的局限性。第二類是誤用檢測，它的基本思想是用一種模式來表示入侵行為。通過分析各種不同的攻擊手段和違規操作等，創建所有可能的攻擊模式的合集和入侵特征庫。當捕捉并預處理后的網絡數據和該特征庫相匹配時，則認定發生了入侵行為。其中匹配所用時間的復雜度是影響其性能的關鍵因素。誤用檢測核心在于有效正確地建立入侵檢測模式，及時有效地更新特征庫，這樣才能保證系統的可用性。

2 Snort 入侵檢測系統

Snort 入侵檢測系統被用于各類平臺，檢測方法屬于誤用檢測，使用快捷方便，規則語言通俗易懂。該系統不僅為開發者提供了可編寫的規則原型，同時用戶也可以自行編制入侵特征庫和檢測標準。Snort 系統框架如圖1 所示。

圖1 snort 系統架構圖

捕獲器：檢測的前提基礎任務就是獲取數據包，首先將網卡更改為混雜模式，并設定中斷模式的時間伐值，降低丟包率，從而精確捕獲經過的網絡數據包；其次根據不同系統環境選擇Libpcap 或者Winpcap函數來收集數據包并分析網絡協議。

解碼器：捕捉好的數據包由解碼器進行拆解分析，目前系統授權的網絡接口有Ethernet、SLIP 等。捕獲的數據包有：以太網、令牌環、UDP、TCP/IP 等。各類數據形式各不相同，因此必須對這些具體的元素進行解碼，形成統一的可驗證格式。Snort 解碼器在不同的數據傳輸層，分別使用不同的解析函數進行解碼，按照從低到高的方式，逐層遞進直至全部完成。

預處理模塊：為了便于檢測模塊對數據進行響應，新捕捉到的數據包不能直接進行檢測匹配，而是先要進行預處理，形成統一的標準可識別的數據。預處理器可由外置插件組成，具有很強的靈活性和可擴展性，主要功能包括：對網絡數據包重組、對異常數據檢測、對網絡協議分類解碼等。

檢測引擎：系統的核心任務就是檢測，它的任務是檢測數據包中是否存在安全威脅。按照用戶設置好的規則，將標準化的數據包和特征庫進行匹配，如果發現異常，則向報警系統發出危險信號，否則丟棄數據包。系統檢測速度的快慢，取決于配置主機的性能和加載好的檢測規則數量。

日志和報警：根據檢測引擎對數據包的檢測結果，該模塊負責生成報警和記錄日志。系統的輸出方式和呈現形式靈活多樣，可以自行設置日志和警報的內容形式、保存目錄和輸出類型等。

Snort 系統在入侵檢測時，首先要進行初始化，如解析代碼命令、載入特征規則、生成三維檢測鏈表等。其次設置網卡模式，調用API 函數捕捉數據包并進行拆解分析，將分析后的數據預處理生成標準統一可用的數據。最后和特征規則庫進行比對，匹配說明有入侵行為，觸發報警輸出模塊，生成日志文件。若不匹配，則返回處理下一個數據包，如此反復循環檢測，直至所有采集到的數據包檢測完成。

隨著高速網絡時代的來臨，入侵檢測系統特征庫不斷增大，如何加快模式匹配速度、減少漏檢與誤檢的產生，是入侵檢測領域研究的一個新方向。

3 BM 算法及其改進算法

Snort 系統在各類網絡安全研究中都備受關注，其搜索檢測引擎模塊經常會被移植到各類系統平臺中。而檢測引擎的核心是模式匹配，常用的模式匹配算法有單模式和多模式。本文著重探討單模式匹配算法BM的思路與特點，并提出一種新的改進算法。

3.1 BM 算法

1977 年，Boyer 和Mooer 受KMP 算法的啟發，闡釋了一種字符串快速匹配的算法，即BM算法[3]。將兩個字符串左對齊，從模式串最右的字符與文本串對應字符進行比較，若相同則繼續向左比較；若不同，則將兩個跨躍數值進行比較，取數值大的作為模式串的右移跨躍距離，再進行下一輪比較直至完畢。算法中有壞字符規則和好后綴規則兩個函數，首先定義：P 為模式串，長度為n，P=P0P1P2...Pn-1，Pj∈∑（0≤j≤n- 1）；T 為文本串，長度為m，T=T0T1T2...Tm-1，Ti∈∑（0≤i≤m- 1）。

壞字符，在P 和T 對比的過程中，出現字符Ti和字符Pj不相同，此時可以分成兩種情況，一是Ti在模式串P 中沒有相同的字符，這時直接將模式串P 右移n 個位置繼續比較。另一種是有一樣的字符，只用考慮和Ti相同的最右邊的Pj，將模式串P 右移n- j 個位置后繼續比較。

好后綴，在對比過程中，P 與T 部分字符相同，此時可以利用已匹配的字符創建一個跨越函數，函數值表示右移距離j，移動后繼續進行下一輪的比較。當出現不匹配時分成兩種情況，一種是模式字符串Pi與模式字符Tj不匹配時,查看Tj左側靠近j 的位置有沒有模式串的一部分（Pj-s+1,...,Pn-s）與已匹配串的一部分（Pj+1,...,Pn）相同,如果相同則跨越S 個距離；再一種是沒有相同的部分,但是P 中有一個最長的前綴與已匹配串部分相同（P1,...,Pn-s）=（Ps+1,...,Pn）,則模式串向右移動S 個距離。

BM匹配算法過程中，影響其性能的關鍵因素耗時，最壞情況為全部遍歷一次,最好情況為一次匹配成功[6]。BM算法的優越性得到了許多專家和學者的認可，但仍不能滿足大吞吐量數據的匹配需求，因此BM算法有待進一步提高。

3.2 BM 的改進算法

從上述的BM算法中可以看出，模式匹配算法要提高效率，關鍵是要解決字符對比失敗以后，模式串向右跨越出的更遠距離，從而減少對比的次數，減少匹配總體耗時。本文在BM算法和其他匹配算法研究的基礎上，結合壞字符串的右移規則，只考慮模式串中存在的字符來增大右移距離，提出了一個新的算法。主要從兩方面思考，匹配窗口右側首選字符是否在模式串字符存在，如果有，是否和模式串首字符相同，以此為依據進行辨別，循環比對完成對整個文本串的檢索。算法的基本思路如下：

第一步，將P 和T 兩個字符串左邊對齊，然后從右開始順序比較，看首字符Pn-1和Tn-1是否相同，如果一致，則繼續比較次字符Pn-2和Tn-2看是否相等，直至全部匹配或者出現不匹配的字符為止。

第二步，當出現不匹配時，觀察模式串P 中是否有當前對比文本串Tn的后一位字符Ti+n，如果有則進入下一步，如果沒有則繼續查看Ti+n的后續字符，直至第s 個字符在模式字符串P 中存在，并檢查該字符Ti+n+s是否和模式串首字符P0相同。

第三步，根據上述情況判斷是否進入下一輪比對。

通過以上匹配算法分析可知，此算法可以快速全面查找文本串，相比BM 算法，增大了模式串向右跨越距離，減少了對比次數，降低了檢測的耗時，整體算法優于BM。

3.3 實例仿真驗證

為了驗證改進算法的性能，實驗使用了Snort、AppServ、adodb、ACID 等軟件，進行了兩類實驗。

實驗一：使用三臺計算機互聯，其中一臺發送隨機攻擊數據包1000 條，另一臺發送普通流量數據包，使用WinPcap 等軟件制作成合成數據包共三組，通過數據包播放器分別發送給搭載BM 算法和改進算法的檢測系統，分別記錄了兩個系統的檢測時間如表1所示。

表1 系統檢測時間對比表

對相同的攻擊數來說，檢測的時間越短，說明系統的檢測速度越快。從獲取的數據來看，BM改進后的算法比BM算法的耗時減少了約3%左右，說明改進的算法是比較成功的。

實驗二：為了進一步確定改進算法的效率，通過輸入相同的模式串和不同長度的文本串進行比較。實驗隨機選取了6 MB 和12 MB 大小的純英文文本，以“world”為模式串進行測試。通過實驗數據驗證如圖2所示。

圖2 不同算法消耗時間對比圖

改進算法無論是在匹配次數還是在耗時上都有所減少，說明改進算法在模式匹配過程中移動距離明顯提升，匹配速度有一定的提高，改進的算法是比較成功的。

4 結語

本文介紹了入侵檢測系統，對Snort 入侵檢測系統的各功能模塊進行了詳細分析說明，得出系統的重要核心是檢測模塊，該模塊的性能則取決于匹配算法的優劣。

通過對BM單模式匹配算法的學習和分析，提出了一種新的算法，該算法通過只考慮模式串中存在的字符來增大右移距離，檢測效率明顯提升。最后為了驗證新算法，部署了Snort 入侵檢測系統，通過不同實驗條件，對改進的算法進行了評測和分析，表明新的改進算法比BM算法更優，對今后高速網絡大吞吐量的入侵檢測有一定的借鑒意義。