GHSA-8RR7-CVQ3-GMFH: Algorithmic Complexity Denial of Service in league/commonmark AttributesExtension

The popular PHP Markdown rendering engine league/commonmark includes an optional configuration module named AttributesExtension. This extension processes special inline syntax to dynamically assign class names, IDs, and miscellaneous attributes directly to HTML elements generated from Markdown. The attack surface is exposed in any deployment where user-supplied Markdown is parsed with this extension enabled.\n\nUnder the hood, the processing pipeline evaluates consecutive attribute definitions to map them to target DOM elements. In versions of league/commonmark preceding 2.10.0, the parsing logic suffers from an algorithmic complexity vulnerability classified under CWE-407 (Inefficient Algorithmic Complexity) and CWE-400 (Uncontrolled Resource Consumption). This flaw leads to severe resource exhaustion.\n\nAn unauthenticated remote attacker can exploit this behavior by submitting a payload containing a high density of structured, adjacent inline attributes or consecutive block attribute lines. The parser attempts to resolve these recursively, causing CPU consumption to scale quadratically relative to the input length, eventually hanging the PHP worker thread and exhausting system capacity.

The core issue resides in the structural handling of attribute merging and filtering within AttributesListener.php and AttributesBlockContinueParser.php. When processing contiguous attribute structures, the parser must merge incoming values into an active accumulation array. The previous implementation executed this operation inside a loop executing once for each parsed attribute node.\n\nAt each step of the iteration, the parser invoked AttributesHelper::mergeAttributes() and subsequently AttributesHelper::filterAttributes(). The filtering routine processes the entire current collection of accumulated attributes against regular expression policies to filter out forbidden schemas or unsafe URLs. Because the filter operation scales with the total size of the accumulated dictionary, this design results in quadratic O(N^2) execution complexity.\n\nphp\n// Vulnerable iterative merge and filter loop\n$attributes = $node->getAttributes();\n$merged = AttributesHelper::mergeAttributes($pending[$id]['attributes'], $attributes);\n$merged = AttributesHelper::filterAttributes($merged, $this->allowList, $this->allowUnsafeLinks);\n$pending[$id]['attributes'] = $merged;\n\n\nAs shown above, evaluating N nodes sequentially triggers N total filtration calls on arrays of increasing size, meaning the computational overhead grows exponentially with input density. Similarly, the class AttributesBlockContinueParser::tryContinue() performed iterative, sequential merging on block-level attribute configurations. When parsing a vertical sequence of attribute blocks, each new line triggered a full merge of the previously resolved attribute array, compounding the performance degradation. This vulnerability extends and completes the earlier patch for GHSA-jjv6-8j6v-6j52, which had only addressed class-attribute merge patterns.

The resolution implemented in version 2.10.0 shifts the parsing flow from continuous inline filtering to a 'Structured Accumulation and Deferred Assembly' pattern. Rather than applying regex validation and merging at each iteration step, the updated parser tracks modifications lazily, performing the intensive filter and consolidation operations once the final structure is known.\n\nThe updated AttributesListener structure uses a dedicated accumulator to map incoming data points without performing immediate merges:\n\nphp\n/**\n * @psalm-type PendingAttributes = array{\n * node: Node,\n * front: array<string, mixed>,\n * back: array<string, mixed>,\n * classFront: list<string>,\n * classBack: list<string>,\n * hasClass: bool,\n * unfiltered: array<string, mixed>\n * }\n */\n\n\nThis design segregates attributes based on append direction and isolates the specific keys modified during the current step, avoiding redundant iterations over unaffected keys.\n\nThe revised logic only processes modified keys through the validation engine, keeping the filtering operation bound to O(1) relative to the accumulator size during individual steps. The code achieves this by running filtering only against newly added elements:\n\nphp\n// Patched iteration step isolating changed keys\n$kept = AttributesHelper::filterAttributes($touched, $this->allowList, $this->allowUnsafeLinks);\n\n\nThis ensures that unmodified elements, which have already passed filtering in prior steps, are not continuously re-evaluated. When document parsing is complete, the listener executes a single, unified consolidation call via the assemble() method. The assembly routine merges the structural front, back, and class components in a single O(N) pass, entirely eliminating the O(N^2) algorithmic bottleneck.

To exploit this vulnerability, an attacker must identify an input vector that parses user-provided Markdown through league/commonmark with the AttributesExtension enabled. Since the extension is commonly deployed to support rich-text features in CMS systems, forums, and documentation platforms, this vulnerability presents a highly accessible vector. No authentication is typically required to reach the Markdown rendering engine.\n\nThe first attack vector targets adjacent inline attributes. By sending a payload with thousands of unique attribute identifiers attached to a single element, the parser is forced to perform quadratic validation cycles:\n\nmarkdown\n{a0=\"v\"}{a1=\"v\"}{a2=\"v\"}{a3=\"v\"}...{a10000=\"v\"}\n\n\nThe high concentration of distinct attributes causes severe performance degradation, quickly hitting the maximum PHP execution limit or locking the CPU core.\n\nThe second attack vector utilizes consecutive block attribute lines to exhaust resources within the block continuation parser. The payload uses consecutive lines to define block-level configurations:\n\nmarkdown\n{a0=v}\n{a1=v}\n{a2=v}\n...\n{a10000=v}\n\n\nWhen parsed, the line-by-line continue parser repeatedly invokes the dictionary merge routine, causing CPU core starvation on the application host. The third attack vector mixes attribute blocks with link references. By interspersing reference declarations with separate attributes targeting a single trailing paragraph, the event listener is forced to resolve each element sequentially, triggering the recursive merging code path. This complex structure bypasses trivial linear scanning and demonstrates the general vulnerability of the continuous-merge architecture.

Successful exploitation of GHSA-8RR7-CVQ3-GMFH allows an unauthenticated remote attacker to cause an immediate Denial of Service (DoS) of the targeted web application. Because PHP typically operates on a synchronous, thread-per-request model (such as PHP-FPM), locking up multiple worker processes with quadratic computations quickly starves the execution pool. This prevents legitimate traffic from being processed.\n\nWhile the vulnerability does not directly expose sensitive data or facilitate remote code execution, its impact on application availability is severe. In shared hosting or containerized environments, CPU exhaustion in one application container can easily degrade performance across the entire host node. This increases the potential blast radius of the attack.\n\nFrom a threat intelligence standpoint, the vulnerability has an exploit maturity classification of 'poc'. Public proof-of-concept payloads exist, but active in-the-wild exploitation remains unconfirmed. The vulnerability is not currently listed on the CISA Known Exploited Vulnerabilities (KEV) catalog, and no corresponding ransomware campaigns have been reported.

The primary and most effective remediation path is upgrading the league/commonmark package to version 2.10.0 or higher. This version integrates the structural performance optimizations that replace the continuous-merge paradigm with deferred linear assembly. Upgrading can be performed seamlessly via Composer by updating dependencies.\n\nWhen immediate patching is not possible due to legacy environment constraints, developers can mitigate the threat by temporarily disabling the AttributesExtension in the commonmark environment configuration. If attributes are not actively required by the business logic, removing this extension eliminates the attack surface completely.\n\nAdditionally, web application firewalls (WAFs) should be configured to detect and block incoming payloads with excessive attribute patterns. Implementing limits on the total length of user-supplied Markdown strings (e.g., restricting input fields to 50KB) serves as a defense-in-depth measure. This reduces the maximum size of any potential quadratic evaluation.\n\nFinally, establishing tight request timeouts and execution resource limits within PHP configurations (such as max_execution_time in php.ini and worker pool limits in php-fpm.conf) ensures that running threads are terminated before they can completely exhaust server resources. This limits the severity of any ongoing DoS attempts.