Context Sensitive Pointer Analysis: Algorithms

How to Implement Context-Sensitive Pointer Analysis

相互依赖的过程

类似于上下文无关指针分析，依旧是在构建 PFG 的同时利用 PFG 传播指针信息。

C.S. Pointer Analysis: Algorithm

算法如下所示：

算法

这里和前面类似，主要是加上了限定的上下文，就不再赘述，对于上下文的信息，在调用规则里也有体现。

Context Sensitivity Variants

Call-Site Sensitivity

select

Select 算法会根据三个参数来确定，分别是调用者上下文，调用点，有堆上下文的接收对象。

上下文无关可以被视为 C.S.分析框架中上下文敏感性的一个特例：Select(,,) = []

每个上下文都由一系列调用点（调用链）组成，在方法调用时，将调用位置追加到调用者上下文中作为被调用者上下文，本质上是对调用栈的抽象。

call-string

这个方法存在一定的问题，看下图例子：

call-string

可以看到在函数之间循环的调用时，会导致调用链无限变长。所以这里的 k 其实就是用于对上下文抽象的限制。

Motivation

  • 确保指针分析终止

  • 避免在现实世界程序中过多上下文（长调用链）导致指针分析爆炸

Approach

  • 每个上下文由调用链的最后 k 个调用站点组成
  • 实际上，k 是一个小数（通常≤3）
  • 方法上下文和堆上下文可能使用不同的 k
    • 例如，方法上下文中 k=2，堆上下文中 k=1

k-Call-Site Sensitivity/k-CFA

  • 1-call-site/1-CFA

    1-CFA

  • 2-call-site/2-CFA

    2-CFA

Object Sensitivity

select

每个上下文都由一个抽象对象列表（由它们的分配位置表示）组成

这里利用 receive object 来作为上下文信息。

区分不同对象上的数据流操作。示例如下：

select

Call-Site vs. Object Sensitivity

select

虽然这里如果让 k = 2 可以避免不准确的情况，但是 1-object 就能做到，主要是由于处理不了调用点相同的情况。或者说如果再多一个调用，那么 k = 2 也无法避免了，但是这里是可以用调用的对象作为上下文区分的。

但是前文的例子让 1-object 来分析也会造成不准确，所以说从理论上讲，它们的精度是不可以进行比较的。不过在实践中，对象敏感性通常优于面向对象语言（如 Java）的调用点敏感性，或许这就是 OO 语言围绕对象的必然结果。

Type Sensitivity

select

在方法调用中，使用包含接收者对象分配位置及其堆上下文的类型作为调用者上下文，即调用点所在类的类型。

这是一个关于对象敏感度的更粗糙的抽象。

在相同的 k 限制下，类型敏感度的精度不优于对象敏感度。

object > type

与对象敏感性相比，类型敏感性通过合并相同类型中的分配位置，以牺牲精度换取更高的效率。

总结