Pillow: Quadratic-time DoS in PDF save_all (PdfParser.next_object_id)

Each doubling of the input roughly quadruples the time. cProfile of the 8 000-frame save attributes 13.5 s of 17.6 s to 24 003 calls of PdfParser.next_object_id (8.9 s inside XrefTable.keys, 3.9 s inside max); encoding and writing the 8 000 pages is the remaining ~4 s and scales linearly.

The per-page id reservation loop runs before any page is written:

# src/PIL/PdfImagePlugin.py:247-259  (_save)
    for im in ims:
        im_number_of_pages = 1
        if save_all:
            im_number_of_pages = getattr(im, "n_frames", 1)
        …
        for i in range(im_number_of_pages):
            image_refs.append(existing_pdf.next_object_id(0))
            if im.mode == "P" and "transparency" in im.info:
                image_refs.append(existing_pdf.next_object_id(0))

            page_refs.append(existing_pdf.next_object_id(0))
            contents_refs.append(existing_pdf.next_object_id(0))

n_frames comes straight from the file (for GIF it is the number of image blocks; the GIF plugin counts them by walking block headers, which is cheap). The frames do not even have to exist: the loop runs on n_frames before any frame is seeked, and for APNG n_frames is the num_frames value declared in the acTL chunk, rejected only if it is 0 or above 0x80000000 (src/PIL/PngImagePlugin.py:716-720). A 125-byte APNG declaring 8 000 frames therefore costs the same ~10–13 s as the 120 KB GIF, and more without bound as the declared count grows. Each of the 3 (or 4, for P images with transparency) calls per frame lands here:

# src/PIL/PdfParser.py:626-634
    def next_object_id(self, offset: int | None = None) -> IndirectReference:
        try:
            # TODO: support reuse of deleted objects
            reference = IndirectReference(max(self.xref_table.keys()) + 1, 0)
        except ValueError:
            reference = IndirectReference(1, 0)
        if offset is not None:
            self.xref_table[reference.object_id] = (offset, 0)
        return reference

# src/PIL/PdfParser.py:175-178  (XrefTable)
    def keys(self) -> set[int]:
        return (
            set(self.existing_entries.keys()) - set(self.deleted_entries.keys())
        ) | set(self.new_entries.keys())

_save passes offset=0, so every reserved id is inserted into xref_table.new_entries. The k-th call therefore materialises three sets covering all k−1 previous ids, computes a difference and a union, and then max() scans the result — O(k) work to produce the integer k. Summed over 3N calls this is O(N²): for 48 000 frames, 144 002 calls over sets growing to 144 002 elements, on the order of 10¹⁰ set-element operations, all spent before _write_image is reached for the first frame. Nothing on this path consults MAX_IMAGE_PIXELS (the frames are 1×1) and nothing raises; for the GIF the save eventually completes and produces a valid PDF, and for the declared-only APNG it raises OSError only once the id loop has finished and the first missing frame is seeked.

This reservation scheme was introduced in 6207b44ab1ff ("issue #2959: support appending to existing PDFs", 2018-01-18) and first shipped in Pillow 5.1.0; before it, the writer numbered objects arithmetically.

For contrast, write_obj(ref, …) with an already-reserved ref (src/PIL/PdfParser.py:548-555) only does a dict store, which is why the page-writing phase that follows is linear; the super-linear cost is entirely in how the next free id is computed.

Impact

The precondition is that the application saves the attacker's image as PDF with save_all=True; Image.open() and load() alone do not reach this code. An application that converts uploaded images to PDF this way — the documented way to get one page per frame from animated GIF/APNG/WebP or multi-page TIFF input — can have a worker held at 100 % CPU for about 10 minutes by a 720 KB GIF, about 4½ minutes by a 480 KB one, with the cost continuing to grow quadratically with upload size. With APNG the file size does not matter at all: a 125-byte file declaring N frames in acTL drives the same quadratic loop, up to the 2³¹ cap. The attacker controls only the file bytes; no unusual dimensions, modes or options are needed, memory use stays under 100 MB so memory limits do not intervene, and the decompression-bomb guard is not applicable. The consequence is denial of service of the process performing the conversion. Single-image PDF saves, and save_all saves of images with tens or hundreds of frames, are unaffected in practice.

This is the same family as earlier accidentally-quadratic parsing issues fixed in Pillow (e.g. CVE-2021-28677, EPS readline), but on the PDF writer side, reached only through a save rather than on open, and driven by frame count rather than by line structure.

Reproducing

repro is a single Python script. Run it with the Python that has Pillow installed (./repro). It uses under 100 MB of RAM and writes no files.

Input. Two kinds of file are built in memory, each with 2 000 and 8 000 frames:

• gif(n): a valid animated GIF — a GIF89a header with a 1×1 logical screen and a 2-colour global palette, then n copies of one 15-byte frame (a 1×1 image descriptor plus the LZW data for one pixel), then the trailer (30 and 120 KB). The only unusual thing about it is how many frames it has.
• apng(n): a 125-byte APNG — a 1×1 greyscale IHDR, an acTL chunk declaring n frames, one fcTL, one IDAT and IEND. Only the first frame exists; the other n − 1 are merely declared.

Action. Each file goes through what an upload-to-PDF converter would do: Image.open(BytesIO(data)), then im.save(BytesIO(), "PDF", save_all=True), timed with time.process_time(). For the APNG the save raises OSError once the writer tries to seek to the second frame; that happens after the id-reservation loop has run for all n declared frames, so the exception is caught and the CPU time up to it is recorded.

Expected output (stock build at this commit):

GIF  frames= 2000 file= 30020 B  save CPU=  1.03s  result=ok
GIF  frames= 8000 file=120020 B  save CPU= 11.68s  result=ok
GIF: 4x frames -> 11.3x CPU (linear ~4x, quadratic ~16x)
APNG frames= 2000 file=   125 B  save CPU=  0.65s  result=OSError(Truncated File Read)
APNG frames= 8000 file=   125 B  save CPU= 10.48s  result=OSError(Truncated File Read)
APNG: 4x frames -> 16.1x CPU (linear ~4x, quadratic ~16x)
BUG

A linear save would take about 4× as long for 4× the frames; here the GIF save grows ~11× and the APNG save ~16×, the latter with the file size fixed at 125 bytes. The script prints BUG when the save CPU for either format grows at least 8× for 4× the frames (twice the linear expectation), otherwise OK. Extending the same curve gives the figures in the table above: about 70 s at 16 000 frames (240 KB GIF), and about 10 minutes for a 720 KB file.

With the attached patch applied, the GIF save takes 0.32 s / 1.20 s (3.7×) and the APNG save 0.01 s / 0.03 s, and the script prints OK.

Suggested fix

Make next_object_id() O(1) by tracking the highest object id ever stored in XrefTable instead of rebuilding the key set on every call. The attached patch does this in src/PIL/PdfParser.py:

--- a/src/PIL/PdfParser.py
+++ b/src/PIL/PdfParser.py
@@ class XrefTable:
         self.deleted_entries = {0: 65536}  # object ID => generation
         self.reading_finished = False
+        self.max_object_id = 0  # highest object ID ever stored, deleted or not

     def __setitem__(self, key: int, value: tuple[int, int]) -> None:
         if self.reading_finished:
             self.new_entries[key] = value
         else:
             self.existing_entries[key] = value
+        if key > self.max_object_id:
+            self.max_object_id = key
         if key in self.deleted_entries:
             del self.deleted_entries[key]
@@ class PdfParser:
     def next_object_id(self, offset: int | None = None) -> IndirectReference:
-        try:
-            # TODO: support reuse of deleted objects
-            reference = IndirectReference(max(self.xref_table.keys()) + 1, 0)
-        except ValueError:
-            reference = IndirectReference(1, 0)
+        # TODO: support reuse of deleted objects
+        reference = IndirectReference(self.xref_table.max_object_id + 1, 0)
         if offset is not None:
             self.xref_table[reference.object_id] = (offset, 0)
         return reference

existing_entries is only ever populated through __setitem__ (from read_xref_table / read_prev_trailer), so the counter also covers ids read from an existing file in append=True mode. The one behavioural difference: when the highest-numbered existing object has just been deleted (del_root() / rewrite_pages() in append mode), the current code hands that id out again with generation 0, whereas the patch moves on to the next unused id — the more conservative choice for an xref table, and the one the existing TODO: support reuse of deleted objects comment points at. With the patch applied and Pillow rebuilt, the 16 000-frame save drops from ~70 s to ~2.5 s, fresh PDF output is unchanged, Tests/test_file_pdf.py and Tests/test_pdfparser.py pass, and the reproducer prints OK.

An alternative limited to the writer would be to reserve the 3 × number_of_pages ids in PdfImagePlugin._save() arithmetically from a single next_object_id() call, but fixing the allocator also covers write_obj(None, …) callers.

The patch does not address a separate, linear issue: PdfImagePlugin._save() still trusts n_frames before any frame is decoded, so a tiny file whose format reports a declared-only frame count (APNG acTL up to 2³¹) still makes it loop 3 × n_frames times before the first failing seek. Reserving ids per successfully seeked frame, or validating n_frames in such plugins, would close that.

The patch

Track the highest object ID in XrefTable so PdfParser.next_object_id() is O(1) instead of rebuilding and scanning the key set

Applies to src/PIL/PdfParser.py at the commit above.

diff --git a/src/PIL/PdfParser.py b/src/PIL/PdfParser.py
index 672557190..82ebfb867 100644
--- a/src/PIL/PdfParser.py
+++ b/src/PIL/PdfParser.py
@@ -133,12 +133,15 @@ class XrefTable:
         )  # object ID => (offset, generation)
         self.deleted_entries = {0: 65536}  # object ID => generation
         self.reading_finished = False
+        self.max_object_id = 0  # highest object ID ever stored, deleted or not
 
     def __setitem__(self, key: int, value: tuple[int, int]) -> None:
         if self.reading_finished:
             self.new_entries[key] = value
         else:
             self.existing_entries[key] = value
+        if key > self.max_object_id:
+            self.max_object_id = key
         if key in self.deleted_entries:
             del self.deleted_entries[key]
 
@@ -624,11 +627,8 @@ class PdfParser:
         self.orig_pages = self.pages[:]
 
     def next_object_id(self, offset: int | None = None) -> IndirectReference:
-        try:
-            # TODO: support reuse of deleted objects
-            reference = IndirectReference(max(self.xref_table.keys()) + 1, 0)
-        except ValueError:
-            reference = IndirectReference(1, 0)
+        # TODO: support reuse of deleted objects
+        reference = IndirectReference(self.xref_table.max_object_id + 1, 0)
         if offset is not None:
             self.xref_table[reference.object_id] = (offset, 0)
         return reference

The reproducer

Its last line is BUG when the issue triggers and OK when it does not. Re-run on a clean build of that commit it printed BUG.

#!/usr/bin/env python3
# PDF save_all is O(frames^2): PdfParser.next_object_id() does max(XrefTable.keys()),
# and keys() rebuilds sets of every id reserved so far, 3 calls per frame.
# (a) valid 1x1 animated GIF, 15 bytes/frame; (b) 125-byte APNG whose acTL merely
# *declares* N frames - ids are reserved for all N before the first seek fails.
import io, struct, time, zlib
from PIL import Image

def gif(n):
    return (b"GIF89a\x01\x00\x01\x00\x80\x00\x00\x00\x00\x00\xff\xff\xff"
            + b"\x2c\x00\x00\x00\x00\x01\x00\x01\x00\x00\x02\x02\x44\x01\x00" * n + b"\x3b")

def apng(n):
    def chunk(t, d):
        return struct.pack(">I", len(d)) + t + d + struct.pack(">I", zlib.crc32(t + d))
    return (b"\x89PNG\r\n\x1a\n"
            + chunk(b"IHDR", struct.pack(">IIBBBBB", 1, 1, 8, 0, 0, 0, 0))
            + chunk(b"acTL", struct.pack(">II", n, 0))
            + chunk(b"fcTL", struct.pack(">IIIIIHHBB", 0, 1, 1, 0, 0, 1, 1, 0, 0))
            + chunk(b"IDAT", zlib.compress(b"\x00\x00")) + chunk(b"IEND", b""))

def save_pdf(data):
    im = Image.open(io.BytesIO(data))
    t = time.process_time()
    try:
        im.save(io.BytesIO(), "PDF", save_all=True)
        res = "ok"
    except OSError as e:          # APNG: frames don't exist, fails *after* the id loop
        res = f"OSError({e})"
    return time.process_time() - t, res

bug = False
for name, make in (("GIF", gif), ("APNG", apng)):
    t = {}
    for n in (2000, 8000):
        data = make(n)
        t[n], res = save_pdf(data)
        print(f"{name:4} frames={n:5} file={len(data):6} B  save CPU={t[n]:6.2f}s  result={res}")
    growth = t[8000] / t[2000]
    print(f"{name}: 4x frames -> {growth:.1f}x CPU (linear ~4x, quadratic ~16x)")
    if growth >= 8:
        bug = True
print("BUG" if bug else "OK")