跳转至

How Semgrep Cut Taint Analysis Time by 75%

📊 Level ⭐⭐⭐ | 9.6KB

Semgrep Pro Engine 1.158.0+ ships a redesigned taint analysis engine that is up to 75% faster on full scans — the win came not from a new algorithm but from noticing the same work was being done twice. 这是三篇性能系列的第二篇，改动以第一篇介绍的 OCaml 连续 profiler Pyro Caml 做论证与验证，作者把成功归给"拿到硬数据而非凭直觉"与做一次、别做两次两条。

摘要

Semgrep 的 Pro Engine 从 1.158.0 起把跨文件（interfile）分析与原本的 intrafile 数据流合并为"只跑一遍"，全量扫描最高提速 75%，部分仓库超过 3 倍。

被删掉的第二遍不是废码，而是历史上为回避"把 intrafile 数据流搬进新框架并证明输出等价"而留下的重复计算：它丢弃已算好的 taint config，把 taint signature 当作环境交给旧代码，然后重算 config、重访所有函数、再做一遍 dataflow。

核心要点

  • P95 全量扫描时长：10 分钟 → 7 分 30 秒（约 25%，与基准仓库初步测得数字吻合）。
  • P99 全量扫描时长：从"噪声很大的平均约 45 分钟"变为"更稳定的 35 分钟"。
  • max scan time：此前几乎贴着 12 小时硬上限（平台绝对上限），改动后在 12 小时以下波动更大、常长时间低于上限。
  • CPU 画像：53 天 CPU 时间中第一遍 taint 约 18 天、第二遍约 7 天；第一遍单独约占总 CPU 三分之一且不可并行。改动后 taint 占总 CPU 约 50% → 33%，被并行比例约 50% → 75%。
  • 单仓库墙钟：repo1 9 小时 → 5 小时 20 分；repo2 3 小时 20 分 → 50 分钟。
  • 验证链路：重构后 200+ 测试失败（按语言分诊）→ 数十个已核对结果的基准仓库得出初步 ~25% 加速 → 生产 1% 扫描 shadow 一周，约 100 个仓库结果不同（多因超时减少）→ 保留回退开关。
  • 关键位置：第二遍 taint 位于 Pro_scan.scan_exn.ProDeep；Deep_scan_helpers.create_index 现在负责过滤大量无用工作并提升并行度。

深度分析

为什么"先拿到 profile 再开工"战胜了凭直觉猜瓶颈

团队对瓶颈的直觉其实很准，但这不足以支撑大改动：这段代码之上累积了三年工程，任何语义漂移都会以"噪声"形式暴露给用户——若用户某天发现一个 SQL 注入告警无故消失，即便扫描快了一倍，信任也会下降。所以"跑一遍显然更快"是常识，却仍需硬数据，否则可能白干一个季度而什么都没变快。

Pyro Caml 给了证据，也教会怎么读 profile：第二遍 taint 的调用栈顶端是 Stdlib__Domain.spawn.body（在并行域中），而第一遍不在该子树下，因此是实打实的墙钟时间、不可并行。口径必须校准——那是 CPU 时间不是墙钟时间（6 核上跑 10 分钟 = 1 小时 CPU），且是"1% 扫描全部 profile 之和"，一次 24 小时的极端扫描就能把图拉成同样形状。结论仍成立：第一遍约占三分之一总 CPU 且加核无解，后续 tracing 亦印证假设，同一个 profiler 事后又量出了并行比例约 50% → 75% 的改善。

那"第二遍"到底重复算了什么

Interfile 流程本身清晰：先建 naming environment（判定 file1 中调用的 foo 即 file2 中定义的那个），再按规则计算 taint config——每条规则定义四类模式匹配：sources（用户可控输入）、propagators（传播 taint 的调用）、sanitizers（标记为安全）、sinks（危险位置如 eval）；随后对每个匹配跑 dataflow，判断 source 能否到达 sink 并跨文件追踪，产出 taint signature（"哪些 source 可能到达哪些 sink"的紧凑编码）。

按常理，接下来只需用 signature 校验 sink 上的条件。但实现为了不动更细粒度的 intrafile 数据流代码、也为了省去"证明新旧输出一致"的成本，选择丢弃 config，把 signature 作为环境传入既有 intrafile 代码，然后重算 config、重访所有函数、再做大批 dataflow，最后才做条件检查——即"run taint twice"。Iago Abal 复盘："如果当时多花几周，本可以只跑一遍。"

为什么取消这一遍能保持语义：第二遍算出的 config 是从同一份源码确定性可推导的，它重走的数据流也已被第一遍的 signature 编码。单遍设计保留"signature 作为环境"的角色，只是把 config 生成与 dataflow 折叠进一次遍历。团队没有当它"显然等价"：200+ 失败测试按语言分诊（如 Python 顶层语句到函数调用的 dataflow 只存在于第二遍），再经基准仓库比对与生产 shadow A/B。精度甚至略升——部分 dataflow 步骤不再超时，少超时即少漏报。

尾延迟（P95/P99/max）为什么比中位数更能说明问题

对外可见的是墙钟时间，而文中报的都是全量扫描（diff 扫描只扫改动文件，瓶颈在别处）。最值得读的是 max scan time 的形状变化：改动前它几乎被钉在 12 小时，而 12 小时并非工作量估计，而是平台绝对上限——曲线贴上限意味着有一批大仓库实际处于"被截断"状态。改动后最大值常远低于上限，大仓库需追加资源才能跑完的概率显著下降，新用户接入时要调的旋钮也随之减少。

P99 的价值在一致性：45 分钟的平均值本身噪声很大，35 分钟则是更稳的基线。稳定的耗时分布让性能回归告警可设、后续优化可归因——图中那两条红线（一次影响性能的事故）正是注脚：基线稳定，才能把事故影响与代码变更效果分开看。

intra-procedural 与 interfile：代价、精度与"缓存"的真正形态

2021 年首版 taint 只有 intra-procedural 能力：单文件内能看清数据流，但"输入进了另一文件定义的函数、该函数里才有 eval"看不见；跨文件能力（interfile）是用户长期诉求，2023 年 2 月随 Pro Engine 发布。每提升一层作用域，都同时换来召回率与成本。

成本大头在内存而非算法：interfile 需要近似全程序的中间状态（naming environment、整套 config），而 OCaml 5.0 之前只能 fork 进程做并行，内存占用按进程数成倍放大。这勉强支撑 intrafile，却撑不起"跑一遍"——那必须一次性持有大量 config 与解析后源码，否则要付序列化落盘代价。因此项目真正的前置条件是 OCaml 5 multicore：不是绕开内存问题，而是等运行时成熟后直接简化算法。

更本质的一层是"缓存 vs 消除"：收益来自消除了一个无需跨运行失效的重复推导——第二遍的输入第一遍在同一进程内已有，属于执行内去重而非缓存命中，故没有失效面；改为跨运行缓存则要承担结果陈旧的风险。

实践启示

  1. 先 profile，再动手；改完再 profile 一次。 直觉只能指出候选瓶颈，数据才能把它变成值得投入的项目；同一工具事后还能量化收益。
  2. 读 profile 必须校准口径。 分清 CPU 时间与墙钟时间、并行（Domain.spawn）与串行子树；采样聚合视图是假设生成器而非证据。
  3. 数一数每个计算跑了几遍。 "这件事必须做两次吗？"是设计层问题而非微观调优；"为避免搬迁代码而重复计算"的历史妥协，会复利成三分之一的总 CPU。
  4. 成本集中时盯尾部而非中位数。 优化付费用户感知的 P95/P99、max 与巨型仓库；分布变稳本身就是收益，它让回归告警与归因成为可能。
  5. 把"语义不变"当成独立工作量排期。 预期有成批（此处 200+）失败测试需分诊、基准仓库比对、生产 shadow A/B，并保留回退开关——这是"告警不会凭空消失"的保险。
  6. 优先消除，谨慎缓存。 执行内可证明等价的去重没有失效面，跨运行缓存则引入陈旧风险；先确认并行前置条件（fork 放大内存，multicore 才让"一次持有全部状态"可行），再定算法形态。

关联

→ 原文存档