Anders Møller and Michael I. Schwartzbach February 10, 2022 这是最新的程序分析技术资料，2022年的。

一、为什么需要过程间分析 前面的数据流分析学习中，我们接触到的都是过程内 intraprocedural 的分析，在过程内 分析遇到函数调用如何处理的呢？ 在过程内分析的情况下，对函数调用的通常的做法是：对方法的调用做最保守的估计， 认为方法调用可以做任何事情，以确保安全近似，举例如下： 对于常量传播的例子来说，如下程序片段： 过程内分析不对函数调用进行处理，在 foo()中对函数 bar()时，静态分析认为 bar()函数 输入的参数是任何值，所以 x = NAC，y=NAC，foo 函数中调用 bar 后的返回值也认为是任何 值，所以 n = NAC。而实际的运行情况来看，n 的值是 10，x 就是 42，y 就是 43。过程内分 析丢失了精度。 为提高分析的精度，就需要进行过程间的分析，数据流通过过程间的控制流边进行传递， 如下图所示：

一、迭代算法 Iterative Algorithm Data Flow Analysis Foundations，数据流分析基础理论。掌握数据流分析 基础理论，才能自如的设计数据流分析算法来解决特定的静态分析问题。 下图是一个通用的数据流分析迭代算法，采用前向数据流，它用来得到一个 数据流问题的解 给定一个含有 k 个节点的程序 CFG，迭代算法每次迭代时更新每个 CFG 节点 的输出信息，即 OUT[n]。 假设数据流分析中数据 data facts 的集合是 V，这里的数据是指我们分析 问题的数据，数据的 domain 就是这些数据抽象值的域。比如，我们在分析到达 定值这个具体数据流问题时，V 就是程序所有变量的集合，domain 就是程序中所 有的变量可能取得的抽象值的集合{0,1}。再如，常量传播例子中，分析的数据 data facts 集合 V 就是程序中所有的变量，v 的 domain 就是{未定义、不是常 量、0、1、2、1.2、...} ，这个 domain 就是无穷的，因为作为常量可是任何数。 在到达定值中，我们用一个 bit vector 来表示节点的输出数据作为