王家琰　徐開勇　戴樂育

(解放軍信息工程大學(xué)　河南 鄭州 450000)

0　引　言

知名市場調(diào)研機(jī)構(gòu)Gartner發(fā)布了2016年第四季度全球智能手機(jī)分析報(bào)告[1]，報(bào)告顯示，在2016年第四季度，全球智能手機(jī)的總銷量達(dá)4.32億部。其中，在智能手機(jī)操作系統(tǒng)方面， Android系統(tǒng)市場占有率繼續(xù)領(lǐng)跑，其市場份額達(dá)到了81.7%，相比之下， iOS系統(tǒng)第四季度市場份額為17.9%， 可見Android系統(tǒng)在智能終端領(lǐng)域有著舉足輕重的作用。伴隨著Android市場份額的增長，其安全問題也凸顯出來，97%移動(dòng)惡意應(yīng)用程序開發(fā)者將Android操作系統(tǒng)作為攻擊目標(biāo)[2]?！?016年手機(jī)安全狀況報(bào)告》[3]顯示，2016年全年，360互聯(lián)網(wǎng)安全中心累計(jì)監(jiān)測到Android用戶感染惡意程序2.53億，平均每天惡意程序感染量約達(dá)到70萬人次。綜上，解決Android手機(jī)應(yīng)用程序的安全問題迫在眉睫。

權(quán)限機(jī)制是Android系統(tǒng)安全架構(gòu)中的重要組成部分。Android要求每個(gè)應(yīng)用程序在開發(fā)時(shí)就聲明它需要的權(quán)限以此來訪問其他文件、數(shù)據(jù)和資源，否則，如果缺少必要的權(quán)限，應(yīng)用程序?qū)o法提供預(yù)期的功能與服務(wù)。研究發(fā)現(xiàn)[4]，隨著Android版本的更新，可申請權(quán)限的數(shù)量正在日益增長，但并非提供更加細(xì)粒度的權(quán)限劃分，而是提供更多的訪問功能，使得普通用戶在安裝應(yīng)用程序時(shí)難以理解和有效利用這一安全機(jī)制。

為了解決Android應(yīng)用中存在的安全問題，本文提出一種基于權(quán)限特征的靜態(tài)檢測方法，設(shè)計(jì)了權(quán)限頻繁項(xiàng)集挖掘算法——DroidFP-Growth算法來進(jìn)行惡意應(yīng)用的檢測。首先使用工具提取應(yīng)用程序權(quán)限列表，然后采用DdroidFP-Growth算法挖掘并構(gòu)建權(quán)限特征關(guān)系庫，最后對未知應(yīng)用進(jìn)行檢測。通過實(shí)驗(yàn)證明本方法可以有效檢測惡意應(yīng)用。

1　相關(guān)工作

隨著Android智能終端的普及，惡意應(yīng)用檢測技術(shù)也進(jìn)入快速發(fā)展階段，就目前來看，主流惡意應(yīng)用檢測方法分為兩種：靜態(tài)檢測方法和動(dòng)態(tài)檢測方法。靜態(tài)分析方法通常使用反編譯技術(shù)得到Java源文件或JAR文件，通過檢測權(quán)限、API調(diào)用、系統(tǒng)調(diào)用等特征來判斷其是否為惡意應(yīng)用；動(dòng)態(tài)分析方法通過收集應(yīng)用程序運(yùn)行時(shí)的數(shù)據(jù)來檢測應(yīng)用程序是否有惡意行為。

權(quán)限機(jī)制作為Android系統(tǒng)的重要的安全機(jī)制之一，可以有效地用于檢測惡意應(yīng)用。文獻(xiàn)[4]展望了Android系統(tǒng)權(quán)限機(jī)制的發(fā)展趨勢，發(fā)現(xiàn)第三方市場提供的應(yīng)用程序和開發(fā)商預(yù)裝在Android終端的應(yīng)用程序大多數(shù)存在申請權(quán)限過度的現(xiàn)象，違反了最少權(quán)限原則。文獻(xiàn)[5]研究了危險(xiǎn)權(quán)限組合，提出了幾個(gè)危險(xiǎn)的權(quán)限組合方式用于檢測惡意應(yīng)用。文獻(xiàn)[6]提出了一個(gè)基于權(quán)限的Android平臺(tái)的惡意應(yīng)用檢測方法，使用PCA(主成分分析)算法進(jìn)行權(quán)限提取后的特征選擇，并應(yīng)用SVM(支持向量機(jī))方法將應(yīng)用分為良性或惡意。文獻(xiàn)[7]提出一種基于Web的工具，稱為“Stowaway”，此工具用于檢測權(quán)限申請過度的問題。文獻(xiàn)[8]利用Google Play收集應(yīng)用程序，并利用機(jī)器學(xué)習(xí)的方法來檢測惡意應(yīng)用。文獻(xiàn)[9]利用API調(diào)用特征進(jìn)行檢測，達(dá)到了較高的精度，并且發(fā)現(xiàn)了Google Play中的新的惡意軟件家族。

近年來同樣有利用數(shù)據(jù)挖掘技術(shù)來進(jìn)行惡意應(yīng)用檢測。文獻(xiàn)[10]設(shè)計(jì)了能夠挖掘權(quán)限之間關(guān)聯(lián)性的權(quán)限頻繁模式挖掘算法—PApriori算法，該算法基于Apriori算法構(gòu)造出權(quán)限關(guān)系特征庫來檢測未知的惡意應(yīng)用，實(shí)驗(yàn)證明其結(jié)果具有有效性和正確性，但是算法的效率不高，耗費(fèi)資源和時(shí)間較長。本文改進(jìn)了FP-Growth算法[11]用于頻繁項(xiàng)集的挖掘。FP-Growth算法效率優(yōu)于Apriori算法。FP-Growth算法利用一種稱為頻繁模式樹(FP-tree)的方式的存儲(chǔ)數(shù)據(jù)，可以直接在FP-tree提取頻繁項(xiàng)集。FP-tree可以將所有數(shù)據(jù)存儲(chǔ)于其構(gòu)造的分支當(dāng)中，分支相互重疊越多，獲得頻繁項(xiàng)集越準(zhǔn)確。FP-Growth算法只需要對數(shù)據(jù)庫進(jìn)行兩次掃描，當(dāng)處理更大數(shù)據(jù)集時(shí)，F(xiàn)P-Growth算法在速度和準(zhǔn)確率上要明顯優(yōu)于Apriori算法。

2　權(quán)限頻繁模式挖掘DroidFP-Growth算法

頻繁項(xiàng)集是指頻繁同時(shí)出現(xiàn)的數(shù)據(jù)的集合，關(guān)聯(lián)規(guī)則是指數(shù)據(jù)可能的存在某種關(guān)系。從數(shù)據(jù)集中挖掘數(shù)據(jù)間的關(guān)聯(lián)規(guī)則被稱作關(guān)聯(lián)分析。尋找數(shù)據(jù)的頻繁項(xiàng)集是一項(xiàng)十分耗時(shí)的任務(wù)，所以需要用更加快速的方法挖掘頻繁項(xiàng)集。不同類別Android應(yīng)用程序會(huì)申請不同的權(quán)限，但是有相同惡意行為的應(yīng)用程序會(huì)申請某幾種相同的權(quán)限。我們將這幾種共同的權(quán)限成為權(quán)限頻繁項(xiàng)集，通過挖掘權(quán)限的頻繁項(xiàng)集可以對惡意應(yīng)用進(jìn)行檢測。

本文基于FP-Growth算法，設(shè)計(jì)了權(quán)限頻繁項(xiàng)集挖掘算法DroidFP-Growth，同時(shí)在算法的基礎(chǔ)上，增加了最大支持度的概念，可以有效地降低數(shù)據(jù)維度和計(jì)算復(fù)雜度，提高算法效率和準(zhǔn)確率。

2.1　概念定義

定義1權(quán)限項(xiàng)集。權(quán)限的集合U={I1，I2，…Im}，I表示每個(gè)權(quán)限。

定義2事務(wù)。設(shè)權(quán)限數(shù)據(jù)庫DB是事務(wù)的集合，其中每個(gè)事務(wù)T是單個(gè)應(yīng)用程序申請的權(quán)限集合。

定義3支持度s。設(shè)U1為權(quán)限項(xiàng)集，s是權(quán)限樣本庫DB中事務(wù)包含U1的百分比，即概率P(U1)。最小支持度min_sup是權(quán)限項(xiàng)集U在樣本集中出現(xiàn)的最小概率，最大支持度max_sup是權(quán)限項(xiàng)集U在樣本集中出現(xiàn)的最大概率。

定義4支持度計(jì)數(shù)。權(quán)限I的出現(xiàn)次數(shù)。

定義5頻繁項(xiàng)列表L。用于儲(chǔ)存所有權(quán)限、支持度計(jì)數(shù)及節(jié)點(diǎn)指針的列表。

定義6權(quán)限FP-Tree。一種包含所有事務(wù)權(quán)限的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)。條件FP-Tree是以某一權(quán)限為基點(diǎn)，由FP-Tree中與下方分支一起出現(xiàn)的上方分支構(gòu)造。

定義7條件權(quán)限基。條件權(quán)限基是以所查找權(quán)限項(xiàng)為結(jié)尾的分支的集合。

2.2　算法描述

DroidFP-Growth算法發(fā)現(xiàn)頻繁項(xiàng)集的基本過程包含三個(gè)步驟：首先是篩選樣本集，然后構(gòu)造權(quán)限FP-Tree，最后從權(quán)限FP-Tree中挖掘權(quán)限頻繁項(xiàng)集。下面通過一組實(shí)例描述算法。

步驟一：篩選樣本集。在篩選中，首先根據(jù)單個(gè)權(quán)限的支持度進(jìn)行篩選，在步驟三中，則是根據(jù)權(quán)限項(xiàng)集的支持度進(jìn)行篩選。表1給出6個(gè)應(yīng)用程序申請的所有權(quán)限，設(shè)最小支持度為3，即min_sup=50.00%，最大支持度為5，即max_sup=83.34%。

表1　一組惡意應(yīng)用的事務(wù)數(shù)據(jù)樣例DB

最小支持度為3，因此舍棄{WRITE_SMS}{RECEIVE_SMS}兩個(gè)權(quán)限，最大支持度為5，先暫時(shí)剔除{WAKE_LOCK}權(quán)限。

步驟二：構(gòu)造權(quán)限FP-Tree。

1)首先掃描一次樣本庫，獲得頻繁項(xiàng)的列表L，按照支持度計(jì)數(shù)遞減排序，即L={{INTERNET}{SEND_SMS}{READ_PHONE_STATE}{ACCESS_FINE_LOCATION}{ACCESS_FINE_LOCATION}{RECORD_AUDIO}}。

2)第二次掃描樣本庫，利用每個(gè)應(yīng)用程序中出現(xiàn)的權(quán)限頻繁項(xiàng)構(gòu)造權(quán)限FP-Tree。創(chuàng)建樹的根節(jié)點(diǎn)NULL。處理每個(gè)事務(wù)時(shí)，依據(jù)L中的順序?qū)⒊霈F(xiàn)的權(quán)限頻繁項(xiàng)添加到權(quán)限FP-Tree中的一個(gè)分支。

① 掃描001.apk，按照L中的順序，構(gòu)造權(quán)限FP-Tree的第一個(gè)樹支<(INTERNET:1)( READ_PHONE_STATE:1)>；

② 掃描002.apk，按照L中的順序排序，與第一個(gè)樹支共享節(jié)點(diǎn)(INTERNET)，將樹節(jié)點(diǎn)(INTERNET)計(jì)數(shù)加1，并創(chuàng)建第二個(gè)樹支：<(SEND_SMS:1), (ACCESS_NETWORK_STATE:1), (ACCESS_FINE_LOCATION:1), (RECORD_AUDIO:1)>;

③ 迭代前兩步，將數(shù)據(jù)庫中的權(quán)限信息都添加到權(quán)限FP-Tree中，構(gòu)造好的FP-Tree如圖1所示。

圖1　權(quán)限FP-Tree

步驟三：挖掘權(quán)限頻繁項(xiàng)集。從一顆權(quán)限FP-Tree中挖掘權(quán)限頻繁項(xiàng)集，一般是根據(jù)L表，自下而上挖掘權(quán)限頻繁項(xiàng)集。其過程如下：首先從權(quán)限FP-Tree中獲取條件權(quán)限基；第二，利用條件權(quán)限基，構(gòu)建一個(gè)權(quán)限條件FP-Tree，構(gòu)造的權(quán)限條件FP-Tree采用自下而上的方式；第三，迭代前兩步，直到樹僅剩一個(gè)權(quán)限項(xiàng)為止。表2給出了上例當(dāng)中每一個(gè)權(quán)限頻繁項(xiàng)的所有上方分支。

表2　每個(gè)權(quán)限頻繁項(xiàng)的條件權(quán)限基

以(RECORD_AUDIO)權(quán)限為例，其條件FP-Tree形成過程如圖2所示。由于最小支持度為3，故去掉(ACCESS_FINE_LOCATION) ，(READ_PHONE_ STATE)，從而得出最小支持度為3時(shí)，其產(chǎn)生的權(quán)限頻繁項(xiàng)集為{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時(shí)其他權(quán)限的頻繁項(xiàng)集，如表3所示。比較所有頻繁項(xiàng)集，獲得其最大頻繁項(xiàng)集，最后將超過最大支持度的權(quán)限{WAKE_LOCK}加入其中，則此組應(yīng)用的最大頻繁項(xiàng)集為{WAKE_LOCK, INTERNET,SEND_SMS, RECORD_AUDIO, ACCESS_NETWORK_STATE}。

表3　其他權(quán)限頻繁項(xiàng)產(chǎn)生的頻繁項(xiàng)集

2.3　算法分析

最小支持度閾值和最大支持度閾值是關(guān)系算法最終檢測率和準(zhǔn)確率的關(guān)鍵要素。在實(shí)驗(yàn)中不斷調(diào)整兩種閾值，給每一類惡意應(yīng)用程序測算不同的閾值，是算法的關(guān)鍵。本文提出的最大支持度閾值的定義，可以大大降低在算法復(fù)雜度和數(shù)據(jù)維度，提高挖掘權(quán)限頻繁項(xiàng)集的效率。

算法1DroidFP-Growth算法

輸入： 樣本庫DB、最小支持度min_sup，最大支持度max_sup。

輸出： 最大權(quán)限頻繁項(xiàng)集Tmax。

方法：

構(gòu)造權(quán)限FP-Tree

1) for(i=1;i≤n;i++){//將n個(gè)應(yīng)用程序全部掃描

//一遍；

2)Ti=extract(DBi)//提取應(yīng)用程序的權(quán)限信息；

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

//小支持度和最大支持度構(gòu)建頻繁項(xiàng)集列表Lk，其中p是第一

//個(gè)元素，P是頻繁項(xiàng)表中去除p后剩余元素組成的項(xiàng)表；

4) returnLk(p|P)

5)Tree=(NULL,P) //創(chuàng)建根節(jié)點(diǎn)NULL；

6) for(i=1;i≤n;i++){//第二次掃描數(shù)據(jù)庫；

7)insert_tree([p|P],Tree)//根據(jù)頻繁項(xiàng)集列表更新權(quán)限FP-Tree；

8) return Tree

從FP-Tree中提取最大頻繁項(xiàng)集；

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

10) returnTmax=p∪P

11) else

12) for(p=1;p≤k;p++){//遍歷頻繁項(xiàng)表中的每一個(gè)元

//素，直到Pk=?；

13)Treek=(pk,Pk)//根據(jù)條件權(quán)限基構(gòu)造條件FP-Tree；

14) returnTk=pk∪Pk}

15) returnTmax=max(T1,T2,…,Tk)//選取最大權(quán)限頻繁

//項(xiàng)集；

16) end if

//挖掘結(jié)束，獲得最大頻繁項(xiàng)集。

3　實(shí)驗(yàn)與結(jié)果

本文設(shè)計(jì)了多個(gè)實(shí)驗(yàn)來驗(yàn)證基于權(quán)限頻繁模式挖掘算法進(jìn)行Android 應(yīng)用惡意代碼檢測的有效性和正確性，對比其他Android 惡意應(yīng)用檢測方法，實(shí)驗(yàn)結(jié)果證明了本文提出的檢測方法效果更優(yōu)。

3.1　實(shí)驗(yàn)樣本

本文使用的惡意應(yīng)用樣本來自于安卓基因組計(jì)劃[12]，此惡意應(yīng)用樣本庫共包含1 260個(gè)惡意應(yīng)用樣本，其內(nèi)包含49個(gè)惡意應(yīng)用家族，此經(jīng)典惡意應(yīng)用樣本庫被其他研究者廣泛使用于惡意應(yīng)用檢測。

使用的測試樣本包含1 000個(gè)不同類別的應(yīng)用，包括常用的軟件集合，如社交軟件、游戲軟件、讀書軟件、辦公軟件等，500個(gè)為惡意應(yīng)用，500個(gè)為正常應(yīng)用。其中正常應(yīng)用從Google Play下載，包含各種類別的Android應(yīng)用，保證了其廣泛性和通用性。同時(shí)為了保證測試樣本的準(zhǔn)確性，使用各種殺毒軟件、惡意應(yīng)用檢測工具進(jìn)行過濾；惡意應(yīng)用測試樣本從惡意樣本分享網(wǎng)站https://virusshare.com/下載收集。

3.2　實(shí)驗(yàn)結(jié)果及分析

在檢測結(jié)果分析中，通常有四個(gè)指標(biāo)衡量檢測結(jié)果的好壞：真陽性TP，表示惡意應(yīng)用檢測準(zhǔn)確個(gè)數(shù)；假陽性FP，表示良性應(yīng)用檢測錯(cuò)誤個(gè)數(shù)；真陰性TN，表示良性應(yīng)用檢測準(zhǔn)確個(gè)數(shù)；假陰性FN，表示惡意應(yīng)用檢測錯(cuò)誤個(gè)數(shù)。檢測率代表所有惡意樣本中正確分類為惡意應(yīng)用的比例，其公式表達(dá)為：

(1)

誤報(bào)率為代表所有正常樣本中錯(cuò)誤分類為惡意應(yīng)用的比例，其公式表達(dá)為：

(2)

分類精度即為準(zhǔn)確率，其公式表達(dá)為：

(3)

本文使用DroidFP-Growth算法進(jìn)行權(quán)限特征庫的建立。同一家族的惡意應(yīng)用其惡意行為類似，認(rèn)為其所申請的權(quán)限也類似，按惡意應(yīng)用家族進(jìn)行權(quán)限頻繁項(xiàng)集的提取，對最終的未知應(yīng)用檢測效果更好。其檢測方法架構(gòu)如圖3所示。

圖3　惡意應(yīng)用檢測方法框架

首先，使用AAPT工具提取樣本庫的應(yīng)用權(quán)限信息，建立權(quán)限樣本庫DB；然后，使用python語言編寫DroidFP-Growth算法，按應(yīng)用家族挖掘最大頻繁項(xiàng)集，構(gòu)建權(quán)限關(guān)系特征庫；最后，對未知應(yīng)用檢測，判斷是否惡意。

使用不同的檢測方法對經(jīng)典惡意樣本庫進(jìn)行檢測，其中Kirin方法[5]只能檢測出37個(gè)，TPR為2.93%；Androguard方法[13]檢測出851個(gè)惡意應(yīng)用，TPR為67.53%；使用同屬數(shù)據(jù)挖掘技術(shù)的PApriori方法[10]檢測出1 003個(gè)惡意應(yīng)用，TPR為79.60%，而使用本方法進(jìn)行檢測，最終可以檢測出1 052個(gè)惡意應(yīng)用，TPR達(dá)到83.49%。其結(jié)果對比如圖4所示，由于篇幅原因，圖中只列舉了樣本集中部分惡意應(yīng)用數(shù)量較多家族。

圖4　實(shí)驗(yàn)結(jié)果對比

將測試樣本分為10組，每組含50個(gè)良性應(yīng)用和50個(gè)惡意應(yīng)用，隨機(jī)抽選5組樣本使用本文提出的方法進(jìn)行檢測，其檢測結(jié)果如表4所示。

表4　測試樣本集檢測結(jié)果

由表4可知，本方法檢測率為82.8%，準(zhǔn)確率達(dá)到85.2%。相比于同類基于權(quán)限特征的檢測方法，有很大的提高。另外本方法的算法速度優(yōu)于其他同類方法，尤其是在挖掘較大樣本集時(shí)，只需要遍歷兩次數(shù)據(jù)集即可獲得頻繁項(xiàng)集，更加有效和準(zhǔn)確。

4　結(jié)　語

針對Android手機(jī)應(yīng)用程序存在的安全問題，本文提出一種基于權(quán)限特征的Android應(yīng)用靜態(tài)檢測方法。方法利用數(shù)據(jù)挖掘技術(shù)，對Android系統(tǒng)特有的權(quán)限特征進(jìn)行頻繁項(xiàng)集挖掘，獲得權(quán)限頻繁項(xiàng)集，以此來對應(yīng)用進(jìn)行檢測。針對挖掘頻繁項(xiàng)集時(shí)速度慢，準(zhǔn)確率低的問題，提出DroidFP-Growth算法。實(shí)驗(yàn)結(jié)果表明，方法的檢測率可達(dá)82.8%，準(zhǔn)確率達(dá)到85.2%，相比其他方法都有進(jìn)一步的提升。本文主要針對靜態(tài)檢測特征中的權(quán)限特征進(jìn)行提取，下一步研究其他特征的檢測方法，包括API、函數(shù)調(diào)用、系統(tǒng)調(diào)用等特征，同時(shí)將動(dòng)態(tài)檢測與靜態(tài)檢測相結(jié)合，形成全面的檢測系統(tǒng)。

[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年中國手機(jī)安全狀況報(bào)告[EB/OL]. http://zt.#/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] 楊歡. 協(xié)議漏洞挖掘及Android平臺(tái)惡意應(yīng)用檢測技術(shù)研究[D]. 西安：西安電子科技大學(xué), 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.