基于增量學(xué)習(xí)SVM的Android惡意應(yīng)用檢測(cè)方法*

熊祖濤，王忠文

(安慶職業(yè)技術(shù)學(xué)院 電子信息系，安徽 安慶 246003)

?

基于增量學(xué)習(xí)SVM的Android惡意應(yīng)用檢測(cè)方法*

熊祖濤，王忠文

(安慶職業(yè)技術(shù)學(xué)院 電子信息系，安徽 安慶 246003)

摘要:針對(duì)傳統(tǒng)Android惡意應(yīng)用檢測(cè)方法在處理大規(guī)模樣本時(shí)存在的訓(xùn)練時(shí)間長(zhǎng)、存儲(chǔ)空間消耗大的問題，提出一種基于增量學(xué)習(xí)SVM的Android惡意應(yīng)用檢測(cè)方法.該方法提取Android應(yīng)用的權(quán)限申請(qǐng)和API函數(shù)調(diào)用特征，利用增量學(xué)習(xí)SVM理論將訓(xùn)練樣本集隨機(jī)劃分為初始樣本集和若干個(gè)增量樣本集，利用循環(huán)迭代方法訓(xùn)練SVM分類器，每次新的訓(xùn)練僅保留上一輪訓(xùn)練得到的支持向量集并合并到新增樣本集中，舍棄大量對(duì)分類結(jié)果不產(chǎn)生影響的樣本以提高分類器學(xué)習(xí)效率，同時(shí)產(chǎn)生新的支持向量集，并最終得到一個(gè)高精度的SVM分類器.通過將增量學(xué)習(xí)SVM算法與常規(guī)SVM算法進(jìn)行對(duì)比實(shí)驗(yàn)，結(jié)果表明，該算法可以有效降低分類器學(xué)習(xí)時(shí)間，減少樣本存儲(chǔ)的空間占用，同時(shí)隨著樣本規(guī)模的積累逐步提高分類精度.

關(guān)鍵詞:增量學(xué)習(xí)；SVM；Android；惡意應(yīng)用檢測(cè)

作為現(xiàn)今擁有最大規(guī)模用戶群體的移動(dòng)端操作系統(tǒng)，Android在給人們生活帶來便利的同時(shí)，其自身也在遭受著越來越多的安全威脅.版本碎片化、系統(tǒng)開源性、非授權(quán)應(yīng)用商店泛濫，以及用戶安全意識(shí)薄弱等因素使得Android系統(tǒng)所面臨的安全問題相對(duì)于另一主流系統(tǒng)iOS更加突出.針對(duì)Android系統(tǒng)的惡意應(yīng)用數(shù)量持續(xù)增長(zhǎng)，涉及領(lǐng)域不斷擴(kuò)大，攻擊形式日新月異，給用戶造成的數(shù)據(jù)破壞、隱私泄露、財(cái)產(chǎn)損失等后果也日益嚴(yán)重，迫切需要采取有效方法對(duì)Android惡意應(yīng)用進(jìn)行準(zhǔn)確檢測(cè)，進(jìn)而采取應(yīng)對(duì)措施.

1相關(guān)研究

隨著機(jī)器學(xué)習(xí)(Machine Learning)技術(shù)逐漸走向成熟，如何利用這些技術(shù)進(jìn)行軟件行為自動(dòng)分類，實(shí)現(xiàn)Android惡意應(yīng)用智能檢測(cè)與處理，正在成為Android安全研究領(lǐng)域的熱點(diǎn)之一[1-2].張怡婷等[3]針對(duì)Android系統(tǒng)授權(quán)管理粒度較粗等問題，提出了一種基于樸素貝葉斯模型的惡意行為識(shí)別方法，綜合考慮軟件運(yùn)行時(shí)的各種特性抽取軟件特征作為分類屬性，通過對(duì)Android安全框架的擴(kuò)展，實(shí)現(xiàn)對(duì)惡意行為的實(shí)時(shí)分析和處理.楊文[4]針對(duì)軟件行為的動(dòng)態(tài)性提出一種基于字符串核函數(shù)的SVM分類方法.通過提取樣本軟件行為特征生成訓(xùn)練數(shù)據(jù)，訓(xùn)練SVM分類器生成分類模型對(duì)待檢測(cè)軟件進(jìn)行分類.董航等[5]將隱馬爾可夫模型(HMM)和支持向量機(jī)(SVM)相結(jié)合，提出了基于HMMs-SVM的程序行為分類模型.楊歡等[6]根據(jù)多類行為特征在惡意代碼檢測(cè)中所起的不同作用，提出綜合考慮Android多類行為特征的算法THEA，通過構(gòu)建適合3類特征的最優(yōu)分類器來綜合評(píng)判Android應(yīng)用是否存在惡意行為.

這些研究方法的共同特點(diǎn)為：在構(gòu)造分類器前先獲得足夠的訓(xùn)練樣本，再利用單一或綜合分類算法構(gòu)造分類器，最后利用測(cè)試樣本對(duì)分類器性能進(jìn)行檢測(cè)，訓(xùn)練樣本規(guī)模決定了最終分類器的精度和穩(wěn)定性.然而，這種方式存在著一定缺陷：首先，一次獲得的初始訓(xùn)練樣本集規(guī)模有限，由此得到的分類器分類精度不高；其次，隨著樣本規(guī)模的上升，建立分類模型所耗費(fèi)的時(shí)間和存儲(chǔ)空間不斷增大，成本增加.

為了降低構(gòu)造分類器的時(shí)間和空間消耗，并通過訓(xùn)練樣本規(guī)模的增加逐步改善分類器性能，需要改變策略，尋找更加有效的解決方法.本文將增量學(xué)習(xí)理論[7-9]應(yīng)用于分類器設(shè)計(jì)中，提出一種基于增量學(xué)習(xí)SVM的分類器訓(xùn)練算法構(gòu)造分類器并對(duì)Android應(yīng)用進(jìn)行有效分類.該算法將訓(xùn)練樣本劃分為若干子集，通過循環(huán)迭代的方法，結(jié)合SVM算法構(gòu)造支持向量集，算法充分利用了樣本學(xué)習(xí)的先驗(yàn)信息，無需重復(fù)對(duì)全部訓(xùn)練樣本進(jìn)行學(xué)習(xí)，能夠接受新增樣本集訓(xùn)練，并隨著樣本集的積累逐步提高學(xué)習(xí)精度.

2支持向量機(jī)(SVM)理論

支持向量機(jī)(Support Vector Machine，SVM)是Vapnik等人根據(jù)統(tǒng)計(jì)學(xué)習(xí)理論提出的一種機(jī)器學(xué)習(xí)方法，它以VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小化準(zhǔn)則為基礎(chǔ)，通過在特征空間構(gòu)建最優(yōu)分類超平面使分類器達(dá)到全局最優(yōu)，并實(shí)現(xiàn)整個(gè)樣本空間的期望風(fēng)險(xiǎn)可控，從而在有限訓(xùn)練樣本的情況下獲得良好的統(tǒng)計(jì)規(guī)律[10-11].其基本思想是：對(duì)于線性可分樣本集，在原空間求解二分類的最優(yōu)分類超平面，將SVM的求解轉(zhuǎn)化成凸二次規(guī)劃問題.對(duì)于線性不可分樣本集，引入松弛項(xiàng)，使用非線性映射將輸入空間的非線性問題轉(zhuǎn)化為高維特征空間中的線性問題，并在該特征空間中尋找最優(yōu)分類超平面.由于求解SVM最終轉(zhuǎn)化為凸二次規(guī)劃問題的求解，因此SVM的解是全局唯一的最優(yōu)解.SVM在解決小樣本、非線性及高維模式識(shí)別問題中體現(xiàn)出很多獨(dú)特優(yōu)勢(shì)，具有良好的泛化能力和魯棒性.

3增量學(xué)習(xí)SVM算法

增量學(xué)習(xí)SVM算法將訓(xùn)練樣本集劃分為初始訓(xùn)練樣本集和若干新增樣本子集并利用SVM進(jìn)行迭代訓(xùn)練，將每次訓(xùn)練得到的支持向量集加入到下一組新增樣本子集中進(jìn)行新一輪訓(xùn)練，對(duì)原始訓(xùn)練集中的訓(xùn)練樣本保持KKT(Karush-Kuhn-Tucker)最優(yōu)化條件.由于該算法在進(jìn)行新一輪訓(xùn)練時(shí)僅使用了上一輪訓(xùn)練得到的支持向量集，舍棄了大量的、對(duì)分類結(jié)果不產(chǎn)生影響的樣本向量，使得訓(xùn)練樣本規(guī)模大大降低，減少了存儲(chǔ)空間的占用和訓(xùn)練時(shí)間的消耗.同時(shí)，支持向量集的加入使得新一輪的訓(xùn)練充分利用了先前學(xué)習(xí)所得到的歷史信息.隨著迭代次數(shù)的增加和新增樣本子集數(shù)量的積累，分類器的性能也得到提升.

設(shè)訓(xùn)練樣本集T={(xi,yi),i=1,2,…,N}，其中，xi∈Rn為T中第i個(gè)包含n維特征向量的訓(xùn)練樣本，yi∈{-1,+1}為xi對(duì)應(yīng)的負(fù)類(非惡意樣本)和正類(惡意樣本)的類別標(biāo)號(hào)，-1代表負(fù)類，+1代表正類.

設(shè)Rn上的線性判別函數(shù)g(x)=w·x+b，分類面方程為w·x+b=0，w為平面法向量，b為閾值.對(duì)g(x)進(jìn)行歸一化處理，使得對(duì)于所有x都有|g(x)|≥1，即離分類面最近的樣本滿足|g(x)|=1，分類間隔為2/‖w‖.要使分類面對(duì)所有樣本正確分類，就必須滿足：

yi(w·xi+b)≥1,i=1,2,…,N

(1)

在正確分類的同時(shí)分類間隔最大(即‖w‖2最小)的分類面即為尋找的最優(yōu)分類面.

線性不可分情況下在公式(1)中增加的一個(gè)松弛項(xiàng)，在求解最優(yōu)超平面可以轉(zhuǎn)化為如下二次優(yōu)化問題：

i=1,2,…,N

s.t.yi(w·xi+b)+ξi1

(2)

式中，C>0為懲罰因子，控制對(duì)錯(cuò)分樣本的懲罰程度.

引入拉格朗日函數(shù)，公式(2)的對(duì)偶問題為：

(3)

0≤αi≤C,i=1,…,N

公式(3)中，αi為拉格朗日乘子.在線性不可分情況下，引入核函數(shù)K(xi,xj)，將非線性問題映射為高維特征空間的線性問題.K(xi,xj)為滿足Mercer條件的核函數(shù)，K(xi,xj)=Φ(xi)TΦ(xj),Φ(x)為空間映射函數(shù).

對(duì)公式(2)和(3)進(jìn)行合并約簡(jiǎn)處理，將公式(3)中的目標(biāo)函數(shù)改寫為：

(4)

其中，Qij=yiyjφT(xi)φ(xj)為對(duì)稱半正定核陣.

應(yīng)用拉格朗日乘子法并滿足KKT條件:αi{yi(w·xi+b)}=0,i=1,…,N.

最后得到SVM最優(yōu)分類函數(shù)：

(5)

f(x)=0為分類面，f(x)=±1為分類間隔面.由此，訓(xùn)練樣本集T中的樣本依據(jù)系數(shù)αi被劃分為兩類：αi=0對(duì)應(yīng)的樣本為非支持向量，對(duì)于分類結(jié)果沒有影響；αi>0對(duì)應(yīng)的樣本為支持向量.其中，αi=C所代表的樣本位于分類間隔面關(guān)于本類的異側(cè)，0<αi

在核函數(shù)的選擇上，高斯徑向基核函數(shù)(RBF)是取值僅僅依賴于特定點(diǎn)距離的實(shí)值函數(shù)：

(6)

對(duì)于高維、小樣本和線性不可分具有較強(qiáng)的適應(yīng)性，本文將其作為增量學(xué)習(xí)SVM的核函數(shù).

增量學(xué)習(xí)SVM訓(xùn)練算法描述如下：

(1)將訓(xùn)練樣本集T隨機(jī)劃分為m個(gè)互不相交的訓(xùn)練子集T0,T1,…,Tm-1；

(2)使用T0作為訓(xùn)練集初始化SVM分類器Ω0，訓(xùn)練得到支持向量集SV0；

(3)對(duì)于i=1,…,m-1，循環(huán)執(zhí)行如下操作：

將SVi-1∪Ti作為新的訓(xùn)練集，訓(xùn)練SVM分類器Ωi，得到新的支持向量集SVi；

(4)輸出支持向量集SVm-1并得到最終的SVM分類器.

增量學(xué)習(xí)SVM訓(xùn)練的過程如圖1所示.

圖1　增量學(xué)習(xí)SVM訓(xùn)練的過程

根據(jù)文獻(xiàn)[12]，在增量學(xué)習(xí)過程中，若Ti中的樣本都滿足Ωi-1的KKT條件，則Ti∩SVi=?，即Ti中沒有新增支持向量；反之，若Ti中有部分樣本不滿足Ωi-1的KKT條件，則Ti∩SVi=?，即Ti中存在新的支持向量[12].據(jù)此，我們?cè)谛略鰳颖炯型ㄟ^對(duì)KKT條件的判斷來舍棄部分對(duì)訓(xùn)練結(jié)果不產(chǎn)生影響的訓(xùn)練子集，進(jìn)一步降低算法的執(zhí)行時(shí)間.

4特征選擇

樣本特征的選擇對(duì)于分類結(jié)果有著重要的影響.由于Android應(yīng)用程序在執(zhí)行惡意行為時(shí)都伴隨著對(duì)系統(tǒng)權(quán)限的使用和對(duì)API函數(shù)的調(diào)用.因此，權(quán)限申請(qǐng)、API函數(shù)調(diào)用序列是目前研究最多的、用來判定Android應(yīng)用是否存在惡意行為的重要特征.本文將對(duì)應(yīng)用程序的這兩類特征進(jìn)行提取.

權(quán)限申請(qǐng)?zhí)卣?在Android系統(tǒng)中，應(yīng)用程序在執(zhí)行敏感操作前需要首先獲得相應(yīng)的操作權(quán)限.Android系統(tǒng)內(nèi)置了100多項(xiàng)系統(tǒng)權(quán)限，這些權(quán)限按照保護(hù)級(jí)別分為normal、dangerous、signal、signalorsystem4種類型.其中，除normal類型外，其他3種都對(duì)應(yīng)著系統(tǒng)敏感權(quán)限.Android應(yīng)用程序?qū)τ谙到y(tǒng)權(quán)限的申請(qǐng)需要在配置文件AndroidManifest.xml中通過uses-permission標(biāo)簽顯式提出，由PackageManager服務(wù)在應(yīng)用程序安裝時(shí)提交給用戶確認(rèn).由于Android采用的是粗粒度權(quán)限管理模式，只有當(dāng)用戶同意授予應(yīng)用程序所申請(qǐng)的全部權(quán)限時(shí)安裝才能成功，惡意應(yīng)用可以通過申請(qǐng)超過自身正常行為需求的敏感權(quán)限來實(shí)施惡意行為.因此，分析應(yīng)用程序?qū)γ舾袡?quán)限的申請(qǐng)情況能夠很好地判定應(yīng)用程序的行為模式.本文按照文獻(xiàn)[13]的方法統(tǒng)計(jì)出Android系統(tǒng)全部敏感權(quán)限(或敏感權(quán)限組合)并予以編號(hào)[13]，通過調(diào)用Android反編譯工具apktool對(duì)APK文件進(jìn)行反編譯，遍歷其中的AndroidManifest.xml文件，提取uses-permission標(biāo)簽中的敏感權(quán)限并將其抽象出來作為應(yīng)用程序行為特征.

API函數(shù)調(diào)用特征.Android API是Google官方通過Android SDK提供給應(yīng)用程序開發(fā)者訪問系統(tǒng)功能的接口，惡意應(yīng)用實(shí)現(xiàn)對(duì)Android系統(tǒng)的訪問也需要通過調(diào)用相應(yīng)的API來實(shí)現(xiàn).跟蹤分析API函數(shù)調(diào)用情況可以獲取應(yīng)用程序?qū)ο到y(tǒng)的訪問情況.API的數(shù)量是有限的，如果用API序號(hào)代表API函數(shù)，則應(yīng)用程序?qū)PI的調(diào)用可以表示為有限長(zhǎng)度的API序列.因此，本文以敏感權(quán)限對(duì)應(yīng)的API為入口，通過對(duì)classes.dex反匯編后生成的smali文件中進(jìn)行函數(shù)調(diào)用序列回溯，提取API函數(shù)調(diào)用序列并抽象為API函數(shù)調(diào)用特征.考慮到部分惡意應(yīng)用可能會(huì)采用代碼混淆、加密等技術(shù)防止自身代碼被反編譯，本文在特征提取時(shí)加入了動(dòng)態(tài)分析模塊，即在代碼反編譯失敗的情況下將APK裝入模擬器運(yùn)行，并從APK運(yùn)行的trace文件日志中獲取API調(diào)用的序列、時(shí)間、次數(shù)等信息，從中抽象出API函數(shù)調(diào)用特征.

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

實(shí)驗(yàn)中所使用的惡意應(yīng)用樣本來源于kafan論壇和VX Heavens上病毒樣本區(qū)，通過注冊(cè)下載獲得；非惡意應(yīng)用樣本下載自Google Play應(yīng)用商店，并經(jīng)過ijiami分析平臺(tái)(http://safe.ijiami.cn/)和360手機(jī)衛(wèi)士安全檢測(cè)，確保非惡意應(yīng)用樣本不包含惡意應(yīng)用.共收集1200個(gè)樣本，其中惡意應(yīng)用和非惡意應(yīng)用樣本各為600.

實(shí)驗(yàn)在DELL VOSTRO 3650-D1298真機(jī)(CPU：Intel G4400 3.3GHz，RAM：DDR3L 1.6GHz)上進(jìn)行，操作系統(tǒng)環(huán)境為Windows 7 Professional(x86).為了更好地觀察實(shí)驗(yàn)結(jié)果，將樣本集進(jìn)行了劃分.首先，隨機(jī)選取了400個(gè)樣本(惡意應(yīng)用和非惡意應(yīng)用樣本各為200)作為初始樣本集，剩下的800個(gè)樣本等分成4組，每組200個(gè)，其中惡意應(yīng)用和非惡意應(yīng)用樣本各占一半.用常規(guī)SVM算法和增量學(xué)習(xí)算法分別進(jìn)行訓(xùn)練.兩種方法的分類時(shí)間和分類器精度(分類準(zhǔn)確率)如表1所示.

表1　常規(guī)SVM算法與增量學(xué)習(xí)SVM算法實(shí)驗(yàn)結(jié)果比較

從實(shí)驗(yàn)結(jié)果的分析可以看出，在初始樣本集上的訓(xùn)練，兩種方法的實(shí)驗(yàn)過程基本等同.隨著增量樣本集的加入，兩者的分類精度均有所上升，但精度對(duì)比并沒有顯著差別；常規(guī)SVM算法的訓(xùn)練時(shí)間與樣本規(guī)模基本成正比，增量學(xué)習(xí)SVM算法的訓(xùn)練時(shí)間卻并沒有明顯增加，而且在與增量樣本集1合并運(yùn)算時(shí)訓(xùn)練時(shí)間反而有所下降.這是因?yàn)?，?dāng)增量樣本集加入時(shí)，常規(guī)SVM算法將增量樣本集與原有樣本集合并訓(xùn)練，因而樣本集不斷增大.增量學(xué)習(xí)SVM算法將增量樣本集與上一輪訓(xùn)練得到的支持向量集合并訓(xùn)練，由于支持向量集僅占所在樣本集的一小部分，因而，訓(xùn)練樣本集的規(guī)模大大降低.同時(shí)，訓(xùn)練樣本集規(guī)模也沒有隨著樣本總數(shù)的增加而成比例地?cái)U(kuò)大.支持向量集的加入使得增量學(xué)習(xí)SVM算法有效地利用了樣本訓(xùn)練的歷史信息，訓(xùn)練得到的分類器精度并沒有下降，而是隨著樣本數(shù)的積累逐步提升并趨于穩(wěn)定.由此可見，增量學(xué)習(xí)SVM算法相較于常規(guī)SVM算法，在保證分類精度的情況下可以有效降低訓(xùn)練時(shí)間，減少樣本存儲(chǔ)占用的空間.對(duì)于大規(guī)模樣本訓(xùn)練，以及樣本集不斷更新的應(yīng)用場(chǎng)景具有更好的適應(yīng)性.

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

通過對(duì)Android惡意應(yīng)用檢測(cè)算法的的研究，提出一種基于增量學(xué)習(xí)SVM的惡意應(yīng)用檢測(cè)算法.該算法將樣本集劃分為初始樣本集和若干個(gè)增量樣本集，利用循環(huán)迭代每次將上一輪訓(xùn)練得到的支持向量集合并到新增樣本集中進(jìn)行訓(xùn)練，舍棄對(duì)分類結(jié)果不產(chǎn)生影響的樣本以提高分類器學(xué)習(xí)效率，并產(chǎn)生新的支持向量集，并最終得到一個(gè)高精度的SVM分類器.與常規(guī)SVM算法相比，該算法可以有效降低分類器學(xué)習(xí)時(shí)間，減少樣本存儲(chǔ)的空間占用，同時(shí)隨著樣本規(guī)模的積累逐步提高分類精度.

參考文獻(xiàn)：

[1]文偉平,梅瑞,寧戈,汪亮亮.Android惡意軟件檢測(cè)技術(shù)分析和應(yīng)用研究[J].通信學(xué)報(bào),2014(08):78-85，94.

[2]彭國(guó)軍,李晶雯,孫潤(rùn)康,肖云倡.Android惡意軟件檢測(cè)研究與進(jìn)展[J].武漢大學(xué)學(xué)報(bào)(理學(xué)版),2015(01):21-33.

[3]張怡婷,張揚(yáng),張濤,楊明,羅軍舟.基于樸素貝葉斯的Android軟件惡意行為智能識(shí)別[J].東南大學(xué)學(xué)報(bào)(自然科學(xué)版),2015(02):224-230.

[4]楊文.基于支持向量機(jī)的Android惡意軟件檢測(cè)方法研究[D].南京:南京理工大學(xué),2015.

[5]董航,李祺,董楓,彭勇,徐國(guó)愛.Android運(yùn)行時(shí)惡意行為檢測(cè)模型研究[J].北京郵電大學(xué)學(xué)報(bào),2014(03):58-61，88.

[6]楊歡,張玉清,胡予濮,劉奇旭.基于多類特征的Android應(yīng)用惡意行為檢測(cè)系統(tǒng)[J].計(jì)算機(jī)學(xué)報(bào),2014(01):15-27.

[7]王修君,沈鴻.一種基于增量學(xué)習(xí)型矢量量化的有效文本分類算法[J].計(jì)算機(jī)學(xué)報(bào),2007(08):1277-1285.

[8]郭躬德,黃杰,陳黎飛.基于KNN模型的增量學(xué)習(xí)算法[J].模式識(shí)別與人工智能,2010(05):701-707.

[9]胡蓉,徐蔚鴻,甘嵐.一種連續(xù)增量學(xué)習(xí)模糊神經(jīng)網(wǎng)絡(luò)[J].模式識(shí)別與人工智能,2013(08):794-800.

[10]張學(xué)工.關(guān)于統(tǒng)計(jì)學(xué)習(xí)理論與支持向量機(jī)[J].自動(dòng)化學(xué)報(bào),2000(01):36-46.

[11]王國(guó)勝.支持向量機(jī)的理論與算法研究[D].北京:北京郵電大學(xué),2008.

[12]Badrinarayanan V,Budvytis I,Cipolla R.Semi-supervised video segmentation using tree structured graphical models [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35(11):2751-2764.

[13]楊歡,張玉清,胡予濮,劉奇旭. 基于權(quán)限頻繁模式挖掘算法的Android惡意應(yīng)用檢測(cè)方法[J].通信學(xué)報(bào),2013 (S1):106-115.

(責(zé)任編輯:王前)

DOI:10.13877/j.cnki.cn22-1284.2016.06.021

*收稿日期：2016-05-19

基金項(xiàng)目：安徽省高校質(zhì)量工程項(xiàng)目(2015jxtd074)；安徽省高校質(zhì)量工程項(xiàng)目(2015zy104)

作者簡(jiǎn)介：熊祖濤，男，安徽肥西人，講師.

中圖分類號(hào)：TP309

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1008-7974(2016)03-0066-04