Home > CAPEC List > CAPEC-492: Regular Expression Exponential Blowup (Version 3.9)

CAPEC-492: Regular Expression Exponential Blowup

Attack Pattern ID: 492
Abstraction: Standard
View customized information:
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.
Extended Description

The algorithm builds a finite state machine and based on the input transitions through all the states until the end of the input is reached. NFA engines may evaluate each character in the input string multiple times during the backtracking. The algorithm tries each path through the NFA one by one until a match is found; the malicious input is crafted so every path is tried which results in a failure. Exploitation of the Regex results in programs hanging or taking a very long time to complete. These attacks may target various layers of the Internet due to regular expressions being used in validation.

Relationships
Section HelpThis table shows the other attack patterns and high level categories that are related to this attack pattern. These relationships are defined as ChildOf and ParentOf, and give insight to similar items that may exist at higher and lower levels of abstraction. In addition, relationships such as CanFollow, PeerOf, and CanAlsoBe are defined to show similar attack patterns that the user may want to explore.
NatureTypeIDName
ChildOfMeta Attack PatternMeta Attack Pattern - A meta level attack pattern in CAPEC is a decidedly abstract characterization of a specific methodology or technique used in an attack. A meta attack pattern is often void of a specific technology or implementation and is meant to provide an understanding of a high level approach. A meta level attack pattern is a generalization of related group of standard level attack patterns. Meta level attack patterns are particularly useful for architecture and design level threat modeling exercises.130Excessive Allocation
Section HelpThis table shows the views that this attack pattern belongs to and top level categories within that view.
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.
Taxonomy Mappings
Section HelpCAPEC mappings to ATT&CK techniques leverage an inheritance model to streamline and minimize direct CAPEC/ATT&CK mappings. Inheritance of a mapping is indicated by text stating that the parent CAPEC has relevant ATT&CK mappings. Note that the ATT&CK Enterprise Framework does not use an inheritance model as part of the mapping to CAPEC.
Relevant to the ATT&CK taxonomy mapping (see parent)
Relevant to the OWASP taxonomy mapping
Entry Name
Regular expression Denial of Service - ReDoS
References
[REF-421] Bryan Sullivan. "Regular Expression Denial of Service Attacks and Defenses". <http://msdn.microsoft.com/en-au/magazine/ff646973.aspx>.
Content History
Submissions
Submission DateSubmitterOrganization
2014年06月23日
(Version 2.6)
CAPEC Content TeamThe MITRE Corporation
Modifications
Modification DateModifierOrganization
2019年04月04日
(Version 3.1)
CAPEC Content TeamThe MITRE Corporation
Updated Related_Weaknesses
2019年09月30日
(Version 3.2)
CAPEC Content TeamThe MITRE Corporation
Updated Related_Attack_Patterns
2020年12月17日
(Version 3.4)
CAPEC Content TeamThe MITRE Corporation
Updated Taxonomy_Mappings
2021年06月24日
(Version 3.5)
CAPEC Content TeamThe MITRE Corporation
Updated Related_Weaknesses
2022年02月22日
(Version 3.7)
CAPEC Content TeamThe MITRE Corporation
Updated Description, Extended_Description
More information is available — Please select a different filter.
Page Last Updated or Reviewed: July 31, 2018

Use of the Common Attack Pattern Enumeration and Classification (CAPEC), and the associated references from this website are subject to the Terms of Use. Copyright © 2007–2025, The MITRE Corporation. CAPEC and the CAPEC logo are trademarks of The MITRE Corporation.

AltStyle によって変換されたページ (->オリジナル) /