李秀 陸南

（江蘇科技大學(xué)電子信息學(xué)院 鎮(zhèn)江 212000）

1 引言

360手機(jī)衛(wèi)士報告顯示［1］，就目前截獲的An?droid惡意應(yīng)用已達(dá)到三千五百萬個，僅2016年全年，截獲的Android惡意應(yīng)用有1403.3萬個，而且還在以每天3.8萬的增速增加。同時，累計檢測到的已感染Android惡意應(yīng)用的用戶達(dá)到2.14億。可以說，近五年以來，Android惡意應(yīng)用正在以指數(shù)形式增長。

目前Android惡意應(yīng)用的檢測方法主要分為動態(tài)檢測和靜態(tài)檢測。靜態(tài)檢測中主流的靜態(tài)特征主要是權(quán)限，Enck［2］、Barrera［3］等都通過對權(quán)限的研究來區(qū)分正常應(yīng)用和惡意應(yīng)用。且隨著大數(shù)據(jù)時代的到來，數(shù)據(jù)挖掘得到越來越廣泛的應(yīng)用，很多研究者將數(shù)據(jù)挖掘應(yīng)用在移動端惡意應(yīng)用檢測上。

Wu D J等利用數(shù)據(jù)挖掘中的聚類和分類提出了一種惡意應(yīng)用檢測方法，首先運用聚類中的K-均值算法和奇異值分解算法SVD處理靜態(tài)特征，然后運用分類中的K最近鄰算法KNN進(jìn)行分類建模［4］。

楊歡等提出了一種PApriori檢測方法，利用Apriori算法分別對49個惡意應(yīng)用家族所申請的權(quán)限信息進(jìn)行關(guān)聯(lián)分析，得到每個惡意應(yīng)用家族在不同支持度和置信度下的極大頻繁項集和關(guān)聯(lián)規(guī)則［5］。但是該方法受到Apriori算法的限制，運行時間較長、效率較低。

Sanz等提出了一種PUMA工具，該工具提取權(quán)限特征，然后用多種數(shù)據(jù)挖掘算法對數(shù)據(jù)進(jìn)行分類建模，最后用多種分類模型對239個待測應(yīng)用程序進(jìn)行分類［6］，但是該方法沒有對權(quán)限進(jìn)行相應(yīng)處理，且待測應(yīng)用程序數(shù)量較少，不能充分說明結(jié)果。

周運飛等人首先對權(quán)限進(jìn)行頻繁模式挖掘，然后得到指定支持度下的極大頻繁項集，最后將它們作為樸素貝葉斯的特征輸入［7］。該方法的真正類率和真負(fù)類率分別為82.6%和83.6%，相對較低，且該方法沒有充分考慮樣本的獨立性。

本文提出了RApriori方法：

1）在利用Apriori算法挖掘極大頻繁項集之前，先用Relief算法對權(quán)限特征去冗余，進(jìn)行第一步特征選擇，這大大減少了Apriori算法的工作量；

2）利用Apriori算法分析正常應(yīng)用和惡意應(yīng)用申請的權(quán)限的差異，分別得出正常應(yīng)用和惡意應(yīng)用的極大頻繁項集，進(jìn)行第二步特征選擇。這樣選擇出的特征有很強(qiáng)的關(guān)聯(lián)性，對分類有較大貢獻(xiàn)。

利用隨機(jī)森林算法建立多棵分類樹，每棵樹都對待測應(yīng)用進(jìn)行判斷，這樣減小了判斷錯誤率，提高了檢測準(zhǔn)確率。

2 檢測方法設(shè)計

檢測方法共分為三部分：特征準(zhǔn)備、特征選擇和特征分類。其流程圖如圖1所示。

圖1 RApriori檢測流程圖

2.1 特征準(zhǔn)備

首先獲得Android正常應(yīng)用和惡意應(yīng)用的安裝包，即.apk文件。正常應(yīng)用來自360應(yīng)用市場（通過騰訊管家和金山毒霸等殺毒軟件進(jìn)行掃描，基本確保了應(yīng)用程序的安全性），共300個；惡意應(yīng)用來自VirusShare，共300個；然后解壓每個Android應(yīng)用程序；最后利用apktool批量反編譯Android應(yīng)用程序，提取每個Android應(yīng)用程序的權(quán)限特征，得到初始權(quán)限特征庫。此時的訓(xùn)練樣本即是擁有初代權(quán)限特征庫的訓(xùn)練樣本。

2.2 特征選擇

2.2.1 基于Relief算法去冗余

應(yīng)用程序所申請的權(quán)限都不是單一存在的，它們之間有一定的關(guān)聯(lián)關(guān)系，本文利用Apriori算法分別對正常應(yīng)用和惡意應(yīng)用的權(quán)限進(jìn)行關(guān)聯(lián)分析。

如果對應(yīng)用程序申請的所有權(quán)限全部進(jìn)行關(guān)聯(lián)分析，毫無疑問，費時費力。所以，對權(quán)限特征進(jìn)行去冗余是有必要的。在對特征去冗余的幾種算法進(jìn)行研究比較之后，發(fā)現(xiàn)Relief算法能很好適用于該場景。

Relief算法在1992年由Kira和Rendell提出，該算法設(shè)計了一個“相關(guān)統(tǒng)計量”來度量特征的重要性，這個“相關(guān)統(tǒng)計量”可以視為是每個特征的“權(quán)重”［8］。它的基本思想是根據(jù)各個特征和類別的相關(guān)性賦予特征不同的權(quán)重，權(quán)重小于某個閾值的特征將被移除。

從擁有初代權(quán)限特征庫的訓(xùn)練樣本中隨機(jī)選擇一個樣本R（該樣本可能是正常應(yīng)用也可能是惡意應(yīng)用）；然后在與R同類的樣本集中，尋找與之最相近的樣本H；再在與R不同類的樣本集中，尋找與之最近鄰的樣本M，最后根據(jù)式（1）更新每個權(quán)限特征的權(quán)重。

式中：R（j）表示樣本R關(guān)于第j個權(quán)限特征的值；d（·）表示距離函數(shù)，用來計算樣本R和樣本H（或樣本M）關(guān)于某個權(quán)限特征的距離；m是隨機(jī)抽樣的次數(shù)。

權(quán)限特征是非數(shù)值型特征，距離函數(shù)d（·）定義如式（2）所示。

最后經(jīng)過篩選過濾，剩余65個權(quán)限。權(quán)重從大 到 小 依 次 為 SEND_SMS、RECEIVE_SMS、WRITE_SETTINGS、 READ_PHONE_STATE、READ_SMS、MOUNT_UNMOUNT_FILESYSTEMS、ACCESS_NETWORK_STATE、 SYS?TEM_ALERT_WINDOW、 RECEIVE_BOOT_COM?PLETED、 VIBRATE、 CHANGE_NET?WORK_STATE、CAMERA……由于權(quán)限較多，在此不一一贅述。

刪除擁有初代權(quán)限特征庫的訓(xùn)練樣本中每個Android應(yīng)用程序多余的權(quán)限特征，即得到擁有二代權(quán)限特征庫的訓(xùn)練樣本。

2.2.2 基于Apriori算法關(guān)聯(lián)選擇

Apriori作為數(shù)據(jù)挖掘中最重要的關(guān)聯(lián)規(guī)則算法，由Agrawal等在1993年提出［9］，一經(jīng)提出，就被應(yīng)用到各個領(lǐng)域。Wang等將Apriori算法運用在電腦端惡意代碼檢測［10］；郭淑紅等利用Apriori算法研究股票市場中股票價格的相關(guān)性［11］；金銳等利用Apriori算法，探求中藥中氣-味-效三者之間的頻繁模式和強(qiáng)關(guān)聯(lián)規(guī)則［12］；韋哲等通過Apriori生成的關(guān)聯(lián)規(guī)則來完成對糖尿病高危人群的初判斷［13］。

Apriori算法的核心思想是通過候選集生成和情節(jié)的向下封閉檢測兩個階段來挖掘頻繁項集。

將擁有二代權(quán)限特征庫的訓(xùn)練樣本送入Apri?ori算法，通過該算法分別找到正常應(yīng)用和惡意應(yīng)用的極大頻繁項集，即是分別找到了正常應(yīng)用和惡意應(yīng)用具有強(qiáng)關(guān)聯(lián)規(guī)則的權(quán)限特征，而這些權(quán)限能很好地區(qū)分正常應(yīng)用和惡意應(yīng)用。

當(dāng)支持度為0.4時，正常應(yīng)用的極大頻繁項集為 ACCESS_COARSE_LOCATION、CHANGE_WIFI_STATE、ACCESS_FINE_LOCATION、GET_TASKS、 INTERNET、 READ_EXTERNAL_STOR?AGE、 READ_PHONE_STATE、 ACCESS_NET?WORK_STATE、SYSTEM_ALERT_WINDOW、VI?BRATE、 WAKE_LOCK、 WRITE_EXTERNAL_STORAGE、 WRITE_SETTINGS、 ACCESS_WIFI_STATE。

當(dāng)支持度為0.25時，惡意應(yīng)用的極大頻繁項集為 INTERNET、 READ_EXTERNAL_STORAGE、READ_PHONE_STATE、READ_SMS、RECEIVE_SMS、SEND_SMS、WAKE_LOCK、WRITE_EXTER?NAL_STORAGE、RECEIVE、C2D_MESSAGE、AC?CESS_COARSE_LOCATION、ACCESS_COARSE_UPDATES、ACCESS_FINE_LOCATION、INSTALL_PACKAGES、RECEIVE_BOOT_COMPLETED、AC?CESS_NETWORK_STATE、SYSTEM_ALERT_WIN?DOW、WRITE_SECURE_SETTINGS、WRITE_SET?TINGS、SET_ALARM、INSTALL_SHORTCUT。

將以上正常應(yīng)用和惡意應(yīng)用的極大頻繁項集相結(jié)合，即得到經(jīng)過二次特征選擇的最終權(quán)限特征庫。

刪除擁有二代權(quán)限特征庫的訓(xùn)練樣本中每個Android應(yīng)用程序多余的權(quán)限特征，即得到擁有最終權(quán)限特征庫的訓(xùn)練樣本。

2.3 特征分類

隨機(jī)森林算法［14］將隨機(jī)性引入其輸入中，使用不同的隨機(jī)數(shù)多次重復(fù)學(xué)習(xí)，然后將多個分類器的預(yù)測結(jié)果通過投票的方式得出結(jié)論，這大大增加了分類結(jié)果的穩(wěn)定性和正確率。

從建立的森林中隨機(jī)選擇一棵分類樹，該分類樹如圖2所示。

多棵分類樹構(gòu)成隨機(jī)森林算法分類器，使用該分類器即可檢測Android應(yīng)用程序是否是惡意應(yīng)用。

3 實驗結(jié)果與分析

3.1 實驗樣本

正常應(yīng)用樣本共1000個，主要從360應(yīng)用市場獲取，并且通過騰訊管家和金山毒霸對該樣本進(jìn)行掃描殺毒，基本確保了正常應(yīng)用的安全性。惡意應(yīng)用樣本共1000個，主要從國外的研究機(jī)構(gòu)Vi?rusShare獲取。

訓(xùn)練樣本主要包含正常應(yīng)用樣本300個、惡意應(yīng)用樣本300個。為充分了解RApriori方法的有效性和穩(wěn)定性，測試樣本主要分為7組，即在包含正常應(yīng)用樣本300個、惡意應(yīng)用樣本300個的訓(xùn)練樣本的基礎(chǔ)之上每次添加正常應(yīng)用100個、惡意應(yīng)用100個，共添加7次。

圖2 決策樹

將7組測試樣本分別利用apktool進(jìn)行反編譯，批量獲得它們的權(quán)限特征，此時得到的是7組擁有初代權(quán)限特征庫的測試樣本。分別對7組擁有初代權(quán)限特征庫的測試樣本進(jìn)行以下處理：對比經(jīng)過Relief算法和Apriori算法的最終權(quán)限特征庫，把擁有初代權(quán)限特征庫的測試樣本的每一個Android應(yīng)用程序多余的權(quán)限剔除。最后得到7組擁有最終權(quán)限特征庫的測試樣本。

3.2 實驗性能參數(shù)

本文的實驗性能參數(shù)主要有4個：真正類、假正類、真負(fù)類和假負(fù)類。

1）真正類，TP（True Positive），如果樣本實際為正類并且被檢測為正類。

2）假正類，F(xiàn)P（False Positive），如果樣本實際為負(fù)類但被檢測為正類。

3）真負(fù)類，TN（True Negative），如果樣本實際為負(fù)類并且被檢測為負(fù)類。

4）假負(fù)類，F(xiàn)N（False Negative），如果樣本實際為正類但被檢測為負(fù)類。

根據(jù)4個實驗性能參數(shù)得到4個實驗性能指標(biāo)：真正類率、假正類率、真負(fù)類率和假負(fù)類率。

真正類率用TPR（True Positive Rate）表示，其計算公式為

假正類率用FPR（False Positive Rate）表示，其計算公式為

真負(fù)類率用TNP（True Negative Rate）表示，其計算公式為

假負(fù)類率用FNR（False Negative Rate）表示，其計算公式為

3.3 實驗結(jié)果與分析

將7組擁有最終權(quán)限特征庫的測試樣本分別作為隨機(jī)森林算法分類模型的輸入，得到的實驗結(jié)果如表1所示。

表1 RApriori方法實驗結(jié)果詳情表

由上表可知，RApriori方法具有較高的準(zhǔn)確率，真正類率和真負(fù)類率基本達(dá)到90%，而假正類率和假負(fù)類率都不到10%。此外，在這七次實驗中，隨著測試樣本數(shù)量的增多，真正類率和真負(fù)類率有相應(yīng)的減少，但幅度并不大，說明該方法可以用來檢測大量惡意應(yīng)用。

上述實驗是經(jīng)過特征選擇后的實驗結(jié)果，如果不經(jīng)過特征選擇，直接把擁有初始權(quán)限特征庫的訓(xùn)練樣本作為隨機(jī)森林算法的輸入，分類建模，然后對7組擁有初始權(quán)限特征庫的測試樣本分別進(jìn)行檢測，得到的檢測結(jié)果詳情表如表2所示。

表2 未經(jīng)特征選擇的實驗結(jié)果詳情表

由上表可以看出，如果不經(jīng)過特征選擇，直接利用隨機(jī)森林算法分類建模，得到的假正類率有的高達(dá)46.6%，而真負(fù)類率僅僅為53.4%。且實驗結(jié)果不穩(wěn)定，相差較大。

隨機(jī)森林算法是建立在決策樹算法的基礎(chǔ)上，決策樹只需建立一棵分類樹即可，而隨機(jī)森林算法需要建立多棵分類樹，文獻(xiàn)［15］使用決策樹分類器來檢測惡意應(yīng)用。在經(jīng)過使用本文提出的特征選擇方法處理訓(xùn)練樣本和測試樣本之后，使用決策樹分類的實驗結(jié)果詳情表如表3所示。

表3 決策樹分類實驗結(jié)果詳情表

由上表可以看出，使用決策樹分類，真正類率和真負(fù)類率基本穩(wěn)定在80%，比使用隨機(jī)森林算法分類低10%左右，而假正類率和假負(fù)類率基本穩(wěn)定在19%，比使用隨機(jī)森林算法分類高10%左右。

4 結(jié)語

本文提出了一種特征選擇方法RApriori，該方法結(jié)合Relief算法和Apriori算法對權(quán)限進(jìn)行二次特征選擇。利用Relief算法對權(quán)限進(jìn)行去冗余，這大大減小了Apriori算法的計算量。選擇具有良好分類特性的隨機(jī)森林算法，該算法基于決策樹算法，不同的是，隨機(jī)森林會建立多棵分類樹，每棵分類樹都對待測應(yīng)用進(jìn)行判斷，最后用投票的方式來決定判斷的結(jié)果，這樣大大提高了檢測的正確率，并降低了檢測的誤報率。

RApriori方法只針對權(quán)限進(jìn)行了研究，如果應(yīng)用程序存在權(quán)限繞過問題（有些應(yīng)用程序可以執(zhí)行某些權(quán)限的行為，但是在AndroidManifest.xml文件中并沒有申請該權(quán)限），很可能會存在漏報問題。下一步工作中，靜態(tài)特征除了研究權(quán)限之外，可以增加諸如意圖、廣播接收器等，更清楚了解應(yīng)用程序的行為信息。