潘偉

【摘要】 由于Android平臺的開放性和普及性，其上的應用開發(fā)日益增多。但由于有Android系統(tǒng)及開發(fā)工具是開源的，所有有些個人和企業(yè)利用反向工程工具對他人開發(fā)的應用進行破解修改，作為自己的產(chǎn)品進行發(fā)布銷售。這種行為嚴重侵害了原作者的利益。應用商城的運營者為了保證自己運營的產(chǎn)品是正版產(chǎn)品，必須花費大量人力進行測試比對。而本文提出了通過提取Android程序包中函數(shù)調(diào)用關(guān)鍵字，并使用文本余弦相似度算法進行盜版應用自動檢測的方法。并基于此方法對Android反盜版系統(tǒng)的基礎(chǔ)構(gòu)架進行了設(shè)計。

【關(guān)鍵詞】 余弦相似度 Android應用 版權(quán)保護 反向工程

一、引言

Android操作系統(tǒng)是由谷歌公司推出的基于Linux開源的嵌入式操作系統(tǒng)，當前它主要運用于手機等移動設(shè)備上。從2008年推出第一款基于Android的手機以來，在短短的5年里，它已超過了原有的塞班系統(tǒng)占領(lǐng)了手機市場份額第一的位置。截止2013年9月全世界采用這款系統(tǒng)的設(shè)備數(shù)量已經(jīng)達到10億臺[1]。

Android系統(tǒng)之所以能這樣受到廣大用戶和開發(fā)者的青睞，主要原因在于其開放的系統(tǒng)和易于上手的應用開發(fā)平臺，大大降低了第三方廠商進入Android應用開發(fā)的門檻。正是由于Android平臺和應用開發(fā)技術(shù)相對透明，有些公司和個人為了其自身利益，剽竊他人應用，進行反向工程，替換小部分代碼、圖片文字，改頭換面作為自己的產(chǎn)品推向市場。這種行為嚴重擾亂了Android應用市場，從長遠來說將影響整個產(chǎn)業(yè)鏈的健康發(fā)展。尤其對于“手機應用商店”的運營方，應該擔負起平臺推廣和銷售的應用產(chǎn)品監(jiān)督和管控的職能，避免侵權(quán)的應用在平臺運營。當前，“手機應用商店”的運營方多是以書面版權(quán)文檔審核，人工評測的方式進行版權(quán)及內(nèi)容審查。這種方式費時費力，而且存在人員主觀因素。因此，需要一種由計算機輔助的應用程序包自動版權(quán)檢測工具。

二、Android應用盜版手段分析

要反Android應用盜版侵權(quán)，就要了解常用的應用盜版手段。作為Android應用盜版者最容易獲得的是已編譯好可執(zhí)行的Android應用程序包。這個包里包括了已編譯的執(zhí)行代碼、本地庫文件、圖片和字符串資源、相關(guān)應用的配置文件等。應用盜版者通過使用反向工程工具把APK包解開，轉(zhuǎn)化為可直接編輯修改的資源文件、配置文件、smali代碼和動態(tài)鏈接庫文件[2]。最容易的應用盜版方法，就是直接修改圖片和字符串資源，這樣可以快速地完成對外觀的修改，使其從用戶界面上完全不同于原應用。還有一些技術(shù)較高的修改者會對配置文件和smali代碼進行修改，改變應用執(zhí)行的順序，跳過一些公司信息、版本信息、聯(lián)網(wǎng)激活等代碼，并植入一些自己的代碼，使得應用運行時的行為與原應用有較大差異。但不論何種手段，是對于一個應用盜版者，沒有源代碼，從成本考慮一般不能對程序運行邏輯進行大的調(diào)整，函數(shù)調(diào)用關(guān)系基本保持與原應用一致。如果對應用程序的片段引用，而程序的主體框架結(jié)構(gòu)都是自創(chuàng)，則不應該歸類為抄襲和盜版的一類。

通過對盜版者的修改行為分析，被盜版的Android 應用和新應用雖然在界面，圖片，文字，甚至用戶體驗流程上可能有很大差異，但是盜版者從節(jié)約成本的經(jīng)濟利益角度考慮，不會對晦澀難懂的字節(jié)碼程序作大的修改。這就為進行自動代碼分析，提取代碼特征進行比對，最終為確定Android應用相似度奠定了基礎(chǔ)。

三、文本余弦相似度概念和運用

文本余弦相似度，是基于一段文字中各關(guān)鍵字的詞頻乘以它的權(quán)重而組成的向量來表示一個文本的特征，而每個文本都可以通過統(tǒng)計獲取到它的特征向量，而兩文本的相似度就是由它們特征向量在空間中的夾角余弦值來表示的。文本的余弦相似度在0到1間變化。如果0代表兩特征向量成直角正交，兩篇文本中沒有任何相同的關(guān)鍵詞，可以認為兩篇文本沒有抄襲的嫌疑。如果1代表特征向量重合，兩篇文本具有完全相同的關(guān)鍵詞，而且出現(xiàn)的頻率完全相同，可以認為兩篇文本有高度抄襲的嫌疑[3]。

要完整理解文本余弦相似度算法，必須先了解詞頻和逆向文件頻率TF-IDF的概念。TF-IDF是一種用于資訊檢索與文本挖掘的常用加權(quán)技術(shù)。詞頻TF表示詞條t在文檔d中出現(xiàn)的頻率。逆向文件頻率IDF表示詞條t在文檔庫中的稀有程度[4]。IDF越大，則說明詞條t具有很好的類別區(qū)分能力。

四、Android應用相似度比較算法設(shè)計

正如前文分析的，作為Android應用最難以修改的部分是程序邏輯。如何從程序包中提取出程序邏輯呢？一個常用的Android程序包反向工程工具Apktool是最好的選擇。在運行帶反編譯參數(shù)的Apktool命令行后，會生成Davlik虛擬機語言（Android的Java虛擬機）表述的程序文件（smali目錄）。它是類似于匯編語言的低級語言，只要做簡單的匯編就能轉(zhuǎn)化為虛擬機可執(zhí)行字節(jié)碼[5]。正是由于此種特性，也就決定了其語法和格式的嚴謹性，語義上無二義性，可以作為比較Android應用相似性的基礎(chǔ)文本。

首先，提取出反編譯后代碼中所有函數(shù)調(diào)用行，并通過空格把語句分成獨立的詞?？梢苑纸鉃椴僮鞣?、參數(shù)、被調(diào)用的函數(shù)。而其中操作符和參數(shù)都是頻繁出現(xiàn)在每個應用中，不能表示特定應用的特征，應該把其歸入到終止統(tǒng)計的詞中，避免干擾特征向量的有用關(guān)鍵詞信息。這樣就只有被調(diào)用的函數(shù)被納入關(guān)鍵詞TD-IDF向量，這個關(guān)鍵詞包括函數(shù)的類名、函數(shù)名、參數(shù)類型列表、返回值類型，是函數(shù)的最基本特征，是最不容易被篡改的內(nèi)容。這樣就可以對于在一個應用中出現(xiàn)的所有被調(diào)用函數(shù)關(guān)鍵詞進行詞頻統(tǒng)計。

得到詞頻TF后，還有一個關(guān)鍵參數(shù)IDF（逆向文件頻率）。這需要對所有可以收集到的應用程序建立應用反編譯庫（必須要有足夠數(shù)量，這對于專門進行應用商城運營的機構(gòu)是相對容易的），提取出每個應用中被調(diào)用的函數(shù)。并以函數(shù)為查詢索引，統(tǒng)計包含這個函數(shù)調(diào)用的應用個數(shù)。知道了應用反編譯庫的總應用個數(shù)和包含這個函數(shù)調(diào)用的應用個數(shù)，就能根據(jù)IDF公式計算出某個函數(shù)調(diào)用的IDF值。如果這個函數(shù)調(diào)用出現(xiàn)的應用越少，這個函數(shù)調(diào)就越能表現(xiàn)出當前應用與其他應用的區(qū)別，IDF值就越大，此函數(shù)調(diào)用在該應用中的特征向量的權(quán)重就越大。

有了一個應用中每個函數(shù)調(diào)用的TF和IDF，就能得到這個應用程序特征向量。每個應用都有這樣一個特征向量，這樣就可以把需要檢測的應用的特征向量和應用庫中的每個應用的特征向量進行組合計算余弦相似度。在得到相似度的值后，可以和設(shè)定相似度閥值比對，比如超過95%的就設(shè)為高度可疑。這樣原本無方向大范圍的人工比對過程，改進為人工對高度可疑的盜版應用的比對，提高了處理效率。對于每個被確定為正版應用的Android包，最后被添加到大的應用庫中，為未來其他應用分析提供更精確地IDF和更豐富的特征向量。

五、Android應用反盜版系統(tǒng)設(shè)計

Android應用相似度比較的算法只是反盜版系統(tǒng)設(shè)計的核心，在系統(tǒng)實現(xiàn)時必須考慮到在成本和效率。因為為應用的數(shù)量是十分龐大的，而且每個應用中的函數(shù)少則數(shù)百，多則數(shù)千。在系統(tǒng)設(shè)計是要考慮如何低成本的存儲這些數(shù)據(jù)非結(jié)構(gòu)化的離散數(shù)據(jù)。顯然關(guān)系型數(shù)據(jù)庫對于這類數(shù)據(jù)存儲是低效和高成本的?？梢钥紤]針對大數(shù)據(jù)和文本處理設(shè)計的Nosql數(shù)據(jù)庫，比如開源的HBASE，可以有效降低成本，平滑擴展。在運算能力上，由于應用庫中每個應用都要和被檢測應用進行相似度比較，而且運算涉及向量運算，運算量較大。考慮到縮短處理時間和提升用戶感知，可以使用多服務(wù)器并行算法，例如Map-reduce算法，把計算任務(wù)平攤到多臺廉價服務(wù)器上，避免采購高價的高性能、多CPU的小型機[6]。最終的相似度計算結(jié)果可以保存到關(guān)系數(shù)據(jù)庫中，用戶可以通過多種索引便捷查詢，或以圖形化報表展示。

六、結(jié)語

關(guān)于如何打擊Android應用盜版是維護產(chǎn)業(yè)健康發(fā)展的關(guān)鍵問題。這個問題需要從法律、管理和技術(shù)多個層面共同解決。而作為應用商店運營者是有義務(wù)對其推廣的應用進行必要的過濾和審核，避免盜版應用上線銷售。在本文中使用了文本余弦相似度算法，通過對應用中的函數(shù)調(diào)用特征進行比較，發(fā)現(xiàn)高度相似的應用，為后續(xù)人工比對提供了方向和指導。這種方法簡單易用，實現(xiàn)成本不高，能起到輔助判斷作用。當然對于盜版者而言可能會有針對此方法故意加入一些無用的代碼段，干擾計算結(jié)果。因此，此方法還可以進行改進，比如過濾掉不被調(diào)用的函數(shù)和代碼段，再進行分析?？偠灾?，盜版和反盜版總是不斷魔高一尺，道高一丈的過程。反盜版的方法需要針對盜版方式的變化不斷提升演進。