從電子郵件記錄檔偵測異常使用行為





蘇志明、曾憲雄、江孟峰、陳昌盛

國立交通大學資訊科學系
新竹市大學路1001號
TEL:(03)5712121 EXT. 56658
EMAIL: sstseng@cis.nctu.edu.tw


摘要

  當企業網路(Intranet)與網際網路連結時,最重要的即是確保企業網路的安全性,避免重要的資料被串改或入侵。利用網路伺服器的紀錄檔(log data),分析網路流量及訊息,以自然分群(unsupervised clustering)的方式瞭解一般網路行為的習慣,針對出現大量的訊息,造成網路及主機負荷過大的破壞方式試圖加以防範,達到保護企業網路安全的目標。

  本篇論文的目的在於找尋較異常且數量較少的群集,以往文獻所提的分群演算法並非專為此目的而設計,因此往往虛耗大量的時間,且通常無法凸顯異常群集資料。因此在本篇論文中除了分析系統記錄檔的資料特性外,並提出一改良式k-means分群演算法,以改善傳統方法的弱點,適合用於篩選異常行為的群集。





一、緒論

 

  當企業網路(Intranet)與網際網路連結時,最重要的即是確保企業網路的安全性,避免重要的資料被串改或入侵。現今對於企業網路安全的維護,主要是應用防火牆(firewall)技術,將可能危害系統安全的來源杜絕於該企業網路之外,但是,在應用需求日益增加的情況下,為了能夠獲得更多網際網路相關資源的服務,防火牆不可能將所有來源阻絕於外,而理論上網路入侵者(crackers)就可能藉由這些途徑入侵與破壞系統[5]。

  為了能達到確保護Intranet的目標,並且在兼顧應用需求的條件下,設計一套網路行為的監控及預警系統有其必要性,基於這個理由,我們以網路流量及訊息作自然分群(unsupervised clustering)[8][10][11],瞭解一般網路行為的習慣,以便能依據此分析結果進而建立網路異常行為的預警系統。相對於防火牆以阻斷來源的方式確保安全,本系統進行的方式著重於分析在一般狀況下,這些資料與數據的分佈範圍,藉由此方式的分析,日後當系統發現網路上有類似異常群集的行為時,極有可能是非法的入侵或蓄意破壞,此時即可迅速的通知系統管理員,以便做出必要的處置。

  現今網際網路上有許多的入侵與破壞方式,在分類上也有不同的方式,簡單而言大致可以分成以下三類[2][3]:

  1. Denial of service:傳送大量訊息,促使網路或某部主機癱瘓,例如大量的電子郵件,或是以一連串不同的IP位址對其連結,使得連結佇列滿載,無法正常工作(TCP SYN attack)

  2. Intrusion:擷取網路上傳遞的封包,對其內容分析並找出入侵系統的方法(例如對其password加以解碼)

  3. Information theft:利用相關系統設計上類似的漏洞,並加以擷取訊息

  第一種破壞方式的特性是,網路上將可能出現大量的訊息,造成網路及主機負荷過大,本篇論文的目標即針對此類破壞方式試圖加以防範。在網際網路上提供了許多相關的網路流量及訊息偵測工具,可以針對以下訊息加以偵測:

  1. 網路流量

  2. 網路負載量

  3. 主機連線情況

  4. 封包使用協定

  5. 封包大小

  6. 封包存活時間

  7. 連線成功率

  經由適當的將這些工具加以研究與應用,並學習國外這個領域的相關經驗,配合類似的發展模式,不僅對我國在建立相關組織的發展將大有助益,或訂定更適合的偵測標準,以確實符合國防,企業網路對於安全的要求。例如針對電子郵件(E-mail)處理來說,系統的記錄可能比較單純,其資訊不外乎下列四類: 人(user)、時間、地點(host info)、及其它。

  若是從使用量統計方面著手,以現在Unix系統的環境而言,有現成的統計量程式,可計算寄信端、收信端分別為跟那一種郵寄程式有關,通常都附有更週詳的系統記錄檔。換而言之,其中許多欄位的資訊,可以透過「資料挖掘」(data mining)[6][12]技巧,從系統記錄檔中整理出一些資料的關連程度,並瞭解其隱藏的訊息。

  本篇論文共分五部分,此第一部分對於現行企業網路與網際網路連結時,提出可能的漏洞,並針對使用者行為提出一套偵測的方式。第二部分針對電子郵件記錄檔{Email log)作簡要的分析與整理。在第三部分裡除了分析其他的分群演算法,並詳細介紹我們所提出的改良式分群演算法。第四部分為實驗結果與分析。第五部分作結論及對未來努力的方向提出可行的方案。





二、電子郵件記錄檔資料分析

  本論文以校園網路「電子郵件系統記錄檔」資料作為資料挖採實驗的對象,以下資料為交通大學計算機中心,信件伺服器所擷取的信件收發記錄檔,原始檔案內容如表一所示。

  表一 原始信件伺服器記錄檔資料

  

  經過整理分析,我們可大致將log所提供的資訊,整理如下:

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

機器名稱      : ccse

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

佇列編號      : FAA26621

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

信件大小      : size=382

處理等級      : class=0

寄件優先權     : pri=30382

收信者數量     : nrcpts=1

訊息編碼      : msgid=<1997...>

寄件者身份資訊   : ctrladdr=root(0/1)

  經過資料的定性分析,除了過濾掉不適合的log參數,針對我們統計過後的資料加以評斷,欲判別特定來源主機(或帳號)是否屬於異常使用狀況。主要依下列原則判斷:

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

  表二的資料為從系統記錄統計過後資料,藉由專家的經驗,針對不同來源位置,篩選並計算系統記錄檔發信筆數、信件大小、間隔時間。

  表二 經由專家判別過後的資料

  

  將表二的判別資料,用統計圖表畫出,結果如下圖二。藉由氣泡圖來表達三個dimension的概念,X軸表同一主機的發信數量,Y軸表示該主機的異常程度,而氣泡的大小則表示該主機的平均發信大小。

  

  圖二 專家判定後的異常程度統計圖





三、針對電子郵件,作異常行為偵測

3.1 一般分群演算法的分析

  觀察傳統分群演算法,我們發現,一般的分群演算法並不適合用於找尋大量資料中異常群集,原因有以下兩點:

  1. 異常行為資料在所有的log資料中,所佔的比例非常的小,且各項參數數值與其它正常資料差異極大,在一般的分群演算法中,常視此種資料為錯誤資料(noise),不是忽略不計,就是給予較低的權重值,以避免引響其他資料的分群[1][7]。

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

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

  基於以上原因,我們將使用一個改良式的k-means分群演算法,將大量資料作粗略的概分,並允許所分的群數大於原先所定的目標群數k,以確保noise 的群集也可以被k-means演算法視作獨立的群集。接著將k個群重心建構成一個「最小展開樹」(minimum spanning tree),依據連線的距離,截斷k-1條較長的連線,所剩的k個群集便是我們希望求得的k群。

3.2 改良式k-means演算法

  在傳統k-means(by Forgy in 1965)[4]演算法中,會因為不同的起始點而造成不同的結果。且在資料量極大的情況下,並不適合做不同起始點的比較。舉例來說,若有50筆的資料欲分為五群,則所有的情況就會有7.4x1032種(Kaufman and Rousseeuw, 1990)[9]。因此,我們採用一個「跳躍式」的啟發策略(heuristic)。來幫助我們將較外圍或較異常的資料獨立出來。

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

  

  

  但是,在最差的情況下,會因上述的分割策略,導致每比資料皆自成一群。因此為了避免這種情況,我們需定一個分割的上限值kmax。若分割的群數超過kmax時,便合併群集中距離最短的兩群。

  在此我們要特別說明,本論文所使用的分割策略極類似ISODATA 演算法(Tou and Gonzalez, 1974),不過此演算法所提的分割與合併策略,不像ISODATA 是在初始狀態即限定分割或合併的參數值:若一群中數量太多即分割,若兩群太近即合併。改良演算法中的合併,分割操作,是完全依照當時分群的需要而定,唯有分割上限值,才需由專家視資料的多寡與特性後設定。

  在第一階段的改良k-means後,若所分的群數為δ。在第二階段中,我們使用「最小展開樹」來作合併的動作。因為k-means演算法是以「平方差總和」(sum of square-error)作為評斷分群結果的好壞,然而此法無法用於凸顯異常的群集。因此我們採用圖形分群理論中的最小展開樹。將δ群的群中心視為節點,利用Prim's MST 演算法,建構成一最小展開樹。依照愈是離群所居的群集愈是異常的概念,截斷前k-1條最長的連線,所得的k群,便是我們所欲求的分群結果。





四、實驗結果與分析

 

  (一)首先我們先以Iris data 為實驗資料,與傳統k-means演算法作比較

    (a)傳統k-means,k=3          (b)傳統k-means,k=4

    (c)改良k-means,k=3          (d)改良k-means,k=4

    (e)傳統k-means,k=3          (f)傳統k-means,k=4

    (g)改良k-means,k=3          (h)改良k-means,k=4

圖三 實驗結果圖示。 (a)(b)(c)(d)的實驗資料來源為取Iris第1,2 個參數值。(e)(f)(g)(h)的實驗資料來源為取Iris第2,3 個參數值。

(二)我們再以 log data 為實驗資料,與傳統k-means演算法作比較

  實驗資料為 25511筆,欲分為六群,為了容易觀察,我們取二個參數值:發信的數量(X軸),信件的大小(Y軸)。分群的結果入下圖所示:

    (i)為傳統k-means,k=6         (j)為改良k-means, k=6

圖四 以電子郵件記錄檔的實驗圖示。

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





五、結論與未來工作

 

  在一般的分群演算法中,即使異常群集在起始時設定為起始中心,但常因數量不多或距離不夠遠,最後被併入另外的群集中,而無法突顯出來。藉由本篇論文所提的兩階段式分群法,在第一階段裡使用改良式k-means演算法,適合用於大量資料,快速地將群集的資料分隔出來。再配合跳躍式的分割特點,使得外圍或較小群集也可以被區隔出來。在第二階段中,使用最小展開樹的節點遠近關係,作為判斷該群集是否較為異常的指標。由實驗的結果可知道,此改良後的演算法,用於找尋異常群集要比傳統的分群演算法來得好。

  目前為止,我們已經對電子郵件資料作詳盡的分析與提出一個可篩選異常資料的演算法,此法可適用於其他在大量資料中過濾異常的群集資料。然而,在實際的網路管理工作上,仍然有許多的管理上漏洞,尚無有效的防範,偵測工具,這些仍有待我們的努力與研究。





參考文獻

[1] Cedeno,A. A. and Suer, G. A. "The use of a similarity coefficient-based method to perform clustering analysis to a large set of data with dissimilar papers", Computers ind. Engng Vol. 33. Nos 1-2, pp. 225-228, 1997.

[2] CERT coordination center, http: //www.cert.org/

[3] Cyberspace Center, Internet security handbook, The Hong Kong University of Science and Technology, Feb., 1997.

[4] Forgy, E. "Cluster analysis of multivariate data: efficiency versus interpreability of classifications.", Biomertrics 21, 768. 1965.

[5] Goldschlag, D. M. and Reed, M. G. and Syverson, P. F."Privacy on the Internet,”Proceeding of INET’97, CD-ROM, 1997.

[6] Han, J. and Cai, Y. and Cercone, N. “Data-driven discovery of quantitative rules in relational database,”IEEE Tran. Knowledge and Data Engineering, Vol. 5, No. 1, pp. 29-40, Feb., 1993.

[7] Hong, T. P. A study of parallel processing and noise management on machine learning, Ph.D. Thesis, National Chiao Tung University, 1992.

[8] JainA. K. and Dubes R. C. , Algorithms for Clustering data, Prentice-Hall, Inc 1988.

[9] Kaufman, L. and P. Rousseeuw. "Finding Groups in Data", An Introduction to Cluster Analysis. Wiley, New York. 1990.

[10] Michaud, P."Clustering techniques", Future Generation Computer System, 13(1997) 135-147.

[11] Sarkar M. and Yegnanarayana, B. and D. Khemani, "A clustering alogrithm using an evolutionary programming-based approach", Pattern Recognition Letters, 18 (1997) pp. 975-986.

[12] Winston, P. H. Artificial Intelligence, 3rd edition, Addison Wesley Publishing Company, 1992.

[13] Zait, M. and Messatfa, H. "A comparative study of clustering methods", Future Generation Computer System 13(1997) 149-159.