基于多類特征的Android 應用重打包檢測方法

鄒慕蓉，胡勇

（四川大學電子信息學院，成都 610064）

基于多類特征的Android 應用重打包檢測方法

鄒慕蓉，胡勇

（四川大學電子信息學院，成都 610064）

針對Android系統的應用重打包安全威脅，提出一種基于多類特征的Android應用重打包檢測方法，結合簡化的圖特征向量檢測算法與圖片相似度算法，在保證應用相似度計算準確率的基礎上提高計算效率。通過原型系統的實驗，表明該系統能抵抗多種代碼混淆帶來的影響，準確地識別重打包應用程序,同時在運算效率上優于原重打包檢測方案。

Android應用；重打包；圖特征向量；感知哈希；抗混淆

0 引言

近年來，隨著移動智能設備的廣泛普及，移動應用的數目迅速增長。據著名互聯網流量監測機構Net Applications[1]發布的移動操作系統市場份額占比顯示，Android系統市場份額高達68.54%，比排名第二的iOS高出近43個百分點。與此同時，有別于iOS系統應用來源的單一性，Android平臺用戶不僅可從官方應用市場下載和安裝應用，如在手機的設置中勾選了“允許安裝未知來源的應用程序”選項，還可以安裝任意來源的應用程序。

Android平臺的開放性吸引了眾多開發者的加入，手機的功能也不斷地被豐富和擴充。Android應用程序安裝包（APK）是包含可執行DEX文件、簽名文件、資源文件等文件的壓縮歸檔文件。使用反編譯工具如Apktool，可以將其解析出類似于匯編的語言的Smali語言文件，甚至能反編譯為與源碼類似的Java文件。APK拆包與重組的便捷性降低了應用重打包的技術門檻，使得利用重打包篡改應用程序很容易實現。

應用重打包是指非授權開發者通過反編譯工具將APK反編譯后，對其代碼進行注入或修改，對資源文件進行刪改，再對修改后的目錄再次進行簽名和打包，生成篡改后APK文件的操作。

重打包應用與原應用實現的關鍵功能大都一致，而重打包后對應用進行重新簽名，會使得二者的簽名信息有所不同。由于一般用戶無法對重打包操作的可靠性和安全性進行鑒別，用戶在不知情的情況下可能安裝這些被篡改的應用。如果這種篡改是惡意的，一方面會對用戶的安全和隱私造成威脅，另一方面侵犯了應用開發者的知識產權利益。因此，針對應用的重打包檢測是很有必要的。應用重打包檢測相關的研究成果按照特征點的選取可分為以下三類：

（1）通過應用代碼特征進行相似度計算。文獻[2]提出DroidMOSS，通過反編譯應用的DEX文件到Dalvik字節碼，對其中的操作碼序列進行模糊散列，生成應用指紋特征，根據特征間的編輯距離來計算應用的相似程度。文獻[3]提出一種基于圖特征向量的檢測方法，依據解析應用中的類依賴關系建立基于圖的特征向量模型，再比較降維后的向量相似程度來實現檢測。

（2）通過應用資源文件的特征進行相似度計算。文獻[4]提出ImageStruct，通過計算不同應用多個圖片間的相似程度來得到應用的相似程度。文獻[5]提出DroidEagle，其中的RepoEagle模塊通過對應用的布局文件建立樹狀結構，由樹間的編輯距離來實現檢測。

（3）通過多類特征進行相似度計算。文獻[6]提出一種通過提取函數調用關系圖的節點數、邊數、平均度、網絡直徑等圖屬性特征，結合音頻、圖片文件特征實現相似性檢測的方法。

單獨提取某一類型的特征信息的相似度計算方法存在一定的局限性。僅針對代碼特征進行相似度計算，對于不能反編譯為Smali文件的APK或加殼的APK就完全不起作用。而僅提取APK資源文件特征進行相似度計算，雖然能很好地抵抗代碼混淆，但對于加載了同樣廣告庫的應用，其資源文件可能會出現很大程度的相似，造成誤判。反之，對于特征信息的過多提取，則會在準確率提高的同時降低相似度判別的效率。因此需要在保證應用相似度計算準確率的基礎上，盡量提高計算效率。

本文提出一種基于多類特征的Android應用重打包檢測方法，結合簡化的基于代碼特征的圖特征向量檢測算法與資源圖片文件相似度算法，在保證應用相似度計算準確率的基礎上提高計算效率。同時加入了應用簽名信息的比較，提高系統的準確性。圖1為系統流程圖。

圖1 系統流程

1 特征提取

本文提取三類特征作為應用相似度的判別依據：由反編譯解析出的應用程序類依賴關系生成的圖特征向量序列、使用感知哈希生成的圖片的指紋序列，以及應用簽名信息串。特征提取部分流程圖如圖2所示。

圖2 特征提取流程

1.1 圖片特征提取

在相似圖片搜索領域采用較多的算法包括：尺度不變特征變換匹配算法（SIFT）、平均哈希算法、感知哈希算法等。其中的感知哈希算法是一類比較哈希方法的統稱，它使用離散余弦變換來獲取圖片的低頻成分，相對于平均哈希算法受均值的影響更小。許多在線的“以圖搜圖”的引擎（如Google和Tineye）都采用該算法進行圖像匹配。因此本文選擇感知哈希算法來實現圖片文件特征的提取。

提取過程中，對APK文件“res/”目錄下的所有圖片文件，通過感知哈希算法進行計算，每幅圖片對應一個散列值，所有圖片散列值的集合作為應用的圖片特征。

1.2 代碼特征提取

常見的Android應用的相似度計算方法往往將應用相似度轉換為抽象語法樹的相似度或圖的相似度來計算，例如生成程序依賴圖PDG或控制流圖CFG、生成抽象語法樹，或對代碼分片執行模糊哈希算法。模糊哈希算法在分片大小不恰當時，簡單的語句刪改都會造成相似度誤判。而將文件相似度轉化為圖或語法樹的相似度，其保留的信息量越大，方法的準確性越高，而執行效率也隨之降低。

類依賴圖是指通過解析反編譯后的Android應用程序，由類間的互調關系生成的有向圖G=。其中V表示圖G中頂點的集合，E是圖G中邊的集合，μ是頂點屬性映射函數。

使用Graphviz軟件分別對某應用混淆前后的類依賴關系進行解析并繪圖，截取其中相應的部分，可得混淆前的圖3（a）和混淆后的圖3（b），從中可以看出，混淆操作雖然改變了類的名稱，但類之間的調用關系并未發生變化，即混淆前后生成的圖僅頂點名稱不同，頂點間的映射關系并未發生改變。因此通過類依賴圖來構建代碼特征是具備一定程度的抗混淆特性的。

圖特征向量算法是指由類依賴圖中的類依賴關系生成轉移概率矩陣，對轉移概率矩陣進行拉普拉斯變換，將輸出的矩陣映射為一個多維特征向量進行Android應用相似性分析的算法。轉移概率的計算方法如公式（1）所示，其中A、B表示有向圖G中的兩個頂點，A與B的out和in屬性分別表示頂點出度（由該頂點指向其他頂點的邊數）和入度（由其他頂點指向該頂點的邊數）。計算出有向圖G中所有節點的轉移概率后，就構成了圖的轉移概率矩陣，隨后按行依次取出其中的非零值，就構成了該圖的特征向量。

圖3

由于算法的輸出結果是一個包含浮點數的序列，做比較的兩個序列長度越長，后續進行相似度計算的耗時越久。為了提升計算效率，本文使用了簡化后的圖特征向量檢測算法，由原算法中提取應用所有包中的類依賴關系，簡化為僅對APK文件包名對應路徑下的類依賴關系進行解析，減少了輸出序列的長度。同時在實驗中觀察到原算法中對轉移概率矩陣做拉普拉斯變換這一步驟對算法性能提升效果不明顯，省略該步驟。代碼特征提取流程如圖4所示。

圖4 代碼特征提取流程

APK文件的包名通過查詢反編譯后的清單文件AndroidManifest.xml得到，該文件中存放了應用的包名、版本、申請的權限、組件信息等描述信息。一般情況下包名對應的應用路徑下存放了應用組件相關文件，調用的其他類往往單獨存放在其它包中。解析該路徑下所有類間的類依賴關系，可以減少解析類的數目，同時保留了相對關鍵的一些類間的類依賴關系。如解析某應用得到的類名為“com.grumoon.volleydemo”，則解析反編譯得到的smali文件的路徑為“/smali/com/grumoon/volleydemo/”，需要解析的類數目由原來的97縮減至35。

1.3 應用簽名信息提取

同一應用的不同版本，其代碼部分的特征及資源文件的特征極為相似，但與重打包應用的區別是，二者的簽名信息是一致的。若不對不同版本加以判斷，會誤判為重打包應用。因此，本文引入對應用簽名信息的提取，降低誤判率。在對應用相似度進行比較后，進一步對二者的應用簽名信息進行比對。本文假設應用原開發者的簽名是私有的，不能被別人獲取到。因此同一應用的不同版本盡管相似度很高，由于簽名信息一致，并不會被判定為重打包應用。APK的“META-INF/”目錄下包含完整的開發者證書，提供開發者相關信息以及公開密鑰的指紋信息，其中描述證書所有者的字符串作為簽名信息的比對依據。

2 相似度計算

相似度計算部分包括代碼特征相似度計算和圖片特征相似度計算，其產生的結果分別用sim（code）和sim（pic）表示，最終給出的相似度根據這兩部分結果加權得到，用sim（APK）表示。具體的計算公式如式（2）所示，其中，ra和rb分別表示兩項特征被賦予的權值，滿足ra+rb=1。對實驗中計算出的特征值進行Logistic回歸分析，得到ra=0.34，rb=0.66，閾值選取為0.45。

2.1 代碼特征相似度計算

代碼特征提取得到一個圖特征向量序列，實質是一個包含浮點型數字的數組，不同應用間的代碼特征相似度最終由數組間的相似度表示。常用的相似度比較算法包括：余弦相似度算法、編輯距離算法、最長公共子串算法等，每種算法在不同情況下的適用性和效率都有所不同。

由于重打包應用程序的主要功能與原應用程序相似，其內部的功能代碼可能會有所刪改，但大體結構不變，其連續性可能會由于插入的代碼而改變。因此本文選擇最長公共子序列算法來計算兩個圖特征向量序列間的相同特征數。圖特征向量序列由代碼特征提取模塊生成，其實質是一個包含浮點數的序列。

最長公共子序列（LCS）算法在保持圖特征向量的順序特性的同時，提取了兩個向量序列的公共特征值，使用動態規劃的思想實現的算法時間復雜度最優可至O（nlogn）。本文僅需要通過該算法得到兩個向量序列公共部分的長度來計算相似度，而不需要回溯數組得到公共部分的內容，進一步提高計算效率。

代碼特征相似度計算公式如公式（3）所示，其中|LCS（X，Y）|表示通過LCS算法得到的序列X與Y間最長公共子序列長度，max（|X|，|Y|）表示兩序列長度中的較大值。使用較大的序列長度作為分母使得計算結果與比較次序無關，并且不會因為某一方序列長度過小而產生誤報。

2.2 圖片特征相似度計算

本文采用圖片指紋間的漢明距離作為圖片特征相似度，然后通過計算杰卡德相似系數得到兩個應用的圖片特征序列的相似程度。每幅圖生成的圖片指紋長度為16位，一般情況下認為圖片指紋間的漢明距離小于5位，就認為兩幅圖像是相似的，也就近似地認為兩幅圖是相同的。實際計算中進行比較的兩組指紋序列的長度往往是不一樣的，因此使用公式（4）所示的杰卡德相似系數來計算最終兩集合的相似程度。其中cnt表示近似相等的圖片數目，m和n分別表示做比較的兩圖片特征序列的長度。

3 實驗分析

根據本文提出的重打包檢測方法實現了一個原型系統，同時實現了一個使用未經簡化的圖特征向量提取算法進行檢測的系統（下文簡稱為Full系統）與之對比。通過抗混淆能力檢測和效率檢測兩項實驗來驗證原型系統的抗混淆能力與執行效率。

3.1 實驗環境

實驗環境為Win7 64位操作系統，4G內存，使用Apktool v2.0.0-RC4進行應用的反編譯，使用Python 2.7版本進行代碼編寫。

3.2 抗混淆能力檢測

選取三種Android混淆工具ProGuard、APKProtect和Allatori分別對Github上較熱門的15個Android開源應用程序進行混淆，通過檢測原應用與混淆后的應用相似度，來驗證原型系統的抗代碼混淆效果。實驗結果如表1所示，計算出的相似度均高于閾值，驗證了原型系統的抗混淆能力。

表1 抗混淆能力檢測

3.3 執行效率檢測

使用原型系統與Full系統對來自Android惡意代碼應用收集平臺Contagiodump的三組應用分別進行相似度檢測，每組中的應用數分別為55、78和105，記錄計算過程中的平均耗時情況（包括反編譯時間），如表2所示。從中可以看出，原型系統在不同組應用的相似度計算中具備更高的運算效率。

表2 執行效率檢測

4 結語

通過對應用相似度計算的有效性和可靠性進行權衡，本文提出一種基于多類特征的Android應用重打包檢測方法，結合簡化的圖特征向量檢測算法與圖片相似度算法，在保證應用相似度計算準確率的基礎上提高計算效率。使用該方法實現原型系統進行實驗，實驗結果表明該系統能抵抗多種代碼混淆帶來的影響，準確地識別重打包應用程序。同時，在運算效率上優于原重打包檢測方案，是一種有效的重打包檢測方法。

本文提出的檢測方法在執行過程中還存在一些不足之處，如不能正常解析使用了加殼或加密技術的應用，同時代碼部分的簡化方式不夠智能，僅簡單地解析了APK包名對應路徑下所有類間的依賴關系。在后續的工作中會盡力完善這些不足之處，在盡可能細化算法粒度的同時提高算法的效率和可用性。

[1]NetMarketShare,Mobile/Tablet Top Operating System Share Trend[EB/OL].http://www.netmarketshare.com/operating-system-marketshare.aspx?qprid=8&qpcustomd=1,2016.

[2]Zhou W,Zhou Y,Grace M,et al.Fast,Scalable Detection of"Piggybacked"Mobile Applications[C].ACM Conference on Data and Application Security and Privacy，2013:185-196.

[3]顏克文.基于圖特征向量的Android程序相似性檢測算法研究[D].湘潭大學,2014.

[4]Jiao S,Cheng Y,Ying L,et al.A Rapid and Scalable Method for Android Application Repackaging Detection[M].Information Security Practice and Experience.Springer International Publishing,2015:349-364.5

[5]Sun M,Li M,Lui J C S.DroidEagle:Seamless Detection of Visually Similar Android Apps[C]，2015:1-12.

[6]王兆國,李城龍,關毅,等.抗混淆的Android應用相似性檢測方法[J].華中科技大學學報（自然科學版）,2016（3）:60-64.

A Repackaging Detection Method of Android Applications Based on Multiple Features

ZOU Mu-rong，HU Yong
（College of Electonics and Information Engineering,Sichuan University,Chengdu 610064）

According to the security threats from Android repackage application,proposes a repackaging detection method of android applications based on multiple features,which combines the graph eigenvector algorithm for code detection and perceptual hash algorithm for image detection.This method improves the calculation efficiency on the basis of ensuring the similarity calculation accuracy.The experiment result of the prototype system indicates that this method can withstand the effects of a variety of code confusion,accurately identify the repackaged Android application.The similarity detection computation efficiency is better than the original method using Graph Eigenvector.

Android Application;Repackage;Graph Eigenvector;Perceptual Hash;Anti Obsfucation

1007-1423（2017）07-0050-04

10.3969/j.issn.1007-1423.2017.07.013

鄒慕蓉（1992-），女，陜西寶雞人，在讀研究生，研究方向為Android安全

2017-01-04

2017-03-01

胡勇（1973-），男，四川成都人，博士，副教授，研究方向為信息安全