{ "cells": [ { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" }, "tags": [] }, "source": [ "# Fuzzing: Breaking Things with Random Inputs\n", "\n", "In this chapter, we'll start with one of the simplest test generation techniques. The key idea of random text generation, also known as *fuzzing*, is to feed a _string of random characters_ into a program in the hope to uncover failures." ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:14:01.860065Z", "iopub.status.busy": "2024-01-18T17:14:01.859646Z", "iopub.status.idle": "2024-01-18T17:14:01.917070Z", "shell.execute_reply": "2024-01-18T17:14:01.916588Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [ { "data": { "text/html": [ "\n", " \n", " " ], "text/plain": [ "" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from bookutils import YouTubeVideo\n", "YouTubeVideo('YjO1pIx7wS4')" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "source": [ "**Prerequisites**\n", "\n", "* You should know fundamentals of software testing; for instance, from the chapter [\"Introduction to Software Testing\"](Intro_Testing.ipynb).\n", "* You should have a decent understanding of Python; for instance, from the [Python tutorial](https://docs.python.org/3/tutorial/).\n" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "source": [ "We can make these prerequisites explicit. First, we'll import a standard package required for working in notebooks." ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:14:01.940949Z", "iopub.status.busy": "2024-01-18T17:14:01.940730Z", "iopub.status.idle": "2024-01-18T17:14:01.943152Z", "shell.execute_reply": "2024-01-18T17:14:01.942854Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import bookutils.setup" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:14:01.944758Z", "iopub.status.busy": "2024-01-18T17:14:01.944635Z", "iopub.status.idle": "2024-01-18T17:14:01.946319Z", "shell.execute_reply": "2024-01-18T17:14:01.946062Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "from typing import Dict, Tuple, Union, List, Any" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Now, we explicitly import (and thus require) the earlier chapter." ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:14:01.947781Z", "iopub.status.busy": "2024-01-18T17:14:01.947681Z", "iopub.status.idle": "2024-01-18T17:14:01.999446Z", "shell.execute_reply": "2024-01-18T17:14:01.999160Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import Intro_Testing" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "## Synopsis\n", "\n", "\n", "To [use the code provided in this chapter](Importing.ipynb), write\n", "\n", "```python\n", ">>> from fuzzingbook.Fuzzer import \n", "```\n", "\n", "and then make use of the following features.\n", "\n", "\n", "This chapter provides two important classes, introduced in [A Fuzzing Architecture](#A-Fuzzing-Architecture):\n", "\n", "* `Fuzzer` as a base class for fuzzers; and\n", "* `Runner` as a base class for programs under test.\n", "\n", "### Fuzzers\n", "\n", "`Fuzzer` is a base class for fuzzers, with `RandomFuzzer` as a simple instantiation. The `fuzz()` method of `Fuzzer` objects returns a string with a generated input.\n", "\n", "```python\n", ">>> random_fuzzer = RandomFuzzer()\n", ">>> random_fuzzer.fuzz()\n", "'%$<1&<%+=!\"83?+)9:++9138 42/ \"7;0-,)06 \"1(2;6>?99$%7!!*#96=>2&-/(5*)=$;0$$+;<12\"?30&'\n", "```\n", "The `RandomFuzzer()` constructor allows a number of keyword arguments:\n", "\n", "```python\n", ">>> print(RandomFuzzer.__init__.__doc__)\n", "Produce strings of `min_length` to `max_length` characters\n", " in the range [`char_start`, `char_start` + `char_range`)\n", "\n", ">>> random_fuzzer = RandomFuzzer(min_length=10, max_length=20, char_start=65, char_range=26)\n", ">>> random_fuzzer.fuzz()\n", "'XGZVDDPZOOW'\n", "```\n", "![](PICS/Fuzzer-synopsis-1.svg)\n", "\n", "### Runners\n", "\n", "A `Fuzzer` can be paired with a `Runner`, which takes the fuzzed strings as input. Its result is a class-specific _status_ and an _outcome_ (`PASS`, `FAIL`, or `UNRESOLVED`). A `PrintRunner` will simply print out the given input and return a `PASS` outcome:\n", "\n", "```python\n", ">>> print_runner = PrintRunner()\n", ">>> random_fuzzer.run(print_runner)\n", "EQYGAXPTVPJGTYHXFJ\n", "\n", "('EQYGAXPTVPJGTYHXFJ', 'UNRESOLVED')\n", "```\n", "A `ProgramRunner` will feed the generated input into an external program. Its result is a pair of the program status (a `CompletedProcess` instance) and an _outcome_ (`PASS`, `FAIL`, or `UNRESOLVED`):\n", "\n", "```python\n", ">>> cat = ProgramRunner('cat')\n", ">>> random_fuzzer.run(cat)\n", "(CompletedProcess(args='cat', returncode=0, stdout='BZOQTXFBTEOVYX', stderr=''),\n", " 'PASS')\n", "```\n", "![](PICS/Fuzzer-synopsis-2.svg)\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## A Testing Assignment\n", "\n", "Fuzzing was born in a \"dark and stormy night in the Fall of 1988\" \\cite{Takanen2008}. Sitting in his apartment in Wisconsin, Madison, professor Barton Miller was connected to his university computer via a 1200 baud telephone line. The thunderstorm caused noise on the line, and this noise in turn caused the UNIX commands on either end to get bad inputs – and crash. The frequent crashes surprised him – surely, programs should be more robust than that? As a scientist, he wanted to investigate the extent of the problem and its causes. So he crafted a _programming exercise_ for his students at the University of Wisconsin-Madison – an exercise that would have his students create the first fuzzers." ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "This is how the [assignment](http://pages.cs.wisc.edu/~bart/fuzz/CS736-Projects-f1988.pdf) read:\n", "\n", "> The goal of this project is to evaluate the robustness of various UNIX utility programs, given an unpredictable input stream. [...] First, you will build a _fuzz generator_. This is a program that will output a random character stream. Second, you will take the fuzz generator and use it to attack as many UNIX utilities as possible, with the goal of trying to break them.\n", "\n", "This assignment captures the essence of fuzzing: _Create random inputs, and see if they break things._ Just let it run long enough, and you'll see." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## A Simple Fuzzer\n", "\n", "Let us try to fulfill this assignment and build a fuzz generator. The idea is to produce random characters, adding them to a buffer string variable (`out`), and finally returning the string." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "This implementation uses the following Python features and functions:\n", "\n", "* `random.randrange(start, end)` – return a random number $[$ `start`, `end` $)$\n", "* `range(start, end)` – create an iterator (which can be used as a list) with integers in the range $[$ `start`, `end` $)$.\n", "* `for elem in list: body` – execute `body` in a loop with `elem` taking each value from `list`.\n", "* `for i in range(start, end): body` – execute `body` in a loop with `i` from `start` to `end` $-$ 1.\n", "* `chr(n)` – return a character with ASCII code `n`" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "source": [ "To use random numbers, we have to import the respective module." ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:02.001457Z", "iopub.status.busy": "2024-01-18T17:14:02.001335Z", "iopub.status.idle": "2024-01-18T17:14:02.003014Z", "shell.execute_reply": "2024-01-18T17:14:02.002750Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import random" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "source": [ "Here comes the actual `fuzzer()` function." ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "button": false, "code_folding": [], "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:02.004833Z", "iopub.status.busy": "2024-01-18T17:14:02.004716Z", "iopub.status.idle": "2024-01-18T17:14:02.006865Z", "shell.execute_reply": "2024-01-18T17:14:02.006608Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def fuzzer(max_length: int = 100, char_start: int = 32, char_range: int = 32) -> str:\n", " \"\"\"A string of up to `max_length` characters\n", " in the range [`char_start`, `char_start` + `char_range`)\"\"\"\n", " string_length = random.randrange(0, max_length + 1)\n", " out = \"\"\n", " for i in range(0, string_length):\n", " out += chr(random.randrange(char_start, char_start + char_range))\n", " return out" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "With its default arguments, the `fuzzer()` function returns a string of random characters:" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:02.008557Z", "iopub.status.busy": "2024-01-18T17:14:02.008424Z", "iopub.status.idle": "2024-01-18T17:14:02.010523Z", "shell.execute_reply": "2024-01-18T17:14:02.010223Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "'!7#%\"*#0=)$;%6*;>638:*>80\"=(/*:-(2<4 !:5*6856&?\"\"11<7+%<%7,4.8,*+&,,$,.\"'" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "fuzzer()" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "Bart Miller coined the term \"fuzz\" as the name for such random, unstructured data. Now imagine that this \"fuzz\" string was the input to a program expecting a specific input format – say, a comma-separated list of values, or an e-mail address. Would the program be able to process such an input without any problems?" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "If the above fuzzing input already is intriguing, consider that fuzzing can easily be set up to produce other kinds of input. For instance, we can also have `fuzzer()` produce a series of lowercase letters. We use `ord(c)` to return the ASCII code of the character `c`." ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:02.012190Z", "iopub.status.busy": "2024-01-18T17:14:02.012080Z", "iopub.status.idle": "2024-01-18T17:14:02.014497Z", "shell.execute_reply": "2024-01-18T17:14:02.014224Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "'zskscocrxllosagkvaszlngpysurezehvcqcghygphnhonehczraznkibltfmocxddoxcmrvatcleysksodzlwmzdndoxrjfqigjhqjxkblyrtoaydlwwisrvxtxsejhfbnforvlfisojqaktcxpmjqsfsycisoexjctydzxzzutukdztxvdpqbjuqmsectwjvylvbixzfmqiabdnihqagsvlyxwxxconminadcaqjdzcnzfjlwccyudmdfceiepwvyggepjxoeqaqbjzvmjdlebxqvehkmlevoofjlilegieeihmetjappbisqgrjhglzgffqrdqcwfmmwqecxlqfpvgtvcddvmwkplmwadgiyckrfjddxnegvmxravaunzwhpfpyzuyyavwwtgykwfszasvlbwojetvcygectelwkputfczgsfsbclnkzzcjfywitooygjwqujseflqyvqgyzpvknddzemkegrjjrshbouqxcmixnqhgsgdwgzwzmgzfajymbcfezqxndbmzwnxjeevgtpjtcwgbzptozflrwvuopohbvpmpaifnyyfvbzzdsdlznusarkmmtazptbjbqdkrsnrpgdffemnpehoapiiudokczwrvpsonybfpaeyorrgjdmgvkvupdtkrequicexqkoikygepawmwsdcrhivoegynnhodfhryeqbebtbqnwhogdfrsrksntqjbocvislhgrgchkhpaiugpbdygwkhrtyniufabdnqhtnwreiascfvmuhettfpbowbjadfxnbtzhobnxsnf'" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "fuzzer(1000, ord('a'), 26)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "Assume a program expects an identifier as its input. Would it expect such a long identifier?" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:14:02.015972Z", "iopub.status.busy": "2024-01-18T17:14:02.015871Z", "iopub.status.idle": "2024-01-18T17:14:02.017385Z", "shell.execute_reply": "2024-01-18T17:14:02.017145Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from bookutils import quiz" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:14:02.018813Z", "iopub.status.busy": "2024-01-18T17:14:02.018725Z", "iopub.status.idle": "2024-01-18T17:14:02.023231Z", "shell.execute_reply": "2024-01-18T17:14:02.022937Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/html": [ "\n", " \n", " \n", " \n", "
\n", "

Quiz

\n", "

\n", "

Which of these produces strings with arbitrary long decimal numbers?
\n", "

\n", "

\n", "

\n", " \n", " \n", "
\n", " \n", " \n", "
\n", " \n", " \n", "
\n", " \n", " \n", "
\n", " \n", "
\n", "

\n", " \n", " \n", "
\n", " " ], "text/plain": [ "" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "quiz(\"Which of these produces strings with arbitrary long decimal numbers?\",\n", " [\n", " \"`fuzzer(100, 1, 100)`\",\n", " \"`fuzzer(100, 100, 0)`\",\n", " \"`fuzzer(100, 10, ord('0'))`\",\n", " \"`fuzzer(100, ord('0'), 10)`\",\n", " ], \"1 ** (2 % 3) * 4\")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Indeed! It is the last one that does the trick:" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:14:02.025119Z", "iopub.status.busy": "2024-01-18T17:14:02.024984Z", "iopub.status.idle": "2024-01-18T17:14:02.027206Z", "shell.execute_reply": "2024-01-18T17:14:02.026951Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "'905902398493166953126081485047020401153418590518545517740565959745145909835837'" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "fuzzer(100, ord('0'), 10)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Fuzzing External Programs\n", "\n", "Let us see what happens if we actually invoke an external program with fuzzed inputs. To this end, let us proceed in two steps. First, we create an _input file_ with fuzzed test data; then we feed this input file into a program of choice." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "### Creating Input Files\n", "\n", "Let us obtain a temporary file name such that we do not clutter the file system." ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:02.028727Z", "iopub.status.busy": "2024-01-18T17:14:02.028621Z", "iopub.status.idle": "2024-01-18T17:14:02.030116Z", "shell.execute_reply": "2024-01-18T17:14:02.029901Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import os\n", "import tempfile" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:02.031518Z", "iopub.status.busy": "2024-01-18T17:14:02.031438Z", "iopub.status.idle": "2024-01-18T17:14:02.033559Z", "shell.execute_reply": "2024-01-18T17:14:02.033339Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt\n" ] } ], "source": [ "basename = \"input.txt\"\n", "tempdir = tempfile.mkdtemp()\n", "FILE = os.path.join(tempdir, basename)\n", "print(FILE)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "We can now open this file for writing. The Python `open()` function opens a file into which we can then write arbitrary contents. It is commonly used in conjunction with the `with` statement, which ensures that the file is closed as soon as it is no longer needed." ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:02.035076Z", "iopub.status.busy": "2024-01-18T17:14:02.034997Z", "iopub.status.idle": "2024-01-18T17:14:02.036886Z", "shell.execute_reply": "2024-01-18T17:14:02.036640Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "data = fuzzer()\n", "with open(FILE, \"w\") as f:\n", " f.write(data)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "We can verify that the file was actually created by reading its contents:" ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:02.038457Z", "iopub.status.busy": "2024-01-18T17:14:02.038363Z", "iopub.status.idle": "2024-01-18T17:14:02.040572Z", "shell.execute_reply": "2024-01-18T17:14:02.040276Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "18%55*,5\n" ] } ], "source": [ "contents = open(FILE).read()\n", "print(contents)\n", "assert(contents == data)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "### Invoking External Programs\n", "\n", "Now that we have an input file, we can invoke a program on it. For the fun of it, let us test the `bc` calculator program, which takes an arithmetic expression and evaluates it.\n", "\n", "To invoke `bc`, let us use the Python `subprocess` module. This is how this works:\n" ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:02.042164Z", "iopub.status.busy": "2024-01-18T17:14:02.042057Z", "iopub.status.idle": "2024-01-18T17:14:02.043784Z", "shell.execute_reply": "2024-01-18T17:14:02.043551Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "import os\n", "import subprocess" ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:02.045250Z", "iopub.status.busy": "2024-01-18T17:14:02.045166Z", "iopub.status.idle": "2024-01-18T17:14:02.053895Z", "shell.execute_reply": "2024-01-18T17:14:02.053525Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "program = \"bc\"\n", "with open(FILE, \"w\") as f:\n", " f.write(\"2 + 2\\n\")\n", "result = subprocess.run([program, FILE],\n", " stdin=subprocess.DEVNULL,\n", " stdout=subprocess.PIPE,\n", " stderr=subprocess.PIPE,\n", " universal_newlines=True) # Will be \"text\" in Python 3.7" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "From the `result`, we can check the program output. In the case of `bc`, this is the result of evaluating the arithmetic expression:" ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:02.055879Z", "iopub.status.busy": "2024-01-18T17:14:02.055701Z", "iopub.status.idle": "2024-01-18T17:14:02.058118Z", "shell.execute_reply": "2024-01-18T17:14:02.057866Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "'4\\n'" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "result.stdout" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "We can also check the status. A value of 0 indicates that the program terminated correctly." ] }, { "cell_type": "code", "execution_count": 19, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:02.059725Z", "iopub.status.busy": "2024-01-18T17:14:02.059610Z", "iopub.status.idle": "2024-01-18T17:14:02.061681Z", "shell.execute_reply": "2024-01-18T17:14:02.061439Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "0" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "result.returncode" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "Any error messages would be available in `results.stderr`:" ] }, { "cell_type": "code", "execution_count": 20, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:02.063129Z", "iopub.status.busy": "2024-01-18T17:14:02.063019Z", "iopub.status.idle": "2024-01-18T17:14:02.064951Z", "shell.execute_reply": "2024-01-18T17:14:02.064710Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "''" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "result.stderr" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Instead of `bc`, you can actually put in any program you like. Be aware, though, that if your program is able to change or even damage your system, there is quite a risk that the fuzzed input contains data or commands that do precisely this." ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:14:02.066358Z", "iopub.status.busy": "2024-01-18T17:14:02.066256Z", "iopub.status.idle": "2024-01-18T17:14:02.070082Z", "shell.execute_reply": "2024-01-18T17:14:02.069843Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/html": [ "\n", " \n", " \n", " \n", "
\n", "

Quiz

\n", "

\n", "

Just for the fun of it, imagine you would test a file removal program - say rm -fr FILE, where FILE is a string produced by fuzzer(). What is the chance of fuzzer() (with default arguments) producing a FILE argument that results in deleting all your files?
\n", "

\n", "

\n", "

\n", " \n", " \n", "
\n", " \n", " \n", "
\n", " \n", " \n", "
\n", " \n", " \n", "
\n", " \n", "
\n", "

\n", " \n", " \n", "
\n", " " ], "text/plain": [ "" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "quiz(\"Just for the fun of it, imagine you would test a file removal program - \"\n", " \"say `rm -fr FILE`, where `FILE` is a string produced by `fuzzer()`. \"\n", " \"What is the chance of `fuzzer()` (with default arguments) producing a `FILE` \"\n", " \"argument that results in deleting all your files?\",\n", " [\n", " \"About one in a billion\",\n", " \"About one in a million\",\n", " \"About one in a thousand\",\n", " \"About one in ten\"\n", " ], \"9 ** 0.5\")" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "The chance is actually higher than you may think. If you remove `/` (the root of all files), for instance, your entire file system will be gone. If you remove `.` (the current folder), all the files in the current directory will be gone. \n", "\n", "The probability of generating a string that is exactly 1 character long is 1/101, this is because the length of the string is determined by calling random.randrange(0, max_length + 1), where the default value of max_length is 100. Per the description given of random.randrange, that should return a random number in [0, 99 + 1). So, we end up with the inclusive range [0, 100] where there are 101 values in the interval.\n", "\n", "For `/` or `.` to be produced, you need a string length of 1 (chance: 1 out of 101) and one of these two characters (chance: 2 out of 32)." ] }, { "cell_type": "code", "execution_count": 22, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:14:02.071632Z", "iopub.status.busy": "2024-01-18T17:14:02.071544Z", "iopub.status.idle": "2024-01-18T17:14:02.073832Z", "shell.execute_reply": "2024-01-18T17:14:02.073510Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "0.0006188118811881188" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "1/101 * 2/32" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "The above code block precludes the possiblity of removing `~` (your home directory), this is because the probability of generating the character '~' is not 1/32; it is 0/32. The characters are created by calling chr(random.randrange(char_start, char_start + char_range)), where the default value of char_start is 32 and the default value of char_range is 32. The documentation for chr reads, \"[r]eturn the string representing a character whose Unicode code point is the integer i.\" The Unicode code point for '~' is 126 and therefore, not in the interval [32, 64). \n", "\n", "If the code were to be changed so that char_range = 95 then the probability of obtaining the character '~' would be 1/94 , thus resulting in the probability of the event of deleting all files being equal to 0.000332\n", "\n", "And all your files in the home directory will be gone" ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:14:02.075526Z", "iopub.status.busy": "2024-01-18T17:14:02.075440Z", "iopub.status.idle": "2024-01-18T17:14:02.077608Z", "shell.execute_reply": "2024-01-18T17:14:02.077332Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "0.0003327969736765437" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "3/94 * 1/94 * 99/101" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "However, we can actually deal with any string as long as the _second_ character is a space – after all, `rm -fr / WHATEVER` will first deal with `/`, and only then with whatever follows. The chances for the first character are 2 out of 32 as the code block above only allows for the probability of obtaining a `/` or a `.` but not a `~`.\n", "\n", "For the space the probability is 1 out of 32.\n", "\n", "We have to include the term for the probability of obtaining at least 2 characters which is required for the scenario of obtaining a space as the second character. This probability is 99/101 because it is calculated as (1 - probabilty of obtaining a single character or no character at all), so it is equal to 1-(2/101).\n", "\n", "Therefore, the probability calculation for the event of deleting all files in the case of having a space for the second character is:\n", "\n", "[probability of obtaining '/' or '. ' followed by a space] = [the probability of obtaining either the '/' character or the '. ' character] * [the probability of obtaining space] * [Probability of getting at least 2 characters] = 0.001914\n", "\n", "\n", "\n", "Diagram of probability of obtaining at least 2 characters." ] }, { "cell_type": "code", "execution_count": 24, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:14:02.079044Z", "iopub.status.busy": "2024-01-18T17:14:02.078959Z", "iopub.status.idle": "2024-01-18T17:14:02.081229Z", "shell.execute_reply": "2024-01-18T17:14:02.080793Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "0.0019144492574257425" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "2/32 * 1/32 * 99/101" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Given that fuzz tests are typically run millions of times, you really don't want to take this risk. Run your fuzzers in a safe environment that you can reset at will, such as a Docker container." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "### Long-Running Fuzzing\n", "\n", "Let us now feed a large number of inputs into our tested program, to see whether it might crash on some. We store all results in the `runs` variable as pairs of input data and the actual result. (Note: running this may take a while.)" ] }, { "cell_type": "code", "execution_count": 25, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:02.082946Z", "iopub.status.busy": "2024-01-18T17:14:02.082808Z", "iopub.status.idle": "2024-01-18T17:14:02.431960Z", "shell.execute_reply": "2024-01-18T17:14:02.431464Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "trials = 100\n", "program = \"bc\"\n", "\n", "runs = []\n", "\n", "for i in range(trials):\n", " data = fuzzer()\n", " with open(FILE, \"w\") as f:\n", " f.write(data)\n", " result = subprocess.run([program, FILE],\n", " stdin=subprocess.DEVNULL,\n", " stdout=subprocess.PIPE,\n", " stderr=subprocess.PIPE,\n", " universal_newlines=True)\n", " runs.append((data, result))" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "We can now query `runs` for some statistics. For instance, we can query how many runs actually passed -- that is, there were no error messages. We use a _list comprehension_ here: The form _expression_ `for` _element_ `in` _list_ `if` _condition_ returns a list of evaluated _expressions_ in which each _element_ comes from _list_ if the _condition_ was true. (Actually, a list comprehension returns a _list generator_, but for our purposes, the generator behaves like a list.) Here, we have the _expression_ be 1 for all elements where _condition_ holds, and we use `sum()` to sum over all elements in the list." ] }, { "cell_type": "code", "execution_count": 26, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:02.433899Z", "iopub.status.busy": "2024-01-18T17:14:02.433773Z", "iopub.status.idle": "2024-01-18T17:14:02.436380Z", "shell.execute_reply": "2024-01-18T17:14:02.436117Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "9" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sum(1 for (data, result) in runs if result.stderr == \"\")" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "Most inputs apparently are invalid – not a big surprise, as it is unlikely that a random input contains a valid arithmetic expression." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Let us take a look at the first error message: " ] }, { "cell_type": "code", "execution_count": 27, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:02.437917Z", "iopub.status.busy": "2024-01-18T17:14:02.437811Z", "iopub.status.idle": "2024-01-18T17:14:02.439886Z", "shell.execute_reply": "2024-01-18T17:14:02.439640Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "'5&8>\"86,?\"/7!1%5-**&-$&)$91;\"21(\\'8\"(%$4,(\"(&!67%89$!.?(*(96(28$=6029:<:$(6 !-+2622(&4'\n", "\n", "Parse error: bad character '&'\n", " /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\n", "\n", "\n" ] } ], "source": [ "errors = [(data, result) for (data, result) in runs if result.stderr != \"\"]\n", "(first_data, first_result) = errors[0]\n", "\n", "print(repr(first_data))\n", "print(first_result.stderr)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Are there any runs with messages other than `illegal character`, `parse error`, or `syntax error`? (Say, something like `crash` or `you found a fatal bug`?) Not very many:" ] }, { "cell_type": "code", "execution_count": 28, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:02.441439Z", "iopub.status.busy": "2024-01-18T17:14:02.441172Z", "iopub.status.idle": "2024-01-18T17:14:02.444215Z", "shell.execute_reply": "2024-01-18T17:14:02.443989Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "[\"\\nParse error: bad character '&'\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n\",\n", " '\\nParse error: bad expression\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad expression\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad expression\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad expression\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad expression\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad expression\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad expression\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad expression\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " \"\\nParse error: bad character '&'\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n\",\n", " '\\nParse error: bad assignment: left side must be scale, ibase, obase, seed, last, var, or array element\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad expression\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " \"\\nParse error: bad character '?'\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n\",\n", " \"\\nParse error: bad character '''\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n\",\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " \"\\nParse error: bad character '?'\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n\",\n", " \"\\nParse error: bad character ':'\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n\",\n", " \"\\nParse error: bad character '&'\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n\",\n", " \"\\nParse error: bad character ':'\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n\",\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad expression\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " \"\\nParse error: bad character '?'\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n\",\n", " '\\nParse error: bad assignment: left side must be scale, ibase, obase, seed, last, var, or array element\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad expression\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " \"\\nParse error: bad character '&'\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n\",\n", " \"\\nParse error: bad character '''\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n\",\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad expression\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " \"\\nParse error: bad character '''\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n\",\n", " \"\\nParse error: bad character '''\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n\",\n", " \"\\nParse error: bad character '&'\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n\",\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " \"\\nParse error: bad character ':'\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n\",\n", " \"\\nParse error: bad character ':'\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n\",\n", " '\\nParse error: bad expression\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad expression\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " \"\\nParse error: bad character '&'\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n\",\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad expression\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad expression\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad expression\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " \"\\nParse error: bad character ':'\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n\",\n", " \"\\nParse error: bad character ':'\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n\",\n", " '\\nParse error: bad expression\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad expression\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad expression\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " \"\\nParse error: bad character '&'\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n\",\n", " \"\\nParse error: bad character '&'\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n\",\n", " \"\\nParse error: bad character '''\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n\",\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad expression\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " \"\\nParse error: bad character ':'\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n\",\n", " '\\nParse error: bad expression\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " \"\\nParse error: bad character '''\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n\",\n", " '\\nParse error: bad expression\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " \"\\nParse error: bad character ':'\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n\",\n", " \"\\nParse error: bad character '''\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n\",\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad expression\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " \"\\nParse error: bad character '&'\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n\",\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " \"\\nParse error: bad character '?'\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n\",\n", " '\\nParse error: bad expression\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad expression\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad expression\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " \"\\nParse error: bad character ':'\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n\",\n", " \"\\nParse error: bad character '''\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n\",\n", " '\\nParse error: bad expression\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n',\n", " '\\nParse error: bad token\\n /var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/tmpnds9g27_/input.txt:1\\n\\n']" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[result.stderr for (data, result) in runs if\n", " result.stderr != \"\"\n", " and \"illegal character\" not in result.stderr\n", " and \"parse error\" not in result.stderr\n", " and \"syntax error\" not in result.stderr]" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "Maybe a crash would be indicated by `bc` just crashing. Unfortunately, the return code is never nonzero:" ] }, { "cell_type": "code", "execution_count": 29, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:02.445654Z", "iopub.status.busy": "2024-01-18T17:14:02.445573Z", "iopub.status.idle": "2024-01-18T17:14:02.447649Z", "shell.execute_reply": "2024-01-18T17:14:02.447401Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "91" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sum(1 for (data, result) in runs if result.returncode != 0)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "How about we let the above `bc` test run for some more? While it is running, let us take a look on how the state of the art was in 1989." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Bugs Fuzzers Find\n", "\n", "When Miller and his students ran their first fuzzers in 1989, they found an alarming result: About **a third of the UNIX utilities** they fuzzed had issues – they crashed, hung, or otherwise failed when confronted with fuzzing input \\cite{Miller1990}. This also included the `bc` program, above. (The `bc` above is a [modern reimplementation](https://git.gavinhoward.com/gavin/bc) whose author is a [staunch believer in fuzzing](https://git.gavinhoward.com/gavin/bc/src/branch/master/tests/fuzzing)!)\n", "\n", "Considering that many of these UNIX utilities were used in scripts that would also process network input, this was an alarming result. Programmers quickly built and ran their own fuzzers, rushed to fix the reported errors, and learned not to trust external inputs anymore." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "What kind of problems did Miller's fuzzing experiment find? It turns out that the mistakes programmers made in 1990 are still the same mistakes being made today.\n" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "### Buffer Overflows\n", "\n", "Many programs have built-in maximum lengths for inputs and input elements. In languages like C, it is easy to excess these lengths without the program (or the programmer) even noticing, triggering so-called **buffer overflows**. The following code, for instance, happily copies the `input` string into a `weekday` string even if `input` has more than eight characters:\n", "```c\n", "char weekday[9]; // 8 characters + trailing '\\0' terminator\n", "strcpy (weekday, input);\n", "```\n", "Ironically, this already fails if `input` is `\"Wednesday\"` (9 characters); any excess characters (here, `'y'` and the following `'\\0'` string terminator) are simply copied to whatever resides in memory after `weekday`, triggering arbitrary behavior; maybe some boolean character variable which would be set from `'n'` to `'y'`. With fuzzing, it is very easy to produce arbitrary long inputs and input elements." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "We can easily simulate this buffer overflow behavior in a Python function:" ] }, { "cell_type": "code", "execution_count": 30, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:02.449344Z", "iopub.status.busy": "2024-01-18T17:14:02.449254Z", "iopub.status.idle": "2024-01-18T17:14:02.451051Z", "shell.execute_reply": "2024-01-18T17:14:02.450811Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def crash_if_too_long(s):\n", " buffer = \"Thursday\"\n", " if len(s) > len(buffer):\n", " raise ValueError" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "And yes, it quickly crashes." ] }, { "cell_type": "code", "execution_count": 31, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:02.452536Z", "iopub.status.busy": "2024-01-18T17:14:02.452460Z", "iopub.status.idle": "2024-01-18T17:14:02.453939Z", "shell.execute_reply": "2024-01-18T17:14:02.453688Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "from ExpectError import ExpectError" ] }, { "cell_type": "code", "execution_count": 32, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:02.455629Z", "iopub.status.busy": "2024-01-18T17:14:02.455530Z", "iopub.status.idle": "2024-01-18T17:14:02.457851Z", "shell.execute_reply": "2024-01-18T17:14:02.457524Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "Traceback (most recent call last):\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_72058/292568387.py\", line 5, in \n", " crash_if_too_long(s)\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_72058/2784561514.py\", line 4, in crash_if_too_long\n", " raise ValueError\n", "ValueError (expected)\n" ] } ], "source": [ "trials = 100\n", "with ExpectError():\n", " for i in range(trials):\n", " s = fuzzer()\n", " crash_if_too_long(s)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "source": [ "The `with ExpectError()` line in the above code ensures that the error message is printed, yet execution continues; this is to differentiate this \"expected\" error from \"unexpected\" errors in other code examples." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "### Missing Error Checks\n", "\n", "Many programming languages do not have exceptions, but instead have functions return special **error codes** in exceptional circumstances. The C function `getchar()`, for instance, normally returns a character from the standard input; if no input is available anymore, it returns the special value `EOF` (end of file). Now assume a programmer is scanning the input for the next character, reading in characters with `getchar()` until a space character is read:\n", "```c\n", "while (getchar() != ' ');\n", "```\n", "What happens if the input ends prematurely, as would perfectly be feasible with fuzzing? Well, `getchar()` returns `EOF`, and keeps on returning `EOF` when called again; so the code above simply enters an infinite loop." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Again, we can simulate such missing error checks. Here's a function that will effectively hang if no space is present in the input:" ] }, { "cell_type": "code", "execution_count": 33, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:02.459507Z", "iopub.status.busy": "2024-01-18T17:14:02.459416Z", "iopub.status.idle": "2024-01-18T17:14:02.461207Z", "shell.execute_reply": "2024-01-18T17:14:02.460953Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def hang_if_no_space(s):\n", " i = 0\n", " while True:\n", " if i < len(s):\n", " if s[i] == ' ':\n", " break\n", " i += 1" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Using the timeout mechanism from our [Introduction to Testing](Intro_Testing.ipynb), we can interrupt this function after some time. And yes, it does hang after a few fuzzing inputs." ] }, { "cell_type": "code", "execution_count": 34, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:02.462606Z", "iopub.status.busy": "2024-01-18T17:14:02.462526Z", "iopub.status.idle": "2024-01-18T17:14:02.464008Z", "shell.execute_reply": "2024-01-18T17:14:02.463771Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "from ExpectError import ExpectTimeout" ] }, { "cell_type": "code", "execution_count": 35, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:02.465423Z", "iopub.status.busy": "2024-01-18T17:14:02.465328Z", "iopub.status.idle": "2024-01-18T17:14:04.472371Z", "shell.execute_reply": "2024-01-18T17:14:04.472010Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "Traceback (most recent call last):\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_72058/3194687366.py\", line 5, in \n", " hang_if_no_space(s)\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_72058/3035466707.py\", line 3, in hang_if_no_space\n", " while True:\n", " File \"/Users/zeller/Projects/fuzzingbook/notebooks/Timeout.ipynb\", line 43, in timeout_handler\n", " raise TimeoutError()\n", "TimeoutError (expected)\n" ] } ], "source": [ "trials = 100\n", "with ExpectTimeout(2):\n", " for i in range(trials):\n", " s = fuzzer()\n", " hang_if_no_space(s)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "The `with ExpectTimeout()` line in the above code ensures that execution of the enclosed code is interrupted after two seconds, printing the error message." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "\n", "### Rogue Numbers\n", "\n", "With fuzzing, it is easy to generate **uncommon values** in the input, causing all kinds of interesting behavior. Consider the following code, again in the C language, which first reads a buffer size from the input, and then allocates a buffer of the given size:\n", "```c\n", "char *read_input() {\n", " size_t size = read_buffer_size();\n", " char *buffer = (char *)malloc(size);\n", " // fill buffer\n", " return (buffer);\n", "}\n", "```\n", "What happens if `size` is very large, exceeding program memory? What happens if `size` is less than the number of characters following? What happens if `size` is negative? By providing a random number here, fuzzing can create all kinds of damages.\n" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Again, we can easily simulate such rogue numbers in Python. The function `collapse_if_too_large()` fails if the passed value (a string) is too large after having been converted to an integer." ] }, { "cell_type": "code", "execution_count": 36, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:04.474308Z", "iopub.status.busy": "2024-01-18T17:14:04.474185Z", "iopub.status.idle": "2024-01-18T17:14:04.475967Z", "shell.execute_reply": "2024-01-18T17:14:04.475699Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def collapse_if_too_large(s):\n", " if int(s) > 1000:\n", " raise ValueError" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "We can have `fuzzer()` create a string of digits:" ] }, { "cell_type": "code", "execution_count": 37, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:04.477495Z", "iopub.status.busy": "2024-01-18T17:14:04.477385Z", "iopub.status.idle": "2024-01-18T17:14:04.479127Z", "shell.execute_reply": "2024-01-18T17:14:04.478863Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "7056414967099541967374507745748918952640135045\n" ] } ], "source": [ "long_number = fuzzer(100, ord('0'), 10)\n", "print(long_number)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "If we feed such numbers into `collapse_if_too_large()`, it will very soon fail." ] }, { "cell_type": "code", "execution_count": 38, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:04.480650Z", "iopub.status.busy": "2024-01-18T17:14:04.480551Z", "iopub.status.idle": "2024-01-18T17:14:04.482430Z", "shell.execute_reply": "2024-01-18T17:14:04.482193Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "Traceback (most recent call last):\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_72058/2775103647.py\", line 2, in \n", " collapse_if_too_large(long_number)\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_72058/1591744602.py\", line 3, in collapse_if_too_large\n", " raise ValueError\n", "ValueError (expected)\n" ] } ], "source": [ "with ExpectError():\n", " collapse_if_too_large(long_number)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "If we really wanted to allocate that much memory on a system, having it quickly fail as above actually would be the better option. In reality, running out of memory may dramatically slow systems down, up to the point that they become totally unresponsive – and restarting is the only option." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "One might argue that these are all problems of bad programming, or of bad programming languages. But then, there are thousands of people starting to program every day, and all of them make the same mistakes again and again, even today. " ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Catching Errors\n", "\n", "When Miller and his students built their first fuzzer, they could identify errors simply because the program would crash or hang – two conditions that are easy to identify. If the failures are more subtle, though, we need to come up with additional checks." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "### Generic Checkers\n", "\n", "Buffer overflows, as [discussed above](#Buffer-Overflows), are a particular instance of a more general problem: In languages like C and C++, a program can access arbitrary parts of its memory – even those parts that are uninitialized, already freed or simply not part of the data structure you are trying to access. This is necessary if you want to write an operating system, and great if you want a maximum of performance or control, but pretty bad if you want to avoid mistakes. Fortunately, there are tools that help catching such issues at runtime, and they are great when combined with fuzzing." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "#### Checking Memory Accesses\n", "\n", "To catch problematic memory accesses during testing, one can run C programs in special _memory-checking_ environments; at runtime, these check for each and every memory operation whether it accesses valid and initialized memory. A popular example is [LLVM Address Sanitizer](https://clang.llvm.org/docs/AddressSanitizer.html) which detects a whole set of potentially dangerous memory safety violations. In the following example we will compile a rather simple C program with this tool and provoke an out-of-bounds read by reading past an allocated portion of memory." ] }, { "cell_type": "code", "execution_count": 39, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:04.484030Z", "iopub.status.busy": "2024-01-18T17:14:04.483925Z", "iopub.status.idle": "2024-01-18T17:14:04.485983Z", "shell.execute_reply": "2024-01-18T17:14:04.485736Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "with open(\"program.c\", \"w\") as f:\n", " f.write(\"\"\"\n", "#include \n", "#include \n", "\n", "int main(int argc, char** argv) {\n", " /* Create an array with 100 bytes, initialized with 42 */\n", " char *buf = malloc(100);\n", " memset(buf, 42, 100);\n", "\n", " /* Read the N-th element, with N being the first command-line argument */\n", " int index = atoi(argv[1]);\n", " char val = buf[index];\n", "\n", " /* Clean up memory so we don't leak */\n", " free(buf);\n", " return val;\n", "}\n", " \"\"\")" ] }, { "cell_type": "code", "execution_count": 40, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:14:04.487500Z", "iopub.status.busy": "2024-01-18T17:14:04.487398Z", "iopub.status.idle": "2024-01-18T17:14:04.488966Z", "shell.execute_reply": "2024-01-18T17:14:04.488702Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from bookutils import print_file" ] }, { "cell_type": "code", "execution_count": 41, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:04.490514Z", "iopub.status.busy": "2024-01-18T17:14:04.490413Z", "iopub.status.idle": "2024-01-18T17:14:04.545004Z", "shell.execute_reply": "2024-01-18T17:14:04.544733Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\u001b[36m#\u001b[39;49;00m\u001b[36minclude\u001b[39;49;00m\u001b[37m \u001b[39;49;00m\u001b[37m\u001b[39;49;00m\u001b[36m\u001b[39;49;00m\n", "\u001b[36m#\u001b[39;49;00m\u001b[36minclude\u001b[39;49;00m\u001b[37m \u001b[39;49;00m\u001b[37m\u001b[39;49;00m\u001b[36m\u001b[39;49;00m\n", "\u001b[37m\u001b[39;49;00m\n", "\u001b[36mint\u001b[39;49;00m\u001b[37m \u001b[39;49;00m\u001b[32mmain\u001b[39;49;00m(\u001b[36mint\u001b[39;49;00m\u001b[37m \u001b[39;49;00margc,\u001b[37m \u001b[39;49;00m\u001b[36mchar\u001b[39;49;00m**\u001b[37m \u001b[39;49;00margv)\u001b[37m \u001b[39;49;00m{\u001b[37m\u001b[39;49;00m\n", "\u001b[37m \u001b[39;49;00m\u001b[37m/* Create an array with 100 bytes, initialized with 42 */\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n", "\u001b[37m \u001b[39;49;00m\u001b[36mchar\u001b[39;49;00m\u001b[37m \u001b[39;49;00m*buf\u001b[37m \u001b[39;49;00m=\u001b[37m \u001b[39;49;00mmalloc(\u001b[34m100\u001b[39;49;00m);\u001b[37m\u001b[39;49;00m\n", "\u001b[37m \u001b[39;49;00mmemset(buf,\u001b[37m \u001b[39;49;00m\u001b[34m42\u001b[39;49;00m,\u001b[37m \u001b[39;49;00m\u001b[34m100\u001b[39;49;00m);\u001b[37m\u001b[39;49;00m\n", "\u001b[37m\u001b[39;49;00m\n", "\u001b[37m \u001b[39;49;00m\u001b[37m/* Read the N-th element, with N being the first command-line argument */\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n", "\u001b[37m \u001b[39;49;00m\u001b[36mint\u001b[39;49;00m\u001b[37m \u001b[39;49;00mindex\u001b[37m \u001b[39;49;00m=\u001b[37m \u001b[39;49;00matoi(argv[\u001b[34m1\u001b[39;49;00m]);\u001b[37m\u001b[39;49;00m\n", "\u001b[37m \u001b[39;49;00m\u001b[36mchar\u001b[39;49;00m\u001b[37m \u001b[39;49;00mval\u001b[37m \u001b[39;49;00m=\u001b[37m \u001b[39;49;00mbuf[index];\u001b[37m\u001b[39;49;00m\n", "\u001b[37m\u001b[39;49;00m\n", "\u001b[37m \u001b[39;49;00m\u001b[37m/* Clean up memory so we don't leak */\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n", "\u001b[37m \u001b[39;49;00mfree(buf);\u001b[37m\u001b[39;49;00m\n", "\u001b[37m \u001b[39;49;00m\u001b[34mreturn\u001b[39;49;00m\u001b[37m \u001b[39;49;00mval;\u001b[37m\u001b[39;49;00m\n", "}\u001b[37m\u001b[39;49;00m\n", "\u001b[37m \u001b[39;49;00m\u001b[37m\u001b[39;49;00m" ] } ], "source": [ "print_file(\"program.c\")" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "We compile this C program with address sanitization enabled:" ] }, { "cell_type": "code", "execution_count": 42, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:04.546586Z", "iopub.status.busy": "2024-01-18T17:14:04.546485Z", "iopub.status.idle": "2024-01-18T17:14:04.760062Z", "shell.execute_reply": "2024-01-18T17:14:04.759329Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "!clang -fsanitize=address -g -o program program.c" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "If we run the program with an argument of `99`, it returns `buf[99]`, which is 42." ] }, { "cell_type": "code", "execution_count": 43, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:04.763377Z", "iopub.status.busy": "2024-01-18T17:14:04.762975Z", "iopub.status.idle": "2024-01-18T17:14:05.270394Z", "shell.execute_reply": "2024-01-18T17:14:05.269799Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "42\r\n" ] } ], "source": [ "!./program 99; echo $?" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Accessing `buf[110]`, however, results in an out-of-bounds error in AddressSanitizer." ] }, { "cell_type": "code", "execution_count": 44, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:05.273658Z", "iopub.status.busy": "2024-01-18T17:14:05.273412Z", "iopub.status.idle": "2024-01-18T17:14:05.759802Z", "shell.execute_reply": "2024-01-18T17:14:05.759414Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "=================================================================\r\n", "\u001b[1m\u001b[31m==72172==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x000104202a9e at pc 0x0001041abe84 bp 0x00016bc56680 sp 0x00016bc56678\r\n", "\u001b[1m\u001b[0m\u001b[1m\u001b[34mREAD of size 1 at 0x000104202a9e thread T0\u001b[1m\u001b[0m\r\n", " #0 0x1041abe80 in main program.c:12\r\n", " #1 0x181c310dc ()\r\n", "\r\n", "\u001b[1m\u001b[32m0x000104202a9e is located 10 bytes after 100-byte region [0x000104202a30,0x000104202a94)\r\n", "\u001b[1m\u001b[0m\u001b[1m\u001b[35mallocated by thread T0 here:\u001b[1m\u001b[0m\r\n", " #0 0x104a57244 in wrap_malloc+0x94 (libclang_rt.asan_osx_dynamic.dylib:arm64e+0x53244)\r\n", " #1 0x1041abdc8 in main program.c:7\r\n", " #2 0x181c310dc ()\r\n", "\r\n", "SUMMARY: AddressSanitizer: heap-buffer-overflow program.c:12 in main\r\n", "Shadow bytes around the buggy address:\r\n", " 0x000104202800: \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m\r\n", " 0x000104202880: \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m\r\n", " 0x000104202900: \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m\r\n", " 0x000104202980: \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m\r\n", " 0x000104202a00: \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[0m00\u001b[1m\u001b[0m \u001b[1m\u001b[0m00\u001b[1m\u001b[0m \u001b[1m\u001b[0m00\u001b[1m\u001b[0m \u001b[1m\u001b[0m00\u001b[1m\u001b[0m \u001b[1m\u001b[0m00\u001b[1m\u001b[0m \u001b[1m\u001b[0m00\u001b[1m\u001b[0m \u001b[1m\u001b[0m00\u001b[1m\u001b[0m \u001b[1m\u001b[0m00\u001b[1m\u001b[0m \u001b[1m\u001b[0m00\u001b[1m\u001b[0m \u001b[1m\u001b[0m00\u001b[1m\u001b[0m\r\n", "=>0x000104202a80: \u001b[1m\u001b[0m00\u001b[1m\u001b[0m \u001b[1m\u001b[0m00\u001b[1m\u001b[0m \u001b[1m\u001b[0m04\u001b[1m\u001b[0m[\u001b[1m\u001b[31mfa\u001b[1m\u001b[0m]\u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m\r\n", " 0x000104202b00: \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m\r\n", " 0x000104202b80: \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m\r\n", " 0x000104202c00: \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m\r\n", " 0x000104202c80: \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m\r\n", " 0x000104202d00: \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m\r\n", "Shadow byte legend (one shadow byte represents 8 application bytes):\r\n", " Addressable: \u001b[1m\u001b[0m00\u001b[1m\u001b[0m\r\n", " Partially addressable: \u001b[1m\u001b[0m01\u001b[1m\u001b[0m \u001b[1m\u001b[0m02\u001b[1m\u001b[0m \u001b[1m\u001b[0m03\u001b[1m\u001b[0m \u001b[1m\u001b[0m04\u001b[1m\u001b[0m \u001b[1m\u001b[0m05\u001b[1m\u001b[0m \u001b[1m\u001b[0m06\u001b[1m\u001b[0m \u001b[1m\u001b[0m07\u001b[1m\u001b[0m \r\n", " Heap left redzone: \u001b[1m\u001b[31mfa\u001b[1m\u001b[0m\r\n", " Freed heap region: \u001b[1m\u001b[35mfd\u001b[1m\u001b[0m\r\n", " Stack left redzone: \u001b[1m\u001b[31mf1\u001b[1m\u001b[0m\r\n", " Stack mid redzone: \u001b[1m\u001b[31mf2\u001b[1m\u001b[0m\r\n", " Stack right redzone: \u001b[1m\u001b[31mf3\u001b[1m\u001b[0m\r\n", " Stack after return: \u001b[1m\u001b[35mf5\u001b[1m\u001b[0m\r\n", " Stack use after scope: \u001b[1m\u001b[35mf8\u001b[1m\u001b[0m\r\n", " Global redzone: \u001b[1m\u001b[31mf9\u001b[1m\u001b[0m\r\n", " Global init order: \u001b[1m\u001b[36mf6\u001b[1m\u001b[0m\r\n", " Poisoned by user: \u001b[1m\u001b[34mf7\u001b[1m\u001b[0m\r\n", " Container overflow: \u001b[1m\u001b[34mfc\u001b[1m\u001b[0m\r\n", " Array cookie: \u001b[1m\u001b[31mac\u001b[1m\u001b[0m\r\n", " Intra object redzone: \u001b[1m\u001b[33mbb\u001b[1m\u001b[0m\r\n", " ASan internal: \u001b[1m\u001b[33mfe\u001b[1m\u001b[0m\r\n", " Left alloca redzone: \u001b[1m\u001b[34mca\u001b[1m\u001b[0m\r\n", " Right alloca redzone: \u001b[1m\u001b[34mcb\u001b[1m\u001b[0m\r\n", "==72172==ABORTING\r\n" ] } ], "source": [ "!./program 110" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "If you want to find errors in a C program, turning on such checks for fuzzing is fairly easy. It will slow down execution by a certain factor depending on the tool (for AddressSanitizer it is typically 2$\\times$) and also consume more memory, but CPU cycles are dead cheap compared to the human effort it takes to find these bugs." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Out-of-bounds accesses to memory are a great security risk, as they may let attackers access or even modify information that is not meant for them. As a famous example, the [HeartBleed bug](https://en.wikipedia.org/wiki/Heartbleed) was a security bug in the OpenSSL library, implementing cryptographic protocols that provide communications security over a computer network. (If you read this text in a browser, it is likely encrypted using these protocols.)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "The HeartBleed bug was exploited by sending a specially crafted command to the SSL *heartbeat* service. A heartbeat service is used to check if the server on the other end is still alive. A client would send the service a string like\n", "\n", "```\n", "BIRD (4 letters)\n", "```\n", "\n", "to which the server would reply with `BIRD`, and the client would know the server is alive." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "Unfortunately, this service could be exploited by asking the server to reply with _more_ than the requested set of letters. This is very well explained in this [XKCD comic](https://xkcd.com/1354/):" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "![XKCD Comic](PICS/xkcd_heartbleed_1.png)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "![XKCD Comic](PICS/xkcd_heartbleed_2.png)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "![XKCD Comic](PICS/xkcd_heartbleed_3.png)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "In the OpenSSL implementation, these memory contents could involve cryptographic certificates, private keys, and more – and worse, no one would notice that this memory just had been accessed. When the HeartBleed bug was discovered, it had been around for many years, and none would know whether and which secrets had already leaked; the quickly set up [HeartBleed announcement page](http://heartbleed.com/) said it all." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "But how was HeartBleed discovered? Very simple. Researchers both at the Codenomicon company as well as with Google compiled the OpenSSL library with a memory sanitizer, and then happily flooded it with fuzzed commands. The memory sanitizer would then notice whether an out-of-bounds memory access had occurred – and actually, it would very quickly discover this." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "A memory checker is just one of many checkers one can run to detect runtime errors during fuzzing. In the [chapter on mining function specifications](DynamicInvariants.ipynb), we will learn more about how to define generic checkers." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "source": [ "We're done with `program`, so we clean up:" ] }, { "cell_type": "code", "execution_count": 45, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:05.762107Z", "iopub.status.busy": "2024-01-18T17:14:05.761950Z", "iopub.status.idle": "2024-01-18T17:14:05.882322Z", "shell.execute_reply": "2024-01-18T17:14:05.881891Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "!rm -fr program program.*" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "#### Information Leaks\n", "\n", "Information leaks may not only occur through illegal memory accesses; they can also occur within \"valid\" memory – if this \"valid\" memory contains sensitive information that should not leak out. Let us illustrate this issue in a Python program. To start with, let us create some program memory filled with actual data and random data:" ] }, { "cell_type": "code", "execution_count": 46, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:05.884379Z", "iopub.status.busy": "2024-01-18T17:14:05.884252Z", "iopub.status.idle": "2024-01-18T17:14:05.886409Z", "shell.execute_reply": "2024-01-18T17:14:05.885997Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "secrets = (\"\" + fuzzer(100) +\n", " \"\" + fuzzer(100) +\n", " \"\" + fuzzer(100) + \"\")" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "We add more \"memory\" characters to `secrets`, filled with `\"deadbeef\"` as marker for uninitialized memory:" ] }, { "cell_type": "code", "execution_count": 47, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:05.888176Z", "iopub.status.busy": "2024-01-18T17:14:05.888036Z", "iopub.status.idle": "2024-01-18T17:14:05.890264Z", "shell.execute_reply": "2024-01-18T17:14:05.889888Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "uninitialized_memory_marker = \"deadbeef\"\n", "while len(secrets) < 2048:\n", " secrets += uninitialized_memory_marker" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "We define a service (similar to the heartbeat service discussed above) that would take a reply to be sent back, as well as a length. It would store the reply to be sent in memory, and then send it back with the given length." ] }, { "cell_type": "code", "execution_count": 48, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:05.891943Z", "iopub.status.busy": "2024-01-18T17:14:05.891823Z", "iopub.status.idle": "2024-01-18T17:14:05.894034Z", "shell.execute_reply": "2024-01-18T17:14:05.893738Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def heartbeat(reply: str, length: int, memory: str) -> str:\n", " # Store reply in memory\n", " memory = reply + memory[len(reply):]\n", "\n", " # Send back heartbeat\n", " s = \"\"\n", " for i in range(length):\n", " s += memory[i]\n", " return s" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "This perfectly works for standard strings:" ] }, { "cell_type": "code", "execution_count": 49, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:05.895588Z", "iopub.status.busy": "2024-01-18T17:14:05.895468Z", "iopub.status.idle": "2024-01-18T17:14:05.897763Z", "shell.execute_reply": "2024-01-18T17:14:05.897503Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "'potato'" ] }, "execution_count": 49, "metadata": {}, "output_type": "execute_result" } ], "source": [ "heartbeat(\"potato\", 6, memory=secrets)" ] }, { "cell_type": "code", "execution_count": 50, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:05.899185Z", "iopub.status.busy": "2024-01-18T17:14:05.899084Z", "iopub.status.idle": "2024-01-18T17:14:05.901220Z", "shell.execute_reply": "2024-01-18T17:14:05.900979Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "'bird'" ] }, "execution_count": 50, "metadata": {}, "output_type": "execute_result" } ], "source": [ "heartbeat(\"bird\", 4, memory=secrets)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "However, if the length is greater than the length of the reply string, additional contents of memory spill out. Note that all of this still occurs within regular array bounds, so an address sanitizer would not be triggered:" ] }, { "cell_type": "code", "execution_count": 51, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:05.902736Z", "iopub.status.busy": "2024-01-18T17:14:05.902636Z", "iopub.status.idle": "2024-01-18T17:14:05.904739Z", "shell.execute_reply": "2024-01-18T17:14:05.904472Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "'hatace for reply>#,,!3?30>#61)$4--8=<7)4 )03/%,5+! \"4)0?.9+?3();<42?=?07(+/+((1)#/0\\'4!>/<#=78%6$!!$<-\"3\"\\'-?1?85!05629%/); *)1\\'/=9%.(#.4%deadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadb'" ] }, "execution_count": 51, "metadata": {}, "output_type": "execute_result" } ], "source": [ "heartbeat(\"hat\", 500, memory=secrets)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "How can one detect such issues? The idea is to identify information that should not leak out, such as the given secrets, but also uninitialized memory. We can simulate such a check in a small Python example:" ] }, { "cell_type": "code", "execution_count": 52, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:05.906325Z", "iopub.status.busy": "2024-01-18T17:14:05.906214Z", "iopub.status.idle": "2024-01-18T17:14:05.907884Z", "shell.execute_reply": "2024-01-18T17:14:05.907633Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from ExpectError import ExpectError" ] }, { "cell_type": "code", "execution_count": 53, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:05.909623Z", "iopub.status.busy": "2024-01-18T17:14:05.909508Z", "iopub.status.idle": "2024-01-18T17:14:05.911751Z", "shell.execute_reply": "2024-01-18T17:14:05.911522Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "Traceback (most recent call last):\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_72058/4040656327.py\", line 4, in \n", " assert not s.find(uninitialized_memory_marker)\n", "AssertionError (expected)\n" ] } ], "source": [ "with ExpectError():\n", " for i in range(10):\n", " s = heartbeat(fuzzer(), random.randint(1, 500), memory=secrets)\n", " assert not s.find(uninitialized_memory_marker)\n", " assert not s.find(\"secret\")" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "With such a check, we find that secrets and/or uninitialized memory indeed leak out. In the [chapter on information flow](InformationFlow.ipynb), we will discuss how to do this automatically, \"tainting\" sensitive information and values derived from them, and ensuring that \"tainted\" values do not leak out." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "As a rule of thumb, you should always _enable as many automatic checkers as possible_ during fuzzing. CPU cycles are cheap, and errors are expensive. If you only execute the program without an option to actually detect errors, you will be missing several opportunities." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "### Program-Specific Checkers\n", "\n", "Besides generic checkers that apply to _all_ programs on a given platform or in a given language, you can also devise _specific_ checkers that apply to your program, or a subsystem. In the [chapter on testing](Intro_Testing.ipynb), we already have hinted at techniques of [runtime verification](Intro_Testing.ipynb#Runtime-Verification) that check function results at runtime for correctness." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "One key idea for detecting errors early is the concept of *assertion* – a predicate that checks the input (precondition) and the result (postcondition) of important functions. The more assertions you have in your program, the higher your chances to detect errors during execution that would go undetected by generic checkers – notably during fuzzing. If you worry about the impact of assertions on performance, keep in mind that assertions can be turned off in production code (although it can be helpful to leave the most critical checks active)." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "One of the most important uses of assertions for finding errors is _checking the integrity of complex data structures._ Let us illustrate the concept using a simple example. Suppose we have a mapping of airport codes to airports, as in" ] }, { "cell_type": "code", "execution_count": 54, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:05.913448Z", "iopub.status.busy": "2024-01-18T17:14:05.913338Z", "iopub.status.idle": "2024-01-18T17:14:05.915167Z", "shell.execute_reply": "2024-01-18T17:14:05.914918Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "airport_codes: Dict[str, str] = {\n", " \"YVR\": \"Vancouver\",\n", " \"JFK\": \"New York-JFK\",\n", " \"CDG\": \"Paris-Charles de Gaulle\",\n", " \"CAI\": \"Cairo\",\n", " \"LED\": \"St. Petersburg\",\n", " \"PEK\": \"Beijing\",\n", " \"HND\": \"Tokyo-Haneda\",\n", " \"AKL\": \"Auckland\"\n", "} # plus many more" ] }, { "cell_type": "code", "execution_count": 55, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:05.916542Z", "iopub.status.busy": "2024-01-18T17:14:05.916443Z", "iopub.status.idle": "2024-01-18T17:14:05.918645Z", "shell.execute_reply": "2024-01-18T17:14:05.918317Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "'Vancouver'" ] }, "execution_count": 55, "metadata": {}, "output_type": "execute_result" } ], "source": [ "airport_codes[\"YVR\"]" ] }, { "cell_type": "code", "execution_count": 56, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:05.920320Z", "iopub.status.busy": "2024-01-18T17:14:05.920213Z", "iopub.status.idle": "2024-01-18T17:14:05.922391Z", "shell.execute_reply": "2024-01-18T17:14:05.922119Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 56, "metadata": {}, "output_type": "execute_result" } ], "source": [ "\"AKL\" in airport_codes" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "This list of airport codes may be pretty critical: if we have a spelling mistake in any of the airport codes, this may impact whatever application we have. We therefore introduce a function that checks the list for consistency. The consistency condition is called a *representation invariant*, and functions (or methods) that check it are therefore typically named `repOK()` for \"the representation is ok\"." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "First, let's have a checker for individual airport codes. The checker fails if the code is inconsistent." ] }, { "cell_type": "code", "execution_count": 57, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:05.923937Z", "iopub.status.busy": "2024-01-18T17:14:05.923832Z", "iopub.status.idle": "2024-01-18T17:14:05.925870Z", "shell.execute_reply": "2024-01-18T17:14:05.925627Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def code_repOK(code: str) -> bool:\n", " assert len(code) == 3, \"Airport code must have three characters: \" + repr(code)\n", " for c in code:\n", " assert c.isalpha(), \"Non-letter in airport code: \" + repr(code)\n", " assert c.isupper(), \"Lowercase letter in airport code: \" + repr(code)\n", " return True" ] }, { "cell_type": "code", "execution_count": 58, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:05.927466Z", "iopub.status.busy": "2024-01-18T17:14:05.927359Z", "iopub.status.idle": "2024-01-18T17:14:05.929205Z", "shell.execute_reply": "2024-01-18T17:14:05.928952Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "assert code_repOK(\"SEA\")" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "We can now use `code_repOK()` to check all elements in the list:" ] }, { "cell_type": "code", "execution_count": 59, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:05.930907Z", "iopub.status.busy": "2024-01-18T17:14:05.930775Z", "iopub.status.idle": "2024-01-18T17:14:05.932643Z", "shell.execute_reply": "2024-01-18T17:14:05.932389Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def airport_codes_repOK():\n", " for code in airport_codes:\n", " assert code_repOK(code)\n", " return True" ] }, { "cell_type": "code", "execution_count": 60, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:05.934524Z", "iopub.status.busy": "2024-01-18T17:14:05.934391Z", "iopub.status.idle": "2024-01-18T17:14:05.936269Z", "shell.execute_reply": "2024-01-18T17:14:05.935917Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "with ExpectError():\n", " assert airport_codes_repOK()" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "If we add an invalid element to the list, our check would fail:" ] }, { "cell_type": "code", "execution_count": 61, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:05.938325Z", "iopub.status.busy": "2024-01-18T17:14:05.938183Z", "iopub.status.idle": "2024-01-18T17:14:05.940301Z", "shell.execute_reply": "2024-01-18T17:14:05.939927Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "airport_codes[\"YMML\"] = \"Melbourne\"" ] }, { "cell_type": "code", "execution_count": 62, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:05.942490Z", "iopub.status.busy": "2024-01-18T17:14:05.942340Z", "iopub.status.idle": "2024-01-18T17:14:05.945802Z", "shell.execute_reply": "2024-01-18T17:14:05.945222Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "Traceback (most recent call last):\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_72058/2308942452.py\", line 2, in \n", " assert airport_codes_repOK()\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_72058/480627665.py\", line 3, in airport_codes_repOK\n", " assert code_repOK(code)\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_72058/865020192.py\", line 2, in code_repOK\n", " assert len(code) == 3, \"Airport code must have three characters: \" + repr(code)\n", "AssertionError: Airport code must have three characters: 'YMML' (expected)\n" ] } ], "source": [ "with ExpectError():\n", " assert airport_codes_repOK()" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Of course, rather than manipulating the list directly, we'd have a special function for adding elements; this could then also check whether the code is valid:" ] }, { "cell_type": "code", "execution_count": 63, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:05.948275Z", "iopub.status.busy": "2024-01-18T17:14:05.948123Z", "iopub.status.idle": "2024-01-18T17:14:05.961390Z", "shell.execute_reply": "2024-01-18T17:14:05.958918Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def add_new_airport(code: str, city: str) -> None:\n", " assert code_repOK(code)\n", " airport_codes[code] = city" ] }, { "cell_type": "code", "execution_count": 64, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:05.964673Z", "iopub.status.busy": "2024-01-18T17:14:05.964519Z", "iopub.status.idle": "2024-01-18T17:14:05.966464Z", "shell.execute_reply": "2024-01-18T17:14:05.966173Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "with ExpectError(): # For BER, ExpectTimeout would be more appropriate\n", " add_new_airport(\"BER\", \"Berlin\")" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "This check also allows us to find out errors in argument lists:" ] }, { "cell_type": "code", "execution_count": 65, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:05.968326Z", "iopub.status.busy": "2024-01-18T17:14:05.968195Z", "iopub.status.idle": "2024-01-18T17:14:05.970613Z", "shell.execute_reply": "2024-01-18T17:14:05.970341Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "Traceback (most recent call last):\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_72058/1427835309.py\", line 2, in \n", " add_new_airport(\"London-Heathrow\", \"LHR\")\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_72058/2655039924.py\", line 2, in add_new_airport\n", " assert code_repOK(code)\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_72058/865020192.py\", line 2, in code_repOK\n", " assert len(code) == 3, \"Airport code must have three characters: \" + repr(code)\n", "AssertionError: Airport code must have three characters: 'London-Heathrow' (expected)\n" ] } ], "source": [ "with ExpectError():\n", " add_new_airport(\"London-Heathrow\", \"LHR\")" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "For maximum checking, though, the `add_new_airport()` function would also ensure the correct representation of the list of airport codes – _before_ and _after_ changing it." ] }, { "cell_type": "code", "execution_count": 66, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:05.972399Z", "iopub.status.busy": "2024-01-18T17:14:05.972274Z", "iopub.status.idle": "2024-01-18T17:14:05.974280Z", "shell.execute_reply": "2024-01-18T17:14:05.973986Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def add_new_airport_2(code: str, city: str) -> None:\n", " assert code_repOK(code)\n", " assert airport_codes_repOK()\n", " airport_codes[code] = city\n", " assert airport_codes_repOK()" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "This catches the inconsistency introduced earlier:" ] }, { "cell_type": "code", "execution_count": 67, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:05.978184Z", "iopub.status.busy": "2024-01-18T17:14:05.978027Z", "iopub.status.idle": "2024-01-18T17:14:05.981030Z", "shell.execute_reply": "2024-01-18T17:14:05.980726Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "Traceback (most recent call last):\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_72058/4151824846.py\", line 2, in \n", " add_new_airport_2(\"IST\", \"Istanbul Yeni Havalimanı\")\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_72058/2099116665.py\", line 3, in add_new_airport_2\n", " assert airport_codes_repOK()\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_72058/480627665.py\", line 3, in airport_codes_repOK\n", " assert code_repOK(code)\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_72058/865020192.py\", line 2, in code_repOK\n", " assert len(code) == 3, \"Airport code must have three characters: \" + repr(code)\n", "AssertionError: Airport code must have three characters: 'YMML' (expected)\n" ] } ], "source": [ "with ExpectError():\n", " add_new_airport_2(\"IST\", \"Istanbul Yeni Havalimanı\")" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "The more `repOK()` assertions exist in your code, the more errors you will catch – even those specific to only your domain and problem. On top, such assertions document the _assumptions you made_ during programming and thus help other programmers to understand your code and prevent errors." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "As a final example, let us consider a rather complex data structure – a [red-black tree](https://en.wikipedia.org/wiki/Red-black_tree), a self-balancing binary search tree. Implementing a red-black tree is not too hard, but getting it correct can be a task of several hours even for experienced programmers. A `repOK()` method, however, documents all the assumptions and checks them as well:" ] }, { "cell_type": "code", "execution_count": 68, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:05.982671Z", "iopub.status.busy": "2024-01-18T17:14:05.982554Z", "iopub.status.idle": "2024-01-18T17:14:05.986332Z", "shell.execute_reply": "2024-01-18T17:14:05.985992Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class RedBlackTree:\n", " def repOK(self):\n", " assert self.rootHasNoParent()\n", " assert self.rootIsBlack()\n", " assert self.rootNodesHaveOnlyBlackChildren()\n", " assert self.treeIsAcyclic()\n", " assert self.parentsAreConsistent()\n", " return True\n", "\n", " def rootIsBlack(self):\n", " if self.parent is None:\n", " assert self.color == BLACK\n", " return True\n", "\n", " def add_element(self, elem):\n", " assert self.repOK()\n", " ... # Add the element\n", " assert self.repOK()\n", "\n", " def delete_element(self, elem):\n", " assert self.repOK()\n", " ... # Delete the element\n", " assert self.repOK()" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Here, `repOK()` is a method that runs on an object of the `RedBlackTree` class. It runs five different checks, all of which have their own assertions. Whenever an element is added or deleted, all these consistency checks are run automatically. If you have an error in any of these, the checkers will find them – if you run the tree through sufficiently many fuzzed inputs, of course." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "### Static Code Checkers\n", "\n", "Many of the benefits from `repOK()` assertions can also be obtained by using _static type checkers_ on your code. In Python, for instance, the [MyPy](http://mypy-lang.org) static checker can find type errors as soon as types of arguments are properly declared:" ] }, { "cell_type": "code", "execution_count": 69, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:05.988119Z", "iopub.status.busy": "2024-01-18T17:14:05.988003Z", "iopub.status.idle": "2024-01-18T17:14:05.989735Z", "shell.execute_reply": "2024-01-18T17:14:05.989467Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "typed_airport_codes: Dict[str, str] = {\n", " \"YVR\": \"Vancouver\", # etc\n", "}" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "If we now add a key with a non-string type, as in" ] }, { "cell_type": "code", "execution_count": 70, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:05.993094Z", "iopub.status.busy": "2024-01-18T17:14:05.992855Z", "iopub.status.idle": "2024-01-18T17:14:05.994782Z", "shell.execute_reply": "2024-01-18T17:14:05.994494Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "typed_airport_codes[1] = \"First\" # type: ignore" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "this would be caught by MyPy immediately:\n", "```sh\n", "$ mypy airports.py\n", "airports.py: error: Invalid index type \"int\" for \"Dict[str, str]\"; expected type \"str\"\n", "```" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Statically checking more advanced properties such as the airport code consisting of exactly three uppercase characters or a tree being acyclic, however, quickly reach the limits of static checking. Your `repOK()` assertions will still be needed – best in conjunction with a good test generator." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## A Fuzzing Architecture\n", "\n", "Since we'd like to reuse some parts of this chapter in the following ones, let us define things in a way that are easier to reuse, and in particular easier to _extend_. To this end, we introduce a number of _classes_ that encapsulate the functionality above in a reusable way. " ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" }, "tags": [] }, "source": [ "### Runner Classes\n", "\n", "The first thing we introduce is the notion of a `Runner` – that is, an object whose job it is to execute some object with a given input. A runner typically is some program or function under test, but we can also have simpler runners.\n", "\n", "Let us start with a base class for runners. A runner essentially provides a method `run(input)` that is used to pass `input` (a string) to the runner. `run()` returns a pair (`result`, `outcome`). Here, `result` is a runner-specific value that gives details on the run; `outcome` is a value that classifies the result in three categories:\n", "\n", "* `Runner.PASS` – the test _passed_. The run produced correct results.\n", "* `Runner.FAIL` – the test _failed_. The run produced incorrect results.\n", "* `Runner.UNRESOLVED` – the test neither passed nor failed. This happens if the run could not take place – for instance, because the input was invalid." ] }, { "cell_type": "code", "execution_count": 71, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:14:05.997312Z", "iopub.status.busy": "2024-01-18T17:14:05.997102Z", "iopub.status.idle": "2024-01-18T17:14:05.999279Z", "shell.execute_reply": "2024-01-18T17:14:05.998922Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "Outcome = str" ] }, { "cell_type": "code", "execution_count": 72, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:06.001060Z", "iopub.status.busy": "2024-01-18T17:14:06.000846Z", "iopub.status.idle": "2024-01-18T17:14:06.003306Z", "shell.execute_reply": "2024-01-18T17:14:06.003011Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "class Runner:\n", " \"\"\"Base class for testing inputs.\"\"\"\n", "\n", " # Test outcomes\n", " PASS = \"PASS\"\n", " FAIL = \"FAIL\"\n", " UNRESOLVED = \"UNRESOLVED\"\n", "\n", " def __init__(self) -> None:\n", " \"\"\"Initialize\"\"\"\n", " pass\n", "\n", " def run(self, inp: str) -> Any:\n", " \"\"\"Run the runner with the given input\"\"\"\n", " return (inp, Runner.UNRESOLVED)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "As a base class, `Runner` merely provides an interface for more complex runners that build on it. More specifically, we introduce *subclasses* that *inherit* the methods from their superclass in order to add additional methods or to override inherited methods.\n", "\n", "Here is one example of such a subclass: `PrintRunner` simply prints out everything that is given to it, overriding the inherited `run()` method. This is the default runner in many situations." ] }, { "cell_type": "code", "execution_count": 73, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:06.005621Z", "iopub.status.busy": "2024-01-18T17:14:06.005425Z", "iopub.status.idle": "2024-01-18T17:14:06.008247Z", "shell.execute_reply": "2024-01-18T17:14:06.007633Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "class PrintRunner(Runner):\n", " \"\"\"Simple runner, printing the input.\"\"\"\n", "\n", " def run(self, inp) -> Any:\n", " \"\"\"Print the given input\"\"\"\n", " print(inp)\n", " return (inp, Runner.UNRESOLVED)" ] }, { "cell_type": "code", "execution_count": 74, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:06.010305Z", "iopub.status.busy": "2024-01-18T17:14:06.010117Z", "iopub.status.idle": "2024-01-18T17:14:06.012902Z", "shell.execute_reply": "2024-01-18T17:14:06.012496Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Some input\n" ] } ], "source": [ "p = PrintRunner()\n", "(result, outcome) = p.run(\"Some input\")" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "The result is just the string we passed as input:" ] }, { "cell_type": "code", "execution_count": 75, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:06.014793Z", "iopub.status.busy": "2024-01-18T17:14:06.014678Z", "iopub.status.idle": "2024-01-18T17:14:06.017061Z", "shell.execute_reply": "2024-01-18T17:14:06.016637Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "'Some input'" ] }, "execution_count": 75, "metadata": {}, "output_type": "execute_result" } ], "source": [ "result" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "Still, at this point, we have no way to classify program behavior:" ] }, { "cell_type": "code", "execution_count": 76, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:06.018713Z", "iopub.status.busy": "2024-01-18T17:14:06.018589Z", "iopub.status.idle": "2024-01-18T17:14:06.020655Z", "shell.execute_reply": "2024-01-18T17:14:06.020394Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "'UNRESOLVED'" ] }, "execution_count": 76, "metadata": {}, "output_type": "execute_result" } ], "source": [ "outcome" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "The `ProgramRunner` class sends the input to the standard input of a program instead. The program is specified when creating a `ProgramRunner` object." ] }, { "cell_type": "code", "execution_count": 77, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:06.022407Z", "iopub.status.busy": "2024-01-18T17:14:06.022268Z", "iopub.status.idle": "2024-01-18T17:14:06.025549Z", "shell.execute_reply": "2024-01-18T17:14:06.025219Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "class ProgramRunner(Runner):\n", " \"\"\"Test a program with inputs.\"\"\"\n", "\n", " def __init__(self, program: Union[str, List[str]]) -> None:\n", " \"\"\"Initialize.\n", " `program` is a program spec as passed to `subprocess.run()`\"\"\"\n", " self.program = program\n", "\n", " def run_process(self, inp: str = \"\") -> subprocess.CompletedProcess:\n", " \"\"\"Run the program with `inp` as input.\n", " Return result of `subprocess.run()`.\"\"\"\n", " return subprocess.run(self.program,\n", " input=inp,\n", " stdout=subprocess.PIPE,\n", " stderr=subprocess.PIPE,\n", " universal_newlines=True)\n", "\n", " def run(self, inp: str = \"\") -> Tuple[subprocess.CompletedProcess, Outcome]:\n", " \"\"\"Run the program with `inp` as input. \n", " Return test outcome based on result of `subprocess.run()`.\"\"\"\n", " result = self.run_process(inp)\n", "\n", " if result.returncode == 0:\n", " outcome = self.PASS\n", " elif result.returncode < 0:\n", " outcome = self.FAIL\n", " else:\n", " outcome = self.UNRESOLVED\n", "\n", " return (result, outcome)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Here's a variant for binary (i.e., non-textual) input and output." ] }, { "cell_type": "code", "execution_count": 78, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:06.027101Z", "iopub.status.busy": "2024-01-18T17:14:06.027012Z", "iopub.status.idle": "2024-01-18T17:14:06.029250Z", "shell.execute_reply": "2024-01-18T17:14:06.028860Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "class BinaryProgramRunner(ProgramRunner):\n", " def run_process(self, inp: str = \"\") -> subprocess.CompletedProcess:\n", " \"\"\"Run the program with `inp` as input. \n", " Return result of `subprocess.run()`.\"\"\"\n", " return subprocess.run(self.program,\n", " input=inp.encode(),\n", " stdout=subprocess.PIPE,\n", " stderr=subprocess.PIPE)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "Let us demonstrate a `ProgramRunner` using the `cat` program – a program that copies its input to its output. We see that a standard invocation of `cat` simply does the job, with the output of `cat` being the same as its input:" ] }, { "cell_type": "code", "execution_count": 79, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:06.030904Z", "iopub.status.busy": "2024-01-18T17:14:06.030807Z", "iopub.status.idle": "2024-01-18T17:14:06.048374Z", "shell.execute_reply": "2024-01-18T17:14:06.047775Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "(CompletedProcess(args='cat', returncode=0, stdout='hello', stderr=''), 'PASS')" ] }, "execution_count": 79, "metadata": {}, "output_type": "execute_result" } ], "source": [ "cat = ProgramRunner(program=\"cat\")\n", "cat.run(\"hello\")" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "### Fuzzer Classes\n", "\n", "Let us now define a *fuzzer* that actually feed data into a consumer. The base class for fuzzers provides one central method `fuzz()` that creates some input. The `run()` function then sends the fuzz() input to a runner, returning the outcome; `runs()` does this for a given number (`trials`) of times." ] }, { "cell_type": "code", "execution_count": 80, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:06.050658Z", "iopub.status.busy": "2024-01-18T17:14:06.050503Z", "iopub.status.idle": "2024-01-18T17:14:06.053918Z", "shell.execute_reply": "2024-01-18T17:14:06.053566Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "class Fuzzer:\n", " \"\"\"Base class for fuzzers.\"\"\"\n", "\n", " def __init__(self) -> None:\n", " \"\"\"Constructor\"\"\"\n", " pass\n", "\n", " def fuzz(self) -> str:\n", " \"\"\"Return fuzz input\"\"\"\n", " return \"\"\n", "\n", " def run(self, runner: Runner = Runner()) \\\n", " -> Tuple[subprocess.CompletedProcess, Outcome]:\n", " \"\"\"Run `runner` with fuzz input\"\"\"\n", " return runner.run(self.fuzz())\n", "\n", " def runs(self, runner: Runner = PrintRunner(), trials: int = 10) \\\n", " -> List[Tuple[subprocess.CompletedProcess, Outcome]]:\n", " \"\"\"Run `runner` with fuzz input, `trials` times\"\"\"\n", " return [self.run(runner) for i in range(trials)]" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "By default, `Fuzzer` objects do not do much, as their `fuzz()` function is merely an abstract placeholder. The subclass `RandomFuzzer`, however, implements the functionality of the `fuzzer()` function, above, adding a parameter `min_length` to specify a minimum length." ] }, { "cell_type": "code", "execution_count": 81, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:06.056070Z", "iopub.status.busy": "2024-01-18T17:14:06.055929Z", "iopub.status.idle": "2024-01-18T17:14:06.059175Z", "shell.execute_reply": "2024-01-18T17:14:06.058832Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "class RandomFuzzer(Fuzzer):\n", " \"\"\"Produce random inputs.\"\"\"\n", "\n", " def __init__(self, min_length: int = 10, max_length: int = 100,\n", " char_start: int = 32, char_range: int = 32) -> None:\n", " \"\"\"Produce strings of `min_length` to `max_length` characters\n", " in the range [`char_start`, `char_start` + `char_range`)\"\"\"\n", " self.min_length = min_length\n", " self.max_length = max_length\n", " self.char_start = char_start\n", " self.char_range = char_range\n", "\n", " def fuzz(self) -> str:\n", " string_length = random.randrange(self.min_length, self.max_length + 1)\n", " out = \"\"\n", " for i in range(0, string_length):\n", " out += chr(random.randrange(self.char_start,\n", " self.char_start + self.char_range))\n", " return out" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "With `RandomFuzzer`, we can now create a fuzzer whose configuration needs to be specified only once when creating the fuzzer." ] }, { "cell_type": "code", "execution_count": 82, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:06.061382Z", "iopub.status.busy": "2024-01-18T17:14:06.061220Z", "iopub.status.idle": "2024-01-18T17:14:06.063722Z", "shell.execute_reply": "2024-01-18T17:14:06.063426Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "'>23>33)(&\"09.377.*3\n", "*+:5 ? (?1$4<>!?3>.'\n", "4+3/(3 (0%!>!(+9%,#$\n", "/51$2964>;)2417<9\"2&\n", "907.. !7:&--\"=$7',7*\n", "(5=5'.!*+&>\")6%9)=,/\n", "?:&5) \";.0!=6>3+>)=,\n", "6&,?:!#2))- ?:)=63'-\n", ",)9#839%)?&(0<6(\"*;)\n", "4?!(49+8=-'&499%?< '\n" ] } ], "source": [ "random_fuzzer = RandomFuzzer(min_length=20, max_length=20)\n", "for i in range(10):\n", " print(random_fuzzer.fuzz())" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "We can now send such generated inputs to our previously defined `cat` runner, verifying that `cat` actually does copy its (fuzzed) input to its output." ] }, { "cell_type": "code", "execution_count": 83, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:06.066714Z", "iopub.status.busy": "2024-01-18T17:14:06.066494Z", "iopub.status.idle": "2024-01-18T17:14:06.119444Z", "shell.execute_reply": "2024-01-18T17:14:06.118973Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "for i in range(10):\n", " inp = random_fuzzer.fuzz()\n", " result, outcome = cat.run(inp)\n", " assert result.stdout == inp\n", " assert outcome == Runner.PASS" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "Combining a `Fuzzer` with a `Runner`, however, is so common that we can use the `run()` method supplied by the `Fuzzer` class for this purpose:" ] }, { "cell_type": "code", "execution_count": 84, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:06.121685Z", "iopub.status.busy": "2024-01-18T17:14:06.121547Z", "iopub.status.idle": "2024-01-18T17:14:06.141140Z", "shell.execute_reply": "2024-01-18T17:14:06.140662Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "(CompletedProcess(args='cat', returncode=0, stdout='?:+= % <1<6$:(>=:9)5', stderr=''),\n", " 'PASS')" ] }, "execution_count": 84, "metadata": {}, "output_type": "execute_result" } ], "source": [ "random_fuzzer.run(cat)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "With `runs()`, we can repeat a fuzzing run a number of times, obtaining a list of results." ] }, { "cell_type": "code", "execution_count": 85, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:06.144235Z", "iopub.status.busy": "2024-01-18T17:14:06.143782Z", "iopub.status.idle": "2024-01-18T17:14:06.188719Z", "shell.execute_reply": "2024-01-18T17:14:06.188351Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "[(CompletedProcess(args='cat', returncode=0, stdout='3976%%&+%6=(1)3&3:<9', stderr=''),\n", " 'PASS'),\n", " (CompletedProcess(args='cat', returncode=0, stdout='33$#42$ 11=*%$20=<.-', stderr=''),\n", " 'PASS'),\n", " (CompletedProcess(args='cat', returncode=0, stdout='\"?<\\'#8 &&72\", stderr=''),\n", " 'PASS'),\n", " (CompletedProcess(args='cat', returncode=0, stdout=\"=,+:,6'5:950+><3(*()\", stderr=''),\n", " 'PASS'),\n", " (CompletedProcess(args='cat', returncode=0, stdout=\" 379+0?'%3137=2:4605\", stderr=''),\n", " 'PASS'),\n", " (CompletedProcess(args='cat', returncode=0, stdout=\"02>!$+:\", stderr=''),\n", " 'PASS'),\n", " (CompletedProcess(args='cat', returncode=0, stdout=\"=-<'3-#88*%&*9< +1&&\", stderr=''),\n", " 'PASS'),\n", " (CompletedProcess(args='cat', returncode=0, stdout='2;;0=3&6=8&30&<-;?*;', stderr=''),\n", " 'PASS'),\n", " (CompletedProcess(args='cat', returncode=0, stdout='/#05=*3($>::#7!0=12+', stderr=''),\n", " 'PASS')]" ] }, "execution_count": 85, "metadata": {}, "output_type": "execute_result" } ], "source": [ "random_fuzzer.runs(cat, 10)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "With this, we have all in place to create fuzzers – starting with the simple random fuzzers introduced in this chapter, but even far more advanced ones. Stay tuned!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Synopsis\n", "\n", "This chapter provides two important classes, introduced in [A Fuzzing Architecture](#A-Fuzzing-Architecture):\n", "\n", "* `Fuzzer` as a base class for fuzzers; and\n", "* `Runner` as a base class for programs under test." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Fuzzers\n", "\n", "`Fuzzer` is a base class for fuzzers, with `RandomFuzzer` as a simple instantiation. The `fuzz()` method of `Fuzzer` objects returns a string with a generated input." ] }, { "cell_type": "code", "execution_count": 86, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:14:06.190879Z", "iopub.status.busy": "2024-01-18T17:14:06.190739Z", "iopub.status.idle": "2024-01-18T17:14:06.193369Z", "shell.execute_reply": "2024-01-18T17:14:06.193071Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "'%$<1&<%+=!\"83?+)9:++9138 42/ \"7;0-,)06 \"1(2;6>?99$%7!!*#96=>2&-/(5*)=$;0$$+;<12\"?30&'" ] }, "execution_count": 86, "metadata": {}, "output_type": "execute_result" } ], "source": [ "random_fuzzer = RandomFuzzer()\n", "random_fuzzer.fuzz()" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "The `RandomFuzzer()` constructor allows a number of keyword arguments:" ] }, { "cell_type": "code", "execution_count": 87, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:14:06.195115Z", "iopub.status.busy": "2024-01-18T17:14:06.194995Z", "iopub.status.idle": "2024-01-18T17:14:06.196982Z", "shell.execute_reply": "2024-01-18T17:14:06.196657Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Produce strings of `min_length` to `max_length` characters\n", " in the range [`char_start`, `char_start` + `char_range`)\n" ] } ], "source": [ "print(RandomFuzzer.__init__.__doc__)" ] }, { "cell_type": "code", "execution_count": 88, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:14:06.198676Z", "iopub.status.busy": "2024-01-18T17:14:06.198557Z", "iopub.status.idle": "2024-01-18T17:14:06.201487Z", "shell.execute_reply": "2024-01-18T17:14:06.201090Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "'XGZVDDPZOOW'" ] }, "execution_count": 88, "metadata": {}, "output_type": "execute_result" } ], "source": [ "random_fuzzer = RandomFuzzer(min_length=10, max_length=20, char_start=65, char_range=26)\n", "random_fuzzer.fuzz()" ] }, { "cell_type": "code", "execution_count": 89, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:14:06.203384Z", "iopub.status.busy": "2024-01-18T17:14:06.203173Z", "iopub.status.idle": "2024-01-18T17:14:06.221808Z", "shell.execute_reply": "2024-01-18T17:14:06.221481Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "# ignore\n", "from ClassDiagram import display_class_hierarchy" ] }, { "cell_type": "code", "execution_count": 90, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:14:06.224407Z", "iopub.status.busy": "2024-01-18T17:14:06.224263Z", "iopub.status.idle": "2024-01-18T17:14:06.669607Z", "shell.execute_reply": "2024-01-18T17:14:06.669135Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "RandomFuzzer\n", "\n", "\n", "RandomFuzzer\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "fuzz()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "Fuzzer\n", "\n", "\n", "Fuzzer\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "fuzz()\n", "\n", "\n", "\n", "run()\n", "\n", "\n", "\n", "runs()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "RandomFuzzer->Fuzzer\n", "\n", "\n", "\n", "\n", "\n", "Legend\n", "Legend\n", "• \n", "public_method()\n", "• \n", "private_method()\n", "• \n", "overloaded_method()\n", "Hover over names to see doc\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 90, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# ignore\n", "display_class_hierarchy(RandomFuzzer,\n", " public_methods=[\n", " Fuzzer.__init__,\n", " Fuzzer.fuzz,\n", " Fuzzer.run,\n", " Fuzzer.runs,\n", " RandomFuzzer.fuzz,\n", " RandomFuzzer.__init__,\n", " ],\n", " project='fuzzingbook')" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Runners\n", "\n", "A `Fuzzer` can be paired with a `Runner`, which takes the fuzzed strings as input. Its result is a class-specific _status_ and an _outcome_ (`PASS`, `FAIL`, or `UNRESOLVED`). A `PrintRunner` will simply print out the given input and return a `PASS` outcome:" ] }, { "cell_type": "code", "execution_count": 91, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:14:06.671744Z", "iopub.status.busy": "2024-01-18T17:14:06.671571Z", "iopub.status.idle": "2024-01-18T17:14:06.674454Z", "shell.execute_reply": "2024-01-18T17:14:06.674153Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "EQYGAXPTVPJGTYHXFJ\n" ] }, { "data": { "text/plain": [ "('EQYGAXPTVPJGTYHXFJ', 'UNRESOLVED')" ] }, "execution_count": 91, "metadata": {}, "output_type": "execute_result" } ], "source": [ "print_runner = PrintRunner()\n", "random_fuzzer.run(print_runner)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "A `ProgramRunner` will feed the generated input into an external program. Its result is a pair of the program status (a `CompletedProcess` instance) and an _outcome_ (`PASS`, `FAIL`, or `UNRESOLVED`):" ] }, { "cell_type": "code", "execution_count": 92, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:14:06.676269Z", "iopub.status.busy": "2024-01-18T17:14:06.676132Z", "iopub.status.idle": "2024-01-18T17:14:06.683849Z", "shell.execute_reply": "2024-01-18T17:14:06.683527Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "(CompletedProcess(args='cat', returncode=0, stdout='BZOQTXFBTEOVYX', stderr=''),\n", " 'PASS')" ] }, "execution_count": 92, "metadata": {}, "output_type": "execute_result" } ], "source": [ "cat = ProgramRunner('cat')\n", "random_fuzzer.run(cat)" ] }, { "cell_type": "code", "execution_count": 93, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:14:06.685594Z", "iopub.status.busy": "2024-01-18T17:14:06.685474Z", "iopub.status.idle": "2024-01-18T17:14:07.097643Z", "shell.execute_reply": "2024-01-18T17:14:07.097272Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "ProgramRunner\n", "\n", "\n", "ProgramRunner\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "run()\n", "\n", "\n", "\n", "run_process()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "Runner\n", "\n", "\n", "Runner\n", "\n", "\n", "\n", "FAIL\n", "\n", "\n", "\n", "PASS\n", "\n", "\n", "\n", "UNRESOLVED\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "run()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "ProgramRunner->Runner\n", "\n", "\n", "\n", "\n", "\n", "PrintRunner\n", "\n", "\n", "PrintRunner\n", "\n", "\n", "\n", "run()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "PrintRunner->Runner\n", "\n", "\n", "\n", "\n", "\n", "Legend\n", "Legend\n", "• \n", "public_method()\n", "• \n", "private_method()\n", "• \n", "overloaded_method()\n", "Hover over names to see doc\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 93, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# ignore\n", "display_class_hierarchy([ProgramRunner, PrintRunner],\n", " public_methods=[\n", " Runner.__init__,\n", " Runner.run,\n", " ProgramRunner.__init__,\n", " ProgramRunner.run,\n", " PrintRunner.run\n", " ],\n", " project='fuzzingbook')" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Lessons Learned\n", "\n", "* Randomly generating inputs (\"fuzzing\") is a simple, cost-effective way to quickly test arbitrary programs for their robustness.\n", "* Bugs fuzzers find are mainly due to errors and deficiencies in _input processing_.\n", "* To catch errors, have as many _consistency checkers_ as possible." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "source": [ "We're done, so don't forget to clean up:" ] }, { "cell_type": "code", "execution_count": 94, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:07.099438Z", "iopub.status.busy": "2024-01-18T17:14:07.099312Z", "iopub.status.idle": "2024-01-18T17:14:07.101380Z", "shell.execute_reply": "2024-01-18T17:14:07.101137Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "os.remove(FILE)\n", "os.removedirs(tempdir)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "source": [ "## Next Steps\n", "\n", "From here, you can explore how to\n", "\n", "* [use _mutations_ on existing inputs to get more valid inputs](MutationFuzzer.ipynb)\n", "* [use _grammars_ to specify the input format and thus get many more valid inputs](Grammars.ipynb)\n", "* [reduce _failing inputs_ for efficient debugging](Reducer.ipynb)\n", "\n", "Enjoy the read!" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Background\n", "\n", "Books on generating software tests in general are scarce (which is why we wrote this book). There are a few notable books on _fuzzing,_ though, also based on the basic fuzzing techniques introduced in this chapter:\n", "\n", "* The book \"Fuzzing – Brute Force Vulnerability Discovery\" covers a wide range of fuzzing domains, including files, Web pages, environment variables, and network protocols. The authors bring in lots of experience from fuzzing at Microsoft, and include a number of ready-made tools for Windows and UNIX programs. The tools have aged somewhat, but the principles remain.\n", "\n", "* The book \"Fuzzing for Software Security Testing and Quality Assurance\" \\cite{Takanen2008}, now in its second edition 2018, covers a wide range of fuzzing tools and detection techniques; its authors bring in plenty of experience from security testing and vulnerability discovery. This is arguably one of the most comprehensive and up-to-date books on the field.\n", "\n", "Specifically for this chapter, the seminal work on fuzzing, introducing both the term and the approach, is \"An Empirical Study of the Reliability of UNIX Utilities\" \\cite{Miller1990}. As the foundation for the field, this is a must-read for anyone interested in fuzzing and robustness testing, with observations as valid today as they were 30 years ago." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Exercises" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "One of the errors found by Miller et al. \\cite{Miller1990} involves the _troff_ typesetting system. _Troff_ takes as input a text consisting of lines; a line beginning with a dot (`.`) includes typesetting commands, as in\n", "\n", "```\n", ".NH\n", "Some Heading\n", ".LP\n", "Some paragraph\n", "```\n", "\n", "which would produce (using `nroff -ms`) the text\n", "\n", "```\n", "1. Some Heading\n", "\n", "Some paragraph\n", "```" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "At the time of Miller et al., _troff_ would fail if its input included\n", "\n", "1. The input sequence `\\D` (backslash + D) followed by a non-printable character\n", "2. A character in the ASCII range 128–255 (i.e., the 8th bit is set) followed by a newline character\n", "3. A single dot (`.`) followed by a newline character." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" }, "solution2": "hidden", "solution2_first": true }, "source": [ "### Exercise 1: Simulate Troff\n", "\n", "For each of the above, write a Python function `f(s)` that fails if `s` fulfills the failure criterion." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "source": [ "**Solution**. Here are three functions that check their input for `troff` bugs:" ] }, { "cell_type": "code", "execution_count": 95, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:07.102942Z", "iopub.status.busy": "2024-01-18T17:14:07.102843Z", "iopub.status.idle": "2024-01-18T17:14:07.104542Z", "shell.execute_reply": "2024-01-18T17:14:07.104190Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [], "source": [ "import string" ] }, { "cell_type": "code", "execution_count": 96, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:07.105910Z", "iopub.status.busy": "2024-01-18T17:14:07.105821Z", "iopub.status.idle": "2024-01-18T17:14:07.108028Z", "shell.execute_reply": "2024-01-18T17:14:07.107709Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [], "source": [ "def no_backslash_d(inp):\n", " pattern = \"\\\\D\"\n", " index = inp.find(pattern)\n", " if index < 0 or index + len(pattern) >= len(inp):\n", " return True\n", " c = inp[index + len(pattern)]\n", " assert c in string.printable" ] }, { "cell_type": "code", "execution_count": 97, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:07.109771Z", "iopub.status.busy": "2024-01-18T17:14:07.109647Z", "iopub.status.idle": "2024-01-18T17:14:07.111663Z", "shell.execute_reply": "2024-01-18T17:14:07.111395Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "Traceback (most recent call last):\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_72058/1873852117.py\", line 2, in \n", " no_backslash_d(\"\\\\D\\0\")\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_72058/2739137185.py\", line 7, in no_backslash_d\n", " assert c in string.printable\n", "AssertionError (expected)\n" ] } ], "source": [ "with ExpectError():\n", " no_backslash_d(\"\\\\D\\0\")" ] }, { "cell_type": "code", "execution_count": 98, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:07.113430Z", "iopub.status.busy": "2024-01-18T17:14:07.113303Z", "iopub.status.idle": "2024-01-18T17:14:07.115305Z", "shell.execute_reply": "2024-01-18T17:14:07.115037Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [], "source": [ "def no_8bit(inp):\n", " for i in range(len(inp) - 1):\n", " assert ord(inp[i]) <= 127 or inp[i + 1] != '\\n'\n", " return True" ] }, { "cell_type": "code", "execution_count": 99, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:07.116953Z", "iopub.status.busy": "2024-01-18T17:14:07.116821Z", "iopub.status.idle": "2024-01-18T17:14:07.118676Z", "shell.execute_reply": "2024-01-18T17:14:07.118413Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "Traceback (most recent call last):\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_72058/4044610929.py\", line 2, in \n", " no_8bit(\"ä\\n\")\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_72058/986149540.py\", line 3, in no_8bit\n", " assert ord(inp[i]) <= 127 or inp[i + 1] != '\\n'\n", "AssertionError (expected)\n" ] } ], "source": [ "with ExpectError():\n", " no_8bit(\"ä\\n\")" ] }, { "cell_type": "code", "execution_count": 100, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:07.120082Z", "iopub.status.busy": "2024-01-18T17:14:07.119974Z", "iopub.status.idle": "2024-01-18T17:14:07.121785Z", "shell.execute_reply": "2024-01-18T17:14:07.121515Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [], "source": [ "def no_dot(inp):\n", " assert inp != \".\\n\"\n", " return True" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" }, "solution2": "hidden", "solution2_first": true }, "source": [ "### Exercise 2: Run Simulated Troff\n", "\n", "Create a class `TroffRunner` as subclass of `Runner` that checks for the above predicates. Run it with `Fuzzer`. Be sure to have the `Fuzzer` object produce the entire range of characters. Count how frequently the individual predicates fail." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "source": [ "**Solution.** Here's a simple example:" ] }, { "cell_type": "code", "execution_count": 101, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:07.123720Z", "iopub.status.busy": "2024-01-18T17:14:07.123558Z", "iopub.status.idle": "2024-01-18T17:14:07.126284Z", "shell.execute_reply": "2024-01-18T17:14:07.125992Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [], "source": [ "class TroffRunner(Runner):\n", " def __init__(self):\n", " self.no_backslash_d_failures = 0\n", " self.no_8bit_failures = 0\n", " self.no_dot_failures = 0\n", "\n", " def run(self, inp):\n", " try:\n", " no_backslash_d(inp)\n", " except AssertionError:\n", " self.no_backslash_d_failures += 1\n", "\n", " try:\n", " no_8bit(inp)\n", " except AssertionError:\n", " self.no_8bit_failures += 1\n", "\n", " try:\n", " no_dot(inp)\n", " except:\n", " self.no_dot_failures += 1\n", "\n", " return inp" ] }, { "cell_type": "code", "execution_count": 102, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:07.127805Z", "iopub.status.busy": "2024-01-18T17:14:07.127693Z", "iopub.status.idle": "2024-01-18T17:14:07.129493Z", "shell.execute_reply": "2024-01-18T17:14:07.129217Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [], "source": [ "random_fuzzer = RandomFuzzer(char_start=0, char_range=256, max_length=10)\n", "troff_runner = TroffRunner()" ] }, { "cell_type": "code", "execution_count": 103, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:07.130940Z", "iopub.status.busy": "2024-01-18T17:14:07.130836Z", "iopub.status.idle": "2024-01-18T17:14:07.755882Z", "shell.execute_reply": "2024-01-18T17:14:07.755559Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [], "source": [ "trials = 100000\n", "for i in range(trials):\n", " random_fuzzer.run(troff_runner)" ] }, { "cell_type": "code", "execution_count": 104, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:07.757700Z", "iopub.status.busy": "2024-01-18T17:14:07.757603Z", "iopub.status.idle": "2024-01-18T17:14:07.759790Z", "shell.execute_reply": "2024-01-18T17:14:07.759558Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [ { "data": { "text/plain": [ "5" ] }, "execution_count": 104, "metadata": {}, "output_type": "execute_result" } ], "source": [ "troff_runner.no_backslash_d_failures" ] }, { "cell_type": "code", "execution_count": 105, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:07.761264Z", "iopub.status.busy": "2024-01-18T17:14:07.761149Z", "iopub.status.idle": "2024-01-18T17:14:07.763074Z", "shell.execute_reply": "2024-01-18T17:14:07.762807Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [ { "data": { "text/plain": [ "1717" ] }, "execution_count": 105, "metadata": {}, "output_type": "execute_result" } ], "source": [ "troff_runner.no_8bit_failures" ] }, { "cell_type": "code", "execution_count": 106, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:07.764467Z", "iopub.status.busy": "2024-01-18T17:14:07.764367Z", "iopub.status.idle": "2024-01-18T17:14:07.766322Z", "shell.execute_reply": "2024-01-18T17:14:07.766086Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [ { "data": { "text/plain": [ "0" ] }, "execution_count": 106, "metadata": {}, "output_type": "execute_result" } ], "source": [ "troff_runner.no_dot_failures" ] }, { "cell_type": "code", "execution_count": 107, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:07.767753Z", "iopub.status.busy": "2024-01-18T17:14:07.767651Z", "iopub.status.idle": "2024-01-18T17:14:08.144795Z", "shell.execute_reply": "2024-01-18T17:14:08.144492Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAjAAAAGzCAYAAAAxPS2EAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/bCgiHAAAACXBIWXMAAA9hAAAPYQGoP6dpAAA2p0lEQVR4nO3de1hVVeL/8c8BPQdRDnjhqiTKlLfQysowr2kgmlpZjXdLRyuxi0ymTOWtKUsbsyazmkltGp20xtR0fuZdUslMQ5SU1NGsBMwbR6VAYP/+6OF8OwIKDoQL36/n2c/DXmvttdfe5+T5tPfa59gsy7IEAABgEK+qHgAAAEB5EWAAAIBxCDAAAMA4BBgAAGAcAgwAADAOAQYAABiHAAMAAIxDgAEAAMYhwAAAAOMQYAAYb//+/YqJiZG/v79sNpuWLl1a1UP6zc2fP182m02HDx+u6qEAvwkCDK4qaWlpGjx4sBo2bCiHw6GwsDANGjRIaWlpVT00/A+GDRum3bt364UXXtD777+vm2++uaqHBKCS1ajqAQC/lSVLlmjAgAGqV6+eRowYoSZNmujw4cN699139dFHH+mDDz7QPffcU9XDRDn99NNPSk5O1jPPPKMxY8ZU9XAA/EYIMLgqHDx4UEOGDFHTpk2VlJSkwMBAd90TTzyhjh07asiQIUpNTVXTpk2rcKTF5eTkyNfXt1h5fn6+CgsLZbfbq2BUV44ff/xRkhQQEFCp+yksLFReXp58fHyK1Z07d061a9f+n/ov7XUGUDJuIeGqMGPGDOXk5Oidd97xCC+S1KBBA7399ts6d+6cpk+f7lH3ww8/aMSIEQoLC5PD4VCTJk306KOPKi8vz93m9OnTGjt2rCIiIuRwONSoUSMNHTpUx48fl1T63ISNGzfKZrNp48aN7rIuXbro+uuv144dO9SpUyf5+vrqT3/6kw4fPiybzaZXXnlFs2bNUmRkpBwOh77++mtJ0r59+3TfffepXr168vHx0c0336zly5d77K9oHFu2bFFCQoICAwNVu3Zt3XPPPe4Q8Gv/7//9P3Xu3Fl+fn5yOp265ZZbtHDhQo8227ZtU48ePeTv7y9fX1917txZW7Zs8Whz5swZPfnkk+7zExQUpDvvvFM7d+68yCv2i6+++kpxcXFyOp2qU6eOunXrps8//9xdP3nyZDVu3FiSNG7cONlsNkVERFy0z9zcXE2aNEm/+93v5HA4FB4erqefflq5ubke7Ww2m8aMGaMFCxaoVatWcjgcWrVqlfs8btq0SaNHj1ZQUJAaNWrk3u7NN990tw8LC1N8fLxOnz7t0Xdpr/PF7Nu3Tw888IACAwNVq1YtNWvWTM8888xFt1m2bJl69erlfv9GRkbq+eefV0FBgUe7/fv3q1+/fgoJCZGPj48aNWqk/v37Kzs7291mzZo16tChgwICAlSnTh01a9as2JjLem7L0hdwKVyBwVXhk08+UUREhDp27FhifadOnRQREaGVK1e6y44ePapbb71Vp0+f1qhRo9S8eXP98MMP+uijj5STkyO73a6zZ8+qY8eO2rt3r4YPH66bbrpJx48f1/Lly/X999+rQYMG5R7riRMnFBcXp/79+2vw4MEKDg52182bN08///yzRo0aJYfDoXr16iktLU233367GjZsqAkTJqh27dpavHix7r77bv373/8udlvsscceU926dTVp0iQdPnxYs2bN0pgxY7Ro0SJ3m/nz52v48OFq1aqVEhMTFRAQoK+++kqrVq3SwIEDJUnr169XXFyc2rZtq0mTJsnLy0vz5s3THXfcoc8++0y33nqrJOmRRx7RRx99pDFjxqhly5Y6ceKENm/erL179+qmm24q9TykpaWpY8eOcjqdevrpp1WzZk29/fbb6tKlizZt2qR27drp3nvvVUBAgMaOHasBAwaoZ8+eqlOnTql9FhYWqk+fPtq8ebNGjRqlFi1aaPfu3Xr11Vf1zTffFJv8u379ei1evFhjxoxRgwYNFBERoZSUFEnS6NGjFRgYqIkTJ+rcuXOSfglUU6ZMUffu3fXoo48qPT1dc+bM0fbt27VlyxbVrFmzTK/zhVJTU9WxY0fVrFlTo0aNUkREhA4ePKhPPvlEL7zwQqnbzZ8/X3Xq1FFCQoLq1Kmj9evXa+LEiXK5XJoxY4YkKS8vT7GxscrNzdVjjz2mkJAQ/fDDD1qxYoVOnz4tf39/paWl6a677lLr1q01depUORwOHThwwCOslvXclqUvoEwsoJo7ffq0Jcnq27fvRdv16dPHkmS5XC7Lsixr6NChlpeXl7V9+/ZibQsLCy3LsqyJEydakqwlS5aU2mbevHmWJOvQoUMe9Rs2bLAkWRs2bHCXde7c2ZJkvfXWWx5tDx06ZEmynE6ndezYMY+6bt26WVFRUdbPP//sse/27dtb1157rbusaBzdu3d3j82yLGvs2LGWt7e3dfr0acuyfjlffn5+Vrt27ayffvqpxGMqLCy0rr32Wis2Ntajr5ycHKtJkybWnXfe6S7z9/e34uPji52fS7n77rstu91uHTx40F129OhRy8/Pz+rUqVOxczNjxoxL9vn+++9bXl5e1meffeZR/tZbb1mSrC1btrjLJFleXl5WWlqaR9ui89ihQwcrPz/fXX7s2DHLbrdbMTExVkFBgbv8jTfesCRZc+fOdZeV9jqXplOnTpafn5/17bffepT/+tyX9D7Lyckp1tfDDz9s+fr6ut8vX331lSXJ+vDDD0vd/6uvvmpJsn788cdS25T13JalL6AsuIWEau/MmTOSJD8/v4u2K6p3uVwqLCzU0qVL1bt37xKfaLHZbJKkf//732rTpk2Jk3+L2pSXw+HQQw89VGJdv379PG6BnTx5UuvXr9cDDzygM2fO6Pjx4zp+/LhOnDih2NhY7d+/Xz/88INHH6NGjfIYW8eOHVVQUKBvv/1W0i+X98+cOaMJEyYUm+9RtF1KSor279+vgQMH6sSJE+79njt3Tt26dVNSUpIKCwsl/TI3Zdu2bTp69GiZz0FBQYFWr16tu+++22NOUmhoqAYOHKjNmzfL5XKVub8iH374oVq0aKHmzZu7x3z8+HHdcccdkqQNGzZ4tO/cubNatmxZYl8jR46Ut7e3e33t2rXKy8vTk08+KS8vL492TqfT4+qedPHX+dd+/PFHJSUlafjw4brmmms86i71HqtVq5b776L3R8eOHZWTk6N9+/ZJkvz9/SVJn376qXJyckrsp2h+0bJly9yv64XKem7L0hdQFgQYVHtFwaQoyJTm10Hnxx9/lMvl0vXXX3/RbQ4ePHjJNuXVsGHDUifmNmnSxGP9wIEDsixLzz33nAIDAz2WSZMmSZKOHTvmsc2FH4J169aVJJ06dUrSL8ck6aLHtX//fkm/PL584X7//ve/Kzc31z1/Yvr06dqzZ4/Cw8N16623avLkyfrvf/970XPw448/KicnR82aNStW16JFCxUWFuq77767aB+ljTstLa3YmK+77jpJxc/Vhef7YnVFAfDCMdvtdjVt2tRdX+Rir/OvFZ2ry3mfpaWl6Z577pG/v7+cTqcCAwM1ePBgSXK/Pk2aNFFCQoL+/ve/q0GDBoqNjdXs2bM95r/8/ve/1+23364//OEPCg4OVv/+/bV48WKPAFLWc1uWvoCyYA4Mqj1/f3+FhoYqNTX1ou1SU1PVsGFDOZ1O/fTTTxW2/9L+L/nCiZRFfv1/zZeqK/pH/6mnnlJsbGyJ2/zud7/zWP/1VYNfsyyr1P1eqGi/M2bM0A033FBim6K5KA888IA6duyojz/+WKtXr9aMGTP08ssva8mSJYqLiyvzPitCYWGhoqKiNHPmzBLrw8PDPdbL81qU1/+6/aWcPn1anTt3ltPp1NSpUxUZGSkfHx/t3LlT48eP9wgMf/nLX/Tggw9q2bJlWr16tR5//HFNmzZNn3/+uRo1aqRatWopKSlJGzZs0MqVK7Vq1SotWrRId9xxh1avXi1vb+8yn9uy9AWUBQEGV4W77rpLf/vb37R582Z16NChWP1nn32mw4cP6+GHH5YkBQYGyul0as+ePRftNzIy8pJtiq5wXPgkyoX/R345im6v1KxZU927d/+f+5N+OSZJ2rNnT7Hwc2Ebp9NZpv2GhoZq9OjRGj16tI4dO6abbrpJL7zwQqkBJjAwUL6+vkpPTy9Wt2/fPnl5eRULG2URGRmpXbt2qVu3bpd9i680RU9Dpaene9z2ysvL06FDhy779Snq61Lvswtt3LhRJ06c0JIlS9SpUyd3+aFDh0psHxUVpaioKD377LPaunWrbr/9dr311lv685//LEny8vJSt27d1K1bN82cOVMvvviinnnmGW3YsEHdu3cv17m9VF9AWXALCVeFcePGqVatWnr44Yd14sQJj7qTJ0/qkUceka+vr8aNGyfpl39g7777bn3yySf68ssvi/VXdLWiX79+2rVrlz7++ONS2xR92CclJbnrCgoK9M477/zPxxUUFKQuXbro7bffVkZGRrH6kh6PvpSYmBj5+flp2rRp+vnnnz3qio6pbdu2ioyM1CuvvKKzZ8+Wut+CggKPWxFFYw4LCyv2aO2veXt7KyYmRsuWLfN4/DwrK0sLFy5Uhw4d5HQ6y31sDzzwgH744Qf97W9/K1b3008/uZ8muhzdu3eX3W7X66+/7nE1691331V2drZ69ep1Wf0GBgaqU6dOmjt3ro4cOeJRd7GrZkVXMn7dJi8vT2+++aZHO5fLpfz8fI+yqKgoeXl5uV+jkydPFuu/6MpbUZuyntuy9AWUBVdgcFW49tpr9d5772nQoEGKiooq9k28x48f17/+9S932JCkF198UatXr1bnzp3dj4VmZGToww8/1ObNmxUQEKBx48bpo48+0v3336/hw4erbdu2OnnypJYvX6633npLbdq0UatWrXTbbbcpMTFRJ0+eVL169fTBBx8U+9C4XLNnz1aHDh0UFRWlkSNHqmnTpsrKylJycrK+//577dq1q1z9OZ1Ovfrqq/rDH/6gW265RQMHDlTdunW1a9cu5eTk6L333pOXl5f+/ve/Ky4uTq1atdJDDz2khg0b6ocfftCGDRvkdDr1ySef6MyZM2rUqJHuu+8+tWnTRnXq1NHatWu1fft2/eUvf7noOP785z+7vy9k9OjRqlGjht5++23l5uYW+76eshoyZIgWL16sRx55RBs2bNDtt9+ugoIC7du3T4sXL9ann3562T9DEBgYqMTERE2ZMkU9evRQnz59lJ6erjfffFO33HKLe+7J5Xj99dfVoUMH3XTTTRo1apT7vbty5Ur3Y90Xat++verWrathw4bp8ccfl81m0/vvv18s9Kxfv15jxozR/fffr+uuu075+fl6//335e3trX79+kmSpk6dqqSkJPXq1UuNGzfWsWPH9Oabb6pRo0buK5plPbdl6Qsokyp7/gmoAqmpqdaAAQOs0NBQq2bNmlZISIg1YMAAa/fu3SW2//bbb62hQ4dagYGBlsPhsJo2bWrFx8dbubm57jYnTpywxowZYzVs2NCy2+1Wo0aNrGHDhlnHjx93tzl48KDVvXt3y+FwWMHBwdaf/vQna82aNSU+Rt2qVati47jUo8IHDx60hg4daoWEhFg1a9a0GjZsaN11113WRx995G5T9JjthY+Fl/Q4t2VZ1vLly6327dtbtWrVspxOp3Xrrbda//rXvzzafPXVV9a9995r1a9f33I4HFbjxo2tBx54wFq3bp1lWZaVm5trjRs3zmrTpo3l5+dn1a5d22rTpo315ptvlngcF9q5c6cVGxtr1alTx/L19bW6du1qbd26tVzn5kJ5eXnWyy+/bLVq1cpyOBxW3bp1rbZt21pTpkyxsrOz3e0klfj4d2nnscgbb7xhNW/e3KpZs6YVHBxsPfroo9apU6c82pT2Ol/Mnj17rHvuuccKCAiwfHx8rGbNmlnPPfdcsXH9+jHqLVu2WLfddptVq1YtKywszHr66aetTz/91OP1/u9//2sNHz7cioyMtHx8fKx69epZXbt2tdauXevuZ926dVbfvn2tsLAwy263W2FhYdaAAQOsb775xmOMZTm3Ze0LuBSbZZVj5h4AAMAVgDkwAADAOAQYAABgHAIMAAAwDgEGAAAYhwADAACMQ4ABAADGqbZfZFdYWKijR4/Kz8+vwr8yHAAAVA7LsnTmzBmFhYV5/LL7haptgDl69Ohl/VYKAACoet99950aNWpUan21DTB+fn6SfjkBl/ObKQAA4LfncrkUHh7u/hwvTbUNMEW3jZxOJwEGAADDXPJXzX+jcQAAAFQYAgwAADAOAQYAABiHAAMAAIxT7gCTlJSk3r17KywsTDabTUuXLvWot9lsJS4zZsxwt4mIiChW/9JLL3n0k5qaqo4dO8rHx0fh4eGaPn365R0hAACodsodYM6dO6c2bdpo9uzZJdZnZGR4LHPnzpXNZlO/fv082k2dOtWj3WOPPeauc7lciomJUePGjbVjxw7NmDFDkydP1jvvvFPe4QIAgGqo3I9Rx8XFKS4urtT6kJAQj/Vly5apa9euatq0qUe5n59fsbZFFixYoLy8PM2dO1d2u12tWrVSSkqKZs6cqVGjRpV3yAAAoJqp1DkwWVlZWrlypUaMGFGs7qWXXlL9+vV14403asaMGcrPz3fXJScnq1OnTrLb7e6y2NhYpaen69SpUyXuKzc3Vy6Xy2MBAADVU6V+kd17770nPz8/3XvvvR7ljz/+uG666SbVq1dPW7duVWJiojIyMjRz5kxJUmZmppo0aeKxTXBwsLuubt26xfY1bdo0TZkypZKOBAAAXEkqNcDMnTtXgwYNko+Pj0d5QkKC++/WrVvLbrfr4Ycf1rRp0+RwOC5rX4mJiR79Fn0VMQAAqH4qLcB89tlnSk9P16JFiy7Ztl27dsrPz9fhw4fVrFkzhYSEKCsry6NN0Xpp82YcDsdlhx8AAGCWSpsD8+6776pt27Zq06bNJdumpKTIy8tLQUFBkqTo6GglJSXp/Pnz7jZr1qxRs2bNSrx9BAAAri7lDjBnz55VSkqKUlJSJEmHDh1SSkqKjhw54m7jcrn04Ycf6g9/+EOx7ZOTkzVr1izt2rVL//3vf7VgwQKNHTtWgwcPdoeTgQMHym63a8SIEUpLS9OiRYv02muvedwiAgAAV69y30L68ssv1bVrV/d6UagYNmyY5s+fL0n64IMPZFmWBgwYUGx7h8OhDz74QJMnT1Zubq6aNGmisWPHeoQTf39/rV69WvHx8Wrbtq0aNGigiRMn8gg1AACQJNksy7KqehCVweVyyd/fX9nZ2XI6nVU9HKBCRUxYWdVDQBU7/FKvqh4CUCnK+vnNbyEBAADjEGAAAIBxCDAAAMA4BBgAAGAcAgwAADAOAQYAABiHAAMAAIxDgAEAAMYhwAAAAOMQYAAAgHEIMAAAwDgEGAAAYBwCDAAAMA4BBgAAGIcAAwAAjEOAAQAAxiHAAAAA4xBgAACAcQgwAADAOAQYAABgHAIMAAAwDgEGAAAYhwADAACMQ4ABAADGIcAAAADjEGAAAIBxCDAAAMA4BBgAAGAcAgwAADAOAQYAABiHAAMAAIxDgAEAAMYhwAAAAOMQYAAAgHEIMAAAwDgEGAAAYBwCDAAAMA4BBgAAGIcAAwAAjEOAAQAAxil3gElKSlLv3r0VFhYmm82mpUuXetQ/+OCDstlsHkuPHj082pw8eVKDBg2S0+lUQECARowYobNnz3q0SU1NVceOHeXj46Pw8HBNnz69/EcHAACqpXIHmHPnzqlNmzaaPXt2qW169OihjIwM9/Kvf/3Lo37QoEFKS0vTmjVrtGLFCiUlJWnUqFHuepfLpZiYGDVu3Fg7duzQjBkzNHnyZL3zzjvlHS4AAKiGapR3g7i4OMXFxV20jcPhUEhISIl1e/fu1apVq7R9+3bdfPPNkqS//vWv6tmzp1555RWFhYVpwYIFysvL09y5c2W329WqVSulpKRo5syZHkEHAABcnSplDszGjRsVFBSkZs2a6dFHH9WJEyfcdcnJyQoICHCHF0nq3r27vLy8tG3bNnebTp06yW63u9vExsYqPT1dp06dKnGfubm5crlcHgsAAKieKjzA9OjRQ//4xz+0bt06vfzyy9q0aZPi4uJUUFAgScrMzFRQUJDHNjVq1FC9evWUmZnpbhMcHOzRpmi9qM2Fpk2bJn9/f/cSHh5e0YcGAACuEOW+hXQp/fv3d/8dFRWl1q1bKzIyUhs3blS3bt0qenduiYmJSkhIcK+7XC5CDAAA1VSlP0bdtGlTNWjQQAcOHJAkhYSE6NixYx5t8vPzdfLkSfe8mZCQEGVlZXm0KVovbW6Nw+GQ0+n0WAAAQPVU6QHm+++/14kTJxQaGipJio6O1unTp7Vjxw53m/Xr16uwsFDt2rVzt0lKStL58+fdbdasWaNmzZqpbt26lT1kAABwhSt3gDl79qxSUlKUkpIiSTp06JBSUlJ05MgRnT17VuPGjdPnn3+uw4cPa926derbt69+97vfKTY2VpLUokUL9ejRQyNHjtQXX3yhLVu2aMyYMerfv7/CwsIkSQMHDpTdbteIESOUlpamRYsW6bXXXvO4RQQAAK5e5Q4wX375pW688UbdeOONkqSEhATdeOONmjhxory9vZWamqo+ffrouuuu04gRI9S2bVt99tlncjgc7j4WLFig5s2bq1u3burZs6c6dOjg8R0v/v7+Wr16tQ4dOqS2bdvqj3/8oyZOnMgj1AAAQJJksyzLqupBVAaXyyV/f39lZ2czHwbVTsSElVU9BFSxwy/1quohAJWirJ/f/BYSAAAwDgEGAAAYhwADAACMQ4ABAADGIcAAAADjEGAAAIBxCDAAAMA4BBgAAGAcAgwAADAOAQYAABiHAAMAAIxDgAEAAMYhwAAAAOMQYAAAgHEIMAAAwDgEGAAAYBwCDAAAMA4BBgAAGIcAAwAAjEOAAQAAxiHAAAAA4xBgAACAcQgwAADAOAQYAABgHAIMAAAwDgEGAAAYhwADAACMQ4ABAADGIcAAAADjEGAAAIBxCDAAAMA4BBgAAGAcAgwAADAOAQYAABiHAAMAAIxDgAEAAMYhwAAAAOMQYAAAgHEIMAAAwDgEGAAAYJxyB5ikpCT17t1bYWFhstlsWrp0qbvu/PnzGj9+vKKiolS7dm2FhYVp6NChOnr0qEcfERERstlsHstLL73k0SY1NVUdO3aUj4+PwsPDNX369Ms7QgAAUO2UO8CcO3dObdq00ezZs4vV5eTkaOfOnXruuee0c+dOLVmyROnp6erTp0+xtlOnTlVGRoZ7eeyxx9x1LpdLMTExaty4sXbs2KEZM2Zo8uTJeuedd8o7XAAAUA3VKO8GcXFxiouLK7HO399fa9as8Sh74403dOutt+rIkSO65ppr3OV+fn4KCQkpsZ8FCxYoLy9Pc+fOld1uV6tWrZSSkqKZM2dq1KhR5R0yAACoZip9Dkx2drZsNpsCAgI8yl966SXVr19fN954o2bMmKH8/Hx3XXJysjp16iS73e4ui42NVXp6uk6dOlXifnJzc+VyuTwWAABQPZX7Ckx5/Pzzzxo/frwGDBggp9PpLn/88cd10003qV69etq6dasSExOVkZGhmTNnSpIyMzPVpEkTj76Cg4PddXXr1i22r2nTpmnKlCmVeDQAAOBKUWkB5vz583rggQdkWZbmzJnjUZeQkOD+u3Xr1rLb7Xr44Yc1bdo0ORyOy9pfYmKiR78ul0vh4eGXN3gAAHBFq5QAUxRevv32W61fv97j6ktJ2rVrp/z8fB0+fFjNmjVTSEiIsrKyPNoUrZc2b8bhcFx2+AEAAGap8DkwReFl//79Wrt2rerXr3/JbVJSUuTl5aWgoCBJUnR0tJKSknT+/Hl3mzVr1qhZs2Yl3j4CAABXl3JfgTl79qwOHDjgXj906JBSUlJUr149hYaG6r777tPOnTu1YsUKFRQUKDMzU5JUr1492e12JScna9u2beratav8/PyUnJyssWPHavDgwe5wMnDgQE2ZMkUjRozQ+PHjtWfPHr322mt69dVXK+iwAQCAyWyWZVnl2WDjxo3q2rVrsfJhw4Zp8uTJxSbfFtmwYYO6dOminTt3avTo0dq3b59yc3PVpEkTDRkyRAkJCR63gFJTUxUfH6/t27erQYMGeuyxxzR+/Pgyj9Plcsnf31/Z2dmXvIUFmCZiwsqqHgKq2OGXelX1EIBKUdbP73IHGFMQYFCdEWBAgEF1VdbPb34LCQAAGIcAAwAAjEOAAQAAxiHAAAAA4xBgAACAcQgwAADAOAQYAABgHAIMAAAwDgEGAAAYhwADAACMQ4ABAADGIcAAAADjEGAAAIBxCDAAAMA4BBgAAGAcAgwAADAOAQYAABiHAAMAAIxDgAEAAMYhwAAAAOMQYAAAgHEIMAAAwDgEGAAAYBwCDAAAMA4BBgAAGIcAAwAAjEOAAQAAxiHAAAAA4xBgAACAcQgwAADAOAQYAABgHAIMAAAwDgEGAAAYhwADAACMQ4ABAADGIcAAAADjEGAAAIBxCDAAAMA4BBgAAGAcAgwAADBOuQNMUlKSevfurbCwMNlsNi1dutSj3rIsTZw4UaGhoapVq5a6d++u/fv3e7Q5efKkBg0aJKfTqYCAAI0YMUJnz571aJOamqqOHTvKx8dH4eHhmj59evmPDgAAVEvlDjDnzp1TmzZtNHv27BLrp0+frtdff11vvfWWtm3bptq1ays2NlY///yzu82gQYOUlpamNWvWaMWKFUpKStKoUaPc9S6XSzExMWrcuLF27NihGTNmaPLkyXrnnXcu4xABAEB1Y7Msy7rsjW02ffzxx7r77rsl/XL1JSwsTH/84x/11FNPSZKys7MVHBys+fPnq3///tq7d69atmyp7du36+abb5YkrVq1Sj179tT333+vsLAwzZkzR88884wyMzNlt9slSRMmTNDSpUu1b9++Mo3N5XLJ399f2dnZcjqdl3uIwBUpYsLKqh4Cqtjhl3pV9RCASlHWz+8KnQNz6NAhZWZmqnv37u4yf39/tWvXTsnJyZKk5ORkBQQEuMOLJHXv3l1eXl7atm2bu02nTp3c4UWSYmNjlZ6erlOnTpW479zcXLlcLo8FAABUTxUaYDIzMyVJwcHBHuXBwcHuuszMTAUFBXnU16hRQ/Xq1fNoU1Ifv97HhaZNmyZ/f3/3Eh4e/r8fEAAAuCJVm6eQEhMTlZ2d7V6+++67qh4SAACoJBUaYEJCQiRJWVlZHuVZWVnuupCQEB07dsyjPj8/XydPnvRoU1Ifv97HhRwOh5xOp8cCAACqpwoNME2aNFFISIjWrVvnLnO5XNq2bZuio6MlSdHR0Tp9+rR27NjhbrN+/XoVFhaqXbt27jZJSUk6f/68u82aNWvUrFkz1a1btyKHDAAADFTuAHP27FmlpKQoJSVF0i8Td1NSUnTkyBHZbDY9+eST+vOf/6zly5dr9+7dGjp0qMLCwtxPKrVo0UI9evTQyJEj9cUXX2jLli0aM2aM+vfvr7CwMEnSwIEDZbfbNWLECKWlpWnRokV67bXXlJCQUGEHDgAAzFWjvBt8+eWX6tq1q3u9KFQMGzZM8+fP19NPP61z585p1KhROn36tDp06KBVq1bJx8fHvc2CBQs0ZswYdevWTV5eXurXr59ef/11d72/v79Wr16t+Ph4tW3bVg0aNNDEiRM9visGAABcvf6n74G5kvE9MKjO+B4Y8D0wqK6q5HtgAAAAfgsEGAAAYBwCDAAAMA4BBgAAGIcAAwAAjEOAAQAAxiHAAAAA4xBgAACAcQgwAADAOAQYAABgHAIMAAAwDgEGAAAYhwADAACMQ4ABAADGIcAAAADjEGAAAIBxCDAAAMA4BBgAAGAcAgwAADAOAQYAABiHAAMAAIxDgAEAAMYhwAAAAOMQYAAAgHEIMAAAwDgEGAAAYBwCDAAAMA4BBgAAGIcAAwAAjEOAAQAAxiHAAAAA4xBgAACAcQgwAADAOAQYAABgHAIMAAAwDgEGAAAYhwADAACMQ4ABAADGIcAAAADjEGAAAIBxCDAAAMA4FR5gIiIiZLPZii3x8fGSpC5duhSre+SRRzz6OHLkiHr16iVfX18FBQVp3Lhxys/Pr+ihAgAAQ9Wo6A63b9+ugoIC9/qePXt055136v7773eXjRw5UlOnTnWv+/r6uv8uKChQr169FBISoq1btyojI0NDhw5VzZo19eKLL1b0cAEAgIEqPMAEBgZ6rL/00kuKjIxU586d3WW+vr4KCQkpcfvVq1fr66+/1tq1axUcHKwbbrhBzz//vMaPH6/JkyfLbrdX9JABAIBhKnUOTF5env75z39q+PDhstls7vIFCxaoQYMGuv7665WYmKicnBx3XXJysqKiohQcHOwui42NlcvlUlpaWqn7ys3Nlcvl8lgAAED1VOFXYH5t6dKlOn36tB588EF32cCBA9W4cWOFhYUpNTVV48ePV3p6upYsWSJJyszM9AgvktzrmZmZpe5r2rRpmjJlSsUfBAAAuOJUaoB59913FRcXp7CwMHfZqFGj3H9HRUUpNDRU3bp108GDBxUZGXnZ+0pMTFRCQoJ73eVyKTw8/LL7AwAAV65KCzDffvut1q5d676yUpp27dpJkg4cOKDIyEiFhIToiy++8GiTlZUlSaXOm5Ekh8Mhh8PxP44aAACYoNLmwMybN09BQUHq1avXRdulpKRIkkJDQyVJ0dHR2r17t44dO+Zus2bNGjmdTrVs2bKyhgsAAAxSKVdgCgsLNW/ePA0bNkw1avzfLg4ePKiFCxeqZ8+eql+/vlJTUzV27Fh16tRJrVu3liTFxMSoZcuWGjJkiKZPn67MzEw9++yzio+P5woLAACQVEkBZu3atTpy5IiGDx/uUW6327V27VrNmjVL586dU3h4uPr166dnn33W3cbb21srVqzQo48+qujoaNWuXVvDhg3z+N4YAABwdauUABMTEyPLsoqVh4eHa9OmTZfcvnHjxvrPf/5TGUMDAADVAL+FBAAAjEOAAQAAxiHAAAAA4xBgAACAcQgwAADAOAQYAABgHAIMAAAwDgEGAAAYhwADAACMQ4ABAADGIcAAAADjEGAAAIBxCDAAAMA4BBgAAGAcAgwAADAOAQYAABiHAAMAAIxDgAEAAMYhwAAAAOMQYAAAgHEIMAAAwDgEGAAAYBwCDAAAMA4BBgAAGIcAAwAAjEOAAQAAxiHAAAAA4xBgAACAcQgwAADAOAQYAABgHAIMAAAwDgEGAAAYhwADAACMQ4ABAADGIcAAAADjEGAAAIBxCDAAAMA4BBgAAGAcAgwAADAOAQYAABinwgPM5MmTZbPZPJbmzZu763/++WfFx8erfv36qlOnjvr166esrCyPPo4cOaJevXrJ19dXQUFBGjdunPLz8yt6qAAAwFA1KqPTVq1aae3atf+3kxr/t5uxY8dq5cqV+vDDD+Xv768xY8bo3nvv1ZYtWyRJBQUF6tWrl0JCQrR161ZlZGRo6NChqlmzpl588cXKGC4AADBMpQSYGjVqKCQkpFh5dna23n33XS1cuFB33HGHJGnevHlq0aKFPv/8c912221avXq1vv76a61du1bBwcG64YYb9Pzzz2v8+PGaPHmy7HZ7ZQwZAAAYpFLmwOzfv19hYWFq2rSpBg0apCNHjkiSduzYofPnz6t79+7uts2bN9c111yj5ORkSVJycrKioqIUHBzsbhMbGyuXy6W0tLRS95mbmyuXy+WxAACA6qnCA0y7du00f/58rVq1SnPmzNGhQ4fUsWNHnTlzRpmZmbLb7QoICPDYJjg4WJmZmZKkzMxMj/BSVF9UV5pp06bJ39/fvYSHh1fsgQEAgCtGhd9CiouLc//dunVrtWvXTo0bN9bixYtVq1atit6dW2JiohISEtzrLpeLEAMAQDVV6Y9RBwQE6LrrrtOBAwcUEhKivLw8nT592qNNVlaWe85MSEhIsaeSitZLmldTxOFwyOl0eiwAAKB6qvQAc/bsWR08eFChoaFq27atatasqXXr1rnr09PTdeTIEUVHR0uSoqOjtXv3bh07dszdZs2aNXI6nWrZsmVlDxcAABigwm8hPfXUU+rdu7caN26so0ePatKkSfL29taAAQPk7++vESNGKCEhQfXq1ZPT6dRjjz2m6Oho3XbbbZKkmJgYtWzZUkOGDNH06dOVmZmpZ599VvHx8XI4HBU9XAAAYKAKDzDff/+9BgwYoBMnTigwMFAdOnTQ559/rsDAQEnSq6++Ki8vL/Xr10+5ubmKjY3Vm2++6d7e29tbK1as0KOPPqro6GjVrl1bw4YN09SpUyt6qAAAwFA2y7Ksqh5EZXC5XPL391d2djbzYVDtRExYWdVDQBU7/FKvqh4CUCnK+vnNbyEBAADjEGAAAIBxCDAAAMA4BBgAAGAcAgwAADAOAQYAABiHAAMAAIxDgAEAAMYhwAAAAOMQYAAAgHEIMAAAwDgEGAAAYBwCDAAAMA4BBgAAGIcAAwAAjEOAAQAAxiHAAAAA4xBgAACAcQgwAADAOAQYAABgHAIMAAAwDgEGAAAYhwADAACMQ4ABAADGIcAAAADjEGAAAIBxCDAAAMA4BBgAAGAcAgwAADAOAQYAABiHAAMAAIxDgAEAAMYhwAAAAOMQYAAAgHEIMAAAwDgEGAAAYBwCDAAAMA4BBgAAGIcAAwAAjEOAAQAAxqnwADNt2jTdcsst8vPzU1BQkO6++26lp6d7tOnSpYtsNpvH8sgjj3i0OXLkiHr16iVfX18FBQVp3Lhxys/Pr+jhAgAAA9Wo6A43bdqk+Ph43XLLLcrPz9ef/vQnxcTE6Ouvv1bt2rXd7UaOHKmpU6e61319fd1/FxQUqFevXgoJCdHWrVuVkZGhoUOHqmbNmnrxxRcresgAAMAwFR5gVq1a5bE+f/58BQUFaceOHerUqZO73NfXVyEhISX2sXr1an399ddau3atgoODdcMNN+j555/X+PHjNXnyZNnt9ooeNgAAMEilz4HJzs6WJNWrV8+jfMGCBWrQoIGuv/56JSYmKicnx12XnJysqKgoBQcHu8tiY2PlcrmUlpZW4n5yc3Plcrk8FgAAUD1V+BWYXyssLNSTTz6p22+/Xddff727fODAgWrcuLHCwsKUmpqq8ePHKz09XUuWLJEkZWZmeoQXSe71zMzMEvc1bdo0TZkypZKOBAAAXEkqNcDEx8drz5492rx5s0f5qFGj3H9HRUUpNDRU3bp108GDBxUZGXlZ+0pMTFRCQoJ73eVyKTw8/PIGDgAArmiVdgtpzJgxWrFihTZs2KBGjRpdtG27du0kSQcOHJAkhYSEKCsry6NN0Xpp82YcDoecTqfHAgAAqqcKDzCWZWnMmDH6+OOPtX79ejVp0uSS26SkpEiSQkNDJUnR0dHavXu3jh075m6zZs0aOZ1OtWzZsqKHDAAADFPht5Di4+O1cOFCLVu2TH5+fu45K/7+/qpVq5YOHjyohQsXqmfPnqpfv75SU1M1duxYderUSa1bt5YkxcTEqGXLlhoyZIimT5+uzMxMPfvss4qPj5fD4ajoIQMAAMNU+BWYOXPmKDs7W126dFFoaKh7WbRokSTJbrdr7dq1iomJUfPmzfXHP/5R/fr10yeffOLuw9vbWytWrJC3t7eio6M1ePBgDR061ON7YwAAwNWrwq/AWJZ10frw8HBt2rTpkv00btxY//nPfypqWAAAoBrht5AAAIBxCDAAAMA4BBgAAGAcAgwAADAOAQYAABiHAAMAAIxDgAEAAMYhwAAAAOMQYAAAgHEIMAAAwDgEGAAAYBwCDAAAMA4BBgAAGIcAAwAAjEOAAQAAxiHAAAAA4xBgAACAcQgwAADAOAQYAABgHAIMAAAwDgEGAAAYhwADAACMQ4ABAADGIcAAAADjEGAAAIBxCDAAAMA4BBgAAGAcAgwAADAOAQYAABiHAAMAAIxDgAEAAMYhwAAAAOMQYAAAgHEIMAAAwDgEGAAAYBwCDAAAMA4BBgAAGIcAAwAAjEOAAQAAxiHAAAAA41zRAWb27NmKiIiQj4+P2rVrpy+++KKqhwQAAK4AV2yAWbRokRISEjRp0iTt3LlTbdq0UWxsrI4dO1bVQwMAAFXsig0wM2fO1MiRI/XQQw+pZcuWeuutt+Tr66u5c+dW9dAAAEAVq1HVAyhJXl6eduzYocTERHeZl5eXunfvruTk5BK3yc3NVW5urns9OztbkuRyuSp8fNdP+rTC+4RZ9kyJrdL9F+bmVOn+UfUq49824EpQ9N62LOui7a7IAHP8+HEVFBQoODjYozw4OFj79u0rcZtp06ZpypQpxcrDw8MrZYy4uvnPquoR4GrHexDV3ZkzZ+Tv719q/RUZYC5HYmKiEhIS3OuFhYU6efKk6tevL5vNVoUjq35cLpfCw8P13Xffyel0VvVwcBXiPYiqxnuw8liWpTNnzigsLOyi7a7IANOgQQN5e3srKyvLozwrK0shISElbuNwOORwODzKAgICKmuIkOR0OvkPF1WK9yCqGu/BynGxKy9FrshJvHa7XW3bttW6devcZYWFhVq3bp2io6OrcGQAAOBKcEVegZGkhIQEDRs2TDfffLNuvfVWzZo1S+fOndNDDz1U1UMDAABV7IoNML///e/1448/auLEicrMzNQNN9ygVatWFZvYi9+ew+HQpEmTit2yA34rvAdR1XgPVj2bdannlAAAAK4wV+QcGAAAgIshwAAAAOMQYAAAgHEIMAAAwDgEGABGiIiI0KxZsy7axmazaenSpb/JeHB16dKli5588smqHgZ+hQCDEjVr1kzLli0rVm6z2dxL7dq1de211+rBBx/Ujh07qmCUqC4KCgr03HPPqUmTJqpVq5YiIyP1/PPPX/LH3C6UkZGhuLg4SdLhw4dls9mUkpJSCSMGSjd//ny+Cf43QIBBifr27avly5eXWDdv3jxlZGQoLS1Ns2fP1tmzZ9WuXTv94x//+I1Hieri5Zdf1pw5c/TGG29o7969evnllzV9+nT99a9/LVc/ISEhfC8HcJUgwKBEffr00cqVK1VYWFisLiAgQCEhIYqIiFBMTIw++ugjDRo0SGPGjNGpU6eqYLQw3datW9W3b1/16tVLERERuu+++xQTE6MvvvjCo92ZM2c0YMAA1a5dWw0bNtTs2bM96n99C6lJkyaSpBtvvFE2m01dunT5LQ4F1cC5c+c0dOhQ1alTR6GhofrLX/7iUX/q1CkNHTpUdevWla+vr+Li4rR//35J0saNG/XQQw8pOzvbfbV68uTJVXAU1R8BBiVq3769CgsLtW3btjK1Hzt2rM6cOaM1a9ZU8shQHbVv317r1q3TN998I0natWuXNm/e7L4dVGTGjBlq06aNvvrqK02YMEFPPPFEqe+5ovCzdu1aZWRkaMmSJZV7EKg2xo0bp02bNmnZsmVavXq1Nm7cqJ07d7rrH3zwQX355Zdavny5kpOTZVmWevbsqfPnz6t9+/aaNWuWnE6nMjIylJGRoaeeeqoKj6b6umJ/SgBVy8vLS3fddZeWLVtWph/QbN68uaRf5h0A5TVhwgS5XC41b95c3t7eKigo0AsvvKBBgwZ5tLv99ts1YcIESdJ1112nLVu26NVXX9Wdd95ZrM/AwEBJUv369Uv9FXvgQmfPntW7776rf/7zn+rWrZsk6b333lOjRo0kSfv379fy5cu1ZcsWtW/fXpK0YMEChYeHa+nSpbr//vvl7+8vm83G+66ScQUGperTp0+p82AuVDTZ0mazVeaQUE0tXrxYCxYs0MKFC7Vz50699957euWVV/Tee+95tLswTEdHR2vv3r2/5VBRzR08eFB5eXlq166du6xevXpq1qyZJGnv3r2qUaOGR339+vXVrFkz3ou/MQIMShUTE6PDhw/rwIEDl2xb9B9u0bwDoDzGjRunCRMmqH///oqKitKQIUM0duxYTZs2raqHBuAKRYBBqXx9fdWtW7cyXYUpuufbvXv332BkqG5ycnLk5eX5z5G3t3exSeSff/55sfUWLVqU2Kfdbpf0yyPaQFlFRkaqZs2aHvP/Tp065Z6f1aJFC+Xn53vUnzhxQunp6WrZsqWkX957vO8qHwEGF9W3b99i3wdz+vRpZWZm6ttvv9WaNWt03333aeHChZozZw7ffYDL0rt3b73wwgtauXKlDh8+rI8//lgzZ87UPffc49Fuy5Ytmj59ur755hvNnj1bH374oZ544okS+wwKClKtWrW0atUqZWVlKTs7+7c4FBiuTp06GjFihMaNG6f169drz549evDBB90B+9prr1Xfvn01cuRIbd68Wbt27dLgwYPVsGFD9e3bV9IvX7p49uxZrVu3TsePH1dOTk5VHlL1ZQEXkZmZadWsWdM6ceKEZVmWJcm9+Pj4WJGRkdawYcOsHTt2VPFIYTKXy2U98cQT1jXXXGP5+PhYTZs2tZ555hkrNzfX3aZx48bWlClTrPvvv9/y9fW1QkJCrNdee82jH0nWxx9/7F7/29/+ZoWHh1teXl5W586df6OjgenOnDljDR482PL19bWCg4Ot6dOnW507d7aeeOIJy7Is6+TJk9aQIUMsf39/q1atWlZsbKz1zTffePTxyCOPWPXr17ckWZMmTfrtD+IqYLOscn7VJa460dHRGj16tIYMGVLVQwEAQBKPUaMMpkyZory8vKoeBgAAblyBAQAAxmESLwAAMA4BBgAAGIcAAwAAjEOAAQAAxiHAAAAA4xBgAACAcQgwAADAOAQYAABgHAIMAAAwzv8Hy/6OP7k6MtcAAAAASUVORK5CYII=\n", "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "%matplotlib inline\n", "\n", "ys = [troff_runner.no_backslash_d_failures,\n", " troff_runner.no_8bit_failures,\n", " troff_runner.no_dot_failures]\n", "\n", "import matplotlib.pyplot as plt\n", "plt.bar([\"\\\\D\", \"8bit\", \"dot\"], ys)\n", "plt.title(\"Occurrences of error classes\");" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "source": [ "Again, we can see that some inputs (such as the single dot) are very improbable." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "### Exercise 3: Run Real Troff" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" }, "solution2": "hidden", "solution2_first": true }, "source": [ "Using `BinaryProgramRunner`, apply the fuzzer you configured on the real `troff` program. Check if you can produce any run whose output code is non-zero, indicating a failure or a crash." ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "source": [ "**Solution.** This is just a matter of putting pieces together." ] }, { "cell_type": "code", "execution_count": 108, "metadata": { "button": false, "deletable": true, "execution": { "iopub.execute_input": "2024-01-18T17:14:08.146734Z", "iopub.status.busy": "2024-01-18T17:14:08.146576Z", "iopub.status.idle": "2024-01-18T17:14:10.529501Z", "shell.execute_reply": "2024-01-18T17:14:10.528898Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [], "source": [ "real_troff_runner = BinaryProgramRunner(\"troff\")\n", "for i in range(100):\n", " result, outcome = random_fuzzer.run(real_troff_runner)\n", " if outcome == Runner.FAIL:\n", " print(result)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "source": [ "Unfortunately, it is very unlikely that you'll find a bug in `troff` at this point. Like most other open source code, it has been fuzzed this way before – and all errors found are already fixed." ] } ], "metadata": { "ipub": { "bibliography": "fuzzingbook.bib", "toc": true }, "kernelspec": { "display_name": "Python 3 (ipykernel)", "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.10.2" }, "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": 4 }