使用指向分析的安卓庫函數(shù)數(shù)據(jù)流摘要方法

高穎慧,楊亞東,張 源,楊 珉

1(復(fù)旦大學(xué) 軟件學(xué)院,上海 201203) 2(上海通用識別技術(shù)研究所,上海 201100) E-mail:yuanxzhang@fudan.edu.cn

1 引 言

近年來,移動智能手機在人們的日常生活中發(fā)揮著越來越重要的作用,其中Android是現(xiàn)在最受歡迎的智能手機操作系統(tǒng).手機上的應(yīng)用軟件以其不斷豐富的功能吸引著用戶的同時也能訪問到更多的用戶隱私信息,而這些敏感數(shù)據(jù)的泄漏將給用戶的安全造成一定的威脅.

針對海量應(yīng)用軟件隱私泄漏的問題,研究人員提出了多種自動化程序分析方法和工具,其中靜態(tài)數(shù)據(jù)流分析是一種非常常用的技術(shù)手段.Android平臺為了減輕應(yīng)用程序開發(fā)者的負擔(dān)和增加代碼復(fù)用,提供大量的Android應(yīng)用程序編程接口(Application Programming Interface,簡稱API).應(yīng)用程序的開發(fā)和執(zhí)行過程中會大量使用到這些API.為了更加精確地分析軟件的行為,靜態(tài)數(shù)據(jù)流分析工具不僅要分析應(yīng)用程序的代碼,也要分析這些API對應(yīng)的庫函數(shù)代碼.

然而,庫函數(shù)數(shù)目眾多、邏輯復(fù)雜,分析庫代碼將會為程序分析引入大量的開銷,遠超過應(yīng)用程序本身的開銷,往往使得分析最終以超時或內(nèi)存不足而告終.同時,針對每一個應(yīng)用軟件都需要對庫代碼重新分析,嚴重制約了靜態(tài)數(shù)據(jù)流分析技術(shù)應(yīng)用于海量應(yīng)用軟件的分析.

處理庫函數(shù)的分析一個比較好的辦法是為庫函數(shù)生成數(shù)據(jù)流摘要,摘要能對每個庫函數(shù)的行為建模,使得分析應(yīng)用程序時無需再分析庫函數(shù)代碼,只需要使用庫函數(shù)摘要就可以得到庫函數(shù)對應(yīng)用程序產(chǎn)生的效果.同時,數(shù)據(jù)流摘要在生成

1http://wala.sf.net/

后,可以被重復(fù)運用于分析各個應(yīng)用程序.但是Android平臺提供的庫函數(shù)數(shù)量巨大,如何為這些函數(shù)生成精確的數(shù)據(jù)流摘要是一個非常重要的問題.通過人工方式編寫函數(shù)摘要需要理解大量代碼才能進行數(shù)據(jù)流建模,無法應(yīng)對百萬級API的數(shù)據(jù)流摘要生成.簡單地基于啟發(fā)式規(guī)則去建模庫函數(shù)數(shù)據(jù)流摘要粒度太粗,無法精確表征庫函數(shù)代碼的實際行為,也不能反應(yīng)各個API之間的差異性行為.

StubDroid[1]是第一個針對Android數(shù)據(jù)流分析問題自動化生成庫函數(shù)摘要的工具.通過自動化地分析庫函數(shù)代碼執(zhí)行期間對數(shù)據(jù)流傳播的影響,StubDroid可以為每個API生成數(shù)據(jù)流摘要,并且應(yīng)用于以FlowDroid[2]為代表的靜態(tài)分析工具中.然而,本文發(fā)現(xiàn)StubDroid只對庫函數(shù)的數(shù)據(jù)依賴關(guān)系建模,并未為庫函數(shù)內(nèi)指針指向信息生成摘要.Java語言的動態(tài)綁定機制使得Android應(yīng)用程序必須根據(jù)對象的實際類型調(diào)用相應(yīng)的函數(shù),是以靜態(tài)分析為了得到精確的函數(shù)調(diào)用圖,需要通過指向分析確定變量在運行時可能指向的對象信息.使用StubDroid生成摘要的靜態(tài)數(shù)據(jù)流分析工具由于不再分析庫代碼,將缺失庫函數(shù)中的指針指向信息,從而生成不精確的函數(shù)調(diào)用關(guān)系并且采取比較保守的方式加載庫函數(shù)摘要中的數(shù)據(jù)流,而這些都將會產(chǎn)生不正確的數(shù)據(jù)流傳播,為數(shù)據(jù)流分析引入假陰性和假陽性的結(jié)果.

因此,本文設(shè)計并實現(xiàn)了一種融合指向分析的自動化數(shù)據(jù)流摘要生成與使用工具Point2Droid.Point2Droid生成的摘要不僅包含庫函數(shù)的數(shù)據(jù)依賴關(guān)系,也為其中的指向關(guān)系建立模型,從而有效補充了StubDroid的不足.同時,我們設(shè)計了四組實驗對Point2Droid的性能進行測試,實驗結(jié)果顯示,Point2Droid能在平均30s內(nèi)為單個庫類生成摘要,生成的摘要經(jīng)人工驗證正確模擬了庫函數(shù)對數(shù)據(jù)流的影響.使用Point2Droid生成的摘要使得靜態(tài)隱私檢測工具的分析效率大大提高,并且檢測出了更多的隱私泄露路徑.

2 背景與相關(guān)工作

2.1 數(shù)據(jù)流分析與指針指向分析

數(shù)據(jù)流分析指的是一組用來獲取有關(guān)數(shù)據(jù)如何沿著程序執(zhí)行路徑流動的相關(guān)信息的靜態(tài)分析技術(shù)(基于變量作用域的數(shù)據(jù)流分析)[3].它能提取出程序的語義信息,在不實際運行應(yīng)用程序的情況下,推測其運行時可能發(fā)生的所有可能的行為,掌握應(yīng)用程序的功能,具有批量化分析、覆蓋率高等優(yōu)點.

指針指向分析是指通過不斷解析賦值語句,根據(jù)右值的指向信息計算和更新左值的指向信息,得到程序運行時各引用變量可能指向的對象,從而確定程序根據(jù)動態(tài)綁定實際所執(zhí)行的函數(shù)的過程.指針指向分析算法主要包括:Steensgaards[5]風(fēng)格算法,一種基于等價(equivalence-based)的指向分析,算法復(fù)雜度為Ο(n),但準確度不高;Andersen[4]風(fēng)格算法,一種基于子集(subset-based)的指向分析,它認為賦值語句將左右兩邊的引用變量產(chǎn)生一種集合包含關(guān)系,即左邊引用變量指針指向集合(Points-to Set)是右邊引用變量Points-to Set的子集,算法復(fù)雜度是Ο(n3),但準確度相對Steensgaards算法好一些.經(jīng)過效率和精度的權(quán)衡,靜態(tài)分析會選擇其中一種算法進行優(yōu)化和改進,現(xiàn)有的靜態(tài)分析框架也提供了基于兩種算法的指針指向分析框架,如本文選擇的Soot Pointer Analysis Research Kit(SPARK)[8]是Soot基于Andersen風(fēng)格算法提供的指向分析框架.

2.2 相關(guān)工作

在靜態(tài)分析方面,Vallée-Rai等人提出了Soot[6]和Fink等人提出的WALA1[7]是最為廣泛使用的兩大Java開源靜態(tài)分析框架,它們將Java字節(jié)碼轉(zhuǎn)化成不同形式的中間表達式,并在此之上實現(xiàn)對應(yīng)用程序進行過程內(nèi)和過程間的分析.隨著對Android安全研究的深入,學(xué)術(shù)界提出各種Android靜態(tài)分析框架:Arzt等人和Gordon等人基于Soot框架分別提出FlowDroid[2]和DroidSafe[9].Lu等人和Wei等人基于WALA框架分別提出了CHEX[10]和Amandroid[11].這些靜態(tài)分析工具雖然在設(shè)計思想、性能及檢測結(jié)果上存在差異,但都需要使用模型加速對庫函數(shù)的分析.其中FlowDroid和CHEX使用一些過于簡單的規(guī)則概括部分庫函數(shù)對數(shù)據(jù)流的影響,Amandroid和DroidSafe則人工精確建模常用的庫函數(shù).由于人工需要耗費極大的精力且版本更新需要重新分析,而簡單規(guī)則過于粗粒度,所以這些工具都并未很好解決庫函數(shù)的問題.

在庫函數(shù)摘要方面,Juan Zhai等人[12]根據(jù)Java庫函數(shù)中的文檔說明對庫函數(shù)行為進行了人工建模,但這種人工方法精度不高且費時費力,無法大規(guī)模應(yīng)用.Yinzhi Cao等人提出EdgeMiner[13],將庫函數(shù)對應(yīng)用程序的回調(diào)總結(jié)在一些規(guī)則中,能自動化地得到Android中的回調(diào)函數(shù),這雖然能協(xié)助建立完整控制流圖,但無法改進對庫函數(shù)的數(shù)據(jù)流分析.Hao Tang等人[14]認為庫函數(shù)的分析結(jié)果使用依賴于上下文,他們提出了一種新的形式化語言TAL來描述這一類庫函數(shù)行為.但此工作目前仍然處于形式化表述的階段,未能生成可用的工具.

3 StubDroid以及存在的問題

StubDroid是為庫函數(shù)中數(shù)據(jù)流關(guān)系建模的全自動工具.它每次只針對一個庫函數(shù),為函數(shù)內(nèi)的變量之間的數(shù)據(jù)依賴關(guān)系建立模型,生成摘要存儲到文件中.當靜態(tài)污點分析工具稍后處理在應(yīng)用程序代碼中對庫函數(shù)調(diào)用時,只需要簡單地插入從摘要文件中得到的信息,在截斷其進一步對被調(diào)用的庫函數(shù)和所有傳遞被調(diào)用者(即庫函數(shù)內(nèi)調(diào)用的函數(shù))分析的情況下,依然可以精確地計算得到這些被調(diào)用的庫函數(shù)和傳遞的被調(diào)用者對污點傳播產(chǎn)生的影響.

具體做法是以對當前庫函數(shù)的參數(shù)、當前對象的this引用和全局變量所涉及的訪問路徑(access path)的數(shù)據(jù)讀取(如圖1第5行的p1)作為source,并以對當前庫函數(shù)的參數(shù)、當前對象的this引用和返回值和全局變量所涉及的訪問路徑(access path)的數(shù)據(jù)寫入(如圖1第5行的this.mX)作為sink,使用FlowDroid執(zhí)行污點分析生成source到sink的數(shù)據(jù)流映射,每一條數(shù)據(jù)流映射表明source和sink之間存在數(shù)據(jù)依賴關(guān)系(即數(shù)據(jù)傳播關(guān)系,如a?b表明變量b依賴于變量a,變量a的數(shù)據(jù)傳播到變量b).如圖1所示,StubDroid在分析完XYHolder構(gòu)造函數(shù)以后會生成參數(shù)1與this.mX、參數(shù)2與this.mY之間的數(shù)據(jù)流映射.分析完成之后將這些數(shù)據(jù)流映射存儲到摘要文件中,之后在靜態(tài)數(shù)據(jù)流分析工具分析應(yīng)用程序代碼遇到庫函數(shù)調(diào)用時會加載相應(yīng)的摘要文件,遍歷從摘要中獲取到數(shù)據(jù)流映射,根據(jù)被依賴變量(source)當前在程序中的狀態(tài),計算依賴變量(sink)的狀態(tài),這樣就完成了根據(jù)數(shù)據(jù)流映射做數(shù)據(jù)傳播,在所有的數(shù)據(jù)流映射處理完之后,就能得到目標庫函數(shù)對程序產(chǎn)生影響后的數(shù)據(jù)狀態(tài).

對于簡單的庫函數(shù),StubDroid能夠很容易使用上述方法建模生成摘要,但當庫函數(shù)內(nèi)存在回調(diào),即庫函數(shù)將通過客戶端傳入的指針調(diào)用函數(shù),由于StubDroid為該庫函數(shù)生成摘要時不會分析客戶端代碼,所以無法確定實際回調(diào)的函數(shù),進而無法得到它的數(shù)據(jù)流傳播.如圖1的evaluate函數(shù),StubDroid為其生成摘要時無法確定傳入對象引用所指向的對象的具體類型,因而不能確定實際調(diào)用的是哪個類的getX()函數(shù)和getY()函數(shù),導(dǎo)致無法進一步分析.為了解決這個問題,避免回調(diào)函數(shù)數(shù)據(jù)流信息的缺失對生成摘要產(chǎn)生的影響,StubDroid使用gap對每一個無法確定的回調(diào)函數(shù)進行占位,并且記錄該函數(shù)簽名,同時建模從source到gap以及從gap到sink之間的數(shù)據(jù)流映射.當對應(yīng)用程序的靜態(tài)分析使用到摘要時,才在gap處插入對應(yīng)的回調(diào)函數(shù)的數(shù)據(jù)流傳播.因此,圖1的evaluate函數(shù)的摘要文件中會包含簽名分別為和的gap.

然而,在使用摘要時,由于不再分析庫代碼,失去了庫函數(shù)內(nèi)對象的指向信息,StubDroid只能保守地根據(jù)摘要中g(shù)ap對應(yīng)的函數(shù)簽名依據(jù)以下步驟查找所有可能的回調(diào)函數(shù):

1)從摘要文件目錄查找所有可能的實現(xiàn)或者繼承了該簽名的方法所包含的數(shù)據(jù)流映射.

2)若1中沒有成功加載到數(shù)據(jù)流映射,則遍歷程序,獲取客戶端代碼中實現(xiàn)或者繼承了該簽名的方法,然后對每一個方法進行靜態(tài)數(shù)據(jù)流分析.

這種保守的方法會產(chǎn)生不正確的數(shù)據(jù)流傳播,從而對數(shù)據(jù)流分析的準確性產(chǎn)生影響.如圖2所示的應(yīng)用程序代碼,當靜態(tài)分析到第8行語句時會加載庫函數(shù)evaluate(圖1)的摘要信息,而evaluate的摘要文件中存在簽名為的gap,StubDroid沒有該gap的指向信息,只能根據(jù)步驟1從XYHolder的摘要文件中找到 getX()(圖1的8～10行)方法并加載其中包含的數(shù)據(jù)流映射,得到返回值this.mX.然而程序在實際運行中,調(diào)用的是BenignXYHolder的getX()(圖2的18到20行)函數(shù),該函數(shù)返回的是常量.于是在這種情況下,將會使得靜態(tài)分析到圖2的第10行產(chǎn)生假陽性的結(jié)果.

4 Point2Droid基本架構(gòu)

為了建模庫函數(shù)行為,本文基于StubDroid設(shè)計并實現(xiàn)了一種融合指向分析的自動化數(shù)據(jù)流摘要生成與使用工具Point2Droid.如圖3所示,Point2Droid根據(jù)功能主要分成兩個模塊:摘要生成模塊和摘要使用模塊.

4.1 摘要生成模塊

該模塊以庫的二進制代碼作為輸入,通過庫代碼中每一個公開(public)函數(shù)執(zhí)行一遍摘要生成所需要的分析得到相應(yīng)的函數(shù)模型摘要,并依此代表每個API會對應(yīng)用程序分析產(chǎn)生的效果.為了進一步提高分析效率,摘要生成過程中會將一個類中所有函數(shù)的摘要輸出到同一個摘要文件中,以節(jié)省內(nèi)存占用、方便共享和復(fù)用.

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

庫函數(shù)模型摘要主要分成兩部分:指針指向摘要和數(shù)據(jù)依賴摘要,其中數(shù)據(jù)依賴摘要由StubDroid生成.為了生成指針指向摘要,Point2Droid首先為當前分析構(gòu)造入口函數(shù),然后從該入口函數(shù)出發(fā)執(zhí)行指針指向分析,指向分析能得到當前分析中所有變量的指向?qū)ο蠹?通過對結(jié)果的處理,得到目標庫函數(shù)在調(diào)用前后對引用變量指向?qū)ο笏鞒龅脑摳淖?并將這一改變記錄下來,建模成函數(shù)指針指向摘要.

4.2 摘要使用模塊

該模塊應(yīng)用于應(yīng)用程序的靜態(tài)分析中,當分析到應(yīng)用程序調(diào)用API時,摘要使用模塊截斷其對庫代碼的進一步分析,通過加載和解析摘要文件中的庫函數(shù)模型,得到API對應(yīng)用程序產(chǎn)生的影響,然后根據(jù)如下公式計算出應(yīng)用程序在函數(shù)調(diào)用后的狀態(tài).這樣既能保證分析的精度,又能節(jié)省對庫函數(shù)分析所浪費的時間和內(nèi)存.

Statusbefore+Changesummary=Statusafter

摘要使用模塊也分成兩部分:指針指向摘要的使用和數(shù)據(jù)依賴摘要的使用.

5 Point2Droid設(shè)計與實現(xiàn)

Point2Droid通過改進Soot[6]內(nèi)置的指向分析框架SPARK[8]生成庫函數(shù)的指向信息摘要,同時基于StubDroid生成數(shù)據(jù)依賴摘要,最后將得到的庫函數(shù)指針指向信息和數(shù)據(jù)傳播信息應(yīng)用于靜態(tài)污點分析工具FlowDroid中.

5.1 構(gòu)造入口函數(shù)

為庫函數(shù)生成指針指向摘要時,由于單個庫函數(shù)不是完整的可執(zhí)行程序,沒有main方法,因而需要構(gòu)造一個DummyMain方法,并且在方法體內(nèi)構(gòu)造調(diào)用當前被分析庫函數(shù)的語句.然后Soot將統(tǒng)一以DummyMain為入口函數(shù)并作為起點,執(zhí)行接下來的分析.

5.2 摘要生成模塊的指針指向分析

為了得到庫函數(shù)中所有指針指向?qū)ο蟮男畔?需要通過如圖4所示的指針指向分析流程為庫函數(shù)生成指針指向摘要.其核心是迭代式地根據(jù)當前可達函數(shù)構(gòu)建指針賦值圖(Pointer Assignment Graph,PAG),然后沿著圖中的邊不斷更新節(jié)點對應(yīng)的引用變量的指向信息.與此同時,依次訪問圖中節(jié)點獲取更新后的指向信息,更新函數(shù)調(diào)用圖,從而添加新的可達函數(shù).最初的可達函數(shù)為入口函數(shù)DummyMain.

圖4 摘要生成的指針指向分析流程圖Fig.4 Points-to analysis of summarization

5.2.1 創(chuàng)建PAG

PAG是用來描述變量與對象指向關(guān)系的有向圖,在Soot中PAG圖中有三類節(jié)點:內(nèi)存分配節(jié)點(Allocation Node,AllocNode),代表代碼中創(chuàng)建一個新的對象(new C());變量節(jié)點(Variable Node,VarNode),代表代碼中的本地變量、方法參數(shù)、 返回值及靜態(tài)域(dst);域引用節(jié)點(Field Dereference Node,FieldRefNode),代表代碼中的域變量(src.f)[8].節(jié)點的指向信息由集合表示,稱為指針指向集合(Points-to Set).指向分析根據(jù)分析語句的不同來生成不同類型的邊,并對不同類型的邊產(chǎn)生不同的Points-to Set傳播規(guī)則,具體如表1所示.

表1 Points-to Set傳播規(guī)則
Table 1 Rules of Points-to Set propagation

語句類型邊(a表示newC())邊類型傳播規(guī)則dst=newC()a→dstAllocNode→VarNodeAllocationa→pt(dst)dst=srcsrc→dstVarNode→VarNodeAssignmentpt(src)→pt(dst)dst.f=srcsrc→dst.fVarNode→FieldRefNodeFieldStoreptsrc()→pta.f()a∈pt(dst)dst=src.fsrc.f→dstFieldRefNode→VarNodeFieldLoadpta.f()→ptdst()a∈pt(src)

5.2.2 創(chuàng)建DummyAllocNode

由于庫函數(shù)做指向分析生成摘要時,缺失參數(shù)以及this引用的指向信息,且?guī)旌瘮?shù)生成的摘要需要適用于所有可能的應(yīng)用和使用上下文中,Point2Droid會在創(chuàng)建PAG時為被分析函數(shù)的參數(shù)和this引用創(chuàng)建DummyAllocNode節(jié)點抽象表示變量在函數(shù)調(diào)用之前所有可能的指向信息,并且在DummyAllocNode和變量節(jié)點之間添加一條Allocation邊(表示為該變量new了一個新對象,見表1).此外,由于參數(shù)和this引用相關(guān)的域變量(如this.f)在函數(shù)調(diào)用前的指向信息也是缺失的,為了區(qū)分二者,當庫函數(shù)內(nèi)使用這些變量時,Point2Droid會為其創(chuàng)建DummyFieldAllocNode節(jié)點.其中DummyFieldAllocNode類繼承自DummyAllocNode類,表示DummyFieldAllocNode節(jié)點是一種特殊的DummyAllocNode節(jié)點.

5.2.3 Points-to Set的傳播與函數(shù)調(diào)用圖的更新

指針指向分析會以所有AllocNode為起點遍歷PAG的邊,使用表1中的規(guī)則傳播和更新節(jié)點的Points-to Set.同時,在節(jié)點更新Points-to Set以后,訪問以該節(jié)點表示的變量為調(diào)用基的調(diào)用點,添加相應(yīng)的函數(shù)調(diào)用邊,更新函數(shù)調(diào)用圖.如調(diào)用點v.m(…)在v更新指向信息后,可以得到v實際指向的對象類型,根據(jù)該類型以及調(diào)用語句聲明的函數(shù)子簽名,解析得到的函數(shù)即為其實際調(diào)用的函數(shù)(callee).

5.2.4 為無法確定的函數(shù)調(diào)用創(chuàng)建gap

由于Points-to Set中存在DummyAllocNode節(jié)點,它是抽象出來的對象,其實際類型需要在客戶端代碼運行時才能確定,所以以指向該節(jié)點的引用變量為調(diào)用基的調(diào)用點在摘要生成階段無法確定其實際的callee,這也將無法計算該callee對指針指向信息所產(chǎn)生的影響,從而影響到整個庫函數(shù)的分析.為了消除不確定callee的影響,Points2Droid借用StubDroid中g(shù)ap的概念,使用gap為該函數(shù)占位,并且記錄進入gap前與gap相關(guān)引用變量(調(diào)用點的調(diào)用基、傳入的參數(shù)和返回值)的指向信息,以及創(chuàng)建DummyAllocNode為離開gap之后的相關(guān)引用變量所有可能的指向信息抽象建模.

5.3 生成指針指向摘要

在指針指向分析得到各引用變量的Points-to Set以后,需要計算出整個目標庫函數(shù)對指針指向?qū)ο笏龅母淖?并將其記錄為摘要.這樣應(yīng)用程序的分析就不再需要庫代碼只需要摘要即可完成Points-to Set的更新與傳播.

由于庫函數(shù)通過參數(shù)、返回值和this引用(統(tǒng)稱為對外開放引用變量)與應(yīng)用程序傳遞指針且會保存gap相關(guān)引用變量的指向信息,所以庫函數(shù)的摘要只需要關(guān)心庫函數(shù)對上述6種引用變量及其域變量的指向信息改變.對于對外開放引用變量及其域變量而言,由于其函數(shù)調(diào)用前指向信息不確定,均使用DummyAllocNode建模其指向信息,所以其函數(shù)調(diào)用前的Points-to Set(用pt(before)表示)只有一個與變量唯一對應(yīng)的DummyAllocNode節(jié)點;而對于gap相關(guān)變量及其域變量而言,其函數(shù)調(diào)用前指向信息為空,pt(after)-pt(before)=pt(after).所以,庫函數(shù)的摘要就是記錄上述6種引用變量及其域變量的Points-to Set.

Points-to Set中主要存儲了兩類節(jié)點,一類是指向庫函數(shù)內(nèi)部實例化的對象AllocNode節(jié)點,另一類是為了建模引用變量可能的指向信息所創(chuàng)建的DummyAllocNode,表示當前變量與被建模的引用變量指向同一對象.這兩類節(jié)點都可以表述為映射關(guān)系,前者為對象和變量之間的映射,后者為變量與變量之間的映射.因此最終生成的摘要應(yīng)是一種多對多的指向映射關(guān)系,為了方便,Point2Droid使用多對一的Map來存儲.

綜上所述,Point2Droid首先找到上面提到的6種基本變量,然后根據(jù)這6種基本變量找到其域變量,在得到這些變量的Points-to Set之后,遍歷Points-to Set中的節(jié)點,提取出如下所示關(guān)系(→表示指向關(guān)系映射),存儲在Map中.

6種引用變量及其域變量→6種引用變量及其域變量

實例類型→6種引用變量及其域變量

5.4 生成摘要文件

Point2Droid使用StubDroid生成數(shù)據(jù)依賴摘要,當一個庫類分析完成以后,它將類中所有函數(shù)的指針指向摘要和數(shù)據(jù)依賴摘要一起存儲到xml格式文件中.xml作為可擴展標記語言,具有結(jié)構(gòu)清晰,讀寫方便等優(yōu)點.

Point2Droid針對圖1示例中的XYEvaluator類生成的摘要文件結(jié)構(gòu)如圖5所示,由于篇幅,只選取了其中部分映射關(guān)系.methods元素是一個類中所有函數(shù)摘要的合集,每一個函數(shù)對應(yīng)一個method元素,屬性signature是該函數(shù)的簽名.每一個函數(shù)摘要包含兩類信息,指針指向關(guān)系映射和數(shù)據(jù)依賴關(guān)系映射,這兩類信息由三類元素表示.

?baseobject:該類元素主要是為了簡化object中的訪問路徑,代表庫函數(shù)中的六種引用變量.

?object: 該類元素使用屬性p2set和屬性field代表多對一的指針指向關(guān)系映射,表示如下所示Points-to Set的傳播規(guī)則.

src∈p2set,pt(src)→pt(field)

?flow: 該類元素使用屬性from和屬性to代表數(shù)據(jù)依賴映射,表示to變量的數(shù)據(jù)依賴于from變量.

Methods之后的gaps元素是類中所有使用到的gap的合集,被baseobject和flow元素中的gap屬性引用到.

5.5 指針指向摘要的使用

指針指向摘要將應(yīng)用于應(yīng)用程序靜態(tài)分析的指針指向分析階段,圖6是使用摘要的指針指向分析流程的示意圖,圖中虛線部分與摘要生成的指針指向分析相同.

圖6 使用摘要的指針指向分析流程圖Fig.6 Points-to Analysis of using summary

5.5.1 加載解析摘要文件

對摘要文件的使用不是直接將目錄下所有的摘要文件都加載到內(nèi)存中,而是當分析程序檢測到應(yīng)用程序調(diào)用API時,Point2Droid才會從磁盤請求此類的摘要文件并將其加載到內(nèi)存中.如果磁盤上存在大量(或許多不同)庫的摘要,則可以大大降低內(nèi)存消耗.

5.5.2 創(chuàng)建DummyVarNode

為了將摘要中指向信息映射到PAG上,我們需要創(chuàng)建DummyVarNode來代表庫函數(shù)中的變量節(jié)點,DummyVarNode繼承自VarNode,表示一個在程序中不存在代碼的變量.但摘要中具有映射關(guān)系的不僅有變量還有域變量和實例對象,是以要分情況生成不同的節(jié)點:

·實例對象,解析出該對象的具體類型,創(chuàng)建AllocNode.

·基本變量,直接創(chuàng)建DummyVarNode.

·域變量,從左到右依次解析訪問路徑,拿到或者創(chuàng)建被引用變量的DummyVarNode,并且根據(jù)DummyVarNode和域創(chuàng)建FieldRefNode,再為域變量創(chuàng)建DummyVarNode,然后在兩個新創(chuàng)建的節(jié)點之間添加一條Load類型的邊.

5.5.3 構(gòu)造PAG

首先為當前庫函數(shù)生成一個過程內(nèi)的指針賦值圖MethodPAG,并在其中根據(jù)函數(shù)簽名信息創(chuàng)建this引用、參數(shù)和返回值對應(yīng)的VarNode節(jié)點.然后根據(jù)摘要中指針指向關(guān)系的映射,在MethodPAG創(chuàng)建相應(yīng)的DummyVarNode節(jié)點,并在兩個具有指向關(guān)系的節(jié)點之間添加一條Assignment邊.最后根據(jù)應(yīng)用程序中的調(diào)用語句按照圖7所示的關(guān)系將MethodPAG與整個應(yīng)用程序的PAG連接起來.這樣就能在不需要庫函數(shù)代碼的情況下依然可以構(gòu)建出完整的PAG,同時得到每個節(jié)點的Points-to Set.

5.5.4 處理Gap和生成GapEdge

由于gap的存在,在DummyVarNode更新得到它的Points-to Set后,需要解析以這個節(jié)點為調(diào)用基的gap所對應(yīng)的callee.遍歷節(jié)點的Points-to Set,取出每個AllocNode,判斷AllocNode的類型是對應(yīng)一個庫函數(shù)類還是一個應(yīng)用程序類.庫函數(shù)類則從摘要文件中加載相應(yīng)文件取出對應(yīng)摘要信息,應(yīng)用程序類則根據(jù)類型和子簽名得到真正的函數(shù).解析得到gap調(diào)用的callee之后,則為這一調(diào)用生成一個特殊的函數(shù)調(diào)用邊GapEdge并保存在函數(shù)調(diào)用圖中,然后再沿著GapEdge更新PAG.

圖7 連接PAG和Method PAGFig.7 Add Method PAG into PAG

5.6 數(shù)據(jù)流摘要的使用

Point2Droid基于StubDroid使用數(shù)據(jù)依賴摘要.但是本文提到過,StubDroid之前因為缺乏指針指向信息,會使用一些保守的方法查找調(diào)用點或者gap所調(diào)用的函數(shù),并且加載所有可能的數(shù)據(jù)依賴,從而產(chǎn)生不正確的數(shù)據(jù)傳播.而Point2Droid能獲得程序完整的指向信息,生成精確的函數(shù)調(diào)用圖,因此將StubDroid改進為根據(jù)調(diào)用點或者gap真實調(diào)用的函數(shù)加載數(shù)據(jù)依賴,得到準確的數(shù)據(jù)傳播,應(yīng)用于數(shù)據(jù)流分析中.

6 實驗與分析

本部分,我們將從摘要生成和摘要使用兩個方面對Point2Droid的性能進行實驗,摘要生成方面將從摘要生成效率和摘要準確性的角度進行衡量,摘要使用方面也將就使用摘要對靜態(tài)分析工具的分析效率和分析結(jié)果方面產(chǎ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虛擬機(build 25.111-b14,mixed mode).在針對摘要生成的測評時將最大內(nèi)存(-Xmx)設(shè)置為16G,在針對摘要使用的測評時將最大內(nèi)存設(shè)置為96G.

6.1 摘要生成的效率測試

我們使用Point2Droid為Android SDK和Oracle JDK中的庫代碼中17個常用類生成摘要文件,并統(tǒng)計其時間開銷.實驗用的測試樣本是由摘要生成相關(guān)實驗的樣本是Android AOSP 4.2手動構(gòu)建的android.jar(Google分發(fā)的SDK只有Stub沒有具體函數(shù)實現(xiàn)),和Java 8(1.8.0_91)使用的rt.jar.

表2的測試結(jié)果顯示Point2Droid能在平均30s內(nèi)為一個類生成摘要,這表明Point2Droid生成摘要不是一個耗時耗力的工作.Android SDK和Oracle JDK所產(chǎn)生的結(jié)果幾乎一致,但有些微的差別,這表明兩者在庫函數(shù)的實現(xiàn)上略有差別,但它們的庫函數(shù)對應(yīng)用程序影響是差不多的.此外可以看到生成摘要的時間與objects、flows的數(shù)目不是一個正相關(guān)的關(guān)系,這是因為庫函數(shù)代碼的復(fù)雜程度與指向關(guān)系映射、數(shù)據(jù)流映射條數(shù)沒有關(guān)系.

表2 摘要生成效率測試的結(jié)果
Table 2 Experiment result of summarization efficiency

類名OracleJDKAndroidSDKobject數(shù)目flow數(shù)目生成時間(s)object數(shù)目flow數(shù)目生成時間(s)java.util.ArrayDeque6415143.156815736.30java.util.ArrayList3811135.484311430.43java.util.HashMap5312523.748212118.77java.util.HashSet7112722.827111918.86java.util.IdentityHash-Map416218.15456517.74java.util.WeakHashMap6514230.367111918.16java.util.Hashtable699128.386013821.54java.util.Stack7520960.986216947.12java.util.Vector6118550.945715543.14java.util.concurrent.Concur-rentHashMap6526559.306616839.81java.util.concurrent.CopyOn-WriteArraySet506927.92397216.87java.io.BufferedReader1614117.652018717.26java.io.CharArrayWriter347538.57337327.71java.io.DataInputStream4516528.753512127.78java.io.ByteArrayInput-Stream22513.6922414.80java.io.BufferedArray-OuputStream134111.01123911.44java.io.FilterOutput-Stream8209.9482110.41平均4511830.644611024.60

6.2 摘要的準確性測試

為了驗證Point2Droid生成指針指向摘要的準確性,我們?nèi)斯ぷ粉檸旌瘮?shù)中的指針傳遞,并為庫函數(shù)最終產(chǎn)生的指向關(guān)系建模,然后對比人工建模的指向關(guān)系映射與Point2Droid生成結(jié)果的差異.由于庫函數(shù)比較復(fù)雜,人工追蹤指針傳遞將花費極大的精力,所以我們只分析了Android SDK中五個類(見表3 )的函數(shù)實現(xiàn),最后結(jié)果顯示Point2Droid生成的指針指向摘要完全與人工分析的結(jié)果完全一致.這證明Point2Droid這樣的自動化摘要生成工具可以為庫函數(shù)生成正確的指向信息,避免人工去編寫摘要.

表3 摘要準確性測試的樣本
Table 3 Test sample of summarization accuracy

類名函數(shù)數(shù)目object數(shù)目指向關(guān)系映射數(shù)目java.util.Observable81617java.util.ArrayDeque286868java.util.Hashtable176066java.io.BufferedWriter173944java.lang.Integer152122

6.3 摘要對靜態(tài)數(shù)據(jù)流分析效率的測試

為了驗證Point2Droid生成的摘要對應(yīng)用程序數(shù)據(jù)流分析性能產(chǎn)生的影響,我們隨機選取的5個大小合適的樣本分別在不使用摘要且加入整個庫函數(shù)的分析、使用StubDroid工具生成的摘要以及使用Point2Droid生成的摘要三種模式下使用靜態(tài)分析工具FlowDroid執(zhí)行數(shù)據(jù)流分析,并且將它們各自的超時(timeout,時間限制)設(shè)為一小時,其它所有運行環(huán)境和參數(shù)均保持一致,最后統(tǒng)計各個分析的時間開銷.

表4 靜態(tài)分析在三種模式下的時間開銷對比
Table 4 Compare time overhead of static analysis in three modes

應(yīng)用程序應(yīng)用程序大小(M)運行時間(s)分析整個庫函數(shù)的FlowDroid使用StubDroid生成摘要的FlowDroid使用Point2Droid生成摘要的FlowDroidDroidCoupon0.86超時57.1124.56ADRD1.62超時28.098.78DroidKungFuSapp2.14超時37.1115.81DogWars4.39超時40.4620.34Plankton8.54超時34.0110.94平均3.51N/A39.3616.09

表4是本次實驗的結(jié)果,由結(jié)果我們可以看到,若應(yīng)用程序的分析中加入對庫函數(shù)的分析往往會導(dǎo)致超時從而得不到分析結(jié)果,而使用摘要替代庫代碼的分析能將整個數(shù)據(jù)流分析的時間開銷降低為幾十秒.此外,我們還注意到,使用Point2Droid生成的摘要模式下執(zhí)行的數(shù)據(jù)流分析將明顯快于在使用StubDroid生成的摘要模式下的分析,前者平均16s而后者平均39s.因此,我們可以認為Point2Droid生成的摘要對靜態(tài)數(shù)據(jù)流分析的效率有顯著的提升.

表5 靜態(tài)污點分析在三種模式下檢測到的隱私泄漏對比
Table 5 Compare leak detection of static analysis in three modes

應(yīng)用程序使用Point2Droid生成摘要使用StubDroid生成摘要不分析庫函數(shù)庫函數(shù)/數(shù)據(jù)流隱私泄漏數(shù)目庫函數(shù)/數(shù)據(jù)流隱私泄漏數(shù)目隱私泄漏數(shù)目DroidKungFuUp-date13485115753Endofday324662851954N/A28DogWars17841830240175Plankton62771614874DroidKungFu1151511318352138DroidKungFu22712234455962010DroidKungFu3197727348632727DroidCoupon20911936791196DroidDreamLight1413632162243219GoldDream189132229932RogueSPPush134758212635837Asroot42441514744CoinPirate1910258346365856Zsone104121243852121GingerMaster159353262505350BeanBot3015023395162311KMin2719244365804240YZHC1819869252726932DroidKungFuSapp159574284627040DroidDream317855845055平均1811629424

6.4 摘要對靜態(tài)數(shù)據(jù)流分析效果的測試

為了測試Point2Droid生成的摘要對靜態(tài)數(shù)據(jù)流分析的檢測效果產(chǎn)生的影響,我們隨機從Android惡意軟件基因組項目[15]中挑選了20個樣本分別在不使用摘要且不分析庫函數(shù)、使用StubDroid工具生成的摘要以及使用Point2Droid生成的摘要三種模式下使用FlowDroid執(zhí)行污點分析,并且統(tǒng)計分析檢測到的隱私泄漏數(shù)目.

本次實驗結(jié)果(表5)顯示,使用Point2Droid的摘要相比于使用StubDroid生成的摘要,需要加載的庫函數(shù)數(shù)目和數(shù)據(jù)流數(shù)目明顯減少,而分析出的隱私泄漏數(shù)目不僅沒有減少,反而有所提高.其中,利用StubDroid生成的摘要進行測試的EndofDay出現(xiàn)了超時,而其它兩種模式下沒有,這是因為使用StubDroid生成的摘要會加載更多的數(shù)據(jù)流從而使得靜態(tài)污點分析將更多的數(shù)據(jù)打上污點,分析的時間增加,導(dǎo)致超時,這也驗證了6.3的結(jié)果.在StubDroid生成摘要模式下和在Point2Droid生成摘要模式下檢測到的隱私泄漏均多于未使用摘要且不分析庫函數(shù)模式下的檢測結(jié)果.

7 總 結(jié)

為了避免庫函數(shù)為程序分析帶來的過多開銷,需要為庫函數(shù)建模生成摘要.針對現(xiàn)有的自動化摘要技術(shù)StubDroid中因缺乏對庫函數(shù)中指向信息建模而產(chǎn)生的數(shù)據(jù)流分析的精確度和覆蓋率上的問題,本文提出了Point2Droid系統(tǒng).Point2Droid實現(xiàn)了對庫函數(shù)的指向信息進行自動化的摘要生成并且在靜態(tài)數(shù)據(jù)流分析過程中自動加載指向信息摘要,通過庫函數(shù)中指向信息的支持,靜態(tài)數(shù)據(jù)流分析工具能生成準確的函數(shù)調(diào)用圖,加載正確的庫函數(shù)信息流,有效地解決了StubDroid系統(tǒng)中存在的精確性和覆蓋率問題.

[1] Arzt S,Bodden E.StubDroid:automatic inference of precise data-flow summaries for the android framework[C].Proceedings of the 38th International Conference on Software Engineering,ACM,2016:725-735.

[2] 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.

[3] Alfred V A,Monica S L,Ravi S,et al.Compilers principles,techniques and tools(2nd )[M].Beijing:China Machine Press,2009:382-402

[4] Andersen L O.Program analysis and specialization for the C programming language[D].University of Cophenhagen,1994.

[5] Steensgaard B.Points-to analysis in almost linear time[C].Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages,ACM,1996:32-41.

[6] Vallée-Rai R,Co P,Gagnon E,et al.Soot-a Java bytecode optimization framework[C].Proceedings of the 1999 Conference of the Centre for Advanced Studies on Collaborative Research,IBM Press,1999:13.

[7] Fink S,Dolby J.WALA-the TJ watson libraries for analysis[EB/OL].https://wala.sourceforge.net,2017.

[8] Lhoták O,Hendren L.Scaling Java points-to analysis using Spark[C].International Conference on Compiler Construction.Springer Berlin Heidelberg,2003:153-169.

[9] Gordon M I,Kim D,Perkins J,et al.Information-flow analysis of Android applications in droid safe[C]. Network and Distributed System Security Symposium.2015.

[10] Lu L,Li Z,Wu Z,et al.CHEX:statically vetting Android apps for component hijacking vulnerabilities[C]. ACM Conference on Computer and Communications Security,ACM,2012:229-240.

[11] Wei F,Roy S,Ou X,et al.Amandroid:a precise and general inter-component data flow analysis framework for security vetting of Android apps[C]. ACM Sigsac Conference on Computer and Communications Security,ACM,2014:1329-1341.

[12] Zhai J,Huang J,Ma S,et al.Automatic model generation from documentation for Java API functions[C]. International Conference on Software Engineering,ACM,2016:380-391.

[13] Cao Y,Fratantonio Y,Bianchi A,et al.EdgeMiner:automatically detecting implicit control flow transitions through the Android framework[C]. Network and Distributed System Security Symposium,2015.

[14] Tang H,Wang X,Zhang L,et al.Summary-based context-sensitive data-dependence analysis in presence of callbacks[C].ACM SIGPLAN Notices,ACM,2015,50(1):83-95.

[15] Zhou Y,Jiang X.Dissecting android malware:Characterization and evolution[C].Security and Privacy (SP),2012 IEEE Symposium on.IEEE,2012:95-109.

附中文參考文獻：

[3] Alfred V A,Monica S L,Ravi S,et al.編輯原理[M].北京：機械工業(yè)出版社，2009:382-402.