针对WebAssembly虚拟机的模糊测试方案

◆林 敏 张 超

(清华大学 北京 100084)

1 引言

随着业界对软件安全问题的关注度不断提升，漏洞挖掘逐渐成为重点研究的内容。模糊测试[1]作为一种通过随机样本挖掘软件漏洞的技术，相比于其他漏洞挖掘技术更加简单高效。它是一种向应用程序提供非预期的输入，通过监控执行中的异常，来发现软件漏洞的方法。目前应用得较为广泛的灰盒测试工具是AFL[2]及其扩展[3-6]。

然而传统的模糊测试存在一个公认的缺点：对于具有复杂文件格式输入的应用程序，随机的比特变异难以生成合法有效的文件，往往在应用程序初始执行阶段就无法通过检查，难以对应用程序的深层逻辑进行有效的检测，导致了模糊测试的低效。

本文对EOS执行智能合约所使用的WebAssembly二进制虚拟机进行研究，该目标对象的输入不仅具有高结构化的特征，同时因其代码段由各种指令组成，还包含丰富的语义信息。想对虚拟机进行完整的测试，不仅要保留 WebAssembly二进制文件的整体结构信息，同时还要在符合 WebAssembly语法的情况下尽可能地变异出包含各种语义的文件。

但是基于覆盖率的模糊测试最大的问题是缺乏对输入文件的结构理解。测试中的变异操作通常在比特的层面进行，例如进行位翻转、删除、添加等，但是对于具有复杂文件格式规范的应用程序来说，不合法的文件可能导致程序在初始的合法性检查阶段就退出，导致生成了大量无效的测试用例，难以发现应用程序的深层次逻辑漏洞。针对传统方案的局限性，研究人员也提出了新的方案，比较主流的有基于字典和污点跟踪的方法。

AFL的作者采用了自定义字典[15]的方式，让用户提供关于输入文件结构的信息。当输入文件中存在魔数和块标识符的情况下，这种方式能发挥比较好的作用。基于AFL的拓展工具VUzzer[7]通过静态分析和动态污点跟踪和的方法来定位变异点。但是这两种方式都不能解决上述的问题，即无法从更高的层面，而非比特层面来改变文件的结构信息。例如，通过字典和污点跟踪的方案都不能添加或完删除文件块。

Driller[8]在AFL的基础上加入了动态符号执行引擎，交替探索程序执行路径，引导模糊测试探索到程序更深层次的节点。但是，基于符号执行增强的模糊测试技术仍然会受限于符号执行中的约束求解问题，符号执行的引入可能会弱化模糊测试本身的可扩展性。

针对上述问题，本文提出了一种针对EOS的WebAssembly二进制虚拟机进行模糊测试的方案，与传统的模糊测试方案不同，本方案通过研究 WebAssembly各模块对执行的影响，利用WebAssembly的文件格式构造有效文件，对WebAssembly文件进行分解，再将各个模块之间进行组合和修改，增加了在高级结构而非比特层面的变异。同时，本方案还对WebAssembly的代码段进行了深入的变异，通过改变初始化数据、打乱的合法指令序列来增加变异的多样性，让输入能探索更多的路径。同时，本方案还引入了一个基于有效性的能量调度方案，让模糊测试在有效的种子上花费更多的时间，增加发现程序处理逻辑漏洞的概率。

基于本文的方案，实现了WASMAFL，是一个基于AFL的模糊测试工具，在其基础上增加了 WebAssembly变异的策略和能量调度策略。在我们的评估中，将两者进行了比较，评估结果表明，在给定的24小时内，WASMAFL可以比AFL发现更多的崩溃，还显著提高了路径覆盖率。

总之，本文的主要贡献是对 WebAssembly虚拟机提出了新的模糊测试方案，能够高效地对其进行灰盒模糊测试，同时该方案也适用于其他脚本语言的虚拟机。

2 研究背景

随着业务逻辑越来越复杂，前端开发的代码量变得越来越大，然而由于JavaScript动态类型语言的限制，造成了严重的性能瓶颈，因此WebAssembly应运而生。WebAssembly[9]是一种体积小、加载快、可移植并且兼容Web的全新二进制格式，可以很方便地将C、C++和Rust等低级语言的代码以接近原生性能的速度运行在浏览器等本地客户端中。同时，WebAssembly也被新兴的区块链技术所看好，被称为“区块链 2.0”的以太坊[10]计划使用WebAssembly虚拟机取代目前的 EVM，被称为“区块链 3.0”的EOS[11]选用了WebAssembly虚拟机作为合约的执行引擎。

EOS作为最具代表性的委托股权证明DPoS平台和第一个去中心化的操作系统，近年来发展迅速，是全球最活跃的社区之一。EOS采用WebAssembly作为智能合约的执行语言。智能合约[12]是一种以信息化方式传播、验证或执行合同的计算机协议，允许在没有第三方的情况下进行交易，这些交易可追踪且不可逆转。由于智能合约可以由任何人发布，因此攻击者可以通过构造恶意合约来对区块链平台进行攻击。同时，由于区块链平台去中心化的特点，单个节点的漏洞会导致成千上万的节点遭到攻击，甚至在传统软件漏洞领域被认为相对危害较小的拒绝服务漏洞，在区块链网络中则可能引发整个网络瘫痪。2018年国内安全公司360发现了 EOS节点的远程执行任意代码，即可以通过远程攻击，直接控制和接管 EOS上运行的所有节点。因此针对区块链合约执行的安全研究尤为重要。

3 系统概述

针对传统灰盒测试对 WebAssembly二进制虚拟机进行漏洞挖掘中存在的问题，本文提出了新的针对 WebAssembly二进制虚拟机的模糊测试方案，同时基于该方案我们实现了漏洞挖掘系统WASMAFL。本章将先对该系统的总体设计进行介绍，再阐述每个组件的设计方案和实现细节，以及各模块之间如何在系统中协调工作，最终实现针对WebAssembly虚拟机的高效模糊测试。

本文针对传统灰盒模糊测试中随机变异带来的低效问题，提出了分层变异算法，通过对段表的组合和指令的比特变异，来实现变异的随机性。接着方案通过指令修正来保证文二进制文件的合法性，生成更有可能触发程序中难以到达路径的测试用例。最后方案在模糊测试的过程中引入了基于合法性的能量调度策略，根据种子的合法性来分配种子的执行时间和变异次数，保证优秀的种子能得到更充分地测试。

WSAMAFL基于AFL进行拓展和修改，其中WASMAFL增加了三个组件，分别是WebAssembly段表组合变异模块、指令变异模块和指令合法性修正模块，同时在对种子进行执行时间分配时，我们引入了基于合法性的能量调度模块。总体架构如下图1所示。用于文件合法性检查的指令修正模块是独立的，和模糊测试器解耦，这样方便更灵活地增加其他规则，以及将算法应用到其他虚拟机对象中。

标准的 WebAssembly模块[13]是由一系列具有特定功能的段结构组成的，段结构中存放着用于描述模块功能和属性的信息，如图2所示。同时模块还定义了一系列用于存储静态资源的索引空间，索引空间内的资源可以由模块中定义的各类指令及相关段结构来进行引用。

图1 WASMAFL架构

3.1 分层变异算法

WebAssembly二进制遵守严格的格式，使用随机变异方法的盲目模糊测试策略会导致大量无效的测试用例并且降低模糊测试效率。因此，为了使得生产的测试用例更有针对性，更有可能满足程序对数据结构和逻辑判断的要求，我们提出了分层变异的策略，通过段表组合和指令变异相结合的方式，来改变虚拟机内存中控制流和数据流的信息，从而对虚拟机进行更充分的测试。分层变异后生成的测试样例具有高度结构化的特征，不会使得程序在合法性检查阶段就退出测试。同时变异后的种子文件具有更加丰富的语义和随机性，能够测试到不符合逻辑的指令流程和数据处理，使得对虚拟机的测试更为充分和全面。

变异过程分为两个部分，分别是对模块的各个段表之间进行组合变异，以及对模块代码段的函数指令进行变异。模糊测试先进行模块段表层的组合变异，再进行段表组合变异和代码段指令变异相叠加的混合变异。

3.1.1 对模块的各个段表之间进行组合变异

段表间的组合变异本质上是通过WebAssembly的模块结构、数据格式等先验知识，来指导并改善测试用例的生成。根据上一章对WebAssembly格式的介绍，我们知道WebAssembly模块由多个段表组成，其中某些段表为模块必须的段表，有且仅有一个，另一些段表则为非必须的段表，通常这些段表通常是虚拟机构造内存模型和上下文执行环境的数据来源，通过对段表的组合变异，可以测试虚拟机是否按照标准进行实现，同时可以检测出段表在不同的上下文环境中，是否存在安全漏洞。这个阶段的变异通过对段表进行合理组合，分别为删除、添加、替换和篡改四类操作。

图2 WebAssembly二进制段表组成示例

（1）段表删除

删除操作以段表为单位，从给定的种子文件中随机选取一个段，只要该段不是仅有的代码段则对其进行删除。例如，随机选择模块的Start段，标准规定在一个WebAssembly模块中只能设置一个Start段，但是因为其不是仅有的代码段，则对其删除，即将 Start段对应的字节部分进行移除，生成新的测试样例。在段表的删除操作中需要注意的是，由于要对虚拟机的指令处理逻辑进行深入的测试，因此需要保证 WebAssembly模块具有实际的语义，所以我们需要保留至少一个代码段，如果模块中存在多个代码段则可以对代码段进行删除。

图3 段表删除操作

（2）段表插入

同理，段表的插入也是以段为单位。对给定的种子文件s1，从其他种子文件中随机选择另一个种子文件s2，选取s2中的随机段，将其插入到s1的模块中，插入的位置不能破坏s1原有的段表结构，即只能插入在原有的任意段表之前或者之后。和段表删除操作不同的是，插入的段表可以是代码段。

图4 段表插入操作

（3）段表替换

段表替换是段表层变异中相对复杂的操作。和段表插入的操作类似的，先选择两个种子文件s1和s2，接着从种子文件s2中选取任意的段表，替换种子文件 s1中对应的段表，生成新的种子文件。需要注意的是，进行替换的段表必须是相同的段表，例如我们随机选取了s2中的start段，想对s1中的start段进行替换，但是s1中不存在start段，那么我们则需要重新选择s2中的其他段表，如果选择的次数超过三次，则放弃此次的替换操作。和插入操作一样，替换操作也不能破坏原有种子文件 s1的模块段表结构。

图5 段表替换操作

（4）段表篡改

段表篡改是针对模块的自定义代码段，根据我们的观察，虚拟机在对自定义段表的处理容易出现崩溃，因此在段表层的变异操作中，我们特地引入了段表的篡改。对于给定的种子文件s，从中任意选择一个段表，将其段表的标识变为自定义段表的标识。例如，对于种子文件s，我们将其type段的标识1变为0，从而该段就变成了自定义段。

图6 段表篡改操作

段表层的变异是在保证模块基本合法性的前提下，尽可能地丰富虚拟机在执行模块时的上下文环境。同时，变异过程也不完全遵守 WebAssembly的标准规定，因此能在模糊测试的过程中验证虚拟机的实现规范。

3.1.2 对模块代码段的函数指令进行变异

段表层的重组变异可以改变虚拟机的内存初始化状态和程序上下文数据，但是虚拟机主要的功能在于对代码段的指令逻辑进行执行。所以在完成段表层的重组后，我们单独对模块的代码段进行变异。

WebAssembly模块的代码段由函数及其指令组成，指令类似于汇编指令，由操作码和操作数组成。我们观察到，在传统模糊测试变异中，如果对指令的操作码进行比特变异，会产生两种结果：变异破坏了指令的合法性，即将指令变成了非法指令，当虚拟机执行到该非法指令会直接报错退出。而如果将指令变异成了其他合法指令，虚拟机也会因为操作数中可能存在的零字节以及编码解析等问题退出执行，导致能够连续正常解析的指令数较少。另一方面，从指令操作数变异的层面上来看，只有少数的变异是有意义的。例如，对于常量指令i32而言，后面跟着的常量的变化大部分可能无法改变程序执行的分支，但是如果是常量的临界值，则可能会导致虚拟机在处理数值时发生溢出。

综上，为了保证代码段变异的充分性，我们在代码段使用比特的粒度进行变异，变异操作包括翻转、替换、算术加减、随机比特变换删除、复制增加等AFL的变异操作。同时，为了减少非法指令造成的退出，我们通过指令修正的方式，保证虚拟机对指令进行完整的解析。

图7 代码段比特变异

3.2 指令合法性修正

上文提到对代码段的比特层面的变异会导致虚拟机在遇到非法指令时退出，因此我们设计了一个优化方案，再使用传统的比特变异方法对代码段数据进行变异后，再对指令进行修正。

指令修正的核心思想是将指令的非法操作码进行NOP指令替换，将指令的非法操作数修改成最大临界值。指令修正模块对变异后的文件进行扫描，识别出变异导致的非法指令位置，根据该位置是指令操作码还是操作数来进行相应的操作。如果识别出是非法操作数，则通过NOP指令进行替换，使得虚拟机能执行后面的逻辑。WebAssembly的操作数通过有符号LEB128、无符号LEB128等进行编码，如果识别出是操作数，则根据操作码对应的操作数编码类型，将操作数改为最大值。

图8 指令合法性修正

指令修正能让虚拟机正常解析的指令数变多，执行的逻辑更多样、更深入，因此，能够提高模糊测试过程中的代码覆盖率。

3.3 基于合法性的调度策略

模糊测试的过程中需要反复选择种子进行变异，如何从语料库中选择有效的种子是模糊测试中的重要课题。通过良好的种子选择策略，模糊器可以优先考虑更有用的种子，包括覆盖更多代码并更有可能触发漏洞，同时减少重复执行同一路径的浪费并节省计算资源。我们将为种子文件分配的执行时间称为种子的能量，能量调度策略决定了在模糊测试过程中为哪些种子分配更多的执行时间和机会。

在 AFL中将能量分配给较小的种子，这样可以提高执行的速度。AFLfast[11]则将更多的能量分配给执行低频路径的种子。本文提出了一种新的能量调度策略，基于文件变异的有效性来分配能量。如果对文件变异后的结果修正越少，那么说明文件变异的效果越好，并且种子修正所需要花费的时间也越低。因此，应该分配更多的能量给这些种子。通常来说，我们会认为文件变异的有效性是一个布尔值，即变异是有有效的或者无效的。但是这里我们使用一个比例来衡量文件变异的有效性。我们将文件变异的有效性定义成修正操作的比例。

对于给定的种子s，基于变异有效性的能量调度prob(s)的分配如下：

其中，t是指令修正的次数，当指令的修正次数大于最大值MAX时，我们认为初始的变异造成的无效文件较多，将对其分配较低的能量，当指令修正的次数小于最大值，则根据修正次数与最大值的差值和比例进行分配。

指令修正次数的最大值是通过实验进行设置，是一个经验数值。同时，在模糊测试的初始阶段，可以通过选项对其进行设置。我们收集了20个较为流行的合约文件进行测试，发现一次变异需要修正的次数超过50，则会显著降低测试的速度。因此，本文选择的最大修正次数为50。

4 实验评估

根据本文的方案，我们在AFL的基础上实现了WASMAFL，将工具与原版AFL_2.52进行对比，分别对EOS的Webassembly虚拟机进行了24个小时的模糊测试。我们对比了新方案和原有方案下发现路径情况和产生的崩溃数量，从表2中我们的可以发现，在路径覆盖率上，有了 35%的提升。在崩溃的产生数量上，WASMAFL比AFL多了6.17%。同时，我们对导致程序崩溃的样本进行分析，根据样本产生崩溃的位置和原理进行了分类，发现AFL只找到了1种段错误类型的崩溃，而WASMAFL工具则找到了2种段错误类型的崩溃。

表1 模糊测试执行结果对比

本文的方案旨在引导程序向更深的路径进行探索，因此表2对两个工具的路径深度和分支覆盖率进行比较，发现路径深度提高了两层，同时分支覆盖率也相应地提高了34%。由于新的方案在执行过程中引入了文件的结构识别和合法性检查，因此实验对执行速度进行了比较，发现执行速度的降低在可接受范围内。

表2 模糊测试执行效果对比

同时我们还对24小时内总路径数和路径深度随时间变化的曲线进行了绘制，从图9可以看出WASMAFL能比AFL更快地到达更深的路径，到达更深路径后总路径数的增长WASMAFL快于AFL。

图9 执行24小时总路径变化曲线

本文通过对 WebAssembly虚拟机的模糊测试方案进行了设计，提出了分层变异算法，最后和通过工具AFL进行测试，通过24小时的对比验证，与原AFL工具效果进行对比评估分析， 表明该方案能够提升模糊测试的覆盖率和崩溃发现数量。

5 结束语

本文提出了一种针 WebAssembly虚拟机的模糊测试方案。通过研究WebAssembly各模块对执行的影响，利用WebAssembly的文件格式构造有效文件，对WebAssembly文件进行解析，再将各个模块之间进行组合和修改，增加了在高级结构而非比特层面的变异。同时，本方案还对WebAssembly的代码段进行了深入的变异，通过改变初始化数据、打乱的合法指令序列来增加变异的多样性，让输入能探索更多的路径。同时，本方案还引入了一个基于有效性的能量调度方案，让模糊测试在有效的种子上花费更多的时间，增加发现程序处理逻辑漏洞的概率。

基于本文的方案，实现了WASMAFL，是一个基于AFL的模糊测试工具，在其基础上增加了 WebAssembly变异的策略和能量调度策略。在我们的评估中，将两者进行了比较，评估结果表明，在给定的24小时内，WASMAFL可以比AFL发现更多的崩溃，还显著地提高了路径覆盖率。