動態規劃理論在DSAMDP方法中的優化研究

趙旭，王偉

西安工程大學計算機科學學院，西安 710048

動態規劃理論在DSAMDP方法中的優化研究

趙旭，王偉

西安工程大學計算機科學學院，西安 710048

1 引言

網絡入侵檢測系統（NIDS）是對網絡中的惡意行為進行識別和處理的系統。隨著網絡速度的提高，對網絡入侵檢測系統的檢測效率提出更高的要求[1]。如何使網絡入侵檢測系統在提高檢測效率的同時保持較低的丟包率和漏檢率，成為該領域內一個研究熱點。

M.Arun等人[2]提出在網絡入侵檢測系統中使用的特征碼檢測技術（SDT）來解決這一問題，Sravani，K等人[3]提出使用分類算法對待檢網絡流量進行數據分類，一些研究者通過聚類算法對入侵檢測系統進行改進，例如劉鳳珠[4]提出了一種改進的K均值聚類算法來提高入侵檢測系統的檢測準確率并降低漏檢率，只是該方法在K取值3到6之間時，有一定的不穩定性。姜參等人[5]提出了一種改進的蟻群聚類的入侵檢測方法來提高檢測率，但是該方法對于未知攻擊的檢測效率較低。朱映映等人[6]提出一種基于深度協議分析對網絡事件進行重新解構的方法來提高系統的檢測精度和速度，同時大幅度地減少了規則庫冗余。王明定[7]等人提出了基于自適應宏流的HASLF分流算法，該算法在丟包率、流破壞數和負載均衡度三個方面均有較強的優越性，只是對跨越多個流的攻擊（如DDoS等）在進行負載均衡時如何有效地減少攻擊證據的破壞，對HASLF算法的硬件實現如何進行優化這兩個問題尚未提出解決方案。趙艷君[8]設計了基于數據挖掘的改進網絡入侵檢測系統模型，該模型在提高系統的檢測率的同時，降低了漏報率。還有一些學者借助粒子群優化算法對入侵檢測系統進行改進。例如吳慶濤[9]等人提出了一種基于粒子群優化的入侵特征選擇算法，以減少特征選擇時間。李正潔[10]將量子粒子群優化算法與免疫原理、移動Agent技術結合，提出組合入侵檢測模型，該模型提高了檢測速度，但是卻存在陷入局部最優問題。而范軒苗[11]、燕紅文[12]、董世博[13]等人另辟蹊徑，通過改進模式匹配算法來提高系統的匹配效率。

在眾多的研究方法中，筆者首次提出通過對網絡流量中多媒體數據單獨處理的方法[14]來降低網絡入侵檢測系統的丟包率，收效良好。在之后對此問題的研究中又提出使用DSAMDP方法[15]進一步改善效果。本文在此基礎上，使用動態規劃理論來優化DSAMDP方法的決策過程，使系統將有限的處理能力集中處理更危險的多媒體信息。

2 DSAMDP方法

網絡入侵檢測系統的常規檢測方法是對所有數據包根據協議、地址、端口等特征分類后進行數千條規則的模式匹配，通常不將多媒體數據包與其他數據包區分對待。這就使占網絡流量比例較大、相對而言較為安全的多媒體數據包成為消耗網絡入侵檢測系統硬件資源的“大戶”。

為解決這一問題，曾設計了對網絡流量中多媒體數據包識別和兩種單獨的處理方法[15]，并依此實現DSAMDP方法。這兩種處理方法具體為：

（1）放行方法：考慮來自服務器的多媒體信息相對來自客戶端的較為安全，所以將網絡流量中從服務器發出的多媒體數據包標記，越過網絡入侵檢測系統常規的規則匹配過程。采用該方法可使系統獲得較高的執行效率和較低的丟包率，但如遇到攜帶有危險信息的多媒體數據包，漏檢率會提高[15]。

（2）相應媒體類型檢測方法：該方法將各類多媒體數據可能攜帶的攻擊特征都放到專門為之建立的多媒體數據規則庫中，當發現流量中的多媒體數據包，就按照其攜帶的多媒體數據類型進行相應檢測。因為針對具體多媒體類別制定的檢測規則數量少于系統默認的檢測規則數量，所以這種方法的執行效率雖然較放行方法低，但漏檢率也降低。

經實驗證明[15]，以上兩種方法與系統常規檢測方法相比，執行效率和丟包率閾值都有所提高（如表1和圖1所示）。

表1 三種方法的檢測效率、丟包率和漏檢率方面比較

圖1 三種不同處理方法的丟包閾值

圖1顯示了三種處理方法的丟包閾值與網絡流量之間的關系，由此提出DSAMDP方法，其基本思想[15]如下：

（1）當系統啟動后首先按照常規檢測方法工作，并且對網絡流量進行監測，根據一段時間內相對穩定的網絡流量所處的區間（即小于W1、W1至W2之間、W2至W3之間、W3以上四個區間），在常規檢測、相應媒體類型檢測、放行三種方法中選擇適當的方法處理，使系統盡量不出現丟包。如果網絡流量數值從一個區間跨越到另一個區間，應重新選擇處理方法。

（2）如果當前處理方法為相應媒體類型檢測，并且網絡流量在W1至W2區間內（在此區間內系統還有剩余處理能力），則應在不丟包前提下，通過遞增方式使用常規檢測方法處理更多的多媒體數據包，如果發生丟包，立即通過遞減方式減少處理多媒體數據包。

（3）如果當前處理方法為放行，并且網絡流量在W2至W3區間內（在此區間內系統還有剩余處理能力），則應在不丟包的前提下，通過遞增方式使用相應媒體類型檢測方法處理更多的多媒體數據包，如果發生丟包，立即通過遞減方式減少處理多媒體數據包[15]。

3 動態規劃

動態規劃是一種解決復雜系統優化問題的方法，是目前解決多階段決策問題的基本理論之一。在多階段決策過程中，根據每一步所選決策的不同，將隨即引起狀態的轉移，最終在變化的狀態中產生一個決策序列。動態規劃的目的是使整個過程的決策序列達到最優效果。

動態規劃的基本原理：

動態規劃的基本原理可以略述為：不論過去的狀態和決策如何，對于前面的決策形成的當前的狀態而言，余下的各個決策必定構成最優策略。

動態規劃的基本方程如下：

其中fn+1(xn+1)=δ(xn+1)是決策過程的終端條件，δ為一個已知函數。當xn+1只取固定的狀態時稱固定終端；當xn+1可在終端集合Xn+1中變動時稱自由終端。最終要求的最優指標函數滿足式（2）：

式（1）是一個遞歸公式，如果目標狀態確定，可以直接利用該公式遞歸求出最優值，但在實際應用中通常將該遞歸公式改為遞推公式求解，這樣效率會更高一些。

4 動態規劃理論對DSAMDP方法的優化過程

4.1 優化方案

雖然多媒體數據包相對安全，但也不能掉以輕心。在DSAMDP方法的步驟2和3中，在不丟包的前提下，會使用更安全的方法優先處理一些更具危險性的多媒體數據包（例如腳本程序、flash、圖片等）。但是這些多媒體數據包如何選擇，既要保證所選擇的多媒體數據包序列不會造成系統超出負載能力，又要使該選擇序列的信息危險度最大化，就成為本節研究的問題。

首先定義如下參數：

M為系統的最大載荷，可預先在同等帶寬條件下通過模擬流量測得。

Xi為每時間片內待挑選的某個多媒體數據包。

Wi為多媒體數據包Xi對系統造成的負載，因為模式匹配算法的時間復雜度與待匹配字符串長度呈正相關[6]，所以Wi由數據包負載長度與數據包最大載荷的比值來確定。

Pi為多媒體數據包Xi的危險度，其值根據數據包攜帶的多媒體信息的危險程度而定，例如數據包攜帶octet-stream、x-shockwave-flash、x-javascript等類型的多媒體數據時，該數據包的Pi值會比較高些。

借鑒動態規劃理論，對DSAMDP方法的優化問題可描述如下：

在圖1的W1～W2（或W2～W3）區間內的每個時間片中，從X1,X2,…,Xn序列中挑選出一個危險度最大的序列使用常規檢測方法（如在W2～W3，使用相應媒體類型檢測方法）來處理，所以，該優化問題可以理解為求解每個時間片內選取的危險性最高的多媒體數據包序列，即：

注：Xi為0表示該數據包未被選中，為1表示被選中。

4.2 優化方案可行性的證明

根據動態規劃法基本要素，能否使用動態規劃理論，必須分析問題解的結構，考察它的最優解是否具有最有子結構特性，其次，應當檢查分解所得的子問題是否相互獨立，是否存在重疊子問題現象。

證明假設(X1,X2,…,Xn)，Xi∈{0,1}是本問題每個時間片內多媒體數據包選取的最優解，則(X2,X3,…,Xn)必是子時間片內的最優解：系統最大載荷為M-W1X1，該子時間片內共有n-1個多媒體數據包，第i(1≤i≤n)個多媒體數據包對網絡入侵檢測系統造成的負載為Wi，該數據包的危險性為Pi(Pi＞0)。如若不然，設則(Z2,Z3,…,Zn)是子時間片內的最優解，而(X1,X2,…,Xn)不是子時間片內的最優解。那么，由此可知，必有：

顯然，(X1,Z2,…,Zn)是比(X1,X2,…,Xn)危險性更高的最優解，則(X1,X2,…,Xn)不是該時間片內的最優解。這與假設相矛盾，所以(X2,X3,…,Xn)必是子時間片內的最優解。由此可見，通過動態規劃理論對動態自適應多媒體數據處理方法的優化問題具有最有子結構特性，可以使用。

4.3 具體優化過程

根據動態規劃理論和優化方案的定義，可獲得狀態轉移方程：

fi(M)表示在最大載荷為M的系統中，前i個被挑選的多媒體數據包可獲得的最大危險度。根據該式，即可求得待檢多媒體數據包的最優選擇序列。

下面是根據式（4）用遞歸方式實現優化方案的關鍵代碼

在以上程序中，執行頻度最大的部分是內層for循環中的語句，由于有一個兩重for循環，循環次數為n×m，所以它的執行次數也是n×m次，那么該優化方法的時間復雜度為O(nm)。

5 實驗結果

5.1 實驗環境

本文所使用的實驗數據是由麻省理工學院林肯實驗室的KDD CUP 99數據集和背景流量混合而成。KDD CUP 99數據集中包括了四大類網絡攻擊類型[16]：DoS、R2L、U2R和PROBE，背景流量是預先在網絡捕獲的真實流量，含有大量多媒體數據包。實驗將通過這兩種混合流量來對比優化前后的效果。

實驗環境配置如下：

（1）處理器：AMD A10-5800K 4核

（2）內存：4 GB DDR3

（3）操作系統：Windows 7

在測試之前，首先對不同的多媒體類型設定危險度（如表2所示），其值根據易攜帶危險信息的程度而定，例如octet-stream類型可攜帶exe文件，所以它的危險度設定較高。

表2 部分多媒體類型設定的危險度

5.2 測試結果及分析

本文設置了三組實驗，第一組通過同一段流量測試優化前后多個時間片內所選多媒體數據包序列的危險度差異（如圖2所示）。

圖2 優化前后不同時間片內所選多媒體數據包序列的危險度對比

第二組實驗通過同一段流量測試優化前后不同危險度的多媒體數據包的檢測比例（如表3所示）。

表3 不同危險度的多媒體數據包在優化前后檢測比例對比

在表3中可以看出，優化后危險度相對較高的多媒體數據包的檢測率有了不同程度的提升，例如octet-stream類型提升了84%，x-JavaScript類型提升了75%，提升幅度較大的原因除了優化的作用以外，還考慮到優化前這些數據被隨機檢測，加之總數較少，所以基數較低。另一方面，也可以看出危險度較低的多媒體數據包檢測率出現下降，如html類型下降18%。

第三組實驗測試優化前后系統丟包率的變化（如圖3所示）。

圖3 優化前后丟包率對比

在圖3中可以看出，優化前后的丟包率變化基本不大，優化后丟包率略高一些的原因考慮是優化過程中為選擇數據包序列而耗費系統資源造成。

6 結束語

在提出的網絡入侵檢測系統中使用動態自適應多媒體數據處理方法降低丟包率的基礎上，使用動態規劃理論對該方法的決策過程進行優化，使每個時間片內選取的多媒體數據包序列的危險度達到最高。通過優化，使網絡入侵檢測系統將有限的處理能力集中處理那些更具危險性的多媒體數據包。實驗結果表明，該方法可提高系統對高危多媒體信息的檢測率。

[1]史志才，夏永祥.高速網絡環境下的入侵檢測技術研究綜述[J].計算機應用研究，2010，27（5）：1606-1610.

[2]Arun M，Krishnan A.Functional verification of signature detection architectures for high speed network applications[J].International Journal of Automation and Computing，2012，9（4）.

[3]SravaniK，SrinivasuP.Comparativestudyofmachine learning algorithm for intrusion detection system[J].Advances in Intelligent Systems and Computing，2014，247：189-196.

[4]Liu Fengzhu.A clustering method for anomaly intrusion detection[J].Computer Security，2013，8：2-6.

[5]姜參，王大偉.一種改進蟻群聚類的入侵檢測方法[J/OL].計算機技術與發展，2013（12）.http：//www.cnki.net/kcms/ detail/61.1450.TP.20130929.1548.060.html.

[6]朱映映，吳錦鋒，朱艷艷，等.網絡入侵檢測中的深度協議分析方法[J].計算機應用研究，2012，29（5）：1891-1895.

[7]王明定，趙國鴻，陸華彪.基于網絡流量特性分析的高速入侵檢測分流算法[J].計算機應用研究，2010，27（9）：3484-3486.

[8]趙艷君，魏明軍.改進數據挖掘算法在入侵檢測系統中的應用[J].計算機工程與應用，2013，49（18）：69-72.

[9]吳慶濤，曹繼邦，鄭瑞娟.基于粒子群優化的入侵特征選擇算法[J].計算機工程與應用，2013，49（7）：89-92.

[10]李正潔，李永忠，徐磊.免疫Agent和量子粒子群優化的入侵檢測方法研究[J].計算機工程與應用，2012，48（1）：102-104.

[11]范軒苗，鄭寧，范淵.Web入侵檢測系統高效多模式匹配算法[J].計算機應用研究，2009，26（4）：1528-1531.

[12]燕紅文.基于Snort的改進BMH單模式匹配算法研究[J].計算機工程與應用，2012，48（31）：78-80.

[13]董世博，李訓根，殷珍珍.一種改進的字符串多模式匹配算法[J].計算機工程與應用，2013，49（8）：133-137.

[14]趙旭，王長山.Snort入侵檢測系統的改進[J].西安工程大學學報，2006，21（6）：859-863.

[15]趙旭.基于Snort的動態自適應多媒體數據處理方法研究[J].計算機系統應用，2011，20（4）：211-213.

[16]Zhang Xinyou.Research of intrusion detection system dataset-KDD CUP99[J].Computer Engineering and Design，2010，31（22）：4809-4812.

ZHAO Xu,WANG Wei

College of Computer Science,Xi’an Polytechnic University,Xi’an 710048,China

There is always a high packet loss rate in the network intrusion detection system,especially when the network traffic is high.The author once raised the method of Dynamic Self-Adapting Multimedia Data Processing（DSAMDP）to reduce the packet loss rate and

good results.On the basis of the above,the idea of optimization in dynamic programming theory is applied to optimize the decision-making steps of the Dynamic Self-Adapting Multimedia Data Processing method.While taking into account of system load capacity,this method can find an optimum solution to how to select the highest risk of multimedia data packet sequence in each time unit.In this way,the limited processing power of network intrusion detection system can be focused on the more dangerous multimedia data packets.Experiments show that this method can let system improve the detection rate of the high risk of multimedia information

Network Intrusion Detection System（NIDS）;multimedia;dynamic programming theory;Dynamic Self-Adapting Multimedia Data Processing（DSAMDP）;optimizing

網絡入侵檢測系統在流量大的情況下經常會出現較高的丟包率，曾提出通過DSAMDP（Dynamic Self-Adapting Multimedia Data Processing，動態自適應多媒體數據處理）方法來解決這一問題，收效良好。在此基礎上，使用動態規劃理論對DSAMDP方法的決策過程進行優化，在兼顧系統負載能力的同時，使每個時間片內選取的多媒體數據包序列的危險度達到最高。這種方法可使網絡入侵檢測系統將有限的處理能力集中處理那些更具危險性的多媒體數據包。實驗結果表明，該方法可提高系統對高危多媒體信息的檢測率。

網絡入侵；多媒體；動態規劃理論；動態自適應多媒體數據處理（DSAMDP）；優化

A

TP393.08

10.3778/j.issn.1002-8331.1402-0080

ZHAO Xu,WANG Wei.Optimization research of DSAMDP method with dynamic programming theory.Computer Engineering and Applications,2014,50（22）：83-87.

陜西省教育廳科研計劃項目資助（No.2010JK568）；中國博士后科學基金項目（No.20090451384）。

趙旭（1978—），男，講師，研究領域為網絡安全；王偉（1969—），男，博士后，副教授，研究領域為網絡性能評估，網絡信息安全。E-mail：37274679@qq.com

2014-02-12

2014-05-06

1002-8331（2014）22-0083-05

CNKI網絡優先出版：2014-06-18,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1402-0080.html