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

【參考文獻】

相關期刊論文 前1條

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

【二級參考文獻】

相關期刊論文 前1條

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

【相似文獻】

相關期刊論文 前10條

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

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

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

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

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

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

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

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

9 呂秋平;潘亞;;網頁設計常用技巧綜述[J];軟件導刊;2008年05期

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

相關會議論文 前7條

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

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

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

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

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

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

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

相關重要報紙文章 前7條

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

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

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

4 ;專用的平臺 瑪賽反垃圾郵件網關（ASMG）[N];網絡世界;2002年

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

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

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

相關博士學位論文 前10條

1 陳曙暉;基于內容分析的高速網絡協(xié)議識別技術研究[D];國防科學技術大學;2007年

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

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

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

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

6 孔寧;物聯(lián)網資源尋址關鍵技術研究[D];中國科學院研究生院（計算機網絡信息中心）;2008年

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

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

9 張凱;基于本體的Web信息集成若干關鍵技術研究[D];復旦大學;2004年

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

相關碩士學位論文 前10條

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

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

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

4 楊琨;反垃圾郵件技術研究及應用[D];四川大學;2005年

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

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

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

8 劉胤;深度包檢測技術的研究與設計[D];貴州大學;2008年

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

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

，

本文編號：2439669