基于API频繁模式挖掘算法的Android恶意应用检测方法

梁俊鹏

(成都信息工程大学信息安全工程学院， 四川　成都　610225)



基于API频繁模式挖掘算法的Android恶意应用检测方法

梁俊鹏

(成都信息工程大学信息安全工程学院， 四川成都610225)

文章提出一种基于API频繁模式挖掘算法的Android恶意应用检测方法，通过挖掘API调用之间的关联，发现恶意软件中具有的频繁模式，采用一定去冗余操作提高检测的准确率检测未知的Android软件,并通过实验验证方法的可行性和有效性.结果显示，该方法对检测未知的Android软件可以达到83﹪的检测准确率，具有一定实用价值，可为进一步研究提供参考.

Android;恶意软件;静态检测;机器学习

市场调研机构高德纳咨询公司发布的最新报告显示，在2015年第二季度的统计中，全球智能手机中82.2﹪采用Android系统产品，占据智能手机市场的主导地位，远超iOS、Windows、BlackBerry等操作系统[1].由于Android系统具有较高的开放性，运行该系统的智能手机越来越多地成为恶意攻击者和恶意软件的攻击目标，出现了大量基于Android系统开发的软件，其中也包含了大量恶意程序.这些恶意软件对用户的信息安全构成了严重威胁，包括隐私泄漏、财产损失、商业机密泄露等.大量普通用户由于缺乏基本的信息安全意识，软件程序的来源渠道不正规等，导致恶意软件快速传播，造成较大危害.根据360公司发布的最新消息，2015年第三季度，360互联网安全中心共截获Android平台新增恶意程序样本558万个，平均每天截获新增手机恶意程序样本近6.07万个，累计监测到移动端用户感染恶意程序7 722万人次，平均每天恶意程序感染量达到83.9万人次.新增恶意程序主要是资费或流量消耗，占53.1﹪；其次为恶意扣费(41.5﹪)和隐私窃取(3.6﹪).这三类恶意程序占总量的98.3﹪，其余类型的恶意程序新增量只占1.7﹪.

不同于别的移动操作系统平台，Android系统允许安装来自未受认证的软件源的应用安装包，如第三方市场、论坛等.随着Android市场份额的急剧扩张，目前网络上有大量为Android系统提供软件下载服务的网站，此类网站每天都会收到大量的软件开发者提交的发布软件的申请，并对这些软件进行审核后提供给公众下载.由于发布申请的数量非常庞大，多数网站无法做到对每一个软件进行详细审查和安全检测，导致部分具有恶意代码的软件被公开发布出来，继而被用户下载.这一过程对网站的信誉和用户的信息安全都造成了损失.

1　相关工作

为应对Android平台上的恶意软件，国内外研究人员进行了一系列研究[2-5].目前，移动平台的恶意代码检测技术主要分为2种：静态检测和动态检测.静态检测多为基于特征码，如哈希值、指令序列等检测方法，大部分安全软件都采用这种检测方法，基于已有的特征库进行检测，误报率较低，但也导致对未知恶意应用的防范较为乏力，具有一定的滞后性.动态检测为软件运行时收集其产生的行为信息，包括API调用、系统调用、内存存取、电源消耗等信息，结合已有的异常特征判定是否为恶意软件，但需要较长的时间来收集动态数据，比静态分析更复杂.文献[6]提出一种基于权限频繁模式挖掘算法的Android恶意应用检测方法，需要对已知的恶意软件家族进行静态分析和权限特征提取，对最新的恶意应用样本检测率较低，仅为50﹪.文献[7]提出一种基于机器学习的Android恶意软件检测模型，训练静态指纹匹配库和动态行为签名库，能在一定程度上检测未知恶意程序，但训练数据量太少，样本说服力不够.文献[8]提出一种基于改进贝叶斯分类的Android恶意软件检测方法，利用移动设备应用程序获取多种行为特征值，应用机器学习技术检测Android恶意软件.该方法只选取了短信、GPS、拨打电话等6种行为特征集合，不能较完整地表现恶意软件的行为，有较大片面性，而且恶意与非恶意的判别标准不完善，还有改进的空间.文献[9]提出一种利用APK文件解压得到classes.dex可执行文件中类与函数名信息，利用机器学习进行分类的方法.

以上基于权限方面的研究存在对过度申请权限造成的干扰处理不到位的问题.为了解决原始权限存在过度申请造成的干扰，本文使用基于关联权限特征的静态分析方法，结合Apriori挖掘算法挖掘恶意行为涉及的关联API特征，然后进行特征的去冗余等计算，选择出最适合进行恶意软件检测的特征集.在Android系统上，一个应用程序需要实现某项功能，比如获取敏感信息、系统资源、使用和修改设备状态等，需要通过调用系统提供的API来完成，不同的代码范围和API使用层级反映了对应模块的代码功能，能够推测出模块在运行过程中可能具有的行为属性和表现形式.由于完成一项恶意行为通常需要多个API的结合使用才能实现，所以我们需要对API使用情况的关联性进行挖掘分析.然而，由于部分在恶意软件中出现的关联组合也会出现在正常程序中，所以需要对此类关联组合进行判断，以提取出最能反映恶意软件和正常软件区别的关联组合.以往的研究多数基于权限相关性特征，由于目前国内的Android应用程序存在权限申请过度的情况，本文基于API的静态分析方法，结合Apriori频繁项集挖掘算法[10]挖掘恶意软件中包含的API频繁项集特征，然后进行特征的去冗余操作，选择出适应于恶意软件检测的特征集，最后基于生成的特征数据库对未知的恶意软件进行检测.

2　基于API频繁模式的挖掘算法

2.1特征提取及预处理

为了便于后续算法的运行，在此对Android应用程序样本进行特征提取及预处理操作，如图1所示.

图1　特征提取及预处理流程

步骤1确定需要提取的敏感API，并形成敏感API数据库，便于后续使用.敏感API来源于对已知恶意软件分析的经验，以及对已知恶意软件和已知正常软件API统计的差异.最终选定了可以用来完成发送短信、删除短信、拨打电话、删除通话记录、修改联系人、执行shell脚本等功能的API；

步骤2利用Apktool对Android应用程序样本进行反编译；

步骤3对上一步反编译得到的smali文件夹中的smali文件进行扫描，查找其中存在的敏感API；

步骤4统计该应用程序使用的API的序号，形成该应用程序的API调用序列，并写入数据库保存.

2.2算法描述

频繁模式是频繁地出现在数据集中的模式，如项集、子序列、子结构等[10].Apriori算法是Agrawal和Srikant R于1994年提出的，为布尔关联规则挖掘频繁项集的原创性算法.频繁模式挖掘搜索给定数据集中反复出现的联系，以发现恶意软件API使用情况的关联性.

2.2.1Apriori算法挖掘关联特征

本文采用一个改进的基于规则挖掘的Apriori算法来进行特征选择和自动筛选，从而进行有效样本分类.为了解决对高频率事件的有效性挖掘，减少对数据库的扫描次数和候选数据集的数量，在经典的Apriori算法基础上提出一个改进的Apriori算法.Apriori算法的基本思想是用迭代的方法产生频繁集，为产生可以满足最小置信度规则的规则集和输出.本文中用到的Apriori算法是建立在Android权限这一相关概念的基础之上的.Apriori算法就是为了挖掘权限频繁项集，挖掘Android应用采用的API之间的关联性，以构建API关联特征库.

本文通过预处理分别得到正常软件和恶意软件的API数据库.每一个Android软件均可以映射为一个包含所有敏感API调用的事务，每个API为一个项，API项的集合为项集，最小支持度为min_support，从2个数据库中分别发现满足最小支持度的频繁项集，并建立特征库.

Apriori算法有两个主要步骤：连接和剪枝.这也是产生频繁项集的两个步骤.

连接：如果一个项集不是频繁集，那么它的超集也一定不是频繁项集.

剪枝：如果一个项集是频繁集，那么它的真子集一定是频繁项集.

输入：

Di： 所选择样本的集合

min_support：最小支持度阈值

输出：

频繁API项集数据库Dataset

伪代码描述：

//找出所有频繁1项集

L1=find_frequent_1_itemsets(D);

For(k=2;Lk-1!=null;k++){

//产生候选，并剪枝

Ck=apriori_gen(Lk-1);

//扫描D进行候选计数

For each事务t∈D{

//得到t的子集

Ct= subset(Ck,t);

For each候选c∈Ct

c.count++;

}

Lk={c∈Ck| c.count>=min_sup}

}

return L=所有的频繁集

2.2.2检测特征库生成步骤

步骤1API频繁项集挖掘：利用Apriori算法选择合适的最小支持度min_support，分别对正常和恶意两类软件的API调用情况进行频繁项集挖掘，并将结果记录到数据库中.结果形式如下：

item: (68, 212, 390, 1037) , support:0.457

其中，item代表频繁项集，support代表该频繁项集的支持度.

步骤2去冗余：由于根据以往的大量实验发现，比对正常软件和恶意软件的频繁项集，部分频繁项集会同时出现于正常软件和恶意软件，会造成检测准确率大幅度降低，故从恶意软件的频繁项集数据库中删除此类数据.

步骤3计算恶意软件的API调用频繁项集在正常软件中出现的次数，升序排列后，记录到恶意特征库中.

步骤4评分：选取上述恶意特征库的前N项频繁项集，判断是否存在于当前的Android应用程序的API序列中.如果存在，则根据一定的机制对其评分.当评分达到一定的阈值时判为恶意程序.

3　实验与分析

3.1实验样本

从VirusShare和Android应用市场获得15 000个样本，14 200个恶意样本(其中10 000个样本用于训练，其余4 200个样本用于验证本算法的检测效果)和800个正常样本(其中500个样本用于训练，其余300个用于验证检测效果).

图2　检测系统特征库生成及未知样本检测

3.2评估标准

为了便于评估实验结果，定义以下指标：

1)设TP(True Positive)表示正常软件预测准确数量；

2)设FP(False Positive)表示正常软件预测错误数量；

3)设TN(True Negative)表示恶意软件预测准确数量；

4)设FN(False Negative)表示恶意软件预测错误数量；

5)定义所有软件检测准确的比例为：

ACC=(TP+TN)/(TP+TN+FP+FN)

本文依据以上指标对检测结果进行验证和评估.

3.3实验结果

本文选择不同的最小支持度min_support值进行频繁项集挖掘，并对相应的检测效果进行比较，结果如表1所示.

表1　检测结果　/﹪

对比以上结果可以发现，在最小支持度为0.35时，总体检测准确率达到83﹪，此时系统具有较好的检测效果.对于恶意软件的漏报情况，主要出现在部分采用本地代码编写的恶意应用上，较少采用Android 框架层的API.本文检测方法无法正确反映其恶意行为，故导致存在一定的漏报情况.在检测效率方面，对4 200个恶意软件样本和300个正常软件样本进行检测，除去预处理过程只花费了11 min，平均每个样本花费时间为0.15 s.

3.4实验分析

本文基于大量的样本进行挖掘和分析，经过多次实验得出较合理的算法参数值，并据此对未知样本的检测准确率达83﹪.与文献[6]相比，其对90个恶意应用的检测率为50﹪，对新出现的恶意软件的适应性较差.本文是针对未知应用进行检测，且相对其检测准确率有较大提高.文献[7]仅对200个恶意软件样本进行检测，检测准确率最高为76﹪.本文获取了数量更多的样本，结果更可靠，且检测准确率也有一定提高.虽然本方法依然存在误判，但其结果可以作为自动检测手段使用，为后续采用其他检测手段和手动检测提供依据.

4　结语

本文基于机器学习，利用Android平台应用程序所使用的API之间的相关性结合频繁项集挖掘算法，提出一种恶意软件检测的方法，并通过去冗余操作提高了检测准确性.本方法对于检测恶意软件具有一定效果，并可与其他检测手段结合，以提高检测准确率.虽然本方法在对Android恶意软件检测中取得了一定效果，但仍然存在不足，需要在以后研究中收集更多恶意样本并修改算法参数等，以提高检测的准确率和算法运行效率.

[1]Gartner. Worldwide Smartphone Sales to End Users by Operating System in 2015[EB/OL].(2015-08-20)[2015-11-12].https://www.gartner.com/newsroom/id/3115517.

[2]ZHOU Y J, JIANG X X. Dissecting android malware: Characterization and evolution[C]. Security and Privacy (SP), IEEE Symposium on IEEE, 2012.

[3]刘华婷,郭仁祥,姜浩. 关联规则挖掘Apriori算法的研究与改进[J]. 计算机应用与软件,2009(1):146-149.

[4]张锐,杨吉云. 基于权限相关性的Android恶意软件检测[J]. 计算机应用,2014(5):1322-1325.

[5]冯博,戴航,慕德俊. Android恶意软件检测方法研究[J]. 计算机技术与发展,2014(2):149-152.

[6]杨欢,张玉清,胡予濮,等. 基于权限频繁模式挖掘算法的Android恶意应用检测方法[J]. 通信学报,2013(S1):106-115.

[7]蔡泽廷. 基于机器学习的Android恶意软件检测模型研究[D].青岛:青岛理工大学,2013.

[8]张思琪. 基于改进贝叶斯分类的Android恶意软件检测[J]. 无线电通信技术,2014(6):73-76.

[9]童振飞. Android恶意软件静态检测方案的研究[D].南京:南京邮电大学,2012.

[10]MICHELINE K. 数据挖掘概念与技术[M]. 北京：机械工业出版社，2012：157-165.

(责任编辑穆刚)

An android malware detection method based on API frequent pattern mining algorithm

LIANG Junpeng

(College of Information Security Engineering,Chengdu University of Information Technology,Chengdu Sichuan 610225,China)

An android malware detection method based on API frequent pattern mining algorithm was proposed in the paper, in which through the digging the relationship of transferring API, the frequent mode in the malware was detected. Using a certain redundancy removal operation to improve the accuracy of detection, the unknown Android software was detected. The possibility and efficiency of the method was tested by the experimental methods. The results show that the method can reach 83﹪ accuracy, so the method has certain value and provides

for the further study.

Android; malware; static detection; machine learning

2016-01-19

梁俊鹏(1990—)，男，江苏南京人，硕士研究生，主要从事信息安全方面的研究.

TP309.5

A

1673-8004(2016)05-0093-05