►
Description
Fuzz Driven Development by Midas Lambrichts
Sometimes you can come up with an easy method to verify correctness, but you struggle with finding actual examples for the unit tests. You know that "For all x it holds that …", but you can't come up with good possibilities for x. This is where relying on fuzzing can quickly drive forward development through providing you with some real examples of what your code doesn't yet cover, allowing you to quickly cover a lot of ground. Together we'll go through the process of using cargo fuzz in order to build a quick program that can squash JSON Patch operations (RFC 6902), touching upon some utilities/libraries from the Rust community (fuzzing tools, serde_json,…), and learning some lessons about what kind of misconceptions you might have when getting started with fuzzing.
A
A
A
Learn
as
you
go
without
having
to
fear
that
you've
just
made
a
big
whoopsie,
you
only
need
to
be
able
to
come
up
with
one
simple
thing:
some
invariant
and
the
le
the
rest
you'll
learn
as
you
go,
but
to
understand
first
driven
development.
We
first
of
course,
have
to
understand
what
fuzzing
is
so
fuzzing
according
to
the
first
book,
which
is
an
excellent
resource
for
anyone
getting
started
with
fuzzing.
A
So
basically,
what
it's
gonna
do
is
just
gonna
come
up
with
random
data
and
give
that
as
input
to
your
software,
and
then
it's
going
to
monitor
your
software
for
some
things.
Most
of
the
time
it's
going
to
just
see
if
your
software
crashes,
if
it
crashes,
it'll
report
that
back
to
you
that,
for
this
input,
something
crashed,
there
are
other
variants.
Sometimes
it
will
keep
fuzzing
indefinitely
and
just
collect
crashes.
And
then,
when
you
say
okay,
you
can
stop
running,
it
will
report
them
all
in
one.
A
Go
if
that's
not
clear
yet
we'll
see
also
a
bit
of
fuzzing
later
on,
once
we
go
to
an
example,
and
that
should
clarify
it
for
you,
okay,
so
we
have
fuzzing
now,
first
driven
development,
so
first
driven
development
is
a
six
step
process
which
the
first
one
is
determining
the
variance.
So
that
was
a
seed.
I
was
referring
to
earlier.
The
one
thing
that
you
need
to
know
this
doesn't
always
need
to
be
correct.
You
can
start
with
an
incorrect
invariant.
A
Second
step,
you
provide
a
first
target
that
expresses
that
invariant
for
you,
fuzzing
target
is
sits
between
the
fuzzer
and
your
software,
which
can
do
a
bit
of
manipulation
on
the
data
before
passing
it
along
to
your
software
and
we're
gonna
run
the
fuzzer
until
it
gives
us
a
failure
and
we're
going
to
think
about.
Why
did
this
fail?
Our
software?
Why
does
this
cause
a
crash
or
whatever,
then,
depending
on
our
reflection,
we
might
just
have
to
write
some
new
unit
tests
and
do
some
development
and
then
step
six.
A
Another
bug
in
your
program
sometimes
also
notice
that
this
doesn't
really
make
sense
if
you
reflect
on
it,
and
that
might
be
because
your
fuzzing
target
doesn't
really
express
the
invariant
that
you
want,
so
you
might
have
to
change
your
fuzzing
target,
sometimes
you'll,
even
after
the
reflection
see
that
your
invariant
actually
doesn't
make
sense
or
isn't
very
good.
So
you
have
to
change
the
invariant
this.
These
are
the
six
steps
of
first
driven
development.
A
Now,
let's
try
to
map
this
on
where
we'll
go
well,
where
in
the
wild
you'll
find
most
feathers
today
or
fizzing
footing,
targets
today
and
that's
on
parsers
or
compilers,
so
the
first
one
is
determining
the
variant
for
a
parser
most
of
the
time.
This
is
going
to
be
it
shouldn't
panic.
It
should
either
return
an
error
or
on
a
cable.
It
should
not.
Panic
also
goes
for
most
compilers.
A
A
You
don't
even
care
about
okay
error,
just
that
it
doesn't
crash,
then
we're
gonna
run
the
feature
until
it
fails,
which
in
this
case
means
that
our
parser
crashed
somewhere,
panicked
somewhere
and
we're
gonna
think
about
why
most
of
the
time.
This
is
just
some
path
you
missed
or
something
like
that.
A
But
since
we
have
a
pretty
simple
fuzzing
target
and
a
pretty
simple
invariant,
it's
very
unlikely
that
it's
gonna
be
one
of
those
two.
So
you're
gonna
write
a
unit
test
for
this
input,
which
just
gives
us
input
so
that
your
test
coverage
increase,
and
then
you
develop
such
that
the
test
passes
and
your
trade
again
in
this
case,
most
of
the
time
back
to
step
three.
A
A
Most
of
you
will
know
what
jason
is,
but
what
is
a
json
patch
so
assume
we
have
this
json
document
to
start
with
two
properties,
a
name
with
the
value
mids
and
a
ranking.
Eight
later
on,
the
user
gains
some
popularity.
His
ranking
goes
up.
He
goes
to
rank
five.
Okay,
he
gains
some
more
popularity.
A
bit
more.
His
ranking
goes
up
to
four.
A
A
again,
if
the
user,
for
example,
changes
its
name
and
by
consequences,
ranking
drops
a
lot,
there's
another
json
patch
for
that
change,
one
to
change
the
ranking
to
950
and
one
to
change
the
name.
Those
are
two
patch
operations,
and
this
is
one
json
patch.
That
array
is
the
json
patch.
The
entries
in
it
are
the
patch
operations.
A
A
So
in
this
case
we
can
express
the
same
thing
from
the
same
starting
document
to
get
to
the
same
end
document
by
just
replacing
the
ranking
with
one
and
the
name
with
meters,
and
that
has
the
same
effect
scoped
out
on
these
documents
on
the
starting
document
and
that's
the
squashing
operation
that
we're
gonna
try
to
do
so
now.
We
know
what
we're
trying
to
write.
Okay,
that's
what
our
library
is.
Gonna
do
is
gonna.
Take
this
squashing.
A
It
takes
a
lot
a
set
of
patches
and
it
tries
to
minimize
it
a
bit,
so
the
library
is
going
to
look
like
this.
We
have
a
public
function
which
takes
the
patches
and
that's
going
to
forward
basically
to
squash
operations,
which
takes
an
iterator
over
all
the
operations
and
all
of
the
patches,
and
for
now
we're
just
going
to
leave
to
do
in
there.
So
we
don't
have
any
logic
yet,
and
this
is
our
starting
point
now.
So
this
is
what
we're
gonna
use
for.
A
A
A
A
So
if
you
have
that,
then
we're
gonna
squash
the
patches
from
the
input,
that's
where
our
library
is
gonna,
do
and
then
we're
gonna
apply
the
patches
in
order
that
we've
been
given
them
that
the
filter
has
generated
for
us
to
get
our
normal
result
and
now
we're
going
to
apply
our
patch
to
the
starting
value
to
get
the
squashed
result
and
then
we're
going
to
see
if
they're
the
same.
They
should
because
it's
the
same
effect,
the
end
documents
should
be
the
same.
A
So
this
is
our
pheasant
target
in
this
case,
so
step
three
running
until
failure.
Nobody
has
ever
seen.
It
is
what
it
looked
like
when
you
start
a
fuzzer.
I
sped
it
up
with
a
factor
100,
because
this
took
a
while,
but
I'd
like
to
draw
your
attention
again
to
that,
we
still
don't
have
any
implementation.
We
still
have
to
do
in
there
and
by
showing
this
I'd
like
to
show
you
that
fuzzing
can
only
show
the
presence
of
bugs,
and
it
can't
show
the
absence.
A
So
it
can
come
up
with
counter
examples
of
where
we
fail
to
uphold
our
invariant,
but
it
can't
guarantee
us
that
we're
upholding
the
invariant
and
what
I'm
trying
to
show
here
is
so
that
duration
of
the
fusing
before
it
fails
does
not
equal
value
quality.
Sorry,
because
again,
we
still
have
that
to
do
in
there
so
step
four
reflect
well.
It
took
a
while
to
get
our
first
question,
it's
difficult
for
the
fuzzer
to
come
up
with
the
input
stroke
that
we
expect.
A
There
are
some
other
ways
around
this
structural
wear
fuzzing,
which
you
can
read
about.
In
the
first
book
risk
facebook,
you
can
seat
the
fuzzer
with
some
data,
but
that's
outside
of
the
scope
of
this
dock,
and
then
this
is
for
brevity.
Normally
this
would
come
become
obvious
after
a
few
iterations,
but
I'm
gonna
already
do
it
here.
A
A
A
A
We
have
some
problems
with
our
fuzzing
target,
but
it
could
also
be
that
our
invariant
isn't
that
great.
So,
let's
re,
let's
take
another
look
at
our
invariant,
so
what
we
had
was
the
effect
of
applying
the
squash,
but
should
be
the
same
as
applying
all
the
patches
that
were
squashed
in
their
order.
A
So,
as
a
keynote
among
you
might
have
noticed
earlier
on,
the
example
is
that
if
you
take
the
initial
document
and
the
end
document-
and
you
calculate
the
patch
between
those
that
you
have
the
minimal
div,
that
can
be
that
we
can
squash
towards
if
we
have
all
the
others,
all
the
other
ones,
the
beginning
and
the
end,
that's
the
minimal
one.
You
can't
do
a
shorter
expression
of
the
difference
between
start
and
end,
then
the
difference
between
start
and
end.
So
that's
our
goal.
That's
what
we're
trying
to
achieve.
A
So
that's
what
we're
gonna
compare
against
we're
no
longer
looking
at
the
effect,
but
we're
looking
at
the
patch
itself
so
to
pour
this
into
a
fuzzing
target
step.
Two.
We
no
longer
try
to
deserialize
into
the
input
script.
Now
we're
deserializing
into
a
vector
of
consequent
json
values
such
that
we
ourselves
can
calculate
consequent
patches
between
them.
So
again,
if,
if
we
can
do
this,
we
continue.
If
we
can't
we
return
feather,
will
mute
date
again
because
we
don't
crash
and
gives
us
a
next
input
that
might
be
deserializable.
A
Also
again,
because
we're
gonna
calculate
patches,
if
we
only
get
one
or
zero
documents,
we
can't
calculate
subsequent
patches.
So
we're
not
going
to
be
able
to
do
anything
with
that
same
story.
Just
return
such
that
the
fizzer
will
mute
it
again,
then
we're
gonna
do
that
actual
calculation
to
get
all
the
patches
between
all
the
documents
and
we're
also
gonna
calculate
the
what
I'm
calling
the
global
patch
the
one
between
the
first
one
and
the
last
one,
because
that's
the
one
that's
minimal,
that's
one
that
we're
gonna,
compare
against.
A
So
that's
a
bit
more
ball
update,
but
it's
just
comparing
the
minimal
diff
with
what
we
squash
into
so
now
we're
going
to
run
until
failure
and
then
after
a
while.
This
is
what
we're
going
to
be
greeted
with
that.
The
threats
are
named
panicked,
not
yet
implemented,
because
still
we
have
that
to
do
in
there
and
then
we're
also
shown
what
input
caused
the
failure
and,
if
we
zoom
in
on
that
a
bit,
we
can
see
that
it's
two
one,
an
array
of
two
and
one
new
line,
tab
new
line,
but
for
us
only.
A
This
is
important
array
of
two
and
one.
So
first
document
is
two.
The
second
document
is
one
and
that
the
fuzzing
target
will
calculate
a
bench
between
them
and
give
that
patch,
because
there's
only
one
well
two
documents,
so
one
patch
give
it
a
patch
to
our
library
and
then
we'll
hit
to
do
so.
Let's
reflect
a
bit.
A
A
What
I
like
to
do
is
write
an
helper
function
that
basically
does
the
same
as
a
fuzzing
target
such
that
I
can
write
these
very
neat
very
tiny
unit
tests
very
quickly
by
just
copy
pasting
that
input
from
the
fuzzer
into
here.
So
this
is
our
first
unit
test
or
logic.
Now
is
just
to
do
and
minimal
thing
that
we
can
do
to
make.
A
This
pause
is
just
return
all
of
the
patch
operations
as
a
vector,
and
that
would
then
result
in
the
unit
test
succeeding
and
we
can
iterate
again,
so
we
again
run
until
failure.
This
time
we
have
a
bit
of
a
bigger
error
message
at
the
end,
but
the
important
parts
are
the
search
and
failed
message.
So
the
left
forces
are
right
with
the
global
batch
versus
the
squashed
patch
and
at
the
bottom
again
we
have
the
input
that
failed.
A
A
So
I
see
that
if
the
pot
is
the
same,
that
I
only
need
to
care
about
the
last
one
and
we
still
have
two
operations,
but
the
first
one
has
the
same
pulse
and
it's
the
second
one
that
basically
still
has
an
effect
at
the
end.
So
when
multiple
operations
are
there
for
the
same
path,
we
only
need
to
keep
the
last
one.
A
So
we
again
pour
this
into
a
unit
test
again
same
thing.
Only
the
input
needs
to
change
this
for
this
and
another
name
of
course,
and
then
we
develop
so
our
implementation,
instead
of
just
collecting
into
the
vector
now
we're
gonna,
use
a
hash
map
from
the
path
to
the
patch
operation,
look
to
all
operations
and
insert
them
by
their
path
and
yeah.
If
you
insert
something
that
already
exists,
then
it
is
going
to
be
overwritten
in
the
hashmap.
A
So
then
to
get
back
into
our
vector
of
batch
operations,
we
just
train
the
hashmap
and
only
care
about
the
patch
operation,
the
pop
the
pulse
that
we
use
as
keys.
We
can
drop
them.
We
only
need
the
patch
operations
as
a
vector,
so
we
collect
it
again.
So
this
will
make
our
unit
test
pulse
again,
so
we
can
iterate
again.
A
We
can
run
it
until
failure
this
time.
This
is
what
we'll
end
up
with
the
failing
input
would
be
4
an
array
with
2
inside
it
and
an
empty
array.
The
global
patch
here
will
be
replace
the
root
by
an
empty
array.
Wheel
or
squash
operations
will
still
return,
replace
the
root
with
an
array
with
number
2
inside
of
it
and
then
remove
the
first
element
of
the
root.
A
So
we'll
write
a
unit
test
again
and
then
we
develop.
This
is
way
too
much
code
to
show
you,
but
the
main
idea
is
a
user
radix
tree
which
can
give
you
keys,
so
the
pods,
which
are
parents
or
prefixes
of
the
part
you're
currently
looking
at
or
all
the
keys,
which
start
with
the
prefix
that
you
give
it
so,
basically
children,
potentially
of
what
you're
using
and
then
you
have
all
sorts
of
combinations
you
can
get
into.
A
A
A
So
our
previous
assumption
still
hold.
This
is
all
operating
on
the
root
path,
but
if
you
think
a
bit
about
this
is
and
more
in
terms
of
the
patches
is
that
the
patches
don't
contain
any
information
where
you
come
from.
If
this
initial
document
this
this
empty
object
was
anything
else,
we
would
succeed
and
then
the
patch
operation
would
be
the
squash
patch
and
the
global
patch
would
be
the
same
again.
A
But
yeah
the
jason
patch
patches
don't
contain
any
information
from
where
you
started
it
only.
It
only
describes
where
you
go
to
like
you
start
from
something
and
you
replace
it
with,
and
then
that
value
is
contained
in
the
patch.
What
value
you
started
with
is
not
contained
in
the
patch
so
here,
actually
we
can
realize
that
the
patches
themselves
don't
contain
enough
information
to
always
come
up
with
a
minimal
patch,
because
we
don't
know
what
you
start
from.
A
A
So
what
we've
been
doing
again,
the
six
steps
of
first
driven
development,
you
determine
an
invariant.
You
write
a
fuzzing
target
that
expresses
an
invariant.
You
run
it
until
failure.
You
reflect
on
that
failure,
potentially
develop
and
do
some
unit
testing,
and
then
you
iterate
again.
Those
are
the
six
steps
of
first
driven
development.
A
So
why
does
this
work?
Why
this
works
is
because
what
we're
doing
on
a
broader
scope
than
this,
the
six
steps.
So
what
we're
doing
is.
Basically,
we
are
using
a
non-cognitive
process,
fuzzing
a
sort
of
fuzzer
software,
which
is
a
program
that
to
drive
and
guide
our
cognitive
development
of
software,
and
we
just
need
to
provide
a
simple
seed
and
invariant.
A
So
we
start
with
a
little
bit
of
cognitive
work,
and
now
we
let
the
fuzzer
guide
us
and
show
us
where
we're
lacking
in
our
invariant
implementation,
expression
of
our
invariant,
so
why
this
is
good
or
why
you
might
want
to
use.
It
is
because
the
cognitive
gaps
that
you
might
have-
and
you
have
if
you
have
limited
domain
knowledge,
they
get
less
chance
to
manifest
because
you're
not
driving
what
you're
gonna
implement
next
is
the
fuzzer.
That's
gonna
show
you
the
here,
there's
still
something
missing
and
you
need
to
take
care
of
it.