编写 ReDoS 安全模式

ReDoS（正则表达式拒绝服务）是一类攻击，其中 精心设计的输入会使正则表达式的匹配时间爆炸。 JS 引擎使用回溯：如果模式“不明确”，则在 不幸的是，它可以执行指数级的尝试。

经典的灾难模式

Pattern: ^(a+)+$
Input:   "aaaaaaaaaaaaaaaaaaaaab"

为了匹配，引擎会尝试每个可能的“a”分区 两个 + 量词。对于 20 个“a”，即 2^20 = ~100 万次尝试。 30 个“a”，就是十亿。

其他危险的例子：

• (a*)*b --“嵌套星”。
• (a|a)* -- 重叠的替代方案。
• (\w+)+@ -- 带有外部量词的贪婪组。

如何发现危险

寻找这些结构：

1. 量词中的量词：(...+)+、(...*)*、(...{n,})+。
2. 量词下的重叠替代项：(a|ab)*、(\w|\d)+。
3. 具有复杂替代方案的前瞻/后瞻重复。

防御性重写

Dangerous:  ^(\w+\s+)+$
Safe:       ^(?:\w+\s+)*\w+$

安全版本将基本情况与重复情况分开，删除 歧义。其他技术：

• 所有格量词 (a++) -- JS 不支持，但在其他引擎中可用。
• 原子模式 ((?>...)) -- 不在 JS 中。
• 在匹配之前限制输入的长度。
• 匹配超时（本课程的编辑器使用超时时间为 500 毫秒的工作人员）。

ReDoS 安全模式的建议

1. 确保交替中的选项是互斥的（例如，不要使用 (a|a+)）。
2. 避免将嵌套量词应用于重叠表达式（例如 (\\s*)*）。
3. 始终优先选择特定的否定字符类 ([^\\n]*) 而不是通用通配符点 (.*)。

尝试一下

复习练习

额外的挑战