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

?

SPRD：基于應用UI和程序依賴圖的Android重打包應用快速檢測方法

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

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

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

重打包；代碼克?。挥脩艚缑?；程序依賴圖；安全與隱私

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 相關(guān)工作

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

2.1 基于代碼克隆的檢測

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

2.2 基于應用資源文件的檢測

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

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

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

3.1 Android應用程序

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

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

3.2 重打包應用

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

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

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

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

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

4 總體設(shè)計

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

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

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

5 SPRD方法

5.1 基本定義

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

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

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

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

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

5.2 應用UI相似性比較

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

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

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

1) UI抽取

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

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

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

2) UI抽象表示

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

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

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

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

⑥ if=true

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

⑨ end if

?end for

3) 指紋生成

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

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

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

4) UI相似應用檢測

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

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

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

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

5.3 程序代碼相似性比較

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

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

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

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

5.4 重打包應用檢測

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

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

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

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

6 實驗與結(jié)果分析

6.1 方法實現(xiàn)

Android平臺重打包應用檢測實驗部分主要有以下6個步驟。

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

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

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

4) 第三方庫過濾。本文使用文獻[40]中提供的1 113個第三方功能庫和240個廣告庫作為白名單，過濾待測應用中的第三方庫。

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

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

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

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

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

表2 實驗數(shù)據(jù)采集

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

6.3 實驗結(jié)果分析

在本文的實驗結(jié)果評價中，主要從本文方法在大規(guī)模應用市場重打包應用檢測的速度和檢測的準確率2個部分來分析實驗結(jié)果。

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

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

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

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

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

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

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

表3 度量指標含義

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

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

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

表4 應用市場中重打包應用比例

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

表5 重打包應用檢測方法比較

6.4 相關(guān)討論

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

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

7 結(jié)束語

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

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

[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] 王浩宇, 王仲禹, 郭耀, 等. 基于代碼克隆檢測技術(shù)的Android應用重打包檢測[J]. 中國科學:信息科學, 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] 焦四輩, 應凌云, 楊軼, 等. 一種抗混淆的大規(guī)模Android 應用相似性檢測方法[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]. 軟件學報, 2016, 27(1): 45-71.

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

[13] 文偉平, 梅瑞, 寧戈, 等. Android 惡意軟件檢測技術(shù)分析和應用研究[J]. 通信學報, 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].計算機研究與發(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惡意代碼特征描述及驗證[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]. 計算機研究與發(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] 楊威, 肖旭生, 李鄧鋒, 等. 移動應用安全解析學: 成果與挑戰(zhàn)[J]. 信息安全學報, 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 惡意應用檢測[J]. 通信學報, 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 應用惡意行為檢測系統(tǒng)[J]. 計算機學報, 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]. 通信學報, 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

國家自然科學基金資助項目（No.U1536204, No.61672394, No.61373169, No.61672393）；國家高技術(shù)研究發(fā)展計劃（“863”計劃）基金資助項目（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-），男，安徽安慶人，武漢大學博士生，主要研究方向為Android安全與隱私、系統(tǒng)安全等。

王麗娜（1964-），女，遼寧營口人，博士，武漢大學教授、博士生導師，主要研究方向為系統(tǒng)安全、網(wǎng)絡(luò)安全、信息隱藏等。

唐奔宵（1991-），男，湖北黃石人，武漢大學博士生，主要研究方向為移動安全與隱私、系統(tǒng)安全等。

趙磊（1985-），男，山東菏澤人，博士，武漢大學副教授、碩士生導師，主要研究方向為軟件安全、系統(tǒng)安全等。