Motivation

CHA存在一些问题,会导致不精确的常量分析，如下图所示：

由于CHA只考虑类名，不考虑上下文，所以会追踪到三个目标方法，导致x = NAC，但实际上调用的只是其中一个，这是不精确的，结果应该是x = 1。

Introduction to Pointer Analysis

指针分析是一个基础性的静态分析，计算指针可以指向的内存位置。对于面向对象（侧重于Java）的程序。计算指针（变量或字段）可以指向的对象。指针分析被看作may-analysis，会过度计算指针可以指向的对象集合，即“指针可能指向哪些对象？”。

如上图例子所示，指针分析就是将一个输入的程序，输出为指针和对象之间的指向关系。

Pointer Analysis and Alias Analysis是两个密切但不相关的概念

  • 指针分析：指针可以指向哪些对象？

  • 别名分析：两个指针可以指向同一个对象吗？

如果两个指针（比如 p 和 q）引用同一个对象，那么 p 和 q 之间就是别名的关系。

p = new C();
q = p;

别名的信息是可以根据指针分析推导出来的。

Applications of Pointer Analysis

  • Fundamental information

    • Call graph, aliases, …

  • Compiler optimization

    • Virtual call inlining, …

  • Bug detection

    • Null pointer detection, …

  • Security analysis

    • Information flow analysis, …

Key Factors of Pointer Analysis

指针分析是一个复杂的系统，影响系统精度和效率的因素很多

Factor Problem Choice
Heap abstraction How to model heap memory? Allocation-site
Storeless
Context sensitivity How to model calling contexts? Context-sensitive
Context-insensitive
Flow sensitivity How to model control flow? Flow-sensitive
Flow-insensitive
Analysis scope Which parts of program should be analyzed? Whole-program
Demand-driven

Heap abstraction

在动态执行中，由于循环和递归，堆对象的数量可以不受限制，为了确保终止，所以我们要通过堆抽象模型将动态分配、无界的具体对象作为有限的抽象对象进行静态分析。

Allocation-Site Abstraction

分配站点抽象是最常用的堆抽象

  • 按分配位置对具体对象进行建模
  • 每个分配站点一个抽象对象，用于表示其所有分配的具体对象

如图所示，设o2是一个创建点，在此处创建了三个对象，利用Allocation-Site Abstraction仅利用一个抽象的对象o2来表示这些对象。可以保证静态分析处理的对象是有限的。

Context Sensitivity

如何对调用上下文进行建模？

Context-sensitive Context-insensitive
Distinguish different calling contexts of a method Merge all calling contexts of a method
Analyze each method multiple times, once for each context Analyze each method once

前者会根据不同的上下文产生不同的结果，而后者对不同的上下文应用相同的分析，所以后者是不准确的。不过我们可以先从后者开始学习起来。

Flow Sensitivity

如何对控制流进行建模？

Flow-sensitive Flow-insensitive
Respect the execution order of the statements Ignore the control-flow order, treat the program as a set of unordered statements
Maintain a map of points-to relations at each program location Maintain one map of points-to relations for the whole program

目前在Java当中并没有证明谁更好，所以在这里学习更简单的Flow-insensitive。

Analysis Scope

Whole-program Demand-driven
Compute points-to information for all pointers in the program Only compute points-to information for the pointers that may affect specific sites of interest (on demand)
Provide information for all possible clients Provide information for specific clients

Concerned Statements

只关注影响指针的语句

Pointers in Java

  • Local variable: x
  • Static field: C.f（有时称为全局变量）
  • Instance field: x.f（建模为由 x 指向的对象的字段f）
  • Array element: array[i]（忽略索引，被建模为一个由数组指向的对象，具有一个字段，例如 arr，该字段可以指向存储在数组中的任何值，如下图所示）

因此，指针分析中会影响指针的语句有：

New x = new T()
Assign x = y
Store x.f = y
Load y = x.f
Call r = x.k(a, …)
其中，通过引入临时变量，将复杂的内存访问转换为三地址代码

而在Call中，有三种情况：

  • Static call C.foo()
  • Special call super.foo()/x.()/this.privateFoo()
  • Virtual call x.foo()

这里面的前两条较为简单，而Virtual Call较为复杂是分析的重点。