{ "cells": [ { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "# Mutation-Based Fuzzing\n", "\n", "Most [randomly generated inputs](Fuzzer.ipynb) are syntactically _invalid_ and thus are quickly rejected by the processing program. To exercise functionality beyond input processing, we must increase chances to obtain valid inputs. One such way is so-called *mutational fuzzing* – that is, introducing small changes to existing inputs that may still keep the input valid, yet exercise new behavior. We show how to create such mutations, and how to guide them towards yet uncovered code, applying central concepts from the popular AFL fuzzer." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "source": [ "**Prerequisites**\n", "\n", "* You should know how basic fuzzing works; for instance, from the [\"Fuzzing\"](Fuzzer.ipynb) chapter." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Fuzzing a URL Parser\n", "\n", "Many programs expect their inputs to come in a very specific format before they would actually process them. As an example, think of a program that accepts a URL (a Web address). The URL has to be in a valid format (i.e., the URL format) such that the program can deal with it. When fuzzing with random inputs, what are our chances to actually produce a valid URL?" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "To get deeper into the problem, let us explore what URLs are made of. A URL consists of a number of elements:\n", "\n", " scheme://netloc/path?query#fragment\n", " \n", "where\n", "\n", "* `scheme` is the protocol to be used, including `http`, `https`, `ftp`, `file`...\n", "* `netloc` is the name of the host to connect to, such as `www.google.com`\n", "* `path` is the path on that very host, such as `search`\n", "* `query` is a list of key/value pairs, such as `q=fuzzing`\n", "* `fragment` is a marker for a location in the retrieved document, such as `#result`" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "In Python, we can use the `urlparse()` function to parse and decompose a URL into its parts." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import fuzzingbook_utils" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "try:\n", " from urlparse import urlparse # Python 2\n", "except ImportError:\n", " from urllib.parse import urlparse # Python 3\n", "\n", "urlparse(\"http://www.google.com/search?q=fuzzing\")" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "We see how the result encodes the individual parts of the URL in different attributes." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Let us now assume we have a program that takes a URL as input. To simplify things, we won't let it do very much; we simply have it check the passed URL for validity. If the URL is valid, it returns True; otherwise, it raises an exception." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def http_program(url):\n", " supported_schemes = [\"http\", \"https\"]\n", " result = urlparse(url)\n", " if result.scheme not in supported_schemes:\n", " raise ValueError(\"Scheme must be one of \" + repr(supported_schemes))\n", " if result.netloc == '':\n", " raise ValueError(\"Host must be non-empty\")\n", "\n", " # Do something with the URL\n", " return True" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Let us now go and fuzz `http_program()`. To fuzz, we use the full range of printable ASCII characters, such that `:`, `/`, and lowercase letters are included." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from Fuzzer import fuzzer" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "fuzzer(char_start=32, char_range=96)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Let's try to fuzz with 1000 random inputs and see whether we have some success." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "for i in range(1000):\n", " try:\n", " url = fuzzer()\n", " result = http_program(url)\n", " print(\"Success!\")\n", " except ValueError:\n", " pass" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "What are the chances of actually getting a valid URL? We need our string to start with `\"http://\"` or `\"https://\"`. Let's take the `\"http://\"` case first. These are seven very specific characters we need to start with. The chance of producing these seven characters randomly (with a character range of 96 different characters) is $1 : 96^7$, or" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "96 ** 7" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "The odds of producing a `\"https://\"` prefix are even worse, at $1 : 96^8$:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "96 ** 8" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "which gives us a total chance of" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "likelihood = 1 / (96 ** 7) + 1 / (96 ** 8)\n", "likelihood" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "And this is the number of runs (on average) we'd need to produce a valid URL scheme:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "1 / likelihood" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Let's measure how long one run of `http_program()` takes:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from Timer import Timer" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "trials = 1000\n", "with Timer() as t:\n", " for i in range(trials):\n", " try:\n", " url = fuzzer()\n", " result = http_program(url)\n", " print(\"Success!\")\n", " except ValueError:\n", " pass\n", "\n", "duration_per_run_in_seconds = t.elapsed_time() / trials\n", "duration_per_run_in_seconds" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "That's pretty fast, isn't it? Unfortunately, we have a lot of runs to cover." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "seconds_until_success = duration_per_run_in_seconds * (1 / likelihood)\n", "seconds_until_success" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "which translates into" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "hours_until_success = seconds_until_success / 3600\n", "days_until_success = hours_until_success / 24\n", "years_until_success = days_until_success / 365.25\n", "years_until_success" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "Even if we parallelize things a lot, we're still in for months to years of waiting. And that's for getting _one_ successful run that will get deeper into `http_program()`." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "What basic fuzzing will do well is to test `urlparse()`, and if there is an error in this parsing function, it has good chances of uncovering it. But as long as we cannot produce a valid input, we are out of luck in reaching any deeper functionality." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Mutating Inputs\n", "\n", "The alternative to generating random strings from scratch is to start with a given _valid_ input, and then to subsequently _mutate_ it. A _mutation_ in this context is a simple string manipulation - say, inserting a (random) character, deleting a character, or flipping a bit in a character representation. This is called *mutational fuzzing* – in contrast to the _generational fuzzing_ techniques discussed earlier.\n", "\n", "Here are some mutations to get you started:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import random" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def delete_random_character(s):\n", " \"\"\"Returns s with a random character deleted\"\"\"\n", " if s == \"\":\n", " return s\n", "\n", " pos = random.randint(0, len(s) - 1)\n", " # print(\"Deleting\", repr(s[pos]), \"at\", pos)\n", " return s[:pos] + s[pos + 1:]" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "seed_input = \"A quick brown fox\"\n", "for i in range(10):\n", " x = delete_random_character(seed_input)\n", " print(repr(x))" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def insert_random_character(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", " # print(\"Inserting\", repr(random_character), \"at\", pos)\n", " return s[:pos] + random_character + s[pos:]" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "for i in range(10):\n", " print(repr(insert_random_character(seed_input)))" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def flip_random_character(s):\n", " \"\"\"Returns s with a random bit flipped in a random position\"\"\"\n", " if s == \"\":\n", " return 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", " # print(\"Flipping\", bit, \"in\", repr(c) + \", giving\", repr(new_c))\n", " return s[:pos] + new_c + s[pos + 1:]\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "for i in range(10):\n", " print(repr(flip_random_character(seed_input)))" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Let us now create a random mutator that randomly chooses which mutation to apply:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def mutate(s):\n", " \"\"\"Return s with a random mutation applied\"\"\"\n", " mutators = [\n", " delete_random_character,\n", " insert_random_character,\n", " flip_random_character\n", " ]\n", " mutator = random.choice(mutators)\n", " # print(mutator)\n", " return mutator(s)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "for i in range(10):\n", " print(repr(mutate(\"A quick brown fox\")))" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "The idea is now that _if_ we have some valid input(s) to begin with, we may create more input candidates by applying one of the above mutations. To see how this works, let's get back to URLs." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Mutating URLs" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "Let us now get back to our URL parsing problem. Let us create a function `is_valid_url()` that checks whether `http_program()` accepts the input." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def is_valid_url(url):\n", " try:\n", " result = http_program(url)\n", " return True\n", " except ValueError:\n", " return False" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "assert is_valid_url(\"http://www.google.com/search?q=fuzzing\")\n", "assert not is_valid_url(\"xyzzy\")" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Let us now apply the `mutate()` function on a given URL and see how many valid inputs we obtain." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "seed_input = \"http://www.google.com/search?q=fuzzing\"\n", "valid_inputs = set()\n", "trials = 20\n", "\n", "for i in range(trials):\n", " inp = mutate(seed_input)\n", " if is_valid_url(inp):\n", " valid_inputs.add(inp)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "We can now observe that by _mutating_ the original input, we get a high proportion of valid inputs:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "len(valid_inputs) / trials" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "What are the odds of also producing a `https:` prefix by mutating a `http:` sample seed input? We have to insert ($1 : 3$) the right character `'s'` ($1 : 96$) into the correct position ($1 : l$), where $l$ is the length of our seed input. This means that on average, we need this many runs:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "trials = 3 * 96 * len(seed_input)\n", "trials" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "We can actually afford this. Let's try:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from Timer import Timer" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "trials = 0\n", "with Timer() as t:\n", " while True:\n", " trials += 1\n", " inp = mutate(seed_input)\n", " if inp.startswith(\"https://\"):\n", " print(\n", " \"Success after\",\n", " trials,\n", " \"trials in\",\n", " t.elapsed_time(),\n", " \"seconds\")\n", " break\n" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "Of course, if we wanted to get, say, an `\"ftp://\"` prefix, we would need more mutations and more runs – most important, though, we would need to apply _multiple_ mutations." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Multiple Mutations\n", "\n", "So far, we have only applied one single mutation on a sample string. However, we can also apply _multiple_ mutations, further changing it. What happens, for instance, if we apply, say, 20 mutations on our sample string?" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "seed_input = \"http://www.google.com/search?q=fuzzing\"\n", "mutations = 50" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "inp = seed_input\n", "for i in range(mutations):\n", " if i % 5 == 0:\n", " print(i, \"mutations:\", repr(inp))\n", " inp = mutate(inp)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "As you see, the original seed input is hardly recognizable anymore. By mutating the input again and again, we get a higher variety in the input." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "To implement such multiple mutations in a single package, let us introduce a `MutationFuzzer` class. It takes a seed (a list of strings) as well as a minimum and a maximum number of mutations. " ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from Fuzzer import Fuzzer" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "class MutationFuzzer(Fuzzer):\n", " def __init__(self, seed, min_mutations=2, max_mutations=10):\n", " self.seed = seed\n", " self.min_mutations = min_mutations\n", " self.max_mutations = max_mutations\n", " self.reset()\n", "\n", " def reset(self):\n", " self.population = self.seed\n", " self.seed_index = 0" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "In the following, let us develop `MutationFuzzer` further by adding more methods to it. The Python language requires us to define an entire class with all methods as a single, continuous unit; however, we would like to introduce one method after another. To avoid this problem, we use a special hack: Whenever we want to introduce a new method to some class `C`, we use the construct\n", "\n", "```python\n", "class C(C):\n", " def new_method(self, args):\n", " pass\n", "```\n", "\n", "This seems to define `C` as a subclass of itself, which would make no sense – but actually, it introduces a new `C` class as a subclass of the _old_ `C` class, and then shadowing the old `C` definition. What this gets us is a `C` class with `new_method()` as a method, which is just what we want. (`C` objects defined earlier will retain the earlier `C` definition, though, and thus must be rebuilt.)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Using this hack, we can now add a `mutate()` method that actually invokes the above `mutate()` function. Having `mutate()` as a method is useful when we want to extend a `MutationFuzzer` later." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "class MutationFuzzer(MutationFuzzer):\n", " def mutate(self, inp):\n", " return mutate(inp)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Let's get back to our strategy, maximizing _diversity in coverage_ in our population. First, let us create a method `create_candidate()`, which randomly picks some input from our current population (`self.population`), and then applies between `min_mutations` and `max_mutations` mutation steps, returning the final result:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "class MutationFuzzer(MutationFuzzer):\n", " def create_candidate(self):\n", " candidate = random.choice(self.population)\n", " trials = random.randint(self.min_mutations, self.max_mutations)\n", " for i in range(trials):\n", " candidate = self.mutate(candidate)\n", " return candidate" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "The `fuzz()` method is set to first pick the seeds; when these are gone, we mutate:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "class MutationFuzzer(MutationFuzzer):\n", " def fuzz(self):\n", " if self.seed_index < len(self.seed):\n", " # Still seeding\n", " self.inp = self.seed[self.seed_index]\n", " self.seed_index += 1\n", " else:\n", " # Mutating\n", " self.inp = self.create_candidate()\n", " return self.inp" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "seed_input = \"http://www.google.com/search?q=fuzzing\"\n", "mutation_fuzzer = MutationFuzzer(seed=[seed_input])\n", "mutation_fuzzer.fuzz()" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "mutation_fuzzer.fuzz()" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "mutation_fuzzer.fuzz()" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "With every new invocation of `fuzz()`, we get another variant with multiple mutations applied. The higher variety in inputs, though, increases the risk of having an invalid input. The key to success lies in the idea of _guiding_ these mutations – that is, _keeping those that are especially valuable._" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Guiding by Coverage\n", "\n", "To cover as much functionality as possible, one can rely on either _specified_ or _implemented_ functionality, as discussed in the [\"Coverage\"](Coverage.ipynb) chapter. For now, we will not assume that there is a specification of program behavior (although it _definitely_ would be good to have one!). We _will_ assume, though, that the program to be tested exists – and that we can leverage its structure to guide test generation.\n", "\n", "Since testing always executes the program at hand, one can always gather information about its execution – the least is the information needed to decide whether a test passes or fails. Since coverage is frequently measured as well to determine test quality, let us also assume we can retrieve coverage of a test run. The question is then: _How can we leverage coverage to guide test generation?_" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "One particularly successful idea is implemented in the popular fuzzer named [American fuzzy lop](http://lcamtuf.coredump.cx/afl/), or *AFL* for short. Just like our examples above, AFL evolves test cases that have been successful – but for AFL, \"success\" means _finding a new path through the program execution_. This way, AFL can keep on mutating inputs that so far have found new paths; and if an input finds another path, it will be retained as well." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Let us build such a strategy. We start with introducing a `Runner` class that captures the coverage for a given function. First, a `FunctionRunner` class:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from Fuzzer import Runner" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "class FunctionRunner(Runner):\n", " def __init__(self, function):\n", " \"\"\"Initialize. `function` is a function to be executed\"\"\"\n", " self.function = function\n", "\n", " def run_function(self, inp):\n", " return self.function(inp)\n", "\n", " def run(self, inp):\n", " try:\n", " result = self.run_function(inp)\n", " outcome = self.PASS\n", " except Exception:\n", " result = None\n", " outcome = self.FAIL\n", "\n", " return result, outcome" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "http_runner = FunctionRunner(http_program)\n", "http_runner.run(\"https://foo.bar/\")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "We can now extend the `FunctionRunner` class such that it also measures coverage. After invoking `run()`, the `coverage()` method returns the coverage achieved in the last run." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from Coverage import Coverage, population_coverage" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "class FunctionCoverageRunner(FunctionRunner):\n", " def run_function(self, inp):\n", " with Coverage() as cov:\n", " try:\n", " result = super().run_function(inp)\n", " except Exception as exc:\n", " self._coverage = cov.coverage()\n", " raise exc\n", "\n", " self._coverage = cov.coverage()\n", " return result\n", "\n", " def coverage(self):\n", " return self._coverage" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "http_runner = FunctionCoverageRunner(http_program)\n", "http_runner.run(\"https://foo.bar/\")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Here are the first five locations covered: " ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "print(list(http_runner.coverage())[:5])" ] }, { "cell_type": "markdown", "metadata": { "run_control": {}, "slideshow": { "slide_type": "subslide" } }, "source": [ "Now for the main class. We maintain the population and a set of coverages already achieved (`coverages_seen`). The `fuzz()` helper function takes an input and runs the given `function()` on it. If its coverage is new (i.e. not in `coverages_seen`), the input is added to `population` and the coverage to `coverages_seen`." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "class MutationCoverageFuzzer(MutationFuzzer):\n", " def reset(self):\n", " super().reset()\n", " self.coverages_seen = set()\n", " # Now empty; we fill this with seed in the first fuzz runs\n", " self.population = []\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 outcome == Runner.PASS and new_coverage not in self.coverages_seen:\n", " # We have new coverage\n", " self.population.append(self.inp)\n", " self.coverages_seen.add(new_coverage)\n", "\n", " return result" ] }, { "cell_type": "markdown", "metadata": { "run_control": {}, "slideshow": { "slide_type": "subslide" } }, "source": [ "Let us now put this to use:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "seed_input = \"http://www.google.com/search?q=fuzzing\"\n", "mutation_fuzzer = MutationCoverageFuzzer(seed=[seed_input])\n", "mutation_fuzzer.runs(http_runner, trials=10000)\n", "mutation_fuzzer.population" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Success! In our population, _each and every input_ now is valid and has a different coverage, coming from various combinations of schemes, paths, queries, and fragments." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "all_coverage, cumulative_coverage = population_coverage(\n", " mutation_fuzzer.population, http_program)\n", "\n", "import matplotlib.pyplot as plt\n", "plt.plot(cumulative_coverage)\n", "plt.title('Coverage of urlparse() with random inputs')\n", "plt.xlabel('# of inputs')\n", "plt.ylabel('lines covered');" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "The nice thing about this strategy is that, applied to larger programs, it will happily explore one path after the other – covering functionality after functionality. All that is needed is a means to capture the coverage." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Lessons Learned\n", "\n", "* Randomly generated inputs are frequently invalid – and thus exercise mostly input processing functionality.\n", "* Mutations from existing valid inputs have much higher chances to be valid, and thus to exercise functionality beyond input processing.\n" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Next Steps\n", "\n", "Our aim is still to sufficiently cover functionality, such that we can trigger as many bugs as possible. To this end, we focus on two classes of techniques:\n", "\n", "1. Try to cover as much _specified_ functionality as possible. Here, we would need a _specification of the input format,_ distinguishing between individual input elements such as (in our case) numbers, operators, comments, and strings – and attempting to cover as many of these as possible. We will explore this as it comes to [grammar-based testing](GrammarFuzzer.ipynb), and especially in [grammar-based mutations](Parser.ipynb).\n", "\n", "2. Try to cover as much _implemented_ functionality as possible. The concept of a \"population\" that is systematically \"evolved\" through \"mutations\" will be explored in depth when discussing [search-based testing](SearchBasedFuzzer.ipynb). Furthermore, [symbolic testing](SymbolicFuzzer.ipynb) introduces how to systematically reach program locations by solving the conditions that lie on their paths.\n", "\n", "These two techniques make up the gist of the book; and, of course, they can also be combined with each other. As usual, we provide runnable code for all. Enjoy!" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Exercises\n" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "### Exercise 1: Fuzzing CGI decode with Mutations\n", "\n", "Apply the above _guided_ mutation-based fuzzing technique on `cgi_decode()` from the [\"Coverage\"](Coverage.ipynb) chapter. How many trials do you need until you cover all variations of `+`, `%` (valid and invalid), and regular characters?" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "run_control": {}, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from Coverage import cgi_decode" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "run_control": {}, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "seed = [\"Hello World\"]\n", "cgi_runner = FunctionCoverageRunner(cgi_decode)\n", "m = MutationCoverageFuzzer(seed)\n", "results = m.runs(cgi_runner, 10000)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "m.population" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "cgi_runner.coverage()" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "all_coverage, cumulative_coverage = population_coverage(\n", " m.population, cgi_decode)\n", "\n", "import matplotlib.pyplot as plt\n", "plt.plot(cumulative_coverage)\n", "plt.title('Coverage of cgi_decode() with random inputs')\n", "plt.xlabel('# of inputs')\n", "plt.ylabel('lines covered');" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "After 10,000 runs, we have managed to synthesize a `+` character and a valid `%xx` form. We can still do better." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" }, "solution2": "hidden", "solution2_first": true }, "source": [ "### Exercise 2: Fuzzing bc with Mutations\n", "\n", "Apply the above mutation-based fuzzing technique on `bc`, as in the chapter [\"Introduction to Fuzzing\"](Fuzzer.ipynb).\n", "\n", "#### Part 1: Non-Guided Mutations\n", "\n", "Start with non-guided mutations. How many of the inputs are valid?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "source": [ "**Solution.** This is just a matter of tying a `ProgramRunner` to a `MutationFuzzer`:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [], "source": [ "from Fuzzer import ProgramRunner" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [], "source": [ "seed = [\"1 + 1\"]\n", "bc = ProgramRunner(program=\"bc\")\n", "m = MutationFuzzer(seed)\n", "outcomes = m.runs(bc, trials=100)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [], "source": [ "outcomes[:3]" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [], "source": [ "sum(1 for completed_process, outcome in outcomes if completed_process.stderr == \"\")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "#### Part 2: Guided Mutations\n", "\n", "Continue with _guided_ mutations. To this end, you will have to find a way to extract coverage from a C program such as `bc`. Proceed in these steps:\n", "\n", "First, get [GNU bc](https://www.gnu.org/software/bc/); download, say, `bc-1.07.1.tar.gz` and unpack it:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "!curl -O mirrors.kernel.org/gnu/bc/bc-1.07.1.tar.gz" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "!tar xfz bc-1.07.1.tar.gz" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Second, configure the package:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "!cd bc-1.07.1; ./configure" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Third, compile the package with special flags:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "!cd bc-1.07.1; make CFLAGS=\"--coverage\"" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "The file `bc/bc` should now be executable..." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "!cd bc-1.07.1/bc; echo 2 + 2 | ./bc" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "...and you should be able to run the `gcov` program to retrieve coverage information." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "!cd bc-1.07.1/bc; gcov main.c" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "As sketched in the [\"Coverage\" chapter](Coverage.ipynb), the file [bc-1.07.1/bc/main.c.gcov](bc-1.07.1/bc/main.c.gcov) now holds the coverage information for `bc.c`. Each line is prefixed with the number of times it was executed. `#####` means zero times; `-` means non-executable line." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Parse the GCOV file for `bc` and create a `coverage` set, as in `FunctionCoverageRunner`. Make this a `ProgramCoverageRunner` class that would be constructed with a list of source files (`bc.c`, `main.c`, `load.c`) to run `gcov` on." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "When you're done, don't forget to clean up:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "!rm -fr bc-1.07.1 bc-1.07.1.tar.gz" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "### Exercise 3\n", "\n", "In this [blog post](https://lcamtuf.blogspot.com/2014/08/binary-fuzzing-strategies-what-works.html), the author of _American Fuzzy Lop_ (AFL), a very popular mutation-based fuzzer discusses the efficiency of various mutation operators. Implement four of them and evaluate their efficiency as in the examples above." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "### Exercise 4\n", "\n", "When adding a new element to the list of candidates, AFL does actually not compare the _coverage_, but adds an element if it exercises a new _branch_. Using branch coverage from the exercises of the [\"Coverage\"](Coverage.ipynb) chapter, implement this \"branch\" strategy and compare it against the \"coverage\" strategy, above." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "### Exercise 5\n", "\n", "Design and implement a system that will gather a population of URLs from the Web. Can you achieve a higher coverage with these samples? What if you use them as initial population for further mutation?" ] } ], "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.8" }, "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 }, "toc-autonumbering": false }, "nbformat": 4, "nbformat_minor": 2 }