Mittel

NLTK: Uncontrolled recursion in DependencyGraph traversal causes denial of service via deep dependency chains

  • Veröffentlicht: 19.11.2026
  • Aktualisiert: 20.11.2026 01:17

Root Cause

The dependency-graph traversal helpers recurse over dependency links without any depth bound or visited set. DependencyGraph._tree (nltk/parse/dependencygraph.py:404) recurses once per dependency link, triples (nltk/parse/dependencygraph.py:432) is a recursive generator, and get_cycle_path (nltk/parse/dependencygraph.py:520) recurses over dependencies. The neighbouring contains_cycle method was deliberately rewritten as an iterative depth-first search, but these sibling helpers on the public traversal path were left recursive with no depth counter.

Impact

An application that parses an untrusted CoNLL/Malt-TAB dependency structure and then walks it via tree() or triples() aborts with an unhandled RecursionError, terminating the affected operation or request worker (denial of service, CWE-674). The recursion is pure Python, so the result is a catchable RecursionError, not memory corruption or code execution. Confidentiality and integrity are unaffected. get_cycle_path additionally lacks a visited set and will not terminate on a genuine cycle.

Attack Chain

  1. The application constructs DependencyGraph(conll_str) from attacker-supplied text where token k's head is token k+1, forming a linear dependency chain of length N. Graph construction (_parse) is iterative and completes without error.
  2. The application calls the public DependencyGraph.tree() (nltk/parse/dependencygraph.py:408), which invokes _tree(root).
  3. _tree recurses once per chain link with no depth guard and no visited set, consuming one stack frame per link (the list comprehension costs roughly two frames per level).
  4. Once the chain length exceeds the interpreter recursion limit, an unhandled RecursionError propagates out of the public API. triples() fails the same way.

Bypass Evidence

Against the shipped source at the default recursion limit, a chain of length 5 walks cleanly through tree(), while a chain of length 5000 raises an unhandled RecursionError; triples() fails identically. The minimal trigger is roughly N=500 tokens at the default recursion limit — a modest, realistic parse. Because the graph builds iteratively in both cases, the fault is isolated to the recursive traversal rather than to parsing. A repository-wide search confirms no depth guard exists in this file; the iterative rewrite was applied only to contains_cycle.

Suggested Fix

Convert _tree, triples, and get_cycle_path to iterative traversals, or add a recursion-depth bound (and, for get_cycle_path, a visited set) analogous to the iterative rewrite already applied to contains_cycle.

Reported by pi (GitHub: @manus-pi).

Fix status (2026-09-28)

Status: MERGED on develop (unreleased; v3.10.3 of 2026-08-12 predates the fix).

PR: #3885 "Bound recursion depth in parsers and traversal helpers" (ekaf), merged 2026-09-11, merge commit e521ecafc on develop.

Fix commit: a74682757 (nltk/parse/dependencygraph.py: _tree, tree and triples stop at MAX_DEPTH=200 with ValueError).

Probe: nltk/test/unit/security_probes/ghsa_xfcv_m889_fmqg.py (added in 2a6704952 on that PR); verdict on develop 2fa3f48fe: FIXED (bounded in tree() (ValueError)).

Release: none yet; no release tag contains e521ecafc.

Betroffene Software

Klicken Sie auf eine Technologie, um alle zugehörigen Schwachstellen anzuzeigen.

PlattformPaketAnfällige VersionenBehoben in
Python (PyPI) nltk < 3.10.4 3.10.4

Verweise

CVSS-Wert 5.3/10
CVSS-Vektor
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L
Schwäche (CWE)
CWE-674
Plattform
Python (PyPI)
Paket
nltk
Veröffentlicht
19.11.2026
Aktualisiert
20.11.2026 01:17

Quellen und Lizenzen

OSV / GitHub Advisory Database - GHSA-xfcv-m889-fmqg - CC BY 4.0

Schwachstellenhistorie: nltk

Alle veröffentlichten Schwachstellen dieses Pakets (Python (PyPI)), neueste zuerst. Zeigt, ob es ein einmaliger Ausrutscher ist oder ein Paket, das man im Auge behalten muss.

Alle (79) im Archiv
Einträge insgesamt
79
Erste → letzte
08.2019 11.2026
Ohne Fix
5
In Angriffen ausgenutzt
0

Verteilung nach Schweregrad

  • Kritisch 5
  • Hoch 41
  • Mittel 31
  • Niedrig 2

Veröffentlichungen pro Jahr

  1. 2019: 1
  2. 2020: 0
  3. 2021: 2
  4. 2022: 1
  5. 2023: 0
  6. 2024: 1
  7. 2025: 0
  8. 2026: 74
Schweregrad:
  1. NLTK: Uncontrolled recursion in DependencyGraph traversal causes denial of service via deep dependency chains dieser Eintrag
    Mittel · 5.3 CVE-2026-129225 < 3.10.4 3.10.4
  2. Hoch CVE-2026-79674 < 3.10.3 3.10.3
  3. Hoch · 8.8 CVE-2026-71513 >= 3.10.0, < 3.10.3 3.10.3
  4. Hoch · 5.9 CVE-2026-62385 < 3.10.0 3.10.0
  5. Hoch · 7.5 CVE-2026-33231 < 3.9.4 3.9.4
Mehr anzeigen (7) 40 von 47 angezeigt

Erkennen Sie Schwachstellen in Ihrer Anwendung

Mit der DockRay-Integration und aktivierter Softwareinventarisierung prüft DockRay gemeldete Komponentenversionen auf bekannte Schwachstellen und benachrichtigt Sie über bestätigte Treffer. Die Abdeckung hängt von der unterstützten Technologie und den verfügbaren Meldungen ab.

Anwendung verbinden
DockRay Newsletter

Anwendungssicherheit in Ihrem Postfach

Wichtige Schwachstellen, konkrete Empfehlungen und praktische Tipps für Ihre Anwendungen. Wählen Sie Ihre Technologien und verfolgen Sie, was für Ihr Projekt relevant ist.

  • Eine tägliche Zusammenfassung neuer Schwachstellen, auch kritischer.
  • Benachrichtigungen über wichtige Updates.
  • Praktische Tipps zur Sicherheit und Überwachung von Anwendungen.

Leer lassen, um Meldungen zu allen Technologien zu erhalten.

Kostenlos anmelden. In jeder E-Mail mit einem Klick abmelden.