[wasm] Syntax- and Type-aware Fuzzer

[wasm] Syntax- and Type-aware Fuzzer

This is the beginning of a new fuzzer that generates
correct-by-construction Wasm modules. This should allow us to better
exercise the compiler and correctness aspects of fuzzing. It is based off
of ahaas' original Wasm fuzzer.

At the moment, it can generate expressions made up of most binops, and
also nested blocks with unconditional breaks. Future CLs will add
additional constructs, such as br_if, loops, memory access, etc.

The way the fuzzer works is that it starts with an array of arbitrary
data provided by libfuzzer. It uses the data to generate an expression.
Care is taken to make use of the entire string. Basically, the 
generator has a bunch of grammar-like rules for how to construct an 
expression of a given type. For example, an i32 can be made by adding
two other i32s, or by wrapping an i64. The process then continues
recursively until all the data is consumed.

We generate an expression from a slice of data as follows:
* If the slice is less than or equal to the size of the type (e.g. 4
  bytes for i32), then it will emit the entire slice as a constant.
* Otherwise, it will consume the first 4 bytes of the slice and use
  this to select which rule to apply. Each rule then consumes the
  remainder of the slice in an appropriate way. For example:
  * Unary ops use the remainder of the slice to generate the argument.
  * Binary ops consume another four bytes and mod this with the length
    of the remaining slice to split the slice into two parts. Each of
    these subslices are then used to generate one of the arguments to
    the binop.
  * Blocks are basically like a unary op, but a stack of block types is
    maintained to facilitate branches. For blocks that end in a break,
    the first four bytes of a slice are used to select the break depth
    and the stack determines what type of expression to generate.
The goal is that once this generator is complete, it will provide a one
to one mapping between binary strings and valid Wasm modules.

Review-Url: https://codereview.chromium.org/2658723006
Cr-Commit-Position: refs/heads/master@{#43289}
Committed: https://chromium.googlesource.com/v8/v8/+/3e1db847b36885f2c40362d88884b7ef65af8271

[Eric Holk, 2017-02-03 03:51:32]

Description was changed from

==========
WIP: Syntax- and Type-aware Wasm Fuzzer

BUG=
==========

to

==========
[wasm] Syntax- and Type-aware Fuzzer

This is the beginning of a new fuzzer that generates
correct-by-construction Wasm modules. This should allow us to better
exercise the compiler and correctness aspects of fuzzing. It is based off
of ahaas' original Wasm fuzzer.

At the moment, it can generate expressions made up of most binops, and
also nested blocks with unconditional breaks. Future CLs will add
additional constructs, such as br_if, loops, memory access, etc.

The way the fuzzer works is that it starts with an array of arbitrary
data provided by libfuzzer. It uses the data to generate an expression.
Care is taken to make use of the entire string. Basically, the 
generator has a bunch of grammar-like rules for how to construct an 
expression of a given type. For example, an i32 can be made by adding
two other i32s, or by wrapping an i64. The process then continues
recursively until all the data is consumed.

We generate an expression from a slice of data as follows:
* If the slice is less than or equal to the size of the type (e.g. 4
  bytes for i32), then it will emit the entire slice as a constant.
* Otherwise, it will consume the first 4 bytes of the slice and use
  this to select which rule to apply. Each rule then consumes the
  remainder of the slice in an appropriate way. For example:
  * Unary ops use the remainder of the slice to generate the argument.
  * Binary ops consume another four bytes and mod this with the length
    of the remaining slice to split the slice into two parts. Each of
    these subslices are then used to generate one of the arguments to
    the binop.
  * Blocks are basically like a unary op, but a stack of block types is
    maintained to facilitate branches. For blocks that end in a break,
    the first four bytes of a slice are used to select the break depth
    and the stack determines what type of expression to generate.
The goal is that once this generator is complete, it will provide a one
to one mapping between binary strings and valid Wasm modules.
==========

[Eric Holk, 2017-02-03 03:51:33]

eholk@chromium.org changed reviewers:
+ ahaas@chromium.org

[Eric Holk, 2017-02-03 21:46:42]

eholk@chromium.org changed reviewers:
+ titzer@chromium.org

[Eric Holk, 2017-02-03 21:46:43]

Adding Ben as a reviewer too.

[ahaas, 2017-02-06 13:46:25]

On 2017/02/03 at 21:46:43, eholk wrote:
> Adding Ben as a reviewer too.

Why do you add the two test cases?

[ahaas, 2017-02-06 14:36:21]

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
File test/fuzzer/wasm-compile.cc (right):

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:45: uint32_t index = get<uint32_t>();
I think even a uint8_t index would be sufficient here, no need to waste 3 bytes.
I think by default the maximum input size is 64 byte. You can set it higher
though in the chromium gn file.

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:69: template <WasmOpcode Op, ValueType... Args>
Is it worth to have a copy of this code for every opcode?

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:71: return [this](DataRange data) {
I'm surprised that you have all these template functions which are called
exactly once to produce a lambda for the alternates array. This design seems
wasteful to me, although I don't really know if it actually matters for the
number of instructions we have in WebAssembly. What are the reasons for this
design?

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:122: v8::internal::wasm::WasmFunctionBuilder* fn_;
I think the code would be easier to read if the WasmFunctionBuilder were called
builder_;

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:129: uint32_t i = 0;
I think you could extract this const construction into a separate function.

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:137: op<kExprI32Eqz, kWasmI32>(), op<kExprI32Eq,
kWasmI32, kWasmI32>(),
I think with // -- you could avoid two operations in one line.

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:211: const std::function<void(DataRange)>
alternates[] = {
What is the reason why you do not use the definitions in wasm-opcodes.h to
generate these alternates arrays?

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:256: op<kExprF32Add, kWasmF32, kWasmF32>(),
Why did you not add the other float instructions?

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:304: abort();
I think we typically use UNREACHABLE(); in V8 and not abort();

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:315: os << "// Copyright 2017 the V8 project
authors. All rights reserved."
Does the test generation work for your fuzzer? That's amazing.

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:327: os << "  builder.addMemory(32, 32, false);" <<
std::endl;
In the WasmModuleBuilder the initial memory size is set to 16, not 32. I made
this mistake for the wasm-code fuzzer and fixed it in
https://chromium-review.googlesource.com/c/436544/

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:354: builder.AddFunction(sigs.i_iii());
Do you use the 3 Parameters?

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:428: if (result_interpreted ==
bit_cast<int32_t>(0xdeadbeef)) {
Do not check for the exception if there may be non-determinism, see
https://codereview.chromium.org/2671813004

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:428: if (result_interpreted ==
bit_cast<int32_t>(0xdeadbeef)) {
Do not check for the exception if there may be non-determinism, see
https://codereview.chromium.org/2671813004

[Eric Holk, 2017-02-15 18:35:26]

On 2017/02/06 13:46:25, ahaas wrote:
> On 2017/02/03 at 21:46:43, eholk wrote:
> > Adding Ben as a reviewer too.
> 
> Why do you add the two test cases?

It was just to have a few of the bugs that the fuzzer found checked in. I guess
they'd go better with the fixes to these bugs instead. I can remove them if
you'd like.

[ahaas, 2017-02-16 09:46:03]

On 2017/02/15 at 18:35:26, eholk wrote:
> On 2017/02/06 13:46:25, ahaas wrote:
> > On 2017/02/03 at 21:46:43, eholk wrote:
> > > Adding Ben as a reviewer too.
> > 
> > Why do you add the two test cases?
> 
> It was just to have a few of the bugs that the fuzzer found checked in. I
guess they'd go better with the fixes to these bugs instead. I can remove them
if you'd like.

Yes, I think these test cases should be added with the fixes, not with the
fuzzer. If there are no fixes yet, could you please make a bug tracker issue?

[Eric Holk, 2017-02-16 22:05:32]

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
File test/fuzzer/wasm-compile.cc (right):

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:45: uint32_t index = get<uint32_t>();
On 2017/02/06 14:36:21, ahaas wrote:
> I think even a uint8_t index would be sufficient here, no need to waste 3
bytes.
> I think by default the maximum input size is 64 byte. You can set it higher
> though in the chromium gn file.

I have an associated Chromium CL at
https://chromium-review.googlesource.com/c/443250/. The max length there is 500,
which is what the wasm code fuzzer used.

What if we compromise on uint16_t? Wasm modules > 64k are probably not going to
be very useful from a debugging standpoint anyway.

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:71: return [this](DataRange data) {
On 2017/02/06 14:36:21, ahaas wrote:
> I'm surprised that you have all these template functions which are called
> exactly once to produce a lambda for the alternates array. This design seems
> wasteful to me, although I don't really know if it actually matters for the
> number of instructions we have in WebAssembly. What are the reasons for this
> design?

I'll admit I was probably overly clever/ambitious with templates. I was hoping
the templates would let us take advantage of C++'s type system to help ensure we
generate valid Wasm modules.

One thing I like about this approach is that in the generate functions down
below we can just make a big list of all the possible variants and then based on
the array size we can automatically pick one at random. The alternative would be
a big switch statement, which I feel like would quickly get ugly, and we'd have
to manually update things like the number of variants and such. As it is now,
adding a variant is often a one line change, whereas I think otherwise we'd need
to keep around three lines in sync.

As far as the code size goes, I suspect once the compiler is done with all of
its optimizations that this basically equivalent to a switch-based version.

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:122: v8::internal::wasm::WasmFunctionBuilder* fn_;
On 2017/02/06 14:36:21, ahaas wrote:
> I think the code would be easier to read if the WasmFunctionBuilder were
called
> builder_;

Done.

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:129: uint32_t i = 0;
On 2017/02/06 14:36:21, ahaas wrote:
> I think you could extract this const construction into a separate function.

Yeah, this is actually basically what DataRange::get does, so I just modified it
to do exactly what we want.

Done.

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:137: op<kExprI32Eqz, kWasmI32>(), op<kExprI32Eq,
kWasmI32, kWasmI32>(),
On 2017/02/06 14:36:21, ahaas wrote:
> I think with // -- you could avoid two operations in one line.

Thanks for the tip!

Done.

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:211: const std::function<void(DataRange)>
alternates[] = {
On 2017/02/06 14:36:21, ahaas wrote:
> What is the reason why you do not use the definitions in wasm-opcodes.h to
> generate these alternates arrays?

When I first wrote this I wasn't quite ready for all of the opcodes, since I was
working on the structure. I wasn't super familiar with wasm-opcodes.h either and
whether they'd be a good fit. I think now I probably could use those
definitions.

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:256: op<kExprF32Add, kWasmF32, kWasmF32>(),
On 2017/02/06 14:36:20, ahaas wrote:
> Why did you not add the other float instructions?

I just wanted to get a few in as a proof of concept and add the others later.

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:304: abort();
On 2017/02/06 14:36:21, ahaas wrote:
> I think we typically use UNREACHABLE(); in V8 and not abort();

Done.

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:315: os << "// Copyright 2017 the V8 project
authors. All rights reserved."
On 2017/02/06 14:36:21, ahaas wrote:
> Does the test generation work for your fuzzer? That's amazing.

Yup, it works! The ast-fuzz tests I included in this CL were generated by this.

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:327: os << "  builder.addMemory(32, 32, false);" <<
std::endl;
On 2017/02/06 14:36:21, ahaas wrote:
> In the WasmModuleBuilder the initial memory size is set to 16, not 32. I made
> this mistake for the wasm-code fuzzer and fixed it in
> https://chromium-review.googlesource.com/c/436544/

Done.

We should probably factor the common code between these two fuzzers into a
shared file.

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:354: builder.AddFunction(sigs.i_iii());
On 2017/02/06 14:36:21, ahaas wrote:
> Do you use the 3 Parameters?

Not yet, but it's an improvement I'd like to add.

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:428: if (result_interpreted ==
bit_cast<int32_t>(0xdeadbeef)) {
On 2017/02/06 14:36:21, ahaas wrote:
> Do not check for the exception if there may be non-determinism, see
> https://codereview.chromium.org/2671813004

Done.

[Eric Holk, 2017-02-16 23:57:28]

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
File test/fuzzer/wasm-compile.cc (right):

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:211: const std::function<void(DataRange)>
alternates[] = {
On 2017/02/16 22:05:31, Eric Holk wrote:
> On 2017/02/06 14:36:21, ahaas wrote:
> > What is the reason why you do not use the definitions in wasm-opcodes.h to
> > generate these alternates arrays?
> 
> When I first wrote this I wasn't quite ready for all of the opcodes, since I
was
> working on the structure. I wasn't super familiar with wasm-opcodes.h either
and
> whether they'd be a good fit. I think now I probably could use those
> definitions.

Actually, I just looked at using those macros again and way types are
represented, such as i_ii, etc., makes it not terribly convenient for the way
I've done things here.

[Eric Holk, 2017-02-17 00:06:33]

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
File test/fuzzer/wasm-compile.cc (right):

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:211: const std::function<void(DataRange)>
alternates[] = {
On 2017/02/16 23:57:28, Eric Holk wrote:
> On 2017/02/16 22:05:31, Eric Holk wrote:
> > On 2017/02/06 14:36:21, ahaas wrote:
> > > What is the reason why you do not use the definitions in wasm-opcodes.h to
> > > generate these alternates arrays?
> > 
> > When I first wrote this I wasn't quite ready for all of the opcodes, since I
> was
> > working on the structure. I wasn't super familiar with wasm-opcodes.h either
> and
> > whether they'd be a good fit. I think now I probably could use those
> > definitions.
> 
> Actually, I just looked at using those macros again and way types are
> represented, such as i_ii, etc., makes it not terribly convenient for the way
> I've done things here.
> 

And also, the opcodes aren't grouped by return type, which would be useful here.

[ahaas, 2017-02-17 09:03:53]

lgtm

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
File test/fuzzer/wasm-compile.cc (right):

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:45: uint32_t index = get<uint32_t>();
On 2017/02/16 at 22:05:31, Eric Holk wrote:
> On 2017/02/06 14:36:21, ahaas wrote:
> > I think even a uint8_t index would be sufficient here, no need to waste 3
bytes.
> > I think by default the maximum input size is 64 byte. You can set it higher
> > though in the chromium gn file.
> 
> I have an associated Chromium CL at
https://chromium-review.googlesource.com/c/443250/. The max length there is 500,
which is what the wasm code fuzzer used.
> 
> What if we compromise on uint16_t? Wasm modules > 64k are probably not going
to be very useful from a debugging standpoint anyway.

sounds good

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:71: return [this](DataRange data) {
On 2017/02/16 at 22:05:31, Eric Holk wrote:
> On 2017/02/06 14:36:21, ahaas wrote:
> > I'm surprised that you have all these template functions which are called
> > exactly once to produce a lambda for the alternates array. This design seems
> > wasteful to me, although I don't really know if it actually matters for the
> > number of instructions we have in WebAssembly. What are the reasons for this
> > design?
> 
> I'll admit I was probably overly clever/ambitious with templates. I was hoping
the templates would let us take advantage of C++'s type system to help ensure we
generate valid Wasm modules.
> 
> One thing I like about this approach is that in the generate functions down
below we can just make a big list of all the possible variants and then based on
the array size we can automatically pick one at random. The alternative would be
a big switch statement, which I feel like would quickly get ugly, and we'd have
to manually update things like the number of variants and such. As it is now,
adding a variant is often a one line change, whereas I think otherwise we'd need
to keep around three lines in sync.
> 
> As far as the code size goes, I suspect once the compiler is done with all of
its optimizations that this basically equivalent to a switch-based version.

I guess as long it is fast enough it is okay.

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:211: const std::function<void(DataRange)>
alternates[] = {
On 2017/02/17 at 00:06:33, Eric Holk wrote:
> On 2017/02/16 23:57:28, Eric Holk wrote:
> > On 2017/02/16 22:05:31, Eric Holk wrote:
> > > On 2017/02/06 14:36:21, ahaas wrote:
> > > > What is the reason why you do not use the definitions in wasm-opcodes.h
to
> > > > generate these alternates arrays?
> > > 
> > > When I first wrote this I wasn't quite ready for all of the opcodes, since
I
> > was
> > > working on the structure. I wasn't super familiar with wasm-opcodes.h
either
> > and
> > > whether they'd be a good fit. I think now I probably could use those
> > > definitions.
> > 
> > Actually, I just looked at using those macros again and way types are
> > represented, such as i_ii, etc., makes it not terribly convenient for the
way
> > I've done things here.
> > 
> 
> And also, the opcodes aren't grouped by return type, which would be useful
here.

Eventually we could think about refactoring wasm-opcodes.h to make it useful for
the fuzzer and for the wasm implementation. Thereby we make sure that if a new
opcode is added, then it will be covered by the fuzzer automatically.

https://codereview.chromium.org/2658723006/diff/80001/test/fuzzer/wasm-compil...
File test/fuzzer/wasm-compile.cc (right):

https://codereview.chromium.org/2658723006/diff/80001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:190: // op<kExprI32ReinterpretF32, kWasmF32>(),
Nit: I fixed this issue already.

[Eric Holk, 2017-02-17 16:41:55]

The CQ bit was checked by eholk@chromium.org

[Eric Holk, 2017-02-17 16:41:56]

The patchset sent to the CQ was uploaded after l-g-t-m from ahaas@chromium.org
Link to the patchset: https://codereview.chromium.org/2658723006/#ps100001
(title: "fixing nits")

[commit-bot: I haz the power, 2017-02-17 16:42:04]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[Eric Holk, 2017-02-17 16:42:09]

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
File test/fuzzer/wasm-compile.cc (right):

https://codereview.chromium.org/2658723006/diff/60001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:211: const std::function<void(DataRange)>
alternates[] = {
On 2017/02/17 09:03:52, ahaas wrote:
> On 2017/02/17 at 00:06:33, Eric Holk wrote:
> > On 2017/02/16 23:57:28, Eric Holk wrote:
> > > On 2017/02/16 22:05:31, Eric Holk wrote:
> > > > On 2017/02/06 14:36:21, ahaas wrote:
> > > > > What is the reason why you do not use the definitions in
wasm-opcodes.h
> to
> > > > > generate these alternates arrays?
> > > > 
> > > > When I first wrote this I wasn't quite ready for all of the opcodes,
since
> I
> > > was
> > > > working on the structure. I wasn't super familiar with wasm-opcodes.h
> either
> > > and
> > > > whether they'd be a good fit. I think now I probably could use those
> > > > definitions.
> > > 
> > > Actually, I just looked at using those macros again and way types are
> > > represented, such as i_ii, etc., makes it not terribly convenient for the
> way
> > > I've done things here.
> > > 
> > 
> > And also, the opcodes aren't grouped by return type, which would be useful
> here.
> 
> Eventually we could think about refactoring wasm-opcodes.h to make it useful
for
> the fuzzer and for the wasm implementation. Thereby we make sure that if a new
> opcode is added, then it will be covered by the fuzzer automatically.

I think this is a good idea. We should also do some general refactoring between
wasm-code.cc and wasm-compile.cc, since they share so much common code. I'm
planning to keep working on cleaning up and improving this fuzzer after it
lands.

https://codereview.chromium.org/2658723006/diff/80001/test/fuzzer/wasm-compil...
File test/fuzzer/wasm-compile.cc (right):

https://codereview.chromium.org/2658723006/diff/80001/test/fuzzer/wasm-compil...
test/fuzzer/wasm-compile.cc:190: // op<kExprI32ReinterpretF32, kWasmF32>(),
On 2017/02/17 09:03:52, ahaas wrote:
> Nit: I fixed this issue already.

Done.

[commit-bot: I haz the power, 2017-02-17 17:06:30]

CQ is committing da patch.

Bot data: {"patchset_id": 100001, "attempt_start_ts": 1487349715996900,
"parent_rev": "76c65af808b1c41a1db863162344ebc3c31b3247", "commit_rev":
"3e1db847b36885f2c40362d88884b7ef65af8271"}

[commit-bot: I haz the power, 2017-02-17 17:06:35]

Description was changed from

==========
[wasm] Syntax- and Type-aware Fuzzer

This is the beginning of a new fuzzer that generates
correct-by-construction Wasm modules. This should allow us to better
exercise the compiler and correctness aspects of fuzzing. It is based off
of ahaas' original Wasm fuzzer.

At the moment, it can generate expressions made up of most binops, and
also nested blocks with unconditional breaks. Future CLs will add
additional constructs, such as br_if, loops, memory access, etc.

The way the fuzzer works is that it starts with an array of arbitrary
data provided by libfuzzer. It uses the data to generate an expression.
Care is taken to make use of the entire string. Basically, the 
generator has a bunch of grammar-like rules for how to construct an 
expression of a given type. For example, an i32 can be made by adding
two other i32s, or by wrapping an i64. The process then continues
recursively until all the data is consumed.

We generate an expression from a slice of data as follows:
* If the slice is less than or equal to the size of the type (e.g. 4
  bytes for i32), then it will emit the entire slice as a constant.
* Otherwise, it will consume the first 4 bytes of the slice and use
  this to select which rule to apply. Each rule then consumes the
  remainder of the slice in an appropriate way. For example:
  * Unary ops use the remainder of the slice to generate the argument.
  * Binary ops consume another four bytes and mod this with the length
    of the remaining slice to split the slice into two parts. Each of
    these subslices are then used to generate one of the arguments to
    the binop.
  * Blocks are basically like a unary op, but a stack of block types is
    maintained to facilitate branches. For blocks that end in a break,
    the first four bytes of a slice are used to select the break depth
    and the stack determines what type of expression to generate.
The goal is that once this generator is complete, it will provide a one
to one mapping between binary strings and valid Wasm modules.
==========

to

==========
[wasm] Syntax- and Type-aware Fuzzer

This is the beginning of a new fuzzer that generates
correct-by-construction Wasm modules. This should allow us to better
exercise the compiler and correctness aspects of fuzzing. It is based off
of ahaas' original Wasm fuzzer.

At the moment, it can generate expressions made up of most binops, and
also nested blocks with unconditional breaks. Future CLs will add
additional constructs, such as br_if, loops, memory access, etc.

The way the fuzzer works is that it starts with an array of arbitrary
data provided by libfuzzer. It uses the data to generate an expression.
Care is taken to make use of the entire string. Basically, the 
generator has a bunch of grammar-like rules for how to construct an 
expression of a given type. For example, an i32 can be made by adding
two other i32s, or by wrapping an i64. The process then continues
recursively until all the data is consumed.

We generate an expression from a slice of data as follows:
* If the slice is less than or equal to the size of the type (e.g. 4
  bytes for i32), then it will emit the entire slice as a constant.
* Otherwise, it will consume the first 4 bytes of the slice and use
  this to select which rule to apply. Each rule then consumes the
  remainder of the slice in an appropriate way. For example:
  * Unary ops use the remainder of the slice to generate the argument.
  * Binary ops consume another four bytes and mod this with the length
    of the remaining slice to split the slice into two parts. Each of
    these subslices are then used to generate one of the arguments to
    the binop.
  * Blocks are basically like a unary op, but a stack of block types is
    maintained to facilitate branches. For blocks that end in a break,
    the first four bytes of a slice are used to select the break depth
    and the stack determines what type of expression to generate.
The goal is that once this generator is complete, it will provide a one
to one mapping between binary strings and valid Wasm modules.

Review-Url: https://codereview.chromium.org/2658723006
Cr-Commit-Position: refs/heads/master@{#43289}
Committed:
https://chromium.googlesource.com/v8/v8/+/3e1db847b36885f2c40362d88884b7ef65a...
==========

[commit-bot: I haz the power, 2017-02-17 17:06:36]

Committed patchset #6 (id:100001) as
https://chromium.googlesource.com/v8/v8/+/3e1db847b36885f2c40362d88884b7ef65a...

[Michael Achenbach, 2017-02-20 10:15:00]

gcc compilation for gcov fails since this commit:
https://build.chromium.org/p/client.v8/builders/V8%20Linux64%20-%20gcov%20cov...

Could you please take a look?

[titzer, 2017-02-20 10:29:40]

On 2017/02/20 10:15:00, Michael Achenbach wrote:
> gcc compilation for gcov fails since this commit:
>
https://build.chromium.org/p/client.v8/builders/V8%20Linux64%20-%20gcov%20cov...
> 
> Could you please take a look?

I see the bug and have a fix. It's a one liner.