vector-forge

Vector Forge

ミューテーションテストを使用してテストベクターのカバレッジ不足を体系的に特定し、その不足を補う新しいテストベクターを生成します。 前後のミューテーションキル率を比較して、有効性を測定します。

使用する場面

• 暗号アルゴリズムやプロトコルのテストベクターを生成する
• 既存のテストベクターが実装をどの程度カバーしているかを評価する
• テストベクターが実行していない実装コードのパスを見つける
• Wycheproof スタイルの実装間テストベクターを作成する
• テストベクタースイートがもたらす具体的なカバレッジ効果を測定する

使用しない場面

• 実装がまだ存在しない（ミューテートするコードが必要です）
• エッジケースのない、単純な実装が1つだけ存在する
• アルゴリズムの実装ではなく、アプリケーションロジックをテストする
• 比較対象となる公開テストベクターがアルゴリズムに存在しない

前提条件

• trailmark がインストールされている — uv run trailmark が失敗する場合は、次を実行します。

  uv tool install trailmark
  

Python snippets: uv run --with trailmark python - (a tool env is not importable)

- ミューテーションテストに対応する言語で、対象アルゴリズムの実装が少なくとも1つある
- テストベクターを読み込み、実装を実行するテストハーネスがある
- 対象言語用のミューテーションテストフレームワークがある

---

## 退けるべき合理化

| 合理化 | 誤りである理由 | 必要な対応 |
|-----------------|-----------------|-----------------|
| 「テストベクターは十分にある」 | ミューテーションテストでそうではないと証明できます | まずベースラインを実行します |
| 「実装独自のテストで十分だ」 | 独自のテストは実装と同じ見落としを共有していることがよくあります | 実装間テストベクターで異なるバグを検出します |
| 「FFI クレートはバインディング層でミューテーションテストできる」 | ラッパーへのミューテーションは、基盤となる実装に影響しません | 実際の実装言語のコードをミューテートします |
| 「タイムアウトしたならミューテーションは検出された」 | タイムアウトだけでは、ミューテーションが検出されたのか生き残ったのか判断できません | 結論を出す前にタイムアウトを解決します |
| 「すべてのミュータントは等価だ」 | ほとんどは等価ではありません — ミューテーションを読んで確認します | 生き残ったミュータントを個別に分類します |
| 「有効なテストベクターを確認すれば十分だ」 | 否定的なアサーションがないと、寛容にするミューテーションは生き残ります | 無効なテストベクターすべてについて拒否をアサートします |
| 「手動分析で問題ない」 | 手動分析ではツールが検出するものを見落とします | ツールをインストールして実行します |

---

## ワークフローの概要

Phase 1: Discovery → Find implementations to test ↓ Phase 2: Harness → Write/adapt test vector harness for each impl ↓ Phase 3: Baseline → Run mutation testing with existing vectors ↓ Phase 4: Escape Analysis → Classify escaped mutants by code path ↓ Phase 5: Vector Gen → Create test vectors targeting escapes ↓ Phase 6: Validation → Re-run mutation testing, compare before/after ↓ Output: Coverage Report + New Test Vectors

---

## フェーズ 1：調査

対象アルゴリズムの実装を探します。次の点を確認します。

1. **高水準言語で書かれた純粋な実装**（Go、Rust、Python）
   — ミューテーションテストの対象として最適です
2. **FFI ラッパークレート** — ラッパーの接着コードのミューテーションに時間を無駄にしないよう、早い段階で特定します
3. **リファレンス実装** — 実装間の検証に役立ちますが、ミューテーションテストの対象として最適とは限りません

実装ごとに、次の点を記録します。
- 言語とミューテーションテストフレームワーク
- 純粋なコードか、FFI ラッパーか
- 既存のテストスイートの規模とカバレッジ
- テストベクターが実行する API サーフェス

### 実装タイプの分類

| タイプ | ミューテーションテストの価値 | 例 |
|------|---------------|---------|
| 純粋な実装 | 高 | zkcrypto/bls12_381 (Rust)、gnark-crypto (Go) |
| C/asm への FFI バインディング | バインディング層では低 | blst Rust crate |
| C/C++ 実装 | 高（Mull を使用） | blst C library |
| 生成コード | 中（ミューテーションが等価な場合があります） | gnark-crypto の生成フィールド演算 |

**重要なポイント：** 実装が FFI 経由で別の言語に処理を委譲する場合は、バインディングではなく、*基盤となる*実装をミューテートする必要があります。Rust/Go/Python の下層に C/C++ がある場合は、Mull などを使用します。

---
## フェーズ 2：ハーネス

各実装について、次の処理を行うテストハーネスを作成します。

1. JSON ファイルからテストベクトルを読み込みます（Wycheproof 形式を推奨）
2. 各ベクトルについて、実装の API を呼び出します
3. **受理と拒否の両方**を検証します。
   - 有効なベクトル：デシリアライズに成功し、出力が期待値と一致する
   - 無効なベクトル：デシリアライズに失敗するか、検証で拒否される
4. 有効なデシリアライズベクトルについて、**ラウンドトリップのアサーション**を追加します。
   `serialize(deserialize(bytes)) == bytes`
5. テスト ID とともに、ベクトルごとの成功／失敗を報告します

**重要：** 有効なベクトルのみを検証するハーネスでは、寛容化を招く変更（例：検証における `&` → `|`）をすべて見逃します。[references/lessons-learned.md](references/lessons-learned.md) §7 を参照してください。

ハーネスは、ミューテーションテストフレームワークから実行可能でなければなりません。
多くのフレームワークでは、次のようにします。
- **Go：** 実装と同じパッケージに `_test.go` ファイルを配置
- **Rust：** `tests/` 内の統合テスト、またはインラインの `#[test]` 関数
- **Python：** pytest テストファイル
- **C/C++：** 実装にリンクしたテストバイナリ

### ハーネスの配置

ハーネスは、ミューテーションテストフレームワークが認識できるよう、*実装のパッケージ内*に配置する必要があります。通常は次のようになります。

```bash
# Go: add test file to the package being mutated
cp wycheproof_test.go /path/to/impl/package/

# Rust: add integration test
cp wycheproof.rs /path/to/crate/tests/

# Python: add test to the test directory
cp test_wycheproof.py /path/to/package/tests/

既存のベクトルの扱い

実装に既存のテストベクトルがある場合：

1. 既存のベクトルのみを使用してミューテーションテストを実行します（ベースライン）
2. 新しいベクトルのみを使用してミューテーションテストを実行します
3. 両方を組み合わせてミューテーションテストを実行します
4. （1）と（3）の差分から、新しいベクトルの効果が分かります

---

フェーズ 3：ベースライン

既存のテストベクトルのみを使用してミューテーションテストを実行します。

フレームワークの選定

言語ごとの設定については、references/mutation-frameworks.md を参照してください。

言語	フレームワーク	コマンド
Go	gremlins	gremlins unleash ./path/to/package
Rust	cargo-mutants	cargo mutants -j N --timeout T
Python	mutmut	mutmut run --paths-to-mutate src/
C/C++	Mull	mull-runner -test-framework=GoogleTest binary

並列実行

大規模なコードベースでは、必ず並列実行を使用します。

• cargo mutants -j 8（Rust、並列ワーカー 8 個）
• gremlins unleash --timeout-coefficient 3（Go、タイムアウトを延長）
• mutmut run --runner "pytest -x -q"（Python、フェイルファスト）

ベースライン結果の記録

実装ごとに、次の指標を記録します。

指標	説明
ミュータント総数	生成されたミューテーションの数
殺された数	テストで検出されたミュータント数
生存数	テストで検出されなかったミュータント数（これらが対象です）
未カバー	テストが一度も到達しないコードパス
タイムアウト	判定が曖昧なため、比較前に解消します
有効率 %	殺された数 /（殺された数 + 生存数）
カバレッジ %	（総数 - 未カバー）/ 総数

フェーズ 4 の分析用に、ミューテーションログ全体を保存します。

---

フェーズ 4：エスケープ分析（グラフを用いたトリアージ）

Trailmark の呼び出しグラフを使用して、エスケープした（生存したもの、および未カバーの）ミュータントをそれぞれ分類し、到達可能性と影響範囲を分析します。

このフェーズでは、必ず genotoxic スキルのトリアージ手法を使用してください。 呼び出しグラフを使うことで、ミューテーションテストの結果を、生存ミュータントの単なる一覧から、実行可能で優先順位付けされたベクトルの対象に変換できます。

ステップ 1：呼び出しグラフを作成する

ミューテーションをトリアージする前に、各実装の Trailmark コードグラフを作成します。

# Go
uv run trailmark analyze --language go --summary {targetDir}

# Rust
uv run trailmark analyze --language rust --summary {targetDir}

このグラフから、次の情報が得られます。

• 呼び出し元の連鎖 — 公開 API のエントリーポイントからミューテーションされた関数までたどり、到達可能性を確認します
• 循環的複雑度 — 循環的複雑度の高い関数を優先します
• 影響範囲 — 呼び出し元が多い関数は、ミューテーションが生存した場合の影響範囲が広くなります

ステップ 2：関連するコードに絞り込む

ミューテーションテストフレームワークはパッケージ全体をテストします。テストベクトルで実行すべきファイル／関数だけに結果を絞り込みます。

# Go (gremlins)
grep -E "(LIVED|NOT COVERED)" baseline.log \
  | grep -E " at (relevant|files)" \
  | sort

# Rust (cargo-mutants)
cat mutants.out/missed.txt | grep "src/relevant"

ステップ 3：グラフに基づく分類

変異が残った箇所ごとに、コールグラフから該当する関数を特定し、 遺伝毒性のトリアージ基準を適用します。

グラフシグナル	分類	対応
グラフ内に呼び出し元がない	誤検出	デッドコードのため、スキップ
テストからのみ呼び出される	誤検出	テストインフラストラクチャ
ロギング／表示／フォーマット	誤検出	見た目のみ
パッケージ間の呼び出し元があるが、カバーされていない	パッケージ間のギャップ	以下を参照
パブリック API から到達可能で、CC が低い	ベクトル不足	対象を絞ったベクトルを設計
パブリック API から到達可能で、CC が高い（>10）	ファジング対象	ベクトルとファジングハーネスの両方
検証／エラーハンドリングのパス	ネガティブベクトル	パスを発動する無効な入力を作成
最適化パス（GLV、SIMD、バッチ）	エッジケースベクトル	最適化のしきい値を発動する入力
左シフト後の |→^（例：(t<<1) | carry）	等価な変異	スキップ — ビット 0 は常に 0 のため、OR と XOR は同じ
Montgomery の limb における ct_eq の &→|	API から到達不能	ベクトルではなく、ライブラリ内部のテストが必要
等価な変異（動作に変化なし）	誤検出	スキップ

ステップ 4：パッケージ間のテストギャップを特定する

重大な落とし穴： 変異フレームワークは、変異を加えたパッケージ内のテストのみを実行することがよくあります。Go（gremlins）と Rust（cargo-mutants）では、次のようになります。

• hash_to_curve/g2.go の変異では、hash_to_curve パッケージ内のテストのみが実行されます。これをインポートする親パッケージ bls12381 のテストは実行されません
• パッケージをまたぐテストで完全に実行される関数は、カバーされていないように見えます。これらは誤検出です
• 確認するには、別のパッケージにある（実行対象外の）テストから、変異した関数が呼び出されているかを調べます

パッケージ間のギャップを解消するには、次のいずれかを行います。

1. パッケージ間テストと同じコードパスを通る薄いテストをサブパッケージに追加する
2. または、gremlins を --test-pkg ./... を指定して実行する（対応している場合）
3. または、レポートにフレームワークの制約として記載する

ステップ 5：セキュリティへの影響度で優先順位を付ける

コールグラフを使って、残った変異を影響度の高い順に並べます。

優先度	基準	例
P0 — 重大	変異によって検証／等価性／認証が弱まる	ct_eq：& → | により等価性の判定が緩くなる
P1 — 高	変異がデシリアライズ時のフラグ解析にある	from_compressed：& → | により無効なフラグを受け入れる
P2 — 中	変異がフィールド演算の内部にある	Fp::square： | → ^ により計算が破損する
P3 — 低	変異が最適化パスにある	phi の自己同型：パフォーマンスパスにのみ影響
スキップ	フォーマット、表示、等価な変異	Debug::fmt の戻り値の置換

ステップ 6：ベクトル戦略ごとにグループ化する

変異が残った箇所を、それらが表すコードパスと必要なテストベクトルの種類ごとにグループ化します。

Deserialization flag validation (P1):
  - g1.rs:339,363-365,384 — from_compressed_unchecked flags
  → Need: valid-point-wrong-flag vectors

Field arithmetic (P2):
  - fp.rs:371-376,406,635-643 — subtract_p, neg, square
  → Need: field arithmetic KATs with edge-case values

Optimization thresholds (P3):
  - g1.go:68, g2.go:75 — GLV vs windowed multiplication
  → Need: scalar multiplication with large scalars

Cross-package (framework limitation):
  - hash_to_curve/g2.go:242-278 — isogeny, sgn0
  → Document as false positive or add sub-package test

各グループは、フェーズ 5 で新しいテストベクトルを作成する対象になります。

---

フェーズ 5：ベクトルの生成

変異が残ったコードパスのグループごとに、そのパスを確実に実行させるテストベクトルを設計します。

ベクターデザインパターン

コードパスの種類	ベクター戦略
ポイントのデシリアライズ	不正なポイント：長さが不正、フィールド要素が無効、曲線上にない、部分群が不正、単位元のポイント
署名検証	有効な署名と、署名・公開鍵・メッセージの各単一ビットを破損させたもの
ハッシュから曲線への写像	空、1 バイト、最大長などのエッジケース入力を含む既知解テスト（KAT）
集約操作	署名者が 1 人、多数、重複、妥当なものと無効なものの混在
エラー処理	すべてのエラーパスについて、それを発生させるベクターを用意します
算術演算のエッジケース	ゼロ、1、フィールド法 - 1、無限遠点
シリアライズフラグ	有効なフラグの組み合わせすべてと、無効なフラグの組み合わせすべて
ラウンドトリップの完全性	有効なデシリアライズ用ベクターごとに、serialize(deserialize(b)) == b を検証します
キャリー／剰余化の不具合	リム幅を縮小して再実装し、不具合を注入して、それを識別できる入力を抽出します

単一不具合のネガティブベクター

各ネガティブベクターには、ほかのすべてが有効な状態で、不具合がちょうど 1 つだけ含まれている必要があります。これにより、テスト対象の検証チェックを特定できます。フラグごとの構築例については、references/vector-patterns.md を参照してください。

不具合シミュレーション（リム幅を縮小した再実装）

ミューテーションテストでローカルな演算子の置き換えしか行わない場合、キャリー伝播や剰余化のオーバーフローといった、より深いアーキテクチャ上の不具合はテストされません。このギャップを埋めるには、対象アルゴリズムをリム幅を縮小（8、16、25、32 ビット）して再実装し、意図的に不具合を注入したうえで、それらを検出するベクターを生成します。

全手法（リム幅の選択、不具合注入カタログ、ベクターの抽出、検証ワークフロー）については、references/fault-simulation.md を参照してください。

実装間の検証

新しいテストベクターは、スイートに追加する前に、少なくとも 2 つの独立した実装で必ず検証する必要があります。

1. 実装 A を使ってベクターを生成します
2. 実装 B（別のコードベースで、できれば別の言語）で検証します
3. B と結果が一致しない場合は調査します。どちらかの実装に不具合があります

ベクター形式

Wycheproof JSON 形式（algorithm、tcId、comment、result、flags を含む testGroups[].tests[]）を使用します。スキーマ全体については、references/vector-patterns.md を参照してください。

Wycheproof へのコントリビューション： ベクターファイルを直接フォーマットするのではなく、Wycheproof の vectorgen ツールを使用してください。生成した変更をエンベロープとして渡します。vectorgen ツールは、tcId の割り当て、テスト数、正規形式へのフォーマット、スキーマ検証を処理しながら、ベクターの追加、更新、置き換えを行えます。Go ベースのジェネレーターでは、vectorgen CLI ツールを使わず、プログラムから github.com/c2sp/wycheproof/vectorgen API を呼び出すこともできます。

現在のワークフローとコマンドについては、references/lessons-learned.md §14 および上流の vectorgen ガイド を参照してください。

---

フェーズ 6：検証

新しいテストベクターを含めて、ミューテーションテストを再実行します。

ヒント： ベクターの開発中は、すばやく反復できるようにファイル単位のミューテーションテストを使用してください（references/lessons-learned.md §12 を参照）。フルクレートのテストは最終比較時のみ実行してください。

実施前後の比較

指標	ベースライン	新しいベクター適用後	差分
キル数	X	Y	Y - X
生存数	A	B	A - B（減少するはずです）
未カバー数	C	D	C - D（減少するはずです）
有効率 %	E%	F%	F - E

成功基準

ベクトルには遡及的な価値（既存コードのミュータントをキルする）と、予防的な価値（今後の実装におけるバグを検出する）があります。両方の種類を生成してください。境界条件のベクトルは成熟したライブラリのキル率を向上させない場合がありますが、新しい実装のバグを検出できます。references/lessons-learned.md §13 を参照してください。

遡及的（測定可能）： 以前は生き残っていた、または未カバーだったミュータントがキルされ、リグレッションがないこと。

キル率に変化がない場合： 実装自体のテストで、これらのパスがすでにカバーされている可能性があります。それでも、ベクトルは実装間の検証価値を高めます。該当するケースを記録してください。

---

出力形式

VECTOR_FORGE_REPORT.md を作成し、対象アルゴリズム、テストした実装、ベースラインの結果、エスケープ分析、新たに生成したベクトル、実行後の結果、実行前後の差分、結論を記載してください。完全なテンプレートについては、references/report-template.md を参照してください。

---

品質チェックリスト

提出前に確認してください。

• FFI ラッパーだけでなく、少なくとも 1 つの純粋な実装に対してミューテーションテストを実施した
• 既存のベクトルを使ったベースライン実行を完了した
• 各実装について Trailmark の呼び出しグラフを構築した
• グラフに基づく分類を使って、エスケープしたミュータントをすべてトリアージした
• パッケージ間の誤検出を特定し、記録した
• セキュリティ上重要なミューテーション（ct_eq、検証、認証）を P0/P1 として優先した
• フォールトシミュレーションとミューテーション由来のベクトルを、2 つ以上の実装と照合して検証した
• 新しいベクトルを含めた実行後のテストを完了した
• 実行前後の差分を算出して説明した
• VECTOR_FORGE_REPORT.md にレポートを作成した
• 新しいテストベクトルを標準形式（Wycheproof JSON）で保存した

---

統合

スキル	関係
genotoxic（Phase 4 で必須）	グラフに基づくトリアージを提供します。呼び出しグラフにより、対処可能なミュータントを 30〜50% 削減できます
mutation-testing（mewt/muton）	Solidity で使用します。Vector Forge は言語に依存しません
property-based-testing	フィールド演算におけるビット単位のミューテーションには、手作業で作成したベクトルよりも適しています
testing-handbook-skills（fuzzing）	CC > 10 で生き残ったミュータントがある関数には、ベクトルとファズハーネスの両方が必要です

---

補足ドキュメント

• references/mutation-frameworks.md - 言語別のミューテーションテストフレームワークのセットアップ
• references/vector-patterns.md - 暗号プリミティブ向けの一般的なテストベクトルパターン
• references/fault-simulation.md - キャリー、剰余削減、オーバーフローのフォールトを再現するためのリム幅の再実装
• references/report-template.md - Vector Forge レポートの Markdown 完全版テンプレート
• references/lessons-learned.md - BLS12-381 のケーススタディ：FFI のキル率、タイムアウトによるマスキング、パッケージ間の誤検出、ビット単位のミューテーションの抜け、セキュリティ上重要な優先事項