融合行為模式的Android 惡意代碼檢測方法

楊吉云，范佳文，周 潔，高凌云

1.重慶大學(xué) 計算機(jī)學(xué)院，重慶400044

2.中國石油集團(tuán)測井有限公司西南分公司，重慶400030

近年來，隨著移動智能終端技術(shù)的快速發(fā)展，移動智能設(shè)備已經(jīng)與人們的生活密不可分。目前智能設(shè)備上的主流操作系統(tǒng)大致可以分為IOS 和Android兩大類，而Android 系統(tǒng)由于其開源的優(yōu)勢，其市場份額逐年上升，目前已占據(jù)了移動操作系統(tǒng)85%以上的市場份額。但Android 系統(tǒng)卻更易受到安全威脅，例如竊取用戶的隱私信息、未經(jīng)用戶許可發(fā)送消息以及誘導(dǎo)用戶訪問惡意網(wǎng)站等，從而嚴(yán)重威脅到用戶的財產(chǎn)信息安全，成為了惡意應(yīng)用程序攻擊的主要目標(biāo)。近年來，如何有效且準(zhǔn)確地檢測Android惡意軟件用于保護(hù)用戶隱私信息已成為信息安全領(lǐng)域的熱點之一。

基于機(jī)器學(xué)習(xí)方法構(gòu)建Android惡意軟件檢測模型是目前主要的研究方向，請求權(quán)限、API（application programming interface）調(diào)用、組件、字節(jié)碼以及API調(diào)用序列等特征在現(xiàn)有基于機(jī)器學(xué)習(xí)的檢測模型中被廣泛應(yīng)用。Wang等人提取APK（Android application package）文件的請求權(quán)限、敏感API 調(diào)用、代碼相關(guān)信息以及硬件信息等多種靜態(tài)特征，結(jié)合集成學(xué)習(xí)方法實現(xiàn)模型的檢測和訓(xùn)練。類似的文獻(xiàn)[3]和文獻(xiàn)[4]將清單文件中的多種字符串特征和API 調(diào)用劃分為不同類型，再對其分別處理后作為特征。Badhani 等人將請求權(quán)限和API 的抽象包作為特征，首先通過K-Modes 聚類方法對數(shù)據(jù)集進(jìn)行聚類，然后使用集成方法實現(xiàn)對惡意代碼的檢測。Wang 等人提出將權(quán)限進(jìn)行風(fēng)險排名的方法，方法中使用互信息、相關(guān)系數(shù)和T 檢驗對Android 單個權(quán)限進(jìn)行風(fēng)險排名，將排名靠前的單個權(quán)限以及風(fēng)險權(quán)限子集作為分類特征。Scalas 等人將提取的API 調(diào)用進(jìn)行分級處理，抽象得到包級、類級和方法級的API 信息，并使用隨機(jī)森林算法對其訓(xùn)練檢測。Fan 等人使用自然語言處理方法以及聚類算法對技術(shù)博客內(nèi)容進(jìn)行分析，構(gòu)建敏感行為特征庫，并對權(quán)限、意圖以及API 調(diào)用作相同處理，根據(jù)敏感行為出現(xiàn)的頻率構(gòu)建特征向量。Xu 等人基于組件間通信機(jī)制提出一種新的檢測方法ICCDetector，與基于惡意軟件所需的資源（權(quán)限和敏感API 調(diào)用等）的方法相比，該方法可有效檢測通過利用組件間通信來操作其他應(yīng)用以執(zhí)行惡意行為的惡意軟件。陳鐵明等人提出一種基于抽象Dalvik 指令的靜態(tài)檢測方法，使用N-gram 對抽象的指令序列進(jìn)行編碼，然后結(jié)合機(jī)器學(xué)習(xí)算法構(gòu)造檢測模型?；谡Z法特征的檢測方法，如請求權(quán)限、API調(diào)用、組件、操作碼等，缺乏應(yīng)用程序的行為語義，可解釋性不強(qiáng)，不能有效檢測新出現(xiàn)的惡意軟件。

應(yīng)用程序的行為通過調(diào)用API 函數(shù)實現(xiàn)，因此API 函數(shù)調(diào)用序列可以表征應(yīng)用程序的行為，在現(xiàn)有檢測方法中被廣泛使用。Lei 等人利用事件組來表示應(yīng)用的行為，并將事件組用于神經(jīng)網(wǎng)絡(luò)的訓(xùn)練。該方法利用不同事件中的行為模式來反映應(yīng)用程序可能的運(yùn)行活動，不僅能有效檢測惡意軟件，還能適應(yīng)惡意軟件的演化。陳鐵明等人動態(tài)提取API 調(diào)用序列，并結(jié)合主題模型檢測應(yīng)用程序的行為，但該方法需要運(yùn)行程序來提取序列會消耗大量的時間和資源。MaMaDroid使用馬爾科夫鏈對抽象API 調(diào)用序列建模，以此來提取特征進(jìn)行惡意代碼檢測。Zhang 等人提出基于關(guān)聯(lián)規(guī)則挖掘的檢測方法。首先提取API 調(diào)用序列并對其抽象化，然后使用關(guān)聯(lián)規(guī)則挖掘算法Aprior 來發(fā)現(xiàn)API 調(diào)用之間的關(guān)聯(lián)規(guī)則，最后結(jié)合機(jī)器學(xué)習(xí)算法實現(xiàn)對Android 惡意代碼的分類檢測。但文獻(xiàn)[13]和文獻(xiàn)[14]都只考慮了兩個API 調(diào)用之間的關(guān)系，其序列特征的行為語義偏弱，且提取的特征序列中包含一些與惡意行為無關(guān)的API調(diào)用，影響檢測效率和分檢測效果。Zhu 等人提出一種基于數(shù)據(jù)挖掘的Android 惡意家族分類方法。首先根據(jù)應(yīng)用程序的API 控制流圖提取API 序列，然后計算每個API 序列的支持度，根據(jù)最小支持度獲得每個家族中頻繁出現(xiàn)的API 序列，最后使用頻繁序列訓(xùn)練分類模型。但該方法沒有對API 函數(shù)進(jìn)行篩選處理，以及沒有考慮不同樣本提取的API 調(diào)用序列數(shù)量不同，會對Android惡意代碼檢測產(chǎn)生影響。

為有效檢測Android 惡意代碼，本文提出一種融合行為模式的Android 惡意代碼檢測方法。首先，提取應(yīng)用程序的API 調(diào)用序列，通過調(diào)用序列約簡和調(diào)用序列合并，提取了最長敏感API 調(diào)用序列。然后，定義加權(quán)支持度，在此基礎(chǔ)上提出了改進(jìn)的序列模式挖掘算法，挖掘同類樣本的平衡序列模式，并將不同類別樣本集中挖掘到的頻繁序列模式集合進(jìn)行過濾，作為分類特征。最后，構(gòu)建了機(jī)器學(xué)習(xí)算法的檢測模型。

1 基于行為模式的檢測方法

1.1 方法概述

本文提出了一種基于行為模式的檢測方法，如圖1 所示，主要由三部分組成：預(yù)處理、特征提取和模型訓(xùn)練。首先，對APK 文件進(jìn)行預(yù)處理以提取敏感API 調(diào)用序列；然后，通過序列模式挖掘技術(shù)獲取良性樣本和惡意樣本間不同的行為模式，篩選出具有高區(qū)分度的特征作為分類特征；最后，根據(jù)分類特征生成的特征向量訓(xùn)練和測試機(jī)器學(xué)習(xí)模型。

圖1 檢測系統(tǒng)架構(gòu)Fig.1 Architecture of detection system

1.2 預(yù)處理

函數(shù)調(diào)用圖是一種基于樹的結(jié)構(gòu)，可以表示應(yīng)用程序中API 的調(diào)用關(guān)系，反映程序的執(zhí)行流程。本文選擇通過對應(yīng)用程序的函數(shù)調(diào)用圖進(jìn)行分析，獲取API調(diào)用序列。

通常，惡意軟件的敏感行為是通過調(diào)用特定的API 實現(xiàn)的。這種特定的API 會受應(yīng)用程序的訪問權(quán)限控制來訪問敏感信息（如，用戶電話號碼、位置信息）或執(zhí)行敏感任務(wù)（如，改變手機(jī)的WIFI狀態(tài)、發(fā)送短信），此類API 被稱為敏感API，本文根據(jù)文獻(xiàn)[16]的方法構(gòu)建敏感API集合。

為了獲得API 調(diào)用序列，本文使用靜態(tài)分析工具FlowDroid來分析Android 應(yīng)用程序的數(shù)據(jù)流，以提取應(yīng)用程序的函數(shù)調(diào)用圖（function call graph，F(xiàn)CG）。FCG 可以用一個有向圖表示，=(,)，其中，={v|1 ＜＜}表示應(yīng)用函數(shù)調(diào)用的全部頂點集，v是函數(shù)。?×是有向邊集，邊e=(v,v)表示函數(shù)v對函數(shù)v進(jìn)行調(diào)用。圖2 是一個簡化的函數(shù)調(diào)用圖，其中節(jié)點、、、、、、是抽象的函數(shù)。

圖2 函數(shù)調(diào)用圖Fig.2 Function call graph

應(yīng)用程序的FCG 擁有成千上萬個節(jié)點和邊，若對整個函數(shù)調(diào)用圖進(jìn)行分析會大大增加時間消耗，并且其余的無關(guān)信息可能會降低模型檢測精度。通過對Android 應(yīng)用程序進(jìn)行分析后發(fā)現(xiàn)，程序的敏感行為通常與敏感函數(shù)節(jié)點有關(guān)，而敏感函數(shù)節(jié)點僅占整個FCG 的一小部分。又由于從函數(shù)調(diào)用圖中提取的API 調(diào)用序列存在信息冗余，即某一個API 調(diào)用序列存在于另一個調(diào)用序列中。為了減少冗余信息，降低序列挖掘過程中的復(fù)雜度，本文提出了最長有效敏感API調(diào)用序列提取方法。

在對序列提取方法進(jìn)行詳細(xì)描述之前，對相關(guān)概念進(jìn)行定義。

（調(diào)用序列）序列是不同函數(shù)項的有序排列，序列記為＜…v＞，其中每個v代表一個API 函數(shù)。序列包含的元素個數(shù)稱為序列的長度，長度為的序列記為-序列。

（子序列）序列中多個連續(xù)的項組成的序列稱為該序列的子序列。若存在序列=＜＞包含在序列=＜…a＞中，即?，則序列是序列的子序列。

最長有效敏感API調(diào)用序列提取方法具體如下:

（1）調(diào)用序列約簡

刪除API 調(diào)用序列中非敏感API 節(jié)點，并保留原敏感API 節(jié)點的調(diào)用順序。在函數(shù)調(diào)用圖=(,)中，圖中所有API 調(diào)用序列組成集合，={,,…,s}，若序列∈，=＜…v＞，其中,,是敏感API，序列中其他節(jié)點是非敏感API，則刪除序列中的非敏感API 并保留敏感API 以及調(diào)用順序，得到序列′=＜＞。通過調(diào)用序列約簡，刪除序列集中所有調(diào)用序列的非敏感節(jié)點，得到該文件只含有敏感API的調(diào)用序列。

（2）調(diào)用序列合并

調(diào)用序列約簡后得到APK 文件的所有敏感API調(diào)用序列組成的集合，={,,…,s}。存在序列s,s∈，若s?s，即調(diào)用序列s是調(diào)用序列s的子序列，則從集合中刪除序列s。通過調(diào)用序列合并，得到該文件所有的最長有效敏感API 調(diào)用序列集合′。

對圖2 所示的函數(shù)調(diào)用圖提取最長有效敏感API調(diào)用序列過程如圖3 所示，其中、、為敏感API，通過調(diào)用序列約簡和調(diào)用序列合并，得到了(,,)和(,)兩個序列。

圖3 提取最長有效敏感API調(diào)用序列過程示例Fig.3 Example of extracting the longest valid sensitive API call sequences

1.3 特征提取

經(jīng)過調(diào)用序列約簡和調(diào)用序列合并，生成了最長有效敏感API 調(diào)用序列集合。AprioriAll算法具有很好的序列模式挖掘性能，可以從最長有效敏感API 調(diào)用序列集合中挖掘出區(qū)分度高的調(diào)用序列，該算法的本質(zhì)是通過計算序列的支持度來篩選頻繁序列模式，支持度定義如下：

（支持度(s)）序列s的支持度是該序列集中包含序列s的序列個數(shù)占序列集中總序列數(shù)的比例，即該序列的頻率。

該算法要求樣本的序列數(shù)量分布均勻，否則會產(chǎn)生虛假序列模式，進(jìn)而降低檢測模型的準(zhǔn)確率。假設(shè)一共有100 個同類APK 文件，每個APK 文件的敏感API 調(diào)用數(shù)量均不相同，其中某個APK 文件（A）提取了100 條敏感API 調(diào)用序列，其余99 個APK 文件只提取了一條敏感API調(diào)用序列?，F(xiàn)A 文件的100條敏感API 調(diào)用序列中均包含子序列，而其余99個APK 序列文件中不包含該序列。A 文件中只有一條敏感API 調(diào)用序列包含子序列，其余的99 個APK 序列文件都包含該序列。根據(jù)支持度定義，計算和的支持度都為0.503。

示例中所有APK 文件都包含序列，而只有一個APK 文件包含序列，由此可知，序列更能代表該類樣本的一種行為，序列比更具樣本代表性。然而通過計算發(fā)現(xiàn)子序列和的支持度相同，即序列和具有相同的代表性，但兩個序列的支持度相同，就意味著根據(jù)支持度產(chǎn)生的序列模式與實際不符，導(dǎo)致最終挖掘到的頻繁序列模式不完全具有數(shù)據(jù)集中樣本行為模式的代表性，從而影響分類模型的檢測準(zhǔn)確度。

為此，在實驗樣本中隨機(jī)選取了3 300 個APK 文件的API 調(diào)用序列，對其分析后發(fā)現(xiàn)在這些APK 文件的API 序列中，敏感API 調(diào)用序列數(shù)量在1～10 范圍內(nèi)的樣本約占APK 樣本總數(shù)的34%，10～20 范圍內(nèi)的樣本比例約為28%，20～50 范圍內(nèi)的樣本比例約為25%，50～100 范圍內(nèi)的樣本比例約為5%，大于100 的樣本比例約為2%。分析結(jié)果表明Android 應(yīng)用的敏感API 調(diào)用序列數(shù)量分布不均勻，因此不能直接應(yīng)用AprioriAll算法進(jìn)行序列模式挖掘。

為了解決該問題，本文提出了加權(quán)支持度，并改進(jìn)了AprioriAll算法。

（加權(quán)支持度ws(s)）序列s的加權(quán)支持度是s在類樣本中出現(xiàn)加權(quán)頻率，其計算方法如式（1）所示：

（頻繁序列模式）給定數(shù)值為最小支持度閾值，對于子序列，如果該序列在數(shù)據(jù)集中的支持度大于或等于閾值，即(s)≥，則稱序列s為數(shù)據(jù)集中的一個頻繁序列模式。

改進(jìn)后算法的主要過程為：首先根據(jù)數(shù)據(jù)集獲取其中的候選1-項集，刪除支持度小于設(shè)定的閾值的1-項集得到頻繁1-序列；再由連接剪枝產(chǎn)生候選2-項集,掃描數(shù)據(jù)庫，刪除小于的序列得到頻繁2-序列；最后遞歸掃描直到候選項集為空時停止掃描。改進(jìn)算法的偽代碼如算法1 所示。

改進(jìn)算法的時間復(fù)雜度與原算法相同，均為()，但該算法針對API 調(diào)用序列數(shù)量不平衡導(dǎo)致大量無用序列存在和代表性序列丟失的問題，對候選序列的支持度計算進(jìn)行了優(yōu)化，提高了挖掘的序列特征的有效性。

改進(jìn)的序列挖掘算法

改進(jìn)后的算法應(yīng)用加權(quán)支持度，解決本文提取的API 調(diào)用序列數(shù)量不平衡導(dǎo)致大量無用序列存在和代表性序列丟失的問題；同時保留了挖掘得到的所有長度的頻繁序列模式，保證了序列信息的多元性。相比其他特征形式（單個敏感API 和G-gram 模式等），該算法挖掘到的序列模式更能有效地表示應(yīng)用程序的行為語義。

根據(jù)最小支持度分別挖掘惡意樣本集和良性樣本集的頻繁序列模式集合和。提取出來的頻繁序列模式集合分別是每個類型樣本集中應(yīng)用程序常使用的API 調(diào)用序列。為了區(qū)分良性和惡意樣本，而不僅僅是檢測惡意代碼，對和進(jìn)行過濾，篩選分類特征。過濾規(guī)則如下：刪除同時出現(xiàn)在兩個集合中的序列模式，即分類特征如式（2）所示：

1.4 模型訓(xùn)練和檢測

本文使用過濾后的敏感API 調(diào)用序列模式作為分類特征，根據(jù)該特征為每個樣本構(gòu)建特征向量，若該API 調(diào)用序列模式特征在樣本中出現(xiàn)，對應(yīng)的特征值為“1”，否則為“0”。本文使用了三種不同的分類算法來建立不同的分類模型，包括K 最近鄰（Knearest neighbors，KNN）、隨機(jī)森林（random forest，RF）以及多層感知機(jī)（multilayer perceptron，MLP）。

2 實驗評估

本章將通過實驗來評估本系統(tǒng)檢測惡意軟件的有效性，包括實驗所用的數(shù)據(jù)集和評估指標(biāo)，基于選取的數(shù)據(jù)集對系統(tǒng)的檢測性能進(jìn)行評估，以及與已有的檢測方法進(jìn)行比較。實驗環(huán)境：IntelCorei5-8400 CPU@2.80 GHz 2.81 GHz 處理器，8 GB 內(nèi)存的Windows 10 專業(yè)版操作系統(tǒng)。

2.1 實驗數(shù)據(jù)集和評估指標(biāo)

為了評估提出方法的有效性，本文收集了近1 萬個實驗樣本，其中包含5 000 個惡意樣本和5 000 個良性樣本。實驗數(shù)據(jù)中的惡意軟件從VirusShare（https://virusshare.com/torrents）數(shù)據(jù)集中收集獲得，良性樣本從Google Play Store（http://play.google.com/store）獲得。為了保證實驗中所用樣本都是純凈的，在實驗之前使用VirusTotal（https://www.virustotal.com）對樣本進(jìn)行檢測，剔除惡意數(shù)據(jù)集中檢測為良性的樣本和良性數(shù)據(jù)集中檢測為惡意的樣本。此外，由于本文方法的分類特征基于FCG，無法提取那些反分析應(yīng)用程序的FCG。最終用于實驗的樣本一共有8 838 個（其中4 722 個惡意軟件和4 116 個良性應(yīng)用程序）。實驗中，80%的樣本用于訓(xùn)練模型，20%的樣本用于測試模型。

本文通過準(zhǔn)確率、精度、F 度量等指標(biāo)來評估實驗結(jié)果。這些評價指標(biāo)都是基于混淆矩陣計算得到的?；煜仃嚾绫? 所示，其中和分別是被模型預(yù)測為與原標(biāo)簽相同的樣本數(shù)量，而和分別是被模型預(yù)測為與原標(biāo)簽相反的樣本數(shù)量。真正例率（）是被識別為惡意的樣本占實際惡意樣本數(shù)的比例，=/(+)。誤報率（）是預(yù)測為惡意的良性樣本占良性樣本總數(shù)的比例，=/(+)。

表1 混淆矩陣Table 1 Confusion matrix

根據(jù)混淆矩陣可以計算分類模型的評估參數(shù)，其中準(zhǔn)確率、精度、F 度量的計算由式（3）～（6）確定：

2.2 性能分析

為了證明提出方法的有效性，本文進(jìn)行了多組實驗，包括采用不同的分類器進(jìn)行實驗的對比、序列模式和敏感API 的實驗對比以及本文方法和其他檢測方法的實驗對比。

本文采用三種不同的分類算法來訓(xùn)練分類器，即K 最近鄰（KNN）、隨機(jī)森林（RF）和多層感知機(jī)（MLP），在加權(quán)支持度閾值為0.01 的條件下，三種分類算法的檢測結(jié)果如表2 所示。從表2 中可以看出，在KNN 分類算法中，當(dāng)值為3 時，模型精度在三種分類算法中表現(xiàn)最好，達(dá)到98.55%，而在隨機(jī)森林分類算法中，同樣是精度表現(xiàn)較好，達(dá)到96.20%，但綜合考慮準(zhǔn)確率、精度、F 度量三個評價標(biāo)準(zhǔn)，當(dāng)使用MLP 訓(xùn)練模型時性能達(dá)到最佳，準(zhǔn)確率為94.45%，精度為96.11%，F(xiàn) 度量為94.64%。

表2 不同分類算法檢測結(jié)果Table 2 Detection results of different classification algorithms %

本文使用提取到的25 000 個敏感API 作為特征在同一數(shù)據(jù)集上進(jìn)行實驗對比，實驗結(jié)果如表3 所示。實驗結(jié)果表明，本文通過挖掘不同樣本的行為模式的方法與只使用敏感API 作為特征的方法相比，檢測率更高，并且F 度量達(dá)94.64%。

表3 敏感API與頻繁序列模式的結(jié)果對比Table 3 Comparison of detection results of sensitive API and frequent sequence patterns

本文檢測模型的整個時間開銷分析如下：在提取應(yīng)用程序的最長有效敏感API 調(diào)用序列過程中，平均分析每個樣本需要8.72 s，其中，惡意樣本平均需要4.47 s 完成提取，而良性樣本完成分析需要約12.90 s。序列模式挖掘階段產(chǎn)生比較大的時間開銷，平均每個樣本花費(fèi)16.04 s。在最后的模型訓(xùn)練分類過程中，每個樣本平均需要0.012 s。整個模型中序列模式挖掘這一過程花費(fèi)更多的時間。另一方面，本文的特征提取方法大幅度減少了樣本特征向量的維度，特征向量維度從25 000 縮小到912，減少了96%，模型訓(xùn)練的時間開銷從0.290 s 降到0.012 s，時間開銷減少95.9%，提高了模型訓(xùn)練的時間效率。

為了驗證本文提出的檢測方法的有效性，將本文方法與兩種同類的Android 惡意代碼檢測方法進(jìn)行了對比。其中陳鐵明等人使用N-gram 對動態(tài)獲取的API 調(diào)用序列進(jìn)行特征提取，并引入主題模型對其進(jìn)行建模。張家旺等人提出將權(quán)限和API 調(diào)用組合建立N-gram 特征序列。實驗結(jié)果如表4 所示，與文獻(xiàn)[12]的檢測方法相比，檢測精度高出了4.61個百分點，與文獻(xiàn)[21]的方法相比，檢測精度高出了2.11 個百分點。因此，本文提出的Android 惡意代碼檢測方法在檢測效果上優(yōu)于以上兩種方法，能有效檢測Android 惡意代碼。

表4 本文方法與其他方法的結(jié)果對比Table 4 Comparison between proposed method and other methods %

3 結(jié)束語

本文提出了一種基于行為模式的Android 惡意代碼檢測方法，通過調(diào)用序列約簡和調(diào)用序列合并，提取了最長敏感API 調(diào)用序列。定義了加權(quán)支持度，在此基礎(chǔ)上提出了改進(jìn)的序列模式挖掘算法。采用特征選擇算法，構(gòu)建了調(diào)用模式特征庫，結(jié)合機(jī)器學(xué)習(xí)算法構(gòu)建分類模型。實驗結(jié)果表明提出的方法能夠有效檢測Android 惡意代碼。與使用敏感API調(diào)用頻率作為特征的檢測系統(tǒng)相比，本文使用行為序列模式可以構(gòu)建更高級的語義以發(fā)現(xiàn)應(yīng)用程序潛在的行為模式。與使用所有敏感API 調(diào)用組合來生成對應(yīng)的關(guān)聯(lián)規(guī)則的方法相比，本文方法提取了更多的語義。同時，通過最長敏感API 調(diào)用序列提取方法減少了特征數(shù)量，消除了無關(guān)特征的干擾，提高了檢測的效率和精度。

AprioriAll 算法在挖掘過程中產(chǎn)生大量的候選序列，且需要對序列數(shù)據(jù)庫進(jìn)行多次掃描，時間開銷較大。在未來的工作中，將繼續(xù)對算法進(jìn)行優(yōu)化，進(jìn)一步提高時間效率。