Evolutionary fuzzing is the state of the art.
It's an application of genetic algorithms to make smarter and better and faster fathers to understand
how it works.
Let's talk about genetic algorithms and how they model evolution in their genetic algorithm.
We have something called a population which consists of individuals.
In our case individuals are fuzzing inputs.
These individuals have a fitness function which is a measure of how good they are for fuzzing.
It might be some metric we're using to assess how good an input is.
So we might say that an input is good when it causes a crash.
Or we can say that's good when it covers the most code or it's good when it covers the most new code
or some other variation the less fit individuals get called out the die whereas the more fat ones remain
and the language just means that inputs that we're not interested in have low fitness.
We're not going to be reusing these individuals that do remain that survive because of high fitness
then reproduce.
So you pick pairs of individuals and those will reproduce to create a hybrid or genetically speaking.
Genetically speaking they'll will do B combination of their genes for fuzzing.
We might take our two inputs that scored high on our metric and then combine them somehow.
For instance we might take the initial segment of one and replace of the initial segment of the other.
And this will create a new input so an offspring in the language of biology in addition so that you're
not just shuffling the same data over and over Balaji introduces mutations and mutations you have all
your genes.
But there were some small probability something random happens and it introduces new genes.
And new structures and this allows your gene pool to expand to other possible individuals that were
not already present in the gene pool for phasing.
We might take our input and then perform some mutation and I'll create a new input which we will then
retain.
And this basically describes the main ideas of genetic algorithms.
There should be some fitness function there should be some method for recombination.
There should be a method for mutation and there should be a phase where the population gets called out.
So note that this is the method used for AFL State of the art father.
So now let's see how we can use it ourselves.
How this works so I'll be using the same function we're working with earlier CGI decoder and here's
all the tracing functionality.
Now go to the final class of an individual some member of that population and an individual is going
to have some value.
So when I'm fuzzing the CGI decoder it's going to be some string.
That's the value and I'm also going to record its coverage.
I'm going to use coverage for fitness and it's going to have a numerical score for its fitness.
So let's say that I'm initializing it I give it a value
which will be substring and then I try to compute the coverage using our functions well before the reason
to try and not a guaranteed success.
Is that it could be actually an input that causes the CGI decoder to crash which is what we're looking
for.
But in case that happens then I will start recording the coverage and lines
I'll record what the type of bargains printed out for our reference and I'll be recording all the coverage
in a dictionary.
And the reason for that is that I want to make sure that I'm keeping count of the coverage of how many
times each type of coverage takes place and I'll be using that in my fitness function.
So if for instance lines 1 2 3 get covered many times I want to make sure that these inputs don't get
repeated too much so I'll be using that in my fitness function.
Initially fitness will be just 9 so discuss this stuff in more detail but for now just bear with me
another function I want just to be able to print to be able to see the values I mentioned the value
coverage and fitness.
And then I want to be able to compute the fitness and the formula I've decided on it makes the most
sense for the application here is for it to be equal to the reciprocal of the number of times that the
coverage is covered.
So again if lines 1 2 3 get covered many times together in the same pattern then I want to make sure
that this side type of input sees a low fitness so that it is less likely to go on to the next generation
because I don't want it to be repeated on the other hand coverages that rarely take place will have
high fitness which is what I want.
So they get explored further.
So this is my individual class which will make up my population.
Now I'll be wanting to keep track of the important samples.
So those are samples that produce new coverages and then be covered dict.
We'll be keeping track of how many times each coverage was covered so that I can use it in my fitness
calculation more to define a function called add to coverage dict.
And it does what it sounds like.
It takes the value and it simply increment the counter.
And in fact we are referring to it even earlier.
So where we instantiate an individual or calculate it coverage and then we'll add it to the dictionary.
Now I'm going to define something called the carrying capacity which will determine the size of the
population.
Basically I will allow the population to grow but then I will kill off.
Call the lower fitness individuals until I'm back down to 100.
So the population always goes back to 100.
Once it goes past 100 they'll go back to 100 and this allows me to focus the year on the most promising
inputs as opposed to a huge number of them where many are not promising I'm going to define an initial
seed which will be the initial members of my population and this will be a couple your cells that seem
to be working.
So then my population will consist of the individuals instantiated on these you or else another function
I'll be wanting.
Is the update fitness scores function which will allow you to.
Which will allow me to update all the fitness scores we'll see that in more detail soon enough.
I also aren't a convenience function that will just show me the information about my population.
This is for debugging purposes and for explanatory purposes.
And I'll also find a get fitness course function which will give me an array of all the fitness scores.
And the reason is that I'll be wanting to sample from it because the fitness is the fitness scores will
be used in a pub ballistic manner.
I won't just be taking the highest fitness individuals but rather the highest fitness individuals will
be more likely to carry on and reproduce.
But there is no guarantee just like in life I'll be defining a function called sample pair for reproduction
and it does what it sounds like it will sample a pair from my from my population based on the fitness.
So first that's going to get the fitness scores then it will choose one individual based on the probability
distribution from a fitness course and then another individual.
And what we're going to do is pair them up and perform recombination.
So once have individual on an individual to I'm going to pick a random point in the string and then
I'll simply swap the first part of one with the first part of the other and then I'll get to New offsprings
we'll see this as an example soon enough and let me update the fitness scores.
In other words initialize them.
Now let's take a look finally at what they look like.
So this year well here gets this code coverage and this one has the same code coverage.
And the third on the same code coverage as well and their fitness scores are 33 percent ish one third
like it should be.
Now we're going to undergo our population is going to undergo a recombination which will later on put
into a loop.
But for now basically what we do is take our population.
We combine half using the methods we just defined so sample a pair for reproduction.
We combine them add them to the new population and then update the scores and then we have a new population.
So let's see what that looks like.
I take my current population which you're seeing here consisting of three inputs and I'm combining and
now that's printed and you see there are a couple new individuals there are no one two three four five
5 members in the populations that 2 are new and they also happen to have the same coverage but that's
OK.
We'll keep going and we can look at them and see.
So in the initial population we had one question mark here.
Now we have two individuals with the question marks and they're different.
You see the ending here has this to G and this one does not.
So you can tell these guys were some recombination happened there.
And if we look at this a little closer we'll be able to tell which ones were combined.
But that's not too important.
Now.
Next let's introduce mutation.
So pick a probability of mutation because mutation is a very powerful thing.
You take some individual regardless of how fit they are you're going to mutate them and now they can
be extremely unfair.
So you can take something really good and then make it really bad for that reason we got to be careful
about how much mutation we're doing.
But at the same time we need mutation so that we don't have too much constraints on the genome.
It allows us to explore more.
So I'm going to recall our functions from the mutations lesson delete insert swap randomize and a convenience
function here.
Produce a random character which will simply pick a random character and then I'm also going to recall
I mutate function which chose at random from these types of mutations and then repeated this for no
mutations times.
And now we are ready to define the mutation phase in which we loop over the whole population looking
at each individual.
And we flip a coin not a fair coin but a coin that's biased using this constant and if it flips one
way then we will mutate the individual.
So we'll apply the mutation and otherwise we will not.
And I will update the fitness because we have changed the population so let's apply mutation and take
a look at what happens
so it doesn't look like much has happened.
Or at least it's hard to find.
But if you look closely you'll see here is Google Now it's Google that's fine.
That's not a problem.
But the coverage is still the same.
Now we're going to define the calling phase in which we kill off individuals that are less fit.
So what we're gonna do is look at whether it's at carrying beyond the carrying capacity or not which
we said to be 100.
Now we're going to get the distribution of fitness is we're going to pick up to Capital an individual
exactly capital and individuals according to the fitness.
So now you see that the more fit individuals are more likely to be retained and the less fit wants less
likely to mutate and then that's what we do in our case we'll be retaining everyone because we don't
have carrying capacity just yet.
So now we run our calling phase for be exactly the same because nothing was called.
And what we just did complete one generation of our algorithm for evolution.
So we started off all the way here with the seeds and we grew our population.
In this case to five members from three and we added some mutations and now if you just repeat this
over and over again you'll see that the coverages will change and we will find bugs and these things
do evolve with time.
So we're going to set a number of generations and I'll be iterating.
So for each generation go through all these phases and let's run this so population generation 0 1 2
3 4 5 and then generation 5 already caught some error so value heir with this input here.
And there's lots of that.
And as you can see even though there is a ton of it eventually it stops doing as many value errors and
that's because of the way we gave reciprocal weight to more frequent coverages.
So the value air coverage was increasing in frequency in the dictionary.
And since we're taking the reciprocal it becomes less and less likely that these individuals survive.
So then it evolved and then now we've found this index error which is actually an error.
We are not expecting so the value error is something you expect.
But there is nothing said about index error and we could see there's more stuff going on.
And the end of the evolution.
Now it can take a look at what went on in by looking at the important samples.
And that's a representative of each coverage.
So if I look at the coverage dictionary
you can see the different types of coverages that have taken place and the important samples are just
representatives one from each.
So for example if you were to run this individual then it would get this coverage.
And if you're on if you were to run this one then you would get this coverage and so on and now it can
take a look at this index air which is a genuine bug.
The whole point of finding the whole point of finding and we can even fur to adhere and see what happened
in more details
and we look and we see that we are getting string index out of range.
And the reason is that if we look here we see that if there is a percentage sign then the next two characters
should be existent but they're not.
For instance I can also put in this input and that still doesn't work.
But if I add another character then it's fine.
So basically our buzzer found us a real vulnerability and it tells us that there's actually a bug in
our code.
So congratulations to us who successfully built up from scratch and executed an evolutionary phase and
found a vulnerability in a piece of code.
Next up we'll be learning how to use the AFL.