Good evening, everyone. Hope you had a good day. Our last keynote for the day is Teri Oda. She has a PhD in computer science with seven published papers. She's currently working as a security researcher in Intel, and she has been awarded numerous awards. And just to name one of them is Google Anita Bogg Scholarship. She's also an org admin for Python Software Foundation in GSOC. Teri, the stage is yours, and I'll put your slides up right now. Hi, Khan India. I hope you can hear me. I actually can't hear you. So this will be a little bit strange. I'm sorry that we can't all be together today, but I'm coming to you live from very foggy and dark Portland, well, just outside of Portland, Oregon. The sun hasn't risen here yet, and it's a little bit hard to breathe because of the fog. So I'm sorry. I've got a cup of water, and I'll do what I can. If you look at the last couple of years of surveys of Python developers, you can see that what people are using Python for is slowly changing and evolving. So data analysis, beta web development a couple of years ago, and the thing that I think is really exciting to me is that machine learning is slowly pushing its way up there. So we're at the point where even if you aren't doing machine learning now, and a lot of you are probably, you're probably going to be looking at it in the next couple of years. There's a good chance you'll learn it. And even if you don't care about any of that, the rise of machine learning and Python together means that you're almost certainly going to be impacted by other people who are doing machine learning here, there, or anywhere. And that's super exciting. That's really, I'm really excited about it because I love machine learning and I love Python. And they seem like a great fit for each other. But as much as I'm excited about it, I'm a little nervous. All right. Sorry, just checking my messages. So I often joke to my friends that Python plus machine learning has created the endless September of machine learning. And if you've not heard this term before, it's an old one from the early days of the internet, when it used to be that people got online usually through university. So every year in September, you'd get a new crop of students and the internet would be full of people who had no idea what they were doing and had foolish questions. And it was chaos for a month every year. And after about a month, people would sort of learn the ropes and learn the unspoken rules and things would settle down, which was fine up until 1993. And in 93, America Online did this big push to get as many people online as they could, as many paying customers as they could garner by sending floppy disks with the program to as many people as they could. And it worked. And so all of a sudden, there were a lot of people online and more people online and more people online and more people online. And the older internet users were not very impressed with this and they coined the term endless September to talk about the fact that it was just a never-ending flood of new users and it never settled down again. That was it. That was the end of the internet as we know it. But that doesn't mean it's the end of everything. However, what do I mean that Python has created the endless September for machine learning? Well, machine learning used to sort of work the same way. It used to be fairly academic. A lot of people came out of universities. You would have sort of a classical education. You might have mentors who you worked with, who could tell you stories about things that didn't work. You'd read papers. You'd read books. You'd have sort of the same time to ramp up before you were sort of released into the world. But that's not the case anymore. You can just go and search for how do I make a neural net and you get a little tutorial with TensorFlow and you're off and running. So there's a constant influx of new users. New users without any sort of background history or anything to help them sort of move into the normal behavior, which, of course, has completely changed. You don't need to go to a university anymore. You don't need to take that compiler's course or learn Lisp before you're in it. You can do machine learning. And before you assume that this whole talk is going to be about how terrible it is and we all should have learned Lisp, let me tell you I didn't learn Lisp either. I'm really a big fan of getting into machine learning in slightly non-standard ways. Although I did go the academic route, I didn't learn Lisp. The reason I got into machine learning was because my friend Assad said, hey, I'm taking this course. It looks kind of cool. You should join me. And I looked at the course and I'm like, oh, that does look kind of cool. But I didn't have the prerequisites. However, at sort of grad school level, that sort of thing doesn't necessarily matter as much. So I went to the prof and I said, in fact, I was still in undergrad at the time. But I went to the prof and said, well, I know this is a grad course and I know I don't actually have all the prerequisites. But it sounds really interesting. Do you mind? And he said, oh, yeah, it'll be fine. Let me know if you get stuck and I can give you some pre-reading or lend you a book or something. And that was it. I was in the course. And it was kind of life-changing, to be completely honest. I was so excited about the Swarm Intelligence course that I kind of accidentally went to grad school. No, no, really, that's really what happened. The final project for that course, I developed a artificial immune system for spam for junk email detection, which was great for me. My parents are biochemists, so I spend a lot of time learning about biology and thinking about these things. Artificial immunology was totally fascinating. It gave me an excuse to flex all those biology muscles without having to actually do lab work or spend hours and days waiting for my seedlings to grow. So it was pretty cool. And I got a paper published. I was still an undergrad. It was amazing. They paid for me to go to a conference in Chicago. I was so excited. But by the time I came around to graduate at the end of the year, the job market wasn't so good. And so the prof I was working with said, hey, you've got most of a master's degree here. You just need to sort of write a thesis. Why don't you take a year and do grad school? And so I did. And that's me. I have a master's in bachelor's in mathematics, master's in artificial intelligence, and a PhD in computer security. And the story about how I got into computer security honestly isn't much more carefully planned out than the story of how I got into artificial intelligence. I actually got interested in computer security while I was in grad school when the skylight in the office that I had broke poured water all over my desk. And this was a problem because I had student papers and stuff in there that I needed to keep locked up by the rules of the university. And so they assigned me a new desk in a room that had had some space, which was the security lab. And I want to say it was like the first day I was there, but it was probably actually in the first week or the first month I came in one day and they had just put in a new security door for pass cards. And about half of the lab was trying to figure out how to get it to play weird noises and whether they could make it the new door, which did have an option to alarm, that find a way to make the new door play. I think it was the Star Trek door opening noise. And the other half of the lab was sitting on the floor outside the lab with the door closed, trying to slide things under the door and trigger the motion sensor so that the door would open without them having to use their pass cards. And I looked at this pile of hooligans that I was sharing some office space with and thought, wow, these are kind of my people. I should learn something about computer security. And so I did. So while we're talking about computer security, it's as good a time as anything, well, while we're talking about security, it's as good a time as any to give the standard legal disclaimer that my employer recommends, which is this talk is all my opinion. It does not represent the views of my employer. I work for Intel where I do open source security. And I sort of like to joke that my job is saying no and telling people that they're wrong because that is a portion of it. But actually a lot of my job is really about explaining things to people so that they can have the knowledge to do the right thing. And in my case, the right thing is to make things a little bit more secure. But let's get back to some machine learning. So I'm really glad that Python and machine learning go together. I'm really glad that lots of new people are getting into the field. That's super exciting to me. It always kind of bugged me that it took so long to get really published in everything. And it's amazing because with all of these tools that are more accessible, we're getting things like open data, which was very hard to find when I was starting. We're getting more opportunities for collaboration, a lot of really new excitement in the field. But as I said, I'm also kind of nervous about it and I'm also kind of sad about it because say what you will about the academic environment but I really enjoyed the part where I got to hear stories about machine learning that did or didn't work, problems that were thought to be intractable and turned out to be tractable. And that was a big portion of what really kept me going in the field through the parts where you have to learn all of the algorithms and well, not all of the algorithms, but you learn a lot of algorithms and you spend a lot of time tuning them. And I think telling those stories, hearing those stories and having some sense of the history of the field actually does make it a little bit better, not just for you because it's fun, but because it helps us avoid some mistakes. So as you may know, I also do a lot of volunteer work for the Python Software Foundation, mentoring students for Google Summer Code and running the program. So I really care about mentoring. And so rather than just whine that there's a lot of noobs in the field and it's kind of scary, I'd like to give you a bit of a masterclass in the parts of the machine learning education that you can't get by finding a very goal-oriented tutorial on how to use TensorFlow. So this is Dr. Terry's lecture on machine learning, my masterclass on machine learning and I even have a whiteboard here for you. So we're just gonna do this thing. So Terry's law number one, your model is only as good as your data. So I guess you probably can't see my whiteboard right now, but it's up on the slide. And this one is pretty much self-explanatory. Garbage in garbage out is sort of a part of the whole field of computer science. If you don't have great data, it's really hard to get anything meaningful. And then number two is your data is always bad. So I don't mean that all of your data is bad, just that it's basically impossible to have perfect data. It's really easy for there to be some sort of way to manipulate the data through, for example, survey questions or who you poll. We often joke in North America that a lot of our polls are done with phone calls and the only people who answer phone calls are over 60 because the rest of us have caller ID and don't bother and haven't really been trained for that. But there's a lot of ways that data can be bad and data, even when you have the best available data may not be perfect. For example, medical data, it's true that many drugs are tested only on men because drug companies don't wanna deal with the issues that could be caused by hormone fluctuations. And so they don't test on women. So we have a lot, a lot of data that is more accessible now, but has some pretty big flaws that may or may not impact what you're trying to do. And then finally, my last law, which is the one that sort of gets top billing in this presentation is that algorithms cheat. And we're gonna tell you some stories about how that happens and when it's really funny. So I don't really wanna give you a whole course on what a machine learning algorithm is. You can look all that up, but here's a sort of rough flow of how most of the algorithms work. So you give it a task that you wanted to do, we'll choose something simple. Today we're going to talk about going and identifying a dog versus a cat.  So this is a cat, I'd have a hundred other cats, this is a dog, I've had to have a hundred other dogs, or maybe I just start with these ones. And so I look at them, I mean, the algorithm looks at them and tries to find features that make them into two distinct sets or reasonably distinct sets with a little margin for error. So an algorithm that's been given this particular data might say, oh, look, well, cats are small, smaller than dogs, and they have point ears and dogs are on average a little bit bigger and they have floppy ears. And so then you go and you test that theory against some data that you've had held out. So I pull out my test data, this is a corgi, and the algorithm will look at it and say, oh, well, it's got pointy ears and it's kind of short, therefore it's a cat. Unfortunately, that's wrong, a corgi is not a cat, a corgi is a dog.  So that's fine for something that's visual. You're probably thinking, but there are much better features you could use for dogs and cats, you could say that cats per and have retractable claws. But to be honest, a lot of tasks that we do in machine learning are sort of image-based, and so they don't necessarily have the whole biological information. Like we could sequence the DNA of these creatures and figure out whether it's a cat or a dog, but that's often not the data that we have available to us. So if we're doing an image classification task, well, we get the easiest available data, right?  Okay, so you do that and you turn the crank and the magic box of your algorithm says, oh, dogs are green. Wait, wait, what? That doesn't make sense, does it?  So here's a Google image search of cats. You can see there's lots of different colors. There's some stripes and of course, because it's 2020, one of them is wearing a face mask. Yeah, that's data is what it is. Okay, pretty reasonable. Looks like a decent collection of cats. And then you look at the dog pictures and oh, look, I see a lot of green. So, and still a face mask because it's still 2020. So yeah, what happens is that people who own dogs are more likely to be taking pictures of them outside in beautiful green grass, with trees, with plants and people who own cats, on average, more of them are inside creatures. So there's not so much green. And so that was good enough, given the thresholds of your algorithm to say, all right, therefore, I don't really need to like, look for facial features or like nose length or the way the body is laid out. No, I can just detect green pixels and that's good enough. And if you have enough green pixels, then you must be outside and therefore it's a dog because algorithms cheat. And this one, we can sort of blame on bad data. Well, clearly I should have used only pictures of creatures with a neutral background or maybe I need to just remove the backgrounds from those pictures to get it to focus only on the part that I really care about. And maybe I should train my algorithm so it gets a bad score anytime it uses something that involves the color green thereafter to try to steer it away from that. But yeah, algorithms cheat. So the next story is one, probably my favorite algorithmic cheating story, which is a program called Genprog. So I worked with the team that did Genprog when I was a postdoc. And it's a super cool algorithm. It's a genetic programming algorithm as you can maybe guess from the name, which means that it mutates code directly. So Genprog itself was used for finding, for fixing bugs in software.  So we've got a bunch of test cases. We pass all of the ones that we have, and then you would have a bug, a new test case that you're failing. And the program would then go and mutate its code, which would give you sort of different options. So we might generate one that, oh, well, it's failing a lot more test cases, but at least pass the one that we wanted. Oh, here's one that's passing a different one. And we'd sort of take those and rank them all. So this one's got a score of three. This one's got a score of one. Okay, well, we toss that one. That one's obviously not good. And we take these two with a score of three and crossbreed them until we get what we want, which is of course something that passes all test cases. And it works pretty well, actually. They could get software fixes for a lot of bugs. Not everything was easy to solve this way. You had to sort of have the code elsewhere to fix it in order to be able to mutate it in. But it worked well for a lot of things. But I'm not here to tell you about the time it worked. Well, of course, we're talking about algorithmic cheating. So the thing that this did for one of the runs was that your score is based on how many check marks you get, right? How many test cases you pass. Okay, so if I want to be sure of getting a really good score, I could spend a whole lot of time mutating until I pass all those test cases or I could throw out the entire test suite, delete the directory and then look, I passed all the test cases. Yeah, because we're gonna say it, algorithms cheat. And of course, to get it to stop cheating, you can protect the test suite or you could choose to use only programs that don't have the instructions for deleting the test suite or have the test suite run on another machine, put it in a virtual machine. There's 101 ways you could fix it. But cheating is really part of what the algorithm is trying to do. That was a great solution as far as you'd given instructions to Genprog because it not only passed all the test cases, didn't fail any test cases, but it was also super fast because it didn't have to run all those test cases. It was pretty much the optimal solution. And yeah, because algorithms cheat. So, why do algorithms cheat? They're designed for it. A lot of, well, artificial intelligence as a concept has been around probably as long as we've been telling stories to each other. But algorithm, machine learning as we currently use the algorithms and such right now has a lot of its roots in sort of the 50s. And so a lot of them were designed with bigger space constraints than we have now. And so you would do things like make your neural net with only a couple of layers because otherwise it would just get out of hand. And so it's built into a lot of the algorithms we use. It's built into the ideas of the algorithms we use right from the get go. And even now where we maybe don't have that sort of, I can't build a model that's too big constraint, we have other constraints like speed. So if we were allowing Genprog to optimize for performance, which was a thing that we were doing, then sure deleting the test cases gave you a boost in speed. Basically, a lot of algorithms are built on the assumption that taking shortcuts actually will help you win, help you get the best or the perfect score. And that's just the way they are. That's why algorithms cheat. And I'm not sure that you can do much about it in that sense. And this has been true even from very early on in the history of artificial intelligence or particularly artificial life. So when I first started, one of the algorithms I was really excited about was a system called TIERRA. And this was maybe, I think it might have been the first artificial life system, but certainly one of the earliest artificial life systems. It had sort of a primordial soup of resources and a self replicating creature. And so the person who designed TIERRA said he made the first creature 80 bytes long and thought, well, I didn't really optimize this. It should be able to get down to something like 75 bytes. And so he's got a little self replicating creature and he lets it run with some copy function that's introduced some mutations and tries to get it to evolve to a better creature, a smaller creature in this case. And so he turns on the system and he goes off, maybe goes to sleep and the next morning or the next day or whatever, he comes in and looks at the system and he thought he could get from 80 bytes to maybe 75 bytes and he wakes up and he's got a creature that's 22 bytes long. So that was pretty successful. It was pretty cool. As he ran the system and sort of analyzed the stuff, he left this fairly open-ended and you saw a lot of interesting things. So one thing was that his little creatures discovered sex as in they discovered swapping genes, swapping bits of code with each other for more optimal mutations. They discovered parasitism where some of the creatures either took advantage of their peers or they even found one which they described as having sex with the dead where it would pull up genetic code from other creatures that had been killed but not yet reaped because of the way the algorithm worked and how the memory was cleared. And when the rules changed, new cheating appeared. So when he decided to make it so that it wasn't beneficial to be small necessarily and each creature got resources based on how big it was, then of course a creature evolved that lied about its size and got more resources and soon took over the whole little primordial soup. So even in a fairly open-ended system, we see stuff that kind of looks like cheating. I mean, there weren't really rules here, it's not, you can't call it cheating in the traditional sense but it's the same sort of deal, it's a shortcut. And it's not something we see only in artificial life. Our top story of 2020 is of course a virus which is basically nature's favorite cheater or least favorite cheater as we're finding this year. A virus is a little chunk of code that doesn't have its own self-replication and so it coerces your own cells into replicating like crazy to populate. And it's super effective. It's very difficult to get rid of a virus because we're all being reminded this year. So why did this evolve? Pretty much because it works. Basically any system is going to have some sort of cheaters and I'm a computer scientist and a computer security person so we usually talk about hackers and cyber criminals and thieves but you could equally talk about politics. There's lots of cheating in politics, edge cases. You could talk about economics or the tax code. It's something that is sort of inherent to any sort of large system. If there's a benefit to finding edge cases in the rules then someone's gonna find it. So let's go back to those three rules again. So your model is only good as good as your data. Your data is always bad and algorithms cheat. So cheating is easier with data artifacts. That's sort of what we saw in our first example with dogs was that the data artifact was that there was green grass in the background. And even if we removed the green grass we might still have an artifact where there'd be things like the reflection of green grass in the eyes or on the highlights fur or whatever. It wouldn't necessarily work. But as I said, all data has some artifacts and so you're basically, your machine learning algorithm is going to be really good at finding what those are and manipulating them in ways that may be kind of not what you were expecting. So an example that I heard about in one of my grad classes was detection of oil spills. So it's useful to detect an oil spill early. It's much easier to clean up. And it wasn't clear to me from the example whether this was just overabundance of caution or whether they were also concerned that some of the people who cause oil spills may be not as motivated as they should be to report them quickly enough and be prompt. But whatever the reason, we wanna detect oil spills. So we feed in, we've got our satellite image data, we've got a bunch of cases of oil spills, we've got a bunch of pristine coastline and ocean and we put those in and see what we get. So turn the crank, get the machine learning to go and you get some good results. And it looks really great until you look at it closely. And that's when they discovered that because all of the images from satellites had date stamps on them and timestamps, what the algorithm was actually doing was not detecting the shape of the oil spill or the way it reflected or anything about the oil spill at all, it was detecting the days that oil spills had occurred. So all of the test data in their first set was pictures of the same oil spill on a single day. And so the algorithm, you guessed it, algorithms cheat, found the date stamp in the corner and figured out how to detect exactly the data it cared about.  But you have to sort of think about this because this is the sort of problem that's gonna occur with other data. So one that I can think of off the top of my head is medical imaging also has date stamps but has other properties that may or may not be relevant to your task. So for example, in many countries, it's very difficult to keep data on children, especially medical data. So a lot of the data sets that include medical data for say cancer detection are gonna be mostly on adults. And is it possible that your algorithm is going to learn markers that are specific to adults that maybe aren't going to matter in children and make it harder for your algorithm to detect cancer in children? Yeah, that's a possibility. And as we said, a lot of drug tests are done on men exclusively. There's a lot of opportunities for this to go horribly wrong. So a more personal example of something that's not medical is smile detection. So I first encountered a smile detecting camera about 20 years ago at a conference. And it's not an unusual thing for people to have even now.   So things like someone has sneezed, someone has coughed, someone is looking the other way, there's hair in your face, whatever. And so the camera can flash a little warning saying, hey, that might not be the best picture. And so you probably can't see super well through the webcam in my very, very dark workshop here. But I'm half Japanese and I have fairly long eyelashes. And so when I smile, it's very hard to see my eyes. So unsurprisingly, even 20 years ago that camera said, oh, did someone blink? And didn't think any picture of me was good, which is kind of insulted.  It's a Japanese thing, but it was a Japanese made camera. They certainly should have had examples of people who looked more or less like me, right? That seems reasonable. And I don't know whether they didn't because they were using some sort of database that just didn't include that many people or whether the English version of the firmware, I was looking at this camera in Canada, I'm Canadian, whether the Canadian version of this firmware that just didn't have the same training for the smell detection. Yeah, it was still kind of insulting though.  So I've been trying to keep this sort of talk on machine learning pretty light, but it's really easy. We can't really avoid bias even in dog photos. Avoiding bias in data that involves humans is much worse, so much worse. And it's a big problem. One of the examples that, a video that I really enjoyed watching is one that's not machine learning based, but certainly a human data needs to be more broad sense, is the racist soap dispenser. So if you've never seen the video, there's a gentleman who's trying to get soap out of the soap dispenser. And you can hear him laughing because it's not working. So it puts his hand in, nothing happens, puts his hand in, nothing happens, and he laughs and he goes and he grabs a paper towel, puts it on his hand, puts it on the soap dispenser and poof, soap. So as you may have guessed, he was a darker skinned individual. I think the video said he was African. And yeah, the soap dispenser probably didn't have any sort of machine learning involved. It was probably just a simple light sensor and it didn't trigger for darker skin. And I've actually always wondered whether that was a problem because I never can trigger those darn things. Maybe I should start using PipTal. And nobody meant it to be racist, but obviously they didn't test it on a wide enough range of potential users if that came up. And another example that doesn't even involve computers is, so I am 1.6 meters tall, the 5'3 in American. So I'm short. I'm not like the shortest ever, but I'm sort of below average height by enough that it's not great to do things like shop for a car or as I discovered a couple of years ago when we were buying a house, it's really hard to shop for a house because every time I went to the kitchen of especially of newer houses, I would discover that I couldn't reach above the lowest level of the cabinets. So these kitchens would have all this fancy, beautiful cabinetry and only like the bottom six inches was useful to me because I'm too short and they'd put them all too high on the wall. And yeah, that's a thing that probably anyone who's tall or short has experienced if you're outside of what people are expecting, that's a problem. And again, I'm kind of insulted by it. Certainly there's plenty of other short half Asian women around here. I can't be the only one who's looking for a house, but it is what it is. So here's an example that really does use machine learning. So these are pictures that were posted to Twitter a couple of weeks ago. The gentleman on the right-hand side was the one who posted them. He's helping the gentleman on the left figure out why he couldn't use the Zoom's replaced the background saying without it having erased his head. Super inconvenient if you wanted to have backgrounds.  So they tried having sort of a more neutral background. They tried changing the lighting, trying to make sure there's a little more light on his face so you could see his eyes and none of it worked. So after some frustrating time figuring out what the heck was going wrong here, he came to this conclusion and can't read it so well, but it turns out that Zoom has a crappy face detection algorithm that erases black faces and determines that a nice pale globe in the background must be a better face than what should be obvious. So I don't know if it actually works exactly like that. And of course probably neither does he since we don't have the inside of the algorithm, but yeah, algorithms cheat. And from what we know about how algorithms cheat, that's a pretty reasonable assumption that maybe it turned out that they didn't use enough examples of black faces when they did their training and their testing. And so the algorithm rather than trying to detect facial features or head shapes or whatever focused on the wrong thing, which was sort of a bigger contrast between you and a dimmer background, sort of a big white globe was probably the face and should be good enough. Yeah, not ideal, but algorithms cheat. In this case, the cheating comes out as a racial bias and you can imagine that it would come out in other ways. If the algorithm was expecting sort of a face to be all one color, it might have trouble with people who have large birthmarks. If it was expecting two eyes, what happens when it encounters someone who's only got one or is wearing an eye patch? It's 2020, we're all discovering that facial detection works really poorly with face masks on because it uses parts that are now covered. Some of the early stuff couldn't handle things like glare from lenses. Many passport photos require you to take your glasses off and it's not for any reason about the human agents at the border, it's to facilitate machine learning on those things so that you have a game. Look, neutral background, no glasses, try to minimize all of the things you can do that would produce forms of bias in your dataset. So, at least the good news is with face masks, we have lots of images to practice on now, but all of these types of cheating have consequences. So debugging why Zoom backgrounds don't work for you takes time, it's not a zero harm thing. It's okay, it's not apocalyptic or anything, but it often is the case that the people who are stuck debugging these weird behaviors caused by machine learning are people who are minorities, either socially or in that dataset and they're gonna encounter this again and again and again, it's really kind of dangerous, but you can also have more direct danger scenarios. So one of the big uses of machine learning that people are talking about right now is for self-driving cars, so recognizing appropriate traffic situations and navigating through safely. But if your self-driving car has lots of examples of pedestrians standing at the side of the road and figures that, okay, well, it looks like a human is a thing that has a head and two arms and feet and is possibly very short as a toddler or as tall as an adult, that's great. So what happens if a self-driving car decides that someone who is missing a leg is therefore not a human and kills someone? I really hope that we don't have too many cases where people die in order for us to discover the flaws in our data, but it's probably, well, it's probably already happening. It's probably already been happening in medicine for years. And again, I'm trying to keep this light, but medical data is really terrifying and I live in the US now and data on policing is really terrifying. There's a lot of stuff where people are trying to use the data and you're like, well, it's real data so it must be the right solution, but there's a lot of forms of bias that have been introduced before you even got to your real data. And without examining those thoroughly, we're doing very dangerous work.  So this is an image that I saw posted to Twitter last month, I think sometime, and it's very old. And the person who posted it said, if your big data person doesn't recognize this image, then you should get rid of them. And I had a laugh because of course I recognize the image, but this is Dr. Terry's masterclass on machine learning. You should not feel guilty for not knowing things. There's always opportunities to learn. So, and I like this one because it's kind of a funny story in that it really illustrates something. So this picture of a plane is an aggregate of data of planes that had bullet holes. So each one of those red dots is a place where the plane was hit with a bullet. So this is a fighter plane. I think it was World War II-ish. I don't remember the whole details of the story, but they were working to figure out how to make the planes not have so many bullet holes when they came back. So they looked at that data. These are where the bullet holes are. Clearly we should put the armor in those places and then the planes will not have these holes through them all the time. And that seemed pretty reasonable to everyone in the room until one person said, wait, no. We need to put the armor in the places where the dots aren't. Why? Well, if the plane has a bullet hole and comes home, then we have the data. But if it gets hit in one of those white places, clearly something goes catastrophically wrong. The plane blows up. We never see it again. So, you know, and you can sort of see where that might happen on this diagram among the things that don't have bullet holes are the engines. So I love this example because it sort of shows you how with exactly the same data, you can have completely opposite answers to the question, depending on mostly what question you're asking. So are we asking the question of how do we get fewer bullet holes in planes? Or are we asking the question of how do we make sure that more pilots come home safely? And so if you ask the how to make fewer bullet holes, then, you know, in the planes that come back, then you can put the armor right where those dots are. But if you want to keep the planes from blowing up in the first place, then you need to put the armor elsewhere. Now that we've had this discussion about all the hilarious and awkward ways in which algorithms cheat and how much of an impact that can have, you may be asking the question, how do I stop algorithmic cheating? But as I said, I put it on the rules for a reason. I'm not sure you can. Algorithms, cheating is basically inherent in the way we design the algorithms to find the fastest, the best, the most efficient solution. And I don't think there's a way to stop that, but maybe that's the wrong question. So maybe a more tractable, a question that we can really actually work on is how do I get better results? So even if you know that inherently your algorithm is probably gonna use any shortcut it finds, how do you make that work for you? So going back to those three laws, your model is only as good as your data, your data is always bad, algorithms cheat. So the first thing to do is to care deeply about the data. So you have to care about things like image quality, whether your data set of people mostly has pretty people, whether it has people of only some skin colors, whether it has people without missing limbs or birthmarks, whether it's your data's already been filtered through some lens of good. So for example, your Google image search is often based on PageRank. Although I gave the last law of algorithms cheat taught billing in this presentation, there's a reason that there are three laws and the first two are about data. Trying to figure out what is good data is really fundamental to getting the machine learning to give you the results that are actually useful to you. And I swear this is the screenshot that I see most often in Python presentations. It's dangerous to go alone, take this. And I think it's because programmers are just like really determined to go things alone and be able to solve entire technical problems by themselves. Maybe it's because we've built up a model where that worked for us often enough that it's fine. But in machine learning, don't do that, please don't do that. This is really something that's better as a team sport. So find domain experts. If you're working with medical data, work with a doctor. If you're working with ecological data, work with the right biologists, whatever. If you can't find that expert because it's weird data or you just don't have access to them, find people who are used to dealing with data. Statisticians, psychologists, biologists, anyone who spends a lot of time looking at bias in data is going to understand this probably better than we are as a computer scientist, unless you're fortunate enough to have some background in other fields. Really, you want a whole team to be doing this. And you should be a little bit suspicious when you see stuff that's like coming out of a grand new startup that has like five programmers and no data scientists and no domain experts and doesn't say they're collaborating with anyone. Maybe that's not really real results and maybe you should not be trusting that. And the data will help a lot, but there's also other things you can do. So there are many algorithms. You can choose one that has a better path that does whatever way it cheats is more suitable for your data. And if it chooses a bad path, as we saw with the dogs, you can always go and retrain and punish. We do this sort of thing all the time and we do this sort of thing in the real world as well.  You move the desks harder apart. Nowadays we do that just so we don't cough on each other, but you also do it so they can't see each other's papers. You might have a proctor watching the room or a camera and you penalize them if they do get caught so that it's not worth the risk to people. And we do this for code as well. Anyone who has a open source project often has continuous integration tests so that when people give you code that doesn't comply with PEP 8 or give you code that breaks other parts of your pro, your entire test suite, then you can just reject it out of hand. And in order to get a good solution, they have to sort of play by those rules. One that comes up for my field is bug bounties. So it's easy to sell a computer security bug in theory on the black market to people, but if you have a bug bounty program then people can just go to you and get paid and they don't have to worry about any of that and they get kudos for it and it's good for the resume. And so we try to encourage people to do the right thing and not exploit the issues that they found. And so in the name of Sailor Moon, in the name of the Moon, I'll punish you. It is totally fair to punish your algorithms and make sure that they are on the path that you feel is the most useful for what you're doing. So the other thing, of course, is that iteration is good. I think iteration is really built into machine learning, but I don't think it's built into sort of the popular culture around machine learning, but so you iterate, you tweak. You didn't learn Python in and get it all right immediately. I know I'm still learning, especially this year because now that we've been able to shut down 2.7, I finally get to learn how to use F strings properly, but you didn't get it right the first time and tweaking and adjusting is really part of what we do. So sometimes you'll have to throw the model out and that's just the way it is, that's fine. And sometimes you'll be able to retrain and rework. So how do I take advantage of algorithmic cheating? I'm a security person, so I always have two questions when I hear about cheating. One is how do I stop it? And two is how do I take advantage of it? So first, the easy answer. We've just said that we need to be aware of sources of bias in our data and we've said that algorithms cheat and use biases in our data. Look, these are two things that can go right together. You can use your cheating algorithms or a different cheating algorithm to help you suss out things that are potential shortcuts and see whether they're real shortcuts or whether they're sources of bias. It can help you figure out where you're lacking in your data or figure out what things need to be excluded or figure out a lot of other things. And I also wanna note that cheating doesn't have to be a bad thing. Cheating may be what you want. I mean, there's a reason we built it into the algorithms. So this is a picture of the DARPA cyber grand challenge that ran at the DEF CON hacking conference. And in this case, they were using algorithms and programs to run a capture the flag contrast, trying to hack into things, trying to patch things and stay safe. And in this case, if you're trying to patch something, it's sometimes really useful to get a patch that, okay, it's not perfect, but it's good enough to stop the known attack and give you enough time to produce something better in behind the scenes. So I say this as a reminder that cheating is sometimes, maybe not a perfect solution, but it's the solution you have. By and large, you wouldn't be using machine learning on something where you had a perfect solution.  So sometimes that heuristic is good enough as long as you're careful about how you deploy it. And a quick shout out to my security folk. If you wanna sort of understand cheating and be able to predict it more accurately, computer security is the field for you. So much like machine learning, computer security has lots of tutorials and big contests. I mean, the DARPA one is obviously sort of an expert level one, but there's lots of capture the flags and security education that's aimed at beginners. And a lot of these things are just plain web games. So you can just play by yourself or again, it's a lot more fun with a friend. Work together and learn a little bit. And really what the field of computer security does is we take beautiful, perfect models of how the world works and then try to find ways to subvert them in ways that are unexpected and beneficial to the attacker or equally subvert them in ways that are not beneficial to the attacker. So it's, I think that machine learning and security go really well together. And nobody's ever gonna be able to convince me otherwise, but it's a fun place to start. The last thing I really wanted to focus on today is being aware of the superficial truth. So machine learning is sort of telling you about the status quo. It's telling you about the data you already have and it's lazy. It's gonna give you the answer at things you wanna hear. And so if your bias and the data's bias are sort of lined up, it's very easy for you to look at those results without looking at how they got there. But to look at the final results and say, oh yeah, that totally makes sense, right? I fed it some data saying that the sky is blue, it told me the sky is blue, we're done. And so it's be suspicious when it seems too perfect or that really it's one of those times where it's great to have a larger team. So there's more eyes on it who might recognize that yeah, that's maybe not the right, the best thing. So going back to those three rules again, if your models is only as good as your data, then you should try to make careful and intentional data choices. If your data is always bad, you can try to actively seek out those biases and flaws so you can understand them, characterize them and maybe deal with them in ways that are more appropriate than just whatever the machine decides is easiest. And algorithms cheat. So don't be afraid to punish them, to rework things, to focus specifically on areas of bias and always check the work. It's very easy to end up with a situation where what you get looks right, but how you get there is not so right. So even if you're never going to do machine learning, what I want to remember to you is that it isn't a magic box where you turn the crank and you get insight, it's a magic box where you turn the crank and sometimes you get green dogs. So it's not really, you don't necessarily get insight until you look at the results. And it's very easy for especially the media to characterize machine learning as like getting expert advice. So you go to the algorithm and it's like a magical oracle that tells you the perfect solution to everything given all of the data, the giant big data that we've looked at and it's gonna be awesome. But it's not, that's not really what machine algorithms are like. They're more like the person who looked at, said, hey, the government has told me that they're going to pay for dead snakes as part of their campaign to eradicate snakes. What they wanted was people to look at that and say, oh, I should kill more snakes. But machine learning is more like the guy who said, oh, I could kill snakes or I could start breeding snakes and then I'd make a lot more money. So yeah, be a little suspicious of anything that claims it's perfect. And so in conclusion, go forth, have fun, do some machine learning, experiment with it. And when you're observing machine learning results, remember my three rules. Your model is only as good as your data, your data is always bad and algorithms cheat. And really, when you're going to go do machine learning, make sure that the machine isn't the only one who learns something. Thanks very much. So I guess I'm gonna take questions, but I don't think I can actually hear the moderator, so I guess I'm gonna have to read them. Yeah, so. So what's the best way to go about generating synthetic data? It depends. It depends on what synthetic data you need. I think that's probably a question that there are entire textbooks written about. And you pretty much, you have to experiment and you have to see what works and what doesn't for your particular application and for your particular algorithms that you're using. What I do to generate data for a neural net is probably gonna be different than I would for an A-life algorithm. So I don't think there's one answer. And in fact, one of the things that I thought about putting in the presentation but hadn't was the no-free lunch theorem, which is a fundamental part of the A-life community, which is that there's not one algorithm that's actually going to work for everything. Like I know we're all like super excited about a neural net, like it's the 70s again, but it's probably not the perfect algorithm for everything. And the same is true for generating data. I don't think this is the best way. Next question is, how should one prepare against unknown pitfalls that you're not aware of when building or designing the system? And that's iterate. Be prepared to iterate as you learn. You're gonna learn. Hopefully you're gonna learn before anyone dies. Do a lot of testing, be as broad as you can in that and just be prepared. Just expect that there are going to be pitfalls and build them into your timelines and build them into your testing and your models. When learning, what learning track should a beginner, should a beginner in machine learning follow in order to get good at it, especially considering ethical and bias aspect of it? So I don't know, because of course, I learned this so long ago that I haven't really looked at the beginner's tracks and unlike in computer security where I train people on my job all the time, I don't train people in machine learning normally. So I don't know the answer to that. But I will tell you that the best sources I've seen, especially about ethical and bias data, come from people who are directly affected by them. So you probably don't want to go to people who are super popular only to learn about how bias works. What you wanna do is you wanna talk to the disabled community, you wanna talk to people of color, whatever minorities you have in your community, women maybe, talk to people who are not the standard people in that field. And that's where you're gonna get the biggest insights, the fastest. And a lot of people, because they care so passionately that this talk about it a lot. And so there's lots of things out there. So just do a little bit more than just searching through the first Google results from machine learning, try searching for machine learning bias and then a community life name, machine learning bias and disability, for example. Yeah, so that's all we have questions for you. Thank you so much for having me. So that was really a very impressive talk from you. Thank you so much, you'll have to... Thank you so much for having you, have a good day.


What's up everybody, Jason here for JaspiersCaseBrace.com 2022 Pinini Illuminance Football just sold out This is a four box break, cricket season number three, and again guys This has its own break crater promo tied into it itself So all you had to do is buy two teams. You've got two teams you get entries into this giveaway We're gonna give away $250 and of course two winners of 125 each the top two names So what we'll do here is that at the end of the break we'll Alphatize the customer names. We'll see who grab two teams or more We'll put them in a list randomizer and the top two in 125 back each now Of course if you did buy spots in these breaks right now after Joe went off air at 10 o'clock or 11 o'clock last night To 3 o'clock Pacific, of course, it's only 138 You're gonna get entries into this giveaway It was only for breaks and spots that were purchased after Joe went off at 11 to 3 o'clock today All right, so once Joe goes on at 3 He'll have a running list like mine will randomize all the names that are in this list here and then top What is it? Top five names win $300 back no matter what this is gonna run So the more spots you purchase before 3 o'clock the more entries you get So there you go guys you guys will also have that chance as well there for customers, of course I only bought in today and here we go So again actually number three is gonna be the first four boxes of the case so luminance football Has 12 boxes picker team one and two is in a filler so number three is actually gonna be the first four So the basic with the remaining eight will be part of number one and two whenever that does sell out Yeah, I know Ryan didn't post a checklist yet But obviously I think Malik Willis will be the big rookie you're chasing for the Titans And I think he should be in here So and again four boxes on the left four boxes in the middle four boxes on the right Let's see if we can get a little number generated here if we roll a one two We're gonna go with the left three four the middle five six right Roll it to six Six so that means we're gonna go one two three four five six so basically these ones here Will be for one and two one slash two One slash two and then we'll decide that later once we sell that out So three autographs one more really car guys All right, here we go First one here is a AJ Dylan to 149 We got a Rogers intensity relic nice Kenny Pig it that dynamic So of course with no checklist out it'll go to the teams are currently on teams It played for the longest of course, and we got a Rookie here for luminance that is a New York Giants actually does tell you the team sometimes Evan Neil With a Trayvon Walker, they go out of 100. That's the number one overall pick right there for the Jaguars So Jacksonville that's gonna be going to Matthew Slade And this looks like a really cool car The forest Buckner we got Trey Lance to 249 Jacobi Myers, that's number tonight in on Lawrence it looks like really cool right there names of the game Jones jr. We have a Jack cone, and then we got a Thornton to 349 Taekwon Thornton, and that'll be Patriots Karen Steele and we got a she She's He came back out right there All right next one We have a out of 99 Buffalo Bills. That is the fun digs Derrick Stingley jr. There you go nice drop picker a top picker there Houston Texans You got a sheesh right there CD lamb We have a vealist Jones jr. And then that Houston Texans would be Jerry We're going to Jerry. I should say Trey Kwan Smith number to 49 for the Saints New Orleans Saints that's going to Jeff Henn. I've a DJ more luminosity Something's interesting really nice actually James Robinson We got a Rashad Bateman to 249 We got a Khalil Shakur to 349 That is Buffalo Bills That is going to Corey Got a Dak Prescott right here take one Thornton and Brett Farr Aaron Rodgers really With a Sam Howell halfway through to 149 With a Mack Jones relic for the Patriots nice little Malik Willis By that dynamic right? That's going to the Tennessee Titans Ryan Harold We have a Nick Chubb to 249 and Desmond Ritter Autograph or a little little sparkles there speckled year one autographs. That's on car Which of course Desmond Ritter was drafted by the Atlanta Falcons on a Brandon Little Joe Burrow here. We have a Tyler baddie Dorsey leavens light speed ink Packers having a good break chateau with that one We got a Jermart Chase. We got a dynamic 50 of 50. That's Josh Allen We have to 249 Kyler Gordon and Lewis For the Minnesota Vikings to 349 a little savage TJ Watt Yeah Packers having a great break Patriots also having a pretty good break too actually, right? All right, last one here guys. So again, this would be basically the last This would be the first four boxes of the case. So if we were to sell out number four four five and six are actually part of The same case. So if you guys wanted to sell out four five and six That'll be from our fresh case as well number four Of course of that one first that'll be the first four and then five and six would be the next two But basically number one and two are tied into a pack filler. So Those won't sell out until we sell out that filler. All right, here we go. We have a Number to 249 that's a boy mate Eli Mitchell relic. We have a she Doesn't ever Whoa, don't look at that. Don't look at that Got some points coming up their car And then everyone's gonna have a shot at these points here That's 600 points and then we have a little tealaw Like a Parsons to 249 with a Sam Hal for Washington, that's actually a number to ten Eight of ten Sam Hal It's actually pretty nice That's gonna go to the Washington commanders Han with that one We have a Patrick Mahomes dynamic We should have one more hit right here guys We got a out of 35 for Baltimore Tyler baddie.  So We got these first four here in the books for boxes here We got a Desmond Ritter got a nice little Malik Willis insert there Derek Stingley Sam Hal and then of course a lot of numbered cards including a lot of nice inserts that'll be top-liverted as well So a lot of stuff going on of course all cars ship as well You got that as well and we had a 600 points from 600 points So we'll give that out to one person in the break. It's about two little randomizers here. So dice roller we have two lists First one everybody gets a shot So we're just gonna randomize all the customer or all the teams and then the second list would be for just customers for the break credit promo so Andy Had to That's one entry Brandon had to that's one entry Chat only with one. So that's only one inch. No entry. Sorry. Same thing with Charles with my eagles Chris with only one Corey with two. So that's an entry Hand with two Jeff with two. So that's an entry each for both of you guys Jeremy Harden with just one Jerry with two That's an entry Karen with just one so Matthew Slade that's an entry for you because you have two Nico with two Patrick Davis with two. So that's an entry each Robert with two Ryan Harrell with two sets an entry each as well And then Sam with just one team Tanner with two Timothy with two So that's an entry each for both of you guys. So it's actually pretty good odds instead of one and sixteen It's gonna be one and thirteen so much better odds and then it's gonna be two winners of 125 each So here we go dice roller for both lists randomizers we got a three and a two five times top two get 125 back each one two three four and It was a five Oh five times. Yes, Brandon. You got a 125 and Timothy with 125 So I'll send that out to you guys right now at the end of this video And let's go five times here for the 600 points number one get 600 points one two three four Five Miami Dolphins owner, which is Robert Dauper. So Robert you're gonna get 600 points Going to you and there you go guys appreciate it number deluminance number four It's from a fresh case and that is our next closest break So that is down to seven left if you guys want to run that back jossby's case breaks.com


Hi, and welcome to program analysis. In this lecture, we will look at symbolic and concocted execution, which are techniques for generating inputs to execute a program without needing a human who is providing these inputs. In contrast to the techniques that we've seen in the last lecture, which was on random testing and fuzzing, we'll now look into a white box test generation technique, which actually looks into the program and tries to analyze this program in some detail in order to find inputs that will execute some new behavior in the program. Here's an overview of what we're going to do in this lecture. So the lecture consists of four videos. Now we're in the first one. And in this first video, I will give an introduction of what symbolic execution actually is and give an overview of what I call classical symbolic execution, which is kind of the pure form of doing symbolic execution. Then we will talk a little bit about what challenges this pure form of symbolic execution is facing. And look at one approach called concocted testing that addresses some of these challenges in an effective way. And then finally, in the last video, we will have a quick look into some of the larger scale applications of these techniques and practice. Everything I'm saying here is based on research papers. And in particular, I can recommend the three papers that you see down here. So if you're interested in some more details on the techniques that I'm describing here, you should have a look at these papers that describe them in more detail and also provide a lot of more examples and empirical results than I do here. Let's start by having a look at what symbolic execution actually is. Symbolic execution is a technique to reason about the behavior of a program by kind of executing it with so-called symbolic values. These symbolic values can be thought of as placeholders for the actual values, which may be associated with some information of what the actual values must look like, but they are not as concrete as the normal input value study would feed into a program. So instead of feeding maybe three and five and 26 into a program as an input, we will reason about these inputs symbolically and just give them a symbol. And then while we reason about different executions of the program, impose more and more constraints on these values. This idea of symbolic execution is pretty old, at least in terms of what alt means in computer science, because it has been proposed by King and then refined a little later by Laurie Clark in the 80s. And then it has been around for quite a while without really being that popular, but around 2005 it became popular and practical again because of some advances in a different subfield of computer science, namely advances in constraint solving. Specifically, there have been very impressive advances in SMT solving and we'll see that this is actually a critical component of this whole idea of symbolic execution. So whenever an SMT solver gets much faster, symbolic execution suddenly also works much better. And around 2005, the point was reached where the SMT solvers were fast enough to make symbolic execution practical and then a lot of people got interested in this pretty old idea again and nowadays, it's again a topic that draws a lot of attention. So before looking into the details of how symbolic execution works, let's just illustrate the idea of this technique using an example. The example is what you see here. So it's a function which happens to be written in JavaScript, but the language doesn't really matter. Any imperative language would work. And this function is taking three arguments, ABC, which are the inputs to this program. So program here means a function. And then in the function itself, we have three local variables X, Y, Z, which are initialized to zero. Then we have a couple of conditions that are checked on the way, which are always conditions on the inputs, so on A, B and C. And depending on these conditions, we may, for example, take this path here or this branch here where we are assigning minus two to X, or we may go into this branch here where inside we are checking another condition which may lead us into this assignment and that assignment. And at the end, there's this assertion which is checking whether the sum of X, Y and Z is not equal to three. And the question is, well, is it actually possible that this assertion is violated? So is there some path through this code where X, Y and Z happens to be, yeah, if you sum them up, happens to be three. Before looking into the symbolic execution of this function, let's at first have a look at a concrete execution of this piece of code, which is nothing really surprising. It's exactly what you would expect to happen when you concretely execute this piece of code. And in this concrete execution, because it's concrete, we need to have concrete values for all the inputs. So for this example, let's assume that A and B and C are all equal to one. So these are our concrete inputs. And then the program is executing and starts by assigning values to these local variables X, Y and Z. So, and these are all initialized to zero. Then we are reaching the first if, which checks whether A is true. A is one, one will be converted into the Boolean true. So the first condition is true and therefore we are taking this first branch where we are now assigning minus two to X. Then we are reaching the second branch where we check whether B is smaller than five. B is one, which is smaller than five. So this is also true, which means we are entering this branch and we'll check the nested if, which is checking that not A and C is true, which happens to be false. Yeah, because A is one, so A is true, which means not A is false. So this whole condition is also false. So we are not assigning anything to Y, but we still have this other statement in the outer branch where we are assigning two to Z. And then we are reaching our assertion where we can now sum up our values X, Y and Z where we find that we have minus two plus zero plus two. And this happens to be zero, which is not equal to three. And that means here our assertion check is successful and we have not found a violation of this assertion. So the concrete execution wasn't really surprising because you've concretely executed programs a lot of times. Let's now have a look at how the symbolic execution of this piece of code will look like. So in the symbolic execution, we again start with the input values, but this time we are not assigning concrete values to them, but we are assigning so-called symbolic values to them. So we start by saying that A is A zero where A zero is the symbolic value that represents the initial value of A. So basically the input that is given to this function and we do the same for B and C by also assigning B zero and C zero to them. So these values here are called symbolic values. Given these symbolic inputs, we are now starting the execution of the program and as before, we will now assign these initial values of zero to X, Y and Z. Next, we are reaching this first if and now in contrast to the concrete execution where we are taking one of the branches, but not the other one, we will now consider both possible behaviors because we wanna symbolically execute this program and while doing this, we will consider all possible behaviors of the program. So we reach this branching point where we are checking a condition and this condition is A in the source code. A currently has the value A zero, so the initial symbolic input that is given to the program. So what we're checking here is whether A zero is true or false. This check can have two outcomes, either it's true or it's false and then depending on whether the condition is true or false, we will or will not execute this assignment of minus two to X. So if it is true, then on this edge here, we are executing this assignment, whereas on the false branch, we do not execute it. Now, no matter whether we have executed this assignment or not, the next statement that we will reach in this program is the second if where we are checking whether B is smaller than five. If we look at the value that B currently has, we see that it has the symbolic value B zero. So actually this check means that we are checking whether B zero is smaller than five and this happens both in the case where we have taken the first branch and in the case where we have not taken this first branch. And again, because this is a Boolean check, there are two possible outcomes, true and false. In the case where this check is false, we are at the end of the program because apart from the assertion statement, which I'm omitting here now, nothing will happen. So basically we will not write anything else here and here because we are at the end of the program if this second if is false. If this check returns true, then we are going into the nested if, which means we will have to do another check and now expressing the condition of this other check. Again, in terms of the symbolic values means that we are checking that not A zero and C zero. And please note that I'm now switching to this logic notation instead of the programming language notation and we'll see why I do this. The reason is basically that we wanna feed these logical formulas into a constraint solver later on. So in the case that this check is true, so again we have these two possible branches here, true and false. And in case this check is true, we will execute this assignment of one to Y and then afterwards we'll have this second assignment of two to Z. And in case the check returns false, we do not perform the first assignment, but we do perform the second one. So in that case, this is the statement that follows. And the same happens essentially in the other execution path, which we have here on the right. So if this check here returns true, then we'll also check whether not A zero and C zero, which again may be true or false. And similar to the other side, if it's true, we will perform these two assignments and if that check returns false, we will only do this one assignment here. Now this tree that I've drawn here, this is actually called an execution tree because it represents all possible executions of this piece of code. And now one other thing we can do is to look at the different conditions that must hold in order for us to take a particular path through this program. And we can do this by basically starting at a root and then going down to one of the leaves and concatenating all the conditions that we see on a wave with a logical end. So let's do this here for this first path that at the end ends here. So in this case, what we'll see is that the condition for taking this path is that A zero is true and B zero smaller than five is true and not A zero, oops, and C zero is true. And now if you look at this condition closely, you'll see that there's a contradiction in it because it can't be that A zero and not A zero is true, which essentially means that by just looking at these conditions, we actually know that this path is infeasible. So it's not possible to actually execute this path with any input that the program could get. Now we can do the same for all the other paths and basically write down the conditions that must be true to take this particular path for each of those. So let's do this also for the second path for which we need to have A zero and B zero smaller than five and now I need to negate this condition up here. So this will be not not A zero and C zero. Now we can do the same for this path, for example. So we will take that path if A zero is true and now I need to negate this condition here, B zero is larger or equal than five. The same can be done for the other path on the right hand side of the tree. So for example, here we would have that not A zero because we are taking the false branch of this conditional here and B zero is smaller than five because the second check returns true and then because the last check also returns true, it's and not A zero and C zero. For this one down here, it's a little different. So here we have A zero and B zero is smaller than five and not not A zero and C zero. And finally for the rightmost path, this one will be executed if we have not A zero and B zero is greater or equal to five because that's the negation of this second check. Now in addition to the conditions that we now know for taking a particular path, we can now also for each of these paths look at the values that our local variables will have and we can compare these values to what is actually requested in this assertion. And if we do this, then what we'll see is that there actually is a path where we can violate the assertion and this is the one that leads us down here because if we take this path, Z will be two, Y will be one and X will be zero, which means our sum is zero plus one plus two, oops. And this happens to be equal to three, which means that our assertion is actually violated. And now because we also see from the condition that this condition can be fulfilled, so there are values for A zero, B zero and C zero, we actually know that there is an input to this function which will violate our assertion. All right, so now you've seen this idea of an execution tree on an example, let me now define what this execution tree actually is. So as the name says, it's a tree and more specifically it's a binary tree. So basically every node has exactly two children. And what this execution tree is representing is the set of all possible execution paths through a given piece of code. In this tree, we have nodes and edges and the nodes in this case represent conditional statements. So for every branching point in the program, we have one node that represents the conditional that is checked at this branching point. And the edges of the node of the tree represent the execution of a sequence of non-conditional statements. So basically everything that happens in between these branching points. And then if you look at the path in this tree, then a path that starts at the root of the tree and goes down to one of the leaves represents an equivalence class of inputs that will lead the program exactly along the same sequence of statements. So as a little quiz or maybe homework for you, I have another piece of code here and I would like to invite you to maybe stop the video at this point and just draw the execution tree for this given function yourself. Because it's the best way to basically check whether you've understood this idea of an execution tree. And then kind of as a check sum, the question for you is how many nodes and edges does this execution tree actually have? So please stop the video here and don't continue until you've done it. And then once you have done it, I will just let you know that the solution for this check sum is that there are three nodes and seven edges in this graph. I will not give you the concrete execution tree, but you're welcome to share it, for example, through Ilias once you've done it to double check whether your solution is correct. Apart from the execution tree, we've seen another concept in this example that I've shown. And this was this concept of symbolic values and of a symbolic state of the program. So the idea behind these symbolic values and a symbolic state is that all values that are unknown, so basically all inputs that are given to a piece of code are kept symbolically. So everything that comes, for example, from the user or is read from a file, so where we do not really know by just looking at the source code what the value will be is kept symbolically and is represented as a symbolic value. And then while the program is executing on the symbolic values, we have this idea of a symbolic state which maps the variables in the program to some combination of the symbolic values which represents the state that these variables will have when the program is executing. So looking at this example down here where we have just a simple function that takes two arguments X and Y and then does some computation on these arguments, we would consider the input values X and Y as something that needs to be handled as a symbolic value. So we would call the initial values that X and Y are having, X0 and Y0. And then we would, for example, do this computation here which adds these two symbolic values and writes them to this local variable Z. And we would represent the value of this local variable Z as a symbolic state which in this case would be the sum of X0 and Y0. Just note that X and X0 are not the same. So if somewhere in here, for example, we would now assign some other value to X which we could, of course, do, let's say X plus one, then the symbolic state of X would be X0 plus one. So X and X0 do not have to be the same but X0 is just the initial value of a symbolic input. Given this symbolic representation of the inputs and of the state of the program you can now reason about the conditions that must hold if a particular path in the program is executed and this is done using so-called path conditions. So that's again a concept you have already seen in the example. So what I'm going to do here is just explain it and define it in a more general way. So a path condition is essentially a quantifier-free formula over the symbolic inputs that represents all the branch decisions that have been taken up to the point in the program where we currently are. So for example, if you look again at this piece of code here then there is this condition that is checked here and the question is what condition must hold for us if we execute these dot, dot, dot statements here. And the answer is that the condition here would be that X0 plus Y0 must be larger than zero simply because the check that we do here is on Z and Z as we've seen on the previous slide is the symbolic state that is represented as X0 plus Y0. And here we are checking whether Z is larger than zero so we get this path condition. So basically this is a formula that tells us what must hold in order to reach this branch down here. So now the nice property of these path conditions is that they are logical formulas and we can check whether a logical formula is actually satisfiable or not. And what this means is that we can check whether a path is actually feasible so whether it can be executed or not by just checking if the path condition is satisfiable. This could be in principle be done by hand but of course you wanna automate this whole process of automatically testing a program through symbolic execution. So we need another piece of software that does this satisfiability check for us and this piece of software is called an SMT or a set solver. Set here simply stands for satisfiability because this is essentially what these solvers are checking. But in practice you often want to not just reason about purely logical formulas but also maybe reason about integers or strings in a program. And therefore most people use so-called SMT solvers which means satisfiability modulo theory where theory just means that the solver also knows something beyond pure logic. For example, it knows something about integers or strings. There are many of these SMT or set solvers out there. Z3 and Gizes and STP are just a few that are popular and if you wanna try out some of them it's they are relatively easy to set up and you can basically feed some logical formulas into them and see if these formulas are satisfiable. In addition to telling you whether a formula is satisfiable what these solvers also do is to provide a concrete solution for the case that a formula is satisfiable and concrete solution essentially means that for all the symbolic values you'll get a concrete value that if you put it into the symbolic value will make the entire formula evaluate to true. So let's illustrate these ideas just with two examples. So let's say we are giving this formula here to a solver where we say, hey A0 plus B0 must be larger than one. Then it will tell you, well, of course, that's satisfiable. There is a way to make this formula true and this is, for example, the solution where A0 is equal to one and B0 is also equal to one. Of course, there's more than one solution but this is just one solution that the solver will give you. The second example is this one down here where we have this slightly more complex logical formula where we're saying A0 plus B0 must be smaller than zero and at the same time we want A0 minus one to be larger than five and B0 should be larger than zero. And now if you look closely at this example, you can figure out that there's actually no way of having A0 and B0 such that this entire formula is true and the solver will also find this for you and will tell you that this formula is unsatisfiable so there is no concrete solution to make this formula true. So now you've seen all these ideas of an execution tree and symbolic representation of inputs and the state of a program and then this solver-based way of reasoning about execution. So you may wonder, well, why do we need all of this? So what are the applications of this symbolic execution? And there are many, many applications actually and the general goal of all of them is to reason about the behavior of a program by not just executing the program but by simultaneously reasoning about different paths that might be executed in this program. This has a couple of basic applications which is what we'll mostly focus on here in this lecture. For example, you can use it to detect infeasible paths so you can rule out that particular path in the program can actually be executed and even if an assertion would be violated if you would execute this path, if you see from the path condition that it's impossible to actually execute that path, then it doesn't really matter. And then as we'll see, you can also use this to generate new test inputs. So because the solver can give you a concrete solution for a particular path condition, you can basically ask the solver, hey, what would be concrete inputs to trigger this path and the solver will tell you. And this way you're basically generating new test inputs that are guaranteed to take a particular path. And then by doing all of this, you can basically use symbolic execution to find bugs and also vulnerabilities by encoding what would represent a bug, for example, as an assertion and then using this idea of symbolic execution and constraint solving to find inputs that would violate an assertion. And this then of course means that you've found a bug. Beyond these basic applications, which is what most people use symbolic execution for, you can use this general idea of reasoning about the behavior of a program for other applications as well. So for example, there's work on generating program invariance based on symbolic execution, where you basically wanna find out properties that must hold at particular points in a program. You can also try to prove that two pieces of code are equivalent. This is an inherently hard problem, but with symbolic execution, you can at least in some cases do this. It's also pretty useful for debugging. So if you have a bug and you want to find out when and why this bug is triggered, you can basically try to encode the conditions that are triggering the bug through symbolic execution. And this can then also, for example, guide something called automated program repair, where an automated technique tries to find a way to change the code in order to fix the bug. So here you would basically know that if this condition holds, the program is in a buggy state. So let's change the code so that it's impossible to reach this particular condition while still maintaining the behavior that is triggered when other paths of the program are executed. All right, and this is already the end of video number one in this lecture on symbolic and concording execution. So we've now looked at classical symbolic execution and you've seen some examples of how this works. And you've also learned about the underlying concepts like the execution tree, the path conditions, and this idea of a constraint solver in order to find inputs that make us take a particular path in the program. In the next videos, we will look into some problems of this overall idea and then we'll also have a look at how these problems can be addressed. Thank you very much for listening and see you next time.