实验作业 7

作业 7：Alias-Aware 的过程间常量传播

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

作业出品：谭添、李樾

1 作业导览

为 Java 实现一个 alias-aware 的过程间常量传播分析

在本次作业中，你需要在作业4的基础上，进一步提高常量传播的精度。具体而言，你需要借助之前作业中实现的指针分析，根据指针分析结果来得到程序中的别名（alias）信息，并用这一信息来在过程间常量传播中更精确地处理对象字段（field）和数组（array）。

和作业4一样，常量传播中只需要考虑 int 类型的值，但在本次作业中，你需要额外考虑程序中的别名，用别名信息来更精确地处理对字段和数组的存取。不过，你可以忽略一些将在第 2 节描述的情况。之后我们将会介绍为了完成本作业所必要的知识。如果你的实现是正确的，你能够观察到：alias-aware 的过程间常量传播相比你在作业 4 中实现的那个具有更高的精度。

之前的所有作业相比，本次作业的开放性更高：我们只在文档中描述你“需要做什么”，而将实现的细节留给你来确定，也就是说你需要自行决定“怎么做”。

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

2 Alias-Aware的常量传播

本节中，我们首先介绍何为别名，然后讨论如何使用别名来处理字段和数组。

2.1 别名

别名用于描述以下情况：一个内存中的数据位置可以通过不同的符号名来访问，这些指向内存中的同一位置的不同符号互为别名。在 Java 中，对实例字段和数组的访问可以形成别名，举例来说，如果变量 x 和 y 指向相同的对象，那么 x.f 和 y.f 这两个字段访问构成了别名open in new window，因为它们实际上指向同一个字段；如果变量 a 和 b 指向同一个数组，并且 i 和 j 有相同的值，那么 a[i] 和 b[j] 这两个数组访问构成了别名，因为它们实际上指向同一个数组中的同一个位置。

在别名存在的情况下，通过对一个字段/数组的访问来修改一个实例字段/数组将会同时修改与这一访问相关的所有别名值。举例来说，如果 x.f，y.f 和 z.f 互为别名，那么 store 语句 x.f = 5; 不仅将 x.f 的值修改为 5，而且同时将 y.f 和 z.f 的值设为 5。因此，为了在常量传播中精确地分析字段和数组的值，我们需要取得被分析程序的别名信息。

值得注意的是，Java 中的静态字段不能拥有别名：对一个静态字段 T.f，它有唯一的符号名（即 T.f），且只能通过 T.f 被访问。由于不需要考虑别名的存在，对静态字段的处理要比对实例字段和数组的处理简单。

2.2 分析实例字段

更精确地处理实例字段. 在作业2和作业4中，我们对实例字段的 load 语句进行了保守的处理，即直接将 load 语句等号左侧的变量设置为 NAC：

x = a.f; // always set val(x) to NAC in previous assignments

在本次作业中，我们朝着精度更高的方向迈进了一步：当分析实例字段的 load 语句时（设该语句为 L），我们找到所有对这一实例字段（以及其别名）进行修改的 store 语句，并将这些语句要 store 的值 meet 之后赋给 L 等号左侧的变量，如下所示：

   y = 5;
   p.f = y; // p.f is an alias of a.f
   ...
L: x = a.f; // meet val(y) to val(x)

此时，若所有可能的 store 语句赋予该字段的值都为同一个常量（本例中为5），那么相比于之前保守的处理方法（认为 x = NAC），我们能得到一个更精确的结果（x = 5）。现在假设另一种情况：某个实例字段被多个 store 语句赋予了不同的值（例如 q.f = 6; 且 q.f 也是 a.f 的别名），或该实例字段被赋值为 NAC（例如 p.f = y; 且 y = NAC），那么为了保证分析 soundness，load 该实例字段的语句 L 等号左侧的变量也应当是 NAC (即 x = NAC)。

计算别名信息. 在本次作业中，我们借助你在之前的作业中实现的指针分析来计算程序的别名信息。具体而言，对任意两个实例字段的访问（设为 x.f 和 y.f），如果它们的 base 变量的指针集（points-to set）有交集（即 x 和 y 的指针集有交集），那么我们认为对这两个实例字段的访问（x.f 和 y.f）互为别名。

分析实例字段的精度取舍. 你可能注意到了，我们上面描述的处理实例字段的方式忽略了 load 和 store 语句出现的顺序，也就是说，我们的处理是流不敏感的（flow-insensitive）。和其他流不敏感的分析一样，这种处理方式会损失一些精度，例如如下代码片段：

p = q = a;
p.f = 555;
x = a.f; // x -> NAC in the current handling
q.f = 666;

分析可以发现 p.f 和 q.f 都是 a.f 的别名，因此我们将所有 store 到 a.f 和其任意别名的值（即 555 和 666）进行 meet 之后赋给 load 语句 x = a.f 的左侧变量 x，从而结果得到 x 在第 3 行后为 NAC，这实际上是不精确的结果。

我们可以通过一些别的分析手段来获得比上面的处理方式更高的精度，例如采用流敏感的方式追踪所有的变量和 access path 的值（一个 access path 表示由一个变量和一系列的字段名构成的访问路径，例如 p.f 和 q.f.g ）。然而，这种处理方式需要对分析算法进行复杂的修改，因此我们在本次作业中选择上述更为简单直接的处理方式。

2.3 分析静态字段

对静态字段的处理比实例字段简单，因为你不需要考虑静态字段的别名。当处理一个静态字段的 load 语句时（假设为 x = T.f;），你只需要找到对同一个字段（T.f）的 store 语句，并将这些保存进字段的值进行 meet 后赋给 load 语句等号左侧的变量（x）。这一处理可以在没有指针分析和别名信息的情况下完成。

值得注意的是，静态字段的值可能来自于字段的初始化（field initializeropen in new window）或类静态初始化块（static initializeropen in new window），例如下面代码片段中的第 2 行和第 7 行：

class A {
    static int one = 1; // field initializer
    static int two;

    static { // static initializer
        one = 1; // generated for field initializer at line 2
        two = 2;
    }
}

具体而言，第 2 行的静态字段初始化会被编译为一个静态初始化块（5 - 8 行）中的 store 语句（第 6 行），因此仅处理静态初始化块即可。然而，本次作业中的 call graph builder 并不处理静态初始化块（但在 Tai-e 中它们会被正确处理），因此这些 store 语句在 ICFG 上是不可达的。简单起见，我们在本次作业中忽略字段的初始化和静态初始化块。

2.4 分析数组

对数组的处理和对实例字段的处理类似。当分析一个数组的 load 语句如 x = a[i]; 时，你需要找到所有修改 a[i] 别名的值的 store 语句，并将这些值 meet 后赋给 x。此处对数组的处理要更复杂一些：当你判断两个对数组的访问 a[i] 和 b[j] 是否互为别名时，你不仅需要考虑它们的 base 变量（a 和 b）的指针集是否有交集，还需要考虑索引值 i 和 j 的关系。有趣的是，由于数组索引也是 int 类型，因此你可以用常量分析来实时计算 i 和 j 的关系。

假设 a 和 b 的指针集有交集，我们根据常量传播中 i 和 j 的结果来决定 a[i] 和 b[j] 是否互为别名。具体参照如下表格（该设计考虑了分析的单调性并确保了分析的 soundness）：

`a[i] and b[j]`	`j = UNDEF`	`j =` $c_{2}$	`j = NAC`
`i = UNDEF`	不互为别名	不互为别名	不互为别名
`i =` $c_{1}$	不互为别名	当且仅当 $c_{1} = c_{2}$ 时互为别名	互为别名
`i = NAC`	不互为别名	互为别名	互为别名

2.5 对字段/数组初始化的说明

由于我们对于字段和数组的处理是流不敏感的，所以当分析 load 一个字段/数组的语句时，我们需要 meet 所有被 store 到该字段/数组的值。在 Java 中，和局部变量不同，字段（包括实例字段和静态字段）和数组即使没有被显式地初始化过也能被 load，这是因为 Java 会隐式地给 int 类型赋初始值为 0open in new window。例如下面这一代码片段：

class A {
    int f; // f is implicitly initialized to 0 by default
}
...
A a = new A();
// a.f = 5;
int x = a.f;

即使对象 new A 的字段 f 没有被显式地初始化，它仍然能够在第 7 行被 load，并且 load 得到的结果为 0（Java 的隐式初始化）。

在这种隐式初始化存在的情况下，如果一个实例字段在程序中被赋予了一个非 0 常量（比如将上述代码片段中的第 6 行解除注释），我们就必须认为它的值为 NAC。这是将它的默认初始化值 0 和被赋予的值（上述代码片段中的值 5）进行 meet 后得到的，也就是说我们会在第 7 行得到 x = NAC。在这种情况下，你会发现我们上面所描述的对字段和数组的处理都变得没有意义了：它会认为任何被 load 的值都是 NAC。

为了处理这一情况，我们为被分析程序设置一个合理的假设：假设所有程序中的字段和数组都在被 load 之前通过 store 语句显式地初始化了。在这一假设下，所有的 load 语句得到的值一定来自于程序中的 store 语句，因此我们可以忽略默认初始值 0 对 int 型字段和数组带来的影响。

3 实现 Alias-Aware 的常量传播

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

大多数你需要用到的类已经在作业 4 和作业 6 中被介绍过。本次作业只引入以下两个新的类。

pascal.taie.analysis.pta.PointerAnalysisResult
该类提供了一系列查询指针分析结果的 API，你可以用它来计算别名信息。值得注意的是，该类分别提供对带上下文的分析结果的查询（例如 getPointsToSet(CSVar)），和对不带上下文的分析结果的查询（例如 getPointsToSet(Var)）。由于过程间常量传播不需要知道指针分析结果中的上下文信息，你应该使用不带上下文的指针分析结果。(注：针对一个上下文敏感的指针分析的分析结果，Tai-e 通过将同一指针在不同上下文下的指针集合并，并将不同上下文下的同一堆对象合并为一个堆对象，来去除上下文敏感的指针分析的结果中的上下文信息。需要注意的是，虽然结果中没有上下文信息，但相比于非上下文敏感，该结果取得了上下文敏感所能带来的精度提升）
pascal.taie.ir.exp.ArrayAccess
该类代表了数组访问表达式，例如 a[i]，该类的实例在类 StoreArray 和 LoadArray 的实例中出现。

3.2 你的任务 [重点!]

在本次作业中，你需要实现你在作业 4 中实现过的两个类的 API，即来自 pascal.taie.analysis.dataflow.inter.InterConstantPropagation 的六个 API：

boolean transferCallNode(Stmt,CPFact,CPFact)
boolean transferNonCallNode(Stmt,CPFact,CPFact)
CPFact transferNormalEdge(NormalEdge,CPFact)
CPFact transferCallToReturnEdge(CallToReturnEdge,CPFact)
CPFact transferCallEdge(LocalEdge,CPFact)
CPFact transferReturnEdge(LocalEdge,CPFact)

和来自 pascal.taie.analysis.dataflow.inter.InterSolver 的两个 API:

void initialize()
void doSolve()

本次作业中，你需要按照第 2 节中描述的那样，更加精确地处理实例字段、静态字段和数组。再次说明：本次作业开放性较高，你需要自行决定实现方式的细节。

和作业 4 类似，为了使 InterConstantPropagation 类可用，你需要首先完成 ConstantPropagation 类。你可以将你在作业 2 中的实现复制到本作业中。类似地，你需要完成 Solver（位于包 pascal.taie.analysis.pta.cs 中）和 _2ObjSelector（本作业的默认上下文 selector ）这两个类以进行上下文敏感的指针分析，其结果将被用来建立调用图（call graph）和计算别名信息。你可以将你在作业 6 中的实现复制到本作业中。

提示：

InterConstantPropagation 的 initialize() 方法会在求解器启动前被调用，它包含了获取 PointerAnalysisResult 的相关代码，如果你的实现中需要进行一些初始化操作，你可以考虑在该方法中进行。
根据你的需要，你可以任意向 InterConstantPropagation 和 InterSolver 中添加 API 和字段。
InterConstantPropagation 在其字段中持有 InterSolver 的实例，因此你可以在 InterConstantPropagation 中调用 solver 的 API。

4 运行与测试

你可以我们在 Tai-e 框架（教学版）配置指南中提到的方式来运行分析。在本作业中，Tai-e 首先为输入程序执行一个上下文敏感的指针分析，并构建一个程序的调用图，然后根据调用图来构建 ICFG，最后在 ICFG 上执行过程间常量传播。为了方便调试，Tai-e 会输出调用图以及过程间常量传播的结果：

#reachable methods: 0

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

#call graph edges: 0

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

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

--------------------<InstanceField: void main(java.lang.String[])> (inter-constprop)--------------------

[0@L4] temp$0 = new A; null

[1@L4] invokespecial temp$0.<A: void <init>()>(); null

[2@L4] a1 = temp$0; null

[3@L5] temp$1 = 111; null

[4@L5] a1.<A: int f> = temp$1; null

[5@L6] x = a1.<A: int f>; null

[6@L7] temp$2 = new A; null

[7@L7] invokespecial temp$2.<A: void <init>()>(); null

[8@L7] a2 = temp$2; null

[9@L8] temp$3 = 222; null

[10@L8] a2.<A: int f> = temp$3; null

[11@L9] y = a2.<A: int f>; null

[12@L9] return; null

在你还未完成作业的时候，输出的调用图为空（没有可达方法），OUT facts 为 null 。当你完成了所有的空缺代码后，分析的输出应当形如：

#reachable methods: 3

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

<A: void <init>()>

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

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

#call graph edges: 3

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

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

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

<InstanceField: void main(java.lang.String[])>[7@L7] invokespecial temp$2.<A: void <init>()>(); -> [<A: void <init>()>]

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

--------------------<A: void <init>()> (inter-constprop)--------------------

[0@L13] invokespecial %this.<java.lang.Object: void <init>()>(); {}

[1@L13] return; {}

--------------------<InstanceField: void main(java.lang.String[])> (inter-constprop)--------------------

[0@L4] temp$0 = new A; {}

[1@L4] invokespecial temp$0.<A: void <init>()>(); {}

[2@L4] a1 = temp$0; {}

[3@L5] temp$1 = 111; {temp$1=111}

[4@L5] a1.<A: int f> = temp$1; {temp$1=111}

[5@L6] x = a1.<A: int f>; {temp$1=111, x=111}

[6@L7] temp$2 = new A; {temp$1=111, x=111}

[7@L7] invokespecial temp$2.<A: void <init>()>(); {temp$1=111, x=111}

[8@L7] a2 = temp$2; {temp$1=111, x=111}

[9@L8] temp$3 = 222; {temp$1=111, temp$3=222, x=111}

[10@L8] a2.<A: int f> = temp$3; {temp$1=111, temp$3=222, x=111}

[11@L9] y = a2.<A: int f>; {temp$1=111, temp$3=222, x=111, y=222}

[12@L9] return; {temp$1=111, temp$3=222, x=111, y=222}

和作业 4 一样，Tai-e 将被分析程序的 ICFG 输出到 output/ 文件夹，这些 ICFG 被储存为可以用 Graphviz 可视化打开的 .dot 文件。

我们为本次作业提供了测试驱动类 pascal.taie.analysis.dataflow.analysis.constprop. InterCPAliasTest，你可以按 Tai-e 框架（教学版）配置指南的描述来用它测试你的实现是否正确。

你可以使用你在在作业 4 中实现的代码来分析本次作业的测试用例，从而观察 alias-unaware 的常量传播和 alias-aware 的常量传播的精度区别。默认情况下，本次作业使用 2 层对象敏感（2-object-sensitive）指针分析来构建程序的调用图并计算别名信息。我们也鼓励你用其他的上下文敏感策略（例如非上下文敏感）来分析同样的测试用例（例如 ObjSens.java），从而观察指针分析的结果是如何从精度上影响一个依赖指针分析的后续分析的。你可以通过将第 6 次作业中你实现的其他几个 context selector 复制到本作业中来进行上述操作。

5 通用准则

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

6 作业提交

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

InterConstantPropagation.java
InterSolver.java
ConstantPropagation.java(optional)

如果你的提交包含该文件，则我们将会用你提交的 ConstantPropagation.java 来进行测试并评分，否则我们使用我们自己的该类来运行测试。

7 评分

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

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

祝君好运!

# 实验作业 7

作业 7：Alias-Aware 的过程间常量传播

# 1 作业导览

# 2 Alias-Aware的常量传播

# 2.1 别名

# 2.2 分析实例字段

# 2.3 分析静态字段

# 2.4 分析数组

# 2.5 对字段/数组初始化的说明

# 3 实现 Alias-Aware 的常量传播

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

# 3.2 你的任务 [重点!]

# 4 运行与测试

# 5 通用准则

# 6 作业提交

# 7 评分

实验作业 7

1 作业导览

2 Alias-Aware的常量传播

2.1 别名

2.2 分析实例字段

2.3 分析静态字段

2.4 分析数组

2.5 对字段/数组初始化的说明

3 实现 Alias-Aware 的常量传播

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

3.2 你的任务 [重点!]

4 运行与测试

5 通用准则

6 作业提交

7 评分