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

1.重慶大學 計算機學院，重慶400044

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

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

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

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

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

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

1.1 方法概述

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

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

1.2 預處理

函數調用圖是一種基于樹的結構，可以表示應用程序中API 的調用關系，反映程序的執(zhí)行流程。本文選擇通過對應用程序的函數調用圖進行分析，獲取API調用序列。

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

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

圖2 函數調用圖Fig.2 Function call graph

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

在對序列提取方法進行詳細描述之前，對相關概念進行定義。

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

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

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

（1）調用序列約簡

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

（2）調用序列合并

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

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

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

1.3 特征提取

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

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

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

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

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

為了解決該問題，本文提出了加權支持度，并改進了AprioriAll算法。

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

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

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

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

改進的序列挖掘算法

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

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

1.4 模型訓練和檢測

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

2 實驗評估

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

2.1 實驗數據集和評估指標

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

本文通過準確率、精度、F 度量等指標來評估實驗結果。這些評價指標都是基于混淆矩陣計算得到的。混淆矩陣如表1 所示，其中和分別是被模型預測為與原標簽相同的樣本數量，而和分別是被模型預測為與原標簽相反的樣本數量。真正例率（）是被識別為惡意的樣本占實際惡意樣本數的比例，=/(+)。誤報率（）是預測為惡意的良性樣本占良性樣本總數的比例，=/(+)。

表1 混淆矩陣Table 1 Confusion matrix

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

2.2 性能分析

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

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

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

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

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

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

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

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

3 結束語

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

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