一种面向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库方法的污点传播语义进行更完备的建模。