ReDoS 正则回溯炸弹：灾难性回溯排查与根治

ReDoS（正则表达式拒绝服务，Regular Expression Denial of Service）是藏在每一行校验代码里的隐形性能炸弹。当一个写得不谨慎的正则表达式遇到精心构造的恶意输入，匹配引擎会陷入“灾难性回溯”（Catastrophic Backtracking），耗时从毫秒级暴涨到指数级，CPU 瞬间被打满，接口随之雪崩。据 Cloudflare 的公开观测，暴露在公网的用户输入校验接口正是 ReDoS 的高发区，一次 0day 级别的 ReDoS 甚至能让整站不可用数小时。本文用可复现的代码示例，带你搞清楚灾难性回溯的成因，并给出从正则改写、原子组、超时到 CI 护栏的一整套根治方案。

一、什么是 ReDoS：当正则变成性能炸弹

绝大多数开发语言的正则引擎（PCRE、Python 的 re、Java 的 java.util.regex、JavaScript 的 V8 实现）都属于“回溯型 NFA 引擎”。它们匹配失败时不会简单地返回失败，而是会不断“回溯”尝试其它可能的路径。绝大多数情况下这没有问题，但当正则结构存在歧义分支时，可能的路径数会随输入长度呈指数增长——这就是 ReDoS。

它最危险的地方在于：正则语法完全合法、单元测试照常通过、压测也看不出问题，只有当攻击者投来一个特制字符串时，单条请求就能把 CPU 跑满。输入校验、URL 路由、日志解析、WAF 规则都是重灾区，而这类代码往往位于请求的最外层，没有鉴权兜底，任何人都能触发。

二、灾难性回溯的成因：NFA 与回溯

2.1 嵌套量词与交替的陷阱

灾难性回溯几乎都来自两类写法：嵌套的重复量词（如 (a+)+）和多选分支能匹配同一字符（如 (a|a)*）。引擎在“这个 a 归前一个 + 还是后一个 +”之间反复犹豫，于是把每一种切分都试一遍，复杂度直接退化为指数级。

2.2 为什么 (a|a)* 这种写法危险

当多个分支都能吃掉同一个字符时，引擎每消费一个字符都要枚举“走哪条分支”，尝试空间随长度翻倍。一旦字符串尾部还有一个无法匹配的错误字符，引擎就把前面所有分支组合全试一遍才肯放弃，于是单次匹配的时间随输入长度呈 2^n 增长。

三、一段代码看懂指数爆炸

下面这段 Python 能直观看到“指数爆炸”。把 25 改成 30，耗时可能从 0.01 秒跳到几秒；改到 40，单线程匹配可能卡上几分钟——这正是对外接口的 DoS 入口，而且攻击成本极低：攻击者只需发一个长字符串。

import time, re

pat = re.compile(r"(a+)+$")        # 危险：嵌套量词，存在灾难性回溯
payload = "a" * 25 + "!"           # 25 个 a + 1 个无法匹配的错误字符
t0 = time.time()
pat.match(payload)
print(f"耗时 {time.time() - t0:.4f}s")  # 25 个 a 很快；30+ 个开始指数级变慢

四、真实受害案例：从 Node 到 Nginx

ReDoS 不是理论攻击。Node.js、Python、Java 的默认正则引擎都是回溯型，历史上多个主流库（如旧版 validator.js、部分 WAF 规则）都中过招。最容易被忽视的一处是反向代理层：Nginx 的 location ~ 使用 PCRE，若 location 正则写得有歧义，恶意 URL 就能让 worker 进程 CPU 100%，拖垮整台机器（可对照《Nginx 反向代理完整配置》里关于 location 匹配的实践）。

它的破坏形态和数据库慢查询高度相似：都是“语法正确、单条极慢、并发即崩”。正如《PostgreSQL 慢查询优化》里讲的，一个没走索引的 SQL 能拖垮整个连接池；一个灾难性回溯的正则同样能让单进程卡死，进而引发雪崩。两者都属于“平时没事、一打就垮”的性能陷阱。

五、根治手段一：把正则改写回线性时间

最根本的解法是改写正则可避免分支爆炸。核心原则：去掉嵌套量词、用具体字符类代替能互相覆盖的多选分支、尽量让每个位置只有一条匹配路径。下面三组对照一眼就能看出问题所在。

# 危险：嵌套量词，存在指数回溯
bad = re.compile(r"^(a+)+$")

# 安全：一条路径到底，复杂度 O(n)
good = re.compile(r"^a+$")

# 需要“至少一个 a 后跟 b”时，别写 (a|a)*b，直接写 ab+
safe = re.compile(r"^ab+$")

六、根治手段二：原子组、占有量词与超时

6.1 原子组 (?>…) 一次性吃掉

原子组 (?>…)（Java、PCRE、.NET 支持）一旦匹配成功就不再把已吃掉的字符“吐出来”回溯，从根上消除了回溯空间。PHP/PCRE 还可用占有量词 ++、*+ 达到同样效果。如果正则无法改写，优先用原子组收口歧义分支。

6.2 Python 3.11+ 的超时参数

如果老正则改不动，至少给匹配加一道超时。Python 3.11 起的 re 支持 timeout 参数，恶意输入会在限定时间被强制中断；Go 的 regexp 默认使用 RE2 线性引擎，天然免疫 ReDoS，是追求安全的首选。

import re

# Python 3.11+：给正则匹配加超时，挡住 ReDoS 攻击输入
try:
    re.compile(r"(a+)+$").match("a" * 30 + "!", timeout=0.5)
except re.TimeoutError:
    print("正则超时，疑似 ReDoS 攻击输入，已拒绝")

七、动手自检：写个正则风险探针

在把正则合进主干前，最实在的做法是自己跑一遍“探针”：让输入长度递增，观察耗时是否超线性增长。一旦耗时在某个长度突然跳变，就能在本地复现 ReDoS，而无需等线上告警。

import re, time

def probe(pat, base="a", limit=45):
    for n in range(5, limit, 5):
        payload = base * n + "!"          # 尾部加一个必不匹配的字符逼出回溯
        t0 = time.time()
        try:
            pat.match(payload, timeout=2)
        except Exception:
            pass
        dt = time.time() - t0
        print(f"len={n:3d} 耗时 {dt:.4f}s")
        if dt > 1.0:
            print("⚠️ 出现超线性增长，疑似 ReDoS，请改写正则")
            break

probe(re.compile(r"(a+)+$"))   # 你会看到耗时在某个长度突然飙升

八、在 CI 加一道正则护栏

光靠人肉 code review 很难发现所有危险正则。把静态扫描塞进流水线，能在合并前拦截。社区工具如 safe-regex、vuln-regex、semgrep 都能扫出“星级”高风险模式，配合下面的 GitHub Actions 即可作为必过卡点。

name: regex-guard
on: [pull_request]
jobs:
  check:
    runs-on: ubuntu-latest
    steps:
      - uses: actions/checkout@v4
      - uses: actions/setup-node@v4
        with:
          node-version: "20"
      - run: npx --yes safe-regex-scanner ./src

搭建流水线的方法可参考《GitHub Actions 实战：从零搭建 CI/CD 流水线》，把这个扫描作为必过的卡点即可，新正则一旦命中高风险模式就直接阻断合并。

九、ReDoS 排雷清单

十、小结

ReDoS 不藏在语法错误里，而藏在“能跑但巨慢”的正则里。工程上三管齐下最稳：写法上避免嵌套量词与多选分支重叠；运行时优先线性引擎（如 RE2）或给匹配加超时；流程上把正则静态扫描塞进 CI 卡点。做到这三点，埋在输入校验里的性能炸弹就会变成哑炮——下一次写校验正则前，先拿探针跑一遍，成本不过几行代码。