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

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

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

【參考文獻】

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

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

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

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

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

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

本文編號：2529523