Billion Laughs and Entity Expansion

Entities can reference other entities, and if each one multiplies the last, a tiny document can expand to gigabytes and exhaust memory. The billion laughs attack weaponizes this into a denial of service. The defense is to cap expansion or refuse the DOCTYPE outright.

Not every XML attack tries to read your files. Some just try to knock the parser over, and the classic way to do it is entity expansion, best known as the billion laughs attack.

The multiplication trick

Internal entities can reference other internal entities. That sounds harmless until you chain them so each layer multiplies the one below:

<!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;">
]>
<lolz>&lol3;</lolz>

Each entity expands to ten of the previous one. With a handful of levels, a document a few hundred bytes long expands to billions of characters, which is where the name comes from. A parser that dutifully resolves every reference tries to build that entire string in memory, and the process runs out of memory or CPU and falls over. It is a denial of service: the payload is tiny, the effect is enormous, and no file is read or network touched.

Why it works

The attack exploits the same entity mechanism behind (XML External Entity), but a different property of it. XXE abuses external entities to reach out and fetch things. Billion laughs abuses internal entities and the fact that expansion is recursive and multiplicative, so cost grows exponentially with depth while the source text grows only linearly. Everything needed is inside the document, which is why disabling external entities alone does not stop it.

The defense

Two defenses apply, and the stronger one is familiar. Parsers can impose expansion limits, capping the total number of entity expansions or the resulting size and aborting when the cap is hit, which many modern parsers now do by default. But the cleaner answer is the same as for XXE: refuse to process the DOCTYPE at all. Entities can only be declared in a DOCTYPE, so a parser that rejects DOCTYPE declarations for untrusted input cannot be handed an expansion bomb in the first place. This is why a safe XML inspector flags any document that declares entities referencing other entities as an expansion risk, and reports it without ever performing the expansion. The signal to watch for is entities defined in terms of other entities, chained more than a level deep.

A denial of service that arrives as a valid document

Nothing about the attack is malformed. The document is well-formed XML, the entities are legal, and the parser is doing precisely what the specification describes. The failure is in arithmetic, not in validation — ten nested entities each referencing the previous ten times is a billion expansions from a few hundred bytes.

This is why input-size limits feel like protection and are not. The dangerous property is the ratio, not the size, and a payload small enough to pass any reasonable byte limit can exhaust memory on expansion.

The defences that work are structural: disable entity expansion, or cap the expansion count and total expanded size at the parser. Both are settings on the object that does the work, which is the same place XXE is fixed — and for the same reason.