趙旭,王偉
西安工程大學(xué)計(jì)算機(jī)科學(xué)學(xué)院,西安 710048
動態(tài)規(guī)劃理論在DSAMDP方法中的優(yōu)化研究
趙旭,王偉
西安工程大學(xué)計(jì)算機(jī)科學(xué)學(xué)院,西安 710048
網(wǎng)絡(luò)入侵檢測系統(tǒng)(NIDS)是對網(wǎng)絡(luò)中的惡意行為進(jìn)行識別和處理的系統(tǒng)。隨著網(wǎng)絡(luò)速度的提高,對網(wǎng)絡(luò)入侵檢測系統(tǒng)的檢測效率提出更高的要求[1]。如何使網(wǎng)絡(luò)入侵檢測系統(tǒng)在提高檢測效率的同時保持較低的丟包率和漏檢率,成為該領(lǐng)域內(nèi)一個研究熱點(diǎn)。
M.Arun等人[2]提出在網(wǎng)絡(luò)入侵檢測系統(tǒng)中使用的特征碼檢測技術(shù)(SDT)來解決這一問題,Sravani,K等人[3]提出使用分類算法對待檢網(wǎng)絡(luò)流量進(jìn)行數(shù)據(jù)分類,一些研究者通過聚類算法對入侵檢測系統(tǒng)進(jìn)行改進(jìn),例如劉鳳珠[4]提出了一種改進(jìn)的K均值聚類算法來提高入侵檢測系統(tǒng)的檢測準(zhǔn)確率并降低漏檢率,只是該方法在K取值3到6之間時,有一定的不穩(wěn)定性。姜參等人[5]提出了一種改進(jìn)的蟻群聚類的入侵檢測方法來提高檢測率,但是該方法對于未知攻擊的檢測效率較低。朱映映等人[6]提出一種基于深度協(xié)議分析對網(wǎng)絡(luò)事件進(jìn)行重新解構(gòu)的方法來提高系統(tǒng)的檢測精度和速度,同時大幅度地減少了規(guī)則庫冗余。王明定[7]等人提出了基于自適應(yīng)宏流的HASLF分流算法,該算法在丟包率、流破壞數(shù)和負(fù)載均衡度三個方面均有較強(qiáng)的優(yōu)越性,只是對跨越多個流的攻擊(如DDoS等)在進(jìn)行負(fù)載均衡時如何有效地減少攻擊證據(jù)的破壞,對HASLF算法的硬件實(shí)現(xiàn)如何進(jìn)行優(yōu)化這兩個問題尚未提出解決方案。趙艷君[8]設(shè)計(jì)了基于數(shù)據(jù)挖掘的改進(jìn)網(wǎng)絡(luò)入侵檢測系統(tǒng)模型,該模型在提高系統(tǒng)的檢測率的同時,降低了漏報(bào)率。還有一些學(xué)者借助粒子群優(yōu)化算法對入侵檢測系統(tǒng)進(jìn)行改進(jìn)。例如吳慶濤[9]等人提出了一種基于粒子群優(yōu)化的入侵特征選擇算法,以減少特征選擇時間。李正潔[10]將量子粒子群優(yōu)化算法與免疫原理、移動Agent技術(shù)結(jié)合,提出組合入侵檢測模型,該模型提高了檢測速度,但是卻存在陷入局部最優(yōu)問題。而范軒苗[11]、燕紅文[12]、董世博[13]等人另辟蹊徑,通過改進(jìn)模式匹配算法來提高系統(tǒng)的匹配效率。
在眾多的研究方法中,筆者首次提出通過對網(wǎng)絡(luò)流量中多媒體數(shù)據(jù)單獨(dú)處理的方法[14]來降低網(wǎng)絡(luò)入侵檢測系統(tǒng)的丟包率,收效良好。在之后對此問題的研究中又提出使用DSAMDP方法[15]進(jìn)一步改善效果。本文在此基礎(chǔ)上,使用動態(tài)規(guī)劃理論來優(yōu)化DSAMDP方法的決策過程,使系統(tǒng)將有限的處理能力集中處理更危險(xiǎn)的多媒體信息。
網(wǎng)絡(luò)入侵檢測系統(tǒng)的常規(guī)檢測方法是對所有數(shù)據(jù)包根據(jù)協(xié)議、地址、端口等特征分類后進(jìn)行數(shù)千條規(guī)則的模式匹配,通常不將多媒體數(shù)據(jù)包與其他數(shù)據(jù)包區(qū)分對待。這就使占網(wǎng)絡(luò)流量比例較大、相對而言較為安全的多媒體數(shù)據(jù)包成為消耗網(wǎng)絡(luò)入侵檢測系統(tǒng)硬件資源的“大戶”。
為解決這一問題,曾設(shè)計(jì)了對網(wǎng)絡(luò)流量中多媒體數(shù)據(jù)包識別和兩種單獨(dú)的處理方法[15],并依此實(shí)現(xiàn)DSAMDP方法。這兩種處理方法具體為:
(1)放行方法:考慮來自服務(wù)器的多媒體信息相對來自客戶端的較為安全,所以將網(wǎng)絡(luò)流量中從服務(wù)器發(fā)出的多媒體數(shù)據(jù)包標(biāo)記,越過網(wǎng)絡(luò)入侵檢測系統(tǒng)常規(guī)的規(guī)則匹配過程。采用該方法可使系統(tǒng)獲得較高的執(zhí)行效率和較低的丟包率,但如遇到攜帶有危險(xiǎn)信息的多媒體數(shù)據(jù)包,漏檢率會提高[15]。
(2)相應(yīng)媒體類型檢測方法:該方法將各類多媒體數(shù)據(jù)可能攜帶的攻擊特征都放到專門為之建立的多媒體數(shù)據(jù)規(guī)則庫中,當(dāng)發(fā)現(xiàn)流量中的多媒體數(shù)據(jù)包,就按照其攜帶的多媒體數(shù)據(jù)類型進(jìn)行相應(yīng)檢測。因?yàn)獒槍唧w多媒體類別制定的檢測規(guī)則數(shù)量少于系統(tǒng)默認(rèn)的檢測規(guī)則數(shù)量,所以這種方法的執(zhí)行效率雖然較放行方法低,但漏檢率也降低。
經(jīng)實(shí)驗(yàn)證明[15],以上兩種方法與系統(tǒng)常規(guī)檢測方法相比,執(zhí)行效率和丟包率閾值都有所提高(如表1和圖1所示)。
表1 三種方法的檢測效率、丟包率和漏檢率方面比較
圖1 三種不同處理方法的丟包閾值
圖1顯示了三種處理方法的丟包閾值與網(wǎng)絡(luò)流量之間的關(guān)系,由此提出DSAMDP方法,其基本思想[15]如下:
(1)當(dāng)系統(tǒng)啟動后首先按照常規(guī)檢測方法工作,并且對網(wǎng)絡(luò)流量進(jìn)行監(jiān)測,根據(jù)一段時間內(nèi)相對穩(wěn)定的網(wǎng)絡(luò)流量所處的區(qū)間(即小于W1、W1至W2之間、W2至W3之間、W3以上四個區(qū)間),在常規(guī)檢測、相應(yīng)媒體類型檢測、放行三種方法中選擇適當(dāng)?shù)姆椒ㄌ幚恚瓜到y(tǒng)盡量不出現(xiàn)丟包。如果網(wǎng)絡(luò)流量數(shù)值從一個區(qū)間跨越到另一個區(qū)間,應(yīng)重新選擇處理方法。
(2)如果當(dāng)前處理方法為相應(yīng)媒體類型檢測,并且網(wǎng)絡(luò)流量在W1至W2區(qū)間內(nèi)(在此區(qū)間內(nèi)系統(tǒng)還有剩余處理能力),則應(yīng)在不丟包前提下,通過遞增方式使用常規(guī)檢測方法處理更多的多媒體數(shù)據(jù)包,如果發(fā)生丟包,立即通過遞減方式減少處理多媒體數(shù)據(jù)包。
(3)如果當(dāng)前處理方法為放行,并且網(wǎng)絡(luò)流量在W2至W3區(qū)間內(nèi)(在此區(qū)間內(nèi)系統(tǒng)還有剩余處理能力),則應(yīng)在不丟包的前提下,通過遞增方式使用相應(yīng)媒體類型檢測方法處理更多的多媒體數(shù)據(jù)包,如果發(fā)生丟包,立即通過遞減方式減少處理多媒體數(shù)據(jù)包[15]。
動態(tài)規(guī)劃是一種解決復(fù)雜系統(tǒng)優(yōu)化問題的方法,是目前解決多階段決策問題的基本理論之一。在多階段決策過程中,根據(jù)每一步所選決策的不同,將隨即引起狀態(tài)的轉(zhuǎn)移,最終在變化的狀態(tài)中產(chǎn)生一個決策序列。動態(tài)規(guī)劃的目的是使整個過程的決策序列達(dá)到最優(yōu)效果。
動態(tài)規(guī)劃的基本原理:
動態(tài)規(guī)劃的基本原理可以略述為:不論過去的狀態(tài)和決策如何,對于前面的決策形成的當(dāng)前的狀態(tài)而言,余下的各個決策必定構(gòu)成最優(yōu)策略。
動態(tài)規(guī)劃的基本方程如下:
其中fn+1(xn+1)=δ(xn+1)是決策過程的終端條件,δ為一個已知函數(shù)。當(dāng)xn+1只取固定的狀態(tài)時稱固定終端;當(dāng)xn+1可在終端集合Xn+1中變動時稱自由終端。最終要求的最優(yōu)指標(biāo)函數(shù)滿足式(2):
式(1)是一個遞歸公式,如果目標(biāo)狀態(tài)確定,可以直接利用該公式遞歸求出最優(yōu)值,但在實(shí)際應(yīng)用中通常將該遞歸公式改為遞推公式求解,這樣效率會更高一些。
4.1 優(yōu)化方案
雖然多媒體數(shù)據(jù)包相對安全,但也不能掉以輕心。在DSAMDP方法的步驟2和3中,在不丟包的前提下,會使用更安全的方法優(yōu)先處理一些更具危險(xiǎn)性的多媒體數(shù)據(jù)包(例如腳本程序、flash、圖片等)。但是這些多媒體數(shù)據(jù)包如何選擇,既要保證所選擇的多媒體數(shù)據(jù)包序列不會造成系統(tǒng)超出負(fù)載能力,又要使該選擇序列的信息危險(xiǎn)度最大化,就成為本節(jié)研究的問題。
首先定義如下參數(shù):
M為系統(tǒng)的最大載荷,可預(yù)先在同等帶寬條件下通過模擬流量測得。
Xi為每時間片內(nèi)待挑選的某個多媒體數(shù)據(jù)包。
Wi為多媒體數(shù)據(jù)包Xi對系統(tǒng)造成的負(fù)載,因?yàn)槟J狡ヅ渌惴ǖ臅r間復(fù)雜度與待匹配字符串長度呈正相關(guān)[6],所以Wi由數(shù)據(jù)包負(fù)載長度與數(shù)據(jù)包最大載荷的比值來確定。
Pi為多媒體數(shù)據(jù)包Xi的危險(xiǎn)度,其值根據(jù)數(shù)據(jù)包攜帶的多媒體信息的危險(xiǎn)程度而定,例如數(shù)據(jù)包攜帶octet-stream、x-shockwave-flash、x-javascript等類型的多媒體數(shù)據(jù)時,該數(shù)據(jù)包的Pi值會比較高些。
借鑒動態(tài)規(guī)劃理論,對DSAMDP方法的優(yōu)化問題可描述如下:
在圖1的W1~W2(或W2~W3)區(qū)間內(nèi)的每個時間片中,從X1,X2,…,Xn序列中挑選出一個危險(xiǎn)度最大的序列使用常規(guī)檢測方法(如在W2~W3,使用相應(yīng)媒體類型檢測方法)來處理,所以,該優(yōu)化問題可以理解為求解每個時間片內(nèi)選取的危險(xiǎn)性最高的多媒體數(shù)據(jù)包序列,即:
注:Xi為0表示該數(shù)據(jù)包未被選中,為1表示被選中。
4.2 優(yōu)化方案可行性的證明
根據(jù)動態(tài)規(guī)劃法基本要素,能否使用動態(tài)規(guī)劃理論,必須分析問題解的結(jié)構(gòu),考察它的最優(yōu)解是否具有最有子結(jié)構(gòu)特性,其次,應(yīng)當(dāng)檢查分解所得的子問題是否相互獨(dú)立,是否存在重疊子問題現(xiàn)象。
證明假設(shè)(X1,X2,…,Xn),Xi∈{0,1}是本問題每個時間片內(nèi)多媒體數(shù)據(jù)包選取的最優(yōu)解,則(X2,X3,…,Xn)必是子時間片內(nèi)的最優(yōu)解:系統(tǒng)最大載荷為M-W1X1,該子時間片內(nèi)共有n-1個多媒體數(shù)據(jù)包,第i(1≤i≤n)個多媒體數(shù)據(jù)包對網(wǎng)絡(luò)入侵檢測系統(tǒng)造成的負(fù)載為Wi,該數(shù)據(jù)包的危險(xiǎn)性為Pi(Pi>0)。如若不然,設(shè)則(Z2,Z3,…,Zn)是子時間片內(nèi)的最優(yōu)解,而(X1,X2,…,Xn)不是子時間片內(nèi)的最優(yōu)解。那么,由此可知,必有:
顯然,(X1,Z2,…,Zn)是比(X1,X2,…,Xn)危險(xiǎn)性更高的最優(yōu)解,則(X1,X2,…,Xn)不是該時間片內(nèi)的最優(yōu)解。這與假設(shè)相矛盾,所以(X2,X3,…,Xn)必是子時間片內(nèi)的最優(yōu)解。由此可見,通過動態(tài)規(guī)劃理論對動態(tài)自適應(yīng)多媒體數(shù)據(jù)處理方法的優(yōu)化問題具有最有子結(jié)構(gòu)特性,可以使用。
4.3 具體優(yōu)化過程
根據(jù)動態(tài)規(guī)劃理論和優(yōu)化方案的定義,可獲得狀態(tài)轉(zhuǎn)移方程:
fi(M)表示在最大載荷為M的系統(tǒng)中,前i個被挑選的多媒體數(shù)據(jù)包可獲得的最大危險(xiǎn)度。根據(jù)該式,即可求得待檢多媒體數(shù)據(jù)包的最優(yōu)選擇序列。
下面是根據(jù)式(4)用遞歸方式實(shí)現(xiàn)優(yōu)化方案的關(guān)鍵代碼
在以上程序中,執(zhí)行頻度最大的部分是內(nèi)層for循環(huán)中的語句,由于有一個兩重for循環(huán),循環(huán)次數(shù)為n×m,所以它的執(zhí)行次數(shù)也是n×m次,那么該優(yōu)化方法的時間復(fù)雜度為O(nm)。
5.1 實(shí)驗(yàn)環(huán)境
本文所使用的實(shí)驗(yàn)數(shù)據(jù)是由麻省理工學(xué)院林肯實(shí)驗(yàn)室的KDD CUP 99數(shù)據(jù)集和背景流量混合而成。KDD CUP 99數(shù)據(jù)集中包括了四大類網(wǎng)絡(luò)攻擊類型[16]:DoS、R2L、U2R和PROBE,背景流量是預(yù)先在網(wǎng)絡(luò)捕獲的真實(shí)流量,含有大量多媒體數(shù)據(jù)包。實(shí)驗(yàn)將通過這兩種混合流量來對比優(yōu)化前后的效果。
實(shí)驗(yàn)環(huán)境配置如下:
(1)處理器:AMD A10-5800K 4核
(2)內(nèi)存:4 GB DDR3
(3)操作系統(tǒng):Windows 7
在測試之前,首先對不同的多媒體類型設(shè)定危險(xiǎn)度(如表2所示),其值根據(jù)易攜帶危險(xiǎn)信息的程度而定,例如octet-stream類型可攜帶exe文件,所以它的危險(xiǎn)度設(shè)定較高。
表2 部分多媒體類型設(shè)定的危險(xiǎn)度
5.2 測試結(jié)果及分析
本文設(shè)置了三組實(shí)驗(yàn),第一組通過同一段流量測試優(yōu)化前后多個時間片內(nèi)所選多媒體數(shù)據(jù)包序列的危險(xiǎn)度差異(如圖2所示)。
圖2 優(yōu)化前后不同時間片內(nèi)所選多媒體數(shù)據(jù)包序列的危險(xiǎn)度對比
第二組實(shí)驗(yàn)通過同一段流量測試優(yōu)化前后不同危險(xiǎn)度的多媒體數(shù)據(jù)包的檢測比例(如表3所示)。
表3 不同危險(xiǎn)度的多媒體數(shù)據(jù)包在優(yōu)化前后檢測比例對比
在表3中可以看出,優(yōu)化后危險(xiǎn)度相對較高的多媒體數(shù)據(jù)包的檢測率有了不同程度的提升,例如octet-stream類型提升了84%,x-JavaScript類型提升了75%,提升幅度較大的原因除了優(yōu)化的作用以外,還考慮到優(yōu)化前這些數(shù)據(jù)被隨機(jī)檢測,加之總數(shù)較少,所以基數(shù)較低。另一方面,也可以看出危險(xiǎn)度較低的多媒體數(shù)據(jù)包檢測率出現(xiàn)下降,如html類型下降18%。
第三組實(shí)驗(yàn)測試優(yōu)化前后系統(tǒng)丟包率的變化(如圖3所示)。
圖3 優(yōu)化前后丟包率對比
在圖3中可以看出,優(yōu)化前后的丟包率變化基本不大,優(yōu)化后丟包率略高一些的原因考慮是優(yōu)化過程中為選擇數(shù)據(jù)包序列而耗費(fèi)系統(tǒng)資源造成。
在提出的網(wǎng)絡(luò)入侵檢測系統(tǒng)中使用動態(tài)自適應(yīng)多媒體數(shù)據(jù)處理方法降低丟包率的基礎(chǔ)上,使用動態(tài)規(guī)劃理論對該方法的決策過程進(jìn)行優(yōu)化,使每個時間片內(nèi)選取的多媒體數(shù)據(jù)包序列的危險(xiǎn)度達(dá)到最高。通過優(yōu)化,使網(wǎng)絡(luò)入侵檢測系統(tǒng)將有限的處理能力集中處理那些更具危險(xiǎn)性的多媒體數(shù)據(jù)包。實(shí)驗(yàn)結(jié)果表明,該方法可提高系統(tǒng)對高危多媒體信息的檢測率。
[1]史志才,夏永祥.高速網(wǎng)絡(luò)環(huán)境下的入侵檢測技術(shù)研究綜述[J].計(jì)算機(jī)應(yīng)用研究,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ìn)蟻群聚類的入侵檢測方法[J/OL].計(jì)算機(jī)技術(shù)與發(fā)展,2013(12).http://www.cnki.net/kcms/ detail/61.1450.TP.20130929.1548.060.html.
[6]朱映映,吳錦鋒,朱艷艷,等.網(wǎng)絡(luò)入侵檢測中的深度協(xié)議分析方法[J].計(jì)算機(jī)應(yīng)用研究,2012,29(5):1891-1895.
[7]王明定,趙國鴻,陸華彪.基于網(wǎng)絡(luò)流量特性分析的高速入侵檢測分流算法[J].計(jì)算機(jī)應(yīng)用研究,2010,27(9):3484-3486.
[8]趙艷君,魏明軍.改進(jìn)數(shù)據(jù)挖掘算法在入侵檢測系統(tǒng)中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(18):69-72.
[9]吳慶濤,曹繼邦,鄭瑞娟.基于粒子群優(yōu)化的入侵特征選擇算法[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(7):89-92.
[10]李正潔,李永忠,徐磊.免疫Agent和量子粒子群優(yōu)化的入侵檢測方法研究[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(1):102-104.
[11]范軒苗,鄭寧,范淵.Web入侵檢測系統(tǒng)高效多模式匹配算法[J].計(jì)算機(jī)應(yīng)用研究,2009,26(4):1528-1531.
[12]燕紅文.基于Snort的改進(jìn)BMH單模式匹配算法研究[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(31):78-80.
[13]董世博,李訓(xùn)根,殷珍珍.一種改進(jìn)的字符串多模式匹配算法[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(8):133-137.
[14]趙旭,王長山.Snort入侵檢測系統(tǒng)的改進(jìn)[J].西安工程大學(xué)學(xué)報(bào),2006,21(6):859-863.
[15]趙旭.基于Snort的動態(tài)自適應(yīng)多媒體數(shù)據(jù)處理方法研究[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,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
網(wǎng)絡(luò)入侵檢測系統(tǒng)在流量大的情況下經(jīng)常會出現(xiàn)較高的丟包率,曾提出通過DSAMDP(Dynamic Self-Adapting Multimedia Data Processing,動態(tài)自適應(yīng)多媒體數(shù)據(jù)處理)方法來解決這一問題,收效良好。在此基礎(chǔ)上,使用動態(tài)規(guī)劃理論對DSAMDP方法的決策過程進(jìn)行優(yōu)化,在兼顧系統(tǒng)負(fù)載能力的同時,使每個時間片內(nèi)選取的多媒體數(shù)據(jù)包序列的危險(xiǎn)度達(dá)到最高。這種方法可使網(wǎng)絡(luò)入侵檢測系統(tǒng)將有限的處理能力集中處理那些更具危險(xiǎn)性的多媒體數(shù)據(jù)包。實(shí)驗(yàn)結(jié)果表明,該方法可提高系統(tǒng)對高危多媒體信息的檢測率。
網(wǎng)絡(luò)入侵;多媒體;動態(tài)規(guī)劃理論;動態(tài)自適應(yīng)多媒體數(shù)據(jù)處理(DSAMDP);優(yōu)化
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.
陜西省教育廳科研計(jì)劃項(xiàng)目資助(No.2010JK568);中國博士后科學(xué)基金項(xiàng)目(No.20090451384)。
趙旭(1978—),男,講師,研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)安全;王偉(1969—),男,博士后,副教授,研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)性能評估,網(wǎng)絡(luò)信息安全。E-mail:37274679@qq.com
2014-02-12
2014-05-06
1002-8331(2014)22-0083-05
CNKI網(wǎng)絡(luò)優(yōu)先出版:2014-06-18,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1402-0080.html