關(guān)于快速高效的模式匹配算法的剖析與改進(jìn)

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

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

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

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

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

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

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

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

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

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

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