低效正则表达式¶

ID: rb/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:
   - 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 是模棱两可的，因为它可以以多种方式匹配某些字符串。有关具体情况的更多信息，请参见参考资料。

建议¶

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

示例¶

考虑以下正则表达式

/^_(__|.)+_$/

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

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

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

参考资料¶

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