课程环境：https://tai-e.pascal-lab.net/lectures.html

课程视频：https://www.bilibili.com/video/BV1b7411K7P4

南大《软件分析》12.0 Pointer Analysis Context Sensitivity II

这一部分主要是介绍加入了 CS 之后的指针分析算法，同时还会介绍前面提到的上下文敏感策略。

Context Sensitive Pointer Analysis: Algorithms

由于要建立一个在 CS 下的 PFG（pointer flow graph），所以需要对 Nodes 和 Edges 重新基于上下文这一概念重新定义。

这里给出五种语句 new，assign，store，load，call 对应的 PFG 建立规则。

上图给出了整个 CS pointer analysis 的算法，与前面的 CI pointer analysis 的区别是为每个变量添加了一个上下文，同时在 ProcessCall 中还添加了一个 Select 算法用来决定当前环境下应该返回的上下文。事实上，从算法层面直观来看改变并不大，但是从理解上实际上是有一定难度的，需要明白每条语句是如何处理不同上下文的。

由于这一部分非常重要（指针分析是整个静态分析基础中的基础），这里算法中的一些部分进行简要解释：

需要注意的是不止算法部分发生了变化，同时 RM 和 CG 的概念也发生了变化，即这两者在新的算法中被限制在了 C.S 中，如下图所示。

老样子 Δ 中依旧存放的是需要传播的对象，这些对象可能是在不同上下文中的，用 表示，算法的后面一部分会对整个 Δ 进行遍历，紧接着是对 store/load 语句的处理，分别有 AddEdge(𝑐:𝑦, 𝑐′:𝑜𝑖.𝑓) 和 AddEdge(𝑐′:𝑜𝑖.𝑓, 𝑐:𝑦)，由于 x 和 y 是处在同一个上下文中（）的，因此这里它们两者的上下文是一样的用 𝑐 表示。

AddReachable

细心点的话可以发现，AddReachable 函数里面都是相同的上下文，这一点也可以从这个函数本身的功能来理解，因为它就是负责来解析当前方法中的 new 和 assign 语句，同时完成对 WL 和添加边的操作。而这些都是在一个方法内完成的，因此其上下文自然也是相同的（因为本质上不牵扯到函数调用）。

ProcessCall

这个函数其实可以根据前面提到的 call rule 来进行理解，在通过 select 选出上下文 之后，然后进行后续的操作。

Context Sensitivity Variants

这一部分会对前面提到的 Select 算法进行详细解释

前面接触的基于调用位置所在行来设置具体的上下文只是上下文敏感分析中的一种策略（Call-site sensitivity），这里还列出了另外两种策略 Object sensitivity 和 type sensitivity，同时给出了 Select 几个参数的含义。这里分别介绍这几种策略

Call-Site Sensitivity

这里给出了 call site sensitivity 的概念，看似说的很晦涩，实际上其实 call site 就是执行位置的调用堆栈（按这个来理解就可以了），这个调用堆栈的内容组成了 call chain

上图就是一个例子，只不过他这里把调用堆栈用行号表示了，原理上是一样的，只不过可以发现在存在递归的函数中，可能存在无穷个上下文，尽管实际运行过程中可能是有穷的，但是由于这里是从静态分析的角度触发，因此在通常情况下会对 call chain 的长度进行限制，尽管这在一定程度上丢失了一部分精度。怎么来理解上下文减少就丢失精度呢，前面有提过上下文实际上就是各个执行环境之间的隔离，这种隔离可以让我们更好的来分析对象的传播，而上下文的减少，则意味着隔离的环境减少，导致变量指向的对象变多了，从而丢失精度。

k-Limiting Context Abstraction

前面提到 call chain 的长度可能会过长，因此 K-CFA(k-Call-Site Sensitivity) 中的 K 就限制了 call chain 的长度。

同样的例子，对于 1-call-site 其结果如上图所示。

这里举了一个 1-call-site 的例子，可以看出最后 x 和 y 都返回了正确的结果。

Object Sensitivity

前面 call site sesitivity 是以调用点位置为核心建立的，而 object sensitivity 实际上是以分配点位置为核心建立的（Essentially allocation-site sensitivity）。

这里给出一个例子来方便理解，最后x也是正确的返回了对象，但是如果是使用 1-call-site，结果如何呢

可以发现 1-call-site返回的结果并不准确，理由是 1-call-site 将 call site 长度只设置为了 1，导致在处理 doSet 函数时，数据 流在这里进行了汇合，从而导致返回的结果并不准确。

但是在有些情况下 1-call-site 会返回正确的结果，而 1-object 会返回错误的结果

原因是在 1-object 的情况下，由于14行和15行的 this.id 的上下文都为 []，从而导致两次调用使得 [:n] = {}。

所以理论上，这两个策略的精确度是不能比较的，但在性能表现上 object sensitivity 是远远高于 call site 的。

Call-Site vs. Object Sensitivity

从两位老师做出的实验成果也可以看出从精度和效率上 object 都是好于 call-site的。

Type Sensitivity

但尽管 object 的效率高于 call site，在实际情况下想要让执行效率更快一点，所以就提出了 type sensitivity。

简单来说就是将同一个上下文中的所有 allocation site 看做是相同的。

最终实验数据结果比较如下：

思考题

总结

至此指针分析的内容彻底结束，虽然在内容上有了一定的理解，但后续仍需通过做实验来强化对这部分内容的理解。