黃思榮,陶非凡,張 源,楊 珉

1(復(fù)旦大學(xué) 軟件學(xué)院,上海 201203) 2(上海通用識別技術(shù)研究所,上海 201100)

1 引 言

近年來,智能移動設(shè)備在人們?nèi)粘Ｉ钪邪缪萘瞬豢苫蛉钡慕巧?其中,安卓是目前最受歡迎的手機(jī)操作系統(tǒng),截止至2017年3月,國內(nèi)安卓系統(tǒng)份額已暴漲至87.3%[注]https://www.kantarworldpanel.com/global/smartphone-os-market-share/,各類安卓應(yīng)用市場為用戶提供了大量功能豐富的應(yīng)用軟件.第三方庫(Third-party libraries)在安卓應(yīng)用程序中被廣泛使用,開發(fā)人員使用它們來構(gòu)建新功能、整合外部服務(wù)和減少發(fā)布應(yīng)用程序的時間,常見的諸如在應(yīng)用中加入廣告進(jìn)行盈利、將應(yīng)用與在線社交媒體進(jìn)行整合、引入單點登錄服務(wù)等.安卓開發(fā)人員可以從流行開源項目服務(wù)(如GitHub,BitBucket)或在線軟件包存儲庫(如Maven)上找到很多有用的第三方庫.此外,安卓集成開發(fā)環(huán)境(Android Integrated Development Environments,簡稱Android IDE)中大多內(nèi)嵌Maven/Gradle支持,極大方便了開發(fā)人員使用第三方庫.有時開發(fā)人員需要進(jìn)一步修改第三方庫使其更適用于當(dāng)前的安卓應(yīng)用,例如,調(diào)整一些UI部件的外觀等.這種情況下,開發(fā)者通常會從項目服務(wù)或在線軟件包存儲庫上下載第三方庫源碼,并直接對源碼進(jìn)行修改.

第三方庫的開發(fā)和使用為安卓應(yīng)用程序的開發(fā)帶來了很大的幫助,但是同樣也給用戶帶來了安全隱患和隱私泄露的風(fēng)險.2015年10月,淘米客SDK[注]http://thehackernews.com/2015/10/android-apps-steal-sms.html個被超過63,000個應(yīng)用使用的廣告庫,被曝光竊取用戶短信.此外,一些流行的第三方庫如百度SDK[注]http://thehackernews.com/2015/11/android-malware-backdoor.html、Facebook SD[注]http://thehackernews.com/2014/07/facebook-sdk-vulnerability-puts.html、Dropbox SDK[注]http://www.infoworld.com/article/2895016/mobile-technology/ibm-discloses-droppedin-vulnerability-for-dropboxs-android-sdk.html都曾被發(fā)現(xiàn)有嚴(yán)重的漏洞,能被攻擊者利用來控制受害者的設(shè)備、竊取敏感信息并注入惡意負(fù)載代碼(malicious payload).然而,現(xiàn)有的應(yīng)用程序安全分析工作(比如隱私泄露分析[10,11]、權(quán)限/風(fēng)險分析[12,13]、敏感API分析[14,15]、漏洞分析[16,17]等)通常把整個應(yīng)用作為單一主體,因此無法準(zhǔn)確檢測出惡意行為是來自于應(yīng)用代碼還是第三方庫代碼.此外,第三方庫的廣泛使用嚴(yán)重影響了應(yīng)用分析工具的有效性.例如,目前的應(yīng)用克隆檢測工具大多數(shù)通過比較應(yīng)用間的代碼相似度實現(xiàn),因此若兩個不同的應(yīng)用程序使用了大量相同的第三方庫,這些工具就會產(chǎn)生誤報.

應(yīng)用程序構(gòu)建的過程模糊了開發(fā)者編寫的代碼和第三方庫之間的邊界,同時開發(fā)者常使用混淆工具(如ProGuard)對字節(jié)碼進(jìn)行混淆,因此可靠有效的第三方庫檢測方法應(yīng)該對常見的混淆技術(shù)具有適應(yīng)性.現(xiàn)有的第三方庫檢測工作如依賴于流行第三方庫名單的簡單包名匹配、程序克隆檢測等,這些方法可靠性不夠,且無法應(yīng)對代碼混淆和包名沖突等情況.如何精確可靠地識別第三方庫成為一個有待解決的技術(shù)挑戰(zhàn).LibScout[1]雖然能應(yīng)對基本的混淆手段,但是它也存在一些問題:一是完全不考慮函數(shù)內(nèi)部的實現(xiàn),丟失大量代碼信息,容易造成誤匹配;二是LibScout中用到的參數(shù)閾值是根據(jù)人工經(jīng)驗確定,效果會受到較大的人為影響.這也是現(xiàn)有的第三方庫檢測方法常見的問題,即參數(shù)閾值往往通過有限的實驗或人工指定.如果在檢測工具中能實現(xiàn)對所有可能的參數(shù)閾值通過有限實驗進(jìn)行自整定,確定一組最佳的參數(shù)賦值用于最終的第三方庫檢測,閾值的設(shè)定將更加可靠有效.

針對上述問題,本文設(shè)計并實現(xiàn)了一個第三方庫檢測工具LibSeeker.它在LibScout函數(shù)簽名哈希的基礎(chǔ)上,加入函數(shù)特征向量對函數(shù)進(jìn)行匹配,補(bǔ)充缺失的代碼信息,降低函數(shù)誤匹配的概率.不同于LibScout以類為比較的基本單位,LibSeeker的匹配細(xì)化到函數(shù)層面,并根據(jù)下一層的匹配情況逐層確定類、包以及整個第三方庫是否匹配.同時,我們還實現(xiàn)了參數(shù)自整定功能,對LibSeeker中使用到的參數(shù)閾值進(jìn)行自動調(diào)整測試,通過實驗確定了最佳的參數(shù)組合.LibSeeker檢測第三方庫的準(zhǔn)確率與召回率在整定后的參數(shù)設(shè)定下能達(dá)到99.82%和95.77%,相比LibScout有大幅度的提升.

2 背景及挑戰(zhàn)

2.1 第三方庫檢測

本節(jié)主要介紹關(guān)于第三方庫檢測的現(xiàn)有研究工作,包括代碼克隆檢測、基于機(jī)器學(xué)習(xí)或代碼聚類的檢測、以及基于哈希特征文件的檢測等.

2.1.1 現(xiàn)有的檢測方法

針對第三方庫檢測的技術(shù),最簡單的就是通過第三方庫的包名白名單在應(yīng)用代碼中檢測第三方庫.但是當(dāng)應(yīng)用進(jìn)行一些簡單混淆(如標(biāo)識符重命名)后這個方法就會失效.

代碼克隆檢測(Clone Detection)技術(shù),本質(zhì)上就是檢測兩段代碼之間的相似程度.通常會基于代碼相似度進(jìn)行計算[2],或是通過從程序依賴圖(program dependency graphs)中提取語義特征[3]進(jìn)行分析,從而檢測出克隆應(yīng)用.

AdDetect[4]和PEDAL[5]使用機(jī)器學(xué)習(xí)來檢測第三方廣告庫.AdDetect使用分層包集群(hierarchical package clustering)來檢測應(yīng)用程序中的(非)主要模塊;而PEDAL則從第三方庫SDK中提取代碼特征并使用包之間的關(guān)系信息來訓(xùn)練分類器,從而在標(biāo)識符被混淆的情況下也能檢測出第三方庫.

AnDarwin[6]和WuKong[7]通過代碼聚類技術(shù)檢測第三方庫代碼.這種方法的前提假設(shè)是第三方庫被許多應(yīng)用普遍使用,且第三方庫代碼不會被修改.但因為在應(yīng)用程序構(gòu)建過程中常常自動或人工地消除死代碼(dead-code elimination),并且開發(fā)者自定義調(diào)整第三方庫的情況也很普遍,所以這個假設(shè)并不現(xiàn)實.LibRadar[8]擴(kuò)展了WuKong的聚類方法,并根據(jù)在聚類中不同包內(nèi)的API調(diào)用頻率為每個檢測到的聚類生成獨特的特征文件,實現(xiàn)對第三方庫的快速檢測.由于代碼聚類和特征提取都不是在原始第三方庫上進(jìn)行,對具有相同的根包(root package)的第三方庫容易產(chǎn)生誤報.

2.1.2 基于哈希特征文件的第三方庫檢測——LibScout

LibScout[1]為第三方庫構(gòu)建與代碼無關(guān)的特征文件,利用高層級的類組織信息來進(jìn)行特征文件匹配,檢測應(yīng)用是否包含給定的第三方庫.LibScout能夠應(yīng)對一些常見的混淆技術(shù),包括標(biāo)識符重命名、API隱藏、控制流隨機(jī)化以及字符串加密等.

LibScout的特征文件是基于層級結(jié)構(gòu)提取的.對于每個第三方庫,按函數(shù)、類、包、第三方庫(或應(yīng)用)這四個層級,由下自上生成哈希,形成一棵深度為3的默克爾樹(Merkle Tree).最底部的函數(shù)哈希使用精簡過的與代碼無關(guān)的函數(shù)簽名,往上每層的哈希值是對所有下一層子節(jié)點的哈希值進(jìn)行排序、然后再取哈希.匹配特征文件則是從上而下進(jìn)行的,先從包的哈希開始比較,當(dāng)包的哈希值不匹配時,再比較包下每個類的哈希值,并計算包的相似度,同時根據(jù)包名的結(jié)構(gòu)和根包對可能的匹配進(jìn)行篩選,最后挑選符合條件并且相似度最大的匹配對.

LibScout基于函數(shù)簽名哈希的匹配方法快速簡單,但是由于只提取了函數(shù)外殼信息,內(nèi)部的代碼都被忽略,而不同函數(shù)簽名沖突的概率較高,因此容易造成較大的誤匹配率.如圖1所示,第三方庫中的包X與應(yīng)用中的包Y都有兩個類,它們的內(nèi)部實現(xiàn)不同,但是由于忽略了函數(shù)內(nèi)部實現(xiàn)和自定義類型,包內(nèi)的兩個類提取出的函數(shù)簽名完全一樣,LibScout會錯誤地將類A、B分別與類C、D匹配,從而得到包X與包Y誤匹配的結(jié)果.同樣地,不同版本的第三方庫如果僅僅修改了函數(shù)內(nèi)的代碼,整體的層級結(jié)構(gòu)沒有變,那么最后得到的哈希特征文件也是一樣的,很可能會匹配到錯誤的第三方庫版本.因此,基于函數(shù)簽名哈希的方式在應(yīng)對混淆技術(shù)的同時,也給第三方庫檢測帶來了不準(zhǔn)確性.

圖1 LibScout誤匹配示意圖Fig.1 Mismatch of LibScout

2.2 參數(shù)自整定

參數(shù)自整定(parameter auto-tuning)本質(zhì)上是對所有的參數(shù)向量(parameter vector)進(jìn)行遍歷,從中挑選出在預(yù)先設(shè)定的衡量標(biāo)準(zhǔn)下最優(yōu)的參數(shù)向量.一個好的調(diào)優(yōu)算法(tuning algorithms)會用盡可能小的代價來嘗試找出一個足夠好的參數(shù)向量.目前的調(diào)優(yōu)算法主要從兩方面來降低總搜索量,一是減少需要進(jìn)行測試的參數(shù)向量數(shù)量,二是減少為每個參數(shù)向量創(chuàng)建的測試數(shù)量.本文中我們主要使用正交試驗和UCB算法來降低搜索量,并使用ROC曲線的AUC值來衡量每個參數(shù)向量的效果.

2.2.1 正交試驗

正交試驗設(shè)計(Orthogonal experimental design)根據(jù)正交性從全面試驗中挑選出部分有代表性的點進(jìn)行試驗,是研究多因素多水平試驗的一種設(shè)計方法.表1是一個三因素二水平的正交表,括號內(nèi)是某化工產(chǎn)品轉(zhuǎn)化率試驗的數(shù)據(jù),三個因素分別為溫度、時間和加堿量,每個因素都有兩種水平取值.如果按照全面實驗要求,需要23=8種參數(shù)組合的實驗;而按照L4(23)正交表安排實驗,則只需要進(jìn)行4種參數(shù)組合的實驗,大大減少了工作量.

表1 用于轉(zhuǎn)化率試驗的L4(23)正交表
Table 1 L4(23)used in conversion experiment

試驗號1(溫度)2(時間)3(加堿量)11(60°C)1(60min)1(5%)21(60°C)2(120min)2(7%)32(100°C)1(60min)2(7%)42(100°C)2(120min)1(5%)

正交表同樣簡化了試驗數(shù)據(jù)的計算分析,根據(jù)試驗結(jié)果可以挑選出這些試驗中最好的參數(shù)組合,同時可以推斷最優(yōu)的參數(shù)組合.對于同一個因素的每一水平取值,其他因素的每個水平分布是均勻的,因此,我們可以統(tǒng)計每列因素上各水平實驗效果的數(shù)據(jù)和,計算得到各水平數(shù)據(jù)的綜合平均值和各因素的變動平方和,分析出每個因素上各水平取值對實驗結(jié)果的影響趨勢,從而挑選出每個因素的最優(yōu)水平取值,進(jìn)一步猜測出最佳的參數(shù)組合.當(dāng)對參數(shù)粒度要求較高時,可以根據(jù)目前的結(jié)果進(jìn)一步細(xì)化各因素的水平值,重復(fù)進(jìn)行正交試驗,直到找到滿意的參數(shù)組合.

2.2.2 UCB算法

UCB(Upper Confidence Bound,置信區(qū)間上界)算法提供了一種多臂問題的選擇方式,根據(jù)每個臂被選所獲得的收益以及被試次數(shù),計算出每個臂的收益均值與試驗次數(shù)標(biāo)準(zhǔn)差之和,挑選值最大的作為下一個進(jìn)行試驗的臂,從而使獲得的收益最大化.

其他針對多臂選擇的算法如小量貪婪(epsilon-Greedy)算法和SOFTMAX算法等,容易受到臂回報隨機(jī)性的影響,當(dāng)初始遇上一次隨機(jī)壞的結(jié)果,這個臂之后被選中的概率會非常小,而這個臂的整體效果有可能并不差.UCB算法克服了這些缺點.它完全不使用隨機(jī)性,每一種情況下,UCB選擇的臂都是可以通過數(shù)據(jù)計算出來的;它不僅僅關(guān)注于收益,同樣會關(guān)注每個臂被試驗的次數(shù);且UCB算法沒有任何需要配置的參數(shù),不需要任何先驗條件.OpenTuner[9]中作者就采用了類似算法來降低搜索代價.

UCB算法對于參數(shù)自整定的意義,在于平衡了我們對不同參數(shù)向量的實驗次數(shù).對于效果很差的參數(shù)向量,我們在少量的測試后就能放棄,減少無意義的測試;而對于效果很好的參數(shù)向量,我們則不斷地對其進(jìn)行測試以保證它的好效果并非偶然.

2.2.3 ROC曲線與AUC值

ROC(Receiver Operating Characteristic)曲線和AUC(Area Under Curve)常被用來評價一個分類器的優(yōu)劣.ROC曲線是根據(jù)不同的分界值,以真陽性率(True Positive Rate,TPR)為縱坐標(biāo)、假陽性率(False Positive Rate,FPR)為橫坐標(biāo)繪制的曲線.其中,真陽性率和假陽性率的計算公式分別為TPR=TP/(TP+FN),FPR=FP/(FP+TN).圖2是一條ROC曲線,曲線上最靠近坐標(biāo)圖左上方的點D效果最好,敏感度和特異度均較高.實際實驗中可通過計算約登指數(shù)(Youden′s J statistic)求得這個最優(yōu)臨界點,約登指數(shù)大小為TPR與FPR之差,剛好就是ROC曲線上的點到y(tǒng)=x在垂直方向上的長度J.

圖2 ROC曲線和約登指數(shù)Fig.2 ROC and Youden′s J statistic

AUC被定義為ROC曲線下的面積.當(dāng)隨機(jī)挑選一個正樣本以及一個負(fù)樣本,當(dāng)前的分類算法根據(jù)計算得到的分值將這個正樣本排在負(fù)樣本前面的概率就是AUC值.AUC值越大,分類器效果更好.

比起其他的評價標(biāo)準(zhǔn),ROC和AUC不容易被樣本的不均衡性所影響.當(dāng)測試集中的正負(fù)樣本的分布變化的時候,ROC曲線能夠保持不變.在實際的數(shù)據(jù)集中經(jīng)常會出現(xiàn)類不平衡(class imbalance)現(xiàn)象,即負(fù)樣本比正樣本多很多(或者相反),而且測試數(shù)據(jù)中的正負(fù)樣本的分布也可能隨著時間變化,這種情況下使用ROC曲線衡量分類器比直接使用準(zhǔn)確率和召回率效果要穩(wěn)定得多.

2.3 存在的問題與挑戰(zhàn)

簡單的包名匹配當(dāng)遇上標(biāo)識符重命名等混淆機(jī)制就會失效,而應(yīng)用中第三方庫代碼常被修改又容易影響到基于代碼聚類的方式.LibScout雖然可以避免標(biāo)識符重命名和API隱藏等混淆技術(shù)的影響,并根據(jù)哈希特征文件檢測是否包含給定的第三方庫,但由于只是對模糊函數(shù)簽名取哈希,對函數(shù)內(nèi)部的代碼變動不敏感,在有助于應(yīng)對混淆的同時,也造成了較大的誤匹配率.

實現(xiàn)一個可靠高效的安卓應(yīng)用第三方庫檢測工具面臨以下幾個挑戰(zhàn):

一是在提高檢測準(zhǔn)確率的同時要保證一定的混淆適應(yīng)性.想要避免LibScout簡單哈希特征文件帶來的高誤報率,需要加入更多的關(guān)于函數(shù)代碼或結(jié)構(gòu)等的信息.但是,常見的混淆工具如Android Studio中自帶的ProGuard,有修改包名、類名和變量名,消除死代碼等混淆功能,開發(fā)者同樣可能對第三方庫進(jìn)行個性化定制,因此加入的信息需要在代碼被修改或刪除的情況下,對檢測第三方庫的結(jié)果有較小的影響.

二是在保證結(jié)果可靠性的同時確保增加的時間開銷是合理的.工具應(yīng)該要盡可能準(zhǔn)確地檢測應(yīng)用中包含的第三方庫,提高檢測的準(zhǔn)確率和召回率,但是這需要分析更多信息,消耗更多時間.然而,分析一個安卓應(yīng)用應(yīng)該在一定時間范圍內(nèi),特別是在實際使用中,工具需要對應(yīng)用商城中成千上萬的安卓應(yīng)用進(jìn)行分析,因此希望每個應(yīng)用需要的分析時間是在合理范圍內(nèi)的.所以第三方庫檢測工具在加入更多分析信息以提高準(zhǔn)確率的同時,也要確保帶來的額外時間開銷是能被接受的.

三是實現(xiàn)參數(shù)的自動調(diào)整.以往的分析工具對于一些參數(shù)閾值的指定,絕大多數(shù)是根據(jù)人工經(jīng)驗指定,或者是人為指定一些可能的值、通過有限的實驗確定里面效果最好的參數(shù).但是這樣的參數(shù)確定方式存在太大的人為因素,且不能在一定范圍內(nèi)遍歷所有參數(shù)組合.而直接遍歷所有可能的參數(shù)向量費時費力,尤其當(dāng)參數(shù)較多時,遍歷帶來的代價太大.因此,我們需要找到一種方式,在盡可能少的測試次數(shù)中,挑選出指定范圍內(nèi)最好的參數(shù)組合.

3 LibSeeker基本架構(gòu)

針對第三方庫檢測面臨的問題和挑戰(zhàn),本文設(shè)計并實現(xiàn)了一個能自動調(diào)整參數(shù)的第三方庫檢測工具LibSeeker.如圖3所示,LibSeeker主要由第三方庫檢測模塊和參數(shù)自整定模塊兩部分組成.

第三方庫檢測模塊.該模塊主要實現(xiàn)了檢測安卓應(yīng)用是否包含給定第三方庫的功能.首先為APK和第三方庫中的函數(shù)提取函數(shù)簽名哈希和特征向量centroid作為識別函數(shù)是否相似的特征,然后進(jìn)行第三方庫與APK之間的包匹配,通過類匹配程度和包之間的層級關(guān)系確定并篩選候選列表,列舉所有情況并計算出全局最大相似度,從而得到最終匹配結(jié)果及第三方庫相似度分值.

圖3 LibSeeker系統(tǒng)架構(gòu)圖Fig.3 System architecture of LibSeeker

參數(shù)自整定模塊.該模塊主要實現(xiàn)對第三方庫檢測中使用到的參數(shù)閾值進(jìn)行自整定的功能.根據(jù)預(yù)先設(shè)定的參數(shù)范圍與精度,使用正交表設(shè)計參數(shù)向量,利用UCB算法挑選下一組測試的參數(shù)向量,傳入第三方庫檢測模塊設(shè)置參數(shù)閾值對測試集進(jìn)行測試,統(tǒng)計結(jié)果并計算AUC值,回饋給UCB算法用以計算選出下一次進(jìn)行測試的參數(shù)向量,直到所有測試集測試完畢.分析統(tǒng)計結(jié)果從而得到不同參數(shù)對測試結(jié)果的影響趨勢并挑選或推斷出最佳的參數(shù)組合.

4 LibSeeker設(shè)計與實現(xiàn)

為了保證LibSeeker的快速有效,我們的實現(xiàn)基于LibScout使用的函數(shù)哈希,并結(jié)合函數(shù)特征向量centroid,匹配安卓應(yīng)用程序與第三方庫的類和包,計算應(yīng)用與該第三方庫的相似度分值,并輸出匹配結(jié)果.同時,我們還利用正交表和UCB算法,實現(xiàn)對參數(shù)閾值的自動優(yōu)化.

4.1 函數(shù)特征提取

本文中底層的函數(shù)匹配主要基于函數(shù)特征向量centroid以及函數(shù)簽名哈希.LibScout中函數(shù)匹配主要基于與代碼無關(guān)的函數(shù)簽名哈希,這類特征的優(yōu)點是快速簡單、節(jié)省時間,但是忽略了代碼信息會帶來一定的誤差.復(fù)雜函數(shù)若只使用僅保留簽名外殼的哈希值匹配,丟失的信息太多,容易造成誤匹配,因此需要使用特征向量輔助匹配.通過分析大量應(yīng)用并提取它們的特征向量,我們發(fā)現(xiàn)很多簡單函數(shù)如get或set函數(shù),提取出的特征向量完全一樣,且在應(yīng)用程序中這類函數(shù)數(shù)量眾多,特征函數(shù)的提取對于簡單函數(shù)的匹配基本上沒有太大幫助.因此,為了節(jié)省比較時間,在本文的實現(xiàn)中,簡單函數(shù)直接使用簽名哈希進(jìn)行匹配,而復(fù)雜函數(shù)則在此基礎(chǔ)上增加了函數(shù)特征向量的匹配.

4.1.1 函數(shù)簽名哈希

本文采用與LibScout相同的函數(shù)哈希.我們要提取與代碼無關(guān)的函數(shù)簽名,首先為每個函數(shù)提取原始簽名,原始簽名由函數(shù)名,參數(shù)列表和返回值類型三部分組成,例如com.fudan.A.test(android.app.Activity,boolean,com.fudan.B)com.fudan.A,其中函數(shù)名com.fudan.A.test和參數(shù)與返回值中出現(xiàn)的自定義類型com.fudan.B、com.fudan.A都可能被混淆工具混淆,因此我們?nèi)サ袅撕瘮?shù)名,并用一個統(tǒng)一的標(biāo)識符X取代出現(xiàn)的自定義類型,而基本類型如boolean以及安卓系統(tǒng)定義的類android.app.Activity則不會被混淆,所以保留下來,最后我們得到的與代碼無關(guān)的函數(shù)簽名為(android.app.Activity,boolean,X)X.我們用MD5算法對這些簽名取哈希值并保存下來,以供后續(xù)第三方庫匹配中使用.

不同于LibScout逐層向上取哈希并將類的哈希值作為比較的基本單位,我們在匹配函數(shù)時還需要加入復(fù)雜函數(shù)特征向量的比較,因此對于類和包我們不采用排序取哈希的方式,而是在之后匹配過程中通過計算匹配成功的函數(shù)比例來判斷類與包是否匹配.

4.1.2 函數(shù)特征向量

我們需要為復(fù)雜函數(shù)提取函數(shù)特征向量centroid.首先根據(jù)函數(shù)中基本塊(basic block)數(shù)量和指令(instruction)數(shù)量判斷函數(shù)是否為需要提取centroid的復(fù)雜函數(shù).因為基本塊多代表函數(shù)內(nèi)部實現(xiàn)出現(xiàn)的循環(huán)和判斷語句較多,邏輯復(fù)雜,而指令數(shù)量則比較直觀地反映了函數(shù)代碼的長度.在本文的實現(xiàn)中,當(dāng)基本塊數(shù)量大于2或指令數(shù)量不少于10時,我們認(rèn)為這個函數(shù)時一個復(fù)雜函數(shù).

最后,我們通過計算兩個函數(shù)centroid之間的差異度來判斷這兩個函數(shù)是否相似.對于centroid向量的8個坐標(biāo)維度,分別計算每個維度上的差異度,例如cx上的差異度為

而兩個特征向量centroid之間的差異度是取這8個維度上差異度的最大值.當(dāng)這個最大值小于我們預(yù)先設(shè)定的函數(shù)差異閾值METHOD_DIFFERENCE_THRESHOLD時,我們認(rèn)為這兩個函數(shù)相似.

4.2 應(yīng)用程序與第三方庫的匹配

不同于LibScout自頂向下地通過比較包哈希與類哈希進(jìn)行匹配,LibSeeker中安卓應(yīng)用與第三方庫的匹配過程是由底層逐層往上確定的,同時也結(jié)合包之間的層級關(guān)系進(jìn)行分析.我們根據(jù)函數(shù)的匹配情況確定類是否可能匹配,同樣也根據(jù)類的匹配情況確定第三方庫包的候選APK包列表.在匹配的過程中我們還要求對應(yīng)APK包和第三方庫包的層級關(guān)系保持一致,以此對候選者進(jìn)行篩選.最后從列舉的所有情況中,找出相似度最大的包匹配.

4.2.1 類之間的匹配

為了判斷一個給定的第三方庫類和應(yīng)用APK類是否匹配,我們循環(huán)遍歷了第三方庫類中每一個函數(shù),嘗試匹配APK類中還未匹配成功的函數(shù).對于每對嘗試進(jìn)行匹配的函數(shù)對,我們首先判斷該函數(shù)是否同為簡單函數(shù)或同為復(fù)雜函數(shù)(基本塊數(shù)量大于2或指令數(shù)量不少于10),當(dāng)它們同為簡單函數(shù)時,只要它們的哈希值相同,就認(rèn)為這兩個函數(shù)匹配成功;當(dāng)它們同為復(fù)雜函數(shù)時,除了哈希值相同,還要求MDD值小于METHOD_DIFFERENCE_THRESHOLD,才算匹配成功;否則匹配失敗.當(dāng)匹配成功的函數(shù)對數(shù)除以該第三方庫類中總函數(shù)個數(shù)所得的值不低于類匹配相似度閾值CLASS_MATCHED_THRESHOLD時,我們認(rèn)為這兩個類是匹配的.

4.2.2 包之間的匹配與相似度計算

當(dāng)檢測一個安卓應(yīng)用APK是否包含給定第三方庫時,我們要先為每個第三方庫包尋找所有可能的候選APK包.遍歷所有APK包,計算與當(dāng)前的第三方庫包之間的匹配程度,對第三方庫包中每個類,嘗試匹配APK包中尚未匹配成功的類,計算類匹配成功數(shù)量除以該第三方庫包中類的總數(shù),若該值不小于候選匹配包相似度閾值PACKAGE_CANDIDATE_THRESHOLD,則將當(dāng)前這個APK包加入該第三方庫包的候選列表中.

接著,根據(jù)包的層級篩選候選匹配列表.在APK包候選者中尋找包名和第三方庫包完全相同的候選包,將其放入成功匹配的第三方庫包-APK包列表中.每次新加入包匹配對時檢查與之前列表中已經(jīng)存在的包匹配對是否存在相鄰或父子關(guān)系,若存在這些關(guān)系,判斷它們匹配的APK包名與新加入的APK包名是否存在同樣的關(guān)系,如果關(guān)系不一致,就拋出匹配失敗的異常.對當(dāng)前已經(jīng)成功匹配的包對,提取第三方庫包的根包名(root package name),然后對還未匹配成功的第三方庫包的候選列表進(jìn)行過濾,若未匹配第三方庫包與已匹配第三方庫包擁有共同的根包,則它的候選APK包也一定是在對應(yīng)的根包下,否則就將其從候選者中刪除.

最后,根據(jù)已經(jīng)匹配成功的第三方庫包-APK包列表、待匹配第三方庫包的候選列表以及這些包名之間的相鄰或父子關(guān)系,枚舉所有可能的匹配情況,計算每種情況下第三方庫中匹配成功的類總數(shù)除以第三方庫所有包下的類總數(shù)的值,作為與第三方庫的相似值.取所有情況中全局相似度最大的值作為最終的第三方庫相似度,并輸出該情況下第三方庫與應(yīng)用中包的匹配情況.同時,我們通過設(shè)定第三方庫相似度閾值LIBRARY_SIMILARITY_THRESHOLD來進(jìn)行分類,輸出該應(yīng)用是否包含給定第三方庫的判斷結(jié)果.

4.3 閾值參數(shù)自整定

在上文特征提取和第三方庫匹配的實現(xiàn)中,有以下4個閾值會影響我們的第三方庫檢測工具的準(zhǔn)確性:

1)METHOD_DIFFERENCE_THRESHOLD(函數(shù)特征向量centroid差異度閾值,下文簡稱MDT);

2)CLASS_MATCHED_THRESHOLD(類匹配相似度閾值,下文簡稱CMT);

3)PACKAGE_CANDIDATE_THRESHOLD(候選匹配包相似度閾值,下文簡稱PCT);

4)LIBRARY_SIMILARITY_THRESHOLD(計算出的與第三方庫相似度閾值,下文簡稱LST).

我們根據(jù)正交表L25(56)設(shè)計25種參數(shù)向量,利用UCB算法減少參數(shù)優(yōu)化過程中的測試次數(shù),通過ROC曲線的AUC值衡量每種參數(shù)組合的效果,從而挑選出在一定精度下最優(yōu)的參數(shù)組合.由于采用AUC衡量實驗結(jié)果,當(dāng)把LibSeeker視為一個二元分類器時,LST就是分界值,所以可以在我們挑選出AUC最大的參數(shù)向量之后,再根據(jù)ROC曲線得到最優(yōu)分界閾值作為LST.因此,我們只需要對MDT、CMT和PCT這三個參數(shù)進(jìn)行參數(shù)自整定.

4.3.1 根據(jù)正交表設(shè)計參數(shù)向量

我們選擇六元素五水平正交表L25(56)來設(shè)計參數(shù)的實驗組合.取L25(56)前三列分別作為MDT、CMT和PCT對應(yīng)的因素,根據(jù)預(yù)先設(shè)置的參數(shù)范圍和精度,為每個參數(shù)分配5個實驗值,然后按照L25(56)中的25種水平組合,設(shè)計25個參數(shù)向量進(jìn)行實驗.

由于正交試驗設(shè)計的特性,對于每個參數(shù),在每種水平取值下,其他參數(shù)的水平取值分布是均勻的.因此,我們可以根據(jù)這25組實驗的結(jié)果,將各參數(shù)下每種取值的結(jié)果累加,獲得水平數(shù)據(jù)和,并計算水平平均值和極差,從而分析出該參數(shù)的取值對實驗結(jié)果的影響趨勢,縮小最優(yōu)取值的可能范圍.然后在縮小后的范圍內(nèi),重新為每個參數(shù)分配5個水平實驗值,重復(fù)實驗,直到最后各參數(shù)值之差符合要求的精度,即可分析挑選出最佳的參數(shù)向量.

4.3.2 計算AUC值

對于每個參數(shù)向量,我們將使用已知的安卓應(yīng)用與第三方庫測試集進(jìn)行測試,測試集事先標(biāo)注好該應(yīng)用是否包含列出的第三方庫.每次測試實驗后能得到一組數(shù)據(jù),即LibSeeker計算所得的第三方庫相似度分值和正負(fù)樣本的標(biāo)簽.

我們將獲得的實驗結(jié)果按照相似度分值從大到小排序,依次將每個數(shù)據(jù)點的相似度分值作為分界閾值,分值大于它的被判斷為正樣本,小于它的被判斷為負(fù)樣本,統(tǒng)計以該數(shù)據(jù)點為分界值情況下的true positive rate(TPR)和false positive rate(FPR),即可生成ROC曲線.

我們可以根據(jù)ROC曲線上的數(shù)據(jù)點來計算AUC值.具體地,每個數(shù)據(jù)點都記錄了大于當(dāng)前分界閾值的正樣本個數(shù)(即TP)和大于當(dāng)前分界閾值的負(fù)樣本個數(shù)(即FN).已知測試集中的正樣本總數(shù)和負(fù)樣本總數(shù),因此可以計算出每個數(shù)據(jù)點的TPR和FPR.因為AUC是ROC曲線下的面積,所以可以通過不斷累加求面積的方式計算AUC.將數(shù)據(jù)點列表按照TP和FP從小到大排序,如圖4所示,首先計算第一個數(shù)據(jù)點的TPR和FPR值,接著計算TPR與FPR乘積除以2的值,即為該點與原點連線上方的三角形區(qū)域(圖4中area區(qū)域)的面積,加入累加面積S中.之后循環(huán)遍歷每個數(shù)據(jù)點,計算上方增加的梯形面積x-y,并把它加入S中.其中,x等于當(dāng)前節(jié)點與前一個點的TPR之差乘以當(dāng)前FPR,y等于當(dāng)前節(jié)點與前一個點的TPR之差與FPR之差的乘積除以2.當(dāng)所有數(shù)據(jù)點遍歷結(jié)束后,就能獲得ROC曲線上方空間的總面積S,又因為整個空間面積為1.0,所以AUC可以由1.0減去S求得.

4.3.3 利用UCB算法進(jìn)行自整定測試

首先我們將所有已知正負(fù)的數(shù)據(jù)集均勻隨機(jī)地劃分為n個測試集合(n值遠(yuǎn)大于25),每個測試集中有一定數(shù)量的正樣本和負(fù)樣本,當(dāng)挑選一組參數(shù)向量對測試集進(jìn)行試驗后,我們能獲得該參數(shù)向量在這次實驗中計算得到的AUC值.

圖4 ROC曲線面積計算示意圖Fig.4 Area calculation of ROC

接著,我們利用UCB算法來為每個參數(shù)向量分配測試機(jī)會,對效果不好的參數(shù)向量盡早過濾,對效果很好的參數(shù)向量反復(fù)實驗從而獲得一個穩(wěn)定的結(jié)果.

我們把25個參數(shù)向量當(dāng)作多臂老虎機(jī)的臂,把AUC值作為拉動一個臂獲得的收益.對于第1個測試集,我們將所有參數(shù)向量都試驗了一次,獲得每個參數(shù)向量的初始AUC值.對于之后的第2至n個測試集,每次都要計算選擇權(quán)值C-score,挑選權(quán)值最大的參數(shù)向量進(jìn)行實驗.選擇權(quán)值的計算公式如下:

其中,t是目前測試的總次數(shù),Tj,t是該參數(shù)向量目前跑過的測試集數(shù)量,α是用以平衡AUC均值和次數(shù)附加值的一個常數(shù)因子.因為AUC值在0.5到1.0之間,而后面的試驗次數(shù)附加值大于1,因此需要通過乘以α來使得公式前后兩部分處于同一數(shù)量級下.在這種情況下UCB算法才能發(fā)揮較好的效果,既能給效果好的參數(shù)向量更多的測試機(jī)會,以期獲得相對穩(wěn)定的結(jié)果,避免因為偶然的高值導(dǎo)致的誤差,同時也能給予試驗次數(shù)少的參數(shù)向量被選中的機(jī)會,避免因為初始的低值就被排除在試驗之外.

當(dāng)所有測試集測試結(jié)束后,統(tǒng)計每個參數(shù)向量的測試次數(shù)和平均AUC值,分析向量的三個因素對結(jié)果的影響,根據(jù)實驗結(jié)果和實際的精度需要,繼續(xù)設(shè)計參數(shù)向量進(jìn)行實驗或結(jié)束測試返回最佳參數(shù)組合.具體實驗情況可見5.2節(jié).

4.3.4 最優(yōu)分界值LST的確定

當(dāng)MDT、CMT和PCT這三個參數(shù)通過參數(shù)自整定過程確定最優(yōu)組合后,我們得到最終LibSeeker檢測的ROC曲線.接著我們就可以通過計算約登指數(shù)來確定ROC曲線的最佳臨界點.約登指數(shù)計算公式如下:

約登指數(shù)=敏感度+特異度-1=TPR-FPR.

ROC曲線的縱坐標(biāo)TPR即為敏感度(sensitivity),而橫坐標(biāo)FPR等于1-特異度(1-specificity),所以約登指數(shù)最大的點就是TPR與FPR差值最大的點,也就是圖中最靠左上角的點,該點所取的臨界值即為最佳LST.具體實現(xiàn)只需要通過遍歷ROC曲線上所有數(shù)據(jù)點,計算它們的約登指數(shù)即可找出最佳分界點,從而得到該點所取的分界值LST,統(tǒng)計出準(zhǔn)確率和召回率.

5 實驗與分析

本部分中,我們將對LibSeeker工具的參數(shù)自整定模塊和第三方庫檢測模塊進(jìn)行實驗并評估效果.實驗環(huán)境為:具有40核心(Intel Xeon E7-4830,2.13Ghz),內(nèi)核版本3.16.0,物理內(nèi)存大小為128G的Linux服務(wù)器.服務(wù)器的操作系統(tǒng)為64位的CentOS 7,運行Java版本為1.8的64位HotSpot虛擬機(jī)(build 25.111-b14,mixed mode).

5.1 數(shù)據(jù)的收集

測試樣本中的安卓應(yīng)用主要來源于表2中四個應(yīng)用市場上收集的APK.

表2 四個安卓應(yīng)用市場收集的APKTable 2 APK collected from four markets

第三方庫則是通過解析F-Droid上的開源應(yīng)用配置文件中的GAV(groupName,artifactId和版本號),從Maven Central Repository上把對應(yīng)groupName和artifactId下的所有第三方庫版本用爬蟲爬下來、保存在數(shù)據(jù)庫中的.同樣地,我們也從兩個網(wǎng)站(Top 100 Android Libraries[注]https://github.com/Freelander/Android_Data/blob/master/Android-Librarys-Top-100.md和Awesome Android[注]https://snowdream.github.io/awesome-android/)上收集熱門的第三方庫.最終我們成功收集到了758種第三方庫,共計11620個版本.

通過分析APK中的配置文件和第三方庫使用時的配置設(shè)置,我們從樣本中獲取了23297個APK-第三方庫匹配對作為正樣本、23271個APK-第三方庫匹配對作為負(fù)樣本,組成了我們的測試集ground truth.將這四萬多測試集均勻隨機(jī)地劃分為100個小測試集,作為之后進(jìn)行參數(shù)自整定實驗使用.隨后,我們又根據(jù)安卓支持包與其他第三方庫之間的依賴關(guān)系,擴(kuò)展了7829個APK-第三方庫匹配對作為正樣本,再加上7446個新的負(fù)樣本,組成新的樣本集以供第三方庫檢測中的對比實驗使用.

5.2 參數(shù)自整定模塊的實驗

本小節(jié)主要描述參數(shù)自整定實驗的具體情況,主要有參數(shù)向量的設(shè)置、α值的確定以及實驗結(jié)果的分析.我們將通過實驗結(jié)果確定最優(yōu)參數(shù)組合,同時計算出分界閾值LST.實驗使用的樣本集為5.1節(jié)中隨機(jī)劃分的100個測試集,共計46568個樣本.

5.2.1 參數(shù)向量及α值的確定

我們分別以0.05、0.1和0.01的精度為PCT、CMT和MDT三個參數(shù)在0.4-0.6、0.5-0.9以及0.01-0.05之間設(shè)計參數(shù)組合.各參數(shù)在五水平上分配對應(yīng)的值如表3所示.

根據(jù)正交表L25(56)設(shè)計參數(shù)向量,將正交表的前三列分別作為PCT、CMT和MDT對應(yīng)的因素,生成(0.4,0.5,0.01)、(0.4,0.6,0.02)、……以及(0.6,0.9,0.04)共25個參數(shù)向量.

為了較好地平衡UCB算法中均值與測試次數(shù)標(biāo)準(zhǔn)差附加值對參數(shù)向量選擇的影響力,我們分別以不同的α值進(jìn)行了100次測試,統(tǒng)計參數(shù)向量的測試次數(shù)分布如表4所示.

表3 各參數(shù)在五水平上的賦值Table 3 Values for each parameter on five levels

表4 參數(shù)向量測試次數(shù)分布表Table 4 Test number distribution of parameter vectors

α值為1時,AUC值對參數(shù)組合被測試次數(shù)的影響可以忽略,各參數(shù)組合都測試了4次;而當(dāng)α值太大比如等于30時,AUC的影響太大以至于很多參數(shù)向量只得到1次被試機(jī)會,次數(shù)附加值起的作用很小,這種情況容易造成因為第一次測試偶然不好的結(jié)果導(dǎo)致之后再也沒有測試機(jī)會,可能帶來誤差.因此,最終我們選定處于中間的α=10來進(jìn)行之后的參數(shù)自整定測試.

5.2.2 參數(shù)自整定實驗分析

我們以α=10對25個參數(shù)向量進(jìn)行實驗,以這25個參數(shù)向量經(jīng)過UCB分配進(jìn)行多次測試后得到的平均AUC值,作為每個參數(shù)向量的實驗結(jié)果.我們對每個因素上各水平取值進(jìn)行統(tǒng)計分析,結(jié)果如表5所示.

在這25個實際測試的參數(shù)組合中,有3個參數(shù)向量實驗獲得的平均AUC較高,分別是AUC為0.9962的(0.5,0.5,0.03)、AUC為0.9953的(0.4,0.5,0.01)和AUC為0.9952的(0.45,0.5,0.02).

統(tǒng)計分析這25個參數(shù)向量的水平數(shù)據(jù),表5中I-V行是該參數(shù)在每個水平(即每種賦值)上的AUC數(shù)據(jù)和,K1-K5則是該參數(shù)各水平取值的AUC綜合平均值,R為該參數(shù)下各水平AUC的極差.可以看出從水平1到5,PCT和CMT對AUC值的影響都是逐漸遞減,而MDT則是有起伏波動,在水平4上達(dá)到最大值,因此我們推斷最優(yōu)的參數(shù)向量為水平(1,1,4)的組合,即在PCT=0.4、CMT=0.5和MDT=0.04時達(dá)到最好的識別第三方庫效果.我們隨機(jī)挑選3個測試集對該參數(shù)組合進(jìn)行測試,得到平均AUC值為0.9967,確實優(yōu)于測試的25個參數(shù)向量,因此我們最終選定該組合作為第三方庫檢測的閾值設(shè)置.

表5 參數(shù)自整定實驗結(jié)果分析Table 5 Parameter auto-tuning results analysis

5.2.3 LST的確定

根據(jù)先前的實驗,我們確定了PCT=0.4、CMT=0.5和MDT=0.04的閾值設(shè)定,在該參數(shù)組合下對所有46568個樣本進(jìn)行實驗,最終得到第三方庫檢測的AUC值為0.9959,根據(jù)實驗數(shù)據(jù)繪制出的ROC曲線是一條十分貼近x=0和y=1的曲線.遍歷所有ROC繪制點,計算每個點TPR與FPR的差值,得到約登指數(shù)最大的點為坐標(biāo)(0.01569,0.99632),此時約登指數(shù)等于0.98062,該點以LST= 0.4955作為臨界值,統(tǒng)計可得在這部分樣本集上的召回率(recall)為99.63%,準(zhǔn)確率(precision)為98.46%.因此,將0.4955確定為之后第三方庫檢測實驗中劃分一個應(yīng)用是否包含指定第三方庫的臨界值.

5.3 第三方庫檢測模塊的實驗

本小節(jié)主要描述關(guān)于LibSeeker檢測第三方庫效果的實驗,同時我們也對LibSeeker與LibScout的效果進(jìn)行比較.實驗中使用與之前參數(shù)自整定實驗不同的樣本集,包括7829個支持包擴(kuò)展的正樣本和7446個負(fù)樣本.

5.3.1 抗混淆性分析

我們對LibSeeker的抗混淆性進(jìn)行分析,挑選正樣本中LibSeeker檢測結(jié)果是完全匹配的,即與第三方庫相似度為1.0的APK-第三方庫匹配對,共計12510對.對這些完全匹配對所包含的6148個APK進(jìn)行類名分析,發(fā)現(xiàn)其中類名被混淆過的有3359個,約占59.64%.而LibSeeker成功檢測出這些混淆過的APK中包含的第三方庫,由此可見LibSeeker在一定程度上可以避免混淆的影響.

5.3.2 與LibScout之間的比較

LibSeeker基于LibScout中使用的代碼無關(guān)函數(shù)哈希進(jìn)行匹配,保留了應(yīng)對混淆的能力,同時加入特征向量centroid降低誤匹配的概率;LibScout中的參數(shù)閾值設(shè)定依賴于有限的實驗和人工經(jīng)驗,而我們在LibSeeker中實現(xiàn)了對參數(shù)向量的自動整定功能,減少人為依賴因素.

我們分別對LibSeeker和LibScout檢測第三方庫的效果進(jìn)行對比實驗,其中針對LibSeeker還進(jìn)行了使用參數(shù)自整定(PCT=0.4、CMT=0.5、MDT=0.04)和使用原始閾值(PCT=0.5、CMT=0.8、MDT=0.02)的對照實驗.我們以LibScout中設(shè)定的第三方庫相似度閾值0.6作為本實驗中LibScout和使用原始閾值的LibSeeker這兩組的LST臨界值,而參數(shù)自整定的LibSeeker這組的LST值設(shè)置為5.2.3節(jié)中計算得到的0.4955.最終實驗結(jié)果如表6所示.

表6 LibSeeker與LibScout實驗結(jié)果比較Table 6 Comparison of LibSeeker and LibScout

從實驗結(jié)果可以看出,LibSeeker中加入的函數(shù)特征向量比較減少了函數(shù)簽名沖突的影響,使得LibSeeker對第三方庫檢測的準(zhǔn)確性優(yōu)于LibScout.而參數(shù)自整定進(jìn)一步優(yōu)化了LibSeeker的效果,比起采用原始閾值的LibSeeker,在準(zhǔn)確率變化不大的情況下,檢測的召回率有了大幅度的提高.使用參數(shù)自整定的LibSeeker的準(zhǔn)確率和召回率達(dá)到了99.82%和95.77%.

6 總 結(jié)

安卓應(yīng)用廣泛使用第三方庫來構(gòu)建功能,大部分現(xiàn)有的第三方庫檢測方法可靠性不夠,對混淆技術(shù)抵抗程度較弱,實驗中的閾值設(shè)定往往依賴于人工經(jīng)驗.本文設(shè)計并實現(xiàn)了能進(jìn)行參數(shù)自整定的第三方庫檢測工具LibSeeker,通過采用LibScout中與代碼無關(guān)的函數(shù)簽名哈希,結(jié)合特征向量centroid,為第三方庫和應(yīng)用中的包進(jìn)行匹配,并根據(jù)層級關(guān)系進(jìn)行篩選,選取全局相似度最大的作為最終匹配結(jié)果,從而實現(xiàn)對第三方庫精確可靠的識別.同時,LibSeeker還實現(xiàn)了對閾值的參數(shù)自整定功能,通過自整定實驗挑選出最優(yōu)的參數(shù)組合,進(jìn)一步提高了第三方庫檢測的準(zhǔn)確率與召回率.