基于變精度覆蓋粗糙集的入侵檢測方法

歐彬利，鐘夏汝，代建華，楊 田*

（1.中南林業(yè)科技大學物流與交通學院，長沙 410004；2.智能計算與語言信息處理湖南省重點實驗室（湖南師范大學），長沙 410081）

（?通信作者電子郵箱math_yangtian@126.com）

0 引言

入侵檢測系統(tǒng)（Intrusion Detection System，IDS）是對網絡傳輸進行實時監(jiān)控，并能在發(fā)生異常時進行預警或采取反應措施的網絡安全設備。目前該系統(tǒng)內的入侵檢測技術主要分誤用檢測和異常檢測兩大類。誤用檢測是與系統(tǒng)內建立的攻擊類型庫進行匹配，具有較低的誤報率，但不能發(fā)現(xiàn)未知行為。異常檢測則是與系統(tǒng)內的正常狀態(tài)進行匹配，將有偏差的行為判定為攻擊，此方法所用時間較長且誤報率高，但能發(fā)現(xiàn)系統(tǒng)內未知的攻擊行為。近年來，提高異常檢測速度，并輔以誤用檢測的模型在入侵檢測系統(tǒng)中發(fā)揮著重要作用。

隨著網絡數(shù)據(jù)量的爆炸式增長，許多學者將數(shù)據(jù)挖掘技術和機器學習方法運用至入侵檢測。由于入侵檢測數(shù)據(jù)的特征維度高，為保證各方法的分類性能，需要在挖掘或學習前進行數(shù)據(jù)降維。粗糙集理論作為一種有效的不確定性數(shù)據(jù)處理工具，其核心屬性約簡（即特征選擇）可以在不需要先驗知識的情況下從數(shù)據(jù)表中得到對分類結果有貢獻的特征集。自Pawlak 等［1］提出的經典粗糙集以來，學者們對其進行推廣，提出了覆蓋粗糙集［2］、模糊粗糙集和粗糙模糊集［3］、變精度粗糙集［4］、變精度覆蓋粗糙集［5-6］、模糊變精度粗糙集［7］、概率變精度模糊粗糙集［8］。針對提出來的各種粗糙集模型，學者們也提出了相應的屬性約簡方法［9-12］。針對變精度粗糙集模型，Mi等［13］將β下和β上分布約簡與區(qū)分矩陣結合起來，提出了適用于變精度粗糙集模型的知識約簡方法。

近年來，許多學者將粗糙集理論與分類算法進行結合，并將其運用至入侵檢測研究。Chen 等［14］利用粗糙集理論進行數(shù)據(jù)降維，并結合支持向量機進行分類。Zhao［15］結合鄰域粗糙集模型和經由粒子群優(yōu)化后的支持向量機模型提出了一種新的入侵檢測集成算法。Panigrahi等［16］提出了一種基于模糊粗糙集理論的混合入侵檢測方法，首先將數(shù)據(jù)分為正常和異常兩類，再使用五種不同的分類器對數(shù)據(jù)進行分類。劉金平等［17］引入模糊粗糙集對數(shù)據(jù)進行最優(yōu)屬性選擇，然后提出一種基于GMM-LDA（Gaussian Mixture Model-Linear Discriminant Analysis）最優(yōu)聚類簇特征學習方法對入侵檢測數(shù)據(jù)進行自適應檢測。由于目前產生的網絡數(shù)據(jù)量龐大，需要入侵檢測系統(tǒng)在短時間內做出即時反應。通過對文獻［14-17］的分析發(fā)現(xiàn)，現(xiàn)有的粗糙集屬性約簡算法可對入侵檢測數(shù)據(jù)進行有效降維，但其時間和空間復雜度高，難以滿足實時監(jiān)控的需求。針對屬性約簡算法運行效率低的特點，Qian 等［18］提出了基于正域的屬性約簡加速算法，提高了約簡運算速度。Yang 等［19］基于覆蓋粗糙集提出的相關族屬性約簡算法具有速度快、內存消耗低的特點。但這兩種算法均未提供對于數(shù)據(jù)噪聲處理的解決方案。

針對相關族方法抗數(shù)據(jù)噪聲能力差的問題，本文提出了適用于變精度覆蓋粗糙集模型的相關族屬性約簡方法。該方法具有相關族方法計算時間短和空間復雜度低的優(yōu)點，同時具備較高的抗噪聲能力。入侵檢測數(shù)據(jù)中正常樣本某個特征上的數(shù)據(jù)噪聲會導致該樣本被劃分到異常類型，從而引發(fā)報警，導致誤報率的提升。用基于變精度覆蓋粗糙集模型的相關族屬性約簡方法處理該數(shù)據(jù)，在保證運行效率的同時，能有效降低誤報率。

1 預備知識

1.1 經典粗糙集

1.2 覆蓋粗糙集

經典粗糙集模型中等價關系的嚴格性，導致其只能用來處理離散型數(shù)據(jù)，故Bonikowski等［2］將等價關系推廣至覆蓋。

定義2［2］假設C 是論域U上的一族非空集合，若滿足關系 ∪C=U，稱 C 是U上的一個覆蓋。MdC(x)={M∈C|x∈M∧(?S∈C ∧x∈S∧S?M?M=S)} 稱為x的極小描述。在不會引起混淆的情況下，通常省略下標C。

由于覆蓋相較于等價關系的復雜性，覆蓋粗糙集近似算子多達22 種，由于篇幅關系，本文只列舉其中1 種，具體內容請參考文獻［20］。

定義3［21］給定信息系統(tǒng)是U上的一個覆蓋?；跇O小描述的上下近似算子分別定義為：

在不會引起混淆的情況下，通常省略下標C。

1.3 變精度覆蓋粗糙集

在實際數(shù)據(jù)中，由于噪聲的廣泛存在，使得粗糙集模型的魯棒性欠佳。為了降低模型的敏感程度，Ziarko［4］提出變精度粗糙集模型，隨后，Zheng等［6］將其推廣至變精度覆蓋粗糙集。

1.4 相關族

為完善覆蓋粗糙集模型屬性約簡理論，Yang 等［19］提出了相關族方法。

2 變精度覆蓋粗糙集決策系統(tǒng)屬性約簡

根據(jù)論域中的對象是否都能被劃分至正域里，將覆蓋決策系統(tǒng)分為協(xié)調覆蓋決策系統(tǒng)和不協(xié)調覆蓋決策系統(tǒng)。

由β相對正域的定義可知，要保持不協(xié)調覆蓋決策系統(tǒng)的β相對正域不縮小，則需要保持β相對正域里對象的β下近似算子MLβC(X)不縮小。

3 算法設計

求取所有約簡，被證明是NP（Non-deterministic Polynomial）完備問題，所以本文基于變精度覆蓋粗糙集相關族屬性約簡方法設計啟發(fā)式算法RF-VPCRS（Related Family based on Variable Precision Covering Rough Set）。該算法分兩步進行：第一步算出每個屬性下的β相關族；第二步在所有條件屬性β相關族的基礎上求得屬性約簡。

令覆蓋決策表的對象個數(shù)為n，屬性個數(shù)為m，步驟1 計算β相關族的時間復雜度為O(n2m)；步驟2是基于β相關族求取屬性約簡，其時間復雜度為O(min{m，n})。因此，算法RFVPCRS的時間復雜度為O(n2m+min{m，n})。

4 實驗與結果分析

基于本文提出的屬性約簡算法RF-VPCRS，選用UCI（University of California Irvine）公開數(shù)據(jù)集biodeg、mfeat_fac 進行參數(shù)分析，以給出算法參數(shù)的推薦范圍?；谕扑]的參數(shù)，選用公開數(shù)據(jù)集NSL-KDD 以驗證算法的有效性。在屬性約簡階段，選用以下三種屬性約簡算法作為對比：基于鄰域粗糙集的屬性約簡算法NRS（Neighborhood Rough Sets）［22］，基于模糊粗糙集依賴度的屬性約簡算法NFRS（Neighborhood Fuzzy Rough Sets）［23］和基于信息熵的屬性約簡算法HANDI（Heuristic Algorithm based on Neighborhood Discrimination Index）［24］。在模型分類階段，選用kNN（k=3）和支持向量機（Support Vector Machine，SVM）兩種分類器以驗證所選屬性的有效性。

該數(shù)值實驗基于Matlab R2018a 軟件完成，運行環(huán)境為：macOS Catalina 10.15.3 系統(tǒng)，2.7 GHz 四核Intel Core i7 處理器，8 GB內存。

4.1 參數(shù)分析

數(shù)據(jù)集biodeg 的樣本數(shù)為1 055，條件屬性個數(shù)為41；數(shù)據(jù)集mfeat_fac的樣本數(shù)為2 000，條件屬性個數(shù)為216。

本文提出的屬性約簡算法共兩個參數(shù)：鄰域ε和變精度β。其中鄰域ε以0.1為步長在[0，1]區(qū)間內變化，變精度β以0.002 為步長在[0.98，1]區(qū)間內變化，kNN（k=3）和SVM 的精度結果分別如圖1～2所示。

圖1 分類精度隨鄰域參數(shù)變化Fig.1 Classification accuracy changing with neighborhood parameter

圖2 分類精度隨變精度參數(shù)變化Fig.2 Classification accuracy changing with variable precision parameter

從圖1 可以看出，兩個數(shù)據(jù)集均在區(qū)間[0，0.5]內取得最高精度，特別是mfeat_fac，在區(qū)間[0.5，1]內的精度為0。所以，鄰域ε的推薦范圍為[0，0.5]。

從圖2 可以看出，由于數(shù)據(jù)集不同，變精度β對分類精度的影響不同。在區(qū)間[0.99，1]內，數(shù)據(jù)集可以取得較高的精度，所以變精度β的推薦范圍為[0.99，1]。

4.2 入侵檢測數(shù)據(jù)集及評價指標

本文選用的數(shù)據(jù)集NSL-KDD是KDD’99數(shù)據(jù)集的合理化去重版本。該數(shù)據(jù)集無缺失值，每個樣本有41 個條件屬性，其中3個字符型屬性和38個數(shù)字型屬性。用于模型訓練的訓練集共23 種類型，包括正常狀態(tài)Normal 和其他22 種攻擊類型，測試數(shù)據(jù)集共40 種類型，包括正常狀態(tài)Normal 和39 種攻擊類型（包括17 種訓練集中所沒有的攻擊類型）。在進行模型訓練之前，首先將條件屬性中的3 個字符型數(shù)據(jù)進行編碼，再將全部41 個條件屬性的值分別進行歸一化處理，公式為：。決策類別中的攻擊類型可分為四大類：端口監(jiān)視或掃描（Surveillance and Probing，Probe），拒絕服務攻擊（Denial of Service，DoS），未授權的本地超級用戶特權訪問（User to Root，U2R）和來自遠程主機的未授權訪問（Remote to Local，R2L）。具體類別劃分如表1 所示。條件屬性名稱編碼如表2所示。

本文采用準確率（ACCuracy，ACC）、召回率（REcall，RE）作為評估指標。準確率的計算式為，召回率的計算式為。其中：TP表示將正常樣本預測為正常的樣本數(shù)；FP表示將正常樣本預測為異常的樣本數(shù)；FN表示將異常樣本預測為正常的樣本數(shù)。

表1 NSL-KDD數(shù)據(jù)集的決策類別劃分Tab.1 Decision classification of NSL-KDD dataset

表2 NSL-KDD數(shù)據(jù)集中條件屬性名稱的編碼Tab.2 Coding of condition attribute names in NSL-KDD dataset

4.3 結果分析

本實驗中采用的鄰域參數(shù)ε為0，變精度β的取值為0.999 9。為了對比不同的約簡算法在不同數(shù)據(jù)規(guī)模下約簡時間的變化，故將數(shù)據(jù)訓練集按比例分為含樣本數(shù)為3 734、7 515、15 949、30 849的四份訓練集。

四份訓練集下的約簡時間如表3 所示。由于HANDI 和NFRS 在樣本量為15 949 和30 849 的數(shù)據(jù)集上計算約簡所需內存已超過本機最大內存而無法進行運算，故用“—”表示。從表3 可以看出，RF-VPCRS 的時間遠少于其他算法，在每份訓練集下都用時最短。特別是在樣本量大的訓練集上，RFVPCRS 的優(yōu)勢更為明顯。在四種算法中，NFRS 的運行所需時間最長，特別是在樣本量為7 515的數(shù)據(jù)集上，NFRS算法運行所需時長為RF-VPCRS算法的96倍。

表3 四種算法的約簡時間 單位：sTab.3 Reduction time of four algorithms unit：s

四份訓練集下的約簡整體準確率如表4 所示。從表4 中可以看出，kNN（k=3）和SVM 的整體最高準確率都在RFVPCRS 中取得，分別為90.53%和89.07%。RF-VPCRS、NRS和NFRS 三種算法在KDDTrian_7515 數(shù)據(jù)集上的整體準確率都高于KDDTrian_3734 數(shù)據(jù)集，而HANDI 算法的結果與之相反。

對比四種算法在KDDTrian_7515 數(shù)據(jù)上選擇的屬性個數(shù)和所選屬性編碼，結果如表5 所示?？梢钥闯觯琋RS 算法所選的屬性個數(shù)最少，其次為HANDI 算法，而RF-VPCRS 和NFRS所選的屬性個數(shù)相對較多，為23 個。屬性編碼中所列的屬性順序是每種算法在選擇屬性時的先后順序，體現(xiàn)了屬性在每種算法中的重要度，越先被選擇，則說明該屬性在算法中的重要程度越高。

表4 四種算法的約簡整體準確率 單位：%Tab.4 Overall reduction accuracy of four algorithms unit：%

表5 四種算法選擇的屬性個數(shù)和屬性編碼Tab.5 Number and coding of attributes selected by four algorithms

在算法RF-VPCRS進行屬性約簡后，再使用kNN（k=3）分類器對KDDTrian_7515進行分類，所得的混淆矩陣如圖3所示。

圖3 混淆矩陣Fig.3 Confusion matrix

具體分析各個類別下的準確率和召回率，如表6 所示。由表6可以看出，Normal的準確率可達97%。

表6 本文算法在五種類別下的準確率和召回率Tab.6 Accuracy and recall of proposed algorithm in five categories

5 結語

針對現(xiàn)有粗糙集屬性約簡算法時間和空間復雜度高，以及抗數(shù)據(jù)噪聲能力不強的問題，本文提出了變精度覆蓋粗糙集決策系統(tǒng)上的相關族屬性約簡算法RF-VPCRS，相較于其他屬性約簡算法，RF-VPCRS 具有計算約簡時間短的優(yōu)點，且可以處理大樣本數(shù)據(jù)集。在入侵檢測數(shù)據(jù)NSL-KDD 上的數(shù)值實驗結果表明，該算法所選的特征子集在分類器上有較好的分類能力。在今后的研究中，我們將繼續(xù)利用此方法研究其他入侵檢測數(shù)據(jù)。