基于API和Permission的Android恶意软件静态检测方法研究

杨鸣坤 罗锦光 欧跃发 慕德俊

1(桂林航天工业学院计算机科学与工程学院 广西 桂林 541004)2(广西电力职业技术学院电子与信息工程系 广西 南宁 530007)3(北部湾大学机械与船舶海洋工程学院 广西 钦州 535011)4(西北工业大学自动化学院 陕西 西安 710072)

0 引 言

360互联网安全中心发布的《2018中国手机安全生态报告》[1]中指出，仅2018年上半年该中心截获安卓平台新增恶意程序样本283.1万个。其中，截获新增手机勒索软件127 455个，1月-7月截获新增手机挖矿木马4 806个。挖矿木马的新增是2017年全年截获量的近20倍。当前APP权限越界行为整体呈增长趋势，尤其是在一些隐私相关的权限使用上。其中，写入通话记录权限被滥用的情况最为严重。

目前，Android软件检测方法主要有基于特征签名(signature-based，又名特征码)的检测方法和基于行为(behavior-based)的检测方法[2-3]。该种检测方法应用广泛，但无法检测未知恶意软件。并且，由于必须要保存每一个病毒新变种的特征签名，会直接导致特征库不断膨胀，进而影响检索特征的复杂度，最终带来能耗的增加。而能耗对智能手机等移动设备来说是非常重要的指标。文献[4-8]分别提出了基于行为的检测方法、结合了静态分析和动态分析的ANDRUBIS系统、一种挖掘权限频繁项集的算法、基于统计学特征的Android恶意应用检测方法以及采用多核模糊支持向量机算法对恶意软件进行检测分类。这些方法中都是通过人工智能算法或数据挖掘算法对Android APK的恶意软件进行分类预测，而没有很好地利用APK文件中的静态信息和Permission在软件的使用率对分类算法的影响。因此本文提出了一种以Android API和Permission作为Android APK特征的检测方案，此方案将一个APK转化为可以量化和参与计算的基于API或Permission的特征向量，实现了以API或Permission为特征的基于改进的k-NN算法静态检测方法。

1 传统k-NN分类算法

k近邻(k-Nearest Neighbour，k-NN)分类算法[9]，是成熟的机器学习算法。该方法的工作原理是存在一个训练样本集，该样本集中的每个数据都存在类别标签，即每一个数据与所属分类的对应关系，当输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，算法提取样本集中特征最相似数据(最近邻)的分类标签。一般来说，只选择样本数据集中前k个最相似的数据，通常k是不大于20的整数。

k-NN算法的核心思想是：当无法判定当前待分类点是从属于已经分类的哪一类时，可以依据统计学的理论看它所处的位置特征，衡量它周围邻居的权重，进而把它归到权重更大的那一类。该算法是基于实例的学习，使用算法时必须有接近实际数据的训练样本数据。在k-NN分类方法中，当数据量达到一定规模时，大概率会出现测试集中的数据(实际上此数据与被标记样本是相邻的)与相似样本的距离过大，导致分类准确率降低，无法有效执行。

2 APK静态信息过滤算法

要想对APK进行静态分析，首先要从APK中获取特征，被定义为恶意的APK都是完成了一定恶意行为的APK，而这些恶意行为最终都是靠程序开发者开发的功能函数来实现的。由于Android的机制，用户自己开发的函数要想实现一定的功能，必然要利用Android的API，所以对于出现APK中的所有函数调用，只将其中的Android API纳入到特征集合中，作为一组检测APK的特征。考虑到Android的安全机制和APK的运行特点，要想使用Android提供的系统功能和系统资源来施行软件的恶意行为，必然还要使用到Android提供的各种权限(Permission)，因此将APK中使用到的权限信息作为另一组检测APK的特征[10]。而本文APK的特征定义就是从反编译之后的代码和Manifest文件中抽取的Android API或Permission信息[11],详细实现过程如下。

假设一个特征(API或者Permission)在训练集样本的m个恶意APK中都有出现，在n个正常APK中都有出现，训练集样本的恶意APK的总数为M，正常APK的总数为N。那么，该特征在恶意APK中的使用率为：

(1)

该特征在正常APK中的使用率为：

(2)

则同一个特征在不同APK中的使用率之差为：

t=|fn-fp|

(3)

准备分类器数据在对算法进行训练之前，要对提取出来的APK静态信息进行过滤，即去掉冗余信息，减少冗余信息的干扰[12-13]。它包括两个方面的内容：一是通过统计学的计算找出一些高危、高使用率的API和Permission作为基准特征；二是对已经提取过的APK进行更进一步的特征向量的构造[14]。要想找出这样的基准API和Permission就要对训练集样本中的APK进行统计，从数据库中取出每个APK中使用的API和Permission，计算每一个API和Permission在多少个训练样本APK中出现过。其算法具体实现如下：

输入：从数据库中取出(M+N)个APK中使用的API和Permission。

Step1FindAPI()；FindPermission()；找基准API和Permission集合。其中基准API集合选择fn、fp、t值大于等于0.2的特征；而基准Permission的集合是仅选择fn和fp都大于等于0.2的。

Step2TranslateAPIVM()；TranslatePermissionVM()；将每一个APK转换成一个向量。其中，提取出的每个APK向量中的每一维的值表示0或1，值为0表示APK没有使用其基准集合中对应的API或Permission，值为1表示APK中使用了其基准集合中对应的API或Permission。

Step3重复(M+N)次Step2。

输出：使用分类算法的训练集，即所有APK的特征向量组成的矩阵。

3 改进的k-NN算法分类器

为了能够使k-NN算法中恶意APK的特征向量与正常APK的特征向量距离更远，使两个恶意APK的特征向量的距离更近，本文对k-NN算法进行了改动。在确定APK的基准特征(API和Permission)之后，如果给恶意APK中使用率高、正常APK中使用率低的API以小的权值，或给恶意APK中使用率低，正常APK中使用率高的API以大的权值，那么会使两个恶意APK的距离比恶意与正常APK的距离更近，这样会使算法的精确度更高。经过实验验证，式(3)正好满足上述规则，即该值为改进的k-NN算法中特征的权值。对未知类别属性的数据集中的每个点一次执行以下操作：

(1) 计算已知类别数据集中的点与当前点之间的距离；

(2) 按照距离递增次序排序；

(3) 选取与当前点距离最小的k个点；

(4) 确定前k个点所在类别的出现频率；

(5) 返回前k个点出现频率最高的类别作为当前点的预测分类。

第(1)步采用欧式距离公式计算两个向量点之间的距离。

点1：w1=(w11,w12,…，w1i,…,w1n)

点2：w2=(w21,w22,…，w2i,…,w2n)

距离：

计算完所有点之间的距离后，可以对数据按照从小到大的次序排列。然后确定前k个距离最小元素所代表的APK的类别，并且k总是正整数，最后输出k个类别中占多数的类别，即为当前测试的APK的类别。为了测试分类器的效果，可以使用已知类别的数据，检验分类器测出的结果是否符合预期结果。通过大量的测试数据，得到分类器的错误率为分类器给出错误结果的次数除以测试执行的总数。

在获得了样本训练集的数据矩阵和样本训练集的类别向量的基础上，设定算法中的k值为10。对于每个样本测试集中的APK，从数据库中分别提取出它关于API和Permission的特征向量，再从对应的数据表中提取出API和Permission的权值向量。然后用待检测APK的特征向量和样本训练集数据矩阵、类别向量，以及API和Permission的权值向量和k值作为改进的k-NN分类器的输入，算法的输出即为待检测的APK的属性类别。

4 静态检测方案的设计与实现

简单地说，机器学习就是把无序的数据转换成有用的信息[15]。本文基于Android APK中包含的各种静态信息利用机器学习方法来判别一个APK是否是恶意程序。

本文首先对已收集到的两类APK样本(恶意APK和正常APK)进行静态特征的提取，然后将提取到的各种静态信息(包括：权限、API、VersionName、Package、MainActivity、ShareUserID、Feature、Activity、Service、Received、Intent)存入数据库中。再利用这些信息从中提取描述一个APK的各种特征，作为描述APK的特征集合，将这些集合存入到数据库中，以提高后续算法的执行效率。从数据库中取出每一个APK的信息，根据特征集合合成每个APK的特征向量，并将每个APK的特征向量作为中间结果存入数据库中。最后将数据库描述APK的中间结果作为分类算法的训练集，执行分类算法，将算法执行的结果存入数据库。测试阶段是从数据库取出测试APK的特征向量，测试算法的精确度。

根据上述方案执行过程设计出的方案系统结构如图1所示。

微功能模块主要实现对文件的读写功能，从官方文件中提取Android API和权限，获取目录内的文件名和子目录名列表，获取一个文件的大小、MD5值等。具体主要是指该功能模块是对其他模块提供支持的一个共用模块，在其他模块中，会频繁用到一些共有的功能，比如：按行读取一个文件的内容；将Python中一个列表的内容按行写入一个dat文件中；获取一个字符串的MD5值，文件的大小、MD5值，当前时间，路径信息等。

静态信息提取模块是完成对APK中静态信息的提取。本模块采用ApkTool反编译工具，对Android APK进行反编译，在输出目录中会看到一个smali目录和AndroidManifest.xml文件，smali目录中按照Java源代码的目录结构存放了生成的所有smali文件。从这些smali文件和AndroidManifest.xml文件中抽取APK的静态信息，存储到数据库中，为最后生成APK的特征向量做准备工作。

分类器模块的设计构造了基于改进的k-NN算法的分类器。其主要实现过程是准备好执行算法所需要的数据，包括确定准API和Permission集合，每个基准特征的条件概率[16-17]、训练集和测试集的样本矩阵、训练集和测试集的样本类别向量、改进的k-NN算法需要的特征权值，最终构造分类器完成对测试集APK的测试。

数据库模块的设计和所有其他模块进行交互，负责将所有模块的计算结果存入数据库，还负责从数据库中取出数据，目的是减少计算量的重复，提升算法执行效率。本文实验所用到的数据表如表1所示。

续表1

5 实 验

本文在Ubuntu操作系统下进行仿真实验，Ubuntu安装在Vmware Workstation虚拟机上，主机采用Windows 7。编程实现语言为Python，采用APKTool工具对APK文件进行反编译，其命令格式为：apktool d[OPTS][apk文件路径][反编译输出目录]。

5.1 数据准备

使用机器学习的方法来对APK进行分类，在算法训练时，需要有足够多的样本集合才能确保分类器的检出性能。本文从网上收集了1 251个恶意APK，1 000个正常APK作为样本的训练集；收集了1 197个恶意APK，1 000个正常APK作为样本的测试集。采用Python语言编写程序，先反编译APK，然后根据已有的Android API和Permission从smali文件和AndroidManifest.xml文件中提取静态信息，并存入数据库，其中API一共18 646条，Permission一共151条。在对训练集APK静态信息进行统计的基础上，可以得出基准API和Permission及它们的权值。取出了120个基准API及其权值，部分数据如表2所示；25个基准Permission及其权值，详细如表3所示。

表2 基准API及其权值(部分数据)

续表2

表3 Permission的条件概率

续表3

根据基准API和Permission将APK转换成特征向量。APK关于API的特征向量是一个120维，关于Permission的特征向量是一个25维，每一维值为0或1的向量，0代表此维对应的API或Permission没有出现在对应的APK中，1代表此维对应的API或Permission出现在了对应的APK中。

5.2 测试指标

为了对实验结果进行分析，从而对算法的检测效率给出量化的结果，定义了一组测试指标：

TP(true positive)：正常APK被正确分类为正常APK的概率，TP=Rp/Np，Rp为被正确分类的正常APK个数，Np为正常APK的个数。

TN(true negative)：恶意APK被正确分类为恶意APK的概率，TN=Rn/Nn，Rn为被正确分类的恶意APK个数，Nn恶意APK的个数。

FP(false positive)：正常APK被错误分类为恶意APK的概率，FP=Wp/Np，Wp为正常APK被错误分类为恶意APK的个数。

FN(false negaitive)：恶意APK被错误分类为正常APK的概率，FN=Wn/Nn，Wn为恶意APK被错误分类为正常APK的个数。

Accuracy：APK被正确分类的概率，Accuracy=(Rp+Rn)/(Np+Nn)。

5.3 实验结果与分析

表4和表5分别列出了使用基于API的特征向量和基于Permission的特征向量的传统k-NN算法和改进的k-NN算法的检测效果。对比两表可以看出，本文方案的检测效果达到了一定的水平。

表4 基于传统的k-NN算法的检测效果

续表4

表5 基于改进的k-NN算法的检测效果

在同样的测试集中，改进的k-NN算法检测方案比传统的k-NN算法检测方案更好，其准确率提升11%左右。原因是实施算法之前提出的特征权值两者有所不同，改进的算法中实现了恶意APK的特征向量与正常的APK的特征向量相似度更低，两个恶意或正常APK的特征向量相似度更高。

从改进k-NN检测方案来具体分析，以API为特征向量，正常APK和恶意APK的检出率分别达到了85%和83%以上。其中，正常APK的检出率与恶意APK的检出率差别不大，因为作为基准特征的API是从训练集的恶意样本和正常样本的共有API中提取出来的。对于没有被正确分类的APK，一是因为没有将敏感恶意API完全覆盖，一些恶意行为不能检测出来；二是因为正常APK中存在着一些跟恶意APK中相似的恶意行为(例如访问网络、访问位置信息、发送短信等)。以Permission为特征向量，正常APK和恶意APK的检出率分别达到了87%和85%以上。检出率整体上比以API为特征的检出率高，这是因为Android API数量相对于Permission来说要高很多，找出的作为基准的API可能存在冗余没有去除，所以检测效率没有以Permission为特征的方案高。

综上可见，本文提出的基于API的特征向量和Permission的特征向量的改进k-NN算法的检测方法是从Android APK中提取信息，再进行统计分析，最终确定了作为基准特征的API有120条，作为基准特征的Permission有25条，它们在恶意APK和正常APK中使用率都高于20%。实验结果表明，本文方法恶意APK和正常APK的检出率都在82%以上。

6 结 语

虽然本文方案达到了预期的实验效果，具备了一定的检测Android恶意软件的能力，但是仍有许多值得研究和改进的地方。如作为基准特征的API或Permission的选取有待改进，在对训练集APK中的API或Permission进行统计分析时，由于只采用了有或无的0/1方式，不能够真实地反映出某个API或Permission在APK中的真实使用率。一个API或Permission的调用序列，能够更真实地反映出恶意行为执行过程，在对恶意APK中的API或Permission进行统计分析时，如果能找出一些恶意行为固有的API或Permission调用序列，那么对于检测恶意APK将具有重大意义，基于API或Permission的恶意软件的检出率将会有很大提高。