一种基于改进的关联规则挖掘算法的Android恶意软件检测方法∗

严 喆 朱保平

1 引言

现有的恶意软件检测方法主要分为两大类［1］，一类是基于特征码的，另外一类是基于行为的。基于特征码的检测方法主要通过判断待检测的软件是否具有已知恶意软件的特征代码片段，这种方法对于已知恶意软件命中率高，但是无法检测出未知的恶意软件。2012年11月，Google提出了将在系统中加入名为“application verification service”的安全特性，Google意图通过“application verification service”来对Android市场进行监督。除此之外，著名的检测工具Androguard［2］也是基于特征码对恶意软件进行检测的，它误报率低，但是由于它是基于特征码进行检测的，因此只能检测出已知的恶意软件，无法对未知的恶意软件进行检测。

基于行为的检测方法［3］是通过对比目标软件和已知的恶意软件的行为来判断目标软件是否是恶意软件。本文主要是对基于权限特征的研究。Zhou Yajin等［4］开发了一个 Android恶意软件的检测系统DroidRanger，在这个系统中，作者使用了两种模式来对恶意软件进行检测，其中一种模式就是基于软件权限行为的过滤方法，它们通过总结不同恶意软件族所申请的敏感权限组合，以此作为过滤标准来判定恶意软件。William Enck等［5］基于Android应用申请的权限列表开发出了Kirin系统，并且它们在对已有的样本学习后，总结并制定出9条与权限相关的安全规则以此对从Android市场上下载下来的310个Android软件进行检测。黄伟等［6］提出了一种基于集成分类的恶意软件检测方法，作者提出的方法中有一部分是在软件权限特征上建立基分类器，并将产生的分类结果用于最后的集成分类模型。Zhang Y等［7］提出了VetDroid系统，作者从软件中提取权限，然后利用自然语言处理技术将软件请求的权限与软件描述文件中描述的权限进行对比依此来识别恶意应用。Arp D等［8］提出了一种检测方法，这种检测方法是基于线性向量机实现的，通过对恶意软件静态分析，收集出软件尽可能多的特征，包括权限特征，API调用特征，网络地址特征等等。

随着Android设备的日益增长，Android平台恶意软件的检测需求也越来越大。由于Android软件申请的各个权限体现着软件的行为特点，一个恶意行为的产生需要多个权限的配合，而经典的关联规则挖掘算法存在着性能缺陷，直接将它运用到挖掘软件权限之间的关系效果不理想，针对以上问题，本文在对Eclat算法进行改进的基础上提出了一个AEclat算法，该算法可以挖掘出恶意软件的极大频繁项集，通过与待检测软件进行权限匹配度检测来判断该软件是否为恶意软件，以此为用户提供参考依据，从而提高Android系统的安全性。

2 基于权限的频繁模式挖掘算法AEclat

本文算法的主要设计思想是：Android软件申请的权限往往会体现出软件的行为特征，因此对软件申请的权限的研究在恶意软件的检测中起着很重要的作用。而对单一权限的研究无法全面地反映软件的行为，往往一个恶意行为的产生需要多个权限的配合，权限之间的关联关系就能反映出软件的行为信息。因此本文在软件申请的权限组合中进行权限关联规则挖掘，从而达到对恶意软件进行检测的目的。

Eclat算法［9］是一种基于深度优先的关联规则挖掘算法，它的数据的表现形式是垂直表示的，并且在Eclat算法中加入了倒排的思想，这加快了频繁项集的生成速度，但是Eclat算法有着自身的局限性，并未充分利用Apriori算法中的先验性质，它是根据两个集合的并集产生新的候选项集，因此它产生的候选项集的数目会非常多，并且每一个都需要计算其支持度，这大大地降低了效率，因此直接利用Eclat算法对软件申请的权限进行关联规则挖掘效率是比较低的。本文在对Eclat算法进行优化的基础上结合软件的权限行为特征设计了基于权限的频繁模式挖掘算法AEclat，该算法以从软件提取出的权限作为数据集，根据软件申请的权限之间的关系，通过得到极大频繁项集，进一步构建权限关系特征库，依此进行Android恶意软件的检测。

本文是在49个恶意软件族上分别运用AEclat算法进行关联规则挖掘，并不是将全部应用混在一起进行挖掘。因为不同的恶意软件族有着自己的特点，分开进行检测更能提高检测的准确性。

本文先对涉及的49个恶意软件族的权限数据库进行预处理。对于每一族应用，都采取以下几个步骤：

1）提取出软件申请的权限，分别构成对应族的权限数据库；

2）统计出软件使用权限的次数，在权限数据库中删除掉该族软件很少申请的权限；

3）找出该族软件都申请的权限；

4）将已经预处理后的权限数据库运用AEclat算法产生所有频繁项集，找出长度最大的频繁项集作为极大频繁项集；

5）把3）找出的权限添加进4）得到的极大频繁项集中，作为最终的极大频繁项集。

具体算法如下：

算法1 AEclat算法

输入：

DataSeti：49个恶意软件族，其中i=1，2…49。

minsup：最小支持度阈值

输出：极大频繁项集数据库DataSet_Permissions；

1）for（i=0；i＜49；i++）｛

2） get Lcommon；//得到该族所有软件都申请的权限；

3） DataSeti=delete（Lcommon） ；//在原有的数据库中删除掉Lcommon；

4） DataSeti=delete（Lrare）； //删除掉所有软件都很少使用的权限；

5）DataSeti=adjust（DataSeti）；//按照字母表的顺序对Data-Seti中的权限进行排序

//调整；

6） L=frequently_permission_set（DataSeti，minsup）；//得 到DataSeti的频繁项集；

7） get Li；//在L中选取长度最大的频繁项集作为极大频繁项集Li；

8） 将Lcommon增加到Li中；

9） 将Li增加至DataSet_Permissions中；

10）｝

11）return DataSet_Permissions；

Procedure frequently_permission_set（DataSeti，minsup）

1）第一次扫描事务数据库DataSeti，得到频繁一项集，L=L∪L1，L初始为φ；

2）二次扫描事务数据库DataSeti，得到频繁2项集，L=L∪L2，设临时候选集Li，初始时Li=L2；

3）repeat

4） for each tj∈ Li｛

5） for each tk∈Li&k＜j｛

6） M=tj∪tk；

7） if（M的所有含有n-1项的子集在L中都可以找到）｛//n=M中元素个数

8） Tidsets（M）=Tidsets（tj）∩ Tidsets（tk）；//Tidsets（M）为M的垂直数据表示；

9） if（|Tidsets（M）|＞=minsup）｛

10） L=L∪M，X=X∪M，初始时X=φ；｝

11） else跳出循环，转入15）；//由于元素的有序性，

后面的频繁项集均//不必连接

12） ｝

13）｝

14）｝

15）Li=X；X=φ；16）until Li为φ。

3 基于AEclat算法的Android恶意软件检测方法

3.1 相关概念

定义1 权限匹配度。待检测软件申请的权限与对应恶意软件族极大频繁项集中权限匹配个数占对应恶意软件族的极大频繁项集的权限总数的百分比叫做权限匹配度。它用于衡量待检测软件是否属于某一恶意软件族。

式中：Lm表示权限匹配度，Nf表示待检测软件申请的权限与对应检测族极大频繁项集中权限匹配个数，Ntotal表示对应检测族的极大频繁项集的权限总数。在本实验中，选取匹配度阈值为0.95。

定义2 命中率。对于恶意软件，恶意软件识别正确的数目占全部软件恶意软件的百分比叫做命中率。式中：Hitrate表示命中率，TP表示恶意软件识别正确的数目，FP表示恶意软件被识别为非恶意软件的数目。

定义3 误报率。对于非恶意软件，非恶意软件被正确识别的数目占全部非恶意软件的百分比叫做误报率。

式中：Falsealarmrate代表误报率，TN代表非恶意软件被正确识别的数目，FN代表非恶意软件被识别为恶意软件的数目。

3.2 基于AEclat算法的Android恶意软件检测方法检测流程

本文在前面介绍了基于权限的频繁模式挖掘算法AEclat，本节将以AEclat算法为核心，介绍一种基于AEclat算法的Android恶意软件检测方法，该方法流程如图1所示。首先构建样本库，该样本库包含了49个恶意软件族，然后对这些恶意软件族进行静态解析，得到软件申请的权限，分别构建各族权限数据库，在各族数据库上分别运用AEclat算法进行挖掘，通过得到各族极大频繁项集，构建出权限关系特征库，最后，输入待检测软件，使其匹配权限关系特征库从而得到统计结果。

基于此流程图，下面给出基于该检测方法的详细说明。

构建训练样本库：本文采用的用于训练的恶意软件样本是文献［10］中的样本，这个样本是由49个恶意软件家族的1260个恶意软件组成；

静态解析app：对各族每个软件样本利用apktool工具进行反编译，获取各个软件的AndroidManifest.xml文件，从AndroidManifest.xml文件中获取各软件的申请权限列表；

构建权限数据库：对于某一族恶意软件，该族每个软件申请的权限作为一行，初步得到该族权限数据库。然后利用第2节所述的数据库预处理方法，构建权限数据库，作为AEclat算法的输入。

AEclat算法处理：使用第2节所述的算法挖掘软件权限之间的关联性，得到各族软件的极大频繁项集。

构建权限关系特征库：权限关系特征库的每一行为一族的极大频繁项集，该特征库用于匹配待检测软件。

匹配检测：输入待检测软件，提取出其申请的权限信息，然后与构建好的权限关系特征库进行匹配，计算出权限匹配度，匹配度大于设置的阈值即认为该软件属于该族恶意软件。

统计结果：对于恶意软件，计算命中率，对于非恶意软件，计算误报率。

4 实验与分析

本文通过设计多个实验来对提出的算法进行有效性和正确性检验，并与其他Android恶意软件检测方法进行对比，实验证明本文提出的方法效果更好。本实验的硬件环境是Intel（R）Pentium（R）CPUG3240，内存6G，操作系统是Windows 7。前文所述的爬虫程序以及格式化处理程序是用python实现的，AEclact算法实现是用Java完成的。

本文采用的测试样本由3部分组成。第一部分恶意软件样本是文献［10］中的样本，它们取自Android Malware Project，这个样本是由49个恶意软件家族的1260个恶意软件组成。第二部分非恶意软件样本是从Google play store上爬虫下来的并经过杀毒软件检测后筛选出来的1200个软件。最后一部分恶意软件样本是从Contagio Mobile中随机获取的200个恶意软件。本文先对包括49个家族的1260个恶意软件样本通过设置不同的最小支持度阈值minsup反复试验，对比考虑多次试验的命中率Hitrate，选取适当的minsup得到49族恶意软件的极大频繁项集。由于篇幅有限，表1展示了我们得到的一部分恶意软件家族的极大频繁项集。

使用本文所述的方法对Android Malware Project恶意软件样本进行检测，共检测出1078个恶意软件，得到的命中率为85.56%，具体结果见表2。对1200个非恶意软件检测，将81个软件误报为恶意软件，误报率为6.75%。对从Contagio Mobile中随机获取的200个恶意软件进行检测，共检测出恶意软件104个，命中率为51%。

表2 Android Malware Project样本不同系统检测结果表

4.1 关于提取的软件敏感权限的对比

DroidRanger［4］是 ZHOU Y J等开发的一个基于Android恶意软件的检测系统，他们提出了一个基于权限的过滤机制，总结出了9个恶意软件族所使用的敏感权限信息，并基于此来过滤可疑的恶意软件。表1是本文算法得到的权限项集和DroidRanger的对比。从对比中可以看出，DroidRanger提出的敏感权限相当有限，直接使用它进行恶意软件的判别将会导致准确率很低，而本文算法得出的极大频繁项集则是可以直接用于恶意软件的检测。

4.2 关于软件检测结果的对比

Androguard［2］是一个用 python 实现的静态的自动化检测程序，它提供了一系列的Apk以及odex，dex，arsc等分析处理功能。由于Androguard是基于python实现的，因此只要能运行python的系统，不论是Linux、Windows还是Mac都能运行Androguard。本文使用的是Ubuntu镜像ARE默认安装的版本。实验结果显示，对于Android Malware Project样本，检测出863个恶意软件，其命中率为68.49%，具体结果见表2。对1200个非恶意软件检测的误报率为0%。对从Contagio Mobile中随机获取的200个恶意软件进行检测的命中率为0%。

Google的“application verification service”启动服务后，当软件被安装到手机上时，软件的名称，SHAI值，版本等信息就会被推送到Google云上并进行检测，如果此软件有隐患，那么就会提示用户是否安装，如果检测到此软件是危险的软件，那么就会直接阻止用户安装。实验结果显示，对于Android Malware Project样本，检测出193个恶意软件，其命中率为15.32%，具体结果见表2。对1200个非恶意软件检测的误报率为0%。对从Contagio Mobile中随机获取的200个恶意软件进行检测的命中率为0%。

Kirin［5］是Enck等提出的基于权限的Android恶意软件检测方法。实验结果显示，对于Android Malware Project样本，检测出36个恶意软件，其命中率为2.86%，具体结果见表2。对1200个非恶意软件检测，系统将106个应用误报为恶意软件，其误报率为8.83%。对从Contagio Mobile中随机获取的200个恶意软件进行检测，检测出4个恶意软件，命中率为2%。

综上所述，对于Android Malware Project样本，明显本方法的命中率比其他三种方法高。对1200个非恶意软件，本文方法的误报率低于Kirin，虽然高于Androguard和Google，但是因为后两者只能识别已知软件，所以误报率为0，并且它们对于未知恶意软件的命中率为0，而本文方法相应的命中率则为51%。本文方法的研究重点是检测未知软件，因此在提高对未知应用的命中率的前提下，牺牲一定的误报率是可以接受的。而虽然Kirin也可以检测出一部分的未知恶意软件，但显然其命中率不如本文方法。

5 结语

针对Android平台恶意软件的检测需求的上升和现有的关联规则挖掘算法的效率较低，不能直接用于恶意软件的检测的问题，本文提出了一种基于权限关联规则的Android恶意软件检测方法。主要工作如下：

1）在对已有的关联规则挖掘算法Eclat算法进行优化的基础之上提出了基于权限的频繁模式挖掘算法AEclat；

2）提出了一种基于AEclat算法的Android恶意软件检测方法；

3）通过与DroidRanger系统的对比，实验证明本文提出的方法提取出的敏感权限更加全面，能够直接用于恶意软件的检测。

4）通过与Google、Kirin和Androguard恶意软件检测系统进行对比，实验分析说明本文提出的方法更好，具有一定的可行性。

［1］Anastasia S，Dennis G.Review of the mobile malware detection approaches［C］//Proceedings of the 23rd International Conference on Parallel，Distributed and Network-Based Processing.Washington，USA：IEEE Computer Society，2015：600-603.

［2］ Androguard ［EB/OL］.http：//code.google.com/p/androguard/，2013.

［3］Arp D，Spreitzenbarth M，Hübner M，et al.DREBIN：effective and explainable detection of Android malware in your pocket［C］//NDSS，2014：1-2.

［4］Zhou Yajin，Wang Zhi，Zhou Wu，et al.Hey，you，get off of my market：detecting malicious Apps in official and alternative Android markets［C］//Proceedings of the 19th Annual Network&Distributed System Security Symposium.Washington，USA：Internet Society，2012：123-129.

［5］Enck W，Ongtang M，Mcdaniel P.On lightweight mobile phone application certification［C］//Proceedings of the 16th ACM Conference on Computer and Communications Security CCS'09，Chicago，IL，USA，2009：235-245.

［6］黄伟，陈昊，郭雅娟，等.基于集成分类的恶意应用检测方法［J］.南京理工大学学报，2016，40（1）：35-40.

HUANGWei，CHENHao，GUOYajuan，et al.Mobile malware detection approach using ensemble classification［J］.Journal of Nanjing University of Science and Technology，2016，40（1）：35-40.

［7］Zhang Yuan，Yang Min，Yang Zhemin，et al.Permission use analysis for vetting undesirable behaviors in Android Apps［J］.IEEE Transactions on Information Forensics and Security，2014，9（11）：1828-1842.

［8］Mas'Ud M Z，Sahib S，Abdollah M F，et al.Analysis of features selection and machine learning classifier in Android malware detection［C］//Proceedings of IEEE International Conference on Information Science and Applications.Washington，USA：IEEE Computer Society，2014：1-5.

［9］Yu Xiaomei，Wang H.Improvement of Eclat Algorithm Based on Support in Frequent Itemset Mining［J］.Journal of Computers，2014，9（9）：12-15.

［10］Zhou Yajin，Jiang Xuxian.Dissecting Android malware：characterization and evolution［C］//Proceedings of the 33rd IEEE Symposium on Security and Privacy，Oakland，USA，2012：95-109.