一种基于本地代码特征的Android恶意代码检测方法

何 平 胡 勇

(四川大学电子信息学院 成都 610065) (721247751@qq.com)

智能手机给人们的生活带来巨大的变化，各种重要信息和业务由手机存储和处理，使得手机越来越重要，也成为不法分子攻击的目标.从2010年发现首个Android木马程序以来，Android下的恶意软件数量急速增长，给用户的数据安全带来难以预测的风险.根据360互联网安全实验室发布的报告，仅在2017年第3季度，Android手机的新增恶意软件数就高达188万个，平均每天有大约2万新的Android恶意软件出现.增长较快的Android恶意代码主要是资源消耗、恶意扣费和隐私窃取等类型，最近甚至出现了锁屏和加密等勒索类型的恶意应用.面对如此严重的威胁，检测Android恶意代码已成为信息安全领域的一个重要研究方向.

1 研究现状

近年来，各国专家学者提出了多种检测Android恶意代码的方法，主要分为静态分析和动态分析两大类.

静态分析是指不运行程序仅对Android应用及其解析生成的文件进行分析的方法.静态分析的对象主要包括AndroidManifest.xml文件、Java源代码、Dalvik字节码和本地代码，利用从这些文件或代码中提取出的权限特征、文本特征以及API调用特征等来识别应用是否包含恶意代码.静态分析具有快速、高效的优点，但对经过代码混淆和多态变形后的恶意代码不太适用，需要做更多的工作.

动态分析是一种基于应用程序运行时行为的检测技术，通常需要修改Android系统，以监控该应用对网络、系统调用、文件和内存的访问，信息的访问模式及其处理行为等.通过分析这些行为是否正常来判断其恶意性.动态分析的优点是不受代码混淆和加密的影响，但需耗费系统资源，对分析人员的技术能力要求也较高，不利于对大规模的应用进行检测.

从Android应用所包含的代码中提取相应特征进行恶意代码检测，已经有较多的方法和研究.李寅等人[1]将DEX文件反编译，并分析其Dalvik字节码中调用的系统函数.通过对每个系统函数分配不同的风险等级，统计整个应用中各系统函数出现的频次，计算其加权平均值，以其值是否超过阈值判断这个应用是否是恶意应用.李挺等人[2]通过提取Dalvik指令序列，然后以Smali代码中的方法为单位将指令序列进行形式化描述，并采用MOSS算法、闵可夫斯基距离以及编辑距离算法计算形式化描述后的代码与已知恶意特征的相似度，并根据相似度比对结果判断待测应用是否含有恶意代码.Kang等人[3]则提出了一种通过分析Dalvik字节码频率来对恶意代码进行检测的方法.陈铁明等人[4]从Dalvik字节码序列中提取N-Gram特征，然后利用随机森林对恶意代码进行检测和分类.李自清[5]提出了一种利用函数调用图来检测Android恶意代码的方法，通过反编译DEX文件提取出函数调用图，然后计算出函数调用图的特征向量，利用得到的特征向量进行恶意代码的检测.

上述方法都是从DEX文件中提取Dalvik字节码的特征进行恶意代码检测，主要利用了Dalvik字节码的文本特征、API调用特征和函数调用图的特征，然后通过相似度比较或者机器学习的方法对恶意代码进行检测，以上方法并没有提取SO文件包含的本地代码的相关特征.同时有研究[6]表明现在86%的Android常用应用都包含本地代码.如果恶意应用将其恶意代码放入SO文件的本地代码中，上述静态检测手段无法取得较好的检测结果.

针对上述方法没有提取SO文件包含的本地代码特征的问题，本文提出一种基于本地代码特征的Android恶意代码静态检测方法，将待检测应用的DEX文件和SO文件转化为ARM汇编代码，并提取汇编代码的控制流图集合，将其与已知恶意应用的控制流图集合进行相似性比较，得出它们的相似度.如果相似度大于某个阈值，则可以确定待检测的Android应用包含了恶意代码.由于提取了SO文件中包含的代码的特征，该方法的代码覆盖率比传统的静态检测方法高.

2 方法描述

本文提出一种基于本地代码特征的Android恶意代码检测方法，该方法通过提取Android应用的本地代码的控制流图特征来检测和分析恶意代码，流程如图1所示：

图1 检测方法的流程

2.1 ART虚拟机

Android应用程序包含的代码通常分为DEX字节码和预编译的本地二进制代码，应用通常运行在Dalvik虚拟机上.Dalvik虚拟机采用和标准的JVM相同的实时编译方法(JIT)来编译程序，也就是在应用运行时进行编译.

从Android4.4开始，Google使用ART(Android runtime)替换了Dalvik虚拟机.ART使用的是提前编译方法(AOT)，即在应用安装时进行编译.ART提高了应用的运行效率，并且减少了电量消耗，但是增加了应用的安装时间和占用的空间.ART将DEX文件中的Dalvik字节码编译生成一个后缀.oat的文件，该文件包含了Dalvik字节码对应的本地代码.如图2所示，利用ART的这一功能将Dalvik字节码转换成本地代码.

图2 DEX文件生成本地代码

2.2 反汇编

将本地代码转化为汇编代码，需要进行反汇编.常用的反汇编算法有2种：线性扫描算法和递归遍历算法.线性扫描算法就是从第1个字节开始依次进行指令的反汇编，直到最后1个字节.该方法的优点是代码覆盖全面，但是如果代码中混合有数据，该方法不能有效区分代码和数据，会产生错误的反汇编结果.使用线性扫描方式的反汇编工具有Windbg，objdump等.第2种方法是递归遍历算法，以程序的控制流作为参考，只有一条指令被另一条指令引用，才会将这条指令反汇编.其优点是能够有效区分数据和代码，但是如果一个分支的目的地址不能静态确定，就可能无法找到并反汇编有效的指令，结合其他方法来进行反汇编处理可以达到很好的效果.IDA Pro使用了递归遍历算法进行反汇编，比使用线性扫描的反汇编器有更好的反汇编效果.根据需求，本文选择递归遍历算法进行本地代码的反汇编处理和程序控制流图的生成.

2.3 控制流图匹配

程序的控制流图可以用来进行源码的相似性比较[7-8]，本文将其应用在恶意代码的检测中.将DEX文件通过ART Compiler生成的本地代码和SO文件包含的本地代码反汇编生成ARM汇编代码，再以函数为单位转化为控制流图，并利用相应的模式对控制流图进行注释，生成经过注释的控制流图集合，然后与恶意代码样本的控制流图集合进行相似性比较.

2.3.1子图同构算法

子图同构算法用于确定一个控制流图是否包含另一个控制流图，或者被另一个控制流图包含.Garey等人[9]提出子图同构问题是NP完全问题，通常生成的程序控制流图是稀疏图，能在可接受的时间内计算出结果.常用的子图匹配算法有Ullmann算法[10]和VF2算法[11]，在算法的时间复杂度上VF2算法要优于Ullmann算法.

本文采用VF2算法来实现程序控制流图的子图同构计算.VF2的基本思想如下：

若图G1=(V1,E1)与图G2=(V2,E2)同构，其中V1，V2表示图G1，G2的节点集合，E1，E2表示边的集合，则G1与G2必定存在映射M={(m,n)∈V1×V2}，其中，m为图G1的节点，n为图G2的节点.

该算法用状态空间表达式(SSR)来表示确定映射函数的步骤.其中M(s)是M的子集，其中s表示每个状态.用状态s到状态s′的转移来表示1对新的匹配的节点加入到当前的状态空间表达式.初始状态为s0，则M(s0)=∅.对于每个中间状态s，算法会计算出可加入当前状态的候选节点对的集合P(s).对于P(s)中的每个节点对，通过判断是否满足可行性规则F(s,n,m)，若F(s,n,m)为真，则将节点对加入到M(s)，从状态s转移到新的状态s′，然后重复上述步骤.图3展示了2个匹配的控制流图，其中虚线表示匹配成功的部分.

图3 2个子图同构的控制流图

2.3.2模式匹配

当一个节点数较少的控制流图(如只有3个节点)与其他控制流图作子图同构匹配时，如果不考虑节点的属性即节点中包含汇编语句，则会产生错误的匹配结果，例如子图匹配成功的某些节点中的汇编语句不同，所以仅根据子图匹配的结果无法准确判断2个控制流图是否匹配.有2种方法可以解决这个问题：

1) 比较控制流图中已匹配的各个节点中的每条ARM汇编语句；

2) 以指令和操作数类型为控制流图节点的每条语句分配对应的模式，然后对控制流图的节点进行模式匹配.

由于ARM汇编有众多的指令和不同的操作数，方法1)会耗费大量时间，所以我们使用方法2)按指令类型和操作数类型定义了18种模式，在反编译生成ARM汇编代码和控制流图时注释其中的汇编语句.该方法不仅能解决节点数较少时控制流图的子图同构问题，而且可以提高子图同构的计算效率，这18种模式如表1所示(操作数类型为空表示不以操作数的类型区分模式):

表1 命令分类与18种模式

在生成控制流图时，使用这些模式对各个节点模块中的语句进行注释，生成带注释的控制流图.图4为一个经过模式注释的控制流图.

在进行子图匹配时，2个控制流图已匹配的每个节点中对应的模式也必须完全匹配，才表示2个控制流图匹配成功.

图4 模式注释生成的控制流图

2.3.3恶意代码相似性识别

利用上文所述的方法，为汇编程序的每一个函数都生成带有注释的控制流图,这样就得到了一个Android应用的控制流图的集合.将这个集合作为Android应用的特征与恶意代码样本生成的特征作匹配.如果一个应用的控制流图的集合中有一定比例的控制流图和恶意代码样本的控制流图匹配，则可以判断这个应用包含恶意代码.

定义待检测应用A与样本应用B的相似度SimilarityA,B，其计算公式如下：

(1)

NumofCFGSetB表示应用B中控制流图的总数，NumofCFGSets表示应用A与应用B匹配的控制流图总数.如果一个待检测应用与恶意代码样本库中的某个应用的相似度SimilarityA,B大于某个阈值，则认为这个应用包含恶意代码.

3 实验分析

本文使用Android ART提供的Compiler将Dalvik字节码转换为本地代码，使用IDA Pro和编程进行反汇编，最后通过编程实现控制流图的注释和匹配.

实验所采用的Android恶意代码样本来自Drebin项目[12]，正常样本来源于Google Play随机下载.实验从所有恶意代码应用样本中随机选择70个组成恶意代码样本库，使用前文描述的方法得到每个样本的控制流图集合.然后再从剩余的恶意样本中随机选取100个与从正常样本中随机选取的200个组成测试样本集SampleSet1,使用同样方法组成测试样本集SampleSet2.处理2个测试样本集生成每个样本的控制流图集合，然后取不同的阈值对SampleSet1进行检测.图5显示了在取不同的阈值(threshold)时，恶意代码的检测率TPR以及误报率FPR.

检测率TPR定义为正确检测出的恶意应用的个数与总的恶意应用的个数的比值，检测率的计算公式如下：

(2)

其中,TP为被正确检测出的恶意应用的个数，FN为被错误地判断成正常应用的恶意应用的个数.误报率FPR定义为被误报为恶意应用的正常应用的个数与正常应用的总数的比值.误报率的计算公式如下：

(3)

其中,FP表示被错误地判断为恶意应用的正常应用的个数，TN表示被正确检测出的正常软件的个数.准确率Accuracy的计算公式如下：

(4)

对图5进行分析，虽然阈值为20%时，检测的检测率达到98%，但同时误报率高达33%.随着阈值的增加，发现检测率和误报率都呈现下降的趋势，综合考虑检测率和误报率，采用60%作为本文实验的阈值.

图5 SampleSet1检测结果分析

利用该阈值对测试样本集SampleSet2进行检测，其检测结果如表2所示.

表2 SampleSet2的检测结果

根据式(2)～(4)，计算得到该方法对于测试样本集SampleSet2的检测率为92%、误报率为5%、准确率为94%.实验结果表明，利用本文提出的方法能有效地检测Android应用中是否包含已知的恶意代码，其恶意代码检测率能达到90%以上.

使用静态分析工具Androguard对样本集SampleSet2进行检测，将其检测结果与本文方法的检测结果作比较.其对比结果如表3所示:

表3 与Androguard的对比结果

使用表3中的检测结果，计算出Androguard工具在检测样本集SampleSet2时的检测率为67%，误报率为3%，准确率为87%.可以看出本文方法的检测率和准确率都要明显优于Androguard工具，而误报率也在可接受的范围内.

4 结 语

本文提出一种基于本地代码特征的Android恶意代码检测方法，该方法将Android中的Dalvik字节码通过ART提供的Compiler编译为ARM本地代码，与SO文件一起进行反汇编生成的ARM汇编代码和控制流图，同时根据指令和操作码的类型定义了18种模式来对控制流图进行注释处理，最后以控制流图为特征利用子图匹配和模式匹配来进行恶意性检测.与现有方法相比较，该方法覆盖了应用中的本地代码，比现有方法的代码覆盖率高，而且提取的是汇编级的特征，能有效应对Java层的代码混淆.经过实验验证，上述方法能够成功检测出应用是否包含已知恶意代码，并且相对于Androguard有更高的检测率和准确率.

在下一步工作中，需要结合Android应用程序的其他特征，并且利用数据挖掘和机器学习相关方法，进一步提高检测的准确率，此外还可研究对加固恶意应用的检测.

[1]李寅, 范明钰, 王光卫. 基于反编译的Android平台恶意代码静态分析[J]. 计算机系统应用, 2012, 21(11): 187-189

[2]李挺, 董航, 袁春阳, 等. 基于Dalvik指令的Android恶意代码特征描述及验证[J]. 计算机研究与发展, 2014, 51(7): 1458-1466

[3]Kang B, Kang B J, Kim J, et al. Android malware classification method: Dalvik bytecode frequency analysis[C]Research in Adaptive and Convergent Systems. New York: ACM, 2013: 349-350

[4]陈铁明, 杨益敏, 陈波. Maldetect:基于Dalvik指令抽象的Android恶意代码检测系统[J]. 计算机研究与发展, 2016, 53(10): 2299-2306

[5]李自清. 基于函数调用图的Android恶意代码检测方法研究[J]. 计算机测量与控制, 2017, 25(10): 198-201

[6]Sun M, Tan G. NativeGuard: Protecting Android applications from third-party native libraries[C]Proc of the 2014 ACM Conf on Security and Privacy in Wireless & Mobile Networks. New York: ACM, 2014: 165-176

[7]陈新. 基于程序控制流图源代码相似程度分析系统[J]. 计算机系统应用, 2013, 22(3): 144-147

[8]吕博然, 吴军华. 基于路径序列相似度判别的程序克隆检测方法[J].计算机工程与应用, 2018, 54(2): 55-61

[9]Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Completeness[M]. San Francisco: W H Freeman, 1983: 208-209

[10]Ullmann J R. An algorithm for subgraph isomorphism[J]. Journal of the ACM, 1976, 23(1): 31-42

[11]Cordella L P, Foggia P, Sansone C, et al. A (sub)graph isomorphism algorithm for matching large graphs[J]. IEEE Trans on Pattern Analysis & Machine Intelligence, 2004, 26(10): 1367-1372

[12]Arp D, Spreitzenbarth M, Hübner M, et al. DREBIN: Effective and explainable detection of Android malware in your pocket[C]Proc of Network and Distributed System Security Symposium. Reston: Internet Society, 2014