本发明所述一种APK的快速检测及提高单位资源利用率的方法是运行虚拟机的计算机确定待检测APK占用每台虚拟机资源的最小值Φ1以及确定当前时间段未被检测APK优先级属性之和与被检测APK优先级属性之和的比值Φ2，并利用拉格朗日加权法对Φ1和Φ2进行加权处理形成Φ值；然后利用遗传算法确定待检测APK最优分配方案，即通过在遗传算法中通过加入适应度P来实现，所述适应度P为所有虚拟机的Φ之和，由此实现关注整个检测系统的最优。本发明的优点在于：本发明是基于APK属性与虚拟机资源关系的提高APK检测速率与资源利用率的方法，使用该方法分配与检测APK时，速度更快，资源利用率更有效。
1.一种APK的快速检测及提高单位资源利用率的方法:包括一台运行虚拟机的计算机；
所述运行虚拟机的计算机从检测队列中批量获取待检测APK；
所述运行虚拟机的计算机获取待检测APK属性和虚拟机资源属性；
所述运行虚拟机的计算机检测并确定待检测APK属性值及虚拟机资源属性值；
所述运行虚拟机的计算机确定APK的属性对应的虚拟机资源的权重，所述权重用于标识APK的属性对虚拟机资源的影响程度；
所述运行虚拟机的计算机建立并计算待检测APK属性值与虚拟机资源属性值函数，具体方式为：将N个APK{APKn|1≤n≤N}分配到M个虚拟机{Vm|1≤m≤M}上，即将N个APK分成M个簇，每个候选簇记为C'm；其满足如下约束条件：放入每个虚拟机中的APK所需资源之和不大于该虚拟机实际所拥有的资,即为：Xt∈{X1,X2,…,XT}且ust≠0，其上需满足：
Xt∈{X1,X2,…,XT}且ust≠0，其中：m表示虚拟机个数，s表示资源种类
优化目标二：对于优先级属性，属性值越高的APK优先分配；
其中：i表示未被选中的APK，j表被选中的APK将以上两个优化目标进行拉格朗日加权，可得如下的综合目标函数：Φ＝δΦ1+(1-δ)Φ2其中，(0≤δ≤1)；
所述运行虚拟机的计算机利用遗传算法确定最优APK分配方案，具体最优APK分配方案的步骤为：步骤一：个体编码生成
使用二进制编码，另外引入一个特殊的编码符号“×”表示禁止基因，禁止基因所对应的虚拟机与该APK性能不匹配或虚拟机处于忙碌状态，不能接受任务分配；
在初始化时，禁止基因被分配编码“×”，并且在后面的遗传操作中都不会改变，即不考虑分配对应的APK给该虚拟机；因此，染色体上的基因有“0”、“1”、“×”三种编码，设第μ行第τ列的基因为 则它的意义如下：步骤二：初始群体的产生
由于遗传算法是对群体进行操作的，确定初始群体的数据；
遗传算法中以所有虚拟机之和的适应度大小来评定整个分配方案的优劣，从而决定遗传机会的大小；
所述适应度用 度量， 越大被选中的概率就越大，其中i表示虚拟机的个数；
使用轮盘赌方法选择构成下一代的个体，任一个体被选择的概率等于其适应值与所有染色体适应值之和的比值，在此选择过程中，精英保留策略被采用，以确保获得的最优个体不被进一步的遗传操作所破坏，从而更有可能收敛到全局最优解；在交叉、变异等操作之后，如果新一代中最优个体的适应值小于上一代中最优个体的适应值，则上一代的最优个体被复制，并取代新一代中的最差个体；
为了确保子代染色总是满足约束条件，使子代染色体总是问题的可行解，两个父代染色体矩阵中的一行或列以一定的交叉概率Pc被交换，交叉完成后，需在父染色体P1、P2和新染色体C1、C2之间进行选择，适应值较高的进入下一代，具体为：O1＝max{fitness(P1),fitness(C1)}O2＝max{fitness(P2),fitness(C2)}；
从N行，M列中随机产生两个随机数p和q，则当满足下面两个条件的时候，将第p行q列的基因 从0变为1或者从1变为0，且需满足如下两个条件：条件1为基因 不是禁止基因，条件2为 上述两个条件同时满足便可进行变异；
所述运行虚拟机的计算机根据最优APK分配方案将待检测APK分配给虚拟机。
2.如权利要求1所述的一种APK的快速检测及提高单位资源利用率的方法，其特征在于：所述APK属性包括：APK文件的大小、DEX文件的大小、APK文件中代码复杂度、APK文件中界面复杂度、APK文件中资源文件复杂度和APK检测优先级，其中，所述APK文件的大小是指APK文件本身占用存储空间的大小，单位为Mb；
所述DEX文件的大小是指APK文件中的扩展名为.dex文件的大小，单位Mb；
所述APK文件中代码复杂度是指dex文件中代码的目录深度与文件数的关系，代码复杂度设置范围为(1，100)，APK文件目录深度为(1，10]，超过10的以10计，APK的文件数(1，
所述APK文件中界面复杂度是指APK在运行过程中的界面数与界面中所使用控件的关系，界面复杂度指设置范围为(1，100)，APK界面总数为(1，100]，超过100的以100计，单个界面的控件总数(1，10]，超过10的以10计；
所述APK文件中资源文件复杂度是指APK中res目录下目录的层级与下面目录和文件数之间的关系，所述资源文件的复杂度设置范围为(1，100)，目录深度为(1，5]，每级最大目录数(1，10]，每个目录的最大文件数(1，100]；
所述APK检测优先级是指APK所要满足的最晚检测开始时间，所需资源的最大数等条件，包括但不限于上述条件，可根据实际情况动态调整；
所述虚拟机资源属性包括CPU指数、内存指数和线程指数，其中，所述CPU指数指的是CPU当前可被使用的资源与CPU原始可使用资源的比率；
所述内存指数指的是内存当前空闲资源与内存原始可使用资源的比率，所述线程指数指的是当前超线程中线程空闲数与原始线程数。
3.如权利要求1所述的一种APK的快速检测及提高单位资源利用率的方法，其特征在于：所述APK属性值包括APK文件的大小属性值、DEX文件的大小属性值、APK文件中代码复杂度属性值、APK文件中界面复杂度属性值、APK文件中资源文件复杂度属性值和APK检测优先级属性值，其中，APK文件的大小属性值，具体为APK实际大小与可检测APK文件最大值之比乘以100；
APK文件中DEX文件的大小属性值，具体为APK中DEX的实际大小与可检测DEX文件的最大值之比乘以100；
APK文件中代码复杂度属性值，具体为DEX文件中代码的目录深度乘以可检测DEX文件的最大值30后除以最大目录深度10并加上DEX文件中文件总数乘以70后除以文件最大数
APK文件中界面复杂度属性值，具体为APK文件的总界面数乘以单个界面控件的最多数除以设定的界面最大数与界面中控件的最大数的积，然后再乘100得到APK文件中界面复杂度属性值；
APK文件中资源文件复杂度属性值，具体为APK文件中Res文件下实际目录深度与实际目录最大数及实际目录文件的最大数之积除以设定的Res文件下的目录深度最大值与目录数最大值及目录中最大文件数的积，然后再乘以100得到PK文件中资源文件复杂度属性值；
APK检测优先级属性值，具体为最晚待检时间10减去最晚设定检测时间除以10后乘以
所述虚拟机资源属性值包括CPU指数值、内存指数值和线程指数值，其中，所述CPU指数值具体为CPU核心数与CPU主频及当前CPU未被使用率的乘积；
所述内存指数值具体为CPU内存大小与当前内存未被使用率的乘积；
所述线程指数值具体为线程数与当前线程未被使用率的乘积。
4.如权利要求1所述的一种APK的快速检测及提高单位资源利用率的方法，其特征在于：所述APK属性对应的虚拟机资源的权重确定方式为：每个APK具有某些属性，而每个虚拟机拥有有限的资源，APK的属性决定了其在虚拟机中的分配结果；
由于虚拟机的某种资源与APK的某些属性相关联，从而决定APK的分配方式，所述关联的表达式为：Rs＝us1X1+us2X2+…+ustXt+…+usTXT其中，
ust表示资源s与属性t之间关系,需同时满足0≤ust≤1和us1+us2+…+ust＝1两个条件；
Rs表示某个APK分配到虚拟机后所占用的虚拟机S类资源。
一种APK的快速检测及提高单位资源利用率的方法
技术领域
[0001] 本发明属于信息安全技术领域，尤其涉及一种Android移动应用程序(Android application package，APK)的快速检测及提高检测系统单位资源利用率的方法。
背景技术
[0002] 随着移动互联网的高速发展，基于Android系统的各类应用被大量开发。与此同时，出现了众多垃圾应用、恶意应用等，使得移动终端面临的安全问题也随之增多，导致开发者和用户利益受损。因此需要对Android的应用程序进行安全检测。
[0003] 现有的检测方法大致包括：静态检测、动态检测以及病毒检测。静态检测是在APK执行前进行检测；动态检测是在APK运行时进行检测；病毒检测是针对APK进行病毒样本识别杀毒。不同检测方法所需的检测速率及消耗检测系统资源的能力不尽相同。
[0004] 目前基于云计算的APK检测，其步骤主要是：首先，上传待测APK文件；其次，根据上传APK的先后次序，依次分配到指定的虚拟机中进行检测。面对大量不同大小、类型、不同检测需求的待测APK时，由于没有考虑到合理分配系统的检测资源，必然会存在一定的检测效率低以及资源利用率低等问题。
[0005] 因此需要一种Android移动应用程序的快速检测及提高检测系统单位资源利用率的方法来解决现有技术存在的问题。
发明内容
[0006] 本发明的目的是针对现有技术的不足，提出一种Android移动应用程序的快速检测及提高单位资源利用率的方法,该方法有效提高APK的检测速度以及检测资源利用率。
[0007] 本发明所述技术方案关注的不是将哪些待检测APK分配到某个虚拟机中最优，而是如何将所有待检测APK分配到不同的虚拟机中，使得检测系统以最优的方式快速检测APK。
[0008] 本发明所述技术方案的技术思路为：运行虚拟机的计算机确定待检测APK占用每台虚拟机资源的最小值Φ1以及确定当前时间段未被检测APK优先级属性之和与被检测APK优先级属性之和的比值Φ2，并利用拉格朗日加权法对Φ1和Φ2进行加权处理形成Φ值；然后利用遗传算法确定待检测APK最优分配方案，即通过在遗传算法中通过加入适应度P来实现，所述适应度P为所有虚拟机的Φ之和，由此实现关注整个检测系统的最优；另外，在本发明使用的遗传算法中，通过交叉、选择等操作实现对整个检测系统实现最优分配，从而达到提高检测资源利用率以实现快速检测APK的目的。
[0009] 实现本发明所述技术效果的具体如下：
[0010] 一种APK的快速检测及提高单位资源利用率的方法:
[0011] 包括一台运行虚拟机的计算机；
[0012] 所述运行虚拟机的计算机从检测队列中批量获取待检测APK；
[0013] 所述运行虚拟机的计算机获取待检测APK属性和虚拟机资源属性；
[0014] 所述运行虚拟机的计算机检测并确定待检测APK属性值及虚拟机资源属性值；
[0015] 所述运行虚拟机的计算机确定APK的属性对应的虚拟机资源的权重，所述权重用于标识APK的属性对虚拟机资源的影响程度；
[0016] 所述运行虚拟机的计算机建立并计算待检测APK属性值与虚拟机资源属性值函数；
[0017] 所述运行虚拟机的计算机利用遗传算法确定最优APK分配方案；
[0018] 所述运行虚拟机的计算机根据最优APK分配方案将待检测APK分配给虚拟机。
[0019] 进一步的，所述APK属性包括：APK文件的大小、DEX文件的大小、APK文件中代码复杂度、APK文件中界面复杂度、APK文件中资源文件复杂度和APK检测优先级，其中，[0020] 所述APK文件的大小是指APK文件本身占用存储空间的大小，单位为Mb；
[0021] 所述DEX文件的大小是指APK文件中的扩展名为.dex文件的大小，单位Mb；
[0022] 所述APK文件中代码复杂度是指dex文件中代码的目录深度与文件数的关系，代码复杂度设置范围为(1，100)，APK文件目录深度为(1，10]，超过10的以10计，APK的文件数(1，1000]，超过1000的以1000计；
[0023] 所述APK文件中界面复杂度是指APK在运行过程中的界面数与界面中所使用控件的关系，界面复杂度指设置范围为(1，100)，APK界面总数为(1，100]，超过100的以100计，单个界面的控件总数(1，10]，超过10的以10计；
[0024] 所述APK文件中资源文件复杂度是指APK中res目录下目录的层级与下面目录和文件数之间的关系，所述资源文件的复杂度设置范围为(1，100)，目录深度为(1，5]，每级最大目录数(1，10]，每个目录的最大文件数(1，100]；
[0025] 所述APK检测优先级是指APK所要满足的最晚检测开始时间，所需资源的最大数等条件，包括但不限于上述条件，可根据实际情况动态调整；
[0026] 所述虚拟机资源属性包括CPU指数、内存指数和线程指数，其中，
[0027] 所述CPU指数指的是CPU当前可被使用的资源与CPU原始可使用资源的比率；
[0028] 所述内存指数指的是内存当前空闲资源与内存原始可使用资源的比率，[0029] 所述线程指数指的是当前超线程中线程空闲数与原始线程数。
[0030] 进一步的，所述APK属性值包括APK文件的大小属性值、DEX文件的大小属性值、APK文件中代码复杂度属性值、APK文件中界面复杂度属性值、APK文件中资源文件复杂度属性值和APK检测优先级属性值，其中，
[0031] APK文件的大小属性值，具体为APK实际大小与可检测APK文件最大值之比乘以100；
[0032] APK文件中DEX文件的大小属性值，具体为APK中DEX的实际大小与可检测DEX文件的最大值之比乘以100；
[0033] APK文件中代码复杂度属性值，具体为DEX文件中代码的目录深度乘以可检测DEX文件的最大值30后除以最大目录深度10并加上DEX文件中文件总数乘以70后除以文件最大数1000得到；
[0034] APK文件中界面复杂度属性值，具体为APK文件的总界面数乘以单个界面控件的最多数除以设定的界面最大数与界面中控件的最大数的积，然后再乘100得到APK文件中界面复杂度属性值；
[0035] APK文件中资源文件复杂度属性值，具体为APK文件中Res文件下实际目录深度与实际目录最大数及实际目录文件的最大数之积除以设定的Res文件下的目录深度最大值与目录数最大值及目录中最大文件数的积，然后再乘以100得到PK文件中资源文件复杂度属性值；
[0036] APK检测优先级属性值，具体为最晚待检时间10减去最晚设定检测时间除以10后乘以100确定；
[0037] 所述虚拟机资源属性值包括CPU指数值、内存指数值和线程指数值，其中，[0038] 所述CPU指数值具体为CPU核心数与CPU主频及当前CPU未被使用率的乘积；
[0039] 所述内存指数值具体为CPU内存大小与当前内存未被使用率的乘积；
[0040] 所述线程指数值具体为线程数与当前线程未被使用率的乘积。
[0041] 所述APK属性对应的虚拟机资源的权重确定方式为：
[0042] 每个APK具有某些属性，而每个虚拟机拥有有限的资源，APK的属性决定了其在虚拟机中的分配结果；
[0043] 设影响APK分配的属性如下：
[0044] X1，X2，…，Xt，…，XT
[0045] 每个虚拟机的剩余资源种类如下：
[0046] R1，R2，…，Rt，…，RT
[0047] 由于虚拟机的某种资源与APK的某些属性相关联，从而决定APK的分配方式，所述关联的表达式为：
[0048] RS＝us1X1+us2X2+…+ustXt…+usTXT
[0049] 其中，
[0050] s＝1,2,3,4,5,6
[0051] t＝1,2,3,4,5,6
[0052] ust表示资源s与属性t之间关系,需同时满足0≤ust≤1和us1+us2+…+ust＝1两个条件；Rs表示某个APK分配到虚拟机后所占用的虚拟机S类资源。
[0053] 所述运行虚拟机的计算机建立并计算待检测APK属性值与虚拟机资源属性值函数的方式为：
[0054] 将N个APK(APKn|1≤n≤N)分配到M个虚拟机(Vm|1≤m≤M)上，即将N个APK分成M个簇，每个候选簇记为C′m；其满足如下约束条件：
[0055] 放入每个虚拟机中的APK所需资源之和不大于该虚拟机实际所拥有的资源，即为：
[0056] Xt∈{X1，X2，…，XT}且ust≠0
[0057] 其上需满足：
[0058] 优化目标一：最大可能地占用每台虚拟机的资源
[0059] Xt∈{X1，X2，…，XT}且ust≠0，
[0060]
[0061] 其中：m表示虚拟机个数，s表示资源种类
[0062] 优化目标二：对于优先级属性，属性值越高的APK优先分配
[0063]
[0064] 其中：i表示未被选中的APK，j表被选中的APK
[0065] 将以上两个优化目标进行拉格朗日加权，可得如下的综合目标函数：
[0066] Φ＝δΦ1+（1-δ）Φ2，其中，(0≤δ≤1)。
[0067] 所述运行虚拟机的计算机利用遗传算法确定最优APK分配方案的具体步骤为：
[0068] 步骤一：个体编码生成
[0069] 使用二进制编码，另外引入一个特殊的编码符号“×”表示禁止基因，禁止基因所对应的虚拟机与该APK性能不匹配或虚拟机处于忙碌状态，不能接受任务分配；在初始化时，禁止基因被分配编码“×”，并且在后面的遗传操作中都不会改变，即不考虑分配对应的APK给该虚拟机；因此，染色体上的基因有“0”、“1”、“×”三种编码，设第μ行第τ列的基因为则它的意义如下：
[0070]
[0071] 步骤二：初始群体的产生
[0072] 由于遗传算法是对群体进行操作的，确定初始群体的数据；
[0073] 骤三：进行适应度计算
[0074] 遗传算法中以所有虚拟机之和的适应度大小来评定整个分配方案的优劣，从而决定遗传机会的大小；
[0075] 所述适应度用 (i表示虚拟机的个数)度量， 越大被选中的概率就越大；
[0076] 步骤四：具体选择
[0077] 使用轮盘赌方法选择构成下一代的个体，任一个体被选择的概率等于其适应值与所有染色体适应值之和的比值，在此选择过程中，精英保留策略被采用，以确保获得的最优个体不被进一步的遗传操作所破坏，从而更有可能收敛到全局最优解；在交叉、变异等操作之后，如果新一代中最优个体的适应值小于上一代中最优个体的适应值，则上一代的最优个体被复制，并取代新一代中的最差个体；
[0078] 步骤五：交叉选择
[0079] 为了确保子代染色总是满足约束条件，使子代染色体总是问题的可行解，两个父代染色体矩阵中的一行或列以一定的交叉概率Pc被交换，交叉完成后，需在父染色体P1、P2和新染色体C1、C2之间进行选择，适应值较高的进入下一代，具体为：
[0080] O1＝max{fitne ss(P1)，fitne ss(C1)}，Q2＝max{fitness(P2)，fitness(C2)}[0081] 步骤六：变异
[0082] 变异运算是对个体的某一个或某一些基因上的基因值按某一较小的概率进行改变，它也是产生新个体的一种操作方法。本模型中我们采用位变异的方法，即从N行，M列中随机产生两个随机数p和q，则当满足下面两个条件的时候，将第p行q列的基因 从0变为1或者从1变为0，且需满足如下两个条件：条件1为基因 不是禁止基因，条件2为上述两个条件同时满足便可进行变异。
[0083] 本发明的优点在于：本发明是基于APK属性与虚拟机资源关系的提高APK检测速率与资源利用率的方法，使用该方法检测APK时，我们只需要对待检测APK属性与虚拟机资源属性建模，计算APK属性与虚拟机资源属性的关系函数，再通过遗传算法，计算APK的调度方案，根据调度方案将APK分配给虚拟机进行检测。由于在目前APK的发布与更新速度更快，所以使用该方法分配与检测APK时，速度更快，资源利用率更有效。
附图说明
[0084] 图1本发明所述技术方案中遗传算法对群体进行操作的初始群体表数据示意图；
[0085] 图2本发明所述技术方案中遗传算法的两个父代染色体矩阵中的一行(或列)以一定交叉概率Pc被交换示意图；
具体实施方式
[0086] 为使本发明的目的、技术方案和优点更加清楚明白，下文对本发明技术方案作进一步详细说明。需要说明的是，在不冲突的情况下，本申请的实施例和实施例中的特征可以任意相互组合。
[0087] 本发明提及的APK属性详细说明如下：
[0088] (1)对于APK文件的大小，用X1表示
[0089] APK文件的大小指的是文件本身占用存储空间的大小，单位为Mb。
[0090] 通常的，APK文件的组成包括：META-INF\，其主要记录文件的证书签名；res\，其主要用于存放资源文件的目录；AndroidManifest.xml，其主要用于程序全局配置文件；classes.dex，其主要用于存放Dalvik字节码；resources.arsc，其主要用于存放编译后的二进制资源文件。
[0091] 目前可检测的APK文件大小在(0，300)Mb之间，且大部分APK的大小在(5，50)Mb之间。测试结果表明，文件越大，所需的检测资源越大。
[0092] X1的值等于APK实际大小除以可检测APK文件的最大值300再乘以100，保留两位小数，公式如下：
[0093]
[0094] 例：APK的实际大小为34.5Mb，具体计算如下：
[0095] X1＝34.5÷300×100＝11.5
[0096] (2)对于APK文件中dex文件的大小，用X2表示
[0097] Dex文件的大小指的是APK文件中的扩展名为.dex文件的大小，单位Mb。
[0098] Dex文件的的大小在(0，30Mb)之间，且大部分dex文件的大小在(1，10Mb)之间，.dex文件越大，说明代码量越大，业务逻辑越复杂。
[0099] X2的值等于APK中Dex实际大小除以可检测Dex文件的最大值30再乘以100，保留两位小数，公式如下：
[0100]
[0101] 例：Dex的实际大小为4.5Mb，具体计算如下：
[0102] X2＝4.5÷30×100＝15
[0103] (3)APK文件中代码复杂度，用X3表示
[0104] 代码复杂度指的是dex文件中代码的目录深度与文件数的关系。
[0105] 代码复杂度设置范围为(1，100)，目录深度为(1，10]，超过10的以10计，类的文件数(1，1000]，超过1000的以1000计。
[0106] X3的值等包的深度值乘以30除10再加类的总数乘以70除1000，保留两位小数，公式如下：
[0107]
[0108] 例：包的深度为7，类的总数为452，代入公式具体如下：
[0109] X3＝7×30÷10+452×70÷1000＝62.64
[0110] (4)APK文件中界面复杂度，用X4表示
[0111] 界面复杂度指的是APK在运行过程中的界面数与界面中所使用控件的关系。
[0112] 界面复杂度指设置范围为(1，100)，界面总数为(1，100]，超过100的以100计，单个界面的控件总数(1，10]，超过10的以10计。
[0113] 的值等包的界面数乘以单个界面控件的最多数除以设定的界面最大数100，界面中控件的最大数10的积，再乘100，保留两位小数，公式如下：
[0114]
[0115] 例：包的界面数为36，界面中控件最多的是8，代入公式具体如下:
[0116] X4＝36×8÷(100×10)×100＝28.8
[0117] (5)APK文件中资源文件复杂度，用X5表示
[0118] 资源文件复杂度指的是APK中res目录下目录的层级与下面目录和文件数之间的关系。
[0119] 资源文件的复杂度设置范围为(1，100)，目录深度为(1，5]，每级最大目录数(1，10]，每个目录的最大文件数(1，100]。(根据情况持续改进)
[0120] 的值等于APK中Res实际目录深度、实际目录最大数、实际目录文件的最大数之积除以设定的Res的目录深度最大值5、目录数最大值10、目录中最大文件数100的积，再乘以100保留两位小数，公式如下：
[0121]
[0122] 例：Res的实际目录深度为3，最大目录数为8，最大文件数为30，具体计算如下：
[0123] X5＝(3×8×20)÷(5×10×100)×100＝9.6
[0124] (6)APK检测优先级，用X6表示
[0125] 优先级指的是APK所要满足的最晚检测开始时间，所需资源的最大数等条件，包括但不限于上述条件。
[0126] 目前设置的范围(1，100)，最晚检测的时间以小时为单位，再乘以100保留两位小数，公式如下：
[0127]
[0128] 例：最晚检测时间为8小时30分，具体计算如下：
[0129] X6＝((10-8)×60-30)÷(10×60)×100＝15
[0130] 本发明提及的虚拟机的资源属性值具体如下：
[0131] (1)CPU指数，用表示
[0132] CPU指数指的是CPU当前可被使用的资源与CPU原始可使用资源的比率，计算公式CPU核心数×CPU主频×(1-CPU当前使用率)。
[0133] (2)内存指数，用表示
[0134] 内存指数指的是内存当前空闲资源与内存原始可使用资源的比率，计算公式CPU内存大小×(1-内存当前使用率)。
[0135] (3)线程指数，用表示
[0136] 线程指数指的是当前超线程中线程空闲数与原始线程数，计算公式线程数×(1-线程当前使用率)。
[0137] 依据上述分析的APK的属性得到一个所需检测资源的计算单位，再根据检测资源本身所对应的属性，通过下面的算法到一个值。
[0138] 每个APK具有某些属性，而每个虚拟机拥有有限的资源，APK的属性决定了其在虚拟机中的分配结果；
[0139] 设影响APK分配的属性如下：
[0140] X1，X2，…，Xt，…，XT
[0141] 每个虚拟机的剩余资源种类如下：
[0142] R1，R2，…，Rt，…，RT
[0143] 由于虚拟机的某种资源可能与APK的某些属性相关联，从而决定APK的分配方式，我们将这种关联用数学形式表示如下：
[0144] Rs＝us1X1+us2X2+…+ustXT…+usTXT
[0145] 其中，各参数的含义为：
[0146] s＝1,2,……,S
[0147] t＝1,2,……,T
[0148] ust表示资源s与属性t之间关系,需同时满足0≤ust≤1和us1+us2+…+ust＝1两个条件；Rs表示某个APK分配到虚拟机后所占用的虚拟机S类资源。
[0149] APK属性与虚拟机资源的关联具体举例分析如下：
[0150] 某APK将会进行静态检测，且APK的各属性描述如下：
[0151] 文件大小为25.7Mb；
[0152] 其中dex文件大小为1.3Mb；
[0153] dex文件中最大目录深度为7级，总文件数为358个；
[0154] 所拥有界面数为26，界面中最多的集成了9个控件；
[0155] 源文件目录中最大目录深度为4级，单个目录下最多的目录数是7个，单个目录下最多的文件数是84个；
[0156] 依据上述属性描述，将属性代入Rs＝us1X1+us2X2+…+ustXt…+usTXT会得到下面的公式：
[0157] Ｒ1＝u11X1+u12X2+u13X3+u14X4+u15X5
[0158] APK属性及计算结果：
[0159] X1＝8.6、X2＝4.3、X3＝46、X4＝23.4、X5＝47
[0160] APK属性与虚拟机资源关联关系：
[0161] u11＝0.15、u12＝0.35、u13＝0.35、u14＝0.05、u15＝0.1
[0162] 将上面各结果代入公式得到如下结果：
[0163] R1＝0.15×8.6+0.35×4.3+0.35×46+0.05×23.4+0.1×47＝24.76。
[0164] 现将N个APK{APKn|1≤n≤N}分配到M个虚拟机{Vm|1≤m≤M}上，即将N个APK分成M个簇，每个候选簇记为C′m；其满足如下约束条件：
[0165] 放入每个虚拟机中的APK所需资源之和不大于该虚拟机实际所拥有的资源，即为：
[0166] Xi∈{X1，X2，…，XT}且ust≠0
[0167] 其上需满足：
[0168] 优化目标一：最大可能地占用每台虚拟机的资源
[0169] Xt∈{X1，X2，…，XT}且ust≠0，
[0170]
[0171] 其中：m表示虚拟机个数，s表示资源种类
[0172] 优化目标二：对于优先级属性，属性值越高的APK优先分配
[0173]
[0174] 其中：i表示未被选中的APK，j表被选中的APK
[0175] 将以上两个优化目标进行拉格朗日加权，可得如下的综合目标函数：
[0176] Φ＝δΦ1+(1-δ)Φ2，其中，(0≤δ≤1)。
[0177] 基于上述分析，利用遗传算法找到最优分配方案，具体包括如下步骤：
[0178] 步骤一：个体编码生成
[0179] 使用二进制编码，另外引入一个特殊的编码符号“×”表示禁止基因，禁止基因所对应的虚拟机与该APK性能不匹配或虚拟机处于忙碌状态，不能接受任务分配。在初始化时，禁止基因被分配编码“×”，并且在后面的遗传操作中都不会改变，意味着不考虑分配对应的APK给该虚拟机。因此，染色体上的基因有“0”、“1”、“×”三种编码，设第行第列的基因为，则它的意义如下：
[0180]
[0181] 步骤二：初始群体的产生
[0182] 如图1所述，遗传算法是对群体进行操作的，其给定了初始群体的数据；
[0183] 步骤三：进行适应度计算
[0184] 遗传算法中以所有虚拟机之和的适应度大小来评定整个分配方案的优劣，从而决定遗传机会的大小；本模型中适应度用 (i表示虚拟机的个数)度量， 越大被选中的概率就越大；
[0185] 步骤四：具体选择
[0186] 使用轮盘赌方法选择构成下一代的个体，任一个体被选择的概率等于其适应值与所有染色体适应值之和的比值；在此选择过程中，精英保留策略被采用，以确保获得的最优个体不被进一步的遗传操作所破坏，从而更有可能收敛到全局最优解；在交叉、变异等操作之后，如果新一代中最优个体的适应值小于上一代中最优个体的适应值，则上一代的最优个体被复制，并取代新一代中的最差个体；例如，设父代染色体种群为：
[0187] P＝{A1，X2，…，Ai，…Aj，…As}
[0188] 而交叉、变异后获得的新种群为：
[0189] Q＝{B1，B2，…Bm，…Bn，…Bs}
[0190] 其中，Ai和Aj,Bm和Bn分别是父代种群和新种群中的最优和最差个体，如果适应值fitness(Bm)＜fitness(Ai)，那么下一代子种群更新如下：
[0191] O＝{B1，B2，…Bm，…Ai，…Bs}
[0192] 步骤五：交叉选择
[0193] 如图2所示，为了确保子代染色总是满足约束条件，使子代染色体总是问题的可行解，两个父代染色体矩阵中的一行(或列)以一定的交叉概率Pc被交换；
[0194] 交叉完成后，需在父染色体P1、P2和新染色体C1、C2之间进行选择，适应值较高的进入下一代：
[0195] Q1＝max{fitness(P1)，fitness(C1)}，Q2＝max{fitness(P2)，fitness(C2)}[0196] 步骤六：变异
[0197] 变异运算是对个体的某一个或某一些基因上的基因值按某一较小的概率进行改变，它也是产生新个体的一种操作方法。本模型中我们采用位变异的方法，即从N行，M列中随机产生两个随机数p和q，则当满足下面两个条件的时候，将第p行q列的基因 从0变为1或者从1变为0，且需满足如下两个条件：条件1为基因 不是禁止基因，条件2为上述两个条件同时满足便可进行变异。
[0198] 以上对本发明进行了详细介绍，本文中应用了实施例对本申请的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本申请的方法及其核心思想；同时，对于本领域的一般技术人员，依据本申请的思想，在具体实施方式及应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对本申请的限制。
