余蘇毅

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

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

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

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

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

經過整理分析，我們可大致將log所提供的信息，整理如下：

寄件時間: Nov/3/05:20:21

機器名稱: ccse

程序名稱[process編號]: sendmail[26621]

隊列編號: FAA26621

來源: from=DBT@gmail.gcn.net.tw

信件大小: size=382

處理等級: class=0

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

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

訊息編碼: msgid=<1997…>

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

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

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

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

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

2 針對電子郵件，作異常行為偵測

2.1 一般分群算法的分析

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

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

但是相反地，我們在此log數(shù)據(jù)分群的目標，便是想要凸顯極少數(shù)，極特異的異常數(shù)據(jù)，因此反而應給予較小的、異常的noise資料，較高的權重.

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

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

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

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

2.2 改良式K-means算法

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

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

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

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

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

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

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

3 實驗結果與分析

(1)首先我們先以Iris data 為實驗數(shù)據(jù)，與傳統(tǒng)K-means算法作比較,結果如圖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ù)據(jù)源為取Iris第1,2個參數(shù)值.(e)(f)(g)(h)的實驗數(shù)據(jù)源為取Iris第2,3個參數(shù)值.

(2)我們再以log data為實驗數(shù)據(jù)，與傳統(tǒng)K-means算法作比較

實驗數(shù)據(jù)為25 511筆，欲分為六群，為了容易觀察，我們取二個參數(shù)值：發(fā)信的數(shù)量(X軸)，信件的大小(Y軸).分群的結果如圖3所示：

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

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

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

4 結論與未來工作

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

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