正则回溯爆炸实测:24 字符卡 0.5 秒,29 字符卡 32 秒
一个表单校验把 CPU 打满
上周排查一个接口超时,最后定位到一行“看起来没问题”的校验正则:^(a+)+$。输入不是攻击流量,只是一段以感叹号结尾的字母串。字符串长度从 14 涨到 29,匹配耗时从 1.6 毫秒涨到 32 秒——每多一个字符,耗时大约翻一倍。
这不是某个引擎的 bug,而是回溯型正则的固有代价:嵌套量词让引擎对同一段字符尝试所有可能的切分方式,路径数随长度按 2 的幂增长。
复现与数据
环境 Python 3.13.14(Windows,单核),测试串为 "a" * n + "!",正则为 ^(a+)+$,每个 n 单独起进程计时,避免互相干扰。
| n | 耗时 |
|---|---|
| 14 | 1.58 ms |
| 18 | 8.74 ms |
| 20 | 36.8 ms |
| 22 | 140 ms |
| 24 | 559 ms |
| 26 | 2.36 s |
| 27 | 5.00 s |
| 28 | 14.2 s |
| 29 | 32.1 s |
相邻两行基本都是 2 倍关系,是标准的指数曲线。换句话说,四十个字符的输入就足以让一个请求线程长时间挂死。
给重复次数加上限救不了
直觉是给内层加个上限:^(?:a{1,64})+$。实测 n=24 时耗时 735 毫秒,比不加限制的 559 毫秒还慢;n=100 时直接超过 40 秒仍未返回。原因不难理解:上限只是把每个位置的候选切分从 n 种压到 64 种,路径总数依然随 n 指数增长,反而多了一层分组开销。
业务里更常见的样子
^(\w+\s?)*$ 这种“单词序列”校验,在标签清洗、标题校验、搜索词过滤里很常见。用 "word " * n + "!" 实测:
| n | 耗时 |
|---|---|
| 6 | 164 ms |
| 8 | 6.44 s |
| 10 | 超过 20 s |
八个单词、四十个字符,就要 6 秒多。日志里一条异常输入,足够把一个接口拖垮。
三种改造方式的实测
第一种,原子组或占有量词。Python 3.11 起支持 (?>...) 与 a++,PCRE、Java 也都有对应写法:
import re, time
text = "a" * 100000 + "!"
for pat in (r"^(a+)+$", r"^(a++)+$", r"^(?>a+)+$"):
t0 = time.perf_counter()
re.match(pat, text)
print(pat, round((time.perf_counter() - t0) * 1000, 3), "ms")
实测 10 万字符:原式 40 秒内未返回;^(a++)+$ 为 0.029 毫秒;^(?>a+)+$ 为 0.037 毫秒。原子组禁止引擎回退进已经匹配过的分组,回溯路径直接消失。代价是语义略微收紧,但对“校验”场景正是想要的效果。
同样的改法用在真实式子上:^(\w++\s?)*$ 处理 100 个单词耗时 0.395 毫秒,^(?>\w+\s?)*$ 为 0.022 毫秒,而原式在 8 个单词时已经是 6.4 秒。
第二种,把嵌套量词展平。(a+)+ 与 a+ 等价,(\w+\s?)* 可以改写成不带嵌套的 (?:\w+\s)*\w? 这类形式。凡是“分组里再套 + 或 *”的结构,都值得先问一句能不能不嵌套。改写后的 ^a+$ 处理 100 万字符只要 10.7 毫秒,是线性的。
第三种,入口护栏。在跑正则之前加长度上限和字符集预检,成本几乎为零:100 万字符的 str.isalnum() 耗时 34.3 毫秒,而一次长度判断只有 0.004 毫秒。绝大多数畸形输入长度异常,这一刀最便宜也最有效。
落地清单
- 校验型正则禁用嵌套量词,能用字符类就不开分组;
- 必须写复杂正则时,用支持原子组、占有量词的写法,或改用不支持回溯的引擎(RE2、Rust regex);
- 对用户输入先判长度,再判字符集,最后才交给正则;
- CI 里加一条静态检查,命中
\((?:[^()]*[+*])[^()]*\)[+*]这类结构就报警; - 改不动的老正则,放进独立进程或带超时的匹配器里跑,别让它占住主线程。
回溯爆炸真正可怕的地方在于:正常输入永远测不出来。单元测试不会拿四十个字符的畸形串去撞正则校验,压测用的也是合规数据。把长度上限和原子组当成默认习惯,比线上出事后再回来查要划算得多。
- 点赞
- 收藏
- 关注作者
评论(0)