正则表达式拒绝服务（ReDoS）攻击详解

正则表达式拒绝服务（ReDoS）是一种针对应用层服务的拒绝服务攻击，攻击者通过构造特定的输入字符串，使正则表达式引擎进入极端低效的匹配路径，导致服务器资源（CPU、内存）被大量占用，从而拒绝正常服务。

1. ReDoS的原理

正则表达式引擎有两种主要匹配方式：

• 确定性有限自动机（DFA）：匹配时间与输入长度线性相关，抗ReDoS能力强，但功能受限（如不支持回溯）。
• 非确定性有限自动机（NFA）：支持复杂功能（如回溯、捕获组），但可能因回溯机制导致匹配时间指数级增长。

关键问题：回溯（Backtracking）
当正则表达式包含模糊匹配（如.*、a+）或分支选择（如(a|aa)*）时，引擎会尝试所有可能的匹配路径。若输入字符串与模式部分匹配但最终不匹配，引擎会不断回溯尝试其他路径，消耗大量计算资源。

示例：危险的正则表达式

^(a+)+$  

该模式试图匹配由字符a组成的字符串，但嵌套的(a+)和+会导致多重回溯。输入字符串"aaaaaaaaX"（末尾有一个无效字符）时，引擎会尝试所有可能的a的分割方式，导致匹配步骤数随a的数量指数级增长。

2. 攻击场景与影响

• Web应用：用户输入校验（如邮箱、URL格式检查）、路由解析、日志分析等场景使用正则表达式时，可能被恶意输入触发ReDoS。
• 系统工具：如grep、sed处理特定文件时卡死。
• 影响：CPU占用率飙升至100%，服务响应缓慢或崩溃，可能连带影响同一服务器上的其他应用。

3. 复现ReDoS攻击（以Node.js为例）

漏洞代码示例：

const regex = /^(a+)+$/; // 危险模式
const maliciousInput = "a".repeat(100) + "X"; // 100个a后加无效字符

// 触发ReDoS（执行时间极长）
console.time("ReDoS");
regex.test(maliciousInput);
console.timeEnd("ReDoS");

结果：当输入字符串中a的数量增加时，匹配时间呈指数增长（如20个a需几毫秒，30个a需数秒）。

4. 识别危险正则表达式

以下模式可能引发ReDoS：

• 嵌套量词：如(a+)+、(a*)*
• 重叠分支：如(a|aa)*
• 模糊匹配与严格后缀：如.*a匹配字符串"aaa...b"

工具检测：

• regex-static-analysis：静态分析工具，标记潜在危险模式。
• rxxr2：在线检测工具（如输入^(a+)+$会提示“有漏洞”）。

5. 防御措施

（1）优化正则表达式

• 避免嵌套量词：将^(a+)+$改为^a+$。
• 使用非捕获组与占有量词：
  • 占有量词（如a++）禁止回溯，但需语言支持（PCRE、Java）。
  • 原子组（如(?>a+)）同样可减少回溯。
• 简化分支：将(a|aa)改为a{1,2}。

（2）限制输入长度

对用户输入设置长度阈值（如邮箱不超过254字符），避免长字符串触发回溯。

（3）超时机制

• 语言层面：如Python的regex库支持timeout参数：

  import regex
  regex.search(r"^(a+)+$", "aaaaaaaaX", timeout=1) # 1秒超时
  

• 异步处理：在Node.js中将正则匹配放入子进程，超时则终止。

（4）使用DFA引擎

如场景允许，换用RE2（基于DFA）等抗ReDoS的引擎。

（5）WAF防护

配置Web应用防火墙规则，拦截已知的ReDoS攻击模式。

6. 安全开发实践

• 代码审查：团队定期检查正则表达式，重点关注嵌套量词和分支。
• 测试：使用模糊测试工具（如regex-fuzzer）验证正则表达式的性能边界。
• 依赖库检查：确保第三方库使用的正则表达式无ReDoS风险。

通过理解回溯机制、识别危险模式并实施防护，可有效避免ReDoS对系统的威胁。