資源描述：
《入侵檢測系統(tǒng)中模式匹配算法的研究》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、入侵檢測系統(tǒng)中模式匹配算法的研究摘要?入侵檢測是網(wǎng)絡(luò)安全的最后一道防線，模式匹配算法是基于特征匹配的入侵檢測系統(tǒng)中的核心算法，模式匹配的效率決定這類入侵檢測系統(tǒng)的性能。本文對入侵檢測系統(tǒng)中的模式匹配算法進(jìn)行了綜述，包括經(jīng)典的單模式匹配算法--KMP算法、BM算法、RK算法和多模式匹配AC算法。對各種算法的性能進(jìn)行了分析。最后提出了改進(jìn)模式匹配算法效率的研究方向。關(guān)鍵詞:網(wǎng)絡(luò)安全；入侵檢測；模式匹配；多模式匹配1引言???隨著Internet應(yīng)用的普及，網(wǎng)絡(luò)安全問題也日益突出。入侵是指試圖破壞資源的完整性、可用性和保密性的活動的集合。作為防火墻之后網(wǎng)絡(luò)安全的最后一道防線，入侵檢測系統(tǒng)（
2、IDS）是指檢測上述行為的活動，識別出未經(jīng)授權(quán)或越權(quán)訪問系統(tǒng)資源的行為的軟硬件系統(tǒng)。由于入侵檢測系統(tǒng)可以在一定程度上主動預(yù)防和檢測出來自系統(tǒng)內(nèi)、外部的入侵，并作出適當(dāng)響應(yīng)，動態(tài)改變網(wǎng)絡(luò)的安全性，因此入侵檢測的研究正成為網(wǎng)絡(luò)安全研究的熱點(diǎn)。???根據(jù)采用的分析技術(shù)入侵檢測分為誤用檢測和異常檢測[1]。誤用檢測根據(jù)已知的攻擊方法，預(yù)先定義入侵模式，通過判斷這些模式是否出現(xiàn)來完成檢測任務(wù)。異常檢測是指根據(jù)用戶的行為或資源的使用狀況的正常程度來判斷是否屬于入侵。由于異常檢測的誤檢率和漏檢率高，因此目前大多數(shù)入侵檢測系統(tǒng)產(chǎn)品均屬誤用檢測。誤用檢測中使用的檢測技術(shù)主要有：模式匹配、專家系統(tǒng)、狀態(tài)
3、轉(zhuǎn)移等，而其中因?yàn)槟Ｊ狡ヅ湓砗唵?、可擴(kuò)展性好而最為常用，例如著名開放源碼的入侵檢測系統(tǒng)Snort就是基于模式匹配的。???由此可見，模式匹配算法的性能直接影響入侵檢測系統(tǒng)的檢測效率。在高速網(wǎng)絡(luò)環(huán)境，如果模式匹配算法來不及處理大量的實(shí)時(shí)網(wǎng)絡(luò)數(shù)據(jù)包，必然會丟棄部分?jǐn)?shù)據(jù)包，而這些被丟棄的數(shù)據(jù)包中就可能包含入侵信息。本文以下部分介紹幾種著名的模式匹配算法，包括單模式匹配算法和多模式匹配算法，為設(shè)計(jì)入侵檢測系統(tǒng)選擇模式匹配算法提供指導(dǎo)。2單模式匹配算法???模式匹配是指在給定長度為n的文本串T=T[1]T[2]…T[n]中查找長度為m的模式串P=P[1]P[2]…P[m]的第一次出現(xiàn)的過程。
4、這里T[i]（1≤i≤n），P[j]（1≤j≤m）∈∑（字符集），若在T中能找到P的出現(xiàn)，則稱匹配成功，否則稱匹配失敗。???一次只能在文本串中對一個(gè)模式串進(jìn)行匹配的算法，稱為單模式匹配算法，可同時(shí)對多個(gè)模式串進(jìn)行匹配的算法稱多模式匹配算法。???平凡的模式匹配算法（BF算法）中，一趟匹配失敗后，T只后移一個(gè)字符，所以算法簡單，但效率低。高效的模式匹配算法都是設(shè)法增大不匹配時(shí)T的后移量，本節(jié)下面介紹3種經(jīng)典的快速單模式匹配算法，第3節(jié)介紹著名的多模式匹配算法—AC算法。2.1KMP算法???D.Knuth、J.Morris和V.Pratt提出一種快速模式匹配算法，稱為KMP算法[2]
5、。???KMP算法的基本思想是：若某趟匹配過程中T[i]和P[j]不匹配，而前j-1個(gè)字符已經(jīng)匹配。此時(shí)只需右移模式串P，文本串T不動，即指針i不回溯，讓P[k]與T[i]繼續(xù)比較。移動后重新開始比較的位置k僅與模式串P有關(guān)，而與目標(biāo)串S無關(guān)，因此K可以事先確定。若定義函數(shù)next(j)=K，則next函數(shù)的定義應(yīng)為：???next(j)=Max{k
6、P[1..K-1]=P[j-k+1..j-1]}???KMP算法的時(shí)間復(fù)雜度是O(m+n)，空間復(fù)雜度是O(m)，對BF算法進(jìn)行了很大的改進(jìn)。2.2BM算法???KMP算法雖然在不匹配時(shí)能使模式串右移若干位，但右移的距離不可能超過一趟匹
7、配操作所進(jìn)行的比較次數(shù)j，存在這一問題的根本原因是KMP算法的匹配操作是從左向右進(jìn)行的。在KMP算法的啟發(fā)下，R.Boyer和J.Moore提出了一種新的快速字符串匹配算法，即BM算法[3]。???BM算法的基本思想是從右向左進(jìn)行比較。開始時(shí)仍是P的最左邊與T的最左邊對齊，但首先進(jìn)行Pm與Tm的比較。當(dāng)某趟比較中出現(xiàn)不匹配時(shí)，BM算法采用兩條啟發(fā)性規(guī)則計(jì)算模式串右移的距離，即壞字符規(guī)則和好后綴規(guī)則。1)?壞字符規(guī)則（BadCharacter）???P中的某個(gè)字符與T中的某個(gè)字符不相同時(shí)使用壞字符規(guī)則右移模式串P，P右移的距離可以通過delta1函數(shù)計(jì)算出來。delta1函數(shù)的定義如下
8、：????2)?好后綴規(guī)則(GoodSuffix)???壞字符規(guī)則沒有考慮已經(jīng)取得的部分匹配的情況，而KMP算法卻考慮了。該規(guī)則將KMP算法和BM算法的思想結(jié)合起來，在不丟失真解的前提下確定一個(gè)新的移動距離delta2，該函數(shù)與樣本P有關(guān)。具體分以下兩種情況，如圖1所示。l?·P中間的某一子串P[j-s+1..m-s]與已比較部分P[j+1..m]相同，可讓P右移s位。l?·P已比較部分P[j+1..m]的后綴P[s+1..m]與P的前綴P[1..m-s]
