DOS via a billion laughs 😈 - Consume arbitrarily much RAM by repeated referencing

Image by the author

The billion laughs attack has been known since 2003 (source). The attack uses the references in XML files to make a small source file be huge in memory if all references are expanded. It’s also known as a LOL bomb, XML bomb, or in a variation as a YAML bomb and git bomb. It is a type of denial of service (DOS) attack as it can bring a service down.

Why you should care

This is a bit too specific to be visible in many news articles. However, there are several big projects which were vulnerable over the years:

2003: libxml2 was vulnerable (CVE-2003-1564)
2015: MediaWiki was vulnerable (CVE-2015-2942)
2016: libxml2 was vulnerable … again (CVE-2016-3705)
2016: HTTP/2 header compression was used to build an HPACK bomb (CVE-2016-6581)
2019: Kubernetes was vulnerable (source, CVE-2019-11253)
2019: c3p0 (a JDBC connection pool) was vulnerable (CVE-2019-5427)

How it works

The following XML defines an entity laugh, then an entity ha2 which contains laugh twice. This pattern is repeated. This means ha5 contains laugh indirectly 16 times. You can see the exponential growth, can’t you?

<?xml version="1.0"?>

<!DOCTYPE root [
<!ENTITY laugh "😆">
<!ENTITY ha2 "&laugh; &laugh;">
<!ENTITY ha3 "&ha2; &ha2;">
<!ENTITY ha4 "&ha3; &ha3;">
<!ENTITY ha5 "&ha4; &ha4;">
]>

<root>&ha5;</root>

With ha31, we would have 2³⁰ times 😆. That is about a billion laughs. Please note how asymmetric this is: With a document that is less than 1 kB in size, the attacker can make the parser consume gigabytes of memory. This can easily consume all memory of a machine and thus render it unusable until the parser is killed or the machine is restarted.

A slight variation of the billion laughs attack is called quadratic blowup.

Please notice that similar attacks are possible in other file formats such as YAML. The key point here is that those formats have references.

How can I defend against a billion laughs?

Assuming that you cannot control the input directly and prevent malicious XML documents from reaching you at all, I can think of 4 measures:

Lazy evaluation of references: Instead of evaluating the whole document at once, the references are only resolved when necessary. It might solve some issues.
No evaluation of references: Throwing the dangerous feature out of the window for sure means that you’re not vulnerable to the attack anymore. You need to make sure it doesn’t affect your users, though. Communicating this might be hard.
Reference recursion depth limit: The parser itself could be aware of this issue and have a threshold when it stops evaluating references. However, this might also lead to false positives — documents that don't get parsed because the parser thinks it’s an attack.
RAM restriction: You can run the code that might execute the billion laughs attack under resource restrictions. This means the execution thread/process receives a (catchable) exception and can continue execution normally. It might especially mean that even if the exception is not thrown, the rest of your system might be fine. Only that thread/process might be killed.

So, how do you do this with Python?

The resource restriction is easiest:

import resource
import contextlib


@contextlib.contextmanager
def limit(resource_type, limit):
    """Temporarily limit a resource."""
    soft_limit, hard_limit = resource.getrlimit(resource_type)
    resource.setrlimit(resource_type, (limit, hard_limit))  # set soft limit
    try:
        yield
    finally:
        resource.setrlimit(resource_type, (soft_limit, hard_limit))  # restore


def dangerous_call():
    [i ** 2 for i in range(10 ** 5)]


try:
    with limit(resource.RLIMIT_AS, 2 ** 24):
        dangerous_call()
except MemoryError:
    print("Your call consumed too much memory!")

Restricting the parser is sometimes possible, sometimes not. It depends on your parser. Some have parameters like resolve_entities (lxml).

Limiting the maximum decompression size was done against the HTTP/2 “HPACK” bomb (source).

DOS via a billion laughs 😈 Consume arbitrarily much RAM by repeated referencing

Why you should care

How it works

How can I defend against a billion laughs?

See also

More in this series