vector-forge

Vector Forge

使用突變測試系統性地識別測試向量覆蓋的缺口，然後生成新的測試向量來填補這些缺口。透過比較突變殺死率的前後差異來衡量有效性。

使用時機

• 為加密演算法或協定生成測試向量
• 評估現有測試向量對實作的覆蓋程度
• 找出沒有測試向量觸及的實作程式碼路徑
• 建立 Wycheproof 風格的跨實作測試向量
• 衡量測試向量套件的具體覆蓋價值

不應使用時機

• 尚無任何實作存在（需要有程式碼可突變）
• 單一簡單實作且沒有邊界情況
• 測試應用程式邏輯而非演算法實作
• 演算法沒有可比較的公開測試向量

前置需求

• trailmark 已安裝 — 若 uv run trailmark 失敗，請執行：

  uv pip install trailmark
  

• 至少一個目標演算法的實作，且語言支援突變測試
• 一個能消費測試向量並執行實作的測試框架
• 目標語言適用的突變測試框架

---

應拒絕的合理化藉口

合理化藉口	為何錯誤	必要行動
「我們的測試向量夠多了」	突變測試會證明並非如此	先執行基線測試
「實作自身的測試已足夠」	自身測試常與實作有相同盲點	跨實作向量能捕捉不同錯誤
「FFI crate 可以在綁定層做突變測試」	對包裝器的突變不影響底層實作	對實際實作語言進行突變
「逾時表示突變已被捕捉」	逾時是模糊的 — 可能被殺死也可能存活	在得出結論前先解決逾時
「所有突變體都是等價的」	大多數並非如此 — 需閱讀突變內容驗證	逐一分類每個逃逸突變體
「檢查有效向量就夠了」	寬鬆的突變在沒有負面斷言時會存活	對每個無效向量都斷言拒絕
「人工分析就夠了」	人工分析會漏掉工具能捕捉的	安裝並執行工具

---

工作流程總覽

階段 1：探索       → 尋找要測試的實作
      ↓
階段 2：測試框架   → 為每個實作撰寫/調整測試向量框架
      ↓
階段 3：基線       → 使用現有向量執行突變測試
      ↓
階段 4：逃逸分析   → 依程式碼路徑分類逃逸突變體
      ↓
階段 5：向量生成   → 建立針對逃逸的測試向量
      ↓
階段 6：驗證       → 重新執行突變測試，比較前後差異
      ↓
輸出：覆蓋報告 + 新測試向量

---

階段 1：探索

尋找目標演算法的實作。尋找：

1. 純實作 在高階語言（Go、Rust、Python）— 這些是突變測試的最佳目標
2. FFI 包裝 crate — 及早識別，避免浪費時間在突變包裝膠水程式碼上
3. 參考實作 — 有助於交叉驗證，但可能不是最佳突變目標

對每個實作，記錄：

• 語言與突變測試框架
• 是純程式碼還是 FFI 包裝
• 現有測試套件的大小與覆蓋率
• 測試向量將觸及的 API 表面

實作類型分類

類型	突變價值	範例
純實作	高	zkcrypto/bls12_381 (Rust)、gnark-crypto (Go)
對 C/asm 的 FFI 綁定	綁定層低	blst Rust crate
C/C++ 實作	高（使用 Mull）	blst C 函式庫
生成程式碼	中等（突變可能等價）	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 §7。

框架必須能被突變測試框架執行。對大多數框架，這表示：

• Go： 與實作同套件的 _test.go 檔案
• Rust： tests/ 中的整合測試或內聯 #[test] 函式
• Python： pytest 測試檔案
• C/C++： 連結實作的測試二進位檔

框架放置位置

框架必須位於實作的套件內部，突變框架才能看到。這通常表示：

# Go：將測試檔案加入被突變的套件
cp wycheproof_test.go /path/to/impl/package/

# Rust：加入整合測試
cp wycheproof.rs /path/to/crate/tests/

# Python：將測試加入測試目錄
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 個平行 worker）
• 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 入口點追蹤到被突變的函式，以判斷可達性
• 圈複雜度 — 優先處理高 CC 的函式
• 爆炸半徑 — 有許多呼叫者的函式，若其突變存活，影響範圍更大

步驟 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：圖形輔助分類

對每個逃逸突變體，將其對應到呼叫圖中的包含函式，並套用 genotoxic 分流標準：

圖形訊號	分類	行動
圖中無呼叫者	誤判	死程式碼，跳過
僅測試呼叫者	誤判	測試基礎設施
日誌/顯示/格式化	誤判	裝飾性
跨套件呼叫者但未覆蓋	跨套件缺口	見下文
從公開 API 可達，低 CC	缺少向量	設計目標向量
從公開 API 可達，高 CC (>10)	模糊測試目標	向量 + 模糊測試框架
驗證/錯誤處理路徑	負面向量	製作觸發該路徑的無效輸入
最佳化路徑（GLV、SIMD、批次）	邊界向量	觸發最佳化門檻的輸入
左移後 |→^（例如 (t<<1) | carry）	等價突變體	跳過 — 位元 0 永遠為 0，OR=XOR
Montgomery limbs 上 ct_eq &→|	API 不可達	需要函式庫內部測試，非向量
等價突變（行為不變）	誤判	跳過

步驟 4：識別跨套件測試缺口

關鍵陷阱： 突變框架通常只執行與突變同套件的測試。對 Go (gremlins) 和 Rust (cargo-mutants)，這表示：

• hash_to_curve/g2.go 中的突變只執行 hash_to_curve 套件的測試，而非匯入它的父套件 bls12381 的測試
• 被跨套件測試完整執行的函式會顯示為未覆蓋 — 這些是誤判
• 確認方式：檢查被突變的函式是否被不同套件中的測試呼叫，而該測試不會被執行

解決跨套件缺口：

1. 在子套件中加入一個薄測試，透過與跨套件測試相同的程式碼路徑呼叫
2. 或使用 --test-pkg ./... 執行 gremlins（若支援）
3. 或在報告中記錄為框架限制

步驟 5：依安全影響排序

使用呼叫圖，依影響排序存活突變體：

優先級	標準	範例
P0 — 嚴重	突變削弱驗證/相等性/認證	ct_eq：& → | 使相等性寬鬆
P1 — 高	反序列化旗標解析中的突變	from_compressed：& → | 接受無效旗標
P2 — 中	欄位算術內部的突變	Fp::square：| → ^ 破壞計算
P3 — 低	最佳化路徑中的突變	phi 自同態：僅影響效能路徑
跳過	格式化、顯示、等價突變	Debug::fmt 回傳值替換

步驟 6：依向量策略分組

將逃逸突變體依其代表的程式碼路徑與所需測試向量類型分組：

反序列化旗標驗證 (P1)：
  - g1.rs:339,363-365,384 — from_compressed_unchecked 旗標
  → 需要：有效點-錯誤旗標向量

欄位算術 (P2)：
  - fp.rs:371-376,406,635-643 — subtract_p、neg、square
  → 需要：含邊界值的欄位算術 KAT

最佳化門檻 (P3)：
  - g1.go:68, g2.go:75 — GLV 與視窗乘法
  → 需要：大標量的純量乘法

跨套件（框架限制）：
  - hash_to_curve/g2.go:242-278 — isogeny、sgn0
  → 記錄為誤判或加入子套件測試

每個分組成為階段 5 新測試向量的目標。

---

階段 5：向量生成

對每個逃逸程式碼路徑分組，設計強制執行該路徑的測試向量。

向量設計模式

程式碼路徑類型	向量策略
點反序列化	畸形點：錯誤長度、無效欄位元素、非曲線、錯誤子群、無窮點
簽章驗證	有效簽章 + 對簽章、公鑰、訊息的每個單一位元破壞
Hash-to-curve	含邊界輸入的已知答案測試（KAT）：空、單一位元組、最大長度
聚合操作	1 個簽署者、多個簽署者、重複簽署者、混合有效/無效
錯誤處理	每個錯誤路徑都應有觸發它的向量
算術邊界	零、一、欄位模數 - 1、無窮點
序列化旗標	每個有效旗標組合 + 每個無效旗標組合
往返完整性	對每個有效反序列化向量，斷言 serialize(deserialize(b)) == b
進位/歸約錯誤	以縮減 limb 寬度重新實作，注入錯誤，提取區分輸入

單一錯誤負面向量

每個負面向量應有恰好一個缺陷，其餘皆有效 — 這能隔離正在測試的驗證檢查。請參閱 references/vector-patterns.md 以取得每個旗標的建構範例。

錯誤模擬（Limb 寬度重新實作）

當突變測試僅套用局部運算子交換時，更深層的架構錯誤（進位傳播、歸約溢位）不會被測試。為填補此缺口，以縮減 limb 寬度（8、16、25、32 位元）重新實作目標演算法，並刻意注入錯誤 — 然後生成能捕捉它們的向量。

請參閱 references/fault-simulation.md 以取得完整方法：limb 寬度選擇、錯誤注入目錄、向量提取與驗證工作流程。

跨實作驗證

每個新測試向量在加入套件前，必須至少對兩個獨立實作驗證：

1. 使用實作 A 生成向量
2. 使用實作 B 驗證（不同程式碼庫，理想上不同語言）
3. 若 B 不同意，調查 — 其中一個實作有錯誤

向量格式

使用 Wycheproof JSON 格式（algorithm、testGroups[].tests[] 含 tcId、comment、result、flags）。請參閱 references/vector-patterns.md 以取得完整 schema。

JSON 編碼： Wycheproof 使用 reformat_json.py 正規化向量，該工具會取消 HTML 實體跳脫。生成向量時使用字面字元，而非 HTML 跳脫序列：

• Go： 使用 json.NewEncoder + enc.SetEscapeHTML(false) —
  絕不使用 json.Marshal/json.MarshalIndent，它們會靜默跳脫 > → \u003e、< → \u003c、& → \u0026
• Python： json.dumps 預設安全
• Node.js： JSON.stringify 預設安全

詳見 references/lessons-learned.md §14。

---

階段 6：驗證

使用包含新測試向量的設定重新執行突變測試。

提示： 向量開發期間使用逐檔案突變測試以快速迭代（見 references/lessons-learned.md §12）。僅在最終比較時執行完整 crate 測試。

前後比較

指標	基線	含新向量	差異
被殺死	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 包裝）
• [ ] 使用現有向量完成基線執行
• [ ] 為每個實作建立 Trailmark 呼叫圖
• [ ] 所有逃逸突變體已使用圖形輔助分類分流
• [ ] 跨套件誤判已識別並記錄
• [ ] 安全關鍵突變（ct_eq、驗證、認證）已優先為 P0/P1
• [ ] 錯誤模擬與突變衍生向量已對 2+ 實作交叉驗證
• [ ] 使用包含新向量的設定完成之後執行
• [ ] 前後差異已計算並解釋
• [ ] 報告已寫入 VECTOR_FORGE_REPORT.md
• [ ] 新測試向量以標準格式（Wycheproof JSON）儲存

---

整合

技能	關係
genotoxic（階段 4 必備）	提供圖形輔助分流 — 呼叫圖可減少 30-50% 可操作突變體
mutation-testing（mewt/muton）	用於 Solidity；Vector Forge 與語言無關
property-based-testing	對欄位算術中的位元級突變，優於手工向量
testing-handbook-skills（模糊測試）	CC > 10 且有存活突變體的函式需要向量與模糊測試框架

---

支援文件

• references/mutation-frameworks.md -
  語言特定的突變測試框架設定
• references/vector-patterns.md -
  加密原語的常見測試向量模式
• references/fault-simulation.md -
  用於進位、歸約與溢位錯誤的 limb 寬度重新實作
• references/report-template.md -
  Vector Forge 報告的完整 Markdown 範本
• references/lessons-learned.md -
  BLS12-381 案例研究：FFI 殺死率、逾時遮蔽、跨套件誤判、位元級突變缺口與安全關鍵優先級