程序分析里有一块基建性价比高到有点被低估程序依赖图PDG。有段时间我在做一个老 Java 项目的缺陷定位工具输入是一个失败的单元测试输出是可能相关的代码行。第一版我用调用图加文本搜索效果惨不忍睹——真正出事的那行跟测试方法之间隔了三层间接调用和四五个条件分支。换成在 PDG 上做后向切片之后同一个 case 的候选行数从两千多降到三十几行而且答案就在里面。PDG 的妙处在于它把路径这种带时间维度的东西压成了边这种静态结构。你不需要真的跑一遍程序就能回答这个变量的值可能从哪来改了这个赋值会影响谁。这篇内容我打算把它拆干净两条依赖边分别怎么算、构造流程哪一步最容易做错、切片器怎么写、真实项目里能拿来干什么、什么情况下不该自己造轮子。适合已经写过一点静态分析、但每次看到依赖两个字就含糊过去的同学。1. 两条边控制依赖与数据依赖的来龙去脉1.1 控制流图给了骨架却没给因果先明确一件事PDG 不是流程图换了身马甲。控制流图CFG描述的是执行顺序上能走到哪节点是语句或基本块边是跳转。拿一段最短的代码举例1 int f(int x) { 2 int y 0; 3 if (x 0) { 4 y 1; 5 } else { 6 y 2; 7 } 8 return y; 9 }它的 CFG 边是这样的起点终点含义23顺序执行34条件为真36条件为假48分支汇合68分支汇合到这一步CFG 能告诉你从 3 出发有两条路但它回答不了第 8 行 return 的 y到底可能是谁给的。你得自己动手枚举路径才能知道。而 PDG 直接把这件事变成查询从 8 出发沿着反向边走能到达 4 和 6走不到别的地方。所以 PDG 要补的就是两种因果信息谁决定了这行代码会不会执行控制依赖谁决定了这行代码用到的值从哪来数据依赖。这两类边一合并图就成型了。1.2 控制依赖靠后支配关系批量算出来控制依赖的定义绕不开后支配这个概念。节点 n 后支配post-dominate节点 m意思是从 m 出发到函数出口的每条路径都经过 n。注意是每一条只要有一条绕过就不算。有了后支配控制依赖的定义是这是 1987 年 Ferrante 那篇经典论文给的形式节点 Y 控制依赖于节点 X当且仅当存在一条从 X 到 Y 的路径使得 Y 后支配这条路径上除 X 外的所有节点并且 Y 不严格后支配 X。读起来费劲换成大白话X 是个分支点Y 是某条分支上不经过就出不去的节点。拿上面那段代码验证一下4 控制依赖于 3 吗从 3 到 4 的路径只有 3→44 后支配这条路径上除 3 以外的所有节点就 4 自己而且 4 并不后支配 3走 3→6→8 就避开了 4。成立。6 同理。8 控制依赖于谁不依赖任何节点——8 后支配 2、3、4、6它是汇合点不是被分支决定的点。这里有个高频踩坑点循环的后支配关系需要虚拟出口。像1: while(c) 2: body;这种结构2 的后支配关系会形成环如果不引入一个虚拟出口节点把所有自然出口和 return 都连到它上面迭代算后支配集的时候会不收敛。我早期写过一个不收敛的版本调试了两小时才发现是忘记加出口节点程序一直在扩集簇里转圈。1.3 数据依赖三种依赖PDG 只留一种数据依赖本身有三类很多人第一次接触时会把它们混成一个东西真依赖flow dependenceS1 定义了变量 vS2 使用了 v且从 S1 到 S2 的路径上没有 v 的其他定义。这是值的流动。反依赖anti-dependenceS1 先读 vS2 后写 v。这是顺序约束不是值传递。输出依赖output dependenceS1 和 S2 都写同一个 v。关键结论标准 PDG 只收真依赖和控制依赖反依赖和输出依赖不进图。原因在于 PDG 的目标是回答值的来源与去处也就是可达性反依赖和输出依赖描述的是这两条语句不能换顺序属于并行化和指令调度要关心的事那是另一支依赖图比如编译器的 Dependence Graph。举个例子说明哪些边会被保留1 a 1; // def a 2 b a 2; // use a, def b 3 a 5; // def a 4 c a b; // use a, use b真依赖1→2a、2→4b、3→4a。注意 1→4 这条不存在因为中间被 3 杀掉了。反依赖2→32 读 a3 写 a。输出依赖1→3。PDG 里最后只剩三条边。这个被后来的定义杀掉的机制术语叫到达定值reaching definitions是数据依赖计算的数学基础。它的方程很朴素OUT[B] GEN[B] ∪ (IN[B] − KILL[B]) IN[B] ∪ OUT[P] for P in pred(B)GEN 是这个节点产生的新定义KILL 是它覆盖掉的旧定义IN 是所有前驱的 OUT 求并。循环结构下要迭代到不动点好在定义域有限一定收敛——这一点比后支配那部分要让人省心得多。2. 从 AST 到 PDG构造流程逐步拆2.1 第一步永远是定粒度它决定了后面所有事在动手写代码之前先决定图的节点代表什么。这个决定比选什么语言、什么框架重要得多因为它同时影响精度和规模而且后期基本改不动。粒度节点数量级精度适合场景表达式级最大最高能区分同一语句内的依赖研究型分析、表达式级切片语句级大高绝大多数论文的默认选择缺陷定位、影响分析基本块级小一个量级左右中等块内语句被绑在一起大规模代码库的粗筛函数级最小低只能回答谁调用了谁架构级影响面评估我的经验是除非你明确知道节点数会成为瓶颈否则一律从语句级起步。基本块级看着省事但它会把a f(); b a 1;这种块内依赖直接吞掉切片结果会变得没法看。真正遇到规模问题时的正确做法是分级——先用函数级和调用图粗筛出可疑模块再对可疑模块跑语句级 PDG而不是一上来就全局降粒度。2.2 后支配树建好之后控制依赖是一批算出来的后支配集用迭代数据流算思路和上面那个到达定值一模一样只是图的走向反过来从出口往入口推。迭代收敛后每个节点都拿到一个后支配我的节点集合。接下来是立即后支配节点ipdom。这里有一个容易写错的地方ipdom 是严格后支配集合里后支配集最大的那个不是最小的。因为它对应的其实是反向图上的立即支配节点越靠近当前节点的后支配节点能后支配的点越多集合越大。我见过不少人在这里写成min图跑出来看着有边、切片结果却是错的非常隐蔽。控制依赖的批量算法是这样的def ipdom_map(pdom): ip {} for n, ds in pdom.items(): strict ds - {n} if not strict: ip[n] None else: # 立即后支配节点 严格后支配集合中后支配集最大的那个 ip[n] max(strict, keylambda x: len(pdom[x])) return ip def control_deps(cfg, pdom): ip ipdom_map(pdom) cd set() # (控制器, 被控制节点) for a, succs in cfg.succ.items(): for b in succs: if b in pdom[a]: # b 后支配 a说明这条边不是分支边 continue cur b while cur is not None and cur not in pdom[a]: cd.add((a, cur)) cur ip.get(cur) return cd逻辑只有两句对每条 CFG 边 a→b如果 b 不后支配 a那它就是一条分支边从 b 沿后支配树往上爬爬到第一个后支配 a 的节点就停爬过的节点全部控制依赖于 a。用这段代码跑 1.1 节那段 if-else会得到(3,4)和(3,6)两条控制依赖。跑那个 while 循环会得到(1,2)以及循环体内所有只在循环里执行的节点——这符合直觉循环体确实被循环条件管着。2.3 数据依赖要考虑覆盖赋值和循环回边数据依赖的计算走的是到达定值但在循环上要小心两件事。一是回边会让同一节点的定义绕回来迭代必须跑到不动点二是同一变量在循环里被多次定义时如果按节点粒度只保留一个定义点就会把跨迭代的依赖压扁。一个真实会翻车的例子for (i 0; i n; i) { sum sum a[i]; // sum 的定义既来自上一次迭代也来自循环前的初始化 }这里sum sum a[i]有一条指向自己的自依赖边loop-carried还有一条来自循环外sum 0的边。如果你的实现对节点内同时出现同名变量的读和写处理得草率自依赖这条边很容易丢。丢了的直接后果是切片时找不到循环前的初始化用户在工具里看到sum 的来源不明。我的处理办法很土但有效在计算 GEN/KILL 时把节点内的读操作定义成先读后写也就是 IN 集合先参与 USE 的解析再被 KILL 覆盖。这样自依赖和外部依赖都能保住。2.4 图合并之后先跑三个一致性检查PDG 建完不要急着切片先做这三项检查。这是我踩过几次坑之后固定下来的习惯基本能在五分钟内定位到九成的构造 bug节点数守恒PDG 的节点集合必须和 CFG 的节点集合完全一致。PDG 只加边不加点一旦数量对不上说明某一步把节点丢了或者在合并时去重了。边类型比例合理统计控制依赖边和真依赖边的数量比。如果控制依赖边异常地少比如接近 0基本可以断定后支配算错了或者出口节点没接好。反之如果控制依赖边占绝大多数且集中在少数几个节点上通常是循环没有正确收敛。抽样人工验证随机挑三条数据依赖边手工确认源点的定义确实能到达目标点且中间没有覆盖定义。这一步最耗时但最值因为前两项只能发现结构性错误语义错误只能靠抽查。3. 一个能跑的后向切片器写下来才算真懂3.1 用 Python 的 ast 模块把 CFG 搭起来构造 CFG 最省事的写法是延续节点风格写一个block(stmts, nxt)函数表示顺序执行这串语句执行完跳到 nxt从后往前折叠就能自动处理嵌套结构。import ast class CFG: def __init__(self): self.succ {} self.label {} self.stmt {} def node(self, nid, text, sNone): self.succ.setdefault(nid, set()) self.label[nid] text self.stmt[nid] s return nid def edge(self, a, b): self.succ[a].add(b) class Builder: def __init__(self, cfg): self.cfg cfg self.seq 0 def fresh(self): self.seq 1 return self.seq def block(self, stmts, nxt): cur nxt for s in reversed(stmts): cur self.stmt_node(s, cur) return cur def stmt_node(self, s, nxt): nid self.fresh() if isinstance(s, ast.If): self.cfg.node(nid, if ast.unparse(s.test), s) self.cfg.edge(nid, nxt) self.cfg.edge(nid, self.block(s.body, nxt)) if s.orelse: self.cfg.edge(nid, self.block(s.orelse, nxt)) return nid if isinstance(s, ast.While): self.cfg.node(nid, while ast.unparse(s.test), s) self.cfg.edge(nid, nxt) self.cfg.edge(nid, self.block(s.body, nid)) # 回边指回循环头 return nid self.cfg.node(nid, ast.unparse(s), s) self.cfg.edge(nid, nxt) return nid调用方式是先建一个EXIT虚拟节点然后entry Builder(cfg).block(tree.body, exit_id)。这个实现只覆盖顺序、if、while 三种结构for/break/continue/try 都得自己补但骨架是对的。3.2 把两类边装进同一张图数据依赖这边先用一个 visitor 收集每个节点定义了哪些变量、使用了哪些变量class DefUse(ast.NodeVisitor): def __init__(self): self.defs, self.uses set(), set() def visit_Name(self, node): if isinstance(node.ctx, ast.Store): self.defs.add(node.id) elif isinstance(node.ctx, ast.Load): self.uses.add(node.id)注意这里故意没处理属性访问和下标也就是a.b、arr[i]全部被忽略。这不是疏忽是有意为之字段和数组要正确处理需要指针分析和别名分析放到迷你版本里会把代码撑到三百行以上反而看不清 PDG 本身的结构。这也是我在实际项目里的策略——先用名字级的粗糙版本跑通全流程看清楚瓶颈在哪再针对性地上别名分析。拿到每个节点的定义集合后跑一遍到达定值的不动点迭代得到每个节点入口处的 IN 集合。IN 集合里每个变量对应的那个定义节点就是真依赖边的源点dd set() for n in nodes: for v in use_set[n]: if v in IN[n]: dd.add((IN[n][v], n)) # 定义点 - 使用点最后把control_deps()的结果和dd一起塞进一个邻接表PDG 就完工了。3.3 切片就是图的传递闭包后向切片的算法简单到有点不公平——就是反向图上的可达性def backward_slice(pdg, criteria): seen set(criteria) work list(criteria) while work: n work.pop() for p in pdg.pred.get(n, ()): if p not in seen: seen.add(p) work.append(p) return seen拿一段带干扰项的代码试试n int(input()) total 0 i 0 while i n: total total i i i 1 print(total) unused 42 distractor total * 2 n从print(total)出发做后向切片应该拿到这几点total相关的赋值、i相关的赋值、while判断节点因为total total i控制依赖于它、以及n的定义。unused 42和distractor一定不在切片里——前者跟 total 完全无关后者虽然用了 total但方向反了它依赖 totaltotal 不依赖它。我特意在样例里放了distractor因为它是最容易出问题的场景如果你不小心把依赖方向搞反了把 pred 写成 succ切片结果会莫名其妙包含下游的语句而且因为图还有连通性看起来不会报错只是结果大了一圈。这类 bug 靠肉眼很难发现必须靠这种带方向性的测试用例。3.4 用切片对比来定位问题切片真正有意思的用法是对比。假设有个函数在某个输入下结果异常你可以对正确路径和错误路径各切一次片取差集。差集里的节点数量通常很少而且是真正区分两种行为的关键语句。我在实际项目里做过一个类似的功能收集失败测试和通过测试的执行轨迹对每个测试崩溃点做切片然后把失败切片集合与通过切片集合做差。效果比单纯看切片好得多因为它自动过滤掉了所有两种情况下都执行的样板代码。这个思路本质上和增量调试是同一套逻辑只是用依赖关系替代了文本级的行删除试探。4. 切片在真实项目里的几个落点4.1 后向切片当聚焦镜从几千行到几十行最直接的用途就是缺陷定位。给一个失败断点或异常抛出点做后向切片然后把切片内的语句按行号排序输出成候选列表。关键在于切片之后还有一步过滤。纯切片会给出一堆技术上相关、实际上无关的语句比如日志打印、参数校验、边界检查。我的做法是给每个切片节点打一个简单权重参与算术运算或赋值链的权重高只做日志输出的权重低。按权重排序之后前二十行里命中真实原因的比例会明显提升。有个经验要分享切片入口点的选择比切片算法本身重要。选错了入口再精确的算法也救不回来。如果异常在一行代码上抛出入口点要选这行代码本身而不是包住它的 try 块——选 try 块会把所有其他分支的语句全部拉进来。4.2 前向切片做变更影响面评估改了某个函数的返回逻辑需要知道哪些地方会受影响。这时候用前向切片从改动点的赋值语句出发沿 PDG 的正向边遍历得到所有可能被波及的语句。单函数内的前向切片很快但它不够用因为影响会跨函数传播。我的组合方案分两步走先用调用图把范围从一个函数扩到所有直接和间接调用它的函数这一步是粗粒度的可能扩出几百个函数再对这些函数逐个做过程内的前向切片只用保留切片中含有敏感数据的那些。举个例子改动的是parse_config的返回值语义第一步用调用图找到 87 个调用者第二步对每个调用者做前向切片检查切片里是否包含对配置文件字段的读取。最后剩下来的是 6 个函数——这个数量级人眼是可以逐一看完的。4.3 切片指纹抗重命名的克隆检测这个用法知道的人不算多但很好使。思路是对每个方法出口做后向切片把切片内的语句按依赖拓扑序序列化成一个字符串再做哈希。生成的指纹有两个好性质一是对变量重命名免疫因为序列化时可以用占位符替代标识符二是对与控制流无关的语句插入免疫比如插了一行日志它不在切片里。要做严格的相似度匹配就不能只用哈希得算切片的编辑距离或者节点序列的最长公共子序列这样能容忍少量差异识别出改过几个常量的近似克隆。这里必须提醒一句切片相同不等于语义相同。切片是过近似的两条不同逻辑的语句在特定控制结构下可能切出一样的集合。所以这个技术适合当召回环节后面必须接人工或语义级的二次确认。我在项目里就把它定位成初筛之后再用符号执行或测试用例验证误报率才算可控。4.4 在 PDG 上做污点可达性安全方向的静态扫描本质上就是在 PDG 上找一条从外部输入到危险操作的路径。这类分析通常会把 PDG 和抽象语法树、CFG 融合成一张图——也就是常说的代码属性图然后在这张图上做可达性查询。PDG 在这里提供的是边但不提供值的形状。也就是说它能告诉你sql这个变量从request来但没法告诉你中间经过了拼接、截断还是转义。所以实际做的时候还要在边上挂条件经过类型转换的边要被标注经过已知净化函数的边要被打断。这些标注就是污点分析里sanitizer的来源。我个人的判断是如果你只是想快速验证一个数据流假设直接用现成的图数据库方案比自研 PDG 划算得多因为这些工具已经把净化函数标注、跨文件解析这些脏活处理好了。5. 精度与规模PDG 构造中的四个高频翻车点5.1 别名一断整条依赖链就没了这是最致命的问题。看这段 C 代码int a 1, b 2; int *p; if (cond) p a; else p b; *p 3; int c a b;如果按变量名做依赖分析*p 3这一行定义了哪个变量答案是不确定。如果这里处理成不知道那c的计算就丢失了来自*p的依赖边如果处理成可能指向 a 或 b那就要加上两条伪依赖边因为实际执行时只有一个成立。这就是别名分析的两难保守may-alias保证不漏但引入伪依赖激进must-alias保证不误但会漏掉真实依赖。PDG 构造里漏比误危险得多因为漏掉一条边切片就少一块使用者根本不知道自己的分析结果是不完整的。对策上我在项目里的默认选择是包含式inclusion-based的指针分析它对 C 这类语言精度够用复杂度也可以接受。数组下标别名则交给下标约束求解简单的等差下标用最大公约数判断就能覆盖大部分场景。5.2 循环折叠伪依赖和漏依赖同时出现经典 PDG 把循环处理成单次迭代折叠这在分析循环不变量时够用但在以下场景会出问题for (i 1; i n; i) { a[i] a[i - 1] 1; // 跨迭代依赖 }折叠之后a[i-1]和a[i]是两个不同的下标表达式按名字或简单下标匹配都找不到依赖关系。这条跨迭代依赖被漏掉了如果你用这个 PDG 去做并行化判断会得出循环可以并行的错误结论。反过来折叠也会造出伪依赖for (i 0; i n; i) { a[i] f(i); b[i] a[i] 1; }如果把循环体当成一个节点a[i] f(i)和b[i] a[i] 1之间的依赖是对的但同一节点内部跨迭代的a[i]写和a[i]读会被误判成冲突。实际执行时它们访问的是不同数组元素根本不存在依赖。处理办法按精度从低到高排一是把数组当作整体对象接受大量伪依赖二是做下标约束测试GCD test、区间分析能判断这两个下标是否可能相等三是上多面体模型处理仿射下标下的依赖关系。我的建议是别一开始就上多面体先用区间分析覆盖常见的i、i1、i-1情形性价比最高。5.3 粒度和规模的两难没有银弹前面提过粒度选择这里补充一个真实感受PDG 的边数在最坏情况下是节点数的平方级而实际代码里这个系数通常也不小。我做过一次统计一个中等规模的模块语句级 PDG 的边数是节点数的三倍左右控制依赖占了其中约三分之一。节点数上去之后切片本身还是线性的但人看不过来。所以规模问题的本质往往不是算力而是结果的可读性。这也是为什么我在实际工具里会给切片结果做二次压缩把连续的、依赖关系相同的语句合并成区间展示只在关键分叉点展开。用户看到的可能还是三十行但内部图的规模可能是它的十倍。5.4 跨过程不建图切片永远是残缺的过程内的 PDG 只能回答函数内部的问题。可现实中这个参数的值从哪来的答案往往在调用者那里改了这个返回值影响谁的答案在被调用的下游。跨过程的标准解法是系统依赖图SDG在 PDG 的基础上加上调用边、参数进边、参数出边。但直接上 SDG 会遇到一个棘手的规模问题——递归调用。如果切片时每次遇到调用点就展开被调函数递归一出现就会无限展开。解决办法是摘要边。它的思路是把被调函数的参数到返回值参数到参数的依赖关系预先算成一个摘要调用点直接引用摘要不展开函数体。这个做法最早在 1990 年的一篇经典论文里被系统化现在几乎所有实用的过程间切片工具都会用。我的实践体会是摘要边的正确性验证特别烦因为它隐藏了中间过程出错了很难定位。我在做的时候会给摘要边加一个调试开关打开后强制展开成普通边然后对比两种模式下的切片结果是否一致。这个对照测试帮我抓出过至少三个摘要计算错误。6. 工具选型什么时候该造轮子什么时候直接用6.1 常见框架的能力边界自研之前先看清楚市面上有什么。下面这张表是我自己踩过一遍之后总结的重点在输入是什么和图上能做多细框架主要输入图能力上手成本典型场景SootJava 字节码或源码Jimple 中间表示、CFGPDG 需要插件中Java 静态分析、教学演示WALAJava、JavaScriptCFG、调用图、SDG、指针分析高过程间切片、研究原型JoernC/C、Java、JavaScript、Python 等代码属性图也就是 AST、CFG、PDG 的融合中低漏洞挖掘、查询式分析CodeQL多语言关系型数据流与污点传播中安全审计、流水线集成SVFLLVM IR指针分析、值流图高C/C 的别名与依赖分析angr二进制CFG、中间表示、符号执行中高没有源码的场景LLVM 的依赖图库LLVM IR依赖图数据结构中自研优化与分析几个使用上的细节值得单独说WALA 的指针分析对 Java 这种有虚调用和反射的语言做了大量工程处理但它的 API 抽象层次偏低你得对控制流和数据流的概念本身很熟才能用得顺。Joern 的代码属性图把三种图合并了查询起来像写 SQL适合快速验证假设但如果你想定制切片算法本身它的可改空间不如直接操作底层图结构。6.2 我的取舍标准实际决策我基本只看三个问题。第一个问题你要的是用图还是改图。只是想拿依赖关系做点事比如找可疑数据流、做影响面评估那直接用 Joern 或 CodeQL别折腾。这些工具已经把跨文件解析、净化函数标注、查询语言这些基础设施都做好了自己从零搭一遍光是处理各种语言的语法边缘情况就能耗掉几个月。第二个问题分析对象有没有源码。有源码且是主流语言上面的选择都成立。如果只有二进制那基本只剩符号执行和二进制层面的图构建这条路而且精度会明显下降——间接跳转和虚调用在二进制层面很难恢复。这时候要降低预期别指望得到和源码级分析一样的切片质量。第三个问题你的分析目标是文本级还是语义级。如果只是想找这个函数名在哪被调用正则加 grep 就够了上 PDG 是杀鸡用牛刀。只有当你要回答这个值能不能流到那个地方改这里会影响哪些行为的时候依赖图才有不可替代的价值。对我自己来说造轮子只在两种情况下合理一是要做研究需要修改切片算法本身二是目标语言太小众现成工具完全不支持。除此之外我都建议先拿现成工具跑一版结果出来看清楚真正的瓶颈在哪——很多时候你以为需要更精确的 PDG实际上需要的是更好的结果排序。最后分享一个我自己反复验证过的小技巧在动手给 PDG 加各种高级特性之前先用它做一个最笨的用途——回答这行代码依赖哪几行。把这个问题在真实项目里跑通、跑准你对依赖图的理解会比读十篇论文扎实得多。我当初就是卡在一个distractor变量上盯着切片结果看了半小时才发现方向搞反了那种原来是这样的瞬间比任何理论推导都管用。
程序依赖图PDG与后向切片：从依赖分析到缺陷定位实战
程序分析里有一块基建性价比高到有点被低估程序依赖图PDG。有段时间我在做一个老 Java 项目的缺陷定位工具输入是一个失败的单元测试输出是可能相关的代码行。第一版我用调用图加文本搜索效果惨不忍睹——真正出事的那行跟测试方法之间隔了三层间接调用和四五个条件分支。换成在 PDG 上做后向切片之后同一个 case 的候选行数从两千多降到三十几行而且答案就在里面。PDG 的妙处在于它把路径这种带时间维度的东西压成了边这种静态结构。你不需要真的跑一遍程序就能回答这个变量的值可能从哪来改了这个赋值会影响谁。这篇内容我打算把它拆干净两条依赖边分别怎么算、构造流程哪一步最容易做错、切片器怎么写、真实项目里能拿来干什么、什么情况下不该自己造轮子。适合已经写过一点静态分析、但每次看到依赖两个字就含糊过去的同学。1. 两条边控制依赖与数据依赖的来龙去脉1.1 控制流图给了骨架却没给因果先明确一件事PDG 不是流程图换了身马甲。控制流图CFG描述的是执行顺序上能走到哪节点是语句或基本块边是跳转。拿一段最短的代码举例1 int f(int x) { 2 int y 0; 3 if (x 0) { 4 y 1; 5 } else { 6 y 2; 7 } 8 return y; 9 }它的 CFG 边是这样的起点终点含义23顺序执行34条件为真36条件为假48分支汇合68分支汇合到这一步CFG 能告诉你从 3 出发有两条路但它回答不了第 8 行 return 的 y到底可能是谁给的。你得自己动手枚举路径才能知道。而 PDG 直接把这件事变成查询从 8 出发沿着反向边走能到达 4 和 6走不到别的地方。所以 PDG 要补的就是两种因果信息谁决定了这行代码会不会执行控制依赖谁决定了这行代码用到的值从哪来数据依赖。这两类边一合并图就成型了。1.2 控制依赖靠后支配关系批量算出来控制依赖的定义绕不开后支配这个概念。节点 n 后支配post-dominate节点 m意思是从 m 出发到函数出口的每条路径都经过 n。注意是每一条只要有一条绕过就不算。有了后支配控制依赖的定义是这是 1987 年 Ferrante 那篇经典论文给的形式节点 Y 控制依赖于节点 X当且仅当存在一条从 X 到 Y 的路径使得 Y 后支配这条路径上除 X 外的所有节点并且 Y 不严格后支配 X。读起来费劲换成大白话X 是个分支点Y 是某条分支上不经过就出不去的节点。拿上面那段代码验证一下4 控制依赖于 3 吗从 3 到 4 的路径只有 3→44 后支配这条路径上除 3 以外的所有节点就 4 自己而且 4 并不后支配 3走 3→6→8 就避开了 4。成立。6 同理。8 控制依赖于谁不依赖任何节点——8 后支配 2、3、4、6它是汇合点不是被分支决定的点。这里有个高频踩坑点循环的后支配关系需要虚拟出口。像1: while(c) 2: body;这种结构2 的后支配关系会形成环如果不引入一个虚拟出口节点把所有自然出口和 return 都连到它上面迭代算后支配集的时候会不收敛。我早期写过一个不收敛的版本调试了两小时才发现是忘记加出口节点程序一直在扩集簇里转圈。1.3 数据依赖三种依赖PDG 只留一种数据依赖本身有三类很多人第一次接触时会把它们混成一个东西真依赖flow dependenceS1 定义了变量 vS2 使用了 v且从 S1 到 S2 的路径上没有 v 的其他定义。这是值的流动。反依赖anti-dependenceS1 先读 vS2 后写 v。这是顺序约束不是值传递。输出依赖output dependenceS1 和 S2 都写同一个 v。关键结论标准 PDG 只收真依赖和控制依赖反依赖和输出依赖不进图。原因在于 PDG 的目标是回答值的来源与去处也就是可达性反依赖和输出依赖描述的是这两条语句不能换顺序属于并行化和指令调度要关心的事那是另一支依赖图比如编译器的 Dependence Graph。举个例子说明哪些边会被保留1 a 1; // def a 2 b a 2; // use a, def b 3 a 5; // def a 4 c a b; // use a, use b真依赖1→2a、2→4b、3→4a。注意 1→4 这条不存在因为中间被 3 杀掉了。反依赖2→32 读 a3 写 a。输出依赖1→3。PDG 里最后只剩三条边。这个被后来的定义杀掉的机制术语叫到达定值reaching definitions是数据依赖计算的数学基础。它的方程很朴素OUT[B] GEN[B] ∪ (IN[B] − KILL[B]) IN[B] ∪ OUT[P] for P in pred(B)GEN 是这个节点产生的新定义KILL 是它覆盖掉的旧定义IN 是所有前驱的 OUT 求并。循环结构下要迭代到不动点好在定义域有限一定收敛——这一点比后支配那部分要让人省心得多。2. 从 AST 到 PDG构造流程逐步拆2.1 第一步永远是定粒度它决定了后面所有事在动手写代码之前先决定图的节点代表什么。这个决定比选什么语言、什么框架重要得多因为它同时影响精度和规模而且后期基本改不动。粒度节点数量级精度适合场景表达式级最大最高能区分同一语句内的依赖研究型分析、表达式级切片语句级大高绝大多数论文的默认选择缺陷定位、影响分析基本块级小一个量级左右中等块内语句被绑在一起大规模代码库的粗筛函数级最小低只能回答谁调用了谁架构级影响面评估我的经验是除非你明确知道节点数会成为瓶颈否则一律从语句级起步。基本块级看着省事但它会把a f(); b a 1;这种块内依赖直接吞掉切片结果会变得没法看。真正遇到规模问题时的正确做法是分级——先用函数级和调用图粗筛出可疑模块再对可疑模块跑语句级 PDG而不是一上来就全局降粒度。2.2 后支配树建好之后控制依赖是一批算出来的后支配集用迭代数据流算思路和上面那个到达定值一模一样只是图的走向反过来从出口往入口推。迭代收敛后每个节点都拿到一个后支配我的节点集合。接下来是立即后支配节点ipdom。这里有一个容易写错的地方ipdom 是严格后支配集合里后支配集最大的那个不是最小的。因为它对应的其实是反向图上的立即支配节点越靠近当前节点的后支配节点能后支配的点越多集合越大。我见过不少人在这里写成min图跑出来看着有边、切片结果却是错的非常隐蔽。控制依赖的批量算法是这样的def ipdom_map(pdom): ip {} for n, ds in pdom.items(): strict ds - {n} if not strict: ip[n] None else: # 立即后支配节点 严格后支配集合中后支配集最大的那个 ip[n] max(strict, keylambda x: len(pdom[x])) return ip def control_deps(cfg, pdom): ip ipdom_map(pdom) cd set() # (控制器, 被控制节点) for a, succs in cfg.succ.items(): for b in succs: if b in pdom[a]: # b 后支配 a说明这条边不是分支边 continue cur b while cur is not None and cur not in pdom[a]: cd.add((a, cur)) cur ip.get(cur) return cd逻辑只有两句对每条 CFG 边 a→b如果 b 不后支配 a那它就是一条分支边从 b 沿后支配树往上爬爬到第一个后支配 a 的节点就停爬过的节点全部控制依赖于 a。用这段代码跑 1.1 节那段 if-else会得到(3,4)和(3,6)两条控制依赖。跑那个 while 循环会得到(1,2)以及循环体内所有只在循环里执行的节点——这符合直觉循环体确实被循环条件管着。2.3 数据依赖要考虑覆盖赋值和循环回边数据依赖的计算走的是到达定值但在循环上要小心两件事。一是回边会让同一节点的定义绕回来迭代必须跑到不动点二是同一变量在循环里被多次定义时如果按节点粒度只保留一个定义点就会把跨迭代的依赖压扁。一个真实会翻车的例子for (i 0; i n; i) { sum sum a[i]; // sum 的定义既来自上一次迭代也来自循环前的初始化 }这里sum sum a[i]有一条指向自己的自依赖边loop-carried还有一条来自循环外sum 0的边。如果你的实现对节点内同时出现同名变量的读和写处理得草率自依赖这条边很容易丢。丢了的直接后果是切片时找不到循环前的初始化用户在工具里看到sum 的来源不明。我的处理办法很土但有效在计算 GEN/KILL 时把节点内的读操作定义成先读后写也就是 IN 集合先参与 USE 的解析再被 KILL 覆盖。这样自依赖和外部依赖都能保住。2.4 图合并之后先跑三个一致性检查PDG 建完不要急着切片先做这三项检查。这是我踩过几次坑之后固定下来的习惯基本能在五分钟内定位到九成的构造 bug节点数守恒PDG 的节点集合必须和 CFG 的节点集合完全一致。PDG 只加边不加点一旦数量对不上说明某一步把节点丢了或者在合并时去重了。边类型比例合理统计控制依赖边和真依赖边的数量比。如果控制依赖边异常地少比如接近 0基本可以断定后支配算错了或者出口节点没接好。反之如果控制依赖边占绝大多数且集中在少数几个节点上通常是循环没有正确收敛。抽样人工验证随机挑三条数据依赖边手工确认源点的定义确实能到达目标点且中间没有覆盖定义。这一步最耗时但最值因为前两项只能发现结构性错误语义错误只能靠抽查。3. 一个能跑的后向切片器写下来才算真懂3.1 用 Python 的 ast 模块把 CFG 搭起来构造 CFG 最省事的写法是延续节点风格写一个block(stmts, nxt)函数表示顺序执行这串语句执行完跳到 nxt从后往前折叠就能自动处理嵌套结构。import ast class CFG: def __init__(self): self.succ {} self.label {} self.stmt {} def node(self, nid, text, sNone): self.succ.setdefault(nid, set()) self.label[nid] text self.stmt[nid] s return nid def edge(self, a, b): self.succ[a].add(b) class Builder: def __init__(self, cfg): self.cfg cfg self.seq 0 def fresh(self): self.seq 1 return self.seq def block(self, stmts, nxt): cur nxt for s in reversed(stmts): cur self.stmt_node(s, cur) return cur def stmt_node(self, s, nxt): nid self.fresh() if isinstance(s, ast.If): self.cfg.node(nid, if ast.unparse(s.test), s) self.cfg.edge(nid, nxt) self.cfg.edge(nid, self.block(s.body, nxt)) if s.orelse: self.cfg.edge(nid, self.block(s.orelse, nxt)) return nid if isinstance(s, ast.While): self.cfg.node(nid, while ast.unparse(s.test), s) self.cfg.edge(nid, nxt) self.cfg.edge(nid, self.block(s.body, nid)) # 回边指回循环头 return nid self.cfg.node(nid, ast.unparse(s), s) self.cfg.edge(nid, nxt) return nid调用方式是先建一个EXIT虚拟节点然后entry Builder(cfg).block(tree.body, exit_id)。这个实现只覆盖顺序、if、while 三种结构for/break/continue/try 都得自己补但骨架是对的。3.2 把两类边装进同一张图数据依赖这边先用一个 visitor 收集每个节点定义了哪些变量、使用了哪些变量class DefUse(ast.NodeVisitor): def __init__(self): self.defs, self.uses set(), set() def visit_Name(self, node): if isinstance(node.ctx, ast.Store): self.defs.add(node.id) elif isinstance(node.ctx, ast.Load): self.uses.add(node.id)注意这里故意没处理属性访问和下标也就是a.b、arr[i]全部被忽略。这不是疏忽是有意为之字段和数组要正确处理需要指针分析和别名分析放到迷你版本里会把代码撑到三百行以上反而看不清 PDG 本身的结构。这也是我在实际项目里的策略——先用名字级的粗糙版本跑通全流程看清楚瓶颈在哪再针对性地上别名分析。拿到每个节点的定义集合后跑一遍到达定值的不动点迭代得到每个节点入口处的 IN 集合。IN 集合里每个变量对应的那个定义节点就是真依赖边的源点dd set() for n in nodes: for v in use_set[n]: if v in IN[n]: dd.add((IN[n][v], n)) # 定义点 - 使用点最后把control_deps()的结果和dd一起塞进一个邻接表PDG 就完工了。3.3 切片就是图的传递闭包后向切片的算法简单到有点不公平——就是反向图上的可达性def backward_slice(pdg, criteria): seen set(criteria) work list(criteria) while work: n work.pop() for p in pdg.pred.get(n, ()): if p not in seen: seen.add(p) work.append(p) return seen拿一段带干扰项的代码试试n int(input()) total 0 i 0 while i n: total total i i i 1 print(total) unused 42 distractor total * 2 n从print(total)出发做后向切片应该拿到这几点total相关的赋值、i相关的赋值、while判断节点因为total total i控制依赖于它、以及n的定义。unused 42和distractor一定不在切片里——前者跟 total 完全无关后者虽然用了 total但方向反了它依赖 totaltotal 不依赖它。我特意在样例里放了distractor因为它是最容易出问题的场景如果你不小心把依赖方向搞反了把 pred 写成 succ切片结果会莫名其妙包含下游的语句而且因为图还有连通性看起来不会报错只是结果大了一圈。这类 bug 靠肉眼很难发现必须靠这种带方向性的测试用例。3.4 用切片对比来定位问题切片真正有意思的用法是对比。假设有个函数在某个输入下结果异常你可以对正确路径和错误路径各切一次片取差集。差集里的节点数量通常很少而且是真正区分两种行为的关键语句。我在实际项目里做过一个类似的功能收集失败测试和通过测试的执行轨迹对每个测试崩溃点做切片然后把失败切片集合与通过切片集合做差。效果比单纯看切片好得多因为它自动过滤掉了所有两种情况下都执行的样板代码。这个思路本质上和增量调试是同一套逻辑只是用依赖关系替代了文本级的行删除试探。4. 切片在真实项目里的几个落点4.1 后向切片当聚焦镜从几千行到几十行最直接的用途就是缺陷定位。给一个失败断点或异常抛出点做后向切片然后把切片内的语句按行号排序输出成候选列表。关键在于切片之后还有一步过滤。纯切片会给出一堆技术上相关、实际上无关的语句比如日志打印、参数校验、边界检查。我的做法是给每个切片节点打一个简单权重参与算术运算或赋值链的权重高只做日志输出的权重低。按权重排序之后前二十行里命中真实原因的比例会明显提升。有个经验要分享切片入口点的选择比切片算法本身重要。选错了入口再精确的算法也救不回来。如果异常在一行代码上抛出入口点要选这行代码本身而不是包住它的 try 块——选 try 块会把所有其他分支的语句全部拉进来。4.2 前向切片做变更影响面评估改了某个函数的返回逻辑需要知道哪些地方会受影响。这时候用前向切片从改动点的赋值语句出发沿 PDG 的正向边遍历得到所有可能被波及的语句。单函数内的前向切片很快但它不够用因为影响会跨函数传播。我的组合方案分两步走先用调用图把范围从一个函数扩到所有直接和间接调用它的函数这一步是粗粒度的可能扩出几百个函数再对这些函数逐个做过程内的前向切片只用保留切片中含有敏感数据的那些。举个例子改动的是parse_config的返回值语义第一步用调用图找到 87 个调用者第二步对每个调用者做前向切片检查切片里是否包含对配置文件字段的读取。最后剩下来的是 6 个函数——这个数量级人眼是可以逐一看完的。4.3 切片指纹抗重命名的克隆检测这个用法知道的人不算多但很好使。思路是对每个方法出口做后向切片把切片内的语句按依赖拓扑序序列化成一个字符串再做哈希。生成的指纹有两个好性质一是对变量重命名免疫因为序列化时可以用占位符替代标识符二是对与控制流无关的语句插入免疫比如插了一行日志它不在切片里。要做严格的相似度匹配就不能只用哈希得算切片的编辑距离或者节点序列的最长公共子序列这样能容忍少量差异识别出改过几个常量的近似克隆。这里必须提醒一句切片相同不等于语义相同。切片是过近似的两条不同逻辑的语句在特定控制结构下可能切出一样的集合。所以这个技术适合当召回环节后面必须接人工或语义级的二次确认。我在项目里就把它定位成初筛之后再用符号执行或测试用例验证误报率才算可控。4.4 在 PDG 上做污点可达性安全方向的静态扫描本质上就是在 PDG 上找一条从外部输入到危险操作的路径。这类分析通常会把 PDG 和抽象语法树、CFG 融合成一张图——也就是常说的代码属性图然后在这张图上做可达性查询。PDG 在这里提供的是边但不提供值的形状。也就是说它能告诉你sql这个变量从request来但没法告诉你中间经过了拼接、截断还是转义。所以实际做的时候还要在边上挂条件经过类型转换的边要被标注经过已知净化函数的边要被打断。这些标注就是污点分析里sanitizer的来源。我个人的判断是如果你只是想快速验证一个数据流假设直接用现成的图数据库方案比自研 PDG 划算得多因为这些工具已经把净化函数标注、跨文件解析这些脏活处理好了。5. 精度与规模PDG 构造中的四个高频翻车点5.1 别名一断整条依赖链就没了这是最致命的问题。看这段 C 代码int a 1, b 2; int *p; if (cond) p a; else p b; *p 3; int c a b;如果按变量名做依赖分析*p 3这一行定义了哪个变量答案是不确定。如果这里处理成不知道那c的计算就丢失了来自*p的依赖边如果处理成可能指向 a 或 b那就要加上两条伪依赖边因为实际执行时只有一个成立。这就是别名分析的两难保守may-alias保证不漏但引入伪依赖激进must-alias保证不误但会漏掉真实依赖。PDG 构造里漏比误危险得多因为漏掉一条边切片就少一块使用者根本不知道自己的分析结果是不完整的。对策上我在项目里的默认选择是包含式inclusion-based的指针分析它对 C 这类语言精度够用复杂度也可以接受。数组下标别名则交给下标约束求解简单的等差下标用最大公约数判断就能覆盖大部分场景。5.2 循环折叠伪依赖和漏依赖同时出现经典 PDG 把循环处理成单次迭代折叠这在分析循环不变量时够用但在以下场景会出问题for (i 1; i n; i) { a[i] a[i - 1] 1; // 跨迭代依赖 }折叠之后a[i-1]和a[i]是两个不同的下标表达式按名字或简单下标匹配都找不到依赖关系。这条跨迭代依赖被漏掉了如果你用这个 PDG 去做并行化判断会得出循环可以并行的错误结论。反过来折叠也会造出伪依赖for (i 0; i n; i) { a[i] f(i); b[i] a[i] 1; }如果把循环体当成一个节点a[i] f(i)和b[i] a[i] 1之间的依赖是对的但同一节点内部跨迭代的a[i]写和a[i]读会被误判成冲突。实际执行时它们访问的是不同数组元素根本不存在依赖。处理办法按精度从低到高排一是把数组当作整体对象接受大量伪依赖二是做下标约束测试GCD test、区间分析能判断这两个下标是否可能相等三是上多面体模型处理仿射下标下的依赖关系。我的建议是别一开始就上多面体先用区间分析覆盖常见的i、i1、i-1情形性价比最高。5.3 粒度和规模的两难没有银弹前面提过粒度选择这里补充一个真实感受PDG 的边数在最坏情况下是节点数的平方级而实际代码里这个系数通常也不小。我做过一次统计一个中等规模的模块语句级 PDG 的边数是节点数的三倍左右控制依赖占了其中约三分之一。节点数上去之后切片本身还是线性的但人看不过来。所以规模问题的本质往往不是算力而是结果的可读性。这也是为什么我在实际工具里会给切片结果做二次压缩把连续的、依赖关系相同的语句合并成区间展示只在关键分叉点展开。用户看到的可能还是三十行但内部图的规模可能是它的十倍。5.4 跨过程不建图切片永远是残缺的过程内的 PDG 只能回答函数内部的问题。可现实中这个参数的值从哪来的答案往往在调用者那里改了这个返回值影响谁的答案在被调用的下游。跨过程的标准解法是系统依赖图SDG在 PDG 的基础上加上调用边、参数进边、参数出边。但直接上 SDG 会遇到一个棘手的规模问题——递归调用。如果切片时每次遇到调用点就展开被调函数递归一出现就会无限展开。解决办法是摘要边。它的思路是把被调函数的参数到返回值参数到参数的依赖关系预先算成一个摘要调用点直接引用摘要不展开函数体。这个做法最早在 1990 年的一篇经典论文里被系统化现在几乎所有实用的过程间切片工具都会用。我的实践体会是摘要边的正确性验证特别烦因为它隐藏了中间过程出错了很难定位。我在做的时候会给摘要边加一个调试开关打开后强制展开成普通边然后对比两种模式下的切片结果是否一致。这个对照测试帮我抓出过至少三个摘要计算错误。6. 工具选型什么时候该造轮子什么时候直接用6.1 常见框架的能力边界自研之前先看清楚市面上有什么。下面这张表是我自己踩过一遍之后总结的重点在输入是什么和图上能做多细框架主要输入图能力上手成本典型场景SootJava 字节码或源码Jimple 中间表示、CFGPDG 需要插件中Java 静态分析、教学演示WALAJava、JavaScriptCFG、调用图、SDG、指针分析高过程间切片、研究原型JoernC/C、Java、JavaScript、Python 等代码属性图也就是 AST、CFG、PDG 的融合中低漏洞挖掘、查询式分析CodeQL多语言关系型数据流与污点传播中安全审计、流水线集成SVFLLVM IR指针分析、值流图高C/C 的别名与依赖分析angr二进制CFG、中间表示、符号执行中高没有源码的场景LLVM 的依赖图库LLVM IR依赖图数据结构中自研优化与分析几个使用上的细节值得单独说WALA 的指针分析对 Java 这种有虚调用和反射的语言做了大量工程处理但它的 API 抽象层次偏低你得对控制流和数据流的概念本身很熟才能用得顺。Joern 的代码属性图把三种图合并了查询起来像写 SQL适合快速验证假设但如果你想定制切片算法本身它的可改空间不如直接操作底层图结构。6.2 我的取舍标准实际决策我基本只看三个问题。第一个问题你要的是用图还是改图。只是想拿依赖关系做点事比如找可疑数据流、做影响面评估那直接用 Joern 或 CodeQL别折腾。这些工具已经把跨文件解析、净化函数标注、查询语言这些基础设施都做好了自己从零搭一遍光是处理各种语言的语法边缘情况就能耗掉几个月。第二个问题分析对象有没有源码。有源码且是主流语言上面的选择都成立。如果只有二进制那基本只剩符号执行和二进制层面的图构建这条路而且精度会明显下降——间接跳转和虚调用在二进制层面很难恢复。这时候要降低预期别指望得到和源码级分析一样的切片质量。第三个问题你的分析目标是文本级还是语义级。如果只是想找这个函数名在哪被调用正则加 grep 就够了上 PDG 是杀鸡用牛刀。只有当你要回答这个值能不能流到那个地方改这里会影响哪些行为的时候依赖图才有不可替代的价值。对我自己来说造轮子只在两种情况下合理一是要做研究需要修改切片算法本身二是目标语言太小众现成工具完全不支持。除此之外我都建议先拿现成工具跑一版结果出来看清楚真正的瓶颈在哪——很多时候你以为需要更精确的 PDG实际上需要的是更好的结果排序。最后分享一个我自己反复验证过的小技巧在动手给 PDG 加各种高级特性之前先用它做一个最笨的用途——回答这行代码依赖哪几行。把这个问题在真实项目里跑通、跑准你对依赖图的理解会比读十篇论文扎实得多。我当初就是卡在一个distractor变量上盯着切片结果看了半小时才发现方向搞反了那种原来是这样的瞬间比任何理论推导都管用。
