王家琰　徐开勇　戴乐育

(解放军信息工程大学　河南 郑州 450000)

0　引　言

知名市场调研机构Gartner发布了2016年第四季度全球智能手机分析报告[1]，报告显示，在2016年第四季度，全球智能手机的总销量达4.32亿部。其中，在智能手机操作系统方面， Android系统市场占有率继续领跑，其市场份额达到了81.7%，相比之下， iOS系统第四季度市场份额为17.9%， 可见Android系统在智能终端领域有着举足轻重的作用。伴随着Android市场份额的增长，其安全问题也凸显出来，97%移动恶意应用程序开发者将Android操作系统作为攻击目标[2]。《2016年手机安全状况报告》[3]显示，2016年全年，360互联网安全中心累计监测到Android用户感染恶意程序2.53亿，平均每天恶意程序感染量约达到70万人次。综上，解决Android手机应用程序的安全问题迫在眉睫。

权限机制是Android系统安全架构中的重要组成部分。Android要求每个应用程序在开发时就声明它需要的权限以此来访问其他文件、数据和资源，否则，如果缺少必要的权限，应用程序将无法提供预期的功能与服务。研究发现[4]，随着Android版本的更新，可申请权限的数量正在日益增长，但并非提供更加细粒度的权限划分，而是提供更多的访问功能，使得普通用户在安装应用程序时难以理解和有效利用这一安全机制。

为了解决Android应用中存在的安全问题，本文提出一种基于权限特征的静态检测方法，设计了权限频繁项集挖掘算法——DroidFP-Growth算法来进行恶意应用的检测。首先使用工具提取应用程序权限列表，然后采用DdroidFP-Growth算法挖掘并构建权限特征关系库，最后对未知应用进行检测。通过实验证明本方法可以有效检测恶意应用。

1　相关工作

随着Android智能终端的普及，恶意应用检测技术也进入快速发展阶段，就目前来看，主流恶意应用检测方法分为两种：静态检测方法和动态检测方法。静态分析方法通常使用反编译技术得到Java源文件或JAR文件，通过检测权限、API调用、系统调用等特征来判断其是否为恶意应用；动态分析方法通过收集应用程序运行时的数据来检测应用程序是否有恶意行为。

权限机制作为Android系统的重要的安全机制之一，可以有效地用于检测恶意应用。文献[4]展望了Android系统权限机制的发展趋势，发现第三方市场提供的应用程序和开发商预装在Android终端的应用程序大多数存在申请权限过度的现象，违反了最少权限原则。文献[5]研究了危险权限组合，提出了几个危险的权限组合方式用于检测恶意应用。文献[6]提出了一个基于权限的Android平台的恶意应用检测方法，使用PCA(主成分分析)算法进行权限提取后的特征选择，并应用SVM(支持向量机)方法将应用分为良性或恶意。文献[7]提出一种基于Web的工具，称为“Stowaway”，此工具用于检测权限申请过度的问题。文献[8]利用Google Play收集应用程序，并利用机器学习的方法来检测恶意应用。文献[9]利用API调用特征进行检测，达到了较高的精度，并且发现了Google Play中的新的恶意软件家族。

近年来同样有利用数据挖掘技术来进行恶意应用检测。文献[10]设计了能够挖掘权限之间关联性的权限频繁模式挖掘算法—PApriori算法，该算法基于Apriori算法构造出权限关系特征库来检测未知的恶意应用，实验证明其结果具有有效性和正确性，但是算法的效率不高，耗费资源和时间较长。本文改进了FP-Growth算法[11]用于频繁项集的挖掘。FP-Growth算法效率优于Apriori算法。FP-Growth算法利用一种称为频繁模式树(FP-tree)的方式的存储数据，可以直接在FP-tree提取频繁项集。FP-tree可以将所有数据存储于其构造的分支当中，分支相互重叠越多，获得频繁项集越准确。FP-Growth算法只需要对数据库进行两次扫描，当处理更大数据集时，FP-Growth算法在速度和准确率上要明显优于Apriori算法。

2　权限频繁模式挖掘DroidFP-Growth算法

频繁项集是指频繁同时出现的数据的集合，关联规则是指数据可能的存在某种关系。从数据集中挖掘数据间的关联规则被称作关联分析。寻找数据的频繁项集是一项十分耗时的任务，所以需要用更加快速的方法挖掘频繁项集。不同类别Android应用程序会申请不同的权限，但是有相同恶意行为的应用程序会申请某几种相同的权限。我们将这几种共同的权限成为权限频繁项集，通过挖掘权限的频繁项集可以对恶意应用进行检测。

本文基于FP-Growth算法，设计了权限频繁项集挖掘算法DroidFP-Growth，同时在算法的基础上，增加了最大支持度的概念，可以有效地降低数据维度和计算复杂度，提高算法效率和准确率。

2.1　概念定义

定义1权限项集。权限的集合U={I1，I2，…Im}，I表示每个权限。

定义2事务。设权限数据库DB是事务的集合，其中每个事务T是单个应用程序申请的权限集合。

定义3支持度s。设U1为权限项集，s是权限样本库DB中事务包含U1的百分比，即概率P(U1)。最小支持度min_sup是权限项集U在样本集中出现的最小概率，最大支持度max_sup是权限项集U在样本集中出现的最大概率。

定义4支持度计数。权限I的出现次数。

定义5频繁项列表L。用于储存所有权限、支持度计数及节点指针的列表。

定义6权限FP-Tree。一种包含所有事务权限的数据存储结构。条件FP-Tree是以某一权限为基点，由FP-Tree中与下方分支一起出现的上方分支构造。

定义7条件权限基。条件权限基是以所查找权限项为结尾的分支的集合。

2.2　算法描述

DroidFP-Growth算法发现频繁项集的基本过程包含三个步骤：首先是筛选样本集，然后构造权限FP-Tree，最后从权限FP-Tree中挖掘权限频繁项集。下面通过一组实例描述算法。

步骤一：筛选样本集。在筛选中，首先根据单个权限的支持度进行筛选，在步骤三中，则是根据权限项集的支持度进行筛选。表1给出6个应用程序申请的所有权限，设最小支持度为3，即min_sup=50.00%，最大支持度为5，即max_sup=83.34%。

表1　一组恶意应用的事务数据样例DB

最小支持度为3，因此舍弃{WRITE_SMS}{RECEIVE_SMS}两个权限，最大支持度为5，先暂时剔除{WAKE_LOCK}权限。

步骤二：构造权限FP-Tree。

1)首先扫描一次样本库，获得频繁项的列表L，按照支持度计数递减排序，即L={{INTERNET}{SEND_SMS}{READ_PHONE_STATE}{ACCESS_FINE_LOCATION}{ACCESS_FINE_LOCATION}{RECORD_AUDIO}}。

2)第二次扫描样本库，利用每个应用程序中出现的权限频繁项构造权限FP-Tree。创建树的根节点NULL。处理每个事务时，依据L中的顺序将出现的权限频繁项添加到权限FP-Tree中的一个分支。

① 扫描001.apk，按照L中的顺序，构造权限FP-Tree的第一个树支<(INTERNET:1)( READ_PHONE_STATE:1)>；

② 扫描002.apk，按照L中的顺序排序，与第一个树支共享节点(INTERNET)，将树节点(INTERNET)计数加1，并创建第二个树支：<(SEND_SMS:1), (ACCESS_NETWORK_STATE:1), (ACCESS_FINE_LOCATION:1), (RECORD_AUDIO:1)>;

③ 迭代前两步，将数据库中的权限信息都添加到权限FP-Tree中，构造好的FP-Tree如图1所示。

图1　权限FP-Tree

步骤三：挖掘权限频繁项集。从一颗权限FP-Tree中挖掘权限频繁项集，一般是根据L表，自下而上挖掘权限频繁项集。其过程如下：首先从权限FP-Tree中获取条件权限基；第二，利用条件权限基，构建一个权限条件FP-Tree，构造的权限条件FP-Tree采用自下而上的方式；第三，迭代前两步，直到树仅剩一个权限项为止。表2给出了上例当中每一个权限频繁项的所有上方分支。

表2　每个权限频繁项的条件权限基

以(RECORD_AUDIO)权限为例，其条件FP-Tree形成过程如图2所示。由于最小支持度为3，故去掉(ACCESS_FINE_LOCATION) ，(READ_PHONE_ STATE)，从而得出最小支持度为3时，其产生的权限频繁项集为{INTERNET, SEND_SMS, ACCESS_NET- WORK_STATE, RECORD_AUDIO }， {INTERNET, SEND_SMS, RECORD_AUDIO }，{ SEND_SMS, ACCESS_NETWORK_STATE, RECORD_AUDIO }，{INTERNET, ACCESS_NETWORK_STATE, RE-CORD_AUDIO }，{INTERNET, RECORD_AUDIO }，{ SEND_SMS, RECORD_AUDIO }，{ ACCESS _NETWORK_STATE, RECORD_AUDIO }。

图2　条件FP-Tree形成过程

同理，按照上述方法，获得最小支持度为3时其他权限的频繁项集，如表3所示。比较所有频繁项集，获得其最大频繁项集，最后将超过最大支持度的权限{WAKE_LOCK}加入其中，则此组应用的最大频繁项集为{WAKE_LOCK, INTERNET,SEND_SMS, RECORD_AUDIO, ACCESS_NETWORK_STATE}。

表3　其他权限频繁项产生的频繁项集

2.3　算法分析

最小支持度阈值和最大支持度阈值是关系算法最终检测率和准确率的关键要素。在实验中不断调整两种阈值，给每一类恶意应用程序测算不同的阈值，是算法的关键。本文提出的最大支持度阈值的定义，可以大大降低在算法复杂度和数据维度，提高挖掘权限频繁项集的效率。

算法1DroidFP-Growth算法

输入： 样本库DB、最小支持度min_sup，最大支持度max_sup。

输出： 最大权限频繁项集Tmax。

方法：

构造权限FP-Tree

1) for(i=1;i≤n;i++){//将n个应用程序全部扫描

//一遍；

2)Ti=extract(DBi)//提取应用程序的权限信息；

3)Lk(p|P)=permissions(Di,min_sup，max_sup)}//根据最

//小支持度和最大支持度构建频繁项集列表Lk，其中p是第一

//个元素，P是频繁项表中去除p后剩余元素组成的项表；

4) returnLk(p|P)

5)Tree=(NULL,P) //创建根节点NULL；

6) for(i=1;i≤n;i++){//第二次扫描数据库；

7)insert_tree([p|P],Tree)//根据频繁项集列表更新权限FP-Tree；

8) return Tree

从FP-Tree中提取最大频繁项集；

9) ifK=1 //只包含单一分支；

10) returnTmax=p∪P

11) else

12) for(p=1;p≤k;p++){//遍历频繁项表中的每一个元

//素，直到Pk=∅；

13)Treek=(pk,Pk)//根据条件权限基构造条件FP-Tree；

14) returnTk=pk∪Pk}

15) returnTmax=max(T1,T2,…,Tk)//选取最大权限频繁

//项集；

16) end if

//挖掘结束，获得最大频繁项集。

3　实验与结果

本文设计了多个实验来验证基于权限频繁模式挖掘算法进行Android 应用恶意代码检测的有效性和正确性，对比其他Android 恶意应用检测方法，实验结果证明了本文提出的检测方法效果更优。

3.1　实验样本

本文使用的恶意应用样本来自于安卓基因组计划[12]，此恶意应用样本库共包含1 260个恶意应用样本，其内包含49个恶意应用家族，此经典恶意应用样本库被其他研究者广泛使用于恶意应用检测。

使用的测试样本包含1 000个不同类别的应用，包括常用的软件集合，如社交软件、游戏软件、读书软件、办公软件等，500个为恶意应用，500个为正常应用。其中正常应用从Google Play下载，包含各种类别的Android应用，保证了其广泛性和通用性。同时为了保证测试样本的准确性，使用各种杀毒软件、恶意应用检测工具进行过滤；恶意应用测试样本从恶意样本分享网站https://virusshare.com/下载收集。

3.2　实验结果及分析

在检测结果分析中，通常有四个指标衡量检测结果的好坏：真阳性TP，表示恶意应用检测准确个数；假阳性FP，表示良性应用检测错误个数；真阴性TN，表示良性应用检测准确个数；假阴性FN，表示恶意应用检测错误个数。检测率代表所有恶意样本中正确分类为恶意应用的比例，其公式表达为：

(1)

误报率为代表所有正常样本中错误分类为恶意应用的比例，其公式表达为：

(2)

分类精度即为准确率，其公式表达为：

(3)

本文使用DroidFP-Growth算法进行权限特征库的建立。同一家族的恶意应用其恶意行为类似，认为其所申请的权限也类似，按恶意应用家族进行权限频繁项集的提取，对最终的未知应用检测效果更好。其检测方法架构如图3所示。

图3　恶意应用检测方法框架

首先，使用AAPT工具提取样本库的应用权限信息，建立权限样本库DB；然后，使用python语言编写DroidFP-Growth算法，按应用家族挖掘最大频繁项集，构建权限关系特征库；最后，对未知应用检测，判断是否恶意。

使用不同的检测方法对经典恶意样本库进行检测，其中Kirin方法[5]只能检测出37个，TPR为2.93%；Androguard方法[13]检测出851个恶意应用，TPR为67.53%；使用同属数据挖掘技术的PApriori方法[10]检测出1 003个恶意应用，TPR为79.60%，而使用本方法进行检测，最终可以检测出1 052个恶意应用，TPR达到83.49%。其结果对比如图4所示，由于篇幅原因，图中只列举了样本集中部分恶意应用数量较多家族。

图4　实验结果对比

将测试样本分为10组，每组含50个良性应用和50个恶意应用，随机抽选5组样本使用本文提出的方法进行检测，其检测结果如表4所示。

表4　测试样本集检测结果

由表4可知，本方法检测率为82.8%，准确率达到85.2%。相比于同类基于权限特征的检测方法，有很大的提高。另外本方法的算法速度优于其他同类方法，尤其是在挖掘较大样本集时，只需要遍历两次数据集即可获得频繁项集，更加有效和准确。

4　结　语

针对Android手机应用程序存在的安全问题，本文提出一种基于权限特征的Android应用静态检测方法。方法利用数据挖掘技术，对Android系统特有的权限特征进行频繁项集挖掘，获得权限频繁项集，以此来对应用进行检测。针对挖掘频繁项集时速度慢，准确率低的问题，提出DroidFP-Growth算法。实验结果表明，方法的检测率可达82.8%，准确率达到85.2%，相比其他方法都有进一步的提升。本文主要针对静态检测特征中的权限特征进行提取，下一步研究其他特征的检测方法，包括API、函数调用、系统调用等特征，同时将动态检测与静态检测相结合，形成全面的检测系统。

[1] Gartner Says Worldwide Sales of Smartphones Grew 7 Percent in the Fourth Quarter of 2016 [EB/OL]. http://www.gartner.com/newsroom/id/3609817.

[2] THREAT REPORT 2015 [EB/OL]. https://www.f-secure.com/documents/996508/1030743/Threat_Report_2015.pdf.

[3] 2016年中国手机安全状况报告[EB/OL]. http://zt.360.cn/1101061855.php?dtid=1101061451&did=490260073.

[4] Wei X,Gomez L,Neamtiu I,et al.Permission evolution in the android ecosystem[C]// Proceedings of the 28th Annual Computer Security Applications Conference. ACM, 2012:31-40.

[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. ACM, 2009:235-245.

[6] Zhao X,Fang J,Wang X. Android malware detection based on permissions[C]//International Conference on Information and Communications Technologies. IET, 2014:1-5.

[7] Felt A P,Chin E,Hanna S,et al.Android permissions demystified[C]// Proceedings of the 18th ACM conference on Computer and communications security.ACM, 2011: 627-638.

[8] Munoz A,Martin I,Guzman A,et al. Android malware detection from Google Play meta-data: Selection of important features[C]// Communications and Network ecurity (CNS), 2015 IEEE Conference on. IEEE, 2015:701-702.

[9] Elish K O,Shu X,Yao D,et al.Profiling user-trigger dependence for Android malware detection[J]. Computers & Security,2015,49(3):255-273.

[10] 杨欢. 协议漏洞挖掘及Android平台恶意应用检测技术研究[D]. 西安：西安电子科技大学, 2014.

[11] Han J, Jian P, Yin Y, et al. Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach[J]. Data Mining and Knowledge Discovery, 2004, 8(1):53-87.

[12] Zhou Y, Jiang X. Dissecting Android Malware: Characterization and Evolution[C]//Security and Privacy. IEEE, 2012:95-109.

[13] Androguard[OL].2016.https://github.com/androguard/androguard.