xmldom: Quadratic-time parsing via the malformed-input recovery path — `parseElementStartPart` re-scan and `normalize()` adjacent-text merge

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.

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)

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.