一種基于多層決策樹分類的入侵檢測方法

方偉 黃澤斌 唐鄭熠 王金水

摘 要：分類技術(shù)在應(yīng)用于入侵檢測時，會因為待識別的用戶行為類型的增加，造成分類性能的下降，從而影響檢測的準確率。針對這一問題，本文研究了數(shù)據(jù)記錄類型所存在的層次性現(xiàn)象，并據(jù)此提出了一種多層分類方法，以減少分類算法所需要識別的記錄類型。以決策樹為分類算法，使用該方法對KDD_Cup_99數(shù)據(jù)集訓(xùn)練多層分類模型，取得了良好的分類性能，特別是明顯改善了小比例樣本的識別性能。

關(guān)鍵詞：入侵檢測; 分類; 決策樹; 類型層次; 多層分類模型

中圖分類號：TP393

文獻標識碼： A

文章編號?1000-5269（2020）05-0095-07???DOI：10.15958/j.cnki.gdxbzrb.2020.05.15

入侵檢測是網(wǎng)絡(luò)安全防護的重要技術(shù)之一，是指對入侵行為的檢測與識別。它通過對網(wǎng)絡(luò)行為、安全日志、審計數(shù)據(jù)等信息的分析，來判斷網(wǎng)絡(luò)或系統(tǒng)中是否出現(xiàn)違反安全策略的攻擊行為[1]。作為一種主動的安全防護技術(shù)，入侵檢測可以在攻擊行為產(chǎn)生危害前進行攔截，并且對內(nèi)部和外部的攻擊或危險行為都能提供有效的防護，因此被視為防火墻技術(shù)的必要補充。

入侵檢測技術(shù)的基本原理是通過對相關(guān)數(shù)據(jù)的分析，構(gòu)建正?；虍惓Ｐ袨榈哪Ｐ?，與用戶行為進行比較匹配，以甄別出可能具有危害性的行為[2-3]。因此，從相關(guān)數(shù)據(jù)中分析發(fā)掘出有效的行為特征與模式是入侵檢測技術(shù)的核心與關(guān)鍵。數(shù)據(jù)挖掘作為一種從海量數(shù)據(jù)中搜索挖掘隱藏信息的有效技術(shù)，十分適用于入侵檢測，包括分類、聚類、異常檢測在內(nèi)的多種數(shù)據(jù)挖掘技術(shù)都在入侵檢測領(lǐng)域取得了顯著的成效[4]。

分類是入侵檢測中較為常用的技術(shù)，研究人員使用了多種不同的分類算法來區(qū)分用戶的正常行為和攻擊行為：段丹青使用支持向量機（support?vector machine，SVM）算法對用戶行為進行分類[5]，取得了97%的分類正確率，但其試驗只將用戶行為分為正常和異常兩種類型，不能充分說明SVM算法的分類能力;馬占飛等[6]采用粒子群算法來調(diào)整SVM算法的參數(shù)，在對5種用戶行為分類的試驗中取得了93%的正確率，同時根據(jù)其對比試驗，傳統(tǒng)的SVM算法在對同樣的數(shù)據(jù)集進行分類時，正確率為85%;夏景明等采用隨機森林算法對用戶行為進行分類[7]，其正確率高達99%，但其同樣只將用戶行為分為兩類，缺乏對復(fù)雜類型分類能力的證明;丁紅衛(wèi)等采用深度卷積神經(jīng)網(wǎng)絡(luò)對5種用戶行為進行分類[8]，并更為細化地比較了每種類型的分類正確率，最高達99%，但該種方法不能對所有類型都保持理想的分類能力，最低的分類正確率僅有64%;SHONE等提出了一種多層非對稱深度自編碼器算法[9]，對5種用戶行為進行分類，除了小比例樣本，都取得了100%的正確率，但由于深度學(xué)習(xí)技術(shù)的固有缺陷，其所訓(xùn)練的分類模型缺乏可解釋性。

本文研究了數(shù)據(jù)集中記錄類型的層次性現(xiàn)象，提出了一種多層次的分類方法，對處于相同層次的記錄類型訓(xùn)練分類模型，從而得到多個針對不同層次記錄類型的分類模型，能夠根據(jù)記錄類型的層次性實現(xiàn)自頂向下的識別。將該方法應(yīng)用在入侵檢測中，不僅能夠?qū)崿F(xiàn)高效準確的行為分類，而且能夠靈活地控制分類的粗細程度。以決策樹作為分類算法，在權(quán)威的入侵檢測數(shù)據(jù)集上進行試驗，結(jié)果表明該方法具有理想的檢測性能，并且能夠有效地緩解由于行為類型增多造成的檢測性能下降的問題。

1?預(yù)備知識

1.1?決策樹分類

分類是指根據(jù)數(shù)據(jù)記錄的各個屬性取值，識別數(shù)據(jù)記錄所屬的類型。通過已有數(shù)據(jù)可以訓(xùn)練得到分類模型，其定義如下：

決策樹是一種樹形的分類模型，其節(jié)點分為測試節(jié)點（非葉子節(jié)點）和決策節(jié)點（葉子節(jié)點）兩類：每個測試節(jié)點包含一個測試條件，每條出邊是測試條件的一個輸出;每個決策節(jié)點包含一個記錄類型的取值，其定義如下：

在使用決策樹對記錄X進行分類時，從根節(jié)點開始進行測試，即計算v = nt0（X），根據(jù)v的值決定下一個測試節(jié)點，直到遇到?jīng)Q策節(jié)點終止，即得到該記錄的類型。

Iterative dichotomiser 3（ID3）是Quinlan于1986年提出的算法，它以貪心策略為基礎(chǔ)，以信息增益作為測試條件有效性的度量指標，是第一個具有廣泛影響力的決策樹算法。Classification 4.5（C4.5）算法同樣是由Quinlan于1993年提出的，它是ID3算法的改進，既能夠處理離散型的屬性，也能夠處理連續(xù)性的屬性，是目前最常用的決策樹算法[10]。

1.2?入侵檢測

入侵檢測是通過分析用戶行為或系統(tǒng)的相關(guān)數(shù)據(jù)，提取各種行為模式或特征，進而識別出系統(tǒng)中存在的危險行為。目前的入侵檢測技術(shù)大致可以分為兩類：

（1）異常檢測：構(gòu)建安全的行為模型作為用戶行為的評價標準，當(dāng)用戶行為明顯有別于安全行為模型時，則認為出現(xiàn)了入侵。

（2）特征檢測：根據(jù)已知的入侵來提取并構(gòu)建入侵行為的特征庫，當(dāng)用戶行為與特征庫中的某個特征模式匹配時，則認為出現(xiàn)了入侵。

在設(shè)計一種新的入侵檢測方法時，需要一個包含正常行為和入侵行為的數(shù)據(jù)集，用于檢測新方法是否有效。目前最為權(quán)威的入侵檢測數(shù)據(jù)集是1999年國際知識發(fā)現(xiàn)和數(shù)據(jù)挖掘競賽所公布的數(shù)據(jù)挖掘與知識發(fā)現(xiàn)數(shù)據(jù)集（knowledge discovery and data mining，KDD_Cup_9）[11]，它來源于1998年MIT的Lincoln試驗室所承擔(dān)的DARPA入侵檢測評估項目。該項目建立了一個模擬軍事網(wǎng)絡(luò)中各類入侵行為的數(shù)據(jù)集，共計約700萬條記錄，包含5大類網(wǎng)絡(luò)攻擊?；谠摂?shù)據(jù)集，Columbia University的入侵檢測系統(tǒng)（intrusion detection systems，IDS）試驗室進行了精簡和完善，發(fā)布了KDD_Cup_99數(shù)據(jù)集。該數(shù)據(jù)集包括兩個版本，完全版本包括約500萬條記錄，而10%的抽樣版本包含約50萬條記錄。迄今為止，KDD_Cup_99是有關(guān)入侵檢測的研究中應(yīng)用最為廣泛的驗證數(shù)據(jù)集。

2?多層決策樹分類方法

2.1?基本原理

決策樹是一種簡單有效的分類技術(shù)，易于使用和理解。但是，當(dāng)需要分類的數(shù)據(jù)記錄具有較多的類型時，會使決策樹的規(guī)模變得龐大，從而降低分類的準確率與效率。因此，減少數(shù)據(jù)記錄的類型，是提高決策樹分類技術(shù)性能的可行途徑。但數(shù)據(jù)記錄類型的減少，不能以弱化分類需求為手段，否則可能導(dǎo)致分類技術(shù)的效果大大降低。

在分類問題中，存在著數(shù)據(jù)記錄的類型具有層次性的現(xiàn)象，例如，人類是哺乳動物的子類、轎車是汽車的子類等。然而決策樹無法識別類型之間的包含關(guān)系，其分類性能也會受到一定程度的影響。

針對這一問題，可以對每一個層次的類型分別訓(xùn)練決策樹，從而顯著減少每棵決策樹所要劃分的類型數(shù)量。同時，通過多棵決策樹的組合，能夠保證對所有的類型完成分類。下面給出形式化定義。

對于兩個記錄類型x和y，若y是x的子類，則記為，子類關(guān)系的集合記為R。

記錄類型如果具有層次性，則可以表示為一棵樹。由于樹的0層只有一個根節(jié)點，即在該層次上只有一個類型，這在實際的分類問題中是不可能出現(xiàn)的。為了解決這個問題，可以在記錄類型的最高層次上，額外添加一個origin類型，作為最高層次類型的父類型，用偽代碼表達為：

其中：T是一棵決策樹;

（2）p是一個記錄類型;

（3）Pp是p的子類型集合。

算法1描述了如何對訓(xùn)練數(shù)據(jù)集D（記錄類型集合為P，子類關(guān)系集合為R），訓(xùn)練出一個分層決策森林F。

算法1對每個記錄類型p，找出其所有子類型集合Q。根據(jù)Q，篩選出D的子集DS，其所含數(shù)據(jù)記錄的類型（d.type），或者屬于Q，或者是Q中某個類型的子孫類型，并將數(shù)據(jù)記錄的類型修改為Q中的對應(yīng)類型。由數(shù)據(jù)子集DS和記錄類型子集Q，使用決策樹算法Train Decision Tree（如C4.5）訓(xùn)練出一棵決策樹T，從而得到一棵分層決策樹TH = （T， p， Q）。所有的分層決策樹構(gòu)成分層決策森林F。

算法2是使用分層決策森林F對數(shù)據(jù)記錄d進行分類的過程。

首先從分層決策森林F中選擇TH·p = origin的分層決策樹，用其對記錄d進行分類，得到d在該分層決策樹上的類型t。若存在另一棵TH·p = t的分層決策樹，則繼續(xù)使用TH對d進行分類，得到新的、更為細化的類型。重復(fù)以上過程，直到不存在TH·p = t。

基于多層決策樹的分類模型具有以下優(yōu)點：

（1）能有效降低決策樹的規(guī)模，避免出現(xiàn)具有大量節(jié)點的復(fù)雜決策樹。

（2）分類模型易于解釋和表達。

（3）能夠根據(jù)分類的粒度要求，提前終止對數(shù)據(jù)記錄的細化分類，從而提高分類效率。

2.2?KDD_Cup_99數(shù)據(jù)集的多層決策樹模型

本節(jié)以KDD_Cup_99數(shù)據(jù)集為例，說明多層決策樹的構(gòu)建與應(yīng)用方法。

KDD_Cup_99數(shù)據(jù)集中的記錄類型共計有23種，除了表示正常訪問的normal類型，剩下的22種類型都表示攻擊訪問，分屬于4大類網(wǎng)絡(luò)攻擊類型[12]，具有明顯的層次性。為了進一步減少單層決策樹所要分類的記錄類型，為其增加一個attack類，作為所有攻擊類型的父類。數(shù)據(jù)記錄類型的層次結(jié)構(gòu)如圖2所示。

根據(jù)算法1，可以訓(xùn)練出由以下6棵分層決策樹構(gòu)成的決策樹森林：

對于一條數(shù)據(jù)記錄，如果它的實際類型是guess-passwd，則會先后調(diào)用TH1、TH2和TH5進行分類。分類過程也可以根據(jù)分類需求，終止在某個中間層次。

3?試驗與結(jié)果分析

3.1?數(shù)據(jù)預(yù)處理

KDD_Cup_99數(shù)據(jù)集共含有4 898 430條記錄，但在記錄類型上的分布并不均衡，并且部分記錄類型的數(shù)據(jù)量過于稀少，對于決策樹的訓(xùn)練沒有實際意義，如表1所示。為了保證記錄類型的均衡，以達到更好的訓(xùn)練效果，將所有類型的記錄數(shù)量限制在2 000～40 000的范圍內(nèi)，故對數(shù)據(jù)集進行以下抽樣處理：

（1）若某種類型的記錄數(shù)量小于2 000，則將該類型的記錄全部刪除。

（2）若某種類型的記錄數(shù)量大于40 000，則從該類型的記錄中隨機抽取40 000條。

（3）若某種類型記錄數(shù)量在2 000～40 000之間，則全部保留。

經(jīng)過抽樣處理后，用于試驗的數(shù)據(jù)集中所包含的記錄類型及其數(shù)量如表3所示。

對于每一種類型的記錄，都取50%作為訓(xùn)練集，50%作為測試集。因此，用于試驗的數(shù)據(jù)集記錄總量為1 096 085條，其中訓(xùn)練集數(shù)量為548 041條，測試集數(shù)量為548 044條。

3.2?試驗過程與結(jié)果

本文的試驗環(huán)境如表4所示。

試驗過程：

（1）對類型屬于{normal， attack}的記錄訓(xùn)練分類模型T1，其對記錄類型的分類準確率記為Acc（T1， normal）和Acc（T1， attack）。

（2）對類型屬于{dos， probel}的記錄訓(xùn)練分類模型T2，其對記錄類型的分類準確率記為Acc（T2， dos）、Acc（T2， probel）。

（3）對類型屬于{back， neptune， smurf}的記錄訓(xùn)練分類模型T3，其對記錄類型的分類準確率記為Acc（T3， back）、Acc（T3， neptune）、Acc（T3， smurf）。

（4）對類型屬于{ipsweep， nmap， portsweep， satan}的記錄訓(xùn)練分類模型T4，其對記錄類型的分類準確率記為Acc（T4， ipsweep）、Acc（T4， nmap）、Acc（T4， portsweep）、Acc（T4， satan）。

試驗結(jié)果如表5所示。

根據(jù)算法2，一條記錄要經(jīng)過多棵決策樹的分類，直至最底層的類型，因此其分類準確率應(yīng)等于上層類型分類準確的乘積，即：

將試驗數(shù)據(jù)集直接使用C4.5決策樹算法進行分類作為對照試驗，結(jié)果如表6所示。

由表6的對照試驗結(jié)果可知，多層決策樹分類方法具有較為優(yōu)異的性能，對各種類型的記錄都保持了很高的分類準確率。對比普通的決策樹分類方法，由于其每次所需要區(qū)分的記錄類型較少，對記錄特征的識別更為準確。普通決策樹分類方法不能有效地區(qū)分neptune和smurf兩種記錄類型，而多層決策樹分類方法則能夠進行有效的識別。

4?結(jié)語

分類技術(shù)在入侵檢測中已經(jīng)得到了較為成功的應(yīng)用，攻擊行為的識別效率和準確率方面都取了較為理想的結(jié)果。但分類技術(shù)在處理多類型數(shù)據(jù)集時，會產(chǎn)生模型構(gòu)建困難、分類準確率下降的問題。本文針對這一問題，結(jié)合入侵行為的類型所具有的層次性特點，提出了一種多層分類的入侵檢測方法，并以決策樹算法進行了實現(xiàn)。試驗結(jié)果表明，該方法能夠有效提高入侵檢測的識別準確率，特別是對小比例的入侵行為的識別上，具有較大的改進。

在本文工作的基礎(chǔ)上，可進一步展開以下研究工作：

（1）研究和比較多層分類模型與單層分類模型的復(fù)雜度。

（2）研究不同分類算法對多層分類模型的性能影響。

（3）研究新出現(xiàn)的攻擊行為類型，并構(gòu)建相關(guān)的數(shù)據(jù)集。

參考文獻：

[1]李威，?楊忠明. 入侵檢測系統(tǒng)的研究綜述[J].?吉林大學(xué)學(xué)報（信息科學(xué)版），?2016，?34（5）： 657-662.

[2]ZARPELO B B，?MIANI R S，?KAWAKANI C T，?et al.?A survey of intrusion detection in Internet of things[J].?Journal of Network & Computer Applications，?2017，?84（3）：25-37.

[3]陳俊，?陳孝威.?基于關(guān)聯(lián)規(guī)則挖掘的IPv6入侵檢測系統(tǒng)研究[J].?貴州大學(xué)學(xué)報（自然科學(xué)版），?2013，?30（2）： 66-71.

[4]BUCZAK A L.?A survey of data mining and machine learning methods for cyber security intrusion detection[J].?IEEE Communications Surveys & Tutorials，?2017，?18（2）： 1153-1176.

[5]段丹青.?入侵檢測算法及其關(guān)鍵技術(shù)研究[D].?長沙： 中南大學(xué)，?2007.

[6]馬占飛，?陳虎年，?楊晉，?等.?一種基于IPSO-SVM算法的網(wǎng)絡(luò)入侵檢測方法[J].?計算機科學(xué)，?2018，?45（2）： 231-235.

[7]夏景明，?李沖，?談玲，?等.?改進的隨機森林分類器網(wǎng)絡(luò)入侵檢測方法[J].?計算機工程與設(shè)計，?2019，?40（8）： 2146-2150.

[8]丁衛(wèi)紅，?萬良，?周康，?等.?基于深度卷積神經(jīng)網(wǎng)絡(luò)的入侵檢測研究[J].?計算機科學(xué)，?2019，?46（7）： 50-55.

[9]SHONE N，?NGOC T N，?PHAI V D，?et al.?A deep learning approach to network intrusion detection[J].?IEEE Transactions on Emerging Topics in Computational Intelligence，?2018，?2（1）： 41-49.

[10]FLETCHER S，?ISLAM M Z，?Decision tree classification with differential privacy： a survey[J].?ACM Computing Surveys，?2016，?48（5）： 161-172.

[11]SIDDIQUE K，?AKHTAR Z，?ASLAM K F，?et al.?KDD_Cup_99 data sets： a perspective on the role of data sets in network intrusion detection research[J].?Computer，?2019，?52（2）： 41-51.

[12]WANG Y，?YANG K，?JING X，?et al.?Problems of KDD_Cup_99 dataset existed and data preprocessing[J].?Applied Mechanics and Materials，?2014，?66（7）： 218-225.

（責(zé)任編輯：于慧梅）