基于多選項二次聯合背包的態勢感知資源分配算法

孫巖煒，郭云川，張玲翠，方濱興

(1.中國科學院信息工程研究所信息安全國家重點實驗室，北京 100093；2.東莞電子科技大學電子信息工程研究院，廣東 東莞 523808)

基于多選項二次聯合背包的態勢感知資源分配算法

孫巖煒1，郭云川1，張玲翠1，方濱興2

(1.中國科學院信息工程研究所信息安全國家重點實驗室，北京 100093；2.東莞電子科技大學電子信息工程研究院，廣東 東莞 523808)

為了有效應對潛在網絡威脅，通過合理利用資源達到最大化提升當前環境安全態勢的目的，研究了有限資源的最優分配方案。網絡態勢的整體性特點使針對某一指標的改善可能會間接影響其他指標，并且投入力度不同，影響程度也有所差異。針對上述特性，將問題抽象成多選項二次聯合背包模型，通過二次背包特性表示態勢評估指標項之間的相互影響，通過多選項背包特性來表示單個指標項的多種投入可能。最后對其做半定規劃松弛，采用分支定界法對問題進行求解。實驗證明了算法的準確性和高效性。

資源分配；態勢感知；多選項二次聯合背包；半定松弛

1 引言

態勢感知的定義最早由Endsley在1988年提出，強調在一定的空間和時間范圍內對環境中元素的獲取和理解，并且對未來的狀態進行預測。隨后在1995年又提出了態勢感知模型[1]，如圖1所示。該定義被應用到網絡中，引起了眾多學者的注意，近年來，涌現出了大量的研究文獻，研究內容主要包括數據采集[2]、數據融合[3,4]、未知異常檢測[5]和態勢可視化展示[6]等，而對用戶進行決策支持的研究則相對較少。正如Tadda等[7]的闡述，目前態勢感知的討論還僅局限于某一個特定的時間點。理想化的模型應像Webb等[8]提出的，分析當前網絡環境態勢，產生相應的措施，態勢受措施影響，進而形成新的態勢，如此循環往復。由此可見，決策支持模塊的研究，是保證整體態勢感知實時性的關鍵。

圖1 態勢感知模型

依照ISO27001、NIST SP800等現有的風險評估準則，以及細化的安全評估指標子項[9]，用戶很容易將當前環境的各個指標進行量化考核，最終加權得到整體的態勢評估結果。但是面對亟待改進的指標子項以及受限的資源總量，如何將資源在指標子項之間進行分配，從而最大化地提升整體的態勢評估結果，是一個復雜的規劃問題。因為態勢是一個整體的概念，各指標子項之間存在著相互的影響關系，牽一發而動全身。例如，通過態勢評估，發現某些關鍵區域缺乏管理和監督，并且工作人員安全意識不足。針對此情況，如果投入大量資源，加大人員考核力度和監管力度，雖然在一定程度上有利于員工提升自己的安全意識，但同時對員工的過分監督、懷疑與不信任，也會產生不可忽視的社會心理學問題[10]，員工有可能表現出消極怠工甚至報復的行為，即對態勢的其他指標子項產生負面影響。正是由于這些錯綜復雜的關聯關系，管理者面對大量有待改進的指標子項，即使有很多改進手段，但容易因考慮不周投入不適當而造成資源的不均衡分配，使最后收益甚微。

面對大量的指標子項，如何分配有限的資源使收益最大化，是典型的背包問題。雖然背包問題有很多種變形，而且相應的算法也很成熟，但是應用到態勢感知環境下，依然有一些問題沒有得到很好的解決。首先，本場景指標子項之間存在相互影響，并且不同的投入力度，其影響程度也有所差異，目前，尚無任何一個模型能夠很好地模擬上述特性；其次，目前，有關背包問題的研究，隨著投入的增長，對應的產出是單調遞增的，而本場景可能存在產出不增反降的情況，目前，針對此情況的求解研究十分有限。

針對上述兩點，本文的主要貢獻如下：將二次背包問題與多選項背包問題相結合，提出了多選項二次聯合背包模型（MCQKP,multiple-choice quadratic knapsack problem），從而很好地解決了態勢感知環境下的資源分配問題；在求解問題時，考慮了收益矩陣元素取值為負的情況，給出了半定規劃松弛的求解方法。

2 相關工作

隨著應用背景的不同，資源分配方法存在巨大差異，根據資源分配模型中參與方的數量差異，可大致分為如下3種：只有單方參與的資源分配問題、雙方參與的資源分配問題以及多方參與的資源分配問題。

單方參與的資源分配問題主要應用在云計算、通信網絡數據傳輸、網絡防護措施選擇等方面，這類問題可簡單概括為：在滿足一定限制的前提下，使參與方的收益最大化或者損失最小化。如果收益函數是線性的，則可用典型的背包問題求解，如果是非線性的，則可以通過取對數等方式將問題線性化之后求解[11]，或采用典型的數據分組分析模型進行分析[12]。Aisopos 等[13]通過背包模型，將云計算中需要的內存、硬盤、CPU資源進行綜合考慮，并且根據用戶需求碎片化的特點，將多重背包問題進行了整數松弛，使整個求解過程的時間復雜度大大降低。Xiao 等[14]的研究目的并非收益最大化，而是在滿足虛擬機需求的前提下，盡可能減少工作實體機數量，從而達到節約資源的目的。另外，通信過程中的帶寬分配，也經常用線性規劃模型來處理。Hajiaghajani等[15]討論終端對終端通信的過程，在保證服務質量的前提下，使最大速率(sum-rate)最大化。Ferdosian等[16]將背包算法用在LTE技術當中，在帶寬有限的前提下，通過評估量化，選取用戶的一個子集提供服務，從而實現系統性能的最大化。同樣受限于帶寬，Sheu等[17]討論無線城域網的資源分配問題，力求通過合理分配帶寬，使網絡吞吐量達到最大化，同時使受眾用戶數量最大化。

涉及雙方參與的資源分配問題，最典型的研究是基于博弈論的資源分配方法。這類研究在網絡攻防領域應用十分廣泛，主要是通過計算納什均衡，來指導管理員對資源的分配。例如，Fielder等[18]通過模擬攻防雙方的零和博弈，算出混合策略下的納什均衡，從而指導用戶進行資源分配優化。Khouzani 等[19]在考慮威脅動態轉移時，同樣通過博弈論的方法，計算帕累托最優，進而計算系統損失的最小值。同樣在資源受限的前提下，Ojamaa等[20]通過離散動態規劃，計算帕累托最優方案，對用戶進行決策支持。

涉及多方參與的資源分配問題，主要應用在云計算、設備到設備（D2D）通信等環境，普遍采用博弈論下的拍賣模型對問題進行模擬和求解。在D2D通信背景下，Wang等[21]提出迭代聯合拍賣算法，通過功率控制和聯合信道管理，有效提高用戶設備的續航能力。Hasan等[22]通過拍賣的方法，研究多層異構網絡下的頻率、時隙等資源的合理分配。有關云計算下的資源分配，Zhang等[23]針對用戶需求的異構性，提出了一種新的競標表述方式，并且構建了具有激勵機制的在線云資源拍賣機制。

結合上述分析，由于本文研究的目的旨在利用有限資源最大化提升當前環境的安全態勢，并未涉及攻擊方，以及其他多方參與的情況，因此，本文研究單方參與的關于網絡安全防護的資源分配問題。與本文類似的研究還包括：Gupta等[24]考慮網絡風險與相應策略之間的關系，假設針對每一個潛在的風險，都會有一個補救措施與之對應，但同時該措施可能會引起其他方面的新風險產生，于是措施選擇問題便轉化成了最小覆蓋的問題。雖然考慮了風險與措施之間的相互影響，但是在建模時將問題進行了簡化，針對某一個風險，只設定了解決、未解決和部分解決這3個狀態，這使其決策支持算法的計算量大大降低。在它的基礎上，Viduto 等[25]還考慮了投入成本的限制因素；Schilling等[11]從德國聯邦信息安全辦公室獲取到大量有價值的安全數據，從中提取出500多項威脅以及1 200多項應對措施，以網絡組件為單位，計算威脅值。Rees等[26]主要對收益、損失等參數進行了討論，通過模糊集理論來處理風險管理當中的不確定性。Sawik等[27]在評估風險時用到了風險價值和條件風險價值這2個指標方法。Mukhopadhyay 等[28]通過基于耦合的貝葉斯信念網絡對網絡風險進行評估和量化，并且根據不同的需求以及有限的投入資源，動態調整決策支持方案。Gordon等[29]將風險與投入進行分級討論，針對不同的安全風險等級，計算相對應的最優投入策略。

雖然文獻[11,24,25]做了內容類似的研究，在選擇防護措施時考慮到了整體性特點，提出了防護措施與安全威脅之間多對多的映射關系，但作者在選擇措施時均只考慮選與不選2種可能，并沒有考慮實施力度的差異，因此，上述研究均有不同程度的局限性。為了克服上述局限，本文采用二次背包模型對問題進行模擬，同時為了使本文的研究更加貼近實際，對問題進行了擴充，目前已有的關于二次背包及其變形[30～32]均已無法滿足需求，因此，本文提出了新的背包模型——多選項二次聯合背包。

3 多選項二次聯合背包問題模型

首先對應用場景進行描述，指出目前研究的不足，接著通過示例引出問題的數學表示，并對問題當中的參數及合理性做了簡單討論，最后提出多選項二次聯合背包模型的數學表述。

3.1 問題描述

在描述問題之前，先給出指標子項以及投入子項的定義，接著給出態勢環境下的背包問題的定義，并且通過逐步引入限制條件，指出目前研究存在的不足。

定義1指標子項。當前環境下，將影響整體態勢的每一個環節，細分為可供評估的若干個指標項，稱之為指標子項，如系統頑健性這個環節包含管理員密碼修改頻率是否達標、服務器代碼是否包含容錯處理和系統內部是否開啟不必要的服務等指標子項；項目及人員管理環節包含特定操作是否有配套規范守則、人員是否遵守、是否有專人監督和是否定期開展人員安全意識考核等子項。每一個指標子項用INDn表示。

定義2投入子項。態勢評估結果中未達標的指標子項，即需要投入一定資源進行改善的指標項。投入子項用INVn表示，每個投入子項包含2個屬性：改善所需資源消耗ri和改善后帶來的評估提升值pi（相關參數將在3.2節做簡單討論，而具體的資源消耗與提升函數關系的討論，超出了本文的研究范圍，在這里只做簡單的假設）。

定義3態勢環境下的背包問題。在投入資源總量受限的條件下，如何選取投入子項進行資源分配，使在不超過總資源限制的前提下，達到評估提升總和最大，這是態勢環境下的背包問題。圖2以柱狀圖的形式描述該問題，針對每一個指標項，其高度表示態勢評估值大小，虛線框表示對該項指標進行投入時所獲得的態勢收益提升，箭頭虛線表示一種可行的分配方案。

圖2 簡單資源分配

在上述問題的基礎上，考慮項目之間存在相互影響的情況。如根據態勢評估結果，需要在人員培訓、人員考核等子項投入資源，最直接的表現是每個投入子項獲得相應的評估值提升。同時，人員培訓還有助于提升員工自身的安全意識，從而在其他工作，如代碼質量方面、密碼強度方面和應急響應方面有間接的提升。但是，加強監督力度等措施，會對工作人員的心里產生不可忽視的影響，甚至產生報復心里，惡意破壞系統內部的正常工作。在本例中的直接體現即對一些特定項產生負收益，資源分配圖示如圖3所示。與圖2相比較，負收益通過實線箭頭表示(圖中部分表示簡化為pxx)。

從圖3可以看出，在投入第2項的時候，除了會獲得自身的收益p22之外，其他項的收益也會受到相應的影響，如圖3中p21、p23等。但是，與二次背包問題不同的是，這里的相互影響是“靜態”的，只要對人員培訓進行投入，那么與其相關聯的p21、p23等就會出現。在這種情況下，只要將問題中的pi稍作調整，即，其中，m為受影響項個數，pii表示投入項i本身的收益，pij表示投入項i對子項j的間接影響收益。經過轉化之后，問題還是可以順利轉化為簡單的背包問題。

圖3 考慮相互影響的資源分配

上面的討論針對某一個投入項i，只有投入與不投入2種情況。而實際中往往每一項i可以有多種投入選擇，即可以選擇投入ri1,ri2,…,rin的資源，同時，其相對應的收益也會存在不同，即。這個問題下的相互影響，已經不再是“靜態”影響，而是會隨著投入的多少發生改變，同樣的投入子項，不同的資源分配，往往會導致大不相同的提升結果。例如，適度對人員監督子項進行投入，會獲得較為理想的正收益，如圖4(c)所示，但是如果過度投入，則會對其他子項產生負面影響，如圖4(a)所示。在這種情況下，現有模型已經無法滿足求解需求，因此，本文提出了多選項二次聯合背包模型。

3.2 多選項二次聯合背包模型參數討論

受二次背包問題的啟發，本文通過二維矩陣表述指標子項之間的相互影響收益，本文統稱為收益矩陣Λ。其中，對角線上的元素表示自身收益，其余元素表示相互影響收益；由于每個子項存在多種投入可能，并且每種投入對其他子項的影響也存在差異，故矩陣當中的每個元素通過4個角標進行描述，其中，pij,kl表示第i項投入j時對第k項投入l時的影響收益，*表示不允許出現的數[33]。

通過一個簡單的例子介紹收益矩陣（為了介紹方便，下述實例并不考慮資源總量的限制）。假設目前可供投入的子項只有人員考核、人員監督和人員培訓3項，每一項可以有投入值為0、1和2這3種選擇。根據定義可以得到如下收益矩陣Λ為

假設投入方案為：對人員考核這一項投入值為1，人員監督投入2，對人員培訓不進行投入，通過0?1向量α表示投入方案，此方案可以通過如下向量表示為

同時，此分配方案對應的總收益為

收益矩陣中的元素pij,kl取值，可參見文獻[9]等，本文只對其合理性做簡單討論。

1) 矩陣中的元素，如果i=k則j=l,即不存在p11,22等元素，在矩陣中用*表示。在上述實例中，即不存在人員考核子項投入1對人員考核子項投入2造成的影響。

2) 針對矩陣當中的元素pij,kl，當j為0，l取任意數時，根據定義可得pij,kl的取值為0，對應上例中的p30,11、p30,22等元素，即投入為0的子項i對其他任何子項的影響為0。但是它關于主對角線位置對稱的元素pkl,ij在上述情況下，卻可能存在不為0的情況，對應上例中的p11,30、p22,30等元素，所以本矩陣嚴格意義上并非對稱矩陣。但是，可以將關于主對角線位置對稱的兩兩元素取平均值，人工將矩陣對稱化，這樣做的目的是方便后續計算，同時不影響計算結果，詳細證明見命題1。

3) 如果i和k保持不變，j和l的任意變化，都會使影響因子產生變化。

命題1在求解收益最大化的過程當中，對于任何一個收益矩陣Λ，在不影響計算結果的前提下，都可以化為一個等價的對稱收益矩陣Λ。

證明假設原始收益矩陣Λ中的元素用pij,kl表示，新建對稱矩陣 ′Λ中的元素用pi′j,kl表示，令

從上面的表述中可以看出 ′Λ是對稱的。現在要證明Λ和 ′Λ具有相同的最優分配方案。設?α為原始收益矩陣Λ的最優分配方案，即

則總的收益提升P可表示為

從上述等式變換可以得知，矩陣Λ的最優分配方案α?同時也是對稱矩陣Λ′的最優分配方案，因此，將矩陣進行對稱化處理，并不影響最優分配方案，故命題得證。

3.3 多選項二次聯合背包模型數學表述

通過上面的描述，最終可以得到多選項二次聯合背包的數學抽象。

假設共有n個物品被分為m個相互獨立的分組：Ν1,…,Nm，每一個物品j∈Ni，重量為wij，Λ為n×n矩陣，其中，pij,ij表示第i組第j個物品被選中所獲得的收益。另外，pij,kl+pkl,ij表示第i組第j個物品與第k組第l個物品同時選中時所產生的額外收益，背包總容量用c表示。同時出于書寫以及計算方便，本文規定pij,ij′=0 (其中j ≠ j′)。多選項二次聯合背包（MCQKP）模型可以表述為

可以看出，該問題是NP難題，因為如果去掉約束條件(1)，問題便轉換為了一般的二次背包問題，而二次背包是NP難題的。另外，與大部分的研究不同，從實際情況出發，本模型并沒有限定矩陣Λ當中的元素的取值為非負。

需要指出的是，從MCQKP的數學表述上來看，它與廣義二次分配問題[34]的表述是極為類似的。但是，二次分配問題的定義，是將M項任務分發給N種可能的設備去處理，其資源消耗矩陣表示如下。

根據定義以及矩陣表述可以看出，二次分配問題當中的每一項任務M都對應相同數目N的分配可能。對應背包問題，它等同于要求每一個分組內的物品數目均相同，這顯然是有局限性的，所以本文闡述的背包模型，在適用范圍上要優于目前已有的廣義二次分配問題。

4 多選項二次聯合背包問題求解

對于背包類的NP問題求解，可分為近似解與精確解兩大類，本文所提的解法屬于精確解。針對背包問題的精確求解，目前已有較為普遍的解決方案CPLEX Optimization Studio，但是受限于其計算問題上界時松弛程度較大，它無法快速地求解這類NP問題，尤其是當計算規模大于一定規模的時候，求解時間將超過1 h甚至更長時間。雖然所有精確解在計算NP問題時的時間復雜度均為指數級，但是計算不同精確度的上界，對于整個計算時間的影響十分明顯。因此，本文借鑒已有研究，對問題進行了半定松弛，通過松弛求解出相比于CPLEX更為精確的上界，并通過啟發式方法求得問題的下界，最后通過分支定界法對問題進行精確求解。

4.1 通過半定松弛求解問題上界

根據文獻[35]提出的QCR方法，本文對MCQKP同樣做了半定松弛，表述如下。

上述問題可以通過CSDP注1：該工具可在網站http://www.coin-or.org/獲取。等已有的求解工具進行求解，求解時間也較為理想，相關證明以及求解方法參考文獻[35]，在此不做過多論述。

4.2 通過啟發式算法計算問題下界

算法參照文獻[36]中介紹的計算下界的啟發式方法，但是由于本問題的分組特性，需要在原方法上加以修改，具體計算步驟如下。

1) 計算問題當中每一個分組i里面收益最高的子項，，并置xij=1。

3) 逐個遍歷集合{xij|xij=1}中的每一個元素，縮小j的值，重新計算，并記作Plow′；選取使ΔPlow=Plow–Plo′w最小的xij變換，即xij置0，xij′置。重復此過程直到W≤c時結束。至此，算法已得到了問題的一個下界Plow1。

4) 繼續對Plow1進行優化。依次遍歷集合{xij|xij=0}的部分，如果xij子項可以直接投入所需資源而沒有超過總限制，則將ΔPijlow記錄為投入該子項所獲得的利益增量。如果無法直接投入，在不超過總資源的基礎上，將該子項與已投入的子項依次輪換，將 ΔPijlow記錄為收益增量的最大值。選取每一個ΔPijlow當中的最大值進行置換，重復此步驟，直到ΔPlow為0時停止，這樣算法就得到了一個較為優質的下界。

4.3 通過分支定界法求解問題的最優解

在得到問題的上界和下界之后，可以用經典的分支定界法對問題進行求解，相關求解的方法在文獻[36]中已有較為詳細的論述。

5 實驗環境與結果分析

5.1 實驗數據及環境

本文在Windows 8系統下進行獨立性能測試。測試機配置為Intel Core i3-3240 3.4 GHz處理器，6 GB內存，其中，CSDP算法采用ECLIPSE集成CSDP-6.1.1進行計算處理， ECLIPSE分配的虛擬內存為2 GB；CLPEX運行環境為CPLEX Optimization Studio Community Edition 12.6。

本文從文獻[9]中提取了30組指標子項，規定其中10組指標子項可投入選項為4項，其余20組指標可投入選項為3項，生成了100×100的收益矩陣Λ。其中，子項之間的相互影響根據文獻[3,37]當中的威脅與防護措施之間多對多的映射來生成。表1列舉了部分措施所對應的威脅數目以及可能引起的負面影響數目。

表1 防護措施與威脅對應關系

具體的各個子項的量化結果，文獻沒有介紹，用戶可以根據每項指標的重要程度差異，來量化投入資源到該子項時所能獲得的收益提升。實驗假設整體態勢的最優值為100，前10項指標項的投入收益p（包含自身收益以及與其相關的所有間接收益）的范圍是0～4，后20項投入收益p的范圍是0～3。

5.2 實驗高效性結果分析

首先進行運行時間的對比，通過隨機生成不同規模的收益矩陣，規定其矩陣密度δ=90%，將矩陣同時放在CPLEX 12.6 Community Edition環境與半定規劃算法進行運算，運行時間上限定為1 800 s，二者的運行時間對比如圖5所示。

圖5 算法運行時間隨收益矩陣規模變化趨勢

從圖5中可以看到，在規模較小的情況下，二者的運行時間差異并不明顯，在CPLEX環境下，運算時間在矩陣規模達到30之后開始急劇增多，在矩陣規模達到50時，已經無法在1 h內求得精確解；而采用半定規劃求解時，當規模增加到100時，其運行時間仍在650 s左右，其1 h內能夠計算出的最大矩陣規模達到125；造成差距如此巨大的一個原因，是由于CPLEX對于問題上界求解的松弛度較高，因此未能有效地縮小枚舉范圍，為了有效地衡量二者在計算上下界時的差異，，松弛度越小，表明上下界貼合越接近，搜索空間越小。表2列出了2種算法松弛度的差異，從表2中可以看出，CPLEX計算的松弛度平均值達到80.9%，而半定規劃的松弛度平均值只有22.26%。

5.3 實驗準確性結果分析

出于最優化計算結果的對比，除了本文提出的多選項二次聯合背包模型之外，還計算了經典背包分配方案[38]和二次背包[39]分配方案。其中，經典背包分配方案在計算時只考慮主對角線元素，而忽視指標項之間的相互影響。二次背包分配方案只考慮投入與不投入2種情況，并不考慮多種投入可能。

表2 2類解法松弛度比較

圖6是3種方案的態勢評估總收益P隨著投入資源總量變化的曲線，可看出，給定任意數量的資源限制，多選項二次聯合背包模型分配方案獲得的收益都是最大的，而且隨著投入數目的增加，其優勢表現得越明顯，因為資源投入越多，其投入的子項數量也相應增多，子項間的相互影響越發明顯，在投入接近140時，收益達到最大值100，而其他2種方案的最大值在90附近。值得注意的是，經典背包方案在投入總量為140附近的時候，出現了態勢評估收益隨投入增加而下降的情況，造成這一現象的原因是各子項之間存在抑制影響，而經典背包方案在考慮資源分配時并沒有兼顧此類影響，致使出現投入增加而收益下降的情況出現。

圖6 態勢評估收益隨總投入變化

圖7是3種分配方案的投入產出比，表示在某一固定投入總量的情況下，單位資源所能獲得的態勢評估收益。由于某種方案在某些特定的投入總數限制下，可能存在資源有剩余的情況，所以實際的投入產出比與總收益的曲線趨勢并不完全一致。從圖7中可以看出，隨著投入增多，單位資源所能獲得的平均收益均為下降趨勢，這是由于在資源總量很少的情況下，要想獲得最大化的收益提升，必然要把有限的資源投入到性價比最高的子項當中，隨著投入總量的增加，單位資源所能獲得的收益提升也隨之降低。經典方案之所以起點較低，同樣是因為沒有考慮子項之間存在的影響收益，單純地選取自身收益最高的子項先行投入，另外2種方案則選取自身收益與影響收益總和最高的子項進行投入。但是二次方案沒有考慮投入的多力度性，在資源總量25附近出現了大幅波動，因為資源總量較少時，二次方案容易出現資源的不完全利用，即并沒有把25的資源全部有效分配，而由于方案考慮的力度過大，剩余資源不足以完成分配，直到總量增加，新增資源與之前的剩余資源足夠進行下一次分配，其收益才會有跳躍式增長。

圖7 單位資源態勢評估收益隨總投入變化

圖8是算法規定投入總數為100的時候，30項指標的投入情況，受到條件限制，二次方案曲線浮動較為明顯，相比之下，另外2種投入方案的浮動較為平緩。聯合方案的投入多集中在中線附近，表明投入較為平均。

圖8 指標子項投入明細

與圖8相對應，圖9是算法規定投入總數為100的時候，30項指標的提升情況。以聯合方案的指標提升值的升序順序進行展示，由于投入資源的差異，各項指標的提升差異較為明顯，但是聯合方案的各項提升較為平均，更加符合態勢的整體性特點，同時整體水平也高于其他2種方案。

圖9 指標子項態勢評估值提升明細

6 結束語

網絡安全態勢感知雖然受到廣泛關注，但是絕大部分研究都聚焦于問題的發現和態勢的展示，決策支持方面的研究則相對較少。在發現威脅以后，如何利用有限的資源最大化地消除隱患，提升當前環境的安全態勢，是一個復雜的規劃問題。因為態勢是一個整體的概念，各子項之間存在著相互的影響關系。根據該特點，本文將問題抽象成為一種新的背包模型，即多選項二次聯合背包，并對其進行了半定規劃松弛，采用分支定界法對問題進行求解。最后通過模擬實驗，證明了本算法的分配方案，要優于目前已有的二次背包分配方案以及經典背包分配方案。

[1]ENDSLEY M R.Toward a theory of situation awareness in dynamic systems[J].Human Factors:The Journal of the Human Factors and Ergonomics Society,1995,37(1):32-64.

[2]DIETTERICH T G,BAO X,KEISER V,et al.Machine learning methods for high level cyber situation awareness[M]//Cyber Situational Awareness.Springer US,2010:227-247.

[3]LIU P,JIA X,ZHANG S,et al.Cross-layer damage assessment for cyber situational awareness[J].Advances in Information Security,2010,46:155-176.

[4]PREDEN J,MOTUS L,MERISTE M,et al.Situation awareness for networked systems[C]//2011 IEEE International Multi-Disciplinary Conference on Cognitive Methods in Situation Awareness and Decision Support (CogSIMA).IEEE,2011:123-130.

[5]BRANNON N G,SEIFFERTT J E,DRAELOS T J,et al.Coordinated machine learning and decision support for situation awareness[J].Neural Networks,2009,22(3):316-325.

[6]TAMASSIA R,PALAZZI B,PAPAMANTHOU C.Graph drawing for security visualization[C]//International Symposium on Graph Drawing.Springer Berlin Heidelberg,2008:2-13.

[7]TADDA G P,SALERNO J S.Overview of cyber situation awareness[M].Cyber Situational Awareness.Springer US,2010:15-35.

[8]WEBB J,AHMAD A,MAYNARD S B,et al.A situation awareness model for information security risk management[J].Computers &Security,2014,44:1-15.

[9]Federal Office for Information Security:13 EL:Cross-reference tables of the IT-grundschutz catalogues:13th version (2013).[EB/OL].https:// http://enos.itcollege.ee/～valdo/bsieng/en/gstoolhtml/allgemein/vorwort /00001.html.

[10]GREITZER F L,FRINCKE D A.Combining traditional cyber security audit data with psychosocial data:towards predictive modeling for insider threat mitigation[M]//Insider Threats in Cyber Security.Springer US,2010:85-113.

[11]SCHILLING A,WERNERS B.Optimizing information systems security design based on existing security knowledge[C]//International Conference on Advanced Information Systems Engineering.Springer International Publishing,2015:447-458.

[12]DU J,COOK W D,LIANG L,et al.Fixed cost and resource allocation based on DEA cross-efficiency[J].European Journal of Operational Research,2014,235(1):206-214.

[13]AISOPOS F,TSERPES K,VARVARIGOU T.Resource management in software as a service using the knapsack problem model[J].International Journal of Production Economics,2013,141(2):465-477.

[14]XIAO Z,SONG W,CHEN Q.Dynamic resource allocation using virtual machines for cloud computing environment[J].IEEE Transactions on Parallel and Distributed Systems,2013,24(6):1107-1117.

[15]HAJIAGHAJANI F,RASTI M.Downlink resource reuse for device-to-device communication underlying cellular networks using a generalized knapsack framework[C]//2016 13th IEEE Annual Consumer Communications &Networking Conference (CCNC).IEEE,2016:171-176.

[16]FERDOSIAN N,OTHMAN M,ALI B M,et al.Greedy–knapsack algorithm for optimal downlink resource allocation in LTE networks[J].Wireless Networks,2015:1-14.

[17]SHEU J P,KAO C C,YANG S R,et al.A resource allocation scheme for scalable video multicast in WiMAX relay networks[J].IEEE Transactions on Mobile Computing,2013,12(1):90-104.

[18]FIELDER A,PANAOUSIS E,MALACARIA P,et al.Decision support approaches for cyber security investment[J].Decision Support Systems,2016,86:13-23.

[19]KHOUZANI M H R,MALACARIA P,HANKIN C,et al.Efficient numerical frameworks for multi-objective cyber security planning[C]//European Symposium on Research in Computer Security.Springer International Publishing,2016:179-197.

[20]OJAMAA A,TYUGU E,KIVIMAA J.Pareto-optimal situation analysis for selection of security measures[C]//MILCOM 2008-2008 IEEEMilitary Communications Conference.IEEE,2008:1-7.

[21]WANG F,XU C,SONG L,et al.Energy-efficient resource allocation for device-to-device underlay communication[J].IEEE Transactions on Wireless Communications14.4.2015:2082-2092.

[22]HASAN M,HOSSAIN E.Distributed resource allocation in D2D-enabled multi-tier cellular networks:an auction approach[C]// 2015 IEEE International Conference on Communications (ICC).IEEE,2015.

[23]ZHANG H,JIANG H,LI B,et al.A framework for truthful online auctions in cloud computing with heterogeneous user demands[J].IEEE Transactions on Computers,2016,65(3):805-818.

[24]GUPTA M,REES J,CHATURVEDI A,et al.Matching information security vulnerabilities to organizational security profiles:a genetic algorithm approach[J].Decision Support Systems,2006,41(3):592-603.

[25]VIDUTO V,MAPLE C,HUANG W,et al.A novel risk assessment and optimization model for a multi-objective network security countermeasure selection problem[J].Decision Support Systems,2012,53(3):599-610.

[26]REES L P,DEANE J K,RAKES T R,et al.Decision support for cyber security risk planning[J].Decision Support Systems,2011,51(3):493-505.

[27]SAWIK T.Selection of optimal countermeasure portfolio in IT security planning[J].Decision Support Systems,2013,55(1):156-164.

[28]MUKHOPADHYAY A,CHATTERJEE S,SAHA D,et al.Cyber-risk decision models:to insure IT or not?[J].Decision Support Systems,2013,56:11-26.

[29]GORDON L A,LOEB M P.The economics of information security investment[M]//Economics of Information Security.Springer US,2004:105-125.

[30]LéTOCART L,PLATEAU M C,PLATEAU G.An efficient hybrid heuristic method for the 0-1 exact k-item quadratic knapsack problem[J].Pesquisa Operacional,2014,34(1):49-72.

[31]SHENG H,SUN J,SUN X.A Rigorous method for solving 0-1 polynomial knapsack problem [J].Journal of Shanghai University (Natural Science Edition),2006,4:012.

[32]BRETTHAUER K M,SHETTY B.Quadratic resource allocation with generalized upper bounds[J].Operations Research Letters,1997,20(2):51-57.

[33]HAHN P,GRANT T.Lower bounds for the quadratic assignment problem based upon a dual formulation[J].Operations Research,1998,46(6):912-922.

[34]HAHN P M,KIM B J,GUIGNARD M,et al.An algorithm for the generalized quadratic assignment problem[J].Computational Optimization and Applications,2008,40(3):351-372.

[35]BILLIONNET A,ELLOUMI S,PLATEAU M C.Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation:the QCR method[J].Discrete Applied Mathematics,2009,157(6):1185-1197.

[36]CAPRARA A,PISINGER D,TOTH P.Exact solution of the quadratic knapsack problem[J].Informs Journal on Computing,1999,11(2):125-137.

[37]ANDERSON R H,FELDMAN P M,GERWEHR S,et al.Securing the US defense information infrastructure:a proposed approach[R].Rand Corp Santa Monica CA,1999.

[38]KELLERER H,PFERSCHY U,PISINGER D.Introduction to NP-completeness of knapsack problems[M].Springer Berlin Heidelberg,2004.

[39]BRETTHAUER K M,SHETTY B.The nonlinear knapsack problem–algorithms and applications[J].European Journal of Operational Research,2002,138(3):459-472.

孫巖煒（1989-），男，山西太原人，中國科學院信息工程研究所博士生，主要研究方向為網絡安全。

郭云川（1977-），男，四川營山人，博士，中國科學院信息工程研究所副研究員，主要研究方向為網絡與信息系統安全、訪問控制。

張玲翠（1986-），女，河北故城人，中國科學院信息工程研究所博士生，主要研究方向為網絡安全、信息保護。

方濱興（1960-），男，江西萬年人，中國工程院院士，東莞電子科技大學教授，主要研究方向為計算機體系結構、計算機網絡與信息安全。

Resource allocation algorithm for situation awareness based on multiple-choice quadratic knapsack

SUN Yan-wei1,GUO Yun-chuan1,ZHANG Ling-cui1,FANG Bin-xing2
(1.State Key Laboratory of Information Security,Institute of Information Engineering,CAS,Beijing 100093,China;2.Institute of Electronic and Information Engineering,University of Electronic Science and Technology of China in Dongguan,Dongguan 523808,China)

In order to deal with the potential cyber-threat and improve the security situation by using limited resource properly,the optimal allocation of resource focused on cyber security situation.The coherence of network situation lead to the fact that the enhancement of certain item may also affect some other items,and different amount of investment may also result in different degree of impact,therefore,the problem was extracted into the multiple-choice quadratic knapsack problem.The characteristics of quadratic knapsack problem was used to model the interactions among the situation indicator items,meanwhile used the multiple choice knapsack problem to model the multiple investment choice for each item.A branch and bound algorithm was conducted by using the semi-definite relaxation.The experiment results show the accuracy and efficiency of proposed algorithm.

resource allocation,situation awareness,multiple-choice quadratic knapsack,semi-definite relaxation

s:Strategic Priority Research Program of Chinese Academy of Sciences(No.XDA06030200),The National Key Research and Development Program of China (No.2016YFB0800303,No.2016YFB0800700),Core Electronic Devices,High-end General Purpose Chips and Basic Software Products (No.2015ZX01029101),The Industry-University-Research Cooperation Project of Guangdong Province (No.2016B090921001)

TP301

A

10.11959/j.issn.1000-436x.2016272

2016-08-11；

2016-11-01

郭云川，guoyunchuan@iie.ac.cn

中國科學院戰略先導專項基金資助項目（No.XDA06030200）；國家重點研發計劃基金資助項目（No.2016YFB0800303,No.2016YFB0800700）；核高基基金資助項目（No.2015ZX01029101）；廣東省產學研合作基金資助項目（No.2016B090921001）