前言
在前一节课的基础上，我们继续来学习带有函数调用的指针分析。值得一提的是，这一节的分析算法是谭添老师自己设计的，可见其功力之深厚。
根据《南大软件分析课程笔记｜07 过程间分析》的知识，在指针分析中引入函数调用实际上就是在进行过程间指针分析，因此它依赖调用图（call graph）。我们之前介绍了基于CHA的调用图构建方法，然而这样构建出来的调用图精确度比较低。本节，我们将介绍基于指针分析同时构建调用图和指向关系的算法。由于指针分析中对象的创建是动态的，这种调用图构建方法又称作“on-the-fly call graph construction”。
这一节的内容稍微复杂一些，要多想、多思考，并编程实践，才能比较好地掌握。
方法调用的指针分析规则
首先，我们要看一下方法调用语句对应的指针分析规则是什么。回忆一下，规则用分数的形式表示，横线上方是前提，分号下方是结论。为方便对照，这里我们把上节课已经讲过的前四类语句也放在下面，加上方法调用语句，一共五类：
| 种类 | 语句 | 规则 | PFG边 |
|---|---|---|---|
| New | i: x = new T() |
$\frac{}{o_{i} \in pt(x)}$ | N/A |
| Assign | x = y |
$\frac{o_{i} \in pt(y)}{o_{i} \in pt(x)}$ | $x \leftarrow y$ |
| Store | x.f = y |
$\frac{o_{i} \in pt(x),\ o_{j} \in pt(y)}{o_{j} \in pt(o_{i}.f)}$ | $o_{i}.f \leftarrow y$ |
| Load | y = x.f |
$\frac{o_{i} \in pt(x),\ o_{j} \in pt(o_{i}.f)}{o_{j} \in pt(y)}$ | $y \leftarrow o_{i}.f$ |
| Call | l: r = x.k(a1, ..., an) |
 |
 |
可以看出，方法调用语句的处理规则最为复杂。我们可以结合程序运行时实际的方法调用过程来理解它：对于变量$x$来说，我们首先要找到它实际指向的对象（$o_{i} \in pt(x)$），进一步定位到该对象所属类的$k$方法（$m = Dispatch(o_{i}, k)$），在，找到$m$后，转到横线下方将$o_{i}$传播给方法内确定对象的$this$指针（$o_{i} \in pt(m_{this})$）；接着，就要模拟方法传参了，在指针分析中形参和实参分开表示，对象从实参传播到形参，这对应横线上方的$o_{u} \in pt(a_{j}), 1 \leq j \leq n$和横线下方的$o_{u} \in pt(m_{p_{j}}), 1 \leq j \leq n$；最后，将方法返回值传递给调用语句的左值——$o_{v} \in pt(m_{ret})$和$o_{v} \in pt(r)$，规则执行完毕。
注意一点，在PFG中，我们并不会在变量$x$与$m_{this}$之间添加边，而是直接将变量$x$所指的对象传播给$m_{this}$，否则可能会增加许多不必要的虚假边（考虑一下$x$可能指向多个对象，而对象所属类又具有多层继承关系的情况）。
过程间指针分析
在上面定义的规则的基础上，我们来考虑过程间指针分析的算法。首先需要注意的是，指针分析与调用图构建是相辅相成、互相依赖的。我们在上一节中提到过，“构建PFG”与“在PFG节点间传播指向关系信息”是互相依赖的，这里也是一样。
在这个场景中，逐渐丰富的调用图指出了目标程序中从main方法开始的所有可达方法。指针分析只需要分析所有可达方法和对应语句即可。
过程间指针分析算法如下图中左半部分所示，右半部分是上一节中的过程内指针分析算法，我们将这两个算法放在一起，便于对照：
可以看到，两个算法在大体流程上具有一定相似性，$Propagate$函数和$AddEdge$函数甚至完全相同，但是其他细节上还是有显著不同的。
首先，过程间指针分析是在可达前提下进行的分析，因此算法最开始传入了入口方法main，并不断通过$AddReachable$更新可达方法集合。另外，过程间分析会调用$ProcessCall$函数来处理方法调用语句，该函数实现了我们在最开始定义的方法调用分析规则。过程间指针分析算法最终的输出有两个：指向关系集合与调用图。
谭添老师在课上给出了一个具体案例，我把其中的关键步骤拼在一页图中，方便理解整个算法的执行过程：
总结与思考
本节课，我们学习了过程间指针分析算法，它更为复杂，但是也更为实用。一句话，期待在未来的安全研究中用到这个算法。