Absolutely as well. Good morning, everybody, as you may have heard.
Hmm!
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.
Professor Stephanie Forrest. Stephanie is professor of Computer science at Arizona State University, where she directs the Biodesign Center for biocomputation, security and society.
Our research focuses on the intersection of biology and computation, including cybersecurity, soft venture, and biological modeling.
She's a member of the Santa Fe Institute.
External faculty, and served at the Us. Department of State as a senior science advisor for cyber policy.
She has a BA. From St. John's College, and an Msn. Phd.
From University of Michigan Stephanie has received a number for one, including the 2,023.
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
and 11. She also has the Nsf. President to investigate, Award.
She is a felified triple E, and a member of the Computing Research Association.
Board of directors. Where she chairs. It's Government Affairs Committee.
So without any further delay let me hand it over to you, Stephanie.
Over to you.
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.
Looking at computation through the biological lens, can help us build better computer systems and understand the ones we have.
Except now my slides are not advancing just a minute.
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.
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
to the University of Michigan and Phd.
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
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.
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
accident fell into this professor position at the University of New Mexico, and that's where I came up through the ranks.
It was. It is a computer science department, a very, also very interdisciplinary, unique department.
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
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.
And the other, I'd say, big impact on my career.
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.
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.
But it was looking back on in a very kind of unusual letter.
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
fuzzy vision, and turn it into, turn it into a real research program.
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.
And I'm very grateful for those as well, and for the wonderful program officers that that I've worked with throughout the years.
I think 2 other things that just happened at the right time.
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
years later I might have had a very different career, and then the web.
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.
I had to find me and come to an unranked department in the desert with a largely unknown professor, and take their chances.
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.
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.
I always said certain had to earn my life as a real computer scientist.
And that often means emphasizing the biologic inspiration or the biological thought.
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.
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.
Okay. So now for the talk.
My research takes the perspective that that by all, as I mentioned that biology and computation have a lot to say to one another.
And I've really emphasized 2 major themes during my career.
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.
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.
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.
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.
That's really looking at software as an evolving system.
And so. Chapter 2 of my talk will be about what I call micro level.
Evolution that is using evolutionary computation methods quite directly to improve software.
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.
And I decided to spare you all my enthusiasm and details about how the immune system actually works.
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.
I mean numbers of different replicating pathogens.
And these pathogens, whether they're viruses or bacteria or parasites.
But viruses and bacteria in particular, are replicating very quickly.
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
also just before I jump into this, wanna mention that there's many, many other defense systems in biology.
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.
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.
We will be talking about what's known as the adaptive arm of the vertebrates.
Immune system. And I just want to focus on a few of the.
Pieces of this system that I think are most compelling to computer science.
And so the first is that the immune system has several different learnings.
Learning, mechanisms that uses learning in different ways.
First of all, it has to learn the distinction between self and other when it jumped.
Detectors and but detectors are things like bessels and T cells and antibodies, thingsy things that you've heard of.
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.
Selections. And that's something that we built built algorithms out.
If we even got a patent and started to company, and and etc., etc.
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.
Then, if you're infected with a with a virus, or I will just say pathogen, and by that mean virus or bacterium.
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.
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.
And then finally over evolutionary time. It has evolved biases towards particularly important classes of threats.
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
piece, it. It recognizes something it's seen before.
It knows it's bad, and so it requires very quickly and very aggressively, so much so.
You usually don't know that yourself, and the the memory is also what immunologists refer to as cross, reactive.
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.
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
it's one of the principles that underlies our vaccine.
Still today. The next thing about the immune system that I love this is probably the thing that really got me hooked.
Is it uses combinatorics. It has this problem.
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.
And so it uses this very cute trick of taking little pieces of genes and and splicing them together.
With noise at the junctions, and it's exactly what a computer scientists might think of doing.
And finally, the whole system is massively parallel and distributed spatially throughout our body.
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.
Okay, so.
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.
And then think of algorithms that that would implement them. And what kinds of problems they would be good for.
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.
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.
We worked on that earlier in in my career, and the secondary response works because of it's essentially a signature detail.
And we've had those have those in cybersecurity for many years.
A a second idea is the idea of a heterogeneous defense, and we see this in cybersecurity.
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.
And the other thread is the thread that comes from in version programming, and later in variance systems that were used for cybersecurity.
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.
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
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.
And that's something, I think we could do more with in cybersecurity.
The third idea is the idea of second signals, and I think the that's used in lots of places in immunology.
Probably the easiest example is the helper T cell, which which?
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.
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.
And that's really the I idea behind 2 factor authentication and many similar systems.
And then I wanna talk. Turn to this idea of a technological ratchet.
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.
But I think is important. I'm just gonna explain it in my own words, and probably abuse the biology somewhat.
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.
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
underneath them, decayed a bit. And that's for me.
Raises the question when we talk about defense in depth.
But how many layers of defense are actually optimal before we start getting toinishing returns, Steve.
Frank has pointed out a nice example of this in in our space, which is the idea of a raid array. You know.
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.
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
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
authentication. I'm even less protective, and I think we may be seeing this process, probably throughout computing, but certainly insightsbersecurity.
And it does raise the question to me of, you know, could we formalize this?
There are a lot of great models in in biology, a lot of nice mathematics that are fairly simple.
And anyway.
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.
And so that leads me to chapter 2 of the talk where we are going to talk about the role of evolution.
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.
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
the second idea is macro level evolution, and the feature one is micro well, I guess I didn't say the first one.
Micro level evolution is the idea of using evolution much more directly on software.
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.
Okay, so that's that's sort of the preview of the rest of the talk.
First I'm gonna talk about this what I'm calling Michael Evolution.
And at that level my collaborator, Wesley, Onceer, from the University of Michigan, and I have worked together for a little over a decade.
Now developing methods for automatically repairing software failures.
Both bugs and security vulnerabilities.
And he spent a great collaborator. All the work I'm gonna talk about.
We've done. Together. We began this work with 2 of our students, who, when?
And Claire Vu is now, I think, George Mason University, and Claire is at Carnegie Mellon, and Claire made this picture years ago.
And it's still the best picture that I the best way I have to explain quickly how this system works.
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.
It's a set of tests that have input output pairs.
And the idea is you run the program on each test and check to make sure it produces the right output.
In this case we know that the program has a bug, because one of its test cases is failing.
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.
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.
We recirculate into the population with additional mutations and sometimes recombinations, and after just a few rounds of this process.
Sometimes it's few as 10. We often about half the time can produce a problem that passes all of the test cases.
And that was really remarkable to me when we first did it.
Needless to say, other people, working in evolutionary computation, had had similar ideas.
But we introduced several innovations that I think actually made it work.
And our system was the first one that really Hi, I think I'm safe.
Saying this worked worked on large, naturally occurring open source programs with naturally occurring bugs. Okay?
So some of our tricks, where we started with a working program.
Most of the people in Geneva programming start with with randomly generated programs.
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
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.
Now people often do move or replace, and actually a lot of people only use delete and copy the second.
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.
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.
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.
And then the third piece of secret sauce was that we restricted our mutations to only change code.
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.
And then the fourth thing isn't isn't due to us.
But it is a fact of the world that most bugs can be fixed with very, very small number of edits.
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.
Moved this statement here, shown in Ard down to here, and that repaired the but it actually did it in a couple of steps.
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.
And but it did that very quickly. Okay, usually, I just stop and see if there's questions.
But I'm just gonna plow on and take the questions at the end.
So that's the same in a nutshell.
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
say, a legitimate sub area of software engineering. And so there have been, we did early on several large kind of systematic empirical studies.
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.
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
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.
I don't know. 2,018, 2,019.
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.
There are just a number of caveats. I don't want you to think that it's a 100% perfect.
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.
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
ground, truth that that needs to be repaired. And so people have called this overfitting.
It's a little bit of a Miss Nowhere, but that's a big concern in the field.
The whole question of how it evaluate repairs.
We do have a standard now which I personally think is not a great one.
But how do you know? How do you judge if a repair is correct or not?
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.
And I think over time the field will address those and get to them.
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.
Okay, so this is an example of obeying the letter. You know.
But fighting a repair that passes a test case passes the test suite, but doesn't necessarily deal with what the programmer wanting.
Hi! I'm just not really interested. So to me it is not that surprising that big.
Let me just check my time. Yeah, it is not that surprising that, hey?
Large language model that can communicate with a wide variety of people.
In natural language, should be able to find, you know, single line repairs to software.
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.
But it is still surprising to me that you can make random mutations to code and fairly quickly find.
Use that method to find repairs. And yeah, it's just it.
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?
And you know, what? What is it about?
Software that makes it amenable to this. This evolutionary computation approach to random mutation and other things.
And so that's actually what I'm most interested in over the past few years.
And my approach has been to learn about properties, that biologists think are important in evolution, and then look for them in software.
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.
And I've I've had 3 s. You've done most of this work, Eric Schilte started with the work on mutational Robustness.
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.
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.
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.
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.
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.
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.
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.
So we started out, asking whether there were neutral mutations in software.
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.
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.
In the execution path that is executed by at least one of the test cases.
So we're not mutating dead code and then we're gonna ask whether or not it still passes the test suite.
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.
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.
Those mutations don't change the behavior of the program on the test cases, and.
I found that really surprising, and I don't.
I still don't actually know why it's true.
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.
2 of which I'm gonna tell you about in the next few slides.
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
it's how many test cases they' or will have some other metrics in.
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
this, the evolutionary process can then climb that peak, and we can find high fitness solutions.
So we've been. We've used this in a variety of settings.
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.
So this first piece of this is Joe Renzello's work, and remind myself on a second.
So this and this. I'll just tell you the experiment first, and you can probably read the slide.
You start with an original program shown in black here every.
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.
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.
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.
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.
So that we had this like held out test for that bug.
And so Joe, using the original test suite, generated this graph, and all of the colored points represent.
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.
So the network is somehow connecting these diverse repairs.
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?
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.
They all tend to search very, very close to the original program.
And so the question is, where should we be searching a neutral space?
And let me just check my time next I've got to speed up.
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
sample over and over and over again. How many of your samples actually constitute a repair for the bug?
That is how dense are those colored points at different distances from the orange.
Joe's way of doing it was a little different.
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.
Some mutations away from the original program.
So if you were doing a single mutation, which is what most methods do.
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.
But it doesn't go on forever I you know there's you start eventually getting interactions between these different edits, negative interactions.
And so the curve tails off. And so, yeah, we fit the curve.
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.
And developed an algorithm called multiplicative weights, Repair.
It's not actually a genetic algorithm, but it does use the mutations.
And and that's that's about to come out in Nacm transactions to okay.
So that's been very interesting and if I had more time I could tell you a lot more about that.
But instead, I'm gonna move on to optimizing Gpu code.
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
them, but they're very hard to optimize. And so Jerry's idea was kuda code.
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.
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?
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?
And so he implemented this thing. I was pretty skeptical.
I have to say, not knowing that much about Gpus, because I know that compilers are really good.
But in fact it on the this set of benchmarks from their community it found an average of 49% speed up.
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.
We don't we don't. We don't know why.
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.
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
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
of runs by the way. But this first run, this is sort of amazing, because first run found.
A version of the program that is still correct. And and this is an example.
Of our program like sorting. That is extremely well tested.
And so we're not worried about.
No, not not concerned that. We're confident that our that are optimized versions of the programs are actually correct.
But anyway, he found a version that runs 28.5% faster, which was very impressive and surprising to our human expert.
And so then he did. This is why he's a great student.
He was able to do a lot of analysis and I'm skipping a few steps.
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.
This is, this is the big one, but it's more complex.
But just to give you the idea. If you have mutation 0.
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.
So this this 0 mutation gives you less than 1% improvement on its own.
The eleventh mutation. If it is only if it's done by itself, it breaks the program.
Program doesn't complete. But if you have both of those together, you get 2% improvement.
And then, similarly, for this thing, if you have these 4 mutations together, you get 15% of the speed up.
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.
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.
Instead of private registers, and don't ask me how it works.
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
memory access. It also found some. Redundant synchronizations.
Those have been better known, I think, in the literature, and in some cases found some unnecessary memory.
Initializations.
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.
And just sort of summarize the past few minutes we have found a variety of pieces of evidence in different settings.
The software has properties that resemble. I'm not gonna claim they are, you know, there, but resemble those of biological systems.
So things like mutation or robustness. Some of these properties are believed to be important for evolution.
And so question is, where do they come from? In software?
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.
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
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.
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.
So I think we at least can say we have all the ingredients.
Of evolution.
And it shouldn't be so surprising that we might have evolution when we consider what our software landscape looks like today.
So we have stack overflow that totally enables copying code from good code.
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.
Of software development that brings fitness, evaluation that is feedback from the users much closer to the development cycle.
And in all of these I think they're interested.
They're all interesting because they blend sort of human human engineering or human ingenuity with with these kind of evolutionary Darwinian mechanisms.
And so, I I think that's kind of interesting.
And the this idea that software somehow blends human engineering with evolutionary dynamics.
It's not really obvious. And it's, you know, many of you may be reacting against this.
I'll hear about that in the questions. I'm sure.
But it's it's not obvious, because it's glaring differences between evolution and engineering.
And Francois Jacko pointed these out many years ago.
He wrote a couple of papers that have this little phrase in it.
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.
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.
But in fact, when I look at the systems that we're building today, I see many, many examples of the 2 of them.
You know, evolutionary engineering, either working together either synergistically or in some cases at cross-purposes.
So antibiotic resistance is a great idea.
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.
And wouldn't it be great if we could account for that evolution when we were designing, designing the drugs?
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.
Some Darwinian, you know. Some of these genetic mechanisms with with engineering to produce useful, useful proteins and and other other substances.
There's all of synthetic biology. And one of my favorite examples.
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
do we also have? Oh, wait! Attack, I guess anyone have a separate slide for that attack.
Fuzzing and cyber security goes the other way.
We have these random mutations that we do to the inputs randomized algorithms, of course, are well known.
Some field of computer science. And I hope I've convinced you that software is a blend between evolution and engineering.
Okay. So I need to wrap up one of the one of the best practices for engineering systems in the context of evolution.
I I think this is a really important question that we should be thinking about.
And I think software is a great place to start thinking about it.
I should mention that the National Academy of Engineering has held this.
Some workshops on this theme of engineering and evolution, but their take is a little different from mine.
Went to one of these workshops, and I was kind of surprised.
They, the bulk of the discussion was about taking engineering methods and using them more directly, like in biomedicine.
And my view is what we need to do is appreciate.
Biology, and think a little differently about how we do our engineering.
And so all of these other things I think fit into that.
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.
I've given you some examples of that, and the science.
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
attributed to him. I've never been able to chase down where.
But anyway, as engineers, we would be foolish to ignore the lessons of a 1 billion years of evolution.
So thank you very much.
Thank you, Stephanie, for a reallyilliant talk.
Very, part-provoking. Let's give a virtual round of applause.
This technique for for the talk, and I'll open it up for questions.
There are a few in the so why don't we start with those?
And and we'll go from there first. One is.
Okay, do, do you want to read them to me, or do you want me to look in the how do you have?
Okay.
Let me read them out that we others can either missed, but I don't know if they can see the all of them.
So wonderful talk. Thank you. What is an example of a neutral editor?
And how are they generated?
Yeah? Great question. This is where I wish I had been in a live audience, so I could have handle that along the way.
So I I gave an example on that slide. Can you still see my slides?
Yes, we can.
Oh, wait just minute. I gotta get out of this.
Okay, just a minute.
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.
Just swapping those 2, whether you recruit on the left or the right doesn't really what order you do.
It doesn't really matter. So the mutations let me just get back up and look at this.
They're generated there, we're not doing anything special to generate them.
We just do the mutations that I described early on.
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.
So there's there's no special thing. This I guess.
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.
Thank you. There are a bunch of questions from Glen Langston.
Let me start with the first one with Gpu, with the Gpu optimization.
It seems like one would need a huge complete fitness test.
Yeah.
It could be that the optimize it could be that the optimize such that it would work perfectly except for one critical failure, mode.
Yeah, that's always that's not just a criticism of the Gpu optimization.
But that's a criticism of the automated repair work as well, and usually in the automated repair.
Context, I appeal to what I believe is practice and industry, which is, if it passes all the test cases, then we're okay.
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.
It's huge. It runs quickly, and it's on, you know.
It's such an important application in bioinformatics that people put a lot of effort into it.
You know it.
Yes, I mean you're only as good as your test cases until we have have someone of automatically testing the correctness.
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
code.
It's relatively easy to generate the invariance and then figure out how they're different between the original program and the repaired program.
And so you you can do things like that.
But I mean, my basic answer is most of the code we use isn't perfect, anyway.
But I realize that's not very satisfying to most people.
So I take that one.
Yeah, I'm gonna skip to a different question.
See from an anonymous attendee.
Do you think that you can identify a few mutants?
Combine them, run many generations and predict the potential outcomes, phenotypes.
Well, it. Okay. By identify a few mutants. I'm not exactly sure what the question means.
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.
Maybe the idea is to evolve from there. Yeah, that I've never tried that.
But that's that would certainly be like if you had a repertoire of mutations that you thought were useful for optimizing Gpus.
You know, there might be just a few tricks that kind of come along.
People. People in the automated repair space have designed.
There's a whole sub-RAM on templated repairs, where the mutation operators are really sort of filling in templates.
And that I, if I understand what the question is, that might be.
Response to the question.
Thank you. We have a question from Michael Littman.
I really like the debugging example you gave with test cases.
I used to select code modifications. How might programming change if this approach were incorporated as part of the development?
Yeah.
Ide instead of a debug time.
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.
Yeah, I think, having a little, I always thought, you know, like an eclipse or something.
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?
At least the the version that I work on it could propose multiple repairs.
And then you you could look at them. But I think the co-pilot people got there before I did.
Going back to a question on the team again by Glenn Langston.
The evolution concept is excellent for explaining existing features, buses exploring a comment.
But it's terrible at predicting exactly what the next generation will be.
Yes.
Bye!
There is a question.
Yeah, I may be okay. I'm I'm just trying to understand what the this this is.
Yeah.
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?
But it's not so good for predicting what's gonna be next.
If by prediction you mean exactly what the next generation of software is gonna look like, you're absolutely correct.
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
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.
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.
And so I think to me that makes it more like evolution, like real evolution, natural, naturally occurring evolution, I should say.
Liftfang has put in a couple of questions at the end.
Great talk, 2 questions. Naturally, evolution happens at a much larger scale and over a long period, time, period.
That should be dramatically.
How can we? Dramatically, yeah, expand the spatial intensity scale of software mutation automatically, how about computational power needed?
And the second question is sometimes unexpected. Mutation leads to significant evolution.
Change? What about unexpected software mutations?
Well, thank you. These are all great questions. So.
First of all, whenever I talk to biologists and say, Oh, yeah.
But you guys have these gigantic populations. We have to cheat because we have small populations.
They always say, Oh, no, there's lots of systems that you know.
Evolve quickly and have small populations, but generally I think you're right.
That evolution takes a long time, and the larger scale.
I. 2 answers to it. One is I think that's why this sort of macro level evolution is so interesting.
Cause. It is happening at a much larger scale, and and the innovation cycle is faster.
You don't, you know? Like, if you're thinking about the evolution of mammals, you don't have to wait.
However long it takes for a baby to grow up and have offspring.
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
unexpected me. So part, that's part one, part 2 on it, sometimes unexpected mutation leads to significant evolution.
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.
I think that was a great example of an unexpected change that, you know, had huge impact on our networking security.
So I think I agree with that.
Do you want me to go to the next one?
Yeah, I think, this. I can read it out. Thank you for your wonderful and inspiring talk.
Do you think it is possible to apply neutral mutations through pair safety issues of machine learning based systems like Chat Gpt.
If yes, could you provide some insights?
I don't know about safety. I do know that evolutionary algorithms are used more traditional versions of them.
Are used fairly extensively to design the architectures for these large marsh learning models in terms of safety.
I don't know. I've thought about using these models to ask other questions, but.
I I don't have a if you've got an idea for how to do it, either.
You should go do it yourself, or you should tell me, and no one will try to figure it out.
But I don't. I don't have any immediate insights on that one.
Yeah, the bunch of comments from it seem like more than like comments and questions from Glenn Lengthston.
So maybe I'll let you read those and see if you wanted to comment on any of those.
Okay.
Okay, so.
One is the question of, do I think? The second question one way?
This effect is manifested. He's in writing new programs to replace old.
Very often, in aronomy. The new programmer will start completely fresh, so that they understand everything.
Then in practice, the new code will not be as well tested as the old housing new implementations much longer.
To get to the same level of quality.
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.
But we're that was a big issue.
You know.
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.
But you know, even in biology we have lots of extinctions.
And so I'm not. I don't have anything really intelligent to say about that.
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
installed in new rather than starting fresh. The first part of this I absolutely agree with that. You know.
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.
You know, could you design a programming language that had higher or lower mutational robustness?
And how much would be good. I don't have the answers to those things.
I think people do already wrap old Code into packages that can be installed in new systems rather than starting freshman.
I think that's that's a fairly common technique, as I know as I understand it.
Thank you. See any other questions.
Oh! This is!
Please go ahead.
Oh, I'll take the last question, does computer science education need to change, to encourage more interdisciplinary exploration?
I say yes, and I have 2 thoughts in this space.
The first thought is, and this is somewhat based on my own intellectual history.
I think that grafting on a little interdisciplinary, you know, seasoning after someone has already received a Phd.
Is probably less successful than introducing interdisciplinary challenges and thoughts, and all of that at the undergraduate level.
So I'm sort of in favor of pushing interdisciplinary education down as early in the program, in someone's education as we can.
I think computer science is. You know, we're we're challenged because our field is you know, expanding, it's just exploding.
So much that yeah, I don't know about your departments, but you know what constitutes core computer science.
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.
And in part by you know where science is taking us to interact with.
You know the immediately adjacent fields, like cognitive science and psychology, and and things like that.
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.
And so.
How we do that, I think, is a real question. You know.
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.
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.
But yeah, it's a big challenge. But the answer my answer is, yes.
In capital letters.
I would agree with that. We have one more question for Michael Edman.
Okay.
Have you looked at the way modern deep learning systems that are working in particular?
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.
Is there a connection is? If there's a connection? Might there be better ways of training these systems by recognizing the connection?
Well, the answer is, I haven't looked very hard I think it's a really intriguing suggestion.
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.
And I've been kind of interested in whether you could build.
Build models that would let you study the effects.
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.
I haven't actually thought very much about this over parameterization problem.
It. Yeah, if you have, if you have deeper thoughts about it, please send them to me.
I don't know. I guess I should have gotten back.
Oh, hang on here! Should get back to my email address in case anyone wants to email me, I do have it down here.
At the end, I think. Yes.
So we'd love to love to hear any thoughts on that front. Michael.
Wonderful. Well, we're getting close to the end of our time.
And if no more questions. So maybe this is a good time to thank Stephanie again for an absolutely brilliant talk.
I really, I learned a lot. So thank you very, very much.
And I believe this in office between 3 and 4 Eastern.
That will be coordinated by Michael. Let me this afternoon. So thank you again, and I look forward to seeing in the afternoon.
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.
Thank you very much.