Till Schneidereit (Mar 05 2020 at 17:40): Till Schneidereit (Mar 05 2020 at 17:40):@Alex Crichton @fitzgen (he/him) @Jonathan Foote this bug, which was created right after the oss-fuzz integration was set up, and seems to be some kind of problem with the setup, says that it'd be closed within a day after being fixed—does that mean it's not fixed yet? https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=20472&q=label%3AProj-wasmtime
fitzgen (he/him) (Mar 05 2020 at 17:45):I think that this is trying to build with clang coverage, which is not supported by rustc.
Looking at the build logs I see stuff like:
Step #5: du: cannot access '/workspace/out/coverage/dumps/compile.*.profraw': No such file or directory Step #5: du: cannot access '/workspace/out/coverage/dumps/instantiate.*.profraw': No such file or directory
Alex Crichton (Mar 05 2020 at 17:45):oh I forgot about that...
Alex Crichton (Mar 05 2020 at 18:01):I opened up https://github.com/google/oss-fuzz/issues/3468
Alex Crichton (Mar 05 2020 at 18:31):"fixed" :D
Till Schneidereit (Mar 05 2020 at 19:45):heh, yes, "fixed". Thank you for handling this!
Jonathan Foote (Mar 09 2020 at 18:56):Hello all. Apologies for the delay in responding here, I was OOO last week :electric_plug: For context, I asked Max (Dor1s) and a few other people about the possibility of google providing resources to work on this when I saw him IRL two weeks ago. Unfortunately it sounds like they probably won't, at least from his perspective.
Jonathan Foote (Mar 09 2020 at 18:57):IIUC we would effectively want https://github.com/rust-lang/rust/issues/34701 addressed
Jonathan Foote (Mar 09 2020 at 18:57):I will mention it on the relevant oss-fuzz GH issue
fitzgen (he/him) (Mar 09 2020 at 20:09):This would be nice to have for sure when evaluating whether a fuzz target is exercising all the corners you expect it to. AFAIK, we "just" need to do the work in rustc to hook this stuff up. @Alex Crichton would know more. Not sure how to prioritize working on this vs other wasmtime things though...
Alex Crichton (Mar 10 2020 at 14:04):Yeah this'd likely looks similar to most of our other sanitizer work which would involve building and shipping the runtime support libraries for select platforms and then having -Z flags in rustc that configures LLVM's pass manager appropriately and then also links the runtime libs, probably not the hardest thing to do but probably also not super trivial.
Alex Crichton (Mar 10 2020 at 14:06):There I think is some basic profiling support already with -Zprofile, but I would suspect that it's not trivially usable
Alex Crichton (Mar 10 2020 at 14:07):oh looks like -Zprofile may be one of the three mechanisms in llvm for coverage, and it may be the wrong one
Andrew Brown (Jun 10 2021 at 20:51):In the Wasmtime meeting today we (@Alex Crichton, @Chris Fallin, @Till Schneidereit) talked a bit about fuzzing: what I took away is that the Wasm SIMD fuzzing should be turned on once we finish the Wasm SIMD implementation but even when that happens the differential fuzz targets (i.e. vs wasmi) won't cover this feature. Is that right?
Alex Crichton (Jun 10 2021 at 20:52):I believe so, yeah
Chris Fallin (Jun 10 2021 at 20:53):Yes, that's right, we would need a Wasm interpreter that supports SIMD; wasmi doesn't as far as I can tell
Andrew Brown (Jun 10 2021 at 20:53):And I guess we were sort of all agreeing that it would be great if we could use the spec interpreter for this... but it might be tricky to run this
Andrew Brown (Jun 10 2021 at 20:53):...tricky from Rust or within our environment, etc.
Chris Fallin (Jun 10 2021 at 20:54):yeah, calling into Ocaml from Rust would be tricky, but maybe doable? I have no idea what the FFI is like on the ML side
Andrew Brown (Jun 10 2021 at 20:54):Do we need to call it as a library or can we get away with forking a process to do that?
Alex Crichton (Jun 10 2021 at 20:55):I wouldn't necessarily consider this a requirement for stabilizing simd though, I think we need to fuzz it at least a little but wasm-smith has us more than covered on that front
Chris Fallin (Jun 10 2021 at 20:55):ah, well we could fork a process as long as we are able to get the memory and global contents in return
Chris Fallin (Jun 10 2021 at 20:55):actually that's an interesting idea: build a server process in Ocaml that wraps the spec interpreter, takes Wasm module bytes as input, and returns execution results, in a protocol over a pipe or something
Alex Crichton (Jun 10 2021 at 20:55):running the spec interpreter on oss-fuzz would be weird though, I'm not sure if we have tight control over the environment the fuzzed binaries are run within, you'd have to look into oss-fuzz for more details on that
Andrew Brown (Jun 10 2021 at 20:56):I wouldn't necessarily consider this a requirement for stabilizing simd though
Yeah, I'm just thinking about what is the best possible end state
Alex Crichton (Jun 10 2021 at 20:56):currently I only know we have tight control over the build environment
Andrew Brown (Jun 10 2021 at 20:56):like, you mean they might not let us open ports, etc.?
Alex Crichton (Jun 10 2021 at 20:56):I'm sure it's at least somewhat possible though, and most of the works is probably just building the server process in ocaml lol
Andrew Brown (Jun 10 2021 at 20:56):because we can certainly build the spec interpreter binary...
Chris Fallin (Jun 10 2021 at 20:57):completely harebrained idea: somehow translate the spec interpreter, or the core (opcode-matching) parts of it, to Rust? I have no idea how regular its implementation is and how easy it would be to parse it
Alex Crichton (Jun 10 2021 at 20:57):nah I'm just not sure how they actually run the binary. I thought it was just "download the binary and run it" which gives us no control over the environment
Alex Crichton (Jun 10 2021 at 20:57):nose goes
Andrew Brown (Jun 10 2021 at 20:57):well, I see a Dockerfile in there so I assumed that is what was building the artifacts?
Chris Fallin (Jun 10 2021 at 20:57):nose goes
I am booked out to checks calendar 2024, but I can slot this in sometime after that :-)
Andrew Brown (Jun 10 2021 at 20:57):in there = https://github.com/google/oss-fuzz/tree/master/projects/wasmtime
Alex Crichton (Jun 10 2021 at 20:58):I think you'd basically just want to double-check what the running environment is in oss-fuzz, I really don't know myself, i just suspect it's probably not "vanilla"
Andrew Brown (Jun 10 2021 at 20:58):yeah
Alex Crichton (Jun 10 2021 at 20:58):yeah the dockerfile there is for building, and I don't think it's used for running but I could be wrong
Chris Fallin (Jun 10 2021 at 20:59):there must be at least some mechanism to get files in place, for fuzzers that want more complex install environments? or maybe not
Chris Fallin (Jun 10 2021 at 20:59):and there's the potential they sandbox things somehow too so one can't exec (seccomp or similar)
Alex Crichton (Jun 10 2021 at 21:01):tbh the best comparison is probably node at this point, I think they've got everything necessary implemented
Alex Crichton (Jun 10 2021 at 21:01):s/best/easiest/
Chris Fallin (Jun 10 2021 at 21:02):another thought: it might be ok (not ideal, but ok) if we have a fuzzing mode that requires some additional environment and setup that oss-fuzz can't provide, as we can still run this elsewhere (e.g., the CI machines in the background)
Andrew Brown (Jun 10 2021 at 21:37):(an aside: does anyone know how to fix -fsanitize-coverage=trace-pc-guard is no longer supported by libFuzzer. Please either migrate to a compiler that supports -fsanitize=fuzzer or use an older version of libFuzzer before I go off trying to figure out how to fix it?)
Andrew Brown (Jun 10 2021 at 21:37):Seen when attempting to run: cargo +nightly fuzz run differential
Chris Fallin (Jun 10 2021 at 21:39):I sometimes run cargo fuzz with -s none to turn off all sanitizers, to get a faster build turnaround when debugging a fuzz crash
Chris Fallin (Jun 10 2021 at 21:40):imho the sanitizers are less important when fuzzing Rust, at least when running locally, as the asserts are the most important oracle (others please correct me if that's not true!)
Andrew Brown (Jun 10 2021 at 21:40):I get: error: 'none' isn't a valid value for '--sanitizer <sanitizer>' [possible values: address, leak, memory, thread]
Chris Fallin (Jun 10 2021 at 21:40):weird, how old is your cargo-fuzz?
Andrew Brown (Jun 10 2021 at 21:41):0.5.2?
Chris Fallin (Jun 10 2021 at 21:41):Ah, I'm on 0.8.0:
cfallin@xap:~/work/regalloc.rs$ cargo fuzz run -s none regalloc2
Compiling regalloc2 v0.0.1 (/home/cfallin/work/regalloc2)
Compiling regalloc v0.0.31 (/home/cfallin/work/regalloc.rs/lib)
Compiling minira-util v0.1.0 (/home/cfallin/work/regalloc.rs)
^C Building [========================> ] 53/57: regalloc2, regalloc, minira-util
cfallin@xap:~/work/regalloc.rs$ cargo fuzz --version
cargo-fuzz 0.8.0
oh... latest is at 0.10.2...
Andrew Brown (Jun 10 2021 at 21:48):and that works great.
fitzgen (he/him) (Jun 14 2021 at 17:28):Chris Fallin said:
another thought: it might be ok (not ideal, but ok) if we have a fuzzing mode that requires some additional environment and setup that oss-fuzz can't provide, as we can still run this elsewhere (e.g., the CI machines in the background)
the downside here is that we have to build all the infrastructure necessary to dedupe crashes, monitor fuzzing processes and respawn them after they find crashes, etc and this is a bunch of work that oss-fuzz already does for us
Andrew Brown (Jun 25 2021 at 00:36):I mentioned in the meeting today that it didn't seem impossible to use OCaml's FFI to call in to the spec interpreter from Rust. Let me describe a possible plan and I'm interested to hear how feasible this all sounds (esp. from people with more Rust/FFI expertise):
Andrew Brown (Jun 25 2021 at 00:37):It would be ideal if all of that could get wrapped up into a wasm-spec-interpreter crate so that we could use it in the fuzzer...
Chris Fallin (Jun 25 2021 at 00:46):That all sounds reasonable!
Andrew Brown (Jul 06 2021 at 16:31):An update on this: I tried out the approach above and it works! Well... at least for int types :grinning:
Andrew Brown (Jul 06 2021 at 16:31):I'll try to get more types working before I share the proposed crate
Chris Fallin (Jul 06 2021 at 16:40):Great news! Looking forward to seeing this!
Chris Fallin (Jul 06 2021 at 16:42):Others will probably appreciate having "actual Wasm spec interpreter as a Rust crate" as well; the ecosystem of wasm interpreters on crates.io is kinda haphazard right now afaict
Andrew Brown (Jul 28 2021 at 20:36):Well, after talking to @Alex Crichton about this I just included the crate in the Wasmtime repository. Here is the current state of things: https://github.com/bytecodealliance/wasmtime/pull/3124
Andrew Brown (Jul 29 2021 at 17:38):@Chris Fallin , @fitzgen (he/him), @Alex Crichton: I think the main problem right now with the PR above is that the wasm-spec-interpreter crate only builds in a certain environment. To solve this, the best I can come up with is to always build the crate but detect during build.rs if the right tools are available and build the OCaml library if they are. If they are not, then set a feature flag and in lib.rs implement the interpret function by immediately panicking. So the crate should always build but will crash at runtime if the OCaml/Linux bits aren't there. Thoughts?
Chris Fallin (Jul 29 2021 at 17:40):That seems like an OK compromise, yeah. I guess we already do something similar for OpenVINO (detect if present at build time, still build without it)
fitzgen (he/him) (Jul 29 2021 at 17:40):sounds fine to me
Alex Crichton (Jul 29 2021 at 17:40):agreed sounds good
Andrew Brown (Jul 29 2021 at 18:49):Well, I forgot a crucial detail so I'm not sure this will work: I can detect if the tools are available, set a feature flag, and use this to compile a panicking interpret function but feature flags set in build.rs don't affect dependencies, IIRC. So the ocaml-sys crate still tries to build and fails. Any ideas?
Alex Crichton (Aug 09 2021 at 17:30):https://github.com/bytecodealliance/wasm-tools/pull/314 may be of interest here in generating more modules that get past instantiation in theory. I still think there's a lot of work to be done on the instruction side of things though where we're more intelligent about generating instructions that aren't super likely to just always trap around memory
Alex Crichton (Aug 11 2021 at 16:21):@Andrew Brown looks like the oss-fuzz build failed last night -- https://oss-fuzz-build-logs.storage.googleapis.com/index.html#wasmtime
Step #4: Compiling cpp_demangle v0.3.2
Step #4: Compiling crossbeam-channel v0.5.1
Step #4: Compiling quote v1.0.9
Step #4: Compiling aho-corasick v0.7.18
Step #4: Compiling jobserver v0.1.22
Step #4: Compiling getrandom v0.2.3
Step #4: error: failed to run custom build command for `wasm-spec-interpreter v0.1.0 (/src/wasmtime/crates/fuzzing/wasm-spec-interpreter)`
Step #4:
Step #4: Caused by:
Step #4: process didn't exit successfully: `/src/wasmtime/target/release/build/wasm-spec-interpreter-e74f205a2f27f8b8/build-script-build` (exit status: 101)
Step #4: --- stdout
Step #4: cargo:rerun-if-changed=ocaml/interpret.ml
Step #4: cargo:rerun-if-changed=ocaml/Makefile
Step #4: make -C spec/interpreter libopt
Step #4: make[1]: Entering directory '/src/wasmtime/crates/fuzzing/wasm-spec-interpreter/ocaml/spec/interpreter'
Step #4: ls binary/decode.ml binary/decode.mli binary/encode.ml binary/encode.mli binary/utf8.ml binary/utf8.mli exec/eval.ml exec/eval.mli exec/eval_numeric.ml exec/eval_numeric.mli exec/f32.ml exec/f32_convert.ml exec/f32_convert.mli exec/f64.ml exec/f64_convert.ml exec/f64_convert.mli exec/float.ml exec/i32.ml exec/i32_convert.ml exec/i32_convert.mli exec/i64.ml exec/i64_convert.ml exec/i64_convert.mli exec/int.ml exec/numeric_error.ml host/env.ml host/spectest.ml main/flags.ml main/main.ml runtime/func.ml runtime/func.mli runtime/global.ml runtime/global.mli runtime/instance.ml runtime/memory.ml runtime/memory.mli runtime/table.ml runtime/table.mli script/import.ml script/import.mli script/js.ml script/js.mli script/run.ml script/run.mli script/script.ml syntax/ast.ml syntax/free.ml syntax/free.mli syntax/operators.ml syntax/types.ml syntax/values.ml text/arrange.ml text/arrange.mli text/lexer.mli text/lexer.mll text/parse.ml text/parse.mli text/parser.mly text/print.ml text/print.mli util/error.ml util/error.mli util/lib.ml util/lib.mli util/sexpr.ml util/sexpr.mli util/source.ml util/source.mli valid/valid.ml valid/valid.mli \
Step #4: | sed 's:\(.*/\)\{0,1\}\(.*\)\.[^\.]*:\2:' \
Step #4: | grep -v main \
Step #4: | sort | uniq \
Step #4: >wasm.mlpack
Step #4: echo >_tags "true: bin_annot"
Step #4: echo >>_tags "true: debug"
Step #4: echo >>_tags "<{util,syntax,binary,text,valid,runtime,exec,script,host,main}/*.cmx>: for-pack(Wasm)"
Step #4: ocamlbuild -lexflags -ml -cflags '-w +a-4-27-42-44-45 -warn-error +a-3' -I util -I syntax -I binary -I text -I valid -I runtime -I exec -I script -I host -I main -libs bigarray -quiet wasm.cmx
Step #4: + /usr/bin/ocamldep -modules syntax/ast.ml > syntax/ast.ml.depends
Step #4: File "syntax/ast.ml", line 156, characters 14-15:
Step #4: Error: Syntax error
Step #4: Command exited with code 2.
Step #4: Makefile:91: recipe for target '_build/wasm.cmx' failed
Step #4: rm wasm.mlpack _tags
Step #4: make[1]: Leaving directory '/src/wasmtime/crates/fuzzing/wasm-spec-interpreter/ocaml/spec/interpreter'
Step #4: Makefile:28: recipe for target 'spec/interpreter/_build/wasm.cmxa' failed
Step #4:
Step #4: --- stderr
Step #4: Cloning into 'ocaml/spec'...
Step #4: make[1]: *** [_build/wasm.cmx] Error 10
Step #4: make: *** [spec/interpreter/_build/wasm.cmxa] Error 2
Step #4: thread 'main' panicked at 'Failed to build the OCaml library using 'make'.', crates/fuzzing/wasm-spec-interpreter/build.rs:57:5
Step #4: note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
Step #4: warning: build failed, waiting for other jobs to finish...
Step #4: error: build failed
Step #4: Error: failed to build fuzz script: "cargo" "build" "--manifest-path" "/src/wasmtime/fuzz/Cargo.toml" "--target" "x86_64-unknown-linux-gnu" "--release" "--features" "peepmatic-fuzzing experimental_x64" "--bins"
Step #4: ********************************************************************************
Step #4: Failed to build.
Step #4: To reproduce, run:
Step #4: python infra/helper.py build_image wasmtime
Step #4: python infra/helper.py build_fuzzers --sanitizer address --engine libfuzzer --architecture x86_64 wasmtime
Step #4: ********************************************************************************
Finished Step #4
ERROR
ERROR: build step 4 "gcr.io/oss-fuzz/wasmtime" failed: step exited with non-zero status: 1
is that an issue perhaps where ocaml is too old?
Alex Crichton (Aug 11 2021 at 16:22):Step #4: File "syntax/ast.ml", line 156, characters 14-15:
Step #4: Error: Syntax error
oh wow it looks super old, like 4.02 may be pulled in?
Andrew Brown (Aug 11 2021 at 16:23):yeah, when I ran the oss fuzz image in docker I saw that 4.02 was pulled in
Andrew Brown (Aug 11 2021 at 16:23):yup
Alex Crichton (Aug 11 2021 at 16:23):Step #1: Setting up ocaml-findlib (1.5.5-2build1) ...
Step #1: Setting up ocaml-compiler-libs (4.02.3-5ubuntu2) ...
Step #1: Setting up ocaml-interp (4.02.3-5ubuntu2) ...
Step #1: Setting up ocaml-nox (4.02.3-5ubuntu2) ...
and I thought, "hm, this might be a problem..." :grinning:
Andrew Brown (Aug 11 2021 at 16:23):well, I wonder if there is a way to use opam to upgrade ocaml or something
Andrew Brown (Aug 11 2021 at 16:24):the issue is that they're using a really old Ubuntu as the base for the oss-fuzz image
Andrew Brown (Aug 11 2021 at 16:24):16.x
Andrew Brown (Aug 11 2021 at 16:24):is there a newer oss fuzz image?
Andrew Brown (Aug 11 2021 at 16:57):Looks like there is no newer oss fuzz image, but I think the following sequence will update the tools to 4.12:
sh <(curl -sL https://raw.githubusercontent.com/ocaml/opam/master/shell/install.sh)
opam init --disable-sandboxing
opam install ocamlbuild
eval $(opam env --switch=default)
Inside the oss fuzz image that is enough to compile the spec interpreter.
Andrew Brown (Aug 11 2021 at 17:01):Unfortunately that has multiple "read from stdin" scripts
Alex Crichton (Aug 11 2021 at 17:15):eh that's fine imo
Andrew Brown (Aug 11 2021 at 17:18)::+1: I would need to figure out how to pass in the right sequence of <enter> y <enter> ...--do you have a preference on how to do that?
Alex Crichton (Aug 11 2021 at 17:25):uh... unsure lol
Alex Crichton (Aug 11 2021 at 17:25):when in doubt sometimes yes | the_script works
Alex Crichton (Aug 11 2021 at 17:25):but if that doesn't work I'd root around for some sort of "please assume yes" cli switch
Andrew Brown (Aug 12 2021 at 15:43):@Alex Crichton, I see that https://github.com/google/oss-fuzz/pull/6205 got merged; how do we see if the build now passes? Do we have to wait for an e-mail telling us it crashed or is there some other way to inspect what is going on?
Alex Crichton (Aug 12 2021 at 15:44):I got an email about another build failure, but I think it's because the changes weren't included
Alex Crichton (Aug 12 2021 at 15:44):I go to oss-fuzz and hit on build logs
Alex Crichton (Aug 12 2021 at 15:44):and it should have logs for wasmtime
Andrew Brown (Aug 12 2021 at 15:55):I don't see that:
image.png
Andrew Brown (Aug 12 2021 at 15:56):or you meant build status?
Andrew Brown (Aug 12 2021 at 15:57):Ok, yeah, if I navigate around in there I can see the logs for the latest build and it is still complaining about a syntax error
Alex Crichton (Aug 19 2021 at 22:23):ok
Alex Crichton (Aug 19 2021 at 22:28):er, sent early.
I did a bit today looking into the spec interpreter timeouts, and my conclusion is that the whole thing is and probably won't ever be written for performance. I fear that our path to differential fuzzing with the spec interpreter is going to be severly limited given the nature of the spec interpreter.
I was curious, so I played around with Deno's rusty_v8 crate to see how bad it would be to set up differential fuzzing against v8 instead of the spec interpreter. I came up with this and it seems to be working pretty well. When I enabled simd it pretty quickly found https://github.com/bytecodealliance/wasmtime/issues/3216 after I waded through the preexisting fuzz bugs. With the bindings I wrote so far we should have comparisions on instantiation results, comparison on values, and comparisons on memory, which I think is above-and-beyond what we do for both wasmi and the spec interpreter at the moment.
I'm curious how others feel about this. Should we switch from the spec interpreter to v8? Should we try to push on the spec interpreter? I think v8 has the benefit that it's (a) maintained by Deno with rusty_v8, so we get that for free and (b) it's a fuzzed engine we're unlikely to find bugs in (performance or otherwise). Personally I feel that we'll get 99% of the benefit of differential fuzzing by just fuzzing against something other than ourselves. While I think it's nice to fuzz against the spec interpreter I don't think it brings the lion's share of the benefit.
Chris Fallin (Aug 19 2021 at 22:32):Interesting -- thank you for digging into this, first of all!
I think there is definitely a lot of value in fuzzing against "peers" -- especially V8 I expect to be very, very closely checked w.r.t. the spec. I'll note that we already had fuzzing against wasmi as well, so if we're going to mainly focus on this sort of fuzzing, it's worth evaluating whether we want to keep the latter. (Probably not, since it doesn't do SIMD, for starters.)
I am curious if there are any really easy-to-pick bits of performance in the spec interpreter, though. While (i) we aren't in the business of maintaining it, and (ii) it will certainly want to optimize for clear, unambiguous implementation over any sort of optimization, it seems to me that the folks who do maintain it would be interested in fixing obvious quadratic behavior, and also, fuzzing against "The Spec" is a gold standard and a nice thing to be able to say we do, if we can
Chris Fallin (Aug 19 2021 at 22:34):I did look a wee bit at what the nested-blocks example was doing and it looked like it had a funky multistage eval step function that prepended Plain and did some stack munging on every level -- it felt like it might be home to some inefficient n^2 list-mapping but I didn't dig deep enough to really say. Is that the part you were looking at?
Alex Crichton (Aug 19 2021 at 22:36):yeah that was the same conclusion I reached on the spec interpreter, adding Plain to new lists in a way that was probably pretty inefficient in terms of list management
Alex Crichton (Aug 19 2021 at 22:36):Personally I don't want to open a bug on the spec repo, I fear it will get lost to the mists of time or otherwise no one will be able to think of a better way that's "clean enough" for the spec interpreter to use
Alex Crichton (Aug 19 2021 at 22:37):I do agree though that we don't really need to do differential-execution against multiple implementations, just one should suffice. If the spec interpreter gets further I think we should remove wasmi, and if v8 gets further we should also remove wasmi
Chris Fallin (Aug 19 2021 at 22:38):fair concern, I too am vaguely scared of crossing a "PL purist" viewpoint that dismisses this if we try to file an issue without a suggested solution; it might be worth playing a bit more with it (by which I mean, I feel like I might do this, in a bit of free time later) though to see if we can offer a constructive suggestion at the same time
Alex Crichton (Aug 19 2021 at 22:40):I did find it quite easy to reproduce with the interpreter, the input wasm I have in the issue can be changed to just have a start function and the instantiation clearly takes multiple seconds, and it gets worse by adding more blocks.
Chris Fallin (Aug 19 2021 at 22:40):jumping ahead a few steps -- in the situation where we get both the spec interpreter to work, and also have your V8 differential fuzzing harness polished and merged -- the question would be: does it make sense to have both? I would argue yes; it's interesting to see if there are disagreements between the spec and the "real world", at least
Chris Fallin (Aug 19 2021 at 22:41):cool, I will put a bit of time into this later then
Alex Crichton (Aug 19 2021 at 22:41):nah if the spec interpreter works I don't think v8 is worth it
Alex Crichton (Aug 19 2021 at 22:41):it's a pretty chonky thing to maintain, even if rusty_v8 does the worst parts for us
Chris Fallin (Aug 19 2021 at 22:41):eh, that's fair, if the complexity/cost is too high
Alex Crichton (Aug 19 2021 at 22:42):like I won't disagree it's strictly better to have more fuzzing, but for bang-for-our-buck I'm not sure how much we'd get
Chris Fallin (Aug 19 2021 at 22:43):I'm actually sort of curious how oss-fuzz budgets CPU time if we add more fuzz targets; do we get a fixed quota per target or per project? in any case if we don't need it badly enough then it's not really good citizenship to burn the cycles shrug
Alex Crichton (Aug 19 2021 at 22:43):heh for that I have no idea...
Alex Crichton (Aug 19 2021 at 22:44):FWIW my take on the spec interpreter is that I think the slowdown is this line b/c all the other lists/maps in the Block case are constant-time, but I could be wrong and it could be related to Label handling later. Unless the ocaml interpreter does crazy optimizations though List32.length and such functions were also O(n) which was about the time I lost hope for making that fast
Chris Fallin (Aug 19 2021 at 22:45):yup I was staring at that exact bit too
Chris Fallin (Aug 19 2021 at 23:36):OK, so here's my understanding of the quadratic behavior: the evaluator step function is designed to step the "configuration" (stack of values, and a list of possibly nested terms that represent remaining instructions) exactly one step, no matter how deep the label stack is. The way that a step works when there are many nested labels on the stack is that we recurse down to the innermost label's instruction list, step its configuration once, then walk back out, rebuilding the nest of Labelterms up to the root of the function's configuration.
So we start with a config like:
Block (Block (Block (Block (Block ... (code)))))and this steps to
Label l1 (Plain Block (Block ...))
then
Label l1(Label l2 (Plain Block ...))
and so on.
However each of the steps must go through 1..n recursive step calls, so we have a total of O(n^2) Ocaml calls and executions of this bit of code.
Chris Fallin (Aug 19 2021 at 23:37):This is made worse by the handling of the call stack -- it's just a part of the "configuration" as well, so we'll have Label (Label (Label ... (Frame (Label (Label (Label ... )))))) with 1000 frames in the 1000-deep-recursion-in-nested-blocks timeout example
Chris Fallin (Aug 19 2021 at 23:38):the fundamental bit that's expensive is the way that the step walks all the way back out the tree of terms and rebuilds it for each inner step; if the inner step did a step to completion then it would be efficient; but I suspect that would break an "execute for exactly one unit of time so as not to run forever" sort of fuel-limiting mechanism
Chris Fallin (Aug 19 2021 at 23:39):fixing this might not be so bad if we don't care about that; but I'd want to spend a bit more time understanding it first
Chris Fallin (Aug 19 2021 at 23:40):(fwiw, perf on the interpreter binary showed ~15% of time in just that one line lined above; and ~50% of time in GC-related code, because of the reallocation on each rebuild of the config)
Chris Fallin (Aug 19 2021 at 23:41):(I'll summarize this on the github issue for the timeout)
Chris Fallin (Aug 20 2021 at 00:55):... and I went and did the thing: https://github.com/cfallin/spec/commit/817f8e84f2fa289723e724553e74d6ce13898ec8
Andrew Brown (Aug 20 2021 at 16:23):Just catching up on this thread: wow! nice analysis and good fix. What are you thinking between merging upstream vs merging into https://github.com/bytecodealliance/wasm-spec-mirror?
Chris Fallin (Aug 20 2021 at 16:34):So I'm cleaning it up a bit and I'll go ahead and create a PR on spec and see what happens -- at worst it will spawn discussion and help to clarify "very simple theoretically correct interpreter" vs. "actually usable interpreter without quadratic behavior" as a position taken by the folks who maintain it :-)
Chris Fallin (Aug 20 2021 at 16:39):https://github.com/WebAssembly/spec/pull/1354
Till Schneidereit (Aug 20 2021 at 16:48):Indeed, great work on figuring this out and fixing it!
My take is that it's fine for the spec interpreter to be written for readability and maintainability over speed—but not for it to execute code in a way that has a different algorithmic complexity class from what production implementations would be expected to have. ISTM that otherwise it just says next to nothing about implementability of proposals, which seems highly unfortunate. Not sure if that'll be the common view, of course
Chris Fallin (Aug 20 2021 at 16:50):Hmm, it seems I don't have push access to wasm-spec-mirror, and the GitHub UI is not letting me create a PR on it when I also have an open one on WebAssembly/spec (unless I'm missing a nonobvious button somewhere)
Chris Fallin (Aug 20 2021 at 16:51):@Till Schneidereit or @Andrew Brown could you grant me permissions and I'll just push a branch for now?
Chris Fallin (Aug 20 2021 at 16:51):... ah, nevermind, I had the wrong base branch selected
Till Schneidereit (Aug 20 2021 at 16:52):I just added wasmtime-core and cranelift-core as repo maintainers
Chris Fallin (Aug 20 2021 at 16:54):there we go, PR onto fuzzing branch: https://github.com/bytecodealliance/wasm-spec-mirror/pull/1
Andrew Brown (Aug 20 2021 at 17:09):Ok, merged... let me create a PR to make sure we pull that branch when fuzzing: https://github.com/bytecodealliance/wasmtime/pull/3221
Chris Fallin (Aug 20 2021 at 17:10):Oh, I just did that too, sorry for racing!
Andrew Brown (Aug 20 2021 at 17:10):heh, I should have checked :grinning:
Andrew Brown (Aug 20 2021 at 17:10):lol, well take your pick
Andrew Brown (Aug 20 2021 at 17:11):(I was going to ask you if you were going to do it and then though, "oh, I can just push that real quick")
Andrew Brown (Aug 20 2021 at 17:11):let's use yours since it creates a constant up top
Chris Fallin (Aug 20 2021 at 17:11):sure, either way :-)
Chris Fallin (Aug 26 2021 at 15:41):@Andrew Brown fyi, it's looking like it probably will not be very feasible to remove the quadratic behavior from the spec interpreter: https://github.com/WebAssembly/spec/pull/1354 (basically we got an "interpreter should be direct translation of small-step semantics" answer)
Chris Fallin (Aug 26 2021 at 15:42):I had an alternate thought though: we could still potentially use it for individual instruction semantics (for especially SIMD this seems valuable). Would it make sense to tweak wasm-smith to generate very simple programs (e.g. no control flow) and use the infra for that?
Andrew Brown (Aug 26 2021 at 15:42):hm, yeah
Andrew Brown (Aug 26 2021 at 15:42):not a bad idea
Chris Fallin (Aug 26 2021 at 15:42):that's sort of a separate use-case than fuzzing against a fast interpreter, sort of a breadth vs. depth thing (by running larger programs we get less coverage of e.g. different bit patterns in inputs)
Andrew Brown (Aug 26 2021 at 15:43):an extension on that would be to configure wasm-smith to avoid generating cases that cause the quadratic slowdown
Andrew Brown (Aug 26 2021 at 15:43):what a pain this turned out to be :grinning:
Chris Fallin (Aug 26 2021 at 15:44):"just fuzz against the spec" they said, "how hard could it be" they said...
Chris Fallin (Aug 26 2021 at 15:44):I think no cnotrol flow (including no calls) is enough to ensure no quadratic behavior
Chris Fallin (Aug 26 2021 at 15:45):that's probably pretty easy to add to the configuration trait; any interest on your part in trying this? (I can throw it on my long-term todo list otherwise but my todo list is also growing quadratically)
Andrew Brown (Aug 26 2021 at 15:46):well, I was thinking about taking a look at the v128 stuff before I go on sabbatical here in a few weeks, I could look at it when I do that
Chris Fallin (Aug 26 2021 at 15:47):awesome!
Chris Fallin (Aug 26 2021 at 18:04):To close the loop on this -- I created https://github.com/bytecodealliance/wasmtime/issues/3251 to track it
Last updated: Nov 22 2024 at 16:03 UTC