基于權限模式挖掘算法GApriori的安卓應用檢測

郭俊 劉洋 袁潤

（湖南汽車工程職業學院 湖南省株洲市 412001）

1 概述

近年來，Android 系統的市場占有比例越來越大，根據Strategy Analytics 給出的數據可知，2017年第二季度Android 手機的市場份額達到了86.7%，遙遙領先其他操作系統的手機。而Android 操作系統的代碼是完全開源，存在很大風險。因此，許多黑客、惡意代碼開發者熱衷于Android 市場，加上Google 對于Android 應用監管不到位，缺乏嚴密的審查機制，各大論壇和應用商店存在許多惡意應用程序，甚至一些正常的apk 文件也會遭到惡意應用程序[1-2]的侵襲，這些都給用戶造成了一定危害。

有關Andorid 系統的Application 中提供了權限機制。對于Android 惡意應用程序，通過其權限作為判別依據。針對惡意應用程序的權限[3-4]統計，從而得到惡意程序相關權限庫，以此來鑒別安卓市場上的應用程序是否為惡意應用。

以往惡意程序檢測可分成兩類，分別是動態檢測和靜態分析。靜態分析是通過對Android 字節碼進行分析，不需要運行軟件，只需抽取其自身特征[5]，然后對應用程序相關的常量特征進行檢測，并由此判斷程序是否為惡意。靜態分析的共同點即不需要執行應用程序，對于Android 平臺的應用程序采用簽名靜態比對，該方法簡單且實用，但也存在比較大的缺點，需要對惡意軟件的信息提前知曉，例如相關權限、簽名等，因此它不能對惡意程序自動識別。而另一類是動態檢測，它需將整個程序封裝在一個密閉環境中，得到程序核心行為特征[6]。

通過對被動采集的參數進行分析，例如線程與進程間運行情況、權限改變情況以及對系統調用情況等。因為動態檢測需要對應用程序運行，還需較長的時間采集動態數據，所以它相比靜態分析更復雜，但是效率更高，更精準。

相比前兩種檢測技術，本文提出了一種基于GApriori 算法的技術。基于GApriori 算法對Android 惡意應用的檢測，利用傳統的Apriori 算法[7]逐層迭代候選產生找出頻繁項集，構建權限關系特征庫T；隨后對權限關系特征庫聚類[8-9]去冗余得到典型權限關系特征庫T'。最后，通過對檢測應用程序匹配T'來檢測未知惡意應用，幫助用戶及時發現潛在惡意應用程序，并且能夠高效、快速發現惡意應用程序。

2 權限頻繁挖掘算法GApriori

2.1 關聯規則產生

關聯規則即是找出數據之間的內在聯系，從而挖掘出一些對用戶有用的信息[10-11]。衡量數據之間的相關性，關聯規則需從支持度、置信度作出判斷，只有支持度和置信度都滿足設定要求，才能認為數據之間存在著關聯性。以下是對關聯規則產生的相關分析。

已知集合N={n1,n2,...nk}，其中每個元素稱為數據項，N={n1,n2,...nk}稱為項集，對N={n1,n2,...nk}中的數據長度稱為項集長度，對k 個長度的項集表示為k-項集。設D 是交易T 的集合，T 是項集，設X 是N 的項集，如果稱T 包含X。

關聯規則的支持度表示包含X，Y 的交易數和全部交易數之比，其公式如（1）所示：

關聯規則的置信度表示包含X，Y 的交易數和包含X 的交易數之比，其公式如（2）所示：

即指包含X，Y 的交易數和。

2.2 GApriori算法基本步驟

（1）對事務數據庫進行掃描，根據支持度計數迭代產生頻繁項集，首先找出頻繁1 項集，記作N1。

（2）通過設定最小支持度min_up，由N1找出頻繁2 項集，記作N2，再由N2找出頻繁3 項集，記作N3，依次類推，直到找不到第K 項集為止。

（3）采用剪枝步對K 項集計算，得到頻繁項。

（4）對頻繁項集聚類去冗余，得到典型頻繁項。

（5）根據典型頻繁項集產生關聯規則。

其中頻繁項集的產生如下所示，假設某個數據庫包含5 個事務，事務用TID 表示，每個事務包含許多數據項N1，N2，N3，N4。

對數據庫進行掃描，得到1 維候選項集，記作L1。

表1：四種檢測方法對比圖

根據支持度計數和最小支持度min_up 比較候選集，刪除支持度計數小于3 的候選集{N4}，由L1得到2 維候選項集，記作L2，對數據庫進行再次掃描，找出2 維候選項集的支持度計數。

根據支持度計數和最小支持度min_up 比較候選集，刪除支持度計數小于3 的候選集{N1，N2}和{N2，N3}，只剩下{N1，N3}這組符合要求，至此，迭代結束。

3 GApriori算法具體實現

GApriori 算法具體實現分為兩個步驟，第一個步驟是獲得頻繁項集，第二步驟對頻繁項集聚類去冗余得到典型頻繁項集。

獲得頻繁項集L 之后，可能有些數據相關性比較強，針對產生的頻繁項集中某些數據相關性比較高，可以去除這些數據，從而得到典型頻繁項集L'。用戶行為、權限特征作為離散型特征，采用互信息熵理論聚類去冗余的算法，其相關計算公式如下所示。

X，Y 是頻繁項集L 中的兩個隨機變量，公式（3）H(X)表示變量X 的信息熵[9]，p(x)表示x 的先驗概率。

公式（4）H(X,Y)表示X，Y 聯合熵[12-13]

公式（5）H(X/Y)表示條件信息熵[12-13]

公式（6）IG(X/Y)表示信息增益值[12-13]，即變量X 熵增的減少反映了在變量Y 存在的情況下，X 增加的信息度，如果IG(X/Y)>IG(Z/Y)，表示X 和Y 的相關性要大于Y 和Z 的相關性。

公式（7）sin(X,Y)表示特征X 和Y 特征之間的相關性。相關度sin(X,Y)的取值在0-1 之間，0 表示不存在相關性，1 表示完全相關性。

圖1：各方法檢測時間對比圖

對（7）式樣本中得到的權限聚類去冗余，剔除相關性強的數據。其具體算法如下：

Input：權限關系特征庫T。

Output：典型權限關系特征庫T'。

（1）取出T 中的任意一個權限，記住作P1權限簇。

（2）查看P1與T 中其他任意權限的相關度距離sin(X,Y)，并與自己設定的閾值η 進行比較，若sin(X,Y)小于η，則把該權限加入當前權限簇,否則舍棄該權限。

（3）判斷T 中剩余權限是否已加入任意權限簇P(P1,P2,...Pk)，如果存在，則需重新建立權限簇Pi，并返回（2）。

（4）對P 進行遍歷。

至此，對權限特征的預處理結束，從而形成新的典型權限關系特征庫T'，屬性維數較少，并且權限之間相關性低，同惡意軟件分類決策相關性高。

4 實驗結果分析

為保證實驗結果的合理性和代表性，選取了國內Android 應用商城52580 個應用程序作為樣本空間，其中不同的應用程序有47820 個。分別通過靜態分析[4]、動態檢測技術[5]、Apriori 算法[6]和GApriori 算法的檢測得到表1，根據檢測的時間得到圖1。

從表1 中的數據可以看出，對于Android 應用商城的52580 個應用程序靜態掃描分析后，可以確定49 個惡意軟件，檢測比例為0.09%，檢測時間266 秒。

動態檢測分析后，發現了126 個惡意程序，檢測比例為0.24%，檢測時間160 秒。

GApriori 算法檢測后，發現了347 個惡意程序，檢測比例為0.65%，檢測時間100 秒。檢測效率是靜態分析的7.4 倍，是動態分析的2.9 倍。GApriori 算法檢測技術通過改進Apriori 算法，能快速地檢測出惡意軟件，可以大大減輕后期人工分析惡意程序特征的工作，Apriori 算法是Agrawal R 等人提出的布爾關聯規則的頻繁項集的原創性算法。GApriori 算法對49 個惡意家族1260 個惡意程序挖掘出頻繁模式的權限關系特征庫，再對權限屬性聚類，獲得典型權限關系特征庫，進一步減少冗余，這樣提高了檢測的準確性和快速性。

根據表1 的數據得到折線圖1，從圖1 中可以看出，GApriori算法隨著樣本數據的增加，檢測所需的時間越來越短，其次是Apriori 算法，再次是動態分析，最慢是靜態分析。當樣本數據達到6000 個時，靜態檢測以后不隨樣本數據的增加而發生變化，始終保持勻速；當樣本達到16000 個時，GApriori 算法增長速率變緩，Apriori 算法增長速率變快，其他兩種增長速率幾乎不變，由此可以得出，GApriori 算法隨著樣本的增加大大提升了檢測速率，達到了預期效果。

5 結束語

針對應用商城存在的一些惡意應用程序，本文提出了GApriori算法檢測技術，通過Apriori 算法得到權限頻繁項集，構建權限關系特征庫，從而對其聚類去冗余得到典型權限關系特征庫，對53080 個應用程序進行檢測。最后，通過多個實驗和其他檢測方法進行對比，實驗結果證明了該算法的高效性和準確性。下一步將研究如何提高聚類去冗余算法的效率，進一步完善該檢測方法。