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 个并行工作进程)
• 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
ct_eq 在 Montgomery 肢体上的 &→|	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：向量生成

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

向量设计模式

代码路径类型	向量策略
点反序列化	畸形点：错误长度、无效域元素、离曲线、错误子群、无穷远点
签名验证	有效签名 + 签名、公钥、消息的所有单比特损坏
哈希到曲线	带边界输入的已知答案测试（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 了解完整模式。

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 (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 杀死率、超时掩盖、跨包误报、位突变缺口和安全关键优先级