| Package | Affected versions | Patched versions |
|---|---|---|
| @xmldom/xmldom | ≥ 0.7.0, < 0.8.15≥ 0.9.0, < 0.9.12 | 0.8.150.9.12 |
| xmldom | ≤ 0.6.0 |
xmldom builds the attribute collection of every parsed element by inserting attributes one at a
time into a DOM NamedNodeMap. Each insertion first performs a linear scan of all
already-inserted attributes to enforce the DOM uniqueness rule (no two attributes with the same
qualified name / namespace+local-name). Parsing an element that carries M distinct attributes
therefore costs 1 + 2 + … + M = O(M²) comparisons.
Because the trigger is simply "one element with many attributes", the attack payload is a
fully well-formed XML document. No malformed markup, no error recovery, and no non-default
parser options are involved — parsing completes silently with zero warning/error/fatalError
events. An attacker who can submit a modest, highly compressible document (a single element with
tens of thousands of attributes, ~340 KB uncompressed) can consume seconds of single-threaded CPU
per request, enabling an unauthenticated denial of service.
This is distinct from the known quadratic-memory namespace-map issue: it burns CPU and it does not require any namespace declarations or nesting.
The DOM content handler adds each attribute of a starting element by calling
el.setAttributeNode(attr) in a loop:
// DOMHandler.startElement
for (var i = 0; i < len; i++) {
var namespaceURI = attrs.getURI(i);
var value = attrs.getValue(i);
var qName = attrs.getQName(i);
var attr = doc.createAttributeNS(namespaceURI, qName);
attr.value = attr.nodeValue = value;
el.setAttributeNode(attr); // O(existing attrs) each — see below
}
setAttributeNode delegates to NamedNodeMap.setNamedItem, which calls getNamedItemNS to look
for an existing attribute with the same namespace URI and local name before appending:
setNamedItem: function (attr) {
var el = attr.ownerElement;
if (el && el !== this._ownerElement) {
throw new DOMException(DOMException.INUSE_ATTRIBUTE_ERR);
}
var oldAttr = this.getNamedItemNS(attr.namespaceURI, attr.localName); // linear scan
if (oldAttr === attr) {
return attr;
}
_addNamedNode(this._ownerElement, this, attr, oldAttr);
return oldAttr;
},
https://github.com/xmldom/xmldom/blob/bb7a085dc5ba1eea3212388509b97bb4b4af32b9/lib/dom.js#L612-L623
Running one of these products? Scan your site to see whether it exposes a vulnerable version.
Scan my site freegetNamedItemNS walks the whole list on every call:
getNamedItemNS: function (namespaceURI, localName) {
if (!namespaceURI) {
namespaceURI = null;
}
var i = 0;
while (i < this.length) {
var node = this[i];
if (node.localName === localName && node.namespaceURI === namespaceURI) {
return node;
}
i++;
}
return null;
},
For the i-th attribute the scan visits i-1 entries, so inserting M distinct attributes performs
Θ(M²) comparisons. There is no hash index or set keyed by name; the map is a plain
array-backed structure.
The same structure exists on 0.8.x. There setNamedItem dedups via
getNamedItem(attr.nodeName) instead of getNamedItemNS, but that method is likewise a full linear
scan, so the complexity is identical:
startElement loop / setAttributeNode:
https://github.com/xmldom/xmldom/blob/e5c14802592685bb872c042c54c3f73758875c85/lib/dom-parser.js#L159-L176setNamedItem → linear getNamedItem:
https://github.com/xmldom/xmldom/blob/e5c14802592685bb872c042c54c3f73758875c85/lib/dom.js#L286-L308The linear-scan NamedNodeMap predates the @xmldom/xmldom fork and is present unchanged in the
unscoped xmldom package back to its earliest published release. In [email protected], parsing already
inserts each attribute one at a time (DOMHandler.startElement loops calling
setAttributeNS → setAttributeNode → NamedNodeMap.setNamedItem), and setNamedItem dedups by
calling getNamedItemNS, which is a full linear while (i--) scan of the already-inserted
attributes — the identical O(M²) structure. The whole unscoped line (0.1.0 … 0.6.0) is
therefore affected; the earliest published tag (0.1.0) was verified to contain the per-insert
linear dedup scan.
A single well-formed element with M distinct attributes. No malformed markup and no options:
'use strict';
var DOMParser = require('@xmldom/xmldom').DOMParser;
function buildDoc(m) {
var parts = new Array(m);
for (var i = 0; i < m; i++) parts[i] = 'a' + i + '="x"';
return '<r ' + parts.join(' ') + '/>'; // <r a0="x" a1="x" ... a{M-1}="x"/>
}
for (var _i = 0, sizes = [2000, 4000, 8000, 16000, 32000]; _i < sizes.length; _i++) {
var m = sizes[_i];
var xml = buildDoc(m);
var t0 = process.hrtime.bigint();
var doc = new DOMParser().parseFromString(xml, 'text/xml'); // silent: no error events
var ms = Number(process.hrtime.bigint() - t0) / 1e6;
console.log(m + ' attrs, ' + xml.length + ' bytes -> ' + ms.toFixed(1) + ' ms; parsed=' +
doc.documentElement.attributes.length);
}
Measured with Node.js v18.20.8 (wall-clock; absolute numbers vary by host, the scaling is the load-bearing fact):
@xmldom/xmldom 0.9.10:
| M (attributes) | input bytes | time (ms) | ratio vs prev |
|---|---|---|---|
| 2000 | 18,894 | 13.4 | — |
| 4000 | 38,894 | 38.7 | ×2.9 |
| 8000 | 78,894 | 100.8 | ×2.6 |
| 16000 | 164,894 | 406.2 | ×4.0 |
| 32000 | 340,894 | 2149.5 | ×5.3 |
@xmldom/xmldom 0.8.13:
| M (attributes) | input bytes | time (ms) |
|---|---|---|
| 2000 | 18,894 | 10.6 |
| 4000 | 38,894 | 19.9 |
| 8000 | 78,894 | 75.9 |
| 16000 | 164,894 | 657.7 |
| 32000 | 340,894 | 1643.2 |
xmldom (unscoped) 0.6.0: 4000 → 28.2 ms, 8000 → 131.8 ms, 16000 → 545.2 ms (≈ ×4 per doubling).
Time grows ≈ ×4 per doubling of M — quadratic. About 340 KB of well-formed input costs ~1.6–2.1 s
of single-threaded CPU, and it keeps scaling: doubling the attribute count quadruples the cost.
The document is trivially generated and compresses to a few kilobytes on the wire.
Unauthenticated, remotely triggerable denial of service against any service that parses attacker-influenced XML/HTML with xmldom. A single request holds one event-loop thread for seconds; a handful of concurrent requests can saturate CPU and stall the process. Because the payload is a plain well-formed document (one element, many attributes), it passes any "must be well-formed" gate and reaches the parser before any application-level validation (e.g. schema checks or signature verification) can run. The payload is highly compressible, so it is effective over compressed transports.
Replaced the per-insert linear duplicate scan on the parse-time dedup path with a name-keyed
index, so de-duplicating an element's attributes during parse is O(M) instead of O(M²) — a
well-formed-but-hostile attribute list can no longer wedge the parse. Behavior-preserving: attribute
order and duplicate resolution (last value wins, first position kept) are byte-identical. Non-breaking
and independent of requireWellFormed; ships on both maintained versions.