CN105528283B - 一种移动应用检测负载均衡算法中计算负载值的方法 - Google Patents

Abstract

本发明公开了一种移动应用检测负载均衡算法中计算负载值的方法，基于由客户端、中心管理节点模块和检测节点组成的实验平台实现；检测节点的心跳包括：当前检测节点的CPU加权负载值，内存加权负载值，队列加权负载值和控制流复杂度加权负载值；中心管理节点模块接受移动应用检测任务和检测子节点的心跳；通过实时接收各检测节点的心跳得到当前各检测节点的负载情况，并通过负载调度器选择出其中最优的检测节点下发移动应用检测任务，然后重新计算各检测节点的负载分数，更新记录的负载信息。优点在于，极大提高了海量移动应用检测任务的执行效率，能满足现今海量应用快速检测的需求；更加合理有效的向检测节点分配任务。

Description

一种移动应用检测负载均衡算法中计算负载值的方法

技术领域

本发明属于信息安全领域，涉及移动应用检测负载均衡的优化方法，具体是一种移动应用检测负载均衡算法中计算负载值的方法。

背景技术

由于移动应用检测任务具有特殊性，难以将其切分为更细粒度的子文件，更不可能对单个移动应用检测任务进行简单粗暴的平均大小切分，导致单个移动应用检测任务内的移动应用大小差别迥异，影响移动应用检测任务的执行效率。另外，影响移动应用检测任务的执行效率的另一个因素是单个移动应用检测任务内的控制流复杂度。

控制流复杂度是指由移动应用检测任务内部的执行流程和执行复杂度，由控制流图中的边数和节点数体现；

控制流图(CFG,Control flow graph，即控制流程图)，是一个过程或程序的抽象表现。移动应用检测任务的控制流图，即移动应用中语句、语句块和过程的执行流抽象。控制流图是一个有向图，包含N个节点node和M条边edge。

现有技术中采用McCabe复杂度度量标准，将软件的流程图转化为有向图，控制流图是McCabe复杂度计算的基础，McCabe复杂度度量作为移动应用检测任务的环路复杂性度量标准，一般用圈复杂度V(G)描述。实验证明，圈复杂度越大的移动应用，静态检测时间越长。

圈复杂度的计算方法如下：

V(G)＝e-n+2

其中e为移动应用检测任务中控制流图中边数，n为移动应用检测任务中控制流图中的节点数。

负载均衡(Load Balancing)算法目的是为了提高任务执行效率，提高系统吞吐量，利用分布式结构提高系统执行性能。通过平衡各检测节点的负载情况，加强了各检测节点的数据处理能力、提高了可用性。各检测节点的负载包括：各检测节点上所有移动应用检测任务的网络吞吐量、CPU负载率、内存使用率等；

在传统负载均衡算法中，一般使用CPU使用率、内存占用率、硬盘使用情况、网络吞吐量等作为服务器负载的衡量标准。

但是，在海量移动应用检测任务的应用场景下，由于移动应用文件小，在检测过程中，服务器硬盘的使用情况不会有很大的变化，硬盘使用量对移动应用的检测影响较小；而由于移动应用的存储和检测都在局域网环境下完成，局域网内网络情况良好，小文件对网络带宽要求不高，因此网络吞吐量对移动应用的检测效率也无明显影响。

在海量移动应用检测任务的应用场景下，使用ActiveMQ将移动应用检测任务存储在队列服务器上，通过ActiveMQ提供的API获取移动应用检测任务的队列大小，并配置队列最大长度，而检测任务队列的大小是衡量一个检测任务需要等待的时间和预计返回时间的最直接因素。

综上，针对海量移动应用检测任务，传统负载均衡算法中，只考虑了影响负载均衡的以下几类因素：1)、检测节点的CPU负载，包括CPU核数、CPU频率、CPU使用百分比；2)、检测节点的内存负载，包括空闲内存百分比；3)、检测节点的任务队列负载，包括任务队列长度和任务队列最大长度。

如若不考虑控制流复杂度，将会使整个检测效率下降50％以上。在有多节点以及海量应用需要检测的情况下，检测时间将会延迟超过1分钟，无法满足现阶段海量移动应用检测的需求。

发明内容

本发明针对海量移动应用检测任务的处理请求，为了提高多线程并行处理效率，结合现有的负载均衡计算方法，引入控制流复杂度作为检测节点的负载信息，提出了一种移动应用检测负载均衡算法中计算负载值的方法，能短时检测大量移动应用。

具体步骤如下：

步骤一、针对每个检测节点，分别计算该检测节点上每个移动应用检测任务的控制流复杂度Complexity；

采用McCabe复杂度度量标准，获取每个移动应用检测任务的控制流图，从而获取该控制流图的边数和节点数，计算控制流复杂度Complexity；

Complexity_j＝e_j-n_j+2

Complexity_j为第j个移动应用检测任务的控制流复杂度；j为待检测的移动应用检测任务的序号，j为整数；e_j为第j个移动应用检测任务的控制流图的边数，n_j为第j个移动应用检测任务的控制流图的节点数。

步骤二、计算每个检测节点上的所有移动应用检测任务的CPU加权负载，内存加权负载，队列加权负载和控制流复杂度加权负载值之和LoadGrade：

LoadGrade_i＝Cw+Mw+Qw+Comw

其中，LoadGrade_i为检测节点i的加权负载值之和；i为检测节点的序号，i为整数；Cw为检测节点i的CPU加权负载值：Cw＝w_cpu*CPUGrade_i；w_cpu是CPU加权负载值的权重；CPUGrade_i为检测节点i的CPU负载值：

CPUCores_i为检测节点i的CPU核数，单位为个；CPUGHz_i为检测节点i的CPU主频，单位为GHz；CPUUsedPerc_i为检测节点i的CPU使用百分比，单位为％。

Mw为检测节点i的内存加权负载值：Mw＝w_memory*MemoryGrade_i；w_memory是内存加权负载值的权重，MemoryGrade_i为检测节点i的内存负载值：

FreeMemory_i为检测节点i的当前空闲内存，单位为％。

Qw为检测节点i的队列加权负载值：Qw＝w_queue*QueueGrade_i；w_queue是队列加权负载值的权重，QueueGrade_i为检测节点i的任务队列负载值：

QueueCapacity_i为检测节点i的任务队列容量即检测节点i的任务队列最大长度，单位为个；QueueNum_i为检测节点i的任务队列当前任务数量即队列大小，单位为个。

Comw为检测节点i的控制流复杂度加权负载值：

Comw＝w_complexity*ComplexityGrade_i

w_complexity为移动应用检测节点的控制流复杂度的权重，ComplexityGrade_i为移动应用检测节点i的控制流复杂度负载值:

Complexity_maxi为时隙T内检测节点i的任务队列中等待检测任务的Complexity之和的最大值；Complexity_averagei为时隙T内检测节点i的任务队列中等待检测任务的Complexity平均值：

∑_TComplexity_j表示在时隙T内检测节点i的等待在任务队列上所有检测任务的Complexity之和，n表示时隙T内的n个移动应用。

检测节点i的各类加权值满足：w_cpu+w_memory+w_queue+w_Complexity＝100

w_cpu,w_memory,w_queue,w_Complexity∈[0,100]

步骤三、将每个检测节点的加权负载值之和LoadGrade的信息包裹在节点心跳中；

步骤四、节点心跳每隔时隙T发送一次给负载调度器，负载调度器计算各个检测节点，将下一个移动应用检测任务分配给LoadGrade最小的检测节点。

本发明的优点在于：

1)、一种移动应用检测负载均衡算法中计算负载值的方法，极大提高了海量移动应用检测任务的执行效率，能满足现今海量应用快速检测的需求。

2)、一种移动应用检测负载均衡算法中计算负载值的方法，用更加合理有效的方式向节点分配任务，保证了节点的充分运作的同时又防止其负荷超载，有利于维护节点寿命。

附图说明

图1是本发明移动应用控制流复杂度与静态检测时间的关系图；

图2是本发明一种移动应用检测负载均衡算法中计算负载值的方法流程图；

图3是本发明与轮询调度法，传统的移动应用检测任务负载均衡算法的时间统计与比较图。

具体实施方式

下面将结合附图对本发明作进一步的详细说明。

如图1所示，随着移动应用控制流复杂度的增加，移动应用的静态检测时间也逐渐增长，移动应用检测效率逐渐降低，因此，可以将移动应用的控制流复杂度作为负载均衡算法的一个参数，让每个检测节点的任务队列上所等待任务的控制流复杂度之和趋于平衡，提高批量执行移动应用检测时的检测性能。

本发明一种移动应用检测负载均衡算法中计算负载值的方法，在海量移动应用检测任务的场景中引入动态反馈负载均衡算法，考虑服务器的实时负载和响应情况，不断调整节点间处理任务数的比例，来避免任务节点在超载时依然收到大量请求，均衡分布式系统中任务节点的负载情况，从而提高整个系统的吞吐率和任务执行效率。

该方法基于由客户端、中心管理节点模块和检测子节点组成的实验平台实现；

检测节点的心跳包括：当前检测节点i的CPU加权负载值，内存加权负载值，队列加权负载值和控制流复杂度加权负载值；

中心管理节点模块接受移动应用检测任务和检测子节点的心跳；通过实时接收各检测节点的心跳得到当前各检测节点的负载情况，并通过负载调度器选择出其中最优的检测节点下发移动应用检测任务，然后重新计算各检测节点的负载分数，更新记录的负载信息。

中心管理节点模块分为心跳接收引擎、负载值计算引擎和检测子节点资源队列三部分。心跳接受引擎接收到检测子节点发来的心跳信息后，将其中的负载信息取出传递给负载值计算引擎；负载值计算引擎根据节点负载信息计算出节点的实时负载值后，根据负载值的大小重排检测子节点资源队列。负载调度器接收到移动应用检测任务后，可以直接分配到负载分数最大，负载最低节的检测子节点；

负载调度器作用是监视和收集各个服务器的负载信息，根据多个负载信息算出一个综合负载值。当综合负载值表示服务器比较忙时，该检测节点的优先级较小，这样新分配到该服务器的移动应用检测任务的请求数就会少一些。当综合负载值表示服务器处于低利用率时，检测节点的优先级较大，以此来增加新分配到该服务器的请求数。

如图2所示，具体步骤如下：

步骤一、针对每个检测节点，分别计算该检测节点上每个移动应用检测任务的控制流复杂度Complexity；

采用McCabe复杂度度量标准，获取每个移动应用检测任务的控制流图，从而获取该控制流图的边数和节点数，计算控制流复杂度Complexity；

Complexity_j＝e_j-n_j+2

Complexity_j为第j个移动应用检测任务的控制流复杂度；j为待检测的移动应用检测任务的序号，j为整数；e_j为第j个移动应用检测任务的控制流图的边数，n_j为第j个移动应用检测任务的控制流图的节点数。

其中，采用McCabe复杂度度量标准，获取每个移动应用检测任务的控制流图的边数和节点数，是通过使用Android的逆向工具Androguard对移动应用进行预处理：Androguard是一个用python编写的Android移动应用静态分析工具，包含多个模块，其中androgexf.py即可生成Android移动应用的控制流图。由于McCabe算法仅需获取移动应用控制流图的边数和节点数，同时为了加快执行效率，仅返回控制流图的边数和节点数。对Android移动应用秒级完成如上预处理，大大少于静态检测时间。

步骤二、计算每个检测节点上的所有移动应用检测任务的CPU加权负载，内存加权负载，队列加权负载和控制流复杂度加权负载值之和LoadGrade：

LoadGrade_i＝Cw+Mw+Qw+Comw

其中，LoadGrade_i为检测节点i的加权负载值之和；i为检测节点的序号，为整数；本实施例选用10个移动应用静态检测子节点，Cw为检测节点i的CPU加权负载值：Cw＝w_cpu*CPUGrade_i；w_cpu是CPU加权负载值的权重；CPUGrade_i为检测节点i的CPU负载值：

CPUCores_i为检测节点i的CPU核数，单位为个；CPUGHz_i为检测节点i的CPU主频，单位为GHz；CPUUsedPerc_i为检测节点i的CPU使用百分比，单位为％。

Mw为检测节点i的内存加权负载值：Mw＝w_memory*MemoryGrade_i；w_memory是内存加权负载值的权重，MemoryGrade_i为检测节点i的内存负载值：

FreeMemory_i为检测节点i的当前空闲内存，单位为％。

Qw为检测节点i的队列加权负载值：Qw＝w_queue*QueueGrade_i；w_queue是队列加权负载值的权重，QueueGrade_i为检测节点i的任务队列负载值：

QueueCapacity_i为检测节点i任务队列容量即最大长度，单位为个；QueueNum_i为检测节点i的任务队列当前任务数量即队列大小，单位为个。

Comw为检测节点i的控制流复杂度加权负载值：

Comw＝w_complexity*ComplexityGrade_i

w_complexity为移动应用检测节点的控制流复杂度的权重，ComplexityGrade_i为移动应用检测节点i的控制流复杂度负载值:

Complexity_maxi为时隙T内检测节点i的任务队列中等待检测的Complexity之和的最大值；Complexity_averagei为时隙T内检测节点i的任务队列中等待检测的Complexity平均值，平均控制流复杂度越大，该检测节点的控制流复杂度负载值越低。

∑_TComplexity_j表示在时隙T内检测节点i的等待在任务队列上所有Complexity之和，n表示时隙T内的n个移动应用。

其中

检测节点i的各类加权值满足：w_cpu+w_memory+w_queue+w_Complexity＝100

w_cpu,w_memory,w_queue,w_Complexity∈[0,100]

步骤三、将每个检测节点的加权负载值之和LoadGrade_i的信息包裹在节点心跳中；

各检测节点将上述负载信息包裹在节点心跳中，节点心跳选用JAVA类，提供了外部接口设置和访问节点的负载信息。

步骤四、节点心跳每隔时隙T发送一次给负载调度器，负载调度器计算各个检测节点，将下一个移动应用检测任务分配给LoadGrade最小的检测节点；

时隙T选用15秒，中心管理节点模块每15秒对各检测节点的负载分数进行更新，得到海量移动应用检测任务中各检测节点的负载值。负载值较高的检测节点优先级较低，负载值较低的检测节点优先级较高，负载值最低的检测节点将接受下一个移动应用检测任务。

选用检测节点分别为2、4、6、8、10个，统计在批量下发500个不同大小及控制流复杂度的应用检测任务时，通过传统的轮询调度法、移动应用检测任务负载均衡算法、以及本发明的引入移动应用控制流复杂度的负载均衡算法进行对比。

如图3所示，本发明与轮询调度法，传统的移动应用检测任务负载均衡算法在不同数量引擎之下，进行任务分配时的时间统计和比较图，可以看出，本发明算法中，各检测节点的执行效率均高于其他两种算法，而且，比移动应用检测任务负载均衡算法提高了54.1％的效率。使用本发明更有利于分布式系统的负载均衡并提高系统的执行效率。

通过使用本发明，统计57691个移动应用检测任务的平均时间为31.413s，其实验结果可以有效反应改进的移动应用检测任务负载均衡算法对海量移动应用检测任务的效率提升。

Claims (1)

1.一种移动应用检测负载均衡算法中计算负载值的方法，其特征在于，包括以下步骤：

步骤一、针对每个检测节点，分别计算该检测节点上每个移动应用检测任务的控制流复杂度Complexity；

通过每个移动应用检测任务的控制流图，获取该控制流图的边数和节点数，计算控制流复杂度Complexity；

Complexity_j＝e_j-n_j+2

Complexity_j为第j个移动应用检测任务的控制流复杂度；j为待检测的移动应用检测任务的序号；e_j为第j个移动应用检测任务的控制流图的边数，n_j为第j个移动应用检测任务的控制流图的节点数；

步骤二、计算每个检测节点上的所有移动应用检测任务的CPU加权负载，内存加权负载，队列加权负载和控制流复杂度加权负载值之和LoadGrade：

LoadGrade_i＝Cw+Mw+Qw+Comw

其中，LoadGrade_i为检测节点i的加权负载值之和；i为检测节点的序号；Cw为检测节点i的CPU加权负载值：Cw＝w_cpu*CPUGrade_i；w_cpu是CPU加权负载值的权重；CPUGrade_i为检测节点i的CPU负载值：

<mrow> <msub> <mi>CPUGrade</mi> <mi>i</mi> </msub> <mo>=</mo> <mfrac> <mrow> <msub> <mi>CPUCores</mi> <mi>i</mi> </msub> <mo>*</mo> <msub> <mi>CPUGHz</mi> <mi>i</mi> </msub> <mo>*</mo> <mrow> <mo>(</mo> <mn>100</mn> <mo>-</mo> <msub> <mi>CPUUsedPerc</mi> <mi>i</mi> </msub> <mo>)</mo> </mrow> </mrow> <mn>100</mn> </mfrac> </mrow>

CPUCores_i为检测节点i的CPU核数；CPUGHz_i为检测节点i的CPU主频；CPUUsedPerc_i为检测节点i的CPU使用百分比；

Mw为检测节点i的内存加权负载值：Mw＝w_memory*MemoryGrade_i；w_memory是内存加权负载值的权重，MemoryGrade_i为检测节点i的内存负载值：

<mrow> <msub> <mi>MemoryGrade</mi> <mi>i</mi> </msub> <mo>=</mo> <mfrac> <mrow> <msub> <mi>FreeMemory</mi> <mi>i</mi> </msub> </mrow> <mn>100</mn> </mfrac> </mrow>

FreeMemory_i为检测节点i的当前空闲内存；

Qw为检测节点i的队列加权负载值：Qw＝w_queue*QueueGrade_i；w_queue是队列加权负载值的权重，QueueGrade_i为检测节点i的任务队列负载值：

<mrow> <msub> <mi>QueueGrade</mi> <mi>i</mi> </msub> <mo>=</mo> <mfrac> <mrow> <msub> <mi>QueueCapacity</mi> <mi>i</mi> </msub> <mo>-</mo> <msub> <mi>QueueNum</mi> <mi>i</mi> </msub> </mrow> <mrow> <msub> <mi>QueueCapacity</mi> <mi>i</mi> </msub> </mrow> </mfrac> </mrow>

QueueCapacity_i为检测节点i的任务队列容量即检测节点i的任务队列最大长度；QueueNum_i为检测节点i的任务队列当前任务数量即队列大小；

Comw为检测节点i的控制流复杂度加权负载值：

Comw＝w_complexity*ComplexityGrade_i

w_complexity为移动应用检测节点的控制流复杂度的权重，ComplexityGrade_i为移动应用检测节点i的控制流复杂度负载值:

<mrow> <msub> <mi>ComplexityGrade</mi> <mi>i</mi> </msub> <mo>=</mo> <mfrac> <mrow> <msub> <mi>Complexity</mi> <mrow> <mi>max</mi> <mi>i</mi> </mrow> </msub> <mo>-</mo> <msub> <mi>Complexity</mi> <mrow> <mi>a</mi> <mi>v</mi> <mi>e</mi> <mi>r</mi> <mi>a</mi> <mi>g</mi> <mi>e</mi> <mi>i</mi> </mrow> </msub> </mrow> <mrow> <msub> <mi>Complexity</mi> <mrow> <mi>max</mi> <mi>i</mi> </mrow> </msub> </mrow> </mfrac> </mrow>

Complexity_maxi为时隙T内检测节点i的任务队列中等待检测任务的Complexity之和的最大值；Complexity_averagei为时隙T内检测节点i的任务队列中等待检测任务的Complexity平均值：

<mrow> <msub> <mi>Complexity</mi> <mrow> <mi>a</mi> <mi>v</mi> <mi>e</mi> <mi>r</mi> <mi>a</mi> <mi>g</mi> <mi>e</mi> <mi>i</mi> </mrow> </msub> <mo>=</mo> <mfrac> <mrow> <msub> <mo>&amp;Sigma;</mo> <mi>T</mi> </msub> <msub> <mi>Complexity</mi> <mi>j</mi> </msub> </mrow> <mi>n</mi> </mfrac> </mrow>

∑_TComplexity_j表示在时隙T内检测节点i的等待在任务队列上所有检测任务的Complexity之和，n表示时隙T内的n个移动应用；

检测节点i的各类加权值满足：w_cpu+w_memory+w_queue+w_Complexity＝100

w_cpu,w_memory,w_queue,w_Complexity∈[0,100]

步骤三、将每个检测节点的加权负载值之和LoadGrade的信息包裹在节点心跳中；

步骤四、节点心跳每隔时隙T发送一次给负载调度器，负载调度器计算各个检测节点，将下一个移动应用检测任务分配给LoadGrade最小的检测节点。