Skip to content

Commit 29c2753

Browse files
committed
fix: bound OverlappingFieldsCanBeMerged validation to prevent quadratic DoS
The rule compares every pair of fields sharing a response name and recurses into their sub-selections — O(n^2), and worse when inline fragments repeat the same response name at multiple nesting levels — so a crafted query could burn minutes of CPU during validation on a single request. Add a per-document comparison budget (MAX_FIELD_COMPARISONS, default 250000, an overridable module constant) that aborts validation with a GraphQLError once exhausted. Realistic queries stay far below the limit.
1 parent 090141f commit 29c2753

2 files changed

Lines changed: 150 additions & 10 deletions

File tree

‎src/graphql/validation/rules/overlapping_fields_can_be_merged.py‎

Lines changed: 59 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -32,7 +32,27 @@
3232

3333
MYPY = False
3434

35-
__all__ = ["OverlappingFieldsCanBeMergedRule"]
35+
__all__ = ["MAX_FIELD_COMPARISONS", "OverlappingFieldsCanBeMergedRule"]
36+
37+
# The maximum number of pairwise field comparisons performed while validating a
38+
# single document with the OverlappingFieldsCanBeMerged rule. The rule compares
39+
# every pair of fields that share a response name and recurses into their
40+
# sub-selections, which is O(n^2) in the number of such fields (and worse when
41+
# inline fragments repeat the same response name at multiple nesting levels). A
42+
# crafted query can therefore drive validation into minutes of CPU on a single
43+
# request. Once this many comparisons have been made, validation is aborted with a
44+
# GraphQLError instead of running to completion. The default is high enough that any
45+
# realistic query stays far below it; it can be raised or lowered by assigning to
46+
# ``graphql.validation.rules.overlapping_fields_can_be_merged.MAX_FIELD_COMPARISONS``.
47+
MAX_FIELD_COMPARISONS = 250_000
48+
49+
50+
class ComparisonBudgetExceededError(Exception):
51+
"""Internal signal that the field-comparison budget has been exhausted.
52+
53+
Raised deep inside the recursive conflict search and caught by the rule to abort
54+
validation. Never surfaces to callers of ``validate``.
55+
"""
3656

3757

3858
def reason_message(reason: "ConflictReasonMessage") -> str:
@@ -67,15 +87,33 @@ def __init__(self, context: ValidationContext):
6787
# times, so this improves the performance of this validator.
6888
self.cached_fields_and_fragment_names: Dict = {}
6989

90+
# Set once the comparison budget is exhausted. Further selection sets are then
91+
# skipped, since validation has already been aborted with an error.
92+
self._budget_exceeded = False
93+
7094
def enter_selection_set(self, selection_set: SelectionSetNode, *_args: Any) -> None:
71-
conflicts = find_conflicts_within_selection_set(
72-
self.context,
73-
self.cached_fields_and_fragment_names,
74-
self.compared_fields_and_fragment_pairs,
75-
self.compared_fragment_pairs,
76-
self.context.get_parent_type(),
77-
selection_set,
78-
)
95+
if self._budget_exceeded:
96+
return
97+
try:
98+
conflicts = find_conflicts_within_selection_set(
99+
self.context,
100+
self.cached_fields_and_fragment_names,
101+
self.compared_fields_and_fragment_pairs,
102+
self.compared_fragment_pairs,
103+
self.context.get_parent_type(),
104+
selection_set,
105+
)
106+
except ComparisonBudgetExceededError:
107+
self._budget_exceeded = True
108+
self.report_error(
109+
GraphQLError(
110+
"Query is too complex to validate for overlapping fields:"
111+
f" exceeded {MAX_FIELD_COMPARISONS} field comparisons."
112+
" Validation was aborted.",
113+
selection_set,
114+
)
115+
)
116+
return
79117
for (reason_name, reason), fields1, fields2 in conflicts:
80118
reason_msg = reason_message(reason)
81119
self.report_error(
@@ -544,6 +582,12 @@ def find_conflict(
544582
Determines if there is a conflict between two particular fields, including comparing
545583
their sub-fields.
546584
"""
585+
# Charge this comparison against the document-wide budget and abort validation once
586+
# it is exhausted, guarding against quadratic-blowup denial of service.
587+
compared_fields_and_fragment_pairs.comparisons += 1
588+
if compared_fields_and_fragment_pairs.comparisons > MAX_FIELD_COMPARISONS:
589+
raise ComparisonBudgetExceededError
590+
547591
parent_type1, node1, def1 = field1
548592
parent_type2, node2, def2 = field2
549593

@@ -780,14 +824,19 @@ class OrderedPairSet:
780824
781825
The first element is matched by object identity (its ``id``), since field maps
782826
are unhashable mappings that are kept alive for the duration of the validation.
827+
828+
Also carries a running count of the pairwise field comparisons performed with
829+
this set, used to enforce the OverlappingFieldsCanBeMerged comparison budget.
783830
"""
784831

785-
__slots__ = ("_data",)
832+
__slots__ = ("_data", "comparisons")
786833

787834
_data: Dict[int, Dict[str, bool]]
835+
comparisons: int
788836

789837
def __init__(self) -> None:
790838
self._data = {}
839+
self.comparisons = 0
791840

792841
def has(self, a: NodeAndDefCollection, b: str, weakly_present: bool) -> bool:
793842
map_ = self._data.get(id(a))

‎tests/validation/test_overlapping_fields_can_be_merged.py‎

Lines changed: 91 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,14 +1,42 @@
1+
from contextlib import contextmanager
12
from functools import partial
23

34
from graphql.utilities import build_schema
45
from graphql.validation import OverlappingFieldsCanBeMergedRule
6+
from graphql.validation.rules import (
7+
overlapping_fields_can_be_merged as overlapping_module,
8+
)
59

610
from .harness import assert_validation_errors
711

812
assert_errors = partial(assert_validation_errors, OverlappingFieldsCanBeMergedRule)
913

1014
assert_valid = partial(assert_errors, errors=[])
1115

16+
budget_schema = build_schema("""
17+
type Query {
18+
field: Node
19+
other: Node
20+
}
21+
22+
type Node {
23+
f: Node
24+
x: String
25+
}
26+
""")
27+
28+
29+
@contextmanager
30+
def budget_of(limit):
31+
# Temporarily lower the module-level comparison budget so the budget tests can
32+
# trigger the guard with small, fast queries.
33+
saved = overlapping_module.MAX_FIELD_COMPARISONS
34+
overlapping_module.MAX_FIELD_COMPARISONS = limit
35+
try:
36+
yield
37+
finally:
38+
overlapping_module.MAX_FIELD_COMPARISONS = saved
39+
1240

1341
def describe_validate_overlapping_fields_can_be_merged():
1442
def unique_fields():
@@ -1193,3 +1221,66 @@ def does_not_infinite_loop_on_recursive_fragments_separated_by_fields():
11931221
}
11941222
}
11951223
""")
1224+
1225+
def describe_comparison_budget():
1226+
def aborts_validation_when_the_comparison_budget_is_exceeded():
1227+
# Repeated inline fragments select the same response name, forcing O(n^2)
1228+
# pairwise comparisons. Once the budget is exhausted the rule aborts with
1229+
# a single error instead of running the comparison to completion. The
1230+
# trailing `other` selection set is visited after the abort and must be
1231+
# skipped, so exactly one error is reported for the whole document.
1232+
query = (
1233+
"{ field { " + " ".join(["... on Node { x }"] * 10) + " } other { x } }"
1234+
)
1235+
with budget_of(5):
1236+
assert_errors(
1237+
query,
1238+
[
1239+
{
1240+
"message": "Query is too complex to validate for"
1241+
" overlapping fields: exceeded 5 field comparisons."
1242+
" Validation was aborted."
1243+
}
1244+
],
1245+
schema=budget_schema,
1246+
)
1247+
1248+
def deduplication_alone_would_not_bound_this_query():
1249+
# Each `f` selection shares the response name `f` but wraps a distinct
1250+
# sub-selection (`a0: x`, `a1: x`, ...), so every field has a distinct
1251+
# structural fingerprint and none conflicts with another (differing
1252+
# aliases merge cleanly). A fix based purely on deduplicating structurally
1253+
# identical fields cannot remove any of these, so it would still perform
1254+
# O(n^2) comparisons; the comparison budget bounds the work regardless.
1255+
query = (
1256+
"{ field { "
1257+
+ " ".join(f"... on Node {{ f {{ a{i}: x }} }}" for i in range(20))
1258+
+ " } }"
1259+
)
1260+
# With a generous budget the query is valid, proving the fields do not
1261+
# conflict and that no deduplication pass could collapse them.
1262+
with budget_of(1_000_000):
1263+
assert_valid(query, schema=budget_schema)
1264+
# With a small budget the same query is aborted rather than validated in
1265+
# quadratic time.
1266+
with budget_of(10):
1267+
assert_errors(
1268+
query,
1269+
[
1270+
{
1271+
"message": "Query is too complex to validate for"
1272+
" overlapping fields: exceeded 10 field comparisons."
1273+
" Validation was aborted."
1274+
}
1275+
],
1276+
schema=budget_schema,
1277+
)
1278+
1279+
def does_not_abort_queries_that_stay_within_the_budget():
1280+
# A valid overlapping query well under the budget validates normally, with
1281+
# no spurious abort error.
1282+
with budget_of(50):
1283+
assert_valid(
1284+
"{ field { ... on Node { x } ... on Node { x } } }",
1285+
schema=budget_schema,
1286+
)

0 commit comments

Comments
 (0)