Stream: git-wasmtime

Topic: wasmtime / PR #3038 Cranelift CLIF-level differential fuzzer

Wasmtime GitHub notifications bot (Jun 28 2021 at 08:38):

afonso360 edited PR #3038 from fuzz-gen to main.

Wasmtime GitHub notifications bot (Jun 28 2021 at 18:01):

cfallin submitted PR review.

Wasmtime GitHub notifications bot (Jun 28 2021 at 18:01):

cfallin created PR review comment:

Tiny nit, but I personally prefer doc-comments to end in periods (e.g. "Compilation Error when compiling a function.").

Wasmtime GitHub notifications bot (Jun 28 2021 at 18:01):

cfallin submitted PR review.

Wasmtime GitHub notifications bot (Jun 28 2021 at 18:01):

cfallin created PR review comment:

Should there be an error-case for "timeout", i.e. ran too long? I'll keep reading to see how infinite loops are caught but this seems like a separate logical case from explicit trap.

Wasmtime GitHub notifications bot (Jun 28 2021 at 18:01):

cfallin created PR review comment:

Ah, it seems we might want a "run for max N steps" method on the interpreter here. Otherwise, if we have an infinite loop (when fuzz-case generation becomes sophisticated enough for that, if it's not already?), we tie up a core indefinitely.

There's a question whether we step for N steps on both sides (interp and compiled) and then compare state at the end, or if we just reject inputs that run that long. I suspect probably the latter is good enough; the former would require instrumentation in the compiler to count ops and stop. We have "fuel" at the Wasmtime level but it's not built-in to Cranelift itself. And, anything a testcase could do to run indefinitely would be tested by other valid test cases as well, so I think it's fine to avoid these inputs altogether.

Wasmtime GitHub notifications bot (Jun 28 2021 at 18:01):

cfallin created PR review comment:

I'd prefer for the fuzz target to be integrated into the toplevel Wasmtime fuzzer crate, I think: while Cranelift is logically separate, it lives in the same repository, is already fuzzed by other fuzz targets there, and it is somewhat confusing to have two different fuzz directories.

Wasmtime GitHub notifications bot (Jun 28 2021 at 18:01):

cfallin created PR review comment:

For now (a first version), we could just reject inputs that trap in the interpreter too, right? This of course means we don't cover edge-cases like "divide should trap in exactly these cases".

I think that trap functionality is also generally handled by the runtime, e.g. Wasmtime, so we would have to build out another Cranelift-level implementation for this to be tested properly; that strikes me as disproportionate effort for the given reward, since trap cases are covered by Wasm tests and Wasm-level fuzzing as well.

Wasmtime GitHub notifications bot (Jun 28 2021 at 18:01):

cfallin created PR review comment:

If we implement Arbitrary for the testcase type, can we just take that type in the fuzz_target!'s lambda directly? I'd prefer that both as it's a little more idiomatic and for the specific reason that this gives us a proper Debug-print of failing test cases.

Wasmtime GitHub notifications bot (Jun 28 2021 at 18:01):

cfallin created PR review comment:

Taking the Arbitrary type directly (comment above) also means we don't have to manually handle this case.

Wasmtime GitHub notifications bot (Jun 28 2021 at 18:01):

cfallin created PR review comment:

End sentence with ., and capitalize "Cranelift" here and below.

Wasmtime GitHub notifications bot (Jun 28 2021 at 18:01):

cfallin created PR review comment:

s/util/utility/

Wasmtime GitHub notifications bot (Jun 28 2021 at 18:01):

cfallin created PR review comment:

This is already supported by cargo fuzz (e.g., cargo fuzz run fuzzgen ./fuzz/artifacts/... -- do we need a separate implementation of it?

Wasmtime GitHub notifications bot (Jun 28 2021 at 18:01):

cfallin created PR review comment:

This "available variables" approach is nice, but gets somewhat complicated with control flow, and you can see e.g. in the regalloc2 SSA generator there's a two-staged approach where we decide what values are defined in each block first, then (i) pick among values defined in blocks that dominate us for uses, (ii) ensure we define all vars we said we would in a given block.

So, in this implementation, what happens if the variable is defined, but only in one predecessor? Do we unconditionally re-define it (and let the frontend handle the SSA fixup for that)?

Another workaround is to decide at the top of the function which variables will exist, and assign initial values to all of them. Then all the rest of the instruction outputs are just redefinitions. This is actually probably the easiest and least buggy (which is what we want for a fuzztest generator!) and still shouldn't sacrifice any coverage, since it can turn into arbitrary SSA.

Wasmtime GitHub notifications bot (Jun 28 2021 at 18:01):

cfallin created PR review comment:

As an aside, I very much like that this is designed to support multiple test inputs per function; this lets us get the most out of the cost of one compilation. Maybe a comment to this effect here?

Wasmtime GitHub notifications bot (Jun 28 2021 at 18:01):

cfallin created PR review comment:

We could, in theory, extend the codegen in the cranelift-meta crate to generate something like this table. I think it would be generally useful to have such a table for other table-driven code, too.

Wasmtime GitHub notifications bot (Jun 28 2021 at 18:01):

cfallin created PR review comment:

As mentioned above, I think that this binary is probably not necessary.

One use-case that you mentioned in the readme is to use this to quickly test the generator in an ad-hoc way. But a better idea might be to have a separate fuzz target that only runs the fuzztest generator, and then checks that the result passes the CLIF validator. In this way, you can test that we're generating valid CLIF. This is what e.g. the ssagen target in regalloc2 does.

Wasmtime GitHub notifications bot (Jun 29 2021 at 10:20):

afonso360 submitted PR review.

Wasmtime GitHub notifications bot (Jun 29 2021 at 10:20):

afonso360 created PR review comment:

No, The main reason I built this was to produce an easily sharable test case, but i see that cargo-fuzz fmt with the Arbitrary impl provides us with that already. I'm going to remove this.

Wasmtime GitHub notifications bot (Jun 29 2021 at 11:41):

afonso360 submitted PR review.

Wasmtime GitHub notifications bot (Jun 29 2021 at 11:41):

afonso360 created PR review comment:

Yeah, lets add this to the TODO queue to be revisited later.

Wasmtime GitHub notifications bot (Jun 29 2021 at 11:48):

afonso360 submitted PR review.

Wasmtime GitHub notifications bot (Jun 29 2021 at 11:48):

afonso360 created PR review comment:

Sounds like a good idea, I've added a new fuzz target that just validates the generated function

Wasmtime GitHub notifications bot (Jun 29 2021 at 12:12):

afonso360 submitted PR review.

Wasmtime GitHub notifications bot (Jun 29 2021 at 12:12):

afonso360 created PR review comment:

when fuzz-case generation becomes sophisticated enough for that, if it's not already?

It isn't simply because we limit the number of generated instructions up to a maximum of 16. Otherwise I think we are simply limited by the input length. On a related note, I moved all of the arbitrary restrictions that we place on the generator into a Config module so that this become more obvious (and so that we can eventually do swarm fuzzing).

There's a question whether we step for N steps on both sides (interp and compiled) and then compare state at the end, or if we just reject inputs that run that long. I suspect probably the latter is good enough

Rejecting inputs that run that long on the interpreter seems like the way to go for me.

Wasmtime GitHub notifications bot (Jun 29 2021 at 12:14):

afonso360 submitted PR review.

Wasmtime GitHub notifications bot (Jun 29 2021 at 12:14):

afonso360 created PR review comment:

I think it makes sense. I'm not seeing a quick way to constrain the interpreter to run just N instructions, so lets add that when we implement branches and control flow.

Wasmtime GitHub notifications bot (Jun 29 2021 at 12:16):

afonso360 submitted PR review.

Wasmtime GitHub notifications bot (Jun 29 2021 at 12:16):

afonso360 created PR review comment:

Great! Lets add this one to the TODO list as well.

Wasmtime GitHub notifications bot (Jun 29 2021 at 12:28):

afonso360 created PR review comment:

The idea here was that this set of "available variables" is defined per block not per function (its not currently separated because we generate just one block), when branching or calling return we choose a random number of variables from the current block to transfer onto the next block (depending on the block "signature").

I don't think we have issues with picking variables defined in predecessors because we never do that, and I don't think we can do that with clif? (I may be wrong here)

Another workaround is to decide at the top of the function which variables will exist, and assign initial values to all of them.

Ah! I didn't know that we could transform non SSA code into SSA code. This might be something that we actually want to fuzz as well. In that case I think this is a good way to go.

Let me know if you want me to change this into the non SSA from.

Wasmtime GitHub notifications bot (Jun 29 2021 at 12:28):

afonso360 submitted PR review.

Wasmtime GitHub notifications bot (Jun 29 2021 at 12:30):

afonso360 edited PR review comment.

Wasmtime GitHub notifications bot (Jun 29 2021 at 12:47):

afonso360 edited PR review comment.

Wasmtime GitHub notifications bot (Jun 29 2021 at 12:52):

afonso360 updated PR #3038 from fuzz-gen to main.

Wasmtime GitHub notifications bot (Jun 29 2021 at 15:23):

afonso360 edited PR review comment.

Wasmtime GitHub notifications bot (Jun 29 2021 at 16:42):

cfallin submitted PR review.

Wasmtime GitHub notifications bot (Jun 29 2021 at 16:42):

cfallin created PR review comment:

when branching ... we choose a random number of variables ... to transfer onto the next block

This definitely works for a straightline sequence of blocks, but how does this work for loops? More generally, if you decide at the end of a block which variables to see as "defined" in the next block, you need to see all in-edges to a block before you know for sure that a variable is defined on every in-edge.

This is the origin of the two-stage approach -- it breaks the cycle: if you pin down what should be defined in each location, you can then, in parallel, both rely on that (in uses) and ensure that (in defs).

I think the easiest answer is to rely on the SSA-builder algorithm built into the variable helper layer which you're using here, and def everything at the top first, then select any variable for each use. The key thing (which I think may be flying under the radar here given the "transfer to the next block" phrasing above) is that "variables" as you're using them are not SSA values or blockparams; the latter are defined by the former depending on where you place the one or more definitions of a variable. (And indeed, a variable can have more than one def.) It's always correct to use a variable that has been defined at least once on every path from the entry block (has some dominating def), so the trivially correct thing to do is define everything (for the first time) in the entry block :-)

Wasmtime GitHub notifications bot (Jun 29 2021 at 17:31):

afonso360 updated PR #3038 from fuzz-gen to main.

Wasmtime GitHub notifications bot (Jun 29 2021 at 17:39):

afonso360 created PR review comment:

I've updated the fuzzer to perform this upfront allocation of variables. I'm slightly concerned that it now seems to be reusing the same variable a lot consecutively, but I think this may be the fuzzer exploring the non ssa to ssa code?

Wasmtime GitHub notifications bot (Jun 29 2021 at 17:39):

afonso360 submitted PR review.

Wasmtime GitHub notifications bot (Jun 29 2021 at 17:39):

afonso360 requested cfallin for a review on PR #3038.

Wasmtime GitHub notifications bot (Jun 30 2021 at 18:56):

afonso360 submitted PR review.

Wasmtime GitHub notifications bot (Jun 30 2021 at 18:56):

afonso360 created PR review comment:

I hadn't seen your reply when writing my previous comment. I've changed it to the upfront allocation and i think it should be better because we are probably going to stress the variable helper a bit more with the fuzzer.

But i'm still not sure i'm following what you are saying.

This definitely works for a straightline sequence of blocks, but how does this work for loops? More generally, if you decide at the end of a block which variables to see as "defined" in the next block, you need to see all in-edges to a block before you know for sure that a variable is defined on every in-edge.

The way I'm thinking about this is as if every block is sort of a function.

function %test(i32, i32) -> i32 {
block0(v0: i32, v1: i32):
    v2 = iconst.i32 10
    jump block1(v1)  ; Here we can choose any of v0, v1, v2

block1(v4: i32):
    v5 = iconst.i32 12
    return v4              ; Here we can choose either v4 or v5 but never v0,v1,v2
}

So in a sense, what I was thinking was: We generate the next block (or reuse an existing one) see what types it has in its signature and choose variables available in the current block to "call" it with (either block params or values locally defined by us).

This way, we don't need to know who called this block, because we never use variables defined by anyone else.

This is more of a curiosity now, because I've changed into the other approach and think it is better, but I'd like to understand why it wouldn't work.

Wasmtime GitHub notifications bot (Jun 30 2021 at 19:00):

afonso360 edited PR review comment.

Wasmtime GitHub notifications bot (Jun 30 2021 at 19:05):

cfallin created PR review comment:

We generate the next block (or reuse an existing one) see what types it has in its signature and choose variables available in the current block to "call" it with (either block params or values locally defined by us).

Ah, I see! The key thing here, I think, is that "what types it has in its signature" is decided before code is generated, and so breaks the cycle: this is the equivalent to the pre-pass I mentioned that decides where to define things so that defs and uses can both rely on those decisions. So this approach would also work.

Given that the cranelift-frontend logic is built to accept multi-def vars and generate SSA, I think that the approach this PR takes now (upfront initializations) is still the right one, but your approach would work well for generating the SSA directly, if we decide to do that instead at some point.

Wasmtime GitHub notifications bot (Jun 30 2021 at 19:05):

cfallin submitted PR review.

Wasmtime GitHub notifications bot (Jun 30 2021 at 19:09):

afonso360 submitted PR review.

Wasmtime GitHub notifications bot (Jun 30 2021 at 19:09):

afonso360 created PR review comment:

Now that I'm looking at this again, I don't think its quite right, we probably should be assigning the block params to the pool of variables instead of creating new ones.

I'll look at this again tommorow

Wasmtime GitHub notifications bot (Jun 30 2021 at 19:10):

cfallin submitted PR review.

Wasmtime GitHub notifications bot (Jun 30 2021 at 19:12):

cfallin submitted PR review.

Wasmtime GitHub notifications bot (Jun 30 2021 at 19:12):

cfallin created PR review comment:

I think this should be right? At least, my understanding is that the blockparams are SSA values while the variables are a higher-level abstraction; it would be more confusing to have a pool of both and then selectively lower vars to SSA values or use an SSA value directly, I think.

Wasmtime GitHub notifications bot (Jul 01 2021 at 09:58):

afonso360 updated PR #3038 from fuzz-gen to main.

Wasmtime GitHub notifications bot (Jul 01 2021 at 10:33):

afonso360 created PR review comment:

Ah, this works only because the first block is special and has the function params. I think for the other blocks we have to associate the block params to existing variables? Otherwise we run into the issue you were pointing out earlier where we may not have defined a variable depending on where we came from.

Anyway, I'll probably start working on the control flow improvements today, and should be in a more informed position to address this when I submit the next PR.

Wasmtime GitHub notifications bot (Jul 01 2021 at 10:47):

afonso360 submitted PR review.

Wasmtime GitHub notifications bot (Jul 01 2021 at 10:57):

afonso360 edited PR review comment.

Wasmtime GitHub notifications bot (Jul 01 2021 at 13:32):

abrown merged PR #3038.

Last updated: Dec 23 2024 at 13:07 UTC