一種基于BM 的入侵檢測優(yōu)化匹配算法

李俊濤

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

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

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

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

1980 年James P.Anderson 在一份報(bào)告中首次提出入侵檢測這一概念，他將未經(jīng)授權(quán)故意試圖訪問信息導(dǎo)致系統(tǒng)不安全的行為闡述為入侵[4]。1987 年Dorothy E.Denning 在統(tǒng)計(jì)實(shí)現(xiàn)的基礎(chǔ)上，給出了一種抽象的入侵檢測模型IDES，主要由系統(tǒng)主體、檢測對象、特征代碼、異?；顒?dòng)、檢測規(guī)則、審計(jì)記錄6 部分組成[3]。后續(xù)又有學(xué)者在IDES 模型的基礎(chǔ)上作了進(jìn)一步的改進(jìn)，將檢測的重心偏向網(wǎng)絡(luò)數(shù)據(jù)流量方面，得到了另一種檢測系統(tǒng)NSM，它側(cè)重于對網(wǎng)絡(luò)數(shù)據(jù)流量的主動(dòng)查找，探尋可疑行為，規(guī)避危險(xiǎn)行為。

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

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

Snort 入侵檢測系統(tǒng)被用于各類平臺(tái)，檢測方法屬于誤用檢測，使用快捷方便，規(guī)則語言通俗易懂。該系統(tǒng)不僅為開發(fā)者提供了可編寫的規(guī)則原型，同時(shí)用戶也可以自行編制入侵特征庫和檢測標(biāo)準(zhǔn)。Snort 系統(tǒng)框架如圖1 所示。

圖1 snort 系統(tǒng)架構(gòu)圖

捕獲器：檢測的前提基礎(chǔ)任務(wù)就是獲取數(shù)據(jù)包，首先將網(wǎng)卡更改為混雜模式，并設(shè)定中斷模式的時(shí)間伐值，降低丟包率，從而精確捕獲經(jīng)過的網(wǎng)絡(luò)數(shù)據(jù)包；其次根據(jù)不同系統(tǒng)環(huán)境選擇Libpcap 或者Winpcap函數(shù)來收集數(shù)據(jù)包并分析網(wǎng)絡(luò)協(xié)議。

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

預(yù)處理模塊：為了便于檢測模塊對數(shù)據(jù)進(jìn)行響應(yīng)，新捕捉到的數(shù)據(jù)包不能直接進(jìn)行檢測匹配，而是先要進(jìn)行預(yù)處理，形成統(tǒng)一的標(biāo)準(zhǔn)可識(shí)別的數(shù)據(jù)。預(yù)處理器可由外置插件組成，具有很強(qiáng)的靈活性和可擴(kuò)展性，主要功能包括：對網(wǎng)絡(luò)數(shù)據(jù)包重組、對異常數(shù)據(jù)檢測、對網(wǎng)絡(luò)協(xié)議分類解碼等。

檢測引擎：系統(tǒng)的核心任務(wù)就是檢測，它的任務(wù)是檢測數(shù)據(jù)包中是否存在安全威脅。按照用戶設(shè)置好的規(guī)則，將標(biāo)準(zhǔn)化的數(shù)據(jù)包和特征庫進(jìn)行匹配，如果發(fā)現(xiàn)異常，則向報(bào)警系統(tǒng)發(fā)出危險(xiǎn)信號(hào)，否則丟棄數(shù)據(jù)包。系統(tǒng)檢測速度的快慢，取決于配置主機(jī)的性能和加載好的檢測規(guī)則數(shù)量。

日志和報(bào)警：根據(jù)檢測引擎對數(shù)據(jù)包的檢測結(jié)果，該模塊負(fù)責(zé)生成報(bào)警和記錄日志。系統(tǒng)的輸出方式和呈現(xiàn)形式靈活多樣，可以自行設(shè)置日志和警報(bào)的內(nèi)容形式、保存目錄和輸出類型等。

Snort 系統(tǒng)在入侵檢測時(shí)，首先要進(jìn)行初始化，如解析代碼命令、載入特征規(guī)則、生成三維檢測鏈表等。其次設(shè)置網(wǎng)卡模式，調(diào)用API 函數(shù)捕捉數(shù)據(jù)包并進(jìn)行拆解分析，將分析后的數(shù)據(jù)預(yù)處理生成標(biāo)準(zhǔn)統(tǒng)一可用的數(shù)據(jù)。最后和特征規(guī)則庫進(jìn)行比對，匹配說明有入侵行為，觸發(fā)報(bào)警輸出模塊，生成日志文件。若不匹配，則返回處理下一個(gè)數(shù)據(jù)包，如此反復(fù)循環(huán)檢測，直至所有采集到的數(shù)據(jù)包檢測完成。

隨著高速網(wǎng)絡(luò)時(shí)代的來臨，入侵檢測系統(tǒng)特征庫不斷增大，如何加快模式匹配速度、減少漏檢與誤檢的產(chǎn)生，是入侵檢測領(lǐng)域研究的一個(gè)新方向。

3 BM 算法及其改進(jìn)算法

Snort 系統(tǒng)在各類網(wǎng)絡(luò)安全研究中都備受關(guān)注，其搜索檢測引擎模塊經(jīng)常會(huì)被移植到各類系統(tǒng)平臺(tái)中。而檢測引擎的核心是模式匹配，常用的模式匹配算法有單模式和多模式。本文著重探討單模式匹配算法BM的思路與特點(diǎn)，并提出一種新的改進(jìn)算法。

3.1 BM 算法

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

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

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

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

3.2 BM 的改進(jìn)算法

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

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

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

第三步，根據(jù)上述情況判斷是否進(jìn)入下一輪比對。

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

3.3 實(shí)例仿真驗(yàn)證

為了驗(yàn)證改進(jìn)算法的性能，實(shí)驗(yàn)使用了Snort、AppServ、adodb、ACID 等軟件，進(jìn)行了兩類實(shí)驗(yàn)。

實(shí)驗(yàn)一：使用三臺(tái)計(jì)算機(jī)互聯(lián)，其中一臺(tái)發(fā)送隨機(jī)攻擊數(shù)據(jù)包1000 條，另一臺(tái)發(fā)送普通流量數(shù)據(jù)包，使用WinPcap 等軟件制作成合成數(shù)據(jù)包共三組，通過數(shù)據(jù)包播放器分別發(fā)送給搭載BM 算法和改進(jìn)算法的檢測系統(tǒng)，分別記錄了兩個(gè)系統(tǒng)的檢測時(shí)間如表1所示。

表1 系統(tǒng)檢測時(shí)間對比表

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

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

圖2 不同算法消耗時(shí)間對比圖

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

4 結(jié)語

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

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