【摘要】：網(wǎng)絡(luò)入侵檢測(cè)在信息安全中占據(jù)著重要的地位，而深度包檢測(cè)(DPI, DeepPacket Inspection)是基于規(guī)則匹配的網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)實(shí)現(xiàn)的重要方法。目前正則表達(dá)式被廣泛用于描述DPI中的各種攻擊特征規(guī)則，用確定的有限狀態(tài)機(jī)（DFA）來(lái)實(shí)現(xiàn)正則表達(dá)式代表的特征規(guī)則的匹配。但這樣做的問(wèn)題是DFA的存儲(chǔ)空間大，難以適應(yīng)規(guī)模日益增長(zhǎng)的特征規(guī)則集。本文試圖從狀態(tài)數(shù)與狀態(tài)轉(zhuǎn)移數(shù)兩個(gè)角度壓縮DFA的存儲(chǔ)空間。 首先，，針對(duì)DFA中狀態(tài)數(shù)龐大的問(wèn)題，通過(guò)對(duì)帶長(zhǎng)度限制的正則表達(dá)式對(duì)應(yīng)的DFA添加計(jì)數(shù)器，使得正則表達(dá)式的構(gòu)造復(fù)雜度與長(zhǎng)度限制無(wú)關(guān)。其中對(duì)三類帶長(zhǎng)度限制的正則表達(dá)式，分別給出了對(duì)應(yīng)的帶計(jì)數(shù)器DFA的構(gòu)造及匹配方法。 其次，在狀態(tài)數(shù)目不變的前提下，對(duì)DFA中狀態(tài)轉(zhuǎn)移數(shù)進(jìn)行壓縮。一方面從壓縮字母表的角度對(duì)字符映射表進(jìn)行改進(jìn)，對(duì)狀態(tài)轉(zhuǎn)移表中列相同的字符在字符映射表中直接映射到目的狀態(tài)，進(jìn)一步壓縮了字母表規(guī)模。另一方面根據(jù)添加默認(rèn)狀態(tài)轉(zhuǎn)移的思想提出了BiD2FA算法，其在WD2FA算法基礎(chǔ)上添加一種比WD2FA取代更多狀態(tài)轉(zhuǎn)移的默認(rèn)狀態(tài)轉(zhuǎn)移，并直接轉(zhuǎn)向匹配到的下一狀態(tài)。通過(guò)對(duì)BiD2FA算法以及字母表壓縮與WD2FA結(jié)合的壓縮方法進(jìn)行實(shí)驗(yàn)，結(jié)果表明狀態(tài)轉(zhuǎn)移數(shù)目都減少為原來(lái)的1%以下。
【圖文】：

startB3D2Cendnot CC,counter2--not C and D,counter2=counter2-2failurecounter2<0 counter2<01counter1=j圖 3.12 ^B+[^\n]{3}CD 對(duì)應(yīng)的帶兩個(gè)計(jì)數(shù)器的 DFA3.3 實(shí)驗(yàn)分析本節(jié)實(shí)驗(yàn)采用了在密蘇里大學(xué)副教授 Michela Becchi 提供的正則表達(dá)式轉(zhuǎn)有動(dòng)機(jī)的開源源代碼（網(wǎng)址 http://regex.wustl.edu/index.php/Main_Page），其代用 C++語(yǔ)言編寫，我們?cè)?visual studio 2010 開發(fā)環(huán)境通過(guò)對(duì)其改寫進(jìn)行 DFA算法實(shí)現(xiàn)和實(shí)驗(yàn)。

可能多轉(zhuǎn)移信息的默認(rèn)狀態(tài)轉(zhuǎn)移。此外還需滿足以下兩個(gè)限制條件：1） 默認(rèn)狀態(tài)轉(zhuǎn)移構(gòu)成的狀態(tài)轉(zhuǎn)移圖中不能含有回路，否則會(huì)產(chǎn)生死循環(huán)。并不是每個(gè)狀態(tài)都存在一條到其它狀態(tài)的默認(rèn)狀態(tài)轉(zhuǎn)移，在狀態(tài)轉(zhuǎn)移圖中，狀態(tài)轉(zhuǎn)移邊構(gòu)成一棵樹或者森林，每棵樹中的根結(jié)點(diǎn)不存在到其它狀態(tài)的默態(tài)轉(zhuǎn)移。由于構(gòu)造樹要比構(gòu)造森林的壓縮效果要好一些，求取具有最大壓縮默認(rèn)狀態(tài)轉(zhuǎn)移就轉(zhuǎn)化為了求取一個(gè)無(wú)向圖中最大帶權(quán)生成樹的問(wèn)題。2） 要限制默認(rèn)狀態(tài)轉(zhuǎn)移構(gòu)成的樹的最大深度(稱為默認(rèn)轉(zhuǎn)移長(zhǎng)度)。假設(shè)狀態(tài)為 n，則最壞條件下最大帶權(quán)生成樹的默認(rèn)轉(zhuǎn)移長(zhǎng)度為 O(n)，即存在某個(gè)狀某些字符的激勵(lì)下，對(duì)應(yīng)的需要跳轉(zhuǎn) n 次才能跳轉(zhuǎn)到目的狀態(tài)。而 DFA 處理字符的時(shí)間復(fù)雜度為 O(1)，用最大帶權(quán)生成樹算法得到的狀態(tài)轉(zhuǎn)移雖然能得大的壓縮率，但匹配效率卻得不到保證。所以需要對(duì)默認(rèn)轉(zhuǎn)移長(zhǎng)度進(jìn)行限制。因此根據(jù)以上三條限制，D2FA 及 WD2FA 算法通過(guò)構(gòu)建一棵默認(rèn)轉(zhuǎn)移長(zhǎng)度不限制的最大帶權(quán)生成樹[19]，為狀態(tài)構(gòu)建默認(rèn)狀態(tài)轉(zhuǎn)移。圖 4.3 為通過(guò) WD2FA構(gòu)造的^B+.{3}D 對(duì)應(yīng)的默認(rèn)狀態(tài)轉(zhuǎn)移樹的示例，其中實(shí)線代表默認(rèn)狀態(tài)轉(zhuǎn)虛線代表非默認(rèn)的狀態(tài)轉(zhuǎn)移，實(shí)線邊上的數(shù)字是默認(rèn)狀態(tài)轉(zhuǎn)移的權(quán)值。
【學(xué)位授予單位】：西安電子科技大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2014
【分類號(hào)】：TP393.08

【參考文獻(xiàn)】

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

1 劉俊超;趙國(guó)鴻;陳曙暉;;一種用于深度報(bào)文檢測(cè)的DFA狀態(tài)表壓縮方法[J];計(jì)算機(jī)工程與應(yīng)用;2008年22期

2 宋明秋;張國(guó)權(quán);鄧貴仕;;入侵檢測(cè)多模式匹配算法[J];計(jì)算機(jī)工程;2006年05期

3 黃昆;張大方;謝高崗;金軍航;;一種面向深度數(shù)據(jù)包檢測(cè)的緊湊型正則表達(dá)式匹配算法[J];中國(guó)科學(xué):信息科學(xué);2010年02期

4 于強(qiáng);霍紅衛(wèi);;一組提高存儲(chǔ)效率的深度包檢測(cè)算法[J];軟件學(xué)報(bào);2011年01期

5 楊毅夫;劉燕兵;劉萍;郭牧怡;郭莉;;正則表達(dá)式的DFA壓縮算法[J];通信學(xué)報(bào);2009年S1期

本文編號(hào)：2529523