目录：

1. Motivation
2. 指针分析介绍
3. 影响指针分析的关键要素
4. 分析哪些语句

重点：

什么是指针分析？影响指针分析的关键因素是什么？指针分析要分析哪些指令？

---

1.Motivation

指针分析必要性：

6-1-PTA-motivation.png

---

2.指针分析

目标：分析程序指针可以指向哪些内存。对于Java等面向对象语言，主要分析指针指向哪个对象。

说明：指针分析属于may analysis，分析的结果是某指针所有可能指向哪些对象，是个over-approximation集合。

示例：面向对象语言中的指针指向问题。对于setB()函数，this指向new A()，因为是调用者是a.setB()；setB()中的b是x传过来的，所以b指向new B()，A.b指向 new B()。

6-2-1-PTA示例.png

区别：

• 指针分析：分析指针所有可能指向的对象。
• 别名分析：分析两个指针是否指向相同的对象，可通过指针分析来推导得到。

应用：基本信息（别名分析/调用图），编译优化（嵌入虚拟调用），漏洞（空指针），安全分析（信息流）。

---

3.影响指针分析的关键要素

指标：精度（precision）& 效率（efficiency）。

影响因素：本课程，我们主要分析分配点的堆抽象技术、上下文敏感/不敏感、流不敏感、全程序分析。

因素	问题	选项
Heap abstraction	如何建模堆内存？	• Allocation-site • Storeless
Context sensitivity	如何建模调用上下文？	• Context-sensitive • Context-insensitive
Flow sensitivity	如何建模控制流？	• Flow-sensitive • Flow-insensitive
Analysis scope	分析哪部分程序？	• Whole-program • Demand-driven

（1）堆抽象（内存建模）

问题：程序动态执行时，堆对象个数理论上是无穷无尽的，但静态分析无法处理这个问题。所以为保证指针分析可以终止，我们采用堆抽象技术，将无穷的具体对象抽象成有限的抽象对象。也即，将有共性的对象抽象成1个静态对象，从而限制静态分析对象的个数。

// 示例
for (...) {
    A a = new A();
}

技术概览：

6-3-1-堆抽象技术概览.png

我们只学习Allocation-Site技术，最常见也最常被使用。

Allocation-Site原理：将动态对象抽象成它们的创建点（Allocation-Site），来表示在该点创建的所有动态对象。Allocation-Site个数是有限的。

示例：循环创建了3个对象，我们用O₂来抽象表示这3个动态对象。

6-3-2-堆抽象示例.png

（2）上下文敏感 Context Sensitivity

问题：考虑是否区分不同call-site对同一函数的调用。

• Context-sensitive：根据某函数调用上下文的不同，多次分析同一函数。

• Context-insensitive：每个函数只分析一次。

  
  6-3-3-上下文敏感示例.png

（3）流敏感 Flow Sensitivity

问题：考虑语句顺序（控制流）的影响 vs 把程序当做无序语句的集合。

方法：流敏感会在每个程序点都保存一份指针指向关系映射，而流不敏感则对整个程序保存一份指向关系映射。

说明：目前流敏感对Java提升不大，不过在C中很有效，本课程分析的是Java，所以重点讨论流不敏感技术。

指针分析示例：

6-3-4-流敏感示例.png

（4）分析范围 Analysis Scope

问题：分析程序的哪一部分？

• Whole-program 全程序：分析全程序的指向关系。
• Demand-driven 需求驱动：只分析影响特定域的指针的指向关系。

---

4.分析哪些语句

问题：哪些语句会影响指针指向，那就只分析这些语句。

Java指针类型：

1. Lacal variable: x

2. Static field:C.f （有时称为全局变量）——不分析

3. Instance field: x.f （对象的field）

4. Array element: array[i] ——不分析，因为静态分析无法确定下标，所以将array中所有成员映射到一个field中，等价于Instance field，所以不重复分析。如下图所示：
   

   6-4-1-数组处理.png

影响指针指向的语句：

1. New: x = new T()
2. Assign：x = y
3. Store： x.f = y
4. Load： y = x.f
5. Call： r = x.k(a,...)
   • Static call： C.foo()
   • Special call： super.foo() / x.<init>() / this.privateFoo()
   • Virtual call：x.foo()

复杂的内存访问可以通过引入临时变量，转化为三地址代码：

x.f.g.h = y;
// 转化为
t1 = x.f;
t2 = t1.g;
t2.h = y;

---

参考

软件分析笔记4：指针分析