【摘要】：正則表達(dá)式匹配在很多網(wǎng)絡(luò)安全領(lǐng)域起著非常重要的作用。確定性有限自動(dòng)機(jī)(DFA,deterministic finiteautomaton)具有線速穩(wěn)定的匹配性能,因而更適合在高速網(wǎng)絡(luò)環(huán)境下執(zhí)行正則表達(dá)式匹配。但DFA可能由于狀態(tài)膨脹而占用巨大的內(nèi)存空間。作為狀態(tài)膨脹問(wèn)題的一種經(jīng)典解決方案,i-DFA在大幅降低內(nèi)存開(kāi)銷的同時(shí),還能保證最差匹配性能。然而,已有方法構(gòu)造i-DFA時(shí)在時(shí)間和空間上都是非常低效的�；跔顟B(tài)分組的思想,提出了一種高效的i-DFA構(gòu)造方法。進(jìn)一步地,對(duì)狀態(tài)分組進(jìn)行了形式化描述,并證明了獲得最優(yōu)狀態(tài)分組是NP困難的,并基于局部搜索的思想提出了一種近優(yōu)的狀態(tài)分組算法。實(shí)驗(yàn)結(jié)果表明,相比經(jīng)典的i-DFA構(gòu)造方法,所做的工作在時(shí)間和空間上都有極大的改進(jìn):i-DFA的狀態(tài)規(guī)�？赡苤皇且延蟹椒ǖ�2/3,而構(gòu)造i-DFA所用時(shí)間僅是已有方法的1/16。
[Abstract]:Regular expression matching plays a very important role in many areas of network security. Deterministic finite automata (DFA,deterministic finiteautomaton) is more suitable for regular expression matching in high-speed networks because of its line-rate stable matching performance. But DFA may take up a huge amount of memory due to state inflation. As a classic solution to the state inflation problem, i-DFA can greatly reduce the memory overhead and ensure the worst matching performance at the same time. However, the existing methods for constructing i-DFA are very inefficient both in time and space. Based on the idea of state grouping, an efficient i-DFA construction method is proposed. Furthermore, the formal description of the state grouping is given, and it is proved that it is difficult to obtain the optimal state grouping by NP, and a near-optimal state grouping algorithm is proposed based on the idea of local search. The experimental results show that compared with the classical i-DFA construction method, the work done is greatly improved in both time and space: the scale of the state of the i-DFA may be only 2 ~ 3 of the existing method. The time it takes to construct a i-DFA is only 1. 16. 6% of the existing method.
【作者單位】： 中國(guó)科學(xué)院信息工程研究所;信息內(nèi)容安全技術(shù)國(guó)家工程實(shí)驗(yàn)室;國(guó)家計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心;
【基金】：國(guó)家高技術(shù)研究發(fā)展計(jì)劃(“863”計(jì)劃)基金資助項(xiàng)目(2011AA010703,2011AA010705) 國(guó)家自然科學(xué)基金資助項(xiàng)目(61070026,61003295) 國(guó)家242信息安全計(jì)劃基金資助項(xiàng)目(2011F47)~~
【分類號(hào)】：TP393.08

【參考文獻(xiàn)】

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

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

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

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

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

【相似文獻(xiàn)】

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

1 葉文暉,梁里寧;在ASP.NET中利用正則表達(dá)式實(shí)現(xiàn)模式驗(yàn)證[J];電腦知識(shí)與技術(shù);2005年24期

2 劉小波,謝芊,李留英;應(yīng)用正則表達(dá)式在ASP.NET中實(shí)現(xiàn)優(yōu)化的輸入驗(yàn)證方法[J];現(xiàn)代圖書情報(bào)技術(shù);2005年10期

3 陳艷軍;;利用正則表達(dá)式開(kāi)發(fā)動(dòng)態(tài)網(wǎng)頁(yè)[J];數(shù)字技術(shù)與應(yīng)用;2010年02期

4 趙書慧;;正則表達(dá)式在JSP登錄頁(yè)面中的應(yīng)用[J];才智;2011年10期

5 李麗莉;李婭;周琪云;;正則表達(dá)式在網(wǎng)絡(luò)信息監(jiān)控分析系統(tǒng)中的應(yīng)用[J];信息技術(shù);2008年04期

6 張瑞;高嶺;田密;;基于JS和正則表達(dá)式的客戶端數(shù)據(jù)驗(yàn)證方法研究[J];延安大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年01期

7 王德安;劉雁南;;Web日志統(tǒng)計(jì)分析[J];電腦編程技巧與維護(hù);2007年06期

8 唐壹勛;;正則表達(dá)式在批量新聞網(wǎng)頁(yè)處理中的應(yīng)用[J];福建電腦;2008年03期

9 呂秋平;潘亞;;網(wǎng)頁(yè)設(shè)計(jì)常用技巧綜述[J];軟件導(dǎo)刊;2008年05期

10 春水東流;;批量處理包含特定字符的行[J];電腦迷;2009年03期

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

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

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

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

4 袁方方;安寶宇;鄭世慧;;基于Netfilter的內(nèi)容過(guò)濾系統(tǒng)的研究與實(shí)現(xiàn)[A];第十三屆中國(guó)科協(xié)年會(huì)第11分會(huì)場(chǎng)-中國(guó)智慧城市論壇論文集[C];2011年

5 梁勇;張文;;網(wǎng)絡(luò)輿情采集系統(tǒng)的設(shè)計(jì)[A];2011年全國(guó)通信安全學(xué)術(shù)會(huì)議論文集[C];2011年

6 王海燕;谷明哲;王靜;孟小峰;;基于預(yù)定義模式的Web信息抽取[A];第十八屆全國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集（研究報(bào)告篇）[C];2001年

7 程志;;微博地震謠言監(jiān)測(cè)系統(tǒng)[A];中國(guó)地震學(xué)會(huì)第14次學(xué)術(shù)大會(huì)專題[C];2012年

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

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

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

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

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

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

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

7 張琦;以融合應(yīng)用圍剿垃圾郵件[N];中國(guó)計(jì)算機(jī)報(bào);2008年

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

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

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

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

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

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

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

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

8 鄧林;網(wǎng)絡(luò)信息安全防護(hù)理論與方法的研究[D];合肥工業(yè)大學(xué);2009年

9 張凱;基于本體的Web信息集成若干關(guān)鍵技術(shù)研究[D];復(fù)旦大學(xué);2004年

10 朱維軍;時(shí)間區(qū)間時(shí)序邏輯模型檢測(cè)：理論、算法及應(yīng)用[D];西安電子科技大學(xué);2011年

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

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

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

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

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

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

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

7 王琳琳;基于HTML Parser的Web信息提取技術(shù)[D];北京郵電大學(xué);2007年

8 劉胤;深度包檢測(cè)技術(shù)的研究與設(shè)計(jì)[D];貴州大學(xué);2008年

9 張子文;高效深度報(bào)文檢測(cè)的研究與實(shí)現(xiàn)[D];國(guó)防科學(xué)技術(shù)大學(xué);2008年

10 王麗;基于Web的商品信息抽取與融合的研究與實(shí)現(xiàn)[D];武漢理工大學(xué);2008年

，

本文編號(hào)：2439669