面向擬態安全防御的異構功能等價體調度算法

劉勤讓，林森杰，顧澤宇

?

面向擬態安全防御的異構功能等價體調度算法

劉勤讓，林森杰，顧澤宇

（國家數字交換系統工程技術研究中心，河南 鄭州 450001）

擬態安全防御的一個關鍵環節是異構功能等價體的調度，現有的調度策略缺乏對冗余體間相似度的考慮，且調度算法較為單一。基于此，提出了一種兼顧動態性和可靠性的異構功能等價體調度算法——隨機種子最小相似度算法，首先隨機確定種子冗余體，然后再根據相似度指標選擇整體相似度最小的最終調度方案。理論分析和仿真實驗表明，該算法的調度周期遠高于最長相異性距離算法，而失效率遠低于隨機調度算法，在動態性和可靠性之間達到了較好的平衡。

擬態安全防御；異構冗余調度；相似度；隨機種子

1 引言

隨著網絡設備和服務的不斷發展和普及，人們對網絡空間的依賴性越來越強，而網絡安全的重要性也越發凸顯。傳統的網絡空間領域中，完成特定服務功能的設備和裝置（包括軟硬件）對外表征的屬性是靜態的、確定的，且與其內在結構之間存在強相關的對應關系，攻擊者通過對其表征內容的收集與分析，可以在一定程度上掌握有關設備和裝置內部的具體信息，并可能發現可利用的漏洞或缺陷。另一方面，攻防雙方的不對稱性導致防御方十分被動，且需要為防御未知的、不確定的攻擊行為付出高昂的代價。

擬態防御作為一種轉變網絡安全格局的新思想，通過構建動態異構冗余的系統架構和運行機制實現針對特定系統漏洞或后門的入侵容忍[1-3]。在擬態防御系統中，冗余控制器接收外部控制參數，生成冗余調度策略和結果仲裁策略，分別發送給輸入代理器和輸出代理器，輸入代理器依據接收到的冗余調度策略選擇相應的異構功能等價體響應外部服務請求，異構功能等價體將結果發送至輸出代理器，輸出代理器根據冗余控制器生成的結果仲裁策略對各個結果進行判決，最終選擇一路作為響應輸出。擬態防御系統架構如圖1所示。

圖1 擬態防御系統架構

傳統的容錯調度本質上還是為確定的處理機調度任務[4-7]，而擬態調度要求對任務調度不確定的冗余體。現有的多模冗余調度主要從可靠性的角度考慮任務執行體[8-10]。文獻[11]提出了一種隨機調度策略，采用完全隨機的調度策略降低攻擊者對特定系統漏洞或缺陷的利用，冗余控制器根據外部控制參數隨機確定異構功能等價體的數量和編號，輸入代理器根據生成的調度策略分配異構功能等價體響應外部服務請求。文獻[12]分別從可信度和性能權重2個方面考慮冗余體的調度問題，通過構建異構冗余池中功能等價體的可信度屬性值和性能權重屬性值，對權值越高的冗余體賦予更高的調度可能性，但沒有考慮2種方案的綜合性能。這些調度策略從不同的角度考量異構體受到調度的合理性，但不夠全面。

異構功能等價體作為系統響應外部服務請求的功能主體，其關鍵特征在于“異構”，“異構”是功能等價體規避攻擊者嗅探和利用系統漏洞缺陷的基礎。現有的冗余體調度策略將異構冗余池內的等價體認為是相互獨立的個體，沒有考慮等價體之間的相似程度。實際上，由于功能的等價，各異構體之間也不可能做到完全相異，且相互之間的差異也有大小之分，故異構度小的幾個等價體之間存在漏洞或缺陷交集的可能性較大。由于現有的擬態判決策略以多數一致性判決為主，若產生的調度策略選擇了相互之間異構度較小的功能等價體集，則攻擊者可以利用這些可能存在的漏洞缺陷交集進行攻擊，得到多數一致的錯誤結果，進而通過仲裁得到錯誤輸出。文獻[13]提出了2種相異性組件選擇算法，分別是最長相異性距離（MD, maximum dissimilarity）算法、最佳平均相異距離（OMD, optimal mean dissimilarity）算法。其中，MD算法選擇相異距離最大的組件構成相異性系統，算法得到的是一個確定的全局最優解，對于異構組件較多的系統，算法復雜度較大，且在應用中相當于構成一個靜態的異構冗余系統，缺乏動態性，并不適合擬態系統；OMD算法選取相異距離近似的組件構成相異性系統，避免了局部最大值對組件選擇的影響，但并不能保證得到異構度最大的組件集合。

本文首先提出通用擬態安全防御的異構功能等價體調度模型，該模型充分考慮了執行體之間相似度對系統性能的影響，同時定義了相似度指標，將調度方案的相似程度進行量化，然后在此基礎上提出了一種兼顧動態性和可靠性的調度算法——隨機種子最小相似度（RSMS, random seed & minimum similarity）算法，最后通過理論分析和仿真實驗對該算法和現有算法的調度周期和失效率進行比較，觀察算法的綜合性能。

2 異構功能等價體調度模型

考慮一個通用擬態防御系統的異構冗余池，符號表示如表1所示，并由以下定義進行形式化描述。

表1 符號表示

對于一個異構冗余池，其組件成分可根據具體擬態邊界和功能模塊劃分，考慮到成本和功耗因素，組件類目數量總是有限的。

雖然對組件的類目進行了劃分，但同一組件的各類目并不是完全孤立的，實際上，一個組件代表一個功能模塊，由于功能的等價，各類目之間總存在一定的相似程度，即可能存在相近甚至相同的漏洞和缺陷為攻擊者所用，故冗余體的調度需要考慮組件類目之間的相似程度。

定義4 冗余池中具有個類目的第個組件的特征相似矩陣為

3 相似度指標

現有的冗余體調度方案常以調度個體的可靠性作為主要的調度指標，但系統的可靠性并不是個體可靠性的簡單疊加。考慮一個冗余系統A，每個子系統具有較高的可靠性，但各子系統十分相似，漏洞相近，針對整個系統的攻擊成本與單個子系統的攻擊成本相差無幾；而另一個冗余系統B，雖然每個子系統可靠性較A中的子系統低，但子系統間異構度較大，難以找到相似的漏洞，由于存在仲裁機制，攻擊難度呈幾何倍數增加。故從安全性的角度看，冗余體之間的異構程度是評價冗余體調度方案的重要指標。文獻[14]對計算機系統的異構性進行了描述，但“異構”是發散的，與某個冗余體相異有多種形式，而“同構”是收斂的，故本文采用“相似度”作為衡量冗余體間差異的指標。相似度指標定義如下。

定義6 冗余體間的相似度等于各組件之間相似度的加權和，即

定義7 組件相似度由對應的特征向量和特征相似矩陣點乘得到，即

4 隨機種子最小相似度算法

擬態調度的動態性導入可以有多種形式，例如，對一個確定的有限冗余池枚舉出所有可能的冗余體集合，為達到動態性和可靠性的折中，選擇其中相似度最小的若干個冗余體集合作為調度方案集合，再根據既定策略（如輪轉、彩票、隨機等）進行調度。這種方法較為直觀且易于實現，但不適用于不確定的、動態變化的冗余池，由于擬態防御存在負反饋機制，若異構冗余體因故障下線或強制清洗，調度方案集合可能受到影響，嚴重時甚至無法提供正常服務。

本文提出一種隨機種子最小相似度算法，算法原理如下。首先，在正常工作的異構冗余體中隨機確定任務執行余度和一個種子冗余體，為擬態調度引入動態性（種子冗余體包含于調度方案中），然后根據最小相似度原則選擇整體相似度最小的調度方案。

式(5)結合調度向量、特征向量和特征相似矩陣，給出了具體調度方案的相似度指標，直觀上考慮，理想的調度方案是選擇符合余度條件且使整體相似度最小的若干冗余體作為任務執行體，但仍存在一個問題：整體相似度最小的冗余體集合可能并不是最合適的調度方案，以下舉例說明這種情況。

圖2 2種調度方案示意

算法的具體流程如下。

1) 隨機確定執行余度和種子冗余體

2) 排除與種子冗余體相似度超過閾值的冗余體

3) 生成初步調度方案集合

4) 確定最終調度方案

計算初步調度方案集合中各元素的整體相似度，取其中整體相似度最小的作為最終調度方案。

算法偽代碼如算法1所示。

算法1 RSMS算法

//排除不符合相似度要求的冗余體

7) end if

8)end for

11) restart

12) else

//生成初步調度方案集合//

19) end if

20) end for

//確定最終調度方案

22) restart

26) end if

27) else

29) break

30) end if

31) end if

32) end if

5 算法性能分析

相對于MD算法和OMD算法，RSMS算法每次確定的冗余體集合是不確定的，同時具備隨機調度算法缺乏的相異性考慮，達到了二者的折中，下面對RSMS算法、隨機調度算法、MD算法和OMD算法的動態性和可靠性進行理論分析。

5.1 動態性分析

算法的動態性體現在調度方案的平均周期。理想的動態性要求調度方案完全不重復，這在無限余度冗余池中才能實現，事實上，由于余度的限制，調度方案必然存在重復的情況，進而存在一個平均調度周期。而只要冗余池確定，則MD算法和OMD算法得出的調度方案都是確定的，即周期為1。以下通過理論推導隨機調度算法和RSMS算法的平均調度周期來比較二者的動態性。

幾個基本假設如下。

假設2 由于RSMS算法的執行余度是隨機確定的，本文假設隨機調度算法也隨機確定余度。

假設4 為簡化分析，暫不考慮相似度閾值。

故RSMS的總體調度周期為

接下來分析調度方案動態性對系統安全性的影響。

假設攻擊者實施攻擊是基于先驗系統信息的，先驗信息越多，則成功概率越高，為便于分析，做出如下假設。

假設5 攻擊者在一個任務執行周期中可進行一次探測。

假設6 若一次探測所得信息與先驗信息矛盾，則先驗信息失效，反之則先驗信息累積。

假設8 不同調度方案的特征信息不相同。

5.2 可靠性分析

系統能否在偶然或惡意的失效情況下連續、可靠、正常地執行是擬態防御首要考慮的問題。在擬態調度環節，各冗余體的可靠性是系統可靠性的基礎，但不同的調度策略決定了系統可靠性的構成。

圖3 不同算法下攻擊成功概率與探測次數的關系

將調度算法的可靠性定義為系統執行任務后得到正確輸出的概率，通過計算隨機調度算法、MD算法、OMD算法、RSMS算法下系統正常工作的概率，分析各種算法理論上的可靠性。

為簡化分析，只考慮失效發生在異構冗余體內的情況，并做出以下假設。

假設10 由于系統的整體可靠性還與擬態仲裁環節相關，以最具代表性的多數一致性表決作為仲裁策略，即選擇超過半數的一致結果作為系統輸出，當所有執行體的結果不能達到多數一致時，則輸出異常。

其中，為常系數，同一余度條件下，若方案整體相似度越高，則出現相同錯誤結果的可能性越大。出現相同錯誤結果的可能性與相同錯誤結果數量呈指數關系。

假設12 輸出異常不認為失效，異常后系統重新執行當前任務。

進而推導出4種算法下系統正常工作的概率如表2所示。

表2 4種算法下系統正常工作的概率

6 仿真實驗

本節將RSMS算法和隨機調度算法、MD算法和OMD算法的性能進行比較，在不同異構體余度和執行余度條件下比較算法的動態性和可靠性，并通過仿真數據對算法總體性能進行分析驗證。

6.1 動態性比較

給定模擬冗余池，余度為9，冗余體間的相似度以參數為(5,15)的分布隨機生成[15]，如圖4所示，得到如下相似度矩陣。

文獻[16]分析了擬態處理機執行余度與安全增益的關系，結論為：余度為3的系統可以達到最佳的折中效果，故本次實驗只考慮執行余度范圍=(3,4,5)的情況。根據第5節的分析，對于不同的執行余度，4種算法的平均調度周期、算法確定的調度方案的平均相似度如表3和表4所示。

圖5 RSMS算法和隨機調度算法的調度周期仿真結果

表3 4種算法的平均調度周期

表4 算法確定的調度方案的平均相似度

下面針對RSMS算法和隨機調度算法以蒙特卡洛法進行100次模擬實驗，觀察各算法的調度周期。在不斷的模擬調度中，若產生與第一次調度結果相同的結果，則一次實驗結束，調度周期為總的調度次數減1，得到實驗結果如圖5所示。

圖5中虛線為各次實驗結果的平均值。從圖5可以看出，實驗結果與理論分析十分吻合，隨機調度算法的平均調度周期最大，RSMS算法次之，而MD算法和OMD算法基本沒有動態性； RSMS算法的平均調度周期為15.884 5，是MD算法的5.3倍。RSMS算法雖然在動態性上不如隨機調度算法，但在余度為3、4、5時，其平均相似度分別降低了43.08%、33.35%、24.94%。

6.2 可靠性比較

算法 RSMS算法7.190 9×10?42.365 6×10?59.210 3×10?5 隨機調度算法0.002 28.022 7×10?51.813 4×10?4 MD算法3.675 1×10?41.335 0×10?56.443 7×10?5 OMD算法0.001 38.450 3×10?51.677 2×10?4

由表5可以看出，RSMS算法的調度方案平均失效率在4種算法中只略高于MD算法，且遠比隨機調度算法低，其可靠性相對較高。

算法 RSMS算法2.766 4×10?43.806 4×10?62.574 5×10?5 隨機調度算法7.664 7×10?41.515 2×10?53.518 6×10?5 MD算法1.141 9×10?48.876 5×10?76.782 0×10?6 OMD算法3.598 9×10?41.058 3×10?51.118 2×10?5

由表6可以看出，RSMS算法的調度方案平均失效率仍然遠低于隨機調度算法，改變失效率向量后，計算結果仍有相同的規律。

由于MD算法和OMD算法確定的調度方案是唯一的，故對RSMS算法和隨機調度算法進行100次模擬調度實驗，計算各次調度結果的失效率，得到的仿真結果如圖7所示，可見實驗結果與理論分析十分吻合。

圖6 不同失效率向量下4種算法的平均失效率

從表6和圖6可以看出，MD算法的可靠性最高，RSMS算法次之，隨機調度算法和OMD算法最低。其中，當余度為3、4、5時，RSMS算法調度方案的平均失效率比隨機調度算法分別低67.32%、70.51%、49.21%。

通過分析和仿真實驗對比4種算法的動態性和可靠性這2個方面的性能，得到4種算法的性能排序，如表7所示。

表7 4種算法的性能排序

從圖7可以看出，隨機調度算法和MD算法各有側重，而RSMS算法兼顧了兩者的優點。RSMS算法通過對異構體之間相似度的考慮，降低了調度方案因發生共因失效而造成錯誤輸出的概率，同時兼具隨機調度的動態性優點，在動態性和可靠性之間達到了較好的平衡。

圖7 RSMS算法和隨機調度算法的失效率仿真結果

7 結束語

擬態防御是改變現有網絡安全格局的新思想，而異構功能等價體的調度是其中的關鍵環節，本文針對擬態防御系統的調度環節，提出了異構功能等價體的調度模型以及調度方案的相似度概念和計算式，并針對調度方案的相似度提出了一種擬態調度算法——隨機種子最小相似度算法。通過對算法調度周期和失效率的理論分析和仿真實驗，證明RSMS算法兼顧了動態性和可靠性。冗余體的可靠性有多種定義方式，并且可能在進程中不斷變化（例如，引用冗余體的歷史記錄），而這種情況下RSMS算法也可適應。

理論上，RSMS算法在動態性和可靠性這2個方面的權重是可以調整的，這與安全性的定義有關，有待后續研究。

[1] 鄔江興. 網絡空間擬態防御研究[J]. 信息安全學報, 2016, 1(4): 1-10.

WU J X. Research on cyber mimic defense[J]. Journal of Cyber Security, 2016, 1(4): 1-10.

[2] 扈紅超, 陳福才, 王禛鵬. 擬態防御DHR模型若干問題探討和性能評估[J]. 信息安全學報, 2016, 1(4): 40-51.

HU H C, CHEN F C, WANG Z P. Performance evaluations on DHR for cyberspace mimic defense[J]. Journal of Cyber Security, 2016, 1(4): 1-10.

[3] 仝青, 張錚, 鄔江興. 基于軟硬件多樣性的主動防御技術[J]. 信息安全學報, 2017, 2(1): 1-12.

TONG Q, ZHANG Z, WU J X. The active defense technology based on the software/hardware diversity[J]. Journal of Cyber Security, 2017, 2 (1):1-12.

[4] REIS G A, CHANG J, VACHHARAJANI N, et al. SWIFT: software implemented fault tolerance[C]//International Symposium on Code Generation and Optimization. 2005:243-254.

[5] WANG J, BAO W, ZHU X, et al. FESTAL: fault-tolerant elastic scheduling algorithm for real-time tasks in virtualized clouds[J]. IEEE Transactions on Computers, 2015, 64(9):2545-2558.

[6] 殷進勇, 顧國昌. 允許多處理機故障的實時任務容錯調度算法[J]. 電子與信息學報, 2010, 32(2):444-448.

YIN J Y, GU G C. A real-time fault-tolerant scheduling algorithm for multiple processor faults[J]. Journal of Electronics & Information Technology, 2010, 32(2):444-448.

[7] 彭浩, 陸陽, 孫峰,等. 副版本不可搶占的全局容錯調度算法[J]. 軟件學報, 2016, 27(12):3158-3171.

PENG H, LU Y, SUN F, et al. Faulttolerant global scheduling with non-preemptive backups[J]. Journal of Software, 2016, 27(12): 3158-3171.

[8] DAS A, KUMAR A, VEERAVALLI B. Reliability and energy-aware mapping and scheduling of multimedia applications on multiprocessor systems[J]. IEEE Transactions on Parallel & Distributed Systems, 2016, 27(3):869-884.

[9] 吉萌, 余少華, 詹翊春. 雙冗余結構路由器故障恢復模型與方案研究[J]. 通信學報, 2006, 27(6):21-28.

JI M, YU S H, ZHAN Y C. Research on fault-recovery model and scheme in dual-system redundancy router[J]. Journal on Communications, 2006, 27(6):21-28.

[10] CHEN C Y. Task scheduling for maximizing performance and reliability considering fault recovery in heterogeneous distributed systems[J]. IEEE Transactions on Parallel & Distributed Systems, 2016, 27(2):521-532.

[11] 鄔江興, 李軍飛, 等. 一種異構功能等價體調度裝置及方法[P]. 中國, CN106161417A, 2016-11-23.

WU J X, LI J F, et al. A heterogeneous redundancies scheduling equipment and method[P]. China, CN106161417A, 2016-11-23.

[12] 馬海龍, 伊鵬, 江逸茗, 等. 基于動態異構冗余機制的路由器擬態防御體系結構[J]. 信息安全學報, 2017, 2(1):29-42.

MA H L, YI P, JIANG Y M, et al. Dynamic heterogeneous redundancy based router architecture with mimic defenses[J]. Journal of Cyber Security, 2017, 2(1):29-42.

[13] 姚文斌, 楊孝宗. 相異性軟件組件選擇算法設計[J]. 哈爾濱工業大學學報, 2003, 35(3):261-264.

YAO W B, YANG X Z. Design of selective algorithm for diverse software components[J]. Journal of Harbin Institute of Technology, 2003, 35(3):261-264.

[14] 曾國蓀, 陳閎中. 探索計算系統異構性的描述[J]. 計算機科學, 2003, 30(12):16-18.

ZENG G S, CHEN H Z. Inquiring the description of heterogeneity among computational systems[J]. Computer Science, 2003, 30(12): 16-18.

[15] 吳奎, 周獻中, 王建宇,等. 基于貝葉斯估計的概念語義相似度算法[J]. 中文信息學報, 2010, 24(2):52-57.

WU K, ZHOU X Z, WANG J Y, et al. A concept semantic similarity algorithm based on bayesian estimation [J]. Journal of Chinese Information Processing, 2010, 24(2):52-57.

[16] 魏帥, 于洪, 顧澤宇, 等. 面向工控領域的擬態安全處理機架構[J]. 信息安全學報, 2017, 2(1):54-73.

WEI S, YU H, GU Z Y, et al. Architecture of mimic security processor for industry control system[J]. Journal of Cyber Security, 2017, 2 (1): 1-12.

Heterogeneous redundancies scheduling algorithm for mimic security defense

LIU Qinrang, LIN Senjie, GU Zeyu

National Digital Switching System Engineering and Technological Research Center, Zhengzhou 450001, China

The scheduling of heterogeneous redundancies is one of the key lines of mimic security defense, but the existing scheduling strategies are lack of consideration about the similarity among redundancies and the scheduling algorithms are incomprehensive. A new scheduling algorithm called random seed & minimum similarity (RSMS) algorithm was proposed, which combined dynamics and reliability by determining a scheduling scheme with minimum global-similarity after choosing a seed-redundancy randomly. Theoretical analysis and simulation results show that RSMS algorithm possessed a far longer scheduling cycle than maximum dissimilarity algorithm, as well as a far lower failure rate than random scheduling algorithm, which represents an effective balance between dynamics and reliability.

mimic security defense, heterogeneous redundancies scheduling, similarity, random seed

TP309

A

2017-12-25；

2018-03-29

國家自然科學基金資助項目（No.61572520, No.61521003）；上海市科研計劃基金資助項目（No.14DZ1104800）

The National Natural Science Foundation of China (No.61572520, No.61521003), Shanghai Research Project (No.14DZ1104800)

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

劉勤讓（1975?），男，博士，國家數字交換系統工程技術研究中心研究員，主要研究方向為寬帶信息網絡及芯片設計。

林森杰（1993?），男，廣東汕頭人，國家數字交換系統工程技術研究中心碩士生，主要研究方向為網絡主動防御。

顧澤宇（1993?），男，遼寧沈陽人，國家數字交換系統工程技術研究中心碩士生，主要研究方向為網絡主動防御。