改進隨機森林在Android惡意軟件檢測中的應用

熊 健，覃仁超，何夢乙，劉建蘭，唐風揚

西南科技大學 計算機科學與技術學院，四川 綿陽621000

近年來智能手機已迅速成為極為流行的計算平臺，使用智能手機的人群日益龐大。其中Android操作系統在智能手機操作系統市場占領絕對優勢，成為使用量最多的移動端操作系統。此外，其開源性和開放性也使得它成為了越來越多黑客的攻擊對象。《2018 年中國手機安全狀況報告》[1]顯示，360互聯網安全中心在當年共截獲約434.2萬個新增Android惡意應用樣本，平均每天新增約1.2 萬個。為減少Android 惡意應用給用戶帶來的危害和損失，Android 惡意軟件的檢測成為近年來一項熱門的研究。

國內外針對Android惡意應用檢測方法做出了許多研究。目前分析Android應用的技術主要包括靜態檢測和動態檢測技術。靜態檢測技術就是在不執行應用的條件下，利用反匯編分析的技術。由于其具有不需執行應用、檢測開銷低等優點成為了眾多學者采用的方法[2]。?ahin等人[3]對權限進行了系統地分析并提出了給權限分配權重的方法，采用k近鄰（KNN）和樸素貝葉斯（NB）方法與已有的研究進行比較；Westyarian 等人[4]提出了利用API 類來檢測Android 惡意軟件，并使用機器學習來區分惡意應用，使用交叉驗證和百分比分割測試來驗證分類的準確性；Ju[5]提出一種靜態檢測的方法，該方法利用程序的權限和包；Yuan等人[6]提出了一種基于貝葉斯分類的Android 應用程序自動分類的有效方法，從應用程序本身和Android market 中提取出應用的權限和字符串作為分類特征；Li等[7]提出一種基于靜態分析的方法，通過提取權限和API 調用函數作為特征來訓練支持向量機（SVM）算法；Arp[8]提出一個靜態分析Android 應用框架，從AndroidManifest 文件中提取一組功能，并通過反匯編代碼生成特征向量，將SVM應用于數據集來識別惡意應用；基于靜態分析的DROIDMAT[9]分析AndroidManifest 文件，提取應用程序的不同功能，例如權限和意圖消息，然后標記了應用程序組件、活動、服務和接收者作為初始點來跟蹤和權限有關聯的API調用，并應用K-means 算法對惡意應用進行分類檢測；Chan 等人[10]提出了一個包含Android 惡意軟件靜態檢測權限和API 調用的特征集。其中，文獻[3]只選取了Android 軟件的權限作為特征，特征選取過于單一；文獻[4]選擇了Android 軟件的API 函數作為特征，選擇范圍比較片面；文獻[5-10]雖然采用了多種特征結合，并運用相應機器學習技術進行檢測，但檢測精度都不夠高。綜上所述，目前Android 惡意軟件檢測的研究成果在檢測效率和精度等方面還有待進一步提高。

本文提出的Android 惡意軟件靜態檢測模型，采用基于行為的靜態分析技術，提取權限、四大組件、API調用以及程序的關鍵信息如動態代碼、反射代碼、本機代碼、密碼代碼和應用程序數據庫等11 個類別作為特征屬性，并對屬性使用信息增益算法（Information Gain，IG）進行優化選擇，通過對比共選取65 個分類特征，先采用有監督的機器學習算法對Android程序進行檢測分類并比較它們之間的精確度，通過對比選擇精確度最高的隨機森林（Random Forest）算法，采用加權投票機制對其進行改進，并將其應用于本模型的惡意軟件檢測分類當中。通過實驗證明，本文提出的模型在有效提高Android惡意軟件檢測效率上具有一定的可行性。

1 Android應用基礎

Android 操作系統基于Lniux 內核，主要由Linux 內核、Android 中間件和應用層三部分構成，如圖1 所示。Linux 內核層位于最下面一層，是系統庫層與硬件之間的橋梁，提供一系列的核心系統服務，負責硬件抽象和驅動程序等；Android中間件層包括應用架構層、Android運行時和系統庫。該層為上層的應用提供了必要的運行環境，為Android系統提供了核心功能；應用層提供了許多API，方便開發人員使用來開發應用程序。

圖1 Android操作系統框架

Android應用程序有四個基本組件：活動（Activity）、廣播接收器（Broadcast Receiver）、內容提供商（Content Provider）和服務（Service）。其中活動組件用于聲明一個實現應用的部分可視化用戶界面；廣播接收器是接收廣播通知的組件，用于實現消息的發布與訂閱；內容提供商用于實現數據共享，為程序間的數據訪問提供接口；服務長期運行在后臺，提供一系列系統服務。

Android 應用程序APK 文件是由JAVA 語言編寫的壓縮安裝包文件，它包含了程序的所有內容。APK文件的主要組成有：META-INF 目錄、assets 目錄、res 目錄、AndroidManifest.xml文件、classes.dex文件、resources.arsc文件。其中META-INF 目錄主要存放校驗文件；assets目錄存放在封裝到APK文件中時要保持原始文件形式的文件；res 目錄主要用來存儲與圖形界面有關的資源文件；AndroidManifest.xml 文件是存儲Android 應用配置的文件，包含如包名、權限列表及組件聲明等信息；classes.dex文件擁有程序的全部邏輯實現；resources.arsc文件是一個已被編譯過的索引文件，用來記錄ID 與資源文件之間的關系。

2 隨機森林算法

2.1 算法分析

隨機森林（RF）算法是由Breiman和Adele開發的一種集成學習算法[11-12]，該算法對Bagging 算法進行了擴展，結合了Bagging和隨機子空間方法，可以用來處理分類問題和回歸問題等。在Bagging 中，通過使用輸入數據的bootstrap 樣本單獨構建每個分類器。在常規決策樹分類器中，劃分屬性是選擇當前結點屬性集合的一個最優解。而在RF 中，首先在結點的屬性集合中隨機選擇一個子集，該子集包含m個屬性，然后再從這個子集中選擇一個最優屬性。這種對于特征的隨機選擇不僅可以在每個特征向量包含許多特征的情況下，使用RF很好進行縮放，而且還可以減少特征屬性之間的相互依賴性（相關性），從而更不容易受到特征內在噪音的影響。RF 算法的流程如圖2 所示，隨機森林算法偽代碼如下。

輸入：樣本集N

For b=1←B

1. 從原始數據N中有放回地抽取bootstrap樣本記為Z

2. 對bootstrap 樣本進行建模并生成決策樹T，生成過程遵循下述原則：

1.1 從所有樣本N中隨機選取M個屬性

1.2 從這M個屬性中選擇最佳分割屬性作為分裂點

1.3 重復以上兩個步驟建立k棵決策樹

end for 輸出：決策樹集合組成隨機森林

圖2 RF算法流程示意圖

3. 使用上述的隨機森林對樣本進行分類檢測，采用簡單投票原則算出最終的分類結果

2.2 算法特點

RF算法簡單易實現、計算開銷小，并且因為其在現實任務中展現出來的強大性能，被譽為“代表集成學習技術水平的方法”。RF 中基學習器的多樣性不僅來自于樣本擾動，還來自屬性擾動，這就使得該算法比單個分類器具有更好的泛化能力和分類效果。通過平均決策樹，具有抗過擬合能力。RF非常穩定，即使數據集中出現了一個新的數據點，整個算法也不會受到過多影響，它只會影響到一棵決策樹，很難對所有決策樹產生影響。但是，RF算法在投票選舉的時候無法區分強、弱分類器之間的差距也存在著可以改進的地方，下面將對其進行改進。

3 改進的隨機森林算法

對于分類任務來說，最常見的預測策略是使用投票法。RF算法采取的是簡單投票原則即將同樣的權值賦值到每棵決策樹上，從而忽略了不同分類器之間強弱的差異，無法增強隨機森林中分類性能優秀和削弱分類性能欠佳的決策樹對分類結果的影響。因此，本文采用加權投票原則對RF 算法進行改進，形成改進的隨機森林（Improved Random Forest，IRF）分類器。具體步驟如下。

（1）首先使用Bagging算法從原始數據集（記為N）中有放回地抽取樣本，形成一個樣本集。因此，會存在一些未被抽取到的樣本，這一部分樣本稱為OOB（Out-Of-Bag）數據，OOB數據中每個樣本沒有被抽到的概率為那么N→∞時p≈0.368，表明沒有被抽中的樣本的概率有36.8%。設X為測試樣本集，x為它的一個樣本；T為訓練完成的決策樹分類器集合，t為當前的決策樹；C為分類結果集合，其中c是C中的一個分類。

（2）將OOB數據輸入到T中，得到每棵決策樹對OOB數據正確分類的比率CRt，作為相應決策樹的權重。

（3）對樣本x使用RF進行檢測分類并加權統計，屬于Malware類的總得票數記為S，則：

（4）選出得票最多的類別C作為樣本x的最終類別，即：

如果按照傳統隨機森林算法采取的簡單投票原則對最終分類結果進行決定，這樣會導致分類性能優秀的決策樹和分類性能欠佳的決策樹擁有相同的權重，從而導致分類性能優秀決策樹的能力得不到充分發揮，而分類性能欠佳的決策樹又對最終分類結果帶來一定的負面影響，從而導致最終的分類結果存在偏差。本文采用改進的隨機森林算法能夠避免上述情況對隨機森林的分類能力帶來的負面影響，增強了森林中分類性能優秀的決策樹在投票中所占的比重，同時削弱了分類性能欠佳的決策樹在投票中所占的比重，對比傳統的隨機森林算法在分類性能上具有一定的優勢。

4 靜態檢測模型

圖3為本文所提出的Android惡意軟件靜態檢測模型結構，共包括5個模塊：反編譯模塊、特征提取模塊、生成特征向量模塊、特征屬性優化模塊和檢測分類模塊。

圖3 Android惡意代碼靜態檢測模型

模型處理過程設計如下：

（1）使用AndroGuard 工具反編譯樣本集中的APK文件，生成對應的AndroidManifest.xml文件和smali文件。

（2）使用Python 模塊分別對permission、activity、provider、receiver和service、API調用、動態代碼、反射代碼、本機代碼、密碼代碼和應用程序數據庫進行屬性值提取，將提取的屬性值保存為文本文件格式，以便后續將其向量化。

（3）在獲得幾大類特征集合后，就要將其映射到向量空間中。運用Python 模塊實現將特征文本文件轉化為特征向量，生成相應的特征向量集合。

（4）使用IG 算法對處理后的特征向量集合進行優化，選取IG值更高更有代表性的65項特征屬性，生成特征優化向量集合。

（5）使用機器學習分類算法對上述優化后的向量集合進行分類檢測，同時檢驗分類的準確性。

4.1 特征選取

Android安裝包（以下簡稱APK 文件）是Android軟件通過打包過后生成的一個相當于壓縮包的文件，但是無法閱讀其直接解壓后里面包含的內容，因此需通過反編譯APK文件獲取其中的信息。為了獲取應用的特征用于機器學習分類算法進行分類檢測，本文采用Andro-Guard工具（https://github.com/androguard/androguard）對APK 文件進行反編譯分析，將應用程序APK 文件以AndroidManifest.xml 和Java 類的形式反編譯為其源代碼，使用Python 模塊從源代碼中解析所需的特征，表1顯示了部分所需的特征。AndroGuard 是用于第三方Android 應用程序的靜態分析工具，該工具可分解應用程序并使用其API訪問其組件。

表1 提取的Android移動應用程序部分特征

為了保證安全性，Android 系統會通過權限機制來限制應用程序能夠訪問的資源，應用程序必須通過用戶授權才能使用某種權限。雖然權限機制在一定程度上增強了系統的安全性，但是用戶最終的權限授予選擇取決于他對權限的關注和理解程度。調查發現，用戶很可能因為迫切需要使用某些應用而忽視權限帶來的風險，從而有可能被惡意軟件利用權限來實現其惡意目的，并有多種方式來執行此操作。因此，權限可以作為反映該應用是否可能存在惡意行為的特征；應用程序通過四大應用組件可以實現相應的功能，四大應用組件在另一方面又可以顯示應用程序在運行中與其他應用程序或系統資源間的交互情況，從而能夠有效反映出應用程序在運行過程中可能進行的操作。因此，本文也選取了四大組件作為特征屬性；Android框架提供了大量的API，這些API的組合調用不僅可以用于良性軟件的開發，還可用來實現惡意的行為：訪問用戶隱私信息、發送惡意扣費短信等。調查發現，惡意軟件對一些高危API的調用次數遠遠高于正常的應用，這在一定程度上可以真實地反映一個應用程序的行為特點，根據這些行為特點可以判別該應用是否存在著惡意行為。因此，本文將一些API調用作為一個識別惡意應用的特征依據；加密代碼可以反映APK 文件是否采取了加密措施，如果在應用程序中檢測到與密碼代碼相關的代碼，則在二進制向量生成階段將is_crypto_code 字段設置為1，否則為0；is_dynamic_code 字段表示檢測類的動態加載，如果在應用程序中檢測到dexClassLoader 方法，則在二進制向量生成階段將字段值設置為1，否則為0；is_native_code字段值表示使用本機庫的應用程序。Native 庫包含本機代碼，這些本機代碼被編譯為二進制代碼并直接在操作系統上運行。通過在應用程序中檢測LoadLibrary方法可以檢測是否使用了本機代碼；is_reflection_code 字段表示應用程序使用反射來動態調用方法，如果在應用程序中檢測到Reflection 方法，則在二進制向量生成階段將字段值設置為1，否則為0；如果在程序中檢測到與數據庫連接，在二進制向量生成階段將字段值設置為1，否則為0。以上字段能在基于傳統特征的基礎上在一定程度上反映應用程序的行為特點，從而可以判斷該應用是否存在著惡意行為。通過實驗發現，采用上述多特征結合相比只采用傳統特征，提高了識別惡意應用的精確度。因此，本文也選取了程序的關鍵信息作為特征屬性。

4.2 生成特征向量

使用集合S表示包含所有特征屬性的并集，如公式（3）所示：

其中集合S1～S11分別表示Android 應用程序中的系統權限、四大組件、API調用和程序關鍵信息的屬性集合，并且通過Python 模塊保證集合中元素的唯一性。利用并集S，定義一個|S|維的向量空間φ，其中的元素要么是0要么是1。

因此，提取某一特征屬性類別X（比如系統權限）下所有Android應用程序的特征屬性并映射到向量空間φ中可由公式（4）表示：

其中，當函數I(x,s)=1 時表示當前應用程序x包含特征s，當函數I(x,s)=0 時表示當前應用程序x不包含特征s。

本文中每個特征屬性類別所包含的APK應用數量不止一個，如表2所示，當APK應用數量較多時，同一類別下的每一個APK的特征描述都必須在同一向量空間中表示出來。

表2 向量空間存儲格式

其中，第一行表示當前功能類別（如系統權限）的所有屬性特征，Class屬性為標記，其余每一行表示對一個APK 應用的特征描述，1 表示當前APK 包含對應的屬性，0 表示不包含，true 標記當前APK 應用為正常軟件，false標記當前APK應用為惡意軟件。

本文選取了標簽項中的17 個屬性值，標簽項中的16 個屬性值，標簽項中的7 個屬性值，標簽項中的3 個屬性值，標簽項中的8 個屬性值，標簽項中的9個屬性值，is_crypto_code，is_dynamic_code，is_native_code，is_reflection_code和is_database等共計65個屬性值作為分類檢測的特征屬性，將其保存為.arff格式的特征向量集合。

4.3 特征優化

特征優化是對于數據進行預處理中的關鍵一步，它的目的是為了消除特征冗余的同時選取相關度比較大的特征，為后續的分類檢測提高其精度以及效率。具體設計如圖4所示。

圖4 特征屬性優化模塊

4.3.1 信息熵

假設X是一個離散型隨機變量，即它擁有有限范圍的取值范圍R={x1,x2,…,xm}，其中xi出現的概率為Pi，設Pi=P{X=xi}，則X的信息熵定義如公式（5）所示：

本文使用信息熵來描述分類事件中出現的不確定性，即分類事件X可能擁有的信息量，那么信息熵越大，獲得的信息量就越多。如果某事件X已經確定一定發生或者不發生，那么得到的信息量為0，當事件X發生的概率為0.5 時，將會得到最大的信息熵。因此對于本文中的分類情況來說，只有當正常和惡意樣本數量所占比例均為0.5時，才能取得最大的信息熵，從而獲取更多的信息量。因此，為了保證獲取最大的信息量，本文采集APK 應用時，始終保持正常應用與惡意應用的數量保持均勻分布。

4.3.2 信息增益

本文通過計算特征集中的每一個特征下分類事件的信息熵來確定每一個特征對于分類事件的不確定性和影響大小，即條件熵。如公式（6）所示：

設X、f是兩個離散隨機變量，隨機變量X條件下f的條件熵H(X|f)表示隨機變量f在已知隨機變量X的條件下發生的不確定性。其中離散變量X的取值可能為{true|false}。

當且僅當H(X|f)=H(X)時，表示在包含特征f的條件下對事件X的判斷無任何影響。否則，只要H(X|f)≥0，特征f對于事件X的判斷就會產生不同程度的影響。

本文采用信息增益來進行特征的選擇優化，即增加了特征f之前與之后，事件X的信息熵之差，如公式（7）所示：

使用IG(X,f1)表示在包含特征f1的情況下判斷成正常應用的信息量IG(X=true,f1)，或者在不包含的情況下判斷成惡意應用的信息量IG(X=false,f1)。同理，可以使用IG(X,f2)來衡量在包含或不包含特征f2的情況下其對于分類任務的貢獻價值。依次類推，分別計算出特征集合中每個特征對于分類任務的可用價值，信息增益越大，代表該特征的可用價值越高，隨后對所有特征的信息增益值進行排序，選擇值更大的特征作為優化后的特征，即可完成特征選擇過程。

4.3.3 特征屬性優化

根據上述IG算法對已提取的特征集合進行優化選擇。根據排序結果，生成對應的優化特征向量集合OFVS.arff。表3 展示了特征屬性數量分別為55、65、75的時候采用隨機森林算法進行分類檢測時的效果對比。

表3 選取不同數量特征屬性采用RF算法分類效果對比

通過表3 可以看到，當特征屬性數量為65、75 的時候效果最好，但特征屬性數量為75 時比特征屬性數量為65 時占用了更多的系統開銷，所以通過信息增益算法選擇65個特征屬性來進行分類檢測。

4.4 分類檢測

將優化后的特征向量集合OFVS.arff分為測試集和訓練集兩類作為輸入，對訓練集采用機器學習分類算法進行訓練同時對測試集進行檢測分類。首先，采用樸素貝葉斯（Naive Bayes，NB）、K最近鄰（K-Nearest Neighbor，K-NN）、Bagging、決策樹（J48）、隨機樹（Random Tree，RT）、隨機森林（Random Forest，RF）分類器對模型進行訓練，并采用現目前流行的十倍交叉驗證技術（K-fold Cross Validation）[13]來評估分類器的性能。即將訓練集劃分為10 個相等并且沒有交集的子集，在每次訓練中將1 個子集作為測試集，剩余的9 個子集用作訓練集，最后以10 次訓練結果平均值作為檢測分類器最后的分類性能。接著使用改進的隨機森林（IRF）分類器對特征優化向量進行分類并檢測。最后對比其分類性能。

5 實驗

5.1 實驗樣本與配置

為了證明本文提出方法的有效性，本文共選取了12 000 個Android 應用文件作為數據集進行分類檢測實驗。其中，6 000 個良性APK 應用來自于國內第三方Android 應用市場；6 000 個惡意APK 應用來自于VirusShare.com提供的惡意軟件樣本集。本文進行實驗的軟件和硬件配置如表4所示。

表4 實驗環境配置

5.2 評估指標

假設TP（True Positive）表示將正常應用樣本正確識別的數量，TN（True Negative）表示將惡意應用樣本正確識別的數量，FP（False Positive）表示將惡意應用樣本誤判為良性的數量，FN（False Negative）表示將正常應用樣本誤判為惡意的數量。即可得到如下分類器評估指標參數：

（1）真陽率（TP Rate，TPR），表示被正確分類的正常應用與數據集中所有正常應用數量的比值。

（2）真陰率（TN Rate，TNR），表示被正確分類的惡意應用與數據集中所有惡意應用數量的比值。

（3）假陽率（FP Rate，FPR），表示被誤判的惡意應用與數據集中所有惡意應用數量的比值。

（4）假陰率（FN Rate，FNR），表示被誤判的正常應用與數據集中所有正常應用數量的比值。

（5）準確率（Accuracy），表示分類器的分類性能。

5.3 實驗結果

為了評估所提出模型的性能，使用Weka中集成的6種數據挖掘算法：樸素貝葉斯（NB）、K近鄰（K-NN）、Bagging、決策樹（J48）、隨機樹（RT）和隨機森林（RF）算法，采用10 折交叉驗證方法對4.3.3 小節中生成的優化特征向量集合進行分類檢測。實驗以測量指標的形式促進了對各種機器學習分類器的分類性能的更好了解，這些指標包括真陽率（TPR）、假陽率（FPR）、準確度（Accuracy）、召回率（Recall）、F 值（F-Measure）和ROC曲線（ROC Area）。

將特征向量集合分為均等的10份，輪流將其中的1份用作測試集，剩下的9 份用作訓練集，并且對10 次的實驗結果求平均值。通過實驗，可以得出RF 算法的檢測效率最高，接著對RF算法進行改進，將IRF算法集成到Weka 中，對數據集進行分類檢測。幾種機器學習分類算法的檢測結果如表5所示。

表5 不同分類器的分類效果對比

從表5 可以看出，使用6 種機器學習分類算法進行分類檢測都有較好的準確率，其中對于惡意軟件檢測能力最弱即TPR值最低的是NB分類器，其針對惡意軟件的檢測率僅為89.1%，而IRF 算法對于惡意軟件的檢測效果最好，檢測精度達到了98.1%。因此，鑒于本文選擇機器學習分類器的應用開銷均相對較低，通過實驗結果可以表明本文所提出的Android惡意軟件檢測模型是切實可行的方案，能夠有效提高Android 惡意軟件檢測的有效性和準確性。

5.4 實驗結論

提出的方法在經過實驗論證后，與以往的研究方法相比主要有以下幾方面的特點：

（1）對比以往對Android 惡意代碼檢測技術采用的傳統特征，本文在傳統特征的基礎上增加了程序的關鍵信息等特征，能夠充分發揮多特征在Android 惡意代碼檢測中所起的作用，提高了對惡意應用的識別率。

（2）通過對比幾種常見分類器的分類效果，選取分類效果更好的隨機森林算法，對其采用加權投票機制進行改進，能夠更大程度上提高檢測的精確度。

（3）實驗使用了大量的真實樣本，使得實驗結果更有說服力。

（4）通過使用Androguard 中相應的函數以及編寫Python代碼，縮短了樣本特征的提取及向量化時間。

6 結束語

本文針對目前移動設備的惡意應用不斷增長，給人們帶來了巨大的危害，比如經濟損失或泄露隱私等情況，提出一種利用多特征、基于改進隨機森林算法的Android惡意軟件靜態檢測模型。模型采用基于行為的靜態分析技術，提取權限、四大組件、API調用以及程序的關鍵信息如動態代碼、反射代碼、本機代碼、密碼代碼和應用程序數據庫等11 個類別作為特征屬性，并對屬性采用IG 算法進行優化選擇，通過對比共選取65個分類特征，最后先采用有監督的機器學習算法對Android程序進行檢測分類并比較它們之間的精確度，通過對比選擇精確度最高的RF 算法采用加權投票機制進行改進，并將其應用于本模型的惡意軟件檢測分類當中。通過實驗表明，本文提出的模型相比目前Android 惡意軟件檢測技術具有較好的檢測效果。

本文提出的Android惡意軟件檢測模型還存在著一些需要改進的地方：（1）本文研究采用了權限、組件、API調用信息和程序的關鍵信息作為特征，在下一步工作中將會考慮更多的特征比如敏感函數對等信息；（2）本文只收集了12 000 個Android 應用程序安裝包，如果能夠收集到更大的數據集可以得到更為精確的檢測結果；（3）下一步考慮結合動態檢測技術來減少惡意軟件的識別率與誤報率；（4）在分類檢測方面考慮采用深度學習等技術進一步提高準確率。下一步工作將會針對以上不足進行研究分析。