[Applause]
yeah that's so with that of the way you
get started so like I said usually in
the information security community the
the focus of security testing is are
things like network switches which
process external lead and provide access
to prime infrastructure so compiler is
not let's say a popular target so let me
be clear if that our threat model is not
by the user who's a developer so we
don't assume that the person using that
your father is delicious but rather we
focus on if the code generated by the
optimizer is correct right so for
example if you have a function this is U
style program essentially what it's
doing is reminding function foo which
returns X and essentially setting that X
to me so if you and it's story
applications you again in the memory the
value returns by so essentially you
expect this to store the value 2 in the
location 0 right so and this is what you
can do the right-hand side after
optimization which is a suite and store
co2 so essentially if you want to make
sure that it's correct code right and it
behaves little pilot behaves to the
experiment so for those of you who are
not familiar with the fast testing for a
nutshell is essentially like this you in
a in a loop you what you do is you
generate input and fill that
program under test and essentially you
can do it for as long as you want but
typically you won't have any games
beyond a certain threshold so at some
point you do control C or in the whole
process it's been shown to be
surprisingly effective at finding bugs
because most of the new tests capture a
subset of program behavior and here we
randomly randomly generate things that
are usually called cases somehow and
break the program however applying
traditional fuzz testing is limited
because our use cases instance
essentially testing little Python and
it's very important to generate valid
programs for the compiler which means
let's say you have the pilot program on
the left so let me program the left
which defines the contract and a
function to incent the contractor does
something right and you apply an effect
assume that the process applies a
mutation mutation is essentially any
operation which tweaks bites acts bites
or mousse pipes from the bike screen on
the left so you can think so the father
sees the input as a stream of bytes or
on the left and it's two weeks by its
and Hayek's removes so you can create a
mutation like the code shown on the
right which basically tweaks the
keyboard function and public right
because it's documented so you can
imagine with a very high likelihood
at the at the input levels is going to
be simply rejected by the pasa and we
don't want that because we know the
program to be parse and then optimized
and then test the optimizer so this
clearly won't work or it works but it's
not very efficient so basically the
learning is that nothing will compile
the required standard invalid programs
and now generating valid programs
requires some sort of structure
awareness so let me talk about more
structure awareness and how we approach
this problem so essentially we start
with a high level specification the
specification is written in the
interface description language called
protocol of protocol buffers this is a
movie it was personally developed by
Google but it's used for various
purposes also in guessing so essentially
in the form of language you can define
units of data as messages and each
message contains one or more fields from
other messages so for example it's
useful to talk of the specification of
the you programming language that we
tested in a top-down fashion at the very
top you have a program
so the message program which contains a
repeated sequence of a message for a
block which we also defined as a
sequence of a message called statement
and so on and so forth so you can you
could although it's not sure
slightly you could define a message
called its statement a for statement and
so on and so forth which contain other
fields and then may statement the union
of all these statements you could use
the keyword one off to make a union of
these statements so essentially with the
specification of the fashion until you
have all the leaf nodes typically
literals or constants and stuff like
that and yeah essentially try to cover
as many aspects of the programming
language as possible
well mind that this is fully handwritten
certs are exhaustive or complete but for
the purpose of testing the hope is that
it covers sufficient language features
for us to get a sufficient of assurance
that thing's what is expected of course
you can find this at the link below if
you are interested so the next thing is
input generation we have aspect how do
we convert respect into a valid input we
don't generate the input ourselves
fortunately there is a library called
approval of your data which is also
developed at Google which takes the
specification shown in the previous
slide and converts it into a valid input
which is an instantiation of the spec so
each input is essentially free for
example it can look like what is shown
below here so you have it defines blocks
and blocks contain some diamond which is
an F statement in this case and if
segment has a condition
which contains the binary operation
which is an equality and the first of
operon of the equalities of vertical
reference the weibull's ID zero and then
the constant x it is being compared
against is 0 this is the textual form of
protobuf message for clarity but of
course this is not doesn't really make
sense yet to feed this to this to the
compiler way because the you optimizer
does not recognize program so we need a
program that converts an instance of the
product of message into a pilot view
program and this is where the converter
program comes in so this is something
that we have to write but fortunately
this is not too complex and it's part of
lines of code so essentially converted
as a source to source translator the
input is the product of serialization
format and the output is the program so
we talked about the product off message
maybe previous lyrics how it looks like
when you convert it to use for what is
shown at the bottom so essentially it's
an if statement with available called X
underscore 0 if it's e check the next
equal to 0 of course this is a snippet
of a larger piece of a program so make
sense to deposit but this is just to
give you an idea how the conversion
looks like and what it what sticking put
any output of the conversion process but
in reality we have the complete valid
program which compiles and the stopping
to put these two pieces together what we
have is a specification that we have
read in the beginning and let me about
fair use are likely to generate input
but that input is not ready to be fed
yes because it's a total puff language
so you use a program you had a program
called for a buck converter which
converts from this language to a valid
test program that can then be fed to the
compiler so finally we have an input
that could be used to test my lovely but
then testing the compiler actually
requires encoding an expectation somehow
so imagine that you randomly test
randomly create a test program but you
don't know what it's supposed to be
doing what side effects it has so how do
you encode an expectation right so what
do you check how do you check out that
this it's doing the right thing the
approach that we use as differential
fast testing so essentially in it worths
tracking the side effects of a program
using an execution trace running the
program and then running the optimized
version of the program and comparing the
side tracks so we use the original
program as a baseline to compare against
and we compare that with the optimized
program so it's not a propagator however
before we can do that we need an
execution quiz which track side-effects
of the execution of the program right so
we need to know somehow what is
happening to check whether it is
happening correctly first optimization
and this is where the Yui interpreter
causes yeah
essentially an interpreter for you
programs that was written by Chris
so essentially what it does is it
interprets arbitrary you programs so
yeah apart from interpretation what it
additionally does is outputs the side
effect of the program as a place a trace
can be thought of as a string so for
example you have the test program under
that you feel it to the yule interpreter
it executes it step-by-step and then in
creates this execution base turn on the
red which can look like you load
something from memory from some address
X and then store it so the slow some
value and I might do need a copy so on
and so forth so we build the execution
trace of the test program using the
Yulin doctor and finally we are ready to
Hashmi like please put all these Doc's
together and yes the optimizer so we
suck returning the program feed it to
the interpreter optimize the same
program pizza again the optimized
version to the interpreter and then you
get to execution fixes with essentially
strings and then we can simply do string
equality check right so the execution
traces of what these versions are equal
everything's fine as we expect if it's
not equal it has a part most likely in
the optimizer but in practice people
also had situations where the bug is a
per se but with high likelihood it's do
so essentially like I said we found
about this process be pretty effective
in practice we found about seven bucks
dope which was in the optimization
rule that was used to essentially
optimize programs fiber in the
experiment he you love to myself yeah
it's not supposed to be used by
right now so that suppose of passing
anyway so yeah - in the EBM optimizes
pellucid production but fortunately he's
low very low severity yeah mostly
because the the bug equivalent question
was optimizing Boston so it was it was a
very specific pattern that was going
wrong and this pattern could be detected
visually because it's a compile-time
constant or yes that's essentially why
it was low the others well of course in
the experimental version so that's why
we're testing it so that's what we've
done
channel is to be going forward the main
thing is we would like to find high
severity bugs before the production
right because that's what matters the
main problem with fuzzing a compiler for
correctness is that it's usually slow
it's a slow process I mean typically in
fuzzing you select the small piece of
code that security critical and deposit
which means typically you would like
execution speeds of over 100 per second
but for example if you want to test
component resulted step2 encoder inside
solidity the problem is that compilation
is slow and this is perfectly fine for
the use case because developers can
spend an additional second or so to save
gas right
the only problem is that if you apply
for processing it it can become a
bottleneck so to find ways to basically
make it more suitable to fuzzing is
charge that we have currently working on
so in conclusion we started doing it
structure we're pausing to detect
problems so the optimizer and alert us
whenever there's a part in the code base
it has been so far is used for me
testing the optimizer and leader and
then decoding it has decent as Charles
but Ben mind that testing is not formal
it doesn't give you any formal
guarantees
yeah take that with the green sauce
right yeah that's about it yeah thank
you so how much do you know about the
coverage the agreements again with say
one day a person but one day it's not
safer with the society running every day
right answer but then it bits an office
over time so we started and then bits of
corpus and then the same corpus is used
so you can think of it as a cumulative
curve it improves over time and then
keeps increasing essentially so
essentially right now as it stands just
for the optimizer it's pretty good it's
about ninety eight ninety three percent
something of edge coverage yeah and we
keep running keep an eye on it and then
see if we can
they idea what's missing is it is it
syntactic features at the end of the
language that aren't in the kernel
buffer specification or sentence so I
believe the syntactic issues are not a
problem right now so so the thing the me
child is to keep up with the language
improvement so a new language features
get added and that has to be reflected
in the proof of spec so essentially to
keep up with it and making sure that
when there's some change that change is
covered in the closet process so yeah
yeah maybe it was missing is to check if
all broad statements inside the
optimizer steps are powered at a very
low level but at the high level it's not
saying
all they do is decide what
- our problem you are introducing
someone else oh they will
site is at least four rounds so
regarding gas plus the new interpreter
is oblivious to guess there's no notion
of gasoline it dis runs good regarding
how we decide basically there's a buck
file by the fuzzing program and we it
has minimized input we try to read on
the input and check the side effects
it's pretty simple workflow maybe
because of the interpreter so here the
execution phase which is solid beautiful
and you compare execution Croesus
reinforced and it's pretty
straightforward so it can quickly tell
you whether a bug in the optimizer or
there's some other poor of course like
we said we introduced code and there
could be a bug in hood that we
introduced but it doesn't take longer
than a few minutes
typically decide whether which bucket it
was it
[Music]
[Applause]