基于SVM的BGP異常流量檢測

摘 要:針對BGP異常檢測領域中獲得的數據具有多變性、小樣本和高維性等特征，提出一種基于SVM的BGP異常流量檢測方法。BGP數據實驗結果表明，應用SVM算法進行BGP異常流量檢測是可行的，有效的。關鍵詞:SVM; BGP; 異常流量檢測; 小樣本

中圖分類號:TN913-34; TP39308文獻標識碼:A

文章編號:1004-373X(2010)18-0118-03

Detection for Abnormal Flow Rate of BGP Based on SVM

SUN Hong-yan1， ZHANG Hong-yu2

(1.Department of Physics， Heze University， Heze 274015， China; 2.Shandong PT Planning and Designing Institute Co. Ltd.， Qingdao 266100， China)

Abstract: A new method of BGP abnormal flow-rate detection based on SVM is proposed， because of the variety， small-sample， and high-dimension of the data obtained in BGP abnormal flow detection. BGP data experiment results show that SVM algorithm is feasible and effective in detecting BGP abnormal flow rate.Keywords: SVM; BGP; abnormal flow-rate detection; small sample

0 引 言

BGP協議是一種路徑向量協議，在一定程度上綜合了距離向量和鏈路狀態算法的優點。簡言之，BGP協議是一種具有較好的簡單性，可擴展性、靈活性以及可靠性的路由協議，是一種專門為域間路由系統設計的路由協議[1]。

異常檢測是入侵檢測技術的一種，它是根據正常狀態下系統的觀察結果檢查當前狀態對正常狀態的偏離，然后通過分析系統或用戶的行為與正常行為的偏差檢測入侵。近年來，研究人員在異常檢測領域引入了各種人工智能和機器學習的方法，比如神經網絡[2]，數據挖掘[3]，人工免疫[4]，遺傳算法[5]等。這些方法大都依賴于大數理論，基于假設樣本數目趨于無窮大，并且要求數據有較強的規律性，檢測速度也難以滿足高速環境的要求。但在入侵檢測領域中獲得的數據大多具有多變性、小樣本和高維性等特征，(例如BGP異常數據) 使得以上方法有一定的局限性。

而SVM是專門處理有限樣本條件下的機器學習問題，其目標是得到在現有信息下的最優解而不僅是樣本數量趨于無窮大的最優值。它所具有的這種在缺乏足夠先驗背景知識下，只需較少的樣本就可以迅速訓練出具有相對較高性能指標，仍然能夠保證較高的正確率的良好特性，使之可以成為一種較好的異常檢測技術。所以針對BGP異常檢測領域中獲得的數據具有多變性、小樣本和高維性等特征[6]，在此采用SVM的方法檢測BGP異常流量。

1 基本概念

SVM方法是20世紀90年代初Vapnik等人根據統計學習理論提出的一種新的機器學習方法，它以結構風險最小化原則為理論基礎，通過適當地選擇函數子集及該子集中的判別函數，使學習機器的實際風險達到最小，保證了通過有限訓練樣本得到的小誤差分類器，對獨立測試集的測試誤差仍然較小。其核心思想是利用滿足Mercer 條件的核函數代替一個非線性映射，使得輸入空間中的樣本點能映射到一個高維的特征空間，并使之在該空間中線性可分，然后構造一個最優超平面來逼近理想分類結果。它專門用于小樣本數據。SVM 方法還可以用于密度估計和孤立點發現。SVM 方法是一個具有最優分類能力和推廣能力的學習機器。

1.1 最優分類面和廣義最優分類面

SVM是從線性可分情況下的最優分類面發展而來的，基本思想可用圖1來說明。圖1中實心點和空心點代表2類樣本，H為它們之間的分類超平面，H1，H2分別為過各類中離分類面最近的樣本且平行于分類面的超平面，它們之間的距離叫作分類間隔(margin)。

所謂最優分類線就是要求分類線不但能將2類樣本正確分開(訓練誤差率為0)，而且使分類間隔最大。分類線方程w#8226;x+b=0[7]，可以對它進行歸一化，使得對線性可分的樣本集(xi，yi)，i=1，2，…，n;x∈Rd，y∈{+1，-1};滿足:

yi[(w#8226;x)+b]-1≥0，i=1，2，…，n(1)

此時分類間隔等于2/w，因此使間隔最大等價于使w (或w2)最小。滿足式(1)，并且使w2最小的分類面就叫作最優分類面，過兩類樣本中離分類面最近的點且平行于最優分類面的超平面H1，H2上的訓練樣本點就稱作支持向量(support vector)，因為它們“支持”了最優分類面。

圖1 最優分類面示意圖

利用 Lagrange優化方法可以把上述最優分類面問題轉化為如下這種較簡單的對偶問題，即:在約束條件[8]:

∑ni=1yiαi=0，αi≥0，i=1，2，…，n(2)

下面對αi求解下列函數的最大值:

Q(α)=∑ni=1αi-12∑ni，j=1αiαjyiyj(xi#8226;xj)(3)

若α*為最優解，則:

w*=∑ni=1αi*yixi(4)

得到的最優分類函數是:



f(x)=sgn{(w*#8226;x)+b*}=

sgn{∑ni=1αi*yi(xi#8226;x)+b*}(5)



從前面的分析可以看出，最優分類面是在線性可分的前提下討論的，在線性不可分的情況下，就是某些訓練樣本不能滿足式(1)的條件，因此可以在條件中增加一個松弛項參數εi≥0，變成:

yi[(w#8226;xi)+b]-1+εi≥0，i=1，2，…，n(6)

將目標函數改為求φ(w，ε)=12(w#8226;w)+C(∑ni=1εi)最小，即折中考慮最少錯分樣本和最大分類間隔，就得到廣義最優分類面。其中，C>0 是一個常數，稱為懲罰系數，它控制對錯分樣本懲罰的程度。得到的最優超平面函數為:

f(x)=sgn{∑ni=1αi*yiK(xi#8226;xj)+b*}(7)

在高維空間實際上只需進行內積運算，而這種內積運算是可以用原空間中的函數實現的，甚至沒有必要知道變換中的形式。

1.2 核函數

選擇滿足Mercer條件的不同內積核函數，就構造了不同的SVM，這樣也就形成了不同的算法。目前研究最多的核函數主要有3類:

(1) 多項式核函數

K(x，xi)=[(x#8226;xi)+1]q(8)

式中:q是多項式的階次，所得到的是q階多項式分類器。

(2) 徑向基函數(RBF)

K(x，xi)=exp{-x-xi2σ2}(9)

所得的SVM是一種徑向基分類器，它與傳統徑向基函數方法的基本區別是，這里每一個基函數的中心對應于一個支持向量，它們以及輸出權值都是由算法自動確定的。但是需要注意的是，選擇不同的σ參數值，相應的分類面會有很大差別。

(3) S形核函數

K(x，xi)=tanh[v(x#8226;xi)+c](10)

事實上，需要進行訓練的樣本集有各式各樣，核函數也各有優劣。而徑向基核函數在多數數據庫上得到略為優良的性能。因此本文SVM采用徑向基核函數進行BGP異常流量檢測。

2 實例實驗

2.1 數據源

本文實驗采用的BGP數據取自RIPE 檔案庫[7]。其中BGP更新數據來自6個隨機選擇的端口。每個BGP數據集有35個屬性，包含1 438個正常數據和238個異常數據，表1列出了BGP數據的35個參數。參數1~3顯示了 BGP更新信息，而BGP更新信息的次數預示著互聯網路由動態變化。參數4~6:多項更新前綴。 Labovitz等人[9]定義了將BGP更新消息劃分為不同類型的方法，此方法涉及9個參數(參數7~15 )，每個參數計數一種不同類型的BGP更新。此外，可捕捉BGP更新時間特性的參數也很重要。參數6~15，分別標示著某一特定的BGP更新類型的跨到達時間。如參數10，它標示著到達一個特定前綴的兩種不同路徑的BGP宣告的交互到達時間。參數16~35表示每一個交互到達時間的均值和標準差。

另外，數據集還包含一個標識屬性，該屬性標明所屬類的類型，即2種類型，其中屬性值1表示正常的BGP網絡行為，屬于正常類，而另一類(屬性值為-1)表示異常類。

表1 BGP數據的35個參數

IDParameterDefinition

1Announce# of BGP announcements

2Withdrawal# of BGP withdrawals

3Update# of BGP updates(=Announce+Withdrawal)

4AnnouPrefix# of announced prefixes

5WithdwPrefix# of withdrawn prefixes

6UpdatedPrefix# of updated prefixes(=AnnouPrefix+WithdwPrefix)

7WWDup# of duplicate withdrawals

8AADupType1# of duplicate announcements

(all fields are the same)

9AADupType2# of duplicate announcements(only AS-PATH and NEXT-HOPfields are the same)

10AADiffAADiff # of new-path announcements(thus implicit withdrawals)

11WADupType1# of re-announcements after withdrawingthe same path (all fields are the same)

12WADupType2# of re-announcements after withdrawing thesame path (only AS-PATH and NEXT-HOPfields are the same)

13WADupWADupType1 + WADupType2

14WADiff# of new paths announced afterwithdrawing an old path

15AW# of withdrawals after announcing the same path

16~35the mean and the standard deviation of ten

different types of inter-arrival time

2.2 SVM與神經網絡性能比較

神經網絡是建立在經驗風險最小化原則基礎上，被廣泛地用來處理非線性高維回歸估計問題。本次實驗的BP神經網絡采用同SVM 識別方案相同的預處理。BP網絡結構:共分3 層:輸入層，40個神經元;隱層，10個單元;輸出層，3個[10]。另外SVM選用的核函數采用的是RBF函數:

K(x，xi)=exp{-(x-xi2/σ2)}

式中:系數σ2=0.5，懲罰系數C=10。

本次實驗選用數據的全部屬性即35個參數進行分類實驗。每個數據集首先隨機分布，然后選取總數據的9/10作為訓練數據集，剩下數據作為測試數據集。重復做10次實驗。平均測試結果就是這10次實驗結果的平均值。這10次實驗分別記為T=1，T=2，…，T=10。

將訓練數據作為輸入數據，利用所描述的SVM方法，將這些數據進行訓練，生成分類器。再將測試數據輸入，通過SVM分類器，輸出數據。整個實驗過程輸出數據分為兩類，正常數據和異常數據。異常數據中并不細分哪種異常病毒數據。表中顯示的是BGP測試數據集的GM。

(1) 1003數據集如表2所示。

表2 SVM與神經網絡在1003數據集的GM

算法T=1T=2T=3T=4T=5

SVM0.814 780.830 990.803 590.848 730.793 69

BP0.769 460.739 350.715 70.756 480.700 94

算法T=6T=7T=8T=9T=10

SVM0.877 560.821 780.846 830.802 330.852 8

BP0.762 130.758 930.740 70.711 180.741 47

(2) 1210數據集如表3所示。

表3 SVM與神經網絡在1210數據集的GM

算法T=1T=2T=3T=4T=5

SVM0.815 110.798 260.820 540.825 250.801 20

BP0.733 610.788 470.734 740.791 610.768 58

算法T=6T=7T=8T=9T=10

SVM0.807 730.806 210.832 580.816 960.819 26

BP0.745 270.712 420.781 570.768 140.778 99

(3) 2810數據集如表4所示。

表4 SVM與神經網絡在2810數據集的GM

算法T=1T=2T=3T=4T=5

SVM0.740 940.809 270.816 550.853 850.816 95

BP0.710 060.794 230.785 670.763 190.742 26

算法T=6T=7T=8T=9T=10

SVM0.791050.800220.819940.87310.83122

BP0.766 10.761 510.718 420.727 150.781 95

SVM與BP在BGP數據集的均值GM比較如圖2所示。其中橫坐標c取1，2，3分別表示BGP數據集1003，1210和2810。縱坐標為GM，是BGP數據的檢測正確率。

圖2 SVM與BP在BGP數據集的均值GM比較

2.3 實驗結果

根據實驗結果(見圖2)，有如下結論:

(1) 使用SVM分類器時均值GM為81%左右，而BP的均值GM為75%左右，這說明將SVM用于BGP異常流量檢測是可行的，有效的。

(2) 從正確率檢測指標看，SVM檢測性能優于BP模型。

3 結 語

本文針對BGP異常數據的多變性、小樣本和高維性等特征，將SVM用于BGP異常流量的檢測，可以保證較好的檢測性能。從GM數值來看，SVM優于BP模型的正確率檢測指標。

參考文獻

[1]Network Working Group. A border gateway protocol 4[R/OL]. [1995-03-24]. Http://www.ietf.org/rfc.

[2]GHOSH A K， SCHWARTZBARD A. A study in using neural networks for anomaly and misuse detection[C]//The 8th USENIX Security Symposium. Washington DC: USENIX， 1999.

[3]王新，劉建輝.基于數據挖掘的入侵檢測系統研究[J].計算機與數字工程，2005，33(11):88-90.

[4]田妍君，粱意文，董紅斌，等.IP包間關聯異常檢測的免疫隱馬爾柯夫模型[J].計算機工程，2005，31(22):146-148.

[5]孫東，黃天戍，秦丙栓，等.基于模糊數據挖掘與遺傳算法的異常檢測方法[J].計算機應用，2006，26(1):210-215.

[6]衣治安，呂曼.基于支持向量機的入侵檢測方法[J].大慶石油學院學報，2007，31(1):82-84.

[7]LI Jun， DOU De-jing， WU Zhen， et al. An Internet routing forensics framework for discovering rules of abnormal BGP events[J]. ACM SIGCOMM Computer Communication Review， 2005， 35(2): 57-62.

[8]POGGIO Tomaso， RIFKIN Ryan， MUKHERJEE Sayan， et al. General ccnditions for predictivity in learning theory[J]. Nature， 2004， 428: 419-422.

[9]LABOVITZ C， MALAN G R， JAHANIAN F. Internet routing instability[J]. IEEE/ACM Transactions on Networking， 1998， 6(5): 515-528.

[10]Simon Haykin.神經網絡原理[M].葉世偉，史忠植，譯.北京:機械工業出版社，2004.