Communications of the ACM

input format, but it also guarantees blind spots, because the corpus is a finite list harvested from human-written tests. The school of dumb fuzzing proposes an answer to this shortcoming, advocating fuzzers that generate input randomly, without regard to validity, thereby covering areas the developer may have overlooked.

This is a bit of a balancing act. With no knowledge of the target program at all, the best a fuzzer could do would be to feed in a random stream of 0s and 1s. That would generally do nothing but trigger input validation code at some intervening layer before reaching the program under test. Triggering only input validation code is the hallmark of a bad fuzzer.

To put some dumb in our fuzzer without resorting to random binary, values are generated from a seed list. Since our test inputs are JavaScript objects consisting of MongoDB commands and primitive values, the seed list is composed of MongoDB commands and primitive types that we know from experience are edge cases. These seed values are kept in a file, and JavaScript objects are generated using them as the keys and values. Here’s an excerpt:

var defaultTokens = { primitives: ['Infinity', '-Infinity', 'NaN', '-NaN', 'ab','AB','000','000000'], commands: ['all', 'bitsAllClear'] // etc. }

These values are drawn from our experience with testing MongoDB, but as far as the fuzzer is concerned they are just nodes of an AST, and it composes the test input from them without regard to what would be valid. Thus, our generational method produces dumbness.

It Doesn’t Work Like This

We are trying to balance coverage with validation avoidance. To generate test input that has a chance of passing input validation, we could start with a template of a valid JavaScript object. The letters in this template represent placeholders:

{a:X, b:Y, c:Z}

We could then replace the capital letters with seed primitive values:

{a: 4294967296, b: 'ab', c: NumberDecimal(-NaN)}

and replace the lowercase letters with seed MongoDB command parameters:

{create: 4294967296,

$add: 'ab', $max: NumberDecimal(-NaN)}

This is not a valid MongoDB command, however. Even filling in a well-formatted template from a list of valid MongoDB primitives, this generated input still triggers only the validation code.

Hybrid Fuzzing

Mutational fuzzing leaves blind spots, and generational fuzzing on its own won’t test interesting logic at all. When combined, however, both techniques become much more powerful. This is how our fuzzer actually works.

As it mutates existing tests, every
once in a while, instead of pulling a re-
placement from the corpus, it gener-
ates an AST node from its list of seeds.
This generational substitution reduc-
es blind spots by producing a value
not present in the corpus, while the
mutational basis means the result-
ing command retains the structure
of valid input, making it likely to pass
validation. Only after it is deep in the
stack does the program realize that
something has gone horribly wrong.

Mission accomplished.

Here is an example of hybrid fuzzing in action, using a simplified version of a test that actually exposed a bug. The fuzzer starts with the following corpus, the first line of which becomes the AST shown in Figure 4:

db.test.insert({x: 1}); db.test.update({some:

"object"}, ...);

The ObjectExpression is converted into a placeholder node, in the same manner as mutational fuzzing.

Then the fuzzer decides that instead of replacing the placeholder node with a value from elsewhere in the corpus, it will replace it with a generated object—in this case, a newExpression with a large NumberLong as the argument, shown in Figure 5.