CKB/CKB-VM 扩展指令集 B 的模糊测试

引言

模糊测试(Fuzzing)是软件测试中一种被广泛采用的测试方法. 其核心思想是向目标函数自动或半自动地输入大量随机数据, 并监控程序的异常行为, 从而发现潜在的实现缺陷. 在 CKB-VM 2021 Edition 升级中, 我们将模糊测试技术引入了 B 扩展指令集的验证流程, 并取得了显著成效. 本文介绍模糊测试的基本原理, 以及我们在 CKB-VM 2021 升级过程中如何具体应用它来发现和修复错误.

测试技术路径的选择

CKB-VM 2021 Edition 最重要的变化之一是引入了 RISC-V B 扩展指令集. B 扩展指令集中的 B 是 Bit-manipulation(位操作)的缩写, 共新增了 43 条指令, 按功能细分为四个子扩展:

子扩展	名称	典型指令
`zba`	地址生成	`sh1add`, `sh2add`, `sh3add`
`zbb`	基础位操作	`clz`, `ctz`, `cpop`, `ror`, `rol`
`zbc`	无进位乘法	`clmul`, `clmulh`, `clmulr`
`zbs`	单位操作	`bset`, `bclr`, `binv`, `bext`

关于 B 扩展指令集对 CKB-VM 性能的具体影响, 可参阅本系列的上一篇文章. 这里聚焦于另一个问题: 如何保证这 43 条指令实现的正确性?

我们首先想到的是使用官方测试用例. 然而, 由于 CKB-VM 与 RISC-V B 扩展规范几乎同步推进, 我们在官方发布 1.0 规范的同时就已准备好实现代码, 而此时官方尚未来得及提供完整的测试套件. 另一个更棘手的问题是, 当时甚至连可用的汇编器(Assembler, 将汇编代码编译为机器码的工具)都没有. 我们面临着巨大的问题: 如果要自行编写测试用例, 别说用 C 语言, 甚至连汇编语言都无法直接使用.

为解决上述两个问题, 我们开展了以下两方面工作.

第一步: 实现一个独立的汇编器. 我们自行实现了 riscv-naive-assembler. 汇编器的作用有两点: 一是让我们能够用汇编代码而非机器码编写测试用例; 二是与 CKB-VM 内部的译码器做交叉验证. 在开发过程中, 负责汇编器的开发者与负责 CKB-VM 译码器的开发者相互独立, 互不通气, 直至各自完成. 之后, 我们生成随机指令流, 先通过汇编器编码, 再输入 CKB-VM 译码器, 将译码结果与原始指令流逐一比对, 只有两者完全一致, 方可相互印证编码器与译码器的正确性.

第二步: 寻找可以交叉验证的参考实现. 缺乏官方测试用例这一困境并非 CKB-VM 独有, 其它 RISC-V 虚拟机团队在实现 B 扩展时同样面临这个问题. 我们注意到 Spike, RISC-V 社区最广泛使用的参考模拟器, 也在同期完成了 B 扩展指令集的支持. 因此我们选择 Spike 作为对照组: 将相同的随机指令流分别在 CKB-VM 2021 和 Spike 中执行, 若两者的最终状态一致, 则认为该指令序列的实现是正确的. 当两个由不同团队独立实现的模拟器能够对相同输入给出相同输出时, 结论的可信度将大幅提升.

随机指令流生成器

完成上述两步准备后, 整个测试方案还差最后一块拼图: 随机指令流生成器. 我们为此编写了 rv64tgen 工具.

rv64tgen 用一张指令规格表描述每条待测指令所接受的参数类型(寄存器 r, 有符号立即数 i12, 无符号立即数 u5/u6 等), 再据此随机生成合法的指令序列并最终输出为一个 RISC-V 汇编文件, 交由 clang 编译成可执行的 ELF 二进制.

寄存器的分工: RISC-V 共有 32 个通用寄存器. rv64tgen 从中保留两个寄存器作专用, 其余 30 个作为空闲寄存器(idle registers)供指令随机选取:

a0: checksum 累加寄存器. 程序开始时置零, 每条指令执行后将其目的寄存器的值累加到 a0.
a1: 内存基址寄存器. 指向程序数据段中预先填充了随机数据的缓冲区, 专供访存指令(lb, lw, sd 等)使用.

每条指令生成后, 紧跟一条 add a0, a0, <rd> 将结果计入 checksum:

clz       ra, sp        # ra = clz(sp),  随机选取空闲寄存器
add       a0, a0, ra    # checksum += ra

rori      a3, a4, 27    # a3 = ror(a4, 27),  立即数在 [0, 63] 内随机生成
add       a0, a0, a3    # checksum += a3

lw        t2, -8(a1)    # t2 = mem[a1 - 8],  偏移量为随机有符号 12 位立即数
add       a0, a0, t2    # checksum += t2

程序结构: rv64tgen 生成的汇编文件整体结构如下:

.section .data
messy:                        # 128 × 4 个随机 quad, 共 4096 字节随机数据
  .quad 0x..., 0x..., ...

.global _start
.section .text
_start:
  li   a0, 0                  # checksum 清零
  la   a1, messy              # a1 指向数据段
  addi a1, a1, 1024           #
  addi a1, a1, 1024           # 偏移 2048, 使访存可向前后各扩展

  # 外层循环 32 次, 内层每次生成 1024 条随机指令
  li   t0, <rand>             # 用随机值初始化全部 30 个空闲寄存器
  li   ra, <rand>
  ...
  clz  ra, sp
  add  a0, a0, ra
  ...

  li   a7, 93                 # Linux syscall: exit
  ecall                       # 退出码即为 a0 的值(checksum)

程序结束时通过 Linux exit 系统调用退出, 退出码即为 a0 的最终值. 将同一份二进制分别在 CKB-VM 2021 和 Spike 中执行, 若退出码相同, 则认为这批指令在两个虚拟机中的执行结果完全一致.

边界值的随机初始化

RISC-V 规范规定所有寄存器均以零值初始化, 但零值并不能提供最高的测试覆盖率. 在每轮指令序列开始前, rv64tgen 会用随机值逐一初始化全部 30 个空闲寄存器, 使测试从"混沌"状态开始.

熟悉测试工程的读者都知道, 边界值是最容易暴露实现缺陷的输入. 以前导零计数(clz)为例, 以下两种输入最容易触发错误:

数字无前导零: 0xffffffffffffffff(最高位为 1, 前导零计数为 0)
数字全部为零: 0x0000000000000000(前导零计数为 64)

若完全随机生成 64 位整数, 恰好命中其中任意一个特殊值的概率约为 5.42x10⁻²⁰, 极低. 因此 rv64tgen 维护了一张系统化生成的边界值表: 对每个位位置 i(0 < i < 64), 生成 2ⁱ-1, 2ⁱ, 2ⁱ+1 以及对应的高位掩码变体, 从而覆盖所有"恰好在某一位发生进位"的临界情形. 每次生成随机数时, 有 5% 的概率从这张边界值表中取值, 95% 的概率生成完全随机的 64 位整数.

测试结果与结论

我们的模糊测试框架平均每秒可执行约 4 万条随机指令, 持续运行 4 天后, 期间共发现约 10 余处大小错误. 这些错误大多集中在 CKB-VM 的 ASM(汇编) 执行模式中, 解释器模式下的错误相对较少. 根本原因在于 ASM 模式包含大量手写汇编代码, 与 Rust 编写的解释器相比, 手写汇编更容易出现细微的实现错误.

经过此轮模糊测试, 我们对 CKB-VM 2021 B 扩展指令集实现的正确性建立了较强的信心, CKB-VM 2021 Edition 也由此得以平稳, 安全地完成升级.

关于模糊测试的一些思考

通过本次实践, 我们认为模糊测试方法值得在更多项目中推广. 其最大优势在于自动化程度高: 测试框架搭建完成后, 整个测试过程完全由计算机驱动, 只要不主动停止, 它可以无限期地持续运行. 随着测试时间的累积, 对程序正确性的信心也会持续增强.

在工程实践中, 有以下几点值得特别关注:

避免输入被过早拒绝. 如果随机生成的数据在程序入口就被格式校验拒绝, 测试便无法深入程序内部. 对于需要结构化输入的系统(如 CKB-VM 需要合法的 ELF 格式文件), 必须生成符合结构约束的合法输入, 而非传统的纯随机字节流. 在本次测试中, 我们使用合法的 RISC-V 汇编代码作为输入, 正是基于这一考量.
模糊测试最适合无状态的单一函数. 模糊测试的效果在给定输入并得到确定性输出这类场景下最为突出. 对于复杂的有状态分布式系统, 模糊测试的适用性有限, 设计难度与投入产出比也往往不尽如人意.