RGFuzz: Rule-Guided Fuzzer for WebAssembly Runtimes

RGFuzz: Rule-Guided Fuzzer for WebAssembly Runtimes

Speakers: JunYoung Park, Yunho Kim, Insu Yun

Conference: IEEE S&P

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

Overview

In this insightful talk from IEEE S&P, JunYoung Park, Yunho Kim, and Insu Yun introduce RGFuzz, a novel rule-guided fuzzer specifically designed to uncover semantic bugs within WebAssembly (Wasm) runtimes. WebAssembly has rapidly emerged as a critical compilation target, lauded for its speed, safety, portability, and compact nature, making it ideal for porting applications to the web and beyond. To maximize performance, Wasm runtimes often employ Just-In-Time (JIT) compilers and sophisticated optimization techniques that translate Wasm bytecode into an Intermediate Representation (IR) before applying various compiler optimization rules. While these optimizations are crucial for speed, they introduce a significant attack surface: errors in these complex rules can lead to miscompilations, causing programs to execute incorrectly, or, in worst-case scenarios, introducing severe security vulnerabilities.

The core challenge in finding these elusive semantic bugs lies in generating test cases that can effectively explore the deep and intricate logic of compiler optimizations, especially the "super complex" rules that involve multiple IR transformations. Traditional fuzzing approaches often struggle to cover these specific code paths due to the sheer complexity and low probability of randomly generating such patterns. RGFuzz addresses this by proposing two innovative techniques: rule-guided fuzzing, which directly leverages extracted compiler optimization rules to inform test case generation, and reverse stack-based generation, which overcomes limitations of prior fuzzers in generating diverse Wasm programs. The efficacy of RGFuzz is demonstrated through its discovery of 20 new bugs, including one assigned a CVE ID, across six widely used Wasm runtimes, marking a significant advancement in the security and reliability of the WebAssembly ecosystem.

Background

▶ Watch: Understanding WebAssembly optimization semantic bugs (1:30)

WebAssembly's rise is predicated on its promise of near-native performance for web applications, enabling high-performance code, often compiled from languages like C, C++, and Rust, to run securely in browsers and other environments. At its heart, WebAssembly executes on a stack-based virtual machine. However, for practical performance, Wasm runtimes don't strictly interpret this stack machine. Instead, they commonly integrate JIT compilers that translate Wasm bytecode into native machine code at runtime. This compilation process often involves an intermediate step where the Wasm program is first converted into an Intermediate Representation (IR). The IR serves as a common language for the compiler to perform various optimizations before generating the final machine code.

These optimizations are critical for achieving WebAssembly's performance goals. They range from simple transformations, like replacing an XOR with -1 with a BIN operation, to highly complex rules involving the rearrangement and simplification of multiple IR instructions. For instance, a sequence of three IRs (e.g., B, B not, B or) might be optimized into two IRs (B not, B or), saving an instruction and improving execution speed. While beneficial, this optimization layer is a prime source of semantic bugs, also known as miscompilation bugs. A semantic bug occurs when the optimized code behaves differently from the original, unoptimized program for certain inputs. Such discrepancies can lead to incorrect program execution, data corruption, or, critically, expose security vulnerabilities by violating developer assumptions or enabling unexpected code paths.

Identifying these bugs is notoriously difficult. Differential fuzzing is a common technique used to detect semantic bugs. This involves generating a large number of test cases (Wasm programs) and executing them on different runtime configurations (e.g., with and without optimizations, or across different Wasm runtimes). Any discrepancy in the execution results indicates a potential semantic bug, warranting further investigation. However, the primary challenge for differential fuzzing in this context is test case generation. To effectively find compiler optimization bugs, the fuzzer must generate Wasm programs that trigger specific, often complex, optimization rules. State-of-the-art fuzzers, as highlighted by the speakers' preliminary study, frequently fail to generate programs that can cover these intricate optimization patterns, especially those involving multiple IR transformations. This limitation stems from two main issues: the difficulty in covering complex rules with unguided fuzzing and the lack of diversity in generated program structures and instructions by existing fuzzer architectures. Previous approaches, such as Abstract Syntax Tree (AST)-based methods, struggle with generating diverse structures, particularly those with multiple return types. Conversely, stack-based methods, while good for structures, often face difficulties generating diverse instructions due to complex stack constraints required for certain operations. This gap in effective test case generation is precisely what RGFuzz aims to bridge.

Key Findings

▶ Watch: Introducing Rule-Guided Fuzzing (RGFuzz) approach (3:15)

RGFuzz has demonstrated significant success in uncovering previously unknown vulnerabilities and improving the coverage of complex optimization paths in WebAssembly runtimes. The evaluation targeted six widely used runtimes, including various optimization levels and architectures, showcasing the broad applicability of the tool.

The most compelling finding is the discovery of 20 new bugs, with one severe vulnerability even receiving a CVE ID. These bugs represent genuine miscompilations that could lead to incorrect program behavior or security exploits. The ability of RGFuzz to pinpoint such flaws underscores its effectiveness in an area where traditional fuzzing often falls short.

Beyond the sheer number of bugs, RGFuzz significantly improved code coverage within WebAssembly runtimes, particularly for optimization logic. The speakers emphasized that this enhanced coverage was a direct result of their rule-guided fuzzing approach. This means RGFuzz was able to systematically explore code paths related to compiler optimizations that were previously inaccessible or extremely difficult to trigger with existing fuzzing techniques.

A notable achievement of RGFuzz is its capability to cover "super complex optimizations." The speakers presented an extreme case involving "several dozens of IRs transforming into a piece of IR," a type of optimization that is nearly impossible to hit randomly. RGFuzz was also successful in covering "rules that require very specific images," indicating its precision in generating highly tailored test cases.

Specific examples of optimization bugs found include instances where a mean operation was mistakenly compiled as a max operation, leading to incorrect numerical results. Another critical bug involved "loading more bytes than expected," particularly problematic when dealing with floating-point numbers which are often handled by specialized XML registers in modern architectures. Such discrepancies can have serious implications for data integrity and program correctness, especially in sensitive applications. These findings collectively validate RGFuzz as a powerful and indispensable tool for enhancing the robustness and security of the WebAssembly ecosystem.

Technical Deep Dive

▶ Watch: Bridging the IR rules to WebAssembly instructions gap (4:00)

RGFuzz's effectiveness stems from two primary technical innovations: rule-guided fuzzing and reverse stack-based generation. These techniques address the fundamental challenges of generating diverse and targeted WebAssembly programs capable of triggering complex compiler optimization bugs.

Rule-Guided Fuzzing (RGF)

The core idea behind rule-guided fuzzing is to make the fuzzer "aware" of the specific optimization rules employed by a compiler. Compiler optimizations are often defined as transformations on the Intermediate Representation (IR). However, fuzzers typically generate programs in WebAssembly (Wasm) bytecode. This creates a significant "gap" between the compiler's IR-level rules and the fuzzer's Wasm-level generation. RGFuzz closes this gap through a two-stage inference process:

1. Instruction-Level Inference:

The first step is to map individual WebAssembly instructions to their corresponding IR representations. This is achieved by taking each WebAssembly instruction, embedding it within a minimal Wasm module, translating that module into the compiler's IR, and then identifying the unique IR instructions generated. This process allows RGFuzz to establish a direct mapping from Wasm instructions to their IR counterparts. For example, a simple i32.xor instruction in Wasm would map to a specific bxor IR instruction. However, some common IR operations, like a generic B not (binary not), might not have a direct, single WebAssembly instruction equivalent. This is where the second inference level becomes crucial.

1. IR-Level Inference:

For IR instructions or patterns that do not have a direct, one-to-one mapping to a single WebAssembly instruction (i.e., "missing linkages"), RGFuzz employs IR-level inference. This technique refers to other compiler optimization rules to expand a "missing" IR into a sequence of known IRs that do have WebAssembly mappings. For instance, if a compiler optimization rule involves a bn (binary not) IR instruction that lacks a direct Wasm equivalent, RGFuzz might leverage another optimization rule that transforms bn into a combination of icons (integer constant) and bxor (binary XOR) IRs. Both icons and bxor typically have direct WebAssembly instruction mappings (e.g., i32.const and i32.xor respectively). By recursively applying this inference, RGFuzz can construct Wasm sequences that, when compiled, will produce the exact IR patterns required to trigger specific optimization rules. This allows the fuzzer to generate highly targeted test cases that can explore even the most complex, multi-IR optimization patterns that traditional fuzzers would likely miss.

By integrating these inference mechanisms, RGFuzz can effectively generate WebAssembly programs that are "aware" of the underlying IR-level optimization rules, significantly increasing the probability of covering those complex code paths and finding semantic bugs.

Reverse Stack-Based Generation (RSG)

The second innovation, reverse stack-based generation, addresses the limitations of prior fuzzing approaches in generating diverse WebAssembly programs, particularly concerning instruction diversity and complex structural constraints.

Previous methods exhibited two main weaknesses:

• AST-based methods struggled to generate diverse program structures, especially those involving multiple return types.
• Stack-based methods, while good at generating varied structures, faced difficulties with instruction diversity because some instructions impose complex constraints on the stack (e.g., requiring specific types or multiple operands to be present before execution).

RGFuzz's reverse stack-based generation overcomes these issues by observing a key characteristic of WebAssembly instructions: most instructions have either zero or one return type. This simplifies the stack requirements for generation. Instead of generating inputs and then an operation that consumes them, RSG works "reversely." It starts by considering the desired output type or the instruction itself, and then determines the minimal set of inputs required on the stack.

For example, consider the V128.select instruction, which operates on 128-bit SIMD (Single Instruction, Multiple Data) values. In a traditional stack-based fuzzer, generating this instruction would require first pushing three V128 types onto the stack (two operands and a condition) before the V128.select instruction could be generated and executed. This significantly constrains the fuzzer's ability to randomly generate such instructions, as the specific stack state must be met. With reverse stack-based generation, the fuzzer can conceptualize the V128.select instruction as needing to produce one V128 type. This reversal simplifies the generation process, making it easier to incorporate instructions with complex operand requirements. The fuzzer can then work backward to generate the necessary preceding instructions to satisfy the input requirements, but with a much lower "text constraint" (i.e., less strict immediate stack state requirements) during the generation phase.

This approach allows RGFuzz to generate a far more diverse set of WebAssembly instructions, including those with complex stack semantics, while retaining the advantages of stack-based generation for producing varied program structures. The combination of rule-guided fuzzing and reverse stack-based generation provides RGFuzz with a powerful and flexible framework for comprehensively testing WebAssembly runtimes for subtle and critical semantic bugs.

Demo / Proof of Concept

▶ Watch: RGFuzz's effectiveness: 20 new bugs and a CVE (6:15)

While the talk did not feature a live, interactive demonstration of RGFuzz in action, the speakers provided compelling evidence of its capabilities through several key examples and qualitative descriptions. These served as powerful proofs of concept for the tool's effectiveness.

The presentation highlighted RGFuzz's ability to cover "super complex optimizations," illustrating this with a visual representation (referred to as "on the left" in the transcript). This extreme case involved a transformation where "several dozens of IRs" were consolidated into "a piece of IR." Such intricate optimization patterns are exceptionally difficult to trigger through random fuzzing, underscoring RGFuzz's precision derived from its rule-guided approach. Similarly, the fuzzer successfully covered "rules that require very specific images" (referred to as "on the right"), indicating its capacity to generate highly tailored WebAssembly programs that match exact IR preconditions for optimization.

The most concrete proofs of concept were the specific optimization bugs discovered:

1. Mean Mistaken as Max: One critical bug involved a scenario where a compiler optimization incorrectly interpreted a calculation intended to find the mean (average) of values as one that should find the maximum value. This type of miscompilation can lead to incorrect numerical results in applications, potentially impacting calculations in scientific, financial, or data processing contexts where precision is paramount.

1. Loading More Bytes Than Expected: Another significant bug involved an issue where the runtime was "loading more bytes than expected," particularly in the context of floating-point operations. The speakers noted that this was related to how floating-point values are often handled using XML registers (likely referring to XMM or YMM registers for SIMD operations) in modern processors. An incorrect byte load could lead to malformed floating-point values, data corruption, or even memory safety issues if boundaries are violated.

These examples clearly demonstrate RGFuzz's capacity to find subtle yet critical flaws in the WebAssembly compilation pipeline. The ability to automatically generate test cases that expose such nuanced semantic errors validates the novel rule-guided and reverse stack-based generation techniques as highly effective for improving the reliability and security of WebAssembly runtimes.

Defensive Implications

▶ Watch: Summary of RGFuzz and its impact (7:40)

The findings presented by RGFuzz have significant implications for developers, security researchers, and users of WebAssembly. The discovery of 20 new bugs, including one CVE, across widely used runtimes underscores that even mature and well-tested compilers can harbor subtle semantic flaws, particularly in their complex optimization layers.

For WebAssembly runtime developers, the primary takeaway is the critical need for more robust and targeted testing methodologies. Relying solely on general-purpose fuzzers is insufficient to uncover the deep, IR-level miscompilations demonstrated by RGFuzz. Developers should consider integrating rule-guided fuzzing techniques similar to RGFuzz into their continuous integration and testing pipelines. This involves:

• Extracting and formalizing optimization rules: A clear understanding and formal definition of compiler optimization rules are prerequisites for any rule-guided fuzzer.
• Implementing IR-aware test generation: Tools that can bridge the gap between high-level language constructs (Wasm) and low-level compiler IR are essential for targeting optimization logic effectively.
• Differential testing: Continuously running Wasm programs with and without optimizations, or across different runtime versions, remains a crucial strategy, but it must be fed with intelligently generated test cases.
• Prioritizing patches: Promptly patching identified miscompilation bugs is vital, as these can have silent but pervasive impacts on applications.

For applications built on WebAssembly, particularly those in security-sensitive domains (e.g., blockchain, confidential computing, edge computing), the presence of these bugs highlights the importance of:

• Staying updated: Ensuring that Wasm runtimes are kept up-to-date with the latest security patches is paramount.
• Thorough testing: While runtime developers are responsible for the compiler, application developers should also conduct their own rigorous testing, especially for critical logic, and consider the potential for miscompilation if using specific, complex Wasm features.
• Redundancy and verification: In highly critical systems, employing redundant execution across different Wasm runtimes or implementing runtime checks to verify critical computations could mitigate risks from subtle miscompilations.

Finally, for security researchers and tool developers, RGFuzz provides a blueprint for advancing the state of the art in compiler fuzzing. The techniques of instruction and IR-level inference, combined with reverse stack-based generation, offer a powerful paradigm for exploring complex compiler internals. Adapting these methods to other language runtimes, virtual machines, or even native compilers could uncover similar classes of elusive bugs, thereby improving the overall security and reliability of modern software infrastructure. The research emphasizes that the complexity introduced by performance optimizations is a persistent source of vulnerabilities that requires sophisticated, domain-specific fuzzing strategies to address effectively.

Key Takeaways

• Semantic Bugs in Wasm Runtimes: Compiler optimizations in WebAssembly runtimes are a significant source of semantic bugs (miscompilations) that can lead to incorrect program execution or security vulnerabilities.
• Limitations of Traditional Fuzzing: Existing fuzzers struggle to generate WebAssembly programs that can effectively cover complex, multi-IR compiler optimization rules due to a lack of guidance and diversity.
• Rule-Guided Fuzzing (RGF): RGFuzz introduces an innovative approach that extracts compiler optimization rules and uses them directly to guide Wasm program generation, enabling targeted exploration of intricate optimization paths.
• Two-Level Inference: RGFuzz bridges the gap between IR-level optimization rules and Wasm-level generation through instruction-level and IR-level inference, allowing it to construct Wasm programs that map to specific IR patterns.
• Reverse Stack-Based Generation (RSG): This technique enhances diversity in test case generation by simplifying stack constraints for complex Wasm instructions, overcoming limitations of previous AST-based and stack-based fuzzers.
• Significant Bug Discovery: RGFuzz successfully found 20 new bugs, including one CVE, across six widely used WebAssembly runtimes, demonstrating its practical effectiveness in improving Wasm runtime security.

About the Speaker(s)

The talk was presented by JunYoung Park from Kais, along with Yunho Kim and Insu Yun. As researchers, their work focuses on enhancing the security and reliability of software systems, with this particular contribution highlighting their expertise in compiler security, fuzzing techniques, and the WebAssembly ecosystem.