基于隨機(jī)森林算法的Android惡意代碼特征分析

劉賀翔，李英娜，張長(zhǎng)勝，任小波，李 川

(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院，云南 昆明 650500)

隨著手機(jī)逐漸成為人們生活中必不可少的產(chǎn)品。惡意代碼開(kāi)發(fā)者利用Android開(kāi)放性平臺(tái)開(kāi)發(fā)出許多惡意代碼，進(jìn)而對(duì)用戶手機(jī)進(jìn)行非法干擾。智能手機(jī)終端一經(jīng)被惡意代碼感染，攻擊者(“黑客”)就可以通過(guò)惡意代碼的方式非法獲取到用戶大量的隱私信息[1](包括用戶帳號(hào)與密碼信息、用戶手機(jī)號(hào)碼信息等)，甚至進(jìn)行截?cái)喽绦?、刪除用戶移動(dòng)終端中的應(yīng)用程序等惡意行為，從而導(dǎo)致一系列嚴(yán)重事件發(fā)生。因此，對(duì)Android惡意代碼的特征分析具有重要的實(shí)際意義。

惡意代碼檢測(cè)效率的主要因素之一是特征的描述能力，如何更為有效地檢測(cè)惡意代碼是目前惡意代碼防御的熱點(diǎn)。中國(guó)科學(xué)院的王蕊，馮登國(guó)等人[2]提出了一種基于語(yǔ)義的惡意代碼行為特征提取及檢測(cè)方法，從而提高對(duì)惡意代碼變種的檢測(cè)能力。西安交通大學(xué)智能網(wǎng)絡(luò)與網(wǎng)絡(luò)安全教育部重點(diǎn)實(shí)驗(yàn)室的胡文君，趙雙等人[3]提出了一種針對(duì)Android平臺(tái)惡意代碼的檢測(cè)方法及系統(tǒng)實(shí)現(xiàn)，同時(shí)免費(fèi)提供分析檢測(cè)服務(wù)，所提檢測(cè)方案具有較高的檢測(cè)率和較低的誤報(bào)率。

本文采用隨機(jī)森林算法(Random Forests Algorithm，RF)對(duì)應(yīng)用特征進(jìn)行匹配訓(xùn)練，從原始訓(xùn)練集中有放回的抽取一定數(shù)量的樣本，作為根節(jié)點(diǎn)并開(kāi)始不斷進(jìn)行訓(xùn)練，直到所有節(jié)點(diǎn)都被遍歷，或者訓(xùn)練結(jié)束，從而實(shí)現(xiàn)特征葉子節(jié)點(diǎn)與案例庫(kù)中的特征匹配。

1 Android權(quán)限特征的提取

權(quán)限特征是對(duì)應(yīng)用程序惡意行為的一種描述，在檢測(cè)移動(dòng)終端惡意代碼的時(shí)候，可以根據(jù)權(quán)限特征對(duì)良性應(yīng)用和惡意應(yīng)用做出區(qū)分。安卓應(yīng)用程序在安裝及運(yùn)行的時(shí)候，它所申請(qǐng)的權(quán)限序列被保存在安卓應(yīng)用程序配置文件AndroidManifest.xml中。為了安卓權(quán)限特征的提取，第一步需要針對(duì)安卓應(yīng)用程序包的APK文件做出反編譯處理的操作，得到配置文件AndroidManifest.xml，提取AndroidManifest.xml配置文件中的權(quán)限特征序列。目前，反編譯預(yù)處理操作應(yīng)用最多的就是apktoolkit反編譯工具。經(jīng)過(guò)運(yùn)用apktoolkit反編譯操作的指令，獲取得到APK文件的源碼[4]。在特征權(quán)限的提取過(guò)程中，主要關(guān)心的是經(jīng)過(guò)反編譯安卓APK文件之后獲得的配置文件AndroidManifest.xml 。配置文件前幾行展示了安卓應(yīng)用程序屏幕設(shè)置的信息、版本的信息等等。從配置文件中，可以得到該移動(dòng)終端安卓應(yīng)用程序所申請(qǐng)的權(quán)限信息，該安卓應(yīng)用程序基本上所申請(qǐng)的權(quán)限有NAPS_RECEIVE、RED_GSERUICES、CANERA、VIBARTE、CALL_PHONE、CACCESS_BOOT_COMPLETED、WRITE_EXTERNAL_STORAGE、WAKE_LOCK、READ_PHONE_STATE、ACCESS_WIFI_STATE、GET_TASKS等。

2 隨機(jī)森林算法的特征分析與應(yīng)用

隨機(jī)森林算法包括許多決策樹(shù)分類器，各個(gè)決策樹(shù)之間沒(méi)有關(guān)聯(lián)。算法工作原理為：隨機(jī)森林算法隨機(jī)并且有放回的從給定訓(xùn)練樣本集合S中重復(fù)抽選出N個(gè)子樣本，組合成新訓(xùn)練樣本集，將這個(gè)樣本集組成的分類樹(shù)合起來(lái)成為隨機(jī)森林。一旦有新的樣本數(shù)據(jù)，隨機(jī)森林算法中的各個(gè)決策樹(shù)(DecisionTree)將會(huì)分別進(jìn)行判斷工作。隨機(jī)森林算法中每一個(gè)DecisionTree都擁有一樣的屬性分布，一個(gè)DecisionTree的分類能力效果可能不好，但是在通過(guò)隨機(jī)產(chǎn)生很多DecisionTree之后，經(jīng)過(guò)統(tǒng)計(jì)一個(gè)個(gè)DecisionTree的分類結(jié)果以后，就可以對(duì)新樣本特征數(shù)據(jù)進(jìn)行分類[5-6]。

2.1 DecisionTree

DecisionTree的功能就是分類器，其結(jié)構(gòu)是樹(shù)狀的。經(jīng)過(guò)訓(xùn)練樣本數(shù)據(jù)，構(gòu)造出DecisionTree，分類新的樣本數(shù)據(jù)，效率較高。

2.2 分裂屬性

分裂屬性兩個(gè)重要信息[7]，信息增益和基尼指數(shù)。

2.2.1 信息增益

隨機(jī)森林算法的模型樣本分類期望信息數(shù)學(xué)表達(dá)形式

I(S1,S2，…，Sm)=-∑Pilog2(pi),i=1,…,m

(1)

式中，S代表數(shù)據(jù)的集合；m代表S的分類數(shù)量P≈|Si/S|；Ci代表某個(gè)分類的標(biāo)號(hào)；Pi代表任意樣本所屬于Ci的概率；Si代表Ci上的樣本所具有的數(shù)量。

I(S1,S2,…Sm)越大，S1,S2,…,Sm越亂，越無(wú)序，分類得到的效果越不好。I(S1,S2,…,Sm)越小，S1,S2,…,Sm越純，越有序，分類得到的效果越好。

參照A屬性，進(jìn)而劃分出子集的熵值

E(A)=∑(S1j+…+Smj)S×I(S1j,…，Smj)

(2)

式中，A代表屬性，擁有V個(gè)不一樣的取值集合，通過(guò)A將S劃分成為數(shù)量為V個(gè)子集，S1,S1，…，Sv，Sij表示子集Sj中類Ci的樣本數(shù)量。

信息增益為

Gain(A)=I(s1,s2,…sm)E(A)

(3)

分裂屬性的選擇規(guī)矩：選取擁有最大信息增益的屬性為分裂屬性。

2.2.2 基尼指數(shù)

Gini指標(biāo)代表Pj類別j出現(xiàn)的頻率；倘若集合T被分成m個(gè)部分N1,N2,…，NM。把這個(gè)被分成m個(gè)部分的Gini用公式表示

(4)

隨機(jī)森林每一棵分類樹(shù)都是二叉樹(shù)結(jié)構(gòu)，分類樹(shù)從根節(jié)點(diǎn)處開(kāi)始按順序?qū)τ?xùn)練樣本集進(jìn)行訓(xùn)練。在分類樹(shù)中，該節(jié)點(diǎn)分裂為兩個(gè)節(jié)點(diǎn)，右節(jié)點(diǎn)和左節(jié)點(diǎn)，兩節(jié)點(diǎn)分別代表樣本訓(xùn)練數(shù)據(jù)的子集，按照一樣的方式不斷分裂下去，直到滿足分支終止條件為止。隨機(jī)森林算法訓(xùn)練具體流程如圖1所示[8]。

圖1 基于隨即森林算法的惡意代碼分類流程圖

第一步原始訓(xùn)練集用S表示；測(cè)試集用T表示；特征維數(shù)用F表示；

If 分類樹(shù)的數(shù)量用T表示，每棵分類樹(shù)的深度用d表示；每個(gè)節(jié)點(diǎn)使用特征數(shù)量用f表示。

End 在節(jié)點(diǎn)上，最少的信息增益用m表示；最少樣本數(shù)量用s表示；第1-t棵樹(shù)時(shí)，i=1-t。

第二步有放回的從訓(xùn)練集S中抽取數(shù)量為S(i)的樣本，作為根節(jié)點(diǎn)并開(kāi)始進(jìn)行訓(xùn)練的操作；

第三步倘若當(dāng)前節(jié)點(diǎn)未能符合end結(jié)束條件，則從F維特征中不放回的隨機(jī)性的選擇f維特征。倘使節(jié)點(diǎn)符合了end結(jié)束條件，當(dāng)前節(jié)點(diǎn)就認(rèn)為是葉子節(jié)點(diǎn)，概率p為C(j)占當(dāng)前樣本集的比例，繼續(xù)訓(xùn)練其他節(jié)點(diǎn)；

第四步重復(fù)第一、第二步，一直到所有節(jié)點(diǎn)被標(biāo)記為葉子節(jié)點(diǎn)；

第五步重復(fù)第二、第三步，一直到所有節(jié)點(diǎn)全都被訓(xùn)練過(guò)，結(jié)束。

基于隨機(jī)森林算法的預(yù)測(cè)過(guò)程如下：

第一步從當(dāng)前樹(shù)的根節(jié)點(diǎn)開(kāi)始，根據(jù)當(dāng)前節(jié)點(diǎn)的閥值a，a就判斷進(jìn)入右節(jié)點(diǎn)，直到到達(dá)滿足終止條件的葉子節(jié)點(diǎn)，并輸出預(yù)測(cè)值；

第二步重復(fù)第一步，直到全部t棵分類樹(shù)都輸出預(yù)測(cè)值為止。輸出結(jié)果為對(duì)每個(gè)C(j)的概率P做累計(jì)，即全部分類樹(shù)中預(yù)測(cè)的概率之和最大的類。

3 實(shí)驗(yàn)數(shù)據(jù)的設(shè)定

針對(duì)靜態(tài)安全測(cè)試，本文添加了一些的樣本信息。包括良性樣本和惡意樣本。其中，Android應(yīng)用惡意代碼數(shù)據(jù)集包括了90個(gè)惡意程序家族，并且其中的惡意程序樣本數(shù)目都不相同，最多的一個(gè)含有638個(gè)惡意程序樣本，所有家族總共含有的惡意程序樣本數(shù)為1 978個(gè)[9-10]。為了更好證明上述方法所達(dá)到的成果，在加入Android惡意程序之外，還向數(shù)據(jù)集中添加了非惡意樣本數(shù)。根據(jù)程序中不同的使用功能，挑出了15個(gè)類別，分別有殺毒軟件、瀏覽器、通信軟件、生活常用軟件及管理類軟件等。對(duì)每一類別中的前190個(gè)熱門(mén)應(yīng)用進(jìn)行下載，共有3 201個(gè)良性代碼數(shù)據(jù)集。部分惡意應(yīng)用代碼家族信息如表1 所示。部分良性應(yīng)用代碼家族信息如表2所示。

表1 惡意應(yīng)用代碼部分家族列表

表2 良性應(yīng)用代碼部分家族列表

本實(shí)驗(yàn)實(shí)施過(guò)程中，將安卓惡意應(yīng)用程序說(shuō)明為正樣本，良性應(yīng)用程序說(shuō)明為負(fù)樣本。為檢測(cè)本文方案的性能以及效果，需要計(jì)算Accuracy(準(zhǔn)確率)，F(xiàn)PR(誤報(bào)率)，F(xiàn)NR(漏報(bào)率) 指標(biāo)。TP 表示惡意樣本被正確分類為惡意樣本的數(shù)量；FN 表示惡意樣本被錯(cuò)誤分為良性樣本的數(shù)量；TN 表示良性樣本的數(shù)量；FP 表示良性樣本誤報(bào)為惡意樣本的數(shù)量。

準(zhǔn)確率的計(jì)算公式為

(5)

誤報(bào)率的計(jì)算公式為

(6)

漏報(bào)率的計(jì)算公式為

(7)

4 實(shí)驗(yàn)與分析

在進(jìn)行權(quán)限特征實(shí)驗(yàn)之前，需要對(duì)權(quán)限特征進(jìn)行分組，根據(jù)權(quán)限特征在相應(yīng)數(shù)據(jù)集上的排序，對(duì)權(quán)限特征進(jìn)行分組，梯度為10 個(gè)權(quán)限特征，一共分了13組，在數(shù)據(jù)集現(xiàn)有的情況下，分別使用某常用算法、隨機(jī)森林(RF)做對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)所采用的數(shù)據(jù)集合當(dāng)中良性安卓樣本和惡意安卓樣本數(shù)量都為500[11-15]。針對(duì)權(quán)限特征在實(shí)驗(yàn)數(shù)據(jù)集上的準(zhǔn)確率、誤報(bào)率、漏報(bào)率進(jìn)行實(shí)驗(yàn)結(jié)果詳細(xì)統(tǒng)計(jì)。實(shí)驗(yàn)結(jié)果如表3，表4所示，準(zhǔn)確率如圖2所示，誤報(bào)率如圖3所示，漏報(bào)率如圖 4所示。

表3 基于某常用算法權(quán)限特征

表4 基于隨機(jī)森林算法權(quán)限特征

圖2 準(zhǔn)確率曲線

圖3 誤報(bào)率曲線

從以上3幅圖中分析得到：從選擇的算法效果來(lái)看，圖2準(zhǔn)確率實(shí)驗(yàn)結(jié)果表明，在權(quán)限特征維度上，隨機(jī)森林算法(RF)的表現(xiàn)基本都比某常用算法要好；圖3表明隨機(jī)森林算法在誤報(bào)率上效果都比某常用算法好；圖4表明，隨機(jī)森林算法的漏報(bào)率在60維之前略顯不足。

圖4 漏報(bào)率曲線

5 結(jié)束語(yǔ)

對(duì)于維度不一樣的權(quán)限特征的選擇，以及不同的算法的選擇，當(dāng)特征維數(shù)約達(dá)到 60維時(shí)，無(wú)論是某常用算法還是RF算法，其準(zhǔn)確率、誤報(bào)率、漏報(bào)率所對(duì)應(yīng)的數(shù)值都接近收斂。所以，在建立基于權(quán)限特征的安卓惡意代碼檢測(cè)模塊的時(shí)候，選擇前60維的權(quán)限特征。綜上所述，為了構(gòu)建權(quán)限特征的檢測(cè)模塊，最終選擇RF算法和后60維的權(quán)限特征。

參考文獻(xiàn)

[1] 張嘉賓.Android應(yīng)用的安全性研究[D]. 北京：北京郵電大學(xué),2013.

[2] 胡文君,趙雙,陶敬,等.一種針對(duì)Android平臺(tái)惡意代碼的檢測(cè)方法及系統(tǒng)實(shí)現(xiàn)[J].西安交通大學(xué)學(xué)報(bào),2013,47(10):37-43.

[3] 王蕊,馮登國(guó),楊軼,等.基于語(yǔ)義的惡意代碼行為特征提取及檢測(cè)方法[J].軟件學(xué)報(bào),2012(2):378-393.

[4] Jian Feng. SLCRM: subjective logic-based cross-layer reputation mechanism for wireless mesh networks[J].中國(guó)通信：英文版, 2012, 9(10):40-48.

[5] Bethany B Cutts, Nicholas Moore, Ariana Fox-Gowda, et al. Testing neighborhood, information seeking, and attitudes as explanations of environmental knowledge using random forest and conditional inference models[J]. Professional Geographer, 2013, 65(4):561-579.

[6] 胡宏,陳彥萍.基于隨機(jī)森林算法的混合入侵檢測(cè)系統(tǒng)研究[J].西安文理學(xué)院學(xué)報(bào):自然科學(xué)版,2013, 16(3):68-71.

[7] 韓奕. 基于行為分析的惡意代碼檢測(cè)與評(píng)估研究[D].北京：北京交通大學(xué),2014.

[8] 李根. Android系統(tǒng)惡意代碼檢測(cè)技術(shù)研究[D].哈爾濱：哈爾濱工業(yè)大學(xué),2014.

[9] 韋澤鯤,夏靖波,張曉燕,等. 基于隨機(jī)森林的流量多特征提取與分類研究[J].傳感器與微系統(tǒng), 2016(12):55-59.

[10] 王閃閃. 基于群智能算法的神經(jīng)網(wǎng)絡(luò)建模研究[J]. 電子科技,2017,30(4):56-59.

[11] 毛蔚軒,蔡忠閩,童力. 一種基于主動(dòng)學(xué)習(xí)的惡意代碼檢測(cè)方法[J]. 軟件學(xué)報(bào),2017,28(2):384-397.

[12] 李博亞, 薛質(zhì). Android系統(tǒng)中惡意代碼的動(dòng)態(tài)檢測(cè)技術(shù)研究[J]. 上海師范大學(xué)學(xué)報(bào):自然科學(xué)版, 2017, 46(1):16-22.

[13] 毛思琪. 安卓手機(jī)失竊密隱患展示系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D]. 北京：北京交通大學(xué), 2016.

[14] 曹正鳳. 隨機(jī)森林算法優(yōu)化研究[D].北京：首都經(jīng)濟(jì)貿(mào)易大學(xué),2014.

[15] 董師師,黃哲學(xué).隨機(jī)森林理論淺析[J]. 集成技術(shù),2013 (1):1-7.