{ "cells": [ { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" }, "tags": [] }, "source": [ "# Grammar Coverage\n", "\n", "[Producing inputs from grammars](GrammarFuzzer.ipynb) gives all possible expansions of a rule the same likelihood. For producing a comprehensive test suite, however, it makes more sense to maximize _variety_ – for instance, by not repeating the same expansions over and over again. In this chapter, we explore how to systematically _cover_ elements of a grammar such that we maximize variety and do not miss out individual elements." ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:43.769539Z", "iopub.status.busy": "2025-10-26T13:26:43.769027Z", "iopub.status.idle": "2025-10-26T13:26:44.477195Z", "shell.execute_reply": "2025-10-26T13:26:44.476915Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [ { "data": { "text/html": [ "\n", " \n", " " ], "text/plain": [ "" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from bookutils import YouTubeVideo\n", "YouTubeVideo('GGb3e5p0HC8')" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "source": [ "**Prerequisites**\n", "\n", "* You should have read the [chapter on grammars](Grammars.ipynb).\n", "* You should have read the [chapter on efficient grammar fuzzing](GrammarFuzzer.ipynb)." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Synopsis\n", "To [use the code provided in this chapter](Importing.ipynb), write\n", "\n", "```python\n", ">>> from fuzzingbook.GrammarCoverageFuzzer import \n", "```\n", "\n", "and then make use of the following features.\n", "\n", "**Note**: The examples in this section only work after the rest of the cells have been executed.\n" ] }, { "cell_type": "code", "execution_count": 104, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:51.634316Z", "iopub.status.busy": "2025-10-26T13:26:51.634224Z", "iopub.status.idle": "2025-10-26T13:26:51.635841Z", "shell.execute_reply": "2025-10-26T13:26:51.635591Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from Grammars import EXPR_GRAMMAR" ] }, { "cell_type": "code", "execution_count": 105, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:51.637200Z", "iopub.status.busy": "2025-10-26T13:26:51.637118Z", "iopub.status.idle": "2025-10-26T13:26:51.638677Z", "shell.execute_reply": "2025-10-26T13:26:51.638479Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "expr_fuzzer = GrammarCoverageFuzzer(EXPR_GRAMMAR)" ] }, { "cell_type": "code", "execution_count": 106, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:51.639921Z", "iopub.status.busy": "2025-10-26T13:26:51.639852Z", "iopub.status.idle": "2025-10-26T13:26:51.641471Z", "shell.execute_reply": "2025-10-26T13:26:51.641240Z" }, "slideshow": { "slide_type": "fragment" }, "tags": [ "remove-input" ] }, "outputs": [], "source": [ "# ignore\n", "expr_fuzzer.fuzz();" ] }, { "cell_type": "code", "execution_count": 107, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:51.642571Z", "iopub.status.busy": "2025-10-26T13:26:51.642485Z", "iopub.status.idle": "2025-10-26T13:26:51.647695Z", "shell.execute_reply": "2025-10-26T13:26:51.647427Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "'-(2 + 3) * 4.5 / 6 - 2.0 / +8 + 7 + 3'" ] }, "execution_count": 107, "metadata": {}, "output_type": "execute_result" } ], "source": [ "expr_fuzzer.fuzz()" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "After fuzzing, the `expansion_coverage()` method returns a mapping of grammar expansions covered." ] }, { "cell_type": "code", "execution_count": 108, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:51.649140Z", "iopub.status.busy": "2025-10-26T13:26:51.649056Z", "iopub.status.idle": "2025-10-26T13:26:51.651169Z", "shell.execute_reply": "2025-10-26T13:26:51.650919Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "{' -> 0',\n", " ' -> 1',\n", " ' -> 2',\n", " ' -> 3',\n", " ' -> 4',\n", " ' -> 5',\n", " ' -> 6',\n", " ' -> 7',\n", " ' -> 8',\n", " ' -> 9',\n", " ' -> ',\n", " ' -> + ',\n", " ' -> - ',\n", " ' -> ()',\n", " ' -> +',\n", " ' -> -',\n", " ' -> ',\n", " ' -> .',\n", " ' -> ',\n", " ' -> ',\n", " ' -> ',\n", " ' -> ',\n", " ' -> * ',\n", " ' -> / '}" ] }, "execution_count": 108, "metadata": {}, "output_type": "execute_result" } ], "source": [ "expr_fuzzer.expansion_coverage()" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Subsequent calls to `fuzz()` will go for further coverage (i.e., covering the other area code digits, for example); a call to `reset()` clears the recorded coverage, starting anew." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Since such coverage in inputs also yields higher code coverage, `GrammarCoverageFuzzer` is a recommended extension to `GrammarFuzzer`." ] }, { "cell_type": "code", "execution_count": 109, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:51.652655Z", "iopub.status.busy": "2025-10-26T13:26:51.652574Z", "iopub.status.idle": "2025-10-26T13:26:51.653993Z", "shell.execute_reply": "2025-10-26T13:26:51.653791Z" }, "slideshow": { "slide_type": "fragment" }, "tags": [ "remove-input" ] }, "outputs": [], "source": [ "# ignore\n", "from ClassDiagram import display_class_hierarchy" ] }, { "cell_type": "code", "execution_count": 110, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:51.655395Z", "iopub.status.busy": "2025-10-26T13:26:51.655324Z", "iopub.status.idle": "2025-10-26T13:26:52.642851Z", "shell.execute_reply": "2025-10-26T13:26:52.642496Z" }, "slideshow": { "slide_type": "subslide" }, "tags": [ "remove-input" ] }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "GrammarCoverageFuzzer\n", "\n", "\n", "GrammarCoverageFuzzer\n", "\n", "\n", "\n", "_new_child_coverage()\n", "\n", "\n", "\n", "choose_node_expansion()\n", "\n", "\n", "\n", "new_child_coverage()\n", "\n", "\n", "\n", "new_coverages()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "SimpleGrammarCoverageFuzzer\n", "\n", "\n", "SimpleGrammarCoverageFuzzer\n", "\n", "\n", "\n", "choose_covered_node_expansion()\n", "\n", "\n", "\n", "choose_node_expansion()\n", "\n", "\n", "\n", "choose_uncovered_node_expansion()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "GrammarCoverageFuzzer->SimpleGrammarCoverageFuzzer\n", "\n", "\n", "\n", "\n", "\n", "TrackingGrammarCoverageFuzzer\n", "\n", "\n", "TrackingGrammarCoverageFuzzer\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "expansion_coverage()\n", "\n", "\n", "\n", "max_expansion_coverage()\n", "\n", "\n", "\n", "missing_expansion_coverage()\n", "\n", "\n", "\n", "reset_coverage()\n", "\n", "\n", "\n", "_max_expansion_coverage()\n", "\n", "\n", "\n", "add_coverage()\n", "\n", "\n", "\n", "choose_node_expansion()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "SimpleGrammarCoverageFuzzer->TrackingGrammarCoverageFuzzer\n", "\n", "\n", "\n", "\n", "\n", "GrammarFuzzer\n", "\n", "\n", "GrammarFuzzer\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "fuzz()\n", "\n", "\n", "\n", "fuzz_tree()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "TrackingGrammarCoverageFuzzer->GrammarFuzzer\n", "\n", "\n", "\n", "\n", "\n", "Fuzzer\n", "\n", "\n", "Fuzzer\n", "\n", "\n", "\n", "run()\n", "\n", "\n", "\n", "runs()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "GrammarFuzzer->Fuzzer\n", "\n", "\n", "\n", "\n", "\n", "Legend\n", "Legend\n", "• \n", "public_method()\n", "• \n", "private_method()\n", "• \n", "overloaded_method()\n", "Hover over names to see doc\n", "\n", "\n", "\n" ], "text/html": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "GrammarCoverageFuzzer\n", "\n", "\n", "GrammarCoverageFuzzer\n", "\n", "\n", "\n", "_new_child_coverage()\n", "\n", "\n", "\n", "choose_node_expansion()\n", "\n", "\n", "\n", "new_child_coverage()\n", "\n", "\n", "\n", "new_coverages()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "SimpleGrammarCoverageFuzzer\n", "\n", "\n", "SimpleGrammarCoverageFuzzer\n", "\n", "\n", "\n", "choose_covered_node_expansion()\n", "\n", "\n", "\n", "choose_node_expansion()\n", "\n", "\n", "\n", "choose_uncovered_node_expansion()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "GrammarCoverageFuzzer->SimpleGrammarCoverageFuzzer\n", "\n", "\n", "\n", "\n", "\n", "TrackingGrammarCoverageFuzzer\n", "\n", "\n", "TrackingGrammarCoverageFuzzer\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "expansion_coverage()\n", "\n", "\n", "\n", "max_expansion_coverage()\n", "\n", "\n", "\n", "missing_expansion_coverage()\n", "\n", "\n", "\n", "reset_coverage()\n", "\n", "\n", "\n", "_max_expansion_coverage()\n", "\n", "\n", "\n", "add_coverage()\n", "\n", "\n", "\n", "choose_node_expansion()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "SimpleGrammarCoverageFuzzer->TrackingGrammarCoverageFuzzer\n", "\n", "\n", "\n", "\n", "\n", "GrammarFuzzer\n", "\n", "\n", "GrammarFuzzer\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "fuzz()\n", "\n", "\n", "\n", "fuzz_tree()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "TrackingGrammarCoverageFuzzer->GrammarFuzzer\n", "\n", "\n", "\n", "\n", "\n", "Fuzzer\n", "\n", "\n", "Fuzzer\n", "\n", "\n", "\n", "run()\n", "\n", "\n", "\n", "runs()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "GrammarFuzzer->Fuzzer\n", "\n", "\n", "\n", "\n", "\n", "Legend\n", "Legend\n", "• \n", "public_method()\n", "• \n", "private_method()\n", "• \n", "overloaded_method()\n", "Hover over names to see doc\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 110, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# ignore\n", "display_class_hierarchy([GrammarCoverageFuzzer],\n", " public_methods=[\n", " Fuzzer.run,\n", " Fuzzer.runs,\n", " GrammarFuzzer.__init__,\n", " GrammarFuzzer.fuzz,\n", " GrammarFuzzer.fuzz_tree,\n", " TrackingGrammarCoverageFuzzer.max_expansion_coverage,\n", " TrackingGrammarCoverageFuzzer.missing_expansion_coverage,\n", " TrackingGrammarCoverageFuzzer.reset_coverage,\n", " GrammarCoverageFuzzer.__init__,\n", " GrammarCoverageFuzzer.fuzz,\n", " GrammarCoverageFuzzer.expansion_coverage,\n", " ],\n", " types={\n", " 'DerivationTree': DerivationTree,\n", " 'Expansion': Expansion,\n", " 'Grammar': Grammar\n", " },\n", " project='fuzzingbook')" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Covering Grammar Elements\n", "\n", "The aim of test generation is to cover all functionality of a program – hopefully including the failing functionality, of course. This functionality, however, is tied to the _structure of the input_: If we fail to produce certain input elements, then the associated code and functionality will not be triggered either, nixing our chances to find a bug in there." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "As an example, consider our expression grammar `EXPR_GRAMMAR` from the [chapter on grammars.](Grammars.ipynb):\n", "\n", "* If we do not produce negative numbers, then negative numbers will not be tested.\n", "* If we do not produce floating-point numbers, then floating-point numbers will not be tested.\n", "\n", "Our aim must thus be to _cover all possible expansions_ – and not only by chance, but _by design_." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "One way to maximize such variety is to _track_ the expansions that occur during grammar production: If we already have seen some expansion, we can prefer other possible expansion candidates out of the set of possible expansions. Consider the following rule in our expression grammar:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "button": false, "execution": { "iopub.execute_input": "2025-10-26T13:26:44.497101Z", "iopub.status.busy": "2025-10-26T13:26:44.496968Z", "iopub.status.idle": "2025-10-26T13:26:44.499077Z", "shell.execute_reply": "2025-10-26T13:26:44.498819Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import bookutils.setup" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:44.500717Z", "iopub.status.busy": "2025-10-26T13:26:44.500609Z", "iopub.status.idle": "2025-10-26T13:26:44.502122Z", "shell.execute_reply": "2025-10-26T13:26:44.501905Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from bookutils import quiz" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:44.503328Z", "iopub.status.busy": "2025-10-26T13:26:44.503243Z", "iopub.status.idle": "2025-10-26T13:26:44.561309Z", "shell.execute_reply": "2025-10-26T13:26:44.561021Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from Fuzzer import Fuzzer" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:44.563039Z", "iopub.status.busy": "2025-10-26T13:26:44.562939Z", "iopub.status.idle": "2025-10-26T13:26:44.564557Z", "shell.execute_reply": "2025-10-26T13:26:44.564337Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from typing import Dict, List, Set, Union, Optional" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:44.565936Z", "iopub.status.busy": "2025-10-26T13:26:44.565859Z", "iopub.status.idle": "2025-10-26T13:26:44.871511Z", "shell.execute_reply": "2025-10-26T13:26:44.871239Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from Grammars import EXPR_GRAMMAR, CGI_GRAMMAR, URL_GRAMMAR, START_SYMBOL\n", "from Grammars import is_valid_grammar, extend_grammar, Grammar" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "button": false, "execution": { "iopub.execute_input": "2025-10-26T13:26:44.873265Z", "iopub.status.busy": "2025-10-26T13:26:44.873124Z", "iopub.status.idle": "2025-10-26T13:26:44.875357Z", "shell.execute_reply": "2025-10-26T13:26:44.875129Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "['+', '-', '()', '.', '']" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "EXPR_GRAMMAR[\"\"]" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "Let us assume we have already produced an `` in the first expansion of ``. As it comes to expand the next factor, we would mark the `` expansion as already covered, and choose one of the yet uncovered alternatives such as `-` (a negative number) or `.` (a floating-point number). Only when we have covered all alternatives would we go back and reconsider expansions covered before." ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:44.876715Z", "iopub.status.busy": "2025-10-26T13:26:44.876632Z", "iopub.status.idle": "2025-10-26T13:26:44.880531Z", "shell.execute_reply": "2025-10-26T13:26:44.880307Z" }, "slideshow": { "slide_type": "subslide" }, "tags": [ "remove-input" ] }, "outputs": [ { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " Quiz\n", " \n", " Which expansions of EXPR_GRAMMAR does the expression 1 + 2 cover?\n", " \n", " \n", " \n", " \n", " \n", " <start> -> <expr>\n", " \n", " \n", " <integer> -> <digit><integer>\n", " \n", " \n", " <integer> -> <digit>\n", " \n", " \n", " <factor> -> +<factor>\n", " \n", " \n", " \n", " \n", " \n", " \n", " " ], "text/plain": [ "" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "quiz(\"Which expansions of `EXPR_GRAMMAR` does the expression `1 + 2` cover?\",\n", " [\n", " \"` -> `\",\n", " \"` -> `\",\n", " \"` -> `\",\n", " \"` -> +`\"\n", " ], [1, 3])" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Indeed! The expression has expansions from `` and into individual digits." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "### Tracking Grammar Coverage\n", "\n", "This concept of _grammar coverage_ is easy to implement. We introduce a class `TrackingGrammarCoverageFuzzer` that keeps track of the current grammar coverage achieved:" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:44.881973Z", "iopub.status.busy": "2025-10-26T13:26:44.881891Z", "iopub.status.idle": "2025-10-26T13:26:44.908657Z", "shell.execute_reply": "2025-10-26T13:26:44.908384Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from Grammars import Grammar, Expansion\n", "from GrammarFuzzer import GrammarFuzzer, all_terminals, nonterminals, \\\n", " display_tree, DerivationTree" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:44.910107Z", "iopub.status.busy": "2025-10-26T13:26:44.910022Z", "iopub.status.idle": "2025-10-26T13:26:44.911550Z", "shell.execute_reply": "2025-10-26T13:26:44.911314Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import random" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "button": false, "execution": { "iopub.execute_input": "2025-10-26T13:26:44.912750Z", "iopub.status.busy": "2025-10-26T13:26:44.912674Z", "iopub.status.idle": "2025-10-26T13:26:44.914386Z", "shell.execute_reply": "2025-10-26T13:26:44.914165Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "class TrackingGrammarCoverageFuzzer(GrammarFuzzer):\n", " \"\"\"Track grammar coverage during production\"\"\"\n", "\n", " def __init__(self, *args, **kwargs) -> None:\n", " # invoke superclass __init__(), passing all arguments\n", " super().__init__(*args, **kwargs)\n", " self.reset_coverage()" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "#### Keeping Track of Expansions\n", "\n", "In the set `covered_expansions`, we store individual expansions seen." ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "button": false, "execution": { "iopub.execute_input": "2025-10-26T13:26:44.915728Z", "iopub.status.busy": "2025-10-26T13:26:44.915645Z", "iopub.status.idle": "2025-10-26T13:26:44.917435Z", "shell.execute_reply": "2025-10-26T13:26:44.917157Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "class TrackingGrammarCoverageFuzzer(TrackingGrammarCoverageFuzzer):\n", " def expansion_coverage(self) -> Set[str]:\n", " \"\"\"Return the set of covered expansions as strings SYMBOL -> EXPANSION\"\"\"\n", " return self.covered_expansions\n", "\n", " def reset_coverage(self) -> None:\n", " \"\"\"Clear coverage info tracked so far\"\"\"\n", " self.covered_expansions: Set[str] = set()" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "We save them the expansions as strings \"_symbol_ -> _expansion_\", using the function `expansion_key()` to generate a string representation for the (_symbol_, _expansion_) pair." ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:44.918713Z", "iopub.status.busy": "2025-10-26T13:26:44.918635Z", "iopub.status.idle": "2025-10-26T13:26:44.920576Z", "shell.execute_reply": "2025-10-26T13:26:44.920344Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def expansion_key(symbol: str, \n", " expansion: Union[Expansion,\n", " DerivationTree, \n", " List[DerivationTree]]) -> str:\n", " \"\"\"Convert (symbol, `expansion`) into a key \"SYMBOL -> EXPRESSION\". \n", " `expansion` can be an expansion string, a derivation tree,\n", " or a list of derivation trees.\"\"\"\n", "\n", " if isinstance(expansion, tuple):\n", " # Expansion or single derivation tree\n", " expansion, _ = expansion\n", "\n", " if not isinstance(expansion, str):\n", " # Derivation tree\n", " children = expansion\n", " expansion = all_terminals((symbol, children))\n", "\n", " assert isinstance(expansion, str)\n", "\n", " return symbol + \" -> \" + expansion" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Here's an example:" ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:44.921936Z", "iopub.status.busy": "2025-10-26T13:26:44.921862Z", "iopub.status.idle": "2025-10-26T13:26:44.923754Z", "shell.execute_reply": "2025-10-26T13:26:44.923493Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "' -> '" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "expansion_key(START_SYMBOL, EXPR_GRAMMAR[START_SYMBOL][0])" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Instead of _expansion_, we can also pass a list of children as argument, which will then automatically be converted into a string." ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:44.925134Z", "iopub.status.busy": "2025-10-26T13:26:44.925055Z", "iopub.status.idle": "2025-10-26T13:26:44.926995Z", "shell.execute_reply": "2025-10-26T13:26:44.926766Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "' -> + '" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "children: List[DerivationTree] = [(\"\", None), (\" + \", []), (\"\", None)]\n", "expansion_key(\"\", children)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "#### Computing Possible Expansions\n", "\n", "We can compute the set of possible expansions in a grammar by enumerating all expansions. The method `max_expansion_coverage()` traverses the grammar recursively starting from the given symbol (by default: the grammar start symbol) and accumulates all expansions in the set `expansions`. With the `max_depth` parameter (default: $\\infty$), we can control how deep the grammar exploration should go; we will need this later in the chapter." ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:44.928353Z", "iopub.status.busy": "2025-10-26T13:26:44.928272Z", "iopub.status.idle": "2025-10-26T13:26:44.930972Z", "shell.execute_reply": "2025-10-26T13:26:44.930750Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class TrackingGrammarCoverageFuzzer(TrackingGrammarCoverageFuzzer):\n", " def _max_expansion_coverage(self, symbol: str, \n", " max_depth: Union[int, float]) -> Set[str]:\n", " if max_depth <= 0:\n", " return set()\n", "\n", " self._symbols_seen.add(symbol)\n", "\n", " expansions = set()\n", " for expansion in self.grammar[symbol]:\n", " expansions.add(expansion_key(symbol, expansion))\n", " for nonterminal in nonterminals(expansion):\n", " if nonterminal not in self._symbols_seen:\n", " expansions |= self._max_expansion_coverage(\n", " nonterminal, max_depth - 1)\n", "\n", " return expansions\n", "\n", " def max_expansion_coverage(self, symbol: Optional[str] = None,\n", " max_depth: Union[int, float] = float('inf')) \\\n", " -> Set[str]:\n", " \"\"\"Return set of all expansions in a grammar \n", " starting with `symbol` (default: start symbol).\n", " If `max_depth` is given, expand only to that depth.\"\"\"\n", " if symbol is None:\n", " symbol = self.start_symbol\n", "\n", " self._symbols_seen: Set[str] = set()\n", " cov = self._max_expansion_coverage(symbol, max_depth)\n", "\n", " if symbol == START_SYMBOL:\n", " assert len(self._symbols_seen) == len(self.grammar)\n", "\n", " return cov" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "We can use `max_expansion_coverage()` to compute all the expansions within the expression grammar:" ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:44.932239Z", "iopub.status.busy": "2025-10-26T13:26:44.932162Z", "iopub.status.idle": "2025-10-26T13:26:44.934482Z", "shell.execute_reply": "2025-10-26T13:26:44.934062Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "{' -> 0',\n", " ' -> 1',\n", " ' -> 2',\n", " ' -> 3',\n", " ' -> 4',\n", " ' -> 5',\n", " ' -> 6',\n", " ' -> 7',\n", " ' -> 8',\n", " ' -> 9',\n", " ' -> ',\n", " ' -> + ',\n", " ' -> - ',\n", " ' -> ()',\n", " ' -> +',\n", " ' -> -',\n", " ' -> ',\n", " ' -> .',\n", " ' -> ',\n", " ' -> ',\n", " ' -> ',\n", " ' -> ',\n", " ' -> * ',\n", " ' -> / '}" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "expr_fuzzer = TrackingGrammarCoverageFuzzer(EXPR_GRAMMAR)\n", "expr_fuzzer.max_expansion_coverage()" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "#### Tracking Expansions while Fuzzing\n", "\n", "During expansion, we can keep track of expansions seen. To do so, we hook into the method `choose_node_expansion()`, expanding a single node in our [Grammar fuzzer](GrammarFuzzer.ipynb)." ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:44.935891Z", "iopub.status.busy": "2025-10-26T13:26:44.935808Z", "iopub.status.idle": "2025-10-26T13:26:44.938192Z", "shell.execute_reply": "2025-10-26T13:26:44.937968Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "class TrackingGrammarCoverageFuzzer(TrackingGrammarCoverageFuzzer):\n", " def add_coverage(self, symbol: str,\n", " new_child: Union[Expansion, List[DerivationTree]]) -> None:\n", " key = expansion_key(symbol, new_child)\n", "\n", " if self.log and key not in self.covered_expansions:\n", " print(\"Now covered:\", key)\n", " self.covered_expansions.add(key)\n", "\n", " def choose_node_expansion(self, node: DerivationTree,\n", " children_alternatives: \n", " List[List[DerivationTree]]) -> int:\n", " (symbol, children) = node\n", " index = super().choose_node_expansion(node, children_alternatives)\n", " self.add_coverage(symbol, children_alternatives[index])\n", " return index" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "The method `missing_expansion_coverage()` is a helper method that returns the expansions that still have to be covered:" ] }, { "cell_type": "code", "execution_count": 19, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:44.939609Z", "iopub.status.busy": "2025-10-26T13:26:44.939516Z", "iopub.status.idle": "2025-10-26T13:26:44.941337Z", "shell.execute_reply": "2025-10-26T13:26:44.941090Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "class TrackingGrammarCoverageFuzzer(TrackingGrammarCoverageFuzzer):\n", " def missing_expansion_coverage(self) -> Set[str]:\n", " \"\"\"Return expansions not covered yet\"\"\"\n", " return self.max_expansion_coverage() - self.expansion_coverage()" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "#### Putting Things Together\n", "\n", "Let us show how tracking works. To keep things simple, let us focus on `` expansions only." ] }, { "cell_type": "code", "execution_count": 20, "metadata": { "button": false, "execution": { "iopub.execute_input": "2025-10-26T13:26:44.942715Z", "iopub.status.busy": "2025-10-26T13:26:44.942597Z", "iopub.status.idle": "2025-10-26T13:26:44.944847Z", "shell.execute_reply": "2025-10-26T13:26:44.944593Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Tree: \n", "Expanding randomly\n", "Now covered: -> 9\n", "Tree: 9\n", "'9'\n" ] }, { "data": { "text/plain": [ "'9'" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "digit_fuzzer = TrackingGrammarCoverageFuzzer(\n", " EXPR_GRAMMAR, start_symbol=\"\", log=True)\n", "digit_fuzzer.fuzz()" ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:44.946207Z", "iopub.status.busy": "2025-10-26T13:26:44.946101Z", "iopub.status.idle": "2025-10-26T13:26:44.948263Z", "shell.execute_reply": "2025-10-26T13:26:44.948034Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Tree: \n", "Expanding randomly\n", "Now covered: -> 0\n", "Tree: 0\n", "'0'\n" ] }, { "data": { "text/plain": [ "'0'" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "digit_fuzzer.fuzz()" ] }, { "cell_type": "code", "execution_count": 22, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:44.949890Z", "iopub.status.busy": "2025-10-26T13:26:44.949773Z", "iopub.status.idle": "2025-10-26T13:26:44.951943Z", "shell.execute_reply": "2025-10-26T13:26:44.951695Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Tree: \n", "Expanding randomly\n", "Now covered: -> 5\n", "Tree: 5\n", "'5'\n" ] }, { "data": { "text/plain": [ "'5'" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "digit_fuzzer.fuzz()" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Here's the set of covered expansions so far:" ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:44.953269Z", "iopub.status.busy": "2025-10-26T13:26:44.953179Z", "iopub.status.idle": "2025-10-26T13:26:44.955275Z", "shell.execute_reply": "2025-10-26T13:26:44.954887Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "{' -> 0', ' -> 5', ' -> 9'}" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "digit_fuzzer.expansion_coverage()" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "This is the set of all expansions we can cover:" ] }, { "cell_type": "code", "execution_count": 24, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:44.957254Z", "iopub.status.busy": "2025-10-26T13:26:44.957077Z", "iopub.status.idle": "2025-10-26T13:26:44.959748Z", "shell.execute_reply": "2025-10-26T13:26:44.959457Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "{' -> 0',\n", " ' -> 1',\n", " ' -> 2',\n", " ' -> 3',\n", " ' -> 4',\n", " ' -> 5',\n", " ' -> 6',\n", " ' -> 7',\n", " ' -> 8',\n", " ' -> 9'}" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "digit_fuzzer.max_expansion_coverage()" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "This is the missing coverage:" ] }, { "cell_type": "code", "execution_count": 25, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:44.961209Z", "iopub.status.busy": "2025-10-26T13:26:44.961096Z", "iopub.status.idle": "2025-10-26T13:26:44.963396Z", "shell.execute_reply": "2025-10-26T13:26:44.962960Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "{' -> 1',\n", " ' -> 2',\n", " ' -> 3',\n", " ' -> 4',\n", " ' -> 6',\n", " ' -> 7',\n", " ' -> 8'}" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "digit_fuzzer.missing_expansion_coverage()" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "On average, how many characters do we have to produce until all expansions are covered?" ] }, { "cell_type": "code", "execution_count": 26, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:44.965349Z", "iopub.status.busy": "2025-10-26T13:26:44.965242Z", "iopub.status.idle": "2025-10-26T13:26:44.967268Z", "shell.execute_reply": "2025-10-26T13:26:44.967025Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def average_length_until_full_coverage(fuzzer: TrackingGrammarCoverageFuzzer) -> float:\n", " trials = 50\n", "\n", " sum = 0\n", " for trial in range(trials):\n", " # print(trial, end=\" \")\n", " fuzzer.reset_coverage()\n", " while len(fuzzer.missing_expansion_coverage()) > 0:\n", " s = fuzzer.fuzz()\n", " sum += len(s)\n", "\n", " return sum / trials" ] }, { "cell_type": "code", "execution_count": 27, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:44.968550Z", "iopub.status.busy": "2025-10-26T13:26:44.968445Z", "iopub.status.idle": "2025-10-26T13:26:44.995933Z", "shell.execute_reply": "2025-10-26T13:26:44.995634Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "28.4" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "digit_fuzzer.log = False\n", "average_length_until_full_coverage(digit_fuzzer)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "For full expressions, this takes a bit longer:" ] }, { "cell_type": "code", "execution_count": 28, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:44.997471Z", "iopub.status.busy": "2025-10-26T13:26:44.997357Z", "iopub.status.idle": "2025-10-26T13:26:45.517253Z", "shell.execute_reply": "2025-10-26T13:26:45.516854Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "138.12" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "expr_fuzzer = TrackingGrammarCoverageFuzzer(EXPR_GRAMMAR)\n", "average_length_until_full_coverage(expr_fuzzer)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Covering Grammar Expansions\n", "\n", "Let us now not only track coverage, but actually _produce_ coverage. The idea is as follows:\n", "\n", "1. We determine children yet uncovered (in `uncovered_children`)\n", "2. If all children are covered, we fall back to the original method (i.e., choosing one expansion randomly)\n", "3. Otherwise, we select a child from the uncovered children and mark it as covered.\n", "\n", "To this end, we introduce a new fuzzer `SimpleGrammarCoverageFuzzer` that implements this strategy in the `choose_node_expansion()` method – the method [the `GrammarFuzzer` superclass uses to select the child to be expanded](GrammarFuzzer.ipynb)." ] }, { "cell_type": "code", "execution_count": 29, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:45.519621Z", "iopub.status.busy": "2025-10-26T13:26:45.519484Z", "iopub.status.idle": "2025-10-26T13:26:45.522850Z", "shell.execute_reply": "2025-10-26T13:26:45.522572Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class SimpleGrammarCoverageFuzzer(TrackingGrammarCoverageFuzzer):\n", " \"\"\"When choosing expansions, prefer expansions not covered.\"\"\"\n", "\n", " def choose_node_expansion(self,\n", " node: DerivationTree,\n", " children_alternatives: List[List[DerivationTree]]) -> int:\n", " \"\"\"Return index of expansion in `children_alternatives` to be selected.\n", " Picks uncovered expansions, if any.\"\"\"\n", "\n", " # Prefer uncovered expansions\n", " (symbol, children) = node\n", " uncovered_children = [c for (i, c) in enumerate(children_alternatives)\n", " if expansion_key(symbol, c)\n", " not in self.covered_expansions]\n", " index_map = [i for (i, c) in enumerate(children_alternatives)\n", " if c in uncovered_children]\n", "\n", " if len(uncovered_children) == 0:\n", " # All expansions covered - use superclass method\n", " return self.choose_covered_node_expansion(node, children_alternatives)\n", "\n", " # Select from uncovered nodes\n", " index = self.choose_uncovered_node_expansion(node, uncovered_children)\n", "\n", " return index_map[index]" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "The two methods `choose_covered_node_expansion()` and `choose_uncovered_node_expansion()` are provided for subclasses to hook in:" ] }, { "cell_type": "code", "execution_count": 30, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:45.524245Z", "iopub.status.busy": "2025-10-26T13:26:45.524147Z", "iopub.status.idle": "2025-10-26T13:26:45.526816Z", "shell.execute_reply": "2025-10-26T13:26:45.526424Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "class SimpleGrammarCoverageFuzzer(SimpleGrammarCoverageFuzzer):\n", " def choose_uncovered_node_expansion(self,\n", " node: DerivationTree,\n", " children_alternatives: List[List[DerivationTree]]) \\\n", " -> int:\n", " \"\"\"Return index of expansion in _uncovered_ `children_alternatives`\n", " to be selected.\n", " To be overloaded in subclasses.\"\"\"\n", " return TrackingGrammarCoverageFuzzer.choose_node_expansion(\n", " self, node, children_alternatives)\n", "\n", " def choose_covered_node_expansion(self,\n", " node: DerivationTree,\n", " children_alternatives: List[List[DerivationTree]]) \\\n", " -> int:\n", " \"\"\"Return index of expansion in _covered_ `children_alternatives`\n", " to be selected.\n", " To be overloaded in subclasses.\"\"\"\n", " return TrackingGrammarCoverageFuzzer.choose_node_expansion(\n", " self, node, children_alternatives)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "By returning the set of expansions covered so far, we can invoke the fuzzer multiple times, each time adding to the grammar coverage. Using the `EXPR_GRAMMAR` grammar to produce digits, for instance, the fuzzer produces one digit after the other:" ] }, { "cell_type": "code", "execution_count": 31, "metadata": { "button": false, "execution": { "iopub.execute_input": "2025-10-26T13:26:45.528368Z", "iopub.status.busy": "2025-10-26T13:26:45.528270Z", "iopub.status.idle": "2025-10-26T13:26:45.530831Z", "shell.execute_reply": "2025-10-26T13:26:45.530519Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "'5'" ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f = SimpleGrammarCoverageFuzzer(EXPR_GRAMMAR, start_symbol=\"\")\n", "f.fuzz()" ] }, { "cell_type": "code", "execution_count": 32, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:45.532417Z", "iopub.status.busy": "2025-10-26T13:26:45.532308Z", "iopub.status.idle": "2025-10-26T13:26:45.534615Z", "shell.execute_reply": "2025-10-26T13:26:45.534290Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "'2'" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f.fuzz()" ] }, { "cell_type": "code", "execution_count": 33, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:45.536102Z", "iopub.status.busy": "2025-10-26T13:26:45.536002Z", "iopub.status.idle": "2025-10-26T13:26:45.537929Z", "shell.execute_reply": "2025-10-26T13:26:45.537691Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "'1'" ] }, "execution_count": 33, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f.fuzz()" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Here's the set of covered expansions so far:" ] }, { "cell_type": "code", "execution_count": 34, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:45.539537Z", "iopub.status.busy": "2025-10-26T13:26:45.539429Z", "iopub.status.idle": "2025-10-26T13:26:45.542172Z", "shell.execute_reply": "2025-10-26T13:26:45.541912Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "{' -> 1', ' -> 2', ' -> 5'}" ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f.expansion_coverage()" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Let us fuzz some more. We see that with each iteration, we cover another expansion:" ] }, { "cell_type": "code", "execution_count": 35, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:45.543460Z", "iopub.status.busy": "2025-10-26T13:26:45.543361Z", "iopub.status.idle": "2025-10-26T13:26:45.545416Z", "shell.execute_reply": "2025-10-26T13:26:45.545110Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0 9 7 4 8 3 6 " ] } ], "source": [ "for i in range(7):\n", " print(f.fuzz(), end=\" \")" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "At the end, all expansions are covered:" ] }, { "cell_type": "code", "execution_count": 36, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:45.546869Z", "iopub.status.busy": "2025-10-26T13:26:45.546753Z", "iopub.status.idle": "2025-10-26T13:26:45.549098Z", "shell.execute_reply": "2025-10-26T13:26:45.548868Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "set()" ] }, "execution_count": 36, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f.missing_expansion_coverage()" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Let us apply this on a more complex grammar – e.g., the full expression grammar. We see that after a few iterations, we cover each and every digit, operator, and expansion:" ] }, { "cell_type": "code", "execution_count": 37, "metadata": { "button": false, "execution": { "iopub.execute_input": "2025-10-26T13:26:45.550678Z", "iopub.status.busy": "2025-10-26T13:26:45.550577Z", "iopub.status.idle": "2025-10-26T13:26:45.575973Z", "shell.execute_reply": "2025-10-26T13:26:45.575523Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "+(0.31 / (5) / 9 + 4 * 6 / 3 - 8 - 7) * -2\n", "+++2 / 87360\n", "((4) * 0 - 1) / -9.6 + 7 / 6 + 1 * 8 + 7 * 8\n", "++++26 / -64.45\n", "(8 / 1 / 6 + 9 + 7 + 8) * 1.1 / 0 * 1\n", "7.7\n", "++(3.5 / 3) - (-4 + 3) / (8 / 0) / -4 * 2 / 1\n", "+(90 / --(28 * 8 / 5 + 5 / (5 / 8))) - +9.36 / 2.5 * (5 * (7 * 6 * 5) / 8)\n", "9.11 / 7.28\n", "1 / (9 - 5 * 6) / 6 / 7 / 7 + 1 + 1 - 7 * -3\n" ] } ], "source": [ "f = SimpleGrammarCoverageFuzzer(EXPR_GRAMMAR)\n", "for i in range(10):\n", " print(f.fuzz())" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "Again, all expansions are covered:" ] }, { "cell_type": "code", "execution_count": 38, "metadata": { "button": false, "execution": { "iopub.execute_input": "2025-10-26T13:26:45.577597Z", "iopub.status.busy": "2025-10-26T13:26:45.577464Z", "iopub.status.idle": "2025-10-26T13:26:45.579755Z", "shell.execute_reply": "2025-10-26T13:26:45.579415Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "set()" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f.missing_expansion_coverage()" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "We see that our strategy is much more effective in achieving coverage than the random approach:" ] }, { "cell_type": "code", "execution_count": 39, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:45.582037Z", "iopub.status.busy": "2025-10-26T13:26:45.581881Z", "iopub.status.idle": "2025-10-26T13:26:45.868671Z", "shell.execute_reply": "2025-10-26T13:26:45.868221Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "52.28" ] }, "execution_count": 39, "metadata": {}, "output_type": "execute_result" } ], "source": [ "average_length_until_full_coverage(SimpleGrammarCoverageFuzzer(EXPR_GRAMMAR))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" }, "toc-hr-collapsed": false }, "source": [ "## Deep Foresight\n", "\n", "Selecting expansions for individual rules is a good start; however, it is not sufficient, as the following example shows. We apply our coverage fuzzer on the CGI grammar from the [chapter on grammars](Grammars.ipynb):" ] }, { "cell_type": "code", "execution_count": 40, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:45.870675Z", "iopub.status.busy": "2025-10-26T13:26:45.870545Z", "iopub.status.idle": "2025-10-26T13:26:45.873020Z", "shell.execute_reply": "2025-10-26T13:26:45.872737Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "{'': [''],\n", " '': ['', ''],\n", " '': ['', '', ''],\n", " '': ['+'],\n", " '': ['%'],\n", " '': ['0',\n", " '1',\n", " '2',\n", " '3',\n", " '4',\n", " '5',\n", " '6',\n", " '7',\n", " '8',\n", " '9',\n", " 'a',\n", " 'b',\n", " 'c',\n", " 'd',\n", " 'e',\n", " 'f'],\n", " '': ['0', '1', '2', '3', '4', '5', 'a', 'b', 'c', 'd', 'e', '-', '_']}" ] }, "execution_count": 40, "metadata": {}, "output_type": "execute_result" } ], "source": [ "CGI_GRAMMAR" ] }, { "cell_type": "code", "execution_count": 41, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:45.874920Z", "iopub.status.busy": "2025-10-26T13:26:45.874798Z", "iopub.status.idle": "2025-10-26T13:26:45.878642Z", "shell.execute_reply": "2025-10-26T13:26:45.878157Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "c\n", "+%a6++\n", "+-\n", "+\n", "++\n", "%18%b7\n", "+e\n", "_\n", "d2+%e3\n", "%d0\n" ] } ], "source": [ "f = SimpleGrammarCoverageFuzzer(CGI_GRAMMAR)\n", "for i in range(10):\n", " print(f.fuzz())" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "After 10 iterations, we still have a number of expansions uncovered:" ] }, { "cell_type": "code", "execution_count": 42, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:45.880506Z", "iopub.status.busy": "2025-10-26T13:26:45.880402Z", "iopub.status.idle": "2025-10-26T13:26:45.882909Z", "shell.execute_reply": "2025-10-26T13:26:45.882562Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "{' -> 2',\n", " ' -> 4',\n", " ' -> 5',\n", " ' -> 9',\n", " ' -> c',\n", " ' -> f',\n", " ' -> 0',\n", " ' -> 1',\n", " ' -> 3',\n", " ' -> 4',\n", " ' -> 5',\n", " ' -> a',\n", " ' -> b'}" ] }, "execution_count": 42, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f.missing_expansion_coverage()" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Why is that so? The problem is that in the CGI grammar, the largest number of variations to be covered occurs in the `hexdigit` rule. However, we first need to _reach_ this expansion. When expanding a `` symbol, we have the choice between three possible expansions:" ] }, { "cell_type": "code", "execution_count": 43, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:45.884434Z", "iopub.status.busy": "2025-10-26T13:26:45.884314Z", "iopub.status.idle": "2025-10-26T13:26:45.886677Z", "shell.execute_reply": "2025-10-26T13:26:45.886276Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "['', '', '']" ] }, "execution_count": 43, "metadata": {}, "output_type": "execute_result" } ], "source": [ "CGI_GRAMMAR[\"\"]" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "If all three expansions are covered already, then `choose_node_expansion()` above will choose one randomly – even if there may be more expansions to cover when choosing ``." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "What we need is a better strategy that will pick `` if there are more uncovered expansions following – even if `` is covered. Such a strategy was first discussed by W. Burkhardt \\cite{Burkhardt1967} under the name of \"Shortest Path Selection\":\n", "\n", "> This version selects, from several alternatives for development, that syntactic unit under which there is still an unused unit available, starting with the shortest path.\n", " \n", "This is what we will implement in the next steps." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Determining Maximum per-Symbol Coverage\n", "\n", "To address this problem, we introduce a new class `GrammarCoverageFuzzer` that builds on `SimpleGrammarCoverageFuzzer`, but with a _better strategy_. First, we need to compute the _maximum set of expansions_ that can be reached from a particular symbol, as we already have implemented in `max_expansion_coverage()`. The idea is to later compute the _intersection_ of this set and the expansions already covered, such that we can favor those expansions with a non-empty intersection." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "The first step – computing the maximum set of expansions that can be reached from a symbol – is already implemented. By passing a `symbol` parameter to `max_expansion_coverage()`, we can compute the possible expansions for every symbol:" ] }, { "cell_type": "code", "execution_count": 44, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:45.888573Z", "iopub.status.busy": "2025-10-26T13:26:45.888454Z", "iopub.status.idle": "2025-10-26T13:26:45.890617Z", "shell.execute_reply": "2025-10-26T13:26:45.890377Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "{' -> 0',\n", " ' -> 1',\n", " ' -> 2',\n", " ' -> 3',\n", " ' -> 4',\n", " ' -> 5',\n", " ' -> 6',\n", " ' -> 7',\n", " ' -> 8',\n", " ' -> 9',\n", " ' -> ',\n", " ' -> '}" ] }, "execution_count": 44, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f = SimpleGrammarCoverageFuzzer(EXPR_GRAMMAR)\n", "f.max_expansion_coverage('')" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "We see that by expanding ``, we can cover a total of 12 productions." ] }, { "cell_type": "code", "execution_count": 45, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:45.892001Z", "iopub.status.busy": "2025-10-26T13:26:45.891902Z", "iopub.status.idle": "2025-10-26T13:26:45.895334Z", "shell.execute_reply": "2025-10-26T13:26:45.895026Z" }, "slideshow": { "slide_type": "fragment" }, "tags": [ "remove-input" ] }, "outputs": [ { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " Quiz\n", " \n", " How many productions would f.max_expansion_coverage('<digit>') return?\n", " \n", " \n", " \n", " \n", " \n", " 10\n", " \n", " \n", " 11\n", " \n", " \n", " 12\n", " \n", " \n", " 13\n", " \n", " \n", " \n", " \n", " \n", " \n", " " ], "text/plain": [ "" ] }, "execution_count": 45, "metadata": {}, "output_type": "execute_result" } ], "source": [ "quiz(\"How many productions would `f.max_expansion_coverage('')` return?\",\n", " [\n", " \"10\",\n", " \"11\",\n", " \"12\",\n", " \"13\"\n", " ], \"100 / 100\")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Indeed. Here are all the possible expansions for ``:" ] }, { "cell_type": "code", "execution_count": 46, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:45.897132Z", "iopub.status.busy": "2025-10-26T13:26:45.897037Z", "iopub.status.idle": "2025-10-26T13:26:45.899185Z", "shell.execute_reply": "2025-10-26T13:26:45.898850Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "{' -> 0',\n", " ' -> 1',\n", " ' -> 2',\n", " ' -> 3',\n", " ' -> 4',\n", " ' -> 5',\n", " ' -> 6',\n", " ' -> 7',\n", " ' -> 8',\n", " ' -> 9'}" ] }, "execution_count": 46, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f.max_expansion_coverage('')" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Determining yet Uncovered Children\n", "\n", "We can now start to implement `GrammarCoverageFuzzer`. Our idea is to determine the _missing coverage_ for each child.\n", "\n", "Given a list of children, we can use `max_expansion_coverage()` to compute the maximum coverage for each child. From this, we _subtract_ the coverage already seen (`expansion_coverage()`). This results in the coverage we can still obtain." ] }, { "cell_type": "code", "execution_count": 47, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:45.900680Z", "iopub.status.busy": "2025-10-26T13:26:45.900566Z", "iopub.status.idle": "2025-10-26T13:26:45.903371Z", "shell.execute_reply": "2025-10-26T13:26:45.903131Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class GrammarCoverageFuzzer(SimpleGrammarCoverageFuzzer):\n", " \"\"\"Produce from grammars, aiming for coverage of all expansions.\"\"\"\n", "\n", " def new_child_coverage(self,\n", " symbol: str,\n", " children: List[DerivationTree],\n", " max_depth: Union[int, float] = float('inf')) -> Set[str]:\n", " \"\"\"Return new coverage that would be obtained \n", " by expanding (`symbol`, `children`)\"\"\"\n", "\n", " new_cov = self._new_child_coverage(children, max_depth)\n", " new_cov.add(expansion_key(symbol, children))\n", " new_cov -= self.expansion_coverage() # -= is set subtraction\n", " return new_cov\n", "\n", " def _new_child_coverage(self, children: List[DerivationTree],\n", " max_depth: Union[int, float]) -> Set[str]:\n", " new_cov: Set[str] = set()\n", " for (c_symbol, _) in children:\n", " if c_symbol in self.grammar:\n", " new_cov |= self.max_expansion_coverage(c_symbol, max_depth)\n", "\n", " return new_cov" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Let us illustrate `new_child_coverage()`. We again start fuzzing, choosing expansions randomly." ] }, { "cell_type": "code", "execution_count": 48, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:45.904693Z", "iopub.status.busy": "2025-10-26T13:26:45.904603Z", "iopub.status.idle": "2025-10-26T13:26:45.906884Z", "shell.execute_reply": "2025-10-26T13:26:45.906652Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Tree: \n", "Expanding randomly\n", "Now covered: -> 2\n", "Tree: 2\n", "'2'\n" ] }, { "data": { "text/plain": [ "'2'" ] }, "execution_count": 48, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f = GrammarCoverageFuzzer(EXPR_GRAMMAR, start_symbol=\"\", log=True)\n", "f.fuzz()" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "This is our current coverage:" ] }, { "cell_type": "code", "execution_count": 49, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:45.908699Z", "iopub.status.busy": "2025-10-26T13:26:45.908530Z", "iopub.status.idle": "2025-10-26T13:26:45.910740Z", "shell.execute_reply": "2025-10-26T13:26:45.910451Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "{' -> 2'}" ] }, "execution_count": 49, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f.expansion_coverage()" ] }, { "cell_type": "code", "execution_count": 50, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:45.912424Z", "iopub.status.busy": "2025-10-26T13:26:45.912306Z", "iopub.status.idle": "2025-10-26T13:26:45.913986Z", "shell.execute_reply": "2025-10-26T13:26:45.913708Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "# docassert\n", "assert f.expansion_coverage() == {' -> 2'}" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "If we want to expand `` into `0`, that would yield us new coverage:" ] }, { "cell_type": "code", "execution_count": 51, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:45.915659Z", "iopub.status.busy": "2025-10-26T13:26:45.915489Z", "iopub.status.idle": "2025-10-26T13:26:45.917769Z", "shell.execute_reply": "2025-10-26T13:26:45.917518Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "{' -> 0'}" ] }, "execution_count": 51, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f.new_child_coverage(\"\", [('0', [])])" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "If we want to expand `` into `2` again, that would yield us _no_ new coverage:" ] }, { "cell_type": "code", "execution_count": 52, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:45.919164Z", "iopub.status.busy": "2025-10-26T13:26:45.919065Z", "iopub.status.idle": "2025-10-26T13:26:45.921245Z", "shell.execute_reply": "2025-10-26T13:26:45.920964Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "set()" ] }, "execution_count": 52, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f.new_child_coverage(\"\", [('2', [])])" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "When we go through the individual expansion possibilities for ``, we see that all expansions offer additional coverage, _except_ for the `2` we have already covered." ] }, { "cell_type": "code", "execution_count": 53, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:45.922729Z", "iopub.status.busy": "2025-10-26T13:26:45.922623Z", "iopub.status.idle": "2025-10-26T13:26:45.924691Z", "shell.execute_reply": "2025-10-26T13:26:45.924444Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0 {' -> 0'}\n", "1 {' -> 1'}\n", "2 set()\n", "3 {' -> 3'}\n", "4 {' -> 4'}\n", "5 {' -> 5'}\n", "6 {' -> 6'}\n", "7 {' -> 7'}\n", "8 {' -> 8'}\n", "9 {' -> 9'}\n" ] } ], "source": [ "for expansion in EXPR_GRAMMAR[\"\"]:\n", " children = f.expansion_to_children(expansion)\n", " print(expansion, f.new_child_coverage(\"\", children))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "This means that whenever choosing an expansion, we can make use of `new_child_coverage()` and choose among the expansions that offer the greatest new (unseen) coverage." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Adaptive Lookahead" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "When choosing a child, we do not look out for the maximum overall coverage to be obtained, as this would have expansions with many uncovered possibilities totally dominate other expansions. Instead, we aim for a _breadth-first_ strategy, first covering all expansions up to a given depth, and only then looking for a greater depth." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "The method `new_coverages()` is at the heart of this strategy: Starting with a maximum depth (`max_depth`) of zero, it increases the depth until it finds at least one uncovered expansion." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "#### Excursion: Implementing `new_coverage()`" ] }, { "cell_type": "code", "execution_count": 54, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:45.926293Z", "iopub.status.busy": "2025-10-26T13:26:45.926189Z", "iopub.status.idle": "2025-10-26T13:26:45.928794Z", "shell.execute_reply": "2025-10-26T13:26:45.928391Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class GrammarCoverageFuzzer(GrammarCoverageFuzzer):\n", " def new_coverages(self, node: DerivationTree,\n", " children_alternatives: List[List[DerivationTree]]) \\\n", " -> Optional[List[Set[str]]]:\n", " \"\"\"Return coverage to be obtained for each child at minimum depth\"\"\"\n", "\n", " (symbol, children) = node\n", " for max_depth in range(len(self.grammar)):\n", " new_coverages = [\n", " self.new_child_coverage(\n", " symbol, c, max_depth) for c in children_alternatives]\n", " max_new_coverage = max(len(new_coverage)\n", " for new_coverage in new_coverages)\n", " if max_new_coverage > 0:\n", " # Uncovered node found\n", " return new_coverages\n", "\n", " # All covered\n", " return None" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "#### End of Excursion" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### All Together\n", "\n", "We can now define `choose_node_expansion()` to make use of this strategy:\n", "1. We determine the possible coverages to be obtained (using `new_coverages()`)\n", "2. We (randomly) select among the children which sport the maximum coverage (using `choose_uncovered_node_expansion()`)." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "#### Excursion: Implementing `choose_node_expansion()`" ] }, { "cell_type": "code", "execution_count": 55, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:45.930655Z", "iopub.status.busy": "2025-10-26T13:26:45.930536Z", "iopub.status.idle": "2025-10-26T13:26:45.933640Z", "shell.execute_reply": "2025-10-26T13:26:45.933346Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class GrammarCoverageFuzzer(GrammarCoverageFuzzer):\n", " def choose_node_expansion(self, node: DerivationTree,\n", " children_alternatives: List[List[DerivationTree]]) -> int:\n", " \"\"\"Choose an expansion of `node` among `children_alternatives`.\n", " Return `n` such that expanding `children_alternatives[n]`\n", " yields the highest additional coverage.\"\"\"\n", "\n", " (symbol, children) = node\n", " new_coverages = self.new_coverages(node, children_alternatives)\n", "\n", " if new_coverages is None:\n", " # All expansions covered - use superclass method\n", " return self.choose_covered_node_expansion(node, children_alternatives)\n", "\n", " max_new_coverage = max(len(cov) for cov in new_coverages)\n", "\n", " children_with_max_new_coverage = [c for (i, c) in enumerate(children_alternatives)\n", " if len(new_coverages[i]) == max_new_coverage]\n", " index_map = [i for (i, c) in enumerate(children_alternatives)\n", " if len(new_coverages[i]) == max_new_coverage]\n", "\n", " # Select a random expansion\n", " new_children_index = self.choose_uncovered_node_expansion(\n", " node, children_with_max_new_coverage)\n", " new_children = children_with_max_new_coverage[new_children_index]\n", "\n", " # Save the expansion as covered\n", " key = expansion_key(symbol, new_children)\n", "\n", " if self.log:\n", " print(\"Now covered:\", key)\n", " self.covered_expansions.add(key)\n", "\n", " return index_map[new_children_index]" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "#### End of Excursion" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "With this, our `GrammarCoverageFuzzer` is now complete! Let us apply it on a series of examples. On expressions, it quickly covers all digits and operators:" ] }, { "cell_type": "code", "execution_count": 56, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:45.935239Z", "iopub.status.busy": "2025-10-26T13:26:45.935126Z", "iopub.status.idle": "2025-10-26T13:26:45.939788Z", "shell.execute_reply": "2025-10-26T13:26:45.939482Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "'-4.02 / (1) * +3 + 5.9 / 7 * 8 - 6'" ] }, "execution_count": 56, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f = GrammarCoverageFuzzer(EXPR_GRAMMAR, min_nonterminals=3)\n", "f.fuzz()" ] }, { "cell_type": "code", "execution_count": 57, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:45.940994Z", "iopub.status.busy": "2025-10-26T13:26:45.940892Z", "iopub.status.idle": "2025-10-26T13:26:45.943327Z", "shell.execute_reply": "2025-10-26T13:26:45.942956Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "set()" ] }, "execution_count": 57, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f.max_expansion_coverage() - f.expansion_coverage()" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "On average, it is again faster than the simple strategy:" ] }, { "cell_type": "code", "execution_count": 58, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:45.944830Z", "iopub.status.busy": "2025-10-26T13:26:45.944714Z", "iopub.status.idle": "2025-10-26T13:26:46.267381Z", "shell.execute_reply": "2025-10-26T13:26:46.267090Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "50.74" ] }, "execution_count": 58, "metadata": {}, "output_type": "execute_result" } ], "source": [ "average_length_until_full_coverage(GrammarCoverageFuzzer(EXPR_GRAMMAR))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "On the CGI grammar, it takes but a few iterations to cover all letters and digits:" ] }, { "cell_type": "code", "execution_count": 59, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:46.269075Z", "iopub.status.busy": "2025-10-26T13:26:46.268952Z", "iopub.status.idle": "2025-10-26T13:26:46.282287Z", "shell.execute_reply": "2025-10-26T13:26:46.282011Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "%18%d03\n", "%c3%94%7f+cd\n", "%a6%b5%e2%5e%4c-54e01a2\n", "%5eb%7cb_ec%a0+\n" ] } ], "source": [ "f = GrammarCoverageFuzzer(CGI_GRAMMAR, min_nonterminals=5)\n", "while len(f.max_expansion_coverage() - f.expansion_coverage()) > 0:\n", " print(f.fuzz())" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "This improvement can also be seen in comparing the random, expansion-only, and deep foresight strategies on the CGI grammar:" ] }, { "cell_type": "code", "execution_count": 60, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:46.284037Z", "iopub.status.busy": "2025-10-26T13:26:46.283930Z", "iopub.status.idle": "2025-10-26T13:26:46.805374Z", "shell.execute_reply": "2025-10-26T13:26:46.805093Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "211.34" ] }, "execution_count": 60, "metadata": {}, "output_type": "execute_result" } ], "source": [ "average_length_until_full_coverage(TrackingGrammarCoverageFuzzer(CGI_GRAMMAR))" ] }, { "cell_type": "code", "execution_count": 61, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:46.806888Z", "iopub.status.busy": "2025-10-26T13:26:46.806782Z", "iopub.status.idle": "2025-10-26T13:26:47.001784Z", "shell.execute_reply": "2025-10-26T13:26:47.001469Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "68.64" ] }, "execution_count": 61, "metadata": {}, "output_type": "execute_result" } ], "source": [ "average_length_until_full_coverage(SimpleGrammarCoverageFuzzer(CGI_GRAMMAR))" ] }, { "cell_type": "code", "execution_count": 62, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:47.003414Z", "iopub.status.busy": "2025-10-26T13:26:47.003291Z", "iopub.status.idle": "2025-10-26T13:26:47.230647Z", "shell.execute_reply": "2025-10-26T13:26:47.230340Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "40.38" ] }, "execution_count": 62, "metadata": {}, "output_type": "execute_result" } ], "source": [ "average_length_until_full_coverage(GrammarCoverageFuzzer(CGI_GRAMMAR))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" }, "toc-hr-collapsed": true, "toc-nb-collapsed": true }, "source": [ "## Coverage in Context\n", "\n", "Sometimes, grammar elements are used in more than just one place. In our expression grammar, for instance, the `` symbol is used for integer numbers as well as for floating point numbers:" ] }, { "cell_type": "code", "execution_count": 63, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:26:47.232181Z", "iopub.status.busy": "2025-10-26T13:26:47.232070Z", "iopub.status.idle": "2025-10-26T13:26:47.234085Z", "shell.execute_reply": "2025-10-26T13:26:47.233872Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "['+', '-', '()', '.
\n", "
EXPR_GRAMMAR
1 + 2
<start> -> <expr>
<integer> -> <digit><integer>
<integer> -> <digit>
<factor> -> +<factor>
f.max_expansion_coverage('<digit>')