企业官网建设流程全解析

程序分析里有一块基建，性价比高到有点被低估：程序依赖图，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 边是这样的：

到这一步，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→4，4 后支配这条路径上除 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 dependence）：S1 定义了变量 v，S2 使用了 v，且从 S1 到 S2 的路径上没有 v 的其他定义。这是"值的流动"。
• 反依赖（anti-dependence）：S1 先读 v，S2 后写 v。这是"顺序约束"，不是值传递。
• 输出依赖（output dependence）：S1 和 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→2（a）、2→4（b）、3→4（a）。注意 1→4 这条不存在，因为中间被 3 杀掉了。
• 反依赖：2→3（2 读 a，3 写 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, key=lambda 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, s=None): 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，但方向反了，它依赖 total，total 不依赖它。

我特意在样例里放了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、i+1、i-1情形，性价比最高。

5.3 粒度和规模的两难，没有银弹

前面提过粒度选择，这里补充一个真实感受：PDG 的边数在最坏情况下是节点数的平方级，而实际代码里这个系数通常也不小。我做过一次统计，一个中等规模的模块，语句级 PDG 的边数是节点数的三倍左右，控制依赖占了其中约三分之一。

节点数上去之后，切片本身还是线性的，但人看不过来。所以规模问题的本质往往不是算力，而是结果的可读性。这也是为什么我在实际工具里会给切片结果做二次压缩：把连续的、依赖关系相同的语句合并成区间展示，只在关键分叉点展开。用户看到的可能还是"三十行"，但内部图的规模可能是它的十倍。

5.4 跨过程不建图，切片永远是残缺的

过程内的 PDG 只能回答函数内部的问题。可现实中"这个参数的值从哪来"的答案，往往在调用者那里；"改了这个返回值影响谁"的答案，在被调用的下游。

跨过程的标准解法是系统依赖图（SDG）：在 PDG 的基础上加上调用边、参数进边、参数出边。但直接上 SDG 会遇到一个棘手的规模问题——递归调用。如果切片时每次遇到调用点就展开被调函数，递归一出现就会无限展开。

解决办法是摘要边。它的思路是：把被调函数的"参数到返回值""参数到参数"的依赖关系预先算成一个摘要，调用点直接引用摘要，不展开函数体。这个做法最早在 1990 年的一篇经典论文里被系统化，现在几乎所有实用的过程间切片工具都会用。

我的实践体会是：摘要边的正确性验证特别烦，因为它隐藏了中间过程，出错了很难定位。我在做的时候会给摘要边加一个调试开关，打开后强制展开成普通边，然后对比两种模式下的切片结果是否一致。这个对照测试帮我抓出过至少三个摘要计算错误。

6. 工具选型：什么时候该造轮子，什么时候直接用

6.1 常见框架的能力边界

自研之前先看清楚市面上有什么。下面这张表是我自己踩过一遍之后总结的，重点在"输入是什么"和"图上能做多细"：

几个使用上的细节值得单独说：WALA 的指针分析对 Java 这种有虚调用和反射的语言做了大量工程处理，但它的 API 抽象层次偏低，你得对控制流和数据流的概念本身很熟才能用得顺。Joern 的代码属性图把三种图合并了，查询起来像写 SQL，适合快速验证假设，但如果你想定制切片算法本身，它的可改空间不如直接操作底层图结构。

6.2 我的取舍标准

实际决策我基本只看三个问题。

第一个问题：你要的是"用图"还是"改图"。只是想拿依赖关系做点事，比如找可疑数据流、做影响面评估，那直接用 Joern 或 CodeQL，别折腾。这些工具已经把跨文件解析、净化函数标注、查询语言这些基础设施都做好了，自己从零搭一遍，光是处理各种语言的语法边缘情况就能耗掉几个月。

第二个问题：分析对象有没有源码。有源码且是主流语言，上面的选择都成立。如果只有二进制，那基本只剩符号执行和二进制层面的图构建这条路，而且精度会明显下降——间接跳转和虚调用在二进制层面很难恢复。这时候要降低预期，别指望得到和源码级分析一样的切片质量。

第三个问题：你的分析目标是文本级还是语义级。如果只是想找"这个函数名在哪被调用"，正则加 grep 就够了，上 PDG 是杀鸡用牛刀。只有当你要回答"这个值能不能流到那个地方""改这里会影响哪些行为"的时候，依赖图才有不可替代的价值。

对我自己来说，造轮子只在两种情况下合理：一是要做研究，需要修改切片算法本身；二是目标语言太小众，现成工具完全不支持。除此之外，我都建议先拿现成工具跑一版结果出来，看清楚真正的瓶颈在哪——很多时候你以为需要更精确的 PDG，实际上需要的是更好的结果排序。

最后分享一个我自己反复验证过的小技巧：在动手给 PDG 加各种高级特性之前，先用它做一个最笨的用途——回答"这行代码依赖哪几行"。把这个问题在真实项目里跑通、跑准，你对依赖图的理解会比读十篇论文扎实得多。我当初就是卡在一个distractor变量上，盯着切片结果看了半小时才发现方向搞反了，那种"原来是这样"的瞬间，比任何理论推导都管用。