Skip to content

NLTK: Uncontrolled recursion in nltk.featstruct.FeatStructReader causes unhandled RecursionError (DoS) via deeply nested feature-structure input

Moderate severity GitHub Reviewed Published Aug 12, 2026 in nltk/nltk • Updated Sep 2, 2026

Package

pip nltk (pip)

Affected versions

<= 3.10.2

Patched versions

3.10.3

Description

Summary

nltk.featstruct.FeatStructReader (used by FeatStruct(str) and by FeatureGrammar.fromstring()) parses feature-structure strings such as [a=1] with a recursive-descent parser that has no nesting-depth limit. A small, trivially-crafted input (~700 bytes) with deeply nested brackets drives the parser past Python's recursion limit and raises an unhandled RecursionError instead of the library's normal, catchable ValueError/LogicalExpressionException. Any application that parses user-supplied feature-structure or feature-grammar text (e.g. NLP teaching tools, grammar "playgrounds", unification-grammar-based NLU pipelines) can be crashed by an unauthenticated input with no special privileges. This is a Denial of Service issue (CWE-674, Uncontrolled Recursion), not a memory-safety or code-execution issue.

This appears to be the same bug class as two issues already fixed elsewhere in the codebase — nltk/jsontags.py (JSONTaggedDecoder.decode_obj, guarded by MAX_DECODE_DEPTH = 200) and nltk/sem/logic.py (LogicParser, guarded by MAX_PARSE_DEPTH = 200) — but nltk/featstruct.py does not have an equivalent guard.

Details

The recursive call chain (current develop branch, nltk/featstruct.py):

  1. FeatStructReader.fromstring() (featstruct.py:2184) calls read_partial() → _read_partial() (featstruct.py:2250).
  2. _read_partial() dispatches to _read_partial_featdict(), which calls _read_value() (featstruct.py:2436) for each feature's value.
  3. _read_value() calls read_value() (featstruct.py:2442), which matches the value against VALUE_HANDLERS (featstruct.py:2478).
  4. If the value itself starts with [ (a nested feature structure), the matched handler is read_fstruct_value (featstruct.py:2479, defined at featstruct.py:2495): 
    def read_fstruct_value(self, s, position, reentrances, match):
    return self.read_partial(s, position, reentrances)
    This calls read_partial() again, which re-enters _read_partial() — the same function from step 1.

This closes a recursive cycle (_read_partial → _read_value → read_value → read_fstruct_value → read_partial → _read_partial → ...) with no depth counter, no MAX_*_DEPTH constant, and no try/except RecursionError anywhere in the class. Each additional [ in the input adds one more full cycle of Python stack frames. Once the input nests deeply enough, Python's own recursion-limit protection fires and raises RecursionError, which is not a subclass of ValueError (the exception type this parser's own _error() helper raises for normal, well-formed parse errors) and therefore propagates uncaught through this API.

For comparison, nltk/sem/logic.py's LogicParser was hardened against exactly this class of issue:

#: Maximum expression-nesting depth the recursive-descent parser will
#: descend to. Deeply nested input would otherwise recurse until Python
#: raises an uncaught RecursionError and crashes the caller
#: (uncontrolled recursion, CWE-674); past this depth a normal
#: LogicalExpressionException is raised instead. Configurable.
MAX_PARSE_DEPTH = 200

(nltk/sem/logic.py:102-107), and nltk/jsontags.py's JSONTaggedDecoder similarly has MAX_DECODE_DEPTH = 200 with an explicit depth check. nltk/featstruct.py has no analogous protection.

FeatureGrammar.fromstring() (nltk/grammar.py) parses feature structures embedded in FCFG grammar rules via the same FeatStructReader, so the same crash is reachable through grammar-string parsing as well as through FeatStruct() directly.

PoC

Verified against the current develop branch in a clean virtualenv (Python 3.12, NLTK installed from this checkout via pip install -e .):

from nltk.featstruct import FeatStruct

depth = 167
payload = "[a=" * depth + "1" + "]" * depth   # 669 bytes
FeatStruct(payload)

Result:

Traceback (most recent call last):
  ...
  File ".../nltk/featstruct.py", line 2310, in _read_partial_featdict
    value, position = self._read_value(name, s, position, reentrances)
  File ".../nltk/featstruct.py", line 2440, in _read_value
    return self.read_value(s, position, reentrances)
  File ".../nltk/featstruct.py", line 2446, in read_value
    return handler_func(s, position, reentrances, match)
  [... repeats ~167 times ...]
RecursionError: maximum recursion depth exceeded
  • Crash threshold: nesting depth 167 (binary-searched between 50 and 200).
  • Payload size: 669 bytes — fits trivially in a single HTTP request body/query parameter.
  • Time to crash: <2ms — no resource exhaustion is needed, only recursion depth.

Minimal reproduction (no server required):

python3 -c "
from nltk.featstruct import FeatStruct
FeatStruct('[a=' * 200 + '1' + ']' * 200)
"

Illustrative server-side context (not part of NLTK itself, but representative of how the bug becomes reachable):

from flask import Flask, request
from nltk.featstruct import FeatStruct

app = Flask(__name__)

@app.route("/parse", methods=["POST"])
def parse_grammar():
    return {"result": str(FeatStruct(request.json["grammar"]))}

A POST of {"grammar": "[a=" * 200 + "1" + "]" * 200} to this endpoint raises the uncaught RecursionError inside the request handler.

Impact

Vulnerability type: Denial of Service via uncontrolled recursion (CWE-674). This is not a memory-corruption bug and does not lead to code execution or data disclosure — Python's own recursion-limit safety net converts what would be a C-level stack overflow into a catchable (but here, uncaught) RecursionError.

Who is affected: Any application that passes externally-supplied text into nltk.featstruct.FeatStruct() or nltk.grammar.FeatureGrammar.fromstring() — for example, NLP/computational-linguistics teaching tools, unification-grammar demo services, or NLU pipelines that accept user-authored feature grammars. This is a narrower slice of NLTK's user base than, e.g., tokenization or POS tagging, since feature-structure/unification-grammar parsing is a more specialized part of the library.

Practical severity depends on deployment:

  • In typical WSGI-style web frameworks (Flask/Django/FastAPI behind gunicorn/uwsgi), an uncaught exception inside a request handler is caught at the framework/server boundary: the single request fails (HTTP 500), the worker process itself survives, and unaffected requests are unimpacted.
  • In single-threaded or per-task-unprotected contexts (e.g. a queue-consuming worker without per-task exception isolation), the uncaught RecursionError can terminate the entire process; without a process supervisor that auto-restarts it, this is a persistent outage until manually restarted. An attacker who repeats the payload can keep such a worker in a crash loop for as long as the attack continues.

Suggested fix: Add a depth counter and a MAX_PARSE_DEPTH-style constant to FeatStructReader, mirroring the existing fix in nltk/sem/logic.py, and raise the library's normal ValueError-based parse error once the limit is exceeded instead of letting RecursionError propagate.

References

@alvations alvations published to nltk/nltk Aug 12, 2026
Published to the GitHub Advisory Database Sep 2, 2026
Reviewed Sep 2, 2026
Last updated Sep 2, 2026

Severity

Moderate

CVSS overall score

This score calculates overall vulnerability severity from 0 to 10 and is based on the Common Vulnerability Scoring System (CVSS).
/ 10

CVSS v4 base metrics

Exploitability Metrics
Attack Vector Network
Attack Complexity Low
Attack Requirements None
Privileges Required None
User interaction None
Vulnerable System Impact Metrics
Confidentiality None
Integrity None
Availability Low
Subsequent System Impact Metrics
Confidentiality None
Integrity None
Availability None

CVSS v4 base metrics

Exploitability Metrics
Attack Vector: This metric reflects the context by which vulnerability exploitation is possible. This metric value (and consequently the resulting severity) will be larger the more remote (logically, and physically) an attacker can be in order to exploit the vulnerable system. The assumption is that the number of potential attackers for a vulnerability that could be exploited from across a network is larger than the number of potential attackers that could exploit a vulnerability requiring physical access to a device, and therefore warrants a greater severity.
Attack Complexity: This metric captures measurable actions that must be taken by the attacker to actively evade or circumvent existing built-in security-enhancing conditions in order to obtain a working exploit. These are conditions whose primary purpose is to increase security and/or increase exploit engineering complexity. A vulnerability exploitable without a target-specific variable has a lower complexity than a vulnerability that would require non-trivial customization. This metric is meant to capture security mechanisms utilized by the vulnerable system.
Attack Requirements: This metric captures the prerequisite deployment and execution conditions or variables of the vulnerable system that enable the attack. These differ from security-enhancing techniques/technologies (ref Attack Complexity) as the primary purpose of these conditions is not to explicitly mitigate attacks, but rather, emerge naturally as a consequence of the deployment and execution of the vulnerable system.
Privileges Required: This metric describes the level of privileges an attacker must possess prior to successfully exploiting the vulnerability. The method by which the attacker obtains privileged credentials prior to the attack (e.g., free trial accounts), is outside the scope of this metric. Generally, self-service provisioned accounts do not constitute a privilege requirement if the attacker can grant themselves privileges as part of the attack.
User interaction: This metric captures the requirement for a human user, other than the attacker, to participate in the successful compromise of the vulnerable system. This metric determines whether the vulnerability can be exploited solely at the will of the attacker, or whether a separate user (or user-initiated process) must participate in some manner.
Vulnerable System Impact Metrics
Confidentiality: This metric measures the impact to the confidentiality of the information managed by the VULNERABLE SYSTEM due to a successfully exploited vulnerability. Confidentiality refers to limiting information access and disclosure to only authorized users, as well as preventing access by, or disclosure to, unauthorized ones.
Integrity: This metric measures the impact to integrity of a successfully exploited vulnerability. Integrity refers to the trustworthiness and veracity of information. Integrity of the VULNERABLE SYSTEM is impacted when an attacker makes unauthorized modification of system data. Integrity is also impacted when a system user can repudiate critical actions taken in the context of the system (e.g. due to insufficient logging).
Availability: This metric measures the impact to the availability of the VULNERABLE SYSTEM resulting from a successfully exploited vulnerability. While the Confidentiality and Integrity impact metrics apply to the loss of confidentiality or integrity of data (e.g., information, files) used by the system, this metric refers to the loss of availability of the impacted system itself, such as a networked service (e.g., web, database, email). Since availability refers to the accessibility of information resources, attacks that consume network bandwidth, processor cycles, or disk space all impact the availability of a system.
Subsequent System Impact Metrics
Confidentiality: This metric measures the impact to the confidentiality of the information managed by the SUBSEQUENT SYSTEM due to a successfully exploited vulnerability. Confidentiality refers to limiting information access and disclosure to only authorized users, as well as preventing access by, or disclosure to, unauthorized ones.
Integrity: This metric measures the impact to integrity of a successfully exploited vulnerability. Integrity refers to the trustworthiness and veracity of information. Integrity of the SUBSEQUENT SYSTEM is impacted when an attacker makes unauthorized modification of system data. Integrity is also impacted when a system user can repudiate critical actions taken in the context of the system (e.g. due to insufficient logging).
Availability: This metric measures the impact to the availability of the SUBSEQUENT SYSTEM resulting from a successfully exploited vulnerability. While the Confidentiality and Integrity impact metrics apply to the loss of confidentiality or integrity of data (e.g., information, files) used by the system, this metric refers to the loss of availability of the impacted system itself, such as a networked service (e.g., web, database, email). Since availability refers to the accessibility of information resources, attacks that consume network bandwidth, processor cycles, or disk space all impact the availability of a system.
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

EPSS score

Exploit Prediction Scoring System (EPSS)

This score estimates the probability of this vulnerability being exploited within the next 30 days. Data provided by FIRST.
(19th percentile)

Weaknesses

Uncontrolled Recursion

The product does not properly control the amount of recursion that takes place, consuming excessive resources, such as allocated memory or the program stack. Learn more on MITRE.

CVE ID

CVE-2026-81724

GHSA ID

GHSA-cw6x-m8jw-qmrh

Source code

Credits

Loading Checking history
See something to contribute? Suggest improvements for this vulnerability.