基于高階異構度的執行體動態調度算法

2022-03-31 07:11:34賈洪勇潘云飛劉文賀曾俊杰張建輝

通信學報 2022年3期

賈洪勇，潘云飛，劉文賀，曾俊杰，張建輝

（1.鄭州大學網絡空間安全學院，河南鄭州 450001；2.國家數字交換系統工程技術研究中心，河南鄭州 450001）

0 引言

針對當今網絡安全易攻難守的局面，美國國家科學技術委員會提出了移動目標防御（MTD，moving target defense）[1]。其采用包括IP 地址和端口跳變[2]、IP 安全協議隨機化[3]、用戶角色隨機化、地址空間隨機化[4-7]、指令集合隨機化[8]以及動態路由[9]等相關技術手段構建一種動態的、不確定的網絡攻防環境，使防御目標對攻擊者表現出不可預測的狀態。

2014 年，鄔江興院士[10]提出了網絡空間擬態防御（CMD，cyber mimic defense），并結合生物學“擬態偽裝”和“特異和非特異性免疫”現象，以異構冗余和動態反饋機制不斷調整防御系統執行環境，從而打破以往的被動防御，以一種主動變遷[11]的方式對已知或未知漏洞后門等實現優秀的防御效果。其核心架構是動態異構冗余（DHR，dynamic heterogeneous redundancy）[12-13]，如圖1 所示。

圖1 DHR 架構

調度和裁決模塊是DHR 的2 個核心模塊。調度模塊具有從等待池調度執行體進入運行池的功能，一個優秀的調度算法應兼顧調度的動態性和安全性，使攻擊者無法判斷當前運行執行體編號并使調入執行體對攻擊者的攻擊造成嚴重阻礙；裁決模塊具有判斷運行池中執行體輸出是否正確的功能，其能幫助系統分辨出已被攻破的執行體，評估并預警系統的安全隱患。調度/裁決算法的可靠程度關系到DHR 架構的安全性，即整個系統的安全程度，因此對調度/裁決算法的研究是至關重要的。本文主要針對調度算法的優化進行研究。

目前，圍繞調度算法[14]的優化問題，已有很多學者提出了相應的解決方案。文獻[15]提出了基于歷史信息的人工調度算法FAWA（feedback artificial weighted algorithm），該算法通過歷史記錄威脅信息動態調度執行體以達到動態改變的效果，但未考慮執行體間的差異性問題；文獻[16-17]采用二階相似性進行裁決/調度算法優化，這種方法能有效增大運行池中執行體的異構度，減小共模漏洞，但在等待池中執行體確定的情況下會造成執行體集調度單一化的問題；文獻[18]提出了基于隨機種子的調度算法，該算法考慮了調度的動態性和執行體間異構度，但其只考慮了執行體的二階異構度，無法準確評估執行體間的差異性；文獻[19]提出了高階異構度的性質并給出了基于高階異構度的裁決算法，其證明了引入高階異構度的裁決算法具有優于傳統僅考慮二階異構度算法的安全性，但并未給出高階異構度的計算方法。目前，執行體調度領域的研究缺少一種從高階層面考慮執行體間異構度的動態調度算法。

本文的主要研究工作及貢獻如下。

1)在FAWA 的基礎上引入高階異構度思想，設計并提出了一種同時考慮歷史威脅信息和執行體高階異構度的調度算法HFAWA（high level heterogeneity feedback artificial weighted algorithm），解決了因未考慮異構度導致系統共模漏洞過多、只考慮異構度造成執行體調度固化無法動態變動的問題。

2)基于容斥原理給出高階相似度和高階異構度的計算方式，解決了目前缺少高階異構度計算方法的問題。

3)通過對DHR 結構中調度模塊與裁決模塊間關聯分析，提出了根據裁決算法動態改變的HFAWA 改進策略，并以大數裁決算法為例給出了相應改變方法。

4)通過進行碰撞實驗和大數裁決系統攻擊（LSA，large number adjudication system attack）實驗，對現有5 種調度方案進行對比評估，驗證了HFAWA 相較于以往方案具有明顯的安全性優勢且兼具動態調度執行體的能力。

1 基于高階異構度的負反饋調度算法

1.1 二階異構度存在的問題

目前，在引入異構度的執行體調度算法的研究中，使用的異構度指標均為二階異構度[16]，其通過異構體之間兩兩比較的差異程度值求和的方式來計算整體的差異度。當運行池大小大于2 時，僅考慮二階異構度的調度算法會產生局限性，造成系統出現共模漏洞。下面進行舉例分析。

假設在系統等待池中存在4 個執行體（編號為1～4），其存在的漏洞情況如表1 所示。

表1 執行體存在的漏洞情況

若當前所需調度執行體數量為3，則可以得到異構體間的2 階相似度矩陣為

對各種調度情況的相似度進行求和，如表2所示。

表2 二階相似度求和

算法應選取二階相似度最小（即異構度最大）結果作為調度方案，即1，2，3 或1，3，4。但當觀察執行體漏洞情況時發現，無論是1，2，3 還是1，3，4 均存在大小為1 的共模漏洞（5 或1）；當系統選擇1，2，4 時，系統整體共模漏洞為0，為最優解。因此，需要引入高階異構度來解決這一問題。

1.2 基于相似度的高階異構度計算方法

文獻[18]給出了二階相似度的相關含義指標，即在余度為n的n模冗余體集合Ω中，相似度由集合中所有不同元素兩兩之間的相似度之和歸一化表示，即

這種相似度計算方式缺乏對高階異構性的考慮，沒有分析高階共生漏洞對異構體的影響，因此文獻[19]提出了高階相似度的相關含義，并給出了相關性質和推論。本節將在其基礎上通過對容斥原理加以分析，從而提出高階相似性的計算方式，并延伸至高階異構度的計算。

容斥原理是統計學中一種常用的計數方法，在計數時為了防止重疊部分被重復計算，提出先對整體所有元素進行計數，然后排除被重復計算元素的方法。其數學表達式為

在碰撞實驗中，執行體由防御原子組成，因此可以將執行體的防御面積當作該執行體中防御原子的集合，從而通過容斥原理計算多個執行體的共同防御面積，即相似性，如圖2 所示。

圖2 三模異構冗余體的高階相似度

圖2中以圓的面積表示執行體的防御平面，S(2)表示2 個執行體之間的二階相似區域，S(3)表示3 個執行體之間的三階相似區域，同理，S(n)表示n個執行體之間的n階相似區域，它們之間的關系為

易知n階相似區域性質與n階相似度性質相符，因此，可將圖2中的n階相似區域等價為n階相似度進行計算。

在得到高階相似度S(n)之后，可進行計算求得高階異構度[20-22]。以碰撞實驗為例，高階異構度的計算式為

對其進行歸一化處理，有

1.3 算法內容

針對之前所述調度算法存在的問題，基于FAWA和高階異構度思想，設計了一種同時考慮歷史威脅信息和異構體間高階異構度的動態調度算法HFAWA。符號表示如表3 所示，并根據以下定義對算法進行形式化描述。

表3 符號表示

定義2異構執行體池。異構執行體池由多個功能等價的異構執行體組成，異構執行體池分為等待池ΩW和運行池ΩR，可表示為Ω={A1，A2，…，AN}，各執行體間相互獨立。

根據表3中的符號定義，對其中部分符號的用法及計算方式做以下說明。

技術因素與技術團隊的建設互為影響，技術選型影響著開發團隊的技術組成和技術積累，同時團隊現有的技術積累和人員配置又影響著技術選型。企業在做移動應用時，通常需同時考慮用戶對應用的功能性和非功能性需求指標, 而非單純的技術因素，下面對一些影響選型的限制因素進行分析。

4)M為執行體調度概率矩陣，其值根據歷史威脅反饋動態改變，計算方式與文獻[14]中計算方法相同。

5)調度值D是算法選取執行體的重要憑證，D值越大，執行體被調度的可能性越高。D的計算式為

根據以上定義及計算式，基于高階異構度的負反饋調度算法HFAWA 如算法1 所示。

算法1基于高階異構度的負反饋調度算法HFAWA

輸入等待池ΩW，運行池執行體容量NR，高階異構度矩陣H，執行體調度概率矩陣M，選取執行體集Sel，最大調度值集合best_s。其中H(n)已提前計算完畢，M矩陣初始默認值為全1，Sel 與best_s 初始為空，大小與ΩR相同

輸出運行池ΩR

算法1 為一次調度的HFAWA 實現，其中矩陣M隨每次調度記錄的歷史威脅信息反饋而改變，從而影響下次調度結果。算法1 對應的算法流程如圖3 所示。

圖3 算法1 對應的算法流程

1.4 算法用例

下面以NR=5的DHR 系統為例，對HFAWA運行流程進行簡要說明。

1)當選擇執行體集Sel 為空時，挑選M數組中最大的執行體A1進行調度加入Sel。Sel={A1}，將Sel 送入算法進行下一執行體選擇。

3)將等待池中除Sel中已有執行體外的執行體wi輪流與Sel中執行體匹配，計算選擇D最大的執行體加入Sel；若D最大值不唯一，將對應執行體分別加入Sel。Sel={A1，A2，A3}，將Sel 送入算法進行下一執行體選擇。

4)將等待池中除Sel中已有執行體外的執行體wi輪流與Sel中執行體匹配，計算M[i]，選擇D最大的執行體加入Sel；若D最大值不唯一，將對應執行體分別加入 Sel。Sel={A1，A2，A3，A4}，將Sel 送入算法進行下一執行體選擇。

5)將等待池中除Sel中已有執行體外的執行體wi輪流與 Sel中執行體匹配，計算D=，選擇D最大的執行體加入Sel；若D最大值不唯一，從中隨機選取一執行體加入Sel。S el={A1，A2，A3，A4，A5}，將Sel 輸出，Sel 即當次選擇調度5 模異構體。

1.5 算法分析

目前，針對多執行體策略的評估方法有很多，如基于博弈模型對攻防雙方進行收益量化作為評判標準[23]、采用攻擊成功累計時長作為評判標準[24]、采用成功控守目標個數作為評判標準[25]等。本文采用當前運行池中執行體集的共模漏洞個數作為評判標準。

在不考慮執行體歷史信息的影響，即執行體調度概率矩陣M時。算法的調度值僅受異構度值Hi影響，即

以表1中執行體情況為例進行分析。

1)在算法初始選擇執行體時，由于各執行體間無調度值差別，因此遍歷所有執行體分別加入執行體待選集Sel中，并送入算法進行下一階段執行體選擇，Sel={{1}，{ 2}，{3 }，{ 4}}。

2)根據之前送入的執行體待選集，分別遍歷剩余執行體并計算二階異構度，選出異構度最高的集合送入算法進行下一階段執行體選擇。根據表1中執行體的二階相似度矩陣可知，此時被選擇送入算法的執行體集為Sel={{1，2}，{1，3}，{1，4}，{ 2，3}，{ 3，4}}（相似度最低）。

3)根據之前送入的執行體待選集，分別遍歷剩余執行體并計算三階異構度，選出異構度最高的集合，此時算法計算最高階數與運行池容量相等，因此輸出算法最終選擇結果Sel={1，2，4}，共模漏洞數量為0。

算法中影響調度值的另一部分矩陣M僅受執行體的歷史信息影響，即執行體被攻擊次數。而在實際情況中，攻擊者是無法預先探知擬態系統中被調度執行體的種類的，即攻擊者的攻擊意圖與調度算法無關。因此，矩陣M對不同算法的安全性影響是相同的，而又由于增加了歷史信息的影響，算法的動態性得到了提升（通過攻擊者的攻擊傾向而動態調度執行體）。

由此可見，HFAWA 在調度時會盡可能選擇使系統共模漏洞數量少的執行體進行調度，能夠在保證安全性的前提下表現出良好的動態性。

2 算法及實驗改進

在碰撞實驗中給出高階異構度計算式H(n)=P(n)-S(n)，這樣做的目的是盡量增大防御面積，選擇防御面積最大的執行體集進行調度。但在實際的擬態場景中并非防御面積越大效果越好。在經典擬態場景中通常需要構建執行體池，由調度算法調度執行體進入運行池，最后根據裁決算法對執行體輸出結果進行裁決。因此，一個優秀的調度算法往往需要根據擬態構造的裁決機制進行相應的調整。

目前，學者已提出了很多裁決算法，如基于高階異構度的裁決算法[19]、基于二進制文件的裁決算法[26]、基于異常值的裁決算法[27]、大數裁決算法[28]等。相較于其他算法，大數裁決算法以其通用性被更廣泛地應用于現有的DHR 系統中，其基本思想是將執行體輸出相同數量最多的結果作為判決結果。因此本節將以大數裁決算法為例，對HFAWA 進行調整，同時構建相應測試模型對算法有效性進行測試。

本文在算法1和文獻[15]碰撞實驗的基礎上做如下調整。

1)將碰撞實驗中執行體由防御原子組成改為執行體由漏洞原子組成，每個執行體的漏洞原子個數為最大威脅數的，且最小不少于10 個。

2)威脅生成策略不變，為隨機裝載和全裝載。碰撞測試調整為若執行體中存在威脅集中的漏洞原子則被攻破。在5 模異構執行體集中，若攻破執行體數超過3 個，則判斷系統被攻破。

大數裁決下5 模執行體高階異構度如表4 所示。調整后的實驗算法如算法2 所示。

算法2大數裁決系統攻擊實驗算法

輸入系統執行體池Ω，執行體調度概率矩陣M，調度總輪次n，歷史威脅記錄矩陣HS

輸出系統平均攻破率PA

1)計算系統高階異構度矩陣H，計算式如表4 所示

表4 大數裁決下5 模執行體高階異構度

算法2 對應的實驗流程如圖4 所示。

圖4 算法2 對應的實驗流程

3 失效率分析

采用大數裁決算法的擬態防御系統被攻破的概率等效于運行池中半數以上執行體產生共模漏洞的概率之和，因此可以采用被選中的異構執行體共模漏洞的面積與公共漏洞的面積之比作為系統被攻破的概率。

幾個基本假設如下。

假設1攻擊者每次隨機使用一種攻擊方式進行攻擊，若該攻擊方式能同時攻破半數以上處于運行池中的執行體，則擬態系統被攻破。

假設2HFAWA、FAWA、H2 算法[15]均使用執行體的歷史信息作為部分調度依據，雖然具體使用方法有所差異，但為了便于分析，均使用P(HI)表示被執行體歷史信息（HI，history information）所影響的執行體調度概率。

假設3當前等待池中執行體的漏洞數量為，二階共模漏洞數量為Nb，…，n階共模漏洞數量為。漏洞總數為Nsum=Na∪Nb∪…∪Nz。

根據以上假設，可得各算法在運行池大小為k的擬態系統中的失效率如表5 所示。

表5 各算法在運行池大小為k 的擬態系統中的失效率

接下來，將通過實驗比較以上算法的安全性能。

4 實驗驗證

4.1 安全性實驗

為了驗證HFAWA 的有效性，將其與其他4 種調度算法（FAWA、FIFO、Random、H2）進行對比。其中H2 為文獻[16]中的算法，該文提出將異構度（2 階）與歷史信息（執行體運行次數）結合，其焦點在于裁決算法的改進，因此根據其思想實現“H2 調度算法”與本文算法進行對比分析。

本文通過2 種實驗對算法的安全性進行對比，實驗分別為碰撞實驗和大數裁決系統攻擊實驗。其中碰撞實驗由文獻[14]提出，其核心思想是通過對攻擊原子和防御原子的碰撞率來衡量系統的安全性，碰撞率越高系統越安全，實驗步驟如下。

Step1等待池和運行池初始化。

Step2構造威脅輸入。

Step3進行動態調度，從等待池中選取異構執行體填入運行池。

Step4進行碰撞檢測和計數。

Step5返回Step2，重復進行多次實驗。

Step6計算平均碰撞概率。

Step7改變威脅數目，返回Step1。

本文對碰撞實驗進行改進，提出了LSA，實驗流程如圖4 所示。2 種實驗的對比實驗環境如表6所示。

表6 對比實驗環境

表6中，隨機部分裝載與隨機全裝載均為隨機裝載，區別在于部分裝載的執行體組成原子中可能會存在0 原子（無效原子）；全裝載的執行體組成原子均為非0 原子（有效原子）。威脅構造方式分為負反饋和隨機裝載2 種，區別在于隨機裝載為隨機選取攻擊原子進行裝載，而負反饋裝載會選取之前的系統攻擊結果中攻破概率最高的攻擊原子進行裝載。

仿真中相關實驗參數設定如下。

1)執行體調度為5 模異構執行體集，即每次從等待池中調度5 個執行體到運行池中。

2)執行體的防御/漏洞原子、威脅集均為隨機生成。

3)實驗采用蒙特卡羅方法進行測試，每種實驗環境下測試10 000 次，最后取均值表示實驗結果。

4)負反饋威脅實驗中威脅原子更新概率式與文獻[15]中相同，為

其中，P1和P2在碰撞實驗中分別表示發生碰撞和未發生碰撞的威脅原子被選中的概率，在LSA 實驗中分別表示未攻破系統和攻破系統的威脅原子被選中的概率；p為單次實驗中該威脅原子與防御/漏洞原子發生碰撞的概率。

實驗參數配置如表7 所示。

表7 實驗參數配置

本文實驗假設每次從等待池中調度5 個執行體（其中原子種類隨機生成）進入運行池中工作，因此設定運行池大小為5，等待池大小為20。在碰撞實驗中異構執行體容量參考文獻[15]中參數進行設置；在LSA 實驗中由于執行體中原子為漏洞原子，在通常漏洞發現的過程中，單一類型系統/軟件存在的漏洞數量應與同功能的系統/軟件發現的漏洞數量總數存在比例關系。因此在LSA實驗中，當威脅數大于100 時異構執行體容量設定為，其執行體容量變化如圖5 所示。實驗結構如圖6 所示。

圖5 LSA 實驗執行體容量變化

圖6 實驗結構

實驗程序用Python 編寫。為更好地量化實驗結果，碰撞實驗中用碰撞率表示威脅被系統防御的概率，碰撞率越高，代表系統防御能力越強；LSA 實驗中用系統攻破率表示系統被威脅攻破的概率，系統攻破率越低，代表系統越安全。

4.1.1 碰撞實驗

根據表5中的環境描述，在碰撞實驗中分別測試了執行體負反饋威脅下部分裝載、負反饋威脅下全裝載、隨機威脅下部分裝載和隨機威脅下全裝載4 種環境，得到的實驗結果如圖7和圖8所示。

從圖7和圖8 的實驗結果可以看出，在全裝載和部分裝載的環境下，HFAWA 都具有優于其他算法的防御效果，且這種優勢在威脅數較少時更明顯。而攻擊方式的改變會對系統的安全性產生一定威脅，但這種威脅主要體現在威脅數較少時碰撞率會有些許降低，威脅數較大時負反饋攻擊的碰撞率反而高于隨機攻擊的碰撞率，這與文獻[15]中的結論是一致的。

圖7 碰撞實驗下執行體全裝載

圖8 碰撞實驗下執行體部分裝載

由于在實際場景中，異構執行體間雖然擁有相同的層級數，但其具有的防御能力和漏洞類型/個數往往都是不同的，因此部分裝載的實驗環境更能體現實際場景中的效果。給出部分裝載環境下的詳細實驗數據，如表8和表9 所示。

表8 隨機攻擊碰撞試驗下執行體部分裝載實驗結果

表9 負反饋攻擊碰撞試驗下執行體部分裝載實驗結果

4.1.2 LSA 實驗

根據圖4 所示流程進行實驗，LSA 實驗中同樣測試了表5中描述的4 種環境，得到的實驗結果如圖9和圖10 所示。

圖9 LSA 實驗下執行體全裝載

圖10 LSA 實驗下執行體部分裝載

從圖9和圖10 的實驗結果可以看出，在LSA實驗中，HFAWA 依然保持著良好的防御能力。雖然在攻擊方式由隨機攻擊變為負反饋攻擊后，系統攻破率會有些許上升，但通過對比可以看出，受影響較大的是威脅數較少的情況（H2 算法受到的影響最大），隨著威脅數增大，攻擊方式的改變對系統攻破率的影響可以忽略。給出部分裝載實驗的詳細數據，如表10和表11 所示。

表10 隨機攻擊大數裁決下執行體部分裝載實驗結果

表11 負反饋攻擊大數裁決下執行體部分裝載實驗結果

4.2 算法性能測試

根據以上實驗參數配置，本文對5 種調度算法的運行時間進行仿真實驗，實驗環境如表12 所示。

表12 性能測試環境

實驗只測試算法在調度選擇過程的時間消耗，由于HFAWA、H2 算法中異構度數組的構建為前期準備工作，因此不將其算作算法時間消耗內。實驗測試每種算法調度10 000 次的時間消耗，詳細數據如表13 所示。

表13 算法時間消耗

在笛卡爾坐標系中繪制表13 所示實驗數據，如圖11 所示。

圖11 算法時間消耗

根據以上實驗結果，可以得到以下結論。

1)在碰撞實驗中，HFAWA 的碰撞率基本上高于其他算法。當威脅數較小時，HFAWA 優勢較明顯；當威脅數大時，HFAWA和FAWA 的碰撞率相近且高于其他算法。這是因為威脅數越大，異構體選擇防御原子相同的概率就越小。當威脅數趨近于無窮時，異構體間出現相同防御原子的概率為0，這時HFAWA 與FAWA 效果相同。

2)在LSA 實驗中，HFAWA 的系統攻破率始終低于其他算法。在異構體部分裝載環境下，使用HFAWA 的系統被攻破概率為0。這是因為在異構體部分裝載環境下，5 模執行體中極易存在3模相似度為0（異構度最大）的情況，這時根據高階異構度調度執行體的HFAWA 效果明顯優于其他算法。

3)由算法性能測試結果可明顯看出，HFAWA在威脅數少的情況下相較于其他3 種算法運行速度較慢，而較H2 算法更快。這是由于HFAWA 的時間消耗主要是算法中異構度數組的比較，這與運行池的大小有直接關系，與威脅個數關系不大，當威脅個數較大時這一消耗可以忽略。而相較于H2 算法中每次實驗都需要更新的歷史信息為二維數組，HFAWA 僅需對一維數組進行更新，因此HFAWA具有優于H2 算法的運行效率。

將以上實驗算法的防御能力和運行速度指標進行對比，結果如表14 所示。

表14 算法指標對比

綜上，HFAWA 能夠在保證系統安全的同時，不造成過高的系統開銷。

5 結束語

針對目前DHR 系統對異構度的考慮僅局限于二階層面，造成系統安全性不足且調度異構體缺乏動態性的問題。本文提出了HFAWA 調度算法，并通過對容斥原理進行擴展應用，給出了高階異構度的計算方式。仿真實驗驗證了HFAWA 具有良好的防御能力和運行速度。后續將基于本文所做工作，繼續優化執行體的調度算法，進一步提高系統安全性。