一種處理混合型屬性的聚類算法在計(jì)算機(jī)取證中的應(yīng)用

黃 斌， 史 亮， 陳德禮， 陳俊杰， 周 超

(1.莆田學(xué)院電子信息工程系， 福建 莆田 351100；2.廈門大學(xué)軟件學(xué)院， 福建 廈門 361005)

0 引言

計(jì)算機(jī)動態(tài)取證是將取證技術(shù)結(jié)合到防火墻、人侵檢測中，對所有可能的計(jì)算機(jī)犯罪行為進(jìn)行實(shí)時(shí)數(shù)據(jù)獲取和分析，智能分析人侵者的企圖，采取措施切斷鏈接或誘敵深人，在確保系統(tǒng)安全的情況下獲取最大量的證據(jù)，并將證據(jù)鑒定、保全、提交的過程[1,2].

數(shù)據(jù)挖掘是一種特定應(yīng)用的數(shù)據(jù)分析過程，可以從包含大量冗余信息的數(shù)據(jù)中提取出盡可能多的隱藏知識，從而為做出正確判斷提供基礎(chǔ).因?yàn)榫哂懈叨茸詣踊奶攸c(diǎn)，數(shù)據(jù)挖掘技術(shù)已經(jīng)被頻繁應(yīng)用于與計(jì)算機(jī)取證領(lǐng)域相近的入侵檢測領(lǐng)域的研究中，用于對海量的安全審計(jì)數(shù)據(jù)進(jìn)行智能化處理，目的是抽象出利于進(jìn)行判斷和比較的特征模型.

K-Means算法作為一種數(shù)據(jù)挖掘中常用的聚類算法，在大數(shù)據(jù)集處理上具有較好的可伸縮、高效性和良好的擴(kuò)張性，因此可以考慮將其應(yīng)用于計(jì)算機(jī)取證中，但K-means算法無法處理符號類型的數(shù)據(jù)，而在計(jì)算機(jī)取證領(lǐng)域中，所要處理的數(shù)據(jù)往往混合型.通常的解決方法是轉(zhuǎn)換符號類型數(shù)據(jù)為數(shù)值，例如直接數(shù)值映射方法：protocol_type屬性里有一般有icmp、tcp、udp等多種可能的取值,直接映射方法是將protocol_type屬性的取值直接映射為一個(gè)自然數(shù)的集合，icmp取值為1，tcp取值為2，udp取值為3,…,以此類推.這種方法簡單易行，但存在著一定的問題：容易對算法造成誤導(dǎo)，錯誤地認(rèn)為該類型特征之間存在著大小關(guān)系.

針對基于聚類的計(jì)算機(jī)取證技術(shù)中所存在的不足，本文采取對符號類型特征進(jìn)行數(shù)值域的映射，并使用主成分分析對數(shù)值映射后增加的維數(shù)進(jìn)行降維.其基本思想是對于有m種不同取值的符號特性，用m比特對其進(jìn)行編碼，當(dāng)且僅當(dāng)特征取值為第i種值時(shí)，其碼字中的第i比特為1，其余比特為0.編碼映射實(shí)際上是將原始的具有多種取值的符號類型特征轉(zhuǎn)換為多個(gè)具有布爾取值的新特征，通過編碼映射將重要的符號型屬性轉(zhuǎn)化為數(shù)值型，再利用主成分分析進(jìn)行降維，從而克服單純使用聚類分析數(shù)據(jù)集中數(shù)值型屬性的不足，提高取證效果.

1 基于聚類的計(jì)算機(jī)取證技術(shù)

聚類是數(shù)據(jù)挖掘中重要的一類方法，聚類分析的方法是指將物理的或抽象的對象分成幾個(gè)群體，在每個(gè)群體內(nèi)部，對象之間具有較高的相似性，而在不同的群體之間相似性則比較低.一般一個(gè)群體也就是一個(gè)類，但與數(shù)據(jù)分類不同的是聚類結(jié)果主要是基于當(dāng)前所處理的數(shù)據(jù)，我們事先并不知道類的結(jié)構(gòu)及每個(gè)對象所屬的類別，可以不依賴預(yù)先定義的類和帶類標(biāo)號的訓(xùn)練實(shí)例來完成數(shù)據(jù)集的劃分,因此基于聚類分析的計(jì)算機(jī)取證技術(shù)可以通過對未標(biāo)識數(shù)據(jù)進(jìn)行訓(xùn)練來檢測異常數(shù)據(jù)，并能夠自適應(yīng)地確定算法參數(shù).該方法不需要手工或其它的分類，也不需要進(jìn)行訓(xùn)練，因此能發(fā)現(xiàn)新型的和未知的異常行為.

圖1 基于聚類分析的計(jì)算機(jī)取證過程

一般的網(wǎng)絡(luò)環(huán)境下正常數(shù)據(jù)規(guī)模是遠(yuǎn)遠(yuǎn)大于入侵行為數(shù)目的，由此可以假設(shè)正常行為的類的數(shù)據(jù)的數(shù)量遠(yuǎn)遠(yuǎn)大于各種體現(xiàn)攻擊行為的類的數(shù)據(jù)的數(shù)量，同時(shí)，我們認(rèn)為同一個(gè)類的實(shí)例都是具有相同類別的實(shí)例，聚類算法所得到的劃分就能夠區(qū)分正常與異常行為.計(jì)算每個(gè)聚類的實(shí)例個(gè)數(shù)占訓(xùn)練集實(shí)例個(gè)數(shù)的比例，將比例最大的聚類標(biāo)記為正常，而將其它的聚類標(biāo)記為異常，從而進(jìn)行計(jì)算機(jī)取證.

2 混合型屬性處理方案

計(jì)算機(jī)取證中數(shù)據(jù)是混合型數(shù)據(jù)集，包含了數(shù)值型和符號型的數(shù)據(jù).在聚類前的數(shù)據(jù)預(yù)處理過程中，我們對符號型的屬性進(jìn)行編碼映射，將原始的具有多種取值的符號類型特征轉(zhuǎn)換為多個(gè)具有布爾取值的新特征，編碼映射保留了符號類型特征不同取值之間的本質(zhì)特征，編碼映射后會增加數(shù)據(jù)集的維數(shù).為了解決這個(gè)問題，我們在編碼映射的基礎(chǔ)上引入主成分分析從而達(dá)到降維的效果.而對于數(shù)據(jù)集中的數(shù)值型屬性特征，由于一些度量單位的不同，造成屬性值之間差異很大，所以在進(jìn)行聚類分析之前我們必須采用標(biāo)準(zhǔn)化與正規(guī)化處理.

2.1 符號型數(shù)據(jù)的轉(zhuǎn)化

符號類型特征雖然與離散類型特征比較相似，但又與之不同.離散特征之間具有大小的關(guān)系，而符號類型特征之間卻沒有.例如：對于“協(xié)議類型(protocol_type)”特征，一般有icmp、tcp、udp等多種可能的取值.各種取值之間只有相同或者不同的關(guān)系而沒有大小的區(qū)別.對于它們的處理，顯然應(yīng)該與離散類型特征有所區(qū)別.

為了便于聚類算法的處理，在預(yù)處理階段需要對符號類型特征進(jìn)行數(shù)值域的映射，本文采用下面編碼映射方法.其做法是：對于有m種不同取值的符號特性，用m比特對其進(jìn)行編碼，當(dāng)且僅當(dāng)特征取值為第i種值時(shí)，其碼字中的第i比特為1，其余比特為0.例如對特征service，如果其取值僅為http、telnet、ftp、imap4、finger、netstat、gopher這7種，而特征protocol_type只有icmp、tcp、udp這3種取值，則對每個(gè)取值可以做如表1所示的編碼.

表1 對符號特征的編碼映射

編碼映射與直接數(shù)值映射法相比，編碼映射保留了符號類型特征不同取值之間的本質(zhì)特征，不會對學(xué)習(xí)算法造成誤導(dǎo)，但同時(shí)如果針對一些取值很多符號類型，要完成編碼需要的比特位數(shù)也會很長,如此會造成維度大幅度增加的結(jié)果.本文用主成分分析來處理編碼映射后增維的問題，從而達(dá)到了降維的目的.

2.2 主成分分析

主成分分析(PCA)是一種熟知的特征抽取方法[3,4].通過計(jì)算樣本協(xié)方差矩陣的本征矢量，PCA線性地將輸入空間映射為低維的特征空間，且新的特征互不相關(guān).PCA的主要思想是降低數(shù)據(jù)集的維度，并盡可能保持?jǐn)?shù)據(jù)集的信息.

我們對編碼映射后生成的矢量進(jìn)行PCA主成分分析，將能充分表征原來映射后生成的矢量主成分與計(jì)算機(jī)取證數(shù)據(jù)中的數(shù)值型數(shù)據(jù)一起進(jìn)行聚類分析.

我們設(shè)計(jì)的基于PCA技術(shù)的符號型數(shù)據(jù)編碼映射生成數(shù)據(jù)集的特征提取方法的實(shí)現(xiàn)算法如下：

步驟1： 設(shè)1行m列的矩陣νi1,νi2,…,νimOi表示1條計(jì)算機(jī)取證原始數(shù)據(jù)中所選的符號屬性經(jīng)過編碼映射后的生成值.計(jì)算機(jī)取證數(shù)據(jù)集中共有k條數(shù)據(jù)，i=1,2,…,k.根據(jù)原始矩陣Oi求出相關(guān)矩陣Xi，其中Xi為m階方陣.初始化，設(shè)i=1.

步驟2： 求出xi的m個(gè)特征值(按由大到小的順序)以及相應(yīng)的正交標(biāo)準(zhǔn)化特征向量νi1,νi2,…,νim，其中νi1,νi2,…,νim均為n行列向量.

步驟3： 以νi1的各個(gè)分量作為系數(shù)，求出各變量的線型組合，得到第一主成分.以νi2的各個(gè)分量作為系數(shù)，求出各變量的線型組合，得到第二主成分.以此類推，通過νim得到第m個(gè)主成分.

步驟4： 設(shè)i=i+1，重復(fù)步驟1、步驟2、步驟3，當(dāng)i=k時(shí)，算法終止.

通常取前3個(gè)主成分就基本能包含或者代表了原有數(shù)據(jù)集的全部信息，所以我們基于此對原數(shù)據(jù)進(jìn)行縮減.通過主成分分析，可以得到數(shù)據(jù)集中較大權(quán)重值所對應(yīng)的變量項(xiàng)，找出在權(quán)值上發(fā)生較大變化的變量項(xiàng)，作為主成分分析后新生成的數(shù)據(jù)集的主干變量項(xiàng)，在考慮其余變量項(xiàng)的實(shí)際意義的基礎(chǔ)上，適當(dāng)去掉影響較小的變量項(xiàng)，從而得到一個(gè)全新的數(shù)據(jù)集，起到降維作用.

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

在本文中，我們采用的數(shù)據(jù)集來自于KDD Cup 1999[5],該數(shù)據(jù)集包含了4大類入侵類型，即PROBE、R2L、U2R和DoS.首先對KDD CUP 99數(shù)據(jù)集進(jìn)行抽樣，按照一定概率隨機(jī)抽取5個(gè)抽樣數(shù)據(jù)集，其中前4個(gè)子集中各含一類攻擊，第5個(gè)子集中的入侵為混合型.各數(shù)據(jù)集的樣本數(shù)接近10 000條.

表2詳細(xì)地列出了各種類型數(shù)據(jù)的抽樣概率和抽取的樣本數(shù)，以及異常攻擊數(shù)據(jù)所占的百分比.本文的抽樣方法是對每一條數(shù)據(jù)生成一個(gè)隨機(jī)概率，如果該隨機(jī)概率小于我們所設(shè)置的抽樣概率比例，就抽取這條數(shù)據(jù)，否則不抽取.因此，在多次抽樣的過程中，雖然某些具體攻擊類型賦予了確定的抽樣概率比例，但是仍然可能每次抽取的樣本數(shù)目不一樣，甚至可能沒有抽到數(shù)據(jù)，如表2，DOS攻擊類型中的pod攻擊，雖然抽取概率是0.03%，但是仍然沒有抽取到樣本.

表2 抽樣KDD-CUP-99的各種類型攻擊數(shù)據(jù)集

從表2可以看出，DOS、Probing和R2L攻擊的異常數(shù)據(jù)百分比在1%到1.5%之間，但是U2R攻擊的異常數(shù)據(jù)百分比小于1%，且都是以100%的概率抽樣，這是由于U2R攻擊類型的數(shù)據(jù)在KDD CUP 99數(shù)據(jù)集中較少的緣故，盡管以全概率進(jìn)行抽樣，但是U2R異常攻擊的百分比比例還是較小.

數(shù)據(jù)集中不是每個(gè)屬性都對取證的結(jié)果有貢獻(xiàn),Srinivas Mukkamala等人利用支持向量機(jī)方法通過實(shí)驗(yàn)指出在KDD Cup 1999數(shù)據(jù)集中有13個(gè)屬性最為重要[6]，因此我們選取這13個(gè)屬性，并對符號型屬性service和protocol_type進(jìn)行編碼映射(見表1),再對其進(jìn)行主成分分析，最后使用K-Means算法對新的數(shù)據(jù)集進(jìn)行聚類，同時(shí)我們也做了只對11個(gè)數(shù)值屬性進(jìn)行聚類分析的仿真實(shí)驗(yàn)，兩者結(jié)果如表3所示：

表3 實(shí)驗(yàn)結(jié)果比較

從實(shí)驗(yàn)結(jié)果我們可以看到，在計(jì)算機(jī)取證中對網(wǎng)絡(luò)連接記錄中的符號型屬性采用編碼映射與主成分分析結(jié)合的方法，無論在4類攻擊類型還是混合攻擊類型上的檢測率都要比單純對數(shù)值型屬性聚類進(jìn)行異常檢測的高，而且在誤檢率上也有大幅度降低.

4 結(jié)束語

本文分析了聚類在計(jì)算機(jī)取證中的應(yīng)用，針對目前基于K-Means算法的計(jì)算機(jī)取證技術(shù)所存在的對符號類型數(shù)據(jù)處理能力欠缺的問題提出了一種處理混合型屬性的聚類算法的計(jì)算機(jī)取證技術(shù)，采用編碼映射處理符號型數(shù)據(jù)，并利用主成分分析來實(shí)現(xiàn)降維，最后在KDD99實(shí)驗(yàn)數(shù)據(jù)集通過聚類分析進(jìn)行了仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果證明采用這種方法能夠取得較高的檢測率與較低的誤檢率.下一步工作是改進(jìn)方法提高R2L和U2R這2類攻擊的檢測率.

參考文獻(xiàn)

[1] 張 俊,麥永浩,龔德忠. 計(jì)算機(jī)取證的時(shí)間分析方法[J]. 湖北警官學(xué)院學(xué)報(bào), 2009,(2)：67-70.

[2]米 佳, 何 平, 汪曉峰. 基于廣義數(shù)據(jù)挖掘的計(jì)算機(jī)取證技術(shù)[J]. 中國人民公安大學(xué)學(xué)報(bào)(自然科學(xué)版), 2008,(3)：52-55.

[3] Jian Yang, David Zhang, Alejandro F Frangi,etal. Two-dimensional PCA: a new approach to appearance-based face representation and recognition .IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26 (1):131-137.

[4]R. B. W. Wang. Identifying Intrusions in computer networks with principal component Analysis[C].Proceedings of the First International Conference on Availability, Reliability and Security,2006.

[5]KDD99 Cup dataset, http://kdd.ics.uci.edu/ databases/kd- dcup99/kddcup99.html.[DB/OL].

[6]黃 斌，史 亮，陳德禮.一種基于聚類和關(guān)聯(lián)規(guī)則修正的入侵檢測技術(shù)[J].莆田學(xué)院學(xué)報(bào)，2009,(2):41-44.