CVE-2026-84310: Algorithmic Complexity Exhaustion in pypdf

The pypdf library is an open-source, pure-Python library designed to parse, split, merge, and manipulate PDF documents. It is widely used in automated ingestion pipelines, search indexing systems, and document processing backends. These deployment scenarios expose a significant attack surface, as backend services often automatically process untrusted, user-supplied PDF documents.

This vulnerability, tracked as CVE-2026-84310, involves two distinct algorithmic complexity exhaustion vectors that can result in complete denial of service. The affected components are located in the document outline parsing routine (_get_outline in pypdf/_doc_common.py) and the text extraction parser (_extract_text in pypdf/_page.py). By exploiting these execution paths, an attacker can craft a highly compact PDF document that consumes disproportionate system resources.

These issues are classified under CWE-405 (Asymmetric Resource Consumption) and CWE-834 (Excessive Iteration). When a vulnerable version of pypdf processes a malicious document, the parsing thread blocks indefinitely, consuming 100% CPU and exhausting system memory. This makes the target service completely unresponsive to subsequent requests.

The first vector resides within the _get_outline() method of the _doc_common.py module. PDF document outlines use dictionary objects linked to other sibling and child outline nodes. The parsing algorithm traverses these elements recursively. While the parser utilized a set of object IDs to prevent infinite loops from circular references, it lacked any global limits on traversal depth or total node counts. An attacker could construct an outline hierarchy with tens of thousands of unique nested items, forcing excessive recursive stack expansion that results in a Python RecursionError or exhaustive CPU consumption.

The second, more significant vector exists in the Form XObject processing implementation of the text extraction routines. PDF documents support Form XObjects, which are self-contained stream objects representing reusable vector or text graphics. When extracting text, pypdf recursively resolves and parses these nested Form XObjects. To defend against infinite recursion loops, the original execution logic maintained a tracking set of active object IDs named known_ids.

The critical bug was located in how this tracking state was cleaned up during execution. When a Form XObject completed processing, its ID was discarded from the known_ids set inside a finally block: known_ids.discard(xform_id). This cleanup strategy successfully prevented active cyclic loops, but it completely failed to track already-visited nodes across sister branches in the tree. Consequently, the logic was highly vulnerable to Directed Acyclic Graph (DAG) expansion attacks.

An attacker can register a linear chain of Form XObjects where each parent object references the next child object multiple times. Because pypdf discards a child ID from its tracking set as soon as that branch completes, it must fully re-parse the child object every single time it is referenced. This causes the total traversal complexity to scale exponentially ($2^{depth}$) relative to the number of defined objects. A document containing only 30 unique Form XObjects can force billions of recursive parsing steps, freezing the process indefinitely.

Prior to version 6.16.1, the vulnerable tracking logic in pypdf/_page.py processed Form XObjects with a local tracking mechanism that did not maintain a global step counter. The vulnerable block structured the parsing of nested forms as follows:

# Vulnerable tracking pattern in pypdf/_page.py
known_ids.add(xform_id)
try:
    # Recursively extract text from the XObject
    text = self.extract_xform_text(xform_id, ...)
finally:
    # The object ID is removed, allowing duplicate processing in sister branches
    known_ids.discard(xform_id)

The security patch introduced in version 6.16.1 fixes both execution paths by implementing a state-tracking dataclass and establishing strict global boundaries. The patch introduces _TraversalState to track execution metrics dynamically across recursive calls:

# Patched traversal state implementation
class _TraversalState:
    def __init__(self) -> None:
        self.entry_count = 0
        self.has_logged = False

In pypdf/_doc_common.py, the developers enforced strict caps on outline parsing, setting OUTLINE_MAX_ENTRIES = 100_000 and OUTLINE_MAX_DEPTH = 100. During recursion, the code now checks whether depth > OUTLINE_MAX_DEPTH or traversal_state.entry_count > OUTLINE_MAX_ENTRIES and immediately raises a LimitReachedError if these thresholds are exceeded.

For the text extraction component, the developers established a limit of MAX_XFORM_INVOCATIONS_PER_EXTRACTION = 5_000. The function _extract_text__xform now increments the global traversal_state.entry_count at each step. If the count exceeds the threshold, the parser terminates processing for that branch, logs a warning, and returns an empty string. This ensures that even the most complex DAG structures execute in linear time, capped at 5,000 operations, resolving the exponential complexity flaw.

Exploiting this vulnerability does not require complex payloads, shellcode, or specific memory layouts. The attack relies entirely on structural parsing properties. An attacker constructs a valid PDF containing a small number of Form XObject streams where each stream contains multiple reference commands (Do operators) targeting the next stream in the hierarchy.

The diagram illustrates how a shallow DAG structure containing only three distinct Form XObjects (F0, F1, and F2) leads to multiple redundant evaluations. At each layer, the processing complexity doubles. An exploit script generates a PDF with a depth of 25 to 30, which fits into a file of less than 10 kilobytes. When parsed, this file forces $2^{30}$ recursive calls, completely blocking the execution thread.

Because the Python interpreter is bound by the Global Interpreter Lock (GIL), a single-threaded web server or celery worker executing this operation will block entirely. This stops the processing of all other concurrent requests handled by that worker. The CPU usage for the worker spikes to 100%, and memory allocations accumulate as stack frames build, leading to potential system instability.

The primary impact of CVE-2026-84310 is a local and remote denial of service. While classified with a CVSS v4.0 base score of 4.8 (Medium), the operational impact on enterprise document ingestion pipelines can be significant. If a web application permits anonymous file uploads and automatically processes them using pypdf (for example, to index text or parse metadata), an attacker can easily exhaust the application's processing resources.

This vulnerability does not allow remote code execution, privilege escalation, or unauthorized data access. However, because pypdf is widely integrated into web application frameworks, search engine spiders, and document management systems, the footprint of affected software is broad.

Additionally, memory utilization during a DAG expansion attack scales significantly. The rapid allocation of nested tracking structures can trigger the host operating system's Out-Of-Memory (OOM) killer. If the vulnerable application runs in a shared container environment, the OOM killer may terminate the entire container or adjacent critical processes, amplifying the scope of the denial of service.

The definitive remediation for CVE-2026-84310 is to upgrade pypdf to version 6.16.1 or later. This release introduces the necessary structural constraints to prevent execution loops from consuming excessive resources. Ensure all deployment requirements files are updated to specify pypdf>=6.16.1.

If upgrading is not immediately possible, implement the following operational defenses:

1. Enforce aggressive processing timeouts. Wrap all PDF parsing tasks in a separate process using Python's multiprocessing library or an external task runner with a strict execution time limit (such as 10 seconds). This ensures that any thread entering an infinite recursion loop is forcefully terminated before it starves the rest of the system.

2. Minimize exposure of vulnerable functions. If your application only requires merging or splitting PDF files, avoid calling page.extract_text() or reading reader.outline on files uploaded by untrusted users. These are the specific endpoints that trigger the vulnerable recursive routines.

3. Use static analysis rules on edge gateways. Implement detection rules at your application boundaries or Web Application Firewall (WAF) to inspect uploaded PDF files for excessive occurrences of /Subtype /Form references combined with recursive Do operators within the same data streams.