本文關(guān)鍵詞：基于多維有限自動(dòng)機(jī)的DFA改進(jìn)算法

  更多相關(guān)文章： 正則表達(dá)式 DFA 有限自動(dòng)機(jī) 狀態(tài)爆炸

【摘要】：多個(gè)正則表達(dá)式規(guī)則編譯成一個(gè)DFA(deter minister finite automata)時(shí),會產(chǎn)生狀態(tài)爆炸、存儲急劇增加的現(xiàn)象。針對最嚴(yán)重的狀態(tài)爆炸問題,從信息論的角度給出了解釋,并提出多維數(shù)學(xué)模型,將冗余狀態(tài)分為0維狀態(tài)和1維狀態(tài),通過前者按照維度壓縮,后者動(dòng)態(tài)構(gòu)建的方法將空間復(fù)雜度降到理論下界,并在此基礎(chǔ)上提出多維有限自動(dòng)機(jī)(MFA,multi-dimensional finite automata)。實(shí)驗(yàn)表明,MFA構(gòu)造時(shí)間比XFA略少,比DFA、STT冗余壓縮算法和Hybrid-FA降低了2~3個(gè)數(shù)量級;存儲空間比XFA略高,比DFA、STT冗余壓縮算法、m DFA、Hybrid-FA降低了1~2個(gè)數(shù)量級;匹配時(shí)間比DFA、Hybrid-FA略多,但是比XFA略少,比STT冗余壓縮算法和m DFA降低了1~2個(gè)數(shù)量級。
【作者單位】： 國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心;中國石油大學(xué)化工學(xué)院;
【關(guān)鍵詞】： 正則表達(dá)式 DFA 有限自動(dòng)機(jī) 狀態(tài)爆炸
【基金】：國家高技術(shù)研究發(fā)展計(jì)劃(“863”計(jì)劃)基金資助項(xiàng)目(2011AA01A103,2011AA01A101) 國家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃(“973”計(jì)劃)基金資助項(xiàng)目(2012CB315901,2013CB329104) 國家科技支撐計(jì)劃基金資助項(xiàng)目(2011BAH19B01)~~
【分類號】：TP301.1;TP393.08
【正文快照】： 1引言近年來,以“棱鏡門”為代表的各類監(jiān)控和攻擊事件為各國的網(wǎng)絡(luò)安全形勢敲響了警鐘。在網(wǎng)絡(luò)信息安全領(lǐng)域,入侵檢測系統(tǒng)(IDS,intrusion de-tection system)扮演著越來越重要的角色,IDS采用深度分組檢測(DPI,deep packet inspection)進(jìn)行病毒檢測、入侵識別、協(xié)議分析等,網(wǎng)

【參考文獻(xiàn)】

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

1 張大方;張潔坤;黃昆;;一種基于智能有限自動(dòng)機(jī)的正則表達(dá)式匹配算法[J];電子學(xué)報(bào);2012年08期

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

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

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

5 喬登科;王卿;柳廳文;孫永;郭莉;;基于狀態(tài)分組的高效i-DFA構(gòu)造技術(shù)[J];通信學(xué)報(bào);2013年08期

6 賀煒;郭云飛;扈紅超;;基于狀態(tài)約束的大規(guī)模正則表達(dá)式匹配算法[J];通信學(xué)報(bào);2013年10期

【共引文獻(xiàn)】

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

1 金學(xué)成;孫煒;梁野;郭玉金;謝忠華;;電力二次系統(tǒng)內(nèi)網(wǎng)安全監(jiān)視平臺的設(shè)計(jì)和實(shí)現(xiàn)[J];電力系統(tǒng)自動(dòng)化;2011年16期

2 韓光輝;曾誠;;正則表達(dá)式方程組的最小解[J];電腦與信息技術(shù);2011年05期

3 肖武德;;一種正則表達(dá)式的高效分組算法[J];計(jì)算機(jī)安全;2010年04期

4 王奇敏;李訓(xùn)根;趙海斌;;基于FPGA的正則表達(dá)式匹配引擎設(shè)計(jì)[J];電子世界;2013年01期

5 吳君欽;王凱;;面向網(wǎng)絡(luò)流的正則表達(dá)式匹配改進(jìn)算法[J];電子技術(shù)應(yīng)用;2013年08期

6 張宏莉;徐東亮;梁敏;劉宇峰;;海量模式高效匹配方法研究[J];電子學(xué)報(bào);2014年06期

7 宮陽陽;劉勤讓;邵翔宇;朱圣平;邢池強(qiáng);彭志彬;賀業(yè)里;;基于多維立方體的正則表達(dá)式匹配算法[J];電子學(xué)報(bào);2014年09期

8 周興旺;;正則表達(dá)式中的與或非解析[J];計(jì)算機(jī)光盤軟件與應(yīng)用;2014年18期

9 王培鳳;李莉;;一種改進(jìn)的多模式匹配算法在Snort中的應(yīng)用[J];計(jì)算機(jī)科學(xué);2012年02期

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

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

1 許憲成;基于網(wǎng)絡(luò)處理器的入侵檢測系統(tǒng)設(shè)計(jì)與性能優(yōu)化研究[D];華南理工大學(xué);2010年

2 張樹壯;面向網(wǎng)絡(luò)安全的高性能特征匹配技術(shù)研究[D];哈爾濱工業(yè)大學(xué);2011年

3 胡侃;車身碰撞安全的若干關(guān)鍵技術(shù)研究[D];吉林大學(xué);2013年

4 董永吉;面向資源優(yōu)化的分層式高速報(bào)文解析技術(shù)研究[D];解放軍信息工程大學(xué);2013年

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

1 段海生;基于正則表達(dá)式的深度包壓縮算法研究[D];西安電子科技大學(xué);2010年

2 張輝;面向網(wǎng)絡(luò)流識別的正則表達(dá)式匹配技術(shù)研究[D];首都師范大學(xué);2011年

3 田健;IDS中VLDC模式匹配算法的研究與應(yīng)用[D];吉林大學(xué);2011年

4 崔保良;基于稀疏表示的協(xié)同入侵檢測[D];廣東工業(yè)大學(xué);2011年

5 劉鵬;面向存儲的正則表達(dá)式匹配算法研究[D];解放軍信息工程大學(xué);2010年

6 李倫;針對大規(guī)模URL關(guān)鍵字的多模匹配算法的性能優(yōu)化[D];哈爾濱工業(yè)大學(xué);2011年

7 仇文娟;云計(jì)算中依賴任務(wù)動(dòng)態(tài)并行調(diào)度機(jī)制的研究[D];大連理工大學(xué);2011年

8 曹鼎;文件類型識別技術(shù)研究[D];解放軍信息工程大學(xué);2011年

9 黃鵬;基于FPGA的高性能模式匹配引擎研究與設(shè)計(jì)[D];解放軍信息工程大學(xué);2011年

10 陳圍;高速IP網(wǎng)絡(luò)中深度包檢測算法研究[D];解放軍信息工程大學(xué);2011年

【二級參考文獻(xiàn)】

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

1 陳曙暉;蘇金樹;范慧萍;侯婕;;一種基于深度報(bào)文檢測的FSM狀態(tài)表壓縮技術(shù)[J];計(jì)算機(jī)研究與發(fā)展;2008年08期

2 曹京;譚建龍;劉萍;郭莉;;布爾表達(dá)式匹配問題研究[J];計(jì)算機(jī)應(yīng)用研究;2007年09期

3 黃昆;張大方;謝高崗;金軍航;;一種面向深度數(shù)據(jù)包檢測的緊湊型正則表達(dá)式匹配算法[J];中國科學(xué):信息科學(xué);2010年02期

4 李偉男;鄂躍鵬;葛敬國;錢華林;;多模式匹配算法及硬件實(shí)現(xiàn)[J];軟件學(xué)報(bào);2006年12期

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

6 曹京;劉燕兵;劉萍;譚建龍;郭莉;;定序窗口布爾表達(dá)式匹配技術(shù)研究[J];通信學(xué)報(bào);2007年12期

7 柳廳文;孫永;卜東波;郭莉;方濱興;;正則表達(dá)式分組的1/(1-1/k)-近似算法[J];軟件學(xué)報(bào);2012年09期

【相似文獻(xiàn)】

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

1 陳燕敏;鄧培民;易忠;;有限自動(dòng)機(jī)矩陣模型的應(yīng)用——有限自動(dòng)機(jī)r階輸入存貯性質(zhì)判定新方法[J];計(jì)算機(jī)工程與應(yīng)用;2007年29期

2 黃飛丹;蒙春鳳;鄧培民;易忠;;由單個(gè)狀態(tài)生成的有限自動(dòng)機(jī)的一些性質(zhì)[J];工程數(shù)學(xué)學(xué)報(bào);2011年01期

3 陳乾;涂道興;莫智文;;模糊有限自動(dòng)機(jī)的乘積覆蓋性[J];模糊系統(tǒng)與數(shù)學(xué);2011年02期

4 翁福利;舒蘭;王澤文;;直覺模糊有限自動(dòng)機(jī)的乘積[J];模糊系統(tǒng)與數(shù)學(xué);2012年04期

5 陶仁驥,陳世華;關(guān)于延遲τ步(可)逆有限自動(dòng)機(jī)結(jié)構(gòu)的一些性質(zhì)[J];計(jì)算機(jī)學(xué)報(bào);1980年04期

6 陳有剛;有限自動(dòng)機(jī)代數(shù)及其算法[J];計(jì)算機(jī)工程與設(shè)計(jì);1990年01期

7 黃飛丹;鄧培民;易忠;;有限自動(dòng)機(jī)的同態(tài)[J];工程數(shù)學(xué)學(xué)報(bào);2014年01期

8 丁春欣;有限自動(dòng)機(jī)的最小化[J];高師理科學(xué)刊;2000年03期

9 沈整;函數(shù)映射與有限自動(dòng)機(jī)關(guān)系及算法探討[J];西南民族學(xué)院學(xué)報(bào)(自然科學(xué)版);2000年02期

10 ;自動(dòng)化理論與技術(shù)[J];電子科技文摘;2003年01期

中國重要會議論文全文數(shù)據(jù)庫 前1條

1 黎中文;張來順;肖健鵬;;改進(jìn)的UIO序列生成算法[A];計(jì)算機(jī)研究新進(jìn)展（2010）——河南省計(jì)算機(jī)學(xué)會2010年學(xué)術(shù)年會論文集[C];2010年

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

1 姚剛;有限自動(dòng)機(jī)可逆性的若干結(jié)果[D];中國科學(xué)院研究生院（軟件研究所）;2003年

2 王茂基;混沌同步中信息傳遞的研究[D];大連理工大學(xué);2011年

3 莫智文;Fuzzy有限態(tài)自動(dòng)機(jī)的最小化及其在心電圖（ECG）識別中的應(yīng)用[D];西南交通大學(xué);2005年

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

1 張勇;一類有限自動(dòng)機(jī)及其積的試驗(yàn)序列[D];廣西師范大學(xué);2008年

2 吳宗顯;概率有限自動(dòng)機(jī)的代數(shù)性質(zhì)[D];廣西師范大學(xué);2008年

3 黃飛丹;循環(huán)有限自動(dòng)機(jī)和有限自動(dòng)機(jī)的路代數(shù)[D];廣西師范大學(xué);2008年

4 林添榮;量子有限自動(dòng)機(jī)等價(jià)性判定研究[D];福建師范大學(xué);2011年

5 辛公彩;交換冪等半環(huán)上的加權(quán)有限自動(dòng)機(jī)的確定式[D];湖南科技大學(xué);2007年

6 孫志強(qiáng);基于半環(huán)代數(shù)理論的有限自動(dòng)機(jī)的探討[D];太原科技大學(xué);2009年

7 劉躍霞;語言半環(huán)上的有限自動(dòng)機(jī)的推廣[D];太原科技大學(xué);2010年

8 陳燕敏;關(guān)于矩陣模型表示下有限自動(dòng)機(jī)的討論[D];廣西師范大學(xué);2006年

9 程偉;模糊有限自動(dòng)機(jī)的分類及其狀態(tài)最小化算法研究[D];四川師范大學(xué);2002年

10 楊楠;矩陣模型在有限自動(dòng)機(jī)上的應(yīng)用[D];廣西師范大學(xué);2007年

，

本文編號：1037676