【摘要】：正則表達式匹配在很多網(wǎng)絡(luò)安全領(lǐng)域起著非常重要的作用。確定性有限自動機(DFA,deterministic finiteautomaton)具有線速穩(wěn)定的匹配性能,因而更適合在高速網(wǎng)絡(luò)環(huán)境下執(zhí)行正則表達式匹配。但DFA可能由于狀態(tài)膨脹而占用巨大的內(nèi)存空間。作為狀態(tài)膨脹問題的一種經(jīng)典解決方案,i-DFA在大幅降低內(nèi)存開銷的同時,還能保證最差匹配性能。然而,已有方法構(gòu)造i-DFA時在時間和空間上都是非常低效的。基于狀態(tài)分組的思想,提出了一種高效的i-DFA構(gòu)造方法。進一步地,對狀態(tài)分組進行了形式化描述,并證明了獲得最優(yōu)狀態(tài)分組是NP困難的,并基于局部搜索的思想提出了一種近優(yōu)的狀態(tài)分組算法。實驗結(jié)果表明,相比經(jīng)典的i-DFA構(gòu)造方法,所做的工作在時間和空間上都有極大的改進:i-DFA的狀態(tài)規(guī)�？赡苤皇且延蟹椒ǖ�2/3,而構(gòu)造i-DFA所用時間僅是已有方法的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.
【作者單位】： 中國科學(xué)院信息工程研究所;信息內(nèi)容安全技術(shù)國家工程實驗室;國家計算機網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心;
【基金】：國家高技術(shù)研究發(fā)展計劃(“863”計劃)基金資助項目(2011AA010703,2011AA010705) 國家自然科學(xué)基金資助項目(61070026,61003295) 國家242信息安全計劃基金資助項目(2011F47)~~
【分類號】：TP393.08

【參考文獻】

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

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

【二級參考文獻】

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

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

【相似文獻】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 ;在論壇中自動顯示超鏈接[N];計算機世界;2006年

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

3 ;軟件組[N];計算機世界;2004年

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

5 ;安氏實時監(jiān)控入侵者[N];中國計算機報;2001年

6 吳征;讓Google為動態(tài)頁面的站點服務(wù)[N];計算機世界;2004年

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，

本文編號：2439669