劉剛，李千目，劉鳳玉，張宏

(南京理工大學 計算機科學與技術(shù)學院，江蘇 南京210094)

0 引言

隨著網(wǎng)絡技術(shù)的廣泛應用，其多樣性、開放性和互聯(lián)性的特點，給網(wǎng)絡帶來了巨大的風險影響，使得網(wǎng)絡容易受到各種攻擊的威脅。如果能夠?qū)崟r準確的預測網(wǎng)絡中的安全風險概率，則對提高網(wǎng)絡安全性至關(guān)重要。

為了能夠有效地預測網(wǎng)絡安全風險，近年來，研究人員紛紛對風險預測進行了研究。文獻［1］提出了一種基于免疫的網(wǎng)絡安全風險檢測模型，通過檢測網(wǎng)絡虛擬抗體濃度，在網(wǎng)絡系統(tǒng)面臨攻擊時對其進行實時風險評估，但該方法僅檢測出風險的大小，并未能預測出未來的風險發(fā)生概率。文獻［2］利用BP 神經(jīng)網(wǎng)絡，結(jié)合平均向量相似系數(shù)來預測信息交互風險概率，但由于神經(jīng)網(wǎng)絡結(jié)構(gòu)的選擇缺乏理論指導，而且對大樣本數(shù)據(jù)學習速度慢，故該預測模型缺乏實時性。文獻［3］基于灰色理論提出了一種P2P 網(wǎng)絡架構(gòu)下的風險評估預測方法，但該方法存在明顯的系統(tǒng)誤差，使得預測的準確性不高。

本文基于馬爾可夫模型，摒棄馬爾可夫預測對系統(tǒng)狀態(tài)轉(zhuǎn)移概率矩陣不隨時間變化的假設(shè)，提出了一種新的網(wǎng)絡安全攻擊實時風險概率預測模型。

1 馬爾可夫時變預測模型

定義:馬爾可夫鏈是隨機變量X1，X2，X3…的一個數(shù)列。隨機變量的范圍，被稱為“狀態(tài)空間”。如果Xt+k對于過去狀態(tài)的條件概率分布僅是Xt的一個函數(shù)，則

這里Xt+k=it+k為t+k 時刻過程處于it+k狀態(tài)。

上面這個恒等式可以被看作是馬爾可夫性質(zhì)。即t+k 時刻系統(tǒng)狀態(tài)Xt+k=it+k的概率分布只與t時刻的狀態(tài)有關(guān)，與t 時刻以前的狀態(tài)無關(guān)。

定義:馬爾可夫鏈模型可表示為(S，P，π)［4］，其中，

1)S 是系統(tǒng)所有可能的狀態(tài)所組成的非空的狀態(tài)集，即系統(tǒng)的狀態(tài)空間。如網(wǎng)絡的狀態(tài)空間為S={1，2，…，N}其中1 表示始態(tài)，N 表示終態(tài)。

2)P =［pij(t，t+k)］n×n是系統(tǒng)的狀態(tài)轉(zhuǎn)移概率矩陣，pij(t，t+k)=P{Xt+k=j|Xt=i}，i，j∈S 表示系統(tǒng)在時刻t 處于狀態(tài)i，經(jīng)過k 步狀態(tài)轉(zhuǎn)移處于狀態(tài)j 的概率。由于鏈在時刻t 從任何一個狀態(tài)出發(fā)，到另一個時刻t+k，必然轉(zhuǎn)移到諸狀態(tài)中的某一個，所以對于任意i∈S，則有

3)π=［π1π2… πn］是系統(tǒng)的初始概率分布，πi是系統(tǒng)的初始時刻處于狀態(tài)i 的概率，滿足

對于pij(t，t+k)=P{Xt+k=j|Xt=i}，i，j∈S，當k=1 時，稱pij(t，t+1)=pij(1)為時刻t 的一步狀態(tài)轉(zhuǎn)移概率，記P 為一步狀態(tài)轉(zhuǎn)移概率矩陣。

定理:設(shè){Xt，t=1，2…n}是一馬爾可夫鏈，則對任意的時刻u，v，有

證明:對于固定的時刻s，u，v 和狀態(tài)i，j，k，由條件概率定義和乘法定理，有

又由于事件組“Xs+u=k”，k =1，2，…n 構(gòu)成一個劃分，故有

將(2)式代入上式，定理得證。

(1)式寫成矩陣形式

推論:k 步轉(zhuǎn)移概率矩陣是一步轉(zhuǎn)移概率矩陣的k 次方。即Pk=P·Pk－1=Pk

證明:利用(3)式，令u =1，v =k－1，得遞推關(guān)系

記行向量π(k)=［π1(k)，π2(k)，…，πn(k)］，其中，πj(k)表示事件在初始(k =0)狀態(tài)為已知的條件下，經(jīng)過k 次狀態(tài)轉(zhuǎn)移后，在第k 個時刻處于狀態(tài)j 的概率。且

根據(jù)馬爾可夫過程的無后效性、貝葉斯條件概率公式及推論，有

式中:π(0)=［π1(0)，π2(0)，…，πn(0)］為初始狀態(tài)概率向量。Pi(i =1，2，…，k)表示系統(tǒng)的i 步狀態(tài)轉(zhuǎn)移概率矩陣。

從上述推理可以看出，傳統(tǒng)的馬爾可夫預測模型是基于假設(shè)系統(tǒng)狀態(tài)轉(zhuǎn)移概率矩陣是不隨時間變化的。然而在許多實際問題中，特別是在網(wǎng)絡攻擊環(huán)境中，狀態(tài)的轉(zhuǎn)移概率，是不斷發(fā)生變化的，因此本文根據(jù)系統(tǒng)狀態(tài)來實時更新狀態(tài)轉(zhuǎn)移概率矩陣。

由于狀態(tài)的轉(zhuǎn)移概率是不斷發(fā)生變化的，則由(2)式可得

式中，P'僅為一個符號，表示t+1 時刻對t 時刻狀態(tài)轉(zhuǎn)移概率矩陣的更新。(6)式中的P'并不相等。

由以上分析可知，如果某一事件在第0 個時刻的初始狀態(tài)已知，即π(0)已知，則利用遞推公式(6)，就可以求得它經(jīng)過k 次狀態(tài)轉(zhuǎn)移后，在第k 個時刻處于各種可能的狀態(tài)的概率，即π(k)，從而就得到該事件在第k 個時刻的狀態(tài)概率預測。因此，如何確定狀態(tài)轉(zhuǎn)移概率矩陣P'是預測的關(guān)鍵。

2 基于Markov 時變預測模型的實時風險概率預測

網(wǎng)絡攻擊一般由信息收集階段、攻擊進行階段、攻擊完成階段三部分構(gòu)成，根據(jù)攻擊的不同階段，將網(wǎng)絡風險狀態(tài)劃分為:無風險狀態(tài)L0(即網(wǎng)絡處于正常狀態(tài))、輕微風險狀態(tài)L1(網(wǎng)絡處于被探測狀態(tài))、較嚴重風險狀態(tài)L2(網(wǎng)絡處于被攻擊狀態(tài))和嚴重風險狀態(tài)L3(網(wǎng)絡已被攻陷)。這些狀態(tài)構(gòu)成了馬爾可夫時變預測模型中的狀態(tài)空間，即S ={L0，L1，L2，L3}，則網(wǎng)絡的風險狀態(tài)轉(zhuǎn)移如圖1所示。

圖1 網(wǎng)絡風險狀態(tài)轉(zhuǎn)移Fig.1 Risk state transition of network

由此可確定網(wǎng)絡風險狀態(tài)轉(zhuǎn)移概率矩陣為

計算狀態(tài)轉(zhuǎn)移概率矩陣P1，就是計算從每個狀態(tài)轉(zhuǎn)移到其他任何一個狀態(tài)的狀態(tài)轉(zhuǎn)移概率。狀態(tài)轉(zhuǎn)移概率的計算一般采用頻率近似概率的思想進行計算。

式中:nij為從狀態(tài)i 出發(fā)，轉(zhuǎn)移到狀態(tài)j 的樣本數(shù)。

更新狀態(tài)轉(zhuǎn)移概率矩陣P'實時迭代的算法下:

第1步:根據(jù)以往歷史樣本數(shù)據(jù)，利用(7)式、(8)式計算出初始的狀態(tài)轉(zhuǎn)移概率矩陣;

第2步:對歷史樣本數(shù)據(jù)進行初始化。輸入數(shù)據(jù)對象集X，輸入指定簇數(shù)目N，并在X 中隨機選取N 個對象作為初始簇中心。設(shè)定迭代終止條件，比如最大循環(huán)次數(shù)或者簇中心收斂誤差容限;

第3步:進行迭代處理。根據(jù)相似度準則將數(shù)據(jù)對象分配到最接近的簇中心，從而形成一簇。初始化隸屬度矩陣。以每一簇的平均向量作為新的簇中心，重新分配數(shù)據(jù)對象;

第4步:反復執(zhí)行第3 步直至滿足終止條件;

第5步:當新樣本到達時，計算內(nèi)聚度，得到新樣本所屬網(wǎng)絡風險狀態(tài)簇別。結(jié)合上一個樣本的風險狀態(tài)簇別，統(tǒng)計風險狀態(tài)轉(zhuǎn)移次數(shù)。然后回到第1 步重新計算狀態(tài)轉(zhuǎn)移概率矩陣，來更新。

內(nèi)聚度計算步驟如下:

第1步:選取歐式距離作為簇劃分標準。將新樣本記錄看作一個n 維向量，任意兩個n 維向量i，j的距離可以利用歐式距離來計算，設(shè)d(i，j)表示簇G 中任意兩個向量間的距離，即

內(nèi)聚值越大，簇內(nèi)元素越相似。之后根據(jù)狀態(tài)轉(zhuǎn)移概率矩陣的計算方法，可得到新的狀態(tài)轉(zhuǎn)移概率矩陣。在初始狀態(tài)概率已知的條件下，利用(6)式，即得出未來某時刻網(wǎng)絡的各個安全風險狀態(tài)概率值。

3 仿真試驗

為了驗證實時風險概率預測的馬爾可夫時變模型的有效性，本文利用KDD CUP 1999 數(shù)據(jù)集［］來做仿真試驗。根據(jù)文獻［6］對數(shù)據(jù)集中各攻擊的具體描述，根據(jù)攻擊階段不同，表1列出了各種攻擊階段對應的風險等級。

表1 攻擊分類Tab.1 Attack classification

由于KDD 數(shù)據(jù)集太過龐大，故在KDD 數(shù)據(jù)包選取各攻擊階段的一種攻擊數(shù)據(jù)進行實驗。本文所選取的攻擊組合為nomal、satan、guess_passwd 和rootkit.根據(jù)表1對38 種攻擊的分類，實驗抽取2%的normal 數(shù)據(jù)(2 192 條記錄)、全部satan 數(shù)據(jù)(1 589條記錄)、全部guess_passwd 數(shù)據(jù)(53 條記錄)和全部rootkit 數(shù)據(jù)(10 條記錄)作為實驗訓練數(shù)據(jù)。

KDD CUP 1999 數(shù)據(jù)集中共有41 個定性和定量屬性特征，其中有8 個離散屬性變量，33 個連續(xù)屬性變量。由于該數(shù)據(jù)集中屬性太多，增加了分析的復雜性，為了減輕分析的負擔，提高風險預測效率，實驗中采取主成分分析法，對原有屬性進行主成分提取，降低特征向量維數(shù)［7］。在保證原始數(shù)據(jù)信息損失最小的前提下，用較少的屬性代替原來較多的屬性但依然能反映原有的大部分信息。

實驗中除去了全部字符型屬性變量和取值全為零的屬性變量，對剩下的26 個屬性進行特征提取，提取特征值大于1、未經(jīng)旋轉(zhuǎn)的主成分。表2給出了主成分分析的結(jié)果。

從表2可以看出，前6 個主成分的累計貢獻率已達到81.437%，這6 個主成分可以基本反映原有屬性所具有的信息，這樣既減少了變量的個數(shù)，降低了20/26 =77%的運算量，又便于問題的全面分析和研究。

主成分分析后，進一步對訓練數(shù)據(jù)分成四個簇用C1，C2，C3，C4來表示，分別代表四種安全風險狀態(tài)L0、L1、L2和L3.圖2給出了簇分布情況，表3給出了簇分析結(jié)果，圖3給出了簇的分布趨勢。

當新樣本數(shù)據(jù)到來時，將新樣本數(shù)據(jù)分別加入到上述4 種簇中，然后根據(jù)內(nèi)聚度的定義，分別計算各簇的內(nèi)聚度，比較內(nèi)聚度數(shù)值的大小，內(nèi)聚度數(shù)值越大，說明新樣本與該簇越相似，故可將新樣本數(shù)據(jù)加入到內(nèi)聚度最大的簇中。

表2 主成分分析結(jié)果Tab.2 The results of principal component analysis

圖2 簇分布情況Fig.2 Cluster distribution

表3 簇分析結(jié)果Tab.3 The results of cluster analysis

圖3 簇分布趨勢Fig.3 Cluster distribution trends

對訓練樣本數(shù)據(jù)中各狀態(tài)轉(zhuǎn)移的次數(shù)進行統(tǒng)計，即前一時刻狀態(tài)轉(zhuǎn)移到后一時刻狀態(tài)的次數(shù)，統(tǒng)計結(jié)果如表4所示。

表4 狀態(tài)轉(zhuǎn)移次數(shù)統(tǒng)計結(jié)果Tab.4 The number of state transition statistics

利用(8)式計算的各個狀態(tài)的轉(zhuǎn)移概率，得到如下初始風險狀態(tài)轉(zhuǎn)移概率矩陣

由于起初網(wǎng)絡是處于正常狀態(tài)，故可認為其初始狀態(tài)概率π(0)={1，0，0，0}。將π(0)與(9)式相乘，可以得到

作為網(wǎng)絡當前的狀態(tài)概率。

實驗從kddcup.datat.txt 剩余90%的數(shù)據(jù)中抽取部分由normal、satan、guess_passwd 和rootkit 構(gòu)成的樣本數(shù)據(jù)集作為測試樣本，分4 組進行測試。

時刻T1輸入第一組實驗測試樣本，其由1 000個normal 樣本數(shù)據(jù)組成;

時刻T2接著輸入第二組實驗測試樣本，由1 000個satan 樣本數(shù)據(jù)組成;

時刻T3接著輸入第三組實驗測試樣本，由50個guess_passwd 樣本數(shù)據(jù)組成;

時刻T4最后輸入第四組實驗測試樣本，由10個rootkit 樣本數(shù)據(jù)組成。

當每一組新的測試樣本到來時，先對樣本進行簇別劃分，然后利用風險狀態(tài)轉(zhuǎn)移概率矩陣的計算方法，重新計算狀態(tài)轉(zhuǎn)移概率矩陣。最后利用(6)式預測未來各風險級別的概率。

表5至表8分別給出了第一組、第二組、第三組和第四組測試樣本的狀態(tài)轉(zhuǎn)移次數(shù)統(tǒng)計。

表5 第一組測試樣本狀態(tài)轉(zhuǎn)移次數(shù)統(tǒng)計結(jié)果Tab.5 The number of state transition statistics of the first group of test samples

表6 第二組測試樣本狀態(tài)轉(zhuǎn)移次數(shù)統(tǒng)計結(jié)果Tab.6 The number of state transition statistics of the second group of test samples

根據(jù)狀態(tài)轉(zhuǎn)移概率矩陣更新算法，可分別得到第一組、第二組、第三組和第四組狀態(tài)轉(zhuǎn)移概率矩陣:

表7 第三組測試樣本狀態(tài)轉(zhuǎn)移次數(shù)統(tǒng)計結(jié)果Tab.7 The number of state transition statistics of the third group of test samples

表8 第四組測試樣本狀態(tài)轉(zhuǎn)移次數(shù)統(tǒng)計結(jié)果Tab.8 The number of state transition statistics of the fourth group of test samples

表9給出了Markov 時變模型預測結(jié)果，表10給出了傳統(tǒng)Markov 預測結(jié)果。

表9 Markov 時變模型預測結(jié)果Tab.9 The results of Markov time－varying model prediction

表10 傳統(tǒng)Markov 預測結(jié)果Tab.10 The results of traditional Markov prediction

從實驗結(jié)果可以看出，基于馬爾可夫時變模型預測出的概率向風險等級高的狀態(tài)轉(zhuǎn)移的速度更快。從輸入的測試數(shù)據(jù)可以看出，網(wǎng)絡在每一時刻的測試數(shù)據(jù)都是同一類型的數(shù)據(jù)，故網(wǎng)絡在每一時刻的風險狀態(tài)應依次為L0、L1、L2和L3.由于馬爾可夫時變模型狀態(tài)轉(zhuǎn)移概率矩陣是隨著樣本的加入實時更新的，每次得到的網(wǎng)絡狀態(tài)概率也會不斷更新變化，這就使得對風險的預測更加準確客觀。仿真實驗表明，應用馬爾可夫時變模型在T1時刻，網(wǎng)絡處于L0狀態(tài)的風險概率最高;在T2時刻網(wǎng)絡處于L1狀態(tài)的風險概率最高;在T3時刻網(wǎng)絡處于L2狀態(tài)的風險概率最高;在T4時刻網(wǎng)絡處于L3狀態(tài)的風險概率最高，預測結(jié)果與實際的測試樣本相吻合。而傳統(tǒng)馬爾可夫預測由于缺乏實時性，導致預測結(jié)果與實際偏差較大，準確性較低。

4 結(jié)論

本文提出了一種面向網(wǎng)絡實時風險預測的馬爾可夫時變模型，與傳統(tǒng)的馬爾可夫預測模型相比，該模型彌補了傳統(tǒng)模型中狀態(tài)轉(zhuǎn)移概率矩陣不隨時間變化的不足，通過實時更新狀態(tài)轉(zhuǎn)移概率矩陣，使得預測結(jié)果更加符合實際，更加客觀與準確。并利用DARPA 的入侵檢測數(shù)據(jù)，結(jié)合特征提取，對該模型進行了仿真實驗，實驗結(jié)果表明該模型具有很好的可行性和有效性。

References)

［1］ 王益豐，李濤，胡曉勤，等.一種基于人工免疫的網(wǎng)絡安全實時風險檢測方法［J］.電子學報，2005，33(5):945－949.WANG Yi－Feng，LI Tao，HU Xiao－Qin，et al.A real－time method of risk evaluation based on artificial immune system for network security［J］.Acta Electronica Sinica，2005，33(5):945－949.(in Chinese)

［2］ 劉芳，蔡志平，肖儂，等.基于神經(jīng)網(wǎng)絡的安全風險概率預測模型［J］.計算機科學，2008，35(12):28－33.LIU Fang，CAI Zhi－ping，XIAO Nong，et al.Risk probability estimating model based on neural networks［J］.Computer Science，2008，35(12):28－33.(in Chinese)

［3］ Liu X Y，F(xiàn)u C，Yang J D，et al.Grey model－enhanced risk assessment and prediction for P2P nodes［C］∥Proceeding FCST’09 Proceedings of the 2009 Fourth International Conference on Frontier of Computer Science and Technology.Washington:IEEE Computer Society，2009.

［4］ 尹清波，張汝波，李雪耀，等.基于線性預測與馬爾可夫模型的入侵檢測技術(shù)研究［J］.計算機學報，2005，28(5):900－907.YIN Qing－bo，ZHANG Ru－bo，LI Xue－yao，et al.Research on technology of intrusion detection based on linear prediction and markov model［J］.Chinese Journal of Computers，2005，28(5):900－907.(in Chinese)

［5］ KDD99.KDD99 cup dataset［DB/OL］.http:∥kdd.ics.uci.edu/databases/kddcup99，1999.

［6］ DARPA.Training data attack description［EB/OL］.http:∥www.ll.mit.edu/mission/communications/ist/corpora/ideval/docs/attacks.html，2008－05－14.

［7］ 吳楓，仲妍，吳泉源.基于增量核主成分分析的數(shù)據(jù)流在線分類框架［J］.自動化學報，2010，36(4):534－542.WU Feng，ZHONG Yan，WU Quan－yuan.Online classification framework for data stream based on incremental kernel principal component analysis［J］.Acta Automatica Sinica，2010，36(4):534－542.(in Chinese)