低效正则表达式¶

ID: java/redos
Kind: problem
Security severity: 7.5
Severity: error
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。

示例¶

考虑此正则表达式

^_(__|.)+_$

它的子表达式 "(__|.)+?" 可以通过 "|" 运算符左侧的第一个备选方案 "__" 或通过右侧第二个备选方案 "." 的两次重复来匹配字符串 "__"。因此，由奇数个下划线后跟其他一些字符组成的字符串将导致正则表达式引擎在拒绝输入之前运行指数量的时间。

可以通过重写正则表达式来消除重复内部备选的两个分支之间的歧义，从而避免此问题

^_(__|[^_])+_$

参考¶

OWASP：正则表达式拒绝服务 - ReDoS。
维基百科：ReDoS。
维基百科：时间复杂度。
詹姆斯·基拉奇、阿西里·拉特纳亚克、海约·蒂勒克：正则表达式拒绝服务攻击的静态分析。
常见弱点枚举：CWE-1333。
常见弱点枚举：CWE-730。
常见弱点枚举：CWE-400。

©GitHub, Inc.
条款
隐私