为什么 CVE-2021-33623 容易受到 ReDoS 攻击？

Question

CVE-2021-33623指出以下代码（在此提交中修复，包括测试用例）存在与 ReDoS 相关的问题：

trimNewlines.end = string => string.replace(/[\r\n]+$/, '');

但究竟为什么它容易受到 ReDoS 攻击？

Answer 1

正则表达式的时间复杂度是O(n\xc2\xb2)因为正则表达式引擎尝试匹配字符串内每个位置的表达式。请注意，正则表达式引擎从左到右解析输入字符串，尝试在每个位置后匹配，并且模式序列也从左到右检查。因此，[\\r\\n]+首先，正则表达式引擎尝试在字符串的开头进行匹配，如果没有 CR/LF 字符，则停止当前位置的模式处理，将索引移动到字符串内的下一个位置，[\\r\\n]+尝试...直到它匹配 CR/LF 字符。只要它们匹配，$才会进行检查。

\n

因此，不会[\\r\\n]+$找到字符串的结尾并向后移动，消耗一个或多个换行符，相反，正则表达式引擎会检查字符串中每个位置的换行符，一旦找到，就会检查字符串的结尾。因此，如果字符串很大，可能会导致性能非常低。

\n

在某些正则表达式风格中，有一种方法可以告诉正则表达式引擎从字符串末尾搜索匹配项，例如在 .NET 中（使用RegexOptions.RightToLeft选项）或在 Python PyPiregex模块中（使用regex.REVERSE选项或(?r)内联版本）。不幸的是，JavaScript 中并非如此。

\n

也许，最安全的方法是匹配除换行符之外的任何字符，然后跟随换行符，捕获它们，但在捕获组内保留长字符串可能也不是一个好主意。因此，虽然您可以考虑.replace(/^([\\r\\n]*[^\\r\\n]+(?:[\\r\\n]+[^\\r\\n]+)*)[\\r\\n]+$/, \'$1\')(或.replace(/^((?:[\\r\\n]*[^\\r\\n]+)+)[\\r\\n]+$/, \'$1\')) 需要131 (132) 步才能完成给定测试输入的匹配，而需要880 步（对于[\\r\\n]+$，但在这些情况下，仅使用字符串操作似乎是最佳方法。

\n