Pillow: PDFのsave_all関数における、オブジェクト数の二乗に比例するDoS脆弱性 (PdfParser.next_object_id)
```
============================================================================
PDFのsave_all関数における、オブジェクト数の二乗に比例するDoS脆弱性 (PdfParser.next_object_id)
場所: src/PIL/PdfParser.py:629 の next_object_id() 関数
コミット: a707c6b21c313880d0771e54965d142dd42358b6
============================================================================
```
PillowのPDF書き込み機能は、マルチフレーム画像をマルチページのPDFとして保存する際に、フレーム数に対して二乗に比例する時間がかかります。 攻撃者は、アップロードされた画像をこの方法で変換するアプリケーションを使用することで、小さなファイルでサーバーのCPUをフル稼働させ、数分間処理を遅延させることができます。 240KBのアニメーション画像では約70秒、720KBの画像では約10分かかります。 また、125バイトのアニメーションPNG画像で、実際にはフレームが存在しないにもかかわらず、大きなフレーム数を宣言するだけで、同様の遅延が発生し、フレーム数が2の31乗に達するまで上限はありません。 メモリ使用量は100MB以下で推移し、圧縮爆弾による制限は適用されません。
原因は、`src/PIL/PdfParser.py`の`PdfParser.next_object_id()`関数にあります。 この関数は、`max(self.xref_table.keys())`を計算することで、次の未使用のIDを特定します。 `XrefTable.keys()`は、予約済みの各IDに対して、呼び出しごとに3つのセットを再構築します。 `PdfImagePlugin._save()`関数は、ページが書き込まれる前に、各フレームに対して3回（透明度を持つパレット画像の場合は4回）この関数を呼び出します。 これにより、IDの予約ループだけでO(N²)の計算量となります。 `n_frames`の値は、ファイルから読み込まれるため、APNGの`acTL`カウントが、フレームが存在しない場合でもループを駆動します。 その場合、保存処理は遅延の後に`OSError`を発生させます。
アプリケーションが攻撃者のファイルに対して `im.save(..., "PDF", save_all=True)` を呼び出すことが前提条件です。`Image.open()` や `load()` だけでは、このコードに到達しません。添付の再現例では、有効な GIF ファイルの場合、フレーム数を4倍にすると、CPU 使用量は約11倍になります。固定長の125バイトのAPNGファイルの場合、約16倍になります。この動作は `6207b44ab1ff` (2018-01-18) で導入され、Pillow 5.1.0 で初めてリリースされました。`XrefTable` 内の最大の ID を追跡する小さな修正により、保存処理が線形になります。
## 詳細
マルチフレーム画像をマルチページのPDFとして保存する (`im.save(fp, "PDF", save_all=True)`) と、フレーム数の二乗に比例するCPU時間が必要になります。これは、ピクセル内容とは無関係です。PDFライターが予約するすべてのオブジェクトIDについて、それまでに予約されたすべてのIDのセットを再構築してスキャンする必要があるためです。
N個の同一の15バイトのフレームで構成された1×1ピクセルのアニメーションGIF（再現例で作成）を、このコミット時点での標準ビルドの2CPU環境で使用すると、以下のようになります（絶対的な時間はマシンによって異なりますが、増加率は一定です）。
| フレーム数 | GIFサイズ | `im.save(BytesIO(), "PDF", save_all=True)` | ピークRSS |
|---|---|---|---|
| 2,000 | 30 KB | 1.1秒 | |
| 8,000 | 120 KB | 14.7秒 | |
| 16,000 | 240 KB | 70秒 | 60 MB |
| 32,000 | 480 KB | 262秒 | 95 MB |
| 48,000 | 720 KB | 120秒でまだ実行中（推定約10分） | |
入力が2倍になると、処理時間は約4倍になります。8,000フレームの保存処理の `cProfile` を実行した結果、17.6秒のうち13.5秒が `PdfParser.next_object_id` の24,003回の呼び出しに費やされています（`XrefTable.keys` 内で8.9秒、`max` 内で3.9秒）。8,000ページのエンコードと書き込みには、残りの約4秒かかり、これは線形に増加します。
各ページのIDの予約処理は、どのページが書き込まれる前に行われます。
```python
# 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`の値はファイルから直接取得されます（GIFの場合、これは画像ブロックの数です。GIFプラグインは、ブロックヘッダーを走査することでこれをカウントします。これは比較的安価な処理です）。フレームが存在しなくても問題ありません。ループは、どのフレームも読み込まれる前に`n_frames`回実行され、APNGの場合、`n_frames`は`acTL`チャンクで宣言された`num_frames`の値です。この値が0以下、または`0x80000000`より大きい場合、エラーとなります（`src/PIL/PngImagePlugin.py:716-720参照）。したがって、8000フレームを宣言する125バイトのAPNGファイルは、120 KBのGIFファイルと同じくらいの処理時間（約10〜13秒）がかかり、宣言されたフレーム数が増えるほど、さらに時間がかかります。フレームごとに3回（または、透明度を持つ`P`画像の場合は4回）呼び出される処理が以下にあります。
```python
# src/PIL/PdfParser.py:626-634
def next_object_id(self, offset: int | None = None) -> IndirectReference:
try:
# TODO: 削除されたオブジェクトの再利用をサポートする
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` は `offset=0` を渡すため、予約されたすべての ID が `xref_table.new_entries` に挿入されます。したがって、k 回目の呼び出しでは、k-1 個の以前の ID をすべてカバーする 3 つのセットが作成され、差分と和集合が計算され、その後 `max()` が結果をスキャンします。これにより、整数 k を生成するために O(k) の処理が必要になります。3N 回の呼び出し全体で考えると、これは O(N²) になります。48,000 フレームの場合、144,002 回の呼び出しがあり、セットの要素数は最大で 144,002 になります。これにより、約 10¹⁰ 回のセット要素操作が発生し、これはすべて `_write_image` が最初のフレームで呼び出される前に完了します。この処理の一部には `MAX_IMAGE_PIXELS` が参照されませんが、エラーは発生しません。GIF の場合、保存処理は最終的に完了し、有効な PDF が生成されます。一方、宣言のみが行われた APNG の場合、ID のループが完了し、最初の欠落フレームが検索されるまで `OSError` が発生します。
この予約スキームは、`6207b44ab1ff` ("issue #2959: support appending to existing PDFs", 2018-01-18) で導入され、Pillow 5.1.0 で初めてリリースされました。それ以前は、書き込み処理はオブジェクトに算術的に番号を付けていました。
対照的に、すでに予約済みの `ref` を持つ `write_obj(ref, …)` ( `src/PIL/PdfParser.py:548-555`) は、辞書への格納のみを行います。そのため、その後のページ書き込みフェーズは線形になります。超線形なコストは、次の未使用の ID がどのように計算されるかに完全に依存します。
## 影響
前提条件は、アプリケーションが攻撃者の画像を `save_all=True` の設定でPDFとして保存することです。`Image.open()` と `load()` だけでは、このコードに到達しません。アップロードされた画像をこの方法でPDFに変換するアプリケーション（アニメーションGIF/APNG/WebPやマルチページのTIFFファイルを1フレームずつPDFにするための、公式に推奨される方法）では、720KBのGIFファイルの場合、約10分間、CPU使用率が100%になることがあります。480KBのファイルでは、約4.5分間です。このCPU使用率は、アップロードされるファイルサイズに対して、二次関数的に増加します。APNGの場合、ファイルサイズは全く関係ありません。`acTL`でNフレームを宣言する125バイトのファイルでも、同じ二次関数のループが発生し、最大2³¹まで増加します。攻撃者はファイルの内容のみを制御します。特殊なサイズ、モード、またはオプションは必要ありません。メモリ使用量は100MBを超えないため、メモリ制限による影響はありません。また、ファイルサイズ爆弾に対する防御機能も適用されません。その結果、PDF変換を実行しているプロセスがサービスを停止してしまいます。単一の画像PDFの保存や、数十または数百のフレームを持つ画像の `save_all` による保存は、実際には影響を受けません。
これは、Pillowで以前に修正された、意図せず二次関数的な処理になる解析の問題（例：CVE-2021-28677、EPSの `readline`）と同じ系統ですが、PDFの *書き込み* 側であり、開くのではなく保存時にのみ発生し、行構造ではなくフレーム数によって駆動されます。
## 再現方法
`repro` は単一のPythonスクリプトです。PillowがインストールされているPythonで実行します（`./repro`）。これは100MB未満のRAMを使用し、ファイルは書き込みません。
**入力。** 2種類のファイルがメモリ上に構築されます。それぞれ2000フレームと8000フレームです。
- `gif(n)`: 有効なアニメーションGIF。`GIF89a`ヘッダー、1×1の論理画面、2色グローバルパレット、そして`n`個の15バイトフレームのコピー（1×1の画像記述子と、1ピクセルのLZWデータ）、最後にトレーラー（30KBと120KB）。特筆すべき点は、フレームの数が多いことです。
- `apng(n)`: 125バイトのAPNG。1×1のグレースケール`IHDR`、`n`個のフレームを宣言する`acTL`チャンク、1つの`fcTL`、1つの`IDAT`と`IEND`。最初のフレームのみが存在し、残りの`n - 1`個は宣言されているだけです。
**動作。** 各ファイルは、PDFへの変換を行うソフトウェアが行う処理と同じものを実行します。`Image.open(BytesIO(data))`で画像を開き、`im.save(BytesIO(), "PDF", save_all=True)`でPDFとして保存します。この処理にかかる時間を`time.process_time()`で計測します。APNGの場合、セーブ処理は、書き込みプログラムが2番目のフレームにアクセスしようとした時点で`OSError`を発生させます。これは、宣言されたすべての`n`個のフレームに対してID予約ループが完了した後で発生するため、例外をキャッチし、その時点までのCPU時間を記録します。
**期待される出力**（このコミット時点での標準ビルド）：
```
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
```
線形な保存であれば、フレーム数が4倍になると、処理時間も約4倍になるはずです。しかし、GIFの保存時間は約11倍、APNGの保存時間は約16倍に増加します。APNGの場合、ファイルサイズは125バイトで固定されています。スクリプトは、どちらの形式でも、フレーム数が4倍になったときに、保存にかかるCPU時間が少なくとも8倍に増加した場合に`BUG`と出力します。それ以外の場合は`OK`と出力します。同様の傾向を延長すると、上記の表に示された数値が得られます。具体的には、16,000フレーム（240KBのGIF）の場合、約70秒、720KBのファイルの場合、約10分かかります。
添付されたパッチを適用すると、GIFの保存時間は0.32秒/1.20秒（3.7倍）、APNGの保存時間は0.01秒/0.03秒となり、スクリプトは`OK`と出力します。
## 提案される修正
`next_object_id()`関数をO(1)に改善するために、`XrefTable`に格納されたオブジェクトIDの中で最も高いものを追跡し、毎回キーセットを再構築するのではなく、その情報を利用します。添付のパッチは、`src/PIL/PdfParser.py`でこの変更を行っています。
```diff
--- 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 # 記録された、または削除されたオブジェクトIDの中で最も高いもの
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` は常に `__setitem__` ( `read_xref_table` または `read_prev_trailer` から) によってのみ設定されるため、このカウンタは、`append=True` モードで既存のファイルから読み込まれた ID もカバーします。動作上の唯一の違いは、最高番号の既存オブジェクトが削除された場合 (`del_root()` または `rewrite_pages()` in append mode)、現在のコードはその ID を世代 0 で再割り当てしますが、パッチでは次の未使用の ID に進みます。これは、Xref テーブルにとってより安全な選択であり、既存の `TODO: 削除されたオブジェクトの再利用をサポートする` というコメントもそれを指しています。パッチを適用して Pillow を再構築すると、16,000 フレームの保存にかかる時間が約 70 秒から約 2.5 秒に短縮され、新規の PDF 出力は変更されず、`Tests/test_file_pdf.py` と `Tests/test_pdfparser.py` は正常にパスし、リプロデューサは `OK` と表示されます。
ライターに限定した別の方法として、`PdfImagePlugin._save()` で `3 × number_of_pages` の ID を、単一の `next_object_id()` 呼び出しで算術的に予約する方法がありますが、アロケータを修正することで、`write_obj(None, …)` を呼び出す箇所もカバーされます。
このパッチは、別の問題、つまり線形的な問題を解決していません。`PdfImagePlugin._save()` は、まだフレームがデコードされる前に `n_frames` の値を信頼しているため、フォーマットが宣言されたフレーム数のみを報告する小さなファイル (APNG の `acTL` で最大 2³¹) でも、最初の失敗するシークが発生する前に `3 × n_frames` 回ループしてしまいます。正常にシークされた各フレームに対して ID を予約するか、このようなプラグインで `n_frames` の値を検証することで、この問題を解決できます。
## パッチの内容
XrefTable 内で最高オブジェクト ID を追跡し、`PdfParser.next_object_id()` を O(1) にし、キーセットの再構築とスキャンを不要にする。
これは、上記のコミットにおける `src/PIL/PdfParser.py` に適用されます。
```diff
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:
) # オブジェクトID => (オフセット, 生成番号)
self.deleted_entries = {0: 65536} # オブジェクトID => 生成番号
self.reading_finished = False
+ self.max_object_id = 0 # 記録されているオブジェクトIDの最大値 (削除された場合も含む)
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: 削除されたオブジェクトの再利用をサポート
- reference = IndirectReference(max(self.xref_table.keys()) + 1, 0)
- except ValueError:
- reference = IndirectReference(1, 0)
+ # TODO: 削除されたオブジェクトの再利用をサポート
+ 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
```
## 再現手順
<details>
<summary>再現手順 — <code>repro</code>, 1,791 bytes (クリックして開きます)</summary>
このファイルの最終行が `BUG` と表示される場合、問題が発生していることを示します。問題が発生しない場合は `OK` と表示されます。同じコミットをクリーンな状態でビルドすると、`BUG` と表示されます。
```python
#!/usr/bin/env python3
# PDFの保存処理は、フレーム数に対してO(フレーム数^2)の計算量になる: PdfParser.next_object_id()は、XrefTable.keys()の最大値を取得し、keys()は、これまでに予約されたすべてのIDのセットを再構築するため、1フレームあたり3回の呼び出しが発生する。
# (a) 有効な1x1のアニメーションGIF、15バイト/フレーム; (b) acTLが単にNフレームを*宣言する*だけの125バイトのAPNG。最初のシークが失敗する前に、すべてのNのIDが予約される。
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: フレームが存在しないため、IDループの*後*でエラーが発生する
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}: フレーム数を4倍にすると、CPU使用量は{growth:.1f}倍になる (線形では約4倍、二次関数では約16倍)")
if growth >= 8:
bug = True
print("BUG" if bug else "OK")
```
</details>
---
影響を受けるパッケージ:
- pip (Python) Pillow: 影響を受けるバージョン >= 5.1.0, < 13.0.0、修正されたバージョン 13.0.0