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

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

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

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

0 引言

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

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

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

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

1 預備知識

1.1 經典粗糙集

1.2 覆蓋粗糙集

經典粗糙集模型中等價關系的嚴格性，導致其只能用來處理離散型數據，故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］給定信息系統是U上的一個覆蓋?；跇O小描述的上下近似算子分別定義為：

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

1.3 變精度覆蓋粗糙集

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

1.4 相關族

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

2 變精度覆蓋粗糙集決策系統屬性約簡

根據論域中的對象是否都能被劃分至正域里，將覆蓋決策系統分為協調覆蓋決策系統和不協調覆蓋決策系統。

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

3 算法設計

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

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

4 實驗與結果分析

基于本文提出的屬性約簡算法RF-VPCRS，選用UCI（University of California Irvine）公開數據集biodeg、mfeat_fac 進行參數分析，以給出算法參數的推薦范圍?；谕扑]的參數，選用公開數據集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）兩種分類器以驗證所選屬性的有效性。

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

4.1 參數分析

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

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

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

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

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

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

4.2 入侵檢測數據集及評價指標

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

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

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

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

4.3 結果分析

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

四份訓練集下的約簡時間如表3 所示。由于HANDI 和NFRS 在樣本量為15 949 和30 849 的數據集上計算約簡所需內存已超過本機最大內存而無法進行運算，故用“—”表示。從表3 可以看出，RF-VPCRS 的時間遠少于其他算法，在每份訓練集下都用時最短。特別是在樣本量大的訓練集上，RFVPCRS 的優勢更為明顯。在四種算法中，NFRS 的運行所需時間最長，特別是在樣本量為7 515的數據集上，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 數據集上的整體準確率都高于KDDTrian_3734 數據集，而HANDI 算法的結果與之相反。

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

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

表5 四種算法選擇的屬性個數和屬性編碼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 結語

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