1. 先从一段“看起来完全正常”的代码说起大概一年前组里有个同事在Perforce的Helix Core上提交了一段C代码CI里的静态分析任务立刻报了一个警告potential null pointer dereference。他觉得非常冤枉跑过来跟我说这段逻辑我在脑子里过了好几遍这个指针在这里不可能是空的工具是不是误报我没有直接回答而是把那段代码打开指着其中一个分支问他如果另一个线程在调用这个函数之前把那个指针释放了工具怎么会知道他愣了几秒然后明白了一件事分析工具并不是和人一样“看了一遍逻辑”而是在编译期间做了一套非常严谨的结构化推演——先画出程序所有可能的执行路径再沿着这些路径追踪数据的产生、传播和消亡。这套推演体系里最重要的两个基础就是今天要聊的控制流分析和数据流分析。如果你在Perforce生态里做过CI接入接触过Klocwork或其他静态分析工具大概率看到过这两个词但很少有人系统讲清楚它们到底在干什么。这篇文章我打算从零开始把这两个概念拆开揉碎讲清楚它们各自回答什么问题、底层是怎么计算的、又如何在真实的静态分析工具里配合起来查出空指针、数组越界、内存泄漏这些经典缺陷。内容不挑语言C/C、Java、Python里的思路是一样的但例子我会用C/C为主因为Perforce的Klocwork在C/C项目里用得最多。2. 控制流分析把“代码的走向”画成一张图2.1 基本块给顺序执行的语句分组控制流分析要回答的问题很直白一段代码从入口到出口有哪些可能的执行顺序但这不能靠人肉梳理尤其当一个函数有七八个嵌套if、两个while循环、中间还有switch和goto的时候人眼根本看不过来。所以工具做的第一件事是把代码切分成基本块Basic Block。基本块的定义是“一组只能从头进、从尾出的顺序执行语句”。换句话说只要进入这个块的第一条语句就一定会顺序执行到块的最后一条中间不会跳出去也不会从外部跳进来。还是举一个具体例子int process(int x, int y) { int z 0; if (x 0) { z x y; } else { z x - y; } return z; }这段代码里int z 0;自己可以看作一个基本块的开始因为它后面紧跟的是if判定if (x 0)本身是条件跳转指令也是一个块的结束z x y;和z x - y;分别在两个互斥分支里各自是独立的基本块最后的return z;是整个函数的出口也是汇合点又构成一个基本块。所以这个函数可以被切成5个基本块入口块、条件块、then分支块、else分支块、出口块。切分的规则并不复杂就是一个函数里找到“跳转目标的起始语句”和“跳转指令的后一条语句”把整段代码按这些断点切分仅此而已。2.2 从分支、循环到控制流图骨架是怎么拼起来的切出基本块之后再根据代码原有的跳转关系把它们连接起来就得到了控制流图Control Flow Graph简称CFG。CFG本质上是一张有向图每个节点是一个基本块每条边代表一个可能的跳转方向。还是上面那个函数CFG大概是这个样子入口块有一条边指向条件块条件块有两条边分别指向then分支和else分支两个分支块各有一条边指向出口块。如果你把这个图画出来会发现“汇合点”是一个很有意思的结构因为从then和else两条路径都能到达这里那么在这个点上数据就可能带有“两种来路”的信息这个信息恰恰是后续数据流分析的关键。循环在CFG里就更有代表性比如int sum 0; for (int i 0; i 10; i) { sum i; }转换成CFG后大概包含入口块、初始化块、条件判断块、循环体块、增量块、出口块。其中条件判断块有一条边回到循环体循环体执行完再通过增量块回到条件判断块因此CFG上会出现一条回边back edge。也就是从这一点开始图就不再是简单的树状结构了而是一个带环的有向图。千万别小看这个“环”。正是因为有环数据流分析的计算才不能只做一遍而需要反复迭代这个我们在下一章会细讲。在此之前只要记住控制流分析构建的CFG是所有后续静态分析的地基没有这张图任何“路径”相关的分析都无从谈起。2.3 光看图能发现哪些问题CFG本身虽然不分析数据但单靠它就能发现好几类问题这也是控制流分析独立存在的价值。第一是不可达代码。如果CFG里某个节点没有任何一条从前驱节点指向它的边那这个节点对应的代码永远不会被执行。比如int foo(int x) { if (x 0) { return 1; } return 0; int y x * 2; // 永远执行不到 }int y x * 2;前面的return 0;已经结束了函数的执行路径所以这个语句在CFG里就是一个没有任何“入边”可达的孤立节点。工具可以直接报unreachable code。第二是圈复杂度Cyclomatic Complexity。这个概念主要度量代码的复杂程度原则是CFG中边的数量减去节点的数量再加上2得到的结果大致等于“独立的线性路径数量”。圈复杂度越高的函数分支越多测试时需要的用例数量也越多出bug的概率自然就高。很多静态分析工具会在控制流分析阶段顺便把这个指标算出来供开发者评估模块质量。第三是死循环风险的结构性提示。虽然从CFG上判断“一个循环会不会真的永远跑下去”属于更深层次的数值分析问题但循环是否存在复杂嵌套、是否存在仅有break才能退出的结构这些都可以在CFG基础上做初步评估。Klocwork等工具的控制流分析器在分析这类结构时会为后续的数据流分析确定循环边界信息比如标记哪些循环是“不可预测边界的”。简单总结一下控制流分析解决的是“程序哪些路径存在”的问题它的输出是一张图一张精确到基本块和跳转边的有向图。接下来要讲的数据流分析就是在这张图上“跑数据”。3. 数据流分析沿着路径追踪数据的“命运”3.1 三条核心问题到达定义、活跃变量、可用表达式如果说控制流分析关心的是“路”数据流分析关心的就是“路上运的货”。它要回答的问题是在程序的某一个具体位置某个数据处于什么状态这个状态是从哪里来的之后又会到哪里去经典的数据流分析主要围绕三类问题展开到达定义Reaching Definitions在程序点P上一个变量x的当前值可能来自哪些赋值语句这些赋值语句称为“到达P点的定义”。比如在汇合点x可能来自then分支的赋值也可能来自else分支的赋值那这个汇合点上x的定义集合就有两个元素。活跃变量Live Variables在程序点P上变量x的值在后续的执行路径中是否还会被读取如果会那x在这里就是活跃的live否则就是死的dead。这是一个反向分析的经典案例因为我们需要从函数出口倒推。可用表达式Available Expressions在程序点P上某个表达式比如a b之前是否已经被计算过并且参与计算的所有变量都没有被重新赋值如果是那这个表达式在这里是“可用”的编译器可以据此做公共子表达式消除。这个指标对编译器优化至关重要对缺陷检测的参考价值没有前两个那么大但理解它能帮你建立更完整的体系认知。这三个问题看似独立但计算框架完全一致。都是先定义每个基本块的**生成gen信息和杀死kill**信息然后在CFG上沿着边的方向或逆着边的方向传递集合不断合并、迭代直到整个图上的信息不再变化。3.2 数据流方程与迭代求解为什么程序会“反复跑”我先用“到达定义”来展示经典的数据流方程这也是理解整个数据流分析的核心。对于任意一个基本块B定义两个集合gen[B]在B内部生成的、能流出B的定义。例如z x y;这条语句如果它在B里那它产生的定义z x y就会被加入gen[B]。kill[B]在B内部被重新赋值的变量它之前的定义都会被杀掉。比如B里有z x - y;那函数里其他给z赋值的定义在这个基本块的出口处都不再有效所以那些赋值语句的定义节点会被标记为“被这个块kill掉的”集合。设in[B]是进入B之前已经到达的定义集合out[B]是离开B之后仍然有效的定义集合。那么有in[B] 所有前驱块 out[P] 的并集out[B] gen[B] ∪ (in[B] - kill[B])这段公式的意思很直观进入当前基本块的数据就是该块所有前驱节点流出的数据总和离开当前块的数据等于“本块自己生成的”加上“从前驱流入但没被本块重新赋值杀掉的”。第一次代入时除了入口块大多数基本块的in和out都是空集。然后算法会在CFG上不断重复计算因为图里有环、有汇合前面的计算会改变后面的输入后面的计算结果又可能反过来影响前面——所以这个方程必须反复迭代直到所有基本块的in和out集合都不再变化。这个稳定状态在数学上叫不动点fixpoint。我当年第一次学这个迭代的时候也觉得绕后来用一个生活类比才真正理解你在一座城市的所有路口设置检查站车辆数据定义从不同方向进入到达路口后有些车辆被拦下kill有些新车被放行gen。由于路网有环、有回堵你不可能只巡逻一次就把每个路口的情况摸清必须一遍一遍地记录、比对、更新直到某个时刻所有路口的记录都稳定下来才可以保证每个路口的记录覆盖了从任意起点出发能到达这里的全部车辆。活跃变量分析的计算方向正好相反从出口倒推到入口方程结构类似但“前驱”变成“后继”“入口”变成“出口”本质还是同样的不动点迭代。工作列表算法Worklist Algorithm是工程里最常用的实现方式维护一个待处理基本块队列每次从队列里取出一个块根据后继/前驱更新它的集合如果发生变化就把相关邻居重新加进队列直到队列为空。3.3 一个贯穿始终的例子从定义到使用的追踪回到第2节的process函数我们现在用活跃变量分析走一遍感受一下这个过程。int process(int x, int y) { int z 0; if (x 0) { z x y; } else { z x - y; } return z; }活跃变量是反向分析所以从出口块开始。出口块里return z;读取了z因此z在出口块入口处是活跃的。倒推到汇合点时z仍然活跃因为两条后继路径then块和else块都引用了z的值。再往前推到条件块此时z虽然已经在前面被赋过值但return z在后面要用所以z在整个分支结构里始终是活跃的。而x和y只在条件判断表达式x 0中被读取一旦进入then或else分支x和y就不再被后续代码读取所以x和y在分支汇合点之后是“死”的但在条件块入口处是活跃的。这个结果有什么工程价值如果分析器发现在某一个赋值之后该变量的后续路径里没有任何读取点就会判断这是一个死存储dead store给出警告。比如你把z x y;改成算完以后并没有用z而是直接return了其他值那这行赋值就是在做无用功属于典型的编码缺陷。空指针分析也是同样的思路。分析器会建立“定义到使用”def-use的链路当看到p maybe_get_null();时它会把这个定义传播到后续所有使用点如果使用点里有p-field或*p这类解引用操作再结合路径上是否有空值检查就能判断潜在的空指针解引用路径。这里“路径上是否有空值检查”这一步就是数据流分析在CFG上做分支条件追踪的典型案例。4. 在Perforce环境里两者如何配合从CFG到缺陷检测4.1 Klocwork到底在编译期做了什么讲完理论回到Perforce的语境里。很多人一听到Perforce第一反应是Helix Core这个版本控制工具但在Perforce官方生态里还有一条重要的产品线是静态分析Static Analysis比较有代表性的就是Klocwork。Klocwork的身影在不少汽车、半导体、航空航天企业的CI流水线里都能见到因为它支持C、C、C#、Java、Python等各种语言还能对接主流构建系统。那Klocwork在分析一份代码时内部到底做了什么第一步它并不是直接读源码文本而是先调用编译器前端比如针对C/C通常会对接Clang或GCC的编译接口把源码解析成抽象语法树Abstract Syntax TreeAST。语法树只保存语法结构不包含执行顺序的语义。第二步它会从AST构建CFG也就是我们前面说的把代码切分为基本块、连成有向图。第三步在CFG之上做数据流分析包括到达定义、活跃变量、区间分析、符号执行等。最后把分析结果与内置的缺陷模型做匹配输出对应的告警。这里有一点值得注意Klocwork构建CFG时用的不是“理想化模型”而是会考虑真实编译器在C/C标准里允许的各种隐式转换、短路径求值short-circuit evaluation、异常处理跳转等。比如a b这种表达式表面上是一行实际上b的执行条件隐含了“a为真”CFG里会为它生成真正的分支节点。如果不做这一步精细处理控制流图就会失真后面的数据流分析结果自然也不可信。4.2 数组越界、空指针、内存泄漏是怎么查出来的有了CFG和数据流分析这两个引擎一系列常见缺陷的检测就变成了“套模型”的问题。数组越界依赖的是区间分析Interval Analysis一种特殊的数据流分析它追踪的是“一个变量的取值范围”而不是定义集合。比如int buf[8]; for (int i 0; i 8; i) { buf[i] 1; }分析器从i 0出发经过循环体时发现i的取值从0开始逐步增大而且基于i 8这个分支条件可以推断i在进入循环体时的范围是[0, 8]。下标i被用于访问buf[i]而buf的长度是8合法的下标范围是[0, 7]于是工具在i的取值集合里发现8这个越界点就在buf[i] 1;这一行报出数组越界。这里的整个分析路径——从赋值定义、分支条件约束到取值区间传播——就是数据流分析在CFG上的一种具体应用。空指针解引用则融合了“定义到达分析”和“分支条件分析”。如果代码里有这样一段void foo(Node *p) { if (p) { apply(p); } p-next NULL; }分析器会看到p-next NULL;这一行可达的路径包括“经过if但不满足if条件的那条路径”。在那种路径上p的取值范围是“逻辑非真”也就是可能为NULL。因此它在最后一行报出潜在空指针解引用。这就是为什么有时候开发者觉得“我在前面明明判断了啊”工具还是报警——因为它看到的不是某一条人为设想的路径而是CFG上所有可达的路径。内存泄漏/资源泄漏依赖的是更复杂的跨过程分析分析器记录malloc、new、open等资源分配点的返回值建立“资源句柄”的定义节点然后追踪这个句柄在后继所有路径上有没有对应free、delete、close的调用。如果有某条路径一直流到函数出口都没遇到释放那这条路径上就存在泄漏。跨函数调用时分析器还会结合函数摘要summary来计算被调用函数是否释放了传入的指针是否把指针存入全局变量等等。污点分析Taint Analysis也是数据流分析的一个重要变种。它首先标记数据来源source比如用户输入、网络消息、环境变量再标记危险操作sink比如system()、strcpy()、SQL拼接查询然后沿着数据流分析从source到sink的路径是否存在如果存在且路径上没有经过净化函数就报告一个漏洞。这在Klocwork的安全审计功能里很常见尤其用于排查命令注入和缓冲区溢出。4.3 路径敏感与路径不敏感误报率的分水岭同样是数据流分析实现层面的“敏感度”差别非常大这是工具之间误报率天差地别的根源。路径不敏感Path-insensitive分析在合并分支时会把两个分支的条件信息都丢掉统一认为“要么走这个分支要么走那个分支”但不记录每个分支的具体条件。这种分析速度快、扩展性好但很容易产生误报。比如if (x 10) { // 这里x一定大于10 use(x); }路径不敏感分析不会记住x 10这个约束它只知道确实存在一条路径可以从左边进入这个分支也知道存在一条路径x可能是任意值于是凡是涉及“初值可能为负数”之类的检查就都可能误报。路径敏感Path-sensitive分析则会把分支条件作为约束纳入数据流状态中。进入某分支时分析状态会额外携带“x 10”这个条件后续更新x时也会更新这个取值范围。Klocwork对许多检查器采用的是路径敏感分析尤其是空指针、数组越界这类需要精确取值范围的检查因为只有路径敏感才能把误报压到可接受水平。但路径敏感的技术代价是状态爆炸。每多一个分支分析的可能状态就翻一倍遇到循环理论上状态数是指数级增长。工程上解决这个问题主要靠两种手段一是状态合并state merging在汇合点把取值范围相似、行为预计一致的状态合并成一个降低后面路径的规模二是搜索剪枝对已经无法触发目标缺陷的路径提前终止分析。这块的实现复杂度和调优经验基本就是各个静态分析工具之间的核心差距所在。5. 工程落地中的几个权衡5.1 全量扫描与增量分析的时间成本理论再完备放到Perforce仓库里一个几十万甚至几百万行代码的项目上落地难题就变成了“分析一次要花多久”。全量扫描听起来最省事每次跑CI把整个代码库拉下来跑一遍全量分析。但代价很大一个大型C项目全量Klocwork分析跑几十分钟甚至几个小时都不稀奇。所以我见到的大多数团队不会每次都全量跑而是采用增量分析策略。增量分析的核心是“变更驱动”。提交到Perforce的变更列表changelist通常只包含少数文件分析器只需要对被修改的文件以及依赖这些文件的文件重新做CFG构建和数据流分析。Klocwork在增量模式下的反应速度会快非常多因为之前分析过的函数摘要可以缓存复用。CI上比较务实的配置是每次提交跑增量分析抓修改直接引入的新问题每天定时跑一次全量分析处理那些跨文件、跨模块的大规模问题。这里要提醒一个很多人容易踩的坑增量分析如果只分析“变更文件本身”跨文件问题会被漏掉。比如你改了一个头文件这个头文件被几百个源文件包含那这条变更的影响面就远超changelist里那两三个文件。因此要么让构建系统把直接依赖变更头文件的文件都纳入分析范围要么至少保证全量任务跑得足够勤不要让问题积累太久。5.2 误报、漏报和人工确认之间的平衡任何静态分析工具都不可能做到零误报和零漏报这个平衡点需要团队自己把握。我先说误报。路径敏感分析虽然能压掉不少误报但对多线程并发、动态别名、位运算、浮点比较等场景依然容易失真。比如两个指针都指向同一块内存分析器无法准确建模这种别名关系时就可能把“通过指针A释放了内存再通过指针B使用”误判成双重释放或空指针。再比如reinterpret_cast把一个整数转成某个合法内存地址分析器通常无法推导这种转换后的具体指向也会产生误报。处理误报的正确姿势不是直接关掉检查器而是学会用分析工具自带的抑制suppression机制在代码里加注释说明“这条告警经过确认是安全的原因是……”。这样后续的代码评审里别人能一眼看出这里人肉判断过而不是工具报了但没人处理。压制理由写得含糊其辞比继续放任误报更危险因为团队很快会对告警丧失信任最终把整个工具当摆设。漏报的情况也值得心里有数。路径敏感分析虽然是好东西但它对状态合并策略的激进程度直接决定漏报率。状态合并得太激进一些罕见但真实的缺陷路径就会被吞掉太保守分析又会超时。所以工具默认配置通常是在速度和精度之间取一个折中。我的经验是对于高风险模块比如安全相关、底层驱动、解析器宁可把分析配置调严格一些接受分析时间变长对普通业务代码默认配置就够用。5.3 把静态分析接入Perforce CI流程的配置建议最后聊点实操如果你正准备把静态分析接入Perforce的CI流水线几个关键点可以参考。第一分析任务和构建任务尽量共享编译数据库。Klocwork支持通过kwinject或者类似的方式抓取构建过程中的编译命令保证它看到的编译选项和你实际构建一致。编译选项不一致会导致解析偏差分析结果虚高且不稳定。不同构建机器上编译器版本不一致也会导致同一个代码两边的分析结果对不上所以CI节点上编译器版本一定要锁定。第二门禁quality gate的设定不要一上来就拉满。直接把“新引入问题为0”设置为硬性门禁大概率会在上线第一周就被迫给一堆难搞的告警豁免门禁形同虚设。更靠谱的做法是先跑观察模式只在CI报告里展示新增问题不阻断提交跑上一两个迭代等团队对工具的行为模式有感觉了再针对明确的高风险告警类别开启阻断。第三让代码所有者来认领告警。静态分析的告警本质上是一份“技术债台账”如果所有告警都堆在CI维护者身上维护者很快就会被磨死。建议按目录或模块把告警归属到对应的代码所有者评审时把告警作为评审检查项之一。我的经验是当每次提交的告警都直接挂在修改者的名下时新引入问题的数量下降比任何制度都明显因为这本质上改变了人的行为模式。第四定期清理静态分析的抑制规则和配置。很多团队的过滤规则filter是半年甚至两年前某次误报之后临时加的加完就没人再管。随着工具版本升级规则可能已经没有任何必要。清理掉这些陈旧规则才能避免告警被误伤也才能让全量分析的结果真正反映代码库的健康状况。最后再说一个个人体会我在实际项目里碰到过很多次开发者把“工具报警”当成“工具在找茬”但在我见过的大多数Case里最终定位下来工具指出的确实是一条真实的、被开发者忽略的执行路径。尤其是在Perforce这种多分支、多并行开发环境里代码审查者只看diff往往看不到“另一条分支里这个变量被改成了什么”这种跨变更的交互问题而数据流分析恰好擅长这个。所以与其把静态分析当成一个机械的质量检查员不如把它看成一位永远不睡觉、永远不说累的代码评审搭档——它会漏它会误报但它的覆盖面和耐力远超任何一个人肉评审员。真正有经验的团队不会追求“一次配置永久安宁”而是在日常迭代里不断校准它、喂养它、偶尔清理它。这样你的CI门禁才会真正有价值而不是给全组人添堵。
