Maldetect：基于Dalvik指令抽象的Android恶意代码检测系统

陈铁明 杨益敏 陈 波

(浙江工业大学计算机科学与技术学院 杭州 310023) (tmchen@zjut.edu.cn)



Maldetect：基于Dalvik指令抽象的Android恶意代码检测系统

陈铁明 杨益敏 陈 波

(浙江工业大学计算机科学与技术学院 杭州 310023) (tmchen@zjut.edu.cn)

提出了一个Android恶意代码的静态检测系统Maldetect，首先采用逆向工程将DEX文件转化为Dalvik指令并对其进行简化抽象，再将抽象后的指令序列进行N-Gram编码作为样本训练，最后利用机器学习算法创建分类检测模型，并通过对分类算法与N-Gram序列的组合分析，提出了基于3-Gram和随机森林的优选检测方法.通过4 000个Android恶意应用样本与专业反毒软件进行的检测对比实验，表明Maldetect可更有效地进行Android恶意代码检测与分类，且获得较高的检测率.

恶意代码；安卓；Dalvik指令；N-Gram；机器学习

随着移动互联网的发展，移动智能终端越来越普及，移动应用的种类与数量都呈现高速增长，智能手机已经成为网民最常用的上网工具.来自Gartner统计数据显示，2015年第4季度全球智能手机的销售量为4亿多台，其中Android系统占据了80.7%[1].截止2016年2月1日，仅Android官方应用市场Google Play上的应用数量就接近200万[2].同时，Android应用安全也面临着两大威胁：应用漏洞和恶意应用.Android应用开发者往往缺少代码审计的能力和代码安全规范检查的习惯，容易在软件生命周期的各个阶段中产生安全漏洞，一旦被攻击者所利用会对软件的完整性、机密性和可用性造成损害[3].Android恶意应用通常是在一些热门的Android应用中插入一段攻击代码，并在安全管理较差的第三方应用商店进行发布与传播[4].根据阿里聚安全发布的2015移动安全病毒年报，18%的Android 设备感染过病毒，95%的热门移动应用存在仿冒应用，恶意应用类型呈现越来越多的趋势[5].常见手机恶意应用的恶意行为包括恶意扣费、信息窃取、短信劫持等，可严重损害手机用户的利益，危害不容忽视.

主流的Android恶意代码检测方法主要有基于特征代码和基于行为的检测.基于特征代码的检测方法通过检测文件是否拥有已知恶意软件的特征代码来判断其是否为恶意软件，具有快速、准确率高等特点，但无法检测未知的恶意代码，且通常需要维护病毒特征数据库.国外著名的Android恶意代码检测工具Androguard[6]就是基于特征代码实现的.

基于行为的检测方法则通过程序的行为与已知恶意行为模式进行匹配，判断目标文件是否包含恶意代码.误报率虽然并不理想，但可实现对未知恶意代码或病毒的检测，可弥补基于特征代码检测的不足.基于行为的分析又可进一步分为动态和静态2种分析方法[7].动态分析方法是指利用“沙盒或虚拟机”来模拟运行程序，通过拦截或监控的方式分析程序运行时的行为特征，一定程度上可绕过代码混淆等代码保护机制，但是计算资源和时间消耗较大，且代码覆盖率低.相对于重量级的动态分析，静态分析则相对属于轻量级的方法，通常是通过逆向工程抽取程序的特征，分析函数调用、程序指令等序列，具有快速高效、代码覆盖率高等特点.

目前，大部分的静态分析方法主要从Android-Manifes.xml文件、lib库文件(.so文件)、Java源文件(通过反编译APK文件获得)等进行特征的提取与分析，而针对Dalvik指令序列的特征研究相对较少，而本文则基于Dalvik指令序列的抽象模型再结合机器学习方法进行研究.本文的主要贡献为：

1) 简化Dalvik指令集，用指令符号抽象一类指令的操作码，并提出了一种基于N-Gram序列的特征模型；

2) 针对抽象的Dalvik指令符号的N-Gram序列特征，结合机器学习分类算法，有效实现了Android恶意代码的检测与分类，与常见反病毒软件相比较，获得较高的检测率.

1 相关工作

针对PC平台的恶意代码检测技术已相对成熟，其中利用N-Gram提取特征的方法也获得了较好的应用效果.例如，文献[8]提出利用OpCode N-Gram代替ByteCode N-Gram，有更高的精度，并对x86平台下的汇编指令进行了实验的验证.文献[9]使用了一种OpCode序列频率的表达式来检测和分类恶意代码，并结合了数据挖掘等方法，也有较高的检测率.

Android代码静态分析方法基本都从Android-Manifes.xml文件、lib库文件(.so文件)、反编译得到的Java源文件中进行特征的提取与分析.例如，文献[10]通过反编译APK得到Java源代码，再从Java源码提取调用方法名作为特征，并结合N-Gram等方法进行恶意软件分类，但该方法没有对混淆过的Java源代码进行处理；文献[11]设计了一种轻量级的Android恶意代码检测方法，将申请的权限、可疑的API函数调用和网络地址等作为静态分析的特征，通过5 560个恶意样本和123 453个正常样本的实验分析，表明有较高的准确率，但是该方法特征的提取依赖于反汇编后的Java源码，混淆过的Java源码会导致该方法失效；文献[12]提出了一种适合恶意代码分析的简化Dalvik中间语言(SDIL)，并结合MOSS算法进行了实验测试，验证了分析方法的有效性，但该方法在代码分析、特征提取时还需加入大量的人工操作，且提取的特征数量与涵盖的恶意代码种类较少.

综上所述，为了提高检测性能，本文首先研究Android的Dalvik指令抽象与简化，提取Dalvik指令的操作码，再借鉴OpCode N-Gram方法提取抽象指令符的序列特征，最后实现针对Android的一种快速有效的恶意代码静态检测方法.

2 本文方法

2.1 系统模型

本文提出了一种Android恶意代码静态检测系统.该系统可以快速有效地检测Android应用程序，识别恶意应用且能够给出恶意家族的类别信息.

整个系统分为2部分:1)恶意代码检测模型和恶意家族分类模型的训练，如图1所示；2)恶意代码检测模型和恶意家族分类模型的测试，如图2所示:

Fig. 1 The detection and classification model.图1 恶意代码的检测与分类模型训练

Fig. 2 The process of predicting malware.图2 恶意代码的检测与分类过程

首先，需要确定训练恶意代码检测模型的训练集.训练集分为2个子集:1)恶意APK样本集合;2)非恶意样本APK集合.APK文件格式通常都包含一个classes.dex文件，该DEX(Dalvik executable format)文件封装了可被Dalvik虚拟机执行的Dalvik字节码.利用工具Apktool[13]反汇编APK文件，就能得到一个包含smali源码的文件目录，smali目录结构对应着Java源码的src目录.smali是对Dalvik字节码的一种解释，所有语句都遵循一套标准的语法规范.从smali文件中提取出Dalvik操作码并进行抽象简化为指令符号，再针对抽象的Dalvik指令符号的N-Gram序列特征进行统计与归一化处理，最后采用机器学习的分类算法建立恶意代码检测模型.同理，按照恶意家族的类型划分多个训练子集，按照上述类似的处理过程，可建立一个恶意家族分类模型.

利用模型检测与分类时，将待测APK文件先进行预处理步骤，提取出Dalvik指令特征并作同样的抽象简化与N-Gram序列化处理，再通过恶意代码检测模型的检测，就可判断出是否为恶意代码，如果不是就直接给出检测结果，如果是则需要进一步通过恶意家族分类模型来获得该恶意代码家族类型.

2.2 Dalvik指令特征与N-Gram

根据文献[14]表明官方Dalvik指令有230条，分别包括方法调用指令、数据操作指令、返回指令等十几种类型.文献[12]提出了一种适合恶意代码分析的简化Dalvik中间语言(SDIL)，对218种指令简化成了13种，并分别统计了指令的频率.基于Dalvik指令集与上述工作，本文另行设计了一种指令符号方案：在指令集中提取出能够正确反映程序语义的指令和操作码，对功能相近的指令进行归类，并将该类的指令集合抽象为指令符号.与原有的Dalvik的指令集相比，更加简化精要，且便于后续的分析与特征提取.表1中给出了最终的设计方案，在Dalvik指令集中提取出的107种代表性指令并分成10大功能相近的类，并且每类指令抽象为一个特定的指令符号，后续N-Gram编码将直接使用这种指令符号代替完整的Dalvik指令.

N-Gram算法经常用于自然语言处理领域，但是它也经常用来处理恶意代码的分析.对Dalvik指令符号进行N-Gram编码，同样可以用于分析Android的恶意代码.N-Gram算法假设第m个词的出现只是与前面的m-1个词相关，现假设有Dalvik指令符号序列为{M,R,G,I,T,P,V}，3-Gram编码后提取的特征为[{M,R,G}，{R,G,I}，{G,I,T}，{I,T,P}，{T,P,V}].表2中给出了当3-Gram编码时一个APK应用中包含的1 000种不同N-Gram特征的频率统计.

Table 1 Symbolic Instruction Set Definition

Table 2 Illustration for the Frequency Statistics of 3-Gram Features

2.3 机器学习方法及评估标准

分类算法是一种典型的机器学习方法.文献[15]介绍了最常见的衡量分类算法性能的评估参数.度量分类算法的有效性最基本的4个指标是：1)真阳性(true positive,TP)，表示正确分类为恶意软件的恶意样本个数；2)假阳性(false positive，FP)，表示错误分类为恶意软件的良性样本个数；3)真阴性(true negative，TN)，表示正确分类为良性软件的良性样本个数；4)假阴性(false negative，FN)，表示错误分类为良性软件的恶意样本个数.由这4个指标可以构成如表3所示的混淆矩阵，用于分析分类算法的优劣性.

Table 3 Confusion Matrix

由上述的基本指标可以构成下面的一些常用指标：

真阳性率(TPR)亦即检测率(detection rate)，有时也称为召回率(recall rate)；假阳性率(FPR)亦即误报率(false alarm rate)；正确率Precision指在真正的恶意样本在分类为恶意样本的比例；分类精度Accuracy是所有正确分类的样本与所有样本之比；F-Measure指准确率与召回率的调和平均值.ROC曲线(接收者运行特征)是一种显示分类算法的TPR和FPR之间折中的图形化方法.AUC(area under the curve)是ROC曲线下方的面积，如果完全准确的模型，面积为1.

3 实验与分析

3.1 实验数据与实验环境

测试所采用的恶意样本来源于德国哥廷根大学Drebin项目的恶意样本数据库[16]，正常的样本通过安卓官方的Google Play应用商店[17]随机下载获得.文献[18]指出在Google Play应用商店中52 208个安卓应用中只有2个为恶意的，所以基本可以认为Google Play应用商店中的安卓应用均为非恶意应用.

本文利用机器学习工具Weka(Waikato envir-onment for knowledge analysis)对实验数据得到的特征用机器学习算法训练分类模型.Weka是一款免费的基于JAVA环境下开源的机器学习软件，集成了大量的机器学习算法，且具有高效准确的特点，所以本文使用它作为机器学习的工具.

3.2 分类算法与N-Gram序列的优选

本节先采用270个恶意样本和330正常样本作为实验样本集，根据2-Gram，3-Gram，4-Gram编码分别提取了不同长度的Dalvik指令符号序列，然后再分别使用4种分类算法包括随机森林算法(Random Forest)、支持向量机算法(SVM)、K-最近邻算法(KNN)、朴素贝叶斯算法(Naive Bayes)对3种编码的序列采用10折交叉验证进行测试，结果如表4～6所示.

Table 4 The Detection Results Based on 2-Gram Sequences

Table 5 The Detection Results Based on 3-Gram Sequences

Table 6 The Detection Results Based on 4-Gram Sequences

选用AUC，TPR，FPR，Precision，Recall，F-Measure等指标作为实验的评估标准.其中,AUC是最重要的标准，它可以正确地反映TPR和FPR之间的关系，AUC值越高代表检测的综合表现越优.FPR也是一项重要的指标，FPR值越低代表误报率越低.在表4中，随机森林算法的AUC值最高，FPR值最低，而TPR值略不如KNN算法.在表5中，随机森林算法的各项指标都表项最优.在表6中，随机森林算法的AUC值最高，KNN算法的FPR值最理想，但是随机森林算法的FPR值与KNN算法的FPR值差距很小.综合分析，在2-Gram，3-Gram，4-Gram指令符号序列中，随机森林算法的表项是最优的.

以随机森林算法为基础进一步寻找最优的N-Gram序列.综合比较表4～6，不难发现，随机森林算法AUC值按从优到劣的顺序为：4-Gram，3-Gram，2-Gram；随机森林算法FPR值按从优到劣的顺序为：3-Gram，4-Gram，2-Gram；2-Gram序列表现都是最劣的，可以不再考虑.4-Gram序列的随机森林算法AUC值比3-Gram序列的随机森林算法AUC值仅高出了2%，而4-Gram序列的随机森林算法FPR值比3-Gram序列的随机森林算法FPR值却高出了30%.综合分析，3-Gram序列的随机森林算法是一种较优的方法.

接下来，分析样本数量对准确性的影响.除了上述实验的600个样本作为小样本集合，再增加一个1 100个样本作为大样本集合作为对比实验，按3-Gram的随机森林算法，采用10折交叉验证对它们进行测试.实验结果如表7和图3所示，不难看出，大样本集的所有评估指标都要优于小样本集，这表明样本数量大小对检测效果有一定的影响，训练样本数量越大则综合表现越优.

Table 7 The Results with Different Size of Samples

Fig. 3 ROC curves with different size of samples.图3 不同样本数量的ROC曲线对比图

3.3 MaldetectVS专业反病毒软件

根据3.2节的实验结果，以实验效果较优的3-Gram序列的随机森林算法作为基础，通过计算信息增益来选取200个区分度最高的特征作为特征选择方法，我们实现了一个Android恶意代码检测系统Maldetect.本节实验我们分别在2 000个样本和4 000个样本的2个数据集上进行实验，并按照60%数据作为Maldetect的训练样本库，40%数据作为测试样本库.作为实验对照，我们也将测试样本发送到ThreatBook多引擎文件检测服务[19]然后得到了9款常见的反病毒软件(Avira,Dr.Web,AVG,Kaspersky,ESET,GDATA,Rising,MSE,Avast)的检测结果，最后统计出各系统的检测率与误报率.

根据表8显示的本次实验结果，我们发现大部分的反病毒软件的检测率都超过了90%，但是也存在一些检测率甚至低于50%的反病毒软件，可能这些反病毒软件并不适用于安卓平台的检测.在2 000个样本数据集上，Maldetect以95.3%的检测率在10款反病毒软件中排第3；在4 000个样本数据集，Maldetect以98.6 %的检测率在10款反病毒软件中排第2.这表明随着样本训练样本数量增加，Maldetect的精确度呈上升趋势.另外，实验所用的恶意样本已经公开了一段时间，大多数反病毒软件的特征库已经加入了这些恶意样本的特征，在检测未公开的恶意样本时，Maldetect的机器学习方式则更加能体现优势.

专业的反病毒软件的误报率基本在0%～1%之间，Maldetect的误报率比它们要稍微高一点.另外，表9也表明随着训练样本数量的增加，Maldetect的误报率呈较明显的下降趋势.

Table 8 Detection Rates of Maldetect and Antivirus Scanners

Table 9 False Positive Rates of Maldetect and Antivirus Scanners

3.4 恶意家族分类实验

除了检测恶意代码，另一个重要方面，我们需要分类恶意家族并进行性能评估.本节实验我们精选样本数量最多、最常见的9个恶意家族共计900个样本作为实验样本，其中60%数据作为训练集，40%数据作为测试集.用Maldetect进行实验测试，结果如表10所示.从表10可知，9类恶意家族的AUC值都不低于0.97，FPR值都不高于0.037，该方法对恶意家族分类有较好的效果，也完全适用于恶意家族的分类.

Table 10 The Results on Classification of Malware Family Using Maldetect

4 总 结

本文提出了一种Android静态检测方法，采用逆向工程将DEX文件转化为Dalvik指令并对其进行简化抽象，再将抽象后的指令序列进行N-Gram编码作为样本训练，通过机器学习的分类算法来创建分类检测模型.在实验环节，对不同分类算法与N-Gram序列分别进行了比较，提出了基于3-Gram和随机森林的优选检测方法.最后，采用2 000个样本与4 000个样本2组样本集，与专业的反毒软件进行对比实验，实验结果表明该方法可有效地进行Android恶意代码检测与分类，且获得较高的检测率.下一步工作将研究在提高训练样本数量的情况下，用聚类的方法选择出典型样本，去除噪声数据，进一步提高准确率、降低误报率.

[1]Egham. Gartner Says Worldwide Smartphone Sales Grew 9.7 Percent in Fourth Quarter of 2015[EB/OL]. (2016-02-18) [2016-04-01]. http://www.gartner.com/newsroom/id/3215217

[2]AppBrain. Android Statistics: Google Play Stats[EB/OL]. (2016-02-01) [2016-03-01]. http://www.appbrain.com/stats

[3]Zhang Yuqing, Fang Zhejun, Wang Kai, et al. Survey of Android vulnerability detection[J]. Journal of Computer Research and Development, 2015, 52(10): 2167-2177 (in Chinese)(张玉清, 方喆君, 王凯, 等. Android安全漏洞挖掘技术综述[J]. 计算机研究与发展, 2015, 52(10): 2167-2177)

[4]Zhang Yuqing, Wang Kai, Yang Huan, et al. Survey of Android OS security[J]. Journal of Computer Research and Development, 2014, 51(7): 1385-1396 (in Chinese)(张玉清, 王凯, 杨欢, 等. Android安全综述[J]. 计算机研究与发展, 2014, 51(7): 1385-1396)

[5]Alibaba. 2015 Security Report[EB/OL]. 2016[2016-03-01]. http://jaq.alibaba.com (in Chinese)(阿里巴巴. 2015年安全报告[EB/OL]. 2016[2016-03-01]. http://jaq.alibaba.com)

[6]Androguard Team. Androguard[EB/OL]. [2016-03-01]. http://code.google.com/p/androguard

[7]Qing Sihan. Research progress on Android security[J]. Journal of Software, 2016, 27(1): 45-71 (in Chinese)(卿斯汉. Android安全研究进展[J]. 软件学报, 2016, 27(1): 45-71)

[8]Shabtai A, Moskovitch R, Feher C, et al. Detecting unknown malicious code by applying classification techniques on opcode patterns[J]. Security Informatics, 2012, 1(1): 1-22

[9]Santos I, Brezo F, Ugarte-Pedrero X, et al. Opcode sequences as representation of executables for data-mining-based unknown malware detection[J]. Information Sciences, 2013, 231(9): 64-82

[10]Dhaya R, Poongodi M. Source code analysis for software vulnerabilities in Android based mobile devices[J]. International Journal of Computer Applications, 2014, 93(17): 10-14

[11]Arp D, Spreitzenbarth M, Hubner M, et al. DREBIN: Effective and explainable detection of Android malware in your pocket[C] //Proc of the 21st Annual Network and Distributed System Security Symposium. San Diego, California: Internet Society, 2014

[12]Dong Hang, He Nengqiang, Hu Ge, et al. Malware detection method of Android application based on simplification instructions[J]. Journal of China Universities of Posts & Telecommunications, 2014, 21(Suppl 1): 94-100

[13]GitHub. Apktool: A tool for reverse engineering Android apk files[EB/OL]. [2016-03-01]. https://github.com/iBotPeaches/Apktool

[14]Paller G. Dalvik opcodes[EB/OL]. [2016-03-01]. http://pallergabor.uw.hu/androidblog/dalvik_opcodes.html

[15]HAN J. Data Mining[M]. San Francisco: Morgan Kaufmann, 2011

[16]Arp D, Spreitzenbarth M, Hubner M, et al. The Drebin Dataset[EB/OL]. [2016-03-01]. https://www.sec.cs.tu-bs.de/～danarp/drebin/index.html

[17]Google Inc. GooglePlay [EB/OL]. [2016-03-01]. https://play.google.com

[18]Grace M, Zhou Y, Zhang Q, et al. RiskRanker: Scalable and accurate zero-day Android malware detection[C] //Proc of the 10th Int Conf on Mobile Systems, Applications, and Services. New York: ACM, 2012: 281-294

[19]ThreatBook Inc. VirusBook [EB/OL]. [2016-03-01]. https://x.threatbook.cn/

Chen Tieming, born in 1978. PhD. Professor in the Zhejiang University of Technology. His main research interests include network and information security.

Yang Yimin, born in 1985. Master candidate in the Zhejiang University of Technology. His main research interests include network and information security.

Chen Bo, born in 1971. Associate professor in the Zhejiang University of Technology. His main research interests include network and information security.

Maldetect: An Android Malware Detection System Based on Abstraction of Dalvik Instructions

Chen Tieming, Yang Yimin, and Chen Bo

(CollegeofComputerScienceandTechnology,ZhejiangUniversityofTechnology,Hangzhou, 310023)

A novel static Android malware detection system Maldetect is proposed in this paper. At first, the Dalvik instructions decompiled from Android DEX files are simplified and abstracted into simpler symbolic sequences. N-Gram is then employed to extract the features from the simplified Dalvik instruction sequences, and the detection and classification model is finally built using machine learning algorithms. By comparing different classification algorithms and N-Gram sequences, 3-Gram sequences with the random forest algorithm is identified as an optimal solution for the malware detection and classification. The performance of our method is compared against the professional anti-virus tools using 4 000 malware samples, and the results show that Maldetect is more effective for Android malware detection with high detection accuracy.

malware; Android; Dalvik instruction; N-Gram; machine learning

2016-05-18；

2016-08-12

国家自然科学基金项目(U1509214)；浙江省自然科学基金项目(LY16F020035)

TP309

This work was supported by the National Natural Science Foundation of China (U1509214) and the Natural Science Foundation of Zhejiang Province of China (LY16F020035).