本文關(guān)鍵詞：基于TCAM的高速可擴(kuò)展的正則表達(dá)式匹配技術(shù)　出處：《中國科學(xué)技術(shù)大學(xué)》2013年博士論文　論文類型：學(xué)位論文

  更多相關(guān)文章： NFA DFA TCAM 正則表達(dá)式匹配 深度包檢測

【摘要】：正則表達(dá)式匹配(Regular expression matching)是很多網(wǎng)絡(luò)應(yīng)用(如入侵檢測、內(nèi)容過濾、協(xié)議分析等)的核心引擎技術(shù),隨著互聯(lián)網(wǎng)及網(wǎng)絡(luò)應(yīng)用的高速發(fā)展,對高速可擴(kuò)展(fast and scalable)的正則表達(dá)式匹配的需求越來越大,但多年來如何實(shí)現(xiàn)高速可擴(kuò)展的正則表達(dá)式這一難題一直困擾著研究者們。正則表達(dá)式用等價(jià)的有限自動(dòng)機(jī)表示,包括非確定性有限自動(dòng)機(jī)(non-deterministic finite automaton, NFA)和確定性有限自動(dòng)機(jī)(deterministic finite automaton, DFA)。NFA所需存儲(chǔ)空間很小但是匹配速度很慢；DFA由于匹配速度很快使得DFA方法成為了實(shí)現(xiàn)正則表達(dá)式匹配的普遍選擇,但DFA的高匹配速度是以可呈指數(shù)膨脹的狀態(tài)空間為代價(jià)的。高速可擴(kuò)展的正則表達(dá)式匹配的終極目標(biāo)就是實(shí)現(xiàn)像DFA一樣的高匹配速度,即每匹配一個(gè)輸入字符只需一次存儲(chǔ)訪問,并且實(shí)現(xiàn)像NFA一樣的低存儲(chǔ)空間,即所需存儲(chǔ)空間隨正則表達(dá)式規(guī)則集呈線性增長。因?yàn)槿龖B(tài)內(nèi)容可尋址存儲(chǔ)器(ternary content addressable memory, TCAM)具有獨(dú)特的并行查找、三態(tài)存儲(chǔ)與模糊匹配的能力,最近研究者們提出了基于TCAM的DFA實(shí)現(xiàn)技術(shù)。然而,這些方法所需的TCAM條目數(shù)仍然高于呈指數(shù)增長的DFA狀態(tài)數(shù),因此其所需的存儲(chǔ)空間仍然過于龐大。 本文提出一種基于TCAM的DFA壓縮技術(shù),該技術(shù)每處理一個(gè)輸入字符僅需一次簡單的TCAM查詢,并且將所需的TCAM條目數(shù)降低到了DFA狀態(tài)數(shù)以下。本文通過發(fā)現(xiàn)和利用NFA與DFA之間存在的結(jié)構(gòu)聯(lián)系,識別出源自相同NFA狀態(tài)的DFA狀態(tài),這些DFA狀態(tài)實(shí)際上是相同NFA狀態(tài)在DFA中不同的副本結(jié)構(gòu)。本文為DFA狀態(tài)設(shè)計(jì)合適的TCAM編碼和TCAM條目壓縮算法,得以有效地將DFA中的這些相似的副本結(jié)構(gòu)進(jìn)行壓縮�；谡鎸�(shí)規(guī)則集的實(shí)驗(yàn)結(jié)果表明,本文方法所使用的TCAM條目數(shù)最多比DFA狀態(tài)數(shù)小兩個(gè)數(shù)量級。 在DFA實(shí)現(xiàn)方法之外,本文又提出首個(gè)基于TCAM的NFA實(shí)現(xiàn)方法,通過合適的TCAM編碼,本文的NFA實(shí)現(xiàn)方法和DFA實(shí)現(xiàn)方法一樣,每處理一個(gè)字符只需一次TCAM查找。NFA運(yùn)行時(shí),并非所有的狀態(tài)都會(huì)同時(shí)活躍,通過將同時(shí)活躍的NFA狀態(tài)劃分到不同分組中進(jìn)行編碼,使得可以用較少的比特?cái)?shù)表示一個(gè)NFA活躍狀態(tài)集合�；贜FA活躍狀態(tài)集的編碼和相應(yīng)的TCAM條目壓縮算法,本文的NFA實(shí)現(xiàn)方法既具備和DFA完全一樣的運(yùn)行速度,同時(shí)所需存儲(chǔ)空間又接近與正則表達(dá)式規(guī)則集大小呈線性增長的NFA大小。基于真實(shí)規(guī)則集的實(shí)驗(yàn)結(jié)果表明,相比基于TCAM的DFA實(shí)現(xiàn)方法,本文的NFA實(shí)現(xiàn)方法能將存儲(chǔ)空間和匹配速度均各自減少和提高一個(gè)數(shù)量級。 此外,本文還設(shè)計(jì)出一種快速的DFA構(gòu)造算法,以打破基于DFA的正則表達(dá)式匹配方法的一個(gè)瓶頸——DFA方法都需要預(yù)先從NFA構(gòu)造一個(gè)與之等價(jià)的DFA。本文通過深入探索自動(dòng)機(jī)內(nèi)在運(yùn)行特性——NFA狀態(tài)間活躍關(guān)系和NFA中導(dǎo)致DFA空間膨脹的因素,設(shè)計(jì)了一種NFA狀態(tài)子集的編碼方法和查詢方法,減少了DFA構(gòu)造過程中狀態(tài)子集的查詢代價(jià)。實(shí)驗(yàn)結(jié)果表明,與傳統(tǒng)的子集構(gòu)造算法相比,本文的方法減少了88.33%～93.57%的DFA構(gòu)造時(shí)間。
[Abstract]:Regular expression matching is the core engine technology of many network applications ( such as intrusion detection , content filtering , protocol analysis , etc . ) . With the high - speed development of Internet and network applications , the problem of fast and scalable regular expression matching is getting more and more , but how to realize the high - speed scalable regular expression for many years has puzzled researchers . Regular expressions are represented by equivalent finite automata , including non - deterministic finite automata ( NFA ) and deterministic finite automata ( DFA ) . Because the matching speed quickly makes the DFA approach a universal choice to achieve regular expression matching , the high matching speed of DFA is at the expense of state space which can be exponentially expanded . The ultimate goal of high - speed scalable regular expression matching is to realize high matching speed like DFA . In this paper , a kind of DFA compression technique is proposed based on the ternary association of DFA . In this paper , we find and use the structure link between NFA and DFA to identify the states of DFA which originate from the same NFA state . In this paper , we find and use the structure of NFA and DFA . These DFA states effectively compress these similar copy structures in DFA . Based on the experimental results of the real rule set , the results show that the maximum number of entries used in this method is two orders of magnitude smaller than the number of DFA states . In addition to the implementation method of DFA , this paper presents the first method of realizing NFA based on the ternary system , which is based on the NFA active state set . The NFA implementation method is not all the same as DFA . The NFA implementation method is based on NFA active state set and corresponding algorithm of the NFA . The NFA implementation method is based on the NFA active state set and the corresponding algorithm of the regular expression rule set . The NFA implementation method can reduce the storage space and the matching speed by one order of magnitude compared with the method of the regular expression . In addition , a fast DFA construction algorithm is designed to break a bottleneck _ DFA method based on DFA - based regular expression matching method .

【學(xué)位授予單位】：中國科學(xué)技術(shù)大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2013
【分類號】：TP333;TP393.08

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 范新龍;張華;;探討編程管理網(wǎng)絡(luò)設(shè)備[J];電腦編程技巧與維護(hù);2010年20期

2 張文典;LAG—一個(gè)詞法分析程序的生成程序[J];小型微型計(jì)算機(jī)系統(tǒng);1985年08期

3 Gary Chan;Java咖啡館(9)——一個(gè)壓縮歸檔實(shí)用軟件[J];電腦愛好者;2004年19期

4 張?zhí)?;基于正則表達(dá)式技術(shù)的數(shù)據(jù)驗(yàn)證及應(yīng)用[J];甘肅科技縱橫;2006年04期

5 項(xiàng)潤華;段紅勇;柳漢雄;;正則表達(dá)式的使用以及在VC6.0的應(yīng)用[J];洛陽工業(yè)高等�？茖W(xué)校學(xué)報(bào);2006年05期

6 梁里寧;;正則表達(dá)式在SQL Server 2000中的實(shí)現(xiàn)與應(yīng)用[J];科技廣場;2008年01期

7 李國晶;王景強(qiáng);;淺析正則表達(dá)式[J];科技資訊;2010年04期

8 劉小平;;在Visual C++ 6.0中使用Boost正則表達(dá)式庫[J];信息與電腦(理論版);2010年03期

9 張申媛;;正則表達(dá)式的實(shí)現(xiàn)[J];科技創(chuàng)新導(dǎo)報(bào);2010年20期

10 胡海星;;DEL命令問題——2001年12期編程擂臺(tái)題解[J];程序員;2002年02期

相關(guān)會(huì)議論文 前10條

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

2 曾雨薇;許向眾;;基于正則表達(dá)式的稅源數(shù)據(jù)解析方案的研究[A];2011高等職業(yè)教育電子信息類專業(yè)學(xué)術(shù)暨教學(xué)研討會(huì)論文集[C];2011年

3 梁興開;趙澤茂;黃亮;;Web應(yīng)用中的ReDoS檢測方法研究[A];浙江省電子學(xué)會(huì)2011學(xué)術(shù)年會(huì)論文集[C];2011年

4 袁真;;構(gòu)造正則表達(dá)式的幾種NFA算法的分析和比較[A];2006年全國理論計(jì)算機(jī)科學(xué)學(xué)術(shù)年會(huì)論文集[C];2006年

5 李佳;魏更宇;胡楠;王樅;楊義先;;基于特征自生成的畸形SIP信令檢測算法[A];2010通信理論與技術(shù)新發(fā)展——第十五屆全國青年通信學(xué)術(shù)會(huì)議論文集（下冊）[C];2010年

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

7 余劉瑯;汪彩萍;程克勤;;基于Snort的檢測SQL注入和跨站腳本攻擊的正則表達(dá)式的探討[A];中國儀器儀表學(xué)會(huì)第九屆青年學(xué)術(shù)會(huì)議論文集[C];2007年

8 何雪松;;Matlab和C#聯(lián)合編程在雨滴譜儀數(shù)據(jù)處理中的應(yīng)用[A];第十五屆全國云降水與人工影響天氣科學(xué)會(huì)議論文集（Ⅱ）[C];2008年

9 王春元;張韜;;一種獲取網(wǎng)頁主要中文信息的方法[A];全國計(jì)算機(jī)安全學(xué)術(shù)交流會(huì)論文集（第二十四卷）[C];2009年

10 鐘濤;陳群秀;;基于層式有限狀態(tài)自動(dòng)機(jī)的災(zāi)難事件抽取系統(tǒng)[A];第三屆全國信息檢索與內(nèi)容安全學(xué)術(shù)會(huì)議論文集[C];2007年

相關(guān)重要報(bào)紙文章 前10條

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

2 ;在論壇中自動(dòng)顯示超鏈接[N];計(jì)算機(jī)世界;2006年

3 清水編譯;Apache 2.2.0帶來了什么？[N];計(jì)算機(jī)世界;2006年

4 廣東 子衿;認(rèn)識Linux中的符號[N];電腦報(bào);2004年

5 ;軟件組[N];計(jì)算機(jī)世界;2004年

6 ;專用的平臺(tái) 瑪賽反垃圾郵件網(wǎng)關(guān)（ASMG）[N];網(wǎng)絡(luò)世界;2002年

7 湖南 劉靚;軟件水平考試備考寶典[N];中國電腦教育報(bào);2004年

8 美國Watchfire公司戰(zhàn)略研究總監(jiān) Danny ALLAN;應(yīng)用掃描:從源頭加固Web應(yīng)用安全[N];中國計(jì)算機(jī)報(bào);2007年

9 吳征;讓Google為動(dòng)態(tài)頁面的站點(diǎn)服務(wù)[N];計(jì)算機(jī)世界;2004年

10 ;安氏實(shí)時(shí)監(jiān)控入侵者[N];中國計(jì)算機(jī)報(bào);2001年

相關(guān)博士學(xué)位論文 前10條

1 陳曙暉;基于內(nèi)容分析的高速網(wǎng)絡(luò)協(xié)議識別技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2007年

2 姜鯤鵬;高速串模式匹配算法研究[D];解放軍信息工程大學(xué);2012年

3 胡圣明;基于內(nèi)存自動(dòng)機(jī)與模式的動(dòng)態(tài)引擎構(gòu)造技術(shù)研究[D];西安電子科技大學(xué);2009年

4 徐建國;網(wǎng)絡(luò)化制造系統(tǒng)中虛擬加工若干關(guān)鍵技術(shù)研究[D];南京理工大學(xué);2007年

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

6 錢忠勝;基于模型的Web應(yīng)用測試用例生成方法[D];上海大學(xué);2008年

7 黃昆;高性能內(nèi)容過濾與分發(fā)技術(shù)研究[D];湖南大學(xué);2009年

8 胡燕;基于Web信息抽取的專業(yè)知識獲取方法研究[D];武漢理工大學(xué);2007年

9 孔寧;物聯(lián)網(wǎng)資源尋址關(guān)鍵技術(shù)研究[D];中國科學(xué)院研究生院（計(jì)算機(jī)網(wǎng)絡(luò)信息中心）;2008年

10 孫偉;XML數(shù)據(jù)庫查詢優(yōu)化及相關(guān)技術(shù)研究[D];哈爾濱工程大學(xué);2006年

相關(guān)碩士學(xué)位論文 前10條

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

2 王飛龍;PBE技術(shù)在文本搜索中的應(yīng)用[D];哈爾濱理工大學(xué);2007年

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

4 溫源;基于FPGA的正則表達(dá)式匹配引擎的設(shè)計(jì)[D];哈爾濱工程大學(xué);2009年

5 劉子乾;基于攻擊模式的系統(tǒng)漏洞檢測工具的設(shè)計(jì)與實(shí)現(xiàn)[D];天津大學(xué);2008年

6 劉一蘭;基于SNMP MIB編譯器的實(shí)現(xiàn)及其生成器技術(shù)的研究[D];華中師范大學(xué);2004年

7 楊琨;反垃圾郵件技術(shù)研究及應(yīng)用[D];四川大學(xué);2005年

8 王小朋;基于代理的元搜索引擎的研究[D];遼寧工程技術(shù)大學(xué);2005年

9 吳蓓;LINUX環(huán)境下IDS與防火墻聯(lián)動(dòng)系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D];四川師范大學(xué);2008年

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

，

本文編號：1397560