楊鳴坤 羅錦光 歐躍發(fā) 慕德俊

1(桂林航天工業(yè)學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院 廣西 桂林 541004)2(廣西電力職業(yè)技術(shù)學(xué)院電子與信息工程系 廣西 南寧 530007)3(北部灣大學(xué)機(jī)械與船舶海洋工程學(xué)院 廣西 欽州 535011)4(西北工業(yè)大學(xué)自動(dòng)化學(xué)院 陜西 西安 710072)

0 引 言

360互聯(lián)網(wǎng)安全中心發(fā)布的《2018中國手機(jī)安全生態(tài)報(bào)告》[1]中指出，僅2018年上半年該中心截獲安卓平臺(tái)新增惡意程序樣本283.1萬個(gè)。其中，截獲新增手機(jī)勒索軟件127 455個(gè)，1月-7月截獲新增手機(jī)挖礦木馬4 806個(gè)。挖礦木馬的新增是2017年全年截獲量的近20倍。當(dāng)前APP權(quán)限越界行為整體呈增長趨勢，尤其是在一些隱私相關(guān)的權(quán)限使用上。其中，寫入通話記錄權(quán)限被濫用的情況最為嚴(yán)重。

目前，Android軟件檢測方法主要有基于特征簽名(signature-based，又名特征碼)的檢測方法和基于行為(behavior-based)的檢測方法[2-3]。該種檢測方法應(yīng)用廣泛，但無法檢測未知惡意軟件。并且，由于必須要保存每一個(gè)病毒新變種的特征簽名，會(huì)直接導(dǎo)致特征庫不斷膨脹，進(jìn)而影響檢索特征的復(fù)雜度，最終帶來能耗的增加。而能耗對智能手機(jī)等移動(dòng)設(shè)備來說是非常重要的指標(biāo)。文獻(xiàn)[4-8]分別提出了基于行為的檢測方法、結(jié)合了靜態(tài)分析和動(dòng)態(tài)分析的ANDRUBIS系統(tǒng)、一種挖掘權(quán)限頻繁項(xiàng)集的算法、基于統(tǒng)計(jì)學(xué)特征的Android惡意應(yīng)用檢測方法以及采用多核模糊支持向量機(jī)算法對惡意軟件進(jìn)行檢測分類。這些方法中都是通過人工智能算法或數(shù)據(jù)挖掘算法對Android APK的惡意軟件進(jìn)行分類預(yù)測，而沒有很好地利用APK文件中的靜態(tài)信息和Permission在軟件的使用率對分類算法的影響。因此本文提出了一種以Android API和Permission作為Android APK特征的檢測方案，此方案將一個(gè)APK轉(zhuǎn)化為可以量化和參與計(jì)算的基于API或Permission的特征向量，實(shí)現(xiàn)了以API或Permission為特征的基于改進(jìn)的k-NN算法靜態(tài)檢測方法。

1 傳統(tǒng)k-NN分類算法

k近鄰(k-Nearest Neighbour，k-NN)分類算法[9]，是成熟的機(jī)器學(xué)習(xí)算法。該方法的工作原理是存在一個(gè)訓(xùn)練樣本集，該樣本集中的每個(gè)數(shù)據(jù)都存在類別標(biāo)簽，即每一個(gè)數(shù)據(jù)與所屬分類的對應(yīng)關(guān)系，當(dāng)輸入沒有標(biāo)簽的新數(shù)據(jù)后，將新數(shù)據(jù)的每個(gè)特征與樣本集中數(shù)據(jù)對應(yīng)的特征進(jìn)行比較，算法提取樣本集中特征最相似數(shù)據(jù)(最近鄰)的分類標(biāo)簽。一般來說，只選擇樣本數(shù)據(jù)集中前k個(gè)最相似的數(shù)據(jù)，通常k是不大于20的整數(shù)。

k-NN算法的核心思想是：當(dāng)無法判定當(dāng)前待分類點(diǎn)是從屬于已經(jīng)分類的哪一類時(shí)，可以依據(jù)統(tǒng)計(jì)學(xué)的理論看它所處的位置特征，衡量它周圍鄰居的權(quán)重，進(jìn)而把它歸到權(quán)重更大的那一類。該算法是基于實(shí)例的學(xué)習(xí)，使用算法時(shí)必須有接近實(shí)際數(shù)據(jù)的訓(xùn)練樣本數(shù)據(jù)。在k-NN分類方法中，當(dāng)數(shù)據(jù)量達(dá)到一定規(guī)模時(shí)，大概率會(huì)出現(xiàn)測試集中的數(shù)據(jù)(實(shí)際上此數(shù)據(jù)與被標(biāo)記樣本是相鄰的)與相似樣本的距離過大，導(dǎo)致分類準(zhǔn)確率降低，無法有效執(zhí)行。

2 APK靜態(tài)信息過濾算法

要想對APK進(jìn)行靜態(tài)分析，首先要從APK中獲取特征，被定義為惡意的APK都是完成了一定惡意行為的APK，而這些惡意行為最終都是靠程序開發(fā)者開發(fā)的功能函數(shù)來實(shí)現(xiàn)的。由于Android的機(jī)制，用戶自己開發(fā)的函數(shù)要想實(shí)現(xiàn)一定的功能，必然要利用Android的API，所以對于出現(xiàn)APK中的所有函數(shù)調(diào)用，只將其中的Android API納入到特征集合中，作為一組檢測APK的特征?？紤]到Android的安全機(jī)制和APK的運(yùn)行特點(diǎn)，要想使用Android提供的系統(tǒng)功能和系統(tǒng)資源來施行軟件的惡意行為，必然還要使用到Android提供的各種權(quán)限(Permission)，因此將APK中使用到的權(quán)限信息作為另一組檢測APK的特征[10]。而本文APK的特征定義就是從反編譯之后的代碼和Manifest文件中抽取的Android API或Permission信息[11],詳細(xì)實(shí)現(xiàn)過程如下。

假設(shè)一個(gè)特征(API或者Permission)在訓(xùn)練集樣本的m個(gè)惡意APK中都有出現(xiàn)，在n個(gè)正常APK中都有出現(xiàn)，訓(xùn)練集樣本的惡意APK的總數(shù)為M，正常APK的總數(shù)為N。那么，該特征在惡意APK中的使用率為：

(1)

該特征在正常APK中的使用率為：

(2)

則同一個(gè)特征在不同APK中的使用率之差為：

t=|fn-fp|

(3)

準(zhǔn)備分類器數(shù)據(jù)在對算法進(jìn)行訓(xùn)練之前，要對提取出來的APK靜態(tài)信息進(jìn)行過濾，即去掉冗余信息，減少冗余信息的干擾[12-13]。它包括兩個(gè)方面的內(nèi)容：一是通過統(tǒng)計(jì)學(xué)的計(jì)算找出一些高危、高使用率的API和Permission作為基準(zhǔn)特征；二是對已經(jīng)提取過的APK進(jìn)行更進(jìn)一步的特征向量的構(gòu)造[14]。要想找出這樣的基準(zhǔn)API和Permission就要對訓(xùn)練集樣本中的APK進(jìn)行統(tǒng)計(jì)，從數(shù)據(jù)庫中取出每個(gè)APK中使用的API和Permission，計(jì)算每一個(gè)API和Permission在多少個(gè)訓(xùn)練樣本APK中出現(xiàn)過。其算法具體實(shí)現(xiàn)如下：

輸入：從數(shù)據(jù)庫中取出(M+N)個(gè)APK中使用的API和Permission。

Step1FindAPI()；FindPermission()；找基準(zhǔn)API和Permission集合。其中基準(zhǔn)API集合選擇fn、fp、t值大于等于0.2的特征；而基準(zhǔn)Permission的集合是僅選擇fn和fp都大于等于0.2的。

Step2TranslateAPIVM()；TranslatePermissionVM()；將每一個(gè)APK轉(zhuǎn)換成一個(gè)向量。其中，提取出的每個(gè)APK向量中的每一維的值表示0或1，值為0表示APK沒有使用其基準(zhǔn)集合中對應(yīng)的API或Permission，值為1表示APK中使用了其基準(zhǔn)集合中對應(yīng)的API或Permission。

Step3重復(fù)(M+N)次Step2。

輸出：使用分類算法的訓(xùn)練集，即所有APK的特征向量組成的矩陣。

3 改進(jìn)的k-NN算法分類器

為了能夠使k-NN算法中惡意APK的特征向量與正常APK的特征向量距離更遠(yuǎn)，使兩個(gè)惡意APK的特征向量的距離更近，本文對k-NN算法進(jìn)行了改動(dòng)。在確定APK的基準(zhǔn)特征(API和Permission)之后，如果給惡意APK中使用率高、正常APK中使用率低的API以小的權(quán)值，或給惡意APK中使用率低，正常APK中使用率高的API以大的權(quán)值，那么會(huì)使兩個(gè)惡意APK的距離比惡意與正常APK的距離更近，這樣會(huì)使算法的精確度更高。經(jīng)過實(shí)驗(yàn)驗(yàn)證，式(3)正好滿足上述規(guī)則，即該值為改進(jìn)的k-NN算法中特征的權(quán)值。對未知類別屬性的數(shù)據(jù)集中的每個(gè)點(diǎn)一次執(zhí)行以下操作：

(1) 計(jì)算已知類別數(shù)據(jù)集中的點(diǎn)與當(dāng)前點(diǎn)之間的距離；

(2) 按照距離遞增次序排序；

(3) 選取與當(dāng)前點(diǎn)距離最小的k個(gè)點(diǎn)；

(4) 確定前k個(gè)點(diǎn)所在類別的出現(xiàn)頻率；

(5) 返回前k個(gè)點(diǎn)出現(xiàn)頻率最高的類別作為當(dāng)前點(diǎn)的預(yù)測分類。

第(1)步采用歐式距離公式計(jì)算兩個(gè)向量點(diǎn)之間的距離。

點(diǎn)1：w1=(w11,w12,…，w1i,…,w1n)

點(diǎn)2：w2=(w21,w22,…，w2i,…,w2n)

距離：

計(jì)算完所有點(diǎn)之間的距離后，可以對數(shù)據(jù)按照從小到大的次序排列。然后確定前k個(gè)距離最小元素所代表的APK的類別，并且k總是正整數(shù)，最后輸出k個(gè)類別中占多數(shù)的類別，即為當(dāng)前測試的APK的類別。為了測試分類器的效果，可以使用已知類別的數(shù)據(jù)，檢驗(yàn)分類器測出的結(jié)果是否符合預(yù)期結(jié)果。通過大量的測試數(shù)據(jù)，得到分類器的錯(cuò)誤率為分類器給出錯(cuò)誤結(jié)果的次數(shù)除以測試執(zhí)行的總數(shù)。

在獲得了樣本訓(xùn)練集的數(shù)據(jù)矩陣和樣本訓(xùn)練集的類別向量的基礎(chǔ)上，設(shè)定算法中的k值為10。對于每個(gè)樣本測試集中的APK，從數(shù)據(jù)庫中分別提取出它關(guān)于API和Permission的特征向量，再從對應(yīng)的數(shù)據(jù)表中提取出API和Permission的權(quán)值向量。然后用待檢測APK的特征向量和樣本訓(xùn)練集數(shù)據(jù)矩陣、類別向量，以及API和Permission的權(quán)值向量和k值作為改進(jìn)的k-NN分類器的輸入，算法的輸出即為待檢測的APK的屬性類別。

4 靜態(tài)檢測方案的設(shè)計(jì)與實(shí)現(xiàn)

簡單地說，機(jī)器學(xué)習(xí)就是把無序的數(shù)據(jù)轉(zhuǎn)換成有用的信息[15]。本文基于Android APK中包含的各種靜態(tài)信息利用機(jī)器學(xué)習(xí)方法來判別一個(gè)APK是否是惡意程序。

本文首先對已收集到的兩類APK樣本(惡意APK和正常APK)進(jìn)行靜態(tài)特征的提取，然后將提取到的各種靜態(tài)信息(包括：權(quán)限、API、VersionName、Package、MainActivity、ShareUserID、Feature、Activity、Service、Received、Intent)存入數(shù)據(jù)庫中。再利用這些信息從中提取描述一個(gè)APK的各種特征，作為描述APK的特征集合，將這些集合存入到數(shù)據(jù)庫中，以提高后續(xù)算法的執(zhí)行效率。從數(shù)據(jù)庫中取出每一個(gè)APK的信息，根據(jù)特征集合合成每個(gè)APK的特征向量，并將每個(gè)APK的特征向量作為中間結(jié)果存入數(shù)據(jù)庫中。最后將數(shù)據(jù)庫描述APK的中間結(jié)果作為分類算法的訓(xùn)練集，執(zhí)行分類算法，將算法執(zhí)行的結(jié)果存入數(shù)據(jù)庫。測試階段是從數(shù)據(jù)庫取出測試APK的特征向量，測試算法的精確度。

根據(jù)上述方案執(zhí)行過程設(shè)計(jì)出的方案系統(tǒng)結(jié)構(gòu)如圖1所示。

微功能模塊主要實(shí)現(xiàn)對文件的讀寫功能，從官方文件中提取Android API和權(quán)限，獲取目錄內(nèi)的文件名和子目錄名列表，獲取一個(gè)文件的大小、MD5值等。具體主要是指該功能模塊是對其他模塊提供支持的一個(gè)共用模塊，在其他模塊中，會(huì)頻繁用到一些共有的功能，比如：按行讀取一個(gè)文件的內(nèi)容；將Python中一個(gè)列表的內(nèi)容按行寫入一個(gè)dat文件中；獲取一個(gè)字符串的MD5值，文件的大小、MD5值，當(dāng)前時(shí)間，路徑信息等。

靜態(tài)信息提取模塊是完成對APK中靜態(tài)信息的提取。本模塊采用ApkTool反編譯工具，對Android APK進(jìn)行反編譯，在輸出目錄中會(huì)看到一個(gè)smali目錄和AndroidManifest.xml文件，smali目錄中按照J(rèn)ava源代碼的目錄結(jié)構(gòu)存放了生成的所有smali文件。從這些smali文件和AndroidManifest.xml文件中抽取APK的靜態(tài)信息，存儲(chǔ)到數(shù)據(jù)庫中，為最后生成APK的特征向量做準(zhǔn)備工作。

分類器模塊的設(shè)計(jì)構(gòu)造了基于改進(jìn)的k-NN算法的分類器。其主要實(shí)現(xiàn)過程是準(zhǔn)備好執(zhí)行算法所需要的數(shù)據(jù)，包括確定準(zhǔn)API和Permission集合，每個(gè)基準(zhǔn)特征的條件概率[16-17]、訓(xùn)練集和測試集的樣本矩陣、訓(xùn)練集和測試集的樣本類別向量、改進(jìn)的k-NN算法需要的特征權(quán)值，最終構(gòu)造分類器完成對測試集APK的測試。

數(shù)據(jù)庫模塊的設(shè)計(jì)和所有其他模塊進(jìn)行交互，負(fù)責(zé)將所有模塊的計(jì)算結(jié)果存入數(shù)據(jù)庫，還負(fù)責(zé)從數(shù)據(jù)庫中取出數(shù)據(jù)，目的是減少計(jì)算量的重復(fù)，提升算法執(zhí)行效率。本文實(shí)驗(yàn)所用到的數(shù)據(jù)表如表1所示。

續(xù)表1

5 實(shí) 驗(yàn)

本文在Ubuntu操作系統(tǒng)下進(jìn)行仿真實(shí)驗(yàn)，Ubuntu安裝在Vmware Workstation虛擬機(jī)上，主機(jī)采用Windows 7。編程實(shí)現(xiàn)語言為Python，采用APKTool工具對APK文件進(jìn)行反編譯，其命令格式為：apktool d[OPTS][apk文件路徑][反編譯輸出目錄]。

5.1 數(shù)據(jù)準(zhǔn)備

使用機(jī)器學(xué)習(xí)的方法來對APK進(jìn)行分類，在算法訓(xùn)練時(shí)，需要有足夠多的樣本集合才能確保分類器的檢出性能。本文從網(wǎng)上收集了1 251個(gè)惡意APK，1 000個(gè)正常APK作為樣本的訓(xùn)練集；收集了1 197個(gè)惡意APK，1 000個(gè)正常APK作為樣本的測試集。采用Python語言編寫程序，先反編譯APK，然后根據(jù)已有的Android API和Permission從smali文件和AndroidManifest.xml文件中提取靜態(tài)信息，并存入數(shù)據(jù)庫，其中API一共18 646條，Permission一共151條。在對訓(xùn)練集APK靜態(tài)信息進(jìn)行統(tǒng)計(jì)的基礎(chǔ)上，可以得出基準(zhǔn)API和Permission及它們的權(quán)值。取出了120個(gè)基準(zhǔn)API及其權(quán)值，部分?jǐn)?shù)據(jù)如表2所示；25個(gè)基準(zhǔn)Permission及其權(quán)值，詳細(xì)如表3所示。

表2 基準(zhǔn)API及其權(quán)值(部分?jǐn)?shù)據(jù))

續(xù)表2

表3 Permission的條件概率

續(xù)表3

根據(jù)基準(zhǔn)API和Permission將APK轉(zhuǎn)換成特征向量。APK關(guān)于API的特征向量是一個(gè)120維，關(guān)于Permission的特征向量是一個(gè)25維，每一維值為0或1的向量，0代表此維對應(yīng)的API或Permission沒有出現(xiàn)在對應(yīng)的APK中，1代表此維對應(yīng)的API或Permission出現(xiàn)在了對應(yīng)的APK中。

5.2 測試指標(biāo)

為了對實(shí)驗(yàn)結(jié)果進(jìn)行分析，從而對算法的檢測效率給出量化的結(jié)果，定義了一組測試指標(biāo)：

TP(true positive)：正常APK被正確分類為正常APK的概率，TP=Rp/Np，Rp為被正確分類的正常APK個(gè)數(shù)，Np為正常APK的個(gè)數(shù)。

TN(true negative)：惡意APK被正確分類為惡意APK的概率，TN=Rn/Nn，Rn為被正確分類的惡意APK個(gè)數(shù)，Nn惡意APK的個(gè)數(shù)。

FP(false positive)：正常APK被錯(cuò)誤分類為惡意APK的概率，F(xiàn)P=Wp/Np，Wp為正常APK被錯(cuò)誤分類為惡意APK的個(gè)數(shù)。

FN(false negaitive)：惡意APK被錯(cuò)誤分類為正常APK的概率，F(xiàn)N=Wn/Nn，Wn為惡意APK被錯(cuò)誤分類為正常APK的個(gè)數(shù)。

Accuracy：APK被正確分類的概率，Accuracy=(Rp+Rn)/(Np+Nn)。

5.3 實(shí)驗(yàn)結(jié)果與分析

表4和表5分別列出了使用基于API的特征向量和基于Permission的特征向量的傳統(tǒng)k-NN算法和改進(jìn)的k-NN算法的檢測效果。對比兩表可以看出，本文方案的檢測效果達(dá)到了一定的水平。

表4 基于傳統(tǒng)的k-NN算法的檢測效果

續(xù)表4

表5 基于改進(jìn)的k-NN算法的檢測效果

在同樣的測試集中，改進(jìn)的k-NN算法檢測方案比傳統(tǒng)的k-NN算法檢測方案更好，其準(zhǔn)確率提升11%左右。原因是實(shí)施算法之前提出的特征權(quán)值兩者有所不同，改進(jìn)的算法中實(shí)現(xiàn)了惡意APK的特征向量與正常的APK的特征向量相似度更低，兩個(gè)惡意或正常APK的特征向量相似度更高。

從改進(jìn)k-NN檢測方案來具體分析，以API為特征向量，正常APK和惡意APK的檢出率分別達(dá)到了85%和83%以上。其中，正常APK的檢出率與惡意APK的檢出率差別不大，因?yàn)樽鳛榛鶞?zhǔn)特征的API是從訓(xùn)練集的惡意樣本和正常樣本的共有API中提取出來的。對于沒有被正確分類的APK，一是因?yàn)闆]有將敏感惡意API完全覆蓋，一些惡意行為不能檢測出來；二是因?yàn)檎PK中存在著一些跟惡意APK中相似的惡意行為(例如訪問網(wǎng)絡(luò)、訪問位置信息、發(fā)送短信等)。以Permission為特征向量，正常APK和惡意APK的檢出率分別達(dá)到了87%和85%以上。檢出率整體上比以API為特征的檢出率高，這是因?yàn)锳ndroid API數(shù)量相對于Permission來說要高很多，找出的作為基準(zhǔn)的API可能存在冗余沒有去除，所以檢測效率沒有以Permission為特征的方案高。

綜上可見，本文提出的基于API的特征向量和Permission的特征向量的改進(jìn)k-NN算法的檢測方法是從Android APK中提取信息，再進(jìn)行統(tǒng)計(jì)分析，最終確定了作為基準(zhǔn)特征的API有120條，作為基準(zhǔn)特征的Permission有25條，它們在惡意APK和正常APK中使用率都高于20%。實(shí)驗(yàn)結(jié)果表明，本文方法惡意APK和正常APK的檢出率都在82%以上。

6 結(jié) 語

雖然本文方案達(dá)到了預(yù)期的實(shí)驗(yàn)效果，具備了一定的檢測Android惡意軟件的能力，但是仍有許多值得研究和改進(jìn)的地方。如作為基準(zhǔn)特征的API或Permission的選取有待改進(jìn)，在對訓(xùn)練集APK中的API或Permission進(jìn)行統(tǒng)計(jì)分析時(shí)，由于只采用了有或無的0/1方式，不能夠真實(shí)地反映出某個(gè)API或Permission在APK中的真實(shí)使用率。一個(gè)API或Permission的調(diào)用序列，能夠更真實(shí)地反映出惡意行為執(zhí)行過程，在對惡意APK中的API或Permission進(jìn)行統(tǒng)計(jì)分析時(shí)，如果能找出一些惡意行為固有的API或Permission調(diào)用序列，那么對于檢測惡意APK將具有重大意義，基于API或Permission的惡意軟件的檢出率將會(huì)有很大提高。