本文關(guān)鍵詞：基于遺傳算法的正則表達(dá)式規(guī)則分組優(yōu)化

  更多相關(guān)文章： 自適應(yīng)遺傳算法 局部優(yōu)化 深度包檢測 正則表達(dá)式 分組算法

【摘要】：隨著互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展,新的網(wǎng)絡(luò)應(yīng)用和服務(wù)不斷出現(xiàn)。隨之,網(wǎng)絡(luò)帶寬迅速擴(kuò)大,致使待檢測規(guī)則集的規(guī)模越來越龐大和復(fù)雜。因而功能強(qiáng)大的正則表達(dá)式成為描述規(guī)則的新一代工具,并成功的應(yīng)用于深度包檢測技術(shù)中。然而,在某種情況下,多條正則表達(dá)式生成合并DFA時會出現(xiàn)狀態(tài)膨脹問題,導(dǎo)致巨大的存儲空間消耗甚至無法生成。通過對正則表達(dá)式集合進(jìn)行分組是解決這一問題的主要方法。目前,已有不少研究者對分組算法進(jìn)行了研究并提出了解決方案,但分組結(jié)果并不理想,不能有效解決DFA空間消耗過大的問題,有待進(jìn)一步優(yōu)化。首先,本文介紹了正則表達(dá)式分組的研究背景與意義以及國內(nèi)外研究現(xiàn)狀。其次,本文介紹了最近鄰優(yōu)化算法,通過定義DFA狀態(tài)矩陣并按最近鄰原則進(jìn)行排序,然后采用從前往后局部優(yōu)化搜索策略來解決正則表達(dá)式分組問題;概括性地闡述了遺傳算法的基本思想及在各個領(lǐng)域的應(yīng)用。為解決正則表達(dá)式匹配問題,提出一種基于正態(tài)自適應(yīng)遺傳優(yōu)化的改進(jìn)正則表達(dá)式分組算法REG-NAGA。根據(jù)迭代次數(shù)和適應(yīng)度集中程度兩個因素的側(cè)重不同,利用正態(tài)函數(shù)自適應(yīng)地改變交叉概率Pc和變異概率Pm,采取最優(yōu)保存策略保證最優(yōu)個體不被大的Pc和Pm破壞,另外,結(jié)合Becchi算法以及局部尋優(yōu)算法來進(jìn)一步優(yōu)化。最后,本文分別從snort、L7-filter這兩個開源系統(tǒng)中隨機(jī)抽取若干條正則表達(dá)式作為測試集,并以Becchi開源的正則表達(dá)式匹配引擎為工具生成的DFA作為實驗數(shù)據(jù),對算法進(jìn)行仿真。本文實現(xiàn)了用于求解正則表達(dá)式分組問題的最近鄰優(yōu)化算法和基于正態(tài)自適應(yīng)遺傳優(yōu)化的改進(jìn)正則表達(dá)式分組算法REG-NAGA。仿真結(jié)果表明,REG-NAGA算法能在全局范圍內(nèi)搜索到更好的解,能有效減少狀態(tài)總數(shù),降低正則表達(dá)式匹配的空間復(fù)雜度。
【學(xué)位授予單位】：深圳大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：TP393.08;TP18

【參考文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前6條

1 劉荷花;崔超;陳晶;;一種改進(jìn)的遺傳算法求解旅行商問題[J];北京理工大學(xué)學(xué)報;2013年04期

2 張樹壯;羅浩;方濱興;云曉春;;一種面向網(wǎng)絡(luò)安全檢測的高性能正則表達(dá)式匹配算法[J];計算機(jī)學(xué)報;2010年10期

3 徐乾;鄂躍鵬;葛敬國;錢華林;;深度包檢測中一種高效的正則表達(dá)式壓縮算法[J];軟件學(xué)報;2009年08期

4 張樹壯;羅浩;方濱興;;面向網(wǎng)絡(luò)安全的正則表達(dá)式匹配技術(shù)[J];軟件學(xué)報;2011年08期

5 吳虎勝;張鳳鳴;趙法棟;;利用自適應(yīng)混合遺傳算法求解平車裝載問題[J];鐵道學(xué)報;2013年12期

6 蔡良偉;劉思麒;李霞;李軍;;基于蟻群優(yōu)化的正則表達(dá)式分組算法[J];深圳大學(xué)學(xué)報(理工版);2014年03期

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前1條

1 位二偉;二倍體自適應(yīng)遺傳算法在函數(shù)優(yōu)化中的應(yīng)用[D];重慶大學(xué);2012年

，

本文編號：1194109