指针分析Pointer Analysis

指针分析作为静态分析中最关键的技术，很多后续的软件分析都依赖于其结果，因此熟悉其流程和操作步骤十分重要。

过程间分析（interprocedural analysis）

在没有引入过程间分析时，所有参数传递和返回值信息都无法传播，从而导致不精确的结果。过程间分析用call edge和return edge将不同的过程内控制流图关联起来，从而提高准确性，并进一步生成整个程序的控制流图（call graph）。

Call Graph Construction (CHA)

调用图（call graph），它用于表示一个程序中的调用关系，是一个从调用点(call-sites)到目标方法（callee）的有向边构成的集合。

在本次学习中，我们后续都是对OOPL（面向对象，Java）语言的程序进行分析。

常见的调用图构建方法有以下四种：

• Class hierarchy analysis (CHA)
• Rapid type analysis (RTA)
• Variable type analysis (VTA)
• Pointer analysis (k-CFA)

在上述列表中，从上往下，精确度逐渐提升；从下往上，效率逐渐提升。我们学习第一个class hierarchy analysis和最后一个pointer analysis。

Static call（静态调用）：用于静态方法，编译时确定。

Special call（特殊调用）：用于私有方法、父类方法或构造函数，编译时确定。

Virtual call（虚拟调用）：用于实例方法（多态），这种调用依赖于对象的实际类型，具有多态性，运行时确定。

在java中主要有上述三种方法调用，static call和special call的目标方法只有一个，但virtual call的目标方法可能有多个，可以参考多态性。因此关键在于找到virtual call中的特定方法（method dispatch）问题。

在运行时，virtual call（如o.foo(...)）基于以下两点进行解析：receiver object的类型（如o的类型）和call site处的方法签名（method signature，如foo(...)）。对于如下方法foo，它的签名为<C: T foo(P, Q, R)>，简写为C.foo(P,P,R)：

class C {
    T foo(P p, Q q, R r) { ... }
}

• Signature = class type + method name + descriptor
• Descriptor = return type + parameter types

在此基础上，我们定义函数Dispatch(c,m)来模拟运行时找到真正的目标方法(method dispatch)的步骤：

Dispatch是后面分析时经常用到的函数，用来找此时真正的方法,这里c‘是c的父类。

CHA算法

这里分成三种情况，如果目标cs是static call则解为方法本身；如果是special call（构造、私有、父类），则先找到其父类cm，再对其父类进行dispatch求解，直到找到真正的父类；如果是virtual call，则对自己本身c以及c的子类（不包含父类）进行dispatch。在实践中发现大部分的情况都是virtualcall。

Call Graph 构建

从entry方法（main方法）出发，对于每个可到达的方法m，为m内部的所有call site通过CHA解析它的目标方法（Resolve(cs)），重复这一过程直到没有任何新方法出现。

WL是work list集合包含即将分析的method，CG是Call graph，请求边的集合；RM是可达方法的集合；Resolve（cs）就是利用CHA求解；最后将cs->目标方法，并加入CG

过程内分析（Interprocedural Control-Flow Graph）

如何构建过程间控制流图（ICFG）？

事实上，一个程序的ICFG包括程序中所有方法的CFG加上两类额外的有向边：

1. Call edges，即从call sites到被调用方法（callee）的entry nodes。传参数
2. Return edges，即从callee的exit nodes到caller的call sites后面紧跟着的语句（return sites）。传返回值

ICFG就是CFG加上call edge和return edge，但是我们发现两处黄线仍然保留，这是call-to-return edges,因为同一方法内部的上下文信息（如本地变量等）需要借助这条边传递。

Interprocedural Data-Flow Analysis

过程间数据流分析并不是一种具体的应用，只是把我们原来针对单一过程的分析应用扩展到整个程序的所有过程上。过程内分析和过程间分析的区别如下：

所谓edge transfer，包含normal edge transfer、call-to-return edge transfer、call edge transfer和return edge transfer。Call-to-return transfer传递的是方法局部值并kill掉LHS变量（left-hand side），call edge transfer传递的是实参值，return edge transfer传递的是返回值。

另外，node transfer在两种分析中也有一些差异。以常量传播为例，过程内分析的情况下，我们遇到类似b = addOne(a)这样的call site时，直接将表达式左侧的变量b（即LHS变量）赋值为NAC；然而在过程间分析时，LHS留待return edge transfer来处理。像左侧a=6的信息直接通过虚线传递，b=ten()时上下b=7与b=10冲突，kill掉左侧b，保留return结果

Pointer Analysis（上下文不敏感C.I）

经过上一节CHA分析，我们发现其也存在一些缺点：比如我只想要知道下图中在new One（）下对应的方法，但CHA分析会得到3个目标函数，存在冗余。所以我们引入了更加精确的分析方法，指针分析PTA。

特别强调，本课程的指针分析主要针对于OO语言的，这里指针特指变量、对象的指向关系

example：a.setB(x)中this是a变量的对象也就是new A，b对应x的对象new B，y=a.getB(),a对应new A，getB()对应this.b，连起来是newA.b,查表也就是new B

别名分析（alias analysis）与指针分析有紧密关联，但是实际上两者是不同的概念。前者想要回答的问题是，两个指针能否指向同一对象？后者想要回答的问题是，一个指针可能指向的对象有哪些？我们也很容易发现，别名信息实际上可以从指针分析的结果中得出。

指针分析有非常多的应用，如基础信息提取（调用图、别名等），编译器优化，Bug检测（空指针等）和安全分析等。

指针分析的关键因素

指针分析是一个复杂系统，许多因素都会影响到分析的准确性和效率。谭添老师将这些因素、涉及的问题和学界已有的研究路线用表格做了归纳，十分清晰明了：

本课程学习其中加粗的因素，也是目前最优解。

Heap Abstraction

“堆抽象”很好理解，就是研究如何对堆内存进行建模。程序运行起来后，从时间上看，堆上对象的数量可能是不定的。例如，某个for循环中可能会包含对象创建操作。

因此，为了确保分析能够终止，在静态分析中，我们会将动态分配的具体对象当作有限抽象对象（finite abstract objects）。例如，将所有在同一语句处创建的对象当作一个来处理，即使该语句可能位于一个for循环中，这样就让其变得有界。

其中，allocation-site是最常用的堆抽象方式。简单来说，就是将具体对象根据它们的分配点（allocation sites）进行抽象。例如，对于下面的代码片段来说，第二行a = new A();是一处allocation-site，我们就将所有在这一行创建的对象抽象为o2。

1 for (i = 0; i < 3; i++) {
2    a = new A();
3 }

Context sensitivity

上下文敏感会把每一遍调用单独分开（克隆），形成多个上下文，分析更准确

上下文不敏感会把同一个方法汇入同一个上下文，分析速度更快？

Flow sensitivity

流敏感会关注程序中语句的执行顺序，在每个程序点处维护一个指针指向关系映射；

流不敏感则会忽略控制流顺序，将程序视作无序的语句集合，为整个程序维护一个指针指向关系映射。

左侧为流敏感，可以发现y最后将x覆盖；右侧为流不敏感，最后x，y都被指向，但结果中存在错误。本课选用流不敏感进行分析。

Analysis scope

whole-program是要求关心所有指针信息，变量->对象；

Demand-driven只需要关心需要提供的受影响的指针信息

我们需要真正分析的程序语句

本课中，我们只需要关心4类指针关系：本地变量（如变量x）、静态域（如c.f，有时也叫全局变量）、实例域（如x.f）和数组元素（如array[i]）

同时我们也只要关心5种指针状态：New，Assign，Store，Load，Call

• 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、special call和virtual call，我们主要关心virtual call。

指针分析的规则

相关域：

• Variables: x,y∈V
• Fields: f,g∈F
• Objects: oi,oj∈O
• Instance fields: oi.f,oj.g∈O×F
• Pointers: Pointer=V∪(O×F)
• Points-to relations: pt:Pointer→P(O)

其中，P(O）表示O的幂集，pt(p)表示p的指向集合。

Rules：

其中规则一栏，上面是前提条件，下面一行是操作目的，如：New就是无条件创建一个x->oi的指针关系；Assign就是y指向的对象，x也要指向该对象。

指针分析实现-PFG

指针分析的目的是将指向信息在指针之间传播。

指针分析实现的关键是，如果pt(x)改变了，应该将这种改变传播到x关联的指针上。图结构很适合这类分析。我们用指针流图（pointer flow graph，简称PFG）来表示程序中对象是如何在不同指针之间“流动”的，pt(x)需要被传播到图中xx的所有后继节点上。

这是与上述规则对应的节点之间的指向关系，右边的变量指向左边。

如图所示，变量按照上述规则进行指向，同时，我们也可以清晰的看出他们之间的传递关系，指针e对于指针b来说是可达的，因此指针b指向的对象也可能被指针e指向。

步骤一：建立PFG图

步骤二：传递PFG中的指向关系

但同时，“构建PFG”与“在PFG节点间传播指向关系信息”是互相依赖的。在指针分析的过程中，PFG是会动态更新的，而不是先构建PFG，再进行所谓的指针分析。

指针分析算法（上下文不敏感）

WL中包含即将被处理的指向关系，是个先进先出的队列，格式为WL⊆⟨Pointer,P(O)⟩，WL的每一项⟨n,pts⟩都是指针n和指向对象集合pts构成的对，这些信息需要被传播到n的现有指向集合pt(n)中。

AddEdge(s,t)算法:如果PFG不存在s->t,则加入该指向关系，同时也要在WL中加入<t,pt(s)>,确保每一个被s指向的对象也被t指向，相当于把当前指针集合传递给下一个指向的对象。

Δ=pts−pt(n)：用来筛除重复项，提高效率

Propagate(n,Δ)，最开始每个变量都有一个空的指向集合，后面会不断更新。将pts指向集合传递给n的指向集合，传递筛选过的指向集合pts给n的后继s，并将<s,pts>加入WL

经过上述算法处理，最后可以得到最终节点e的指向关系，以及各个变量之间的传递关系。

Rule: Call

前面已经举例了4中常见的Rules，下面介绍最复杂的call调用，

先对目标方法m进行Dispatch，找寻真正的目标函数；明确mthis的指向，但不需要再添加PFG边；对于m中的参数p1,p2,在PFG中增加变量参数的指向边，a1->p1;对于返回结果mret，增加与对象的指向边mret->r

过程间指针分析（Interprocedural Pointer Analysis）

在上面定义的规则的基础上，我们来考虑过程间指针分析的算法。首先需要注意的是，指针分析与调用图构建是相辅相成、互相依赖的。我们在上一节中提到过，“构建PFG”与“在PFG节点间传播指向关系信息”是互相依赖的，这里也是一样。

在这个场景中，逐渐丰富的调用图指出了目标程序中从main方法开始的所有可达方法。指针分析只需要分析所有可达方法和对应语句即可。

可以看到，两个算法在大体流程上具有一定相似性，但仍有不同。

S是可到达状态的集合；
Sm是方法m的状态的集合；
RM是可到达方法的集合

ProcessCall中AddEdge（ai,pi）中传递的是方法中的参数，如下面例子中传递B的A foo（A y）中的y给第五行中的a所指的对象o3

首先，过程间指针分析是在可达前提下进行的分析，因此算法最开始传入了入口方法main，并不断通过AddReachable更新可达方法集合。另外，过程间分析会调用ProcessCall函数来处理方法调用语句，该函数实现了我们在最开始定义的方法调用分析规则。过程间指针分析算法最终的输出有两个：指向关系集合与调用图。

先处理entry入口方法，如果有call调用处理call，找到真正处理的方法mthis，添加RM和CG的信息，再处理方法内部，对于参数和返回值添加边，最后对于WL中的信息propagate，添加指向关系和处理后继。

Pointer Analysis(上下文敏感C.S）

前面我们学习处理的都是上下文不敏感的指针分析，虽然速度快，但会出现精度丢失的问题，如下图：

x最终指向应该只有一个o1，但因为不敏感最终o2也会传播下去.上下文不敏感（context insensitivity，简称C.I.）分析的不精确性主要体现在：

• 在动态执行过程中，一个方法可能在不同的调用上下文（calling contexts）中被调用多次。
• 在不同的调用上下文中，方法中的变量可能指向不同的对象。
• 在C.I.指针分析中，不同上下文中的对象通过返回值或方法副作用被混在一起传播到程序各处，导致了虚假数据流。

Call-site

最经典的上下文敏感处理策略是“call-site sensitivity”，它将每个方法的上下文表示为由call sites组成的链（可能包括方法的call site，caller的call site，甚至caller的caller的call site等），对程序动态运行时的调用栈进行抽象。

在call-site中不同方法调用的上下文会被克隆区分，同样是id方法，可以被区分为id[1]和id[2]，从而使分析更加准确。

Context-Sensitive Heap

面向对象的程序是heap-intensive的。因此，为了提高准确性，我们也要对堆抽象（heap abstraction）做上下文敏感处理——抽象对象将带有heap context。在基于allocation-site的堆抽象基础上，上下文敏感的堆抽象将提供粒度更细的堆模型：

为什么C.S.的堆抽象能够提高准确性呢？这是因为（可以与前文描述的C.I.的不精确性结合起来理解）：

• 在动态执行过程中，一个allocation site可能在不同的调用上下文中创建多个对象。
• 在同一个site创建的不同对象可能是由不同的数据流控制的——例如，将不同的值（值可能来自不同的方法调用）存储到对象的域中。

因此，在指针分析中，在没有heap context时，合并不同上下文的数据流到一个抽象对象可能导致准确度降低；将位于同一allocation size但不同上下文的对象区分开来才能提高准确度。

这是上下文不敏感和敏感堆的处理图，可以看出左图我们最终要得到的是n=x1.f，x1.f可以由O8.f得到，但由于不区分上下文，x2.f也指向O8.f，最终得到对象不精确；右图中，我们对于对象object也加入上下文信息，这样就可以精确的得到想要的上下文信息。

上下文敏感的指针分析规则

与前面不敏感的规则相比，上下文敏感的前四条规则要在变量x和对象o前加上上下文信息c：，Call规则要增加一条select语句，用于为目标方法m根据call site l处的信息选取对应的上下文，ct是callee的上下文。

上下文敏感指针分析算法

与不敏感相比，此算法只在变量和对象前加入了上下文信息c:，以及call中的select选取上下文信息的语句。

并且其中的AddEdge和Propagate方法没变，这两个函数不涉及上下文信息。

Select上下文的选择方式

c是caller context，l是call site，c’:oi是带有堆上下文的消息接收对象（一种看待OOP的视角：调用某个对象的方法，其实就是给该对象发消息）。

常见的C.S.处理方法有三种：call-site sensitivity、object sensitivity和type sensitivity。

Call-Site Sensitivity

Call-site sensitivity由Olin Shivers于1991年在他的博士论文Control-Flow Analysis of Higher-Order Languages中提出。其思想是，每个上下文都是一个call sites列表（调用链），在方法调用时，将call site加入到caller context中，作为callee context，实质上就是调用栈的抽象：

Select(c,l, )=[l’, … ,l’’,l] where c=[l’, … ,l’’]

k-CFA全称是k-Limiting Context Abstraction。顾名思义，就是要限制上下文的长度。Call-site sensitivity的特性导致这样产生的上下文可能会非常长，比如递归的情况。一方面，我们要确保指针分析能够终止；另一方面，我们不希望上下文过长，也没必要过长。

因此，我们为上下文长度设置一个上界k——每个上下文只包括前k个call sites，更早的就丢掉。实践中，k通常小于3。另外，方法上下文和堆上下文可能采用不同的k。在实践中，方法的k一般设为2，堆的k一般设为1.

完整例子可以从pdf的120页开始往下看，常看常新。

经过对比发现，C.S比C.I分析的更准确。

Object Sensitivity

对象敏感性。这种处理方式在2002年的一篇论文Parameterized Object Sensitivity for Points-to Analysis for Java被提出，思路与前一种截然不同——用抽象对象（由对象allocation sites表示）列表来构成上下文，而非call sites构成。在方法调用时，将接收者对象和它的heap context作为callee context。相应的SelectSelect函数如下：

Select( ‾, ‾,c’:oi)=[oj, … ,ok,oi] where c’=[oj, … ,ok]

由于抽象对象由allocation sites表示，因此这种处理方式也叫做allocation-site sensitivity。

经过与call-site的对比发现，object的结果更为准确。

Object sensitivity其实模拟的就是Java语言运行时的动态处理过程。具体到这个例子而言，不同的上下文都可能流经call-site [12]，然而1-CFA导致历史上下文被丢掉了，准确度自然下降。增加k-CFA的k可以缓解问题，但是并不能完全解决——只要类似的调用层数比k大，这样的问题都会出现。

理论上，call-site sensitivity和object sensitivity的准确性是不可比较的。

实践中，在处理OOP时，object sensitivity一般比call-site sensitivity的效果更好

可以看到，在处理各类问题是，obj的效率和准确度都更高。

Type Sensitivity

类型敏感性。从名字上我们就大概能猜出来它的思路，甚至能够猜到它的准确性可能会比object sensitivity低一些，但是效率会高一些。所谓类型敏感性，就是使用包含allocation site的“类型”和堆上下文作为callee object。

这种处理方式在2011年的一篇论文Pick YourContexts Well: Understanding Object-Sensitivity被提出。

需要注意的是，是包含allocation site的类型，不是接收对象的类型。例如，在下面这段代码中，InType(o3)=X，不是Y：

1 class X {
2     void m() {
3         Y y = new Y();
4     }
5 }

严谨地说，在相同k-limiting条件下，type sensitivity的准确性不高于object sensitivity。