2. 密码科学技术国家重点实验室(北京信息科学技术研究院), 北京 100094;
3. 河南省信息安全重点实验室(解放军信息工程大学), 河南 郑州 450001
2. State Key Laboratory of Cryptology(Beijing Academy of Information Science and Technology), Beijing 100094, China;
3. He'nan Province Key Laboratory of Information Security(PLA Information Engineering University), Zhengzhou 450001, China
飞速发展的移动互联网和快速普及的智能终端, 使得人们的生活水平和生活方式得到了极大的提高和改变.然而, 在人们享受它们带来的繁荣与便利的同时, 存储在智能终端上的隐私数据安全受到了前所未有的挑战[1].在众多隐私保护技术中, 动态污点跟踪技术可有效地、实时地、细粒度地保护用户隐私数据, 但在应用了动态污点跟踪技术后, 系统实时执行效率都将严重下降.例如, 在虚拟机实时运行层引入污点跟踪技术后, 对于每一条可能传播污点的虚拟机指令, 都将插入多条本地指令以完成污点跟踪.这些指令不但降低了系统的实时执行效率, 而且通过即时编译后产生的冗余代码占用了更多的系统内存.因此, 如何有效地解决动态污点跟踪效率问题, 是制约其能否广泛应用与形成产品的关键.本文将动态污点跟踪技术与即时编译优化技术相结合, 并应用于安卓系统上的隐私信息流控制与保护, 实现了正确和有效的污点跟踪优化, 提高了动态污点跟踪系统的效率.
1 相关工作动态污点跟踪[2]又可称为动态信息流跟踪或动态数据流跟踪, 是指在程序执行过程中跟踪所感兴趣的数据流集合.按其应用领域分类, 主要包括软件漏洞挖掘[3]、隐私数据流保护、数据生命周期分析[4]、软件配置诊断和输入过滤[5]等.按其实现方法分类, 主要包括全系统模拟、中间虚拟机实现[6]、动态二进制插装、源码到源码转换、基于编译的污点跟踪[7]和基于硬件污点跟踪等.基于动态二进制插装实现污点跟踪系统一般依赖于插装平台.按跟踪粒度, 又可分为细粒度和粗粒度跟踪.上述工作均属于细粒度跟踪, 细粒度跟踪还包括基于语言的信息流控制[8, 9]工作.粗粒度的污点跟踪主要体现在操作系统进程级别的信息流跟踪, 如Asbestos[10], Flume[11]和GPTM[12].以上研究普遍存在系统效率较低的问题, 例如, TaintCheck对系统应用执行速度将减缓20倍~30倍.
污点跟踪优化相关研究工作从5个方面尝试解决以上问题.
● 第一, 增加额外硬件资源, 例如增加处理器、寄存器和内存或者将工作传输给远程主机[13, 14].此种优化又有两个研究方向:其一, 污点跟踪代码仍然嵌入到程序代码中, 采用并行化[15]思想将混杂的代码分配到不同CPU处理, 从而提高系统运行效率; 其二, 将污点跟踪代码从程序中解耦合[16].ShadowReplica[17]将污点跟踪代码分配到不同的CPU处理, 不同CPU间采用相应通信机制传递污点警报.这类方法的缺点是需要多核硬件支持, 不适应本文情况.但利用此种解耦合方法, 本文在MIR(middle intermediate representation)编译为LIR(low-level intermediate representation)过程中插入的污点跟踪代码, 并使用LIR数据结构中相应标志位将程序代码和污点跟踪代码区分开来, 便于优化时依据污点跟踪代码特性进行针对性的优化.
● 第二, 将部分动态污点跟踪工作转化到静态分析时完成, 主要思想是:通过静态组件将程序源码或二进制文件统一转化为中间代码, 并插入相应的污点跟踪指令, 最终形成可直接执行并包含污点跟踪的程序代码.文献[18]将污点跟踪过程抽象成污点传播代数, 并使用DAG(direct acyclic graph)进行复写传播和公共子表达式删除等优化.文献[19]结合静态与动态分析, 在静态分析时通过编译器保守地完成信息流跟踪代码插入, 有效地减少了动态运行时实施信息流跟踪的负荷.以上的研究缺点在于静态分析缺乏运行时profile信息, 从而导致优化效果较差, 而且缺乏对操作系统和高级语言的支持.
● 第三, 依据需求动态关闭或开启污点跟踪功能[20, 21], 这类研究工作的缺点在于动态开启或关闭的时机难以确定, 且存在开启或关闭时的性能损耗.非专业用户在关闭污点跟踪时可能存在隐私泄漏情况.
● 第四, 依据用户或者系统需求, 仅对程序部分代码进行污点跟踪[22, 23], 而对一些非重要代码不进行污点跟踪.这类研究工作的缺点在于, 无法严格确定哪些程序代码需要进行跟踪, 而且容易产生漏报, 导致跟踪精确性较差.
● 第五, 依赖于插装平台在即时编译时进行代码优化.以valgrind为例, 其即时编译过程如下:首先将机器码转化为tree IR, 然后通过复写和常量传播、常量折叠、死代码删除、公共子表达式删除和循环展开等优化方法将tree IR转化为flat IR, 然后向flat IR中插装, 并再次进行常量折叠和死代码消除优化, 最后将flat IR转化为本地代码.因而在使用valgrind进行指令级别代码插装时, 可对形成的flat IR再次进行针对性优化.Lift[24]实现了Fast-Path, Merged Check和Fast Switch优化.但已有研究工作如libdft[25]都未针对污点传播代码的特性进行优化, 而是使用一般优化方法, 如方法内联、活跃变量分析和分支预测等.
本文有以下4个方面的优势.
● 其一, 相对于低级语言虚拟机, 高级语言虚拟机指令含有丰富的高层语义, 更利于程序逻辑向污点传播逻辑转化.
● 其二, 插装平台为污点传播所建立的污点影子内存使用1bit的污点值, 难以进行彩色污点跟踪.Dalvik虚拟机污点值采用32bit表示, 拓宽污点值域, 更利于建立一个污点传播分析的框架.
● 其三, dalvik虚拟机具备解释器和即时编译器, 解释器可为即时编译器提供足够的运行时profile信息, 可自适应地对热点路径进行污点跟踪优化.其原因在于:第一, 若冷路径污点跟踪优化算法所占用的时间长于运行代码的执行时间, 则显然是入不敷出的, 因而不宜进行优化; 第二, 即使污点跟踪优化算法所占有的时间长于运行代码的执行时间, 但由于该热点路径反复执行, 即以1次优化的代价换取多次执行的开销是值得的.
● 其四, 基于dalvik虚拟机实现的污点跟踪和安卓手机操作系统是完美结合的, 不需要插装平台的支持和较高专业知识水平用户, 具有良好的易用性和用户透明性.
安卓上动态信息流分析代表性工作是TaintDroid[26], 通过在操作系统源码关键处插入钩子, 实现自动对个人隐私数据打上污点标记和检测是否存在带有污点标记的数据通过网络等路径离开系统; 通过消息级别、程序变量级别、程序方法级别和文件级别的动态污点跟踪, 实现了污点在程序运行过程中的准确传播和污点永久记忆.但TaintDroid对可能发生污点传播的指令都进行跟踪, 而未针对污点跟踪代码进行优化工作.目前没有面向安卓的动态污点跟踪优化相关工作, 与dalvik虚拟机性能优化相关的研究主要包括:文献[27]提出了一种基于文件的动态即时编译代码共享方法, 有效提高了虚拟机内存使用效率和热路径重编译负荷; 文献[28]改进了dalvik虚拟机自适应编译系统, 提出了一种基于结果反馈的动态自适应阈值重置策略, 有效提高了循环、分支跳转和派发指令的执行效率.关于java虚拟机性能优化相关工作主要包括基于编译策略优化技术、基于性能监控优化技术、基于证据的优化技术和基于语言特性优化技术.本文工作结合基于中间虚拟机实现方法和基于编译的污点跟踪实现方法, 针对虚拟机基于热路径的即时编译特征和污点传播特性, 依据程序运行的热点原理, 即, 程序的大部分(80%)运行时间是耗费在小部分(20%)代码上, 结合已有优化技术, 提出了一种动态污点编译优化方法, 对单条热路径进行局部性污点传播优化, 有效提高污点传播技术应用后虚拟机实时执行效率.
2 污点传播优化基础在虚拟机指令级别引入污点传播机制后, 如果简单地对每一条虚拟机指令都插入若干条污点传播指令以完成污点跟踪, 则会带来相当大的运行时开销.因此, 需要将插入的污点传播指令进行优化, 即在目标指令中消除不必要的污点传播指令, 或将污点传播指令移动位置, 或将污点传播指令序列替换为可完成同样污点传播功能但执行速度更快的指令序列.将此定义污点传播优化.要实现污点传播优化, 需要解决以下4个关键问题:第一是污点传播代码与程序代码语义的一致性, 也可称为正确性, 正确性要求程序代码执行时发生污点传播时要准确跟踪, 未发生污点传播时不能错误跟踪; 第二是污点传播代码优化后的高效性, 即要求跟踪代码优化后在运行时间和空间都能优化于未优化的代码; 第三是优化算法合算性, 优化算法代价是能够换取程序执行污点传播时所需的时间和空间的性能开销; 第四是优化算法精确性, 即在正确性基础上确保优化后代码是精确的, 优化算法精确性主要依赖于污点传播分析算法精确性, 可有效防止污点传播假阳性和假阴性.
本节通过分析污点传播语义的特性, 提出了污点传播逻辑.在此基础上进一步提出了污点传播框架, 从理论方面有效解决了前3个问题.第4个问题依赖于全局的污点传播分析和控制流分析, 有待后续进一步深入研究.
2.1 污点传播逻辑污点传播的过程可看作是对程序内部整个污染状态的一系列转换过程, 程序污染状态由各变量的污点值组成, 同时还可能包括运行时刻栈帧和寄存器所存储的各变量污点值.程序执行时, 每一条污点传播语句都将一个输入污染状态转化为一个新的输出污染状态.在整个污点传播分析过程中, 仅分析与污点传播相关的数据流信息.将复杂的数据类型和数值计算逻辑抽象成独立的污点传播逻辑, 也可以理解为将程序逻辑中污点传播语句转化为污点传播逻辑中污点传播表示式(不包含控制流引起污点传播).
结合Dalvik即时编译时虚拟机指令向SSA(static single-assignment)表示的MIR转化的特点, 引入以下相关概念.
定义1(污染点(T)). 变量var的污染点是MIR所处位置, 执行该指令后, 变量var污点值会发生改变.
变量污染点分析需针对不同虚拟机指令类型.例如, OP_MOVE vA, vB是vA的污染点, 同理, 该类型指令还包括数值转换指令(如OP_INT_TO_LONG vA, vB)、数值计算(如OP_ADD_INT vAA, vBB, vCC)、逻辑运算(如OP_AND_ INT vAA, vBB, vCC)等.特别地, 对于OP_MIR_PHI指令, 也认为是vA的污染点.
定义2(传播点(P)). 变量var的传播点是语句MIR所处位置, 执行该语句后变量var的污点值会影响其他变量的污点值.
变量传播点分析也需针对不同虚拟机指令类型.例如, 指令OP_MOVE vA, vB是vA的污染点, 同时也是vB的传播点.指令OP_ADD_INT vAA, vBB, vCC是vA的污染点, 同时也是vB和vC的传播点.同理, 该类型虚拟机指令还包括逻辑运算如OP_AND_INT vAA, vBB, vCC等等.特别地, 对于OP_RETURN指令, 认为是vA的传播点.
由以上定义, 对于指令OP_ADD_INT vAA, vBB, vCC, 其污点传播可表达为TaintA=TaintB|TaintC.同理, 可将所有MIR指令统一抽象为污点传播逻辑(taint propagation logic, 简称TPL), 其语义如图 1所示.
Const代表污染的基本颜色种类的集合.clean表示数据未被污染, color1到color32表示数据已被相应的颜色污染.考虑dalvik虚拟机使用寄存器大小为32位, 以32位无符号整数2n表示某种颜色.例如, 红色代表短信类隐私信息, 以0x00000001表示; 黄色代表联系人类隐私信息, 以0x00000002表示.污点标记变量var记录当前数据(变量、对象)污染状态, 由任意不同种的基本颜色colori组成, 数据被何种污点标记是不确定的.例如, 某数据包含短信类信息和联系人类隐私信息, 其污点可用0x00000003(0x00000001|0x00000002) 表示.Binary-op将程序逻辑中发生污点传播的指令统一抽象成二元或操作符“|”, 在污点传播框架内可理解为集合并操作, 在系统实现部分是逻辑或操作.例如, 加法指令x+y与减法指令x-y在程序数值运算结果虽然不同, 但在污点传播逻辑下运算结果都是x|y.同时, 对于不会引起污点传播指令则直接约减.内存读写指令load与store表示污点在内存与寄存器间读写操作, 写入内存确保污点跟踪正确性.表达式exp定义是递归的, 元表达式由两个污点变量和一个或操作符运算组成.语句stat语义上完整表达的污点传播过程, 即表达式运算后污点值由赋值运算符将污点值赋予变量var.
2.2 污点传播框架 2.2.1 污点传播值域在污点传播逻辑下, 将每条污点传播语句和一个污点值关联起来, 污点值是指在某处可观察到所有污染状态集合的抽象表示.所有可能的污点值的集合称为污点传播值域, 以整体的的方式抽象地研究污点传播, 污点值域是一个乘积格, 每个污点变量对应的格如图 2所示(ci代表colori).对于任意值x属于值集V, 交汇运算∧取集合并集∪, 有:(1) x∧x=x, 满足等幂性; (2) x∧y=y∧x, 满足可交换性; (3) x∧(y∧z)=(x∧y)∧z, 满足可结合性.其顶元素是空集∅, 表示为T, 对于V中的所有x, 有T∧x=x; 底元素是全集U, 表示为⊥, 对于V中所有x, 有⊥∧x=⊥.
交汇运算符定义了污点值域上的一个偏序(记为≤), 污点值域即各个污点变量到格中某个值的映射, 记污点变量v在映射m中的值为g(v).因此, g≤g'当且仅当对于所有污点变量v, 都有g(v)≤g'(v).也可以表达为m∧m'= m".当且仅当对于所有污点变量v, g(v)∧g'(v)=g"(v).偏序集(V, ≤)上的一个上升链是一个满足x1 < x2 < … < xn的序列, 定义格的高度是所有上升链中 < 关系个数的最大值, 在图 2所示的上升链中, 元素最大为33, 故其高度为32.
2.2.2 传递函数族F在污点传播逻辑中, 每个语句Stat对应一个传递函数fs, 包含多个语句的程序块的传递函数可通过将各个语句对应的传递函数组合起来而构造得到.函数集合F由一组传递函数fs组成, 其输入是污点变量到格中元素的映射IN[S], 输入则是发生污点传播后一个新的映射OUT[S].在前向污点传播分析中, 传递函数fs以语句之前IN[S]作为输入, 并输出语句之后的OUT[S]; 传递函数F对于组合运算是封闭的, 即对于F中的任意函数f和g, 存在h(x)=g(f(x))的函数h也在F中.传递函数族F中存在一个单元函数I, 接受一个映射作为输入并输出返回的相同的映射, 即:对于V中的所有x, 有I(x)=x.
2.2.3 框架的单调性单调性在格中定义为:① 对于所有F中的f以及所有V中的x和y, f(x∧y)≤f(x)∧f(y).单调性也可等价定义为:② 对于所有F中的f以及所有V中的x和y, x≤y蕴含f(x)≤f(y).现证明两种定义是等价的.
证明:先证明单调性② 可推导出单调性①:由于x∧y是x和y的最大下界, 则x∧y≤x且x∧y≤y, 由单调性② 可知, f(x∧y)≤f(x)且f(x∧y)≤f(y); 同时, f(x∧y)是f(x)和f(y)的最大下界, 单调性① 得证.
然后证明单调性① 可推导出单调性②:假设x≤y, 由单调性① 可知, f(x∧y)≤f(x)∧f(y), 根据定义有x∧y=x.因此有f(x)≤f(x)∧f(y).因为f(x∧y)是f(x)和f(y)的最大下界, 得到f(x)∧f(y)≤f(y).从而f(x)≤f(x)∧f(y)≤f(y), 即f(x)≤f(y), 单调性② 得证.如图 2所示的格显然满足单调性② 定义, 因为对于任意集合X和Y, X属于X∪Y.
2.2.4 框架下污点传播分析为了便于理解和直观形象地分析污点传播, 以如下dalvik指令代码为例进行分析.
.method public loop()V
const/16 v3,
0x3e8
:goto_0
add-int/2addr v0, v1
add-int/2addr v1, v0
add-int/lit8 v2, v2, 0x1
if-lt v2, v3, :goto_0
return-void
.end method
示例代码程序逻辑是将a=a+b与b=b+a计算1 000次.现着重分析每条语句在污点传播框架下表达式及其污点操作的实现.对于Dalvik指令const/16 v3, 0x3e8, 在污点传播逻辑下表达为
通过上述污点传播分析, 污点跟踪代码有如下特征.
● 其一, 在程序逻辑向污点传播逻辑转化后, 污点传播逻辑对应的本地指令集变小.最主要包含以下4种: setTaintClear(*cUnit, rlDest)方法和setTaintClearWide(*cUnit, rlDest)方法编译为mov指令; loadTaintDirect(*cUnit, rlSrc, reg1)方法和loadTaintDirectWide(*cUnit, rlSrc, reg1)方法编译为ldr指令; storeTaintDirect(*cUnit, rlDest, reg1)方法和storeTaintDirectWide(*cUnit, rlDest, reg1)方法编译为str指令; opRegRegReg(cUnit, kOpOr, taint1, taint1, taint2)方法编译为orr指令.因此, 污点传播本地指令集主要包括ldr, str, mov和orr指令.相对arm指令集是非常小的一个子集.
● 其二, 程序逻辑向污点传播逻辑转化后, 污点传播代码具备了一些新的特征.例如, a=a+b和a=a-b虽然在程序逻辑下计算出的a数值不一样, 但在污点传播逻辑下, a的污点值是一样的.又如for (i=0; i < 100;i++) a=a+b, 在循环执行时, a的数值是一直变化的, 但在污点传播逻辑下, a的污点值是不变的.
● 其三, 在插入的污点跟踪代码中, 存在许多内存和寄存器之间存取数据的指令.比如, 要完成a=a+b, 就需要在内存中取a的污点值, 取b的污点值; 同时, 完成运算后, 还要将a的污点值保存到内存.
针对污点传播代码的特征(上述3种特征), 对经典流数据流算法进行改进, 提出了3种适应污点传播代码特性、针对性更强、效率更高的优化算法.主要改进体现在如下两个方面.
● 其一, 指令数据结构的改进.在dalvik即时编译过程中, 程序指令一般被组织为一条双向链表.而本文将程序指令和污点传播指令组织为一条双向链表, 污点传播指令又组织为另一条双向链表, 其开销只是在指令数据结构中加入*TAINT_PRE和*TAINT_NEXT.
● 其二, 数据流算法的改进, 由于污点传播指令单独组织, 优化算法只需遍历插入的污点传播代码, 无需遍历所有的程序指令.从而算法效率更高.
对于每一种优化算法, 都是依据上述污点传播代码的特征进行优化的.同时, 考虑在即时编译器下以最快速度进行污点跟踪优化, 优化算法在污点传播分析的同时进行污点跟踪优化, 而不像传统编译器将数据流分析和代码优化算法分开.
3.1 冗余污点存取消除冗余污点存取消除是指消除冗余的污点在寄存器和内存之间移动.以虚拟机指令add-int/2addr v0, v1和add-int/2addr v1, v0为例.Dalvik即时编译器将其转化为表 1第1列所示LIR(已将内存读指令集中并前置), 其中, r5表示栈针位置, 内存数据偏移量以字节为单位.对于第1条虚拟机指令add-int/2addr v0, v1, 首先, 由于污点值交叉保存在内存, 将变量v0和v1从偏移位置0和8处读入寄存器r1和r2, 并将其污点值从偏移位置4和12处读入寄存器r0和r3.然后, 将操作数及其污点进行数值运算adds r1, r1, r2和污点传播运算orr r0, r0, r3.最后, 将数值和污点值写回内存.同理, 对于第2条指令完成相同动作.由于即时编译器仅简单地将虚拟指令翻译为LIR指令, 因此产生的代码较为庞大和冗余.通过对虚拟机指令的污点传播分析, 可得出第1条指令和第2条指令变量值及其污点值在内存中位置一致, 此时, 第2条指令不需要再次读取操作数及其污点, 且第1条指令不需要立即将数值运算结果和污点传播运算结果保存到内存, 可在第2条指令执行完成后再保存相应数据值及其污点值.删除冗余的污点存取代码后优化结果见表 1第2列.
污点存取冗余是由于在污点传播代码中有大量无用的内存存取指令(数量几乎占插入代码的70%), 通过分析污点在内存与寄存器之间移动的特性, 可实现冗余污点存取消除.在区分必然别名和寄存器值不被破坏的情况下, 对于污点存取指令, 分以下4种情况讨论.
(1) 读后读(read after read, 简称RAR):数据污点值读取后又再次读取.对于此种情况, 如果污点数值在第1次读取内存与第2次读取内存之间不存在对该污点值的写入指令, 则可以删除后一条读取内存指令.
(2) 写后写(write after write, 简称WRW):数据污点值写入内存后又再次写入内存.对于此种情况, 如果污点数值在第1次写入内存与第2次写入内存之间对该污点值的读入指令, 则可以删除前一条污点值的写入指令.
(3) 读后写(read after write, 简称RAW):数据污点值在读取后写入内存.对于此种情况, 如果在读取和写入内存之间不存在该数据污点值的传播点和污染点, 则可将读取和写入内存指令删除; 如果在读取和写入内存之间存在对该数据污点值的传播点但不存在污染点, 则可将写入内存指令删除.
(4) 写后读(write after read, 简称WRA):数据污点值写入内存后读取.对于此情况, 则可将读取指令删除.
其具体算法如算法1所示.
算法1.冗余污点存取代码消除.
输入:编译单元*cUnit, 路径污点跟踪首指令*headLIR, 路径污点跟踪尾指令*tailLIR.
输出:编译单元*cUnit.
1. for (currentLIR=TAINT_PREV_LIR(t_tailLIR);
currentLIR!=t_headLIR; currentLIR=TAINT_PREV_LIR(currentLIR))
2. { if (!(EncodingMap[currentLIR→opcode].flags & (IS_LOAD|IS_STORE))) continue;
3. //判断当前污点传播指令类型是否为内存存取类型, 若否, 则继续循环
4. for (moveLIR=TAINT_PREV_LIR(currentLIR);
moveLIR!=t_headLIR; moveLIR=TAINT_PREV_LIR(moveLIR))
5. { if (!(EncodingMap[moveLIR→opcode].flags & (IS_LOAD|IS_STORE))) continue;
6. //判断当前污点传播指令类型为内存存取类型, 若否, 则继续循环
7. if (moveLIR→operands[0]=currentLIR→operands[0]& &
moveLIR→aliasInfo==currentLIR→aliasInfo)
8. //互为别名, 操作数本地寄存器一致且未被破坏
9. { if ((isCurrentLIRLoad & & isMoveLIRLoad)||(!isCurrentLIRLoad & & isMoveLIRLoad))
10. {moveLIR→flags.isNop=true; }
11. //将后一读取指令删除
12. else if (!isThisLIRLoad & & !isCheckLIRLoad)
13. {CurrentLIR→flags.isNop=true; }
14. //将前一污点写入指令删除
15. else if (isThisLIRLoad & & !isCheckLIRLoad)
16. { if (currntTaintMask==moveTaintMask)
17. moveLIR→flags.isNop=true; }
18. //将后一污点写入指令删除}
19. } end if
20. } //end for
21. } //end for
3.2 污点重复计算消除污点重复计算消除是指消除污点值的重复计算.同样以虚拟机指令add-int/2addr v0, v1与add-int/2addr v1, v0为例, 执行第1条Dalvik指令后, v0污点值更新为
对于污点重复计算消除, 由于其程序逻辑中复杂的数值计算都将转化为污点传播逻辑中的或运算, 因而会产生大量重复的计算表达式.针对这种污点传播代码的特性, 通过分析此种污点计算代码的特性, 给出污点重复计算消除算法.其实现的基本思想是:对于给定形如orr r0, r0, r1和orr r1, r1, r0表达式, 若其间不存在其他对r0与r1的污染点, 则可将后一表达式替换为执行速度更快的指令mov r1, r0.
其具体算法如算法2所示.
算法2.污点重复计算消除.
输入:编译单元*cUnit, 路径污染跟踪首指令*headLIR, 路径污点跟踪尾指令*tailLIR.
输出:编译单元*cUnit.
1. for (currentLIR=TAINT_PREV_LIR(tailLIR);
currentLIR!=t_headLIR; currentLIR=TAINT_PREV_LIR(currentLIR))
2. { if (!(EncodingMap[currentLIR→opcode].flags & (IS_ORR))) continue;
3. //判断当前污点传播指令类型是否为ORR类型
4. for (moveLIR=TAINT_PREV_LIR(currentLIR); moveLIR!=t_headLIR; moveLIR=PREV_LIR(moveLIR))
5. { if (!(EncodingMap[moveLIR→opcode].flags & (IS_ORR))) continue;
6. //判断当前污点传播指令类型是否为ORR类型
7. if (moveLIR→operands[0]=currentLIR→operands[0] & &
moveLIR→operands[2]==currentLIR→operands[2])
8. //操作数本地寄存器一致
9. {newLIR=dvmCompilerRegCopyNoInsert(cUnit, moveLIR→operands[0],
moveLIR→operands[2]);
10. dvmCompilerInsertLIRAfter(moveLIR, newLIR);
11. moveLIR→flags.isNop=true; }
12. //产生一条mov复制指令并插入, 同时, 将后一orr运算指令删除
13. else if (moveLIR→operands[0]==currentLIR→operands[0]||
moveLIR→operands[0]==currentLIR→operands[2])
14. break;
15. //操作数在该处污染, 结束当前循环, 在外循环中检查下一条currentLIR
16. } //end for
17. } //end for
3.3 循环不变污点传播代码外提循环是程序中不可缺少的一种控制结构, 因为循环中的代码要重复执行, 所以对循环代码的污点优化效果十分明显.循环不变污点传播代码外提, 是指将循环体中反复进行污点值运算但污点值不变的代码提取到循环体必经后置基本块.仍然以第2节的dalvik代码为例, 即时编译器探测到此循环并选择add-int/2addr v0, v1和add-int/lit8 v2, v2, 0x1和if-lt v2, v3, :goto_0为热点路径, 并将其编译为7个基本块, 其中, 关键基本块Code Block与Normal Chaining Cell代码见表 2第2列.在程序逻辑下, 变量a的数值是循环变化的.但污点传播逻辑下, 变量a的污点值是循环不变的.同理, 对于循环归纳变量, 其污点值也是不变的.因此, 可将ldr r0, [r5, #4], ldr r3, [r5, #12], ldr r7, [r5, #28], orr r0, r0, r3等污点操作指令提取到循环必经后置节点, 见表 2第3列.
实现循环不变污点传播代码外提, 关键在于找到循环污点不变量, 分以下两种情况讨论.
● 第1是循环归纳变量, 循环归纳变量较容易分析, 其污染点和传播点都在PHI节点处, 且其数值加减某一常数.如示例代码add-int/lit8 v2, v2, 0x1, 当中v2是归纳变量, 其污点值在循环过程中不变.
● 第2是非归纳不变量, 非归纳不变量分析较为复杂.第1种情况是某变量污染点和传播点都在一处且传播点位于该处的其他变量在循环体内不存在污染点, 如示例代码add-int/2addr v0, v1满足此类情况, v0寄存器的污染点和传播点都在该指令处, 且v1寄存器在循环其他处不存在污染点; 第2种情况是某变量污染点和传播点都在一处且传播点位于该处的其他变量是循环污点不变量, 如示例代码add-int/2addr v0, v1与add-int/2addr v1, v0中, v0和v1的污点值均是循环不变量.第2种情况需要使用迭代算法, 由于污点传播框架中污点值域格具有有穷的高度, 且是单调的, 可证明迭代算法是收敛的.其证明过程可参见编译原理中数据流分析算法敛散性证明[29].
因而, 循环不变污点传播代码外提算法如算法3所示.
算法3.循环不变污点传播代码外提算法.
输入:编译单元*cUnit, 循环体污点传播首指令*headLIR, 循环体污点传播尾指令*tailLIR.
输出:编译单元*cUnit.
1. for (currentLIR=t_headLIR; currentLIR!=t_tailLIR; currentLIR=TAINT_NEXT_LIR(currentLIR))
2. { if (!(EncodingMap[currentLIR→opcode].flags & (IS_ORR)) continue;
3. //判断当前污点传播指令类型是否ORR类型
4. findLIV=1;
5. for (moveLIR=TAINT_NEXT_LIR(currentLIR); moveLIR!=t_tailLIR;
moveLIR=TAINT_NEXT_LIR(moveLIR))
6. { if (moveLIR→operands[0]==currentLIR→operands[0] & &
!((moveLIR→operands[2]==const||isLIV(moveLIR→operands[2]))))
7. findLIV=0;
8. break; }
9. if (findLIV=1)
10. {newLIR=dvmCompilerCopyLIR(cUnit, moveLIR);
11. dvmCompilerInsertLIRAfter(chainingcellLIR, newLIR);
12. moveLIR→flags.isNop=true; }
13. //将循环不变污点传播代码外提
14. } //end for
15. } //end for
4 系统实现框架与测试 4.1 系统实现框架在Dalvik即时编译器基础上实现了污点传播编译优化技术, 其整体框架如图 3所示.
(1) 在解释器进行热点路径探测, 若该路径入口指令执行次数达到阈值threshold(40), 则编译该路径并进行污点传播优化; 否则, 不进行污点传播优化(冷路径优化代价过大).
(2) 创建编译线程, 完成MIR到SSA转换和基本的方法内联优化, 并填充MIR相应污点数据结构.
(3) 将MIR转换成LIR:首先, 依据程序逻辑向污点传播逻辑转化特点, 完成MIR指令污染点和传播点分析, 并将插入的污点跟踪指令组织为双向链表; 填充LIR相应污点数据结构(Taint_map), 并完成路径流图分析.若该路径是循环, 则需完成循环信息分析.
(4) 通过以上3种污点传播优化算法, 完成对以双向链表组织的污点跟踪指令的LIR进行污点传播优化.最后, 将LIR转化成机器码, 并返回路径将入口内存地址.
4.2 系统功能与性能测试本文所有测试均在模拟器上进行, 操作系统环境为os/Ubuntu-12.04, cpu/2.27GHZ, RAM/4GB, version/ Android-4.1.1.启动模拟器关键参数如下:emulator –kernel qumu-armv7 –ramdisk ramdisk.img –data userdata.img –sdcard sdcard.img –partition-size 500 –memory 512(本文原型系统OFCDroid和对比系统FCDroid可从http://pan.baidu.com/s/1pJC63uN处下载).
4.2.1 系统功能测试功能测试的目的在于测试污点优化正确性, 即在应用污点传播优化算法后, 与未优化前系统隐私泄露报告是否一致.测试用例使用系统应用和自制应用wzztest.apk, 测试用例包括了不同类型Dalvik指令OP_MOVE, OP_RETURN, OP_CONST, OP_AGET, OP_APUT, OP_IGET, OP_IPUT, OP_SGET, OP_SPUT, OP_INVOKE, OP_ INT_TO_LONG, OP_ADD_INT和OP_OR_INT.测试的隐私数据类型包括string, char, byte, int, long, float, doube和array.以自带短信程序在通过系统调用接口读取联系人息时, 短信程序与安卓系统间通信方法writeString()所含的路径将被编译为热点路径, 其测试结果如图 4所示.其中, 路径中包含的Dalvik指令如下.
const-string v1, “*”
new-instance v3, Ljava/lang/StringBuilder
invoke-virtual{v3, v1}, Ljava/lang/StringBuilder;
→append(Ljava/lang/String; ) Ljava/lang/StringBuilder;
move-result-object v4
其次, 使用污点跟踪测试床DroidBench[30]测试系统污点跟踪的正确性.DroidBench是专门针对安卓平台开发的污点跟踪测试工具, 可测试系统在数组污点跟踪、方法污点跟踪、指令污点跟踪、应用内部和外部通信污点跟踪和隐式污点跟踪等方面污点跟踪的正确性, 测试结果见表 3.在所选取的51个小测试中, OFCDroid检测到其中36个隐私泄漏并发出警告, 15个未发出警告, 7个误报.未发出警告是由于未跟踪隐式信息流, 误报是由于数组和字符串污点跟踪过于粗糙.OFCDroid与FCDroid各项测试结果均一致, 表明经过污点传播优化后, 污点跟踪仍然是正确的.
4.2.2 系统性能测试
首先测试污点传播优化算法对单条热路径的优化效果和优化代价, 优化效果主要通过编译后代码的大小来衡量, 代码越小, 其执行速度越快, 内存占用越少, 故优化效果更佳.优化代价主要通过编译每条热路径耗费时间长短来衡量, 编译时间越短, 优化代价就越低.选择安卓操作系统最常被编译为热点路径所属的方法作为测试对象, 其测试结果见表 4.
● 对于方法Ljava/io/File; fixSlashes, Android系统通过即时编译器编译后代码占用116字节内存空间, 编译耗时26 458ms; 加入污点传播机制后, FCDroid系统通过即时编译器编译后代码占用140字节内存空间, 编译耗时27 973ms; 引入污点传播优化机制后, OFCDroid系统通过即时编译器编译后代码占用128字节内存空间, 编译耗时31 196ms.编译器以11.5%的编译时间代价获取了8.5%的运行速度和内存占用的优化效果.
● 对于方法Ljava/lang/String; hashcode, 优化效果最佳达到14.2%, 但优化代价也最大.
● 对于方法Ljava/lang/character; isHighSurrogate, 其优化代价最小为2.8%, 但优化效果最差.
Android系统平均每条热路径占用102字节, 平均编译时间为23 095ms; FCDroid系统平均每条热路径占用127字节, 平均编译时间为25 056ms; OFCDroid系统平均每条热路径占用117字节, 平均编译时间为27 728ms.实验结果表明, 经过优化后, 每条路径平均少占用10字节, 相对于整条热路径指令, 污点跟踪优化算法的平均优化率为7.8%.相对于插入的污点跟踪指令, 污点跟踪优化算法平均优化率为38%.
然后, 测试各污点传播优化算法对于单条热路径的优化性能.优化性能主要通过各污点传播优化算法执行时间的长短来衡量, 执行时间越长, 算法相对性能就越差.同样选择上述表 4热点路径作作为测试对象, 其测试结果见表 5.
● 对于优化算法冗余污点存取消除, 平均优化时间1 180ms, 方法LAndroid/os/systemproperties; getint耗时最长为2 169ms.
● 对于优化算法污点重复计算消除, 平均优化时间135ms, 方法Ljava/io/File; fixSlashes耗时最长为222ms.
● 对于优化算法循环不变污点传播代码外提, 方法Ljava/io/File; fixSlashes和Ljava/lang/String; hashCode中路径包含循环, 平均优化时间1 936ms.由于其他路径不属于循环, 故其用时为0us.
其次, 选择常见系统应用并测试其使用性能.选择见表 6第1列所示的安卓应用程序作为测试对象, 每个应用分别进行20次使用测试, 并记录其平均执行时间和方差, 经过优化后的执行时间越短, 表明优化效果越好.系统优化效率的计算方法为
$ \text{(}Tim{{e}_{\text{FCDroid}}}\text{-}Tim{{e}_{\text{OFCDroid}}}\text{)/}Tim{{e}_{\text{FCDroid}}}\times \text{100 }\!\!%\!\!\text{ }\text{. } $ |
● 对于发送短信, 测试点击信息发送直至发送成功所需时间, Android系统耗时72ms; 加入污点传播机制后, FCDroid系统耗时86ms; 经过优化后, OFCDroid系统耗时78ms.污点跟踪优化后, 系统效率提高了9.3%.
● 对于拨打电话, 测试按下拨打键至系统硬件产生回应所需时间, 其优化效率为6.5%.
● 对于拍摄照片, 测试按下拍摄键至保存照片完成(照片大小约在546KB左右)所需时间, 其优化效率为6.8%.
● 对于微信聊天, 测试按下发送键至信息发送完成所需时间, 其优化效率为7.7%.
● 对于浏览网页, 测试按下前进键至网页完成显示所需时间, 其优化效率为6.3%.
● 对于读取联系人信息和浏览照片, 其优化效率分别为9.0%和6.2%.
● 对于压缩文件, 选择1M大小的单个txt文件, 测试开始压缩至压缩完成所需时间, 其优化效率为3.1%.相对来说优化效率偏低, 可能是由于压缩算法主要实现在.so文件中, 而本文工作是基于即时编译的污点跟踪优化, 是在将dalvik字节码编译转化为本地指令码过程中进行的污点传播优化.
整体上, 通过优化后, 系统效率平均提高了6.8%.
最后, 采用caffeineMark 3.0测试OFCDroid系统整体性能, 其测试结果如图 5所示.对于caffeineMark测试结果, 在float得分与logic得分上, OFCDroid与FCDroid差别并不明显, 由于其得分高低主要与硬件性能相关; 而在loop得分, OFCDroid比FCDroid多出26%.这是由于循环代码执行次数多, 容易被探测为热点路径且被编译为本地代码.以方法Ljava/lang/String; hashCode为例, 设其循环执行次数为n, 每条指令执行时间为mms, 其优化后节省指令数为8, 则对于该方法执行一次可节省8nmms.循环次数越多, 优化效果就越明显.
5 结束语
本文针对污点跟踪技术在移动隐私保护方面存在效率较低的问题, 提出了一种基于即时编译的动态污点传播优化方法.首先, 将程序逻辑精确抽象为污点传播逻辑, 简化污点传播分析复杂性; 然后, 提出了一个污点传播框架, 证明该框架下污点传播分析算法的正确性和有效性, 给出了污点传播代码优化算法的实现及算法的性能测试结果.实验结果表明, 该优化方法有效提高了动态污点跟踪系统的性能.由于污点传播优化精确性问题依赖于全局的污点传播分析和控制流分析, 还有待后续进一步的深入研究.
[1] | Wan ZY, Jiang X. Dissecting Android malware:Characterization and evolution. In:Proc. of the IEEE Symp. on Security and Privacy. Oakland:IEEE, 2012. 95-109.[doi:10.1109/SP.2012.16] |
[2] | Schwartz EJ, Avgerinos T, Brumley D. All you ever wanted to know about dynamic taint analysis and forward symbolic execution (but might have been afraid to ask). In:Proc. of the IEEE Symp. on Security and Privacy. Oakland:IEEE, 2010. 317-331.[doi:10.1109/SP.2010.26] |
[3] | Sun H, Li HP, Zeng QK. Statically detect and Run-time check integer-based vulnerabilities with information flow. Ruan Jian Xue Bao/Journal of Software, 2013, 24(12): 2767–2781 (in Chinese with English abstract). http://www.jos.org.cn/ch/reader/view_abstract.aspx?flag=1&file_no=4385&journal_id=jos [doi:10.3724/SP.J.1001.2013.04385] |
[4] | Chow J, Pfaff B, Garfinkel T, Christpher K, Rosenblum M. Understanding data lifetime via whole system simulation. In:Proc. of the USENIX Security Symp. Berkeley:USENIX, 2004. 321-336. |
[5] | Attariyan M, Flinn J. Automating configuration troubleshooting with dynamic information flow analysis. In:Proc. of the 9th OSDI. Berkeley:USENIX, 2010. 237-250. |
[6] | Nair SK, Simpson PND, Crispo B, Tanenbaum AS. A virtual machine based information flow control system for policy enforcement. Electronic Notes in Theoretical Computer Science, 2008, 197(1): 3–16 . [doi:10.1016/j.entcs.2007.10.010] |
[7] | Lam LC, Chiueh T. A general dynamic information flow tracking framework for security applications. In:Proc. of the 22nd Annual Computer Security Applications Conf. (ACSAC 2006). IEEE, 2006. 463-472.[doi:10.1109/ACSAC.2006.6] |
[8] | Myers AC, Liskov B. Protecting privacy using the decentralized label model. ACM Trans. on Software Engineering and Methodology, 2000, 9(4): 410–442 . [doi:10.1145/363516.363526] |
[9] | Hedin D, Sabelfeld A. Information-Flow security for a core of javaScript. In:Proc. of the IEEE 25th Computer Security Foundations Symp. (CSF). Cambridge:IEEE, 2012. 3-18.[doi:10.1109/CSF.2012.19] |
[10] | Efstathopoulos P, Krohn M, VanDeBogart S, Frey C, Ziegler D. Labels and event processes in the Asbestos operating system. In:Proc. of the SOSP. Brighton:ACM Press, 2005. 17-30.[doi:10.1145/1095810.1095813] |
[11] | Krohn M, Yip A, Brodsky M, Cliffer N, Kaashoek MF, Kolher E. Information flow control for standard OS abstractions. In:Proc. of the ACM SIGOPS Operating Systems Review. New York:ACM Press, 2007. 321-334.[doi:[10.1145/1294261.1294293]] |
[12] | Yang Z, Yin LH, Duan MY, Wu JY, Jin SY, Guo L. Generalized taint propagation model for access control in operation systems. Ruan Jian Xue Bao/Journal of Software, 2012, 23(6): 1602–1619 (in Chinese with English abstract). http://www.jos.org.cn/ch/reader/view_abstract.aspx?flag=1&file_no=4083&journal_id=jos [doi:10.3724/SP.J.1001.2012.04083] |
[13] | Portokalidis G, Homburg P, Anagnostakis K, Bos H. Paranoid Android:Versatile protection for smartphones. In:Proc. of the 26th Annual Computer Security Applications Conf. ACM Press, 2010. 347-356.[doi:10.1145/1920261.1920313] |
[14] | Chen S, Kozuch M, Strigkos T, Ryan M, Gibbons PB. Flexible hardware acceleration for instruction-grain program monitoring. ACM SIGARCH Computer Architecture News, 2008, 36(3): 377–388 . [doi:10.1145/1394608.1382153] |
[15] | Ruwase O, Gibbons PB, Mowry TC, Ramachandran V, Chen S, Kozuch M. Parallelizing dynamic information flow tracking. In:Proc. of the 20th Annual Symp. on Parallelism in Algorithms and Architectures. ACM Press, 2008. 35-45.[doi:10.1145/1378533.1378538] |
[16] | Chow J, Garfinkel T, Chen PM. Decoupling dynamic program analysis from execution in virtual environments. In:Proc. of the USENIX 2008 Annual Technical Conf. Berkeley:USENIX, 2008. 1-14. |
[17] | Jee K, Kemerlis VP, Keromytis AD, Portokalidis G. ShadowReplica:Efficient parallelization of dynamic data flow tracking. In:Proc. of the 2013 ACM SIGSAC Conf. on Computer & Communications Security. ACM Press, 2013. 235-246.[doi:10.1145/2508859.2516704] |
[18] | Jee K, Portokalidis G, Kemerlis VP, Ghosh S, August DI. A general approach for efficiently accelerating software-based dynamic data flow tracking on commodity hardware. In:Proc. of the 19th NDSS. San Diego:Internet Society, 2012. 324-335. |
[19] | Chang W, Streiff B, Lin C. Efficient and extensible security enforcement using dynamic data flow analysis. In:Proc. of the 15th ACM Conf. on Computer and Communications Security. Alexandria:ACM Press, 2008. 39-50.[doi:10.1145/1455770.1455778] |
[20] | Ho A, Fetterman M, Clark C, Warfield A, Hand S. Practical taint-based protection using demand emulation. ACM SIGOPS Operating Systems Review, 2006, 40(4): 29–41 . [doi:10.1145/1218063.1217939] |
[21] | Portokalidis G, Bos H. Eudaemon:Involuntary and on-demand emulation against zero-day exploits. In:Proc. of the 2008 EuroSys. ACM Press, 2008. 287-299.[doi:10.1145/1352592.1352622] |
[22] | Saxena P, Sekar R, Puranik V. Efficient fine-grained binary instrumentation with applications to taint-tracking. In:Proc. of the 6th CGO. ACM Press, 2008. 74-83. |
[23] | Kim HC, Keromytis AD. On the deployment of dynamic taint analysis for application communities. IEICE Trans. on Information & Systems, 2009, 92(3): 548–551 . |
[24] | Qin F, Wang C, Li Z, Kim H, Zhou Y. Lift:A low-overhead practical information flow tracking system for detecting security attacks. In:Proc. of the 39th Annual IEEE/ACM Int'l Symp. on Microarchitecture. IEEE, 2006. 135-148.[doi:10.1109/MICRO.2006.29] |
[25] | Kemerlis VP, Portokalidis G, Jee K, Keromytis AD. libdft:Practical dynamic data flow tracking for commodity systems. ACM SIGPLAN Notices, 2012, 47(7): 121–132 . [doi:10.1145/2365864.2151042] |
[26] | Enck W, Gilbert P, Han S, Tendulkar, Chun BG. TaintDroid:An information-flow tracking system for realtime privacy montoring on smartphones. In:Proc. of the OSDI. Berkeley:USENIX, 2010. 255-270.[doi:10.1145/2494522] |
[27] | Huang Y, Chen Y, Yang W, Shann JJ. File-Based sharing for dynamically compiled code on Dalvik virtual machine. In:Proc. of the Int'l Computer Symp. IEEE, 2010. 489-494.[doi:10.1109/COMPSYM.2010.5685462] |
[28] | Ling M, Wu JP, Feng KH. An adaptive compilation system based on the dalvik virtual machine. Acta Electronica Sinica, 2013, 41(8): 1622–1627 (in Chinese with English abstract). [doi:10.3969/j.issn.0372-2112.2013.08.027] |
[29] | Aho AV, Sethi R, Ullman JD. Compilers, Principles, Techniques. 2nd ed., Addison Wesley Publishing Company, 1986. 688-703. |
[30] | Fritz C, Arzt S, Rasthofer S, Bodden E, Bartel A. Highly precise taint analysis for android application. Technical Report, TUD-CS-2013-0113, 2013. http://www.bodden.de/pubs/TUD-CS-2013-0113.pdf |
[3] | 孙浩, 李会朋, 曾庆凯. 基于信息流的整数漏洞插装和验证. 软件学报, 2013, 24(12): 2767–2781. http://www.jos.org.cn/ch/reader/view_abstract.aspx?flag=1&file_no=4385&journal_id=jos [doi:10.3724/SP.J.1001.2013.04385] |
[12] | 杨智, 殷丽华, 段洣毅, 吴金宇, 金舒原, 郭莉. 基于广义污点传播模型的操作系统访问控制. 软件学报, 2012, 23(6): 1602–1619. http://www.jos.org.cn/ch/reader/view_abstract.aspx?flag=1&file_no=4083&journal_id=jos [doi:10.3724/SP.J.1001.2012.04083] |
[28] | 凌明, 武建平, 冯克环. 一种Dalvik虚拟机的自适应编译系统. 电子学报, 2013, 41(8): 1622–1627. [doi:10.3969/j.issn.0372-2112.2013.08.027] |