CKB/CKB-VM 模糊测试实践

引言

模糊测试(Fuzzing 或 Fuzz)是软件测试中常用的一种测试方法. 模糊测试的核心思想是将自动或半自动生成的随机数据输入到一个函数中, 并监视程序的异常, 以发现可能存在的程序错误. 我们在 CKB-VM 2021 升级中采用了模糊测试技术, 并取得了相当好的效果. 本文的目的在于介绍模糊测试的基本原理以及我们是如何在本次 CKB-VM 2021 升级中应用模糊测试, 发现和排查错误.

测试技术路径的选择

CKB-VM 2021 升级最大的改变之一, 是增加了 RISC-V B 扩展指令集. B 扩展指令集中的 B 是 bit-manipulation 的缩写, 即位操作. 在 CKB-VM 2019 版本中, 我们提供了 RISC-V IMC 指令集: IMC 指令集提供基本的整数操作, 例如加法, 减法, 乘法或移位等操作. B 扩展指令集则进一步提供了更多新的操作: 例如整数的循环左移, 循环右移, 按位与/或/异或, 非, 按位置位/置零或者前导零计数等. 许多位操作都是我们在写算法时经常要使用到的, 而 B 扩展指令集就恰恰提供了这些操作的原生指令! 它带来好处是两方面的: 性能提升的同时且程序体积减少.

B 扩展指令集总共新增了 43 个指令, 按照作用可以细分为 4 个子类: 地址生成指令(Address generation instructions), 基础位操作指令(Basic bit-manipulation), 无进位乘法(Carry-less multiplication)和单位操作(Single-bit instructions)指令. 本文略过细节不讲, 详细的内容可以下载官方 PDF https://github.com/riscv/riscv-bitmanip/releases 进行查看. 如此数量庞大的指令带给我们一个难题: 如何保证这 43 个指令的实现的正确性? 我们首先想到的是使用官方测试用例, 但非常的不幸, 由于 CKB-VM 与 RISC-V B 扩展指令集规范是同步推进的--我们几乎在官方发布 1.0 版本规范的同时就准备好了代码, 它导致的结果是官方在那时并未来得及准备测试用例, 因此我们面临没有测试用例可用的窘境. 另一个更加严峻的问题是, 我们那时候连可以使用的汇编器(Assembler, 将汇编代码编译为机器码的工具)都没有: 如果我们准备自己编写测试用例, 不能使用 C 语言, 甚至连汇编语言都无法使用.

为了解决这两个问题, 我们做了以下两部分工作. 我们首先自己实现了一个汇编器 riscv-naive-assembler, 其次我们编写了一个随机 RISC-V 指令流生成程序.

汇编器是测试的第一步, 它的必要性有两点: 1) 我们可以使用汇编代码编写测试代码, 而不是机器码. 2) 因为 CKB-VM 在指令的执行前会做译码工作, 因此汇编器可以同 CKB-VM 内的译码器做交叉验证, 确保一条指令经过编码和译码后解析出来的仍然是同一条指令. 我们安排了两个开发者做这件工作, A 开发者编写一个独立于 CKB-VM 存在的汇编器, B 开发者在 CKB-VM 中编写译码过程, 在开发过程中 A 与 B 开发者互不沟通, 直到各自的工作完成. 之后, 我们生成随机的指令流, 首先通过汇编器, 然后将汇编器的输出传入 CKB-VM, 再从 CKB-VM 的译码过程中取回译码后的指令流, 与原始指令流进行比对并确保它们完全一致.

接下来是指令执行过程的测试. 我们面临的窘境是我们缺少官方的测试用例, 但请注意这个问题并不仅仅发生在我们身上, 其它 RISC-V 虚拟机团队也将同样的遇到此问题. 例如 Spike, 它是一个知名的 RISC-V 模拟器, 它实现了大多数 RISC-V 扩展, 是 RISC-V 社区开发者最常用的工具之一. 我们注意到 Spike 在 CKB-VM 2021 升级不久后也加入了 B 扩展指令集, 因此我们同样可以使用 Spike 模拟器作为与 CKB-VM 2021 进行交叉验证的对照组, 如果一段随机的指令流经过 CKB-VM 2021 和 Spike 后可以得出一致的结果, 只要该随机指令流覆盖度足够高并且经过长时间的测试, 那么我们就有相当大的把握相信 CKB-VM 2021 对 B 扩展指令集的实现与 Spike 的实现是一致的. 当两个不同的团队得出相同的结果时, 结果也将更有说服力. 在 B 扩展指令集外, 我们还需要重新回归测试基本的 RISC-V IMC 指令集, 对于 IMC 指令集我们采用了 Sail 模拟器而非 Spike 模拟器.

你大概会好奇这 Sail 与 Spike 模拟器之间有什么区别? Spike 实现了 RISC-V 指令, 但 Sail RISC-V 则是 RISC-V 指令的官方规范--只是目前为止 Sail 还未实现 B 扩展指令集.

模糊测试的随机指令流生成器

从上面的技术路径来看, 要完成 CKB-VM 2021 升级的测试还差最后一块拼图: 随机指令流生成器. 我们为此编写了 rfuzzing 工具, 它采用一种内部格式标记了每个待测试指令的格式, 然后依据格式不停生成指令. 在 RISC-V 的 B 扩展指令集中, 一个指令只接受两种不同类型的输入: 寄存器和立即数.

关于寄存器, RISC-V 总共有 32 个寄存器, 其名称分别为:

registers = [
    'zero', 'ra',   'sp',   'gp',
    'tp',   't0',   't1',   't2',
    's0',   's1',   'a0',   'a1',
    'a2',   'a3',   'a4',   'a5',
    'a6',   'a7',   's2',   's3',
    's4',   's5',   's6',   's7',
    's8',   's9',   's10',  's11',
    't3',   't4',   't5',   't6',
]

rfuzzing 在随机指令的生成过程中将这 32 个寄存器的前 31 个作为空闲寄存器(idle registers)供指令随意使用, 最后一个 t6 寄存器作为 checksum 状态寄存器--每个指令执行完毕后, checksum 寄存器都将当前指令的计算结果叠加到之前的状态上. 例如对于 clz 指令来说, 我们可能会生成如下的随机指令流:

clz ra, sp     # ra = clz(sp)  # 从空闲寄存器中随机取两个寄存器作为 clz 的输入
add t6, t6, ra # t6 = t6 + ra  # 将指令结果加入到 t6 寄存器, t6 最终的值即为 checksum

clz s5, gp     # s5 = clz(gp)  ...
add t6, t6, s5 # t6 = t6 + s5  ...

关于立即数, 我们会在指令的可选立即数范围内随机选择一个数字, 例如对于 rori 指令(循环右移指令), 它的基本格式是 rori rd, rs, uimm6, 它所执行的操作是将 rs 寄存器内的值循环右移 uimm6 位后保存在 rd 寄存器中, 其中 uimm6 立即数的大小在 0 到 64 之间. rfuzzing 就可能会针对 rori 指令生成如下的指令:

rori a3, a4, 27 # a3 = a4 >> 27 # 从空闲寄存器中随机取两个寄存器作为 rori 的输入并生成一个位于 0 到 64 之间的立即数
add t6, t6, a3  # t6 = t6 + a3  # 将指令结果加入到 t6 寄存器, t6 最终的值即为 checksum

我们循环上述的过程, 便可以生成一系列的测试指令, 每个指令的计算结果都被反映在 checksum 寄存器中. 最终我们将 checksum 寄存器的值作为程序的退出码退出程序, 我们在 CKB-VM 2021 与 Spike 中同时执行测试代码, 如果它们最终的退出码相同, 那么就可以认为这一系列的测试指令在两个虚拟机中都有相同的表现.

寄存器的随机初始化

RISC-V 规范约定其所有寄存器均以零值开始初始化, 但这并不是我们想要的. 在随机生成的测试代码之前, 我们会额外插入一段随机初始化代码以初始化寄存器中的值, 使得测试代码可以从"混沌"状态开始. 熟悉测试的朋友们应当知道, 当输入数据是某些边界值的时候, 程序更容易出现问题, 例如一个除法运算, 我们就要谨慎除数为零的情况. 回到之前的前导零(clz)计算的例子, 我们认为以下两种情况比较特殊, 在编写代码的时候更容易写出 Bug:

  1. 数字没有前导零, 即 0xffffffffffffffff
  2. 数字为零(即它的所有位均为前导零), 0x0000000000000000

想象一下, 如果我们遵循完全随机的生成数字, 那么凑巧生成 0xffffffffffffffff 或 0x0000000000000000 的概率是多少? 答案是 5.42e-20, 这个概率真的是太低了! 因此在 CKB-VM 的模糊测试中, 我们有意提高了一些边界值数字出现的概率, 例如 0x0000000000000000, 0x0000000000000001, 0xffffffffffffffff, 0x8000000000000000 等.

测试结果和结论

本轮模糊测试经统计平均每秒可以测试 4 万个随机指令, 总共测试时长 4 天左右, 期间总共发现约 10 余处错误, 这些错误大多集中在 CKB-VM 的 ASM 与 AOT 模式下, 而在 CKB-VM 的解释器模式下错误较少. 其本质原因是 CKB-VM 的 ASM 与 AOT 模式存在大量手工编写的汇编代码, 比起 Rust 编写的解释器代码更容易出现错误. 我们将在下一篇文章中介绍一个难以通过常规手段发现的错误.

模糊测试是 CKB-VM 测试流程中重要的一环, 在经过模糊测试后, 我们对此次 CKB-VM 2021 平稳和安全地升级有非常强大的信心.

模糊测试的一些细节

通过这次实践, 我们认为模糊测试方法值得在各个项目中进行推广. 模糊测试的数据生成和测试都是交由计算机完成的, 只要我们不手动停下它它就可以无限测试下去, 这意味着我们可以使用更多时间去做更有意义的事情. 随着模糊测试的时间变长, 你也将有更强的信心相信自己的程序是正确的. 模糊测试有几个细节需要测试人员进行额外关注:

  1. 随机输入的数据被过早拒绝. 许多时候我们需要一种结构化的数据, 例如 CKB-VM 的 ELF 结构数据. 如果你只是生成随机的数据, 那么大部分情况下它们将直接被解析器拒绝, 而无法深入程序内部. 因此在 CKB-VM 的模糊测试中我们使用合法的汇编代码作为输入.
  2. 模糊测试的最佳应用场景是单个无状态的函数. 你很难用模糊测试去测试一个 K8S 系统, 这真的没有必要.