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.
This yields the following test:
db.test.insert({a:
new
Number-
Long("9223372036854775808")});
db.test.update({}, {$inc: {a: 13.0}});
The result is that a large 64-bit integer is inserted into MongoDB, and
then its value is updated. When the ac-
Figure 4. AST of one command in the corpus. (checking on this)
expression
statement
object
expression
member
expression
db.test
insert
x
1
arguments
Figure 5. Placeholder replaced with a generated object.
expression
statement
object
expression
member
expression
db.test
insert
x
new
expression
NumberLong
9223....5808
arguments