P7
2021-04-28 14:55:25 4 举报AI智能生成
南大软件分析P7
作者其他创作
大纲/内容
Motivation
Constant Propagation（常量传播）
到目前为止，我们学到的所有分析都是过程内的。那么，如何处理方法调用？
为方法调用做出最保守的假设，以实现逼近安全。
不精确的来源
x = NAC, y = NAC
n = NAC
为了获得更高的精度，我们需要进行过程间分析：沿着过程间控制流边缘（即调用和返回边缘）传播数据流信息
添加了调用边和返回边后
要进行过程间分析，我们就需要调用图
Call Graph Construction (CHA)
Call Graph（调用图）
程序中调用关系的表示
本质上，调用图是从调用点到其目标方法（被调用点）的一组调用边。
一个例子
CG图的应用
所有过程间分析的基础
程序优化
程序理解
程序调试
程序测试
CG图是非常重要的程序信息
OOPLs（面向对象的程序设计语言）的CG图构造（特别针对Java）
Class hierarchy analysis (CHA)//类层次分析
Rapid type analysis (RTA)//快速类型分析
Variable type analysis (VTA)//变量类型分析
Pointer analysis (k-CFA)//指向分析
比较
南大软件分析主要讲CHA和k-CFA，本节讲CHA，后面会讲k-CFA。
Java中的方法调用（调用方式）
Virtual call是OOPLs调用图构造的关键
虚拟调用的方法分派
在运行时，虚拟调用将根据以下条件进行解析：
1.接收者对象的类型（由o指向）：c
2.调用点的方法签名：m
在本节中，签名充当方法的标识符
签名=类类型+方法名称+描述符
描述符=返回类型+参数类型
我们定义函数Dispatch(c,m)，来模拟运行时方法分派的过程
疑问：c'应该是c的子类吧？
如果 𝑐 包含与 𝑚 具有相同名称和描述符的非抽象方法𝑚’，则Dispatch(c,m) = m'
方法分派的一个例子
疑问：这个例子用来解释虚拟调用的方法分派？
Class Hierarchy Analysis（CHA）//类层次分析
需要整个程序的类层次结构信息（继承结构）
根据调用点的接收变量的声明类型来解析虚拟调用
假设接收变量a可以指向A类的对象或A的所有子类
通过查找类A的类层次结构来解析目标方法
CHA的调用解析
我们定义函数Resolve(𝑐𝑠) 以通过CHA解析调用点的可能目标方法
静态调用的例子
special调用的例子
special调用包括：（1）私有实例方法、（2）构造方法、（3）父类实例方法
虚拟调用的例子
算法中虚拟调用中的子类包括 c 的所有直接和间接子类
一个例子
疑问
CHA的特点
优点（快）
仅考虑在调用点处声明的接收变量的类型及其继承层次结构
忽略数据和控制流信息
缺点（不精确）
容易引入虚假目标方法
CHA在IDE中也有使用
CHA在IDEA中的使用
CG图的构造
通过CHA建立整个程序的CG图
（1）从入口点方法开始（主要针对main方法）
（2）对于每个可达方法 𝑚，通过CHA（Resolve（𝑐𝑠））为 𝑐𝑠 中的每个调用点解析目标方法。
（3）重复直到没有新的方法被发现。
示意图
算法
一个例子
Interprocedural Control-Flow Graph
一些定义
CFG
CFG代表单个方法的结构
ICFG
ICFG代表整个程序的结构
使用ICFG，我们可以执行过程间分析
程序的ICFG由程序中方法的CFG以及两种附加的边组成
Call edges
从调用方法到被调用方法的入口节点
Return edges
从被调用方法的返回语句到其调用方法之后的语句（即返回点）
ICFG = CFGs + call & return edges
call & return edges 的信息来自CG图
疑问：CG图和控制流图的关系？
ICFG的一个例子
Interprocedural Data-Flow Analysis
引入
使用基于过程间控制流图（ICFG）的方法调用来分析整个程序
Edge transfer（边传递）
调用边传递：将数据流从调用点传递到被调用点的入口节点（沿着调用边）
返回边传递：将数据流从被调用点的返回节点传递到返回点（沿着返回边）
Interprocedural Constant Propagation（过程间常量传播）
调用边传递
传递参数值
返回边传递
传递返回值
节点传递
与过程内常量传播相同，再加上：
对于每个调用点，请杀死LHS变量的数据流值。 它的值将沿着返回边流向返回点。
疑问：LHS是啥？
赋值操作的左侧
一个过程间常量传播的例子（包括几个注意点）
call-to-return edge的作用
kill掉LHS变量的结果
没有kill掉LHS变量的结果（会造成结果的不精确）
过程内和过程间常量传播的比较
过程间常量传播比过程内常量传播更精确
0 条评论
下一页
