擬態多執行體架構下的超時閾值計算方法

聶德雷，趙博，王崇，汪欣，燕昺昊

?

擬態多執行體架構下的超時閾值計算方法

聶德雷1，趙博2，王崇2，汪欣3，燕昺昊2

（1. 天津市濱海新區科技和工業創新委員會，天津 300000； 2. 國家數字交換系統工程技術研究中心，河南 鄭州 450002； 3. 天津濱海新區信息技術創新中心，天津 300000）

針對當前超時策略算法難以應對任務量起伏劇烈情況的問題，提出了一種應用于擬態防御架構系統的基于等效比例執行時間的超時閾值預測算法，利用擬態防御架構中多個功能等價執行體任務執行時間正相關的原理，預測任務執行時間并設置合理的超時閾值。仿真結果表明，所提算法能夠針對不同任務情況動態地預測并設定超時閾值，有效地提高了超時判決效率，尤其適用于任務量變化劇烈的場景。

擬態防御；閾值計算；多執行體；超時判決

1 引言

隨著網絡技術的不斷發展，網絡空間安全的重要性愈發凸顯。擬態安全防御是一種應對網絡攻擊威脅的新思想，其通過構建動態異構冗余的系統架構和運行機制實現“容侵”[1-3]。在擬態防御系統中，擬態調度器從異構冗余池內動態選擇多個異構功能等價執行體進行任務分配，各執行體將處理結果輸出給仲裁器進行仲裁，得到最終結果。

雖然異構功能等價體在設計過程中盡可能保持功能等價性能接近，但在實際環境中面對不同任務時，處理效率無法保證完全一致，故仲裁器需要等待所有執行體處理完畢并輸出結果才可進行一致性裁決。若存在某個執行體受到攻擊、非法操控或者隨機失效而無法產生有效輸出或任務執行時間顯著延長的情況，將導致仲裁器陷入長時間等待，甚至致使其他執行體無法繼續執行后續任務，不僅增加系統時間開銷，而且嚴重影響系統的正常運行。因此，在系統構建中引入超時機制來限制異構體執行任務的最長時間，這對于提高系統仲裁效率、保障系統正常運行具有重要意義。

針對超時機制問題，Ryu等[4]提出了一種基于測量的二進制指數超時（MBET, measurement- based binary exponential timeout）策略，令每個流的超時相互獨立，先設定一個足夠大的超時參數，然后在每個超時時間內觀測流吞吐量并調整超時參數（以2的指數形式遞減或維持不變），優點是可以快速得到理想的超時參數且實現簡單，但沒有對初始參數的設置進行討論，且不適用于吞吐量變化較大的場景。錢迎進等[5]提出了一種基于滑動時間窗口算法的自適應超時策略，利用滑動窗口算法得到各時間段內的服務時間歷史記錄，并預測下一階段的超時參數，其優點是超時參數可以根據擁塞情況動態調整，且有多種方案可以選擇，但沒有對擬合精度和效果進行深入討論。周明中等[6]提出了一種兩層自適應超時策略（TSAT），綜合固定超時和自適應超時的優點，對于不同特點的網絡流采用不同的超時策略，能有效提高系統效能，節省存儲空間，但實現起來較復雜。Claffy[7]提出了一種固定超時的實現方法，雖然可以取得較好的效果，但是不具有動態性和適應性。Fonti等[8]分析了在計算機中更新應用程序超時值的機制系統。侯穎等[9]通過自適應超時技術過濾器解決網絡空間擁塞問題。

通過分析發現，現有的超時機制都是使用單個處理單元或執行體，通過某種規則或計數器實現超時控制，其對超時閾值或處理時間的預測往往基于一個前提，即相鄰任務的任務量接近、任務執行時間變化趨勢可預測。然而在實際應用中，大量場景的任務量變化無規律可循，相鄰任務的執行時間也不具相關性，此時上述閾值預測算法性能會急劇下降。本文提出了一種新的超時閾值預測（EPET，equivalent proportional execution time）算法。EPET利用執行體功能等價性原理，通過歷史任務執行時間隊列來近似估算執行體間的處理效率，并以完成任務的執行體為基準，預測剩余執行體的執行時間并計算超時閾值。相比已有方法，EPET不僅能夠較好地應對前后任務差異較大的情況，適用于擬態防御環境，而且計算復雜度低，避免產生額外開銷。

2 基于多執行體的自適應超時閾值預測算法

2.1 EPET算法

當前已有的超時閾值算法只針對單執行體情況[10-11]，利用歷史任務的處理時間來預測下一任務的處理時間，并不適用于任務量變化劇烈、無規律可循的情況。擬態防御架構區別于普通系統架構的重要特征之一為包含多個異構功能等價體，存在一致性特征，即在構建擬態防御架構時選擇性能相近的功能等價體，以保證運行結果的無偏性，同時便于后續裁決過程。因此對于同樣的任務，多個異構執行體的處理時間較為接近，并與處理能力呈近似反比關系。進一步，在面對不同處理量的任務時，多個異構執行體的處理時間往往會呈現相同的增加或減少趨勢[12]。

因此，在EPET算法中，通過利用第一個完成任務的等價體的執行時間及各執行體間的執行時間等效比例，來估算其余等價體的執行時間。即

考慮到預測精度、系統負載以及傳輸延時等情況，最終選取的超時閾值需要對期望的任務執行耗時進行合理放大，避免由于超時閾值選取過小導致誤報率增大的情況。

其中，t為最終選取的超時閾值，為放大系數，依據應用場景的具體需求設定，取＞1。

進一步，EPET通過對每個執行體維護一個歷史任務執行時間隊列來計算各執行體的執行時間等效比例。

歷史任務執行時間隊列Q更新規則如下。

1) 若執行體為當前時刻第一個完成任務執行并輸出有效結果的執行體，則將執行體的實際執行時間t加入時間隊列，并將隊列中最遠時刻時間記錄移出隊列，此時，Q更新為

2.2 特殊性分析

本文針對擬態防御系統提出自適應超時閾值算法，本意是排除由于執行周期過長、產生隨機錯誤或受到攻擊而無法在合理時間內得到有效輸出的異構執行體。然而，算法實施過程存在特殊情況，即執行體可能由于某些異常原因或受到遠程控制，導致執行體未按照控制命令完整地執行相應的功能，造成執行時間顯著縮短。進而在此類情況下，通過EPET算法進行異構執行體超時閾值預測將導致正常執行體全部被判決為超時，擬態防御機制失效，嚴重影響系統正常運行及安全性能。

為解決上述問題，此時EPET規則改進如下。

1) 根據第一個完成任務的執行體計算出超時閾值，若其他所有執行體的執行時間均超過該超時閾值，即根據該閾值其他執行體全部被判為超時，則判決此時執行體異常且預測超時閾值失效，繼續等待其余執行體輸出結果。

2) 若根據第二個執行體1完成任務時間計算出來的超時閾值并未導致其余執行體全部被判為超時，即存在執行體在預測閾值時間內完成任務，則判定此時超時閾值預測有效。此時以第二個執行體為基準，按照2.1節所述規則更新所有執行體歷史事件隊列。

3) 若根據第二個執行體1完成任務時間計算出來的超時閾值繼續導致其余執行體全部被判為超時，重復上述步驟，直到有執行體在預測閾值時間內完成任務。

根據擬態防御架構原理，攻擊者同時針對所有異構功能執行體完成攻擊或控制僅存在理論上的可能性，在實際環境中為保證擬態防御性能異構性，執行體的研發、組成、選取、運行等過程差異顯著，致使攻擊者無法在短時間內利用有限的人力、物力完成對所有執行體的探測和攻擊過程，因此，所有執行體都存在異常的情況不在本文算法考慮之內。

2.3 復雜度分析

3 實驗設置

為實現對本文提出的EPET自適應超時閾值預測算法進行仿真，搭建基于擬態原理構建的處理器系統，原理如圖1所示。擬態處理器系統包括4個異構處理器、一個擬態調度器以及相關外圍接口。其中，4個異構處理器分別為AMD、x86 i3、ARM Cortex-A9、龍芯1F(32 bit MIPS架構)，分別搭載Windows7、Windows10、Ubuntu、中標麒麟系統，獨立并行處理用戶端下發的指令及任務；調度模塊為Xilinx Virtex-7系列FPGA，型號為XC7VX690T，主要完成對外通信接口、數據指令分發、處理結果判決、數據分組轉發等任務，3個處理器模塊接收調度模塊發送來的數據和指令，并完成任務處理，再將結果轉發給調度模塊。硬件平臺上，FPGA和各處理器之間的數據傳輸過程極短，可以忽略。仿真實驗過程針對同一實驗進行多次，最終結果取各次結果平均值，保證結果的無偏性。

圖1 擬態處理器系統原理

此外，實驗中編寫了一個模擬任務執行的控制臺程序，分為Client端和Server端，用戶通過Client端發送執行命令及數據，各異構處理器運行Server端接收指令和數據并執行。收發程序的具體執行過程如下。

1) 保持用戶PC與擬態處理器系統聯通。

2) 用戶使用Client端程序向擬態處理器發送執行指令，由FPGA下達至各CPU的Server端；

3) 各CPU在收到指令和數據后進行處理，而后將結果上傳。

4) FGPA記錄任務的開始時間和結束時間。

5) FPGA對各CPU的輸出進行仲裁，然后將最終結果上傳給用戶，Client端顯示文件接收結果。

Server端每發一個數據，視為執行一次任務，任務執行周期由發包時間和處理時間組合得到。一次任務執行完后，間隔100 μs，Client端再發送一個執行指令。

4 實驗仿真與分析

4.1 參數測定及分析

1) 最優放大系數選取過程

EPET算法考慮到實際網絡環境中存在測量誤差、傳輸處理時延等不可控因素，需要對算法預測得出的超時閾值進行合理放大，避免由于超時閾值過于貼近理論值而導致誤報率升高。但放大系數的選取需依照不同系統環境來設定，一方面，若放大系數選取過小，難以解決誤報率高的問題；另一方面，若放大系數選取過大，不僅可能導致異常執行體被判決為正常，也將增加正常執行體的平均等待時間，降低系統運行效率。

本文實驗通過設置測試指令集，對放大系數取值范圍在(1,2]內的執行體平均超時誤報率及正常執行體平均等待時間進行測定，精度為0.1。其中，誤報率定義為正常執行事件被判決為超時的次數占總執行事件的比率，正常執行體平均等待時間t定義為所有正常執行體對于同一任務的預測超時閾值與實際執行時間的差值平均值。實驗結果如圖2所示，從圖2(a)中可以看出，在本文實驗環境下，當放大系數小于1.6時，執行體平均超時誤報率呈不斷下降趨勢，當放大系數大于1.6時，執行體平均超時誤報率雖繼續下降，但趨勢放緩；從圖2(b)中可以看出，預測超時閾值與實際執行時間的差值平均值不斷增大。綜上考慮，本文中放大系數選取為1.6。

圖2 放大系數對EPET算法性能的影響

2) 最優執行體歷史事件執行時間隊列長度選擇過程

從圖3所示實驗結果可以看出，隨著執行體歷史事件執行時間隊列長度的增加，差值比率的數值不斷下降，表明超時閾值的預測準確率逐漸增大。但當隊列長度超過5時，差值比率的數值下降速度放緩，繼續增加隊列長度不僅無法獲得更加顯著的性能提升，而且會繼續增加系統存儲開銷，因此本文實驗中選取隊列長度為5。

圖3 歷史事件時間隊列長度對EPET算法性能的影響

4.2 實驗驗證及分析

基于4.1節選取出的EPET算法最優參數，本節通過設定指令集對算法的有效性進行驗證，實驗結果如圖4所示。從圖4中的不同曲線不難看出，CPU在面對不同系統指令時的處理時間起伏較大，表明CPU在一段時間內任務量存在波動情況。在這種情形下，超時閾值能夠及時隨著CPU處理時間的變化而增加或減小，能夠很好地適應任務量的劇烈和大幅變化。

圖4 EPET算法部分實驗結果及性能指標

從圖4(a)可看出，4個執行體對連續多個任務的處理時間從20 μs到190 μs，如果采用固定閾值方法將超時閾值設置為固定值，則超時閾值需大于190 μs才能保證系統正常運行而不出現誤報。為了保證一定的安全余量，超時閾值可能需要設置到250 μs甚至300 μs以上。且這是對所有任務而言的，即使執行體面臨簡單任務時的執行時間僅為20 μs，執行體也要等到所設置的固定閾值時刻才能夠進行超時判斷，將極大地降低整個處理系統的效率。

從圖4(b)可知，按照本文提出的EPET算法預測出的超時閾值，可根據CPU任務量的變化自適應地升高或降低，閾值范圍從不到30 μs至240 μs。當任務量較小時，超時閾值也較低，能夠及時判斷執行體的狀態，節約執行體等待時間，提升處理系統效率；當任務量較大時，超時閾值也相應升高，能夠有效降低虛警率。

從圖4(c)可知，當CPU處于正常狀態時，其超時閾值與實際執行時間的差值始終為正值，說明沒有出現估算的超時閾值小于實際執行時間的情況，即EPET算法對于各CPU正常執行系統指令時的超時閾值預測未出現誤報，且在合理范圍之內。

為進一步說明本文提出的EPET算法的有效性，取上述4種CPU上各指令執行時間平均值與固定閾值情況與文獻[5]提出的滑動窗口預測算法STW進行性能對比，實驗結果如圖5所示。由于固定閾值的設置通常根據經驗進行，因此針對本文實驗環境，結合圖4中的實驗數據，可知系統的最大執行時間約為180 μs，為了保證一定的余量，對比實驗中固定閾值設置為200 μs。

圖5 固定閾值、PEPT算法超時閾值、STW算法超時閾值性能比較

圖5(a)表示CPU對于系統指令的實際執行時間平均值與閾值（包括固定閾值，根據EPET算法計算得到的動態閾值，根據STW算法計算得到的動態閾值）；圖5(b)表示不同閾值與實際執行時間的差值，包括EPET及STW動態閾值與執行時間的差，以及固定閾值與執行時間的差；圖5(c)表示CPU在處理過程中差值相對執行時間的占比，即差值比率。從圖中可以看出，當CPU在執行較為簡單的任務時，一旦發生超時，在固定閾值條件下，需等待較長的時長甚至幾倍于執行時間的時長才能夠判斷超時，造成整個系統長時間停滯，帶來了不必要的時間浪費，影響指令執行效率。

在本例中，固定閾值條件下，超時閾值恒定為200 μs，超時閾值與系統實際執行時間的最大差值為180.2 μs，最小差值為93.9 μs，平均差值為136.5 μs；文獻[5]中提出的STW算法超時閾值最大值為248.9 μs，最小值為79.5 μs，平均值為146.1 μs。而采用本文提出的EPET自適應計算超時閾值，超時閾值的最大值為224.3 μs，最小值為56.8 μs，平均值為124.8 μs，相對于200 μs的固定閾值減少了37.6%，相比于STW算法預測出的閾值減少了14.6%。這表明相同情況下，EPET算法相比固定閾值算法平均可節約37.6%的等待時間，且相比STW動態閾值預測算法縮短了14.6%的等待時間。進一步，STW算法超時閾值與系統實際執行時間的最大差值為131.9 μs，最小差值為47.5 μs，平均差值為98.8 μs；EPET算法預測出的超時閾值與系統執行時間的最大差值為103.4 μs，最小差值為24.7 μs，平均差值為76.1 μs。相對于固定超時算法，EPET超時閾值與系統執行時間的最大差值減少了51.3%，最小差值減少了56.5%，平均差值減少了39.1%；相比STW動態閾值預測算法，EPET超時閾值與系統執行時間的最大差值減少了21.6%，最小差值減少了48.1%，平均差值減少了22.9%。且在差值比率指數方面，EPET算法平均差值比率處于3種算法中最小值，表明本文的EPET算法具有最優的預測精度。

綜合上述分析可知，本文提出的EPET算法可以根據系統指令執行時間的長短動態地改變超時閾值，在保證最大限度檢測出系統異常的情況下，有效減少了等待時間，提高了超時識別的速度，避免了系統由于需要判斷CPU是否正常而長時間等待的情況，尤其是針對某段時間內系統任務量波動較大的情況，EPET算法能夠提供一個更為有效和靈活的方案。

5 結束語

本文提出了一種面向多執行體的自適應超時閾值預測算法EPET，該算法基于擬態防御架構中包含多個性能接近的異構功能等價體的特性，通過對每個執行體維護一個歷史事件執行時間隊列，采用等效比例執行時間策略得到當前任務的超時閾值。實驗結果表明，相比固定閾值及動態閾值算法，本文提出的EPET自適應閾值預測算法可顯著減少系統對CPU的超時判決速度，降低正常執行體平均等待時間，提升系統的整體運行效率，尤其適合執行體前后任務計算量無規律、波動較大的情況，具有低復雜度的特性。

[1] 鄔江興. 擬態計算與擬態安全防御的原意和愿景[J]. 電信科學, 2014, 30(7): 1-7.

WU J X. Meaning and vision of mimic computing and mimic security defense[J]. Telecommunications Science, 2014, 30(7): 1-7.

[2] 仝青, 張錚, 鄔江興. 基于軟硬件多樣性的主動防御技術[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.

[3] 魏帥, 于洪, 顧澤宇, 等. 面向工控領域的擬態安全處理機架構[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.

[4] RYU B, CHENEY D, BRAUN H W. Internet flow characterization: adaptive timeout strategy and statistical modeling[C]// Passive & Active Measurement Workshop. 2001: 45.

[5] 錢迎進, 肖儂, 金士堯. 大規模集群中一種自適應可擴展的RPC超時機制[J]. 軟件學報, 2010, 21(12): 3199-3210.

QIAN Y J, XIAO N, JIN S Y. Adaptive scalable rpc timeout mechanism for large scale clusters[J]. Journal of Software, 2010, 21(12): 3199-3210.

[6] 周明中, 龔儉, 丁偉. 網絡流超時策略研究[J]. 通信學報, 2005, 26(4): 88-93.

ZHOU M Z, GONG J, DING W. Study of network flow timeout strategy[J]. Journal of Communications, 2005, 26(4):88-93.

[7] CLAFFY K C, BRAUN H W, POLYZOS G C. A parameterizable methodology for Internet traffic flow profiling[J]. IEEE Journal on Selected Areas in Communications, 1995, 13(8): 1481-1494.

[8] FONTI L, LUPINI F, MANGANELLI P. Timeout value adaptation: U S Patent 9,769,022[P]. 2017-9-19.

[9] 侯穎, 黃海, 蘭巨龍, 等. 基于自適應超時計數布魯姆過濾器的流量測量算法[J]. 電子與信息學報, 2015, 37(4):887-893.

HOU Y, HUANG H, LAN J L, et al. An adaptive timeout counter bloom filter algorithm for traffic measurement[J]. Journal of Electronics & Information Technology, 2015, 37(4):887-893.

[10] 余瑩, 李肯立, 徐雨明. 計算集群中一種基于任務運行時間的組合預測方案[J]. 計算機應用, 2015, 35(8):2153-2157.

YU Y, LI K L, XU Y M. combined prediction scheme for runtime of tasks in computing cluster[J]. Journal of Computer Applications, 2015, 37(4):887-893.

[11] 張霄宏, 海林鵬, 賈宗璞, 等. 同構Hadoop環境作業執行時間計算方法[J]. 計算機工程與應用, 2014, 50(10):249-252.

ZHANG X H, HAI L P, JIA Z P, et al. Method for computing execution time of jobs in homogeneous Hadoop environments[J]. Computer Engineering and Applications, 2014, 50(10): 249-252.

[12] 張曹哲, 尤政. 超時策略動態閾值的閾值選擇影響因素[J]. 哈爾濱工業大學學報, 2013, 45(6):119-123.

ZHANG C Z, YOU Z. The influencing factor of threshold selection in dynamic threshold of timeout policies[J]. Journal of Harbin Institute of Technology, 2013, 45(6):119-123.

Timeout threshold estimation algorithm in mimic multiple executors architecture

NIE Delei1, ZHAO bo2, WANG Chong2, WANG Xin3, YAN Binghao2

1. Economic-Technological Development Committee in Tianjin Binhai New Area, Tianjin 300000, China. 2. National Digital Switching System Engineering & Technological R & D Center, Zhengzhou 450002; China 3.Information Technology Innovation Center of Tianjin Binhai New Area, Tianjin 300000, China

Aiming at the problem that the current timeout strategy algorithm is difficult to cope with the violent situation of task volume, a timeout threshold prediction algorithm based on equivalent proportional execution time applied to the mimetic defense architecture system is proposed. The algorithm utilizes the principle that the execution time of multiple functional equivalent executable tasks in the mimetic defense architecture is positively related, predicts the task execution time and sets a reasonable timeout threshold. The simulation results show that the proposed algorithm can dynamically predict and set the timeout threshold for different task situations, which effectively improves the timeout judgment efficiency, especially for scenarios with dramatic changes in workload.

mimic defense, threshold calculation, multiple executors, timeout judgment

TP302.1

A

10.11959/j.issn.2096-109x.2018084

聶德雷（1988-），男，山東莒南人，碩士，天津市濱海新區科技和工業創新委員會主任科員，主要研究方向為網絡安全。

趙博（1981-），男，吉林公主嶺人，博士，國家數字交換系統工程技術研究中心助理研究員，主要研究方向為架構安全。

王崇（1995-），男，河北邯鄲人，國家數字交換系統工程技術研究中心碩士生，主要研究方向為擬態處理。

汪欣（1986-），男，河南周口人，碩士，天津濱海新區信息技術創新中心工程師，主要研究方向為系統結構。

燕昺昊（1994-），男，山西呂梁人，國家數字交換系統工程技術研究中心碩士生，主要研究方面為自適應算法。

2018-08-11；

2018-09-25

趙博，lieut.zhao@126.com