alexcrichton opened issue #4322:
Wasmtime recently had https://github.com/bytecodealliance/wasmtime/issues/4315 filed against it which discovered that there were two separate bugs in the SIMD implementation on x86_64. This discovery comes after "months of continuous oss-fuzzing" for the simd feature. I wanted to file an issue here with some investigation of why this happened because this theoretically should not happen.
Specifically here the bug was a buggy instruction lowering (two different ones). One fix (https://github.com/bytecodealliance/wasmtime/pull/4318) surfaced by corrupting an input register which I think only causes issues if the input is attempted to be reused elsewhere (e.g. a constant reused somewhere else). I don't know precisely but my impression was that this involved some register pressure, a "big" function, and constants to line up. This specific bug I could see as very difficult to discover via wasm-smith. The second bug, however, (https://github.com/bytecodealliance/wasmtime/pull/4317) was a trivial bug in the
select
instruction which showed up with the smallest of tests forselect
. The fact that wasm-smith never discovered this is alarming to me.Digging in it appears to be a confluence of factors which makes wasm-smith basically unable to find these bugs:
- The
select
instruction requires 3 operands on the stack of specific types. Turns out this very rarely happens. I inserted apanic!
whenever aselect
instruction was even considered a candidate, and it was rarely hit. Even less rarely is the instruction chosen to be emitted.- The
i32
input toselect
I think is almost always nonzero at runtime itself. The specific bug only happened when the condition was 0, however. I think this is because a lot of i32s come from things likei32.const
which is practically never zero.- Even if
select
is generated with v128 inputs (which happens quite rarely) it's often never actually even executed at runtime. The few test cases I found which generated this instruction immediately had infinite recursion or an infinite loop with the interesting instructions far away.I unfortunately don't know if there's really a "fix" for issues like this. We could throw a bunch more heuristics at wasm-smith but at some point we probably need a somewhat fundamental new strategy for fuzzing here to get significantly more coverage.
cfallin commented on issue #4322:
I suspect that for individual instruction semantics, something like #3251 might be a reasonable solution. If we focus on generating test cases for individual Wasm instructions, we can drive the random code generation in the other direction: e.g. we have a
v128.select
, we know what the stack signature is, let's provide those inputs. Along the same lines, "unit-testing" individual instructions lets us more easily run through their input data-space with many test vectors (invocations) for one function.Without coverage feedback libFuzzer may not know that some of those inputs are only sensitive to particular values (e.g. zero), but we could maybe bias probabilities too, if needed. (Custom entropy based on... similar bits? Closeness of some args to others? Surely the propcheck/quickcheck folks have some useful heuristics here...)
All the above won't give us coverage of multiple-instruction patterns (I think this objection was also raised in #3251) but unit-testing instruction lowerings seems like a sufficiently useful and unique use-case to me that it's worth its own fuzz target and approach...
alexcrichton labeled issue #4322:
Wasmtime recently had https://github.com/bytecodealliance/wasmtime/issues/4315 filed against it which discovered that there were two separate bugs in the SIMD implementation on x86_64. This discovery comes after "months of continuous oss-fuzzing" for the simd feature. I wanted to file an issue here with some investigation of why this happened because this theoretically should not happen.
Specifically here the bug was a buggy instruction lowering (two different ones). One fix (https://github.com/bytecodealliance/wasmtime/pull/4318) surfaced by corrupting an input register which I think only causes issues if the input is attempted to be reused elsewhere (e.g. a constant reused somewhere else). I don't know precisely but my impression was that this involved some register pressure, a "big" function, and constants to line up. This specific bug I could see as very difficult to discover via wasm-smith. The second bug, however, (https://github.com/bytecodealliance/wasmtime/pull/4317) was a trivial bug in the
select
instruction which showed up with the smallest of tests forselect
. The fact that wasm-smith never discovered this is alarming to me.Digging in it appears to be a confluence of factors which makes wasm-smith basically unable to find these bugs:
- The
select
instruction requires 3 operands on the stack of specific types. Turns out this very rarely happens. I inserted apanic!
whenever aselect
instruction was even considered a candidate, and it was rarely hit. Even less rarely is the instruction chosen to be emitted.- The
i32
input toselect
I think is almost always nonzero at runtime itself. The specific bug only happened when the condition was 0, however. I think this is because a lot of i32s come from things likei32.const
which is practically never zero.- Even if
select
is generated with v128 inputs (which happens quite rarely) it's often never actually even executed at runtime. The few test cases I found which generated this instruction immediately had infinite recursion or an infinite loop with the interesting instructions far away.I unfortunately don't know if there's really a "fix" for issues like this. We could throw a bunch more heuristics at wasm-smith but at some point we probably need a somewhat fundamental new strategy for fuzzing here to get significantly more coverage.
alexcrichton commented on issue #4322:
I had forgotten about that issue! That's an excellent point though. I also filed https://github.com/bytecodealliance/wasmtime/issues/4338 as possible other wasm fuzzers we could integrate. Otherwise though other wasm-smith improvements include https://github.com/bytecodealliance/wasm-tools/issues/266.
While this may not be the most useful issue to keep open I'm tempted to leave it here as "if anyone searches the fuzzing tag in the Wasmtime repo this'll trigger them to think about improving wasm-smith"
abrown commented on issue #4322:
Hey, I had completely forgotten about #3251 but I believe when I added
allowed_instructions
towasm-smith
it was motivated in part by that issue. The idea would be to configurewasm-smith
to only allow could be configured to generate functions with, e.g., numeric and vector instructions (seeInstructionKind
for the categories allowed) and setmax_instructions
to, e.g., 3 (to test possible interactions with other instructions). With the small test case generated, we could then also generate instructions in the other direction @cfallin mentions, by randomizing the function arguments. What do you all think of that as a new fuzz target?
abrown edited a comment on issue #4322:
Hey, I had completely forgotten about #3251 but I believe when I added
allowed_instructions
towasm-smith
it was motivated in part by that issue. The idea would be to configurewasm-smith
to generate functions with, e.g., numeric and vector instructions (seeInstructionKind
for the categories allowed) and setmax_instructions
to, e.g., 3 (to test possible interactions with other instructions). With the small test case generated, we could then also generate instructions in the other direction @cfallin mentions, by randomizing the function arguments. What do you all think of that as a new fuzz target?
fitzgen commented on issue #4322:
We could also add a "no control flow" mode to
wasm-smith
, which might end up pretty similar to the "test a single instruction" thing in practice.In fact, @abrown added the
InstructionKinds
filtering and we don't really use that in our fuzz targets yet. Covers a lot of the same stuff. We could actually probably use this to avoid control instructions already.I think we also only pass zeros in as arguments to whatever functions we generate, and we could probably do much better than that as well (at least try zero, max, and one random bit pattern).
abrown edited a comment on issue #4322:
Hey, I had completely forgotten about #3251 but I believe when I added
allowed_instructions
towasm-smith
it was motivated in part by that issue. The idea would be to configurewasm-smith
to generate functions with, e.g., numeric and vector instructions (seeInstructionKind
for the categories allowed) and setmax_instructions
to, e.g., 3 (to test possible interactions with other instructions). With the small test case generated, we could then also randomly generate in the value space that @cfallin mentions, by randomizing the function arguments. What do you all think of that as a new fuzz target?
fitzgen commented on issue #4322:
@abrown jinx ;)
What do you all think of that as a new fuzz target?
Yes, definitely.
alexcrichton commented on issue #4322:
One thing I think we'd also want to change about wasm-smith is the signatures of functions as well. Right now we drop all values that don't correspond to the function's type so differential fuzzing has a hard time picking these up. Ideally we want a mode where we generate the function body first and then we wrap that in a function of the appropriate type.
abrown commented on issue #4322:
Hm... how? I wasn't really aware of the limitations on function signatures.
fitzgen commented on issue #4322:
We just choose a signature, and then generate a body. Alex is suggesting we generate a body and then derive a signature from that.
fitzgen commented on issue #4322:
Makes sense for returns, not necessarily for parameters though, since generating a body needs to know what locals are available.
abrown commented on issue #4322:
Or the first instruction dictates what locals _must_ be available which should bubble up to the signature... This is the part that I'm having trouble seeing in wasm-smith. It doesn't seem designed for this kind of thing?
abrown commented on issue #4322:
Ok, how about this: we add
SingleFunctionModule
towasm-smith
which takes aConfig
, anUnstructured
, and aSignature
. TheSignature
could be something like:pub struct Signature { params: Vec<ValTy>, returns: Vec<ValTy>, }
ValTy
would be some set-like struct that could beArbitrary
-generated and would cover the Wasm types (i32
,f32
,v128
, etc.). So one could either manually set the parameters of the function (I think this has come up in the past as a need) OR one could generate thisSignature
with a range of types. (Or something like that... looking for feedback here).The
SingleFunctionModule
would then... well, what _would_ it do? Generate instructions to use all of the arguments before we get tomax_instructions
? We don't have to re-local.get
the arguments, right?
alexcrichton commented on issue #4322:
One idea is to perhaps:
- Generate an arbitrary list of parameters
- Generate an arbitrary function body using those parameters
- Using what's left on the stack assign that as the return value of the function
- Insert the final function type into a module
I like the idea though of using a completely new dedicated
SingleFunctionModule
(or similar) generator for this. That module could also have a list of values to invoke the exported function with perhaps?
abrown commented on issue #4322:
So you mean "arbitrary list of parameters" not "arbitrary list of parameter types"?
alexcrichton commented on issue #4322:
Oh sorry I meant types there, but I was thinking we could in actuality do:
- generate an arbitrary list of parameter types
- Additionally, afterwards, generate a list of arbitrary values to invoke the function with
whether that second step belongs in wasm-smith or wasmtime I dunno but either seems fine by me
alexcrichton commented on issue #4322:
The single-instruction generator from Andrew came out of this and nothing else has turned up in the meantime. Additionally Andrew did a lot of refactoring to have one
differential
fuzzer so I think we're in a better place now (hopefully). I'm going to subsequently close this.
alexcrichton closed issue #4322:
Wasmtime recently had https://github.com/bytecodealliance/wasmtime/issues/4315 filed against it which discovered that there were two separate bugs in the SIMD implementation on x86_64. This discovery comes after "months of continuous oss-fuzzing" for the simd feature. I wanted to file an issue here with some investigation of why this happened because this theoretically should not happen.
Specifically here the bug was a buggy instruction lowering (two different ones). One fix (https://github.com/bytecodealliance/wasmtime/pull/4318) surfaced by corrupting an input register which I think only causes issues if the input is attempted to be reused elsewhere (e.g. a constant reused somewhere else). I don't know precisely but my impression was that this involved some register pressure, a "big" function, and constants to line up. This specific bug I could see as very difficult to discover via wasm-smith. The second bug, however, (https://github.com/bytecodealliance/wasmtime/pull/4317) was a trivial bug in the
select
instruction which showed up with the smallest of tests forselect
. The fact that wasm-smith never discovered this is alarming to me.Digging in it appears to be a confluence of factors which makes wasm-smith basically unable to find these bugs:
- The
select
instruction requires 3 operands on the stack of specific types. Turns out this very rarely happens. I inserted apanic!
whenever aselect
instruction was even considered a candidate, and it was rarely hit. Even less rarely is the instruction chosen to be emitted.- The
i32
input toselect
I think is almost always nonzero at runtime itself. The specific bug only happened when the condition was 0, however. I think this is because a lot of i32s come from things likei32.const
which is practically never zero.- Even if
select
is generated with v128 inputs (which happens quite rarely) it's often never actually even executed at runtime. The few test cases I found which generated this instruction immediately had infinite recursion or an infinite loop with the interesting instructions far away.I unfortunately don't know if there's really a "fix" for issues like this. We could throw a bunch more heuristics at wasm-smith but at some point we probably need a somewhat fundamental new strategy for fuzzing here to get significantly more coverage.
Last updated: Dec 23 2024 at 12:05 UTC