南大《软件分析》7.0 Interprocedural Analysis

Motivation

顾名思义，过程间分析。在前面的内容中，我们一直关注的是过程内（intraprocedural）的 CFG（control flow gragh）分析，但别忘了，但仅有这些还不能达到我们分析整个程序的目的，因为在真正的程序中，还会存在有大量的方法调用 call method，只有把这些加入到分析框架下，才能够深入对整个程序进行分析。

首先借助一个例子来简单介绍过程内和过程间的分析区别：

上图左边是一个常量传播分析代码片段，可以看到在 foo 函数中有调用 bar 函数，在过程内分析时，通常采用保守策略，即默认函数返回的是一个 NAC（非常量），也就造成了后续计算出来的结果 n 也是 NAC，但实际上通过观察可以发现，bar 函数只是简单的对变量加一然后返回，从而造成结果的不精确。所以过程间分析的出现就解决了这一问题，具体如下：

可以看到过程间分析考虑到了方法调用，并通过调用边（call edges）和返回边（return edges）表示，从而计算得到了一个更精确的结果。

Call Graph Construction (CHA)

调用图的建立，与我们之前的 CFG 类似，这个 CHA 只不过是从 call 的位置建立 call graph。以下就是对一个简单代码片段建立 call graph 的过程。

call graph 的优点：

过程间分析的基础
程序优化
程序理解
程序调试
程序测试
其它…

本课程关注上面加粗的两类 call graph，下面的部分讲述 CHA。

在 java 中存在三种方法调用，分别为 static call，special call，virtual call（不知道这三类方法调用的可以GPT解决），对于 static call 和 special call 这两类方法调用在在编译时就可以明确知道其调用的是具体哪个方法。但是！virtual call 与这两者存在区别，我们都知道一些面向对象语言都有多态这一性质，在运行时动态确定调用具体哪个方法。

由于是静态分析，为了搞清楚 virtual call 具体调用的是哪个方法，我们需要对 virtual call 有一个更深刻的认识。

在运行时，virtual call 的解析是基于对象的类型和具体的调用方法签名，上图给出了签名的表示形式。

这里给出了 Dispatch 算法，这个算法是用来模拟在运行时对于一个方法调用，如何找到其具体位置，当类c包含一个非抽象的同名同描述符的方法时，直接返回结果，否则找到的父类，进入到下一次 Dispatch 的过程，直到最后找到满足条件的，下图是一个 dispatch 计算的例子，对着算法分析就行。

下图给出了 CHA 的必要条件，且 CHA 基于声明类型和变量。

如何理解上图中最后一段话呢，即假设变量 a 指向类 A 或者类 A 的所有子类，这一点在下面的 resolve 函数有所体现：

cs 指 call site，即程序调用点。前面有提到在 java 中 cs 分三类 static call，special call， virtual call，如果 cs 是属于 virtual call 类型，则首先会找到对应 cs 处变量的类型（属于哪一个类），然后用一个for循环遍历当前类和其所有的子类，并调用 Dispatch(c, m)。

上图给出了一个计算 Resolve 具体的例子，

对于 Resolve(a.foo()) = {A.foo(), C.foo(), D.foo()}，可以这样理解，由于 a.foo 对应的是一个 virtual call，所以会进入 Resolve 第三个部分，然后找到 A 和 A 的所有子类，并全部调用 Dispatch，由于 B 并没有重写 foo 函数，故最终结果为 {A.foo(), C.foo(), D.foo()}。

对于Resolve(b.foo()) = {A.foo(), C.foo(), D.foo()}，可以理解为，首先会调用 Dispatch(B, b.foo())，但 B 没有 foo 方法，因此根据 Dispatch 的算法，找到其父类 A，然后返回 A.foo。

CHA 的一些缺点和优点如上所示，CHA 可以拿来在 IDE 中展示类之间的方法调用关系。

有了前面的 CHA 还不够，因为我们要研究的是整个程序的调用图（call graph），具体思想如下：

对于整个程序的 call graph 建立算法如下：

对于其中几个关键变量解释如下：

WL: 这个集合用来保存所有需要被处理的方法，如

CG：所有的调用边集合

RM：所有可到达的方法集合

用具体的例子解释如下：

首先初始状态 WL 不为空，CG 和 RM 为空，然后由于 WL 不为空，会进入 while 循环，将 A.main() 从 WL 中移出，然后添加 A.main 加入到 RM，在找到 A.main 中所有的方法调用 T，然后依次遍历 T 中所有调用的方法，在上图中对应的就是 foo 方法，结果如下：