Aug 7, 2026·6 min read·13 visits
A quadratic complexity flaw in league/commonmark's heading slug generator allows remote attackers to exhaust server CPU and trigger a total Denial of Service by submitting Markdown documents with thousands of identical headings.
An algorithmic complexity vulnerability in the UniqueSlugNormalizer component of the league/commonmark PHP library allows unauthenticated remote attackers to trigger severe CPU resource consumption and Denial of Service (DoS) by submitting a Markdown document containing a high volume of duplicate headings. The slug generation loop resets its sequential search index back to 1 for every collision, resulting in a quadratic execution path. This flaw affects versions from 2.0.0-beta1 up to and including 2.8.3, and is patched in version 2.9.0.
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/commonmarkFor 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.
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H| Product | Affected Versions | Fixed Version |
|---|---|---|
league/commonmark thephpleague | >= 2.0.0-beta1, <= 2.8.3 | 2.9.0 |
| Attribute | Detail |
|---|---|
| CWE ID | CWE-400 (Uncontrolled Resource Consumption) |
| Attack Vector | Network / Unauthenticated |
| CVSS v3.1 Score | 7.5 (High) |
| Exploit Status | Proof-of-Concept (PoC) Available |
| Vulnerability Class | Algorithmic Complexity / Denial of Service |
| Affected Component | UniqueSlugNormalizer |
The product does not properly control the allocation and maintenance of a limited resource, enabling an actor to influence the amount of resources consumed, eventually leading to the exhaustion of available resources.
NATS Server prior to versions 2.12.8 and 2.14.3 contains an incorrect authorization vulnerability (CWE-863) in its message tracing subsystem. When evaluating whether a connection is permitted to publish trace events to a destination subject specified in the Nats-Trace-Dest header, the server only checks standard client permissions and omits permission checks for leaf node connections. This allows a connected leaf node operator with restricted publishing privileges to emit internal trace events to unauthorized subjects and suppress standard message delivery using the Nats-Trace-Only header.
CVE-2026-63341 is a high-severity Denial of Service (DoS) vulnerability in the Aedes MQTT broker for Node.js affecting all versions prior to 1.1.1. The flaw stems from missing input validation on the hierarchical depth of incoming MQTT topic strings before they are passed to the underlying topic-matching engine, qlobber. Because qlobber enforces a hardcoded limit of 100 topic levels and throws a synchronous exception when this threshold is exceeded, an attacker can send a single MQTT packet containing 101 or more forward-slash-separated levels to trigger an uncaught exception that immediately terminates the Node.js broker process.
CVE-2026-61725 is a path traversal vulnerability (CWE-22) in the sevenz-rust2 Cargo package prior to version 0.21.1. The vulnerability occurs because the decompression utility fails to validate or sanitize archive entry filenames before joining them with the destination directory path via std::path::Path::join. An attacker who supplies a crafted 7z archive containing parent directory traversal sequences or absolute paths can write or overwrite arbitrary files on the host filesystem with the privileges of the extracting process.
CVE-2026-77309 (GHSA-jrjx-9jjw-747m) is a high-severity unauthenticated remote code execution vulnerability affecting NASA-AMMOS AIT-GUI versions 1.0.0 through 2.5.0. The flaw results from chaining an incomplete file cleanup error in the telemetry query endpoint (/tlm/query) with a directory traversal flaw in the script execution endpoint (/script/run). An attacker on an adjacent network can stage arbitrary Python statements into a static file on disk and execute that file under the privileges of the AIT-GUI web server process.
A vulnerability classified under CWE-116 (Improper Encoding or Escaping of Output) exists in memtomem-stm versions 0.1.0 through 0.1.33. The software acts as a Model Context Protocol (MCP) short-term memory proxy gateway for AI agent architectures. When surfacing retrieved memories and scratchpad items into downstream Large Language Model (LLM) context envelopes, the SurfacingFormatter component fails to properly sanitize untrusted memory attributes. An attacker with the ability to plant untrusted content into the agent's long-term or working memory store can inject arbitrary structural delimiters, close the <surfaced-memories> XML boundary prematurely, visually obscure instructions using Unicode bidirectional overrides, and execute stored prompt injection attacks against downstream LLM agents.
CVE-2026-77331 (GHSA-72jh-722p-rqr3) is a concurrency and session-state synchronization vulnerability in memtomem-stm, a short-term memory proxy gateway for AI agents. In versions 0.1.2 prior to 0.1.34, concurrent Model Context Protocol (MCP) Remote Procedure Call (RPC) failures or mid-flight task cancellations can initiate duplicate reconnect loops and permit dirty or cancelled transport sessions to be reused. This deficiency results in session-state integrity loss and local service degradation.