一種面向Trace與漏洞驗證的污點分析方法

秦 彪,郭 帆,楊晨霞

(1.江西師范大學 計算機信息工程學院,南昌 330022; 2.豫章師范學院 計算機系,南昌 330105)

0 概述

隨著當前智能手機的普及,手機應用的安全性備受關注。隱私泄露是智能手機最嚴重的安全問題之一,其指APP中存在一條從讀取隱私數據的Source方法調用語句到輸出隱私數據的Sink方法調用的執行路徑,并且未經用戶許可[1]。利用Source方法可以讀取通訊錄、收發短信等,利用Sink方法可以寫文件、發短信或發送網絡報文等。研究人員提出了許多方案來檢測APP中潛在的隱私泄露漏洞,其中污點分析方法是主流檢測方法之一。污點分析通常從Source開始跟蹤外部引入的數據(污點),檢查其是否未經驗證就直接傳播到Sink位置,如果是則可能存在漏洞。

污點分析可分為靜態分析和動態分析。靜態分析不運行代碼,直接掃描代碼或者轉換后的中間代碼,提取其中的詞法、語法和語義,結合控制流分析和數據流分析,判定污點是否能從Source傳遞到Sink[2]。動態分析指插樁并監控APP運行時行為,動態獲取程序的控制流和數據流,實時跟蹤污點傳播,在Sink位置檢測是否有污點信息輸出[2]。相比動態分析,靜態分析可靠性更高,其可以在程序發布之前對APP進行檢查,但是存在分析結果虛警率過高問題。靜態分析需要耗費大量資源并且性能較差,為在實現精度和效率平衡的同時保證可靠性,往往會對所有分支的數據流信息進行保守合并,從而產生大量虛警。

本文提出一種新的污點分析方法,在插樁APK并記錄應用在運行時的執行路徑信息(Trace)后,對Trace進行上下文敏感和域敏感的污點分析,同時定義指令級污點傳播語義和一致性約束,進而驗證Trace是否存在隱私泄露。

1 相關工作

污點分析本質上屬于數據流分析技術,其在信息安全領域得到廣泛應用,主要用于漏洞分析和惡意代碼檢測等,研究人員設計了許多污點分析工具。Taj[3]是一個高效的面向Web應用的污點分析工具,它分為兩個階段:一是執行指針分析,構造應用的方法調用圖;二是將方法調用圖作為輸入,設計一種混合的輕量級切片算法跟蹤污點信息流。文獻[4]采用與Taj相似的方法,設計了一種基于精確指針分析的靜態分析方法,通過用戶提供的缺陷規范自動生成對應的靜態分析器,以達到有針對性靜態檢測程序缺陷的目的。文獻[5]基于類型的污點分析,實現了一個上下文敏感的面向安全信息流的類型系統SFlow。FlowDroid[6]是目前較好的一種針對APP上下文敏感、流敏感、域敏感和對象敏感的精確污點分析工具,其對Android的多方法入口以及基于事件和回調機制的控制流進行了準確刻畫,但是沒有考慮組件間通信(ICC)。StubDroid[7]以污點數據流摘要的形式對Android框架建模,它基于FlowDroid,應用域敏感、對象敏感及上下文敏感的指針分析,充分考慮了回調機制,但是沒有分析ICC通信。文獻[8]聚焦于FlowDroid沒有考慮的包含用戶交互的回調方法,利用圖可達性方法盡量識別可能驅動用戶交互方法的執行路徑,是Flowdroid的有效補充。Amandroid[9]采用組件級的分析,使用Flowdroid對APP生命周期建模的的方式對單個組件進行建模,并應用字符串分析技術來識別ICC通信,主要用于識別信息泄漏。

污點分析分為靜態分析和動態分析。根據Rice定理[10-11],靜態分析針對程序的任何非平凡屬性(例如程序是否存在數組越界),無法做到既完備又可靠。多數工具生成的控制流圖存在許多不確定性,如弱類型檢查、未定義的行為以及別名指針等。因此,靜態分析往往采用近似方法,導致分析結果存在虛警和漏報[12]。為了消除靜態分析結果的虛警,研究人員提出許多解決方法并設計和實現了多個靜態漏洞檢測工具。文獻[12]認為惡意應用的多個Source之間的相關性與正常應用存在差異,提出一種分析結果中的多個Source是否綁定觸發Sink的污點分析技術MultiFlow,利用這種差異可以降低虛警率。但MultiFlow在處理單源污點的數據流傳播問題時常出現誤判,并且沒有記錄調用回調方法時傳遞的數據流事實。文獻[13]以靜態分析的結果作為輸入,逆向搜索可能發生缺陷的約束條件,使用約束求解判斷缺陷的可滿足性,進而驗證結果是否虛警。文獻[14]對目標程序進行控制流分析,判斷警報的可達性并得到制導信息,再利用混合執行測試的方法,跟蹤程序運行時內存狀態并判斷內存是否泄漏,驗證漏洞是否虛警。文獻[12-13]的方法都需要通過約束求解判定路徑是否可行,然而在實際應用中,路徑條件復雜多變,約束求解存在約束表達困難和無法獲得正確解的問題,導致虛警驗證失敗。

動態分析是指在程序執行時監聽程序狀態,或者使用插樁在程序執行時獲得程序的數據流和控制流,在Source處給數據打上污點標簽,然后實時跟蹤污點數據,在Sink處檢測是否污點數據被輸出導致信息泄漏。TaintDroid[15]修改Dalvik虛擬機,將經典污點傳播遷移至Android底層,采用指令插樁的方式實時監控污點數據傳播過程,但運行時開銷太大,實用性不高。CopperDroid[16]修改定制的Android模擬器,記錄APK運行時的系統調用序列,分析污點數據傳播以發現惡意行為,可以抵抗應用層的代碼混淆,不需要修改Android系統,部署方便且適應性強。VetDroid[17]在TaintDroid基礎上實現基于權限的動態污點分析,尋找敏感資源使用的污點傳播,可診斷是否存在違背預定義策略的行為。Aurasium[18]對Android系統與Linux內核之間的通信進行插樁,監控APP與底層系統之間的交互,重構APP的組件間或進程間通信從而發現違背預定義安全策略的執行路徑。但是Aurasium存在性能瓶頸、Android版本更新較快等問題,很難實際部署。AppIntent[19]從可疑路徑中抽取事件處理方法集合,形成事件處理方法約束圖,并根據約束條件產生用戶輸入,驗證該路徑是否是用戶許可的路徑,排除虛警。此類方法的通用問題是可靠性不夠,動態驗證時無法覆蓋完整的路徑集合,導致許多漏報和虛警。

動態分析普遍存在運行效率和檢測代碼覆蓋率低的問題。本文提出的面向插樁Android應用后產生的執行Trace的污點分析方法,在指令級定義污點傳播必須滿足的一致性約束,保證污點分析的語義正確性,驗證Trace是否包含真實漏洞。

2 整體設計

本文方法的整體流程如圖1所示,具體如下:

1)對APK靜態插樁,生成新的.dex文件,使插樁后的Android應用在執行時能夠記錄程序的執行路徑信息(Trace)。

2)將新生成的.dex文件打包成插樁后的APK,并安裝到Android模擬器或真機中,然后手工執行插樁后的應用,執行完畢后輸出Trace。

3)對Trace進行別名分析和污點分析,分析程序執行過程中的運行時信息,進而根據這些信息驗證隱私泄露是否真實存在。

圖1 本文方法整體流程

分析模塊的內部層次結構如圖2所示,其中方法調用現場信息收集子模塊處在最底層,作為整個分析模塊的基礎,在別名分析時需要查找方法調用現場信息以確定實參到形參的別名數據流走向,進而別名分析又為污點分析提供支撐。

圖2 分析模塊的層次結構

手工執行插樁的Android應用獲得的Trace本質上是一條順序的代碼序列,污點分析的目標是根據Trace中的信息分析每條指令位置的全局污點信息。Java變量都以引用形式標識運行時具體的內存位置,因此,不同變量可能指向同一塊內存空間,即它們互為別名,污點分析需要精確的別名信息。Android應用存在大量的方法調用,特別是回調方法和注冊監聽組件事件的處理方法,在進行別名分析之前需要收集Trace中的方法調用現場信息,包括發生方法調用的位置信息和實參與形參之間的映射關系。

根據獲得的別名分析結果,將污點狀態信息標記到別名變量指向的內存塊上,以此來跟蹤污點傳播過程。污點分析中傳遞的數據流事實是被污染變量的污染狀態集合,稱為污點狀態集合。污點狀態集合中的每個元素以二元組的形式定義:(var,taint_level),其中,var表示變量的訪問路徑(Access Path),taint_level表示被污染變量的受污染程度,方法規定3種污染程度,即部分污染(pa)、完全污染(ta)和可信(trust)。影響污點數據流傳播的執行語句包括方法調用語句和賦值語句。

方法調用語句分為調用庫方法和調用自定義方法。分析庫方法調用時,以污點傳播摘要的方式對庫方法執行產生的污點信息流建模,根據具體的摘要調整并記錄方法執行后各相關內存塊的污點狀態信息。分析自定義方法調用時需要進一步遞歸分析方法體內部每條語句的污點傳播語義來實現跨方法污點傳播過程。

在分析賦值語句時,首先按賦值語句右值的不同類型定義污點傳播語義規則,依照規則記錄污點傳播過程,然后再按左值的不同類型,調整相關變量的污點狀態信息。對內存塊的污點狀態信息的修改或調整都必須滿足污點傳播的一致性約束,避免錯誤記錄污點傳播信息。

2.1 污點傳播一致性約束

令X是輸入的數據流事實,Y是輸出的數據流事實,則在污點傳播過程中,污點狀態變化應滿足如下污點傳播一致性約束:

1.(a,ta)∈X→(a,pa)?X;(a,pa)∈X→(a,ta)?X;

2.(a,ta)∈X→(a.f,ta)∈X∨(a[i],ta)∈X.(?i,f);

3.(a,pa)∈X→(a.f,ta)∈X∨(a.f,pa)∈X∨(a.[i],ta)∈X∨((a.f,ta)?X∧(a.f,pa)?X)∨(a[i],ta)?X.(?i,f);

4.(a,ta)?X∧(a,pa)?X→(a.f,ta)?X∧(a.f,pa)?X∧(a[i],ta)?X∧(a[i],pa)?X.(?i,f);

5.(a,pa)∈X∨(a,ta)∈X∨(b,pa)∈X∨(b,ta)∈X→(b[a],ta)∈X∨(a[b],ta)∈X;

6.isMustAlias(a,b)∧(a,ta)∈X→(b,ta)∈X; (?b)

isMustAlias(a,b)∧(a,pa)∈X→(b,pa)∈X; (?b)

isMustAlias(a,b)∧(a,ta)?X∧(a,pa)?X→(b,pa)?X∧(b,ta)?X;(?b)

其中:isMustAlias(a,b)表示a與b一定互為別名;約束1表示在傳遞的數據流事實中,變量a的被污染程度是完全污染(ta)、部分污染(pa)或是污點狀態集合中不記錄變量a的污點狀態信息,即a可信(trust),a的污點狀態只能是這3種情況之一;約束2表示如果變量a是ta,那么a的所有子域對象也必須是ta;約束3表示如果變量a是pa,那么a的子域對象可能是ta、pa或可信;約束4表示如果變量a可信,那么a的所有子域對象也必須可信,即污點狀態集合中不含有a和a的任何子域對象;約束5表示如果數組元素a[i]中,有一個引用變量不可信,即a或i不可信,那么實例變量a[i]不可信,并且a[i]必須是ta;約束6表示互為別名的變量的污點狀態信息必須相同。

2.2 污點傳播語義

本節形式化定義和描述不同指令的污點傳播語義,ConstGen和ConstKill分別表示不依賴之前的數據流結果,每次執行指令都會產生或刪除的數據流事實,而DepGen和DepKill分別表示需要依賴之前的數據流結果,執行指令才會產生或刪除的數據流事實,MustAlias(a)返回a的所有別名集合。

2.2.1 賦值語句

圖3中給出2個示例代碼片段,用于輔助解釋各條規則的含義。

圖3 示例代碼片段

賦值語句描述如下:

1)形如a=12、a=b、a=b.f、a=b[i]、a=new等。

(1)a=Constant(常量,基本類型Primary)

MustAlias(a)=ConstGen=DepGen=DepKill=Ф

ConstKill={(a,pa),(a,ta),(a.f,pa),(a.f,ta),(a[i],pa),(a[i],ta)}(?i,f)

圖3(a)的第1條語句導致變量s被污染,第2條語句是賦值語句,將常量“Hello world!”賦值給s,由于常量是可信的,s由原來指向的污點內存塊轉為指向存放常量“Hello world!”的內存塊,s的污點狀態由不可信變為可信。假設s有子域或者s是數組類型變量,則s的子域或所有數組元素的污點狀態都會被右值變量的污點狀態覆蓋,即左值的污點狀態信息必須與右值的污點狀態信息一致。

(2)a=b,b.f,class.f,b[i]

MustAlias(a)=ConstGen=ConstKill=Ф

If(b,ta),(b.f,ta),(class.f,ta),(b[i],ta)∈X/*?i,f.右值完全污染*/

DepGen={(a,ta),(a.f,ta),(a[i],ta)}

DepKill={(a,pa),(a.f,pa),(a[i],pa)}

If(b,pa),(b.f,pa),(class.f,pa),(b[i],pa)∈X/*?i,f.右值部分污染*/

DepGen={(a,pa),(a.f,pa),(a[i],pa)}

DepKill={(a,ta),(a.f,ta),(a[i],ta)}

If(b,pa),(b,ta),(b.f,pa),(b.f,ta),(class.f,pa),(class.f,ta),(b[i],pa),(b[i],ta)?X/*?i,f.右值可信*/

DepGen=Ф

DepKill={(a,pa),(a,ta),(a.f,pa),(a.f,ta),(a[i],pa),(a[i],ta)}

對于第2類賦值語句,污點信息是從右值傳播到左值,因此,執行此類語句后,左值污點狀態的改變取決于右值原來的污點狀態。在圖3(a)的第6條語句中,p.name將污點信息通過賦值語句傳遞給s,s的污點狀態等于p.name記錄的污點信息:如果p.name是ta,那么s為ta;如果p.name是pa,那么s為pa;如果p.name是trust,那么s為trust。

p.name在執行第5條語句時被完全污染,所以執行完第6條語句后,s也被完全污染。

(3)a=new…

MustAlias(a)=ConstGen=DepKill=DepGen=Ф

ConstKill={(a,pa),(a,ta),(a.f,pa),(a.f,ta),(a[i],pa),(a[i],ta)}(?i,f)

在上述語句中,右值為new表達式。執行該語句時,系統會分配新的內存空間給左值變量,所以污點狀態集合中與左值相關的污點信息會被清除。在圖3(a)的第3條語句中,變量s重新指向一個新的字符串對象的內存塊,污點傳播語義與第1條常量賦值的語義相同。

2)形如a.f=b、a[i]=b、class.f=b,其中,f表示對象域,class.f表示類的靜態域。

(1)a.f=b(i指任意下標)

MustAlias(a.f)=ConstGen=ConstKill=Ф,MustAlias(a)≠Ф

If(b,ta)∈X/*右值完全污染*/

If (a,ta)∈X

DepGen=DepKill=Ф

If (a,pa)∈X

DepGen={(a.f,ta),(a.f.h,ta),(a.f[i],ta)}∪f_gen(a,f,ta);(?i,h)

DepKill={(a.f,pa),(a.f.h,pa),(a.f[i],pa)}∪f_kill(a,f,ta);(?i,h)

If (a,pa)?X∧(a,ta)?X

DepGen={(a,pa),(a.f,ta),(a.f.h,ta),(a.f[i],ta)}∪f_gen(a,f,ta);(?i,h)

DepKill=f_kill(a,f,ta);

If(b,pa)∈X/*右值部分污染*/

If (a,ta)∈X

DepGen={(a,pa),(a.f,pa),(a.f.h,pa),(a.f[i],pa)}∪f_gen(a,f,pa);(?i,h)

DepKill={(a,ta),(a.f,ta),(a.f.h,ta),(a.f[i],ta)}∪f_kill(a,f,pa);(?i,h)

If (a,pa)∈X

DepGen={(a.f,pa),(a.f.h,pa),(a.f[i],pa)}∪f_gen(a,f,pa);(?i,h)

DepKill={(a.f,ta),(a.f.h,ta),(a.f[i],ta)}∪f_kill(a,f,pa);(?i,h)

If (a,pa)?X∧(a,ta)?X

DepGen={(a,pa),(a.f,pa),(a.f.h,pa),(a.f[i],pa)}∪f_gen(a,f,pa);(?i,h)

DepKill=f_kill(a,f,pa);(?i,h)

If(b,pa)?X∧(b,ta)?X/*右值可信*/

If (a,ta)∈X

DepGen={(a,pa)}∪f_gen(a,f,trust);

DepKill={(a,ta),(a.f,ta),(a.f,pa),(a.f.h,ta),(a.f.h,pa),(a.f[i],ta),(a.f[i],pa)}∪f_kill(a,f,trust);(?i,h)

If (a,pa)∈X

DepGen=f_gen(a,f,trust);

DepKill={(a.f,ta),(a.f,pa),(a.f.h,ta),(a.f.h,pa),(a.f[i],ta),(a.f[i],pa)}∪f_kill(a,f,trus);(?i,h)

If (a,pa)?X∧(a,ta)?X

DepGen=DepKill=Ф

f_gen和f_kill函數定義如圖4所示。

圖4 f_gen與f_kill函數定義

在“a.f=b”形式的賦值語句中,左值的訪問路徑長度為2,因此,在污點信息從右值傳遞到左值后,需要另外調整與a.f相關的別名變量的污點信息。例如a.f的污點狀態由trust變為ta,那么a就變為pa,如果c.d是a的一個別名變量,并且c原本是trust,那么需要將c的污點狀態也調整為pa。在圖3(b)的第4條語句中,右值t在執行第3條語句時被完全污染,t將污點信息傳遞給p.name,所以p.name的污點狀態與t一致,也是ta。但是p.name在被t污染之前是可信的,在對象p中還可能存在其他可信域,因此保守地約定p是pa而不是ta。

(2)class.f=a(左值是類的靜態成員)

MustAlias(class.f)=ConstGen=ConstKill=Ф

If(a,pa)∈X/*右值部分污染*/

DepGen={(class.f,pa),(class.f.h,pa),(class.f[i],pa)}(?i,h)

DepKill={(class.f,ta),(class.f.h,ta),(class.f[i],ta)}(?i,h)

If(a,ta)∈X/*右值完全污染*/

DepGen={(class.f,ta),(class.f.h,ta),(class.f[i],ta)}(?i,h)

DepKill={(class.f,pa),(class.f.h,pa),(class.f[i],pa)}(?i,h)

If(a,pa)?X∧(a,ta)?X/*右值可信*/

DepGen={Ф}

DepKill={(class.f,pa),(class.f,ta),(class.f.h,pa),(class.f.h,ta),(class.f[i],pa),(class.f[i],ta)}(?i,h)

在圖3(b)的第5條語句中,Person.type被改為ta。由于此前Person.type是trust,并且所有其他Person類型的對象都是trust,因此當Person.type變為ta后,因為type域被所有Person類型對象共用,所以需要將其他Person類型的對象修改為pa。

(3)a[i]=b(i指某一個數組下標,j為任意下標)

MustAlias(a[i])=ConstGen=ConstKill=Ф

If(b,ta)∈X∨(b,pa)∈X

If(a,ta)∈X

DepGen={(a[i],ta),(a[i].f,ta),(a[i][j],ta)}∪f_gen(a,a[i],ta);(?j,f)

DepKill=Ф;

If(a,pa)?X∧(a,ta)?X

DepGen={(a,ta),(a[i],ta),(a[i].f,ta),(a[i][j],ta)}∪f_gen(a,a[i],ta);(?j,f)

DepKill=Ф;

If(b,ta)?X∧(b,pa)?X

If (a,ta)∈X

DepGen={(a[i],ta),(a[i].f,ta),(a[i][j],ta)}∪f_gen(a,a[i],ta);(?j,f)

DepKill=Ф;

If(a,pa)?X∧(a,ta)?X

DepGen=DepKill=Ф

在圖3(b)執行第8條語句之前,數組對象array和array[0]、array[1]都是trust,執行第8條語句后,由于右值t是ta,因此污點信息首先傳遞給array[1],導致array[1]被修改為ta,根據2.1節給出的第5條污點狀態一致性約束,數組對象和元素都為trust或者都為ta。因此,array[0]和array指向的內存塊都被改為ta,保證他們的污點狀態信息與array[1]一致。

2.2.2 方法調用語句

圖5中給出2個Trace片段,用于輔助解釋各類方法調用語句。

圖5 Trace片段

1)與庫方法調用相關的語句

(1)Trust(a)(調用定義的驗證方法摘要)

ConstGen=ConstKill=DepGen=Ф

DepKill={(a,pa),(a,ta),(a.f,pa),(a.f,ta),(a[i],pa),(a[i],ta)}∪{(x,pa),(x,ta)|x∈MustAlias(a)}(?i,f)

(2)a=TaintSource(污染源source)

ConstGen=ConstKill=DepKill=Ф

DepGen={(a,ta),(a.f,ta),(a[i],ta)}(?i,f)

(3)其他(依據定義的庫方法摘要)

圖3(a)的最后一條語句是調用驗證方法secret對變量s進行無害化處理,即執行secret后,s由ta變為trust。

2)與自定義方法調用相關語句

分析與自定義方法調用相關語句的污點傳播時,必須關注參數傳遞和方法返回;方法體內其他語句的污點傳播必須滿足一致性約束。

(1)方法調用語句形式為virtualinvokea.f(b)、c=virtualinvokea.f(b)、specialinvokea.f(b)或c=specialInvokea.f(b)。

①r0:=@this:Class/*this引用的初始化語句*/

ConstGen=ConstKill=DepKill=Ф

If(a,pa)∈X/*方法調用者部分可信*/

DepGen={(r0,pa),(r0.f,pa),(r0[i],pa)}(?i,f)

If(a,ta)∈X/*方法調用者完全不可信*/

DepGen={(r0,ta),(r0.f,ta),(r0[i],ta)}(?i,f)

If(a,pa)?X∧(a,ta)?X/*方法調用者可信*/

DepGen=Ф

②i0:=@parameter0:type/*實參傳遞給形參的語句*/

ConstGen=ConstKill=DepKill=Ф

If(b,pa)∈X/*實參部分可信*/

DepGen={(i0,pa),(i0.f,pa),(i0[i],pa)}(?i,f)

If(b,ta)∈X/*實參完全不可信*/

DepGen={(i0,ta),(i0.f,ta),(i0[i],ta)}(?i,f)

If(b,pa)?X∧(b,ta)?X/*實參可信*/

DepGen=Ф

③return

ConstGen=ConstKill=Ф

DepKill={(var,taint_state)|方法調用現場的上下文無法訪問的var}

If在當前語句點的數據流事實中包含有記錄r0、r0.f、r0[i]

DepGen={將r0、r0.f、r0[i]的污點狀態傳遞給對應的a、a.f、a[i]}(?i,f)

If在當前語句點的數據流事實中都沒有記錄r0、r0.f、r0[i]的污點狀態

DepGen=Ф

④return i1;

ConstGen=ConstKill=Ф

DepKill={(var,taint_state)|方法調用站無法訪問var}

If(i1,pa)∈X(方法返回值部分可信)

DepGen={(c,pa),(c.f,pa),(c[i],ta)}(?i,f)

/*如果在當前語句點的數據流事實中包含有記錄r0、r0.f、r0[i]的污點狀態,則再并上集合{將r0、r0.f、r0[i]的污點狀態傳遞給對應的a、a.f、a[i]}*/

If(i1,ta)∈X/*方法返回值完全不可信*/

DepGen={(c,ta),(c.f,ta),(c[i],ta)}(?i,f)

/*如果在當前語句點的數據流事實中包含有記錄r0、r0.f、r0[i]的污點狀態,則再并上集合{將r0、r0.f、r0[i]的污點狀態傳遞給對應的a、a.f、a[i]}*/

If(i1,pa)?X∧(i1,ta)?X/*方法返回值可信*/

DepGen=Ф

/*如果在當前語句點的數據流事實中包含有記錄r0、r0.f、r0[i]的污點狀態,則再并上集合{將r0、r0.f、r0[i]的污點狀態傳遞給對應的a、a.f、a[i]}*/

方法的參數傳遞語句中的污點傳播路徑與賦值語句相同,污點信息都是從右值傳播到左值。在參數傳遞時,左值變量的訪問路徑長度至多為1,因此,無需像賦值語句那樣調整別名變量的污點狀態。當方法返回時,如果調用該方法的語句是賦值語句,那么污點信息從返回值傳播到左值。在圖5(a)的第2條語句中,在參數傳遞時,實參變量$r1和$r7分別將污點信息傳遞給第3和第4條語句的形參變量$r1和$r0。當is_name方法執行完畢,第6條返回語句將被污染的返回值$z0賦值給第2條語句的接收變量$z0,它們互為別名,即它們指向同一內存塊并且是ta。

(2)方法調用形式為staticinvokef(a)或b=staticinvokef(a)。

①i0:=@parameter0:type

ConstGen=ConstKill=DepKill=Ф

If(a,pa)∈X/*實參部分可信*/

DepGen={(i0,pa),(i0.f,pa),(i0[i],pa)}(?i,f)

If(a,ta)∈X/*實參完全不可信*/

DepGen={(i0,ta),(i0.f,ta),(i0[i],ta)}(?i,f)

If(a,pa)?X∧(a,ta)?X/*實參可信*/

DepGen=Ф

②return

ConstGen=ConstKill=DepGen=Ф

DepKill={(var,taint_state)|方法調用站無法訪問var}

③return i1

ConstGen=ConstKill=Ф

DepKill={(var,taint_state)|方法調用站無法訪問var}

If(i1,pa)∈X/*方法返回值部分可信*/

DepGen={(b,pa),(b.f,pa),(b[i],pa)}(?i,f)

If(i1,ta)∈X/*方法返回值完全不可信*/

DepGen={(b,ta),(b.f,ta),(b[i],ta)}(?i,f)

If(i1,pa)?X∧(i1,ta)?X/*方法返回值可信*/

DepGen=Ф

在圖5(b)的Trace片段中,變量$r4是污染源,第5條語句是靜態方法調用。在參數傳遞時,實參$r4將污點信息傳遞給形參$r0,所以第3條語句的變量$r0的污點狀態信息來自$r4,即$r0與$r4的污點信息相同。在執行完第5條語句的靜態方法時,第9條方法返回語句將$r4賦值給接收變量$r5,即變量$r4和$r5互為別名,它們指向的內存塊的污點狀態信息等于$r4在返回語句位置的污點狀態。

2.2.3 其他規定

針對賦值語句的污點傳播,保守定義3條通用傳播語義:

1)右值是二元操作符表達式(BinopExpr),如果右邊的兩個操作數都是trust,那么左值修改為trust;否則,左值被修改為ta。例如a=b+c,只有當b和c都為trust時,a才被改為trust,否則a為ta。

2)右值是類型判別表達式(InstanceOf)或一元操作符表達式(UnopExpr),首先將右值的污點狀態信息拷貝給到左值,然后調整與左值相關的其他變量的污點信息。例如在圖6給出的示例代碼中,a的污點信息與b相同。

圖6 Jimple代碼示例

Fig.6 Example of Jimple code

3)右值是方法調用表達式(InvokExpr)時,如果調用自定義方法,由于已經記錄了調用現場信息,并對相關內存塊的污點狀態信息進行過跟蹤,所以無需再做額外操作。如果調用庫方法,就需要判斷該方法是否source方法,是則將該方法當做污染源進行處理,否則根據下文定義的庫方法污點傳播摘要和驗證方法污點傳播摘要進行分析。

3 原型系統實現

原型系統由插樁模塊、別名分析模塊和污點分析模塊組成,其中通過插樁程序記錄程序運行時的執行路徑信息(Trace),Trace本質上是一條順序執行的代碼序列。將Trace作為輸入,分析其中的別名關系和污點信息。

3.1 別名分析模塊

別名分析的基礎是方法調用現場信息,重點是方法調用過程中的實參與形參的映射關系。定義數據結構“Stack>”記錄方法調用現場信息,其中每個現場元素以HashMap鍵-值對的形式存儲,包含2種信息:一是“position”,表示方法調用語句在Trace中的位置信息,直接從Trace中記錄的語句信息獲得;二是“actual_formal_map”,使用“LinkedList>”類型,根據方法簽名存儲實參與形參之間的映射關系,Pair的第1個元素表示實參,第2個元素表示形參;LinkedList中最后1個元素用于記錄實例方法的this引用的傳遞信息,如果不是實例方法調用語句則不記錄。

別名分析模塊按Trace中的指令順序模擬實際運行時動態分配的內存空間,在每塊內存空間中記錄所有指向該內存空間的別名引用,即別名集合。根據不同語句類型判斷別名信息的傳遞,進而跟蹤內存空間的別名信息的變化。內存空間的數據結構定義如下:

LinkedList>,HashSet>>>

上述結構以鏈表的形式存儲程序申請的所有內存塊,其中每一個Pair代表一個內存塊,在每個內存塊中記錄了2種信息:別名信息和內存塊信息。它們各映射成一個集合(HashSet),分別是PointsToSet和BlocksSet。PointsToSet記錄所有指向該內存塊的變量,集合中的所有變量之間都互為別名。BlocksSet記錄的是內存塊集合。集合中的元素類型是HashMap,每個元素記錄了申請內存塊的位置信息、內存塊的子空間位置信息和內存塊的污點信息,具體字段記錄的內容如表1所示。

表1 內存塊記錄的信息

依照表1的定義,順序遍歷Trace中的語句信息,分析每條指令并跟蹤別名信息的傳遞過程。經分析,對Android應用執行時的別名信息造成影響的語句類型共有4種,分別是參數傳遞語句(IdentityStmt)、賦值語句(AssignStmt)、方法調用語句(InvokeStmt)和方法返回語句(ReturnStmt)。

3.2 庫方法污點傳播摘要

在污點分析過程中,本文方法不對底層系統調用庫、JDK和SDK庫方法的內部數據流進行污點分析,而是采用建模的方式定義污點傳播摘要,記錄調用庫方法前后內存中的污點信息變化。同時對庫方法中包含的驗證方法(Sanitizer)進行建模,定義無害化處理的污點傳播摘要。采用白名單結合正則匹配的策略對自定義驗證方法進行識別,主要基于方法名稱、傳遞參數類型和返回值類型。例如,對于名字中包含“validate”“encrypt”或“check”等子串的方法調用語句,如果參數類型和返回值類型的簽名滿足預定義規則,那么使用預定義的污點傳播摘要直接生成方法調用后的內存污點信息。

下面給出典型庫方法的污點傳播摘要示例,按照方法的調用方式分為靜態調用(StaticInvokeExpr)和實例調用(InstanceInvokeExpr)2種類型。

1)靜態調用。在默認情況下,如果方法調用現場接收方法的返回值,那么將所有實參的污點信息直接傳播給接收變量。污點傳播路徑如圖7中箭頭所示。對一些非典型的靜態調用方法如,污點傳播路徑是從其他實參傳遞到第3個實參指向的內存塊。

圖7 靜態調用庫方法的默認污點傳播路徑

Fig.7 Default taint propagation path of static invocation library method

2)實例調用。在默認情況下,污點信息從所有實參傳播到this指向的內存塊,如果方法調用現場接收方法的返回值,那么將this的污點信息再傳遞到接收變量。

圖8給出的全類名中定義的庫方法,如果方法調用現場處接收方法的返回值,那么污點信息從實參和this傳播到接收變量,然后再從實參傳播到this變量所指向的內存塊,如果被調用方法是“read”,那么污點信息還會從this和其他實參傳播到第一個實參。

圖8 Java中的全類名

此外,還有2個特殊的方法:一是,污點信息還會從this和其他實參傳播到第3個實參變量;二是,污點信息還會從this和其他實參傳播到第2個實參。

3.3 驗證方法污點傳播摘要

同樣,按照調用方式分為靜態調用和實例調用。

1)靜態調用。方法簽名類似,那么接收方法返回值的變量經過了驗證,即接收變量是可信的。如果方法名包含“check”“encode”“secret”“validate”和“sanitize”字符串,那么這些方法被認為是驗證方法,所有實參將在方法體內做無害化處理,它們的污點狀態被置為trust。

2)實例調用。同樣,如果實例調用方法的方法名包含約定的字符串,那么所有實參、this變量和接收返回值的變量都會被無害化處理,它們的污點狀態被置為trust。對于圖9給出的驗證方法,它們被調用后,所有實參和this變量都被無害化處理,污點狀態為trust。

圖9 部分驗證方法的方法簽名

4 實驗分析

原型系統基于Soot-trunk 3.0[20]和FlowDroid 2.0框架實現,使用JDK 1.8開發,總計5 700余行代碼,其中插樁模塊1 400余行,別名分析模塊和污點分析模塊共4 300余行。實驗環境為Genymotion搭建的模擬器,運行系統版本為Android4.4,操作系統版本是Ubuntu 18.04.1 LTS,處理器i5-3230M,CPU 2.6 GHz,內存8 GB。

實驗測試選取DroidBench2.0[21]作為測試數據集,它包含了13類共119個Android應用。剔除跨組件通信、應用間通信和多線程3類測試樣本共34個(原型系統目前還不支持這三類的應用程序)。另外,在實際記錄程序執行Trace和分析過程中,有15個樣本無法獲得有效的Trace,最終得到70個有效樣本。運行FlowDroid對這70個樣本進行靜態,共發現64個泄露,進一步采用本文方法對70個樣本進行分析,實驗結果如表2所示。可以看出,本文方法共獲得72條Trace,共發現68個泄露,與FlowDroid的結果比較,發現它報告了4條虛警,并有8條漏報。

表2 本文方法與MultiFlow方法的實驗結果比較

Table 2 Experimental results comparsion of the proposed method and MultiFlow method

方法Trace數泄露數虛警數漏報數本文方法726848MultiFlow方法—6815

圖10是一組實驗獲得的Trace片段結構。FlowDroid報告了2條泄露,分別是從第1行Source執行到第3和第5行的Sink1和Sink2。其中從Source到Sink1的隱私泄露,本文方法給出了Source到Sink1的完整污點傳播路徑,因此該漏洞真實存在。Source到Sink2共存在4條可執行路徑,在運行程序獲得4條Trace后,對每條Trace進行污點分析,沒有發現任何的污點傳播路徑,因此報告該漏洞是虛警。

圖10 Trace片段結構

圖11是一組發現FlowDroid漏報的Trace片段,污染源Source在圖中第10行語句處,發現污點變量$r6可以傳播到第26行的$r13變量中,即26行的Sink語句觸發了污點變量$r13,這里有一條Source到Sink的未經驗證的路徑,路徑如圖12所示。

表2中第2行是使用MultiFlow對相同樣本集進行分析的實驗結果。MultiFlow通過檢測是否組合綁定的多對Source能同時觸發Sink來降低虛警率,包括2個分析階段:1)單源分析,檢測每一個Source是否傳播到Sink;2)多源分析,以組合的方式檢測多個Source能否綁定同時觸發Sink。MultiFlow總共報告68個泄露,發現了1個虛警和5個漏報。

MulfiFlow未能找到潛在的3個虛警和3個漏報,其中未發現的3個虛警是由于MultiFlow丟失了污點在回調方法間傳遞的數據流信息。在未檢測到的3個漏報中,2個分別發生在修改Shared Preference的回調方法中的和構造Fragement的回調方法中,第3個是在多源分析階段將其中的2條泄露報警錯誤地合并成一條。實驗結果表明,相比MultiFlow和FlowDroid,本文方法準確率更高,能夠有效減少虛警,并降低漏報率。

圖11 實驗獲得的Trace片段

圖12 污點傳播路徑

5 結束語

本文設計一種面向Android應用的Trace污點分析方法。通過插樁Android應用記錄程序運行時的Trace,在此基礎上結合別名分析與污點分析方法,驗證Trace中是否存在隱私泄露。本文方法不支持跨組件、跨應用程序之間的數據通信過程,其對Android 庫方法的建模也仍不完備,可能導致污點分析不精確。因此,下一步將研究跨組件污點數據流事實的傳播,同時對Android庫方法的污點傳播語義進行更完備的建模。