王 蕾,周 卿,何冬杰,李 煉,馮曉兵

1(計算機體系結(jié)構(gòu)國家重點實驗室(中國科學(xué)院 計算技術(shù)研究所),北京 100190)

2(中國科學(xué)院大學(xué),北京 100190)

隨著移動應(yīng)用的廣泛普及,其安全問題正受到嚴重的挑戰(zhàn).移動支付、電子商務(wù)、社交網(wǎng)絡(luò)等活動中存在著大量的用戶隱私數(shù)據(jù),大量第三方移動應(yīng)用程序的使用導(dǎo)致隱私數(shù)據(jù)難以被有效地保護.例如,印度的一家公司設(shè)計了一組智能手機應(yīng)用開發(fā)工具包SilverPush,它可以嵌入到一個正常的手機應(yīng)用中并在后臺運行,在用戶不知情的情況下收集用戶的隱私數(shù)據(jù)(包括IMEI ID、位置信息、視頻與音頻信息、Web瀏覽記錄等),并將其發(fā)送給廣告推薦商[1].污點分析技術(shù)(taint analysis)[2]是信息流分析技術(shù)(information-flow analysis)[3]的一種實踐方法.該技術(shù)通過對系統(tǒng)中的敏感數(shù)據(jù)進行標記,繼而跟蹤標記數(shù)據(jù)在程序中的傳播,檢測系統(tǒng)安全問題.據(jù)調(diào)查分析[4],在Android應(yīng)用的靜態(tài)安全檢測中,污點分析則是最為流行的分析方案.

污點分析可以有效地檢測Android應(yīng)用的隱私泄露問題.舉例說明,圖1所示為一段Android應(yīng)用程序代碼,運行該段程序會導(dǎo)致用戶的密碼數(shù)據(jù)通過發(fā)送短信的方式泄露.污點分析首先要識別引入敏感數(shù)據(jù)的接口(source,污點源)并進行污點標記.具體到程序中,即識別第 4行的 passwordText接口為污點源,并對pwd變量進行標記.如果被標記的變量又通過程序依賴關(guān)系傳播了給其他變量,那么根據(jù)相關(guān)傳播規(guī)則繼續(xù)標記對應(yīng)的變量.當被標記的變量到達信息泄露的位置(sink,污點匯聚點)時,則根據(jù)對應(yīng)的安全策略進行檢測.圖1中,第 8行帶污點標記的leakedMessage變量可以傳播到發(fā)送信息的sendTextMessage接口,這就意味著密碼數(shù)據(jù)會被該接口泄露.污點分析又分為靜態(tài)和動態(tài)的污點分析.靜態(tài)污點分析是指在不運行代碼的前提下,通過分析程序變量間的數(shù)據(jù)依賴關(guān)系來進行污點分析.相對于動態(tài)運行的污點分析,靜態(tài)污點分析可以在程序發(fā)布之前對應(yīng)用程序安全問題進行檢測,避免了發(fā)布之后造成的安全問題.另外,該技術(shù)具有分析覆蓋率高(不依賴測試集合)、無需程序插樁(而導(dǎo)致的程序運行出現(xiàn)開銷)等優(yōu)勢.

Fig.1 An example of taint analysis圖1 污點分析示例

然而,在檢測 Android應(yīng)用隱私泄露問題時,靜態(tài)污點分析存在結(jié)果誤報率較高的問題.這是由于為了能夠發(fā)現(xiàn)所有潛在的惡意行為,污點分析需要將可能的敏感信息泄露路徑都報告出來,而程序中正常功能也需要選定一些敏感的數(shù)據(jù)傳播到外界.據(jù)統(tǒng)計,MudFlow[5]利用靜態(tài)污點分析工具FlowDroid測試的2 866個良性軟件(benign App)一共產(chǎn)生了338 610條污點分析結(jié)果,檢測人員需要在大量集合中選出具有惡意行為的結(jié)果,這將是效率極低的.利用污點分析解決的隱私泄露問題(提高檢測精度)是當前Android安全的重要研究熱點.一些研究工作[5-8]嘗試使用統(tǒng)計的方法進行惡意行為區(qū)分,例如,MudFlow[5]嘗試對比污點分析結(jié)果和良性軟件結(jié)果的差異,利用 SVM 分類模型檢測出一個軟件是否是惡意軟件.然而,檢測人員常常需要驗證具體的泄露路徑,該工具只能給出一個軟件整體是否具有惡意行為(而且該工具也會存在誤報),無法給出其中一條污點分析路徑[Source→Sink]是否是直接導(dǎo)致隱私泄露的結(jié)果,這驅(qū)使我們嘗試更加有效的分析方案.不同于其他方法,本文選擇了另外一種假設(shè)作為切入點:我們假設(shè)良性軟件和惡意軟件所使用的敏感數(shù)據(jù)流之間的相關(guān)性(綁定發(fā)生特性)是有差異的(我們將在第 5.1節(jié)來驗證該差異確實存在).例如,在良性軟件中,地圖信息和設(shè)備標識信息的驗證往往不在一個模塊中執(zhí)行,而惡意軟件則將設(shè)備信息與定位信息一起(綁定)發(fā)送到網(wǎng)絡(luò).然而,當前研究工作沒有提供有效的多源分析技術(shù).基于上述的分析與假設(shè),本文提出了一種分析污點結(jié)果中多源之間是否綁定發(fā)生的污點分析技術(shù).該技術(shù)可以給出污點分析結(jié)果之間是否可以在一次執(zhí)行中綁定發(fā)生.此外,本文還提出了一種高效的實現(xiàn)方法,使得多次的多源分析開銷很低.隨后,本文將該技術(shù)應(yīng)用到Android應(yīng)用隱私泄露檢測中.

總之,本文的主要貢獻如下.

(1)創(chuàng)新地提出了一種解決多源綁定發(fā)生問題的污點分析技術(shù).該技術(shù)具有上下文敏感、流敏感、域敏感的特性,且可以精確地區(qū)分出分支條件路徑互斥的情況.

(2)提出了一種多源綁定發(fā)生技術(shù)的高效實現(xiàn)方法.該方法將高復(fù)雜度(指數(shù)級別)的多源問題進行近似,并提出了一種按需的多源污點傳播方法.實驗結(jié)果表明,該方法與傳統(tǒng)污點分析相比,開銷僅為19.7%,且多次的多源分析開銷很低(進一步分析的平均時間為0.3s).

(3)實現(xiàn)了原型系統(tǒng)MultiFlow,應(yīng)用其到2 116個良性手機軟件和2 089個惡意手機軟件的隱私泄露檢測中,發(fā)現(xiàn)了良性軟件和惡意軟件的綁定發(fā)生特性有較大的差別,且本文方法和傳統(tǒng)方法對比有較大的精度提升(減少多源對 41.1%).最后,我們還提出了一種污點分析結(jié)果風險評級標準,應(yīng)用評級結(jié)果可以直接提高檢測的效率和精度.

本文第1節(jié)對本文的研究背景進行介紹,包括靜態(tài)污點分析的通用解決方案及Android隱私泄露檢測相關(guān)技術(shù).第 2節(jié)使用實際例子演示本文的研究動機并分析該問題的難點.第 3節(jié)介紹多源綁定發(fā)生的污點分析技術(shù),包括問題定義以及提高精度和效率兩方面的關(guān)鍵技術(shù).第4節(jié)給出具體實驗以驗證多源技術(shù)的開銷.第5節(jié)將該技術(shù)應(yīng)用到實際隱私泄露檢測中.第6節(jié)為相關(guān)工作.第7節(jié)對本文進行總結(jié),并深入討論該技術(shù)潛在的應(yīng)用場景.

1 背景知識

1.1 IFDS框架

一般而言,靜態(tài)污點分析問題都是被轉(zhuǎn)化為數(shù)據(jù)流分析問題[9]進行求解:首先,根據(jù)程序中的函數(shù)調(diào)用關(guān)系構(gòu)建調(diào)用圖(call graph,簡稱 CG);其次,為了提供更細粒度地區(qū)分程序不同執(zhí)行路徑的分析,還需要構(gòu)建控制流圖(control flow graph,簡稱CFG);最后,在過程內(nèi)和過程間,根據(jù)不同的程序特性進行具體的數(shù)據(jù)流傳播分析(與指針分析).在具體實現(xiàn)中,污點分析常常被設(shè)計為一種按需的分析算法:以污點源 source函數(shù)為驅(qū)動源,分析其返回值(污點)在程序中的傳播,直到匯聚點sink函數(shù)為止.

IFDS框架[10]是一個精確高效的上下文敏感和流敏感的數(shù)據(jù)流分析框架,于1996年由Reps等人提出.IFDS的全稱是過程間(interprocedural)、有限的(finite)、滿足分配率的(distributive)、子集合(subset)問題.該問題作用在有限的數(shù)據(jù)流域中,且數(shù)據(jù)值(data flow fact)需要通過并(或交)的集合操作滿足分配率.滿足上述限定的問題都可以利用IFDS算法進行求解(文獻[10]中的Tabulation算法),而污點分析問題正是滿足IFDS問題要求的.污點分析的數(shù)據(jù)流值是污點變量,表示當前污點變量可以到達程序點Stmt.該算法的最壞的時間復(fù)雜度是O(ED3),其中,E是當前控制流圖中的邊個數(shù),D是數(shù)據(jù)流域的大小.

IFDS問題求解算法的核心思想就是將程序分析問題轉(zhuǎn)化為圖可達問題[11].算法的分析過程在一個按照具體問題所構(gòu)造的超圖(exploded supergraph)上進行(如圖2的例子所示),其中,數(shù)據(jù)流值可被表示成圖中的節(jié)點.算法擴展了一個特殊數(shù)據(jù)流值:0值,用于表示空集合;程序分析中轉(zhuǎn)移函數(shù)的計算,即對數(shù)據(jù)流值的傳遞計算,被轉(zhuǎn)化為圖中的邊的求解.為了更好地進行描述,算法根據(jù)程序的特性將分析分解成4種轉(zhuǎn)移函數(shù)(邊).

(1)Call-Flow,即求解函數(shù)調(diào)用(參數(shù)映射)的轉(zhuǎn)移函數(shù).

(2)Return-Flow,即求解函數(shù)返回語句返回值到調(diào)用點的轉(zhuǎn)移函數(shù).

(3)CallToReturn-Flow,即函數(shù)調(diào)用到函數(shù)返回的轉(zhuǎn)移函數(shù).

(4)Normal-Flow,是指除了上述3種函數(shù)處理范圍之外的語句的轉(zhuǎn)移函數(shù).

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

IFDS求解算法Tabulation是一種動態(tài)規(guī)劃的算法,即求解過的子問題的路徑可被重復(fù)地利用.由于其數(shù)據(jù)流值滿足分配率,因此可以在分支或函數(shù)調(diào)用將邊進行合并.求解算法包括了兩類路徑的計算:路徑邊(path edge)和摘要邊(summary edge).

· 路徑邊表示的是過程內(nèi)從起點到當前計算點的可達路徑.

· 摘要邊表示的是函數(shù)調(diào)用到函數(shù)返回的邊,其主要特點是,如果在不同調(diào)用點再次遇到同樣的函數(shù)調(diào)用,可以直接利用其摘要邊信息,從而避免了函數(shù)內(nèi)重復(fù)的路徑邊的計算.

下面以圖2中的例子來演示IFDS算法是如何求解污點分析問題的,其中的數(shù)據(jù)流值表示由污點源傳播來的污點變量.為了簡潔,我們簡寫污點源函數(shù)為source(),泄露點為sink(b),其中,b為泄露變量(下文同理).如第 2行所示,此時將產(chǎn)生一條由0到a的邊.對于第3行的賦值語句[b=a;]和a變量,Normal-flow一般被定義為:如果賦值語句右值是污點變量,那么產(chǎn)生左值為污點變量且保留原值,即產(chǎn)生a→b和a→a的邊.對于第4行的程序函數(shù)調(diào)用,由于b是函數(shù)foo的參數(shù),分析將啟動Call-Flow函數(shù).Call-Flow一般定義為:如果實參為污點變量,就會對應(yīng)產(chǎn)生形參的污點變量,即產(chǎn)生b→x的邊.對于第10行的程序函數(shù)返回點,Return-Flow將產(chǎn)生返回語句的值到調(diào)用點返回值映射的邊,即產(chǎn)生y→c的邊.對于污點匯聚點 sink函數(shù),如果有數(shù)據(jù)流值經(jīng)過該語句,例如圖中的變量c,則表示存在一條路徑從0到達語句sink(c),c為最終觸發(fā)sink的污點變量.對于foo中已經(jīng)計算完成的入口到出口的邊(圖中x→y),分析將其保存為摘要邊,之后,如果程序其他位置用 foo時,則直接利用該摘要邊即可.

1.2 FlowDroid

FlowDroid[12]是當前最流行的開源Android靜態(tài)污點分析工具,目前被廣泛地應(yīng)用于檢測Android隱私泄露和其他Android安全問題.FlowDroid接受待分析的apk文件作為輸入,利用反編譯工具Dexpler和Java分析工具Soot[13]將apk文件轉(zhuǎn)化成Soot中間表示Jimple,隨后在Jimple上進行靜態(tài)的污點分析.其分析的結(jié)果是多個污點源到污點匯聚點(Src→Sink)的集合.FlowDroid提供了完整的 Android函數(shù)調(diào)用圖的構(gòu)建,且提供了高精確度和高效率的污點傳播分析.Android框架中存在大量回調(diào)函數(shù),導(dǎo)致 Android程序的分析存在多入口的問題.FlowDroid嘗試對 Android生命周期函數(shù)進行模擬,迭代地加入預(yù)先分析的入口函數(shù)(異步調(diào)用、回調(diào)函數(shù)等),使用dummyMain和虛擬節(jié)點連接成完整的調(diào)用圖.在污點傳播分析中,FlowDroid正是基于IFDS[10]數(shù)據(jù)流分析框架(提供了面向 Java的 Call-Flow、Return-Flow、CallToReturn-Flow、Normal-Flow的污點傳播轉(zhuǎn)移函數(shù)).FlowDroid同時提出一種按需的后向別名分析方法,使用Access Path來支持域敏感.因此,FlowDroid具有流敏感、上下文敏感、域敏感的高精確度.FlowDroid使用Susi[14]工具來生成在Android隱私泄露應(yīng)用中使用的源和匯聚點;使用手工書寫的摘要來對庫函數(shù)的語義進行模擬(后續(xù)工作提供了 StubDroid[15]來自動生成庫函數(shù)的摘要).FlowDroid的初衷是提供一個敏感度高且高效的污點分析工具,然而其沒有深入探索污點分析檢測Android應(yīng)用隱私泄露的問題.

2 研究動機

正如引言中所述,當前污點分析面臨的一個重要研究問題就是:污點分析結(jié)果無法回答一個應(yīng)用程序是否具有隱私泄露(誤報率高).本節(jié)用一個例子來說明本文的研究動機.我們選擇兩個應(yīng)用程序的程序片段來演示當前污點分析檢測隱私泄露問題的困難,其中,圖3是從Google Play[16]應(yīng)用市場中下載的一個新聞應(yīng)用程序的代碼片段,它是一個沒有隱私泄露行為的應(yīng)用軟件;另一個程序(如圖4所示)是一個從Genome庫[17]中得到的惡意軟件 DroidKungfu的變體.具體分析,新聞應(yīng)用利用了地理位置的信息來提供用戶當?shù)氐奶鞖鉅顩r,圖3左側(cè)是其代碼片段.同時,該應(yīng)用的另一個常用功能就是提供設(shè)備號以便進行網(wǎng)絡(luò)設(shè)備驗證,圖3右側(cè)為其相關(guān)代碼.然而,如圖4所示的惡意軟件片段在一個特殊的回調(diào)函數(shù)OnStartCommand下直接獲取程序的地理位置信息和用戶的設(shè)備號信息,然后傳遞給網(wǎng)絡(luò).它是以盜取用戶敏感信息為目的的.

Fig.3 A code snippet of benign App圖3 良性應(yīng)用軟件代碼片段

Fig.4 A code snippet of malware圖4 惡意軟件代碼片段

我們使用 FlowDroid對兩個應(yīng)用程序進行隱私泄露檢測.由于 FlowDroid只是考慮單一的污點分析結(jié)果,分析上述兩個應(yīng)用程序的結(jié)果都是:{地理信息(getLatitude/getLongitude)發(fā)送到網(wǎng)絡(luò)}和{設(shè)備信息(getDeviceId/getMacAddress)發(fā)送到網(wǎng)絡(luò)}.即便我們嘗試一些統(tǒng)計分析的方法,例如應(yīng)用 MudFlow 中的統(tǒng)計結(jié)果(一種分類器)來區(qū)分,由于兩者的結(jié)果是完全一樣的,分類器也是無法區(qū)分兩者的惡意行為的.因此,單獨地依據(jù)FlowDroid的結(jié)果判斷隱私泄露,會導(dǎo)致該問題檢測的誤報,這促使我們嘗試更加精化的分析方法.

進一步分析我們發(fā)現(xiàn),在新聞應(yīng)用中,由于發(fā)送信息是在不同的模塊下,因此在一次執(zhí)行過程中,必然是只能發(fā)送地理位置信息到網(wǎng)絡(luò)就不會發(fā)送用戶的設(shè)備信息,反之亦然.然而對比惡意軟件,由于地理信息和用戶設(shè)備等信息是惡意軟件同時需要的,因此它們往往是綁定在一起發(fā)送到網(wǎng)絡(luò)的.目前的污點分析只能提供單一的污點源和匯聚點的組合結(jié)果,并沒有考慮多個組合之間的相關(guān)性關(guān)系.出于上述考慮,本研究的目標就是利用多個污點源到污點匯聚點組合的相關(guān)性來降低隱私泄露檢測的誤報率.更進一步來講,我們研究在程序的一次執(zhí)行(一次事件觸發(fā)下)路徑上,多個污點分析組合是否能夠綁定發(fā)生在這一路徑上.我們將該問題命名為多源綁定發(fā)生問題,而提供解決此問題的污點分析稱為多源綁定發(fā)生的污點分析技術(shù).

更加特殊的情況如圖3右側(cè)程序的分支 7和分支 9下,在設(shè)備驗證模塊中,由于某些情況(缺少 SIM 卡),getDeviceId函數(shù)將返回空,這時需要使用設(shè)備的Wifi物理地址(getMacAddress)作為設(shè)備標識.FlowDroid得到的結(jié)果是getDeviceId→NETWORK和getMacAddress→NETWORK.然而在一次執(zhí)行過程中,它們是不可能都被執(zhí)行的,原因是IF分支的真分支和假分支是互斥的情況.由此可見,多源綁定發(fā)生的污點分析技術(shù)需要區(qū)分不同路徑下的分析結(jié)果;其次,雖然在上述例子中沒有出現(xiàn),但分析還需要保證如FlowDroid一樣的精度(上下文敏感、流敏感、域敏感等)以及可用范圍內(nèi)的開銷.這些都給發(fā)掘污點分析結(jié)果之間的相關(guān)性帶來了困難.因此,本研究的關(guān)鍵技術(shù)是提出一種精確高效的多源綁定發(fā)生的污點分析技術(shù).

3 多源綁定發(fā)生的污點分析技術(shù)

3.1 多源綁定發(fā)生問題定義

首先,本文給出了多源綁定發(fā)生問題的形式化描述.

定義1(程序執(zhí)行的軌跡流).在程序的一次執(zhí)行中,從程序入口到程序出口的一系列被執(zhí)行的語句序列P:

其中,Si表示程序執(zhí)行過程中執(zhí)行的指令語句.如果P1是P的子序列,那么P1?P,其含義表示P1出現(xiàn)在P的執(zhí)行過程中.

定義2(污點分析軌跡流).從污點源傳播到污點匯聚點的一系列被執(zhí)行的語句序列F:

如果F?P,則說明一條污點分析軌跡流F出現(xiàn)在程序執(zhí)行P中或程序的一次執(zhí)行P可以觸發(fā)污點分析結(jié)果F.

定義3(多源綁定發(fā)生).令表示一組污點分析軌跡流,那么在一次執(zhí)行軌跡流P中,該組軌跡流能夠綁定發(fā)生,當且僅當滿足如下公式:

我們簡稱多源綁定發(fā)生問題為多源問題.令的大小(即中污點結(jié)果的個數(shù))為k,我們稱大小為k的F的綁定發(fā)生問題為k-多源綁定發(fā)生問題,簡稱k-多源問題.傳統(tǒng)的產(chǎn)生獨立污點結(jié)果的污點分析則是 1-多源問題.

目前,使用靜態(tài)分析解決多源綁定發(fā)生問題具有很大的挑戰(zhàn).

· 首先,由于程序中分支和循環(huán)的存在,程序可能的執(zhí)行路徑數(shù)量會根據(jù)分支的數(shù)量呈指數(shù)級上升.為了完成有效的分析,靜態(tài)(污點)分析常用的方法是在分支交匯處合并數(shù)據(jù)流值,以表示出當前可能發(fā)生的數(shù)據(jù)流值.例如,圖3例子中,分支結(jié)束點第 13行得到的最終數(shù)據(jù)流值包含的源是{getDeviceId,getMacAddress},表示兩個源都可能傳播到網(wǎng)絡(luò).然而,同樣的問題在多源綁定發(fā)生問題中并不適用,因為如果在程序分支處進行合并就無法有效地區(qū)分出不同路徑下的污點傳播.

· 其次,一次污點分析往往會產(chǎn)生多組污點分析結(jié)果,記其個數(shù)為k.對k-多源問題求解的復(fù)雜度會是k的指數(shù)級別(將在后文進行論證),即便我們僅對結(jié)果中的兩對源進行分析(2-多源問題),k對結(jié)果之間兩兩組合的個數(shù)是,此時,我們可能的查詢次數(shù)最多會有次數(shù).如果多源問題的開銷較大的話,多次的查詢會導(dǎo)致系統(tǒng)難以使用.

本文創(chuàng)新地提出了解決上述難點的方法,我們將在第3.2節(jié)介紹多源綁定發(fā)生的污點分析技術(shù)(保證精度),在第3.3節(jié)介紹一種高效的實現(xiàn)方法(保證效率).

3.2 多源綁定發(fā)生的污點分析

正如第 1節(jié)所述,靜態(tài)污點分析的數(shù)據(jù)流值表示的是當前的污點變量可能到達該語句 Stmt.為了能夠保證多源綁定發(fā)生的分析,我們創(chuàng)新地提出了將數(shù)據(jù)流值擴展以污點變量組成的向量的形式,如公式(1)所示.

令v1,v2,…,vn-1,vn為污點變量,其綁定發(fā)生的數(shù)據(jù)流值為

數(shù)據(jù)流值是一個污點變量組成的向量,而整個數(shù)據(jù)流值表示向量中所有的變量在當前的語句 Stmt上是可以綁定到達的.以圖5中的程序為例,如果數(shù)據(jù)流值〈b1,b2〉分別傳播到sink(b1)和sink(b2),則表示污點變量b1和b2的源是可以綁定發(fā)生的.傳統(tǒng)的污點分析方法(如FlowDroid中的方法)正是該方法的一個特例,即數(shù)據(jù)流值為一元向量的情況.

Fig.5 An example of multi-source binding data flow analysis(1)圖5 多源綁定發(fā)生數(shù)據(jù)流傳播示例(1)

上述數(shù)據(jù)流值形式保證其分析可以滿足IFDS問題,從而對該問題的求解可以支持上下文敏感和流敏感的性質(zhì).具體來講,我們提供了IFDS問題的擴展數(shù)據(jù)流方程相關(guān)的轉(zhuǎn)移函數(shù),即Normal-Flow函數(shù)、Call-Flow函數(shù)、Return-Flow函數(shù)、CallToReturn-Flow函數(shù),表1給出了算法詳細的偽代碼.解釋如下:令表示數(shù)據(jù)流值向量,用v表示中對應(yīng)維度的元素,算法重用了傳統(tǒng)的污點分析的轉(zhuǎn)移函數(shù)(簡稱為 solo轉(zhuǎn)移函數(shù),算法中的soloNormal/soloCall/soloReturn/soloCallToReturn函數(shù))用來表示對單一的v的污點變量獨立的傳播規(guī)則.由于solo轉(zhuǎn)移函數(shù)已經(jīng)在文獻[18]中提供,這里省略.在 Normal-Flow函數(shù)中,對中的每一維度v進行遍歷,如果v在當前語句n的計算,即Normal(v,n)的結(jié)果為soloRes集合,那么對于soloRes中每一個元素t,用t替換原中v生成新值,即.replace(v,t)來表示保證其他維度不變用新值t替換v生成新值.例如在圖5右側(cè)的傳播:對于語句[b1=a1;],數(shù)據(jù)流值〈a1,a2〉中的a1 會根據(jù) soloNormal函數(shù)產(chǎn)生a1 和b1,所以最終的函數(shù)會生成〈a1,a2〉和〈b1,a2〉.在 Call-Flow 函數(shù)中,需要對v中所有在函數(shù)調(diào)用中使用的變量都進行污點傳播;對中每一維度元素,查找其是否在函數(shù)調(diào)用中使用,如果有使用,則用soloCall生成的新值進行替換.Return函數(shù)與Call函數(shù)類似,只是將參數(shù)映射轉(zhuǎn)化為返回值的映射.CallToReturn與Normal類似,一種特殊的CallToReturn函數(shù)是對污點源和匯聚點的處理函數(shù),例如,〈0,0〉表示IFDS框架的初始值(0值),污點源source1和source2為兩個不同的源.對于污點源的計算,算法將從0產(chǎn)生對應(yīng)位置的污點變量,如語句[inta1=source1();]將從〈0,0〉產(chǎn)生〈a1,0〉.算法的初始輸入是待分析的多個源的集合,而其他不在這個集合的污點源并不會進行分析.圖5右側(cè)演示了左側(cè)程序的傳播過程.可見,算法能夠有效地生成〈b1,b2〉向量,也就是之后可以綁定地觸發(fā)sink(b1)和sink(b2)的污點變量.

Table 1 Data flow transfer functions of multi-source binding analysis表1 多源綁定發(fā)生的數(shù)據(jù)流轉(zhuǎn)移函數(shù)

該方法的主要特點就是能夠區(qū)分出分支(IF)互斥的路徑中污點變量的傳播,如圖6所示程序為例,source1()源的污點變量c1的傳播路徑是source1→a1→b1→c1.其中,如果變量無法傳遞到中間變量b1,自然無法傳遞到c1.如果考慮到分支的情況,分支Brb1和Brc1控制了污點源source1()進行傳遞的變量b1和c1,而分支Brb2和Brc2則控制對source2()傳播的b2和c2.不難發(fā)現(xiàn),Brb1和Brb2是互斥的.這會導(dǎo)致a1污點傳播到b1而a2就不會傳播到b2,反之亦然.所以對于可以觸發(fā)sink(b1)的b1和觸發(fā)sink(b2)的b2對應(yīng)的源是不能綁定發(fā)生的.我們的方法可以有效地區(qū)分出此類情況.如圖6右側(cè)的具體數(shù)據(jù)流傳遞所示,傳播算法可以正確地區(qū)分出具有互斥關(guān)系的分支.由最后的結(jié)果可見:結(jié)果向量集合中不會存在具有互斥(不會再一次執(zhí)行中綁定發(fā)生)的污點變量,〈b1,b2〉,〈c1,c2〉,〈b1,c2〉,〈c1,b2〉是不會出現(xiàn)在結(jié)果中的.

Fig.6 An example of multi-source binding data flow analysis(2)圖6 多源綁定發(fā)生數(shù)據(jù)流傳播示例(2)

此外,我們還擴展了一個特殊的污點變量:END值(如圖5所示),END(S)表示從S的源出發(fā)的污點變量已經(jīng)流到sink().這是出于考慮:有些情況雖然一個源已經(jīng)被sink觸發(fā)了,但是為了整體的分析,還需要繼續(xù)告知其他源該源已經(jīng)發(fā)生的信息.例如圖7的情況,源src1和源src2是可以同時發(fā)生的,但是在src1的污點變量還未能到達sink1()時,src2的污點變量就已經(jīng)傳播到sink2,且在func1內(nèi)部完成了該傳播.通過使用END數(shù)據(jù)流,可以有效地解決該問題,即在sink2之后,在src2源對應(yīng)維度增加END變量繼續(xù)傳遞.END值不同于觸發(fā)sink但又可以繼續(xù)傳播的污點變量,因為END是可以跨越過程的.

Fig.7 An example of multi-source binding data flow analysis(3)圖7 多源綁定發(fā)生數(shù)據(jù)流傳播示例(3)

3.3 多源問題的高效實現(xiàn)方法

由于IFDS求解算法的最壞時間復(fù)雜度是O(ED3),算法的效率與數(shù)據(jù)流域D的大小(即數(shù)據(jù)流值的個數(shù))有直接關(guān)系.我們令傳統(tǒng)方法(1-多源問題)的污點變量個數(shù)是Dsolo,多源問題中源的個數(shù)(向量維度)是k,那么最壞情況,代入得知,整個問題的復(fù)雜度是.由此可見,多源綁定發(fā)生問題算法的復(fù)雜度是k指數(shù)級別的.

為了能夠高效地實現(xiàn)多源問題的分析,我們將該問題近似為:將k-多源問題轉(zhuǎn)化為次的 2-多源問題求解.具體來講,令k-多源問題中的所有源進行兩兩組合形成的集合為S,如果S中所有的2-多源問題都能滿足(綁定發(fā)生),我們就近似認為k-多源問題能夠滿足.例如,對于結(jié)果為{getDeviceId,getMacAddr,getLineNum}的 3-多源問題,需要保證{getDeviceId,getMacAddr}、{getDeviceId,getLineNum}和{getLineNum,getMacAddr}這 3個 2-多源問題都滿足.我們提出上述近似方法的原因是:首先,如果k-多源問題滿足,那么S中的2-多源問題是一定都滿足的(充分條件),所以該近似不會產(chǎn)生漏報.雖然反之不成立(不滿足必要條件),即會產(chǎn)生誤報,但是我們認為在隱私泄露檢測問題中,k-多源問題綁定發(fā)生和其所有兩兩組合的 2-多源綁定都發(fā)生的危害是相近的.同時,我們在實驗中發(fā)現(xiàn),一般能夠滿足上述近似的k-多源問題,實際上有很大概率是完全滿足k-多源綁定發(fā)生的,誤報率很低.我們將在實驗部分進一步闡述相關(guān)驗證.

上述的近似方法導(dǎo)致數(shù)據(jù)流域個數(shù)D的值降低為,算法的時間復(fù)雜度是.一般情況下,污點源的個數(shù)k的值并不會太大,且為了保證完整的分析結(jié)果,控制流的邊的個數(shù)往往不變,因此,k2×E的數(shù)量往往無法被降低,此時,減少Dsolo的個數(shù)將是本技術(shù)提高效率的關(guān)鍵.本節(jié)將提供一種減少Dsolo的個數(shù)的高效實現(xiàn)方法.

由于污點分析的本質(zhì)是一個按需的分析問題,即污點傳播只在污點源到匯聚點之間的路徑傳播,直觀上,污點分析應(yīng)該只針對該路徑進行分析即可.傳統(tǒng)的污點分析在未遇到污點匯聚點時并不知道最終的傳播路徑,因此需要保守地傳播所有污點傳播的變量.當擴展到多源綁定發(fā)生問題時,這種方法將產(chǎn)生大量的無用傳播.如圖8中的例子所示.來自source1的返回值a1會在第3行傳遞給f1、在第4行傳遞給t1,t1會在第11行傳遞給t2,t2在第12行觸發(fā) sink.這條完整的路徑為a1→t1→t2→sink,在圖8右側(cè)路徑中的紅色節(jié)點即為該傳播路徑.然而對于f1來講,他可以傳遞給f2、b、f3變量,但這些變量并不會觸發(fā)sink,如圖8右圖中白色節(jié)點之間的路徑.然而在多源綁定問題分析時,即與source2的返回值a2形成向量,會根據(jù)上節(jié)的算法生成〈f2,a2〉,〈b,a2〉,〈f3,a2〉的值.同理,這些值也不會到達sink進行觸發(fā).可見,這些值的傳播實際上是沒有意義的.當a2進一步在程序中傳播時,則會帶來更多的無用數(shù)據(jù)流值.基于上述觀察,本節(jié)方法的核心思想就是消減這些無用的數(shù)據(jù)流值,只在可以觸發(fā)sink的路徑上進行多源分析,即在圖中只傳播紅色節(jié)點變量(對于source1)和藍色節(jié)點變量(對于source2).

為了維護污點源和匯聚點的路徑信息,我們需要利用一種重要的數(shù)據(jù)結(jié)構(gòu)[19]——數(shù)據(jù)流值的前驅(qū)節(jié)點(predecessor)和鄰居節(jié)點(neighbor).所謂一個數(shù)據(jù)流值的前驅(qū)節(jié)點,是指直接生成該節(jié)點的數(shù)據(jù)流值.例如,圖8中,數(shù)據(jù)流值t1的前驅(qū)節(jié)點是a1.數(shù)據(jù)流值的鄰居節(jié)點是指,如果兩個數(shù)據(jù)流值可在分支(循環(huán))出口進行合并(merge),但它們分別來自不同分支,那么它們之間互為鄰居關(guān)系.例如圖8中第6行處的分支,第7行和第9行都會產(chǎn)生數(shù)據(jù)流值b.為了區(qū)分不同分支的值,令第7行處為b′,第9行處為b,那么在分支結(jié)束處會將b的鄰居節(jié)點設(shè)置成b′.為了維護正確的污點分析路徑,鄰居信息是不可以被省略的,b′的前驅(qū)是f1,b的前驅(qū)是f2,它們分別代表不同的路徑.有了上述的數(shù)據(jù)結(jié)構(gòu),就可以利用觸發(fā)sink的變量進行回溯,求得完整的污點分析路徑,進而在多源分析中重用.另外,為了在多源分析中使用這些路徑信息,我們還需為數(shù)據(jù)流值擴展一個結(jié)構(gòu)用于存儲由〈useStmt,nextDatafact〉組成的集合.useStmt表示當前數(shù)據(jù)流值將要被使用的位置;nextDatafact表示在useStmt處產(chǎn)生的新數(shù)據(jù)流值.例如,t1在第11行生成t2,那么useStmt為line11,nextDatafact是t2.

Fig.8 Efficient implementation method and data flow’s predecessor and neighbor圖8 高效實現(xiàn)方法以及數(shù)據(jù)流值前驅(qū)和鄰居示例

基于上述結(jié)構(gòu),多源綁定發(fā)生的高效實現(xiàn)方法具體流程如下.

(1)運行傳統(tǒng)(1-多源問題)的污點分析,并通過FlowTwist[19]中的算法將數(shù)據(jù)流值的前驅(qū)和鄰居進行記錄;并得到觸發(fā)sink的污點數(shù)據(jù)流值集合sinkSet.我們記該過程為SoloFlow.

(2)將sinkSet中的值加入工作集中;對于工作集中的數(shù)據(jù)流值D,得到D的前驅(qū)pred(通過getPredecessor方法),將D和產(chǎn)生D值的位置語句(通過getCurrentStmt得到)記錄到pred中的〈useStmt,nextDatafact〉集合域中(使用方法SetUseStmt()).將D的neigh和pred加入工作集,迭代地對工作集中的數(shù)據(jù)流值遍歷直到結(jié)束.具體算法如算法1所示.我們記該過程為PreProcess.

(3)執(zhí)行多源綁定的污點分析:由于每一個數(shù)據(jù)流值已經(jīng)在 PreProcess過程中記錄了其后繼的產(chǎn)生位置useStmt和后繼的值nextDatafact,我們修改原Solo轉(zhuǎn)移函數(shù)為只有在useStmt的位置產(chǎn)生新的數(shù)據(jù)流值nextDatafact即可.記該過程為MultiFlow.

算法1.PreProcess過程算法.

輸入:sinkSet.

輸出:sourceSet.

舉例說明,對于a1 變量,經(jīng)過 PreProcess 過程之后,a1 中〈useStmt,nextDatafact〉域的值是〈line4,t1〉.因此,該變量只在第4行處生成t1而不會在第3行處生成f1.同理,t1也只會在第11行處產(chǎn)生t2.如圖8右側(cè)紅色部分是source1的傳播路徑,而白色部分則不會計算.可見,該方法可將大量的無用變量的傳播進行消除,而對于過程間的數(shù)據(jù)流值,效率提高的效果將更加明顯.此外,我們還利用了SoloFlow階段產(chǎn)生的摘要邊信息應(yīng)用到上述方法進行優(yōu)化,即當只有一個維度的污點變量被函數(shù)調(diào)用使用,并且當前該調(diào)用已經(jīng)具有該值得摘要邊時,我們直接使用其摘要信息產(chǎn)生其函數(shù)返回值.摘要邊也是在SoloFlow中自然產(chǎn)生的,因此不會引入額外的開銷.

上述方法的主要特點是:我們只需要執(zhí)行 1次污點傳播以及回溯地完成路徑信息的記錄(soloFlow和PreProcess過程),但是可以執(zhí)行多次的多源綁定發(fā)生(MultiFlow過程)的分析.所以,對于一次污點分析的結(jié)果進行n次的綁定發(fā)生分析,其時間為T=time(SoloFlow)+time(PreProcess)+n×time(MultiFlow).對于一個k-多源問題,其近似計算方法的時間是.

4 實 驗

4.1 實 現(xiàn)

為了驗證本文技術(shù)的有效性,我們實現(xiàn)了一個原型系統(tǒng) MultiFlow.MultiFlow的實現(xiàn)是基于 Soot和FlowDroid的:重用了FlowDroid面向Android特性構(gòu)建的函數(shù)調(diào)用圖,使用訪問路徑(access path)來保證域敏感的分析,在Soot的中間表示Jimple上完成多源污點分析.MultiFlow重用了FlowDroid的后向傳播求解的別名分析,將一個污點變量別名的數(shù)據(jù)流值的前驅(qū)設(shè)置成該變量的前驅(qū).由于Android系統(tǒng)是事件驅(qū)動的,MultiFlow設(shè)置一次多源綁定分析的結(jié)束為一次回調(diào)函數(shù)的結(jié)束.

在下文的所有實驗以及第5節(jié)的應(yīng)用中,我們統(tǒng)一使用表2所示的污點源和匯聚點.

Table 2 Sources and sinks in MultiFlow provided by Susi表2 MultiFlow使用的Susi提供的源和匯聚點

表2所示的污點源和匯聚點由SuSi工具提供,由于排版受限,我們將源和匯聚點縮寫成其函數(shù)名和方法名的形式,省略了參數(shù)和返回值類型,完整的名字請參考https://blogs.uni-paderborn.de/sse/tools/susi/.

4.2 效 率

本節(jié)將驗證多源綁定技術(shù)的效率.本文的技術(shù)為傳統(tǒng)污點分析技術(shù)精度的提升提供了可能,但是該技術(shù)也會引入開銷的增加.因此,該實驗的目的就是驗證多源綁定發(fā)生技術(shù)與傳統(tǒng)技術(shù)相比有多少開銷.實驗對比對象是傳統(tǒng)的污點分析,此處我們使用FlowDroid的污點分析階段.實驗機器的配置是:64核Intel(R)Xeon(R)CPU E7-4809(2.0GHz)和128G RAM,為每一個Java虛擬機分配32G的內(nèi)存.我們隨機地從Google Play應(yīng)用市場下載驗證程序,并盡量選擇其中可運行規(guī)模較大的程序.這里,我們選擇 IFDS邊的個數(shù)作為計算規(guī)模的衡量標準,最終的驗證程序包含16個Android應(yīng)用程序.由于我們將k-多源問題轉(zhuǎn)化為2-多源問題,我們將驗證多次的2-多源問題.此時,我們在1-多源問題(SoloFlow階段)的結(jié)果中兩兩組合形成的集合中隨機選擇10對組合進行2-多源問題計算(如果少于10次,則將所有源進行兩兩組合計算).我們對驗證集合的程序運行3次,隨后記錄其執(zhí)行時間的平均值,表3是相關(guān)的實驗結(jié)果.

Table 3 Time overhead of multi-source binding taint analysis technique表3 多源綁定發(fā)生污點分析技術(shù)的時間開銷

由實驗結(jié)果得出,我們的方法與傳統(tǒng)方法相比不會有較大開銷.此外,由于通常多源分析會進行多次MultiFlow階段的查詢,我們驗證了多源問題高效實現(xiàn)方法的各個階段時間所占比例.如圖9所示,由于SoloFlow階段的時間即為1-多源問題的時間,所以我們的主要開銷是time(PreProcess)+n×time(2-MultiFlow).

Fig.9 Percentage of each phase of the efficient implementation method圖9 高效實現(xiàn)方法的各個階段所占比例

從圖9中可以發(fā)現(xiàn),2-MultiFlow所用時間所占比例僅為1%(平均0.3s).這正說明了多源高效實現(xiàn)方法的有效性.因此,我們的開銷主要消耗在 PreProcess階段.也就是說,進一步對 2-MultiFlow進行多次查詢對系統(tǒng)的查詢開銷影響并不大.綜合統(tǒng)計,本文技術(shù)的平均時間開銷(PreProcess階段開銷)為19.7%,這在靜態(tài)分析中往往是可以接受的.

4.3k-多源問題近似方法驗證

本節(jié)將驗證將k-多源問題轉(zhuǎn)化為次的2-多源問題的可行性.由于此方法并不會產(chǎn)生漏報,而可能產(chǎn)生誤報,我們這里主要驗證其誤報率的大小,也就是說,驗證次 2-多源問題滿足的條件下,k-多源問題的滿足情況.這里,我們選擇在惡意軟件庫中挑選程序進行驗證.我們在Genome庫[17]中隨機挑選50個具有隱私泄露問題的程序,利用 MultiFlow對其所有的污點分析結(jié)果兩兩配對進行 2-多源問題分析.我們使用反編譯工具將其轉(zhuǎn)化為可讀的中間表示代碼,對其結(jié)果進行人工驗證.我們發(fā)現(xiàn),這 50個程序中,所有通過近似方法滿足的k-多源問題就是k-多源綁定發(fā)生的.進一步分析,如果近似方法不滿足,則說明具有多個2-多源問題分別出現(xiàn)在了不同的分支下,如圖10 所示的分支,多源對〈src1,src2〉,〈src1,src3〉,〈src2,src3〉分別出現(xiàn)在不同的分支下,而我們選擇的這50個例子是沒有這種復(fù)雜情況的.這也充分地驗證了k-多源問題近似方法的可行性.

Fig.10 An example of thek-multi approximation method violation圖10k-多源問題近似方法違反示例

5 Android應(yīng)用隱私泄露檢測應(yīng)用

本節(jié)我們將探索多源技術(shù)在 Android應(yīng)用隱私泄露檢測中的應(yīng)用.首先,本節(jié)驗證了當前良性軟件和惡意軟件在多源綁定發(fā)生特性上的差異,從而提供區(qū)分惡意行為的依據(jù);其次,本節(jié)驗證多源技術(shù)相比簡單方法的精確度提升;最后,本節(jié)提出了一種污點分析結(jié)果風險評級方法,檢測人員即可從結(jié)果中惡意行為級別由高到低地進行檢測,從而縮小了檢測范圍,提高了分析的效率.

5.1 良性軟件和惡意軟件多源綁定發(fā)生特性差異

本節(jié)將驗證文章開始部分提出的假設(shè):良性軟件和惡意軟件的多源綁定特性具有較大差異,從而可以利用其提高檢測精度.實驗使用統(tǒng)計方法進行驗證,選擇具有較大數(shù)量的良性軟件庫和惡意軟件庫作為驗證集合.我們在應(yīng)用市場中隨機選擇了2 116個程序作為良性軟件庫測試集合,其中,1 148個來源于Google play應(yīng)用市場[16],968個來源于安智網(wǎng)應(yīng)用市場[20].另外選擇了 2 089個程序作為惡意軟件庫集合,其中,1 089個來自Genome庫[17],1 000個來自 VirusShare庫[21].最后,使用 MultiFlow 對這些軟件進行多源綁定的分析,將所有SoloFlow階段產(chǎn)生的結(jié)果之間的所有組合進行了分析,如果兩個源可以綁定發(fā)生,我們就停止對這兩個源(其他調(diào)用點)進行分析.

在良性軟件庫運行結(jié)果中,337個(占15.9%)應(yīng)用程序(由于超時、反編譯錯誤等問題)無法正常分析,443個(占20.9%)程序產(chǎn)生小于2條污點分析結(jié)果(綁定發(fā)生至少需要2個源).我們將這兩類程序去除,最終可以進行綁定發(fā)生分析的集合包括1 336個應(yīng)用程序,其中有382個(占能多源分析的28.6%)應(yīng)用程序沒有綁定發(fā)生的污點分析結(jié)果(雖然有大于1條的傳統(tǒng)污點分析結(jié)果,但都不是綁定發(fā)生的).對剩下的具有綁定發(fā)生結(jié)果的954個應(yīng)用程序進行統(tǒng)計分析,實驗使用 Apriori算法[22]抽取頻繁項集,其中,選擇最小支持度(support)為 10%,即多源組合中出現(xiàn)次數(shù)大于整個集合的 10%(95個)的多源組合.最后統(tǒng)計結(jié)果按照支持度進行排序,見表4.在惡意軟件庫運行結(jié)果中,除去103個(占4.9%)應(yīng)用程序無法正常分析和711個(占34%)程序產(chǎn)生小于2條的污點分析結(jié)果(惡意軟庫中還包含很多非隱私泄露問題的惡意問題[17],這種情況并不會產(chǎn)生污點分析結(jié)果),最終可以進行綁定分析的集合有1 275個.另外發(fā)現(xiàn)有237個(占能多源分析的18.7%)應(yīng)用程序沒有綁定發(fā)生的污點分析結(jié)果.最后對剩下的產(chǎn)生結(jié)果的1 038個應(yīng)用程序進行統(tǒng)計分析,同樣使用Apriori算法抽取頻繁項集(最小支持度 10%),統(tǒng)計結(jié)果見表5.同時,我們還對比良性軟件庫中使用頻繁的組合在惡意軟件庫中所占的比例(反之亦然),結(jié)果為表4和表5的最后一列.

從表中的結(jié)果可以發(fā)現(xiàn),惡意軟件和良性軟件在多源綁定發(fā)生特性上具有明顯的差異.具體來講:

· 首先,在使用頻繁度上,良性軟件和惡意軟件的統(tǒng)計結(jié)果差別很大.良性軟件統(tǒng)計結(jié)果包含 16個組合,且其中有8個組合出現(xiàn)在惡意軟件統(tǒng)計結(jié)果中;但惡意軟件統(tǒng)計結(jié)果產(chǎn)生了38個組合,而只有6個組合也出現(xiàn)在良性軟件的統(tǒng)計結(jié)果中.針對排名次序差異的比較結(jié)果更為明顯,良性軟件結(jié)果中出現(xiàn)頻率最多的是{getLongitude,getLatitude}(47%),其次是{getDeviceId,getLongitude/getLongitude}(39%)和{getDeviceId,(java.net.URL)openConnection}(34%),這也說明了良性軟件使用的都是用戶常用的功能,即地理信息(經(jīng)度/緯度)、地理信息和設(shè)備號、設(shè)備號和網(wǎng)絡(luò)輸入信息.我們發(fā)現(xiàn),這些信息在惡意軟件統(tǒng)計結(jié)果中也會出現(xiàn),這充分說明了當前惡意軟件經(jīng)常需要偽裝成一個正常的軟件,所以同樣會使用這些常用的功能組合.然而對比惡意軟件結(jié)果,{getDeviceId,getSubscriberId}出現(xiàn)的次數(shù)是最多的(43%),而該對組合在良性結(jié)果中僅占 0.4%(4個),這反映出良性軟件往往不需要 getDeviceId和getSubscriberId綁定發(fā)生,而惡意軟件則出于盜取更多設(shè)備信息的目的將兩者綁定發(fā)送.表5中的大部分組合都是此類的信息,它們是組合1、組合5、組合6、組合9、組合10、組合12～組合38,一共32組,它們出現(xiàn)在良性軟件中的概率最大僅為2.5%.

· 其次,我們發(fā)現(xiàn),惡意軟件結(jié)果平均每個組合中源的個數(shù)更多,良性軟件結(jié)果中只有組合5和組合10包含3個源(這里,getLongitude、getLatitude被視為1個源).而在惡意軟件結(jié)果中,有18個組合包含3組以上的源,有5個組合包含4個以上的源,更特殊地,組合36包含了5個源,這也充分說明了惡意軟件是需要更多的信息來完成惡意行為的.

· 最后,針對某些源,兩個庫之間的配對差異也很明顯.例如,在惡意軟件庫中,對于(ContentResolver)query主要和getDeviceId綁定發(fā)生,(ContentResolver)query出現(xiàn)時,getDeviceId綁定發(fā)生概率為95%.而在良性軟件庫中,(ContentResolver)query經(jīng)常和(database.Cursor)getString(數(shù)據(jù)庫查詢)源綁定出現(xiàn),(database.Cursor)getString出現(xiàn)概率為 99%.這也說明惡意軟件經(jīng)常是發(fā)送用戶賬戶信息結(jié)合設(shè)備信息來完成用戶賬戶信息的盜取,而良性軟件則是正常的數(shù)據(jù)庫功能.

Table 4 High frequency results in benign App set表4 良性應(yīng)用軟件測試集合中出現(xiàn)頻率高的結(jié)果

Table 5 High frequency results in malicious App set表5 惡意軟件測試集合中出現(xiàn)頻率高的結(jié)果

5.2 Android應(yīng)用隱私泄露檢測的精確度提升驗證

本節(jié)所驗證精確度的衡量標準是對良性軟件的檢查結(jié)果中 2-多源對的個數(shù),2-多源對個數(shù)越少,該工具的精確度就越高.之所以使用良性軟件的結(jié)果,是因為工具報告的良性軟件中的污點路徑并不是以隱私泄露竊取為目的的,在隱私泄露檢測上,該工具產(chǎn)生了誤報.當分析多源問題結(jié)果時,用戶必須手工驗證每個多源對結(jié)果是否是真實的泄露.多源對的數(shù)目越少,用戶所檢測的范圍就越小,說明檢測工具的誤報就越少.而且當前沒有準確標注惡意軟件中污點分析路徑的惡意行為的基準集合(benchmark),而良性軟件中的路徑是非惡意行為則是一個確定的事實.我們會在下一節(jié)介紹風險評級方法用以提高人工檢測惡意軟件中惡意行為路徑效率的方法.

基于上述標準,我們統(tǒng)計了第5.1節(jié)中能夠產(chǎn)生大于1條污點分析結(jié)果的良性軟件,一共1 336個.分別使用MultiFlow和FlowDroid分析其產(chǎn)生的結(jié)果數(shù)目,對比圖如圖11所示.對于不考慮多源(圖11中SOLO列)的情況,即將 FlowDroid中所有的源進行統(tǒng)計(這里,我們假設(shè)同一個源出現(xiàn)多個調(diào)用點等同于用出現(xiàn)一次源),此時FlowDroid得到3 935個源.此時,MultiFlow會產(chǎn)生3 472個2-多源對,其中,一共有2 827個非重復(fù)的源.對于多源的情況,由于當前 FlowDroid沒有多源分析的功能,我們假設(shè)其產(chǎn)生的結(jié)果中所有源的兩兩組合等同于 2-多源分析的結(jié)果,此時,FlowDroid產(chǎn)生了5 890個2-多源的對,對比MultiFlow產(chǎn)生的3 472個對,可見MultiFlow與FlowDroid相比在多源計算減少了2 418個2-多源對,提升了41.1%的精度.

Fig.11 Result number comparision of MultiFlow and FlowDroid on multi-source analysis圖11 MultiFlow和FlowDroid多源結(jié)果數(shù)量對比

5.3 污點分析結(jié)果風險評級

對污點分析的結(jié)果進行風險評級具有較大的意義.當前的工具[5-8]不能保證 100%檢測精度的惡意軟件分類,這難免使得檢測人員需要手工地檢查每一條污點分析結(jié)果.即便上述工具可以精確報告該軟件具有惡意行為,檢測人員也可能想知道具體是哪條路徑泄露的信息,或產(chǎn)生什么類型的泄露行為等.如果對污點分析結(jié)果進行評級,程序員就可以從危害級別較高的組合到級別較低的組合分別進行檢測,一旦確定高危險度的路徑是惡意路徑則不必繼續(xù)分析,這使得待分析的范圍縮小而提高了檢測的效率.由于第 5.1節(jié)的實驗證實了多源特性在惡意和良性軟件間的差異,本節(jié)嘗試利用該特性對污點分析結(jié)果進行風險評級.

本文的風險評級規(guī)則建立在3個啟發(fā)式規(guī)則上.

啟發(fā)式規(guī)則 1.如果一個污點源不與其他任何的源綁定發(fā)生,我們則認為該源的污點分析路徑幾乎沒有惡意行為.我們相信,惡意軟件在盜取了用戶的敏感數(shù)據(jù)之后是需要進行惡意行為的,然而單獨地盜取一種敏感數(shù)據(jù)往往是沒有意義的,例如只盜取用戶的密碼信息而不知道用戶名等.而對于良性軟件來講,它們往往針對一類固定的信息進行正常使用,例如手機設(shè)備號驗證或者單一的物理地址使用等.

啟發(fā)式規(guī)則 2.在大量的良性軟件分析中,如果某些源的組合經(jīng)常綁定發(fā)生,那么很可能這些組合是良性的.例如,地理信息中,經(jīng)度信息往往和緯度信息綁定發(fā)生,如果只有經(jīng)度和緯度的綁定發(fā)生,則認為其只是獲取地理信息這一單一的行為.

啟發(fā)式規(guī)則 3.在大量的數(shù)據(jù)分析中,如果某些多源組合經(jīng)常出現(xiàn)在惡意軟件中,卻很少出現(xiàn)在良性軟件中,那么這些多源組合的綁定發(fā)生是具有惡意性的.在表5中,一些組合正好滿足這樣的特性.例如組合 18和組合22,它們出現(xiàn)在惡意結(jié)果中的頻率分別為15%和14%,然而在良性軟件統(tǒng)計結(jié)果中出現(xiàn)次數(shù)為0.這也說明了在上一節(jié)的庫中,只要包含組合18和組合22的都是惡意軟件,而產(chǎn)生泄露的信息正是組合18和組合22.

基于此,我們將污點分析的組合分成4類級別,由高到低依次是級別IV、級別III、級別II、級別I.其中,級別IV是最嚴重的危險級別,其組合是根據(jù)規(guī)則3產(chǎn)生的,在本應(yīng)用中,我們使用表5中的組合1、組合5、組合6、組合9、組合10、組合12～組合38作為級別IV的組合,這些組合出現(xiàn)在惡意結(jié)果中的頻率高于10%,但是出現(xiàn)在良性結(jié)果中的頻率低于2.5%.級別II的組合是由規(guī)則2產(chǎn)生的,在本應(yīng)用中我們認為,如果一個應(yīng)用程序產(chǎn)生的多源組合集合中只出現(xiàn)在表4,那么這些組合的危險度一般不高.級別I的組合是由規(guī)則1產(chǎn)生的,如果一個污點源不與其他任何的源綁定發(fā)生,則是級別I.最后,如果組合不是上述3種級別,則認為它是級別III.

進一步地,我們將上述的評級規(guī)則對實際手機軟件進行應(yīng)用,驗證該規(guī)則是否可以有效地區(qū)分出不同類別的軟件及其污點分析結(jié)果.我們直接將軟件中包含的評級規(guī)則最高的級別作為其標簽,利用其標簽將所有驗證集合的軟件進行分類.我們的驗證集合是第5.1節(jié)中所有能夠產(chǎn)生1條以上污點結(jié)果的軟件,其中包含1 336個良性軟件和1 275個惡意軟件.如果使用表5中的組合1、組合5、組合6、組合9、組合10、組合12～組合38對集合中軟件進行檢測,可以直接檢測出685個具有級別IV組合的軟件.使用規(guī)則2可以檢測出953個包含級別II及其以下級別組合的軟件.使用規(guī)則1可以檢測出621個只包含級別I污點分析結(jié)果的軟件,剩下的352個軟件是包含級別 III及其以下級別組合的軟件.圖12為該結(jié)果的分布圖,可見,包含級別 IV組合的軟件占有26%,這也說明了我們的方法可以直接給出占較大規(guī)模的惡意結(jié)果(占實際惡意軟件的66%),檢測人員可以直接識別出26%個惡意軟件中的具體泄露路徑而不必分析其他路徑.而級別II和級別I的結(jié)果分別占37%和24%,由此可見,該方法可以直接篩選出超過大半的良性的軟件,一般情況下,此類軟件的檢測優(yōu)先級較低.而對于包含級別III及其以下危險的軟件只包含13%,且檢測人員可以優(yōu)先檢查具有級別II的污點路徑.上述的應(yīng)用數(shù)據(jù)也直接說明了使用該評級標準可以區(qū)分出不同級別的軟件,間接地幫助檢測人員提高檢測效率和精度.

Fig.12 Distribution of App’s taint result risk ranking圖12 污點結(jié)果評級分布

6 相關(guān)工作對比

污點分析技術(shù)是一類重要的程序分析技術(shù),如今,大量的研究工作應(yīng)用其解決計算機系統(tǒng)信息的保密性和完整性問題.Mino[23]在硬件級別上擴展了寄存器的標志位來實現(xiàn)污點分析,以進行一些基礎(chǔ)漏洞挖掘,如緩沖區(qū)溢出.Privacy Scope[24]、Dytan[25]利用插樁工具 Pin[26]實現(xiàn)了針對 x86程序的動態(tài)污點分析.TAJ[27]工具利用混合切片的污點分析提供Java Web安全漏洞的檢測.在面向Android安全的應(yīng)用中,TaintDroid[28]是當前最流行的動態(tài)檢測隱私泄露的工具,它使用多層次的插樁來完成污點傳播.然而,TaintDroid必須在運行時對APK文件進行檢測,這依賴于APK輸入測試集合來觸發(fā)敏感數(shù)據(jù)流,且TaintDroid會對Android系統(tǒng)本身帶來一定的開銷,每次Android版本更新之后,TaintDroid都需要重新進行定制.CHEX[29]嘗試使用靜態(tài)的污點分析方法檢測智能手機組件劫持漏洞.FlowDroid[12]則提供了更精確的靜態(tài)污點傳播.DroidSafe[30]結(jié)合 Android Open Source Porject(AOSP)實現(xiàn)了與原 Android接口語義等價的分析模型,并使用精確分析存根(accurate analysis stub)將AOSP代碼之外的函數(shù)加入到模型,在此基礎(chǔ)上進行污點分析.IccTA[31]利用靜態(tài)程序插樁和IC3工具[32]提供了敏感信息通過組件間進行泄露的檢測方法.正如前文所述,上述工具雖然提供了基礎(chǔ)污點分析方法,但是沒有關(guān)注分析結(jié)果之間的相關(guān)性,也沒有解決結(jié)果之間多源綁定發(fā)生的技術(shù).

此外,利用污點分析對Android應(yīng)用市場中惡意軟件分類的相關(guān)工作也與本文類似.MudFlow[5]利用數(shù)據(jù)挖掘的方法直接使用FlowDroid的輸出結(jié)果進行惡意軟件分類,該工具針對2 866個良性軟件的污點結(jié)果進行統(tǒng)計訓(xùn)練,其核心思想是,通過對良性軟件產(chǎn)生的污點結(jié)果與當前待檢測的 Apk文件的差異來判斷其惡意性.Apposcopy[6]嘗試利用污點分析結(jié)合組件的語義信息提供應(yīng)用簽名,之后,嘗試利用簽名匹配來檢測惡意行為.Dark Hazard[7]使用特殊的分支條件下的污點分析觸發(fā)路徑作為機器學(xué)習(xí)的特征,從而檢測惡意的隱藏敏感操作.雖然上述工具都是以提高檢測精度為出發(fā)點,但是我們發(fā)現(xiàn),這些方法都是直接使用污點分析的結(jié)果,并不會提高污點分析本身的功能.我們?nèi)绻僭O(shè)污點分析是一個黑盒,那么這些方法使用黑盒產(chǎn)生結(jié)果,然后在外部進行分析;而我們的方法是在黑盒內(nèi)部提供更細粒度的分析.所以我們相信,多源污點分析是可以直接應(yīng)用到上述方法中完成更進一步精度提升的.我們將在后續(xù)的工作中,將多源技術(shù)結(jié)合機器學(xué)習(xí)技術(shù)及更多語義信息來探索高精度的惡意軟件分類方法.

7 總結(jié)與未來的工作

本文以當前污點分析檢測Android應(yīng)用隱私泄露的誤報率高為出發(fā)點,針對惡意軟件和良性軟件之間的多源綁定發(fā)生特性差異來提高檢測精度.我們提出了一種多源綁定發(fā)生的靜態(tài)污點分析技術(shù):在精度上,該技術(shù)具有上下文敏感、流敏感、域敏感等特性,并且可以有效地區(qū)分出分支互斥路徑的情況;在效率上,提出一種按需的高效實現(xiàn)方法,降低了多次的多源問題計算的開銷.我們的實驗數(shù)據(jù)表明:即使在一次污點分析結(jié)果上進行多次多源問題分析,我們的執(zhí)行時間也在可以接受的范圍之內(nèi)(初始階段開銷為 19.7%,進一步的多源分析時間平均為 0.3s).隨后驗證了多源綁定發(fā)生技術(shù)在隱私泄露檢測問題中的應(yīng)用,發(fā)現(xiàn)當前良性軟件和惡性軟件的多源綁定發(fā)生特性確實具有較大的差異.隨后,我們驗證了多源技術(shù)與簡單方法相比的精度提升(減少多源對41.1%).最后提出了一種智能手機隱私泄露結(jié)果風險評級標準,應(yīng)用此評級結(jié)果,可以進一步改善用戶的檢測的效率.

在未來的工作中,我們將把該技術(shù)與其他應(yīng)用技術(shù)相結(jié)合,以提供更高的惡意軟件檢測精度.

· 首先,該技術(shù)可以結(jié)合更多語義信息,基于語義信息的惡意軟件檢測方法可以避免代碼混淆技術(shù)帶來的威脅,而多源綁定發(fā)生技術(shù)為更多語義信息支持提供可能性,一些有效的語義信息包括Android生命周期、特殊的回調(diào)函數(shù)、關(guān)鍵的API使用、GUI信息特征、特殊的分支觸發(fā)條件等.例如,我們可以提取污點分析路徑中的關(guān)鍵API作為語義信息基礎(chǔ),探索多個綁定發(fā)生源之間的API調(diào)用序列之間的關(guān)系.又如,我們可以探索在一個特殊的Button觸發(fā)下,有哪些多源被綁定發(fā)生.如果這些源綁定發(fā)生行為與Button本身語義違反,則可以報告相關(guān)問題.

· 其次,我們將探索更有效的統(tǒng)計分析方法.目前,利用該方法在檢測 Android安全問題上有很大的應(yīng)用空間.例如,MudFlow嘗試將待分析程序與良性軟件間的差異作為特征,進一步利用 SVM 分類器進行檢測.DroidADDMiner[8]利用了FlowDroid提取API數(shù)據(jù)之間的依賴關(guān)系作為特征向量進行惡意軟件檢測.多源方法在上述方法中的應(yīng)用需要更有效的統(tǒng)計方法支持.另外一個值得研究方向是探索應(yīng)用市場中不同的目錄類別下的應(yīng)用程序中多源問題的使用情況,因為相同類別下的 APK往往會有類似的使用結(jié)果,探索相關(guān)的多源特性違反情況可以提供保證軟件質(zhì)量和軟件安全的特征.

此外,多源綁定的污點分析技術(shù)還可以用來對別名分析進行優(yōu)化.非別名的污點傳播是跟隨程序的執(zhí)行而傳播的,然而對于別名的傳播往往不能通過直接的計算可以得到.例如,FlowDroid嘗試在遇到堆變量賦值計算別名時啟動一個后向的別名分析求解器.此時,如果后向的別名傳播和正向的變量在分支互斥的路徑下,則會產(chǎn)生誤報.例如,如圖13所示,a和b別名的前提是IF語句執(zhí)行了第5行的分支,而實際的污點傳播則是通過第7行進行的.此時,我們可以利用多源綁定的技術(shù)對該問題進行精度提升(設(shè)置a為另一個污點源,判斷a是否與source綁定發(fā)生).我們堅信多源技術(shù)是一類重要基礎(chǔ)性的技術(shù),未來將被更多程序分析領(lǐng)域應(yīng)用.

Fig.13 An example of alias analysis optimization圖13 別名分析優(yōu)化示例