一种基于社团结构分析的Android恶意代码检测方法

摘要

本发明提出了一种基于社团结构分析的Android恶意代码检测方法，在对目标程序的逆向分析过程中，首先，自动获取权限、函数、类、系统API等重要静态特征信息；然后，利用函数及函数间的调用关系构建函数调用图，并对函数调用图进行预处理；对赋权后的函数调用图进行循环分裂与分析，得到社团结构的正确划分；最后，对从社团结构中提取出的特征进行机器学习，得到最终的恶意性判定结果。本发明方法在面对由“重打包”技术产生的大量Android应用程序样本时，能够快速地进行程序内部结构分析和恶意代码检测。

说明书

技术领域

本发明涉及Android移动端应用的恶意代码检测领域，特别涉及快速检测由“重打包”技术产生的大量Android应用程序样本的恶意代码。

背景技术

近年来，随着“重打包”和“代码混淆”技术被广泛的应用于恶意的移动端应用程序，大量针对恶意代码的研究工作围绕着分析应用程序的内部结构展开。很多基于程序内部结构特征的检测方法能够通过分析目标程序的反编译代码，提取或构建出不同的图调用结构，之后再通过比较目标样本和恶意样本图结构的差异程度来判定程序的恶意性。研究成果表明，这类检测方法在对抗“重打包”和部分“代码混淆”技术方面有较好的效果。

与传统的基于签名的恶意代码检测方式相比，该类方法主要解决了以下两个主要问题。第一，基于签名的检测方法时效性差，很难发现未知病毒。基于签名的检测方法大多需要借助人工分析，提取出包含病毒信息的字节序列或者特定字符串作为特征，存入特征数据库，再通过与待检测程序代码进行特征匹配来判定程序的恶意性。而基于结构化特征的方法大多能够实现对样本的自动分析与检测，其方法普遍具有一定的启发性，能够更好的识别未知病毒。第二，基于签名的检测方法在对抗由“重打包”产生的大量变种样本时效率较低。同时“代码混淆”技术能够加大对目标程序的分析难度。而基于结构化特征的检测方法借助新变种样本大多在内部结构上与已有病毒相似的特点，能够通过比较两者的相似性，快速识别病毒。对程序内部结构的分析也能够抵御部分的代码混淆技术。

但在实际使用中发现，很多基于结构化特征的检测方法在执行时间和图结构的构建与分析上存在不足，主要原因如下：第一，应用程序的内部调用结构通常比较复杂。为了比较图的相似性，往往需要存储大量含有恶意行为的图结构作为特征库。在此基础上，直接匹配图或子图并计算其相似性通常带来巨大的计算量。第二，在构建图结构方面，很多方法倾向于将部分语义信息赋予图结构中，形成了如控制流图、数据依赖图和权限事件图等多种类别的图结构。然而，这些方法普遍需要对一个给定的规范进行精准匹配，反而不利于对抗大量的变种病毒。同时，利用已知样本的特征进行新的图的构建也不利于检测未知病毒。

在对移动应用的内部函数调用图结构分析中发现，移动应用程序中的函数调用图结构不同于随机网络，已呈现出部分复杂网络的特性，如无标度性。因此，整个调用图可利用社团生成方法被划分为多个社团结构。在这些社团结构中，节点之间联系紧密，而与其他社团中的节点联系稀疏。然而基于纯结构特征上的划分出的社团并不一定能最好的反映出应用程序的行为特征，因此需要在社团划分过程中结合移动应用程序的其他特征来共同判定划分结果。

发明内容

本发明所要解决的技术问题是提供一种基于社团结构分析的Android恶意代码检测方法，解决很多传统基于结构特征恶意代码检测方法中由图相似度比较带来的耗时过高，和构建具有特定意义的图结构后不利于对抗大量由重打包技术产生的变种病毒的问题；也对社团生成方法的改进，提高本方法在图分割时的执行效率。

为解决上述技术问题，本发明采用的技术方案是：

一种基于社团结构分析的Android恶意代码检测方法，包括以下步骤：

步骤1：对待检测的移动应用程序进行反编译，得到反编译代码，从中提取出移动应用程序的静态信息；

步骤2：通过分析移动应用程序的静态信息，得到静态特征出现在良性样本或恶意样本的频率，并根据它们在不同样本中出现的频率差分别为其分配恶意值；

步骤3：构建函数调用图；

步骤4：对函数调用图进行预处理，包括删除孤立节点、为函数调用图的节点分配权值；

步骤5：定义边介数为关键节点到其余节点间的最短路径，关键节点定义为：

其中，n代表整个图中的节点数，D_i是节点i的度，K是与节点i直接相连的节点数，W(q_m)是节点集k中节点m的权重；

定义图为G＝(V,E)，其中V是节点集，E是边集，则边介数的计算公式为：

其中，是节点i与节点j之间包含边e的最短路径，g_e是边e的权重；

步骤6：定义模块度参数Q为：

Q＝∑_j(e_jj-a_j²)

其中社团j的矩阵元素被定义为e_jj，它表示社团j中边的数量；a_j²表示连接社团j中任意点的边的数量；当Q的值达到巅峰并开始下降时，终止计算；

步骤7：记录每次删除边介数最高的边后所形成的社团划分版本，通过对这些划分版本中各个社团的恶意值、属性、节点规模情况进行评价，选择最优的一个划分版本；

步骤8：从确定的社团划分版本中，提取出三方面信息作为分类特征，即具有恶意特征的社团数、各社团中的最高恶意值、各社团恶意值总和；

步骤9：通过对分类特征进行机器分类学习，得到恶意性判定结果。

进一步的，所述静态信息包括移动应用程序使用到的权限、与权限相关联的函数、系统函数、JAVA包、类以及所有函数及其调用关系。

进一步的，所述步骤9中，机器分类学习的训练阶段采用线下单独训练的方式执行。

进一步的，在所述步骤1中，使用的反编译工具为androguard或者apktool。

与现有技术相比，本发明的有益效果是：

1、本发明方法在对由重打包技术产生大量变种病毒样本的检测时，具有较高的检测率。

2、本发明方法采用机器学习的方式来取代图相似度的比较，大大降低了计算的复杂度，提高了程序执行效率。

3、在进行图分割时，改进了经典的GN社团生成方法，进一步提高了程序运行效率。

4、在社团生成过程中，结合了静态特征来判定最优划分效果，而非仅由图的拓扑结构特征来确定社团结果，使得本方法划分出的社团能够更好的反应移动应用的真实行为。

5、机器学习的训练阶段采用线下单独训练的方式执行，不会降低对目标程序进行实际检测时的运行效率。

附图说明

图1为本恶意代码检测方法的整体架构图。

图2为本发明的检测环境拓扑图。

图3为Android应用程序逆向工程流程图。

图4为本发明社团生成流程图。

图5为机器学习与恶意代码识别流程图。

图6为本发明方法与传统GN方法的社团生成效率比较。

图7为本发明方法在不同规模的训练集下的检测效率。

具体实施方式

下面结合附图和具体实施方式对本发明作进一步详细的说明。本发明方法结合函数调用图的结构特征和应用程序的静态特征来共同判定最理想的社团划分结果，再从最终划分出的社团中提取出用于机器学习的特征，将它们放入特征向量进行分类学习，从而达到判定该应用程序恶意性的目的。本发明方法通过改进GN方法来提高图的划分效率，使用机器学习技术来进行恶意性判断也绕开了图相似度比较带来的复杂计算。实验结果表明该方法能够高效率的识别恶意代码。

按照图2所示的检测环境拓扑图搭建检测环境。其中，测试服务器端操作系统为ubuntu12.04，反编译工具部署Androguard1.6等，Java运行环境部署Eclipse4及其以上版本。移动终端搭载Android 2.x和以上版本的系统，以满足能够运行不同时期和类型的移动应用程序的要求。样本数据库空间推荐在500G以上，并具有继续可扩展性，以具备容纳足够多样本的能力，测试服务器上需要配置防火墙。

本发明具体实现过程详述如下：

步骤1：首先对待检测的移动应用程序进行反编译，得到反编译代码，如“.smali”代码文件等，并从中提取出该应用使用到的权限、与权限相关联的函数、系统函数、JAVA包、类以及所有函数及其调用关系等静态信息。例如，如附图3，使用反编译工具(如androguard、apktool等)将APK文件进行反编译，能够获取到res中的布局文件、drawable中的图片资源，AndroidManifest.xml中的组件声明和权限声明，values中的常量值等数据。同时，将apk改为zip或rar后缀，用解压工具解压获取到classes.dex文件，然后使用dex2jar工具将其反编译，获取到classes.jar文件，然后使用JD-GUI能够获取到该应用的java源代码。

步骤2：通过分析大量移动应用程序的静态信息，得到不同权限、系统函数、包等静态特征出现在良性样本或恶意样本的频率，并根据它们在不同样本中出现的频率差分别为其分配了恶意值。

步骤3：根据步骤1中提取的所有函数及其调用关系构建出函数调用图。

步骤4：对函数调用图进行预处理，主要包括2个方面：首先删除孤立节点，孤立节点较难反应出代码的某种行为特征，而且经重打包技术产生的功能模块也很难发生在孤立节点上，故将其删除；其次，为函数调用图的节点分配权值，节点的权值就是与之相关的敏感信息的恶意值之和。

步骤5：为了提高图的划分效率，改进GN社团生成方法。本方法将边介数的计算过程重新定义为关键节点到其余节点间的最短路径，而非任意节点对之间的最短路径。对关键节点的定义为：

其中，n代表整个图中的节点数，D_i是节点i的度，K是与节点i直接相连的节点数，W(q_m)是节点集k中节点m的权重。需要注意的是，在计算边介数时需要考虑边的权重，以保证权重较高的边不会轻易被删除掉，因此，边介数也被重新定义了。

假设图被定义为G＝(V,E)，其中V是节点集，E是边集，边介数的计算公式为：

其中，是节点i与节点j之间包含边e的最短路径，g_e是边e的权重。

步骤6：重定义图循环分裂的终止条件；在GN方法中，模块度参数Q是从图结构上衡量和评价社团生成效果的指标，Q被定义为：

Q＝∑_j(e_jj-a_j²)

其中社团j的矩阵元素被定义为e_jj，它表示社团j中边的数量；a_j²表示连接社团j中任意点的边的数量；在函数调用图的分裂中，Q的值一般在0.3至0.7之间变动，越接近1效果越好；当Q的值达到巅峰并开始下降时，将终止计算。

步骤7：社团结构最终生成结果确定；每次删除边介数最高的边后所形成的社团划分版本都会被记录下来，通过对这些划分版本中各个社团的恶意值、属性、节点规模情况进行评价，能够选择出最优的一个划分版本，该版本中的社团就被确定为最终社团生成结果。

步骤8：社团特征提取；从最终确定的社团划分版本中，提取出三方面信息作为分类特征：1)具有恶意特征的社团数；2)各社团中的最高恶意值；3)各社团恶意值总和。

步骤9：特征向量分类训练，得到判定结果；通过对分类特征进行机器分类学习，得到最终的恶意性判定结果。

下面将结合附图在方法运行效率、检测率等方面对本发明提出的方法与传统的GN方法、三种恶意代码检测软件、以及一种基于控制流图的检测方法进行比较。

如附图6所示，随着函数调用图节点数量的增加，使用传统GN方法进行图分裂的执行时间增长很快，而本方法的执行时间并没有快速增长，并始终保持在一个合理的区间。如附图7所示，随着训练集的压缩，本方法的检测效率呈较缓慢的下降，并始终保持在80％以上，表明本方法的检测率并没有过度依赖训练集。

表1本方法与三种病毒检测软件以及一种基于控制流图的检测方法的检测效率对比

从表1可以看出，在对实验数据集中部分主要病毒家族的恶意代码检测中，本方法的检测率范围在93.8％至100％之间，平均检测率为99.1％，该结果要优于表1中的其他病毒检测软件和方法。