GraphQL-core: Denial of service via quadratic complexity in the OverlappingFieldsCanBeMerged validation rule

Summary

The OverlappingFieldsCanBeMerged validation rule can be driven into quadratic — and in the worst case O(n²·m²) — running time by a small, highly compressible query. A single 364 KB document can occupy one CPU core for over five minutes during validation, before any resolver runs. Because the rule is part of specified_rules and therefore enabled by default, every GraphQL-core based server is affected at default settings.

Details

OverlappingFieldsCanBeMerged compares every pair of fields that share a response name and recurses into their sub-selections. The memoization added for CVE-2023-26144 (GHSA-9pv7-vfvm-6vr7) is keyed by named fragment identity, so it does not cover this path: inline fragments are flattened into the parent selection set before the cache is consulted, and therefore every pair is re-compared from scratch at every nesting level.

Repeating an inline fragment that selects the same response name at two nesting levels multiplies the two effects. There was no comparison budget and no validation timeout, so the rule ran to completion regardless of cost.

The cost is incurred in the validation phase, which is what makes this hard to defend against from outside the library: query-depth limiters, complexity analyzers and cost estimators all operate on the parsed document after validation, and the malicious document is trivially shallow (depth 3, complexity 1). The payload is also one short string repeated many times, so it compresses to a few kilobytes and slips past body-size limits and WAF inspection that only see the compressed request.

Proof of concept

import time
from graphql import build_schema, parse, validate

schema = build_schema(
    "type Query { field: Node } type Node { f: Node, g: Node, x: String }"
)

def gen(n: int, m: int) -> str:
    inner = " ".join(["... on Node { x }"] * m)
    outer = " ".join([f"... on Node {{ f {{ {inner} }} }}"] * n)
    return f"{{ field {{ {outer} }} }}"

query = gen(200, 100)          # 364 KB, gzips to a few KB
document = parse(query)
start = time.perf_counter()
validate(schema, document)      # returns no errors — it just burns CPU
print(f"{(time.perf_counter() - start):.0f}s")

Measured on GraphQL-core 3.2.8 / CPython 3.12 / Linux x86_64:

n	m	query size	validation time
20	20	7.6 KB	0.16 s
50	50	46 KB