Introduction

Problem of Context-Insensitive (C.I.)

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

具体如下图所示：

当分析到int i = x.get() 时，上下文不敏感指针分析会认为 $x$ 指向 $o_1,o_2$，因此做常量分析时，$i$ 的分析结果就是 NAC，这当然是不准确的——其关键点在于n没有上下文，因此不同函数调用时，n会记录下所有调用结果的集合。

Context Sensitivity(C.S.)

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

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

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

例如如上代码，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.

注意，对每个函数的克隆本质是对函数内变量的克隆，如下图所示：

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

补充1：另一种实现方法是使用内联，即把被调函数的代码嵌入到调用函数中，对参数进行改名替换，实际效果与这里的克隆等效。

补充2：克隆思想不只是可以做过程间分析，还可以做过程内分析，比如对于循环，可以展开一定层数k做分析。

Context-Sensitive Heap

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

如下图，对n做上下文敏感分析：

在变量上下文敏感，堆不敏感时（左侧），在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$指针集中（发生在同一上下文中）；
$\frac{}{c:o_i \in pt(c:x)}$
Assign, x = y
$\frac{c':o_{i} \in pt(c:y)}{c':o_{i} \in pt(c:x)}$
出现赋值后，让 $c:y$ 指向的内容 $c’:o_i$ 指向 $c:x$，注意$x$和$y$在同一上下文，而$o_i$在另一个上下文；
Store, x.f = y
$\frac{c':o_i \in pt(c:x), c'':o_j \in pt(c:y)}{c'':o_j \in pt(c':o_i.f)}$
赋值给域时，取上下文$y$的指向对象$c’’:o_j$，取上下文 $x$ 的指向对象$c’:o_i$，将$c’’:o_j$加入到$c’:o_i.f$的指向集合中；
Load, y = x.f
$\frac{c':o_{i} \in pt(c:x), c'':o_{j} \in pt\left(c':o_{i} . f\right)}{c'':o_{j} \in pt(c:y)}$
属性赋值给变量时，指向对于上下文 $x$ 指向的对象 $c’:o_i$ ，取出其域 $c’:o_i.f$ 指向的对象 $c’’:o_j$，将其加入到$c:y$。

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

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

$\frac{ c^{\prime}: o_{i} \in p t(c: x) \\ m=\text { Dispatch }\left(o_{i}, k\right), c^{t}=\operatorname{Select}\left(c, l, c^{\prime}: o_{i}\right) \\ c^{\prime \prime}: o_{u} \in p t(c: a j), 1 \leq j \leq n \\ c^{\prime \prime \prime}: o_{v} \in p t\left(c^{t}: m_{r e t}\right) }{c^{\prime}: o_{i} \in p t\left(c^{t}: m_{t h i s}\right) \\ c^{\prime \prime}: o_{u} \in p t\left(c^{t}: m_{p j}\right), 1 \leq j \leq n \\ c^{\prime \prime \prime}: o_{v} \in p t(c: r) }$

先对于$o_i,k$，解析其方法；
给定调用点上下文 $c$、调用点 $l$、x指向对象的上下文$c’:o_i$，通过$select()$，选择callee的上下文$c^t$（如下图所示，select选择出[2]和[3]上下文
传this，注意传到$c^t$上下文中——$c^{\prime}: o_{i} \in p t\left(c^{t}: m_{t h i s}\right)$；
传形参，传给$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}$；
传返回值，将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的加边策略：

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的加边策略：

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

Algorithm with C.S.

算法如上图所示，黄色底为存在变化的区域，其中添加了对上下文的处理，而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(\boldsymbol{c},\boldsymbol{l},\_)=[l',\dots,l'',l]\\ \text{where }c=[l',\dots,l'']$

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

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

那么特别的，

0-call-site/CFA上下文不敏感；
1-call-site/CFA 可以表示为 $Select(c,l,_)=[l]$，注意到 $c$ 被丢弃
2-call-site/CFA 可以表示为
$Select(c,l,_)=[l'',l]\\ where c=[l',l'']$
注意到第一个$l’$被丢弃。

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

Example

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

初始化阶段，处理main()函数：

将 $[]: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语句，将n1，n2加入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 → {}")

后续分析较为简单，不再记录，最终结果为：

Object Sensitivity

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

$\begin{array}{c} \operatorname{Select}\left(\_,\_, \boldsymbol{c}^{\prime}: \boldsymbol{o}_{\boldsymbol{i}}\right)=\left[o_{j}, \ldots, o_{k}, o_{i}\right] \\ \text { where } c^{\prime}=\left[o_{j}, \ldots, o_{k}\right] \end{array}$

举例来说：

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

从调用图也可看出分别：

Object Sensitivity理论上并不优于Call Site，如先前例子Object弱于Call Site：

Type Sensitivity

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

$\operatorname{Select}\left(\_, \_, \_, m\right)=\left[t^{\prime}, \ldots, t^{\prime \prime}, \operatorname{InType}\left(m\right)\right] \\ \text{where }c^{\prime}=\left[t^{\prime}, \ldots, t^{\prime \prime}\right]$

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

举例来说：

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

Experiment

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

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

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

Propagate(), AddEdge() and Dispatch()

Propagate():

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():

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()：

$Dispatch(c, m)=\left\{ \begin{array}{ll} m' ,& \text{if } c \text{ contains non-abstract method }m' \\ & \text{that has the same name and descriptor as }m\\ Dispatch(c', m), & \text{otherwise} \end{array}\right.\\ \text{where }c'\text{ is superclass of }c$

在北大课程中还介绍了两种指针分析方法

Anderson指向分析[5]，复杂度$O(n^3)$（n为变量个数），也叫 Inclusion-based，本课程介绍CFA与之类似；
Steensgaard指向分析，复杂度为$O(n\alpha(n))$（n为语句数，接近线性时间），也叫Unification-based。

还有一种流敏感的指针分析算法[6]，其利用部分SSA做指针分析的优化，提高分析速度。

References

Olin Shivers, 1991. “Control-Flow Analysis of Higher-Order Languages”. Ph.D. Dissertation. Carnegie Mellon University.
Ana Milanova, Atanas Rountev, and Barbara G. Ryder. “Parameterized Object Sensitivity for Points-to and Side-Effect Analyses for Java”. ISSTA 2002.
Yannis Smaragdakis, Martin Bravenboer, and Ondrej Lhoták. “Pick Your Contexts Well: Understanding Object-Sensitivity”. POPL 2011.
Yue Li, Tian Tan, Anders Møller, and Yannis Smaragdakis. “A Principled Approach to Selective Context Sensitivity for Pointer Analysis”. TOPLAS 2020.
The Ant and the Grasshopper: Fast and Accurate Pointer Analysis for Millions of Lines of Code, Hardekopf and Lin, PLDI 2007
Hardekopf B, Lin C. Flow-sensitive pointer analysis for millions of lines of code. CGO 2011:289-298.