CodeQL 文档
CodeQL 资源

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

ID: js/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:
   - javascript-code-scanning.qls
   - javascript-security-extended.qls
   - javascript-security-and-quality.qls

点击查看 CodeQL 仓库中的查询

某些正则表达式需要很长时间才能将某些输入字符串与之匹配，以至于匹配长度为 *n* 的字符串所需的时间与 *nk* 甚至 *2n* 成正比。这种正则表达式会对性能造成负面影响，甚至可能允许恶意用户通过为正则表达式构造一个代价高昂的输入字符串来执行拒绝服务（“DoS”）攻击。

许多流行的 JavaScript 平台提供的正则表达式引擎使用回溯非确定性有限自动机来实现正则表达式匹配。虽然这种方法在空间上效率很高，并且支持捕获组等高级特性，但它在时间上一般效率不高。这种自动机的最坏情况时间复杂度可能是多项式甚至指数级的，这意味着对于某些形状的字符串，将输入长度增加十个字符可能会使自动机慢 1000 倍左右。

通常，如果正则表达式包含`r*`或`r+`形式的重复，则该正则表达式会受到此问题的困扰，其中子表达式`r`是模棱两可的，因为它可以以多种方式匹配某些字符串。有关确切情况的更多信息，请参阅参考资料。

建议

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

示例

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

text.replace(/^\s+|\s+$/g, ''); // BAD

子表达式`"\s+$"`将从左到右匹配`text`中的空白字符，但它可以在空白序列中的任何位置开始匹配。对于**不**以空白字符结尾的字符串，这将是一个问题。这样的字符串将迫使正则表达式引擎为序列中的每个空白字符处理一次每个空白序列。

最终这意味着修剪字符串的时间成本是字符串长度的平方。因此，像`“a b”`这样的字符串将需要几毫秒才能处理，但类似的字符串，用一百万个空格而不是一个空格，将需要几分钟才能处理。

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

请注意，子表达式`“^\s+”`**不是**问题，因为`^`锚点限制了该子表达式可以开始匹配的位置，并且由于正则表达式引擎从左到右匹配。

示例

作为类似但略微微妙的问题，考虑匹配包含数字的行的正则表达式，这些数字可能使用科学记数法编写

/^0\.\d+E?\d+$/.test(str) // BAD

这个正则表达式的错误在于子表达式 \d+E?\d+，因为如果输入字符串中没有 E，第二个 \d+ 可以从第一个 \d+ 匹配的任何位置开始匹配数字。

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

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

示例

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

/^(\+|-)?(\d+|(\d*\.\d*))?(E|e)?([-+])?(\d+)?$/.test(str) // BAD

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

if (str.length > 1000) {
    throw new Error("Input too long");
}

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

参考资料

  • ©GitHub, Inc.
  • 条款
  • 隐私