notebooks/ConfigurationFuzzer.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "slide"
    },
    "toc-hr-collapsed": false
   },
   "source": [
    "# Testing Configurations\n",
    "\n",
    "The behavior of a program is not only governed by its data.  The _configuration_ of a program – that is, the settings that govern the execution of a program on its (regular) input data, as set by options or configuration files – just as well influences behavior, and thus can and should be tested.  In this chapter, we explore how to systematically _test_ and _cover_ software configurations.  By _automatically inferring configuration options_, we can apply these techniques out of the box, with no need for writing a grammar.  Finally, we show how to systematically cover _combinations_ of configuration options, quickly detecting unwanted interferences."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "**Prerequisites**\n",
    "\n",
    "* You should have read the [chapter on grammars](Grammars.ipynb).\n",
    "* You should have read the [chapter on grammar coverage](GrammarCoverageFuzzer.ipynb)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": true,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Configuration Options\n",
    "\n",
    "When we talk about the input to a program, we usually think of the _data_ it processes. This is also what we have been fuzzing in the past chapters – be it with [random input](Fuzzer.ipynb), [mutation-based fuzzing](MutationFuzzer.ipynb), or [grammar-based fuzzing](GrammarFuzzer.ipynb).  However, programs typically have several input sources, all of which can and should be tested – and included in test generation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": true,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "One important source of input is the program's _configuration_ – that is, a set of inputs that typically is set once when beginning to process data and then stays constant while processing data, while the program is running, or even while the program is deployed.  Such a configuration is frequently set in _configuration files_ (for instance, as key/value pairs); the most ubiquitous method for command-line tools, though, are _configuration options_ on the command line."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "As an example, consider the `grep` utility to find textual patterns in files.  The exact mode by which `grep` works is governed by a multitude of options, which can be listed by providing a `--help` option:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "!grep --help"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "All these options need to be tested for whether they operate correctly.  In security testing, any such option may also trigger a yet unknown vulnerability.  Hence, such options can become _fuzz targets_ on their own.  In this chapter, we analyze how to systematically test such options – and better yet, how to extract possible configurations right out of given program files, such that we do not have to specify anything."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Options in Python\n",
    "\n",
    "Let us stick to our common programming language here and examine how options are processed in Python.  The `argparse` module provides a parser for command-line arguments (and options) with great functionality – and great complexity.  You start by defining a parser (`argparse.ArgumentParser()`) to which individual arguments with various features are added, one after another.  Additional parameters for each argument can specify the type (`type`) of the argument (say, integers or strings), or the number of arguments (`nargs`)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "By default, arguments are stored under their name in the `args` object coming from `parse_args()` – thus, `args.integers` holds the `integers` arguments added earlier.  Special actions (`actions`) allow to store specific values in given variables; the `store_const` action stores the given `const` in the attribute named by `dest`.  The following example takes a number of integer arguments (`integers`) as well as an operator (`--sum`, `--min`, or `--max`) to be applied on these integers.  The operators all store a function reference in the `accumulate` attribute, which is finally invoked on the integers parsed:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import argparse"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def process_numbers(args=[]):\n",
    "    parser = argparse.ArgumentParser(description='Process some integers.')\n",
    "    parser.add_argument('integers', metavar='N', type=int, nargs='+',\n",
    "                        help='an integer for the accumulator')\n",
    "    group = parser.add_mutually_exclusive_group(required=True)\n",
    "    group.add_argument('--sum', dest='accumulate', action='store_const',\n",
    "                       const=sum,\n",
    "                       help='sum the integers')\n",
    "    group.add_argument('--min', dest='accumulate', action='store_const',\n",
    "                       const=min,\n",
    "                       help='compute the minimum')\n",
    "    group.add_argument('--max', dest='accumulate', action='store_const',\n",
    "                       const=max,\n",
    "                       help='compute the maximum')\n",
    "\n",
    "    args = parser.parse_args(args)\n",
    "    print(args.accumulate(args.integers))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Here's how `process_numbers()` works.  We can, for instance, invoke the `--min` option on the given arguments to compute the minimum:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "process_numbers([\"--min\", \"100\", \"200\", \"300\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Or compute the sum of three numbers:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "process_numbers([\"--sum\", \"1\", \"2\", \"3\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "When defined via `add_mutually_exclusive_group()` (as above), options are mutually exclusive.  Consequently, we can have only one operator:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import fuzzingbook_utils"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from ExpectError import ExpectError"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "with ExpectError(print_traceback=False):\n",
    "    process_numbers([\"--sum\", \"--max\", \"1\", \"2\", \"3\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## A Grammar for Configurations\n",
    "\n",
    "How can we test a system with several options?  The easiest answer is to write a grammar for it.  The grammar `PROCESS_NUMBERS_EBNF_GRAMMAR` reflects the possible combinations of options and arguments:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from Grammars import crange, srange, convert_ebnf_grammar, extend_grammar, is_valid_grammar\n",
    "from Grammars import START_SYMBOL, new_symbol"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "PROCESS_NUMBERS_EBNF_GRAMMAR = {\n",
    "    \"<start>\": [\"<operator> <integers>\"],\n",
    "    \"<operator>\": [\"--sum\", \"--min\", \"--max\"],\n",
    "    \"<integers>\": [\"<integer>\", \"<integers> <integer>\"],\n",
    "    \"<integer>\": [\"<digit>+\"],\n",
    "    \"<digit>\": crange('0', '9')\n",
    "}\n",
    "\n",
    "assert is_valid_grammar(PROCESS_NUMBERS_EBNF_GRAMMAR)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "PROCESS_NUMBERS_GRAMMAR = convert_ebnf_grammar(PROCESS_NUMBERS_EBNF_GRAMMAR)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "We can feed this grammar into our [grammar coverage fuzzer](GrammarCoverageFuzzer.ipynb) and have it cover one option after another:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from GrammarCoverageFuzzer import GrammarCoverageFuzzer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "f = GrammarCoverageFuzzer(PROCESS_NUMBERS_GRAMMAR, min_nonterminals=10)\n",
    "for i in range(3):\n",
    "    print(f.fuzz())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Of course, we can also invoke `process_numbers()` with these very arguments. To this end, we need to convert the string produced by the grammar back into a list of individual arguments, using `split()`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "f = GrammarCoverageFuzzer(PROCESS_NUMBERS_GRAMMAR, min_nonterminals=10)\n",
    "for i in range(3):\n",
    "    args = f.fuzz().split()\n",
    "    print(args)\n",
    "    process_numbers(args)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "In a similar way, we can define grammars for any program to be tested; as well as define grammars for, say, configuration files.  Yet, the grammar has to be updated with every change to the program, which creates a maintenance burden.  Given that the information required for the grammar is already all encoded in the program, the question arises: _Can't we go and extract configuration options right out of the program in the first place?_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "## Mining Configuration Options\n",
    "\n",
    "In this section, we try to extract option and argument information right out of a program, such that we do not have to specify a configuration grammar.  The aim is to have a configuration fuzzer that works on the options and arguments of an arbitrary program, as long as it follows specific conventions for processing its arguments.  In the case of Python programs, this means using the `argparse` module.\n",
    "\n",
    "Our idea is as follows: We execute the given program up to the point where the arguments are actually parsed – that is, `argparse.parse_args()` is invoked.  Up to this point, we track all calls into the argument parser, notably those calls that define arguments and options (`add_argument()`).  From these, we construct the grammar."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### Tracking Arguments\n",
    "\n",
    "Let us illustrate this approach with a simple experiment: We define a trace function (see [our chapter on coverage](Coverage.ipynb) for details) that is active while `process_numbers` is invoked.  If we have a call to a method `add_argument`, we access and print out the local variables (which at this point are the arguments to the method)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import sys"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import string"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def traceit(frame, event, arg):\n",
    "    if event != \"call\":\n",
    "        return\n",
    "    method_name = frame.f_code.co_name\n",
    "    if method_name != \"add_argument\":\n",
    "        return\n",
    "    locals = frame.f_locals\n",
    "    print(method_name, locals)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "What we get is a list of all calls to `add_argument()`, together with the method arguments passed:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "sys.settrace(traceit)\n",
    "process_numbers([\"--sum\", \"1\", \"2\", \"3\"])\n",
    "sys.settrace(None)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "From the `args` argument, we can access the individual options and arguments to be defined:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def traceit(frame, event, arg):\n",
    "    if event != \"call\":\n",
    "        return\n",
    "    method_name = frame.f_code.co_name\n",
    "    if method_name != \"add_argument\":\n",
    "        return\n",
    "    locals = frame.f_locals\n",
    "    print(locals['args'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "sys.settrace(traceit)\n",
    "process_numbers([\"--sum\", \"1\", \"2\", \"3\"])\n",
    "sys.settrace(None)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "We see that each argument comes as a tuple with one (say, `integers` or `--sum`) or two members (`-h` and `--help`), which denote alternate forms for the same option.  Our job will be to go through the arguments of `add_arguments()` and detect not only the names of options and arguments, but also whether they accept additional parameters, as well as the type of the parameters."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### A Grammar Miner for Options and Arguments"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Let us now build a class that gathers all this information to create a grammar."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "We use the `ParseInterrupt` exception to interrupt program execution after gathering all arguments and options:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class ParseInterrupt(Exception):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The class `OptionGrammarMiner` takes an executable function for which the grammar of options and arguments is to be mined:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class OptionGrammarMiner(object):\n",
    "    def __init__(self, function, log=False):\n",
    "        self.function = function\n",
    "        self.log = log"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The method `mine_ebnf_grammar()` is where everything happens.  It creates a grammar of the form\n",
    "\n",
    "```\n",
    "<start> ::= <option>* <arguments>\n",
    "<option> ::= <empty>\n",
    "<arguments> ::= <empty>\n",
    "```\n",
    "\n",
    "in which the options and arguments will be collected.  It then sets a trace function (see [our chapter on coverage](Coverage.ipynb) for details) that is active while the previously defined `function` is invoked.  Raising `ParseInterrupt` (when `parse_args()` is invoked) ends execution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "class OptionGrammarMiner(OptionGrammarMiner):\n",
    "    OPTION_SYMBOL = \"<option>\"\n",
    "    ARGUMENTS_SYMBOL = \"<arguments>\"\n",
    "\n",
    "    def mine_ebnf_grammar(self):\n",
    "        self.grammar = {\n",
    "            START_SYMBOL: [\"(\" + self.OPTION_SYMBOL + \")*\" + self.ARGUMENTS_SYMBOL],\n",
    "            self.OPTION_SYMBOL: [],\n",
    "            self.ARGUMENTS_SYMBOL: []\n",
    "        }\n",
    "        self.current_group = self.OPTION_SYMBOL\n",
    "\n",
    "        old_trace = sys.settrace(self.traceit)\n",
    "        try:\n",
    "            self.function()\n",
    "        except ParseInterrupt:\n",
    "            pass\n",
    "        sys.settrace(old_trace)\n",
    "\n",
    "        return self.grammar\n",
    "\n",
    "    def mine_grammar(self):\n",
    "        return convert_ebnf_grammar(self.mine_ebnf_grammar())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The trace function checks for four methods: `add_argument()` is the most important function, resulting in processing arguments; `frame.f_locals` again is the set of local variables, which at this point is mostly the arguments to `add_argument()`.  Since mutually exclusive groups also have a method `add_argument()`, we set the flag `in_group` to differentiate."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Note that we make no specific efforts to differentiate between multiple parsers or groups; we simply assume that there is one parser, and at any point at most one mutually exclusive group."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "class OptionGrammarMiner(OptionGrammarMiner):\n",
    "    def traceit(self, frame, event, arg):\n",
    "        if event != \"call\":\n",
    "            return\n",
    "\n",
    "        if \"self\" not in frame.f_locals:\n",
    "            return\n",
    "        self_var = frame.f_locals[\"self\"]\n",
    "\n",
    "        method_name = frame.f_code.co_name\n",
    "\n",
    "        if method_name == \"add_argument\":\n",
    "            in_group = repr(type(self_var)).find(\"Group\") >= 0\n",
    "            self.process_argument(frame.f_locals, in_group)\n",
    "        elif method_name == \"add_mutually_exclusive_group\":\n",
    "            self.add_group(frame.f_locals, exclusive=True)\n",
    "        elif method_name == \"add_argument_group\":\n",
    "            # self.add_group(frame.f_locals, exclusive=False)\n",
    "            pass\n",
    "        elif method_name == \"parse_args\":\n",
    "            raise ParseInterrupt\n",
    "\n",
    "        return None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The `process_arguments()` now analyzes the arguments passed and adds them to the grammar:\n",
    "\n",
    "* If the argument starts with `-`, it gets added as an optional element to the `<option>` list\n",
    "* Otherwise, it gets added to the `<argument>` list.\n",
    "\n",
    "The optional `nargs` argument specifies how many arguments can follow.  If it is a number, we add the appropriate number of elements to the grammar; if it is an abstract specifier (say, `+` or `*`), we use it directly as EBNF operator.\n",
    "\n",
    "Given the large number of parameters and optional behavior, this is a somewhat messy function, but it does the job."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "class OptionGrammarMiner(OptionGrammarMiner):\n",
    "    def process_argument(self, locals, in_group):\n",
    "        args = locals[\"args\"]\n",
    "        kwargs = locals[\"kwargs\"]\n",
    "\n",
    "        if self.log:\n",
    "            print(args)\n",
    "            print(kwargs)\n",
    "            print()\n",
    "\n",
    "        for arg in args:\n",
    "            self.process_arg(arg, in_group, kwargs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "class OptionGrammarMiner(OptionGrammarMiner):\n",
    "    def process_arg(self, arg, in_group, kwargs):\n",
    "        if arg.startswith('-'):\n",
    "            if not in_group:\n",
    "                target = self.OPTION_SYMBOL\n",
    "            else:\n",
    "                target = self.current_group\n",
    "            metavar = None\n",
    "            arg = \" \" + arg\n",
    "        else:\n",
    "            target = self.ARGUMENTS_SYMBOL\n",
    "            metavar = arg\n",
    "            arg = \"\"\n",
    "\n",
    "        if \"nargs\" in kwargs:\n",
    "            nargs = kwargs[\"nargs\"]\n",
    "        else:\n",
    "            nargs = 1\n",
    "\n",
    "        param = self.add_parameter(kwargs, metavar)\n",
    "        if param == \"\":\n",
    "            nargs = 0\n",
    "\n",
    "        if isinstance(nargs, int):\n",
    "            for i in range(nargs):\n",
    "                arg += param\n",
    "        else:\n",
    "            assert nargs in \"?+*\"\n",
    "            arg += '(' + param + ')' + nargs\n",
    "\n",
    "        if target == self.OPTION_SYMBOL:\n",
    "            self.grammar[target].append(arg)\n",
    "        else:\n",
    "            self.grammar[target].append(arg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The method `add_parameter()` handles possible parameters of options.  If the argument has an `action` defined, it takes no parameter.  Otherwise, we identify the type of the parameter (as `int` or `str`) and augment the grammar with an appropriate rule."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import inspect"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "class OptionGrammarMiner(OptionGrammarMiner):\n",
    "    def add_parameter(self, kwargs, metavar):\n",
    "        if \"action\" in kwargs:\n",
    "            # No parameter\n",
    "            return \"\"\n",
    "\n",
    "        type_ = \"str\"\n",
    "        if \"type\" in kwargs:\n",
    "            given_type = kwargs[\"type\"]\n",
    "            # int types come as '<class int>'\n",
    "            if inspect.isclass(given_type) and issubclass(given_type, int):\n",
    "                type_ = \"int\"\n",
    "\n",
    "        if metavar is None:\n",
    "            if \"metavar\" in kwargs:\n",
    "                metavar = kwargs[\"metavar\"]\n",
    "            else:\n",
    "                metavar = type_\n",
    "\n",
    "        self.add_type_rule(type_)\n",
    "        if metavar != type_:\n",
    "            self.add_metavar_rule(metavar, type_)\n",
    "\n",
    "        param = \" <\" + metavar + \">\"\n",
    "\n",
    "        return param"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The method `add_type_rule()` adds a rule for parameter types to the grammar.  If the parameter is identified by a meta-variable (say, `N`), we add a rule for this as well to improve legibility."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class OptionGrammarMiner(OptionGrammarMiner):\n",
    "    def add_type_rule(self, type_):\n",
    "        if type_ == \"int\":\n",
    "            self.add_int_rule()\n",
    "        else:\n",
    "            self.add_str_rule()\n",
    "\n",
    "    def add_int_rule(self):\n",
    "        self.grammar[\"<int>\"] = [\"(-)?<digit>+\"]\n",
    "        self.grammar[\"<digit>\"] = crange('0', '9')\n",
    "\n",
    "    def add_str_rule(self):\n",
    "        self.grammar[\"<str>\"] = [\"<char>+\"]\n",
    "        self.grammar[\"<char>\"] = srange(\n",
    "            string.digits\n",
    "            + string.ascii_letters\n",
    "            + string.punctuation)\n",
    "\n",
    "    def add_metavar_rule(self, metavar, type_):\n",
    "        self.grammar[\"<\" + metavar + \">\"] = [\"<\" + type_ + \">\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The method `add_group()` adds a new mutually exclusive group to the grammar.  We define a new symbol (say, `<group>`) for the options added to the group, and use the `required` and `exclusive` flags to define an appropriate expansion operator.  The group is then prefixed to the grammar, as in\n",
    "\n",
    "```\n",
    "<start> ::= <group><option>* <arguments>\n",
    "<group> ::= <empty>\n",
    "```\n",
    "\n",
    "and filled with the next calls to `add_argument()` within the group."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "class OptionGrammarMiner(OptionGrammarMiner):\n",
    "    def add_group(self, locals, exclusive):\n",
    "        kwargs = locals[\"kwargs\"]\n",
    "        if self.log:\n",
    "            print(kwargs)\n",
    "\n",
    "        required = kwargs.get(\"required\", False)\n",
    "        group = new_symbol(self.grammar, \"<group>\")\n",
    "\n",
    "        if required and exclusive:\n",
    "            group_expansion = group\n",
    "        if required and not exclusive:\n",
    "            group_expansion = group + \"+\"\n",
    "        if not required and exclusive:\n",
    "            group_expansion = group + \"?\"\n",
    "        if not required and not exclusive:\n",
    "            group_expansion = group + \"*\"\n",
    "\n",
    "        self.grammar[START_SYMBOL][0] = group_expansion + \\\n",
    "            self.grammar[START_SYMBOL][0]\n",
    "        self.grammar[group] = []\n",
    "        self.current_group = group"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "That's it!  With this, we can now extract the grammar from our `process_numbers()` program.  Turning on logging again reveals the variables we draw upon."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "miner = OptionGrammarMiner(process_numbers, log=True)\n",
    "process_numbers_grammar = miner.mine_ebnf_grammar()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Here is the extracted grammar:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "process_numbers_grammar"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The grammar properly identifies the group found:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "process_numbers_grammar[\"<start>\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "process_numbers_grammar[\"<group>\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "It also identifies a `--help` option provided not by us, but by the `argparse` module:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "process_numbers_grammar[\"<option>\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The grammar also correctly identifies the types of the arguments:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "process_numbers_grammar[\"<arguments>\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "process_numbers_grammar[\"<integers>\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The rules for `int` are set as defined by `add_int_rule()`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "process_numbers_grammar[\"<int>\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "We can take this grammar and convert it to BNF, such that we can fuzz with it right away:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "assert is_valid_grammar(process_numbers_grammar)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "grammar = convert_ebnf_grammar(process_numbers_grammar)\n",
    "assert is_valid_grammar(grammar)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "f = GrammarCoverageFuzzer(grammar)\n",
    "for i in range(10):\n",
    "    print(f.fuzz())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Each and every invocation adheres to the rules as set forth in the `argparse` calls.  By mining options and arguments from existing programs, we can now fuzz these options out of the box – without having to specify a grammar."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "toc-hr-collapsed": true
   },
   "source": [
    "## Testing Autopep8"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Let us try out the option grammar miner on real-world Python programs.  `autopep8` is a tool that automatically converts Python code to the [PEP 8 Style Guide for Python Code](https://www.python.org/dev/peps/pep-0008/).  (Actually, all Python code in this book runs through `autopep8` during production.)  `autopep8` offers a wide range of options, as can be seen by invoking it with `--help`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "!autopep8 --help"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Autopep8 Setup\n",
    "\n",
    "We want to systematically test these options.  In order to deploy our configuration grammar miner, we need to find the source code of the executable:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import os"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def find_executable(name):\n",
    "    for path in os.get_exec_path():\n",
    "        qualified_name = os.path.join(path, name)\n",
    "        if os.path.exists(qualified_name):\n",
    "            return qualified_name\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "autopep8_executable = find_executable(\"autopep8\")\n",
    "assert autopep8_executable is not None\n",
    "autopep8_executable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Next, we build a function that reads the contents of the file and executes it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def autopep8():\n",
    "    executable = find_executable(\"autopep8\")\n",
    "\n",
    "    # First line has to contain \"/usr/bin/env python\" or like\n",
    "    first_line = open(executable).readline()\n",
    "    assert first_line.find(\"python\") >= 0\n",
    "\n",
    "    contents = open(executable).read()\n",
    "    exec(contents)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Mining an Autopep8 Grammar\n",
    "\n",
    "We can use the `autopep8()` function in our grammar miner:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "autopep8_miner = OptionGrammarMiner(autopep8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "and extract a grammar for it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "autopep8_ebnf_grammar = autopep8_miner.mine_ebnf_grammar()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "This works because here, `autopep8` is not a separate process (and a separate Python interpreter), but we run the `autopep8()` function (and the `autopep8` code) in our current Python interpreter – up to the call to `parse_args()`, where we interrupt execution again.  At this point, the `autopep8` code has done nothing but setting up the argument parser – which is what we are interested in."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The grammar options mined reflect precisely the options seen when providing `--help`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print(autopep8_ebnf_grammar[\"<option>\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Metavariables like `<n>` or `<line>` are placeholders for integers.  We assume all metavariables of the same name have the same type:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "autopep8_ebnf_grammar[\"<line>\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The grammar miner has inferred that the argument to `autopep8` is a list of files:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "autopep8_ebnf_grammar[\"<arguments>\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "which in turn all are strings:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "autopep8_ebnf_grammar[\"<files>\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "As we are only interested in testing options, not arguments, we fix the arguments to a single mandatory input.  (Otherwise, we'd have plenty of random file names generated.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "autopep8_ebnf_grammar[\"<arguments>\"] = [\" <files>\"]\n",
    "autopep8_ebnf_grammar[\"<files>\"] = [\"foo.py\"]\n",
    "assert is_valid_grammar(autopep8_ebnf_grammar)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Creating Autopep8 Options"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Let us now use the inferred grammar for fuzzing.  Again, we convert the EBNF grammar into a regular BNF grammar:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "autopep8_grammar = convert_ebnf_grammar(autopep8_ebnf_grammar)\n",
    "assert is_valid_grammar(autopep8_grammar)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "And we can use the grammar for fuzzing all options:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "f = GrammarCoverageFuzzer(autopep8_grammar, max_nonterminals=4)\n",
    "for i in range(20):\n",
    "    print(f.fuzz())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Let us apply these options on the actual program.  We need a file `foo.py` that will serve as input:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def create_foo_py():\n",
    "    open(\"foo.py\", \"w\").write(\"\"\"\n",
    "def twice(x = 2):\n",
    "    return  x  +  x\n",
    "\"\"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "create_foo_py()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print(open(\"foo.py\").read(), end=\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "We see how `autopep8` fixes the spacing:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "!autopep8 foo.py"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Let us now put things together.  We define a `ProgramRunner` that will run the `autopep8` executable with arguments coming from the mined `autopep8` grammar."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from Fuzzer import ProgramRunner"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Running `autopep8` with the mined options reveals a surprisingly high number of passing runs.  (We see that some options depend on each other or are mutually exclusive, but this is handled by the program logic, not the argument parser, and hence out of our scope.)  The `GrammarCoverageFuzzer` ensures that each option is tested at least once.  (Digits and letters, too, by the way.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "f = GrammarCoverageFuzzer(autopep8_grammar, max_nonterminals=5)\n",
    "for i in range(20):\n",
    "    invocation = \"autopep8\" + f.fuzz()\n",
    "    print(\"$ \" + invocation)\n",
    "    args = invocation.split()\n",
    "    autopep8 = ProgramRunner(args)\n",
    "    result, outcome = autopep8.run()\n",
    "    if result.stderr != \"\":\n",
    "        print(result.stderr, end=\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Our `foo.py` file now has been formatted in place a number of times:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print(open(\"foo.py\").read(), end=\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We don't need it anymore, so we clean up things:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import os"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "os.remove(\"foo.py\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "## Classes for Fuzzing Configuration Options\n",
    "\n",
    "Let us now create reusable classes that we can use for testing arbitrary programs.  (Okay, make that \"arbitrary programs that are written in Python and use the `argparse` module to process command-line arguments.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The class `OptionRunner` is a subclass of `ProgramRunner` that takes care of automatically determining the grammar, using the same steps we used for `autopep8`, above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class OptionRunner(ProgramRunner):\n",
    "    def __init__(self, program, arguments=None):\n",
    "        if isinstance(program, str):\n",
    "            self.base_executable = program\n",
    "        else:\n",
    "            self.base_executable = program[0]\n",
    "\n",
    "        self.find_contents()\n",
    "        self.find_grammar()\n",
    "        if arguments is not None:\n",
    "            self.set_arguments(arguments)\n",
    "        super().__init__(program)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "First, we find the contents of the Python executable:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class OptionRunner(OptionRunner):\n",
    "    def find_contents(self):\n",
    "        self._executable = find_executable(self.base_executable)\n",
    "        first_line = open(self._executable).readline()\n",
    "        assert first_line.find(\"python\") >= 0\n",
    "        self.contents = open(self._executable).read()\n",
    "\n",
    "    def invoker(self):\n",
    "        exec(self.contents)\n",
    "\n",
    "    def executable(self):\n",
    "        return self._executable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Next, we determine the grammar using the `OptionGrammarMiner` class:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class OptionRunner(OptionRunner):\n",
    "    def find_grammar(self):\n",
    "        miner = OptionGrammarMiner(self.invoker)\n",
    "        self._ebnf_grammar = miner.mine_ebnf_grammar()\n",
    "\n",
    "    def ebnf_grammar(self):\n",
    "        return self._ebnf_grammar\n",
    "\n",
    "    def grammar(self):\n",
    "        return convert_ebnf_grammar(self._ebnf_grammar)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The two service methods `set_arguments()` and `set_invocation()` help us to change the arguments and program, respectively."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from Grammars import unreachable_nonterminals"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class OptionRunner(OptionRunner):\n",
    "    def set_arguments(self, args):\n",
    "        self._ebnf_grammar[\"<arguments>\"] = [\" \" + args]\n",
    "        # Delete rules for previous arguments\n",
    "        for nonterminal in unreachable_nonterminals(self._ebnf_grammar):\n",
    "            del self._ebnf_grammar[nonterminal]\n",
    "\n",
    "    def set_invocation(self, program):\n",
    "        self.program = program"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "We can instantiate the class on `autopep8` and immediately get the grammar:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "autopep8_runner = OptionRunner(\"autopep8\", \"foo.py\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print(autopep8_runner.ebnf_grammar()[\"<option>\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "An `OptionFuzzer` interacts with the given `OptionRunner` to obtain its grammar, which is then passed to its `GrammarCoverageFuzzer` superclass."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class OptionFuzzer(GrammarCoverageFuzzer):\n",
    "    def __init__(self, runner, *args, **kwargs):\n",
    "        assert issubclass(type(runner), OptionRunner)\n",
    "        self.runner = runner\n",
    "        grammar = runner.grammar()\n",
    "        super().__init__(grammar, *args, **kwargs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "When invoking `run()`, the `OptionFuzzer` creates a new invocation (using `fuzz()` from its grammar) and runs the now given (or previously set) runner with the arguments from the grammar.  Note that the runner specified in `run()` can differ from the one set during initialization; this allows for mining options from one program and applying it in another context."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class OptionFuzzer(OptionFuzzer):\n",
    "    def run(self, runner=None, inp=\"\"):\n",
    "        if runner is None:\n",
    "            runner = self.runner\n",
    "        assert issubclass(type(runner), OptionRunner)\n",
    "        invocation = runner.executable() + \" \" + self.fuzz()\n",
    "        runner.set_invocation(invocation.split())\n",
    "        return runner.run(inp)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### Example: Autopep8\n",
    "\n",
    "Let us apply our newly defined classes on the `autopep8` runner:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "autopep8_fuzzer = OptionFuzzer(autopep8_runner, max_nonterminals=5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "for i in range(3):\n",
    "    print(autopep8_fuzzer.fuzz())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "We can now systematically test `autopep8` with these classes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "autopep8_fuzzer.run(autopep8_runner)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Example: MyPy\n",
    "\n",
    "We can extract options for the `mypy` static type checker for Python:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "assert find_executable(\"mypy\") is not None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "mypy_runner = OptionRunner(\"mypy\", \"foo.py\")\n",
    "print(mypy_runner.ebnf_grammar()[\"<option>\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "mypy_fuzzer = OptionFuzzer(mypy_runner, max_nonterminals=5)\n",
    "for i in range(10):\n",
    "    print(mypy_fuzzer.fuzz())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Example: Notedown\n",
    "\n",
    "Here's the configuration options for the `notedown` Notebook to Markdown converter:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "assert find_executable(\"notedown\") is not None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "notedown_runner = OptionRunner(\"notedown\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print(notedown_runner.ebnf_grammar()[\"<option>\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "notedown_fuzzer = OptionFuzzer(notedown_runner, max_nonterminals=5)\n",
    "for i in range(10):\n",
    "    print(notedown_fuzzer.fuzz())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Combinatorial Testing\n",
    "\n",
    "Our `CoverageGrammarFuzzer` does a good job in covering each and every option at least once, which is great for systematic testing.  However, as we also can see in our examples above, some options require each other, while others interfere with each other.  What we should do as good testers is not only to cover every option individually, but also _combinations_ of options."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The Python `itertools` module gives us means to create combinations from lists.  We can, for instance, take the `notedown` options and create a list of all pairs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from itertools import combinations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "option_list = notedown_runner.ebnf_grammar()[\"<option>\"]\n",
    "pairs = list(combinations(option_list, 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "There's quite a number of pairs:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "len(pairs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print(pairs[:20])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Testing every such pair of options frequently suffices to cover all interferences between options.  (Programs rarely have conditions involving three or more configuration settings.)  To this end, we _change_ the grammar from having a list of options to having a list of _option pairs_, such that covering these will automatically cover all pairs."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "We create a function `pairwise()` that takes a list of options as occurring in our grammar and returns a list of _pairwise options_ – that is, our original options, but concatenated."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def pairwise(option_list):\n",
    "    return [option_1 + option_2\n",
    "            for (option_1, option_2) in combinations(option_list, 2)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Here's the first 20 pairs:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print(pairwise(option_list)[:20])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The new grammar `pairwise_notedown_grammar` is a copy of the `notedown` grammar, but with the list of options replaced with the above pairwise option list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "notedown_grammar = notedown_runner.grammar()\n",
    "pairwise_notedown_grammar = extend_grammar(notedown_grammar)\n",
    "pairwise_notedown_grammar[\"<option>\"] = pairwise(notedown_grammar[\"<option>\"])\n",
    "assert is_valid_grammar(pairwise_notedown_grammar)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Using the \"pairwise\" grammar to fuzz now covers one pair after another:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "notedown_fuzzer = GrammarCoverageFuzzer(\n",
    "    pairwise_notedown_grammar, max_nonterminals=4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "for i in range(10):\n",
    "    print(notedown_fuzzer.fuzz())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Can we actually test all combinations of options?  Not in practice, as the number of combinations quickly grows as the length increases.  It decreases again as the number of options reaches the maximum (with 20 options, there is only 1 combination involving _all_ options), but the absolute numbers are still staggering:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "for combination_length in range(1, 20):\n",
    "    tuples = list(combinations(option_list, combination_length))\n",
    "    print(combination_length, len(tuples))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Formally, the number of combinations of length $k$ in a set of options of length $n$ is the binomial coefficient\n",
    "$$\n",
    "{n \\choose k} = \\frac{n!}{k!(n - k)!}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "which for $k = 2$ (all pairs) gives us\n",
    "\n",
    "$$\n",
    "{n \\choose 2} = \\frac{n!}{2(n - 2)!} = n \\times (n - 1)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "For `autopep8` with its 29 options..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "len(autopep8_runner.ebnf_grammar()[\"<option>\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "... we thus need 812 tests to cover all pairs:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "len(autopep8_runner.ebnf_grammar()[\"<option>\"]) * \\\n",
    "    (len(autopep8_runner.ebnf_grammar()[\"<option>\"]) - 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "For `mypy` with its 110 options, though, we already end up with 11,990 tests to be conducted:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "len(mypy_runner.ebnf_grammar()[\"<option>\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "len(mypy_runner.ebnf_grammar()[\"<option>\"]) * \\\n",
    "    (len(mypy_runner.ebnf_grammar()[\"<option>\"]) - 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Even if each pair takes a second to run, we'd still be done in three hours of testing, though."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "If your program has more options that you all want to get covered in combinations, it is advisable that you limit the number of configurations further – for instance by limiting combinatorial testing to those combinations that possibly can interact with each other; and covering all other (presumably orthogonal) options individually."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "This mechanism of creating configurations by extending grammars can be easily extended to other configuration targets.  One may want to explore a greater number of configurations, or expansions in specific contexts.  The [exercises](#Exercises), below, have a number of options ready for you."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": true,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Lessons Learned\n",
    "\n",
    "* Besides regular input data, program _configurations_ make an important testing target.\n",
    "* For a given program using a standard library to parse command-line options and arguments, one can automatically extract these and convert them into a grammar.\n",
    "* To cover not only single options, but combinations of options, one can expand the grammar to cover all pairs, or come up with even more ambitious targets."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "## Next Steps\n",
    "\n",
    "If you liked the idea of mining a grammar from a program, do not miss:\n",
    "\n",
    "* [how to mine grammars for input data](GrammarMiner.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Our next steps in the book focus on:\n",
    "\n",
    "* [how to parse and recombine inputs](Parser.ipynb)\n",
    "* [how to assign weights and probabilities to specific productions](ProbabilisticGrammarFuzzer.ipynb)\n",
    "* [how to simplify inputs that cause a failure](Reducer.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Background\n",
    "\n",
    "Although configuration data is just as likely to cause failures as other input data, it has received relatively little attention in test generation – possibly because, unlike \"regular\" input data, configuration data is not so much under control of external parties, and because, again unlike regular data, there is little variance in configurations.  Creating models for software configurations and using these models for testing is commonplace, as is the idea of pairwise testing.  For an overview, see \\cite{Pezze2008}; for a discussion and comparison of state-of-the-art techniques, see \\cite{Petke2015}.\n",
    "\n",
    "More specifically, \\cite{Sutton2007} also discuss techniques to systematically cover command-line options.  Dai et al. \\cite{Dai2010} apply configuration fuzzing by changing variables associated with configuration files.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "subslide"
    },
    "toc-hr-collapsed": false
   },
   "source": [
    "## Exercises"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    },
    "toc-hr-collapsed": true
   },
   "source": [
    "### Exercise 1: #ifdef Configuration Fuzzing\n",
    "\n",
    "In C programs, the *C preprocessor* can be used to choose which code parts should be compiled and which ones should not.  As an example, in the C code\n",
    "\n",
    "```C\n",
    "#ifdef LONG_FOO\n",
    "long foo() { ... }\n",
    "#else\n",
    "int foo() { ... }\n",
    "#endif\n",
    "```\n",
    "\n",
    "the compiler will compile the function `foo()` with return type`long` if the _preprocessor variable_ `LONG_FOO` is defined, and with return type `int` if not.  Such preprocessor variables are either set in the source files (using `#define`, as in `#define LONG_FOO`) or on the C compiler command line (using `-D<variable>` or `-D<variable>=<value>`, as in `-DLONG_FOO`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Such *conditional compilation* is used to configure C programs towards their environment.  System-specific code can contain lots of conditional compilation.  As an example, consider this excerpt of `xmlparse.c`, the XML parser that is part of the Python runtime library:\n",
    "\n",
    "```c\n",
    "#if defined(_WIN32) && !defined(LOAD_LIBRARY_SEARCH_SYSTEM32)\n",
    "# define LOAD_LIBRARY_SEARCH_SYSTEM32  0x00000800\n",
    "#endif\n",
    "\n",
    "#if !defined(HAVE_GETRANDOM) && !defined(HAVE_SYSCALL_GETRANDOM) \\\n",
    "    && !defined(HAVE_ARC4RANDOM_BUF) && !defined(HAVE_ARC4RANDOM) \\\n",
    "    && !defined(XML_DEV_URANDOM) \\\n",
    "    && !defined(_WIN32) \\\n",
    "    && !defined(XML_POOR_ENTROPY)\n",
    "# error\n",
    "#endif\n",
    "\n",
    "#if !defined(TIOCSWINSZ) || defined(__SCO__) || defined(__UNIXWARE__)\n",
    "#define USE_SYSV_ENVVARS\t/* COLUMNS/LINES vs. TERMCAP */\n",
    "#endif\n",
    "\n",
    "#ifdef XML_UNICODE_WCHAR_T\n",
    "#define XML_T(x) (const wchar_t)x\n",
    "#define XML_L(x) L ## x\n",
    "#else\n",
    "#define XML_T(x) (const unsigned short)x\n",
    "#define XML_L(x) x\n",
    "#endif\n",
    "\n",
    "int fun(int x) { return XML_T(x); }\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "A typical configuration for the C preprocessor on the above code could be `cc -c -D_WIN32 -DXML_POOR_ENTROPY -DXML_UNICODE_WCHAR_T xmlparse.c`, defining the given preprocessor variables and selecting the appropriate code fragments."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Since the compiler can only compile one configuration at a time (implying that we can also only _test_ one resulting executable at a time), your task is to find out which of these configurations actually compile.  To this end, proceed in three steps."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Part 1: Extract Preprocessor Variables\n",
    "\n",
    "Write a _function_ `cpp_identifiers()` that, given a set of lines (say, from `open(filename).readlines()`), extracts all preprocessor variables referenced in `#if` or `#ifdef` preprocessor instructions.  Apply `ifdef_identifiers()` on the sample C input above, such that\n",
    "\n",
    "```python\n",
    "cpp_identifiers(open(\"xmlparse.c\").readlines()) \n",
    "```\n",
    "\n",
    "returns the set\n",
    "\n",
    "```python\n",
    "{'_WIN32', 'LOAD_LIBRARY_SEARCH_SYSTEM32', 'HAVE_GETRANDOM', 'HAVE_SYSCALL_GETRANDOM', 'HAVE_ARC4RANDOM_BUF', ...}\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "**Solution.**  Let us start with creating a sample input file, `xmlparse.c`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "filename = \"xmlparse.c\"\n",
    "\n",
    "open(filename, \"w\").write(\n",
    "    \"\"\"\n",
    "#if defined(_WIN32) && !defined(LOAD_LIBRARY_SEARCH_SYSTEM32)\n",
    "# define LOAD_LIBRARY_SEARCH_SYSTEM32  0x00000800\n",
    "#endif\n",
    "\n",
    "#if !defined(HAVE_GETRANDOM) && !defined(HAVE_SYSCALL_GETRANDOM) \\\n",
    "    && !defined(HAVE_ARC4RANDOM_BUF) && !defined(HAVE_ARC4RANDOM) \\\n",
    "    && !defined(XML_DEV_URANDOM) \\\n",
    "    && !defined(_WIN32) \\\n",
    "    && !defined(XML_POOR_ENTROPY)\n",
    "# error\n",
    "#endif\n",
    "\n",
    "#if !defined(TIOCSWINSZ) || defined(__SCO__) || defined(__UNIXWARE__)\n",
    "#define USE_SYSV_ENVVARS\t/* COLUMNS/LINES vs. TERMCAP */\n",
    "#endif\n",
    "\n",
    "#ifdef XML_UNICODE_WCHAR_T\n",
    "#define XML_T(x) (const wchar_t)x\n",
    "#define XML_L(x) L ## x\n",
    "#else\n",
    "#define XML_T(x) (const unsigned short)x\n",
    "#define XML_L(x) x\n",
    "#endif\n",
    "\n",
    "int fun(int x) { return XML_T(x); }\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "To find C preprocessor `#if` directives and preprocessor variables, we use regular expressions matching them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "re_cpp_if_directive = re.compile(r\"\\s*#\\s*(el)?if\")\n",
    "re_cpp_identifier = re.compile(r\"[a-zA-Z_$]+\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "def cpp_identifiers(lines):\n",
    "    identifiers = set()\n",
    "    for line in lines:\n",
    "        if re_cpp_if_directive.match(line):\n",
    "            identifiers |= set(re_cpp_identifier.findall(line))\n",
    "\n",
    "    # These are preprocessor keywords\n",
    "    identifiers -= {\"if\", \"ifdef\", \"ifndef\", \"defined\"}\n",
    "    return identifiers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "cpp_ids = cpp_identifiers(open(\"xmlparse.c\").readlines())\n",
    "cpp_ids"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Part 2: Derive an Option Grammar\n",
    "\n",
    "With the help of `cpp_identifiers()`, create a grammar which has C compiler invocations with a list of options, where each option takes the form `-D<variable>` for a preprocessor variable `<variable>`.  Using this grammar `cpp_grammar`, a fuzzer \n",
    "\n",
    "```python\n",
    "g = GrammarCoverageFuzzer(cpp_grammar)\n",
    "```\n",
    "\n",
    "would create C compiler invocations such as\n",
    "\n",
    "```python\n",
    "[g.fuzz() for i in range(10)]\n",
    "['cc -DHAVE_SYSCALL_GETRANDOM xmlparse.c',\n",
    " 'cc -D__SCO__ -DRANDOM_BUF -DXML_UNICODE_WCHAR_T -D__UNIXWARE__ xmlparse.c',\n",
    " 'cc -DXML_POOR_ENTROPY xmlparse.c',\n",
    " 'cc -DRANDOM xmlparse.c',\n",
    " 'cc -D_WIN xmlparse.c',\n",
    " 'cc -DHAVE_ARC xmlparse.c', ...]\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "**Solution.** This is not very difficult:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from Grammars import new_symbol"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "cpp_grammar = {\n",
    "    \"<start>\": [\"cc -c<options> \" + filename],\n",
    "    \"<options>\": [\"<option>\", \"<options><option>\"],\n",
    "    \"<option>\": []\n",
    "}\n",
    "for id in cpp_ids:\n",
    "    s = new_symbol(cpp_grammar, \"<\" + id + \">\")\n",
    "    cpp_grammar[\"<option>\"].append(s)\n",
    "    cpp_grammar[s] = [\" -D\" + id]\n",
    "\n",
    "cpp_grammar"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "assert is_valid_grammar(cpp_grammar)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Part 3: C Preprocessor Configuration Fuzzing\n",
    "\n",
    "Using the grammar just produced, use a `GrammarCoverageFuzzer` to\n",
    "\n",
    "1. Test each processor variable individually\n",
    "2. Test each pair of processor variables, using `pairwise()`.\n",
    "\n",
    "What happens if you actually run the invocations?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "**Solution.** We can simply run the coverage fuzzer, as described above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "g = GrammarCoverageFuzzer(cpp_grammar)\n",
    "g.fuzz()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from Fuzzer import ProgramRunner"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(10):\n",
    "    invocation = g.fuzz()\n",
    "    print(\"$\", invocation)\n",
    "    # subprocess.call(invocation, shell=True)\n",
    "    cc_runner = ProgramRunner(invocation.split(' '))\n",
    "    (result, outcome) = cc_runner.run()\n",
    "    print(result.stderr, end=\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To test all pairs, we can use `pairwise()`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pairwise_cpp_grammar = extend_grammar(cpp_grammar)\n",
    "pairwise_cpp_grammar[\"<option>\"] = pairwise(cpp_grammar[\"<option>\"])\n",
    "pairwise_cpp_grammar[\"<option>\"][:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(10):\n",
    "    invocation = g.fuzz()\n",
    "    print(\"$\", invocation)\n",
    "    # subprocess.call(invocation, shell=True)\n",
    "    cc_runner = ProgramRunner(invocation.split(' '))\n",
    "    (result, outcome) = cc_runner.run()\n",
    "    print(result.stderr, end=\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Some of the compilation errors we get could be expected – for instance, defining `XML_UNICODE_WCHAR_T` when actually, the type is not supported in our environment.  Other errors may not be expected – and it is these errors we would find through systematic configuration fuzzing, as described above."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "At the end, don't forget to clean up:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    },
    "solution2": "hidden",
    "solution2_first": true
   },
   "outputs": [],
   "source": [
    "os.remove(\"xmlparse.c\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    },
    "solution2": "hidden",
    "solution2_first": true
   },
   "outputs": [],
   "source": [
    "if os.path.exists(\"xmlparse.o\"):\n",
    "    os.remove(\"xmlparse.o\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "subslide"
    },
    "toc-hr-collapsed": true
   },
   "source": [
    "### Exercise 2: .ini Configuration Fuzzing\n",
    "\n",
    "Besides command-line options, another important source of configurations are _configuration files_.  In this exercise, we will consider the very simple configuration language provided by the Python `ConfigParser` module, which is very similar to what is found in Microsoft Windows _.ini_ files."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The following example for a `ConfigParser` input file stems right from [the ConfigParser documentation](https://docs.python.org/3/library/configparser.html):\n",
    "```\n",
    "[DEFAULT]\n",
    "ServerAliveInterval = 45\n",
    "Compression = yes\n",
    "CompressionLevel = 9\n",
    "ForwardX11 = yes\n",
    "\n",
    "[bitbucket.org]\n",
    "User = hg\n",
    "\n",
    "[topsecret.server.com]\n",
    "Port = 50022\n",
    "ForwardX11 = no\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The above `ConfigParser` file can be created programmatically:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import configparser"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "config = configparser.ConfigParser()\n",
    "config['DEFAULT'] = {'ServerAliveInterval': '45',\n",
    "                     'Compression': 'yes',\n",
    "                     'CompressionLevel': '9'}\n",
    "config['bitbucket.org'] = {}\n",
    "config['bitbucket.org']['User'] = 'hg'\n",
    "config['topsecret.server.com'] = {}\n",
    "topsecret = config['topsecret.server.com']\n",
    "topsecret['Port'] = '50022'     # mutates the parser\n",
    "topsecret['ForwardX11'] = 'no'  # same here\n",
    "config['DEFAULT']['ForwardX11'] = 'yes'\n",
    "with open('example.ini', 'w') as configfile:\n",
    "    config.write(configfile)\n",
    "\n",
    "with open('example.ini') as configfile:\n",
    "    print(configfile.read(), end=\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "and be read in again:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "center",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "config = configparser.ConfigParser()\n",
    "config.read('example.ini')\n",
    "topsecret = config['topsecret.server.com']\n",
    "topsecret['Port']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Part 1: Read Configuration\n",
    "\n",
    "Using `configparser`, create a program reading in the above configuration file and accessing the individual elements."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Part 2: Create a Configuration Grammar\n",
    "\n",
    "Design a grammar that will automatically create configuration files suitable for your above program.  Fuzz your program with it."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Part 3: Mine a Configuration Grammar\n",
    "\n",
    "By dynamically tracking the individual accesses to configuration elements, you can again extract a basic grammar from the execution.  To this end, create a subclass of `ConfigParser` with a special method `__getitem__`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "solution2": "hidden",
    "solution2_first": true
   },
   "outputs": [],
   "source": [
    "class TrackingConfigParser(configparser.ConfigParser):\n",
    "    def __getitem__(self, key):\n",
    "        print(\"Accessing\", repr(key))\n",
    "        return super().__getitem__(key)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "For a `TrackingConfigParser` object `p`, `p.__getitem__(key)` will be invoked whenever `p[key]` is accessed:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "tracking_config_parser = TrackingConfigParser()\n",
    "tracking_config_parser.read('example.ini')\n",
    "section = tracking_config_parser['topsecret.server.com']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Using `__getitem__()`, as above, implement a tracking mechanism that, while your program accesses the read configuration, automatically saves options accessed and values read.  Create a prototype grammar from these values; use it for fuzzing."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "At the end, don't forget to clean up:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import os"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    },
    "solution2": "hidden",
    "solution2_first": true
   },
   "outputs": [],
   "source": [
    "os.remove(\"example.ini\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    },
    "solution2": "hidden"
   },
   "source": [
    "**Solution.** Left to the reader.  Enjoy!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "subslide"
    },
    "toc-hr-collapsed": true
   },
   "source": [
    "### Exercise 3: Extracting and Fuzzing C Command-Line Options\n",
    "\n",
    "In C programs, the `getopt()` function are frequently used to process configuration options.  A call\n",
    "\n",
    "```\n",
    "getopt(argc, argv, \"bf:\")\n",
    "```\n",
    "\n",
    "indicates that the program accepts two options `-b` and `-f`, with `-f` taking an argument (as indicated by the following colon)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "center",
    "slideshow": {
     "slide_type": "subslide"
    },
    "solution2": "hidden",
    "solution2_first": true
   },
   "source": [
    "#### Part 1: Getopt Fuzzing\n",
    "\n",
    "Write a framework which, for a given C program, automatically extracts the argument to `getopt()` and derives a fuzzing grammar for it.  There are multiple ways to achieve this:\n",
    "\n",
    "1. Scan the program source code for occurrences of `getopt()` and return the string passed.  (Crude, but should frequently work.)\n",
    "2. Insert your own implementation of `getopt()` into the source code (effectively replacing `getopt()` from the runtime library), which outputs the `getopt()` argument and exits the program.  Recompile and run.\n",
    "3. (Advanced.) As above, but instead of changing the source code, hook into the _dynamic linker_ which at runtime links the program with the C runtime library.  Set the library loading path (on Linux and Unix, this is the `LD_LIBRARY_PATH` environment variable) such that your own version of `getopt()` is linked first, and the regular libraries later.  Executing the program (without recompiling) should yield the desired result.\n",
    "\n",
    "Apply this on `grep` and `ls`; report the resulting grammars and results."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    },
    "solution2": "hidden"
   },
   "source": [
    "**Solution.** Left to the reader.  Enjoy hacking!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    },
    "solution2": "hidden",
    "solution2_first": true
   },
   "source": [
    "#### Part 2: Fuzzing Long Options in C\n",
    "\n",
    "Same as Part 1, but also hook into the GNU variant `getopt_long()`, which accepts \"long\" arguments with double dashes such as `--help`.  Note that method 1, above, will not work here, since the \"long\" options are defined in a separately defined structure."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    },
    "solution2": "hidden"
   },
   "source": [
    "**Solution.** Left to the reader.  Enjoy hacking!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Exercise 4: Expansions in Context\n",
    "\n",
    "In our above option configurations, we have multiple symbols which all expand to the same integer.  For instance, the `--line-range` option of `autopep8` takes two `<line>` parameters which both expand into the same `<int>` symbol:\n",
    "\n",
    "```\n",
    "<option> ::= ... | --line-range <line> <line> | ...\n",
    "<line> ::= <int>\n",
    "<int> ::= (-)?<digit>+\n",
    "<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "center",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "autopep8_runner.ebnf_grammar()[\"<line>\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "center",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "autopep8_runner.ebnf_grammar()[\"<int>\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "autopep8_runner.ebnf_grammar()[\"<digit>\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Once the `GrammarCoverageFuzzer` has covered all variations of `<int>` (especially by covering all digits) for _one_ option, though, it will no longer strive to achieve such coverage for the next option.  Yet, it could be desirable to achieve such coverage for each option separately."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "One way to achieve this with our existing `GrammarCoverageFuzzer` is again to change the grammar accordingly.  The idea is to _duplicate_ expansions – that is, to replace an expansion of a symbol $s$ with a new symbol $s'$ whose definition is duplicated from $s$.  This way, $s'$ and $s$ are separate symbols from a coverage point of view and would be independently covered."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "As an example, consider again the above `--line-range` option.  If we want our tests to independently cover all elements of the two `<line>` parameters, we can duplicate the second `<line>` expansion into a new symbol `<line'>` with subsequent duplicated expansions:\n",
    "```\n",
    "<option> ::= ... | --line-range <line> <line'> | ...\n",
    "<line> ::= <int>\n",
    "<line'> ::= <int'>\n",
    "<int> ::= (-)?<digit>+\n",
    "<int'> ::= (-)?<digit'>+\n",
    "<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9\n",
    "<digit'> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Design a function `inline(grammar, symbol)` that returns a duplicate of `grammar` in which every occurrence of `<symbol>` and its expansions become separate copies.  The above grammar could be a result of `inline(autopep8_runner.ebnf_grammar(), \"<line>\")`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "When copying, expansions in the copy should also refer to symbols in the copy.  Hence, when expanding `<int>` in\n",
    "\n",
    "```<int> ::= <int><digit>```\n",
    "\n",
    "make that\n",
    "\n",
    "```<int> ::= <int><digit>\n",
    "<int'> ::= <int'><digit'>\n",
    "```\n",
    "\n",
    "(and not `<int'> ::= <int><digit'>` or `<int'> ::= <int><digit>`)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    },
    "solution2": "hidden",
    "solution2_first": true
   },
   "source": [
    "Be sure to add precisely one new set of symbols for each occurrence in the original grammar, and not to expand further in the presence of recursion."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    },
    "solution2": "hidden"
   },
   "source": [
    "**Solution.** Again, left to the reader.  Enjoy!"
   ]
  }
 ],
 "metadata": {
  "ipub": {
   "bibliography": "fuzzingbook.bib",
   "toc": true
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": true
  },
  "toc-autonumbering": false
 },
 "nbformat": 4,
 "nbformat_minor": 2
}