搞程序分析、做编译优化、写单元测试覆盖率统计的朋友估计都躲不开一个东西控制流图Control Flow Graph简称CFG。不管你是刚接触静态分析还是已经在折腾插桩、模糊测试CFG都是绕不开的地基。简单说它就是把代码里所有可能执行的路径用图的方式画出来节点是基本块边是跳转关系。有了这张图机器才能“看懂”程序有哪些走法我们才能在上面做数据流分析、路径覆盖、死代码检测这些事。这篇东西我不打算堆教科书定义而是按我自己实际做项目的经验来拆CFG到底怎么建、基本块怎么切、循环和异常怎么处理、建完图之后能拿来干什么还有最常见的坑是什么。适合刚入门编译原理或者正在做代码分析工具的同学也适合那些写测试工具但一直没搞明白覆盖率上报原理的工程师。看完你应该能自己手写一个简化版的CFG生成器并且知道怎么用它解决实际工程问题。1. 内容整体设计与思路拆解CFG到底在解决什么问题1.1 为什么不能直接拿源码分析刚接触代码分析时我第一反应是直接读AST抽象语法树觉得树已经把代码结构表达清楚了为什么还要转成图后来踩了坑才明白AST表达的是“嵌套关系”但程序执行是“流动”的。if、loop、break、return这些控制结构会让执行流在一个代码块之间来回跳转这种平级跳转关系在树状结构里表达起来非常别扭。举个例子一个简单的if-elseif (x 0) { y 1; } else { y -1; } z y * 2;在AST里两个分支是兄弟节点但它们之间的“互斥关系”只是一棵树的并列分支。可当你真正执行时要么走then分支要么走else分支最后汇合到y -1之后的那条赋值语句。这种“分叉”和“汇合”才是程序执行流的关键。CFG就是专门为这种流动关系设计的基本块是节点条件跳转是分叉跳转目标是边汇合点是公共后继。这样我们就能清晰回答“从A点出发哪些地方可能被执行到”。1.2 CFG是几乎所有程序分析工具的中枢可能有人觉得CFG只是编译原理课上的一个概念离工程很远。实际上只要你接触过以下工具背后基本都有CFG的影子代码覆盖率工具如gcov、JaCoCo需要CFG来识别基本块和边从而计算语句覆盖、分支覆盖、路径覆盖。静态分析工具如SonarQube、SpotBugs在CFG上跑污点分析、空指针分析、资源泄漏检测。编译器优化如LLVM、GCC利用CFG做死代码消除、循环不变量外提、内联决策。模糊测试如LibFuzzer通过CFG计算目标函数的可达路径指导输入生成。打个生活化的比方CFG之于程序分析就像地图之于出行。代码是城市里的建筑AST是每栋楼的内部结构图而CFG是路网和导航路线。你要知道从A点到B点能不能走通、要经过哪些路口靠楼内结构图是不够的必须有路网图。CFG就是程序执行的“路网图”。1.3 设计CFG生成器时的两个核心问题设计一个CFG生成器本质上要回答两个问题一是节点切多细二是边怎么画才准确。节点切太细比如每条语句一个节点图会很精确但规模爆炸数据流分析跑起来很慢节点切太粗整个函数一个节点又丢失了路径信息分析没有意义。所以工程上通常引入“基本块Basic Block”的概念一段顺序执行的语句序列内部没有跳转只有入口和出口。在一个基本块内部只要第一条语句执行了后面所有语句都会按顺序执行中间不可能跳到别处也不可能从中间插入。边则分两类无条件跳转边和条件跳转边。if的两个分支产生两条条件边return、throw产生出口边终结边goto产生无条件边。绘制边时最需要注意的是“Fall-through”行为很多体系结构里条件不满足时并不需要显式跳转直接顺序执行下一条但CFG里仍然要为这个隐式分支画一条边否则后续分析会漏路径。2. 核心细节解析与实操要点从源码到CFG的完整拆解2.1 基本块的划分规则leader算法实际工程中构建CFG不是对着源码一行行画而是先用leader算法把代码切成基本块。规则很简单一条语句成为基本块的首条语句leader当且仅当满足以下任一条件它是函数入口的第一条语句。它是任何跳转指令的目标语句即被某条goto、if、case、循环头、异常处理器指向。它紧跟在一条跳转指令之后包括条件跳转的分支目标之后、无条件跳转之后、return/throw之后。把leader找出来后从每个leader开始直到下一个leader之前不包含下一个leader的所有语句就构成一个基本块。这个算法简单高效处理顺序代码、分支、循环都没有问题。举个例子下面这段伪代码1: a 1 2: if b 0 goto 5 3: a -1 4: goto 6 5: a 2 6: c a * 2按规则找leader第1行是入口是leader第2行的跳转目标是第5行所以第5行是leader第2行是条件跳转紧跟它的是第3行所以第3行是leader第4行是无条件跳转紧跟其后的是第5行已经是leader第4行本身也是一个leader因为它紧跟在跳转指令后这里注意第4行紧跟在第3行这个普通赋值后面但由于第4行本身就是一条跳转指令它应该成为leader吗仔细看规则3“紧跟在一条跳转指令之后”成为leader。第4行紧跟的是第3行不是跳转指令所以不能靠这条规则。但是第4行是第3行基本块内的一条指令不我们需要逐个判断。第3行是leader从第3行开始第3行a -1第4行goto 6它们顺序执行没有跳转目标指向第4行所以第3行和第4行应该连成一个基本块即块内包含a -1和goto 6。但这样块内最后一条是跳转指令没问题。然后紧跟第4行之后的是第5行已经是leader所以第5行开始新块。最终基本块划分是块1第1、2行、块2第3、4行、块3第5行、块4第6行。边为块1-块2if条件为真走5注意第2行是if b 0 goto 5所以要画两条边if条件成立时块1-块3目标5if不成立时块1-块2fall-through到3。块2-块4goto 6。块3-块4顺序fall-through。最终CFG就是标准的菱形结构。这个例子很典型leader算法看起来简单但它决定了CFG的粒度。如果你切错了后面所有分析都会出问题。我在实际写代码时习惯把“跳转指令自身”和“跳转目标”分开处理先扫描一遍收集所有跳转目标再收集所有跳转指令的后续指令最后合并去重这样不容易漏。2.2 指令级CFG与基本块级CFG的选择基本块CFG适合大多数分析但也有一些场景需要更细粒度的指令级CFG。比如做二进制分析时每条机器指令都可能触发断言、异常、系统调用基本块粒度会丢失这些中间状态又比如做反向切片时需要知道某条指令是否可能被某条路径跳过指令级图更精确。代价就是节点数膨胀一个数量级遍历开销大增。我的经验是优先做基本块级CFG等需要精确到指令时再展开成指令级而不是一开始就上细粒度。很多静态分析工具比如LLVM的llvm::Function对象内部维护的CFG其实是基本块级只有在特定pass中才会遍历指令列表做更细的分析。这样做的好处是内存占用可控分析框架简洁清晰。2.3 构建CFG时的数据结构设计自己实现CFG时节点和边的数据结构设计直接决定后续开发的效率。我常用的做法是class BasicBlock: def __init__(self, id, leaders, instructions): self.id id self.instructions instructions self.succs [] # 后继基本块列表 self.preds [] # 前驱基本块列表边的信息存成succs和preds双向列表而不是单独建边对象。这样遍历前驱和后继都很快而且处理不可达代码时容易定位。每个基本块内部还建议保存第一条指令和最后一条指令的引用因为很多分析如活跃变量分析需要知道块内最后写入的变量。边的类型也要记录虽然简单的列表也能跑通但遇到分支分析时必须知道每条边是“条件为真”“条件为假”还是“无条件”。我习惯用一个字典存边的属性edge_attrs {} edge_attrs[(src.id, dst.id)] {type: true_branch, condition: b 0}这样后续做分支覆盖、条件覆盖时不用重新解析语法树直接查边属性就行。2.4 处理高级语言中的控制结构不同语言给CFG构建挖的坑不太一样。我用得比较多的是C/C、Java和Python简单说说几个典型结构if/else加上隐式fall-through边。C语言里如果if没有else条件为假时执行下一条语句这条边很容易被漏掉。我在做插桩时就因为漏了这条边导致覆盖率统计少了“条件为假分支”的覆盖。switch/case每个case是一个基本块break是跳转到switch出口。要注意的是C语言中case没有break时会fall-through到下一个case这种“穿透”边必须在CFG里体现否则分析结果会和实际执行完全不符。循环for/while/do-while循环头是循环条件的判断点循环体基本块和循环出口基本块都会指向它。构建CFG时循环会产生回边循环体内跳回循环头这也是后续识别循环结构、做循环优化的关键。判断回边的一个简单方法是看目标节点是否“支配”源节点但初学者可以先通过“目标节点在遍历栈中”来判断。异常处理try/catch/finally这是高级语言构建CFG最头疼的部分。异常可能在任何一条指令处抛出理论上每条指令都有一条隐式边指向catch块。精确建模非常贵通常保守做法是把整个try块视为一个基本块从该块画一条边到catch块再从catch块画到后续块。虽然丢失了精确的异常抛出点但很多分析已经够用。如果需要精确异常流得靠编译器中间表示如JVM字节码的异常表提供。函数调用CFG通常按函数为单位构建调用语句只在CFG中体现为一个普通节点边上标记被调函数。跨过程分析需要调用图CG配合这也说明CFG不是万能的但它是调用图的基础——没有CFG你连哪些位置可能触发调用都定位不准。3. 实操过程与核心环节实现手写一个简化CFG构建器3.1 准备输入定义适合分析的中间表示为了不陷入具体语言的语法解析我一般先把源代码转成一个简单的中间表示IR每条指令用一个三元组表示操作符、操作数列表、跳转目标信息。比如instructions [ {op: assign, args: [a, 1], jump: None}, {op: branch, args: [b, 0], jump: L5}, # if b 0 goto L5 {op: assign, args: [a, -1], jump: None}, {op: goto, args: [], jump: L6}, {op: label, args: [L5], jump: None}, {op: assign, args: [a, 2], jump: None}, {op: label, args: [L6], jump: None}, {op: assign, args: [c, [*, a, 2]], jump: None}, ]这个IR是伪代码级的好处是语言无关。实际项目中如果对接真实语言可以用Clang的AST或GCC的GIMPLE但核心的leader算法是通用的。3.2 实现leader算法和基本块切分用Python写一个简单的切分函数def find_leaders(instructions): leaders set() leaders.add(0) # 入口 for i, ins in enumerate(instructions): # 跳转目标 if ins[jump] and ins[jump].startswith(L): target_index find_label_index(instructions, ins[jump]) leaders.add(target_index) # 跳转指令的后继指令 if ins[op] in (branch, goto, return, throw): if i 1 len(instructions): leaders.add(i 1) return sorted(leaders) def build_basic_blocks(instructions, leaders): blocks [] for idx, leader in enumerate(leaders): end leaders[idx 1] if idx 1 len(leaders) else len(instructions) blocks.append(instructions[leader:end]) return blocks这里把所有跳转指令的目标label收集入leader集合还把跳转指令的下一条指令也加入leader这就是前面说的规则2和规则3。第1条规则通过初始add(0)实现。切分后的每个基本块内部指令只有最后一条可能是跳转指令前面的指令都是顺序执行。如果你的输入是AST则需要先遍历AST把if/while/for转成带label的跳转指令这一步通常称为“Lowering”。我建议初学时直接用文本IR练手把概念跑通了再对接真实语言。3.3 建立基本块之间的边有了基本块列表接下来就是根据最后一条指令类型连接边def build_cfg(blocks, instructions): block_by_start {} for idx, block in enumerate(blocks): start_line get_start_line(block) block_by_start[start_line] idx for i, block in enumerate(blocks): last_ins block[-1] if last_ins[op] goto: target find_label_index(instructions, last_ins[jump]) add_edge(i, block_by_start[target], unconditional) elif last_ins[op] branch: target find_label_index(instructions, last_ins[jump]) add_edge(i, block_by_start[target], true) # fall-through: 下一条指令属于下一个基本块 if i 1 len(blocks): add_edge(i, i 1, false) elif last_ins[op] in (return, throw): pass # 无后继终结 else: # 普通顺序执行连到下一个基本块 if i 1 len(blocks): add_edge(i, i 1, fallthrough)这里有个细节容易踩坑branch指令的false分支是顺序执行下一条指令但如果下一条指令刚好是某个跳转目标那么基本块划分时分支目标块可能不是按顺序紧邻的其实leader算法保证跳转目标肯定是一个新基本块的开始false分支的fall-through目标必然紧跟当前基本块之后除非分支指令被放在了基本块的中间这违背了基本块的定义。所以用i 1来访问false目标基本是安全的但为了严谨还是应该根据指令地址去定位下一个leader而不是简单用基本块索引。计算地址时可以用指令序号映射到基本块ID这样更稳。3.4 一个完整的小例子我用前面那个IR跑了一遍构建逻辑得到的基本块和边如下基本块ID包含指令后继BB01: a 1; 2: if b 0 goto L5BB1false, BB2trueBB13: a -1; 4: goto L6BB3unconditionalBB25: L5: a 2BB3fallthroughBB36: L6: c a * 2无你可以看到这其实就是个标准的菱形结构if的真分支和假分支在BB3汇合。如果读者想验证可以把这个CFG用Graphviz画出来节点写“BB0: a1; if b0”画出来非常直观。实际工具里我还会把每个基本块的入口行号和出口行号存下来方便后续映射到源码位置。3.5 从CFG获取关键信息支配树、回边、循环识别构建完CFG后有很多分析可以在图上做。我最早做的分析是“支配树”因为编译器优化和循环识别都依赖它。一个节点A支配节点B指的是从入口到B的每一条路径都经过A。计算支配树有经典的Lengauer-Tarjan算法但初学者可以先用简单的迭代数据流算法def compute_dominators(cfg, entry): dom {} for node in cfg.nodes: dom[node] set(cfg.nodes) if node ! entry else {entry} changed True while changed: changed False for node in cfg.nodes: if node entry: continue new_dom None for pred in node.preds: if new_dom is None: new_dom dom[pred].copy() else: new_dom new_dom dom[pred] new_dom.add(node) if new_dom ! dom[node]: dom[node] new_dom changed True return dom得到支配关系后如果把每个节点的直接支配者idom作为父节点就能构建支配树。有了支配树找回边就很简单一条从A到B的边如果B支配A那么它就是回边代表一个循环。这个判断在循环优化和路径分析里特别有用。4. 常见问题与排查技巧实录CFG构建和分析中的那些坑4.1 为什么我的CFG总是漏掉最后一个基本块新手最常遇到的Bug是图构建完成后发现CFG的出口节点不见了或者最后一个基本块没有任何前驱。原因通常是处理return/throw时忘了收集“当前基本块之后的所有指令”作为新的leader。看这段代码if x: return 1 y 2如果没有把return 1的下一条指令y 2设为leader那么y 2就会和前一个基本块合并在一起结果return和y2在同一个基本块里这完全违反了基本块的定义。我用leader算法时凡是遇到return、throw这类终止指令都会强制把下一条指令设为leader即使它不可达。这样CFG里会保留一个“不可达基本块”虽然它没有前驱但后续分析中可以通过不可达代码检测发现它。如果你不想保留可以做一轮活跃性分析把不可达块删掉但初学时最好保留因为不可达代码也是静态分析要报告的问题之一。4.2 条件边和fall-through边画反了分支覆盖率的统计依赖每条边的正确语义。我在做C代码覆盖率时发现有些工具报告的分支覆盖数字怎么都对不上最后定位到是我把true和false边交换了。原因是高级语言里if (a b)对应的IR可能是一条branch a b, Lfalse也就是条件为假时才跳转条件为真时直接顺序执行。这时候CFG中必须先弄清楚边属性记录的是“源指令的跳转条件”而不是“高级语言里的真/假”。建议在构建IR时就约定所有branch指令的第一操作数是跳转条件且跳转目标为“条件成立”时的目标不成立时fall-through。然后用一个字段明确标注避免二义性。4.3 循环和switch的case穿透导致路径爆炸路径爆炸是CFG分析里绕不开的话题。一个函数如果有两个if和一个循环理论上路径数量可能指数增长。实践中不要尝试枚举所有路径而是改用基于支配关系或数据流的抽象分析。比如做覆盖时边覆盖和基本块覆盖都是多项式可计算的但路径覆盖是NP难的。如果你非要计算路径覆盖可以限制路径长度或使用符号执行枚举有限路径。我在做测试用例生成时通常先用CFG算出所有可达边再用约束求解器去生成覆盖这些边的输入而不是去枚举完整路径。4.4 我该选择现成的CFG库还是自己写这个问题很多读者私信问过。我的观点是如果只是做学术分析或快速验证优先用现成框架比如LLVM的CFG、Java的Soot框架、Python的ast模块加networkx自己构建也行。但如果你想深入理解原理或者要处理自定义DSL、老旧代码自己实现一遍leader算法和CFG构建能帮你避开很多黑盒问题。我自己最初用networkx实现了整个CFG分析流程后面迁移到生产环境时把这些逻辑移植到C版本的LLVM pass里几乎不用改设计所以这个领域的知识迁移性很强。4.5 多个出口函数和中断处理的特殊场景C语言里的setjmp/longjmp、C的异常、Java的finally都会让CFG出现“多重出口”或“异常阴影边”。处理这些结构时最稳妥的方法是在构建CFG之前就确定语义边界要么忽略异常路径只做乐观分析并注释清楚要么为每个可能抛异常的指令都加入指向异常处理块的边但这样图会变得很密。我在做企业级代码扫描工具时采用的路子是“分层CFG”正常控制流是一层异常控制流是另一层分析时按需合并。这样正常路径的分析不会被异常边干扰而专门做异常流分析时可以单独遍历异常层性能和准确性都照顾到了。4.6 CFG与源码映射回退踩的坑构建CFG时如果只保留基本块ID后续输出告警、覆盖率报告时需要把CFG节点映射回源码行号这一步经常出问题。比如编译器优化后源码行号可能缺失宏展开后指令实际来自哪个文件哪一行都可能变化。我的经验是在构建基本块时提前把每条指令的源码位置文件、起始行、结束行保存下来CFG节点里存一个“行号区间列表”。这样无论后续做什么分析只要拿到基本块ID就能快速定位到用户可读的源码位置。不要等分析完了再往回找那时候指令和源码的映射关系早就丢了。5. 从CFG到实际应用我在项目里的三个落地场景5.1 用CFG优化测试用例生成我做过一个Python项目的自动测试用例生成工具核心逻辑就是先从源码构建CFG然后找出未被覆盖的边。每次生成新的测试输入就执行一次插桩后的程序统计哪些CFG边被走到。然后针对未覆盖的边回溯它的路径条件和约束用z3求解器生成满足条件的输入。这个流程里CFG是路径回溯的骨架从入口到目标边顺着CFG找到所有经过该边的路径再把路径上所有分支条件合取起来求解。虽然听起来复杂但CFG建对了后面每一步都是顺理成章的事。5.2 用CFG做死代码检测死代码有很多种其中一种“不可达代码”直接可以通过CFG的前驱关系判断。如果一个基本块没有前驱且它不是入口那么就是不可达。但要注意有些代码通过反射、动态加载调用静态CFG里可能误判为不可达。我的处理方式是先构建CFG跑一遍不可达检测再针对标记为不可达的节点做人工二次确认必要时把动态调用的入口加入白名单。实际工程中不可达代码的误报率通常不高但仍然建议不要把不可达检测作为唯一依据要配合符号执行或动态追踪。5.3 用CFG做路径敏感分析路径敏感分析是很多静态检查器的核心比如空指针检测。它需要知道“变量在哪些路径上可能为null”。做法是在CFG的边上附加路径条件然后把沿路径的变量状态作为“数据流事实”传播。这个分析本质上是把CFG当成一个状态机每个节点是程序点每条边是状态转移转移条件就是分支表达式。理解了这点后很多高级分析都是CFG的变形包括符号执行、抽象解释、模型检测。可以说CFG不是终点而是所有高级分析的起点。6. 基于CFG的扩展数据流分析的四个经典实例CFG建好后如果不做点分析总觉得白建了。这里分享四个最实用的数据流分析实例都是直接跑在CFG上的。6.1 可达性分析从入口基本块出发做BFS或DFS遍历CFG能到达的节点就可达不能到达的就是不可达代码。这个最简单但它是很多分析的基础。6.2 活跃变量分析活跃变量分析是寄存器分配的关键算法。对于每个基本块计算“在本块之前定义的变量在后来还会不会被使用”。它需要从CFG的出口开始反向遍历不断合并后继块的活跃信息。公式是in[B] use[B] ∪ (out[B] - def[B])out[B] ∪ in[S]S是B的所有后继。这个分析没有CFG根本跑不起来因为需要知道后继关系。6.3 到达定值分析到达定值分析用于检测“某变量在当前位置的赋值是否可能影响后续使用”。它是编译优化和静态检查的基础。和前一个分析类似但沿着CFG正向传播out[B] gen[B] ∪ (in[B] - kill[B])in[B] ∩ out[P]P是B的所有前驱。这个“交”和“并”的选择差异是初学者最容易搞混的。用CFG图来想到达定值关心的是“所有前驱都必须保证的信息”所以用交活跃变量关心的是“任何后继都可能用到”所以用并。6.4 可达路径摘要有时候不需要完整遍历CFG只需要知道从某个节点出发能否到达另一个节点。可以先对CFG做缩点强连通分量合并把循环变成单个节点然后做DAG上的可达性查询。这样能在O(VE)预处理后以O(1)或接近O(1)的速度回答很多“可达性”问题。我在做影响范围分析时经常用这个方法改了一个函数想知道哪些调用方会受影响先把所有函数的CFG合并成一个过程间CFG再做缩点和可达性查询比逐条路径遍历快了不止一个量级。7. 实操心得如何高效调试CFG构建工具7.1 用可视化调试CFGCFG是个图用纯文本日志调试非常痛苦。我建议把构建结果导出成DOT格式用Graphviz画出来一眼就能看出边的方向是不是反了、基本块是不是切错了。我的项目里加了一个环境变量DUMP_CFG1构建完成后自动输出每个函数的CFG图。遇到分析结果不对第一件事永远是看CFG图而不是看分析算法的代码。很多你觉得是“数据流算法bug”的问题实际是CFG本身的问题。这个习惯帮我省了无数时间。7.2 用断言校验CFG的性质CFG有一些不变量可以用断言自动检查。比如每个非入口基本块至少有一个前驱除非是孤立块每个基本块最多有两个后继普通判断无条件跳转所有边的目标节点必须存在入口节点不能被任何边指向除非有外部调用。我每次构建完CFG都会跑一遍这些断言能快速发现leader算法和建边逻辑的疏漏。特别是在支持异常处理的复杂IR里这个校验几乎救了我好多次。7.3 保持CFG与源码同步在大型项目上做分析代码每天都在变。如果CFG构建工具不随代码更新分析结果很快就会过期。我的建议是把CFG构建做成一个独立模块输入是AST或IR输出是标准CFG对象这样只要语法解析部分更新CFG构建逻辑基本不用改。同时要建立回归测试准备一组小函数用例把构建后的CFG序列化下来作为golden文件每次改动后对比差异。这样即使改了leader算法也不会悄悄破坏某些特殊情况。7.4 性能优化经验构建CFG本身很快但大规模项目里指令数量可能上千万条这时leader集合和边集合的存储方式就很重要。避免使用Python的类对象作为基本块节点而是用整数ID加并行数组存储邻接表边的属性不要存字典而是用独立的数组按下标索引。我第一次处理一个百万行代码项目时用Python list存BasicBlock对象导致内存占用超过20GB改成ID邻接表后降到2GB以内。如果你准备打造生产级工具这点值得一开始就注意。8. 结尾的小思考很多人学控制流图时只把它当成编译原理的一个考点背完leader算法就放下了。但我在实际项目里越来越觉得CFG就是程序员和程序之间的“思维桥梁”它把源代码从“给人看的文本”变成“可计算的图结构”让机器有了理解程序控制逻辑的抓手。无论是做覆盖率、找缺陷、还是做优化CFG都是那个绕不开的地基。如果你正打算写一个分析工具我建议先把CFG建扎实后面很多事都会顺很多。最后分享一个我自己常用的检查方法用你手上任意一个开源项目随便挑一个函数手动画出它的CFG再用工具验证。画错几次没关系多错几次你对基本块、边、支配关系这些概念的理解就会比看书深刻得多。别问我为什么知道我当年就是这么把CFG吃透的。