一種基于權限特征的Android惡意應用檢測方法

王家琰　徐開勇　戴樂育

(解放軍信息工程大學　河南 鄭州 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.