输入只多了 4 个字符，正则的工作量变成 16 倍

一个校验输入格式的正则，测试用例全部通过，线上也跑了很久。某一天一条几十个字符的输入让一个线程的 CPU 长时间占满。这条输入和正常输入只差最后一个字符：正常输入能匹配，它差一点匹配不上。

Java 的 java.util.regex 用回溯的方式匹配：遇到有多种走法的地方先选一种，走不通再退回来换另一种。输入能匹配时，通常第一种走法就成功了；输入差一点匹配不上时，引擎要把所有走法都试完才能下结论。走法的数量由表达式的写法决定，有的写法下它随输入长度按指数增长。

这类问题有两个容易忽略的地方：性能测试用的几乎都是能匹配的输入，测不出来；触发它的输入可以由外部用户构造，所以它同时是一个拒绝服务的入口（ReDoS）。

本文用一个确定的指标把回溯的工作量数出来，并且在 JDK 8 和 JDK 25 上各跑一遍，因为两个版本的结果不一样。实验见文末。

一、把工作量数出来

Pattern.matcher 接受的是 CharSequence。给输入包一层，统计 charAt 被调用的次数，就得到一个不受机器快慢影响的工作量指标：

final class Counting implements CharSequence {
    final String s; long calls;
    public char charAt(int i) { calls++; return s.charAt(i); }
    // length、subSequence 直接委托给 s
}

对 (a+)+b 做两组测试，输入分别是 n 个 a 加一个 b（能匹配）和 n 个 a 加一个 !（差最后一个字符）：

输入	n=10	n=14	n=18	n=22	n=26
能匹配（JDK 8 与 25 相同）	13	17	21	25	29
差一个字符，JDK 8	3070	49150	786430	12582910	超过 2 亿
差一个字符，JDK 25	121	225	361	529	729

能匹配的输入只需要 n+3 次。差一个字符的输入，在 JDK 8 上每增加 4 个字符工作量乘以 16，也就是每个字符翻一倍；n=26 时超过了实验设的 2 亿次上限。

图 1 · 实测：纵轴是匹配过程中读取字符的次数（对数刻度），横轴是输入里 a 的个数，输入的最后一个字符让匹配失败。(a+)+b 在 JDK 8 上每多 4 个字符增长 16 倍；JDK 25 上同一个表达式只按平方增长；给它加上一个反向引用，JDK 25 上又回到了指数增长。改写成 a+b 之后在两个版本上都是线性的。

二、指数从哪里来

(a+)+ 的意思是「一段或多段 a」，而每一段又是「一个或多个 a」。同样一串 aaaa，可以看成一段四个，也可以看成两段（1+3、2+2、3+1）、三段、四段。n 个 a 一共有 2 的 n-1 次方种分法。

输入能匹配时，引擎用贪婪的走法一次吃完所有 a，接着匹配到 b，结束。输入以 ! 结尾时，b 匹配失败，引擎退回去换一种分法再试，直到所有分法都失败。每一种分法的结局其实都一样，但回溯引擎不记得「这个位置已经失败过」。

图 2 · 4 个 a 已经有 8 种切法，每多一个字符翻一倍。输入以 ! 结尾时，每一种切法的结局都一样，回溯引擎却不记得「这个位置已经失败过」，只能全部试完。实测在 JDK 8 上 n=26 时超过 2 亿次读取；改写成 a+b 后同一段输入只有一种切法，n=26 时 53 次

容易出问题的结构有一个共同点：同一段输入可以被表达式用多种方式切分。常见的形态：

• 量词套量词：(a+)+、(a*)*、(\w+\s?)+。最后一种很有迷惑性，它想表达「用空格分开的单词」，但空格是可选的，于是一个长单词可以被切成任意多个「单词」。
• 相邻的量词能匹配同样的字符：\d+\d+、.*.*=.*。
• 分支之间有重叠：(a|ab)+、(\w|\d)+。

真实代码里它们往往藏在更长的表达式里，比如校验逗号分隔的数字 ^(\d+,?)+$、校验邮箱或域名的 ^(\w+[.-]?)+@…。

三、JDK 9 之后好了一部分，不是全部

上表里 JDK 25 的一行不是指数，而是 (n+1) 的平方。JDK 9 起，Pattern 对一部分嵌套量词加了记忆：在同一个位置已经失败过的尝试不再重复。教科书上的例子在新版本上因此不再爆炸，这也是「我试了一下，没复现」的常见原因。

但这个优化有适用条件，而且没有写进 Pattern 的规范。同样的结构稍作变化，JDK 25 上仍然是指数增长：

表达式	变化	n=10	n=14	n=18	n=22	n=26
(["'])(\w+\s?)+\1	表达式里有反向引用	5117	81917	1310717	20971517	超过 2 亿
(a+)+?b	外层量词是懒惰的	3070	49150	786430	12582910	超过 2 亿
((a+)+)+b	多套一层	6119	98271	1572823	25165775	超过 2 亿
(a{1,10}){1,10}b	有界重复	3068	46627	550332	4510014	26293876

第一行最值得注意：「引号里是若干个单词，前后引号要一致」是很自然的写法，反向引用 \1 一出现，记忆就不再生效。

所以不能把运行时版本当成保护。升级 JDK 会让一部分表达式变快，但表达式是否安全仍然要逐个确认；在旧版本上跑的服务，教科书例子仍然是指数的。

四、改写

改写的目标是让同一段输入只有一种切分方式。

去掉不必要的嵌套。 (a+)+b 与 a+b 接受的字符串完全相同，后者是线性的（n=26 时 53 次）。

把可选的分隔符改成必需的。 「用空格分开的单词」写成「一个单词，后面跟若干个（空格加单词）」，每个单词的边界就唯一了：

^(\w+\s?)+$          改成   ^\w+(\s\w+)*$
^(\d+,?)+$           改成   ^\d+(,\d+)*,?$
(["'])(\w+\s?)+\1    改成   (["'])\w+(\s\w+)*\s?\1

改写后三个表达式在 n=26 的失败输入上分别是 55、81、132 次。改写可能改变接受的字符串集合（例如是否允许结尾的分隔符、连续的分隔符），要用原有的测试用例确认语义没变。

占有量词与原子组。 a++（占有量词）和 (?>a+)（原子组）的含义是：这一段匹配完之后不再退回来重新切分。(a++)+b 和 (?>a+)+b 在失败输入上只需要 n+3 次。它们会改变匹配语义：a++a 永远匹配不上，因为前面把 a 全吃掉且不肯让出来。只在「这一段不需要回退」确实成立的地方用。

占有量词和原子组的支持并不统一：Java 很早就支持；Python 的 re 模块从 3.11 起支持；JavaScript 的正则至今不支持这两种写法，只能靠改写表达式或在匹配前限制输入长度。同一个表达式在几种语言之间移植时，要先确认目标语言是否支持。

改写时还要注意分组编号：把 (\w+) 改成 (?:\w+)、或者在前面新增一个分组，都会改变后面所有分组的编号，替换模板里的 $2、代码里的 group(2) 会悄悄指向另一段内容，而且不会报错。分组较多的表达式改用命名分组（(?<year>\d{4})），引用时用名字，改写就不会影响引用。

不用正则。 按固定分隔符切分、判断前后缀、提取定长字段，用 indexOf、split 的简单分隔符或手写循环更清楚，也没有回溯。

五、不是指数的也可能很慢

清理结尾空白的 \s+$ 没有嵌套量词，但用 find 去找时，输入是一长串空格后面跟一个非空白字符：

空格数	1000	2000	4000	8000
空格在前，结尾是 x	503500	2007000	8014000	32028000
x 在前，空格在结尾	1001	2001	4001	8001

长度翻倍，工作量变成 4 倍。find 从每一个起始位置都尝试一次：从第 1 个空格开始吃到最后发现后面不是结尾，失败；再从第 2 个空格开始……这是平方增长，不会让服务卡死几十秒，但在几万字符的输入上已经是可观的 CPU 时间。带 .* 的查找类表达式有同样的问题。

六、给匹配加上界限

改写之后仍然应该假设某个表达式有问题，尤其是输入来自外部的地方。

限制输入长度。 这是最便宜也最有效的一条。指数增长在长度很小时无害：((a+)+)+b 匹配 12 个 a 加 !，JDK 25 上是 24547 次。用户名、邮箱、订单号都有合理的长度上限，在进入正则之前检查。

给匹配设预算。 java.util.regex 没有超时参数，匹配过程也不响应线程中断。可以利用它通过 CharSequence 读取输入这一点，在 charAt 里计数或检查截止时间，超出时抛异常：

public char charAt(int i) {
    if (++calls > budget) throw new IllegalStateException("regex budget exceeded");
    return s.charAt(i);
}

实验里预算设为 100 万次，((a+)+)+b 匹配 40 个 a 加 ! 时在第 100 万次调用后抛出了异常，匹配就此中止。检查中断标志（Thread.currentThread().isInterrupted()）也可以放在这里，让外层的超时取消真正生效。

表达式不要来自用户。 允许用户提交正则（搜索、过滤规则、路由配置）等于允许用户提交任意耗时的计算。必须支持时，用保证线性时间的引擎（例如 RE2/J，代价是不支持反向引用和环视），并限制表达式长度。

把失败输入放进测试。 对每个校验用的正则，除了合法和明显非法的输入，再加一类：很长、而且只在最后一个字符上不合法的输入。用上面的计数包装断言工作量不超过输入长度的某个倍数，比断言耗时稳定。

---

配套实验

• codesphere-labs/java/regex-backtracking：同一份代码在 JDK 25.0.4.1 与 JDK 8u504 上的 charAt 调用次数：嵌套量词、反向引用、懒惰量词、三层嵌套、有界重复、改写后的表达式、结尾空白的查找，以及预算与长度上限（验证记录）

参考资料

• JDK 25 API：java.util.regex.Pattern（贪婪、懒惰、占有量词与原子组的定义）
• OWASP：Regular expression Denial of Service
• JDK 25 源码：java/util/regex/Pattern.java（循环节点对已失败位置的记忆属于实现，未写入规范）
• RE2/J（线性时间的正则引擎及其不支持的语法）
• Russ Cox：Regular Expression Matching Can Be Simple And Fast