markdown-it: Kwadratowy czas renderowania pojedynczej wielowierszowej definicji odnośnika przy domyślnych opcjach (regresja od 14.0)

Podsumowanie

Definicja odnośnika referencyjnego, której etykieta lub tytuł nigdy nie zostaną zamknięte, charakteryzuje się złożonością O(n²) w markdown-it 15.0.2 przy domyślnych opcjach. Linie kontynuacji są pobierane leniwie za pomocą str += lineContent w pliku src/rules_block/reference.ts, a kolejne wywołania charCodeAt oraz slice spłaszczają cons-string silnika V8, kopiując wszystko, co dotychczas zgromadzono; operacja ta wykonuje się, zanim reguła uzna definicję za nieprawidłową. Jest to regresja wprowadzona przez PR #1004 w 14.0.0: wersja 13.0.2 przetwarzała wejście o rozmiarze 313 KB w 125 ms, podczas gdy każda kolejna wersja potrzebuje około 11 sekund na to samo wejście. Przy poniższych rozmiarach 200 KB zajmuje 3.6 sekund, 400 KB zajmuje 18.1 sekund, a 800 KB zajmuje 74.0 sekund, co daje około 4–5× przy każdym podwojeniu rozmiaru. Do wywołania problemu nie są wymagane żadne dodatkowe opcje.

Szczegóły

Plik src/rules_block/reference.ts dołącza linie kontynuacji za pomocą str += lineContent w liniach 74, 83, 100, 133 i 150, a następnie indeksuje skumulowany ciąg znaków poprzez str.charCodeAt(pos) w pętlach etykiety i białych znaków oraz str.slice(...) w parseLinkTitle. Silnik V8 reprezentuje += jako cons-string, a kolejne wywołanie charCodeAt lub slice spłaszcza go, kopiując dotychczas zgromadzoną zawartość, przez co jedna definicja obejmująca n wierszy kosztuje O(n²). Izolacja potwierdza, że odpowiada za to ta reguła: przetwarzanie samych bloków z wyłączonym parserem inline nadal jest kwadratowe, md.disable('reference') sprawia, że to samo wejście jest przetwarzane liniowo, a ten sam tekst bez początkowego [ ma złożoność liniową. Poprawka polega na śledzeniu pozycji w state.src zamiast budowania ciągu str lub na zbieraniu wycinków linii w tablicy i parsowaniu na ich podstawie. Minimalnie należy zatrzymać skanowanie etykiety po 999 znakach (CommonMark §6.3) przed pobieraniem kolejnych linii oraz ograniczyć kontynuację tytułu. Należy dodać test patologiczny z niezamkniętym tytułem i etykietą o długości 100k linii. Otwarty PR #1215 modyfikuje ten sam plik, lecz jego sprawdzenie etykiety wykonuje się po pętli etykiety, więc nie ogranicza żadnego z wariantów, a poprawka może zostać wdrożona razem z tym PR.

Zaobserwowany wynik z PoC: 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)

Porównanie regresji przy 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

Instrukcja uruchomienia 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

Kod PoC:

// 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));
}

Wpływ

Jest to podatność odmowy usługi wynikająca ze złożoności algorytmicznej (CWE-407). Podatny jest każdy serwer renderujący Markdown od użytkowników za pomocą markdown-it przy domyślnych opcjach, w tym komentarze, zgłoszenia, czaty, wiki, podglądy dokumentacji oraz interfejsy LLM. Treść żądania o rozmiarze ~400 KB blokuje pętlę zdarzeń Node.js na około 18 sekund, a treść o rozmiarze ~800 KB na około 74 sekund. Jest to ta sama klasa podatności i model atakującego co w przypadku GHSA-253c, jednak jest osiągalna bez żadnych dodatkowych opcji konfiguracyjnych, ponieważ dotknięta ścieżka to podstawowa reguła blokowa.