vector-forge

Vector Forge

使用变异测试系统地找出测试向量覆盖中的缺口，然后生成新的测试向量来填补这些缺口。 通过比较变异杀死率前后的变化来衡量效果。

适用场景

• 为密码算法或协议生成测试向量
• 评估现有测试向量对某个实现的覆盖情况
• 找出没有任何测试向量覆盖的实现代码路径
• 创建 Wycheproof 风格的跨实现测试向量
• 衡量一套测试向量的实际覆盖价值

不适用场景

• 尚无任何实现（需要有代码可供变异）
• 只有一个简单且不存在边缘情况的实现
• 测试应用逻辑，而非算法实现
• 该算法没有可供比较的公开测试向量

前置条件

• 已安装 trailmark — 如果 uv run trailmark 运行失败，请运行：

  uv tool install trailmark
  

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

- 至少有一种目标算法的实现，且其编程语言支持变异测试
- 一个能够读取测试向量并调用该实现的测试框架
- 目标语言的变异测试框架

---

## 应避免的错误想法

| 错误想法 | 错误原因 | 必须采取的行动 |
|-----------------|----------------|-----------------|
| “我们的测试向量已经够多了” | 变异测试能证明并非如此 | 先运行基线测试 |
| “实现自带的测试已经足够” | 自带测试常与实现存在相同的盲点 | 跨实现测试向量能发现不同的缺陷 |
| “可以在绑定层对 FFI crate 进行变异测试” | 对包装代码的变异不会影响底层实现 | 对实际实现所用的语言进行变异 |
| “超时意味着变异已被捕获” | 超时的含义不明确——变异可能已被杀死，也可能仍然存活 | 在得出结论前解决超时问题 |
| “所有变异体都是等价的” | 大多数并非如此——阅读变异后的代码进行核验 | 逐一归类每个逃逸的变异体 |
| “检查有效向量就够了” | 没有否定断言时，宽松的变异仍会存活 | 对每个无效向量都断言其应被拒绝 |
| “人工分析就行” | 人工分析会漏掉工具能捕获的问题 | 安装并运行工具 |

---

## 工作流概览

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 包装 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](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 访问，圈复杂度低	缺失向量	设计有针对性的向量
可从公共 API 访问，圈复杂度高（>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. 或使用 --test-pkg ./... 运行 gremlins（如果支持）
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 阶段：向量生成

对于每组逃逸代码路径，设计能强制执行该路径的测试向量。

向量设计模式

代码路径类型	向量策略
点反序列化	畸形点：长度错误、字段元素无效、不在曲线上、不属于正确的子群、单位点
签名验证	有效签名 + 对签名、公钥、消息进行的所有单比特损坏
哈希到曲线	已知答案测试（KAT），涵盖边界情况输入：空、单字节、最大长度
聚合操作	1 个签名者、多个签名者、重复签名者、有效与无效混合
错误处理	每条错误路径都应有一个能触发它的向量
算术边界情况	零、一、字段模数 - 1、无穷远点
序列化标志	每种有效标志组合 + 每种无效标志组合
往返完整性	对每个有效反序列化向量，断言 serialize(deserialize(b)) == b
进位／约简故障	使用缩小的肢宽重新实现，注入故障，并提取可区分的输入

单故障负向向量

每个负向向量都应恰好有一个缺陷，其他所有内容均有效——这样才能隔离要测试的验证检查。按标志构造示例，请参见 references/vector-patterns.md。

故障模拟（肢宽重新实现）

如果变异测试仅适用于局部运算符替换，那么更深层的架构错误（进位传播、约简溢出）就不会经过测试。为弥补这一不足，请使用缩小的肢宽（8、16、25、32 位）重新实现目标算法，并故意注入故障，然后生成能捕获这些故障的向量。

完整方法请参见 references/fault-simulation.md：肢宽选择、故障注入目录、向量提取和验证工作流。

跨实现验证

每个新增测试向量在加入测试套件前，都必须经过至少两个独立实现的验证：

1. 使用实现 A 生成向量
2. 使用实现 B 验证（代码库不同，最好使用不同语言）
3. 如果 B 的结果不一致，请进行调查——其中一个实现存在错误

向量格式

使用 Wycheproof JSON 格式（algorithm、testGroups[].tests[]，包含 tcId、comment、result、flags）。完整架构请参见 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）。最终比较时才运行完整 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（Phase 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 杀死率、超时掩盖、跨包误报、按位变异缺口和安全关键优先级