Common Weakness Enumeration

CWE-407

Allowed-with-Review

Inefficient Algorithmic Complexity

Abstraction: Class · Status: Incomplete

An algorithm in a product has an inefficient worst-case computational complexity that may be detrimental to system performance and can be triggered by an attacker, typically using crafted manipulations that ensure that the worst case is being reached.

584 vulnerabilities reference this CWE, most recent first.

GHSA-F8M6-WMRX-8VH2

Vulnerability from github – Published: 2026-10-14 15:32 – Updated: 2026-10-14 15:32
VLAI
Details

OW2 ASM 3.0 before 9.11 contains a quadratic memory allocation vulnerability in MethodWriter.computeMaxStackAndLocal() and computeAllFrames() when using COMPUTE_MAXS or COMPUTE_FRAMES. Attackers can supply a crafted class file with thousands of overlapping exception handlers, causing excessive Edge allocations and an OutOfMemoryError that crashes the JVM.

Show details on source website

{
  "affected": [],
  "aliases": [
    "CVE-2026-110260"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-407"
    ],
    "github_reviewed": false,
    "github_reviewed_at": null,
    "nvd_published_at": "2026-10-14T15:17:07Z",
    "severity": "MODERATE"
  },
  "details": "OW2 ASM 3.0 before 9.11 contains a quadratic memory allocation vulnerability in MethodWriter.computeMaxStackAndLocal() and computeAllFrames() when using COMPUTE_MAXS or COMPUTE_FRAMES. Attackers can supply a crafted class file with thousands of overlapping exception handlers, causing excessive Edge allocations and an OutOfMemoryError that crashes the JVM.",
  "id": "GHSA-f8m6-wmrx-8vh2",
  "modified": "2026-10-14T15:32:22Z",
  "published": "2026-10-14T15:32:22Z",
  "references": [
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2026-110260"
    },
    {
      "type": "WEB",
      "url": "https://asm.ow2.io/versions.html"
    },
    {
      "type": "WEB",
      "url": "https://gitlab.ow2.org/asm/asm/-/blob/ASM_9_10_1/asm/src/main/java/org/objectweb/asm/MethodWriter.java#L1662"
    },
    {
      "type": "WEB",
      "url": "https://gitlab.ow2.org/asm/asm/-/commit/91057c98239d994aed5e46434e34e00d593c0daf"
    },
    {
      "type": "WEB",
      "url": "https://gitlab.ow2.org/asm/asm/-/merge_requests/461"
    },
    {
      "type": "WEB",
      "url": "https://www.vulncheck.com/advisories/ow2-asm-3.0-before-9.11-quadratic-memory-allocation-via-exception-handlers"
    }
  ],
  "schema_version": "1.4.0",
  "severity": [
    {
      "score": "CVSS:3.1/AV:L/AC:L/PR:N/UI:R/S:U/C:N/I:N/A:H",
      "type": "CVSS_V3"
    },
    {
      "score": "CVSS:4.0/AV:L/AC:L/AT:N/PR:N/UI:P/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N/E:X/CR:X/IR:X/AR:X/MAV:X/MAC:X/MAT:X/MPR:X/MUI:X/MVC:X/MVI:X/MVA:X/MSC:X/MSI:X/MSA:X/S:X/AU:X/R:X/V:X/RE:X/U:X",
      "type": "CVSS_V4"
    }
  ]
}

GHSA-F9F8-XRCX-W6X5

Vulnerability from github – Published: 2026-11-13 12:31 – Updated: 2026-11-13 12:31
VLAI
Details

Scapy before 2.8.0 contains a denial of service vulnerability in BER_num_dec() and BERcodec_OID.do_dec() that allows remote attackers to exhaust CPU by supplying oversized OID arcs. Attackers can send ASN.1/BER data with many base-128 continuation bytes to cause quadratic CPU consumption or an uncaught ValueError crash on Python 3.11+.

Show details on source website

{
  "affected": [],
  "aliases": [
    "CVE-2026-128237"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-407"
    ],
    "github_reviewed": false,
    "github_reviewed_at": null,
    "nvd_published_at": "2026-11-13T10:18:11Z",
    "severity": "MODERATE"
  },
  "details": "Scapy before 2.8.0 contains a denial of service vulnerability in BER_num_dec() and BERcodec_OID.do_dec() that allows remote attackers to exhaust CPU by supplying oversized OID arcs. Attackers can send ASN.1/BER data with many base-128 continuation bytes to cause quadratic CPU consumption or an uncaught ValueError crash on Python 3.11+.",
  "id": "GHSA-f9f8-xrcx-w6x5",
  "modified": "2026-11-13T12:31:40Z",
  "published": "2026-11-13T12:31:40Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/secdev/scapy/security/advisories/GHSA-xx44-g48m-mjp6"
    },
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2026-128237"
    },
    {
      "type": "WEB",
      "url": "https://www.vulncheck.com/advisories/scapy-before-2.8.0-denial-of-service-via-quadratic-ber-oid-decoding"
    }
  ],
  "schema_version": "1.4.0",
  "severity": [
    {
      "score": "CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L",
      "type": "CVSS_V3"
    },
    {
      "score": "CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:L/SC:N/SI:N/SA:N/E:X/CR:X/IR:X/AR:X/MAV:X/MAC:X/MAT:X/MPR:X/MUI:X/MVC:X/MVI:X/MVA:X/MSC:X/MSI:X/MSA:X/S:X/AU:X/R:X/V:X/RE:X/U:X",
      "type": "CVSS_V4"
    }
  ]
}

GHSA-F9PM-GCPP-FWJP

Vulnerability from github – Published: 2026-09-07 15:33 – Updated: 2026-09-07 15:33
VLAI
Details

commonmark versions from 1.5.0 before 2.8.4 contain a denial of service vulnerability in the Attributes extension where AttributesListener::findTargetAndDirection() performs quadratic-time sibling list scanning. Unauthenticated attackers can submit approximately 32 KB of repeated attribute blocks to cause parsing to take over 5 seconds, exhausting server resources.

Show details on source website

{
  "affected": [],
  "aliases": [
    "CVE-2026-86433"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-407"
    ],
    "github_reviewed": false,
    "github_reviewed_at": null,
    "nvd_published_at": "2026-09-07T13:20:42Z",
    "severity": "HIGH"
  },
  "details": "commonmark versions from 1.5.0 before 2.8.4 contain a denial of service vulnerability in the Attributes extension where AttributesListener::findTargetAndDirection() performs quadratic-time sibling list scanning. Unauthenticated attackers can submit approximately 32 KB of repeated attribute blocks to cause parsing to take over 5 seconds, exhausting server resources.",
  "id": "GHSA-f9pm-gcpp-fwjp",
  "modified": "2026-09-07T15:33:53Z",
  "published": "2026-09-07T15:33:53Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/thephpleague/commonmark/security/advisories/GHSA-g2gp-3wwq-f4ph"
    },
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2026-86433"
    },
    {
      "type": "WEB",
      "url": "https://www.vulncheck.com/advisories/commonmark-1.5.0-before-2.8.4-denial-of-service-via-attributes"
    }
  ],
  "schema_version": "1.4.0",
  "severity": [
    {
      "score": "CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H",
      "type": "CVSS_V3"
    },
    {
      "score": "CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N/E:X/CR:X/IR:X/AR:X/MAV:X/MAC:X/MAT:X/MPR:X/MUI:X/MVC:X/MVI:X/MVA:X/MSC:X/MSI:X/MSA:X/S:X/AU:X/R:X/V:X/RE:X/U:X",
      "type": "CVSS_V4"
    }
  ]
}

GHSA-FC36-5GC3-JMHX

Vulnerability from github – Published: 2025-11-19 12:30 – Updated: 2025-11-19 12:30
VLAI
Details

Inefficient algorithm complexity in mjson in HAProxy allows remote attackers to cause a denial of service via specially crafted JSON requests.

Show details on source website

{
  "affected": [],
  "aliases": [
    "CVE-2025-11230"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-407"
    ],
    "github_reviewed": false,
    "github_reviewed_at": null,
    "nvd_published_at": "2025-11-19T10:15:45Z",
    "severity": "HIGH"
  },
  "details": "Inefficient algorithm complexity in mjson in HAProxy allows remote attackers to cause a denial of service via specially crafted JSON requests.",
  "id": "GHSA-fc36-5gc3-jmhx",
  "modified": "2025-11-19T12:30:20Z",
  "published": "2025-11-19T12:30:20Z",
  "references": [
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2025-11230"
    },
    {
      "type": "WEB",
      "url": "https://www.haproxy.com/blog/october-2025-cve-2025-11230-haproxy-mjson-library-denial-of-service-vulnerability"
    }
  ],
  "schema_version": "1.4.0",
  "severity": [
    {
      "score": "CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H",
      "type": "CVSS_V3"
    }
  ]
}

GHSA-FC86-6RV6-2JPM

Vulnerability from github – Published: 2026-05-04 22:22 – Updated: 2026-05-04 22:22
VLAI
Summary
webonyx/graphql-php has quadratic validation cost in OverlappingFieldsCanBeMerged via inline fragments
Details

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/graphql-php@v15.31.4 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/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 code path and are believed vulnerable but were not retested individually.

Remediation

Three options ordered from best to minimal:

Option 1 -- Adopt the Adameit algorithm

Replace 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 for the design discussion and the Sangria PR #12 for the original implementation.

Option 2 -- Comparison budget

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

Option 3 -- Cap inline-fragment flattening

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

Resources

Show details on source website

{
  "affected": [
    {
      "package": {
        "ecosystem": "Packagist",
        "name": "webonyx/graphql-php"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "15.32.2"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [],
  "database_specific": {
    "cwe_ids": [
      "CWE-407"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2026-05-04T22:22:09Z",
    "nvd_published_at": null,
    "severity": "HIGH"
  },
  "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(), \u0027getType\u0027], $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__.\u0027/vendor/autoload.php\u0027;\n\nuse GraphQL\\Language\\Parser;\nuse GraphQL\\Validator\\DocumentValidator;\nuse GraphQL\\Utils\\BuildSchema;\n\n$schema = BuildSchema::build(\u0027type Query { field: Node }  type Node { f: Node, g: Node, x: String }\u0027);\n\nfunction gen(int $n, int $m): string {\n    $inner = implode(\u0027 \u0027, array_fill(0, $m, \u0027... on Node { x }\u0027));\n    $outer = implode(\u0027 \u0027, 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).",
  "id": "GHSA-fc86-6rv6-2jpm",
  "modified": "2026-05-04T22:22:09Z",
  "published": "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"
    }
  ],
  "schema_version": "1.4.0",
  "severity": [
    {
      "score": "CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H",
      "type": "CVSS_V3"
    }
  ],
  "summary": "webonyx/graphql-php has quadratic validation cost in OverlappingFieldsCanBeMerged via inline fragments"
}

GHSA-FC8X-2RWW-XW9M

Vulnerability from github – Published: 2026-09-02 14:38 – Updated: 2026-09-02 14:38
VLAI
Summary
pypdf: Inefficient handling of non-whitespace inputs in read_until_whitespace
Details

Impact

An attacker who uses this vulnerability can craft a PDF which leads to long runtimes. This requires a call to read_until_whitespace with an input which does not have whitespace for a long time.

Patches

This has been fixed in pypdf==6.15.0.

Workarounds

If you cannot upgrade yet, consider applying the changes from PR #3947.

Show details on source website

{
  "affected": [
    {
      "package": {
        "ecosystem": "PyPI",
        "name": "pypdf"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "6.15.0"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [
    "CVE-2026-82398"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-407"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2026-09-02T14:38:12Z",
    "nvd_published_at": "2026-08-31T22:17:23Z",
    "severity": "MODERATE"
  },
  "details": "### Impact\nAn attacker who uses this vulnerability can craft a PDF which leads to long runtimes. This requires a call to `read_until_whitespace` with an input which does not have whitespace for a long time.\n\n### Patches\nThis has been fixed in [pypdf==6.15.0](https://github.com/py-pdf/pypdf/releases/tag/6.15.0).\n\n### Workarounds\nIf you cannot upgrade yet, consider applying the changes from PR [#3947](https://github.com/py-pdf/pypdf/pull/3947).",
  "id": "GHSA-fc8x-2rww-xw9m",
  "modified": "2026-09-02T14:38:12Z",
  "published": "2026-09-02T14:38:12Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/py-pdf/pypdf/security/advisories/GHSA-fc8x-2rww-xw9m"
    },
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2026-82398"
    },
    {
      "type": "WEB",
      "url": "https://github.com/py-pdf/pypdf/pull/3947"
    },
    {
      "type": "WEB",
      "url": "https://github.com/py-pdf/pypdf/commit/4959848e057e37c218dccad7465259210923faaa"
    },
    {
      "type": "PACKAGE",
      "url": "https://github.com/py-pdf/pypdf"
    },
    {
      "type": "WEB",
      "url": "https://github.com/py-pdf/pypdf/releases/tag/6.15.0"
    }
  ],
  "schema_version": "1.4.0",
  "severity": [
    {
      "score": "CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:L/SC:N/SI:N/SA:N",
      "type": "CVSS_V4"
    }
  ],
  "summary": "pypdf: Inefficient handling of non-whitespace inputs in read_until_whitespace"
}

GHSA-FC9G-5QG7-MF45

Vulnerability from github – Published: 2026-10-21 20:38 – Updated: 2026-10-21 20:38
VLAI
Summary
Pillow: Quadratic GIF comment copying during save
Details

On Pillow 12.3.0 and upstream main (ad277e2761b489681e71b51e91367d46b0ceabb9), a GIF with a long comment makes _get_global_header() copy portions of the comment repeatedly when saving, including comments carried over from untrusted images. I suggest provisional Moderate severity for crafted-image CPU denial of service, with CVSS-B 6.9 assuming a network service automatically opens unauthenticated uploads and they are resaved as GIFs; impact depends on input-size, concurrency, and worker CPU limits.

Show details on source website

{
  "affected": [
    {
      "package": {
        "ecosystem": "PyPI",
        "name": "pillow"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "9.2.0"
            },
            {
              "fixed": "13.0.0"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [
    "CVE-2026-112891"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-407"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2026-10-21T20:38:43Z",
    "nvd_published_at": "2026-10-19T22:17:08Z",
    "severity": "MODERATE"
  },
  "details": "On Pillow 12.3.0 and upstream `main` (`ad277e2761b489681e71b51e91367d46b0ceabb9`), a GIF with a long comment makes `_get_global_header()` copy portions of the comment repeatedly when saving, including comments carried over from untrusted images. I suggest provisional **Moderate** severity for crafted-image CPU denial of service, with CVSS-B 6.9 assuming a network service automatically opens unauthenticated uploads and they are resaved as GIFs; impact depends on input-size, concurrency, and worker CPU limits.",
  "id": "GHSA-fc9g-5qg7-mf45",
  "modified": "2026-10-21T20:38:43Z",
  "published": "2026-10-21T20:38:43Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/python-pillow/Pillow/security/advisories/GHSA-fc9g-5qg7-mf45"
    },
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2026-112891"
    },
    {
      "type": "WEB",
      "url": "https://github.com/python-pillow/Pillow/commit/68a3fe957d8a4d552e8c69d96066d749f0614c7e"
    },
    {
      "type": "PACKAGE",
      "url": "https://github.com/python-pillow/Pillow"
    },
    {
      "type": "WEB",
      "url": "https://github.com/python-pillow/Pillow/releases/tag/13.0.0"
    }
  ],
  "schema_version": "1.4.0",
  "severity": [
    {
      "score": "CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:L/SC:N/SI:N/SA:N",
      "type": "CVSS_V4"
    }
  ],
  "summary": "Pillow: Quadratic GIF comment copying during save"
}

GHSA-FCCG-MWVH-QQG4

Vulnerability from github – Published: 2026-09-08 18:14 – Updated: 2026-09-08 18:14
VLAI
Summary
Netty: Fragmented ClientHello records trigger quadratic pre-handshake reassembly in default SNI parsing
Details

Summary

Netty's default SNI entrypoint reparses and recopies previously received ClientHello fragments on every additional TLS handshake record. A remote peer can send a small first record that advertises a large ClientHello length and then drip the body in many tiny records, causing superlinear (quadratic) CPU work before the handshake completes. With 4095 one-byte fragments, the handler recopies 8,386,560 bytes from only 24,579 bytes on the wire — a 341× amplification ratio.

Affected Entrypoints

  • io.netty.handler.ssl.SniHandler — default constructors
  • io.netty.handler.ssl.SslClientHelloHandler — pre-handshake ClientHello aggregation path

Vulnerable Code Locations

  • handler/src/main/java/io/netty/handler/ssl/SniHandler.java:85
  • handler/src/main/java/io/netty/handler/ssl/SslClientHelloHandler.java:75 (decode entry)
  • handler/src/main/java/io/netty/handler/ssl/SslClientHelloHandler.java:165 (handshakeBuffer.clear)
  • handler/src/main/java/io/netty/handler/ssl/SslClientHelloHandler.java:174 (writeBytes re-copy)
  • codec-base/src/main/java/io/netty/handler/codec/ByteToMessageDecoder.java:294 (cumulation retention)

Exploit Path

1. TCP connection → SniHandler → SslClientHelloHandler.decode
2. First record: TLS handshake header declaring large ClientHello length (e.g., 4096 bytes)
3. Attacker sends thousands of tiny follow-on handshake records (1 byte each)
4. On each fragment: handshakeBuffer.clear() + writeBytes() re-copies ALL accumulated body bytes
5. Total bytes copied = n*(n+1)/2 where n = number of body bytes → quadratic
6. Event-loop CPU exhausted before SslHandler takes over

Impact

  • Vulnerability Type: Inefficient Algorithmic Complexity
  • An unauthenticated network attacker can drive disproportionate CPU consumption on the Netty event loop
  • Affects all Netty deployments using SniHandler for TLS termination (the default SNI path)
  • No privileges, user interaction, or special configuration required
  • Can degrade or stall TLS connection handling for all clients on the affected event loop
  • The attack requires only modest bandwidth (~25 KB) to trigger significant CPU work

Credits

Found by a security research team from the University of Sydney, focusing on detecting open source software vulnerabilities. Liyi Zhou: https://lzhou1110.github.io/ Ziyue Wang: https://zyy0530.github.io/ Strick: https://str1ckl4nd.github.io/ Maurice: https://maurice.busystar.org/ Chenchen Yu: https://7thparkk.github.io/

Show details on source website

{
  "affected": [
    {
      "database_specific": {
        "last_known_affected_version_range": "\u003c= 4.2.16.Final"
      },
      "package": {
        "ecosystem": "Maven",
        "name": "io.netty:netty-handler"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "4.2.0.Final"
            },
            {
              "fixed": "4.2.17.Final"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    },
    {
      "database_specific": {
        "last_known_affected_version_range": "\u003c= 4.1.136.Final"
      },
      "package": {
        "ecosystem": "Maven",
        "name": "io.netty:netty-handler"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "4.1.137.Final"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [
    "CVE-2026-75596"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-407"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2026-09-08T18:14:56Z",
    "nvd_published_at": "2026-08-19T21:17:37Z",
    "severity": "MODERATE"
  },
  "details": "### Summary\n\nNetty\u0027s default SNI entrypoint reparses and recopies previously received ClientHello fragments on every additional TLS handshake record. A remote peer can send a small first record that advertises a large ClientHello length and then drip the body in many tiny records, causing **superlinear (quadratic) CPU work** before the handshake completes. With 4095 one-byte fragments, the handler recopies **8,386,560 bytes** from only **24,579 bytes** on the wire \u2014 a **341\u00d7 amplification** ratio.\n\n### Affected Entrypoints\n\n- `io.netty.handler.ssl.SniHandler` \u2014 default constructors\n- `io.netty.handler.ssl.SslClientHelloHandler` \u2014 pre-handshake ClientHello aggregation path\n\n### Vulnerable Code Locations\n\n- `handler/src/main/java/io/netty/handler/ssl/SniHandler.java:85`\n- `handler/src/main/java/io/netty/handler/ssl/SslClientHelloHandler.java:75` (decode entry)\n- `handler/src/main/java/io/netty/handler/ssl/SslClientHelloHandler.java:165` (handshakeBuffer.clear)\n- `handler/src/main/java/io/netty/handler/ssl/SslClientHelloHandler.java:174` (writeBytes re-copy)\n- `codec-base/src/main/java/io/netty/handler/codec/ByteToMessageDecoder.java:294` (cumulation retention)\n\n### Exploit Path\n\n```\n1. TCP connection \u2192 SniHandler \u2192 SslClientHelloHandler.decode\n2. First record: TLS handshake header declaring large ClientHello length (e.g., 4096 bytes)\n3. Attacker sends thousands of tiny follow-on handshake records (1 byte each)\n4. On each fragment: handshakeBuffer.clear() + writeBytes() re-copies ALL accumulated body bytes\n5. Total bytes copied = n*(n+1)/2 where n = number of body bytes \u2192 quadratic\n6. Event-loop CPU exhausted before SslHandler takes over\n```\n\n### Impact\n\n- **Vulnerability Type:** Inefficient Algorithmic Complexity\n- An unauthenticated network attacker can drive disproportionate CPU consumption on the Netty event loop\n- Affects **all** Netty deployments using `SniHandler` for TLS termination (the default SNI path)\n- No privileges, user interaction, or special configuration required\n- Can degrade or stall TLS connection handling for all clients on the affected event loop\n- The attack requires only modest bandwidth (~25 KB) to trigger significant CPU work\n\n---\n### Credits\n\nFound by a security research team from the University of Sydney, focusing on detecting open source software vulnerabilities.\nLiyi Zhou: https://lzhou1110.github.io/\nZiyue Wang: https://zyy0530.github.io/\nStrick: https://str1ckl4nd.github.io/\nMaurice: https://maurice.busystar.org/\nChenchen Yu: https://7thparkk.github.io/",
  "id": "GHSA-fccg-mwvh-qqg4",
  "modified": "2026-09-08T18:14:56Z",
  "published": "2026-09-08T18:14:56Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/netty/netty/security/advisories/GHSA-fccg-mwvh-qqg4"
    },
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2026-75596"
    },
    {
      "type": "WEB",
      "url": "https://github.com/netty/netty/pull/17213"
    },
    {
      "type": "WEB",
      "url": "https://github.com/netty/netty/pull/17217"
    },
    {
      "type": "WEB",
      "url": "https://github.com/netty/netty/commit/1b5abc6443b63726c72cdd285af2feb7ddbb8ff7"
    },
    {
      "type": "WEB",
      "url": "https://github.com/netty/netty/commit/9e0519239108a69b7e9bbc5e9182ee139a0d7961"
    },
    {
      "type": "PACKAGE",
      "url": "https://github.com/netty/netty"
    },
    {
      "type": "WEB",
      "url": "https://github.com/netty/netty/releases/tag/netty-4.1.137.Final"
    },
    {
      "type": "WEB",
      "url": "https://github.com/netty/netty/releases/tag/netty-4.2.17.Final"
    }
  ],
  "schema_version": "1.4.0",
  "severity": [
    {
      "score": "CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:L/SC:N/SI:N/SA:N",
      "type": "CVSS_V4"
    }
  ],
  "summary": "Netty: Fragmented ClientHello records trigger quadratic pre-handshake reassembly in default SNI parsing"
}

GHSA-FF2V-F99F-WM3F

Vulnerability from github – Published: 2026-07-29 15:31 – Updated: 2026-07-29 15:31
VLAI
Details

cJSON through 1.7.19 contains an inefficient algorithmic complexity flaw in cJSON_Compare(). When comparing objects, the function recurses into each shared subtree twice, once in each direction, with no depth guard, making the running time exponential in nesting depth. A small, deeply nested document of a few hundred bytes (depth around 40) compared for equality consumes hours of CPU, and the cost roughly doubles with each additional level of nesting. An application that calls cJSON_Compare() on attacker-influenced JSON that is structurally equal to a reference document is exposed to a denial-of-service condition.

Show details on source website

{
  "affected": [],
  "aliases": [
    "CVE-2026-67216"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-407"
    ],
    "github_reviewed": false,
    "github_reviewed_at": null,
    "nvd_published_at": "2026-07-29T14:16:35Z",
    "severity": "HIGH"
  },
  "details": "cJSON through 1.7.19 contains an inefficient algorithmic complexity flaw in cJSON_Compare(). When comparing objects, the function recurses into each shared subtree twice, once in each direction, with no depth guard, making the running time exponential in nesting depth. A small, deeply nested document of a few hundred bytes (depth around 40) compared for equality consumes hours of CPU, and the cost roughly doubles with each additional level of nesting. An application that calls cJSON_Compare() on attacker-influenced JSON that is structurally equal to a reference document is exposed to a denial-of-service condition.",
  "id": "GHSA-ff2v-f99f-wm3f",
  "modified": "2026-07-29T15:31:12Z",
  "published": "2026-07-29T15:31:12Z",
  "references": [
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2026-67216"
    },
    {
      "type": "WEB",
      "url": "https://github.com/DaveGamble/cJSON/blob/v1.7.19/cJSON.c#L3057-L3180"
    },
    {
      "type": "WEB",
      "url": "https://joshua.hu/cjson-json-parser-cve-vulnerabilities"
    },
    {
      "type": "WEB",
      "url": "https://www.vulncheck.com/advisories/cjson-cjson-compare-exponential-complexity-denial-of-service"
    }
  ],
  "schema_version": "1.4.0",
  "severity": [
    {
      "score": "CVSS:3.1/AV:N/AC:H/PR:N/UI:N/S:U/C:N/I:N/A:H",
      "type": "CVSS_V3"
    },
    {
      "score": "CVSS:4.0/AV:N/AC:L/AT:P/PR:N/UI:N/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N/E:X/CR:X/IR:X/AR:X/MAV:X/MAC:X/MAT:X/MPR:X/MUI:X/MVC:X/MVI:X/MVA:X/MSC:X/MSI:X/MSA:X/S:X/AU:X/R:X/V:X/RE:X/U:X",
      "type": "CVSS_V4"
    }
  ]
}

GHSA-FF5C-CP5C-9WJF

Vulnerability from github – Published: 2026-09-02 14:33 – Updated: 2026-09-02 14:33
VLAI
Summary
NLTK: Uncontrolled resource consumption in RecursiveDescentParser via ambiguous or left-recursive grammars
Details

nltk.parse.RecursiveDescentParser (and SteppingRecursiveDescentParser) enumerate parses top-down with no bound on the number of recursive steps. A small, crafted context-free grammar makes a short input consume unbounded CPU (and/or exhaust the Python recursion stack), pinning a process indefinitely — a denial of service.

Proof of concept

Both of the following hang on a 24-token input (killed after 8s; growth is super-linear in input length), on NLTK develop:

from nltk import CFG
from nltk.parse import RecursiveDescentParser

# (a) left recursion -> unbounded recursion
g = CFG.fromstring("S -> S S | 'a'")
list(RecursiveDescentParser(g).parse(["a"] * 24))   # hangs

# (b) ambiguous grammar -> exponential number of parses
g = CFG.fromstring("S -> 'a' S | 'a' S S | 'a'")
list(RecursiveDescentParser(g).parse(["a"] * 24))   # hangs

Impact

An application that runs RecursiveDescentParser on a grammar (or an input) drawn from an untrusted source can be driven into an unbounded CPU / stack-exhaustion loop by a tiny payload. No confidentiality or integrity impact; single-process availability only.

Sibling

The RegexpTokenizer ReDoS reported alongside this (CVE-2026-12875) is a different class (caller-supplied regex) and is addressed under GHSA-w3v8-gmh9-3wv7.

Show details on source website

{
  "affected": [
    {
      "database_specific": {
        "last_known_affected_version_range": "\u003c= 3.10.2"
      },
      "package": {
        "ecosystem": "PyPI",
        "name": "nltk"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "3.10.3"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [
    "CVE-2026-12876"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-407",
      "CWE-674"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2026-09-02T14:33:38Z",
    "nvd_published_at": null,
    "severity": "MODERATE"
  },
  "details": "`nltk.parse.RecursiveDescentParser` (and `SteppingRecursiveDescentParser`) enumerate parses top-down with no bound on the number of recursive steps. A small, crafted context-free grammar makes a short input consume unbounded CPU (and/or exhaust the Python recursion stack), pinning a process indefinitely \u2014 a denial of service.\n\n## Proof of concept\n\nBoth of the following hang on a 24-token input (killed after 8s; growth is super-linear in input length), on NLTK develop:\n\n```python\nfrom nltk import CFG\nfrom nltk.parse import RecursiveDescentParser\n\n# (a) left recursion -\u003e unbounded recursion\ng = CFG.fromstring(\"S -\u003e S S | \u0027a\u0027\")\nlist(RecursiveDescentParser(g).parse([\"a\"] * 24))   # hangs\n\n# (b) ambiguous grammar -\u003e exponential number of parses\ng = CFG.fromstring(\"S -\u003e \u0027a\u0027 S | \u0027a\u0027 S S | \u0027a\u0027\")\nlist(RecursiveDescentParser(g).parse([\"a\"] * 24))   # hangs\n```\n\n## Impact\n\nAn application that runs `RecursiveDescentParser` on a grammar (or an input) drawn from an untrusted source can be driven into an unbounded CPU / stack-exhaustion loop by a tiny payload. No confidentiality or integrity impact; single-process availability only.\n\n## Sibling\n\nThe RegexpTokenizer ReDoS reported alongside this (CVE-2026-12875) is a different class (caller-supplied regex) and is addressed under GHSA-w3v8-gmh9-3wv7.",
  "id": "GHSA-ff5c-cp5c-9wjf",
  "modified": "2026-09-02T14:33:39Z",
  "published": "2026-09-02T14:33:38Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/nltk/nltk/security/advisories/GHSA-ff5c-cp5c-9wjf"
    },
    {
      "type": "WEB",
      "url": "https://github.com/nltk/nltk/pull/3649"
    },
    {
      "type": "WEB",
      "url": "https://github.com/nltk/nltk/commit/43aaca1b9024138421c97f970bf13ee19ac8129d"
    },
    {
      "type": "PACKAGE",
      "url": "https://github.com/nltk/nltk"
    },
    {
      "type": "WEB",
      "url": "https://github.com/nltk/nltk/releases/tag/v3.10.3"
    }
  ],
  "schema_version": "1.4.0",
  "severity": [
    {
      "score": "CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:L/SC:N/SI:N/SA:N",
      "type": "CVSS_V4"
    }
  ],
  "summary": "NLTK: Uncontrolled resource consumption in RecursiveDescentParser via ambiguous or left-recursive grammars"
}

No mitigation information available for this CWE.

No CAPEC attack patterns related to this CWE.