(upbeat music)
- [Instructor] Evolutionary fuzzing is the state of the art.
It's an application of genetic algorithms
to make smarter and better and faster fuzzers.
To understand how it works,
let's talk about genetic algorithms
and how they model evolution.
In a 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 are 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 it'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, they die,
whereas the more fit ones remain.
In fuzzing language just means
that inputs that we are not interested in,
that 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,
they'll be 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 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,
biology introduces mutations.
So mutations, you have all your genes,
but then with 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 fuzzing, we might take our input
and then perform some mutation,
and that will 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 fuzzer.
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, I'm going to define a class
of an individual, some member of the 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 the 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 some string.
And then I try to compute the coverage
using our functions from before.
And the reason it's a 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, instead of recording the coverage and lines,
I'll record what the type of bug is,
print it out for our own 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.
And initially, fitness will be just none.
So I'll discuss this stuff in more detail,
but for now, just bear with me.
Another function I want is 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
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 type of input
receives 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 the covered dict will be keeping track
of how many times each coverage was covered,
so that I can use it in my fitness calculation.
I'm going to define a function called add_to_coverage_dict.
And it does what it sounds like,
it takes a value and it simply increments the counter.
And in fact, we are referring to it even earlier.
So when we instantiate an individual,
we'll calculate its coverage,
and then we will 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'll 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, it'll go back to 100.
And this allows me to focus the fuzzer
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 URLs that seem to be working.
So then my population will consist of the individuals
instantiated on these URLs.
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 want a convenience function
that will just show me information about my population.
This is for debugging purposes
and for explanatory purposes.
And I'll also define a get_fitness_scores 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 fitnesses, the fitness scores will be used
in a probabilistic manner.
I won't just be taking the highest fitness individuals,
but rather the highest fitness individuals
who'll be more likely to carry on and reproduce.
But there's 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 population
based on the fitness.
So first, it's going to get the fitness scores,
then it will choose one individual
based on the probability distribution
from the fitness scores,
and then another individual.
And what we're going to do is pair them up
and perform recombination.
So once have individual1 and individual2,
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 I'll get two new offsprings.
We'll see this as an example soon enough.
And let me update the fitness scores.
In other words, initialize them.
And then let's take a look finally at what they look like.
So this URL here gets this code coverage,
and this one has the same code coverage,
and the third one, the same code coverage as well.
And their fitness scores are 33%-ish,
1/3, like it should be.
Now, we are going to undergo,
our population is going to undergo a recombination,
which we'll later on put into a loop.
But for now, basically what we do is take our population,
recombine half using the methods we just defined,
so sample a pair for reproduction,
recombine them, add them to the new population.
And then update the scores,
and there you 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 recombining.
And now, let's print it.
And you see there are a couple new individuals.
There are now one, two, three, four, five.
Five members in the population, so two are new.
And they also happen to have the same coverage.
But that's okay.
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 2g,
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 right now.
Next, let's introduce mutation.
So I'll 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 unfit.
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_random_character,
which will simply pick a random character.
And then I'm also going to recall our mutate function,
which chose at random from these types of mutations,
and then repeated this for num_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 closer,
you'll see here it used to be google,
now it's oogle.
That's fine. (snickers)
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 going to do is look at whether it's at caring,
beyond the caring capacity or not, which we set to be 100.
Then we're going to get the distribution of fitnesses.
We are going to pick up to capital N individuals.
Exactly capital N individuals, according to the fitness.
So now you see that the more fit individuals
are more likely to be retained,
and the less fit ones, less likely to be retained.
And then that's what we do.
In our case, we'll be retaining everyone
because we don't have caring capacity just yet.
So then we run our calling phase,
should be exactly the same because nothing was called.
And what we just did completes one generation
of our algorithm, of our 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 we can just repeat this over and over again.
You'll see that the coverages will change
and we'll find bugs, and these things do evolve in time.
So I'm 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 error,
with this input here.
Then there's lots of that.
And as you can see, even though there's 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 error 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 it found this index error,
which is actually an error we are not expecting.
So the value error is something to expect,
but there's nothing said about index error.
And we can see there's more stuff going on,
and the end of the evolution.
And now we can take a look at what went on
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 were to run this one,
then you would get this coverage, and so on.
And now we can take a look at this index error,
which is a genuine bug, the whole point of finding,
the whole point of fuzzing.
And we can even refer to it here
and see what happened in more details.
And then 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 in another character, then it's fine.
So basically, our fuzzer found us a real vulnerability,
and it tells us that there's actually a bug in our code.
So congratulations to us,
we've successfully built up from scratch
and executed an evolutionary fuzzing
and found a vulnerability in a piece of code.
Next up, we'll be learning how to use AFL.