视频： 南京大学《软件分析》课程07（Interprocedural Analysis 课程主页：Static Program Analysis | Tai-e (pascal-lab.net) 笔记参考：(34条消息) 【课程笔记】南大软件分析课程—16课时完整版_bsauce的博客-CSDN博客_南京大学软件分析 软件分析（七）Inter-procedural Analysis - 知乎 (zhihu.com) 软件分析 - 知乎 (zhihu.com) PPT： Interprocedural Analysis (nju.edu.cn)
1.Motivation
1. 1为什么需要过程间分析（Interprocedural Analysis）
我们之前学习的是过程内分析（Interprocedural Analysis），过程内分析聚焦于函数内部，对于函数间的调用采取的策略是最保守（安全）的假设，但是安全性高伴随的就是精确度低，如下图，过程内分析就会将变量 x，y，n 设置为 NAC
但是过程间分析增加了 call 和 return 边，这样可以将不同函数的数据流信息通过边来传输，如下图所示，x，y，n 分别为 42， 43， 10
想要进行过程间分析，那么我们就需要调用图（call graph）
1. 2调用图
调用图就是程序中调用关系的表示，本质是调用边的集合，从调用点（call-sites）到目标函数（target methods / callees）的边
应用：是所有过程间分析（跨函数分析）的基础，对于程序优化，程序理解，程序调试等有很重要的作用。
1. 3针对面向对象程序设计语言 (OOPLs) 的调用图构造
主要有如下几种构建算法，从上往下精度变高，速度变慢。主要聚焦于第一个和最后一个算法
1.4Java 的调用分类
- OO 语言的调用图构建的关键（难点）所在就是虚拟调用，因为它的目标函数有多个，并且需要在运行时才能确定。
1.5Method Dispatch of Virtual Calls
因为在运行中，一个虚拟函数的 resolved（意思就是把这个虚拟调用“解”为目标函数）基于两点：receiver objects 的类型和调用方法的签名（signature）。
O 是 receiver，foo 是方法签名
Signature 是方法的一个标识：
- Signature = class type（类） + method name（方法名字） + descriptor
- Descriptor = return type（返回类型） + parameter types（参数类型）
如下图的例子，表示了类 C 中的方法 foo 的 signature（旁边是简写方法）
接下来介绍求解目标函数的方法 dispatch (c, m) ，c 表示 reciever object，m 表示函数签名
如上图所示，当 c 对应的类中的非抽象方法（m‘）（非抽象方法是指实际可执行的函数主体）与 m 具有相同的名字和 descriptor，返回 m‘，否则递归执行 dispatch（c‘，m），c’是 c 的父类。
实例：
2.Class Hierarchy Analysis (CHA) 类层级分析
前提：需要整个程序的类层次结构信息 (继承结构)
原理：假设接收变量 a 可以指向类 a 的对象或 a 的所有子类，通过查找类 A 的类层次结构来解析目标方法
算法：
- cs 就是 call site
- 对于静态调用，直接返回函数签名 m，目标函数就是该类中的静态函数
- 对于特殊调用，取得函数签名的类型，递归调用 dispatch 方法
- 对于私有函数和构造函数，它们就在当前类中，dispatch 返回的就是 m
- 父类函数就需要递归去父类找目标函数
- 对于虚拟调用，首先取得 cs 的变量的声明类，然后在该类本身和该类的子类中递归解析目标函数
示例：
- C 的声明类型是 C，没有子类，所以解析目标函数只会在 C 类中找
- 同理，A 的声明类型是 A，有子类 B，C ，D，所以都要去找
- B 的声明类型是 B，首先找 B 本身，但是 B 本身没有函数，根据 dispatch 方法需要去它的父类去找，然后找 B 的子类
那么如果 b 示例化了呢。
CHA 算法仍然会把 C.foo 和 D.foo 解析到，但是实际上因为 b 已经实例化，所以这两个函数根本不会用，这是 CHA 的弊端。
2.1CHA 的特点
CHA 优点是速度快，只考虑声明类型，忽略数据流和控制流；缺点是准确度低。 本类中有同名函数就在本类和子类找，没有就从父类找，接着找父类的子类中的同名函数（CHA 分析）。 CHA 在 IDE 中用的比较多
2.2利用 CHA 构造调用图
基本思想就是遍历每个函数中的每个调用指令，调用CHA的Resolve()找到对应的目标函数和调用边，函数+调用边=调用图。
- WL 是待解析的方法
- CG 是调用图，调用边的集合
- RM 可达方法的集合（就是已经解析过的方法，避免重复解析）
老师在这里讲了一个建图的例子，建议看视频走一遍
3. 过程间的控制流图 Interprocedural Control-Flow Graph
- CFG 表示单个方法的结构，ICFG 表示整个程序的结构
- 程序的 ICFG 由方法的 CFG 组成，不同程序的 CFG 通过调用边和返回边互联，组成了 ICFG
- 调用边 call edges：从调用点到被调用者的入口节点
- 返回边 return edges：从调用的出口节点到从被调用者的出口节点到其调用点 (即返回点) 后面的语句。
实例：
4. 过程间数据流分析 Interprocedural Data-Flow Analysis
过程间分析和过程内分析的区别
- Call edge transfer：将数据流从调用站点传输到被调用方的入口节点 (沿调用边)（传输参数值）
- Return edge transfer：将数据流从被调用方的出口节点传输到返回站点 (沿返回边)（传输返回值）
- Node transfer：和过程内常量传播是一样的，对每个调用点，将等号左边部分 kill 掉。（意思就是该结点的 out 要把在 in 中把结点内的左边变量去掉，为啥呢，左边变量的值交给返回边来生成）
示例
- 注意图中有两条 call-to-return 边，这个边是不能省去的，因为这种类型的边负责了本地数据的流动，比如说那个 a 和 c 没有参与函数的调用，那么它俩就顺着这个边流到了下一个结点，而无需也去 ten 方法里面绕一圈，提高分析的效率。
- 最后两个结点也解释了为啥要 kill 掉 LHS (left hand side 等号左边的值)，如果不 kill 掉 b，那么最后一个结点的 b 将会有两个输入 7 和 10，那么分析结果 b 就是一个非常量 NAC 了。