文章目录
前言
正则基础
1.1 基础语法
1.2 正则案例
1.3 贪婪匹配
1.4 正则引擎
ReDos攻击
2.1 缺陷实例
2.2 计算回溯
2.3 缺陷正则
2.4 检测工具
总结
前言
开发人员使用了正则表达式来对用户输入的数据进行有效性校验, 当编写校验的正则表达式存在缺陷或者不严谨时, 攻击者可以构造特殊的字符串来大量消耗服务器的系统资源，造成服务器的服务中断或停止。
正则基础
关于正则表达式的语法及其使用，可参见 Java-正则表达式 和 正则表达式 - 语法，本文不过多展开。
1.1 基础语法
正则表达式 (Regular Expression, Regex) 是由字符 (可为英文字母、数字、符号等) 与元字符(特殊符号)组成的一种有特定规则的特殊字符串。在模式匹配中，正则表达式通常被用于验证邮箱、URL、手机号码等。
常用元字符:
1.2 正则案例
正则表达式是一种用于匹配（编程语言中）字符串的模式。下面通过一个示例来理解它吧，该示例是“用正则表达式在服务器端验证电子邮件地址”。
上面是一段 JavaScript 代码（译者注：不会 JS 也无妨，对阅读本文的影响不大，请继续阅读）。我们在这里使用的正则表达式是 [a-z0–9]+@[a-z]+.[a-z]{2,3}。我们提供了几个电子邮件地址，然后我们需要检查它们是否遵循电子邮件地址的一般模式。让我们分解一下正则表达式。
[a-z0–9]+：表示此处的字符串可以是任何小写字母和数字。末尾的加号 (+) 表示必须至少有一个字符（无论是小写字母还是数字）。
@：表示此处应该有 AT（@）符。
[a-z]+：表示此处字符串应该包含（一个或多个）小写字母的字符
.：表示此处应该有一个点（.）
[a-z]{2,3}：表示此处字符串是由小写字母组成的，但其长度只能是 2 或 3。
让我们将其与我们选择的电子邮件 ID 进行比较。让电子邮件 ID 为 yourremail12@yahooemail.com。
youremail12@ 对应于 [a-z0-9]+@
yahooemail 对应于 [a-z]+
.com 对应于 .[a-z]{2,3}
这通常是正则表达式的工作方式。
1.3 贪婪匹配
如果我想匹配 x 和 y 之间所有的字符，我可以简单地用 x.*y 进行处理，注意，.代表任意字符。因此，该表达式将成功匹配 x)dw2rfy 字符串。
但是，默认情况下，重复运算符是很贪婪的。他们会尝试尽可能多的匹配。让我们再考虑上面的例子，x.y 表达式如果对字符串 axaayaaya 进行处理，就会返回 xaayaay。但是使用者可能并不期待这种结果，他们也许只想要字符串 xaay，这种 xy 的模式就是贪婪匹配和非贪婪匹配发挥作用的地方。默认情况下，表达式将返回尽可能长的结果，但我们可以通过使用运算符 ? 指定其进行非贪婪匹配，此时表达式为 x.?y。
1.4 正则引擎
正则表达式引擎分成两类：一类称为 DFA（确定性有限状态自动机），另一类称为 NFA（非确定性有限状态自动机）。两类引擎要顺利工作，都必须有一个正则式和一个文本串，一个捏在手里，一个吃下去。
DFA 捏着文本串去比较正则式，看到一个子正则式，就把可能的匹配串全标注出来，然后再看正则式的下一个部分，根据新的匹配结果更新标注。
而 NFA 是捏着正则式去比文本，吃掉一个字符，就把它跟正则式比较，匹配就记下来：“某年某月某日在某处匹配上了！”，然后接着往下干。一旦不匹配，就把刚吃的这个字符吐出来，一个个的吐，直到回到上一次匹配的地方。
引擎 区别 语言 匹配方式
DFA 速度快、特性少 mysql等 拿文本去比较正则
NFA 速度慢、特性多 python、java、php、ruby、.net、perl等 拿正则去比较文本
ReDos攻击
2.1 缺陷实例
请在浏览器 F12 开发者工具的控制台执行以下正则表达式匹配语句，感受下浏览器的变化：
/(a+)+z/.test('aaaaab')
/(a+)+z/.test('aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab')
1
2
对于第一个语句，浏览器很快给出匹配结果 false，但是对于第二个语句，浏览器允许半个小时都出不来结果，且观察 cpu 处于高占用率状态，同时浏览器当前 Tab 页无任何响应（只能强制关闭）：
如此简单的正则匹配，JS引擎却陷入了“死循环”之中，原因下面会进行解释。
2.2 计算回溯
计算机在处理正则表达式的时候可以说是非常愚蠢，虽然看上去它们有很强的计算能力。当你需要用 a+z 表达式对字符串 aaaaaaaaaaaaaaab 进行匹配时，任何人都可以迅速告诉你无匹配结果，因为这个字符串不包含字符 z。但是计算机的正则表达式引擎并不知道！它将执行以下操作：
以上 JS 引擎的正则表达式匹配过程称为“回溯”。可以看到“回溯”所干的事效率是非常低的……
如果正则表达式是上面缺陷实例所展示的 (a+)+z，匹配文本依然是 aaaa……aaab 的话，按照上述正则回溯的过程，其需要执行的步数增长大致如下图：
如上所见，计算步骤数随着输入字符串中 X 的数量呈指数增长……
此处附上一个在线观察正则匹配过程的站点：regular-expression-visualizer。
2.3 缺陷正则
以下为存在问题的正则：
//1)英文的个人名字:
Regex: ^[a-zA-Z]+(([',.-][a-zA-Z ])?[a-zA-Z])$
Payload: aaaaaaaaaaaaaaaaaaaaaaaaaaaa!
//2)Email格式验证
Regex: ^(0-9a-zA-Z@(([0-9a-zA-Z])+([-\w][0-9a-zA-Z])*.)+[a-zA-Z]{2,9})$
Payload: a@aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!
//3)复数验证
Regex: ^\d0-9*$
Payload: 1111111111111111111111111!
//4)模式匹配
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!
//5)DataVault:
Regex: ^[(,.)]$
Payload: [,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
//6)WinFormsAdvanced:
Regex: \A([A-Z,a-z]\s?[0-9][A-Z,a-z])\Z
Payload: aaaaaaaaaaaaaaaaaa!
//7)EntLib:
Regex: ^([^"]+)(?:([^"]+))*$
Payload: \\\\\\\\“
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
发现有以下规律：
正则表达式将重复元字符（+、*）应用于复杂的子表达式。；
对于重复元字符的子表达式，存在一个匹配，同时该匹配也是另一个有效匹配的后缀。
简单表达出来为下几种情况：
(a+)+
([a-zA-Z]+)
(a|aa)+
(a|a?)+
(.a){x} for x > 10
1
2
3
4
5
2.4 检测工具
ReDos攻击往往需要结合白盒审计才能有效发现存在缺陷的正则表达式。那么在已知源码的情况下，如何快速判断一个正则表达式是否存在问题呢？
直接上链接： Github regexploit，安装方式很简单：
使用方法更简单……
输入你想要检测的正则表达式，即可判断是否存在 ReDos 攻击，并且给出 Payload。
总结
ReDos攻击的防范手段：
降低正则表达式的复杂度，尽量少用分组；
严格限制用户输入的字符串长度(特定情况下)；
使用单元测试、fuzzing 测试保证安全；
使用静态代码分析工具, 如: sonar；
添加服务器性能监控系统, 如: zabbix。
本文参考：
Github regexploit；
一个由正则表达式引发的血案（解决版）；
正则表达式所引发的DoS攻击（Redos）；
JavaScript Web服务器ReDoS漏洞分析；
正则redos攻击，一行简单的代码是怎样让浏览器彻底崩溃的！
————————————————
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/weixin_39190897/article/details/125692338
