ReDOS（正则表达式拒绝服务攻击）深入解析与防御

1. ReDOS概述

ReDOS（Regular expression Denial of Service）即正则表达式拒绝服务攻击，是指当开发人员使用存在缺陷或不严谨的正则表达式对用户输入进行校验时，攻击者可以构造特殊字符串使服务器陷入大量计算，消耗系统资源，最终导致服务中断。

2. 正则表达式引擎基础

2.1 有限状态自动机（FSM/FSA）

• 为研究有限内存计算过程和语言类而抽象的计算模型
• 拥有有限数量的状态，输入字符串决定状态迁移
• 分为确定性（DFA）和非确定性（NFA）两类

2.2 正则表达式引擎类型

DFA（确定性有限状态自动机）

• 以文本为导向，捏着文本串比较正则式
• 每个字符只需扫描一次，速度快但特性少
• 匹配原则："最长的左子正则式优先匹配成功"

NFA（非确定性有限状态自动机）

• 以正则为导向，捏着正则式比较文本串
• 需要"吃字符、吐字符"的回溯操作，速度慢但特性丰富
• 匹配原则："最左子正则式优先匹配成功"
• 支持lazy和backreference等高级特性
• 主流实现：Perl、Ruby、Python re、Java、.NET等

3. ReDOS产生原理

3.1 关键因素

• 使用NFA引擎的正则表达式
• 存在"重复分组构造"的正则模式
• 组内同时出现：1)重复 2)交替重叠

3.2 典型漏洞模式

^(a+)+$
([a-zA-Z]+)*
(a|aa)+
(a|a?)+
(.*a){x} (x > 10)

3.3 攻击原理

当恶意输入（如"aaaaaaaaaaaaaaaaaaX"）匹配这些正则时：

1. NFA引擎会尝试所有可能的匹配路径
2. 由于重复和交替重叠的组合，导致指数级回溯
3. 消耗大量CPU资源和时间

4. 实际业务场景中的危险正则

4.1 常见漏洞模式示例

1. 姓名验证：

   ^[a-zA-Z]a-zA-Z ])?[a-zA-Z]*)*$
   

   攻击载荷：aaaaaaaaaaaaaaaaaaaaaaaaaaaa!

2. Java类名验证：

   ^(([a-z])+.)+[A-Z]([a-z])+$
   

   攻击载荷：aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!

3. 邮箱验证：

   ^([0-9a-zA-Z]([-.\w]*[0-9a-zA-Z])*@(([0-9a-zA-Z])+([-\w]*[0-9a-zA-Z])*\.)+[a-zA-Z]{2,9})$
   

   攻击载荷：a@aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!

4. 多邮箱验证：

   ^[a-zA-Z]a-zA-Z ])?[a-zA-Z]*)*\s+<(\w[-._\w]*\w@\w[-._\w]*\w\.\w{2,3})>$|^(\w[-._\w]*\w@\w[-._\w]*\w\.\w{2,3})$
   

   攻击载荷：aaaaaaaaaaaaaaaaaaaaaaaa!

5. 十进制验证：

   ^\d*[0-9](|.\d*[0-9]|)*$
   

   攻击载荷：1111111111111111111111111!

6. 模式匹配：

   ^([a-z0-9]+([\-a-z0-9]*[a-z0-9]+)?\.){0,}([a-z0-9]+([\-a-z0-9]*[a-z0-9]+)?){1,63}(\.[a-z0-9]{2,7})+$
   

   攻击载荷：aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!

4.2 PHP中的ReDOS案例

function is_php($data){
    return preg_match('/<\?.*[(`;?>].*/is', $data);
}

攻击原理：

1. 输入<?php phpinfo();//aaaaa...（大量a字符）
2. .*贪婪匹配到字符串末尾
3. 回溯尝试匹配[(;?>]`，逐个回退字符
4. 当a字符足够多时，超过PHP的pcre.backtrack_limit（默认1000000）
5. preg_match()返回false而非0或1

安全修复：

if(is_php($input) === 0) {  // 使用全等比较
    // 安全处理
}

5. 防御措施

5.1 编码实践

1. 避免嵌套量词（如(a+)+）
2. 避免重叠交替（如(a|aa)+）
3. 使用原子组（Atomic Grouping）减少回溯
4. 设置合理的匹配超时和回溯限制

5.2 语言特定防护

• PHP：检查preg_match()返回值使用===，设置pcre.backtrack_limit
• Python：使用re.match()时考虑设置超时（Python 3.11+支持）
• Java：配置合理的超时参数

5.3 测试验证

1. 使用模糊测试工具检测正则表达式
2. 对用户输入设置长度限制
3. 性能测试：输入逐渐增长的字符串观察响应时间

6. 总结

ReDOS是Web应用中容易被忽视的安全威胁，源于NFA引擎的正则表达式实现机制。开发人员应：

1. 理解不同正则引擎的特性差异
2. 避免编写存在"重复分组+交替重叠"模式的正则
3. 实施严格的输入验证和长度限制
4. 正确处理正则匹配函数的返回值
5. 对关键正则表达式进行安全测试

通过以上措施，可以有效防范ReDOS攻击，保障系统服务的可用性和稳定性。