GHSA-3Q6V-R5MR-HXV8: Algorithmic Complexity Denial of Service in league/commonmark GFM Table Extension

The GitHub Flavored Markdown (GFM) Table extension within the PHP league/commonmark library contains an algorithmic complexity flaw. This flaw enables remote attackers to exhaust CPU resources on the hosting server, resulting in a Denial of Service. The vulnerability lies specifically within the table start parser, which attempts to determine if an active paragraph represents the initiation of a GFM table container.\n\nUnder standard conditions, markdown paragraphs are processed line-by-line as they grow. When the GFM Table extension is enabled, the library invokes the table parser on every line to evaluate potential table syntax. Because the parser performs an unconstrained scan of the entire accumulated paragraph on every iteration, the time complexity scales quadratically ($O(N^2)$) relative to the number of lines $N$ within the paragraph block.\n\nThis behavior classifies the vulnerability under CWE-400 (Uncontrolled Resource Consumption) and CWE-1333 (Inefficient Regular Expression Complexity / Algorithmic Complexity). The exposure surface is significant because many web applications leverage league/commonmark to render user-provided Markdown content in forums, comments, and documentation portals without prior input length validation.

The technical root cause centers on the TableStartParser::tryStart() method. The parser is designed to identify the start of a GFM table, which requires detecting a header row followed by a delimiter row. However, a paragraph block remains active and continues to grow until a blank line or a different block-level container interrupts it. Each time a new line is added to this active paragraph, the library queries the table block-start parser.\n\nInside TableStartParser::tryStart(), the code calls $parserState->getParagraphContent() to retrieve the entire accumulated paragraph content as a single string. It then performs a quick-check lookup using the PHP native function \\strpos($paragraph, '|'). If the pipe character is not found, the parser immediately returns, indicating that no table starts here.\n\nWhile this check is designed to quickly discard non-table lines, executing it on the entire growing paragraph buffer creates the performance bottleneck. On line 1, \\strpos scans line 1. On line 2, it scans lines 1 and 2. On line $N$, it scans the entire block of $N$ lines. If the paragraph is extremely long and contains no pipe characters, the total scanning time becomes quadratic with respect to the number of lines.\n\nAn important constraint exists within this execution path. A pre-evaluation filter called SkipLinesStartingWithLettersParser evaluates incoming lines first. If a line begins with a standard alphabetical character, this parser short-circuits the table evaluation. Consequently, the quadratic-time vulnerability can only be triggered if the payload contains lines starting with non-alphabetical characters, such as numbers, spaces, or multibyte Unicode characters.

The vulnerable implementation of TableStartParser::tryStart() in versions prior to 2.10.2 highlights the scanning inefficiency. The method attempts to locate a pipe character within the entire historical paragraph string before verifying the current line's validity. This is demonstrated in the pre-patch source code:\n\nphp\npublic function tryStart(Cursor $cursor, MarkdownParserStateInterface $parserState): ?BlockStart\n{\n $paragraph = $parserState->getParagraphContent();\n if ($paragraph === null || \\strpos($paragraph, '|') === false) {\n return BlockStart::none();\n }\n\n\nTo fix this behavior, the maintainers isolated the table header checking logic. In Markdown GFM table specifications, only the line immediately preceding the table delimiter row can serve as the table header. Therefore, there is no technical requirement to scan the preceding lines of an active paragraph. The patch targets the last line of the paragraph exclusively.\n\nThe corrected implementation uses \\strrpos() to locate the last newline character in the accumulated paragraph. It then extracts only the final line of text using \\substr() and performs the \\strpos() check on that segment alone. This modification guarantees that the scan length is limited to the length of the current line, $O(L)$, reducing the overall parsing time complexity from quadratic $O(N^2)$ to linear $O(N).\n\ndiff\n- if ($paragraph === null || \\strpos($paragraph, '|') === false) {\n+ if ($paragraph === null) {\n+ return BlockStart::none();\n+ }\n+\n+ // Only the paragraph's last line can be the header row, so limit the quick check to it.\n+ // Scanning the whole (growing) paragraph on every line would be quadratic.\n+ $lastLineBreak = \\strrpos($paragraph, \"\\n\");\n+ $lastLine = $lastLineBreak === false ? $paragraph : \\substr($paragraph, $lastLineBreak + 1);\n+ if (\\strpos($lastLine, '|') === false) {\n return BlockStart::none();\n }\n

An attacker can exploit this vulnerability by submitting a highly dense Markdown payload to any application endpoint that parses GFM Markdown. The target configuration must have the GFM TableExtension enabled. The attack requires no authentication or special privileges.\n\nThe crafted payload must fulfill four specific criteria to bypass optimization structures and trigger the vulnerable loop. First, the input must contain thousands of lines. Second, none of the lines may begin with standard alphabetical characters. Third, none of the lines may contain a pipe symbol. Fourth, the paragraph must remain unbroken by empty lines.\n\nStandard proof-of-concept payloads utilize repeated lines of numerical sequences or multibyte Unicode sequences. When the parser processes these inputs, the CPU utilization of the executing PHP worker process spikes to 100%. If an attacker submits multiple requests concurrently, the server's thread pool becomes completely exhausted, resulting in a global denial of service for all users.\n\nHere is an illustration of the execution flow during an attack:\n\nmermaid\ngraph LR\n A[\"Client sends payload\"] --> B[\"Markdown parser initialized\"]\n B --> C[\"TableStartParser processes each line\"]\n C --> D{\"Line starts with letter?\"}\n D -- \"Yes\" --> E[\"Short-circuit evaluation\"]\n D -- \"No\" --> F[\"Scan entire accumulated paragraph for '|'\"]\n F --> G{\"Is paragraph long?\"}\n G -- \"Yes (No '|' found)\" --> H[\"Quadratic-time O(N^2) CPU loop\"]\n G -- \"No\" --> I[\"Process next line\"]\n H --> J[\"CPU resource exhaustion & Thread lock\"]\n

The primary impact of this vulnerability is a complete Denial of Service (DoS) of the hosting application. Because PHP processes are typically single-threaded and capped by pool limits, a small number of concurrent exploit payloads can easily exhaust all available PHP worker threads. This blocks legitimate incoming HTTP traffic, leading to timeout errors and system downtime.\n\nThe vulnerability is remediated by upgrading league/commonmark to version 2.10.2 or higher. This release contains the patch that limits string scanning to the last line of the active paragraph block. If upgrading is not immediately feasible, developers can mitigate the risk by disabling the TableExtension from the CommonMark environment configuration.\n\nIn addition to patching, implementing Web Application Firewall (WAF) rules or rate-limiting mechanisms can provide defense-in-depth. Security teams should monitor for POST requests containing exceptionally large payloads with highly repetitive numerical or multibyte lines. Input validation that restricts maximum submission sizes before parsing further reduces the attack surface.