指针分析 Pointer Analysis¶
作者: 杨广亮
更新日期: 2026-01-06
版权声明: 本文档遵循 CC BY-NC-SA 4.0 协议
指针分析（Pointer Analysis），也叫指向关系分析（Points-to Analysis），是用来分析程序中指针变量所指向的内存对象的技术。
从程序分析总体流程来讲，指针分析并不是必须的。从抽象语法树AST到中间表示IR，再到控制流图CFG和全局控制流图ICFG，以及跨函数数据流分析，这些步骤在没有指针分析的情况下也可以完成。再加上，指针分析的难度极大，实现复杂度极高，最终导致很多程序分析框架选择不实现指针分析。
尽管如此，在很多复杂重要问题场景中，指针分析是解决这些问题的关键：
- 别名问题（Aliasing）：当两个指针指向同一内存时，通过一个指针对内存进行的修改，会影响另一个指针的内存读取。仅仅通过数据流分析往往很难解决别名问题，别名问题会造成数据流传播中的漏报错误。指向关系分析则是解决别名问题的利器，可以检测出两个指针变量指向内容是否一致。当然，这里关于指针的别名问题，也同样适用于对象引用。
- 函数调用图生成问题（Call Graph Generation）：函数调用图CG是很多全局性程序分析的基础，例如跨函数控制流和跨函数数据流分析。有的工具通过类型系统和类层级关系等构建CG，但是由于高阶函数（Higher-order function，即能接受其他函数作为参数、将函数作为返回值的函数）等复杂代码的存在，导致CG不够完整或存在大量错误。指针分析可以从函数名变量指向的内存对象中提取类型信息，从而生成更精确的调用图。
- 内存安全分析（Memory Safety）：指针分析可以帮助检测内存安全漏洞，如空指针解引用、悬空指针、内存泄漏等。
指针分析是极具挑战性的，是NP-hard问题（参见Pointer-induced aliasing: a problem taxonomy, 1991），可以说是整个程序分析领域的“皇冠”。从指针分析算法的历史也能略窥其复杂性。数据流分析的Gen/Kill算法在上世纪70年代就已经被提出，并得到广泛应用。与此同时，指针算法则一直缺乏，直到1994年，Andersen在其博士论文"Program Analysis and Specialization for the C Programming Language"中提出了基于集合约束的指针分析算法，才为现代指针分析奠定基础。Andersen算法至今仍是当代指针分析的主流方法之一，几乎所有现代指针分析工具都基于它或其变体实现。
本章将详细介绍指针分析的基本概念、经典的Andersen算法、分析精度指标，以及算法的改进和实际应用。
1. 基本概念¶
1.1 指针与指向关系¶
在程序中，指针（Pointer）或引用（Reference）是一种特殊的变量，它存储的是被指向内存或对象的地址，而不是普通的数值。通过指针或引用，程序可以间接访问和操作内存中的数据。指向关系（Points-to）描述了指针变量与其可能指向的内存对象之间的关系。
我们用符号 p → o 表示指针变量p可能指向内存对象o，同时，使用指向集合 pts（Points-to set）表示指针变量p可能指向的所有对象，即pts(p) = {o}。
以下面的c代码演示指向关系及其影响：
[01] int x = 10;
[02] int* p = &x;
[03] *p = 20;
在这个例子中，[02]指令将p指向x，即p → x。这种指向关系在[03]指令中发挥作用，该指令修改了p指向的内存对象，使其变更为20。虽然[03]指令中没有涉及到x，但是其本质上还是对x进行修改。这里分析的关键就在于理清p和x之间的指向关系。
1.2 别名问题¶
别名（Aliasing）是指两个或多个不同的指针变量指向或者引用同一个内存位置。别名是指向关系的一种延伸，在现实编程中广泛存在，也给程序分析带来挑战。
将上述例子稍作修改来说明别名问题及其影响：
[01] int x = 10;
[02] int* p = &x;
[03] int* q = p;
[04] *q = 20;
在这个例子中，指令[03]使得指针p和q是别名关系，它们同时都指向x内存位置。因此，当[04]指令执行时，x的值还是被修改为20。同理，在[03]和[04]也没有存在x，但是最终结果是x的内存内容被修改了。如果只是简单分析数据流，就难以理解程序对x的修改。
1.3 函数调用¶
函数是程序分析的基本单元，对函数调用的处理直接决定了跨函数处理的质量。按照函数解析直接程度，可以分类为：
- 直接调用（Direct call）：调用者caller直接调用被调用函数callee。
- 间接调用（Indirect call）：调用者callee通过指针变量来调用被调用函数callee。
[00] void foo() {}
......
[01] void (*fp)();
[02] fp = foo;
[03] fp();
[04] foo();
以上述代码为例，[04]指令中的函数调用foo函数属于直接调用，不依赖于任何额外的指针变量。而[03]指令则通过指针变量fp调用foo函数。如果是基于编译器（例如Clang/LLVM），编译器会规范[03]处函数调用的格式（即函数签名 Signature：包含参数和返回值的类型），函数签名可以帮助找到callee。但是，如果是基于源码分析，就需要通过指针分析[03]指令中fp指向关系：fp → foo，得到callee是foo函数。
在面向对象编程语言中，函数调用的格式往往是receiver.method()，其中receiver是调用者所属的对象，method是函数名。同理地，如果是基于编译器（例如Java或Dalvik字节码）的分析，也可以通过函数签名来确定callee。但是，如果是基于源码分析，则需要通过指针分析得到receiver引用的具体的对象，从对象中检索method函数名，从而定位到callee。
1.4 堆对象抽象¶
堆对象（Heap object）是动态分配的内存单元，它是运行时在“堆（heap）”内存区域中创建的。堆对象是指针分析中最核心的部分。但是在实际例子中，堆对象可能被创建非常多，导致程序分析的效率会下降。因此，需要对堆对象进行抽象合并。
[01] for (int i = 0; i < n; i++) {
[02] *p = malloc(sizeof(int));
[03] ...
[04] }
以上述代码为例，在[02]处，指针变量p指向一个堆内存对象。如果每次循环都创建一个内存对象，那么在[04]处，指针变量p可能指向多个对象，使得程序分析变得非常困难。
通常需要对堆对象进行抽象（Abstraction）或者说合并。常见的抽象策略包括：
-
类型抽象（Type-based Abstraction）：将所有相同类型的堆对象抽象为一个，这种抽象更加粗粒度，精度较低，但相应的分析效率也更高。
-
分配点抽象（Allocation-site Abstraction）：将同一个内存分配指令创建的所有堆内存对象都抽象为一个抽象对象。在上述例子上，尽管循环可能执行多次，创建多个不同的内存对象，但在分配点抽象下，可以将这些堆内存对象都抽象为一个对象，记为
object_L02（即[02]处创建的抽象对象）。 -
上下文敏感抽象（Context-sensitive Abstraction）：在分配点抽象的基础上，进一步区分不同调用上下文下创建的对象，这可以提高精度，但也增加了分析复杂度。
分配点抽象是一种非常常见的内存对象抽象策略，在本节指针分析算法中，主要基于分配点抽象。
2. Andersen算法¶
Andersen算法是指针分析中最经典的算法之一。它将指向关系分析转换为集合约束求解问题，也被称为基于集合包含约束的分析（Inclusion-based Analysis），或者基于子集的分析（Subset-based Analysis）。
Andersen算法的主要思路是，为每个指针变量维护指向集合 pts（Points-to Set），用来表示该指针可能指向的所有对象，然后根据程序指令生成对应的约束条件（Constraints），最终通过迭代汇总和求解这些约束，来计算指向关系结果。
2.1 约束生成规则¶
Andersen算法的关键在于对指向集合pts约束的生成和收集，下面的表格总结了各个指令的指向关系约束的生成规则：
| 指令类型 | 指令 | 生成的约束 | 含义 |
|---|---|---|---|
| 内存分配 | x = malloc() |
{object_stmt} ⊆ pts(x) |
新分配的抽象对象object_stmt包含在x的指向集合中 |
| 赋值指令 | x = y |
pts(y) ⊆ pts(x) |
指针y的指向集合在x的指向集合中 |
| 地址取值 | x = &y |
{y} ⊆ pts(x) |
y内存对象在x的指向集合中 |
| 指针存储 | *x = y |
∀o ∈ pts(x): pts(y) ⊆ pts(o) |
对于x指向的每个对象o，y的指向集包含在o的指向集合中 |
| 指针加载 | x = *y |
∀o ∈ pts(y): pts(o) ⊆ pts(x) |
对于y指向的每个对象o，o的指向集包含在x的指向集合中 |
其中函数调用指令x=method(args)，如果method是用于间接调用的函数指针，那么其指向关系约束为：
∀o ∈ pts(method):
// 根据变量method的指向集找到被调用函数callee
callee = dispatch(o)
// 对齐函数调用实参args和callee函数声明的形参parameters的指向集
pts(args_i) ⊆ pts(callee.parameters_i)
// 设置返回值的指向集
pts(callee.return) ⊆ pts(x)
从上述表格中，可以看到Andersen算法采用的一种保证soundness的保守策略，因此每一次规则都是在收集指向集合包含关系，即但凡有一个指向关系，那么该关系就一定会被收集。
2.2 Andersen指针分析¶
基于上述针对指向集合包含关系约束的思路，设计基于Worklist通过不动点迭代求解约束的分析方法。函数内Andersen指针分析具体算法流程如下：
算法： Andersen指针分析pointer_analysis()
输入： IR代码，入口函数 main
输出： 全程序每个指针的指向集合 pts
1. 全局初始化:
// 初始化指向集合
pts = ∅
// 初始化Worklist
Worklist = ∅
// 初始化已被访问过的函数
VisitedMethods = ∅
2. 增加辅助函数：扫描函数scan_method()
function scan_method(method):
if method ∉ VisitedMethods:
VisitedMethods.add(method)
// 将函数体内的所有语句生成约束加入 Worklist
for stmt in method.body:
constraint = generate_constraint(stmt)
Worklist.push(constraint)
3. 添加入口函数:
// 初始化入口函数
scan_method(main)
4. 迭代求解:
while Worklist ≠ ∅:
constraint = Worklist.pop()
// 处理约束
case constraint of:
// [情况 1] 内存分配: x = malloc()
{o} ⊆ pts(x):
if {o} ⊄ pts(x):
pts(x) = pts(x) ∪ {o}
// 把受x影响的约束添加到Worklist中
add_dependent_constraints(x, Worklist)
// [情况 2] 赋值指令: x = y
pts(y) ⊆ pts(x):
diff = pts(y) - pts(x)
if diff ≠ ∅:
pts(x) = pts(x) ∪ diff
// 把受x影响的约束添加到Worklist中
add_dependent_constraints(x, Worklist)
// [情况 3] 地址取值: x = &y
{y} ⊆ pts(x):
if y ∉ pts(x):
pts(x) = pts(x) ∪ {y}
// 把受x影响的约束添加到Worklist中
add_dependent_constraints(x, Worklist)
// [情况 4] 指针存储: *x = y
∀o ∈ pts(x) pts(y) ⊆ pts(o):
diff = pts(y) - pts(o)
if diff ≠ ∅:
pts(o) = pts(o) ∪ pts(y)
// 把受o影响的约束添加到Worklist中
add_constraint_to_worklist(o, Worklist)
// [情况 5] 指针加载: x = *y
∀o ∈ pts(y), pts(o) ⊆ pts(x):
diff = pts(o) - pts(x)
if diff ≠ ∅:
pts(x) = pts(x) ∪ pts(o)
// 把受x影响的约束添加到Worklist中
add_constraint_to_worklist(x, Worklist)
// [情况 6] 函数调用: x = method(args)
∀callee ∈ pts(method):
// 确保 callee 函数体被扫描
scan_method(callee)
// 参数传递 (实参 -> 形参)
for i in 0..len(args):
new_constraint = pts(args[i]) ⊆ pts(callee.params[i])
Worklist.push(new_constraint)
// 3. 返回值传递
if x exists:
new_constraint = pts(callee.return_var) ⊆ pts(x)
Worklist.push(new_constraint)
5. 返回 pts
Andersen指针分析通过维护指针到抽象对象集合的单调增长关系，将程序中的指向关系建模为一组集合包含约束。由于所有约束均为单调函数，整个分析过程必然在有限步内收敛到不动点，从而保证算法终止。该算法采用May analysis的保守策略，任何可能存在的指向关系都会被纳入结果，因此分析结果是sound。
在Andersen指针分析算法中，有几个实现的难点需要注意：
- 如何存储pts指向集合？ 指向集合需要存储对象，同时需要与其他对象集合取并集、甚至差集，如何设计高效的数据结构来存储对象集合变成一个问题。
- 如何存储constraints？ 约束并不是一种结构化的数据，表达好指向关系并不是很容易。
- 如何找到受影响的约束添加到Worklist？ 给定一个pts指向集合，可能需要遍历所有的约束关系，才能找到受影响的约束，然后添加到Worklist中，整个过程效率很差。
对于问题1，可以使用Bit Vector来存储对象集合，并集和差集等操作被转换成两个整数的位运算，极为高效。对于问题2和问题3，指针赋值图 PAG(Pointer Assignment Graph)的提出和应用，大大提高了算法可行性。
3. 基于PAG的Andersen算法¶
在实际实现Andersen算法时，直接处理约束集合会面临诸多效率问题。指针赋值图 PAG(Pointer Assignment Graph)很好地解决了该问题,最早在Java分析框架Soot的SPARK指针分析模块中提出和实现(参见Scaling Java Points-to Analysis using SPARK, 2003)。通过PAG就可传播指向集合，因此，PAG将约束求解问题转换为图可达性问题。
3.1 PAG构造¶
PAG最早是针对Java字节码构造的。其中，PAG节点是对指针变量和内存对象抽象,而PAG的边是对指向关系的约束抽象。
PAG的节点可以是以下几种类型：
- 变量节点(VarNode): 代表程序中的指针变量
- 分配节点(AllocNode): 代表内存分配点抽象出的对象
- 字段引用节点(FieldRefNode): 代表对象的字段
PAG的边可以是以下几种类型:
| 类型 | 对应语句 | 生成的约束 | 含义 | PAG边 | 边类型 |
|---|---|---|---|---|---|
| 内存分配 | x = new T | {object_stmt} ⊆ pts(x) | x指向新分配对象 | AllocNode → VarNode(x) | New(object_stmt, x) |
| 指针赋值 | x = y | pts(y) ⊆ pts(x) | 指向集从y传播到x | VarNode(y) → VarNode(x) | Assign(y, x) |
| 字段存储 | x.f = y | ∀o ∈ pts(x): pts(y) ⊆ pts(o.f) | 通过x的指向对象,将y传播到字段f | VarNode(y) → FieldRefNode(o.f) | Store(y, x.f) |
| 字段加载 | x = y.f | ∀o ∈ pts(y): pts(o.f) ⊆ pts(x) | 从y指向对象的字段f传播到x | FieldRefNode(o.f) → VarNode(x) | Load(y.f, x) |
其中函数调用指令x=receiver.method(args)，那么其指向关系约束为：
∀o ∈ pts(receiver):
// 根据变量receiver的指向集找到被调用函数callee
callee = dispatch(o.type, method)
// 如果是虚函数，那么需要设置this参数
pts(receiver) ⊆ pts(this)
// 对齐函数调用实参args和callee函数声明的形参parameters的指向集
pts(args_i) ⊆ pts(callee.parameters_i)
// 设置返回值的指向集
pts(callee.return) ⊆ pts(x)
3.2 基于PAG的Andersen算法实现¶
基于PAG，将Andersen指针分析转换为基于图的指向集合的传播问题。新的算法包括两部分，一部分是构建PAG，另一部分是使用PAG进行指向集的传播。具体算法流程如下：
算法: 基于PAG的Andersen指针分析
输入: 程序的中间表示IR
输出: 每个指针的指向集合pts
1. 构建初始PAG:
PAG = Graph()
// 初始化指向集合
pts = ∅
// 初始化Worklist
Worklist = ∅
// 初始化已被访问过的函数
VisitedMethods = ∅
// 初始化字段存储
StoreConstraints = ∅
// 初始化字段加载
LoadConstraints = ∅
// 初始化函数调用
CallConstraints = ∅
2. 增加辅助函数：第一次访问函数scan_method()
function scan_method(method):
if method ∉ VisitedMethods:
VisitedMethods.add(method)
for stmt in method.body:
case stmt of:
// 为每个分配点创建New边
x = new T (at line L):
pts(x) = pts(x) ∪ {object_L}
Worklist.push(x)
// 为赋值创建Assign边
x = y:
PAG.add(Assign(y, x))
if pts(y) ≠ ∅:
Worklist.push(y)
// 保存字段访问Store关系
x.f = y:
StoreConstraints.add(x, f, y)
// 保存字段加载Load关系
x = y.f:
LoadConstraints.add(x, y, f)
// 保存函数调用关系
x = receiver.method(args):
CallConstraints.add(x, receiver, method, args)
3. 添加入口函数:
// 初始化入口函数
scan_method(main)
4. 迭代求解:
while Worklist ≠ ∅:
n = Worklist.pop()
// [情况 1] Assign边: m = n
for Assign(n, m) ∈ PAG:
diff = pts(n) - pts(m)
if diff ≠ ∅:
pts(m) = pts(m) ∪ diff
Worklist.push(m)
// [情况 2] Store边: x.f = y
for each (x, f, y) ∈ StoreConstraints where x == n:
for each o ∈ pts(x):
if Assign(y, o.f) ∉ PAG:
PAG.add(Assign(y, o.f))
if pts(y) ≠ ∅:
Worklist.push(y)
// [情况 3] Load边: x = y.f
for each (x, y, f) ∈ LoadConstraints where y == n:
for each o ∈ pts(y):
if Assign(o.f, x) ∉ PAG:
PAG.add(Assign(o.f, x))
if pts(o.f) ≠ ∅:
Worklist.push(o.f)
// [情况 4] 函数调用
for each (x, receiver, method, args) ∈ CallConstraints where receiver == n:
for each o ∈ pts(n):
callee = dispatch(o.type, method)
// 确保 callee 函数体被扫描
scan_method(callee)
// 如果是虚函数，对齐this
PAG.add(Assign(receiver, callee.this))
if pts(receiver) ≠ ∅:
Worklist.push(receiver)
// 参数传递 (实参 -> 形参)
for i in 0..len(args):
PAG.add(Assign(args[i], callee.params[i]))
if pts(args[i]) ≠ ∅:
Worklist.push(args[i])
// 3. 返回值传递
if x exists:
PAG.add(Assign(callee.ret, x))
if pts(callee.ret) ≠ ∅:
Worklist.push(callee.ret)
5. 返回 pts
3.3 示例¶
[01] class Box {
[02] int data;
[03] }
[04]
[05] void main() {
[06] Box b = new Box();
[07] Box p = b;
[08] Box q = b;
[09]
[10] p.data = 10;
[11] int x = q.data;
[12] }
在上述Java代码中，p和q同时引用对象b，因此他们是别名，当p.data被修改，那么q.data也会被修改。
下面展示Andersen指针分析如何解决别名的问题：
第一步: 扫描main函数，更新PAG¶
| 指令 | 操作 | 说明 |
|---|---|---|
[06] b = new Box() |
pts(b) = {object_L06} Worklist.push(b) |
创建分配点内存抽象object_L06 |
[07] p = b |
PAG.add(Assign(b, p)) Worklist.push(b) |
加入赋值边b → p到PAG中 |
[08] q = b |
PAG.add(Assign(b, q)) Worklist.push(b) |
加入赋值边b → q到PAG中 |
[10] p.data = 10 |
StoreConstraints.add(p, data, 10) | 记录Store |
[11] x = q.data |
LoadConstraints.add(x, q, data) | 记录Load |
经过第一步之后，pts的初始状态为:
pts(b) = {object_L06}
得到的PAG为
b
/ \
/ \
assign assign
| |
v v
p q
而Worklist = [b]
第二步: 迭代传播pts¶
2.1: 首先，处理b, pts(b) = {object_L06}
[Assign边] Assign(b, p):
pts(p) = {object_L06}
Worklist.push(p)
[Assign边] Assign(b, q):
pts(q) = {object_L06}
Worklist.push(q)
2.2: 其次，处理 p, pts(p) = {object_L06}
[Store边] 找到 (p, data, 10):
对于 object_L06 ∈ pts(p):
记录: object_L06.data 被修改
2.3: 然后，处理 q, pts(q) = {object_L06}
[Load边] 找到 (x, q, data):
对于 object_L06 ∈ pts(q):
读取: object_L06.data
最后结果¶
pts(b) = {object_L06}
pts(p) = {object_L06}
pts(q) = {object_L06}
通过指针分析,我们发现:
pts(p) ∩ pts(q) = {object_L06} ∩ {object_L06} = {object_L06} ≠ ∅
因此 p 和 q 是别名!
结论¶
- [10]指令
p.data = 10修改了 object_L06.data 为 10 - [11]指令
x = q.data读取了 object_L06.data - 因此 x 的值是 10
通过指针分析，我们成功识别出p和q是别名，指向同一对象，帮助准确追踪数据流: p.data → object_L06.data → q.data。
4. 分析精度¶
Andersen指针分析算法奠定了指针分析的基础。此后各种改进版本不断被提出，其算法也不断被改进和优化，其精度也不断得到提高。改进的方向主要有以下几种：
4.1 上下文敏感（Context Sensitive）和上下文不敏感（Context Insensitive）¶
上下文敏感和上下文不敏感是指对分析过程是否能够对同一个函数在不同调用位置的行为进行区分。
[01] int* identity(int *p) {
[02] return p;
[03] }
[04]
[05] void main(){
[06] int a, b;
[07] int *x = identity(&a); // Call Site 1
[08] int *y = identity(&b); // Call Site 2
[09] }
以上述代码为例，identity函数将输入的指针p作为参数，返回该指针。在运行时，[07]和[08]的函数调用会分别返回指向a和b的指针。
如果是上下文敏感的指针分析算法，那么[07]和[08]的调用结果会不同，会得到不同的结果，即pts(x) = {a}，pts(y) = {b}，因为分析中会为每个调用位置维护独立的分析结果。相反地，如果是上下文不敏感的指针分析算法，那么[07]和[08]的调用结果会相同，即pts(x) = {a, b}，pts(y) = {a, b}，因为[07]和[08]处对identity函数的调用无法区分出来。
为了区分上下文，常见的上下文敏感策略有以下三种：
- 调用点敏感（Call-site Sensitivity）：用调用函数指令的位置来区分上下文。
- 对象敏感（Object Sensitivity）：在receiver.method()函数调用中，通过不同的receiver来区分上下文，特别适合面向对象语言。
- 类型敏感（Type Sensitivity）：用类型信息来区分上下文。
通常限制为k层敏感度，一般来说k=1或k=2。当K过大时，分析成本会急剧增加。
4.2 流敏感（Flow Sensitive）和流不敏感（Flow Insensitive）¶
流敏感性决定了分析是否考虑语句的执行顺序。流不敏感时，会不考虑语句顺序，将所有语句的效果合并。
[01] p = &a;
[02] p = &b;
在上述代码中，如果是流不敏感的指针分析算法，那么[01]和[02]的赋值会合并，得到pts(p) = {a, b}。而如果是流敏感的指针分析算法，那么[01]后得到pts(p) = {a}，[02]指令被执行后，会得到pts(p) = {b}。
4.3 路径敏感（Path Sensitive）和路径不敏感（Path Insensitive）¶
路径敏感性决定了分析是否区分不同的执行路径。如果是路径不敏感，则不区分不同的控制流路径，合并所有可能路径的结果。
[01] int a, b;
[02] int *p;
[03] if (condition) {
[04] p = &a;
[05] } else {
[06] p = &b;
[07] }
[08] *p = 10;
针对上述代码的分析，如果是路径不敏感分析，那么在[08]处就会得到pts(p) = {a, b}，两个分支的赋值结果会合并，那么*p = 10 可能修改a或b。而如果是路径敏感分析，不同的执行路径会得到区分，为每条路径维护独立的分析状态：
路径1: condition为真
pts(p) = {a}
*p = 10 只修改a
路径2: condition为假
pts(p) = {b}
*p = 10 只修改b
5. Andersen算法的改进和应用¶
有了上述精度的认知后，我们可以得到一个结论，即原始的Andersen算法是上下文不敏感、流不敏感、路径不敏感的指针分析算法。
后续的改进版本，主要针对这三方面精度进行了改进，使得指针分析算法更加准确：
5.1 上下文敏感¶
每个函数往往一个入口和多个出口。当进入Callee函数分析以后，往往很容易就忘记了调用者Caller函数的信息了，“不记得来时的路了”，导致不知道要返回到哪个函数。上下文不敏感分析就是“无所谓了”，会把所有的出口函数都考虑进去，来保证soundness，也相应地造成精度下降。
上下文敏感的改进就需要考虑caller的信息了，将所有的堆抽象和变量从一维扩展为二维，即（上下文，元素），这样保留了调用者信息，也使得指针分析更加准确。
5.2 流敏感¶
流敏感的问题的解决往往通过引入SSA（静态单一赋值Static Single Assignment）来解决。
5.3 路径敏感¶
路径敏感问题的解决需要分析分支语句，引入路径条件约束（Path Constraint），结合SAT（Boolean Satisfiability）解析器来解决。
6. Andersen指针分析算法的收敛性¶
Andersen指针分析一定会收敛并终止，其核心原因可以归结为两点：单调性（Monotonicity）和有限性（Finiteness）。
-
指向集合的单调递增性
- Andersen算法是一个指向集不断并集和扩大的过程，只增不减，同时PAG的边一旦建立，绝不会被删除，因此，指向集单调递增。
-
指针分析处理的元素都是有限的：
- 有限的指针变量
- 有限的抽象对象，可以使用“分配点抽象”（Allocation site abstraction）等多种策略进行抽象
- 有限的指向关系，每个指针最多指向所有对象，这个数量是存在上限的
因此，Andersen算法通过在有限的搜索空间内，以单调递增的方式逼近边界，只要程序规模是有限的，它就一定会在有限步内停止。