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: - The number of possible backtracking attempts are exponential relative to the length of the input. - The input can fail to match the regular expression. - The input can be long enough. Attackers can create crafted inputs that intentionally cause the regular expression to use excessive backtracking in a way that causes the CPU consumption to spike.
Use regular expressions that do not support backtracking, e.g. by removing nested quantifiers.
Effectiveness: High
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.
Effectiveness: Moderate
Do not use regular expressions with untrusted input. If regular expressions must be used, avoid using backtracking in the expression.
Effectiveness: High
Limit the length of the input that the regular expression will process.
Effectiveness: Moderate
Automated static analysis, commonly referred to as Static Application Security Testing (SAST), can find some instances of this weakness by analyzing source code (or binary/compiled code) without having to execute it. Typically, this is done by building a model of data flow and control flow, then searching for potentially-vulnerable patterns that connect "sources" (origins of input) with "sinks" (destinations where the data interacts with external components, a lower layer such as the OS, etc.)
Effectiveness: High