当您需要搜索和替换文本时，正则表达式会派上用场。但是，在某些情况下，它们可能会导致系统变慢，甚至容易受到 ReDoS 攻击。
介绍
ReDoS 是 DoS 攻击的一个子类型。ReDoS 攻击的目的是通过低效的正则表达式停止应用程序或使其变慢。
ReDoS攻击可分为两种类型：
- 具有恶意模式的字符串将传递给应用程序。然后此字符串用作正则表达式，从而导致 ReDoS。
- 将特定格式的字符串传递给应用程序。然后，此字符串由易受攻击的正则表达式进行评估，从而导致 ReDoS。
任何 ReDoS 攻击的要点都是在应用程序中使用易受攻击的正则表达式。将某种格式的字符串传递给正则表达式会导致其计算不合理地长。
如果 ReDoS 攻击成功，则正则表达式计算会导致灾难性的回溯。这是正则表达式引擎中回溯函数的结果，该函数遍历可能的字符串匹配，直到找到正确的字符串匹配。如果没有正确的匹配项，则正则表达式在循环访问所有可能的选项之前不会停止。所有可能选项的完整迭代会导致正则表达式的计算时间过长，令人无法接受。这称为灾难性回溯。
如果正则表达式包含至少一个可能导致大量匹配选项的子表达式，则正则表达式容易受到灾难性回溯的影响。
灾难性回溯：真实例子
让我们检查几个正则表达式的漏洞。
我写了一个小程序——它显示了正则表达式的计算时间如何取决于计算字符串中的字符数的图表。在接下来的示例中，我将使用此程序向您展示灾难性的回溯。
例 1
让我们看一个简单的合成示例：
(x+)+y让我们比较两种情况下 （x+）+y 表达式的计算时间：
- 正则表达式的输入逐个接受与指定模式对应的字符串。同时，每个后续字符串的长度比前一个字符串多 1。
- 正则表达式的输入接受与模式不匹配的字符串（字符串末尾没有 y 字符）。同时，每个后续字符串的长度比前一个字符串多 1。
这种实验的结果如下：
图 1：如果字符串与模式 （x+）+y 匹配，则正则表达式的执行时间。
图 2：如果字符串与 （x+）+y 模式不匹配（ 末尾缺少 y 字符），则正则表达式的执行时间。
如您所见，第一组的字符串会立即处理。但是，第二组的处理呈指数级增长！为什么会这样？
问题是，在第一种情况下，正则表达式在第一次尝试时找到匹配项。在第二种情况下处理字符串时，一切都变得非常复杂。x+ 模板可以匹配任意数量的 x 个字符。（x+）+ 模板可以适合由一个或多个与 x+ 对应的子字符串组成的字符串。因此，有许多选项可以将字符串与正则表达式匹配。它们的数量取决于由 x 个字符组成的子字符串的长度。每次正则表达式找不到 y 字符时，它就会开始检查下一个选项。只有在检查了所有这些之后，正则表达式才会给出答案 — 没有找到匹配项。
下表显示了 xxxx 字符串与 （x+）+y 正则表达式的几种可能匹配：
幸运的是，并非所有正则表达式都容易受到灾难性回溯的影响。如果正则表达式满足以下条件，则容易受到攻击：
- 有两个子表达式，其中一个包含另一个子表达式。此外，以下量词之一应用于它们中的每一个：“*”，“+”，“*？”，“+？”，“{…}”。在前面的示例中，（x+）+ 子表达式包含 x+。
- 有一个字符串可以与两个子表达式匹配。例如，xxxx 字符串可能同时适合 x+ 和 （x+）+ 模板。
（\d？|的表达式….|[1-9])+ 类型是一个小例外。这里是 （\d？|….|[1-9])+ 表达式包括子表达式 \d？ 和 [1-9]。它们通过“|”运算符枚举。这些子表达式也可以适合相同的字符串，例如 111。在这种情况下，将“？”量词应用于其中一个子表达式也会导致漏洞。
例 2
我们发现 （x+）+y 表达式很脆弱。现在让我们通过添加对另一个字符是否存在的检查来稍微更改它：
(x+z)+y现在我们有 （x+z）+ 子表达式，xz 和 xxxxz 字符串可以匹配到这个表达式。此子表达式包括 x+ 子表达式，它可以对应于 x、xxxx 等字符串。如您所见，这些子表达式不能与相同的值匹配。因此，第二个条件不满足，也没有灾难性的回溯。
图 3：尝试使用一组字符串“破坏”正则表达式失败。它们中的每一个都对应于 x+ 子表达式或 （x+z）+ 子表达式。
例 3
现在让我们看看下一个正则表达式：
newDate\((-?\d+)*\)这个正则表达式有一个任务 — 搜索 newDate（12-09-2022） 类型的子字符串。我们可以称之为正则表达式安全吗？不。除了正确的字符串外，正则表达式还会考虑正确的 newDate（8-911-111-11-11） 甚至 newDate（1111111111111） 字符串。但是，要了解问题的本质，这样的表达对我们来说就足够了。
上述选项都不会导致灾难性的回溯。但是，如果我们处理“newDate（1111111111111”类型的字符串，就会发生这种情况。
图 4：与模式不匹配的正则表达式检查字符串的执行时间（字符串末尾没有右括号）。
我们再次看到灾难性的回溯。发生这种情况是因为 （-？\d+）* 子表达式，其中包括 \d+ 子表达式。“*”或“+”量词应用于两个子表达式，并且同一字符串可以与每个子表达式匹配，例如 111。
让我们将这些观察结果与之前检查的正则表达式的条件进行比较：
- 有两个子表达式，其中一个包含另一个子表达式。以下量词之一应用于它们中的每一个：“*”、“+”、“*？”、“+？”、“{…}”。（-？\d+）*） 子表达式包括 \d+;
- 有一个字符串可以与两个子表达式匹配。例如，1111 字符串可能同时适合 \d+ 模板和 （-？\d+）*）。
顺便说一下，newDate\（（-？\d+）*\） 正则表达式在一个真实项目——RestSharp 库中造成了一个漏洞 （CVE-2021-27293）。
例 4
作为最后一个例子，让我们在更复杂的正则表达式中寻找漏洞：
^(([A-Z]:|\\main)(\\[^\\]+)*(,\s)?)+$此表达式的任务是查找表示文件或目录路径列表的字符串。此列表中的每个元素都用逗号和空格字符分隔。列表项可以由对应于以下两种类型之一的路径表示：
- 完整路径，例如：D：\catalog\subcatalog\file.txt，
- 主文件夹的相对路径，例如：\main\catalog\file.exe。
因此，对应于模式的字符串可能如下所示：
D：\catalog， C：\catalog\file.cs， \main\file.txt， \main\， project\main.csproj
正则表达式将毫无问题地计算此类字符串。
处理几乎任何不正确的字符串处理也是如此，例如：
D：\catalog\file.cs\catalog\file.cs\catalog\file.cs\catalog\file.cs\catalog\file.cs\catalog\file.cs\\\
但是，如果我们将以下类型的字符串传递给正则表达式，情况会发生变化：
D：\main\main\main\main\main\main\main\main\
图 5：处理 D：\main …\main\\\ 格式。
让我们检查一下原始正则表达式 （^（（[A-Z]：|\\main）（\\[^\\]+）*（，\s）？）+$） 了解更多详情。请注意，相互跟随的子表达式 （[A-Z]：|\\main） 和 （\\[^\\]+）* 可以与相同的 \main 字符串匹配。此外，可以忽略以下子表达式 （（，\s）？），因为“？”量词允许与此模板不匹配。
因此，可以简化原始正则表达式以仅检查一种特殊情况 – D：\main …\main 格式的字符串：
^(([A-Z]:|\\main)(\\main)*)+$当我们查看此字符串的简化版本时，灾难性回溯漏洞变得清晰起来。
- 有一个子表达式 （（[A-Z]：|\\main）（\\main）*）+ 带有“+”量词。此子表达式包括 （\\main）* 和“*”量词。
- 两个子表达式：（（[A-Z]：|\\main）（\\main）*）+ 和 （\\main）* 可能适合同一个字符串，例如 \main\main\main。
因此，脆弱表达式的两个条件都满足。
让我们重点介绍导致 ^（（[A-Z]：|\\main）（\\[^\\]+）*（，\s）中灾难性回溯的主要因素？+$ 正则表达式：
- “+”量词应用于 （（[A-Z]：|\\main）（\\[^\\]+）*（，\s）？）+ 子表达式;
- “*”量词应用于 （\\[^\\]+）* 子表达式;
- 子表达式 （[A-Z]：|\\main） 和 （\\[^\\]+）* 可能适合相同的 \main 字符串;
- （，\s）？子表达式可以省略，因为“？”量词。
缺少其中至少一个将使正则表达式绝对安全。
如何防止灾难性回溯
让我们看一下保护正则表达式免受灾难性回溯的主要方法。我们将使用 newDate\（（-？\d+）*\） 作为示例。下面的代码是用 C# 编写的。但是，类似的功能可能存在于支持正则表达式的其他编程语言中。
选项 1
添加对通过正则表达式处理字符串的执行时间限制。在 .NET 中，我们可以通过在调用静态方法或初始化新的正则表达式对象时设置 matchTimeout 参数来做到这一点。
RegexOptions options = RegexOptions.None;
TimeSpan timeout = TimeSpan.FromSeconds(1);
Regex pattern = new Regex(@"newDate\((-?\d+)*\)", options, timeout);
Regex.Match(str, @"newDate\((-?\d+)*\)", options, timeout);
图 6：正则表达式的执行时间限制为一秒。
选项 2
使用原子组 （？>…）：
Regex pattern = new Regex(@"newDate\((-?\d+)*\)", options, timeout);
对于标记为原子组的表达式，将禁用回溯功能。因此，在所有可能的匹配选项中，原子组将始终仅与一个包含最大字符数的子字符串匹配。
尽管原子群是防止灾难性回溯的可靠方法，但我们建议谨慎使用它们。在某些情况下，使用原子组会降低正则表达式计算的准确性。
图 7：标记为原子组的子表达式不再容易受到灾难性回溯的影响。
选项 3
通过将不安全的子表达式替换为安全的等效项来重写正则表达式。例如，若要查找 newDate（13-09-2022） 类型的字符串，可以使用 newDate\（（\d{2}-\d{2}-\d{4}）\） 而不是 newDate\（（-？\d+）*\）。
后者有两个子表达式：（-？\d+）* 和 \d+。\d+ 子表达式包含在 （-？\d+）* 中。同一个子字符串可以匹配这两个子表达式。安全等效项允许将任何子字符串与只有一个模板匹配，因为模板 \d{…} 之间必须检查“-”字符。