Ｒｏｕｇｈ集在基于異常的入侵檢測系統中的應用研究

張寧丹　曾曉華

[摘要]針對入侵檢測系統中安全規則提取的困難，提出利用粗集方法從系統日志信息中挖掘安全規則，并給出規則挖掘算法。通過KDDCup99入侵數據測試集中的數據驗證該方法的有效性和可行性，為入侵檢測中安全規則的提取提供一種新方法。

[關鍵詞]網絡安全 入侵檢測 粗集方法 數據挖掘

中圖分類號：TP3文獻標識碼：A文章編號：1671－7597（2009）0310044－02

一、引言

將數據挖掘技術應用于入侵檢測中，構建基于數據挖掘技術的入侵檢測系統，就可以自動地從大量的審計數據中發現新的模型或安全規則，消除入侵檢測系統中規則提取和編碼的困難，建立一個準確性高的智能入侵檢測系統。

二、有關概念與理論

1．粗集理論是波蘭數學家Z.Pawlak在1982年提出的一種數據分析的方法。在分類的意義下，粗集理論定義了模糊性與不確定性的概念，其特點是不需要預先給定某些特征或屬性的數量描述，而是直接從給定問題的描述集合出發，找出該問題中的內在規律。目前已被廣泛應用于人工智能、模式識別、知識數據庫挖掘、決策支持、機器學習、智能控制等領域。粗集理論中的核心問題是屬性約簡，即從決策表中去除不必要的屬性。屬性約簡的目標就是要從條件屬性集合中發現部分必要的條件屬性，使得這部分條件屬性形成的相對于決策屬性的分類和所有條件屬性所形成的相對于決策屬性的分類一致，即與所有條件屬性相對于決策屬性有相同的分類能力。入侵檢測可以看作是一種分類問題，即將每一條審計記錄分為正常的或是某一種特定的入侵。

2．入侵檢測：顧名思義，是指對入侵行為的發現，它通過在計算機網絡或計算機系統中的若干關鍵點收集信息并對收集到的信息進行分析，從而判斷網絡或系統中是否有違反安全策略的行為和被攻擊的跡象。入侵檢測是指識別惡意破壞計算機或網絡系統安全的過程，通過對計算機或網絡系統中的若干關鍵信息進行收集、分析，從中發現網絡或系統中是否有違反安全策略的行為和被攻擊的跡象。完成入侵檢測功能的軟件和硬件組合便是入侵檢測系統。

三、系統原型設計

（一）設計原理與方法

基于入侵檢測系統與Rough集理論的特點，且考慮到本文主要討論Rough集理論在基于異常的入侵檢測上的應用，本文將主要關注Rough集理論在檢測時的應用細節，以此證明Rough集理論在異常入侵檢測上的應用可能性、優越點、不足以及應用時所需要考慮的問題。在進行系統設計時，將遵循以下原則進行系統設計：

1．多層抽象化：即系統以分層形式實現，并在各層間抽象化，以減少算法本身對外部數據形式及模塊的依賴。

2．架構參考一些當前學術界和行業領域里的IDS框架模型，以此作為系統架構的模板，這樣可以避免在設計架構時出現重大缺陷，同時也有利于兼容性。

（二）模型中Rough集的核心算法

使用Rough Set理論分析決策系統的一般過程是先對決策表的屬性進行約簡然后由屬性約簡得到決策規則具體步驟如下：

1．數據采集建立樣本集；

2．對連續屬性進行離散化；

3．用離散化后的條件屬性和決策屬性建立決策表；

4．用Rough Set 理論對條件屬性化簡得到最小決策表即決策規則；

5．用決策規則對經屬性處理后的待識樣本進行決策。

其中使用到關于Rough集理論的主要算法有下列幾種：離散化算法、屬性約簡算法、規則生成算法、分類算法，以及在處理數據集規模比較大時所用到的分解算法。有些算法也可以把屬性約簡和規則生成合并在一起，然而功能依然是相似的。而這些算法之間的彼此關系，可以用下面的圖1表示。

（三）數據離散化

一般在進行屬性約簡和規則生成之前，都需要進行離散化。離散化過程是對屬性值屬于連續空間的屬性進行處理，使得該屬性值的值域可以由若干個區間來表示，每個區間作為一個離散子，原來該屬性里的各記錄中，該屬性的值將根據它所屬的離散子，轉化成該離散子所對應的新值。從而使得所有連續空間可以由若干個離散區間表示，從而在規則算法處理時，能產生更加符合需要的規則集。在對入侵檢測數據集的處理中，我們采用算法1所示的離散化過程。

Algorithm 1：離散化過程

Input:The consistent decision table A

Output:The semi-minimal set of cuts P consistent with A

Data Structure: D-the semi-minimal set of cuts; L=PART(D)-the partition of U defined by D;CA-the set of all possible cuts on A

（四）Decomposition Tree算法

標準的RSKDD處理過程對于大數據集的分析效率較低，在做規則生成之前，應對數據表進行分解。分解過程是KDD在處理數據規模非常大的數據集時常常使用的方法。分解過程是一個比較通用的方法，其主要目的是通過在數據集的屬性中通過尋找出某些分類標記或分類界限，然后以這些分類標記或界限作為分解因子，把數據集分解成數個子集，然后再對這些子集使用相同的分解方法，直到所有分解出來的子集所包含的數據元素個數均符合規定的大小，然后再對每個數據子集使用數據挖掘算法。樹狀結構通常是表示這種分解結果的一個比較好的形式，我們稱它為分解樹。在分解樹中，每個分支的集合，在該分支所表示的屬性上，有著相同的屬性特點，如左分支的所有集合該屬性都小于等于這個分支節點的節點值，而右分支的所有集合該屬性都大于這個分支節點的節點值。分解樹算法過程大致如下，它首先去找到表A的最佳模板，然后根據模板將A分成兩個子集，再對兩個子集判斷，若未達到符合的大小，則遞歸進行分解直到完成。

Algorithm2: Decomposition by template tree

Step1Find the best template T in A.

Step2Divide A onto two subtables:A1 containing all objects satisfying

T and A2=A- A1

Step3If obtained subtables are of acceptable size(in the sense of rough set methods)

then stop

else repeat from step 1 to 3 for all"too large"subtables.

該算法生成一個二叉樹，葉子節點是從原表中分解出來的子表，這些子表再通過規則生成算法生成各自的規則集保存在葉節點里，則該生成樹可用于接下來的分類操作中。假設u為一個待分類對象且A(T)是一個包含所有符合模板T的對象的子表，通過算法3從根開始搜索直到將該對象的類別分類出來。

Algorithm3: Classification by template tree

Step 1 If u matches template T found for A

then: go to subtree related to A(T)

else :go to subtree related to A(〕.

Step2 If u is at the leaf of the tree then go to 3

else: repeat 1-2 substituting A(T)(or A()for A .

四、實驗結果

實驗中使用了KDDCup99的數據作為訓練和檢測數據。

（一）實驗選取的數據介紹

在實驗中，我們選取KDDCup99數據集中的一部分數據作為我們實驗的訓練數據和測試數據。

（二）屬性集約簡

實驗中我們對離散化后的訓練數據用粗糙集進行屬性約簡，在具有41個屬性的訓練數據上，我們共生成了4個屬性集約簡，屬性集約簡的表示形式如下：

(duration,service,src_bytes,dst_bytes)

(duration,service,src_bytes,dst_host_count)

(service,src_bytes,dst_bytes,logged_in,dst_host_count,

dst_host_same_src_port_rate)

(protocol_type,src_bytes,dst_bytes,is_guest_login,dst_host_count,

dst_host_srv_count,dst_host_same_src_port_rate)

（三）實驗結果和分析

經過對大量訓練數據和測試數據的反復訓練及測試，得到比較理想的效果。從表2可以看出，本文提出的Rough集在基于異常的入侵檢測方法具有高檢測率、低誤檢率。

五、總結

本文通過實驗驗證了基于Rough集理論的異常入侵檢測模型的有效性，測試了系統的性能。實驗結果表明，該方法對DoS和Probe攻擊具有很高的檢測率，具有較低的誤檢率，并且對U2R和R2L攻擊也具有較好的檢測率，這進一步說明了將Rough集應用于基于異常的入侵檢測模型的可行性。

基金項目：湖南省教育廳科學研究資助項目(07c720)

參考文獻：

[1]E著、李逢天等譯，Carter,Cisco，安全入侵檢測系統，北京：人民郵電出版社，2003.

[2]羅守山，入侵檢測，北京郵電大學出版社，2004.4.

[3]韓東海、王超、李群，入侵檢測系統及實例剖析，北京：清華大學出版社，2002.5.