0%

静态程序分析课程笔记(指针分析-上下文敏感)

Introduction

Problem of Context-Insensitive (C.I.)

  • 每次函数调用时,调用的上下文不一样;
  • 在不同的调用上下文里,函数内的变量会指向不同;
  • 在上下文不敏感的指针分析中,函数内的对象指向的内容是不同上下文混合起来的(如上例中 $n$ 指向 $o_1$ 和 $o_2$),而这些内容会后向传播,造成更多不准确的结果。

具体如下图所示:
image-20200829210207900

当分析到int i = x.get() 时,上下文不敏感指针分析会认为 $x$ 指向 $o_1,o_2$,因此做常量分析时,$i$ 的分析结果就是 NAC,这当然是不准确的。

Context Sensitivity(C.S.)

Context sensitivity models calling contexts by distinguishing different data flows of different contexts to improve precision.

上下文敏感模型会在调用时会区分不同上下文,以提升准确率。

上下文敏感分析需要对上下文抽象建模,目前最经典的策略是 call-site sensitivity,即上下文为调用点函数(调用点+被调函数)序列。

image-20200829221253965

例如如上代码,id()函数存在两个上下文 [1][2]

Cloning-Based Context Sensitivity

为实现上下文敏感分析,最简单的方法是 cloning-based,即对于每一个函数,每到新的上下文就克隆一份新函数和其变量:

In cloning-based context-sensitive pointer analysis, each method is qualified by one or more contexts.

注意,对每个函数的克隆本质是对函数内变量的克隆,如下图所示:
image-20200830103742490

对于id()函数内变量 n 来说,在第一行和第二行调用时,分别克隆出[1]:n[2]:n个变量

Context-Sensitive Heap

对于OO语言,不仅变量有上下文,对象实例也需要有上下文,即需要做堆抽象(对象存储在堆区)。

如下图,对n做上下文敏感分析:
image-20200830104632305
在变量上下文敏感,堆不敏感时(左侧),在newX(Number)中x没有上下文,恒指向$o_8$,那么在第三行第四行调用时, $o_8.f$ 存在 $o_1, o_2$两种可能,因此n也有两种可能,分析结果不准确。

而堆敏感时(右侧),newX(Number)中存在上下文,即对于第三行第四行调用,产生不同上下文的x——$3:o_8$ 和$4:o_8$,它们分别指向$o_1$和$o_2$,因此n的分析时准确的。

注意,一般变量和堆敏感通常是同时使用的,缺一不可。

Context Sensitive Pointer Analysis: Rules

Domain

  • 上下文(Context):$ c, c’,c’’ \in C $
    C指所有上下文集合,根据不同的上下文抽象策略,c的表示内容不同,对于call-site sensitivity,而言,c为call-site的序列(callsite这里可用行号表示);

  • 上下文敏感方法(Context-sensitive methods):$ c:m \in C \times M $
    上下文方法表示为 $c:m$,属于 $C$ 和 $M$的笛卡尔积;

  • 上下文敏感变量(Context-sensitive variables):$ c:x, c’:y \in C \times V $
    与上下文方法类似,$c:x$ 表示在上下文 $c$ 下变量 $x$ 的指向;

  • 上下文敏感对象(Context-sensitive methods):$ c:o_i, c’:o_j \in C \times O $

  • 域(Fields),$ f,g \in F $
    因为域依附于对象,而对象实例存在上下文,因此域实际也存在了上下文;

  • 对象实例域(Instance fields):$ c: o_{i} \cdot f, c^{\prime}: o_{j} \cdot g \in \mathrm{C} \times \mathrm{O} \times \mathrm{F} $

  • 上下文敏感指针(Context-sensitive pointers):$ CSPointer=(C\times V) \cup (C \times O \times F) $
    上下文敏感指针属于上下文变量和实例域的并集;

  • 指向关系(Points-to relations):$pt: CSPointer \rightarrow\mathcal{P}(C\times O)$

Rules

  • New,i: x = new T()

    新建对象时, 上下文 $c$ 下 $o_i$ 加入$c:x$指针集中(发生在同一上下文中);

  • Assign, x = y

    出现赋值后,让 $c:y$ 指向的内容 $c’:o_i$ 指向 $c:x$,注意$x$和$y$在同一上下文,而$o_i$在另一个上下文;

  • Store, x.f = y

    赋值给域时,取上下文$y$的指向对象$c’’:o_j$,取上下文 $x$ 的指向对象$c’:o_i$,将$c’’:o_j$加入到$c’:o_i.f$的指向集合中;

  • Load, y = x.f

    属性赋值给变量时,指向对于上下文 $x$ 指向的对象 $c’:o_i$ ,取出其域 $c’:o_i.f$ 指向的对象 $c’’:o_j$,将其加入到$c:y$。

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

image-20200830114749403

Call语句,l: r = x.k(a1,...,an)

  1. 先对于$o_i,k$,解析其方法;

  2. 给定调用点上下文 $c$、调用点 $l$、x指向对象的上下文$c’:o_i$,通过$select()$,选择callee的上下文$c^t$(如下图所示,select选择出[2]和[3]上下文

    image-20200830120358405

  3. 传this,注意传到$c^t$上下文中——$c^{\prime}: o_{i} \in p t\left(c^{t}: m_{t h i s}\right)$;

  4. 传形参,传给$c^t$上下文的形参——$\frac{c^{\prime \prime}: o_{u} \in p t(c: a j), 1 \leq j \leq n }{c^{\prime \prime}: o_{u} \in p t\left(c^{t}: m_{p j}\right), 1 \leq j \leq n}$;
  5. 传返回值,将callee上下文的返回值传回caller上下文的变量$r$中——$\frac{c^{\prime \prime \prime}: o_{v} \in p t\left(c^{t}: m_{r e t}\right)}{c^{\prime \prime \prime}: o_{v} \in p t(c: r)}$

可见:上下文敏感实际记录了函数调用栈(上下文),而上下文不敏感在进入callee后就无法知道caller的信息。

Context Sensitive Pointer Analysis:Algorithms

Pointer Flow Graph with C.S.

上下文敏感的指针流图有如下定义:

  • 节点:$CSPointer = (C \times V) \cup (C \times O \times F)$

    节点由上下文敏感的变量或是域组成

  • 边:$CSPointer \times CSPointer$

    边 $x \rightarrow y$ 指指针 $x$ 的指向信息同时被 $y$ 指向

对于 New、Assign、Store和Load的加边策略:

image-20200830200755158

new新建一个节点,不需要加边;assign添加 $c:x\leftarrow c:y$ 这一条边(上下文相同);Store添加 $c’:o_i.f \leftarrow c:y$ 边,注意 $y$ 虽然和 $x$ 上下文相同,但是真正加边跨越了上下文($y$ 和 $o_i.f$ 的上下文不同);Load添加$c:y \leftarrow c’:o_i.f$ 边,与Store为反操作。

对于Call的加边策略:

image-20200830201313643

添加实参新参的边,以及返回值的边(注意边跨越了caller和callee的上下文, $c$ 和 $c^t$),this 保证准确度仍使用指针值传递的方式,不加边。

Algorithm with C.S.

image-20200830202712606

算法如上图所示,黄色底为存在变化的区域,其中添加了对上下文的处理,而Propagate()AddEdge()Dispathch() 函数内容与先前相同。

算法输入仍为一个入口函数$m^{entry}$,输出为PFG和指向内容;

首先初始化,$S$ 表示可达语句集合,$S_m$表示函数m中的语句集合,$RM$表示上下文敏感的可达函数集合,CG表示上下文敏感的调用图,都初始化为空后,调用AddReachable(),注意初始情况上下文为空[]

AddReachable()处理new和assign语句,所有操作都在上下文 $c$ 中操作;

接着处理worklist,在处理store和load语句时,按先前图示添加边即可;

重点在于ProcessCall(),根据先前分析,首先用Dispatch()解析出调用的方法,接着通过Select()获取调用进callee的上下文 $c^t$,接下来的加入工作列表、加入可达函数集合的操作都在 $c^t$ 上下文中进行,最后按先前图示加入参数和返回值的边。

Context Sensitivity Variants(Implementation of Select()

对于上下文有不同的抽象表示,其中主要有 Call-site sensitivity,Object sensitivity 和 Type sensitivity。

Call-Site Sensitivity(k-CFA)

调用点敏感 [1]上下文由调用点行号和先前上下文组抽,即上下文本质上是调用栈的抽象:

上式表示了调用点敏感的select()函数的实现,即当前上下文 $c$ 的 $l$ 行发生了调用,那么调用进的上下文为$[c,l]$

但碰到递归调用时,上下文会无限的增加,此时需要视上下文为队列,并限制队列长度$k$(因此此方法也叫 k-CFA),实际应用时,$k \leq 3$,且函数上下文长度和堆上下文长度可以不一致,目前效果最好的是函数上下文长度为 $k=2$ 而堆上下文长度为 $k=1$。

那么特别的,

  • 1-call-site/CFA 可以表示为 $Select(c,l,_)=[l]$,注意到 $c$ 被丢弃

  • 2-call-site/CFA 可以表示为

    注意到第一个$l’$被丢弃。

可以看出,$k$ 的值越长效果越准确,但是效率越低。

举例

如下图所示,蓝底代码为待分析代码,注意代码中没有store和load语句因此不需要看这两个语句的处理,并且不考虑heap sensitive:

初始化阶段,处理main()函数:
image-20200902201538441

将 $[]:C.main()$ 加入 RM 集合,因为函数存在new语句,将$\langle []:c, \{o_3\}\rangle$ 加入WL;

循环处理WL,处理$\langle []:c, \{o_3\}\rangle$

  • 执行$Propagate()$,更新PFG
  • 注意到语句中存在c.m()执行$ProcessCall([]:c,o_3)$
    • $select()$给出$c^t=[4]$
    • 传this,将$\langle [4]:m_{this}, \{o_3\}\rangle$ 加入 $WL$
    • CG中接入调用边 $[]:4\rightarrow[4]:C.m()$
    • 执行$AddReachable([4]:C.m())$
      • $[4]:C.m()$加入$RM$
      • 因为m()函数中存在new语句,将n1n2加入WL

处理结果如下:

  • WL:$\left[\langle c^t:m_{this}, \{o_3\}\rangle, \left\langle[4]: n 1,\left\{o_{12}\right\}\right\rangle,\left\langle[4]: n 2,\left\{o_{13}\right\}\right\rangle\right]$

  • CG:$\{[]:4\rightarrow[4]:C.m()\}$

  • RM:$\{ []:C.main(), [4]:C.m()\}$

  • PFG:

      graph LR
    _c("[]:c → {o3}")
    4_cm_this("[4]:C.m_this → {}")

处理$\langle[4]:C.m_{this},\{o_3\}\rangle$:

  • 执行$Propagate()$,更新PFG,$[4]:C.m_{this}$

  • 注意到存在x=this.id(n1),执行$ProcessCall([4]:C.m_{this}, o_3)$

    • $select()$给出$c^t=[14]$
  • 添加$\langle [14]:m_{this}, \{o_3\}\rangle$至$WL$

    • CG中接入调用边 $[4]:14\rightarrow[14]:C.id(Number)$
  • 执行$AddReachable([]:C.m())$

    • $[14]:C.id(Number)$加入$RM$
    • 添加参数边至 $PFG$
  • 添加返回值边至 $PFG$

  • 注意到存在y=this.id(n2),执行$ProcessCall([4]:C.m_{this}, o_3)$,处理方式同上

处理结果如下

  • WL:$\left[ \left\langle[4]: n 1,\left\{o_{12}\right\}\right\rangle,\left\langle[4]: n 2,\left\{o_{13}\right\}\right\rangle, \langle [14]:m_{this}, \{o_3\}\rangle \right]$

  • CG:$\{[]:4\rightarrow[4]:C.m(), [4]:14\rightarrow[14]:C.id(Number), [4]:15\rightarrow[15]:C.id(Number)\}$

  • RM:$\{ []:C.main(), [4]:C.m(), [14]:C.id(Number), [15]:C.id(Number)\}$

  • PFG:

      graph LR
    _c("[]:c → {o3}")
    4cm_this("[4]:C.m_this → {o3}")
    4_n1("[4]:n1 → {}") --> 14_n("[14]:n → {}")
    14_n-->4_x("[4]:x → {}")
    4_n2("[4]:n2 → {}") --> 15_n("[15]:n → {}")
    15_n-->4_y("[4]:y → {}")

后续分析较为简单,不再记录,最终结果为:
image-20200902212048049

Object Sensitivity

对象敏感[2]的上下文由调用者对象和先前上下文组成:

举例来说:
image-20200902213056427

对于第5行代码调用后,1-object的上下文解析为$[o_1]$,可见对于第 7 行的指针分析而言,1-object效果优于1-call-site;

从调用图也可看出分别:
image-20200902213307436

Object Sensitivity理论上并不优于Call Site,如先前例子Object弱于Call Site:
image-20200902213557030

Type Sensitivity

类型敏感[3]的上下文由调用点类和先前上下文组成:

注意这里笔记改了一下老师的公式,这里 $Select()$ 的参数 $m$ 指caller,$InType()$ 为获取caller类名的函数。

举例来说:
image-20200903204348536

对于第3、5、7行的调用,1-Type的结果为$[X]$——因为main()方法属于 X 类。不难看出,Type-sensitivity是 Object-sensistivity的再一次抽象,提高速度而降低了精度(效果<=Object-sensitivity)。

Experiment

在李樾、谭添老师的论文[4]中,对比了三者的效率和精度,may-fail-cast 指强制转换出错的次数,精度越高出错次数会越少,call-graph-edge 指产生的调用图边数,精度越高边越少。
image-20200903205546848

可以看出,从准确率角度,对象敏感最准确;从效率角度,类型敏感效率最高,而对于面向对象的 Java 语言,call-site效果最差。

顺带一提的是,论文[4]中介绍了一种新算法,因为程序分析在大多时候不需要上下文敏感,因此只在需要上下文敏感处使用准确的Object分析,就可以既保证精度又有足够的速度。

Propagate(), AddEdge() and Dispatch()

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

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指向内容>加入工作队列

Dispatch():

Related work

  1. Olin Shivers, 1991. “Control-Flow Analysis of Higher-Order Languages”. Ph.D. Dissertation. Carnegie Mellon University.
  2. Ana Milanova, Atanas Rountev, and Barbara G. Ryder. “Parameterized Object Sensitivity for Points-to and Side-Effect Analyses for Java”. ISSTA 2002.
  3. Yannis Smaragdakis, Martin Bravenboer, and Ondrej Lhoták. “Pick Your Contexts Well: Understanding Object-Sensitivity”. POPL 2011.
  4. Yue Li, Tian Tan, Anders Møller, and Yannis Smaragdakis. “A Principled Approach to Selective Context Sensitivity for Pointer Analysis”. TOPLAS 2020.