{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# Greybox Fuzzing\n",
"\n",
"The first version of [American Fuzzy Lop](http://lcamtuf.coredump.cx/afl/) (AFL) was released on November 2013. Since then, AFL has become one of the most successful fuzzing tools and comes in many flavours, e.g., [AFLFast](https://github.com/mboehme/aflfast), [AFLGo](https://github.com/aflgo/aflgo), and [AFLSmart](https://github.com/aflsmart/aflsmart). AFL has made fuzzing a popular choice for automated vulnerability detection. It was the first to demonstrate that vulnerabilities can be detected automatically at a large scale in many security-critical, real-world applications.\n",
"\n",
"\n",
"Figure 1. American Fuzzy Lop Command Line User Interface\n",
"\n",
"In this chapter, we are going to expand on what we have learned in the chapter on [Mutation-based Fuzzing](MutationFuzzer.ipynb). We will explore the greybox fuzzing algorithm behind AFL and how we can exploit it to solve various problems for automated vulnerability detection."
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"**Prerequisites**\n",
"* [Fuzzing: Breaking Things with Random Inputs](Fuzzer.ipynb)\n",
"* [Mutation-based Fuzzing](MutationFuzzer.ipynb)\n",
"\n",
"We'll have a few refreshers on these topics throughout this chapter. So, don't worry if you don't satisfy the prerequisits."
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": true,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Ingredients for Greybox Fuzzing\n",
"\n",
"### Background\n",
"AFL is a *mutation-based fuzzer*. Meaning, AFL generates new inputs by slightly modifying a seed input (i.e., mutation), or by joining the first half of one input with the second half of another (i.e., splicing).\n",
"\n",
"AFL is also *greybox fuzzer* (not blackbox nor whitebox). Meaning, AFL leverages coverage-feedback to learn how to reach deeper into the program. It is not entirely blackbox because AFL leverages at least *some* program analysis. It is not entirely whitebox either because AFL does not build on heavyweight program analysis or constraint solving. Instead, AFL uses lightweight program instrumentation to glean some information about the (branch) coverage of a generated input.\n",
"If a generated input increases coverage, it is added to the seed corpus for further fuzzing.\n",
"\n",
"To instrument a program, AFL injects a piece of code right after every conditional jump instruction. When executed, this so-called trampoline assigns the exercised branch a unique identifier and increments a counter that is associated with this branch. For efficiency, only a coarse branch hit count is maintained. In other words, for each input the fuzzer knows which branches and roughly how often they are exercised. \n",
"The instrumentation is usually done at compile-time, i.e., when the program source code is compiled to an executable binary. However, it is possible to run AFL on uninstrumented binaries using tools such as a virtual machine (e.g., [QEMU](https://github.com/mirrorer/afl/blob/master/qemu_mode)) or a dynamic instrumentation tool (e.g., [Intel PinTool](https://github.com/vanhauser-thc/afl-pin)). For Python programs, we can collect coverage information without any instrumentation (see chapter on [collecting coverage](Coverage.ipynb#Coverage-of-Basic-Fuzzing)).\n",
"\n",
"### Mutator and Seed"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import random\n",
"import fuzzingbook_utils\n",
"from Coverage import Coverage, population_coverage"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"First, we'll introduce the Mutator class. Given a seed input *inp*, the mutator returns a slightly modified version of *inp*. Later, we extend this class to consider the input grammar for smart greybox fuzzing."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"class Mutator(object):\n",
" \n",
" def __init__(self):\n",
" self.mutators = [\n",
" self.delete_random_character,\n",
" self.insert_random_character,\n",
" self.flip_random_character\n",
" ]\n",
" \n",
" def delete_random_character(self,s):\n",
" \"\"\"Returns s with a random character deleted\"\"\"\n",
" if s == \"\":\n",
" return self.insert_random_character(s)\n",
"\n",
" pos = random.randint(0, len(s) - 1)\n",
" return s[:pos] + s[pos + 1:]\n",
"\n",
" def insert_random_character(self,s):\n",
" \"\"\"Returns s with a random character inserted\"\"\"\n",
" pos = random.randint(0, len(s))\n",
" random_character = chr(random.randrange(32, 127))\n",
" return s[:pos] + random_character + s[pos:]\n",
"\n",
" def flip_random_character(self,s):\n",
" \"\"\"Returns s with a random bit flipped in a random position\"\"\"\n",
" if s == \"\":\n",
" return self.insert_random_character(s)\n",
"\n",
" pos = random.randint(0, len(s) - 1)\n",
" c = s[pos]\n",
" bit = 1 << random.randint(0, 6)\n",
" new_c = chr(ord(c) ^ bit)\n",
" return s[:pos] + new_c + s[pos + 1:]\n",
" \n",
" def mutate(self, inp):\n",
" \"\"\"Return s with a random mutation applied\"\"\"\n",
" mutator = random.choice(self.mutators)\n",
" return mutator(inp)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's try the mutator. You can actually interact with such a \"cell\" and try other inputs by loading this chapter as Jupyter notebook: [Click here](https://mybinder.org/v2/gh/uds-se/fuzzingbook/master?filepath=docs/beta/notebooks/Greybox_Fuzzing.ipynb)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"Mutator().mutate(\"good\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now we introduce a new concept; the power schedule. A power schedule distributes the precious fuzzing time among the seeds in the population. Our objective is to maximize the time spent fuzzing those (most progressive) seeds which lead to higher coverage increase in shorter time.\n",
"\n",
"We call the likelihood with which a seed is chosen from the population as the seed's *energy*. Throughout a fuzzing campaign, we would like to prioritize seeds that are more promising. Simply said, we do not want to waste energy fuzzing non-progressive seeds. We call the procedure that decides a seed's energy as the fuzzer's *power schedule*. For instance, AFL's schedule assigns more energy to seeds that are shorter, that execute faster, and yield coverage increases more often.\n",
"\n",
"First, there is some information that we need to attach to each seed in addition to the seed's data. Hence, we define the following `Seed` class."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"scrolled": true
},
"outputs": [],
"source": [
"class Seed(object):\n",
" \n",
" def __init__(self, data):\n",
" \"\"\"Set seed data\"\"\"\n",
" self.data = data\n",
" \n",
" def __str__(self):\n",
" \"\"\"Returns data as string representation of the seed\"\"\"\n",
" return self.data\n",
" __repr__ = __str__"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Power Schedule\n",
"The power schedule that is implemented below assigns each seed the same energy. Once a seed is in the population, it will be fuzzed as often as any other seed in the population.\n",
"\n",
"In Python, we can squeeze long for-loops into much smaller statements.\n",
"* `lambda x: ...` returns a function that takes `x` as input. Lambda allows for quick definitions unnamed functions.\n",
"* `map(f, l)` returns a list where the function `f` is applied to each element in list `l`.\n",
"* `np.random.choice(l,p)` returns element `l[i]` with probability in `p[i]`."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import numpy as np"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"class PowerSchedule(object):\n",
" \n",
" def assignEnergy(self, population):\n",
" \"\"\"Assigns each seed the same energy\"\"\"\n",
" for seed in population:\n",
" seed.energy = 1\n",
"\n",
" def normalizedEnergy(self, population):\n",
" \"\"\"Normalize energy\"\"\"\n",
" energy = list(map(lambda seed: seed.energy, population))\n",
" sum_energy = sum(energy) # Add up all values in energy\n",
" norm_energy = list(map(lambda nrg: nrg/sum_energy, energy))\n",
" return norm_energy\n",
" \n",
" def choose(self, population):\n",
" \"\"\"Choose weighted by normalized energy.\"\"\"\n",
" self.assignEnergy(population)\n",
" norm_energy = self.normalizedEnergy(population)\n",
" seed = np.random.choice(population, p=norm_energy)\n",
" return seed"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's see whether this power schedule chooses seeds uniformly at random. We ask the schedule 10k times to choose a seed from the population of three seeds (A, B, C) and keep track of the number of times we have seen each seed. We should see each seed about 3.3k times."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"population = [Seed(\"A\"), Seed(\"B\"), Seed(\"C\")]\n",
"schedule = PowerSchedule()\n",
"hits = {\n",
" \"A\" : 0,\n",
" \"B\" : 0,\n",
" \"C\" : 0\n",
"}\n",
"\n",
"for i in range(10000):\n",
" seed = schedule.choose(population)\n",
" hits[seed.data] += 1\n",
"\n",
"hits"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Looks good. Every seed has been chosen about a third of the time.\n",
"\n",
"### Runner and Sample Program\n",
"We'll start with a small sample program of six lines. In order to collect coverage information during execution, we import the `FunctionCoverageRunner` class from the chapter on [mutation-based fuzzing](MutationFuzzer.ipynb#Guiding-by-Coverage). \n",
"\n",
"The `FunctionCoverageRunner` constructor takes a Python `function` to execute. The function `run` takes an input, passes it on to the Python `function`, and collects the coverage information for this execution. The function `coverage()` returns a list of tuples `(function name, line number)` for each statement that has been covered in the Python `function`."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from MutationFuzzer import FunctionCoverageRunner"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The `crashme` function raises an exception for the input \"bad!\". Let's see which statements are covered for the input \"good\"."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def crashme (s):\n",
" if len(s) > 0 and s[0] == 'b':\n",
" if len(s) > 1 and s[1] == 'a':\n",
" if len(s) > 2 and s[2] == 'd':\n",
" if len(s) > 3 and s[3] == '!':\n",
" raise Exception()\n",
"\n",
"crashme_runner = FunctionCoverageRunner(crashme)\n",
"crashme_runner.run(\"good\")\n",
"list(crashme_runner.coverage())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In `crashme`, the input \"good\" only covers the if-statement in line 2. The branch condition `len(s) > 0 and s[0] == 'b'` evaluates to False. \n",
"\n",
"## AFLFast: Fuzzer Boosting\n",
"\n",
"### Blackbox Mutation-based Fuzzer\n",
"Let's integrate both the mutator and power schedule into a fuzzer. We'll start with a blackbox fuzzer -- which does *not* leverage any coverage information. \n",
"\n",
"Our `MutationFuzzer` class inherits from the [Fuzzer](Fuzzer.ipynb#Fuzzer-Classes) class. For now, we only need to know the functions `fuzz` which returns a generated input and `runs` which executes `fuzz` a specified number of times. For our `MutationFuzzer` class, we override the function `fuzz`."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from Fuzzer import Fuzzer"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The `MutationFuzzer` is constructed with a set of initial seeds, a mutator, and a power schedule. Throughout the fuzzing campaign, it maintains a seed corpus called `population`. The function `fuzz` returns either an unfuzzed seed from the initial seeds, or the result of fuzzing a seed in the population. The function `create_candidate` handles the latter. It randomly chooses an input from the population and applies a number of mutations."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"class MutationFuzzer(Fuzzer):\n",
" \n",
" def __init__(self, seeds, mutator, schedule):\n",
" self.seeds = seeds\n",
" self.mutator = mutator\n",
" self.schedule = schedule\n",
" self.inputs = []\n",
" self.reset()\n",
"\n",
" def reset(self):\n",
" \"\"\"Reset the initial population and seed index\"\"\"\n",
" self.population = list(map(lambda x: Seed(x), self.seeds))\n",
" self.seed_index = 0\n",
"\n",
" def create_candidate(self):\n",
" \"\"\"Returns an input generated by fuzzing a seed in the population\"\"\"\n",
" seed = self.schedule.choose(self.population)\n",
"\n",
" # Stacking: Apply multiple mutations to generate the candidate\n",
" candidate = seed.data\n",
" trials = min(len(candidate), 1 << random.randint(1,5))\n",
" for i in range(trials):\n",
" candidate = self.mutator.mutate(candidate)\n",
" return candidate\n",
"\n",
" def fuzz(self):\n",
" \"\"\"Returns first each seed once and then generates new inputs\"\"\"\n",
" if self.seed_index < len(self.seeds):\n",
" # Still seeding\n",
" self.inp = self.seeds[self.seed_index]\n",
" self.seed_index += 1\n",
" else:\n",
" # Mutating\n",
" self.inp = self.create_candidate()\n",
" \n",
" self.inputs.append(self.inp)\n",
" return self.inp\n",
" "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Okay, let's take the mutation fuzzer for a spin. Given a single seed, we ask it to generate three inputs."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"seed_input = \"good\"\n",
"mutation_fuzzer = MutationFuzzer([seed_input], Mutator(), PowerSchedule())\n",
"print(mutation_fuzzer.fuzz())\n",
"print(mutation_fuzzer.fuzz())\n",
"print(mutation_fuzzer.fuzz())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's see how many statements the mutation-based blackbox fuzzer covers in a campaign with n=30k inputs.\n",
"\n",
"The fuzzer function `runs(crashme_runner, trials=n)` generates `n` inputs and executes them on the `crashme` function via the `crashme_runner`. As stated earlier, the `crashme_runner` also collects coverage information."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import time\n",
"n = 30000"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"blackbox_fuzzer = MutationFuzzer([seed_input], Mutator(), PowerSchedule())\n",
"\n",
"start = time.time()\n",
"blackbox_fuzzer.runs(crashme_runner, trials=n)\n",
"end = time.time()\n",
"\n",
"\"It took the blackbox mutation-based fuzzer %0.2f seconds to generate and execute %d inputs.\" % (end - start, n)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In order to measure coverage, we import the [population_coverage](Coverage.ipynb#Coverage-of-Basic-Fuzzing) function. It takes a set of inputs and a Python function, executes the inputs on that function and collects coverage information. Specifically, it returns a tuple `(all_coverage, cumulative_coverage)` where `all_coverage` is the set of statements covered by all inputs, and `cumulative_coverage` is the number of statements covered as the number of executed inputs increases. We are just interested in the latter to plot coverage over time."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from Coverage import population_coverage"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We extract the generated inputs from the blackbox fuzzer and measure coverage as the number of inputs increases."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"_, blackbox_coverage = population_coverage(blackbox_fuzzer.inputs, crashme)\n",
"bb_max_coverage = max(blackbox_coverage)\n",
"\n",
"\"The blackbox mutation-based fuzzer achieved a maximum coverage of %d statements.\" % bb_max_coverage"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The following generated inputs increased the coverage for our `crashme` [example](#Runner-and-Sample-Program)."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"[seed_input] + \\\n",
"[blackbox_fuzzer.inputs[idx] for idx in range(len(blackbox_coverage)) \n",
" if blackbox_coverage[idx] > blackbox_coverage[idx - 1]\n",
"]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"***Summary***. This is how a blackbox mutation-based fuzzer works. We have integrated the *mutator* to generate inputs by fuzzing a provided set of initial seeds and the *power schedule* to decide which seed to choose next."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Greybox Mutation-based Fuzzer\n",
"In contrast to a blackbox fuzzer, a greybox fuzzer *does* leverage coverage information. Specifically, a greybox fuzzer adds to the seed population generated inputs which increase code coverage.\n",
"\n",
"The function `run` is inherited from the [Fuzzer](Fuzzer.ipynb#Fuzzer-Classes) class. It is called to generate and execute exactly one input. We override this function to add an input to the `population` that increases coverage. The greybox fuzzer attribute `coverage_seen` maintains the set of statements, that have previously been covered."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"class GreyboxFuzzer(MutationFuzzer):\n",
" \n",
" def reset(self):\n",
" \"\"\"Reset the initial population, seed index, coverage information\"\"\"\n",
" super().reset()\n",
" self.coverages_seen = set()\n",
" self.population = [] # population is filled during greybox fuzzing\n",
" \n",
" def run(self, runner):\n",
" \"\"\"Run function(inp) while tracking coverage.\n",
" If we reach new coverage,\n",
" add inp to population and its coverage to population_coverage\n",
" \"\"\"\n",
" result, outcome = super().run(runner)\n",
" new_coverage = frozenset(runner.coverage())\n",
" if new_coverage not in self.coverages_seen:\n",
" # We have new coverage\n",
" seed = Seed(self.inp)\n",
" seed.coverage = runner.coverage()\n",
" self.coverages_seen.add(new_coverage)\n",
" self.population.append(seed)\n",
"\n",
" return (result, outcome)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's take our greybox fuzzer for a spin."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"seed_input = \"good\"\n",
"greybox_fuzzer = GreyboxFuzzer([seed_input], Mutator(), PowerSchedule())\n",
"\n",
"start = time.time()\n",
"greybox_fuzzer.runs(crashme_runner, trials=n)\n",
"end = time.time()\n",
"\n",
"\"It took the greybox mutation-based fuzzer %0.2f seconds to generate and execute %d inputs.\" % (end - start, n)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Does the greybox fuzzer cover more statements after generating the same number of test inputs?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"_, greybox_coverage = population_coverage(greybox_fuzzer.inputs, crashme)\n",
"gb_max_coverage = max(greybox_coverage)\n",
"\n",
"\"Our greybox mutation-based fuzzer covers %d more statements\" % (gb_max_coverage - bb_max_coverage)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Our seed population for our [example](#Runner-and-Sample-Program) now contains the following seeds."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"greybox_fuzzer.population"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Coverage-feedback is indeed helpful. The new seeds are like bread crumbs or milestones that guide the fuzzer to progress more quickly into deeper code regions. Following is a simple plot showing the coverage achieved over time for both fuzzers on our simple [example](#Runner-and-Sample-Program)."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"%matplotlib inline\n",
"\n",
"import matplotlib.pyplot as plt\n",
"\n",
"line_bb, = plt.plot(blackbox_coverage, label=\"Blackbox\")\n",
"line_gb, = plt.plot(greybox_coverage, label=\"Greybox\")\n",
"plt.legend(handles=[line_bb, line_gb])\n",
"plt.title('Coverage over time')\n",
"plt.xlabel('# of inputs')\n",
"plt.ylabel('lines covered')\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"***Summary***. We have seen how a greybox fuzzer \"discovers\" interesting seeds that can lead to more progress. From the input `good`, our greybox fuzzer has slowly learned how to generate the input `bad!` which raises the exception. Now, how can we do that even faster?\n",
"\n",
"***Try it***. How much coverage would be achieved over time using a blackbox *generation-based* fuzzer? Try plotting the coverage for all three fuzzers. You can define the blackbox generation-based fuzzer as follows.\n",
"```Python\n",
"from Fuzzer import RandomFuzzer\n",
"blackbox_gen_fuzzer = RandomFuzzer(min_length=4, max_length=4, char_start=32, char_range=96)\n",
"```\n",
"You can execute your own code by opening this chapter as Jupyter notebook: [Click here](https://mybinder.org/v2/gh/uds-se/fuzzingbook/master?filepath=docs/beta/notebooks/Greybox_Fuzzing.ipynb)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Boosted Greybox Fuzzer\n",
"Our boosted greybox fuzzer assigns more energy to seeds that promise to achieve more coverage. We change the power schedule such that seeds that exercise \"unusual\" paths have more energy. With *unusual paths*, we mean paths that are not exercised very often by generated inputs.\n",
"\n",
"In order to identify which path is exercised by an input, we leverage the function `getPathID` from the section on [trace coverage](WhenIsEnough.ipynb#Trace-Coverage)."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import pickle # serializes an object by producing a byte array from all the information in the object\n",
"import hashlib # produces a 128-bit hash value from a byte array"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The function `getPathID` returns a unique hash for a coverage set."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def getPathID(coverage):\n",
" \"\"\"Returns a unique hash for the covered statements\"\"\"\n",
" pickled = pickle.dumps(coverage)\n",
" return hashlib.md5(pickled).hexdigest()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"There are several ways to assign energy based on how unusual the exercised path is. In this case, we implement an exponential power schedule which computes the energy $e(s)$ for a seed $s$ as follows\n",
"$$e(s) = \\frac{1}{f(p(s))^a}$$\n",
"where \n",
"* $p(s)$ returns the ID of the path exercised by $s$, \n",
"* $f(p)$ returns the number of times the path $p$ is exercised by generated inputs, and \n",
"* $a$ is a given exponent."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"class AFLFastSchedule(PowerSchedule):\n",
" \n",
" def __init__(self, exponent):\n",
" self.exponent = exponent\n",
" \n",
" def assignEnergy(self, population):\n",
" \"\"\"Assign exponential energy inversely proportional to path frequency\"\"\"\n",
" for seed in population:\n",
" seed.energy = 1 / (self.path_frequency[getPathID(seed.coverage)] ** self.exponent)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In the greybox fuzzer, lets keep track of the number of times $f(p)$ each path $p$ is exercised, and update the power schedule."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"class CountingGreyboxFuzzer(GreyboxFuzzer):\n",
"\n",
" def reset(self):\n",
" \"\"\"Reset path frequency\"\"\"\n",
" super().reset()\n",
" self.schedule.path_frequency = {}\n",
" \n",
" def run(self, runner):\n",
" \"\"\"Inform scheduler about path frequency\"\"\"\n",
" result, outcome = super().run(runner)\n",
"\n",
" path_id = getPathID(runner.coverage())\n",
" if not path_id in self.schedule.path_frequency:\n",
" self.schedule.path_frequency[path_id] = 1\n",
" else:\n",
" self.schedule.path_frequency[path_id] += 1\n",
" \n",
" return(result, outcome)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Okay, lets run our boosted greybox fuzzer $n=10k$ times on our simple [example](#Runner-and-Sample-Program). We set the exponentent of our exponential power schedule to $a=5$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"n=10000\n",
"seed_input = \"good\"\n",
"fast_schedule = AFLFastSchedule(5)\n",
"fast_fuzzer = CountingGreyboxFuzzer([seed_input], Mutator(), fast_schedule)\n",
"start = time.time()\n",
"fast_fuzzer.runs(crashme_runner, trials=n)\n",
"end = time.time()\n",
"\n",
"\"It took the fuzzer w/ exponential schedule %0.2f seconds to generate and execute %d inputs.\" % (end - start, n)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"x_axis = np.arange(len(fast_schedule.path_frequency))\n",
"y_axis = list(fast_schedule.path_frequency.values())\n",
"\n",
"plt.bar(x_axis, y_axis)\n",
"plt.xticks(x_axis)\n",
"#plt.yscale(\"log\")\n",
"#plt.yticks([10,100,1000,10000])\n",
"plt.show()\n",
"\n",
"print(\" path id 'p' : path frequency 'f(p)'\")\n",
"fast_schedule.path_frequency"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"How does it compare to our greybox fuzzer with the classical power schedule?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"seed_input = \"good\"\n",
"orig_schedule = PowerSchedule()\n",
"orig_fuzzer = CountingGreyboxFuzzer([seed_input], Mutator(), orig_schedule)\n",
"start = time.time()\n",
"orig_fuzzer.runs(crashme_runner, trials=n)\n",
"end = time.time()\n",
"\n",
"\"It took the fuzzer w/ original schedule %0.2f seconds to generate and execute %d inputs.\" % (end - start, n)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"x_axis = np.arange(len(orig_schedule.path_frequency))\n",
"y_axis = list(orig_schedule.path_frequency.values())\n",
"\n",
"plt.bar(x_axis, y_axis)\n",
"plt.xticks(x_axis)\n",
"#plt.yscale(\"log\")\n",
"#plt.yticks([10,100,1000,10000])\n",
"plt.show()\n",
"\n",
"print(\" path id 'p' : path frequency 'f(p)'\")\n",
"orig_schedule.path_frequency"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The exponential power schedule shaves some of the executions of the \"high-frequency path\" off and adds them to the lower-frequency paths. The path executed least often is either not at all exercised using the traditional power schedule or it is exercised much less often.\n",
"\n",
"Let's have a look at the energy that is assigned to the discovered seeds."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"orig_energy = orig_schedule.normalizedEnergy(orig_fuzzer.population)\n",
"\n",
"for (seed, norm_energy) in zip(orig_fuzzer.population, orig_energy):\n",
" print(\"'%s', %0.5f, %s\" % (getPathID(seed.coverage), norm_energy, seed.data))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"fast_energy = fast_schedule.normalizedEnergy(fast_fuzzer.population)\n",
"\n",
"for (seed, norm_energy) in zip(fast_fuzzer.population, fast_energy):\n",
" print(\"'%s', %0.5f, %s\" % (getPathID(seed.coverage), norm_energy, seed.data))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Exactly. Our new exponential power schedule assigns most energy to the seed exercising the lowest-frequency path.\n",
"\n",
"Let's compare them in terms of coverage achieved over time for our simple [example](#Runner-and-Sample-Program)."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"_, orig_coverage = population_coverage(orig_fuzzer.inputs, crashme)\n",
"_, fast_coverage = population_coverage(fast_fuzzer.inputs, crashme)\n",
"line_orig, = plt.plot(orig_coverage, label=\"Original Greybox Fuzzer\")\n",
"line_fast, = plt.plot(fast_coverage, label=\"Boosted Greybox Fuzzer\")\n",
"plt.legend(handles=[line_orig, line_fast])\n",
"plt.title('Coverage over time')\n",
"plt.xlabel('# of inputs')\n",
"plt.ylabel('lines covered')\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As expected, the boosted greybox fuzzer (with the exponential power schedule) achieves coverage much faster.\n",
"\n",
"***Summary***. By fuzzing seeds more often that exercises low-frequency paths, we can explore program paths in a much more efficient manner.\n",
"\n",
"***Try it***. You can try other exponents for the fast power schedule, or change the power shedule entirely. Note that a large exponent can lead to overflows and imprecisions in the floating point arithmetic producing unexpected results. You can execute your own code by opening this chapter as Jupyter notebook: [Click here](https://mybinder.org/v2/gh/uds-se/fuzzingbook/master?filepath=docs/beta/notebooks/Greybox_Fuzzing.ipynb)\n",
"\n",
"***Read***. You can find out more about fuzzer boosting in the paper \"[Coverage-based Greybox Fuzzing as Markov Chain](https://mboehme.github.io/paper/CCS16.pdf)\" and check out the implementation into AFL at [http://github.com/mboehme/aflfast]."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Complex Example: XMLParser\n",
"Let's compare the three fuzzers on a more realistic example, the Python [HTML parser](https://docs.python.org/3/library/html.parser.html). We run all three fuzzers $n=5k$ times on the HTMLParser, starting with the \"empty\" seed."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from html.parser import HTMLParser\n",
"import traceback"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# create wrapper function\n",
"def my_parser(inp):\n",
" parser = HTMLParser() # resets the HTMLParser object for every fuzz input\n",
" parser.feed(inp)\n",
"\n",
"n = 5000\n",
"seed_input = \" \" # empty seed\n",
"parser_runner = FunctionCoverageRunner(my_parser)\n",
"blackbox_fuzzer = MutationFuzzer([seed_input], Mutator(), PowerSchedule())\n",
"greybox_fuzzer = GreyboxFuzzer([seed_input], Mutator(), PowerSchedule())\n",
"boosted_fuzzer = CountingGreyboxFuzzer([seed_input], Mutator(), AFLFastSchedule(5))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"start = time.time()\n",
"blackbox_fuzzer.runs(parser_runner, trials=n)\n",
"greybox_fuzzer.runs(parser_runner, trials=n)\n",
"boosted_fuzzer.runs(parser_runner, trials=n)\n",
"end = time.time()\n",
"\n",
"\"It took all three fuzzers %0.2f seconds to generate and execute %d inputs.\" % (end - start, n)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"How do the fuzzers compare in terms of coverage over time?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"_, black_coverage = population_coverage(blackbox_fuzzer.inputs, my_parser)\n",
"_, grey_coverage = population_coverage(greybox_fuzzer.inputs, my_parser)\n",
"_, boost_coverage = population_coverage(boosted_fuzzer.inputs, my_parser)\n",
"line_black, = plt.plot(black_coverage, label=\"Blackbox Fuzzer\")\n",
"line_grey, = plt.plot(grey_coverage, label=\"Greybox Fuzzer\")\n",
"line_boost, = plt.plot(boost_coverage, label=\"Boosted Greybox Fuzzer\")\n",
"plt.legend(handles=[line_boost, line_grey, line_black])\n",
"plt.title('Coverage over time')\n",
"plt.xlabel('# of inputs')\n",
"plt.ylabel('lines covered')\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Both greybox fuzzers clearly outperform the greybox fuzzer. The reason is that the greybox fuzzer \"discovers\" interesting inputs along the way. Let's have a look at the last 10 inputs generated by the greybox versus blackbox fuzzer."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"blackbox_fuzzer.inputs[-10:]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"greybox_fuzzer.inputs[-10:]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The greybox fuzzer executes much more complicated inputs, many of which include special characters such as opening and closing brackets and chevrons (i.e., `<, >, [, ]`). Yet, many important keywords, such as `` are still missing. How can we inform the fuzzer about these important keywords?\n",
"\n",
"***Try it***. You can re-run these experiments to understand the variance of fuzzing experiments. Sometimes, the fuzzer that we claim to be superior does not seem to outperform the inferior fuzzer. In order to execute your own code, you just need to open this chapter as Jupyter notebook: [Click here](https://mybinder.org/v2/gh/uds-se/fuzzingbook/master?filepath=docs/beta/notebooks/Greybox_Fuzzing.ipynb)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## AFLSmart: Smart Greybox Fuzzing\n",
"\\todo{Reference [Fuzzing with Input Fragments](LangFuzzer.ipynb)}\n",
"\n",
"### Dictionary: Injecting Important Keywords\n",
"Today, dictionaries are the main mechanism to inform a greybox fuzzer about important keywords in the input.\n",
"\n",
"\\todo{}"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"class DictMutator(Mutator):\n",
" def __init__(self, dictionary):\n",
" super().__init__()\n",
" self.dictionary = dictionary\n",
" self.mutators.append(self.insert_from_dictionary)\n",
" \n",
" def insert_from_dictionary(self,s):\n",
" \"\"\"Returns s with a keyword from the dictionary inserted\"\"\"\n",
" pos = random.randint(0, len(s))\n",
" random_keyword = random.choice(self.dictionary)\n",
" return s[:pos] + random_keyword + s[pos:]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"n=2500\n",
"html_dict = [\"\",\"\",\"\", \"='a'\"]\n",
"dict_fuzzer = CountingGreyboxFuzzer([seed_input], DictMutator(html_dict), AFLFastSchedule(5))\n",
"start = time.time()\n",
"dict_fuzzer.runs(parser_runner, trials=n)\n",
"end = time.time()\n",
"\n",
"\"It took the fuzzer %0.2f seconds to generate and execute %d inputs.\" % (end - start, n)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"_, dict_coverage = population_coverage(dict_fuzzer.inputs, my_parser)\n",
"line_dict, = plt.plot(dict_coverage, label=\"Dictionary-supported Fuzzer\")\n",
"line_boost, = plt.plot(boost_coverage, label=\"Boosted Greybox Fuzzer\")\n",
"plt.legend(handles=[line_dict, line_boost])\n",
"plt.xlim(0,n)\n",
"plt.title('Coverage over time')\n",
"plt.xlabel('# of inputs')\n",
"plt.ylabel('lines covered')\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Structural Mutation of Valid Seeds\n",
"\\todo{Recall [Grammar-based Mutational Fuzzing](LangFuzzer.ipynb)}"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Structural Mutation of Invalid Seeds\n",
"\\todo{partial parsing, degree of validity}"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Putting it all Together\n",
"\\todo{integration with low-level mutations and dictionary, deferred parsing}"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\\todo{Reference [AFLSmart](https://github.com/aflsmart/aflsmart) and \"[Smart Greybox Fuzzing](https://arxiv.org/abs/1811.09447)\"}\n",
"\n",
"## AFLGo: Directed Greybox Fuzzing\n",
"Sometimes, you just want the fuzzer to reach some dangerous location in the source code. This could be a location, where you expect a buffer overflow. Or you want to test a recent change in your code base. How do we direct the fuzzer towards these locations?\n",
"\n",
"In this chapter, we introduce directed greybox fuzzing as an optimization problem."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Solving the Maze\n",
"To provide a meaningful example where you can easily change the code complexity and target location, we generate the maze source code from the maze provided as string. This example is loosly based on an old [blog post](https://feliam.wordpress.com/2010/10/07/the-symbolic-maze/) on symbolic execution by Felipe Andres Manzano (Quick shout-out!).\n",
"\n",
"You simply specify the maze as a string. Like so."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"maze_string = \"\"\"\n",
"+-+-----+\n",
"|X| |\n",
"| | --+ |\n",
"| | | |\n",
"| +-- | |\n",
"| |#|\n",
"+-----+-+\n",
"\"\"\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The code is generated using the function `generate_maze_code`. We'll hide the implementation and instead explain what it does. If you are interested in the coding, go [here](ControlFlow.ipynb#Example:-Maze)."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from ControlFlow import generate_maze_code"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"maze_code = generate_maze_code(maze_string)\n",
"exec(maze_code)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The objective is to get the \"X\" to the \"#\" by providing inputs `D` for down, `U` for up, `L` for left, and `R` for right."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(maze(\"DDDDRRRRUULLUURRRRDDDD\")) # Appending one more 'D', you have reached the target."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For each \"tile\", a tile-function is generated. \n",
"* If the current tile is \"benign\" (` `), the tile-function corresponding to the next input character (D, U, L, R) is called. Unexpected input characters are ignored. If no more input characters are left, it returns \"VALID\" and the current maze state.\n",
"* If the current tile is a \"trap\" (`+`,`|`,`-`), it returns \"INVALID\" and the current maze state.\n",
"* If the current tile is the \"target\" (`#`), it returns \"SOLVED\" and the current maze state.\n",
"\n",
"***Try it***. You can test other sequences of input characters, or even change the maze entirely. In order to execute your own code, you just need to open this chapter as Jupyter notebook: [Click here](https://mybinder.org/v2/gh/uds-se/fuzzingbook/master?filepath=docs/beta/notebooks/Greybox_Fuzzing.ipynb)\n",
"\n",
"To get an idea of the generated code, lets look at the static [call graph](https://en.wikipedia.org/wiki/Call_graph). A call graph shows the order in which functions can be executed."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from ControlFlow import print_callgraph"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print_callgraph(maze_code)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### A First Attempt\n",
"To fuzz the maze, we extend the [DictMutator](Greybox_Fuzzing.ipynb#Dictionary:-Injecting-Important-Keywords) class to append dictionary keywords to the end of the seed and to remove a character from the end of the seed."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"class MazeMutator(DictMutator):\n",
" def __init__(self, dictionary):\n",
" super().__init__(dictionary)\n",
" self.mutators.append(self.delete_last_character)\n",
" self.mutators.append(self.append_from_dictionary)\n",
"\n",
" def append_from_dictionary(self,s):\n",
" \"\"\"Returns s with a keyword from the dictionary appended\"\"\"\n",
" random_keyword = random.choice(self.dictionary)\n",
" return s + random_keyword\n",
" \n",
" def delete_last_character(self,s):\n",
" \"\"\"Returns s without the last character\"\"\"\n",
" if (len(s) > 0):\n",
" return s[:-1]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's try a standard greybox fuzzer with the classic power schedule and our extended maze mutator (n=10k)."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"n = 10000\n",
"seed_input = \" \" # empty seed\n",
"\n",
"maze_runner = FunctionCoverageRunner(maze)\n",
"maze_mutator = MazeMutator([\"L\",\"R\",\"U\",\"D\"])\n",
"maze_schedule = PowerSchedule()\n",
"maze_fuzzer = GreyboxFuzzer([seed_input], maze_mutator, maze_schedule)\n",
"\n",
"start = time.time()\n",
"maze_fuzzer.runs(maze_runner, trials=n)\n",
"end = time.time()\n",
"\n",
"\"It took the fuzzer %0.2f seconds to generate and execute %d inputs.\" % (end - start, n)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We will need to print statistics for several fuzzers. Why don't we define a function for that?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def print_stats(fuzzer):\n",
" total = len(fuzzer.population)\n",
" solved = 0\n",
" invalid = 0\n",
" valid = 0\n",
" for seed in fuzzer.population:\n",
" s = maze(str(seed.data))\n",
" if \"INVALID\" in s: invalid += 1\n",
" elif \"VALID\" in s: valid += 1\n",
" elif \"SOLVED\" in s: \n",
" solved += 1\n",
" if solved == 1: print(\"First solution: %s\" % seed)\n",
" else: print(\"??\")\n",
"\n",
" print(\"\"\"Out of %d seeds, \n",
"* %4d solved the maze, \n",
"* %4d were valid but did not solve the maze, and \n",
"* %4d were invalid\"\"\" % (total, solved, valid, invalid)) "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"How well does our good, old greybox fuzzer do?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print_stats(maze_fuzzer)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"It probably didn't solve the maze a single time. How can we make the fuzzer aware how \"far\" a seed is from reaching the target? If we know that, we can just assign more energy to that seed.\n",
"\n",
"***Try it***. Print the statistics for the boosted fuzzer using the `AFLFastSchedule` and the `CountingGreyboxFuzzer`. It will likely perform much better than the unboosted greybox fuzzer: The lowest-probablity path happens to be also the path which reaches the target. You can execute your own code by opening this chapter as Jupyter notebook: [Click here](https://mybinder.org/v2/gh/uds-se/fuzzingbook/master?filepath=docs/beta/notebooks/Greybox_Fuzzing.ipynb) \n",
"\n",
"### Computing Function-Level Distance\n",
"Using the static call graph for the maze code and the target function, we can compute the distance of each function $f$ to the target $t$ as the length of the shortest path between $f$ and $t$.\n",
"\n",
"Fortunately, the generated maze code includes a function called `target_tile` which returns the name of the target-function."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"target = target_tile()\n",
"target"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now, we need to find the corresponding function in the call graph. The function `get_callgraph` returns the call graph for the maze code as [networkx](https://networkx.github.io/) graph. Networkx provides some useful functions for graph analysis."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import networkx as nx\n",
"from ControlFlow import get_callgraph"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"CG = get_callgraph(maze_code)\n",
"for node in CG.nodes():\n",
" if target in node:\n",
" target_node = node\n",
" break\n",
"target_node"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can now generate the function-level distance. The dictionary `distance` contains for each function the distance to the target-function. If there is no path to the target, we assign a maximum distance (`0xFFFF`).\n",
"\n",
"The function `nx.shortest_path_length(CG, node, target_node)` returns the length of the shortest path from function `node` to function `target_node` in the call graph `CG`."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"distance = {}\n",
"for node in CG.nodes():\n",
" if \"__\" in node: \n",
" name = node.split(\"__\")[-1]\n",
" else: \n",
" name = node\n",
" try:\n",
" distance[name] = nx.shortest_path_length(CG, node, target_node)\n",
" except:\n",
" distance[name] = 0xFFFF"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"These are the distance values for all tile-functions on the path to the target function."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"{k: distance[k] for k in list(distance) if distance[k] < 0xFFFF}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"***Summary***. Using the static call graph and the target function $t$, we have shown how to compute the function-level distance of each function $f$ to the target $t$.\n",
"\n",
"***Try it***. You can try and execute your own code by opening this chapter as Jupyter notebook: [Click here](https://mybinder.org/v2/gh/uds-se/fuzzingbook/master?filepath=docs/beta/notebooks/Greybox_Fuzzing.ipynb) \n",
"* How do we compute distance if there are multiple targets? (Hint: [Geometric Mean](https://en.wikipedia.org/wiki/Geometric_mean)).\n",
"* Given the call graph (CG) and the control-flow graph (CFG$_f$) for each function $f$, how do we compute basic-block (BB)-level distance? (Hint: In CFG$_f$, measure the BB-level distance to *calls* of functions on the path to the target function. Remember that BB-level distance in functions with higher function-level distance is higher, too.)\n",
"\n",
"***Read***. If you are interested in other aspects of search, you can follow up by reading the chapter on [Search-based Fuzzing](SearchBasedFuzzer.ipynb). If you are interested, how to solve the problems above, you can have a look at our paper on \"[Directed Greybox Fuzzing](https://mboehme.github.io/paper/CCS17.pdf)\".\n",
"\n",
"### Directed Power Schedule\n",
"Now that we know how to compute the function-level distance, let's try to implement a power schedule that assigns *more energy to seeds with a lower average distance* to the target function. Notice that the distance values are all *pre-computed*. These values are injected into program binary, just like the coverage instrumentation. In practice, this makes the computation of the average distance *extremely efficient*.\n",
"\n",
"If you really want to know. Given the function-level distance $d_f(s,t)$ of a function $s$ to a function $t$ in call graph $CG$, our directed power schedule computes the seed distance $d(i,t)$ for a seed $i$ to function $t$ as $d(i,t)=\\sum_{s\\in CG}\\dfrac{d_f(s,t)}{|CG|}$ where $|CG|$ is the number of nodes in the call graph $CG$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"class DirectedSchedule(PowerSchedule):\n",
" def __init__(self, distance, exponent):\n",
" self.distance = distance\n",
" self.exponent = exponent\n",
"\n",
" def __getFunctions__(self, coverage):\n",
" functions = set()\n",
" for f, _ in set(coverage):\n",
" functions.add(f)\n",
" return functions\n",
" \n",
" def assignEnergy(self, population):\n",
" \"\"\"Assigns each seed energy inversely proportional\n",
" to the average function-level distance to target.\"\"\"\n",
" for seed in population:\n",
" if not hasattr(seed, 'distance'):\n",
" num_dist = 0\n",
" sum_dist = 0\n",
" for f in self.__getFunctions__(seed.coverage):\n",
" if f in list(distance):\n",
" sum_dist += distance[f]\n",
" num_dist += 1\n",
" seed.distance = sum_dist / num_dist\n",
" seed.energy = (1 / seed.distance) ** self.exponent"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's see how the directed schedule performs against the good, old greybox fuzzer."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"directed_schedule = DirectedSchedule(distance, 3)\n",
"directed_fuzzer = GreyboxFuzzer([seed_input], maze_mutator, directed_schedule)\n",
"\n",
"start = time.time()\n",
"directed_fuzzer.runs(maze_runner, trials=n)\n",
"end = time.time()\n",
"\n",
"\"It took the fuzzer %0.2f seconds to generate and execute %d inputs.\" % (end - start, n)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print_stats(directed_fuzzer)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"It probably didn't solve a single maze either, but we have more valid solutions. So, there is definitely progress.\n",
"\n",
"Let's have a look at the distance values for each seed."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"y = [seed.distance for seed in directed_fuzzer.population]\n",
"x = range(len(y))\n",
"plt.scatter(x, y)\n",
"plt.ylim(0,max(y))\n",
"plt.xlabel(\"Seed ID\")\n",
"plt.ylabel(\"Distance\")\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's normalize the y-axis and improve the importance of the small distance seeds.\n",
"\n",
"### Improved Directed Power Schedule\n",
"The improved directed schedule normalizes seed distance between the minimal and maximal distance.\n",
"Again, if you really want to know. Given the seed distance $d(i,t)$ of a seed $i$ to a function $t$, our improved power schedule computes the new seed distance $d'(i,t)$ as \n",
"$$\n",
"d'(i,t)=\\begin{cases}\n",
"1 & \\text{if } d(i,t) = \\text{minD} = \\text{maxD}\\\\\n",
"\\text{maxD} - \\text{minD} & \\text{if } d(i,t) = \\text{minD} \\neq \\text{maxD}\\\\\n",
"\\frac{d(i,t)-\\text{minD}}{\\text{maxD} - \\text{minD}} & \\text{otherwise}\n",
"\\end{cases}\n",
"$$\n",
"where \n",
"$$\\text{minD}=\\min_{i\\in T}[d(i,t)]$$\n",
"and\n",
"$$\\text{maxD}=\\max_{i\\in T}[d(i,t)]$$\n",
"where $T$ is the set of seeds (i.e., the population)."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"class AFLGoSchedule(DirectedSchedule):\n",
" def assignEnergy(self, population):\n",
" \"\"\"Assigns each seed energy inversely proportional\n",
" to the average function-level distance to target.\"\"\"\n",
" min_dist = 0xFFFF\n",
" max_dist = 0\n",
" for seed in population:\n",
" if not hasattr(seed, 'distance'):\n",
" num_dist = 0\n",
" sum_dist = 0\n",
" for f in self.__getFunctions__(seed.coverage):\n",
" if f in list(distance):\n",
" sum_dist += distance[f]\n",
" num_dist += 1\n",
" seed.distance = sum_dist / num_dist\n",
" if seed.distance < min_dist: min_dist = seed.distance\n",
" if seed.distance > max_dist: max_dist = seed.distance\n",
"\n",
" for seed in population:\n",
" if (seed.distance == min_dist):\n",
" if min_dist == max_dist:\n",
" seed.energy = 1\n",
" else: \n",
" seed.energy = max_dist - min_dist\n",
" else:\n",
" seed.energy = ((max_dist - min_dist) / (seed.distance - min_dist)) "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's see how the improved power schedule performs."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"aflgo_schedule = AFLGoSchedule(distance, 3)\n",
"aflgo_fuzzer = GreyboxFuzzer([seed_input], maze_mutator, aflgo_schedule)\n",
"\n",
"start = time.time()\n",
"aflgo_fuzzer.runs(maze_runner, trials=n)\n",
"end = time.time()\n",
"\n",
"\"It took the fuzzer %0.2f seconds to generate and execute %d inputs.\" % (end - start, n)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print_stats(aflgo_fuzzer)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In contrast to all previous power schedules, this one generates hundreds of solutions. It has generated many solutions. \n",
"\n",
"Let's filter out all ignored input characters from the first solution. The function `filter(f, seed.data)` returns a list of elements `e` in `seed.data` where the function `f` applied on `e` returns True."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"for seed in aflgo_fuzzer.population:\n",
" s = maze(str(seed.data))\n",
" if \"SOLVED\" in s:\n",
" filtered = \"\".join(list(filter(lambda c: c in \"UDLR\", seed.data)))\n",
" print(filtered)\n",
" break"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This is definitely a solution for the maze specified at the beginning!\n",
"\n",
"***Summary***. After pre-computing the function-level distance to the target, we can develop a power schedule that assigns more energy to a seed with a smaller average function-level distance to the target. By normalizing seed distance values between the minimum and maximum seed distance, we can further boost the directed power schedule.\n",
"\n",
"***Try it***. Implement and evaluate a simpler directed power that uses the minimal (rather than average) function-level distance. What is the downside of using the minimal distance? In order to execute your code, you just need to open this chapter as Jupyter notebook: [Click here](https://mybinder.org/v2/gh/uds-se/fuzzingbook/master?filepath=docs/beta/notebooks/Greybox_Fuzzing.ipynb)\n",
"\n",
"***Read***. You can find out more about directed greybox fuzzing in the equally-named paper \"[Directed Greybox Fuzzing](https://mboehme.github.io/paper/CCS17.pdf)\" and check out the implementation into AFL at [http://github.com/aflgo/aflgo]."
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": true,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Lessons Learned\n",
"\n",
"\\todo{}\n",
"* _Lesson one_\n",
"* _Lesson two_\n",
"* _Lesson three_"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Next Steps\n",
"\n",
"_Link to subsequent chapters (notebooks) here, as in:_\n",
"\n",
"* [use _mutations_ on existing inputs to get more valid inputs](MutationFuzzer.ipynb)\n",
"* [use _grammars_ (i.e., a specification of the input format) to get even more valid inputs](Grammars.ipynb)\n",
"* [reduce _failing inputs_ for efficient debugging](Reducer.ipynb)\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Background\n",
"\n",
"_Cite relevant works in the literature and put them into context, as in:_\n",
"\n",
"The idea of ensuring that each expansion in the grammar is used at least once goes back to Burkhardt \\cite{Burkhardt1967}, to be later rediscovered by Paul Purdom \\cite{Purdom1972}."
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": true,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Exercises\n",
"\n",
"_Close the chapter with a few exercises such that people have things to do. To make the solutions hidden (to be revealed by the user), have them start with_\n",
"\n",
"```markdown\n",
"**Solution.**\n",
"```\n",
"\n",
"_Your solution can then extend up to the next title (i.e., any markdown cell starting with `#`)._\n",
"\n",
"_Running `make metadata` will automatically add metadata to the cells such that the cells will be hidden by default, and can be uncovered by the user. The button will be introduced above the solution._"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Exercise 1: _Title_\n",
"\n",
"_Text of the exercise_"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"cell_style": "center",
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"# Some code that is part of the exercise\n",
"pass"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
},
"solution2": "shown",
"solution2_first": true
},
"source": [
"_Some more text for the exercise_"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
},
"solution2": "hidden",
"solution2_first": true
},
"source": []
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
},
"solution2": "hidden"
},
"source": [
"**Solution.** _Some text for the solution_"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
},
"solution": "hidden",
"solution2": "hidden",
"solution2_first": true,
"solution_first": true
},
"source": [
"### Exercise 2: _Title_\n",
"\n",
"_Text of the exercise_"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"cell_style": "split",
"slideshow": {
"slide_type": "skip"
},
"solution2": "hidden"
},
"outputs": [],
"source": [
"# Some code for the solution\n",
"2 + 2"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
},
"solution2": "hidden"
},
"source": [
"_Some more text for the solution_"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "skip"
},
"solution": "hidden",
"solution2": "hidden"
},
"source": [
"**Solution.** _Solution for the exercise_"
]
}
],
"metadata": {
"ipub": {
"bibliography": "fuzzingbook.bib",
"toc": true
},
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.6"
},
"toc": {
"base_numbering": 1,
"nav_menu": {},
"number_sections": true,
"sideBar": true,
"skip_h1_title": true,
"title_cell": "",
"title_sidebar": "Contents",
"toc_cell": false,
"toc_position": {},
"toc_section_display": true,
"toc_window_display": true
},
"varInspector": {
"cols": {
"lenName": 16,
"lenType": 16,
"lenVar": 40
},
"kernels_config": {
"python": {
"delete_cmd_postfix": "",
"delete_cmd_prefix": "del ",
"library": "var_list.py",
"varRefreshCmd": "print(var_dic_list())"
},
"r": {
"delete_cmd_postfix": ") ",
"delete_cmd_prefix": "rm(",
"library": "var_list.r",
"varRefreshCmd": "cat(var_dic_list()) "
}
},
"types_to_exclude": [
"module",
"function",
"builtin_function_or_method",
"instance",
"_Feature"
],
"window_display": false
}
},
"nbformat": 4,
"nbformat_minor": 2
}