基于改進決策樹算法的DNS流量異常動態檢測

沈廣東

(泉州信息工程學院，福建 泉州 362000)

決策樹算法實質上屬于一種貪心算法，通常由多叉樹或二叉樹來描述。在決策樹中，每一非葉子節點都可以形容某種劃分規則[1]，而葉子節點均用來描述類別。通常情況下，決策樹算法采用自頂向下方式，從根節點開始按照劃分規則生成完整的決策樹。在決策樹算法中，通常包含兩個部分，分別為決策樹生成與修剪，而決策樹修剪通常是指對已構建好的決策樹進行優化，以降低決策樹過度擬合問題。

域名系統(Donmain Name System，DNS)屬于互聯網核心部分，通常用于提供互聯網域名服務，在網絡中其能夠實現IP地址與域名之間的映射[2]，對于網絡來說，DNS流量的安全性十分關鍵，若DNS遭受到攻擊，則會導致網站出現虛假副本，使網絡受到大量威脅[3]，因此，及時對DNS數據進行分析，獲取其中的異常流量，能夠有效維護網絡安全。

有較多學者對DNS的異常檢測進行了研究，秦輝東等[4]研究基于多特征的DNS異常檢測方法，但該方法在異常密度較高的情況下，檢測結果不夠精準；展鵬等[5]研究基于特征符號表示的網絡異常流量檢測方法，但該方法所獲取的流量異常特征不夠明顯。為此，本文研究基于改進決策樹算法的網絡DNS流量異常動態檢測方法，通過對決策樹算法的改進，實現動態監測DNS異常流量。

1 網絡DNS流量異常動態檢測

1.1 網絡DNS流量異常現象分析

網絡中異常DNS流量通常是指惡意網站URL，若用戶不經意間連接到這些URL時，會導致隱私數據泄露，且會在后臺下載惡意代碼，使得惡意攻擊者訪問用戶隱私內容。本文針對網絡DNS流量異常現象進行研究，相較于傳統惡意代碼，DNS流量異常現象出現時，攻擊者通常會訪問用戶服務器[6-7]，以獲取控制命令，從而使惡意攻擊者執行惡意命令，因此，DNS異常流量現象屬于受害者主機與攻擊者之間的信息交互，即攻擊者需要向受害者主機發送命令，當主機接收后才能夠完成相應攻擊[8]，而攻擊命令通常在命令控制信道中出現，因此，檢測DNS異常流量可以及時發現域名被查詢的情況，可以幫助用戶及時切斷攻擊者的服務器連接，保障網絡命令控制信道安全。

1.2 網絡DNS流量異常特征選擇

特征選擇與特征提取不同，特征提取是獲取網絡DNS流量異常特征，而特征選擇則是對特征的篩選，實質上是選出具有代表異常的小范圍流量[9-10]。

傳統的網絡DNS流量特征選擇算法有蟻群算法、遺傳算法等，但這些算法所選出的特征并不完全，因此，本文利用新型的鄰域粗糙集算法選擇網絡DNS流量異常特征。

在鄰域粗糙集算法中具有以下定義：

(1)假設Y為隨機獲取的樣本集，此時設條件、決策屬性集分別為K、B，并通過D描述K的鄰域，則設計鄰域決策系統為。

(2)在中，樣本集Y被集合B處理為n個等價類，并表示為a,b,…,n。K的約簡屬性為?W?K，則可通過公式(1)定義B的鄰域粗糙集下近似。

Z={Z·a,Z·b,L,Z·n}

(1)

公式(1)中，L表示鄰域范圍，Z表示其鄰域下近似值，同時可通過公式(2)定義B的鄰域粗糙集上近似。

Q={Q·a,Q·b,L,Q·n}

(2)

公式(2)中，Q表示其鄰域上近似值。由公式(1)與公式(2)可以獲知，粗糙集理論的邊界域W，如公式(3)所示。

(3)

(3)在鄰域決策系統中，定義如式(4)所示。

(4)

公式(4)中，B依賴K的程度由J表示。

(4)在鄰域決策系統中，?i∈W?D，假設J>Q，則表示屬性i的存在具有必要性，若無法成立，則屬性i的存在不具有必要性。

(5)在鄰域決策系統中，若W?D可以實現：J=Q、?i∈W，J

(6)在鄰域決策系統中，假設W?D，i∈D-W可以滿足，則可通過公式(5)定義i在W中的重要度V。

(5)

在上述過程中，本文通過鄰域粗糙集算法理論，設計一種鄰域決策系統。并通過如下步驟完成網絡DNS流量異常特征選擇：

向決策系統中輸入條件特征集S，計算S的鄰域依賴度，同時從中隨機挑選特征s，計算s與其鄰域的距離函數，若S中全部特征均計算完畢，則刪掉具有改變最小距離函數的特征，刪除該特征后輸出特征選擇結果。

1.3 基于C4.5決策樹算法的網絡DNS流量異常動態檢測

決策樹算法能夠從無規則實例集中分析出分類規則。由于C4.5算法具有較高的計算效率，因此，本文選擇C4.5算法進行網絡DNS流量異常動態檢測。

在決策樹算法中，最主要的部分就是對內部節點分支的選擇，不同的劃分情況得到的決策樹效果也存在較大區別，C4.5算法主要采用信息熵理論，將信息增益最高屬性設為分類屬性。在上述網絡DNS流量異常特征選擇步驟獲取的特征集S中，假設S的理想劃分為S={s1,s2,…,sn}，則可通過公式(6)表示信息增益率。

R(S,β)=HG(S,β)/HS(S,β)

(6)

公式(6)中，β表示引入測試條件；當S被β劃分后得到的信息增益由HG(S,β)表示；β產生的分割信息熵由HS(S,β)表示。

C4.5算法通過信息增益率獲取節點的分枝，但在確定分枝的過程中，由于劃分產生的分割信息較小，會導致增益結果不夠精準。為此，采用最短距離劃分方法設計決策樹，假設兩個劃分間的距離為Mantaras范式距離，則將與理想劃分距離最近的屬性作為測試條件。

(7)

公式(7)中，S對S′的條件熵為H(S′|S)；S′對S的條件熵為H(S|S′)；同時，H(S,S′)為S對S′的聯合熵。

由于訓練時容易出現過度擬合現象，因此，還需要對C4.5算法進行改進，使檢測過程更加精準。

1.4 基于改進決策樹算法的網絡DNS流量異常動態檢測

C4.5算法屬于在ID3算法的基礎上進行優化。但由于C4.5算法在屬性X只存在一個值時，分裂信息值會接近于0，導致分裂信息的倒數接近無窮大，會使分類結果存在異常。

本文對C4.5算法進行改進，構成BL4DT算法，向C4.5算法中添加平衡變量，之后再對信息增益率進行計算。

對于網絡DNS流量異常動態檢測問題，在上述網絡DNS流量異常特征選擇步驟獲取的特征集S中，目標函數為Ci(i=1,2,3,…,m)，其中包含m個不同的特征屬性，且目標函數服從分布P=(p1,p2,p3,…,pm)，此時，可通過公式(8)計算S的熵。

(8)

公式(8)中，熵是指S的不確定性，由此可以得到驗證，如式(9)所示。

0≤E(S)≤log2m

(9)

設由網絡DNS流量異常特征構成的樣本集合為S={A1,A2,…,Am}，其中具備m個屬性特征，則訓練樣本集為|S|，全部訓練樣本均被調整為n個各自獨立的類Ci(i=1,2,3,…,n)，其中每個類相應的樣本數表示為|Ci|，此時，針對S內的屬性Ai進行分析，其對應的信息增益G(S,Ai)如公式(10)所示。

G(S,Ai)=E(S)-E(S,Ai)

(10)

公式(10)中，Ai的值空間表示為values(Ai)，當Ai的值為v時其子樣本集為Sv，且在此時Sv={s∈S|A(s)=v}。

對于C4.5算法在計算時存在的分裂信息度量sp，主要通過公式(11)實現計算。

(11)

根據上述分析，此時可以獲取BL4DT算法對信息增益率的計算過程，如公式(12)所示。

(12)

當完成改進信息增益率計算后，為使計算結果更加精準，引入平衡變量，若A的信息增益率最大時，向其中引入平衡變量，并通過公式(13)表示平衡因子α計算方式。

(13)

公式(13)中，數據集N被調整為m個各種類型的特征屬性Ci(i=1,2,3,…,m)；在屬性A中，共具備n個不同值，其中A獲取的第i類記錄里在Cj中的樣本數由xij描述，當引入平衡變量后，包含m個值的屬性A信息增益可通過公式(14)計算。

(14)

假設S被屬性A分解為n個部分，即{S1,S2,…,Sn}，則屬性A取值為Ai時，在S中包含正例Pi個、反例ni個，通過I(pi,ni)描述的Si信息，此時，可通過公式(15)描述屬性A的信息熵。

(15)

其中，I(pi,ni)通過式(16)計算：

(16)

按照極限公式理論，若x→0，則ln(1+x)≈x，按照這一標準，對上述公式進行簡化，簡化結果如公式(17)所示。

(17)

信息增益率可以作為網絡DNS正常流量與異常流量的分割屬性，其具有較強的判別能力，可以使動態檢測效果更佳完美。通過以下步驟表示改進后的決策樹(BL4DL)算法的網絡DNS流量異常動態檢測過程：

輸入：屬性集合A以及樣本集S。

(1)構建節點T。

(2)假設訓練樣本為空，則無法完成建樹，返回至步驟(1)再次創建。

(3)假設屬性集合A為空，則返回步驟(1)將節點T設為單節樹，并向節點T賦予樣本集S內出現最密切的類。

(4)若全部訓練樣本都存在于相同類(Class)中，則返回步驟(1)，將T設為葉節點，并向T賦予S中的類。

(5)從A中挑選信息增益率最大的屬性Ai。

(6)將節點T標記為屬性Ai。

(7)針對每個Ai中的實際值c，通過節點T生長出Ai=c分支。

(8)將S中Ai=c的訓練樣本集合設為S′。

(9)若S′為空，則產生葉子節點，并向S′賦予訓練樣本中含量最大的類，若S′不為空，則引入BL4DT(S′,{A-Ai})作為返回節點。

輸出：一顆判定樹，即網絡DNS流量異常動態檢測的結果。

2 實驗分析

從企業網絡中搜集DNS流量，該網絡通過隧道協議傳輸，因此，DNS流量更加清晰，適合標記異常狀態，通過人工方式標記DNS流量異常，并通過本文方法對此進行檢測，驗證方法有效性。

分析應用本文方法后，能否對不同網絡DNS流量特征異常現象實現選擇，分析結果如表1所示。

表1 網絡DNS流量特征異常現象特征選擇

根據表1可知，應用本文方法，能夠有效實現多種網絡DNS流量特征異常時的選擇，可以為DNS流量異常動態監測提供可靠幫助。

分析應用本文方法檢測到網絡中某日DNS流量的平均異常比，并與實際流量異常情況進行對比，對比結果如圖1所示。

圖1 網絡DNS流量平均異常比

根據圖1可知，在不同時間下，網絡DNS流量的平均異常比均有所不同，在4h與8h之間平均異常比相對較高，而20h～24h之間平局異常比略低，通過本文方法的檢測結果可以看出，檢測到的平均異常比與實際異常比十分接近，說明本文方法能夠精確實現網絡DNS流量異常智能檢測。

不同的網絡DNS流量異常密度會使異常動態檢測的檢測率發生變化，本文選取三種異常密度進行分析，分析不同異常密度下，本文方法的ROC曲線變化，分析結果如圖2所示。

圖2 本文方法ROC曲線變化

根據圖2ROC曲線可以看出，當虛警率不斷增加，本文方法在不同異常密度下的檢測率也隨之上升，其中，異常密度越大，檢測率相對較低，但是在應用本文方法下，最大異常密度30%的最低檢測率也保持在55%以上，說明應用本文方法，可在較大異常密度下實現流量異常檢測。

在網絡未出現時延時，流量保持500KB左右，當網絡出現不同程度的時延，網絡DNS流量則出現異常，隨著時延的變化流量處于200KB～1000KB之間波動，分析應用本文方法前后，對DNS流量狀態的檢測情況，檢測結果如圖3所示。

圖3 網絡DNS流量檢測情況

根據圖3可知，應用本文方法前，當網絡出現時延時，流量已處于大范圍波動，但對流量異常情況并未明細檢測，檢測得到的流量變化僅處于400～600KB之間，而應用本文方法后，流量發生異常變化時，本文方法能夠清晰檢測到流量的狀態波動。由此可知，本文方法能夠較好地實現網絡DNS流量異常檢測。

3 結論

本文研究基于改進決策樹算法的網絡DNS流量異常動態檢測方法，選擇網絡DNS流量異常特征，并通過決策樹算法對該流量異常特征進行檢測，由于決策樹算法存在一定缺陷，因此，對該算法進行改進，使網絡DNS流量異常動態檢測更加完善。在此基礎上，可將該方法應用至較多領域，同時，未來也可繼續對該方法進行優化，使網絡DNS流量異常情況能夠得到處理。