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).