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



CVE-2021-33623声明以下代码(在本次提交中修复,包括测试用例(存在与ReDoS相关的问题:

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

但为什么它容易受到ReDoS攻击呢?

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

因此,[rn]+$不会找到字符串的末尾,而是使用一个或多个换行字符向后移动,相反,正则表达式引擎会检查字符串中每个位置的换行字符,一旦找到,就会检查字符串的末尾因此,如果字符串很大,可能会导致性能非常低。

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

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

最新更新