CWE-1333
Inefficient Regular Expression Complexity
The product uses a regular expression with a worst-case computational complexity that is inefficient and possibly exponential.
Mitigation
Phase: Architecture and Design
Description:
- Use regular expressions that do not support backtracking, e.g. by removing nested quantifiers.
Mitigation
Phase: System Configuration
Description:
- 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.
Mitigation
Phase: Implementation
Description:
- Do not use regular expressions with untrusted input. If regular expressions must be used, avoid using backtracking in the expression.
Mitigation
Phase: Implementation
Description:
- Limit the length of the input that the regular expression will process.
CAPEC-492: Regular Expression Exponential Blowup
An adversary may execute an attack on a program that uses a poor Regular Expression(Regex) implementation by choosing input that results in an extreme situation for the Regex. A typical extreme situation operates at exponential time compared to the input size. This is due to most implementations using a Nondeterministic Finite Automaton(NFA) state machine to be built by the Regex algorithm since NFA allows backtracking and thus more complex regular expressions.