本文關(guān)鍵詞：一種高效的正則表達式匹配方法

  更多相關(guān)文章： 深度包檢測 正則表達式 子集分割 有限自動機 混合自動機

【摘要】：為實現(xiàn)網(wǎng)絡(luò)安全檢測中大規(guī)模正則表達式的匹配,分析了在從非確定型有限自動機(NFA)到確定型有限自動機(DFA)的子集構(gòu)造過程中導(dǎo)致狀態(tài)爆炸性增長的原因,并提出了一種高效的正則表達式匹配方法。這種方法通過將部分DFA狀態(tài)轉(zhuǎn)變成受限的NFA狀態(tài)來消除狀態(tài)數(shù)量的劇烈增長,并會形成一種DFA狀態(tài)與受限的NFA狀態(tài)交替出現(xiàn)的有限自動機,稱為DNFA。DNFA將DFA與NFA結(jié)合在一起,實現(xiàn)匹配速度與內(nèi)存空間占用的平衡,其多層結(jié)構(gòu)也更加適合復(fù)雜正則表達式規(guī)則。實驗結(jié)果表明,上述方法可以在大大減少內(nèi)存需求的情況下,實現(xiàn)正則表達式的高效匹配。
【作者單位】： 北京郵電大學(xué)網(wǎng)絡(luò)技術(shù)研究院;
【關(guān)鍵詞】： 深度包檢測 正則表達式 子集分割 有限自動機 混合自動機
【基金】：科技支撐計劃(2012BAH37B02,2012BAH42B02) 863計劃(2012AA03001) 242計劃(2013A012,2013A133)資助項目
【分類號】：TP393.08
【正文快照】： 0引言 述,因此,越來越多的正則表達式被應(yīng)用到網(wǎng)絡(luò)安全的各個方面,例如Linux應(yīng)用層協(xié)議分類器(Linux當(dāng)今,深度包檢測技術(shù)巳被廣泛應(yīng)用于網(wǎng)絡(luò)安 Application Protocol Classifier,L7[4]),開源的人侵檢全的各個方面,例如人侵檢測系統(tǒng)(intrusion detec- 測系統(tǒng)Snort[5]、Bro[6],

【參考文獻】

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

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

【共引文獻】

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

1 丁麟軒;黃昆;張大方;;基于并行字符索引的多步長正則表達式匹配算法[J];計算機研究與發(fā)展;2015年03期

2 徐成成;陳曙暉;;NetMagic平臺上正則表達式匹配技術(shù)實現(xiàn)[J];小型微型計算機系統(tǒng);2015年02期

3 陳曙暉;徐成成;;基于兩級存儲的正則表達式匹配技術(shù)[J];通信學(xué)報;2014年06期

4 張樹壯;吳志剛;羅浩;;一種高效的正則表達式匹配方法[J];高技術(shù)通訊;2014年06期

5 馬珂;;試論MD5算法的安全分析及破解[J];現(xiàn)代婦女(下旬);2014年05期

6 楊雨;胡亞娟;林萍;;正則表達式在英語語調(diào)統(tǒng)計分析中的應(yīng)用研究[J];平頂山學(xué)院學(xué)報;2013年05期

7 肖明明;余順爭;;基于文法推斷的協(xié)議逆向工程[J];計算機研究與發(fā)展;2013年10期

8 馬珂;;U保證MD5算法的安全分析及破解[J];中國-東盟博覽;2013年03期

9 鄭天明;王韜;郭世澤;李華;趙新杰;;改進的空間協(xié)議識別算法[J];通信學(xué)報;2012年05期

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

【二級參考文獻】

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

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

2 王永成,沈州,許一震;改進的多模式匹配算法[J];計算機研究與發(fā)展;2002年01期

【相似文獻】

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

1 王甲春;;正則表達式的五個良好習(xí)慣[J];中文信息;2003年11期

2 白紅哲,馬立勇;基于正則表達式的話務(wù)報告處理軟件的實現(xiàn)[J];通信管理與技術(shù);2005年02期

3 孟巖;;一夫當(dāng)關(guān)——《精通正則表達式》書評[J];程序員;2007年08期

4 ;新書上架[J];程序員;2007年10期

5 路個的;;請個伙伴,助你成長為正則表達式高手[J];電腦愛好者;2008年23期

6 余晟;;正則表達式隨筆[J];程序員;2008年03期

7 余晟;;正則表達式隨筆(續(xù))[J];程序員;2008年09期

8 周健鋒;;正則表達式的強大功能[J];電腦知識與技術(shù);2009年16期

9 夏陽陽;李建華;;新疆勘探生產(chǎn)經(jīng)營管理系統(tǒng)中正則表達式的應(yīng)用[J];辦公自動化;2009年20期

10 李國晶;王景強;;淺析正則表達式[J];科技資訊;2010年04期

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

1 管杰裕;;正則表達式在氣象信息處理中的應(yīng)用[A];2005年廣西氣象學(xué)會學(xué)術(shù)年會論文集[C];2005年

2 劉琪;牛文靜;;正則表達式在惡意代碼動態(tài)分析中的應(yīng)用[A];2009通信理論與技術(shù)新發(fā)展——第十四屆全國青年通信學(xué)術(shù)會議論文集[C];2009年

3 王輝;丁明君;楊進;;正則表達式在企業(yè)信息管理開發(fā)中的應(yīng)用[A];2010年MIS/S&A學(xué)術(shù)交流會議論文集（中國造船工程學(xué)會學(xué)術(shù)論文集）[C];2010年

4 田珂;趙國鴻;;利用TCAM與正則表達式對郵件協(xié)議進行二次識別的思想研究[A];第十六屆計算機工程與工藝年會暨第二屆微處理器技術(shù)論壇論文集[C];2012年

中國重要報紙全文數(shù)據(jù)庫 前1條

1 彭福祥 張鈞;ASP.NET基本數(shù)值處理技巧[N];計算機世界;2006年

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

1 彭坤楊;基于TCAM的高速可擴展的正則表達式匹配技術(shù)[D];中國科學(xué)技術(shù)大學(xué);2013年

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

1 韓家寶;圖數(shù)據(jù)搜索引擎Trinity中正則表達式匹配子系統(tǒng)的設(shè)計與實現(xiàn)[D];哈爾濱工業(yè)大學(xué);2015年

2 徐成成;基于兩級存儲的正則表達式匹配技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2013年

3 李哲夫;正則表達式在電信業(yè)務(wù)處理中的應(yīng)用研究[D];暨南大學(xué);2008年

4 范慧萍;基于正則表達式的協(xié)議識別研究與實現(xiàn)[D];國防科學(xué)技術(shù)大學(xué);2007年

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

6 姜英杰;支持正則表達式的文本匹配優(yōu)化算法[D];東北大學(xué);2012年

7 張潔坤;時空高效的正則表達式匹配算法研究[D];湖南大學(xué);2010年

8 張娜;基于正則表達式的深度包檢測研究[D];華東師范大學(xué);2007年

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

10 劉俊超;基于正則表達式的應(yīng)用層協(xié)議識別技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2008年

，

本文編號：859734