基于A(yíng)C-BM改進(jìn)算法的入侵檢測技術(shù)研究論文
摘 要：網(wǎng)絡(luò )的飛速發(fā)展帶來(lái)了諸多安全隱患，入侵檢測技術(shù)作為一種積極防御手段成為了網(wǎng)絡(luò )安全領(lǐng)域的研究熱點(diǎn)。模式匹配由于原理簡(jiǎn)單、無(wú)需訓練、檢測效率高、擴展性好廣泛用于目前的入侵檢測系統。本文首先分析了模式匹配，比較了經(jīng)典的模式匹配算法，總結了其存在的問(wèn)題，并在此基礎上對AC-BM模式匹配算法進(jìn)行優(yōu)化，提出了AC-BM改進(jìn)算法，有效提高了檢測效率，降低了檢測過(guò)程中的資源消耗。
關(guān)鍵詞：入侵檢測 模式匹配 AC-BM改進(jìn)算法 檢測效率
隨著(zhù)網(wǎng)絡(luò )的日新月異，網(wǎng)絡(luò )入侵行為變得越來(lái)越復雜，因此網(wǎng)絡(luò )安全也日益受到人們廣泛關(guān)注。入侵檢測系統能夠在不影響網(wǎng)絡(luò )正常工作的前提下，對網(wǎng)絡(luò )數據進(jìn)行監測、收集和分析，進(jìn)而從中發(fā)現是否存在入侵行為 [1]。根據入侵檢測方法的不同，可以分為異常檢測技術(shù)和誤用檢測技術(shù)。誤用檢測技術(shù)存在一個(gè)已知攻擊模式特征庫，通過(guò)網(wǎng)絡(luò )數據與庫中攻擊模式進(jìn)行匹配來(lái)判斷是否存在入侵行為，其檢測的誤報率較低。誤用檢測中使用的檢測技術(shù)主要有模式匹配、專(zhuān)家系統、狀態(tài)轉移等，而模式匹配由于原理簡(jiǎn)單、可擴展性好等特點(diǎn)被廣泛應用[2]。網(wǎng)絡(luò )數據包的高速傳輸使得模式匹配算法應用于入侵檢測領(lǐng)域面臨了諸多問(wèn)題，模式匹配的效率將直接影響入侵檢測的性能。
1 模式匹配
模式匹配是指：已知一長(cháng)度為n的文本字符串T=T1T2….Tn和一長(cháng)度為t (t
目前的模式匹配算法多分為單模式匹配和多模式匹配[3]。若每次文本串只能對一種模式串進(jìn)行模式匹配，這種方法稱(chēng)為單模式匹配算法。即己知文本串Text=T[l...n]和模式串Pattern=P[l...t]，對于1<=f<=n，存在T[f+1...f+t]=P[1…t]。
網(wǎng)絡(luò )入侵類(lèi)型日益復雜，為了提高匹配速度期望可以實(shí)現每次可以同時(shí)對多個(gè)模式進(jìn)行匹配，這種方法稱(chēng)為多模式匹配方法。也就是說(shuō)，文本字符串Text=T[l...n]對模式樹(shù)進(jìn)行掃描時(shí)，至少在模式樹(shù)種發(fā)現其中一個(gè)模式串與之相匹配。
2 應用于入侵檢測的經(jīng)典模式匹配算法
2.1 BM算法[4]
BM基本思想是進(jìn)行匹配時(shí)，將文本字符串和模式串左邊對齊，然后從右向左進(jìn)行字符比較。如果字符匹配，則繼續進(jìn)行下一次比較;若模式字符P[k]和文本字符串T[i+k]文本字符串不匹配，此時(shí)分別計算Goodsuffix[k]和Badchar[T[i+k]]-(m-k) 兩個(gè)函數值中更大的那個(gè)作為偏移量，文本字符串指針向右移動(dòng)偏移量的長(cháng)度，進(jìn)而重新開(kāi)始匹配。此外，若找到了模式串在文本字符串中出現過(guò)一次，則文本字符串向右移動(dòng)Goodsuffix[0]的距離。一直進(jìn)行下去直到找出模式串所有可能出現的位置。
2.2 AC算法[5]
AC算法巧妙地將字符比較轉化為了狀態(tài)轉移。AC算法有以下兩個(gè)特點(diǎn)：一是掃描字符時(shí)不需要回溯;二是時(shí)間復雜度為O(n)，與模式的數目和長(cháng)度無(wú)關(guān)。
該方法的核心思想是在A(yíng)C算法匹配開(kāi)始之前，首先建立轉向函數goto()，失效函數failure()和輸出函數output()，在此基礎上構建出樹(shù)形狀態(tài)機。在掃描匹配階段，AC算法采用以上三個(gè)函數掃描文本字符串，從而搜索島模式串在文本字符串中所有出現的位置。
2.3 AC-BM算法[6]
AC-BM 算法的模式樹(shù)從文本右端向左邊移動(dòng)，每一次匹配時(shí)字符從左到右進(jìn)行比較，AC-BM算法同時(shí)使用壞字符移動(dòng)規則和好前綴移動(dòng)規則。
壞字符移動(dòng)：如果模式串與文本字符串不匹配，則移動(dòng)模式樹(shù)中其他模式分支和當前比較字符相同的`那個(gè)字符的位置。如果在當前深度上，模式樹(shù)中的任何一個(gè)模式分支在文本字符串中都沒(méi)有出現，則模式樹(shù)的移動(dòng)偏移量等于模式書(shū)中最短的模式分支的長(cháng)度min l。
好前綴移動(dòng)：移動(dòng)模式樹(shù)，使其與已經(jīng)匹配成功另一個(gè)模式分支的完全前綴的后一位置處，也可以是移動(dòng)到模式樹(shù)中的另一個(gè)模式分支的后綴可以匹配成功文本的前綴的后一位置。需要注意的是，移動(dòng)模式樹(shù)時(shí)，其移動(dòng)偏移量必須小于模式樹(shù)中最短模式分支的長(cháng)度min l。
3 改進(jìn)的AC-BM算法
AC-BM算法結合了AC算法和BM算法的優(yōu)點(diǎn)，允許將不同模式放在一棵模式樹(shù)上同時(shí)進(jìn)行搜索匹配。但AC-BM算法仍舊存在一些問(wèn)題。一是每一次模式串的移動(dòng)距離必須小于模式樹(shù)中模式分支的最短長(cháng)度 min l。二是AC-BM算法沿用了BM算法壞字符移動(dòng)和好前綴移動(dòng)，但好前綴規則預處理階段過(guò)程比較復雜，并且難以實(shí)現。三是每一次的匹配都對所有字符進(jìn)行一一比較，即便是有些字符在模式樹(shù)中沒(méi)有出現過(guò)也要進(jìn)行比較，并且模式樹(shù)的跳躍距離是根據匹配過(guò)程中單個(gè)“壞字符”決定的，但這些壞字符在下一輪匹配中卻不一定能匹配成功。四是AC-BM算法的每次匹配都是從左往右，因此可能出現模式串和文本字符串的相當一部分前綴一致，但最后極少數后綴不同時(shí)還是需要進(jìn)行很多次字符比較的浪費。
基于以上缺點(diǎn)，并結合AC-BM算法自身特點(diǎn)，主要考慮從加大算法跳躍距離和減少每輪匹配字符比較次數兩方面對其進(jìn)行改進(jìn)。
3.1 改進(jìn)算法描述
為了避免匹配過(guò)程中壞字符存在于文本串最后幾個(gè)字符，使之前的字符比較都是浪費的情況，AC-BM改進(jìn)算法在每次匹配開(kāi)始前，首先檢驗待匹配文本串的最后兩個(gè)字
【基于A(yíng)C-BM改進(jìn)算法的入侵檢測技術(shù)研究論文】相關(guān)文章：
網(wǎng)絡(luò )信息理入侵檢測技術(shù)研究論文11-07
基于遺傳算法的車(chē)牌定位技術(shù)研究論文11-06
基于遺傳算法的優(yōu)化設計論文11-20
碰撞檢測中的KDOPS算法論文06-15