在不受控数据上使用的多项式正则表达式¶

ID: rb/polynomial-redos
Kind: path-problem
Security severity: 7.5
Severity: warning
Precision: high
Tags:
   - security
   - external/cwe/cwe-1333
   - external/cwe/cwe-730
   - external/cwe/cwe-400
Query suites:
   - ruby-code-scanning.qls
   - ruby-security-extended.qls
   - ruby-security-and-quality.qls

单击查看 CodeQL 代码库中的查询

一些正则表达式需要很长时间才能将某些输入字符串与之匹配，以至于匹配长度为 *n* 的字符串所花费的时间与 *n^k* 甚至 *2ⁿ* 成正比。此类正则表达式可能会对性能产生负面影响，甚至允许恶意用户通过为正则表达式匹配创建代价高昂的输入字符串来执行拒绝服务 (”DoS”) 攻击。

Ruby 解释器 (MRI) 使用的正则表达式引擎使用回溯非确定性有限自动机来实现正则表达式匹配。虽然这种方法空间效率高，并支持捕获组等高级功能，但它在一般情况下时间效率不高。这种自动机的最坏情况时间复杂度可能是多项式甚至指数级的，这意味着对于特定形状的字符串，将输入长度增加十个字符可能会使自动机慢约 1000 倍。

请注意，Ruby 3.2 及更高版本已实现了一种缓存机制，完全消除了此查询标记的正则表达式的最坏情况时间复杂度。因此，此查询标记的正则表达式仅在 3.2 之前的 Ruby 版本中存在问题。

通常，如果正则表达式包含 r* 或 r+ 形式的重复，则该正则表达式会受到此问题的影响，其中子表达式 r 是模糊的，因为它可以以多种方式匹配某些字符串。可以在参考资料中找到有关具体情况的更多信息。

建议¶

修改正则表达式以消除歧义，或确保与正则表达式匹配的字符串足够短，以至于时间复杂度无关紧要。

示例¶

考虑此正则表达式的使用，它会删除字符串中的所有前导和尾随空格

text.gsub!(/^\s+|\s+$/, '') # BAD

子表达式 "\s+$" 将从左到右匹配 text 中的空格字符，但它可以在空格序列中的任何位置开始匹配。这对不以空格字符结尾的字符串来说是个问题。这种字符串会迫使正则表达式引擎对每个空格序列进行处理，每个空格序列对应一个空格字符。

这最终意味着修剪字符串的时间成本与字符串的长度成二次方。因此，像 "a b" 这样的字符串需要几毫秒才能处理，但具有一百万个空格而不是只有一个空格的类似字符串需要几分钟。

通过重写正则表达式以不包含关于何时开始匹配空格序列的歧义来避免此问题。例如，通过使用负向后顾 (/^\s+|(?<!\s)\s+$/)，或仅使用内置的 strip 方法 (text.strip!)。

请注意，子表达式 "^\s+" 没有问题，因为 ^ 锚点限制了该子表达式可以开始匹配的位置，以及正则表达式引擎从左到右匹配。

示例¶

作为类似但稍有微妙的问题，请考虑匹配带有数字的行的正则表达式，这些数字可能使用科学计数法编写

/^0\.\d+E?\d+$/ # BAD

此正则表达式的问题在于子表达式 \d+E?\d+，因为如果输入字符串中没有 E，则第二个 \d+ 可以从第一个 \d+ 的第一个匹配之后开始匹配数字。

这对不以数字结尾的字符串来说是个问题。这种字符串会迫使正则表达式引擎对每个数字序列进行处理，每个数字序列对应一个数字，再次导致二次时间复杂度。

为了使处理速度更快，应重写正则表达式，使得两个 \d+ 子表达式没有重叠匹配：/^0\.\d+(E\d+)?$/。

示例¶

有时不清楚如何重写正则表达式以避免问题。在这种情况下，通常只需限制输入字符串的长度即可。例如，以下正则表达式用于匹配数字，并且在某些非数字输入上可能会出现二次时间复杂度

is_matching = /^(\+|-)?(\d+|(\d*\.\d*))?(E|e)?([-+])?(\d+)?$/.match?(str)

如何重写此正则表达式以避免此问题并不明显。但是，您可以通过将长度限制为 1000 个字符来缓解性能问题，这样始终可以在合理的时间内完成。

if str.length > 1000
    raise ArgumentError, "Input too long"
end

is_matching = /^(\+|-)?(\d+|(\d*\.\d*))?(E|e)?([-+])?(\d+)?$/.match?(str)

参考资料¶

OWASP：正则表达式拒绝服务 - ReDoS.
维基百科：ReDoS.
维基百科：时间复杂度.
James Kirrage、Asiri Rathnayake、Hayo Thielecke：针对正则表达式拒绝服务攻击的静态分析.
常见漏洞枚举：CWE-1333.
常见漏洞枚举：CWE-730.
常见漏洞枚举：CWE-400.