基于结构相似度的Andriod恶意外挂软件检测算法

李 蓉，周维柏

(广州商学院 信息技术与工程学院，广东 广州 510280)

近年来随着智能手机的普及，造就了APP急剧增长，然而庞大商机利益驱使下产生大量的恶意攻击，对于越来越多的恶意APP则需要一个快速有效的系统来检测，如何快速高效分析并检测出恶意软件已经成为目前的研究热点[1]。

目前Android恶意软件检测主要是以检测方案所选取的特征值来进行区分，常用的检测方法有静态分析和动态分析两种。动态分析是创造一个可控的环境，从Android应用程序的“行为”中提取特征值，主要是系统调用信息和网络流量信息[2]；Shabtai等人[3]从内存占用和CPU负载等信息中提取动态特征，Liu等人[4]通过监听异常的电量消耗来进行恶意软件检测；这种动态检测的缺点就是同样传送网络信息，可能传送给正常使用者，也可能是攻击者，仅靠状态、流量、频率上判断还是不够准确的。静态分析是通过分析权限或APP里的API来执行恶意软件检测，Cerbo等人[5]、Peng等人[6]和张乐峰等人[7]采用APP的权限作为特征值，通过比对权限来表示恶意软件和正常软件的差异，从而达到恶意软件检测的目的，然而仅权限信息还不足以检测恶意APP，因为一些权限请求没有在Android平台上明确定义，因此邵舒迪等人[8]提出基于权限和API特征结合的检测方法，将权限特征和API特征结合，形成新的API-权限特征集合，具有很好的检测效果。宁卓等人[9]对method和class签名进行多级匹配，通过数据流模式挖掘找出恶意软件，另外Grace等人[10]使用操作系统核心中的漏洞，利用一些特殊权限相关的API作为特征值进行检测，修扬等人[11]则采取静态和动态结合，根据操作代码序列频率向量和可执行文件运行时的行为特征向量来进行检测。

上述的检测方法并没考虑外挂恶意软件的检测，对外挂恶意软件的检测效果都不是很理想。因此本文提出一种基于结构相似度的检测方法，以源码中敏感API和系统命令作为特征值，建立树状结构图，并通过比较恶意APP和可疑APP的结构相似性，来判别是否为恶意软件，实验表明本算法可行可靠。

1 恶意软件

恶意软件是指在计算机系统上执行恶意任务的病毒、蠕虫和特洛伊木马等程序。恶意软件分为原生态恶意软件和外挂恶意软件两种类型，原生态恶意软件为攻击者直接开发一个独立带有恶意行为的新APP，外挂恶意软件则为攻击者将带有恶意行为的程序注入到其他正常APP上，因为只是将有恶意的行为代码注入正常的APP，导致被注入的恶意行为的程序同一般正常的程序行为是差不多的，使用者不容易分辨。现今的检测系统对原生态的恶意程序检测率保持着一定的水平，但对外挂恶意软件的检测率大多不甚理想。

当恶意代码注入到两个正常的APP时，恶意行为是一样的，可是两个APP的整体结构和内容则完全不一样，这样造成当今检测系统无法检测到。不过即使class或method完全不一样，但其所使用的API肯定是相同的，因此本研究就使用API作为特征值。特征提取的方法以信息增益IG和互信息MI最为常见，由于互信息MI可测量两个系统间的相关性，且MI模型特点是易于理解，其时间复杂度低[12]，很适合恶意程序实时检测，所以本文运用互信息MI进行特征提取。

互信息MI根据特征词的出现情况来衡量它对文本类别的重要程度。对于给定特征词T={tj,j=1,2,…,m}和类别C，它们之间的互信息计算公式如式(1)：

(1)

其中P(tj∩c)为类别c中包含tj的概率，P(tj)表示特征项tj在整个训练集中出现的概率，P(c)表示类别c出现的概率。互信息值越大，它们之间出现的概率越大，其和类别之间的共存关系越强[13]。

2 基于结构相似度的Android恶意软件检测方法

针对外挂恶意软件，本文分别使用源码中的class、method、API和系统命令构建结构图，再通过机器学习分析良性APP和恶意APP的API和系统命令，找出恶意APP常用的敏感API和系统命令，并利用分析出来的恶意APP常用的敏感API和系统命令修改先前建立的结构图，最后使用修改后的结构图进行可疑APP和恶意APP的比对，达到检测可疑APP是否为恶意APP的目的。系统流程图如图1所示。

图1 系统流程图

2.1 逆向工程

将收集的恶意APP和良性APP通过逆向工程技术反编译出APP源码。先使用Apktool工具将收集来的APK文件反编译成.dex文件，再将dex文件用Dex2jar工具转译成jar文件，最后将jar压缩成.class文件，利用JAD工具拆解成可供后续重建结构图使用的java原文件。

2.2 构建结构图

本文提出以结构相似度为基础的恶意APP检测方法，通过分析未知APP和恶意APP的结构相似度，来达到检测恶意APP的目的。所以本文先将利用反编译的源码依照其中的class、method、API和系统命令构建结构图，如图2所示。

图2 正常APP结构图

2.3 找出恶意程序常用的API和系统命令

使用网络爬虫程序从Android开发网站中抓取Android APP所使用的所有API。相同的恶意程序会使用相同的API和相同的代码。以此为基础将反编译完成的恶意APK以及正常原文件，利用MI分析出恶意程序常用的敏感API及系统命令作为本文所使用的特征值，并在之后以此特征值进行结构图的修改。本文利用MI找出的敏感API有：getSubscriberID、getAttributeBoole-anValue、getSimserialNumber、GetAttributeUnsigne-dIntValue、getInstalledPacksges、startNow、CornerPathEffect、addRoundRect、getLine1Number、getShortClassName、getExtraInfo、getRunningservices、sendTextMessage共13个。

2.4 建立以敏感API为基础的APP结构图

利用以上选出的敏感API和系统命令与结构图进行比对，将不含敏感API和系统命令的部分移除，只留下有敏感API和系统命令两部分，作为最后用来检测的结构图。

假设将两个相同的恶意程序M1和M2注入Line和Game这两个正常的APP里。图3为正常程序Line被注入恶意程序M1后的结构图，里面包含sendTextMessage()，getLine1Number()两个敏感API。图4为正常程序Game被注入恶意程序M2后的结构图，里面包含sendTextMessage()，getLine1Number()两个敏感API。

图3 Line被注入恶意程序M1的结构图

图4 Game被注入恶意程序M2的结构图

图3和图4的结构明显不同，这样会造成检测系统识别不出恶意程序。虽然两程序的结构不同，但他们都有sendTextMessage()，getLine1Number()两个敏感API，当我们当我们把不包含敏感API的结构删除后，得到两个结构图就可以共享相似的结构，图5为修改后的Line恶意程序结构图，图6为修改后的Game恶意程序结构图。

图5 修改后的Line恶意程序结构图

图6 修改后的Game恶意程序结构图

2.5 计算结构相似度进行恶意程序检测

在完成对可疑APP和已知的恶意APP的结构构建后，通过比对结构相似度来评估可疑APP是否为恶意APP。本文采用的相似度为结构的相似度，使用编辑距离算法(Levenshtein Distance)作为计算字串相似度的算法。这是由于两个字串之间，由一个转成另一个所需的最少编辑操作次数，而且该算法两个字串长度不必相同且符合代码改写编辑操作。非常合适作为结构相似度评估算法。

本文利用结构的相似度和Method的相似度作为分类依据，判断Method的相似度以Method字串为内容，m1和m2两个Method的相似度计算公式如式(2)：

(2)

其中Strm1和Strm2为对应的Method的字串，Editdist(Strm1,Strm2)为利用编辑距离算法所算出Strm1和Strm2字串间的距离。在两个完全不相似的情况下，编辑距离会等于StrLenm1，StrLenm2中的最大值，即Max(StrLenm1,StrLenm2)，由此可知Editdist(Strm1,Strm2)在Max(StrLenm1,StrLenm2)中的所占比例可表示Strm1和Strm2的相似度。

但恶意程序不可能只有一个Method，所以我们先假设恶意程序Px具有n个带有敏感API的Method，即Px={mx1,mx2,…,mxn}，而恶意程序Py具有m个带有敏感API的Method，即Py={my1,my2,…,mym}，要算出Px和Py两程序之间的文件结构相似度，以Px为基础，根据Px所有的Method一一去同Py比较，最后将Px上所有Method与Py的Method计算出的相似度分数的最大值求和。计算公式如式(3):

(3)

因为Method越多,所得到的数值会越大，为避免数值过大，我们将得到的数值再去除以最多Method的那个恶意程序的Method数量，计算公式如式(4)：

(4)

其中NumOfAPKa为APKa中含有敏感API的所有Method数量，NumOfAPKb为APKb中含有敏感API的所有Method数量。上述公式计算的值介于0到1之间的实数，我们设立一个门槛值，当相似度大于门槛值时，就判定为恶意软件。

3 实验结果与分析

为验证本算法，我们进行两部分的实验，第一部分是验证本算法的可行性，第二部分验证本算法的优越性。

3.1 实验环境

本文实验采用虚拟环境，虚拟环境版本为QEMU version 2.12.0，Android模拟环境为Nexus S(4.0",480 x 800:hdpi)，API版本为Android4.4.2-API Level19，CPU/ABI为ARM(armeabi-v7a)，Skin为WVGA800，Front Camera和Back Camera选“Emulated”，Memory Options为RAM1024，Internal Storage为200MiB，SD Card Size为512Mib。采用Java语言编写。

3.2 算法的可行性

算法的可行性验证，采用自行编写的功能少简易的APP，对逆向工程技术与本文提出的相似度计算方法进行验证。共有A、B、C、D、E五个APP，分别为A:takepicture，B:getPhoto，C:phonecall，D:takepicture-M，E:phonecall-M。A、B、C、为3个正常的APK，其中A和B相似，C和D、E两个APK都不相似，D、E分别以A、C为基础注入相同恶意程序的APK。

3.2.1 实验说明 模拟1：使用两个不相似的APK进行实验；在不考虑其他因素的情况下，本算法的预期相似度较低。

模拟2：使用两个相似的APK进行实验；因两个APK是相似的，本算法预期相似度应该较高。

模拟3：使用两个不相似但都含有敏感API的APK进行实验，不看敏感API；如不看敏感API的部分，模拟3与模拟1极为相似，因此本算法预期模拟3在不看敏感API的情况下计算出的相似度应该低。

模拟4：使用两个不相似但都含有敏感API的APK进行实验，看敏感API；本算法预期相似度较高。

3.2.2 实验结果 使用公式(3)计算得到的相似度的结果如表1所示。

从表1中可以看出模拟1中的相似度结果来看两个APK非常不相似，实际上A和C也是不相似的；从模拟2中的相似度结果来看两个APK非常相似，实际上A和B也是相似的两个APK；从模拟3中的相似度结果来看两个APK不相似，实际上D和E不相似但都加入相同敏感API；从模拟4中的相似度结果来看非常相似，实际上D和E不相似但都加入相同敏感API。总之模拟1和模拟2如本文预期结果一样，模拟3和模拟4原本两个不同的APK，但都含有敏感API，结果也同本文预期一样。从而验证本算法是可行的。

利用逆向工程技术对D和E这两个APK反编译，再利用反编译的结果建立结构图，将每个Method利用编辑距离算法计算，模拟3的结果如表2所示，模拟4的结果如表3所示。

表2中M01到M05为takepicture-M的Method，其中M01:takepictur，M02:onActivityResult，M03:onCreat，M04:onRequestPermissionsResult，M05:ontakepicture。K01到K05为phonecall-M的Method，其中K01:phonecall，K02:PermissionsResult，K03:ResultActivity，K04onCreate，K05:onphonecall。从表中可看出M01、K01和M05、K05的数值明显高出其他，这是这Method都包含敏感API(sendTexMessage())。模拟3的相似度结果为(0.96+0.27+0.19+0.18+0.63)/5=0.446。模拟3实验说明两个加入相同恶意程序的APK，如果不看敏感API，把全部的Method都加入计算，得到的结果会是数值较低，结构不相似的。

表1 模拟实验相似度的计算结果

表2 模拟3的编辑距离算法计算的结果

表3中MA1、MA2为takepicture-M含有敏感API的Method，KA1、KA2为phonecall-M含有敏感API的Method。计算出APK的相似度(0.96+0.63)/2=0.79。模拟4说明本算法，将不包含敏感API的部分删除后，进行相似度的计算，得到的结果相当的高，从而验证本文提出的算法能充分识别出两个不相似但含有相同敏感API的APK。

表3 模拟4的编辑距离算法计算的结果

通过实验，我们将门槛值设为0.6，当相似度大于0.6时我们就判定相比较的APK为相似的APK，反之就判定为不相似。

3.3 算法的优越性

3.3.1 实验数据 本实验数据来自北卡州立大学计算机科学系研究人员Xuxian Jiang策划的android恶意软件基因组计划中的数据，该项目收集1260个android恶意代码样本，含49种不同恶意程序家族。本文首先精选10个恶意程序家族，共137对恶意程序。正常APP则使用网络爬虫程序在google应用商店获取，也精选137对。

3.3.2 评价指标 为量化恶意程序的检测效果，评价标准规定如下：TP为恶意样本被正确检测为恶意样本的数量，FN恶意样本被误认为正常样本的数量，TN正常样本被正确分类为正常样本的数量，FP正常样本被误认为恶意样本的数量。评价指标：

3.3.3 实验结果及分析 本实验首先由10个恶意家族中各挑选一个APK作为训练样本，再将274个APK与10个训练样本进行相似度计算，相似则判为恶意样本，否则判为正常样本。实验结果如表4所示。

从表4可以看出，137对正常APK中有10个APK被分类为恶意软件，这是由于这些正常APK中使用API与本文提出的敏感API是一样的，正常APP与恶意APP在在传送信息时的代码是非常相似的，所以本文实验时将正常的APK判定为恶意，通过实验结果可知本文提到的方法对于未知的APK是否为恶意的分辨率可达93.27%。

不同算法的性能比较如表5所示。从表中可看出本文提出的算法要好于其他几种。这是由于文献[11]基于操作代码序列频率向量来检查，动态分析可有效检测恶意软件，然后某些恶意软件因程序的设计关系无法触发恶意行为，导致动态分析无法完全检测恶意App。同时动态分析会消耗大量资源。文献[14]静态分析Android应用配置文件与Java源文件，分析权限请求或API呼叫来检测恶意程序。然后权限信息不足以检测恶意程序，因为有些权限请求没有在Android平台中明确定义。文献[15]结合动态检测方法和静态检测方法，构造出一种混合特征集。由于外挂恶意程序为注入其他正常的App中，同正常的App程序差别不大，所以很难检测出来，并且这种方法消耗资源大。本文选出恶意App常用的API和系统命令，再简化结构图，大大减少资源的消耗，由静态分析降低资源消耗，利用结构对比增加检测率，从而达到提高外挂恶意软件的检测效率的目的。

表4 恶意APK检测结果

表5 不同算法的性能比较结果

4 结束语

因现行Android恶意软件检测系统难以检测注入式的外挂恶意软件，因此本文提出基于结构相似度的Android恶意软件检测方法，以APP结构为基础，利用MI选出敏感API，最后计算相似度来判断恶意软件。实验表明本算法可行可靠。