notebooks/Reducer.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "# Reducing Failure-Inducing Inputs\n",
    "\n",
    "By construction, fuzzers create inputs that may be hard to read.  This causes issues during _debugging_, when a human has to analyze the exact cause of the failure.  In this chapter, we present techniques that _automatically reduce and simplify failure-inducing inputs to a minimum_ in order to ease debugging."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "**Prerequisites**\n",
    "\n",
    "* The simple \"delta debugging\" technique for reduction has no specific prerequisites.\n",
    "* As reduction is typically used together with fuzzing, reading the [chapter on basic fuzzing](Fuzzer.ipynb) is a good idea.\n",
    "* The later grammar-based techniques require knowledge on [derivation trees](GrammarFuzzer.ipynb) and [parsing](Parser.ipynb)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": true,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "## Why Reducing?\n",
    "\n",
    "At this point, we have seen a number of test generation techniques that all in some form produce inputs in order to trigger failures.  If they are successful – that is, the program actually fails – we must find out why the failure occurred and how to fix it."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": true,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "Here's an example of such a situation.  We have a class `MysteryRunner` class with a `run()` method that – given its code – can occasionally fail.  But under which circumstances does this actually happen?  We have deliberately obscured the exact condition in order to make this non-obvious."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import fuzzingbook_utils"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from Fuzzer import RandomFuzzer, Runner"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MysteryRunner(Runner):\n",
    "    def run(self, inp):\n",
    "        x = inp.find(chr(0o17 + 0o31))\n",
    "        y = inp.find(chr(0o27 + 0o22))\n",
    "        if x >= 0 and y >= 0 and x < y:\n",
    "            return (inp, Runner.FAIL)\n",
    "        else:\n",
    "            return (inp, Runner.PASS)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us fuzz the function until we find a failing input."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mystery = MysteryRunner()\n",
    "random_fuzzer = RandomFuzzer()\n",
    "while True:\n",
    "    inp = random_fuzzer.fuzz()\n",
    "    result, outcome = mystery.run(inp)\n",
    "    if outcome == mystery.FAIL:\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "failing_input = result\n",
    "failing_input"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Something in this input causes `MysteryRunner` to fail.  But what is it?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": true,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "## Manual Input Reduction\n",
    "\n",
    "One important step in the debugging process is _reduction_ – that is, to identify those circumstances of a failure that are relevant for the failure to occur, and to _omit_ (if possible) those parts that are not.  As Kernighan and Pike \\cite{Kernighan1999} put it:\n",
    "\n",
    "> For every circumstance of the problem, check whether it is relevant for the problem to occur.  If it is not, remove it from the problem report or the test case in question."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Specifically for inputs, they suggest a _divide and conquer_ process:\n",
    "\n",
    "> Proceed by binary search.  Throw away half the input and see if the output is still wrong; if not, go back to the previous state and discard the other half of the input.\n",
    "\n",
    "This is something we can easily try out.  For instance, we can see whether the error still occurs if we only feed in the first half:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "half_length = len(failing_input) // 2   # // is integer division\n",
    "first_half = failing_input[:half_length]\n",
    "mystery.run(first_half)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nope – the first half alone does not suffice.  Maybe the second half?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "second_half = failing_input[half_length:]\n",
    "mystery.run(second_half)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This did not go so well either.  We may still proceed by cutting away _smaller chunks_ – say, one character after another.  If our test is deterministic and easily repeated, it is clear that this process eventually will yield a reduced input.  But still, it is a rather inefficient process, especially for long inputs.  What we need is a _strategy_ that effectively minimizes a failure-inducing input – a strategy that can be automated."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Delta Debugging"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One strategy to effectively reduce failure-inducing inputs is _delta debugging_ \\cite{Zeller2002}.  Delta Debugging implements the \"binary search\" strategy, as listed above, but with a twist: If neither half fails (also as above), it keeps on cutting away smaller and smaller chunks from the input, until it eliminates individual characters.  Thus, after cutting away the first half, we cut away\n",
    "the first quarter, the second quarter, and so on."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us illustrate this on our example, and see what happens if we cut away the first quarter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "quarter_length = len(failing_input) // 4\n",
    "input_without_first_quarter = failing_input[quarter_length:]\n",
    "mystery.run(input_without_first_quarter)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ah! This has failed, and reduced our failing input by 25%.  Let's remove another quarter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "input_without_first_and_second_quarter = failing_input[quarter_length * 2:]\n",
    "mystery.run(input_without_first_and_second_quarter)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is not too surprising, as we had that one before:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "second_half"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "input_without_first_and_second_quarter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How about removing the third quarter, then?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "input_without_first_and_third_quarter = failing_input[quarter_length:\n",
    "                                                      quarter_length * 2] + failing_input[quarter_length * 3:]\n",
    "mystery.run(input_without_first_and_third_quarter)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ok.  Let us remove the fourth quarter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "input_without_first_and_fourth_quarter = failing_input[quarter_length:quarter_length * 3]\n",
    "mystery.run(input_without_first_and_fourth_quarter)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Yes!  This has succeeded.  Our input is now 50% smaller."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have now tried to remove pieces that make up $\\frac{1}{2}$ and $\\frac{1}{4}$ of the original failing string.  In the next iteration, we would go and remove even smaller pieces – $\\frac{1}{8}$, $\\frac{1}{16}$ and so on.  We continue until we are down to $\\frac{1}{97}$ – that is, individual characters."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "However, this is comething we happily let a computer do for us.  We first introduce a `Reducer` class as an abstract superclass for all kinds of reducers.  The `test()` methods runs a single test (with logging, if so wanted); the `reduce()` method will eventually reduce an input to the minimum."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Reducer(object):\n",
    "    def __init__(self, runner, log_test=False):\n",
    "        \"\"\"Attach reducer to the given `runner`\"\"\"\n",
    "        self.runner = runner\n",
    "        self.log_test = log_test\n",
    "        self.reset()\n",
    "\n",
    "    def reset(self):\n",
    "        self.tests = 0\n",
    "\n",
    "    def test(self, inp):\n",
    "        result, outcome = self.runner.run(inp)\n",
    "        self.tests += 1\n",
    "        if self.log_test:\n",
    "            print(\"Test #%d\" % self.tests, repr(inp), repr(len(inp)), outcome)\n",
    "        return outcome\n",
    "\n",
    "    def reduce(self, inp):\n",
    "        self.reset()\n",
    "        # Default: Don't reduce\n",
    "        return inp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `CachingReducer` variant saves test results, such that we don't have to run the same tests again and again:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class CachingReducer(Reducer):\n",
    "    def reset(self):\n",
    "        super().reset()\n",
    "        self.cache = {}\n",
    "\n",
    "    def test(self, inp):\n",
    "        if inp in self.cache:\n",
    "            return self.cache[inp]\n",
    "\n",
    "        outcome = super().test(inp)\n",
    "        self.cache[inp] = outcome\n",
    "        return outcome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here comes the _Delta Debugging_ reducer.  Delta Debugging implements the strategy sketched above: It first removes larger chunks of size $\\frac{1}{2}$; if this does not fail, then we proceed to chunks of size $\\frac{1}{4}$, then $\\frac{1}{8}$ and so on."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our implementation uses almost the same Python code as Zeller in \\cite{Zeller2002}; the only difference is that it has been adapted to work on Python 3 and our `Runner` framework.    The variable `n` (initially 2) indicates the granularity – in each step, chunks of size $\\frac{1}{n}$ are cut away.  If none of the test fails (`some_complement_is_failing` is False), then `n` is doubled – until it reaches the length of the input."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DeltaDebuggingReducer(CachingReducer):\n",
    "    def reduce(self, inp):\n",
    "        self.reset()\n",
    "        assert self.test(inp) != Runner.PASS\n",
    "\n",
    "        n = 2     # Initial granularity\n",
    "        while len(inp) >= 2:\n",
    "            start = 0\n",
    "            subset_length = len(inp) / n\n",
    "            some_complement_is_failing = False\n",
    "\n",
    "            while start < len(inp):\n",
    "                complement = inp[:int(start)] + \\\n",
    "                    inp[int(start + subset_length):]\n",
    "\n",
    "                if self.test(complement) == Runner.FAIL:\n",
    "                    inp = complement\n",
    "                    n = max(n - 1, 2)\n",
    "                    some_complement_is_failing = True\n",
    "                    break\n",
    "\n",
    "                start += subset_length\n",
    "\n",
    "            if not some_complement_is_failing:\n",
    "                if n == len(inp):\n",
    "                    break\n",
    "                n = min(n * 2, len(inp))\n",
    "\n",
    "        return inp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To see how the `DeltaDebuggingReducer` works, let us run it on our failing input.  With each step, we see how the remaining input gets smaller and smaller, until only three characters remain:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dd_reducer = DeltaDebuggingReducer(mystery, log_test=True)\n",
    "dd_reducer.reduce(failing_input)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we know why `MysteryRunner` fails – it suffices that the input contains two matching parentheses with a number between them.  Delta Debugging determines this is 29 steps.  Its result is _1-minimal_, meaning that every character contained is required to produce the error; removing any (as seen in tests `#27` and `#29`, above) no longer makes the test fail.  This property is guaranteed by the delta debugging algorithm, which in its last stage always tries to delete characters one by one."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": true,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "A reduced test case such as the one above has many advantages:\n",
    "\n",
    "* A reduced test case __reduces the _cognitive load_ of the programmer__.  The test case is shorter and focused, and thus does not burden the programmer with irrelevant details.  A reduced input typically leads to shorter executions and smaller program states, both of which reduce the search space as it comes to understanding the bug.  In our case, we have eliminated lots of irrelevant input – only the two characters the reduced input contains are relevant.\n",
    "\n",
    "* A reduced test case __is easier to communicate__.  All one needs here is the summary: `MysteryRunner fails on \"()\"`, which is much better than `MysteryRunner fails on a 4100-character input (attached)`.\n",
    "\n",
    "* A reduced test case helps in __identifying duplicates__.  If similar bugs have been reported already, and all of them have been reduced to the same cause (namely that the input contains matching parentheses), then it becomes obvious that all these bugs are different symptoms of the same underlying cause – and would all be resolved at once with one code fix."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How effective is delta debugging?  In the best case (when the left half or the right half fails), the number of tests is logarithmic proportional to the length $n$ of an input (i.e., $O(\\log_2 n)$); this is the same complexity as binary search.  In the worst case, though, delta debugging can require a number of tests proportional to $n^2$  (i.e., $O(n^2)$) – this happens in the case when we are down to character granularity, and we have to repeatedly tried to delete all characters, only to find that deleting the last character results in a failure \\cite{Zeller2002}.  (This is a pretty pathological situation, though.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In general, delta debugging is a robust algorithm that is easy to implement, easy to deploy, and easy to use – provided that the underlying test case is deterministic and runs quickly enough to warrant a number of experiments.  As these are the same prerequisites that make fuzzing effective, delta debugging makes an excellent companion to fuzzing."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "subslide"
    },
    "toc-hr-collapsed": false
   },
   "source": [
    "## Grammar-Based Input Reduction\n",
    "\n",
    "If the input language is syntactically complex, delta debugging may take several attempts at reduction, and may not be able to reduce inputs at all.  In the second half of this chapter, we thus introduce an algorithm named _Grammar-Based Reduction_ (or GRABR for short) that makes use of _grammars_ to reduce syntactically complex inputs."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Lexical Reduction vs. Syntactic Rules\n",
    "\n",
    "Despite its general robustness, there are situations in which delta debugging might be inefficient or outright fail.  As an example, consider some _expression input_ such as `1 + (2 * 3)`.  Delta debugging requires a number of tests to simplify the failure-inducing input, but it eventually returns a minimal input"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "expr_input = \"1 + (2 * 3)\"\n",
    "dd_reducer = DeltaDebuggingReducer(mystery, log_test=True)\n",
    "dd_reducer.reduce(expr_input)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Looking at the tests, above, though, only few of them actually represent syntactically valid arithmetic expressions.  In a practical setting, we may want to test a program which actually _parses_ such expressions, and which would _reject_ all invalid inputs.  We define a class `EvalMysteryRunner` which first _parses_ the given input (according to the rules of our expression grammar), and _only_ if it fits would it be passed to our original `MysteryRunner`.  This simulates a setting in which we test an expression interpreter, and in which only valid inputs can trigger the bug."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from Grammars import EXPR_GRAMMAR"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from Parser import EarleyParser  # minor dependency"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class EvalMysteryRunner(MysteryRunner):\n",
    "    def __init__(self):\n",
    "        self.parser = EarleyParser(EXPR_GRAMMAR)\n",
    "\n",
    "    def run(self, inp):\n",
    "        try:\n",
    "            tree = self.parser.parse(inp)[0]\n",
    "        except SyntaxError as exc:\n",
    "            return (inp, Runner.UNRESOLVED)\n",
    "\n",
    "        return super().run(inp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "eval_mystery = EvalMysteryRunner()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Under these circumstances, it turns out that delta debugging utterly fails.  None of the reductions it applies yield a syntactically valid input, so the input as a whole remains as complex as it was before."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dd_reducer = DeltaDebuggingReducer(eval_mystery, log_test=True)\n",
    "dd_reducer.reduce(expr_input)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This behavior is possible if the program under test has several constraints regarding input validity.  Delta debugging is not aware of these constraints (nor of the input structure in general), so it might violate these constraints again and again."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### A Grammmar-Based Reduction Approach\n",
    "\n",
    "To reduce inputs with high syntactical complexity, we use another approach: Rather than reducing the input string, we reduce the _tree_ representing its structure.  The general idea is to start with a _derivation tree_ coming from parsing the input, and then _substitute subtrees by smaller subtrees of the same type_.  These alternate subtrees can either come\n",
    "\n",
    "1. From the tree itself, or\n",
    "2. By applying an alternate grammar expansion using elements from the tree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Let us show these two strategies using an example.  We start with a derivation tree from an arithmetic expression:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from GrammarFuzzer import all_terminals, expansion_to_children, display_tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "derivation_tree = EarleyParser(EXPR_GRAMMAR).parse(expr_input)[0]\n",
    "display_tree(derivation_tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Simplifying by Replacing Subtrees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To simplify this tree, we could replace any `<expr>` symbol up in the tree with some `<expr>` subtree down in the tree.  For instance, we could replace the uppermost `<expr>` with its right `<expr>` subtree, yielding the string `(2 + 3)`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import copy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "new_derivation_tree = copy.deepcopy(derivation_tree)\n",
    "# We really should have some query language\n",
    "sub_expr_tree = new_derivation_tree[1][0][1][2]\n",
    "display_tree(sub_expr_tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "new_derivation_tree[1][0] = sub_expr_tree\n",
    "display_tree(new_derivation_tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "all_terminals(new_derivation_tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Replacing one subtree by another only works as long as individual elements such as `<expr>` occur multiple times in our tree.  In the reduced `new_derivation_tree`, above, we could replace further `<expr>` trees only once more."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Simplifying by Alternative Expansions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A second means to simplify this tree is to apply _alternative expansions_.  That is, for a symbol, we check whether there is an alternative expansion with a smaller number of children.  Then, we replace the symbol with the alternative expansion, filling in needed symbols from the tree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As an example, consider the `new_derivation_tree` above.  The applied expansion for `<term>` has been\n",
    "\n",
    "    <term> ::= <term> * <factor>\n",
    "    \n",
    "Lat us replace this with the alternative expansion:\n",
    "\n",
    "    <term> ::= <factor>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "term_tree = new_derivation_tree[1][0][1][0][1][0][1][1][1][0]\n",
    "display_tree(term_tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "shorter_term_tree = term_tree[1][2]\n",
    "display_tree(shorter_term_tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "new_derivation_tree[1][0][1][0][1][0][1][1][1][0] = shorter_term_tree\n",
    "display_tree(new_derivation_tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "all_terminals(new_derivation_tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we replace derivation subtrees by (smaller) subtrees, and if we search for alternate expansions that again yield smaller subtrees, we can systematically simplify the input.  This could be much faster than delta debugging, as our inputs would always be syntactically valid.  However, we need a strategy for when to apply which simplification rule. This is what we develop in the remainder of this section."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### A Class for Reducing with Grammars\n",
    "\n",
    "We introduce the `GrammarReducer` class, which is again a `Reducer`.  Note that we derive from `CachingReducer`, as the strategy will produce several duplicates."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class GrammarReducer(CachingReducer):\n",
    "    def __init__(self, runner, parser, log_test=False, log_reduce=False):\n",
    "        super().__init__(runner, log_test=log_test)\n",
    "        self.parser = parser\n",
    "        self.grammar = parser.grammar()\n",
    "        self.start_symbol = parser.start_symbol()\n",
    "        self.log_reduce = log_reduce\n",
    "        self.try_all_combinations = False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### A Few Helpers\n",
    "\n",
    "We define a number of helper functions, which we will need for our strategy.  `tree_list_to_string()` does what the name suggest, creating a string from a list of derivation trees:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tree_list_to_string(q):\n",
    "    return \"[\" + \", \".join([all_terminals(tree) for tree in q]) + \"]\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree_list_to_string([derivation_tree, derivation_tree])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The function `possible_combinations()` takes a list of lists $[[x_1, x_2], [y_1, y_2], \\dots]$ and creates a list of combinations $[[x_1, y_1], [x_1, y_2], [x_2, y_1], [x_2, y_2], \\dots]$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def possible_combinations(list_of_lists):\n",
    "    if len(list_of_lists) == 0:\n",
    "        return []\n",
    "\n",
    "    ret = []\n",
    "    for e in list_of_lists[0]:\n",
    "        if len(list_of_lists) == 1:\n",
    "            ret.append([e])\n",
    "        else:\n",
    "            for c in possible_combinations(list_of_lists[1:]):\n",
    "                new_combo = [e] + c\n",
    "                ret.append(new_combo)\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "possible_combinations([[1, 2], ['a', 'b']])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The functions `number_of_nodes()` and `max_height()` return the number of nodes and the maximum height of the given tree, respectively."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def number_of_nodes(tree):\n",
    "    (symbol, children) = tree\n",
    "    return 1 + sum([number_of_nodes(c) for c in children])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "number_of_nodes(derivation_tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def max_height(tree):\n",
    "    (symbol, children) = tree\n",
    "    if len(children) == 0:\n",
    "        return 1\n",
    "    return 1 + max([max_height(c) for c in children])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "max_height(derivation_tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "toc-hr-collapsed": false
   },
   "source": [
    "### Simplification Strategies\n",
    "\n",
    "Let us now implement our two simplification strategies – replacing subtrees and alternate expansions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Finding Subtrees\n",
    "\n",
    "The method `subtrees_with_symbol()` returns all subtrees in the given tree whose root is equal to the given symbol.  If `ignore_root` is set (default), then the root node of `tree` is not compared against.  (The `depth` parameter will be discussed below.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class GrammarReducer(GrammarReducer):\n",
    "    def subtrees_with_symbol(self, tree, symbol, depth=-1, ignore_root=True):\n",
    "        # Find all subtrees in TREE whose root is SYMBOL.\n",
    "        # If IGNORE_ROOT is true, ignore the root note of TREE.\n",
    "\n",
    "        ret = []\n",
    "        (child_symbol, children) = tree\n",
    "        if depth <= 0 and not ignore_root and child_symbol == symbol:\n",
    "            ret.append(tree)\n",
    "\n",
    "        # Search across all children\n",
    "        if depth != 0 and children is not None:\n",
    "            for c in children:\n",
    "                ret += self.subtrees_with_symbol(c,\n",
    "                                                 symbol,\n",
    "                                                 depth=depth - 1,\n",
    "                                                 ignore_root=False)\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's an example: These are all subtrees with `<term>` in our derivation tree `derivation_tree`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "grammar_reducer = GrammarReducer(\n",
    "    mystery,\n",
    "    EarleyParser(EXPR_GRAMMAR),\n",
    "    log_reduce=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "all_terminals(derivation_tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[all_terminals(t) for t in grammar_reducer.subtrees_with_symbol(\n",
    "    derivation_tree, \"<term>\")]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we want to replace `<term>` subtrees to simplify the tree, these are the subtrees we could replace them with."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Alternate Expansions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our second strategy, simplifying by alternate expansions, is a bit more complex.  We first fetch the possible expansions for the given symbol (starting with the ones with the fewest children).  For each expansion, we fill in values for the symbols from the subtree (using `subtrees_with_symbols()`, above).  We then pick the first possible combination (or _all_ combinations, if the attribute `try_all_combinations` is set)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class GrammarReducer(GrammarReducer):\n",
    "    def alternate_reductions(self, tree, symbol, depth=-1):\n",
    "        reductions = []\n",
    "\n",
    "        expansions = self.grammar.get(symbol, [])\n",
    "        expansions.sort(\n",
    "            key=lambda expansion: len(\n",
    "                expansion_to_children(expansion)))\n",
    "\n",
    "        for expansion in expansions:\n",
    "            expansion_children = expansion_to_children(expansion)\n",
    "\n",
    "            match = True\n",
    "            new_children_reductions = []\n",
    "            for (alt_symbol, _) in expansion_children:\n",
    "                child_reductions = self.subtrees_with_symbol(\n",
    "                    tree, alt_symbol, depth=depth)\n",
    "                if len(child_reductions) == 0:\n",
    "                    match = False   # Child not found; cannot apply rule\n",
    "                    break\n",
    "\n",
    "                new_children_reductions.append(child_reductions)\n",
    "\n",
    "            if not match:\n",
    "                continue  # Try next alternative\n",
    "\n",
    "            # Use the first suitable combination\n",
    "            for new_children in possible_combinations(new_children_reductions):\n",
    "                new_tree = (symbol, new_children)\n",
    "                if number_of_nodes(new_tree) < number_of_nodes(tree):\n",
    "                    reductions.append(new_tree)\n",
    "                    if not self.try_all_combinations:\n",
    "                        break\n",
    "\n",
    "        # Sort by number of nodes\n",
    "        reductions.sort(key=number_of_nodes)\n",
    "\n",
    "        return reductions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "grammar_reducer = GrammarReducer(\n",
    "    mystery,\n",
    "    EarleyParser(EXPR_GRAMMAR),\n",
    "    log_reduce=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "all_terminals(derivation_tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's _all_ combinations for `<term>`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "grammar_reducer.try_all_combinations = True\n",
    "print([all_terminals(t)\n",
    "       for t in grammar_reducer.alternate_reductions(derivation_tree, \"<term>\")])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The default, though, is simply to return the first of these:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "grammar_reducer.try_all_combinations = False\n",
    "[all_terminals(t) for t in grammar_reducer.alternate_reductions(\n",
    "    derivation_tree, \"<term>\")]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Both Strategies Together"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us now merge both strategies.  To replace a subtree with a given symbol, we first search for already existing subtrees (using `subtrees_with_symbol()`); then we go for alternate expansions (using `alternate_expansions()`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class GrammarReducer(GrammarReducer):\n",
    "    def symbol_reductions(self, tree, symbol, depth=-1):\n",
    "        \"\"\"Find all expansion alternatives for the given symbol\"\"\"\n",
    "        reductions = (self.subtrees_with_symbol(tree, symbol, depth=depth)\n",
    "                      + self.alternate_reductions(tree, symbol, depth=depth))\n",
    "\n",
    "        # Filter duplicates\n",
    "        unique_reductions = []\n",
    "        for r in reductions:\n",
    "            if r not in unique_reductions:\n",
    "                unique_reductions.append(r)\n",
    "\n",
    "        return unique_reductions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "grammar_reducer = GrammarReducer(\n",
    "    mystery,\n",
    "    EarleyParser(EXPR_GRAMMAR),\n",
    "    log_reduce=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "all_terminals(derivation_tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These are the possible reductions for `<expr>` nodes.  Note how we first return subtrees (`1 + (2 * 3)`, `(2 * 3)`, `2 * 3`) before going for alternate expansions of `<expr>` (`1`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "reductions = grammar_reducer.symbol_reductions(derivation_tree, \"<expr>\")\n",
    "tree_list_to_string([r for r in reductions])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These are the possible reductions for `<term>` nodes.  Again, we first have subtrees of the derivation tree, followed by the alternate expansion `1 * 1`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "reductions = grammar_reducer.symbol_reductions(derivation_tree, \"<term>\")\n",
    "tree_list_to_string([r for r in reductions])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Reduction Strategy\n",
    "\n",
    "We are now able to return a number of alternatives for each symbol in the tree.  This is what we apply in the core function of our reduction strategy, `reduce_subtree()`.  Starting with `subtree`, for every child, we find possible reductions.  For every reduction, we replace the child with the reduction and test the resulting (full) tree.  If it fails, our reduction was successful; otherwise, we put the child back into place and try out the next reduction.  Eventually, we apply `reduce_subtree()` on all children, reducing these as well."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class GrammarReducer(GrammarReducer):\n",
    "    def reduce_subtree(self, tree, subtree, depth=-1):\n",
    "        symbol, children = subtree\n",
    "        if len(children) == 0:\n",
    "            return False\n",
    "\n",
    "        if self.log_reduce:\n",
    "            print(\"Reducing\", all_terminals(subtree), \"with depth\", depth)\n",
    "\n",
    "        reduced = False\n",
    "        while True:\n",
    "            reduced_child = False\n",
    "            for i, child in enumerate(children):\n",
    "                (child_symbol, _) = child\n",
    "                for reduction in self.symbol_reductions(\n",
    "                        child, child_symbol, depth):\n",
    "                    if number_of_nodes(reduction) >= number_of_nodes(child):\n",
    "                        continue\n",
    "\n",
    "                    # Try this reduction\n",
    "                    if self.log_reduce:\n",
    "                        print(\n",
    "                            \"Replacing\",\n",
    "                            all_terminals(\n",
    "                                children[i]),\n",
    "                            \"by\",\n",
    "                            all_terminals(reduction))\n",
    "                    children[i] = reduction\n",
    "                    if self.test(all_terminals(tree)) == Runner.FAIL:\n",
    "                        # Success\n",
    "                        if self.log_reduce:\n",
    "                            print(\"New tree:\", all_terminals(tree))\n",
    "                        reduced = reduced_child = True\n",
    "                        break\n",
    "                    else:\n",
    "                        # Didn't work out - restore\n",
    "                        children[i] = child\n",
    "\n",
    "            if not reduced_child:\n",
    "                if self.log_reduce:\n",
    "                    print(\"Tried all alternatives for\", all_terminals(subtree))\n",
    "                break\n",
    "\n",
    "        # Run recursively\n",
    "        for c in children:\n",
    "            if self.reduce_subtree(tree, c, depth):\n",
    "                reduced = True\n",
    "\n",
    "        return reduced"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "All we now need is a few drivers.  The method `reduce_tree()` is the main entry point into `reduce_subtree()`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class GrammarReducer(GrammarReducer):\n",
    "    def reduce_tree(self, tree):\n",
    "        return self.reduce_subtree(tree, tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The custom method `parse()` turns a given input into a derivation tree:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class GrammarReducer(GrammarReducer):\n",
    "    def parse(self, inp):\n",
    "        tree = self.parser.parse(inp)[0]\n",
    "        if self.log_reduce:\n",
    "            print(all_terminals(tree))\n",
    "        return tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The method `reduce()` is the one single entry point, parsing the input and then reducing it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class GrammarReducer(GrammarReducer):\n",
    "    def reduce(self, inp):\n",
    "        tree = self.parse(inp)\n",
    "        self.reduce_tree(tree)\n",
    "        return all_terminals(tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us try this out in practice on our input `expr_input` and the `mystery()` function.  How quickly can we reduce it?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "expr_input"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "grammar_reducer = GrammarReducer(\n",
    "    eval_mystery,\n",
    "    EarleyParser(EXPR_GRAMMAR),\n",
    "    log_test=True)\n",
    "grammar_reducer.reduce(expr_input)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Success!  In only five steps, our `GrammarReducer` reduces the input to the minimum that causes the failure.  Note how all tests are syntactically valid by construction, avoiding the `UNRESOLVED` outcomes that cause delta debugging to stall."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### A Depth-Oriented Strategy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Even if five steps already are good, we can still do better.  If we look at the log, above, we see that after test `#2`, where the input (tree) is reduced to `2 * 3`, our `GrammarReducer` first tries to replace the tree with `2` and `3`, which are the alternate `<term>` subtrees.  This may work, of course; but if there are many possible subtrees, our strategy will spend quite some time trying one after the other."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Delta debugging, as introduced above, follows the idea of trying to cut inputs approximately in half, and thus quickly proceeds towards a minimal input.  By replacing a tree with much smaller subtrees, we _could_ possibly reduce a tree significantly, but may need several attempts to do so.  A better strategy is to only consider _large_ subtrees first – both for the subtree replacement as well as for alternate expansions.  To find such _large_ subtrees, we limit the _depth_ by which we search for possible replacements in the subtree – first, by looking at the direct descendants, later at lower descendants."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is the role of the `depth` parameter used in `subtrees_with_symbol()` and passed through the invoking functions.  If set, _only_ symbols at the given depth are returned.  Here's an example, starting again with our derivation tree `derivation_tree`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "grammar_reducer = GrammarReducer(\n",
    "    mystery,\n",
    "    EarleyParser(EXPR_GRAMMAR),\n",
    "    log_reduce=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "all_terminals(derivation_tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "display_tree(derivation_tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "At a depth of 1, there is no `<term>` symbol:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[all_terminals(t) for t in grammar_reducer.subtrees_with_symbol(\n",
    "    derivation_tree, \"<term>\", depth=1)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "At a depth of 2, we have the `<term>` subtree on the left hand side:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[all_terminals(t) for t in grammar_reducer.subtrees_with_symbol(\n",
    "    derivation_tree, \"<term>\", depth=2)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "At a depth of 3, we have the `<term>` subtree on the right hand side:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[all_terminals(t) for t in grammar_reducer.subtrees_with_symbol(\n",
    "    derivation_tree, \"<term>\", depth=3)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The idea is now to start with a depth of 0, subsequently increasing it as we proceed:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class GrammarReducer(GrammarReducer):\n",
    "    def reduce_tree(self, tree):\n",
    "        depth = 0\n",
    "        while depth < max_height(tree):\n",
    "            reduced = self.reduce_subtree(tree, tree, depth)\n",
    "            if reduced:\n",
    "                depth = 0    # Start with new tree\n",
    "            else:\n",
    "                depth += 1   # Extend search for subtrees\n",
    "        return tree        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "grammar_reducer = GrammarReducer(\n",
    "    mystery,\n",
    "    EarleyParser(EXPR_GRAMMAR),\n",
    "    log_test=True)\n",
    "grammar_reducer.reduce(expr_input)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that a depth-oriented strategy needs even fewer steps in our setting."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Comparing Strategies\n",
    "\n",
    "We close by demonstrating the difference between text-based delta debugging and our grammar-based reduction.  We build a very long expression:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from GrammarFuzzer import GrammarFuzzer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "long_expr_input = GrammarFuzzer(EXPR_GRAMMAR, min_nonterminals=100).fuzz()\n",
    "long_expr_input"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With grammars, we need only a handful of tests to find the failure-inducing input:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from Timer import Timer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "grammar_reducer = GrammarReducer(eval_mystery, EarleyParser(EXPR_GRAMMAR))\n",
    "with Timer() as grammar_time:\n",
    "    print(grammar_reducer.reduce(long_expr_input))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "grammar_reducer.tests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "grammar_time.elapsed_time()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Delta debugging, in contrast, requires orders of magnitude more tests (and consequently, time).  Again, the reduction is not closely as perfect as it is with the grammar-based reducer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dd_reducer = DeltaDebuggingReducer(eval_mystery)\n",
    "with Timer() as dd_time:\n",
    "    print(dd_reducer.reduce(long_expr_input))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dd_reducer.tests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dd_time.elapsed_time()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that if an input is syntactically complex, using a grammar to reduce inputs is the best way to go."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": true,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "## Lessons Learned\n",
    "\n",
    "* Reducing failure-inducing inputs to a minimum is helpful for testing and debugging.\n",
    "* _Delta debugging_ is a simple and robust algorithm to easily reduce test cases.\n",
    "* For syntactically complex inputs, _grammar-based reduction_ is much faster and yields better results."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "## Next Steps\n",
    "\n",
    "Our next chapter focuses on [Web GUI Fuzzing](WebFuzzer.ipynb), another domain where generating and reducing test cases is central."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Background\n",
    "\n",
    "The delta debugging algorithm discussed here stems from \\cite{Zeller2002}; actually, this is the exact Python implementation as used by Zeller in 2002.  The idea of systematically reducing inputs has been discovered a number of times, although not as  automatic and generic as delta debugging. \\cite{Slutz1998}, for instance, discusses systematic reduction of SQL statements for SQL databases; the general process as manual work is well described by \\cite{Kernighan1999}."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The deficits of delta debugging as it comes to syntactically complex inputs were first discussed in *compiler testing*, and _reducing tree inputs_ rather than string inputs was quickly discovered as an alternative.  *Hierarchical Delta Debugging* (*HDD*) \\cite{Misherghi2006} applies delta debugging on subtrees of a parse tree, systematically reducing a parse tree to a minimum.  _Generalized Tree Reduction_ \\cite{Herfert2017} generalizes this idea to apply arbitrary _patterns_ such as replacing a term by a compatible term in a subtree, as `subtrees_with_symbol()` does.\n",
    "\n",
    "None of the existing approaches, though, makes use of grammars to apply expansion alternatives (as `alternate_reductions()` does); nor do they strive towards replacing larger subtrees first (as `reduce_tree()` does).  The present chapter thus makes an original contribution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "While `GrammarReducer` is a generic approach that can be parameterized with an arbitrary grammar, _language-specific_ approaches can do a much better job for the language at hand.  *C-Reduce* \\cite{Regehr2012} is a reducer specifically targeting the reduction of programming languages.  Besides reductions in the style of delta debugging or tree transformations, C-Reduce comes with more than 30 source-to-source transformations that replace aggregates by scalars, remove function parameters at a definition and all call sites, change functions to return `void` and deleting all `return` statements, and many more.  While specifically instantiated for the C language (and used for testing C compilers), these principles extend to arbitrary programming languages following an ALGOL-like syntax.  When testing a compiler, C-Reduce is the tool to go for."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This [blog post](https://www.drmaciver.com/2019/01/notes-on-test-case-reduction/) by David McIver contains lots of insights on how to apply reduction in practice, in particular multiple runs with different abstraction levels."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": true,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "## Exercises\n",
    "\n",
    "How to best reduce inputs is still an underdeveloped field of research, with lots of opportunities."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "### Exercise 1: Mutation-Based Fuzzing with Reduction\n",
    "\n",
    "When fuzzing with a population, it can be useful to occasionally _reduce_ the length of each element, such that future descendants are shorter, too, which typically speeds up their testing.\n",
    "\n",
    "Consider the `MutationFuzzer` class from [the chapter on mutation-based fuzzing](MutationFuzzer.ipynb). \n",
    "Extend it such that whenever a new input is added to the population, it is first reduced using delta debugging."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    },
    "solution2": "hidden"
   },
   "source": [
    "**Solution.** Left to the reader."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "solution": "hidden",
    "solution2": "hidden",
    "solution2_first": true,
    "solution_first": true
   },
   "source": [
    "### Exercise 2: Reduction by Production\n",
    "\n",
    "Grammar-based input reduction, as sketched above, might be a good algorithm, but is by no means the only alternative.  One interesting question is whether \"reduction\" should only be limited to elements already present, or whether one would be allowed to also create _new_ elements.  These would not be present in the original input, yet still allow to produce a much smaller input that would still reproduce the original failure."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "solution": "hidden",
    "solution2": "hidden",
    "solution2_first": true,
    "solution_first": true
   },
   "source": [
    "As an example, consider the following grammar:\n",
    "\n",
    "```\n",
    "<number> ::= <float> | <integer> | <not-a-number>\n",
    "<float> ::= <digits>.<digits>\n",
    "<integer> ::= <digits>\n",
    "<not-a-number> ::= NaN\n",
    "<digits> ::= [0-9]+\n",
    "```\n",
    "\n",
    "Assume the input `100.99` fails.  We might be able to reduce it to a minimum of, say, `1.9`.  However, we cannot reduce it to an `<integer>` or to `<not-a-number>`, as these symbols do not occur in the original input.  By allowing to _create_ alternatives for these symbols, we could also tests inputs such as `1` or `NaN` and further generalize the class of inputs for which the program fails."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "solution": "hidden",
    "solution2": "hidden",
    "solution2_first": true,
    "solution_first": true
   },
   "source": [
    "Create a class `GenerativeGrammarReducer` as subclass of `GrammarReducer`; extend the method `reduce_subtree()` accordingly."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "skip"
    },
    "solution": "hidden",
    "solution2": "hidden"
   },
   "source": [
    "**Solution.** Left to the reader."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "solution": "hidden",
    "solution2": "hidden",
    "solution2_first": true,
    "solution_first": true
   },
   "source": [
    "### Exercise 3: The Big Reduction Shoot-Out\n",
    "\n",
    "Create a _benchmark_ for the grammars already defined earlier, consisting of:\n",
    "\n",
    "1. A set of _inputs_, produced from these very grammars using `GrammarFuzzer` and derivatives;\n",
    "2. A set of _tests_ which check for the occurrence of individual symbols as well as pairs and triples of these symbols:\n",
    "    * Tests should be _unresolved_ if the input is not syntactically valid;\n",
    "    * Tests should _fail_ if the symbols (or pairs or triples thereof) occur;\n",
    "    * Tests should _pass_ in all other cases.\n",
    "    \n",
    "Compare delta debugging and grammar-based debugging on the benchmark.  Implement HDD \\cite{Misherghi2006} and _Generalized Tree Reduction_ \\cite{Herfert2017} and add them to your comparison.  Which approach performs best, and under which circumstances?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "skip"
    },
    "solution": "hidden",
    "solution2": "hidden"
   },
   "source": [
    "**Solution.** Left to the reader."
   ]
  }
 ],
 "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,
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}