前段時間在烏云知識庫上面看到一篇比較有意思的文章利用機器學習進行惡意代碼分類 。這篇文章對Kaggle上的一個惡意代碼分類比賽中冠軍隊伍所采用的方法進行了介紹，展現了機器學習在安全領域的應用與潛力。但是這個比賽的主題是惡意代碼的分類，沒有進一步實現惡意代碼的檢測；其次比賽的代碼只是針對Windows平臺的PE格式，缺少對移動應用的研究。受此啟發，嘗試利用機器學習方法在Android平臺對惡意代碼進行檢測，最終得到了一定的檢測效果。
目前惡意軟件檢測方法主要有基于特征代碼(signature-based)的檢測方法和基于行為(behavior-based)的檢測方法。基于特征代碼的檢測方法，通過檢測文件是否擁有已知惡意軟件的特征代碼(如一段特殊代碼或字符串)來判斷其是否為惡意軟件。它的優點是快速、準確率高、誤報率低，但是無法檢測未知的惡意代碼。基于行為的檢測方法，則依靠監視程序的行為與已知的惡意行為模式進行匹配，以此判斷目標文件是否具備惡意特征。它的優點可以檢測未知的惡意代碼變種，缺點是誤報率較高。
基于行為的分析方法又分為動態分析方法和靜態分析方法。動態分析方法是指利用“沙盒或模擬器”來模擬運行程序，通過監控或者攔截的方式分析程序運行的行為，但是很消耗資源和時間。靜態分析方法則是通過逆向手段抽取程序的特征，分析其中指令序列等。本文采用靜態分析的方法進惡意行代碼檢測。
Weka（Waikato Environment for Knowledge Analysis），是一款免費的，非商業化基于JAVA環境下開源的機器學習（machine learning）以及數據挖掘（data minining）軟件。Weka存儲數據的格式是ARFF（Attribute-Relation File Format）文件，是一種ASCII文本文件。本文就是將特征數據生成ARFF格式的文件，利用Weka自帶的分類算法進行數據訓練與模型測試。
機器學習中分為有監督學習與無監督學習。有監督學習就是根據訓練集，用學習算法學習出一個模型，然后可以用測試集對模型進行評估準確度和性能。分類算法屬于有監督學習，需要先建立模型。常見的分類算法有：隨機森林(Random Forest)、支持向量機(SVM)等。
Wikipedia上面有APK（Android application package）的介紹。
APK文件格式是一種基于ZIP的格式，它與JAR文件的構造方式相似。它的互聯網媒體類型是application/vnd.android.package-archive;
一個APK文件通常包含以下文件：
所有的文件中需要重點注意的是classes.dex，安卓的執行代碼被編譯后封裝在這個文件中。
區別與JAVA虛擬機(JVM)，安卓的虛擬機稱為Dalvik虛擬機（DVM）。Java虛擬機運行的是Java字節碼，Dalvik虛擬機運行的是Dalvik字節碼。Java虛擬機基于棧架構，Dalvik虛擬機基于寄存器架構。
DVM擁有專屬的DEX可執行文件格式和指令集代碼。smali和baksmali 則是針對DEX執行文件格式的匯編器和反匯編器，反匯編后DEX 文件會產生.smali 后綴的代碼文件，smali代碼擁有特定的格式與語法，smali語言是對Dalvik 虛擬機字節碼的一種解釋。
apktool工具是在smali工具的基礎上進行封裝和改進的，除了對DEX文件的匯編和反匯編功能外，還可以對APK 中已編譯成二進制的資源文件進行反編譯和重新編譯。本文直接使用apktool工具來反匯編APK文件，而不是使用smali和baksmali工具。
#!bash
java -jar apktool.jar d D:\drebin\The_Drebin_Dataset\set\apk\DroidKungFu\xyz.apk
命令執行成功會在out 目錄下產生如下所示的一級目錄結構：
其中，smali目錄結構對應著原始的java源碼src目錄。
Smali是對DVM字節碼的一種解釋，雖然不是官方標準語言，但所有語句都遵循一套語法規范。Dalvik opcodes的詳細說明可以參考這篇文章http://pallergabor.uw.hu/androidblog/dalvik_opcodes.html，里面詳細列舉了Dalvik Opcode 的含義及用法、例子。
由于Dalvik指令有兩百多條，對此需要進行了分類與精簡，去掉了無關的指令，只留下了M、R、G、I、T、P、V七大類核心的指令集合，并且只保留操作碼字段，去掉了參數。M、R、G、I、T、P、V七大類指令集合分別代表了移動、返回、跳轉、判斷、取數據、存數據、調用方法七種類型的指令，對指令進行了一次分類與描述。具體見下圖：
n-gram是自然語言處理領域的概念，但是它也經常用來處理惡意代碼的分析。OpCode N-gram就是對指令操作碼字段提取N-gram特征，n可以取值為2，3，4等。對一個smali格式的匯編文件的OpCode N-gram如下圖所示：
整個系統分兩大部分：建立惡意代碼檢測模型、測試惡意代碼檢測模型。
建立惡意代碼檢測模型如下所示：
用C++寫了幾個程序，對模型建立過程中的數據進行處理：
測試惡意代碼檢測模型如下所示：
用機器學習工具Weka進行模型測試，檢測模型的準確度。得到準確度高的模型可以用來預測未知Android代碼是否為惡意代碼。
實驗數據分為惡意代碼樣本與正常代碼樣本。正常代碼樣本從安卓市場下載；惡意代碼樣本數據來源于Drebin項目，該病毒庫收集了2010年8月至2012年10月178種共5560份APK樣本文件。178種惡意代碼家族的數據量分布如下圖所示：
本文采用540個惡意樣本與560個良性樣本，2個分類，一共合計1100個樣本。分類算法采用隨機森林，150棵決策樹，n取3，進行十折交叉驗證。
準確率如下圖所示，1045個樣本得到正確分類，5個樣本分類失敗。對于malware，其中TPR（真陽性率）=0.981，FPR（假陽性率)=0.08，Precision(查準率) =0.922
ROC曲線效果如下，AUC=0.9923
ROC（Receiver Operating Characteristic）曲線和AUC常被用來評價一個二值分類器（binary classifier）的優劣,具體關于AUC相關知識請參見https://en.wikipedia.org/wiki/Area_under_the_curve_(pharmacokinetics)
