Project: WASC Threat Classification

Threat Type: Attack

Reference ID: WASC-41

XML Attribute Blowup

XML Attribute Blowup is a denial of service attack against XML parsers. The attacker provides a malicious XML document, which vulnerable XML parsers process in a very inefficient manner, leading to excessive CPU load. The essence of the attack is to include many attributes in the same XML node. Vulnerable XML parsers manage the attributes in an inefficient manner (e.g. in a data container for which insertion of a new attribute has O(n) runtime), resulting in a non-linear (in this example, quadratic, i.e. O(n²)) overall runtime, leading to a denial of service condition via CPU exhaustion.

Example:

<?xml version="1.0"?>

<foo

a1=""

a2=""

...

a10000=""

/>

In this example, there are 10,000 attributes in the foo node, thus a vulnerable XML parser would perform around 50,000,000 "basic operations" (the sum of work in all 10,000 insertions, i.e. the sum of the numbers 1-10,000). If each such operation takes 100 nanoseconds to complete, the overall processing time for this XML document would be 5 seconds. The size of the XML document is around 90KB. A more sustainable DoS can be achieved with 100,000 attributes, in which case there will be around 5,000,000,000 "basic operations" (sum of 1-100,000), taking 500 seconds. The size of the XML document in this case will be 1MB. In both cases, it's possible to reduce the size of the XML document by using the full range (uppercase letters, lowercase letters, digits, etc.) of the possible XML attribute name. That is, instead of using attribute names consisting of a leading letter ("a" in the above examples) and digits, an attacker can use attribute name using a combination of lowercase letters, uppercase letters and digits such as "aaa", "aaA" and "az9". By doing so, it's possible to generate 100,000 different attribute names using only 3 characters (instead of attribute name of 6 characters, as in the above example) - this reduces the XML document size from 1MB to about 700KB.

This issue can be solved either by limiting the amount of attributes per XML element (or more coarsely, limiting the total size of the XML document), or by using a more efficient data container, e.g. (assuming C++) the STL map container [4].

References

Amit Klein: IIS 5.x/6.0 WebDAV (XML parser) attribute blowup DoS

[1] http://www.securityfocus.com/archive/1/378179

Amit Klein: Multiple Vendor SOAP server (XML parser) attribute blowup DoS

[2] http://www.securityfocus.com/archive/1/346973

Amit Klein: Xerces-C++ 2.5.0: Attribute blowup denial-of-service

[3] http://www.securityfocus.com/archive/1/377344

Wikipedia entry 'map (C++ container)'

[4] http://en.wikipedia.org/wiki/Map_(C%2B%2B_container

See also 'Denial of Service'

[5] https://projects.webappsec.org/Denial-Of-Service