安全數據采集代理頑健部署策略研究

陳黎麗，王震，郭云川，華佳烽，姚宇超，李鳳華,4

（1. 西安電子科技大學綜合業務網絡國家重點實驗室，陜西 西安 710071；2. 中國科學院信息工程研究所第五研究室，北京 100093；3. 杭州電子科技大學網絡空間安全學院，浙江 杭州 310018；4. 中國科學院大學網絡空間安全學院，北京 100049）

1 引言

近年來，“網絡黑產”事件頻繁發生，攻擊者以“趨利”的思想策略地發動針對性的攻擊。例如，2018年12月，攻擊者通過加密電腦上的doc、jpg等常用文件的勒索病毒，利用微信支付二維碼勒索贖金，但支付寶用戶并未受到影響。目前，大部分的Internet服務提供商與大型企業網絡部署了網絡監測系統[1-3]，系統管理員通過網絡監測器（如流量分析程序、網絡入侵防御系統和防火墻等）對網絡性能數據進行實時收集，從而監測網絡的性能和安全狀況。雖然現有的網絡監測系統可以收集到一些安全數據（如網絡流量、CPU占用率等），但是針對上述“策略式攻擊”相關的安全數據缺少精準有效的監測策略。同時，由于受到資源成本的限制，只能部署有限數量的采集代理進行安全數據的監測采集。因此，在敵對環境中，如何優化部署采集代理獲取更好的監測效果成為一個極為重要的課題。

在敵對環境中，優化部署采集代理問題面臨著以下幾個挑戰。首先，采集代理針對不同類型設備采集的內容存在差異，例如，載有防火墻的設備可采集到UFW、Snort等相關日志信息，載有數據庫服務器的設備可采集到MySQL相關日志信息。上述日志信息存在數據異構性，為數據解析威脅事件帶來困難。因此，需要對異構性的安全數據進行統一度量。其次，上述的安全數據與威脅之間存在關聯關系，不同的異構數據組合能監測到不同的威脅。因此，為了更精準地監測“策略式攻擊”，需要考慮如何部署有限數量的采集代理，使采集到的異構數據組合獲得盡可能好的監測效果。最后，采集代理一旦部署，無法在短時間內移除，攻擊者通過漏洞掃描、網絡滲透、社會工程學等手段獲取網絡系統的信息（如漏洞信息、防火墻的位置等），并且策略地選擇對其“最有利”（“最有利”指的是使網絡攻擊影響最大）的方式實施攻擊。因此，需要考慮如何優化部署采集代理，在應對敵對情況時監測效果具有頑健性。

針對監測點部署問題，現已有不少學者開展了相關研究。在網絡測量領域中，網絡測量部署模型主要以優化為主體思想，并在此基礎上提出了一系列的啟發式近似算法[4-7]，為本文的研究奠定了基礎。網絡測量系統主要測量鏈路流量或端到端帶寬、時延、分組丟失率等性能參數[8]。然而，本文研究的采集代理部署在不同類型的設備上，安全數據類型不同，包括網絡流量數據、網絡日志數據和設備狀態數據，這些數據具有很強的異構性。在環境監測領域中，現有工作主要解決如何放置有限數量的傳感器來檢測污染物的問題[9-11]。其中，文獻[10]對敵對情況下如何部署采集器進行了研究，將對抗設置為對手在知道傳感器位置的情況下選擇在哪里進行污染，該設置與本文敵對情景設置相近。然而，環境監測中的采集項主要包括污染物類型、污染物質量和污染時間等相關參數[11]。而本文主要從網絡威脅層面考慮，例如，威脅事件發生的概率、威脅事件對目標系統的影響等。最后，在網絡安全監測領域中，已有不少采集代理的部署方法。例如，基于訪問控制策略的部署方法[2]和基于線性規劃的部署方法[12-14]。其中，文獻[14]對異構性強的日志信息進行度量，利用日志與威脅之間的關聯關系構建優化目標，并對該方法的伸縮性進行討論，該度量方法為統一量化異構數據提供了啟發。然而，本文研究的是在敵對情況中進行采集代理的部署，不僅要考慮日志數據、流量數據和設備狀態數據這 3類異構數據，而且還要考慮敵對環境中部署方法的頑健性，以上3個方面的相關研究無法直接解決本文的問題，因此，本文提出了一種適用于敵對情況下的采集代理優化部署算法——采集代理頑健部署（RCD, robust collection deployment）算法。本文的主要貢獻如下。

1) 將敵對環境下采集代理優化部署問題歸結為一個攻防博弈問題，并且考慮到采集代理獲取的安全數據的異構性，構建度量攻防博弈（MADG，metric attack and defense game）模型。

2) 在MADG模型的基礎上，利用系統、威脅和采集代理以及三者之間的關聯關系構建威脅-采集樹，利用威脅事件發生的可能性和威脅事件對系統的影響構建攻擊效用函數。

3) 利用上述目標函數的次模性，提出了一種基于貪婪的采集代理頑健部署算法——RCD算法，該算法能找到一組性能至少與最優集合一樣的部署位置集合，但時間成本會稍微增加。

4) 通過構建具體網絡案例模型和擴展模型，從求解時間和求解質量方面進行了一系列的實驗，并與精確求解算法和啟發式算法進行了對比，表明RCD算法的頑健性和可擴展性。

2 相關工作

首先，從3個角度對網絡監測點部署的相關研究進行了梳理。其次，為了直觀地描述敵對環境，借鑒了威脅建模中威脅樹的思想，并對威脅建模的相關工作進行了梳理。

2.1 監測點部署

近年來，很多學者從不同角度對網絡監測點部署問題開展了研究。首先，在網絡測量領域中，主要研究工作集中在網絡測量部署模型及其優化算法上。Aqil[3]把網絡測量部署問題映射為經典優化問題，利用經典優化問題的難解性和近似算法進行求解。Breitbart等[4]使用同樣的映射，采用整數規劃來解決優化問題。Hochbaum[5]則設計了一個啟發式算法求解近似解。此外，Chaudet等[7]對網絡測量部署模型和優化算法進行了歸納總結。Suh等[6]針對主動監測時部署信標分配問題和被動監測時部署tap設備的分配問題進行研究，提出了一個問題組合和高效通用混合整數規劃（MIP, mixed integer programming）公式。上述工作側重于優化問題的描述和求解，沒有考慮采集項中是否存在異構性，且在敵對環境方面沒有給出相關討論。

其次，在環境監測領域中，針對放置有限數量的傳感器來檢測污染物的問題，Leskovec等[9]最早將部署采集器監測水污染的問題歸結為“爆發檢測”問題，并提出了基于貪婪的優化部署算法——CELF（cost-effective lazy forward selection）算法。Comboul等[11]考慮了水分配網中不確定參數對部署方案的影響，從確定系統、不確定系統和靈敏傳感器3個方面對優化部署問題進行優化，利用目標函數次模性提出貪婪算法求解最優化問題。此外，Kraused等[10]針對敵對環境下水分配網絡中采集器優化部署的問題進行了研究，其中對抗設置為對手在知道傳感器位置的情況下選擇污染位置，并對此提出了一種具有頑健性的優化部署算法——Saturation算法。以上研究雖然與本文的研究領域不同，但是解決的問題與本文的問題都是有限個數節點的優化部署問題。

在網絡安全監測領域中，為了盡早發現復雜網絡中病毒的傳播，Yu等[12]提出了一種最小化最壞的感染規模的啟發式算法——MMI（minimizing the maximum infection）算法，該算法具有較快的收斂速度。Zhou等[13]研究了如何有效地部署傳感器位置，以便在網絡中早期發現動態有害級聯問題，并將級聯的動態屬性因素考慮在內，在 CELF算法[9]的基礎上，提出了UBG（upper bound based greedy）算法，求出收益函數的上界，以便刪除不必要的檢測時間估計，同時為了提升計算速度，提出了 2個加速算法。Thakore等[14]先對異構的日志信息進行了度量，并通過日志信息與威脅事件的關系建立了映射關系，然后又在度量的基礎上提出了一個啟發式優化部署算法——GOMD（greedy algorithm to compute the optimal monitor deployment）算法。此外，Talele等[2]針對采集已知攻擊問題的局限性，提出了一種計算網絡監控位置的方法，該方法利用主機間可用訪問控制策略的通用性來計算大規模系統的采集代理的部署位置。上述這些工作均忽略了攻擊者對采集代理部署策略的影響，因此現存的優化部署方案頑健性不足，無法很好地應對敵對環境。

2.2 威脅建模

威脅建模是針對攻擊者如何執行潛在攻擊或對系統構成安全威脅進行簡化、抽象描述的過程。對威脅進行建模可以更直觀地描述威脅和評估威脅影響。在威脅建模的工具中，威脅樹是較常用的一種。Marback等[15]提出了一種基于威脅模型的安全測試方法，該方法可以從威脅樹中自動生成安全測試序列，并將其轉換為可執行測試。Pardue等[16]提出了一種基于威脅樹和蒙特卡羅模擬的風險模型和風險評估技術，其目標是對直覺或風險估計進行合理而簡潔的量化。Morikawa等[17]提出了威脅樹模板來幫助非專家分析人員構建威脅樹，每個模板都是一個冗余的威脅樹，裝載了代表許多可能攻擊場景的分支，以及針對此類攻擊的相應漏洞和對策的典型示例。目前，上述工作均從攻擊的角度來描述威脅和威脅實現的條件，忽略了威脅和安全數據之間的內在聯系。

3 模型

在描述模型之前，為了不出現異議，將采集器、采集代理、網絡監測器統一用“采集代理”表示，涉及采集到的“安全數據”用“采集項”表示。在對敵對環境中優化部署采集代理問題進行建模之前，對該問題進行以下2個基本假設。

假設 1采集代理方面。每個采集代理的采集能力是相同的，部署在不同類型的設備上，不同類型的設備輸出不同類型的數據，因此能夠采集到的采集項具有差異。

假設 2威脅方面。攻擊者是貪婪的，攻擊者通過掃描、滲透、社會工程學等手段獲取部署位置，從而選擇對自己“最有利”的方式進行攻擊，且不會進行無效攻擊。

3.1 問題描述

本文所要優化的問題是如何優化部署采集代理獲取更好的監測效果，并且可以保證部署的成本盡可能最少。本文將其建模為一個基于度量的零和博弈模型——MADG模型：管理員作為防守方（defender），其對應的防守策略是在通信網絡上選取k個設備進行采集代理的部署；攻擊者作為攻擊方（attacker），其攻擊策略是選取所有攻擊方式中的一種。由于是零和博弈，因此有

攻擊方根據獲取的網絡相關信息選擇攻擊效用值最大的一種攻擊方式，而防守方選擇使攻擊方的攻擊策略收益最小化的策略集合，即攻擊方的目的是最大化攻擊效用，防守方的目的是最小化攻擊方的攻擊效用。因此，該問題的目標函數可表示為

3.2 部署目標相關度量定義

為了對式(1)中的目標函數進行精確的分析，本節借鑒文獻[14]中給出的度量框架的一部分，對本文目標函數中相關元素進行了定義和度量。本文的符號及其含義如表1所示。

表1 符號含義

定義 1威脅事件。已經造成攻擊影響的事件和可能會對網絡造成攻擊影響的事件，即系統中存在的攻擊或入侵行為，或者系統中可能出現的攻擊或入侵行為。

本文使用Ψ表示能夠在系統中檢測到的和可能發生的所有威脅事件的集合。

威脅事件并非是采集代理直接采集的采集項條目，而是通過對一個或多個采集信息相關性的分析確定能夠檢測出的威脅。

定義 2內嵌式采集代理。實現網絡監測的采集組件和采集器的統稱。采集組件是安裝在操作系統（如Windows系統、Linux系統等）中的軟件，采集器是部署在終端（如手機終端、衛星終端等）上的傳感器，兩者都可以對部署的設備上的各種類型的數據進行收集，本文用S= {s1,s2, …,sm}表示內嵌式采集代理si(1≤i≤m)的集合。

采集項可以分為3類，即日志數據、網絡流量數據和設備狀態數據。其中，日志數據可以分為以下4類：1) 主機上安裝的Windows系統、Linux系統等操作系統日志數據，2) 網絡中部署的路由器、交換機等傳輸設備日志數據，3) 主機上記錄的SSH、MySQL、HTTP、Web等具體服務運行日志數據，4) 安全防護系統防火墻、IDS等安全設備日志數據。

定義3特征信標。通過采集代理生成的信息可以推斷出系統中發生的威脅事件，在此用?表示[14]。

特征信標并非采集代理采集到的實際數據，而是使用一些邏輯謂詞對單個或多個采集代理獲取的采集項進行連接和加工而生成的信息，是用來定義檢測威脅的必要條件。特征信標的生成主要有 2個步驟：1) 對于每一個威脅事件，將每個采集代理采集的采集項進行分組，根據它們提供的證據類型支持檢測威脅事件；2) 根據采集項和威脅事件的內在聯系，確定需要采集哪些信標、可以監測到哪些威脅事件。

文獻[18-19]對邏輯規范的后續研究工作提供了一定的研究依據，但該問題不是本文的重點，在此不再贅述。此外，在現有的開源情報（如OSINT）和入侵檢測技術為關聯關系映射提供了技術支持的同時，文獻[20-23]針對不同類型網絡中的威脅事件所對應的采集項進行了研究和調研，為該問題提供了一定的理論依據。

采用上述2個步驟，可以對采集到的異構數據格式進行統一，避免了來自不同類型設備上的日志、流量、設備狀態信息格式的差異，同時該方法可以在一定程度上簡化安全領域專家對特征信標的枚舉。盡管無法指定采集代理數據的確定格式，但是專家能夠理解每條特征信標提供的語義信息。

定義 4采集代理和特征信標對應關系。由一個映射函數表示?:s→Φ(C)，即其中，Φ(C)為C的冪集。現對該映射進行說明：映射是從采集代理到采集項一對多的關系，并表示由給定采集代理生成的一組采集項?？紤]多維網絡的異構性、設備差異性較大等因素，針對任何一個威脅事件，可能有多種檢測方法，本文統一采用最小特征信標集合來監測分析威脅事件。

定義 5最小特征信標集合。一組特征信標集合τ能夠檢測分析到一個威脅事件ψ，即所有最小特征信標集合中的元素足以監測到威脅事件ψ[14]。

定義 6檢測威脅事件的證據。一個給定映射γ:Ψ→Φ(Φ(C))，其中，γ(ψ)=(τ|τ用于檢測威脅事件ψ)[14]，γ是一個從威脅事件到特征信標的一對多的映射。在眾多映射中，只要有一組特征信標監測到威脅事件即可。

定義 7真實性。采集代理的真實性是指采集代理所產生的特征信標是正確的[14]。

采集代理的真實性不是二元的，因此本文應用模糊邏輯來評估采集代理的真實性，即采集代理可能不會從真實的信標轉變為錯誤的信標，而可能會繼續為少數威脅事件以外的其他威脅事件提供正確的信標。正如 Hosmer[24]所提出的，模糊邏輯比概率論更適合這種情況。因此，本文定義了一個函數σS，將采集代理映射到生成信標的真實性作為一個模糊邏輯度，表示由采集代理生成的信標中有多少是真實的，即

其中，R為實數集合。

本文將采集代理的真實性映射到其產生的所有指標的真實性上。如果沒有采集代理生成信標，默認情況下該采集代理的真實性為0，即

為了監測一個威脅事件，至少需要采集來自該威脅事件對應最小信標集合中的一個特征信標。因此，對于一個最小的特征信標集合τ，本文結合所有最小特征信標集合τ的真實值來定義該最小特征信標集合τ的置信度。最后，給出監測到的威脅事件Ψ的置信度的定義為：該威脅事件Ψ對應的所有最小特征信標集合的置信度的MTL分離值即為Ψ的置信度。

定義8置信度。置信度定義為[14]

本文考慮了攻擊者在觀察到采集代理的部署位置時，會選擇破壞效果最大的威脅事件進行攻擊，換言之，采集代理部署位置的集合，決定了攻擊者的攻擊策略。

為了直觀地對敵對環境進行描述，本文借鑒威脅建模的思想通過威脅樹對威脅事件、威脅特征信標和采集代理之間的內在聯系，構建威脅-采集樹模型，如圖1所示，并給出了相關定義。

圖1 威脅-采集樹模型

定義9威脅-采集樹。威脅-采集樹是描述威脅事件和采集代理之間通過采集項中信標確定映射關系的一個層次結構，包括目標系統、攻擊類型、威脅事件、信標和采集代理5個層次。其中，第一層是目標系統，即管理員需要保護的系統；第二層是目標系統可能受到攻擊的攻擊類型；第三層是每種攻擊類型可以通過一些威脅事件來實現；第四層是每個威脅事件所對應的威脅特征信標；第五層是能夠采集到威脅信標的采集代理。由此，本文將攻擊方的效用Utilityattacker使用攻擊方選取的威脅事件的風險函數Risk來表示。

定義10風險。風險是威脅事件發生的可能性與威脅事件的影響的乘積，即風險效用函數，具體可形式化定義為

其中，Pψ為攻擊方在防守方部署了采集代理時，威脅事件ψ可能發生的概率，Iψ為威脅事件ψ對系統的影響，即

其中，Ec表示影響系統機密性，wc表示影響系統機密性的權重，Ei表示影響系統完整性，wi表示影響系統完整性的權重，Ea表示影響系統可性，wa表示影響系統可用性的權重?！坝绊憽北硎疽环N威脅事件對系統的影響，本文從機密性、完整性和可用性3個方面對其進行衡量。

Pψ為攻擊方在防守方部署了采集代理時，某一個威脅事件可能發生的概率。該概率是該威脅事件發生但未被最小特征信標集合監測到的概率與該威脅事件發生且被最小特征信標集合監測到的概率之和，即

根據數學歸納，可以將式(4)簡化為

通過上述定義和度量，現將目標函數表示為

3.3 部署目標屬性

根據3.2節中給出的效用函數可以發現，該效用函數具有次模性，即在采集代理部署節點足夠的情況下，再添加一個采集代理的部署點能獲得的收益并不比部署該點前的收益大。后文中使用函數R來代替Riskψ，目標函數R具有以下特性。

1) 次模性：若對所有Sd1?Sd2?V且s∈VSd，則有

2) 單調性：若對所有的Sd1?Sd2?V，則有

3) 規定：R(V)=0。

因此，攻擊者收益問題可以形式化為其中，R具有標準單調次模性，k是部署點個數的限制。式(7)是一個NP-hard問題[25]，該問題經常使用啟發式算法求近似解。Nemhauser等[26]提出一個基本結論：對于具有次模性的函數，貪婪算法實現了一個常數因子近似值，通過貪婪算法集合Sd至少獲得一個常數分數該常數分數是基于通過最優解獲取的觀察點值。例如除非 P=NP[22]，否則沒有多項式時間算法可以提供更好的近似保證。

因此，針對本文的問題選擇使用貪婪算法，其算法思想為：從一個空集開始，迭代地添加一個元素)，直到添加元素的個數滿足k的要求，則貪婪算法選擇完畢。

針對敵對環境，優化采集代理部署問題解決以下問題，即

防守方的目標是選擇一組設備點部署采集代理，能夠應對攻擊方時監測效果表現最好。因此要考慮攻擊方對部署策略的影響。本文的敵對環境設置為攻擊方知道防守方采集代理部署的位置Sd，選擇對防守方結果最壞的Ri。應注意的是，盡管所有的Ri都具有次模性，但是G(Sd)=maxi Ri(Sd)不具備次模性。在這個設置中，簡單貪婪算法可以執行。

本文的目標是找到在應對策略式攻擊時表現良好的采集代理部署位置。因此，本文在連續博弈的矩陣中尋找一種平衡，每一個Sd作為一行，每個Ri作為一列。

定理 1對于式(9)所示問題，除非 P=NP，否則不存在任何多項式時間逼近算法。

證明設n是實際問題中的規模大小，β(.)＞0是任意一個關于n的正函數。如果存在一個多項式時間算法，能夠保證找到一組個數為k的集合S′d，則有

則P =NP。

因此，除非 P=NP，否則就不存在任何可以提供保證的算法。證畢。

4 頑健性采集代理部署算法

由于本文的優化部署目標函數是最小化攻擊方效用，該效用使用了度量值作為目標函數和約束條件，目標函數具有非線性和非凸性。因此，不可能使用凸優化技術（如內部點方法）來解決此目標函數。此外，還有一個額外的限制，即采集代理部署變量是二進制的，所以使用梯度下降方法的混合整數非線性程序解決方案也沒有用處，因為度量函數在搜索空間上不是連續的。同時考慮到敵對環境的設置，本文借鑒了文獻[10]對抗設置來針對目標函數的優化。

4.1 RCD算法思路

RCD算法是在貪婪算法的基礎上進行的。首先，將式(9)問題進行轉換，找到替代的方案。

設集合Sd的大小最大為k，對于所有i可以滿足Ri(Sd)≤z，z盡可能小。

然后，解決目標轉換后成為式(11)問題：對于每個z的取值，可找到成本最低的集合Sd，對于所有的i可以滿足Ri(Sd)≤z。如果成本最低的集合最多具有k個元素，則z是可行的。

最后，用一個固定的z來描述近似解方程(10)。對于z＞ 0，有

最初的函數Ri在z的位置被截斷，其中，函數也是次模函數[27]，其平均值是

次模函數在凸組合下是封閉的，因此，是單調的次模函數。

4.2 RCD算法

本節詳細介紹 RCD算法過程，該算法能找到一組，至少和最優集合一樣的結果，但求解時間會稍微增加。貪婪算法和 RCD算法具體偽代碼如算法1和算法2所示。

算法1貪婪算法

輸入，z

輸出采集代理S的部署位置集合Sd

算法2RCD算法RCD(R1,R2,…,Ri,k)

輸入效用函數R1,R2,…,Ri，采集代理個數k

輸出采集代理S的部署位置集合Sdbest

12) 輸出Sdbest

首先，計算出算法2中所能取到的最大值zmax和最小值zmin，其中，最大值zmax是當所有采集代理都沒有部署時，攻擊方效用值最大；最小值zmin是當所有設備節點上都部署采集代理，攻擊方效用最小。其次，求出最大值zmax和最小值zmin的平均值z，同時，針對任意一組采集代理集合Sd都可以計算出對應的收益。再次，調用算法1，根據均值z與依次找出每一輪中增量絕對值最大的設備節點ID的組合，并且將其賦值給Sdbest；如果Sdbest個數不滿足k的要求，則使用z當前的取值賦給zmax或zmin。最后，再次調用算法1，依次循環來找到滿足目標函數的部署集合。需要注意的是，每次調用算法1時，都是從空集開始的。

5 實驗

5.1 算例

本節以一個小型網絡為目標，如圖2所示，將MADG模型和RCD算法進行實例化，該算例中網絡設備節點共有5個，可以部署采集代理的設備，根據開放式Web應用程序安全項目（OWASP, Open Web Application Security Project）中top10的攻擊類型，選取排名靠前的4類網絡威脅事件。

圖2 小型網絡

采集代理與各指標之間的映射關系為

最小信標集合與威脅事件的對應關系為

根據上述思路可以在采集項中提取對應信息，生成特征信標。本算例中生成的特征信標為

?1: SSH嘗試失敗次數＞閾值

?2: SSH開始嘗試次數＞閾值

?3: Syn半連接個數

?4: XXS嘗試通過資源上的URL字符串/logfile/index.php?page =capture_data.php

?5: XXS嘗試通過表格NET_STAT_INFO注入?6: XXS嘗試通過資源上的URL字符串/logfile/index.php

?7: 包含MySQL版本的字符串

?8:接收到網絡數據分組的個數＞正常值?9: HTTP PHP文件POST請求

?10: MySQL注入HTTP獲取嘗試

?11: CPU利用率＞正常值

?12：表格NET_STAT_INFO嘗試SQL注入

?13: MySQL注入類型詢問

根據威脅事件與威脅事件特征信標之間的關系、威脅事件特征信標和采集代理之間的內在聯系，構建威脅-采集樹模型，如圖3所示。每個威脅事件的最小特征信標集合發生的概率如表2所示。

表2 最小特征信標集合發生的概率

圖3 小算例的威脅-采集樹模型

由于每個特征信標是由不同的采集代理采集的采集項生成的，因此每個特征信標的置信度與生成它的采集代理的置信度保持一致。根據圖2的網絡結構可知，s1為防火墻被攻擊方攻擊的概率比較大，那么它的置信度相對就會小一些，因此，通過MTL給出s1的置信度為0.3，依次類推，給出其他設備置信度，如表3所示。

表3 采集代理置信度

通過對系統的機密性（confidentiality）、完整性（integrity）和可用性（availability）3個方面的考慮，同時參照OWASP中top10列表中的信息，給出本節算例中每個威脅事件的影響值，如表4所示。

表4 威脅事件影響值

本節算例分別使用EXACT算法、GOMD算法[14]、RCD算法進行計算，相關數據如表5所示，3種算法的具體求解數據見附錄。

表5 3種算法求解

5.2 擴展

為測試本文提出的RCD算法的擴展性，在BA網絡上使用50個設備節點、100個威脅事件作為基準進行實驗，并從中生成不同規模的網絡和不同規模的威脅事件集合，分別對每種規模的網絡進行100次實驗，取平均值作為實驗結果。

本節主要對 RCD算法的時效性和頑健性進行驗證，分別對其運行時間和求解質量進行實驗，并與EXACT算法、MMI算法[12]和GOMD算法[14]進行對比。以上所有實驗均在Windows 10的64位系統上運行，該系統加載Inter(R) i7處理器、500 GB硬盤和8 GB內存。

首先，本文在不同規模的網絡（設備節點數量從0個節點增加到50個節點，步長為5）上進行實驗，采集代理的數量k=3，各算法的運行時間如圖4所示，求解質量如表6所示。

圖4 不同規模網絡的運行時間對比

表6 不同規模網絡的求解質量對比

實驗表明，EXACT算法隨著網絡規模增長（20個設備節點時）求解時間開始急劇增長，然而MMI算法[12]和 GOMD 算法[14]的求解時間增長相對緩慢；RCD算法求解時間的增長介于EXACT算法和GOMD算法之間。其中，當設備節點為35個時，由于要多次調用Greedy算法，RCD算法的運行時間出現急劇增長。

在求解質量方面，攻擊者對目標系統的影響值越大，求解數值越大，求解的質量就越差。實驗表明，MMI算法的求解質量最差，GOMD算法在小規模的網絡下（如設備節點在 10個以內）所得解與EXACT算法保持一致，但隨著網絡規模的增加，GOMD算法與EXACT算法之間存在很大的偏差，而RCD算法始終與EXACT算法保持一致。

其次，在網絡規模固定（設備節點數量為 50）的情況下，通過改變采集代理的數量（k=0，3，5，10，15，20，25），對RCD算法和3種對比算法進行實驗。各算法的運行時間如圖5所示，求解質量如表7所示。

圖5 相同規模網絡的運行時間對比

表7 相同規模網絡的求解質量對比

隨著采集代理數量的增加，產生的排列組合數量過多，EXACT算法計算時間急劇上升。當采集代理數量為3時，運行時間為730.057 s，當采集代理數量為5時，運行時間為1 500 s；MMI算法和GOMD算法可以在相對較短的時間內計算出有效解，計算時間的趨勢呈線性增長；RCD算法在開始階段，計算時間隨著采集代理數量呈線性增長，當采集代理數量增加到3個時，運行時間增長趨勢變緩，當采集代理數量增加到5個時，計算時間趨于穩定。

實驗表明，當網絡設備數量總數相等時，采集代理數量增加到一定數量后，EXACT算法求解質量會趨于恒定，且無法給出有效解。雖然 MMI算法和GOMD算法可以給出有效解，但求解質量無法達到精確解值。然而，RCD算法基本與EXACT算法保持一致，隨著采集代理的數量增加，當EXACT算法無法給出有效解時，RCD算法仍然可以繼續給出有效解。

通過實驗表明，本文提出的RCD算法以時間成本為代價，保證了求解質量的精確度，因此該算法是有效可行的，且具有頑健性，還能夠進行一定的擴展。

6 結束語

本文針對敵對情況下采集代理優化部署問題進行了研究。首先，將攻防雙方建模為一個攻防博弈問題，提出一個度量攻防博弈模型——MADG模型；其次，對模型中涉及的系統、威脅和采集代理的相關屬性進行定義和度量，并通過威脅事件和采集項之間的復雜聯系構建了威脅-采集樹；再次，采用數學規劃對攻擊方的效用函數進行構建，即優化的目標函數，并設計了一個具有頑健性的采集代理部署算法——RCD算法，使防守方在面對攻擊方進行策略式攻擊時，部署策略具有比較好的頑健性；最后，通過構建實際算例，分析了本文方法的有效性和可擴展性。

附錄 3種算法的具體求解數據

3種算法的具體求解數據如表8～表10所示。

表8 EXACT算法精確求解

（表8續表）

表9 GOMD算法近似求解

（表9續表）

表10 RCD算法近似求解

（表10續表）