Billion laughs 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.^[1]

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

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. Versions with larger amount of entries also exist.

In the most frequently cited example, the first entity is the string "lol", hence the name "billion laughs". At the time this vulnerability was first reported, the computer memory used by a billion instances of the string "lol" would likely exceed that available to the process parsing the XML.

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.

< ? xml version= "1.0" ? > <!DOCTYPE lolz [ <!ELEMENT lolz ( #PCDATA ) > <!ENTITY lol1 "lollollollollollollollollollol" > <!ENTITY lol2 "&lol1;&lol1;&lol1;&lol1;&lol1;&lol1;&lol1;&lol1;&lol1;" > <!ENTITY lol3 "&lol2;&lol2;&lol2;&lol2;&lol2;&lol2;&lol2;&lol2;&lol2;" > <!ENTITY lol4 "&lol3;&lol3;&lol3;&lol3;&lol3;&lol3;&lol3;&lol3;"> > <!ENTITY lol5 "&lol4;&lol4;&lol4;&lol4;&lol4;&lol4;&lol4;&lol4;&lol4;" > <!ENTITY lol6 "&lol5;&lol5;&lol5;&lol5;&lol5;&lol5;&lol5;&lol5;&lol5;" > <!ENTITY lol7 "&lol6;&lol6;&lol6;&lol6;&lol6;&lol6;&lol6;&lol6;" > <!ENTITY lol8 "&lol7;&lol7;&lol7;&lol7;&lol7;&lol7;&lol7;&lol7;" > <!ENTITY lol9 "&lol8;&lol8;&lol8;&lol8;&lol8;&lol8;&lol8;&lol8;&lol8;&lol8;" > ]> <lolz > &lol9; </لولز >

عندما يقوم محلل XML بتحميل هذا المستند، يلاحظ أنه يتضمن عنصرًا جذريًا واحدًا، "lolz"، يحتوي على النص " & lol9;". مع ذلك، فإن " & lol9;" كيان مُعرَّف يتوسع إلى سلسلة نصية تحتوي على عشر سلاسل نصية " & lol8;". كل سلسلة نصية " & lol8;" هي كيان مُعرَّف يتوسع إلى عشر سلاسل نصية " & lol7;"، وهكذا. بعد معالجة جميع عمليات توسيع الكيانات، ستحتوي هذه الكتلة الصغيرة (أقل من 1 كيلوبايت) من XML فعليًا على 10 ^{^9} = مليار كلمة "lol"، مما يشغل ما يقرب من 3 جيجابايت من الذاكرة. ^{[ 2 ]}

قد يتطلب هجوم المليار ضحكة الموصوف أعلاه مساحة أو وقتًا هائلاً . ويؤدي التباين الناتج عن التضخم التربيعي إلى نمو تربيعي في متطلبات الموارد بمجرد تكرار كيان كبير مرارًا وتكرارًا، لتجنب التدابير المضادة التي تكشف الكيانات المتداخلة بكثافة. ^{[ 5 ]} (انظر نظرية التعقيد الحسابي لمقارنة فئات النمو المختلفة).

يمكن أن يوجد هجوم "مليار ضحكة" لأي تنسيق ملف يمكن أن يحتوي على توسعات ماكرو، على سبيل المثال قنبلة YAML هذه:

أ : &أ [ "lol" , "lol" , "lol" , "lol" , "lol" , "lol" , "lol" , "lol" , "lol" ] ب : &ب [ *أ , *أ , *أ , *أ , *أ , *أ , *أ , *أ , *أ ] ج : &ج [ *ب , *ب , *ب , *ب , *ب , *ب , *ب , *ب , *ب ] د : &د [ *ج , *ج , *ج , *ج , *ج , *ج , *ج , *ج , *ج ] هـ : &هـ [ *د , *د , *د , *د , *د , *د , *د , *د , *د ] و : &ف [ *هـ , *هـ , *هـ , *هـ , *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 ] i : &i [ *h , *h , *h , *h , *h , *h , *h , *h , *h ]

تسبب هذا في تعطل الإصدارات السابقة من لغة Go لأن معالج YAML الخاص بها (على عكس مواصفات YAML) يقوم بتوسيع المراجع كما لو كانت وحدات ماكرو. تم تعديل معالج YAML الخاص بلغة Go بحيث يفشل في التحليل إذا أصبح حجم الكائن الناتج كبيرًا جدًا.

تأثرت برامج المؤسسات، مثل Kubernetes، بهذا الهجوم عبر محلل YAML الخاص بها. ^{[ 6 ] [ 7 ]} ولهذا السبب، يُفضل استخدام محلل ذي قدرات محدودة عمدًا (مثل StrictYAML)، أو غالبًا ما تُفضل تنسيقات الملفات التي لا تسمح بالمراجع للبيانات الواردة من مصادر غير موثوقة. ^{[ 8 ]}

• تعريف نوع المستند – مجموعة من تعريفات الترميز للغة ترميز عائلة SGML (DTD)، وهو قالب للتحقق من صحة ملفات XML 
• قنبلة التفرع – نوع من هجمات حجب الخدمة البرمجية ، وهي طريقة مماثلة لاستنزاف موارد النظام من خلال التكرار. 
• الاستدعاء الذاتي – عملية تكرار العناصر بطريقة متشابهة ذاتيًا 
• هجوم الكيانات الخارجية XML – نوع من الهجمات على أنظمة الحاسوب 
• قنبلة Zip – ملف مضغوط خبيث مصمم لتعطيل البرنامج أو النظام الذي يقرأه ، وهو هجوم مشابه يستخدم ملفات Zip المضغوطة