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(指针影响语句)
通过引入临时变量,将复杂的内存访问转换为三地址代码