#  WRTester: Differential Testing of WebAssembly Runtimes via Semantic-aware
Binary Generation

Shangtong Cao  Beijing University of Posts and TelecommunicationsChina ,
Ningyu He  Peking UniversityChina ,  Xinyu She  Huazhong University of Science
and TechnologyChina ,  Yixuan Zhang  Peking UniversityChina ,  Mu Zhang
University of UtahAmerica and  Haoyu Wang  Huazhong University of Science and
TechnologyChina

###### Abstract.

Wasm runtime is a fundamental component in the Wasm ecosystem, as it directly
impacts whether Wasm applications can be executed as expected. Bugs in Wasm
runtime bugs are frequently reported, thus our research community has made a
few attempts to design automated testing frameworks for detecting bugs in Wasm
runtimes. However, existing testing frameworks are limited by the quality of
test cases, i.e., they face challenges of generating both semantic-rich and
syntactic-correct Wasm binaries, thus complicated bugs cannot be triggered. In
this work, we present WRTester, a novel differential testing framework that
can generated complicated Wasm test cases by disassembling and assembling of
real-world Wasm binaries, which can trigger hidden inconsistencies among Wasm
runtimes. For further pinpointing the root causes of unexpected behaviors, we
design a runtime-agnostic root cause location method to accurately locate
bugs. Extensive evaluation suggests that WRTester outperforms SOTA techniques
in terms of both efficiency and effectiveness. We have uncovered 33 unique
bugs in popular Wasm runtimes, among which 25 have been confirmed.

††copyright: none

##  1\. Introduction

WebAssembly (Wasm), a low-level bytecode format, was proposed by several
Internet giants in 2017 (Haas et al., 2017). Due to its excellent portability,
native-like speed, compacted size, and safety guarantee, Wasm is gaining
growing popularity. In 2022, more than 97% existing browsers have supported
Wasm. Beyond web browsers, Wasm has been favoured in a wide range of domains,
including mobile apps, blockchain, and IOT, etc. Wasm can be regarded as the
compilation target for almost all main-stream high-level programming
languages, e.g., C, C++, Go, and Rust (Zakai, 2011; MDN, 2023; TinyGo, 2023).
Wasm binaries are executed in Wasm runtimes, which is similar to a virtual
machine that serves as an intermediate layer between the WASM binaries and the
underlying system. Currently, lots of Wasm runtimes have been implemented and
actively maintained on GitHub, like Wasmtime (wasmtime, 2023), Wasmer (Wasmer,
2023), and WasmEdge (WasmEdge, 2023).

Wasm runtimes, play a key role in the ecosystem, as it directly impacts
whether Wasm applications can be executed as expected. However, a variety of
Wasm runtime specific bugs have been reported from time to time. For example,
Zhang et al. (Yixuan et al., 2023) have empirically analyzed over 300 real-
world bugs of Wasm runtimes and created a taxonomy of 31 bug categories of
Wasm runtimes. Thus, some fellow researchers in our community proposed to
develop automated methods for detecting bugs in Wasm runtimes. For example,
Jiang et al. (Jiang et al., 2022) have uncovered that Wasm runtimes may cannot
execute the given Wasm binary correctly by adopting coverage-guided fuzzing.
WADIFF (Zhou et al., 2023) further adopted symbol execution to generate lots
of Wasm binaries and conducted differential testing to identify implementation
bugs of runtimes.

Although recent automated testing approaches have shown promising results in
identifying Wasm runtime bugs via Wasm binary generation, they are however
limited by their inability to generate semantically rich binaries (see §2.3),
thus complicated bugs cannot be triggered. For example, WADIFF can only test
the implementation bugs at the single instruction level, as it cannot generate
test cases with a large number of instructions, while real-world Wasm binaries
are indeed much more complex. Specifically, there exist over 430 kinds of
instructions and 13 types of sections with different functionalities in Wasm,
indicating that Wasm is a bytecode format with rich semantics. For
comprehensive testing, it is crucial and necessary to ensure that the
generated Wasm binaries can cover as much semantics as possible. Further, it
is impossible to generate Wasm binaries arbitrarily, as each Wasm binary
should be validated for syntactic correctness before executing, including
stack balance verification etc, which ensures that the generated Wasm binaries
should be syntactic-correct.

This work. We present WRTester, a novel differential testing framework for
Wasm runtimes that can generate syntactic-correct and semantic-rich Wasm
binaries. To achieve this, we have designed a dedicated algorithm to extract
basic elements from real-world Wasm binaries, and randomly assemble them into
Wasm binaries with valid syntax and rich semantics. Based upon this, WRTester
further applies different levels of mutation strategies (e.g, AST-level and
module-level mutation) on generated Wasm binaries to increase their diversity.
WRTester sends the generated Wasm binaries to Wasm runtimes simultaneously to
investigate inconsistent behaviors. As different forms of input binaries that
cause the same inconsistent state may be reported redundantly, which would
result in an excessive amount of generated inputs. Thus, for further
pinpointing the root causes of inconsistencies, we proposed a root cause
identification algorithm that can accurately locate bugs on a function-level
or even instruction-level. Extensive experiments show the superiority of
WRTester over state-of-the-art techniques in both terms of efficiency and
effectiveness, i.e., WRTester can generate 6.0x and 148.8x Wasm binaries that
can lead to inconsistencies over two baseline tools. By applying WRTester to
four representative Wasm runtimes, it has generated over 167K Wasm binaries
that can lead to inconsistencies among Wasm runtimes, which are further
located to 33 unique bugs. With our timely disclosure, 25 bugs has been
confirmed by runtime developers, and 11 of them have been fixed with our aid,
by the time of this writing.

We make the following main contributions in this work:

  * •

We propose WRTester, a novel differential testing framework that can generate
syntactic-correct and semantic-rich Wasm binaries by disassembling and
assembling of real-world Wasm binaries, which significantly increases the
diversity of generated Wasm binaries in terms of semantics.

  * •

We design a runtime-agnostic root cause identification algorithm that can
accurately pinpoint the location of bugs, which significantly eases the burden
of runtime developers for further verification and bug patching.

  * •

WRTester have identified 33 unique bugs that can lead to unexpected behaviors
for mainstream Wasm runtimes, among which 25 have been confirmed and 11 have
been patched with our timely disclosure.

##  2\. Background & Motivation

###  2.1. WebAssembly

WebAssembly (Wasm) is an emerging stack-based binary format that can be
compiled from mainstream high-level languages. Except for the original four
primary data types, i.e., i32, i64, f32, and f64, v128 is introduced in the
recent specification to support SIMD instructions (WebAssembly, 2023c).
Specifically, the leading i, f, and v respectively refer to integers, float
numbers, and vectors, while the following number stands for the length in
bits. Each Wasm binary is composed of 13 sections (WebAssembly, 2023e), and
complex functionalities can only be achieved by coupling sections, e.g.,
implementing a function requires three sections. The type section declares the
function signatures, the code section contains all local variables and the
function body, and the function section keeps a mapping relation from the type
index to the function index. Wasm applies a specific structured control flow.
Instructions in Wasm are divided into code blocks, which can be led by block
or loop. Code blocks can be nested, but the context of an inner code block is
independent to its outer ones. Moreover, there are no goto-like instructions
in Wasm, indicating the control flow cannot be directed arbitrarily. Instead,
br and br_if are used for control flow jumps, whose target has to be the
heading (led by loop) or tailing (led by block) of its outer code block.

Each Wasm binary will be statically verified on its syntactic validity before
executing. The verification mainly focuses on the stack. On the one hand, it
verifies if each instruction can take operands whose types match the ones
defined in the specification. On the other hand, it verifies the stack
balance, i.e., the behavior of each block and function is consistent with its
signature.

###  2.2. Wasm Runtime

Wasm runtime provides an executing environment for Wasm binaries in various
hardware and operating systems (Yixuan et al., 2023). They play a vital role
in supporting Wasm-based functionalities in blockchain platforms (eosio, 2023)
and embedded devices (Wallentowitz et al., 2022), enabling the deployment of
lightweight, high-performance applications in resource-sensitive environments.
Additionally, except for the inefficient interpreting mode, both JIT (Just-In-
Time) and AOT (Ahead-Of-Time) are adopted by some runtimes to improve the
performance. Wasm runtime is also responsible for handling interactions
between Wasm binaries and the external environment. In the early stage, each
runtime has its specific set of compiling tool chains and wrappers for APIs
exposed by the operating systems, which results in a severe compatibility
issue. Thus, WebAssembly System Interface (WASI) (WebAssembly, 2023a) emerges,
which defines the function signatures of each API as well as its behavior.
Currently, WASI is supported by lots of mainstream Wasm runtimes as well as
their compiling tool chains.

###  2.3. Motivation

Improper implementation of Wasm runtimes will significantly hamper the
intentional design goal of Wasm, i.e., security and efficiency. However,
testing the correctness of the implementation of Wasm runtimes is challenging.
Currently, only differential testing, one of the dynamic analysis methods, is
adopted by existing studies (Zhou et al., 2023; Yixuan et al., 2023). This is
because the static verification may be struggled with the complex logic in
runtimes, and the pre-defined rules very likely import false positives.
Differential testing is a widely adopted technique that compares the outputs
or states among different targets (i.e., different implementations of the same
functionality) while giving an identical input. Moreover, it is independent of
oracles, one of the main challenges faced by other dynamic analysis methods,
like grey-box fuzzing. Although differential testing seems to be a promising
approach, there still exist some challenges for detecting bugs in Wasm
runtimes, which can be summarized as follows:

Challenge #1: Generating syntactic-correct and semantic-rich Wasm binaries. As
we mentioned in §2.1, each Wasm binary should be validated for syntactic
correctness before executing. Further, in Wasm, there exist over 430
instructions and 13 types of sections with different functionalities,
indicating that Wasm is a bytecode format with rich semantics. To reach the
goal of comprehensive testing, instead of guaranteeing the syntactic
correctness, it is also crucial and necessary to ensure that the generated
Wasm binaries can cover as much semantics as possible. In other words, the
generated Wasm binaries should be syntactic-correct and semantic-rich. As for
the syntactic correctness, the generated binaries should be stack-balanced,
and the index reference among sections should be correct. As for the semantic
richness, on the one hand, the instructions in the generated Wasm binary
should interact with as many sections as possible. On the other hand, these
instructions should be covered as much as possible during execution at
runtime.

Challenge #2: Error locating to refine Wasm binaries according to root causes.
During the differential testing process, when observing inconsistent results
among different runtimes, it is challenging to pinpoint the root cause on each
case. Specifically, differential testing will generate lots of Wasm binaries,
each of which is composed of at least hundreds of thousands of instructions.
It is hard to locate which function or instruction indeed leads to a bug, even
less pinpointing the root cause. Indeed, many inconsistent results observed
during the testing process are introduced by the same bug. However,
implementing the bug diagnosing processes is challenging because not all Wasm
runtimes come with developed debugging tools. Moreover, handling the
compatibility issue among these runtimes also raises the concern of
scalability.

Limitations of current tools. To the best of our knowledge, only two tools are
available for differential testing Wasm runtimes, i.e., wasm-smith (Alliance,
2023) and WADIFF (Zhou et al., 2023). Specifically, wasm-smith is a Wasm test
case generator proposed by the official community. It randomly selects
instructions while considering the stack balance to guarantee the syntactic
correctness. As for WADIFF, it adopts symbolic execution to generate test
cases for each instruction according to the specification. However, both tools
have certain limitations.

(a) A Wasm binary generated by wasm-smith.

(b) A Wasm binary generated by WADIFF.

Figure 1. Comparison of Wasm binaries.

Specifically, wasm-smith ignores the semantics of the generated Wasm binaries,
hindered by the Challenge #1. As shown in Figure 1(a), the br instruction at
L7 will direct the control flow to L11, i.e., the end of the function. In
other words, instructions between L7 and L11 will be ignored by runtimes.
Additionally, L2 indicates that the results should be an i32 and a f32. To
ensure the stack balance, wasm-smith simply pushes two constant values (L12
and L13) of the corresponding types. This means that this function can be
aggressively optimized to only include the last two instructions.
Consequently, wasm-smith can only generate Wasm binaries composed of lots of
meaningless instructions, which hampers both efficiency and effectiveness of
differential testing.

As for WADIFF, which adopts symbolic execution on the Wasm specification of
each instruction to generate test cases, it can only generate simple Wasm
binaries ($\sim$10 – 100 instructions) to verify runtimes. As shown in Figure
1(b), this Wasm binary verifies the implementation of i32.add. WADIFF follows
the Occam’s Razor principle (Occ, 2023), i.e., following the simplest control
flow and giving only the necessary parameters generated by constraints. In
other word, it is hard for WADIFF to cover complex functionalities among 13
sections within a single Wasm binary. Moreover, it can only generate a finite
number of Wasm binaries after traversing all possible paths for each
instruction, and its random mutation method is likely to generate invalid ones
(Zhou et al., 2023). Last but not least, generating test cases against control
instructions is not supported by WADIFF yet, e.g., call_indirect and loop. In
summary, WADIFF also faces the Challenge #1 we proposed previously.

Our approach. To address these two challenges, we come up with some key ideas.
Specifically, to generate syntactic-correct and semantic-rich Wasm binaries,
we extract AST nodes from existing real-world Wasm binaries and randomly
assemble them in a syntactic-correct way. Moreover, to increase the diversity
of semantics, we also import some mutations on AST-level and module-level,
like introducing SIMD instructions. As for the error locating issue, we
implement a static instrumentation based error locating algorithm, which is
runtime-agnostic to perform the function-level or even instruction-level root
cause localization.

##  3\. Approach

Figure 2. The architecture and workflow of WRTester.

###  3.1. Overview

The workflow of WRTester is depicted in Fig 2, which can be divided into three
phases, i.e., corpus preparing, binary generating & mutating, and differential
testing. Specifically, in the corpus preparing phase, based on all collected
real-world Wasm binaries, WRTester firstly parses the corresponding ASTs and
extracts valid sub-trees from them. Then, in the binary generating & mutating
phase, WRTester randomly assembles AST sub-trees as a valid Wasm binary. To
enhance the diversity of the generated Wasm binaries, WRTester performs AST-
level and module-level mutations. Last, in the final differential testing
phase, WRTester sends Wasm binaries to Wasm runtimes simultaneously to
investigate inconsistent behaviors. Taking advantage of static
instrumentation, WRTester can conduct a runtime-agnostic error locating on
Wasm binaries that lead to such inconsistent behaviors. We detail these three
phases in the following.

###  3.2. Corpus Preparing

Instead of directly generating Wasm binaries, we decide to take real-world
Wasm binaries that possess rich semantics as basic elements to assemble Wasm
binaries. To be specific, we extract their abstract syntax tree (AST), split
them into sub-trees, and assemble them in a syntactic-valid way. Thus, the
corpus preparing phase can be divided into steps including context extracting,
AST parsing, and post-processing, which are depicted in Algorithm 1.

Algorithm 1 The corpus preparing algorithm.

1:$instrs$ \- list of instructions, $binary$ \- the Wasm binary

2:$ASTs$ \- the corpus, composed of a list of AST

3:function CorpusPreparing($instrs$, $binary$)

4: $ASTs\leftarrow\textsc{InitializeList}()$

5: for each $instr\in instrs$ do

6: $context\leftarrow\textsc{GetContext}(instr,binary)$ $\triangleright$
§3.2.1

7: if $instr.opcode\in[block,loop,if]$ then $\triangleright$ §3.2.2

8: $node\leftarrow Node(instr,context)$

9: $node.child\leftarrow\textsc{CorpusPreparing}(instr.args,binary)$

10: else

11: $node\leftarrow Node(instr,context)$

12: end if

13: $params\leftarrow context.type.params$

14: while $params$ do

15: for each $preNode\in\textsc{Reversed}(ASTs)$ do

16: $node\leftarrow\textsc{AppendChild}(node,preNode)$

17: $ASTs.pop()$

18: $params.pop()$

19: end for

20: end while

21: $ASTs.append(node)$

22: end for

23: $ASTs\leftarrow\textsc{PostProcessing}(ASTs)$ $\triangleright$ §3.2.3

24: return $ASTs$

25:end function

####  3.2.1. Context extracting.

Wasm is a statically typed language, each Wasm binary will be comprehensively
verified syntactically and semantically before being executed. Specifically,
on the syntactic side, Wasm is a stack-based language. Therefore, each
instruction will consume and append a certain number of operands from and onto
the stack. For example, i32.load requires an i32 operand as the address and
pushes the retrieved data onto the stack. For some instructions, the number of
required arguments and return values are variable, like call and block. In
these cases, guaranteeing the stack balance needs to consider the signature of
the callee and all included instructions, respectively. On the semantic side,
a Wasm binary is composed of 13 sections with different functionalities.
Without considering the semantic validity, even a stack-balanced Wasm binary
cannot pass the verification yet. For example, if we have assembled a function
foo, who invokes bar, we should guarantee the existence of bar: not only its
implementation in the code section, but also its function signature declared
in the type section and the mapping relation kept in the function section.

Table 1. Instruction types and the representations, as well as the stack type
and semantic constraint should be guaranteed.

Instruction | Stack Type | Semantic Constraint
---|---|---
Numeric Instructions
i32.const c | $[]\rightarrow[i32]$ |
i64.add | $[i64,i64]\rightarrow[i64]$ |
Vector Instructions
v128.const c | $[]\rightarrow[v128]$ |
i32x4.add | $[v128,v128]\rightarrow[v128]$ |
Parametric Instructions
select | $[t,t,i32]\rightarrow[t]$ |
drop | $[t]\rightarrow[]$ |
Variable Instructions
local.get n | $[]\rightarrow[t]$ |  $\texttt{Local}\ v$ $\texttt{idx}_{v}=n$ $\texttt{type}_{v}=t$
global.set n | $[t]\rightarrow[]$ |  $\texttt{Global}\ v$ $\texttt{idx}_{v}=n$ $\texttt{type}_{v}=t$
Memory Instructions
i32.load memarg | $[i32]\rightarrow[i32]$ |  $\texttt{page}_{addr}\in[min,max]$
Table Instructions
table.get n | $[i32]\rightarrow[t]$ |  $\texttt{Table}\ tb$ $\texttt{idx}_{tb}=n$
Control Instructions
call n | $[t^{*}]\rightarrow[t^{*}]$ |  $\texttt{Function}\ f$ $\texttt{Signature}\ s=[t^{*}]\rightarrow[t^{*}]$ $\texttt{signature}_{f}=s$ $\texttt{idx}_{f}=n$
call_indirect n | $[t^{*},i32]\rightarrow[t^{*}]$ |  $\texttt{IndirectFunction}\ f$ $\texttt{Signature}\ s=[t^{*}]\rightarrow[t^{*}]$ $\texttt{signature}_{f}=s$ $\texttt{idx}_{s}=n$
block n | $[t^{*}]\rightarrow[t^{*}]$ |  $\texttt{Signature}\ s=[t^{*}]\rightarrow[t^{*}]$ $\texttt{idx}_{s}=n$

To solve this challenge, we firstly categorize Wasm instructions into seven
groups according to their operations on the stack, i.e., stack type, and the
corresponding must-satisfied semantic constraints. Table 1 illustrates some
representatives of each group. Specifically, the stack type of numeric
instructions is fixed, and there are no extra semantic constraints on them.
Vector instructions are similar to them, but are specifically designed for the
vector type (see §2.1). In addition, the stack type of parametric instructions
may vary. For example, drop consumes an operand from the stack whichever its
type. Thus, the stack type of drop is $[t]\rightarrow[]$, where t is a
wildcard and refers to any type. The other four types of instructions need
semantic constraint. For example, $\texttt{local.get}\ n$ has two pieces of
constraints: for a local variable $v$, its index and type should be $n$ and
$t$, respectively. As for memory and table instructions, they are respectively
responsible for interacting with the memory and table area. They also limited
by the corresponding semantic constraints. For instance, i32.load requires the
target address must be within the valid address range, i.e., $[min,max]$.
Table instructions require the corresponding index should be existed and
matched. In Wasm, two kinds of function invocations exist, through call and
call_indirect, respectively. They have subtle differences in semantic
constraints. For call n, it directly invokes the n-th function, while the n in
call_indirect n indicates the index of the function type declared in the type
section. The index of callee is retrieved from the stack, i.e., the second i32
of the parameters of its stack type.

To build the corpus, the algorithm takes a list of instructions and its
corresponding binary as input. While going through the instruction list (L3),
the algorithm extracts context information at L4. Specifically, for each
instruction, it not only concretizes the stack type according to the context
provided by the binary, but also binds the corresponding semantic constraints
to the instruction. For example, when encountering a call instruction, whose
number and type of consumed elements on the stack are not statically
determined, the algorithm extracts its immediate number $n$ and obtains its
function signature by indexing through the function and type section. To this
end, the $[t^{*}]\rightarrow[t^{*}]$ can be concretized, like
$[i32,i32]\rightarrow[i64]$. In summary, the algorithm can bind the necessary
context information to each instruction according to stack type and semantic
constraints declared in Table 1.

####  3.2.2. AST parsing.

Parsing ASTs of real-world Wasm binaries is necessary before extracting sub-
trees from them to build the corpus. Taking advantage of the extracted context
as we mentioned in §3.2.1, a Wasm binary can be easily parsed to the
corresponding AST. To better illustrate how this process happens, Fig. 3 to
Fig. 3 show a factorial function written in C, the instruction list of the
compiled Wasm binary, and the corresponding AST, respectively. We detail the
process combining with Algorithm 1. As we can see from Fig. 3, the compiled
instruction list is quite flat, which is hard to identify the AST structure.
Therefore, the algorithm firstly identifies if current instruction is any of
block, loop, or if (L5 to L7 in Algorithm 1) to recursively build AST as only
sub-trees led by these instructions can be nested. Then, the algorithm
constructs the AST according to the stack type, as shown from L11 to L20 in
Algorithm 1. For example, in the instruction list, the first instruction,
i.e., i32.const 5, takes no elements from the stack, thus it jumps over the
iteration at L12 and is pushed to $ASTs$ at L19. Then, its following local.set
0 takes an element from the stack as shown in Table 1. Thus, the while-loop at
L12 is executed once. Within the while-loop, the last AST node, i.e., the
previous i32.const 5 is set as the child for local.set 0, which will then be
pushed to $ASTs$. Even the algorithm meets call, such an instruction with
variable number of arguments, its context is determined in §3.2.1 by
retrieving the callee’s function signature, thus the AST can be built without
any issue. Due to the recursive construction as shown at L7 in Algorithm 1,
the block (L7 of Fig. 3) will lead the loop (L8 of Fig. 3), within which it
implements the factorial calculation as shown in the C source code.
Consequently, after traversing the factorial function, $ASTs$ is composed of
four nodes, each of which can be regarded as a root of a sub-tree of the AST
(Fig. 3).

####  3.2.3. Post-processing

As we can see from Fig. 3, the 1st and 2nd sub-trees are quite similar. In
other words, if we take both of them into valid elements in the final corpus,
the generated Wasm binaries may be duplicated. Therefore, in the post-
processing stage, we try to minimize the size of the corpus to avoid
generating duplicated Wasm binaries. In general, for each sub-tree, we firstly
remove the immediate number of each instruction. Then, we adopt a DFS on sub-
trees to identify the ones with identical instruction dependent relationship.
Take Fig. 3 as an example, because both 1st and 2nd sub-trees have local.set
as the root node of i32.const, only one of them will be retained.

(a) The source code in C.

(b) The compiled bytecode.

(c) The parsed AST of the Wasm bytecode.

Figure 3. A concrete example of AST parsing.

###  3.3. Binary Generating & Mutating

Given the sub-trees extracted from ASTs of real-world Wasm binaries as corpus,
as well as the extracted context information on each instruction, WRTester can
generate valid Wasm binaries efficiently and effectively. Additionally,
WRTester also conducts mutations on these generated binaries to bring in more
diversities. The binary generating and binary mutating are detailed as
follows.

####  3.3.1. Binary generating

We generate a Wasm binary following a bottom-up way, i.e., building a valid
entry function, maintaining necessary invoking relation, and supplementing
extra semantics.

Step I: Building a valid entry function. First of all, we need to generate a
function body of an entry function. In general, we randomly sample a specified
number of AST sub-trees from the corpus. Then, we concatenate and transform
them into a sequence of Wasm instructions, which is regarded as the body of
the entry function. In Wasm, a function is composed of not only a set of
instructions as its implementation, but also some local variables that can be
accessed within the current function. Thus, WRTester adds five local variables
for the entry function, typed as i32, i64, f32, f64, and v128 (see §2.1) and
indexed from 0 to 4, respectively. For each variable instruction in the newly
generated entry function, WRTester gets their stack type mentioned in Table 1
and conducts necessary rewriting on the immediate number. For example, if a
local.get is bound an operand with type i64, its immediate number will be
rewritten as 1. Finally, according to the signature of the entry function,
WRTester appends necessary local.get before the final return instruction.
Consequently, WRTester generates an entry function composed of five local
variables and a list of instructions, where the immediate number of each
variable instruction is rewritten to the index according to its bound stack
type extracted in Algorithm 1.

Step II: Maintaining necessary invoking relation. Except for considering the
validity intra-functionally when building the entry function, the inter-
functional validity should also be ensured, i.e., maintaining function invoke
relations from the entry function. In Wasm, only two instructions can invoke
function calls, i.e., call and call_indirect. Thus, WRTester traverses each
instruction. When meets call, WRTester generates a callee according to its
bound concretized stack type and semantic constraint. Instead of generating a
callee with an empty function body whose aim is solely maintaining the stack
balance, the callee is adopted the same method as we mentioned in the Step I.
In other words, the callee has a functional function body, and it may
recursively generate its callees. As for call_indirect, maintaining its
invoking relation requires a little extra effort. Specifically, the callee of
call_indirect is determined at runtime. As shown in Fig 4, WRTester firstly
generates a callee as its handling on call. Then, it inserts the function
index into the function table to make the indexing process raise no
exceptions. Last, to make sure the call_indirect can actually be guided to the
newly generated callee, WRTester inserts a drop and an i32.const c before it,
where the c is the index.

Figure 4. The concrete steps of WRTester on maintaining necessary invoking
relation of the callindirect instruction.

Step III: Supplementing extra semantics. For a Wasm binary, only focusing on
functions cannot fully guarantee its semantic correctness because the
functionalities are decoupled into all 13 sections. Thus, extra semantics
should be supplemented. Take the data section as an example, which is used to
initiate the linear memory of Wasm binary. To avoid memory-related
instructions from raising exceptions, WRTester goes through the memory
instructions of each function to determine the maximum addressing range
depending on its semantic constraint. Within the range, WRTester will fill
random data into the data section. Similarly, for the table and element
sections that make up the indirect function table of Wasm, we construct them
based on the context of table instructions in the binary. This ensures correct
executions on table instructions. As for the global section, whose elements
can be accessed by all functions, we adopt the same strategy as inserting
local variables in functions. That is, WRTester only inserts five global
elements with five different type in the global section, and rewrites the
immediate numbers of all global.get and global.set instructions according to
their bound stack type to the corresponding index.

####  3.3.2. Binary mutating

Though a substantial number of Wasm binaries can be generated through the
methods we mentioned in §3.3.1, there are two shortcomings. On the one hand,
it is still difficult to increase the code coverage of tested runtimes through
assembling ASTs from existing Wasm binaries. On the other hand, due to the
ongoing evolution of Wasm, it is hard to verify the implementation of runtimes
on new features. For instance, SIMD instructions is newly introduced to handle
vectors, and the number of SIMD related instructions is 236, far more than
instructions defined in Wasm 1.0 (WebAssembly, 2023d).

To address these shortcomings, we propose a set of mutation strategies to try
to comprehensively test Wasm runtimes and uncover hidden issues in them.
Generally speaking, the mutation strategies can be divided into AST-level
mutation and module-level mutation, while the former one can be integrated
into the Step I and Step II in §3.3.1 and the latter one can be performed when
conducting the Step III in §3.3.1.

AST-level mutation is to mutate the instructions of ASTs in the corpus we
collected, and its purpose is to extend the semantics of AST, so as to further
improve the code coverage of runtime testing.

  * •

Mutate immediate numbers. Improper processes on corner cases are more likely
to trigger bugs or even vulnerabilities (Yixuan et al., 2023; Johnson et al.,
2023; Michael et al., 2023). Therefore, part of the mutation resources is put
on the immediate number of instructions. For example, for constant
instructions, like i32.const, WRTester tries to replace the original operand
with the value near the boundary, e.g., $2^{32}-1$. Furthermore, for memory
load and store instructions, WRTester attempts to mutate the offset and
alignment arguments.

  * •

Mutate operations. The remaining mutation resources are put on the operations
themselves of instructions. Generally speaking, to support SIMD instructions,
WRTester conducts mutations on numeric and memory instructions to the SIMD
ones with similar semantics. For example, in Fig 5, the original
implementation (left side) is i32.const followed by an i32.load. After
mutating both of them into SIMD instructions with similar semantics, the
mutated implementation (right side) is v128.const followed by a v128.load.
However, we can observe that the type of the consumed element of v128.load
mismatches the one pushed by v128.const. Fortunately, Wasm specification
provides a set of instructions to convert the element type (WebAssembly,
2023b). Thus, WRTester adds an extra i32x4.splat to convert v128 to i32 to
make the mutated implementation valid.

We further design a strategy to increase the diversity of ASTs. Specifically,
as illustrated in Table 1, instructions may have identical stack type, like
i32.add and i32.sub. Arbitrarily conducting interchanges among these
instructions will not break the stack balance. Therefore, WRTester randomly
replaces instructions to others according to the stack type.

Figure 5. Mutating normal instructions to the SIMD ones.

Module-level mutation. In addition to the inconsistency in the implementation
of instructions, deficiencies in the runtime’s verification on the whole Wasm
module can also pose security risks. For example, incomplete memory boundary
checks may lead to sandbox escapes. Thus, we also perform module-level
mutations during the Step III in §3.3.1. Specifically, Cao et al. (Cao et al.,
2023) has summarized five functionalities in Wasm, i.e., Global, Import &
Export, Memory, Function, and Custom. Except for the last functionality, which
has no association with the semantics of a Wasm binary, against each of the
others, we have designed a specific mutation strategies, which are detailed in
the following.

  * •

Global. Except for the data type, each global variable possesses various other
attributes, such as whether the variable is mutable. We randomly mutate the
attributes of each global element.

  * •

Import & Export. Wasm can import or export various semantics, such as
functions, memory, and even global variables. WRTester randomly adds import
and export items (in the import and export sections) to the generated
binaries.

  * •

Memory. As we mentioned in the Step III in §3.3.1, the data section is
initiated with random data. Except for that, Wasm still requires all memory
accesses should be within the valid address limitation. Thus, WRTester mutates
the address limitation to test the correctness of runtime’s memory boundary
checks.

  * •

Function. Part of this functionality is related to the code section, which is
handled by §3.3.1. Thus, WRTester primarily mutates the table section. Similar
to the memory section, the table section determines the range of the indirect
function table, which is used for indexing by call_indirect. To this end, the
correctness of runtime’s boundary checks can be covered.

###  3.4. Differential Testing

During differential testing, we firstly should identify the inconsistency
among runtimes. Additionally, due to the large number of Wasm binaries being
fed to runtimes, many inconsistencies might be caused by the same underlying
issue. Effectively locating the root cause can improve the efficiency of the
whole testing process. We next explain how we address these issues.

####  3.4.1. Inconsistency Identification

During the differential testing process, we cannot simply take different
output as inconsistency because some of them are triggered by non-bug factors,
like differences in design principles and implementational distinctions.
First, Wasm is still under development, thus runtimes may have different
levels on supporting the Wasm specification. For example, some runtimes may
not support SIMD instructions yet, resulting in an unsupported prompt when
encountering Wasm binaries with SIMD instructions. Second, the output of
various runtimes is also influenced by their implementation styles. For
example, some runtimes may consider i32 and i64 integers as signed when
outputting them, while other runtimes may treat them as unsigned. The Wasm
specification does not explicitly define these behaviors. Third, different
runtimes adopt diverse ways to handle error messages. For example, when
encountering an out-of-bounds table access, some runtimes may only output
undefined element, while other runtimes provide more specific reasons, such as
out of bounds table access.

Figure 6. The types of inconsistencies during execution.

To reduce the number of false positives, i.e., inconsistent behaviors due to
the above non-bug reasons, we give a clear definition of inconsistent behavior
as shown in Fig. 6. Specifically, we define three kinds of inconsistent
behaviors based on the lifetime of a Wasm binary being executed by runtimes,
namely compilation failure (CF), runtime failure (RF), and unexpected output
(UO). These three types are mutually exclusive and cover all inconsistent
behaviors we identified during the differential testing. The first two types
happen when runtimes encounter unexpected errors during the corresponding
stage. As the name suggests, the compilation failure occurs when the Wasm
binary is compiled and instantiated. The Wasm runtime will crash, that is, the
input Wasm binary will not be executed at all. When Wasm binaries are
executed, runtimes may still crash, usually due to raised exceptions, which is
named as runtime failure. We identify this inconsistency behavior by the
classes of raised exceptions. The last one, i.e., unexpected output, can only
be observed when a Wasm binary is executed.

As for identifying which runtime indeed has an unexpected behavior, we take
the majority rule as other differential testing studies adopt (Zhou et al.,
2023), i.e., we consider the behavior generated by most runtimes when
executing a binary as correct, while runtimes exhibiting other types of
behavior are considered potentially buggy. For example, if a binary encounters
out-of-bounds memory access in three runtimes and another runtime prompts an
indirect function table related error, the latter runtime is considered
potentially buggy.

####  3.4.2. Root Cause Locating

Different Wasm binaries may trigger the same bug in Wasm runtimes, thus
performing an error locating is necessary to deduplicate these Wasm binaries
according to the root causes of triggered inconsistency. To this end, we
propose a runtime-agnostic binary instrumentation method for root cause
localization, which is detailed in Algorithm 2, consisting of function-level
localization and instruction-level localization.

Algorithm 2 The error locating algorithm.

1:$binary$ \- inconsistent binary, $type$ \- inconsistent type

2:$funcid$ \- the index of inconsistent function. $instr$ \- the inconsistent
instruction

3:function FuncLocating($binary,type$)

4: $logsList\leftarrow\textsc{FuncInstrumentation}(binary)$

5: $funcid\leftarrow None$

6: for each $logs\in logsList$ do

7: if $\textsc{CompareFuncLogs}(logs)=False$ then

8: $funcid\leftarrow\textsc{FindInconsistentFunc}(logsList)$

9: end if

10: end for

11: if $type=OUTPUT$ then

12: $instr\leftarrow InstrLocating(binary,funcid)$

13: return $instr$

14: else

15: return $funcid$

16: end if

17:end function

1:$binary$ \- inconsistent binary, $funcid$ \- the index of inconsistent
function

2:$instr$ \- The inconsistent instruction

3:function InstrLocating($binary,funcid$)

4: $logsList\leftarrow\textsc{InstrInstrumentation}(binary,funcid)$

5: $instr\leftarrow None$

6: for each $logs\in logsList$ do

7: if $\textsc{CompareInstrLogs}(logs)=False$ then

8: $instr\leftarrow logs.instr$

9: $break$

10: end if

11: end for

12: return $instr$

13:end function

Function-level Localization. It is designed for runtime failure and unexpected
output inconsistency types (see §3.4.1). Specifically, the localization is
implemented by static binary instrumentation. Before and after each call
instruction, the instrumented function is responsible for printing the index
of the invoked function along with its parameters or return values, which is
achieved by the imported fd_write function, one of the WASI functions (see
§2.2). Formally, the FuncLocating in Algorithm 2 illustrates the
implementation of function-level localization. It takes the binary that
exhibits inconsistencies and its corresponding inconsistency type as inputs.
Then the binary is instrumented at the function level and then executed by
runtimes to obtain the respective output logs (L2). At the loop at L4, the
algorithm iterates over the logs outputted by instrumented functions,
consisting of arguments and return values. The algorithm then compares the
logs among runtimes to find the function that caused the inconsistent behavior
(L5-L7). It is worth noting that the binary generating method guarantees the
call relationship is quite simple, i.e., each function is only called once and
there is not recursive invocation, thus we can find the inconsistent function
with a simple queue traversing (L6). Lastly, the algorithm examines whether
the instruction-level localization should be further invoked depending on if
the inconsistency type is unexpected output.

Instruction-level Localization. The InstrLocating will be invoked if the
inconsistency behavior is due to the unexpected output. Specifically, it takes
the binary exhibiting inconsistencies and the index of its inconsistent
function as input. Then InstrLocating performs instruction-level
instrumentation on the specified function within the binary and feeds the
instrumented binary to runtimes to get their output logs (L2). The
instrumentation is conducted by printing the opcode of non-control-flow
instruction and the value on the top of the stack after each instruction. L4
to L10 iterate the output of each instrumentation point. By comparing the
values on the stack after the execution of each instruction, the algorithm
identifies the specific instruction responsible for the observed inconsistency
behavior. Consequently, the instruction that leads to buggy inconsistency is
returned.

##  4\. Implementation & Evaluation

###  4.1. Implementation & Experimental Setup

We have implemented WRTester with over 7.4K LOC of Python3 code from scratch.
All experiments were performed on a server in Ubuntu 22.04 with a 64-core AMD
EPYC 7713 CPU and 256GB RAM. Our evaluation is driven by the following
research questions:

  * RQ1

What is the performance of WRTester compared with baselines?

  * RQ2

How many real-world bugs in Wasm runtimes can be identified by WRTester?

  * RQ3

What are the characteristics of the detected bugs?

Benchmark. We use the WasmBench (WasmBench, 2023), a well-known benchmark
consisting of over 8K Wasm binaries. These binaries are collected from various
sources, including code repositories, web applications, and package managers.
Consequently, it guarantees the richness in terms of semantics of Wasm
binaries, laying the foundation for WRTester to generate a corpus.

Baselines. We select wasm-smith (Alliance, 2023) and WADIFF (Zhou et al.,
2023) as baselines. Specifically, wasm-smith is a Wasm binary generator that
is widely-adopted in testing Wasm runtimes (wasmtime, 2023; Wasmer, 2023). It
is worth noting that Wasm binaries generated by wasm-smith in the default mode
are mostly unable to be directly executed by runtimes because it may import
functions that are supported by runtimes. Therefore, we configure it to
generate Wasm binaries without imported functions, and each binary has a
minimum of ten functions, all of which are exported. As for WADIFF, it adopts
symbolic execution on specifications of each instruction to generate Wasm
binaries to test the correctness of Wasm runtimes on executing instructions.

Targeted Runtime. We select the representative Wasm runtimes according to two
criteria. First, the stars of the runtime are greater than 3K. Second, the
runtime is actively maintained for the last three months and has been
officially released for over a year. Consequently, wasmtime (wasmtime, 2023),
Wasmer (Wasmer, 2023), wamr (wamr, 2023), and WasmEdge (WasmEdge, 2023) are
selected. Note that, no inconsistent behaviors are identified for Wasmer, thus
we omit it in the following three RQs.

Table 2. The number of generated Wasm binaries and the ones that can trigger
inconsistent behaviors, where CF, RF, UO, and T refer to compilation failure,
runtime failure, unexpected output, and the sum of these cases, respectively.
B and UB represent to bugs and unique bugs that are not discovered by the
other two tools.

| WRTester | wasm-smith | WADIFF
---|---|---|---
| # Generated
---
Wasm Binaries
269,998 | 343,299 | 283,330
wasmtime | CF | 3,151 | 0 | 0
RF | 0 | 0 | 0
UO | 0 | 0 | 0
T | 3,151 | 0 | 0
B | 1 | 0 | 0
UB | 1 | 0 | 0
wamr | CF | 40,158 | 5,555 | 0
RF | 7,578 | 5,479 | 0
UO | 1,441 | 0 | 443
T | 49,177 | 11,034 | 443
B | 7 | 5 | 2
UB | 4 | 4 | 0
WasmEdge | CF | 0 | 0 | 0
RF | 10,032 | 0 | 0
UO | 3,543 | 0 | 0
T | 13,575 | 0 | 0
B | 7 | 0 | 0
UB | 7 | 0 | 0
Total (Sum of above runtimes) | CF | 43,309 | 5,555 | 0
RF | 17,610 | 5,479 | 0
UO | 4,984 | 0 | 443
T | 65,903 | 11,034 | 443
B | 15 | 5 | 2
UB | 12 | 4 | 0

###  4.2. RQ1: Comparison with Baselines

Overall Result. For fair comparison, we run each tool separately for 24 hours
on all four targeted Wasm runtimes. Table 2 illustrates the number of
generated Wasm binaries (the second row) and the ones that are able to result
in inconsistent behaviors (the rows leading by T). As we can see, the
efficiency of these three tools is indistinguishable, and they all can
generate and perform the corresponding differential testing on 300,000 Wasm
binaries within 24 hours. However, when it comes to the number of Wasm
binaries that can lead to inconsistent behaviors, the difference in efficiency
among them is significant. WRTester generate more than 65K Wasm binaries that
can result in inconsistent behaviors, which is 6.0x and 148.8x than wasm-smith
and WADIFF respectively. Interestingly, we can easily observe that wasm-smith
and WADIFF can only detect inconsistent behaviors in wamr, while WRTester is
also effective in wasmtime and WasmEdge. This is because the aim of binaries
generated by wasm-smith is more about testing the syntax verification of
runtimes, which may has been widely tested by the other runtimes before
release. As for WADIFF, it can only test the implementation inconsistency of
instruction-level.

Distribution of inconsistencies. We further analyze the types of
inconsistencies (mentioned in §3.4.1) identified, as the rows led by CF
(compilation failure), RF (runtime failure), and UO (unexpected output) in
Table 2. Interestingly, for wasmtime, all identified inconsistency behaviors
are CF, while all cases of WasmEdge fall into another two categories. We
speculate that this is due to the different robustness of the two runtimes in
their modular implementations. Moreover, the most cases that can lead to
inconsistent behavior can be found in wamr for all the three tools, while only
WRTester can identify all three kinds of inconsistencies, which further
suggests the effectiveness of WRTester.

Bugs. We make a step further to investigate the root causes of these
inconsistency behaviors, as shown in the rows led by B and UB, indicating the
number of bugs and unique bugs that are not discovered by the other two tools.
WRTester identifies 15 bugs in total within 24 hours, while 12 of which are
not discovered by wasm-smith and WADIFF. Interestingly, we can also observe
that wasm-smith found four unique bugs that are not identified by WRTester
during testing against wamr, which are all syntactic bugs. For example, one
case has a br_table followed by an array with more than 30 branches as
targets, where wamr failed to examine if the type of each targeted block is
identical. Such a long br_table is unusual in real-world cases, thus WRTester
cannot find this issue within 24 hours even with the help of mutation
strategies.

Answer to RQ1. Compared with the state-of-the-art baselines, i.e., wasm-smith
and WADIFF, WRTester illustrates its superiority in both terms of efficiency
and effectiveness in identifying unexpected behaviors in Wasm runtimes, where
the number of identified cases is 6.0x and 148.8x than them, respectively.

###  4.3. RQ2: Runtime Bugs in the Wild

Our previous exploration suggests that WRTester outperforms SOTA techniques
greatly. Thus, we next seek to apply WRTester to identifying runtime bugs in
the wild. For the targeted runtimes, WRTester performs differential testing
for 72 hours111Note that, the reason we set the time frame of 72 hours is that
the number of unique bugs WRTester identified remain stable after roughly 65
hours.. In total, WRTester has generated 832,053 Wasm binaries, 167,343 out of
which (accounting for 20.11%) can lead to inconsistent behavior across Wasm
runtimes. Table 3 illustrates the break down details.

Table 3. The break down of 167,343 Wasm binaries that can lead to inconsistent
behaviors generated by WRTester. The number in parenthesises is the number of
unique bugs.

|  CF |  RF |  UO |  Total
---|---|---|---|---
wasmtime | 8,692 (1) | 0 (0) | 0 (0) | 8,692 (1)
wamr | 99,578 (4) | 17,568 (10) | 2,763 (5) | 119,909 (19)
WasmEdge | 0 (0) | 30,273 (7) | 8,469 (6) | 38,742 (13)
Total | 108,270 (5) | 47,841 (17) | 11,232 (11) | 167,343 (33)

Behavior Inconsistencies. Among all these three runtimes, WRTester generates a
total of 119,908 cases that can trigger inconsistencies in wamr, which is 3.1x
and 13.8x than WasmEdge and wasmtime. Most of the inconsistent cases belong to
CF, accounting for 65% of all binaries.

Bugs. As shown in Table 3, for all the 167,343 inconsistent cases, our root
cause localization method pinpoints 33 unique bugs, and 5, 17, and 11 of them
are classified into CF, RF, and UO, respectively. Over half of the bugs are
discovered within the first 24 hours, and the growth rate gradually slows down
in the following hours. Note that, against wasmtime, we only identified a
single type bug that can generate its unexpected behaviors, which is
consistent with the results presented in RQ1. It is noteworthy that although
WRTester generated the highest number of binaries resulting in CF, there are
only 4 unique bugs. After investigating the reason, we found that it is
because wamr raises exceptions when parsing the complex representation of
immediate values of v128.const. Because our mutation strategies (see §3.3.2)
can import such instructions, a large number of binaries trigger this
inconsistent behavior.

Table 4. Detailed information of all confirmed bugs.

Runtime | Issue | Type | Root Cause | Status
---|---|---|---|---
wasmtime | #7558 | CF | type conversion error | Fixed
wamr | #2450 | RF | integer overflow | Fixed
#2555 | RF | llvm compiler crash | Fixed
#2556 | CF | non-alignment issue | Fixed
#2557 | CF | value kind check missing | Fixed
#2561 | UO | instruction implementation error | Fixed
#2677 | CF | type conversion error | Fixed
#2690 | UO | instruction implementation error | Fixed
#2720 | RF | memory check error | Fixed
#2789 | CF | string check error | Fixed
#2861 | UO | instruction implementation error | Confirmed
#2862 | UO | instruction implementation error | Confirmed
WasmEdge | #2812 | UO | instruction implementation error | Confirmed
#2814 | RF | memory check error | Confirmed
#2815 | UO | instruction implementation error | Confirmed
#2988 | UO | instruction implementation error | Confirmed
#2996 | UO | instruction implementation error | Confirmed
#2997 | UO | instruction implementation error | Confirmed
#2999 | UO | instruction implementation error | Confirmed
#3018 | RF | memory check error | Confirmed
#3019 | RF | memory check error | Confirmed
#3057 | RF | memory check error | Confirmed
#3063 | RF | memory check error | Confirmed
#3068 | RF | memory check error | Confirmed
#3076 | RF | memory check error | Confirmed

Bug Reporting. For each unique bug we identified, we randomly select binaries
and report them to runtime developers, and we further provide root cause
analysis to them for aiding bug fixing. For the 33 unique bugs, 25 of them
have been confirmed by developers, and 11 of them have been fixed by the time
of this writing, as shown in Table 4. For those confirmed ones, we will
conduct detailed case studies on some representatives in the following §4.4

Answer to RQ2. WRTester successfully generated more than 167K Wasm binaries
that can lead to unexpected behaviors of Wasm runtimes, which were caused by
33 unique bugs. With our timely disclosure, 25 bugs have already been
confirmed by runtime developers, and 11 of them have been fixed with our help.

###  4.4. RQ3: Bug Characterization

We go a step further to analyze the root cause of each bug manually. As shown
in Table 4 illustrates, most of these bugs are caused by instruction
implementation errors, while some bugs are due to boundary check and type
conversion errors. We next select three fixed bugs as representative ones for
case studies.

⬇

1(memory (;0;) 65536 65536)

2(data (;0;) (i32.const -79158787) "Bp222N")

Listing 1: Wasmtime Type conversion error.

Case 1: Wasmtime Type conversion error. Listing 1 shows a part of the Wasm
binary generated by WRTester, leading to the #7558 issue of Wasmtime.
Specifically, L1 specifies the maximum space of the linear memory of this
binary is 4 GB. However, L2 initializes the memory area starting from the
offset of -79158787, which needs to be interpreted as an unsigned 32-bit
integer. Unfortunately, wasmtime incorrectly takes this number as a signed
one, leading to a compilation failure as a negative address is invalid.

⬇

1(module

2 (func (result v128)

3 v128.const i32x4 0x3d52aa71 0xea2f90b2 0xb20cdf3d 0x4d6054bc

4 i32.const -7235

5 i8x16.shl)

6 (export "main" (func 0)))

Listing 2: Wamr instruction implementation error.

Case 2: wamr instruction implementation error. Listing 2 illustrates a part of
the Wasm binary generated by WRTester that triggers the #2690 issue of wamr.
To be specific, the i32.const -7235 at L4 determines how many bits should be
left-shifted, and it should be interpreted as the unsigned number 58302.
Unfortunately, wamr incorrectly treats -7235 as a signed number and directly
performs modulo with 128. Thus, the following instruction left-shift the
v128.const at L3 in different bit. To this end, though this code snippet can
be executed normally, wamr outputs a different output compared with other
runtimes.

⬇

1(export "\00jCeH" (func 0))

2(export "" (func 1))

3(export "fj" (func 2))

Listing 3: Wamr string check error.

Case 3: wamr string check error. Listing 3 shows a case that leads to the
#2789 issue of wamr. The first two export items export \00jCeH and an empty
string, respectively. Note that, both of them start with a \00. Instead of
using Unicode string to handle import and export names, as required by the
Wasm spec, wamr adopts c-style string. Thus wamr mistakenly resolves the first
two exports to two empty strings, which causes wamr to fail to compile the
bytecode and raise the duplicate export name exception.

Answer to RQ3. Instruction implementation error and memory check error are the
top two factors leading to the unexpected behaviors of Wasm runtimes,
underlining the importance of performing adequate sanity checks and following
the specification.

##  5\. Discussion

Ethical Consideration. This work aims to identify real-world bugs in Wasm
runtimes. We have identified 33 unique bugs, and reported them to runtime
developers immediately for responsibility. By the time of this writing, most
of them have been confirmed, although some bugs are in the process of fixing.
we have repeatedly urged developers to fix them by providing necessary help.

Semantics. Although WRTester tries to generate binaries with rich semantics as
much as possible, they might be not as semantically rich as real-world
binaries. This is mainly due to the fact that some complex control flows
within sub-trees of ASTs cannot be fully executed. To reach these deep and
nested nodes, it depends on the context provided by the previous ASTs.
Although we assign values to local variables in functions, we cannot guatantee
that we can restore every contexts.

Scalability. Wasm is experiencing fast development, and many new proposals are
emerging. WRTester’s current ability to test the semantics of runtimes might
not encompass some new proposals. However, we argue that WRTester can be
easily extended to cover the new semantics by incorporating real-world Wasm
binaries that exploit new features. Additionally, we will design more
generation and mutation strategies for these new semantics to expand the
capabilities of WRTester.

##  6\. Related Work

Wasm binary security. Lots of existing work focus on the security side of Wasm
binaries (Lehmann et al., 2020, 2021; Brito et al., 2022; Marques et al.,
2022; Michael et al., 2023; Haßler and Maier, 2021; He et al., 2021, 2023;
Stiévenart et al., 2022). Daniel et al. (Lehmann et al., 2020) analyzed the
memory issues in Wasm binaries, like stack overflow and heap metadata
corruption, and adopted binary instrumentation and AFL to detect such memory
bugs (Lehmann et al., 2021). Tools like Wasmati (Brito et al., 2022) and Wasp
(Marques et al., 2022) leverage code property graphs and concolic execution,
respectively, to identify vulnerabilities in Wasm binaries. MSWasm (Michael et
al., 2023) addresses Wasm’s memory safety issues by introducing semantics
related to memory safety for Wasm.

Wasm runtime testing. There exist some work in testing Wasm runtimes (Yixuan
et al., 2023; Jiang et al., 2022; Zhou et al., 2023; Jiang et al., 2023).
Specifically, WADIFF (Zhou et al., 2023) utilizes symbolic execution on the
specification of instructions to generate Wasm binaries to conduct the
following differential testing. Moreover, Zhang et al. (Yixuan et al., 2023)
develops a pattern-based bug detection framework based on pre-defined domain
knowledge. Additionally, Jiang et al. (Jiang et al., 2023) leverages existing
performance testing benchmarks to discover performance issues in server-side
Wasm runtimes via differential testing. However, these approaches still
struggle in generating Wasm binaries with rich semantics.

Differential testing. McKeeman (McKeeman, 1998) first introduced the concept
of differential testing. Then, it has been extensively employed against
various applications, including virtual machines (Chen et al., 2016, 2019;
Bernhard et al., 2022), compilers (Sheridan, 2007; Ofenbeck et al., 2016;
Morisset et al., 2013), deep learning frameworks (Deng et al., 2023; Guo et
al., 2020), and symbolic execution engines (Kapus and Cadar, 2017). This paper
borrows the idea of differential testing and applies it to Wasm runtimes.

##  7\. Conclusion

This paper presents WRTester, a novel differential testing framework for Wasm
runtimes. WRTester can generate syntactic-correct and semantic-rich Wasm
binaries by disassembling and assembling of real-world Wasm binaries. For
further pinpointing the root causes of inconsistencies and locating the bugs,
we further propose a root cause identification algorithm that can accurately
locate bugs on a function-level or even instruction-level. WRTester shows
great performance via extensive evaluation, and we have uncovered 33 real-
world bugs in popular Wasm runtimes.

## References

  * (1)
  * Occ (2023) 2023\.  Occam’s razor.  https://en.wikipedia.org/wiki/Occam%27s_razor
  * Alliance (2023) Bytecode Alliance. 2023.  Github wasm-tools repository.  https://github.com/bytecodealliance/wasm-tools/tree/main/crates/wasm-smith
  * Bernhard et al. (2022) Lukas Bernhard, Tobias Scharnowski, Moritz Schloegel, Tim Blazytko, and Thorsten Holz. 2022.  JIT-picking: Differential fuzzing of JavaScript engines. In _Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security_. 351–364.
  * Brito et al. (2022) Tiago Brito, Pedro Lopes, Nuno Santos, and José Fragoso Santos. 2022.  Wasmati: An efficient static vulnerability scanner for WebAssembly.  _Computers & Security_ 118 (2022), 102745.
  * Cao et al. (2023) Shangtong Cao, Ningyu He, Yao Guo, and Haoyu Wang. 2023.  BREWasm: A General Static Binary Rewriting Framework for WebAssembly. In _International Static Analysis Symposium_. Springer, 139–163.
  * Chen et al. (2019) Yuting Chen, Ting Su, and Zhendong Su. 2019.  Deep differential testing of JVM implementations. In _2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE)_. IEEE, 1257–1268.
  * Chen et al. (2016) Yuting Chen, Ting Su, Chengnian Sun, Zhendong Su, and Jianjun Zhao. 2016.  Coverage-directed differential testing of JVM implementations. In _proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation_. 85–99.
  * Deng et al. (2023) Zizhuang Deng, Guozhu Meng, Kai Chen, Tong Liu, Lu Xiang, and Chunyang Chen. 2023.  Differential Testing of Cross Deep Learning Framework $\\{$APIs$\\}$: Revealing Inconsistencies and Vulnerabilities. In _32nd USENIX Security Symposium (USENIX Security 23)_. 7393–7410.
  * eosio (2023) eosio. 2023.  eosio official website.  https://eos.io/
  * Guo et al. (2020) Qianyu Guo, Xiaofei Xie, Yi Li, Xiaoyu Zhang, Yang Liu, Xiaohong Li, and Chao Shen. 2020.  Audee: Automated testing for deep learning frameworks. In _Proceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering_. 486–498.
  * Haas et al. (2017) Andreas Haas, Andreas Rossberg, Derek L Schuff, Ben L Titzer, Michael Holman, Dan Gohman, Luke Wagner, Alon Zakai, and JF Bastien. 2017.  Bringing the web up to speed with WebAssembly. In _Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation_. 185–200.
  * Haßler and Maier (2021) Keno Haßler and Dominik Maier. 2021.  Wafl: Binary-only webassembly fuzzing with fast snapshots. In _Reversing and Offensive-oriented Trends Symposium_. 23–30.
  * He et al. (2021) Ningyu He, Ruiyi Zhang, Haoyu Wang, Lei Wu, Xiapu Luo, Yao Guo, Ting Yu, and Xuxian Jiang. 2021.  EOSAFE: Security Analysis of EOSIO Smart Contracts.. In _USENIX Security Symposium_. 1271–1288.
  * He et al. (2023) Ningyu He, Zhehao Zhao, Jikai Wang, Yubin Hu, Shengjian Guo, Haoyu Wang, Guangtai Liang, Ding Li, Xiangqun Chen, and Yao Guo. 2023.  Eunomia: Enabling User-specified Fine-Grained Search in Symbolically Executing WebAssembly Binaries.  _arXiv preprint arXiv:2304.07204_ (2023).
  * Jiang et al. (2022) Bo Jiang, Zichao Li, Yuhe Huang, Zhenyu Zhang, and W Chan. 2022.  Wasmfuzzer: A fuzzer for webassembly virtual machines. In _34th International Conference on Software Engineering and Knowledge Engineering, SEKE 2022_. KSI Research Inc., 537–542.
  * Jiang et al. (2023) Shuyao Jiang, Ruiying Zeng, Zihao Rao, Jiazhen Gu, Yangfan Zhou, and Michael R Lyu. 2023.  Revealing Performance Issues in Server-side WebAssembly Runtimes via Differential Testing.  _arXiv preprint arXiv:2309.12167_ (2023).
  * Johnson et al. (2023) Evan Johnson, Evan Laufer, Zijie Zhao, Dan Gohman, Shravan Narayan, Stefan Savage, Deian Stefan, and Fraser Brown. 2023.  WaVe: a verifiably secure WebAssembly sandboxing runtime. In _2023 IEEE Symposium on Security and Privacy (SP)_. IEEE, 2940–2955.
  * Kapus and Cadar (2017) Timotej Kapus and Cristian Cadar. 2017.  Automatic testing of symbolic execution engines via program generation and differential testing. In _2017 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE)_. IEEE, 590–600.
  * Lehmann et al. (2020) Daniel Lehmann, Johannes Kinder, and Michael Pradel. 2020.  Everything old is new again: Binary security of webassembly. In _Proceedings of the 29th USENIX Conference on Security Symposium_. 217–234.
  * Lehmann et al. (2021) Daniel Lehmann, Martin Toldam Torp, and Michael Pradel. 2021.  Fuzzm: Finding memory bugs through binary-only instrumentation and fuzzing of webassembly.  _arXiv preprint arXiv:2110.15433_ (2021).
  * Marques et al. (2022) Filipe Marques, José Fragoso Santos, Nuno Santos, and Pedro Adão. 2022.  Concolic Execution for WebAssembly. In _36th European Conference on Object-Oriented Programming (ECOOP 2022)_. Schloss Dagstuhl-Leibniz-Zentrum für Informatik.
  * McKeeman (1998) William M McKeeman. 1998.  Differential testing for software.  _Digital Technical Journal_ 10, 1 (1998), 100–107.
  * MDN (2023) MDN. 2023.  MDN web docs website.  https://developer.mozilla.org/en-US/docs/WebAssembly/Rust_to_wasm
  * Michael et al. (2023) Alexandra E Michael, Anitha Gollamudi, Jay Bosamiya, Evan Johnson, Aidan Denlinger, Craig Disselkoen, Conrad Watt, Bryan Parno, Marco Patrignani, Marco Vassena, et al. 2023\.  Mswasm: Soundly enforcing memory-safe execution of unsafe code.  _Proceedings of the ACM on Programming Languages_ 7, POPL (2023), 425–454.
  * Morisset et al. (2013) Robin Morisset, Pankaj Pawan, and Francesco Zappa Nardelli. 2013.  Compiler testing via a theory of sound optimisations in the C11/C++ 11 memory model.  _ACM SIGPLAN Notices_ 48, 6 (2013), 187–196.
  * Ofenbeck et al. (2016) Georg Ofenbeck, Tiark Rompf, and Markus Püschel. 2016.  RandIR: differential testing for embedded compilers. In _Proceedings of the 2016 7th ACM SIGPLAN Symposium on Scala_. 21–30.
  * Sheridan (2007) Flash Sheridan. 2007.  Practical testing of a C99 compiler using output comparison.  _Software: Practice and Experience_ 37, 14 (2007), 1475–1488.
  * Stiévenart et al. (2022) Quentin Stiévenart, Coen De Roover, and Mohammad Ghafari. 2022.  Security risks of porting c programs to WebAssembly. In _Proceedings of the 37th ACM/SIGAPP Symposium on Applied Computing_. 1713–1722.
  * TinyGo (2023) TinyGo. 2023.  TinyGo official docs webpage.  https://tinygo.org/docs/guides/webassembly/
  * Wallentowitz et al. (2022) Stefan Wallentowitz, Bastian Kersting, and Dan Mihai Dumitriu. 2022.  Potential of WebAssembly for Embedded Systems. In _2022 11th Mediterranean Conference on Embedded Computing (MECO)_. IEEE, 1–4.
  * wamr (2023) wamr. 2023.  Github wamr repository.  https://github.com/bytecodealliance/wasm-micro-runtime
  * WasmBench (2023) WasmBench. 2023.  Github WasmBench repository.  https://github.com/sola-st/WasmBench
  * WasmEdge (2023) WasmEdge. 2023.  Github WasmEdge repository.  https://github.com/WasmEdge/WasmEdge
  * Wasmer (2023) Wasmer. 2023.  Github Wasmer repository.  https://github.com/wasmerio/wasmer
  * wasmtime (2023) wasmtime. 2023.  Github wasmtime repository.  https://github.com/bytecodealliance/wasmtime
  * WebAssembly (2023a) WebAssembly. 2023a.  Github WASI repository.  https://github.com/WebAssembly/WASI
  * WebAssembly (2023b) WebAssembly. 2023b.  Index of WebAssembly instructions.  https://webassembly.github.io/spec/core/appendix/index-instructions.html
  * WebAssembly (2023c) WebAssembly. 2023c.  SIMD proposal for WebAssembly.  https://github.com/WebAssembly/simd
  * WebAssembly (2023d) WebAssembly. 2023d.  WebAssembly 1.0 specification webpage.  https://www.w3.org/TR/wasm-core-1/#a7-index-of-instructions
  * WebAssembly (2023e) WebAssembly. 2023e.  WebAssembly specification webpage.  https://webassembly.github.io/spec/core/binary/index.html
  * Yixuan et al. (2023) Zhang Yixuan, Cao Shangtong, Wang Haoyu, Zhenpeng Chen, Luo Xiapu, Mu Dongliang, Ma Yun, Huang Gang, and Liu Xuanzhe. 2023.  Characterizing and Detecting WebAssembly Runtime Bugs.  _ACM Transactions on Software Engineering and Methodology_ (2023).
  * Zakai (2011) Alon Zakai. 2011.  Emscripten: an LLVM-to-JavaScript compiler. In _Proceedings of the ACM international conference companion on Object oriented programming systems languages and applications companion_. 301–312.
  * Zhou et al. (2023) Shiyao Zhou, Muhui Jiang, Weimin Chen, Hao Zhou, Haoyu Wang, and Xiapu Luo. 2023.  WADIFF: A Differential Testing Framework for WebAssembly Runtimes. In _2023 38th IEEE/ACM International Conference on Automated Software Engineering (ASE)_. IEEE Computer Society, 939–950.