Waltzz: WebAssembly Runtime Fuzzing with Stack-Invariant Transformation

Waltzz: WebAssembly Runtime Fuzzing with Stack-Invariant Transformation

Speakers: Lingming Zhang, from Zhejiang University

Conference: USENIX Security

YouTube: https://www.youtube.com/watch?v=XZo2wVYnnv8

Overview

This talk introduces Waltzz, a novel, domain-specific fuzzer meticulously designed for WebAssembly (Wasm) runtimes. Presented by Lingming Zhang from Zhejiang University, Waltzz addresses the critical challenge of effectively identifying security vulnerabilities such as remote code execution and sandbox escapes within Wasm execution environments. Wasm, a high-performance binary instruction format, enables code written in various languages to run efficiently across web and other platforms. Its runtimes are foundational to many modern applications, making their security paramount.

The core problem Waltzz tackles stems from the inherent limitations of traditional fuzzing approaches when applied to Wasm. Byte-level fuzzers like AFL++ generate an overwhelming number of semantically invalid Wasm modules due to Wasm's strict stack-based semantics and type validation requirements, hindering their effectiveness. Conversely, generative fuzzers, while ensuring validity, often struggle with exploring the vast and diverse instruction combinations within the Wasm standard. Waltzz innovates by employing Stack Invariant Transformation, a principle that allows for the generation of diverse yet semantically valid Wasm inputs, thereby significantly enhancing bug-finding capacity and code coverage in critical Wasm runtimes. This work is crucial for bolstering the security posture of the rapidly expanding Wasm ecosystem.

Background

▶ Watch: Introduction and limitations of current Wasm fuzzers (0:00)

WebAssembly (Wasm) has emerged as a crucial technology, providing a secure and high-performance execution environment for code across various platforms, including web browsers and serverless functions. As a stack-based language, Wasm instructions operate by pushing and popping values onto an execution stack, adhering to strict type rules. Wasm runtimes are mandated to validate the stack semantics and control flow integrity of any input Wasm module before execution. For instance, an i32.add instruction expects two i32 values on the stack; any deviation leads to immediate rejection. This rigorous validation is a critical security feature, preventing malformed modules from causing undefined behavior or exploiting runtime vulnerabilities.

However, this very design poses significant challenges for traditional fuzzing techniques. Generic, byte-level mutational fuzzers, such as AFL++, operate by making small, arbitrary changes (like bit flips) to input binaries. When applied to Wasm, these mutations almost invariably corrupt the intricate stack semantics or control flow, rendering the generated modules invalid. Preliminary experiments cited in the talk revealed that over 98% of test cases generated by AFL++ were rejected by Wasm runtimes, severely limiting its ability to explore code paths and find bugs. Such a high invalidity rate means the fuzzer spends most of its time generating unusable inputs, effectively "hitting the wall."

On the other end of the spectrum are generative fuzzers, like Wasm Smith, which are designed to produce semantically valid Wasm modules from scratch. While these fuzzers guarantee validity, they often rely on fixed, predefined rules and templates. This approach struggles with the sheer complexity and vastness of the Wasm instruction set, which comprises over 400 instructions with diverse functionalities. Consequently, generative fuzzers often fail to explore the expansive input space comprehensively, leading to a lack of diversity in the generated test cases and potentially missing obscure instruction combinations that could trigger vulnerabilities.

To overcome this dilemma—the trade-off between input validity and diversity—Waltzz draws inspiration from prior work in type-system-aware fuzzing, such as Code Alchemist and Facility. The core insight is to abstract away the specific operations on stack values and instead focus on the accumulative effects on stack types. This led to the development of Stack Invariant Transformation. The basic intuition is that if two different sequences of Wasm instructions have identical impacts on the stack's types (e.g., both pop zero values and push one i64 value), they can be interchanged without violating Wasm's semantic rules. This principle allows Waltzz to introduce significant structural and operational diversity into Wasm modules while simultaneously ensuring their semantic validity, thereby addressing the fundamental limitations of existing fuzzers in the Wasm domain.

Key Findings

▶ Watch: High-level workflow of the Waltzz fuzzer (4:00)

Waltzz demonstrates a significant leap forward in the effectiveness of Wasm runtime fuzzing, outperforming state-of-the-art fuzzers across key metrics. The evaluation, conducted over 72 hours on seven Wasm runtimes (including three web embeddings: SpiderMonkey, JavaScriptCore, V8; and four non-web embeddings: Wasm Micro Runtime, Wasmer, Wasmtime, Wasm Interpret), and repeated ten times, yielded compelling results:

• Superior Code Coverage: Waltzz achieved an average of 12.4% more code coverage compared to the nearest competitor. This enhanced exploration of the target runtime's codebase directly translates to a higher likelihood of uncovering hidden vulnerabilities.
• Increased Bug-Finding Capacity: The fuzzer demonstrated a 1.38 times higher bug-finding capacity than its closest rival. This quantitative advantage highlights Waltzz's efficiency in identifying actual security flaws.
• Discovery of New Vulnerabilities: Waltzz successfully uncovered a total of 20 new bugs across the evaluated Wasm runtimes. All identified bugs were thoroughly verified, and a remarkable 17 CVE IDs were assigned, underscoring the severity and novelty of the discovered vulnerabilities.
• 100% Semantic Validity: A critical finding is Waltzz's ability to generate hundreds of thousands of semantically valid inputs with a 100% success rate. This achievement, directly attributed to the Stack Invariant Transformation principle, completely bypasses the high invalidity rates that plague traditional fuzzers like AFL++.
• Contribution of Diverse Mutators: An analysis of individual mutator contributions revealed that all mutation methods—control flow, data flow, and splicing—play a significant role in Waltzz's overall effectiveness. The study also noted that different target runtimes might favor specific mutators; for example, the splicing mutator was particularly effective in finding new paths within SpiderMonkey, while performing moderately on other targets. This suggests a synergistic design where the combination of diverse, stack-invariant mutations is crucial for comprehensive fuzzing.

These findings collectively establish Waltzz as a highly effective and robust solution for securing the complex and rapidly evolving WebAssembly ecosystem.

Technical Deep Dive

▶ Watch: Designing mutators for diverse control flow structures (5:00)

The technical prowess of Waltzz lies in its innovative workflow and the sophisticated design of its mutators and generator, all underpinned by the Stack Invariant Transformation principle.

Waltzz Workflow

At a high level, Waltzz operates through a multi-stage process:

1. Seed Input Processing: It begins with a seed Wasm module, which is parsed and transformed into a Typed Intermediate Representation (IR). This IR explicitly captures the Wasm module's structure and, crucially, the type information associated with each instruction's stack effects.
2. Stack Invariant Transformation: The typed IR then undergoes a series of mutations and generations, guided by the stack invariant principle. This produces a list of transformed IRs.
3. Module Generation and Execution: These transformed IRs are then lifted back into concrete Wasm modules.
4. Runtime Execution and Feedback: The generated Wasm modules are sequentially executed by the instrumented Wasm runtime. If new code paths are uncovered (feedback-driven fuzzing) or a crash occurs, the corresponding test case is added to the seed pool or crash directory, respectively. Otherwise, the test case is discarded.

Stack Invariant Transformation: The Core Principle

The fundamental concept enabling Waltzz's success is Stack Invariant Transformation. This principle dictates that one sequence of Wasm instructions can be replaced by another if their cumulative effects on the execution stack's types are identical. This means they must pop the same types and number of values from the stack and push the same types and number of values onto the stack. For example, both i64.add and i64.sub instructions pop two i64 values and push one i64 value. Therefore, they are stack-invariant and can be interchanged. This allows Waltzz to alter the actual operations or control flow of a Wasm module while guaranteeing that the module remains semantically valid and executable by the runtime.

Mutator Design

Waltzz employs a suite of specialized mutators, categorized by their focus:

Control Flow Mutators

These mutators are designed to explore diverse possibilities within both intra- and inter-procedure control flow, respecting Wasm's structured control flow (blocks, loops, if instructions).

• Recursive Mutator: This mutator aims to create more deeply nested control structures. For instance, it might wrap an existing block instruction into a new loop structure, increasing the complexity of control flow paths.
• Branch Target Mutator: It modifies the target label of br (branch) instructions. By altering where a branch jumps, it can redirect execution to different control flows within the module, exploring alternative execution paths.
• Code Call Mutator: This mutator changes the target function of call instructions. By directing a call to a different function, it exercises different inter-procedural paths and function interactions.

Data Flow Mutators

These mutators focus on altering the values manipulated by instructions and the operations performed on them, all while maintaining stack type invariants.

• Interesting Value Mutator: Wasm instructions often use immediate values (e.g., constants for numerical computations, memory addressing). This mutator adjusts these immediate values, specifically targeting boundary values (e.g., 0, max_int, min_int). For example, it might change an i32.const 5 instruction to i32.const 65535 (the largest unsigned 16-bit integer value), hoping to trigger edge cases in arithmetic or memory operations.
• Operator Mutator: This mutator replaces one operator with another, adhering strictly to the stack invariant transformation principle. For instance, an i32.add instruction (pops two i32, pushes one i32) can be replaced by an i32.le_s (signed less than or equal to, also pops two i32, pushes one i32 - a boolean result represented as an integer), as their stack type effects are identical. This introduces functional diversity while preserving validity.
• Splicing Mutator: A broadly adopted technique in mutational fuzzing, the splicing mutator in Waltzz combines instruction sequences from two different seed inputs. Crucially, this combination is only performed if the instruction sequence being replaced in seed A has the same stack type effects as the instruction sequence from seed B that is inserted in its place. This allows for the creation of highly novel and diverse test cases by combining valid fragments from existing modules.

Skeleton-Based Generator

The skeleton-based generator is a sophisticated component designed to construct entirely new code snippets that might be rare or non-existent in the initial seed corpus. It addresses the complexity of simultaneously satisfying Wasm's intricate type checks and control flow integrity rules.

• Separation of Concerns: The generator separates the creation of the overall control flow skeleton from the generation of specific stack values.
• Control Flow Planning: Given a target result type (e.g., i32, f32, f64) expected on the stack, the generator first plans the high-level control flow structure. It determines which parts of the target result type each control structure (e.g., block, loop) will be responsible for generating.
• Recursive Structure Generation: Within each sub-control structure, the generator recursively builds further control flow structures until a predefined maximum depth is reached. This enables the creation of highly complex and deeply nested control flows.
• Filling in Stack Values: Once the maximum recursive depth is met, the generator begins filling in concrete Wasm instructions that produce stack values of the desired types. For example, if an i32 type is needed, it might generate an i32.reinterpret_f32 instruction. If this instruction requires an f32 on the stack, the generator will then insert an f32.const instruction to provide that value, and so forth, until all required stack values are generated and the desired result types are met. This systematic approach ensures both structural complexity and semantic validity.

By integrating these advanced mutation and generation strategies, all governed by the principle of Stack Invariant Transformation, Waltzz effectively navigates the challenges of Wasm fuzzing, leading to unprecedented coverage and bug-finding capabilities.

Demo / Proof of Concept

▶ Watch: Data flow mutators for stack value manipulation (7:00)

While the talk does not feature a live, interactive demonstration of Waltzz in action, the extensive evaluation results presented serve as a robust proof of concept for its effectiveness. The core of the "demo" aspect in this context is the empirical evidence of Waltzz's superior performance compared to existing state-of-the-art fuzzers.

The demonstration of Waltzz's capabilities is conveyed through its ability to:

• Outperform Baselines: The comprehensive comparison against fuzzers like AFL++, Redqueen, Wasm Smith, Wasm Fuzzer, and Webleak, showing a 12.4% increase in code coverage and 1.38 times more bugs found, concretely proves its practical utility.
• Uncover Real-World Bugs: The discovery of 20 new bugs, with 17 CVE IDs assigned, in widely used Wasm runtimes (such as SpiderMonkey, JavaScriptCore, and V8, along with non-web embeddings like Wasmer and Wasmtime) serves as definitive proof that Waltzz can identify critical, previously unknown vulnerabilities. These assigned CVEs signify that the bugs found are impactful and required official patches, validating Waltzz's contribution to real-world security.
• Achieve 100% Input Validity: The reported 100% validity rate for generated inputs, representing hundreds of thousands of valid Wasm modules, underscores the success of the Stack Invariant Transformation in practice. This result directly addresses the primary challenge in Wasm fuzzing and showcases Waltzz's technical robustness.

In essence, the "proof of concept" is delivered through the rigorous experimental methodology and the impactful security outcomes, demonstrating that Waltzz is a highly effective and practical tool for securing WebAssembly runtimes.

Defensive Implications

▶ Watch: Skeleton-based generator for novel Wasm code (8:50)

The findings from Waltzz have profound implications for developers, security researchers, and maintainers of WebAssembly runtimes and applications. Given Wasm's growing adoption in critical environments—from web browsers to serverless edge computing—the security of its underlying runtimes is paramount. Compromises, as highlighted by previous attacks, can lead to severe consequences such as remote code execution (RCE) and sandbox escapes.

Here are key defensive implications:

• Prioritize Advanced Fuzzing: Wasm runtime developers should recognize that traditional byte-level fuzzing is largely ineffective. Integrating domain-specific, type-aware fuzzers like Waltzz into their continuous integration/continuous deployment (CI/CD) pipelines is no longer optional but a necessity. Proactive, sophisticated fuzzing is the most effective way to identify complex vulnerabilities before they are exploited in the wild.
• Strengthen Stack Semantics and Control Flow Validation: The success of Waltzz's Stack Invariant Transformation underscores the importance of robust and comprehensive validation of Wasm's stack semantics and structured control flow. While runtimes already perform these checks, the bugs found suggest there are still subtle edge cases or complex interactions that can bypass current safeguards. Developers should meticulously review and harden these validation mechanisms.
• Focus on Edge Cases in Data Flow: The effectiveness of the Interesting Value Mutator points to vulnerabilities arising from how runtimes handle immediate values, particularly boundary conditions (e.g., 0, MAX_INT, MIN_INT). Implementers should pay extra attention to numerical operations, type conversions, and memory addressing when these extreme values are involved.
• Review and Learn from Discovered CVEs: The 17 CVE IDs assigned as a result of Waltzz's findings represent concrete vulnerability patterns. Runtime developers should analyze these CVEs to understand common weaknesses, specific instruction sequences, or runtime behaviors that lead to exploitable bugs. This knowledge can inform targeted code reviews and more resilient implementations.
• Embrace Diversity in Test Case Generation: The talk highlights that different mutators contribute uniquely to bug finding, and their effectiveness varies across different runtimes. This suggests that a diverse set of fuzzing strategies, rather than relying on a single approach, is crucial for comprehensive security testing. Developers should strive to generate a wide array of syntactically valid yet semantically challenging Wasm modules.
• Invest in Runtime Hardening: Beyond fuzzing, general hardening practices for Wasm runtimes remain critical. This includes robust memory safety implementations, strict sandboxing policies, and minimizing the attack surface. Fuzzing helps identify flaws, but a well-engineered, secure-by-design runtime provides the foundational resilience.

By adopting these defensive strategies, Wasm runtime developers can significantly enhance the security posture of their products, protecting users and applications from critical vulnerabilities in the evolving WebAssembly landscape.

Key Takeaways

• Traditional byte-level fuzzers like AFL++ are largely ineffective for WebAssembly (Wasm) runtimes due to Wasm's strict stack-based semantics, leading to over 98% invalid inputs.
• Stack Invariant Transformation is a highly effective principle for Wasm fuzzing, enabling the generation of diverse yet 100% semantically valid Wasm modules by preserving stack type effects during mutations.
• Waltzz significantly outperforms existing state-of-the-art fuzzers, achieving 12.4% more code coverage and finding 1.38 times more bugs, leading to the discovery of 20 new vulnerabilities and 17 assigned CVE IDs.
• A combination of diverse mutators (control flow, data flow, splicing) and a sophisticated skeleton-based generator is crucial for comprehensive Wasm fuzzing, addressing both structural complexity and value manipulation.
• The security of Wasm runtimes is critical, and advanced, domain-specific fuzzing techniques like Waltzz are essential tools for proactive vulnerability discovery and hardening against severe attacks like RCE and sandbox escapes.

About the Speaker(s)

The talk was presented by Lingming Zhang, who is affiliated with Zhejiang University. No additional biographical details were provided in the transcript or metadata.