基于稀疏框架的靜態污點分析優化技術

王 蕾 何冬杰 李 煉 馮曉兵

(計算機體系結構國家重點實驗室(中國科學院計算技術研究所) 北京 100190) (中國科學院大學 北京 100049) (wanglei2011@ict.ac.cn)

當前，隱私數據保護是信息系統安全的重要研究挑戰之一，大量的互聯網(電子郵件、社交網絡)、移動應用(移動支付、手機定位)、物聯網(智能家居、智能醫療等)相關數據需要存放在應用端，如果應用程序因存在漏洞而被攻擊者利用(完整性違反)或者第三方應用程序有意地竊取用戶系統中本地的數據(保密性違反)，則會產生隱私泄露問題[1].對系統應用中潛在的隱私數據泄露風險檢測是當前該領域的重要研究方向.污點分析技術[2](taint analysis)是信息流分析技術[3](information-flow analysis)的一種實踐方法.該技術通過對系統中敏感數據進行標記，繼而跟蹤標記數據在程序中的傳播，檢測系統的保密性和完整性等安全問題.據調查分析[4]，在Android應用的靜態安全檢測中，污點分析是最為流行的分析方案.

污點分析又被分為靜態污點分析和動態污點分析.靜態污點分析是指在不運行代碼的前提下通過分析程序變量間的數據依賴關系來進行污點分析.相比動態運行的污點分析，靜態污點分析無需對程序進行插樁而導致運行時出現額外開銷，并且不依賴于測試用例輸入，可以在程序發布之前對應用程序進行檢測，避免發布之后造成的安全問題.然而，當前靜態污點分析技術的分析性能仍然不能滿足安全檢測的需求.例如，MudFlow[5]嘗試使用靜態污點分析工具FlowDroid[6]對當前Android應用市場的應用進行安全漏洞檢測，它只能使用低敏感度的程序分析且在運行內存較大(730 GB)的環境下，一些例子仍然出現檢測超時.并且，低敏感度的程序分析會報告出大量的誤報，這會給檢測人員帶來諸多不便，同樣降低了檢測的效率，類似的問題還存在其他工作中[7-9].因此，對高敏感度的靜態污點分析進行空間和時間上的優化是一個值得研究的問題.

最近，在程序分析領域中，大量的研究工作[10-18]嘗試使用稀疏的方式對靜態程序分析問題進行效率優化.所謂的稀疏程序優化是指數據流值(data flow fact)不再沿著控制流圖(control flow graph， CFG)上進行傳遞，而轉移到利用DEF-USE鏈得到的相關數據結構上傳遞.例如文獻[10]利用了半稀疏(semi-sparse)的方法對指針分析進行優化，將指針數據流值從CFG上的傳播轉移到數據流圖中進行傳播.使用DEF-USE鏈代替CFG來傳遞數據流值可以消除不必要的傳播計算從而達到優化的目的.

由于污點分析只是分析污點能否從污點源(source)傳播到匯聚點(sink)，是一種按需的分析方式，當前的主流靜態污點分析(FlowDroid)是基于IFDS框架的，而目前的IFDS框架是沒有對稀疏優化進行支持的.因此，本文的工作內容正是嘗試利用稀疏的優化方法對靜態污點分析進行優化.

本文的主要貢獻包含4個方面:

1) 發現并分析當前基于IFDS(interprocedural,finite,distributive,subset)問題的靜態污點工具FlowDroid計算中存在大量無關聯傳播，并通過實驗驗證其比例平均高達85.2%.

2) 為了支持稀疏的污點傳播，提出了一種稀疏的IFDS數據流分析框架，提供面向流敏感和域敏感的變量使用點索引的計算方法.

3) 設計了基于稀疏數據流分析框架的污點分析技術.

4) 實現一個基于本文技術的原型系統Flow-DroidSP，經過實驗驗證，該工具在提升性能的同時沒有帶來精度上的損失.在非剪枝模式下，相比原FlowDroid具有平均4.8倍的時間加速和61.5%的內存降低，在剪枝模式下，具有平均18.1倍的時間加速和76.1%的內存降低.

1 背景知識

1.1 IFDS數據流分析框架

一般而言，靜態污點分析問題都是被轉化為數據流分析問題[19]進行求解:首先為每一個過程構建控制流圖或者過程間的控制流圖，然后根據不同敏感度(上下文敏感、流敏感等)進行具體的數據流傳播分析(與指針/別名分析).IFDS框架[20]是一個精確高效的上下文敏感和流敏感的數據流分析框架，其全稱是過程間(interprocedural)、有限的(finite)、滿足分配率的(distributive)、子集合(subset)問題.該問題作用在有限的數據流域中且數據值對并(或交)的集合操作滿足分配率.滿足上述限定的問題都可以利用IFDS算法進行求解(文獻[20]中的Tabulation算法)，而污點分析正是滿足IFDS算法要求的一個問題.污點分析的數據流值是污點變量，它表示有哪些污點變量可以到達當前程序點.

IFDS問題求解算法的核心思想就是將程序分析問題轉化為圖可達問題[21].算法的分析過程在一個按照具體問題所構造的超圖(exploded supergraph)上進行(如圖1例子所示).其中數據流值可以被表示成圖中的節點，算法擴展了一個特殊數據流值:0值，用于表示空集合；程序分析中轉移函數的計算，即對數據流值的傳遞計算被轉化為圖中的邊的求解.為了更好地進行描述，算法根據程序的特性將分析分解成4種轉移函數(邊):1)Call-Flow，即求解函數調用(參數映射)的轉移函數.2)Return-Flow，即求解函數返回語句返回值到調用點的轉移函數.3)CallToReturn-Flow，即函數調用到函數返回的轉移函數.4)Normal-Flow，是指除了上述3種函數處理范圍之外的語句的轉移函數.IFDS求解算法Tabulation是一種動態規劃的算法，即求解過的子問題的路徑可以被重復地利用，而由于其數據流值滿足分配率，因此可以在分支或函數調用將邊進行合并.求解算法包括了2類路徑的計算:路徑邊集(path edges)和摘要邊集(summary edges).路徑邊集表示的是起點0值到當前計算點的可達路徑，使用傳播函數propagate將計算完成的邊繼續沿CFG傳播到其下一個節點;摘要邊集表示的是函數調用到函數返回的邊，其主要特點是如果在不同調用點再次遇到同樣的函數調用，可以直接利用其摘要邊集信息從而避免了函數內重復的路徑邊集的計算.

Fig. 1 An example of taint analysis by using IFDS algorithm圖1 使用IFDS算法求解污點分析示例

1.2 FlowDroid與別名分析

FlowDroid[6]是當前最為流行的面向Java，Android應用程序的開源靜態污點分析工具，被廣泛應用于Android App的隱私泄露檢測和Java程序相關安全漏洞挖掘.FlowDroid基于Java分析工具Soot[22]，將待分析程序字節碼轉化成Soot中間表示Jimple，隨后在Jimple上進行靜態的污點分析.其分析的結果是多個污點源到污點匯聚點(source→sink)的集合.在污點傳播分析中，FlowDroid正是基于IFDS數據流分析框架.同時，FlowDroid使用訪問路徑(access path，即形如v.f.g)來支持域敏感，如果訪問路徑長度超過預定值時，FlowDroid將對其進行保守的裁剪(例如裁剪成v.f.*的形式)，在具體實現中訪問路徑的長度一般設置為5.因此，FlowDroid具有流敏感、上下文敏感、域敏感的高精確度.

FlowDroid的另一貢獻就是提供了一種按需的面向別名的污點傳播方法，該方法同樣是基于IFDS框架的.具體來講，FlowDroid在遇到一個堆變量(heap object)的域進行污點賦值時，會啟動一個后向的IFDS求解器求解其別名相關的污點值，如果生成與該變量別名的污點變量，則又啟動一個前向的IFDS求解器進行前向傳播該值.以圖2中的偽代碼為例，程序的行④污點源(函數source()的返回值)賦值到了一個堆對象的域a.f中，此時將啟動一個后向的分析來尋找與a.f別名的污點值(過程1)，當后向求解器分析到a使用點行②時，將產生與a別名的對象b的對應污點值，即b.f(過程2)，同時啟動一個前向分析，繼續找b.f的使用位置(過程3).同理，過程4/5/6/7是對b.f和c.f的進一步傳播.為了解決流敏感的分析，FlowDroid引入激活點的概念，激活點的作用是保證未被激活的變量只有通過了激活點之后才是一個真正的污點值，否則即便到達泄露點也不會觸發泄露.例如在過程6中的c.f變量只有再次經過了行④的激活點到達行⑤觸發了sink，才是一個真正的泄露.而對于過程3中的b.f，雖然也到達了函數sink，但是它沒有經過激活點，因此行③的sink不能被觸發.

Fig. 2 An example of FlowDroid-style alias based taint analysis圖2 FlowDroid方式的別名間污點傳播示例

本文的工作正是基于FlowDroid進行擴展優化的，目前FlowDroid中污點傳播所使用的數據流分析無論是前向求解還是后向求解(計算別名)都是基于IFDS框架的.IFDS框架的計算規模直接影響了污點分析的開銷.然而，當前IFDS框架仍然是基于CFG或過程間CFG的，這會導致數據流分析中存在無關聯的傳播.所謂的無關聯傳播是指數據流值傳播到某語句，但是該語句不會利用其生成其他數據流值或將其殺死，例如圖1中變量a在行①被使用之后還會繼續傳遞到行②～④直到程序結束，而行③～④中沒有使用a產生其他數據流值，a在行③～④上的傳播正是無關聯傳播.因此本文的目標正是利用稀疏的優化方法來消除這種無關聯的傳播，從而達到效率優化的目的.

2 研究動機

在面向高精確(流敏感和域敏感)的污點分析的計算中，無關聯的數據流傳播還將被擴大，進而產生更大的性能開銷.具體來講：

1) 現代編譯器利用中間表示對程序進行分析或者優化，基于3地址的中間表示被各大編譯器采用(如Soot的Jimple表示).例如圖3(a)程序為一段程序的源碼，圖3(b)程序是其3地址表示，這種轉換過程必然會引入大量的臨時變量，對于行②中的b.f.h=a.f語句將被轉化為程序圖3(b)中的行②～④的程序，其中利用了2個臨時變量tmp1，tmp2.這種臨時變量的使用會增加無關聯傳播的規模.

Obj foo(Obj p){ …① a.f=p;② b.f.h=a.f;③ retum b.f.h;} Obj foo(Obj p){ …① a.f=p;② tmp1=a.f;③ tmp2=b.f;④ tmp2.h=tmp1;⑤ retum tmp2.h;}(a) Source code(b) Three-address IR void caller1(){ …① x.f1=source();② Obj y=foo(x);③ sink(y.f1);} void caller2(){ …① x.f2=source();② Obj y=foo(x);③ sink(y.f2);}(c) Caller1(d) Caller2

Fig. 3 An example of unrelated taint propagation
圖3 無關聯污點傳播示例

2)為了支持域敏感的分析，FlowDroid使用訪問路徑來表示污點變量，由于相同對象的不同域需要不同的區分，這會導致同一份代碼因不同域的使用而被執行多次、無關聯傳播將會被放大.例如，圖3(c)和圖3(d)中程序都調用了函數foo()，但是它們所傳遞的參數對應的域是不同的，分別是x.f1和x.f2．對于同一個對象但訪問不同參數的情況，IFDS認為它們是不同的變量而不會對其進行摘要優化.此時，參數p.f1傳遞到tmp2.h 等過程產生的變量，如tmp1.f.f1和tmp2.h.f1等，那么對于p.f2的計算，也同樣需要再次生成，如變量tmp1.f.f2和tmp2.h．f2等，可見無關聯傳播增加了1倍.

3) 為了支持流敏感，FlowDroid使用了激活點的方法，每一個未被激活的數據流都會存在一個激活點，即使數據流值中的訪問路徑相同但因激活點不同，數據流值仍然是不同的，同理2)這也同樣導致摘要優化失效.不同激活點的數據流值通過相同的代碼片段將會導致這種無關聯傳播的增加.

為了驗證上述無關聯傳播確實存在，以及計算其規模和所占比例，我們針對FlowDroid進行實驗驗證.

具體的評測對象是最新版本的FlowDroid(2017年11月)，針對其IFDS計算邊進行插樁統計，統計的規則有3項：

1) 對于Normal Flow和CallToReturn Flow，通過該函數生成了其他值或者被殺死，那么置為有關聯的，否則視為無關聯傳播.

2) 對于Call Flow，如果存在被調用函數(callee)且當前數據流值可以通過被調用函數生成相關形參，那么這個變量是有關聯的傳播.

3) 對于Return Flow，如果數據流值可以通過退出語句生成調用者(caller)的相關返回值，那么將設置其為有關聯的傳播.

評測的實驗機器配置是:64核Intel?Xeon?CPU E7-4809(2.0 GHz)和128 GB RAM，為每一個Java虛擬機分配32 GB的內存.配置選項選擇打開流敏感性并且設置訪問路徑的長度為5.具體的評測用例是在安智網[23]隨機下載的25個Android應用程序.由于某些軟件是不存在惡意行為的且對計算規模較小的程序評測沒有意義，這里去除掉了沒有產生泄露結果或分析結果過快(小于10 s)的6個應用和3個運行超出內存的應用，最終評測用例集合包含16個應用程序，它們的基本信息如表1所示，本文后續評測用例所用標號是與該表標號一一對應的.隨后使用FlowDroid對其運行3次檢測，提取結果并求平均值，其最終的統計運行結果如表2所示.

Table 1 The Information of Evaluation Dataset表1 評測用例基本信息

表2中第2列(Running Time)和第3列(Memory Size)是程序的運行時間和內存開銷.其中編號11的程序，盡管程序的規模只有1.5 MB，但是程序運行時間卻長達1 922 s，這正是由于流敏感和上下文敏感的較高時間復雜度導致的.第5列(#IFDS)是總的IFDS計算邊個數，而第6列是無關聯的IFDS計算邊(#UR-IFDS)個數，其中總IFDS計算邊個數平均高達1.1×107，而無關聯IFDS計算邊個數平均為1.01×107.可見無關聯的計算邊占總計算邊的比例是很高的，其中最低比例是79.1%，最高比例為92.9%，平均比例為85.2%，這也充分驗證了前面的分析.所以得出結論是：由于域敏感和流敏感的特性使得IFDS算法的摘要優化失效，當前無關聯的計算占總計算的比例較高且規模較大.本文的研究目標正是嘗試將數據流值直接傳遞到其使用點的位置，跨過這些無關聯的傳播(稀疏的方式)，來消除這種無關聯的計算.

Table 2 The Results on Evaluation of FlowDroid表2 使用FlowDroid對數據集進行評測結果

為了解決該問題，本文的方法將DEF-USE鏈的思想引入到IFDS計算框架中，在數據流傳播時，直接將數據流值從其產生的位置傳遞到其真正使用點.

3 稀疏的IFDS框架

提供稀疏的污點分析的前提正是提供稀疏的數據流分析框架.本節將介紹如何將經典的數據流分析框架IFDS擴展成稀疏的形式.本文的方法同樣是嘗試使用DEF-USE鏈來代替CFG進行數據流值傳播.然而與傳統方法不同的是：為了支持域敏感和流敏感，本文使用了一種特殊的數據結構來存儲變量的使用點，并提供了快速的構建算法(3.3節和3.4節介紹)，最后我們在3.5節修改了原IFDS的傳播函數，將得到的數據流值直接傳播到其使用點.

3.1 指令定義

首先定義本框架中用到的指令規則，將程序中所有語句轉化為3地址的形式(Jimple中間表示形式)，保證程序中只存在6種與數據流傳播相關的指令.為了方便后續規則的表示，這里將賦值語句[COPY]根據目標為左值或者右值的情況分成[READ]和[WRITE]形式.對于堆變量的域訪問，如形如v.f變量的訪問，我們命名其堆所在對象為基對象(base),即變量v，f則是基對象中的域(field).對堆對象域的讀和寫被定義為[LOAD]和[STORE]規則.如表3所示為所有的6種指令規則.

Table 3 The Rules of the Instruction表3 指令規則

3.2 變量使用點索引

為了維護域敏感和流敏感性，這里使用一種特殊的數據結構來表示變量的DEF-USE關系.

定義1. 變量使用點索引.變量使用點索引是一個表(map)結構，它的鍵值(key)是變量的域，它的值(value)是該變量對應域的所有使用點集合.

這里使用一個特殊域null來表示變量中域為空的情況，使用函數setUses[f]=[stmt]表示將語句[stmt]加入到變量的域f的使用點集合中，使用v.getUseStmts(f)來表示獲得的f域對應的使用點集合，使用v.getUseStmts(*)表示獲得v的索引表中所有域對應的使用點集合.

3.3 自治數據流圖ADFG

定義2. 自治數據流圖(autonomous data flow graph, ADFG).自治數據流圖是一個有向圖G=N,E，其中節點N表示程序中的變量且所有變量的基對象相同，邊E為表示節點所在語句之間的控制流.

如圖4(b)正是基對象為a的自治數據流圖，對于基對象a的所有相關變量均在該圖中，且這些變量所在的語句(圖4(b)用行號表示)之間的控制流是節點之間相連的邊.ADFG的優勢就是圖中變量的基對象相同且保存了完整的控制流信息，之后對每一個獨立的變量計算其DEF-USE(變量使用點索引)時，即可在ADFG中進行，這既提高了分析效率，又保證了流敏感.

Fig. 4 An example of ADFG圖4 自治數據流圖(基對象為a)示例

基于ADFG的定義，我們提供了一種快速的構建ADFG的算法.該算法將按照變量的基對象進行分區，然后對于每一個分區中的變量分別計算其獨立的數據流圖.具體算法如算法1所示:

算法1. 構建自治數據流圖算法.

輸入:程序的allCFGs;

輸出:程序的allADFGs.

①collectVariables(…);

②partitionByBasicBlock(…);

③buildADFG(…).

子過程1.collectVariables.

輸入:程序的allCFGs.

① for eachoneCFGinallCFGsdo

② for eachvarin eachstmtofoneCFGdo

③varInfoSetMap[base]←[var,bb,idx];

④ end for

⑤ end for

子過程2.partitionByBasicBlock.

輸入:varInfoSetMap.

① for eachvarInfoSetinvarInfoSetMapdo

② for eachvarinvarInfoSetdo

③bb=var.getBasicBlock();

④bbToVarInfoMap[bb]←var;

⑤ end for

⑥ end for

子過程3.buildADFG.

輸入:bbToVarInfoMap.

① for eachbbinbbToVarInfoMapdo

②ret=innerBBSolver(bb,bb.varSet);

③ varinfotail=ret.getTail;

④ fornextinbb.getSuccsdo

⑤traverseEachBB(next,tail);

⑥ end for

⑦ end for

子過程4.traverseEachBB.

輸入:后繼基本塊next，和前驅基本塊的尾節點preTail.

①ret=innerBBSolver(next,next.varSet);

②varinfohead=ret.getHead;

③preTail.setSucc(head);

④ fornextinbb.getSuccsdo

⑤traverseEachBB(next,ret.getTail);

⑥ end for

函數collectVariables將變量按照其基對象進行分區，存儲到Hash表varInfoSetMap中，對于一個變量，這里存儲的信息包括變量的值var和其基本塊信息bb以及其所在基本塊內部的索引號idx.函數partitionByBasicBlock再通過它所在的基本塊分區并存儲到Hash表bbToVarInfoMap中.之后，函數buildADFG對基對象相同的變量集合按每一個基本塊進行遍歷，在基本塊內部，buildADFG調用innerBBSolver方法順序的將后繼語句加入到前驅語句的后繼集合中.在基本塊之間，buildADFG通過innerBBSolver的返回值得到每一個基本塊的頭節點和尾節點，為上一個基本塊的尾節點設置下一個基本塊的頭節點為其后繼.

至此，ADFG上每一個變量都包含其控制流中的后繼信息，且不包含其他基對象的變量.函數collectVariables和partitionByBasicBlock線性地掃描程序中的變量，所以其算法時間復雜度是線性的.而buildADFG將對每一個基本塊進行遍歷，在基本塊內部則順序訪問每一個變量，所以buildADFG算法的時間復雜度也是線性的，整個構建ADFG算法的時間復雜度是線性的.

3.4 變量使用點索引的計算

在ADFG上，所有變量的基對象均相同且仍包含其控制流信息，整個CFG按照基對象的不同被分成多個ADFG.分析器將分別遍歷每一個ADFG，使用數據流分析的方法計算其變量的使用位置，將其存儲到使用點索引中.如表4所示為計算使用點索引的數據流轉移函數，圖5為對應示例.我們將在4.2節討論如何使用該索引為污點分析的訪問路徑生成具體的使用點以及對使用點集合進行剪枝.該分析使用了傳統的工作集(worklist)算法，初始化集合是所有語句中的變量v/v.f與當前語句[stmt](即變量的定義語句)組成的對[stmt],v/v.f.

Table 4 Data Flow Transfer Function for Computing

Fig. 5 Examples of variable using map computing圖5 計算變量使用點索引示例

表4中，第3列定義值(DEF value)是轉移函數的輸入，即變量的定義位置傳遞過來的數據流值，轉移函數的功能是決定是否將當前語句設置為該值的使用點.根據3.1節中的指令定義，定義值只能為v或者v.f的形式，例如圖5中被方格括住的變量.第4列Set USE Rule表示對定義值設置使用點索引的規則.為了區分域敏感特性，需要為不同的域存儲不同的使用點.如3.2節定義，使用setUses[f]=[Stmt]來表示將語句[stmt]加入到變量v的域f的使用點集合中，而setUses[null]表示定義值域是空的情況.第5列IsKill列表示定義值是否被殺死(True)或者繼續尋找其使用位置(False).

對于[ALLOC]和[WRITE]規則，如圖5(a)中例子所示，無論定義值是v還是v.f，都會將對v變量進行重新賦值，傳來的定義值不再有效.因此設置IsKill為True且不會產生使用關系.

對于[READ]規則，如果定義值是v,如圖5(b)左側程序，說明任何的形如v.*的訪問路徑都會傳遞到使用點，所以設置空域的使用點集合(setUses[null]=[stmt]).如果定義值是v.f，如圖5(b)右側程序，說明只有形如v.f.*的訪問路徑會傳遞到使用點，則設置域f的使用點集合(setUses[f]=[stmt]).

對于[LOAD]規則，說明訪問路徑第1個域滿足和f相等時才會被使用.所以無論訪問路徑是形如v.*或v.f.*的輸入，都將設置域f的使用點集合(setUses[f]=[stmt]).

對于[STORE]規則，如果定義值是v.f，如圖5(d)規則右側程序，同[WRITE]規則，傳來的定義值不再有效.如果定義值是v，說明形如v.*的訪問路徑可能傳播到該語句，且需要殺死其中第1個域為f的值.由于當前訪問路徑是無法表示形如v.{*-f}的數據流值，為了不丟失信息，這里使用一種延遲處理的方法：首先將該語句加入到定義值空域的使用點集合中(setUses[null]=[stmt])，然后保守地認為該定義值全部失效(將其殺死)，最后在初始化集合中增加一個虛擬的[stmt],v的定義值，增加新的虛擬定義值的目的是為了繼續傳播除f域之外的值.以圖5(d)左側程序為例，假設函數foo的返回值得到的訪問路徑是v.f2，v.f2根據空域的使用點可以傳播到[v.f1=“…”;]處，由于域不同，分析規則不會殺死該值，則會繼續啟動對v.f2使用點的查詢，此時將使用虛擬定義值v進行索引查詢，即可找到域f2的使用點[w=v.f2;].如果函數foo的返回值是v.f1的話，該值傳播到[v.f1=“…”]會根據分析規則被殺死.這種延遲處理的方式既不會損失精度又可以正確地進行更新.

對于[CALL]規則，如圖5(e)所示規則.這里設置使用點的規則同[WRITE]，這是因為在IFDS框架中函數的參數是否能夠通過函數調用繼續向下傳遞是由Call和CallToReturn規則決定的，所以這里直接將定義值置為失效，待Call和CallToReturn產生其返回值再進一步查找與傳播.

3.5 傳播函數

框架還需修改原IFDS框架的傳播函數(文獻[20]中算法行35的函數propagate)，這里為傳播函數增加一個包裝函數propagateWrapper，如算法2所示.

算法2. 稀疏的IFDS傳播函數propagate-Wrapper.

輸入:定義語句src、目標數據流值dtarget;

輸出:目標語句use、目標數據流值dtarget.

①useSet=defValue.getUseStmts();

② for eachuseStmtinuseSetdo:

③propagate(useStmt,dtarget)

④ end for

包裝函數將通過當前變量及其使用點索引獲得其使用點集合，然后將數據流值直接傳遞到其使用點.本算法不會影響IDFS產生新的數據流值的計算，而只是修改其傳播的目的語句，即達到稀疏傳播而又不影響正確性.例如圖6中a在行②處將仍然會產生b值，但會將b值直接傳播到其使用位置，即行③.

Fig. 6 An example of sparse IFDS framework圖6 稀疏的IFDS框架示例

4 基于稀疏框架的污點分析

4.1 總體框架

基于第3節的稀疏框架，本節設計實現了與其適配的污點分析技術，圖7所示為其整體框架.相對于傳統的污點分析(FlowDroid)，該框架增加一個預先分析(preAnalysis)的過程，即構建ADFG和計算變量使用點索引的過程.與FlowDroid一樣，分析的第1部分仍是待分析程序的ICFG(圖7中Build ICFG過程)，以此作為預先分析的輸入.預先分析過程生成的使用點索引作為污點傳播前向分析和后向分析(別名分析)的輸入，最后是輸出結果部分.

Fig. 7 The overview of the our taint analysis framework圖7 基于稀疏的污點分析總體框架

4.2 污點傳播中使用點的維護與剪枝

由于在3.4節中提供了面向域敏感和流敏感的變量使用點索引，本節將根據具體的輸入使用這些索引產生污點分析的使用點，并達到對使用點集合剪枝的效果.與FlowDroid類似，我們同樣使用訪問路徑來表示數據流值.具體如算法3所示:

算法3. 污點傳播使用點集合剪枝算法.

輸入:當前語句點stmt、數據流值訪問路徑apath;

輸出:數據流值的使用點集合useSet.

① ifapath.getFirstField≠null do

②useSet=∪getUseStmts(apath.

getFirstField)+getUseStmts(null);

④ ifisStore(stmt) do:

⑤useSet=∪(getUseStmts(*)-

getUseStmts(f));

⑥ else

⑦useSet∪=getUseStmts(*);

⑧ end if

⑨ end if

算法3的輸入是當前語句stmt和產生的數據流值的訪問路徑，這里用apath表示.如果當前apath是形如v.f.*的形式，即訪問路徑的第一個域是f，那么使用域null和f產生其使用點集合，即算法3中行②.這種方法可以過濾掉和f域不同的且不為空的域的使用點.如果apath是形如v.*的形式，說明當前v的子域不確定，因此需要傳播到其所有域的使用點，即算法3的行⑦.一種特殊的情況，如果語句是[STORE]形式，根據表4的[STORE]規則，當前存在一個v的虛擬定義變量的使用點索引，那么查找并使用該索引：除了需要產生所有域的使用點之外，還需要從中減去當前語句被賦值域的使用點，即算法3中行⑤，這是由于當前[STORE]已經將該域更新為其他值，無需再為該域計算使用點.最終算法的輸出是useSet,即根據當前訪問路徑得到的使用點集合.

本文的方法雖然沒有改變算法的復雜度(IFDS算法的時間復雜度為O(ED3)，空間復雜度為O(ED2)，其中E是當前控制流圖中的邊個數，D是數據流域的大小).但是由于我們的方法對當前控制流圖轉化成稀疏的形式(自治數據流圖)，所以E的值將會明顯的縮小，此外D的值也由于無關聯傳播被消除而變小，這也是本文方法能夠提高效率的原因.

4.3 面向別名傳播的變量使用點索引

在反向的IFDS計算中，后向的別名間污點傳播使用的變量使用點索引與前向傳播稍有不同：由于需要在使用點計算其別名的污點，所以同樣將語句加入其使用點集合中.表5是對應的轉移函數，其中與正向的轉移函數不同的是:[ALLOC]和[WRITE]和[LOAD]規則，即需要保留它們的使用點.

Table 5 Data Flow Transfer Function for Computing

4.4 流敏感的別名傳播維護

為了維護流敏感的別名傳播，基于IFDS的污點分析引入了激活點的概念，稀疏的方法同樣需要考慮這個問題，由于稀疏的方法不能沿著CFG上的每一條語句進行傳播，這給維護激活點帶來了挑戰.

為了解決該問題，我們利用了可能可達性的概念，所謂的可能可達(may reach)是一種偏序關系|→:如果程序語句S1和S2存在偏序關系S1|→S2，則說明可能存在一條執行路徑使得變量從S1到EXIT流經S2.相反，如果S1|→S2不被滿足，則說明一定不存在一條執行路徑從S1到EXIT流經S2.

那么，定義當前污點變量的定義點是defStmt，污點變量的激活點是activeStmt，污點變量的使用點是useStmt，如圖8中所示.則污點值被激活的必要條件是：

Fig. 8 An example of active stmt maintenance圖8 FlowDroid的激活點維護示例

約束1.defStmt|→activeStmt且activeStmt|→useStmt.

證明. 必要性證明.如果defStmt|→activeStmt不滿足，那么污點變量不會流經激活點，污點一定不會被激活.如果activeStmt|→useStmt不滿足，則說明到達activeStmt的值一定不會到達useStmt，也就不會存在被激活的變量到達useStmt.

證畢.

至于偏序關系|→是可以在預處理階段計算出的哈希映射進行查詢的.比較過程內2點S1和S2的偏序關系|→的方法：如果它們在一個基本塊中且該基本塊不在循環中，那么直接比較其基本塊內部索引號.否則比較基本塊之間的可能可達關系.而基本塊的可能可達關系可以在預處理中很快的得到一個Hash映射.所以整個偏序關系比較的時間復雜度是O(1)的.

不過滿足約束1的情況并不是滿足污點激活的充分條件，這是因為會存在數據流值被殺死的情況.為了保證精度，我們為滿足約束1的數據流值再啟動一個獨立的更新(update)分析，更新分析是沿著CFG進行的，直接使用傳統數據流方程求解(與FlowDroid方法一致).如果數據流值既滿足約束1又不被更新階段所殺死，則說明是被激活的.

4.5 剪枝優化討論

至此，本文的算法既保證了稀疏性又保證相比原FlowDroid不會損失任何的精確度.在具體實現中，基于變量使用點索引的剪枝算法還能夠消除FlowDroid的誤報，提高檢測的精度.具體分析：

Fig. 9 An example of FlowDroid conservative sub-field process圖9 FlowDroid的保守子域處理示例

如果當前分析器不確定具體的訪問路徑的子域時，FlowDroid會用一種保守的方式為其所有的子域均進行污點標記，即使用形如v.*的訪問路徑表示v以及v的所有子域均為污點標記.這里命名該處理方式為保守子域處理.保守子域處理方式雖然不會產生漏報，但是顯然是會產生誤報的.除了分析器不知道具體是哪個子域被標記的之外，還會存在分析器無法對子域進行正確更新的情況.如圖9所示，行①的source正是產生了v.*的數據流值，是一種保守子域的處理.當v.*傳播到行②時，由于不能確定是哪個子域被更新的(當前數據流值無法表示形如v.{*-f})，此時只能保守地不更新而繼續傳播v.*值.因此v.*到達行③時則會報告出泄露.而實際上行③的v.f1值已經在行②被設置成非敏感的數據，所以該報告是誤報.

而這種誤報是可以利用本文的方法進行消除的.具體分析：對于行②的左值v.f1，根據3.4節算法計算得到的使用點索引是(setUses[f1]=[L3])，而當數據流值v.*到達行②時，分析器執行4.2節算法3的行⑤分支，即使用規則[useStmt=∪getUseStmt(*)-getUseStmt(f)]來計算其使用點集合.此時，Hash表中f1域對應的使用點將會從總使用集合中刪除.因此，此時使用點集合中只包含行④而不會包含行③，繼而誤報被消除.

另外，據實驗觀察，這種保守子域的處理方式存在的情況是比較多的，這是因為不但直接引入的變量會產生保守子域處理，如果訪問路徑的長度超過預先設置的值時，FlowDroid會將該訪問路徑進行裁剪(cut off)，裁剪后的變量也是一種保守子域處理的方式.例如預先設置的訪問路徑閾值為3時，當生成的訪問路徑為v.f.g.h時，則會保守地轉化成v.f.g.*的情況.如果程序中存在循環的情況(使得訪問路徑長度不斷增加)，這種裁剪而導致的保守子域處理的情況尤為突出，我們在實驗評測部分統計驗證了經過裁剪的數據流值占總數據流值所占比例是較大的(5.4節).

5 實現與實驗

基于本文方法，我們在FlowDroid和Soot的基礎上實現了原型系統FlowDroidSP，其中重用了FlowDroid創建ICFG、訪問路徑、提取結果部分以及計算污點的轉移函數(4種IFDS轉移函數).為了保證函數調用和函數返回的過程能夠找到參數和返回值對應的使用點，這里在創建ADFG時，為函數參數和返回值增加了虛擬的定義值.最后，我們使用了100多個單元測試用例測試其健壯性.

為了驗證本文方法的精確度，FlowDroidSP實現了2種模式：剪枝模式和非剪枝模式.剪枝模式(簡稱FlowDroidSP-P)正是利用了具有域敏感和流敏感的變量使用點索引進行剪枝的實現版本.如在4.5節所討論，由于FlowDroid的保守子域處理，導致剪枝的模式會對FlowDroid的精度進行提升，然而這不利于驗證其是否會損失精度.因此，我們實現了非剪枝的模式(簡稱FlowDroidSP-NP)專用于驗證精確度.在非剪枝模式的實現中，我們將4.2節的算法3中所有分支都執行[useSet=∪getUseStmt(*);]規則，即使用其所有域的使用點，不進行剪枝處理.非剪枝算法理論上是和FlowDroid原算法精度完全一致的.

所有實驗所使用的機器的配置是:64核Intel?Xeon?CPU E7-4809(2.0 GHz)和128 GB RAM,為每一個Java虛擬機分配32 GB的內存.同FlowDroid一樣，設置訪問路徑的長度為5.這里所使用的測試集合同第2節中的16個應用程序.使用FlowDroidSP對每一個測試用例獨立運行3次，提取結果并求平均值.

5.1 評測問題

本節我們將試圖利用實驗驗證3個評測問題：

1) 相比FlowDroid，本文的方法是否會損失精度.

2) 預處理階段和獨立更新算法的開銷是多少.

3) FlowDroidSP相比FlowDroid的性能提升效果是多少.

5.2 問題1：精確度驗證

驗證精確度需要使用非剪枝版本.這里的評價標準是產生的結果數目是相同的.表6是Flow-Droid和FlowDroidSP的對比運行結果.表中F-Res列為原FlowDroid產生的結果個數而NP-Res列為非剪枝模式FlowDroidSP產生的結果個數，可見非剪枝版本的FlowDroidSP與FlowDroid產生的結果個數是完全一致的，總共產生341個泄露結果.這進一步驗證了本文的方法相比FlowDroid方法是沒有精度損失的.

5.3 問題2：預處理和更新階段開銷

如表6所示，表中PRE-T列是FlowDroidSP非剪枝模式下的預處理過程的運行時間，其中標號16的程序最高為2.6 s，標號9的程序最低為0.2 s，平均為0.9 s.對于內存開銷(PRE-Mem列)，其中標號16開銷最高為429 MB，標號9開銷最低為11 MB，平均為126 MB.預處理的平均消耗時間占平均總分析時間的百分比小于1%,而內存消耗平均占比為4%.由此可見，預處理的時間和空間開銷是很低的.時間上，相對于分析的平均時間91.1 s，這種開銷幾乎可以忽略不計.預處理開銷低的原因是由于線性復雜度的ADFG構建算法和在此基礎上的過程內的DEF-USE分析.同樣，對于獨立更新階段的時間消耗(表6中SP-T列)，最高時間消耗是4.1 s，最低是0.07 s，平均時間消耗是1.3 s.可見，雖然獨立更新階段算法不是線性復雜度的，但是由于我們首先使用了約束1進行過濾，導致需要獨立更新的數據值已經很少了.為此，本實驗單獨的統計了獨立更新的值(Active-SP)與需要激活但不滿足約束1的值(Active)之間所占百分比的對比，結果如圖11所示.可見，獨立更新部分所占比例是較小的(平均4.2%).

Fig. 10 Comparison on FlowDroid and FlowDoidSP beyond different mode圖10 FlowDroid和FlowDroidSP不同模式下的結果對比

Fig. 11 Proportion diagram of independent updating 圖11 獨立更新計算值占可激活值的比例圖

5.4 問題3：性能提升效果

Fig. 12 Proportion diagram of cutting off date flow facts圖12 具有裁剪標識的數據流占總數比例圖

本節將對打開剪枝優化進行評測，如表6中列P-Time，P-Mem，P-Res為剪枝模式下FlowDroidSP的運行時間、內存消耗和產生泄露的結果數量.最終圖10給出了3種評測模式(原FlowDroid，非剪枝模式，剪枝模式的FlowDroidSP)的在運行時間，內存消耗和產生結果數量的對比柱狀圖.在運行時間上，非剪枝版本平均加速比為4.8倍，在剪枝版本中，平均加速比為18.1倍.非剪枝版本的時間消耗加速比波動范圍正常，最低3.3倍，最高8.6倍.而剪枝版本的加速比波動范圍是非常大的，最低提升4.2倍，最高提升高達54倍，這是一方面由于剪枝方法本質決定，如果在程序傳播初始階段就能夠有效地殺死不該傳播的數據流值，會避免后續污點大量的擴散，另一方面我們猜測剪枝方法的加速比也和程序中保守子域的規模有關，保守子域處理的情況越多，可能剪枝的情況就會越多.為此，我們統計了具有被裁剪標識(當前訪問路徑被裁剪后會得到一個裁剪標識)的數據流的數量，如圖12所示為該數目占當前所有數據流值的比例.對于編號1、編號9、編號13的例子，其所占比例為25%，12.9%，20.9%.所以剪枝優化對其提升比例不高(分別為4.8，4.2，13.9倍).而對于其他例子中該規模是相對較高，例如編號8的比例高達97.4%，所以剪枝算法對其優化的加速比可以高達54倍.對于內存消耗上，在非剪枝模式下，FlowDroidSP降低內存消耗平均為61.5%.在剪枝模式下，FlowDroidSP降低內存消耗平均為76.1%.另外對于產生泄露結果數目的影響，在剪枝模式下，FlowDroidSP是有一定精確度提升的，一共消減了154個誤報結果，占總數的17.7%.

6 相關工作對比

數據流分析是靜態程序分析的經典分析方法，IFDS框架[20]率先將流敏感和上下文敏感的分析問題轉化成圖可達問題進行求解，提高了分析的效率，該算法的最壞時間復雜度是O(ED3)，其中E是當前控制流圖中的邊個數，D是數據流域的大小.文獻[24]在2010年對IFDS進行了效率提升，它利用一種按需的方法對ICFG進行構建，為調用函數和被調用函數建立一個映射關系，當調用退出時只有存在于映射里面的調用者才會為其計算返回值.后來，該方法被實現到開源工具Heros[25]中，FlowDroid正是基于這個版本的IFDS進行實現的.FlowTwist[7]利用了祖先和鄰居的數據結構將數據值之間的傳播關系進行連接，以保證來自不同源的數據流值可以進行合并，增加了分析的擴展性.然而，當前沒有工作探索對IFDS進行稀疏化的支持.同樣，本文的方法本質是修改IFDS的傳播函數，因此也適用于上述2個工作.

針對FlowDroid進行利用以檢測安全問題的工作有很多[4].例如，達姆施塔特大學的安全軟件工程實驗室圍繞了FlowDroid構建了一整套的安全檢測生態系統[26]，這包括使用Susi[27]來提供污點分析所使用的源和匯聚點；使用IccTA[28]提供敏感信息通過組件間進行泄露的檢測方法；使用StubDroid[29]利用FlowDroid對庫函數進行摘要提??；Harvester[30]利用FlowDroid提取關鍵路徑信息，然后動態的驗證這些信息是否是泄露等工作；靜態污點分析的另一大挑戰就是流敏感的別名分析，FlowDroid的流敏感的別名分析最初思想來源于Andromeda[31]，其本質是基于CFL-圖可達問題的變體；Sridharan等人[32]嘗試將對Java的別名分析轉化為CFL-圖可達問題；隨后又在文獻[33]中提出了基于精簡(refine-ment)的優化，然而，基于CFL的Java指針分析都是流不敏感的.為了解決流敏感問題，FlowDroid引入了激活點的方法；Boomerang[34]是最近提出的一個面向Java的按需的別名分析工具，它也是基于IFDS的，可以支持流敏感和上下文敏感.同樣Boomerang也會面臨類似的效率問題，我們認為本文的方法同樣適用于Boomerang來提高其分析效率.

稀疏程序優化方法是目前指針分析領域的重點優化方案.Hardekopf和Lin[10]在2009年首次將流敏感的指針分析應用到百萬行代碼量的程序分析中，提出了半稀疏的流敏感指針分析方法，該方法利用部分SSA(partial SSA)使得本地變量的分析轉移到該表示中，構建了SEG(sparse evaluation graph)進行具體指針分析；隨后Hardekopf[11]又利用了流不敏感的分析做為預處理將其擴展成全稀疏的形式；Lhotak和Chung[13]的SUPT同樣利用全稀疏的SSA表示并提供了強更新(strong update)的支持；Li等人[14]將圖可達的思想引入到值流圖(value flow graph)中進行按需的流敏感的指針分析優化.然而，上述的工作都是針對于C/C++語言進行開展的且這些分析往往需要一定的預處理(SSA或者流不敏感的分析支持).

污點分析技術是一類重要的程序分析技術，如今大量的研究工作應用其解決計算機系統信息的保密性和完整性問題:Mino[35]在硬件級別上擴展了寄存器的標志位來實現污點分析用來進行一些基礎漏洞挖掘，如緩沖區溢出；TAJ[36]工具利用了混合切片的靜態分析技術提供Java Web安全漏洞的檢測；TaintDroid[37]是當前最流行的動態Android應用隱私泄露檢測工具，它使用的多層次的插樁來完成污點傳播.然而，TaintDroid必須在運行時對APK文件進行檢測，這依賴于APK輸入測試集合來觸發敏感數據流，且TaintDroid會對Android系統本身帶來一定開銷，每次Android版本更新之后，Taint-Droid都需要重新進行定制.CHEX[38]嘗試使用靜態的污點分析方法檢測智能手機組件劫持漏洞；DroidSafe[39]結合Android Open Source Project實現了與原Android接口語義等價的分析模型，并使用精確分析存根(accurate analysis stub)將AOSP代碼之外的函數加入到模型，在此基礎上進行污點分析.

7 總結與未來工作

本文針對檢測移動應用隱私泄露問題的污點分析技術進行性能提升.基于稀疏優化的思想，本文將傳統數據流分析框架擴展成稀疏的形式，即將數據流值直接傳播到其使用點，避免其在定義點和使用點之間的無關聯傳播.我們提出了一種特殊的數據結構-變量使用點索引來存儲流敏感和域敏感的DEF-USE關系，并提供快速的構建算法.以此結構為輸入，提供了對應的污點分析技術.另外，本文還發現基于流敏感和域敏感的DEF-USE關系可以對污點分析中保守子域處理的情況進行有效的剪枝，可以同時提升其效率和精度.

最后本文實現了工具FlowDroidSP并進行評測.實驗表明，FlowDroidSP在提升性能的同時沒有帶來精度上的損失.在非剪枝模式下，可以帶來時間加速比4.8倍，內存消耗降低61.5%，在剪枝模式下，可以帶來時間加速比18.1倍，內存消耗降低76.1%，并且消減了17.7%的誤報結果.

由于IFDS框架分配率的限制，當前污點分析還不能支持別名之間的強更新，后續我們將探索如何利用預處理信息提供別名間的強更新.此外，根據5.4節的實驗結果不難得出的結論是當前保守子域問題也是限制污點分析擴展性的瓶頸，盡管稀疏框架可以對其進行優化剪枝，但仍然不能完全消除其誤報，未來對保守子域的精確計算也是一個值得研究的方向.