GHSA-93r5-fhx6-vmg9

## Summary

`xmldom`'s malformed-input **error-recovery path** has two quadratic-time (O(n²)) behaviors that a single crafted input triggers together, so a tiny, highly compressible document (tens of KB) stalls the Node.js event loop for multiple seconds. It is reachable from `DOMParser.parseFromString` under **default options** — i.e. from unauthenticated, network-delivered XML — making this an unauthenticated denial of service. One of the two behaviors, the `normalize()` adjacent-text merge, is **additionally reachable programmatically** — via a plain `normalize()` call on a DOM built with adjacent text nodes, independent of the parser — so its fix must live in `normalize()`, not only in a parser bound.

## Details

### Finding A — `parseElementStartPart` quadratic re-scan

A `<` character is not a delimiter in any tag-parsing state, so `parseElementStartPart` scans forward character-by-character over any embedded `<` until it reaches the next `>` (or end of input), then validates the accumulated slice as a tag name and throws `invalid tagName:` on failure. The main loop catches this, reports an `error`, sets `end = -1`, and recovers by advancing a single character (`appendText(Math.max(tagStart, start) + 1)`). With a long run of `<` and a distant `>`, each of the O(n) recovery retries performs an O(n) scan plus an O(n) anchored regex validation over the growing candidate ⇒ **O(n²)**.

Code (0.9.x, `bb7a085dc5ba1eea3212388509b97bb4b4af32b9`):

- `parseElementStartPart` character scan — https://github.com/xmldom/xmldom/blob/bb7a085dc5ba1eea3212388509b97bb4b4af32b9/lib/sax.js#L263-L461 - tag-name validation (`setTagName` → throws `invalid tagName`) — https://github.com/xmldom/xmldom/blob/bb7a085dc5ba1eea3212388509b97bb4b4af32b9/lib/sax.js#L886-L891 - main-loop `catch` → `error` + `end = -1` — https://github.com/xmldom/xmldom/blob/bb7a085dc5ba1eea3212388509b97bb4b4af32b9/lib/sax.js#L234-L242 - single-character recovery fallback — https://github.com/xmldom/xmldom/blob/bb7a085dc5ba1eea3212388509b97bb4b4af32b9/lib/sax.js#L247

Code (0.8.x, `e5c14802592685bb872c042c54c3f73758875c85`):

- `parseElementStartPart` — https://github.com/xmldom/xmldom/blob/e5c14802592685bb872c042c54c3f73758875c85/lib/sax.js#L227 - `catch` → `error` + `end = -1` — https://github.com/xmldom/xmldom/blob/e5c14802592685bb872c042c54c3f73758875c85/lib/sax.js#L202-L208 - recovery fallback — https://github.com/xmldom/xmldom/blob/e5c14802592685bb872c042c54c3f73758875c85/lib/sax.js#L213 - `setTagName` validation — https://github.com/xmldom/xmldom/blob/e5c14802592685bb872c042c54c3f73758875c85/lib/sax.js#L616-L621

### Finding B — `normalize()` adjacent-text O(K²) merge

`endDocument()` calls `document.normalize()`. For a parent with K adjacent text nodes (produced by the one-character recovery of Finding A), `normalize()` performs K−1 merges. Each merge does a `removeChild` — which re-indexes **all** child nodes of the parent (O(K)) — and an `appendData` — which rebuilds the accumulator string `this.data + text` (O(K)). Total: **O(K²)**.

Well-formed XML cannot produce adjacent text-node siblings *through the parser* (each text run is one node; comments, CDATA, PIs, and elements sit between runs), so the **parse-path** trigger for Finding B is the malformed-input recovery that emits single-character text nodes. The same O(K²) merge is, however, independently reachable via the public `normalize()` API on a programmatically built tree (see "Finding B is additionally reachable programmatically" below).

Code (0.9.x, `bb7a085dc5ba1eea3212388509b97bb4b4af32b9`):

- `endDocument` → `normalize()` — https://github.com/xmldom/xmldom/blob/bb7a085dc5ba1eea3212388509b97bb4b4af32b9/lib/dom-parser.js#L418-L420 - `normalize()` adjacent-text merge — https://github.com/xmldom/xmldom/blob/bb7a085dc5ba1eea3212388509b97bb4b4af32b9/lib/dom.js#L1336-L1356 - `removeChild` re-index-all branch — https://github.com/xmldom/xmldom/blob/bb7a085dc5ba1eea3212388509b97bb4b4af32b9/lib/dom.js#L1788-L1798 - `appendData` string rebuild — https://github.com/xmldom/xmldom/blob/bb7a085dc5ba1eea3212388509b97bb4b4af32b9/lib/dom.js#L2786-L2790

Code (0.8.x, `e5c14802592685bb872c042c54c3f73758875c85`):

- `endDocument` → `normalize()` — https://github.com/xmldom/xmldom/blob/e5c14802592685bb872c042c54c3f73758875c85/lib/dom-parser.js#L213-L214 - `normalize()` merge — https://github.com/xmldom/xmldom/blob/e5c14802592685bb872c042c54c3f73758875c85/lib/dom.js#L529-L549 - `removeChild` re-index-all branch — https://github.com/xmldom/xmldom/blob/e5c14802592685bb872c042c54c3f73758875c85/lib/dom.js#L756-L773 - `appendData` string rebuild — https://github.com/xmldom/xmldom/blob/e5c14802592685bb872c042c54c3f73758875c85/lib/dom.js#L1533

### Finding B is additionally reachable programmatically (no parser involved)

`Node.prototype.normalize()` is public API on every `Document`/`Element`. A tree built entirely through the ordinary DOM API — `new DOMImplementation().createDocument(...)`, then K× `createTextNode` + `appendChild` on one parent — reaches the **same** O(K²) merge when the application calls `normalize()`, with **no** parsing and **no** error-recovery. The parser is only *one* of the two callers of the vulnerable merge:

- the parser's automatic `endDocument()` → `document.normalize()` (the parse-path trigger above), and - any explicit application call to the public `normalize()` on a tree with adjacent text nodes.

`XMLSerializer` does **not** call `normalize()`, so serializing an un-merged tree is O(total text), not O(K²); the O(K²) surface is exactly those two `normalize()` callers. Consequently a parser-side bound alone cannot remediate Finding B — the fix must live in `normalize()`.

## Affected Versions

Both findings are present across the full published `@xmldom/xmldom` history — both currently-maintained versions (`0.8.x` and `0.9.x`) are affected — and across the retired unscoped `xmldom` line. Finding B's `normalize()` merge is additionally reachable **programmatically**: a direct `normalize()` call on a DOM built with adjacent text nodes hits the same O(K²) merge, independent of the parser — so, unlike Finding A, it does not require the malformed-input recovery path.

## Proof of Concept

Default `DOMParser`, no options. The input is trivially compressible (`a<` / `a<>` repeated) and never throws — it is parsed via the recovery path.

```js const { DOMParser } = require('@xmldom/xmldom');

// Silence the expected `error`-level recovery reports (default handler logs // them to console.error without throwing; only fatalError throws). console.error = function () {};

function timeParse(label, xml, mime) { const t0 = process.hrtime.bigint(); new DOMParser().parseFromString(xml, mime); // completes; no exception const ms = Number(process.hrtime.bigint() - t0) / 1e6; console.log(label + ' bytes=' + Buffer.byteLength(xml) + ' time=' + ms.toFixed(1) + ' ms'); }

for (const N of [4000, 8000, 16000, 32000]) { // Finding A: long re-scans, O(n^2) during parse. timeParse('A N=' + N, '<r>' + 'a<'.repeat(N) + '</r>', 'text/xml'); // Finding B: short re-scans (cheap parse) but K adjacent text nodes -> O(K^2) in normalize(). timeParse('B N=' + N, '<r>' + 'a<>'.repeat(N) + '</r>', 'text/html'); // Combined: ONE input hits both A and B under the default parser. timeParse('C N=' + N, '<r>' + 'a<'.repeat(N) + '</r>', 'text/xml'); } ```

Measured on Node v18.20.8 (absolute ms vary by host; the load-bearing fact is that doubling the input ~quadruples the time — canonical O(n²)):

Finding A, isolated (`"<r>" + "a<"×N + "</r>"`, normalize disabled to isolate the re-scan):

| N | input bytes | `@xmldom/xmldom` 0.9.10 | 0.8.13 | |--:|--:|--:|--:| | 2000 | 4007 | 43 ms | 37 ms | | 4000 | 8007 | 129 ms | 106 ms | | 8000 | 16007 | 434 ms | 424 ms | | 16000 | 32007 | 1629 ms | 1611 ms |

Finding B, isolated (`"<r>" + "a<>"×N + "</r>"`, time attributable to `normalize()`):

| K (N) | input bytes | 0.9.10 | 0.8.13 | |--:|--:|--:|--:| | 4000 | 12007 | 120 ms | 165 ms | | 8000 | 24007 | 589 ms | 771 ms | | 16000 | 48007 | 3142 ms | 4448 ms | | 32000 | 96007 | 12127 ms | 12951 ms |

Combined (default parser, both findings; `"<r>" + "a<"×N + "</r>"`):

| N | input bytes | 0.9.10 | 0.8.13 | |--:|--:|--:|--:| | 4000 | 8007 | 341 ms | 397 ms | | 8000 | 16007 | 1894 ms | 1641 ms | | 16000 | 32007 | 4398 ms | 7661 ms |

~32 KB of input → several seconds of single-threaded event-loop stall.

### Finding B via the public `normalize()` API (no parser)

```js const { DOMImplementation } = require('@xmldom/xmldom');

function timeNormalize(K) { const doc = new DOMImplementation().createDocument(null, 'r', null); const el = doc.documentElement; for (let i = 0; i < K; i++) el.appendChild(doc.createTextNode('x')); // K adjacent text nodes const t0 = process.hrtime.bigint(); doc.normalize(); // O(K^2) merge — no parsing involved const ms = Number(process.hrtime.bigint() - t0) / 1e6; console.log('K=' + K + ' time=' + ms.toFixed(1) + ' ms'); } for (const K of [2000, 4000, 8000, 16000, 32000]) timeNormalize(K); ```

Measured on Node v18.20.8 (doubling K ~quadruples the time — O(K²)):

| K | 0.9.10 | 0.8.13 | |--:|--:|--:| | 2000 | 5.7 ms | 5.6 ms | | 32000 | 1263 ms | 1704 ms |

This path is reachable by any application that builds a DOM from attacker-influenced data and calls `normalize()`, entirely independent of `DOMParser`.

## Impact

Availability only: a single parse of a small crafted document blocks the Node.js event loop for the duration of the quadratic work (multiple seconds at tens of KB; larger inputs scale as O(n²)). No memory blow-up beyond transient strings, no data exposure, no integrity impact. Because XML is routinely accepted from untrusted sources and parsed with default options, one request can stall a server. The payloads are highly compressible, so any endpoint accepting compressed XML faces additional amplification. Finding B is additionally reachable via an explicit `normalize()` call on a programmatically built DOM (see Proof of Concept), so applications that construct a document from attacker-influenced data and normalize it are exposed even without parsing.

## Severity note

The complexity is **quadratic**, not exponential, so a multi-second stall requires tens-to-hundreds of KB of input. `VA:H` reflects that xmldom applies **no** input-size limit and the path runs on default-options parsing, so a single unbounded parse can fully stall the event loop.

## Fix Applied

Two independent, non-breaking fixes shipped together — each alone leaves the other's quadratic cost dominating the default parse. Finding A — terminate the malformed tag-name scan at an embedded `<`, so error recovery is linear instead of O(n²). DOM output is unchanged; only the reported error-message text differs (error strings are not a semver contract). Finding B — merge adjacent text nodes in `normalize()` in O(K) instead of O(K²), which also closes the same slowdown reachable programmatically through a direct `normalize()` call. Both ship on both maintained versions.