基于決策樹的安全策略沖突檢測

（中國船舶重工集團公司第七二二研究所 武漢 430205）

1 引言

網絡安全的重要性引起了人們的關注，由于不斷增加的網絡攻擊威脅，各類網絡中的重要元素逐漸變為網絡安全設備（如防火墻和IPSec網關）。在這些網絡管理中，系統行為的規范一般是由策略定義［1］，由策略決定安全設備在不同情況下執行的動作。目前廣泛應用的網絡管理方法是結合策略的方法［2］，但目前策略配置主要由人工進行配置，由于人工配置的原因會出現配置的策略之間的沖突。一些安全漏洞可能會在安全設備執行策略時出現，導致系統的正常運行受到影響。隨著網絡規模的增大，策略的數目也在不斷增加，使得策略沖突情況將更容易發生。因此，對策略進行沖突檢測來減少這些情況是至關重要的。由于分布式系統具有種類繁多的安全設備和結構復雜的網絡，難以實現人工方式對策略沖突進行檢測。目前網絡管理領域中關于策略的重要研究方向是找到一種方法可以準確快速檢測策略沖突。

2 相關工作

近年來在安全策略的沖突檢測方面，國內外做了許多研究，針對策略沖突檢測提出了不同的方法，文獻［3］提出了一種基于有限狀態傳感器策略的碰撞檢測方法，該方法將事件轉移函數和自適應子集添加到有限自動機（Finite State Transducer，FST）中以處理沖突。文獻［4］提出了一種有向無環圖模型（DAG），該模型通過將分布式系統中的元素抽象為DAG來檢測策略沖突。文獻［5］還使用圖論來檢測和解決從沖突。與以前的文獻不同，文獻［6］使用分類樹的授權算法將父節點的規則與子節點上的相應規則進行比較，從而檢測沖突。文獻［7～8］中通過對策略語義的研究，實現了策略沖突檢測。當現有策略與靜態職責分離策略共存時，文獻［9］所提出的沖突解決方法以滿足互斥要求為目標。這些方法在性能上均存在不足，在基于角色、有限自動機、有向圖等方法上，對于規則的順序比較具有較強依賴性。而本文的決策樹模型將對上訴問題進行解決，決策樹可以大量減少順序比較。

近年來國內外對決策樹進行了大量研究，2010年，普渡大學博士B.Vamanan針對大規模規則集研究提出基于分子集的決策樹算法EffiCuts［10］。2013年，北京大學W.Li博士在EffiCuts算法基礎上提出改進算法HybridCuts算法［11］，通過減少子集數目提升算法查找性能。對于決策樹切割技術單一問題，2014年中科院計算所G.Xie團隊提出智能切割算法 SmartSplit［12］。2018 年，北京大學 W.Li博士再次對決策樹算法進行改進，提出融合等長度和等密度切割的決策樹算法 CutSplit［13］。2019 年，W.Li博士再次進行優化，提出支持高性能更新的TabTree算法［14］?，F在已經有的大量關于決策樹的研究的出現證明了決策樹在現實中具有應用價值。

3 安全策略沖突基本概念

安全策略的匹配順序是從上到下，因此安全策略中的沖突可能是由不同規則之間的依賴性引起的。因此，沖突檢測的第一步是對不同規則之間的關系進行定義。

由于IPSec的自上而下的策略匹配，如果安全策略順序配置不正確，則可能永遠不會觸發某些規則，從而導致策略錯誤。策略沖突從定義上可以被分為以下幾類沖突。

1）策略屏蔽沖突

規則Rx屏蔽了規則Ry，當且僅當滿足以下兩個條件之一：

Rx[序號]＜ Ry[序號]，Rx=Ry，Rx[行為]≠ Ry[行為]

Rx[序號]＜Ry[序號]，Ry? Rx，Rx[行為]≠ Ry[行為]

2）策略冗余沖突

對規則Rx來說，規則Ry是冗余的，當且僅當滿足下面兩個條件之一：

Rx[序號]＜ Ry[序號]，Rx=Ry，Rx[行為]=Ry[行為]

Rx[序號]＜ Ry[序號]，Ry? Rx，Rx[行為]=Ry[行為]

反之，對規則Ry來說，規則Rx是冗余的，當且僅當：

Rx[序號]＜ Ry[序號]，Rx? Ry，Rx[行為]=Ry[行為]

當存在以下情況時，內部策略也將發生冗余沖突：

Rx[序號]＜ Ry[序號]，Rx∩ Ry≠ φ，Rx[行為]=Ry[行為]

3）策略相關沖突

規則Rx和Ry之間出現策略相關沖突，當且僅當滿足以下條件：

Rx[序號]＜Ry[序號]，Rx∩Ry≠φ，Rx[行為]≠Ry[行為]

4 訪問列表沖突決策樹模型

在數據分類領域中，決策樹是一項重要技術，通過學習訓練集構造決策樹，然后根據決策樹模型對目標數據類別進行預測［15］。在構造決策樹時，首要的步驟是預處理策略集對應的五元組數據，具體是將復合維度分解和確定維度空間。五元組中的源、目的地址，源、目的端口均為連續維度，在進行劃分時的維度范圍是最小值至最大值，而協議則是非連續維度，協議中的值為一個個的協議元素，在進行劃分時為元素集合的劃分。對于協議這種非連續維度中的元素可能存在元素A包含元素B的情況，這種情況下對應維度就為復合維度，在預處理時需要將復合維度進行分解，將例如元素B的這類元素分解為其本身與其父元素的組合。例如表1中的策略的元素有SCTP、TCP、UDP和IP這些協議。這些協議元素中例如SCTP就可以視為復合元素，將這種復合元素分解為所有復合元素的父元素的集合，即IP/SCTP。以此類推，表1中的協議這類復合型維度可以被分解為表2所示。

表1 規則示例

表2 復合維度分解

在預處理時，對于源IP地址、目的IP地址這類連續維度，將對應維度在規則中的最大值和最小值找到。由于協議這類非連續維度的范圍就是維度中所有可以取到的元素集合。因此，表1對應的維度范圍如表3所示。

表3 確定維度空間

在對策略集進行預處理后，我們可以開始構建決策樹。首先，我們可以根據確定的維度空間對策略集中的規則進行裁剪。首先確定決策樹的兩個參數：葉子節點中可以存放的最大規則數T和每個維度范圍可劃分為np個。當T小于當前節點內存放的規則數時，說明節點內存放規則數多于設定值，選擇對應的維度范圍進行均分，當節點內存放規則均不大于T時就認為該節點為葉子節點，當所有節點均劃為葉子節點時，決策樹的構造就完成了。

以表4中的規則為例，由于規則數目較少，假定T和np均為3，在構建決策樹時，先以源IP地址進行劃分，源IP地址的維度空間為202.168.80.0～202.168.80.255，根據np=3，將其均勻的切割為3個區間，若規則中源IP地址落在202.168.60.0～202.168.60.85的范圍內時將其劃分到第一個節點，規則中源IP地址落在 202.168.80.86～202.168.80.170的范圍內時將其劃分到第二個節點，規則中源IP地址落在202.168.80.171～202.168.80.255的范圍內時將其劃分到第三個節點，然后對劃分后的節點與T進行大小判斷，若節點內的規則數大于T則選擇下一個維度即目的地址進行切割，直到葉子節點內的規則數均不大于T。

圖1 構造決策樹

圖2是決策樹構建算法流程，先對策略集進行預處理，若存在復合維度，先將復合型維度進行分解，統計連續維度范圍，從源IP地址開始，將范圍均分為np個范圍，計算落在劃分的各個節點范圍中的策略數，判斷T是否小于節點內策略數，若T小于節點內策略數，擇下一個維度進行劃分，直到所有葉子節點內策略數均不大于T，在找到對應葉子節點后，順序查找比較存放在葉子節點內的策略，若葉子節點中存放的策略的五元組存在交集，則進一步判斷存在的沖突類型。根據上述策略的沖突分類判斷沖突類型，若為屏蔽沖突，根據希望執行動作決定將被屏蔽策略刪除或將屏蔽策略刪除，若為冗余沖突，可刪除冗余的策略，若為相關沖突，則將兩條策略交集部分根據希望執行動作進行分割，將交集部分劃分到希望執行的動作對應策略下，將另一條策略中的交集部分刪除。若新增策略與已有策略之間沒有交集則將其添加至相應的葉子節點內。

圖2 算法流程

基于決策樹的策略沖突檢測具體步驟如下。

1）將已有策略集構建為一個決策樹模型，決策樹構建完成后先檢測當前情況內的葉子節點內是否存在策略沖突，若存在，根據沖突類型的不同選擇不同解決方法，若不存在，則說明當前構建完成的決策樹中不含沖突策略，在之后新增策略比對時，只存在新增策略與已有策略之間的沖突。

2）將新增策略A從源IP地址這個維度進行比對劃分，根據新增策略A的源IP地址范圍判斷其落在哪個子節點分支上，若源IP地址同時落在兩個或兩個以上的源IP地址分支上，則將策略A根據源IP地址分支的范圍劃分為n個相應源IP地址范圍的策略。

3）將新增策略A繼續以下一個維度進行匹配，操作與步驟2）類似，直至將策略A與對應葉子節點匹配。

4）將新增策略A與相應的葉子節點內的策略進行順序比對，判斷策略A與已有策略之間是否存在交集，若無交集，則說明新增策略與已有策略之間不存在沖突，若存在交集，則判斷新增策略與已有策略之間的沖突類型。

這種方法下僅需檢測對應葉子節點內的規則就可以找到策略之間是否發生沖突，不需要對所有已有策略進行比對，分析是否產生沖突。

5 沖突檢測算法性能分析

目前提出的對策略的沖突進行檢測的方法一般是基于順序匹配，本文提出的決策樹方法對比順序匹配極大減少了策略查找數目。本文的方法是先構造決策樹，通過將策略在不同維度上進行切割，最終形成每個葉子節點內策略數均不大于T的決策樹，在進行策略沖突檢測時，先將策略在決策樹中分維度進行匹配，在最后與之相匹配的葉子節點內的規則集中進行順序查找匹配。對于n條規則，構造決策樹進行沖突檢測的方法的時間復雜度為O（mn），在決策樹的葉子節點內進行策略的查找匹配的時間復雜度為O（Tm）。在文獻［7］中的方法中需要對每兩條策略之間進行特征因子處理，進行了大量的順序查找比對，這種方法的時間復雜度為O（nm）。將兩種方法的測試數據進行對比，當策略數目較少的時候，本文方法與文獻［7］的方法相比并沒有出現明顯的優勢，但隨著策略數目的翻倍增加，本文方法的算法效率對比文獻［7］的方法優勢越發明顯，對同樣數目的策略，策略沖突檢測時間出現明顯減少。

圖3 相同運行環境下本文算法與文獻［7］方法運行時間對比

6 結語

本文結合了包分類中的匹配思想，先對策略進行預處理、構建決策樹后，在葉子節點中查找規則沖突情況。本文提出的方法中若新增策略為確定值而非范圍時，進行分維度查找匹配的過程與包分類的過程類似。因此對策略進行劃分，在葉子節點內進行查找的方法對包分類也有參考意義。對比之前基于順序查找的各種方法來說，本文提出的方法在查找上提高了性能。與文獻［7］的方法比較，當規則數目較大時，時間效率有很大提升，有明顯的優勢。本文由于測試數據的IP地址范圍有限，對于變化范圍更大的IP地址范圍需進一步研究調整決策樹的。但本文針對五元組模型提出的策略沖突檢測模型，對于其他策略模型是否具有適用性還需作進一步的研究。