SPRD：基于應(yīng)用UI和程序依賴圖的Android重打包應(yīng)用快速檢測(cè)方法

汪潤，王麗娜，唐奔宵，趙磊

?

SPRD：基于應(yīng)用UI和程序依賴圖的Android重打包應(yīng)用快速檢測(cè)方法

汪潤1,2,3，王麗娜1,2,3，唐奔宵1,2,3，趙磊1,2,3

（1. 武漢大學(xué)空天信息安全與可信計(jì)算教育部重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430072；2. 武漢大學(xué)計(jì)算機(jī)學(xué)院，湖北 武漢 430072；3. 武漢大學(xué)國家網(wǎng)絡(luò)安全學(xué)院，湖北 武漢 430072）

研究發(fā)現(xiàn)重打包應(yīng)用通常不修改應(yīng)用用戶交互界面（UI, user interface）的結(jié)構(gòu)，提出一種基于應(yīng)用UI和程序代碼的兩階段檢測(cè)方法。首先，設(shè)計(jì)了一種基于UI抽象表示的散列快速相似性檢測(cè)方法，識(shí)別UI相似的可疑重打包應(yīng)用；然后，使用程序依賴圖作為應(yīng)用特征表示，實(shí)現(xiàn)細(xì)粒度、精準(zhǔn)的代碼克隆檢測(cè)?；谒岱椒▽?shí)現(xiàn)了一種原型系統(tǒng)——SPRD（scalable and precise repacking detection），實(shí)驗(yàn)驗(yàn)證所提方法具有良好的可擴(kuò)展性和準(zhǔn)確性，可以有效地應(yīng)用于百萬級(jí)應(yīng)用和億萬級(jí)代碼的大規(guī)模應(yīng)用市場(chǎng)。

重打包；代碼克隆；用戶界面；程序依賴圖；安全與隱私

1 引言

移動(dòng)互聯(lián)網(wǎng)的快速發(fā)展使一些智能設(shè)備如智能手機(jī)、智能手表等廣泛普及并帶來了移動(dòng)應(yīng)用數(shù)量的劇增。根據(jù)全球移動(dòng)通信系統(tǒng)協(xié)會(huì)（GSMA, Global System for Mobile Communications Association）的一份報(bào)告顯示，從2016年開始移動(dòng)設(shè)備的數(shù)量已經(jīng)超過了人類的總?cè)藬?shù)。目前，兩大主流移動(dòng)平臺(tái)，Android平臺(tái)的官方商店Google Play和iOS平臺(tái)的App Store上均有超過百萬的移動(dòng)應(yīng)用。移動(dòng)應(yīng)用不僅能夠提供給用戶豐富的功能體驗(yàn)，而且也給人們的生活帶來了很多便利。在移動(dòng)市場(chǎng)中由于惡意應(yīng)用的普遍存在，對(duì)用戶的安全和隱私已經(jīng)造成了嚴(yán)重的威脅。

報(bào)告顯示，Android平臺(tái)已經(jīng)成為惡意軟件泛濫的重災(zāi)區(qū)，其中，98%以上的惡意應(yīng)用都是發(fā)現(xiàn)在Android平臺(tái)。在這些惡意應(yīng)用中，有超過86%的應(yīng)用都是重打包應(yīng)用[1]。重打包應(yīng)用是由惡意開發(fā)者反編譯修改已經(jīng)發(fā)布在應(yīng)用商店中的合法應(yīng)用程序，在程序代碼中插入惡意的代碼片段或修改部分代碼片段，引誘用戶下載安裝使用，達(dá)到謀取利益或傳播惡意軟件的目的。由于Android應(yīng)用程序具有易反編譯修改等特點(diǎn)，重打包應(yīng)用在Android平臺(tái)上更為普遍。從惡意開發(fā)者制造重打包應(yīng)用的動(dòng)機(jī)來看，主要有以下2種。

1) 謀取非法利益。惡意開發(fā)者替換應(yīng)用中的廣告庫，重打包后發(fā)布到應(yīng)用市場(chǎng)，賺取廣告收益或漢化侵權(quán)謀取利益等。

2) 傳播惡意軟件。惡意開發(fā)者反編譯修改應(yīng)用程序，插入惡意代碼，竊取用戶隱私信息如讀取用戶短信、通信錄等，上傳到遠(yuǎn)程服務(wù)器或利用惡意代碼實(shí)施遠(yuǎn)程攻擊等。

由于Android平臺(tái)上重打包應(yīng)用廣泛存在且重打包應(yīng)用的嚴(yán)重危害性，已經(jīng)引起了研究人員的廣泛關(guān)注并展開了一系列的相關(guān)研究工作[2,3]。這些研究工作多是通過計(jì)算應(yīng)用之間的相似性，利用應(yīng)用之間的相似度完成重打包應(yīng)用的檢測(cè)。具體來說，概括為以下2種方法。第一種方法是基于代碼克隆的重打包應(yīng)用檢測(cè)[4~8]。這種方法主要是比較應(yīng)用程序代碼的相似度，提取應(yīng)用程序的代碼模式如控制流圖和數(shù)據(jù)流圖等作為應(yīng)用代碼的特征表示。但是這種方法不能有效應(yīng)對(duì)代碼混淆的問題，同時(shí)由于其檢測(cè)效率低下并不適用于百萬級(jí)應(yīng)用市場(chǎng)的億萬級(jí)代碼檢測(cè)。另外一種方法是基于Android應(yīng)用資源文件的重打包檢測(cè)[9~11]。這種方法利用Android應(yīng)用交互性強(qiáng)的特點(diǎn)，在Android應(yīng)用的安裝文件中存在大量的資源文件，如圖片、音頻以及視頻文件等，而重打包應(yīng)用不修改或較少地修改安裝文件中的資源文件，通過比較資源文件的相似性實(shí)現(xiàn)重打包應(yīng)用檢測(cè)，這種方法可以有效緩解代碼混淆的攻擊，但是存在較高的誤報(bào)率。Android應(yīng)用中存在大用戶界面（UI），應(yīng)用UI是一種特殊的資源文件。有研究發(fā)現(xiàn)重打包應(yīng)用為了引誘用戶下載通常不修改應(yīng)用（UI）的結(jié)構(gòu)，因此，有研究將UI作為應(yīng)用相似性比較的特征[9,10]。這種方法也屬于基于Android應(yīng)用資源文件的重打包應(yīng)用檢測(cè)方法。但是這類方法的不足在于有些應(yīng)用使用的是同一套模板，導(dǎo)致在檢測(cè)的時(shí)候存在較高的誤報(bào)率。

研究發(fā)現(xiàn)，目前，針對(duì)Android平臺(tái)重打包應(yīng)用檢測(cè)方法存在的不足體現(xiàn)在以下3個(gè)方面：1) 能夠?qū)崿F(xiàn)高檢測(cè)準(zhǔn)確率，但檢測(cè)速度低下，不能有效應(yīng)用于百萬級(jí)應(yīng)用市場(chǎng)的重打包檢測(cè)；2) 能夠?qū)崿F(xiàn)快速檢測(cè)，但不能保證檢測(cè)的準(zhǔn)確率；3) 一些方法在檢測(cè)的速度和準(zhǔn)確率之間做到很好的平衡，但是在預(yù)處理階段需要消耗大量的計(jì)算資源。因此，如何在檢測(cè)的速度、準(zhǔn)確率和計(jì)算資源開銷這3個(gè)方面進(jìn)行平衡是目前重打包應(yīng)用檢測(cè)中亟待解決的問題。在面對(duì)百萬級(jí)應(yīng)用市場(chǎng)的重打包應(yīng)用檢測(cè)中，存在以下3個(gè)挑戰(zhàn)。

1) 程序代碼量巨大。在百萬級(jí)的應(yīng)用市場(chǎng)中存在近10億行代碼，如果僅在代碼層進(jìn)行兩兩比較需要進(jìn)行超過1016次比較。在有新的應(yīng)用上架時(shí)，同樣需要重新進(jìn)行一次比較，計(jì)算資源開銷巨大，無法做到實(shí)時(shí)的在線檢測(cè)。

2) 源代碼獲取困難。安全分析人員僅能從應(yīng)用市場(chǎng)上獲取應(yīng)用的安裝文件（apk），反編譯獲取smali代碼，其可讀性差，導(dǎo)致基于源碼的代碼克隆檢測(cè)等技術(shù)并不能直接應(yīng)用。

3) 攻擊方式多樣。國內(nèi)市場(chǎng)發(fā)布的應(yīng)用多經(jīng)過代碼混淆處理，導(dǎo)致基于控制流圖等特征表示的代碼克隆檢測(cè)方法效果不理想。惡意開發(fā)者還會(huì)猜測(cè)檢測(cè)系統(tǒng)的工作原理，精心構(gòu)造重打包應(yīng)用繞過檢測(cè)。

為了解決面向百萬級(jí)應(yīng)用市場(chǎng)的快速重打包應(yīng)用檢測(cè)問題，同時(shí)保證檢測(cè)的準(zhǔn)確率和降低計(jì)算資源的開銷，在一定程度上對(duì)抗代碼混淆的攻擊。本文提出了一種基于應(yīng)用UI和程序代碼的兩階段重打包應(yīng)用檢測(cè)方法。首先，利用重打包應(yīng)用通常不修改應(yīng)用UI結(jié)構(gòu)的特點(diǎn)，設(shè)計(jì)了一種基于應(yīng)用UI抽象表示的散列快速相似性檢測(cè)方法，識(shí)別出可疑的重打包應(yīng)用；然后，提取這些可疑重打包應(yīng)用的程序依賴圖（PDG, program dependency graph）作為應(yīng)用的特征表示，在代碼層進(jìn)行細(xì)粒度的代碼克隆分析，檢測(cè)相似的代碼片段，有效地解決應(yīng)用UI作為特征表示帶來檢測(cè)誤報(bào)率高的問題。本文提出的應(yīng)用UI抽象表示方法能夠?qū)箲?yīng)用資源文件的插入、修改等攻擊。利用PDG作為應(yīng)用的代碼特征表示可以有效抵抗代碼插入、修改等攻擊行為[6]。實(shí)驗(yàn)表明，上述方法能夠應(yīng)用于百萬級(jí)應(yīng)用市場(chǎng)的快速準(zhǔn)確重打包應(yīng)用檢測(cè)，同時(shí)本文方法不需要在預(yù)處理階段反編譯所有的待測(cè)應(yīng)用，可以節(jié)約大量的計(jì)算資源開銷。本文的主要貢獻(xiàn)如下。

1) 設(shè)計(jì)并實(shí)現(xiàn)了一套面向百萬級(jí)應(yīng)用市場(chǎng)的兩階段重打包應(yīng)用快速檢測(cè)（SPRD, scalable and precise repacking detection）系統(tǒng)，利用應(yīng)用UI和程序代碼作為應(yīng)用相似性檢測(cè)的特征，實(shí)現(xiàn)快速準(zhǔn)確的重打包應(yīng)用檢測(cè)。

2) 提出了一種基于Android應(yīng)用UI抽象表示的散列快速相似性檢測(cè)方法，可以在秒級(jí)時(shí)間內(nèi)實(shí)現(xiàn)百萬級(jí)應(yīng)用的快速相似性檢測(cè)。

3) 利用應(yīng)用程序依賴圖作為應(yīng)用程序代碼的特征表示，實(shí)現(xiàn)應(yīng)用程序代碼細(xì)粒度、高精度的克隆檢測(cè)，降低僅使用應(yīng)用UI作為應(yīng)用特征表示帶來的高誤報(bào)率。

4) 實(shí)驗(yàn)中從Google Play官方商店和多個(gè)第三方移動(dòng)應(yīng)用市場(chǎng)收集了超過100萬個(gè)應(yīng)用，在大規(guī)模的實(shí)驗(yàn)數(shù)據(jù)集中驗(yàn)證了本文方法的有效性，實(shí)驗(yàn)結(jié)果顯示SPRD可以達(dá)到93.3%的檢測(cè)準(zhǔn)確率。

2 相關(guān)工作

Android平臺(tái)已經(jīng)成為移動(dòng)惡意軟件的重災(zāi)區(qū)，對(duì)用戶的安全和隱私造成了嚴(yán)重的威脅。因此，建立健康的移動(dòng)應(yīng)用市場(chǎng)有著重要的意義。近年來，學(xué)術(shù)界和工業(yè)界為此做了許多重要的工作[11~24]。由于Android平臺(tái)的開放性以及Android應(yīng)用易反編譯等特點(diǎn)，重打包應(yīng)用成為Android平臺(tái)最常見的惡意軟件類型之一[25~29]。目前，針對(duì)Android重打包應(yīng)用的檢測(cè)主要分為基于代碼克隆[4~8,30~33]和基于應(yīng)用資源文件相似性比較[9,10,34~36]這2類方法，它們都是通過計(jì)算應(yīng)用之間的相似性檢測(cè)重打包應(yīng)用。接下來，詳細(xì)介紹這2類檢測(cè)方法。

2.1 基于代碼克隆的檢測(cè)

基于代碼克隆的重打包應(yīng)用檢測(cè)是一種最常見的代碼相似性檢測(cè)方法并被廣泛應(yīng)用于Android重打包應(yīng)用檢測(cè)。DroidMOSS[4]在操作碼上使用了一種模糊散列技術(shù)生成表示應(yīng)用的指紋信息，然后，使用編輯距離計(jì)算2個(gè)應(yīng)用的相似性。Juxtapp[5]首先利用-gram對(duì)應(yīng)用的操作碼進(jìn)行處理，然后，使用一種基于Bloom-filter的特征散列算法生成應(yīng)用的向量表示，再使用Jaccard相似性距離計(jì)算2個(gè)應(yīng)用的相似性。文獻(xiàn)[4]和文獻(xiàn)[5]的2種方法可以實(shí)現(xiàn)大規(guī)模的應(yīng)用相似性比較，但是如果在代碼中插入或調(diào)整代碼位置等，會(huì)導(dǎo)致檢測(cè)方法失效，也就是說不能有效地檢測(cè)3.2節(jié)中的類型2重打包應(yīng)用。DNADroid[6]使用程序依賴圖作為應(yīng)用的特征表示，借助WALA為應(yīng)用中每個(gè)類的每個(gè)方法生成一個(gè)PDG，利用圖的相似性匹配來檢測(cè)相似的應(yīng)用，這種方法有較高的檢測(cè)準(zhǔn)確率，但是由于圖匹配無法在多項(xiàng)式時(shí)間內(nèi)完成，因此該方法難以擴(kuò)展到百萬級(jí)的應(yīng)用市場(chǎng)檢測(cè)。文獻(xiàn)[7,8]利用一種基于計(jì)數(shù)的代碼克隆檢測(cè)技術(shù)實(shí)現(xiàn)重打包應(yīng)用的檢測(cè)，同時(shí)該方法有效地降低Android平臺(tái)中第三方庫在應(yīng)用相似性比較中造成的影響，但是文獻(xiàn)中的方法難以應(yīng)用于存在嚴(yán)重代碼混淆和百萬級(jí)市場(chǎng)的程序代碼相似性比較情況。Chen等[30,31]利用應(yīng)用程序控制流圖的質(zhì)心表示移動(dòng)應(yīng)用的特征，實(shí)現(xiàn)大規(guī)?？焖俚膽?yīng)用相似性檢測(cè)。但是該方法在處理之前要抽取所有應(yīng)用的控制流圖，需要消耗大量的計(jì)算資源，而且在代碼混淆嚴(yán)重時(shí)，會(huì)影響控制流圖的生成，直接導(dǎo)致該方法失效。

2.2 基于應(yīng)用資源文件的檢測(cè)

由于Android應(yīng)用的事件觸發(fā)機(jī)制設(shè)計(jì)，在Android應(yīng)用中存在豐富的用戶交互界面UI。有研究發(fā)現(xiàn)惡意開發(fā)者為了迷惑用戶下載安裝應(yīng)用，通常不修改或較少修改應(yīng)用的UI等資源文件。ViewDroid[9]提出了一種將用戶界面作為應(yīng)用特征表示的重打包應(yīng)用檢測(cè)方法，利用有向圖表示應(yīng)用，其中，有向圖的頂點(diǎn)是應(yīng)用的視圖（view），有向邊表示2個(gè)視圖之間可以通過事件進(jìn)行切換，然后利用VF2算法[37]比較圖的相似性實(shí)現(xiàn)應(yīng)用的相似性比較。如果攻擊者在應(yīng)用中惡意地插入多余的視圖以及應(yīng)用的視圖很少的情況下，該方法并不能取得較理想的效果。DroidEagle[10]使用應(yīng)用布局作為特征檢測(cè)應(yīng)用的相似性，該系統(tǒng)由用于部署大規(guī)模應(yīng)用市場(chǎng)檢測(cè)子系統(tǒng)RepoEagle和輕量級(jí)的用于移動(dòng)端檢測(cè)的子系統(tǒng)HostEagle這2個(gè)部分組成，幫助用戶實(shí)現(xiàn)快速檢測(cè)。如果應(yīng)用的布局被惡意開發(fā)者做了少量的修改會(huì)導(dǎo)致客戶端檢測(cè)失效，造成DroidEagle不能應(yīng)用于大規(guī)模應(yīng)用市場(chǎng)的快速檢測(cè)。以上基于應(yīng)用UI等資源文件的檢測(cè)方法均可以有效地對(duì)抗代碼混淆的攻擊，但是應(yīng)用UI的樹型特征表示難以應(yīng)對(duì)大規(guī)模應(yīng)用市場(chǎng)的應(yīng)用快速相似性比較。另外，存在一些應(yīng)用從同一套模板的基礎(chǔ)上開發(fā)而來，其布局和風(fēng)格相似，但并不是重打包應(yīng)用，導(dǎo)致這類方法在此類應(yīng)用的分析上會(huì)存在較高的誤報(bào)率。

綜上所述，現(xiàn)有的重打包應(yīng)用檢測(cè)方法沒有在檢測(cè)的速度和準(zhǔn)確率之間做到很好的平衡，難以應(yīng)對(duì)百萬級(jí)應(yīng)用市場(chǎng)快速、準(zhǔn)確檢測(cè)的要求。本文提出了一種基于應(yīng)用UI和程序代碼的兩階段檢測(cè)方法，旨在解決海量應(yīng)用市場(chǎng)中，快速準(zhǔn)確的重打包應(yīng)用檢測(cè)問題，降低分析檢測(cè)過程中計(jì)算資源的開銷。

3 相關(guān)背景知識(shí)

3.1 Android應(yīng)用程序

應(yīng)用集中分發(fā)機(jī)制是Android、iOS等移動(dòng)平臺(tái)區(qū)別于PC平臺(tái)軟件生態(tài)系統(tǒng)的重要特點(diǎn)，移動(dòng)應(yīng)用市場(chǎng)在保護(hù)用戶安全和隱私方面扮演了重要的角色。Android應(yīng)用程序主要由程序代碼和資源文件構(gòu)成，資源文件包括UI、多類型資源的xml文件（如顏色、字符串等）、圖片、音頻和視頻等。程序代碼主要包括由Java語言編寫編譯生成的Dalvik字節(jié)碼和由C/C++語言編寫編譯生成的so文件。本文僅考慮修改由Java語言編寫生成的重打包應(yīng)用，修改由C/C++語言編寫的本地代碼不在本文的研究范圍內(nèi)，而且鮮有報(bào)告指出惡意開發(fā)者通過修改本地代碼生成重打包應(yīng)用。

在Android應(yīng)用程序靜態(tài)分析中，通常會(huì)受到第三方的庫文件和代碼混淆的影響。在Android應(yīng)用程序中第三方的庫文件被大量使用如功能擴(kuò)展庫、工具類庫等。這些庫文件會(huì)占用一定比例的代碼，它們的存在也嚴(yán)重影響基于程序分析的應(yīng)用相似性比較[38]。應(yīng)用開發(fā)者從保護(hù)版權(quán)或應(yīng)用安全的角度出發(fā)，通常會(huì)對(duì)Android應(yīng)用進(jìn)行一些代碼混淆處理操作，這會(huì)直接導(dǎo)致程序分析技術(shù)應(yīng)用困難。應(yīng)用UI是Android應(yīng)用4個(gè)組件之一Activity的重要表現(xiàn)形式，重打包應(yīng)用為了誘導(dǎo)用戶下載安裝使用，通常不修改應(yīng)用UI的結(jié)構(gòu)。利用應(yīng)用UI作為應(yīng)用相似性特征表示，可以降低在程序分析階段由于第三方的庫文件、代碼混淆等對(duì)分析造成的影響。

3.2 重打包應(yīng)用

謀取非法收益和傳播惡意代碼收集用戶的隱私數(shù)據(jù)，實(shí)施非法攻擊威脅用戶的安全是惡意開發(fā)者制造重打包應(yīng)用的主要?jiǎng)訖C(jī)。Android平臺(tái)重打包應(yīng)用的最大特點(diǎn)是惡意開發(fā)者在保持原有合法應(yīng)用核心功能不變的基礎(chǔ)上，通過增加、刪除和修改程序代碼以及改變應(yīng)用資源文件等方法生成重打包應(yīng)用。根據(jù)惡意開發(fā)者修改apk文件的內(nèi)容以及重打包應(yīng)用構(gòu)造的精細(xì)程度，本文對(duì)重打包應(yīng)用主要概括為以下4種類型。

類型1 不修改UI和程序代碼。一些惡意開發(fā)者在生成重打包應(yīng)用時(shí)保持應(yīng)用UI和程序代碼不變，僅僅修改簽名或替換一些廣告庫等。

類型2 不修改UI，修改部分程序代碼。一些重打包應(yīng)用僅僅修改UI組件的屬性如替換UI中的字符顯示、圖片等，不修改UI的結(jié)構(gòu)，但是增加、刪除和修改部分程序代碼。

類型3 不修改UI，修改程序代碼但保持功能語義相同。保持UI結(jié)構(gòu)不變，惡意開發(fā)者在理解應(yīng)用功能的基礎(chǔ)上，重新編寫代碼實(shí)現(xiàn)相似的應(yīng)用功能。

類型4 UI不同，僅復(fù)制或修改部分功能代碼片段。該類型重打包應(yīng)用主要是開發(fā)者抄襲了其他應(yīng)用的部分功能，復(fù)制部分代碼作為重打包應(yīng)用的子功能。

4 總體設(shè)計(jì)

本節(jié)主要介紹所提方法的基本思想以及系統(tǒng)的總體設(shè)計(jì)等內(nèi)容。目前，針對(duì)Android平臺(tái)的重打包應(yīng)用檢測(cè)方法難以在檢測(cè)的速度、檢測(cè)的準(zhǔn)確率和計(jì)算資源開銷等三方面做到有效的平衡，導(dǎo)致在百萬級(jí)應(yīng)用市場(chǎng)的大規(guī)模檢測(cè)中存在困難。研究發(fā)現(xiàn)重打包應(yīng)用通常不修改或較少修改應(yīng)用UI的結(jié)構(gòu)，本文基于此發(fā)現(xiàn)提出了一種兩階段的檢測(cè)方案，實(shí)現(xiàn)應(yīng)用快速準(zhǔn)確的相似性比較。

本文重打包應(yīng)用系統(tǒng)SPRD的框架如圖1所示。首先從各大應(yīng)用市場(chǎng)收集大量的Android應(yīng)用程序，其中，包括Android的官方應(yīng)用市場(chǎng)Google Play。第一階段應(yīng)用UI的快速相似性比較步驟主要分為預(yù)處理和相似性檢測(cè)這2個(gè)部分，在預(yù)處理中，首先抽取Android應(yīng)用的UI，將UI中每一個(gè)視圖（view）生成一種抽象化的表示，并使用散列算法生成view的唯一指紋值；在相似性檢測(cè)部分將每一個(gè)應(yīng)用的view指紋值進(jìn)行比對(duì)，并將指紋值相同的view做聚類處理，找出UI相似的應(yīng)用，輸出可疑的重打包應(yīng)用集合。在第二階段程序代碼的細(xì)粒度克隆檢測(cè)中，首先，反編譯在第一階段中輸出的可疑重打包應(yīng)用，生成每一個(gè)應(yīng)用的PDG作為其特征表示，利用圖的相似性比較算法實(shí)現(xiàn)程序代碼的克隆檢測(cè)。最后，根據(jù)上述2個(gè)階段計(jì)算得出的相似值進(jìn)行綜合判定完成重打包應(yīng)用的檢測(cè)。

本文方法能夠有效檢測(cè)類型1和類型 2的重打包應(yīng)用。針對(duì)類型3的重打包應(yīng)用，可以運(yùn)用本文中第一階段的方法獲得可疑重打包應(yīng)用，降低應(yīng)用在程序分析階段的規(guī)模，顯著提高分析和檢測(cè)的效率。針對(duì)類型4的重打包應(yīng)用，可以運(yùn)用本文第二階段的代碼克隆檢測(cè)方法，實(shí)現(xiàn)有效檢測(cè)。但是會(huì)存在檢測(cè)速度慢、難以拓展至百萬級(jí)應(yīng)用市場(chǎng)規(guī)模的問題。

5 SPRD方法

5.1 基本定義

本文的兩階段重打包應(yīng)用檢測(cè)方法主要從應(yīng)用UI和程序代碼2個(gè)部分展開比較，在詳細(xì)描述本文的檢測(cè)方法之前，這里先給出一些基本的符號(hào)解釋和定義。

定義1 Android應(yīng)用程序。Android應(yīng)用程序表示為=(,)。其中，代表應(yīng)用的用戶交互界面UI，代表應(yīng)用程序代碼。

圖1 Android重打包應(yīng)用檢測(cè)系統(tǒng)SPRD框架

定義2 Android應(yīng)用UI。Android應(yīng)用UI表示為{V},=1,…,。其中，V表示應(yīng)用的視圖view，表示應(yīng)用中view的個(gè)數(shù)。Android應(yīng)用UI的view表示為=<,,>。其中，和分別表示布局和組件集合，表示布局和組件之間的包含關(guān)系。Android應(yīng)用UI的多個(gè)view之間通過事件進(jìn)行切換，view中每個(gè)組件（如Button、ImageView等）都包含在布局（如LinearLayout、ScrollView等）中控制顯示。

定義3 Android應(yīng)用程序代碼。Android應(yīng)用程序代碼表示為{G},1,…,。其中，G表示Android應(yīng)用Dalvik字節(jié)碼生成的程序依賴圖，表示應(yīng)用程序中函數(shù)的個(gè)數(shù)。應(yīng)用程序依賴圖表示為<,，其中，表示函數(shù)的語句集，表示邊集，當(dāng)語句之間有數(shù)據(jù)或控制依賴時(shí)，語句之間存在有向邊連接。

5.2 應(yīng)用UI相似性比較

本文中第一階段利用應(yīng)用UI作為特征進(jìn)行應(yīng)用的相似性比較，發(fā)現(xiàn)UI相似的可疑重打包應(yīng)用，主要分為離線和在線2種分析比較方式。在離線分析中，從各大Android應(yīng)用市場(chǎng)中收集大量的應(yīng)用樣本，通過在收集的待測(cè)應(yīng)用中做UI的相似性比較識(shí)別可疑的重打包應(yīng)用。離線分析檢測(cè)過程中，本文中構(gòu)建應(yīng)用view的指紋數(shù)據(jù)庫，每個(gè)應(yīng)用view都有相應(yīng)的指紋標(biāo)識(shí)。在線分析中，針對(duì)剛上架的移動(dòng)應(yīng)用，根據(jù)待檢測(cè)應(yīng)用生成的view指紋，在指紋數(shù)據(jù)庫中按照指紋的屬性字段進(jìn)行線性查找，實(shí)現(xiàn)從移動(dòng)應(yīng)用市場(chǎng)中快速地匹配出UI相似的應(yīng)用。利用UI進(jìn)行相似性檢測(cè)能夠大幅度減少程序代碼的比較次數(shù)和分析時(shí)間，降低計(jì)算資源的開銷，提高檢測(cè)的速度。

本文提出了一種應(yīng)用UI的抽象表示方法，實(shí)現(xiàn)應(yīng)用UI的快速檢測(cè)，識(shí)別檢測(cè)可疑的重打包應(yīng)用，如圖1中第一階段所示。在UI相似的可疑重打包應(yīng)用檢測(cè)中，主要分為預(yù)處理和相似性檢測(cè)等兩部分。在預(yù)處理中，本文提出了一種應(yīng)用UI抽象表示方法，能夠有效抵御如修改view和組件的屬性、插入以及修改部分view和組件等攻擊。同時(shí)，設(shè)計(jì)了一種基于應(yīng)用UI抽象表示的指紋生成方法，用于實(shí)現(xiàn)相似應(yīng)用view的快速比較、匹配和查找等操作。在相似性檢測(cè)中，主要是通過比較應(yīng)用UI的view指紋。將相同的view指紋放入到同一個(gè)類別中，完成指紋的聚類操作。然后，通過比較2個(gè)應(yīng)用中相同view比例來分析應(yīng)用的相似性。最后，輸出UI相似的可疑重打包應(yīng)用到下一階段進(jìn)行細(xì)粒度的程序代碼相似性檢測(cè)。

應(yīng)用的UI相似性檢測(cè)主要包括UI組件的抽取、UI抽象表示、應(yīng)用特征指紋的生成以及相似性計(jì)算等部分，本節(jié)將詳細(xì)介紹這些組成部分的細(xì)節(jié)內(nèi)容。

1) UI抽取

在應(yīng)用UI的相似性檢測(cè)中首先需要抽取應(yīng)用UI的特征表示，獲取應(yīng)用UI的基本組成單元。在Android應(yīng)用中，UI的基本組成單元是view。view中包含有多個(gè)與用戶直接進(jìn)行交互的組件，如按鈕Button，每個(gè)組件都屬于一個(gè)布局（ViewGroup），如線性布局LinearLayout。圖2是從Google Play中下載解析微信應(yīng)用中的一個(gè)view得到的樹型結(jié)構(gòu)圖，每一個(gè)節(jié)點(diǎn)均表示組件或布局。每個(gè)組件都有屬性標(biāo)識(shí)，本文不抽取屬性“visibility= "invisible"”的組件，因?yàn)橥ㄟ^研究分析發(fā)現(xiàn)大量的惡意應(yīng)用會(huì)在view中添加這類不可見的組件，繞過檢測(cè)。

圖2 view樹型結(jié)構(gòu)

本文直接反編譯應(yīng)用獲取apk文件中的布局文件，解析應(yīng)用UI的view結(jié)構(gòu)。本文的view解析方法，相比于ViewDroid[9]等不需要通過反編譯代碼獲取動(dòng)態(tài)生成的布局結(jié)構(gòu)，節(jié)省了大量的計(jì)算資源開銷。同時(shí)，本文增加了細(xì)粒度的代碼克隆檢測(cè)，用于克服應(yīng)用UI作為特征表示帶來的漏報(bào)。

2) UI抽象表示

將應(yīng)用UI的view樹型結(jié)構(gòu)進(jìn)行特征抽象表示，用于實(shí)現(xiàn)快速的相似性檢測(cè)。惡意開發(fā)者在制造重打包應(yīng)用時(shí)，通常會(huì)修改view中組件的屬性，如位置、大小、文本的文字內(nèi)容、圖片的鏈接等。但是，應(yīng)用中UI的view結(jié)構(gòu)通常不會(huì)被修改。本文使用一種抽象化表示規(guī)則來轉(zhuǎn)變view的結(jié)構(gòu)表示，然后將應(yīng)用中所有的view組合形成應(yīng)用UI的抽象表示集合?；谖闹械腢I抽象表示方法，將圖2的樹型view結(jié)構(gòu)表示成線性文本，本文的抽象表示規(guī)則具體如下。

元素表示。針對(duì)view的基本組成元素組件和布局，不考慮它們的屬性，直接表示成其名稱字符串小寫的形式，如布局LinearLayout表示成字符串“l(fā)inearlayout”，組件Button表示成“button”，組件“CheckBox”表示成“checkbox”等。

視圖表示。在UI抽取中，view表示成樹型結(jié)構(gòu)如圖2所示。本文將樹型結(jié)構(gòu)按廣度優(yōu)先遍歷將每一層的節(jié)點(diǎn)逐層進(jìn)行線性表示，同一層的兄弟節(jié)點(diǎn)按照字符串字典排序，針對(duì)同一層中值相同的兄弟節(jié)點(diǎn)，比較以該節(jié)點(diǎn)為頂點(diǎn)的子樹大小。表1是圖1的樹型結(jié)構(gòu)描述，并按照節(jié)點(diǎn)的抽象表示進(jìn)行排序。

根據(jù)表1和view樹型結(jié)構(gòu)線性抽象表示規(guī)則，圖2中的應(yīng)用view樹型結(jié)構(gòu)線性抽象化表示為“(a(b(c,d(g(j,k,l)),e(h,i),f)))”，然后將表1中的ID分別用相應(yīng)的節(jié)點(diǎn)抽象表示字符串做替換，得出最終的線性表示，如圖3所示。view樹型結(jié)構(gòu)線性抽象表示算法設(shè)計(jì)如算法1所示。

表1 view樹型結(jié)構(gòu)描述

view線性抽象表示(linearlayout(relativelayout(imageview,linearlayout(linearlayout(textview,textview,textview)),relativelayout(button,progressbar),textview))) 散列值7c3e342aab2cdb8d1e088a7f60e3c7af 指紋三元組{140,7c3e342aab2cdb8d1e088a7f60e3c7af, com.tencent.mm }

圖3 view指紋生成

算法1 view樹型結(jié)構(gòu)線性抽象表示

輸入 UI的view結(jié)構(gòu)樹

輸出 UI的view線性抽象表示

①=(); /*獲取樹的高度*/

② forin range(0,)

⑤=(); /* 判斷集合中是否存在值相同的節(jié)點(diǎn)*/

⑥ if=true

⑧(,,); /* 比較相同節(jié)點(diǎn)的子樹，并調(diào)整集合節(jié)點(diǎn)的順序*/

⑨ end if

?end for

3) 指紋生成

對(duì)每一個(gè)view進(jìn)行抽象表示之后，生成相應(yīng)的指紋對(duì)其進(jìn)行表示，實(shí)現(xiàn)應(yīng)用相似view的快速比較、匹配和查找等操作。本文中應(yīng)用UI的view指紋表示成一個(gè)三元組的形式，用于快速地識(shí)別可疑的重打包應(yīng)用。其指紋的三元組表示為<,,>。其中，為線性抽象表示字符串的長度，表示字符串的散列值，表示為應(yīng)用程序的ID。圖3為圖2中view生成的指紋，圖2是從Google Play中獲取的微信應(yīng)用（:）。

在生成view的指紋后，SPRD以鍵值對(duì)的形式保存所有應(yīng)用view指紋的三元組在字典中。其中，鍵key是字符串長度，值value是散列值和應(yīng)用ID組成的二元組。在字典中，相同鍵的值以列表的形式連續(xù)存放。圖4為存放view的字典。

140 : {{‘7c3e342aab2cdb8d1e088a7f60e3c7af’, ‘com.tencent.mm’}} 圖4 存放應(yīng)用view指紋的字典DIC

4) UI相似應(yīng)用檢測(cè)

在UI相似應(yīng)用檢測(cè)中，通過比較應(yīng)用的UI相似性生成可疑的重打包應(yīng)用集合。然后將UI相似的可疑重打包應(yīng)用在本文方法的第二階段做細(xì)粒度的程序代碼相似性分析，檢測(cè)可疑的重打包應(yīng)用。SPRD的應(yīng)用UI相似性檢測(cè)分為離線檢測(cè)和在線檢測(cè)2種情況。其中，離線檢測(cè)是為了從已收集的應(yīng)用中找出UI相似的可疑重打包應(yīng)用；在線檢測(cè)是針對(duì)新上架的應(yīng)用，在已收集的應(yīng)用集合中，找出UI相似的應(yīng)用。

在離線的UI相似應(yīng)用檢測(cè)中，依次遍歷字典的鍵，針對(duì)中相同鍵值的列表，將列表中抽象表示字符串的散列值進(jìn)行兩兩相似性比較。如果值相同，則檢測(cè)出相似的應(yīng)用view。在得到存在view相似的應(yīng)用后，通過分析2個(gè)應(yīng)用中所有的view相似比例來度量應(yīng)用UI的相似性，從而判定其是否為一對(duì)可疑的重打包應(yīng)用。

應(yīng)用UI的相似性度量如式(1)所示，通過計(jì)算2個(gè)應(yīng)用UI的view相似比例來判定是否為可疑的重打包應(yīng)用。在式(1)中，1和2表示應(yīng)用的UI（如定義2所示），1×2表示應(yīng)用1和應(yīng)用2的view笛卡爾集。在笛卡爾集1×2中，集合元素表示為(V,V')，其中，V和V'分別為應(yīng)用1和應(yīng)用2的view。函數(shù)(1×2,)用于檢測(cè)集合1×2中第個(gè)元素的view對(duì)是否相似，如果相似則函數(shù)返回1，否則返回0。|1×2|表示集合中元素的個(gè)數(shù)，|1|和|2|分別表示應(yīng)用1和應(yīng)用2中UI的view個(gè)數(shù)。

如果(1,2)大于閾值0.8，判定這2個(gè)應(yīng)用的UI相似，下一步將UI相似的應(yīng)用做細(xì)粒度的程序代碼克隆檢測(cè)。其中，通過大量的測(cè)試樣本調(diào)節(jié)發(fā)現(xiàn)，閾值為0.8是比較合理的。

5.3 程序代碼相似性比較

相同模板開發(fā)出來的應(yīng)用，UI總是保持相似，但它們并不是重打包應(yīng)用。因此，針對(duì)這類重打包應(yīng)用需要在應(yīng)用程序的代碼層進(jìn)行細(xì)粒度的代碼相似性檢測(cè)，識(shí)別相似的代碼片段，降低使用應(yīng)用UI作為特征檢測(cè)帶來的誤報(bào)率。相同應(yīng)用的不同版本，UI有時(shí)也會(huì)保持較高的相似性。但是它們的簽名相同，可以通過提取應(yīng)用的簽名信息來判定應(yīng)用是否為不同版本的應(yīng)用。

本文使用程序依賴圖PDG作為應(yīng)用程序代碼的特征表示，實(shí)現(xiàn)細(xì)粒度的代碼克隆檢測(cè)?；赑DG的代碼特征表示可以有效地抵御攻擊者在應(yīng)用程序代碼中插入、刪除語句以及修改語句順序等操作的攻擊。PDG主要用于表示程序函數(shù)體中語句之間的依賴關(guān)系，包括數(shù)據(jù)依賴和控制依賴等2種[39]。由定義3可知，PDG的頂點(diǎn)是函數(shù)體中的語句，邊是指頂點(diǎn)的語句之間存在數(shù)據(jù)依賴或控制依賴。其中，數(shù)據(jù)依賴是指如果語句S1中數(shù)據(jù)依賴語句S2，則S1中有變量的值取決于S2；控制依賴是指如果語句S1與語句S2存在控制依賴關(guān)系，那么語句S1可以控制語句S2執(zhí)行與否。

本文程序代碼克隆檢測(cè)如圖5所示，在得到apk文件之后，對(duì)每一個(gè)apk文件做反編譯處理，抽取應(yīng)用程序中每個(gè)函數(shù)的PDG。由于第三方庫在應(yīng)用程序開發(fā)中被大量使用，使用白名單過濾第三方庫對(duì)程序代碼克隆檢測(cè)造成的影響。另外，一些代碼行數(shù)少的函數(shù)存在功能通用以及代碼模板相似的特點(diǎn)，這些函數(shù)的PDG更可能出現(xiàn)相似或相同的問題，因此，本文過濾掉PDG的節(jié)點(diǎn)小于特定值（本文特定值設(shè)為8）的函數(shù)。程序代碼克隆檢測(cè)是通過2個(gè)程序代碼形成的PDG中找出相同的節(jié)點(diǎn)，該問題可以轉(zhuǎn)化成子圖同構(gòu)的問題，也即發(fā)現(xiàn)2個(gè)PDG中語句的映射關(guān)系，應(yīng)用的程序代碼相似性計(jì)算如式(2)所示。

在式(2)中，程序代碼D1和D2如定義3所示，|D1|表示程序代碼D1的函數(shù)個(gè)數(shù)（過濾掉通用的第三方庫），C(G)表示D1在D2中找到最佳匹配子圖的節(jié)點(diǎn)個(gè)數(shù)。

5.4 重打包應(yīng)用檢測(cè)

本文利用惡意開發(fā)者為了誘導(dǎo)用戶下載安裝使用重打包應(yīng)用，通常不修改應(yīng)用UI結(jié)構(gòu)的特點(diǎn)。提出了一種基于應(yīng)用UI抽象表示的散列快速可疑重打包應(yīng)用檢測(cè)方法以及通過細(xì)粒度的程序代碼分析實(shí)現(xiàn)準(zhǔn)確的代碼克隆檢測(cè)。細(xì)粒度的代碼克隆檢測(cè)用于降低使用應(yīng)用UI作為特征檢測(cè)帶來的誤報(bào)率，提高重打包應(yīng)用檢測(cè)的準(zhǔn)確率。

在本文兩階段重打包應(yīng)用檢測(cè)中，需要統(tǒng)計(jì)和分析有多少應(yīng)用UI和應(yīng)用程序代碼被惡意開發(fā)者在合法應(yīng)用基礎(chǔ)上做了多大程度的修改。在研究過程中，發(fā)現(xiàn)重打包應(yīng)用具有以下2個(gè)特點(diǎn)：1) 重打包應(yīng)用的UI常保持不變，惡意開發(fā)者會(huì)插入或修改程序代碼，因此，相比于應(yīng)用UI，程序代碼更能表示應(yīng)用的特征；2) 在Android應(yīng)用程序中，應(yīng)用UI中view的個(gè)數(shù)明顯少于應(yīng)用中函數(shù)的個(gè)數(shù)。

因此，在應(yīng)用的相似性計(jì)算中，需要考慮應(yīng)用UI和應(yīng)用程序代碼的相似度以及它們被修改的數(shù)量或比例等因素。由上述的重打包應(yīng)用特點(diǎn)可知，應(yīng)用的相似性受程序代碼的影響更大。在本文中，應(yīng)用1和2相似性計(jì)算表示為：(1,2)?(1,2)(1?)?(1,2)。其中，系數(shù)為權(quán)重系數(shù)，根據(jù)應(yīng)用中view和應(yīng)用程序代碼中函數(shù)的個(gè)數(shù)計(jì)算得出，用于反映有多少應(yīng)用的view和函數(shù)被修改。具體的計(jì)算如式(3)~式(5)所示。

其中，1、2和1、2|分別表示應(yīng)用UI的view和應(yīng)用程序代碼的函數(shù)個(gè)數(shù)，(1,2)和(1,2)如式(1)和式(2)所示，如果(1,2)大于閾值0.85，判定應(yīng)用1和2是一對(duì)重打包應(yīng)用。通過大量的測(cè)試樣本調(diào)節(jié)發(fā)現(xiàn)，閾值為0.85是比較合理的。

6 實(shí)驗(yàn)與結(jié)果分析

6.1 方法實(shí)現(xiàn)

Android平臺(tái)重打包應(yīng)用檢測(cè)實(shí)驗(yàn)部分主要有以下6個(gè)步驟。

1) apk文件反編譯。使用Keytool提取應(yīng)用的簽名信息，作為唯一標(biāo)識(shí)區(qū)分應(yīng)用。Apktool用來反編譯應(yīng)用程序，獲取apk的資源文件和smali代碼等，解析應(yīng)用UI的xml文件獲取應(yīng)用UI的view結(jié)構(gòu)。

2) UI指紋生成。本文使用MD5算法生成UI線性抽象表示的散列值。

3) 指紋字典存儲(chǔ)。本文選擇使用Python自帶的數(shù)據(jù)字典結(jié)構(gòu)，能夠在(1)時(shí)間復(fù)雜度內(nèi)實(shí)現(xiàn)鍵的查找。

4) 第三方庫過濾。本文使用文獻(xiàn)[40]中提供的1 113個(gè)第三方功能庫和240個(gè)廣告庫作為白名單，過濾待測(cè)應(yīng)用中的第三方庫。

5) 應(yīng)用程序代碼的PDG生成。本文使用soot[41]為程序中所有類的每種方法生成PDG。在本文設(shè)置當(dāng)語句之間存在數(shù)據(jù)依賴時(shí)，語句之間建立有向邊連接，有研究發(fā)現(xiàn)數(shù)據(jù)依賴更加有效的對(duì)抗（如程序代碼中修改、插入等攻擊行為）。

6) 程序代碼相似性比較。本文使用VF2算法[37]找出PDG的同構(gòu)子圖，識(shí)別相似的程序代碼片段。

6.2 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)來源

基于所提方法，本文實(shí)現(xiàn)了面向大規(guī)模的Android重打包應(yīng)用快速檢測(cè)方法原型系統(tǒng)SPRD，具體的實(shí)驗(yàn)環(huán)境CPU為Intel(R) Core(TM) i7-6700K 4 GHz，32 GB內(nèi)存，操作系統(tǒng)為Ubuntu14.04。

本文中實(shí)驗(yàn)數(shù)據(jù)來源于Android官方應(yīng)用商店Google Play，國內(nèi)應(yīng)用商店（Baidu、Anzhi）、美國應(yīng)用商店（Pandaapp）和歐洲應(yīng)用商店（Opera）等，具體的各應(yīng)用商店的實(shí)驗(yàn)數(shù)據(jù)采集情況如表2所示。實(shí)驗(yàn)數(shù)據(jù)中apk文件大小分布如圖6所示，收集的apk文件最小的為8 KB，最大的為49.5 MB，超過76%的apk文件大小超過1 MB，有超過60%的apk文件大小為1~10 MB，這些實(shí)驗(yàn)數(shù)據(jù)基本上可以代表Android應(yīng)用市場(chǎng)中應(yīng)用程序的普遍大小。采集的所有apk文件超過7 TB，代碼總量超過10億行。

表2 實(shí)驗(yàn)數(shù)據(jù)采集

圖6 實(shí)驗(yàn)數(shù)據(jù)中apk文件大小分布

6.3 實(shí)驗(yàn)結(jié)果分析

在本文的實(shí)驗(yàn)結(jié)果評(píng)價(jià)中，主要從本文方法在大規(guī)模應(yīng)用市場(chǎng)重打包應(yīng)用檢測(cè)的速度和檢測(cè)的準(zhǔn)確率2個(gè)部分來分析實(shí)驗(yàn)結(jié)果。

本文方法分為2個(gè)階段，第一階段利用重打包應(yīng)用不修改應(yīng)用UI的結(jié)構(gòu)，它們的UI保持相似的特征，識(shí)別出UI相似的可疑重打包應(yīng)用。圖7表示在第一階段的UI相似性檢測(cè)中，應(yīng)用數(shù)量的增長與UI相似性檢測(cè)時(shí)間的關(guān)系。從圖7可以看出，在離線分析中，隨著應(yīng)用數(shù)量的增加，應(yīng)用UI相似性檢測(cè)的時(shí)間并不發(fā)生顯著變化。在生成應(yīng)用指紋之后，本文的應(yīng)用view相似性比較方法，依然可以在13 s內(nèi)從百萬級(jí)應(yīng)用中快速地檢測(cè)出view相似的應(yīng)用。因此，本文所提UI相似性檢測(cè)方法可以有效應(yīng)用于大規(guī)模移動(dòng)應(yīng)用市場(chǎng)。

圖7 應(yīng)用數(shù)量與應(yīng)用UI相似性檢測(cè)時(shí)間關(guān)系

應(yīng)用UI的相似性檢測(cè)用于提高第二階段中細(xì)粒度的程序代碼克隆檢測(cè)效率，降低程序代碼克隆檢測(cè)中比較的次數(shù)。圖8表示在第二階段的程序代碼克隆檢測(cè)中，應(yīng)用數(shù)量的增長與代碼對(duì)比較次數(shù)的關(guān)系。從圖8可以發(fā)現(xiàn)，隨著應(yīng)用數(shù)量的增長，如果不通過第一階段的UI相似性分析找出可疑的重打包應(yīng)用，僅僅通過應(yīng)用程序代碼兩兩比較檢測(cè)應(yīng)用的相似性，其代碼比較的次數(shù)呈現(xiàn)指數(shù)爆炸式增長。通過對(duì)比發(fā)現(xiàn)，本文利用第一階段的UI相似性比較，其程序代碼的比較次數(shù)依然可以保持在線性增長空間中。

圖8 程序代碼對(duì)比較次數(shù)與應(yīng)用數(shù)量關(guān)系

在檢測(cè)時(shí)間方面，SPRD完整檢測(cè)時(shí)間包括第一階段的應(yīng)用UI相似性檢測(cè)和第二階段的細(xì)粒度代碼克隆檢測(cè)。由于本文第一階段UI相似性檢測(cè)中能夠?qū)?yīng)用分析的規(guī)模壓縮到原規(guī)模的11.3%左右，而在第一階段中應(yīng)用UI的分析與檢測(cè)平均時(shí)間只是第二階段代碼克隆檢測(cè)時(shí)間的10%左右。因此，SPRD的完整檢測(cè)時(shí)間明顯快于文獻(xiàn)[6]、文獻(xiàn)[33]、文獻(xiàn)[7]等基于代碼克隆檢測(cè)的方法。本文方法SPRD能夠在15.2 s完成完整百萬級(jí)的重打包應(yīng)用檢測(cè)，按照Centroid[30]實(shí)驗(yàn)評(píng)價(jià)檢測(cè)時(shí)間線性增長規(guī)律計(jì)算可知，其處理百萬級(jí)應(yīng)用時(shí)的平均檢測(cè)時(shí)間在25.6 s。在特征抽取中，SPRD相比于Centroid僅有11.3%的待測(cè)應(yīng)用需要進(jìn)行耗時(shí)的代碼分析，但是Centroid需要利用程序分析方法抽取所有待分析應(yīng)用的控制流圖。

圖9表示在5.2節(jié)應(yīng)用UI相似性檢測(cè)和5.4節(jié)重打包應(yīng)用檢測(cè)中，閾值與準(zhǔn)確率的關(guān)系。實(shí)驗(yàn)中通過多次測(cè)試調(diào)整閾值發(fā)現(xiàn)，閾值設(shè)為0.8時(shí)，UI的相似性檢測(cè)準(zhǔn)確率最高達(dá)到87.1%；閾值設(shè)為0.85時(shí)，應(yīng)用的相似性檢測(cè)準(zhǔn)確率最高達(dá)到93.3%。

在本文中，重打包應(yīng)用檢測(cè)的結(jié)果利用機(jī)器學(xué)習(xí)中經(jīng)常使用到的指標(biāo)進(jìn)行評(píng)價(jià)和度量，分別是：1) 真陽性（TP, true positive）；2) 假陽性（FP, false positive）；3) 真陰性（TN, true negative）；4) 假陰性（FN, false negative）。這4個(gè)度量指標(biāo)的具體含義如表3所示。

表3 度量指標(biāo)含義

根據(jù)4個(gè)度量指標(biāo)，構(gòu)成以下4個(gè)常用指標(biāo)。具體計(jì)算式為

Androguard是一個(gè)用于Android應(yīng)用逆向分析和靜態(tài)分析的開源工具。本文使用Androguard測(cè)試文中檢測(cè)出的重打包應(yīng)用的準(zhǔn)確性。實(shí)驗(yàn)結(jié)果分析發(fā)現(xiàn)，本文方法能夠?qū)崿F(xiàn)精準(zhǔn)率（precision）為93.4%，召回率（recall）為90.5%，準(zhǔn)確率和召回率的調(diào)和平均值（F-score）為91.9%，準(zhǔn)確率（accuracy）為93.3%。

利用本文的重打包應(yīng)用檢測(cè)系統(tǒng)SPRD分析表2中收集的測(cè)試應(yīng)用，5個(gè)應(yīng)用市場(chǎng)中重打包應(yīng)用分布情況如表4所示。

表4 應(yīng)用市場(chǎng)中重打包應(yīng)用比例

從實(shí)驗(yàn)結(jié)果分析看，相比于現(xiàn)有的基于代碼克隆的檢測(cè)和基于應(yīng)用資源文件的檢測(cè)方法，本文的兩階段重打包應(yīng)用檢測(cè)方法能夠?qū)崿F(xiàn)檢測(cè)準(zhǔn)確率高、檢測(cè)速度快以及計(jì)算資源開銷小等。本文方法與這2類方法在檢測(cè)速度、檢測(cè)準(zhǔn)確率和計(jì)算資源開銷這3個(gè)方面的比較如表5所示。

表5 重打包應(yīng)用檢測(cè)方法比較

6.4 相關(guān)討論

本文使用白名單機(jī)制過濾第三方的庫文件在代碼克隆檢測(cè)中帶來的干擾，由于收集到的第三方庫存在不完備等問題，在檢測(cè)中會(huì)造成一些誤報(bào)率。在未來的工作中，嘗試收集更多第三方的庫文件減少這方面的誤報(bào)率。在程序代碼克隆檢測(cè)中，本文主要分析應(yīng)用程序的Java代碼，沒有考慮應(yīng)用程序的本地代碼。因此，修改本地代碼的重打包行為，文中的方法并不奏效?？梢詰?yīng)用二進(jìn)制代碼克隆檢測(cè)相關(guān)技術(shù)解決本文工作在本地代碼克隆檢測(cè)中的不足，但是少有研究指出惡意的開發(fā)者通過修改本地代碼生成重打包應(yīng)用，因此，本文的研究范圍依然是合理的。

本文方法不需要反編譯所有的待檢測(cè)應(yīng)用，抽取它們的程序代碼特征表示，節(jié)省了大量的計(jì)算資源開銷。計(jì)算的時(shí)間復(fù)雜度方面，通過第一階段的UI相似性分析，檢測(cè)出可疑重打包應(yīng)用集合||?（待檢測(cè)應(yīng)用數(shù)量）。在使用PDG作為特征表示進(jìn)行代碼克隆檢測(cè)時(shí)，其中，VF2算法在最壞情況的時(shí)間復(fù)雜度為(!)，最好情況為(2)，可以滿足大規(guī)模環(huán)境中快速檢測(cè)的要求。

7 結(jié)束語

本文提出了一種基于應(yīng)用UI和程序代碼的兩階段重打包應(yīng)用檢測(cè)方法，利用重打包應(yīng)用不修改應(yīng)用UI結(jié)構(gòu)的特點(diǎn)，設(shè)計(jì)了一種基于應(yīng)用UI抽象表示的散列快速相似性檢測(cè)方法。然后，使用PDG作為應(yīng)用的特征表示，實(shí)現(xiàn)應(yīng)用程序代碼的克隆檢測(cè)，提高應(yīng)用相似性檢測(cè)的準(zhǔn)確率，并降低使用應(yīng)用UI作為特征檢測(cè)帶來的誤報(bào)率。實(shí)驗(yàn)結(jié)果表明，本文方法可以應(yīng)用于百萬級(jí)應(yīng)用市場(chǎng)的重打包應(yīng)用檢測(cè)與防御，不僅具有較高的檢測(cè)準(zhǔn)確率，而且通過兩階段的檢測(cè)方法可以節(jié)約大量的計(jì)算資源開銷。本文的方法解決了現(xiàn)有Android平臺(tái)重打包應(yīng)用檢測(cè)方法難以在檢測(cè)的速度、檢測(cè)的準(zhǔn)確率和計(jì)算資源開銷這3個(gè)方面進(jìn)行有效平衡的問題。但本文的重打包應(yīng)用檢測(cè)系統(tǒng)也存在一些缺陷，需要做進(jìn)一步改進(jìn)。

本文檢測(cè)方法仍然需要通過分析應(yīng)用的相似性實(shí)現(xiàn)重打包應(yīng)用檢測(cè)，未來工作嘗試抽取重打包應(yīng)用程序的內(nèi)在特征實(shí)現(xiàn)檢測(cè)，例如程序代碼的風(fēng)格、代碼間的關(guān)聯(lián)程度等。針對(duì)部分程序代碼的克隆問題，未來的工作試圖抽取一種輕量級(jí)的代碼特征，實(shí)現(xiàn)快速比較并且可以對(duì)抗代碼插入、修改等攻擊。

[1] ZHOU Y, JIANG X. Dissecting Android malware: characterization and evolution[C]//IEEE Symposium on Security and Privacy (SP).2012: 95-109.

[2] ACAR Y, BACKES M, BUGIEL S, et al. Sok: lessons learned from Android security research for appified software platforms[C]// 2016 IEEE Symposium on Security and Privacy (SP). 2016: 433-451.

[3] XU M, SONG C, JI Y, et al. Toward engineering a secure Android ecosystem: a survey of existing techniques[J]. ACM Computing Surveys (CSUR), 2016, 49(2): 38.

[4] ZHOU W, ZHOU Y, JIANG X, et al. Detecting repackaged smartphone applications in third-party Android marketplaces[C]//The second ACM conference on Data and Application Security and Privacy. 2012: 317-326.

[5] HANNA S, HUANG L, WU E, et al. Juxtapp: a scalable system for detecting code reuse among Android applications[C]//International Conference on Detection of Intrusions and Malware, and Vulnerability Assessment. 2012: 62-81.

[6] CRUSSELL J, GIBLER C, CHEN H. Attack of the clones: detecting cloned applications on Android markets[C]//European Symposium on Research in Computer Security. 2012: 37-54.

[7] WANG H, GUO Y, MA Z, et al. Wukong: a scalable and accurate two-phase approach to Android app clone detection[C]//The 2015 International Symposium on Software Testing and Analysis. 2015: 71-82.

[8] 王浩宇, 王仲禹, 郭耀, 等. 基于代碼克隆檢測(cè)技術(shù)的Android應(yīng)用重打包檢測(cè)[J]. 中國科學(xué):信息科學(xué), 2014, 44(1): 142-157.

WANG H Y, WANG Z Y, GUO Y, et al. Detecting repackaged Android applications based on code clone detection technique[J]. Science China Information Sciences, 2014, 44(1): 142-157.

[9] ZHANG F, HUANG H, ZHU S, et al. ViewDroid: towards obfuscation-resilient mobile application repackaging detection[C]//The 2014 ACM Conference on Security and Privacy in Wireless & Mobile Networks. 2014: 25-36.

[10] SUN M, LI M, LUI J. Droideagle: seamless detection of visually similar Android apps[C]//The 8th ACM Conference on Security & Privacy in Wireless and Mobile Networks. 2015: 9.

[11] 焦四輩, 應(yīng)凌云, 楊軼, 等. 一種抗混淆的大規(guī)模Android 應(yīng)用相似性檢測(cè)方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(7): 1446-1457.

JIAO S B, YING L Y, YANG Y, et al. An anti-obfuscation method for detecting similarity among Android applications in large scale[J]. Journal of Computer Research and Development, 2014, 51(7): 1446-1457.

[12] 卿斯?jié)h. Android 安全研究進(jìn)展[J]. 軟件學(xué)報(bào), 2016, 27(1): 45-71.

QING S H. Research progress on Android security[J]. Journal of Software, 2016, 27(1): 45-71.

[13] 文偉平, 梅瑞, 寧戈, 等. Android 惡意軟件檢測(cè)技術(shù)分析和應(yīng)用研究[J]. 通信學(xué)報(bào), 2014, 35(8): 78-86.

WEN W P, MEI R, NING G, et al. Malware detection technology analysis and applied research of Android platform[J]. Journal on Communications, 2014, 35(8): 78-86.

[14] 張玉清, 王凱, 楊歡, 等. Android安全綜述[J].計(jì)算機(jī)研究與發(fā)展,2014,51(7):1385-1396.

ZHANG Y Q, WANG K, YANG H, et al. Survey of Android OS security[J]. Journal of Computer Research and Development, 2014, 51(7):1385-1396.

[15] 李挺, 董航, 袁春陽, 等. 基于Dalvik指令的Android惡意代碼特征描述及驗(yàn)證[J].計(jì)算機(jī)研究與發(fā)展,2014,51(7): 1458-1466.

LI T, DONG H, YUAN C Y, et al. Description of Android malware feature based on Dalvik instructions[J]. Journal of Computer Research and Development, 2014,51(7):1458-1466.

[16] 張玉清, 方喆君, 王凱, 等. Android 安全漏洞挖掘技術(shù)綜述[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(10): 2167-2177.

ZHANG Y Q, FANG Z J, WANG K, et al. Survey of Android vulnerability detection[J]. Journal of Computer Research and Development, 2015, 52(10): 2167-2177.

[17] 楊威, 肖旭生, 李鄧鋒, 等. 移動(dòng)應(yīng)用安全解析學(xué): 成果與挑戰(zhàn)[J]. 信息安全學(xué)報(bào), 2016, 1(2): 1-14.

YANG W, XIAO X S, LI D F, et al. Security analytics for mobile apps: achievements and challenges[J]. Journal of Cyber Security, 2016, 1(2): 1-14.

[18] 劉新宇, 翁健, 張悅, 等. 基于 APK 簽名信息反饋的Android 惡意應(yīng)用檢測(cè)[J]. 通信學(xué)報(bào), 2017, 38(5): 190-198.

LIU X Y, WENG J, ZHANG Y, et al. Android malware detection based on APK signature information feedback[J]. Journal on Communications, 2017, 38(5): 190-198.

[19] FAN M, LIU J, WANG W, et al. DAPASA: detecting Android piggybacked apps through sensitive subgraph analysis[J]. IEEE Transactions on Information Forensics and Security, 2017, 12(8): 1772-1785.

[20] 楊歡, 張玉清, 胡予濮, 等. 基于多類特征的Android 應(yīng)用惡意行為檢測(cè)系統(tǒng)[J]. 計(jì)算機(jī)學(xué)報(bào), 2014, 37(1): 15-27.

YANG H, ZHANG Y Q, HU Y P, et al. A malware behavior detection system of Android applications based on multi-class features[J]. Chinese Journal of Computers, 2014, 37(1): 15-27.

[21] ARP D, SPREITZENBARTH M, HUBNER M, et al. DREBIN: effective and explainable detection of Android malware in your pocket[C]//NDSS. 2014.

[22] YAN L K, YIN H. DroidScope: seamlessly reconstructing the os and dalvik semantic views for dynamic Android malware analysis[C]// USENIX Security Symposium. 2012: 569-584.

[23] ARZT S, RASTHOFER S, FRITZ C, et al. Flowdroid: precise context, flow, field, object-sensitive and lifecycle-aware taint analysis for Android apps[J]. ACM Sigplan Notices, 2014, 49(6): 259-269.

[24] ENCK W, GILBERT P, HAN S, et al. TaintDroid: an information-flow tracking system for realtime privacy monitoring on smartphones[J]. ACM Transactions on Computer Systems (TOCS), 2014, 32(2): 5.

[25] 許艷萍, 馬兆豐, 王中華, 等. Android 智能終端安全綜述[J]. 通信學(xué)報(bào), 2016, 37(6): 169-174.

XU Y P, MA Z F, WANG Z H, et al. Survey of security for Android smart terminal[J]. Journal on Communications, 2016, 37(6):169-174.

[26] LI L, LI D, BISSYANDE T F, et al. Understanding Android App piggybacking[C]//The 39th International Conference on Software Engineering Companion. 2017: 359-361.

[27] REAVES B, BOWERS J, GORSKI III S A, et al. Android: assessment and evaluation of Android application analysis tools[J]. ACM Computing Surveys (CSUR), 2016, 49(3): 55.

[28] GONZALEZ H, STAKHANOVA N, GHORBANI A A. Droidkin: lightweight detection of Android apps similarity[C]//International Conference on Security and Privacy in Communication Systems. 2014: 436-453.

[29] KIM D, GOKHALE A, GANAPATHY V, et al. Detecting plagiarized mobile apps using API birthmarks[J]. Automated Software Engineering, 2016, 23(4): 591-618.

[30] CHEN K, LIU P, ZHANG Y. Achieving accuracy and scalability simultaneously in detecting application clones on Android markets[C]//The 36th International Conference on Software Engineering. 2014: 175-186.

[31] CHEN K, WANG P, LEE Y, et al. Finding unknown malice in 10 seconds: mass vetting for new threats at the Google-Play Scale[C]//USENIX Security. 2015: 15.

[32] ZHOU W, ZHOU Y, GRACE M, et al. Fast, scalable detection of piggybacked mobile applications[C]//The Third ACM Conference on Data and Application Security and Privacy. 2013: 185-196.

[33] CRUSSELL J, GIBLER C, CHEN H. Andarwin: scalable detection of semantically similar Android applications[C]//European Symposium on Research in Computer Security. 2013: 182-199.

[34] SHAO Y, LUO X, QIAN C, et al. Towards a scalable resource-driven approach for detecting repackaged Android applications[C]//The 30th Annual Computer Security Applications Conference. 2014: 56-65.

[35] GADYATSKAYA O, LEZZA A L, ZHAUNIAROVICH Y. Evaluation of resource-based App repackaging detection in Android[C]//Nordic Conference on Secure IT Systems. 2016: 135-151.

[36] SOH C, TAN H B K, ARNATOVICH Y L, et al. Detecting clones in Android applications through analyzing user interfaces[C]//The 2015 IEEE 23rd International Conference on Program Comprehension. 2015: 163-173.

[37] CORDELLA L P, FOGGIA P, SANSONE C, et al. A (sub) graph isomorphism algorithm for matching large graphs[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(10): 1367-1372.

[38] LI M, WANG W, WANG P, et al. Libd: scalable and precise third-party library detection in Android markets[C]//The 39th International Conference on Software Engineering. 2017: 335-346.

[39] LIU C, CHEN C, HAN J, et al. GPLAG: detection of software plagiarism by program dependence graph analysis[C]//The 12th ACM SIGKDD International Conference On Knowledge Discovery And Data Mining. 2006: 872-881.

[40] LI L, BISSYANDé T F, KLEIN J, et al. An investigation into the use of common libraries in Android apps[C]//2016 IEEE 23rd International Conference on Software Analysis, Evolution, and Reengineering (SANER). 2016: 403-414.

[41] LAM P, BODDEN E, LHOTAK O, et al. The soot framework for Java program analysis: a retrospective[C]//Cetus Users and Compiler Infrastructure Workshop (CETUS 2011).2011.

SPRD: fast application repackaging detectionapproach in Android based on application’sUI and program dependency graph

WANG Run1,2,3, WANG Li’na1,2,3, TANG Benxiao1,2,3, ZHAO Lei1,2,3

1. Key Laboratory of Aerospace Information Security and Trusted Computing Ministry of Education, Wuhan University, Wuhan 430072, China 2. School of Computer, Wuhan University, Wuhan 430072, China3. School of Cyber Science and Engineering, Wuhan University, Wuhan 430072, China

A two stage detection approach which combine application’s UI and program code based on the observation that repackaging applications merely modify the structure of their user interface was proposed. Firstly, a fast hash similarity detection technique based on an abstracted representation of UI to identify the potential visual-similar repackaging applications was designed. Secondly, program dependency graph is used to represent as the feature of app to achieve fine-grained and precise code clone detection. A prototype system, SPRD, was implemented based on the proposed approach. Experimental results show that the proposed approach achieves a good performance in both scalability and accuracy, and can be effectively applied in millions of applications and billions of code detection.

repackaging, code clone, user interface, program dependency graph, security and privacy

TP309.1

A

10.11959/j.issn.1000-436x.2018045

2017-08-09；

2017-12-21

王麗娜，lnwang@whu.edu.cn

國家自然科學(xué)基金資助項(xiàng)目（No.U1536204, No.61672394, No.61373169, No.61672393）；國家高技術(shù)研究發(fā)展計(jì)劃（“863”計(jì)劃）基金資助項(xiàng)目（No.2015AA016004）

The National Natural Science Foundation of China (No.U1536204, No.61672394, No.61373169, No.61672393), The National High Technology Research and Development Program of China (863 Program) (No.2015AA016004)

汪潤（1991-），男，安徽安慶人，武漢大學(xué)博士生，主要研究方向?yàn)锳ndroid安全與隱私、系統(tǒng)安全等。

王麗娜（1964-），女，遼寧營口人，博士，武漢大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)橄到y(tǒng)安全、網(wǎng)絡(luò)安全、信息隱藏等。

唐奔宵（1991-），男，湖北黃石人，武漢大學(xué)博士生，主要研究方向?yàn)橐苿?dòng)安全與隱私、系統(tǒng)安全等。

趙磊（1985-），男，山東菏澤人，博士，武漢大學(xué)副教授、碩士生導(dǎo)師，主要研究方向?yàn)檐浖踩⑾到y(tǒng)安全等。