正则表达式引发线上 CPU 飙升案例¶

一、现象¶

线上 CPU 突然飙到 100%，应用响应慢。用 top -Hp 发现几个线程一直在跑。

二、根因：灾难性回溯（Catastrophic Backtracking）¶

正则引擎（Java 的 Pattern）是 NFA 自动机，会回溯。当模式有嵌套量词如 (a+)+b，遇到不匹配的字符串时，会尝试所有可能的拆分方式，时间复杂度指数级。

// 反例
Pattern p = Pattern.compile("(\\w+)*@");
// 输入 "aaaaaaaaaaaaaaaaaaaaaa!"
// 回溯次数爆炸

三、案例：用户输入校验¶

// 校验邮箱 / 手机号
Pattern p = Pattern.compile("^([0-9a-zA-Z]+)*@[0-9a-zA-Z]+$");
String input = request.getParameter("email");
Matcher m = p.matcher(input);
boolean valid = m.matches();

攻击者输入一串无意义字符，正则引擎疯狂回溯，CPU 打满。

四、排查步骤¶

top -Hp <pid> 找高 CPU 线程。
printf "%x\n" <tid> 转十六进制。
jstack <pid> | grep <hex> 看线程栈。
发现栈停在 Pattern$BnM.match / Pattern$Curly.match0。

五、解决¶

1. 写正则时避免嵌套量词¶

(\\w+)*    ❌
(\\w*)     ✅ 直接用 *

2. 限制输入长度¶

if (input.length() > 100) {
    return false;
}

从入口限制，避免长字符串进入正则。

3. 用更简单的校验¶

邮箱校验不要靠复杂正则，用 commons-validator 或简单规则。

4. 超时保护¶

Java 9+ 支持正则超时：

Pattern p = Pattern.compile("...");
p.matcher(input).matches(1, TimeUnit.SECONDS);

六、预防¶

代码评审检查正则。
对用户输入的正则（模板系统）要沙箱。
线上压测包含恶意长输入。

高频追问

NFA vs DFA：Java 用 NFA，支持回溯但可能指数级慢；部分语言用 DFA，快但功能少。
怎么写安全正则：避免 (a+)+、(a*)*、(a|a)* 这类嵌套。