CVE-2026-59937: pypdf Replaces Quadratic xref Recovery with Cached Object Scan

Vulnerability

CVE-2026-59937 describes a denial-of-service condition in pypdf before 6.14.0 when parsing crafted PDFs with many malformed cross-reference entries. The vulnerable path attempted recovery by performing a regex search across the full PDF buffer for each missing or malformed xref object entry, which creates an O(N*M) pattern where N is the number of xref entries processed and M is the size of the scanned buffer. The advisory and CVE context identify this as CPU exhaustion triggered by attacker-controlled PDF structure rather than memory corruption or privilege escalation. See the official advisory at GHSA-55H5-XMCQ-C37V and the CVE records at NVD and CVE.org.

f = re.search(rf"{num}\s+(\d+)\s+obj".encode(), buf)
if f is None:
    generation = int(f.group(1))
    offset = f.start()

As summarized in the patch source, this recovery logic repeatedly scanned buf for each object number. Under a malformed xref table with thousands of bad entries, the parser could be forced into excessive sequential work. The added regression test constructs 20,000 corrupt xref entries and asserts successful parsing under a timeout, which is consistent with the reported attack shape in the patch PR.

Patch

The patch replaces repeated ad hoc regex recovery with a one-time cache built from a full object discovery pass. Instead of searching the entire buffer separately for each xref entry, the reader now computes a mapping from object number to the first discovered (offset, generation) tuple and reuses it for subsequent lookups.

def _load_recovery_cache(self, data: bytes) -> dict[int, tuple[int, int]]:
    cache = {}
    for object_number, generation_number, object_start in self._find_pdf_objects(data):
        if object_number in cache:
            # Always use the first match.
            continue
        cache[object_number] = (object_start, generation_number)
    return cache

recovery_cache = self._load_recovery_cache(buf)

The recovery path then checks membership in the cache and uses the cached tuple instead of invoking a fresh regex scan. This is the key algorithmic change documented in PR #3887. The tests added alongside the code change are relevant and targeted:

• A timeout-based regression test for malformed standard xref tables with 20,000 corrupt entries.
• A unit test validating that duplicate object numbers preserve the first match in the recovery cache.

These tests support both the performance claim and the intended cache semantics.

Review

Pros

• The patch directly addresses the root algorithmic issue: repeated full-buffer searches are replaced by a single precomputation plus O(1)-style dictionary lookups.
• The new helper _load_recovery_cache isolates the recovery-cache construction logic, improving readability and making the behavior testable.
• The duplicate-handling rule is explicit: the first discovered object wins. This matches the prior inline comment and avoids ambiguity in cache population.
• The regression test is attack-shaped rather than synthetic-only. A malformed xref table with 20,000 corrupt entries is a credible reproduction of the CPU exhaustion scenario described in the advisory.
• The timeout annotation provides practical protection against performance regressions in CI.

Cons

• The patch shifts cost from repeated scans to a full object enumeration pass. This is the correct tradeoff for the reported issue, but it still means recovery on very large PDFs incurs a whole-buffer scan and cache allocation.
• The provided snippets do not quantify complexity or benchmark results, so reviewers must infer the improvement from the code structure and regression test.
• The malformed recovery path semantics still depend on _find_pdf_objects. If that helper has pathological behavior on adversarial input, the overall parser may still be exposed to other performance edge cases not covered by this fix.
• The timeout-based test validates practical runtime bounds but does not assert exact complexity, so future changes could degrade performance without immediately failing on all environments.

Verdict

Root-cause.

This patch appears to remediate the underlying cause of CVE-2026-59937 rather than merely reducing symptoms. The vulnerable behavior was the per-entry sequential regex recovery loop over the entire PDF buffer; the fix removes that loop and replaces it with a single cached discovery pass. That is an algorithmic correction aligned with the vulnerability description in the advisory and CVE records. Based on the available diff and tests in the patch source, the change is technically sound, appropriately scoped, and likely sufficient for the reported CPU exhaustion vector.