關于快速高效的模式匹配算法的剖析與改進

1、關于快速高效的模式匹配算法的剖析與改良摘要：模式匹配算法是現(xiàn)代化網(wǎng)絡入侵檢測中的關鍵環(huán)節(jié),本文主要介紹了幾種常用的模式匹配算法,并在此根底上,提出一種更快捷、更高效的改良方法,以提升模式匹配的效率與質(zhì)量,保證網(wǎng)絡平安.關鍵詞：模式匹配入侵檢測改良隨著我國計算機與網(wǎng)絡技術的飛速開展,網(wǎng)絡應用已涉及到人們生產(chǎn)、生活的各個領域,其重要性日益凸顯.隨之而來的網(wǎng)絡攻擊問題也備受關注,給網(wǎng)絡平安性帶來挑戰(zhàn).傳統(tǒng)的網(wǎng)絡防御模式,主要采取身份認證、防火墻、數(shù)據(jù)加密等技術,但是與當前網(wǎng)絡發(fā)展不適應.在此背景下,入侵檢測技術營運而生,并建立在模式匹配根底上,保證檢測的快捷性、準確性,應用越來越廣泛.1、模式匹配原

2、理概述模式匹配是入侵檢測領域的重要概念,源自入侵信號的層次性.結合網(wǎng)絡入侵檢測的底層審計事件,從中提取更高層次的內(nèi)容.通過高層事件形成的入侵信號,遵循一定的結構關系,將入侵信號的抽象層次進行具體劃分.入侵領域大師kumar將這種入侵信號劃分為四大層次,并將每一個層次與匹配模式相對應.以下將分別對四大層次進行分析：(1)存在.只要存在審計事項,就可以證實入侵行為的發(fā)生,并深層次挖掘入侵企圖.存在主要對應的匹配模式就是“存在模式可以說,存在模式就是在固定的時間內(nèi),檢查系統(tǒng)中的特定狀態(tài),同時判斷系統(tǒng)狀態(tài).(2)序列.一些入侵的發(fā)生,是遵循一定的順序,而組成的各種行為.具體表現(xiàn)在一組事件的秩序上.序列

3、對應的是“序列模式,在應用序列模式檢測入侵時,主要關注間隔的時間與持續(xù)的時間.(3)規(guī)那么.規(guī)那么表示的是一種可以擴展的表達方式,主要通過and邏輯表達來連接一系列的描述事件規(guī)那么.一般適用于這種模式的攻擊信號由相關活動組成,這些活動之間往往不存在事件的順序關系.(4)其他.其他模式是不包含前面幾種方法的攻擊,在具體應用過程中,難以與其他入侵信號進行模式匹配,大多為局部實現(xiàn)方式.2、幾種常用的模式匹配算法2.1 ac算法ac算法(aho-corasick)是一種可以同時搜索假設干個模式的匹配算法,最早時期在圖書館書目查詢系統(tǒng)中應用,效果良好.通過使用ac算法,實現(xiàn)了利用有限狀態(tài)自動機結構對所有

4、字符串的接收過程.自動機具有結構性特征,且每一個前綴都利用唯一狀態(tài)顯示,甚至可同時應用于多個模式的前綴中.如果文本中的某一個字符不屬于模式中預期的下一個字符范圍內(nèi),或者可能出現(xiàn)錯誤鏈接的指向狀態(tài)等,那么最長模式的前綴同時也可作為當前狀態(tài)相對應的后綴.ac算法的復雜性在于o(n),預處理階段的復雜性那么在于o(項.在采取ac算法的有限狀態(tài)自動機中,應該在每一個字符的模式串中分別建立節(jié)點,提升該算法的使用效率與質(zhì)量.目前,應用有限自動計算法是一種較為典型與常用的方法,如果模式集比擬大,可能引發(fā)空間膨脹問題.在使用ac算法時,搜索輸入串過程中沒有跳躍,直接根據(jù)順序輸入,因此在規(guī)那么較少的情況下,ac

5、算法的搜索性能并不理想.2.2 kmp算法kmps算法與簡單的算法有所不同,如果某一次的匹配失敗,那么模式串不一定是向右移動一格,即使向右移動,也未必從模式的起點位置開始匹配.kmp的具體計算方法為：當某次試匹配成功之后,如果tx?px,那么即使在模式之前j-1個字符全部匹配,而實現(xiàn)已經(jīng)獲知子模式p1p2px-1,且最常的首子串與尾子串同等,即：p1p2pk-1=px-k+1pjxk+2pj-k,那么在下一次的匹配過程中,就可以將模式串向右移動,表示為nextx,代表當模式串中的第x個字符和主串中的相應字符出現(xiàn)“失配現(xiàn)象,那么模式中就需要重新與主串中的字符位置進行比較,在預處理時就可以完成ne

6、xtx的計算工作.為了能完整表達完全匹配的各種情況,以上各首子串必須保證為最長.因此,對于任何一個子模式來說p1p2px,其中1Wxwn,“自匹配中的首子串都是唯一的,僅能與模式的自身結構相關.通過應用kmp算法,采取一次將模式向右移動假設干位置的方式,保證匹配過程中不需要任何回溯.在相對較好的情況下,使用kmp算法的時間復雜度是0m+n,nextx的計算時間復雜度是02.3 bm算法bm算法是單模式匹配算法的其中一種,屬于精確的字符串匹配算法,采取從右向左的比擬方式,應用了“壞字符與“好后綴兩種啟發(fā)原那么.bm算法與kmp算法具有一定區(qū)別,主要是對模式串的掃描方式相反,即由從左向右改為從右向

7、左.采用bm算法采用這種掃描方式的優(yōu)勢在于：如果在正文中出現(xiàn)了個別模式?jīng)]有的字符,那么可以將此模式迅速掠過正文.應用bm算法,關鍵在于如何提升正文的匹配速度,尤其是字符在該模式中的具體位置.假設模式為w1,n,同時定義函數(shù)x,函數(shù)x明確了正文中可能產(chǎn)生字符的模式位置：x>(1,2,3,4,n),且x6.函數(shù)x的定義如下：對于每一個x6來說,假設在執(zhí)行正文的位置j起“返前一段以及模式從左向右的匹配檢查過程中,無論在哪一位置,如果存在不匹配現(xiàn)象,就開始執(zhí)行從wn和tj+x的從右向左的匹配檢查.這種檢查的效果相當于將模式向右側(cè)滑動一段距離.很明顯,tj不會在模式中出現(xiàn)或者僅在模式的末端存在,向

8、右側(cè)滑動的最大距離為n.3、一種新的模式匹配算法隨著計算機與網(wǎng)絡的不斷應用與拓展,網(wǎng)絡流量迅速增加,各種匹配原那么與匹配效率逐漸落后,無法滿足現(xiàn)代化高速網(wǎng)絡的開展需要.尤其隨著各種檢測規(guī)那么的不斷提出,各種數(shù)據(jù)包匹配的次數(shù)也有所改變,因此很難完全滿足性能.針對這一情況,在各種根本算法的根底上,充分利用“本次匹配不成功原那么,在匹配失敗的情況下,盡量跳過多個字符,實現(xiàn)迅速匹配目標.實際上,本文介紹的快速高效的全新模式匹配算法qs,是bm的簡化算法形式,具體描述如下：當p1,2n和ti,i+1,i+n-1對齊的情況下,就可以實現(xiàn)匹配.如果匹配失敗,就分析ti+n個字符,以此判斷右移p1,2n的距離

9、.由于某一次匹配失敗之后,模式會至少向右側(cè)移動一格位置,那么一般情況下,ti+n字符就會在下一次匹配中出現(xiàn).因此,匹配失敗后,就可以綜合考慮ti+n而非ti,i+1,i+n-1中的某個字符,這樣模式最大右移的距離是n+1,在bm算法中那么是n.以下將對兩種改進方法分別進行論述：(1)經(jīng)過改良的算法,如果文本和模式的某次匹配失敗,那么對于ti,i+1,i+n-1左邊的字符ti-1就可以采取壞字符移動的方式,而ti,i+1,i+n-1那么采取好前綴移動.在文本中,應該取指針移動距離最大的一個,即minlength+1(minlength)是模式集合中的最短模式長度.針對文本中的所有字符(w)來說,

10、可將壞字符的移動函數(shù)定義為：如果w出現(xiàn)在p中,那么執(zhí)行公式(1),否那么執(zhí)行公式(2).(2)在傳統(tǒng)的匹配算法中,當匹配失敗之后,就會分別計算壞字符啟發(fā)函數(shù)或者好前綴啟發(fā)函數(shù),然后取其中最大值,作為移動量.但是每次計算的時間比擬長,因此需要改良壞字符優(yōu)先策略.如果利用壞字符啟發(fā)可以實現(xiàn)n或者n+1的量,就不需要再計算前綴啟發(fā)函數(shù),最大限度地縮短模式匹配算法時間.經(jīng)過改良的算法,預處理時間復雜度是0(11+1pl),此處II代表字符集的大小,IpI那么是模式集中所有的模式長度綜合.這種算法的最正確情況為：在每次模式樹的第一個字符和文本比擬不匹配,而且存在偏移量的最大值minlength+1,改良

11、算法的最正確性能,那么比擬的次數(shù)為：在每次進行模式樹中的最長模式,最后一個字符和文本比擬時匹配失敗,那么最小偏移量是1,改良之后的算法也具備最差性能,這種情況下的比擬次數(shù)為：minlength+n-2(minlength-1)maxlength,時間復雜度是0(nmaxlength).在平均情況下,時間復雜度和字符出現(xiàn)概率相關,可以通過概率模型計算.由上可見,隨著各種網(wǎng)絡應用的不斷完善,網(wǎng)絡入侵檢測計算日益開展,逐漸無法適應網(wǎng)絡環(huán)境的要求,必須加快改良與優(yōu)化策略,將改良的算法應用于入侵檢測系統(tǒng)中,提升檢測效率,保證網(wǎng)絡安全運行.參考文獻1陳圍.采用集合切分編碼的大容量模式匹配算法j.計算機應用研究,2021(6).2王爍.字符串模式匹配的硬件加速研究j.中國科學技術大學：通信與信息系統(tǒng).2021.3孫偉.基于模式匹配和協(xié)議分析的入侵檢測技術研究j.湖南大學：計算機應用技術,2006.4魯宏偉,魏凱,孔華鋒.一種改良的kmp高效模式匹配算法j.華中科技大學學報,2006(10).5張航,王宏志,李建中