余蘇毅

(寧德師范學(xué)院 信息與機(jī)電工程學(xué)院,福建 寧德 352100)

當(dāng)內(nèi)聯(lián)網(wǎng)(Intranet)與因特網(wǎng)連接時(shí)，最重要的即是確保內(nèi)聯(lián)網(wǎng)的安全性，避免重要的數(shù)據(jù)被串改或入侵.現(xiàn)今對(duì)于內(nèi)聯(lián)網(wǎng)安全的維護(hù)，主要是應(yīng)用防火墻(firewall)技術(shù)，將可能危害系統(tǒng)安全的來(lái)源杜絕于該內(nèi)聯(lián)網(wǎng)之外.相對(duì)于防火墻以阻斷來(lái)源的方式確保安全，本系統(tǒng)進(jìn)行的方式著重于分析在一般狀況下，這些數(shù)據(jù)與數(shù)據(jù)的分布范圍，藉由此方式的分析，日后當(dāng)系統(tǒng)發(fā)現(xiàn)網(wǎng)絡(luò)上有類似異常群集的行為時(shí)，極有可能是非法的入侵或蓄意破壞，此時(shí)即可迅速的通知系統(tǒng)管理員，以便做出必要的處置.

1 電子郵件記錄文件數(shù)據(jù)分析

本論文以校園網(wǎng)絡(luò)“電子郵件系統(tǒng)記錄文件”數(shù)據(jù)作為數(shù)據(jù)挖采實(shí)驗(yàn)的對(duì)象，以下數(shù)據(jù)為交通大學(xué)計(jì)算機(jī)中心，信件服務(wù)器所擷取的信件收發(fā)記錄文件[1]，源文件內(nèi)容如表1所示.

表1 原始信件服務(wù)器記錄文件數(shù)據(jù)

經(jīng)過(guò)整理分析，我們可大致將log所提供的信息，整理如下：

寄件時(shí)間: Nov/3/05:20:21

機(jī)器名稱: ccse

程序名稱[process編號(hào)]: sendmail[26621]

隊(duì)列編號(hào): FAA26621

來(lái)源: from=DBT@gmail.gcn.net.tw

信件大小: size=382

處理等級(jí): class=0

寄件優(yōu)先權(quán): pri=30382

收信者數(shù)量: nrcpts=1

訊息編碼: msgid=<1997…>

發(fā)件人身份信息: ctrladdr=root(0/1)

經(jīng)過(guò)資料的定性分析，除了過(guò)濾掉不適合的log參數(shù)，針對(duì)我們統(tǒng)計(jì)過(guò)后的資料加以評(píng)斷，欲判別特定來(lái)源主機(jī)(或賬號(hào))是否屬于異常使用狀況[2].主要依下列原則判斷：

(1)信件的大小.(2)發(fā)出時(shí)間是否非常集中.(3)信件來(lái)源，寄信對(duì)象有特定或異常.(4)信件傳遞路徑.

表2的數(shù)據(jù)為從系統(tǒng)記錄統(tǒng)計(jì)過(guò)后數(shù)據(jù)，藉由專家的經(jīng)驗(yàn)，針對(duì)不同來(lái)源位置，篩選并計(jì)算系統(tǒng)記錄文件發(fā)信筆數(shù)、信件大小、間隔時(shí)間.

將表2的判別數(shù)據(jù)，用統(tǒng)計(jì)圖表畫出，結(jié)果如圖1.藉由氣泡圖來(lái)表達(dá)3個(gè)dimension的概念，X軸表示同一主機(jī)的發(fā)信數(shù)量，Y軸表示該主機(jī)的異常程度，而氣泡的大小則表示該主機(jī)的平均發(fā)信大小.[3]

2 針對(duì)電子郵件，作異常行為偵測(cè)

2.1 一般分群算法的分析

觀察傳統(tǒng)分群算法，可以發(fā)現(xiàn)，一般的分群算法并不適合用于找尋大量數(shù)據(jù)中異常群集，原因有以下兩點(diǎn)：

(1)異常行為數(shù)據(jù)在所有的log數(shù)據(jù)中，所占的比例非常的小，且各項(xiàng)參數(shù)數(shù)值與其它正常數(shù)據(jù)差異極大，在一般的分群算法中，常視此種數(shù)據(jù)為錯(cuò)誤數(shù)據(jù)(noise)，不是忽略不計(jì)，就是給予較低的權(quán)重值，以避免影響其它數(shù)據(jù)的分群.

但是相反地，我們?cè)诖薼og數(shù)據(jù)分群的目標(biāo)，便是想要凸顯極少數(shù)，極特異的異常數(shù)據(jù)，因此反而應(yīng)給予較小的、異常的noise資料，較高的權(quán)重.

表2 經(jīng)由專家判別過(guò)后的數(shù)據(jù)

圖1 專家判定后的異常程度統(tǒng)計(jì)圖

(2)在一般的分群法需O(n2)的時(shí)間花費(fèi)，但log數(shù)據(jù)動(dòng)輒數(shù)萬(wàn)筆，非一般數(shù)十筆的實(shí)驗(yàn)資料可以比擬，因此必須找尋一個(gè)在合理時(shí)間內(nèi)，可以概略分群的快速算法.

基于以上原因，我們將使用一個(gè)改良式的K-means分群算法[4]，將大量數(shù)據(jù)作粗略的概分，并允許所分的群數(shù)大于原先所定的目標(biāo)群數(shù)k，以確保noise的群集也可以被K-means算法視作獨(dú)立的群集.接著將k個(gè)群重心建構(gòu)成一個(gè)“最小展開樹”(minimum spanning tree)，依據(jù)聯(lián)機(jī)的距離，截?cái)鄈-1條較長(zhǎng)的聯(lián)機(jī)，所剩的k個(gè)群集便是我們希望求得的k群.

2.2 改良式K-means算法

在傳統(tǒng)K-means(by Forgy in 1965)算法中，會(huì)因?yàn)椴煌钠鹗键c(diǎn)而造成不同的結(jié)果.且在數(shù)據(jù)量極大的情況下，并不適合做不同起始點(diǎn)的比較.[5]舉例來(lái)說(shuō)，若有50筆的數(shù)據(jù)欲分為五群，則所有的情況就會(huì)有7.4×1 032種(Kaufman and Rousseeuw,1990).因此，我們采用一個(gè)“跳躍式”的啟發(fā)策略(heuristic)[6]，來(lái)幫助我們將較外圍或較異常的數(shù)據(jù)獨(dú)立出來(lái).

與傳統(tǒng)算法相同，我們?cè)诔跏紶顟B(tài)定義欲分群數(shù)據(jù)M={x1,x2,…,xm}，xi屬于Rn及任取k個(gè)起始中心C={z1,z2…,zk}，然后逐一將每筆數(shù)據(jù)歸入與之最接近的群集.在將一筆數(shù)據(jù)加入群集時(shí)，我們同時(shí)除了更新該群集的中心點(diǎn)外，并計(jì)算出所有群集間的最小距離min(C).故在將數(shù)據(jù)歸入群集前，比較數(shù)據(jù)與群集的最小距離min(d)與min(C).若min(d)大于min(C)，則將該資料獨(dú)立成新的群中心[7].如此，當(dāng)距離較遠(yuǎn)的異常數(shù)據(jù)都會(huì)因此被獨(dú)立出來(lái)而自成一群.δ為每次遞回時(shí)的最新群數(shù).

min(C)=min‖zj-zh‖2fori,h=1,2,…,δ，j≠h

min(d)=min‖xi-zj‖2fori=1,2,…,m，j=1,2,…,δ

但是，在最差的情況下，會(huì)因上述的分割策略，導(dǎo)致每筆數(shù)據(jù)皆自成一群.因此,為了避免這種情況，我們需定一個(gè)分割的上限值kmax.若分割的群數(shù)超過(guò)kmax時(shí)，便合并群集中距離最短的兩群.

在此,我們要特別說(shuō)明，本論文所使用的分割策略極類似ISODATA算法(Tou and Gonzalez,1974)[8]，不過(guò)此算法所提的分割與合并策略，不像ISODATA是在初始狀態(tài)即限定分割或合并的參數(shù)值：若一群中數(shù)量太多即分割，若兩群太近即合并.改良算法中的合并，分割操作，是完全依照當(dāng)時(shí)分群的需要而定，唯有分割上限值，才需由專家視數(shù)據(jù)的多寡與特性后設(shè)定.

在第一階段的改良K-means后，若所分的群數(shù)為δ.在第二階段中，我們使用“最小展開樹”來(lái)作合并的動(dòng)作.因?yàn)镵-means算法是以“平方差總和”(sum of square-error)作為評(píng)斷分群結(jié)果的好壞，然而此法無(wú)法用于凸顯異常的群集.因此，我們采用圖形分群理論中的最小展開樹.將δ群的群中心視為節(jié)點(diǎn)，利用Prim’s MST算法，建構(gòu)成一最小展開樹.依照愈是離群所居的群集愈是異常的概念，截?cái)嗲発-1條最長(zhǎng)的聯(lián)機(jī)，所得的k群，便是我們所欲求的分群結(jié)果.

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

(1)首先我們先以Iris data 為實(shí)驗(yàn)數(shù)據(jù)，與傳統(tǒng)K-means算法作比較,結(jié)果如圖2所示.

(a) 傳統(tǒng)K-means，k=3

(b) 傳統(tǒng)K-means，k=4

(c) 改良K-means，k=3

(d) 改良K-means，k=4

(e) 傳統(tǒng)K-means，k=3

(f) 傳統(tǒng)K-means，k=4

(g) 改良K-means，k=3

(h) 改良K-means，k=4

(a)(b)(c)(d)的實(shí)驗(yàn)數(shù)據(jù)源為取Iris第1,2個(gè)參數(shù)值.(e)(f)(g)(h)的實(shí)驗(yàn)數(shù)據(jù)源為取Iris第2,3個(gè)參數(shù)值.

(2)我們?cè)僖詌og data為實(shí)驗(yàn)數(shù)據(jù)，與傳統(tǒng)K-means算法作比較

實(shí)驗(yàn)數(shù)據(jù)為25 511筆，欲分為六群，為了容易觀察，我們?nèi)《€(gè)參數(shù)值：發(fā)信的數(shù)量(X軸)，信件的大小(Y軸).分群的結(jié)果如圖3所示：

(a) 傳統(tǒng)K-means，k=6

(b) 改良K-means，k=6

由實(shí)驗(yàn)結(jié)果的圖示，我們可以觀察到凡是使用傳統(tǒng)K-means算法的分群結(jié)果大抵皆會(huì)將一個(gè)大的群集分割為數(shù)個(gè)小群集，以降低分群的總平方差(sum of square-error)[9].而藉由改良式算法所得的結(jié)果，因?yàn)榻?jīng)過(guò)最小展開樹依距離的遠(yuǎn)近重新分群，所以會(huì)將較遠(yuǎn)的異常群集獨(dú)立出來(lái).經(jīng)由以上的分群作業(yè)，可以將郵寄記錄中的異常行為來(lái)源者，清晰地過(guò)濾出來(lái)，可作為系統(tǒng)管理者在管理或決策上的輔助.

4 結(jié)論與未來(lái)工作

在一般的分群算法中，即使異常群集在起始時(shí)設(shè)定為起始中心，但常因數(shù)量不多或距離不夠遠(yuǎn)，最后被并入另外的群集中，而無(wú)法突顯出來(lái).藉由本文所提的兩階段式分群法，在第一階段里使用改良式K-means算法，適合用于大量數(shù)據(jù)，快速地將群集的資料分隔出來(lái).再配合跳躍式的分割特點(diǎn)，使得外圍或較小群集也可以被區(qū)隔出來(lái).在第二階段中，使用最小展開樹的節(jié)點(diǎn)遠(yuǎn)近關(guān)系，作為判斷該群集是否較為異常的指標(biāo).由實(shí)驗(yàn)結(jié)果可知，改良后的算法用于找尋異常群集要比傳統(tǒng)的分群算法來(lái)得好.

目前為止，我們已經(jīng)對(duì)電子郵件數(shù)據(jù)作詳盡的分析與提出一個(gè)可篩選異常數(shù)據(jù)的算法，此法可適用于其它在大量數(shù)據(jù)中過(guò)濾異常的群集數(shù)據(jù).然而，在實(shí)際的網(wǎng)絡(luò)管理工作上，仍然有許多管理上的漏洞，有待我們進(jìn)一步努力，研究更有效的偵測(cè)工具，去偵測(cè)和防范網(wǎng)絡(luò)使用中的異常行為.