前言

从这节课开始，谭添老师主讲。前半部分，我们主要学习了单一过程内的数据流分析理论及应用。在前面知识的基础上，这节课将介绍如何进行过程间分析（interprocedural analysis）。

以之前我们研究过的常量传播为例，在没有引入过程间分析时，所有参数传递和返回值信息都无法传播，从而导致不精确的结果。过程间分析用call edge和return edge将不同的过程内控制流图关联起来，从而提高准确性，并进一步生成整个程序的控制流图。

本节课的知识点有三个：调用图构建、过程间控制流图和过程间数据流分析。

Call Graph Construction (CHA)

首先，我们需要了解调用图（call graph），它用于表示一个程序中的调用关系，是一个从call-sites到目标方法（callee）的有向边构成的集合。

调用图是程序分析中的非常重要的概念，有着非常广泛的应用。本课专注于以Java为代表的面向对象语言（OOPL）的调用图构建。

常见的调用图构建方法有以下四种：

  • Class hierarchy analysis (CHA)
  • Rapid type analysis (RTA)
  • Variable type analysis (VTA)
  • Pointer analysis (k-CFA)

在上述列表中，从上往下，精确度逐渐提升；从下往上，效率逐渐提升。本课将覆盖第一个class hierarchy analysis（本节）和最后一个pointer analysis（接下来若干节）。

在Java语言中，方法调用通常有三种：

Static call Special call Virtual call
Instruction invokestatic invokespecial invokeinterface
Receiver objects ✗ ✓ ✓
Target methods Static methods
  • Constructors
  • Private instance methods
  • Superclass instance methods
 Other instance methods
#Target methods 1 1 ≥ 1
Determinacy Compile-time Compile-time Run-time

从上图可以看出，static call和special call对应的目标方法都只有一个，而virtual call的目标方法可能会有多个，这正是OOPL多态性（polymorphism）的体现。因此，调用图构建的重点在于分析virtual call。具体来说，我们要解决virtual call的method dispatch问题。

在运行时，virtual call（如o.foo(...)）基于以下两点进行解析：receiver object的类型（如o的类型）和call site处的方法签名（method signature，如foo(...)）。对于如下方法foo，它的签名为<C: T foo(P, Q, R)>，简写为C.foo(P,P,R)：

class C {
	T foo(P p, Q q, R r) { ... }
}

分解一下，可得到：

  • Signature = class type + method name + descriptor
  • Descriptor = return type + parameter types

在此基础上，我们定义函数$Dispatch(c, m)$来模拟运行时method dispatch的步骤： $$ Dispatch(c, m) = \begin{cases} m^{’} &\text{if c contains m’} \\ Dispatch(c^{’}, m) &\text{otherwise} \end{cases} $$

其中，$m’$是$c$中的一个非抽象方法，拥有与$m$相同的name和descriptor；$c’$是$c$的父类。

在以上定义的基础上，我们来看Class Hierarchy Analysis（CHA）算法。该算法于1995年在以Jeffrey Dean为第一作者的论文中首次提出。该算法需要整个程序的类继承关系信息作为输入，基于receiver变量的声明类型来确定给定call site处的virtual call。假设receiver变量a可能指向class A或A的所有子类的某个对象示例，该算法将通过分析class A的class hierarchy来找到call site调用的目标方法。

算法伪代码描述如下：

image-20230325181301226

这个算法比较简单。其中需要注意的是，对于special call的情况，那么算法将调用$Dispatch$去求解，而非直接返回父类的方法，这是因为父类的方法也可能是继承自它的父类。另外，对于virtual call的情况，考虑到多态，需要遍历所有子类，并把符合条件的子类中的方法都加入到结果中。

这个算法不考虑实际值，只考虑“声明类型”，因此存在一定误报。例如，在下图中的Bb = new B();处，其实new B()已经限制了对象一定是class B的示例，但CHA算法依然会将子类考虑进来（好处在于效率高）：

image-20230325181940486

在CHA的基础上，我们给出调用图构建思路：从entry方法（main方法）出发，对于每个可到达的方法$m$，为$m$内部的所有call site通过CHA解析它的目标方法（$Resolve(cs)$），重复这一过程直到没有任何新方法出现。

我们用伪代码描述这一算法流程：

image-20230325182726989

可以看出，这个算法的求解思路正是我们在《南大软件分析课程笔记｜06 数据流分析理论》中学到的Worklist方式。

这个算法比较简单，这里直接附上谭添老师课上给出的一个例子：

image-20230326102011813

这节课上的代码比较窄长，示意图也不太好用Mermaid直接画，所以我就直接把课件中的关键部分截图放上来了 :-)

Interprocedural Control-Flow Graph

OK，学完了如何构建调用图，我们来研究一下如何构建过程间控制流图（ICFG）——基于此，我们就可以进一步开展过程间分析了。

事实上，一个程序的ICFG包括程序中所有方法的CFG加上两类额外的有向边：

  1. Call edges，即从call sites到被调用方法（callee）的entry nodes。
  2. Return edges，即从callee的exit nodes到caller的call sites后面紧跟着的语句（return sites）。

以上两点很好理解，与汇编层面的控制流转移特点一致。另外，这两类边正是基于上一节的调用图生成的。

这里附上一个谭添老师展示的ICFG示例：

image-20230326103028388

其中，值得注意的是call-to-return边。尽管看上去call edges和return edges能够把call sites的语句和紧邻语句连接起来，但是我们仍然要保留call-to-return这条边，因为同一方法内部的上下文信息（如本地变量等）需要借助这条边传递——毕竟，call/return edges不会传递这些局部信息。

Interprocedural Data-Flow Analysis

这节课的内容确实很好理解。接下来，我们就来研究一下本文的主题——过程间数据流分析！

过程间数据流分析并不是一种具体的应用，只是把我们原来针对单一过程的分析应用扩展到整个程序的所有过程上。过程内分析和过程间分析的区别如下：

Intraprocedural Interprocedural
Program representation CFG ICFG = CFGs + call/return edges
Transfer functions Node transfer Node transfer + edge transfer

所谓edge transfer，包含normal edge transfer、call-to-return edge transfer、call edge transfer和return edge transfer。Call-to-return transfer传递的是方法局部值并kill掉LHS变量（left-hand side），call edge transfer传递的是实参值，return edge transfer传递的是返回值。

另外，node transfer在两种分析中也有一些差异。以常量传播为例，过程内分析的情况下，我们遇到类似b = addOne(a)这样的call site时，直接将表达式左侧的变量b（即LHS变量）赋值为NAC；然而在过程间分析时，LHS留待return edge transfer来处理。

下面是一个常量传播在过程内分析和过程间分析两种情况下的对比案例：

Xnip2023-03-26_11-38-28

可以看出，过程间分析比过程内分析要精确很多。

总结与思考

本节课我们主要学习了调用图构建、过程间控制流图和过程间数据流分析。谭添老师和李樾老师的一个共同的优点是，在课件中用例子将抽象的算法一步步运行的过程展示出来，大大降低了理解难度。

下节课开始，我们将学习指针分析。Los geht’s!