Redos攻击原理与检测防御

发表于 | 分类于 | 阅读次数

同名博客发表于菊厂3ms

Regular expression Denial of Service (ReDoS)是一种利用程序实现时采用了不安全的正则表达式，从而构造特定输入引起DOS拒绝服务的一种攻击手段。

在正式讨论ReDos之前，先来介绍一下预备知识。

Regex与DFA、NFA

不想看原理可以直接跳过去看例子，部分人可秒懂

正则表达式，又称规则表达式，英文名为Regular Expression，在代码中常简写为regex、regexp或RE，是计算机科学的一个概念。

正则表通常被用来检索、替换那些符合某个模式(规则)的文本。

正则表达式是对字符串（包括普通字符（例如，a 到 z 之间的字母）和特殊字符（称为“元字符”））操作的一种逻辑公式，就是用事先定义好的一些特定字符、及这些特定字符的组合，组成一个“规则字符串”，这个“规则字符串”用来表达对字符串的一种过滤逻辑。

正则表达式是一种文本模式，模式描述在搜索文本时要匹配的一个或多个字符串。

DFA 引擎在线性时状态下执行，因为它们不要求回溯（并因此它们永远不测试相同的字符两次）。
DFA 引擎还可以确保匹配最长的可能的字符串。
但是，因为 DFA 引擎只包含有限的状态，所以它不能匹配具有反向引用的模式；并且因为它不构造显示扩展，所以它不可以捕获子表达式。

传统的 NFA 引擎运行所谓的“贪婪的”匹配回溯算法，以指定顺序测试正则表达式的所有可能的扩展并接受第一个匹配项。
因为传统的 NFA 构造正则表达式的特定扩展以获得成功的匹配，所以它可以捕获子表达式匹配和匹配的反向引用。
但是，因为传统的 NFA 回溯，所以它可以访问完全相同的状态多次（如果通过不同的路径到达该状态）。
因此，在最坏情况下，它的执行速度可能非常慢。因为传统的 NFA 接受它找到的第一个匹配，所以它还可能会导致其他（可能更长）匹配未被发现。

POSIX NFA 引擎与传统的 NFA 引擎类似。
不同的一点在于：在它们可以确保已找到了可能的最长的匹配之前，它们将继续回溯。
因此，POSIX NFA 引擎的速度慢于传统的 NFA 引擎；并且在使用 POSIX NFA 时，您恐怕不会愿意在更改回溯搜索的顺序的情况下来支持较短的匹配搜索，而非较长的匹配搜索。

  • 使用DFA引擎的程序主要有：awk,egrep,flex,lex,MySQL,Procmail等；
  • 使用传统型NFA引擎的程序主要有：GNU Emacs,Java,ergp,less,more,.NET语言,PCRE library,Perl,PHP,Python,Ruby,sed,vi；
  • 使用POSIX NFA引擎的程序主要有：mawk,Mortice Kern Systems’ utilities,GNU Emacs(使用时可以明确指定)；
  • 也有使用DFA/NFA混合的引擎：GNU awk,GNU grep/egrep,Tcl。

下面用实例来说明正则匹配时，NFA与DFA引擎的区别：

1
2
字符串： hello regextest
正则表达式：  \reg(axtest|extext|extest)

DFA：拿着字符串文本去匹配正则表达式。
hello没有正则匹配的，去掉，reg匹配上了，继续；exte和第二、三分支匹配，继续；st和第三分支匹配，至此，regextest匹配成功，结束。过程中字符串只遍历了一次。

NFA：拿着正则表达式去对比字符串文本。
r->淘汰hello，匹配到r，e->e，g->g，a->e失败，回溯到上一个匹配的g，匹配下一个正则，e->e，x->x，t->t，e->e，x->s失败，回溯到上一个匹配的e，匹配下一个正则，s->s，t->t，匹配成功，结束。过程中字符串遍历了多次。

DOS

DOS攻击这里引用段子嘎的介绍：
DoS（Denial of Service，拒绝服务）是一种网络攻击手段，通过大量合法的请求占用大量网络资源，以达到瘫痪网络的目的。
形象一点的比喻是，你开了一家小面馆，黑客派了几个广场的大爷大妈涌入你的店里坐着吹空调，也不消费就霸着场子，导致其他顾客根本无法进店消费。
想详细了解可自行去查资料。


下面开始介绍本文重点：ReDos

原理

本文主要介绍使用NFA引擎的程序语言，使用DFA引擎的程序不存在ReDos。因为NFA引擎的回溯机制，导致了当字符串文本与正则表达式不匹配时，所花费的时间要比匹配时长的多。
简单点说，确定匹配成功就不做了，但是要确定匹配失败，则需要与所有可能的路径进行对比匹配，都证明匹配不了，才能确定匹配失败。

此时，如果使用简单的非分组正则表达式来进行匹配，也不会引起问题，例如：

1
^\d+$

  • 1）23x
    23,x　　2,3x 　　23x
    标粗部分为确认不匹配的部分，第一次遇到不匹配时回溯到上一个继续进行匹配，共3次

  • 2）123x
    123,x　　12,3x　　1,23x　　123x
    标粗部分为确认不匹配的部分，第一次遇到不匹配时回溯到上一个继续进行匹配，共4次

此时呈线性增长。

但是，如果使用重复性分组正则表达式来进行匹配，则可能引起问题，例如：

1
^\(d+)+$

  • 1）23x
    23,x　　2,3,x　　2,3x 　　23x
    标粗部分为确认不匹配的部分，迭代多次才能确认原字符串不匹配，总共需要2^2 = 4次

  • 2）123x
    123,x　　12,3,x　　12,3x　　1,23,x　　1,2,3,x　　1,2,3x　　1,23x　　123x
    标粗部分为确认不匹配的部分，迭代多次才能确认原字符串不匹配，总共需要2^3 = 8次

此时呈指数增长。


验证

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# coding:utf-8
import time
import re
strs = (
    '1234567890x',
    '12345678901234567890x',
    '1234567890123456789012345x',
    '12345678901234567890123456x',
    '123456789012345678901234567x',
    '1234567890123456789012345678x',
    '12345678901234567890123456789x'
)
regex = '^(\d+)+$'
def fun(strs, regex):
    t1 = time.time()
    result = re.compile(regex).match(strs)
    t2 = time.time()
    print("%s : %s : %.2f" % (strs, str(result), (t2 - t1)))
for s in strs:
    fun(s, regex)

运行结果：

1
2
3
4
5
6
7
8
9
10
C:\Python\Python36\python.exe D:/python/get_hi3ms_user_files/redos/redos.py
1234567890x : None : 0.00
12345678901234567890x : None : 0.09
1234567890123456789012345x : None : 2.95
12345678901234567890123456x : None : 5.92
123456789012345678901234567x : None : 12.51
1234567890123456789012345678x : None : 24.68
12345678901234567890123456789x : None : 52.39
Process finished with exit code 0

可以看出每增加一位，其运行时间呈现指数增长。

再来查看运行时的CPU占用，测试机子为4核电脑，单进程跑，CPU25%，单核占满了。

同时运行4个程序就能跑满100%CPU，可造成拒绝服务。

影响

容易引起ReDos的正则表达式主要有两类：
1、 包含具有自我重复的重复性分组的正则，例如：

1
2
3
4
5
^(\d+)+$
^(\d*)*$
^(\d+)*$
^(\d+|\s+)*$
…

2、 包含替换的重复性分组，例如：

1
2
3
^(\d|\d|\d)+$
^(\d|\d?)+$
…

目前已经在使用的，甚至是一些官方提供的正则表达式，也可能存在缺陷：

1、 正则表达式库网站中，提供的专门用于验证电子邮件的正则

1
/^([a-zA-Z0-9])(([\-.]|[_]+)?([a-zA-Z0-9]+))*(@){1}[a-z0-9]+[.]{1}(([a-z]{2,3})|([a-z]{2,3}[.]{1}[a-z]{2,3}))$/

输入：aaaaaaaaaaaaaaaaaaaaaaaa!

2、 OWASP验证正则表达式库，这也是一个有缺陷的正则：

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

输入：aaaaaaaaaaaaaaaaaaaaaaaa!

3、 常用的：
多个邮箱地址验证

1
^[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!

复数验证

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

输入: 1111111111111111111111111!

模式匹配

1
^([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!

另外，攻击者也可能通过输入来自己构造缺陷正则，从而发起攻击：
例如：

1
2
3
4
String userName = textBox1.Text;
String password = textBox2.Text;
Regex testPassword = new Regex(userName);
match match = testPassword.Match(password);

此时，攻击者输入：

1
2
Userame：^(( [az])+.)+ [AZ]([az])+$
Password：aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa！

则会引起ReDos.

风险因素

在web的每一层都包含有正则表达式，也就是每一层都会存在有缺陷的正则风险。
攻击者能够攻击Web浏览器（PC端或者移动端）、WAF、数据库或者是Web服务器。

检测

其实理想的方法是在代码编译时用一个正则去查找匹配存在缺陷的正则表达式，然而搜索了一下，没有找到这种有效的正则。目前比较好的检测手段主要分两种。

  • 一是静态代码工具分析，通过抓取代码中的正则去匹配已知的存在缺陷的特征库，重点需要检测存在分组和重复的正则，这种方法的准确率主要依赖于特征库的质量。
  • 二是通过模糊测试去程序中进行检测。在使用了正则的地方不断使用多种字符串去进行输入匹配，记录下引擎在判断是否匹配时花费的时间，时间过长则很有可能存在不安全的正则。这种方法依赖于构造的字符串是否够全面。

防御

目前主要的防御手段主要还是在程序中避免出现不安全的正则：

  • 1、 在编写正则的时候，尽量不要使用过于复杂的正则，越复杂越容易有缺陷，且越不容易进行全面的测试；
  • 2、 编写正则的时候，尽量减少分组的使用量，使用的越多出现缺陷的可能性越大
  • 3、 避免动态构造正则（即new Regex(…)），如果需要构造，也保证不要使用用户的输入来进行动态构造。
  • 4、 严格限制用户输入的长度限制。

服务端可以进行性能监控，暂时还没法进行有效的防御。




参考链接：
https://msdn.microsoft.com/zh-cn/magazine/ff646973.aspx
https://www.owasp.org/index.php/Regular_expression_Denial_of_Service_-_ReDoS
https://baike.baidu.com/item/%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F/1700215?fr=aladdin
http://www.freebuf.com/articles/network/124422.html

文章作者:Cookia

原始链接:http://cookia.cc/2017/09/13/redos/

许可协议: CC BY-NC-ND 4.0 转载请保留原文链接及作者。