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.