基于多選項二次聯(lián)合背包的態(tài)勢感知資源分配算法

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

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

基于多選項二次聯(lián)合背包的態(tài)勢感知資源分配算法

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

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

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

資源分配；態(tài)勢感知；多選項二次聯(lián)合背包；半定松弛

1 引言

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

圖1 態(tài)勢感知模型

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

3 多選項二次聯(lián)合背包問題模型

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

3.1 問題描述

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

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

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

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

圖2 簡單資源分配

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

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

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

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

3.2 多選項二次聯(lián)合背包模型參數(shù)討論

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

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

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

同時，此分配方案對應(yīng)的總收益為

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

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

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

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

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

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

從上面的表述中可以看出 ′Λ是對稱的?，F(xiàn)在要證明Λ和 ′Λ具有相同的最優(yōu)分配方案。設(shè)?α為原始收益矩陣Λ的最優(yōu)分配方案，即

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

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

3.3 多選項二次聯(lián)合背包模型數(shù)學(xué)表述

通過上面的描述，最終可以得到多選項二次聯(lián)合背包的數(shù)學(xué)抽象。

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

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

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

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

4 多選項二次聯(lián)合背包問題求解

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

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

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

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

4.2 通過啟發(fā)式算法計算問題下界

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

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

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

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

4.3 通過分支定界法求解問題的最優(yōu)解

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

5 實驗環(huán)境與結(jié)果分析

5.1 實驗數(shù)據(jù)及環(huán)境

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

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

表1 防護措施與威脅對應(yīng)關(guān)系

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

5.2 實驗高效性結(jié)果分析

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

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

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

5.3 實驗準確性結(jié)果分析

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

表2 2類解法松弛度比較

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

圖6 態(tài)勢評估收益隨總投入變化

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

圖7 單位資源態(tài)勢評估收益隨總投入變化

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

圖8 指標子項投入明細

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

圖9 指標子項態(tài)勢評估值提升明細

6 結(jié)束語

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

[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-），男，山西太原人，中國科學(xué)院信息工程研究所博士生，主要研究方向為網(wǎng)絡(luò)安全。

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

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

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

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

中國科學(xué)院戰(zhàn)略先導(dǎo)專項基金資助項目（No.XDA06030200）；國家重點研發(fā)計劃基金資助項目（No.2016YFB0800303,No.2016YFB0800700）；核高基基金資助項目（No.2015ZX01029101）；廣東省產(chǎn)學(xué)研合作基金資助項目（No.2016B090921001）