很多人学静态分析时都会卡在一个点上明明把数据流分析那一套规则背得滚瓜烂熟可一放到真实程序上结果总是不对劲。原因往往只有一个——真实程序里到处是方法调用而经典的过程内分析把每一次调用都当成一个黑盒。黑盒一多精度就没了。我整理某高校软件分析课程07的过程间分析Interprocedural Analysis这一讲时把这个问题彻底想通了过程间分析不是一个新的分析算法而是一层架在普通数据流分析之上的“管道系统”让数据真正能在方法之间流动起来。这篇文章适合两类人看一类是在补静态分析基础的学生另一类是要在自己的工具链里实现过程间分析的开发者。我尽量把课程里那些抽象的规则翻译成能直接落地的工程思路也会把我自己实现时踩过的坑一并交代清楚。1. 过程内分析的死角一次方法调用就能让精度归零1.1 过程内分析怎么做又败在哪里过程内分析的定义很朴素一次只分析一个方法。分析方法内部的 CFG控制流图为每个程序点计算数据流值遇到方法调用指令时不去看被调用方法内部发生了什么而是把它当成一个不透明操作。对常量传播来说调用点的结果就是未知对指针分析来说调用点产生的引用就是新的未知对象。课程里有一个非常经典的例子我稍微改一下结构int bar(int x) { return x 1; } void main() { int a 1; int b bar(a); int c a 1; int d b c; }只要算过一遍过程内常量传播你就会发现一个反直觉的结果b、d全被标记成 Not A ConstantNAC。可是人一眼就看得出来bar(a)一定等于 2d一定等于 3。为什么分析器算不出来因为过程内分析根本不会进入bar的内部bar(a)的返回值对它来说就是一个未知数。如果只是常量传播这种场景损失的精度还能忍。但当你做的是一整套污点分析、逃逸分析、或者别名分析的时候方法调用处理不好结果会差到完全不可用。比如a obj.getX()你如果不知道getX()内部到底返回了什么字段后面的分析基本上只能靠猜。这一讲的整个出发点就在这里必须让分析“看穿”方法调用。这是过程间分析要解决的核心问题。1.2 从黑盒到白盒过程间分析到底在“间”什么过程间分析做的事情粗看就是一句话把所有的分析方法串成一个整体让数据流沿着真实的调用路径流动。但“串起来”这三个字背后有三个具体工程问题第一调用目标是谁。a.foo()里的foo可能是多个子类里各自实现的版本分析器必须知道这个调用点可能跳到哪些方法。第二数据怎么传递。实参怎么变成形参、返回值怎么传回调用点、方法内部的局部变量污染会不会泄漏到调用方的其他路径上。第三迭代怎么收敛。过程间分析的数据流图比单方法 CFG 大得多不动点迭代需要一种更聪明的调度方式。课程里把这些问题拆成了两块前面讲调用图构建后面讲过程间数据流分析。调用图回答“可能调用谁”数据流分析回答“数据怎么流”。这两块是顺序依赖的关系——调用图错了后面的数据流分析再精确也没有意义。2. 调用图构建的基石CHA 算法与它的取舍2.1 虚分派调用图要解决的核心难题先看看调用图长什么样。调用图是个有向图每个节点是一个方法每条边是一个调用关系。一个调用点可能对应多条边因为语言里有虚方法、接口方法甚至函数指针。构建调用图的核心工作就是处理虚分派一个调用表达式的静态类型是 A但运行时指向的实际对象可能是 A 的任意一个子类。举一个最简单的多态例子class A { void foo() { ... } } class B extends A { void foo() { ... } } void test(A x) { x.foo(); }x的静态类型是 A但它可能实际指向B的实例。调用点x.foo()既可能调到A.foo()也可能调到B.foo()。如果不把这两个目标都找出来调用图就是不完整的后续过程间分析会把某些路径整个漏掉。CHAClass Hierarchy Analysis解决的就是这个问题。它只根据类的继承层次来枚举可能的调用目标不关心对象的实际创建位置。做法非常直接从调用点的接收者静态类型出发在这类型本身以及它的所有子类里查找所有 override 了该方法的方法定义全部作为候选目标。2.2 CHA 的完整流程课程里给出的 CHA 流程可以拆成四步。我按自己的理解重新组织一下第一步解析调用指令。先识别调用点的调用类型是静态调用static、特殊调用super还是虚调用virtual/interface。静态调用和 super 调用可以直接确定目标方法只有虚调用需要走类层次。第二步确定接收者的声明类型。比如x.foo()x的声明类型就是 A。第三步遍历声明类型及其子类链。在 A 以及继承 A 的所有子类中搜索foo()的方法声明只要某个子类 override 了foo()就把这个方法加入候选集合。第四步把候选方法映射成调用图中的边然后对新增的方法继续做同样的处理直到没有新方法被加入。核心逻辑用伪代码表达就是这样resolve(call site cs) { T declared_type(cs.receiver) for each method m in hierarchy_of(T): if m.name cs.method_name m.signature cs.signature: add_edge(cs, m) }看起来简单但有一个很重要的点CHA 对子类的搜索是“全量”的。也就是说它不会区分 A 的子类里哪些是实际被实例化过的。没有new B()的代码B.foo()依然会被列为调用目标。这是 CHA 精度低的最根本来源后面第 2.3 节细说。2.3 快但粗糙CHA 精度与性能的权衡CHA 的优势是快。它不需要做任何程序分析只需要类继承关系所以构建调用图的时间非常短在 IDE 里面做“查找所有实现”这种功能几乎是秒开。但它的代价就是候选方法集合偏大引入大量实际不会发生的调用边。我们用一个直观的对比来说明不同算法之间的精度梯度算法候选目标集来源精度构建成本CHA接收者静态类型的所有子类低极低RTA仅程序中出现过的类型中低指针分析接收者的可达对象集合高高CHA 到 RTA 的改进思路很直接程序里new过的类型集合是有限的把类层次搜索范围从“所有子类”缩小到“当前程序可达类型中被实例化的子类”就能砍掉不少假调用边。课程后面讲指针分析时会更进一步直接分析出某个变量可能指向哪些对象把虚调用的分派精度提到最高。这里必须强调一个工程观点不要一上来就上指针分析。调用图的构建成本会直接放大后面的过程间分析。实际项目里先用 CHA 搭一个完整链路确认数据流分析逻辑是对的再逐步精化分派策略是性价比最高的路线。我见过很多团队一上来就搞全程序指针分析结果跑一个中大型项目要几分钟连迭代调试都做不下去。3. 过程间数据流分析的桥梁设计节点转移与边转移3.1 ICFG给过程间分析铺路有了调用图下一步就是把单方法的 CFG 拼成一张更大的图——过程间控制流图Interprocedural Control Flow Graph, ICFG。ICFG 的节点集合包含每个方法 CFG 里的所有节点以及每个调用点对应的两个特殊节点Call 节点和 Return Site 节点。Call 节点是调用指令所在的节点Return Site 节点是调用指令执行完之后继续执行的节点在字节码里通常就是下一条指令。为什么要把一个调用点拆成两个节点因为调用前后这两个节点的数据流状态差异极大Call 节点之前是调用方的状态Return Site 节点之后是被调方法返回后的状态。混在一起的话参数传递和返回值处理会纠缠不清。ICFG 的边也分三类。普通 CFG 边是方法内部的跳转调用边是从 Call 节点指向被调方法入口节点的边返回边从被调方法的出口节点指向 Return Site 节点。这三类边合起来构成了数据在方法之间流动的通道。光有这三类边还不够还有一个非常关键的设计Call-to-Return 边。它从 Call 节点直接连到 Return Site 节点不经过被调方法。这条边模拟的是“被调方法不影响某个变量”的路径。没有这条边过程间分析的所有路径都必须经过被调方法内部计算代价极大而且会错误地把被调方法内部的变量修改传播到调用方的其他路径上。它是过程间数据流分析精度和性能的关键。3.2 call 与 return 节点的转移函数设计课程里把过程间分析的数据流规则设计成节点转移函数和边转移函数两部分。先看 Call 节点和 Return 节点的转移函数我直接用常量传播域的变量值来描述。Call 节点要做两件事。第一件是处理参数的“向上传递”把实参值传给被调方法的形参。比如int b bar(a)这里a的值 1 会通过 Call 节点流入bar方法入口处的形参x。第二件是向下的局部处理把返回值对应的变量旧值杀掉。还是这个例子调用完成后b会被重新赋值所以 Call 节点向下传递时要把b标记为未定义UNDEF防止旧值顺着别的路径流入 Return Site。Return 节点做的事情更纯粹把被调方法出口处的返回值变量值复制给调用点的 Return Site。比如bar内部有return x 1此时返回变量的值是 2那么从 Return 节点流出时2 要顺着返回边到达main方法里bar(a)的 Return Site 节点。这里有一个初学者经常混的概念Call 节点的“向下传递”和 Return 边的“返回数据”是两回事。Call 节点的向下传递处理的是调用前可能残留的旧值Return 边传递的才是真实返回值。两者方向不同处理的数据也不同。3.3 call-to-return 边切断被调方法对调用点无关变量的污染为什么单独把 Call-to-Return 边拎出来讲因为它是过程间分析最容易漏掉、也最容易写错的一环。它的语义很特别沿着这条边流动的数据只包括那些保证不会被本次调用修改的变量。怎么定义“不会被修改”最简单的方式是用预先算好的 mod 集合。所谓 mod 集合就是某个方法内部可能修改的全局变量或者调用方可见变量的集合。如果被调方法的 mod 集合不包含某个变量那么这个变量在 Call-to-Return 边上的值就是安全的可以从 Call 节点直接抄到 Return Site。反过来说如果被调方法会修改某个变量那这条路就不能传这个变量的旧值必须把对应变量杀掉。课程里给了一个非常典型的例子void main() { int a 1; int b callee(a); // callee 内部会修改 a // 这里 a 不能被想当然地当成 1 }如果一开始不知道callee会修改aCall-to-Return 边会把a 1直接传到 Return Site那分析结果就是错的。正确地做法是查询callee的 mod 集合发现a在其中则在 Call-to-Return 边传值时 kill 掉a。用一句话总结Call-to-Return 边模拟的是“绕过被调方法”的路径它必须依赖被调方法的副作用信息来保证精度。没有这一层处理过程间分析的正确性无从谈起。3.4 套入常量传播域完整的五要素课程最后把这套框架总结成了五个具体要素。道理不复杂就是套用经典数据流分析框架域、方向、转移函数、meet 操作、迭代入口。只是这次的作用对象变成了 ICFG。常量传播的域是每个变量的常量值状态包括 UNDEF、常量、NAC。方向是前向分析沿着 ICFG 的控制流方向传播。转移函数就是前面说的节点转移加边转移。meet 操作是同值取该值不同值取 NAC任何值和 UNDEF 合并结果取那个非 UNDEF 的值。迭代入口从main方法出发或者更准确地说是从整个程序的入口集合出发。这个框架有一个特别优雅的地方它只定义了三种路径上的数据流动方式就把所有跨方法的数据传递都覆盖了。正常边管方法内部流动调用边管参数传入返回边管返回值传回Call-to-Return 边管绕过被调方法的传播。四类元素合在一起构成了一条完整的“过程间路径”的所有可能形态。4. 常量传播实战推演从入口到不动点4.1 一个小程序的完整推演这一节我们把前面的规则全部串起来手动推一遍常量传播。程序如下int addOne(int x) { return x 1; } int twice(int x) { return x * 2; } void main() { int a 1; int b addOne(a); int c twice(b); int d a b c; }从入口开始的数据流推演过程main入口处a 1。到达第一个 Call 节点addOne(a)。实参a的值为 1通过调用边传到addOne的形参x。Call 节点向下同时 kill 掉b的旧值此时b还未定义所以不会有实际影响。同时 Call-to-Return 边把a 1原样传到 Return Site因为我们知道addOne不会修改a。addOne方法内部执行return x 1。此时x 1所以返回值状态是 2。这个 2 通过返回边传回main方法中对应的 Return Site 节点b 2。紧接着到达第二个 Call 节点twice(b)。实参b的值为 2 传到形参x。twice内部执行x * 2返回值为 4。传回后c 4。最后执行int d a b c三个变量分别是 1、2、4所以d 7。最终结果a 1b 2c 4d 7全部是常量。这个程序如果只用过程内分析结果会是b NACc NACd NAC两者之间是完全不同的精度级别。4.2 过程内与过程间的精度对比把两种分析的结果放在一个表格里差异一目了然程序点过程内分析过程间分析int a 1之后a 1a 1int b addOne(a)之后b NACb 2int c twice(b)之后c NACc 4int d a b c之后d NACd 7可以看出过程间分析并不是用什么高深的奇技淫巧它只是让数据老老实实走了一遍真实的调用路径。所有看似神奇的精度提升都来源于“方法之间能传数据”这件事本身。这里有一个很值得玩味的点过程内分析在d上得到 NAC不只是因为b未知还因为它在b未知的情况下连a都是安全的却不敢确认导致一步错步步错。过程间分析因为把b追出来了整个链路的精度全部保住了。精度的损失是会累积的这是我在实际做工具时体会最深的一句话。4.3 调用图的“外溢价值”过程间分析产出的调用图不是一次性消耗品。课程里没有展开但这里值得多说一句调用图本身就是一个非常有价值的程序分析产物。IDE 的“查找所有实现”、方法跳转、重构时的安全影响范围计算都用的是类似 CHA 或更精化的调用图。做编译器优化的团队拿调用图做内联决策、死代码消除也比直接分析字节码高效得多。所以哪怕你的分析任务非常简单只要程序里有方法调用构建一张可用的调用图都值得。它是一次性投资后面的所有分析都能复用。我在实际工程里维护分析框架时调用图都是单独模块单独缓存因为几乎每一个下游分析都要它。5. 工程实现踩过的坑与几条实在经验5.1 worklist 调度里最容易被忽略的触发关系理论上讲把 ICFG 建好、转移函数写好直接套用传统的不动点迭代就行。但工程实现时有一个很隐蔽的性能陷阱worklist 的触发关系。举个例子。addOne方法入口形参的值发生变化时addOne内部所有后续节点的状态都可能发生连锁变化这没错。但如果addOne的 Return 节点的返回值状态发生了变化会发生什么答案是所有调用addOne的调用点对应的 Return Site 节点都必须重新入队处理。这一步如果漏了分析结果几乎必然不对。另一个容易被忽略的点是 Call-to-Return 边的依赖关系。如果被调方法的 mod 集合是动态计算的那 mod 集合变化时也要触发相关 Call-to-Return 边的重新传播。课程里通常会预设 mod 集合是固定的但真实工程里你放上一个全程序副作用分析这个集合本身就要迭代逼近。我在早期版本里没处理这种依赖结果跑出来的常量传播值时对时错最后定位到是 mod 集合更新后没有重新触发调用点整整调了两天才发现。实现的建议是把“节点状态变化”和“边状态变化”分别建模成两类 worklist 事件并且确保返回值变化事件能够映射到所有调用点的 Return Site 上。最好在测试里覆盖“同一个方法被不同调用点调用”的场景这是最容易暴露调度问题的用例。5.2 库方法、native 方法与手写模型真实程序不可能只分析你写的代码。一旦调用图里出现System.currentTimeMillis()、StringBuilder.append()这类方法CHA 通常解析不出合理的目标因为它们要么是 native 方法要么在 JDK 的类库深处。业界通用做法是给库方法写模型手工定义每个关键库方法的参数传递关系、返回值属性和副作用。比如Collections.emptyList()可以建模成“返回一个空的不可变 List 对象”String.valueOf(int)可以建模成“返回一个新字符串对象”。这样下游分析不需要真的钻进 JDK 源码也能获得足够精确的结果。写模型的时候注意一个原则模型的精度要跟分析的精度对齐。如果你做的是常量传播库方法模型只需要关心“是否返回常量”如果你做的是指针分析模型就得多写一步“返回对象是否逃逸”。模型不是越多越好只有那些真的会被调用并影响分析结果的方法才值得单独建模。5.3 精度与规模从 CHA 走向更精细的分派最后说一个方向性的经验。CHA 的调用图精度低这在小型 Demo 上不会造成明显问题但一旦跑到中大型项目接口方法有多实现的时候候选目标集会膨胀得非常快。调用边一多过程间分析需要更新状态的方法就多分析时间成倍增长。我做过的实践里最有效的优化路径不是直接换指针分析而是先做一次 RTA 或者非常轻量的类型传播把程序中所有实例化过的类型收集起来然后让虚调用分派只在实例化类型集合里搜索。这个改进通常只需要额外维护一个“已创建类型集合”复杂度极低却能让调用边数量显著下降。如果这一步还不够再去考虑真正的指针分析。课程的后续章节会讲指针分析如何为虚调用提供更精确的 dispatch 信息那是一条更长的路。但从 CHA 到 RTA 再到指针分析每一步都是精度与性能的权衡不存在“越精确越好”这种说法。工程上永远是够用就好。我自己在这门课学到的最有价值的东西不是那些规则本身而是它不断提醒我分析一个方法的时候永远要意识到方法外部还存在一个更大的环境调用的连接让每一个方法都不可能真正孤立。过程间分析就是在为这种不孤立搭建严谨的桥梁。后面的学习中指针分析、逃逸分析、污点分析全都踩在这座桥上把这套基础砸实了后面会顺畅很多。