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

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

点击查看 CodeQL 存储库中的查询

某些正则表达式需要很长时间才能将某些输入字符串匹配到一个点，在这个点上匹配长度为n 的字符串所需的时间与n^k 甚至2ⁿ 成正比。此类正则表达式会对性能产生负面影响，甚至允许恶意用户通过为正则表达式匹配构造一个昂贵的输入字符串来执行拒绝服务（“DoS”）攻击。

Java 提供的正则表达式引擎使用回溯非确定性有限自动机来实现正则表达式匹配。虽然此方法具有空间效率，并且允许支持高级功能（如捕获组），但它通常不具有时间效率。此类自动机的最坏情况时间复杂度可以是多项式的，甚至可以是指数的，这意味着对于特定形状的字符串，将输入长度增加十个字符可能会使自动机的速度降低约 1000 倍。

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

请注意，Java 9 及更高版本对 ReDoS 有一些缓解措施；但是它们并不完美，更复杂的正则表达式仍然可能受到此问题的影响。

建议¶

修改正则表达式以消除歧义，或确保使用正则表达式匹配的字符串足够短，以至于时间复杂度无关紧要。或者，可以使用保证线性时间执行的备用正则表达式库，例如 Google 的 RE2J。

示例¶

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

Pattern.compile("^\\s+|\\s+$").matcher(text).replaceAll("") // BAD

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

这最终意味着修剪字符串的时间成本与字符串的长度成二次方关系。因此，像 "a b" 这样的字符串将花费数毫秒来处理，但一个类似的字符串，其中有百万个空格而不是一个空格，将花费几分钟。

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

请注意，子表达式 "^\\s+" 不是有问题的，因为 ^ 锚定限制了该子表达式何时可以开始匹配，并且正则表达式引擎从左到右匹配。

示例¶

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

"^0\\.\\d+E?\\d+$""

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

对于不以数字结尾的字符串，这是有问题的。这样的字符串将强制正则表达式引擎对序列中的每个数字进行处理，再次导致二次时间复杂度。

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

示例¶

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

Pattern.matches("^(\\+|-)?(\\d+|(\\d*\\.\\d*))?(E|e)?([-+])?(\\d+)?$", str); 

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

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

Pattern.matches("^(\\+|-)?(\\d+|(\\d*\\.\\d*))?(E|e)?([-+])?(\\d+)?$", str); 

参考¶

OWASP：正则表达式拒绝服务 - ReDoS。
Wikipedia：ReDoS。
Wikipedia：时间复杂度。
James Kirrage、Asiri Rathnayake、Hayo Thielecke：正则表达式拒绝服务攻击的静态分析。
通用弱点枚举：CWE-1333。
通用弱点枚举：CWE-730。
通用弱点枚举：CWE-400。

©GitHub, Inc.
条款
隐私