《探错笔记》之一个正则引发的血案:ReDOS

ReDoS(Regular expression Denial of Service) 正则表达式拒绝服务攻击。

开发人员使用了正则表达式来对用户输入的数据进行有效性校验, 当编写校验的正则表达式存在缺陷或者不严谨时, 攻击者可以构造特殊的字符串来大量消耗服务器的系统资源，造成服务器的服务中断或停止。

ReDoS 原理

概述

正则表达式也能造成拒绝服务?是的,当正则表达式写得不好时,就有可能被恶意输入利用,消耗大量资源,从而造成DOS.这种攻击被称为ReDOS。
正则表达式引擎分成两类：一类称为 DFA（确定性有限状态自动机），另一类称为 NFA（非确定性有限状态自动机）。两类引擎要顺利工作，都必须有一个正则式和一个文本串，一个捏在手里，一个吃下去。
DFA 捏着文本串去比较正则式，看到一个子正则式，就把可能的匹配串全标注出来，然后再看正则式的下一个部分，根据新的匹配结果更新标注。
而 NFA 是捏着正则式去比文本，吃掉一个字符，就把它跟正则式比较，匹配就记下来：“某年某月某日在某处匹配上了！”，然后接着往下干。
一旦不匹配，就把刚吃的这个字符吐出来，一个个的吐，直到回到上一次匹配的地方。
部分程序及其所使用的正则引擎:
引擎类型 | 程序
——– | —–
DFA | awk(大多数版本)、egrep（大多数版本）、flex、lex、MySQL、Procmail
传统型 NFA | GNU Emacs、Java、grep（大多数版本）、less、more、.NET语言、PCRE library、Perl、PHP（所有三套正则库）、Python、Ruby、set（大多数版本）、vi
POSIX NFA | mawk、Mortice Lern System’s utilities、GUN Emacs（明确指定时使用）
DFA/NFA混合 | GNU awk、 GNU grep/egrep、 Tcl
DFA 对于文本串里的每一个字符只需扫描一次，比较快，但特性较少； NFA 要翻来覆去吃字符、吐字符，速度慢，但是特性(如:分组、替换、分割)丰富。

NFA 支持惰性(lazy) 、回溯(backtracking) 、反向引用(backreference) ， NFA 缺省应用 greedy 模式， NFA 可能会陷入递归险境导致性能极差。

说明

ReDOS 是一种代码实现上的缺陷。我们知道正则表达式是基于NFA(Nondeterministic Finite Automaton)的,它是一个状态机, 每个状态和输入符号都可能有许多不同的下一个状态。正则解析引擎将遍历所有可能的路径直到最后。由于每个状态都有若干个“下一个状态”,因此决策算法将逐个尝试每个“下一个状态”,直到找到一个匹配的。
我们定义一个正则表达式 ^(a+)+$ 来对字符串 aaaaX 匹配。使用 NFA 的正则引擎，必须经历 2^4=16 次尝试失败后才能否定这个匹配。
但是当输入以下字符串时:
aaaaaaaaaaaaaaaaX
就变成了65536条可能的路径;此后每增加一个“a”,路径的数量都会翻倍。
这极大地增加了正则引擎解析数据时的消耗。当用户恶意构造输入时,这些有缺陷的正则
表达式就会消耗大量的系统资源(比如CPU和内存),从而
导致整台服务器的性能下降,表现
的结果是系统速度很慢,有的进程或服务失去响应, 与拒绝服务的后果是一样的。

总结

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

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

有缺陷的正则表达式会包含如下部分：
•(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+&lt;(\w[-._\w]*\w@\w[-._\w]*\w\.\w{2,3})&gt;$|^(\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!