P8
2021-04-28 14:55:54 3 举报AI智能生成
南大软件分析P8
作者其他创作
大纲/内容
Motivation
CHA和Pointer Analysis的比较
CHA存在的不精确问题
Pointer Analysis能够解决CHA的不精确问题
总结
CHA基于class hierarchy（类层次），会产生虚假调用，导致常量传播的结果不精确。
Pointer Analysis基于points-to relation（指向关系），不会产生虚假调用，常量传播的结果精确。
Introduction to Pointer Analysis
指向分析说明
指向分析是基础的静态分析
计算指针可以指向的存储位置
对于面向对象的程序（主要针对Java）
计算指针（变量或字段）可以指向哪些对象
被视为may-analysis
计算指针可以指向的一组对象的over-approximation，即，“指针可能会指向哪些对象？”
指向分析是具有40多年历史的研究领域
在今天仍然是一个活跃的领域
指向分析的一个例子
Pointer Analysis 和 Alias Analysis（别名分析的比较）
它们是两个密切相关但又不同的概念
指向分析：指针可以指向哪些对象？
别名分析：两个指针可以指向同一个对象吗？
如果两个指针（分别为p和q）指向同一个对象，则p和q是别名。
别名信息可以从指向关系（points-to relations）获得。
指向分析的应用
基本信息
CG图、别名
编译器优化
虚拟调用内联
错误检测
空指针检测
安全性分析
信息流分析
指针分析是最基本的静态程序分析之一，几乎所有其他分析都是基于此进行的。
Key Factors of Pointer Analysis
引入
指向分析是一个复杂的系统。
多种因素会影响系统的精度和效率。
堆抽象
如何为堆内存建模？
分配地点
无存储
上下文敏感
如何为调用的上下文建模？
上下文敏感
上下文非敏感
流敏感
如何对控制流进行建模？
流敏感
流非敏感
分析范围
应该分析程序的哪一部分？
整个程序
需求驱动
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
• switch-case
• for/while/do-while
• break/continue
• …
• switch-case
• for/while/do-while
• break/continue
• …
这些语句不直接影响指针，
在指针分析中被忽略。
在指针分析中被忽略。
我们只关注影响指针的语句（Pointer-Affecting Statements）
Java中的指针
本地变量（Local variable）
x
静态域（Static field）
C.f
有时被称为全局变量
实例域（Instance field）
x.f
建模为具有字段 f 的对象（由x指向）
数组元素（Array element）
array[i]
忽略索引。 建模为具有单个字段（例如arr）的对象（由数组指向），该字段可能指向数组中存储的任何值
Pointer-Affecting Statements（指针影响语句）
New
x = new T()
Assign
x = y
Store
x.f = y
Load
y = x.f
Call
r = x.k(a, …)
通过引入临时变量，将复杂的内存访问转换为三地址代码
0 条评论
下一页
