实验作业 5

作业 5：非上下文敏感指针分析

南京大学《软件分析》课程

作业出品：谭添、李樾

1 作业导览

为 Java 实现非上下文敏感的指针分析。
为指针分析实现一个调用图的实时构建算法。

在本次作业中，你将在 Tai-e 上为 Java 实现一个非上下文敏感的指针分析，并在指针分析的过程中实时构建调用图。如果你的实现正确，该调用图会比用类层次结构分析（CHA）建立的更加精确，具体见后文。

在本次作业中，我们将教你如何处理课上没有涉及的一些 Java 特性，即静态字段、数组和静态方法，这样你的指针分析就可以处理 Java 中所有类型的指针了。

在阅读接下来的内容前，请先按照 Tai-e 框架（教学版）配置指南将作业 5 对应的 Tai-e 项目（位于实验作业仓库的 A5/tai-e/ ）配置好。

2 实现指针分析

2.1 分析范围

你将实现第 9 讲和第 10 讲中介绍的非上下文敏感的指针分析算法。该算法处理两种指针（局部变量和实例字段）以及实例方法调用。为了使该指针分析更实用，你将在本次作业中额外处理另两种指针（静态字段和数组索引）以及静态方法调用。我们将在第 2.2 节介绍处理这些特性的分析规则。这些规则与你在课上所学到的规则非常相似（甚至更简单）。你需要在理解指针分析算法的基础上弄清楚如何实现它们。

2.2 新分析规则

在这一节中，我们引入新的指针分析规则来处理静态字段、数组索引和静态方法调用。

静态字段. 静态字段的处理很简单：我们只需要在静态字段和变量之间传值。我们用 $T . f$ 表示静态字段 T.f 的指针，然后定义如下规则来处理静态字段的 store 和 load：

类型	语句	规则	PFG 边
Static Store	`T.f = y`	$o_{i} \in p t (y)$ $o_{i} \in p t (T . f)$	$T . f \leftarrow y$
Static Load	`y = T.f`	$o_{i} \in p t (T . f)$ $o_{i} \in p t (y)$	$y \leftarrow T . f$

数组索引. 正如第 8 讲课件第 86 页所解释的，常规指针分析不区分对不同数组索引（位置）的 load 和 store。假设 $o_{i}$ 代表一个数组对象，那么我们用 $o_{i} [*]$ 表示一个指向数组中所有对象的指针（无论保存在数组的什么位置）。基于这样的处理，我们定义了数组 store 和 load 的规则：

类型	语句	规则	PFG 边
Array Store	`x[i] = y`	$o_{u} \in p t (x), o_{v} \in p t (y)$ $o_{v} \in p t (o_{u} [*])$	$o_{u} [*] \leftarrow y$
Array Load	`y = x[i]`	$o_{u} \in p t (x), o_{v} \in p t (o_{u} [*])$ $o_{v} \in p t (y)$	$y \leftarrow o_{u} [*]$

静态方法. 静态方法的处理与实例方法大体相同，除了1）我们不需要在 receiver object 上进行 dispatch 以解析（resolve）出被调用的方法，2）我们不需要传 receiver object。因为静态方法的处理不需要考虑 receiver object，因此它的处理规则也比实例方法更简单：

类型	语句	规则	PFG 边
Static Call	`r = T.m(a1,...,an)`	$o_{u} \in p t (a_{j}), 1 \leq j \leq n$ $o_{v} \in p t (m_{r e t})$ $o_{u} \in p t (m_{p j}), 1 \leq j \leq n$ $o_{v} \in p t (r)$	$a_{1} \to m_{p 1}$ ... $a_{n} \to m_{p n}$ $r \leftarrow m_{r e t}$

2.3 Tai-e 中你需要了解的类

在本节中，我们首先介绍与 IR 有关的类（pascal.taie.ir.*），然后介绍与指针分析有关的类（pascal.taie.analysis.pta.*）。这些类都是你完成本次作业所需要了解的。

pascal.taie.ir.stmt.DefinitionStmt
你在之前的作业中已经见过这个类。它表示程序中所有的定义语句，例如 x = y 和 x = m(…)。在本次作业中，所有影响指针的语句都是这个类的子类，如下图所示（你将处理红框中的类）：
这些类很简单，你可以通过阅读源代码和注释来熟悉它们。注意，Invoke 既表示实例方法调用，也表示静态方法调用，正如你在作业 4 中看到的那样，你可以使用它的 isStatic() 方法来检查该 Invoke 语句是静态调用还是实例调用。类似地，LoadField 和 StoreField 同时表示实例和静态字段的 load 和 store。这两个类也提供了 isStatic() 方法来检查一个 LoadField/StoreField 语句是 load/store 静态字段还是实例字段。
pascal.taie.ir.exp.Var
你之前已经见过这个类，它表示 Tai-e IR 中的变量。对于所有实例字段 loads/stores、数组 loads/stores 或实例调用的 base 变量，这个类提供了一些方便的 API 来查找相关语句。例如，假设我们正在分析下面的代码片断：
```
x = y;
x.h = a;
x.g = z;
a = x.f;
b = y.f;
c = x.m();
d[i] = c;
e = d[i];
```
如果 var 代表变量 x，那么 var.getStoreFields() 返回第 2 行和第 3 行的两个字段 store 语句，var.getLoadFields() 返回第 4 行的字段 load 语句，var.getInvokes() 返回第 6 行的实例调用；如果 var 代表变量 d，那么 var.getStoreArrays() 返回第 7 行的数组 store 语句，var.getLoadArrays() 返回第 8 行的数组 load 语句。
这些 API 简化了指针分析的实现，所以我们强烈建议你在本次作业中使用它们。你可以阅读 Var 类的源代码和注释以了解更多信息。
pascal.taie.language.classes.JField
这个类表示程序中的各个字段。

下面我们介绍与指针分析相关的类。这些类大多都很简单，你应该阅读它们的源代码和注释来思考如何使用它们。

pascal.taie.analysis.pta.core.heap.Obj
这个类表示指针分析中的抽象对象，即指针集（points-to sets）中的对象。
pascal.taie.analysis.pta.core.heap.HeapModel
这个类表示堆模型（即堆抽象），它用来对堆对象进行建模。给定一个 New 语句（即创建点 allocation site），你可以使用 HeapModel 的 getObj(New) 方法来获得与它对应的抽象对象（即 Obj）。因为我们采用了第 8 讲课件第 44 页中介绍的创建点抽象，所以该方法为每个 New 语句返回一个唯一的抽象对象。
pascal.taie.analysis.pta.ci.PointsToSet
这个类表示指针集，即指针分析中的 Obj 集合。它是可迭代的，也就是说，你可以通过 for 循环来迭代一个指针集中的所有对象：
```
PointsToSet pts = ...;
for (Obj obj : pts) ...
```
pascal.taie.analysis.pta.ci.Pointer
这个类表示分析中的指针，即 PFG（指针流图，pointer flow grpah）中的节点。每个指针都与一个指针集相关联，你可以调用 getPointsToSet() 来获得这个指针集。这个类有四个子类：
它们与第 8 讲课件第 82 页中介绍的 Java 中的四种指针相对应。
pascal.taie.analysis.pta.ci.PointerFlowGraph
这个类表示程序的指针流图。它还维护着从变量、静态字段、实例字段、数组索引到相应指针（即 PFG 节点）的映射，因此你可以利用这个类的 API 获得各种指针。
pascal.taie.analysis.pta.ci.WorkList
这个类表示指针分析算法中的 worklist。它有一个内部 Record 类open in new window Entry 表示 worklist 中的条目。
pascal.taie.analysis.pta.ci.Solver
这个类实现了一个上下文无关的指针分析求解器。它是不完整的，你需要按照第 2.4 节的要求来完成它。

除了上述类之外，你还需要了解 JMethod、IR、InvokeExp、DefaultCallGraph 和 Edge 等类。由于这些类在前面的作业中已经介绍过了，我们在此不做赘述。

2.4 你的任务 [重点!]

你的任务是实现 Solver 类。我们已经在 Solver.initialize() 中初始化了 worklist、指针流图和调用图，并将它们存在 Solver 的字段 worklist、pointerFlowGraph 和 callGraph 中，这样你就可以操作它们了。当你建立调用图时，可以使用前面作业中介绍的 DefaultCallGraph 的 API 来修改调用图。你需要完成指针分析算法的主要部分。具体来说，你要完成以下五个 API：

void addReachable(JMethod)
这个方法实现了第 10 讲课件第 119 页中给出的 AddReachable 函数。
提示：
1. 不要忘记在该方法中处理静态字段 loads/stores 和静态方法调用。
2. 你可以通过如下方法获得 LoadField/StoreField 语句要 load/store 的字段：
```
LoadField stmt = ...;
JField field = stmt.getFieldRef().resolve();
```
3. 为了实时建立调用图，你需要解析方法调用的被调用者。出于方便，我们提供了 Solver.resolveCallee(Obj,Invoke) 来解析 Java 中静态调用、虚调用、接口调用和特殊调用（static, virtual, interface, and special invocations）的被调用者。
4. 在 addReachable() 中，对于不同种类的语句，你需要使用不同的逻辑来处理。实现这种需求的一个合理方式是访问者模式open in new window。Tai-e 的 IR 天然支持访问者模式。具体来说，Tai-e 提供了 pascal.taie.ir.stmt.StmtVisitor 类，这是所有 Stmt 访问者的通用接口，它为所有种类的语句都声明了访问操作。另外，Stmt 的非抽象子类都实现了 accept(StmtVisitor) 方法，因此它们可以回调来自具体访问者的访问操作。
  在 Solver 中，我们为 Stmt 访问者提供了代码框架（即内部类 StmtProcessor），并在 initialize() 中创建了它的实例，并将该实例存在字段 stmtProcessor 中。如果你选择通过访问者模式实现 addReachable() 的逻辑，那么你应该在类 stmtProcessor 中实现相关的 visit(…) 方法，并使用它来处理可达方法中的语句。在这次作业中，visit(…) 方法的返回值被忽略，因此你在实现 visit(…) 方法时只需要返回 null。
  如果你不熟悉访问者模式，用其他方式实现 addReachable() 也是完全可以的。
void addPFGEdge(Pointer,Pointer)
这个方法实现了第 9 讲课件第 43 页中给出的 AddEdge 函数。
void analyze()
这个方法实现了第 10 讲课件第 125 页中给出的 Solve 函数的主要部分，即 while 循环部分。
提示：不要忘记在这个方法中处理数组 loads/stores。
PointsToSet propagate(Pointer,PointsToSet)
这个方法合并了算法中的两个步骤。正如第 9 讲课件第 43 页中的 Propagate 函数所描述的那样，它首先计算差集（ $Δ = p t s - p t (n)$ ），然后将 $p t s$ 传播到 $p t (p)$ 中。它返回 $Δ$ 作为调用的结果。
void processCall(Var,Obj)
这个方法实现了第 10 讲课件第 124 页中的 ProcessCall 函数。
提示：
1. 你将在这个方法中处理所有种类的实例方法调用，即虚调用、接口调用和特殊调用。处理接口调用和特殊调用的逻辑与处理虚调用的逻辑完全相同（你在课上已经学过）。你也可以使用上面提到的 resolveCallee() （代替算法中的 Dispatch）来解析所有种类的实例方法调用，即虚调用、接口调用和特殊调用。
2. 为了保证 soundness，你应该将一个方法中由返回变量（即返回语句中出现的变量）所指向的所有对象传播给其调用点等号左侧的变量。你可以通过相关的 IR 对象获得一个方法的所有返回变量。

我们已经为上述 API 提供了代码框架，你的任务是填入带有注释 “TODO – finish me“ 的部分。

3 运行与测试

你可以按照 Tai-e 框架（教学版）配置指南中的描述来运行指针分析程序。在这次作业中，Tai-e 对程序进行非上下文敏感的指针分析，并输出各类指针的指针集以及最后构建出的调用图：

--------------Pointer analysis statistics:--------------

#var pointers: 0

#var points-to: 0

#static field points-to: 0

#instance field points-to: 0

#array indexes points-to: 0

#reachable methods: 0

#call graph edges: 0

----------------------------------------

Points-to sets of all variables

Points-to sets of all static fields

Points-to sets of all instance fields

Points-to sets of all array indexes

#reachable methods: 0

----------Reachable methods:----------

#call graph edges: 0

----------Call graph edges:----------

----------------------------------------

由于你还没有完成指针分析程序，所以指针集和调用图都是空的。在你完整地实现指针分析后，输出结果应该形如：

--------------Pointer analysis statistics:--------------

#var pointers: 13

#var points-to: 17

#static field points-to: 0

#instance field points-to: 0

#array indexes points-to: 0

#reachable methods: 5

#call graph edges: 6

----------------------------------------

Points-to sets of all variables

<A: void <init>()>/%this -> [NewObj{<B: A foo(A)>[0@L18] new A}, NewObj{<Example: void main(java.lang.String[])>[0@L4] new A}, NewObj{<Example: void main(java.lang.String[])>[3@L5] new B}]

<B: A foo(A)>/%this -> [NewObj{<Example: void main(java.lang.String[])>[3@L5] new B}]

<B: A foo(A)>/r -> [NewObj{<B: A foo(A)>[0@L18] new A}]

<B: A foo(A)>/temp$0 -> [NewObj{<B: A foo(A)>[0@L18] new A}]

<B: A foo(A)>/y -> [NewObj{<Example: void main(java.lang.String[])>[0@L4] new A}]

<B: void <init>()>/%this -> [NewObj{<Example: void main(java.lang.String[])>[3@L5] new B}]

<Example: void main(java.lang.String[])>/a -> [NewObj{<Example: void main(java.lang.String[])>[0@L4] new A}]

<Example: void main(java.lang.String[])>/b -> [NewObj{<Example: void main(java.lang.String[])>[3@L5] new B}]

<Example: void main(java.lang.String[])>/c -> [NewObj{<B: A foo(A)>[0@L18] new A}]

<Example: void main(java.lang.String[])>/temp$0 -> [NewObj{<Example: void main(java.lang.String[])>[0@L4] new A}]

<Example: void main(java.lang.String[])>/temp$1 -> [NewObj{<Example: void main(java.lang.String[])>[3@L5] new B}]

<Example: void main(java.lang.String[])>/temp$2 -> [NewObj{<B: A foo(A)>[0@L18] new A}]

<java.lang.Object: void <init>()>/%this -> [NewObj{<B: A foo(A)>[0@L18] new A}, NewObj{<Example: void main(java.lang.String[])>[0@L4] new A}, NewObj{<Example: void main(java.lang.String[])>[3@L5] new B}]

Points-to sets of all static fields

Points-to sets of all instance fields

Points-to sets of all array indexes

#reachable methods: 5

----------Reachable methods:----------

<A: void <init>()>

<B: A foo(A)>

<B: void <init>()>

<Example: void main(java.lang.String[])>

<java.lang.Object: void <init>()>

#call graph edges: 6

----------Call graph edges:----------

<A: void <init>()>[0@L10] invokespecial %this.<java.lang.Object: void <init>()>(); -> [<java.lang.Object: void <init>()>]

<B: A foo(A)>[1@L18] invokespecial temp$0.<A: void <init>()>(); -> [<A: void <init>()>]

<B: void <init>()>[0@L16] invokespecial %this.<A: void <init>()>(); -> [<A: void <init>()>]

<Example: void main(java.lang.String[])>[1@L4] invokespecial temp$0.<A: void <init>()>(); -> [<A: void <init>()>]

<Example: void main(java.lang.String[])>[4@L5] invokespecial temp$1.<B: void <init>()>(); -> [<B: void <init>()>]

<Example: void main(java.lang.String[])>[6@L6] temp$2 = invokevirtual b.<A: A foo(A)>(a); -> [<B: A foo(A)>]

----------------------------------------

此外，Tai-e 将其分析过的程序的类的 IRs 输出到文件夹 output/。这些 IR 以 .tir 文件的形式存储，可以被通用的文本编辑器打开。

我们提供了测试驱动程序 pascal.taie.analysis.pta.CIPTATest，你可以用它来测试你的实现。

我们鼓励你使用你在作业 4 中的实现，即基于 CHA 的调用图构建器，来分析这个作业中的测试样例（例如，Example.java），并观察由 CHA 和指针分析构建的调用图的精度差异。

4 通用准则

在这次作业中，你只需要保证实现的正确性。不必过早考虑效率。
禁止把你的作业包发给其他人参考。
禁止抄袭。自己的工作必须由自己完成。

5 作业提交

你应当提交一个 zip 文件，其中包括你实现好的以下类：

Solver.java

6 评分

你可以参照实验作业评测系统使用指南来使用我们的作业评测系统对你完成的作业进行评分。

你的分数将取决于你实现的正确性：我们将用你提交的实现来分析 src/test/resources/ 目录下的测试文件。另外，我们也会分析未公开提供的测试用例，比较其得到的结果和正确的分析结果从而进行评分。

祝君好运!

# 实验作业 5

作业 5：非上下文敏感指针分析

# 1 作业导览

# 2 实现指针分析

# 2.1 分析范围

# 2.2 新分析规则

# 2.3 Tai-e 中你需要了解的类

# 2.4 你的任务 [重点!]

# 3 运行与测试

# 4 通用准则

# 5 作业提交

# 6 评分

实验作业 5

1 作业导览

2 实现指针分析

2.1 分析范围

2.2 新分析规则

2.3 Tai-e 中你需要了解的类

2.4 你的任务 [重点!]

3 运行与测试

4 通用准则

5 作业提交

6 评分