什么是 ReDoS（灾难性回溯）？

CWE-1333: Inefficient Regular Expression Complexity参考页面

简要说明

支持回溯的正则引擎在匹配失败后，可能会尝试以不同方式拆分同一输入。某些含糊模式的尝试次数会随输入长度呈指数增长。实际延迟取决于正则、引擎、输入长度、并发量和资源限制；重复的高开销请求可能耗尽服务容量。

易受攻击的模式

# Nested quantifier
^(a+)+$

# Overlapping alternatives, quantified
^(a|aa)+$

# A long matching prefix plus a final mismatch can
# force extensive retries in vulnerable engines.
# Do not benchmark this with attacker-sized input.

更安全的写法

# Bound input before matching, then use a simple
# full-string identifier rule with no nested ambiguity.
import re

IDENTIFIER = re.compile(r"[a-z0-9]{1,64}\Z")

def valid_identifier(value: str) -> bool:
    if not isinstance(value, str) or len(value) > 64:
        return False
    return IDENTIFIER.fullmatch(value) is not None

# A bound reduces worst-case work; still set request
# size, concurrency, and execution-time limits.

回溯为何会激增

在回溯引擎中，像 ^(a+)+$ 这样的模式存在歧义：序列 aaaa 可以用多种方式分配给嵌套量词。若末尾字符不匹配，引擎可能需要尝试多个分支，才能判定整个字符串失败。

对于存在这种歧义的模式，匹配前缀后跟不匹配字符时，探索路径数可能随前缀长度呈指数增长。这取决于具体的模式与引擎组合，并非所有正则或失败匹配都会如此。并发请求下，较短输入也可能产生影响；应限制输入长度、并发量和执行时间。

不可信输入会从哪里进入正则

输入校验是显而易见的入口，但风险也可能藏在其他地方：解析 User-Agent 等请求头、日志处理、Markdown 与语法高亮、URL 路由、内容过滤器和 WAF 规则，以及对传入字段执行正则的库。许多常用软件包曾发布 ReDoS 公告，因此依赖树和自有模式同样需要审查。

常见问题

Which languages are affected?

风险取决于引擎和模式，而不只是编程语言。某些回溯引擎会在特定模式上进行过多尝试。Go 的 regexp 文档保证运行时间与输入长度呈线性关系。Rust 的 regex crate 对单次搜索给出 O(m·n)（m 为模式长度，n 为输入长度）；模式固定时，对输入长度为线性。重复搜索迭代器的最坏复杂度不同。这些引擎不支持反向引用等会妨碍此类保证的功能。

Is a length limit enough on its own?

长度限制可以限制匹配的工作量，但安全上限取决于模式、引擎、请求速率和服务预算。还应修复含糊模式，并在解析或匹配前应用限制。

How do I find vulnerable patterns?

使用支持 ReDoS 检查的静态分析器，并结合实际使用的引擎审查结果。检查包含重复量词的重复组，或前缀重叠的分支；随后在隔离环境中用有界输入和严格超时进行测试。

Can I add a timeout instead?

超时支持取决于运行时和 API。在 .NET 中，对不可信输入的匹配应明确设置超时。其他环境要查阅具体引擎文档；若没有可用超时，应采用更安全的引擎或重写模式。超时应与输入和并发限制配合使用，不能让含糊模式本身变高效。

参考资料

另请参阅 Node.js ReDoS：正则表达式与 CVE-2026-83606