面向擬態云服務的異構執行體調度算法

普黎明，劉樹新，丁瑞浩，王凱

（信息工程大學，河南 鄭州 450002）

1 引言

在云計算產業蓬勃發展的大環境下，云安全問題已成為阻礙其發展的難題，未知漏洞或后門成為云安全中最主要的威脅。云計算本質上是在現有技術的基礎上建立的，已有技術的漏洞后門會直接轉移到云服務平臺上[1]，云服務提供商向用戶提供大量一致化的基礎軟件（如操作系統、數據庫和應用軟件等）資源，又加劇了漏洞后門向云端的聚集，帶來了大范圍的安全問題與服務隱患。

網絡空間擬態防御（CMD,cyber mimic defense）是國內團隊提出的改變網絡空間“易攻難守”游戲規則的技術，把擬態防御技術應用到云環境中構建擬態云服務，將大大增強系統的安全防御效能，大幅提升攻擊者的攻擊難度，增強云服務系統的安全性。擬態防御技術以動態異構冗余（DHR,dynamic heterogeneous redundancy）為核心架構，該架構由輸入代理、異構執行體池、輸出裁決器、控制器等組成。控制器根據調度、裁決等策略指揮系統各部件協同工作，在其控制下，輸入代理向異構執行體池進行請求分發，異構執行體池處理請求并向輸出裁決器發出響應，輸出裁決器對各執行體的處理結果進行判決產生唯一輸出[2-4]。其中，控制器對異構執行體池的調度對擬態系統的安全性有著重要的作用。目前，該技術已在存儲服務器[5]、Web服務器[6]、路由器[7]、SDN 控制器[8]、域名服務器[9]等領域得到應用。

傳統的異構冗余技術大幅提高了系統的可靠性和容錯能力[10-11]，應用比較廣泛，但缺乏動態性，不關注異構體調度，抗攻擊能力較DHR 技術弱[12-13]。擬態云服務系統需要綜合考慮執行體的動態、異構和冗余特性，通過調度機制達到三者之間平衡互補[6]。文獻[14]提出的最長相異性距離組件選擇算法和最佳平均相異距離的軟件組件選擇算法主要從空間維度討論相異性，解決容錯設計中軟件組件的選擇問題，但沒有考慮動態情況。文獻[15]提出的最大異構系統選擇算法只從時間維度給出共同漏洞指標，并沒有考慮空間維度的漏洞累積，而且也只選出執行體最大的異構集，動態性較差。文獻[16]利用復雜性和差異性從空間維度來描述異構性指標，其調度算法穩定性較好，但動態性不足。文獻[17]提出共同漏洞指標（CVI,common vulnerability indicator）量化系統相似度，其指標僅從時間維度考慮相似性，缺乏空間維度特性。文獻[18]提出異構功能等價體調度模型，從空間層面來度量相似性，并據此提出隨機種子最小相似度（RSMS,random seed and minimum similarity）算法，該算法兼顧動態性和可靠性，但其動態性和種子可選集容量強相關，當種子可選集較小時動態性不足。

本文首先基于相似性指標定義了執行體調度指標，從時空維度對執行池相似性進行建模；然后根據該指標提出執行池調度方案以及基于優先級和時間片的執行池調度（PSPT,pool scheduling based on priority and time slice）算法；最后通過實驗和分析對PSPT 算法和RSMS 算法的動態性、相似性和耗時進行比較，討論算法的綜合性能。

2 執行體調度指標

異構執行體調度指標需要綜合考慮異構性和動態性，執行池變換得越快，異構性越好，系統越安全。本文通過對執行體的相似性評估來反映其異構性指標，相似性和異構性成反比，且相似性的評估方法較成熟，同時通過策略控制調度得到動態性。

2.1 擬態云服務

擬態云服務（MCS,mimic cloud service）是網絡空間擬態防御技術的一種應用，其構造如圖1 所示。根據擬態防御原理及DHR 架構，MCS 構造主要包括調度集、執行池、服務代理、控制器。其中調度集是多個功能等價的異構執行體集合實體，圖1 中表示為虛擬節點；執行池是MCS 的功能執行單元，池中虛擬節點實際上映射到調度集中對應的節點，它是調度集的一個邏輯映射單元，不同的節點組合可以映射出不同的執行池；服務代理負責接收并向執行池分發用戶請求，對返回的多個響應進行多模裁決并輸出；控制器通過配置分發與裁決策略指揮服務代理工作，通過調度策略管理執行池和調度集映射關系。

執行池虛擬節點的數量稱作執行體冗余度，簡稱余度。余度可根據實際情況調整，控制器在給定余度的條件下保持執行池的動態性和異構性。動態性可增加系統的不確定性，減少同種攻擊連續成功的概率，提升漏洞和后門的利用難度[6]。異構性可增加系統的穩健性，并減少多個執行體同時存在共同漏洞和后門的概率，進而降低擬態逃逸的概率[2]。因此，執行池調度策略及算法的優劣直接決定了MCS 的安全性。

圖1 擬態云服務構造示意

圖1 是在余度為3 的條件下，由虛擬節點2、3、5 組成執行池時的擬態云服務構造示意圖。當余度變化時，執行池的虛擬節點數量也變化，但結構維持不變；執行池虛擬節點和調度集虛擬節點的邏輯映射關系由控制器通過調度策略來控制。

2.2 相似性指標

本文采用文獻[17]的共有漏洞指標表示執行體的相似性，即通過統計執行體共有漏洞的數量來表示相似程度，共有漏洞數多代表相似程度高，反之相似程度低，共同漏洞信息可以通過CVE（common vulnerabilities and exposures）數據庫得到。

定義1執行體。提供云服務實際功能的實體記為Executori，簡寫為Ei，其中i 表示第i 個執行體，在MCS 系統中稱為虛擬節點。

執行體由多個類別的構件組成，例如操作系統、數據庫、應用服務軟件這3 種構件組成一個應用功能實體，表示為Ei={Clp| l,p=1,2,3,…,n}，其中 Clp表示第l 類的第p 個構件。

同一個系統中，所有執行體的構件種類和數量是一致的。例如，所有執行體的第一種構件是操作系統，第二種是數據庫，以此類推。若一個執行體由3 種構件組成，則其他執行體也同樣由這3 種構件組成，但每個種類的構件數量可能是不一樣的，例如某系統中操作系統構件只有Windows 2012，數據庫構件有MySQL、Oracle、SQL Server 等。

定義2調度集。系統中所有功能等價的執行體集合記為 E={ Ei| i=1,2,3,…,n}，調度集中所有的執行體統一編號，即i 表示編號，n 表示執行體數量，該集合中的執行體是控制器備選的調度對象。

定義3執行池。執行池是MCS 系統DHR 架構的任務執行部件，系統中同一時刻在線工作的功能等價執行體集合記為P={ Ei|1≤i ≤ n}，且| P |=r，其中r 表示執行體的余度，考慮到輸出時多數一致裁決原則對執行體數量的要求，取3 ≤ r ≤n，即執行池至少要有3 個執行體。由定義可知，P ?E 表示執行池的執行體由控制器從調度集中調入。

考慮到組成執行體的構件隨時間在不斷發展變化（例如，Windows 已經從最初的3.1 版本發展到如今的Windows 10），其漏洞的種類和數量也發生了變化，可能會變得越來越多，或者越來越少。因此，在選擇執行池配置時應考慮時間維度，例如，相比最近出現較少漏洞的執行體可能會有更好的安全性，最近共有漏洞較少的執行體集也會有更好的異構性；最近出現的漏洞威脅較高，時間權重配置高一些，較早出現的漏洞威脅較低，時間權重配置低一些。

定義4時間權重因子[17]。定義為

其中，i ∈ {y-years +1,…,y-2,y-1,y}；y 表示年份（例如2019 年，則y=2019）；years 表示參與漏洞統計的年數，至少為1 年，通常不會有使用超過10 年的構件版本。由式(1)可知，在若干年時間內，越接近y 權重越大，y 的時間權重因子取值為αy=1。α 因子從時間維度考慮了構件歷史漏洞的重要程度，也可理解為攻擊者利用歷史漏洞的可能性。

定義5空間權重因子。執行體由多個類別的構件組成，從系統結構角度看是多個空間層次的構件組成，例如通常所說的存儲層、計算層、服務層，或者硬件層、系統層、應用層等。每個層次（類別）的構件在執行體整體安全性中的重要性是不一樣的，對于應用型服務來說，攻擊者能直接攻擊的目標必然是最頂層的應用服務軟件，比如Web 服務，該層構件的安全性直接決定了執行體的整體安全性，因此該構件的空間權重應設置較大。定義為

其中，tiers ＞ 0表示組成執行體的構件層數，例如由存儲層、計算層、服務層組成的執行體tiers=3；l ∈{1,2,3,…,tiers}表示第l 層的構件，取值由底層向頂層遞進，底層的構件l=1，頂層的構件l=tiers。

由定義5 可知，底層構件的空間權重因子β 取值最小，頂層構件的空間權重因子取值為βl=tiers=1。β 因子從空間維度考慮了各層（類）構件的重要程度，也可理解為攻擊者利用該構件攻擊的可能性。

定義6構件共有漏洞指標。同一種類的構件對 Clp和 Clq的共同漏洞數記為 vi(A,B)，其定義為

式(3)表示第l 類構件對第p 和q 號構件在y 年的共有漏洞指標，該指標從時間維度考慮了最近years年的構件共有漏洞情況，在一定程度上也可由歷史表現反映或預測未知漏洞的部分情況。共有漏洞數量越大，CVI 越大，構件越相似，反之異構性越小。

定義7執行體共有漏洞指標。結合定義1 和定義5 可以得到執行體對的CVI，表示為

其中，Clp∈Ej,Clq∈ Ek，l 表示層次（或類別），tiers表示組成執行體的構件層數。該指標從空間維度考慮了執行體的共有漏洞情況。

執行體CVI 物理意義如圖2 所示。

圖2 執行體CVI 物理意義

從圖2 中可看出，執行體CVI 從橫向角度表示構件對（j 號執行體的某層p 號構件和k 號執行體的同層q 號構件）之間的共有漏洞指標，該指標回溯了最近若干年的共有漏洞情況，體現了時間維度特性；從縱向角度表示執行體對的共有漏洞指標由各層構件對（從第一層到第tiers 層）的CVI 累計得出，并考慮了各層的重要性程度，體現了空間維度特性。

定義8執行池漏洞指標。定義為

其中，j ＜ k且1≤ j ≤r-1,2≤ k ≤ r，r 表示該執行池的余度，j、k 表示執行體在當前執行池中的編號。該指標表示執行池中執行體對CVI 的平均值。

3 執行池調度算法

對于給定的構件集，其組成的調度集顯然是確定的，滿足r 余度要求的執行池數量也是確定的，即從調度集中構建r 余度執行池的數量是確定的。當構件集發生變化（新增或減少構件）時，調度集和執行池也隨之變化，但直到構件集下一次變化之前，調度集和執行池是確定的。此外，由于CMD負反饋機制等原因引起執行體下線或清洗，也會改變執行體集和執行池。因此，構件集、調度集和執行池在總體上具有不確定性，是動態變化的，但在一定的時間片內是相對確定的。執行體的調度是在一定的條件下啟動的，例如構件集變化了，可能有更好的相似性組合，可以調入該組合；執行體下線了，引起執行池的變化，需要調入一個執行體；動態策略觸發，需要調整執行池等。

不論何種原因觸發調度，系統都可以預先準備好執行池調度方案，這比在觸發時再計算相關方案能夠得到更好的調度效率。因此有如下定義。

定義9調度方案。調度方案是以CVIy(P)升序排列的執行池集合，記為F={Pi| i=1,2,…,N}，其中P 表示執行池，i 表示排序后的序號，i 值越小表示該序號的執行池相似度越小，即CVIy(P)越小，該執行池將優先調度，即序號就是調度優先級。

通常情況下，對于給定余度的執行池，應選調CVIy(P)較小的執行池，但執行池內的執行體之間可能存在局部極值的情況[2-3]，雖然平均相似度較小，但某一對執行體的相似度比較大，它們的共有漏洞被攻擊成功的概率相對較高。調度方案應考慮這種情況，可設置一個相似度閾值，如果執行池中存在超過閾值的執行體對，則降低該執行池優先級，放入方案末端，也可以根據策略刪除該執行池。

定義10相似度閾值。記為threshold，一般情況下threshold 取值應大于執行體CVI 的平均值，且應小于最大值，具體取值可根據經驗調整。

對于執行體數量為n 的調度集（已根據構件的兼容屬性配置好執行體），以r 余度構建執行池，可以構建出包含個執行池的列表，記作PoolList。系統在啟動時，或在執行體下線及上線后，新的調度任務還未觸發前，分別計算出個執行池的CVIy(P)值，并按照前文原則排序得出調度方案F，此時調度方案F 就是排序后的PoolList，同時可知調度方案F 已經包含了r 余度下所有可能的執行池。調度方案生成算法偽代碼如算法1 所示。

算法1調度方案生成算法

輸入調度集E，余度r，相似度閾值threshold，調度策略Policies

輸出調度方案F

在系統執行過程中，若因安全原因下線執行體，則需選調另一個不包含該執行體的執行池；另外，考慮到穩定性要求，通常會選調包含當前執行池中非下線執行體的執行池，以減少更換的執行體。若是動態策略觸發調度操作，為保障良好的動態性和較長的調度周期，只需選調下一優先級的執行池，按照調度方案F 循環調度。執行體下線和上線以及余度r 變化會引起執行池的變化，在本次調度完成之后，需要使用算法1 重新生成調度方案，但不會立即觸發調度操作；動態策略觸發調度操作不會使調度池變化，不需要重新生成調度方案。

定義11時間片策略。對于策略觸發的調度，系統根據方案優先級順序給出一個調度時間間隔，稱為時間片，記為TF={ti| i=1,2,…,N}，其中 TF表示調度方案F 的時間片策略，ti表示方案中第i 個執行池的時間片。優先級高的調度間隔長，反之調度間隔短，以此在受控條件下平衡動態性和異構性要求，使之達到互補。系統根據時間片策略調用算法2 對執行池進行動態調度，該算法稱為PSPT 調度算法。

算法2PSPT 調度算法

輸入當前池序號cp，調度方案列表PoolList，下線執行體Edown，是否策略觸發isPolicy

輸出當前執行池序號

4 實驗分析

本節對調度算法進行實驗和分析，把PSPT 算法與文獻[18]提出的RSMS 算法對比，測試算法的動態性、平均相似度、耗時等效果。實驗設備采用Thinkpad T480 筆記本電腦，配置為Intel Core i7 1.80 GHz CPU和16 GB RAM，軟件系統采用Ubuntu Linux 版本18.04LTS 和JDK 12.0.1，工具為Java 和Python。

根據文獻[6,19]對余度與成本及安全增益的關系分析可知，余度為3 的執行池實用性較好，且可以達到最佳折中效果。因此，本文實驗主要以余度為3 的執行池開展。

4.1 算法動態性比較

算法的動態性體現在調度方案的重復周期，理想的動態性是調度的方案盡量不重復，但受于可選異構執行體和余度的限制，調度方案實際上是一個有限集合，方案在調度過程中必然會出現重復，重復的平均周期越長，動態性越好。

分析RSMS 算法可知，該算法的動態性主要由隨機函數來體現，當隨機函數選中種子執行體時，該種子對應的執行池也就確定了，也即調度方案和種子是對應的，方案的調度周期等效于種子執行體重復出現的周期。而PSPT 算法的調度周期由調度方案列表的長度決定，對于給定的調度集，調度方案長度是確定的，該長度值為，其中n 為調度集的執行體個數，r 為執行池余度。

實驗對100 個執行體的調度集進行算法調度測試，執行池余度設為3，假設執行體被調度的概率相同。為簡化分析聚焦周期測試，暫不考慮相似度閾值，加入相似度閾值因素后，可選范圍會縮小，2 種算法的平均周期值都會有所降低，即動態性會變差。每個算法進行100 次實驗，出現重復方案時按一次計算。實驗結果如圖3 所示，其中周期表示的是調度次數，粗虛線表示周期的平均值。

圖3 算法周期測試

分析圖3 可知，RSMS 算法的調度周期符合隨機函數特點，取值比較發散，平均周期約為100；PSPT 算法的調度周期實驗值符合算法預期值=161 700，該算法的周期固定為161 700，平均周期約是RSMS 算法的1 617 倍。實驗結果與前述分析一致，PSPT 算法的動態性大幅優于RSMS 算法。

4.2 算法相似度比較

RSMS 算法選中種子執行體時，也就確定了執行池，換句話說，對于給定的100 個執行體的調度集，只有100 個可能的種子，對應可選中的就是100 個可能的執行池，而每個執行池都有CVI 值。因此，為簡化實驗，聚焦算法的隨機特性帶來的相似度變化，在給定余度條件下，本文在執行池CVI 最小值和總平均值（調度集所有執行體組合的平均CVI 值）之間隨機給出100 個執行池作為RSMS 算法的可選集，PSPT算法的可選集為=161 700 個；假設余度為3 的執行池CVI 值服從參數為[5,15]的β 分布[18]，則概率密度曲線和對應的執行池CVI 值分布如圖4 所示。

圖4 實驗數據CVI 值分布特征

圖4 中CVI 數據總平均值為249.7。考慮到RSMS 算法每個周期的調度次數有很大不同（見4.1節分析），為得到較好的平均數據，進行100 個周期的調度實驗并計算CVI 平均值；PSPT 算法每周期的調度次數相同，而且一個周期即可覆蓋方案中所有的執行池，該算法進行一個周期的調度實驗即可計算出平均CVI。

實驗 1不考慮閾值和時間片策略，余度r=(3,4,5)，測試調度算法得到方案的平均相似度。實驗結果如表1 所示。

表1 不同算法的調度方案平均相似度

由表1 可知，RSMS 算法的平均相似度隨余度增加而增加；PSPT 算法的平均相似度不隨余度變化，維持在總平均值。當余度較小時，RSMS 算法的平均相似度大幅優于PSPT 算法，隨著余度的增加差距逐漸減小，當余度增加到等于執行體數量時，平均相似度將趨于一致。

實驗2不考慮閾值，將余度設為3，針對PSPT算法啟用時間片策略并測試單位時間內的平均相似度。時間片策略數據如下：基準時間片取10 個單位時間，調度方案F 列表以為界，后半部分順序取值區間為[10,100]，前半部分順序取值區間為[100,10K]，其中K={10,20,30,…,200}，方案F 從該區間中由大到小獲取時間片，實驗結果如圖5 所示。

圖5 單位時間CVI 值隨時間片策略變化關系

從圖5 可以看出，隨著K 值增大，單位時間內CVI 值快速減小，逼近表1 中RSMS 算法的平均值。經分析可知，因為調度方案前半部分的執行池CVI值較小，增大該部分時間片將會在一段時間內降低CVI 值，該段時間內執行池的相似性較低，但動態性有所損失。實際應用時可根據情況設置合適的時間片策略，獲得異構性和動態性的平衡，進而得到較好的安全性。

實驗3不考慮時間片策略，將余度固定為3，調整相似度閾值，測試相似度閾值對算法平均相似度的影響。實驗結果如圖6 所示。

圖6 不同算法平均相似度隨相似度閾值變化關系

從圖6 中可以看出，隨著相似度閾值的減小，RSMS 算法的平均相似度變化不大，當相似度閾值低于總平均值249.7 時，平均相似度快速減小；PSPT算法的平均相似度隨相似度閾值快速減小。經分析可知，當相似度閾值減小時，PSPT 算法快速過濾掉相似度較大的執行池，使獲得的方案列表縮短，平均相似度降低，調度周期也變短；當相似度閾值低于總平均值時，RSMS 算法也會較多地過濾掉可選方案，使平均相似度快速下降，同時調度周期也縮短。實際應用時，因前者的平均相似度由算法本身決定，不易附加干預手段，需要控制好余度的選取，以達到成本和相似性的平衡，余度過高會增加成本。后者需要控制好閾值選取，以取得較好的平均相似度且平衡動態性要求，且后者受策略控制較大，可根據實際經驗干預并調整策略。

4.3 算法耗時比較

調度算法的執行，大多是由策略驅動的，執行體下線或上線引發的調度是少數。因此，實驗只考慮策略驅動的調度操作，聚焦算法本身的耗時比較。考慮到算法耗時主要受到調度集規模的影響，通過增加2 種算法的調度集規模來測試耗時情況，調度集規模設為3～1 000，對每個規模調度集分別測量算法的CPU 耗時。實驗結果如圖7 所示。

圖7 調度規模耗時情況

由圖7 可以看出，RSMS 算法耗時隨規模總體呈線性增加，PSPT 算法耗時基本維持不變。經分析可知，RSMS 算法主要由循環語句產生耗時，該語句循環次數與規模直接關聯，時間復雜度為O(n)；PSPT 算法處理的數據已經過排序處理，可直接按序取出，耗時與規模無關，時間復雜度為O(1)。PSPS 算法能夠穩定維持較低的時間成本和較小的調度時延，優于RSMS 算法。

5 結束語

擬態云服務是網絡空間擬態防御技術的一種應用，執行體的調度機制是其關鍵技術，本文針對調度機制給出包含時空特性的執行體調度指標，以此提出一種基于優先級和時間片的執行池調度算法PSPT，該算法在動態性和時間成本上優于RSMS 算法，配合時間片策略也可在相似性上接近RSMS 算法，且在滿足冗余性基礎上可以兼顧動態性和異構性。后續考慮對服務代理接收執行體返回值的網絡時延情況進行研究，據此優化調度方案和算法。