正则表达式测试器

2019年7月2日 13:42 UTC,Cloudflare 全球边缘节点的每台服务器 CPU 都达到了 100%。HTTP 流量停止流动。根据其公开的事故复盘报告,原因是几分钟前部署的一条新 WAF 规则: (?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*))) 末尾带有无界 + 的那个字符类,在应用于某些精心构造的字符串时,触发了 PCRE 的指数时间回溯。正则引擎进入失控状态,尝试数十亿种排列组合来"完成"匹配。Cloudflare 每台服务器上的每个 CPU 同时被这项工作占满,持续了 27 分钟。复盘报告为这种故障模式命名:catastrophic backtracking(灾难性回溯),也称 ReDoS(Regex Denial of Service,正则拒绝服务)。 其机制是结构性的。大多数生产环境的正则引擎(PCRE、Java 的 java.util.regex、Python 的 re、Ruby 的 Onigmo、JavaScript 的 V8 Irregexp)都用回溯实现匹配。当匹配尝试在模式后段失败时,引擎会回退并尝试另一条路径。对于嵌套量词 — 如 (a+)+、(.*)*、(\w*)*$ 这样的模式 — 每个字符划分到内层分组和外层分组的方式呈指数级增长。一个 30 个字符的输入,在引擎放弃之前可能产生 2^30 ≈ 10 亿次划分尝试。CPU 会在单次正则匹配上耗费数秒、数分钟,某些情况下甚至数年。 需要警惕的模式:(1) 任何把量词套在量词外面的形式 — (a+)+ 是教科书案例。(2) 含有相同前缀的分支 — (a|aa)+。(3) 贪婪量词作用于以可能不匹配的字面量结尾的无界片段 — 用 ^(a+)+\$ 去测试 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab" 会让大多数引擎慢如蜗牛。 存在三种防御手段。(1) 使用结构上免疫的引擎。RE2(Google)、Hyperscan、Rust 的 regex crate、Go 的 regexp 以及 Lua patterns 都使用线性时间的 NFA 模拟,它们不回溯。代价是不支持某些形式的反向引用和后顾(lookbehind),但对 95% 的真实模式来说没有问题。RE2 正是因为 Google 曾发生 ReDoS 事故才被设计出来的。(2) 为每次正则求值设置真实时钟超时。Java 的 Pattern.matcher 没有内置超时(必须借助线程中断);.NET 正是为此明确添加了 Regex(pattern, options, timeout)。(3) 对模式做静态检查。vuln-regex-detector、safe-regex 和 ESLint 的 no-unsafe-regex 之类的工具能在上线前标记出最危险的结构形态。 一条务实的规则:如果你接受最终用户提供的正则,绝不要在没有超时的情况下使用语言的默认引擎。如果模式是你自己写的,请先用上述某个检查工具跑一遍,尤其是在部署到请求路径上的 WAF 或输入校验器之前。2019 年的 Cloudflare 这两条都没有做。

// Catastrophic patterns
/^(a+)+$/.test('a'.repeat(30) + 'b');
// V8: ~30 seconds. Engine in tight backtracking loop.

/(.*)*=/.test('=' + 'a'.repeat(50));
// Even worse with inner unbounded greedy.

// Production safety in Node
const RE2 = require('re2');         // linear time
const safe = new RE2('(a+)+');
safe.test('a'.repeat(30) + 'b');    // returns instantly, false

// Native regex with watchdog (workers)
function timedRegex(pattern, input, ms = 50) {
  return new Promise((resolve, reject) => {
    const w = new Worker(`onmessage = e => {
      const re = new RegExp(e.data.p);
      postMessage(re.test(e.data.s));
    }`, { eval: true });
    const timer = setTimeout(() => { w.terminate(); reject(new Error('regex timeout')); }, ms);
    w.onmessage = e => { clearTimeout(timer); resolve(e.data); w.terminate(); };
    w.postMessage({ p: pattern, s: input });
  });
}

// .NET — built-in timeout
var re = new Regex(pattern, RegexOptions.None, TimeSpan.FromMilliseconds(50));

现代正则实现由三个引擎主导,它们之间的差异很重要。 PCRE(Perl Compatible Regular Expressions)。驱动 PHP、nginx、Apache、以及历史上 Cloudflare 的 WAF 等众多软件的 C 库。基于回溯,支持最完整的功能集:反向引用、后顾(PCRE2 支持变长)、递归、原子分组、占有型量词、条件模式、支持所有语法形式的命名捕获、callout。代价是最坏情况的行为 — 面对对抗性输入时的指数时间。PCRE2(现代分支)加入了 JIT 编译器,使平均情况的原始匹配速度可与 RE2 竞争,但没有改变最坏情况。 RE2(Google)。由 Russ Cox 编写的 C++ 实现,也绑定到 Go 的标准库。基于 Thompson 的 NFA 模拟算法构建:引擎维护一组可能的解析器状态,并让它们随输入同步前进。无论模式多复杂,时间都与输入长度成线性关系。代价是有些功能无法支持:任意反向引用(正则不能要求记住任意先前匹配过的文本),某些绑定中后顾被限制为有界长度。对真实代码库中 95% 的正则模式而言,RE2 是可以直接替换的方案,以放弃少数冷门特性为代价消除了 ReDoS。Google 在一系列正则故障之后把所有内部服务迁移到了 RE2。 JavaScript V8(Irregexp)。浏览器的正则引擎。基于回溯,但经过深度优化:它在 JIT 层面把正则模式编译成本地代码。支持后顾(自 2018 年,ES2018)、命名捕获 (\(?<name>...\))、Unicode 属性转义 (\p{Letter})、s 标志(dotAll)和 d 标志(匹配索引)。它没有超时原语 — 失控的模式会让标签页崩溃。较新的 V8 版本(2022 年起)有一个实验性的线性时间模式,可以通过 v8 引擎标志中的 /l 标志启用,但默认关闭,也没有暴露给标准 JS。 实用指南:服务端,凡是接触用户输入的模式都优先使用 RE2(Go 原生、Node 用 re2 npm、Rust 用 regex-rs、Python 用 google-re2)。如果需要更丰富的功能集且信任这些模式,就用 PCRE。浏览器端,接受 V8 没有内置保护这一事实 — 保持模式简单,避免嵌套量词,优先使用不回溯的结构(JS 没有原子分组 /(?>x)/,但可以用 /(?=(x))\1/ 这个前瞻技巧模拟)。只要有可能,就用显式字符串操作替换复杂正则 — string.includes、string.split、indexOf 都是线性时间,而且快得没有上限。 功能不匹配也很要紧。从 Stack Overflow 的 PCRE 答案复制的代码经常在 JavaScript 中不工作:PCRE 的变宽后顾、占有型量词 (a++)、递归子例程 ((?R)) 以及部分 Unicode 类都是 PCRE 独有。JavaScript 独有的功能包括 d(hasIndices)标志和 v(Unicode-Sets)标志(ES2024)。在引擎之间移植时,一定要用你的测试用例跑一遍模式 — 悄无声息的语义差异非常常见。

// PCRE-only that fails in JS:
preg_match('/^(?P>group)$(?<group>foo|bar)/', $s);  // recursion
preg_match('/(?<=\w+)b/', $s);                     // var-width lookbehind

// JavaScript-only:
'abcabc'.matchAll(/(?<x>\w)/dg);  // d flag → result[i].indices
[...'abc'.matchAll(/[\p{Letter}--[a]]/v)]; // v flag set difference

// Cross-engine safe baseline (works everywhere):
const safePattern = /^[a-zA-Z][a-zA-Z0-9_]{0,31}$/;

// Server: use RE2 in Node
const RE2 = require('re2');
const safe = new RE2('^([a-z]+)\\s+(\d+)$');
const m = safe.match('alice 42');
m;  // ['alice 42', 'alice', '42']

// Replace regex with string ops when you can — guaranteed O(n)
const isEmail = (s) => s.includes('@') && s.indexOf('@') === s.lastIndexOf('@');

环视(lookaround)是零宽断言:它检查当前位置之前或之后的内容,而不消费任何字符。共有四种:肯定前瞻 (?=...)、否定前瞻 (?!...)、肯定后顾 (?<=...)、否定后顾 (?<!...)。它们功能强大,却经常被滥用。正则教程里看到的环视,大约 80% 都可以改写成使用捕获组的普通正则,而且会更快、更易读。 正当的用途可以归为几类。 (1) 在不消费分隔符的情况下做分词。用 /(?<=\D)(?=\d)|(?<=\d)(?=\D)/ 这样的正则把 "abc123def" 拆成字母和数字,会在字母与数字的边界处插入切分点而不消费任何字符,因此 .split 返回 ["abc","123","def"]。用非零宽的正则实现同样的效果,需要显式地重新拼装。 (2) 断言匹配区域之外的约束。"找出后面跟着单位的数字,但我不想让单位出现在匹配结果里":/\d+(?=px|em|rem)/。没有前瞻的话,你要么把单位包含进匹配(再后处理去掉),要么用捕获组并引用第 1 组。前瞻更干净。 (3) 在一个模式里校验多个相互独立的约束。经典的"密码必须包含数字、字母、特殊字符,且不少于 12 个字符"模式:/^(?=.*\d)(?=.*[a-zA-Z])(?=.*[!@#$%])\S{12,}$/。每个 (?=...) 都在不前进位置的情况下针对整个字符串检查一条规则。这可行且简洁,但它同时也是"在应用代码里做多个独立校验会更清晰"的典型例子。 (4) Unicode 中的单词边界。JavaScript 的 \b 默认只针对 ASCII。要在 Unicode 文本上断言"字母边界",需要带 Unicode 标志的 /(?<![\p{Letter}\p{Mark}])foo(?![\p{Letter}\p{Mark}])/u。 什么时候不该用环视:凡是捕获组就能解决的场合。用 /(\d+)px/ 匹配 "12px",不用后顾就能得到 match[1] = "12"。把 /(?<=\$)\d+/.exec("$42")[0] 换成 /\$(\d+)/.exec("$42")[1] — 数据相同,正则更简单,而且在包括后顾受限引擎在内的所有引擎中都能运行。 一个隐蔽的性能陷阱:在回溯引擎中,位于量词分组内部的环视可能成倍放大最坏情况的工作量,因为每一步回溯都会重新求值断言。RE2 能处理前瞻,但不支持任意后顾。Java 在 9 中加入了有界后顾。Python 只支持定长后顾。ECMAScript 自 2018 年起同时支持前瞻和无界后顾,但 Safari 直到 2023 年才提供后顾支持,所以如果需要兼容旧版 Safari,后顾就不能用。

// Tokenize on letter/digit boundary (zero-width split)
'abc123def'.split(/(?<=\D)(?=\d)|(?<=\d)(?=\D)/);
// → ['abc', '123', 'def']

// Match number followed by CSS unit, exclude the unit
const px = '20px 1rem 3em'.match(/\d+(?=px|em|rem)/g);
// → ['20', '1', '3']

// Password rule with lookaheads
/^(?=.*\d)(?=.*[a-z])(?=.*[A-Z])(?=.*[!@#$%^&*])\S{12,}$/.test(pw);

// Lookbehind for dollar amount
'price $42 and €50'.match(/(?<=\$)\d+/);  // ['42']

// SAME RESULT without lookbehind (more portable)
'price $42 and €50'.match(/\$(\d+)/)[1];   // '42'

// AVOID: nested-quantifier-with-lookahead — slow on adversarial input
/^(.+(?=.+))+$/.test('a'.repeat(20) + 'X');  // backtracks badly