ReDoS 原理

概述

DFA对于文本串里的每一个字符只需扫描一次，比较快，但特性较少；NFA要翻来覆去吃字符、吐字符，速度慢，但是特性(如:分组、替换、分割)丰富。NFA支持  惰性(lazy)、回溯(backtracking)、反向引用(backreference)，NFA缺省应用greedy模式，NFA可能会陷入递归险境导致性能极差。

说明

我们定义一个正则表达式^(a+)+$来对字符串aaaaX匹配。使用NFA的正则引擎，必须经历2^4=16次尝试失败后才能否定这个匹配。同理字符串为aaaaaaaaaaX就要经历2^10=1024次尝试。如果我们继续增加a的个数为 20 个、30 个或者更多，那么这里的匹配会变成指数增长。

下面我们以python语言为例子来进行代码的演示:

#!/usr/bin/env python# coding: utf-8import reimport timedef exp(target_str): """ """ s1 = time.time() flaw_regex = re.compile('^(a+)+$') flaw_regex.match(target_str) s2 = time.time() print("Consuming time: %.4f" % (s2-s1))if __name__ == '__main__': str_list = ( 'aaaaaaaaaaaaaaaaX', # 2^16 'aaaaaaaaaaaaaaaaaaX', # 2^18 'aaaaaaaaaaaaaaaaaaaaX', # 2^20 'aaaaaaaaaaaaaaaaaaaaaaX', # 2^22 'aaaaaaaaaaaaaaaaaaaaaaaaX', # 2^24 'aaaaaaaaaaaaaaaaaaaaaaaaaaX', # 2^26 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaX', # 2^36 ) for evil_str in str_list: print('Current: %s' % evil_str) exp(evil_str) print('--'*40)

把上面的代码保存成redos.py文件并执行这个 py 脚本文件:

$ python redos.pyCurrent: aaaaaaaaaaaaaaaaXConsuming time: 0.0043--------------------------------------------------------------------------------Current: aaaaaaaaaaaaaaaaaaXConsuming time: 0.0175--------------------------------------------------------------------------------Current: aaaaaaaaaaaaaaaaaaaaXConsuming time: 0.0678--------------------------------------------------------------------------------Current: aaaaaaaaaaaaaaaaaaaaaaXConsuming time: 0.2370--------------------------------------------------------------------------------Current: aaaaaaaaaaaaaaaaaaaaaaaaXConsuming time: 0.9842--------------------------------------------------------------------------------Current: aaaaaaaaaaaaaaaaaaaaaaaaaaXConsuming time: 4.1069--------------------------------------------------------------------------------Current: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaX

输出到最后一行貌似程序卡住了

总结

每个恶意的正则表达式模式应该包含：

• 使用重复分组构造
• 在重复组内会出现
  • 重复
  • 交替重叠

有缺陷的正则表达式会包含如下部分：

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

注意: 这里的a是个泛指

实例

下面我们来展示一些实际业务场景中会用到的缺陷正则。

• 英文的个人名字:

  • Regex: ^[a-zA-Z]+(([\'\,\.\-][a-zA-Z ])?[a-zA-Z]*)*$
  • Payload: aaaaaaaaaaaaaaaaaaaaaaaaaaaa!

• Java Classname

  • Regex: ^(([a-z])+.)+[A-Z]([a-z])+$
  • Payload: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!

• Email 格式验证

  • Regex: ^([0-9a-zA-Z]([-.\w]*[0-9a-zA-Z])*@(([0-9a-zA-Z])+([-\w]*[0-9a-zA-Z])*\.)+[a-zA-Z]{2,9})$
  • Payload: a@aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!

• 多个邮箱地址验证

  • Regex: ^[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})$
  • Payload: aaaaaaaaaaaaaaaaaaaaaaaa!

• 复数验证

  • Regex: ^\d*[0-9](|.\d*[0-9]|)*$
  • Payload: 1111111111111111111111111!

• 模式匹配

  • Regex: ^([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})+$
  • Payload: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!

使用python来进行测试有缺陷的正则示例:

$ python -c "import re;re.match('^[a-zA-Z]+(([\'\,\.\-][a-zA-Z ])?[a-zA-Z]*)*$', 'aaaaaaaaaaaaaaaaaaaaaaaaaaaa!')"

ReDoS 防范

哪里会用到Regex, 几乎在我们的网络程序与设备资源的任何位置都会用到。如: WAF、Web前端、Web后端、DB数据库等。

常见位置

客户端

• 浏览器
• 移动设备

服务器端

防范手段

防范手段只是为了降低风险而不能百分百消除  ReDoS  这种威胁。当然为了避免这种威胁的最好手段是尽量减少正则在业务中的使用场景或者多做测试, 增加服务器的性能监控等。

• 降低正则表达式的复杂度, 尽量少用分组
• 严格限制用户输入的字符串长度(特定情况下)
• 使用单元测试、fuzzing 测试保证安全
• 使用静态代码分析工具, 如: sonar
• 添加服务器性能监控系统, 如: zabbix

参考

浅析 ReDoS
前端 ReDOS 攻击