網(wǎng)絡消費網(wǎng) >  5G > > 正文
模式匹配算法在入侵檢測中的應用
時間:2022-02-07 22:22:01

摘 要:僅依靠傳統(tǒng)的被動防御技術(shù)已經(jīng)不能滿足如今的網(wǎng)絡安全需要,基于模式匹配入侵檢測系統(tǒng)正成為研究和應用的熱點,模式匹配效率的高低決定了這類入侵檢測系統(tǒng)的性能。全面綜述了應用入侵檢測系統(tǒng)的經(jīng)典的模式匹配算法,包括單模式匹配算法中的KMP算法、BM算法、RK算法和多模式匹配算法中的AC算法、AC―BM算法,并對各種算法的執(zhí)行效率進行了總結(jié)。通過分析算法的思想,提出了未來此類算法的研究方向。關(guān)鍵詞:入侵檢測;KMP算法;BM算法;RK算法;AC算法;AC―BM算法

0 引 言 隨著網(wǎng)絡技術(shù)的發(fā)展,各種基于網(wǎng)絡的應用層出不窮。面對日益突出的網(wǎng)絡安全問題,僅靠傳統(tǒng)的被動防御已經(jīng)不能滿足要求,能夠主動檢測并預防的入侵檢測系統(tǒng)應運而生。 根據(jù)采用的分析方法,入侵檢測分為誤用檢測和異常檢測。誤用檢測是指:根據(jù)己知的攻擊方法,預先定義入侵特征,通過判斷這此特征是否出現(xiàn)來完成檢測任務。異常檢測是指:根據(jù)用戶的行為或資源的使用狀況的正常程度來判斷是否屬于入侵。由于異常檢測的誤檢率和漏檢率高,因此目前大多數(shù)人侵檢測系統(tǒng)產(chǎn)品均主要采用誤用檢測的方法。誤用檢測中使用的檢測技術(shù)主要有:模式匹配、專家系統(tǒng)、狀態(tài)轉(zhuǎn)移等,其中模式匹配原理簡單,可擴展性好,而且最為常用。據(jù)統(tǒng)計,現(xiàn)在大約95%的入侵檢測都是特征匹配的入侵檢測。由此可見,模式匹配算法性能的好壞直接影響到入侵檢測系統(tǒng)的效率。隨著網(wǎng)絡傳輸速度的大幅度提高,入侵檢測系統(tǒng)需要處理的數(shù)據(jù)量越來越大,如果模式匹配算法來不及處理這些實時的大量的數(shù)據(jù)包,必然會丟棄部分數(shù)據(jù)包,而這些被丟棄的數(shù)據(jù)包中很可能就包含有入侵信息,從而造成漏報。在此介紹幾種著名的用于入侵檢測的模式匹配算法,包括單模式匹配算法和多模式匹配算法,通過對它們進行剖析和實際測試,提出入侵檢測系統(tǒng)中模式匹配算法的選擇策略和未來的研究方向。

1 單模式匹配算法1.1 相關(guān)定義 模式匹配:是指在給定長度為n的目標串T=T1T2…Tn中查找長度為m的模式串P=P1P2…Pm的首次出現(xiàn)或多次出現(xiàn)的過程。這里Ti(1≤i≤n),Pj(1≤j≤m)∈∑(字符集),若P在T中出現(xiàn)1次或多次,則稱匹配成功,否則稱匹配失敗。單模式匹配算法:在目標串中1次只能對1個模式串進行匹配的算法。 多模式匹配算法:在目標串中可同時對多個模式串進行匹配的算法。 最簡單的模式匹配算法是Brute―Force算法(BF算法)。在BF算法的目標串和模式串的字符比較中,只要有1個字符不相等,而不管前面已有多少個字符相等,就需要把目標串T回退,下次比較時目標串T只后移1個字符。雖然算法簡單,但效率低下,不適合用于入侵檢測系統(tǒng)中,不做重點介紹。 高效的模式匹配算法都是設法增大不匹配時目標串T或模式串P之間的偏移量,以減少總的比較次數(shù)。下面介紹3種經(jīng)典的快速單模式匹配算法。1.2 KMP算法 1970年,S.A.Cook從理論上證明了一維模式匹配問題可以在O(m+2)時間內(nèi)解決。D.E.Knuth,V.R.Pratt和T.H.Morris在BF算法的基礎上提出了一種快速模式匹配算法,稱為KMP算法,該算法消除了BF算法的目標串指針在相當多個字符比較相等后,只要有1個字符比較不等便需要回溯的缺點,使算法的效率得到了大幅度提高,時間復雜度達到最理想的O(m+n),空間復雜度是O(m)。 KMP算法的基本思想是:若某趟匹配過程中Ti和Pj不匹配,而前j一1個字符已經(jīng)匹配。此時只需右移模式串P,目標串T不動,即指針i不回溯,讓Pk與Ti繼續(xù)比較。移動后重新開始比較的位置k僅與模式串P有關(guān),而與目標串T無關(guān),因此k可以通過下面的next函數(shù)事先確定。 定義next[j]函數(shù)為:

1.3 BM算法 相對于BF算法,KMP算法雖然消除了主串指針的回溯,在不匹配時能使模式串右滑若干位,但由上述next函數(shù)可知:右滑的最大距離不會超過1趟匹配操作所進了的比較次數(shù)j,原因在于KMP算法的匹配操作是從左到右進行的。受到KMP算法的啟發(fā),R.S.Boyer和J.S.Moore提出一種新的快速字符串匹配算法一BM算法。 BM算法基本思想是:開始時將目標串T與模式串P左對齊,自右至左逐個字符進行比較(即首先比較Pm與Tm);當某趟比較時Ti與模式串的對應字符不匹配,則把模式串右滑d(x)一段距離,執(zhí)行由Pm與Ti+d(x)起始的自右至左的匹配檢查。BM算法采用以下兩條規(guī)則計算模式串右移的距離: (1)好后綴移動。其又分為2種情況: ①P已比較部分P[j+1…m]與其中間的某一子串P[j一s+l…m―s]相同,P右移s位。如圖1所示。

②P已比較部分P[j+l…m]的后綴P[s+l…m]與P的前綴P[l…m―s]相同,P右移s位。如圖2所示。

取滿足上述兩種情況的s的最小值作為移動距離。因此可以定義一個距離函數(shù)distl(j):

關(guān)鍵詞: 應用 入侵檢測 算法 匹配 模式

版權(quán)聲明:
    凡注明來網(wǎng)絡消費網(wǎng)的作品,版權(quán)均屬網(wǎng)絡消費網(wǎng)所有,未經(jīng)授權(quán)不得轉(zhuǎn)載、摘編或利用其它方式使用上述作品。已經(jīng)本網(wǎng)授權(quán)使用作品的,應在授權(quán)范圍內(nèi)使用,并注明"來源:網(wǎng)絡消費網(wǎng)"。違反上述聲明者,本網(wǎng)將追究其相關(guān)法律責任。
    除來源署名為網(wǎng)絡消費網(wǎng)稿件外,其他所轉(zhuǎn)載內(nèi)容之原創(chuàng)性、真實性、完整性、及時性本站不作任何保證或承諾,請讀者僅作參考并自行核實。
熱文

網(wǎng)站首頁 |網(wǎng)站簡介 | 關(guān)于我們 | 廣告業(yè)務 | 投稿信箱
 

Copyright © 2000-2020 m.netfop.cn All Rights Reserved.
 

中國網(wǎng)絡消費網(wǎng) 版權(quán)所有 未經(jīng)書面授權(quán) 不得復制或建立鏡像
 

聯(lián)系郵箱:920 891 263@qq.com

備案號:京ICP備2022016840號-15

營業(yè)執(zhí)照公示信息