企业官网建设流程全解析

最近在整理某高校《软件分析》课程笔记，正好把第7讲“过程间分析（Interprocedural Analysis）”彻底啃了一遍。这一讲可以说是整门课的第一个分水岭：前面几讲讲的控制流分析、数据流分析，默认都在单个函数体内做；可真实程序几乎没有不跨函数的，一旦遇到函数调用，过程内分析的结论要么失真，要么直接没法用。这篇笔记就把我对过程间分析的完整理解，从“为什么非它不可”到调用图构建，再到过程间数据流分析的两条经典路线和上下文敏感，重新梳理一遍。对正在学编译器、静态分析，或者在做代码缺陷检测、程序理解相关工作的朋友，这份整理应该能帮你少走不少弯路。

1. 为什么过程内分析不够用：先从实际问题讲起

1.1 一个再普通不过的例子

先看一段非常简单的代码：

int add(int a, int b) { return a + b; } void main() { int x = 1; int y = 2; int z = add(x, y); // use(z) }

如果只做过程内分析，也就是把每个函数单独抽出来分析，那么在main函数里遇到z = add(x, y)这个调用点时会非常尴尬。最粗暴的做法是把这个语句当成“杀死所有数据流信息”的黑洞：z从此变成非常量，x、y的值也全部视为未知。这样得到的结论虽然安全，但精度差得离谱——我们肉眼就能看出来z一定等于3，分析器却告诉你“不知道”。

更麻烦的是正确性问题。过程内分析无法知道被调函数是否修改了全局状态、是否给外部对象写了字段，也无法知道函数返回之后哪些变量还活着。于是很多分析必须做最保守的假设：调用之后所有可达内存全部被修改，所有临时值全部作废。这样的分析结果在真实项目里基本没有实用价值，因为误报会多到没法看。

1.2 核心问题：函数调用边界怎么处理

过程间分析要解决的核心问题就是：数据流信息如何跨过函数边界传递。具体拆解成两个子问题：

1. 调用图（Call Graph）构建：一个调用点c: x.f(args)到底可能调用哪些函数？在面向对象语言里，由于动态派发，这个答案通常不是一个函数，而是一组候选函数。
2. 过程间数据流分析（Interprocedural Dataflow Analysis）：调用点的实参值如何传给被调函数的形式参数？返回值如何传回调用点？全局变量和堆对象如何在调用前后保持或更新？

这两件事是有先后顺序的：先有调用图，才能知道数据该往哪些函数里传。调用图越不精确，后续数据流分析就要背负越多虚假路径，整体精度直接被拉低。这也是为什么几乎所有静态分析框架的第一阶段都是在拼命优化调用图。

2. 调用图构建：把所有“可能”都列出来

2.1 从声明类型到候选方法：CHA算法的完整推导

调用图构建最经典的入门算法是 CHA（Class Hierarchy Analysis，类层次分析）。思路极其直白：我不猜运行时对象到底是谁，我只根据声明类型去类继承关系里把所有可能的方法实现都捞出来。

举个例子：

class A { void f() { ... } } class B extends A { void f() { ... } } class C extends B { // 没有重写 f，继承 B 的实现 } void test(A a) { a.f(); // 调用点 }

调用点a.f()里a的声明类型是A。CHA 的做法是：

• 先看类A里有没有f，有的话加入候选集合；
• 再遍历A的所有子类，如果子类重写了f，就把子类的f也加入候选集合；
• 如果子类没重写，则继续沿继承链找最近的那个重写版本。

所以上面例子里候选集合就是{A.f(), B.f()}，因为C没重写f，它用自己的还是继承来的B.f，CHA 直接把B.f算作C这一支的答案。如果接口也参与进来，规则稍微扩展：接口里的抽象方法、default 方法，以及所有实现类里对应的方法，都要进候选集合。

CHA 的好处是简单、快，只依赖类层次结构信息，一遍遍历就能构建完整个程序的调用图。坏处是精度很差：test的形参a实际运行时也许只可能是某个C对象，绝对不会是A或B，但 CHA 不管这些数据流信息，把所有候选都给你列出来，于是分析器必须假设每条路径都可能发生。

2.2 RTA、0-CFA 与 k-CFA：精度阶梯怎么选

既然 CHA 过于保守，自然的改进思路就是引入一点运行时信息。行业内按精度从低到高，大致有这样一档一档的算法：

• RTA（Rapid Type Analysis）：CHA 的基础上，只保留那些在程序里确实被new过的类。如果一个类在整个程序里从未被实例化，那么它里面定义的方法就不可能成为运行时目标，直接淘汰。这个改进实现成本极低，精度提升却不小，很多工业级工具默认就用它。
• 0-CFA：比 RTA 更进一步，开始追踪变量的“指向关系”。它会根据赋值语句A a = new A()建立一个从变量到可能对象的映射，然后沿着数据流传播这个映射。分析调用点时不看声明类型，而是看这个变量可能指向哪些对象的分配点，再基于对象类型去找方法实现。这样a.f()的候选集合可以精确到“这个变量真的可能指向的类”。
• k-CFA：在 0-CFA 的基础上加上下文敏感，为不同调用上下文分别追踪指向关系，精度最高，代价也最大。一般的规则是层数越高，候选集合越小，但算法复杂度呈指数增长。

2.3 调用图算法怎么选：一张表讲清楚

我自己的实际体会是：选调用图算法永远是个精度和开销的博弈。先跑 CHA 看总体规模，如果候选方法集合大到数据流分析无法承受，再升级到 RTA 通常能砍掉相当一部分不可能目标。至于 0-CFA 和 k-CFA，在真实项目里往往配合按需分析（on-demand）使用，而不是一上来就对全程序跑高精度算法。

3. 过程间数据流分析：让数据跨过函数边界流动

3.1 ICFG：给每个函数加上“出入口”

有了调用图，下一步就是把数据流信息真正传起来。这一讲的核心数据结构叫ICFG（Interprocedural Control Flow Graph，过程间控制流图）。理解它最简单的方式是：把每个函数的 CFG 当作一张独立的地图，然后在“调用点”和“被调函数入口”之间架桥，在“被调函数出口”和“调用点的下一条语句”之间再架桥。

具体来说，ICFG 等于三部分叠加：

• 所有函数的 CFG；
• 一组call edges，从调用点指向被调函数的入口节点；
• 一组return edges，从被调函数的出口节点指向调用点之后的语句。

比如main里调用add(x, y)时，ICFG 中会同时存在一条从调用前状态到add入口的状态流，以及一条从add出口状态回到main调用后的状态流。这样一来，x=1和y=2就能顺着 call edge 流进add的形参a、b；add算完结果后，返回值再顺着 return edge 流回z。

3.2 常量传播实例：完整走一遍数据流

回到开头的add例子，假设要做的是常量传播。过程间分析的输出应该是：

• 在main的z = add(x, y)之后，z的抽象值是常量3；
• 在add函数体里，形参a、b分别可以确定为常量1、2。

这个过程如果手推，大概分四步：

1. main入口初始化x=1、y=2；
2. 流经z = add(x, y)调用点时，沿 call edge 产生一组新的数据流事实：进入add入口时，a = x (即1)、b = y (即2)；
3. 在add的 CFG 里跑常规常量传播，得到return a + b处返回值是常量3；
4. 沿 return edge 回到main，把返回值常量3赋给z。

听起来很简单，但这里面藏着一个关键问题：同一个函数可能被多个调用点调用，每次调用时形参的抽象值都不一样。如果不加区分，把不同调用点的实参混在一起传到同一个函数体里，结果就会变成“合并后的最保守近似”。比如一个调用点传1，另一个调用点传2，合并之后形参变成“非常量”，返回值也跟着变成“非常量”，所有调用点的精度集体下降。这就是所谓的过程间分析精度杀手，必须用上下文信息来隔离。

3.3 方法一：Call-string，给数据流值贴标签

应对上面这个问题，第一套经典方案是Call-string 方法。核心思路是：给每个数据流值加上一个“我在哪个调用历史下产生的”标签，也就是调用字符串（call string）。这个字符串记录了从入口到当前函数所经过的调用点序列。

举个例子。main调用了add，调用点编号是1；add内部又调用helper，调用点编号是2。那么在helper函数体内，所有数据流值都会带着调用字符串1-2。如果main另一个位置也调用了add，调用点编号是3，那从这条路进去的数据流值标签就是3-2。两个上下文互不干扰，各自维护一套抽象状态。

手写代码时，Call-string 分析通常是这么组织的：

• 数据流状态从“变量到抽象值”的映射，扩展成“调用字符串 × 变量到抽象值”的映射；
• worklist 里的每个元素是一个(函数节点, 调用字符串)对；
• 每次通过 call edge 进入一个新函数时，把当前调用字符串拼接上当前调用点编号，作为被调函数入口的上下文；
• 每次通过 return edge 返回时，弹出最后一个调用点编号，回到调用方的上下文。

递归调用会让调用字符串无限变长，所以必须限制长度。通常做法是设置一个阈值k，只保留最近k个调用点，超过阈值就截断合并，这就是标题里常说的 k-CFA 的由来。实际用的时候 k=1 已经能让精度有肉眼可见的提升，k=2 在很多场景下就开始有点吃不住了。

3.4 方法二：函数摘要，把函数当成一张“查表”

第二种经典方案叫函数摘要（Functional / Summary 方法）。它的思路完全反过来：不重复分析函数体，而是把每个函数事先编译成一张“输入 → 输出”的转换表。

可以这样类比：Call-string 是每次调用都把函数体完整跑一遍，类似每次算算术都重新推导一遍公式；函数摘要则是先把公式推出来，之后每个调用点直接套用公式。

对于一个形如int add(int a, int b) { return a + b; }的函数，摘要大概长这样：

• 输入：a = 常量1，b = 常量2
• 输出：返回值为常量3

分析器在做过程间分析时，遇到add(x, y)调用，只需要把当前x、y的抽象值代进摘要的输入模式里，查一下输出得到返回值，完全不需要进入add的函数体。如果add被调用了成千上万次，省下来的时间是相当可观的。

函数摘要的难点在于“摘要的生成”。不是每个函数都像add这么简单，函数内部可能有分支、有循环、有状态更新、有再次的函数调用。所以实际工程里通常会用不动点迭代的方法先算出每个函数在格上的转移函数，把内部数据流逻辑压缩成“输入状态到输出状态”的映射，再缓存起来复用。

3.5 两种方法怎么取舍

我在实际项目里的做法是：对应用代码核心路径用 Call-string 拿细节，对庞大的第三方库函数用预计算的摘要，两者结合起来的分析速度能快一个数量级。这种“混合模式”在工业级分析器里非常常见。

4. 上下文敏感：精度革命还是性能陷阱

4.1 上下文敏感到底在解决什么

过程间分析做到这一步，很多人会问：Call-string 给数据流值贴了调用历史标签，这不就是上下文敏感吗？严格说，Call-string 只是上下文敏感的一种实现形式。理解上下文敏感这件事，关键是先分清两个维度：

• 控制流上下文：关注“这个值是在哪个调用序列下产生的”，对应 Call-string；
• 数据流上下文（对象敏感性）：关注“这个值来自哪个对象分配点”，通常叫对象敏感分析（object sensitivity）。

两者在真实的面向对象程序里都很重要。比如分析一个集合类List，如果只能区分调用历史，却分不清list1.add(1)和list2.add(2)里的list1、list2是两个不同对象，那么分析器就会把两个对象的状态混在一起，精度直接崩溃。所以在 Java 这类语言的分析中，对象敏感往往比调用字符串更关键。

4.2 精度的代价：状态爆炸与工程权衡

上下文敏感的代价是空间和时间的双重膨胀。不敏感分析里，一个函数只要维护一套抽象状态；加了上下文之后，每个可能的上下文都要维护一套状态。上下文的组合数量往往是指数级的，这就是所谓的状态爆炸。

现实中踩坑的经验是：不要一上来就用高 k 值的上下文敏感分析跑全量程序。我在做某个中型项目的逃逸分析时，一开始用了 k=3 的上下文敏感配置，结果跑到一半内存直接撑爆。后来改回 k=1，再配合按需细化（遇到特定告警再加深上下文深度），效果立竿见影：内存占用降到五分之一，分析时间从小时级降到分钟级，而关键告警一条都没漏。

还有一个容易被忽略的细节：上下文敏感并不总是“更精确”。它只是在某个特定的上下文划分方式下更精确。如果划分维度选得不好，比如调用字符串记录了路径上所有中间函数，但这些函数对目标变量的值完全没影响，那么这些上下文只是白白增加状态数量，对精度没有任何帮助。这就需要经验性地选择“敏感维度”和“敏感深度”。

5. 常见误区与排查思路

5.1 误区：CHA 就等于过程间分析

我刚学的时候也犯过这个错，以为调用图构建完，过程间分析就做完了。实际上 CHA 只是搭建了一个“数据流该往哪走”的骨架，真正决定分析质量的是走在上面的数据流算法。调用图负责回答“可能调用谁”，数据流分析负责回答“数据流经这些调用时值怎么变”，两者缺一不可。判断一个分析器好不好，不仅要看调用图精度，还要看数据流传递时对上下文、对象状态的区分能力。

5.2 误区：Call-string 长度越大越好

有段时间我总想把 k 调大一点，觉得上下文越深越精确。但事实上随着 k 增大，收益递减，代价却指数上升。而且递归程序里的调用深度是无限的，k 再大也覆盖不了所有真实调用链，最终都要靠截断求近似。工程上更合理的做法是先跑一个粗粒度分析找出可能出问题的热点区域，再对这个区域做高精度上下文分析，而不是全局一刀切用大 k。

5.3 递归调用、多态与库函数怎么处理

递归调用是过程间分析的一道经典关卡。直接用调用字符串会无限增长，必须靠截断或不动点迭代来保证终止。通常做法是：当调用字符串达到长度上限后，把新状态和已有状态合并，用格上的偏序关系判断是否收敛。

多态和接口的 default 方法也是常见坑点。CHA 处理接口时，要把接口的抽象方法加上所有实现类的方法全部纳入候选；如果候选集合为空，也就是一个调用点找不到任何可行方法实现，通常意味着代码有编译错误，或者分析模型有遗漏，要优先排查是不是类型层次信息没收集全。

库函数的处理则是另一个层面的问题。对 SDK 和第三方库，不可能真的把整包源码都拉进分析，一般用一组手工建模的摘要来描述它们的核心行为，比如“某函数会修改入参对象的某个字段”“某函数返回新对象”。这个摘要库的质量，往往决定了整个分析器在实际项目里的可用性。

根据我个人在好几个静态分析项目里折腾的经验，过程间分析这部分最反直觉的地方在于：真正难的不是把数据传过函数边界，而是如何在传递过程中不丢失区分度。调用图和上下文敏感方案选得好，分析结果既快又准；选不好，要么慢到没法用，要么快但全是误报。如果你也在搭自己的分析器，我的建议非常简单：先用 CHA + Call-string(k=1) 把整条流程跑通，再逐步把调用图升级到 RTA 或 0-CFA，最后根据实际误报情况决定要不要上对象敏感。这条路虽然看起来慢，但每一步都能看得见收益，排查问题也会容易很多。