應用Q學習決策的最優攻擊路徑生成方法

李 騰，曹世杰，尹思薇，魏大衛，馬鑫迪，馬建峰

(西安電子科技大學 網絡與信息安全學院，陜西 西安 710071)

網絡攻擊圖和最佳攻擊路徑規劃的分析一直以來都是國內外信息安全領域討論和研究的熱點話題之一。在對系統網絡進行滲透測試時，滲透測試人員在了解對方網絡拓撲以及主機之間連通性的前提下，都希望能夠找到一條代價最小、高效精準的攻擊路徑，以達到滲透的預期目標。本文所要解決的問題就是如何在一個存在IDS報警的網絡主機環境里通過機器學習的方式高效精準地尋找到最優的攻擊路徑。防守者如果能夠提前對攻擊路徑進行構造，站在攻擊者的角度思考問題時，則可以幫助系統防御者更好地防護系統，最終避免攻擊和威脅的發生。但由于系統網絡的復雜性和諸多不確定因素，如：攻擊者的攻擊行為選擇不確定性，環境反饋因素不確定性，主機系統漏洞利用難度不確定性，等，這些不利的條件都對生成攻擊圖或攻擊路徑造成了很大的困難。同時攻擊者模型的建立與完善的好壞也將直接影響最優攻擊路徑的價值大小。所以，綜合上述的種種因素，合理、科學、高效地生成攻擊圖和攻擊路徑具有不小的挑戰與困難。

攻擊圖是目前十分流行的用來分析網絡脆弱性關聯度的技術，最早是由文獻[1]提出的基于攻擊圖的網絡脆弱性分析方法。針對攻擊圖構造問題，現有的生成攻擊圖的方式也有很多，主要可分為基于網絡屬性(即網絡安全狀態空間)和基于網絡脆弱性這兩類，同時大多數都是依靠遍歷和搜索圖結構來獲取攻擊圖，但存在一定的問題，如狀態爆炸、攻擊圖生成速率較慢等。文獻[2]所構建的網絡動態威脅分析屬性攻擊圖(DT-AAG)模型，雖然解決了傳遞環路的問題，但其算法冗余，生成圖效率低下。文獻[3]通過將節點表達為網絡安全狀態、有向邊表達攻擊規則的方法，但是存在節點爆炸的問題，等等。文獻[4]提出的方法不同于以往傳統的生成攻擊圖的方式，而是將Q-learning這種動態規劃的算法思想運用到網絡攻擊圖的生成方法中去；然而該方法不適合計算規模較大的網絡拓撲環境，且后續生成最優攻擊路徑的效率也較低。文獻[5]提出將Q-learning機制直接運用到規劃最優攻擊路徑的問題上，從而不依靠生成攻擊圖便可直接獲取最優攻擊路徑，同時模擬攻擊者不需要訓練數據、在線學習即可，并且還解決了算法空間復雜度高、生產最佳路徑冗余的問題，但是沒有考慮主機集群中存在IDS等報警防御機制等情況，且部分算法和模型定義略顯復雜，缺乏針對性，占用了較多的內存資源空間。

為解決上述問題，文中提出了一種基于Q-learning算法的最優攻擊路徑生成方法。該方法主要以Q-learning 算法決策思想為基礎，并改善、簡化攻擊者決策算法模型，在進行分區可達性的篩檢之后，開始模擬攻擊者的攻擊回合，其間設置環境障礙與影響因素，最終得到最優攻擊路徑。文中實驗模擬了一個中小型公司的內網環境，經過指定的回合數訓練學習后，模擬攻擊者能夠精確、高效地尋找到最優攻擊路徑，且實驗結果表明，目標網絡結構越復雜，通過提前分區可達性刪除冗余主機的方法越能突出優勢。

論文工作的主要貢獻在于：

(1) 通過分區和區域可達性分析，降低需要檢測的連接數量，提高以Q-learning 算法為核心的模擬攻擊者尋找攻擊路徑的整體學習效率。

(2) 構建復雜有干擾因素的實驗環境場景，增強Q-learning算法模型在多變的網絡環境中的適應性和決策能力，豐富了實驗場景的同時，驗證了整體方案的可靠性。

(3) 簡化了Q-learning算法模型，使得整個尋路過程更加具有針對性，同時減少占用較多的內存資源空間，使算法變得十分高效。

(4) 采用多回合制訓練模式，利用多線程并行計算輔助模擬攻擊者學習和訓練，大大縮減訓練時間，并通過遍歷搜索Q表的方式得到最優攻擊路徑，降低算法的復雜度。

1 相關工作

傳統的大多數生成分析網絡脆弱性的方式都是通過構建攻擊圖來實現的；采用優先搜索的算法遍歷攻擊圖以獲取最優攻擊路徑，根據攻擊圖的構建方式可分為狀態攻擊圖和屬性攻擊圖，這也是最常用的兩種構建方式。文獻[6]對攻擊圖的基本構成做出了詳細的介紹，并且分析了各種攻擊圖類型的優缺點。但是基于以上兩種攻擊圖所存在的問題是：攻擊路徑生成速度較慢，并且應對狀態爆炸問題而采用的限定路徑的方法導致了攻擊路徑的缺失。LIU等建立的網絡攻擊節點路徑檢測模型具有較高的準確性，有效地提高了網絡安全分析的效率，但是存在狀態爆炸的問題。為了解決攻擊圖存在的上述問題，降低這些問題對獲取最優攻擊路徑的影響，研究人員將隱馬爾可夫模型和攻擊圖相結合，并采用蟻群優化算法以概率式方法計算最優攻擊路徑，同時文獻[7]在此基礎再次進行了深度研究。但將隱馬爾可夫模型和攻擊圖相結合并采用蟻群優化計算的方法在面對大規模計算機集群時，由于其開銷問題，無法快速計算出最優攻擊路徑。同時，文獻[8]根據路徑的攻擊成本，通過蟻群優化算法來進行最優攻擊路徑的預測，但不足之處在于追求較低的攻擊代價的同時，忽略了攻擊收益對于預測攻擊路徑的影響。基于貝葉斯網絡的分析模型具有強大的不確定性問題處理能力，同時也能夠有效地進行多源信息表達與融合。文獻[9]就貝葉斯網絡，提出了將CVSS評分系統與其相結合的分析模型，各個節點上的置信度被轉化為成本和收益的計算，的確對貝葉斯網絡的分析模型進行了優化；但是不足之處在于未考慮單位時間內的攻擊收益和成本的差值。文獻[10]在消除攻擊圖上環路的基礎上，將模型轉換為貝葉斯網絡攻擊模型(BNAG)，引入節點攻擊難度和節點狀態變遷度量指標計算節點可達概率。之后，文獻[11]又定義了網絡攻擊增益圖(NAPG)模型，根據路徑概率、增益速率，利用最優增益路徑預測算法實現對最優增益路徑的預測。除此之外，文獻[12]針對當前攻擊圖模型中很少考慮攻擊事件對所有屬性節點置信度的動態影響，提出一種基于貝葉斯攻擊圖的動態風險評估模型，該模型運用貝葉斯信念網絡建立用于描述攻擊行為中多步原子攻擊間因果關系的概率攻擊圖。但基于貝葉斯網絡的攻擊圖并沒有解決最優彌補集的問題。文獻[13]提出了基于轉換的攻擊圖分析方法研究，論證了最優彌補集問題與加權碰集問題之間的等價性，并提供了相應的形式化轉換方法。除攻擊圖外，攻擊行為態勢和攻擊路徑的預測也是需要解決的難題。文獻[14]為準確、全面地預測攻擊行為并量化攻擊威脅，提出一種基于攻擊預測的安全態勢量化方法；該方法也通過設計基于動態貝葉斯攻擊圖的攻擊預測算法，進而推斷后續攻擊行為。文獻[15]通過對無線網絡中異常信息的入侵意圖進行預測，可以有效地保證網絡的安全性和穩定性，但是該模型分析的效率不高。胡昌振團隊針對以上的問題提出了將Q-learning的算法思想應用到尋找最優攻擊路徑上去，這種規劃方式主要解決了以下的問題：① 提出的網絡模型不需要進行訓練，因此不需要收集訓練數據；② 可在線學習，實時確定不同時刻不同網絡狀態對應的最佳攻擊路徑；③ 學習率使用了退火模型，所以收斂的更加精確；④ 由于不需要生成攻擊圖，所以可以適用于大規模計算機集群。引入Q-learning算法可以解決大部分基于攻擊圖生成攻擊路徑方式所存在的問題，但是同樣也帶來了新的問題，就文獻[5]提出的方案方法來看，其缺點如下：① 算法空間復雜度較高，因此占用內存空間較多；② 存在路徑冗余的問題。胡昌振等就之前提出的Q-learning算法的方案提出了進一步的改進措施，其具體的改進措施和優點如下：① 將動作和狀態融合，降低算法的空間復雜度；② 加快最優攻擊路徑的生成速度；③ 使得生產的攻擊路徑更加簡潔有效。但是在胡昌振等改進后的該方法中，并沒有在模擬攻擊者開始學習尋路之前簡化網絡拓撲圖，使得整個訓練過程會增加冗余的環境分支，從而降低模擬攻擊者尋路的整體效率。實驗環境中也未加入防御措施和防御手段去阻礙、干擾攻擊者的訓練學習過程，同時立即回報函數定義復雜，使得整個尋路過程缺乏針對性。

2 提出方法

2.1 方法概述

為了解決攻擊圖的生成結果冗余、生成效率低下以及攻擊路徑的生成存在需要人工修剪的問題，提出了一種簡化網絡拓撲、強化具體攻擊模型的方法。方法圖如圖1所示。

該方法通過路由表和防火墻策略規則，計算分區子網間可達性，對目標網絡結構進行化簡，同時刪除冗余的網絡拓撲結構分支，并將修改完善后的Q-learning的核心算法決策思想加入到模擬攻擊者的決策行為依賴函數中，以回合制的方式反復地進行學習和訓練，不斷更新自己的行為決策；其間設置監控、障礙干擾攻擊者的決策過程，最終獲取到最優網絡攻擊路徑序列的方法。在整個尋路過程中，通過利用分區可達性使整體的訓練學習效率極大的提高，而且具體化后的Q-learing決策思想模型，能夠通過不斷的適應環境以此來更新行為-價值表，提高模擬攻擊者行為決策的科學性與準確性，以獲得最大的回報函數值，并最終達到收斂。同時也能夠針對不同的訓練環境，作出合理的選擇與判斷，生成的攻擊路徑序列也不存在需要人工修剪的問題。

2.2 系統描述

2.2.1 網絡拓撲化簡

首先獲取攻擊環境中的網絡主機分布結構，繪制網絡拓撲圖；然后通過圖2所示子網可達性判斷的方法，根據網絡環境中的各路由器的路由表與環境子網表計算出子網間可達性；接著對子網間可達性表進行進一步的細化切分，只篩選出可達的子網，并通過圖3所示防火墻規則判斷的方法，結合主機網絡信息表和防火墻規則表計算出主機可達性，最后得到主機可達性表。主機可達性表包括兩種情況，第1種情況是主機之間屬于同一子網，第2種情況是主機之間屬于不同子網且子網間存在可達關系，若不屬于同一個子網且子網間不可達，則不用計算主機之間的連通性。在整個過程中，采用并行的機制進行計算，以提高計算的效率。通過分析分區可達性，可大大減少對攻擊者需要訓練和學習環境中的冗余主機節點，提高攻擊者的整體學習效率。

圖2 子網可達性判斷偽代碼

2.2.2 攻擊者模型建立

首先通過漏洞掃描器和人工確認檢測，獲取該網絡環境下各主機中存在的漏洞，建立主機漏洞狀態表Host_vulns(HostID，vulnID，vulnScore)，其中HostID指主機名稱編號，vulnID指主機漏洞編號，vulnScore指漏洞評級。

然后建立Q-learning學習模型Q，即模擬攻擊者的決策行為選擇模型。公式如下：

q(St，a)=(1-α)*q(St，a)+α*(Rt+1+γ*maxaq(a，St+1)) ，

(1)

其中，①α表示學習效率，決定現實的Q值與估計的Q值之間的誤差有多少會被模擬攻擊者所學習到，從而更新Q表中的值；在這個模型中，α取常數值0.01；不同于文獻[5]中所設定那樣，假設該攻擊者具有穩定的學習能力，不會受環境的因素等其他因素的影響，在具體化攻擊者模型的同時簡化了公式，降低算法的復雜度；②γ表示對未來獎勵的衰減值；若γ取值為(0，0.5)，則表示該攻擊者在一定的評價指標下只考慮眼前的利益價值，而容易忽略長遠的價值，即缺乏遠見意識；若γ取值為(0.5，1.0)遞增上漲，則表示該攻擊者逐漸有遠見，不滿足于眼前的利益，而考慮長久化的利益，從而獲取最優攻擊路徑的效果會更佳；根據對攻擊者的模擬情況來看，對γ的取值為常數0.9，表示這是一個有經驗且有遠見的攻擊模擬攻擊者；③Rt+1表示模擬攻擊者到達下一狀態的立即獎勵；④ maxaq(a，st+1)表示模擬攻擊者想象自己在下一狀態時采取在該狀態下的行為集合所得到的Q值中的最大值。

同時簡化立即回報函數R(S，S′)，淡化中間過程主機在整個攻擊過程中的價值分量，統一設置立即回報值為0：

R(S，S′)=0(S′≠S_IDS&&S′≠S_TARGET) 。

(2)

提高IDS報警主機和最終目的主機在此過程中的絕對影響，分別設置立即回報值為

R(S，S_TARGET)=TARGET_VALUE，R(S，S_IDS)=-(TARGET_VALUE+1) ，

(3)

其中，TARGET_VALUE為除目標主機之外的其余主機的漏洞評級的均值加上目標主機的漏洞評級。

2.2.3 最優攻擊路徑構造

通過上述所構造的基于Q-learning的決策算法，將該算法加入到模擬攻擊者的決策行為選擇函數中，同時設置模擬攻擊者的初始主機位置并確定目標主機，然后開始獲取最優攻擊路徑。在整個決策模型中，設置ε-greedy的值為0.9，ε-greedy為用在決策上的一種策略，具體表示模擬攻擊者在90%的情況下會根據Q表給模擬攻擊者的狀態價值反饋來選擇自身的行為；而在10%的情況下，模擬攻擊者會隨機選取自身的行為，不依據Q表進行決策。獲取最優攻擊路徑的過程如下：首先獲取網絡結構，接著根據圖4所示主機可達性計算的方法獲取主機可達性表，然后通過漏掃和人工確認獲取主機漏洞狀態表，漏洞作為已知條件，通過二次確認部署成功，并同時初始化Q表。接下來的尋路訓練采用回合制的方式進行，初始化回合數為n，在每次回合中，利用圖5所示獲取最優攻擊序列的方法模擬攻擊者進行尋路學習并根據Q-learning算法模型同步更新Q表。但在利用圖5方法尋路的整個過程中，會發生兩種情況：一是成功獲取到目標主機權限，二是被配置有IDS異常行為檢測報警系統的主機檢測到，并被永久封禁IP。兩種情況都代表著一回合的結束，但在后者情況中模擬攻擊者需要更換IP代理再次進行尋路學習訓練，直到回合數達到設定要求。在第n+1次尋路過程里，重新設置Q-learning算法模型中的ε-greedy值為1，使模擬攻擊者在該回合中完全按照之前尋路訓練得到的Q表進行決策判斷，以獲取最終的最優攻擊路徑序列。

圖4 主機可達性計算偽代碼

3 實驗與分析

3.1 實驗設置

本次實驗場景選擇為模擬一家公司的內網環境，公司內網中存在內網服務器區、技術部vlan、財政部vlan、市場部vlan、內部文件信息區。攻擊者初始主機位置在該公司技術部的一名員工主機上，目標主機為內部文件信息區的某一存儲大量信息文件的主機。通過實驗網絡環境中的各路由器的路由表與環境子網表計算出子網間可達性，接著對子網間可達性表進行進一步的細化切分，只篩選出可達的子網，并通過主機網絡信息表和防火墻規則表計算出主機可達性，從而獲取主機可達性表，并刪除了冗余主機節點。

3.2 獲取攻擊路徑

得到所生成的主機可達性表后，開始100次回合數的尋路訓練，在第101次尋路過程中，將ε-greedy值設置為1，表示模擬攻擊者完全依賴Q表進行行為決策的選擇，通過前面回合過程中的訓練學習，Q表中的值已達到收斂，即通過Q表進行決策可有效地反映模擬攻擊者的學習效果與決策結果。模擬攻擊者最終獲取到最優攻擊路徑序列為：Attack_ sequence=[H1，H2，H9，H8，H7，Ht]，即H1H2H8H7Ht這條攻擊路徑，如圖6所示。經過檢測，所得路徑確為本實驗環境中的最優攻擊路徑。同時，改變實驗環境主機拓撲結構，主機結構變化為圖7的連通性結構，再次進行實驗分析。根據同樣的方法得到的最優攻擊序列為：Attack_ sequence=[H1，H5，H6，H9，H12，H15，HT]，如圖5所示，經過檢測，所得路徑也確為該環境下的最優攻擊路徑。

圖6 初始環境下最優攻擊路徑

3.3 性能對比

在本節中，通過控制變量的方法，測試在不同的回合數設定值的條件下，模擬攻擊者每回合的時耗情況，即平均回合時耗(總時耗/回合數)。同時，將本文方法與文獻[5]的方法進行對比，在相同的網絡環境下，測試不同網絡主機數量對總時耗的影響。圖8和圖9為實驗數據結果。

圖8結果表明，隨著回合數的增加，模擬攻擊者的每回合時耗不斷下降，且下降比例隨著回合數的增加比例同步上升。在文中所建立的Q-learning決策模型中，Q表扮演了很重要的角色，通過Q表的不斷迭代更新，Q表在模擬攻擊者的行為決策選擇中產生的積極影響也越來越大，表明模擬攻擊者有更大的可能性去選擇更加適合的下一步行為。

圖8 攻擊者每回合的時耗情況

圖9結果表明，隨著環境主機數量的不斷增加，在主機數量不太大，網絡環境復雜度有限的情況下，兩種方法的總時耗相差不大。但隨著主機數量的大幅度增加，文中方法與文獻[5]所提出Q學習改進方法的差異逐漸拉大，且文中方法的總時耗增加幅度遠小于與胡昌振等所提出Q學習改進方法中的總時耗的增加幅度。該結果是因為文中方法在進行模擬訓練之前，先對目標網絡環境的網絡拓撲結構進行了分區域可達性判斷，刪除了大量冗余節點，在環境主機數量逐漸增大的過程中，該步驟便對整個尋路過程產生了極大的積極影響。該實驗結果進一步證實了在復雜度高的網絡環境中，通過分區和區域可達性分析來化簡網絡拓撲結果，刪除冗余主機節點，有利于降低檢測數量，提高尋路過程的效率。

最后，從準確度的角度比較了文中方案與胡昌振團隊方法的差異。圖10實驗結果表明，在尋路試驗次數不太多的情況下，文中方法的準確度不及他文方法；但隨著試驗次數的不斷增加，文中所建立的模擬攻擊者模型對目標環境的適應能力也逐漸增強；同時在本文的Q-learning決策算法模型中，將部分參數常數化，使得模擬攻擊者的模型變得十分具體，這在面對一個陌生的網絡環境是不太友好的，但隨著熟悉程度的增加，輔助模擬攻擊者進行決策行為選擇的Q表總體趨勢逐漸達到收斂，模擬攻擊者對該網絡環境的決策能力與適應能力也并行提高。所以在實驗次數達到一定的程度下，文中方法與胡昌振團隊的準確度大致相同，并在某些時間段中，文中方法的準確度高于胡昌振團隊的方法的準確度。

文中方法的P-R曲線圖如圖11所示，P-R曲線圖的平衡點BEP在(0.56，0.58)區間，該值表明文中方法的機器學習具有良好的性能與可靠性。

圖10 準確度差異比較情況

4 結束語

將Q-learning算法思想運用到尋找最優攻擊路徑的方法中去，同時對攻擊者決策模型、環境等具體措施做出了針對性的改進。并且，方法中加入了分區域分析主機可達性、刪除冗余主機節點的策略。經過實驗之后，得到了準確的最優攻擊序列。同時，所采用的算法模型顯著地降低了算法的復雜度，減少了所占內存空間，并在復雜網絡環境下具有突出的優勢。在后續工作中，首先需要進一步完善模型，減少常數化參數的設定，增強模型的擴展性。其次，改進獲取最優攻擊路徑的方式，使獲取過程更加的科學、準確，減少或避免出現最優攻擊路徑生成存在冗余節點、攻擊路徑生成不全等其他問題。