Execution-Aware Program Reduction for WebAssembly via Record and Replay
Doehyun Baek, Daniel Lehmann, Ben L. Titzer, Sukyoung Ryu, Michael Pradel · 2025
Read Execution-Aware Program Reduction for WebAssembly via Record and Replay by Doehyun Baek, Daniel Lehmann, Ben L. Titzer, Sukyoung Ryu, Michael Pradel (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-07834.txt.
Introduction
Doehyun Baek and co-authors shrink WebAssembly programs that expose browser engine bugs, in work from 2025. A smaller failing program is far easier to debug, but standard reducers ignore how the program actually ran.
Their tool records a real execution, finds the function that triggers the bug, and rebuilds a tiny program that replays only that function's exchanges with the rest. A hybrid version adds a conventional reducer on top. On 28 real bug cases across three engines, the replay method cut programs to about 1.2 percent of their size in roughly fifteen minutes. The hybrid reached 0.13 percent, beating prior tools on size and speed.
Catalog record
| CREATOR | Doehyun Baek, Daniel Lehmann, Ben L. Titzer, Sukyoung Ryu, Michael Pradel |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 52 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-07834
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Execution-Aware Program Reduction for WebAssembly via Record and Replay Doehyun Baek, Daniel Lehmann, Ben L. Titzer, Sukyoung Ryu, Michael Pradel Abstract WebAssembly (Wasm) programs may trigger bugs in their engine implementations. To aid debugging, program reduction techniques try to produce a smaller variant of the input program that still triggers the bug. However, existing execution-unaware program reduction techniques struggle with large and complex Wasm programs, because they rely on static information and apply syntactic transformations, while ignoring the valuable information offered by the input program’s execution behavior. We present RR-Reduce and Hybrid-Reduce, novel execution-aware program reduction techniques that leverage execution behaviors via record and replay. RR-Reduce identifies a bug-triggering function as the target function, isolates that function from the rest of the program, and generates a reduced program that replays only the interactions between the target function and the rest of the program. Hybrid-Reduce combines a complementary execution-unaware reduction technique with RR-Reduce to further reduce program size. We evaluate RR-Reduce and Hybrid-Reduce on 28 Wasm programs that trigger a diverse set of bugs in three engines. On average, RR-Reduce reduces the programs to 1.20% of their original size in 14.5 minutes, which outperforms the state of the art by 33.15 × \times in terms of reduction time. Hybrid-Reduce reduces the programs to 0.13% of their original size in 3.5 hours, which outperforms the state of the art by 3.42 × \times in terms of reduced program size and 2.26 × \times in terms of reduction time. We envision RR-Reduce as the go-to tool for rapid, on-demand debugging in minutes, and Hybrid-Reduce for scenarios where developers require the smallest possible programs. and I Introduction WebAssembly (Wasm) [ 1 ] is a language for the web designed for efficient, sandboxed execution. Wasm engines, like any other software, may contain bugs. Indeed, several techniques for detecting bugs in Wasm implementations have been proposed recently [ 2 , 3 , 4 , 5 ] . These bug-triggering Wasm programs are often large and complex, which makes debugging the affected engine challenging. Program reduction, which aims to find a smaller variant of the input program that still triggers the bug, is used to mitigate this problem. Delta Debugging [ 6 ] is the pioneering input reduction technique, and various others have been proposed since then [ 7 , 8 , 9 ] . For reducing Wasm programs, there are two industrially supported tools: wasm-reduce [ 10 ] and wasm-shrink [ 11 ] . While these tools are effective in some cases, they are limited in terms of both effectiveness and efficiency. To illustrate the limitations of currently available techniques, consider the commanderkeen program [ 12 ] , which reveals a miscompilation bug in the Wizard engine [ 13 ] . The Wasm binary is 3.9MB in size, which is not uncommon for binaries compiled from large programs. Wasm-reduce, i.e., the most effective existing tool for Wasm, reduces commanderkeen to 1.3MB after 24 hours of processing, which is far too large for a human to manually debug. Wasm-reduce is an example of an execution-unaware program reduction technique, i.e., it ignores the execution behavior of the input program. We identify two reasons why such execution-unaware techniques struggle with our example program and other input programs: (1) The reduction process applies syntactic transformations based on static information only, leading to a huge search space of possible reduced programs. (2) Checking whether the bug is preserved by a reduced program is expensive, as the Wasm engine has to execute the program to check whether the bug is still triggered. For the commanderkeen program, each such oracle invocation takes about 9 seconds, which is a long time for a program reduction technique that needs to perform many oracle invocations to find a reduced program. A detailed inspection of the above example and other bug-triggering Wasm programs reveals an interesting observation: Usually, a single function in the program is responsible for triggering the bug. For example, the commanderkeen program contains 1,970 functions, but only one of them is relevant for triggering the bug. A naive approach to reduce the program would be to simply remove all other functions from the Wasm binary. However, this naive approach would lead to a program that fails to compile and execute, hence failing to trigger the bug, as the bug-triggering function depends on other functions and other code in the program. For the motivating example, 580 other functions are executed before the bug is triggered. We hypothesize that these problems can be addressed by leveraging the execution behavior of the input program, which provides valuable information about the dependencies between different parts of the program. This information may be used for isolating the bug-triggering function and any other code necessary to trigger a bug-exposing execution. Based on this hypothesis, we ask the question: Can we use information about the execution of an input program to reduce the input program more effectively? To answer this question, this paper presents RR-Reduce, an execution-aware program reduction technique for Wasm. A key insight of the approach is that we can repurpose existing record and replay techniques for execution-aware program reduction. Record and replay is a debugging technique that records a program execution and then replays the recorded execution. It has been adopted in many domains, including native binaries [ 14 , 15 ] , JavaScript [ 16 , 17 ] , and Wasm [ 12 ] . Usually, record and replay is used to provide a deterministic way to replay an entire execution of a program. Instead, we use this technique to replay only parts of an input program that are essential to trigger the bug. More specifically, RR-Reduce performs three steps: First, identify a bug-triggering function of the input program, which we call the target function. Second, partition the input program into two subprograms: one containing the target function and another containing the remaining functions. Third, use record and replay to generate a new program that includes the unmodified target function and generated replay functions that mimic the behavior of the remaining functions. Our RR-Reduce approach can be used as a stand-alone program reduction technique, or in combination with existing program reduction techniques. We call the latter approach Hybrid-Reduce, which applies an existing reduction technique (wasm-reduce) to the output of RR-Reduce. This further reduces output, at the expense of additional time. Getting back to our motivating example, Figure 1 shows the reduced program produced by Hybrid-Reduce. Instead of the 1.3MB output of the existing wasm-reduce tool, our approach yields a reduced program of only 158 bytes. Such a small program enables engine developers to debug the bug in a reasonable time, ultimately leading to more robust implementations of Wasm. Fig. 1 : Hybrid-Reduce’s output for commanderkeen. We evaluate RR-Reduce and Hybrid-Reduce on 28 Wasm programs that trigger bugs in three Wasm engines. The results show that Hybrid-Reduce clearly outperforms the state of the art, wasm-reduce, and that our two approaches offer different effectiveness-efficiency trade-offs. Specifically, RR-Reduce reduces the amount of code a developer must inspect to 1.20% of the original size, on average, while taking 871 seconds, which is a 33.15x improvement in efficiency over the state of the art. That is, RR-Reduce significantly reduces input programs while