使用指向分析的安卓庫函數數據流摘要方法

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

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

1 引 言

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

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

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

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

1http://wala.sf.net/

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

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

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

2 背景與相關工作

2.1 數據流分析與指針指向分析

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

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

2.2 相關工作

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

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

3 StubDroid以及存在的問題

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

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

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

然而,在使用摘要時,由于不再分析庫代碼,失去了庫函數內對象的指向信息,StubDroid只能保守地根據摘要中gap對應的函數簽名依據以下步驟查找所有可能的回調函數:

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

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

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

4 Point2Droid基本架構

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

4.1 摘要生成模塊

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

圖3 Point2Droid系統架構示意圖Fig.3 System architecture of Point2Droid

庫函數模型摘要主要分成兩部分:指針指向摘要和數據依賴摘要,其中數據依賴摘要由StubDroid生成.為了生成指針指向摘要,Point2Droid首先為當前分析構造入口函數,然后從該入口函數出發執行指針指向分析,指向分析能得到當前分析中所有變量的指向對象集合,通過對結果的處理,得到目標庫函數在調用前后對引用變量指向對象所作出的該改變,并將這一改變記錄下來,建模成函數指針指向摘要.

4.2 摘要使用模塊

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

Statusbefore+Changesummary=Statusafter

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

5 Point2Droid設計與實現

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

5.1 構造入口函數

為庫函數生成指針指向摘要時,由于單個庫函數不是完整的可執行程序,沒有main方法,因而需要構造一個DummyMain方法,并且在方法體內構造調用當前被分析庫函數的語句.然后Soot將統一以DummyMain為入口函數并作為起點,執行接下來的分析.

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

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

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

5.2.1 創建PAG

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

表1 Points-to Set傳播規則
Table 1 Rules of Points-to Set propagation

語句類型邊(a表示newC())邊類型傳播規則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 創建DummyAllocNode

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

5.2.3 Points-to Set的傳播與函數調用圖的更新

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

5.2.4 為無法確定的函數調用創建gap

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

5.3 生成指針指向摘要

在指針指向分析得到各引用變量的Points-to Set以后,需要計算出整個目標庫函數對指針指向對象所做的改變,并將其記錄為摘要.這樣應用程序的分析就不再需要庫代碼只需要摘要即可完成Points-to Set的更新與傳播.

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

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

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

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

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

5.4 生成摘要文件

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

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

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

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

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

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

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

5.5 指針指向摘要的使用

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

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

5.5.1 加載解析摘要文件

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

5.5.2 創建DummyVarNode

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

·實例對象,解析出該對象的具體類型,創建AllocNode.

·基本變量,直接創建DummyVarNode.

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

5.5.3 構造PAG

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

5.5.4 處理Gap和生成GapEdge

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

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

5.6 數據流摘要的使用

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

6 實驗與分析

本部分,我們將從摘要生成和摘要使用兩個方面對Point2Droid的性能進行實驗,摘要生成方面將從摘要生成效率和摘要準確性的角度進行衡量,摘要使用方面也將就使用摘要對靜態分析工具的分析效率和分析結果方面產生的影響進行評估.

實驗環境為:具有40核心(Intel Xeon E7-4830,2.13Ghz),內核版本3.16.0,物理內存大小為128G的Linux服務器.服務器的操作系統為64位的CentOS 7,運行Java版本為1.8的64位HotSpot虛擬機(build 25.111-b14,mixed mode).在針對摘要生成的測評時將最大內存(-Xmx)設置為16G,在針對摘要使用的測評時將最大內存設置為96G.

6.1 摘要生成的效率測試

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

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

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

類名OracleJDKAndroidSDKobject數目flow數目生成時間(s)object數目flow數目生成時間(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生成指針指向摘要的準確性,我們人工追蹤庫函數中的指針傳遞,并為庫函數最終產生的指向關系建模,然后對比人工建模的指向關系映射與Point2Droid生成結果的差異.由于庫函數比較復雜,人工追蹤指針傳遞將花費極大的精力,所以我們只分析了Android SDK中五個類(見表3 )的函數實現,最后結果顯示Point2Droid生成的指針指向摘要完全與人工分析的結果完全一致.這證明Point2Droid這樣的自動化摘要生成工具可以為庫函數生成正確的指向信息,避免人工去編寫摘要.

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

類名函數數目object數目指向關系映射數目java.util.Observable81617java.util.ArrayDeque286868java.util.Hashtable176066java.io.BufferedWriter173944java.lang.Integer152122

6.3 摘要對靜態數據流分析效率的測試

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

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

應用程序應用程序大小(M)運行時間(s)分析整個庫函數的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是本次實驗的結果,由結果我們可以看到,若應用程序的分析中加入對庫函數的分析往往會導致超時從而得不到分析結果,而使用摘要替代庫代碼的分析能將整個數據流分析的時間開銷降低為幾十秒.此外,我們還注意到,使用Point2Droid生成的摘要模式下執行的數據流分析將明顯快于在使用StubDroid生成的摘要模式下的分析,前者平均16s而后者平均39s.因此,我們可以認為Point2Droid生成的摘要對靜態數據流分析的效率有顯著的提升.

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

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

6.4 摘要對靜態數據流分析效果的測試

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

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

7 總 結

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

[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].北京：機械工業出版社，2009:382-402.