發(fā)布時(shí)間：2021-07-06 01:50

　　面對(duì)日益復(fù)雜的網(wǎng)絡(luò)攻擊,傳統(tǒng)基于精準(zhǔn)字符串的模式匹配不能勝任復(fù)雜多變的網(wǎng)絡(luò)環(huán)境,正則表達(dá)式以其靈活,高效,表達(dá)能力強(qiáng)的特點(diǎn)迅速成為高速網(wǎng)絡(luò)環(huán)境中匹配引擎用于描述規(guī)則的語(yǔ)言,在網(wǎng)絡(luò)安全領(lǐng)域有著重要的應(yīng)用。深度包檢測(cè)技術(shù)中采用正則表達(dá)式描述網(wǎng)絡(luò)協(xié)議。采用正則表達(dá)式描述“某種規(guī)則”十分高效、簡(jiǎn)潔,多條正則表達(dá)式描述的規(guī)則可以合并生成一個(gè)DFA引擎,可以實(shí)現(xiàn)一次掃描完成對(duì)所有的規(guī)則的匹配。但基于DFA正則表達(dá)式匹配引擎存在“狀態(tài)膨脹”的問(wèn)題,不同的正則表達(dá)式合并后,在理論最糟糕的情況下,會(huì)導(dǎo)致合并后的匹配引擎狀態(tài)數(shù)呈指數(shù)增長(zhǎng),造成巨大的內(nèi)存空間占用,以至于普通的電腦硬件平臺(tái)難以完成大規(guī)模規(guī)則的模式匹配工作。降低DFA的存儲(chǔ)空間需求是實(shí)現(xiàn)正則表達(dá)式高效率匹配亟待解決的問(wèn)題,對(duì)正則表達(dá)式進(jìn)行合理的分組是解決DFA的狀態(tài)膨脹的重要方式。然而現(xiàn)有的分組算法所求的分組結(jié)果并不理想,未能在分組數(shù)和總狀態(tài)數(shù)上找到一個(gè)恰當(dāng)?shù)钠胶恻c(diǎn),未能實(shí)現(xiàn)分組數(shù)和總狀態(tài)數(shù)的雙重最優(yōu)。首先,本文分析了當(dāng)前正則表達(dá)式分組的研究現(xiàn)狀和現(xiàn)有分組算法的不足,隨后,在第2章中,針對(duì)當(dāng)前分組策略的不足,創(chuàng)新性的提出了兩種新的分組策略,即最... 

【文章來(lái)源】：深圳大學(xué)廣東省

【文章頁(yè)數(shù)】：75 頁(yè)

【學(xué)位級(jí)別】：碩士

【部分圖文】：

NFA狀態(tài)轉(zhuǎn)化圖

基于人工魚群算法的正則表達(dá)式分組研究求是實(shí)現(xiàn)正則表達(dá)式高速匹配廣泛應(yīng)用 2-1時(shí)間復(fù)雜度OODFA 和 NFA 的存儲(chǔ)消耗和處理復(fù)雜度對(duì)一條正則表達(dá)式 m 條正則表達(dá)內(nèi)存消耗 時(shí)間復(fù)雜度 (n2) O(n) O(n2m) (1) O(∑2) O(1)

組算法和 Becchi 分組算法[21]進(jìn)行比較，表 2-2 所示的是規(guī)則集選取于入侵rt 的分組結(jié)果對(duì)比。為了進(jìn)一步說(shuō)明本文提出的最小沖突分組算法的有效合在選取方面，我們從大規(guī)模正則表達(dá)式集合中抽取了 15 組規(guī)則集合，算法進(jìn)行仿真實(shí)驗(yàn)，規(guī)則條數(shù)從 N=4 條開始到 N=110 條，在表 2-3 和 2-4則集選取于 L7-filter 的分組情況。表 2-2 snort 規(guī)則集合分組結(jié)果對(duì)比規(guī)則集合 N= 4 10 16 23 40不分組(狀態(tài)數(shù)/組數(shù)) 76/1 3461/1 5867/1 8204/1 19019/1Becchi(狀態(tài)數(shù)/組數(shù)) 30/3 335/5 509/5 698/5 1744/5GREMC(狀態(tài)數(shù)/組數(shù)) 30/3 308/5 454/5 628/6 1432/5


本文編號(hào)：3267273