“Billion laughs attack”的意思、由来-开放百科全书

In computer security, a billion laughs attack is a type of denial-of-service (DoS) attack which is aimed at parsers of XML documents.^[1]

It is also referred to as an XML bomb or as an exponential entity expansion attack.^[2]

Details

The example attack consists of defining 10 entities, each defined as consisting of 10 of the previous entity, with the document consisting of a single instance of the largest entity, which expands to one billion copies of the first entity.

In the most frequently cited example, the first entity is the string "lol", hence the name "billion laughs". The amount of computer memory used would likely exceed that available to the process parsing the XML (it certainly would have at the time the vulnerability was first reported).

While the original form of the attack was aimed specifically at XML parsers, the term may be applicable to similar subjects as well.^[1]

The problem was first reported as early as 2002,^[3] but began to be widely addressed in 2008.^[4]

Defenses against this kind of attack include capping the memory allocated in an individual parser if loss of the document is acceptable, or treating entities symbolically and expanding them lazily only when (and to the extent) their content is to be used.

Code example

When an XML parser loads this document, it sees that it includes one root element, "lolz", that contains the text "&lol9;". However, "&lol9;" is a defined entity that expands to a string containing ten "&lol8;" strings. Each "&lol8;" string is a defined entity that expands to ten "&lol7;" strings, and so on. After all the entity expansions have been processed, this small (< 1 KB) block of XML will actually contain 10⁹ = a billion "lol"s, taking up almost 3 gigabytes of memory.^[5]

Variations

The billion laughs attack described above takes an exponential amount of space. The quadratic blowup variation causes quadratic growth in storage requirements by simply repeating a large entity over and over again, to avoid countermeasures that detect heavily nested entities.^[6] (See computational complexity theory for comparisons of different growth classes.)

A "Billion laughs" attack should exist for any file format that can contain references, for example this YAML bomb:

For this reason, file formats that do not allow references are often preferred for data arriving from untrusted sources.^[7]{{not in source|date=November 2018}}

See also

References

1. ^¹{{cite web |url=http://www.ibm.com/developerworks/xml/library/x-tipcfsx.html |title=Tip: Configure SAX parsers for secure processing |first=Elliotte Rusty |last=Harold |authorlink=Elliotte Rusty Harold |date=27 May 2005 |work=IBM developerWorks |archiveurl=https://www.webcitation.org/5wwJidGdh?url=http://www.ibm.com/developerworks/xml/library/x-tipcfsx.html |archivedate=4 March 2011 |accessdate=4 March 2011 |deadurl=yes |df= }}
2. ^{{cite journal | url = http://msdn.microsoft.com/en-us/magazine/ee335713.aspx | title = XML Denial of Service Attacks and Defenses | first = Bryan | last = Sullivan | journal = MSDN Magazine |date=November 2009 | publisher = Microsoft Corporation | accessdate = 2011-05-31}}
3. ^{{cite web | url = http://www.securityfocus.com/archive/1/303509 | title = SecurityFocus | date = 2002-12-16 | accessdate = 2015-07-03}}
4. ^{{cite web | url = http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2003-1564 | title = CVE-2003-1564 | work = Common Vulnerabilities and Exposures | publisher = The MITRE Corporation | date = 2003-02-02 | accessdate = 2011-06-01}}
5. ^{{cite web|url=http://msdn.microsoft.com/en-us/magazine/ee335713.aspx|author=Bryan Sullivan|accessdate=2011-12-21|title=XML Denial of Service Attacks and Defenses}}
6. ^https://docs.python.org/2/library/xml.html#xml-vulnerabilities
7. ^http://www.cio.com/article/3082084/web-development/xml-is-toast-long-live-json.html