English
Français
Light
Dark
System

Alert System

Stay informed at all times
Create an account Open a free account Login Manage your alerts

CAPEC-492

Regular Expression Exponential Blowup
Draft
2014-06-23 00:00 +00:00
2022-02-22 00:00 +00:00
CAPEC Mitre.org

Alerte pour un CAPEC

Stay informed of any changes for a specific CAPEC.
Alert management

Description

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.

Informations

Prerequisites

This type of an attack requires the ability to identify hosts running a poorly implemented Regex, and the ability to send crafted input to exploit the regular expression.

Mitigations

Test custom written Regex with fuzzing to determine if the Regex is a poor one. Add timeouts to processes that handle the Regex logic. If an evil Regex is found rewrite it as a good Regex.

Related Weaknesses

CWE-ID Weakness Name
CWE-400 Uncontrolled Resource Consumption
The product does not properly control the allocation and maintenance of a limited resource, thereby enabling an actor to influence the amount of resources consumed, eventually leading to the exhaustion of available resources.
CWE-1333 Inefficient Regular Expression Complexity
The product uses a regular expression with an inefficient, possibly exponential worst-case computational complexity that consumes excessive CPU cycles.

References

REF-421

Regular Expression Denial of Service Attacks and Defenses
Bryan Sullivan.
http://msdn.microsoft.com/en-au/magazine/ff646973.aspx

Submission

Name Organization Date Date Release
CAPEC Content Team The MITRE Corporation 2014-06-23 +00:00

Modifications

Name Organization Date Comment
CAPEC Content Team The MITRE Corporation 2019-04-04 +00:00 Updated Related_Weaknesses
CAPEC Content Team The MITRE Corporation 2019-09-30 +00:00 Updated Related_Attack_Patterns
CAPEC Content Team The MITRE Corporation 2020-12-17 +00:00 Updated Taxonomy_Mappings
CAPEC Content Team The MITRE Corporation 2021-06-24 +00:00 Updated Related_Weaknesses
CAPEC Content Team The MITRE Corporation 2022-02-22 +00:00 Updated Description, Extended_Description

More information
Click on the button to the left (OFF), to authorize the inscription of cookie improving the functionalities of the site. Click on the button to the left (Accept all), to unauthorize the inscription of cookie improving the functionalities of the site.