billion laughs attack
≈ 3 min read
Names in other languages
- eoatako de miliardoj da ridoj
- Englishbillion laughs attack
- Españolmil millones de risas
- FrançaisXML entity expansion
- УкраїнськаКвадратичний вибух
- DeutschEntitätsexpansion
- 日本語billion laughs攻撃
- 中文十亿笑声
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In computer security, a billion laughs attack is a type of denial-of-service attack (DoS attack) which is aimed at parsers of XML documents. It is also referred to as an XML bomb or as an exponential entity expansion attack.
In computer security, a billion laughs attack is a type of denial-of-service attack (DoS attack) which is aimed at parsers of XML documents. It is also referred to as an XML bomb or as an exponential entity expansion attack. ]> &lol9; 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 ( 9 = a billion "lol"s, taking up almost 3 gigabytes of memory.
Variations
The billion laughs attack described above can take an exponential amount of space or time. The quadratic blowup variation causes quadratic growth in resource requirements by simply repeating a large entity over and over again, to avoid countermeasures that detect heavily nested entities. (See computational complexity theory for comparisons of different growth classes.)
A "billion laughs" attack could exist for any file format that can contain macro expansions, for example this YAML bomb: 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] This crashed earlier versions of Go because the Go YAML processor (contrary to the YAML spec) expands references as if they were macros. The Go YAML processor was modified to fail parsing if the result object becomes too large.
Enterprise software like Kubernetes has been affected by this attack through its YAML parser. For this reason, either a parser with intentionally limited capabilities is preferred (like StrictYAML) or file formats that do not allow references are often preferred for data arriving from untrusted sources.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1373508825 under CC BY-SA 4.0; modifications have been made.