面向应用检测任务的负载均衡算法研究

黄高攀 何金陵 庄岭 张利

摘要：随着移动应用数量剧增，移动应用安全检测的需求日益增大，面向海量移动应用检测平台的效率显得愈发重要。然而现有的负载均衡算法在负载因子的度量上存在局限性和效率问题。分析了已有调度算法中负载因子度量的不足，结合现有的移动应用检测方法的特性，引入了移动应用软件规模作为负载因子。根据该算法，设计了一个移动应用检测平台，通过实验验证，该算法有效避免了海量任务下检测节点负载不均衡的问题，加快了移动应用的检测效率，提高了海量移动应用检测平台的吞吐量，取得良好效果。

关键词：载均衡;海量移动应用;软件规模;静态检测;文件特征

中图分类号：TP311.5

文献标识码：A

随着移动智能终端的快速普及和功能的日趋强大，移动应用数量正以前所未有的速度呈爆炸性增长。目前国内Android第三方应用商店有几百家，市场上可供下载的应用数量不计其数。这些移动应用在给用户的生活带来便利的同时，也引发了一些安全问题。360互联网安全中心发布的《2017年中国手机安全状况报告》指出[1]，2016全年，360互联网安全中心累计截获Android平台恶意程序样本1403.3万个，Android用户感染恶意程序2.53亿，平均每天新增3.8万恶意程序样本。因此，面向海量移动应用检测平台的效率显得愈发重要。 对分布式调度任务而言，如海量日志分析，可对文件进行简单的切分，再进行均衡调度分析[2]。但是对于Android应用而言，内部文件间相互关联，无法将应用切分为更小文件孤立分析，从而导致单个应用检测时间跨度很大[3]。因此，为了检测任务调度的均衡性，现有海量移动应用检测平台添加了移动应用检测任务量作为负载均衡因素，然而在对检测任务量的评估过程中，仍存在考虑不全面且效率较低的问题[4-6]。针对目前负载均衡算法中对负载因子度量存在的不足，提出一种基于应用内部文件特征的海量移动应用检测调度算法。

1 移动应用软件规模

Android应用检测的关注点是应用中代码的逻辑和数据的信息[7]，因此应用的软件规模直接影响到检测任务量。软件工程中是通过代码的行数对软件规模进行度量。

对Android应用而言，其主要包括Java和C两类程序设计语言[8]。在本文的研究场景中，分析的对象是打包后的Android应用程序，因此和常规的Java或C工程不同，难以基于源码行数[9]进行软件规模衡量。获取应用程序源码信息需要进行反汇编反编译等操作[10]，耗时长且准确度较低，并且dalvik虚拟机和CPUAndroid运行时是直接读取并执行底层指令，因此底层指令的规模更能体现移动应用软件规模。

具体来说，Android应用中Java代码会被编译成dex文件[11]，运行在dalvik虚拟机上。当Android程序运行时，dalvik虚拟机会从dex文件中取出方法的dalvik指令，逐条运行。因此Android中Java的规模，是通过dalvik指令的规模决定的。

Android应用引用的C代码通常被编译成so动态链接库，动态链接库不是交由dalvik虚拟机解释执行，而是直接由手机的处理器CPU解析汇编指令执行。因此Android中C语言的规模，是由动态链接库arm指令的规模决定的。

综上本文会结合不同文件的特性，去衡量软件规模，从而进一步度量检测的任务量。

1.1 移动应用软件规模度量方法

Android应用后缀名为apk。通过解压缩观察到其包括AndroidManifest.xml、META -INF、Dex、So、resources.arsc等。AndroidManifest.xml、Dex、So是敏感信息出现的多发区[12]，也是我们安全分析的重点。

结合apk内不同文件的特性和检测流程，我们快速地提取文件的特征参数计算移动应用软件规模。对于AndroidManifest.xml文件，我们提取其文件大小作为其特征参数;对于class.dex文件，我们提取文件头中的变量个数、方法个数、类个数作为其特征参数;对于s0链接库，我們提取SHT中的代码段大小、数据段大小作为其特征参数[13]。不同文件有不同的规模计算公式。整个应用的软件规模为有效文件规模的加权和。

1.1.1 AndroidManifest

AndroidManifest解析只涉及信息提取，步骤比较简单。由于XML通用的标记结构，AndroidMani-fest的检测时间随文件大小呈正相关。用Complexity_{AndrocdManifest}来衡量AndroidManifest的文件规模，Complexity_{AdrocdManifes}等于APK中AndroidManifest实际大小，公式如下：

Complexity_{AndrocdManifest}=Size_{AndrocdManifest}

（1）

1.1.2 Dex

目前针对Android应用程序dex的静态分析技术，主要是通过反编译dex文件，获取smali文件，然后解析smali文件内部的每条指令，建立程序控制流图，后续再针对控制流图展开进一步的分析。因此，smali指令的数量会影响dex静态分析的工作量[14]。本文通过dex文件结构的特性，快速统计所有方法中的指令数量，作为dex文件规模的衡量因子。

Dex文件结构如图1所示，structDexCode中的表示指令集的个数。

通过遍历dex中的所有class信息，针对每个class遍历所有的method信息，获取method中的指令个数。具体提取过程如下：

输入：Android Dex文件——Dex

输出：Android Dex文件规模-insnsSize

BEGIN

insnsSize←0

for DexClassDef in Dex.DexClassDefs

DexClassData←-DexClassDef.classDataOff

directMethods←DexClassData.directMethod

for directMethod in directMethods

DexCode←-directMethod. codeOff

insnsSize←insnsSize+ DexCode.insnsSize

end for

virtualMethod←DexClassData.virtualMethod

for virtualMethod in virtualMethod

DexCode←virtualMethod. codeOff

insnsSize←insnsSize+ virtualMethod.codeOff

end for

用Complexity&x来衡量dex的文件规模，公式如下：

1.1.3 So链接厍

针对so文件的静态分析，首先会进行反汇编操作，将so中的二进制信息转化成汇编代码[15]，再结合代码区和数据区进行控制流和数据流的分析。因此，本文通过so文件中的代码区和数据区的大小来衡量s0文件检测的文件规模。

Android中的s0文件是elf格式。根据elf文件的结构定义，其包含：ELF头、区信息表、段信息表、以及各区详细信息等。

Section Header Table（SHT）记录了每个section的名称、类型、大小以及在整个ELF文件中的字节偏移位置等信息。常见的Section有.text、.data、.bss、.got。其中，代码段.text，数据段.data和.bss包含重要的信息，也是检测引擎的分析对象，其大小和检测时间呈正相关。

因此本文通过解析Section Header Table获取了.text的大小textSize，.data的大小dataSize和.bss的大小bssSize。

用变量Complexitys。来衡量s0的文件规模，公式如下：

Complexitys.=textSize+ dataSize+bssSize （3）

1.1.4 移动应用软件规模

应用的软件规模为所有文件规模的加权和。Complexity AndrocdManifest为应用AndroidManifest文件的规模，Complexity Dex为应用Dex文件的规模，Com-plexitys。为应用So文件的规模。WAndroidManifest、WDex、W So分别为AndroidManifest文件、Dex文件、So文件的權值。本文选取了500个移动应用，在正常检测的过程中分别统计AndroidManifest、Dex、So的检测时长，并计算三类文件的单位规模检测时长，最后计算得出三者之间的比例为Androidmanifest：Dex：So=1：10：13，故本文按上述比例设置相应权值。

1.2 移动应用软件规模对检测的影响

选取了检测时间Ss到40分钟内的500个移动应用，对其进行应用软件规模和检测时间的统计比对。移动应用软件规模的度量采用公式（4），发现应用软件规模和静态检测时间呈正相关，随着应用软件规模的增加，移动应用检测时间增长。实验数据统计如图3所示。

从图3中可以看出，移动应用检测时间与应用软件规模回归方程方差大于9，明显正相关。随着移动应用软件规模的增加，移动应用的静态检测时间也逐渐增长。因此，可以将移动应用的软件规模作为负载均衡算法的一个参数，让每个检测节点的任务队列上所等待任务的软件规模之和趋于平衡，则在批量执行移动应用的检测任务时，检测性能将大大提高。

2 基于移动应用软件规模的任务调度

2.1 平台设计

移动应用检测平台由客户端、中心管理节点、检测子节点组成。其中，中心管理节点接受检测任务根据检测子节点的负载情况，选择最优节点下发检测任务;接受检测子节点心跳，重新计算检测机节点负载分数，更新记录的负载信息。中心管理节点的负载均衡模块框架如图4所示。

负载均衡模块分为心跳接受引擎、负载值计算引擎、检测子节点资源队列三部分。心跳接受引擎接收到检测子节点发来的心跳信息后，将其中的负载信息取出传递给负载值计算引擎;负载值计算引擎根据节点负载信息计算出节点的实时负载值后，根据负载值的大小重排检测子节点资源队列。这样，中心节点收到移动应用检测任务后，可以直接取出检测子节点资源队列中的队头元素，即负载分数最大、负载最低节点。

2.2 调度算法

在分布式调度系统的中心管理节点上有一个负载均衡调度器，其作用是监视和收集各个服务器的负载信息。负载调度器根据多个负载信息算出一个综合能力值。

在传统负载均衡算法中，一般使用CPU使用率、内存占用率、硬盘使用情况、网络吞吐量作为服务器负载的衡量标准。但在本文所述应用场景下，由于移动应用小文件的特点，在检测过程中，服务器硬盘的使用情况变化不大，硬盘使用量对移动应用的检测影响较小;由于移动应用的存储和检测都在局域网下完成，局域网内网络情况优异，网络吞吐量对移动应用的检测效率也无明显影响。

综上，在实验过程中，根据移动应用检测任务的特点以及服务器负载的特点，将影响负载均衡的因素分为以下几类：

（1）检测节点CPU负载，包括CPU核数、CPU频率、CPU使用百分比。

（2）检测节点内存负载，包括最大内存、内存使用百分比。

（3）检测节点任务队列负载，包括任务长度和任务队列最大长度。

（4）检测节点应用软件规模。

2.3 特征提取时间效率

本实验对比基于控制流复杂度的动态反馈算法和基于软件规模大小的动态反馈算法。统计在批量下发400个不同大小及任务量的移动应用任务时，提取各自调度策略所需特征需要的时间。

从图5中可以看出，基于控制流复杂度的动态反馈算法提取负载信息需要数秒，且和控制流复杂度呈正比，对于控制流复杂度较高的应用，提取负载信息需要几十秒，这会是一笔很大的时间开销。而使用基于文件特征的动态反馈算法提取负载信息，提取时间为毫秒级别且近似于常数。可见基于应用软件规模的动态反馈算法提取特征的效率优于基于控制流复杂度的动态反馈算法，有效减少了负载均衡模块在负载信息提取方面的开销，提高了负载均衡算法的效率。

2.4 改进的应用检测任务动态反馈算法效率分析

2.4.1 负载均衡算法功能评估

本实验对比基于应用控制流复杂度的动态反馈算法和基于应用软件规模的动态反馈算法。统计在批量下发900个不同大小及任务量的移动应用检测任务时，6个检测节点的负载情况，实验结果如图6所示。

从图6中可以看出，基于应用软件规模的动态反馈算法对任务量的平衡能力优于基于控制流的动态反馈算法，有效避免了高性能任务节点的任务堆积和低性能的任务节点长时间空闲。

2.4.2 负载均衡算法性能评估

负载均衡算法的目的是为了提高任务执行效率，提高系统吞吐量，利用分布式结构提高系统执行性能。

对基于控制流复杂度的动态反馈算法、基于应用软件规模的动态反馈算法，分别统计在批量下发500个不同大小及任务量的应用在应用检测任务时，2、4、6、8、10个检测节点的任务执行情况，实验结果如图7所示。

从图7中可以看出，使用基于应用软件规模的动态反馈算法进行任务调度后，各检测节点的执行效率高于基于控制流复杂度的动态反馈算法，效率提高38.6%。使用基于应用软件规模的动态反馈算法，有利于分布式系统的负载均衡并提高系统的执行效率。

3 结论

介绍了一种适用于海量移动应用检测任务调度的负载均衡算法，该算法结合移动应用检测节点的CPU、内存、等待应用的软件规模，计算移动应用检测节点的负载值，通过负载值进行移动应用检测任务的调度下发。实验表明，该算法有效避免了高性能任务节点堆积和低性能的任务节点长时间空闲，并提升在应对海量移动应用安全检测任务时的系统效率。通过该算法，移动应用检测系统对检测节点的任务平衡能力加强，吞吐量加大，系统的检测效率提高。本文介绍的这种海量移动应用检测任务负载均衡算法，可以满足海量移动应用检测需求，有利于提供检测系统执行效率。

参考文献

[1]王雪芬，郭黎黎.“互联网+”时代智能手机网络安全问题探析[J].电子技术与软件工程，2018（01）：222-223.

[2]郝春亮，沈捷，张珩，等，大数据背景下集群调度结构与研究进展[J].计算机研究与发展，2018，55（01）：53-70.

[3]刘新宇，翁健，张悦，等.基于APK签名信息反馈的Android恶意应用检测[J].通信学报，2017，38（05）：190-198.

[4]杨忠明，粱本来，秦勇，等.多检测引擎监测的动态负载均衡算法[J].计算机应用，2017，37（03）：717-721.

[5]陈斌，刘晓洁，艾磊，等，一种动态的入侵检测系统负载均衡方法[J]网络新媒体技术，2015，4（05）：39-44.

[6]李敬华，李倩茹，贾蓓，数据中心服务器负载均衡问题研究[J].电信快报，2014（04）：25-28.

[7]吴敬征，武延军，武志飞，等，基于有向信息流的Android隐私泄露类恶意应用检测方法[J]中国科学院大学学报，2015，32（06）：807-815.

[8]赵光泽，李晖，孟杨.Android平台WebView组件安全及应用加固研究[J].信息网络安全，2015（10）：61-65.

[9]吕照进，沈立炜，赵文耘，面向场景的安卓应用代码定位方法[J].计算机科学，2017，44（02）：216-221+256.

[10]巫志文，李炜，基于Android平台的软件加固方案的设计与实现[J].电信工程技术与标准化，2015，28（01）：33-37.

[11]朱洪军，陈耀光，华保健，等.一种Android应用加固方案[J].计算机应用与软件，2016，33（11）：297-300+320.

[12]郭伟.基于安卓系统的移动应用程序安全加固系统的设计[J].数字技术与应用，2016（06）：201.

[13]趙北庚，王剑锋.关于Android短信恶意木马Smali汇编码逆向分析[J].网络安全技术与应用，2015（10）：88.

[14]刘方圆，孟宪佳，汤战勇，等.基于smali代码混淆的Android应用保护方法[J].山东大学学报：理学版，2017，52（03）：44-50.

[15]崔弘，喻波，方莹，恶意代码分类的一种高维特征融合分析方法[J].计算机应用研究，2017，34（04）：1120-1123+1150.