面向拟态安全防御的异构功能等价体调度算法

刘勤让，林森杰，顾泽宇



面向拟态安全防御的异构功能等价体调度算法

刘勤让，林森杰，顾泽宇

（国家数字交换系统工程技术研究中心，河南 郑州 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−），男，辽宁沈阳人，国家数字交换系统工程技术研究中心硕士生，主要研究方向为网络主动防御。