一種基于結(jié)構(gòu)相似性的Android公用庫檢測方法

慕志穎, 李智虎, 李曉宇

(1.西北工業(yè)大學(xué) 網(wǎng)絡(luò)安全學(xué)院, 陜西 西安 710072; 2.中國電力科學(xué)研究院有限公司, 北京 100192)

近年來，移動應(yīng)用需求增長迅速，移動操作系統(tǒng)市場獲得了快速增長。Android的市場份額日漸提高，已占據(jù)移動操作系統(tǒng)過半市場份額[1]。但Android平臺的應(yīng)用安全問題也越來越嚴重，用戶隱私竊取、設(shè)備吸費等安全事件層出不窮，惡意應(yīng)用程序泛濫。

為達到運行時用戶無感知的目的，大部分Android惡意應(yīng)用程序通過重打包方式(即將惡意代碼加入反編譯的正常應(yīng)用程序后重新組裝并簽名)實現(xiàn)惡意功能隱藏。普通用戶下載并安裝該類“正常”應(yīng)用后可能會在完全不知情的情況下泄漏隱私信息或遭受經(jīng)濟損失。因此，Android應(yīng)用程序重打包檢測已成為Android應(yīng)用安全領(lǐng)域的一個研究熱點[2-3]。

基于多種目的(提高開發(fā)效率、提供廣告等)，大量Android應(yīng)用會在開發(fā)過程中使用公用代碼庫。絕大部分重打包檢測方法[4-5]在檢測前嘗試排除公用代碼，降低這部分代碼對檢測結(jié)果的影響。但在當前應(yīng)用程序不斷涌現(xiàn)、公用代碼庫總量不斷提高的背景下，現(xiàn)有公用庫檢測方法的效率已無法滿足檢測的需求。

針對現(xiàn)有方法的不足，本文提出一種基于結(jié)構(gòu)相似性的公用代碼庫檢測方法，結(jié)合粗粒度的應(yīng)用程序安裝包結(jié)構(gòu)分析與細粒度的代碼特征比較，對應(yīng)用程序安裝包進行檢測，快速分析并定位應(yīng)用中使用的公用代碼庫，降低對后續(xù)重打包檢測過程中的干擾。

1 相關(guān)工作

現(xiàn)有Android應(yīng)用重打包檢測方法的基本原理是將反編譯后的應(yīng)用安裝包模塊解耦，分析并提取部分模塊進行下一步檢測。由于需要執(zhí)行成對比較，整個檢測過程的開銷(耗時、計算資源占用)隨檢測對象模塊數(shù)量上升而呈指數(shù)級增長。同時，非相關(guān)模塊的存在會劣化檢測效果。Android應(yīng)用中大量存在并使用的公用代碼庫對這些方法造成了嚴重影響。

已有一些方法[4-5]使用白名單的方式將應(yīng)用中的公用代碼文件過濾排除，由此提升了檢測效率與效果。但該方式存在2點不足：①更新不及時，需要大量人工參與；②使用包名作為過濾條件，惡意應(yīng)用可通過修改包名輕易規(guī)避。

針對這種情況，部分學(xué)者提出了一些改進方案。文獻[6]反編譯應(yīng)用程序后從AndroidManifest.xml配置文件中獲取權(quán)限等特征，通過這些提取的特征檢測應(yīng)用程序是否重打包。但該方法提取的特征相對比較粗粒度，容易出現(xiàn)較高的誤判。SimiDroid提取基于方法、應(yīng)用程序組件、資源文件的特征，通過這些特征不僅分析應(yīng)用程序之間的相似度，還對檢測結(jié)果進行了分析，取得了較好的檢測效果[7]。文獻[8]提取應(yīng)用程序調(diào)用的關(guān)鍵APIs,利用圖神經(jīng)網(wǎng)絡(luò)和聚類算法對圖結(jié)構(gòu)數(shù)據(jù)進行處理，為Android第三方庫的聚類分析提供了一種新的思路。

2 基于結(jié)構(gòu)相似性的公用庫檢測

公用庫檢測的核心評估指標主要為：①檢出率，準確發(fā)現(xiàn)應(yīng)用中的公用庫；②速度，快速檢測百萬量級應(yīng)用。本文提出的檢測方法面向大規(guī)模量級應(yīng)用環(huán)境，考慮Android應(yīng)用安裝包的特性，分析代碼包的目錄與文件分布結(jié)構(gòu)，過濾結(jié)構(gòu)不相似的代碼包，使用代碼文件的API特征進行細粒度比較，完成公用庫包的分類。

如圖1所示，檢測過程主要包括5個步驟：預(yù)處理，將Android應(yīng)用安裝包解壓縮并反編譯；弱關(guān)聯(lián)子包提取，利用PDG[9]解析各個代碼子包，抽取與主包群關(guān)聯(lián)性較弱的子包作為公用庫候選；包結(jié)構(gòu)相似度計算，基于子包目錄與文件分布結(jié)構(gòu)，與比較對象進行粗粒度的相似度計算；代碼結(jié)構(gòu)相似度計算，提取代碼文件的API調(diào)用信息,生成包結(jié)構(gòu)特征碼并計算結(jié)構(gòu)相似度；公用庫分類，利用結(jié)構(gòu)相似度分類至所屬公用庫。

2.1 預(yù)處理

本文使用apktool工具[10]反編譯Android應(yīng)用程序安裝包，獲得該應(yīng)用程序的所有構(gòu)成內(nèi)容，包括Androidmanifest.xml、資源文件與以包形式分布的smali代碼文件。

2.2 弱關(guān)聯(lián)子包提取

正常應(yīng)用中包括兩類代碼包：主包群與公用庫包。主包群包含應(yīng)用程序入口所在包及與入口包存在較強調(diào)用關(guān)系的代碼包。公用庫代碼的用途主要是廣告和部分功能的實現(xiàn)，主包群不會與公用庫包存在頻繁交互。同時，主包群與公用庫往往都是單向調(diào)用關(guān)系。因此，與主包群之間調(diào)用次數(shù)較少或有向調(diào)用關(guān)系較弱的代碼包可視為候選公用庫包。將主包群與公用庫包有效分離可以減少后續(xù)相似度計算消耗，提高速度。

如圖2所示，本文使用PDG方法分離應(yīng)用中的主包群和潛在公用庫包。利用預(yù)處理后的smali文件，在代碼包之間生成具有權(quán)重(調(diào)用次數(shù))的圖。結(jié)合確定的應(yīng)用入口所在包，形成主包群與候選公用庫包。

圖2 子包解耦分離

2.3 包結(jié)構(gòu)相似度計算

包結(jié)構(gòu)主要指代碼包中，文件目錄與代碼文件的分布情況。Android代碼包結(jié)構(gòu)與操作系統(tǒng)文件系統(tǒng)高度相似，可使用樹狀結(jié)構(gòu)表示。如圖3所示，包結(jié)構(gòu)包括根節(jié)點(頂級包)、目錄節(jié)點(子包)、代碼文件節(jié)點及相應(yīng)的深度信息。

圖3 代碼包結(jié)構(gòu)示例

公用庫的目的是被應(yīng)用程序調(diào)用，為確保穩(wěn)定性，連續(xù)版本之間的包結(jié)構(gòu)不會出現(xiàn)大量變化。同時，正常情況下，不同作者公用庫之間的包結(jié)構(gòu)不會出現(xiàn)高度相似的情況。基于上述分析，在代碼包比較過程中，可計算比較對象之間的包結(jié)構(gòu)相似度，以粗粒度剔除包結(jié)構(gòu)相似度不高的情況。

2個代碼包Pa,Pb的包結(jié)構(gòu)相似度范圍為[0,1],定義為

Psim(Pa,Pb)=

(1)

式中:PsimP(Pa,Pb)為包目錄分布相似度;PsimF(Pa,Pb)為代碼文件分布相似度。α與β調(diào)整2類分布相似度權(quán)重,范圍為[0,1],且α+β=1。

包目錄分布相似度使用代碼包內(nèi)所有目錄的分布情況,計算2個比較對象同一深度級別的目錄數(shù)量差值與總和比值,獲得該深度級別的相似度。通過累加各個深度的相似度,獲得最終的包目錄分布相似度,定義為

(2)

式中：DP為2個比較對象中目錄深度級別的較大值;Mai與Mbi分別為2個比較對象該深度級別的目錄數(shù)量。

與包目錄分布相似度相似,代碼文件分布相似度為2個比較對象同一深度級別smali文件的數(shù)量差值與總和比值,定義為

(3)

DF為2個比較對象中代碼文件深度級別的較大值。Nai與Nbi為2個比較對象該深度級別的代碼文件數(shù)量。

建立閾值TP(范圍為[0,1]),過濾包結(jié)構(gòu)相似度不高(Psim((Pa,Pb)

2.4 代碼結(jié)構(gòu)相似度計算

該步驟面向smali代碼文件級相似度計算,用于細粒度的精確文件匹配,主要包括代碼文件特征計算及代碼包相似度計算。前者基于smali文件代碼生成文件特征,后者在此基礎(chǔ)上進行結(jié)構(gòu)相似度計算,最終生成2個比較對象的相似度結(jié)果。

考慮代碼文件相似度計算與文檔去重操作的同質(zhì)性,本文使用Simhash算法[11]、結(jié)合Android代碼結(jié)構(gòu)生成代碼文件特征。具體的生成規(guī)則如下:

1) 讀取smali文件,統(tǒng)計選定的32個Android API調(diào)用次數(shù)作為權(quán)重;

2) 分別生成所有API的64位哈希值,轉(zhuǎn)換為二進制位串;

3) 哈希值所有位串計算:若該位為0,則轉(zhuǎn)換為權(quán)重負值,若為1則為權(quán)重正值;

4) 按位累加所有32個位串的計算結(jié)果;

5) 按位轉(zhuǎn)換上一步計算結(jié)果:若該位為負值,轉(zhuǎn)換為0,正值轉(zhuǎn)為1。

完成上述特征計算操作后,本文獲得了代碼包內(nèi)所有smali文件的64位二進制特征碼。

代碼包相似度計算過程以樹狀包目錄分布為基礎(chǔ),遞歸計算各個深度級別的包目錄相似度與代碼文件相似度。本文使用簡化的SimRank[12]計算過程。各級深度的包目錄相似度定義為

(4)

式中:C為阻尼系數(shù);Spa與Spb為2個比較對象的同一級別子包(目錄);k為當前深度級別,范圍為0至2個比較對象包的最大深度;Oa與Ob分別為與當前子包有父子關(guān)系的下級子包及下級代碼文件總數(shù),若Oa和Ob為0,Fsimk(Spa,Spb)為0;Vai與Vbi需同時為下級子包(Spai,Spbj)或下級代碼文件(Fai,Fbi),即Fsimk+1(Spai,Fbj)=0,Fsimk+1(Fai,Spbj)=0。

同時,下級代碼文件對的相似度為

Fsimk+1(Fai,Fbj)=HAM(Fai,Fbj)

(5)

式中，HAM(Fai,Fbj)表示hamming距離，即文件對的相似度為64位二進制特征碼的漢明距離。

各級子包相似度遞歸計算,最終2個比較對象(頂級代碼目錄)之間的相似度為

Fsim(Pa,Pb)=Fsim0(Spa,Spb)

(6)

2.5 公用庫分類

最后,本文使用代碼結(jié)構(gòu)相似度Fsim(Pa,Pb)與經(jīng)過粗粒度篩選的數(shù)據(jù)庫中公用庫包比較。設(shè)置2個閾值TH及TL,范圍均為[0,1]。分類規(guī)則如下:

1)Fsim(Pa,Pb)大于等于TH的比較對象對加入備選列表:若列表內(nèi)無元素,直接執(zhí)行下一步;只有一個元素,直接分類為對應(yīng)的公用庫;若列表元素數(shù)量大于1,分類為Fsim(Pa,Pb)最大的公用庫;

2) 若Fsim(Pa,Pb)大于等于TL的數(shù)量大于等于1,認為該包有較大可能為其他公用庫包的更新版或修改版,記錄信息后新建存儲為公用庫包;

3) 若上述條件均不滿足,標記為臨時公用庫包,參與后續(xù)分類比較。經(jīng)額定周期,如依然沒有高度相似包,則刪除該包,否則升級為公用庫包。

3 實驗與結(jié)果

3.1 實驗設(shè)置與數(shù)據(jù)集

實驗分為兩部分:小規(guī)模驗證評估本文提出檢測方法的相關(guān)性能;大規(guī)模測試分析市場中應(yīng)用程序使用公用庫的現(xiàn)實情況及大量級檢測樣本下的性能(速度指標)。實驗運行環(huán)境為一臺聯(lián)想ThinkServer服務(wù)器(Intel Xeon E3、64 GB內(nèi)存、1 TB硬盤)。對應(yīng)該實驗設(shè)置,實驗數(shù)據(jù)集分為2組。

小規(guī)模驗證使用人工下載的數(shù)據(jù)集,共包含200個APK安裝包。經(jīng)過人工挑選與驗證,共出現(xiàn)368次公用庫包使用,包含332個SHA1哈希計算結(jié)果不同的包,共出現(xiàn)44個不同包名。

使用自己開發(fā)的分布式應(yīng)用抓取器搜索并下載大規(guī)模測試數(shù)據(jù)集。數(shù)據(jù)集抓取時間為2016年3月至4月,來源為國內(nèi)5個主流應(yīng)用市場,共抓取存儲105 985個APK安裝包,占用392 GB存儲空間。所有安裝包均經(jīng)過解壓驗證,剔除了非正常APK安裝包和較復(fù)雜的應(yīng)用(例如微信)。需要指出的是,考慮游戲應(yīng)用程序普遍體積較大的情況,本文的數(shù)據(jù)集中沒有包含游戲,均為普通應(yīng)用程序。

3.2 評價指標

本文使用檢出率(true positive rate,TPR)與誤報率(false positive rate,FPR)作為評價所提出方法的指標。表1定義參與2個評價指標計算的參數(shù)。需要指出,具有同一包名但存在代碼差異的代碼包無法定性分類,所以仍然依賴包名進行人工分類。

表1 評價參數(shù)定義

檢出率定義為

(7)

誤報率定義為

(8)

3.3 結(jié)果分析

使用小規(guī)模驗證數(shù)據(jù)集,設(shè)置固定參數(shù)包括:α,β,C,TL使用5對閾值(TP和TH)進行實驗。

表2 不同閾值對下的檢測結(jié)果

實驗結(jié)果如表2所示。隨著2項閾值的提高,檢出包的數(shù)量也不斷增加。TP=0.70且TH=0.70時檢出包基本匹配包名數(shù)量(44),但有1個包可能與其他包混淆,未能檢出。同時,TP=0.90且TH=0.95時,檢出包數(shù)量接近非哈希相同包數(shù)量(332)。在閾值較低時,RT和RF均不理想。隨著閾值提高,2項數(shù)據(jù)逐漸提高。

不合理的高閾值提高了檢測性能,但會導(dǎo)致過度分類,修改較小、主觀上可以歸為一類的代碼包(例如小版本升級)實際運行中會分成2類,造成空間(特征存儲)和時間(后續(xù)包分類)開銷增大,不適合在大規(guī)模樣本環(huán)境中使用。此外,實驗結(jié)果與樣本集有較強關(guān)聯(lián)。

一個APK文件的檢測平均耗時如表3所示。預(yù)處理與弱關(guān)聯(lián)子包提取操作耗時較長，但對數(shù)據(jù)集規(guī)模不敏感。包結(jié)構(gòu)相似度計算只統(tǒng)計比較目錄與文件分布結(jié)構(gòu)，速度較快，且在大規(guī)模數(shù)據(jù)集處理中速度下降幅度不大。詳細分析代碼結(jié)構(gòu)相似度計算過程，發(fā)現(xiàn)耗時主要發(fā)生在特征計算部分，相似度計算耗時較短且沒有隨數(shù)據(jù)集規(guī)模增大而嚴重下降，證明該方法具有較好的可伸縮性。最后的公用庫分類操作較簡單，耗時基本可以忽略。

表3 檢測過程平均耗時 s

最后，本文統(tǒng)計了大規(guī)模測試中排名前十的公用庫出現(xiàn)次數(shù)，如圖4所示。可以看出，在實驗數(shù)據(jù)集中，除了部分工具庫，大部分還是廣告平臺。

圖4 公用庫統(tǒng)計次數(shù)

實驗結(jié)果證明，本文提出的檢測方法能保證公用庫的檢出率與誤報率，具有較高的檢測速度與可伸縮性，適合在大規(guī)模數(shù)據(jù)環(huán)境中應(yīng)用。但實驗也說明該方法在部分計算過程中存在效率問題，需要進行優(yōu)化(例如使用并行計算提高特征計算速度)。

4 結(jié) 論

本文提出了一種基于結(jié)構(gòu)相似性的Android公用代碼庫檢測方法，整合應(yīng)用安裝包結(jié)構(gòu)比較與代碼文件特征計算，實現(xiàn)不同粒度的代碼分析與定位。實驗結(jié)果顯示，該方法可快速、有效定位并分類現(xiàn)實應(yīng)用程序中的公用代碼庫。

考慮該方法與重打包檢測的原理通用性，下一步的主要工作是優(yōu)化該方法，適配大規(guī)模應(yīng)用市場中的重打包應(yīng)用程序檢測與家族化分類。