基于決策樹和協議分析的入侵檢測研究

摘要：當前大多數入侵檢測產品使用的是基于規則的簡單模式匹配技術，它們存在著資源消耗量大、誤報率高以及隨著網速的提高出現丟包等問題。針對這些問題，提出了用決策樹算法實現基于協議分析的入侵檢測方法。試驗結果表明，該方法具有較高的檢測速度和較低的正誤報率。

關鍵詞：決策樹； 協議分析； 入侵檢測

中圖分類號：TP309文獻標志碼：A

文章編號：1001-3695(2007)12-0171-03

0引言

當前大多數異常入侵檢測系統使用的是簡單模式匹配技術。然而簡單模式匹配技術有如下一些問題：a)支持這種方法的計算量巨大，影響了檢測效率。b)簡單模式匹配不理解規則中入侵特征的真正含義，僅靠強力探測方式進行特征串匹配。一些特征串值只有在某個特定域內才有特殊含義，如果在其他域內匹配到時就會產生誤報。

協議分析技術利用網絡協議的高度規則性對報頭中相應位置的協議信息進行分析，只檢測對入侵檢測有用的字段。在協議解碼部分不僅對低層協議解碼，而且還對應用層協議進行解碼。因為協議分析技術引導搜索數據包明確特定的部分而不是整個有效載荷，減少了搜索空間，所以能提高入侵檢測的效率。又由于協議分析技術將搜索空間降低為單個的域，確保特征串的實際意義被真正理解。例如，可以通過檢測狀態碼中是否含有代表服務被拒絕的“403”來發現是否有未授權訪問網頁^[1]。然而簡單模式匹配方法則可能在非狀態碼的其他域內搜索到“403”，于是將正常數據判斷為入侵數據而導致正誤判。協議分析技術較好地解決了這個問題，降低了正誤判率，被認為是下一代入侵檢測的希望。

隨著網絡流量的增大和入侵種類的增多，數據挖掘被引入入侵檢測^[2]。決策樹^[3，4]方法作為數據挖掘的一種，通過大量樣本數據的訓練提取對入侵行為最具概括性的描述；加上算法生成的決策樹模型簡單優化，使得對大量數據的預測過程中總的匹配次數減少，檢測結果更加準確、高效。決策樹方法被用于對現有的入侵檢測系統檢測規則進行優化^[5]，目的是建立屬性與類別之間的關系，從而有效減少手工分析入侵行為和入侵模型編碼的工作量，提高了入侵檢測的效率。這正好適應了網絡數據量增大和入侵種類增多的趨勢。

本文將決策樹與協議分析技術結合起來用于入侵檢測系統。它們的結合不僅因為其各自的優勢對于提高檢測效率和降低正誤判率有很好的作用，還因為生成決策樹和檢測對象所需的屬性—值形式的數據是由協議分析得來的。協議分析是入侵檢測決策樹生成的基礎和應用的對象。

1入侵檢測決策樹

決策樹方法是數據挖掘中分類方法的一種。其核心思想是選擇某種決策樹算法利用樣本數據生成決策樹模型，然后用生成的決策樹對未知數據進行分類預測^[5]。決策樹模型的生成過程也就是分類模型的生成過程，用生成的決策樹對未知數據進行分類的過程就是分類模型的預測過程。入侵檢測可以被看做是對網絡數據是正常還是入侵的預測，即通過一個分類模型將網絡數據分為入侵和正常兩類。由于決策樹有創建優化的分類模型和高效的分類預測的作用，將它應用到入侵檢測問題中有著非常重要的意義和實際應用價值。

1．1決策樹算法思想及算法選擇

決策樹算法基本思想為：假設R為訓練樣本集，每一個樣本均有若干個屬性。從樣本集根節點出發，根據對屬性值的測試結果逐漸分裂產生分支節點，直到產生一棵完整的樹。要為R構造決策樹必須首先確定屬性測試選擇標準，選出當前檢測屬性。常用的屬性選擇標準有信息增益、信息增益率和gain等。按屬性選擇標準并按當前屬性的n個值將R分裂為n個子集。若第i個子集Ri含有的所有記錄的類別標簽一致，該節點就成為決策樹的葉節點，停止分裂并以所屬分類標記這個葉節點；而對不滿足此條件的R的其他子集按照上述方法繼續分裂，直到所有子集所含記錄均屬于一個類為止。

決策樹方法的起源是概念學習系統CLS，發展到ID3算法為高潮，后來又演化為能處理連續屬性的C4.5算法。有名的決策樹算法還有CART和SLIQ等。ID3算法選擇具有最高信息增益的屬性作為測試屬性，只能處理離散屬性。C4.5算法^[6，7]對ID3算法作了改進，選擇具有最高信息增益率的屬性作為測試屬性，能處理連續屬性。CART算法可以處理高度傾斜或多態的數值型數據，也可以處理順序或無序的類屬性數據。對于協議分析問題時將協議字段作為屬性，它們中既有離散型的又有連續型的，因此不能用ID3算法。又由于網絡數據僅有兩個分類，并不復雜，也無高度傾斜或多態等問題。如果用太復雜的算法，反而會影響效率。本系統選用C4．5算法。

1．2入侵檢測決策樹結構模型

入侵檢測決策樹由節點和將節點連接起來的分支組成。節點分為普通節點和葉節點。其中每個普通節點表示對某個協議字段屬性的檢測。它由一個數據結構表示。該數據結構記載了此節點的測試屬性、屬性類別、默認最佳分類、指向分支列表的指針，以及當此屬性為連續型時的一些域值數據。每個普通節點會有一個或多個分支。每個分支代表協議字段屬性的一個值。該值可能是固定離散的，如網絡服務屬性可能的值為FTP、Telnet等；也可能是連續的，如持續時間，連續值由“閾”來表示。每個分支引向另一個節點。決策樹的葉節點則標記了匹配到該節點處的記錄所屬的分類，而其他部分為空。描述節點的數據結構如下：

typedef struct _treerec {

Attribute Tested; 節點測試屬性（通過計算最高增益率得來）

Int NodeType; 樹節點的類型（離散型或連續型）

Int LeafClass; 節點默認最佳分類（在檢測過程中出現異常或未知屬性值時，以此分類標記）

Int ItemNumber; 匹配到此節點處訓練數據記錄的數量（用于計算此節點的默認最佳分類）

int * ClassNumber； 指向每個分類含訓練數據記錄的數量標的指針（用于計算此節點的默認最佳分類）

int Forks; 此節點處分支數量（屬型可能值的個數）

float Cut； 連續屬性的閾（用于處理連續屬性）

float Lower； 閾的下限（用于處理連續屬性）

float Upper； 閾的上限（用于處理連續屬性）

float Mid； 50%點（用于處理連續屬性）

Tree * Branch; Branch[x]=屬性值為x的子樹

}TreeRec;

為了簡單直觀地表示入侵檢測決策樹，將決策樹模型的一部分作出一個示例圖，如圖1所示。其中service、URL、FTP command和content分別是決策樹中標記節點的屬性。Seivice屬性的值有FTP、HTTP、Telnet等分別標記服務屬性的分支。此處不一一列出。葉節點由I和N分別標記分類intrusion和normal。

1．3入侵檢測決策樹的生成過程

決策樹算法利用由一個個連接記錄組成的訓練數據出發，在生長樹的每一步中通過計算，選擇信息增益率最高的屬性作為當前節點的測試屬性，最后得出可用于判斷連接記錄所屬類型的決策樹。決策樹的生成過程如下：

a）建立數據分類和屬性文件

數據分類包含intrusion和normal兩類。屬性文件用于存放屬性名、屬性類型以及離散型屬性的所有可能取值。其中屬性類型根據每個屬性對應的協議字段的特點而標記為離散型或連續型。

b）準備訓練數據

由于決策樹檢測模型的生成是以訓練數據為基礎的，訓練數據必須是正常數據與涵蓋各種入侵類型的入侵數據的混合。它們可以是由專家構建的專門用于訓練的數據，也可以是長期積累下來捕獲得到的網絡數據的集合，并且不斷補充新的網絡數據樣本。一般訓練數據源是以tcpdump格式存儲的。訓練數據源經過協議分析預處理生成決策樹可以處理的屬性—值的二維表形式。表中每一列代表一個屬性，每一行代表一個連接信息。

c）由信息增益率選擇測試屬性創建決策樹

對目前的二維表，建立一個節點N。如果數據表中的數據均屬于同一類，N就是葉節點，在該葉節點上標上所屬的那一個類。如果數據表中沒有其他屬性可以考慮，N也是葉節點，按照少數服從多數的原則在葉節點上標上匹配至此節點處的訓練數據子集中大多數記錄所屬的類別；否則，根據信息增益比選出一個最佳屬性作為節點N的測試屬性。節點屬性選定以后，對于該測試屬性的每一個取值從N生出一個分支， 并將數據表中與該分支有關的數據收集起來形成分支節點的數據表。以此類推，重復以上過程為該節點建立子樹。

1．4用決策樹進行入侵檢測

檢測引擎就是通過遍歷入侵檢測決策樹來實現檢測工作的。網絡數據經過處理后，轉換成與訓練數據相同的格式。將屬性—值型記錄中與根節點測試屬性對應的屬性值提取出來，將此值與該節點發出的分支值（即該測試屬性的可能值）比較。如果找不到匹配的分支，則該記錄檢測結束，此記錄的分類為該節點的默認最佳分類。如果默認分類為入侵，則立即報警。如果此屬性值與某個分支值匹配，該分支將此記錄指向下一個節點，再對下一個節點屬性進行比較。依此往復，直到到達葉節點為止。葉節點所標記的分類變為該記錄的分類。

由此可見，對一條記錄進行檢測，它所走過的路程就是決策樹中的一條從根節點到葉節點的路徑。與必須一條條進行匹配的基于規則的簡單模式匹配方法相比較而言，節省了很多冗余的比較次數。又由于屬性選擇算法保證了構建的決策樹的簡單優化，減少了對大量網絡數據進行檢測過程中總的比較次數，提高了檢測效率。

2決策樹入侵檢測系統結構

為驗證決策樹算法的效果，筆者構建了用于對網絡協議分析的入侵檢測試驗系統。該系統主要由離線檢測模型生成部分和在線檢測兩部分構成，如圖2所示。

a)離線檢測模型，生成部分負責入侵檢測決策樹的生成。入侵檢測決策樹也就是檢測模型。它在系統中的作用相當于基于規則的入侵檢測系統中的規則集，而入侵檢測決策樹以更有效、更優化的組織方式將入侵特征以樹的結構組織起來。離線檢測模型生成部分包含決策樹生成器、協議分析器、訓練數據庫和訓練數據源四個部分。決策樹生成器是其核心部分，它接收來自訓練數據庫的數據，利用C4．5算法構建決策樹；協議分析器用于將以tcpdump格式的訓練數據源或捕獲的網絡數據包經過一系列處理，形成屬性—值形式的數據；處理過程包括IP分片合并、TCP會話重組和一些常用的應用層協議分析；訓練數據庫中的數據則是訓練數據源經過協議分析處理后形成的屬性—值結果。

b)在線檢測部分，負責對實時網絡數據包進行在線檢測。它包含數據接收器、協議分析器、檢測引擎及用戶界面。協議分析器用于對捕獲的網絡數據包進行處理，形成以屬性—值形式表示的數據，此數據格式與生成決策樹的訓練數據格式相同；檢測引擎以協議分析器輸出的屬性—值序列作為輸入，通過對決策樹進行遍歷來實現檢測功能；用戶界面用于檢測控制、報警和響應。

3系統運行流程

基于決策樹的入侵檢測系統運行流程包括訓練數據的生成過程、入侵檢測模型的生成過程和在線檢測過程三個步驟。

a）訓練數據生成。構造決策樹需要提供一個訓練數據集，訓練數據集是由一組記錄構成的。每條記錄是一個由關鍵字段組成的屬性—值向量；另外在每條記錄的末尾還有一個類別標記。一個具體的記錄用如下形式表示：(a1，a2，…，an;c)。其中：ai表示字段值；c表示類別。

由于網絡數據包是連續的二進制流，不滿足訓練數據的格式要求，為此，要將網絡數據包還原成基于傳輸層的連接記錄，有一些記錄還需要進行高層的協議分析。經過重組還原和協議分析后，按照協議的格式提取出需要的特征字段，生成屬性—值形式的二維表。其中：每行表示一個網絡連接；每列表示一個協議的字段或經過協議分析后提取的屬性。在每一行的末尾明確標記為N和I。其中，屬性通常有由IP協議分析得來的字段sip、dip、sport、dport、ttl、tos、fragid、ipoption、dsize、ip_proto，由TCP協議分析得來的字段flags、seq、ack、window，由ICMP協議分析得來的字段itype、icode、icmp_id、icmp_seq外；還有由應用層協議分析得來的字段，如針對HTTP協議的request method、URL、state code，針對Telnet協議的StartTime、Username、Logged in、command等。表1為一個簡要示例。

b）決策樹生成。以前面得到的二維表形式的訓練數據作為輸入，用C4．5算法生成決策樹。

c）在線檢測。協議分析和基于決策樹模型進行檢測是在線檢測中最重要的兩個部分。在線檢測中的協議分析部分與生成訓練數據時用到的協議分析技術一樣。檢測的過程就是對決策樹中一條分支遍歷的過程。

4實驗測試

實驗中用C4.5算法進行決策樹的構建，并以此決策樹作為檢測引擎的基礎。實驗環境為：主機處理器是Intel Pentium 2．80 GHz，內存512 MB，操作系統采用紅帽子Linux 7．3，內核是2．4．18。使用MIT Lincoln Labs 1998年用于DARPA入侵檢測評估的tcpdump數據文件^[8]作為訓練和測試數據。

實驗1基于決策樹和協議分析的檢測引擎與基于規則的簡單模式匹配的檢測引擎的性能比較。

決策樹生成模塊通過對訓練數據的學習訓練生成決策樹，并以檢測規則的形式提取出這些訓練數據中包含的入侵種類的相應規則。將訓練數據由少逐漸增加，生成的決策樹規模和相應的規則數量也逐漸增加。記錄基于決策樹的檢測引擎和基于規則的簡單模式匹配的檢測引擎處理287 MB數據包所需時間隨規則數量增加的變化情況，并將它們進行比較。實驗過程中，規則數從200條開始每次增加200然后增加400條，一直增加到1 200條。實驗結果數據如表2所示。將兩組數據比較得到如圖3所示的對比分析結果。

由實驗結果可以看到，在測試數據相同的前提下，當規則數量少于300條時，采用基于規則的簡單模式匹配技術所需檢測時間略少；隨著規則數量的逐步增加，基于決策樹的檢測引擎所需檢測時間大大少于前者。特別在規則數量達到1 200條時，采用基于規則的簡單模式匹配算法所需檢測時間是采用基于決策樹模型的檢測方法所需檢測時間的1．4倍。

實驗2應用層協議分析技術與簡單模式匹配技術的正誤報率的比較。

本實驗僅對常用的應用層HTTP、FTP和Telnet協議進行了分析。在對底層協議分析產生屬性字段的基礎上增添了針對應用層協議的屬性字段。例如HTTP增加的屬性字段有請求方法、請求頁面和狀態碼等。實驗環境同上。實驗過程為：首先收集一些僅在協議中某個特定字段內有意義的待檢測的入侵特征值；然后手工將這些值放入網絡包的數據部分，一共構建了25條測試數據。簡單模式匹配方法將它們均判為入侵，無法對這種情況進行正確判斷；而基于決策樹的協議分析入侵檢測方法對其中20條均進行了正確的判斷。

5結束語

本文采用決策樹C4．5算法實現了基于決策樹的協議分析網絡入侵檢測，將協議分析技術與決策樹方法有機地結合起來，在提高檢測效率和降低誤報率方面均取得了較好的效果。

a）高性能。由于本系統采用了協議分析技術，依托網絡協議的高度規則性，引導檢測引擎只搜索數據包明確特定的部分，有效地減少了搜索空間，大大提高了檢測效率。用決策樹模型對未知數據的預測過程即是對決策樹中某一分支的遍歷過程。該過程相對于簡單規則匹配技術對每一條規則均要逐一進行匹配而言，計算量小、搜索速度快。

b）減少正誤判。將搜索空間降低為單個的域，確保特征串的實際意義被正確理解，降低了正誤判。

c）只給定訓練數據和屬性選擇標準，程序就能自動生成決策樹，因而減少了數據挖掘方法從大量數據中發掘入侵特征的人力和人工編寫特征編碼的主觀性和低效率。

這并不代表一旦通過訓練數據生成決策樹模型后就一勞永逸了。因為基于決策樹的入侵檢測系統很難準確檢測訓練數據中不包含的新的入侵種類，所以訓練數據的質量也是決策樹模型是否有效的一個重要因素。訓練數據要盡可能全面地包含各種入侵類型，在一定的時間內要對訓練數據進行補充更新，以便將新的入侵特征更新到決策樹模型中。

參考文獻：

[1]LEE W. A data mining framework for constructing features and mo－dels for intrusion detection systems[D]. New York: Columbia University， 1999:22-26.

[2]FIELDING R， GETTYS J， MOGUL J， et al. HTTP/1．1 RFC 2616， Hypertext transfer protocol[S]. 2006.

[3]HAN Jian－wei， KAMBER M. Data mining concepts and techniques[M]. Beijing:China Machine Press， 2000:188－194.

[4]PECK L， TRACHIER G. Security technology decision tree tool[C]//Proc of the 38th Annual International Carnahan Conference on Security Technology. 2004:91-98.

[5]楊學兵，張俊.決策樹算法及核心技術[J].計算機應用與發展，2007，17(1):43-45.

[6]KRUEGEL C， TOTH T. Using decision trees to improve signature based intrusion detection[C]//Proc of the 6th International Workshop on the Recent Advances in Intrusion Detection(RAID). USA: Springer－Verlag， 2003:173－191.

[7]RUGGIERI S. Efficient C4.5[J]. IEEE Trans on Knowledge and Data Engineering， 2002，14(2):438-444.

[8]DARPA 1998 data set[EB/OL].[2005].http://www.ll.mit.edu/IST/ideval/data/1998/1998 data_index.html.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”