{"id":"GHSA-vj8h-fx38-h3vc","summary":"GraphQL-core: Denial of service via quadratic complexity in the OverlappingFieldsCanBeMerged validation rule","details":"### Summary\n\nThe `OverlappingFieldsCanBeMerged` validation rule can be driven into quadratic — and\nin the worst case `O(n²·m²)` — running time by a small, highly compressible query. A\nsingle 364 KB document can occupy one CPU core for over five minutes during\n*validation*, before any resolver runs. Because the rule is part of `specified_rules`\nand therefore enabled by default, every GraphQL-core based server is affected at\ndefault settings.\n\n### Details\n\n`OverlappingFieldsCanBeMerged` compares every pair of fields that share a response\nname and recurses into their sub-selections. The memoization added for\nCVE-2023-26144 (`GHSA-9pv7-vfvm-6vr7`) is keyed by **named fragment** identity, so it\ndoes not cover this path: inline fragments are flattened into the parent selection\nset before the cache is consulted, and therefore every pair is re-compared from\nscratch at every nesting level.\n\nRepeating an inline fragment that selects the same response name at two nesting\nlevels multiplies the two effects. There was no comparison budget and no validation\ntimeout, so the rule ran to completion regardless of cost.\n\nThe cost is incurred in the **validation phase**, which is what makes this hard to\ndefend against from outside the library: query-depth limiters, complexity analyzers\nand cost estimators all operate on the parsed document *after* validation, and the\nmalicious document is trivially shallow (depth 3, complexity 1). The payload is also\none short string repeated many times, so it compresses to a few kilobytes and slips\npast body-size limits and WAF inspection that only see the compressed request.\n\n### Proof of concept\n\n```python\nimport time\nfrom graphql import build_schema, parse, validate\n\nschema = build_schema(\n    \"type Query { field: Node } type Node { f: Node, g: Node, x: String }\"\n)\n\ndef gen(n: int, m: int) -\u003e str:\n    inner = \" \".join([\"... on Node { x }\"] * m)\n    outer = \" \".join([f\"... on Node {{ f {{ {inner} }} }}\"] * n)\n    return f\"{{ field {{ {outer} }} }}\"\n\nquery = gen(200, 100)          # 364 KB, gzips to a few KB\ndocument = parse(query)\nstart = time.perf_counter()\nvalidate(schema, document)      # returns no errors — it just burns CPU\nprint(f\"{(time.perf_counter() - start):.0f}s\")\n```\n\nMeasured on GraphQL-core 3.2.8 / CPython 3.12 / Linux x86_64:\n\n| n | m | query size | validation time |\n|---|---|---|---|\n| 20 | 20 | 7.6 KB | 0.16 s |\n| 50 | 50 | 46 KB | 5.2 s |\n| 100 | 100 | 182 KB | 81 s |\n| 200 | 100 | 364 KB | **319 s** |\n\nDoubling `n` at fixed `m` quadruples the time, as expected for a quadratic outer loop\ndriving a quadratic inner walk.\n\n### Impact\n\nDenial of service. One request pins one worker process for minutes; because CPython\nholds the GIL for this pure-CPU work, a handful of concurrent requests can saturate a\ntypical multi-worker deployment. No authentication is required, and no data is\ndisclosed or modified.\n\n### Patches\n\nFixed in **3.2.12** and **3.3.0rc1**.\n\nValidation now enforces a per-document comparison budget. Once\n`MAX_FIELD_COMPARISONS` (default `250_000`) pairwise comparisons have been made, the\nrule aborts and reports a `GraphQLError` instead of running to completion:\n\n\u003e Query is too complex to validate for overlapping fields: exceeded 250000 field\n\u003e comparisons. Validation was aborted.\n\nThe default is far above what any realistic query reaches. It is a module-level\nconstant and can be raised or lowered:\n\n```python\nfrom graphql.validation.rules import overlapping_fields_can_be_merged\n\noverlapping_fields_can_be_merged.MAX_FIELD_COMPARISONS = 1_000_000\n```\n\nNote the behaviour change: a pathological query that previously validated — slowly —\nnow produces a validation error.\n\n### Workarounds\n\nIf you cannot upgrade, reject oversized documents before they reach `validate()`.\nNote that a request body-size limit must be applied to the **decompressed** body to be\neffective here, since the payload is highly compressible. Removing\n`OverlappingFieldsCanBeMergedRule` from the rule set is *not* a safe workaround: it is\na correctness rule required by the specification.\n\nA body-size limit remains worthwhile after upgrading — the comparison budget bounds\nthis specific rule, not overall request cost.\n\n### Credits\n\nReported by @BZHunt, who also reviewed the fixes\nbefore release. In memory of ZaX, who was the driving force behind this discovery.\n\nIndependently found and diagnosed by @bcmyguest, who\nalso proposed a fix.","aliases":["CVE-2026-75507"],"modified":"2026-10-22T16:45:03.746268085Z","published":"2026-10-22T16:26:40Z","database_specific":{"github_reviewed_at":"2026-10-22T16:26:40Z","nvd_published_at":null,"cwe_ids":["CWE-400","CWE-407"],"severity":"HIGH","github_reviewed":true},"references":[{"type":"WEB","url":"https://github.com/graphql-python/graphql-core/security/advisories/GHSA-vj8h-fx38-h3vc"},{"type":"WEB","url":"https://github.com/graphql-python/graphql-core/commit/150e59814d97d12140be005a558c93188ef89198"},{"type":"WEB","url":"https://github.com/graphql-python/graphql-core/commit/29c2753a7ee30a96a4109e7c6add1a2dae0497d7"},{"type":"PACKAGE","url":"https://github.com/graphql-python/graphql-core"},{"type":"WEB","url":"https://github.com/graphql-python/graphql-core/releases/tag/v3.2.12"},{"type":"WEB","url":"https://github.com/graphql-python/graphql-core/releases/tag/v3.3.0rc1"}],"affected":[{"package":{"name":"graphql-core","ecosystem":"PyPI","purl":"pkg:pypi/graphql-core"},"ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"3.0.0"},{"fixed":"3.2.12"}]}],"versions":["3.0.0","3.0.1","3.0.2","3.0.3","3.0.4","3.0.5","3.0.6","3.1.0","3.1.0b0","3.1.0b1","3.1.0b2","3.1.1","3.1.2","3.1.3","3.1.4","3.1.5","3.1.6","3.1.7","3.2.0","3.2.0rc1","3.2.0rc2","3.2.0rc3","3.2.0rc4","3.2.0rc5","3.2.1","3.2.10","3.2.11","3.2.2","3.2.3","3.2.4","3.2.5","3.2.6","3.2.7","3.2.8","3.2.9"],"database_specific":{"source":"https://github.com/github/advisory-database/blob/main/advisories/github-reviewed/2026/10/GHSA-vj8h-fx38-h3vc/GHSA-vj8h-fx38-h3vc.json"}},{"package":{"name":"graphql-core","ecosystem":"PyPI","purl":"pkg:pypi/graphql-core"},"ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"3.3.0a1"},{"fixed":"3.3.0rc1"}]}],"versions":["3.3.0a1","3.3.0a10","3.3.0a11","3.3.0a12","3.3.0a13","3.3.0a14","3.3.0a2","3.3.0a3","3.3.0a4","3.3.0a5","3.3.0a6","3.3.0a7","3.3.0a8","3.3.0a9","3.3.0b0","3.3.0b1","3.3.0b2","3.3.0rc0"],"database_specific":{"source":"https://github.com/github/advisory-database/blob/main/advisories/github-reviewed/2026/10/GHSA-vj8h-fx38-h3vc/GHSA-vj8h-fx38-h3vc.json"}}],"schema_version":"1.9.0","severity":[{"type":"CVSS_V3","score":"CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H"}]}