Introduction to Pointer Analysis
指向分析说明
指向分析是基础的静态分析
计算指针可以指向的存储位置
对于面向对象的程序（主要针对Java）
计算指针（变量或字段）可以指向哪些对象
被视为<b>may-analysis</b>
计算指针可以指向的一组对象的<b>over-approximation</b>，即，“指针<b>可能</b>会指向哪些对象？”
指向分析是具有40多年历史的研究领域
在今天仍然是一个活跃的领域
Pointer Analysis 和 Alias Analysis（别名分析的比较）
它们是两个密切相关但又不同的概念
指向分析：指针可以指向哪些对象？
别名分析：两个指针可以指向同一个对象吗？
如果两个指针（分别为p和q）指向同一个对象，则p和q是别名。
别名信息可以从指向关系（points-to relations）获得。
指向分析的应用
指针分析是最基本的静态程序分析之一，几乎所有其他分析都是基于此进行的。
Key Factors of Pointer Analysis
引入
指向分析是一个复杂的系统。
多种因素会影响系统的<b>精度</b>和<b>效率</b>。
上下文敏感
如何为调用的上下文建模？
上下文敏感
上下文非敏感
Heap Abstraction（How to model heap memory?）
在动态执行中，由于循环和递归，堆对象的数量可以不受限制
为了确保终止，堆抽象模型将动态分配的，无边界的具体对象（unbounded concrete objects）作为有限抽象对象（finite abstract objects）进行静态分析。
图2.堆内存可以建模为无存储，基于存储或混合的。 这些模型使用分配位点，k限制，模式，变量，其他通用工具谓词或高阶逻辑进行了总结。
Allocation-Site Abstraction（分配点抽象）
最常用的堆抽象
通过分配点对具体对象进行建模
每个分配点对应一个抽象对象，代表其所有分配的具体对象
程序中分配点（allocation sites）的数量是有界的，因此抽象对象（ abstract objects）一定是有限的。
Context Sensitivity（How to model calling contexts?）
上下文敏感
区分方法的不同调用上下文
多次分析每种方法，每种情况分析一次
上下文敏感分析是非常有用的技术，大大提高了分析的精度，在以后的课程中会有更多介绍。这里先会介绍上下文非敏感分析。
Flow Sensitivity（How to model control flow?）
流敏感
遵守语句的执行顺序
在每个程序位置维护指向关系图（map of points-to relations）
流非敏感
忽略控制流顺序，将程序视为一组无序语句
维护整个程序的一张指向关系图
到目前为止，我们了解到的所有数据流分析都是对流敏感的
本课程会采用非流敏感
Analysis Scope（Which parts of program should be analyzed?）
整个程序
计算程序中所有指针的指向信息
为所有可能的客户提供信息
需求驱动
仅计算可能影响特定的需要（按需）的指针的指向信息
提供特定客户的信息
本课程会采用whole-program
Concerned Statements
我们要分析什么？
现代语言通常有多种语句（statements）
• if-else<br>• switch-case<br>• for/while/do-while<br>• break/continue<br>• …
这些语句不直接影响指针，<br>在指针分析中被忽略。
我们只关注影响指针的语句（<b>Pointer-Affecting Statements</b>）
Java中的指针
数组元素（Array element）
array[i]
<b>忽略索引</b>。 建模为具有单个字段（例如arr）的对象（由数组指向），该字段可能指向数组中存储的任何值
Pointer-Affecting Statements（指针影响语句）
通过引入临时变量，将复杂的内存访问转换为三地址代码
