一種基于粗糙集屬性約簡的入侵檢測算法

謝景偉

（湖南大眾傳媒職業技術學院，長沙 410100）

0 概述

一般情況下入侵檢測系統（簡稱IDS）是對入侵的方法和系統的脆性進行分析的即時監視，以及依據專業人員知識人工寫入的，且它是根據具體的系統環境和不同的檢測方法的，普通的IDS是由事件采集器和分析器、檢測模式數據庫、檢測模式生成器等主要部件組成。

事件采集器主要負責采集數據（包括網絡數據包，系統日志等）；

事件分析器主要負責分析檢測，并發出入侵警報；

檢測模式數據庫主要負責存放已檢測出的攻擊模式（也包括正常行為）；

檢測模式生成器主要負責生成新模式加入到檢測模式數據庫。

在現實的網絡傳輸中，平常數據量傳輸特別巨大、數據異常繁復。并且海量的數據里很多與入侵攻擊沒有關系，這些數據也許不一致、不完整，這樣就造成入侵檢測誤報、漏報。

粗糙集理論（Rough set）是一類對付不確定、不精確和知識模糊等問題的數學方面的工具。在應對殘缺數據分析、推斷和找出數據間的聯系、攝取有效特征、簡化數據信息、模糊知識的說明、總結、歸納等地方有著無與倫比的優勢。這些年來它獲得了學術界的矚目，并已出色地被用在機械學習、決斷分析、模式識別等方面。而將其用在入侵檢測，就可以達到自發從海量統計數據中找出新模型并制定新的安全規則，建立高精的智能IDS。

1 粗糙集基本概念

1.1 信息處理系統

信息處理系統可以簡稱信息系統，一般可以用S=（U，A）簡化替代S=（U，A，V，f）。

信息處理系統的信息變換為關系表格形式顯示，關系表每一行對應需要進行分析的一個對象，每一列對應這個對象的一個屬性值。對象信息由各屬性值來代替，此外關系表中一個屬性就表示一個等價關系，全部的關系表也就是被定義的一系列等價關系，這就是知識庫，這么做之后，之前討論的信息約簡就能夠轉化成關系表中屬性約簡。

1.2 屬性約簡

決策表代表決策信息系統的簡化，其中有海量的樣本信息。而其中一個樣本代表一條決策規則，全部規則又構成一個決策規則集。在現實使用里，這種決策規則集沒有實用性，因里面每個基本規則沒有適用性，僅僅是機械的記下一個樣本信息，沒法適應別的狀況，而進行屬性約簡后決策表的一條記錄變成了有相同規律的樣本信息，決策規則于是有了非常強的適用性[6]。

在信息分析中，最開始的決策表里的屬性并非相同重要，不必要關系在信息庫里是冗余的，冗余屬性不單占用資源，且會擾亂人們，不能作出正確、簡潔的決策，故決策表中屬性約簡的作用就是把冗余信息從信息庫中剔除，并且屬性約簡不影響信息庫的分類功能。籠統的說，決策表的條件屬性對應決策屬性時相對屬性約簡不唯一，也就是說同一決策表可以存在多個屬性約簡，其中屬性的數量將直接決定決策規則的繁復和功能。所以，人們都希望能找到有最少屬性數量的屬性約簡，只是由于屬性組合的沖突問題又變成最小約簡問題即是NP-Hard問題。當今應對此問題措施是引入啟發數據到屬性約簡，之后經由啟發數據可以縮減樣本待搜索信息量，由此達到優化約簡效率目的。

2 基于粗糙集屬性入侵檢測系統(DIS)模型

2.1 DIS模型

當前，基于粗糙集理論的DIS組成部分為事件采集器、數據挖掘器、智能決策機制以及模式匹配，主要是應用粗糙集理論對采集過來的數據進行分析和處理，得到用于入侵檢測的模式，也就是能夠生成有效的安全規則，然后模式匹配模塊就能夠依據這些規則來做入侵分析，得出判斷，而決策部分就依據該判斷作出相應的改進。

本章所討論的基于粗糙集的DIS模型就是在對粗糙集屬性頻度約簡算法進行改進的基礎上，實現了入侵數據的處理分析，經由對應的處理剔除審計數據中冗余的信息，大大提升了數據挖掘步驟的效率，并能得到高效、簡潔的安全規則。

2.2 基于屬性頻度的啟發式約簡算法及其改進

2.2.1 啟發式約簡算法（基于屬性頻度）

當前，一般的屬性頻度算法以決策表相應的差別矩陣為基本，綜合其中全體屬性集合，列出全部非核屬性在差別矩陣中的頻數，假如某非核屬性的頻數max，則表明這個非核屬性在甄別兩個不同的決策對象中起的作用最大，故應首先把它加入到約簡集合中，并把包含該屬性的全部其他屬性組合刪除。

基于屬性頻度的啟發式算法：

將一個決策表作為算法的輸入：T=U,R,V,f,U是論域，R=C∪D中C,D分別表示條件屬性的集合和決策屬性的集合。

該決策表T的一個約簡B表示算法的輸出。

第一步：尋找核屬性即C0；開始初始化 B：C0→B

第二步：刪除M中全部和B的交集不為空集的元素，且從條件屬性集合中剔除B中所含元素。即：M-Q→M，C-B→P，Q={ | AijAij∩B≠?}。

第三步：將ck∈P帶入，算出在M中屬性頻度函數p(ck)，再從全部的 p(ck)找出有max值的cq，即 p(cq)= max{p(ck)}。

第四步：將cq歸入約簡集合中：B∪cq→B

第五步：重復第一到第四步直到M=?。

2.2.2 基于屬性頻度的啟發式約簡算法的改進（最優化約簡）

屬性頻度算法是根據屬性的頻度數來確定核屬性，如果某個屬性在決策表所對應的差別矩陣中出現的頻數很多，那么就說這個屬性對于決策規則是很重要的，故應首先被考慮加入核屬性集合中。然而在現實運用中會出現達到max頻度的屬性不止一個。

對這一現象原算法采取從這些都達到最大頻度的屬性中隨機挑選一個加入核屬性集合中。顯然這樣得到的約簡結果很可能不是決策表最優化約簡。

基于屬性頻度的啟發式算法的改進（實例）：

輸入端：一個決策表T=U,R,V,f，U表示論域，R=C∪D，C,D表示條件屬性集合以及決策屬性集合。

輸出端：決策表T的約簡結果B。

第一步：尋找決策表核屬性C0，同時初始化B：C0→B

第二步：刪除M中全部和B的交集不為空集合的元素，從條件屬性集合中剔除B相應元素。即：M-Q→M，C-B→P，Q={ | AijAij∩B≠?}。

第三步：

(1)對全部的ck∈P，算出M的屬性頻度函數p(ck)；

(2)從全部p(ck)列出具有max值的cq，如果有max頻度的屬性有且只有一個，則 p(cq)=max{p(ck)}，隨后將cq加入約簡集合：B∪cq→B，隨后跳到第四步；如果有max頻度的屬性不止一個時轉到第三步的（3）；

(3)算出屬性頻度最大的各屬性的 POSB∪{cq}(D) /IND(B,D)中所含元素數目，之后將 POSB∪{cq}(D) /IND(B,D)內元素數目最多的屬性cq加入約簡集合：B∪cq→B。

第五步：重復第一到第四步直到M=?。

2.2.3 實驗證明

為驗證改進后算法可靠性，本節將進行UCI中的信息系統的測試分析。

仿真程序的開發環境及平臺：

（1）CPU：Intel*2 2.4G

（2）內存： DDR400 768M

（3）操作系統：Windows XP sp3

（4）開發平臺：VC++6.0

程序分為三部分進行：

第一部分：將數據集合用常用的屬性頻度算法進行屬性約簡，即原始算法約簡對照。

第二部分：用改進算法對同樣數據集合進行約簡。即改進算法推演。

表1 醫療數據屬性列表

第三部分：依據前兩部分實驗結果比較分析，并且得出最終結論。

例證：

使用一組共有700條的醫療數據屬性列表作為數據集合。其中條件屬性和決策屬性（用class表示）如下表所示，此類屬性均為離散型數據，故能夠進行直接屬性約簡計算。

兩部分的運算結果如表2所示：

表2 兩種算法的約簡結果

依據約簡集合{A,C,E,F}、{C,E,F,G}約簡原始數據集，最后約簡比對情況如表3所示：

表3 約簡結果比對

顯然，約簡集合{C,E,F,G}比{A,C,E,F}約簡效率高得多。此外，根據多次實驗在50%的情況下原算法得出的約簡集合相對較弱，這證明了改進算法或多或少地優化了約簡率。

3 結束語

現實的入侵檢測非常復雜，入侵檢測的分析數據量也越來越大，而粗糙集理論是處理這類問題的強有力的工具。本文在分析了粗糙集理論、約簡算法的研究基礎上，把粗糙集的數據約簡技術應用到對網絡數據的分析處理中，對基于屬性頻度的啟發式約簡算法進行了改進，實驗結果表明，這種方法具有很高的約簡性，通過粗糙集屬性約簡能夠剔除待分析數據集合里冗余信息，此外通過數據挖掘獲取安全規則。在識別未知攻擊方面具有較好的性能，對于入侵檢測技術的發展具有重要價值。

[1]王丹,吳孟達,劉銀山.屬性約簡的一種簡單算法[A].第12屆全國模糊系統與模糊數學學術年會論文集[C].2004.

[2]武志峰.粗糙集理論及其在入侵檢測中的應用研究[D].南京師范大學碩士論文，2005，(4).

[3]曾黃磷.粗集理論及其應用——關于數據推理的新方法[M].重慶：重慶大學出版社,1996.

[4]王國胤.Rough集理論與知識獲取[M].西安：西安交通大學出版社,2001.

[5]謝旭東,梁剛,黃天云.入侵檢測系統技術介紹與發展趨勢[J].福建電腦，2004，（6）.

[6]常曉艷,劉振娟.基于粗糙集屬性約簡的過程控制規則提取[A].第二屆全國信息獲取與處理學術會議論文集[C].2004.

[7]唐忠，曹俊月.基于粗糙集屬性約簡的SVM異常入侵檢測方法[J].通信技術,2009，（2）.