名称

regex-redos-review

描述

当需要评审正则表达式是否存在灾难性回溯风险、或要为不可信输入设计安全匹配规则时使用。该技能识别嵌套量词、重叠分支、重复分组等 ReDoS 诱因，给出线性时间改写方案与输入长度上限，并附带可运行的耗时增长探测脚本。适用于表单校验、日志解析、路由匹配、WAF 规则与文本抽取。关键词：正则表达式、ReDoS、灾难性回溯、回溯爆炸、正则安全、性能、嵌套量词、重叠分支、输入校验、线性时间、正则改写、WAF、日志解析。

正则表达式回溯风险评审

判断一条正则在最坏输入下是线性还是指数级，并把它改写到可控。

何时使用

正则作用于用户输入、日志、抓取内容等不可信文本。
线上出现 CPU 飙高、请求超时，怀疑与匹配有关。
需要为校验规则设定输入长度上限。
评审 WAF、网关、日志采集规则。

不适用：编译期常量且输入可控的内部匹配；简单的 substring 判断。

输入

正则原文与使用语言/引擎（PCRE、Java、Python、JavaScript、Go RE2）。
输入来源与最大长度。
是否可接受改写后语义变化。

优先确认引擎：Go 的 RE2 与 Rust regex 不支持回溯，天然免疫；JavaScript、Java、Python re、PCRE 需要重点检查。

工作流

第 1 步：结构扫描

逐段标记高风险结构：

结构	示例	风险
嵌套量词	`(a+)+`	指数级回溯
相邻可重叠量词	`aa`	组合爆炸
重叠分支	`(a	ab)+`
量词作用于含量词分组	`(\w+\s?)*`	空格组合爆炸
无锚点的全局匹配	`.*x`	线性扫描放大
回溯引用	`(a+)\1`	难以优化

第 2 步：构造最坏输入

按结构生成能触发最大回溯的输入，例如：

(a+)+$ 对应 aaaa...a!
(\w+\s?)*$ 对应 aaaa aaaa aaaa!
(a|aa)+$ 对应 aaaa...a!

用 scripts/redos_probe.py 对长度 10、15、20、25 的输入计时，观察耗时增长曲线。

第 3 步：判定

输入长度每加 5，耗时约翻倍以上：疑似指数级，必须改写。
耗时为线性或接近线性：可接受，但仍需设置长度上限。
短输入就超时：立即下线该规则。

判定时给足预热，避免把首次编译计入。

第 4 步：改写

按 references/safe-rewrites.md 选择：

用占有量词或原子组消除回溯（引擎支持时）。
把 (a+)+ 改为 a+。
把 (a|ab)+ 改为 (ab|a)+ 或拆成两个判断。
用字符类替代分支：(cat|car) → ca[tr]。
用"先切分再匹配"替代跨段贪婪匹配。
无法安全改写时，换用 RE2 类线性引擎。

第 5 步：设限与监控

输入长度硬上限：校验类 256、日志字段 4 KB、正文 64 KB。
匹配超时：Java 用 Matcher 配合超时线程，Python 用信号或第三方超时库。
统计慢匹配：记录耗时超过阈值的规则与输入长度。

检查清单

[ ] 已确认正则引擎是否支持回溯。
[ ] 已扫描嵌套量词与重叠分支。
[ ] 已用递增长度输入验证增长曲线。
[ ] 高风险规则已改写或替换引擎。
[ ] 输入长度上限已设置在调用方。
[ ] 匹配超时与慢日志已配置。
[ ] 改写后有等价性测试覆盖原有用例。
[ ] 规则上线前在预发压测过最坏输入。

输出模板

## 结论
安全 / 需改写 / 立即下线

## 风险点
| 正则 | 结构 | 最坏输入 | 增长 | 结论 |
| --- | --- | --- | --- | --- |

## 改写建议
原式 → 新式（附等价性说明）

## 防护
- 长度上限：
- 超时：
- 监控：

## 验证
- 探测数据：
- 回归用例：

反模式

用 .* 跨行贪婪匹配整段文本。
认为"加个 ^ 和 $ 就安全"——锚点不消除回溯。
只在正常输入上测试。
把复杂校验全塞进一条正则。
依赖前端校验，服务端不做限制。

参考文件

references/safe-rewrites.md：常见危险结构的等价改写。
scripts/redos_probe.py：耗时增长探测脚本。