GHSA-MH25-X5HQ-WRQP: Algorithmic Complexity Denial of Service in league/commonmark UniqueSlugNormalizer

The league/commonmark package is a highly popular, extensible PHP Markdown parser that fully supports the CommonMark and GitHub Flavored Markdown (GFM) specifications. Within modern web applications, it is standard practice to enable heading anchors using extensions like the HeadingPermalinkExtension. This component relies on the UniqueSlugNormalizer to transform heading text into readable, unique identifiers for HTML anchor linking.

When multiple headings within a single document produce the same initial slug, the normalizer appends a sequential numeric suffix to guarantee uniqueness (e.g., # Heading becomes heading, the second becomes heading-1, and the third becomes heading-2). This mechanism is critical for ensuring page navigation and structural integrity of parsed HTML documents.

However, in all versions of the library from 2.0.0-beta1 up to and including 2.8.3, the unique slug generation engine contains an algorithmic complexity flaw. Specifically, when processing a document with a massive sequence of duplicate headings, the CPU time required to generate unique identifiers escalates quadratically ($O(N^2)$). This flaw allows unauthenticated remote attackers to trigger severe CPU resource consumption, leading to a complete Denial of Service.

To understand the core algorithmic vulnerability, we must examine how the UniqueSlugNormalizer tracks and resolves slug collisions. The normalizer maintains an internal tracking array named $alreadyUsed to keep track of every slug that has already been generated within the current parsing context. In the vulnerable versions, this array maps the slug string to a simple boolean value (array<string, bool>).

When a new heading is parsed, the engine normalizes the text to create a base slug. If this base slug already exists in the $alreadyUsed array, the normalizer enters a do-while loop to find a unique suffix. Crucially, the loop resets the suffix search index to 0 and increments it by 1 on every single collision, sequentially checking if $normalized-$suffix is present in the tracking array.

For the $N$-th identical heading in a document, the normalizer must sequentially verify that $normalized-1, $normalized-2, ..., $normalized-(N-1) are all occupied before it can conclude that $normalized-N is free. This linear search inside a loop results in a classic quadratic complexity flaw. The total number of array lookups required for $N$ identical headers is calculated as $\frac{N(N + 1)}{2}$. For example, a document containing 10,000 duplicate headers requires approximately 50 million array lookups and string interpolations, exhausting server CPU capacity.

Evaluating the code-level changes between v2.8.3 and v2.9.0 highlights the exact mechanism of the flaw and the patch. In the vulnerable version, the loop repeatedly calls \array_key_exists starting from zero:

// Vulnerable Implementation in v2.8.3 and lower
if (\array_key_exists($normalized, $this->alreadyUsed)) {
    $suffix = 0;
    do {
        ++$suffix;
    } while (\array_key_exists("$normalized-$suffix", $this->alreadyUsed));
 
    $normalized = "$normalized-$suffix";
}
$this->alreadyUsed[$normalized] = true;

The patch in version v2.9.0 completely restructures this tracking logic. Instead of mapping slugs to boolean values, the $alreadyUsed array now maps each base slug to the next numeric suffix to try as an integer (array<string, int>).

// Patched Implementation in v2.9.0
if (isset($this->alreadyUsed[$normalized])) {
    $suffix = $this->alreadyUsed[$normalized];
    while (isset($this->alreadyUsed["$normalized-$suffix"])) {
        ++$suffix;
    }
 
    $this->alreadyUsed[$normalized] = $suffix + 1;
    $normalized = "$normalized-$suffix";
}
$this->alreadyUsed[$normalized] = 1;

By tracking the last used suffix in the state array, the normalizer avoids checking previously assigned indices. It directly fetches the cached next suffix, reducing the lookups from a quadratic $O(N^2)$ to a linear $O(N)$ overall complexity. This fix is complete and robust against variant attacks because it ensures that subsequent lookups bypass the occupied suffix range entirely.

Exploiting this vulnerability does not require complex tooling, authorization, or specific network positioning. The only prerequisite is a web application endpoint that parses user-supplied Markdown content using league/commonmark with heading anchor links or permalinks enabled. This scenario is highly common on wiki pages, blog comment sections, ticket systems, and public forums.

An attacker executes the attack by compiling a Markdown document composed of a large number of duplicate headings. A typical payload contains thousands of identical heading elements:

# duplicate
# duplicate
# duplicate
# duplicate
# duplicate
... [repeated 10,000 times] ...

When the attacker submits this payload via an HTTP POST request, the PHP parser thread attempts to resolve the unique slugs for all 10,000 headers. This triggers millions of iterations of the internal loop, locking the corresponding PHP-FPM or CGI process at 100% CPU utilization. Because standard web server configurations limit the number of simultaneous PHP worker processes, sending a few parallel requests with this payload completely depletes the worker pool, causing a total Denial of Service for all legitimate users.

The concrete security impact of this vulnerability is a high-severity Denial of Service (DoS). While the vulnerability does not expose sensitive data, alter database records, or facilitate remote code execution, it represents a highly effective vector for disrupting application availability with minimal effort.

From a CVSS v3.1 perspective, we assess this vulnerability at a score of 7.5 (High), with the vector string CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H. This reflects that the attack can be launched over the network without authentication or user interaction, and results in a high availability impact.

In standard PHP hosting architectures, worker pools are shared across the entire web application. When an attacker exhausts the worker threads by submitting colliding heading payloads, the entire web server is rendered incapable of serving other static or dynamic requests. This results in broad downtime, rendering the application completely offline until the hung worker processes are terminated or the web server is restarted.

The primary and recommended remediation is to upgrade league/commonmark to version v2.9.0 or higher. This version implements the optimized $alreadyUsed tracking index that completely eliminates the quadratic execution complexity.

composer update league/commonmark

For organizations that cannot immediately apply the patch, several effective mitigation options exist. The first option is to disable the HeadingPermalinkExtension if unique anchor links are not strictly necessary for the application's layout. This stops the vulnerable normalizer code path from executing entirely.

// Disable HeadingPermalinkExtension in your Markdown Environment configuration
// $environment->addExtension(new HeadingPermalinkExtension());

Additionally, applications should implement input validation controls. Setting a reasonable limit on the overall length of user-submitted Markdown or restricting the maximum number of headings allowed in a single request protects the parser from handling excessively large or malicious structures. Setting a strict max_execution_time in PHP's configuration also ensures hung threads are killed before they exhaust the server's thread pool.