謝景偉

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

0 概述

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

事件采集器主要負責采集數(shù)據(jù)（包括網(wǎng)絡數(shù)據(jù)包，系統(tǒng)日志等）；

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

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

檢測模式生成器主要負責生成新模式加入到檢測模式數(shù)據(jù)庫。

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

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

1 粗糙集基本概念

1.1 信息處理系統(tǒng)

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

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

1.2 屬性約簡

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

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

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

2.1 DIS模型

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

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

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

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

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

基于屬性頻度的啟發(fā)式算法：

將一個決策表作為算法的輸入：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中屬性頻度函數(shù)p(ck)，再從全部的 p(ck)找出有max值的cq，即 p(cq)= max{p(ck)}。

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

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

2.2.2 基于屬性頻度的啟發(fā)式約簡算法的改進（最優(yōu)化約簡）

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

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

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

輸入端：一個決策表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的屬性頻度函數(shù)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)中所含元素數(shù)目，之后將 POSB∪{cq}(D) /IND(B,D)內元素數(shù)目最多的屬性cq加入約簡集合：B∪cq→B。

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

2.2.3 實驗證明

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

仿真程序的開發(fā)環(huán)境及平臺：

（1）CPU：Intel*2 2.4G

（2）內存： DDR400 768M

（3）操作系統(tǒng)：Windows XP sp3

（4）開發(fā)平臺：VC++6.0

程序分為三部分進行：

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

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

表1 醫(yī)療數(shù)據(jù)屬性列表

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

例證：

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

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

表2 兩種算法的約簡結果

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

表3 約簡結果比對

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

3 結束語

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

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

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

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

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

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

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

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