Motivation
CHA 只看定义类型,会得到很多实际不被调用的子类方法,如下图所示,CHA的常量分析时只能得到NAC
而指针分析会得到更精确的对象类型:
Introduction to Pointer Analysis
A fundamental static analysis, computes which memory locations a pointer can point to.
For object-oriented programs, computes which objects a pointer (variable or field) can point to.
即指针分析[1]用于分析一个指针究竟指向哪一块内存,对于面向对象程序,指针分析可用于分析一个指针指向哪一个变量或者域。
指针分析是may分析。
指针分析和别名分析
指针分析回答指针指向哪一个对象(内存)的问题
别名分析回答两个指针是否指向同一对象(内存)的问题
指针分析的应用
- 基础信息构建
- Call graph、别名分析
- 编译器优化
- Bug检测
- 空指针异常
- 安全分析
- 信息流分析
Key Factors of Pointer Analysis
指针分析是一个复杂系统,很多因素影响了指针分析的准确度和效率:
Factor | Problem | Choice |
---|---|---|
Heap abstraction | 如何对堆内存建模 | 1. Allocation site*; 2. Storeless |
Context sensitivity | 是否上下文敏感 | 1. Context-sensitive*; 2. Context-insensitive* |
Flow sensitivity | 是否流敏感 | 1. Flow-sensitive; 2. Flow-insensitive* |
Analysis scope | 分析范围 | 1. Whole-program*; 2. Demand-driven |
打“*”号的为本课程介绍的分析方法。
Heap Abstraction(堆抽象)
在静态分析视角中,程序中会创建无限数量的对象实例(考虑到难以分析循环/递归终止条件),为了保证指针分析能够终止,需要将无限数量的对象抽象为有限数量的对象
如上图所示,主要有两大流派[2]:
- Store based model
- Storeless model
其中,Store based model 中的 Allocation sites 较为常用,其抽象依据是同一创建点的对象为同一对象:
上下文敏感
指针分析过程中如何对调用上下文建模,主要分为两种
- 上下文敏感
- 每一个上下文分析一次
- 每次调用时,不同上下文方法对象不一样,重复分析函数
- 上下文不敏感
- 同一个函数只分析一次
- 分析时合并所有调用的输入
- 一般地精度较低
下图左侧为上下文敏感,右侧为上下文不敏感:
个人认为对于特定的分析(如污点分析)做好函数摘要(summary)后,就可以做上下文不敏感的分析,同时不损失精度。
流敏感
做指针分析时,对控制流的处理
- 控制流敏感[4]
- 考虑执行顺序
- 维护每一程序点的指针指向关系
- 控制流不敏感
- 保存所有可能指向的对象
如上图代码中,控制流敏感(蓝色)对每个程序点都做了记录,而控制流不敏感(橘色)则保存指针的所有可能指向;
先前的数据流分析都是流敏感的,而在java语言的指针分析中,Flow-sensitive效果未必比Flow-insensitive好,因此主要介绍 insensitive。
Analysis Scope
指针分析可以分析全程序,也可根据需要分析部分代码中的指针信息:
- Whole-program
- 分析程序所有信息
- Demand-driven
- 分析部分指针信息
- 计算量比全程序小
- 但考虑到依赖,所以计算速度未必更快
Concerned Statements
Java中的指针
- 本地变量(local variable),e.g.,
x
- 静态域(static field), e.g.,
C.f
,作为全局变量分析,与本地变量分析方法类似(本课不做讨论) - 对象域(instance field),e.g.,
x.f
,实例对象的属性 数组元素(array element),e.g., array[i],由于静态分析没法计算数组下标,通用做法将其作为single field,与处理instance field类似(本课不做讨论)
如上图所示,原先数组下表的访问
array[0]
变为array.arr
。
与指针分析相关的语句
- New:
x = new T()
- Assign:
x = y
- Store:
x.f = y
- Load:
y = x.f
- Call:
r = x.k (a, ...)
注意对于真实场景下 x.f.g.h=y
的情况,在三地址码表示时可以用临时变量做简化,变为t1=x.f; t2=t1.g; t2.h=y
对于对象调用(Call)语句,存在三种调用类型:
- Static call:
C.foo()
- Special call:
super.foo()/x.<init>()/this.privateFoo()
- Virtual call:
x.foo()
由于 static call和special all 都只有一种函数原型,因此只需分析virtual call的情况。
Pointer Analysis: Rules
Domains and Notations
以下为需要用到的定义:
- 变量:$x,y \in V$
- 域(Fields):$f,g\in F$
- 对象(Objects):$o_i, o_j \in O$
- 实例属性(Instance fields):$o_i.f, o_j.g \in O \times F$
- 指针:$Pointer = V \cup (O \times F)$
注:
- $P(O)$ 指$O$的幂集
- $pt(p)$ 表示指向 $p$ 的指针集合
Rules
$\frac{a}{b}$为推导符号,即如果条件 $a$ 满足,那么 $b$ 也满足(在infer那也介绍过此符号),个人感觉可以理解为$\{a\}stmt\{b\}$,也可以理解为满足$a$ 后,进行$b$操作。
New,
i: x = new T()
,新建对象时, $o_i$ 加入指针集中 (写法不同):Assign,
x = y
,出现赋值后,让y指向的内容指向x:Store,
x.f = y
,赋值给属性时,将指向 $y$ 的指针也放入 $o_{i}.f$ 的集合中:
- Load,
y = x.f
,属性赋值给变量时,指向 $o_i.f$ 的指针指向 $y$:
下图给出四种情况的形象表示:
How to Implement Pointer Analysis
Pointer analysis is to propagate points-to information among pointers (variables & fields).
指针分析就是在变量和域(指针)中传递指向内存的信息。
也有观点是指针分析就是求解一系列指针的约束条件[3]。
Pointer Flow Graph
因此使用图来保存指针之间的关系,当指针 x 变化时,同时需要改变 x 后继指针的指向内容。
Pointer flow graph of a program is a directed graph that expresses how objects flow among the pointers in the program.
图中的点为指针(变量或者抽象对象实例的域/属性):
Nodes:$Pointer = V \cup (O \times F)$
图中的边 $x \rightarrow y $ 表示指针 $x$ 指向的对象也被 $y$ 指向($x$ 的指针信息流向 $y$ )
Edges:$Pointer \times Pointer$
因此,先前的四条语句产生的边可以用下图表示:
Pointer Analysis: Algorithms
Worklist
$WL \subseteq \left \langle Pointer, \mathcal{P}(O)\right \rangle^*$, 即WL中的元素为$n, pts$,表示指针$n$可能指向的内存/对象集合为 $pts$
加边函数 AddEdge():
1 | def AddEdge(s, t): |
即若添加 $s \rightarrow t$ ,首先检查该边是否在PFG中,若不存在,则将该边加入PFG;并且检查 s 指向的内存集合,如果集合不空,则需保证 $s$ 指向的内容被 $t$ 指向,即加入工作队列中。
指针传播函数 Propagate():
1 | def Propagate(n, pts): |
即 pts 不为空时,将 $pts$ 内容存入 $n$ 的指针集合中,接着找n的后继s,对每一个s,将 <s, pts> 加入WL。
主函数 Solve()
:
1 | def Solve(s): |
首先可以看到,在9、11、19和21行分别处理了new、assign、store和load操作:
- 对于new操作,直接将 $\left \langle x, o_i \right\rangle$ 加入worklist
- 对于assign操作,将x指向的内容也被y指向,即调用
AddEdge()
接下来进入循环,直到工作队列为空:
- 取出队头要处理的指针n和其对应的pts
- 求差异 Δ,pts中的有一些地址先前已经传播过,只需处理剩余部分
- 调用
Propogate()
,将 Δ 内容放入 $pt(n)$ 并且添加新的work
接着需要处理对象操作,17-18的行意指若指针n表示的是一个变量(而不是field),那么对于每一个 Δ 中的对象实例,处理所有与 $x.f$ 相关的 store 和 load 操作,对 store 和 load 操作都是使用AddEdge()
处理(19-22行)。
具体示例
考虑如下代码:
1 | b = new C(); |
首先经过solve():L9-12
的初始化:
- WL=[<b,{o1}>, <c,{o3}>]
PFG:
graph RL b("b{}") --> a("a{}") c("c{}") --> d("d{}")
处理<b,{o1}>: 主要执行第16行Propagate()
- WL=[<c,{o3}>, <a,{o1}>],因为b→a,所以增加了一个新work
- PFG:
graph RL b("b{o1}") --> a("a{}") c("c{}") --> d("d{}")
处理<c, {o3}>,除了propagate(c, {o3})
,注意到第 4 行和第 6 行,所以还需处理store,即AddEdge(a,o3.f)
,AddEdge(d,o3.f)
,因为目前 a 和 d 指向内容都是空集,所以 WL 不增加:
- WL=[<a,{o1}>, <d,{o3}>]
- PFG:
graph RL b("b{o1}") --> a("a{}") c("c{o3}") --> d("d{}") a-->o3.f["o3.f{}"] d-->o3.f
处理<a,{o1}>,propagate(a, {o1})
:
- WL=[<d,{o3}>, <o3.f, {o1}>]
- PFG:
graph RL b("b{o1}") --> a("a{o1}") c("c{o3}") --> d("d{}") a-->o3.f["o3.f{}"] d-->o3.f
处理<d,{o3}>,propagate(d, {o3})
, 以及注意到第 7 行的 load 语句,调用AddEdge(o3.f,e)
:
- WL=[<o3.f, {o1}>, <o3.f, {o3}>]
PFG:
graph RL b("b{o1}") --> a("a{o1}") c("c{o3}") --> d("d{o3}") a-->o3.f["o3.f{}"] d-->o3.f o3.f --> e("e{}")
后面步骤省略,最后 PFG 结果为:
graph RL b("b{o1}") --> a("a{o1}") c("c{o3}") --> d("d{o3}") a-->o3.f["o3.f{o1, o3}"] d-->o3.f o3.f --> e("e{o1, o3}")
可以看到 PFG 中已经记录了每个指针变量可能指向的对象。
Pointer Analysis with Method Calls
在分析 call statments 时,需要做过程间分析,即需要构建 call graph,已知的 CHA 构建的 call graph 是不准确的,本节课介绍如何使用指针分析本身构建 call graph,即完成跨函数的指针分析。
Rule: Call
对于之前忽略的 Call stmt,有如下推导规则:
主要有4部分:
- 由 $Dispatch(o_i, k)$ 获取目标方法,$Dispatch()$ 实现与之前 CHA 分析相同:
- 被$x$ 指向的对象$o_i$ ,也被 $m_{this}$ 指向;
- 对于每一个实参$a_j$所指向的信息,也被形参 $m_{pj}$ 所指向——在PFG上增加 “实参→形参”边;
- 对于被返回值 $m_{ret}$ 指向的对象$o_v$,也被等号左边变量 $r$ 指向——在PFG上增加“ret→r”的边。
讨论为什么对于 $m_{this}$ 不增加边,而对其他参数就增加边:
注意到 $x$ 指向的信息是一个集合,而 $m_{this}$ 由$Dispatch()$ 解析后可以唯一确定一个对象,换句话说:
对于this来说,指针分析已经可以唯一确定该对象实例,若传递 $x$ 的指向对象集合反而造成分析不准确,如下图所示:
对于其他参数,指针分析无法确定它们的唯一对象实例,为保证may分析,需要传递先前所有可能性,即可能指向的集合。
归根结底,this和不同参数还是有区别的,this的实例参与了 Dispatch 过程。
Interprocedural pointer analysis
- 和其他过程间分析一样,过程间指针分析需要指定一个函数入口
- 过程间指针分析一边做指针分析,一边构造调用图
- 由入口出发不断探索未知函数,直到所有可被探索的函数都被处理完成,这样既可以提高效率,又可以提高精度
Algorithm
1 | def Solve(s): |
与单函数的指针分析不同,主要变化在12、13、14、15和26行,在函数初始化阶段,增加可达语句集合、可达函数集合和调用图,以及对 new 和 assign 的处理放在了 AddReachable()
函数中,在变化的每个对象实例中,通过 ProcessCall()
处理call stmt——当n为一个变量时调用。
AddReachable(m)
AddReachable(m)
函数用于将新的方法 $m$ 加入可达集合中,同时处理 $m$ 中 new 和 assign 语句,处理方法与单函数类似:
1 | def AddReachable(m): |
ProcessCall(x, 𝑜𝑖)
$ProcessCall(x,o_i)$ 用于处理 call 语句,算法如下:
1 | def ProcessCall(x, 𝑜𝑖): |
Example
设有如下待分析代码:
1 | class A { |
首先程序初始化,有如下结果:
- worklist,由3、4行的new stmt:
WL=[<a,{o3}>,<b,{o4}>] - RM,
A.main()
成为已知函数:
RM={A.main()} - CG={}
- PFG为空,因为没有assign
进入循环,处理 <a,{o3}>:
a
没有store、load和call,因此只做propagate(a,{o3})
- WL=[<b,{o4}>]
- RM={A.main()}
- CG={}
- PFG:
graph RL a("a{o3}")
处理 <b,{o4}>:
- 先做
propagate(b,{o4})
; - 由于第5行存在调用,执行
ProcessCall(b, o4)
,在函数中,首先解析到调用函数为m=B.foo(A)
,将 <B.foo/this. {o4}> 加入 worklist; - 接着由于之前没有分析过该函数调用:
- 将
5→B.foo(A)
加入CG
- 将
- 调用
AddReachable()
- 将
B.foo(A)
加入到已知函数 - 注意到11行存在new操作,将{<r, o11>}加入worklist
- 调用
AddEdge(ai, pi)
,更新PFG - 调用
AddEdge(r, c)
,更新PFG
- 将
处理结果为:
- WL=[<B.foo/this, {o4}>, <r, {o11}>, <y, {o3}>]
- RM={A.main(), B.foo(A)}
- CG={5→B.foo(A)}
- PFG:
graph RL a("a{o3}")-->y("y{}") b("b{}") r("r{}")-->c("c{}")
处理<B.foo/this, {o4}>
:
只需要做Propagate(B.foo/this, {o4})
- WL=[<B.foo/this, {o4}>, <r, {o11}>, <y, {o3}>]
- RM={A.main(), B.foo(A)}
- CG={5→B.foo(A)}
- PFG:
graph RL a("a{o3}")-->y("y{}") b("b{}") r("r{}")-->c("c{}") Bfoo("B.foo/this{o4}")
后续步骤类似,最后结果为:
- WL=[<B.foo/this, {o4}>, <r, {o11}>, <y, {o3}>]
- RM={A.main(), B.foo(A)}
- CG={5→B.foo(A)}
- PFG:
graph RL a("a{o3}")-->y("y{o3}") b("b{o4}") r("r{o11}")-->c("c{o11}") Bfoo("B.foo/this{o4}")
相关文献
- William E. Weihl, “Interprocedural Data Flow Analysis in the Presence of Pointers, Procedure Variables, and Label Variables”. POPL 1980.
- Vini Kanvar, Uday P. Khedker, “Heap Abstractions for Static Analysis”. ACM CSUR 2016.
- Lars Ole Andersen, 1994. “Program Analysis and Specialization for the C Programming Language”. Ph.D. Thesis. University of Copenhagen.
- Hardekopf B, Lin C. Flow-sensitive pointer analysis for millions of lines of code. CGO 2011:289-298.
- Lecture Notes on Pointer Analysis, https://www.cs.cmu.edu/~aldrich/courses/15-819O-13sp/resources/pointer.pdf