[wasm] Syntax- and Type-aware Fuzzer

test/fuzzer/wasm-compile.cc

+// Copyright 2017 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <stddef.h>
+#include <stdint.h>
+#include <stdlib.h>
+
+#include <utility>
+
+#include "include/v8.h"
+#include "src/isolate.h"
+#include "src/objects.h"
+#include "src/ostreams.h"
+#include "src/wasm/wasm-interpreter.h"
+#include "src/wasm/wasm-module-builder.h"
+#include "src/wasm/wasm-module.h"
+#include "test/common/wasm/test-signatures.h"
+#include "test/common/wasm/wasm-module-runner.h"
+#include "test/fuzzer/fuzzer-support.h"
+
+#define WASM_CODE_FUZZER_HASH_SEED 83
+
+typedef uint8_t byte;
+
+using namespace v8::internal::wasm;
+
+namespace {
+
+class DataRange {
+  const uint8_t* data_;
+  uint32_t size_;
+
+ public:
+  DataRange(const uint8_t* data, uint32_t size) : data_(data), size_(size) {}
+
+  uint32_t size() const { return size_; }
+
+  std::pair<DataRange, DataRange> split(uint32_t index) const {
+    return std::make_pair(DataRange(data_, index),
+                          DataRange(data_ + index, size() - index));
+  }
+
+  std::pair<DataRange, DataRange> split() {
+    uint32_t index = get<uint32_t>();

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

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.

[Eric Holk, 2017/02/16 22:05:31]

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.

[ahaas, 2017/02/17 09:03:52]

sounds good

+    if (size() > 0) {
+      index = index % size();
+    } else {
+      index = 0;
+    }
+    return split(index);
+  }
+
+  template <typename T>
+  T get() {
+    if (sizeof(T) > size()) {
+      return T();
+    } else {
+      T result;
+      memcpy(&result, data_, sizeof(result));
+      data_ += sizeof(result);
+      size_ -= sizeof(result);
+      return result;
+    }
+  }
+};
+
+class WasmGenerator {
+  template <WasmOpcode Op, ValueType... Args>

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

Is it worth to have a copy of this code for every opcode?

+  std::function<void(DataRange)> op() {
+    return [this](DataRange data) {

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

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?

[Eric Holk, 2017/02/16 22:05:31]

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.

[ahaas, 2017/02/17 09:03:52]

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

+      Generate<Args...>(data);
+      fn_->Emit(Op);
+    };
+  }
+
+  template <ValueType T>
+  std::function<void(DataRange)> block() {
+    return [this](DataRange data) {
+      blocks_.push_back(T);
+      fn_->EmitWithU8(kExprBlock,
+                      static_cast<uint8_t>(WasmOpcodes::ValueTypeCodeFor(T)));
+      Generate<T>(data);
+      fn_->Emit(kExprEnd);
+      blocks_.pop_back();
+    };
+  }
+
+  template <ValueType T>
+  std::function<void(DataRange)> block_br() {
+    return [this](DataRange data) {
+      blocks_.push_back(T);
+      fn_->EmitWithU8(kExprBlock,
+                      static_cast<uint8_t>(WasmOpcodes::ValueTypeCodeFor(T)));
+
+      const uint32_t target_block = data.get<uint32_t>() % blocks_.size();
+      const ValueType break_type = blocks_[target_block];
+
+      Generate(break_type, data);
+      fn_->EmitWithVarInt(kExprBr, target_block);
+      fn_->Emit(kExprEnd);
+      blocks_.pop_back();
+    };
+  }
+
+ public:
+  WasmGenerator(v8::internal::wasm::WasmFunctionBuilder* fn) : fn_(fn) {}
+
+  void Generate(ValueType type, DataRange data);
+
+  template <ValueType T>
+  void Generate(DataRange data);
+
+  template <ValueType T1, ValueType T2, ValueType... Ts>
+  void Generate(DataRange data) {
+    const auto parts = data.split();
+    Generate<T1>(parts.first);
+    Generate<T2, Ts...>(parts.second);
+  }
+
+ private:
+  v8::internal::wasm::WasmFunctionBuilder* fn_;

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

I think the code would be easier to read if the WasmFunctionBuilder were called
builder_;

[Eric Holk, 2017/02/16 22:05:31]

Done.

+  std::vector<ValueType> blocks_;
+};
+
+template <>
+void WasmGenerator::Generate<kWasmI32>(DataRange data) {
+  if (data.size() <= sizeof(uint32_t)) {
+    uint32_t i = 0;

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

I think you could extract this const construction into a separate function.

[Eric Holk, 2017/02/16 22:05:31]

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

Done.

+    while (data.size() > 0) {
+      i <<= 8;
+      i |= data.get<uint8_t>();
+    }
+    fn_->EmitI32Const(i);
+  } else {
+    const std::function<void(DataRange)> alternates[] = {
+        op<kExprI32Eqz, kWasmI32>(), op<kExprI32Eq, kWasmI32, kWasmI32>(),

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

I think with // -- you could avoid two operations in one line.

[Eric Holk, 2017/02/16 22:05:31]

Thanks for the tip!

Done.

+        op<kExprI32Ne, kWasmI32, kWasmI32>(),
+        op<kExprI32LtS, kWasmI32, kWasmI32>(),
+        op<kExprI32LtU, kWasmI32, kWasmI32>(),
+        op<kExprI32GeS, kWasmI32, kWasmI32>(),
+        op<kExprI32GeU, kWasmI32, kWasmI32>(),
+
+        op<kExprI64Eqz, kWasmI64>(), op<kExprI64Eq, kWasmI64, kWasmI64>(),
+        op<kExprI64Ne, kWasmI64, kWasmI64>(),
+        op<kExprI64LtS, kWasmI64, kWasmI64>(),
+        op<kExprI64LtU, kWasmI64, kWasmI64>(),
+        op<kExprI64GeS, kWasmI64, kWasmI64>(),
+        op<kExprI64GeU, kWasmI64, kWasmI64>(),
+
+        op<kExprF32Eq, kWasmF32, kWasmF32>(),
+        op<kExprF32Ne, kWasmF32, kWasmF32>(),
+        op<kExprF32Lt, kWasmF32, kWasmF32>(),
+        op<kExprF32Ge, kWasmF32, kWasmF32>(),
+
+        op<kExprF64Eq, kWasmF64, kWasmF64>(),
+        op<kExprF64Ne, kWasmF64, kWasmF64>(),
+        op<kExprF64Lt, kWasmF64, kWasmF64>(),
+        op<kExprF64Ge, kWasmF64, kWasmF64>(),
+
+        op<kExprI32Add, kWasmI32, kWasmI32>(),
+        op<kExprI32Sub, kWasmI32, kWasmI32>(),
+        op<kExprI32Mul, kWasmI32, kWasmI32>(),
+
+        op<kExprI32DivS, kWasmI32, kWasmI32>(),
+        op<kExprI32DivU, kWasmI32, kWasmI32>(),
+        op<kExprI32RemS, kWasmI32, kWasmI32>(),
+        op<kExprI32RemU, kWasmI32, kWasmI32>(),
+
+        op<kExprI32And, kWasmI32, kWasmI32>(),
+        op<kExprI32Ior, kWasmI32, kWasmI32>(),
+        op<kExprI32Xor, kWasmI32, kWasmI32>(),
+        op<kExprI32Shl, kWasmI32, kWasmI32>(),
+        op<kExprI32ShrU, kWasmI32, kWasmI32>(),
+        op<kExprI32ShrS, kWasmI32, kWasmI32>(),
+        op<kExprI32Ror, kWasmI32, kWasmI32>(),
+        op<kExprI32Rol, kWasmI32, kWasmI32>(),
+
+        op<kExprI32Clz, kWasmI32>(), op<kExprI32Ctz, kWasmI32>(),
+        op<kExprI32Popcnt, kWasmI32>(),
+
+        op<kExprI32ConvertI64, kWasmI64>(), op<kExprI32SConvertF32, kWasmF32>(),
+        op<kExprI32UConvertF32, kWasmF32>(),
+        op<kExprI32SConvertF64, kWasmF64>(),
+        op<kExprI32UConvertF64, kWasmF64>(),
+        // TODO(ahaas): Uncomment this once the nondeterminism detection is
+        // working again.
+        //
+        // op<kExprI32ReinterpretF32, kWasmF32>(),
+
+        block<kWasmI32>(), block_br<kWasmI32>()};
+
+    const auto which = data.get<uint8_t>();
+
+    alternates[which % arraysize(alternates)](data);
+  }
+}
+
+template <>
+void WasmGenerator::Generate<kWasmI64>(DataRange data) {
+  if (data.size() <= sizeof(uint64_t)) {
+    // TODO (eholk): generate full 64-bit constants
+    uint64_t i = 0;
+    while (data.size() > 0) {
+      i <<= 8;
+      i |= data.get<uint8_t>();
+    }
+    const uint8_t bytes[] = {WASM_I64V(i)};
+    fn_->EmitCode(bytes, arraysize(bytes));
+  } else {
+    const std::function<void(DataRange)> alternates[] = {

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

What is the reason why you do not use the definitions in wasm-opcodes.h to
generate these alternates arrays?

[Eric Holk, 2017/02/16 22:05:31]

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.

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

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]

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

[ahaas, 2017/02/17 09:03:52]

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.

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

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.

+        op<kExprI64Add, kWasmI64, kWasmI64>(),
+        op<kExprI64Sub, kWasmI64, kWasmI64>(),
+        op<kExprI64Mul, kWasmI64, kWasmI64>(),
+
+        op<kExprI64DivS, kWasmI64, kWasmI64>(),
+        op<kExprI64DivU, kWasmI64, kWasmI64>(),
+        op<kExprI64RemS, kWasmI64, kWasmI64>(),
+        op<kExprI64RemU, kWasmI64, kWasmI64>(),
+
+        op<kExprI64And, kWasmI64, kWasmI64>(),
+        op<kExprI64Ior, kWasmI64, kWasmI64>(),
+        op<kExprI64Xor, kWasmI64, kWasmI64>(),
+        op<kExprI64Shl, kWasmI64, kWasmI64>(),
+        op<kExprI64ShrU, kWasmI64, kWasmI64>(),
+        op<kExprI64ShrS, kWasmI64, kWasmI64>(),
+        op<kExprI64Ror, kWasmI64, kWasmI64>(),
+        op<kExprI64Rol, kWasmI64, kWasmI64>(),
+
+        op<kExprI64Clz, kWasmI64>(),
+        op<kExprI64Ctz, kWasmI64>(),
+        op<kExprI64Popcnt, kWasmI64>(),
+
+        block<kWasmI64>(),
+        block_br<kWasmI64>()};
+
+    const auto which = data.get<uint8_t>();
+
+    alternates[which % arraysize(alternates)](data);
+  }
+}
+
+template <>
+void WasmGenerator::Generate<kWasmF32>(DataRange data) {
+  if (data.size() <= sizeof(uint32_t)) {
+    // TODO (eholk): generate full 64-bit constants
+    uint32_t i = 0;
+    while (data.size() > 0) {
+      i <<= 8;
+      i |= data.get<uint8_t>();
+    }
+    fn_->Emit(kExprF32Const);
+    fn_->EmitCode(reinterpret_cast<uint8_t*>(&i), sizeof(i));
+  } else {
+    const std::function<void(DataRange)> alternates[] = {
+        op<kExprF32Add, kWasmF32, kWasmF32>(),

[ahaas, 2017/02/06 14:36:20]

Why did you not add the other float instructions?

[Eric Holk, 2017/02/16 22:05:31]

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

+        op<kExprF32Sub, kWasmF32, kWasmF32>(),
+        op<kExprF32Mul, kWasmF32, kWasmF32>(),
+
+        block<kWasmF32>(), block_br<kWasmF32>()};
+
+    const auto which = data.get<uint8_t>();
+
+    alternates[which % arraysize(alternates)](data);
+  }
+}
+
+template <>
+void WasmGenerator::Generate<kWasmF64>(DataRange data) {
+  if (data.size() <= sizeof(uint64_t)) {
+    // TODO (eholk): generate full 64-bit constants
+    uint64_t i = 0;
+    while (data.size() > 0) {
+      i <<= 8;
+      i |= data.get<uint8_t>();
+    }
+    fn_->Emit(kExprF64Const);
+    fn_->EmitCode(reinterpret_cast<uint8_t*>(&i), sizeof(i));
+  } else {
+    const std::function<void(DataRange)> alternates[] = {
+        op<kExprF64Add, kWasmF64, kWasmF64>(),
+        op<kExprF64Sub, kWasmF64, kWasmF64>(),
+        op<kExprF64Mul, kWasmF64, kWasmF64>(),
+
+        block<kWasmF64>(), block_br<kWasmF64>()};
+
+    const auto which = data.get<uint8_t>();
+
+    alternates[which % arraysize(alternates)](data);
+  }
+}
+
+void WasmGenerator::Generate(ValueType type, DataRange data) {
+  switch (type) {
+    case kWasmI32:
+      return Generate<kWasmI32>(data);
+    case kWasmI64:
+      return Generate<kWasmI64>(data);
+    case kWasmF32:
+      return Generate<kWasmF32>(data);
+    case kWasmF64:
+      return Generate<kWasmF64>(data);
+    default:
+      abort();

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

I think we typically use UNREACHABLE(); in V8 and not abort();

[Eric Holk, 2017/02/16 22:05:31]

Done.

+  }
+}
+}
+
+extern "C" int LLVMFuzzerTestOneInput(const uint8_t* data, size_t size) {
+  // Save the flag so that we can change it and restore it later.
+  bool generate_test = v8::internal::FLAG_wasm_code_fuzzer_gen_test;
+  if (generate_test) {
+    v8::internal::OFStream os(stdout);
+
+    os << "// Copyright 2017 the V8 project authors. All rights reserved."

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

Does the test generation work for your fuzzer? That's amazing.

[Eric Holk, 2017/02/16 22:05:31]

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

+       << std::endl;
+    os << "// Use of this source code is governed by a BSD-style license that "
+          "can be"
+       << std::endl;
+    os << "// found in the LICENSE file." << std::endl;
+    os << std::endl;
+    os << "load(\"test/mjsunit/wasm/wasm-constants.js\");" << std::endl;
+    os << "load(\"test/mjsunit/wasm/wasm-module-builder.js\");" << std::endl;
+    os << std::endl;
+    os << "(function() {" << std::endl;
+    os << "  var builder = new WasmModuleBuilder();" << std::endl;
+    os << "  builder.addMemory(32, 32, false);" << std::endl;

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

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/

[Eric Holk, 2017/02/16 22:05:31]

Done.

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

+    os << "  builder.addFunction(\"test\", kSig_i_iii)" << std::endl;
+    os << "    .addBodyWithEnd([" << std::endl;
+  }
+  v8_fuzzer::FuzzerSupport* support = v8_fuzzer::FuzzerSupport::Get();
+  v8::Isolate* isolate = support->GetIsolate();
+  v8::internal::Isolate* i_isolate =
+      reinterpret_cast<v8::internal::Isolate*>(isolate);
+
+  // Clear any pending exceptions from a prior run.
+  if (i_isolate->has_pending_exception()) {
+    i_isolate->clear_pending_exception();
+  }
+
+  v8::Isolate::Scope isolate_scope(isolate);
+  v8::HandleScope handle_scope(isolate);
+  v8::Context::Scope context_scope(support->GetContext());
+  v8::TryCatch try_catch(isolate);
+
+  v8::internal::AccountingAllocator allocator;
+  v8::internal::Zone zone(&allocator, ZONE_NAME);
+
+  TestSignatures sigs;
+
+  WasmModuleBuilder builder(&zone);
+
+  v8::internal::wasm::WasmFunctionBuilder* f =
+      builder.AddFunction(sigs.i_iii());

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

Do you use the 3 Parameters?

[Eric Holk, 2017/02/16 22:05:31]

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

+
+  WasmGenerator gen(f);
+  gen.Generate<kWasmI32>(DataRange(data, static_cast<uint32_t>(size)));
+
+  uint8_t end_opcode = kExprEnd;
+  f->EmitCode(&end_opcode, 1);
+  f->ExportAs(v8::internal::CStrVector("main"));
+
+  ZoneBuffer buffer(&zone);
+  builder.WriteTo(buffer);
+
+  v8::internal::wasm::testing::SetupIsolateForWasmModule(i_isolate);
+
+  v8::internal::HandleScope scope(i_isolate);
+
+  ErrorThrower interpreter_thrower(i_isolate, "Interpreter");
+  std::unique_ptr<const WasmModule> module(testing::DecodeWasmModuleForTesting(
+      i_isolate, &interpreter_thrower, buffer.begin(), buffer.end(),
+      v8::internal::wasm::ModuleOrigin::kWasmOrigin, true));
+
+  // Clear the flag so that the WebAssembly code is not printed twice.
+  v8::internal::FLAG_wasm_code_fuzzer_gen_test = false;
+  if (module == nullptr) {
+    if (generate_test) {
+      v8::internal::OFStream os(stdout);
+      os << "            ])" << std::endl;
+      os << "            .exportFunc();" << std::endl;
+      os << "  assertThrows(function() { builder.instantiate(); });"
+         << std::endl;
+      os << "})();" << std::endl;
+    }
+    return 0;
+  }
+  if (generate_test) {
+    v8::internal::OFStream os(stdout);
+    os << "            ])" << std::endl;
+    os << "            .exportFunc();" << std::endl;
+    os << "  var module = builder.instantiate();" << std::endl;
+    os << "  module.exports.test(1, 2, 3);" << std::endl;
+    os << "})();" << std::endl;
+  }
+
+  ModuleWireBytes wire_bytes(buffer.begin(), buffer.end());
+  int32_t result_interpreted;
+  bool possible_nondeterminism = false;
+  {
+    WasmVal args[] = {WasmVal(1), WasmVal(2), WasmVal(3)};
+    result_interpreted = testing::InterpretWasmModule(
+        i_isolate, &interpreter_thrower, module.get(), wire_bytes, 0, args,
+        &possible_nondeterminism);
+  }
+
+  ErrorThrower compiler_thrower(i_isolate, "Compiler");
+  v8::internal::Handle<v8::internal::JSObject> instance =
+      testing::InstantiateModuleForTesting(i_isolate, &compiler_thrower,
+                                           module.get(), wire_bytes);
+  // Restore the flag.
+  v8::internal::FLAG_wasm_code_fuzzer_gen_test = generate_test;
+  if (!interpreter_thrower.error()) {
+    CHECK(!instance.is_null());
+  } else {
+    return 0;
+  }
+  int32_t result_compiled;
+  {
+    v8::internal::Handle<v8::internal::Object> arguments[] = {
+        v8::internal::handle(v8::internal::Smi::FromInt(1), i_isolate),
+        v8::internal::handle(v8::internal::Smi::FromInt(2), i_isolate),
+        v8::internal::handle(v8::internal::Smi::FromInt(3), i_isolate)};
+    result_compiled = testing::CallWasmFunctionForTesting(
+        i_isolate, instance, &compiler_thrower, "main", arraysize(arguments),
+        arguments, v8::internal::wasm::ModuleOrigin::kWasmOrigin);
+  }
+  if (result_interpreted == bit_cast<int32_t>(0xdeadbeef)) {

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

Do not check for the exception if there may be non-determinism, see
https://codereview.chromium.org/2671813004

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

Do not check for the exception if there may be non-determinism, see
https://codereview.chromium.org/2671813004

[Eric Holk, 2017/02/16 22:05:31]

Done.

+    CHECK(i_isolate->has_pending_exception());
+    i_isolate->clear_pending_exception();
+  } else {
+    // The WebAssembly spec allows the sign bit of NaN to be non-deterministic.
+    // This sign bit may cause result_interpreted to be different than
+    // result_compiled. Therefore we do not check the equality of the results
+    // if the execution may have produced a NaN at some point.
+    if (!possible_nondeterminism && (result_interpreted != result_compiled)) {
+      V8_Fatal(__FILE__, __LINE__, "WasmCodeFuzzerHash=%x",
+               v8::internal::StringHasher::HashSequentialString(
+                   data, static_cast<int>(size), WASM_CODE_FUZZER_HASH_SEED));
+    }
+  }
+  return 0;
+}