Page 14 - 《软件学报》2020年第10期

2990 Journal of Software 软件学报 Vol.31, No.10, October 2020

果,其中,Kill 将消除表达式的污点状态,Gen 将生成表达式的污点状态:
InState(block)= p pred(block) OutState(p) (3)
OutState(block)=Gen(block) (InState(block)–Kill(block)) (4)
对于包含循环的函数,将迭代计算每个基本块的 InState 和 OutState,直到该基本块的 InState 和 OutState 的
状态不再改变.函数的污点状态与函数出口基本块的 OutState 相同.这样,就可以得到函数内所有表达式与相应
函数形参之间的污点关系,即为该函数 f 的污点摘要 TS(f).
对于每个函数 f,其形参列表为 A={a 1 ,a 2 ,…},函数中每个变量 v 的污点状态记为 T(v),其值可能是被污染、
无污染或依赖于函数的形参,即
⎧ tainted
⎪
T () v = ⎨ untainted (5)
⎪
⎩ ∪ aA′ Ta { a i ( , ), i A } | RelyOn a v a ∈
(), A′ =
i
∈
2.3.3 按需过程间污点分析
首先将入口函数的参数标记为污染的.然后从入口函数开始,对 FS 的所有函数依据调用图上的拓扑顺序分
析,通过函数调用语句,在调用点将实参的污点值传递给函数形参,计算得到 FS 中每个函数形参的污点值.如果
有多个函数调用同一函数,则被调用函数的参数污点值是其所有调用者实参的污点值之和.
f
对于函数 f 的第 i 个形参 a i ,其污点值是 f 所有调用者 Caller 1 ,…,Caller j 相应实参 p i 的污点值之和,即
j
( Ta f ) i T (= ∪ caller k ) p .
i
k = 1
当需要查询程序中表达式的污点状态时,如果发现可以直接得到污点值,则直接返回(tainted/untainted);否
则,表示该表达式的污点状态依赖于函数的形参,此时只需要将所依赖的函数形参的污点值 T(a)代入到公式(5)
第 3 个赋值中即可得到原表达式的污点值.
2.3.4 示例解析
如图 2 所示的代码片段,其中,函数 f 的控制流程图如图 5 所示,图 5 中冒号后的数字是入口语句的行号.分
析可知,4 个数组表达式的数组下标为 n、2 和 i.通过对函数 f 进行污点分析,可以知道 f 中的变量 n 和 i 的污点
值与 f 的参数 m 一致.然后对 main 函数进行污点分析,argc 和 argv 由外部输入,因此是污染的.由于 main 函数通
过参数 argc–1 调用函数 f,导致函数 f 的形参 m 为污染的.进而,f 中的变量 n 和 i 也是污染的.

Fig.5 CFG of function f in test.c
图 5 示例 test.c 函数 f 的控制流程图
2.4 数组越界缺陷检测
对于每一条数组访问语句 arr[idx],数组 arr 对应的数组长度列表为{len 0 ,len 1 ,…,len n },其数组越界缺陷的检
测结果记为 W(arr[idx]),W(arr[idx])≡T 表示该数组访问语句会导致数组越界,W(arr[idx])≡F 表示该数组访问语