CVE-2026-84305: Algorithmic Complexity Vulnerability (ReindentFilter CPU Exhaustion) in sqlparse

The non-validating SQL parser library for Python, sqlparse, provides features for tokenizing, parsing, and formatting SQL statements. The vulnerability resides within the formatting module, specifically affecting the ReindentFilter class which manages token alignment and indentation. When formatting is performed with the reindentation flag enabled, the parser calculates indentation offsets dynamically for each SQL token group.\n\nAn attack surface is exposed in applications that accept user-defined SQL statements and format them before logging, displaying, or processing them further. This is a common pattern in database management interfaces, web-based SQL beautifiers, and query-logging systems. By supplying a crafted SQL input, an attacker can exploit an inefficient algorithm in the formatting step to cause a denial of service.\n\nThe vulnerability is classified under CWE-407 (Inefficient Algorithmic Complexity). It exhibits quadratic $O(N^2)$ time complexity when processing structures with numerous parallel tuple sequences. This behavior allows relatively small payloads to exhaust CPU resources on the target system.

The core issue exists in how the ReindentFilter calculates the column offset for any given token during formatting. To compute this offset, the filter calls the internal _get_offset(self, token) method, which determines the length of the string emitted on the current line prior to the token. In versions before 0.6.0, this calculation relied on a helper method named _flatten_up_to_token(self, token).\n\nThe _flatten_up_to_token() method performs a forward traversal of the parsed Abstract Syntax Tree (AST), starting from the very first token in the statement (self._curr_stmt) up to the target token. After yielding all preceding tokens, the filter joins them into a single string to measure the characters on the active line. This layout requires a complete reconstruction of the preceding SQL string for every call to _get_offset().\n\nWhen a SQL query contains a large number of tuple lists, such as thousands of elements within an IN clause or an INSERT INTO ... VALUES statement, _get_offset() is executed once for each group. For $N$ parenthesized groups, the system performs a sequence of string building operations proportional to $1 + 2 + \dots + N$, resulting in $O(N^2)$ quadratic complexity. While sqlparse implements a limit of MAX_GROUPING_TOKENS = 10000 to prevent deep recursion, a flat array of tuples bypasses this threshold, permitting execution of the vulnerable formatting routine.

A review of the vulnerable implementation in sqlparse/filters/reindent.py highlights the inefficient forward traversal mechanism. The helper method _flatten_up_to_token() flattens the syntax tree starting from the root of the parsed structure for every offset evaluation:\n\npython\n# Vulnerable implementation in sqlparse < 0.6.0\ndef _flatten_up_to_token(self, token):\n \"\"\"Yields all tokens up to token but excluding current.\"\"\"\n if token.is_group:\n token = next(token.flatten())\n\n for t in self._curr_stmt.flatten():\n if t == token:\n break\n yield t\n\ndef _get_offset(self, token):\n raw = ''.join(map(str, self._flatten_up_to_token(token)))\n line = (raw or '\\n').splitlines()[-1]\n return len(line) - len(self.char * self.leading_ws)\n\n\nThe patch introduced in version 0.6.0 (commit a51df6d9e2d31b44be9adb6bc8732517db6bf96b) completely eliminates _flatten_up_to_token(). It introduces _current_line_len(), which performs a backward traversal from the current token. It navigates backwards through parent and sibling nodes, accumulating character counts and halting immediately upon encountering a newline character:\n\npython\n# Patched implementation in sqlparse >= 0.6.0\ndef _current_line_len(self, token):\n length = 0\n node = token\n while node is not self._curr_stmt and node.parent is not None:\n parent = node.parent\n stack = parent.tokens[:parent.tokens.index(node)]\n while stack:\n prev_ = stack.pop()\n if prev_.is_group:\n stack.extend(prev_.tokens)\n continue\n value = prev_.value\n size = len(value)\n if not size:\n continue\n lines = value.splitlines()\n if len(lines) == 1 and len(lines[0]) == size:\n length += size\n continue\n lines = (value + '.').splitlines()\n tail = len(lines[-1]) - 1 + length\n if tail:\n return tail\n if len(lines) > 2:\n return len(lines[-2])\n length = len(lines[0])\n node = parent\n return length\n\n\nThis remediation successfully reduces the computational complexity of determining the offset from $O(\text{statement\_length})$ to $O(\text{line\_length})$. Since SQL lines are naturally bounded by design, the lookup executes in nearly constant time, rendering the overall formatting operation linear $O(N)$.

Exploitation of this vulnerability requires an application configuration that formats user-controlled SQL input with the opt-in reindent=True parameter. An attacker can construct a payload consisting of a large, flat collection of tuple elements. This structure is intentionally designed to remain below the default security limit of 10,000 grouping tokens, ensuring that the initial parsing phase completes without exception.\n\nmermaid\ngraph LR\n A[\"Crafted Payload (~12 KB SQL)\"] --> B[\"sqlparse.format(reindent=True)\"]\n B --> C[\"ReindentFilter processes token groups\"]\n C --> D[\"Quadratic complexity in _get_offset()\"]\n D --> E[\"100% CPU exhaustion on worker thread\"]\n\n\nTo execute the attack, a payload containing approximately 1,500 tuples is sent to the target endpoint. Each tuple increases the overall prefix length that the vulnerable version must reconstruct. As the formatting engine handles each sequential group, the computational overhead escalates. This results in CPU starvation for the active application thread.\n\nThe benchmark code demonstrates that doubling the size of the tuple array causes a four-fold increase in execution time. While a normal SQL query of standard size formats in milliseconds, a 12 KB payload can pin a modern CPU core for several seconds, leading to thread exhaustion if multiple requests are processed simultaneously.

The primary impact of CVE-2026-84305 is application-level denial of service. When a vulnerable instance processes a crafted SQL statement, the executing worker thread is blocked entirely while computing token offsets. In single-threaded runtime environments, this action halts the entire application process, preventing all other concurrent requests from being served.\n\nIn multi-threaded or multi-process architectures, an attacker can launch concurrent requests containing the payload to consume all available worker slots. Once the thread pool is fully utilized, the application server stops responding to legitimate traffic. This can trigger health check failures, causing automated load balancers to terminate and restart the containers, compounding the service disruption.\n\nThis vulnerability is assigned a CVSS v4.0 score of 5.1, reflecting a medium-severity local or remote threat with low operational complexity. There is no risk of confidentiality loss, data integrity compromise, or privilege escalation. The scope of impact is restricted strictly to resource exhaustion and system availability.

The primary remediation step is upgrading the sqlparse package to version 0.6.0 or higher. This release contains the updated backward-traversal algorithm that resolves the algorithmic complexity flaw. Security teams should verify dependencies in project requirements files and execute the package update.\n\nIf immediate upgrade is not feasible, a temporary workaround consists of disabling the reindent formatting flag in application code. Developers should review all invocations of sqlparse.format() and ensure that reindent is set to False when processing input from untrusted sources. This action bypasses the vulnerable ReindentFilter execution path completely.\n\npython\n# Vulnerable pattern\nformatted_query = sqlparse.format(user_input, reindent=True)\n\n# Mitigated pattern\nformatted_query = sqlparse.format(user_input, reindent=False)\n\n\nThe fix implemented in version 0.6.0 is complete and robust. By switching from a full prefix-rebuilding forward scan to a localized backward scan bounded by newline characters, the library avoids calculating offset information for irrelevant lines. This algorithmic improvement permanently eliminates the quadratic behavior without reducing the functionality of the formatting system.