1 Fuzzer

Caleb Meredith edited this page 2018-08-06 10:00:10 -07:00

Unescape Escape

Table of Contents

• Implementation
• Next Steps

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

Prepack includes a fuzz tester which generates valid JavaScript programs in optimized functions for testing. The commands to run the fuzzer are:

• yarn fuzz: Starts generating tests in the foreground and logs progress. If it finds an error it will try and shrink it before returning the shrunken program to you with the invalid results.
• yarn fuzz-sample: See a selection of the programs generated by the fuzzer.
• yarn fuzz-overnight: Spin up a worker for each CPU and try to find failing test cases. Your computer will be basically unusable while you run this, so leave it running overnight. Failed test cases will be saved in fuzzer/overnight.sqlite so in the morning you can use sqlite3 to inspect the errors the fuzzer found.

The fuzzer generates programs with an optimized function and executes them twice:

1. In Node.js
2. In Node.js after running Prepack

Then compares the results. If the results are different then the fuzzer will attempt to shrink the program to something easier to debug and return this to you. See this gist for some samples of generated programs. Here’s an example of a function you might see:

function f3(a1, a2, a3, a4, a5, a6) {
  2;
  var x2;

  if (0) {
    return a1 ? false : a2;
  } else {
    var x1 = a3;
    x2 = x1;
  }

  var x6;

  if (x2) {
    var x3;

    if (x2) {
      x3 = x2;
    } else {
      x3 = a4;
    }

    var x4 = x3;
    x6 = x4;
  } else {
    var x5;

    if (a5) {
      x5 = x2;
    } else {
      x5 = a6;
    }

    x6 = f2(x5);
  }

  return x6;
}

Implementation

To generate programs we use leebyron/testcheck which is actually a JS compiled version of the official Clojure library clojure/test.check. testcheck is designed for generative property testing at a much smaller scale then program fuzzing. So we are abusing the library a bit to use it as a fuzzer. Our reasoning is that we wanted to write the fuzzer in JS (to have access to the Babel AST) and we didn’t want to write our own case generating framework. If we outgrow testcheck then we can keep the DSL, but rewrite the generation/shrinking logic. Although its been working fine so far.

The generator code in fuzzer/src/gen.js may look odd to you. It uses immutable.js and a state monad implemented with a JS generator so the code looks imperative. We need state since generating various program components depends on things like “what variables are declared at a given point in time,” but because we’re limited to only using a single recursive generator (based on performance lessons I learned from my first fuzzer) we can’t pass around state at the generator level and must instead maintain state at the result level. At first we tried hacking together some imperative state, but when shrinking programs testcheck replays some generators to get new programs. So what do you do when you need a stateful process that needs to be replayed? You use a monad.

Next Steps

There are a lot of JavaScript features which are not implemented in the fuzzer. We should add these features to get better coverage of Prepack.