一種基于模糊哈希的Android變種惡意軟件檢測方法

王文沖，凌 捷

廣東工業(yè)大學 計算機學院，廣州 510006

1 引言

惡意代碼已經成為當今計算機系統(tǒng)中最嚴重的安全威脅之一。在Android移動平臺中，惡意軟件的數(shù)目與日劇增。據(jù)2016年第二季度MaAfee Labs統(tǒng)計數(shù)據(jù)表明，新增移動端惡意軟件數(shù)量近200萬，相比于第一季度增長了14%，而總數(shù)量則高達1 100萬[1]。面對著如此龐大的數(shù)字，需要有一個高效快速的方法，來自動對大量的應用軟件進行掃描并檢測。傳統(tǒng)的商業(yè)安全軟件中，為了能夠具備更高的實時檢測速度，大都是通過提取字符串作為特征碼。在檢測過程中，安全軟件只需直接判斷其是否擁有與已知特征碼相同的字符串[2]。然而，這種基于字符串的特征碼提取方法有著一定程度上的不足，就是難以檢測到多態(tài)變形的惡意軟件[3]。

當前Android惡意軟件檢測及分類方法總體可以分為兩大類：（1）基于特征碼的惡意代碼檢測方法。（2）基于機器學習算法的惡意代碼檢測方法?；谔卣鞔a的檢測方法是通過判斷待檢測軟件中是否擁有與已知惡意代碼相匹配的API或者字符串等字節(jié)碼數(shù)據(jù)來實現(xiàn)的。這種方法具有極高的檢測速度，但是很容易遭受代碼混淆攻擊[4]?；跈C器學習的檢測方法[5-8]則是通過提取出應用程序的行為特征，如權限請求、關鍵API等信息，并運用機器學習算法來對大量的樣本數(shù)據(jù)進行分類檢測。然而這些方法都沒有結合實際的語義進行分析，因此很大程度上會出現(xiàn)檢測錯誤。因為即使是具備相同的API集合但是調用次序的差異將會直接導致整個軟件行為極大的不同。

為了解決此類問題，部分學者提出了對應用軟件進行語義分析，以圖表的形式來表示整個應用軟件中代碼間的調用情況。文獻[9-11]是直接將已知待檢測應用軟件調用圖與惡意代碼庫中調用圖進行匹配，當一致時則表明為惡意軟件。然而，直接利用這種精確匹配的方法難以抵抗代碼混淆攻擊[12]，并且無法檢測出未知惡意軟件。隨后很多學者在此基礎上對該方法進行了改進，其中，文獻[13]提出一種度量各API調用圖間相似度的方法，能夠有效地檢測出各類多態(tài)變形軟件。文獻[14-15]利用消息標記的方法來跟蹤應用程序代碼中敏感信息的流向。文獻[16]則利用調用圖來反向跟蹤敏感行為觸發(fā)的上下文環(huán)境。然而，直接利用這種利用調用圖的分析方法，在檢測的時候，需要對整個文件邏輯進行分析，極大地降低了檢測效率，特別面對復雜調用圖匹時，其計算復雜度急劇增長。因此該類方法并不適用于當今巨大的病毒樣本。文獻[17]中利用機器學習的方法來提取Android應用程序中所使用權限的特征，并用于惡意代碼檢測。在文獻[18]中則是利用數(shù)據(jù)挖掘中神經網(wǎng)絡算法來對惡意代碼行為進行分析。文獻[19]以大量的樣本數(shù)據(jù)為基礎，從中提取與已知惡意軟件的特征，并利用這些特征來用于對新樣本的檢測。而文獻[20]則是根據(jù)每個應用程序的執(zhí)行權限、API調用流程等特征，利用KNN算法來對不同種類的應用程序進行分類。隨后的文獻[21-23]相繼使用SVM、貝葉斯等算法來實現(xiàn)惡意軟件的分類。然而，這種基于機器學習的方法是從統(tǒng)計學的角度去提取特征，很容易出現(xiàn)誤檢現(xiàn)象。

目前為止，仍未能夠有一種有效的方法來對未知惡意軟件進行檢測，很大程度上依賴于人工分析來實現(xiàn)。然而，由于惡意軟件的數(shù)量與日俱增，其中存在大量的變種病毒。因此需要有一種快速高效的方法對未知的樣本進行過濾，從而來降低人工分析成本。針對此問題，Jesse等人[24]利用模糊哈希算法來識別檢測相同類別的惡意軟件。然而該方法只能對相似文件進行檢測，一旦文件結構出現(xiàn)變化，將無法檢測。在此基礎上，本文通過自動化提取Apk中字符串以及函數(shù)長度分布信息來生成模糊哈希值，具有更高的抗干擾性，同時通過簡化病毒庫來提高檢測速度。

2 基本思路

在本文中，首先對Apk字符串以及函數(shù)長度這兩方面的信息特征提取，并將其映射為模糊哈希值的形式，使得相同種類的惡意軟件之間具有相似的哈希值。再將已知的惡意軟件樣本生成的模糊哈希值作為特征庫，用于對變種的檢測。同時為了提高檢測效率，在病毒庫中使用k-means算法對其進行聚類，并將每一類別的質點來代表該種類中其他所有的變種病毒，從而簡化整個病毒庫，并提高檢測效率。系統(tǒng)框架如圖1所示。

圖1 系統(tǒng)框架流程圖

3 惡意特征提取方法

在Apk中不同應用程序所使用的字符串以及函數(shù)長度的分布情況都不一樣，然而對于同一種類的變種Apk中只是對少部分字符串以及功能函數(shù)做修改。因此，將字符串以及函數(shù)長度分布這兩方面來作為特征信息，用于對變種病毒的識別。分別如下：

（1）字符串特征，提取出應用軟件中特有的字符串信息。文獻[25]中通過提取將PC端應用軟件中字符串來對惡意軟件進行分類，并取得較好的效果。本文在此基礎上，根據(jù)Apk字節(jié)碼的結構特點，并結合布隆過濾器（Bloom Filter），提出一種高效字符串的特征向量生成方法。

（2）函數(shù)長度分布特征，即提取代碼中不同長度函數(shù)的數(shù)量各自所占比例信息。在這一部分將文獻[26]所提出的方法做稍微修改并應用到Android平臺的應用軟件中。

字符串以及函數(shù)特征所生成的向量組合在一起，從而生成該應用程序對應的模糊哈希值。由于在同一個Apk中包名進行字符串混淆時，常使得字符串特征向量出現(xiàn)變化，但其函數(shù)特征向量仍然不變。同樣的，在某些Apk包中函數(shù)數(shù)量較小時，彼此函數(shù)特征向量的彼此距離并不明顯。因此，將兩種特征向量結合，并作為該Apk包的模糊哈希值，能夠更為準確地描述整個Apk包，并使得相同種類的Apk包具有相近的模糊哈希值。

3.1 模糊哈希算法相關理論

文本中常包含大量的信息，對其進行比較時常需要在高緯度空間中查找最近鄰關系。特別是當文本較大時，其計算復雜度以及存儲空間將劇增。為了解決此問題，需要對文本進行降維處理。運用具有局部敏感特性的哈希函數(shù)h，將文件映射為低維數(shù)據(jù)，并以散列值的形式來表示。對文件相似性比較時，期望內容近似但數(shù)據(jù)并不完全相同的源文件擁有相似或相同的哈希值。

記高維空間中存在任意兩個數(shù)據(jù)點x,y，其度量函數(shù)為d(x,y)，給定兩個距離d1,d2(0

其中，p1＞p2，則稱h為模糊哈希函數(shù)。

通常使用對文件進行分片的形式來實現(xiàn)，并使用高效檢索哈?；蚣用芄Ｋ惴ㄓ嬎愠雒恳黄墓Ｖ?，最后將所有分片的哈希值串聯(lián)起來作為文件的哈希值進行比較。分片哈?？梢詫⒐Ｖ档淖兓拗圃谖募热莅l(fā)生變化的分片之內，而保持其他分片的哈希值不變。本文將在此基礎上提出一種針對Apk包的模糊哈希值產生方法，使其具有更高的計算速度以及抗干擾性。

3.2 字符串特征提取方法

在Apk應用程序中，每一種類別Apk都會有自己特有的字符串信息，在此通過解析dex文件可以提取其所使用的字符串，圖2為某一Apk包中所使用的部分字符串列表。

圖2 字符串列表

不同應用程序所使用的字符串都不一樣，然而對于同一種類的變種Apk中只是對少部分字符串做修改，它們彼此含有大量相同的字符串。因此，可以將字符串的相似程度來作為特征來實現(xiàn)對變種應用程序的識別。

然而，直接對每個應用程序中所有字符串進行匹配，來計算彼此包含的相同字符串的數(shù)量是很不現(xiàn)實的。因為每個Apk包中字符串的數(shù)量成千上萬個，時間復雜度高達O(n2)。

在本文中，使用哈希算法，將Apk中所有字符串映射成一個特征向量。當兩個Apk含有相同字符串越多，其對應的特征向量間距離越小。

記Apk中字符串集合為：

哈希函數(shù)為Hash(x)，使其滿足：

圖3 字符串映射

具體實現(xiàn)算法如下：

算法1字符串特征向量生成

輸入：初始化Apk字符串集合S。

輸出：特征向量SV。

該算法中，首先提取出應用程序所包含的所有字符串，再利用哈希函數(shù)Hash（）來計算各個字符串的哈希值，再將特征向量中該哈希值所對應的位置數(shù)值加1。從而得到該Apk的字符串特征向量SV={sv1,sv2,…,svm}。

3.3 函數(shù)長度分布信息提取

每個不同的Apk應用程序包中所包含的函數(shù)數(shù)量以及各個函數(shù)的長度均有所不同，在此以函數(shù)中所包含指令的字節(jié)數(shù)來表示其的長度。

下面通過解析Apk中dex文件來獲取各個函數(shù)的長度，并根據(jù)長度從大到小的順序對函數(shù)進行排序，如圖4所示。其中每一個點的坐標(x,y)表示第x個函數(shù)的長度值為y。圖中藍色與綠色分別表示兩個不同Apk包中函數(shù)的長度分布情況。

圖4 函數(shù)長度分布圖

在此，同樣需要將Apk包的函數(shù)分別特征映射為特征向量的形式。

記Apk中各個函數(shù)的長度集合為：

其中 fi表示第i個函數(shù)的長度，n為Apk中包含的函數(shù)數(shù)量，且 fi≤fi+1，1≤i≤n。

根據(jù)應用程序中函數(shù)的長度特征，選取指數(shù)模型(y=aekx+b)來表征各個區(qū)間的取值范圍，其中a,b,k為常數(shù)，x=1,2,…,m。記函數(shù)的最大長度為L，記為 fn,為了滿足y(0)=1,y(m)=L,在此可令a=1,b=0,k=ln(L)/m。則此時每個區(qū)間記為：

其中，x=0,2,…,m-1。

下面以一個例子來說明，設某一Apk應用程序中函數(shù)長度分布分別為：（2，2，3，6，8，8，10，11，15，20，24，33，45，70，77，132）。

其最大值L=132，分組數(shù)m=4。此時各個區(qū)間分別為：

[1，3.4），[3.4，11.5），[11.5，38.8），[38.8，132）

因此，其函數(shù)分布特征向量：FV={3,5,4,4}。

4 特征病毒庫生成及變種檢測

本文結合前面提到兩種方法分別來提取應用程序的字符串特征以及函數(shù)特征，并用于生成模糊哈希值。由于同一變種惡意軟件中常常具有相同或相似的字符串或函數(shù)長度分布特征，因此，在對變種病毒進行檢測時，通過利用模糊哈希值之間的距離計算即可，當彼此具有相近的距離時，表示檢測到變種病毒。

令模糊哈希值FH=(SV,FV)，并以曼哈頓距離來度量兩個模糊哈希值間的相似程度。

記兩個模糊哈希值分別為：

則，其距離定義為：

對變種病毒進行檢測時，直接通過對模糊哈希值間距離的計算即可匹配到相似的Apk，極大地提高了檢測效率。

在實現(xiàn)對變種惡意軟件檢測時，首先計算病毒庫中樣本的模糊哈希值FH，利用k-means算法對模糊哈希值進行聚類，并將聚類后各類別的質點來代表該類中其他所有點。當需要對未知的惡意軟件進行檢測時，只需計算該惡意軟件的模糊哈希值與各類別的質點之間的距離，當距離小于某一閾值時，則說明該惡意軟件屬于某一類別病毒的變種。這樣可以無需對病毒庫中所有模糊哈希值進行距離的計算，極大地提高了檢測速度，且壓縮病毒庫的存儲空間。

利用模糊哈希值以及k-means算法來生成能用于檢測變種的病毒特征庫。

算法2病毒樣本特征庫生成

輸入：變種家族數(shù)k，模糊哈希值集合{FH1,FH2,…,FHN}，N為樣本數(shù)量。

輸出：病毒樣本特征庫V。

1.隨機選取 k 個聚類質點為 μ1,μ2,…,μk

2.重復下面過程直到收斂

對每個樣本i，計算其所屬家族類

對每一個家族類 j，重新計算質心

3.將所有質點μ添加到特征庫V中

以質心代表整個樣本族中所有樣本，極大地降低了特征庫的大小，從而提高檢測速度。對于每一個新樣本的檢測，只需計算其模糊哈希值與各變種家族的質心之間的距離，當距離小于該變種家族中的最大距離時，則表示其該新樣本屬于該家族。在添加新樣本后再重新計算該變種家族的質心μ。

算法3病毒樣本特征庫生成

輸入：病毒特征庫V，新樣本FH

輸出：更新病毒特征庫V′

5 實驗結果與分析

為了驗證本文所提出方法在對變種惡意軟件檢測的有效性，分別從檢測準確率、誤檢率以及檢測速度三方面進行分析評估。文中實驗樣本是由文獻[27]提供的Android惡意軟件樣本庫作，以及從應用市場下載的200個正常應用軟件為測試數(shù)據(jù)。

本實驗中將字符串特征向量以及函數(shù)特征向量的維度m均取值為5，產生模糊哈希值。再對300多個Android惡意軟件樣本抽樣，并生成病毒庫。之后再利用k-means聚類，來得到各家族的質點，從而實現(xiàn)對病毒庫的簡化。如表1所示，在此只列舉25個樣本數(shù)據(jù)。

表1 病毒庫聚類

圖5 檢測準確率及誤檢率

為了能夠評估本文所提出方法的有效性，分別從檢測準確率、誤檢率這兩方面進行度量。其中記能被檢測到的惡意軟件數(shù)量為TM，未能被檢測到的惡意軟件數(shù)量為FM，被誤檢的正常軟件數(shù)量為TN，沒被誤檢的正常軟件數(shù)量為FN，則：

檢測準確率：P=TM/(TM+FM)

誤檢率：E=TN/(TN+FN)

下面分別用ssdeep及本文方法（Ours），對300多個Android惡意軟件樣本家族聚類的準確率以及對200個正常軟件的誤檢率進行對比，如圖5所示。

在上面實驗中，由于FakeNotify、Pjapps、DroidKungFu2這三種類別的惡意軟件家族中部分樣本的資源文件以及部分指令發(fā)生了修改，造成了使用ssdeep算法計算出來的模糊哈希值存在較大的變化。本文提出的方法是從dex文件中的字符串以及函數(shù)中來提取特征產生模糊哈希值，能夠具有較高的抗干擾效果。對于Kmin以及DroidKungFu3這兩種類別的惡意軟件，是由正常應用中插入了少量的惡意代碼，使得與原正常應用差異較小，因此其誤檢率相對較高。為解決此問題，可以使用白名單以及簽名驗證的方式來避免。

同時，在對運行效率分析時，模擬對樣本數(shù)量為5 000、10 000以及500 000的病毒庫進行掃描，產生樣本特征庫所用時間進行對比，如圖6。

圖6 運行時間對比

由于ssdeep是逐字節(jié)讀取固定長度的內容，以固定窗口的形式進行滑動，每次對窗口內的內容進行計算，最終再將各個窗口的哈希值進行組合產生模糊哈希值，并以加權編輯距離來度量任意兩個模糊哈希值之間的相似度。這需要耗費大量的計算。而本文中所提出的方法是直接解析dex文件，提取出里面字符串以及函數(shù)的信息并生成模糊哈希值，具有較高的運算速度。

6 結束語

本文從字符串以及函數(shù)長度分布這兩個方面來提取Apk應用程序包的特征信息，用于產生模糊哈希值。該值能夠準確地描述樣本特征，并使得相似的Apk包的模糊哈希值之間的距離較短。再利用k-means聚類算法來對樣本庫中所有模糊哈希值進行聚類，得到每一家族樣本的質點。在對新樣本進行檢測時，只需計算與各家族樣本的質點之間相似度，減少了病毒庫中樣本數(shù)，從而提高了檢測速度。