NLTK: Quadratic-time CPU denial of service in Tree.chomsky_normal_form right-factor binarization via list.pop(0)

Exploitation

No confirmed exploitation recorded. Patch Next marks exploitation only from CISA KEV.

CVSS

7.5 · CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H

EPSS

• CVE-2026-126298: 0.58% estimated exploitation activity in the next 30 days; percentile 48.34 (FIRST EPSS, 2026-11-13). This is a model estimate, not proof of exploitation or customer exposure.

As published by the source; long descriptions are shortened.

Summary `Tree.chomsky_normal_form()` binarizes a parse tree and defaults to right factoring. For a node with N children the right-factor branch repeatedly removes the first element of a working list with `list.pop(0)`, which shifts all remaining elements each time, so binarizing one wide node costs O(N^2). An application that converts an attacker-supplied treebank tree to Chomsky Normal Form can be forced into tens of seconds of single-threaded CPU by one wide flat tree. No authentication or user interaction is required.

Root Cause In the default right-factor branch the transform executes `curNode[0:] = [nodeCopy.pop(0), newNode]` inside a loop over the N children of a node. `list.pop(0)` is O(len) because it shifts every remaining element down by one; performed N-2 times over a shrinking length-N list this sums to O(N^2). The left-factor branch instead uses `nodeCopy.pop()` (removing the last element), which is O(1) and linear overall, so the two branches differ only by this…

Published by the source

14 Nov 2026, 00:07 UTC

Last modified by the source

14 Nov 2026, 00:15 UTC

Source last checked

14 Nov 2026, 07:50 UTC

1. Revision 2 · amended · 14 Nov 2026

   Amended from osv record GHSA-r53h-rw34-8h97

2. Revision 1 · created · 14 Nov 2026

   Published from ghsa record GHSA-r53h-rw34-8h97

Preview the exact text before you copy it. Commands are read-only suggestions; review them before running anything.

# Patch Next advisory brief: CVE-2026-126298

Advisory: NLTK: Quadratic-time CPU denial of service in Tree.chomsky_normal_form right-factor binarization via list.pop(0)
IDs: CVE-2026-126298, GHSA-r53h-rw34-8h97
Record: https://patchnext.com/advisories/cve-2026-126298 (revision 2, source checked 14 Nov 2026, 07:50 UTC)
Inventory: none attached. This brief comes from a public page and does not say whether any deployment is affected.
Severity: High (CVSS 7.5)
Exploitation: no confirmed exploitation recorded. Patch Next confirms exploitation only from CISA KEV.
Vendor response: Vendor fix available; fixed versions by package: nltk 3.10.4. A vendor fix does not mean a deployment is fixed.

## Affected components
- PyPI nltk: affected < 3.10.4; fixed in 3.10.4

## Suggested inspection (read-only)
- `python -m pip show nltk`: prints the installed version. Run with the environment that serves production active.

## Supported action
Upgrade each affected component to a fixed version on its release line. For a transitive dependency, upgrade the parent package or add an override or constraint, then regenerate the lockfile. Redeploy every environment that ran an affected version.

## Required regression checks
- Run the test suite and a production build.
- Exercise the features that depend on nltk.
- Repeat the inspection and confirm that only fixed versions remain installed.

## Rollback considerations
- Keep the previous lockfile and deployment artifact. Rolling back reinstates the vulnerable version, so apply any documented mitigation while you fix forward.

## Unresolved questions
- Which deployments run an affected version?
- Exploitation status can change. Check again before lowering the priority.
- Mark the work resolved only after the fixed version is verified in production.

## Sources
- Verified: https://github.com/advisories/GHSA-r53h-rw34-8h97 (GitHub-reviewed advisory GHSA-r53h-rw34-8h97 lists affected ranges: PyPI nltk >=0 <=3.10.3)
- Verified: https://osv.dev/vulnerability/GHSA-r53h-rw34-8h97 (OSV record GHSA-r53h-rw34-8h97 lists affected ranges: PyPI nltk >=0 <3.10.4 (fixed))

Commands are suggestions: review each one before running it.