1. 从一次代码审计的困境说起PDG到底是什么去年帮朋友看一个遗留系统十几万行代码没有任何文档注释率不到百分之三。我需要搞清楚一个核心问题某个全局配置变量到底在哪些地方被修改、又影响了哪些下游逻辑。当时第一反应是全局搜索变量名结果搜出来四百多个引用点一个个跟下去三天都没理清楚调用链路。后来换了个思路用静态分析工具生成了整个项目的程序依赖图把变量作为节点把赋值和读取关系作为边一张图铺开哪些地方写、哪些地方读、读写之间隔着几层控制条件一目了然。那次经历让我真正意识到程序依赖图不是学术论文里的花架子而是处理复杂代码时的一把手术刀。PDG全称Program Dependence Graph中文叫程序依赖图。它用图结构来描述一个程序内部各语句、变量、控制结构之间的依赖关系。图里的节点通常代表程序中的一条语句、一个表达式或者一个基本块边则代表依赖关系。依赖关系主要分两种数据依赖和控制依赖。数据依赖说的是一个语句定义的值被另一个语句使用控制依赖说的是一个语句是否执行取决于某个条件判断的结果。把这两种依赖关系画在一张图上就得到了PDG。很多人第一次接触PDG会把它和控制流图搞混。控制流图描述的是程序执行的顺序路径节点是基本块边是跳转关系它回答的是“下一步执行哪里”。PDG回答的问题不一样它回答的是“这个值从哪来、到哪去”“这条语句在什么条件下才会执行”。举个例子一个if-else分支在控制流图里你会看到两条分叉的路径但在PDG里你会看到分支体内的语句都依赖于那个if条件形成控制依赖边。两者视角不同用途也不同。PDG能做什么最直接的应用是程序切片。给定一个变量和一个程序点切片算法沿着PDG的边反向或正向遍历就能提取出所有可能影响该变量值或受该变量值影响的语句集合。这在调试的时候特别好用——你不需要看整个程序只需要看切片出来的那几十行相关代码。除此之外PDG还广泛用于代码优化、漏洞检测、克隆代码识别、软件水印、编译器的指令调度等场景。可以说凡是需要理解代码语义关系的地方PDG都有用武之地。这篇文章适合谁看如果你正在做静态分析、代码审计、编译器开发、或者单纯想提升自己阅读复杂代码的能力PDG是一个绕不开的基础设施。我会从核心概念讲起把数据依赖和控制依赖拆开揉碎然后讲怎么构建PDG、怎么用它做切片最后分享一些实际使用中踩过的坑和排查技巧。整个过程我会尽量用生活化的类比来解释保证没有编译原理背景的读者也能跟上。2. 核心概念拆解数据依赖与控制依赖到底在说什么2.1 数据依赖值的流动轨迹数据依赖的本质是“值从哪里来到哪里去”。在程序里一个变量被赋值之后后续用到这个变量的地方就产生了数据依赖。形式化一点说如果语句S2使用了语句S1定义的变量v并且从S1到S2之间存在一条路径使得v没有被重新定义那么S2数据依赖于S1。这个“没有被重新定义”的条件很关键它保证了S1定义的值确实能到达S2。我习惯用一个快递的类比来理解。S1是发货人v是包裹S2是收货人。如果中间有人把包裹截走了变量被重新赋值那S2收到的就不是S1发的货了它们之间的数据依赖就断了。所以数据依赖分析的核心工作就是追踪每个变量的定义点和使用点然后判断定义点的值能否“活着”到达使用点。这个“活着”的概念在编译器领域叫“活跃变量分析”是数据流分析的基础。数据依赖还可以细分为几种类型。流依赖是最常见的就是前面说的定义到使用的依赖。反依赖是使用到定义的依赖比如先读变量再写变量写操作反依赖于读操作。输出依赖是两个写操作之间的依赖都写同一个变量。这几种依赖在并行化分析里特别重要因为反依赖和输出依赖可以通过变量重命名来消除而流依赖是真正的数据流动不能随便消除。在实际代码里数据依赖往往比想象中复杂。考虑数组的情况a[i] a[i-1] 1这里既有对a[i]的写又有对a[i-1]的读。如果i和i-1在运行时可能指向同一个位置那就存在依赖如果编译器能证明它们不会别名那就不存在依赖。别名分析是数据依赖分析里最头疼的问题之一也是很多静态分析工具精度上不去的主要原因。2.2 控制依赖什么条件下才会执行控制依赖描述的是语句之间的执行条件关系。如果语句S2是否执行取决于语句S1的判断结果那么S2控制依赖于S1。最典型的就是if语句if块内的所有语句都控制依赖于if条件。循环也类似循环体内的语句控制依赖于循环条件。控制依赖的数学定义基于后支配关系。在一个控制流图里如果从入口到出口的每一条路径都经过节点X那么X后支配入口。如果节点Y后支配节点X但Y不后支配X的某个前驱那么X控制依赖于Y。这个定义听起来绕但用起来很直接你只需要看从条件判断到目标语句之间是不是所有路径都必须经过那个判断。用生活场景类比你出门是否带伞控制依赖于“是否下雨”这个判断。如果下雨你带伞如果不下雨你不带伞。带伞这个动作的执行与否完全由天气判断决定。在程序里控制依赖就是这种“条件决定执行”的关系。控制依赖在程序切片里扮演的角色很微妙。当你对一个变量做切片时如果只沿着数据依赖走你会漏掉那些“虽然不直接产生数据但决定了数据是否被产生”的语句。比如一个变量在if块里被赋值如果你不把if条件纳入切片你就不知道这个赋值在什么情况下才会发生。所以完整的切片必须同时考虑数据依赖和控制依赖。2.3 控制流图与PDG的关系骨架与神经控制流图是构建PDG的基础。没有控制流图你无法确定语句之间的执行顺序和路径可达性也就无法计算控制依赖。控制流图的节点是基本块边是可能的控制转移。基本块是一段顺序执行、只有一个入口和一个出口的代码序列。构建控制流图的过程大致是先把代码解析成抽象语法树然后遍历语法树识别基本块的边界比如跳转指令、函数调用、条件分支接着在基本块之间连边。对于结构化程序控制流图比较规整对于充满goto的遗留代码控制流图可能一团乱麻这也是为什么很多静态分析工具对goto语句支持不好。PDG可以看作是在控制流图的基础上叠加了数据依赖信息。控制流图告诉你“程序可能怎么走”PDG告诉你“数据怎么流、条件怎么控”。两者结合才能完整描述程序的语义关系。在实际工具里通常先构建控制流图然后在控制流图上做数据流分析得到数据依赖同时基于后支配关系计算控制依赖最后合并成PDG。这里有个容易混淆的点PDG的节点和控制流图的节点不一定一一对应。控制流图的节点是基本块而PDG的节点可以是单条语句也可以是基本块取决于分析的粒度。粒度越细精度越高但图也越大分析开销越高。实际使用中需要根据任务需求做权衡。3. 构建PDG的完整实操流程3.1 从源码到抽象语法树第一步解析构建PDG的第一步是把源代码解析成抽象语法树。这个过程和编译器前端做的事情一样词法分析把字符流变成token流语法分析把token流变成语法树。对于C/C代码可以用Clang的LibTooling对于Java可以用Eclipse JDT对于PythonPython自带的ast模块就能搞定。我以Python为例演示一下。假设有这样一段代码def process(data): result [] for item in data: if item 0: value item * 2 result.append(value) return result用Python的ast模块解析后你会得到一棵树根节点是Module下面有FunctionDefFunctionDef的body里有Assign、For、If等节点。每个节点都带有行号信息这对后续定位代码位置很重要。解析阶段需要注意几个问题。第一宏和预处理指令的处理。C/C代码里的宏展开会让语法树和源码的对应关系变得复杂需要保留足够的源位置信息。第二语法错误的容错。实际项目里经常有编译不过的代码解析器需要能跳过错误继续分析。第三多语言混合。有些项目里Python调C、Java调Kotlin跨语言分析需要统一的中间表示。3.2 构建控制流图把执行路径画出来拿到语法树之后下一步是构建控制流图。基本思路是遍历语法树识别控制流结构。顺序语句直接串联if语句产生分支条件节点指向then块和else块两个块最后汇合到后继节点循环语句产生回边循环体末尾指回循环条件。对于上面那段Python代码控制流图大致是这样的入口指向result []然后指向for循环的条件判断条件为真时进入循环体循环体里先判断item 0为真则执行赋值和append然后回到循环条件条件为假时跳出循环执行return。构建控制流图时函数调用怎么处理是个关键决策。保守的做法是把函数调用当作一个普通节点不展开激进的做法是做过程间分析把被调函数的控制流图内联进来。前者精度低但速度快后者精度高但可能遇到递归导致无限展开。实际工具通常提供配置选项让用户根据场景选择。3.3 计算数据依赖定义-使用链的追踪数据依赖的计算依赖于定义-使用链。对每个变量找出所有定义点和所有使用点然后判断哪些定义能到达哪些使用。这个判断过程叫到达定值分析是数据流分析里的经典问题。到达定值分析的算法框架是为每个程序点维护一个集合集合里是能到达该点的所有定义。沿着控制流图迭代遇到定义就加入集合遇到使用就记录依赖关系遇到汇合点就做集合并集。迭代直到集合不再变化为止。对于有循环的程序可能需要多轮迭代才能收敛。实际实现时可以用位向量来表示定义集合每个定义对应一个bit位集合运算就是位运算速度很快。对于大型程序还可以用SSA形式来简化分析。SSA形式下每个变量只被赋值一次定义-使用链直接体现在变量命名上不需要迭代求解。LLVM的IR就是SSA形式所以基于LLVM做数据依赖分析会方便很多。数组和指针的处理是数据依赖分析的难点。对于数组a[i]如果i是变量编译器需要做别名分析来判断a[i]和a[j]是否可能指向同一位置。保守的做法是假设所有数组访问都可能别名这样会产生大量伪依赖降低分析精度。精确的做法是用区间分析或符号执行来确定下标范围但开销很大。3.4 计算控制依赖后支配树的妙用控制依赖的计算基于后支配树。后支配树的构建算法是先在控制流图上计算每个节点的直接后支配者然后把这些关系组织成一棵树。有了后支配树控制依赖的判断就很简单如果节点X的后支配者Y不后支配X的某个前驱那么X控制依赖于Y。后支配树的经典算法是Lengauer-Tarjan算法时间复杂度接近线性。实际实现时可以先用简单的迭代算法求出所有后支配关系再构建树。对于中小规模的控制流图迭代算法足够快对于大规模图才需要上Lengauer-Tarjan。控制依赖在结构化程序里比较规整但在有goto、break、continue、异常处理的程序里会变得复杂。比如异常处理try块里的语句控制依赖于可能抛出异常的调用catch块里的语句控制依赖于异常是否被抛出。这些非结构化的控制流会让控制依赖图变得稠密增加分析复杂度。3.5 合并成PDG一张图看全依赖关系数据依赖和控制依赖都算出来之后把它们合并到同一张图上就得到了PDG。合并的方式很简单节点集合取并集边集合也取并集。但要注意同一个节点可能既有数据依赖边又有控制依赖边需要用不同的边类型区分。合并后的PDG可能非常大。一个十万行代码的项目PDG可能有几十万个节点和上百万条边。直接可视化是不现实的需要做图缩减或聚类。常用的缩减方法包括合并强连通分量、折叠不相关的子图、按函数或模块分层展示。在实际工具里PDG通常不会完整地画出来而是作为查询的底层数据结构。用户提出一个切片请求工具在PDG上做遍历返回相关的节点集合。这种用法下PDG的大小不是问题关键是遍历效率。可以用邻接表存储图用深度优先搜索做遍历性能通常可以接受。4. 程序切片PDG最实用的落地场景4.1 切片的基本原理沿着依赖边走程序切片的核心思想是给定一个切片准则通常是某个程序点和该点上的某个变量找出所有可能影响该变量值的语句。在PDG上这个操作就是从切片准则对应的节点出发沿着数据依赖边和控制依赖边反向遍历收集所有可达的节点。反向切片回答的是“这个值受什么影响”。正向切片则相反从切片准则出发沿着依赖边正向遍历回答的是“这个值影响了什么”。两种切片在实际中都有用调试的时候通常用反向切片找根因影响分析的时候用正向切片评估修改范围。切片算法本身不复杂就是图遍历。但实际实现时需要考虑几个问题。第一过程间切片。如果切片准则涉及函数参数或返回值需要跨函数边界追踪依赖。第二动态切片。静态切片会包含所有可能的执行路径但实际运行时只走其中一条。动态切片利用运行时信息只保留实际执行到的路径精度更高但需要运行程序。第三切片粒度。语句级切片和变量级切片的结果不同需要根据需求选择。4.2 用切片做调试快速定位问题根源我遇到过一个典型的调试场景某个计算结果偶尔出错但不是每次都错。代码里有个复杂的条件判断链涉及七八个布尔变量。用传统方法我在每个条件分支加日志跑了好几次才复现问题。后来用切片工具以出错的计算结果为切片准则做反向切片工具直接告诉我这个结果依赖于哪几个变量的哪几次赋值我顺着切片结果一看发现其中一个布尔变量在某个边界条件下被错误地初始化了。切片做调试的优势在于它自动帮你过滤掉了不相关的代码。一个函数可能有几百行但真正影响目标变量的可能只有十几行。切片把这十几行提取出来你的注意力就能集中在真正重要的地方。特别是对于遗留代码你对代码结构不熟悉切片就像一张地图告诉你从目标点往回走会经过哪些关键路口。4.3 用切片做影响分析改代码前先看波及范围修改一个函数或一个变量之前最怕的是不知道会影响到哪些下游逻辑。正向切片正好解决这个问题。以被修改的变量为切片准则做正向切片所有受它影响的语句都会被收集出来。如果切片结果里出现了你不认识的模块那就说明这个修改的波及范围超出了预期需要格外小心。我在做代码重构时经常用这招。比如要把一个全局变量改成参数传递先用正向切片看看这个变量影响了哪些函数然后评估改造工作量。如果切片结果显示只影响了三个函数那改造起来很快如果影响了三十个函数那就得考虑是不是先加一层封装逐步迁移。影响分析还可以用于回归测试的测试用例选择。修改了某个函数后正向切片能告诉你哪些代码路径可能受影响然后从测试集中挑选覆盖这些路径的用例来跑比全量回归测试节省大量时间。4.4 切片精度的影响因素与优化切片的精度受好几个因素影响。别名分析越精确数据依赖越准确切片越小越精确。控制依赖的计算越精确条件分支的纳入越合理。过程间分析的深度越深跨函数的依赖追踪越完整。但精度和性能是一对矛盾。精确的别名分析可能需要做指针分析开销很大。过程间分析如果遇到递归可能需要做上下文敏感的分析复杂度更高。实际使用中需要根据任务的重要性和代码的规模来权衡。对于关键模块的深度分析可以开启高精度模式对于大规模代码的快速扫描可以用保守但快速的配置。还有一个容易被忽视的因素是库函数的处理。程序里大量调用标准库或第三方库如果把这些调用当作黑盒切片就会在调用点断掉。如果要对库函数也做分析就需要库函数的PDG或者摘要信息。实际工具通常提供库函数摘要机制手动或自动地为常用库函数生成依赖摘要。5. 常见问题与排查技巧实录5.1 依赖关系丢失或多余别名分析的锅最常见的问题就是切片结果里少了该有的语句或者多了不该有的语句。少了通常是因为别名分析过于保守把一些实际存在的依赖判没了。多了通常是因为别名分析过于激进把一些不存在的依赖判有了。排查这类问题的思路是先找到可疑的依赖边然后检查别名分析的假设。比如两个指针p和q如果分析认为它们可能指向同一块内存就会在*p 1和*q 2之间建立依赖。如果实际上它们永远不会别名这条依赖就是多余的。反过来如果分析认为它们不会别名但运行时确实别名了依赖就丢了。解决方法是调整别名分析的精度。对于指针密集的代码可以开启流敏感和上下文敏感的别名分析。对于数组可以用仿射表达式分析下标范围。如果工具支持还可以手动标注别名关系覆盖自动分析的结论。5.2 控制依赖计算错误非结构化控制流的坑有goto、setjmp/longjmp、异常处理的代码控制依赖很容易算错。goto会打破结构化控制流的假设让后支配关系变得复杂。异常处理会让控制流图出现隐式的边如果构建控制流图时没有正确建模异常传播路径控制依赖就会出错。排查这类问题可以先检查控制流图的构建是否正确。把控制流图画出来人工核对每条边是否合理。特别关注异常处理块、finally块、资源释放块的控制流。如果控制流图有问题控制依赖肯定不对。对于非结构化控制流可以考虑先做控制流规范化把goto转换成结构化的循环和分支。但这在自动化工具里很难做到完美实际中更多是接受一定的不精确性在切片结果里人工排除明显不相关的语句。5.3 大规模项目的性能瓶颈图太大怎么办十万行以上的项目PDG的规模会非常大构建和分析都可能遇到性能问题。内存占用高、构建时间长、切片查询慢这些都是常见症状。优化思路有几个方向。第一按需构建。不要一次性构建整个项目的PDG而是以函数或模块为单位用到哪个构建哪个。第二增量更新。代码修改后只重新分析受影响的函数而不是全量重建。第三图压缩。合并强连通分量折叠不相关的子图减少节点和边的数量。第四并行化。不同函数的PDG构建可以并行切片查询也可以并行。我在处理一个二十万行的C项目时采用了按需构建加缓存的策略。首次分析某个函数时构建它的PDG并缓存后续查询直接命中缓存。对于跨函数的切片只构建切片路径上涉及到的函数。这样把内存占用从几十GB降到了几GB查询响应时间从分钟级降到了秒级。5.4 常见问题速查表问题现象可能原因排查方法解决思路切片结果缺少关键语句别名分析过于保守检查指针和数组的别名假设提高别名分析精度手动标注别名切片结果包含大量无关语句别名分析过于激进检查是否存在伪依赖边开启流敏感分析缩小别名范围控制依赖边异常控制流图构建错误可视化控制流图人工核对修正异常处理和goto的建模构建时间过长全量分析规模太大统计各阶段耗时按需构建增量更新并行化内存占用过高PDG节点和边太多统计节点和边数量图压缩分模块加载跨函数切片断裂过程间分析未开启检查函数调用点的处理方式开启过程间分析生成库函数摘要5.5 几个容易被忽视的实操心得第一个心得不要追求完美的PDG。静态分析本质上是在做近似完全精确的PDG在理论上就不可判定。接受一定的不精确性把精力放在关键路径的精确分析上性价比更高。第二个心得可视化很重要。虽然完整的PDG画不出来但局部子图的可视化对理解依赖关系帮助很大。Graphviz是个好工具把切片结果导出成dot格式渲染出来看比看文本输出直观得多。第三个心得结合动态信息。静态PDG加上运行时轨迹可以得到更精确的动态切片。如果条件允许在关键路径上插桩收集运行时依赖和静态PDG互相印证能发现很多静态分析遗漏的问题。第四个心得版本对比。同一个项目不同版本的PDG做差分能快速识别出修改引入的新依赖。这在代码审查和回归测试里特别有用比看diff文本更能理解修改的语义影响。6. 从PDG到更广阔的代码分析世界PDG是代码分析的基础设施但它不是终点。在PDG之上可以构建更高级的分析。比如系统依赖图把多个函数的PDG用调用边和参数边连接起来支持全程序分析。比如值流图把PDG里的数据依赖边细化到值级别支持更精确的污点分析。比如代码属性图把抽象语法树、控制流图、PDG合并成一张超图支持多视角的代码查询。实际工作中我很少直接操作PDG的底层数据结构更多是使用基于PDG构建的上层工具。比如CodeQL用数据库的方式存储代码的语义关系底层就包含了类似PDG的依赖信息。比如Joern用图数据库存储代码属性图支持复杂的图查询。这些工具把PDG的复杂性封装起来让分析人员可以用更高级的语言表达分析逻辑。但理解PDG的原理仍然很重要。当工具给出的结果不符合预期时你需要知道底层发生了什么才能调整配置或换用其他方法。当需要定制分析时你需要知道PDG能提供什么信息才能设计出可行的方案。PDG就像编程里的指针平时用高级语言写代码不太需要直接操作它但理解它让你对程序的行为有更深刻的把握。最后分享一个我常用的技巧当你面对一个完全陌生的代码库时先别急着读代码。用工具生成几个关键变量的切片看看这些切片涉及哪些函数、哪些模块。切片的分布能快速告诉你代码的核心逻辑在哪里、模块之间的耦合关系如何。这比从头到尾读代码效率高得多也是我这些年在代码分析里最依赖的方法之一。 程序依赖图PDG完全指南：从数据依赖到程序切片实战
1. 从一次代码审计的困境说起PDG到底是什么去年帮朋友看一个遗留系统十几万行代码没有任何文档注释率不到百分之三。我需要搞清楚一个核心问题某个全局配置变量到底在哪些地方被修改、又影响了哪些下游逻辑。当时第一反应是全局搜索变量名结果搜出来四百多个引用点一个个跟下去三天都没理清楚调用链路。后来换了个思路用静态分析工具生成了整个项目的程序依赖图把变量作为节点把赋值和读取关系作为边一张图铺开哪些地方写、哪些地方读、读写之间隔着几层控制条件一目了然。那次经历让我真正意识到程序依赖图不是学术论文里的花架子而是处理复杂代码时的一把手术刀。PDG全称Program Dependence Graph中文叫程序依赖图。它用图结构来描述一个程序内部各语句、变量、控制结构之间的依赖关系。图里的节点通常代表程序中的一条语句、一个表达式或者一个基本块边则代表依赖关系。依赖关系主要分两种数据依赖和控制依赖。数据依赖说的是一个语句定义的值被另一个语句使用控制依赖说的是一个语句是否执行取决于某个条件判断的结果。把这两种依赖关系画在一张图上就得到了PDG。很多人第一次接触PDG会把它和控制流图搞混。控制流图描述的是程序执行的顺序路径节点是基本块边是跳转关系它回答的是“下一步执行哪里”。PDG回答的问题不一样它回答的是“这个值从哪来、到哪去”“这条语句在什么条件下才会执行”。举个例子一个if-else分支在控制流图里你会看到两条分叉的路径但在PDG里你会看到分支体内的语句都依赖于那个if条件形成控制依赖边。两者视角不同用途也不同。PDG能做什么最直接的应用是程序切片。给定一个变量和一个程序点切片算法沿着PDG的边反向或正向遍历就能提取出所有可能影响该变量值或受该变量值影响的语句集合。这在调试的时候特别好用——你不需要看整个程序只需要看切片出来的那几十行相关代码。除此之外PDG还广泛用于代码优化、漏洞检测、克隆代码识别、软件水印、编译器的指令调度等场景。可以说凡是需要理解代码语义关系的地方PDG都有用武之地。这篇文章适合谁看如果你正在做静态分析、代码审计、编译器开发、或者单纯想提升自己阅读复杂代码的能力PDG是一个绕不开的基础设施。我会从核心概念讲起把数据依赖和控制依赖拆开揉碎然后讲怎么构建PDG、怎么用它做切片最后分享一些实际使用中踩过的坑和排查技巧。整个过程我会尽量用生活化的类比来解释保证没有编译原理背景的读者也能跟上。2. 核心概念拆解数据依赖与控制依赖到底在说什么2.1 数据依赖值的流动轨迹数据依赖的本质是“值从哪里来到哪里去”。在程序里一个变量被赋值之后后续用到这个变量的地方就产生了数据依赖。形式化一点说如果语句S2使用了语句S1定义的变量v并且从S1到S2之间存在一条路径使得v没有被重新定义那么S2数据依赖于S1。这个“没有被重新定义”的条件很关键它保证了S1定义的值确实能到达S2。我习惯用一个快递的类比来理解。S1是发货人v是包裹S2是收货人。如果中间有人把包裹截走了变量被重新赋值那S2收到的就不是S1发的货了它们之间的数据依赖就断了。所以数据依赖分析的核心工作就是追踪每个变量的定义点和使用点然后判断定义点的值能否“活着”到达使用点。这个“活着”的概念在编译器领域叫“活跃变量分析”是数据流分析的基础。数据依赖还可以细分为几种类型。流依赖是最常见的就是前面说的定义到使用的依赖。反依赖是使用到定义的依赖比如先读变量再写变量写操作反依赖于读操作。输出依赖是两个写操作之间的依赖都写同一个变量。这几种依赖在并行化分析里特别重要因为反依赖和输出依赖可以通过变量重命名来消除而流依赖是真正的数据流动不能随便消除。在实际代码里数据依赖往往比想象中复杂。考虑数组的情况a[i] a[i-1] 1这里既有对a[i]的写又有对a[i-1]的读。如果i和i-1在运行时可能指向同一个位置那就存在依赖如果编译器能证明它们不会别名那就不存在依赖。别名分析是数据依赖分析里最头疼的问题之一也是很多静态分析工具精度上不去的主要原因。2.2 控制依赖什么条件下才会执行控制依赖描述的是语句之间的执行条件关系。如果语句S2是否执行取决于语句S1的判断结果那么S2控制依赖于S1。最典型的就是if语句if块内的所有语句都控制依赖于if条件。循环也类似循环体内的语句控制依赖于循环条件。控制依赖的数学定义基于后支配关系。在一个控制流图里如果从入口到出口的每一条路径都经过节点X那么X后支配入口。如果节点Y后支配节点X但Y不后支配X的某个前驱那么X控制依赖于Y。这个定义听起来绕但用起来很直接你只需要看从条件判断到目标语句之间是不是所有路径都必须经过那个判断。用生活场景类比你出门是否带伞控制依赖于“是否下雨”这个判断。如果下雨你带伞如果不下雨你不带伞。带伞这个动作的执行与否完全由天气判断决定。在程序里控制依赖就是这种“条件决定执行”的关系。控制依赖在程序切片里扮演的角色很微妙。当你对一个变量做切片时如果只沿着数据依赖走你会漏掉那些“虽然不直接产生数据但决定了数据是否被产生”的语句。比如一个变量在if块里被赋值如果你不把if条件纳入切片你就不知道这个赋值在什么情况下才会发生。所以完整的切片必须同时考虑数据依赖和控制依赖。2.3 控制流图与PDG的关系骨架与神经控制流图是构建PDG的基础。没有控制流图你无法确定语句之间的执行顺序和路径可达性也就无法计算控制依赖。控制流图的节点是基本块边是可能的控制转移。基本块是一段顺序执行、只有一个入口和一个出口的代码序列。构建控制流图的过程大致是先把代码解析成抽象语法树然后遍历语法树识别基本块的边界比如跳转指令、函数调用、条件分支接着在基本块之间连边。对于结构化程序控制流图比较规整对于充满goto的遗留代码控制流图可能一团乱麻这也是为什么很多静态分析工具对goto语句支持不好。PDG可以看作是在控制流图的基础上叠加了数据依赖信息。控制流图告诉你“程序可能怎么走”PDG告诉你“数据怎么流、条件怎么控”。两者结合才能完整描述程序的语义关系。在实际工具里通常先构建控制流图然后在控制流图上做数据流分析得到数据依赖同时基于后支配关系计算控制依赖最后合并成PDG。这里有个容易混淆的点PDG的节点和控制流图的节点不一定一一对应。控制流图的节点是基本块而PDG的节点可以是单条语句也可以是基本块取决于分析的粒度。粒度越细精度越高但图也越大分析开销越高。实际使用中需要根据任务需求做权衡。3. 构建PDG的完整实操流程3.1 从源码到抽象语法树第一步解析构建PDG的第一步是把源代码解析成抽象语法树。这个过程和编译器前端做的事情一样词法分析把字符流变成token流语法分析把token流变成语法树。对于C/C代码可以用Clang的LibTooling对于Java可以用Eclipse JDT对于PythonPython自带的ast模块就能搞定。我以Python为例演示一下。假设有这样一段代码def process(data): result [] for item in data: if item 0: value item * 2 result.append(value) return result用Python的ast模块解析后你会得到一棵树根节点是Module下面有FunctionDefFunctionDef的body里有Assign、For、If等节点。每个节点都带有行号信息这对后续定位代码位置很重要。解析阶段需要注意几个问题。第一宏和预处理指令的处理。C/C代码里的宏展开会让语法树和源码的对应关系变得复杂需要保留足够的源位置信息。第二语法错误的容错。实际项目里经常有编译不过的代码解析器需要能跳过错误继续分析。第三多语言混合。有些项目里Python调C、Java调Kotlin跨语言分析需要统一的中间表示。3.2 构建控制流图把执行路径画出来拿到语法树之后下一步是构建控制流图。基本思路是遍历语法树识别控制流结构。顺序语句直接串联if语句产生分支条件节点指向then块和else块两个块最后汇合到后继节点循环语句产生回边循环体末尾指回循环条件。对于上面那段Python代码控制流图大致是这样的入口指向result []然后指向for循环的条件判断条件为真时进入循环体循环体里先判断item 0为真则执行赋值和append然后回到循环条件条件为假时跳出循环执行return。构建控制流图时函数调用怎么处理是个关键决策。保守的做法是把函数调用当作一个普通节点不展开激进的做法是做过程间分析把被调函数的控制流图内联进来。前者精度低但速度快后者精度高但可能遇到递归导致无限展开。实际工具通常提供配置选项让用户根据场景选择。3.3 计算数据依赖定义-使用链的追踪数据依赖的计算依赖于定义-使用链。对每个变量找出所有定义点和所有使用点然后判断哪些定义能到达哪些使用。这个判断过程叫到达定值分析是数据流分析里的经典问题。到达定值分析的算法框架是为每个程序点维护一个集合集合里是能到达该点的所有定义。沿着控制流图迭代遇到定义就加入集合遇到使用就记录依赖关系遇到汇合点就做集合并集。迭代直到集合不再变化为止。对于有循环的程序可能需要多轮迭代才能收敛。实际实现时可以用位向量来表示定义集合每个定义对应一个bit位集合运算就是位运算速度很快。对于大型程序还可以用SSA形式来简化分析。SSA形式下每个变量只被赋值一次定义-使用链直接体现在变量命名上不需要迭代求解。LLVM的IR就是SSA形式所以基于LLVM做数据依赖分析会方便很多。数组和指针的处理是数据依赖分析的难点。对于数组a[i]如果i是变量编译器需要做别名分析来判断a[i]和a[j]是否可能指向同一位置。保守的做法是假设所有数组访问都可能别名这样会产生大量伪依赖降低分析精度。精确的做法是用区间分析或符号执行来确定下标范围但开销很大。3.4 计算控制依赖后支配树的妙用控制依赖的计算基于后支配树。后支配树的构建算法是先在控制流图上计算每个节点的直接后支配者然后把这些关系组织成一棵树。有了后支配树控制依赖的判断就很简单如果节点X的后支配者Y不后支配X的某个前驱那么X控制依赖于Y。后支配树的经典算法是Lengauer-Tarjan算法时间复杂度接近线性。实际实现时可以先用简单的迭代算法求出所有后支配关系再构建树。对于中小规模的控制流图迭代算法足够快对于大规模图才需要上Lengauer-Tarjan。控制依赖在结构化程序里比较规整但在有goto、break、continue、异常处理的程序里会变得复杂。比如异常处理try块里的语句控制依赖于可能抛出异常的调用catch块里的语句控制依赖于异常是否被抛出。这些非结构化的控制流会让控制依赖图变得稠密增加分析复杂度。3.5 合并成PDG一张图看全依赖关系数据依赖和控制依赖都算出来之后把它们合并到同一张图上就得到了PDG。合并的方式很简单节点集合取并集边集合也取并集。但要注意同一个节点可能既有数据依赖边又有控制依赖边需要用不同的边类型区分。合并后的PDG可能非常大。一个十万行代码的项目PDG可能有几十万个节点和上百万条边。直接可视化是不现实的需要做图缩减或聚类。常用的缩减方法包括合并强连通分量、折叠不相关的子图、按函数或模块分层展示。在实际工具里PDG通常不会完整地画出来而是作为查询的底层数据结构。用户提出一个切片请求工具在PDG上做遍历返回相关的节点集合。这种用法下PDG的大小不是问题关键是遍历效率。可以用邻接表存储图用深度优先搜索做遍历性能通常可以接受。4. 程序切片PDG最实用的落地场景4.1 切片的基本原理沿着依赖边走程序切片的核心思想是给定一个切片准则通常是某个程序点和该点上的某个变量找出所有可能影响该变量值的语句。在PDG上这个操作就是从切片准则对应的节点出发沿着数据依赖边和控制依赖边反向遍历收集所有可达的节点。反向切片回答的是“这个值受什么影响”。正向切片则相反从切片准则出发沿着依赖边正向遍历回答的是“这个值影响了什么”。两种切片在实际中都有用调试的时候通常用反向切片找根因影响分析的时候用正向切片评估修改范围。切片算法本身不复杂就是图遍历。但实际实现时需要考虑几个问题。第一过程间切片。如果切片准则涉及函数参数或返回值需要跨函数边界追踪依赖。第二动态切片。静态切片会包含所有可能的执行路径但实际运行时只走其中一条。动态切片利用运行时信息只保留实际执行到的路径精度更高但需要运行程序。第三切片粒度。语句级切片和变量级切片的结果不同需要根据需求选择。4.2 用切片做调试快速定位问题根源我遇到过一个典型的调试场景某个计算结果偶尔出错但不是每次都错。代码里有个复杂的条件判断链涉及七八个布尔变量。用传统方法我在每个条件分支加日志跑了好几次才复现问题。后来用切片工具以出错的计算结果为切片准则做反向切片工具直接告诉我这个结果依赖于哪几个变量的哪几次赋值我顺着切片结果一看发现其中一个布尔变量在某个边界条件下被错误地初始化了。切片做调试的优势在于它自动帮你过滤掉了不相关的代码。一个函数可能有几百行但真正影响目标变量的可能只有十几行。切片把这十几行提取出来你的注意力就能集中在真正重要的地方。特别是对于遗留代码你对代码结构不熟悉切片就像一张地图告诉你从目标点往回走会经过哪些关键路口。4.3 用切片做影响分析改代码前先看波及范围修改一个函数或一个变量之前最怕的是不知道会影响到哪些下游逻辑。正向切片正好解决这个问题。以被修改的变量为切片准则做正向切片所有受它影响的语句都会被收集出来。如果切片结果里出现了你不认识的模块那就说明这个修改的波及范围超出了预期需要格外小心。我在做代码重构时经常用这招。比如要把一个全局变量改成参数传递先用正向切片看看这个变量影响了哪些函数然后评估改造工作量。如果切片结果显示只影响了三个函数那改造起来很快如果影响了三十个函数那就得考虑是不是先加一层封装逐步迁移。影响分析还可以用于回归测试的测试用例选择。修改了某个函数后正向切片能告诉你哪些代码路径可能受影响然后从测试集中挑选覆盖这些路径的用例来跑比全量回归测试节省大量时间。4.4 切片精度的影响因素与优化切片的精度受好几个因素影响。别名分析越精确数据依赖越准确切片越小越精确。控制依赖的计算越精确条件分支的纳入越合理。过程间分析的深度越深跨函数的依赖追踪越完整。但精度和性能是一对矛盾。精确的别名分析可能需要做指针分析开销很大。过程间分析如果遇到递归可能需要做上下文敏感的分析复杂度更高。实际使用中需要根据任务的重要性和代码的规模来权衡。对于关键模块的深度分析可以开启高精度模式对于大规模代码的快速扫描可以用保守但快速的配置。还有一个容易被忽视的因素是库函数的处理。程序里大量调用标准库或第三方库如果把这些调用当作黑盒切片就会在调用点断掉。如果要对库函数也做分析就需要库函数的PDG或者摘要信息。实际工具通常提供库函数摘要机制手动或自动地为常用库函数生成依赖摘要。5. 常见问题与排查技巧实录5.1 依赖关系丢失或多余别名分析的锅最常见的问题就是切片结果里少了该有的语句或者多了不该有的语句。少了通常是因为别名分析过于保守把一些实际存在的依赖判没了。多了通常是因为别名分析过于激进把一些不存在的依赖判有了。排查这类问题的思路是先找到可疑的依赖边然后检查别名分析的假设。比如两个指针p和q如果分析认为它们可能指向同一块内存就会在*p 1和*q 2之间建立依赖。如果实际上它们永远不会别名这条依赖就是多余的。反过来如果分析认为它们不会别名但运行时确实别名了依赖就丢了。解决方法是调整别名分析的精度。对于指针密集的代码可以开启流敏感和上下文敏感的别名分析。对于数组可以用仿射表达式分析下标范围。如果工具支持还可以手动标注别名关系覆盖自动分析的结论。5.2 控制依赖计算错误非结构化控制流的坑有goto、setjmp/longjmp、异常处理的代码控制依赖很容易算错。goto会打破结构化控制流的假设让后支配关系变得复杂。异常处理会让控制流图出现隐式的边如果构建控制流图时没有正确建模异常传播路径控制依赖就会出错。排查这类问题可以先检查控制流图的构建是否正确。把控制流图画出来人工核对每条边是否合理。特别关注异常处理块、finally块、资源释放块的控制流。如果控制流图有问题控制依赖肯定不对。对于非结构化控制流可以考虑先做控制流规范化把goto转换成结构化的循环和分支。但这在自动化工具里很难做到完美实际中更多是接受一定的不精确性在切片结果里人工排除明显不相关的语句。5.3 大规模项目的性能瓶颈图太大怎么办十万行以上的项目PDG的规模会非常大构建和分析都可能遇到性能问题。内存占用高、构建时间长、切片查询慢这些都是常见症状。优化思路有几个方向。第一按需构建。不要一次性构建整个项目的PDG而是以函数或模块为单位用到哪个构建哪个。第二增量更新。代码修改后只重新分析受影响的函数而不是全量重建。第三图压缩。合并强连通分量折叠不相关的子图减少节点和边的数量。第四并行化。不同函数的PDG构建可以并行切片查询也可以并行。我在处理一个二十万行的C项目时采用了按需构建加缓存的策略。首次分析某个函数时构建它的PDG并缓存后续查询直接命中缓存。对于跨函数的切片只构建切片路径上涉及到的函数。这样把内存占用从几十GB降到了几GB查询响应时间从分钟级降到了秒级。5.4 常见问题速查表问题现象可能原因排查方法解决思路切片结果缺少关键语句别名分析过于保守检查指针和数组的别名假设提高别名分析精度手动标注别名切片结果包含大量无关语句别名分析过于激进检查是否存在伪依赖边开启流敏感分析缩小别名范围控制依赖边异常控制流图构建错误可视化控制流图人工核对修正异常处理和goto的建模构建时间过长全量分析规模太大统计各阶段耗时按需构建增量更新并行化内存占用过高PDG节点和边太多统计节点和边数量图压缩分模块加载跨函数切片断裂过程间分析未开启检查函数调用点的处理方式开启过程间分析生成库函数摘要5.5 几个容易被忽视的实操心得第一个心得不要追求完美的PDG。静态分析本质上是在做近似完全精确的PDG在理论上就不可判定。接受一定的不精确性把精力放在关键路径的精确分析上性价比更高。第二个心得可视化很重要。虽然完整的PDG画不出来但局部子图的可视化对理解依赖关系帮助很大。Graphviz是个好工具把切片结果导出成dot格式渲染出来看比看文本输出直观得多。第三个心得结合动态信息。静态PDG加上运行时轨迹可以得到更精确的动态切片。如果条件允许在关键路径上插桩收集运行时依赖和静态PDG互相印证能发现很多静态分析遗漏的问题。第四个心得版本对比。同一个项目不同版本的PDG做差分能快速识别出修改引入的新依赖。这在代码审查和回归测试里特别有用比看diff文本更能理解修改的语义影响。6. 从PDG到更广阔的代码分析世界PDG是代码分析的基础设施但它不是终点。在PDG之上可以构建更高级的分析。比如系统依赖图把多个函数的PDG用调用边和参数边连接起来支持全程序分析。比如值流图把PDG里的数据依赖边细化到值级别支持更精确的污点分析。比如代码属性图把抽象语法树、控制流图、PDG合并成一张超图支持多视角的代码查询。实际工作中我很少直接操作PDG的底层数据结构更多是使用基于PDG构建的上层工具。比如CodeQL用数据库的方式存储代码的语义关系底层就包含了类似PDG的依赖信息。比如Joern用图数据库存储代码属性图支持复杂的图查询。这些工具把PDG的复杂性封装起来让分析人员可以用更高级的语言表达分析逻辑。但理解PDG的原理仍然很重要。当工具给出的结果不符合预期时你需要知道底层发生了什么才能调整配置或换用其他方法。当需要定制分析时你需要知道PDG能提供什么信息才能设计出可行的方案。PDG就像编程里的指针平时用高级语言写代码不太需要直接操作它但理解它让你对程序的行为有更深刻的把握。最后分享一个我常用的技巧当你面对一个完全陌生的代码库时先别急着读代码。用工具生成几个关键变量的切片看看这些切片涉及哪些函数、哪些模块。切片的分布能快速告诉你代码的核心逻辑在哪里、模块之间的耦合关系如何。这比从头到尾读代码效率高得多也是我这些年在代码分析里最依赖的方法之一。