Details
The quadratic accumulation was introduced in b2b737b68b06 ("Allow arbitrary number of comment extension subblocks", 2018-11-27), first released in Pillow 5.4.0.
Reproducing
repro is a single Python script that uses the installed Pillow. Run it with no arguments. It needs no files, no network and no rebuild.
It builds two GIFs of the same length, at 2 MB and at 4 MB. Each is the 13-byte GIF89a header for a 1×1 screen, followed by size/5 copies of the 5-byte extension 21 <label> 01 41 00, then a minimal 1×1 image and the trailer:
- comments: label
0xFE. Each extension is a 1-byte comment, so_seek()appends each one toinfo["comment"]with+=(GifImagePlugin.py:266). - control: label
0x01(plain-text extension). The bytes are the same apart from the label._seek()reads them through the same loop and the sameself.data()calls, then throws them away.
The script times Image.open(io.BytesIO(data)) on each file. It does not call load(), because _open() already parses frame 0. It checks that the image came out as 1×1. Typical output on a 2-CPU machine:
2 MB GIF control (0x01): 0.16 s comments (0xFE): 5.14 s
4 MB GIF control (0x01): 0.26 s comments (0xFE): 33.53 s
doubling 2 MB -> 4 MB multiplied open() time by x6.5 (linear: ~x2)
4 MB comment GIF took x129 as long as the same-size control
BUG
For a linear parser, doubling the file would roughly double the time, and the two files would take about the same time. The script prints BUG when all three of these hold:
- doubling the comment file from 2 MB to 4 MB multiplies its open time by at least 3×;
- the 4 MB comment file takes at least 20× as long as its control;
- the 4 MB comment file takes at least 8 s.
Otherwise it prints OK. The run is deterministic, CPU-bound on one core, and takes about 40 s.
Suggested fix
The attached patch changes GifImageFile._seek() in src/PIL/GifImagePlugin.py to accumulate comment data in a local list instead of with bytes concatenation, and to join it once when the frame's info is committed:
@@ def _seek(self, frame: int, update_image: bool = True) -> None:
info: dict[str, Any] = {}
+ comment_blocks: list[bytes] | None = None
frame_transparency = None
@@
elif s[0] == 254:
#
# comment extension
#
- comment = b""
+ if comment_blocks is None:
+ comment_blocks = []
+ else:
+ # If multiple comment blocks in frame, separate with \n
+ comment_blocks.append(b"\n")
# Read this comment block
while block:
- comment += block
+ comment_blocks.append(block)
block = self.data()
-
- if "comment" in info:
- # If multiple comment blocks in frame, separate with \n
- info["comment"] += b"\n" + comment
- else:
- info["comment"] = comment
s = b""
continue
@@
- if info.get("comment"):
- self.info["comment"] = info["comment"]
+ if comment_blocks:
+ comment = b"".join(comment_blocks)
+ if comment:
+ self.info["comment"] = comment
for k in ["duration", "extension"]:
This removes the quadratic copying at both sites (:261 per sub-block and :266 per extension); the 4 MB reproducer file opens in about 0.3 s, the same as its control, and the reproducer no longer prints BUG on a patched build. The resulting info["comment"] is unchanged for empty, multi-sub-block, multi-extension and later-frame comments — including Tests/images/multiple_comments.gif → b"Test comment 1\nTest comment 2" — and Tests/test_file_gif.py passes unchanged. The GIF writer (_write_local_header / _save) is not affected.
The patch deliberately adds no size cap. Unlike PNG zTXt, which PngImagePlugin.MAX_TEXT_CHUNK guards against decompression amplification, a GIF comment can be no larger than the file that carries it, so once the copy is linear there is nothing left to bound, and a hard cap would reject valid files with large comments. If a limit is wanted anyway, a MAX_COMMENT_SIZE check inside the sub-block loop is a small policy addition on top of this patch.
The patch
GIF: collect comment extension sub-blocks in a list and join once per frame instead of repeated bytes += in GifImageFile._seek()
Applies to src/PIL/GifImagePlugin.py at the commit above.
diff --git a/src/PIL/GifImagePlugin.py b/src/PIL/GifImagePlugin.py
index 11fb180fc..05007d2ac 100644
--- a/src/PIL/GifImagePlugin.py
+++ b/src/PIL/GifImagePlugin.py
@@ -217,6 +217,7 @@ class GifImageFile(ImageFile.ImageFile):
palette: ImagePalette.ImagePalette | Literal[False] | None = None
info: dict[str, Any] = {}
+ comment_blocks: list[bytes] | None = None
frame_transparency = None
interlace = None
frame_dispose_extent = None
@@ -254,18 +255,16 @@ class GifImageFile(ImageFile.ImageFile):
#
# comment extension
#
- comment = b""
+ if comment_blocks is None:
+ comment_blocks = []
+ else:
+ # If multiple comment blocks in frame, separate with \n
+ comment_blocks.append(b"\n")
# Read this comment block
while block:
- comment += block
+ comment_blocks.append(block)
block = self.data()
-
- if "comment" in info:
- # If multiple comment blocks in frame, separate with \n
- info["comment"] += b"\n" + comment
- else:
- info["comment"] = comment
s = b""
continue
elif s[0] == 255 and frame == 0 and block is not None:
@@ -433,8 +432,10 @@ class GifImageFile(ImageFile.ImageFile):
)
]
- if info.get("comment"):
- self.info["comment"] = info["comment"]
+ if comment_blocks:
+ comment = b"".join(comment_blocks)
+ if comment:
+ self.info["comment"] = comment
for k in ["duration", "extension"]:
if k in info:
self.info[k] = info[k]
The reproducer
<details>
<summary>Reproducer — <code>repro</code>, 2,263 bytes (click to open)</summary>
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
"""Quadratic CPU in Image.open() on GIF comment extensions.
GifImageFile._seek() appends every comment extension to info["comment"] with
bytes `+=` (src/PIL/GifImagePlugin.py:266), copying the whole accumulated
comment each time. Image.open() runs _seek(0) eagerly, so merely opening a GIF
made of many tiny comment extensions costs O(size^2) CPU.
We time Image.open() on two files of identical length:
ATTACK - a 1x1 GIF whose body is thousands of 1-byte comment extensions (label 0xFE)
CONTROL - the same bytes with label 0x01 (plain-text extension), which _seek()
reads through the same loop but discards instead of concatenating.
A linear parser would take ~2x longer when the file doubles, and the two files
would cost about the same.
"""
import io
import time
from PIL import Image
HEADER = b"GIF89a" + b"\x01\x00\x01\x00" + b"\x00\x00\x00" # 1x1 screen, no palette
IMAGE = b",\x00\x00\x00\x00\x01\x00\x01\x00\x00" + b"\x02\x02\x44\x01\x00" # 1x1 frame
TRAILER = b";"
def make_gif(size: int, label: int) -> bytes:
# each extension is `21 <label> 01 'A' 00`: one 1-byte sub-block, then terminator
extension = b"!" + bytes([label]) + b"\x01A\x00"
return HEADER + extension * (size // 5) + IMAGE + TRAILER
def time_open(data: bytes) -> float:
start = time.perf_counter()
with Image.open(io.BytesIO(data)) as im: # no load(): the cost is in open()
elapsed = time.perf_counter() - start
assert im.size == (1, 1)
return elapsed
MB = 1 << 20
attack, control = {}, {}
for size in (2 * MB, 4 * MB):
control[size] = time_open(make_gif(size, 0x01))
attack[size] = time_open(make_gif(size, 0xFE))