劉啟川，覃仁超，劉 玲，卜得慶，袁 平

(西南科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，四川 綿陽 621010)

0 引 言

目前，Android惡意應(yīng)用檢測方法主要集中在提取不同的特征和機(jī)器學(xué)習(xí)算法改進(jìn)上，通過提取出應(yīng)用中的API[1]、權(quán)限[2,3]、調(diào)用關(guān)系[4]和IP地址[5]等特征，并將這些特征使用樸素貝葉斯(Naive Bayesian，NB)、決策樹(decision tree)、支持向量機(jī)(support vector machine，SVM)和K最近鄰(k-nearest neighbors，KNN)等不同的機(jī)器學(xué)習(xí)算法構(gòu)造分類器進(jìn)行分類[5,6]。但多特征包涵大量冗余信息，文獻(xiàn)[7]指出更多的特征可能導(dǎo)致更差的分類性能。為了得到更好的檢測效果，消除冗余特征，特征選擇算法已被大量用于Android惡意軟件檢測方法中[8]。

在Android惡意應(yīng)用檢測中，使用不同的特征選擇算法已經(jīng)成為不少學(xué)者提高檢測效率的研究方法，當(dāng)前主要方法為卡方檢驗(yàn)(Chi-squared test，CHI)、信息增益法(information gain，IG)和粒子群優(yōu)化算法等[9,10]，其特征選擇算法大多借鑒于其它領(lǐng)域，忽略了Android應(yīng)用數(shù)據(jù)集特征的分布特點(diǎn)，并未通過量化特征對分類效果的貢獻(xiàn)程度來選擇特征。因此，本文提出了一種基于特征貢獻(xiàn)度(feature contribution，F(xiàn)C)的特征選擇算法，該算法通過計(jì)算應(yīng)用的權(quán)限、敏感方法、組件信息和硬件信息等基本特征的貢獻(xiàn)度，能選擇出對分類最有幫助的特征進(jìn)行惡意應(yīng)用檢測。

1 特征貢獻(xiàn)度

1.1 卡方檢驗(yàn)和信息增益

卡方檢驗(yàn)是統(tǒng)計(jì)學(xué)中一種用于獨(dú)立性檢驗(yàn)的假設(shè)檢驗(yàn)方法，即驗(yàn)證兩個(gè)變量是否相互度量，其數(shù)學(xué)公式如式(1)所示

(1)

而信息增益算法是信息論中的重要概念，其衡量標(biāo)準(zhǔn)是通過量化特征為分類系統(tǒng)帶來多少信息，越重要的特征帶來的信息越多，信息增益也就越大。其數(shù)學(xué)公式如式(2)所示

IG(fi)=H(C)-H(C|fi)

(2)

其中，H(C) 表示整個(gè)系統(tǒng)的信息熵，H(C|fi) 是在給定特征fi下的條件熵，此時(shí)IG(fi) 即為信息增益。其中，信息增益算法更加偏向選擇在惡意和良性應(yīng)用中廣泛分布的特征，因?yàn)檫@種特征具有更大的信息增益。

上述兩種傳統(tǒng)特征選擇算法都不適用于惡意應(yīng)用檢測領(lǐng)域，因此針對惡意應(yīng)用檢測中的特征選擇算法十分必要。

1.2 特征貢獻(xiàn)度計(jì)算

貢獻(xiàn)度通常用于衡量某一因素對整體的貢獻(xiàn)程度。在Android應(yīng)用特征數(shù)據(jù)集特征的分布有著如下特點(diǎn)：

(1)良性應(yīng)用中使用過的特征數(shù)量通常大于在惡意應(yīng)用中使用過的特征數(shù)量；

(2)大部分特征都是非典型特征，有很大一部分特征的存在對分類沒有幫助；

(3)在良性應(yīng)用中頻繁使用的特征和惡意應(yīng)用中頻繁使用的特征有著明顯的區(qū)別。

因此，本文根據(jù)上述的特點(diǎn)將特征貢獻(xiàn)度定義為單個(gè)特征對分類的貢獻(xiàn)程度。通過計(jì)算特征的貢獻(xiàn)度對特征進(jìn)行選擇，選出的特征在分類時(shí)越能表征樣本類間的特性和樣本類內(nèi)的特性，則該特征就對樣本的分類貢獻(xiàn)越大。故有定義如下：

定義1 類間貢獻(xiàn)度：類間貢獻(xiàn)度表示特征項(xiàng)在類間分布中的貢獻(xiàn)程度，特征項(xiàng)在類間分布越不平衡，其貢獻(xiàn)程度越大，記作FCout。

FCout(fi) 計(jì)算公式如式(3)所示

(3)

定義2 類內(nèi)貢獻(xiàn)度：類內(nèi)貢獻(xiàn)度反應(yīng)了特征項(xiàng)在類內(nèi)中的貢獻(xiàn)程度，特征項(xiàng)在類內(nèi)出現(xiàn)頻率越高，其貢獻(xiàn)程度越大，記作FCin。

FCin(fi) 計(jì)算公式如式(4)所示

(4)

其中，num(sam(fi)all,Cj) 表示j類中包含fi特征的樣本數(shù)量，num(samall,Cj) 表示j類中所有樣本數(shù)，num(fall,Call-Ci) 表示除了i類中特征的數(shù)量，num(fall,Call) 表示所有特征的數(shù)量。公式的主要目的是為了將類別中的特征頻率歸一化后求得類內(nèi)貢獻(xiàn)度。

定義3 特征貢獻(xiàn)度：fi特征的特征貢獻(xiàn)度指的是對fi特征對分類的貢獻(xiàn)程度，用FC(fi) 表示，綜合式(3)和式(4)，F(xiàn)C(fi) 如式(5)所示

FC(fi)=FCout(fi)×FCin(fi)

(5)

由式(3)、式(4)和式(5)可得：

(1)當(dāng)特征項(xiàng)只在一個(gè)類別中出現(xiàn)時(shí)，其分類能力最強(qiáng)，此時(shí)FCout最大為1；當(dāng)特征項(xiàng)在各個(gè)類別中均勻分布時(shí)，其分類能力最弱，此時(shí)FCout最小為0。顯然，F(xiàn)Cout與分類能力成正比。

(2)當(dāng)特征項(xiàng)在類中出現(xiàn)頻率越高，其越能代表這個(gè)類，F(xiàn)Cin也越大；當(dāng)特征項(xiàng)在類別中出現(xiàn)的頻率越低，其越不具有代表性，F(xiàn)Cin也越小。顯然，F(xiàn)Cin與代表性成正比。

本文提出的貢獻(xiàn)度算法不僅考慮到了特征在類中的出現(xiàn)頻率，還考慮到了特征在類間的分布情況。通過特征貢獻(xiàn)度式(5)的運(yùn)算后的FC(fi) 的值越大，就越能說明特征fi的貢獻(xiàn)度越大，其作用也越重要。

2 系統(tǒng)的架構(gòu)與實(shí)現(xiàn)

2.1 模型設(shè)計(jì)

本文的惡意應(yīng)用檢測系統(tǒng)主要包括3個(gè)部分：特征提取模塊、特征選擇模塊和分類模塊，其模型如圖1所示。其中，特征提取模塊主要作用是將應(yīng)用進(jìn)行逆向，并提取權(quán)限、敏感方法、組件信息和硬件調(diào)用信息特征，將其向量化，生成特征向量集合；特征選擇模塊則是對特征向量集合中的特征使用基于特征貢獻(xiàn)度的算法進(jìn)行貢獻(xiàn)度分配，選擇出典型特征數(shù)據(jù)集；分類模塊則是將前面構(gòu)建好的數(shù)據(jù)集運(yùn)用機(jī)器學(xué)習(xí)算法，訓(xùn)練分類器進(jìn)行預(yù)測和分析。

圖1 系統(tǒng)總體設(shè)計(jì)

2.2 特征提取模塊

特征提取模塊中需要解決的首要問題是確定Android應(yīng)用中那些特征與惡意應(yīng)用檢測緊密相關(guān)。大致思想是通過逆向Android應(yīng)用軟件，提取與其功能和行為相對應(yīng)的所有特征，提取的特征可以分為4個(gè)不同的類別：

(1)權(quán)限：Android應(yīng)用程序必須根據(jù)其所提供的功能明確聲明它們將使用哪些權(quán)限。例如，某應(yīng)用程序聲明了SEND_SMS和READ_CONTACTS權(quán)限，該程序就具有通過短信泄露手機(jī)聯(lián)系人的威脅;若聲明了SEND_SMS和READ_SMS，該程序就具有通過短信泄露用戶短信的威脅[2]。因此，可以使用權(quán)限功能來對良性應(yīng)用程序和惡意應(yīng)用程序進(jìn)行分類。

(2)敏感方法：僅依賴Android權(quán)限管理系統(tǒng)不能完整的體現(xiàn)應(yīng)用的功能和行為，部分惡意軟件可以繞過權(quán)限控制，但是調(diào)用API卻無法隱藏，比如獲取設(shè)備ID需要調(diào)用getDeviceId()方法，發(fā)送短信需要調(diào)用sendTextMessage()方法。顯然，增加與Android系統(tǒng)相關(guān)的敏感方法，可以幫助惡意應(yīng)用檢測。

(3)組件信息：Android應(yīng)用程序通常由活動(dòng)(Activity)、內(nèi)容提供器(Content Provider)服務(wù)(Service)和廣播接收器(Broadcast Receiver)構(gòu)成。惡意代碼行為的實(shí)現(xiàn)需要通過組件的形式表達(dá)，在某種程度上說，Android應(yīng)用程序組件信息在可以表示其運(yùn)行時(shí)的行為，并且同一家族的惡意代碼，其組件有一定的相似性。因此可以選擇組件信息對應(yīng)用程序分類。

(4)硬件調(diào)用信息：在Android系統(tǒng)中，要使用硬件除了聲明相應(yīng)的權(quán)限以外還要使用與硬件相關(guān)的類。例如在調(diào)用與wifi相關(guān)的方法時(shí)，就必然使用到Android.hardware.wifi類。因此，硬件調(diào)用信息也可以作為分類的信息之一。

特征提取模塊中另一個(gè)需要解決的問題是如何提取和表示這4種具有代表性的特征，本文主要通過以下步驟：

(1)對樣本庫中APK文件進(jìn)行逆向得到大量xml或smali文件，如AndroidManifest.xml和Class.dex文件。

(2)遍歷AndroidManifest.xml文件和包含源代碼的.Smali文件，可以獲得部分應(yīng)用程序的基本信息，如權(quán)限信息、四大組件信息和與Android相關(guān)的API調(diào)用信息等。

(3)對樣本應(yīng)用數(shù)據(jù)進(jìn)行上述處理，生成了一個(gè)包含24 605特征的特征集合，其所對應(yīng)的數(shù)學(xué)表達(dá)為F=(f1,f2,…,fn,label)， 其中n為特征數(shù)量，label為特征的標(biāo)簽。

(4)將每個(gè)應(yīng)用逆向后的特征信息與特征庫比對，有該特征記為1，沒有記為0。數(shù)學(xué)表示形如：si=(1,0,…,0,y)， 當(dāng)應(yīng)用為良性應(yīng)用時(shí)，y為0，否則y為1。

最終，應(yīng)用數(shù)據(jù)集變?yōu)橐粋€(gè)包含0、1的信息矩陣S=(s1,s2,…,sn)T， 其中si表示i應(yīng)用的特征向量，實(shí)現(xiàn)了數(shù)據(jù)集的矩陣化。

2.3 特征選擇模塊

樣本集通過特征提取器提取后，提取出了24 605個(gè)特征。但是其中大部分特征對于分類都不具有幫助，只有少部分特征可以用于對應(yīng)用進(jìn)行分類。在特征選擇模塊中，首先，信息矩陣通過方差檢測，消除了全為1或者全為0的特征。隨后，通過設(shè)置特征貢獻(xiàn)度的最小值選擇方式選擇典型特征，形成了一個(gè)只有典型特征的特征矩陣S′=(s′1,s′2,…,s′n)T。

如表1所示，與短信相關(guān)的特征能夠?qū)阂鈶?yīng)用分類有著更大的貢獻(xiàn)。某些特征(如：INTERNET權(quán)限)在惡意應(yīng)用和良性應(yīng)用中都被大量使用，這種特征不具有區(qū)分度；又比如，某些特征(如：android.hardware.screen.portrait硬件信息)只有很少的應(yīng)用使用，這種特征不具有代表性。

表1 貢獻(xiàn)度top5特征

2.4 分類模塊

機(jī)器學(xué)習(xí)算法已經(jīng)廣泛應(yīng)用于許多領(lǐng)域，如文本分類、圖像識別和惡意應(yīng)用檢測等。首先，分類模塊將通過特征選擇模塊后生成的矩陣S′作為Android惡意應(yīng)用檢測數(shù)據(jù)集輸入。隨后，選取了幾種常見的機(jī)器學(xué)習(xí)算法如：NB、SVM，KNN和J48對數(shù)據(jù)集進(jìn)行訓(xùn)練和預(yù)測。最后，輸出相應(yīng)的評估結(jié)果等詳細(xì)信息，以便選取出最適合的分類器。

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

為了評估基于貢獻(xiàn)度的特征選擇算法的效果，本文先進(jìn)行了多次實(shí)驗(yàn)以選擇出最好的機(jī)器學(xué)習(xí)分類算法，再與其它兩種特征選擇算法進(jìn)行比較。實(shí)驗(yàn)所用原始數(shù)據(jù)集包含2306個(gè)應(yīng)用程序，其中50%是惡意應(yīng)用，另外50%是良性應(yīng)用程序。惡意應(yīng)用是從https://virusshare.com/[11]中收集的，良性應(yīng)用是從Google Play，小米應(yīng)用商店等應(yīng)用市場上下載得到的，并使用Virus Total網(wǎng)站進(jìn)行掃描，以確保它們都不是惡意應(yīng)用。本文使用的機(jī)器學(xué)習(xí)分類算法是通過機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘工具Weka實(shí)現(xiàn)和驗(yàn)證的，驗(yàn)證方式采用了十折交叉驗(yàn)證。

3.1 實(shí)驗(yàn)分析

為了找到合適的分類算法，本文比較了NB、SVM、KNN和J48這幾種常見的分類算法的性能。通過準(zhǔn)確率(Accuracy)和召回率(Recall)對分類效果進(jìn)行評價(jià)，數(shù)學(xué)公式如式(6)、式(7)所示

(6)

(7)

其中，TP、FP、FN和TN分別指的是分類正確的正例(TP)、分類錯(cuò)誤的正例(FP)、分類錯(cuò)誤的負(fù)例(FN)和分類正確的負(fù)例(TN)的數(shù)量。

本文的特征貢獻(xiàn)度閾值分別設(shè)定為0.2，0.18，0.16，0.14和0.1，分別選擇出來19，34，119，316和1342個(gè)特征，之后使用上述4種算法在典型特征上構(gòu)建分類器。

從表2可以看出，首先，隨著典型特征數(shù)量的增加，除了NB以外的3種算法的準(zhǔn)確度和召回率都有所提高。其次，在這些算法中，SVM和KNN可以在特征變化時(shí)始終達(dá)到較高的精度，最好達(dá)到了96.1%的準(zhǔn)確率和召回率，甚至比使用了全部特征的準(zhǔn)確率和召回率都要高。再次，除了NB算法外的其它算法的召回與準(zhǔn)確率幾乎相同，這意味著特征選擇后的特征可以等同地分類惡意應(yīng)用和良性應(yīng)用。最后，可以看到在NB中，隨著特征的增多，其準(zhǔn)確率和召回率反而下降。這是因?yàn)樨惾~斯算法要求特征具有嚴(yán)格的獨(dú)立性。舉例來說，當(dāng)SEND_SMS這個(gè)權(quán)限特征的特征貢獻(xiàn)度高時(shí)候，與其相關(guān)的敏感API的特征貢獻(xiàn)度也很可能比較高，此時(shí)選出來的特征相關(guān)性較強(qiáng)，反而影響NB的分類效果。

3.2 實(shí)驗(yàn)對比

為了評估特征選擇的性能，本文比較了卡方檢驗(yàn)、信息增益和本文提出的特征選擇算法。由表2可知SVM和KNN算法有著較好的分類效果，本文選擇了前19，34，119，316和1342個(gè)特征并且分別構(gòu)建了基于KNN和SVM的檢測模型，結(jié)果如圖2所示，其中圖2(a)和圖2(b)表示不同特征選擇算法在SVM分類器下的準(zhǔn)確率和召回率。圖2(c)和圖2(d)表示不同特征選擇算法在KNN分類器下的準(zhǔn)確率和召回率。

表2 不同數(shù)量的特征對不同分類器的比較

圖2 不同特征選擇算法在不同分類器的準(zhǔn)確率和召回率

由圖2可知，無論哪種特征選擇算法，隨著被選擇的特征數(shù)量越多，SVM和KNN分類器的準(zhǔn)確率和召回率總體都呈上升趨勢。而本文提出的特征選擇算法在準(zhǔn)確率和召回率方面明顯優(yōu)于其它兩種算法，尤其是在選擇了較少特征的時(shí)候?？梢缘玫剑夯谪暙I(xiàn)度的特征選擇算法可以在選擇更少的特征的情況下，達(dá)到比傳統(tǒng)特征選擇算法更優(yōu)異的效果。

4 結(jié)束語

本文根據(jù)應(yīng)用數(shù)據(jù)集中特征的分布特性提出了基于特征貢獻(xiàn)度的特征選擇算法。實(shí)驗(yàn)結(jié)果表明：

(1)本文的特征選擇算法適合惡意應(yīng)用檢測數(shù)據(jù)集，所選擇的特征明顯好于傳統(tǒng)的特征選擇算法選擇的特征，對于惡意應(yīng)用檢測是有效和可靠的。

(2)算法選擇的特征在分類器中的準(zhǔn)確率和召回率最高可達(dá)到96.1%，且準(zhǔn)確和召回率十分接近，具有優(yōu)異的檢測效果。

(3)相比與CHI和IG算法，該算法可以在較少特征的情況下達(dá)到理想的檢測效果，能大大提高檢測的效率。

下一步的工作中，將從以下幾個(gè)方面拓展本文的研究：首先，對特征選擇算法進(jìn)行改進(jìn)，例如使其自適應(yīng)的選擇閾值，而不用人工的設(shè)置閾值。其次可以對特征選擇算法拓展到對惡意應(yīng)用家族進(jìn)行分類，針對不同類型的惡意應(yīng)用(如：流氓行為、資費(fèi)消耗、信息竊取等)進(jìn)行選擇典型特征，提高算法的應(yīng)用范圍。