基于集成學習投票算法的Android惡意應用檢測

趙宇鑫，努爾布力，艾 壯

1.新疆大學 軟件學院，烏魯木齊830046

2.新疆大學 網絡中心，烏魯木齊830046

3.新疆大學 信息科學與工程學院，烏魯木齊830046

1 引言

根據Gartner 公司的統計，截至2017 年，Android 智能手機操作系統的市場占有率已經達到85.9%。Android系統受到了市場的青睞，這與其開源的特性密不可分。隨著基于Android系統二次開發的操作系統和手機數量的增長，Android平臺逐漸成為攻擊者的主要目標，系統自身和應用程序的安全問題變得越來越嚴重。爆炸式增長的應用市場的管理因此成為一種新興的涉及惡意應用程序檢測的關鍵問題。隨著Android惡意應用檢測技術的發展，越來越復雜的惡意應用逃避系統檢測。因此，Android 應用程序市場的管理需要有效的方法來檢測惡意程序。應用程序市場通常會根據應用程序開發人員指定的類別或通過分析應用程序開發人員提供的描述對應用程序進行分類。惡意應用的開發人員很容易操縱這個過程來逃避檢測。并且隨著應用數量的激增，快速準確地自動分類應用程序從而提高管理效率，變得至關重要。

在這種背景下，本文提出了一個新的模型，以便在檢測惡意應用程序方面有效地管理應用商店中的大量應用程序。應用商店從每個APK（Android Application Package）文件中提取大量功能，并使用這些功能來表示應用程序的行為。一般來說，惡意應用的行為與良性應用程序的行為不同。例如，惡意應用程序可能會請求其功能上不需要的權限。某個類別中的良性應用程序的行為也與其他類別的行為區別開來。從所有的應用程序中，總共提取了2 374 348 個功能[1]，分為11 種類型。為了提高檢測和分類的效率，使用SVM-RFE（Support Vector Machine Recursive Feature Elimination）根據功能對檢測的重要性對其進行排名。然后，使用包括SVM（Support Vector Machine）、K-NN（K-Nearest Neighbor）、NB（Na?ve Bayes）、CART（Classification and Regression Tree）和RF（Random Forest）在內的五個分類器的集合來檢測惡意應用程序。在該模型框架的最終實驗中，使用MASV檢測方法實現了99.27%的檢測精度。

2 基本概念及相關工作

2.1 定義

2.1.1 指示函數

Π(·)為指示函數，當·為真時輸出1，為假時輸出0。定義如下：

2.1.2 特征排序和排名標準

特征選擇是通過窮舉出所有的特征子集，選擇滿足給定“模型選擇”標準的最佳特征子集。但由于子集的組合數量龐大，窮舉出所有的特征子集不切實際，可以回歸到一種實際可用的方法，首先將特征數量減少到可管理的大小，其中特征排序算法比較有競爭力，可實現。

特征排序算法顧名思義就是通過對每個特征依照某種標準進行評估，對每個特征進行打分或賦權值，選擇出固定數量排名最高的特征進行下一步的分析或設計分類器。本文用到的SVM遞歸特征消除算法是依照敏感性分析對特征進行排名，具體原理如下。

OBD（Optimal Brain Damage）算法作者LeCun[2]提出使用成本函數DJ(x)代替權重作為修剪特征的標準：

對于線性判別函數J 與ωi的二次函數是等價的，最小值時可以表示為：

該公式進一步證明[3]可以使用(ωi)2作為排序標準。

2.1.3 梯度上升算法的目標函數和代價函數

梯度上升算法的目標函數為：

其中，θi(i=0,1,2,3,4,5)為梯度上升模型參數，也是該算法的輸出；xi(i=1,2,3,4,5)為每個樣本的基分類器輸出的正確率值，增加一個特征x0=1。

代價函數J ：

其中，yj設為1，m 代表迭代次數，使得代價函數J 最大化，對應的θ 就是最優參數。

2.2 背景

計算機系統和網絡的安全性是一個廣泛討論的主題，因為目前對系統或網絡基礎設施的攻擊是主要威脅?，F已提出了許多方法來確保系統安全[4-6]和網絡安全[7-12]。

2.2.1 基于權限檢測Android惡意應用程序

本文工作的動機是確保Android 應用程序的安全性。目前，檢測Android 惡意應用程序的工作主要集中在靜態特征的分析[13-19]或動態特征[20-22]的分析。由于Android權限限制API（Application Programming Interface）的調用，所請求的權限可以表現應用程序的部分行為。Pandita 團隊[17]提出WHYPER，采用自然語言處理技術來解釋為什么應用程序需要某些權限。在之前的調研工作中，Wang團隊[23]根據風險對權限進行了排名，并系統地研究了Android權限在檢測惡意應用程序方面的表現。Barrera 等人[24]調查了1 100 個最受歡迎的應用程序，發現這些應用程序只需要小部分權限，還發現應用類別和權限之間的關系不是非常密切。Chia 團隊[25]和Felt 團隊[26]研究列出了Android 應用中最常用的權限。Enck 等人[27]開發了一個工具，該工具通過將Android 應用程序請求的權限與預定義的權限列表進行匹配來檢查應用程序是否是惡意的。Zhou 團隊[28]提出了一種基于行為足跡的權限方案，用于檢測已知Android 惡意軟件家族的新樣本，并應用基于啟發式的過濾方案來識別未知惡意家族的某些固有行為。

2.2.2 基于API調用和功能檢測Android惡意應用程序

Shabtai等人[29]研究靜態分析技術來解析Android源代碼，他們還應用機器學習技術，通過從Android應用程序中提取的靜態功能對游戲和工具進行分類。La Polla等人[30]概述了移動設備安全方面的相關工作。Nath等人[31]比較了用于分析Android 惡意軟件的各種機器學習技術。Lindorfer等人[32]介紹了MARVIN，這是一種利用機器學習技術以風險評分的形式評估未知Android應用程序的系統。Peiravian團隊[33]通過權限和API調用來檢測出惡意應用程序。Pirscoveanu 等人[34]開發了一個分布式Android 惡意軟件測試環境。Amin 團隊[35]調查了惡意應用的性質和身份，并提出了基于網絡和系統調用的檢測方法。Apvrille 等人[36]用Alligator 結合了幾種分類算法，提取了代碼級的功能，并對未知應用進行了分類。

目前的檢測方法在某些方面存在不足。首先，所使用方法是基于應用程序的權限與應用的類型比較來判斷該應用程序是否是惡意應用程序，不能應對新類型的Android應用程序，適應性較差且誤報率較高。其次，僅使用基于機器學習單分類器的Android惡意應用檢測雖然在檢測速度上略有優勢，但檢測的正確率并不是很高。

2.3 基于應用程序功能的特征提取

本文根據Arp 等人[13]提出的Android 功能特征提取方法，對Android 應用程序進行靜態分析。通過線性掃描應用程序的XML（eXtensible Markup Language）文件以及反編譯的dex 代碼提取有效特征。為了進行通用和可擴展的分析，將所有提取的功能表示為字符串集，例如權限、廣播和API調用。提取以下11組字符串[1]。

2.3.1 程序清單中的功能集

為Android開發的每個應用程序都必須包含一個名為AndroidManifest.xml的清單文件，該清單文件提供支持該應用程序安裝和執行的數據。使用Android Asset Packaging Tool可以在設備上有效地檢索此文件中存儲的信息，該工具能夠提取以下數據集：

FS1 組件名稱：大多數Android 惡意應用程序都是經過重新打包的合法應用程序[37]，攻擊者將相同的惡意有效負載（通常在組件方面）插入到許多不同的合法應用程序中。將組件名稱作為功能集包含在內，以捕獲良性和惡意應用程序中出現的組件重用行為。

FS2 請求的權限以及FS3 硬件和軟件要求：應用程序嘗試訪問哪些資源對于檢測惡意軟件非常重要。在Android系統中，請求的權限（FS2）以及硬件和軟件要求（FS3）指示應用對系統資源的需求。權限請求模式可以表現應用程序的資源訪問意圖。在數據集中，使用了Android平臺和第三方應用程序定義的所有權限。硬件和軟件要求（FS3）是指Android應用程序使用元素標簽在其清單文件中向設備傳達其硬件和軟件要求。因此，提取了Android 文檔[38]中定義的硬件和軟件特征描述符作為第3個特征集。

FS4 過濾后的廣播：Android 平臺將廣播用作應用程序的消息傳遞對象，并且平臺可以將其發送到另一個應用程序的組件以請求操作。惡意應用程序通常使用廣播過濾器進行聲明，以接收特定的系統事件（例如BOOT_COMPLETED）來激活惡意活動。在這項工作中，將樣本清單文件中的所有廣播過濾器提取為功能集。

2.3.2 反編譯代碼中的功能集

Android 應用程序是用Java 開發的，并被編譯為Dalvik 虛擬機的優化字節碼。該字節碼可以有效地反匯編，并提供有關API調用和應用程序中使用的數據信息。使用基于Android 平臺的dex 庫的反編譯程序，可以輸出應用程序中包含的所有API調用和字符串。

FS5 受限的API 調用和FS6 使用的權限：請求權限并不意味著該應用程序實際上訪問了相應的資源。掃描應用程序樣本的反編譯代碼，并記錄它們是否調用某些受保護的API。另外，使用PScout[39]提供的API 權限映射來獲取使用的權限。使用的權限和受限制的API調用反映了應用程序實際在不同程度級別上訪問的資源。

FS7證書信息：應用開發人員必須使用證書對自己的APK 文件簽名，該證書的私鑰由他們自己持有。該證書有助于將開發人員與其他開發人員區分開。可以從證書中提取開發人員信息，例如國家/地區、電子郵件地址、組織、州或省以及SHA-1指紋。

FS8源代碼中的URL、IP地址、文件路徑和數字：通過正則表達式模式匹配，收集了反編譯代碼中的所有URL、IP 地址、文件路徑字符串和數字（三位數以上）作為功能集。這些字符串可能涉及許多惡意行為。

FS9 有效負載信息：有效負載指APK 存檔中的文件。將有效負載信息作為功能集包含在內，是因為某些惡意應用程序在主機應用程序中包含額外的.apk文件，誘騙用戶安裝這些惡意.apk文件，并且惡意應用程序為了避免引起懷疑，可以將文件擴展名從.apk或.dex更改為.png。

FS10代碼模式：在此功能集中，檢查應用程序是否動態加載.dex 文件或Linux 本地代碼，應用程序是否執行shell 命令，應用程序是否使用Java 反射機制以及應用程序是否調用密碼功能等。

FS11 可疑的API 調用：受Drebin[13]的啟發，提取了某些API 調用，這些API 調用允許訪問敏感資源，例如訪問設備ID，發送和接收惡意應用程序經常使用的SMS消息。

本文以Android 應用程序的功能為依據進行分類，借鑒機器學習中集成學習的方法，提出了MASV檢測方法。由于Android 應用程序功能特征龐大，本文先使用SVM-RFE 算法對特征的重要性進行排序，去掉一些對訓練模型不重要的特征。同時，針對集成學習加權投票的權重選擇耗時較長的問題，使用梯度上升算法訓練并得出每個基分類器的權重。MASV 檢測方法集合了每個基分類算法的優點，提升了檢測方法的適應性和準確率，同時減少了集成學習模型的訓練時間，提高了效率。

3 MASV集成方法

3.1 綜述

本文提出了一個模型框架MASV來過濾大量Android應用程序，從而檢測惡意應用程序。如圖1 所示，在將應用程序輸入模型后，從APK 文件中提取大量功能特征。如果通過MASV將其識別為惡意應用，則會觸發警報。具體步驟如下：

步驟1 將待檢測的Android 應用程序功能特征使用SVM-RFE 算法進行重要性排名，淘汰不重要的樣本特征。

步驟2 將選擇后的特征矩陣輸入五個基分類器。

步驟3 根據五個基分類器的預測結果輸入到訓練好的集成學習加權投票分類器中，得出分類結果。

步驟4 根據分類結果判定該Android 應用程序的性質，結束。

3.2 基于SVM-RFE的特征選擇

在檢測惡意應用程序時，提取和選擇功能始終很重要。在這項工作中，通過靜態分析技術從應用程序中提取靜態特征。靜態分析技術是指分析代碼特征，例如語法、詞典、數據流和控制流。與在應用程序運行時從系統中提取功能的動態分析相比，應用靜態分析會消耗更少的資源和時間，并且不需要執行應用程序。由于有大量的應用程序集，因此更專注于靜態分析以確保檢測效率。

通過靜態分析，從所有應用程序中提取2 374 340個功能，具體數量如表1所示。由于功能的數量太大而無法有效處理，本文使用SVM-RFE 算法根據其對檢測的重要性對每個特征的權重進行排序。SVM-RFE算法[3]的過程如下：

表1 功能集（特征選擇前）

（1）訓練分類器（優化權重ωi以使得J 最優）；

（2）計算所有特征的排序標準(DJ(i)或(ωi)2)；

（3）刪除具有最小排序評分的功能。

該迭代循環是消除排名最差的一個過程。出于計算效率的原因，一次刪除多個功能特征可能更為有效，但會降低分類器的評分結果。在這種情況下，該方法產生與特征排名相反的特征子集。

如果一次刪除一項功能特征，會有一個相應的功能排名。但排名最高（最后淘汰）的功能不一定是最重要的特征，因為一些功能特征可以和其他互補功能特征很好地區分數據。

通常，SVM-RFE采用的是線性核函數，推廣到多維特征向量的應用場景，需要采用非線性核函數。本實驗采用的是RBF核函數。

SVM-RFE（RBF核）算法描述如下所示：

進而將線性SVM應用于惡意應用程序檢測并實現SVM 模型，其中每個特征的標簽由其在區分良性應用和惡意應用方面的有效性決定。權重為正的特征被視為“惡意特征”，而權重為負特征被視為“良性特征”。一些權重等于0，表明它們對分類沒有貢獻，因此可以在分析中刪除。如圖2 所示，實驗測試了1 000～46 000 個特征每隔3 000特征的ACC值，發現當特征數量為34 000個時，ACC值最高。最后使用34 630個功能，用于執行惡意應用和良性應用程序的分類。經過特征選擇后的特征指標如表2所示。

圖1 MASV集成框架

圖2 各特征數的ACC值

表2 功能集（特征選擇后）

3.3 基于分類器的檢測

MASV檢測方法使用了五種基分類器，五種分類器的原理及優缺點如表3所示。

3.4 基于集成學習的加權投票算法

為了發揮每種算法的優勢并進一步提高檢測和分類的準確性，通過五種分類算法的對比，在獲得上述五種算法的分類結果后，采用多分類器的集合進行多數表決。軟投票，即一種加權投票法，其做法就是以每個基分類器測試結果的正確率為權重，對每個類進行加權平均，取得分最高的類別作為分類結果。

加權投票算法如下所示。

對于訓練樣本D，其中x 為訓練樣本值，在本文中就是Android應用程序功能特征值，y 為樣本x 所對應的標記?；鶎W習器L1,L2,…,L5在本文中實際有五種，也就是五種基分類器（SVM，RF，NB，K-NN，CART）。ht表示基學習器Lt在樣本x 上的輸出。輸出結果為標記空間C 中的一個值，本文為二分類問題，只有兩個值，正例標記為-1，反例標記為+1。其中Π(·)為指示函數，詳見第2.1.1小節。加權投票法的輸出為：

3.5 基于梯度上升的權重選擇

梯度上升是一個用來求目標函數最大值的算法，最優的路線是沿著該函數的梯度方向探尋。傳統集成學習加權投票法首先對每個基分類器測試結果的正確率進行計算，然后以正確率作為權重，對每個類概率進行加權平均，得分最高的類作為分類結果。本文對此權重選擇方法進行了改進，使用各基分類器10 次交叉驗證的正確率（ACC）結果組成訓練集，將其作為梯度上升算法的輸入，將步長α 設置為0.001，可以快速得到各基分類器加權投票的權重。

表3 五種分類算法對比

本文使用梯度上升算法來求出集成學習加權投票的權重，目標函數hθ和代價函數J ，詳見第2.1.3 小節。使代價函數J 最大化，對應的θ 就是最優參數。

θi的更新公式如下：

其中，α 為步長。

梯度上升的偽代碼如下所示：

輸入：多分類器輸出結果集D={(x1,y1),(x2,y2),…,(xm,ym)}

1. 初始化所有θ=1,α=0.001,y=1

2. for 1,2,…,m do

6. end for

輸出：θi

4 實驗評估

4.1 實驗環境和應用程序集

在實驗過程中，實驗環境使用Windows 系統，具有四核的Xeon CPU和64 GB內存的服務器。使用Python編寫的scikit-learn 軟件包作為實驗中的機器學習工具包，因為它可以在各種環境中訪問和重用，且配置簡便。

本文使用由良性應用程序和惡意應用程序組成的大型應用程序集來驗證本文提出的MASV 方法。應用程序數據來自北京交通大學Wang團隊[1]所整理收集的2014 年和2015 年的Android 應用功能集。該數據集總共231 619個應用程序，包括213 256個良性應用程序和18 363個惡意應用程序。使用VirusTotal標記良性應用程序，如果VirusTotal 中的防病毒引擎不足以將該應用視為惡意應用，會將其視為良性應用。數據預處理中將App 樣本轉換為LIBSVM 格式，每行描述一個App 樣本，第一列表示分類標簽，其余列表示功能特征。本實驗使用欠采樣，去掉部分良性樣本，使得惡意樣本和良性樣本數量平衡，最終使用的數據集良性樣本和惡意樣本數量如表4 所示。分層選擇80%的樣本作為訓練數據，其余20%的樣品作為測試數據。根據應用市場的分類，目前獲取的APK數量如表5所示。

表4 實驗數據集切分

表5 應用程序數據集分類描述

4.2 實驗設計

首先，本文實驗將數據集的80%作為訓練集，20%作為測試集，再將訓練集分為訓練集和驗證集，采用十折交叉驗證的方法對分類器進行訓練，這樣做是為了對模型參數調優。其次，為了提高SVM分類器的效率，本文使用SVM-RFE算法對數據特征的重要性進行了全局排名。然后，使用梯度上升算法，將五個基分類器的輸出結果的準確率作為梯度上升算法的輸入，對集成學習加權投票的參數ω 進行預估。最后，通過加權投票算法訓練模型，使用測試集得出預測值。

本文的實驗方法較Wang團隊[40]提出的檢測方法有所不同。首先，本文使用的集成學習投票方法是加權投票方式，較多數投票方式在準確率上有所提高。其次，本文率先使用了梯度上升算法確定每個分類器的權重，原理是基于訓練時的準確率求最優解問題。為了檢驗MASV的檢測效果，本文使用五種基分類器作為對比實驗進行分析，并和同樣使用應用程序功能特征作為研究對象的幾種方法進行了比較。

4.3 評價指標

在本文的實驗中，分類器結果的評估通過表6混淆矩陣中的各項數值，分別計算出準確率（ACC）、正確率（PRE）、召回率（REC）以及F1值（F1-score），計算公式如下：

表6 分類結果混淆矩陣

4.4 模型訓練參數

對于SVM 分類器的評估實驗，在所有實驗中選擇線性核函數。參數ωi，即每個類別的權重，被指定為與每個類別中的樣本數成反比。另一個參數c，錯誤懲罰參數，設置為0.25。

特征的數量是CART的重要參數，將此參數設置為默認值，因為使用默認值時精度最佳。在設置決策樹深度這一參數時，對決策樹深度取100～1 200 分別進行了對比實驗，如圖3所示，結果在TreeDepth=1 000 時正確率最高，ACC=96.89%。

圖3 CART的樹深度參數比較

將K=3 設為K-近鄰的參數。如圖4 所示，ACC、PRE、F1-score 的數值都隨K 值的增加而遞減，只有REC 值隨K 值的增加而增加，但K 為3～15 時的REC值變化不大，取K=3 使得K-NN的正確率、準確率、F1值都獲得一個較為不錯的結果。

圖4 K-NN的K 值參數比較

決策樹的數量是RF 的一個重要參數，因為在尋找最佳分割時需要考慮這些參數。通過幾次實驗來平衡效率和準確性，并將決策樹的數量設置為100，如圖5、圖6 所示。對于樸素貝葉斯分類算法，在實驗中選擇MultinomialNB模型。

圖5 RandomForest的決策樹數量參數比較

圖6 RandomForest的決策樹數量參數比較

集成學習投票算法SVM、RF、NB、K-NN 和CART分類器的權重為ω1,ω2,ω3,ω4,ω5,使用本文提到的梯度上升算法得到的結果分別為0.772，0.157，0.001，0.044，0.027。

4.5 實驗結果與分析

五種分類器和集成學習方法的惡意應用程序檢測結果如表7所示?？梢钥闯觯琒VM分類器的準確率ACC在五個基分類器中是最高的，達到98.93%。評估結果表明，除NB算法外，各算法的檢測準確率非常相似。從表7 還可以看出，SVM 算法和RF 算法的檢測結果非常接近。一般來說，RF 算法的實驗檢測結果優于CART算法，因為RF 算法也是一種基于決策樹的集成學習方法，實驗結果也證明了這一結論。NB 分類算法準確率最低，只有61.63%，正確率PRE 僅有61.99%，這也說明貝葉斯模型不適合分類Android應用程序功能特征。

表7 各分類器實驗結果 %

采用具有軟投票機制的五種分類器集合后，本文的MASV 方法在檢測惡意應用程序方面達到了99.27%的準確率。通常，本文的集成方法優于基本分類器SVM、RF、NB、K-NN和CART。

4.6 與其他方法比較

表8所示是Drebin、LR（Logistic Regression）、Droid-Ensemble 和本文方法的對比結果。通過和同樣使用應用程序功能數據集的其他方法比較，可以看出MASV方法在TPR（True Positive Rate）上有較大優勢，但本實驗結果的FPR（False Positive Rate）略低于其他方法，如圖7、圖8所示?？梢缘贸?，本實驗檢測良性樣本的正確率較為有效，因為本文惡意樣本數量多于其他方法，所以FPR 略有偏高，但不明顯。綜上所述，本文這種集成學習加權投票算法的檢測效果優于Drebin[13]使用的SVM方法、Wang 團隊[1]使用的LR 方法和使用多數投票的DroidEnsemble[40]方法。

表8 MASV與其他方法比較

圖7 檢測方法的TPR比較

圖8 檢測方法的FPR比較

5 結束語

本文提出了一個檢測惡意應用程序的模型框架，將惡意應用程序用于五個分類器的集合模型分類，旨在簡化Android 應用程序市場的管理。給定一個應用程序，本文的模型框架從應用程序中提取大量功能，然后使用這些功能來檢測它是否是惡意的。如果被識別為惡意應用程序，則會觸發警報。否則，它將被歸類為良性應用程序類別。本文采用五個分類器的集合，即SVM、K-NN、NB、CART和RF，集成學習軟投票算法用于檢測惡意應用程序和良性應用程序的分類。實驗結果表明，MASV 在檢測和分類方面比五個基本分類器更穩健。在惡意應用程序檢測實驗中，本文的集成方法實現了99.27%的檢測精度。

在未來的工作中，計劃探索更多信息功能，以更好地體現應用程序的行為，提高惡意應用程序和良性應用程序的分類效果。目前，還在研究設計更有效的方法以針對惡意應用進行分類，以及使用分布式計算減少模型訓練時間。