前言

虽然指针分析本身已经比CHA精确很多，但是前面我们学习的指针分析是上下文不敏感的，相对于上下文敏感的指针分析来说，会有一些false positives。谭添老师提到，上下文敏感分析是目前Java指针分析中最有效的分析方式。本节和下一节，我们将学习上下文敏感的指针分析。

上下文不敏感的指针分析存在的问题

我们首先来看一个例子：

void main() {
	Number n1, n2, x, y;
    n1 = new One();
    n2 = new Two();
    x = id(n1);
    y = id(n2);
    int i = x.get();
}
Number id(Number n) {
	return n;
}
interface Number { int get(); }
class One implements Number { public int get() { return 1; }}
class Two implements Number { public int get() { return 2; }}

对于这样一个例子来说，上下文不敏感的指针分析将构建出如下PFG：

graph TD A("n1\n{o1}") --> C("n\n{o1, o2}") B("n2\n{o2}") --> C C --> D("x\n{o1, o2}") C --> E("y\n{o1, o2}")

我们如果在此基础上进行常量传播，变量$i$的结果将是NAC，因为它可能是1或2。然而，事实上该程序真正执行时，变量$i$只可能是1，也就是变量$x$只可能指向对象$o_{1}$。

这个例子展示了上下文不敏感分析的误报问题。

对于同样的例子，我们如果采用上下文敏感的分析思路，将构建出如下的PFG：

graph TD A("n1\n{o1}") --> C("id(n1): n\n{o1}") B("n2\n{o2}") --> D("id(n2): n\n{o2}") C --> E("x\n{o1}") D --> F("y\n{o2}")

此时前述误报消失，变量$i$的常量传播结果将是1，因为变量$x$只指向对象$o_{1}$。

总的来看，上下文不敏感（context insensitivity，简称C.I.）分析的不精确性主要体现在：

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

上下文敏感分析简介

上下文敏感（context sensitivity，简称C.S.）分析通过区分不同上下文中的不同数据流来对调用上下文进行建模，从而提升准确性。

Call-Site Sensitivity

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

例如，对于下面这一小段代码，在call-site sensitivity策略下，id(Number)方法有两个不同的上下文[1]和[2]：

1 x = id(n1);
2 y = id(n2);
3 int i = x.get();
4
5 Number id(Number n) {
6     return n;
7 }

Cloning-Based Context Sensitivity

另外，一种最直观的上下文敏感实现方式是“cloning-based context sensitivity”，每个方法和变量都会带有一个或多个上下文。针对代码中的一个方法或变量，我们仿佛是为每个上下文克隆了一个该方法或变量，从而将它们区分开来。上述代码相应的PFG如下图所示：

graph TD A("n1\n{o1}") --> C("[1]:n\n{o1}") B("n2\n{o2}") --> D("[2]:n\n{o2}") C --> E("x\n{o1}") D --> F("y\n{o2}")

Context-Sensitive Heap

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

image-20230406202300628

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

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

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

下面是一个对比的案例。左侧表格展示的是对方法、变量应用上下文敏感处理，但不对堆进行上下文敏感处理的指针分析结果；右侧展示的是对方法、变量和堆都进行上下文敏感处理的指针分析结果，可以看出，后者比前者更精准：

image-20230406203335797

另外，同时对方法、变量和堆进行上下文敏感处理才能最大程度地提高精确度，只处理后者不处理前者同样会导致精确度降低：

image-20230406203420127

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

老规矩，还是先介绍一下相关的域（domain）和记法：

  • Context: $c, c’, c’’ \in C$
  • Context-sensitive methods: $c:m \in C \times M$
  • Context-sensitive variables: $c:x,\ c’:y \in C \times V$
  • Context-sensitive objects: $c:o_{i},\ c’:o_{j} \in C \times O$
  • Fields: $f, g \in F$
  • Instance fields: $c: o_{i}.f,\ c’:o_{j}.g \in C \times O \times F$
  • Context-sensitive pointers: $\text{CSPointer} = (C \times V) \cup (C \times O \times F)$
  • Points-to relations: $pt: \text{CSPointer} \rightarrow P(C \times O)$

规则部分与之前学过的上下文不敏感的指针分析规则类似，横线上方是前提（premise），下方是结论（conclusion）。其中，New对应的规则的横线上方是空的，意味着无条件得出下方的结论。

种类 语句 规则 图示
New i: x = new T() $\frac{}{c:o_{i} \in pt(c:x)}$ image-20230406205623478
Assign x = y $\frac{c’:o_{i} \in pt(c:y)}{c’:o_{i} \in pt(c:x)}$ image-20230406205641934
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)}$ image-20230406205657782
Load y = x.f $\frac{c’:o_{i} \in pt(c:x),\ c’’:o_{j} \in pt(c’:o_{i}.f)}{c’’:o_{j} \in pt(c:y)}$ image-20230406205716742
Call l: r = x.k(a1, ..., an) image-20230406215641893 -

其中，$Select$函数用于为目标方法$m$根据call site $l$处的信息选取对应的上下文，$c^{t}$是callee的上下文。

image-20230406220110061

总结与思考

本节课，我们初步学习了上下文敏感的指针分析，下一节将继续学习这一技术。

这一节的B站视频只有四千多播放量了——而世之奇伟、瑰怪，非常之观，常在于险远，而人之所罕至焉，故非有志者不能至也。