docs/notebooks/APIFuzzer.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "# Fuzzing APIs\n",
    "\n",
    "So far, we have always generated _system input_, i.e. data that the program as a whole obtains via its input channels.  However, we can also generate inputs that go directly into individual functions, gaining flexibility and speed in the process.  In this chapter, we explore the use of grammars to synthesize code for function calls, which allows you to generate _program code that very efficiently invokes functions directly._  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:24.105165Z",
     "iopub.status.busy": "2023-01-07T14:21:24.104778Z",
     "iopub.status.idle": "2023-01-07T14:21:24.160668Z",
     "shell.execute_reply": "2023-01-07T14:21:24.160890Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "        <iframe\n",
       "            width=\"640\"\n",
       "            height=\"360\"\n",
       "            src=\"https://www.youtube-nocookie.com/embed/CC1VvOGkzm8\"\n",
       "            frameborder=\"0\"\n",
       "            allowfullscreen\n",
       "            \n",
       "        ></iframe>\n",
       "        "
      ],
      "text/plain": [
       "<IPython.lib.display.IFrame at 0x1060d1ed0>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from bookutils import YouTubeVideo\n",
    "YouTubeVideo('CC1VvOGkzm8')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "**Prerequisites**\n",
    "\n",
    "* You have to know how grammar fuzzing work, e.g. from the [chapter on grammars](Grammars.ipynb).\n",
    "* We make use of _generator functions_, as discussed in the [chapter on fuzzing with generators](GeneratorGrammarFuzzer.ipynb).\n",
    "* We make use of probabilities, as discussed in the [chapter on fuzzing with probabilities](ProbabilisticGrammarFuzzer.ipynb)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "## Synopsis\n",
    "<!-- Automatically generated. Do not edit. -->\n",
    "\n",
    "To [use the code provided in this chapter](Importing.ipynb), write\n",
    "\n",
    "```python\n",
    ">>> from fuzzingbook.APIFuzzer import <identifier>\n",
    "```\n",
    "\n",
    "and then make use of the following features.\n",
    "\n",
    "\n",
    "This chapter provides *grammar constructors* that are useful for generating _function calls_.\n",
    "\n",
    "The grammars are [probabilistic](ProbabilisticGrammarFuzzer.ipynb) and make use of [generators](GeneratorGrammarFuzzer.ipynb), so use `ProbabilisticGeneratorGrammarFuzzer` as a producer.\n",
    "\n",
    "```python\n",
    ">>> from GeneratorGrammarFuzzer import ProbabilisticGeneratorGrammarFuzzer\n",
    "```\n",
    "`INT_GRAMMAR`, `FLOAT_GRAMMAR`, `ASCII_STRING_GRAMMAR` produce integers, floats, and strings, respectively:\n",
    "\n",
    "```python\n",
    ">>> fuzzer = ProbabilisticGeneratorGrammarFuzzer(INT_GRAMMAR)\n",
    ">>> [fuzzer.fuzz() for i in range(10)]\n",
    "['-51', '9', '0', '0', '0', '0', '32', '0', '0', '0']\n",
    ">>> fuzzer = ProbabilisticGeneratorGrammarFuzzer(FLOAT_GRAMMAR)\n",
    ">>> [fuzzer.fuzz() for i in range(10)]\n",
    "['0e0',\n",
    " '-9.43e34',\n",
    " '-7.3282e0',\n",
    " '-9.5e-9',\n",
    " '0',\n",
    " '-30.840386e-5',\n",
    " '3',\n",
    " '-4.1e0',\n",
    " '-9.7',\n",
    " '413']\n",
    ">>> fuzzer = ProbabilisticGeneratorGrammarFuzzer(ASCII_STRING_GRAMMAR)\n",
    ">>> [fuzzer.fuzz() for i in range(10)]\n",
    "['\"#vYV*t@I%KNTT[q~}&-v+[zAzj[X-z|RzC$(g$Br]1tC\\':5<F-\"',\n",
    " '\"\"',\n",
    " '\"^S/\"',\n",
    " '\"y)QDs_9\"',\n",
    " '\")dY~?WYqMh,bwn3\\\\\"A!02Pk`gx\"',\n",
    " '\"01n|(dd$-d.sx\\\\\"83\\\\\"h/]qx)d9LPNdrk$}$4t3zhC.%3VY@AZZ0wCs2 N\"',\n",
    " '\"D\\\\6\\\\xgw#TQ}$\\'3\"',\n",
    " '\"LaM{\"',\n",
    " '\"\\\\\"ux\\'1H!=%;2T$.=l\"',\n",
    " '\"=vkiV~w.Ypt,?JwcEr}Moc>!5<U+DdYAup\\\\\"N 0V?h3x~jFN3\"']\n",
    "```\n",
    "`int_grammar_with_range(start, end)` produces an integer grammar with values `N` such that `start <= N <= end`:\n",
    "\n",
    "```python\n",
    ">>> int_grammar = int_grammar_with_range(100, 200)\n",
    ">>> fuzzer = ProbabilisticGeneratorGrammarFuzzer(int_grammar)\n",
    ">>> [fuzzer.fuzz() for i in range(10)]\n",
    "['154', '149', '185', '117', '182', '154', '131', '194', '147', '192']\n",
    "```\n",
    "`float_grammar_with_range(start, end)` produces a floating-number grammar with values `N` such that `start <= N <= end`.\n",
    "\n",
    "```python\n",
    ">>> float_grammar = float_grammar_with_range(100, 200)\n",
    ">>> fuzzer = ProbabilisticGeneratorGrammarFuzzer(float_grammar)\n",
    ">>> [fuzzer.fuzz() for i in range(10)]\n",
    "['121.8092479227325',\n",
    " '187.18037169119634',\n",
    " '127.9576486784452',\n",
    " '125.47768739781723',\n",
    " '151.8091820472274',\n",
    " '117.864410860742',\n",
    " '187.50918008379483',\n",
    " '119.29335112884749',\n",
    " '149.2637029583114',\n",
    " '126.61818995939146']\n",
    "```\n",
    "All such values can be immediately used for testing function calls:\n",
    "\n",
    "```python\n",
    ">>> from math import sqrt\n",
    ">>> fuzzer = ProbabilisticGeneratorGrammarFuzzer(int_grammar)\n",
    ">>> call = \"sqrt(\" + fuzzer.fuzz() + \")\"\n",
    ">>> call\n",
    "'sqrt(143)'\n",
    ">>> eval(call)\n",
    "11.958260743101398\n",
    "```\n",
    "These grammars can also be composed to form more complex grammars. `list_grammar(object_grammar)` returns a grammar that produces lists of objects as defined by `object_grammar`.\n",
    "\n",
    "```python\n",
    ">>> int_list_grammar = list_grammar(int_grammar)\n",
    ">>> fuzzer = ProbabilisticGeneratorGrammarFuzzer(int_list_grammar)\n",
    ">>> [fuzzer.fuzz() for i in range(5)]\n",
    "['[118, 111, 188, 137, 129]',\n",
    " '[170, 172]',\n",
    " '[171, 161, 117, 191, 175, 183, 164]',\n",
    " '[189]',\n",
    " '[129, 110, 178]']\n",
    ">>> some_list = eval(fuzzer.fuzz())\n",
    ">>> some_list\n",
    "[172, 120, 106, 192, 124, 191, 161, 100, 117]\n",
    ">>> len(some_list)\n",
    "9\n",
    "```\n",
    "In a similar vein, we can construct arbitrary further data types for testing individual functions programmatically.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": true,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "slide"
    },
    "toc-hr-collapsed": false
   },
   "source": [
    "## Fuzzing a Function\n",
    "\n",
    "Let us start with our first problem: How do we fuzz a given function?  For an interpreted language like Python, this is pretty straight-forward.  All we need to do is to generate _calls_ to the function(s) we want to test.  This is something we can easily do with a grammar."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": true,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "As an example, consider the `urlparse()` function from the Python library.  `urlparse()` takes a URL and decomposes it into its individual components."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "button": false,
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:24.163749Z",
     "iopub.status.busy": "2023-01-07T14:21:24.163186Z",
     "iopub.status.idle": "2023-01-07T14:21:24.164469Z",
     "shell.execute_reply": "2023-01-07T14:21:24.164873Z"
    },
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import bookutils"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:24.166808Z",
     "iopub.status.busy": "2023-01-07T14:21:24.166505Z",
     "iopub.status.idle": "2023-01-07T14:21:24.167624Z",
     "shell.execute_reply": "2023-01-07T14:21:24.167926Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from urllib.parse import urlparse"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:24.169840Z",
     "iopub.status.busy": "2023-01-07T14:21:24.169539Z",
     "iopub.status.idle": "2023-01-07T14:21:24.171041Z",
     "shell.execute_reply": "2023-01-07T14:21:24.171266Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "ParseResult(scheme='https', netloc='www.fuzzingbook.com', path='/html/APIFuzzer.html', params='', query='', fragment='')"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "urlparse('https://www.fuzzingbook.com/html/APIFuzzer.html')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "You see how the individual elements of the URL – the _scheme_ (`\"http\"`), the _network location_ (`\"www.fuzzingbook.com\"`), or the path (`\"//html/APIFuzzer.html\"`) are all properly identified.  Other elements (like `params`, `query`, or `fragment`) are empty, because they were not part of our input."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "To test `urlparse()`, we'd want to feed it a large set of different URLs.  We can obtain these from the URL grammar we had defined in the [\"Grammars\"](Grammars.ipynb) chapter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:24.173350Z",
     "iopub.status.busy": "2023-01-07T14:21:24.172978Z",
     "iopub.status.idle": "2023-01-07T14:21:24.659142Z",
     "shell.execute_reply": "2023-01-07T14:21:24.659365Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from Grammars import URL_GRAMMAR, is_valid_grammar, START_SYMBOL\n",
    "from Grammars import opts, extend_grammar, Grammar\n",
    "from GrammarFuzzer import GrammarFuzzer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:24.661645Z",
     "iopub.status.busy": "2023-01-07T14:21:24.661147Z",
     "iopub.status.idle": "2023-01-07T14:21:24.666543Z",
     "shell.execute_reply": "2023-01-07T14:21:24.667143Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "url_fuzzer = GrammarFuzzer(URL_GRAMMAR)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:24.671830Z",
     "iopub.status.busy": "2023-01-07T14:21:24.671472Z",
     "iopub.status.idle": "2023-01-07T14:21:24.673003Z",
     "shell.execute_reply": "2023-01-07T14:21:24.673266Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ParseResult(scheme='https', netloc='user:password@cispa.saarland:8080', path='/', params='', query='', fragment='')\n",
      "ParseResult(scheme='http', netloc='cispa.saarland:1', path='/', params='', query='', fragment='')\n",
      "ParseResult(scheme='https', netloc='fuzzingbook.com:7', path='', params='', query='', fragment='')\n",
      "ParseResult(scheme='https', netloc='user:password@cispa.saarland:80', path='', params='', query='', fragment='')\n",
      "ParseResult(scheme='ftps', netloc='user:password@fuzzingbook.com', path='', params='', query='', fragment='')\n",
      "ParseResult(scheme='ftp', netloc='fuzzingbook.com', path='/abc', params='', query='abc=x31&def=x20', fragment='')\n",
      "ParseResult(scheme='ftp', netloc='user:password@fuzzingbook.com', path='', params='', query='', fragment='')\n",
      "ParseResult(scheme='https', netloc='www.google.com:80', path='/', params='', query='', fragment='')\n",
      "ParseResult(scheme='http', netloc='fuzzingbook.com:52', path='/', params='', query='', fragment='')\n",
      "ParseResult(scheme='ftps', netloc='user:password@cispa.saarland', path='', params='', query='', fragment='')\n"
     ]
    }
   ],
   "source": [
    "for i in range(10):\n",
    "    url = url_fuzzer.fuzz()\n",
    "    print(urlparse(url))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "This way, we can easily test any Python function – by setting up a scaffold that runs it.  How would we proceed, though, if we wanted to have a test that can be re-run again and again, without having to generate new calls every time?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Synthesizing Code\n",
    "\n",
    "The \"scaffolding\" method, as sketched above, has an important downside: It couples test generation and test execution into a single unit, disallowing running both at different times, or for different languages.  To decouple the two, we take another approach: Rather than generating inputs and immediately feeding this input into a function, we _synthesize code_ instead that invokes functions with a given input."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "For instance, if we generate the string"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:24.675003Z",
     "iopub.status.busy": "2023-01-07T14:21:24.674707Z",
     "iopub.status.idle": "2023-01-07T14:21:24.676084Z",
     "shell.execute_reply": "2023-01-07T14:21:24.676296Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "call = \"urlparse('http://www.example.com/')\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "we can execute this string as a whole (and thus run the test) at any time:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:24.678582Z",
     "iopub.status.busy": "2023-01-07T14:21:24.678139Z",
     "iopub.status.idle": "2023-01-07T14:21:24.679849Z",
     "shell.execute_reply": "2023-01-07T14:21:24.680186Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "ParseResult(scheme='http', netloc='www.example.com', path='/', params='', query='', fragment='')"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "eval(call)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "To systematically generate such calls, we can again use a grammar:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:24.682452Z",
     "iopub.status.busy": "2023-01-07T14:21:24.682122Z",
     "iopub.status.idle": "2023-01-07T14:21:24.683217Z",
     "shell.execute_reply": "2023-01-07T14:21:24.683485Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "URLPARSE_GRAMMAR: Grammar = {\n",
    "    \"<call>\":\n",
    "        ['urlparse(\"<url>\")']\n",
    "}\n",
    "\n",
    "# Import definitions from URL_GRAMMAR\n",
    "URLPARSE_GRAMMAR.update(URL_GRAMMAR)\n",
    "URLPARSE_GRAMMAR[\"<start>\"] = [\"<call>\"]\n",
    "\n",
    "assert is_valid_grammar(URLPARSE_GRAMMAR)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "This grammar creates calls in the form `urlparse(<url>)`, where `<url>` comes from the \"imported\" URL grammar.  The idea is to create many of these calls and to feed them into the Python interpreter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:24.685869Z",
     "iopub.status.busy": "2023-01-07T14:21:24.685488Z",
     "iopub.status.idle": "2023-01-07T14:21:24.687090Z",
     "shell.execute_reply": "2023-01-07T14:21:24.687342Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'<call>': ['urlparse(\"<url>\")'],\n",
       " '<start>': ['<call>'],\n",
       " '<url>': ['<scheme>://<authority><path><query>'],\n",
       " '<scheme>': ['http', 'https', 'ftp', 'ftps'],\n",
       " '<authority>': ['<host>',\n",
       "  '<host>:<port>',\n",
       "  '<userinfo>@<host>',\n",
       "  '<userinfo>@<host>:<port>'],\n",
       " '<host>': ['cispa.saarland', 'www.google.com', 'fuzzingbook.com'],\n",
       " '<port>': ['80', '8080', '<nat>'],\n",
       " '<nat>': ['<digit>', '<digit><digit>'],\n",
       " '<digit>': ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'],\n",
       " '<userinfo>': ['user:password'],\n",
       " '<path>': ['', '/', '/<id>'],\n",
       " '<id>': ['abc', 'def', 'x<digit><digit>'],\n",
       " '<query>': ['', '?<params>'],\n",
       " '<params>': ['<param>', '<param>&<params>'],\n",
       " '<param>': ['<id>=<id>', '<id>=<nat>']}"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "URLPARSE_GRAMMAR"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "We can now use this grammar for fuzzing and synthesizing calls to `urlparse)`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:24.690190Z",
     "iopub.status.busy": "2023-01-07T14:21:24.689793Z",
     "iopub.status.idle": "2023-01-07T14:21:24.691187Z",
     "shell.execute_reply": "2023-01-07T14:21:24.691429Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'urlparse(\"http://user:password@fuzzingbook.com:8080?abc=x29\")'"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "urlparse_fuzzer = GrammarFuzzer(URLPARSE_GRAMMAR)\n",
    "urlparse_fuzzer.fuzz()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Just as above, we can immediately execute these calls.  To better see what is happening, we define a small helper function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:24.693639Z",
     "iopub.status.busy": "2023-01-07T14:21:24.693283Z",
     "iopub.status.idle": "2023-01-07T14:21:24.694486Z",
     "shell.execute_reply": "2023-01-07T14:21:24.694737Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "# Call function_name(arg[0], arg[1], ...) as a string\n",
    "def do_call(call_string):\n",
    "    print(call_string)\n",
    "    result = eval(call_string)\n",
    "    print(\"\\t= \" + repr(result))\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:24.697359Z",
     "iopub.status.busy": "2023-01-07T14:21:24.696973Z",
     "iopub.status.idle": "2023-01-07T14:21:24.698735Z",
     "shell.execute_reply": "2023-01-07T14:21:24.698924Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "urlparse(\"http://www.google.com?abc=def\")\n",
      "\t= ParseResult(scheme='http', netloc='www.google.com', path='', params='', query='abc=def', fragment='')\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "ParseResult(scheme='http', netloc='www.google.com', path='', params='', query='abc=def', fragment='')"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "call = urlparse_fuzzer.fuzz()\n",
    "do_call(call)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "If `urlparse()` were a C function, for instance, we could embed its call into some (also generated) C function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:24.700920Z",
     "iopub.status.busy": "2023-01-07T14:21:24.700613Z",
     "iopub.status.idle": "2023-01-07T14:21:24.701841Z",
     "shell.execute_reply": "2023-01-07T14:21:24.702088Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "URLPARSE_C_GRAMMAR: Grammar = {\n",
    "    \"<cfile>\": [\"<cheader><cfunction>\"],\n",
    "    \"<cheader>\": ['#include \"urlparse.h\"\\n\\n'],\n",
    "    \"<cfunction>\": [\"void test() {\\n<calls>}\\n\"],\n",
    "    \"<calls>\": [\"<call>\", \"<calls><call>\"],\n",
    "    \"<call>\": ['    urlparse(\"<url>\");\\n']\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:24.703852Z",
     "iopub.status.busy": "2023-01-07T14:21:24.703548Z",
     "iopub.status.idle": "2023-01-07T14:21:24.704971Z",
     "shell.execute_reply": "2023-01-07T14:21:24.704781Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "URLPARSE_C_GRAMMAR.update(URL_GRAMMAR)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:24.706700Z",
     "iopub.status.busy": "2023-01-07T14:21:24.706338Z",
     "iopub.status.idle": "2023-01-07T14:21:24.707842Z",
     "shell.execute_reply": "2023-01-07T14:21:24.708087Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "URLPARSE_C_GRAMMAR[\"<start>\"] = [\"<cfile>\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:24.709901Z",
     "iopub.status.busy": "2023-01-07T14:21:24.709591Z",
     "iopub.status.idle": "2023-01-07T14:21:24.711111Z",
     "shell.execute_reply": "2023-01-07T14:21:24.711322Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "assert is_valid_grammar(URLPARSE_C_GRAMMAR)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:24.714831Z",
     "iopub.status.busy": "2023-01-07T14:21:24.714482Z",
     "iopub.status.idle": "2023-01-07T14:21:24.715947Z",
     "shell.execute_reply": "2023-01-07T14:21:24.716248Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#include \"urlparse.h\"\n",
      "\n",
      "void test() {\n",
      "    urlparse(\"http://user:password@cispa.saarland:99/x69?x57=abc\");\n",
      "}\n",
      "\n"
     ]
    }
   ],
   "source": [
    "urlparse_fuzzer = GrammarFuzzer(URLPARSE_C_GRAMMAR)\n",
    "print(urlparse_fuzzer.fuzz())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Synthesizing Oracles\n",
    "\n",
    "In our `urlparse()` example, both the Python as well as the C variant only check for _generic_ errors in `urlparse()`; that is, they only detect fatal errors and exceptions.  For a full test, we need to set up a specific *oracle* as well that checks whether the result is valid."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Our plan is to check whether specific parts of the URL reappear in the result – that is, if the scheme is `http:`, then the `ParseResult` returned should also contain a `http:` scheme.  As discussed in the [chapter on fuzzing with generators](GeneratorGrammarFuzzer.ipynb), equalities of strings such as `http:` across two symbols cannot be expressed in a context-free grammar.  We can, however, use a _generator function_ (also introduced in the [chapter on fuzzing with generators](GeneratorGrammarFuzzer.ipynb)) to automatically enforce such equalities."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Here is an example.  Invoking `geturl()` on a `urlparse()` result should return the URL as originally passed to `urlparse()`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:24.718419Z",
     "iopub.status.busy": "2023-01-07T14:21:24.718101Z",
     "iopub.status.idle": "2023-01-07T14:21:24.982986Z",
     "shell.execute_reply": "2023-01-07T14:21:24.983771Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from GeneratorGrammarFuzzer import GeneratorGrammarFuzzer, ProbabilisticGeneratorGrammarFuzzer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:24.988128Z",
     "iopub.status.busy": "2023-01-07T14:21:24.987659Z",
     "iopub.status.idle": "2023-01-07T14:21:24.989051Z",
     "shell.execute_reply": "2023-01-07T14:21:24.989296Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "URLPARSE_ORACLE_GRAMMAR: Grammar = extend_grammar(URLPARSE_GRAMMAR,\n",
    "{\n",
    "     \"<call>\": [(\"assert urlparse('<url>').geturl() == '<url>'\",\n",
    "                 opts(post=lambda url_1, url_2: [None, url_1]))]\n",
    "})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:24.992624Z",
     "iopub.status.busy": "2023-01-07T14:21:24.992264Z",
     "iopub.status.idle": "2023-01-07T14:21:24.993642Z",
     "shell.execute_reply": "2023-01-07T14:21:24.993954Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "assert urlparse('https://user:password@cispa.saarland/abc?abc=abc').geturl() == 'https://user:password@cispa.saarland/abc?abc=abc'\n"
     ]
    }
   ],
   "source": [
    "urlparse_oracle_fuzzer = GeneratorGrammarFuzzer(URLPARSE_ORACLE_GRAMMAR)\n",
    "test = urlparse_oracle_fuzzer.fuzz()\n",
    "print(test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:24.995995Z",
     "iopub.status.busy": "2023-01-07T14:21:24.995700Z",
     "iopub.status.idle": "2023-01-07T14:21:24.996850Z",
     "shell.execute_reply": "2023-01-07T14:21:24.997092Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "exec(test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "In a similar way, we can also check individual components of the result:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:24.999670Z",
     "iopub.status.busy": "2023-01-07T14:21:24.999360Z",
     "iopub.status.idle": "2023-01-07T14:21:25.000493Z",
     "shell.execute_reply": "2023-01-07T14:21:25.000728Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "URLPARSE_ORACLE_GRAMMAR: Grammar = extend_grammar(URLPARSE_GRAMMAR,\n",
    "{\n",
    "     \"<call>\": [(\"result = urlparse('<scheme>://<host><path>?<params>')\\n\"\n",
    "                 # + \"print(result)\\n\"\n",
    "                 + \"assert result.scheme == '<scheme>'\\n\"\n",
    "                 + \"assert result.netloc == '<host>'\\n\"\n",
    "                 + \"assert result.path == '<path>'\\n\"\n",
    "                 + \"assert result.query == '<params>'\",\n",
    "                 opts(post=lambda scheme_1, authority_1, path_1, params_1,\n",
    "                      scheme_2, authority_2, path_2, params_2:\n",
    "                      [None, None, None, None,\n",
    "                       scheme_1, authority_1, path_1, params_1]))]\n",
    "})\n",
    "\n",
    "# Get rid of unused symbols\n",
    "del URLPARSE_ORACLE_GRAMMAR[\"<url>\"]\n",
    "del URLPARSE_ORACLE_GRAMMAR[\"<query>\"]\n",
    "del URLPARSE_ORACLE_GRAMMAR[\"<authority>\"]\n",
    "del URLPARSE_ORACLE_GRAMMAR[\"<userinfo>\"]\n",
    "del URLPARSE_ORACLE_GRAMMAR[\"<port>\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.003534Z",
     "iopub.status.busy": "2023-01-07T14:21:25.001674Z",
     "iopub.status.idle": "2023-01-07T14:21:25.004794Z",
     "shell.execute_reply": "2023-01-07T14:21:25.005111Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "result = urlparse('https://www.google.com/?def=18&abc=abc')\n",
      "assert result.scheme == 'https'\n",
      "assert result.netloc == 'www.google.com'\n",
      "assert result.path == '/'\n",
      "assert result.query == 'def=18&abc=abc'\n"
     ]
    }
   ],
   "source": [
    "urlparse_oracle_fuzzer = GeneratorGrammarFuzzer(URLPARSE_ORACLE_GRAMMAR)\n",
    "test = urlparse_oracle_fuzzer.fuzz()\n",
    "print(test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.006870Z",
     "iopub.status.busy": "2023-01-07T14:21:25.006557Z",
     "iopub.status.idle": "2023-01-07T14:21:25.007796Z",
     "shell.execute_reply": "2023-01-07T14:21:25.008026Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "exec(test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The use of generator functions may feel a bit cumbersome.  Indeed, if we uniquely stick to Python, we could also create a _unit test_ that directly invokes the fuzzer to generate individual parts:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.010055Z",
     "iopub.status.busy": "2023-01-07T14:21:25.009752Z",
     "iopub.status.idle": "2023-01-07T14:21:25.010927Z",
     "shell.execute_reply": "2023-01-07T14:21:25.011153Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def fuzzed_url_element(symbol):\n",
    "    return GrammarFuzzer(URLPARSE_GRAMMAR, start_symbol=symbol).fuzz()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.013836Z",
     "iopub.status.busy": "2023-01-07T14:21:25.013539Z",
     "iopub.status.idle": "2023-01-07T14:21:25.014680Z",
     "shell.execute_reply": "2023-01-07T14:21:25.014968Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "scheme = fuzzed_url_element(\"<scheme>\")\n",
    "authority = fuzzed_url_element(\"<authority>\")\n",
    "path = fuzzed_url_element(\"<path>\")\n",
    "query = fuzzed_url_element(\"<params>\")\n",
    "url = \"%s://%s%s?%s\" % (scheme, authority, path, query)\n",
    "result = urlparse(url)\n",
    "# print(result)\n",
    "assert result.geturl() == url\n",
    "assert result.scheme == scheme\n",
    "assert result.path == path\n",
    "assert result.query == query"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Using such a unit test makes it easier to express oracles.  However, we lose the ability to systematically cover individual URL elements and alternatives as with [`GrammarCoverageFuzzer`](GrammarCoverageFuzzer.ipynb) as well as the ability to guide generation towards specific elements as with [`ProbabilisticGrammarFuzzer`](ProbabilisticGrammarFuzzer.ipynb).  Furthermore, a grammar allows us to generate tests for arbitrary programming languages and APIs."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "toc-hr-collapsed": false
   },
   "source": [
    "## Synthesizing Data\n",
    "\n",
    "For `urlparse()`, we have used a very specific grammar for creating a very specific argument.  Many functions take basic data types as (some) arguments, though; we therefore define grammars that generate precisely those arguments.  Even better, we can define functions that _generate_ grammars tailored towards our specific needs, returning values in a particular range, for instance."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Integers\n",
    "\n",
    "We introduce a simple grammar to produce integers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.016723Z",
     "iopub.status.busy": "2023-01-07T14:21:25.016436Z",
     "iopub.status.idle": "2023-01-07T14:21:25.017866Z",
     "shell.execute_reply": "2023-01-07T14:21:25.017669Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from Grammars import convert_ebnf_grammar, crange"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.019465Z",
     "iopub.status.busy": "2023-01-07T14:21:25.019175Z",
     "iopub.status.idle": "2023-01-07T14:21:25.020443Z",
     "shell.execute_reply": "2023-01-07T14:21:25.020687Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from ProbabilisticGrammarFuzzer import ProbabilisticGrammarFuzzer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.022629Z",
     "iopub.status.busy": "2023-01-07T14:21:25.022316Z",
     "iopub.status.idle": "2023-01-07T14:21:25.023598Z",
     "shell.execute_reply": "2023-01-07T14:21:25.023832Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "INT_EBNF_GRAMMAR: Grammar = {\n",
    "    \"<start>\": [\"<int>\"],\n",
    "    \"<int>\": [\"<_int>\"],\n",
    "    \"<_int>\": [\"(-)?<leaddigit><digit>*\", \"0\"],\n",
    "    \"<leaddigit>\": crange('1', '9'),\n",
    "    \"<digit>\": crange('0', '9')\n",
    "}\n",
    "\n",
    "assert is_valid_grammar(INT_EBNF_GRAMMAR)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.026213Z",
     "iopub.status.busy": "2023-01-07T14:21:25.025910Z",
     "iopub.status.idle": "2023-01-07T14:21:25.027319Z",
     "shell.execute_reply": "2023-01-07T14:21:25.027564Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'<start>': ['<int>'],\n",
       " '<int>': ['<_int>'],\n",
       " '<_int>': ['<symbol-1><leaddigit><digit-1>', '0'],\n",
       " '<leaddigit>': ['1', '2', '3', '4', '5', '6', '7', '8', '9'],\n",
       " '<digit>': ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'],\n",
       " '<symbol>': ['-'],\n",
       " '<symbol-1>': ['', '<symbol>'],\n",
       " '<digit-1>': ['', '<digit><digit-1>']}"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "INT_GRAMMAR = convert_ebnf_grammar(INT_EBNF_GRAMMAR)\n",
    "INT_GRAMMAR"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.030549Z",
     "iopub.status.busy": "2023-01-07T14:21:25.030232Z",
     "iopub.status.idle": "2023-01-07T14:21:25.031701Z",
     "shell.execute_reply": "2023-01-07T14:21:25.032017Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['699', '-44', '321', '-7', '-6', '67', '0', '0', '57', '0']\n"
     ]
    }
   ],
   "source": [
    "int_fuzzer = GrammarFuzzer(INT_GRAMMAR)\n",
    "print([int_fuzzer.fuzz() for i in range(10)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "If we need integers in a specific range, we can add a generator function that does right that:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.033755Z",
     "iopub.status.busy": "2023-01-07T14:21:25.033460Z",
     "iopub.status.idle": "2023-01-07T14:21:25.034801Z",
     "shell.execute_reply": "2023-01-07T14:21:25.034980Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from Grammars import set_opts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.036772Z",
     "iopub.status.busy": "2023-01-07T14:21:25.036419Z",
     "iopub.status.idle": "2023-01-07T14:21:25.037631Z",
     "shell.execute_reply": "2023-01-07T14:21:25.037869Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.039914Z",
     "iopub.status.busy": "2023-01-07T14:21:25.039609Z",
     "iopub.status.idle": "2023-01-07T14:21:25.040896Z",
     "shell.execute_reply": "2023-01-07T14:21:25.041159Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def int_grammar_with_range(start, end):\n",
    "    int_grammar = extend_grammar(INT_GRAMMAR)\n",
    "    set_opts(int_grammar, \"<int>\", \"<_int>\",\n",
    "        opts(pre=lambda: random.randint(start, end)))\n",
    "    return int_grammar"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.043694Z",
     "iopub.status.busy": "2023-01-07T14:21:25.043376Z",
     "iopub.status.idle": "2023-01-07T14:21:25.044980Z",
     "shell.execute_reply": "2023-01-07T14:21:25.045206Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['942', '955', '997', '967', '939', '923', '984', '914', '991', '982']"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "int_fuzzer = GeneratorGrammarFuzzer(int_grammar_with_range(900, 1000))\n",
    "[int_fuzzer.fuzz() for i in range(10)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Floats\n",
    "\n",
    "The grammar for floating-point values closely resembles the integer grammar."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.047390Z",
     "iopub.status.busy": "2023-01-07T14:21:25.047036Z",
     "iopub.status.idle": "2023-01-07T14:21:25.048324Z",
     "shell.execute_reply": "2023-01-07T14:21:25.048612Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "FLOAT_EBNF_GRAMMAR: Grammar = {\n",
    "    \"<start>\": [\"<float>\"],\n",
    "    \"<float>\": [(\"<_float>\", opts(prob=0.9)), \"inf\", \"NaN\"],\n",
    "    \"<_float>\": [\"<int>(.<digit>+)?<exp>?\"],\n",
    "    \"<exp>\": [\"e<int>\"]\n",
    "}\n",
    "FLOAT_EBNF_GRAMMAR.update(INT_EBNF_GRAMMAR)\n",
    "FLOAT_EBNF_GRAMMAR[\"<start>\"] = [\"<float>\"]\n",
    "\n",
    "assert is_valid_grammar(FLOAT_EBNF_GRAMMAR)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.051137Z",
     "iopub.status.busy": "2023-01-07T14:21:25.050794Z",
     "iopub.status.idle": "2023-01-07T14:21:25.052399Z",
     "shell.execute_reply": "2023-01-07T14:21:25.052578Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'<start>': ['<float>'],\n",
       " '<float>': [('<_float>', {'prob': 0.9}), 'inf', 'NaN'],\n",
       " '<_float>': ['<int><symbol-2><exp-1>'],\n",
       " '<exp>': ['e<int>'],\n",
       " '<int>': ['<_int>'],\n",
       " '<_int>': ['<symbol-1-1><leaddigit><digit-1>', '0'],\n",
       " '<leaddigit>': ['1', '2', '3', '4', '5', '6', '7', '8', '9'],\n",
       " '<digit>': ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'],\n",
       " '<symbol>': ['.<digit-2>'],\n",
       " '<symbol-1>': ['-'],\n",
       " '<symbol-2>': ['', '<symbol>'],\n",
       " '<exp-1>': ['', '<exp>'],\n",
       " '<symbol-1-1>': ['', '<symbol-1>'],\n",
       " '<digit-1>': ['', '<digit><digit-1>'],\n",
       " '<digit-2>': ['<digit>', '<digit><digit-2>']}"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "FLOAT_GRAMMAR = convert_ebnf_grammar(FLOAT_EBNF_GRAMMAR)\n",
    "FLOAT_GRAMMAR"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.058365Z",
     "iopub.status.busy": "2023-01-07T14:21:25.058063Z",
     "iopub.status.idle": "2023-01-07T14:21:25.059467Z",
     "shell.execute_reply": "2023-01-07T14:21:25.059716Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['0', '-4e0', '-3.3', '0.55e0', '0e2', '0.2', '-48.6e0', '0.216', '-4.844', '-6.100']\n"
     ]
    }
   ],
   "source": [
    "float_fuzzer = ProbabilisticGrammarFuzzer(FLOAT_GRAMMAR)\n",
    "print([float_fuzzer.fuzz() for i in range(10)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.061871Z",
     "iopub.status.busy": "2023-01-07T14:21:25.061514Z",
     "iopub.status.idle": "2023-01-07T14:21:25.062910Z",
     "shell.execute_reply": "2023-01-07T14:21:25.063251Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def float_grammar_with_range(start, end):\n",
    "    float_grammar = extend_grammar(FLOAT_GRAMMAR)\n",
    "    set_opts(float_grammar, \"<float>\", \"<_float>\", opts(\n",
    "        pre=lambda: start + random.random() * (end - start)))\n",
    "    return float_grammar"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.066414Z",
     "iopub.status.busy": "2023-01-07T14:21:25.066006Z",
     "iopub.status.idle": "2023-01-07T14:21:25.067612Z",
     "shell.execute_reply": "2023-01-07T14:21:25.067801Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['900.1695968039919',\n",
       " '900.3273891873373',\n",
       " '900.225192820568',\n",
       " '900.3231805358258',\n",
       " '900.4963527393471',\n",
       " 'inf',\n",
       " 'inf',\n",
       " '900.6037658059212',\n",
       " '900.6212350658716',\n",
       " '900.3877831415683']"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "float_fuzzer = ProbabilisticGeneratorGrammarFuzzer(\n",
    "    float_grammar_with_range(900.0, 900.9))\n",
    "[float_fuzzer.fuzz() for i in range(10)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Strings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Finally, we introduce a grammar for producing strings."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.070287Z",
     "iopub.status.busy": "2023-01-07T14:21:25.069970Z",
     "iopub.status.idle": "2023-01-07T14:21:25.071351Z",
     "shell.execute_reply": "2023-01-07T14:21:25.071603Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "ASCII_STRING_EBNF_GRAMMAR: Grammar = {\n",
    "    \"<start>\": [\"<ascii-string>\"],\n",
    "    \"<ascii-string>\": ['\"<ascii-chars>\"'],\n",
    "    \"<ascii-chars>\": [\n",
    "        (\"\", opts(prob=0.05)),\n",
    "        \"<ascii-chars><ascii-char>\"\n",
    "    ],\n",
    "    \"<ascii-char>\": crange(\" \", \"!\") + [r'\\\"'] + crange(\"#\", \"~\")\n",
    "}\n",
    "\n",
    "assert is_valid_grammar(ASCII_STRING_EBNF_GRAMMAR)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.073683Z",
     "iopub.status.busy": "2023-01-07T14:21:25.073383Z",
     "iopub.status.idle": "2023-01-07T14:21:25.074542Z",
     "shell.execute_reply": "2023-01-07T14:21:25.074780Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "ASCII_STRING_GRAMMAR = convert_ebnf_grammar(ASCII_STRING_EBNF_GRAMMAR)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.161542Z",
     "iopub.status.busy": "2023-01-07T14:21:25.118975Z",
     "iopub.status.idle": "2023-01-07T14:21:25.339637Z",
     "shell.execute_reply": "2023-01-07T14:21:25.339970Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['\"BgY)\"', '\"j[-64Big65wso(f:wg|}w&*D9JthLX}0@PT^]mr[`69Cq8H713ITYx<#jpml)\\\\\"\"', '\"{);XWZJ@d`\\'[h#F{1)C9M?%C`=\"', '\"Y\"', '\"C4gh`?uzJzD~$\\\\\\\\\"=|j)jj=SrBLIJ@0IbYiwIvNf5#pT4QUR}[g,35?Wg4i?3TdIsR0|eq3r;ZKuyI\\'<\\\\\"[p/x$<$B!\\\\\"_\"', '\"J0HG33+E(p8JQtKW.;G7 ^?.\"', '\"7r^B:Jf*J.@sqfED|M)3,eJ&OD\"', '\"c3Hcx^&*~3\\\\\"Jvac}cX\"', '\"\\'IHBQ:N+U:w(OAFn0pHLzX\"', '\"x4agH>H-2{Q|\\\\kpYF\"']\n"
     ]
    }
   ],
   "source": [
    "string_fuzzer = ProbabilisticGrammarFuzzer(ASCII_STRING_GRAMMAR)\n",
    "print([string_fuzzer.fuzz() for i in range(10)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Synthesizing Composite Data\n",
    "\n",
    "From basic data, as discussed above, we can also produce _composite data_ in data structures such as sets or lists.  We illustrate such generation on lists."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.341613Z",
     "iopub.status.busy": "2023-01-07T14:21:25.341316Z",
     "iopub.status.idle": "2023-01-07T14:21:25.343549Z",
     "shell.execute_reply": "2023-01-07T14:21:25.343889Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "LIST_EBNF_GRAMMAR: Grammar = {\n",
    "    \"<start>\": [\"<list>\"],\n",
    "    \"<list>\": [\n",
    "        (\"[]\", opts(prob=0.05)),\n",
    "        \"[<list-objects>]\"\n",
    "    ],\n",
    "    \"<list-objects>\": [\n",
    "        (\"<list-object>\", opts(prob=0.2)),\n",
    "        \"<list-object>, <list-objects>\"\n",
    "    ],\n",
    "    \"<list-object>\": [\"0\"],\n",
    "}\n",
    "\n",
    "assert is_valid_grammar(LIST_EBNF_GRAMMAR)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.345732Z",
     "iopub.status.busy": "2023-01-07T14:21:25.345436Z",
     "iopub.status.idle": "2023-01-07T14:21:25.346688Z",
     "shell.execute_reply": "2023-01-07T14:21:25.346882Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "LIST_GRAMMAR = convert_ebnf_grammar(LIST_EBNF_GRAMMAR)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Our list generator takes a grammar that produces objects; it then instantiates a list grammar with the objects from these grammars."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.349225Z",
     "iopub.status.busy": "2023-01-07T14:21:25.348906Z",
     "iopub.status.idle": "2023-01-07T14:21:25.350122Z",
     "shell.execute_reply": "2023-01-07T14:21:25.350388Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def list_grammar(object_grammar, list_object_symbol=None):\n",
    "    obj_list_grammar = extend_grammar(LIST_GRAMMAR)\n",
    "    if list_object_symbol is None:\n",
    "        # Default: Use the first expansion of <start> as list symbol\n",
    "        list_object_symbol = object_grammar[START_SYMBOL][0]\n",
    "\n",
    "    obj_list_grammar.update(object_grammar)\n",
    "    obj_list_grammar[START_SYMBOL] = [\"<list>\"]\n",
    "    obj_list_grammar[\"<list-object>\"] = [list_object_symbol]\n",
    "\n",
    "    assert is_valid_grammar(obj_list_grammar)\n",
    "\n",
    "    return obj_list_grammar"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.386245Z",
     "iopub.status.busy": "2023-01-07T14:21:25.357622Z",
     "iopub.status.idle": "2023-01-07T14:21:25.387722Z",
     "shell.execute_reply": "2023-01-07T14:21:25.387988Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['[0, -4, 23, 0, 0, 9, 0, -6067681]',\n",
       " '[-1, -1, 0, -7]',\n",
       " '[-5, 0]',\n",
       " '[1, 0, -628088, -6, -811, 0, 99, 0]',\n",
       " '[-35, -10, 0, 67]',\n",
       " '[-3, 0, -2, 0, 0]',\n",
       " '[0, -267, -78, -733, 0, 0, 0, 0]',\n",
       " '[0, -6, 71, -9]',\n",
       " '[-72, 76, 0, 2]',\n",
       " '[0, 9, 0, 0, -572, 29, 8, 8, 0]']"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "int_list_fuzzer = ProbabilisticGrammarFuzzer(list_grammar(INT_GRAMMAR))\n",
    "[int_list_fuzzer.fuzz() for i in range(10)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.403830Z",
     "iopub.status.busy": "2023-01-07T14:21:25.402493Z",
     "iopub.status.idle": "2023-01-07T14:21:25.479410Z",
     "shell.execute_reply": "2023-01-07T14:21:25.479664Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['[\"gn-A$j>\", \"SPX;\", \"\", \"\", \"\"]',\n",
       " '[\"_\", \"Qp\"]',\n",
       " '[\"M\", \"5\\\\\"`X744\", \"b+5fyM!\", \"gR`\"]',\n",
       " '[\"^h\", \"8$u\", \"\", \"\", \"\"]',\n",
       " '[\"6X;\", \"\", \"T1wp%\\'t\"]',\n",
       " '[\"-?Kk\", \"@B\", \"}\", \"\", \"\"]',\n",
       " '[\"FD<mqK\", \")Y4NI3M.&@1/2.p\", \"]C#c1}z#+5{7ERA[|\", \"EOFM])BEMFcGM.~k&RMj*,:m8^!5*:vv%ci\"]',\n",
       " '[\"\", \"*B.pKI\\\\\"L\", \"O)#<Y\", \"\\\\\", \"\", \"\", \"\"]',\n",
       " '[\"g\"]',\n",
       " '[\"\", \"\\\\JS;~t\", \"h)\", \"k\", \"\", \"\"]']"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "string_list_fuzzer = ProbabilisticGrammarFuzzer(\n",
    "    list_grammar(ASCII_STRING_GRAMMAR))\n",
    "[string_list_fuzzer.fuzz() for i in range(10)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.514175Z",
     "iopub.status.busy": "2023-01-07T14:21:25.513807Z",
     "iopub.status.idle": "2023-01-07T14:21:25.515304Z",
     "shell.execute_reply": "2023-01-07T14:21:25.515628Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['[900.558064701869, 900.6079527708223, 900.1985188111297, 900.5159940886509, 900.1881413629061, 900.4074809145482, 900.8279453113845, 900.1531931708976, 900.2651056125504, inf, 900.828295978669]',\n",
       " '[900.4956935906264, 900.8166792417645, 900.2044872129637]',\n",
       " '[900.6177668624133, 900.793129850367, 900.5024769009476, 900.5874531663001, inf, 900.3476216137291, 900.5680329060473, 900.1524624203945, 900.1157565249836, 900.0943774301732, 900.1589468212459, 900.8563415304703, 900.2871041191156, 900.2469765832253, 900.408183791468]',\n",
       " '[NaN, 900.1152482126347, 900.1139109179966, NaN, 900.0634308730662, 900.1918596242257]',\n",
       " '[900.49418992478]',\n",
       " '[900.6566851795975, NaN, 900.5585085641878, 900.8678799526169, 900.5580757140183]',\n",
       " '[900.6265067760952]',\n",
       " '[900.5271187218734, 900.3413004135587, 900.0362652510535, 900.2938223153569, 900.6584186055829, 900.5394909707123, 900.5119630230411, 900.2024669591465]',\n",
       " '[900.5068304562362, 900.5173419618334, 900.5268996804168, 900.5247314889621, 900.1082421801126, 900.761200730868, 900.100950598924, 900.1424140649187, inf, inf, 900.4546924838603, 900.7025508468811, 900.5147250716594, 900.4943696257178, 900.814107878577, 900.3540228715348, 900.6165673939341, 900.121833279104, 900.8337503512706, 900.0607374037857, 900.2746253938637, 900.2491844866619, 900.7325728031923]',\n",
       " '[900.6962790125643, 900.6055198052603, 900.0950691946015, 900.6283670716376, NaN, 900.112869956762]']"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "float_list_fuzzer = ProbabilisticGeneratorGrammarFuzzer(list_grammar(\n",
    "    float_grammar_with_range(900.0, 900.9)))\n",
    "[float_list_fuzzer.fuzz() for i in range(10)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Generators for dictionaries, sets, etc. can be defined in a similar fashion.  By plugging together grammar generators, we can produce data structures with arbitrary elements."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Synopsis\n",
    "\n",
    "This chapter provides *grammar constructors* that are useful for generating _function calls_.\n",
    "\n",
    "The grammars are [probabilistic](ProbabilisticGrammarFuzzer.ipynb) and make use of [generators](GeneratorGrammarFuzzer.ipynb), so use `ProbabilisticGeneratorGrammarFuzzer` as a producer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.517464Z",
     "iopub.status.busy": "2023-01-07T14:21:25.517172Z",
     "iopub.status.idle": "2023-01-07T14:21:25.518391Z",
     "shell.execute_reply": "2023-01-07T14:21:25.518579Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from GeneratorGrammarFuzzer import ProbabilisticGeneratorGrammarFuzzer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "`INT_GRAMMAR`, `FLOAT_GRAMMAR`, `ASCII_STRING_GRAMMAR` produce integers, floats, and strings, respectively:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.522078Z",
     "iopub.status.busy": "2023-01-07T14:21:25.521745Z",
     "iopub.status.idle": "2023-01-07T14:21:25.523715Z",
     "shell.execute_reply": "2023-01-07T14:21:25.524222Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['-51', '9', '0', '0', '0', '0', '32', '0', '0', '0']"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fuzzer = ProbabilisticGeneratorGrammarFuzzer(INT_GRAMMAR)\n",
    "[fuzzer.fuzz() for i in range(10)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.534628Z",
     "iopub.status.busy": "2023-01-07T14:21:25.534276Z",
     "iopub.status.idle": "2023-01-07T14:21:25.535841Z",
     "shell.execute_reply": "2023-01-07T14:21:25.536033Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['0e0',\n",
       " '-9.43e34',\n",
       " '-7.3282e0',\n",
       " '-9.5e-9',\n",
       " '0',\n",
       " '-30.840386e-5',\n",
       " '3',\n",
       " '-4.1e0',\n",
       " '-9.7',\n",
       " '413']"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fuzzer = ProbabilisticGeneratorGrammarFuzzer(FLOAT_GRAMMAR)\n",
    "[fuzzer.fuzz() for i in range(10)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.543540Z",
     "iopub.status.busy": "2023-01-07T14:21:25.543220Z",
     "iopub.status.idle": "2023-01-07T14:21:25.698781Z",
     "shell.execute_reply": "2023-01-07T14:21:25.699084Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['\"#vYV*t@I%KNTT[q~}&-v+[zAzj[X-z|RzC$(g$Br]1tC\\':5<F-\"',\n",
       " '\"\"',\n",
       " '\"^S/\"',\n",
       " '\"y)QDs_9\"',\n",
       " '\")dY~?WYqMh,bwn3\\\\\"A!02Pk`gx\"',\n",
       " '\"01n|(dd$-d.sx\\\\\"83\\\\\"h/]qx)d9LPNdrk$}$4t3zhC.%3VY@AZZ0wCs2 N\"',\n",
       " '\"D\\\\6\\\\xgw#TQ}$\\'3\"',\n",
       " '\"LaM{\"',\n",
       " '\"\\\\\"ux\\'1H!=%;2T$.=l\"',\n",
       " '\"=vkiV~w.Ypt,?JwcEr}Moc>!5<U+DdYAup\\\\\"N 0V?h3x~jFN3\"']"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fuzzer = ProbabilisticGeneratorGrammarFuzzer(ASCII_STRING_GRAMMAR)\n",
    "[fuzzer.fuzz() for i in range(10)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "`int_grammar_with_range(start, end)` produces an integer grammar with values `N` such that `start <= N <= end`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.702827Z",
     "iopub.status.busy": "2023-01-07T14:21:25.702485Z",
     "iopub.status.idle": "2023-01-07T14:21:25.703906Z",
     "shell.execute_reply": "2023-01-07T14:21:25.704223Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['154', '149', '185', '117', '182', '154', '131', '194', '147', '192']"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "int_grammar = int_grammar_with_range(100, 200)\n",
    "fuzzer = ProbabilisticGeneratorGrammarFuzzer(int_grammar)\n",
    "[fuzzer.fuzz() for i in range(10)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "`float_grammar_with_range(start, end)` produces a floating-number grammar with values `N` such that `start <= N <= end`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.708210Z",
     "iopub.status.busy": "2023-01-07T14:21:25.707642Z",
     "iopub.status.idle": "2023-01-07T14:21:25.709555Z",
     "shell.execute_reply": "2023-01-07T14:21:25.709881Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['121.8092479227325',\n",
       " '187.18037169119634',\n",
       " '127.9576486784452',\n",
       " '125.47768739781723',\n",
       " '151.8091820472274',\n",
       " '117.864410860742',\n",
       " '187.50918008379483',\n",
       " '119.29335112884749',\n",
       " '149.2637029583114',\n",
       " '126.61818995939146']"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "float_grammar = float_grammar_with_range(100, 200)\n",
    "fuzzer = ProbabilisticGeneratorGrammarFuzzer(float_grammar)\n",
    "[fuzzer.fuzz() for i in range(10)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "All such values can be immediately used for testing function calls:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.712695Z",
     "iopub.status.busy": "2023-01-07T14:21:25.712128Z",
     "iopub.status.idle": "2023-01-07T14:21:25.713459Z",
     "shell.execute_reply": "2023-01-07T14:21:25.713814Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from math import sqrt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.716575Z",
     "iopub.status.busy": "2023-01-07T14:21:25.716196Z",
     "iopub.status.idle": "2023-01-07T14:21:25.717900Z",
     "shell.execute_reply": "2023-01-07T14:21:25.718346Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'sqrt(143)'"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fuzzer = ProbabilisticGeneratorGrammarFuzzer(int_grammar)\n",
    "call = \"sqrt(\" + fuzzer.fuzz() + \")\"\n",
    "call"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.720519Z",
     "iopub.status.busy": "2023-01-07T14:21:25.720175Z",
     "iopub.status.idle": "2023-01-07T14:21:25.721875Z",
     "shell.execute_reply": "2023-01-07T14:21:25.722113Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "11.958260743101398"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "eval(call)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "These grammars can also be composed to form more complex grammars. `list_grammar(object_grammar)` returns a grammar that produces lists of objects as defined by `object_grammar`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.727632Z",
     "iopub.status.busy": "2023-01-07T14:21:25.727234Z",
     "iopub.status.idle": "2023-01-07T14:21:25.729075Z",
     "shell.execute_reply": "2023-01-07T14:21:25.729450Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['[118, 111, 188, 137, 129]',\n",
       " '[170, 172]',\n",
       " '[171, 161, 117, 191, 175, 183, 164]',\n",
       " '[189]',\n",
       " '[129, 110, 178]']"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "int_list_grammar = list_grammar(int_grammar)\n",
    "fuzzer = ProbabilisticGeneratorGrammarFuzzer(int_list_grammar)\n",
    "[fuzzer.fuzz() for i in range(5)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.733654Z",
     "iopub.status.busy": "2023-01-07T14:21:25.733332Z",
     "iopub.status.idle": "2023-01-07T14:21:25.734578Z",
     "shell.execute_reply": "2023-01-07T14:21:25.734830Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "some_list = eval(fuzzer.fuzz())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.736773Z",
     "iopub.status.busy": "2023-01-07T14:21:25.736451Z",
     "iopub.status.idle": "2023-01-07T14:21:25.737957Z",
     "shell.execute_reply": "2023-01-07T14:21:25.738277Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[172, 120, 106, 192, 124, 191, 161, 100, 117]"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "some_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-01-07T14:21:25.740108Z",
     "iopub.status.busy": "2023-01-07T14:21:25.739735Z",
     "iopub.status.idle": "2023-01-07T14:21:25.741295Z",
     "shell.execute_reply": "2023-01-07T14:21:25.741585Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(some_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "In a similar vein, we can construct arbitrary further data types for testing individual functions programmatically."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": true,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Lessons Learned\n",
    "\n",
    "* To fuzz individual functions, one can easily set up grammars that produce function calls.\n",
    "* Fuzzing at the API level can be much faster than fuzzing at the system level, but brings the risk of false alarms by violating implicit preconditions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Next Steps\n",
    "\n",
    "This chapter was all about manually writing test and controlling which data gets generated.  [In the next chapter](Carver.ipynb), we will introduce a much higher level of automation:\n",
    "\n",
    "* _Carving_ automatically records function calls and arguments from program executions.\n",
    "* We can turn these into _grammars_, allowing to test these functions with various combinations of recorded values.\n",
    "\n",
    "With these techniques, we automatically obtain grammars that already invoke functions in application contexts, making our work of specifying them much easier. "
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Background\n",
    "\n",
    "The idea of using generator functions to generate input structures was first explored in QuickCheck \\cite{Claessen2000}.   A very nice implementation for Python is the [hypothesis package](https://hypothesis.readthedocs.io/en/latest/) which allows writing and combining data structure generators for testing APIs."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": true,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Exercises\n",
    "\n",
    "The exercises for this chapter combine the above techniques with fuzzing techniques introduced earlier."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    },
    "solution2": "hidden",
    "solution2_first": true
   },
   "source": [
    "### Exercise 1: Deep Arguments\n",
    "\n",
    "In the example generating oracles for `urlparse()`, important elements such as `authority` or `port` are not checked.  Enrich `URLPARSE_ORACLE_GRAMMAR` with post-expansion functions that store the generated elements in a symbol table, such that they can be accessed when generating the assertions."
   ]
  },
  {
   "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
    },
    "slideshow": {
     "slide_type": "subslide"
    },
    "solution2": "hidden",
    "solution2_first": true
   },
   "source": [
    "### Exercise 2: Covering Argument Combinations\n",
    "\n",
    "In the chapter on [configuration testing](ConfigurationFuzzer.ipynb), we also discussed _combinatorial testing_ – that is, systematic coverage of _sets_ of configuration elements.  Implement a scheme that by changing the grammar, allows all _pairs_ of argument values to be covered."
   ]
  },
  {
   "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
    },
    "slideshow": {
     "slide_type": "subslide"
    },
    "solution2": "hidden",
    "solution2_first": true
   },
   "source": [
    "### Exercise 3: Mutating Arguments\n",
    "\n",
    "To widen the range of arguments to be used during testing, apply the _mutation schemes_ introduced in [mutation fuzzing](MutationFuzzer.ipynb) – for instance, flip individual bytes or delete characters from strings.  Apply this either during grammar inference or as a separate step when invoking functions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    },
    "solution2": "hidden"
   },
   "source": [
    "**Solution.** Left to the reader."
   ]
  }
 ],
 "metadata": {
  "ipub": {
   "bibliography": "fuzzingbook.bib",
   "toc": true
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": true
  },
  "toc-autonumbering": false
 },
 "nbformat": 4,
 "nbformat_minor": 4
}