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$指针集中(发生在同一上下文中);
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$。
下图给出四种情况的形象表示:
Call语句,l: r = x.k(a1,...,an)
:
先对于$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()
函数的实现,即当前上下文 $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 可以表示为
注意到第一个$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]的上下文由调用者对象和先前上下文组成:
举例来说:
对于第5行代码调用后,1-object的上下文解析为$[o_1]$,可见对于第 7 行的指针分析而言,1-object效果优于1-call-site;
从调用图也可看出分别:
Object Sensitivity理论上并不优于Call Site,如先前例子Object弱于Call Site:
Type Sensitivity
类型敏感[3]的上下文由调用点类和先前上下文组成:
注意这里笔记改了一下老师的公式,这里 $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():
1 | def Propagate(n, pts): |
AddEdge():
1 | def AddEdge(s, t): |
Dispatch():
Related work
在北大课程中还介绍了两种指针分析方法
- 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.