CAPEC - CAPEC-197: Exponential Data Expansion (Version 3.9)


Common Attack Pattern Enumeration and Classification A Community Resource for Identifying and Understanding Attacks

Home > CAPEC List > CAPEC-197: Exponential Data Expansion (Version 3.9)

CAPEC-197: Exponential Data Expansion

Attack Pattern ID: 197

Abstraction: Detailed

View customized information:

Description

An adversary submits data to a target application which contains nested exponential data expansion to produce excessively large output. Many data format languages allow the definition of macro-like structures that can be used to simplify the creation of complex structures. However, this capability can be abused to create excessive demands on a processor's CPU and memory. A small number of nested expansions can result in an exponential growth in demands on memory.

Alternate Terms

Term: Billion Laughs Attack

Term: XML Bomb

Term: XML Entity Expansion (XEE)

Likelihood Of Attack

High

Typical Severity

Medium

Relationships

This 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.

Nature	Type	ID	Name
ChildOf	Standard Attack Pattern - A standard level attack pattern in CAPEC is focused on a specific methodology or technique used in an attack. It is often seen as a singular piece of a fully executed attack. A standard attack pattern is meant to provide sufficient details to understand the specific technique and how it attempts to accomplish a desired goal. A standard level attack pattern is a specific type of a more abstract meta level attack pattern.	230	Serialized Data with Nested Payloads
CanFollow	Detailed Attack Pattern - A detailed level attack pattern in CAPEC provides a low level of detail, typically leveraging a specific technique and targeting a specific technology, and expresses a complete execution flow. Detailed attack patterns are more specific than meta attack patterns and standard attack patterns and often require a specific protection mechanism to mitigate actual attacks. A detailed level attack pattern often will leverage a number of different standard level attack patterns chained together to accomplish a goal.	228	DTD Injection

This table shows the views that this attack pattern belongs to and top level categories within that view.

View Name	Top Level Categories
Domains of Attack	Software
Mechanisms of Attack	Abuse Existing Functionality

Execution Flow

Explore

Survey the target: An adversary determines the input data stream that is being processed by a data parser that supports using subsitituion on the victim's side.
Techniques
Use an automated tool to record all instances of URLs to process requests.
Use a browser to manually explore the website and analyze how the application processes requests.

Experiment

Craft malicious payload: The adversary crafts a malicious message containing nested exponential expansion that completely uses up available server resources. See the "Example Instances" section for details on how to craft this malicious payload.

Exploit

Send the message: Send the malicious crafted message to the target URL.

Prerequisites

This type of attack requires that the target must receive input but either fail to provide an upper limit for entity expansion or provide a limit that is so large that it does not preclude significant resource consumption.

Skills Required

[Level: Low]

Ability to craft nested data expansion messages.

Resources Required

None: No specialized resources are required to execute this type of attack.

Consequences

This table specifies different individual consequences associated with the attack pattern. The Scope identifies the security property that is violated, while the Impact describes the negative technical impact that arises if an adversary succeeds in their attack. The Likelihood provides information about how likely the specific consequence is expected to be seen relative to the other consequences in the list. For example, there may be high likelihood that a pattern will be used to achieve a certain impact, but a low likelihood that it will be exploited to achieve a different impact.

Scope	Impact	Likelihood
Availability	Unreliable Execution Resource Consumption

Mitigations

Design: Use libraries and templates that minimize unfiltered input. Use methods that limit entity expansion and throw exceptions on attempted entity expansion.

Implementation: For XML based data - disable altogether the use of inline DTD schemas when parsing XML objects. If a DTD must be used, normalize, filter and use an allowlist and parse with methods and routines that will detect entity expansion from untrusted sources.

Example Instances

The most common example of this type of attack is the "many laughs" attack (sometimes called the 'billion laughs' attack). For example:

<?xml version="1.0"?>
<!DOCTYPE lolz [

<!ENTITY lol "lol">
<!ENTITY lol2 "&lol;&lol;&lol;&lol;&lol;&lol;&lol;&lol;&lol;&lol;">
<!ENTITY lol3 "&lol2;&lol2;&lol2;&lol2;&lol2;&lol2;&lol2;&lol2;&lol2;&lol2;">
<!ENTITY lol4 "&lol3;&lol3;&lol3;&lol3;&lol3;&lol3;&lol3;&lol3;&lol3;&lol3;">
<!ENTITY lol5 "&lol4;&lol4;&lol4;&lol4;&lol4;&lol4;&lol4;&lol4;&lol4;&lol4;">
<!ENTITY lol6 "&lol5;&lol5;&lol5;&lol5;&lol5;&lol5;&lol5;&lol5;&lol5;&lol5;">
<!ENTITY lol7 "&lol6;&lol6;&lol6;&lol6;&lol6;&lol6;&lol6;&lol6;&lol6;&lol6">
<!ENTITY lol8 "&lol7;&lol7;&lol7;&lol7;&lol7;&lol7;&lol7;&lol7;&lol7;&lol7;">
<!ENTITY lol9 "&lol8;&lol8;&lol8;&lol8;&lol8;&lol8;&lol8;&lol8;&lol8;&lol8;">

]>
<lolz>&lol9;</lolz>

This is well formed and valid XML according to the DTD. Each entity increases the number entities by a factor of 10. The line of XML containing lol9; expands out exponentially to a message with 10^9 entities. A small message of a few KBs in size can easily be expanded into a few GB of memory in the parser. By including 3 more entities similar to the lol9 entity in the above code to the DTD, the program could expand out over a TB as there will now be 10^12 entities. Depending on the robustness of the target machine, this can lead to resource depletion, application crash, or even the execution of arbitrary code through a buffer overflow.

This example is similar, but uses YAML. This was used to attack Kubernetes [REF-686]

a: &a ["lol","lol","lol","lol","lol","lol","lol","lol","lol"]
b: &b [*a,*a,*a,*a,*a,*a,*a,*a,*a]
c: &c [*b,*b,*b,*b,*b,*b,*b,*b,*b]
d: &d [*c,*c,*c,*c,*c,*c,*c,*c,*c]
e: &e [*d,*d,*d,*d,*d,*d,*d,*d,*d]
f: &f [*e,*e,*e,*e,*e,*e,*e,*e,*e]
g: &g [*f,*f,*f,*f,*f,*f,*f,*f,*f]
h: &h [*g,*g,*g,*g,*g,*g,*g,*g,*g]
i: &i [*h,*h,*h,*h,*h,*h,*h,*h,*h]

Related Weaknesses

A Related Weakness relationship associates a weakness with this attack pattern. Each association implies a weakness that must exist for a given attack to be successful. If multiple weaknesses are associated with the attack pattern, then any of the weaknesses (but not necessarily all) may be present for the attack to be successful. Each related weakness is identified by a CWE identifier.

CWE-ID	Weakness Name
770	Allocation of Resources Without Limits or Throttling
776	Improper Restriction of Recursive Entity References in DTDs ('XML Entity Expansion')

Taxonomy Mappings

Relevant to the WASC taxonomy mapping

Entry ID	Entry Name
44	XML Entity Expansion

References

[REF-64] Amit Klein. "Multiple vendors XML parser (and SOAP/WebServices server) Denial of Service attack using DTD". <http://www.securityfocus.com/archive/1/303509>.

[REF-65] Pete Lindstrom. "Attacking & Defending Web Services". SPiRE Security. 2002. <http://www.webtorials.com/main/comnet/cn2003/web-service/24.pdf>.

[REF-66] Elliotte Rusty Harold. "Tip: Configure SAX parsers for secure processing". IBM developerWorks. IBM. 2005-05-27. <http://www.ibm.com/developerworks/xml/library/x-tipcfsx.html>.

[REF-67] Bryan Sullivan. "XML Denial of Service Attacks and Defenses". <http://msdn.microsoft.com/en-us/magazine/ee335713.aspx>.

Content History

Submissions
Submission Date	Submitter	Organization
2014-06-23 (Version 2.6)	CAPEC Content Team	The MITRE Corporation
2014-06-23 (Version 2.6)
Modifications
Modification Date	Modifier	Organization
2017-08-04 (Version 2.11)	CAPEC Content Team	The MITRE Corporation
2017-08-04 (Version 2.11)	Updated Resources_Required
2018-07-31 (Version 2.12)	CAPEC Content Team	The MITRE Corporation
2018-07-31 (Version 2.12)	Updated References
2020-07-30 (Version 3.3)	CAPEC Content Team	The MITRE Corporation
2020-07-30 (Version 3.3)	Updated Mitigations
2020-12-17 (Version 3.4)	CAPEC Content Team	The MITRE Corporation
2020-12-17 (Version 3.4)	Updated Related_Attack_Patterns, Taxonomy_Mappings
2021-10-21 (Version 3.6)	CAPEC Content Team	The MITRE Corporation
2021-10-21 (Version 3.6)	Updated @Name, Alternate_Terms, Description, Example_Instances, Execution_Flow, Mitigations, Prerequisites, Related_Weaknesses, Skills_Required
2022-02-22 (Version 3.7)	CAPEC Content Team	The MITRE Corporation
2022-02-22 (Version 3.7)	Updated Execution_Flow
2022-09-29 (Version 3.8)	CAPEC Content Team	The MITRE Corporation
2022-09-29 (Version 3.8)	Updated Example_Instances
Previous Entry Names
Change Date	Previous Entry Name
2021-10-21 (Version 3.6)	XML Entity Expansion

More information is available — Please select a different filter.

Page Last Updated or Reviewed: October 21, 2021


	Site Map \| Terms of Use \| Manage Cookies \| Cookie Notice \| Privacy Policy \| Contact Us \| 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–2024, The MITRE Corporation. CAPEC and the CAPEC logo are trademarks of The MITRE Corporation.

Common Attack Pattern Enumeration and Classification

CAPEC-197: Exponential Data Expansion