graphql-php is affected by a Denial of Service via quadratic complexity in OverlappingFieldsCanBeMerged validation
The advisory, in context
The OverlappingFieldsCanBeMerged validation rule exhibits quadratic time complexity when processing queries with many repeated fields sharing the same response name. An attacker can send a crafted query like { hello hello hello ... } with thousands of repeated fields, causing excessive CPU usage during validation before execution begins.
This is not mitigated by existing QueryDepth or QueryComplexity rules.
Observed impact (tested on v15.31.4):
- 1000 fields: ~0.6s
- 2000 fields: ~2.4s
- 3000 fields: ~5.3s
- 5000 fields: request timeout (>20s)
Root cause: collectConflictsWithin() performs O(n²) pairwise comparisons of all fields with the same response name. For identical repeated fields, every comparison returns "no conflict" but the quadratic iteration count causes resource exhaustion.
Fix: Deduplicate structurally identical fields before pairwise comparison, reducing the complexity from O(n²) to O(u²) where u is the number of unique field signatures (typically 1 for this attack pattern).
Credit: Ashwak N (ashwakn04@gmail.com)
Affected packages
Start with the recorded fix for your release branch. Check your installed version and test compatibility before upgrading. Fixing this advisory does not rule out other vulnerabilities in the release.
Earlier releases before 15.31.5
Fixed in 15.31.5
186 explicitly affected 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.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
View affected-version evidence
{
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"fixed": "15.31.5"
}
],
"type": "ECOSYSTEM"
}
],
"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.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"
]
}