0%

静态程序分析课程笔记(指针分析)

Motivation

CHA 只看定义类型,会得到很多实际不被调用的子类方法,如下图所示,CHA的常量分析时只能得到NAC

而指针分析会得到更精确的对象类型:

image-20200818213708639

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(堆抽象)

在静态分析视角中,程序中会创建无限数量的对象实例(考虑到难以分析循环/递归终止条件),为了保证指针分析能够终止,需要将无限数量的对象抽象为有限数量的对象
image-20200820210803574

如上图所示,主要有两大流派[2]:

  • Store based model
  • Storeless model

其中,Store based model 中的 Allocation sites 较为常用,其抽象依据是同一创建点的对象为同一对象:

image-20200820211117510

上下文敏感

指针分析过程中如何对调用上下文建模,主要分为两种

  • 上下文敏感
    • 每一个上下文分析一次
    • 每次调用时,不同上下文方法对象不一样,重复分析函数
  • 上下文不敏感
    • 同一个函数只分析一次
    • 分析时合并所有调用的输入
    • 一般地精度较低

下图左侧为上下文敏感,右侧为上下文不敏感:

image-20200820211514827

个人认为对于特定的分析(如污点分析)做好函数摘要(summary)后,就可以做上下文不敏感的分析,同时不损失精度。

流敏感

做指针分析时,对控制流的处理

  • 控制流敏感[4]
    • 考虑执行顺序
    • 维护每一程序点的指针指向关系
  • 控制流不敏感
    • 保存所有可能指向的对象

image-20200820212053813

如上图代码中,控制流敏感(蓝色)对每个程序点都做了记录,而控制流不敏感(橘色)则保存指针的所有可能指向;

先前的数据流分析都是流敏感的,而在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类似(本课不做讨论)
    image-20200820212836084

    如上图所示,原先数组下表的访问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$:

下图给出四种情况的形象表示:
image-20200821212128271

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$

因此,先前的四条语句产生的边可以用下图表示:
image-20200823104858792

Pointer Analysis: Algorithms

Worklist

$WL \subseteq \left \langle Pointer, \mathcal{P}(O)\right \rangle^*$, 即WL中的元素为$n, pts$,表示指针$n$可能指向的内存/对象集合为 $pts$

加边函数 AddEdge():

1
2
3
4
5
def AddEdge(s, t):
if s → t ∉ PFG:
add s → t to PFG # 将s → t加入PFG
if pt(s) is not empty:
add <t, pt(s)> to WL # 将<t,s指向内容>加入工作队列

即若添加 $s \rightarrow t$ ,首先检查该边是否在PFG中,若不存在,则将该边加入PFG;并且检查 s 指向的内存集合,如果集合不空,则需保证 $s$ 指向的内容被 $t$ 指向,即加入工作队列中。

指针传播函数 Propagate():

1
2
3
4
5
6
7
8
9
def Propagate(n, pts):
"""
n: 指针n
pts: n可能指向的新的指针集合
"""
if pts is not empty:
pt(n) ⋃= pts # 将pts内容存入到指针指向的集合中
for each n → s ∈ PFG
add s, pts to WL

即 pts 不为空时,将 $pts$ 内容存入 $n$ 的指针集合中,接着找n的后继s,对每一个s,将 <s, pts> 加入WL。

主函数 Solve()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def Solve(s):
"""
S: 程序所有语句
WL:工作队列
PFG: Pointer flow graph
"""
WL = [] # e.g., [<n, pts>] 表示指针n可能会指向pts集合(每次迭代就会有新的可能)
PFG = {} # e.g., {<x, {𝑜𝑖}>} 表示指针x指向对象𝑜𝑖
for each i: x = new T() ∈ 𝑆: # 处理 new stmt
add <x, {𝑜𝑖}> to WL
for each x = y ∈ S: # 处理 assign stmt
AddEdge(y, x)
while WL is not empty:
remove n, pts from WL
Δ = pts - pt(n)
Propagate(n, Δ)
if n represents a variable x:
for each 𝑜𝑖 ∈ Δ:
for each x.f = y ∈ S: # 处理 store stmt
AddEdge(y, 𝑜𝑖.𝑓)
for each y = x.f ∈ S: # 处理 load stmt
AddEdge(𝑜𝑖.𝑓, y)

首先可以看到,在9、11、19和21行分别处理了new、assign、store和load操作:

  • 对于new操作,直接将 $\left \langle x, o_i \right\rangle$ 加入worklist
  • 对于assign操作,将x指向的内容也被y指向,即调用AddEdge()

接下来进入循环,直到工作队列为空:

  1. 取出队头要处理的指针n和其对应的pts
  2. 求差异 Δ,pts中的有一些地址先前已经传播过,只需处理剩余部分
  3. 调用Propogate(),将 Δ 内容放入 $pt(n)$ 并且添加新的work

接着需要处理对象操作,17-18的行意指若指针n表示的是一个变量(而不是field),那么对于每一个 Δ 中的对象实例,处理所有与 $x.f$ 相关的 store 和 load 操作,对 store 和 load 操作都是使用AddEdge()处理(19-22行)。

具体示例

考虑如下代码:

1
2
3
4
5
6
7
b = new C();
a = b;
c = new C();
c.f = a;
d = c;
c.f = d;
e = d.f;

首先经过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,有如下推导规则:

image-20200823202143283

主要有4部分:

  1. 由 $Dispatch(o_i, k)$ 获取目标方法,$Dispatch()$ 实现与之前 CHA 分析相同:
  2. 被$x$ 指向的对象$o_i$ ,也被 $m_{this}$ 指向;
  3. 对于每一个实参$a_j$所指向的信息,也被形参 $m_{pj}$ 所指向——在PFG上增加 “实参→形参”边;
  4. 对于被返回值 $m_{ret}$ 指向的对象$o_v$,也被等号左边变量 $r$ 指向——在PFG上增加“ret→r”的边。

讨论为什么对于 $m_{this}$ 不增加边,而对其他参数就增加边:

注意到 $x$ 指向的信息是一个集合,而 $m_{this}$ 由$Dispatch()$ 解析后可以唯一确定一个对象,换句话说:

  1. 对于this来说,指针分析已经可以唯一确定该对象实例,若传递 $x$ 的指向对象集合反而造成分析不准确,如下图所示:
    image-20200823204227690

  2. 对于其他参数,指针分析无法确定它们的唯一对象实例,为保证may分析,需要传递先前所有可能性,即可能指向的集合。

归根结底,this和不同参数还是有区别的,this的实例参与了 Dispatch 过程。

Interprocedural pointer analysis

  1. 和其他过程间分析一样,过程间指针分析需要指定一个函数入口
  2. 过程间指针分析一边做指针分析,一边构造调用图
  3. 由入口出发不断探索未知函数,直到所有可被探索的函数都被处理完成,这样既可以提高效率,又可以提高精度

Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def Solve(s):
"""
S: 程序所有语句
WL: 工作队列
PFG: Pointer flow graph
S: 可达所有语句集合 s_m表示函数m的所有语句集合
RM: 可达所有函数集合
CG: 调用图,保存边
"""
WL = [] # e.g., [<n, pts>] 表示指针n可能会指向pts集合(每次迭代就会有新的可能)
PFG = {} # e.g., {<x, {𝑜𝑖}>} 表示指针x指向对象𝑜𝑖
S = {} # added
RM = {} # added
CG = {} # added
AddReachable(m) # difference
while WL is not empty:
remove n, pts from WL
Δ = pts - pt(n)
Propagate(n, Δ)
if n represents a variable x:
for each 𝑜𝑖 ∈ Δ:
for each x.f = y ∈ S: # 处理 store stmt
AddEdge(y, 𝑜𝑖.𝑓)
for each y = x.f ∈ S: # 处理 load stmt
AddEdge(𝑜𝑖.𝑓, y)
ProcessCall(x, 𝑜𝑖) # added

与单函数的指针分析不同,主要变化在12、13、14、15和26行,在函数初始化阶段,增加可达语句集合、可达函数集合和调用图,以及对 new 和 assign 的处理放在了 AddReachable() 函数中,在变化的每个对象实例中,通过 ProcessCall()处理call stmt——当n为一个变量时调用。

AddReachable(m)

AddReachable(m)函数用于将新的方法 $m$ 加入可达集合中,同时处理 $m$ 中 new 和 assign 语句,处理方法与单函数类似:

1
2
3
4
5
6
7
8
9
10
def AddReachable(m):
if m ∉ RM:
# 添加新的已知方法和语句
add m to RM
S ∪= S_m
# 更新 worklist 和 PFG
for each i: x = new T() ∈ S_m:
add <x, {𝑜𝑖}> to WL
for each x = y ∈ S_m:
AddEdge(y, x)

ProcessCall(x, 𝑜𝑖)

$ProcessCall(x,o_i)$ 用于处理 call 语句,算法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def ProcessCall(x, 𝑜𝑖): 
for l: r = x.k(a1,…,an) ∈ S:
# 获取方法m
𝑚 = Dispatch(𝑜𝑖, k)
# pass receiver object to "this"
add <m_this,{𝑜𝑖}> to WL
if l → m ∉ CG:
# 构建call graph
add l → m to CG
# 标记新方法为已知方法
AddReachable(m)
# 传递每个参数,建边
for parameter 𝑝𝑖 of m:
AddEdge(𝑎𝑖, 𝑝𝑖)
# 传递返回值
AddEdge(𝑚_𝑟𝑒𝑡, r)

Example

设有如下待分析代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class A {
static void main() {
A a = new A();
A b = new B();
A c = b.foo(a);
}
A foo(A x) { … }
}
class B extends A {
A foo(A y) {
A r = new A();
return r;
}
}

首先程序初始化,有如下结果:

  • 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}>:

  1. 先做propagate(b,{o4});
  2. 由于第5行存在调用,执行ProcessCall(b, o4),在函数中,首先解析到调用函数为m=B.foo(A),将 <B.foo/this. {o4}> 加入 worklist;
  3. 接着由于之前没有分析过该函数调用:
    1. 5→B.foo(A) 加入CG
  4. 调用 AddReachable()
    1. B.foo(A)加入到已知函数
    2. 注意到11行存在new操作,将{<r, o11>}加入worklist
    3. 调用 AddEdge(ai, pi),更新PFG
    4. 调用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}")

相关文献

  1. William E. Weihl, “Interprocedural Data Flow Analysis in the Presence of Pointers, Procedure Variables, and Label Variables”. POPL 1980.
  2. Vini Kanvar, Uday P. Khedker, “Heap Abstractions for Static Analysis”. ACM CSUR 2016.
  3. Lars Ole Andersen, 1994. “Program Analysis and Specialization for the C Programming Language”. Ph.D. Thesis. University of Copenhagen.
  4. Hardekopf B, Lin C. Flow-sensitive pointer analysis for millions of lines of code. CGO 2011:289-298.
  5. Lecture Notes on Pointer Analysis, https://www.cs.cmu.edu/~aldrich/courses/15-819O-13sp/resources/pointer.pdf