基于数据挖掘的Android恶意应用检测方法的研究∗

李秀 陆南

（江苏科技大学电子信息学院 镇江 212000）

1 引言

360手机卫士报告显示［1］，就目前截获的An⁃droid恶意应用已达到三千五百万个，仅2016年全年，截获的Android恶意应用有1403.3万个，而且还在以每天3.8万的增速增加。同时，累计检测到的已感染Android恶意应用的用户达到2.14亿。可以说，近五年以来，Android恶意应用正在以指数形式增长。

目前Android恶意应用的检测方法主要分为动态检测和静态检测。静态检测中主流的静态特征主要是权限，Enck［2］、Barrera［3］等都通过对权限的研究来区分正常应用和恶意应用。且随着大数据时代的到来，数据挖掘得到越来越广泛的应用，很多研究者将数据挖掘应用在移动端恶意应用检测上。

Wu D J等利用数据挖掘中的聚类和分类提出了一种恶意应用检测方法，首先运用聚类中的K-均值算法和奇异值分解算法SVD处理静态特征，然后运用分类中的K最近邻算法KNN进行分类建模［4］。

杨欢等提出了一种PApriori检测方法，利用Apriori算法分别对49个恶意应用家族所申请的权限信息进行关联分析，得到每个恶意应用家族在不同支持度和置信度下的极大频繁项集和关联规则［5］。但是该方法受到Apriori算法的限制，运行时间较长、效率较低。

Sanz等提出了一种PUMA工具，该工具提取权限特征，然后用多种数据挖掘算法对数据进行分类建模，最后用多种分类模型对239个待测应用程序进行分类［6］，但是该方法没有对权限进行相应处理，且待测应用程序数量较少，不能充分说明结果。

周运飞等人首先对权限进行频繁模式挖掘，然后得到指定支持度下的极大频繁项集，最后将它们作为朴素贝叶斯的特征输入［7］。该方法的真正类率和真负类率分别为82.6%和83.6%，相对较低，且该方法没有充分考虑样本的独立性。

本文提出了RApriori方法：

1）在利用Apriori算法挖掘极大频繁项集之前，先用Relief算法对权限特征去冗余，进行第一步特征选择，这大大减少了Apriori算法的工作量；

2）利用Apriori算法分析正常应用和恶意应用申请的权限的差异，分别得出正常应用和恶意应用的极大频繁项集，进行第二步特征选择。这样选择出的特征有很强的关联性，对分类有较大贡献。

利用随机森林算法建立多棵分类树，每棵树都对待测应用进行判断，这样减小了判断错误率，提高了检测准确率。

2 检测方法设计

检测方法共分为三部分：特征准备、特征选择和特征分类。其流程图如图1所示。

图1 RApriori检测流程图

2.1 特征准备

首先获得Android正常应用和恶意应用的安装包，即.apk文件。正常应用来自360应用市场（通过腾讯管家和金山毒霸等杀毒软件进行扫描，基本确保了应用程序的安全性），共300个；恶意应用来自VirusShare，共300个；然后解压每个Android应用程序；最后利用apktool批量反编译Android应用程序，提取每个Android应用程序的权限特征，得到初始权限特征库。此时的训练样本即是拥有初代权限特征库的训练样本。

2.2 特征选择

2.2.1 基于Relief算法去冗余

应用程序所申请的权限都不是单一存在的，它们之间有一定的关联关系，本文利用Apriori算法分别对正常应用和恶意应用的权限进行关联分析。

如果对应用程序申请的所有权限全部进行关联分析，毫无疑问，费时费力。所以，对权限特征进行去冗余是有必要的。在对特征去冗余的几种算法进行研究比较之后，发现Relief算法能很好适用于该场景。

Relief算法在1992年由Kira和Rendell提出，该算法设计了一个“相关统计量”来度量特征的重要性，这个“相关统计量”可以视为是每个特征的“权重”［8］。它的基本思想是根据各个特征和类别的相关性赋予特征不同的权重，权重小于某个阈值的特征将被移除。

从拥有初代权限特征库的训练样本中随机选择一个样本R（该样本可能是正常应用也可能是恶意应用）；然后在与R同类的样本集中，寻找与之最相近的样本H；再在与R不同类的样本集中，寻找与之最近邻的样本M，最后根据式（1）更新每个权限特征的权重。

式中：R（j）表示样本R关于第j个权限特征的值；d（·）表示距离函数，用来计算样本R和样本H（或样本M）关于某个权限特征的距离；m是随机抽样的次数。

权限特征是非数值型特征，距离函数d（·）定义如式（2）所示。

最后经过筛选过滤，剩余65个权限。权重从大 到 小 依 次 为 SEND_SMS、RECEIVE_SMS、WRITE_SETTINGS、 READ_PHONE_STATE、READ_SMS、MOUNT_UNMOUNT_FILESYSTEMS、ACCESS_NETWORK_STATE、 SYS⁃TEM_ALERT_WINDOW、 RECEIVE_BOOT_COM⁃PLETED、 VIBRATE、 CHANGE_NET⁃WORK_STATE、CAMERA……由于权限较多，在此不一一赘述。

删除拥有初代权限特征库的训练样本中每个Android应用程序多余的权限特征，即得到拥有二代权限特征库的训练样本。

2.2.2 基于Apriori算法关联选择

Apriori作为数据挖掘中最重要的关联规则算法，由Agrawal等在1993年提出［9］，一经提出，就被应用到各个领域。Wang等将Apriori算法运用在电脑端恶意代码检测［10］；郭淑红等利用Apriori算法研究股票市场中股票价格的相关性［11］；金锐等利用Apriori算法，探求中药中气-味-效三者之间的频繁模式和强关联规则［12］；韦哲等通过Apriori生成的关联规则来完成对糖尿病高危人群的初判断［13］。

Apriori算法的核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。

将拥有二代权限特征库的训练样本送入Apri⁃ori算法，通过该算法分别找到正常应用和恶意应用的极大频繁项集，即是分别找到了正常应用和恶意应用具有强关联规则的权限特征，而这些权限能很好地区分正常应用和恶意应用。

当支持度为0.4时，正常应用的极大频繁项集为 ACCESS_COARSE_LOCATION、CHANGE_WIFI_STATE、ACCESS_FINE_LOCATION、GET_TASKS、 INTERNET、 READ_EXTERNAL_STOR⁃AGE、 READ_PHONE_STATE、 ACCESS_NET⁃WORK_STATE、SYSTEM_ALERT_WINDOW、VI⁃BRATE、 WAKE_LOCK、 WRITE_EXTERNAL_STORAGE、 WRITE_SETTINGS、 ACCESS_WIFI_STATE。

当支持度为0.25时，恶意应用的极大频繁项集为 INTERNET、 READ_EXTERNAL_STORAGE、READ_PHONE_STATE、READ_SMS、RECEIVE_SMS、SEND_SMS、WAKE_LOCK、WRITE_EXTER⁃NAL_STORAGE、RECEIVE、C2D_MESSAGE、AC⁃CESS_COARSE_LOCATION、ACCESS_COARSE_UPDATES、ACCESS_FINE_LOCATION、INSTALL_PACKAGES、RECEIVE_BOOT_COMPLETED、AC⁃CESS_NETWORK_STATE、SYSTEM_ALERT_WIN⁃DOW、WRITE_SECURE_SETTINGS、WRITE_SET⁃TINGS、SET_ALARM、INSTALL_SHORTCUT。

将以上正常应用和恶意应用的极大频繁项集相结合，即得到经过二次特征选择的最终权限特征库。

删除拥有二代权限特征库的训练样本中每个Android应用程序多余的权限特征，即得到拥有最终权限特征库的训练样本。

2.3 特征分类

随机森林算法［14］将随机性引入其输入中，使用不同的随机数多次重复学习，然后将多个分类器的预测结果通过投票的方式得出结论，这大大增加了分类结果的稳定性和正确率。

从建立的森林中随机选择一棵分类树，该分类树如图2所示。

多棵分类树构成随机森林算法分类器，使用该分类器即可检测Android应用程序是否是恶意应用。

3 实验结果与分析

3.1 实验样本

正常应用样本共1000个，主要从360应用市场获取，并且通过腾讯管家和金山毒霸对该样本进行扫描杀毒，基本确保了正常应用的安全性。恶意应用样本共1000个，主要从国外的研究机构Vi⁃rusShare获取。

训练样本主要包含正常应用样本300个、恶意应用样本300个。为充分了解RApriori方法的有效性和稳定性，测试样本主要分为7组，即在包含正常应用样本300个、恶意应用样本300个的训练样本的基础之上每次添加正常应用100个、恶意应用100个，共添加7次。

图2 决策树

将7组测试样本分别利用apktool进行反编译，批量获得它们的权限特征，此时得到的是7组拥有初代权限特征库的测试样本。分别对7组拥有初代权限特征库的测试样本进行以下处理：对比经过Relief算法和Apriori算法的最终权限特征库，把拥有初代权限特征库的测试样本的每一个Android应用程序多余的权限剔除。最后得到7组拥有最终权限特征库的测试样本。

3.2 实验性能参数

本文的实验性能参数主要有4个：真正类、假正类、真负类和假负类。

1）真正类，TP（True Positive），如果样本实际为正类并且被检测为正类。

2）假正类，FP（False Positive），如果样本实际为负类但被检测为正类。

3）真负类，TN（True Negative），如果样本实际为负类并且被检测为负类。

4）假负类，FN（False Negative），如果样本实际为正类但被检测为负类。

根据4个实验性能参数得到4个实验性能指标：真正类率、假正类率、真负类率和假负类率。

真正类率用TPR（True Positive Rate）表示，其计算公式为

假正类率用FPR（False Positive Rate）表示，其计算公式为

真负类率用TNP（True Negative Rate）表示，其计算公式为

假负类率用FNR（False Negative Rate）表示，其计算公式为

3.3 实验结果与分析

将7组拥有最终权限特征库的测试样本分别作为随机森林算法分类模型的输入，得到的实验结果如表1所示。

表1 RApriori方法实验结果详情表

由上表可知，RApriori方法具有较高的准确率，真正类率和真负类率基本达到90%，而假正类率和假负类率都不到10%。此外，在这七次实验中，随着测试样本数量的增多，真正类率和真负类率有相应的减少，但幅度并不大，说明该方法可以用来检测大量恶意应用。

上述实验是经过特征选择后的实验结果，如果不经过特征选择，直接把拥有初始权限特征库的训练样本作为随机森林算法的输入，分类建模，然后对7组拥有初始权限特征库的测试样本分别进行检测，得到的检测结果详情表如表2所示。

表2 未经特征选择的实验结果详情表

由上表可以看出，如果不经过特征选择，直接利用随机森林算法分类建模，得到的假正类率有的高达46.6%，而真负类率仅仅为53.4%。且实验结果不稳定，相差较大。

随机森林算法是建立在决策树算法的基础上，决策树只需建立一棵分类树即可，而随机森林算法需要建立多棵分类树，文献［15］使用决策树分类器来检测恶意应用。在经过使用本文提出的特征选择方法处理训练样本和测试样本之后，使用决策树分类的实验结果详情表如表3所示。

表3 决策树分类实验结果详情表

由上表可以看出，使用决策树分类，真正类率和真负类率基本稳定在80%，比使用随机森林算法分类低10%左右，而假正类率和假负类率基本稳定在19%，比使用随机森林算法分类高10%左右。

4 结语

本文提出了一种特征选择方法RApriori，该方法结合Relief算法和Apriori算法对权限进行二次特征选择。利用Relief算法对权限进行去冗余，这大大减小了Apriori算法的计算量。选择具有良好分类特性的随机森林算法，该算法基于决策树算法，不同的是，随机森林会建立多棵分类树，每棵分类树都对待测应用进行判断，最后用投票的方式来决定判断的结果，这样大大提高了检测的正确率，并降低了检测的误报率。

RApriori方法只针对权限进行了研究，如果应用程序存在权限绕过问题（有些应用程序可以执行某些权限的行为，但是在AndroidManifest.xml文件中并没有申请该权限），很可能会存在漏报问题。下一步工作中，静态特征除了研究权限之外，可以增加诸如意图、广播接收器等，更清楚了解应用程序的行为信息。