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

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

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

0 引言

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

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

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

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

1 預(yù)備知識

1.1 經(jīng)典粗糙集

1.2 覆蓋粗糙集

經(jīng)典粗糙集模型中等價(jià)關(guān)系的嚴(yán)格性，導(dǎo)致其只能用來處理離散型數(shù)據(jù)，故Bonikowski等［2］將等價(jià)關(guān)系推廣至覆蓋。

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

由于覆蓋相較于等價(jià)關(guān)系的復(fù)雜性，覆蓋粗糙集近似算子多達(dá)22 種，由于篇幅關(guān)系，本文只列舉其中1 種，具體內(nèi)容請參考文獻(xiàn)［20］。

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

在不會引起混淆的情況下，通常省略下標(biāo)C。

1.3 變精度覆蓋粗糙集

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

1.4 相關(guān)族

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

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

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

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

3 算法設(shè)計(jì)

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

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

4 實(shí)驗(yàn)與結(jié)果分析

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

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

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ū)間內(nèi)變化，變精度β以0.002 為步長在[0.98，1]區(qū)間內(nèi)變化，kNN（k=3）和SVM 的精度結(jié)果分別如圖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]內(nèi)取得最高精度，特別是mfeat_fac，在區(qū)間[0.5，1]內(nèi)的精度為0。所以，鄰域ε的推薦范圍為[0，0.5]。

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

4.2 入侵檢測數(shù)據(jù)集及評價(jià)指標(biāo)

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

本文采用準(zhǔn)確率（ACCuracy，ACC）、召回率（REcall，RE）作為評估指標(biāo)。準(zhǔn)確率的計(jì)算式為，召回率的計(jì)算式為。其中：TP表示將正常樣本預(yù)測為正常的樣本數(shù)；FP表示將正常樣本預(yù)測為異常的樣本數(shù)；FN表示將異常樣本預(yù)測為正常的樣本數(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 結(jié)果分析

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

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

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

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

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

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

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

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

圖3 混淆矩陣Fig.3 Confusion matrix

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

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

5 結(jié)語

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