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

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

1 引言

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

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

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

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

2) 在MADG模型的基礎(chǔ)上，利用系統(tǒng)、威脅和采集代理以及三者之間的關(guān)聯(lián)關(guān)系構(gòu)建威脅-采集樹，利用威脅事件發(fā)生的可能性和威脅事件對系統(tǒng)的影響構(gòu)建攻擊效用函數(shù)。

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

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

2 相關(guān)工作

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

2.1 監(jiān)測點部署

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

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

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

2.2 威脅建模

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

3 模型

在描述模型之前，為了不出現(xiàn)異議，將采集器、采集代理、網(wǎng)絡監(jiān)測器統(tǒng)一用“采集代理”表示，涉及采集到的“安全數(shù)據(jù)”用“采集項”表示。在對敵對環(huán)境中優(yōu)化部署采集代理問題進行建模之前，對該問題進行以下2個基本假設。

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

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

3.1 問題描述

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

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

3.2 部署目標相關(guān)度量定義

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

表1 符號含義

定義 1威脅事件。已經(jīng)造成攻擊影響的事件和可能會對網(wǎng)絡造成攻擊影響的事件，即系統(tǒng)中存在的攻擊或入侵行為，或者系統(tǒng)中可能出現(xiàn)的攻擊或入侵行為。

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

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

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

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

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

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

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

采用上述2個步驟，可以對采集到的異構(gòu)數(shù)據(jù)格式進行統(tǒng)一，避免了來自不同類型設備上的日志、流量、設備狀態(tài)信息格式的差異，同時該方法可以在一定程度上簡化安全領(lǐng)域?qū)＜覍μ卣餍艠说拿杜e。盡管無法指定采集代理數(shù)據(jù)的確定格式，但是專家能夠理解每條特征信標提供的語義信息。

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

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

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

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

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

其中，R為實數(shù)集合。

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

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

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

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

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

圖1 威脅-采集樹模型

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

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

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

其中，Ec表示影響系統(tǒng)機密性，wc表示影響系統(tǒng)機密性的權(quán)重，Ei表示影響系統(tǒng)完整性，wi表示影響系統(tǒng)完整性的權(quán)重，Ea表示影響系統(tǒng)可性，wa表示影響系統(tǒng)可用性的權(quán)重。“影響”表示一種威脅事件對系統(tǒng)的影響，本文從機密性、完整性和可用性3個方面對其進行衡量。

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

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

通過上述定義和度量，現(xiàn)將目標函數(shù)表示為

3.3 部署目標屬性

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

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

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

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

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

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

針對敵對環(huán)境，優(yōu)化采集代理部署問題解決以下問題，即

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

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

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

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

則P =NP。

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

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

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

4.1 RCD算法思路

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

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

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

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

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

次模函數(shù)在凸組合下是封閉的，因此，是單調(diào)的次模函數(shù)。

4.2 RCD算法

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

算法1貪婪算法

輸入，z

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

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

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

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

12) 輸出Sdbest

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

5 實驗

5.1 算例

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

圖2 小型網(wǎng)絡

采集代理與各指標之間的映射關(guān)系為

最小信標集合與威脅事件的對應關(guān)系為

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

?1: SSH嘗試失敗次數(shù)＞閾值

?2: SSH開始嘗試次數(shù)＞閾值

?3: Syn半連接個數(shù)

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

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

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

?8:接收到網(wǎng)絡數(shù)據(jù)分組的個數(shù)＞正常值?9: HTTP PHP文件POST請求

?10: MySQL注入HTTP獲取嘗試

?11: CPU利用率＞正常值

?12：表格NET_STAT_INFO嘗試SQL注入

?13: MySQL注入類型詢問

根據(jù)威脅事件與威脅事件特征信標之間的關(guān)系、威脅事件特征信標和采集代理之間的內(nèi)在聯(lián)系，構(gòu)建威脅-采集樹模型，如圖3所示。每個威脅事件的最小特征信標集合發(fā)生的概率如表2所示。

表2 最小特征信標集合發(fā)生的概率

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

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

表3 采集代理置信度

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

表4 威脅事件影響值

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

表5 3種算法求解

5.2 擴展

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

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

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

圖4 不同規(guī)模網(wǎng)絡的運行時間對比

表6 不同規(guī)模網(wǎng)絡的求解質(zhì)量對比

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

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

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

圖5 相同規(guī)模網(wǎng)絡的運行時間對比

表7 相同規(guī)模網(wǎng)絡的求解質(zhì)量對比

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

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

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

6 結(jié)束語

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

附錄 3種算法的具體求解數(shù)據(jù)

3種算法的具體求解數(shù)據(jù)如表8～表10所示。

表8 EXACT算法精確求解

（表8續(xù)表）

表9 GOMD算法近似求解

（表9續(xù)表）

表10 RCD算法近似求解

（表10續(xù)表）