为什么 CVE-2021-33623 易受 ReDoS 攻击?
Why is CVE-2021-33623 vulnerable to ReDoS?
CVE-2021-33623 states that the following code (fixed in this commit,其中包括测试用例)有与 ReDoS 相关的问题:
trimNewlines.end = string => string.replace(/[\r\n]+$/, '');
但为什么它容易受到 ReDoS 攻击?
正则表达式的时间复杂度为 O(n²)
,因为正则表达式引擎会尝试匹配字符串中每个位置的表达式。请注意,正则表达式引擎从左到右解析输入字符串,尝试在每个位置后的每个位置进行匹配,并且模式序列也从左到右检查。所以,先取 [\r\n]+
,正则表达式引擎尝试匹配字符串的开头,如果没有 CR/LF 个字符,则停止当前位置的模式处理,将索引移动到尝试字符串中的下一个位置 [\r\n]+
... 直到匹配 CR/LF 个字符。仅当它们匹配时,才会检查 $
。
因此,[\r\n]+$
没有找到字符串的末尾并返回消耗一个或多个换行符字符,相反,正则表达式引擎检查字符串中的每个位置以查找该行break chars,一旦找到,就会检查字符串的结尾。 因此,如果字符串很大,这会导致性能非常低。
在某些正则表达式风格中,有一种方法可以告诉正则表达式引擎从字符串末尾搜索匹配项,例如,在 .NET 中(使用 RegexOptions.RightToLeft
选项),或在 Python PyPi regex
模块(带有 regex.REVERSE
选项或 (?r)
内联版本)。不幸的是,在 JavaScript.
中并非如此
可能,最安全的方法是匹配换行符以外的任何字符,然后是换行符,捕获它们,但是在捕获组中保留一个长字符串可能也不是一个好主意。因此,虽然您可以考虑采用 131 (132) steps to complete a match on the given test input compared to 880 steps([\r\n]+$
模式需要)的 .replace(/^([\r\n]*[^\r\n]+(?:[\r\n]+[^\r\n]+)*)[\r\n]+$/, '')
(或 .replace(/^((?:[\r\n]*[^\r\n]+)+)[\r\n]+$/, '')
),但在这些情况下,仅使用字符串操作似乎是最好的方法.
CVE-2021-33623 states that the following code (fixed in this commit,其中包括测试用例)有与 ReDoS 相关的问题:
trimNewlines.end = string => string.replace(/[\r\n]+$/, '');
但为什么它容易受到 ReDoS 攻击?
正则表达式的时间复杂度为 O(n²)
,因为正则表达式引擎会尝试匹配字符串中每个位置的表达式。请注意,正则表达式引擎从左到右解析输入字符串,尝试在每个位置后的每个位置进行匹配,并且模式序列也从左到右检查。所以,先取 [\r\n]+
,正则表达式引擎尝试匹配字符串的开头,如果没有 CR/LF 个字符,则停止当前位置的模式处理,将索引移动到尝试字符串中的下一个位置 [\r\n]+
... 直到匹配 CR/LF 个字符。仅当它们匹配时,才会检查 $
。
因此,[\r\n]+$
没有找到字符串的末尾并返回消耗一个或多个换行符字符,相反,正则表达式引擎检查字符串中的每个位置以查找该行break chars,一旦找到,就会检查字符串的结尾。 因此,如果字符串很大,这会导致性能非常低。
在某些正则表达式风格中,有一种方法可以告诉正则表达式引擎从字符串末尾搜索匹配项,例如,在 .NET 中(使用 RegexOptions.RightToLeft
选项),或在 Python PyPi regex
模块(带有 regex.REVERSE
选项或 (?r)
内联版本)。不幸的是,在 JavaScript.
可能,最安全的方法是匹配换行符以外的任何字符,然后是换行符,捕获它们,但是在捕获组中保留一个长字符串可能也不是一个好主意。因此,虽然您可以考虑采用 131 (132) steps to complete a match on the given test input compared to 880 steps([\r\n]+$
模式需要)的 .replace(/^([\r\n]*[^\r\n]+(?:[\r\n]+[^\r\n]+)*)[\r\n]+$/, '')
(或 .replace(/^((?:[\r\n]*[^\r\n]+)+)[\r\n]+$/, '')
),但在这些情况下,仅使用字符串操作似乎是最好的方法.