Page 133 - 《软件学报》2021年第6期

张捷 等:基于污染变量关系图的 Android 应用污点分析工具 1707

以避免形成回路.当一轮迭代结束时,如果此轮迭代生成新的 TVG 边或谓词,则启动新一轮迭代继续检测;否则,
算法结束.需要说明的是:启动新一轮迭代主要是因为在前一轮迭代中,新生成的污染变量或谓词可能在下一轮
迭代产生新的污染变量或谓词,需要进一步检测.当程序中存在较复杂的污染流时,例如跨越多个方法或者包含
较多别名,算法可能需要更多的迭代,从而找出所有污染变量.
我们以图 1 程序为例,算法在分析图 1(a)方法中语句 3~语句 5 时,分别使用 R1,R8,R10 生成序偶〈SC 1 ,a〉,〈a,b〉
和谓词 Param(Send,1,b);在分析图 1(b)方法时,语句 1、语句 3、语句 4 分别使用 R4,R7,R14(语句 1 在 Jimple 代
码中对应一条参数声明语句),生成序偶〈b,x〉,〈x,y〉,〈y,SK 1 〉,由此在一次迭代中可得到 TVG 边集 E={(SC 1 ,a),(a,b),
(b,x),(x,y),(y,SK 1 )}.在下一次迭代中,算法没有更新 TVG 或生成谓词,因此算法结束.值得说明的是:一些赋值语
句既可满足别名规则 R9 生成污染变量,也可满足清除规则 R16 生成 Clean 谓词.因为在现实程序中,一些别名关
系的形成本身伴随清除污染变量的效果.例如:x 是污染变量且是堆变量,如果赋值语句 x=y 发生在 x 被污染之
前,则仅仅是别名关系而没有清除作用;但如果发生在 x 被污染之后,则 x 被清除并指向 y 的内存,形成与 y 的别
名关系.因此,我们在使用规则时,对被清除的变量使用清除标记表明该变量被清除,在 TVG 中并不删除该节点,
并同样可以传播新的污染变量.而在之后的污染流验证过程,算法会根据具体语句执行顺序进行判定.
2.5 污染流提取和验证

根据 TVG 的性质,如果图中存在 SK 节点,则一定存在从 SC 到 SK 的可达路径.该路径上的顶点形成一条从
污点源经过污染变量到泄露点的变量序列,这条变量序列所表示的污染流,我们称为潜在污染流.路径上的边实
际上对应程序中发生污染传播过程的语句,路径上的边序列能够确定一条语句序列,我们称之为潜在污染路径.
因为 TVG 是根据污染变量的关系构建的,潜在污染流的生成没有考虑语句执行顺序和函数调用点情况,所以是
不准确的.为了提高精度,我们需要在函数调用图和控制流图找出一条合理的可执行路径,验证潜在污染流所对
应的潜在污染路径能够成功得到执行,从而证明潜在污染流的可行性.
一般来说,验证潜在污染路径就是要寻找一条可执行路径,使其完全符合潜在污染路径的语句顺序.图 3 中
展示了 3 个不同程序片段的控制流图.图 3(a)中的程序在构建 TVG 后,可以得到从 SC 到 SK 的可达路径为(SC,b,
c,SK),对应的潜在污染路径是(2,3,4),我们在验证此潜在污染路径时,只需沿着控制流图的执行顺序一一确认,即
可验证该潜在污染流成立,如图中蓝色曲线所示.但是,当涉及别名规则生成的污染变量和被清除的污染变量
时,我们需要根据情况判断潜在污染路径.在图 3(b)中的程序,TVG 的可达路径是(SC,b.str,c.str,SK),对应的潜在
污染路径是(3,2,4),不存在可执行路径满足该潜在污染路径.由于变量 b.str 对 c.str 的污染传播是在 b 被污染前
的别名声明中发生的,我们对由别名规则产生的污染变量的语句增加一条反向的搜索,如图中红色曲线所示,之
后可找到一条执行路径(2,3,4)满足条件,由此可验证污染流成立.需要说明:假如别名声明语句 b=c 出现在语句 3
之后,虽然别名关系可以生成,但语句同时满足变量 b 的清除规则,所以无法形成污染流.假如别名声明语句 2 改
为 c=b,该语句无论出现在语句 3 之前还是之后都可以形成污染流.在图 3(c)中,污染变量 a 在语句 3 中被赋值为
null,此时污染变量 a 被清除,而在 TVG 中仍会得到可达路径(SC,a,SK)和潜在污染路径(2,4),但我们定义的清除
规则中会标记变量 a 并记录语句 3,在搜索可执行路径时,如果在语句 2 后面存在语句 3,则终止此条路径的搜索
并验证此污染流不成立.验证潜在污染流的相关算法和实现细节我们会在下一节详细解释.

1 String b, c; 1 TestClass b, c; 1 String a;
2 b=Source( ); 2 b=c; 2 a=Source( );
3 c=b; 3 b.str=Source( ); 3 a=null; ×
4 Sink(c); 4 Sink(c.str); 4 Sink(a);

(a) (b) (c)
Fig.3 Control flow graph of code snippets with taint flows
图 3 含有污染流的代码片段的控制流图