楊佳，付才，韓蘭勝，魯宏偉，劉京亮

（1.華中科技大學(xué)計(jì)算機(jī)學(xué)院，湖北 武漢 430074；2.北京航空精密機(jī)械研究所，北京 100876)

1 引言

近年來，隨著移動(dòng)智能終端設(shè)備的迅速發(fā)展，Android 應(yīng)用占據(jù)了移動(dòng)應(yīng)用市場(chǎng)的主要份額。據(jù)統(tǒng)計(jì)，2017 年已有超過15.5 億部智能手機(jī)被使用，其中超過80%的手機(jī)搭載了Android 系統(tǒng)。海量規(guī)模的各類移動(dòng)應(yīng)用（App）投放在多個(gè)第三方應(yīng)用市場(chǎng)供用戶下載，例如谷歌應(yīng)用市場(chǎng)中Android 應(yīng)用數(shù)量已經(jīng)接近140 萬。這些移動(dòng)應(yīng)用已在辦公、娛樂等各個(gè)方面深入人們的生活，成為不可或缺的一部分。

然而，由于Android 系統(tǒng)的開放性和Android 應(yīng)用的易被破解性，許多非法開發(fā)者利用克隆技術(shù)或者反編譯工具仿造出大量的克隆App。目前，應(yīng)用重打包已經(jīng)成為惡意軟件傳播的主要途徑之一。目前，有超過85%的安卓應(yīng)用存在重打包行為，這不僅侵害了原開發(fā)者的知識(shí)版權(quán)和利益，也對(duì)移動(dòng)用戶的安全和隱私造成危害。此外，一些攻擊者會(huì)修改原始App中的函數(shù)邏輯，如去除App 中的支付函數(shù)、修改原App 中的廣告庫，甚至插入各種各樣的惡意代碼，再用一個(gè)新的簽名重新打包這些惡意App?？寺pp在第三方應(yīng)用市場(chǎng)中大量地被下載使用，嚴(yán)重干擾了應(yīng)用市場(chǎng)的正常環(huán)境。為保護(hù)合法用戶和原創(chuàng)開發(fā)者的正當(dāng)權(quán)益，如何實(shí)現(xiàn)高效準(zhǔn)確的App 克隆檢測(cè)是當(dāng)前移動(dòng)應(yīng)用市場(chǎng)面臨的技術(shù)挑戰(zhàn)。

由于App 市場(chǎng)的規(guī)模龐大，App 的數(shù)量不斷快速增長(zhǎng)，僅基于本地的計(jì)算資源進(jìn)行App 克隆檢測(cè)會(huì)因?yàn)橛布渲幂^低而出現(xiàn)計(jì)算能力有限、電源功耗過高等問題，本地檢測(cè)技術(shù)已不能滿足百萬數(shù)量級(jí)的App 分析需求。移動(dòng)互聯(lián)網(wǎng)中的云計(jì)算、大數(shù)據(jù)及虛擬化技術(shù)為解決大規(guī)模App 克隆檢測(cè)問題提供了技術(shù)支撐。本文基于云環(huán)境提出了一種高效App 克隆檢測(cè)方法，構(gòu)建了檢測(cè)原型系統(tǒng)，提高了App 克隆檢測(cè)的效率，能有效應(yīng)對(duì)大規(guī)模App 克隆檢測(cè)挑戰(zhàn)。

許多研究者提出了多種App 克隆檢測(cè)技術(shù)，主要有以下三類：基于簡(jiǎn)單散列特征提取的技術(shù)[1]、基于靜態(tài)語義特征提取的技術(shù)[2-6]、更加復(fù)雜有效的基于Android 應(yīng)用UI 結(jié)構(gòu)特征的提取技術(shù)[7-10]。第三類檢測(cè)技術(shù)中基于UI 結(jié)構(gòu)特征的檢測(cè)方法主要分析用戶接口之間的使用相似度進(jìn)而判斷App是否克隆。目前，Androguard[11]和FSquaDRA[12]是用于App 克隆檢測(cè)的主要公用工具。Androguard 能夠在Dalvik 字節(jié)碼層進(jìn)行比較，F(xiàn)SquaDRA 能夠基于源文件進(jìn)行相似度分析。然而這些研究還存在以下問題：基于散列值和某一特定靜態(tài)語義分析方案的適應(yīng)性還需增強(qiáng)，例如，在克隆中使用代碼混淆可避免被基于靜態(tài)語義特征的方法檢測(cè)出來；而UI 結(jié)構(gòu)特征提取方案需要提取整個(gè)App 的UI 調(diào)用結(jié)構(gòu)，同時(shí)需要復(fù)雜的圖匹配計(jì)算來比較App 相似度，因此對(duì)于小結(jié)構(gòu)UI 圖的App 難以達(dá)到較好的檢測(cè)效果。

本文主要從以下3 個(gè)方面來討論目前的工作。

1)二進(jìn)制層函數(shù)克隆檢測(cè)方案

在二進(jìn)制層的克隆檢測(cè)方案中，一種通用的方法是使用基于函數(shù)執(zhí)行序列的路徑進(jìn)行代碼相似度檢測(cè)。這種方法能夠檢測(cè)控制流程圖（CFG,control flow graph）的變化，但是不能準(zhǔn)確地檢測(cè)在不同平臺(tái)或者代碼混淆下的函數(shù)克隆。另一種方法是利用代碼的靜態(tài)特征進(jìn)行App 克隆檢測(cè)。但當(dāng)惡意開發(fā)者對(duì)這些靜態(tài)特征進(jìn)行修改的時(shí)候，例如修改字段變量的常數(shù)或API Call 的調(diào)用序列等，這種方法的正確率就無法得到保障。Rendezvous[13]在二進(jìn)制代碼上使用代碼搜索的辦法進(jìn)行克隆檢測(cè)，這種方法有2 個(gè)限制：首先，需要代碼的ngram 特征來提高準(zhǔn)確率；其次，需要將整個(gè)CFG 分為幾個(gè)子圖來處理。Pewny 等[14]提出了一種基于已知的漏洞簽名的搜索方案，該方案計(jì)算二進(jìn)制代碼塊的語義散列來進(jìn)行函數(shù)的克隆比較，然而這種方案并不高效。Feng 等[15]提出了基于控制流程圖的惡意代碼檢測(cè)方案，但是需要復(fù)雜的圖匹配過程。

2)App 克隆檢測(cè)

傳統(tǒng)方法檢測(cè)惡意App 主要通過權(quán)重很大的靜態(tài)和動(dòng)態(tài)特征來進(jìn)行黑白名單檢測(cè)，但是不能檢測(cè)未知的惡意代碼，如果之前并沒有收錄這種惡意代碼，則無法進(jìn)行檢測(cè)。例如，Zhou[16]利用軟件權(quán)限、API 調(diào)用順序等靜態(tài)特征進(jìn)行檢測(cè)，但是僅利用這些靜態(tài)特征進(jìn)行檢測(cè)會(huì)導(dǎo)致較低的準(zhǔn)確率。David[17]能夠自動(dòng)劃分一個(gè)函數(shù)調(diào)用圖的社區(qū)結(jié)構(gòu)，這些劃分的社區(qū)結(jié)構(gòu)能夠用于新的惡意代碼檢測(cè)。Arp 等[18]提出一種新的輕量級(jí)的檢測(cè)方案，這種方案從安卓應(yīng)用中提取八類特征，然后對(duì)這些特征用SVM 進(jìn)行分類實(shí)現(xiàn)檢測(cè)[3]。

3)動(dòng)態(tài)檢測(cè)

該檢測(cè)方式需要App 在一個(gè)虛擬的環(huán)境下運(yùn)行，從動(dòng)態(tài)特征中提取信息。Andrubis[19]即是動(dòng)態(tài)地進(jìn)行檢測(cè)，但是耗時(shí)過長(zhǎng)。Enck[20]提出了一個(gè)系統(tǒng)Taintdroid，通過追蹤敏感信息的流動(dòng)來進(jìn)行克隆行為的檢測(cè)，這種方法同樣非常耗時(shí)，在效率上有所欠缺，無法應(yīng)對(duì)大規(guī)模的檢測(cè)。

實(shí)現(xiàn)云環(huán)境下高效的函數(shù)層App 克隆檢測(cè)方案存在以下一些困難和挑戰(zhàn)。

1)相比面向源代碼的克隆分析，移動(dòng)應(yīng)用App中基于可執(zhí)行字節(jié)碼的克隆分析更為復(fù)雜。移動(dòng)應(yīng)用的源碼并不能輕易獲取，同時(shí)，Android 應(yīng)用中大量使用的代碼混淆技術(shù)也給重打包檢測(cè)增加了難度。

2)海量的應(yīng)用規(guī)模為克隆檢測(cè)效率提出了更高的要求。隨著各類Android 應(yīng)用的普及，App應(yīng)用數(shù)量呈現(xiàn)出飛速增長(zhǎng)的趨勢(shì)，通過App 的UI 調(diào)用圖或者動(dòng)態(tài)分析等方法都無法應(yīng)對(duì)大規(guī)模級(jí)別的克隆分析。

3)移動(dòng)應(yīng)用中第三方庫函數(shù)的大量使用干擾了克隆檢測(cè)的效率與準(zhǔn)確率。只有App 自身核心函數(shù)代碼來源于其他應(yīng)用才能認(rèn)定是克隆App，之前的工作僅通過黑白名單過濾第三方庫函數(shù)，在正確性和效率方面存在很大的問題。

4)系統(tǒng)需要具備良好的可擴(kuò)展性。在有新應(yīng)用添加到云端時(shí)，既要快速分析判斷，又要將新應(yīng)用特征快速融合到整體克隆特征庫中，實(shí)現(xiàn)增量特征更新。如果需要和之前的App 克隆檢測(cè)數(shù)據(jù)庫同時(shí)學(xué)習(xí)與提煉，其應(yīng)用效率會(huì)受到影響。

針對(duì)上述問題，本文面向云環(huán)境提出了一種基于函數(shù)編碼的App 克隆檢測(cè)方法，并實(shí)現(xiàn)了該方法的原型系統(tǒng)，稱為Pentagon。該方法在App字節(jié)碼層面對(duì)函數(shù)的控制流程圖與基本代碼塊進(jìn)行特征編碼，從函數(shù)層面比較2 個(gè)App 之間的相似度。所有的特征提取過程和檢測(cè)算法均在云環(huán)境下構(gòu)建和實(shí)施。本文主要貢獻(xiàn)如下。

1)設(shè)計(jì)了根據(jù)App 字節(jié)碼提取函數(shù)基本代碼塊特征的方法。每個(gè)執(zhí)行函數(shù)由多個(gè)基本代碼塊通過跳轉(zhuǎn)連接組成，首先針對(duì)每個(gè)執(zhí)行函數(shù)提取原始CFG，然后提取每個(gè)CFG 圖形節(jié)點(diǎn)的特征，即基本代碼塊特征，這些特征值表示了該代碼塊的靜態(tài)統(tǒng)計(jì)特征以及該代碼在CFG 中調(diào)用跳轉(zhuǎn)結(jié)構(gòu)特征。

2)提出了融合代碼塊特征和函數(shù)CFG 特征的編碼算法。該編碼算法將App 中任一函數(shù)編碼成幾個(gè)關(guān)鍵值的特征向量，提取的函數(shù)CFG 有向圖特征空間被壓縮成低維的數(shù)字特征空間；然后，基于該特征空間使用高效的聚類方法過濾第三方庫函數(shù)；同時(shí)，證明了算法中函數(shù)特征編碼的單調(diào)性，一個(gè)特征編碼僅代表一個(gè)函數(shù)。

3)解決了規(guī)模化App 增量更新的問題。Pentagon對(duì)App 中每個(gè)函數(shù)進(jìn)行獨(dú)立編碼，對(duì)于新增加的應(yīng)用程序，Pentagon 可單獨(dú)編碼該App 中所有函數(shù)特征，然后在數(shù)據(jù)庫中對(duì)App 進(jìn)行搜索比較，避免了同時(shí)整體提煉所有App 特征值的復(fù)雜過程。

4)從第三方應(yīng)用市場(chǎng)收集了超過152 789個(gè)應(yīng)用程序，對(duì)原型系統(tǒng)進(jìn)行了大規(guī)模的實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)結(jié)果表明本文方法的預(yù)處理效率和克隆檢測(cè)效率是目前典型App 克隆方案的8～100 倍。在1 000 個(gè)函數(shù)中一個(gè)克隆函數(shù)的平均搜索時(shí)間為7.9 ×10-9s。同時(shí)，App 克隆檢測(cè)的正確率達(dá)到97.6%。

2 問題描述和方案總覽

本節(jié)首先說明設(shè)計(jì)移動(dòng)應(yīng)用App 克隆檢測(cè)系統(tǒng)需要解決的問題，然后介紹本文提出的面向云環(huán)境下的App 克隆檢測(cè)方案。

2.1 問題描述

本文需要解決的關(guān)鍵問題是在云環(huán)境下如何快速判斷一個(gè)未知App 是否為克隆App，并判斷克隆App 中具體哪些函數(shù)是相似的及其相似度大小。判斷App 是否克隆，需要滿足以下條件。1)不同的開發(fā)源有相同的App 功能函數(shù)。通過查看 Android 應(yīng)用的簽名密鑰和App 中所有函數(shù)的特征來判斷該App 是否為克隆。如果這些不同簽名的App具有相似或相同的核心函數(shù)特征，則說明是克隆App。2)相似的函數(shù)不能包括第三方庫函數(shù)。App的代碼中一般包含了許多相同的第三方庫函數(shù)，這些庫函數(shù)不能作為判斷克隆的依據(jù)，克隆檢測(cè)方案需要過濾這些第三方庫函數(shù)。

檢測(cè)App 是否克隆的基本步驟如下。從非結(jié)構(gòu)化的App 字節(jié)碼中提取CFG 特征，然后將每個(gè)含有基本代碼塊特征信息的CFG編碼為一個(gè)低維數(shù)字特征，該特征向量表示App 中的函數(shù)特征。通過不同App中所有的函數(shù)特征匹配來實(shí)現(xiàn)App 函數(shù)層的克隆檢測(cè)。App 克隆檢測(cè)問題數(shù)學(xué)描述如下。

問題1如何設(shè)計(jì)一個(gè)函數(shù)f計(jì)算每個(gè)App 函數(shù)的編碼特征。通過App 中所有函數(shù)的編碼特征獲得App 的矩陣表示，即其中，表示整個(gè)函數(shù)的編碼特征向量，j=1,2,…,m，也是矩陣A中第j列列向量；m表示App中函數(shù)的個(gè)數(shù)。在函數(shù)f中，表示CFG 中基本代碼塊i的特征，|v|表示一個(gè)CFG 中代碼塊的個(gè)數(shù)。

問題2如何設(shè)計(jì)一個(gè)有效的過濾函數(shù)F以去除App 中第三方庫函數(shù)。這是提高App 克隆檢測(cè)正確率的重點(diǎn)問題，由于App 克隆檢測(cè)需要比較所有的代碼塊特征，如果不同App 中有大量相同的第三方庫函數(shù)，一方面會(huì)增加克隆檢測(cè)時(shí)間，另一方面會(huì)干擾克隆檢測(cè)的準(zhǔn)確率，相同的第三方庫函數(shù)不能作為克隆的檢測(cè)依據(jù)。

2.2 方案總覽

本節(jié)主要介紹函數(shù)層的特征編碼方案，并說明本文方案如何解決第2.1 節(jié)中提出的問題。本文的App 克隆檢測(cè)方案的基本思想是：首先，提取App反編譯smali 文件中每個(gè)函數(shù)的CFG；然后，針對(duì)每個(gè)CFG 中的每個(gè)基本代碼塊提取關(guān)鍵特征值，并根據(jù)編碼算法將所有的基本代碼塊特征和CFG 跳轉(zhuǎn)結(jié)構(gòu)編碼為低維的向量表示，將該向量存儲(chǔ)到App 特征數(shù)據(jù)庫中；最后，用余弦相似度計(jì)算2 個(gè)函數(shù)特征之間的向量距離，通過該距離判斷App 是否克隆。

如圖1 所示，Pentagon 有以下3 個(gè)檢測(cè)步驟。1)CFG 提取云環(huán)境，包括安卓市場(chǎng)下載App、反編譯和CFG 提取過程。2）函數(shù)特征生成及過濾云環(huán)境，主要為Pentagon 編碼過程，Pentagon 編碼的函數(shù)特征用來進(jìn)行第三方庫函數(shù)過濾。3）云環(huán)境下App 克隆檢測(cè)，主要為特征向量相似度比較。每一個(gè)步驟都在云環(huán)境下實(shí)現(xiàn)，具體實(shí)現(xiàn)過程為：首先編寫自動(dòng)下載App 的爬蟲引擎，將下載的App 存儲(chǔ)到對(duì)應(yīng)的服務(wù)區(qū)中；然后通過并發(fā)方式對(duì)每個(gè)下載的App 進(jìn)行CFG 提取以及函數(shù)特征編碼；結(jié)合云環(huán)境下內(nèi)存流計(jì)算方式并行地處理這些App，獲得App 中每個(gè)函數(shù)的低維數(shù)據(jù)表示，并將編碼特征存儲(chǔ)在云端的非結(jié)構(gòu)化數(shù)據(jù)庫中。

上述檢測(cè)步驟中，第一步，主要提取函數(shù)CFG中的基本代碼塊屬性。在Pentagon 中，CFG 的每一個(gè)節(jié)點(diǎn)提取5 個(gè)屬性值，這5 個(gè)屬性值分別表示字節(jié)碼特征和該基本代碼塊在CFG 中的拓?fù)浣Y(jié)構(gòu)。第二步，根據(jù)CFG 的拓?fù)浣Y(jié)構(gòu)，設(shè)計(jì)了一種基于圖形嵌入的編碼算法，將CFG 中的所有節(jié)點(diǎn)特征編碼為一個(gè)單調(diào)的低維數(shù)字特征，并通過反證法證明其單調(diào)性；使用函數(shù)編碼特征進(jìn)一步過濾第三方庫函數(shù)，在過濾之前，先刪除每個(gè)App 中重復(fù)的函數(shù)，然后通過聚類算法刪除第三方庫函數(shù)。第三步，給定一個(gè)待檢測(cè)的App，使用局部敏感散列（LSH,local sensitive hash）搜索算法實(shí)現(xiàn)高效的函數(shù)特征匹配。由于函數(shù)特征是獨(dú)立編碼，不需要更新之前的App函數(shù)特征庫，只需在數(shù)據(jù)庫中增加新的App 特征。

3 Pentagon 函數(shù)編碼

本節(jié)重點(diǎn)描述Pentagon 函數(shù)特征編碼算法，該算法將App 中每個(gè)函數(shù)編碼為一個(gè)一維向量，該一維向量能夠單調(diào)表示App 中的函數(shù)特征。

3.1 原始CFG 提取

Android 應(yīng)用一般是由開發(fā)者將所有的源碼和資源打包成APK (Android package)文件，然后發(fā)布供用戶下載。APK 文件是一個(gè)壓縮包，解壓縮之后的文件夾內(nèi)主要包含該應(yīng)用的Dalvik 字節(jié)碼、UI資源、UI 布局、配置文件、簽名信息等。其中，Dalvik 字節(jié)碼是App 的可執(zhí)行函數(shù)文件。Android應(yīng)用程序通常用Java 語言實(shí)現(xiàn)，然后被編譯成Dalvik 字節(jié)碼。

APK 文件本質(zhì)上是一個(gè)壓縮文件。反編譯的classes.dex 文件是App 主要的代碼文件，源代碼編譯成class 后，轉(zhuǎn)成jar，再壓縮成dex 文件。dex 文件是可以直接在Android 虛擬機(jī)上運(yùn)行的文件。smali語言是davlik 的寄存器語言，語法上和匯編語言相似，一個(gè)smali 文件中包含了很多函數(shù)，每個(gè)函數(shù)中包含了一系列的操作碼及該操作碼對(duì)應(yīng)的寄存器和處理數(shù)據(jù)。本方案首先對(duì)smali 文件提取CFG。CFG 中的每個(gè)節(jié)點(diǎn)代表函數(shù)中的一個(gè)代碼塊。CFG中跳轉(zhuǎn)結(jié)構(gòu)開始于一個(gè)代碼塊，結(jié)束于另一個(gè)代碼塊，有向邊表示控制流程圖的跳轉(zhuǎn)結(jié)構(gòu)。

3.2 函數(shù)特征編碼

編碼函數(shù)特征的主要思想是從App 的smali 文件的字節(jié)碼中提取一個(gè)帶有代碼塊特征的CFG，并將該特征CFG 投影編碼為一個(gè)包含5 個(gè)屬性值的低維向量特征。與函數(shù)代碼塊的其他特征（如I/O特征和其他語義特征[16]）不同，CFG 能更加全面地匹配函數(shù)的執(zhí)行流程特征。CFG 中的邊表示基本代碼塊之間的調(diào)用關(guān)系，CFG 中的每個(gè)代碼塊包含了一系列的操作碼和數(shù)據(jù)。本文基于圖形嵌入的思想來編碼帶有代碼塊信息的 CFG 結(jié)構(gòu)。Pentagon 融合了CFG 拓?fù)浣Y(jié)構(gòu)和基本代碼塊的靜態(tài)特征綜合完成函數(shù)特征編碼。圖2 表示CFG 的抽象圖，一個(gè)圓圈表示一個(gè)基本代碼塊，也是CFG圖中的一個(gè)節(jié)點(diǎn)，圓圈中的字母表示該基本代碼塊的序號(hào)，圓圈旁邊每一行表示一行dex 匯編代碼，其中包含了操作碼及使用的寄存器（v0～v4表示寄存器），圖中的箭頭表示2 個(gè)代碼塊跳轉(zhuǎn)的一條有向邊。

圖1 Pentagon 檢測(cè)步驟

圖2 CFG 抽象圖

定義CFG 為一個(gè)有向圖(V,E)，其中，V是一個(gè)函數(shù)的代碼塊集合，E?V×V是一系列代碼塊之間的連接邊。每個(gè)基本代碼塊的特征表示為一個(gè)一維向量。其中，si為代碼塊i在CFGj中的使用序列，pi為代碼塊i的操作碼的數(shù)目，ai為調(diào)用不同的API Call 的個(gè)數(shù)，oi為代碼塊i的出度，l i為代碼塊的循環(huán)結(jié)構(gòu)的個(gè)數(shù)，并定義代碼塊i有唯一的權(quán)重ωi。根據(jù)提出的算法，使用權(quán)重ωi編碼所有的節(jié)點(diǎn)特征。具體的計(jì)算過程如式(1)所示。

其中，e(i,k)表示Gj中節(jié)點(diǎn)i到節(jié)點(diǎn)j之間的一條邊|V|表示節(jié)點(diǎn)數(shù)。計(jì)算結(jié)果是每個(gè)函數(shù)的特征，其中，c js、cjp、cja表示代碼塊的統(tǒng)計(jì)特征，cjo、cjl表示CFG 拓?fù)浣Y(jié)構(gòu)的跳轉(zhuǎn)結(jié)構(gòu)。

3.3 權(quán)重參數(shù)生成

Pentagon 的關(guān)鍵是計(jì)算每個(gè)節(jié)點(diǎn)i的權(quán)重ωi，ωi用于函數(shù)特征的融合編碼。為了得到每個(gè)節(jié)點(diǎn)的權(quán)重，首先定義帶有代碼塊特征的CFG 一級(jí)跳轉(zhuǎn)結(jié)構(gòu)和全局跳轉(zhuǎn)結(jié)構(gòu)[21-22]。

1)一級(jí)跳轉(zhuǎn)結(jié)構(gòu)。一級(jí)跳轉(zhuǎn)結(jié)構(gòu)L描述CFG中任意2 個(gè)節(jié)點(diǎn)之間的跳轉(zhuǎn)情況。

如果節(jié)點(diǎn)i和k之間至少有一條有向邊，則e(i,k)=1；否則e(i,k)=0。一級(jí)跳轉(zhuǎn)結(jié)構(gòu)對(duì)CFG 編碼非常重要，表示在函數(shù)代碼中CFG 結(jié)構(gòu)代碼塊的一級(jí)繼承和調(diào)用情況。

2)全局跳轉(zhuǎn)結(jié)構(gòu)。全局跳轉(zhuǎn)結(jié)構(gòu)N描述了節(jié)點(diǎn)與CFG 中的其他節(jié)點(diǎn)之間的一級(jí)跳轉(zhuǎn)情況。

其中，Nu表示節(jié)點(diǎn)u和CFG 圖中其他節(jié)點(diǎn)的一級(jí)跳轉(zhuǎn)，節(jié)點(diǎn)的總數(shù)為|V|。比較Nu和Nv之間的相似度，獲得節(jié)點(diǎn)u與節(jié)點(diǎn)v之間的全局跳轉(zhuǎn)N(u,v)。直觀來說，全局跳轉(zhuǎn)結(jié)構(gòu)表示如果2 個(gè)節(jié)點(diǎn)連接了更多相同的節(jié)點(diǎn)，則它們之間的聯(lián)系會(huì)更加緊密，這些設(shè)想在很多領(lǐng)域都被合理證明。

在CFG 的有向邊e(i,k)中，定義從節(jié)點(diǎn)i到節(jié)點(diǎn)k之間的跳轉(zhuǎn)概率為

其中，

經(jīng)驗(yàn)概率表示節(jié)點(diǎn)i和k在圖CFG 的實(shí)際跳轉(zhuǎn)概率。為了計(jì)算權(quán)重參數(shù)，本文將跳轉(zhuǎn)概率分布和經(jīng)驗(yàn)概率分布之間的距離函數(shù)作為目標(biāo)函數(shù)，通過計(jì)算2 個(gè)概率之間 KL（Kullback-Leibler）距離，得到損失函數(shù)O1。

全局跳轉(zhuǎn)結(jié)構(gòu)定義了代碼塊和CFG 中其他節(jié)點(diǎn)的連接情況，以及該代碼塊在CFG 中的上下文。本文定義全局跳轉(zhuǎn)結(jié)構(gòu)的連接概率為

其中，|V| 表示節(jié)點(diǎn)的個(gè)數(shù)。為了保留圖CFG 中的全局跳轉(zhuǎn)結(jié)構(gòu)，需要上下文條件概率分布接近于經(jīng)驗(yàn)概率分布，上下文經(jīng)驗(yàn)概率為

其中，oi表示節(jié)點(diǎn)i的出度。同樣根據(jù)KL 距離定義以下的損失函數(shù)。

Pentagon 在編碼函數(shù)之前，需要先計(jì)算每個(gè)節(jié)點(diǎn)的權(quán)重ωi。根據(jù)一級(jí)跳轉(zhuǎn)結(jié)構(gòu)和全局跳轉(zhuǎn)結(jié)構(gòu)獲得的損失函數(shù)O1和O2，對(duì)CFG 中的所有邊進(jìn)行取樣，然后對(duì)目標(biāo)函數(shù)進(jìn)行求導(dǎo)，如式(3)所示。

由于損失函數(shù)是凸函數(shù)[19]，當(dāng)式(3)中導(dǎo)數(shù)為0時(shí)，可得到損失函數(shù)的最小值。令其一階導(dǎo)數(shù)趨近于0，求得所有的權(quán)重參數(shù)ωi。然后，使用權(quán)重序列Ω={ω1,ω2,…,ω n}編碼整個(gè)CFG 獲得函數(shù)的特征。

3.4 Pentagon 的單調(diào)性

由Ω編碼 CFG 結(jié)構(gòu)計(jì)算的函數(shù)特征為。編碼過程需要確保每個(gè)特征向量能唯一表示一個(gè)函數(shù)特征。

函數(shù)特征由?組成的一系列的線性等式函數(shù)計(jì)算而得。由于不同的CFG 有不同的跳轉(zhuǎn)結(jié)構(gòu)，所以當(dāng)?不同時(shí)，即有不同的線性等式，可以使用反證法來證明單調(diào)性。假設(shè)不同的CFG 有相同的特征，即對(duì)于CGFi和CFGj考慮到節(jié)點(diǎn)個(gè)數(shù)不同其?也不同，本文使用反證法，假設(shè)2 個(gè)CFG的節(jié)點(diǎn)個(gè)數(shù)相同，根據(jù)和式(1)，得到式(4)。

其中，n表示CFGi和CFGj的節(jié)點(diǎn)的個(gè)數(shù)，ωik表示CFGi中的節(jié)點(diǎn)k的權(quán)重。由于式(2)中，sigmoid 是單調(diào)函數(shù)，并且當(dāng)2 個(gè)CFG 的結(jié)構(gòu)不同時(shí)，這2個(gè)CFG 的實(shí)際邊分布概率也不相同，即pi≠pj，p是單調(diào)函數(shù)，則對(duì)任意k，CFGi和CFGj中每個(gè)節(jié)點(diǎn)的權(quán)重ωik≠ωjk。當(dāng)節(jié)點(diǎn)的數(shù)目相同時(shí)，節(jié)點(diǎn)的序列集是相同的，但是每一對(duì)有相同的調(diào)用序列的函數(shù)對(duì)都有不同的權(quán)重參數(shù)序列，并且由于CFG的結(jié)構(gòu)不同，即oik≠ojk且lik≠ljk，因此，式(4)不成立。

通過上述反證法，證明了不同的CFG 能編碼為不同的特征，Pentagon 編碼的函數(shù)是單調(diào)的。證畢。

3.5 CFG 編碼舉例

根據(jù)圖2 提取的原始CFG，以下用i，j表示該CFG 中基本代碼塊的編號(hào)，首先根據(jù)一級(jí)跳轉(zhuǎn)結(jié)構(gòu)和全局跳轉(zhuǎn)結(jié)構(gòu)計(jì)算權(quán)重參數(shù)，具體的計(jì)算過程如下。

考慮到kω iωj?1，令

并且CFG 結(jié)構(gòu)中最后一個(gè)出口節(jié)點(diǎn)的權(quán)重ω5=0，然后對(duì)導(dǎo)數(shù)兩邊同時(shí)取對(duì)數(shù)，有以下的等式。

最后，得到權(quán)重參數(shù)為Ω=[1,2,3,1,0]，計(jì)算函數(shù)的特征如下

3.6 基于函數(shù)編碼特征的App 表示

一個(gè)完整App的smali文件中包含了很多函數(shù)，每個(gè)函數(shù)被編碼成一維向量特征根據(jù)App 中所有函數(shù)的編碼特征，獲取每個(gè)App 的矩陣表示A，對(duì)于不同大小的App，所包含函數(shù)的個(gè)數(shù)m不同，由于App 中會(huì)有重復(fù)函數(shù)，重復(fù)函數(shù)的字符串特征和CFG 拓?fù)浣Y(jié)構(gòu)相同，重復(fù)的函數(shù)編碼表現(xiàn)為矩陣A中有相同的列。

大量的重復(fù)函數(shù)需要重復(fù)比對(duì)，降低了效率和正確率。根據(jù)統(tǒng)計(jì)調(diào)研，App 所包含的函數(shù)個(gè)數(shù)集中在2 000～20 000，實(shí)驗(yàn)的預(yù)處理過程首先要?jiǎng)h除重復(fù)的函數(shù)。使用python 庫的numpy 包中的“unique()"函數(shù)來刪除每個(gè)App 矩陣中的重復(fù)函數(shù)。最后App 的矩陣表示為

4 Pentagon 的第三方庫函數(shù)過濾

App 的代碼中一般包含了許多相同的第三方庫函數(shù)，這些相同函數(shù)不能作為克隆依據(jù)，克隆檢測(cè)方案需要過濾這些第三方庫函數(shù)。本節(jié)描述如何根據(jù)聚類算法刪除第三方庫函數(shù)。

假設(shè)App 數(shù)據(jù)庫足夠大，并且第三方庫函數(shù)在許多App 中都被使用。由于編碼之后的函數(shù)特征能夠單調(diào)表示App 中的函數(shù)，這些函數(shù)特征可用于過濾第三方庫函數(shù)。為了提高效率和準(zhǔn)確度，本文主要通過兩大步驟來過濾第三方庫函數(shù)：第一步根據(jù)每個(gè)函數(shù)特征對(duì)應(yīng)的平均權(quán)重參數(shù)進(jìn)行粗粒度過濾；第二步在第一步的基礎(chǔ)上，進(jìn)行嚴(yán)格比對(duì)聚類。具體如下。

第一步，統(tǒng)計(jì)所有函數(shù)中相同ω出現(xiàn)的頻率，使帶有相同的ω的函數(shù)特征聚集在同一類中，第三方庫函數(shù)會(huì)被聚集到一個(gè)遠(yuǎn)遠(yuǎn)大于其他類別的類中，計(jì)算所有不同ω的類中的函數(shù)個(gè)數(shù)，選取其中聚類函數(shù)個(gè)數(shù)在前60%的聚類作為下一步需要比較的對(duì)象。第二步，實(shí)施嚴(yán)格比對(duì)，只有當(dāng)2 個(gè)函數(shù)向量特征完全對(duì)應(yīng)相同時(shí)，才會(huì)重新將這些函數(shù)放置到同一類別中，最后將聚類中函數(shù)數(shù)目較多的一些函數(shù)作為第三方庫函數(shù)，刪除每個(gè)App 表示矩陣中包含這些第三方庫函數(shù)的特征，剩下的就是App 核心功能的函數(shù)。

5 Pentagon 克隆決策

Pentagon 系統(tǒng)克隆決策由2 個(gè)層面的相似度比較功能構(gòu)成，首先是函數(shù)級(jí)別的特征相似度比較，其次是App 之間的相似度比較。

5.1 函數(shù)特征相似度比較

本系統(tǒng)使用余弦相似度函數(shù)進(jìn)行相似度計(jì)算，每個(gè)函數(shù)特征向量有5 個(gè)值。任意2 個(gè)函數(shù)的特征向量的相似度定義如下

其中，δf表示函數(shù)之間差異度閾值。如果2個(gè)函數(shù)相同，則Sf=1。

根據(jù)Pentagon 的函數(shù)特征編碼過程，如果修改了原始執(zhí)行代碼塊中操作碼的一小部分，函數(shù)特征的編碼結(jié)果不會(huì)更改過多；如果改變某一個(gè)代碼塊中操作碼的執(zhí)行順序，同樣也不會(huì)過多地改變函數(shù)特征；但如果整個(gè)CFG 的跳轉(zhuǎn)結(jié)構(gòu)發(fā)生了大量的變化，或者代碼塊的統(tǒng)計(jì)特征改變了很多，對(duì)函數(shù)特征就會(huì)產(chǎn)生相應(yīng)的影響。

5.2 App 相似度比較

函數(shù)層相似度比較用于檢測(cè)相似的App，但是相似的App 不一定是克隆的App。有以下2 種情況不屬于App 克隆。1)2 個(gè)App 中，一個(gè)App 相比另一個(gè)App 有超過某一固定數(shù)目的不同的核心函數(shù)。2)App 來自相同的作者，僅是不同的版本。

首先，比較2 個(gè)App 中函數(shù)的個(gè)數(shù)。Appa和Appa′中包含的函數(shù)個(gè)數(shù)分別為|c|和|c′| 。如果

則判定這2 個(gè)App 不是克隆的。其中，σ是任意2個(gè)App 的函數(shù)數(shù)目比例常數(shù)，具體根據(jù)實(shí)驗(yàn)App中的函數(shù)數(shù)目決定，。

其次，需要通過使用函數(shù)層的相似度來比較App 的相似度，具體計(jì)算式如下

設(shè)定δa是App 相似度閾值，如果S a＞δa，這2個(gè)App 定義為克隆App。

6 性能測(cè)試與分析

本文實(shí)驗(yàn)分為以下3 個(gè)主要部分：App 中所有函數(shù)CFG 特征提取、函數(shù)編碼、App 克隆檢測(cè)。在準(zhǔn)備階段，使用Python 語言編寫爬蟲程序，該程序自動(dòng)在6 個(gè)Android 市場(chǎng)中下載App。然后，使用Androgurad 工具，將App 文件反編譯為smali 文件。根據(jù)smali文件提取每個(gè)函數(shù)的CFG，使用Pentagon對(duì)每個(gè)函數(shù)的CFG 進(jìn)行特征編碼。由于函數(shù)間的編碼互不影響，Pentagon 能夠并行編碼每個(gè)App 中的函數(shù)。在克隆檢測(cè)部分，比較2 個(gè)待檢測(cè)的App中的所有函數(shù)，來確定這2 個(gè)App 是否為克隆App以及其中具體的克隆函數(shù)。

本文提出的原型系統(tǒng)在Linux 平臺(tái)實(shí)現(xiàn)，并且添加了對(duì)OS X 平臺(tái)的支持。在應(yīng)用程序預(yù)處理模塊，使用了3 個(gè)開源工具Androguard、Keytool、Dex2jar。Androgurad 工具用來反編譯App 產(chǎn)生原始CFG，Keytool 用來提取應(yīng)用程序的簽名信息，Dex2jar 用來將得到的Dalvik 字節(jié)碼文件反編譯成JAR 包。通過編寫腳本，將這些工具組合成一個(gè)自動(dòng)化的工具鏈，可以批量對(duì)應(yīng)用程序進(jìn)行預(yù)處理。Pentagon 特征提取和相似度分析主要用Python 來實(shí)現(xiàn)。App 樣本庫的特征提取后保存在云端文件系統(tǒng)中，所有應(yīng)用的預(yù)處理和特征提取只需要進(jìn)行一次。

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

本文共進(jìn)行了2 個(gè)階段的實(shí)驗(yàn)，第一階段是小規(guī)模實(shí)驗(yàn)，用來驗(yàn)證第三方庫函數(shù)過濾的效率及本文方法的準(zhǔn)確性；第二階段是大規(guī)模實(shí)驗(yàn)，用來測(cè)試系統(tǒng)的可擴(kuò)展性和性能。實(shí)驗(yàn)數(shù)據(jù)集包含以下幾個(gè)數(shù)據(jù)庫：游戲App 數(shù)據(jù)庫、社交App 數(shù)據(jù)庫、娛樂App數(shù)據(jù)庫、金融數(shù)據(jù)庫和其他數(shù)據(jù)庫。在這5 個(gè)數(shù)據(jù)庫中共下載了152 789 個(gè)應(yīng)用程序，其中，包含的函數(shù)個(gè)數(shù)為7 490 721 877 個(gè)。數(shù)據(jù)庫1 中函數(shù)個(gè)數(shù)為1 596 096 888 個(gè)，數(shù)據(jù)庫2 中函數(shù)個(gè)數(shù)為1 142 135 436 個(gè)，數(shù)據(jù)庫3 中函數(shù)個(gè)數(shù)為2 151 246 841個(gè)，數(shù)據(jù)庫4 中函數(shù)個(gè)數(shù)為1 120 121 321 個(gè)，數(shù)據(jù)庫5 中函數(shù)個(gè)數(shù)為1 481 121 391 個(gè)。

測(cè)試數(shù)據(jù)包含兩部分。一部分是從網(wǎng)絡(luò)中下載的克隆App，從知名的Android 第三方應(yīng)用市場(chǎng)以及各種Android 論壇下載有可能是重打包的應(yīng)用（通過名字、描述來判斷，如破解版、修改版等），并且從其他官方市場(chǎng)尋找可能對(duì)應(yīng)的原版應(yīng)用。另一部分是通過人工重打包應(yīng)用獲取的克隆App。對(duì)下載的合法應(yīng)用進(jìn)行一些簡(jiǎn)單修改（更改變量和函數(shù)名、添加刪除代碼和第三方庫等），最后將修改后的應(yīng)用重新簽名并且打包。本文選取大小在 50 KB 到 68 MB 之間的App 做實(shí)驗(yàn)，這個(gè)區(qū)間的App 大小基本能代表Android 市場(chǎng)中一般應(yīng)用程序的大小。在實(shí)驗(yàn)之后手動(dòng)安裝和檢查應(yīng)用代碼來驗(yàn)證結(jié)果的準(zhǔn)確性。實(shí)驗(yàn)運(yùn)行在12 核 1.6 GHz 的Linux 服務(wù)器，內(nèi)存為16 GB，硬盤為7 TB，同時(shí)開啟4 個(gè)線程并行處理。

6.2 實(shí)驗(yàn)比較

在函數(shù)層的克隆分析方面，本文在準(zhǔn)確率和效率上對(duì)比目前一種較好的基于函數(shù)層的App 克隆檢測(cè)方法：基于CFG 質(zhì)心運(yùn)算提取特征的App 克隆檢測(cè)方案Centroid[23]。在App 克隆檢測(cè)層面，本文對(duì)比當(dāng)前較好的工作：FSquaDRA[12]、Wukong[24]、Centroid[23]。

6.3 重復(fù)函數(shù)刪除

圖3 表示刪除重復(fù)函數(shù)前不同函數(shù)數(shù)目的App出現(xiàn)的次數(shù)，也就是對(duì)應(yīng)于某一具體函數(shù)數(shù)目App的個(gè)數(shù)，橫坐標(biāo)表示每個(gè)App 中函數(shù)的數(shù)目，縱坐標(biāo)表示這一函數(shù)數(shù)目的App 的出現(xiàn)頻率。圖4 表示刪除重復(fù)函數(shù)之后不同函數(shù)數(shù)目的App 出現(xiàn)的次數(shù)?？梢钥闯鲈谡麄€(gè)樣本中函數(shù)的個(gè)數(shù)下降了17.07%～67.27%。某些App 中，重復(fù)函數(shù)的個(gè)數(shù)超過了一半，一些大的App 中包含了更多的重復(fù)函數(shù)?？梢钥闯?，重復(fù)函數(shù)的個(gè)數(shù)和App 的大小呈現(xiàn)下降的趨勢(shì)。一些只含有20 個(gè)函數(shù)的App 中基本沒有重復(fù)函數(shù)。刪除一個(gè)含有17 863 個(gè)函數(shù)的App中的重復(fù)函數(shù)的平均時(shí)間少于1 s。

圖3 刪除前的函數(shù)分布

圖4 刪除后的函數(shù)分布

6.4 第三方庫函數(shù)過濾

本節(jié)實(shí)驗(yàn)對(duì)數(shù)據(jù)集中所有App 編碼的函數(shù)特征進(jìn)行聚類，用于第三方庫函數(shù)的過濾，前文說明了不同的權(quán)重代表不同的函數(shù)，即如果則i和j表示2 個(gè)不同的函數(shù)，首先，計(jì)算所有不同的權(quán)重的出現(xiàn)次數(shù)。圖5 中分別展示了所有ω值對(duì)應(yīng)的所有函數(shù)特征的函數(shù)數(shù)目分布，以及所有ω值對(duì)應(yīng)的不同的函數(shù)特征的函數(shù)數(shù)目的分布。比如，同一個(gè)ω可能出現(xiàn)多個(gè)函數(shù)特征，即有ω的函數(shù)特征可能相同也可能不同，因此要區(qū)分同一個(gè)權(quán)重ω對(duì)應(yīng)的函數(shù)特征是否相同。圖5 橫坐標(biāo)表示出現(xiàn)的所有ω的值，縱坐標(biāo)表示權(quán)重為該ω的函數(shù)數(shù)目，也就是函數(shù)的出現(xiàn)頻率。從圖中可以看出，出現(xiàn)頻率較高的函數(shù)數(shù)目的權(quán)重ω為1～103。然后選擇權(quán)重ω為1～103對(duì)應(yīng)的函數(shù)特征作為第三方庫函數(shù)的特征。其次，在相同ω的聚類中嚴(yán)格比較函數(shù)特征，選取聚類中函數(shù)各數(shù)較大的類作為第三方庫函數(shù)，并查看這些函數(shù)特征對(duì)應(yīng)的函數(shù)名和函數(shù)可執(zhí)行代碼。實(shí)驗(yàn)顯示函數(shù)個(gè)數(shù)在前十的聚類都是安卓支持庫，或者廣告支持庫，這些都不在白名單中。為了刪除第三方庫函數(shù)，在聚類之后需要求得聚類大小的閾值作為下一步聚類的條件。

圖5 不同權(quán)重中所有的函數(shù)和不同的函數(shù)的數(shù)目分布

本實(shí)驗(yàn)使用2 種方法來決定第三方庫函數(shù)的過濾閾值。首先，下載300 個(gè)App，這些App 中包含超過14 個(gè)不同的已經(jīng)確定的第三方庫。手動(dòng)反編譯這些App，對(duì)相應(yīng)的函數(shù)進(jìn)行標(biāo)記，在最后的檢測(cè)結(jié)果中，將出現(xiàn)的頻率數(shù)目的前29.02%的聚類作為第三方庫函數(shù)進(jìn)行過濾。其次，將所有數(shù)據(jù)庫的App 的函數(shù)特征進(jìn)行聚類，選擇大小在前29.02%的聚類，手動(dòng)檢測(cè)這些類別的函數(shù)特征對(duì)應(yīng)的函數(shù)，標(biāo)記為“第三方庫函數(shù)”“關(guān)鍵代碼”或者“不能確定”。根據(jù)這些標(biāo)記判斷聚類閾值選擇的準(zhǔn)確性。

結(jié)合上述的2 種方法，最終選擇聚類大小的數(shù)目為1 610，如果相同函數(shù)特征的聚類數(shù)目超過了1 610，則判定為第三方庫函數(shù)。過濾了第三方庫函數(shù)后，整個(gè)App 數(shù)據(jù)庫中的函數(shù)數(shù)目下降了79.26%。過濾前，有超過63.60%的App 中包含的函數(shù)數(shù)目在504～5 973 之間，平均每個(gè)App 有2 259個(gè)函數(shù)；過濾后，大部分的App 包含的函數(shù)數(shù)目為84～1 976，平均每個(gè)App 只有627 個(gè)函數(shù)，超過249、419、203 個(gè)函數(shù)被過濾。

6.5 準(zhǔn)確率

為了表示App 函數(shù)檢測(cè)的正確率，用以下2 個(gè)參數(shù)來評(píng)估實(shí)驗(yàn)的好壞，即TPR（true positive rate）和FPR（false positive rate），TPR 是在搜索問題中正確找到克隆函數(shù)的比例，F(xiàn)PR 表示找到的克隆匹配是不正確的匹配函數(shù)的比例，由TPR 和FPR 的數(shù)據(jù)組成的曲線為ROC 曲線。從測(cè)試數(shù)據(jù)庫隨機(jī)選取一些檢測(cè)樣本序列q，一個(gè)樣本實(shí)際上有m個(gè)克隆函數(shù)，在樣本函數(shù)數(shù)目L中，如果認(rèn)為前F個(gè)函數(shù)是檢測(cè)出來的克隆函數(shù)，實(shí)際上，F(xiàn)個(gè)函數(shù)中正確匹配的克隆函數(shù)有c個(gè)，剩下的L-c，就是誤報(bào)率。設(shè)當(dāng)F越大的時(shí)候，TPR 和FPR 都會(huì)逐漸變高，這兩者的相加值不為1。

由于本文是基于函數(shù)層編碼的App 克隆檢測(cè)方法，為了說明本文的準(zhǔn)確率，本文將和目前的函數(shù)克隆檢測(cè)的方案進(jìn)行比較，根據(jù)本文提供的測(cè)試集，將這些測(cè)試集的App 反編譯的函數(shù)編碼成一維特征后作為輸入，進(jìn)行App 克隆搜索檢測(cè)，同時(shí)與本文前面提到的方法進(jìn)行比較，圖6 表示數(shù)據(jù)庫中不同大小的App 對(duì)應(yīng)的數(shù)目。圖7 表示設(shè)置不同的函數(shù)向量差異閾值時(shí)，對(duì)應(yīng)的失敗率大小。從圖中可以看出，如果函數(shù)差異閾值小于0.005 7，則在函數(shù)層的檢測(cè)失敗率為2.4%。如果函數(shù)差異閾值大于0.02，則函數(shù)的錯(cuò)誤率大于20%。函數(shù)差異閾值越大，則FPR 越大。閾值需要確保相似的函數(shù)有相近的特征，由于Pentagon 編碼的特征是單調(diào)的，不同的函數(shù)之間的特征差異比較大，如果閾值被設(shè)置得過大，那么相似的函數(shù)就被認(rèn)為不同的函數(shù)，這樣就會(huì)增加FPR。

圖6 不同大小的 App 的總數(shù)

Pentagon 系統(tǒng)在當(dāng)前已經(jīng)投放市場(chǎng)正在使用的游戲App 中檢測(cè)發(fā)現(xiàn)了2 個(gè)克隆樣本（為了保護(hù)版權(quán)，本文不對(duì)這2 個(gè)App 樣本進(jìn)行具體說明）。這2 個(gè)App 在應(yīng)用市場(chǎng)都顯示為具有自主知識(shí)產(chǎn)權(quán)，但經(jīng)過本文系統(tǒng)檢測(cè)發(fā)現(xiàn)，它們之間存在克隆關(guān)系，并且通過動(dòng)態(tài)調(diào)試，也確認(rèn)了這2 個(gè)App 中存在克隆關(guān)系，表現(xiàn)出本文方案的實(shí)際應(yīng)用效果。

圖7 錯(cuò)誤率和閾值之間的關(guān)系

圖8 展示了實(shí)驗(yàn)結(jié)果的ROC 曲線，可以看到本文提出的 Pentagon 編碼方式的正確率高于Centroid 方案，取App 差異閾值為圖7 所示的約為0.01 時(shí)候，根據(jù)ROC 曲線可以看到檢測(cè)的準(zhǔn)確率可以達(dá)到97.6%。由于Pentagon 是單調(diào)的，而且對(duì)函數(shù)的信息編碼得更完整，不僅獲取了每個(gè)代碼塊的主要統(tǒng)計(jì)特征信息，還獲取了每個(gè)CFG 的結(jié)構(gòu)特征，所以Pentagon 的準(zhǔn)確率很高。Centroid 并不是嚴(yán)格單調(diào)地表示特征，相比較，本文提出的編碼方案能更正確地表示函數(shù)的特征。

圖8 ROC 曲線

6.6 函數(shù)層效率

本文主要從以下3 個(gè)方面對(duì)系統(tǒng)效率進(jìn)行比較：CFG 特征的提取效率；Pentagon 編碼時(shí)間；函數(shù)克隆檢測(cè)時(shí)間。這三方面指標(biāo)表示App 克隆檢測(cè)的預(yù)處理效率。本文有關(guān)效率的實(shí)驗(yàn)使用全部的152 789 個(gè)App，對(duì)所有的App 提取特征進(jìn)行存儲(chǔ)，并生成用于App 克隆檢測(cè)的數(shù)據(jù)庫。

1)CFG 特征提取時(shí)間。圖9 展示了Pentagon 的CFG提取時(shí)間。該特征提取時(shí)間不包含App生成CFG時(shí)間，因?yàn)镻entagon 的編碼只需要給CFG 的每個(gè)代碼塊提取5 個(gè)值，Centroid 給CFG 的每個(gè)代碼塊提取3 個(gè)值，但Centroid 在給CFG 中的基本代碼塊進(jìn)行編號(hào)的過程稍微復(fù)雜一些，所以需要更多的時(shí)間，但總體來說，2 種方案的CFG 特征提取時(shí)間相差不大。

圖9 每個(gè)函數(shù)的 CFG 中代碼塊的特征提取時(shí)間

2)Pentagon 編碼時(shí)間。圖10 展示了Pentagon生成時(shí)間隨著函數(shù)的數(shù)目增加而增長(zhǎng)。Pentagon 將APP中一個(gè)函數(shù)的CFG編碼為一個(gè)特征，Pentagon是一種線性計(jì)算的編碼，當(dāng)函數(shù)個(gè)數(shù)有20 000 個(gè)時(shí)，即使串行編碼，Pentagon 的編碼時(shí)間僅僅需要1 h。由于Pentagon 的編碼方式是解耦合的，因此利用并行的方式可以大大縮短編碼時(shí)間。

圖10 Pentagon 編碼時(shí)間

3)搜索時(shí)間。圖11 表示Pentagon 的編碼特征用于App 克隆檢測(cè)出的搜索時(shí)間，使用6 個(gè)不同度量的樣本大小來檢測(cè)搜索效率，這6 個(gè)文本中函數(shù)個(gè)數(shù)c為1 03～108，隨機(jī)選擇1 到10 000 個(gè)函數(shù)序列作為提交的搜索序列，平均搜索時(shí)間隨著函數(shù)數(shù)目的增加持續(xù)增長(zhǎng)，在1 000 個(gè)函數(shù)中平均的搜索時(shí)間為7.9 ×10-9s。

圖11 Pentagon 函數(shù)層的克隆搜索檢測(cè)時(shí)間

6.7 App 克隆檢測(cè)時(shí)間

當(dāng)獲取了所有的App 函數(shù)特征之后，先按照本文方案刪除第三方庫函數(shù)，每個(gè)App 大概需要0.01 s去除重復(fù)的函數(shù)，刪除了第三方庫函數(shù)之后，檢測(cè)一個(gè)App，需要比較檢測(cè)的App 和待檢測(cè)的App之間所有的函數(shù)，實(shí)驗(yàn)表明，本文方案計(jì)算2 個(gè)App 之間的相似值需要0.079 s。表1 比較了當(dāng)前幾個(gè)比較好的App 克隆檢測(cè)方案FSquaDRA[5]、Wukong[20]、Centroid[4]和本文方案之間的效率。

表1 App 克隆檢測(cè)效率

7 結(jié)束語

與現(xiàn)有的App 克隆檢測(cè)方案相比較，本系統(tǒng)具有以下2 個(gè)突出的優(yōu)勢(shì)。1）在對(duì)第三方庫函數(shù)過濾的方案中，不局限于已有的白名單進(jìn)行過濾，過濾更為精確有效?，F(xiàn)有方案使用白名單通過App 函數(shù)中的包名來過濾第三方庫函數(shù)，在準(zhǔn)確性上面存在問題，因?yàn)槭紫炔豢赡芡暾娴卮_定第三方庫函數(shù)，其次，混淆可能改變包函數(shù)的名字，使過濾方案失效，本文發(fā)現(xiàn)部分第三方庫函數(shù)沒有具體的名稱。 2）本文方案不僅考慮了基本代碼塊之間的靜態(tài)特征，同時(shí)也考慮了CFG 中代碼塊之間的跳轉(zhuǎn)結(jié)構(gòu)，現(xiàn)有的App 檢測(cè)方案主要考慮靜態(tài)特征，比如提取不同的API Call 調(diào)用順序來檢測(cè)克隆，這些特征同樣會(huì)因?yàn)榛煜?。本文的方法采用CFG 函數(shù)結(jié)構(gòu)編碼，并融合代碼塊屬性特征，相比較其他方案在克隆分析上可靠性更高，實(shí)驗(yàn)結(jié)果也驗(yàn)證了上述結(jié)論。

Pentagon 能夠快速應(yīng)用于云環(huán)境下大規(guī)模App函數(shù)層克隆檢測(cè)，實(shí)現(xiàn)了更準(zhǔn)確高效地查找克隆App 以及定位具體克隆函數(shù)的目標(biāo)，對(duì)維護(hù)移動(dòng)互聯(lián)網(wǎng)應(yīng)用知識(shí)產(chǎn)權(quán)的良好生態(tài)具有積極支撐意義。下一步將在特征自動(dòng)化提取、第三方函數(shù)庫優(yōu)化、跨平臺(tái)克隆檢測(cè)等方面做進(jìn)一步工作，以促進(jìn)Pentagon 系統(tǒng)應(yīng)用推廣。