于振洋

(淮陰工學(xué)院計(jì)算機(jī)工程學(xué)院，江蘇 淮安 223003)

0 引言

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，計(jì)算機(jī)網(wǎng)絡(luò)業(yè)務(wù)也呈現(xiàn)出多元化的趨勢(shì)。在網(wǎng)絡(luò)規(guī)模不斷擴(kuò)大的同時(shí)，出現(xiàn)了數(shù)據(jù)流量過大導(dǎo)致網(wǎng)絡(luò)擁塞、惡意攻擊等網(wǎng)絡(luò)崩潰現(xiàn)象，因此，網(wǎng)絡(luò)流量預(yù)測(cè)在現(xiàn)代網(wǎng)絡(luò)中具有重要作用。進(jìn)行流量預(yù)測(cè)能夠使人們實(shí)時(shí)監(jiān)控網(wǎng)絡(luò)流量，在網(wǎng)絡(luò)性能出現(xiàn)惡化之前采取相關(guān)遏制措施。

網(wǎng)絡(luò)流量預(yù)測(cè)一直是研究的重點(diǎn)問題，目前已提出許多預(yù)測(cè)模型和算法。這些預(yù)測(cè)模型和算法主要分為:基于自回歸或自回歸滑動(dòng)平均的預(yù)測(cè)模型、基于自回歸綜合滑動(dòng)平均的預(yù)測(cè)模型、基于分形自回歸綜合滑動(dòng)平均的預(yù)測(cè)模型、基于神經(jīng)網(wǎng)絡(luò)的預(yù)測(cè)模型、結(jié)合小波變換和小波分析的預(yù)測(cè)模型及綜合小波與神經(jīng)網(wǎng)絡(luò)的預(yù)測(cè)模型。當(dāng)人獲得指導(dǎo)信息時(shí)，如何利用這種信息，來進(jìn)一步提高算法的性能是一個(gè)值得研究的課題。流量分析的基礎(chǔ)是對(duì)流量的測(cè)量，如何利用分析所得結(jié)果，反過來指導(dǎo)主動(dòng)式測(cè)量的進(jìn)行，也是非常有意義的課題。

1 基于Boosting的學(xué)習(xí)算法

Boosting是一類使得弱學(xué)習(xí)算法的性能得以提高的學(xué)習(xí)策略。基于Boosting的學(xué)習(xí)算法的思路如下:如果要想找到許多條簡(jiǎn)單粗略的判斷準(zhǔn)則要比找到一條非常精確的準(zhǔn)則容易得多，在Boosting算法中，通過不斷調(diào)用這種“弱的”或“基本的”學(xué)習(xí)算法，每次用訓(xùn)練樣本的不同子集對(duì)它進(jìn)行訓(xùn)練(更確切地說，是訓(xùn)練樣本的不同分布或權(quán)重)，每次被調(diào)用時(shí)，基本的學(xué)習(xí)算法將產(chǎn)生一條新的弱的判斷準(zhǔn)則，循環(huán)多次后，Boosting算法必須把這些弱的準(zhǔn)則結(jié)合成一條準(zhǔn)則，該準(zhǔn)則很可能比弱準(zhǔn)則中任何一條都要精確得多。

以處理二分類問題的ADA－Boost為例，得到基于Boosting的學(xué)習(xí)算法流程如下:

ADA－Boost算法流程:

(1) 給定訓(xùn)練集(x1，y1)，…，(xm，ym)，其中，xt∈ X={－1，+1}，yt∈{－1，+1}。

(2)初始化樣本權(quán)重分布D1(t)=1/N(t=1，…，N)。

(3)迭代過程在每一輪迭代中t(t=1，2，…，T):

(a)利用分布Dt訓(xùn)練一個(gè)弱分類器;

(b)得到弱分類器ht:X→R;

(c)計(jì)算弱分類器的訓(xùn)練誤差st=Prt－Dt［ht(xt) ≠ yt］;

(d)計(jì)算弱分類器重要性αt∈R;

(e)更新樣本權(quán)重分布。

在理論上，ADA－Boost算法的訓(xùn)練誤差的界由下式給出:

其中，f(x)=∑αtht(x)。從上式可知，只要保證在每一輪迭代中，弱分類器的效果比隨機(jī)猜測(cè)要好一點(diǎn)，Boosting算法的訓(xùn)練誤差就會(huì)隨著迭代步數(shù)的增加呈指數(shù)下降趨勢(shì)。從這個(gè)角度看，Boosting算法有效地將一個(gè)弱學(xué)習(xí)算法轉(zhuǎn)化成一個(gè)強(qiáng)學(xué)習(xí)算法(給定足夠多的數(shù)據(jù)，能產(chǎn)生一個(gè)錯(cuò)誤率任意的分類器)。

關(guān)于ADA－Boost的推廣誤差，文獻(xiàn)［7］已經(jīng)分別給出了幾種不同形式的上界，從而在理論上給出了ADA－Boost有效性的一些解釋。

目前，基于Boosting的算法主要應(yīng)用在監(jiān)督問題(大多數(shù)情況下是二分類問題)和異常網(wǎng)絡(luò)流量監(jiān)測(cè)中，本文將主要研究其在非監(jiān)督情況下的應(yīng)用。

2 基于Boosting的異常流量檢測(cè)算法

本節(jié)研究基于Boosting的異常流量檢測(cè)算法，首先給出基于ADA－Boost的算法流程，然后討論算法的各個(gè)實(shí)現(xiàn)細(xì)節(jié)。本文提出兩種不同形式的弱學(xué)習(xí)算法設(shè)計(jì)方式以及相應(yīng)的誤差評(píng)價(jià)分析:估計(jì)多變量高斯分布以及估計(jì)超球體區(qū)域，在前一種策略中，假定正常流量的分布是一種多變量的單高斯分布;在Boosting算法的每一輪迭代中，估計(jì)多變量高斯分布根據(jù)樣本的當(dāng)前權(quán)重分布，估計(jì)高斯分布的均值向量和協(xié)方差矩陣，這種方法屬于基于概率密度估計(jì)的方法。在后一種策略中假定正常流量聚集在一個(gè)超球體內(nèi)部;在Boosting算法的每一輪迭代中，估計(jì)超球體區(qū)域根據(jù)樣本的當(dāng)前權(quán)重分布，估計(jì)超球體的球心和半徑，這種方法屬于基于置信區(qū)域估計(jì)的方法。

2.1 算法流程

根據(jù)ADA－Boost算法的一般流程，很容易得到基于Boosting的異常網(wǎng)絡(luò)流量檢測(cè)算法流程:

(1)從網(wǎng)絡(luò)流量歷史數(shù)據(jù)中，建立訓(xùn)練集D={Xt，t=1，…，N} ∈Rm，N為原始訓(xùn)練集D中所有樣本的總數(shù)。

(2)初始化訓(xùn)練集樣本的權(quán)重:D1(t)=1/N。

(3)重復(fù)如下迭代過程，直到終止準(zhǔn)則滿足，在每一輪迭代中 t(t=1，2，…，T):

(a)根據(jù)樣本的當(dāng)前權(quán)重分布Dt，在訓(xùn)練集D上訓(xùn)練一個(gè)弱學(xué)習(xí)算法;

(b)得到一個(gè)弱學(xué)習(xí)算法:Rp→R;

(c)利用所得到的弱學(xué)習(xí)算法:評(píng)估訓(xùn)練集D中每一個(gè)樣本t的誤差信息lt(t);

(d)計(jì)算弱學(xué)習(xí)算法的訓(xùn)練誤差st;

(e)選擇系數(shù)αt∈R，以衡量弱回歸算子的重要性;

(f)更新訓(xùn)練集D中樣本的權(quán)重分布:Di→Di+1;

(g)判斷終止準(zhǔn)則是否滿足。

(4)組合上述過程中得到的弱學(xué)習(xí)算法的輸出:{{ht，t=1，2，…，T} → H}。

(5)對(duì)于測(cè)試數(shù)據(jù)xtest∈Rm，根據(jù)第(4)步的輸出結(jié)果，判定其是否為異常情況。

2.2 設(shè)計(jì)弱學(xué)習(xí)算法

在本文中設(shè)計(jì)了兩種形式的弱學(xué)習(xí)算法:

(1)估計(jì)多變量高斯分布

這種情況下假定正常流量的分布是一個(gè)多變量的單高斯分布N(μ，∑)，在第t輪的迭代中，參數(shù)μ和∑分布通過公式(1)和公式(2)確定:

對(duì)于任一樣本，其在估計(jì)多變量高斯分布(MGE)條件下的輸出可通過樣本的概率密度表示:

(2)估計(jì)超球體區(qū)域

假定正常流量聚集在一個(gè)超球體內(nèi)部，假設(shè)估計(jì)超球體區(qū)域的球心為μ，采用馬氏距離來衡量任意一個(gè)點(diǎn)X到球心的距離:

在第t輪的迭代中，參數(shù)μt和∑t同樣通過公式(1)和公式(2)確定。為了確定超球體的半徑r，在指定虛警率的情況下，通過假設(shè)—校驗(yàn)的方法來確定，或者簡(jiǎn)單地將其設(shè)置為一個(gè)常數(shù)。對(duì)于任何一個(gè)樣本，其在估計(jì)超球體區(qū)域的輸出表示為:

2.3 評(píng)價(jià)樣本的誤差信息

在得到一種弱學(xué)習(xí)算法以后，需要評(píng)價(jià)訓(xùn)練集中的每一個(gè)樣本的誤差信息。無論采用哪一種弱學(xué)習(xí)算法(估計(jì)多變量高斯分布或估計(jì)超球體區(qū)域)，誤差信息用下式來評(píng)價(jià):Lt(t)=1－h(huán)t(t)，如果Lt(t)表示在第t輪迭代中第t個(gè)樣本的誤差信息，得到各個(gè)樣本的誤差信息以后，弱學(xué)習(xí)算法的誤差由下式計(jì)算得到:

為了權(quán)衡弱學(xué)習(xí)算法的重要性，采用和ADA－Boost一樣的策略為

2.4 算法設(shè)計(jì)

(1)更新權(quán)重分布

采用和ADA－Boost算法相同的樣本的權(quán)重分布更新策略:

其中，Zt是以規(guī)整化的系數(shù)，以保證Dt+1(t)是一種數(shù)據(jù)的分布形式。

(2)算法終止準(zhǔn)則

在理論上，ADA－Boost算法在εt≥0.5時(shí)終止，為了避免εt長(zhǎng)期停留在0.5附近，在本文中設(shè)置一個(gè)最大迭代步數(shù)Tmax。這樣，算法的終止準(zhǔn)則可由公式(8)給出:

(3)組合弱回歸算子輸出

為了得到算法最終的輸出，設(shè)定采用中值方式組合弱學(xué)習(xí)方法的輸出:

(4)判定流量正常與否

對(duì)于某一個(gè)測(cè)試數(shù)據(jù)Xtext∈Rm，用公式(8)得到輸出值hj·(Xtext)，如果hj·(Xtext) ≥c，判斷樣本正常，否則判斷樣本異常，參數(shù)c通過預(yù)設(shè)的虛警率確定:

3 實(shí)驗(yàn)結(jié)果及分析

3.1 實(shí)驗(yàn)過程

實(shí)驗(yàn)環(huán)境為Matlab 2009b，在實(shí)驗(yàn)中我們采用經(jīng)典的DARPA 1999 Data Set，該數(shù)據(jù)集持續(xù)時(shí)間為7個(gè)星期，數(shù)據(jù)大小為10G，包括54種攻擊，該數(shù)據(jù)集提供的文檔說明每一起攻擊事件的類型、發(fā)生和結(jié)束時(shí)間以及包含的主機(jī)，每一種攻擊還有一個(gè)類標(biāo)志，DARPA入侵檢測(cè)數(shù)據(jù)庫(kù)一共有四個(gè)類型:R2L(Remote To Local)、U2R(User To Root)、DOS(Denial Of Service)、PROBE，R2L 是遠(yuǎn)程用戶獲得本地用戶權(quán)限攻擊，U2R為本地普通用戶獲得超級(jí)用戶權(quán)限攻擊，R2L、U2L的攻擊可能會(huì)破壞網(wǎng)絡(luò)和系統(tǒng)的保密性、完整性和認(rèn)證，DOS為拒絕服務(wù)攻擊，破壞系統(tǒng)的可用性，PROBE為試探攻擊，破壞系統(tǒng)的機(jī)密性，并給其它攻擊類型提供信息。

通過實(shí)驗(yàn)，獲取整個(gè)數(shù)據(jù)集中的第一周數(shù)據(jù):Tue和 Wed數(shù)據(jù)不含任何形式的攻擊(Attack Free)，用來構(gòu)成訓(xùn)練數(shù)據(jù)集D;Thu和Fri數(shù)據(jù)含有若干形式的攻擊(如表1)，用來構(gòu)成測(cè)試數(shù)據(jù)集，文獻(xiàn)［8］提出的一類SVM方法，被用來與本文算法作比較。

表1 DARPA 1999 Data Set第一周的攻擊類型信息

圖1 基于Boosting的算法和OCSVM ROC結(jié)果比較

基于Boosting的算法中，相關(guān)參數(shù)和操作設(shè)置如下:

(1)每個(gè)樣本的持續(xù)時(shí)間(Duration)分別設(shè)為60s、120s、180s、300s;

(2)將應(yīng)用估計(jì)超球體區(qū)域當(dāng)作弱學(xué)習(xí)算子時(shí)，超球的半徑確定的方法為:每次迭代，使得球內(nèi)的樣本數(shù)目占訓(xùn)練集樣本總數(shù)的95%;

(3)最大迭代步數(shù)Tmax設(shè)為30。

3.2 基于Boosting的實(shí)驗(yàn)結(jié)果和分析

在測(cè)試集上的ROC(Receiver Operating Characteristic)結(jié)果如圖1所示。

ROC曲線是查準(zhǔn)率隨虛警率(False Alarm Rate)變化的曲線，其中，圓圈表示使用Boosting(弱學(xué)習(xí)算法為估計(jì)多變量高斯分布)的檢測(cè)結(jié)果(MGE)，正方形表示使用Boosting(弱學(xué)習(xí)算法為估計(jì)超球體區(qū)域)的檢測(cè)結(jié)果(HBE)，三角形表示使用一類支持向量機(jī)(OCSVM)的結(jié)果。從圖1中可知，基于Boosting的檢測(cè)算法總要優(yōu)于OCSVM。

通過比較兩種不同的弱學(xué)習(xí)算法可知，如果樣本的持續(xù)時(shí)間(Duration)較短(60s、120s)，那么虛警率較低(＜10%)時(shí)，估計(jì)超球體區(qū)域的性能要優(yōu)于估計(jì)多變量高斯分布;當(dāng)虛警率較高(＞10%)時(shí)，估計(jì)多變量高斯分布的性能要略優(yōu)于估計(jì)超球體區(qū)域。另一方面，如果樣本的持續(xù)時(shí)間(Duration)較長(zhǎng)(180s、300s)，那么兩種機(jī)制的性能基本相當(dāng)。

4 結(jié)論

本文將Boosting算法引入到異常網(wǎng)絡(luò)流量的檢測(cè)當(dāng)中，設(shè)計(jì)了兩種不同的弱學(xué)習(xí)方法:估計(jì)多變量高斯分布和估計(jì)超球體區(qū)域。實(shí)驗(yàn)結(jié)果表明，基于Boosting的檢測(cè)算法性能要優(yōu)于OCSVM。這表明Boosting作為一種提升弱學(xué)習(xí)算法性能的一般性策略，在非監(jiān)督情況下是十分有效的。

［1］Mohammad Assaad，Romuald Boné.A new boosting algorithm for improved time－series forecasting with recurrent neural networks［J］.Information Fusion，2008，9(1):41－55.

［2］Michael Kearns，Leslie G.Valiant.Cryptographic limitations on learning Boolean formulae and finite automata［J］.Journal of the Association for Computing Machinery，1994，41(1):67－95.

［3］［7］Michael C.Mozer，RichardWolniewicz，David B.Grimes，et al.Predicting subscriber dissatisfaction and improving retention in the wireless telecommunications industry［J］.IEEE Transactions on Neural Networks，2000(11):690－696.

［4］［8］Keerthi S S，Lin C J.Asymptotic behaviors of support vector machines with Gaussian kernel［J］.Neural Computation，2003，15(7):1667－1689.

［5］趙秀麗，趙俊龍.基于局部相關(guān)性的L2Boosting算法［J］.計(jì)算機(jī)工程，2010，36(8):1－3.

［6］鐘向陽，凌捷.基于多閾值Boosting方法的人臉檢測(cè)［J］.計(jì)算機(jī)工程，2009，35(11):172－174.