GHSA-FC86-6RV6-2JPM: Denial of Service via Algorithmic Complexity in webonyx/graphql-php

The webonyx/graphql-php library provides a comprehensive PHP implementation of the GraphQL specification. It handles query parsing, validation, and execution. The vulnerability exists within the pre-execution query validation phase, specifically in the logic responsible for ensuring that overlapping fields within a selection set can be safely merged in the response.

According to the GraphQL specification, any two fields in a selection set that share the same response name must have identical arguments and compatible return types. The library enforces this via the OverlappingFieldsCanBeMerged rule. Validation occurs before query execution, meaning any complexity limits applied to execution resolvers do not protect the validation step.

This flaw is classified under CWE-400: Uncontrolled Resource Consumption. An unauthenticated attacker can submit a relatively small, structurally complex query that forces the server into prolonged computation. This algorithmic complexity results in CPU exhaustion, effectively creating a Denial of Service (DoS) condition against the application.

The root cause of this vulnerability lies in the pairwise comparison strategy used by the OverlappingFieldsCanBeMerged rule. To enforce the specification, the validator must compare every field against every other field that shares the same output name within a given selection set. The original implementation included a memoization cache (comparedFragmentPairs) to optimize comparisons involving named fragments.

However, the cache mechanism was not applied to inline fragments. Because inline fragments are anonymous by nature, the validator flattened them directly into the parent selection set during processing. This flattening bypassed the optimization logic entirely. Consequently, the validator processed these inline fragments repeatedly for every level of nesting.

For a selection set containing $N$ fields, the mathematical complexity of the validation is $O(N^2)$. When inline fragments are deeply nested, the operation scales up to $O(N^2 \times M^2)$, where $M$ represents the depth of the sub-selections. This non-linear scaling allows a small input payload to trigger millions of recursive comparison operations.

Prior to version 15.32.2, the findConflict method in OverlappingFieldsCanBeMerged.php performed unbounded recursion. It compared field definitions and their sub-selections without tracking the total number of operations performed across the entire validation run. The lack of an upper bound meant the PHP process would continue execution until memory limits were exceeded or the client disconnected, though the CPU consumption would persist until the script timed out.

The fix implemented in commit 996adcfce33442f6fc01214777bc8620cc142d85 introduces a strict resource budget directly into the validation class. A new constant, DEFAULT_MAX_COMPARISON_COUNT, establishes a ceiling of 100,000 comparisons. A stateful counter tracks the number of times findConflict is invoked during a single validation pass.

protected function findConflict(
    string $responseName,
    array $field1,
    array $field2
): ?array {
    if (++$this->comparisonCount > $this->comparisonLimit) {
        return [
            [$responseName, 'Too many field comparisons, query is too complex to validate'],
            [$field1[1]],
            [$field2[1]],
        ];
    }
    // ... original comparison logic
}

When the threshold is breached, the method immediately returns a validation error, short-circuiting the deep recursion. While this mitigates the primary CPU exhaustion vector, researchers note that loop overhead remains in the caller functions (collectConflictsWithin and collectConflictsBetween). A substantial volume of top-level fields can still incur performance costs even with the early return.

Exploitation requires no specialized access or authentication if the GraphQL endpoint is publicly exposed. The attacker only needs network access to submit HTTP POST requests containing the malicious payload. The attack vector focuses on structure over size, generating a payload well under one megabyte to evade standard Web Application Firewall (WAF) request size limits.

The attack payload leverages repeated inline fragments to force the vulnerability. The following PHP snippet demonstrates how an attacker dynamically constructs the Proof-of-Concept query. By nesting 100 inner fragments within 100 outer fragments, the resulting query expands exponentially during the validation phase.

$innerFragments = implode(' ', array_fill(0, 100, '... on Node { x }'));
$outerFragments = implode(' ', array_fill(0, 100, "... on Node { f { {$innerFragments} } }"));
$query = "{ field { {$outerFragments} } }";

Upon receiving this query, the GraphQL server parses the document and initiates the validation rules. The OverlappingFieldsCanBeMerged rule enters the unoptimized processing loop. A single request generated by the script above initiates tens of thousands of field comparisons, maximizing CPU utilization for the handling PHP worker process. Concurrent requests will quickly exhaust the worker pool, resulting in application unresponsiveness.

The impact of this vulnerability is isolated entirely to system availability. An attacker cannot achieve remote code execution, alter data, or extract sensitive information. However, the asymmetric nature of the attack requires minimal bandwidth and computational effort from the attacker while inflicting a severe penalty on the target infrastructure.

When successfully exploited, the vulnerable PHP process consumes 100% of its assigned CPU core. Because typical PHP environments (such as PHP-FPM) manage a finite pool of worker processes, a small batch of parallel requests will saturate the pool. Legitimate user requests will queue and eventually time out, resulting in a widespread Denial of Service condition.

The calculated CVSS v3.1 vector is CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H, reflecting a base score of 7.5. The attack is executable over the network without privileges or user interaction. The high availability impact underscores the risk to production environments operating unpatched versions of the library.

The definitive remediation is upgrading the webonyx/graphql-php library to version 15.32.2 or later. This release introduces the comparisonLimit check that bounds the algorithmic complexity. Organizations using Composer for dependency management should update their composer.lock file and deploy the patched vendor package.

For environments where immediate patching is not feasible, security engineers can implement compensating controls. The library allows custom limits to be injected into validation rules. Developers can initialize the OverlappingFieldsCanBeMerged rule with a lower threshold, such as 50,000, to restrict computation further depending on expected traffic complexity.

Additionally, defense-in-depth measures should be applied globally at the application level. Implementing strict query depth limits and query complexity analysis before validation will reject malicious structures early. Web Application Firewalls can also be configured to drop payloads containing excessive repetition of the string ... on, further reducing the attack surface.