XML Quadratic Blowup vs Billion Laughs Attack

XML entity expansion attacks are Denial of Service (DoS) vulnerabilities that exploit standard XML parsers by forcing them to consume excessive CPU and memory resources. While both the Billion Laughs attack and the Quadratic Blowup attack misuse Document Type Definition (DTD) entities to exhaust system memory, they differ significantly in their structural design, growth rates, and ability to bypass basic parser defenses.

The Billion Laughs Attack: Exponential Growth

The Billion Laughs attack, also known as an XML entity expansion or XML bomb, relies on deeply nested, recursive entity references. In this attack, an initial entity containing a small string is defined, and subsequent entities reference the previous entity multiple times.

For example, &lol1; contains ten &lol; references, &lol2; contains ten &lol1; references, and this pattern continues through &lol9;. When the parser attempts to resolve the final entity, the expansion grows exponentially:

\[\text{Size} = \text{Base String} \times 10^n\]

Because of this exponential multiplier (\(O(10^n)\)), an XML payload as small as one kilobyte can expand into several gigabytes of data in memory, instantly crashing the parser or freezing the host system.

The Quadratic Blowup Attack: Flat, Repetitive Expansion

The Quadratic Blowup attack was designed specifically to bypass security controls implemented to prevent the Billion Laughs attack. Many XML parsers attempt to mitigate Billion Laughs by enforcing an entity recursion depth limit (e.g., allowing no more than a few levels of nested entities).

Instead of nesting entities deeply, a Quadratic Blowup attack defines a single, extremely large entity (e.g., several thousand or hundred thousand characters) without recursion. The document then references this large entity repeatedly within a single element:

\[\text{Size} = \text{Entity Size} \times \text{Number of References}\]

Because both the payload size and the number of references scale linearly, the resulting memory consumption scales quadratically (\(O(N^2)\)). A document under 1 MB can expand into tens or hundreds of gigabytes of memory while maintaining an entity nesting depth of only one level.

Core Differences

Feature Billion Laughs Attack Quadratic Blowup Attack
Expansion Mechanism Deeply nested, recursive entity definitions Single large entity repeated many times without nesting
Growth Rate Exponential (\(O(k^n)\)) Quadratic (\(O(N^2)\))
Payload Structure Small file with multiple layers of entity declarations Medium-sized file with large entity values and flat repetitions
Bypass Capability Blocked by entity depth/recursion limits Bypasses depth limits because it uses zero or shallow nesting

Mitigation

Relying solely on entity depth limits is insufficient to protect XML parsers against both vulnerabilities. Comprehensive protection requires: