markdown-it: Quadratische Rendering-Zeit einer einzelnen mehrzeiligen Link-Referenzdefinition bei Standardoptionen (Regression seit 14.0)

Zusammenfassung

Eine Link-Referenzdefinition, deren Label oder Titel niemals geschlossen wird, weist in markdown-it 15.0.2 mit Standardoptionen eine Komplexität von O(n²) auf. Fortsetzungszeilen werden in src/rules_block/reference.ts verzögert über str += lineContent angehängt, und nachfolgende Aufrufe von charCodeAt sowie slice verflachen den V8-Cons-String, wodurch alles bisher Gesammelte kopiert wird; dies geschieht, bevor die Regel entscheidet, dass die Definition ungültig ist. Es handelt sich um eine Regression, die durch PR #1004 in 14.0.0 eingeführt wurde: 13.0.2 verarbeitete eine Eingabe von 313 KB in 125 ms, während jede Version danach etwa 11 Sekunden für dieselbe Eingabe benötigt. Bei den folgenden Größen benötigt 200 KB 3.6 Sekunden, 400 KB benötigt 18.1 Sekunden und 800 KB benötigt 74.0 Sekunden, was etwa dem 4–5-Fachen pro Verdopplung entspricht. Es sind keine Optionen erforderlich, um das Verhalten auszulösen.

Details

src/rules_block/reference.ts hängt Fortsetzungszeilen mit str += lineContent in den Zeilen 74, 83, 100, 133 und 150 an und indiziert den akkumulierten String anschließend über str.charCodeAt(pos) in den Label- und Whitespace-Schleifen sowie über str.slice(...) in parseLinkTitle. V8 stellt += als Cons-String dar, und das nächste charCodeAt oder slice verflacht ihn, wobei alles bisher Gesammelte kopiert wird; daher erfordert eine Definition über n Zeilen O(n²). Isolierte Tests bestätigen, dass diese Regel verantwortlich ist: Ein reines Block-Parsing mit deaktiviertem Inline ist weiterhin quadratisch, md.disable('reference') macht dieselbe Eingabe linear, und derselbe Text ohne das führende [ ist ebenfalls linear. Der Fix besteht darin, Positionen in state.src zu verfolgen, anstatt str aufzubauen, oder Zeilenabschnitte in einem Array zu sammeln und darüber zu parsen. Mindestens sollte das Scannen des Labels nach 999 Zeichen (CommonMark §6.3) beendet werden, bevor weitere Zeilen geladen werden, und die Titelfortsetzung begrenzt werden. Fügen Sie einen pathologischen Test mit einem nicht geschlossenen Titel und Label über 100k Zeilen hinzu. Das offene PR #1215 bearbeitet dieselbe Datei, seine Label-Prüfung erfolgt jedoch nach der Label-Schleife, sodass keine der beiden Varianten begrenzt wird und die Behebung zusammen mit diesem PR erfolgen kann.

Die beobachtete Ausgabe des PoC war: unclosed title n=100000 200009 B 3585.5 ms unclosed title n=200000 400009 B 18107.1 ms (5.05x) unclosed title n=400000 800009 B 73954.4 ms (4.08x)

Regressionsvergleich bei 313 KB: 13.0.2 → 125 ms, 14.1.0 → 11.4 s, 15.0.0 → 10.6 s, 15.0.2 → 10.7 s.

Proof of Concept

Ausführung des PoC:

1. mkdir -p markdown-it-poc && cd markdown-it-poc
2. npm init -y
3. npm i markdown-it@15.0.2
4. node poc_markdown_it.js

Der PoC lautet:

// poc_markdown_it.js
// Requires: npm install markdown-it@15.0.2
const MarkdownIt = require('markdown-it');
const md = new MarkdownIt();

function bench(label, src) {
  const t0 = process.hrtime.bigint();
  md.render(src);
  const t1 = process.hrtime.bigint();
  console.log(
    `${label.padEnd(30)} ${String(src.length).padStart(9)} B ${(Number(t1 - t0) / 1e6).toFixed(1).padStart(9)} ms`
  );
}

// Unclosed title: one reference definition spread over many lines
for (const n of [100000, 200000, 400000]) {
  bench(`unclosed title n=${n}`, '[a]: /u "' + 'x\n'.repeat(n));
}

// Unclosed label
for (const n of [5000, 10000, 20000]) {
  bench(`unclosed label n=${n}`, '[' + 'a\n'.repeat(n));
}

Auswirkungen

Dies ist ein Denial-of-Service durch algorithmische Komplexität (CWE-407). Jeder Server, der Markdown von Benutzern mit markdown-it unter Standardoptionen rendert, ist betroffen, einschließlich Kommentaren, Issues, Chats, Wikis, Dokumentenvorschauen und LLM-Chat-UIs. Ein Request-Body von ca. 400 KB blockiert die Node.js-Ereignisschleife für etwa 18 Sekunden und ein Body von ca. 800 KB für etwa 74 Sekunden. Dies entspricht derselben Klasse und demselben Angreifermodell wie GHSA-253c, ist jedoch ohne optionale Konfigurationen erreichbar, da der betroffene Pfad eine Core-Block-Regel ist.