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

高凤娟 等:基于污点分析的数组越界缺陷的静态检测方法 2989

基于每个函数 f 的基本块 bb 中数组名 arr 的数组长度的集合 size(arr,f,bb)={s i ,s j ,…,s k },取其中的最大值记
为数组长度的上界 up,取其中的最小值记为数组长度的下界 low,则数组长度的区间为[low,up],如果数组长度为
外部输入的变量,无法确定上下界,则保留长度集合.
示例解析.如图 2 代码示例,遍历可知,在函数 f 中,共有 4 个数组表达式的使用位置,即 11 行的 s.noisy[n]、
12 行的 arr[2]和 16 行的 s.arr[i]以及 tmp[i].s.noisy[n]和 s.arr[i]均为结构体成员数组,可以直接定位其数组声明
位置为第 3 行、第 4 行,继而可知数组长度分别为 12 和 15.tmp[i]的数组声明位置为第 9 行,数组长度为 3.arr[2]
来自于函数参数,通过指针分析可知,动态数组 p 和 q 为 arr 的别名,因此 arr 数组长度集合为{j,k}.
2.3 按需污点分析
按需污点分析是指本文中的污点分析只针对程序中的数组下标和数组长度进行静态污点分析,包括过程
内和过程间污点分析.本文将外部输入(包括用户或文件的输入以及主函数的参数)作为污点源.通过污点传播,
可以得到程序中每个关注变量 v 的污点值 T(v),可以是被污染(tainted)或者无污染(untainted),即
T(v)∈{tainted,untainted}.
污点值的 tainted 可以对应布尔值 1,untainted 可以对应布尔值 0,因此可以使用逻辑运算符“或”(记为 来
计算污点值的和,即只要有一个子表达式的污点值为 tainted,则整个表达式的污点值为 tainted.
2.3.1 污点传播规则
对于污点分析中遇到的每条语句,将按照如下污点传播规则计算该语句的污点值.
常量.每个常量 c 是非污染的.比如字符串常量、整型常量和浮点型常量等.
T(c)=untainted.
类型转换.类型转换后的表达式 CastExpr(e)的污点值与原来类型的表达式 e 的污点值一致.
T(CastExpr(e))=T(e).
数组下标表达式.将被当作一个整体,数组的某一个元素被污染,则整个数组为污染的.结构体同理.
T(arr[i])=T(arr),T(expr.elem)=T(expr).
一元运算表达式.op expr 的污点值等于其中表达式 expr 的污点值.
T(op expr)=T(expr).
二元运算表达式.expr1 op expr2 的污点值等于子表达式 expr1 和 expr2 的污点值之和.
T(expr1 op expr2)=T(expr1) T(expr2).
三元运算表达式.expr1?expr2:expr3 的污点值等于子表达式 expr2 和 expr3 的污点值之和.
赋值表达式.赋值语句 expr1=expr2 将把右侧表达式的污点值传递给左侧变量.
T(expr1)=T(expr2).
条件语句.if c then expr1 else expr2 将把条件语句中条件表达式 c 的污点值传递给基本块中的赋值语句中
的左值.循环语句同理,同时,循环变量的污点值等于循环上界的污点值.
函数调用语句.设函数 f 有 n 个参数,对 f 的调用语句将把第 i 个实参 p i 的污点值传递给第 i 个形参 a i .
∀i∈[0,n),T(a i )=T(p i ).
同时,函数调用语句将把被调用函数返回值的污点状态传递给调用者被赋值的变量.
函数返回语句.如果返回的是变量,则函数返回值的污点值等于该变量的污点值;如果返回的是常量(包括
返回值为空),则函数返回值的污点值为 untainted.
2.3.2 按需过程内污点分析
污点分析前,首先统计程序中所有与数组下标和数组长度相关的函数,以及直到入口函数的所有调用者函
数,构成数组相关函数集合 FS.过程内的污点分析是对 FS 中的每个函数进行前向数据流分析.对于函数中的每
个基本块,使用 InState 表示一个基本块在该基本块入口时的污点状态,是其所有前驱基本块的 OutState 的并集,
代表在该基本块执行前所有表达式的污点状态;OutState 表示一个基本块在该基本块出口时的污点状态,是在
该基本块的 InState 的基础上,由该基本块中的语句按照上一节中的污点传播规则更新表达式的污点状态的结