1. 先搞清楚 PDG 到底解决什么问题1.1 从一次“改一行崩三处”的事故说起程序分析这四个字听起来很学术但落到日常里其实特别具体。我做过程序依赖图Program Dependence GraphPDG相关的工具链最初动机特别朴素一个函数里改了一行赋值回归测试挂了三个不相干的用例而这三个用例从调用关系上根本看不出跟那行代码有什么联系。人工翻代码翻了半天才发现是某个全局缓存被那一行间接改了后面几个模块读到的是脏数据。如果你也遇到过类似的场景那你其实已经在手工做程序依赖分析了只是没把它图论化。PDG 要做的事情就是把“谁影响谁执行”“谁影响谁的取值”这两类关系全部显式地画成一张有向图。节点是程序里的语句或基本块边是依赖关系。有了这张图你能回答的问题就变得非常具体改了这一句哪些代码的执行路径会变哪一段代码参与了崩溃变量的值计算这段死代码是不是真的永远不会被执行很多人第一次听到 PDG 会把它跟抽象语法树AST搞混。AST 描述的是代码长什么样——语法结构、嵌套关系PDG 描述的是代码怎么动——执行的先后、数值的流动。前者是静态的骨架照片后者是动态的因果网络。这个区别决定了它们能回答完全不同的两类问题。PDG 适合谁来用我的经验是三类人获益最大一是做静态分析工具、代码扫描器的工程同学PDG 是你绕不开的中间表示二是做编译器优化、JIT 的开发者切片和指令调度都依赖它三是接手工遗留系统、需要评估改动风险的业务开发者。前两类是刚需第三类属于“学会了能省大量加班时间”的技能。1.2 控制依赖与数据依赖PDG 的两根骨架PDG 之所以叫“依赖”图是因为它把程序语义拆成了两种最基本的约束。第一种是控制依赖Control Dependence。直观理解语句 B 是否执行取决于语句 A 的判断结果那么 B 控制依赖于 A。比如if (x 0) { y 1; }那y 1这条语句是否执行完全由x 0这个判断决定所以它控制依赖于这个条件判断。注意控制依赖描述的是一种“是否执行”的依赖不是“执行几次”的依赖。第二种是数据依赖Data Dependence。直观理解语句 B 用到的一个值是语句 A 算出来并写进去的那么 B 数据依赖于 A。比如a 3; b a 1;第二条语句读的a来自第一条语句的写入这就是一条典型的流依赖Flow Dependence。数据依赖本身还能细分成三类流依赖先写后读、反依赖先读后写、输出依赖先写后写。前一类是真正的“值传递”后两类更多是并发和重排序时需要关注的次序约束。把这两类边叠加到同一张图上就是 PDG。它的力量在于任何一条可能的因果链你都能在图上沿着边走一遍找出来。程序切片、变更影响分析、死代码检测这些任务的本质都是在 PDG 上做可达性搜索——从某个节点出发正向或反向走一遍边得到的就是被影响或被依赖的代码集合。我个人的判断是理解 PDG 的关键不在于记住定义而在于想明白“为什么需要两种依赖而不是一种”。因为程序的语义本身就是“控制流决定执行顺序 数据流决定取值来源”这两层缺了任何一层分析结果都会失真。只看数据依赖你会以为if分支里的赋值和else分支里的赋值是同一层的只看控制依赖你根本不知道变量从哪来。1.3 有了 AST 和 CFG为什么还要 PDG这是新人问得最多的问题值得认真回答因为它直接决定了你要不要投入时间学 PDG。AST 的问题在于它只表达语法层级。你从 AST 上能看出b a 1是某函数的第二个语句但看不出这个a是从哪里来的。做代码搜索、格式化、重构时 AST 够用做语义分析就不够了。CFG控制流图比 AST 强它把语句按执行顺序连起来分支、循环都变成了边。但 CFG 有一个致命局限它把所有可能的执行路径都平铺在一张图里边的数量随分支数量指数增长。一个嵌套十层的if结构CFG 上就是上千条路径。更麻烦的是CFG 只告诉你怎么走不告诉你值的来源。你想知道“变量 v 的取值可能来自哪里”在 CFG 上必须自己写数据流方程迭代求解。PDG 的价值就是把这两层信息一次性固化下来。它不展开所有路径而是用控制依赖边把“分支与此分支内语句”的关系直接连上用数据依赖边把“定义点与使用点”直接连上。图规模从路径级降到了语句级查询效率完全不是一个量级。实测下来一个几万行的模块CFG 上的路径枚举基本做不下去但 PDG 的节点数就是语句数边数通常在语句数的 1.5 到 3 倍之间规模是完全可控的。提示如果你的分析任务只涉及单条语句内的表达式变换AST 就够了一旦涉及跨语句、跨分支的语义关联请直接上 PDG不要试图在 CFG 上打补丁。还有一个容易被忽略的点PDG 是天然适合做“反向查询”的结构。业务场景里我们更常问的是“谁影响了这一行”而不是“这一行影响了谁”。反向走数据依赖边就是经典的程序切片方向。CFG 上做反向查询极其别扭因为边的方向是按执行顺序定义的。这一点在实际工具开发中会反复体现出来。2. PDG 的节点、边与构建原理拆解2.1 节点粒度语句级、基本块级还是表达式级选择节点粒度是构建 PDG 的第一个决策它直接影响图的规模和分析精度我踩过这个坑先说结论默认选基本块级需要高精度时局部降到语句级。语句级节点最好理解一个语句就是一个节点依赖关系直观。问题是循环体里几十条语句会产生大量细碎的边图规模膨胀得很快。我统计过一个约 1500 行的 C 文件语句级 PDG 大概是 1100 个节点、2800 条边人工看基本没戏。基本块级是把连续无分支的语句合并成一个节点。上面的例子合并后大约 320 个节点、700 条边规模降了一个量级代价是块内的依赖关系被压缩掉了。做变更影响分析、切片这种粗粒度任务基本块级完全够用。表达式级是最细的把a b c拆成t1 b、t2 c、t3 t1 t2、a t3这样的三地址码形式。好处是数据依赖极其精确坏处是节点数暴涨且中间变量是编译器造出来的跟源码行号对不上给用户看报告时会很痛苦。下面这张表是我实践中的经验值可以直接参考粒度典型节点规模精度适合的任务主要痛点函数级极小很低模块耦合分析内部依赖全丢失基本块级中等中变更影响、粗切片块内信息压缩语句级大中高缺陷检测、污点分析图规模膨胀表达式级极大高编译器优化行号映射困难我通常的做法是做一个“混合粒度”函数入口、分支判断、循环判断、函数调用这些关键语句单独成节点其余顺序语句合并成块。这样既保住了控制依赖的准确性又控制了规模。这个策略不是理论上的最优解但工程上性价比最高。2.2 控制依赖怎么算后支配树加路径条件控制依赖有严格的形式化定义不是拍脑袋定的。标准定义是节点 Y 控制依赖于节点 X当且仅当满足两个条件——存在一条从 X 到出口的路径不经过 Y即 Y 不后支配 X且 X 的所有其他后继都后支配 Y。这个定义第一次读会有点绕我用自己的话翻译一遍。第一步先算后支配关系如果从某个节点出发无论走哪条路最终都会经过节点 P那么 P 后支配这个节点。后支配关系可以组织成一棵树叫后支配树。第二步找那些“分叉点”后继如果一个判断语句的某个分支最终会汇聚到某节点 P而另一个分支不会那么这个分支内的语句就控制依赖于这个判断。实际算法分三步走我用代码说明每一步在干什么。第一步构造 CFG 并把所有边反向得到反向图。def build_reverse_cfg(cfg): rev {n: set() for n in cfg} for u, succs in cfg.items(): for v in succs: rev[v].add(u) return rev第二步在反向图上从虚拟出口节点做支配点计算。支配点用的是经典迭代算法初始化时假设每个节点被所有节点支配然后不断收缩集合直到收敛。def compute_dominators(nodes, preds, entry): dom {n: set(nodes) for n in nodes} dom[entry] {entry} changed True while changed: changed False for n in nodes: if n entry: continue ps preds[n] if not ps: continue common set.intersection(*(dom[p] for p in ps)) new_dom common | {n} if new_dom ! dom[n]: dom[n] new_dom changed True return dom第三步把支配关系取反就得到后支配关系再按“直接后支配”的定义提取出后支配树的父子边。有了后支配树控制依赖就可以直接读出来遍历 CFG 的每条边 (X, Y)如果 Y 不是 X 的直接后支配节点的祖先关系中的那个节点就把 Y 所在的子树里、直到 X 的直接后支配节点为止的所有节点标记为控制依赖 X。这个描述有点抽象实操中我建议直接用标准算法实现别自己简化简化版本在循环和break语句上几乎必错。循环上的控制依赖要特别小心。for (i 0; i n; i)循环体控制依赖于循环条件判断这个没问题。但循环条件本身又依赖于循环变量的更新循环变量更新又在循环体内。这形成了一个环。PDG 允许有环但在做切片的时候必须处理环否则搜索会死循环。我的做法是在切片算法里维护一个已访问集合遇到已访问节点直接剪枝。2.3 数据依赖怎么算到达定值分析数据依赖的计算本质上是回答一个问题在语句 T 用到的变量 v它的值可能是由哪些语句写进去的解决这个问题的标准方法是到达定值分析Reaching Definitions。每条赋值语句视为一个“定值点”分析的目标是求出每个程序点上哪些定值点可能到达即从该定值点出发到当前点中间没有被新的定值杀死。用数据流方程表达转移函数OUT[B] GEN[B] ∪ (IN[B] - KILL[B])汇合操作IN[B] ∪ OUT[P]P 是 B 的所有前驱其中GEN[B]是块 B 中产生的定值KILL[B]是块 B 中杀掉的、针对同一变量的其他定值。这个方程用迭代法求解因为是单调框架一定能收敛。def reaching_definitions(blocks, gen, kill, preds, entry): in_sets {b: set() for b in blocks} out_sets {b: set() for b in blocks} changed True while changed: changed False for b in blocks: if b ! entry: merged set() for p in preds[b]: merged | out_sets[p] in_sets[b] merged new_out gen[b] | (in_sets[b] - kill[b]) if new_out ! out_sets[b]: out_sets[b] new_out changed True return in_sets, out_sets算完到达定值后构造数据依赖边就很简单了对每条使用变量 v 的语句 T找到所有能到达 T 的 v 的定值点 S连一条 S → T 的流依赖边。同时如果 T 本身也定义了 v或者有别的语句定义了 v 且与 T 的读取点交错就产生反依赖和输出依赖边。这里有个实操细节同一语句内部的自依赖要过滤掉。i i 1这条语句左边定义的i和右边使用的i是两个不同的定值/使用事件如果不过滤会自己连自己图上看很别扭。正确做法是在语句内部先处理“读取时可见的定值”即右侧的i用的是语句执行前的旧值这个旧值来自之前某个定值点不是本条语句。另一个细节是变量重命名。同一个变量名在不同作用域可能是不同实体如果前端解析没做好作用域绑定会出现张冠李戴的依赖边。这个坑我在处理 C 模板代码时踩得很惨模板实例化前后变量名相同但类型不同必须靠符号表拿到唯一 ID 才能正确构图。2.4 过程间 PDG跨函数的那条线怎么连单函数 PDG 只能解决函数内部的因果分析真实工程里最有价值的问题几乎都跨函数这个接口参数被哪些下游代码改过这个返回值影响了哪些调用点过程间扩展有两个主流思路。第一个是内联展开Inlining。把被调函数直接展开到调用点然后就变成了单函数 PDG 问题。优点是分析精度最高缺点是在递归调用和深层调用链上会爆炸。我一般给内联设一个深度上限比如 3 到 5 层超过就用摘要替代。第二个是函数摘要Function Summary。为每个函数预先计算一份摘要描述“这个函数读取了哪些外部变量”“写了哪些外部变量”“返回值依赖哪些参数”。调用点用摘要来连边不需要展开函数体。摘要的好处是可缓存、可复用适合大规模代码。坏处是精度受摘要表达能力限制比如函数内部的条件分支会丢失摘要只能给出“可能影响”这种保守结论。我实际做工具时用的是混合策略调用深度浅、函数体小的直接内联调用深度深、被反复调用的用摘要。可以用一个简单的启发式规则决定条件策略理由函数体小于 50 行且无递归内联精度高成本可接受被调用点超过 10 个用摘要避免重复展开存在递归强制摘要防止无限展开涉及虚函数或多态调用保守连边到所有可能实现精度换正确性过程间连边的具体做法是在调用点 C把实际参数节点连到形参节点实参到形参的流依赖在函数返回点 R把返回值节点连回调用点 C返回值到调用点的流依赖如果有全局变量或引用参数被修改还需要从函数所有出口连一条边回到调用点的后继。引用参数是最麻烦的因为它是双向的读写都要连边而且必须区分“函数执行前”和“函数执行后”两个视角。注意过程间分析如果用摘要务必在报告里标注“可能依赖”。保守的假阳性结果在缺陷检测里可以接受但在自动重构场景下可能造成误改这是两个完全不同的风险等级。3. 动手实现一套可用的 PDG 原型怎么搭3.1 工具选型自己写还是用现成框架先说我的结论学习阶段自己写生产阶段用成熟框架。自己写的价值在于PDG 的每个环节——CFG 构造、后支配树、到达定值——你都会亲手实现一遍之后看任何框架的输出都不会有黑箱感。而且教学性质的实现代码量其实不大核心逻辑三百行左右就能跑通一个支持基本控制结构和局部变量的版本。成熟框架这边我常用的有这几类。针对 Java 生态的 Soot 是老牌选择它的 CFG 和过程间分析做得很扎实缺点是构建时间长、对新版 Java 语法支持偶有滞后。Joern 更适合做代码属性图CPG方向的查询它把 AST、CFG、PDG 融合成一张图用图查询语言写规则特别方便适合做安全扫描规则。Python 生态里如果你只处理 Python 代码直接基于ast模块加自己实现的数据流分析往往比引入重型框架更快。选型时我最看重的三个维度语言支持你的目标代码库是什么语言框架能不能正确解析边界语法这决定了是能用还是不能用。扩展性能不能方便地加入自定义分析规则比如你自己的污点源点定义。Soot 和 Joern 都支持但接入成本不同。可解释性输出的依赖边能不能定位回源码行号这直接决定了报告能不能给用户看。框架支持语言上手难度适合场景自研任意中学习、定制化分析SootJava/Android中高Java 程序分析Joern多语言中安全规则、代码查询WALAJava高学术级过程间分析我个人在做过几个项目后的体会是不要一开始就上重型框架。先用自研版本把流程跑通明确自己的分析目标到底需要什么精度再决定引入哪个框架来补足。很多情况下我们真正需要的是语句级的数据依赖根本用不上框架里的过程间全程序分析能力上重型框架纯属杀鸡用牛刀。3.2 第一步源码到 CFGCFG 构造是所有后续分析的地基这一步错了后面全错。我用一段具体代码来说明整个构造过程int sum(int n) { int s 0; for (int i 1; i n; i) { if (i % 2 0) { s i; } } return s; }构造 CFG 的关键是把控制结构拆解成基本块加跳转边。上面这段的块划分是B0s 0; i 1B1i n循环条件B2i % 2 0条件判断B3s iB4iB5return s边的关系是B0 → B1B1 → B2真、B1 → B5假B2 → B3真、B2 → B4假B3 → B4B4 → B1。构造时有两个容易出错的地方。第一是循环条件的求值位置C 语言的for循环条件在每轮迭代开始时求值所以条件是独立的块不是循环体的第一部分。第二是**break和continue的边**break应该连到循环的出口块continue连到循环的更新块这两条边如果连错控制依赖会全乱。我用的构建方法是递归下降解析语句序列遇到if递归处理两个分支并接后续块遇到while把条件块和体块组成环。这个思路对结构化语言都能覆盖遇到goto这种非结构化控制流就只能老老实实做标签到块的映射靠后处理补边。3.3 第二步后支配树与控制依赖有了 CFG控制依赖计算就是前面 2.2 节算法的直接应用。这里补充几个实操层面的注意点。虚拟出口节点的处理很关键。函数可能有多个return语句直接算后支配会因为出口不唯一而得不到正确结果。标准做法是加一个虚拟出口节点 E所有return和抛出异常的语句都连向 E然后在包含 E 的图上做后支配分析。E 本身不参与任何依赖关系只是为了让后支配树有唯一的根。后支配树的构建我建议直接用 Lengauer-Tarjan 算法虽然实现稍复杂但复杂度接近线性比朴素迭代快得多。如果只是学习用朴素的迭代求支配集也能跑就是在大函数上慢一些。控制依赖边提取时我见过最常见的错误是把循环回边也当成控制依赖。循环体控制依赖于循环条件这是对的但循环条件不控制依赖于循环体虽然循环变量的更新在循环体内。区分的方法是严格的“不后支配”判定循环条件块 B1 被 B4 反向边连回来B1 的另一个后继是出口 B5B5 不经过 B2/B3/B4所以 B2 到 B4 这一串控制依赖于 B1。而 B1 自己不满足这个条件因为它被所有路径经过吗不是从 B0 直接到 B1 再到 B5 的路径不经过 B2所以 B2 控制依赖于 B1方向是对的反过来不成立。这段逻辑说的时候容易绕实际实现时只要严格按定义走不做任何“优化简化”结果就是对的。我一开始为了省事用“分支内所有语句都控制依赖判断语句”这种粗略规则结果遇到嵌套的if-else if链时else if分支内的语句被错误地连到了外层的if上切片结果多出一大堆无关代码。3.4 第三步到达定值与数据依赖边数据依赖的实现在 2.3 节已经给出了核心方程这里补充三个工程上的处理细节。细节一指针和引用的保守处理。如果你不做别名分析遇到指针解引用*p 1最保守的做法是假设它可能修改任意变量。这样会产生大量虚假依赖边但不会漏。我通常会给用户一个精度开关默认模式下对指针做保守处理高精度模式下加一层基于类型和简单别名规则的过滤。二者在报告里的表述必须区分清楚。细节二数组下标的处理。a[i] 1到底算定义了a[i]还是整个a如果做精确的索引分析可以区分a[0]和a[1]不做的话只能保守地把整个数组当一个变量。工程上多数情况下保守处理是可行的因为数组下标通常来自循环变量跨迭代的依赖本来就存在。细节三跨语句的数据依赖要先做变量作用域绑定。找同名的局部变量在不同嵌套层级里的关系必须靠符号表。我实现时会给每个变量声明分配唯一 ID所有引用都指向这个 ID这样就不会出现不同作用域的i被误连的情况。这一步在前端解析阶段就要做好等到构图时才发现作用域问题就晚了。数据依赖边构建完成后我习惯做一次统计校验流依赖边数应该和代码中“变量读取次数”大致同量级反依赖和输出依赖边数通常会少一半左右。如果统计结果严重偏离这个直觉值说明前面某一步出问题了这时候回头查比对着图硬看效率高得多。3.5 第四步可视化输出与人工校验PDG 画出来给人看是个技术活。几百个节点全画在一张图上除了证明“我算出了图”没有任何价值。我的做法是分两种输出模式。一种是局部视图用户指定一个源码行只画出与该行直接相连的依赖边控制依赖和数据依赖用不同颜色或线型区分。这种视图节点数通常不超过 20 个人能看懂。另一种是切片视图画出从某行出发反向切片的完整节点集合但用折叠方式把块内节点合并显示只展开跨块的关键边。校验环节我强烈建议做回归测试集。手写十几个小函数每个函数包含一种典型控制结构顺序、if、if-else、while、for、嵌套循环、break、continue、多 return、递归人工标出期望的依赖边然后跑工具对比。这套测试集是我踩坑之后才建的建完之后发现的问题比之前一个月手工检查发现的还多。提示可视化千万不要用一次性输出全图的方式给业务方看反馈永远是“看不懂”。给一个“点哪看哪”的交互式局部依赖视图接受度高得多。4. 踩坑实录PDG 构建中的典型问题与排查方法4.1 依赖边爆炸精度与规模的取舍依赖边爆炸是第一个会撞上的墙。我在一个约 8000 行的模块上跑过语句级保守分析节点数约 6000边数直接冲到 42000 条平均每个节点七条出边。这个密度下任何基于可达性的查询都会变慢而且结果集大到没法用。根因通常在三个地方。一是全局变量的保守处理任何对全局变量的写入都连到所有读取点这在大模块里会产生 O(N²) 级别的边。二是指针别名不做分析时按“可能指向一切”处理边数直接乘以变量总数的量级。三是过程间调用如果一个被调函数被上百处调用每个调用点都展开边数翻倍增长。应对策略上我按收益从高到低排先做函数级摘要把被高频调用的函数用摘要替代再做别名分析的基础版本至少区分“局部地址取址”和“堆对象”最后才考虑降粒度。降粒度是最后手段因为它会丢精度前面的手段不会。有个小众但很实用的技巧按查询方向裁剪图。如果你只做反向切片那正向的边其实不需要全存可以在构建时只保留“定义点到使用点”的反向索引。图的规模能降一半以上。这个优化对只做缺陷回溯定位的场景特别合适。4.2 别名、指针与数组下标数据依赖的头号难题别名分析做得好不好直接决定 PDG 的可用性。我在这上面浪费的时间最多总结几条经验。第一条别追求全精度别名分析。学术上的精确别名分析复杂度高到不实用工业界普遍用的是基于类型和字段的近似方法。比如两个指针如果类型不兼容多半不别名字段不同的对象访问通常不别名。这层简单规则就能过滤掉大部分虚假依赖。第二条区分“必须别名”和“可能别名”。p a; *p 1;这是必须别名可以精确连边。void f(int *p) { *p 1; }里p指向谁取决于调用点这是可能别名。可能别名可以推迟到过程间分析阶段用调用点的实参来具体化。这样函数内部的图更干净。第三条数组下标优先做区间分析而不是逐点分析。a[i]在循环里如果只关心是否存在跨迭代依赖直接判定“循环体内对 a 的写和读可能存在依赖”就够了不需要求出 i 的具体取值集合。逐点分析只在数组下标是常量、且数组很大时才值得做。数组还有个特殊坑越界访问在分析上是合法的。a[10]在长度为 5 的数组上静态分析不会报错还会老老实实连一条边。这类代码在真实项目里不少见尤其是处理底层缓冲区的代码。我的处理方式是在图构建时保留这类边但在报告生成时标注“存在潜在越界访问”把分析结果和风险提示分开。4.3 循环、异常与跳转语句的边界处理循环带来的问题主要是依赖边的环。控制依赖上循环条件和循环体互相依赖数据依赖上循环变量的自增和循环条件的读取形成环。处理方式我在 2.2 节提过搜索时维护已访问集合。但还有一个更隐蔽的问题跨迭代依赖的方向。考虑s s i这一句里的s既读又写。读的是上一轮迭代的s写的是本轮迭代的s。如果在同一轮里把这两个事件当成同一条语句会算出一条自环。正确做法是把“迭代内依赖”和“迭代间依赖”分开。迭代间依赖是真实的不能省迭代内自环是假象应当过滤。判断方法是看这次读事件前面的最近定值是不是本轮迭代的写事件。如果是说明是本轮内先写后读属于语句内部次序过滤如果前面没有定值那读的就是上一轮的写保留。异常处理路线的 CFG 比普通路径复杂得多。try-catch-finally结构里try块内的任何语句都可能抛出异常跳到catch所以严格来说每条语句都有到catch入口的隐式边。全部连上会让图爆炸我的做法是只对“显式抛出”的调用点连边同时对可能抛出异常的调用按其类型签名做保守判断。这是精度上的妥协报告里必须标注清楚。goto语句在结构化代码里不多但在系统级代码和生成代码里经常出现。处理goto的唯一正确方式是先把 CFG 上的所有标签块识别出来再按跳转目标手工补边不能依赖控制结构的嵌套关系推导。我试过用结构化假设去处理含goto的代码结果控制依赖整个错位切片结果完全不可信。4.4 常见问题速查表现象可能原因排查方法解决方向图中出现大量无关依赖边指针/全局变量保守处理统计单个变量出边数看是否有异常高值加别名分析或改为按需计算切片结果包含整个函数循环回边方向错误检查循环条件块的出边是否双向连修正循环块划分依赖边方向反了CFG 边构造反向打印 CFG 邻接表人工核对修正前端 CFG 生成跨函数依赖全部丢失调用点未连边检查是否只做了函数内分析补过程间连边或摘要同名变量依赖错乱作用域未绑定打印变量 ID 与声明位置映射前端加符号表分析速度突然变慢别名分析复杂度高计时各阶段看分析阶段耗时占比分层处理先粗后细报告行号对不上源码中间表示行号丢失打印中间表示的源位置信息前端保留位置元数据这张表里的每一条都是我在实际项目里真遇到过并解决的不是理论推演。其中“报告行号对不上”这一条特别容易被低估很多自研工具到最后才发现没法把中间表示映射回源码导致分析结果再准确也没法交付。行号信息必须从解析阶段一路带到底层数据结构中间任何一次变换都不能丢。5. PDG 能落地的四类场景与影响范围5.1 程序切片从一行崩溃日志倒推影响代码程序切片是 PDG 最经典的应用也是最容易做出效果的应用。核心思路就是反向可达性搜索给定崩溃点使用的变量沿数据依赖边反推它所有可能的定值点再沿控制依赖边反推决定这些点是否执行的判断语句如此递归直到没有新节点。实际操作时切片算法有几个变体。后向切片Backward Slice回答“哪些代码影响了这一行”用于调试和根因分析。前向切片Forward Slice回答“这一行影响了哪些代码”用于变更影响评估。砍刀切片Chop是两个点的交集回答“A 到 B 之间的影响路径有哪些”精度最高但计算量最大。我用后向切片做过线上崩溃的根因定位收益很直接。日志里报了一个空指针异常异常栈只有三行但实际触发原因藏在一个初始化顺序问题里。用切片从空指针变量反推索引出七处可能的定值其中三处在同一函数被立即排除剩下四处跨了两个模块人工核对后确认是其中一处配置加载时机问题。整个过程从半天缩短到二十分钟。切片精度的关键仍然是前面说的数据依赖精度。如果你的别名分析做得很粗切片结果会把整块代码都圈进来那就失去了定位价值。所以在工程上我建议把切片功能和分析精度绑定成不同的等级产品粗粒度切片用于快速筛查高精度切片用于最终确认用户按需选用。5.2 污点分析与缺陷检测污点分析本质上是带标签的切片把不可信输入标记为污点源沿数据依赖和控制依赖边走看能不能到达敏感操作。跟普通切片相比多了两件事一是污点传播规则什么时候污点被清理比如经过整数转换后二是路径可行性判断这条传播路径真的可能被执行吗。PDG 在这里的价值是提供了完整的传播通道。只看数据依赖会漏掉“因为分支条件而间接影响”的情况比如if (userInput 1) { exec(cmd); }这种userInput到exec之间没有直接的数据流只有控制依赖。这条路必须靠 PDG 才能连上。死代码检测是另一个衍生应用。如果一个语句既不影响任何输出前向切片为空又依赖于不可达的条件那它基本就是死代码。纯粹基于 CFG 做可达性判断会漏掉很多情况因为条件不可达不等于语句不可达需要结合数据依赖判断条件是否恒假。实际做缺陷检测时最大的挑战不是构图而是误报控制。PDG 上能连出一条路径不代表这条路径在真实运行中可达。我的做法是引入多层过滤第一层过滤掉明显不可达的路径比如条件互斥第二层用简单的区间分析判断下标和循环边界第三层交给人工复核。三层过滤下来误报率能降一个数量级。5.3 变更影响分析与回归测试选择这个场景是我认为 PDG 在业务研发中价值最高的落地方向。具体问题一次提交改了几行代码需要跑哪些回归用例传统做法是靠模块路径匹配改了哪个模块就跑哪个模块的用例。问题是跨模块依赖完全捕捉不到前面说的“改 A 崩 C”就是这个问题。用 PDG 做前向切片从改动的语句出发找出所有受影响的语句集合再把语句集合映射到用例上就能得到一个精确得多的用例子集。映射的方法是这样每个测试用例在运行时通常会覆盖一批代码位置把覆盖信息和前向切片结果做交集非空就说明该用例可能受影响。这个方案要求你有覆盖率数据这是它唯一的门槛。好处是精度比模块级匹配高得多我实测过能减少约六成的用例执行量同时不漏掉真正的回归失败。变更影响分析还有个隐性价值给代码评审提供上下文。评审者看到的往往只有一个 diff不知道这段改动会牵连到哪里。如果把前向切片结果附在 diff 旁边评审者能直接看到受影响的代码位置评审效率和准确性都会提升。5.4 遗留系统理解与代码重构接手一个没有任何文档的遗留系统时PDG 是很好的探索工具。最直接的用法是关键变量溯源选定一个业务上重要的变量比如订单状态画出它的完整依赖子图就能看出这个状态是怎么被一步步修改的。这比顺着调用链读代码效率高得多因为调用链是从上往下的依赖图是从数据出发的后者更贴近业务理解方式。重构场景下PDG 能回答“这个函数能不能安全地内联”“这个变量能不能删除”这类问题。变量能不能删看它在 PDG 上有没有被读取的边函数能不能内联看它的调用点上下文会不会产生依赖冲突。这些判断用手工做极其费时用图上的可达性查询就是几行代码的事。我个人的经验是遗留系统改造项目里投入时间构建一份可用的 PDG前期的学习成本大概两到三周但后续每次改动评估都能节省大量时间尤其是那些横跨多个模块的改动。这笔投入的回收周期通常在三个月以内。最后一个技巧是关于工具的长期维护把 PDG 的构建结果缓存成可增量更新的结构。代码库每次提交只改动少量文件全量重建图是浪费。按文件粒度缓存子图改动文件时只重建该文件及其受影响节点的子图其余复用缓存。这个优化我做过在大型代码库上把单次分析时间从分钟级压缩到秒级是让工具真正能被日常使用的关键一步。 程序依赖图PDG原理与工程实践：从控制/数据依赖到切片与变更影响分析
1. 先搞清楚 PDG 到底解决什么问题1.1 从一次“改一行崩三处”的事故说起程序分析这四个字听起来很学术但落到日常里其实特别具体。我做过程序依赖图Program Dependence GraphPDG相关的工具链最初动机特别朴素一个函数里改了一行赋值回归测试挂了三个不相干的用例而这三个用例从调用关系上根本看不出跟那行代码有什么联系。人工翻代码翻了半天才发现是某个全局缓存被那一行间接改了后面几个模块读到的是脏数据。如果你也遇到过类似的场景那你其实已经在手工做程序依赖分析了只是没把它图论化。PDG 要做的事情就是把“谁影响谁执行”“谁影响谁的取值”这两类关系全部显式地画成一张有向图。节点是程序里的语句或基本块边是依赖关系。有了这张图你能回答的问题就变得非常具体改了这一句哪些代码的执行路径会变哪一段代码参与了崩溃变量的值计算这段死代码是不是真的永远不会被执行很多人第一次听到 PDG 会把它跟抽象语法树AST搞混。AST 描述的是代码长什么样——语法结构、嵌套关系PDG 描述的是代码怎么动——执行的先后、数值的流动。前者是静态的骨架照片后者是动态的因果网络。这个区别决定了它们能回答完全不同的两类问题。PDG 适合谁来用我的经验是三类人获益最大一是做静态分析工具、代码扫描器的工程同学PDG 是你绕不开的中间表示二是做编译器优化、JIT 的开发者切片和指令调度都依赖它三是接手工遗留系统、需要评估改动风险的业务开发者。前两类是刚需第三类属于“学会了能省大量加班时间”的技能。1.2 控制依赖与数据依赖PDG 的两根骨架PDG 之所以叫“依赖”图是因为它把程序语义拆成了两种最基本的约束。第一种是控制依赖Control Dependence。直观理解语句 B 是否执行取决于语句 A 的判断结果那么 B 控制依赖于 A。比如if (x 0) { y 1; }那y 1这条语句是否执行完全由x 0这个判断决定所以它控制依赖于这个条件判断。注意控制依赖描述的是一种“是否执行”的依赖不是“执行几次”的依赖。第二种是数据依赖Data Dependence。直观理解语句 B 用到的一个值是语句 A 算出来并写进去的那么 B 数据依赖于 A。比如a 3; b a 1;第二条语句读的a来自第一条语句的写入这就是一条典型的流依赖Flow Dependence。数据依赖本身还能细分成三类流依赖先写后读、反依赖先读后写、输出依赖先写后写。前一类是真正的“值传递”后两类更多是并发和重排序时需要关注的次序约束。把这两类边叠加到同一张图上就是 PDG。它的力量在于任何一条可能的因果链你都能在图上沿着边走一遍找出来。程序切片、变更影响分析、死代码检测这些任务的本质都是在 PDG 上做可达性搜索——从某个节点出发正向或反向走一遍边得到的就是被影响或被依赖的代码集合。我个人的判断是理解 PDG 的关键不在于记住定义而在于想明白“为什么需要两种依赖而不是一种”。因为程序的语义本身就是“控制流决定执行顺序 数据流决定取值来源”这两层缺了任何一层分析结果都会失真。只看数据依赖你会以为if分支里的赋值和else分支里的赋值是同一层的只看控制依赖你根本不知道变量从哪来。1.3 有了 AST 和 CFG为什么还要 PDG这是新人问得最多的问题值得认真回答因为它直接决定了你要不要投入时间学 PDG。AST 的问题在于它只表达语法层级。你从 AST 上能看出b a 1是某函数的第二个语句但看不出这个a是从哪里来的。做代码搜索、格式化、重构时 AST 够用做语义分析就不够了。CFG控制流图比 AST 强它把语句按执行顺序连起来分支、循环都变成了边。但 CFG 有一个致命局限它把所有可能的执行路径都平铺在一张图里边的数量随分支数量指数增长。一个嵌套十层的if结构CFG 上就是上千条路径。更麻烦的是CFG 只告诉你怎么走不告诉你值的来源。你想知道“变量 v 的取值可能来自哪里”在 CFG 上必须自己写数据流方程迭代求解。PDG 的价值就是把这两层信息一次性固化下来。它不展开所有路径而是用控制依赖边把“分支与此分支内语句”的关系直接连上用数据依赖边把“定义点与使用点”直接连上。图规模从路径级降到了语句级查询效率完全不是一个量级。实测下来一个几万行的模块CFG 上的路径枚举基本做不下去但 PDG 的节点数就是语句数边数通常在语句数的 1.5 到 3 倍之间规模是完全可控的。提示如果你的分析任务只涉及单条语句内的表达式变换AST 就够了一旦涉及跨语句、跨分支的语义关联请直接上 PDG不要试图在 CFG 上打补丁。还有一个容易被忽略的点PDG 是天然适合做“反向查询”的结构。业务场景里我们更常问的是“谁影响了这一行”而不是“这一行影响了谁”。反向走数据依赖边就是经典的程序切片方向。CFG 上做反向查询极其别扭因为边的方向是按执行顺序定义的。这一点在实际工具开发中会反复体现出来。2. PDG 的节点、边与构建原理拆解2.1 节点粒度语句级、基本块级还是表达式级选择节点粒度是构建 PDG 的第一个决策它直接影响图的规模和分析精度我踩过这个坑先说结论默认选基本块级需要高精度时局部降到语句级。语句级节点最好理解一个语句就是一个节点依赖关系直观。问题是循环体里几十条语句会产生大量细碎的边图规模膨胀得很快。我统计过一个约 1500 行的 C 文件语句级 PDG 大概是 1100 个节点、2800 条边人工看基本没戏。基本块级是把连续无分支的语句合并成一个节点。上面的例子合并后大约 320 个节点、700 条边规模降了一个量级代价是块内的依赖关系被压缩掉了。做变更影响分析、切片这种粗粒度任务基本块级完全够用。表达式级是最细的把a b c拆成t1 b、t2 c、t3 t1 t2、a t3这样的三地址码形式。好处是数据依赖极其精确坏处是节点数暴涨且中间变量是编译器造出来的跟源码行号对不上给用户看报告时会很痛苦。下面这张表是我实践中的经验值可以直接参考粒度典型节点规模精度适合的任务主要痛点函数级极小很低模块耦合分析内部依赖全丢失基本块级中等中变更影响、粗切片块内信息压缩语句级大中高缺陷检测、污点分析图规模膨胀表达式级极大高编译器优化行号映射困难我通常的做法是做一个“混合粒度”函数入口、分支判断、循环判断、函数调用这些关键语句单独成节点其余顺序语句合并成块。这样既保住了控制依赖的准确性又控制了规模。这个策略不是理论上的最优解但工程上性价比最高。2.2 控制依赖怎么算后支配树加路径条件控制依赖有严格的形式化定义不是拍脑袋定的。标准定义是节点 Y 控制依赖于节点 X当且仅当满足两个条件——存在一条从 X 到出口的路径不经过 Y即 Y 不后支配 X且 X 的所有其他后继都后支配 Y。这个定义第一次读会有点绕我用自己的话翻译一遍。第一步先算后支配关系如果从某个节点出发无论走哪条路最终都会经过节点 P那么 P 后支配这个节点。后支配关系可以组织成一棵树叫后支配树。第二步找那些“分叉点”后继如果一个判断语句的某个分支最终会汇聚到某节点 P而另一个分支不会那么这个分支内的语句就控制依赖于这个判断。实际算法分三步走我用代码说明每一步在干什么。第一步构造 CFG 并把所有边反向得到反向图。def build_reverse_cfg(cfg): rev {n: set() for n in cfg} for u, succs in cfg.items(): for v in succs: rev[v].add(u) return rev第二步在反向图上从虚拟出口节点做支配点计算。支配点用的是经典迭代算法初始化时假设每个节点被所有节点支配然后不断收缩集合直到收敛。def compute_dominators(nodes, preds, entry): dom {n: set(nodes) for n in nodes} dom[entry] {entry} changed True while changed: changed False for n in nodes: if n entry: continue ps preds[n] if not ps: continue common set.intersection(*(dom[p] for p in ps)) new_dom common | {n} if new_dom ! dom[n]: dom[n] new_dom changed True return dom第三步把支配关系取反就得到后支配关系再按“直接后支配”的定义提取出后支配树的父子边。有了后支配树控制依赖就可以直接读出来遍历 CFG 的每条边 (X, Y)如果 Y 不是 X 的直接后支配节点的祖先关系中的那个节点就把 Y 所在的子树里、直到 X 的直接后支配节点为止的所有节点标记为控制依赖 X。这个描述有点抽象实操中我建议直接用标准算法实现别自己简化简化版本在循环和break语句上几乎必错。循环上的控制依赖要特别小心。for (i 0; i n; i)循环体控制依赖于循环条件判断这个没问题。但循环条件本身又依赖于循环变量的更新循环变量更新又在循环体内。这形成了一个环。PDG 允许有环但在做切片的时候必须处理环否则搜索会死循环。我的做法是在切片算法里维护一个已访问集合遇到已访问节点直接剪枝。2.3 数据依赖怎么算到达定值分析数据依赖的计算本质上是回答一个问题在语句 T 用到的变量 v它的值可能是由哪些语句写进去的解决这个问题的标准方法是到达定值分析Reaching Definitions。每条赋值语句视为一个“定值点”分析的目标是求出每个程序点上哪些定值点可能到达即从该定值点出发到当前点中间没有被新的定值杀死。用数据流方程表达转移函数OUT[B] GEN[B] ∪ (IN[B] - KILL[B])汇合操作IN[B] ∪ OUT[P]P 是 B 的所有前驱其中GEN[B]是块 B 中产生的定值KILL[B]是块 B 中杀掉的、针对同一变量的其他定值。这个方程用迭代法求解因为是单调框架一定能收敛。def reaching_definitions(blocks, gen, kill, preds, entry): in_sets {b: set() for b in blocks} out_sets {b: set() for b in blocks} changed True while changed: changed False for b in blocks: if b ! entry: merged set() for p in preds[b]: merged | out_sets[p] in_sets[b] merged new_out gen[b] | (in_sets[b] - kill[b]) if new_out ! out_sets[b]: out_sets[b] new_out changed True return in_sets, out_sets算完到达定值后构造数据依赖边就很简单了对每条使用变量 v 的语句 T找到所有能到达 T 的 v 的定值点 S连一条 S → T 的流依赖边。同时如果 T 本身也定义了 v或者有别的语句定义了 v 且与 T 的读取点交错就产生反依赖和输出依赖边。这里有个实操细节同一语句内部的自依赖要过滤掉。i i 1这条语句左边定义的i和右边使用的i是两个不同的定值/使用事件如果不过滤会自己连自己图上看很别扭。正确做法是在语句内部先处理“读取时可见的定值”即右侧的i用的是语句执行前的旧值这个旧值来自之前某个定值点不是本条语句。另一个细节是变量重命名。同一个变量名在不同作用域可能是不同实体如果前端解析没做好作用域绑定会出现张冠李戴的依赖边。这个坑我在处理 C 模板代码时踩得很惨模板实例化前后变量名相同但类型不同必须靠符号表拿到唯一 ID 才能正确构图。2.4 过程间 PDG跨函数的那条线怎么连单函数 PDG 只能解决函数内部的因果分析真实工程里最有价值的问题几乎都跨函数这个接口参数被哪些下游代码改过这个返回值影响了哪些调用点过程间扩展有两个主流思路。第一个是内联展开Inlining。把被调函数直接展开到调用点然后就变成了单函数 PDG 问题。优点是分析精度最高缺点是在递归调用和深层调用链上会爆炸。我一般给内联设一个深度上限比如 3 到 5 层超过就用摘要替代。第二个是函数摘要Function Summary。为每个函数预先计算一份摘要描述“这个函数读取了哪些外部变量”“写了哪些外部变量”“返回值依赖哪些参数”。调用点用摘要来连边不需要展开函数体。摘要的好处是可缓存、可复用适合大规模代码。坏处是精度受摘要表达能力限制比如函数内部的条件分支会丢失摘要只能给出“可能影响”这种保守结论。我实际做工具时用的是混合策略调用深度浅、函数体小的直接内联调用深度深、被反复调用的用摘要。可以用一个简单的启发式规则决定条件策略理由函数体小于 50 行且无递归内联精度高成本可接受被调用点超过 10 个用摘要避免重复展开存在递归强制摘要防止无限展开涉及虚函数或多态调用保守连边到所有可能实现精度换正确性过程间连边的具体做法是在调用点 C把实际参数节点连到形参节点实参到形参的流依赖在函数返回点 R把返回值节点连回调用点 C返回值到调用点的流依赖如果有全局变量或引用参数被修改还需要从函数所有出口连一条边回到调用点的后继。引用参数是最麻烦的因为它是双向的读写都要连边而且必须区分“函数执行前”和“函数执行后”两个视角。注意过程间分析如果用摘要务必在报告里标注“可能依赖”。保守的假阳性结果在缺陷检测里可以接受但在自动重构场景下可能造成误改这是两个完全不同的风险等级。3. 动手实现一套可用的 PDG 原型怎么搭3.1 工具选型自己写还是用现成框架先说我的结论学习阶段自己写生产阶段用成熟框架。自己写的价值在于PDG 的每个环节——CFG 构造、后支配树、到达定值——你都会亲手实现一遍之后看任何框架的输出都不会有黑箱感。而且教学性质的实现代码量其实不大核心逻辑三百行左右就能跑通一个支持基本控制结构和局部变量的版本。成熟框架这边我常用的有这几类。针对 Java 生态的 Soot 是老牌选择它的 CFG 和过程间分析做得很扎实缺点是构建时间长、对新版 Java 语法支持偶有滞后。Joern 更适合做代码属性图CPG方向的查询它把 AST、CFG、PDG 融合成一张图用图查询语言写规则特别方便适合做安全扫描规则。Python 生态里如果你只处理 Python 代码直接基于ast模块加自己实现的数据流分析往往比引入重型框架更快。选型时我最看重的三个维度语言支持你的目标代码库是什么语言框架能不能正确解析边界语法这决定了是能用还是不能用。扩展性能不能方便地加入自定义分析规则比如你自己的污点源点定义。Soot 和 Joern 都支持但接入成本不同。可解释性输出的依赖边能不能定位回源码行号这直接决定了报告能不能给用户看。框架支持语言上手难度适合场景自研任意中学习、定制化分析SootJava/Android中高Java 程序分析Joern多语言中安全规则、代码查询WALAJava高学术级过程间分析我个人在做过几个项目后的体会是不要一开始就上重型框架。先用自研版本把流程跑通明确自己的分析目标到底需要什么精度再决定引入哪个框架来补足。很多情况下我们真正需要的是语句级的数据依赖根本用不上框架里的过程间全程序分析能力上重型框架纯属杀鸡用牛刀。3.2 第一步源码到 CFGCFG 构造是所有后续分析的地基这一步错了后面全错。我用一段具体代码来说明整个构造过程int sum(int n) { int s 0; for (int i 1; i n; i) { if (i % 2 0) { s i; } } return s; }构造 CFG 的关键是把控制结构拆解成基本块加跳转边。上面这段的块划分是B0s 0; i 1B1i n循环条件B2i % 2 0条件判断B3s iB4iB5return s边的关系是B0 → B1B1 → B2真、B1 → B5假B2 → B3真、B2 → B4假B3 → B4B4 → B1。构造时有两个容易出错的地方。第一是循环条件的求值位置C 语言的for循环条件在每轮迭代开始时求值所以条件是独立的块不是循环体的第一部分。第二是**break和continue的边**break应该连到循环的出口块continue连到循环的更新块这两条边如果连错控制依赖会全乱。我用的构建方法是递归下降解析语句序列遇到if递归处理两个分支并接后续块遇到while把条件块和体块组成环。这个思路对结构化语言都能覆盖遇到goto这种非结构化控制流就只能老老实实做标签到块的映射靠后处理补边。3.3 第二步后支配树与控制依赖有了 CFG控制依赖计算就是前面 2.2 节算法的直接应用。这里补充几个实操层面的注意点。虚拟出口节点的处理很关键。函数可能有多个return语句直接算后支配会因为出口不唯一而得不到正确结果。标准做法是加一个虚拟出口节点 E所有return和抛出异常的语句都连向 E然后在包含 E 的图上做后支配分析。E 本身不参与任何依赖关系只是为了让后支配树有唯一的根。后支配树的构建我建议直接用 Lengauer-Tarjan 算法虽然实现稍复杂但复杂度接近线性比朴素迭代快得多。如果只是学习用朴素的迭代求支配集也能跑就是在大函数上慢一些。控制依赖边提取时我见过最常见的错误是把循环回边也当成控制依赖。循环体控制依赖于循环条件这是对的但循环条件不控制依赖于循环体虽然循环变量的更新在循环体内。区分的方法是严格的“不后支配”判定循环条件块 B1 被 B4 反向边连回来B1 的另一个后继是出口 B5B5 不经过 B2/B3/B4所以 B2 到 B4 这一串控制依赖于 B1。而 B1 自己不满足这个条件因为它被所有路径经过吗不是从 B0 直接到 B1 再到 B5 的路径不经过 B2所以 B2 控制依赖于 B1方向是对的反过来不成立。这段逻辑说的时候容易绕实际实现时只要严格按定义走不做任何“优化简化”结果就是对的。我一开始为了省事用“分支内所有语句都控制依赖判断语句”这种粗略规则结果遇到嵌套的if-else if链时else if分支内的语句被错误地连到了外层的if上切片结果多出一大堆无关代码。3.4 第三步到达定值与数据依赖边数据依赖的实现在 2.3 节已经给出了核心方程这里补充三个工程上的处理细节。细节一指针和引用的保守处理。如果你不做别名分析遇到指针解引用*p 1最保守的做法是假设它可能修改任意变量。这样会产生大量虚假依赖边但不会漏。我通常会给用户一个精度开关默认模式下对指针做保守处理高精度模式下加一层基于类型和简单别名规则的过滤。二者在报告里的表述必须区分清楚。细节二数组下标的处理。a[i] 1到底算定义了a[i]还是整个a如果做精确的索引分析可以区分a[0]和a[1]不做的话只能保守地把整个数组当一个变量。工程上多数情况下保守处理是可行的因为数组下标通常来自循环变量跨迭代的依赖本来就存在。细节三跨语句的数据依赖要先做变量作用域绑定。找同名的局部变量在不同嵌套层级里的关系必须靠符号表。我实现时会给每个变量声明分配唯一 ID所有引用都指向这个 ID这样就不会出现不同作用域的i被误连的情况。这一步在前端解析阶段就要做好等到构图时才发现作用域问题就晚了。数据依赖边构建完成后我习惯做一次统计校验流依赖边数应该和代码中“变量读取次数”大致同量级反依赖和输出依赖边数通常会少一半左右。如果统计结果严重偏离这个直觉值说明前面某一步出问题了这时候回头查比对着图硬看效率高得多。3.5 第四步可视化输出与人工校验PDG 画出来给人看是个技术活。几百个节点全画在一张图上除了证明“我算出了图”没有任何价值。我的做法是分两种输出模式。一种是局部视图用户指定一个源码行只画出与该行直接相连的依赖边控制依赖和数据依赖用不同颜色或线型区分。这种视图节点数通常不超过 20 个人能看懂。另一种是切片视图画出从某行出发反向切片的完整节点集合但用折叠方式把块内节点合并显示只展开跨块的关键边。校验环节我强烈建议做回归测试集。手写十几个小函数每个函数包含一种典型控制结构顺序、if、if-else、while、for、嵌套循环、break、continue、多 return、递归人工标出期望的依赖边然后跑工具对比。这套测试集是我踩坑之后才建的建完之后发现的问题比之前一个月手工检查发现的还多。提示可视化千万不要用一次性输出全图的方式给业务方看反馈永远是“看不懂”。给一个“点哪看哪”的交互式局部依赖视图接受度高得多。4. 踩坑实录PDG 构建中的典型问题与排查方法4.1 依赖边爆炸精度与规模的取舍依赖边爆炸是第一个会撞上的墙。我在一个约 8000 行的模块上跑过语句级保守分析节点数约 6000边数直接冲到 42000 条平均每个节点七条出边。这个密度下任何基于可达性的查询都会变慢而且结果集大到没法用。根因通常在三个地方。一是全局变量的保守处理任何对全局变量的写入都连到所有读取点这在大模块里会产生 O(N²) 级别的边。二是指针别名不做分析时按“可能指向一切”处理边数直接乘以变量总数的量级。三是过程间调用如果一个被调函数被上百处调用每个调用点都展开边数翻倍增长。应对策略上我按收益从高到低排先做函数级摘要把被高频调用的函数用摘要替代再做别名分析的基础版本至少区分“局部地址取址”和“堆对象”最后才考虑降粒度。降粒度是最后手段因为它会丢精度前面的手段不会。有个小众但很实用的技巧按查询方向裁剪图。如果你只做反向切片那正向的边其实不需要全存可以在构建时只保留“定义点到使用点”的反向索引。图的规模能降一半以上。这个优化对只做缺陷回溯定位的场景特别合适。4.2 别名、指针与数组下标数据依赖的头号难题别名分析做得好不好直接决定 PDG 的可用性。我在这上面浪费的时间最多总结几条经验。第一条别追求全精度别名分析。学术上的精确别名分析复杂度高到不实用工业界普遍用的是基于类型和字段的近似方法。比如两个指针如果类型不兼容多半不别名字段不同的对象访问通常不别名。这层简单规则就能过滤掉大部分虚假依赖。第二条区分“必须别名”和“可能别名”。p a; *p 1;这是必须别名可以精确连边。void f(int *p) { *p 1; }里p指向谁取决于调用点这是可能别名。可能别名可以推迟到过程间分析阶段用调用点的实参来具体化。这样函数内部的图更干净。第三条数组下标优先做区间分析而不是逐点分析。a[i]在循环里如果只关心是否存在跨迭代依赖直接判定“循环体内对 a 的写和读可能存在依赖”就够了不需要求出 i 的具体取值集合。逐点分析只在数组下标是常量、且数组很大时才值得做。数组还有个特殊坑越界访问在分析上是合法的。a[10]在长度为 5 的数组上静态分析不会报错还会老老实实连一条边。这类代码在真实项目里不少见尤其是处理底层缓冲区的代码。我的处理方式是在图构建时保留这类边但在报告生成时标注“存在潜在越界访问”把分析结果和风险提示分开。4.3 循环、异常与跳转语句的边界处理循环带来的问题主要是依赖边的环。控制依赖上循环条件和循环体互相依赖数据依赖上循环变量的自增和循环条件的读取形成环。处理方式我在 2.2 节提过搜索时维护已访问集合。但还有一个更隐蔽的问题跨迭代依赖的方向。考虑s s i这一句里的s既读又写。读的是上一轮迭代的s写的是本轮迭代的s。如果在同一轮里把这两个事件当成同一条语句会算出一条自环。正确做法是把“迭代内依赖”和“迭代间依赖”分开。迭代间依赖是真实的不能省迭代内自环是假象应当过滤。判断方法是看这次读事件前面的最近定值是不是本轮迭代的写事件。如果是说明是本轮内先写后读属于语句内部次序过滤如果前面没有定值那读的就是上一轮的写保留。异常处理路线的 CFG 比普通路径复杂得多。try-catch-finally结构里try块内的任何语句都可能抛出异常跳到catch所以严格来说每条语句都有到catch入口的隐式边。全部连上会让图爆炸我的做法是只对“显式抛出”的调用点连边同时对可能抛出异常的调用按其类型签名做保守判断。这是精度上的妥协报告里必须标注清楚。goto语句在结构化代码里不多但在系统级代码和生成代码里经常出现。处理goto的唯一正确方式是先把 CFG 上的所有标签块识别出来再按跳转目标手工补边不能依赖控制结构的嵌套关系推导。我试过用结构化假设去处理含goto的代码结果控制依赖整个错位切片结果完全不可信。4.4 常见问题速查表现象可能原因排查方法解决方向图中出现大量无关依赖边指针/全局变量保守处理统计单个变量出边数看是否有异常高值加别名分析或改为按需计算切片结果包含整个函数循环回边方向错误检查循环条件块的出边是否双向连修正循环块划分依赖边方向反了CFG 边构造反向打印 CFG 邻接表人工核对修正前端 CFG 生成跨函数依赖全部丢失调用点未连边检查是否只做了函数内分析补过程间连边或摘要同名变量依赖错乱作用域未绑定打印变量 ID 与声明位置映射前端加符号表分析速度突然变慢别名分析复杂度高计时各阶段看分析阶段耗时占比分层处理先粗后细报告行号对不上源码中间表示行号丢失打印中间表示的源位置信息前端保留位置元数据这张表里的每一条都是我在实际项目里真遇到过并解决的不是理论推演。其中“报告行号对不上”这一条特别容易被低估很多自研工具到最后才发现没法把中间表示映射回源码导致分析结果再准确也没法交付。行号信息必须从解析阶段一路带到底层数据结构中间任何一次变换都不能丢。5. PDG 能落地的四类场景与影响范围5.1 程序切片从一行崩溃日志倒推影响代码程序切片是 PDG 最经典的应用也是最容易做出效果的应用。核心思路就是反向可达性搜索给定崩溃点使用的变量沿数据依赖边反推它所有可能的定值点再沿控制依赖边反推决定这些点是否执行的判断语句如此递归直到没有新节点。实际操作时切片算法有几个变体。后向切片Backward Slice回答“哪些代码影响了这一行”用于调试和根因分析。前向切片Forward Slice回答“这一行影响了哪些代码”用于变更影响评估。砍刀切片Chop是两个点的交集回答“A 到 B 之间的影响路径有哪些”精度最高但计算量最大。我用后向切片做过线上崩溃的根因定位收益很直接。日志里报了一个空指针异常异常栈只有三行但实际触发原因藏在一个初始化顺序问题里。用切片从空指针变量反推索引出七处可能的定值其中三处在同一函数被立即排除剩下四处跨了两个模块人工核对后确认是其中一处配置加载时机问题。整个过程从半天缩短到二十分钟。切片精度的关键仍然是前面说的数据依赖精度。如果你的别名分析做得很粗切片结果会把整块代码都圈进来那就失去了定位价值。所以在工程上我建议把切片功能和分析精度绑定成不同的等级产品粗粒度切片用于快速筛查高精度切片用于最终确认用户按需选用。5.2 污点分析与缺陷检测污点分析本质上是带标签的切片把不可信输入标记为污点源沿数据依赖和控制依赖边走看能不能到达敏感操作。跟普通切片相比多了两件事一是污点传播规则什么时候污点被清理比如经过整数转换后二是路径可行性判断这条传播路径真的可能被执行吗。PDG 在这里的价值是提供了完整的传播通道。只看数据依赖会漏掉“因为分支条件而间接影响”的情况比如if (userInput 1) { exec(cmd); }这种userInput到exec之间没有直接的数据流只有控制依赖。这条路必须靠 PDG 才能连上。死代码检测是另一个衍生应用。如果一个语句既不影响任何输出前向切片为空又依赖于不可达的条件那它基本就是死代码。纯粹基于 CFG 做可达性判断会漏掉很多情况因为条件不可达不等于语句不可达需要结合数据依赖判断条件是否恒假。实际做缺陷检测时最大的挑战不是构图而是误报控制。PDG 上能连出一条路径不代表这条路径在真实运行中可达。我的做法是引入多层过滤第一层过滤掉明显不可达的路径比如条件互斥第二层用简单的区间分析判断下标和循环边界第三层交给人工复核。三层过滤下来误报率能降一个数量级。5.3 变更影响分析与回归测试选择这个场景是我认为 PDG 在业务研发中价值最高的落地方向。具体问题一次提交改了几行代码需要跑哪些回归用例传统做法是靠模块路径匹配改了哪个模块就跑哪个模块的用例。问题是跨模块依赖完全捕捉不到前面说的“改 A 崩 C”就是这个问题。用 PDG 做前向切片从改动的语句出发找出所有受影响的语句集合再把语句集合映射到用例上就能得到一个精确得多的用例子集。映射的方法是这样每个测试用例在运行时通常会覆盖一批代码位置把覆盖信息和前向切片结果做交集非空就说明该用例可能受影响。这个方案要求你有覆盖率数据这是它唯一的门槛。好处是精度比模块级匹配高得多我实测过能减少约六成的用例执行量同时不漏掉真正的回归失败。变更影响分析还有个隐性价值给代码评审提供上下文。评审者看到的往往只有一个 diff不知道这段改动会牵连到哪里。如果把前向切片结果附在 diff 旁边评审者能直接看到受影响的代码位置评审效率和准确性都会提升。5.4 遗留系统理解与代码重构接手一个没有任何文档的遗留系统时PDG 是很好的探索工具。最直接的用法是关键变量溯源选定一个业务上重要的变量比如订单状态画出它的完整依赖子图就能看出这个状态是怎么被一步步修改的。这比顺着调用链读代码效率高得多因为调用链是从上往下的依赖图是从数据出发的后者更贴近业务理解方式。重构场景下PDG 能回答“这个函数能不能安全地内联”“这个变量能不能删除”这类问题。变量能不能删看它在 PDG 上有没有被读取的边函数能不能内联看它的调用点上下文会不会产生依赖冲突。这些判断用手工做极其费时用图上的可达性查询就是几行代码的事。我个人的经验是遗留系统改造项目里投入时间构建一份可用的 PDG前期的学习成本大概两到三周但后续每次改动评估都能节省大量时间尤其是那些横跨多个模块的改动。这笔投入的回收周期通常在三个月以内。最后一个技巧是关于工具的长期维护把 PDG 的构建结果缓存成可增量更新的结构。代码库每次提交只改动少量文件全量重建图是浪费。按文件粒度缓存子图改动文件时只重建该文件及其受影响节点的子图其余复用缓存。这个优化我做过在大型代码库上把单次分析时间从分钟级压缩到秒级是让工具真正能被日常使用的关键一步。