鄒慕蓉，胡勇

（四川大學(xué)電子信息學(xué)院，成都 610064）

基于多類特征的Android 應(yīng)用重打包檢測(cè)方法

鄒慕蓉，胡勇

（四川大學(xué)電子信息學(xué)院，成都 610064）

針對(duì)Android系統(tǒng)的應(yīng)用重打包安全威脅，提出一種基于多類特征的Android應(yīng)用重打包檢測(cè)方法，結(jié)合簡(jiǎn)化的圖特征向量檢測(cè)算法與圖片相似度算法，在保證應(yīng)用相似度計(jì)算準(zhǔn)確率的基礎(chǔ)上提高計(jì)算效率。通過(guò)原型系統(tǒng)的實(shí)驗(yàn)，表明該系統(tǒng)能抵抗多種代碼混淆帶來(lái)的影響，準(zhǔn)確地識(shí)別重打包應(yīng)用程序,同時(shí)在運(yùn)算效率上優(yōu)于原重打包檢測(cè)方案。

Android應(yīng)用；重打包；圖特征向量；感知哈希；抗混淆

0 引言

近年來(lái)，隨著移動(dòng)智能設(shè)備的廣泛普及，移動(dòng)應(yīng)用的數(shù)目迅速增長(zhǎng)。據(jù)著名互聯(lián)網(wǎng)流量監(jiān)測(cè)機(jī)構(gòu)Net Applications[1]發(fā)布的移動(dòng)操作系統(tǒng)市場(chǎng)份額占比顯示，Android系統(tǒng)市場(chǎng)份額高達(dá)68.54%，比排名第二的iOS高出近43個(gè)百分點(diǎn)。與此同時(shí)，有別于iOS系統(tǒng)應(yīng)用來(lái)源的單一性，Android平臺(tái)用戶不僅可從官方應(yīng)用市場(chǎng)下載和安裝應(yīng)用，如在手機(jī)的設(shè)置中勾選了“允許安裝未知來(lái)源的應(yīng)用程序”選項(xiàng)，還可以安裝任意來(lái)源的應(yīng)用程序。

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

應(yīng)用重打包是指非授權(quán)開發(fā)者通過(guò)反編譯工具將APK反編譯后，對(duì)其代碼進(jìn)行注入或修改，對(duì)資源文件進(jìn)行刪改，再對(duì)修改后的目錄再次進(jìn)行簽名和打包，生成篡改后APK文件的操作。

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

（1）通過(guò)應(yīng)用代碼特征進(jìn)行相似度計(jì)算。文獻(xiàn)[2]提出DroidMOSS，通過(guò)反編譯應(yīng)用的DEX文件到Dalvik字節(jié)碼，對(duì)其中的操作碼序列進(jìn)行模糊散列，生成應(yīng)用指紋特征，根據(jù)特征間的編輯距離來(lái)計(jì)算應(yīng)用的相似程度。文獻(xiàn)[3]提出一種基于圖特征向量的檢測(cè)方法，依據(jù)解析應(yīng)用中的類依賴關(guān)系建立基于圖的特征向量模型，再比較降維后的向量相似程度來(lái)實(shí)現(xiàn)檢測(cè)。

（2）通過(guò)應(yīng)用資源文件的特征進(jìn)行相似度計(jì)算。文獻(xiàn)[4]提出ImageStruct，通過(guò)計(jì)算不同應(yīng)用多個(gè)圖片間的相似程度來(lái)得到應(yīng)用的相似程度。文獻(xiàn)[5]提出DroidEagle，其中的RepoEagle模塊通過(guò)對(duì)應(yīng)用的布局文件建立樹狀結(jié)構(gòu)，由樹間的編輯距離來(lái)實(shí)現(xiàn)檢測(cè)。

（3）通過(guò)多類特征進(jìn)行相似度計(jì)算。文獻(xiàn)[6]提出一種通過(guò)提取函數(shù)調(diào)用關(guān)系圖的節(jié)點(diǎn)數(shù)、邊數(shù)、平均度、網(wǎng)絡(luò)直徑等圖屬性特征，結(jié)合音頻、圖片文件特征實(shí)現(xiàn)相似性檢測(cè)的方法。

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

本文提出一種基于多類特征的Android應(yīng)用重打包檢測(cè)方法，結(jié)合簡(jiǎn)化的基于代碼特征的圖特征向量檢測(cè)算法與資源圖片文件相似度算法，在保證應(yīng)用相似度計(jì)算準(zhǔn)確率的基礎(chǔ)上提高計(jì)算效率。同時(shí)加入了應(yīng)用簽名信息的比較，提高系統(tǒng)的準(zhǔn)確性。圖1為系統(tǒng)流程圖。

圖1 系統(tǒng)流程

1 特征提取

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

圖2 特征提取流程

1.1 圖片特征提取

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

提取過(guò)程中，對(duì)APK文件“res/”目錄下的所有圖片文件，通過(guò)感知哈希算法進(jìn)行計(jì)算，每幅圖片對(duì)應(yīng)一個(gè)散列值，所有圖片散列值的集合作為應(yīng)用的圖片特征。

1.2 代碼特征提取

常見的Android應(yīng)用的相似度計(jì)算方法往往將應(yīng)用相似度轉(zhuǎn)換為抽象語(yǔ)法樹的相似度或圖的相似度來(lái)計(jì)算，例如生成程序依賴圖PDG或控制流圖CFG、生成抽象語(yǔ)法樹，或?qū)Υa分片執(zhí)行模糊哈希算法。模糊哈希算法在分片大小不恰當(dāng)時(shí)，簡(jiǎn)單的語(yǔ)句刪改都會(huì)造成相似度誤判。而將文件相似度轉(zhuǎn)化為圖或語(yǔ)法樹的相似度，其保留的信息量越大，方法的準(zhǔn)確性越高，而執(zhí)行效率也隨之降低。

類依賴圖是指通過(guò)解析反編譯后的Android應(yīng)用程序，由類間的互調(diào)關(guān)系生成的有向圖G=。其中V表示圖G中頂點(diǎn)的集合，E是圖G中邊的集合，μ是頂點(diǎn)屬性映射函數(shù)。

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

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

圖3

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

圖4 代碼特征提取流程

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

1.3 應(yīng)用簽名信息提取

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

2 相似度計(jì)算

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

2.1 代碼特征相似度計(jì)算

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

由于重打包應(yīng)用程序的主要功能與原應(yīng)用程序相似，其內(nèi)部的功能代碼可能會(huì)有所刪改，但大體結(jié)構(gòu)不變，其連續(xù)性可能會(huì)由于插入的代碼而改變。因此本文選擇最長(zhǎng)公共子序列算法來(lái)計(jì)算兩個(gè)圖特征向量序列間的相同特征數(shù)。圖特征向量序列由代碼特征提取模塊生成，其實(shí)質(zhì)是一個(gè)包含浮點(diǎn)數(shù)的序列。

最長(zhǎng)公共子序列（LCS）算法在保持圖特征向量的順序特性的同時(shí)，提取了兩個(gè)向量序列的公共特征值，使用動(dòng)態(tài)規(guī)劃的思想實(shí)現(xiàn)的算法時(shí)間復(fù)雜度最優(yōu)可至O（nlogn）。本文僅需要通過(guò)該算法得到兩個(gè)向量序列公共部分的長(zhǎng)度來(lái)計(jì)算相似度，而不需要回溯數(shù)組得到公共部分的內(nèi)容，進(jìn)一步提高計(jì)算效率。

代碼特征相似度計(jì)算公式如公式（3）所示，其中|LCS（X，Y）|表示通過(guò)LCS算法得到的序列X與Y間最長(zhǎng)公共子序列長(zhǎng)度，max（|X|，|Y|）表示兩序列長(zhǎng)度中的較大值。使用較大的序列長(zhǎng)度作為分母使得計(jì)算結(jié)果與比較次序無(wú)關(guān)，并且不會(huì)因?yàn)槟骋环叫蛄虚L(zhǎng)度過(guò)小而產(chǎn)生誤報(bào)。

2.2 圖片特征相似度計(jì)算

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

3 實(shí)驗(yàn)分析

根據(jù)本文提出的重打包檢測(cè)方法實(shí)現(xiàn)了一個(gè)原型系統(tǒng)，同時(shí)實(shí)現(xiàn)了一個(gè)使用未經(jīng)簡(jiǎn)化的圖特征向量提取算法進(jìn)行檢測(cè)的系統(tǒng)（下文簡(jiǎn)稱為Full系統(tǒng)）與之對(duì)比。通過(guò)抗混淆能力檢測(cè)和效率檢測(cè)兩項(xiàng)實(shí)驗(yàn)來(lái)驗(yàn)證原型系統(tǒng)的抗混淆能力與執(zhí)行效率。

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)環(huán)境為Win7 64位操作系統(tǒng)，4G內(nèi)存，使用Apktool v2.0.0-RC4進(jìn)行應(yīng)用的反編譯，使用Python 2.7版本進(jìn)行代碼編寫。

3.2 抗混淆能力檢測(cè)

選取三種Android混淆工具ProGuard、APKProtect和Allatori分別對(duì)Github上較熱門的15個(gè)Android開源應(yīng)用程序進(jìn)行混淆，通過(guò)檢測(cè)原應(yīng)用與混淆后的應(yīng)用相似度，來(lái)驗(yàn)證原型系統(tǒng)的抗代碼混淆效果。實(shí)驗(yàn)結(jié)果如表1所示，計(jì)算出的相似度均高于閾值，驗(yàn)證了原型系統(tǒng)的抗混淆能力。

表1 抗混淆能力檢測(cè)

3.3 執(zhí)行效率檢測(cè)

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

表2 執(zhí)行效率檢測(cè)

4 結(jié)語(yǔ)

通過(guò)對(duì)應(yīng)用相似度計(jì)算的有效性和可靠性進(jìn)行權(quán)衡，本文提出一種基于多類特征的Android應(yīng)用重打包檢測(cè)方法，結(jié)合簡(jiǎn)化的圖特征向量檢測(cè)算法與圖片相似度算法，在保證應(yīng)用相似度計(jì)算準(zhǔn)確率的基礎(chǔ)上提高計(jì)算效率。使用該方法實(shí)現(xiàn)原型系統(tǒng)進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明該系統(tǒng)能抵抗多種代碼混淆帶來(lái)的影響，準(zhǔn)確地識(shí)別重打包應(yīng)用程序。同時(shí)，在運(yùn)算效率上優(yōu)于原重打包檢測(cè)方案，是一種有效的重打包檢測(cè)方法。

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

[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程序相似性檢測(cè)算法研究[D].湘潭大學(xué),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]王兆國(guó),李城龍,關(guān)毅,等.抗混淆的Android應(yīng)用相似性檢測(cè)方法[J].華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版）,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-），女，陜西寶雞人，在讀研究生，研究方向?yàn)锳ndroid安全

2017-01-04

2017-03-01

胡勇（1973-），男，四川成都人，博士，副教授，研究方向?yàn)樾畔踩?/p>