Hopefully you guys will see this as a nice talk for setting the stage.
The original idea was to have it as a very in-depth, very long two-panel talk. I think that
was very optimistic. So this will be hopefully a cool talk in kind of the history and the
uh, the field of program analysis. How we got where we got and where we came from.
Let's see, we're almost there. Is it not? Can we have a countdown?
New set? Alright! The stage is mine. Psych! I'm not talking about program analysis. We're
gonna look at cats all day. But in all seriousness, when I saw that it was the 25th anniversary of
DEF CON, I had this thought because just the week before I read the CFP, I was reading some
paper about program analysis that was published in the 90s. And I was thinking that, you know,
wow, these guys had like a lot of the same ideas that we're having now. And they were talking
about this in the 90s. I wonder how much other such history has kind of fallen by the wayside.
And so I started looking a little bit, digging through, and I wrote this proposal for the CFP
to kind of go through the last 25 years of program analysis. And then when I was putting together
the slides, I realized that program analysis goes way farther back. So where does, you know,
the 25 years number come from? And I thought about some more. I realized that 25 years
is actually my involvement with program analysis. 25 years ago, my grandma gifted me a book called
Professor Fortran's Encyclopedia, which had like a cat named X and a professor named Fortran
and a caterpillar named Caterpillar. And it went through their adventures in computer land
and taught kids all about computer. I was crazy about this book. I ditched classes in first grade
to hide in the stairwell and reread this book over and over. And I learned basic from it. And
then later on, moved on to C and so forth. And I realized very early on that if I, you know,
make a standard program that asks me for my name, and my name is too long, my last name, by the way,
is Shorshutashvili. So I actually triggered bugs with this last name, then the program would crash.
That turns out to be a buffer overflow and so forth. And then I started realizing that
it's incredible to look at a computer program, try to understand how it really works. I mean,
that's a whole different world in there, right? A world of ones and zeros and assembly instructions
and logic gates. And somewhere along the line, it becomes alive and it starts behaving in ways
that you don't quite understand ahead of time. And that's manual program analysis,
understanding how this works. But then you can take that and make it automated. You can create
programs that can understand programs. And it's like a whole level of craziness. That's like
creating some sort of intelligence almost. And that's what fascinates me about program analysis.
That's what's kept me going down the path I've been going for the last 25 years.
And so this talk is about, you know, the history of program analysis. And it's about, you know,
why we want to do program analysis in terms of kind of the dry things like we want to,
you know, hack programs, we want to make sure programs are safe. But try to approach this
topic from the sort of kid's perspective of discovering a whole new world of how programs
work, and how programs might understand other programs. Program analysis is useful,
but it's also kind of magical in a way. So with that said, let's move on to technical issues.
Hmm. Hold on. Boom. Success. Let's move on to program analysis.
Program analysis is a field that has basically three parts to it, right? You want to analyze
a program, but you always want to analyze a program to figure something out about it. So
for example, you might want to make sure that a certain specification of the program holds. The
program doesn't crash, the program doesn't allow random people to unlock your smart key for your
house, the program doesn't allow, you know, for your brakes to be remotely controlled, and so on.
And you have a goal that you want to achieve with that specification. So for example,
if your specification is, hey, I don't want this to crash, you could say, I want to make sure that
that specification holds always. Or you might want to say, I want to make sure that that
specification does not hold. I want to find the crash, right? So kind of, are you looking for bugs?
Are you trying to make sure things are safe? And then, of course, once you decide what you want to
do, you need to decide how you want to do it. What is the technique that you're going to use to
reason about a specification on your program? And with these three kind of categories in mind,
I'm going to run you through the history of program analysis and where along the line you
collected different items, kind of different instances of these three categories. And so
we're going to commence on a brief history of computing, starting in the 1830s with Charles
Babbage. Charles Babbage created the analytical engine. It was a mechanical computer, super far
ahead of its time. And he wrote a bunch of programs for it. By all accounts, these programs were
actually really buggy. So that's really interesting. Some of the first computer programs written
were already buggy. We didn't have that term yet. I'll talk about that later. And about a decade
later, Ada Lovelace published a series of notes and more reasoning about this analytical engine,
including the first complex program for one of these machines. So this is Ada Lovelace's
description of the execution trace of this program. And the program computed Bernoulli numbers.
And so she goes through instruction by instruction and says how variables change,
and so forth. And this is in the 1840s, right? And so that's where things started. In 1947,
about 105 years later, we got the term bug. Grace Hopper found, or people working with her,
a actual moth inside a computer causing a computer error. So 100 years roughly after the
first instance of kind of a computer in the semi-modern era, we have kind of this official
term for the word bug. And this very quickly started getting people thinking about how do we
kind of prevent actual software bugs. The moth, I guess, technically was kind of a wetware bug.
But how do we prevent bugs in our software? And one of the kind of early visionaries here was
Alan Turing, who's known for, of course, the Turing machine, but also cracking Enigma and
onwards and onwards. But he also had the first paper that I could find that talked about,
maybe we should try to make sure that the program is correct. And he published this in 1949. So two
years after the kind of invention of the term bug, people start thinking about how do we make sure
that there are no bugs in a program. And this creates the field of program verification.
So program verification says, hey, given a program and the specification, we want to make sure that
there are no bugs in this program, that this program carries out the computation needs to
carry out and so forth, and doesn't go astray. So as an example, here's a simple program that
has a crash, but that crash is not reachable, right? So if you give this program
the somehow three numbers that add up, where a plus b equals c, but then c minus b is not
equal to a, it'll crash. And you want to see if this program is safe. You can run a program
verification on it, which will identify, you know, hopefully that this condition can never
hold, and will produce a proof that tells you that the program is safe according to your
specification. So that's great. And if everything worked like that in the real world, then we might
not have bugs. And in certain cases, it does work like this in the real world. So there is formally
verified hardware, according to a specific specification, of course. So things that
the specification doesn't reason about, you know, maybe still can go wrong with that hardware,
but things that are covered by the specification don't. So there's, you know, hardware that can
provably not contain kind of timing side channel attacks, for example. And there's verified
software. I heard recently that Google, for example, is switching over to a formally verified
crypto system. And so the problems, of course, come when the software kind of gets bigger and
complexity starts getting introduced, and verification stops being able to reason about
things very effectively. So for example, here we have a different type of program, right? And
this program also doesn't crash. That A cubed plus B cubed equals C cubed, that's Fermat's last
theorem, right? That is not solvable. There's no solution. But it took humans hundreds of years
to figure this out. And the computer, you know, verification tools, unless they're special coded
for this, will also be unable to handle it. So it will kind of see this condition, it'll say, okay,
well, if this condition is true, then the program will crash. Can I prove that the condition is
always false? And if it can't prove that the condition is always false, it has no choice
but to alert that the program cannot be verified. So what happens then, right? So then
you have to go in and you have to start looking at the program manually and finding bugs. And
if anyone's used kind of commercially available static analysis tools, you're very well familiar
with the false positive problem, right? You open up a binary or a piece of software and the tool
pops up alerts all over the place. And some of those are actual bugs. But you spend a lot of time
chasing down the alerts. So when we look at, you know, software, open source software, for example,
we often see, you know, a security check done twice, the same check. If A is not null,
if A is not null. Why is that check there twice? Because for whatever reason, a program verification
tool alerted that there could be a bug there and the programmer figured out some hack to make it
shut up. So program verification, while it's a very useful field, like I said, there is verified
software and hardware out there. It's not kind of the final answer on its own. So we also at some
point need to have kind of the flip side. So program verification can say that is safe. But,
you know, after that it says, okay, I can't really reason about it. So the flip side is you have a
technique that says that is not safe. I can prove it. But I can't really prove, you know, if it is
safe. But if it is not safe, I'll give you a counterexample. And the way this works is by,
you know, finding counterexamples to whatever technique. So in this case, with a slightly
different condition, that is A squared plus B squared equals C squared, a technique might find
A, B, and C of three, four, and five as a counterexample that will reproduce a crash.
And so this is, there are many techniques that, you know, we'll mention later that can be used
to do program testing. But one of the very early ones, the first instance of program testing of
this style that I found was in the 1950s, which is about four decades before I thought that this
kind of idea was created. Programmers in the 1950s would program in punch cards. And to test
their code, it was common practice to dig punch cards out of the trash and feed them as input to
your program. This is unexpected input, just random stuff. And of course, by random stuff,
program shouldn't crash. So this is kind of an early example of this sort of
kind of institutionalized testing that we're, you know, only seeing come back recently.
And so, you know, these early developments, verification, testing, the creation of those
two ideas, and then the idea of what you might check for. So the, you know, trash decks check
for crashes. Turing reasoned about ensuring logical properties. But this is all done manually.
So this is kind of our first set of tools in our tool bag, and they're manual tools. We have to
dig them out. Okay, let's get our trash, you know, cards. This one got eaten by something and,
you know, put in the ones that won't jam your machine and try them. But none of this was
automated. And so as computers became more and more ubiquitous, the need for automation started
showing itself. So again, we come on a mention of Grace Hopper here, because she not only found the
first bug, but she also invented the compiler. So Grace Hopper in 1952 published a paper saying,
hey, what if we wrote in kind of higher level languages and it got, you know, squished down to
computer code. And this took a little while to catch on. And the reason it took a while to catch
on, one of the reasons is that the code that was generated by this compiler was very slow.
It couldn't be, you know, optimized as well as handwritten assembly could at the time.
And so this identified another need, another goal of program analysis, transformation of binaries
into something different, something faster in this case. And in the modern era, you know,
you can transform binaries, for example, or transform programs to ensure that they're safe.
Transfer programs to meet any sort of specification around on a different set of hardware.
And so now we needed to optimize code because, you know, people write slow code when they're
writing source for whatever reason. And another thing happened, people started realizing that
we have all of these architectures with all of this data flowing around in them. And if you're
not very, very, very careful, some data could be read from or written to a different location than
intended, and the memory could be corrupted. So I just played, you know, two days of a CTF full of
these errors, of course, memory corruption bugs. And this was first described in 1968. In 1968,
there was a paper saying, hey, you know, we noticed that if the kernel, they called it a
monitor at the time, blindly trusts everything that, you know, the user space sends it, bad
things can start to happen. And so this paper introduced that concept. It's also the paper that,
you know, one of the early works in memory protection and virtual memory and so forth,
which is pretty interesting that immediately they realized this was a problem. And a little while
later, there was, you know, Ken Thompson's reflecting on trusting trust, where he reasoned
that you could build in a backdoor into a compiler that could build in backdoors into sensitive code.
And so suddenly, we have two more things that we need to worry about in terms of specifications,
or even more, but, you know, including memory safety, information disclosure,
and authentication, right? So now you might want to verify that a program doesn't have a backdoor.
Or you might verify that a program will not leak your sensitive private information. That is,
that one is very relevant today with all of our phones having all of our information and
very little control over it. And so the need for automation was pretty well established
by the kind of turn of the century, for sure. But even before that, those papers were like
in the 1960s or something, late 1960s. And very quickly, oops, sorry, very quickly,
people started to meet this need. The research community started pumping out
automated approaches. And so I'm going to introduce a couple of these automated approaches.
And before I do so, I want to make you guys experts in program analysis, so that we can
reason about what's going on here. So we'll talk about a couple of prerequisites, right?
So let's say you have a program. So on the top right, there's like a little Python program
that's already a vulnerable program, by the way. And so you have this program,
and you want to analyze it. So you have to reason about a program in a slightly different way
as a computer than as a human. So for example, a program is viewed by a computer as a set of
basic blocks. A basic block is a piece of code that is executed all together before passing on
control flow somewhere else. So in our case, we'll pretend that input is part of this basic block. So
this X equals input is a single basic block, and then it might branch depending on the input,
right? So if you put in 42, it'll do one thing. If you put in something else, it'll do another.
And so this is the end of the basic block, and then the result of that if statement is two other
basic blocks, the true case and the false case. And each of these has a constraint that has to
be met, right? In order to go down one path, you have to put in 42. In order to go down another,
you have to put in not 42. And so these are called constraints. If you then look at all of the basic
blocks of a program, this is called a control flow graph because that's, you know, these are
basic blocks and control flows between them. And if you look at a path down this graph, now in this
case the graph is nice and simple, but in reality it could have loops, a path might hit the same node
multiple times, and so on. And then you look at the constraints all along this path. These are
the path predicates that uniquely identify this path. So if you collect all of these constraints
and you say that x is not 42 but x is 1337, that input will... any input that matches those
constraints will take the same path through the program. So these are kind of the prerequisites
of our program analysis techniques. So now we'll go through three of them. Actually for time reasons
we'll go through two of them and mention a third. But we'll start with symbolic execution. And
symbolic execution got a lot of hype recently, especially with stuff like the cyber grant
challenge and so on, as a way for machines to reason about program code. And you think that
this is something new, but it turns out that it's not. It's quite old actually. So 40 years ago,
a little bit more, the first symbolic execution paper that I could find was proposed.
And there were several actually, right in one year basically. So this idea
had some prerequisites that were met and then it exploded. And so the symbolic execution engines
were developed that could then symbolically execute Fortran code. Now we have symbolic
execution engines that you can download off GitHub that can execute binaries, Java,
Android, whatever you want. And this is kind of a fairly powerful way of reasoning about programs.
And let's run through an introduction of it with a slightly more complicated
example than what we learned about program analysis with.
Hold on. So here's a program that has several bugs, right? One is it,
well, it definitely has one bug and that is if you enter a username of service
and a command code of seven, it'll crash, right? You can imagine that instead of this crash,
it does some system relevant stuff. So it could be a backdoor instant memory
corruption, but basically we have a program with a bug and we would like to find this bug.
So let's see how we might approach this problem with symbolic execution, right?
So first let's look at the control flow graph of this program, starting from the beginning. Again,
the control flow graph is made up of basic blocks and the control flow transitions between them.
So we start at this input. If the input is service, it branches. If the username is service,
it branches into one side of the equation of the program where it checks for the command code
being seven. And if it is, it crashes. If not, it prints an on command and then it exits.
On the other side of the branch, it asks for a passcode. If the passcode is invalid,
it prints invalid passcode. Otherwise, it calls the authentication function,
then it prints exit and exits. So this is our control flow graph. And how would
we use symbolic execution to try to find that crash, try to find the ability to reach this crash?
So we would start executing the program in an emulator. And in this emulator, instead of ones
and zeros, we are working on X, Y, and other symbols. So, for example, username is a symbol
in this emulator. So when we pull in an input, it will produce an unconstrained variable called
username. And we don't know what username is. Username can be anything. Because, you know,
that is how we implement our emulator. And as we check for values of username, we
create what are called constraints, right? So these are the exact constraints that the basic
block checks when it pushes execution forward. And we collect two constraints in this case.
On the one side, username equals service. On the other side, it does not equal service. These are
constraints. And we continue executing both sides of this statement with symbolic execution.
But then we hit something that is very bad for symbolic execution. We hit, for example,
string processing functions. So a string processing function like A2I might check a
given byte, see if it is a number. If it is a number, it'll do one thing. If it's not, it'll
do another, right? Or if it's a certain number, it might do one. If it's not a certain number,
it'll do another. So it'll keep branching the symbolic emulator at every...
I'm sorry? Oh, awesome. It'll keep branching the symbolic emulator at every if statement,
every check on this number until we get into a situation where there are just too many checks,
right? So it'll try to check for a command code of, you know,
10 bytes with arbitrary values of 9 bytes and so on. And there's an exponential path explosion
here. And there are some approaches in the symbolic execution world to try to deal with
this sort of path explosion. But in general, these approaches boil down to the requirement
to remove paths, right? And lose this information. And so in the end, the symbolic execution engine
might only find certain paths and not others and miss the bug. Because we have to simplify
to keep things tractable. So that's symbolic execution. It might find the bug if you're lucky,
but if you're not, and it has to simplify its state space essentially as it's executing,
there are certain things that it might miss. Symbolic execution was proposed as you saw in
1975. But the interesting thing is that in Ada Lovelace's notes from 1942, we can see
that she did a symbolic trace of the execution of her program. So where she has this sort of
program execution log in her notes, she writes down the symbol, the equation for each variable
as the program progresses. And this is the first symbolic trace of a program, done in 1842 before
computers were invented. So that was a pretty interesting thing to find. And kind of a nice
point of history that we can put as the start of program analysis in this sense. 1842, not 1975 or
1949 or any of those much, much later dates. And so symbolic execution is a kind of tool in our
tool set that we can use to achieve either verification of a specification, the testing of a
specification, or to support the transformation of code. Of course, how you verify a program, for
example, using symbolic execution is a pretty complex thing with the symbolic execution style
that I described for program testing. It generates inputs to find vulnerabilities, but it can't prove
that there aren't any. But that's kind of a, we could go down that route for an entire semester
course, and not just a 45 minute introductory talk. So I'll leave that as future research for
you guys. And we'll go on to static analysis, because static analysis can show that, for example,
a program is immune to a certain class of vulnerabilities or properly implements a certain
specification. Static analysis, or at least one of the very common ways to do static analysis,
which is abstract interpretation, was proposed in 1977, shortly after symbolic execution.
And abstract interpretation looks at the control flow graph, the program as a whole, essentially.
It doesn't have to figure out how to reach a certain basic block to reason about properties
of the program at that basic block, which is the problem that symbolic execution had, and the reason
that symbolic execution could not find the bug in our example. And so static analysis with
abstract interpretation might be able to find that bug, probably will be able to find that bug if it
is a simple bug, or actually, I should say, will be able to find that bug. Because if it cannot
prove that a piece of code is safe, it will raise an alert. The problem is that, as we talked about,
there are false positives. So in our program, it might think that that function has a bug, even if
it doesn't, alert on that, and eat up time for a human to go through and verify all these results.
And so through abstract interpretation, we got a way to perform verification or specification
on a program in 1977, 40 years ago. And then we moved on to fuzzing. And so fuzzing is kind of one
of the biggest ways to find vulnerabilities in modern software. And it's actually surprisingly
simple. Proposed in 1981, initially, in its most basic form, which was, hey, let's throw random
input at a program and see if it crashes. It's evolved quite a bit since then. And so the
specific implementation of fuzzing that I'll describe here is implemented by American Fuzzy
Lab. It's a fuzzer that mutates its inputs when it detects differences in program execution.
And so let's see how it would run on our program here. We'll start with
some randomly generated test case or human-seeded test case. So a human might input a username of
ASDF and a password of 111. And that input will trigger certain basic blocks to be executed,
right? And so we executed the username input, of course. We executed the check for the
kind of service username that could lead to the crash. We did not satisfy it, so we took the else
branch, read in the passcode, and errored out on an invalid passcode and exited. So we triggered
those basic blocks. And so the fuzzer starts mutating this input, right? It might make a
capital D or something. Or it might mutate input in a way that passes another check. So it mutated
the input in a way that passes that passcode check. It actually doesn't, because there's
another bug in the program that I didn't notice before. But let's pretend that it
creates a valid size of a passcode and triggers that authentication function, right? So that
is a new basic block that it triggers. Now with fuzzing, we've triggered a block that symbolic
execution before us wasn't able to trigger just through randomly mutating inputs. But then we get
stuck. Because through randomly mutating inputs, we are unable to satisfy complex checks, right?
We need a username of service, and we have randomly mutated usernames. The chances are
that we'll create the string service are very slim, and we'll keep guessing and guessing and
guessing. Of course, in this specific case, you could seed the fuzzer with the string service,
and you could scan the program for all of its strings and automatically
make the fuzzer pass this check. But string checks aren't the only complex checks
in programs. There are hashes, there are complex input formats, dependencies between
different input bytes. And so in the general case, we cannot guarantee, of course, with a fuzzer
that we will find code that is protected by these complex checks. And so fuzzing
with this random data, of course, is a throwback to this trash deck concept. So fuzzing
was invented in 1950, not 1981. Or at least manual fuzzing. So again, we find that
program analysis techniques harken back to the middle of the century, and sometimes even
farther to the 1800s. So now we have this kind of toolbox of a bunch of specifications that we
can enforce, some goals that our analysis could try to achieve, and the technique through which
we can achieve them. And next, we should evaluate them, understand how these different
goals or how these different techniques help us achieve program analysis goals. And
as a scientist, if you start thinking up an approach, and you have a cool idea,
have a new program analysis technique, you want to evaluate it. So you want to take
programs and specifications, feed them into your technique, and see how well it does. This is my
clipart slide, by the way. So hopefully my clipart game is on point. So you run your analysis,
you get your results, and you're happy, right? Well, there are a number of problems with this.
One is that the analysis is more complex than you might think, because any program analysis
has to deal with the environment of the program it's analyzing. And environments like Windows,
macOS, Linux, mobile devices, cyber-physical devices, they have really complex environments.
Having to model this environment, even before understanding how much better your program
analysis technique is than previous techniques, is quite a big investment that people often don't
make, or make in a very fast manner. Another problem is finding a good data set to evaluate
on, right? There's not really a good data set for... or there wasn't a great data set for
vulnerability research. This problem is actually being worked on, and new data sets are being
created, as I'll talk about. But you need a good data set with ideally known vulnerabilities,
so you can reason about how many of them your bug finds, and with variable vulnerabilities
in different programs, so your technique isn't just specifically tailored for one style of
vulnerability that you happen to detect, or one specific program that you happen to be very good
at analyzing. Another problem is these specifications. Specifications in the real
world are very complex, whereas specifications that you might want to use for your analysis tool
initially in the early stages of development need to be fairly simple and ideally pre-provided. I
mean, if you're looking at analyzing something like Chrome, and your specification is that Chrome
should not leak user data to someone that should not get this user data, that's impossibly broad
and impossible to enforce. Is your bank allowed to have your various cookies or something along
these lines? So you need a very good data set, standard data set, with a very good
standard implementation, standard set of specifications, so that you can analyze
how well your technique runs compared to different work, and compare those results
to prior work, because that's a very important part of science and technical development,
understanding if you're making an improvement or not. And so we had problems as an analysis
community in meeting all of these goals, and having a good data set of applications,
with a good set of specifications, on a good environment that wasn't too complex to implement,
and that could produce results that we could reason about, that we could say,
we have ground truth data for the vulnerabilities that are actually in this data set, and we detect
x of them, or we manage to rule out vulnerabilities in code that has no vulnerabilities,
and so our program verification is correct. And so, like I mentioned, there have been
several projects to solve this problem, to create these data sets, and one of these
projects essentially was the Cyber Grand Challenge. If you guys were here last year,
you probably saw all of the Cyber Grand Challenge, you know, hoopla, where for the first time in
history, seven fully automated program analysis machines fought each other in a game of capture
the flag. So the same game that I spent the entire weekend playing and only got four hours of sleep
is the game that machines who didn't need to sleep played yesterday, last year rather. And
these machines, of course, suffered from all of the problems that I just talked about,
the environment problem, the specification problem, and so the Cyber Grand Challenge
created a custom operating system with very specific vulnerability specifications to
evaluate these systems. Now, for the actual competition, of course, the source code wasn't
available, since then they released the source code, so you can really look at the source code,
understand the vulnerability, and then reason about how well your tool finds certain
vulnerabilities across 249 binaries. So it's a 249 program, so it's a data set that has a
lot of variants, there are a lot of different types and different difficulties of vulnerabilities,
and all of this is freely available for people to analyze their tool and understand how well it does.
That's my other piece of clip art. So the Cyber Grand Challenge and the programs that
were written for this, these 249 programs making up the Cyber Grand Challenge data set,
allowed us to do what I call, to perform what I call the program analysis nursery experiments.
So I see the Cyber Grand Challenge data set as the nursery of program analysis, where you can
reason about different improvements for different techniques. So for example, Symbolic Execution on
the entire data set finds nine vulnerabilities. This Symbolic Execution has implemented in
Anger, which I'll talk about in a sec, which is an open source binary analysis program available
on GitHub. But Symbolic Execution on this entire data set finds nine vulnerabilities. That's not a
lot, right? There are vulnerabilities in every program of these 249 programs. It only finds
vulnerabilities in nine of them. Of course, we can optimize Symbolic Execution using various
tricks. So Anger supports, for example, concrete execution when there is no uncertainty in the
state, when all the data is known, or when there are constraints on all the data. And so by
utilizing all of these optimizations, we can get 26 crashes, crashing 26 binaries.
Utilizing static analysis, so combining Symbolic Execution with Veritesting, which is a technique
created by Carnegie Mellon University that utilizes parts of abstract interpretation to help
with Symbolic Execution, we can push that up to 31. So I should say here that this is our
implementation of Veritesting, and it might be suboptimal. So their Veritesting might be
considerably better. But that all pales in comparison with fuzzing. This seemingly simple
technique of throwing random data and seeing what happens finds 106 crashing binaries in the data
set. So this gives us an idea of where program analysis is, and this is a good showcase for
the simplicity of evaluating all of these different analyses on this data set and reasoning about
the results. Because now we can look at them in terms of, you know, summation numbers. But
there's also some subtleties there. They find bugs, different types of bugs in different binaries. So
we can look into that and make inferences and try to create new approaches. So for example,
we looked at the difference in the types of bugs that symbolic execution found and that fuzzing
found, and we realized that they have very different coverage. So the types of the basic
blocks that fuzzing can trigger are very different from the basic blocks that symbolic execution can
trigger. And sometimes one finds a crash, sometimes another finds a crash, sometimes neither of them
find a crash. In fact, very frequently. And so we decided to combine them in a very
straightforward but careful way. And the idea is as follows. We begin by fuzzing the binary. This is
nice and fast and achieves decent code coverage, but as we discussed, eventually gets stuck
on complex checks. And then we use symbolic execution to find the constraint that can get
through that check, but possibly suffer from other limitations of symbolic execution and not
find the actual bug. And then we synchronize that back into the fuzzer. We synchronize the
knowledge of how to bypass the complex check back into the fuzzer, and it continues to mutate that
input until it finds the bug. And we do this iteratively, back and forth between the fuzzer
and symbolic execution. So by implementing symbolic assistance for the fuzzer in this way,
we achieve on this entire dataset 118 crashes. And an interesting thing here is that we have
this 118 crashes in the dataset, but if you take the union of all of the different techniques,
all the different techniques have crashed something like this from memory, 150 to 160
binaries. So there's a lot of uniqueness between the different techniques used here.
Driller, the applicability of it varies by program, whether or not there are complex checks.
We can run through a quick run here. So this is a control flow graph of an example program,
and driller starts in the top left corner there. And it first starts by fuzzing a portion of the
program before it gets stuck in a complex check. And this is the basic block coverage on the right
in this graph here. You can see just kind of flat lines, right? So then if we run the symbolic
execution engine to help the fuzzer reach extra code paths, it allows us to find just a little
tiny bit more basic blocks in the executor, some more basic blocks in that control flow graph of
the program. And if we keep invoking the symbol execution engine to help the fuzzer get unstuck
every time that the coverage flat lines like that, we eventually drill into the program deep
enough to find the bug. And so that's how driller works. There's still a lot to do. So there's this
whole red area that however many programs, about 100 programs that we have never exploited before,
that we've never crashed before using any automated techniques, which represent missing
tools basically that humanity has yet to develop, or at least we have yet to develop.
And so if this all sounds interesting to you, I encourage you to join in. There are several ways
that you can participate in program analysis research. One is you can contribute to open
source frameworks. So we run one of these frameworks in our research lab. It's called
anger. Go to anger.io. There's a lot that we could use help with documentation, environment support,
better techniques, and so on. And the other is that I'm always looking for students. I'm starting
as a professor at Arizona State University. I just finished a PhD at UC Santa Barbara, and both of
those places are incredible places to go to if you want to do research in program analysis or in
general security. So if you're thinking about graduate school, or you are curious and want to
do an internship, reach out to me. I'll put you in touch with the right people, and you could explore
that. The presentation is available online. All my contact info is right here, and I guess we'll
questions in the hall? Awesome. Thank you, guys.