基于函數(shù)調(diào)用圖的Android惡意代碼檢測(cè)方法研究

(青海民族大學(xué) 物理與電子信息工程學(xué)院，西寧 810007)

基于函數(shù)調(diào)用圖的Android惡意代碼檢測(cè)方法研究

李自清

(青海民族大學(xué)物理與電子信息工程學(xué)院，西寧810007)

隨著移動(dòng)互聯(lián)網(wǎng)的迅猛發(fā)展和智能設(shè)備的普及，Android 平臺(tái)的安全問題日益嚴(yán)峻，不斷增多的惡意軟件對(duì)終端用戶造成了許多困擾，嚴(yán)重威脅著用戶的隱私安全和財(cái)產(chǎn)安全；因此對(duì)惡意軟件的分析與研究也成為安全領(lǐng)域的熱點(diǎn)之一；提出了一種基于函數(shù)調(diào)用圖的 Android 程序特征提取及檢測(cè)方法；該方法通過對(duì) Android 程序進(jìn)行反匯編得到函數(shù)調(diào)用圖，在圖譜理論基礎(chǔ)上，結(jié)合函數(shù)調(diào)用圖變換后提取出的圖結(jié)構(gòu)和提取算法，獲取出具有一定抗干擾能力的程序行為特征；由于 Android 函數(shù)調(diào)用圖能夠較好地體現(xiàn) Android 程序的功能模塊、結(jié)構(gòu)特征和語義；在此基礎(chǔ)上，實(shí)現(xiàn)檢測(cè)原型系統(tǒng)，通過對(duì)多個(gè)惡意 Android 程序分析和檢測(cè)，完成了對(duì)該系統(tǒng)的實(shí)驗(yàn)驗(yàn)證；實(shí)驗(yàn)結(jié)果表明，利用該方法提取的特征能夠有效對(duì)抗各類 Android 程序中的混淆變形技術(shù)，具有抗干擾能力強(qiáng)等特點(diǎn)，基于此特征的檢測(cè)對(duì)惡意代碼具有較好地識(shí)別能力。

機(jī)器學(xué)習(xí);Android 程序;函數(shù)調(diào)用圖;圖譜理論;特征提取

0 引言

Android 系統(tǒng)得到應(yīng)用以來，以較低成本的開銷、良好的用戶體驗(yàn)和較高的開源性等優(yōu)點(diǎn)獲得了廣泛好評(píng)。但由于簡(jiǎn)單的安全檢查機(jī)制，引來無數(shù)惡意者對(duì)于 Android 應(yīng)用市場(chǎng)進(jìn)行惡意攻擊。各類惡意軟件對(duì)于Android平臺(tái)的攻擊包括惡意扣費(fèi)、竊取隱私、消耗資源、遠(yuǎn)程控制、惡意傳播等嚴(yán)重影響了用戶的信息安全，對(duì)個(gè)人隱私、企業(yè)發(fā)展、國(guó)家安全都造成了嚴(yán)重的威脅和不可挽回的損失。如何檢測(cè) Android 惡意程序成了信息安全中不可忽視重要任務(wù)。馮本慧[1]指出傳統(tǒng)的 Android 惡意程序檢測(cè)技術(shù)過度依賴分析人員的經(jīng)驗(yàn)，且無法檢測(cè)未知惡意程序等問題，面對(duì)當(dāng)前數(shù)目龐大的且層出不窮的 Android 惡意程序，分析效率低下。因此需要利用數(shù)據(jù)挖掘技術(shù)實(shí)現(xiàn)檢測(cè)的自動(dòng)化、智能化。而當(dāng)前此方法的研究重點(diǎn)主要分為兩個(gè)方面，一是不同分類算法的選擇使用，不同分類算法的效率與精度各有不同， 二是 Android 程序的特征以及特征選擇的方法，不同特征描述的是惡意代碼不同層面的信息 Android 程序特征提取技術(shù)在此背景下應(yīng)運(yùn)而生。

本文提出了一種基于函數(shù)調(diào)用圖的 Android 惡意程序提取和檢測(cè)技術(shù)，該方法在圖譜理論基礎(chǔ)上，結(jié)合函數(shù)調(diào)用圖變換后提取出的圖結(jié)構(gòu)和提取算法，獲取出具有一定抗干擾能力的程序行為特征，將提取出的特征輸入決策樹模型進(jìn)行訓(xùn)練得到預(yù)測(cè)系統(tǒng)。圖特征提取只需進(jìn)行靜態(tài)提取，不需要?jiǎng)討B(tài)運(yùn)行，且實(shí)現(xiàn)了檢測(cè)的智能化與自動(dòng)化，易于應(yīng)用于未知惡意程序檢測(cè)。實(shí)驗(yàn)結(jié)果表明該方法對(duì)常見的混淆變形后的惡意程序具有較好的魯棒性和時(shí)效性。

1 Android 惡意程序特征提取與預(yù)測(cè)模型

1.1 Android 惡意程序特征提取技術(shù)分析

Android 字節(jié)特征提取技術(shù)是利用定長(zhǎng)或者變長(zhǎng)的 n-gram 滑動(dòng)窗口滑動(dòng)惡意代碼文件所獲得的序列信息。Reddy[2]使用此技術(shù)在文本分類中取得了很好的效果。字節(jié)序列作為特征，雖然可以獲得惡意代碼的編碼風(fēng)格等有用信息，但由于缺乏語義信息，對(duì)于加密混淆后的病毒檢測(cè)效率低下。Altyeb[3]開始利用惡意代碼的應(yīng)用程序編程接口做為特征，由于惡意代碼需要實(shí)現(xiàn)自身的功能需要借助操作系統(tǒng)提供的 API 完成，而 API 的調(diào)用序列可以表示惡意代碼的行為以及涉及的語義信息。API 調(diào)用序列分為靜態(tài)和動(dòng)態(tài)的調(diào)用序列，靜態(tài)調(diào)用序列不需要運(yùn)行程序的前提下獲得文件導(dǎo)入表或者反匯編文件中的 API 調(diào)用序列，動(dòng)態(tài)調(diào)用序列即需要在虛擬機(jī)運(yùn)行程序中利用調(diào)試等技術(shù)獲得與系統(tǒng)交互的 API 調(diào)用序列。獲得 API 調(diào)用信息作為特征，使用分類算法進(jìn)行檢測(cè)，最后達(dá)到了較高的精度。然而，由于惡意代碼會(huì)隱藏導(dǎo)入表 API 的調(diào)用，使得無法獲得全部 API 調(diào)用信息，最終導(dǎo)致靜態(tài) API 序列 作為特征檢測(cè)惡意代碼的效率不高，但惡意代碼需要完成自身功能及時(shí)隱藏導(dǎo)入表 API 調(diào)用，也會(huì)與操作系統(tǒng)中的 API 進(jìn)行交互，因此 Zhang M[4]將可疑文件置于虛擬機(jī)中運(yùn)行動(dòng)態(tài)獲得API 序列，并計(jì)算 API 序列和正常文件的距離作為特征進(jìn)行檢測(cè)。動(dòng)態(tài)獲得 API 調(diào)用 序列的特征進(jìn)行檢測(cè)技術(shù)中，要獲得特征就必須運(yùn)行惡意代碼，導(dǎo)致開銷過大，而對(duì)于某些能夠檢測(cè)到虛擬機(jī)存在環(huán)境的病毒無能為力，并且一些惡意代碼采用了相關(guān)行為層的混淆技術(shù)，導(dǎo)致動(dòng)態(tài)提取 API 調(diào)用序列失敗。函數(shù)調(diào)用圖是編譯過程對(duì)程序中函數(shù)調(diào)用關(guān)系的一種靜態(tài)描述，其中節(jié)點(diǎn)表示函數(shù)，邊表示函數(shù)之間的調(diào)用關(guān)系，由于程序的功能性主要由庫(kù)函數(shù)和系統(tǒng)調(diào)用來決定，因此函數(shù)調(diào)用圖能為程序的實(shí)際行為提供靜態(tài)的有效近似，是程序的結(jié)構(gòu)化表示形式，對(duì)于基于源碼或二進(jìn)制碼的局部軟件變形具有魯棒性，函數(shù)調(diào)用圖通過 IDA Pro 這種成熟的交互式反匯編工具生成。因此部分研究人員從將研究重點(diǎn)轉(zhuǎn)移到了提取函數(shù)調(diào)用圖的特征作為程序特征圖。劉星[5]提出用函數(shù)調(diào)用圖的相似性距離度量?jī)蓚€(gè)代碼的相似性來檢測(cè)惡意代碼，該方法考慮了惡意代碼中函數(shù)的指令級(jí)信息以及函數(shù)之間的調(diào)用關(guān)系。楊帆[6]提出了基于二分圖匹配的圖編輯距離檢測(cè)惡意程序，圖編輯距離通過將一個(gè)圖轉(zhuǎn)換為另一個(gè)圖需要編輯操作集合的最小數(shù)量來度量程序間的關(guān)系。賴興瑞[7]提取出函數(shù)依賴圖的最大公共子圖作為中文 web 文本分類。顏克文[8]在安卓程序相似性比較中通過函數(shù)調(diào)用圖轉(zhuǎn)換為特征向量，以圖特征向量之間相似性衡量程序相似性不失為一種辦法，但是提取出的特征向量不具備相同維度，一次只能對(duì)少數(shù)程序進(jìn)行比較。

因此，不論是圖編輯距離、最大公共子圖還是圖同構(gòu)方法在 Android 海量應(yīng)用場(chǎng)景下計(jì)算代價(jià)非常大[9-11]，要對(duì)大量程序進(jìn)行檢測(cè)，其實(shí)現(xiàn)的時(shí)間復(fù)雜度和空間復(fù)雜度不具備可行性。

1.2 預(yù)測(cè)模型建立

Android 惡意程序特征提取與預(yù)測(cè)模型分為3個(gè)模塊：特征提取模塊、構(gòu)造分類器模塊、 預(yù)測(cè)模塊組成如下圖 1 所示：

1)輸入安卓程序被稱為“訓(xùn)練數(shù)據(jù)”，每組訓(xùn)練數(shù)據(jù)有一個(gè)明確的標(biāo)識(shí)或結(jié)果，如 Android 程序?qū)?yīng)著“惡意程序”或“正常程序”[12]。在建立分類模型之前，需要對(duì)數(shù)據(jù)進(jìn)行預(yù)處理即將 Android 程序進(jìn)行反編譯，從函數(shù)調(diào)用關(guān)系中提取出依賴特征、構(gòu)造函數(shù)調(diào)用圖的特征向量，接著建立一個(gè)學(xué)習(xí)過程，將處理后的特征向量輸入分類模型中，將分類模型的預(yù)測(cè)結(jié)果與“訓(xùn)練數(shù)據(jù)”的實(shí)際結(jié)果進(jìn)行比較，不斷的調(diào)整預(yù)測(cè)模型，直到模型的預(yù)測(cè)結(jié)果達(dá)到一個(gè)預(yù)期的準(zhǔn)確率。

2)構(gòu)造分類器模塊中，分類器采用梯度上升決策樹實(shí)現(xiàn)，原理為：算法開始時(shí)，為每個(gè)樣本賦上一個(gè)估計(jì)值，初始時(shí)每個(gè)樣本的估計(jì)值都一樣，在每一步訓(xùn)練中得到的模型(分類回歸樹)，會(huì)是的數(shù)據(jù)點(diǎn)的估計(jì)有對(duì)有錯(cuò)，計(jì)算數(shù)據(jù)點(diǎn)估計(jì)值與實(shí)際值的殘差的梯度，在每一次模型梯度減少的方向建立一個(gè)新模型，重復(fù)N次(N由用戶指定)，會(huì)得到N個(gè)簡(jiǎn)單的分類器(分類回歸樹)，將N個(gè)分類器組合起來(加權(quán)、或者進(jìn)行投票等)，得到一個(gè)最終的模型

3)病毒檢測(cè)模塊中，分類器中得到N個(gè)簡(jiǎn)單分類器，用N個(gè)分類器依次對(duì)未知病毒文件進(jìn)行判斷，每次判斷病毒文件按照樹的分支條件選擇符合自己的葉子節(jié)點(diǎn)，計(jì)算每次分類器判斷得到的葉子節(jié)點(diǎn)的信息增益，相加最多的為最終結(jié)果。

圖1 Android 惡意代碼檢測(cè)模型圖

2 程序特征提取與檢測(cè)技術(shù)

2.1 Android 程序預(yù)處理技術(shù)

Android 平臺(tái)的應(yīng)用程序包以 APK 格式為主，用戶將 APK 文件直接傳輸?shù)绞謾C(jī)上即可進(jìn)行安裝。因此，Android 惡意程序的各種惡意行為，大多是通過在應(yīng)用程序包中植入惡意代碼或惡意組件來實(shí)現(xiàn)的。惡意攻擊者將惡意程序注入并隱藏在安全應(yīng)用程序中，經(jīng)過重新打包，表現(xiàn)出同原安全應(yīng)用程序一樣的外在，導(dǎo)致程序使用者將其認(rèn)定為安全應(yīng)用程序下載， 并安裝到自己的 Android 手機(jī)上。當(dāng)程序啟動(dòng)后，被注入到安全應(yīng)用程序中的惡意程序就開始了自己的惡意行為，對(duì)用戶信息安全構(gòu)成了嚴(yán)重的威脅。在安全應(yīng)用程序中注入惡意程序 主要由以下步驟構(gòu)成，第一步對(duì)其進(jìn)行反匯編；第二步在反匯編后的安全應(yīng)用程序中注入惡意代碼，加入的應(yīng)用程序的功能和惡意攻擊的代碼的內(nèi)容有關(guān)；第三步將被改寫過的安全應(yīng)用程序重新打包并簽名。進(jìn)行以上三步，一個(gè) Android 惡意程序就形成了[13]。要提取函數(shù)調(diào)用圖需在第三方網(wǎng)站上下載 APK 文件，對(duì) APK 文件進(jìn)行解壓， META-INF 為存放簽名信息文件 res 目錄存放資源文件，classes.dex 是 java 源碼編譯后生成的 java 字節(jié)碼文件，是最終用來被虛擬機(jī) Dalvik 加載和運(yùn)行的可執(zhí)行 Android 文件。對(duì) classes.dex 文件反編譯，根據(jù)反編譯的程序即可生成函數(shù)調(diào)用圖，例如將一個(gè)手機(jī)照明軟件反編譯后提取出的部分函數(shù)調(diào)用圖如圖2所示。

圖2 函數(shù)調(diào)用圖

其中節(jié)點(diǎn)表示函數(shù)，邊表示函數(shù)之間的調(diào)用關(guān)系，有向邊也稱弧,邊的始點(diǎn)稱為弧尾,終點(diǎn)稱為弧頭，一條弧表示弧尾的節(jié)點(diǎn)函數(shù)調(diào)用弧頭的節(jié)點(diǎn)函數(shù)。

2.2 函數(shù)調(diào)用圖特征提取技術(shù)

得到了函數(shù)調(diào)用圖G后需要提取圖的特征向量，從函數(shù)調(diào)用圖中提取特征向量具體步驟如下：

1)一個(gè)圖有G頂點(diǎn)集V(G)={V1,V2，…，Vn} 和邊集E(G)={eI1,e2，…，en} ，鄰接矩陣A(G) 是一個(gè)N×N階矩陣,若G的頂點(diǎn)ViVj相鄰，那么鄰接矩陣A(G)i,j的元素取值為 1，否則為零。

將函數(shù)調(diào)用圖G轉(zhuǎn)化為鄰接矩陣為G→A(G)的矩陣，N為函數(shù)調(diào)用圖的節(jié)點(diǎn)數(shù)。

2)轉(zhuǎn)移概率：根據(jù)頂點(diǎn)的出度信息和頂點(diǎn)之間的調(diào)用關(guān)系計(jì)算頂點(diǎn)之間的轉(zhuǎn)移概率，通過計(jì)算頂點(diǎn)之間的轉(zhuǎn)移概率體現(xiàn)類依賴關(guān)系的調(diào)用概率。

u表示主調(diào)頂點(diǎn)，v表示被調(diào)頂點(diǎn)，out表示頂點(diǎn)的出度，in表示頂點(diǎn)的入度。轉(zhuǎn)移概率為：

計(jì)算轉(zhuǎn)移概率矩陣A(G)→D(G)

3)譜圖論是一種常用的研究方法,其可以利用拉普拉斯矩陣來描述圖的結(jié)構(gòu)。通過分析 拉普拉斯矩陣及其特征值能夠?qū)D結(jié)構(gòu)有更清晰的認(rèn)識(shí),特別是在很多情況下,需要提高拉普 拉斯矩陣的次小特征值λ2,以使圖結(jié)構(gòu)得到優(yōu)化。為了更好地反映圖的全局信息，可以對(duì)函數(shù)調(diào)用圖做拉普拉斯變換，拉普拉斯矩陣是度矩陣和鄰接矩陣的差。度矩陣是一個(gè)對(duì)角矩陣， 其包含了每個(gè)頂點(diǎn)的度。在處理有向圖時(shí)，根據(jù)應(yīng)用來選擇入度或出度。對(duì)轉(zhuǎn)移概率矩陣做拉普拉斯變換D(G)L(G)。

4)矩陣特征值的集合稱作圖的譜。設(shè)A是n階方陣，如果數(shù)λ和n維非零列向量x使 關(guān)系式Ax=λx成立，那么這樣的數(shù)稱為矩陣特征值，非零向量x稱為A的對(duì)應(yīng)于特征值的特征向量，圖的特征向量已被廣泛應(yīng)用以及被證實(shí)可以反映圖的特性。由于鄰接矩陣與點(diǎn)的標(biāo)記有關(guān)。譜是一個(gè)圖常量，當(dāng)兩個(gè)圖的鄰接矩陣有相同的特征集時(shí)，它們被稱為譜相似。譜相似的圖不必同構(gòu)，但同構(gòu)的圖必譜相似，因此需要求出變換后的拉普拉斯矩陣L(G)的特征值(λ1λ2……λm) 以及特征值所對(duì)應(yīng)的特征向量(μ1μ2……μ1)。

5)將特征向量按對(duì)應(yīng)特征值大小排序，取前k個(gè)特征向量(μ1μ2……μk)。

6)圖的譜特征選擇譜系數(shù)夾角譜特征，對(duì)于圖G，目標(biāo)是找出同序列圖像頂點(diǎn)之間具有一致性的相似性，及不同序列圖像的差異性。圖的普特征已經(jīng)被廣泛證實(shí)可以反映圖的特 性，因此使用譜系數(shù)夾角特征作為圖的特征向量提取。 譜系數(shù)夾角定義為圖中在特征向量空間的特征向量各分量之間的夾角的余弦值：

用譜系數(shù)夾角表達(dá)圖特征，計(jì)算各特征向量之間的余弦夾:

v=(C(1,2),C(1,3)……C(1,k),C(2,3)……

C(2,k)……C(k-1,k))

函數(shù)調(diào)用圖提取特征向量步驟如圖3所示。

圖3 特征提取流程圖

2.3 Android 程序預(yù)測(cè)技術(shù)

2.3.1 構(gòu)造分類器技術(shù)

依照上述方法提取出 APK 樣本函數(shù)調(diào)用圖的特征向量，每個(gè)樣本取出函數(shù)調(diào)用圖的特征向量，構(gòu)造分類器。構(gòu)造分類器的本質(zhì)是使用某種算法對(duì)已知類別數(shù)據(jù)集進(jìn)行訓(xùn)練并得到一個(gè)分類模型，該數(shù)據(jù)集是由多個(gè)屬性組成的特征向量，其中包含類別標(biāo)記，訓(xùn)練結(jié)果輸出一組可以對(duì)未知 型的數(shù)據(jù)進(jìn)行預(yù)測(cè)分類的判定規(guī)則。

本技術(shù)的分類器采用梯度上升決策樹方法(Gradient Boosting Decicion Tree)實(shí)現(xiàn)，原 理為：算法開始時(shí)，為每個(gè)樣本賦上一個(gè)估計(jì)值，初始時(shí)每個(gè)樣本的估計(jì)值都一樣，在每一 步訓(xùn)練中的到的模型(分類回歸樹)，會(huì)是的數(shù)據(jù)點(diǎn)的估計(jì)有對(duì)有錯(cuò)，計(jì)算數(shù)據(jù)點(diǎn)估計(jì)值與實(shí)際值的殘差的梯度，在每一次模型梯度減少的方向建立一個(gè)新模型，重復(fù)N次(N由用 戶指定)，會(huì)得到N個(gè)簡(jiǎn)單的分類器(分類回歸樹)，將N個(gè)分類器組合起來(加權(quán)、或 者進(jìn)行投票等)，得到一個(gè)最終的模型。構(gòu)造分類器方法如圖 4 所示。

圖4 迭代分類器構(gòu)造圖

N個(gè)簡(jiǎn)單的分類器采用分類回歸樹構(gòu)造，具體步驟如下：

1)輸入X和Y-p的梯度g

2)遍歷X，選擇任意特征的特征值X(ij)，計(jì)算所有用特征值劃分后的信息不純性度(可 以選擇GINI指數(shù)、雙化指數(shù)、有序雙化指數(shù))，信息不純度越大代表信息當(dāng)前X包含的病毒 種類越雜亂，找到信息不純度最小時(shí)的X(kl)。

3)求出X(il){i:0～m-1}中所有大于X(kl)的值d(k){k:1,2}，將X的所有的d(k)行 組成左子樹數(shù)據(jù)集LX，對(duì)應(yīng)的g為L(zhǎng)g,將剩下的行組成右子樹數(shù)據(jù)集RX，對(duì)應(yīng)的病毒種類為Rg。

4)若劃分后的LX,RX的數(shù)量是否小于用戶設(shè)定數(shù)量，返回1)繼續(xù)尋找X(kl),r若信息不純性度量是小于一定值則執(zhí)行5)，否則執(zhí)行7)。

5)返回當(dāng)前X對(duì)應(yīng)的g的平均值為分類樹的葉節(jié)點(diǎn)。

6)選擇X(kl)為分裂結(jié)點(diǎn)，節(jié)點(diǎn)的左子樹是大于特征值的數(shù)據(jù)集LX,Lg，節(jié)點(diǎn)的右子樹 小于等于特征值的數(shù)據(jù)集RX,Rg。

7)將左子樹的數(shù)據(jù)集LX,Lg做為新數(shù)據(jù)集X,g，執(zhí)行2)。

8)將右子樹的數(shù)據(jù)集RX,Rg作為新數(shù)據(jù)集X,g，執(zhí)行3)。

2.3.2 預(yù)測(cè)技術(shù)

分類器中得到N個(gè)簡(jiǎn)單分類器，用N個(gè)分類器依次對(duì)未知病毒文件進(jìn)行判斷，每次判斷病毒文件按照樹的分支條件選擇符合自己的葉子節(jié)點(diǎn)，計(jì)算每次分類器判斷得到的葉子節(jié)點(diǎn)的信息增益，想加最多的為最終結(jié)果

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

3.1 實(shí)驗(yàn)數(shù)據(jù)來源

實(shí)驗(yàn)非惡意程序樣本主要從Google Play 上下載，包括游戲娛樂、工具類、系統(tǒng)管理類 等程序。雖然據(jù)報(bào)道稱 Google Play 也存在會(huì)出現(xiàn)惡意軟件的可能性，但一經(jīng)發(fā)現(xiàn)便會(huì)被立 刻下架，我們認(rèn)為在所有軟件市場(chǎng)中Google Play 的審核是相對(duì)嚴(yán)格的，因此我們假定下載 的程序?yàn)檎７菒阂獬绦?。雖然常有 Android 惡意軟件的報(bào)道，但并沒有公開的惡意軟件樣本庫(kù)，主要通過平時(shí)在虛擬機(jī)上運(yùn)行手機(jī)報(bào)毒的惡意軟件作為惡意程序樣本。

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

隨機(jī)選取參與訓(xùn)練的良性程序和惡意程序各50個(gè)提取10維特征后輸入分類模型進(jìn)行分類實(shí)驗(yàn)，再選擇未參與訓(xùn)練的新數(shù)據(jù)進(jìn)行檢測(cè)，進(jìn)行五輪實(shí)驗(yàn)，其中選擇7項(xiàng)標(biāo)準(zhǔn)來評(píng)測(cè)實(shí) 驗(yàn)結(jié)果。

TP為真陽(yáng)性，即檢測(cè)正確的惡意樣本數(shù)量；

FP為假陽(yáng)性，即檢測(cè)錯(cuò)誤的良性樣本數(shù)量；

FN為假陰性，即檢測(cè)錯(cuò)誤的惡意樣本數(shù)量；

TN為真陰性，即檢測(cè)正確的良性樣本數(shù)量；

TPR為真陽(yáng)率，TPR=TP/P=TP/(TP+FN)表征一種命中率；

FPR為假陰率，F(xiàn)PR=FP/N=FP/(FP+TN)表征一種錯(cuò)誤命中率；

ACC為檢測(cè)正確所有樣本所占總樣本量的比值。實(shí)驗(yàn)結(jié)果如表1所示。

表1 樣本檢測(cè)結(jié)果表

由以上模擬實(shí)驗(yàn)可以看出，訓(xùn)練樣本的預(yù)測(cè)效果相對(duì)較好，對(duì)于新出現(xiàn)的樣本具有一定的檢測(cè)能力，但不夠穩(wěn)定和理想，原因可能是輸入訓(xùn)練模型的樣本數(shù)量偏少，另外如果能按軟件的分類如游戲、娛樂、工具、系統(tǒng) 管理等來進(jìn)行訓(xùn)練與檢測(cè)也許效果會(huì)更好，因?yàn)椴煌愋偷能浖枰恼{(diào)用的函數(shù)以及權(quán)限集合也有所不同。

3.3 修正實(shí)驗(yàn)

因此擴(kuò)大樣本容量，以及按軟件的分類進(jìn)行訓(xùn)練，隨機(jī)選取游戲娛樂、音樂軟件、聊天220工具、辦公軟件、下載工具類別各50個(gè)軟件進(jìn)行訓(xùn)練，再選擇未參與訓(xùn)練的新數(shù)據(jù)進(jìn)行檢測(cè)，實(shí)驗(yàn)結(jié)果如表2 所示。

表2 樣本檢測(cè)結(jié)果表

訓(xùn)練樣本數(shù)類別TPFNTNFPTPR/%FPR/%ACC/%游戲37133515743072音樂40103515803075聊天419911822280辦公35153317703468下載33174010662073新樣本數(shù)游戲3416446681278音樂29213218583661聊天37132822744465辦公39113119783870下載30202713602657

由以上模擬實(shí)驗(yàn)可以看出，將數(shù)據(jù)按類別分別訓(xùn)練樣本后，由于不同類型的軟件所需要的權(quán)限集合與組合有所不同，因此檢測(cè)效果相對(duì)之前較好，學(xué)習(xí)到的模式與規(guī)律在各種類型的惡意代碼中是基本穩(wěn)定的，對(duì)新出現(xiàn)的惡意代碼也有較好的檢測(cè)能力。

4 結(jié)論

本文提出了 Android 惡意程序特征提取與檢測(cè)新方案，該方案采用靜態(tài)分析技術(shù)，基于 Android 程序惡意代碼本身的函數(shù)調(diào)用順序及程序結(jié)構(gòu)特征，將惡意代碼抽象為圖結(jié)構(gòu)，提取出圖結(jié)構(gòu)特征放入迭代決策樹系統(tǒng)進(jìn)行訓(xùn)練，得到預(yù)測(cè)模型來實(shí)現(xiàn)對(duì)未知惡意程序的有效判斷。主要特點(diǎn)如下：1)通過圖相似性對(duì)比轉(zhuǎn)化為圖特征向量相似性對(duì)比，提高了匹配效率，有效識(shí)別惡意代碼的變種，時(shí)間效率高，不依賴于人工分析；2)用圖的譜夾角表達(dá)圖特征，既表達(dá)了空間各點(diǎn)的連接關(guān)系，同時(shí)不受空間尺度的影響；3)應(yīng)用決策樹技術(shù)實(shí)現(xiàn)檢測(cè)的自動(dòng)化與智能化，由于學(xué)習(xí)到的模式與規(guī)律在各種類型的惡意代碼中是基本穩(wěn)定的，對(duì)新出現(xiàn)的惡意代碼也有很好的檢測(cè)能力。

目前實(shí)驗(yàn)的惡意代碼庫(kù)規(guī)模較小，特征提取的維數(shù)較小，圖特征提取沒有對(duì)冗余信息進(jìn)行處理，這是下一步需要解決和完善的問題。

[1] 馮本慧.基于數(shù)據(jù)挖掘于機(jī)器學(xué)習(xí)的惡意代碼檢測(cè)技術(shù)研究[D].長(zhǎng)沙：中南大學(xué)，2013.

[2] Nagaprasad S, Reddy T R, Reddy P V, et al. Empirical evaluations using character and word N-grams on authorship attribution for Telugu text[M].Intelligent Computing and Applications,Springer India, 2015:613-623.

[3] Shubair A, Ramadass S, Altyeb A A. kENFIS: kNN-based evolving neuro-fuzzy inference system for computer worms detection[J].Journal of Intelligent & Fuzzy Systems Applications in Engineering &Technology, 2014, 26(4):1893-1908.

[4] Zhang M, Duan Y, Yin H, et al. Semantics- AwareAndroid Malware Classification Using Weighted Contextual API Dependency Graphs[A]. ACM[C]. 2014:1105-1116.

[5] 劉 星.惡意代碼的函數(shù)調(diào)用圖相似性分析 [J].計(jì)算機(jī)工程與科學(xué), 2014:1-3.

[6] 楊 帆.基于圖編輯距離的惡意代碼檢測(cè) [J].武漢大學(xué)學(xué)報(bào),2013:1-3.

[7] 賴興瑞.基于最大公共子圖的中文 Web 文本分類研究 [D].廈門：廈門大學(xué), 2011.

[8] 顏克文.基于圖特征向量的安卓程序相似性檢測(cè)算法研究[D].湘潭：湘潭大學(xué)，2014.

[9] Seo S H, Gupta A, Mohamed S A,et al.Detecting mobile malware threats to homeland security through static analysis[J].Journal of Network and Computer Applications,2014,38:43-53.

[10] Jang J, Woo M, et al. Towards automatic software lineage inference[A]. Proceedings of the 22nd USENIX conference on Security. USENIX Association[C]. Berkeley, CA, USA: USENIX Association, 2013:81-96.

[11] Grace M, Zhou Y, Zhang Q, et al. RiskRanker: Scalable and Accurate Zero-day Android Malware Detection[A]. Proceedings of the 10th International Conference on Mobile Systems, Applications and Services (MobiSys'12)[C]. 2012:4-20.

[12] Arp D, Spreitzenbarth M, Hübner M, et al. Drebin: Efficient and Explainable Detection of Android Malware in Your Pocket[A]. Proceedings of the 21th Annual Network and Distributed System Security Symposium (NDSS'14)[C].2014.

[13] Peng H, Gates C, Sarma B, et al. Using Probabilistic Generative Models for Ranking Risks of Android Apps[A].Proceedings of the 2012 ACM Conference on Computer and Communications Security (CCS’12)[C].2012: 2-5.

AndroidMaliciousCodeDetectionMethodBasedonFunctionCallGraph

Li Ziqing

(School of Physics and Electronic Information Engineering, Qinghai University for Nationalities，Xinin 810007， China)

With the popularity of the rapid development of mobile Internet and smart devices, Android platform security issues become more and more serious, more malware caused a lot of trouble to the end user, a serious threat to the safety of the user's privacy and property safety. Therefore, the analysis and research of malware has become one of the hot topics in security field. An innovative practical feature extraction and detection of Android program scheme based on function call graph is proposed in this paper. On Android program disassembling function call graph is obtained by the method, which based on the spectral graph theory, combined with the function call graph transformation after extraction of graph structure and extraction algorithm to obtain a certain anti-interference ability of program behavior characteristics. On this basis, the prototype system is realized, and the system is verified by the analysis and detection of a number of malicious Android programs. The experimental results show that the features extracted by this method can effective against all kinds of Android application confusion deformation technology, has the characteristics of strong anti-jamming ability. Based on this feature detection of malicious code has better recognition ability.。

machine learning; Android program; function call graph; spectral graph theory; feature extraction

2017-03-29；

2017-04-13。

教育部“春暉計(jì)劃”合作科研項(xiàng)目(S2015037)。

李自清(1975-),男,陜西人，碩士,講師，主要從事計(jì)算機(jī)應(yīng)用技術(shù)方向的研究。

1671-4598(2017)10-0198-04

10.16526/j.cnki.11-4762/tp.2017.10.050

TP311.1

A