正则回溯爆炸实测:24 字符卡 0.5 秒,29 字符卡 32 秒

举报
yd_243452805 发表于 2026/11/13 11:47:11 2026/11/13
【摘要】 用 Python 3.13 实测回溯型正则的指数爆炸:^(a+)+$ 匹配 n 个 a 加一个非法结尾字符,耗时从 n=14 的 1.58 ms 涨到 n=29 的 32 秒,每多一个字符约翻倍;给内层加 {1,64} 上限反而更慢。原子组 (a++)+ 与 (?>a+)+ 处理 10 万字符仅 0.03 ms,附三种改造方案与落地检查清单。

一个表单校验把 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 里加一条静态检查,命中 \((?:[^()]*[+*])[^()]*\)[+*] 这类结构就报警;
  • 改不动的老正则,放进独立进程或带超时的匹配器里跑,别让它占住主线程。

回溯爆炸真正可怕的地方在于:正常输入永远测不出来。单元测试不会拿四十个字符的畸形串去撞正则校验,压测用的也是合规数据。把长度上限和原子组当成默认习惯,比线上出事后再回来查要划算得多。

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0)

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。