一種基于改進(jìn)的關(guān)聯(lián)規(guī)則挖掘算法的Android惡意軟件檢測方法?

嚴(yán) 喆 朱保平

1 引言

現(xiàn)有的惡意軟件檢測方法主要分為兩大類［1］，一類是基于特征碼的，另外一類是基于行為的?；谔卣鞔a的檢測方法主要通過判斷待檢測的軟件是否具有已知惡意軟件的特征代碼片段，這種方法對于已知惡意軟件命中率高，但是無法檢測出未知的惡意軟件。2012年11月，Google提出了將在系統(tǒng)中加入名為“application verification service”的安全特性，Google意圖通過“application verification service”來對Android市場進(jìn)行監(jiān)督。除此之外，著名的檢測工具Androguard［2］也是基于特征碼對惡意軟件進(jìn)行檢測的，它誤報(bào)率低，但是由于它是基于特征碼進(jìn)行檢測的，因此只能檢測出已知的惡意軟件，無法對未知的惡意軟件進(jìn)行檢測。

基于行為的檢測方法［3］是通過對比目標(biāo)軟件和已知的惡意軟件的行為來判斷目標(biāo)軟件是否是惡意軟件。本文主要是對基于權(quán)限特征的研究。Zhou Yajin等［4］開發(fā)了一個(gè) Android惡意軟件的檢測系統(tǒng)DroidRanger，在這個(gè)系統(tǒng)中，作者使用了兩種模式來對惡意軟件進(jìn)行檢測，其中一種模式就是基于軟件權(quán)限行為的過濾方法，它們通過總結(jié)不同惡意軟件族所申請的敏感權(quán)限組合，以此作為過濾標(biāo)準(zhǔn)來判定惡意軟件。William Enck等［5］基于Android應(yīng)用申請的權(quán)限列表開發(fā)出了Kirin系統(tǒng)，并且它們在對已有的樣本學(xué)習(xí)后，總結(jié)并制定出9條與權(quán)限相關(guān)的安全規(guī)則以此對從Android市場上下載下來的310個(gè)Android軟件進(jìn)行檢測。黃偉等［6］提出了一種基于集成分類的惡意軟件檢測方法，作者提出的方法中有一部分是在軟件權(quán)限特征上建立基分類器，并將產(chǎn)生的分類結(jié)果用于最后的集成分類模型。Zhang Y等［7］提出了VetDroid系統(tǒng)，作者從軟件中提取權(quán)限，然后利用自然語言處理技術(shù)將軟件請求的權(quán)限與軟件描述文件中描述的權(quán)限進(jìn)行對比依此來識(shí)別惡意應(yīng)用。Arp D等［8］提出了一種檢測方法，這種檢測方法是基于線性向量機(jī)實(shí)現(xiàn)的，通過對惡意軟件靜態(tài)分析，收集出軟件盡可能多的特征，包括權(quán)限特征，API調(diào)用特征，網(wǎng)絡(luò)地址特征等等。

隨著Android設(shè)備的日益增長，Android平臺(tái)惡意軟件的檢測需求也越來越大。由于Android軟件申請的各個(gè)權(quán)限體現(xiàn)著軟件的行為特點(diǎn)，一個(gè)惡意行為的產(chǎn)生需要多個(gè)權(quán)限的配合，而經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法存在著性能缺陷，直接將它運(yùn)用到挖掘軟件權(quán)限之間的關(guān)系效果不理想，針對以上問題，本文在對Eclat算法進(jìn)行改進(jìn)的基礎(chǔ)上提出了一個(gè)AEclat算法，該算法可以挖掘出惡意軟件的極大頻繁項(xiàng)集，通過與待檢測軟件進(jìn)行權(quán)限匹配度檢測來判斷該軟件是否為惡意軟件，以此為用戶提供參考依據(jù)，從而提高Android系統(tǒng)的安全性。

2 基于權(quán)限的頻繁模式挖掘算法AEclat

本文算法的主要設(shè)計(jì)思想是：Android軟件申請的權(quán)限往往會(huì)體現(xiàn)出軟件的行為特征，因此對軟件申請的權(quán)限的研究在惡意軟件的檢測中起著很重要的作用。而對單一權(quán)限的研究無法全面地反映軟件的行為，往往一個(gè)惡意行為的產(chǎn)生需要多個(gè)權(quán)限的配合，權(quán)限之間的關(guān)聯(lián)關(guān)系就能反映出軟件的行為信息。因此本文在軟件申請的權(quán)限組合中進(jìn)行權(quán)限關(guān)聯(lián)規(guī)則挖掘，從而達(dá)到對惡意軟件進(jìn)行檢測的目的。

Eclat算法［9］是一種基于深度優(yōu)先的關(guān)聯(lián)規(guī)則挖掘算法，它的數(shù)據(jù)的表現(xiàn)形式是垂直表示的，并且在Eclat算法中加入了倒排的思想，這加快了頻繁項(xiàng)集的生成速度，但是Eclat算法有著自身的局限性，并未充分利用Apriori算法中的先驗(yàn)性質(zhì)，它是根據(jù)兩個(gè)集合的并集產(chǎn)生新的候選項(xiàng)集，因此它產(chǎn)生的候選項(xiàng)集的數(shù)目會(huì)非常多，并且每一個(gè)都需要計(jì)算其支持度，這大大地降低了效率，因此直接利用Eclat算法對軟件申請的權(quán)限進(jìn)行關(guān)聯(lián)規(guī)則挖掘效率是比較低的。本文在對Eclat算法進(jìn)行優(yōu)化的基礎(chǔ)上結(jié)合軟件的權(quán)限行為特征設(shè)計(jì)了基于權(quán)限的頻繁模式挖掘算法AEclat，該算法以從軟件提取出的權(quán)限作為數(shù)據(jù)集，根據(jù)軟件申請的權(quán)限之間的關(guān)系，通過得到極大頻繁項(xiàng)集，進(jìn)一步構(gòu)建權(quán)限關(guān)系特征庫，依此進(jìn)行Android惡意軟件的檢測。

本文是在49個(gè)惡意軟件族上分別運(yùn)用AEclat算法進(jìn)行關(guān)聯(lián)規(guī)則挖掘，并不是將全部應(yīng)用混在一起進(jìn)行挖掘。因?yàn)椴煌膼阂廛浖逵兄约旱奶攸c(diǎn)，分開進(jìn)行檢測更能提高檢測的準(zhǔn)確性。

本文先對涉及的49個(gè)惡意軟件族的權(quán)限數(shù)據(jù)庫進(jìn)行預(yù)處理。對于每一族應(yīng)用，都采取以下幾個(gè)步驟：

1）提取出軟件申請的權(quán)限，分別構(gòu)成對應(yīng)族的權(quán)限數(shù)據(jù)庫；

2）統(tǒng)計(jì)出軟件使用權(quán)限的次數(shù)，在權(quán)限數(shù)據(jù)庫中刪除掉該族軟件很少申請的權(quán)限；

3）找出該族軟件都申請的權(quán)限；

4）將已經(jīng)預(yù)處理后的權(quán)限數(shù)據(jù)庫運(yùn)用AEclat算法產(chǎn)生所有頻繁項(xiàng)集，找出長度最大的頻繁項(xiàng)集作為極大頻繁項(xiàng)集；

5）把3）找出的權(quán)限添加進(jìn)4）得到的極大頻繁項(xiàng)集中，作為最終的極大頻繁項(xiàng)集。

具體算法如下：

算法1 AEclat算法

輸入：

DataSeti：49個(gè)惡意軟件族，其中i=1，2…49。

minsup：最小支持度閾值

輸出：極大頻繁項(xiàng)集數(shù)據(jù)庫DataSet_Permissions；

1）for（i=0；i＜49；i++）｛

2） get Lcommon；//得到該族所有軟件都申請的權(quán)限；

3） DataSeti=delete（Lcommon） ；//在原有的數(shù)據(jù)庫中刪除掉Lcommon；

4） DataSeti=delete（Lrare）； //刪除掉所有軟件都很少使用的權(quán)限；

5）DataSeti=adjust（DataSeti）；//按照字母表的順序?qū)ata-Seti中的權(quán)限進(jìn)行排序

//調(diào)整；

6） L=frequently_permission_set（DataSeti，minsup）；//得 到DataSeti的頻繁項(xiàng)集；

7） get Li；//在L中選取長度最大的頻繁項(xiàng)集作為極大頻繁項(xiàng)集Li；

8） 將Lcommon增加到Li中；

9） 將Li增加至DataSet_Permissions中；

10）｝

11）return DataSet_Permissions；

Procedure frequently_permission_set（DataSeti，minsup）

1）第一次掃描事務(wù)數(shù)據(jù)庫DataSeti，得到頻繁一項(xiàng)集，L=L∪L1，L初始為φ；

2）二次掃描事務(wù)數(shù)據(jù)庫DataSeti，得到頻繁2項(xiàng)集，L=L∪L2，設(shè)臨時(shí)候選集Li，初始時(shí)Li=L2；

3）repeat

4） for each tj∈ Li｛

5） for each tk∈Li&k＜j｛

6） M=tj∪tk；

7） if（M的所有含有n-1項(xiàng)的子集在L中都可以找到）｛//n=M中元素個(gè)數(shù)

8） Tidsets（M）=Tidsets（tj）∩ Tidsets（tk）；//Tidsets（M）為M的垂直數(shù)據(jù)表示；

9） if（|Tidsets（M）|＞=minsup）｛

10） L=L∪M，X=X∪M，初始時(shí)X=φ；｝

11） else跳出循環(huán)，轉(zhuǎn)入15）；//由于元素的有序性，

后面的頻繁項(xiàng)集均//不必連接

12） ｝

13）｝

14）｝

15）Li=X；X=φ；16）until Li為φ。

3 基于AEclat算法的Android惡意軟件檢測方法

3.1 相關(guān)概念

定義1 權(quán)限匹配度。待檢測軟件申請的權(quán)限與對應(yīng)惡意軟件族極大頻繁項(xiàng)集中權(quán)限匹配個(gè)數(shù)占對應(yīng)惡意軟件族的極大頻繁項(xiàng)集的權(quán)限總數(shù)的百分比叫做權(quán)限匹配度。它用于衡量待檢測軟件是否屬于某一惡意軟件族。

式中：Lm表示權(quán)限匹配度，Nf表示待檢測軟件申請的權(quán)限與對應(yīng)檢測族極大頻繁項(xiàng)集中權(quán)限匹配個(gè)數(shù)，Ntotal表示對應(yīng)檢測族的極大頻繁項(xiàng)集的權(quán)限總數(shù)。在本實(shí)驗(yàn)中，選取匹配度閾值為0.95。

定義2 命中率。對于惡意軟件，惡意軟件識(shí)別正確的數(shù)目占全部軟件惡意軟件的百分比叫做命中率。式中：Hitrate表示命中率，TP表示惡意軟件識(shí)別正確的數(shù)目，F(xiàn)P表示惡意軟件被識(shí)別為非惡意軟件的數(shù)目。

定義3 誤報(bào)率。對于非惡意軟件，非惡意軟件被正確識(shí)別的數(shù)目占全部非惡意軟件的百分比叫做誤報(bào)率。

式中：Falsealarmrate代表誤報(bào)率，TN代表非惡意軟件被正確識(shí)別的數(shù)目，F(xiàn)N代表非惡意軟件被識(shí)別為惡意軟件的數(shù)目。

3.2 基于AEclat算法的Android惡意軟件檢測方法檢測流程

本文在前面介紹了基于權(quán)限的頻繁模式挖掘算法AEclat，本節(jié)將以AEclat算法為核心，介紹一種基于AEclat算法的Android惡意軟件檢測方法，該方法流程如圖1所示。首先構(gòu)建樣本庫，該樣本庫包含了49個(gè)惡意軟件族，然后對這些惡意軟件族進(jìn)行靜態(tài)解析，得到軟件申請的權(quán)限，分別構(gòu)建各族權(quán)限數(shù)據(jù)庫，在各族數(shù)據(jù)庫上分別運(yùn)用AEclat算法進(jìn)行挖掘，通過得到各族極大頻繁項(xiàng)集，構(gòu)建出權(quán)限關(guān)系特征庫，最后，輸入待檢測軟件，使其匹配權(quán)限關(guān)系特征庫從而得到統(tǒng)計(jì)結(jié)果。

基于此流程圖，下面給出基于該檢測方法的詳細(xì)說明。

構(gòu)建訓(xùn)練樣本庫：本文采用的用于訓(xùn)練的惡意軟件樣本是文獻(xiàn)［10］中的樣本，這個(gè)樣本是由49個(gè)惡意軟件家族的1260個(gè)惡意軟件組成；

靜態(tài)解析app：對各族每個(gè)軟件樣本利用apktool工具進(jìn)行反編譯，獲取各個(gè)軟件的AndroidManifest.xml文件，從AndroidManifest.xml文件中獲取各軟件的申請權(quán)限列表；

構(gòu)建權(quán)限數(shù)據(jù)庫：對于某一族惡意軟件，該族每個(gè)軟件申請的權(quán)限作為一行，初步得到該族權(quán)限數(shù)據(jù)庫。然后利用第2節(jié)所述的數(shù)據(jù)庫預(yù)處理方法，構(gòu)建權(quán)限數(shù)據(jù)庫，作為AEclat算法的輸入。

AEclat算法處理：使用第2節(jié)所述的算法挖掘軟件權(quán)限之間的關(guān)聯(lián)性，得到各族軟件的極大頻繁項(xiàng)集。

構(gòu)建權(quán)限關(guān)系特征庫：權(quán)限關(guān)系特征庫的每一行為一族的極大頻繁項(xiàng)集，該特征庫用于匹配待檢測軟件。

匹配檢測：輸入待檢測軟件，提取出其申請的權(quán)限信息，然后與構(gòu)建好的權(quán)限關(guān)系特征庫進(jìn)行匹配，計(jì)算出權(quán)限匹配度，匹配度大于設(shè)置的閾值即認(rèn)為該軟件屬于該族惡意軟件。

統(tǒng)計(jì)結(jié)果：對于惡意軟件，計(jì)算命中率，對于非惡意軟件，計(jì)算誤報(bào)率。

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

本文通過設(shè)計(jì)多個(gè)實(shí)驗(yàn)來對提出的算法進(jìn)行有效性和正確性檢驗(yàn)，并與其他Android惡意軟件檢測方法進(jìn)行對比，實(shí)驗(yàn)證明本文提出的方法效果更好。本實(shí)驗(yàn)的硬件環(huán)境是Intel（R）Pentium（R）CPUG3240，內(nèi)存6G，操作系統(tǒng)是Windows 7。前文所述的爬蟲程序以及格式化處理程序是用python實(shí)現(xiàn)的，AEclact算法實(shí)現(xiàn)是用Java完成的。

本文采用的測試樣本由3部分組成。第一部分惡意軟件樣本是文獻(xiàn)［10］中的樣本，它們?nèi)∽訟ndroid Malware Project，這個(gè)樣本是由49個(gè)惡意軟件家族的1260個(gè)惡意軟件組成。第二部分非惡意軟件樣本是從Google play store上爬蟲下來的并經(jīng)過殺毒軟件檢測后篩選出來的1200個(gè)軟件。最后一部分惡意軟件樣本是從Contagio Mobile中隨機(jī)獲取的200個(gè)惡意軟件。本文先對包括49個(gè)家族的1260個(gè)惡意軟件樣本通過設(shè)置不同的最小支持度閾值minsup反復(fù)試驗(yàn)，對比考慮多次試驗(yàn)的命中率Hitrate，選取適當(dāng)?shù)膍insup得到49族惡意軟件的極大頻繁項(xiàng)集。由于篇幅有限，表1展示了我們得到的一部分惡意軟件家族的極大頻繁項(xiàng)集。

使用本文所述的方法對Android Malware Project惡意軟件樣本進(jìn)行檢測，共檢測出1078個(gè)惡意軟件，得到的命中率為85.56%，具體結(jié)果見表2。對1200個(gè)非惡意軟件檢測，將81個(gè)軟件誤報(bào)為惡意軟件，誤報(bào)率為6.75%。對從Contagio Mobile中隨機(jī)獲取的200個(gè)惡意軟件進(jìn)行檢測，共檢測出惡意軟件104個(gè)，命中率為51%。

表2 Android Malware Project樣本不同系統(tǒng)檢測結(jié)果表

4.1 關(guān)于提取的軟件敏感權(quán)限的對比

DroidRanger［4］是 ZHOU Y J等開發(fā)的一個(gè)基于Android惡意軟件的檢測系統(tǒng)，他們提出了一個(gè)基于權(quán)限的過濾機(jī)制，總結(jié)出了9個(gè)惡意軟件族所使用的敏感權(quán)限信息，并基于此來過濾可疑的惡意軟件。表1是本文算法得到的權(quán)限項(xiàng)集和DroidRanger的對比。從對比中可以看出，DroidRanger提出的敏感權(quán)限相當(dāng)有限，直接使用它進(jìn)行惡意軟件的判別將會(huì)導(dǎo)致準(zhǔn)確率很低，而本文算法得出的極大頻繁項(xiàng)集則是可以直接用于惡意軟件的檢測。

4.2 關(guān)于軟件檢測結(jié)果的對比

Androguard［2］是一個(gè)用 python 實(shí)現(xiàn)的靜態(tài)的自動(dòng)化檢測程序，它提供了一系列的Apk以及odex，dex，arsc等分析處理功能。由于Androguard是基于python實(shí)現(xiàn)的，因此只要能運(yùn)行python的系統(tǒng)，不論是Linux、Windows還是Mac都能運(yùn)行Androguard。本文使用的是Ubuntu鏡像ARE默認(rèn)安裝的版本。實(shí)驗(yàn)結(jié)果顯示，對于Android Malware Project樣本，檢測出863個(gè)惡意軟件，其命中率為68.49%，具體結(jié)果見表2。對1200個(gè)非惡意軟件檢測的誤報(bào)率為0%。對從Contagio Mobile中隨機(jī)獲取的200個(gè)惡意軟件進(jìn)行檢測的命中率為0%。

Google的“application verification service”啟動(dòng)服務(wù)后，當(dāng)軟件被安裝到手機(jī)上時(shí)，軟件的名稱，SHAI值，版本等信息就會(huì)被推送到Google云上并進(jìn)行檢測，如果此軟件有隱患，那么就會(huì)提示用戶是否安裝，如果檢測到此軟件是危險(xiǎn)的軟件，那么就會(huì)直接阻止用戶安裝。實(shí)驗(yàn)結(jié)果顯示，對于Android Malware Project樣本，檢測出193個(gè)惡意軟件，其命中率為15.32%，具體結(jié)果見表2。對1200個(gè)非惡意軟件檢測的誤報(bào)率為0%。對從Contagio Mobile中隨機(jī)獲取的200個(gè)惡意軟件進(jìn)行檢測的命中率為0%。

Kirin［5］是Enck等提出的基于權(quán)限的Android惡意軟件檢測方法。實(shí)驗(yàn)結(jié)果顯示，對于Android Malware Project樣本，檢測出36個(gè)惡意軟件，其命中率為2.86%，具體結(jié)果見表2。對1200個(gè)非惡意軟件檢測，系統(tǒng)將106個(gè)應(yīng)用誤報(bào)為惡意軟件，其誤報(bào)率為8.83%。對從Contagio Mobile中隨機(jī)獲取的200個(gè)惡意軟件進(jìn)行檢測，檢測出4個(gè)惡意軟件，命中率為2%。

綜上所述，對于Android Malware Project樣本，明顯本方法的命中率比其他三種方法高。對1200個(gè)非惡意軟件，本文方法的誤報(bào)率低于Kirin，雖然高于Androguard和Google，但是因?yàn)楹髢烧咧荒茏R(shí)別已知軟件，所以誤報(bào)率為0，并且它們對于未知惡意軟件的命中率為0，而本文方法相應(yīng)的命中率則為51%。本文方法的研究重點(diǎn)是檢測未知軟件，因此在提高對未知應(yīng)用的命中率的前提下，犧牲一定的誤報(bào)率是可以接受的。而雖然Kirin也可以檢測出一部分的未知惡意軟件，但顯然其命中率不如本文方法。

5 結(jié)語

針對Android平臺(tái)惡意軟件的檢測需求的上升和現(xiàn)有的關(guān)聯(lián)規(guī)則挖掘算法的效率較低，不能直接用于惡意軟件的檢測的問題，本文提出了一種基于權(quán)限關(guān)聯(lián)規(guī)則的Android惡意軟件檢測方法。主要工作如下：

1）在對已有的關(guān)聯(lián)規(guī)則挖掘算法Eclat算法進(jìn)行優(yōu)化的基礎(chǔ)之上提出了基于權(quán)限的頻繁模式挖掘算法AEclat；

2）提出了一種基于AEclat算法的Android惡意軟件檢測方法；

3）通過與DroidRanger系統(tǒng)的對比，實(shí)驗(yàn)證明本文提出的方法提取出的敏感權(quán)限更加全面，能夠直接用于惡意軟件的檢測。

4）通過與Google、Kirin和Androguard惡意軟件檢測系統(tǒng)進(jìn)行對比，實(shí)驗(yàn)分析說明本文提出的方法更好，具有一定的可行性。

［1］Anastasia S，Dennis G.Review of the mobile malware detection approaches［C］//Proceedings of the 23rd International Conference on Parallel，Distributed and Network-Based Processing.Washington，USA：IEEE Computer Society，2015：600-603.

［2］ Androguard ［EB/OL］.http：//code.google.com/p/androguard/，2013.

［3］Arp D，Spreitzenbarth M，Hübner M，et al.DREBIN：effective and explainable detection of Android malware in your pocket［C］//NDSS，2014：1-2.

［4］Zhou Yajin，Wang Zhi，Zhou Wu，et al.Hey，you，get off of my market：detecting malicious Apps in official and alternative Android markets［C］//Proceedings of the 19th Annual Network&Distributed System Security Symposium.Washington，USA：Internet Society，2012：123-129.

［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 CCS'09，Chicago，IL，USA，2009：235-245.

［6］黃偉，陳昊，郭雅娟，等.基于集成分類的惡意應(yīng)用檢測方法［J］.南京理工大學(xué)學(xué)報(bào)，2016，40（1）：35-40.

HUANGWei，CHENHao，GUOYajuan，et al.Mobile malware detection approach using ensemble classification［J］.Journal of Nanjing University of Science and Technology，2016，40（1）：35-40.

［7］Zhang Yuan，Yang Min，Yang Zhemin，et al.Permission use analysis for vetting undesirable behaviors in Android Apps［J］.IEEE Transactions on Information Forensics and Security，2014，9（11）：1828-1842.

［8］Mas'Ud M Z，Sahib S，Abdollah M F，et al.Analysis of features selection and machine learning classifier in Android malware detection［C］//Proceedings of IEEE International Conference on Information Science and Applications.Washington，USA：IEEE Computer Society，2014：1-5.

［9］Yu Xiaomei，Wang H.Improvement of Eclat Algorithm Based on Support in Frequent Itemset Mining［J］.Journal of Computers，2014，9（9）：12-15.

［10］Zhou Yajin，Jiang Xuxian.Dissecting Android malware：characterization and evolution［C］//Proceedings of the 33rd IEEE Symposium on Security and Privacy，Oakland，USA，2012：95-109.