GHSA-8344-3jmq-59r6 xmldom: Quadratic-time attribute deduplication

• npm @xmldom/xmldom: >= 0.7.0, < 0.8.15 → fixed in 0.8.15 • npm @xmldom/xmldom: >= 0.9.0, < 0.9.12 → fixed in 0.9.12 • npm xmldom: <= 0.6.0 (no fix yet)

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 '; // } for (var _i = 0, sizes = [2000, 4000, 8000, 16000, 32000]; _i ' + 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.