基于轮换策略的异构云资源分配算法

倪思源，扈红超，刘文彦，梁 浩

（1.郑州大学 中原网络安全研究院，郑州 450000；2.中国人民解放军战略支援部队信息工程大学，郑州 450000）

0 概述

云计算凭借其随需应变、按需即付的优势给用户带来极大的便利。为支持大规模的云服务，数据中心需开通数千台服务器和交换机。数据中心要为众多服务器和网络设备供电，因此会消耗大量能源。典型数据中心的能耗相当于25 000 户家庭的能耗，每5 年可能翻1 番［1-2］。最近的研究结果表明，由于数据中心的服务器利用率不足会导致大量的资源被浪费，且服务器的平均利用率仅为5%～20%之间［3］。因此，在提供云服务的同时，提高数据中心的服务器利用率非常重要。

部署在服务器上的虚拟机被攻击后会影响正常服务，所以研究人员提出一种冗余备份的虚拟机策略，冗余策略能够提高云计算环境的容错性，减小对用户体验带来的影响。然而，系统组件的同质化，使得攻击者易于探测用户信息、窃取用户数据，导致云计算环境受到安全威胁［4］。2019 年1 月，研发人员发现WINRAR 漏洞，该漏洞威胁了5 亿用户的系统安全。同年10 月，Android 零日漏洞也被发现，该漏洞威胁了华为、三星、小米等多家电子设备的安全。基础设施异构化能够增大攻击者探测难度［5］，提高云计算环境的安全性，在此基础上对虚拟机进行动态轮换能够进一步增强虚拟机安全性，通过动态改变虚拟机的部署位置和虚拟机的操作系统，避免用户虚拟机受到侧信道攻击［6］和探测攻击［7］。

然而，异构云基础设施和虚拟机轮换会带来云计算资源分配的难题［8］。一方面，由于基础设施异构化使得传统的装箱方法不再适用资源分配，供应商需考虑每一个服务器可提供的资源来实现负载均衡。另一方面，虚拟机的轮换会改变当前服务器的负载情况，如何在轮换的过程中减小负载波动值得研究。本文提出一种基于轮换策略的异构云资源分配算法，将不同的资源抽象成维度不同的向量，利用余弦定理来衡量向量之间的相似度，根据向量间的相似度进行资源分配以实现负载平衡，并在初次资源分配完成后对虚拟机选择相似度最高的服务器进行轮换。

1 相关研究

云计算中的资源分配属于大规模多任务调度问题，一直是人们研究的热点。文献［9］提出一种两步式的资源分配算法，首先在云中选择一个集群，然后在集群中选择一个节点部署虚拟机，该模型使用了3 个集群和6 个节点，实验结果表明，选择合适的集群比选择合适的节点对资源分配的影响更大。文献［10］讨论了如何量化服务器和整个系统间的负载平衡，该研究选用贪心算法来平衡服务器之间的负载，当服务器负载超过阈值时，对该服务器上的虚拟机进行迁移，并计算迁移虚拟机后的服务器负载平衡变化值，选取最小不平衡变化值进行迁移。文献［11］根据虚拟机的状态，提出了静态虚拟机放置和动态虚拟机放置的算法，既考虑了单个服务器的资源剩余量和资源利用率，又兼顾了整体服务器的资源剩余量和资源利用率。该算法使用平面资源六边形，由代表不同资源利用类别的三角形组成。虚拟机被分配到互补资源三角形中的服务器上来平衡总体利用率。文献［12］在文献［11］的基础上提出了一种虚拟机放置互补策略。该互补策略考虑资源使用和时间使用两个方面，并认为在不同时间使用相同资源的虚拟机或在相同时间使用不同资源的虚拟机是互补的。文献［13］设计一种基于启发式正交二叉树搜索的三维装箱算法，该算法以所有叶子节点填充率最高为目标，满足了装箱的3 个约束条件。文献［14］结合日常砌墙策略，提出了一种混合模拟退火算法，利用找点法和参考线规则来进行装箱，该算法能有效解决三维装箱问题。

虚拟机是一种用于模拟物理服务器的虚拟化技术。随着虚拟化的发展，虚拟机扩容和虚拟机的实时迁移为提高服务器利用率提供了两种潜在的解决方案［15-16］。虚拟机大小调整方案可以对虚拟机资源配置的细粒度进行调整。与峰值资源请求的资源调配相比，虚拟机大小调整的资源调配可以更好地利用物理资源，而计算开销可以忽略不计。实时迁移能够以无中断的方式在不同服务器之间移动正在运行的虚拟机。通过应用实时迁移和虚拟机扩容，数据中心管理器可以将虚拟机整合到更少的服务器上，以提高数据中心的能源使用率。在整合虚拟机时，可能存在虚拟机工作负载突发的情况使服务器过载［17］。虚拟机迁移通过改变底层的物理环境可以抵御云计算中的侧信道攻击，文献［18］在此基础上利用MTD 技术，通过多个操作系统的轮换来增强安全性，并利用现有技术，提供了一个可行的动态防御解决方案，可以方便地部署在真实的网络环境中。不同于虚拟机迁移，该方案通过轮换删除原服务器上的虚拟机，并在新的服务器上部署新的虚拟机。测试结果表明，平台的多样性和动态性提高了系统的安全性，攻击成功率与轮换时间间隔成反比。

随着云计算的发展，越来越多的计算资源被提供给客户，如CPU、内存大小、磁盘大小、带宽等。因此，分配方法应该支持任意数量的维度［19］。同时，在保障虚拟机安全性的同时服务器的资源利用率和负载波动也应被关注。针对以上问题，本文在传统的装箱方法上做了改进，并提出一种基于轮换策略的异构云资源分配算法，主要贡献如下：

1）对底层物理设施异构化，通过异构底层物理服务器，增大攻击者探测难度，提升云计算环境安全性。

2）将影响虚拟机部署的资源抽象成向量，多维度地考虑资源分配问题，以更贴近真实的资源分配环境，同时根据虚拟机部署资源的向量与物理服务器向量间的相似度选择虚拟机，使得计算节点成本更小，能源利用率更大。

3）在每个虚拟机初次部署的同时，为每个虚拟机设置驻留时间，当到达驻留时间后根据当前服务器负载情况对虚拟机进行轮换。轮换会改变虚拟机的操作系统以及所部署的服务器位置，在提高资源利用率的同时提升了执行体的安全性。

2 问题描述

虚拟机在部署时会面临服务器选择问题，由于不同的服务器负载情况可能不同，在部署时会影响云平台的整体负载情况。本文将多维异构资源的分配问题分为2 个阶段：

1）初次部署虚拟机。将虚拟机部署在异构的物理服务器上，同时保证各个服务器资源利用率高和服务器间负载平衡，这本质上是一个多目标优化问题。

2）轮换已经部署好的虚拟机。轮换可以减小攻击者对虚拟机的影响，提升虚拟机安全性，但是轮换会引起服务器负载变化，所以在考虑虚拟机安全的同时，应尽量减小服务器的负载波动。

2.1 装箱问题

资源分配问题通常被视为装箱问题，即在最少的箱子里放置最多的物品。云计算中影响资源分配的因素有很多，如CPU、内存大小、磁盘大小、带宽等。本文用不同的维度来表示这些因素，并对云计算中多维资源分配问题进行研究。装箱问题描述如下：有n种体积不同的物品，将这n种物品装到体积为C的m个箱子中，并约定这n种物品的体积均小于箱子的体积C。不同的装箱策略使用的箱子个数可能不同，装箱问题要求使用最少的箱子来装这些物品。

云计算的物理基础设施是由一台台的物理服务器组成的，异构能有效提高云计算环境的安全性，但是异构的服务器之间容量不同，因此异构装箱较传统的装箱问题相比引入了新的问题。对于每台服务器均需满足以下约束条件：

部署在服务器J上的虚拟机资源需求要小于服务器容量，不满足该约束条件即视为装箱失败。以三维装箱为例，将服务器的CPU、内存与磁盘空间抽象为互不相关的3 个维度，如图1 所示。的容量为（6,6,3），的容量 为(7,5,6)。的体积为(2,1,3)的体积为(1,2,1)，的体积为(1,2,2)，的体积为(3,1,2)，的体积为(2,1,1)。按传统的装箱方法，当虚拟机任务请求到达时，先尝试放入已经打开的箱子，如果能放下就放入该箱子，放不下就开启新的箱子，直到找到能放下的箱子为止。如图1（a）所示；可以放置在，放置后剩余资源为(5,5,0)，此时磁盘空间已经使用完，但是CPU 与内存空间还剩余很多，会造成严重的资源浪费；、和可以放置在上，放置后剩余资源为(2,0,2)，此时，导致无法放置。但这种放置策略会造成资源浪费，即PM的利用率不高。如图1（b）所示，将放置在上，和放置在上，此时，所有虚拟机都能成功部署在服务器上。这种放置策略可以有效提高箱子的利用率，减少资源的浪费。

图1 虚拟机放置策略Fig.1 Virtual machine placement strategies

2.2 轮换问题

网络攻击对网络系统的危害主要分为网络可用性危害与信息安全属性危害［20］，主要体现在对可用性、机密性、完整性、不可抵赖性、认证性等安全属性的危害。由于不同的系统遇到危害时敏感性反应不同，假设攻击者只要能入侵目标主机便视为成功攻击，攻击过程的5 个阶段描述如图2 所示。

图2 侵入攻击阶段示意图Fig.2 Schematic diagram of intrusion attack phase

同一台物理服务器上的虚拟机之间共享资源，攻击者通过定位到目标主机所在的服务器位置，将攻击者控制的虚拟机与目标主机部署到同一台服务器上，并对目标主机发起侧信道攻击。同时，攻击者也可以探测用户虚拟机的操作系统，根据用户操作系统漏洞对目标主机进行攻击。攻击成功率P与虚拟机操作系统漏洞有关：

其中，V表示虚拟机操作系统漏洞。因此，动态地改变虚拟机部署的位置和虚拟机的操作系统能够增大攻击者的探测难度，降低攻击者的攻击成功率。

3 模型建立

本节提出基于轮换策略的异构云资源分配算法，将异构云资源分配问题建模为多维装箱问题进行求解，同时提出一个资源分配利用率指标，根据该指标选择虚拟机要部署的服务器位置。

3.1 系统模型

3.2 资源分配利用率指标

本节根据利用率指标来解决虚拟机布局问题。在资源分配时根据当前服务器的负载情况以及资源利用率来选择虚拟机的放置位置，参数定义如表1所示。

表1 参数定义Table 1 Parameters definition

式（3）表示服务器j的剩余资源为服务器j的总资源减去部署虚拟机i所占用的资源。由于部署虚拟机时要考虑当前服务器负载情况以及资源剩余情况，因此本文根据当前的服务器资源利用率来选择虚拟机的部署位置。对于一个2 维向量空间，两个向量间的夹角越小，两个向量越相似。将此推广至两个k维向量，即虚拟机i的资源需求request 与服务器j的资源剩余，这两个k维向量余弦值如式（5）所示，其中θvp表示虚拟机i的资源需求与服务器j的剩余资源夹角大小。

θvp值越大表示虚拟机i的资源需求与服务器j的剩余资源之间夹角越大，两个向量相关性越低。反之，θvp值越小表示虚拟机的资源需求与服务器的剩余容量相关性越高。本文选取与虚拟机i的θvp值最小的服务器j来放置虚拟机。

4 基于轮换策略的装箱方法

4.1 装箱方法

资源分配问题本质上是一个多目标优化的问题，旨在提高能源效率、资源利用率、负载平衡和服务器整合。本文将云计算中的异构资源分配问题视为多维异构装箱问题，具体描述如下：有n个体积不同的虚拟机(0 ≤i≤n)，m个容量不同的服务器(0 ≤j≤m)，如式（6）所示，目标是用最少的服务器部署最多的虚拟机。

目标函数：

在革命战争年代，长征时期红军战士爬雪山、过草地、煮皮带、吃树根，坚决执行“不拿群众一针一线”的方针；在社会主义年代，老一代科学家风餐露宿、顽强拼搏，克服各种难以想象的困难，突破技术难关，最终完成了我国“两弹一星”战略。大学生接受红色文化熏陶，有助于将艰苦奋斗精神渗透到他们的学习和生活中去，培养谦虚、踏实的学习和生活态度[1]。

由于虚拟机是多维资源包，本文用向量来表示虚拟机的多维资源，其中k表示资源类型的维度。式（7）表示放置的虚拟机资源需求要小于服务器的剩余资源，表示服务器j的k维资源剩余情况，表示服务器的容量，表示虚拟机i各个维度占的体积。式（8）表示将虚拟机i部署在服务器j上。

4.2 轮换方法

变量说明：

S(xij)：0-1 变量，当虚拟机i在服务器j上的状态正常时，S(wij)为1，否则为0。

约束条件：

式（9）表示虚拟机i在服务器j上驻留的时间不能超过时间t。式（10）表示服务器的负载变化情况，它等于虚拟机轮换前后服务器体积的变化，其中，add 表示轮换后服务器j新增的虚拟机体积，delete 表示服务器j上要删除的虚拟机体积。式（11）表示服务器当前负载状态，它等于动态轮换之前服务器的负载与轮换后服务器负载变化之和。虚拟机动态轮换时也要满足式（7）的约束条件，即轮换的虚拟机体积要小于服务器的容量。

本文通过动态、异构的虚拟机部署方式来增强虚拟机的安全性。对于虚拟机(Ov,Pj)，本文考虑操作系统Ov以及部署的服务器位置Pj两个要素，通过异构操作系统Ov和部署的服务器位置Pj来提高虚拟机的安全性。如图3 所示，在创建虚拟机(O1,P1)时，给每个虚拟机提前设定好驻留时间，同时设置代理监控每个虚拟机的状态。当虚拟机到达驻留时间或虚拟机状态异常时，便删除该服务器上的虚拟机，但是该虚拟机的数据仍然存在一个安全的共享数据库中。同时，创建一个新的虚拟机(O2,P2)，该虚拟机操作系统与原虚拟机不同，部署的服务器位置也不同，但是虚拟机(O2,P2)能从数据库中获取虚拟机(O1,P1)的数据，并和虚拟机(O1,P1)一样对外提供服务。虚拟机根据当前服务器的负载，选择θvp值最大的服务器进行轮换，并要求request，即当前服务器剩余容量大于要轮换的虚拟机体积。

图3 虚拟机轮换方法Fig.3 Virtual machine rotation method

4.3 轮换策略的装箱方法

算法1基于轮换策略的异构云多维资源分配算法

本文根据服务器利用率指标来解决虚拟机布局问题。在资源分配时根据当前服务器的负载情况以及资源利用率来选择虚拟机的放置位置。对虚拟机遍历所有的服务器，通过式（5）计算θvp值，θvp=[θvp(i,1),θvp(i,2),…,θvp(i,j)]。将虚拟机部署到θvp值最小的服务器上，此时应注意服务器的负载情况，若服务器资源剩余量小于虚拟机资源请求，则选择θvp第二小的服务器上，依次类推，直到能成功部署虚拟机为止。若资源池中有虚拟机需要轮换，服务器的负载状态要同时考虑轮换的虚拟机体积和部署的虚拟机体积。若资源池中无虚拟机需要轮换，服务器的负载状态仅考虑要部署的虚拟机体积。

1）时间复杂度分析。当初次部署虚拟机时，没有虚拟机进行轮换。n个虚拟机遍历m个服务器，并选取最佳θvp选择服务器，时间复杂度为O(mn)。当有虚拟机进行轮换且轮换个数为w时，轮换的时间复杂度为O(wn)。

2）安全性分析。探测攻击是攻击者常用的一种攻击手段。攻击者通过向用户发送带有恶意网址或附件的电子邮件来收集有关目标网络信息，并根据收集到的信息来判断用户的操作系统，然后利用该操作系统的漏洞发动攻击。对于攻击者来说，每次无论是否攻击成功，都能获得用户的操作系统类型，并为下次攻击做准备。攻击成功率如式（12）所示：

其中，P表示虚拟机被攻击成功的概率，V表示虚拟机操作系统的种类，n表示攻击者发动的攻击次数，探测攻击最多发动2 次攻击就一定能攻击成功。轮换策略增大了攻击者的攻击难度，使得攻击者无法根据上一次探测到的信息来判断用户的操作系统。

5 实验结果与分析

5.1 实验设置

本文实验在Intel®CoreTMi7-4790 CPU 3.6 GHz，16 GB RAM 的主机上进行，基于轮换策略的多维异构装箱算法采用C++语言编程实现，并利用Matlab工具对实验结果进行分析。攻击者已知的操作系统漏洞和防御者操作系统具有的漏洞都服从［0，11］的均匀分布，攻击手段采用探测攻击。每个实验进行100 次蒙特卡洛仿真，保证误差在合理范围内。

本文通过通用漏洞披露（Common Vulnerability Enumeration，CVE）公布的数据，获取了11 种操作系统在1994 年—2017 年被公开的所有漏洞。这11 种操作系统分别是OB（OpenBSD）、NB（NetBSD）、FB（FreeBSD）、W03（Windows Server 2003）、W08（Windows Server 2008）、W12（Windows Server 2012）、U（Ubuntu）、D（Debian）、R（Redhat）、OS（OpenSolaris）和S（Solaris）。表2 所示为上述系统存在的漏洞数量以及不同操作系统间存在的共同漏洞数量。

表2 操作系统共同漏洞数量Table 2 Number of common vulnerabilities in operating systems

假设攻击者已获知的操作系统为Ii，该系统的漏洞数为V(Ii)，用户虚拟机的操作系统为Ij，用户的操作系统漏洞数为V(Ij)，攻击者已知的漏洞和用户虚拟机间的操作系统共同漏洞数为V(Ii,Ij)。用户虚拟机被攻击成功的概率为：

5.2 实验分析

仿真实验1不同维度下服务器资源利用率的对比实验。本实验分别对10 台服务器、50 个虚拟机和20 台服务器、100 个虚拟机这两种组合进行分析。对比这两种组合中不同维度下的服务器资源利用率情况。实验结果如图4 所示。

图4 不同维度下服务器资源利用率对比Fig.4 Comparison of server resource utilization in different dimensions

从图4 可以看出，对于10 台服务器和50 个虚拟机的装箱实验，不同维度的服务器资源利用率不同，随着维度的升高，虚拟机的资源利用率逐渐降低。在2 维时资源利用率为0.990 0，在3 维时资源利用率为0.989 7，在5 维时资源利用率为0.988 7；对于20 台服务器和100 个虚拟机，在2 维时资源利用率为0.981 5，在3 维资源利用率为0.978 4，在5 维时资源利用率为0.967 9。通过以上实验分析结果可以看出，随着维度的增加，服务器的资源利用率会降低。

仿真实验2不同异构程度的装箱对比实验。实验设置10台服务器、50个虚拟机进行装箱。对异构程度不同的虚拟机与服务器组合进行对比分析。4 组组合分别是：同构服务器，同构虚拟机；同构服务器，异构虚拟机；异构服务器，同构虚拟机；异构服务器，异构虚拟机。将本文所使用的基于最大利用率策略与轮流放置策略、随机放置策略进行对比，如图5所示。

图5 服务器异构装箱资源利用率对比Fig.5 Comparison of server heterogeneous packing resource utilization

从图5 可以看出：当服务器与虚拟机都同构时，3 种策略下的服务器平均资源利用率相同，均为0.990 0；当服务器同构、虚拟机异构时，基于最大利用率策略与轮流策略的资源利用率相同为0.993 9，随机放置策略的服务器的资源利用率为0.979 1；当服务器异构、虚拟机同构时，基于最大利用率策略下平均资源利用率最高为0.993 8，轮流策略次之，平均资源利用率为0.965 2，随机策略最差，平均资源利用率为0.941 6；当服务器异构、虚拟机异构时，基于最大利用率策略下平均资源利用率最高为0.993 8，轮流策略次之，平均资源利用率为0.940 7，随机策略最差，平均资源利用率为0.848 2。以上实验结果表明，基于利用率装箱策略在异构装箱问题中表现较好。

仿真实验3不同策略下服务器利用率的对比实验。实验分为两组：一组是10 台服务器，50 个虚拟机；另一组是20 台服务器，100 个虚拟机。对比两组配置在不同虚拟机部署策略下的服务器资源利用率。

图6 所示为基于利用率装箱策略和轮流放置策略、随机放置策略的资源利用率情况。

图6 不同策略下服务器资源利用率对比Fig.6 Comparison of server resource utilization under different strategy

从图6 可以看出：当服务器为10 台，虚拟机为50 个时，计算每台服务器的负载情况。本文使用的基于利用率装箱策略下服务器的平均资源利用率为0.993 6，差值为0.016 8，轮流放置策略的平均资源利用率为0.981 4，差值为0.051 1，随机放置策略的平均资源利用率为0.841 0，差值为0.323 0。当服务器为20 台，虚拟机数量为100 个时，计算每台服务器的负载情况。基于利用率装箱策略平均资源利用率为0.991 7，差值为0.028 4，轮流放置策略的平均资源利用率为0.981 6，差值为0.048 0，随机放置策略的平均资源利用率为0.848 2，差值为0.471 4。以上实验分析可得，基于利用率装箱策略能够有效提高服务器的资源利用率并减小负载波动。

仿真实验4轮换前后服务器负载状态对比实验。由于每个虚拟机创建的时间不同，每个虚拟机开始轮换的时间也不同，因此本实验单独考虑每个虚拟机轮换情况。首先从服务器资源池中随机选取10 个虚拟机，依次进行轮换并计算轮换前后服务器负载平衡变化。

如图7 所示，轮换前服务器的平均负载平衡率为0.966 5，差值为0.055 3。进行10 次轮换后服务器的平均负载平衡率为0.964 0，差值为0.068 5。通过分析实验数据可得，轮换后服务器的负载平衡率降低了0.002 5，不同服务器之间负载平衡率差值增大了0.013 5，轮换后服务器平均负载平衡降低了0.2 个百分点，负载波动值增大了15.3 个百分点。

图7 轮换前后负载平衡率变化情况Fig.7 Changes in load balance rate before and after rotation

仿真实验5有无轮换策略下虚拟机被攻击的对比实验。本文实验随机从操作系统库中选取1 个操作系统，从物理资源池中随机选择1 台服务器来部署虚拟机，操作系统服从［0，11］均匀分布。攻击者对用户虚拟机发动探测攻击，并根据探测到的信息调整攻击策略发动下一次攻击。实验进行100 次蒙特卡洛仿真，保证误差在合理范围内。

图8 所示为有无轮换策略下用户操作系统被攻击成功的概率的实验对比分析。

图8 虚拟机被攻击成功的概率对比Fig.8 Comparison of success rate of virtual machines being attacked

本文针对的是探测攻击，在攻击链中攻击者先探测用户的虚拟机，根据从用户探测到的信息来判断用户的操作系统，然后根据掌握的操作系统漏洞对用户发起攻击。如图8 所示，对于非轮换策略，攻击者在首次发动攻击时，有0.27 的概率能够成功攻击用户，但是第一次攻击结束后，攻击者根据探测到的信息再次发动攻击的成功率变为1。对于有轮换策略，用户在攻击者发动1 次探测的时间范围内进行轮换，此时用户的操作系统已经改变，攻击者已经无法根据上次探测到的信息来确定用户的操作系统。进行100 次探测攻击实验，攻击者的平均攻击成功率约为0.183 6，轮换后虚拟机的安全性提升了18.5 个百分点，实验结果表明，轮换策略能够有效提高操作系统的安全性。

6 结束语

云计算中的资源分配通常被建模为装箱问题。在装箱问题中，静态同构的云计算环境会威胁到虚拟机安全，动态异构的云计算环境更符合真实的资源分配情况，但也引入了新的资源分配问题。同时，由于影响资源分配的因素较多，传统的装箱方法无法解决多维的资源分配问题。针对以上问题，本文提出一种基于轮换策略的多维异构云资源分配算法。将虚拟机和服务器资源抽象为向量，并给出一种利用率指标，根据利用率指标为虚拟机选择要部署的服务器。为提高虚拟机的安全性引入了轮换策略，给每个虚拟机设定一定的驻留时间，当虚拟机在服务器上的驻留时间达到阈值或虚拟机状态出现异常后，对虚拟机进行轮换。实验结果表明，该算法在多维异构的装箱问题中具有较高的资源利用率，且能够提高虚拟机的安全性。下一步研究方向为寻找最佳轮换周期，在保证安全性的前提下尽可能减少轮换产生的开销。