正则表达式所引发的DoS攻击（Redos）
⾸先，让我们介绍⼀些重点知识。
重复运算符
+是重复运算符，可代表某个字符或某个模式的重复。
ca+t 将会匹配 caaaat
此外，还有另⼀个重复运算符*。它和+之间唯⼀的区别是：+代表重复⼀次多次，*代表重复零次或多次。
ca*t  将同时匹配      caaaat和ct
ca+t  将匹配caaaat  但不会匹配  ct
贪婪匹配和⾮贪婪匹配
如果我想匹配X和y之间所有的字符，我可以简单地⽤x.*y进⾏处理，注意，.代表任意字符。因此，该表达式将成功匹配x)dw2rfy字符串。
但是，默认情况下，重复运算符是很贪婪的。他们会尝试尽可能多的匹配。
让我们再考虑上⾯的例⼦，
x.*y表达式如果对字符串axaayaaya进⾏处理，就会返回xaayaay。但是使⽤者可能并不期待这种结果，他们也许只想要字符串xaay，这
种x<anything here>y的模式就是贪婪匹配和⾮贪婪匹配发挥作⽤的地⽅。默认情况下，表达式将返回尽可能长的结果，但我们可以通过使⽤运算符?指定其进⾏⾮贪婪匹配，此时表达式为x.*?y
计算（回溯）
计算机在处理正则表达式的时候可以说是⾮常愚蠢，虽然看上去它们有很强的计算能⼒。当你需要⽤x*y表达式对字符串xxxxxxxxxxxxxx进⾏匹配时，任何⼈都可以迅速告诉你⽆匹配结果，因为这个字符串不包含字符y。但是计算机的正则表达式引擎并不知道！它将执⾏以下操作
xxxxxxxxxxxxxx # 不匹配
xxxxxxxxxxxxxx # 回溯
xxxxxxxxxxxxx  # 不匹配
xxxxxxxxxxxxx  # 回溯
xxxxxxxxxxxx  # 不匹配
xxxxxxxxxxxx  # 回溯
xxxxxxxxxxx    # 不匹配
xxxxxxxxxxx    # 回溯
>>很多很多步骤
xx            # 不匹配
x              # 回溯
x              # 不匹配
# ⽆匹配结果
你不会以为结束了吧？这只是第⼀步！
现在，正则表达式引擎将从第⼆个x开始匹配，然后是第三个，然后是第四个，依此类推到第14个x。
最终总步骤数为256。
它总共需要256步才能得出⽆匹配结果这⼀结论。计算机在这⽅⾯真的很蠢。
同样，如果你使⽤⾮贪婪匹配，x*?y表达式会从⼀个字母开始匹配，直到尝试过所有的可能，这和贪婪匹配⼀样愚蠢。
利⽤
正如之前所见，使⽤正则表达式进⾏匹配搜索可能需要计算执⾏⼤量计算步骤，但⼀般来说这并不是问题，因为计算机速度很快，并且可以在眨眼间完成数千个步骤。
但是，计算机也是有极限的，我们能否造出⼀个字符串让计算机长时间的超负荷运转？这很有趣，也许我们可以试试以下简单的步骤：
了解正则表达式的模式
查看它是否有可能回溯
查看它是否有重复符号
regex匹配
查看它是否有安全限制
DoS！
那么，我们到底如何发现这些潜在的攻击点呢？
重复运算符嵌套
如果你看到⼀个重复运算符嵌套于另⼀个重复运算符，就可能存在问题。
表达式：  xxxxxxxxxx 17945(x+)*y
Motive: 会匹配任意数量的x加上⼀个y
匹配字符串: xxxxxxxxxx(10 chars)
计算步骤数: 17945
此时计算步骤数并不算多，但是，这个增长趋势是很惊⼈的。
字符串                  X的个数步数
z                      0                      3
xz                    1                      6
xxz                    2                      19
xxxz                  3                      49
xxxxz                  4                      122
xxxxxz                5                      292
xxxxxxz                6                      687
xxxxxxxz              7                      1585
xxxxxxxxz              8                      3604
xxxxxxxxxz            9                      8086
xxxxxxxxxxz            10                    17945
xxxxxxxxxxxz          11                    39451
xxxxxxxxxxxxz          12                    86046
xxxxxxxxxxxxxz        13                    186400
xxxxxxxxxxxxxxz        14                    401443
xxxxxxxxxxxxxxxz      15                    860197
xxxxxxxxxxxxxxxxz      16                    1835048
xxxxxxxxxxxxxxxxxz    17                    3899434
xxxxxxxxxxxxxxxxxxz    18                    8257581
xxxxxxxxxxxxxxxxxxxz  19                    17432623
xxxxxxxxxxxxxxxxxxxxz  20                    36700210
xxxxxxxxxxxxxxxxxxxxxz 21                    77070388
如上所见，计算步骤数随着输⼊字符串中X的数量呈指数增长。
我不是很擅长数学，但如果输⼊40个x，貌似需要的计算步骤数是：
计算步骤数 = 98516241848729725
如果计算机可以在1秒内完成100万个计算步骤，则需要3123年才能完成所有计算。以上我们所展⽰的情况看起来很是糟糕，但是还存在其他糟糕的情况。
多个重复运算符1
如果两个重复运算符相邻，那么也有可能很脆弱。
表达式：  .*d+.jpg
Motive: 会匹配任意字符加上数字加上.jpg
匹配字符串: 1111111111111111111111111 (25 chars)
计算步骤数: 9187
它没有前⼀个那么严重，但如果程序没有控制输⼊的长度，它也⾜够致命。
多个重复运算符2
如果两个重复运算符较为相近，也有可能受到攻击。
表达式：  .*d+.*a
Motive: 会匹配任意字符串加上数字加上任意字符串加上a字符
匹配字符串: 1111111111111111111111111 (25 chars)
计算步骤数: 77600
多个重复运算符3
|符号加上[]符号再配上+也可能受到攻击。
表达式：  (d+|[1A])+z
Motive: 会匹配任意数字或任意（1或A）字符串加上字符z
匹配字符串: 111111111 (10 chars)
计算步骤数: 46342
以上就是我所知道⼀些利⽤场景情况。你还知道更多吗？欢迎和我交流。
如何寻这样的漏洞？
你⼀定想知道在哪⾥寻这样的漏洞。⽬前来说⼀般应⽤于⽩盒审计，或者⽹站代码处于开源的情况，你可以查看它是否使⽤了⼀些敏感的正则表达式。
其他
以上介绍的攻击场景并不适⽤于所有正则表达式引擎（同时受到开发语⾔的影响），且已有针对回溯攻击的防护。
资源
：⽤于检查正则表达式是否容易受到回溯影响的⼯具。
（付费）：它可以帮助您分析正则表达式。它有很多功能，包括计算步骤数，使⽤各种正则表达式引
擎等。如果正则表达式容易受到回溯的影响，它也会发出警告。
： Static Analysis for Regular ex pression Exponential Runtime via Substructural Logics
⽂章：Vulnerability in a real world regex pattern
感谢你的阅读！

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。