Fuzzing in JavaScript, an exercise in monadic computation

May 30, 2009 by asmyczek

As I mentioned in a previous post, following is an introduction to monadic computation in JavaScript. The intent of this post is to demonstrate many advantages of monadic abstraction by implementing a concrete example from ground up. The theory behind monads I will leave to other online tutorials.

The previously described parser is a slightly too complex example for an introduction, so let’s implement something simpler, a fuzzer. To make this more interesting, let’s develop a DSL to fuzz on JavaScript objects and in particular on HTTP requests parsed to objects of the form { method : ‘POST’, uri: ‘index.html’, host:’www.xyz.com’, …}. For a quick preview of the DSL feel free to scroll down to the end of this post or run the demo.

Some basics

What is a fuzzer? We can define a fuzzer as a function that takes an input object and returns it in an altered version. To create fuzzers we can define functions like:

var ret = function(v) {
  return function (o) { return v; };
};

var prepend = function(s) {
  return function(o) { return s + o; };
};

Here the ret (for return) fuzzer replaces the input with the value v and prepend prefixes the input with s. For example the fuzzer var f = prepend(‘../’); will return ‘../index.html’ when executed as f(‘index.html’).

Additionally we need a method to execute fuzzers in sequence. For this we define the function bind:

var bind = function(a, f) {
  return function(o) { return f(a(o))(o); };
};

Bind executes argument fuzzer a and passes its result to the function f. f may process the result of a but always returns a second fuzzer, which is executed in bind to compute the final result. The key to sequencing is the function f which returns a fuzzer as result.
It turns out that ret and bind are the basic blocks of any kind of computation and a structure build on top of this functions (and satisfies these laws) is called a monad. The previously defined function prepend can be expressed in terms of bind and ret as well (see source code for details).

To make sequencing more accessible, we define two functions, seq and repeat: 

var seq = function(as, f) {
  var rec = function(as, r) {
    return (as.length > 0)?
      bind(as[0], function(n) { return rec(as.slice(1), f(r, n)); }) :
      ret(r);
  };
  return rec(as);
};

var repeat = curry(function(a, f, n) {
  return seq(map(ret(a), new Array(n)), f);
});

// some useful accumulator functions
var cons = function(r, n) { return (r || []).concat(n); };
var sum = function(r, n) { return (r || 0) + n; };
var join  = function(r, n) { return (r || "") + n; };
var or    = function(r, n) { return r || n; };

seq runs fuzzers as and applies function f on the result from previous executions and the current one to accumulate the result. Repeat executes the same fuzzer n-times. For example: seq([ret(2), ret(2), ret(2)], sum)() and repeat(ret(2), sum)(3)() will return 6.
Repeat uses the partial application function curry in its implementation. We can call curried functions with limited arguments and provide the missing once later, for example:

var overflow = repeat(ret('A'), join);

Now we can generate overflows with different length, for example overflow(5) will return ‘AAAAA’.

Handling objects

To fuzz on object we need methods to access object properties, update objects and generate multiple object variations. We can define these functions as following:

var property = curry(function(n, a) {
  return function(o) { o[n] = a(o[n]); return o; };
});

var update = function(as) {
  return seq(as, or);
};

var mutate = function(as) {
  var cs = map(function(a) { return function(o) { return a(copy(o)); }; }, as);
  return seq(cs, cons);
};

var permutate = function(as) {
  return bind(as[0], function(fs) {
    return (as.length > 1)?
      mutate(map(ret, map(permutate(as.slice(1)), fs))) :
      mutate(map(ret, fs));
    });
};

The helper function map applies function f on all values of array as and copy creates a new object with the input object as prototype. As you can immediately see, the property function is a fuzzer as well and thus can be combination with all other fuzzers using bind. Additionally it is a curryied function, so we can use it as a property selector. To access properties of our HTTP request object we define:

var method = property(“methodâ€?);
var uri = property(“uriâ€?);

For example method(ret(‘POST’))(request_object) will return the request_object with method property set to POST. To apply multiple changes to one object we can use the function update, for example var f = update([method(ret('POST')), uri(ret('home.html'))]); f(request_object) will return the object with changed properties method and uri. mutate works the same way update does, but returns one object for every fuzzer in the array. In the above example, mutate would return two objects, the first one with just changed method and the second one with just changed uri property. To generate all possible combinations between mutate results we can use permutate as we will see next. The fuzzer library is complete!

Let’s fuzz

First we define a small object stub we like to fuzz on:

var request_object = {
  method : 'GET',
  uri	      : 'index.html'
};

Using accessors defined above we can fuzz on method property as following:

var request_methods = map(ret, ['GET', 'POST', 'HEAD']);
var requests = mutate(map(method, request_methods));

The array request_methods contains ret fuzzers which replace the input with one of the listed methods. In requests we first apply all ret parsers to the accessor method to fuzz on method property of a request object. To generate one object for every request method, we pass this to the mutate fuzzer. Therefore requests(request_object) will return three objects, everyone with a different method.

We can apply the same logic to fuzz on uri property:

var overflows       = map(overflow, [1, 2, 4, 8]);
var uri_overflows   = mutate(map(uri, [id].concat(overflows)));

var updir           = update([uri(prepend('../'))]);
var updirs          = mutate(map(repeat(updir, or), [1,2,3]));

In short:

  • uri_overflows(request_object) will generate five objects. The first one is unchanged (id) and the following ones with changed uri to ‘A’, ‘AA’, etc.
  • updirs(request_object) will generate three objects with uris ‘../index.html’, ‘../../index.html’ etc.

We can combine both uri fuzzers using mutate or permutate. mutate will apply the fuzzers after each other resulting in 8 object variation. However using permutate we generate all combinations between this two fuzzer resulting in 15 different objects with uris like ‘../../AAAA’ etc.

Putting it all together:

var fuzzer = permutate([requests, uri_overflows, updirs]);

fuzzer(request_object) will return 45 different objects (see demo).

This is maybe not the most useful fuzzer yet, but as you can see, with every new fuzzing function build on top of the presented ones, the amount of combinations we can generate increases almost exponentially. To make the fuzzer library more sophisticated we can add a managed state to the computation, as described in the last section of the source code.

Happy fuzzing!

Categories: Fuzzing, JavaScript
736 Comments
Bookmark and Share