CWE-1333: Inefficient Regular Expression Complexity
CWE版本: 4.18
更新日期: 2025-09-09
弱点描述
The product uses a regular expression with an inefficient, possibly exponential worst-case computational complexity that consumes excessive CPU cycles.
扩展描述
Some regular expression engines have a feature called "backtracking". If the token cannot match, the engine "backtracks" to a position that may result in a different token that can match. Backtracking becomes a weakness if all of these conditions are met:
常见后果
影响范围: Availability
技术影响: DoS: Resource Consumption (CPU)
潜在缓解措施
阶段: Architecture and Design
描述: Use regular expressions that do not support backtracking, e.g. by removing nested quantifiers.
有效性: High
阶段: System Configuration
描述: Set backtracking limits in the configuration of the regular expression implementation, such as PHP's pcre.backtrack_limit. Also consider limits on execution time for the process.
有效性: Moderate
阶段: Implementation
描述: Do not use regular expressions with untrusted input. If regular expressions must be used, avoid using backtracking in the expression.
有效性: High
阶段: Implementation
描述: Limit the length of the input that the regular expression will process.
有效性: Moderate
观察示例
参考: CVE-2020-5243
server allows ReDOS with crafted User-Agent strings, due to overlapping capture groups that cause excessive backtracking.
参考: CVE-2021-21317
npm package for user-agent parser prone to ReDoS due to overlapping capture groups
参考: CVE-2019-16215
Markdown parser uses inefficient regex when processing a message, allowing users to cause CPU consumption and delay preventing processing of other messages.
参考: CVE-2019-6785
Long string in a version control product allows DoS due to an inefficient regex.
参考: CVE-2019-12041
Javascript code allows ReDoS via a long string due to excessive backtracking.
参考: CVE-2015-8315
ReDoS when parsing time.
参考: CVE-2015-8854
ReDoS when parsing documents.
参考: CVE-2017-16021
ReDoS when validating URL.
引入模式
| 阶段 | 说明 |
|---|---|
| Implementation | A RegEx can be easy to create and read using unbounded matching characters, but the programmer might not consider the risk of excessive backtracking. |