WEBVTT 00:00:00.000 --> 00:00:04.000 Absolutely as well. Good morning, everybody, as you may have heard. 00:00:04.000 --> 00:00:00.000 Hmm! 00:00:00.000 --> 00:00:12.000 My name is Manishh Parasher. I'm the office director for the office, advanced cyber infrastructure within the size directorate, and it's my honor and pleasure to introduce our speaker today. 00:00:12.000 --> 00:00:24.000 Professor Stephanie Forrest. Stephanie is professor of Computer science at Arizona State University, where she directs the Biodesign Center for biocomputation, security and society. 00:00:24.000 --> 00:00:34.000 Our research focuses on the intersection of biology and computation, including cybersecurity, soft venture, and biological modeling. 00:00:34.000 --> 00:00:38.000 She's a member of the Santa Fe Institute. 00:00:38.000 --> 00:00:47.000 External faculty, and served at the Us. Department of State as a senior science advisor for cyber policy. 00:00:47.000 --> 00:00:47.000 She has a BA. From St. John's College, and an Msn. Phd. 00:00:47.000 --> 00:00:56.000 From University of Michigan Stephanie has received a number for one, including the 2,023. 00:00:56.000 --> 00:01:16.000 I triple computationally, intelligence, pioneer award the 2,020 test of time award from the IP security and privacy Symposium, the 2019 most influential paper, one from the International Conference on Software Engineering and the Acm to Aaa Alan Neville Award in 2,000 00:01:16.000 --> 00:01:20.000 and 11. She also has the Nsf. President to investigate, Award. 00:01:20.000 --> 00:01:24.000 She is a felified triple E, and a member of the Computing Research Association. 00:01:24.000 --> 00:01:29.000 Board of directors. Where she chairs. It's Government Affairs Committee. 00:01:29.000 --> 00:01:28.000 So without any further delay let me hand it over to you, Stephanie. 00:01:28.000 --> 00:01:34.000 Over to you. 00:01:34.000 --> 00:01:39.000 Well, thank you so much for inviting me here today, and for that kind introduction today, I want to speak about how computing has become more biological over time and how. 00:01:39.000 --> 00:01:54.000 Looking at computation through the biological lens, can help us build better computer systems and understand the ones we have. 00:01:54.000 --> 00:01:59.000 Except now my slides are not advancing just a minute. 00:01:59.000 --> 00:02:17.000 Why is that? There we go first? However, I was asked to say a few words at the beginning about my personal story, which, needless to say, has many threads, so I chose to focus on my intellectual story, which really began at St. 00:02:17.000 --> 00:02:36.000 John's College, where I spent 4 years reading the great books in math and science, as well as in literature and philosophy, and wrote my senior thesis Girdel's famous incompleteness and undecidability theorems, and that let me kind of throw a backdoor 00:02:36.000 --> 00:02:38.000 to the University of Michigan and Phd. 00:02:38.000 --> 00:03:01.000 In computer science, the department there at the time was also very interdisciplinary, and I think these 2 experiences really being steeped in interdisciplinary thinking, have set me on the path that I'm still on today, after receiving my Phd I landed at the 00:03:01.000 --> 00:03:18.000 after, a tour in Silicon Valley, I landed at the center for nonlinear studies in Los Alamos, where I was surrounded by physicists studying nonlinear dynamical systems, and I started to think about computation from a dynamical systems. 00:03:18.000 --> 00:03:39.000 Perspective and it was there that I was really introduced to the Santa Fe Institute, which has become, I have to say, my intellectual home and home base for the ever since, and I still spend a lot of time at the Institute, and learn a huge amount every time I visit I kind of by 00:03:39.000 --> 00:03:47.000 accident fell into this professor position at the University of New Mexico, and that's where I came up through the ranks. 00:03:47.000 --> 00:03:54.000 It was. It is a computer science department, a very, also very interdisciplinary, unique department. 00:03:54.000 --> 00:04:13.000 And you know, like made it all the way up to I think, distinguished professor, and I was department chair and did all of that, and ultimately moved one State to the West to Arizona State, which is from the top down relentlessly interdisciplinary so 00:04:13.000 --> 00:04:31.000 I've had this great fortune in my career to land in all these different institutions, that each have a different take on interdisciplinary thought, and they have all made me part of who I am today. 00:04:31.000 --> 00:04:34.000 And the other, I'd say, big impact on my career. 00:04:34.000 --> 00:04:47.000 I have to say, was the National Science Foundation, and it's really a privilege to be here today to tell you first of all to acknowledge all the support that I've had. 00:04:47.000 --> 00:04:58.000 But then to tell you some of what I've done with that support, and I'd say the biggest impact award I received was the first one, and I don't know if you can see on your screen this letter. 00:04:58.000 --> 00:05:03.000 But it was looking back on in a very kind of unusual letter. 00:05:03.000 --> 00:05:25.000 But it it LED me to believe that I had won the presidential young investigator reward which for those of you who don't remember the details, gave me 5 years of essentially unrestricted, very generous funding, and that allows me to take what I have to say at the time was a pretty 00:05:25.000 --> 00:05:26.000 fuzzy vision, and turn it into, turn it into a real research program. 00:05:26.000 --> 00:05:39.000 And so I just I can't emphasize too much how much difference that wanna word made to me since then I've had many other rewards from Nsf. 00:05:39.000 --> 00:05:47.000 And I'm very grateful for those as well, and for the wonderful program officers that that I've worked with throughout the years. 00:05:47.000 --> 00:05:53.000 I think 2 other things that just happened at the right time. 00:05:53.000 --> 00:06:17.000 That allowed me to kind of develop my research voice. The first one was that interdisciplinary research became fashionable in the sciences just as I was kind of coming up for tenure, and so I've often reflected if that happened 5 years sooner that our 5 00:06:17.000 --> 00:06:22.000 years later I might have had a very different career, and then the web. 00:06:22.000 --> 00:06:39.000 The web came on board again during those early years, and that allowed a steady stream of just incredibly talented and motivated students, who had essentially the same vision. 00:06:39.000 --> 00:06:48.000 I had to find me and come to an unranked department in the desert with a largely unknown professor, and take their chances. 00:06:48.000 --> 00:07:03.000 And so the work I'm talking about today, of course, is mostly their work, much less than mine, and we've had a lot of fun along with, okay, any other personal things anyone wants to know about and happy to talk about that. 00:07:03.000 --> 00:07:13.000 As well my plan today, you know, I've because I've been in computer science departments and receive most of my funding from size. 00:07:13.000 --> 00:07:16.000 I always said certain had to earn my life as a real computer scientist. 00:07:16.000 --> 00:07:24.000 And that often means emphasizing the biologic inspiration or the biological thought. 00:07:24.000 --> 00:07:34.000 That's behind the work I do. And so today I'm going to kind of double down on the biology and I hope you'll all indulge me in that. 00:07:34.000 --> 00:07:48.000 And really try to make the case for strong connections between biology and computation, especially connections that go beyond neurons which we're already getting a lot of leverage out of. 00:07:48.000 --> 00:07:53.000 Okay. So now for the talk. 00:07:53.000 --> 00:08:04.000 My research takes the perspective that that by all, as I mentioned that biology and computation have a lot to say to one another. 00:08:04.000 --> 00:08:08.000 And I've really emphasized 2 major themes during my career. 00:08:08.000 --> 00:08:15.000 The first is this idea of defending complex systems from malicious behavior, and, in my view, that and I've worked on all of these. 00:08:15.000 --> 00:08:31.000 That's everything from vaccine design to the adaptive therapies for cancer, that that we're developing in my center today to other kinds of evolving pathogens. 00:08:31.000 --> 00:08:45.000 And then, of course, to what will be chapter one of my talk cyber security, which is another interesting complex system that has to defend against malicious behavior. 00:08:45.000 --> 00:08:50.000 So that'll be the first part of the talk, and that's going to be abbreviated so that I can get to theme 2, which is where I've done more work in the past few years. 00:08:50.000 --> 00:08:58.000 That's really looking at software as an evolving system. 00:08:58.000 --> 00:09:03.000 And so. Chapter 2 of my talk will be about what I call micro level. 00:09:03.000 --> 00:09:12.000 Evolution that is using evolutionary computation methods quite directly to improve software. 00:09:12.000 --> 00:09:27.000 And then Chapter 3 will step back and talk about the macro level, or kind of the inadvertent evolution that I think is going on in software. 00:09:27.000 --> 00:09:35.000 And I decided to spare you all my enthusiasm and details about how the immune system actually works. 00:09:35.000 --> 00:09:56.000 And just focus on a few of the interesting information processing aspects of the immune system but I do have to say at least, what the immune system does, which is face the task of detecting and eliminating potentially huge numbers different numbers. 00:09:56.000 --> 00:09:56.000 I mean numbers of different replicating pathogens. 00:09:56.000 --> 00:10:00.000 And these pathogens, whether they're viruses or bacteria or parasites. 00:10:00.000 --> 00:10:08.000 But viruses and bacteria in particular, are replicating very quickly. 00:10:08.000 --> 00:10:32.000 So the system has to notice that it's been infected respond almost immediately as fast as it can, and it also has to be very careful to avoid false positives, because false positives lead to what is known as auto immunity, and that's a very serious problem so I 00:10:32.000 --> 00:10:37.000 also just before I jump into this, wanna mention that there's many, many other defense systems in biology. 00:10:37.000 --> 00:10:51.000 And these range from Crispr systems inside, single cells. You've probably heard about Crispr up to the kinds of heterogeneities and diversity that we see in populations. 00:10:51.000 --> 00:11:00.000 So the immune system operates at the scale of the individual, and there are many different kinds of immune systems in different animals and plants. 00:11:00.000 --> 00:11:06.000 We will be talking about what's known as the adaptive arm of the vertebrates. 00:11:06.000 --> 00:11:12.000 Immune system. And I just want to focus on a few of the. 00:11:12.000 --> 00:11:17.000 Pieces of this system that I think are most compelling to computer science. 00:11:17.000 --> 00:11:21.000 And so the first is that the immune system has several different learnings. 00:11:21.000 --> 00:11:23.000 Learning, mechanisms that uses learning in different ways. 00:11:23.000 --> 00:11:32.000 First of all, it has to learn the distinction between self and other when it jumped. 00:11:32.000 --> 00:11:40.000 Detectors and but detectors are things like bessels and T cells and antibodies, thingsy things that you've heard of. 00:11:40.000 --> 00:11:51.000 I'm sure the method that it uses to do this is, it uses several different methods, but one of the strategies is known as negative. 00:11:51.000 --> 00:11:50.000 Selections. And that's something that we built built algorithms out. 00:11:50.000 --> 00:12:02.000 If we even got a patent and started to company, and and etc., etc. 00:12:02.000 --> 00:12:11.000 Once. It has a set of detectors that it are sort of biased to match non self, and guaranteed as much as possible, not to react to self. 00:12:11.000 --> 00:12:20.000 Then, if you're infected with a with a virus, or I will just say pathogen, and by that mean virus or bacterium. 00:12:20.000 --> 00:12:31.000 But when we're infected with with a pathogen, it then has this problem of responding quickly, and that's known as the primary response, and it uses another form of learning. 00:12:31.000 --> 00:12:47.000 One that looks a lot like a genetic algorithm to actually evolve a set of detectors that are tailored specifically to match that particular pattern. 00:12:47.000 --> 00:12:56.000 And then finally over evolutionary time. It has evolved biases towards particularly important classes of threats. 00:12:56.000 --> 00:13:19.000 It also has memory. Memory is the reason that you don't get sick a second time when you're reinfected with the same virus, and that is known as a secondary response, and essentially what the immune system does in the secondary response is it this is the signature detection kind of 00:13:19.000 --> 00:13:21.000 piece, it. It recognizes something it's seen before. 00:13:21.000 --> 00:13:21.000 It knows it's bad, and so it requires very quickly and very aggressively, so much so. 00:13:21.000 --> 00:13:37.000 You usually don't know that yourself, and the the memory is also what immunologists refer to as cross, reactive. 00:13:37.000 --> 00:13:44.000 And we might call it associative and computer science. And that's really the that's the same principle that many vaccines are based on, including what I showed here. 00:13:44.000 --> 00:14:05.000 This picture of a very famous, the first, I think it was the first vaccine by Edward Jenner, who inoculated a little boy with cowpox, in the hope that it would protect him against a closely related and much more lethal disease smallpox, and if fact, that worked and 00:14:05.000 --> 00:14:09.000 it's one of the principles that underlies our vaccine. 00:14:09.000 --> 00:14:18.000 Still today. The next thing about the immune system that I love this is probably the thing that really got me hooked. 00:14:18.000 --> 00:14:21.000 Is it uses combinatorics. It has this problem. 00:14:21.000 --> 00:14:33.000 We only have 20 to 25,000 genes in that code for everything we do in the body, and yet the immune system has to make an enormous number of detect detectors that can recognize an enormous number of different foreign patterns. 00:14:33.000 --> 00:14:39.000 And so it uses this very cute trick of taking little pieces of genes and and splicing them together. 00:14:39.000 --> 00:14:50.000 With noise at the junctions, and it's exactly what a computer scientists might think of doing. 00:14:50.000 --> 00:14:58.000 And finally, the whole system is massively parallel and distributed spatially throughout our body. 00:14:58.000 --> 00:15:07.000 And it's just. It's a remarkable system, and I feel like it's under appreciated by by most of my colleagues in computer science. 00:15:07.000 --> 00:15:14.000 Okay, so. 00:15:14.000 --> 00:15:25.000 Some of these concepts that I've described have been applied in computing, and in some cases they've been used deliberately, like in my own work, where I actually try to go learn about the mechanisms. 00:15:25.000 --> 00:15:29.000 And then think of algorithms that that would implement them. And what kinds of problems they would be good for. 00:15:29.000 --> 00:15:49.000 But, in other cases they've been discovered independently, like people who have no one in biology, and I will argue that I think some some of these biological systems are emerging spontaneously and are interesting. For that reason. 00:15:49.000 --> 00:16:01.000 So I'm just gonna highlight a few. I've talked about the primary and secondary response, and you can think of the primary response as being like an anomaly intuition detection system. 00:16:01.000 --> 00:16:10.000 We worked on that earlier in in my career, and the secondary response works because of it's essentially a signature detail. 00:16:10.000 --> 00:16:15.000 And we've had those have those in cybersecurity for many years. 00:16:15.000 --> 00:16:24.000 A a second idea is the idea of a heterogeneous defense, and we see this in cybersecurity. 00:16:24.000 --> 00:16:34.000 I have to say that the ideas we worked on early didn't really take hold in the commercial world, but the idea of address space randomization certainly did. 00:16:34.000 --> 00:16:44.000 And the other thread is the thread that comes from in version programming, and later in variance systems that were used for cybersecurity. 00:16:44.000 --> 00:16:58.000 And there's starting to be a little resurgence of interest in that idea of having multiple implementations, each of which is independent or semi-independent, that can be run simultaneously. 00:16:58.000 --> 00:17:21.000 And looked for consistency, and in those well the recent interest is the idea is that there's so many implementations of things like blockchain algorithms out there that that you can pull these different implementations and use them without having to generate the diversity yourself now I do wanna point 00:17:21.000 --> 00:17:29.000 out that the immune system, as a defense system is also heterogeneous, meaning that each of us has our own unique immune system, and that provides a huge amount of population robustness. 00:17:29.000 --> 00:17:41.000 And that's something, I think we could do more with in cybersecurity. 00:17:41.000 --> 00:17:47.000 The third idea is the idea of second signals, and I think the that's used in lots of places in immunology. 00:17:47.000 --> 00:18:00.000 Probably the easiest example is the helper T cell, which which? 00:18:00.000 --> 00:18:10.000 Yeah, it's the idea is that when auto immunity is such a problem that you don't want to just pull the trigger at the first. 00:18:10.000 --> 00:18:19.000 The first time you think you have found a problem, but you need a confirming, a second, a second confirmation from from an independent source. 00:18:19.000 --> 00:18:25.000 And that's really the I idea behind 2 factor authentication and many similar systems. 00:18:25.000 --> 00:18:33.000 And then I wanna talk. Turn to this idea of a technological ratchet. 00:18:33.000 --> 00:18:44.000 And this is something that evolutionary biologists have been very interested in, and that we haven't talked about very much in in computer science. 00:18:44.000 --> 00:18:55.000 But I think is important. I'm just gonna explain it in my own words, and probably abuse the biology somewhat. 00:18:55.000 --> 00:19:11.000 But the idea is that each time a new mechanism is added to increase robustness or security, we actually reduced the selective pressure on our existing systems which leads leads to their degradation over time. 00:19:11.000 --> 00:19:33.000 At the same time it adds the overhead of maintaining the new mechanism, and so ultimately, as we add more and more layers of robustness, prettyection, or defense, we get diminishing returns and irreversibility cause we can't go back because cause the ones 00:19:33.000 --> 00:19:35.000 underneath them, decayed a bit. And that's for me. 00:19:35.000 --> 00:19:40.000 Raises the question when we talk about defense in depth. 00:19:40.000 --> 00:19:48.000 But how many layers of defense are actually optimal before we start getting toinishing returns, Steve. 00:19:48.000 --> 00:19:56.000 Frank has pointed out a nice example of this in in our space, which is the idea of a raid array. You know. 00:19:56.000 --> 00:20:07.000 If you, if all your memory, if all your data is stored on a single disk, you that disk has to be super reliable and therefore more expensive. 00:20:07.000 --> 00:20:26.000 But once people figured out to organize multiple discs in an array and spread out the data so that it could be, you could recover all your data, even if one or more disk failed that reduced the pressure the need to have really high reliable 00:20:26.000 --> 00:20:49.000 reliability disks, and I think an example of this, at least for me personally, in cyber security, is the idea of a password which in the old days I was very protective of my passwords, and then firewalls came along and I got a little less protective and 2 factor 00:20:49.000 --> 00:21:00.000 authentication. I'm even less protective, and I think we may be seeing this process, probably throughout computing, but certainly insightsbersecurity. 00:21:00.000 --> 00:21:05.000 And it does raise the question to me of, you know, could we formalize this? 00:21:05.000 --> 00:21:11.000 There are a lot of great models in in biology, a lot of nice mathematics that are fairly simple. 00:21:11.000 --> 00:21:14.000 And anyway. 00:21:14.000 --> 00:21:32.000 So that's that's an example of how kind of the natural development of our infrastructure may maybe creating structures that we haven't haven't thought of, or systems that we haven't thought of. 00:21:32.000 --> 00:21:32.000 And so that leads me to chapter 2 of the talk where we are going to talk about the role of evolution. 00:21:32.000 --> 00:21:49.000 Much more directly, and I always like to say computer programmers like to think of themselves like the picture on the left here, as you know, writing software, that's the product of intelligent design. 00:21:49.000 --> 00:22:19.000 Carefully crafted to me the specification, and I actually think and will argue that software is actually evolving in a sort of inadvertently through the collective actions of many, many programmers who are interacting with each other through that code and so I refer to the first level 00:22:21.000 --> 00:22:28.000 the second idea is macro level evolution, and the feature one is micro well, I guess I didn't say the first one. 00:22:28.000 --> 00:22:39.000 Micro level evolution is the idea of using evolution much more directly on software. 00:22:39.000 --> 00:22:52.000 And it turns out, software is a amenable to that which was quite surprising, and I suspect the reason it's amenable to it is because of the properties that our software has acquired. 00:22:52.000 --> 00:22:56.000 Okay, so that's that's sort of the preview of the rest of the talk. 00:22:56.000 --> 00:23:03.000 First I'm gonna talk about this what I'm calling Michael Evolution. 00:23:03.000 --> 00:23:15.000 And at that level my collaborator, Wesley, Onceer, from the University of Michigan, and I have worked together for a little over a decade. 00:23:15.000 --> 00:23:15.000 Now developing methods for automatically repairing software failures. 00:23:15.000 --> 00:23:24.000 Both bugs and security vulnerabilities. 00:23:24.000 --> 00:23:27.000 And he spent a great collaborator. All the work I'm gonna talk about. 00:23:27.000 --> 00:23:33.000 We've done. Together. We began this work with 2 of our students, who, when? 00:23:33.000 --> 00:23:43.000 And Claire Vu is now, I think, George Mason University, and Claire is at Carnegie Mellon, and Claire made this picture years ago. 00:23:43.000 --> 00:23:53.000 And it's still the best picture that I the best way I have to explain quickly how this system works. 00:23:53.000 --> 00:24:03.000 So in the next show if you give me a program, let's say it's written in C, and and and it has a test suite test suite shown here. 00:24:03.000 --> 00:24:08.000 It's a set of tests that have input output pairs. 00:24:08.000 --> 00:24:13.000 And the idea is you run the program on each test and check to make sure it produces the right output. 00:24:13.000 --> 00:24:21.000 In this case we know that the program has a bug, because one of its test cases is failing. 00:24:21.000 --> 00:24:39.000 And so conceptually I'm just skipping, you know, a lot of the technical detail conceptually, we take that program and make, let's say, 40 copies of it where each copy has one or more mutations to the code itself. 00:24:39.000 --> 00:24:51.000 Then out of the population we pull the programs one at a time, and we run them on the test suite to evaluate their fitness as a biologist would say, and the ones that do poorly, we throw away the ones that do better. 00:24:51.000 --> 00:25:07.000 We recirculate into the population with additional mutations and sometimes recombinations, and after just a few rounds of this process. 00:25:07.000 --> 00:25:19.000 Sometimes it's few as 10. We often about half the time can produce a problem that passes all of the test cases. 00:25:19.000 --> 00:25:23.000 And that was really remarkable to me when we first did it. 00:25:23.000 --> 00:25:33.000 Needless to say, other people, working in evolutionary computation, had had similar ideas. 00:25:33.000 --> 00:25:38.000 But we introduced several innovations that I think actually made it work. 00:25:38.000 --> 00:25:44.000 And our system was the first one that really Hi, I think I'm safe. 00:25:44.000 --> 00:25:54.000 Saying this worked worked on large, naturally occurring open source programs with naturally occurring bugs. Okay? 00:25:54.000 --> 00:25:58.000 So some of our tricks, where we started with a working program. 00:25:58.000 --> 00:26:06.000 Most of the people in Geneva programming start with with randomly generated programs. 00:26:06.000 --> 00:26:28.000 So that made our problem much more tractable. The second thing we did was we defined mutations that mimics human edit operations rather than just trying to like make up new variable names, or, you know, you take bits or something and our mutations are things that people do 00:26:28.000 --> 00:26:35.000 they delete lines of code, they copy a line of code from one place in the program to some place else, and they, our original thing, was swap 2 lines of code. 00:26:35.000 --> 00:26:45.000 Now people often do move or replace, and actually a lot of people only use delete and copy the second. 00:26:45.000 --> 00:26:54.000 So. The implication of that is that we're not actually trying to invent new code we're sort of just rearranging code that already exist. 00:26:54.000 --> 00:27:05.000 And I think that was important. And the second thing, which was kind of a guess, a lucky guess is that our mutations work on entire statements. 00:27:05.000 --> 00:27:15.000 And so those could be assign, you know, atomic statements like an assignment statement, or they could be compound statements like a while loop or something. 00:27:15.000 --> 00:27:23.000 And then the third piece of secret sauce was that we restricted our mutations to only change code. 00:27:23.000 --> 00:27:37.000 That was had been executed by the failing test cases, so that again, I think the first and the third of these are what actually made it possible for the system to work. 00:27:37.000 --> 00:27:41.000 And then the fourth thing isn't isn't due to us. 00:27:41.000 --> 00:27:49.000 But it is a fact of the world that most bugs can be fixed with very, very small number of edits. 00:27:49.000 --> 00:27:59.000 And so I think that was another. Another part of our success, and I've just shown a little example down here if this is an infinite loop kind of a famous infinite loop that we looked at early in our work and what the this Jim Crow algorithm did is it effectively. 00:27:59.000 --> 00:28:07.000 Moved this statement here, shown in Ard down to here, and that repaired the but it actually did it in a couple of steps. 00:28:07.000 --> 00:28:26.000 It. It first copied the statement down here that it did a bunch of other things that didn't really help the situation, that it, and then it finally figured out to get rid of this one. 00:28:26.000 --> 00:28:32.000 And but it did that very quickly. Okay, usually, I just stop and see if there's questions. 00:28:32.000 --> 00:28:36.000 But I'm just gonna plow on and take the questions at the end. 00:28:36.000 --> 00:28:38.000 So that's the same in a nutshell. 00:28:38.000 --> 00:29:00.000 How well does it work in practice? Well, it had. It worked amazingly well from our point of view, and it worked well enough that it stimulated a huge amount of interest in a field that what became known as automated program repair, which is now I think it's safe to 00:29:00.000 --> 00:29:12.000 say, a legitimate sub area of software engineering. And so there have been, we did early on several large kind of systematic empirical studies. 00:29:12.000 --> 00:29:31.000 And now many, many people have published many, many papers, with many, many tools, their own tools, of course, and their own little improvements on tools, using a few benchmarks, we we developed this benchmark in C, called many bugs. 00:29:31.000 --> 00:29:50.000 That was Clara Lewis's dissertation work, and but now I'd say the gravity of the field has moved towards Java, and defects for Jay is by far the most prevalent prevalent benchmark there there's also 00:29:50.000 --> 00:30:01.000 been a number of industry, transitions. Some of them are better advertised than others, but it has moved out into industry, and then, starting in. 00:30:01.000 --> 00:30:05.000 I don't know. 2,018, 2,019. 00:30:05.000 --> 00:30:19.000 The machine learning community discover this problem. And now I'd say, machine learning methods are sort of swamping, swapping the field and reporting great success. 00:30:19.000 --> 00:30:21.000 There are just a number of caveats. I don't want you to think that it's a 100% perfect. 00:30:21.000 --> 00:30:38.000 These are some of the things we tripped over turned out many test test suites in the wild, have buggy tests and the genetic algorithms are very good at exploiting those. 00:30:38.000 --> 00:31:02.000 It's easy enough. I'll have any example on the next slide of actually, I'd like to say, obeying the letter of the law, like the the details of of the tests of the test rather than the spirit of the law that is actually the 00:31:02.000 --> 00:31:07.000 ground, truth that that needs to be repaired. And so people have called this overfitting. 00:31:07.000 --> 00:31:12.000 It's a little bit of a Miss Nowhere, but that's a big concern in the field. 00:31:12.000 --> 00:31:17.000 The whole question of how it evaluate repairs. 00:31:17.000 --> 00:31:23.000 We do have a standard now which I personally think is not a great one. 00:31:23.000 --> 00:31:28.000 But how do you know? How do you judge if a repair is correct or not? 00:31:28.000 --> 00:31:38.000 Be beyond? Does it pass? It's test cases, and then now, with all the machine learning methods, there's a whole set of new issues that have cropped up recently. 00:31:38.000 --> 00:31:43.000 And I think over time the field will address those and get to them. 00:31:43.000 --> 00:32:03.000 Bye, I the the the real caveat is when you read these papers, everyone reports numbers, and you have to do a lot of digging to see how well the numbers actually match up with each other, because there's a lot of apple to oranges kinds of comparisons. 00:32:03.000 --> 00:32:09.000 Okay, so this is an example of obeying the letter. You know. 00:32:09.000 --> 00:32:19.000 But fighting a repair that passes a test case passes the test suite, but doesn't necessarily deal with what the programmer wanting. 00:32:19.000 --> 00:32:30.000 Hi! I'm just not really interested. So to me it is not that surprising that big. 00:32:30.000 --> 00:32:36.000 Let me just check my time. Yeah, it is not that surprising that, hey? 00:32:36.000 --> 00:32:42.000 Large language model that can communicate with a wide variety of people. 00:32:42.000 --> 00:32:52.000 In natural language, should be able to find, you know, single line repairs to software. 00:32:52.000 --> 00:33:04.000 I you know to me that's not surprising, and I'm sure that will alright continue to be successful and have more more success and more generality. 00:33:04.000 --> 00:33:15.000 But it is still surprising to me that you can make random mutations to code and fairly quickly find. 00:33:15.000 --> 00:33:24.000 Use that method to find repairs. And yeah, it's just it. 00:33:24.000 --> 00:33:37.000 I that that has, how this could be working has bothered me right from the beginning, and so this really brings us to Chapter 3, which is asking how? 00:33:37.000 --> 00:33:43.000 And you know, what? What is it about? 00:33:43.000 --> 00:33:52.000 Software that makes it amenable to this. This evolutionary computation approach to random mutation and other things. 00:33:52.000 --> 00:33:57.000 And so that's actually what I'm most interested in over the past few years. 00:33:57.000 --> 00:34:10.000 And my approach has been to learn about properties, that biologists think are important in evolution, and then look for them in software. 00:34:10.000 --> 00:34:27.000 And today we've looked at 4 such properties, mutational robustness, mutual landscapes, fitness, distributions, and epstasis, which is just a fancy word for interactions between genes. 00:34:27.000 --> 00:34:35.000 And I've I've had 3 s. You've done most of this work, Eric Schilte started with the work on mutational Robustness. 00:34:35.000 --> 00:34:47.000 Joe Renzua, one of my current students, is looking at these neutral landscapes and fitness distributions, and Jerry Lou, another one of my current students, is, I wouldn't say, looking for epistasis. 00:34:47.000 --> 00:35:04.000 He has stumbled across some very interesting at the Stasis. And so I'm just gonna tell you a little bit about those before we start wrapping up. 00:35:04.000 --> 00:35:26.000 So, and then we began this investigation by considering something called mutual mutations, and in biology most mutations I should say most mutations are deleterious, that is, they reduce fitness just like they do in in in our software systems. 00:35:26.000 --> 00:35:33.000 And but it's and then there's a very, very small number that are beneficial and I think that's not unlike our situation. Software. 00:35:33.000 --> 00:35:47.000 But it turns out there's a large number surprisingly large number of mutations in the middle that are don't have any immediate effect on fitness. 00:35:47.000 --> 00:36:03.000 No no observable effect, and those are referred to as neutral mutations, and in biology they are believed to be a key enabler of the evolutionary process. 00:36:03.000 --> 00:36:18.000 There is arguments in the field about why they're so important, but they've been known about for a long time, and and most biologists I've talked to at least all all think that they're tremendously important. 00:36:18.000 --> 00:36:24.000 So we started out, asking whether there were neutral mutations in software. 00:36:24.000 --> 00:36:38.000 So we defined a neutral mutation to be, and a random edit, or a mutation that is applied to a program and leaves the program able to still pass its original test suite. 00:36:38.000 --> 00:36:53.000 So in this case, we're gonna we're gonna start out with a program that passes all of this tests. And then we're gonna make them a single random mutation to it. 00:36:53.000 --> 00:36:53.000 In the execution path that is executed by at least one of the test cases. 00:36:53.000 --> 00:37:04.000 So we're not mutating dead code and then we're gonna ask whether or not it still passes the test suite. 00:37:04.000 --> 00:37:18.000 And Eric Schulte. My student, did this, you know he did it for an enormous number of programs in different coming in different languages and at different levels of representation. 00:37:18.000 --> 00:37:37.000 And yeah, all. And in all cases there was an amazing amount of what's called mutual robustness in the case of the gen product mutations I described at the source code level for C, it's about 30% of the time. 00:37:37.000 --> 00:37:47.000 Those mutations don't change the behavior of the program on the test cases, and. 00:37:47.000 --> 00:37:50.000 I found that really surprising, and I don't. 00:37:50.000 --> 00:37:56.000 I still don't actually know why it's true. 00:37:56.000 --> 00:38:10.000 But I do believe that they, these mutations, are really important, both for allowing our systems to work, but also for improving search, and so we've been using this property in several ways. 00:38:10.000 --> 00:38:18.000 2 of which I'm gonna tell you about in the next few slides. 00:38:18.000 --> 00:38:40.000 But the basic idea is that if you think of this, look at the figure, if you think of this circle here as containing all of the different program variants, we call them, or single mutants of the program and think of the Y-axis as being fitness whether 00:38:40.000 --> 00:38:45.000 it's how many test cases they' or will have some other metrics in. 00:38:45.000 --> 00:39:06.000 The idea is that if there's no selection, because they're neutral, they don't affect fitness, then the population can spread out across that circle, and it's more likely that a single individual will encounter one of these so called local optima and be able to 00:39:06.000 --> 00:39:12.000 this, the evolutionary process can then climb that peak, and we can find high fitness solutions. 00:39:12.000 --> 00:39:12.000 So we've been. We've used this in a variety of settings. 00:39:12.000 --> 00:39:29.000 I'm gonna tell you just a little bit about how it relates to bug repairs, and then how it, how we've been using it to reduce the run times of gpu codes. 00:39:29.000 --> 00:39:47.000 So this first piece of this is Joe Renzello's work, and remind myself on a second. 00:39:47.000 --> 00:39:47.000 So this and this. I'll just tell you the experiment first, and you can probably read the slide. 00:39:47.000 --> 00:39:51.000 You start with an original program shown in black here every. 00:39:51.000 --> 00:40:13.000 The question is, what what does neutral space look like like if we just explore the space of programs that are neutral with respect to the test suite, that is, they pass the same set of tests as the original program. 00:40:13.000 --> 00:40:24.000 What does that space look like? And so Joe did. A whole variety of experiments where you sort of make one neutral mutation, and then you make another one. 00:40:24.000 --> 00:40:26.000 You kind of take, as they say, it walks through neutral space and he played around in particular with one program that had a latent bug. 00:40:26.000 --> 00:40:41.000 So that the the program was released into the wild with a test suite, and it turned out it had a bug that the tests didn't test for, but it was discovered later. 00:40:41.000 --> 00:40:46.000 So that we had this like held out test for that bug. 00:40:46.000 --> 00:40:54.000 And so Joe, using the original test suite, generated this graph, and all of the colored points represent. 00:40:54.000 --> 00:41:12.000 This was with no selection, represent solutions, repairs to this particular bug, and in this case he looked at the repairs and convinced himself they were correct, and the colors are all semantically distinct kinds of repairs. 00:41:12.000 --> 00:41:15.000 So the network is somehow connecting these diverse repairs. 00:41:15.000 --> 00:41:30.000 Through these, you know, intermediaries, and and so the question is, if we're in the business of looking for repairs, how far away from the original program should we be looking? 00:41:30.000 --> 00:41:34.000 You know. You notice there's none of the repairs are right around around here, and and I should say, this is where our method and all the other methods that I know about. 00:41:34.000 --> 00:41:44.000 They all tend to search very, very close to the original program. 00:41:44.000 --> 00:41:49.000 And so the question is, where should we be searching a neutral space? 00:41:49.000 --> 00:41:55.000 And let me just check my time next I've got to speed up. 00:41:55.000 --> 00:42:18.000 So if you think of the X-axis here as on this graph, as how far away a neutral space you are, how many neutral mutations have been applied to the sync, to a single program, and the Y-axis as how many of your samples if you do that 00:42:18.000 --> 00:42:25.000 sample over and over and over again. How many of your samples actually constitute a repair for the bug? 00:42:25.000 --> 00:42:30.000 That is how dense are those colored points at different distances from the orange. 00:42:30.000 --> 00:42:30.000 Joe's way of doing it was a little different. 00:42:30.000 --> 00:42:44.000 You generated a large pool of neutral edits then he selects sort of random subsets from them, but he found this very interesting phenomenon, which is, and in this case it was, I think, 270. 00:42:44.000 --> 00:42:49.000 Some mutations away from the original program. 00:42:49.000 --> 00:42:48.000 So if you were doing a single mutation, which is what most methods do. 00:42:48.000 --> 00:43:03.000 You're over here, but if you go 270 mutations away, you end up up here where you're 100 times more likely to find a repair. 00:43:03.000 --> 00:43:12.000 But it doesn't go on forever I you know there's you start eventually getting interactions between these different edits, negative interactions. 00:43:12.000 --> 00:43:17.000 And so the curve tails off. And so, yeah, we fit the curve. 00:43:17.000 --> 00:43:30.000 We've got sort of a general form for it. We think it reflects the interaction of 2 competing tendencies, and we've confirmed it in a lot of other programs I've just shown 3 of them here, and so he has taken this idea. 00:43:30.000 --> 00:43:37.000 And developed an algorithm called multiplicative weights, Repair. 00:43:37.000 --> 00:43:41.000 It's not actually a genetic algorithm, but it does use the mutations. 00:43:41.000 --> 00:43:50.000 And and that's that's about to come out in Nacm transactions to okay. 00:43:50.000 --> 00:43:58.000 So that's been very interesting and if I had more time I could tell you a lot more about that. 00:43:58.000 --> 00:44:09.000 But instead, I'm gonna move on to optimizing Gpu code. 00:44:09.000 --> 00:44:30.000 So this is work that I did in collaboration I have am doing in collaboration with Carol, who was on the faculty at Asu, and it's now at Facebook and her student who have now inherited Jerry Lou and the idea here is that Gpus are really important and everyone's using 00:44:30.000 --> 00:44:37.000 them, but they're very hard to optimize. And so Jerry's idea was kuda code. 00:44:37.000 --> 00:44:48.000 Pull out the piece that runs on the Gpu, and essentially use that same process I described, for Jim Frog. His algorithm has some differences, but it's the same basic idea where you apply random mutations. 00:44:48.000 --> 00:45:01.000 You make sure they still pass the test cases, but in this case, in addition, you evaluate your fitness, function is, how fast do they run? 00:45:01.000 --> 00:45:11.000 So you can think of him as this process is finding all the neutral mutations, and then Benny's adding on the fitness by saying, How fast do they run? 00:45:11.000 --> 00:45:17.000 And so he implemented this thing. I was pretty skeptical. 00:45:17.000 --> 00:45:23.000 I have to say, not knowing that much about Gpus, because I know that compilers are really good. 00:45:23.000 --> 00:45:27.000 But in fact it on the this set of benchmarks from their community it found an average of 49% speed up. 00:45:27.000 --> 00:45:47.000 Now I have to say that the sometimes we got 0, and sometimes we got a huge amount, and we don't don't exactly know. 00:45:47.000 --> 00:45:49.000 We don't we don't. We don't know why. 00:45:49.000 --> 00:46:01.000 Some programs are more amountable to being optimized than others, and we don't have a good way of predicting, so that's that's still sort of unsolved, anyway. 00:46:01.000 --> 00:46:20.000 But we are very encouraged by those results, and so I say, I was boasting a little to some friends of mine at Lawrence Berkeley Labs, and they handed us a challenge which was a state of the art implementation of a well known bioinformatics algorithm for multiple 00:46:20.000 --> 00:46:42.000 sequence, alignment that had been very important was designed explicitly to run fast on Gpus, and they not only that they had hand tuned the code, and by someone who knew a lot about Gpus, and so they gave us that version of the Code and Jerry, did we've now done lots 00:46:42.000 --> 00:46:48.000 of runs by the way. But this first run, this is sort of amazing, because first run found. 00:46:48.000 --> 00:46:54.000 A version of the program that is still correct. And and this is an example. 00:46:54.000 --> 00:46:57.000 Of our program like sorting. That is extremely well tested. 00:46:57.000 --> 00:47:02.000 And so we're not worried about. 00:47:02.000 --> 00:47:13.000 No, not not concerned that. We're confident that our that are optimized versions of the programs are actually correct. 00:47:13.000 --> 00:47:26.000 But anyway, he found a version that runs 28.5% faster, which was very impressive and surprising to our human expert. 00:47:26.000 --> 00:47:29.000 And so then he did. This is why he's a great student. 00:47:29.000 --> 00:47:36.000 He was able to do a lot of analysis and I'm skipping a few steps. 00:47:36.000 --> 00:47:51.000 But the gist. Is that a significant amount of the improvement or speed up comes from collections of interdependent mutations, and I'm just gonna explain one right here. 00:47:51.000 --> 00:47:53.000 This is, this is the big one, but it's more complex. 00:47:53.000 --> 00:47:59.000 But just to give you the idea. If you have mutation 0. 00:47:59.000 --> 00:48:10.000 So that the the numbers represent a particular mutation, just an index numbering, you know, labeling the mutation and the color inside tells you how much improvement. 00:48:10.000 --> 00:48:17.000 So this this 0 mutation gives you less than 1% improvement on its own. 00:48:17.000 --> 00:48:20.000 The eleventh mutation. If it is only if it's done by itself, it breaks the program. 00:48:20.000 --> 00:48:31.000 Program doesn't complete. But if you have both of those together, you get 2% improvement. 00:48:31.000 --> 00:48:39.000 And then, similarly, for this thing, if you have these 4 mutations together, you get 15% of the speed up. 00:48:39.000 --> 00:48:54.000 And this little, this little graph on the right just kind of shows you the order in which these 4 mutations were discovered, and how much speed up they gave the optimizations were really interesting and counterintuitive. 00:48:54.000 --> 00:48:59.000 So for the arc. If there's any architectural people here, I just want to say that one of them involved switching to use shared memory to share for some data. 00:48:59.000 --> 00:49:04.000 Instead of private registers, and don't ask me how it works. 00:49:04.000 --> 00:49:25.000 Because I'm not the architecture person, but Jerry dug into it and you know it's very counterintuitive, but it turns out that you eliminate a conditional, and you save so much by eliminating the conditional that you it's worth the price of having slower 00:49:25.000 --> 00:49:31.000 memory access. It also found some. Redundant synchronizations. 00:49:31.000 --> 00:49:39.000 Those have been better known, I think, in the literature, and in some cases found some unnecessary memory. 00:49:39.000 --> 00:49:42.000 Initializations. 00:49:42.000 --> 00:49:57.000 Okay, lots more to say about that. But in the time I have left I want to just step back and consider what I refer to as Macro Evolution. 00:49:57.000 --> 00:50:09.000 And just sort of summarize the past few minutes we have found a variety of pieces of evidence in different settings. 00:50:09.000 --> 00:50:18.000 The software has properties that resemble. I'm not gonna claim they are, you know, there, but resemble those of biological systems. 00:50:18.000 --> 00:50:26.000 So things like mutation or robustness. Some of these properties are believed to be important for evolution. 00:50:26.000 --> 00:50:31.000 And so question is, where do they come from? In software? 00:50:31.000 --> 00:50:43.000 And I can't prove it, but I think part of the answer is that the software we have today is, in fact, the result of many generations of inadvertent evolution. 00:50:43.000 --> 00:51:04.000 And so I'll just remind you that over a century ago Darwin identified the sort of 3 key ingredients of evolution, variation, natural selection of successful variants and inheritance of those variants by their offspring and I argue that we have the 00:51:04.000 --> 00:51:19.000 same thing in software, especially today, where every time I borrow a piece of code from someplace else and copy it into my code base and start using it. 00:51:19.000 --> 00:51:29.000 That is, selection and inheritance. Every time I make small changes to it, or recombine it with other other code that I got from someplace else that's reconciliation. 00:51:29.000 --> 00:51:34.000 So I think we at least can say we have all the ingredients. 00:51:34.000 --> 00:51:38.000 Of evolution. 00:51:38.000 --> 00:51:48.000 And it shouldn't be so surprising that we might have evolution when we consider what our software landscape looks like today. 00:51:48.000 --> 00:51:55.000 So we have stack overflow that totally enables copying code from good code. 00:51:55.000 --> 00:52:06.000 For 1 point to another. We have a little cartoon here that illustrates how recombination might work, and of course we have the continual integration model. 00:52:06.000 --> 00:52:16.000 Of software development that brings fitness, evaluation that is feedback from the users much closer to the development cycle. 00:52:16.000 --> 00:52:18.000 And in all of these I think they're interested. 00:52:18.000 --> 00:52:32.000 They're all interesting because they blend sort of human human engineering or human ingenuity with with these kind of evolutionary Darwinian mechanisms. 00:52:32.000 --> 00:52:38.000 And so, I I think that's kind of interesting. 00:52:38.000 --> 00:52:49.000 And the this idea that software somehow blends human engineering with evolutionary dynamics. 00:52:49.000 --> 00:52:57.000 It's not really obvious. And it's, you know, many of you may be reacting against this. 00:52:57.000 --> 00:52:57.000 I'll hear about that in the questions. I'm sure. 00:52:57.000 --> 00:53:05.000 But it's it's not obvious, because it's glaring differences between evolution and engineering. 00:53:05.000 --> 00:53:07.000 And Francois Jacko pointed these out many years ago. 00:53:07.000 --> 00:53:15.000 He wrote a couple of papers that have this little phrase in it. 00:53:15.000 --> 00:53:27.000 Nature is a tinkerer, not an inventor, and he really distinguished between evolution, which he referred to as tinkering and craftsmanship, which I call engineering. 00:53:27.000 --> 00:53:41.000 Okay, how was my time doing? Alright? Hi, so I think it's it's tempting to really think of these 2 processes as completely divorced, totally different kinds of things in opposition to one another. 00:53:41.000 --> 00:53:50.000 But in fact, when I look at the systems that we're building today, I see many, many examples of the 2 of them. 00:53:50.000 --> 00:54:00.000 You know, evolutionary engineering, either working together either synergistically or in some cases at cross-purposes. 00:54:00.000 --> 00:54:04.000 So antibiotic resistance is a great idea. 00:54:04.000 --> 00:54:13.000 You know you design your drugs in the lab, and then release them in into the wild, into the body, and guess what evolution takes over. 00:54:13.000 --> 00:54:21.000 And wouldn't it be great if we could account for that evolution when we were designing, designing the drugs? 00:54:21.000 --> 00:54:31.000 I'm just gonna go through these really, quickly, Francis Arnold won the Nobel Prize in chemistry in 2,018 for what she calls directed evolution, which is kind of combined. 00:54:31.000 --> 00:54:45.000 Some Darwinian, you know. Some of these genetic mechanisms with with engineering to produce useful, useful proteins and and other other substances. 00:54:45.000 --> 00:54:51.000 There's all of synthetic biology. And one of my favorite examples. 00:54:51.000 --> 00:55:14.000 Here are these xenobots where people actually used evolutionary computation to design design a simple robot, and then took cells from a frog embryo and built the robot to that specification and show that it could solve the tasks that the that it was designed to 00:55:14.000 --> 00:55:18.000 do we also have? Oh, wait! Attack, I guess anyone have a separate slide for that attack. 00:55:18.000 --> 00:55:18.000 Fuzzing and cyber security goes the other way. 00:55:18.000 --> 00:55:26.000 We have these random mutations that we do to the inputs randomized algorithms, of course, are well known. 00:55:26.000 --> 00:55:42.000 Some field of computer science. And I hope I've convinced you that software is a blend between evolution and engineering. 00:55:42.000 --> 00:55:52.000 Okay. So I need to wrap up one of the one of the best practices for engineering systems in the context of evolution. 00:55:52.000 --> 00:55:57.000 I I think this is a really important question that we should be thinking about. 00:55:57.000 --> 00:56:01.000 And I think software is a great place to start thinking about it. 00:56:01.000 --> 00:56:07.000 I should mention that the National Academy of Engineering has held this. 00:56:07.000 --> 00:56:14.000 Some workshops on this theme of engineering and evolution, but their take is a little different from mine. 00:56:14.000 --> 00:56:14.000 Went to one of these workshops, and I was kind of surprised. 00:56:14.000 --> 00:56:25.000 They, the bulk of the discussion was about taking engineering methods and using them more directly, like in biomedicine. 00:56:25.000 --> 00:56:27.000 And my view is what we need to do is appreciate. 00:56:27.000 --> 00:56:34.000 Biology, and think a little differently about how we do our engineering. 00:56:34.000 --> 00:56:38.000 And so all of these other things I think fit into that. 00:56:38.000 --> 00:56:57.000 But in summary, I believe, the perspective of bu biology is important, because it provides both insight and guidance, and so the guidance part is the engineering that we can do, using bio-inspired computing. 00:56:57.000 --> 00:57:01.000 I've given you some examples of that, and the science. 00:57:01.000 --> 00:57:21.000 The insight part is what we can do by, for example, looking at these biological properties of computation and just in case you don't, don't believe me, I will appeal to one of the godfathers of our field carver, mead and quote him, this quote is 00:57:21.000 --> 00:57:24.000 attributed to him. I've never been able to chase down where. 00:57:24.000 --> 00:57:32.000 But anyway, as engineers, we would be foolish to ignore the lessons of a 1 billion years of evolution. 00:57:32.000 --> 00:57:36.000 So thank you very much. 00:57:36.000 --> 00:57:36.000 Thank you, Stephanie, for a reallyilliant talk. 00:57:36.000 --> 00:57:46.000 Very, part-provoking. Let's give a virtual round of applause. 00:57:46.000 --> 00:57:52.000 This technique for for the talk, and I'll open it up for questions. 00:57:52.000 --> 00:57:52.000 There are a few in the so why don't we start with those? 00:57:52.000 --> 00:57:59.000 And and we'll go from there first. One is. 00:57:59.000 --> 00:58:04.000 Okay, do, do you want to read them to me, or do you want me to look in the how do you have? 00:58:04.000 --> 00:58:03.000 Okay. 00:58:03.000 --> 00:58:08.000 Let me read them out that we others can either missed, but I don't know if they can see the all of them. 00:58:08.000 --> 00:58:12.000 So wonderful talk. Thank you. What is an example of a neutral editor? 00:58:12.000 --> 00:58:17.000 And how are they generated? 00:58:17.000 --> 00:58:25.000 Yeah? Great question. This is where I wish I had been in a live audience, so I could have handle that along the way. 00:58:25.000 --> 00:58:30.000 So I I gave an example on that slide. Can you still see my slides? 00:58:30.000 --> 00:58:31.000 Yes, we can. 00:58:31.000 --> 00:58:34.000 Oh, wait just minute. I gotta get out of this. 00:58:34.000 --> 00:58:41.000 Okay, just a minute. 00:58:41.000 --> 00:58:49.000 I should have pointed this out. This. So this is an example from Quicksort, so if you, if you had the swap mutation, then you could imagine. 00:58:49.000 --> 00:58:54.000 Just swapping those 2, whether you recruit on the left or the right doesn't really what order you do. 00:58:54.000 --> 00:58:58.000 It doesn't really matter. So the mutations let me just get back up and look at this. 00:58:58.000 --> 00:59:06.000 They're generated there, we're not doing anything special to generate them. 00:59:06.000 --> 00:59:12.000 We just do the mutations that I described early on. 00:59:12.000 --> 00:59:26.000 So we we find a statement, and we, you know, randomly delete it or copy it to some place else, or swap it with another statement. 00:59:26.000 --> 00:59:29.000 So there's there's no special thing. This I guess. 00:59:29.000 --> 00:59:40.000 The special thing is that then, after the test, after we run the test suite, if it still passes the test suite, then we check it as being neutral. 00:59:40.000 --> 00:59:45.000 Thank you. There are a bunch of questions from Glen Langston. 00:59:45.000 --> 00:59:48.000 Let me start with the first one with Gpu, with the Gpu optimization. 00:59:48.000 --> 01:00:04.000 It seems like one would need a huge complete fitness test. 01:00:04.000 --> 00:59:57.000 Yeah. 00:59:57.000 --> 01:00:08.000 It could be that the optimize it could be that the optimize such that it would work perfectly except for one critical failure, mode. 01:00:08.000 --> 01:00:14.000 Yeah, that's always that's not just a criticism of the Gpu optimization. 01:00:14.000 --> 01:00:22.000 But that's a criticism of the automated repair work as well, and usually in the automated repair. 01:00:22.000 --> 01:00:34.000 Context, I appeal to what I believe is practice and industry, which is, if it passes all the test cases, then we're okay. 01:00:34.000 --> 01:00:51.000 In the case of the multiple, I mean, it is certainly a concern, but in the case of the of the multiple sequence alignment, we are competent that we've got a solid, a test suite that tests all possible scenarios. 01:00:51.000 --> 01:00:54.000 It's huge. It runs quickly, and it's on, you know. 01:00:54.000 --> 01:01:04.000 It's such an important application in bioinformatics that people put a lot of effort into it. 01:01:04.000 --> 01:01:08.000 You know it. 01:01:08.000 --> 01:01:19.000 Yes, I mean you're only as good as your test cases until we have have someone of automatically testing the correctness. 01:01:19.000 --> 01:01:38.000 We did do some work at a few years ago on invariant using invariance, automatically generating invariance like dynamic invariance and because you're only changing in the case of the bug repairs because you're only changing a few lines of 01:01:38.000 --> 01:01:41.000 code. 01:01:41.000 --> 01:01:50.000 It's relatively easy to generate the invariance and then figure out how they're different between the original program and the repaired program. 01:01:50.000 --> 01:01:57.000 And so you you can do things like that. 01:01:57.000 --> 01:02:02.000 But I mean, my basic answer is most of the code we use isn't perfect, anyway. 01:02:02.000 --> 01:02:07.000 But I realize that's not very satisfying to most people. 01:02:07.000 --> 01:02:10.000 So I take that one. 01:02:10.000 --> 01:02:14.000 Yeah, I'm gonna skip to a different question. 01:02:14.000 --> 01:02:17.000 See from an anonymous attendee. 01:02:17.000 --> 01:02:20.000 Do you think that you can identify a few mutants? 01:02:20.000 --> 01:02:34.000 Combine them, run many generations and predict the potential outcomes, phenotypes. 01:02:34.000 --> 01:02:41.000 Well, it. Okay. By identify a few mutants. I'm not exactly sure what the question means. 01:02:41.000 --> 01:02:53.000 I guess. But if the idea the idea is I could identify which meetings were the good ones and combine them, and and then run them for, and then start evolving. 01:02:53.000 --> 01:03:02.000 Maybe the idea is to evolve from there. Yeah, that I've never tried that. 01:03:02.000 --> 01:03:11.000 But that's that would certainly be like if you had a repertoire of mutations that you thought were useful for optimizing Gpus. 01:03:11.000 --> 01:03:11.000 You know, there might be just a few tricks that kind of come along. 01:03:11.000 --> 01:03:14.000 People. People in the automated repair space have designed. 01:03:14.000 --> 01:03:27.000 There's a whole sub-RAM on templated repairs, where the mutation operators are really sort of filling in templates. 01:03:27.000 --> 01:03:34.000 And that I, if I understand what the question is, that might be. 01:03:34.000 --> 01:03:36.000 Response to the question. 01:03:36.000 --> 01:03:40.000 Thank you. We have a question from Michael Littman. 01:03:40.000 --> 01:03:44.000 I really like the debugging example you gave with test cases. 01:03:44.000 --> 01:03:54.000 I used to select code modifications. How might programming change if this approach were incorporated as part of the development? 01:03:54.000 --> 01:03:52.000 Yeah. 01:03:52.000 --> 01:04:00.000 Ide instead of a debug time. 01:04:00.000 --> 01:04:09.000 Yeah. Well, that was my great idea. I had to start a company, but I think co-pilot is kind of an example of it. 01:04:09.000 --> 01:04:13.000 Yeah, I think, having a little, I always thought, you know, like an eclipse or something. 01:04:13.000 --> 01:04:21.000 If if you had a little button you could click that just said, propose a repair, and the nice thing is about these algorithms, is it? 01:04:21.000 --> 01:04:27.000 At least the the version that I work on it could propose multiple repairs. 01:04:27.000 --> 01:04:36.000 And then you you could look at them. But I think the co-pilot people got there before I did. 01:04:36.000 --> 01:04:43.000 Going back to a question on the team again by Glenn Langston. 01:04:43.000 --> 01:04:49.000 The evolution concept is excellent for explaining existing features, buses exploring a comment. 01:04:49.000 --> 01:04:56.000 But it's terrible at predicting exactly what the next generation will be. 01:04:56.000 --> 01:04:59.000 Yes. 01:04:59.000 --> 01:05:07.000 Bye! 01:05:07.000 --> 01:05:08.000 There is a question. 01:05:08.000 --> 01:05:15.000 Yeah, I may be okay. I'm I'm just trying to understand what the this this is. 01:05:15.000 --> 01:05:13.000 Yeah. 01:05:13.000 --> 01:05:28.000 Again, where being in person would be nice, I think that's saying that looking at these biological properties might be useful for explaining what's there? 01:05:28.000 --> 01:05:37.000 But it's not so good for predicting what's gonna be next. 01:05:37.000 --> 01:05:46.000 If by prediction you mean exactly what the next generation of software is gonna look like, you're absolutely correct. 01:05:46.000 --> 01:06:02.000 But I do think we know a lot about the patterns of evolutionary dynamics like the rate at which evolution happens, or the fact that evolution happens you know, with these punctuated equilibria, you know, there's there's a lot of things like that that 01:06:02.000 --> 01:06:17.000 wouldn't involve exactly predicting with the makeup of the next generation is but these sort of larger patterns, and of course, something we've struggled with in evolutionary computation for years is this problem of premature convergence. 01:06:17.000 --> 01:06:27.000 So one of the nice things in software is so open, you know, if people are doing this in this gigantic population, wise, it's completely open-ended. 01:06:27.000 --> 01:06:36.000 And so I think to me that makes it more like evolution, like real evolution, natural, naturally occurring evolution, I should say. 01:06:36.000 --> 01:06:40.000 Liftfang has put in a couple of questions at the end. 01:06:40.000 --> 01:06:53.000 Great talk, 2 questions. Naturally, evolution happens at a much larger scale and over a long period, time, period. 01:06:53.000 --> 01:06:49.000 That should be dramatically. 01:06:49.000 --> 01:07:04.000 How can we? Dramatically, yeah, expand the spatial intensity scale of software mutation automatically, how about computational power needed? 01:07:04.000 --> 01:07:05.000 And the second question is sometimes unexpected. Mutation leads to significant evolution. 01:07:05.000 --> 01:07:16.000 Change? What about unexpected software mutations? 01:07:16.000 --> 01:07:25.000 Well, thank you. These are all great questions. So. 01:07:25.000 --> 01:07:32.000 First of all, whenever I talk to biologists and say, Oh, yeah. 01:07:32.000 --> 01:07:31.000 But you guys have these gigantic populations. We have to cheat because we have small populations. 01:07:31.000 --> 01:07:41.000 They always say, Oh, no, there's lots of systems that you know. 01:07:41.000 --> 01:07:44.000 Evolve quickly and have small populations, but generally I think you're right. 01:07:44.000 --> 01:07:50.000 That evolution takes a long time, and the larger scale. 01:07:50.000 --> 01:07:58.000 I. 2 answers to it. One is I think that's why this sort of macro level evolution is so interesting. 01:07:58.000 --> 01:08:04.000 Cause. It is happening at a much larger scale, and and the innovation cycle is faster. 01:08:04.000 --> 01:08:06.000 You don't, you know? Like, if you're thinking about the evolution of mammals, you don't have to wait. 01:08:06.000 --> 01:08:17.000 However long it takes for a baby to grow up and have offspring. 01:08:17.000 --> 01:08:39.000 The other answer. Is a little cynical, but I I say, if we gave these methods, you know even a fraction of the power that we're devoting to training these machine learning models, we could run with much bigger populations for much longer periods of time, and yeah, the 01:08:39.000 --> 01:08:42.000 unexpected me. So part, that's part one, part 2 on it, sometimes unexpected mutation leads to significant evolution. 01:08:42.000 --> 01:08:59.000 Change? What about unexpected software and mutation? Well, indeed, I think I had a little picture of the heartbreak, blood, heart, bleed bug on my slide. 01:08:59.000 --> 01:09:08.000 I think that was a great example of an unexpected change that, you know, had huge impact on our networking security. 01:09:08.000 --> 01:09:16.000 So I think I agree with that. 01:09:16.000 --> 01:09:18.000 Do you want me to go to the next one? 01:09:18.000 --> 01:09:24.000 Yeah, I think, this. I can read it out. Thank you for your wonderful and inspiring talk. 01:09:24.000 --> 01:09:35.000 Do you think it is possible to apply neutral mutations through pair safety issues of machine learning based systems like Chat Gpt. 01:09:35.000 --> 01:09:40.000 If yes, could you provide some insights? 01:09:40.000 --> 01:09:52.000 I don't know about safety. I do know that evolutionary algorithms are used more traditional versions of them. 01:09:52.000 --> 01:10:06.000 Are used fairly extensively to design the architectures for these large marsh learning models in terms of safety. 01:10:06.000 --> 01:10:18.000 I don't know. I've thought about using these models to ask other questions, but. 01:10:18.000 --> 01:10:23.000 I I don't have a if you've got an idea for how to do it, either. 01:10:23.000 --> 01:10:27.000 You should go do it yourself, or you should tell me, and no one will try to figure it out. 01:10:27.000 --> 01:10:32.000 But I don't. I don't have any immediate insights on that one. 01:10:32.000 --> 01:10:39.000 Yeah, the bunch of comments from it seem like more than like comments and questions from Glenn Lengthston. 01:10:39.000 --> 01:10:45.000 So maybe I'll let you read those and see if you wanted to comment on any of those. 01:10:45.000 --> 01:10:59.000 Okay. 01:10:59.000 --> 01:11:05.000 Okay, so. 01:11:05.000 --> 01:11:04.000 One is the question of, do I think? The second question one way? 01:11:04.000 --> 01:11:14.000 This effect is manifested. He's in writing new programs to replace old. 01:11:14.000 --> 01:11:21.000 Very often, in aronomy. The new programmer will start completely fresh, so that they understand everything. 01:11:21.000 --> 01:11:29.000 Then in practice, the new code will not be as well tested as the old housing new implementations much longer. 01:11:29.000 --> 01:11:36.000 To get to the same level of quality. 01:11:36.000 --> 01:11:45.000 Yes, especially I mean, the big problem is when the old programs I don't know if they're still old programs written in Fortran. 01:11:45.000 --> 01:11:53.000 But we're that was a big issue. 01:11:53.000 --> 01:11:58.000 You know. 01:11:58.000 --> 01:12:17.000 I think you could certainly use a method like this to help help quickly debug these new codes, or if you're willing just to trust the evolutionary process, I guess you could just let the old code evolve forever. 01:12:17.000 --> 01:12:21.000 But you know, even in biology we have lots of extinctions. 01:12:21.000 --> 01:12:28.000 And so I'm not. I don't have anything really intelligent to say about that. 01:12:28.000 --> 01:12:43.000 I guess now that I think about it, so I'll I think I'll pass on that one computer code should be better designed to enable evolution of programming languages and system design based on your model code would advance more rapidly by wrapping old code into packages that could be 01:12:43.000 --> 01:12:50.000 installed in new rather than starting fresh. The first part of this I absolutely agree with that. You know. 01:12:50.000 --> 01:13:14.000 If we really believed that these evolutionary processes are happening, whether they're done by humans are done by computers, it would be worth some thought about what the best languages languages are, and what kind of primitives would in you know what would enable evolution i've often wondered. 01:13:14.000 --> 01:13:20.000 You know, could you design a programming language that had higher or lower mutational robustness? 01:13:20.000 --> 01:13:25.000 And how much would be good. I don't have the answers to those things. 01:13:25.000 --> 01:13:33.000 I think people do already wrap old Code into packages that can be installed in new systems rather than starting freshman. 01:13:33.000 --> 01:13:43.000 I think that's that's a fairly common technique, as I know as I understand it. 01:13:43.000 --> 01:13:49.000 Thank you. See any other questions. 01:13:49.000 --> 01:13:57.000 Oh! This is! 01:13:57.000 --> 01:13:54.000 Please go ahead. 01:13:54.000 --> 01:14:09.000 Oh, I'll take the last question, does computer science education need to change, to encourage more interdisciplinary exploration? 01:14:09.000 --> 01:14:16.000 I say yes, and I have 2 thoughts in this space. 01:14:16.000 --> 01:14:25.000 The first thought is, and this is somewhat based on my own intellectual history. 01:14:25.000 --> 01:14:36.000 I think that grafting on a little interdisciplinary, you know, seasoning after someone has already received a Phd. 01:14:36.000 --> 01:14:47.000 Is probably less successful than introducing interdisciplinary challenges and thoughts, and all of that at the undergraduate level. 01:14:47.000 --> 01:15:01.000 So I'm sort of in favor of pushing interdisciplinary education down as early in the program, in someone's education as we can. 01:15:01.000 --> 01:15:06.000 I think computer science is. You know, we're we're challenged because our field is you know, expanding, it's just exploding. 01:15:06.000 --> 01:15:18.000 So much that yeah, I don't know about your departments, but you know what constitutes core computer science. 01:15:18.000 --> 01:15:29.000 You know, that's those that's fodder for a faculty to argue about for an entire year, and at the same time we are being encouraged in part by the Nsf. 01:15:29.000 --> 01:15:35.000 And in part by you know where science is taking us to interact with. 01:15:35.000 --> 01:15:44.000 You know the immediately adjacent fields, like cognitive science and psychology, and and things like that. 01:15:44.000 --> 01:16:01.000 But also with, I think, anthropology and sociology, and so we're sort of being forced to an ethics, you know, to be reaching out more and at the same time we feel like we have more and more to teach in our core. 01:16:01.000 --> 01:16:04.000 And so. 01:16:04.000 --> 01:16:09.000 How we do that, I think, is a real question. You know. 01:16:09.000 --> 01:16:18.000 I think one answer is, we don't try to teach people everything they might need to know, but we teach them how to get what they need to know. 01:16:18.000 --> 01:16:27.000 And you know how to be critical readers, and how to acquire new skill sets rather than thinking that they have to get all those skills into our classes. 01:16:27.000 --> 01:16:28.000 But yeah, it's a big challenge. But the answer my answer is, yes. 01:16:28.000 --> 01:16:35.000 In capital letters. 01:16:35.000 --> 01:16:39.000 I would agree with that. We have one more question for Michael Edman. 01:16:39.000 --> 01:16:40.000 Okay. 01:16:40.000 --> 01:16:46.000 Have you looked at the way modern deep learning systems that are working in particular? 01:16:46.000 --> 01:17:02.000 I'm wondering if you perceive anything evolutionary about the trend towards over parametization, putting a lot of lots and lots of randomly initialized units way more than needed to actually solve the problem. 01:17:02.000 --> 01:17:16.000 Is there a connection is? If there's a connection? Might there be better ways of training these systems by recognizing the connection? 01:17:16.000 --> 01:17:25.000 Well, the answer is, I haven't looked very hard I think it's a really intriguing suggestion. 01:17:25.000 --> 01:17:45.000 I have some vague thoughts about, you know there's some very kind of fundamental equations in population genetics that relate population size to effective mutation rate and selective pressure. 01:17:45.000 --> 01:17:49.000 And I've been kind of interested in whether you could build. 01:17:49.000 --> 01:17:55.000 Build models that would let you study the effects. 01:17:55.000 --> 01:18:07.000 See if you could measure those kinds of effects based on how, how, how big the training data set is, or how many people have contributed to the data set. 01:18:07.000 --> 01:18:07.000 I haven't actually thought very much about this over parameterization problem. 01:18:07.000 --> 01:18:17.000 It. Yeah, if you have, if you have deeper thoughts about it, please send them to me. 01:18:17.000 --> 01:18:20.000 I don't know. I guess I should have gotten back. 01:18:20.000 --> 01:18:25.000 Oh, hang on here! Should get back to my email address in case anyone wants to email me, I do have it down here. 01:18:25.000 --> 01:18:31.000 At the end, I think. Yes. 01:18:31.000 --> 01:18:40.000 So we'd love to love to hear any thoughts on that front. Michael. 01:18:40.000 --> 01:18:45.000 Wonderful. Well, we're getting close to the end of our time. 01:18:45.000 --> 01:18:55.000 And if no more questions. So maybe this is a good time to thank Stephanie again for an absolutely brilliant talk. 01:18:55.000 --> 01:19:00.000 I really, I learned a lot. So thank you very, very much. 01:19:00.000 --> 01:19:06.000 And I believe this in office between 3 and 4 Eastern. 01:19:06.000 --> 01:19:16.000 That will be coordinated by Michael. Let me this afternoon. So thank you again, and I look forward to seeing in the afternoon. 01:19:16.000 --> 01:19:28.000 Yeah, well, thank you, everyone. Thank these were great questions. And I do just wanna say this was such an honor and privilege to be able to give this lecture. So thank you. 01:19:28.000 --> 01:19:35.000 Thank you very much.