本文關鍵詞：基于多維有限自動機的DFA改進算法

  更多相關文章： 正則表達式 DFA 有限自動機 狀態(tài)爆炸

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

【參考文獻】

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

1 張大方;張潔坤;黃昆;;一種基于智能有限自動機的正則表達式匹配算法[J];電子學報;2012年08期

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

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

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

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

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

【共引文獻】

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

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

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

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

4 王奇敏;李訓根;趙海斌;;基于FPGA的正則表達式匹配引擎設計[J];電子世界;2013年01期

5 吳君欽;王凱;;面向網(wǎng)絡流的正則表達式匹配改進算法[J];電子技術應用;2013年08期

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

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

8 周興旺;;正則表達式中的與或非解析[J];計算機光盤軟件與應用;2014年18期

9 王培鳳;李莉;;一種改進的多模式匹配算法在Snort中的應用[J];計算機科學;2012年02期

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

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

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

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

3 胡侃;車身碰撞安全的若干關鍵技術研究[D];吉林大學;2013年

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

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

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

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

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

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

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

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

7 仇文娟;云計算中依賴任務動態(tài)并行調度機制的研究[D];大連理工大學;2011年

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

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

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

【二級參考文獻】

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

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

2 曹京;譚建龍;劉萍;郭莉;;布爾表達式匹配問題研究[J];計算機應用研究;2007年09期

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

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

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

6 曹京;劉燕兵;劉萍;譚建龍;郭莉;;定序窗口布爾表達式匹配技術研究[J];通信學報;2007年12期

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

【相似文獻】

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

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

2 黃飛丹;蒙春鳳;鄧培民;易忠;;由單個狀態(tài)生成的有限自動機的一些性質[J];工程數(shù)學學報;2011年01期

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

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

5 陶仁驥,陳世華;關于延遲τ步(可)逆有限自動機結構的一些性質[J];計算機學報;1980年04期

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

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

8 丁春欣;有限自動機的最小化[J];高師理科學刊;2000年03期

9 沈整;函數(shù)映射與有限自動機關系及算法探討[J];西南民族學院學報(自然科學版);2000年02期

10 ;自動化理論與技術[J];電子科技文摘;2003年01期

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

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

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

1 姚剛;有限自動機可逆性的若干結果[D];中國科學院研究生院（軟件研究所）;2003年

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

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

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

1 張勇;一類有限自動機及其積的試驗序列[D];廣西師范大學;2008年

2 吳宗顯;概率有限自動機的代數(shù)性質[D];廣西師范大學;2008年

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

4 林添榮;量子有限自動機等價性判定研究[D];福建師范大學;2011年

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

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

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

8 陳燕敏;關于矩陣模型表示下有限自動機的討論[D];廣西師范大學;2006年

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

10 楊楠;矩陣模型在有限自動機上的應用[D];廣西師范大學;2007年

，

本文編號：1037676