Page 137 - 《软件学报》2021年第6期
P. 137
张捷 等:基于污染变量关系图的 Android 应用污点分析工具 1711
• 清除规则:对于赋值语句,若左值是污染变量,右值为常量、空值或非污染变量,则该污染变量被清除;
• 特殊规则:当识别出特殊规则规定的污染方式时,执行对应的特殊操作.
3.5 污染流提取及验证模块
在 TVG 构建完成之后,污染流提取及验证模块首先使用 GraphT 图形库计算 TVG 中所有从顶点 SC 到顶
点 SK 的可达路径,每条可达路径代表一条潜在污染流.路径由以 TaintedValue 对象为元素的数组(tv 1 ,tv 2 ,…,tv n )
表示,tv 1 和 tv n 分别表示顶点 SC 和 SK.然后,工具根据函数调用图和控制流图中的函数调用点和语句执行顺序
相关信息验证潜在污染流的可行性,TaintedValue 对象中包含的 Context 类型的 stmt 成员提供了语句位置信息,
我们按照该语句位置在控制流图上定位语句,并分段搜索是否存在符合要求的可达路径,即,每次确认相邻两个
TaintedValue 对象的 stmt 语句之间是否存在可达路径.最后,工具将删除虚假的潜在污染流,保留并输出可行的
污染流.算法 1 给出了验证潜在污染流可行性的具体步骤,算法输入为 TVG 上的一条潜在污染流以及 app 的函
数调用图和控制流图,输出为表示潜在污染流是否可行的布尔值.算法的大致思路是:分段搜索符合要求的可执
行路径,在搜索中遇到因别名规则产生的变量时会启动额外的反向路径搜索;另外,每段符合要求的路径上不能
存在当前变量或者其别名的清除语句.算法的具体解释如下.
第 1 行、第 2 行进行变量的初始化,其中:tv_c,tv_d 分别表示污染流每段的当前污染变量和目标污染变量,
cleanSet 存储清除当前污染变量及其别名变量的语句集合.
第 3 行启动循环,对潜在污染流分段进行验证,在确定所有污染变量后循环结束.
第 4 行~第 11 行:当 tv_d 是由别名规则生成的污染变量时,首先搜索从 tv_d 到 tv_c 的反向路径,如果存在反
向路径且路径不包含别名变量 tv_d 的清除语句,则在 cleanSet 中添加别名污染变量 tv_d 的清除语句,将 tv_d 更
新为下一个污染变量,tv_c 不改变,并跳过当前循环;如果反向路径包含别名变量 tv_d 的清除语句使得别名关系
不成立,则返回 false.
第 12 行~第 19 行:如果不存在从 tv_d 到 tv_c 的反向路径,则搜索从 tv_c 到 tv_d 的前向路径,如果存在前向
路径且路径不包含 cleanSet 中的清除语句,则在 cleanSet 中添加别名污染变量 tv_d 的清除语句,并且将 tv_c 更
新为 tv_d,将 tv_d 更新为下一个污染变量;如果不存在符合条件的路径,则返回 false.
第 20 行~第 27 行:当 tv_d 不是通过别名规则生成的污染变量时,搜索从 tv_c 到 tv_d 的前向路径.如果存在
路径且路径不包含 cleanSet 中的清除语句,将 cleanSet 更新为 tv_d 的清除语句,并且将 tv_c 更新为 tv_d,将 tv_d
更新为下一个污染变量;如果不存在符合条件的路径,则返回 false.
第 28 行、第 29 行:如果循环正常结束,则潜在污染流中的每一段都被验证,返回 true.
算法 1. 污染流验证算法.
输入:Flow=(tv 1 ,tv 2 ,…,tv n ),CG,CFG;
输出:true or false /*污染流是否可行*/.
1. tv_c=tv 1 ; i=2; tv_d=tv i ;
2. cleanSet=null;
3. while i≤n do
4. if tv_d.taintWay==TaintWay.ALIAS
5. path=findPath(tv_d.stmt,tv_c.stmt); //反向路径搜索
6. if path!=null
7. if checkOnPath(path,tv_d.cleanStmts)==false //检查 path 上是否存在 tv_d 的清除语句
8. cleanSet.addAll(tv_d.cleanStmts); //添加清除语句到 cleanSet
9. i++; tv_d=tv i ; continue;
10. else return false;
11. end if
12. else