CVE-2026-126298: NLTK: Quadratic-time CPU denial of service in Tree.chomsky_normal_form right-factor binarization via list.pop(0)
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.
References
- github.com/advisories/GHSA-r53h-rw34-8h97
- github.com/nltk/nltk/commit/457ebe349f8dd8080224f76a64aff806dd437057
- github.com/nltk/nltk/commit/677857dcafd84e4591865d976b562a27dfde566e
- github.com/nltk/nltk/pull/3909
- github.com/nltk/nltk/releases/tag/v3.10.4
- github.com/nltk/nltk/security/advisories/GHSA-r53h-rw34-8h97
- nvd.nist.gov/vuln/detail/CVE-2026-126298
- www.vulncheck.com/advisories/nltk-before-3.10.4-quadratic-cpu-denial-of-service-via-tree-chomsky-normal-form
Code Behaviors & Features
Detect and mitigate CVE-2026-126298 with GitLab Dependency Scanning
Secure your software supply chain by verifying that all open source dependencies used in your projects contain no disclosed vulnerabilities. Dependency Scanning using SBOM also detects vulnerabilities from proprietary advisories that this site does not include. Learn more about Dependency Scanning using SBOM →