Skip to content

Prettier quadratic CPU consumption when formatting GFM Markdown tables

Moderate
fisker published GHSA-4cm8-f57v-mqm6 Oct 11, 2026

Package

npm prettier (npm)

Affected versions

>=3.9.0, <=3.9.9; 3.9.9 tested

Patched versions

3.9.10

Description

Summary

Prettier's Markdown parser (parser "markdown", also reached through "mdx" table content) ships a bundled micromark-extension-gfm-table whose EditMap resolves event edits by linearly scanning an in-memory array on every edit. A GFM table with N body rows triggers O(N) edits, each scanning an O(N) list (plus an O(N) event slice per edit in consume()), so formatting time grows as O(N²).

A ~40 KB Markdown document that is a single GFM table with 4,000 rows takes ~1.1 s to format, whereas a paragraph of the identical byte size takes ~65 ms. Doubling the row count roughly quadruples the time. Because Prettier is embedded in countless online formatters, playgrounds, and review/comment widgets that turn untrusted Markdown into HTML or formatted text, an attacker can send a small (~100–300 KB) Markdown payload that pins a CPU core for tens of seconds. There is no error, no malformed input required — the table is valid CommonMark/GFM.

No prototype-pollution vector was found; this is an availability (algorithmic-complexity) issue only.

Details

  • Affected package: prettier (npm), version 3.9.9 (latest stable), commit cdd17f2 ("Release 3.9.9", 2026-09-23). Node v22.23.2, macOS arm64.
  • The Markdown parser was newly migrated to micromark in Prettier 3.9.0 (2026-06-27); this code path is new and had not been load-tested against adversarial table shapes.
  • Bundled dependency: [email protected] (pinned in Prettier's lockfile). The linear-scan EditMap.add is the root cause.
  • Root cause file/line (upstream source of the bundled code): micromark-extension-gfm-table/lib/edit-map.js, function addImplementation, the while (index < editMap.map.length) linear scan (≈ lines 132–153), compounded by the reverse-iteration events.slice() loop in consume() (≈ lines 98–119).
  • Root cause in the Prettier bundle: node_modules/prettier/plugins/markdown.mjs, line 33. The minified EditMap class is var Kr=class{constructor(){this.map=[]}add(t,r,n){sd(this,t,r,n)}consume(t){...}} (ctor at line 33 col 22432) and the linear-scan inserter is function sd(e,t,r,n){...for(;a<e.map.length;){if(e.map[a][0]===t){...}a+=1}e.map.push([t,r,n])} (line 33 col 22793). The table resolveAll function cd(...) allocates p=new Kr and calls p.add(...) once per cell boundary per row.
  • Why it is quadratic: for a table with N rows, cd/Qr/ro issue ~4N add() calls. Each add scans the entire map array (which grows to O(N)) to dedupe edits at a given index → O(N²) comparisons. consume() then iterates the O(N) edits in reverse, calling events.slice(...) (an O(events.length) copy) each time → a second O(N²) term.
  • Sibling surface checked: the same EditMap is used only by GFM tables. Plain nested links/images ([[[...x...]]]) show a much milder linear-in-N² term in core micromark (≈10× smaller constant; ~150 ms at N=6,400) and are not reported here as a separate issue. The less/postcss-less parser showed a superlinear signal in isolation but it originates in postcss-less itself and is not reachable through Prettier's bundled version with a smaller constant; not included.
  • Prototype pollution: canaries planted on Object.prototype and fed __proto__/constructor.prototype keys across JSON, YAML, babel, graphql, glimmer, html, css parsers did not result in pollution of a fresh object.

Tested patch

The following patch was tested before reporting:

From 0000000000000000000000000000000000000000 (prettier bundled micromark-extension-gfm-table 2.1.1)
Subject: [PATCH] perf(markdown): make GFM table EditMap add O(1) instead of O(n)

The bundled micromark-extension-gfm-table EditMap resolved edits by linearly
scanning `map` for a matching index on every `add()` call. A table with N
rows issues O(N) edits, each scanning an O(N)-length array, making table
parsing O(N^2). A second O(N) factor comes from the per-edit
`events.slice()` inside `consume()`.

This change keys edits by index in a Map, mirroring the upstream fix
(shipped in micromark-extension-gfm-table 2.1.2). Output is byte-identical.

---
 src/language-markdown/parse/micromark/edit-map.js (derived) | 16 ++++++++------
 1 file changed, 10 insertions(+), 6 deletions(-)

diff --git a/edit-map.js b/edit-map.js
--- a/edit-map.js
+++ b/edit-map.js
@@ -34,6 +34,11 @@ export class EditMap {
      * @type {Array<Change>}
      */
     this.map = [];
+
+    /**
+     * Changes by index, so `add` does not scan `map`.
+     * @type {Map<number, Change>}
+     */
+    this.index = new Map();
   }
 ...
@@ -132,21 +137,17 @@ function addImplementation(editMap, at, remove, add) {
   if (remove === 0 && add.length === 0) {
     return;
   }
-  let index = 0;
-  while (index < editMap.map.length) {
-    if (editMap.map[index][0] === at) {
-      editMap.map[index][1] += remove;
-      editMap.map[index][2].push(...add);
-      return;
-    }
-    index += 1;
-  }
-  editMap.map.push([at, remove, add]);
+  const existing = editMap.index.get(at);
+  if (existing) {
+    existing[1] += remove;
+    existing[2].push(...add);
+    return;
+  }
+  const change = [at, remove, add];
+  editMap.map.push(change);
+  editMap.index.set(at, change);
 }
 ...
   // in consume(), after `this.map.length = 0;` add:
+  this.index.clear();

Release note:
  Markdown: fix quadratic (O(n^2)) CPU usage when formatting GFM tables with
  many rows. A table of N rows now parses in O(N) instead of O(N^2); output
  is unchanged. Upgrades bundled micromark-extension-gfm-table to 2.1.2.

Proof of concept

Environment: Node v22.23.2, [email protected] from npm, prettier.format(code, { parser: "markdown" }).

Exploit input (4,000-row GFM table, ~40 KB):

| a | b |
|---|---|
| x | y |
| x | y |
...   (4,000 identical rows)

Control (paragraph of identical byte length, ~40 KB): word word word ...

Measured wall time (pre-patch, captured):

N (rows) Exploit table (ms) Control paragraph (ms)
500 44 14
1,000 104 22
2,000 309 37
4,000 1,079 66
8,000 4,087 113

Doubling N → ~3.5–4× time (constant ms/N² ≈ 4e-5); control grows linearly (~2×). A 25,600-row table (~250 KB) exceeds ~40 s on one core.

Post-patch (applying the fix below — keying EditMap edits by index in a Map):

N (rows) Exploit table (ms) post-patch
500 32
1,000 58
2,000 81
4,000 157
8,000 360

Doubling N → ~2× (linear). At N=8,000 the table format time dropped from 4,087 ms to 360 ms (≈11×). Output on the exploit and on a representative table corpus was verified byte-identical (112,028 bytes matched exactly before/after).

A runnable harness (poc.js, verify-identical.js) and the raw timing tables are in the artifacts directory.

Impact

  • Availability denial: a single small HTTP request to an online Prettier-based Markdown formatter/playground pins a worker CPU core for seconds-to-minutes. A handful of concurrent such requests exhausts the formatter's worker pool, denying service to legitimate users.
  • Confidentiality and integrity are unaffected; no code execution, no information disclosure, no prototype pollution.
  • The payload is valid, syntactically correct GFM — no fuzzing/crash conditions, no parser error — so it passes through normal input filters.
  • Scope of affected users: anyone exposing Prettier's Markdown parser to untrusted input (playgrounds, issue/comment renderers, docs pipelines, shared format-as-a-service).

Severity

Moderate

CVSS overall score

This score calculates overall vulnerability severity from 0 to 10 and is based on the Common Vulnerability Scoring System (CVSS).
/ 10

CVSS v3 base metrics

Attack vector
Network
Attack complexity
Low
Privileges required
None
User interaction
None
Scope
Unchanged
Confidentiality
None
Integrity
None
Availability
Low

CVSS v3 base metrics

Attack vector: More severe the more the remote (logically and physically) an attacker can be in order to exploit the vulnerability.
Attack complexity: More severe for the least complex attacks.
Privileges required: More severe if no privileges are required.
User interaction: More severe when no user interaction is required.
Scope: More severe when a scope change occurs, e.g. one vulnerable component impacts resources in components beyond its security scope.
Confidentiality: More severe when loss of data confidentiality is highest, measuring the level of data access available to an unauthorized user.
Integrity: More severe when loss of data integrity is the highest, measuring the consequence of data modification possible by an unauthorized user.
Availability: More severe when the loss of impacted component availability is highest.
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L

CVE ID

No known CVE

Weaknesses

Uncontrolled Resource Consumption

The product does not properly control the allocation and maintenance of a limited resource. Learn more on MITRE.

Credits