基于聚類算法的入侵檢測模型設計

摘 要: 本文提出了一種基于數據挖掘方法的入侵檢測模型，通過數據挖掘的聚類算法，提高入侵檢測的時效性與準確性。

關鍵詞: 入侵檢測 數據挖掘 聚類算法 模型設計

網絡攻擊和新攻擊手段的日益增長對入侵檢測技術提出了更高的要求。目前的入侵檢測系統普遍存在缺乏可適應性、有效性和擴展性的問題。基于數據挖掘技術的入侵檢測很好地解決了快速處理海量數據的問題，而且通過利用數據挖掘技術建立自適應的入侵檢測模型，它還能夠提供很好的適應性，解決了傳統入侵檢測系統要通過人工編碼進行更新的難題。本文采用數據挖掘聚類算法構造異常入侵檢測模型。基于通用的入侵檢測模型，在模型中最重要的模塊檢測模塊中應用數據挖掘聚類算法的方法，采用兩種聚類算法最大最小值法和C-均值算法來識別和檢測入侵信息。

一、系統總體結構設計

該入侵檢測模型的總體結構主要分為三大模塊:預處理模塊、檢測模塊和決策響應模塊。具體結構如圖1所示。

二、數據預處理模塊

(一)網絡數據包捕獲

根據入侵檢測的特點，在運用聚類算法進行挖掘前，我們首先要收集網絡上的原始數據，并對其進行分析，使得原始網絡數據包恢復成TCP/IP層的連接記錄，然后對其進行標準化的處理，將其轉換成符合數據挖掘的數據源。

以太網(Ethernet)具有共享介質的特征，信息是以明文的形式在網絡上傳輸，當網絡適配器設置為監聽模式(混雜模式，Promiscuous)時，由于采用以太網廣播信道爭用的方式，監聽系統與正常通信的網絡能夠并聯連接，并可以捕獲任何一個在同一沖突域上傳輸的數據包。IEEE802.3標準的以太網采用的是持續CSMA/CD(載波偵聽多址訪問/沖突檢測)的方式，正是由于以太網采用這種廣播信道爭用的方式，各個站點可以獲得其它站點發送的數據。運用這一原理，信息捕獲系統能夠攔截我們所要的信息，這是捕獲數據包的物理基礎[1]。

網絡上數據的截獲主要依賴于所使用的操作系統，不同的操作系統一般有不同的實現途徑。在UNIX或Linux系統中，一般采用由美國洛倫茲伯克利國家實驗室所編寫的專用于數據包捕獲功能的API函數庫Libpcap來實現。而在Windows系統中，則使用WinPcap，WinPcap是由伯克利分組捕獲庫派生而來的分組捕獲庫，它能夠在Windows操作平臺上來實現對底層包的截取過濾。捕獲數據包的過程如圖2。

(二)數據預處理

預處理階段主要的工作是把從網絡中收集到的各種網絡連接記錄和從計算機內部收集到各種記錄等數據信息進行過濾、格式轉換等預處理。其中計算機內部的數據信息主要包括操作系統審計記錄、系統日志和應用程序的日志信息。除此之外，還包括其他的一些數據來源，主要包括其他安全產品提供的數據、網絡設備提供的數據，以及所謂的“帶外”信息。

數據收集器在事件信息收集之后，通過多種數據轉換工作，把信息定制成統一的規范格式。在某些時候還需要包括數據的結構化、特征屬性的選取，以及其他的相關的處理。在基于網絡的入侵檢測系統中，數據包可以被緩存并重新還原為TCP會話。在異常檢測中，可以根據一些用于分類的特征數據(例如主機名)，將事件數據轉化成以數字形式表示的數組或表格(例如IP地址)。與誤用檢測相類似，不同形式的信息可能被轉換成統一的規范格式。系統收集用戶會話數據，并將之提煉成數字形式的特征向量，這使得事件數據可以占據更少的存儲空間。它還允許特定數據字段的聚合，以便檢測引擎可以方便地辨認出特定的用戶行為模式。

原始的網絡數據包本身還不適合于進行數據挖掘，需要將原始的網絡數據包恢復成TCP/IP層的連接記錄。具體對于TCP協議的數據包，預處理過程如下:按照包中的源地址/端口、目的地址/端口、序列號、確認序列號、標志位等信息將歸屬于同一次TCP連接的數據包組合成連接記錄的形式，并進行相應的統計處理。預處理結果為產生TCP連接記錄，其中包含有關本次TCP連接的統計信息，例如連接起始時間、持續時間、雙方發送的數據字節數等。同時，由于網絡事件通常在時間上具有很強的相關性，尤其對于探測攻擊(Port Sweep等)及拒絕服務攻擊(SYN-Flood，teardrop等)來說更是如此。因此我們可以考慮在檢測數據中加入基于時間的統計特性，如將時間窗大小設定為2秒，針對每一條連接記錄，統計出在2秒時間窗內目標地址是某臺主機的記錄和在2秒時間窗內目標端口是某服務端口的記錄。對于其他如HTTP、TELENT等協議的預處理過程與處理TCP的過程相似。

(三)數據標準化處理

聚類算法的輸入通常為一個包含N條記錄R，R，…，R的數據集，這N條記錄的d維特征向為X，X，…，X，即R=(X，X，…，X)，1≤i≤N，其中X是一個連續或離散類型的變量，代表數據的一個特征的取值。一個通用的聚類算法應該能夠從給定的任意分布的數據集中產生聚類。然而如果直接根據某個固定的距離(聚類寬度)來對數據點進行聚類，由于不同的特征可能具有不同的衡量標準，因而可能導致它們在距離計算的過程中起到不同的作用，產生大數吃小數的問題，最終影響聚類和異常結果的準確性。例如有兩條二維的記錄，利用下列公式得到Euclidean距離為:D(R，R)==。

可以看到整個距離完全由記錄的第一項屬性值所決定。為了解決這些問題，在運用聚類法進行入侵檢測前，首先應該對每條記錄的特征向量值進行標準化處理，所謂標準化處理就是賦予所有特征相同的權值，將初始測量值轉換為無單位變量。

對于經過分析處理后的每條網絡連接記錄，都包含有兩種類型的特征向量，分別是數字形式的特征值和離散形式的特征值，如連接傳送的字節數、同一端口的連接數都屬于數字形式的特征值，而連接使用的協議類型等則屬于離散形式的特征值。還有一些用數字表示的特征值實際上也屬于離散形式的特征值，如連接的目的端口地址等。

三、數據挖掘檢測模塊

基于數據挖掘的入侵檢測模型檢測模塊主要的任務是利用數據挖掘技術執行實時入侵檢測工作。檢測階段接收來自經過數據預處理過的各種數據記錄，使用數據挖掘技術分析數據記錄中的各種關聯關系和隱藏的、潛在的關系，并將其與正常的入侵檢測規則集進行對比來實現對各種入侵行為的檢測。檢測模塊是入侵檢測系統的最核心部分，也是最復雜的一部分。在此模型中應用聚類分析的數據挖掘算法，來檢測已知或未知入侵信息。

因為聚類能夠把數據按照數據自身的特點進行歸類，所以入侵檢測中引入此方法，用來識別未知的攻擊，這里假設各種攻擊能夠根據各自的特征聚為一類[2]。

(一)聚類算法

下面介紹C-均值算法步驟，它分為以下幾步。

1.條件及約定

設待分類的模式特征矢量集為{x，x，…，x}，類的數目C是預先取定的。

2.基本思想

該方法取定C類和選取C個初始聚類中心，按最小距離原則將各模式分配到C類中的某一類，之后不斷地計算類心和調整各模式的類別，最終使各模式到其類別中心的距離平方值的和最小。

3.算法步驟

(1)任選C個模式特征矢量作為初始聚類中心:z，z，…，z，令k=0。

(2)將待分類的模式特征矢量集{x}模式逐個按最小距離原則分化給c類中的某一類，即:

如果d=min[d]，i=1，2，…，N (公式1)，則判x∈w。

式中d表示x和w的中心z的距離，上角表示迭代次數。于是產生新的聚類w(j=1，2，…，c)。

(3)計算重新分類后的各類心

z=1/nx，i=1，2，…，c (公式2)。

式中n為w類中所含模式的個數。因為這種一步采取平均的方法將計算調整后各類的中心，且定為C類，故稱C-均值法。

(4)收斂性分析

我們以Euclidean距離為例，簡單地分析該算法的收斂性。在上述的算法中，雖然沒有直接運用準則函數J=||x-z|| (公式3)進行分類，但在(2)中根據(公式3)進行模式劃分可使J趨于變小。設某樣本x從聚類w移至聚類w中，w移出x后的集合記為，w移入x后的集合記為。設w和w所含樣本數分別為n和n，聚類w、、w和的均值分別為m、、m和，顯然有:

=m-(x-m)/(n-1) (公式4)，

=m+(x-m)/(n+1) (公式5)。

而這兩個新的聚類的類內Euclidean距離(平方)和與原來的兩個聚類的類內Euclidean距離(平方)J和J的關系是:=J-nj(||x-m||)/(n-1) (公式6)，=J+n(||x-m||)/(n+1) (公式7)。

當x距m比距m更近時，就有:n||x-m||/(n+1)

C-均值法是以確定的類數及選定的初始聚類中心為前提，使各模式到其所判屬類別中心距離(平方)值和最小的最佳聚類。顯然，該算法的分類結果受到取定的類別數目及聚類中心的初始位置的影響，所以結果只能是局部最優。但其結果簡單，結果尚能令人滿意，故應用較多。如模式分布呈類內團聚狀，該算法是能達到很好的聚類結果的。在實際中需要試探不同的C值和選取不同的聚類中心初始值，以進一步達到更大范圍的最優結果。

(二)特征提取與特征選擇[3]

特征提取與選擇的過程是對原始數據進行變換，得到最能反映分類本質的特征。在不同的書籍和文獻中“特征提取”、“特征選擇”的意義并不是完全相同的:“特征提取”在有的文獻中專指特征的形成過程，有的則指從形成、經選擇或變換到得出有效特征這一全過程。在文中，“特征提取”指的是從高維的測量空間通過映射(或變換)的方法降低維數得到特征空間的過程。“特征選擇”指的是從一組特征中挑選出一些最有效的特征以達到降低特征空間維數的目的的過程。從定義中可以看出實際上“特征選擇”是“特征提取”的特例。

特征選擇和提取通過去除不相關的和冗余的特征使特征數減少，即N的值變小。由于特征數的減少，還可以去掉一些重復的實例，使P也減小。這樣可以有效地避免“維數災難”和“組合爆炸”。而由于N和P的減小，可以減少算法學習的時間，提高分類的準確性。這對于解決變化較大數據集合的學習問題是有幫助的。而且，數據集合的減小也使遺失數據和錯誤數據的絕對數減小。

從現有的特征選擇算法來看，一個特征選擇算法由三個重要的方面決定:評判特征子集優劣的指標、搜索策略和搜索方向。這三個方面也構成了研究特征選擇的框架。

搜索策略有:窮舉搜索、啟發式搜索和不確定搜索。窮舉搜索是搜索所有可能的特征子集，這種搜索策略一定可以發現最優的特征子集，但搜索空間大，當特征數較多時是無法實現的:啟發式搜索按照一定的啟發式規則搜索特征子集，這種搜索策略，搜索空間比較小，可能丟失最優子集。這兩種搜索方法各有優劣，實際中需要平衡效率和結果之間的關系，作出選擇。不確定搜索實際上就是一種平衡方法，比較典型的不確定搜索有遺傳算法和模擬退火算法。

搜索方向分為:順序前進產生(SFG)、順序后退產生(SBG)、雙向產生(BG)和隨機產生(RG)。SFG從一個空集開始，逐步添加特征，自到發現最優解或滿足算法停止條件:SBG從特征全集開始逐步減少特征，發現最優解或滿足算法停止條件。RG隨機地產生特征子集，主要用于不確定搜索。

四、決策響應模塊

決策響應模塊的主要目的是對經過檢測階段分析的各種分析結果作出具體的判斷，并給予具體的響應(報警或更新)。當數據記錄經過數據挖掘算法的分析和特征提取器提取的特征后與正常規則庫中的規則進行比較，如果發現有新的入侵行為，則發出入侵警告，并將該入侵特征作為一個新的特征模式去更新規則庫以實現入侵檢測系統的規則庫的自動更新。當然，我們還可以通過專家手動更新規則庫。如果是正常活動數據，則不傳給系統安全人員，從保守的角度同時也是降低漏報率角度出發，將模糊的、未知的、事件按未知攻擊類型處理，并把它們和警報記錄一起傳給安全人員。

本文提出了一種聚類的數據挖掘方法進行異常入侵檢測的模型模型，分析了各個模塊的功能及聚類的經典算法。聚類算法可以有效地將入侵數據和正常數據區分開來，從而在檢測率和誤警率上也可以取得較好的效果。聚類挖掘技術作為一種從大量數據集中發現知識的智能化手段，可以從海量安全審計數據中自動提取出盡可能多的隱藏的安全信息，近幾年在入侵檢測系統研究中得到應用，已成為信息安全中的一個熱點信息。

參考文獻:

[1]唐正軍.入侵檢測技術導論.機械工業出版社，2004:15.

[2]張培帥.聚類算法在瓦網絡入侵檢測技術中的作用[J].電腦知識與技術，2008:1194-1196.

[3]李向偉.數據挖掘及實現技術研究.計算機與現代化，2006.8.