🏗️ Move wasm-smith's non-trapping mode logic to CodeBuilder #769

itsrainy · 2022-09-20T17:07:38Z

Prior to this change, the non-trapping logic in wasm-smith was implemented as a post-processing step. Random wasm would get generated and then the no_traps() logic would attempt to modify the generated instructions to ensure that the resulting wasm wouldn't trap. This led to a couple challenges: there are some instructions (such as unreachable and call_indirect) that we don't want to emit at all in non-trapping mode, and there are some instructions that we haven't yet implemented a non-trapping solution for (such as SIMD Lane loads/stores). This meant that running wasm-smith in non-trapping mode could still result in a wasm program that would trap. While discussing how best to communicate and work around this nuance, @fitzgen and I realized that these were probably better dealt with while the code is being generated, rather than after the fact.

This change moves much of the non-trapping logic from src/core/no_traps.rs to a code_builder module (src/core/code_builder/no_traps.rs). It then calls into those functions from CodeBuilder, while entirely avoiding unreachable, call_indirect, and possibly trapping instructions that we haven't yet dealt with.

TODO:

I'm currently working on adding a fuzz target to verify that disallow_traps works and to find the cases I inevitably missed

fitzgen

LGTM, although yeah we should have that fuzz target

crates/wasm-smith/src/core.rs

crates/wasm-smith/src/core/code_builder.rs

itsrainy · 2022-09-20T19:40:34Z

crates/wasm-smith/src/core/no_traps.rs

-
-    /// Mask data and element segments' offsets to be in bounds of their
-    /// associated tables and memories.
-    fn no_trapping_segments(&mut self) {


i just realized I never moved this over

nagisa · 2022-09-22T13:12:49Z

crates/wasm-smith/src/core/code_builder.rs

+    if module.config.disallow_traps() {
+        no_traps::store(
+            Instruction::V128Store { memarg },
+            module,
+            builder,
+            instructions,
+        );
+    } else {
+        instructions.push(Instruction::V128Store { memarg });
+    }


I’m wondering if this pattern would be better served by making a choice between trapping or non-trapping variants and then generating an instruction that is guaranteed to be either way? Are there any instructions that would fall in the “unknown” territory somewhere?

This sort of split model would allow to easily add/maintain other kinds of generation “modes” as well (e.g. deterministic vs non-deterministic), and I wonder if it would result in better fuzz coverage (the fuzzer would be able to flip between the two broad categories of instructions at runtime on a per-instruction basis)

@nagisa that's interesting! I'm wondering how useful the "guaranteed to trap" case would actually be. If we were to create a version of this code that does the opposite (ie. makes every division have a denominator of 0, makes every load/store have an out of bounds address, etc), then I would think any generated programs would trap relatively early and not improve coverage all that much except in testing that traps are handled correctly by the runtime. Maybe a wasm-smith flag to generate programs that are guaranteed to eventually trap would be helpful for improving coverage, since that would allow us to explore whether different program state affects the trap-handling behavior of the runtime.

Either way, maybe we discuss this further on #266 (or a new issue)? I think work in that direction could be an improvement on this work, but not immediately necessary.

As far as ease of adding/maintaining other modes, I agree that having this turn into something like the below would be unideal:

if option_1 { generate_instruction(); } else if option_2 { generate_instruction_but_slightly_differently(); } else { generate_instruction_more_differently(); }

That being said, I think I'm inclined to leave that kind of refactoring for when/if we actually add more modes like this

That being said, I think I'm inclined to leave that kind of refactoring for when/if we actually add more modes like this

Of course, that was just me thinking out loud, not necessarily suggesting that this must be implemented here and now ^^ Should have made it clear in my original comment.

itsrainy · 2022-09-22T23:49:23Z

@fitzgen I've been finagling with the fuzzer for a little bit and I haven't been able to get any functions to run yet, but I think I might be close(🤞).

The fuzzer currently errs on line 49 with

Insufficient resources: memory minimum size of 281474976710656 pages exceeds memory limits

I'm not sure where that size is coming from, but I think it's in the Memory being generated by dummy_imports. I haven't found any immediately obvious config options for Store, Engine, or Module that seem like they'd let me set that to something reasonable.

itsrainy · 2022-09-22T23:51:30Z

fuzz/fuzz_targets/no-traps.rs

+        config.threads_enabled = false;
+        config.allow_start_export = false;
+        config.max_memories = config.max_memories.min(1);
+        config.memory64_enabled = true;
+        config.exceptions_enabled = false;


These config options were mostly an attempt to get around errors that were preventing the Module or Store from getting instantiated. I would not be surprised if some of these aren't actually necessary.

fitzgen

Looks pretty good, a few suggestions below. Is it running and passing?

fitzgen · 2022-09-23T18:16:27Z

fuzz/Cargo.toml

+path = "fuzz_targets/no-traps.rs"
+test = false
+doc = false
+required-features = ["wasmtime"]


Nitpick: no newline at the end of the file.

fitzgen · 2022-09-23T18:17:41Z

fuzz/fuzz_targets/no-traps.rs

+    let (wasm_bytes, config) = match wasm_tools_fuzz::generate_valid_module(&mut u, |config, _| {
+        config.disallow_traps = true;
+        config.threads_enabled = false;
+        config.allow_start_export = false;


I don't think this should be necessary.

fitzgen · 2022-09-23T18:17:53Z

fuzz/fuzz_targets/no-traps.rs

+        config.threads_enabled = false;
+        config.allow_start_export = false;
+        config.max_memories = config.max_memories.min(1);
+        config.memory64_enabled = true;


I don't think this should be necessary either.

fitzgen · 2022-09-23T18:18:09Z

fuzz/fuzz_targets/no-traps.rs

+        config.disallow_traps = true;
+        config.threads_enabled = false;
+        config.allow_start_export = false;
+        config.max_memories = config.max_memories.min(1);


Not this one actually.

fitzgen · 2022-09-23T18:19:43Z

fuzz/fuzz_targets/no-traps.rs

+                store.add_fuel(1_000).unwrap();
+                match func.call(&mut store, &args, &mut results) {
+                    Ok(_) => continue,
+                    Err(_) => panic!("wasm trapped"),


The trap might be because we ran out of fuel, in which case it is fine and we can continue.

fitzgen · 2022-09-23T18:20:48Z

fuzz/fuzz_targets/no-traps.rs

+                let mut results = dummy::dummy_values(func_ty.results());
+                let func = instance.get_func(&mut store, export.name()).unwrap();
+                func_ty.results();
+                store.add_fuel(1_000).unwrap();


You probably want to reset to exactly 1000 fuel each time, rather than keep adding 1000 in the case where there is left over fuel from last iteration.

https://cs.github.com/bytecodealliance/wasmtime/blob/bb6a8a717ab9dcf0594a577893fb31a6528ada1b/crates/fuzzing/src/oracles.rs?q=set_fuel#L790-L801

fitzgen · 2022-09-23T18:22:16Z

fuzz/fuzz_targets/no-traps.rs

+    // Validate the module or component and assert that it passes validation.
+    let mut validator = wasmparser::Validator::new_with_features(wasmparser::WasmFeatures {
+        component_model: false,
+        multi_value: config.multi_value_enabled,
+        multi_memory: config.max_memories > 1,
+        bulk_memory: true,
+        reference_types: true,
+        simd: config.simd_enabled,
+        relaxed_simd: config.relaxed_simd_enabled,
+        memory64: config.memory64_enabled,
+        threads: config.threads_enabled,
+        exceptions: config.exceptions_enabled,
+        ..wasmparser::WasmFeatures::default()
+    });
+    if let Err(e) = validator.validate_all(&wasm_bytes) {
+        panic!("Invalid module: {}", e);
+    }


Might be a little bit easier to read this fuzz target if validation was pulled out into a validate function and then calling exports was also pulled out into its own call_function_exports function or something like that. As is, it is a bit of a wall of code to read.

fitzgen · 2022-09-23T18:24:43Z

The fuzzer currently errs on line 49 with

We can configure a maximum to the size of memories generated to avoid this issue.

itsrainy · 2022-09-23T18:36:29Z

Looks pretty good, a few suggestions below. Is it running and passing?

No not yet! As-is it bails at line 49 every time so it isn't even making it to the function calls. I'll remove the config options that aren't needed but I might need some help to figure out how to properly instantiate the wasm. I roughly followed the pattern in the failed-instantiations fuzzer, but I think I'm missing something

itsrainy · 2022-10-27T19:24:11Z

I've spent some time these past couple days tracking down some edge cases in the non-trapping logic. My general workflow for this has been:

Run the no-traps fuzz target (cargo fuzz run no-traps --features=wasmtime -s none)
Wait 3-10 minutes for the fuzzer to find a crash
Minimize the case (cargo fuzz tmin ....)
Figure out what the issue is by looking at the resulting .wat, our trap-avoiding logic, the specific wasmtime error, etc.
Repeat

The amount of time spent at step 2 is increasing (which is good!), but due to the nature of this, it's hard to know if there are 3 more bugs or 300 more bugs. A good "readiness" measure here might be "fuzzer runs for X minutes without crashing" or even better "the fuzz target is starting to find issues elsewhere". For now, I'm going to step away for a day or so and continue plugging away at this later.

Co-authored-by: Nick Fitzgerald <fitzgen@gmail.com>

in non-trapping mode

Co-authored-by: Nick Fitzgerald <fitzgen@gmail.com>

It was occasionally running into an 'attempt to multiply with overflow' for 32-bit memories, so we check the value before casting to avoid that.

for using eq, but it is the only value that is not equal to itself, so ne will work.

an f64. This is necessary because `i64::MAX as f64` will result in an f64 value that is not representable by an i64.

…ctions that must check if the memory offset plus the size of the type is within the bounds of our memory. In order for us to emit this code, that value must fit in a u64. In the case where the memory offset is u64::MAX, then our rust code panics in trying to generate the wasm due to an attempt to add with overflow. To solve this, I've added an upper bound on our memory offsets for load operations while running in non-trapping mode.

… mode

This was happening with modules that had a large number of memory.grow or table.grow instructions.

itsrainy · 2022-11-07T16:47:38Z

The only traps this is now throwing for me are StackOverflows on modules with recursive functions that look something like this:

  (func (;0;) (type 0) (result f64)
    call 0
     ...
   )

These can't easily be avoided without somehow keeping track of the call-stack size, which we'd have to do in the emitted wasm, and then somehow handling the "we're about to exceed our stack depth" case. It takes the fuzzer a few hours to run into this case on my machine.

From chatting with @fitzgen it sounds like ignoring this for now and documenting the behavior in the config docs should be good for the time being.

If I add a case to ignore StackOverflow traps, like this:

- Err(err) if err.to_string().contains("all fuel consumed") => continue,
+ Err(err)
+     if err.to_string().contains("all fuel consumed")
+         || err.to_string().contains("call stack exhausted") =>
+ {
+     continue
+ }

then the fuzzer runs for 20+ hours on my machine! I think this means that we've found all the cases that we would expect to trap 🎉

@fitzgen any other changes you'd like to see here?

fitzgen

Looks great, thanks @itsrainy! Just one nitpick about documentation.

crates/wasm-smith/src/config.rs

fitzgen

Thanks! This was a big one!

itsrainy force-pushed the rainy/code-builder-no-traps branch from 5368d5d to 4a4b4a7 Compare September 20, 2022 17:33

fitzgen approved these changes Sep 20, 2022

View reviewed changes

crates/wasm-smith/src/core.rs Outdated Show resolved Hide resolved

crates/wasm-smith/src/core/code_builder.rs Outdated Show resolved Hide resolved

itsrainy commented Sep 20, 2022

View reviewed changes

nagisa reviewed Sep 22, 2022

View reviewed changes

itsrainy commented Sep 22, 2022

View reviewed changes

fitzgen reviewed Sep 23, 2022

View reviewed changes

itsrainy force-pushed the rainy/code-builder-no-traps branch from d6cf31b to 12b440a Compare October 3, 2022 21:22

itsrainy mentioned this pull request Oct 4, 2022

Adjust fuel consumption to be empty when fuel is at 0 rather than 1 bytecodealliance/wasmtime#5013

Merged

itsrainy force-pushed the rainy/code-builder-no-traps branch from a28e99d to 9eb28a0 Compare October 25, 2022 16:37

itsrainy and others added 17 commits October 27, 2022 15:51

Change CodeBuilder functions to emit multiple instructions

1fd44cf

Co-authored-by: Nick Fitzgerald <fitzgen@gmail.com>

Move no-trapping logic to a code_builder module

a9fc52e

Add configuration option to disallow traps

0123e51

Don't generate trapping instructions that haven't been handled yet

77bc09f

in non-trapping mode

Remove unused import_count function

e21bd93

Update crates/wasm-smith/src/core/code_builder.rs

2fcf98e

Add first pass at fuzzer to verify non-trapping mode does not trap

9ec356a

rebase

2b24907

Address review comments

df12a02

Handle table and element segments in no-trapping mode

1bd49f4

Co-authored-by: Nick Fitzgerald <fitzgen@gmail.com>

Fix smoke test for non-trapping mode

c21d147

It was occasionally running into an 'attempt to multiply with overflow' for 32-bit memories, so we check the value before casting to avoid that.

Clamp generated data offset to min memory size minus data length

bb29731

Handle running out of fuel during instantiation

1f82680

Don't generate simd instructions in non-trapping mode

da9a663

Use ne rather than eq to check for NaN values. NaN can't be checked

b2a21dd

for using eq, but it is the only value that is not equal to itself, so ne will work.

Perform bounds checking for trunc instructions in non-trapping mode

e90582e

Adjust fuel to avoid "out of fuel" error on consume(0)

62c27b3

itsrainy added 3 commits October 27, 2022 15:52

Explicitly specify the largest/smallest i64 that can be represented as

4fda694

an f64. This is necessary because `i64::MAX as f64` will result in an f64 value that is not representable by an i64.

Don't emit unreachable instructions in non-trapping mode

a42cabf

itsrainy force-pushed the rainy/code-builder-no-traps branch from 3af5bea to a42cabf Compare October 27, 2022 19:52

itsrainy added 7 commits November 2, 2022 15:08

Explicitly specify max/min values for f32

1b35fdb

Handle min/max f32 values representable as i32

9c9f68b

Ensure stores/loads with negative addresses don't trap

9dde658

Don't allow stores with memarg.offset==i64::MAX while in non-trapping…

eed452c

… mode

Refactor mem offset calculation to be in one place

d2df2f8

Use a ResourceLimiter to prevent libfuzzer from running out of memory.

7ef8bac

This was happening with modules that had a large number of memory.grow or table.grow instructions.

Clean up code a little bit

3a761e6

fitzgen approved these changes Nov 8, 2022

View reviewed changes

crates/wasm-smith/src/config.rs Outdated Show resolved Hide resolved

Add doc to disallow_traps explaining StackOverflow traps

9a1a86f

fitzgen approved these changes Nov 9, 2022

View reviewed changes

fitzgen merged commit 31e4f11 into bytecodealliance:main Nov 9, 2022

itsrainy deleted the rainy/code-builder-no-traps branch November 9, 2022 18:59

alexcrichton mentioned this pull request Dec 2, 2022

wasm-smith: add a "no trapping" mode #266

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

🏗️ Move wasm-smith's non-trapping mode logic to CodeBuilder #769

🏗️ Move wasm-smith's non-trapping mode logic to CodeBuilder #769

itsrainy commented Sep 20, 2022

fitzgen left a comment

itsrainy Sep 20, 2022

nagisa Sep 22, 2022

itsrainy Sep 22, 2022 •

edited

nagisa Sep 22, 2022

itsrainy commented Sep 22, 2022

itsrainy Sep 22, 2022

fitzgen left a comment

fitzgen Sep 23, 2022

fitzgen Sep 23, 2022

fitzgen Sep 23, 2022

fitzgen Sep 23, 2022

fitzgen Sep 23, 2022

fitzgen Sep 23, 2022

fitzgen Sep 23, 2022

fitzgen commented Sep 23, 2022

itsrainy commented Sep 23, 2022 •

edited

itsrainy commented Oct 27, 2022 •

edited

itsrainy commented Nov 7, 2022

fitzgen left a comment

fitzgen left a comment

🏗️ Move wasm-smith's non-trapping mode logic to CodeBuilder #769

🏗️ Move wasm-smith's non-trapping mode logic to CodeBuilder #769

Conversation

itsrainy commented Sep 20, 2022

fitzgen left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

itsrainy Sep 22, 2022 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

itsrainy commented Sep 22, 2022

Choose a reason for hiding this comment

fitzgen left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

fitzgen commented Sep 23, 2022

itsrainy commented Sep 23, 2022 • edited

itsrainy commented Oct 27, 2022 • edited

itsrainy commented Nov 7, 2022

fitzgen left a comment

Choose a reason for hiding this comment

fitzgen left a comment

Choose a reason for hiding this comment

itsrainy Sep 22, 2022 •

edited

itsrainy commented Sep 23, 2022 •

edited

itsrainy commented Oct 27, 2022 •

edited