做程序分析这些年我手里最常用、也最容易被低估的一张图就是程序依赖图Program Dependence GraphPDG。很多刚入门程序分析的朋友学完控制流图CFG就觉得差不多了觉得一张流程图能看清分支和循环就够了。可真正上手做变更影响分析、程序切片、缺陷定位的时候你会发现CFG只能告诉你代码怎么走但回答不了改这一行到底会牵动哪些地方。PDG解决的正是后面这个问题它把控制依赖和数据依赖显式地画成边让谁决定谁执行谁的数据从谁来变成可以直接遍历的图结构。这篇文章我打算按我自己带新人的路子写先讲清楚PDG到底解决什么问题、它的能力边界在哪再把控制依赖和数据依赖这两根支柱拆开讲透包括后支配、到达定值这些背后的数学定义然后从一段十几行的C代码出发一步步手搓出一张PDG把每一步的计算过程和参数选择都写清楚接着聊它在工程里的四类真实用法再给出工具选型建议和可以直接抄的实操命令最后是我这些年踩过的坑和排查清单。不管你是刚接触程序分析的学生还是已经在做静态分析工具、代码审计、编译器优化的工程师应该都能从里面捞到点能直接用的东西。1. 为什么程序依赖图PDG值得单独拎出来讲1.1 从控制流图到依赖关系的认知跃迁我们先对齐一下概念。控制流图是把程序拆成基本块用有向边表示执行完这块可能跳到哪块。它的信息是可达性从入口能不能走到这个块、这个块之后可能去哪。但可达性是可能层面的它不区分这个块一定会执行和这个块可能执行。举个例子if (a 0) x 1; else x 2;这两条赋值语句在CFG里都只是分支的两个出口地位是对称的。可如果你想知道x 的最终值受谁影响你需要知道这两条语句各自在什么条件下才生效而且它们和后面的return x之间有一条数据流的因果链。CFG本身不表达这层因果它只表达顺序和跳转。PDG就是在这个缺口上补了一刀。它在CFG的基础上额外画出两类边控制依赖边表示X 的执行与否决定了 Y 是否执行数据依赖边表示Y 用到的某个值是由 X 定义的。节点还是那些语句或基本块但图的语义从怎么走升级成了谁影响谁。这一步升级看着简单但它把很多原本要靠人肉推理的问题变成了图上的可达性问题。我常跟新人打比方CFG是城市路网图告诉你怎么从A开到BPDG是供应链图告诉你哪个零件缺货会卡住哪条产线。路网图能帮你导航供应链图才能帮你做风险分析。做程序分析谁影响谁的问题占了绝大多数。1.2 一个真实场景为什么CFG回答不了改这行会影响谁假设你在维护一个老系统某天要改一个校验逻辑原本if (score 60)改成if (score 55)。你打开CFG看哦这是改了个分支条件跳转关系变了。但真正的问题是这行改动会不会让下游某个统计报表算错会不会让某个已经写过测试用例的接口行为变化CFG给不出答案因为阈值的具体数值在CFG里只是个表达式节点它看不到score是怎么一路被算出来、又怎么一路被消费掉的。而PDG里score的定义点会有一串数据依赖边指向所有用到它的地方score 60这个判断又会有一串控制依赖边指向它管辖的语句。你从改动点出发沿着这两类边走一遍走到哪里停影响范围就在哪里。这就是后向切片的雏形也是变更影响分析最朴素的实现方式。我在实际项目里做过一次统计一个中等规模的服务端模块改一个核心配置读取的默认值用CFG人工追影响范围大概要小半天还容易漏换成基于PDG的脚本扫一遍十几秒出结果命中二十多个文件其中有三个是人工追的时候压根没想到的间接依赖。这个差距不是效率问题是漏报问题。1.3 PDG的能力边界说法与实话讲完好处得泼点冷水。PDG不是万能的它的精度完全取决于前面的分析精度。具体说有三个天花板第一别名分析的精度决定了数据依赖的精度。C/C里int *p x; *p 1;这种间接写如果你不做指针分析就不知道它定义了x数据依赖边就丢了。Java里的字段访问、反射也是同一个问题。第二PDG是语句级的图粒度比AST粗。你想知道某个变量的某个位被改了PDG层面看不到得下沉到更细的表示比如SSA形式或值流图。第三过程间依赖需要额外扩展。标准的PDG是单个过程函数内的图跨函数的调用关系要靠System Dependence GraphSDG来表达SDG里多了调用点、形参实参的绑定边。很多人说PDG能看到跨函数影响其实说的是SDG。注意别把PDG和CPG搞混。CPGCode Property Graph是把AST、CFG、PDG三种图叠加在一张属性图上Joern这类工具用的是CPG。PDG是CPG的一个子集讲原理时分开看更清楚。把边界划清楚后面聊算法和工具的时候才不会期待错位。我见过太多团队一上来就想用PDG做全程序精确分析最后卡在指针分析上动不了其实退一步做函数内切片效果已经很够用了。2. PDG的两根支柱控制依赖与数据依赖2.1 控制依赖用后支配边界定义谁决定谁执行先讲控制依赖这是PDG里最数学的一块也是最容易讲糊的一块。它的正式定义建立在**后支配post-dominance**之上。后支配的定义是从节点 v 到出口节点的每一条路径都经过节点 w就说 w 后支配 v。反过来如果没有其他后支配节点能夹在 w 和 v 之间w 就是 v 的立即后支配节点immediate post-dominator记作 ipdom(v)。出口节点本身天然后支配所有能到达出口的节点。有了 ipdom控制依赖的定义就干净了节点 Y 控制依赖于节点 X当且仅当存在 CFG 中的一条边 (X, B)使得 Y 在从 B 出发沿后支配树上行的路径上且 Y 不等于 ipdom(X)。换成大白话从 X 出来的某条边走走走路上碰到的第一个必然会到达出口的汇合点是 ipdom(X)那这条边到 ipdom(X) 之间被卡住的所有节点都得听 X 的。X 决定它们执不执行。拿一个具体例子对一下。if (a 0) { s1; s2; }这样的结构里s1、s2都控制依赖于那个if判断因为判断走真分支才会执行它们。而if后面的那条语句不受控制依赖约束——不管走哪个分支它都执行它后支配了if所以从if出来的边走到它就停了。这里有个常被忽略的细节循环的控制依赖。while (c) { s; }里s控制依赖于c这个判断没错但循环体本身还有个回边。回边的存在会让后支配关系变得微妙——循环里的节点如果存在break、continue或者异常出口后支配树的分支会更碎。我在实现切片工具的时候循环是最容易出错的区域后面第6章会专门讲。2.2 数据依赖从到达定值到def-use链数据依赖相对好理解本质是定义-使用关系def-use。节点 Y 数据依赖于节点 X条件是X 定义了变量 v存在一条从 X 到 Y 的路径路径上 v 没有被重新定义也就是 X 的定义到达了 Y而 Y 使用了 v。这里的到达就是经典数据流分析里的到达定值reaching definitions。它是个前向的、may分析并集运算的框架标准的工作表算法worklist就能求IN[B] ∪ OUT[P] for P in pred(B) OUT[B] gen[B] ∪ (IN[B] - kill[B])其中gen[B]是基本块 B 里被定义且能活着出去的定义集合kill[B]是 B 里被重新定义的那些定义集合。迭代到不动点为止。求出来之后对每个使用点看 IN 集合里有哪些定义到达了就给这些定义到使用点连一条数据依赖边。拿一段代码走一遍会更直观int compute(int a, int b) { int result 0; // D1: result 的定义 if (a 0) { // 用到 a result a b; // D2: result 的定义用到 a、b } else { result a - b; // D3: result 的定义用到 a、b } return result; // 用到 result }D1定义了result但它到return result的路径上必然经过D2或D3中的一个分支二选一但总有其一执行。所以D1被完全 kill 掉了return那里到达的只有D2和D3。数据依赖边就是D2 → return和D3 → return没有D1 → return。实操心得很多人第一次写到达定值时把 kill 写成了块内所有定义结果发现精度差很多。正确做法是只 kill 那些在块内被重新定义、且出口处仍然有效的定义。另外要注意gen和kill的顺序——如果同一个块里先x1再x2块内第一次定义不该出现在 OUT 里。数据依赖还有个容易漏的分支参数传入和返回值传出。在过程内PDG里形参一般建模成一个formal-in节点函数参数变量的使用点数据依赖于它返回值建模成formal-out。这样做的目的是让PDG在函数边界上是闭合的方便后续拼成SDG。2.3 边上的标签比节点更重要节点层面的信息量其实有限——基本块里是什么语句AST也能告诉你。PDG真正的信息增量在边上。所以我很建议在实现时给边打标签哪怕一开始只打粗粒度的。控制依赖边可以标注真分支假分支循环体循环退出数据依赖边可以标注变量名和定义/使用的位置。这些标签在后面做切片解释、生成人可读的影响报告时价值极大。我做过一个影响分析报告生成器输出第37行修改影响第108行原因是 result 变量经第54行传递这种可解释性直接决定了业务方愿不愿意用你的工具。表格对比一下两类边的差异方便记忆维度控制依赖边数据依赖边理论基础后支配关系到达定值 / def-use分析方向基于CFG反向图基于CFG前向数据流边语义X决定Y是否执行X定义的值被Y使用典型问句什么条件下这行才跑这个值从哪来、到哪去精度瓶颈循环、异常、多出口指针、数组、别名把这两类边放在同一张图上PDG就有了因果图的雏形。有意思的是控制依赖和数据依赖经常交织在一起一个变量在某个分支里被赋值这个赋值点的存在本身就受控制依赖约束而它又给下游贡献了数据依赖。做切片的时候必须同时考虑只追一种必然漏。3. 从源码到PDG一步步手搓一遍光讲定义容易飘我带着走一遍完整流程。为了控制篇幅用前面那段 C 代码降到三地址码级别来算。你按这个思路可以推到真实编译器中间表示IR上逻辑是一样的。3.1 第一步把源码降成三地址码并构建CFG先把源码降成线性化的三地址码这里的编号就是后面的节点号1: result 0 2: if a 0 goto 3 else goto 5 3: t1 a b 4: result t1; goto 7 5: t2 a - b 6: result t2; goto 7 7: ret result 8: exit对应的 CFG 边集合是1→2, 2→3, 2→5, 3→4, 4→7, 5→6, 6→7, 7→8。节点 8 是唯一的出口。注意降级到三地址码是必须的一步。直接在AST上算控制依赖也能做但AST有嵌套结构后支配的定义会变得很别扭。三地址码把嵌套拉平了后支配和到达定值都变成了标准的图论问题。这也是为什么主流工具LLVM IR、SOOT的Jimple、Joern的CPG都先做降级。降到这个粒度还有个好处每条语句最多一个定义SSA味道数据依赖的生成和 kill 规则变得极其简单——gen就是块内定义kill就是同名变量的其他定义。3.2 第二步反向图求后支配拿到立即后支配节点后支配有个很实用的性质在反向图把所有边方向翻转上出口节点 8 变成了入口后支配就等价于反向图上的支配。所以后支配树不用自己写算法直接对反向CFG跑一遍支配树算法就行。如果用 Python networkx核心就几行import networkx as nx def build_ipdom(cfg_edges, exit_node): cfg nx.DiGraph() cfg.add_edges_from(cfg_edges) rev cfg.reverse(copyTrue) idom nx.immediate_dominators(rev, exit_node) return idom对这段代码跑出来结果是这样节点ipdom88根78476734562712核对一下节点 3从 3 到 8 的路径只有3→4→7→8所以后支配 3 的节点是{4,7,8}其中离 3 最近的是 4对上了。节点 2 呢从 2 出发有两条路径2→3→4→7→8和2→5→6→7→8两条都经过的是{7,8}还有 2 自己所以 ipdom(2)7也对。实操心得networkx 的immediate_dominators用的是 Lengauer-Tarjan 的简化实现对小图够用。如果你的CFG有几万个节点建议换成迭代式或 Cooper-Harvey-Kennedy 算法实测在大型函数上能快一个数量级。另外要注意有出口不可达的节点比如死循环在反向图上算不出 idom得先做不可达节点剪枝否则会直接报错。3.3 第三步按算法扫边求控制依赖拿到 ipdom 之后控制依赖的标准算法就是扫一遍CFG的每条边对 CFG 中每条边 (A, B): 如果 B ipdom(A)跳过 否则从 runner B 开始: 如果 runner ipdom(A)停止 把 runner 记为控制依赖于 A runner ipdom(runner)翻译成 Pythondef control_deps(cfg_edges, ipdom): cd {} for a, b in cfg_edges: if b ipdom[a]: continue runner b while runner ! ipdom[a]: cd.setdefault(runner, set()).add(a) runner ipdom[runner] return cd在这段代码上跑一遍。边2→3ipdom(2)73 不等于 7从 3 开始——3 控制依赖于 2runner 变成 ipdom(3)44 不等于 74 也控制依赖于 2runner 变成 ipdom(4)7等于 ipdom(2)停。得到{3,4}控制依赖于 2。边2→5同理得到{5,6}控制依赖于 2。其他边比如1→2ipdom(1)2B 正好等于 ipdom(A)直接跳过节点2本来就无条件执行不受1控制。4→7和6→7也是同理跳过。最终控制依赖集合被控节点控制依赖于32425262这个结果符合直觉真分支和假分支里的语句都听if号令。3.4 第四步数据流分析求数据依赖接着算数据依赖。因为已经降成三地址码def 和 use 都很明确先用工作表算法求每个节点的 IN 集合。递推过程每轮迭代到不动点节点语句genkillIN到达的定义1result 0{1:result}{2,3,6:result}∅2if a0∅∅{1}3t1 a b{3:t1}∅{1}4result t1{4:result}{1,3,6:result}{1, 3}5t2 a - b{5:t2}∅{1}6result t2{6:result}{1,4,5:result}{1, 5}7ret result∅∅{4, 6}8exit∅∅{7}看第 4 行IN 里虽然有1:result但它自己又定义了一次 result所以定义 1 到这里就被吃掉了出去的时候不复存在。这就是为什么最后第 7 行拿到的 IN 是{4, 6}而不是{1, 4, 6}——分支汇合处两个定义都被保留了而初始定义被两条路径上的重新定义杀掉了。注意这里体现的是may分析并集也就是可能到达。如果你的场景需要必然到达must分析交集比如判断某个赋值是否在所有路径上都执行过那 IN 要用交集运算。做切片用 may 分析做优化用 must 分析别搞反。把 IN 集合翻译成数据依赖边就是对节点 Y 的每个 use把 IN[Y] 中定义该变量的定义节点 X 连一条边X → Y。结果如下使用点使用变量到达的定义数据依赖边2a形参 aformal_in_a → 23a, b形参formal_in_a → 3formal_in_b → 34t133 → 45a, b形参formal_in_a → 5formal_in_b → 56t255 → 67result4, 64 → 76 → 73.5 第五步合并、验证与可视化把控制依赖边和数据依赖边叠到同一张图上PDG 就成型了。节点还是那 8 个加两个形参节点边是两类边的并集。验证是必须的我一般用两个方法交叉检查。第一个是人工反推从节点 7 反向遍历所有依赖边应该能走到{4,6}再走一步到{3,5}再到形参{a,b}。这个集合应该正好覆盖影响返回值 result 的所有语句比 7 行代码减去无用行数量对得上。第二个是切片验证写个断言确认节点 1result0不在后向切片里——因为它确实被 kill 了。如果它出现了说明你的 kill 规则写错了这是新人最常犯的错。可视化方面我建议别依赖重型绘图库用 Graphviz 的 dot 直接出图就够dot -Tsvg pdg.dot -o pdg.svg控制依赖边用虚线styledashed数据依赖边用实线并标注变量名形参节点用不同形状。等你调试几十张图以后会发现能一眼看出哪条边是控制、哪条是数据效率翻倍。4. PDG在工程里的四大实战用法4.1 程序切片反向遍历就是后向切片程序切片是PDG最经典的用途定义来自 Weiser 那篇 1981 年的文章给定一个切片准则slicing criterion通常是一个语句加一个变量找出所有可能影响该点该变量取值的语句集合这就是后向切片反过来找被该点影响的集合是前向切片。在PDG上实现切片算法简单到有点朴素从准则节点出发沿着反向的依赖边做一次图遍历DFS或BFS都行遍历到的所有节点就是后向切片。前向切片则沿正向边遍历。不需要任何额外的数据流分析因为依赖关系已经在边上了。这个把分析问题变成图遍历问题的思路是PDG最大的价值。你要是用CFG做切片得在每个节点上跑一遍数据流方程复杂度高还得处理各种边界在PDG上就是一个nx.descendants的事。import networkx as nx def backward_slice(pdg, criterion_nodes): result set() for n in criterion_nodes: result | nx.descendants(pdg.reverse(copyFalse), n) return result实际用的时候有两个细节值得注意。第一切片准则的选择很关键同一个程序选不同准则切片大小能差好几倍我一般会结合业务语义选输出变量或状态变更点作为准则。第二切片粒度问题如果在语句级切片循环体会整体进来如果切片粒度太粗结果会大到没法看。我的经验是函数级别的切片结果超过原代码 70% 就要警惕往往说明准则选得不好或者依赖边太糊。4.2 变更影响分析改一行到底牵动多少代码这是我用得最多的场景。核心思路一句话把改动点当成切片准则做前向切片结果就是潜在影响范围。具体到工程落地我会分三步走。第一步把改动定位到具体节点这一步通常靠 diff 加 AST 匹配把行号映射到中间表示的节点号。映射这一步是最容易出错的因为宏展开、模板实例化、编译优化都会让行号漂移所以要基于编译前的源码做映射别用优化后的IR。第二步从改动节点出发做前向切片得到受影响节点集合。第三步把节点集合映射回源文件和行号生成人可读的报告。这里有个可以提高实用性的技巧给影响分等级。控制依赖和数据依赖的强度不一样——数据依赖是硬因果改了大概率真会变控制依赖是条件性的改了只是可能改变执行路径。我会在报告里把两者分开列数据依赖命中的标红控制依赖命中的标黄。业务方看这种分级报告接受度明显更高也不容易被你报了两百个文件这种数字吓到。再补一个踩坑经验跨文件的影响传播一定要用SDG。只在函数内做PDG你会漏掉改了这个函数的返回语义调用方全部受影响这种最典型的情况。SDG 里调用点通过call、parameter-in、parameter-out这几类特殊边连接起来做跨过程切片时沿这些边走就行。代价是图会大很多实测一个十万行项目建完整SDG内存能到几个G所以一般会做函数级别的按需展开on-demand而不是全量构建。4.3 缺陷定位与调试从崩溃点倒推可疑输入PDG在这块有个很直观的用法从崩溃点做后向切片缩小嫌疑范围。程序在某个点崩了传统做法是翻调用栈、打日志、二分定位。用PDG你可以把崩溃点作为准则做后向切片得到所有可能影响该点状态的语句然后把这些语句作为重点检查对象。这个思路在数据竞争、空指针、越界这类缺陷上特别有效。举个例子某次线上故障是一个空指针崩溃点在obj.field。做后向切片之后发现能影响obj的只有三条赋值路径其中两条明确做了判空第三条是从某个配置解析函数返回的。看一眼就知道问题在哪。整个过程几分钟。还有个进阶玩法是差值切片dicing。假设你有两个版本一个正常一个出错分别做切片取差集差集里的语句就是最可疑的改动。这个思路在回归测试失败定位上很实用。实现上要注意切片准则必须选在结果不同的那个可观测点上否则两个切片可能完全一样差集为空。实操心得切片结果不要直接给人看太抽象。我一般会把切片节点按源文件分组每组里按行号排序再标出节点之间的依赖路径。给同事看的时候直接说从 crash 点回溯这条链是 A→B→C最可疑的是 B 这行两个版本不一致对方秒懂。可视化不是锦上添花是让工具真正被用起来的关键。4.4 克隆检测与代码相似度PDG在代码克隆检测里也有位置。基于文本的克隆检测对变量重命名、语句重排很敏感稍微改一下就不认了基于PDG的检测把代码抽象成图再做子图同构或者图哈希对语法变体的容忍度高很多。常见做法是给每个PDG节点生成一个结构化签名比如归一化后的语句类型加操作符然后对图做 Weisfeiler-Lehman 之类的迭代哈希最终得到整张图的指纹。指纹接近就认为相似。另一种做法是做子图匹配找两个函数里同构的依赖子图用来发现复制粘贴后改了几个常量的代码。实际做的时候有两个坑。第一个是规模问题子图同构是NP难问题工业界一般退化为近似匹配或者先做候选筛选再精确匹配。第二个是归一化程度要调好归一化太弱等价代码认不出来归一化太强把不同业务语义的代码判成克隆误报一堆。我的经验是先只归一化变量名和字面量保留控制结构的差异误报率能降不少。5. 工具选型别一上来就自己造轮子5.1 主流开源方案横向对比新手最大的误区是从零手写PDG构建器。教学阶段可以练手生产环境一定要用成熟工具。常用的几类方案对比如下工具语言支持图类型优点局限LLVM / ClangC/C/Rust前端等IR上的CFG依赖需自建中间表示规整pass生态成熟依赖分析要自己写无现成PDGSOOT / JimpleJava/AndroidCFG、数据流、调用图分析框架完整学术积累深语法支持滞后于新版本JavaWALAJava/JSCFG、SDG、指针分析过程间分析强大SDG现成学习曲线陡文档偏少JoernC/C/Java/JS/Python等CPGASTCFGPDG查询语言友好跨语言精度对指针分析较弱CodeQL多语言数据库化语义图查询能力极强规则生态大许可限制自定义成本高选型建议按你的语言栈和精度要求走。做 C/C 且要精确指针分析LLVM 打底自己搭做 Java 生态SOOT 或 WALA 都行要现成SDG选 WALA做多语言扫描和快速原型Joern 上手最快。注意不要被支持多语言这个卖点带偏。跨语言工具的代价通常是每种语言的精度都不如专精工具。做安全审计看的是召回跨语言工具够用做编译器优化看的是准确必须用编译器中端自带的分析。5.2 用 Joern 跑出第一张图含命令如果你想今天就见到一张真实的PDG我推荐从 Joern 入手装好之后就能跑。基本流程是三步导入代码生成CPG、用查询语言取图、导出可视化。# 安装需先装好 JVM ./joern-install.sh --interactive # 生成 CPG joern-parse /path/to/source --output /tmp/cpg.bin # 进入交互式查询 joern --cpg /tmp/cpg.bin进入 Joern 的 shell 后可以直接查某个方法的控制依赖结构// 找到目标方法 val m cpg.method.name(compute).head // 打印其控制结构 m.controlStructure.lJoern 的 CPG 把 AST 边、CFG 边、依赖边都放在同一张属性图上用reachableBy这类原语就能做切片。导出到文件后用 Graphviz 或者自己写个脚本转成邻接表都可以。如果你想更原生地看到PDG我另一个推荐的路径是用 SOOT 的 Jimple 加它的DirectedGraph接口代码量大概三四百行就能把控制依赖和数据依赖都打出来。这条路的好处是每一步的计算你都能打断点看调试体验比黑盒工具好太多。5.3 自研PDG绕不开的三个矛盾即便有现成工具很多时候你还是得自研一部分比如嵌入式领域的私有语言、领域特定语言DSL。自研的时候有三组矛盾绕不开提前想清楚能省很多时间。第一组是规模与精度。全程序精确分析的结果是图爆炸你必须在某个地方做近似。我的建议是指针分析可以先做流不敏感flow-insensitive的快速版本拿到大致别名关系再对热点函数做流敏感的精确分析。分级处理比一次性追求极限精度务实得多。第二组是构建开销与查询开销。PDG可以在需要时按需构建查询哪个函数就建哪个也可以全量预构建。按需构建省内存但首次查询慢全量构建反之。IDE插件这类交互式场景选按需CI扫描这类批处理场景选全量。第三组是精度与可解释性。分析精度越高边越多报告越长用户越不想看。我的做法是在内部保留高精度图对外输出时做一次摘要只保留跨函数、跨文件、跨模块的边函数内的边折叠成一句函数内若干语句受影响。6. 踩坑实录与常见问题速查6.1 依赖边爆炸与图规模失控第一个大坑是边数失控。一个几千行的模块PDG边数轻松上万如果不做任何裁剪就扔给可视化工具出来的图是一团黑完全没法看。应对办法有三个层次。第一层是图结构裁剪去掉传递闭包能推出的冗余边。比如 A→B→C 和 A→C 同时存在时A→C 是冗余的可以删掉。这一步能把边数砍掉三成以上。第二层是查询时裁剪做切片时设深度上限或只保留跨文件的边。第三层是采样可视化展示时只画与准则相关的子图别画全图。还有个隐蔽的规模问题是循环体带来的冗余边。循环里的变量定义每轮迭代产生的到达关系可能被算成多条边实际上一轮的边就够了。如果做流敏感分析注意别把迭代次数展开成节点那样规模会失控。6.2 指针、数组、别名的精度黑洞第二个大坑是间接访问。*p 1定义了谁a[i] 1改了数组哪个元素obj.field 1改了哪个字段这些不解决数据依赖边就是残缺的。处理策略要分层。数组先做整数组一个符号的粗粒度处理如果发现精度不够比如循环里频繁读写同一数组的不同下标再上依赖测试dependence test做下标分析。指针要先做别名分析工程上常用的是基于类型和分配点的别名分类类似 LLVM 的AliasAnalysis接口分出肯定别名可能别名肯定不别名三档只对前两档建边。字段访问在面向对象语言里更复杂要考虑继承和动态派发。Java里obj.method()可能调到多个实现处理方法是对每个可能的实现都建一条跨过程的边然后在调用图层面做剪枝。注意别指望一步到位做出精确指针分析。学术上的精确算法复杂度高得离谱工程上都是够用就行。我在项目里用过一个很土的策略对局部变量和形参做精确跟踪对其他一律按可能别名处理实测覆盖了八成以上的真实场景剩下的靠人工复核。6.3 循环、异常与函数调用的特殊依赖第三个大坑是控制流的特殊结构。循环里的break、continue、多出口函数、异常处理块都会让后支配关系变得不符合直觉进而影响控制依赖的正确性。循环回边的处理关键是虚拟出口。如果一个循环可能不终止while(true)它在CFG上没有通往出口的路径后支配树的构建会失败。标准做法是给这类循环加一个虚拟的出口边指向一个虚拟出口节点让所有节点都能到达某个出口。异常处理块要单独建模。try-catch结构里catch 块控制依赖于可能抛异常的语句这条边的语义和普通分支不一样。很多工具为了简化直接忽略了异常边结果在做资源泄漏检测时大量漏报因为释放资源的语句被异常打断的影响追不出来。函数调用在过程内PDG上是黑洞——调用点看起来只定义了一个返回值但它可能通过全局变量、引用参数、副作用影响一大堆东西。做过程内分析时要把这些当作可能定义处理也就是保守地认为调用点 kill 了所有全局变量和引用参数指向的内存。这会让精度掉一大截但至少不会漏。6.4 常见问题速查表把上面这些坑整理成一张速查表出问题时对照着看现象可能原因排查方向处理建议切片结果几乎包含全程序指针/数组分析过粗边太密检查别名分析粒度加类型限定做流敏感优化切片漏掉本该影响的语句kill 规则过激或数据流不收敛手工验算 IN/OUT 集合检查块内定义顺序与 kill 集合后支配树构建失败存在不可达出口的节点找死循环和多出口函数引入虚拟出口节点控制依赖边缺失循环 break/continue 未处理检查回边与多出口单独建模跳转语句的控制效果影响报告越报越多跨过程边未剪枝检查 SDG 调用边只保留跨模块边函数内折叠行号映射错位宏展开或优化导致漂移用源码级而非优化IR映射在降级前建立行号映射表图构建耗时过长全量构建或指针分析太重打点看哪个阶段慢改按需构建热点函数精确化还有一条不算技术坑但很关键的经验先明确分析目标再选精度。做安全扫描看重召回宁可多报不能漏报边可以建得保守一些做自动重构看重精确宁可少报不能误改边必须精确。这两个目标的PDG实现细节完全不同一上来不定清楚后面返工的成本很高。最后分享一个我一直在用的小技巧给PDG的每条边加一个来源标签标记这条边是靠哪种分析得到的——是后支配算出来的控制依赖还是到达定值算出来的数据依赖还是别名分析推断出来的可能依赖。做问题排查时直接过滤可能依赖这类边看结果变化多大就能快速判断是不是别名分析的精度拖累了整体效果。这个方法帮我在好几个项目里几分钟定位到精度瓶颈比盲目优化算法参数高效得多。
程序依赖图PDG实战：控制依赖、数据依赖与程序切片
做程序分析这些年我手里最常用、也最容易被低估的一张图就是程序依赖图Program Dependence GraphPDG。很多刚入门程序分析的朋友学完控制流图CFG就觉得差不多了觉得一张流程图能看清分支和循环就够了。可真正上手做变更影响分析、程序切片、缺陷定位的时候你会发现CFG只能告诉你代码怎么走但回答不了改这一行到底会牵动哪些地方。PDG解决的正是后面这个问题它把控制依赖和数据依赖显式地画成边让谁决定谁执行谁的数据从谁来变成可以直接遍历的图结构。这篇文章我打算按我自己带新人的路子写先讲清楚PDG到底解决什么问题、它的能力边界在哪再把控制依赖和数据依赖这两根支柱拆开讲透包括后支配、到达定值这些背后的数学定义然后从一段十几行的C代码出发一步步手搓出一张PDG把每一步的计算过程和参数选择都写清楚接着聊它在工程里的四类真实用法再给出工具选型建议和可以直接抄的实操命令最后是我这些年踩过的坑和排查清单。不管你是刚接触程序分析的学生还是已经在做静态分析工具、代码审计、编译器优化的工程师应该都能从里面捞到点能直接用的东西。1. 为什么程序依赖图PDG值得单独拎出来讲1.1 从控制流图到依赖关系的认知跃迁我们先对齐一下概念。控制流图是把程序拆成基本块用有向边表示执行完这块可能跳到哪块。它的信息是可达性从入口能不能走到这个块、这个块之后可能去哪。但可达性是可能层面的它不区分这个块一定会执行和这个块可能执行。举个例子if (a 0) x 1; else x 2;这两条赋值语句在CFG里都只是分支的两个出口地位是对称的。可如果你想知道x 的最终值受谁影响你需要知道这两条语句各自在什么条件下才生效而且它们和后面的return x之间有一条数据流的因果链。CFG本身不表达这层因果它只表达顺序和跳转。PDG就是在这个缺口上补了一刀。它在CFG的基础上额外画出两类边控制依赖边表示X 的执行与否决定了 Y 是否执行数据依赖边表示Y 用到的某个值是由 X 定义的。节点还是那些语句或基本块但图的语义从怎么走升级成了谁影响谁。这一步升级看着简单但它把很多原本要靠人肉推理的问题变成了图上的可达性问题。我常跟新人打比方CFG是城市路网图告诉你怎么从A开到BPDG是供应链图告诉你哪个零件缺货会卡住哪条产线。路网图能帮你导航供应链图才能帮你做风险分析。做程序分析谁影响谁的问题占了绝大多数。1.2 一个真实场景为什么CFG回答不了改这行会影响谁假设你在维护一个老系统某天要改一个校验逻辑原本if (score 60)改成if (score 55)。你打开CFG看哦这是改了个分支条件跳转关系变了。但真正的问题是这行改动会不会让下游某个统计报表算错会不会让某个已经写过测试用例的接口行为变化CFG给不出答案因为阈值的具体数值在CFG里只是个表达式节点它看不到score是怎么一路被算出来、又怎么一路被消费掉的。而PDG里score的定义点会有一串数据依赖边指向所有用到它的地方score 60这个判断又会有一串控制依赖边指向它管辖的语句。你从改动点出发沿着这两类边走一遍走到哪里停影响范围就在哪里。这就是后向切片的雏形也是变更影响分析最朴素的实现方式。我在实际项目里做过一次统计一个中等规模的服务端模块改一个核心配置读取的默认值用CFG人工追影响范围大概要小半天还容易漏换成基于PDG的脚本扫一遍十几秒出结果命中二十多个文件其中有三个是人工追的时候压根没想到的间接依赖。这个差距不是效率问题是漏报问题。1.3 PDG的能力边界说法与实话讲完好处得泼点冷水。PDG不是万能的它的精度完全取决于前面的分析精度。具体说有三个天花板第一别名分析的精度决定了数据依赖的精度。C/C里int *p x; *p 1;这种间接写如果你不做指针分析就不知道它定义了x数据依赖边就丢了。Java里的字段访问、反射也是同一个问题。第二PDG是语句级的图粒度比AST粗。你想知道某个变量的某个位被改了PDG层面看不到得下沉到更细的表示比如SSA形式或值流图。第三过程间依赖需要额外扩展。标准的PDG是单个过程函数内的图跨函数的调用关系要靠System Dependence GraphSDG来表达SDG里多了调用点、形参实参的绑定边。很多人说PDG能看到跨函数影响其实说的是SDG。注意别把PDG和CPG搞混。CPGCode Property Graph是把AST、CFG、PDG三种图叠加在一张属性图上Joern这类工具用的是CPG。PDG是CPG的一个子集讲原理时分开看更清楚。把边界划清楚后面聊算法和工具的时候才不会期待错位。我见过太多团队一上来就想用PDG做全程序精确分析最后卡在指针分析上动不了其实退一步做函数内切片效果已经很够用了。2. PDG的两根支柱控制依赖与数据依赖2.1 控制依赖用后支配边界定义谁决定谁执行先讲控制依赖这是PDG里最数学的一块也是最容易讲糊的一块。它的正式定义建立在**后支配post-dominance**之上。后支配的定义是从节点 v 到出口节点的每一条路径都经过节点 w就说 w 后支配 v。反过来如果没有其他后支配节点能夹在 w 和 v 之间w 就是 v 的立即后支配节点immediate post-dominator记作 ipdom(v)。出口节点本身天然后支配所有能到达出口的节点。有了 ipdom控制依赖的定义就干净了节点 Y 控制依赖于节点 X当且仅当存在 CFG 中的一条边 (X, B)使得 Y 在从 B 出发沿后支配树上行的路径上且 Y 不等于 ipdom(X)。换成大白话从 X 出来的某条边走走走路上碰到的第一个必然会到达出口的汇合点是 ipdom(X)那这条边到 ipdom(X) 之间被卡住的所有节点都得听 X 的。X 决定它们执不执行。拿一个具体例子对一下。if (a 0) { s1; s2; }这样的结构里s1、s2都控制依赖于那个if判断因为判断走真分支才会执行它们。而if后面的那条语句不受控制依赖约束——不管走哪个分支它都执行它后支配了if所以从if出来的边走到它就停了。这里有个常被忽略的细节循环的控制依赖。while (c) { s; }里s控制依赖于c这个判断没错但循环体本身还有个回边。回边的存在会让后支配关系变得微妙——循环里的节点如果存在break、continue或者异常出口后支配树的分支会更碎。我在实现切片工具的时候循环是最容易出错的区域后面第6章会专门讲。2.2 数据依赖从到达定值到def-use链数据依赖相对好理解本质是定义-使用关系def-use。节点 Y 数据依赖于节点 X条件是X 定义了变量 v存在一条从 X 到 Y 的路径路径上 v 没有被重新定义也就是 X 的定义到达了 Y而 Y 使用了 v。这里的到达就是经典数据流分析里的到达定值reaching definitions。它是个前向的、may分析并集运算的框架标准的工作表算法worklist就能求IN[B] ∪ OUT[P] for P in pred(B) OUT[B] gen[B] ∪ (IN[B] - kill[B])其中gen[B]是基本块 B 里被定义且能活着出去的定义集合kill[B]是 B 里被重新定义的那些定义集合。迭代到不动点为止。求出来之后对每个使用点看 IN 集合里有哪些定义到达了就给这些定义到使用点连一条数据依赖边。拿一段代码走一遍会更直观int compute(int a, int b) { int result 0; // D1: result 的定义 if (a 0) { // 用到 a result a b; // D2: result 的定义用到 a、b } else { result a - b; // D3: result 的定义用到 a、b } return result; // 用到 result }D1定义了result但它到return result的路径上必然经过D2或D3中的一个分支二选一但总有其一执行。所以D1被完全 kill 掉了return那里到达的只有D2和D3。数据依赖边就是D2 → return和D3 → return没有D1 → return。实操心得很多人第一次写到达定值时把 kill 写成了块内所有定义结果发现精度差很多。正确做法是只 kill 那些在块内被重新定义、且出口处仍然有效的定义。另外要注意gen和kill的顺序——如果同一个块里先x1再x2块内第一次定义不该出现在 OUT 里。数据依赖还有个容易漏的分支参数传入和返回值传出。在过程内PDG里形参一般建模成一个formal-in节点函数参数变量的使用点数据依赖于它返回值建模成formal-out。这样做的目的是让PDG在函数边界上是闭合的方便后续拼成SDG。2.3 边上的标签比节点更重要节点层面的信息量其实有限——基本块里是什么语句AST也能告诉你。PDG真正的信息增量在边上。所以我很建议在实现时给边打标签哪怕一开始只打粗粒度的。控制依赖边可以标注真分支假分支循环体循环退出数据依赖边可以标注变量名和定义/使用的位置。这些标签在后面做切片解释、生成人可读的影响报告时价值极大。我做过一个影响分析报告生成器输出第37行修改影响第108行原因是 result 变量经第54行传递这种可解释性直接决定了业务方愿不愿意用你的工具。表格对比一下两类边的差异方便记忆维度控制依赖边数据依赖边理论基础后支配关系到达定值 / def-use分析方向基于CFG反向图基于CFG前向数据流边语义X决定Y是否执行X定义的值被Y使用典型问句什么条件下这行才跑这个值从哪来、到哪去精度瓶颈循环、异常、多出口指针、数组、别名把这两类边放在同一张图上PDG就有了因果图的雏形。有意思的是控制依赖和数据依赖经常交织在一起一个变量在某个分支里被赋值这个赋值点的存在本身就受控制依赖约束而它又给下游贡献了数据依赖。做切片的时候必须同时考虑只追一种必然漏。3. 从源码到PDG一步步手搓一遍光讲定义容易飘我带着走一遍完整流程。为了控制篇幅用前面那段 C 代码降到三地址码级别来算。你按这个思路可以推到真实编译器中间表示IR上逻辑是一样的。3.1 第一步把源码降成三地址码并构建CFG先把源码降成线性化的三地址码这里的编号就是后面的节点号1: result 0 2: if a 0 goto 3 else goto 5 3: t1 a b 4: result t1; goto 7 5: t2 a - b 6: result t2; goto 7 7: ret result 8: exit对应的 CFG 边集合是1→2, 2→3, 2→5, 3→4, 4→7, 5→6, 6→7, 7→8。节点 8 是唯一的出口。注意降级到三地址码是必须的一步。直接在AST上算控制依赖也能做但AST有嵌套结构后支配的定义会变得很别扭。三地址码把嵌套拉平了后支配和到达定值都变成了标准的图论问题。这也是为什么主流工具LLVM IR、SOOT的Jimple、Joern的CPG都先做降级。降到这个粒度还有个好处每条语句最多一个定义SSA味道数据依赖的生成和 kill 规则变得极其简单——gen就是块内定义kill就是同名变量的其他定义。3.2 第二步反向图求后支配拿到立即后支配节点后支配有个很实用的性质在反向图把所有边方向翻转上出口节点 8 变成了入口后支配就等价于反向图上的支配。所以后支配树不用自己写算法直接对反向CFG跑一遍支配树算法就行。如果用 Python networkx核心就几行import networkx as nx def build_ipdom(cfg_edges, exit_node): cfg nx.DiGraph() cfg.add_edges_from(cfg_edges) rev cfg.reverse(copyTrue) idom nx.immediate_dominators(rev, exit_node) return idom对这段代码跑出来结果是这样节点ipdom88根78476734562712核对一下节点 3从 3 到 8 的路径只有3→4→7→8所以后支配 3 的节点是{4,7,8}其中离 3 最近的是 4对上了。节点 2 呢从 2 出发有两条路径2→3→4→7→8和2→5→6→7→8两条都经过的是{7,8}还有 2 自己所以 ipdom(2)7也对。实操心得networkx 的immediate_dominators用的是 Lengauer-Tarjan 的简化实现对小图够用。如果你的CFG有几万个节点建议换成迭代式或 Cooper-Harvey-Kennedy 算法实测在大型函数上能快一个数量级。另外要注意有出口不可达的节点比如死循环在反向图上算不出 idom得先做不可达节点剪枝否则会直接报错。3.3 第三步按算法扫边求控制依赖拿到 ipdom 之后控制依赖的标准算法就是扫一遍CFG的每条边对 CFG 中每条边 (A, B): 如果 B ipdom(A)跳过 否则从 runner B 开始: 如果 runner ipdom(A)停止 把 runner 记为控制依赖于 A runner ipdom(runner)翻译成 Pythondef control_deps(cfg_edges, ipdom): cd {} for a, b in cfg_edges: if b ipdom[a]: continue runner b while runner ! ipdom[a]: cd.setdefault(runner, set()).add(a) runner ipdom[runner] return cd在这段代码上跑一遍。边2→3ipdom(2)73 不等于 7从 3 开始——3 控制依赖于 2runner 变成 ipdom(3)44 不等于 74 也控制依赖于 2runner 变成 ipdom(4)7等于 ipdom(2)停。得到{3,4}控制依赖于 2。边2→5同理得到{5,6}控制依赖于 2。其他边比如1→2ipdom(1)2B 正好等于 ipdom(A)直接跳过节点2本来就无条件执行不受1控制。4→7和6→7也是同理跳过。最终控制依赖集合被控节点控制依赖于32425262这个结果符合直觉真分支和假分支里的语句都听if号令。3.4 第四步数据流分析求数据依赖接着算数据依赖。因为已经降成三地址码def 和 use 都很明确先用工作表算法求每个节点的 IN 集合。递推过程每轮迭代到不动点节点语句genkillIN到达的定义1result 0{1:result}{2,3,6:result}∅2if a0∅∅{1}3t1 a b{3:t1}∅{1}4result t1{4:result}{1,3,6:result}{1, 3}5t2 a - b{5:t2}∅{1}6result t2{6:result}{1,4,5:result}{1, 5}7ret result∅∅{4, 6}8exit∅∅{7}看第 4 行IN 里虽然有1:result但它自己又定义了一次 result所以定义 1 到这里就被吃掉了出去的时候不复存在。这就是为什么最后第 7 行拿到的 IN 是{4, 6}而不是{1, 4, 6}——分支汇合处两个定义都被保留了而初始定义被两条路径上的重新定义杀掉了。注意这里体现的是may分析并集也就是可能到达。如果你的场景需要必然到达must分析交集比如判断某个赋值是否在所有路径上都执行过那 IN 要用交集运算。做切片用 may 分析做优化用 must 分析别搞反。把 IN 集合翻译成数据依赖边就是对节点 Y 的每个 use把 IN[Y] 中定义该变量的定义节点 X 连一条边X → Y。结果如下使用点使用变量到达的定义数据依赖边2a形参 aformal_in_a → 23a, b形参formal_in_a → 3formal_in_b → 34t133 → 45a, b形参formal_in_a → 5formal_in_b → 56t255 → 67result4, 64 → 76 → 73.5 第五步合并、验证与可视化把控制依赖边和数据依赖边叠到同一张图上PDG 就成型了。节点还是那 8 个加两个形参节点边是两类边的并集。验证是必须的我一般用两个方法交叉检查。第一个是人工反推从节点 7 反向遍历所有依赖边应该能走到{4,6}再走一步到{3,5}再到形参{a,b}。这个集合应该正好覆盖影响返回值 result 的所有语句比 7 行代码减去无用行数量对得上。第二个是切片验证写个断言确认节点 1result0不在后向切片里——因为它确实被 kill 了。如果它出现了说明你的 kill 规则写错了这是新人最常犯的错。可视化方面我建议别依赖重型绘图库用 Graphviz 的 dot 直接出图就够dot -Tsvg pdg.dot -o pdg.svg控制依赖边用虚线styledashed数据依赖边用实线并标注变量名形参节点用不同形状。等你调试几十张图以后会发现能一眼看出哪条边是控制、哪条是数据效率翻倍。4. PDG在工程里的四大实战用法4.1 程序切片反向遍历就是后向切片程序切片是PDG最经典的用途定义来自 Weiser 那篇 1981 年的文章给定一个切片准则slicing criterion通常是一个语句加一个变量找出所有可能影响该点该变量取值的语句集合这就是后向切片反过来找被该点影响的集合是前向切片。在PDG上实现切片算法简单到有点朴素从准则节点出发沿着反向的依赖边做一次图遍历DFS或BFS都行遍历到的所有节点就是后向切片。前向切片则沿正向边遍历。不需要任何额外的数据流分析因为依赖关系已经在边上了。这个把分析问题变成图遍历问题的思路是PDG最大的价值。你要是用CFG做切片得在每个节点上跑一遍数据流方程复杂度高还得处理各种边界在PDG上就是一个nx.descendants的事。import networkx as nx def backward_slice(pdg, criterion_nodes): result set() for n in criterion_nodes: result | nx.descendants(pdg.reverse(copyFalse), n) return result实际用的时候有两个细节值得注意。第一切片准则的选择很关键同一个程序选不同准则切片大小能差好几倍我一般会结合业务语义选输出变量或状态变更点作为准则。第二切片粒度问题如果在语句级切片循环体会整体进来如果切片粒度太粗结果会大到没法看。我的经验是函数级别的切片结果超过原代码 70% 就要警惕往往说明准则选得不好或者依赖边太糊。4.2 变更影响分析改一行到底牵动多少代码这是我用得最多的场景。核心思路一句话把改动点当成切片准则做前向切片结果就是潜在影响范围。具体到工程落地我会分三步走。第一步把改动定位到具体节点这一步通常靠 diff 加 AST 匹配把行号映射到中间表示的节点号。映射这一步是最容易出错的因为宏展开、模板实例化、编译优化都会让行号漂移所以要基于编译前的源码做映射别用优化后的IR。第二步从改动节点出发做前向切片得到受影响节点集合。第三步把节点集合映射回源文件和行号生成人可读的报告。这里有个可以提高实用性的技巧给影响分等级。控制依赖和数据依赖的强度不一样——数据依赖是硬因果改了大概率真会变控制依赖是条件性的改了只是可能改变执行路径。我会在报告里把两者分开列数据依赖命中的标红控制依赖命中的标黄。业务方看这种分级报告接受度明显更高也不容易被你报了两百个文件这种数字吓到。再补一个踩坑经验跨文件的影响传播一定要用SDG。只在函数内做PDG你会漏掉改了这个函数的返回语义调用方全部受影响这种最典型的情况。SDG 里调用点通过call、parameter-in、parameter-out这几类特殊边连接起来做跨过程切片时沿这些边走就行。代价是图会大很多实测一个十万行项目建完整SDG内存能到几个G所以一般会做函数级别的按需展开on-demand而不是全量构建。4.3 缺陷定位与调试从崩溃点倒推可疑输入PDG在这块有个很直观的用法从崩溃点做后向切片缩小嫌疑范围。程序在某个点崩了传统做法是翻调用栈、打日志、二分定位。用PDG你可以把崩溃点作为准则做后向切片得到所有可能影响该点状态的语句然后把这些语句作为重点检查对象。这个思路在数据竞争、空指针、越界这类缺陷上特别有效。举个例子某次线上故障是一个空指针崩溃点在obj.field。做后向切片之后发现能影响obj的只有三条赋值路径其中两条明确做了判空第三条是从某个配置解析函数返回的。看一眼就知道问题在哪。整个过程几分钟。还有个进阶玩法是差值切片dicing。假设你有两个版本一个正常一个出错分别做切片取差集差集里的语句就是最可疑的改动。这个思路在回归测试失败定位上很实用。实现上要注意切片准则必须选在结果不同的那个可观测点上否则两个切片可能完全一样差集为空。实操心得切片结果不要直接给人看太抽象。我一般会把切片节点按源文件分组每组里按行号排序再标出节点之间的依赖路径。给同事看的时候直接说从 crash 点回溯这条链是 A→B→C最可疑的是 B 这行两个版本不一致对方秒懂。可视化不是锦上添花是让工具真正被用起来的关键。4.4 克隆检测与代码相似度PDG在代码克隆检测里也有位置。基于文本的克隆检测对变量重命名、语句重排很敏感稍微改一下就不认了基于PDG的检测把代码抽象成图再做子图同构或者图哈希对语法变体的容忍度高很多。常见做法是给每个PDG节点生成一个结构化签名比如归一化后的语句类型加操作符然后对图做 Weisfeiler-Lehman 之类的迭代哈希最终得到整张图的指纹。指纹接近就认为相似。另一种做法是做子图匹配找两个函数里同构的依赖子图用来发现复制粘贴后改了几个常量的代码。实际做的时候有两个坑。第一个是规模问题子图同构是NP难问题工业界一般退化为近似匹配或者先做候选筛选再精确匹配。第二个是归一化程度要调好归一化太弱等价代码认不出来归一化太强把不同业务语义的代码判成克隆误报一堆。我的经验是先只归一化变量名和字面量保留控制结构的差异误报率能降不少。5. 工具选型别一上来就自己造轮子5.1 主流开源方案横向对比新手最大的误区是从零手写PDG构建器。教学阶段可以练手生产环境一定要用成熟工具。常用的几类方案对比如下工具语言支持图类型优点局限LLVM / ClangC/C/Rust前端等IR上的CFG依赖需自建中间表示规整pass生态成熟依赖分析要自己写无现成PDGSOOT / JimpleJava/AndroidCFG、数据流、调用图分析框架完整学术积累深语法支持滞后于新版本JavaWALAJava/JSCFG、SDG、指针分析过程间分析强大SDG现成学习曲线陡文档偏少JoernC/C/Java/JS/Python等CPGASTCFGPDG查询语言友好跨语言精度对指针分析较弱CodeQL多语言数据库化语义图查询能力极强规则生态大许可限制自定义成本高选型建议按你的语言栈和精度要求走。做 C/C 且要精确指针分析LLVM 打底自己搭做 Java 生态SOOT 或 WALA 都行要现成SDG选 WALA做多语言扫描和快速原型Joern 上手最快。注意不要被支持多语言这个卖点带偏。跨语言工具的代价通常是每种语言的精度都不如专精工具。做安全审计看的是召回跨语言工具够用做编译器优化看的是准确必须用编译器中端自带的分析。5.2 用 Joern 跑出第一张图含命令如果你想今天就见到一张真实的PDG我推荐从 Joern 入手装好之后就能跑。基本流程是三步导入代码生成CPG、用查询语言取图、导出可视化。# 安装需先装好 JVM ./joern-install.sh --interactive # 生成 CPG joern-parse /path/to/source --output /tmp/cpg.bin # 进入交互式查询 joern --cpg /tmp/cpg.bin进入 Joern 的 shell 后可以直接查某个方法的控制依赖结构// 找到目标方法 val m cpg.method.name(compute).head // 打印其控制结构 m.controlStructure.lJoern 的 CPG 把 AST 边、CFG 边、依赖边都放在同一张属性图上用reachableBy这类原语就能做切片。导出到文件后用 Graphviz 或者自己写个脚本转成邻接表都可以。如果你想更原生地看到PDG我另一个推荐的路径是用 SOOT 的 Jimple 加它的DirectedGraph接口代码量大概三四百行就能把控制依赖和数据依赖都打出来。这条路的好处是每一步的计算你都能打断点看调试体验比黑盒工具好太多。5.3 自研PDG绕不开的三个矛盾即便有现成工具很多时候你还是得自研一部分比如嵌入式领域的私有语言、领域特定语言DSL。自研的时候有三组矛盾绕不开提前想清楚能省很多时间。第一组是规模与精度。全程序精确分析的结果是图爆炸你必须在某个地方做近似。我的建议是指针分析可以先做流不敏感flow-insensitive的快速版本拿到大致别名关系再对热点函数做流敏感的精确分析。分级处理比一次性追求极限精度务实得多。第二组是构建开销与查询开销。PDG可以在需要时按需构建查询哪个函数就建哪个也可以全量预构建。按需构建省内存但首次查询慢全量构建反之。IDE插件这类交互式场景选按需CI扫描这类批处理场景选全量。第三组是精度与可解释性。分析精度越高边越多报告越长用户越不想看。我的做法是在内部保留高精度图对外输出时做一次摘要只保留跨函数、跨文件、跨模块的边函数内的边折叠成一句函数内若干语句受影响。6. 踩坑实录与常见问题速查6.1 依赖边爆炸与图规模失控第一个大坑是边数失控。一个几千行的模块PDG边数轻松上万如果不做任何裁剪就扔给可视化工具出来的图是一团黑完全没法看。应对办法有三个层次。第一层是图结构裁剪去掉传递闭包能推出的冗余边。比如 A→B→C 和 A→C 同时存在时A→C 是冗余的可以删掉。这一步能把边数砍掉三成以上。第二层是查询时裁剪做切片时设深度上限或只保留跨文件的边。第三层是采样可视化展示时只画与准则相关的子图别画全图。还有个隐蔽的规模问题是循环体带来的冗余边。循环里的变量定义每轮迭代产生的到达关系可能被算成多条边实际上一轮的边就够了。如果做流敏感分析注意别把迭代次数展开成节点那样规模会失控。6.2 指针、数组、别名的精度黑洞第二个大坑是间接访问。*p 1定义了谁a[i] 1改了数组哪个元素obj.field 1改了哪个字段这些不解决数据依赖边就是残缺的。处理策略要分层。数组先做整数组一个符号的粗粒度处理如果发现精度不够比如循环里频繁读写同一数组的不同下标再上依赖测试dependence test做下标分析。指针要先做别名分析工程上常用的是基于类型和分配点的别名分类类似 LLVM 的AliasAnalysis接口分出肯定别名可能别名肯定不别名三档只对前两档建边。字段访问在面向对象语言里更复杂要考虑继承和动态派发。Java里obj.method()可能调到多个实现处理方法是对每个可能的实现都建一条跨过程的边然后在调用图层面做剪枝。注意别指望一步到位做出精确指针分析。学术上的精确算法复杂度高得离谱工程上都是够用就行。我在项目里用过一个很土的策略对局部变量和形参做精确跟踪对其他一律按可能别名处理实测覆盖了八成以上的真实场景剩下的靠人工复核。6.3 循环、异常与函数调用的特殊依赖第三个大坑是控制流的特殊结构。循环里的break、continue、多出口函数、异常处理块都会让后支配关系变得不符合直觉进而影响控制依赖的正确性。循环回边的处理关键是虚拟出口。如果一个循环可能不终止while(true)它在CFG上没有通往出口的路径后支配树的构建会失败。标准做法是给这类循环加一个虚拟的出口边指向一个虚拟出口节点让所有节点都能到达某个出口。异常处理块要单独建模。try-catch结构里catch 块控制依赖于可能抛异常的语句这条边的语义和普通分支不一样。很多工具为了简化直接忽略了异常边结果在做资源泄漏检测时大量漏报因为释放资源的语句被异常打断的影响追不出来。函数调用在过程内PDG上是黑洞——调用点看起来只定义了一个返回值但它可能通过全局变量、引用参数、副作用影响一大堆东西。做过程内分析时要把这些当作可能定义处理也就是保守地认为调用点 kill 了所有全局变量和引用参数指向的内存。这会让精度掉一大截但至少不会漏。6.4 常见问题速查表把上面这些坑整理成一张速查表出问题时对照着看现象可能原因排查方向处理建议切片结果几乎包含全程序指针/数组分析过粗边太密检查别名分析粒度加类型限定做流敏感优化切片漏掉本该影响的语句kill 规则过激或数据流不收敛手工验算 IN/OUT 集合检查块内定义顺序与 kill 集合后支配树构建失败存在不可达出口的节点找死循环和多出口函数引入虚拟出口节点控制依赖边缺失循环 break/continue 未处理检查回边与多出口单独建模跳转语句的控制效果影响报告越报越多跨过程边未剪枝检查 SDG 调用边只保留跨模块边函数内折叠行号映射错位宏展开或优化导致漂移用源码级而非优化IR映射在降级前建立行号映射表图构建耗时过长全量构建或指针分析太重打点看哪个阶段慢改按需构建热点函数精确化还有一条不算技术坑但很关键的经验先明确分析目标再选精度。做安全扫描看重召回宁可多报不能漏报边可以建得保守一些做自动重构看重精确宁可少报不能误改边必须精确。这两个目标的PDG实现细节完全不同一上来不定清楚后面返工的成本很高。最后分享一个我一直在用的小技巧给PDG的每条边加一个来源标签标记这条边是靠哪种分析得到的——是后支配算出来的控制依赖还是到达定值算出来的数据依赖还是别名分析推断出来的可能依赖。做问题排查时直接过滤可能依赖这类边看结果变化多大就能快速判断是不是别名分析的精度拖累了整体效果。这个方法帮我在好几个项目里几分钟定位到精度瓶颈比盲目优化算法参数高效得多。
