00:00:00.000-->00:00:05.000 >>Hopefully you guys, uh, will see this as, uh, as a nice um talk, for setting the stage. Uh, 00:00:08.750-->00:00:15.583 the original idea was to have it as a very indepth, very long too panel talk. I think that, that, 00:00:15.583-->00:00:20.583 uh, that was very, uh, optimistic. Uhm, so this will be hopefully a cool talk in kind of 00:00:23.625-->00:00:29.583 the history and the, uh, the, the field of programming analysis how we got where we got 00:00:29.583-->00:00:36.375 and where we came from. Uhm, let’s see, we're almost there. Is it nine? >>Yes, sir. >>Do we 00:00:36.375-->00:00:43.125 have a countdown? [laughter] It is set? Alright! The stage is mine! Psych, I'm not talking 00:00:43.125-->00:00:49.042 about programming analysis. We're gonna look at cats, all day! Uhm, but in all 00:00:49.042-->00:00:54.042 seriousness, uh, when I saw that it was the 25th anniversary of Def Con, uhm, I had this thought 00:00:59.000-->00:01:05.000 because it, just the week before I read the, the CFD, I was reading some paper about 00:01:05.000-->00:01:11.125 programming analysis. Uh, that was published in the 90s and I was think that, you know, wow! 00:01:11.125-->00:01:17.542 These guys had like a lot of the same ideas that we're having now and they were talking about this 00:01:17.542-->00:01:23.958 in the 90s. I wonder how much other such history has kind of fallen by the wayside. Uh, and, 00:01:23.958-->00:01:27.458 uh, so I started looking a little bit. Digging through. And I wrote this, uh, proposal for 00:01:27.458-->00:01:32.458 this CFD, uhm, to kind of go through the last 25 years of programming analysis and then 00:01:35.958-->00:01:40.125 when I was putting together the slides I realized that programming analysis goes way 00:01:40.125-->00:01:45.125 farther back. So, uh, where does, you know the 25 years, uh, number come from? Uhm, and I 00:01:48.875-->00:01:54.458 thought about it some more and realized that 25 years is actually my involvement with 00:01:54.458-->00:01:59.958 this programming analysis. 25 years ago my grandma gifted me a book called 'Professor Fortran's 00:01:59.958-->00:02:05.625 Encyclopedia' which had like a cat named 'X' and, uh, a professor named Fortran, and a 00:02:05.625-->00:02:11.417 caterpillar named 'Caterpillar'. Uhm, and it, it went through their adventures in computer 00:02:11.417-->00:02:16.417 land and, uh, taught kids all about computers - I was, I was crazy about this book. I ditched 00:02:16.417-->00:02:21.542 classes in first grade to hide in the stairwell and reread this book over and over. And I 00:02:21.542-->00:02:26.542 learned basic from it, and then later on, uh, moved on to, to C and so forth and I realized very 00:02:31.542-->00:02:35.667 early on that if I, you know, make a standard program that asked me for my name and my name 00:02:35.667-->00:02:40.500 is too long, my last name by the way, Shoshitaishvili, so I actually triggered bugs with 00:02:40.500-->00:02:47.375 this last name. Uhm, then the program would crash and so then, you know, then that turns out to 00:02:47.375-->00:02:53.792 be a buffer and so forth. And then I started realizing that it's incredible to look at a 00:02:53.792-->00:02:57.833 computer program try to understand how it really works. I mean that's a whole different 00:02:57.833-->00:03:04.000 world in there, right? A world of ones and zeros...and uh, assembly instructions and logic 00:03:04.000-->00:03:09.708 gates and somewhere along the line it becomes alive. And it becomes behaving, it starts 00:03:09.708-->00:03:16.417 behaving in ways that you don't quite understand ahead of time. Uhm, and that's manual program 00:03:16.417-->00:03:23.125 analysis - understanding how this works but then you can take that and make it automated. You 00:03:23.125-->00:03:28.125 can create programs that can understand programs. And it's like a whole level of, uh 00:03:30.667-->00:03:36.292 craziness. That's like creating some sort of intelligence almost and, and that's what fascinates 00:03:36.292-->00:03:40.250 me about program analysis. That's what's kept me, uh,going down the path I've been going 00:03:40.250-->00:03:45.250 for the last 25 years. And so, uh, this talk is about, you know the history of programming 00:03:48.000-->00:03:52.500 analysis and it's about, you know, why we wanna do programming analysis in terms 00:03:52.500-->00:03:57.625 of, kinda, the dry things. Like, we wanna, you know, hack programs. We wanna make sure 00:03:57.625-->00:04:02.625 programs are safe. But, uhm, try to approach this topic from the, sort of, kids perspective... Of 00:04:07.917-->00:04:12.917 discovering a whole new world of how programs work. And how programs might understand other 00:04:12.917-->00:04:17.917 programs. Uh, program analysis is useful but it's also kind of magical, in a way. So, with that 00:04:22.542-->00:04:27.542 said - let's move on to technical issues. Hhm, hold on, boom! Success - let's move on to 00:04:33.083-->00:04:38.083 programming analysis! Uhm, program analysis is a, uh, field that has basically three parts 00:04:43.500-->00:04:48.333 to it, right? You wanna analyse a program but you always want to analyse a program to figure 00:04:48.333-->00:04:53.667 something out about it. So, for example, you might want to make sure that a certain 00:04:53.667-->00:04:59.500 specification... Of the program holds. The program doesn't crash; the program doesn't allow 00:04:59.500-->00:05:05.042 random people to unlock your, uh, smart key your house. Uh, the program doesn't allow, you 00:05:05.042-->00:05:10.042 know, for your breaks to be remotely controlled and so on. Uhm, and, uh, you have a, a goal 00:05:13.042-->00:05:16.833 that you want to achieve with that specification. So, for example, if your specification 00:05:16.833-->00:05:21.833 is a, I, uh, don't want this to crash, you could say I want to make sure that, that, uh, 00:05:23.917-->00:05:29.250 specification holds always. Or you want to say, you might want to say I want to make sure that 00:05:29.250-->00:05:34.500 specification does not fall, I want a crash, right? So, kind of - are you looking for bugs; are 00:05:34.500-->00:05:38.625 you trying to make sure things are safe? And, uh, then of course once you decide what you 00:05:38.625-->00:05:42.542 want to do you need to decide how you want to do it. What is the technique that you're going 00:05:42.542-->00:05:47.542 to use to reason about a specification on your program. Uhm, and with these three, kind 00:05:53.333-->00:05:58.583 of, categories in mind, I'm gonna run you through the history of program analysis and, 00:05:58.583-->00:06:03.583 uh, where along the line we collected different, uh, items, kind of different instances, uh, 00:06:05.708-->00:06:10.708 of these three categories. Uhm, and so we're gonna commence of a brief history of computing 00:06:13.000-->00:06:18.000 starting in the 1830s with Charles Babbage. Uh, Charles Babbage created the analytical 00:06:20.125-->00:06:25.875 engine, it was a mechanical computer - super far ahead of its time. Uhm, and he wrote a 00:06:25.875-->00:06:31.042 bunch of programs for it, uh, by all accounts these programs were actually really buggy. So, 00:06:31.042-->00:06:34.917 that's really interesting, so, uhm, the first computer program's written, were already 00:06:34.917-->00:06:40.625 buggy. We didn't have that term yet, I'll talk about that later. Uhm, and about a decade later 00:06:40.625-->00:06:45.625 Ada Lovelace, uh, published a series of notes, uhm, and uh, more reasoning about this 00:06:48.458-->00:06:54.250 analytical engine - including the first program, the first complex program for one of these 00:06:54.250-->00:07:00.708 machines. So this is Aida Lovelace's, uh, description of the trace of, uh, the, the 00:07:00.708-->00:07:07.125 executions traits of this program. Right? The program computed bernoulli numbers and 00:07:07.125-->00:07:13.833 so she goes through instruction by instruction and says how, uh, variables change and so forth. 00:07:13.833-->00:07:18.833 And this was in the 1840s, right? Uhm, and so that's where, uh, things started, in, uh, 1947 00:07:23.833-->00:07:28.833 about a hundred and five years later, uh, we got the term bug. Grace Hopper found a, or people 00:07:31.458-->00:07:36.458 working with her found a, uh, actual moth inside a computer causing a computer error. So, a 00:07:38.792-->00:07:45.500 hundred years roughly after the first instance of, kind of, a computer in the semi-modern era 00:07:45.500-->00:07:50.500 we have, kind of, this official term for the word bug. [background noise] Uhm, and this 00:07:53.500-->00:07:59.083 very quickly, uhm, started getting people thinking about how do we, kind of prevent 00:07:59.083-->00:08:04.333 actual software bug. The moth I guess technically was kind of a wetware bug. Uhm, how do we 00:08:04.333-->00:08:09.333 prevent bug in our software? And one of the kind of early, uh, visionaries here was, uhm, Alan 00:08:12.083-->00:08:18.542 Turing, uhm, who's known... Of course for the Turing machine; but also cracking enigma and, 00:08:18.542-->00:08:23.542 and, and onwards and onwards. Uhm, but he also had the first paper that I could find that 00:08:26.125-->00:08:31.125 talked about - 'Hey, maybe we should try to make sure the program is correct', right? Uhm, 00:08:34.375-->00:08:40.625 and he published this in 1949 - so two years after the, kind of invention of the term bug. 00:08:40.625-->00:08:43.083 People start thinking about how do we, uh, make sure that their are no bugs in the, in a 00:08:43.083-->00:08:45.083 program. And this, uh, creates the field of program verification - so, program 00:08:45.083-->00:08:47.083 verification says like 'Hey, given a program and it's specifications we wanna make 00:08:47.083-->00:08:49.083 sure that there are no bugs in this program. That this program, uh, carries out the computation 00:08:49.083-->00:08:52.917 it needs to carry out and so forth and, uhm, and doesn't go astray'. Uhm, so, as an example, 00:08:52.917-->00:08:57.917 here's a, a simple program that, uh, has a crash but that crash is not reachable, right? So, if 00:09:19.583-->00:09:24.583 you give this program, uh, the, uh, somehow three numbers that add up - a plus b equals c, but 00:09:29.750-->00:09:35.625 then c minus b i not equal to a, it'll crash. And you wanna see if this program is safe. You can 00:09:35.625-->00:09:40.625 run a program verification, uh, on it which will identify, you know, hopefully that, uh, this, 00:09:43.833-->00:09:49.875 uhm, condition can never hold and will produce a proof that will tell you that the program 00:09:49.875-->00:09:55.333 is safe according to your specification. So that's great and if everything worked like 00:09:55.333-->00:10:00.333 that in the real world, uh... Then we might not have bugs. And, and in, in, in certain 00:10:03.042-->00:10:06.333 cases it does work like this, uh, in the real world. So, there is formally verified hardware, 00:10:06.333-->00:10:09.292 according to a specific specification of course, so it things that the specification 00:10:09.292-->00:10:14.292 does not reason about, you know, maybe still can go wrong with that hardware but, uh, thinks 00:10:14.292-->00:10:19.542 that, uh, are, are, uh, covered by the specification don't. So, there's you know, hardware that 00:10:19.542-->00:10:27.500 can provably not contain, uh, timing side channel attacks for example. Uhm, and there's 00:10:27.500-->00:10:32.792 verified software, uhm, I heard recently that Google for example is switching over to a formally 00:10:32.792-->00:10:42.042 verified crypto, uh, system. Uhm, and so the problems of course come when, when the 00:10:42.042-->00:10:46.708 software kind of becomes bigger and complexity starts getting introduced and, uh, verification 00:10:46.708-->00:10:52.750 stops being able to reason about things very effectively. So, for example, here, uhm, we have a 00:10:52.750-->00:10:56.667 different type of program, right? And,. uh, this program also doesn't crash. That, uh, a 00:10:56.667-->00:11:02.875 cubed plus b cubed equals c cubed - that's from Arzela's theorem, right? That is not 00:11:02.875-->00:11:09.667 solvable, there's no solution. Uhm, but it took humans hundreds of years, uh, to figure this out 00:11:09.667-->00:11:16.167 and the, uh, computer verification tools, unless there's a special coder for this 00:11:16.167-->00:11:22.833 will, uh, also be unable to handle it. So, it will kind of see this, uhm, condition, it'll 00:11:22.833-->00:11:31.667 say 'Okay, well, if, uh, if this condition is true then the program will crash. Can I prove 00:11:31.667-->00:11:34.542 that the condition is always false?' And if it can't prove that the condition is always 00:11:34.542-->00:11:43.333 false it has no choice but to, uh, alert that the program can not be verified. So, uhm, that 00:11:43.333-->00:11:51.292 happens to that, right? So then you have to go in and you have to start looking at, uh, the 00:11:51.292-->00:11:55.833 program manually and, and finding bugs and if anyone's used kind of commercially 00:11:55.833-->00:12:01.875 available, uh, static analysis tools, uhm, you're very well familiar with the false positive 00:12:01.875-->00:12:07.083 problem, right? You open up a, uh, binary or a, a piece of software and the tool pops up 00:12:07.083-->00:12:14.333 alerts all over the place, and uhm, some of those are actual bugs but you spend a lot of time 00:12:14.333-->00:12:21.667 chasing down the alerts. Uh, so when we've looked at, you know software, open sourced software 00:12:21.667-->00:12:29.458 for example, uhm, we often see, you know, security check done twice. You know, the same check, 00:12:29.458-->00:12:35.708 you know, if a is not null, if a is not null. Why is that check there twice? Because for 00:12:35.708-->00:12:36.458 whatever reason, a, uh, program verification tool alerted that there could be a bug there and 00:12:36.458-->00:12:51.208 the programmer figured out some hack to make it shut up. [laughter] So, program 00:12:51.208-->00:12:57.792 verification, while it's a very useful field, like I said there is verified software and 00:12:57.792-->00:13:03.208 hardware out there, uhm, it's not kind of the, the, final answer on it's own. And we also 00:13:03.208-->00:13:08.542 at some point need to have kind of the flipside - so program verification can say 'That is 00:13:08.542-->00:13:14.042 safe but', you know, after that it says 'Okay, I, I, I can't really reason about it'. So, the 00:13:14.042-->00:13:19.583 flipside is you have a technique that says 'That is not safe, I can prove it. But I can't really 00:13:19.583-->00:13:23.625 prove, you know, if it is safe, but you know, if it is not safe I can give you a counter 00:13:23.625-->00:13:30.417 example'. Uhm, and the way this works is, uh, by, you know, finding counter examples; do 00:13:30.417-->00:13:37.667 whatever technique, uhm, so in this case with a slightly different, uh, uhm, condition. 00:13:37.667-->00:13:45.542 That is, uh, a squared plus b squared equals c squared - a technique might find a, b, and c 00:13:45.542-->00:13:49.917 as three, four, and five as a counter example that will reproduce a crash. And, so, this 00:13:49.917-->00:13:55.833 is, uh, there are many techniques that, you know, will be mentioned later that, uh, can 00:13:55.833-->00:14:02.208 be used to do program testing. But one of the very early one, the first instance of, uh, 00:14:02.208-->00:14:08.417 program testing of this style that I found was in the 1950s - which is about four decades 00:14:08.417-->00:14:16.708 before I thought that this, uhm, kind of idea was, was, uh created. Uh, programmers in the 00:14:16.708-->00:14:23.917 1950s would program in punch cards and, uh, to test their code it was common practice to 00:14:23.917-->00:14:30.792 dig punch cards out of the trash and feed them as input to your program. This unexpected input - 00:14:30.792-->00:14:37.333 just random stuff and, of course, if I ran random stuff your program shouldn't crash. So 00:14:37.333-->00:14:45.625 this is kind of an early, uh, uhm, example of the sort of, uh, kind of institutionalized 00:14:45.625-->00:14:54.167 testing, uh, that we're, you know, only seeing come back, uhm, recently. Uhm, and so, the, 00:14:54.167-->00:14:59.000 the, these early developments - verification, testing, the, the creation of those two ideas, 00:14:59.000-->00:15:06.083 uhm, and then, uhm, the idea what you might check for so, uh, the , uhm, you know. Uh, Turing 00:15:06.083-->00:15:13.125 reasoned about, uh, ensuring logical properties. Uhm, but this was all done manually so 00:15:13.125-->00:15:18.708 this kind of our first, uh, set of tools in our tool bag and they're manual tools. You have 00:15:18.708-->00:15:23.625 to dig them out, uh, okay, yea, let's get our trash, uh, you know, cards, this one's got 00:15:23.625-->00:15:28.667 eaten by something and you know, put in the ones that won't jam your machine and, and, and, uh, 00:15:28.667-->00:15:37.583 try them. Uh, but none of this was automated and so, uh, as computers became more and more 00:15:37.583-->00:15:42.958 ubiquitous the need for automation started showing itself. Uhm... So, again. The 00:15:42.958-->00:15:50.500 we, uhm, uh, a mention of Grace Hopper here, uhm, because she not only found the first bug but 00:15:50.500-->00:15:58.125 she also invented the compiler. So, Grace Hopper in 1952 published a paper saying 'Hey, 00:15:58.125-->00:16:02.042 what if wrote in kind of higher level languages and you know, it got squashed down to, to 00:16:02.042-->00:16:09.500 computer code.' Uhm, and, uh, this took a little while to catch on and the reason it took 00:16:09.500-->00:16:16.750 a while to catch on, well, one of the reasons is that, uh, the code that was generated by this 00:16:16.750-->00:16:22.083 compiler was very slow. It couldn't be, uh, you know, it could be optimized as well as 00:16:22.083-->00:16:29.333 hand-written assembly could at the time. Uh, and so this, uh, identified another need, another 00:16:29.333-->00:16:33.708 goal of programming analysis - transformation of binaries into something different, something 00:16:33.708-->00:16:38.542 faster in this case. Uhm, and, and in the modern era, you know, you can transform binaries for 00:16:38.542-->00:16:44.667 example or transfer programs to, uh, ensure that they're safe. You can transform programs to 00:16:44.667-->00:16:51.250 meet any sort of specification to run on a different set of hardware. Uhm, and so, uh, now 00:16:51.250-->00:16:55.708 we needed to optimize code because, you know, people write slow code when they're writing 00:16:55.708-->00:17:04.000 source for whatever reason. Uhm, and, uh, another thing happened, people started realizing that we 00:17:04.000-->00:17:11.083 have all these, uh, architectures with, uhm, all of this data floating around in 00:17:11.083-->00:17:16.292 them and if you're not very very very careful some data could be read from or written to a 00:17:16.292-->00:17:23.083 different location than intended. And, uh, the memory could be corrupted. So, I just 00:17:23.083-->00:17:29.583 played, you know, two days of a CTF full of these errors of course, memory corruptions, uh, 00:17:29.583-->00:17:37.667 bugs, uhm, and, uh, this was first described in 1968, in 1968 there was a paper saying hey, 00:17:37.667-->00:17:44.333 you know, we noticed that, uh if the kernel, I think they called it a monitor at the time, 00:17:44.333-->00:17:51.625 blindly trusts everything that, uh, you know the user, the user space sends bad things can start 00:17:51.625-->00:17:55.958 to happen. Uhm, and so this paper introduced this concept. It's also the paper that, you 00:17:55.958-->00:18:02.042 know, one of the early works in memory protection, uh and virtual memory and so forth. 00:18:02.042-->00:18:07.792 Uhm, which is pretty interesting the immediately they realized this was a problem. And, uhm, a 00:18:07.792-->00:18:13.292 little while later... Uh, there was a, you know, Ken Thompson's reflections on trusting trust 00:18:13.292-->00:18:17.333 for the very reason that you can build in a backdoor into a compiler that could build in 00:18:17.333-->00:18:22.917 backdoors into sensitive code. And so, suddenly we have, uhm, two more things that we need to, 00:18:22.917-->00:18:30.542 uh, worry about in terms of specifications. Uhm, or even more, but, you know, including 00:18:30.542-->00:18:35.333 memory safety; information disclosure; uh, and authentication, right? So, now 00:18:35.333-->00:18:42.375 you might want to verify that a program doesn't have a backdoor. Uhm, or you might verify that a 00:18:42.375-->00:18:48.458 program will not leak your private sensitive information. That is; that one is, uh, very, 00:18:48.458-->00:18:53.792 uh, relevant today with all of our phones having all of our information and, uh, very little 00:18:53.792-->00:18:58.417 control over it. [sneeze] Uhm, and so, the need for automation was pretty well established, uh, 00:18:58.417-->00:19:10.167 by the kind of, turn of the century for sure, uhm, but even before that, uh, those papers 00:19:10.167-->00:19:18.875 were like in the 19- you know 60s or something, late 1960s and very quickly. Oops, sorry. Very 00:19:18.875-->00:19:23.250 quickly, uh, people started to, uhm, meet this need. The research community started 00:19:23.250-->00:19:27.875 pumping out automated approaches and so I'm going to introduce a couple of these automated 00:19:27.875-->00:19:34.708 approaches. Uhm, and, uh, before I do so, I want to make you guys, uh, experts in program 00:19:34.708-->00:19:42.583 analysis so that we can reason about what's going on here. So, uh, we'll talk about a couple of 00:19:42.583-->00:19:50.750 prerequisites, right? So, let's say you have a program, so, on the top right there's like a 00:19:50.750-->00:19:58.000 little python program already, uh, that, already a vulnerable program, by the way. Uh, and so 00:19:58.000-->00:20:03.167 you have this program, uh, and you wanna analyse it. So you have to reason about a program 00:20:03.167-->00:20:08.833 in a slightly different way as computer than as a human. So, for example, a program is viewed 00:20:08.833-->00:20:14.667 by a computer as a set of basic blocks. A basic block is a piece of code that is executed, uh, 00:20:14.667-->00:20:21.750 all together before passing on control flow somewhere else. So, uh, in our case, we'll pretend 00:20:21.750-->00:20:28.667 that... Input is, are the basic blocks of this x equals input is, uh, a single basic block and 00:20:28.667-->00:20:33.833 then it might branch depending on the input. Right? So, if you put in '42' it'll do one thing; 00:20:33.833-->00:20:38.583 if you put in, uh, something else, it'll do another. And so this is the end of the basic 00:20:38.583-->00:20:44.458 block and then the result of that IF statement is two other basic blocks - the true case and 00:20:44.458-->00:20:51.917 false case. And each of these has, uhm, a, uh, constraint that has to be met, right? In order 00:20:51.917-->00:20:57.208 to go down one path you have to put in 42; in order to go down another you have to put in not 00:20:57.208-->00:21:03.583 42 - as these are called constraints. If you then, uh, look at all of the basic blocks 00:21:03.583-->00:21:08.083 of a program - this is called a control flow graph. Uhm, because, that's, uhm, you know 00:21:08.083-->00:21:14.833 these are basic blocks and control flows between them. And, uh, if you look at a path down 00:21:14.833-->00:21:21.750 this graph - no in this case the graph is nice and simple but in reality it could have loops. A 00:21:21.750-->00:21:25.875 path might hit the same node multiple times and so on. UIhm, and then you look at the 00:21:25.875-->00:21:32.708 contraints all along this path. These are the path predicates that, uh, uniquely identified 00:21:32.708-->00:21:40.708 this path. Uhm, so if you collect all of these constraints and you, uh, say x is not 42 but 00:21:40.708-->00:21:48.958 x is 1 43 7 that input will, uh, any input that matches those constraints will take the same 00:21:48.958-->00:21:55.042 path through the program. Uhm, so these are kind of the, the prerequisites of our program 00:21:55.042-->00:21:59.458 analysis technique so now we'll go through three of them actually, for time reasons we'll 00:21:59.458-->00:22:05.333 go through two of them and mention a third. But we'll start with symbolic execution. And 00:22:05.333-->00:22:11.292 symbolic execution got a lot of hype, uhm, recently especially with stuff like the cyber grand 00:22:11.292-->00:22:20.292 challenge, uhm, uh and so on a s way for, uh, machines to reason about program code. Uhm, and 00:22:20.292-->00:22:25.875 you'd think that this is something new but it turns out that it is not. It's, uh, quite 00:22:25.875-->00:22:32.250 old actually, so 40 years ago, uh, little bit more, the first symbolic execution paper that I 00:22:32.250-->00:22:38.333 could find was proposed. Uhm, and there were, there were several actually, right, in one 00:22:38.333-->00:22:43.875 year basically. So, this idea had some prerequisites that were met and then it exploded. Uhm, 00:22:43.875-->00:22:51.000 and so the symbolic execution engines were developed that, uh, could then symbolically execute 00:22:51.000-->00:22:56.542 force ran code. Now we have symbolic execution engines, uh, that you can download off GitHub 00:22:56.542-->00:23:05.458 that can execute binaries, Java, uh, Android, whatever you want. Uhm, and, uh, this is kind of a, 00:23:05.458-->00:23:10.750 a fairly powerful way of reasoning about programs. And, uh, let's run through an 00:23:10.750-->00:23:16.542 introduction of it with a slightly more complicated, uhm, example than, you know, what we 00:23:16.542-->00:23:24.292 learned about binary - uh, program analysis with. Uhm, hold on. [pause] So, here's a program 00:23:24.292-->00:23:32.875 that has several bugs, right? Uhm, one is it, uh, well, it definitely has one bug and that 00:23:32.875-->00:23:38.708 is if you enter, uhm, a, uh, username of 'service' and the command code of seven it'll 00:23:38.708-->00:23:43.958 crash, right? [audience noise] Uhm, you can imagine that instead of this crash it does 00:23:43.958-->00:23:49.333 some system, uh relevant stuff so it could be a backdoor. And so - instant memory corruption, 00:23:49.333-->00:23:53.125 but basically we have a program with a bug... And we would like to find this bug. So, I see how 00:23:53.125-->00:23:58.375 some of you might approach this problem with symbolic execution, right? Uhm, so, first let's look 00:23:58.375-->00:24:03.458 at the base, uh, the control flow graph of this program - starting from the beginning. And 00:24:03.458-->00:24:08.417 the control flow graph is, uh, made up of basic blocks and the control for transitions between 00:24:08.417-->00:24:13.792 them. So, we start at this input, uhm, if the input is 'service' it branches. If the 00:24:13.792-->00:24:20.417 username is service it branches into one side of the, uh, equation where it, of the 00:24:20.417-->00:24:26.333 program where it, uh, checks for the command code being seven. And if it is it crashes; if not 00:24:26.333-->00:24:35.208 it prints unknown command. Uhm, and then it, uh, exists. On the other side of the branch it, uh, 00:24:35.208-->00:24:41.792 checks - asks for a, a passcode. If the passcode is invalid it prints 'Invalid passcode' 00:24:41.792-->00:24:47.250 otherwise it calls the authentication function and then it prints 'exit' and exits. So, 00:24:47.250-->00:24:51.750 this is our, our control flow graph and how would we, uh, use symbolic executions to try to 00:24:51.750-->00:24:56.250 find that crash - to try to find, uh, the ability to read the crash. So,uh, we would start 00:24:56.250-->00:25:05.500 executing the program in an emulator and in this emulator - instead of ones and zeros we are 00:25:05.500-->00:25:14.083 working on, uh, 'x', 'y' and other symbols, right? So for example 'username', uh, is a 00:25:14.083-->00:25:19.625 symbol in this, uh, emulator, so when we pull in an input it will produce an unconstrained 00:25:19.625-->00:25:25.292 variable called 'username'. And you don't know what username is; username could be anything. Uh, 00:25:25.292-->00:25:30.958 because, you know... That is, you know, how our, how we increment our emulator. Uhm, and 00:25:30.958-->00:25:39.292 as we check for values of username, we create what are called 'constraints', right? So 00:25:39.292-->00:25:46.000 these are the exact constraints of the basic block checks, uh, when it pushes execution 00:25:46.000-->00:25:52.000 forward. Uhm, and we collect two constraints in this case, on the one side 'username equals 00:25:52.000-->00:25:55.250 service' and on the other side it 'does not equal service'. These are constraints and we 00:25:55.250-->00:26:02.000 continue, uh, executing both sides of the If statement with symbolic execution. But then we 00:26:02.000-->00:26:09.375 hit something that is very bad for symbolic execution. We hit, uh, for example string 00:26:09.375-->00:26:15.917 processing functions. So, a string processing function like 'a to i' might check a given 00:26:15.917-->00:26:20.792 byte. See if it is a number, if it is a number it'll do one thing. If it's not it'll do 00:26:20.792-->00:26:25.750 another, right? Or if it's a certain number it might be one, if it's not simple number it 00:26:25.750-->00:26:31.833 will do another. So, it'll keep branching - the symbolic emulator at every, uh... I'm 00:26:31.833-->00:26:40.333 sorry... [pause] Oh, awesome. It'll keep branching the symbolic emulator at, uh, every 00:26:40.333-->00:26:49.458 if statement; at every check I'm this number until we get into a situation where there are just 00:26:49.458-->00:26:58.542 too many checks, right? So, it'll try to check for a command code of, you know, uh, ten bytes 00:26:58.542-->00:27:04.750 with, uh, arbitrary values of nine bytes and so on. And there's exponential, uh, path 00:27:04.750-->00:27:10.667 explosion here, uh, and there are some approaches in the symbolic, uh, execution world to 00:27:10.667-->00:27:16.500 kind of deal with this sort of path explosion. But, in general these approaches boil down to 00:27:16.500-->00:27:20.750 the requirement to remove paths, right? And lose this information. And so, in the end 00:27:20.750-->00:27:28.750 the symbolic execution engine might, uhm, only find certain paths and not others and miss 00:27:28.750-->00:27:36.667 the bug because we had to simplify to keep things tractable. So, that's symbolic 00:27:36.667-->00:27:41.958 execution. It might find a bug - if we're lucky, right? But if you're not and it has to 00:27:41.958-->00:27:48.333 simplify, uh, it's state space essentially, uh, as it's executing there are certain 00:27:48.333-->00:27:55.292 things that it might miss. Uhm, so my execution was proposed as, uh, you saw, in 1975, uh, but 00:27:55.292-->00:28:04.667 the interesting thing is that in, uh, Ada Lovelace's notes from, uhm, 1942, we can see that 00:28:04.667-->00:28:14.542 she did a symbolic trace of the execution of her program. So, in, where she has this sort of 00:28:14.542-->00:28:21.708 program execution, uh, log in her notes, she writes down the symbol, the, the equation for 00:28:21.708-->00:28:28.708 each, uh, uh, variable as, uh, the program progresses. And this is the first symbolic trace of a 00:28:28.708-->00:28:33.750 program - done in 1842 back before computers were invented. So, that was a pretty 00:28:33.750-->00:28:41.125 interesting thing to find, uh, and kind of a nice point of history that we can put as the 00:28:41.125-->00:28:48.792 start of program analysis, in this sense - 19 - uh, 1842. Not, you know, 1975 or 1949 or, uh, 00:28:48.792-->00:28:58.500 any of those much, much later dates. [sniff] And so symbolic execution, uh, is a kind of tool 00:28:58.500-->00:29:04.542 in our tools set. Uhm, that, uh, we can use to achieve, uh, either verification or 00:29:04.542-->00:29:09.875 specification but testing that specification , uh, or to support the transformation of 00:29:09.875-->00:29:16.375 code. Uh, of course how you verify a program for example using just symbolic execution. 00:29:16.375-->00:29:21.750 Uh, is a pretty complex, uh, thing with the symbolic execution style that described - 00:29:21.750-->00:29:25.583 the sort of program you're testing it generates inputs to find vulnerabilities but it 00:29:25.583-->00:29:34.792 can't prove that there aren't any. Uhm, but, uh, that's kind of a - you could go down that 00:29:34.792-->00:29:40.583 route for an entire semester course and not just a, uh, 45 minute introductory talk. So, 00:29:40.583-->00:29:45.125 I'll leave that as future research for you guys. [audience noise] And we'll go on to static 00:29:45.125-->00:29:54.333 analysis because static analysis can, uh, show that for example a program is, uhm, immune to a 00:29:54.333-->00:30:02.125 certain class of vulnerabilities or, uh, so, properly implements a certain specification. Uhm, 00:30:02.125-->00:30:09.792 static analysis, uh, or at least one of the very, uh, common ways to do static analysis which is 00:30:09.792-->00:30:16.833 abstract interpretation, uh, was proposed in, uh, 1977 shortly after symbolic execution. And, 00:30:16.833-->00:30:23.708 uh, abstract interpretation looks at the, uh... Oops, that should say 'abstract 00:30:23.708-->00:30:29.417 interpretation', uhm, looks at, uh, control flow graph. The, the, the program as a whole, 00:30:29.417-->00:30:36.167 essentially. [background noise] It, uh... Doesn't have to figure out how to reach a certain, uh, 00:30:36.167-->00:30:43.833 basic block to reason about properties of the program at that basic block. Uh, which, is 00:30:43.833-->00:30:46.833 the the problem that symbolic execution had and, and, and, uh the reason symbolic execution 00:30:46.833-->00:30:53.458 could not find the bug in our example. And so, uh, static analysis with abstract 00:30:53.458-->00:30:58.667 interpretation might be able to find that - probably will be able to find that bug if it is a 00:30:58.667-->00:31:05.542 simple bug or, actually, I should say WILL be able to find that bug. Uhm, because if it 00:31:05.542-->00:31:10.417 cannot prove that a piece of code is safe it will, uh, raise an alert. The problem is that, 00:31:10.417-->00:31:15.667 as we talked about, there are false positives so in our program it might think that 00:31:15.667-->00:31:23.083 function has a bug even if it, uh, doesn't alert on that and eat up time, uh, for a human to 00:31:23.083-->00:31:29.625 go through and verify all these results. Uhm, and so through it, abstract interpretation we've 00:31:29.625-->00:31:37.292 got a way to, uhm, perform verification or specification on a program. Uh, in 1977, 40 years 00:31:37.292-->00:31:45.083 ago. Uhm, and then we moved on to, uh, fuzzing and so fuzzing is kind of one of the uh, uh, 00:31:45.083-->00:31:50.875 biggest ways to find vulnerabilities in modern software and it's actually 00:31:50.875-->00:31:56.292 surprisingly simple, uh, proposed in 1981, initially in its most basic form which was, 00:31:56.292-->00:32:01.875 uh, hey, uhm, let's throw random input into our program and and see if it crashes. It's evolved 00:32:01.875-->00:32:09.625 quite a bit since then and so, the specific, uh, implementation of fuzzing that I'll describe 00:32:09.625-->00:32:17.375 here is implemented by American fuzzy loft, uhm, it's a fuzzer that mutates its inputs when it 00:32:17.375-->00:32:24.458 detects differences in program execution. And so, let's see how it would run on our program 00:32:24.458-->00:32:31.583 here, uhm, we'll start with, uh, some randomly generated test case or human-seeded test case; 00:32:31.583-->00:32:41.375 so a human might input a user name of ASDF and a password of 1 1 1. And, uh, that, uhm, input 00:32:41.375-->00:32:47.000 will trigger certain basic blocks to be executed, right? And so it executed the user name 00:32:47.000-->00:32:53.708 input, of course. We executed the chat for the, uhm, kind of service username that could lead 00:32:53.708-->00:33:00.083 to the crash. We did not satisfy it so we took the else branch, uh, read in the passcode and, 00:33:00.083-->00:33:06.917 uh, error'd out on, on invalid, uh, passcode. Uhm, and exited. So we triggered those basic 00:33:06.917-->00:33:14.375 blocks. And so the fuzzer starts mutating this input, right? It might make the lowercase d a 00:33:14.375-->00:33:25.208 capital D or something or it might, uhm, or it might mutate, uh, input in a way, uh, passes 00:33:25.208-->00:33:31.625 another check. So it mutated input in a way that, uh, passes that, uh, passcode check. It 00:33:31.625-->00:33:36.958 actually doesn't because there's another bug in the program that I didn't notice before. But, uh, 00:33:36.958-->00:33:44.292 let's pretend that it, uh, uh, it, it creates a valid, you know, size of a passcode. And, 00:33:44.292-->00:33:50.708 uh, triggers that authenticated, uh, authentication function, right? So that is a new basic 00:33:50.708-->00:33:55.875 block that it triggers and now we, with fuzzing we've, uh, triggered a block that, you 00:33:55.875-->00:34:02.083 know, symbolic execution before us wasn't able to trigger. Uh, just through randomly mutating, 00:34:02.083-->00:34:08.667 uhm, inputs. But then we get stuck because through randomly mutating inputs we are unable to 00:34:08.667-->00:34:18.708 satisfy complex checks, right? We need a username of 'service' and we have randomly mutated 00:34:18.708-->00:34:23.958 usernames. The chances are that it'll create the string service are very slim and we'll keep 00:34:23.958-->00:34:29.000 guessing and guessing and guessing. Of course, in this specific case, you could seed 00:34:29.000-->00:34:34.000 the fuzzer with the string 'service' and you could scan the binary for, or the program for 00:34:34.000-->00:34:40.125 all of its strings and, uh, automatically, you know, make the fuzzer pass this check but, 00:34:40.125-->00:34:46.208 you know, screen checks aren't the only complex checks in programs - these are hashes; 00:34:46.208-->00:34:53.333 there are, uh, complex, uh, input formats, uhm, dependencies between different input bytes 00:34:53.333-->00:35:01.375 and so in the general case we, uh, cannot guarantee of course with a fuzzer that we'll find, 00:35:01.375-->00:35:08.542 uh, code that is protected by these complex checks. Uhm, and so, you know, fuzzing with this 00:35:08.542-->00:35:19.042 random data, of course is a throwback to this trash stack concept. So, you know, fuzzing 00:35:19.042-->00:35:27.792 was invented in 1950 - not 1981 - uhm, or at least manual fuzzing. Uh, so, again, we find 00:35:27.792-->00:35:33.750 that, you know, program analysis techniques harping back to the middle of the century, uh, and 00:35:33.750-->00:35:40.208 even, and sometimes even farther to, uh, the 1800's. Uhm, so now we kind of have this toolbox of 00:35:40.208-->00:35:47.083 a bunch of specifications that we can enforce, uh, a, uh some goals that our analysis could, 00:35:47.083-->00:35:53.417 uh, try to achieve and the technique through which we, uh, can achieve them and, uh, next 00:35:53.417-->00:36:03.667 we should evaluate them and understand how these, uh, different, uh, understand how 00:36:03.667-->00:36:07.708 these different goals, uhm, or how these different techniques help us, uh, achieve program 00:36:07.708-->00:36:16.958 analysis goals. And, uhm... As a scientist, you know,uh, if you, uh, uh, start thinking up an 00:36:16.958-->00:36:24.625 approach and you have a cool idea and you have, uh, a new program analysis technique - you 00:36:24.625-->00:36:30.333 want to evaluate it. So, you wanna take, uh, programs and specifications; feed them into 00:36:30.333-->00:36:37.042 your technique and see how well it does. This is my clipart, uhm, slide by the way, so 00:36:37.042-->00:36:42.417 hopefully my clipart game is on point. Uhm, so, you, you run your analysis; you get your 00:36:42.417-->00:36:49.292 results; and you're happy, right? Well there a number of problems with this - one, is 00:36:49.292-->00:36:55.667 that the analysis is more complex than you might think because any program analysis has 00:36:55.667-->00:37:01.333 to deal with the environment of the program it's analyzing. And environments like Windows, MAC 00:37:01.333-->00:37:10.167 OS, Linux, uh, mobile devices. Uh, cyber physical devices - they have really complex 00:37:10.167-->00:37:20.708 environments and having to model this environment even before analyzing, uh, understanding how 00:37:20.708-->00:37:27.083 much better your program analysis has to be unique; is than previous techniques is 00:37:27.083-->00:37:32.208 quite a big investment that, uh, people often don't make or, uh, make in a kind of, uh, very, uh, 00:37:32.208-->00:37:38.500 fast matter. Another problem is finding a good dataset... To evaluate on, right? Uh, there's 00:37:38.500-->00:37:49.917 not really a good dataset for, or there wasn't great dataset for vulnerability research - 00:37:49.917-->00:37:51.833 this problem is actually being worked on and new datasets are being created as I'll, uh, talk 00:37:51.833-->00:37:56.292 about. But you need a good dataset with, uh, ideally known vulnerabilities, so you can 00:37:56.292-->00:38:00.750 reason about how many of them you'll do bug finds. Uh, and, uhm, with a variable 00:38:00.750-->00:38:05.917 vulnerability and different programs, so, you're, uh, your technique isn't, uhm, you know, 00:38:05.917-->00:38:13.833 specifically tailored for, uh, one style of vulnerability that you happen to detect, uh, or, 00:38:13.833-->00:38:18.792 one specific program that you have to be very good at analyzing. Uhm, another problem 00:38:18.792-->00:38:23.625 is these specifications, right? Specifications in the real world are very complex, uh, where as 00:38:23.625-->00:38:31.917 specifications, uhm, that you might want to use for your, uh, analysis tool initially in the 00:38:31.917-->00:38:36.458 early stages of development need to be fairly simple and ideally be provided. I mean if you're 00:38:36.458-->00:38:42.958 looking at the, uh, analyzing something like Chrome and your specification is that Chrome 00:38:42.958-->00:38:49.833 should not leak, uh, user data to someone that should not get this user data. That's 00:38:49.833-->00:38:55.708 impossibly broad and impossible to enforce. Is your bank allowed to have your, you know, various 00:38:55.708-->00:39:04.667 cookies or, or, something along these lines? Uhm, so, you need a very good dataset - standard 00:39:04.667-->00:39:10.042 dataset or a very good, uh, standard implementation, uhm, uh, standard set of 00:39:10.042-->00:39:18.208 specifications so that you can analyse how well your technique runs compared to, uh, uh, 00:39:18.208-->00:39:25.375 different work and compare those results to prior work because that's a very important part of 00:39:25.375-->00:39:29.625 science and technical development is understanding if you're making an improvement or 00:39:29.625-->00:39:40.125 not. [sniff] Uhm, and so we had problems as a, analysis community in, in meeting all of 00:39:40.125-->00:39:44.125 these goals [sneeze] And having a good dataset of application with a good set of 00:39:44.125-->00:39:51.042 specifications on a good, uhm, environment that wasn't too complex to, uh, implement and I 00:39:51.042-->00:39:56.458 could produce results that we could reason about; that we could say okay, you know, we 00:39:56.458-->00:40:03.875 have ground proof data for the vulnerabilities that are actually in this dataset and uh, 00:40:03.875-->00:40:11.833 we detect x of them. Or we, uh, manage to rule out vulnerabilities in code that has 00:40:11.833-->00:40:19.000 no vulnerabilities and, uh, you know, so our program verification is correct. Uhm, 00:40:19.000-->00:40:25.833 and, and so there, like I've mentioned there have been several, uh, projects to, uh, 00:40:25.833-->00:40:30.708 solve this problems or create these data sets. And on of these, uh projects essentially 00:40:30.708-->00:40:36.750 with the cyber grand challenge. If you guys were here last year you probably saw all of the, uh, 00:40:36.750-->00:40:44.750 cyber grand challenge, uh, you know, hoopla, uh, where for the first time in history seven 00:40:44.750-->00:40:52.167 fully automated program analysis machines, uh, fought each other in a game of 'capture the flag'. 00:40:52.167-->00:40:59.167 So, the same game that I spent the entire weekend, uh, playing and only got four hours of sleep 00:40:59.167-->00:41:06.833 - is the game that machines that didn't need to sleep - played yesterday, uh, last year rather. 00:41:06.833-->00:41:13.500 And, uhm, these, uh, machines of course suffer from all the of the problems I just talked 00:41:13.500-->00:41:17.250 about. The environmental problem; the specification problem. And so the cyber grand 00:41:17.250-->00:41:25.583 challenge created a custom operating system with very specific vulnerability 00:41:25.583-->00:41:33.958 specifications to, uh, evaluate these systems. Now, for the actual competition of course the 00:41:33.958-->00:41:38.750 source code wasn't available since then, uh, they, uh, released source code so you can 00:41:38.750-->00:41:44.958 really look at the source code; understand the vulnerability and then reason about how well your 00:41:44.958-->00:41:50.750 tool finds certain vulnerabilities. Across 249 binaries - so it's, uh, it's a 00:41:50.750-->00:41:58.708 249 programs; so, it's a dataset that has a, uh, lot of variants. There a lot of different types, 00:41:58.708-->00:42:07.417 uhm, and uh, different difficulties of vulnerabilities and, uhm, all of this is freely 00:42:07.417-->00:42:14.625 available for, uh, people to analyse their tool and understand how well it does. 00:42:14.625-->00:42:19.792 That's my other piece of clipart. [audience noise] Uhm, so the cyber grand challenge and 00:42:19.792-->00:42:25.958 the, the programs that, that were written for these - the 249 programs making up the cyber 00:42:25.958-->00:42:34.000 grand challenge dataset, uhm, allowed us to, uh, do what I call; to perform what I call the 00:42:34.000-->00:42:38.500 program analyses nursery experiments. So, I see the cyber grand challenge dataset the 00:42:38.500-->00:42:43.042 nursery of program analysis where you can reason about different improvements for 00:42:43.042-->00:42:49.542 different techniques. So, for example symbolic execution on the entire dataset finds nine 00:42:49.542-->00:42:53.375 vulnerabilities - the symbolic execution as implemented in Anger which I'll talk about in a 00:42:53.375-->00:42:58.042 sec. Uh, which is an open source, uh, binary analysis program available on GitHub. 00:42:58.042-->00:43:05.000 Uhm, but symbolic execution on this entire dataset finds nine vulnerabilities. That's not a 00:43:05.000-->00:43:11.333 lot, right? There are vulnerabilities in every program of these 249 programs - it only 00:43:11.333-->00:43:17.250 finds vulnerabilities in nine of them. Uhm, of course we can optimize symbolic execution 00:43:17.250-->00:43:22.000 using various tricks - anger supports, for example, concrete execution when there's, uh, no 00:43:22.000-->00:43:26.958 uncertainty in this state; when all the data is known. Uh, or when there are constraints on 00:43:26.958-->00:43:36.583 all the data and so by utilizing all of these optimizations, uh, we can get 26, uh, crashes - 00:43:36.583-->00:43:43.167 crashes in 26 binaries. Uh, utilizing static analyses. [background noise] Sso, uh, uh, 00:43:43.167-->00:43:47.542 combining symbolic execution with vary-testing which is a technique by Carnegie Mellon 00:43:47.542-->00:43:53.750 University, uh, that utilizes parts of abstract interpretation to help with symbolic execution. 00:43:53.750-->00:43:58.458 We can push that up to 31 - so I should say here that this our implementation of vary testing 00:43:58.458-->00:44:04.500 and it might be, uh, suboptimal so, there varied testing might be considerably better. Uhm, but 00:44:04.500-->00:44:12.250 that all pales in comparison with fuzzing. This seemingly simple technique of throwing 00:44:12.250-->00:44:20.250 random data and seeing what happens, uh, finds 106 crashing binaries in the dataset. Uhm, so 00:44:20.250-->00:44:26.167 this gives us an idea of where program analysis is and, and, this is a good showcase for the 00:44:26.167-->00:44:32.833 simplicity of, of evaluating, uh, all of these different analysis on this dataset and 00:44:32.833-->00:44:39.042 reasoning about the results. Because now we can look at them in terms of, uh, you know, 00:44:39.042-->00:44:43.417 summation numbers but there's also some subtleties there - they find bugs. [background 00:44:43.417-->00:44:48.417 noise] Different types of bugs in different binaries. So, uh, we can look into that and make 00:44:48.417-->00:44:57.292 inferences and try to create new, um, approaches. So, for example, we looked at the 00:44:57.292-->00:45:02.750 difference in the types of bugs that symbolic execution found and that fuzzing found. And we, 00:45:02.750-->00:45:09.125 uh, realize that they have very different coverage. So, the types of; the basic blocks that 00:45:09.125-->00:45:12.333 fuzzing can trigger are very different than the basic blocks that symbolic execution can 00:45:12.333-->00:45:17.000 trigger. And sometimes one finds a crash; sometimes another finds a crash; sometimes neither of 00:45:17.000-->00:45:22.875 them finds a crash. In fact, very frequently. And, so, we uhm, decided to combine them in 00:45:22.875-->00:45:32.750 a very, uh, straightforward but careful way. Uhm, the idea is as follows. We begin by fuzzing the 00:45:32.750-->00:45:37.708 binary; this is nice an fast and achieves decent code coverage but as we discussed eventually 00:45:37.708-->00:45:43.958 gets stuck on complex checks. And then we use symbolic execution to find a constraint 00:45:43.958-->00:45:50.083 that can get through that check but possibly suffer from other limitations in symbolic 00:45:50.083-->00:45:53.833 execution and not find the actual bug. And then we synchronize that back into the 00:45:53.833-->00:45:59.000 fuzzer - we synchronize the knowledge of how to bypass the complex check back into the 00:45:59.000-->00:46:07.000 fuzzer and it continues to mutate that input until it finds the bug. Uhm, and we do this 00:46:07.000-->00:46:11.875 iteratively, or, uh, back and forth between the fuzzer and the symbolic execution. So, by 00:46:11.875-->00:46:20.542 implementing symbolic assistance, for the fuzzer in this way, uh, we achieve - on 00:46:20.542-->00:46:27.625 this entire dataset - 118 crashes. Uhm, and an interesting is here, here is that we have 00:46:27.625-->00:46:35.000 this 118 crashes in the dataset but, uhm, if you find the union of all of the different 00:46:35.000-->00:46:38.750 techniques - all of the different techniques have crashed, something like this 00:46:38.750-->00:46:46.458 from memory, 150 to 160 binaries. So, there's a lot of, uh, uniqueness between the 00:46:46.458-->00:46:53.792 different techniques used here. Uhm, driller, uh, the applicability of it varies by 00:46:53.792-->00:46:58.083 program whether or not there are complex checks, uhm, we can run through a quick run here. So 00:46:58.083-->00:47:05.167 this is a control flow graph of an example program and driller start in the top left corner 00:47:05.167-->00:47:13.083 there. And, uh, it first starts by fuzzing a portion of the program before it gets stuck in 00:47:13.083-->00:47:19.917 a complex check. Uhm, and this is the basic block coverage on the right in this graph here. 00:47:19.917-->00:47:25.625 Uhm, you can see it just kinda flatlines, right? So, then if we run the symbolic execution 00:47:25.625-->00:47:33.750 engine to, uh, help the fuzzer reach extra code paths, uh, it allows us to find just a little 00:47:33.750-->00:47:40.125 tiny, uh, bit more basic blocks in the; uh, execute some more basic blocks in that, uh, 00:47:40.125-->00:47:45.208 control flow graph with the program. And if we keep, uh, invoking the symbolic execution 00:47:45.208-->00:47:52.042 engine to help the fuzzer get unstuck every time that, the, the coverage flatlines like, we 00:47:52.042-->00:47:57.375 eventually drill into the program deep enough to find the bug. And so that's how it really 00:47:57.375-->00:48:04.208 works. Uhm, there's still a lot to do, so there's this whole red, uh, area that, uh, however 00:48:04.208-->00:48:10.500 many programs - about 100 programs that we have never exploited before. Uhm, that 00:48:10.500-->00:48:14.333 we've never crashed before using any automated techniques. Uh, which represent, uh, missing, 00:48:14.333-->00:48:22.333 uh, tools, basically that humanity has yet to develop, or at least we have yet to develop. 00:48:22.333-->00:48:29.375 Uhm, and so if this all sounds interesting to I encourage you to join in. There's several ways 00:48:29.375-->00:48:34.042 that you can participate in program analysis research. One is you can contribute to open 00:48:34.042-->00:48:39.750 source frameworks - so, uh, we run one of these frameworks, uhm, in our research lab - it's 00:48:39.750-->00:48:45.292 called 'Anger' go to Anger dot i o. There's a lot that, uh, we could use help with - 00:48:45.292-->00:48:52.000 documentation; environment support; uh, better techniques; uhm, and so on. Uhm, and the 00:48:52.000-->00:48:56.958 other is that I am always looking for students. I'm starting as a professor at 00:48:56.958-->00:49:05.708 Arizona State University, uhm, I just finished a phd at, UC Santa Barbara and both of those places 00:49:05.708-->00:49:11.833 are incredible places to go to if you want to do research in program analysis or in general 00:49:11.833-->00:49:19.750 security. So, if you're thinking about graduate school, or, uh, you are, uhm, curious and want 00:49:19.750-->00:49:25.583 to do an internship uh, reach out to me - I'll put you in touch with the right people. 00:49:25.583-->00:49:31.833 Uhm, and, uh, you can explore that. Uh, the presentation is available online; all my contact 00:49:31.833-->00:49:37.917 info is right here and I guess we'll do questions in the hall. Awesome, thank you guys! 00:49:37.917-->00:00:00.000 [applause]