以南大视频课件为主

Motivation
Introduction to Pointer Analysis 06:50
- Pointer Analysis and Alias Analysis 14:50
- Application of Pointer Analysis 17:20
Key Factors of Pointer Analysis 19:15
- Heap Abstration 21:30
- Context Sensitivity 27:40
- Flow Sensitivity 32:30
- Analysis Scope 45:40
- Pointer Analysis in This Course 52:20 --> 60:20
Concerned Statements 64:50
Conclusion&下节课内容 77:00

指针分析

南大小课堂开课啦～

Problem of CHA

void foo() {
  Number n = new One();
  int x = n.get();
}

interface Number {
  int get();
}

class Zero implements Number {
  public int get() { return 0; }
}

class One implements Number {
  public int get() { return 1; }
}

class Two implements Number {
  public int get() {return 2;}
}

在这个例子中，很显然object n，new的是一个One。

因此返回1。

如果按照CHA, 那么X就是根据变量类型(Number)来解，而Number有三个子类。因此此时x指向3个值(0, 1, 2)

一句话，CHA看不到object的声明类型。

因此在做常量传播的时候，我们的CHA方法就会拿到两个假值(0,2)，此时的结果就是NAC(不精确)。

而做指针分析，故名思义，就是知道n指向哪个object。

一个 class在new 的时候，会做如下事情：在内存中构造一个object, 运行构造函数，并使用n指向这个object, 因此这里的n就等同与一个指向object地址的指针。

这个例子中，指针分析可以知道n指向new One这个唯一对象。然后构造调用图(对new One做dispatch)，得到唯一一个get方法。

指针分析介绍

定义

指针分析可以看作一个基础的静态分析，他回答的问题是程序中每个指针可以指向那些地址。

对于OO语言来说，指针分析回答的是一个变量(或者field)可以指向哪些object(may analysis)。

Answer: Which object a pointer can point to?

Let's explain it by an analysis process:

void foo() {
  A a = new A();
  B x = new B();
  a.setB(x);
  B y = a.getB();
}

class A {
  B b;
  void setB(B b) {
    this.b = b;
  }
  B getB() {
    return this.b;
	}
}

本例子中，类A 是类B的容器，并提供了get, set方法。在foo()方法中，独立的new了A和B。而变量a是new A的指针，变量x是new B的指针。之后，a调用 setB方法将new B()，store进了new A()。接着又声明了变量y，通过getB方法获取了new B（指向，没 new）。

很datalog

Key Factors of Pointer Analysis

Allocation-Site Abstraction

### Context Sensitivity

How to model calling contexts?

上下文敏感，在指针分析中，如何对调用上下文进行建模。

上下文这个概念有点抽象。就是一个过程调用另一个过程时工作栈上的状态(好像更抽象了)。

class Test {
  public boolean foo(int p) {
 		if (p == 1)
    {
      return true;
    }
    else
    {
      return false;
    }
  }
}

  
void foo() {
  	Test a = new Test();
    Test b = new Test();
    int x = 1;
    boolean test_a = a.foo(x);
  	x = 2;	
  	boolean test_b = b.foo(x);
}

对于上下文敏感，对于同一个方法，他有多个上下文，么个上下文分别分析一次

这里有两个上下文，就会有两个不同的分析。

对于上下文不敏感：

方法foo()只分析一次。汇合上下文可能会丢失精度。

向下文敏感技术是一个重要技术，他能很大程度提高分析精度

Flow Sensitivity

How to model control flow?

因为同样的语句，如果顺序不同可能结果就不一样

int a = 1;
int b = 2;
a = b;
int c;
c = b-a;
c = a-b;

在程序的每一个点,都维护着一个映射(状态)。每一条语句，都存着数据流到达这一点的数据流信息

在指针分析中要做的流敏感，就要让每一个指针维持一个指向关系集合：

在这个图片中，可以看到变量c指向了new C, 经过Allocation-site Abstraction后就是o1

c->{o1}

然后第二句对一个字面量"x"进行了store操作，符号c.f也就是o1.f。

第三句中s = c.f把o1.f取出来塞给了s。

到了第四句o1.f更新了。

人为的去审计当然是指影响o1.f了，因为顺序执行,s的赋值语句已经被执行过了。

但是在流不敏感的情况下，分析程序只知道: s = o1.f，至于在程序流的哪个位置上是不管的。

因此在第四行：

流敏感: s->{"x"}, o1.f->{"y"}

流不敏感：

把程序当成无序集合，将所有的控制流信息忽略掉。

因此在整个程序中，流不敏感只维护一个指针集

所有只维护一个map, 记录程序在运行期间所有指向的对象。

注意由于流不敏感的分析忽略了控制流信息，因此为了保证分析结果是safe的，在分析到s指向o1.f后，就要把程序中所有o1.f map的对象全部传给s(保守期间)。

! 目前没有证据在JAVA上Flow Sensitive 对 Flow Senisitive 精确许多

Analysis Scope

Which parts of program should be analyzed?

全程序分析(Whole-program)
按需分析(Demand-driven)

对于如下例子:

如果我们只想知道程序中第5行的call graph,那么我们只需要对变量z做指针分析就可以了。

z->{o4}

有时候按需分析不一定比全程序块，可能设计大量冗余计算。

What Do We Analyze?

以下是语句不会修改指针指向的语句：

~~if else~~

~~switch case~~

~~for/while/do...while~~

~~break/continue~~

...

Java当中有哪些指针：

Local variable: x (数量最多)
Static field: C.f (与处理variable类似，有文献看作是global field)
Instance field: x.f (instance field是将x.f的组合看作一个指针，也是需要重点分析)
Array element: array[i]

对于数组，静态分析的通用做法是建模成只有一个field的object

Ignore indexes. Modeled as an object(pointed by array) with a single field, say arr, which may point to any value stored in array.

在右边的指针分析中，注意array在声明时new 无长度信息，因为将array看作一个object, 包含唯一的field arr. 对所有下标(无视下标)都看作对这个field进行store。

所以，指针分析基本上就是围绕以下五条语句：

x = new T()   // New 
x = y // Assign
x.f = y // Store
y = x.f // Load  
r = x.k(a, ...)  // Call

使用三地址码简化分析

Complex memory-accesses will be converted to three-address code by introducing temporary variables

x.f.g.h = y;
t1 = x.f;
t2 = t1.g;
t2.h = y;