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

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

2.2 数组长度区间分析
首先,定位数组下标访问语句,然后,通过后向数据流分析得到所关注数组名的别名,进而定位到数组声明
语句,每一个数组声明语句对应一个相应的数组长度.由于一个数组可能对应多个数组声明语句,因此,这一过
程将分析得到数组的长度区间,具体步骤如下.
数组长度区间分析.对于数组访问语句 arr[idx],在 AST 上判断是否存有数组声明大小,如果无法直接获取
数组声明大小,则进行指针分析,得到 arr 实际是某个或者某几个静态数组或动态数组的别名.
本文设计了一种流敏感、上下文敏感的按需指针分析.按需是指本文只对所关注的数组名(即通过被污染
数组下标访问数组元素的语句中的数组名)进行指针分析,目的是计算出数组名实际对应的静态数组或动态数
组表达式.对于每个函数 f,首先,统计每个基本块 block 中包含被污染的数组下标的数组表达式,然后从最底层包
含关注数组表达式的位置开始,向上进行一个后向数据流分析,后向数据流分析中,使用 OutState 表示一个基本
块在该基本块出口时的状态,是其所有后继基本块的 InState 的并集,如公式(1)所示,此处代表在该基本块每个
所关注的数组名对应的待分析的指针集合;InState 表示一个基本块在该基本块入口时的状态,如公式(2)所示,此
处是在其 OutState 的基础上,该基本块的赋值语句根据下文的指针处理规则对每个所关注的数组名对应的待分
析的指针集合进行杀死(kill)和生成(gen)的结果.
OutState(block)= s succ(block) InState(s) (1)
InState(block)=Gen(block) (OutState(block)–Kill(block)) (2)
指针分析时,InState 和 OutState 维护的是在某一个基本块中每个所关注的数组名 arr 对应的待分析的指针
集合 AliasSet={p 1 ,p 2 ,…,p n }.初始时,AliasSet={arr}.对于 AliasSet 中每一个指针 p,首先查询 AST 是否可以直接获
取静态数组声明的大小,如果可以,则将 AliasSet 中该元素 p 标记为终止点,停止对 p 进行指针分析;否则,继续对
p 进行指针分析,针对以下赋值语句,后向数组流分析的具体指针处理规则为:
• p=malloc(size)将 AliasSet 中的 p 替换为 malloc(size),并将 AliasSet 中该元素 malloc(size)标记为终止点,
停止对 malloc(size)进行指针分析.
• p=&a 将 AliasSet 中的 p 替换为&a.
• p=q 将 AliasSet 中的 p 替换为 q,后续数据流分析继续分析 q 的别名.
• p=*q 将 AliasSet 中的 p 替换为*q.
• *p=q 将 AliasSet 中的 p 替换为&q.
• p=g(…)将进入函数 g 中,从函数返回语句开始进行指针分析.
如果 AliasSet 中的元素包含&符号,形如&p,则在后续数据流分析中分析对 p 的赋值表达式,如果替换的新
指针为 q,则 AliasSet 中替换&p 为&q,如果新指针为*q,则 AliasSet 中&p 替换为&(*q),即替换为 q,以此类推.规则
中将 AliasSet 中的 p 替换为 q,对应着对 AliasSet 中杀死(Kill)p 和生成(Gen)q.
如果在函数 f 中没有定位到数组名对应的数组声明语句,则用相同方法分析该函数的所有调用者.以此类
推,直到定位到数组声明语句.由于不同的上下文、不同的分支将导致一个数组名可能存在多个数组声明语句
作为别名,其中,每一个数组声明语句将对应一个数组长度,因此,对于一个数组名 arr,通过指针分析将得到它的
一组数组长度{s 0 ,s 1 ,…,s n }.为了支持流敏感和上下文敏感,将在数据流分析过程中额外记录:(1) 每个基本块
block 的后继节点集合(计算方法参照公式(1)),记为 succs(block);(2) 在分析函数 f 时,过程间后向数据流分析的
函数调用链,记为 succs(f).对于数组名 arr,当在指针分析时,在函数 f 的基本块 bb 中定位到一个 arr 的数组声明
语句作为别名时(即 AliasSet 中的终止点之一记为 p 0 ),设 p 0 对应的数组长度为 s 0 ,则将记录 s 0 对应的有效函数和
基本块信息,有效函数信息为过程间后向数据流分析的函数调用链,即 ValidFuncs(s 0 )=succs(f),有效基本块信息
为所在基本块的后继节点集合,即 ValidBBs(s 0 )=succs(bb).最终,每个数组名 arr,记录一组数组长度{s 0 ,s 1 ,…,s n },
且其中每一个数组长度 s i 记录该值的作用域,即有效函数 ValidFuncs(s 0 )=succs(f)和有效基本块 ValidBBs(s 0 )=
succs(bb),并由此推导出每个函数 f 的每个基本块 bb 中数组名 arr 对应的数组长度的集合 size(arr,f,bb)={s i ,
s j ,…,s k }.