{ "cells": [ { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "# Greybox Fuzzing with Grammars\n", "\n", "In this chapter, we introduce important extensions to our syntactic fuzzing techniques, all leveraging _syntactic_ parts of _existing inputs_.\n", "\n", "1. We show how to leverage _dictionaries_ of input fragments during fuzzing. The idea is to integrate such dictionaries into a _mutator_, which would then inject these fragments (typically keywords and other items of importance) into population.\n", "\n", "2. We show how to combine [parsing](Parser.ipynb) and [fuzzing](GrammarFuzzer.ipynb) with grammars. This allows _mutating_ existing inputs while preserving syntactical correctness, and to _reuse_ fragments from existing inputs while generating new ones. The combination of language-based parsing and generating, as demonstrated in this chapter, has been highly successful in practice: The _LangFuzz_ fuzzer for JavaScript has found more than 2,600 bugs in JavaScript interpreters this way.\n", "\n", "3. In the previous chapters, we have used grammars in a _black-box_ manner – that is, we have used them to generate inputs regardless of the program being tested. In this chapter, we introduce mutational _greybox fuzzing with grammars_: Techniques that make use of _feedback from the program under test_ to guide test generations towards specific goals. As in [lexical greybox fuzzing](GreyboxFuzzer.ipynb), this feedback is mostly _coverage_, allowing us to direct grammar-based testing towards uncovered code parts. This part is inspired by the _AFLSmart_ fuzzer, which combines parsing and mutational fuzzing." ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:45.273027Z", "iopub.status.busy": "2025-10-26T13:27:45.272637Z", "iopub.status.idle": "2025-10-26T13:27:45.987826Z", "shell.execute_reply": "2025-10-26T13:27:45.987453Z" }, "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('hSGzcjUj7Vs')" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "**Prerequisites**\n", "\n", "* We build on several concepts from [the chapter on greybox fuzzing (without grammars)](GreyboxFuzzer.ipynb).\n", "* As the title suggests, you should know how to fuzz with grammars [from the chapter on grammars](Grammars.ipynb)." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" }, "tags": [] }, "source": [ "## Synopsis\n", "To [use the code provided in this chapter](Importing.ipynb), write\n", "\n", "```python\n", ">>> from fuzzingbook.GreyboxGrammarFuzzer 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" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Fuzzing with Dictionaries\n", "\n", "Rather than mutating strings randomly, the `DictMutator` class allows inserting tokens from a dictionary, thus increasing fuzzer performance. The dictionary comes as a list of strings, out of which random elements are picked and inserted - in addition to the given mutations such as deleting or inserting individual bytes." ] }, { "cell_type": "code", "execution_count": 73, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:29:02.360850Z", "iopub.status.busy": "2025-10-26T13:29:02.360728Z", "iopub.status.idle": "2025-10-26T13:29:02.362629Z", "shell.execute_reply": "2025-10-26T13:29:02.362330Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "dict_mutator = DictMutator([\"\", \"\", \"\", \"='a'\"])" ] }, { "cell_type": "code", "execution_count": 74, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:29:02.363905Z", "iopub.status.busy": "2025-10-26T13:29:02.363805Z", "iopub.status.idle": "2025-10-26T13:29:02.366119Z", "shell.execute_reply": "2025-10-26T13:29:02.365704Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "HelloWorld
HelloWorld
\n", "='a'HelloWorld
\n", "Hello</pitle></head><body>World<br/></body></html>\n", "<html><head><tivtle>HelloWorld
\n", "HelloWorld
\n", "HelloWorld
\n", "Hello</tictle></head><body>World<br/></body></html>\n", "<html><head><title>Hello</ti='a'tle></head><body>World<br/></body></html>\n", "<html6<head><title>HelloWorld
\n" ] } ], "source": [ "seeds = [\"HelloWorld
\"]\n", "for i in range(10):\n", " print(dict_mutator.mutate(seeds[0]))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "This `DictMutator` can be used as an argument to `GreyboxFuzzer`:" ] }, { "cell_type": "code", "execution_count": 75, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:29:02.367805Z", "iopub.status.busy": "2025-10-26T13:29:02.367652Z", "iopub.status.idle": "2025-10-26T13:29:02.402294Z", "shell.execute_reply": "2025-10-26T13:29:02.401834Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "runner = FunctionCoverageRunner(my_parser)\n", "dict_fuzzer = GreyboxFuzzer(seeds, dict_mutator, PowerSchedule())" ] }, { "cell_type": "code", "execution_count": 76, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:29:02.404157Z", "iopub.status.busy": "2025-10-26T13:29:02.404011Z", "iopub.status.idle": "2025-10-26T13:29:02.407833Z", "shell.execute_reply": "2025-10-26T13:29:02.407293Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "dict_fuzzer_outcome = dict_fuzzer.runs(runner, trials=5)" ] }, { "cell_type": "code", "execution_count": 77, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:29:02.409654Z", "iopub.status.busy": "2025-10-26T13:29:02.409542Z", "iopub.status.idle": "2025-10-26T13:29:02.411446Z", "shell.execute_reply": "2025-10-26T13:29:02.411141Z" }, "slideshow": { "slide_type": "fragment" }, "tags": [ "remove-input" ] }, "outputs": [], "source": [ "# ignore\n", "from ClassDiagram import display_class_hierarchy\n", "from Coverage import Location # minor dependency" ] }, { "cell_type": "code", "execution_count": 78, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:29:02.412916Z", "iopub.status.busy": "2025-10-26T13:29:02.412805Z", "iopub.status.idle": "2025-10-26T13:29:03.515017Z", "shell.execute_reply": "2025-10-26T13:29:03.514360Z" }, "slideshow": { "slide_type": "subslide" }, "tags": [ "remove-input" ] }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "DictMutator\n", "\n", "\n", "DictMutator\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "insert_from_dictionary()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "Mutator\n", "\n", "\n", "Mutator\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "DictMutator->Mutator\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", "DictMutator\n", "\n", "\n", "DictMutator\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "insert_from_dictionary()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "Mutator\n", "\n", "\n", "Mutator\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "DictMutator->Mutator\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": 78, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# ignore\n", "display_class_hierarchy([DictMutator],\n", " public_methods=[\n", " Mutator.__init__,\n", " DictMutator.__init__,\n", " ],\n", " types={'DerivationTree': DerivationTree,\n", " 'Location': Location},\n", " project='fuzzingbook')" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Fuzzing with Input Fragments\n", "\n", "The `LangFuzzer` class introduces a _language-aware_ fuzzer that can recombine fragments from existing inputs – inspired by the highly effective `LangFuzz` fuzzer. At its core is a `FragmentMutator` class that that takes a [_parser_](Parser.ipynb) as argument:" ] }, { "cell_type": "code", "execution_count": 79, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:29:03.516858Z", "iopub.status.busy": "2025-10-26T13:29:03.516653Z", "iopub.status.idle": "2025-10-26T13:29:03.519186Z", "shell.execute_reply": "2025-10-26T13:29:03.518879Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "parser = EarleyParser(XML_GRAMMAR, tokens=XML_TOKENS)\n", "mutator = FragmentMutator(parser)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "The fuzzer itself is initialized with a list of seeds, the above `FragmentMutator`, and a power schedule:" ] }, { "cell_type": "code", "execution_count": 80, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:29:03.520791Z", "iopub.status.busy": "2025-10-26T13:29:03.520680Z", "iopub.status.idle": "2025-10-26T13:29:03.524618Z", "shell.execute_reply": "2025-10-26T13:29:03.524298Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "seeds = [\"HelloWorld
\"]\n", "schedule = PowerSchedule()\n", "lang_fuzzer = LangFuzzer(seeds, mutator, schedule)" ] }, { "cell_type": "code", "execution_count": 81, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:29:03.526510Z", "iopub.status.busy": "2025-10-26T13:29:03.526399Z", "iopub.status.idle": "2025-10-26T13:29:03.889118Z", "shell.execute_reply": "2025-10-26T13:29:03.888794Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "HelloWorld
\n", "HelloWorld
\n", "HelloWorld
\n", "HelloWorld
\n", "WorldWorld\n", "WorldWorld\n", "HelloWorld\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "World\n", "HelloWorld\n", "<head><title>HelloWorld
\n" ] } ], "source": [ "for i in range(10):\n", " print(lang_fuzzer.fuzz())" ] }, { "cell_type": "code", "execution_count": 82, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:29:03.890495Z", "iopub.status.busy": "2025-10-26T13:29:03.890408Z", "iopub.status.idle": "2025-10-26T13:29:04.749473Z", "shell.execute_reply": "2025-10-26T13:29:04.749032Z" }, "slideshow": { "slide_type": "subslide" }, "tags": [ "remove-input" ] }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "LangFuzzer\n", "\n", "\n", "LangFuzzer\n", "\n", "\n", "\n", "create_candidate()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "AdvancedMutationFuzzer\n", "\n", "\n", "AdvancedMutationFuzzer\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "fuzz()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "LangFuzzer->AdvancedMutationFuzzer\n", "\n", "\n", "\n", "\n", "\n", "Fuzzer\n", "\n", "\n", "Fuzzer\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "fuzz()\n", "\n", "\n", "\n", "run()\n", "\n", "\n", "\n", "runs()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "AdvancedMutationFuzzer->Fuzzer\n", "\n", "\n", "\n", "\n", "\n", "FragmentMutator\n", "\n", "\n", "FragmentMutator\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "add_to_fragment_pool()\n", "\n", "\n", "\n", "add_fragment()\n", "\n", "\n", "\n", "count_nodes()\n", "\n", "\n", "\n", "delete_fragment()\n", "\n", "\n", "\n", "is_excluded()\n", "\n", "\n", "\n", "mutate()\n", "\n", "\n", "\n", "recursive_delete()\n", "\n", "\n", "\n", "recursive_swap()\n", "\n", "\n", "\n", "swap_fragment()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "Mutator\n", "\n", "\n", "Mutator\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "FragmentMutator->Mutator\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", "LangFuzzer\n", "\n", "\n", "LangFuzzer\n", "\n", "\n", "\n", "create_candidate()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "AdvancedMutationFuzzer\n", "\n", "\n", "AdvancedMutationFuzzer\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "fuzz()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "LangFuzzer->AdvancedMutationFuzzer\n", "\n", "\n", "\n", "\n", "\n", "Fuzzer\n", "\n", "\n", "Fuzzer\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "fuzz()\n", "\n", "\n", "\n", "run()\n", "\n", "\n", "\n", "runs()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "AdvancedMutationFuzzer->Fuzzer\n", "\n", "\n", "\n", "\n", "\n", "FragmentMutator\n", "\n", "\n", "FragmentMutator\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "add_to_fragment_pool()\n", "\n", "\n", "\n", "add_fragment()\n", "\n", "\n", "\n", "count_nodes()\n", "\n", "\n", "\n", "delete_fragment()\n", "\n", "\n", "\n", "is_excluded()\n", "\n", "\n", "\n", "mutate()\n", "\n", "\n", "\n", "recursive_delete()\n", "\n", "\n", "\n", "recursive_swap()\n", "\n", "\n", "\n", "swap_fragment()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "Mutator\n", "\n", "\n", "Mutator\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "FragmentMutator->Mutator\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": 82, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# ignore\n", "display_class_hierarchy([LangFuzzer, FragmentMutator],\n", " public_methods=[\n", " Fuzzer.__init__,\n", " Fuzzer.fuzz,\n", " Fuzzer.run,\n", " Fuzzer.runs,\n", " AdvancedMutationFuzzer.__init__,\n", " AdvancedMutationFuzzer.fuzz,\n", " GreyboxFuzzer.run,\n", " Mutator.__init__,\n", " FragmentMutator.__init__,\n", " FragmentMutator.add_to_fragment_pool,\n", " ],\n", " types={'DerivationTree': DerivationTree,\n", " 'Location': Location},\n", " project='fuzzingbook')" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Fuzzing with Input Regions\n", "\n", "The `GreyboxGrammarFuzzer` class uses two mutators:\n", "* a _tree mutator_ (a `RegionMutator` object) that can parse existing strings to identify _regions_ in that string to be swapped or deleted.\n", "* a _byte mutator_ to apply bit- and character-level mutations." ] }, { "cell_type": "code", "execution_count": 83, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:29:04.751208Z", "iopub.status.busy": "2025-10-26T13:29:04.751058Z", "iopub.status.idle": "2025-10-26T13:29:04.753299Z", "shell.execute_reply": "2025-10-26T13:29:04.752974Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "tree_mutator = RegionMutator(parser)\n", "byte_mutator = Mutator()" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "The _schedule_ for the `GreyboxGrammarFuzzer` class can be a regular `PowerSchedule` object. However, a more sophisticated schedule is provided by `AFLSmartSchedule`, which assigns more [energy](GreyboxFuzzer.ipynb#Power-Schedules) to seeds that have a higher degree of validity." ] }, { "cell_type": "code", "execution_count": 84, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:29:04.754874Z", "iopub.status.busy": "2025-10-26T13:29:04.754761Z", "iopub.status.idle": "2025-10-26T13:29:04.756651Z", "shell.execute_reply": "2025-10-26T13:29:04.756287Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "schedule = AFLSmartSchedule(parser)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "The `GreyboxGrammarFuzzer` constructor takes a set of seeds as well as the two mutators and the schedule:" ] }, { "cell_type": "code", "execution_count": 85, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:29:04.758092Z", "iopub.status.busy": "2025-10-26T13:29:04.757976Z", "iopub.status.idle": "2025-10-26T13:29:04.762072Z", "shell.execute_reply": "2025-10-26T13:29:04.761754Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "aflsmart_fuzzer = GreyboxGrammarFuzzer(seeds, byte_mutator, tree_mutator, schedule)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "As it relies on code coverage, it is typically combined with a `FunctionCoverageRunner`:" ] }, { "cell_type": "code", "execution_count": 86, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:29:04.763470Z", "iopub.status.busy": "2025-10-26T13:29:04.763374Z", "iopub.status.idle": "2025-10-26T13:29:05.010321Z", "shell.execute_reply": "2025-10-26T13:29:05.009948Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "runner = FunctionCoverageRunner(my_parser)\n", "aflsmart_outcome = aflsmart_fuzzer.runs(runner, trials=5)" ] }, { "cell_type": "code", "execution_count": 87, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:29:05.012584Z", "iopub.status.busy": "2025-10-26T13:29:05.012409Z", "iopub.status.idle": "2025-10-26T13:29:05.979692Z", "shell.execute_reply": "2025-10-26T13:29:05.979273Z" }, "slideshow": { "slide_type": "subslide" }, "tags": [ "remove-input" ] }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "GreyboxGrammarFuzzer\n", "\n", "\n", "GreyboxGrammarFuzzer\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "create_candidate()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "GreyboxFuzzer\n", "\n", "\n", "GreyboxFuzzer\n", "\n", "\n", "\n", "run()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "GreyboxGrammarFuzzer->GreyboxFuzzer\n", "\n", "\n", "\n", "\n", "\n", "AdvancedMutationFuzzer\n", "\n", "\n", "AdvancedMutationFuzzer\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "fuzz()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "GreyboxFuzzer->AdvancedMutationFuzzer\n", "\n", "\n", "\n", "\n", "\n", "Fuzzer\n", "\n", "\n", "Fuzzer\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "fuzz()\n", "\n", "\n", "\n", "run()\n", "\n", "\n", "\n", "runs()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "AdvancedMutationFuzzer->Fuzzer\n", "\n", "\n", "\n", "\n", "\n", "AFLSmartSchedule\n", "\n", "\n", "AFLSmartSchedule\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "assignEnergy()\n", "\n", "\n", "\n", "degree_of_validity()\n", "\n", "\n", "\n", "parsable()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "PowerSchedule\n", "\n", "\n", "PowerSchedule\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "AFLSmartSchedule->PowerSchedule\n", "\n", "\n", "\n", "\n", "\n", "RegionMutator\n", "\n", "\n", "RegionMutator\n", "\n", "\n", "\n", "add_to_fragment_pool()\n", "\n", "\n", "\n", "delete_fragment()\n", "\n", "\n", "\n", "swap_fragment()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "FragmentMutator\n", "\n", "\n", "FragmentMutator\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "add_to_fragment_pool()\n", "\n", "\n", "\n", "add_fragment()\n", "\n", "\n", "\n", "count_nodes()\n", "\n", "\n", "\n", "delete_fragment()\n", "\n", "\n", "\n", "is_excluded()\n", "\n", "\n", "\n", "mutate()\n", "\n", "\n", "\n", "recursive_delete()\n", "\n", "\n", "\n", "recursive_swap()\n", "\n", "\n", "\n", "swap_fragment()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "RegionMutator->FragmentMutator\n", "\n", "\n", "\n", "\n", "\n", "Mutator\n", "\n", "\n", "Mutator\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "FragmentMutator->Mutator\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", "GreyboxGrammarFuzzer\n", "\n", "\n", "GreyboxGrammarFuzzer\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "create_candidate()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "GreyboxFuzzer\n", "\n", "\n", "GreyboxFuzzer\n", "\n", "\n", "\n", "run()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "GreyboxGrammarFuzzer->GreyboxFuzzer\n", "\n", "\n", "\n", "\n", "\n", "AdvancedMutationFuzzer\n", "\n", "\n", "AdvancedMutationFuzzer\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "fuzz()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "GreyboxFuzzer->AdvancedMutationFuzzer\n", "\n", "\n", "\n", "\n", "\n", "Fuzzer\n", "\n", "\n", "Fuzzer\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "fuzz()\n", "\n", "\n", "\n", "run()\n", "\n", "\n", "\n", "runs()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "AdvancedMutationFuzzer->Fuzzer\n", "\n", "\n", "\n", "\n", "\n", "AFLSmartSchedule\n", "\n", "\n", "AFLSmartSchedule\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "assignEnergy()\n", "\n", "\n", "\n", "degree_of_validity()\n", "\n", "\n", "\n", "parsable()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "PowerSchedule\n", "\n", "\n", "PowerSchedule\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "AFLSmartSchedule->PowerSchedule\n", "\n", "\n", "\n", "\n", "\n", "RegionMutator\n", "\n", "\n", "RegionMutator\n", "\n", "\n", "\n", "add_to_fragment_pool()\n", "\n", "\n", "\n", "delete_fragment()\n", "\n", "\n", "\n", "swap_fragment()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "FragmentMutator\n", "\n", "\n", "FragmentMutator\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "add_to_fragment_pool()\n", "\n", "\n", "\n", "add_fragment()\n", "\n", "\n", "\n", "count_nodes()\n", "\n", "\n", "\n", "delete_fragment()\n", "\n", "\n", "\n", "is_excluded()\n", "\n", "\n", "\n", "mutate()\n", "\n", "\n", "\n", "recursive_delete()\n", "\n", "\n", "\n", "recursive_swap()\n", "\n", "\n", "\n", "swap_fragment()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "RegionMutator->FragmentMutator\n", "\n", "\n", "\n", "\n", "\n", "Mutator\n", "\n", "\n", "Mutator\n", "\n", "\n", "\n", "__init__()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "FragmentMutator->Mutator\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": 87, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# ignore\n", "display_class_hierarchy([GreyboxGrammarFuzzer, AFLSmartSchedule, RegionMutator],\n", " public_methods=[\n", " Fuzzer.__init__,\n", " Fuzzer.fuzz,\n", " Fuzzer.run,\n", " Fuzzer.runs,\n", " AdvancedMutationFuzzer.__init__,\n", " AdvancedMutationFuzzer.fuzz,\n", " GreyboxFuzzer.run,\n", " GreyboxGrammarFuzzer.__init__,\n", " GreyboxGrammarFuzzer.run,\n", " AFLSmartSchedule.__init__,\n", " PowerSchedule.__init__,\n", " Mutator.__init__,\n", " FragmentMutator.__init__,\n", " FragmentMutator.add_to_fragment_pool,\n", " RegionMutator.__init__,\n", " ],\n", " types={'DerivationTree': DerivationTree,\n", " 'Location': Location},\n", " project='fuzzingbook')" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Background\n", "First, we [recall](GreyboxFuzzer.ipynb#Ingredients-for-Greybox-Fuzzing) a few basic ingredients for mutational fuzzers.\n", "* **Seed**. A _seed_ is an input that is used by the fuzzer to generate new inputs by applying a sequence of mutations.\n", "* **Mutator**. A _mutator_ implements a set of mutation operators that applied to an input produce a slightly modified input.\n", "* **PowerSchedule**. A _power schedule_ assigns _energy_ to a seed. A seed with higher energy is fuzzed more often throughout the fuzzing campaign.\n", "* **AdvancedMutationFuzzer**. Our _mutational blackbox fuzzer_ generates inputs by mutating seeds in an initial population of inputs.\n", "* **GreyboxFuzzer**. Our _greybox fuzzer_ dynamically adds inputs to the population of seeds that increased coverage.\n", "* **FunctionCoverageRunner**. Our _function coverage runner_ collects coverage information for the execution of a given Python function.\n", "\n", "Let's try to get a feeling for these concepts." ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:46.009679Z", "iopub.status.busy": "2025-10-26T13:27:46.009537Z", "iopub.status.idle": "2025-10-26T13:27:46.011857Z", "shell.execute_reply": "2025-10-26T13:27:46.011552Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import bookutils.setup" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:46.013529Z", "iopub.status.busy": "2025-10-26T13:27:46.013401Z", "iopub.status.idle": "2025-10-26T13:27:46.015442Z", "shell.execute_reply": "2025-10-26T13:27:46.014951Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from typing import List, Set, Dict, Sequence, cast" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:46.016885Z", "iopub.status.busy": "2025-10-26T13:27:46.016775Z", "iopub.status.idle": "2025-10-26T13:27:46.583336Z", "shell.execute_reply": "2025-10-26T13:27:46.582942Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from Fuzzer import Fuzzer\n", "from GreyboxFuzzer import Mutator, Seed, PowerSchedule\n", "from GreyboxFuzzer import AdvancedMutationFuzzer, GreyboxFuzzer\n", "from MutationFuzzer import FunctionCoverageRunner" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "The following command applies a mutation to the input \"Hello World\"." ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:46.585994Z", "iopub.status.busy": "2025-10-26T13:27:46.585798Z", "iopub.status.idle": "2025-10-26T13:27:46.588655Z", "shell.execute_reply": "2025-10-26T13:27:46.588238Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "'Lello World'" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Mutator().mutate(\"Hello World\")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "The default power schedule assigns energy uniformly across all seeds. Let's check whether this works.\n", "\n", "We choose 10k times from a population of three seeds. As we see in the `hits` counter, each seed is chosen about a third of the time." ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:46.591083Z", "iopub.status.busy": "2025-10-26T13:27:46.590924Z", "iopub.status.idle": "2025-10-26T13:27:46.610590Z", "shell.execute_reply": "2025-10-26T13:27:46.610241Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "{'A': 3387, 'B': 3255, 'C': 3358}" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "population = [Seed(\"A\"), Seed(\"B\"), Seed(\"C\")]\n", "schedule = PowerSchedule()\n", "hits = {\n", " \"A\": 0,\n", " \"B\": 0,\n", " \"C\": 0\n", "}\n", "\n", "for i in range(10000):\n", " seed = schedule.choose(population)\n", " hits[seed.data] += 1\n", "\n", "hits" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Before explaining the function coverage runner, lets import Python's HTML parser as example..." ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:46.612426Z", "iopub.status.busy": "2025-10-26T13:27:46.612268Z", "iopub.status.idle": "2025-10-26T13:27:46.614129Z", "shell.execute_reply": "2025-10-26T13:27:46.613758Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from html.parser import HTMLParser" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "... and create a _wrapper function_ that passes each input into a new parser object." ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:46.615839Z", "iopub.status.busy": "2025-10-26T13:27:46.615725Z", "iopub.status.idle": "2025-10-26T13:27:46.617577Z", "shell.execute_reply": "2025-10-26T13:27:46.617221Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def my_parser(inp: str) -> None:\n", " parser = HTMLParser()\n", " parser.feed(inp)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "The `FunctionCoverageRunner` constructor takes a Python `function` to execute. The function `run()` takes an input, passes it on to the Python `function`, and collects the coverage information for this execution. The function `coverage()` returns a list of tuples `(function name, line number)` for each statement that has been covered in the Python `function`." ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:46.619217Z", "iopub.status.busy": "2025-10-26T13:27:46.619101Z", "iopub.status.idle": "2025-10-26T13:27:46.622476Z", "shell.execute_reply": "2025-10-26T13:27:46.622075Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "[('reset', 119),\n", " ('goahead', 263),\n", " ('unescape', 130),\n", " ('__init__', 112),\n", " ('goahead', 156)]" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "runner = FunctionCoverageRunner(my_parser)\n", "runner.run(\"Hello World\")\n", "cov = runner.coverage()\n", "\n", "list(cov)[:5] # Print 5 statements covered in HTMLParser" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Our greybox fuzzer takes a seed population, mutator, and power schedule. Let's generate 5000 fuzz inputs starting with an \"empty\" seed corpus." ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:46.624365Z", "iopub.status.busy": "2025-10-26T13:27:46.624256Z", "iopub.status.idle": "2025-10-26T13:27:46.626208Z", "shell.execute_reply": "2025-10-26T13:27:46.625710Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import time\n", "import random" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:46.627664Z", "iopub.status.busy": "2025-10-26T13:27:46.627563Z", "iopub.status.idle": "2025-10-26T13:27:46.629461Z", "shell.execute_reply": "2025-10-26T13:27:46.629169Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "n = 5000\n", "seed_input = \" \" # empty seed\n", "runner = FunctionCoverageRunner(my_parser)\n", "fuzzer = GreyboxFuzzer([seed_input], Mutator(), PowerSchedule())" ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:46.630869Z", "iopub.status.busy": "2025-10-26T13:27:46.630771Z", "iopub.status.idle": "2025-10-26T13:27:47.613135Z", "shell.execute_reply": "2025-10-26T13:27:47.612290Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "start = time.time()\n", "fuzzer.runs(runner, trials=n)\n", "end = time.time()" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:47.615853Z", "iopub.status.busy": "2025-10-26T13:27:47.615684Z", "iopub.status.idle": "2025-10-26T13:27:47.618143Z", "shell.execute_reply": "2025-10-26T13:27:47.617794Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "'It took the fuzzer 0.98 seconds to generate and execute 5000 inputs.'" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "\"It took the fuzzer %0.2f seconds to generate and execute %d inputs.\" % (end - start, n)" ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:47.619933Z", "iopub.status.busy": "2025-10-26T13:27:47.619798Z", "iopub.status.idle": "2025-10-26T13:27:47.622331Z", "shell.execute_reply": "2025-10-26T13:27:47.621963Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "'During this fuzzing campaign, we covered 75 statements.'" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "\"During this fuzzing campaign, we covered %d statements.\" % len(runner.coverage())" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Fuzzing with Dictionaries\n", "\n", "To fuzz our HTML parser, it may be useful to inform a mutational fuzzer about important keywords in the input – that is, important HTML keywords. The general idea is to have a _dictionary_ of pre-defined useful inputs that could then be inserted as such when mutating an input.\n", "\n", "This concept is illustrated in the following diagram. When mutating an input, we may insert given keywords from the dictionary (in red).\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "To implement this concept, we extend our mutator to consider keywords from a dictionary." ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:47.624785Z", "iopub.status.busy": "2025-10-26T13:27:47.624591Z", "iopub.status.idle": "2025-10-26T13:27:47.628561Z", "shell.execute_reply": "2025-10-26T13:27:47.627840Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class DictMutator(Mutator):\n", " \"\"\"Mutate strings using keywords from a dictionary\"\"\"\n", "\n", " def __init__(self, dictionary: List[str]) -> None:\n", " \"\"\"Constructor. `dictionary` is the list of keywords to use.\"\"\"\n", " super().__init__()\n", " self.dictionary = dictionary\n", " self.mutators.append(self.insert_from_dictionary)\n", "\n", " def insert_from_dictionary(self, s: str) -> str:\n", " \"\"\"Returns s with a keyword from the dictionary inserted\"\"\"\n", " pos = random.randint(0, len(s))\n", " random_keyword = random.choice(self.dictionary)\n", " return s[:pos] + random_keyword + s[pos:]" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Let's try to add a few HTML tags and attributes and see whether the coverage with `DictMutator` increases." ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:47.630868Z", "iopub.status.busy": "2025-10-26T13:27:47.630762Z", "iopub.status.idle": "2025-10-26T13:27:49.971811Z", "shell.execute_reply": "2025-10-26T13:27:49.971460Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "'It took the fuzzer 2.34 seconds to generate and execute 5000 inputs.'" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "runner = FunctionCoverageRunner(my_parser)\n", "dict_mutator = DictMutator([\"\", \"\", \"\", \"='a'\"])\n", "dict_fuzzer = GreyboxFuzzer([seed_input], dict_mutator, PowerSchedule())\n", "\n", "start = time.time()\n", "dict_fuzzer.runs(runner, trials=n)\n", "end = time.time()\n", "\n", "\"It took the fuzzer %0.2f seconds to generate and execute %d inputs.\" % (end - start, n)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Clearly, it takes longer. In our experience, this means more code is covered:" ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:49.973417Z", "iopub.status.busy": "2025-10-26T13:27:49.973311Z", "iopub.status.idle": "2025-10-26T13:27:49.975622Z", "shell.execute_reply": "2025-10-26T13:27:49.975230Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "'During this fuzzing campaign, we covered 121 statements.'" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "\"During this fuzzing campaign, we covered %d statements.\" % len(runner.coverage())" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "How do the fuzzers compare in terms of coverage over time?" ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:49.977128Z", "iopub.status.busy": "2025-10-26T13:27:49.977020Z", "iopub.status.idle": "2025-10-26T13:27:49.978608Z", "shell.execute_reply": "2025-10-26T13:27:49.978366Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from Coverage import population_coverage" ] }, { "cell_type": "code", "execution_count": 19, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:49.979980Z", "iopub.status.busy": "2025-10-26T13:27:49.979886Z", "iopub.status.idle": "2025-10-26T13:27:49.981565Z", "shell.execute_reply": "2025-10-26T13:27:49.981275Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import matplotlib.pyplot as plt # type: ignore" ] }, { "cell_type": "code", "execution_count": 20, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:49.983108Z", "iopub.status.busy": "2025-10-26T13:27:49.983015Z", "iopub.status.idle": "2025-10-26T13:27:52.097241Z", "shell.execute_reply": "2025-10-26T13:27:52.096972Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAk0AAAHHCAYAAACiOWx7AAAAOnRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjEwLjYsIGh0dHBzOi8vbWF0cGxvdGxpYi5vcmcvq6yFwwAAAAlwSFlzAAAPYQAAD2EBqD+naQAAV2dJREFUeJzt3Qd8U2X3wPHTRdl77yl7CciUISjrRRBUEP6KovA6UJkKDhAXQ0FEQRR9QVT0VRFcL0uGyJapDFmyRAoyyywd9/85T5uQlLakK7lJf9/PJya5uU2eJLX3cJ7znBtkWZYlAAAASFFwyg8DAABAETQBAAB4gKAJAADAAwRNAAAAHiBoAgAA8ABBEwAAgAcImgAAADxA0AQAAOABgiYAAAAPEDQBgJ9p3bq1uQDwLoImwA/s379f/v3vf0vFihUle/bskjdvXmnevLm8/fbbcvnyZV8PD5lg586d8tJLL8nBgwd9PRQACYI49xxgbz/++KPcc889Eh4eLg888IDUqlVLrl69KqtWrZK5c+fKgw8+KB988IGvh4kM9vXXX5vvffny5ddllfT7V9myZfPR6ICsKdTXAwCQvAMHDkivXr2kXLlysmzZMilRooTzsSeeeEL27dtngio7unTpkuTMmdPXw7C1ixcvSq5cuVL9cwRLgG8wPQfY2IQJE+TChQvy0UcfuQVMDpUrV5ann37aeT8mJkZeeeUVqVSpkslMlS9fXp577jmJiopy7vOvf/3LTPMlpWnTptKwYUO3bZ9++qk0aNBAcuTIIQULFjRB3JEjR9z20UyIZsA2bdokLVu2NMGSvq769ttvpXPnzlKyZEkzJh2bjjE2Nva61586daoZm77WLbfcIr/88kuS9Tv6fkaPHm3evz5nmTJl5JlnnnF7nyn56quvnO+pcOHC8n//939y9OhR5+NvvvmmBAUFyaFDh6772ZEjR5qg5cyZM85t69evlw4dOki+fPnMe2/VqpWsXr3a7ed0qk2fU6fdevfuLQUKFJAWLVokOb5Zs2aZLJNq06aN+Tm9rFixwvl5u34mul0f//LLL2XMmDFSqlQpyZMnj9x9991y7tw587kMGjRIihYtKrlz55aHHnooyc/Kk+8ayNJ0eg6APZUqVcqqWLGix/v37dtXp9utu+++25o6dar1wAMPmPvdunVz7jN79myzbcOGDW4/e/DgQbP9jTfecG579dVXraCgIKtnz57WtGnTrDFjxliFCxe2ypcvb505c8a5X6tWrazixYtbRYoUsZ588knr/ffft+bPn28e09e+9957zfO+99571j333GNeZ9iwYW6vr8+v22+99VZrypQp1pAhQ6yCBQtalSpVMs/vEBsba91xxx1Wzpw5rUGDBpnXGjhwoBUaGmp17dr1hp/RzJkzzes0atTIeuutt6wRI0ZYOXLkcHtPhw4dMu97woQJ1/28fh+dO3d23l+6dKmVLVs2q2nTptbEiRPNc9apU8dsW79+vXO/0aNHm9etUaOGGae+X/2OkrJ//37rqaeeMvs/99xz1ieffGIuERERzs/b9TNZvny52bdevXpmHPr56c/re+jVq5fVu3dvq2PHjub17r//frOvfpeuPP2ugayMoAmwqXPnzpmDmyeBgNq6davZ/5FHHnHbrsGJbl+2bJnzecPDw62hQ4e67acBgh40NWBwBFEhISHWa6+95rbf77//bgIU1+16ANfXmD59+nXjunTp0nXb/v3vf5ug58qVK+Z+VFSUVahQIRPIREdHO/ebNWuWeV7XAEGDh+DgYOuXX35xe059bd139erVyX5GV69etYoWLWrVqlXLunz5snP7Dz/8YH521KhRzm0afDRo0MDt5zXQ1P008FRxcXFWlSpVrPbt25vbru+5QoUK1u23335d0HTfffdZnvjqq6/M/hoQJZZc0KTvS9+jg76WfqcaMLnS91auXDnn/dR810BWxvQcYFORkZHmWqdZPPG///3PXA8ZMsRt+9ChQ821o/ZJV9517NjRTOW4rgP573//K02aNJGyZcua+998843ExcXJvffeKydPnnReihcvLlWqVDEFyq50mkynfRLTqR6H8+fPm+e49dZbTc3TH3/8YbZv3LhRTp06Jf3795fQ0Gulln369DHTWImn1qpXry7VqlVzG9dtt91mHk88Llf6OidOnJDHH3/crEJ00OlDfT7X+rCePXua6UZduej6Gen77Nq1q7m/detW2bt3r5lu0/E7xqK1Sm3btpWVK1eaz9DVo48+KplFFwqEhYU57zdu3Nh8x/369XPbT7frtJtO56bluwayKgrBAZvS4MYRaHhC62+Cg4NNnY8rPfDlz5/frT5HA4L58+fL2rVrpVmzZiYw0ABh8uTJzn00GNADrh40k+J6cFZaR5NUgfKOHTvkhRdeMIXsjkDQQettHGNXiceuAZTWZbnSce3atUuKFCmS5Lg0KEqO43WqVq163WMaNOmKRAetKdIAVAMlrc/Sz0IDNg04Hd+NjkX17ds32dfU9+ga+FWoUEEyiyPgddAaK6U1X4m3a5CkYytUqFCqv2sgqyJoAmxKD8xaPL19+/ZU/ZwWBN9Ily5dTMGyZps0aNJrDbgcxcdKD6r6XAsWLJCQkJDrnkMLipPLKDmcPXvWFEXre3n55ZdNEbhmeDZv3izPPvvsdVkYT+jP1K5dWyZNmpTk44kDhLTSz14zYvrZaNC0bt06OXz4sIwfP95tLOqNN96QevXqJfk8nnxOGSWp7yml7Y5MY2q/ayCrImgCbExXumkPJs0I6cq2lGhbAj34adZAp68cjh8/boIXfdxBl7nrc2vmRIMPzaZogKCBgoMGOHpQ1czITTfdlKbx66ounbbS6R9dVefaSiHx2JW2UNDVYg46faTNHevUqeM2rm3btpnpL08CxKReZ/fu3c7pPAfd5voZOTJyOpWnj+lnpIGmBpyuY1EaFLZr104yUmrfW3pkxHcNZAXUNAE2psvoNcB55JFHTPCTmE6raVdw1alTJ3PtOsWmHBkZrdtJHBD8/fff8uGHH5ogRO+76t69u8k66BL2xD1w9b4GQzfiyFq4/rw2Zpw2bZrbftrmQKeJZsyY4ayzUZ999pnb0n6ldTfaHkD3TUy7o2s9UXL0dXTZ/fTp092W3GuGRaf8En9GPXr0MO/h888/NwGmBpqufZV0eb4GHNqiQFtDJPbPP/9IWjleRwPezJYR3zWQFZBpAmxMD8hz5swxAY1mj1w7gq9Zs8YcyLUjuKpbt66prdHMlGNabMOGDfLxxx9Lt27d3DI4jiBLi8yHDRtmDpgaICR+7VdffdX0JdJsjz6H7q9Zonnz5smAAQPMz6ZEp/60nkfH9dRTT5nsySeffHLdgVlrobSP0ZNPPmkyQBoY6WtqvyIdh2vW5f777zdTZlpQrQXKejoZ7fmkReW6fdGiRdf1mnKtzdHpNS1Y18/nvvvuM8GoBp5aOzV48GC3/TXA0s9NA0+tLUscWOqUpgadWudUs2ZN87xa26VBnY5NM1Dff/+9pIVO9+n3ouPV2iMtQNfPRseU0TLiuwayBF8v3wNwY3v27LH69+9veuZo/588efJYzZs3t9555x3nsn2ly/W1v44udw8LC7PKlCljjRw50m0fV3369DFL1du1a5fsa8+dO9dq0aKFlStXLnOpVq2a9cQTT1i7d+927qPL32vWrJnkz2sLgCZNmpheSCVLlrSeeeYZa9GiRUkup9f+QroUXlsi3HLLLeZnddl/hw4d3PbTZfXjx483r6n7FihQwOyn711bKtzIf//7X6t+/frmZ7UXlH4Of/31V5L7zpgxw4xVP3PXNgWutmzZYnXv3t20TdDn1Pegvam0h1PilgP//PPPDcfn+traF0rbAbh+Xsm1HNA2BUn1pPr111/dtic3Fk++ayAr49xzAGxLa7R0lZxOHyU1HQcA3kRNEwBbuHLlynXTdrNnz5bTp09fdxoVAPAFMk0AbEFX2mlNkbY90KJwbUug59zTWi7tIcVJagH4GoXgAGxBC7G1x9KUKVNMdklPGKuF7+PGjSNgAmALZJoAAAA8QE0TAACABwiaAAAAPEBNU8KyZu2MrM3cvHnqAgAAkHZaYaSNZ/UUUNpsNrMRNImYgCmjTvIJAAC868iRI1K6dOlMfx2CJhGTYXJ86HraAwAAYH+RkZEm6eE4jmc2giaXs4lrwETQBACAfwnyUmkNheAAAAAeIGgCAADwAEETAACABwiaAAAAPEDQBAAA4AGCJgAAAA8QNAEAAHiAoAkAAMADBE0AAAAeIGgCAADwAEETAACABwiaAAAAPMAJewHAx2Ji4yQi8oqvhwH4nfORl7z6egRNAOBDlmVJt2mrZfvRSF8PBfA7cVEETQCQZVyIinEGTOGhVEwAqREb693/ZwiakCUs3hEhr/y4U67GxPl6KICb2IRfyVzZQmTHyx18PRzAr0RGRkq+N733egRNyBK+3vSXHDl92dfDAJJVt0x+Xw8BwA0QNMHv60HeXrpX9hw/n+J+mw6dMdcvdK4uTSsV8tLoAM8ESZBULprb18MAcAMETfBrB05elMk/7fV4/xZVCku14nkzdUwAgMBE0AS/dulqrLnOmz1UhrevmuK+pQvmJGACAKQZQRP82tWEKtr8ObPJ/U3L+3o4AIAAxvpW+LXohNVwoSFBvh4KACDAETTBr8XEWeY6Wwi/ygCAzMWRBgExPRdG0AQAyGQcaeDXmJ4DAHgLQRMCYnqOTBMAILOxeg7p9u6yvbJ89z8+ee3TF6+aa2qaAACZjaAJ6RIdGycTl+wRKz7h4zOl8ufw7QAAAAGPoAnpEhUT5wyY3rmvvk+mycJCgjg1CgAg0xE0IV2iouM7cqvOtUtIcDAF2QCAwEQhCDJoyX8QARMAIKARNCFdoqLjgyYKsQEAgY7pORuyLEtOXrgqlvi4utoDEZFXzHV4WIivhwIAQKYiaLKhoV9tk282HxV/QqYJABDoCJps6NeDp523g/ygTEiH2Kl2CV8PAwCATEXQZEOxsfHTct8NbC51Suf39XAAAICvC8FXrlwpXbp0kZIlS0pQUJDMnz/f7fELFy7IwIEDpXTp0pIjRw6pUaOGTJ8+3W2fK1euyBNPPCGFChWS3LlzS48ePeT48ePiz2ITGh+FsBoNAADb8GnQdPHiRalbt65MnTo1yceHDBkiCxculE8//VR27dolgwYNMkHUd99959xn8ODB8v3338tXX30lP//8s/z999/SvXt38WexCedTCw2mTggAALvw6fRcx44dzSU5a9askb59+0rr1q3N/QEDBsj7778vGzZskDvvvFPOnTsnH330kcyZM0duu+02s8/MmTOlevXqsm7dOmnSpIn480loyTQBAGAftk5lNGvWzGSVjh49apbhL1++XPbs2SN33HGHeXzTpk0SHR0t7dq1c/5MtWrVpGzZsrJ27Vrx95qmUIImAABsw9aF4O+8847JLmlNU2hoqAQHB8uMGTOkZcuW5vGIiAjJli2b5M/vXixdrFgx81hyoqKizMUhMjJS7IRMEwAA9hNs96BJp9k026RZpYkTJ5qi759++ildzzt27FjJly+f81KmTBmxEwrBAQCwH9tmmi5fvizPPfeczJs3Tzp37my21alTR7Zu3SpvvvmmmZIrXry4XL16Vc6ePeuWbdLVc/pYckaOHGmKzF0zTXYKnK4VghM0AQBgF7bNNGmtkl50Ss5VSEiIxMXFn++sQYMGEhYWJkuXLnU+vnv3bjl8+LA0bdo02ecODw+XvHnzul3sQmu3HEETmSYAAOzDp5km7cO0b98+5/0DBw6YTFLBggVNMXerVq1k+PDhpkdTuXLlTEuB2bNny6RJk8z+OrX28MMPm6yR/owGP08++aQJmPx15ZwjYFK0HACyqCuRIh/dLnL6gK9HAtjblfgkSpYImjZu3Cht2rRx3ndMmWmbgVmzZskXX3xhptL69Okjp0+fNoHTa6+9Jo8++qjzZ9566y2TjdKmllrc3b59e5k2bZr4K0cRuCJmArKoiN9E/vnD16MA7C/Ouye2D7J0PiiL05omzVpp3ydfTtVFXomWIf/dKj/tOmHu73q5g+TIFuKz8QDwkf3LRD65S6RwVZH/m+vr0QC2FRl5XvKVq+m147dtC8GzoqW7jjsDpoK5skm2UFJNQJYUGx1/nS2nSH77LFIBbCfYuy2DCJpsICY2TuZsOCyLd8SfMy9bSLDMe7wZheBAVg+aQrL5eiQAXBA02cDq/adk1Lc7nPcHtKwo5Qrl8umYAPhQ7NX4a4ImwFYImmzg7KX4P5Al8mWX7jeXkr7Nyvt6SADskGkK5k80YCf8H2kDMQnnmqtSLI8Mb1/N18MB4GtxTM8BdkTQZKPeTGHUMAH+TRcjXzmnN9L3POY5NGgKy5BhAcgYBE02EJ3Q4Tw0hKAJ8GvfDBD5/cuMez6CJsBWWNNuo+k5OoADfu7P5Rn3XMFhIpXbZdzzAUg3Mk026gJOpgnwc1cvxl8/uVkkf7n0PVdQkEgwzW0BOyFoskmfJkVfJsCP6TR79KX42+F5RUL48woEGv6vtlGmKYzpOdjN2cMia94RuZoQDCB5cTHXbmsnbwABh6DJRjVNIUzPwW42fBB/gefC84mE5vD1KABkAoKmVLp8NVYW74ww1xnlt7/OmmtaDsB2os7HX1dsLVKhla9H4x/KtxAhawwEJIKmVJrxy58yacmeTHnu7Nko+oRNp5wqtBS5dYivRwMAPkXQ5CHLsuTAyYvOrFDVYnmkTMGMq1vIFR4i9zUqm2HPB2SI2Jhry98BIIsjaPLQ6O92yOy1h9xOqtujQWmfjgnwWqaJc6ABAEGTpzYdOmOu84SHSqkCOeTWKoV9PSTAi+dAI9MEAARNKTgReUV6f7hejp+7Iheuxv+L+7P+jaVO6fy+Hhrg5ek5/lQAAH8Jb5Bd2nfigvN+wVzZpGKR3D4dE+BVTM8BgBN/CT1oOlmvTH55q2c9KZY3XHJm4yNDFsL0HAA4EQGkIM6ynCvbKhTO5evhAN5HpgkAnPhLmILYhExTsJ44E8hKjvwqsn+ZyOmD8fcJmgCAoCklBE3Isv77fyIXIq7dD8/jy9EAgC0QNKUgYXZOQji9CbKay6fjr+v0FClUJb4jOABkcQRNKYhNiJrINCHLiU0oAL/9FZE8xXw9GgCwBc4q6cH0XAifErKSOD0ZtSPNyqo5AHAgHPBg9RzTc8iSK+ZUMCeRBgAHgiYPMk1BTM8hK07NKU7UCwBOBE2eTM8RNCErNrRUTM8BgBNBUwqYnkPWrWlKQH8mAHAiaEpBbFz8NavnkCWn54JCdG7a16MBANsgaPIo0+TrkQA+mJ4jywQAbvirmII4OoLDTqIuiOxbIhITlbmvc/Gf+GvqmQDADUGTJ80tqWmCHawYK7L2Xe+9Xmh2770WAPgBnwZNK1eulDfeeEM2bdokx44dk3nz5km3bt3c9tm1a5c8++yz8vPPP0tMTIzUqFFD5s6dK2XLljWPX7lyRYYOHSpffPGFREVFSfv27WXatGlSrFixDMs0sXoOthB5NP668E0i+cpk/uvV6p75rwEAfsSnQdPFixelbt260q9fP+ne/fo/0Pv375cWLVrIww8/LGPGjJG8efPKjh07JHv2a/8CHjx4sPz444/y1VdfSb58+WTgwIHmuVavXp1hmSZWz8FWTScb/1uk0SO+Hg0AZDk+DZo6duxoLsl5/vnnpVOnTjJhwgTntkqVKjlvnzt3Tj766COZM2eO3HbbbWbbzJkzpXr16rJu3Tpp0qRJusYXFR2/fC48lEpw2EBsQtBEgTYA+IRto4G4uDiTQbrpppvMlFvRokWlcePGMn/+fOc+Oq0XHR0t7dq1c26rVq2ambpbu3Ztss+t03iRkZFul6Rcio7vV5MzGwcp2CjTRJduAPAJ2wZNJ06ckAsXLsi4ceOkQ4cOsnjxYrnrrrvM1JvWN6mIiAjJli2b5M+f3+1ntZ5JH0vO2LFjzVSe41KmTJmUM01htv2YkJXQCgAAfMrWmSbVtWtXU7dUr149GTFihPzrX/+S6dOnp+u5R44caab2HJcjR44kuV9MwhhCqWmCnTp1hxA0AYAv2Pavb+HChSU0NNSslnOl9UqrVq0yt4sXLy5Xr16Vs2fPumWbjh8/bh5LTnh4uLncSEzC6jmCJtiqUzfTcwDgE7bNNOm0W6NGjWT37t1u2/fs2SPlypUztxs0aCBhYWGydOlS5+O6/+HDh6Vp06bpHkNsbELQREtw2Kqmybb/1gGAgObTv75as7Rv3z7n/QMHDsjWrVulYMGCpph7+PDh0rNnT2nZsqW0adNGFi5cKN9//72sWLHC7K/1SNqOYMiQIeZntCXBk08+aQKm9K6cU0zPwZY1TXTqBoCsFzRt3LjRBEMOGvyovn37yqxZs0zht9YvaeH2U089JVWrVjWNLbV3k8Nbb70lwcHB0qNHD7fmlhnBMT1HnyZkupP7RC6eSHmfKwmrPINDvDIkAIC7IMtK6OCYhWnLAc1aaVG4Zqsc7v9ovfyy96S81bOu3FW/tE/HiAB2eJ3If9p7vv+DP4qUv/YPBwDIqiKTOX5nFoojUhDjqGkKpqYJmejU/vjrsJwieUulvG+B8iKlGnhlWAAAdwRNKaCmCV4t8K7QSqT3F74eDQAgGaRQUkBNE7y7Ko5aJQCwM4KmFMQmBE1htBxAZrLiM5q0EgAAeyMaSEF0Qk0TmSZkKjJNAOAXCJpSEEtNE7yBppUA4BcImlJATRO8gqAJAPwCQZMHNU2cRgVeOREv03MAYGtEAx71aSLTBG8ETWSaAMDOCJqScepClETFxNc0MT0Hr0zPBZFpAgA745+2Sfh8w2EZ+c3vzvuhIQRNyETUNAGAX+CvdBK2Hj7rzDDVLJlXKhbO7eshIZBZ1DQBgD8gaEpCXMI5jIfdUVUea13J18NBRlv4nMjO+WIbV87FX5NpAgBb4690EmITgiZKmQKQfrfrp1/L7thJkWq+HgEAIAUETUlIiJkkOIioKeDERF0LmB5aIBKWU2whPI9IIbKaAGBnBE0pTM8RMwWg6EvXbpdpTB0RAMBjtBxIQkJPS1oNBKI/l8dfh4QTMAEAUoWgKQlxCVET03MBJvqKyNf94m9nz+vr0QAA/AxBUwrTcySaAkzM5Wu3O07w5UgAAH6IoCnFmiaipoCs8FfVu/hyJAAAP0TQlITY+LOnUNMU0PhuAQCpQ9CUBIvpucDPNAXxqw8ASB2OHElgei5AWQkpRMV3CwBIJYKmJMTS3DJAuWaa+G4BAKlD0JTC9FwIn07gTs8BAJBKhAUpthwgGxFYHEET3ysAIPUImpIQl1D6Qk1TgGaa+F4BAGlA0JSEWFbPBSgyTQCAtCNoSqmmiYxEgGaa+LUHAKQeR48UTtjL9FyAthzgewUApAFBUxJinSfs9fVIkLGYngMApB1BU4otBzi4BhQKwQEA6UDQlML0HC0HAg2ZJgCAnwZNK1eulC5dukjJkiVN/dD8+fOT3ffRRx81+0yePNlt++nTp6VPnz6SN29eyZ8/vzz88MNy4cKFdI0rOuGMvWSaAgyZJgCAvwZNFy9elLp168rUqVNT3G/evHmybt06E1wlpgHTjh07ZMmSJfLDDz+YQGzAgAFpHtMn6w7JHxHnze1c4SFpfh7YEZkmAEDahYoPdezY0VxScvToUXnyySdl0aJF0rlzZ7fHdu3aJQsXLpRff/1VGjZsaLa988470qlTJ3nzzTeTDLJScvbSVXlx/nbn/aJ5sqfq52FztBwAAKSDrY8ecXFxcv/998vw4cOlZs2a1z2+du1aMyXnCJhUu3btJDg4WNavX5/q17sSHeu8PfPBRlKmYM50jB62w/QcAMBfM003Mn78eAkNDZWnnnoqyccjIiKkaNGibtt0/4IFC5rHkhMVFWUuDpGRkeY6Jjb+oJo9LFjaVHN/XgQCpucAAAGYadq0aZO8/fbbMmvWrAxvMjl27FjJly+f81KmTBmzPS7hoBoabNuPBRmSafL1QAAA/si20cEvv/wiJ06ckLJly5rskV4OHTokQ4cOlfLly5t9ihcvbvZxFRMTY1bU6WPJGTlypJw7d855OXLkSPzPJvQaYNVcoCLTBAAIwOk5rWXS+iRX7du3N9sfeughc79p06Zy9uxZk5Vq0KCB2bZs2TJTC9W4ceNknzs8PNxcEosjaAps1DQBAPw1aNJ+Svv27XPeP3DggGzdutXUJGmGqVChQm77h4WFmQxS1apVzf3q1atLhw4dpH///jJ9+nSJjo6WgQMHSq9evVK9cs61pomgKVCRaQIA+On03MaNG6V+/frmooYMGWJujxo1yuPn+Oyzz6RatWrStm1b02qgRYsW8sEHH6TrnHOhBE2BiZYDAAB/zTS1bt3aeZ43Txw8ePC6bZqVmjNnToaMJyaOTuABzYr/fpmeAwCkBf/kdhHHiXoDHNNzAIC0I2hyEZvQ25KgKUBRCA4AyOzpuQIFCnjcK0mX+/srapoCHZkmAEAmB02TJ0923j516pS8+uqrZvm/Lvl3nM5Ezw334osvij+LjIox1yE0twxMZJoAAJkdNPXt29d5u0ePHvLyyy+bpf0OepqTd999V3766ScZPHiw+KspS/eYaw6pgYpMEwAg7VKdUtGMkvZGSky3adDkz8JC4j+OOqXz+XooyAy0HAAApEOqjx7acPLbb7+9brtuS9yM0t9cuhpfCX5Pw/hz0SHAMD0HAPBmn6YxY8bII488IitWrHCeqmT9+vWycOFCmTFjhvizy1e1pilMcoWH+HooyBRMzwEAvBg0Pfjgg+b0JVOmTJFvvvnGbNP7q1atSvF8b/7gUnSsSFCY5Ayz7Sn5kCGZJl8PBADgj9IUHWhwpKcvCTRR0XEi2UTCw6h5CUxkmgAAaZem6GD//v3ywgsvSO/eveXEiRNm24IFC2THjh3izxLaNNHcMlBR0wQA8GbQ9PPPP0vt2rVNHdPcuXPlwoULZvu2bdtk9OjREghCOKgGKDJNAAAvBk0jRowwzS2XLFki2bJlc26/7bbbZN26dRIIggmaAvyEvUy/AgBSL9VHj99//13uuuuu67YXLVpUTp48KYGAhuABiuk5AEA6pDo8yJ8/vxw7duy67Vu2bJFSpUpJIKCmKVAxPQcA8GLQ1KtXL3n22WclIiLCnMQ3Li5OVq9eLcOGDZMHHnhAAgHTcwGKTBMAwJtB0+uvvy7VqlWTMmXKmCLwGjVqSMuWLaVZs2ZmRV0gINMUqMg0AQC81KfJsiyTYdLGlqNGjTL1TRo41a9fX6pUqSKBgtVzAWrlm/HXfL8AAG8ETZUrVzb9mDRI0mxTIOKYGqDOHo6/DqbjOwAgk6fngoODTbB06tQpCVQ6M6e1Wgjg6bnOk3w9EABAVqhpGjdunAwfPly2b98ugYh6pizQp4lMEwAgDVJ99NAVcpcuXZK6deua5pY5cuRwe/z06dPiz1g5F8BYPQcA8GbQNHnyZAlkZJoCGB3BAQDeDJr69u0rgYyVcwGMoAkAkA5pOnrs37/f9GS677775MSJE2bbggULzKo6fxdMpikLBE18xwAALwRNP//8s9SuXVvWr18v33zzjenTpLZt2yajR48Wf0fMFMDINAEA0iHVR48RI0bIq6++KkuWLDGF4A633XabrFu3TvwdNU0BjKAJAJAOqT56aBfwu+6667rtRYsWlZMnT4q/Y/VcVlg9R9AEAEi9VB898ufPL8eOHbtu+5YtW6RUqVLi78g0BTAyTQCAdEj10aNXr17y7LPPmnPQaefsuLg4Wb16tQwbNsz0cPJ3ZJoCGJkmAEA6pPro8frrr0u1atXMeee0CLxGjRrSsmVLadasmVlR5+/INAUwVs8BALzZp0mLv2fMmCEvvviiOZWKBk7169c356QLBMRMWSBoEr5kAIAXgqZVq1ZJixYtpGzZsuYSaOjTFMCoaQIApEOqjx7aWqBChQry3HPPyc6dOyXQ0BE8gBE0AQDSIdVHj7///luGDh1qmlzWqlVL6tWrJ2+88Yb89ddfqX7xlStXSpcuXaRkyZKmqHz+/PnOx6Kjo03BuTbSzJUrl9lHC8319ROfILhPnz6SN29es7Lv4YcfdjbcTAtqmgIYQRMAIB1SffQoXLiwDBw40KyY09Op3HPPPfLxxx9L+fLlTRYqNS5evCh169aVqVOnXvfYpUuXZPPmzaZ2Sq+1+/ju3bvlzjvvdNtPAyY9fYs22/zhhx9MIDZgwABJKw3eEKAImgAA6RBkWY512GkTGxtrzjunwc1vv/1m7qdpIEFBMm/ePOnWrVuy+/z6669yyy23yKFDh0w91a5du8zqPd3esGFDs8/ChQulU6dOJvOl2SlPREZGSr58+aTMoC8lR67csvvVjml6D7C5l/Jr5CQydI9InmK+Hg0AIJ0cx+9z586ZGafMluZ/cmum6fHHH5cSJUpI7969zVTdjz/+KJlJPxQNrnQaTq1du9bcdgRMql27dhIcHGzOjZecqKgo80G7Xhxa3VQkU98DfIk+TQCAtEv10WPkyJGmEFyn4g4fPixvv/22aXT5ySefSIcOHSSzXLlyxdQ43Xfffc5oUl9XT9/iKjQ0VAoWLGgeS87YsWNNZOq4aM8p58+HMD0XkFwTqgRNAABvtBzQmqHhw4fLvffea+qbvEGLwvX1dCbxvffeS/fzaeA3ZMgQ533NNDkCJzqCB3qPJppbAgC8FDTptJw3OQImrWNatmyZ25xl8eLF5cSJE277x8TEmBV1+lhywsPDzSUprJ4LUARNAABvB01KV81NnjzZFGIrLcZ++umnpVKlSpIZAdPevXtl+fLlUqhQIbfHmzZtKmfPnpVNmzZJgwYNzDYNrPR8eI0bN07Ta9KnKSsETUzPAQC8EDQtWrTILPvX/kzNmzd3Zp9q1qwp33//vdx+++0eP5f2U9q3b5/z/oEDB2Tr1q2mJkkLzO+++27TbkBbCeiqPEedkj6up3OpXr26qaPq37+/TJ8+3QRZ2g5BTyrs6cq5xMg0BSiCJgCAt1sO6Hnm2rdvL+PGjXPbPmLECFm8eLEJcjy1YsUKadOmzXXb+/btKy+99JIpOE+KZp1at25tbutUnAZKGrDpqrkePXrIlClTJHfu3B6Pw7XlQO8WVWVcjzoe/yy8JPJvkbOH0/7z0ZdFPkloZ/Hc3yLZcmXY0AAAWaPlQKozTTol9+WXX163vV+/fmbKLjU08EkpZvMkntOs05w5cySjcO45GzofITK5jkhcdMY8H5kmAIA3gqYiRYqYKbQqVaq4bddtiZf/+6NQgib7OXMoPmAKDhXJXy59z1W5rUhYjowaGQAgC0l10KT1Q3qakj///FOaNWvmrGkaP3682zJ+f0XLARtyZJgKVBB5cqOvRwMAyKJSHTTp6VLy5MkjEydONP2OlBZdaw3SU089Jf6OQnAbiouJvw4J8/VIAABZWKqDJj2NyeDBg83l/PnzZpsGUYGCoMmGYhOCpuAQX48EAJCFpTpo0rYA2kBSa5pcgyXtpRQWFibly5cXf0bQZONMUzCZJgCA76R6GdGDDz4oa9asuW67niBXH/N3NLe0cU0T03MAAH8KmrZs2eJsaumqSZMmZgWdv6PlgA3FJgRNunoOAAB/CZq0pslRy+RKG0tp125/R8hkQ3EJv1cETQAAfwqaWrZsKWPHjnULkPS2bmvRooX4O2bnbIjpOQCADaT6n+7aj0kDp6pVq8qtt95qtv3yyy+mlbmeLNffBZFrsp8LJ+KvyTQBAPwp01SjRg357bff5N5775UTJ06YqboHHnhA/vjjD6lVq1bmjBJZ16aPRX4aHX+boAkA4ENpOgppM8vXX39dAhHTczbz14Zrt6t19uVIAABZHGcuTYSYyaZF4O3GiNTr7evRAACyMIKmRMg02Qwr5wAANkHQlERLBdixGzhBEwDAtwia4CdBE+edAwD4WdB0+fJluXTpkvP+oUOHZPLkybJ48eKMHhsgYsXFX5NpAgD4W9DUtWtXmT17trl99uxZady4sUycONFsf++998TfMTtnM2SaAAD+GjRt3rzZ2dTy66+/lmLFiplskwZSU6ZMEX9Hc0uboaYJAOCvQZNOzeXJk8fc1im57t27S3BwsDlhrwZP/o5Mk80QNAEA/DVoqly5ssyfP1+OHDkiixYtkjvuuMNs1+7gefPmFX9HzGQzzpYDTM8BAPwsaBo1apQMGzZMypcvL7fccos0bdrUmXWqX7+++DsyTTZDnyYAgE2k+kh09913S4sWLeTYsWNSt25d5/a2bdvKXXfdldHjQ1bH9BwAwJ/7NBUvXtzUNS1ZssS0IFCNGjWSatWqib+jENwmLp4U+fIBkRM74+8HMT0HAPCzoOnUqVMmq3TTTTdJp06dTMZJPfzwwzJ06FDxd0zP2cSeRSI7vxW5eiH+fr5Svh4RACCLS3XQNHjwYAkLC5PDhw9Lzpw5ndt79uwpCxcuzOjxIauKvRp/XfJmkUeWiRSv7esRAQCyuFQXimjBt66aK126tNv2KlWqBEjLAVJNtuoErhmm0g18PRoAAFKfabp48aJbhsnh9OnTEh4eLv6OkMlmQVMQp0cEANhDqo9I2g3ccRoVR2YmLi5OJkyYIG3atMno8SGrsqz4a4ImAIC/Ts9pcKSF4Bs3bpSrV6/KM888Izt27DCZptWrV4u/Y3bOJsg0AQBsJtVHpFq1asmePXtMryY9Sa9O1+mpVLZs2SKVKlUSf0fMZBMETQAAm0lTx8B8+fLJ888/L4GIQnCbIGgCAARC0HT27FnZsGGDOd+c1jO5euCBB8SfETPZBEETAMBmUn1E+v7776Vs2bLSoUMHGThwoDz99NPOy6BBg1L1XCtXrpQuXbpIyZIlTYZHTwTsyrIsc667EiVKSI4cOaRdu3ayd+9et320lqpPnz7mZMH58+c3TTYvXEhoiJgGxEw2QdAEALCZVB+RtOt3v379TGCiGaczZ844LxrApIbWQ+n566ZOnZps0fmUKVNk+vTpsn79esmVK5e0b99erly54txHAyYtRNdTuvzwww8mEBswYEBq3xZsGzQRxgIA/HR67ujRo/LUU08l2asptTp27GguSdEs0+TJk+WFF14wBedKWx0UK1bMZKR69eolu3btMl3If/31V2nYsKHZ55133jGnd3nzzTdNBivVOEjbA5kmAIDNpPqIpJkebTeQ2Q4cOCARERFmSs61AL1x48aydu1ac1+vdUrOETAp3T84ONhkptKCkMkmCJoAAP6eaercubMMHz5cdu7cKbVr1zbnoXN15513ZsjANGBSmllypfcdj+l10aJF3R4PDQ2VggULOvdJSlRUlLk4REZGOm+TaLIJgiYAgL8HTf379zfXL7/88nWPaTF3bGys2N3YsWNlzJgxST4WRK7JHgiaAAA2k+ojkrYYSO6SkQFT8eLFzfXx48fdtut9x2N6rW0PXMXExJiCdMc+SRk5cqScO3fOeTly5IjzMTJNNkHQBACwGdsekSpUqGACn6VLl7pNo2mtUtOmTc19vdYVfJs2bXLus2zZMhPAae1TcvTEwtqiwPUCuwZNIb4eCQAAnk/P6bJ/XcafPXt2czslurLOU9q2YN++fW7F31u3bjU1SdoLSvs+vfrqq1KlShUTRL344otmRVy3bt3M/tWrVzf9onTKUNsSREdHm95RurIuTSvnKAS3DzJNAAB/DJreeust0w9Jgya9nRytaUpN0KSr8Nq0aeO8P2TIEHPdt29fmTVrljkZsPZy0oBNM0p6vjttMaDjcPjss89MoKQnEdZVcz169LhhYJcSpudsgj5NAAB/DJo0A5TU7fRq3bq16ceUUhCmBedJFZ07aFZqzpw5GTYmCsFtgkwTAMBmOCIlRsxkD45gmqAJAOBPmSbHtJknJk2aJP6MmMkmyDQBAPwxaNqyZYtHT6bTaUCGIGgCAPhj0LR8+XLJKgj8XJzcJ3L2oG9e++zh+GuCJgCAv3YED3SETAnOHBJ5V8/pl3yhvlcE8ysKALAHjkiJkGhKcPZQfMAUEi5SpKpvxpA9n0jN+J5cAAD4GkFTIgRNCWKuxl8XrSby75W+Hg0AAD5HwUgi9GlKEHMl/lozTQAAgKAJyYiNir8OJWgCAEARNCXC9FyCGIImAABcETQh6Xqmn8bE3w69dp4/AACyMoKmROjTJCJ/rhC5EBF/O1dhX48GAABbIGhKhJBJRK6ev3a79UhfjgQAANsgaEqERJOIxMXGX1dsLZKnuK9HAwCALRA0IfmgiW7cAAA4ETQlQp8mDZpi4q8JmgAAcCJoSoTpOZegKSjE1yMBAMA2CJoSIWZyzTQRNAEA4EDQlAiZJmqaAABICkHTdYiaxCJoAgAgMYImXI/pOQAArkPQlAjTcwRNAAAkhaApkZzZCBSoaQIA4HocFRNpUrGQ+KW4OJG/t4hEX0r/c50+EH9NywEAAJwImlzUKplXwkL8NPm2bqrI4hcy9jlDwjL2+QAA8GMETS5Cgv20oCk2RuTYtvjbuYqK5CyY/ufMlkuk9r3pfx4AAAIEQZO/B02H14t82l3k6oX4+7ePEanX29ejAgAg4PjpXFTmCPbHpXP7l10LmMLziZRt4usRAQAQkMg0uQgNsVnQtH2uyJp3rzWbTMq5o/HXzQeJ3PYCdUgAAGQSgiYXQXbLNK1++1qt0o2UupmACQCATETQ5MLnC+d2zBM5uPra/VN/xl93elOkQIXkfy5HgfigCQAAZBqCJhchvsw0xUSJzO0vEhftvj0oWKRGN5HcRXw1MgAAQNBko9VzsdHXAqYWg0WCE6baStQlYAIAwAYImuwSNFlx1263GiESlt13YwEAANfxdRVPimJjY+XFF1+UChUqSI4cOaRSpUryyiuviGVZzn309qhRo6REiRJmn3bt2snevXv9sOXAtffEWYMBALAfWwdN48ePl/fee0/effdd2bVrl7k/YcIEeeedd5z76P0pU6bI9OnTZf369ZIrVy5p3769XLlyxb9qmlwzTVrHBAAAbMXW03Nr1qyRrl27SufOnc398uXLy+effy4bNmxwZpkmT54sL7zwgtlPzZ49W4oVKybz58+XXr16+dH0nEumScg0AQBgN7ZOaTRr1kyWLl0qe/bsMfe3bdsmq1atko4dO5r7Bw4ckIiICDMl55AvXz5p3LixrF27NtnnjYqKksjISLeLCrZL0MT0HAAAtmPrTNOIESNMQFOtWjUJCQkxNU6vvfaa9OnTxzyuAZPSzJIrve94LCljx46VMWPGXLf9nwtR4juuQZOtY1kAALIkWx+dv/zyS/nss89kzpw5snnzZvn444/lzTffNNfpMXLkSDl37pzzcuTIEbP9tmpFxWfINAEAYGu2zjQNHz7cZJsctUm1a9eWQ4cOmUxR3759pXjx4mb78ePHzeo5B71fr169ZJ83PDzcXBLzaajiLAQnYAIAwI5snWm6dOmSBAe7D1Gn6eLi4gMMbUWggZPWPTnodJ6uomvatKn4l4RME1kmAABsydaZpi5dupgaprJly0rNmjVly5YtMmnSJOnXr5/zBLuDBg2SV199VapUqWKCKO3rVLJkSenWrVvqXzDIBpkm6pkAALAlWwdN2o9Jg6DHH39cTpw4YYKhf//736aZpcMzzzwjFy9elAEDBsjZs2elRYsWsnDhQsme3c86ajtrmsg0AQBgR0GWa3vtLEqn9LRVwYyl2+WR22r6ZhBnj4hMriUSEi7y4gnfjAEAAD88fp87d07y5s2b6a/HXJAL3+Z4qGkCAMDOCJrsgtVzAADYGkGTbVoOODJNfCUAANgRR2jbYHoOAAA7I2hy4dN4hUwTAAC2xhHaLmg5AACArRE0uQjyZcDibG5J0AQAgB0RNNmnEjxhDARNAADYEUGTXXAaFQAAbI0jtN1aDlDTBACALRE02QU1TQAA2BpBk4sg3/YcSBgEXwkAAHbEEdoF03MAACA5BE12QSE4AAC2xhHahW/LiWg5AACAnRE02QWZJgAAbI0jtAs71IFT0wQAgD0RNLngNCoAACA5BE22QU0TAAB2RtBkm+m5hEwT03MAANgSQZNdOPo0UQgOAIAthfp6AFna8Z0in3YXuXSKmiYAAGyOoMmXDq0WOX/MfVvpRr4aDQAASAFBky/PPefILt3UQaTzpPipuTzFvTsGAADgEYImF16fGHMETdlyieQr5e1XBwAAqUDVsS/RBRwAAL/B0dqF12uwHSvmaDMAAIDtETT5EpkmAAD8BkdrX55GhaAJAAC/wdHap9NzBE0AAPgLjtY+5egC7utxAACAGyFoskPLATJNAADYHkdrX+J8cwAA+A3bH62PHj0q//d//yeFChWSHDlySO3atWXjxo3Oxy3LklGjRkmJEiXM4+3atZO9e/em7cWoaQIAAMmw9dH6zJkz0rx5cwkLC5MFCxbIzp07ZeLEiVKgQAHnPhMmTJApU6bI9OnTZf369ZIrVy5p3769XLlyJQ2v6O3Vc/RpAgDAX9j6NCrjx4+XMmXKyMyZM53bKlSo4JZlmjx5srzwwgvStWtXs2327NlSrFgxmT9/vvTq1UtsjUwTAAB+w9ZH6++++04aNmwo99xzjxQtWlTq168vM2bMcD5+4MABiYiIMFNyDvny5ZPGjRvL2rVrU/16tBwAAADJsfXR+s8//5T33ntPqlSpIosWLZLHHntMnnrqKfn444/N4xowKc0sudL7jseSEhUVJZGRkW4XnyBoAgDAb9h6ei4uLs5kml5//XVzXzNN27dvN/VLffv2TfPzjh07VsaMGXPddu9XFjlWz1HTBACA3dk6xaEr4mrUqOG2rXr16nL48GFzu3jx4ub6+PHjbvvofcdjSRk5cqScO3fOeTly5Ij4BJkmAAD8hq2P1rpybvfu3W7b9uzZI+XKlXMWhWtwtHTpUufjOtWmq+iaNm2a7POGh4dL3rx53S4qyNsZH2fQRKYJAAC7s/X03ODBg6VZs2Zmeu7ee++VDRs2yAcffGAujiBn0KBB8uqrr5q6Jw2iXnzxRSlZsqR069bNDzqC09wSAAB/YeugqVGjRjJv3jwznfbyyy+boEhbDPTp08e5zzPPPCMXL16UAQMGyNmzZ6VFixaycOFCyZ49u9ieI9NEnyYAAGzP1kGT+te//mUuydFskwZUekkv77ccINMEIHMX01y9etXXwwDSTJtbh4SEiF3YPmgKaBSCA8gkGixpLzsNnAB/lj9/flO/7PW64yQQNLmguSWAQKBnSzh27Jj5F7qeVSE4mL8x8M/f40uXLsmJEyecK+p9jaDJRZDXzz3H6jkAGS8mJsYcbHRRTM6cOX09HCDNcuTIYa41cNIzg/h6qo5/fvgUNU0AMl5sbKy5zpYtm6+HAqSbI/CPjo4WX+No7YrpOQABxA41IEAg/R5ztM4MWngZdeHGl5iEVS02+oUAAH+yYsUKc1DVljMpKV++vGlZk1l0DPPnz/f5cyBzETS5yJDQJfqKyNRbRMaWuvFl25yMfGUA8Ft6TtE8efKYeiyHCxcumCXnrVu3TjJQ2r9/v2mArEXv+fLlM4/NmjXLrLbKCA8++KB5Hb3oOPRk8Lfffrv85z//uW5Voo6hY8eOHj3vSy+9JPXq1btue2qeA75B0JTRKcDT+0VO7fV8/7BcImWTP+ULAGQFbdq0MUHSxo0bndt++eUXs9RcT4115coV5/bly5dL2bJlpVKlSqZuKzOXo3fo0MEEMwcPHpQFCxaYcT799NOmf6BrgKdj0FN0pUdGPEdGrFhzfV9wR9CUHkc2iMxoKzKt2bXLF73jHytSTeT5iBtfRhwSKd/c1+8EAHyqatWqZkm5ZpEc9HbXrl3N2SDWrVvntl2Dl8TTc3r7oYceMidid2SINKvjoCsK+/XrZzJaGnQ5TsmVEg1iNJgpVaqU3HzzzfLcc8/Jt99+awIozWolN7X2119/yX333ScFCxaUXLlyScOGDU3wpz8zZswY2bZtm3OMjudJ/By///673HbbbWYFWaFChcyZLzSwdM2E6SnD3nzzTfPZ6T5PPPGEW8H0J598Yl5b37O+j969ezuX8Lt+fvp+GjRoYN7vp59+atpUuAawavLkyebcr1m59xdBk4tU/ztl82yRoxtFTuy4djlzMP6x4rVFwnLc+BISlgnvBAAS9bu5GuOTi762pzQQ0iySg97WqblWrVo5t1++fNkEH46gyZVO1emBXU/CrtkhvQwbNsz5+MSJE00AsWXLFnn88cflscceu+6k8J7QQKZu3bryzTffJPm4BjY65qNHj8p3331nAiQ95ZcGGz179pShQ4dKzZo1nWPUbYnp6cHat28vBQoUkF9//VW++uor+emnn2TgwIFu++nnotOUev3xxx+bAMw1mNMA6pVXXjFj0IBMM2YabCU2YsQIGTdunOzatUvuvPNOadeuncycOdNtn5kzZ5qfzcp9v+jTlFZxsSJbPom/3exJkcrtrj0WHCpSqqHPhgYAri5Hx0qNUYt88to7X24vObN5dqjRQEhPwq7TQxocaXCjwYce+LXmSa1du1aioqKSDJp0qk5rmzRzolmVxDp16mSCJfXss8/KW2+9ZYINzXKlVrVq1eS3335L8rE5c+bIP//8Y4IdzTSpypUrOx/PnTu3hIaGJjlG1+fQKcnZs2ebTJV69913pUuXLjJ+/HhTX6U0qNLt2r9Ix9S5c2dZunSp9O/f3zyumTWHihUrypQpU8x5XTWw03E46KnItF7L4ZFHHpFHH31UJk2aZLJPmzdvNpkvzbJlZVk3XExCqqbED19LFUvl20Uqtr52Kd9CJMwPThgMADaiWSXNsGiwofVMN910kxQpUsQETo66Jp1O0oO/Tq+lVp06dZy3HYGV61RVamgGLbk6qq1bt0r9+vWdAVNaaMZHs1mOgEk1b97cZKtcs2OasXJt+KjTdK7vadOmTSbQ0s9Lp+j0s1SHDx92ez3NwLnSaT993nnz5pn7mr1q06aNWYWYlZFpSquoyGu3y9/qy5EAQIpyhIWYjI+vXttTmo0pXbq0yf6cOXPGeYDXzuZ6Opg1a9aYx3R6LC10BZwrDXrSWp+jQY3WWqXUxdobUnpPjik+vXz22WcmANVgSe8nPpGza3DmyNo98MADZkque/fuJvP19ttvS1ZH0JTW06jEJawuKNNYJAvP7wKwPz2QejpF5muazdBskgZNw4cPd25v2bKlKVbesGGDqUVKjh7sHR3RM8uyZcvMVNXgwYOTzWh9+OGHcvr06SSzTZ6MsXr16ia7o4GPI6BZvXq1qSfydDrxjz/+kFOnTplaJQ06VeLi7pToFF2tWrVk2rRpZsq0e/fuktVxtE9rIXhswuqEYAq5ASAjg6ZVq1aZKS5Hpknp7ffff99kSJKqZ3LQ6SOt19G6npMnT5oVc+mh9VMRERGmqFvrel5//XWzok9bDmgmJim6ak6n/nSKSwOdP//8U+bOnWvqsRxjPHDggHmPOkZ9jcT69Okj2bNnl759+8r27dtNhu3JJ5+U+++/31nPdCM6JacB2jvvvGPGoEXpWhTuKQ3cmjRpYuq/9D3l8GIGza4ImtJTCK6CfXvyQAAIJBoQaRG4TtW5BgcaNJ0/f97ZmiA5uoJOC5h1RZpOR02YMCFd41m4cKF5PQ10tGeTBi9aTK0F0cmdPFYDlcWLF5sTzGrxee3atU22x7F/jx49zHPpe9Uxfv7550meb23RokUmW6WF23fffbe0bdvWFH17Sp9bs1W68q5GjRpmDNqeIDUefvhhE6i6FpRnZUFWataDBqjIyEiz4mLx5j/l9vpJz1FfZ+sckfmPxa+a+7+5mT1EAPCYFkxrJkNrbjRbAaSVZqY06EpupaCvf58dx2/tzaWtJjIbmaa0ck7P+UedAAAAntIpTp0W1MyWTgsiHkFTWouaHIXgBE0AgACjTTS1Q7i2gWBq7hqO+OldPUfQBAAIMIk7iyMemaa0cgRNnAYFAIAsgaAprR3Bz/0Vf02mCQCALIGgKa3+3hp/HX3Z1yMBAABeQNCU1uaWOQrEXxf0sEUBAADwawRN6a1pKnTtzNUAACBwETS5ouUAAABIBkFTWgvBHUFTEKdRAQBf0ZP76gmJz549m+J+ehqUyZMnS6C+v8x+DsQjaEorKy7+mnPPAUC6TZ8+XfLkySMxMTFuXanDwsJMg8WkgoD9+/ebc80dO3bMnEpDaW+h/Pnzi694Gpzpfvoe9KInwtX79957ryxbtsxtv8Tv70b0sxo0aFC6ngPJI2hKayE403MAkGH05LUaJG3cuNG57ZdffpHixYvL+vXrzfnHHPSkuWXLlpVKlSqZk+PqPhp8+JuXX37ZBDO7d++W2bNnm2CvXbt28tprrzn3yYj3Z5fP6OrVq+LvCJrSiqAJADJM1apVpUSJEiaL5KC3u3btak7Uum7dOrftGmQlnnrS2w899JA5easji/PSSy85f+7SpUvmlCCa0dKg64MPPnAbw++//y633XabyfwUKlRIBgwYYAK5lLI43bp1kwcffND5+KFDh2Tw4MHO10+JjkODGR1Ly5YtzXhefPFFGTVqlAmkEr8/h9WrV5vXypkzpxQoUEDat28vZ86cMeP4+eef5e2333a+/sGDB5N8jrlz50rNmjUlPDzcZLkmTpzoNjbd9vrrr6f4eT377LNy0003mXFUrFjRjD06OuG8rCLms69Xr558+OGHzpPtanCon21UVNR1n+P9998vdkfQlN6aJoImAHZnWSJXL/rmoq/tIQ2ENIvkoLc1OGjVqpVz++XLl03myRE0JZ6G0qkxPdu9ZnD0MmzYMOfjGhg0bNhQtmzZIo8//rg89thjzuDk4sWLJvjQIOTXX3+Vr776Sn766SdzDjZPffPNN1K6dGlnBkkvqfX000+LZVny7bffJvn41q1bpW3btlKjRg1Zu3atrFq1Srp06SKxsbEmWGratKn079/f+fplypS57jk2bdpkpgJ79eplAkUNbjTgSXzalJQ+L6XBlP7Mzp07zWvPmDFD3nrrLXG1b98+E6DpZ6Njv+eee8xYv/vuO+c+J06ckB9//NEvznHHEd9NWs49R9wJwOaiL4m8XtI3r/3c3yLZcnm0qwZCmsnRuiYNjvRgrQGTZi+05klpoKBZiqSCJp2G0rodzapoBiexTp06mYO/I0uiB3gNxjTLNWfOHDMFqJmQXLnix/vuu++agGT8+PFSrFixG46/YMGCEhIS4swgpYU+R9GiRU2GKCkTJkwwgcy0adOc2zRj5PoZaOYnpdefNGmSCbw0UFKaLdLA54033nBmzW70eakXXnhBXDNTGqB+8cUX8swzz7hNyelnWqRIEee23r17y8yZM00ApT799FOTyUpcu2ZHHPHTKi42/ppMEwBkCD1oasZHMz1az6QHcz3YauDkqGvSqSadCtKDbGrVqVPHedsRWGmWQ+3atUvq1q3rDJhU8+bNJS4uzi274g2aaUpuas+RaUoPfa/63lzp/b1795oskCefl/rvf/9rfk63586d2wRRhw8fFlflypVzC5iUZsIWL14sR48eNfc1W6XBmq9rrjzBET/N03METQD8RFjO+IyPr17bQ5UrVzbTW5rN0BodDZZUyZIlzTTTmjVrzGNad5SmoYS5n2BdD9IaFHkqODjYBDSuXGt4MsKpU6fkn3/+MTVASdF6K29J6fNau3at9OnTR8aMGWOmNTXDp1mmxLVRrkGoQ/369U2AqhmoO+64Q3bs2GGm5/yBX2Waxo0bZ74010I8/ZfHE088YQrLNNLt0aOHHD9+PE3Pn+3i3yJnD3t2iUk45xxBEwB/+BehTpH54pLK7IFOu2k2SS+u0zVaKL1gwQLZsGFDklNzrtNTrtkST1WvXl22bdtmMl2uBdcaKDmmozRj4lqnpK+zffv2DHl9B60N0tfUwuikaPZn6dKlyf68J6+v71Xfmyu9r5k9nV70xJo1a0wW6fnnnzfThVWqVDFF8J565JFHTIZJp+l0xWBStVd25DdHfE3Xvv/++27pQqWrFDRC1aI9jXS1aK979+7X/UJ4osa89iLhqUwP0twSADKMBkT6D2HN4DgyTUpv6993rZFJKWjS2hpd8aaBhWYztL5HLzeiWZPRo0dL3759TWG0ZnuefPJJs6LLUc+kGa4hQ4aYY462O9DaoMQNI/X1V65caYqsdWVa4cKFk33N8+fPS0REhHmvBw4cMLU9utJs7NixJuuWlJEjR0rt2rVNrdGjjz5qgiTNvml9kL6Wvr5OZWpNlCYStEYqsaFDh0qjRo3klVdekZ49e5qskdZvudZJ3UiVKlXMVJxml/S59DOZN2+exz+vdU1aA6XF45px8hd+kWnS/wH0F1o/XF3Z4KDLSj/66CPzi6u/zA0aNDBRq0bArstTPWWFhIuEZvf8UqyWSLEaGfxuASDr0oBIi8A1aHAtvtagSYMMR2uC5OgKOg0mNBjQzJAWTntCA6tFixbJ6dOnTRBw9913m9ohDSYcdHWXBlUPPPCAGY/WViUO4HTlnAYsGlQlruVJTFsL6HvR96rBmR7TNNjTouvkaDZI64E0K3bLLbeY1XK60i40ND4HooGIZot0dZ2+fuIaI3XzzTfLl19+aQKeWrVqmXHouF2LwG/kzjvvNEkLDWS1rYAedx2F5Z7QJIfODGlgl1xWzY6CrMQTtDakv6QaLWvlvqZr9QvSZaXaOVV/qXXu27UDrKYMdQpPv9Ck6MoL1x4RkZGRJjWov7C6VBUA/JmWLWjmwtEbB7Cjtm3bmpV/U6ZMSfPvsx6/NQDz1vHb9tNzGglv3rzZTM8lpmlNTU0mbpmv/zrRx5KjqU8tXgMAAN515swZZ91aaqYE7cDWQdORI0dMo68lS5Zk6L+WdE5Y56UTZ5oAAEDmql+/vgmctP+Vo8jeX9g6aNKupdoTQudfHXRVgBbZ6Tyzzj9rUaAW4rlmm3T1XEqNvbQ4Ty8AAMC7DibTuNMfhNp9vlNbvLvS8wpVq1bNFMppdkj7SGjhnBaUKW1CpoVvWhwHAACQJYImbUWvlf2JG2VpTybH9ocffthMtWmhuBaB6RJRDZiaNGnio1EDAIBAZOugyRO6ok4bgWmmSVfEaWdSfyssA4DM4AeLowG/+j32i5YDmc3bSxYBIDNps0Q9u7yefkT/tgH+7NSpU6a+OamO5bQcAACkizY61GaN2tVa6z41Gw/4G8uy5NKlSyZg0sVenp7iJTMRNAFAgNFzdGqnaW0ImJrzgQF2lD9//hRXxHsTQRMABCBt/KvnB9O2LIC/CgsLs0WGyYGgCQAClE7LcRoVIOMw0Q0AAOABgiYAAAAPEDQBAAB4gJoml8ZZ2u8BAAD4h8iE47a3Wk4SNCU0zlJ6LjsAAOB/x/F8XmjkStAkYs5bp/REv3TP9f2/GjR4PXLkCN3ZfYzvwj74LuyF78M+tBN42bJlncfxzEbQlLAsV2nAxP8A9qDfA9+FPfBd2Affhb3wfdiHt7reUwgOAADgAYImAAAADxA0iUh4eLiMHj3aXMO3+C7sg+/CPvgu7IXvI+t+F0GWt9bpAQAA+DEyTQAAAB4gaAIAAPAAQRMAAIAHCJoAAAA8kOWDpqlTp0r58uUle/bs0rhxY9mwYYOvh+T3Vq5cKV26dJGSJUtKUFCQzJ8/3+1xXXswatQoKVGihOTIkUPatWsne/fuddvn9OnT0qdPH9M4Ln/+/PLwww/LhQsX3Pb57bff5NZbbzXfnXbnnTBhglfenz8ZO3asNGrUSPLkySNFixaVbt26ye7du932uXLlijzxxBNSqFAhyZ07t/To0UOOHz/uto92y+/cubPkzJnTPM/w4cMlJibGbZ8VK1bIzTffbFaxVK5cWWbNmuWV9+gv3nvvPalTp46zIWLTpk1lwYIFzsf5Hnxn3Lhx5m/VoEGDnNv4PrzjpZdeMp+966VatWr2/R6sLOyLL76wsmXLZv3nP/+xduzYYfXv39/Knz+/dfz4cV8Pza/973//s55//nnrm2++0ZWZ1rx589weHzdunJUvXz5r/vz51rZt26w777zTqlChgnX58mXnPh06dLDq1q1rrVu3zvrll1+sypUrW/fdd5/z8XPnzlnFihWz+vTpY23fvt36/PPPrRw5cljvv/++V9+r3bVv396aOXOm+Yy2bt1qderUySpbtqx14cIF5z6PPvqoVaZMGWvp0qXWxo0brSZNmljNmjVzPh4TE2PVqlXLateunbVlyxbz/RYuXNgaOXKkc58///zTypkzpzVkyBBr586d1jvvvGOFhIRYCxcu9Pp7tqvvvvvO+vHHH609e/ZYu3fvtp577jkrLCzMfDeK78E3NmzYYJUvX96qU6eO9fTTTzu38314x+jRo62aNWtax44dc17++ecf234PWTpouuWWW6wnnnjCeT82NtYqWbKkNXbsWJ+OK5AkDpri4uKs4sWLW2+88YZz29mzZ63w8HAT+Cj9pdaf+/XXX537LFiwwAoKCrKOHj1q7k+bNs0qUKCAFRUV5dzn2WeftapWreqld+afTpw4YT7bn3/+2fnZ64H7q6++cu6za9cus8/atWvNff0jFBwcbEVERDj3ee+996y8efM6P/9nnnnG/OFz1bNnTxO0IXn6O/zhhx/yPfjI+fPnrSpVqlhLliyxWrVq5Qya+D68GzTVrVs3ycfs+D1k2em5q1evyqZNm8zUkOu5a/T+2rVrfTq2QHbgwAGJiIhw+9z1nH86Ner43PVap+QaNmzo3Ef31+9n/fr1zn1atmwp2bJlc+7Tvn17M/V05swZr74nfzu5pXKc3FL/H4iOjnb7PjQ1rifAdP0+ateuLcWKFXP7rPWkpTt27HDu4/ocjn34fylpsbGx8sUXX8jFixfNNB3fg2/otI9O6yT+zPg+vGvv3r2mnKNixYqmLEOn2+z6PWTZoOnkyZPmD5frB630vh7UkTkcn21Kn7te67y0q9DQUHOgd90nqedwfQ24i4uLMzUbzZs3l1q1ajk/Kw08NUhN6fu40Wed3D76h+vy5cuZ+r78ye+//27qMrSu4tFHH5V58+ZJjRo1+B58QIPWzZs3m7q/xPg+vKdx48amvmjhwoWm7k//Ya21qufPn7fl9xCapncJwC//Vb19+3ZZtWqVr4eSZVWtWlW2bt1qMn5ff/219O3bV37++WdfDyvLOXLkiDz99NOyZMkSs5AEvtOxY0fnbV0ooUFUuXLl5MsvvzQLhewmy2aaChcuLCEhIddV4ev94sWL+2xcgc7x2ab0uev1iRMn3B7XlRC6os51n6Sew/U1cM3AgQPlhx9+kOXLl0vp0qWd2/Wz0qnqs2fPpvh93OizTm4fXSVmxz98vqL/ataVOw0aNDAZjrp168rbb7/N9+BlOu2jf2N0NZVmsfWiweuUKVPMbc1C8H34Rv78+eWmm26Sffv22fL/i+Cs/MdL/3AtXbrUbfpC72uNATJHhQoVzC+w6+euKVKtVXJ87nqt/5PoHzaHZcuWme9H/xXi2EdbG+h8t4P+q1H/JV+gQAGvvic701p8DZh0Gkg/Q/38Xen/A2FhYW7fh9aFaU2B6/eh00qugax+1voHR6eWHPu4PodjH/5fSpn+TkdFRfE9eFnbtm3NZ6lZP8dFayi1nsZxm+/DNy5cuCD79+83LWls+f+FlcVbDuiqrVmzZpkVWwMGDDAtB1yr8JG2FSm69FMv+is2adIkc/vQoUPOlgP6OX/77bfWb7/9ZnXt2jXJlgP169e31q9fb61atcqscHFtOaCrKrTlwP3332+WbOt3qUtKaTng7rHHHjPtHVasWOG2pPfSpUtuS3q1DcGyZcvMkt6mTZuaS+IlvXfccYdpW6DLdIsUKZLkkt7hw4eb1S1Tp05laXUiI0aMMKsWDxw4YH7v9b6uCF28eLF5nO/Bt1xXzym+D+8YOnSo+fuk/1+sXr3atA7QlgG60teO30OWDpqU9mvQL0T7NWkLAu0LhPRZvny5CZYSX/r27etsO/Diiy+aoEeD1rZt25q+Na5OnTplgqTcuXObpaMPPfSQCcZcaY+nFi1amOcoVaqUCcbgLqnvQS/au8lBg9XHH3/cLH/XPyx33XWXCaxcHTx40OrYsaPphaV/0PQPXXR09HXfe7169cz/SxUrVnR7DVhWv379rHLlypnPR/+o6++9I2BSfA/2Cpr4PryjZ8+eVokSJczno3/H9f6+ffts+z0E6X/SnkgDAADIGrJsTRMAAEBqEDQBAAB4gKAJAADAAwRNAAAAHiBoAgAA8ABBEwAAgAcImgAAADxA0ATAr/zxxx/SpEkTc6LVevXqJblP69atZdCgQV4fG4DARnNLAJnin3/+kVKlSsmZM2fMuR71RJy7du2SsmXLput5e/bsKSdPnpT//Oc/kjt3bilUqNB1++jJnfWcVXny5BFveumll2T+/Pnm/GUAAk+orwcAIDCtXbtW6tatK7ly5TInZC5YsGC6AyalJ/Ps3LmzlCtXLtl99LUAIKMxPQcgU6xZs0aaN29ubq9atcp5OyVxcXHy8ssvS+nSpSU8PNxMvy1cuND5eFBQkGzatMnso7c1s+PJ9Fz58uXl9ddfl379+pnskwZvH3zwgfPxgwcPmuf74osvpFmzZmbqr1atWvLzzz8795k1a5bJlrnSrJL+nOPxMWPGyLZt28w2veg2TebrOPU19T2VLFlSnnrqqVR9lgDsgUwTgAxz+PBhqVOnjrl96dIlCQkJMYHD5cuXTRChQUfv3r1l2rRpSf7822+/LRMnTpT3339f6tevb6bg7rzzTtmxY4dUqVJFjh07Ju3atZMOHTrIsGHDzPScp/R5X3nlFXnuuefk66+/lscee0xatWolVatWde4zfPhwmTx5stSoUUMmTZokXbp0kQMHDiQ5BZjUtOH27dtNkPfTTz+Zbfny5ZO5c+fKW2+9ZQKymjVrSkREhAmsAPgfMk0AMoxmUbSeZ+XKlea+TstpZkhrmhYvXmwe0yxRct5880159tlnpVevXiaYGT9+vMk2aSCjihcvLqGhoSZY0tupCZo6deokjz/+uFSuXNm8RuHChWX58uVu+wwcOFB69Ogh1atXl/fee88EPR999JFHz58jRw4zHh2fjk0vuk0DSb2twZ5mm2655Rbp37+/x+MGYB8ETQAyjAYMOhWmK9waNWpksk6aWSlWrJi0bNnSPKbBSlIiIyPl77//vm4aT+9rAXl6OTJgSrNeGsicOHHCbZ+mTZu6vZeGDRum+7Xvuecek2mrWLGiCZbmzZsnMTEx6XpOAL7B9ByADKPTT4cOHZLo6GhTn6SZFw0Q9KK3tXhbp9p8QVfTudLAScfoqeDgYFOf5Erf542UKVNGdu/ebabslixZYrJdb7zxhqmXSjwmAPZGpglAhvnf//5npuA0i/Ppp5+a21pQrdNrelsfT07evHnN9N7q1avdtut9rTHyhnXr1jlva6CnU4s6VaeKFCki58+fl4sXLzr3SdxaQKchY2Njr3tenabT+qgpU6bIihUrzMrC33//PVPfC4CMR6YJQIbRTJJOxx0/fly6du1qsjmaWdI6oRIlStzw57UQe/To0VKpUiVTyzRz5kwTmHz22WdeGf/UqVNNwbkGSlq8rT2mdMWdaty4seTMmdMUkuvqN63X0iJ3Vzr9qIXjOmZdAagr9T7//HMTSDl+XoNJDaJSapkAwJ7INAHIUJpJ0XomXba/YcMGEzx4EjApDUaGDBkiQ4cOldq1a5uVaN99950JZLxh3Lhx5qL9pbRNgr62owZLez9pwKPZMh2bBkOJWx5ocKgr+9q0aWMyU7qPrhicMWOGqc3Suiqdpvv+++89WpEHwF7oCA4gy9M+TRUqVJAtW7Yke2oWACDTBAAA4AGCJgAAAA8wPQcAAOABMk0AAAAeIGgCAADwAEETAACABwiaAAAAPEDQBAAA4AGCJgAAAA8QNAEAAHiAoAkAAMADBE0AAAByY/8Pl4NMYRoDVWEAAAAASUVORK5CYII=", "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "_, dict_cov = population_coverage(dict_fuzzer.inputs, my_parser)\n", "_, fuzz_cov = population_coverage(fuzzer.inputs, my_parser)\n", "line_dict, = plt.plot(dict_cov, label=\"With Dictionary\")\n", "line_fuzz, = plt.plot(fuzz_cov, label=\"Without Dictionary\")\n", "plt.legend(handles=[line_dict, line_fuzz])\n", "plt.xlim(0, n)\n", "plt.title('Coverage over time')\n", "plt.xlabel('# of inputs')\n", "plt.ylabel('lines covered');" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "\n", "\n", "***Summary.*** Informing the fuzzer about important keywords already goes a long way towards achieving lots of coverage quickly.\n", "\n", "***Try it.*** Open this chapter as Jupyter notebook and add other HTML-related keywords to the dictionary in order to see whether the difference in coverage actually increases (given the same budget of 5k generated test inputs).\n", "\n", "***Read up.*** Michał Zalewski, author of AFL, wrote several great blog posts on [making up grammars with a dictionary in hand](https://lcamtuf.blogspot.com/2015/01/afl-fuzz-making-up-grammar-with.html) and [pulling JPEGs out of thin air](https://lcamtuf.blogspot.com/2014/11/pulling-jpegs-out-of-thin-air.html)!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" }, "tags": [], "toc-hr-collapsed": false }, "source": [ "## Fuzzing with Input Fragments\n", "\n", "While dictionaries are helpful to inject important keywords into seed inputs, they do not allow maintaining the structural integrity of the generated inputs. Instead, we need to make the fuzzer aware of the _input structure_. We can do this using [grammars](Grammars.ipynb). Our first approach \n", "\n", "1. [parses](Parser.ipynb) the seed inputs, \n", "2. disassembles them into input fragments, and \n", "3. generates new files by reassembling these fragments according to the rules of the grammar." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "This combination of _parsing_ and _fuzzing_ can be very powerful. For instance, we can _swap_ existing substructures in an input:\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "We can also _replace_ existing substructures by newly generated ones:\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "All these operations take place on [derivation trees](GrammarFuzzer.ipynb), which can be parsed from and produced into strings at any time." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Parsing and Recombining JavaScript, or How to Make 50,000 USD in Four Weeks\n", "\n", "In \"Fuzzing with Code Fragments\" \\cite{Holler2012}, Holler, Herzig, and Zeller apply these steps to fuzz a JavaScript interpreter. They use a JavaScript grammar to\n", "\n", "1. _parse_ (valid) JavaScript inputs into parse trees,\n", "2. _disassemble_ them into fragments (subtrees),\n", "3. _recombine_ these fragments into valid JavaScript programs again, and\n", "4. _feed_ these programs into a JavaScript interpreter for execution." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "As in most fuzzing scenarios, the aim is to cause the JavaScript interpreter to crash. Here is an example of LangFuzz-generated JavaScript code (from \\cite{Holler2012}) that caused a crash in the Mozilla JavaScript interpreter:\n", "\n", "```javascript\n", "var haystack = \"foo\";\n", "var re_text = \"^foo\";\n", "haystack += \"x\";\n", "re_text += \"(x)\";\n", "var re = new RegExp(re_text);\n", "re.test(haystack);\n", "RegExp.input = Number();\n", "print(RegExp.$1);\n", "```" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "From a crash of the JavaScript interpreter, it is frequently possible to construct an *exploit* that will not only crash the interpreter, but instead have it execute code under the attacker's control. Therefore, such crashes are serious flaws, which is why you get a bug bounty if you report them." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "In the first four weeks of running his _LangFuzz_ tool, Christian Holler, first author of that paper, netted _more than USD 50,000 in bug bounties_. To date, LangFuzz has found more than 2,600 bugs in the JavaScript browsers of Mozilla Firefox, Google Chrome, and Microsoft Edge. If you use any of these browsers (say, on your Android phone), the combination of parsing and fuzzing has contributed significantly in making your browsing session secure.\n", "\n", "(Note that these are the same Holler and Zeller who are co-authors of this book. If you ever wondered why we devote a couple of chapters on grammar-based fuzzing, that's because we have had some great experience with it.)" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Parsing and Recombining HTML\n", "\n", "In this book, let us stay with HTML input for a while. To generate valid HTML inputs for our Python `HTMLParser`, we should first define a simple grammar. It allows defining HTML tags with attributes. Our context-free grammar does not require that opening and closing tags must match. However, we will see that such context-sensitive features can be maintained in the derived input fragments, and thus in the generated inputs." ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:52.099107Z", "iopub.status.busy": "2025-10-26T13:27:52.099006Z", "iopub.status.idle": "2025-10-26T13:27:52.100597Z", "shell.execute_reply": "2025-10-26T13:27:52.100335Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import string" ] }, { "cell_type": "code", "execution_count": 22, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:52.101787Z", "iopub.status.busy": "2025-10-26T13:27:52.101710Z", "iopub.status.idle": "2025-10-26T13:27:52.150666Z", "shell.execute_reply": "2025-10-26T13:27:52.150408Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from Grammars import is_valid_grammar, srange, Grammar" ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:52.152294Z", "iopub.status.busy": "2025-10-26T13:27:52.152202Z", "iopub.status.idle": "2025-10-26T13:27:52.153818Z", "shell.execute_reply": "2025-10-26T13:27:52.153606Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "XML_TOKENS: Set[str] = {\"\", \"\"}" ] }, { "cell_type": "code", "execution_count": 24, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:52.155107Z", "iopub.status.busy": "2025-10-26T13:27:52.155028Z", "iopub.status.idle": "2025-10-26T13:27:52.157015Z", "shell.execute_reply": "2025-10-26T13:27:52.156807Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "XML_GRAMMAR: Grammar = {\n", " \"\": [\"\"],\n", " \"\": [\"\",\n", " \"\",\n", " \"\",\n", " \"\"],\n", " \"\": [\"<>\", \"< >\"],\n", " \"\": [\"</>\", \"< />\"],\n", " \"\": [\">\"],\n", " \"\": [\"=\", \" \"],\n", " \"\": [\"\", \"\"],\n", " \"\": [\"\", \"\"],\n", " \"\": srange(string.ascii_letters + string.digits +\n", " \"\\\"\" + \"'\" + \".\"),\n", " \"\": srange(string.ascii_letters + string.digits +\n", " \"\\\"\" + \"'\" + \" \" + \"\\t\"),\n", "}" ] }, { "cell_type": "code", "execution_count": 25, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:52.158270Z", "iopub.status.busy": "2025-10-26T13:27:52.158191Z", "iopub.status.idle": "2025-10-26T13:27:52.159909Z", "shell.execute_reply": "2025-10-26T13:27:52.159645Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "assert is_valid_grammar(XML_GRAMMAR)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "In order to parse an input into a derivation tree, we use the [Earley parser](Parser.ipynb#Parsing-Context-Free-Grammars)." ] }, { "cell_type": "code", "execution_count": 26, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:52.161320Z", "iopub.status.busy": "2025-10-26T13:27:52.161238Z", "iopub.status.idle": "2025-10-26T13:27:52.220738Z", "shell.execute_reply": "2025-10-26T13:27:52.220476Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from Parser import EarleyParser, Parser\n", "from GrammarFuzzer import display_tree, DerivationTree" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Let's run the parser on a simple HTML input and display all possible parse trees. A *parse tree* represents the input structure according to the given grammar." ] }, { "cell_type": "code", "execution_count": 27, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:52.222367Z", "iopub.status.busy": "2025-10-26T13:27:52.222274Z", "iopub.status.idle": "2025-10-26T13:27:52.223906Z", "shell.execute_reply": "2025-10-26T13:27:52.223662Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from IPython.display import display" ] }, { "cell_type": "code", "execution_count": 28, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:52.225456Z", "iopub.status.busy": "2025-10-26T13:27:52.225358Z", "iopub.status.idle": "2025-10-26T13:27:57.864448Z", "shell.execute_reply": "2025-10-26T13:27:57.864115Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "0\n", "<start>\n", "\n", "\n", "\n", "1\n", "<xml-tree>\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "\n", "\n", "\n", "2\n", "<xml-open-tag>\n", "\n", "\n", "\n", "1->2\n", "\n", "\n", "\n", "\n", "\n", "7\n", "<xml-tree>\n", "\n", "\n", "\n", "1->7\n", "\n", "\n", "\n", "\n", "\n", "10\n", "<xml-close-tag>\n", "\n", "\n", "\n", "1->10\n", "\n", "\n", "\n", "\n", "\n", "3\n", "< (60)\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "\n", "\n", "\n", "4\n", "<id>\n", "\n", "\n", "\n", "2->4\n", "\n", "\n", "\n", "\n", "\n", "6\n", "> (62)\n", "\n", "\n", "\n", "2->6\n", "\n", "\n", "\n", "\n", "\n", "5\n", "html\n", "\n", "\n", "\n", "4->5\n", "\n", "\n", "\n", "\n", "\n", "8\n", "<text>\n", "\n", "\n", "\n", "7->8\n", "\n", "\n", "\n", "\n", "\n", "9\n", "Text\n", "\n", "\n", "\n", "8->9\n", "\n", "\n", "\n", "\n", "\n", "11\n", "</\n", "\n", "\n", "\n", "10->11\n", "\n", "\n", "\n", "\n", "\n", "12\n", "<id>\n", "\n", "\n", "\n", "10->12\n", "\n", "\n", "\n", "\n", "\n", "14\n", "> (62)\n", "\n", "\n", "\n", "10->14\n", "\n", "\n", "\n", "\n", "\n", "13\n", "html\n", "\n", "\n", "\n", "12->13\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "0\n", "<start>\n", "\n", "\n", "\n", "1\n", "<xml-tree>\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "\n", "\n", "\n", "2\n", "<xml-open-tag>\n", "\n", "\n", "\n", "1->2\n", "\n", "\n", "\n", "\n", "\n", "7\n", "<xml-tree>\n", "\n", "\n", "\n", "1->7\n", "\n", "\n", "\n", "\n", "\n", "14\n", "<xml-close-tag>\n", "\n", "\n", "\n", "1->14\n", "\n", "\n", "\n", "\n", "\n", "3\n", "< (60)\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "\n", "\n", "\n", "4\n", "<id>\n", "\n", "\n", "\n", "2->4\n", "\n", "\n", "\n", "\n", "\n", "6\n", "> (62)\n", "\n", "\n", "\n", "2->6\n", "\n", "\n", "\n", "\n", "\n", "5\n", "html\n", "\n", "\n", "\n", "4->5\n", "\n", "\n", "\n", "\n", "\n", "8\n", "<xml-tree>\n", "\n", "\n", "\n", "7->8\n", "\n", "\n", "\n", "\n", "\n", "11\n", "<xml-tree>\n", "\n", "\n", "\n", "7->11\n", "\n", "\n", "\n", "\n", "\n", "9\n", "<text>\n", "\n", "\n", "\n", "8->9\n", "\n", "\n", "\n", "\n", "\n", "10\n", "T (84)\n", "\n", "\n", "\n", "9->10\n", "\n", "\n", "\n", "\n", "\n", "12\n", "<text>\n", "\n", "\n", "\n", "11->12\n", "\n", "\n", "\n", "\n", "\n", "13\n", "ext\n", "\n", "\n", "\n", "12->13\n", "\n", "\n", "\n", "\n", "\n", "15\n", "</\n", "\n", "\n", "\n", "14->15\n", "\n", "\n", "\n", "\n", "\n", "16\n", "<id>\n", "\n", "\n", "\n", "14->16\n", "\n", "\n", "\n", "\n", "\n", "18\n", "> (62)\n", "\n", "\n", "\n", "14->18\n", "\n", "\n", "\n", "\n", "\n", "17\n", "html\n", "\n", "\n", "\n", "16->17\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "0\n", "<start>\n", "\n", "\n", "\n", "1\n", "<xml-tree>\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "\n", "\n", "\n", "2\n", "<xml-open-tag>\n", "\n", "\n", "\n", "1->2\n", "\n", "\n", "\n", "\n", "\n", "7\n", "<xml-tree>\n", "\n", "\n", "\n", "1->7\n", "\n", "\n", "\n", "\n", "\n", "14\n", "<xml-close-tag>\n", "\n", "\n", "\n", "1->14\n", "\n", "\n", "\n", "\n", "\n", "3\n", "< (60)\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "\n", "\n", "\n", "4\n", "<id>\n", "\n", "\n", "\n", "2->4\n", "\n", "\n", "\n", "\n", "\n", "6\n", "> (62)\n", "\n", "\n", "\n", "2->6\n", "\n", "\n", "\n", "\n", "\n", "5\n", "html\n", "\n", "\n", "\n", "4->5\n", "\n", "\n", "\n", "\n", "\n", "8\n", "<xml-tree>\n", "\n", "\n", "\n", "7->8\n", "\n", "\n", "\n", "\n", "\n", "11\n", "<xml-tree>\n", "\n", "\n", "\n", "7->11\n", "\n", "\n", "\n", "\n", "\n", "9\n", "<text>\n", "\n", "\n", "\n", "8->9\n", "\n", "\n", "\n", "\n", "\n", "10\n", "Te\n", "\n", "\n", "\n", "9->10\n", "\n", "\n", "\n", "\n", "\n", "12\n", "<text>\n", "\n", "\n", "\n", "11->12\n", "\n", "\n", "\n", "\n", "\n", "13\n", "xt\n", "\n", "\n", "\n", "12->13\n", "\n", "\n", "\n", "\n", "\n", "15\n", "</\n", "\n", "\n", "\n", "14->15\n", "\n", "\n", "\n", "\n", "\n", "16\n", "<id>\n", "\n", "\n", "\n", "14->16\n", "\n", "\n", "\n", "\n", "\n", "18\n", "> (62)\n", "\n", "\n", "\n", "14->18\n", "\n", "\n", "\n", "\n", "\n", "17\n", "html\n", "\n", "\n", "\n", "16->17\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "0\n", "<start>\n", "\n", "\n", "\n", "1\n", "<xml-tree>\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "\n", "\n", "\n", "2\n", "<xml-open-tag>\n", "\n", "\n", "\n", "1->2\n", "\n", "\n", "\n", "\n", "\n", "7\n", "<xml-tree>\n", "\n", "\n", "\n", "1->7\n", "\n", "\n", "\n", "\n", "\n", "18\n", "<xml-close-tag>\n", "\n", "\n", "\n", "1->18\n", "\n", "\n", "\n", "\n", "\n", "3\n", "< (60)\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "\n", "\n", "\n", "4\n", "<id>\n", "\n", "\n", "\n", "2->4\n", "\n", "\n", "\n", "\n", "\n", "6\n", "> (62)\n", "\n", "\n", "\n", "2->6\n", "\n", "\n", "\n", "\n", "\n", "5\n", "html\n", "\n", "\n", "\n", "4->5\n", "\n", "\n", "\n", "\n", "\n", "8\n", "<xml-tree>\n", "\n", "\n", "\n", "7->8\n", "\n", "\n", "\n", "\n", "\n", "15\n", "<xml-tree>\n", "\n", "\n", "\n", "7->15\n", "\n", "\n", "\n", "\n", "\n", "9\n", "<xml-tree>\n", "\n", "\n", "\n", "8->9\n", "\n", "\n", "\n", "\n", "\n", "12\n", "<xml-tree>\n", "\n", "\n", "\n", "8->12\n", "\n", "\n", "\n", "\n", "\n", "10\n", "<text>\n", "\n", "\n", "\n", "9->10\n", "\n", "\n", "\n", "\n", "\n", "11\n", "T (84)\n", "\n", "\n", "\n", "10->11\n", "\n", "\n", "\n", "\n", "\n", "13\n", "<text>\n", "\n", "\n", "\n", "12->13\n", "\n", "\n", "\n", "\n", "\n", "14\n", "e (101)\n", "\n", "\n", "\n", "13->14\n", "\n", "\n", "\n", "\n", "\n", "16\n", "<text>\n", "\n", "\n", "\n", "15->16\n", "\n", "\n", "\n", "\n", "\n", "17\n", "xt\n", "\n", "\n", "\n", "16->17\n", "\n", "\n", "\n", "\n", "\n", "19\n", "</\n", "\n", "\n", "\n", "18->19\n", "\n", "\n", "\n", "\n", "\n", "20\n", "<id>\n", "\n", "\n", "\n", "18->20\n", "\n", "\n", "\n", "\n", "\n", "22\n", "> (62)\n", "\n", "\n", "\n", "18->22\n", "\n", "\n", "\n", "\n", "\n", "21\n", "html\n", "\n", "\n", "\n", "20->21\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "0\n", "<start>\n", "\n", "\n", "\n", "1\n", "<xml-tree>\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "\n", "\n", "\n", "2\n", "<xml-open-tag>\n", "\n", "\n", "\n", "1->2\n", "\n", "\n", "\n", "\n", "\n", "7\n", "<xml-tree>\n", "\n", "\n", "\n", "1->7\n", "\n", "\n", "\n", "\n", "\n", "14\n", "<xml-close-tag>\n", "\n", "\n", "\n", "1->14\n", "\n", "\n", "\n", "\n", "\n", "3\n", "< (60)\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "\n", "\n", "\n", "4\n", "<id>\n", "\n", "\n", "\n", "2->4\n", "\n", "\n", "\n", "\n", "\n", "6\n", "> (62)\n", "\n", "\n", "\n", "2->6\n", "\n", "\n", "\n", "\n", "\n", "5\n", "html\n", "\n", "\n", "\n", "4->5\n", "\n", "\n", "\n", "\n", "\n", "8\n", "<xml-tree>\n", "\n", "\n", "\n", "7->8\n", "\n", "\n", "\n", "\n", "\n", "11\n", "<xml-tree>\n", "\n", "\n", "\n", "7->11\n", "\n", "\n", "\n", "\n", "\n", "9\n", "<text>\n", "\n", "\n", "\n", "8->9\n", "\n", "\n", "\n", "\n", "\n", "10\n", "Tex\n", "\n", "\n", "\n", "9->10\n", "\n", "\n", "\n", "\n", "\n", "12\n", "<text>\n", "\n", "\n", "\n", "11->12\n", "\n", "\n", "\n", "\n", "\n", "13\n", "t (116)\n", "\n", "\n", "\n", "12->13\n", "\n", "\n", "\n", "\n", "\n", "15\n", "</\n", "\n", "\n", "\n", "14->15\n", "\n", "\n", "\n", "\n", "\n", "16\n", "<id>\n", "\n", "\n", "\n", "14->16\n", "\n", "\n", "\n", "\n", "\n", "18\n", "> (62)\n", "\n", "\n", "\n", "14->18\n", "\n", "\n", "\n", "\n", "\n", "17\n", "html\n", "\n", "\n", "\n", "16->17\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "0\n", "<start>\n", "\n", "\n", "\n", "1\n", "<xml-tree>\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "\n", "\n", "\n", "2\n", "<xml-open-tag>\n", "\n", "\n", "\n", "1->2\n", "\n", "\n", "\n", "\n", "\n", "7\n", "<xml-tree>\n", "\n", "\n", "\n", "1->7\n", "\n", "\n", "\n", "\n", "\n", "18\n", "<xml-close-tag>\n", "\n", "\n", "\n", "1->18\n", "\n", "\n", "\n", "\n", "\n", "3\n", "< (60)\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "\n", "\n", "\n", "4\n", "<id>\n", "\n", "\n", "\n", "2->4\n", "\n", "\n", "\n", "\n", "\n", "6\n", "> (62)\n", "\n", "\n", "\n", "2->6\n", "\n", "\n", "\n", "\n", "\n", "5\n", "html\n", "\n", "\n", "\n", "4->5\n", "\n", "\n", "\n", "\n", "\n", "8\n", "<xml-tree>\n", "\n", "\n", "\n", "7->8\n", "\n", "\n", "\n", "\n", "\n", "15\n", "<xml-tree>\n", "\n", "\n", "\n", "7->15\n", "\n", "\n", "\n", "\n", "\n", "9\n", "<xml-tree>\n", "\n", "\n", "\n", "8->9\n", "\n", "\n", "\n", "\n", "\n", "12\n", "<xml-tree>\n", "\n", "\n", "\n", "8->12\n", "\n", "\n", "\n", "\n", "\n", "10\n", "<text>\n", "\n", "\n", "\n", "9->10\n", "\n", "\n", "\n", "\n", "\n", "11\n", "T (84)\n", "\n", "\n", "\n", "10->11\n", "\n", "\n", "\n", "\n", "\n", "13\n", "<text>\n", "\n", "\n", "\n", "12->13\n", "\n", "\n", "\n", "\n", "\n", "14\n", "ex\n", "\n", "\n", "\n", "13->14\n", "\n", "\n", "\n", "\n", "\n", "16\n", "<text>\n", "\n", "\n", "\n", "15->16\n", "\n", "\n", "\n", "\n", "\n", "17\n", "t (116)\n", "\n", "\n", "\n", "16->17\n", "\n", "\n", "\n", "\n", "\n", "19\n", "</\n", "\n", "\n", "\n", "18->19\n", "\n", "\n", "\n", "\n", "\n", "20\n", "<id>\n", "\n", "\n", "\n", "18->20\n", "\n", "\n", "\n", "\n", "\n", "22\n", "> (62)\n", "\n", "\n", "\n", "18->22\n", "\n", "\n", "\n", "\n", "\n", "21\n", "html\n", "\n", "\n", "\n", "20->21\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "0\n", "<start>\n", "\n", "\n", "\n", "1\n", "<xml-tree>\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "\n", "\n", "\n", "2\n", "<xml-open-tag>\n", "\n", "\n", "\n", "1->2\n", "\n", "\n", "\n", "\n", "\n", "7\n", "<xml-tree>\n", "\n", "\n", "\n", "1->7\n", "\n", "\n", "\n", "\n", "\n", "18\n", "<xml-close-tag>\n", "\n", "\n", "\n", "1->18\n", "\n", "\n", "\n", "\n", "\n", "3\n", "< (60)\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "\n", "\n", "\n", "4\n", "<id>\n", "\n", "\n", "\n", "2->4\n", "\n", "\n", "\n", "\n", "\n", "6\n", "> (62)\n", "\n", "\n", "\n", "2->6\n", "\n", "\n", "\n", "\n", "\n", "5\n", "html\n", "\n", "\n", "\n", "4->5\n", "\n", "\n", "\n", "\n", "\n", "8\n", "<xml-tree>\n", "\n", "\n", "\n", "7->8\n", "\n", "\n", "\n", "\n", "\n", "15\n", "<xml-tree>\n", "\n", "\n", "\n", "7->15\n", "\n", "\n", "\n", "\n", "\n", "9\n", "<xml-tree>\n", "\n", "\n", "\n", "8->9\n", "\n", "\n", "\n", "\n", "\n", "12\n", "<xml-tree>\n", "\n", "\n", "\n", "8->12\n", "\n", "\n", "\n", "\n", "\n", "10\n", "<text>\n", "\n", "\n", "\n", "9->10\n", "\n", "\n", "\n", "\n", "\n", "11\n", "Te\n", "\n", "\n", "\n", "10->11\n", "\n", "\n", "\n", "\n", "\n", "13\n", "<text>\n", "\n", "\n", "\n", "12->13\n", "\n", "\n", "\n", "\n", "\n", "14\n", "x (120)\n", "\n", "\n", "\n", "13->14\n", "\n", "\n", "\n", "\n", "\n", "16\n", "<text>\n", "\n", "\n", "\n", "15->16\n", "\n", "\n", "\n", "\n", "\n", "17\n", "t (116)\n", "\n", "\n", "\n", "16->17\n", "\n", "\n", "\n", "\n", "\n", "19\n", "</\n", "\n", "\n", "\n", "18->19\n", "\n", "\n", "\n", "\n", "\n", "20\n", "<id>\n", "\n", "\n", "\n", "18->20\n", "\n", "\n", "\n", "\n", "\n", "22\n", "> (62)\n", "\n", "\n", "\n", "18->22\n", "\n", "\n", "\n", "\n", "\n", "21\n", "html\n", "\n", "\n", "\n", "20->21\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "0\n", "<start>\n", "\n", "\n", "\n", "1\n", "<xml-tree>\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "\n", "\n", "\n", "2\n", "<xml-open-tag>\n", "\n", "\n", "\n", "1->2\n", "\n", "\n", "\n", "\n", "\n", "7\n", "<xml-tree>\n", "\n", "\n", "\n", "1->7\n", "\n", "\n", "\n", "\n", "\n", "22\n", "<xml-close-tag>\n", "\n", "\n", "\n", "1->22\n", "\n", "\n", "\n", "\n", "\n", "3\n", "< (60)\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "\n", "\n", "\n", "4\n", "<id>\n", "\n", "\n", "\n", "2->4\n", "\n", "\n", "\n", "\n", "\n", "6\n", "> (62)\n", "\n", "\n", "\n", "2->6\n", "\n", "\n", "\n", "\n", "\n", "5\n", "html\n", "\n", "\n", "\n", "4->5\n", "\n", "\n", "\n", "\n", "\n", "8\n", "<xml-tree>\n", "\n", "\n", "\n", "7->8\n", "\n", "\n", "\n", "\n", "\n", "19\n", "<xml-tree>\n", "\n", "\n", "\n", "7->19\n", "\n", "\n", "\n", "\n", "\n", "9\n", "<xml-tree>\n", "\n", "\n", "\n", "8->9\n", "\n", "\n", "\n", "\n", "\n", "16\n", "<xml-tree>\n", "\n", "\n", "\n", "8->16\n", "\n", "\n", "\n", "\n", "\n", "10\n", "<xml-tree>\n", "\n", "\n", "\n", "9->10\n", "\n", "\n", "\n", "\n", "\n", "13\n", "<xml-tree>\n", "\n", "\n", "\n", "9->13\n", "\n", "\n", "\n", "\n", "\n", "11\n", "<text>\n", "\n", "\n", "\n", "10->11\n", "\n", "\n", "\n", "\n", "\n", "12\n", "T (84)\n", "\n", "\n", "\n", "11->12\n", "\n", "\n", "\n", "\n", "\n", "14\n", "<text>\n", "\n", "\n", "\n", "13->14\n", "\n", "\n", "\n", "\n", "\n", "15\n", "e (101)\n", "\n", "\n", "\n", "14->15\n", "\n", "\n", "\n", "\n", "\n", "17\n", "<text>\n", "\n", "\n", "\n", "16->17\n", "\n", "\n", "\n", "\n", "\n", "18\n", "x (120)\n", "\n", "\n", "\n", "17->18\n", "\n", "\n", "\n", "\n", "\n", "20\n", "<text>\n", "\n", "\n", "\n", "19->20\n", "\n", "\n", "\n", "\n", "\n", "21\n", "t (116)\n", "\n", "\n", "\n", "20->21\n", "\n", "\n", "\n", "\n", "\n", "23\n", "</\n", "\n", "\n", "\n", "22->23\n", "\n", "\n", "\n", "\n", "\n", "24\n", "<id>\n", "\n", "\n", "\n", "22->24\n", "\n", "\n", "\n", "\n", "\n", "26\n", "> (62)\n", "\n", "\n", "\n", "22->26\n", "\n", "\n", "\n", "\n", "\n", "25\n", "html\n", "\n", "\n", "\n", "24->25\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "0\n", "<start>\n", "\n", "\n", "\n", "1\n", "<xml-tree>\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "\n", "\n", "\n", "2\n", "<xml-open-tag>\n", "\n", "\n", "\n", "1->2\n", "\n", "\n", "\n", "\n", "\n", "7\n", "<xml-tree>\n", "\n", "\n", "\n", "1->7\n", "\n", "\n", "\n", "\n", "\n", "22\n", "<xml-close-tag>\n", "\n", "\n", "\n", "1->22\n", "\n", "\n", "\n", "\n", "\n", "3\n", "< (60)\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "\n", "\n", "\n", "4\n", "<id>\n", "\n", "\n", "\n", "2->4\n", "\n", "\n", "\n", "\n", "\n", "6\n", "> (62)\n", "\n", "\n", "\n", "2->6\n", "\n", "\n", "\n", "\n", "\n", "5\n", "html\n", "\n", "\n", "\n", "4->5\n", "\n", "\n", "\n", "\n", "\n", "8\n", "<xml-tree>\n", "\n", "\n", "\n", "7->8\n", "\n", "\n", "\n", "\n", "\n", "19\n", "<xml-tree>\n", "\n", "\n", "\n", "7->19\n", "\n", "\n", "\n", "\n", "\n", "9\n", "<xml-tree>\n", "\n", "\n", "\n", "8->9\n", "\n", "\n", "\n", "\n", "\n", "12\n", "<xml-tree>\n", "\n", "\n", "\n", "8->12\n", "\n", "\n", "\n", "\n", "\n", "10\n", "<text>\n", "\n", "\n", "\n", "9->10\n", "\n", "\n", "\n", "\n", "\n", "11\n", "T (84)\n", "\n", "\n", "\n", "10->11\n", "\n", "\n", "\n", "\n", "\n", "13\n", "<xml-tree>\n", "\n", "\n", "\n", "12->13\n", "\n", "\n", "\n", "\n", "\n", "16\n", "<xml-tree>\n", "\n", "\n", "\n", "12->16\n", "\n", "\n", "\n", "\n", "\n", "14\n", "<text>\n", "\n", "\n", "\n", "13->14\n", "\n", "\n", "\n", "\n", "\n", "15\n", "e (101)\n", "\n", "\n", "\n", "14->15\n", "\n", "\n", "\n", "\n", "\n", "17\n", "<text>\n", "\n", "\n", "\n", "16->17\n", "\n", "\n", "\n", "\n", "\n", "18\n", "x (120)\n", "\n", "\n", "\n", "17->18\n", "\n", "\n", "\n", "\n", "\n", "20\n", "<text>\n", "\n", "\n", "\n", "19->20\n", "\n", "\n", "\n", "\n", "\n", "21\n", "t (116)\n", "\n", "\n", "\n", "20->21\n", "\n", "\n", "\n", "\n", "\n", "23\n", "</\n", "\n", "\n", "\n", "22->23\n", "\n", "\n", "\n", "\n", "\n", "24\n", "<id>\n", "\n", "\n", "\n", "22->24\n", "\n", "\n", "\n", "\n", "\n", "26\n", "> (62)\n", "\n", "\n", "\n", "22->26\n", "\n", "\n", "\n", "\n", "\n", "25\n", "html\n", "\n", "\n", "\n", "24->25\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "0\n", "<start>\n", "\n", "\n", "\n", "1\n", "<xml-tree>\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "\n", "\n", "\n", "2\n", "<xml-open-tag>\n", "\n", "\n", "\n", "1->2\n", "\n", "\n", "\n", "\n", "\n", "7\n", "<xml-tree>\n", "\n", "\n", "\n", "1->7\n", "\n", "\n", "\n", "\n", "\n", "18\n", "<xml-close-tag>\n", "\n", "\n", "\n", "1->18\n", "\n", "\n", "\n", "\n", "\n", "3\n", "< (60)\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "\n", "\n", "\n", "4\n", "<id>\n", "\n", "\n", "\n", "2->4\n", "\n", "\n", "\n", "\n", "\n", "6\n", "> (62)\n", "\n", "\n", "\n", "2->6\n", "\n", "\n", "\n", "\n", "\n", "5\n", "html\n", "\n", "\n", "\n", "4->5\n", "\n", "\n", "\n", "\n", "\n", "8\n", "<xml-tree>\n", "\n", "\n", "\n", "7->8\n", "\n", "\n", "\n", "\n", "\n", "11\n", "<xml-tree>\n", "\n", "\n", "\n", "7->11\n", "\n", "\n", "\n", "\n", "\n", "9\n", "<text>\n", "\n", "\n", "\n", "8->9\n", "\n", "\n", "\n", "\n", "\n", "10\n", "T (84)\n", "\n", "\n", "\n", "9->10\n", "\n", "\n", "\n", "\n", "\n", "12\n", "<xml-tree>\n", "\n", "\n", "\n", "11->12\n", "\n", "\n", "\n", "\n", "\n", "15\n", "<xml-tree>\n", "\n", "\n", "\n", "11->15\n", "\n", "\n", "\n", "\n", "\n", "13\n", "<text>\n", "\n", "\n", "\n", "12->13\n", "\n", "\n", "\n", "\n", "\n", "14\n", "e (101)\n", "\n", "\n", "\n", "13->14\n", "\n", "\n", "\n", "\n", "\n", "16\n", "<text>\n", "\n", "\n", "\n", "15->16\n", "\n", "\n", "\n", "\n", "\n", "17\n", "xt\n", "\n", "\n", "\n", "16->17\n", "\n", "\n", "\n", "\n", "\n", "19\n", "</\n", "\n", "\n", "\n", "18->19\n", "\n", "\n", "\n", "\n", "\n", "20\n", "<id>\n", "\n", "\n", "\n", "18->20\n", "\n", "\n", "\n", "\n", "\n", "22\n", "> (62)\n", "\n", "\n", "\n", "18->22\n", "\n", "\n", "\n", "\n", "\n", "21\n", "html\n", "\n", "\n", "\n", "20->21\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "0\n", "<start>\n", "\n", "\n", "\n", "1\n", "<xml-tree>\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "\n", "\n", "\n", "2\n", "<xml-open-tag>\n", "\n", "\n", "\n", "1->2\n", "\n", "\n", "\n", "\n", "\n", "7\n", "<xml-tree>\n", "\n", "\n", "\n", "1->7\n", "\n", "\n", "\n", "\n", "\n", "18\n", "<xml-close-tag>\n", "\n", "\n", "\n", "1->18\n", "\n", "\n", "\n", "\n", "\n", "3\n", "< (60)\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "\n", "\n", "\n", "4\n", "<id>\n", "\n", "\n", "\n", "2->4\n", "\n", "\n", "\n", "\n", "\n", "6\n", "> (62)\n", "\n", "\n", "\n", "2->6\n", "\n", "\n", "\n", "\n", "\n", "5\n", "html\n", "\n", "\n", "\n", "4->5\n", "\n", "\n", "\n", "\n", "\n", "8\n", "<xml-tree>\n", "\n", "\n", "\n", "7->8\n", "\n", "\n", "\n", "\n", "\n", "11\n", "<xml-tree>\n", "\n", "\n", "\n", "7->11\n", "\n", "\n", "\n", "\n", "\n", "9\n", "<text>\n", "\n", "\n", "\n", "8->9\n", "\n", "\n", "\n", "\n", "\n", "10\n", "T (84)\n", "\n", "\n", "\n", "9->10\n", "\n", "\n", "\n", "\n", "\n", "12\n", "<xml-tree>\n", "\n", "\n", "\n", "11->12\n", "\n", "\n", "\n", "\n", "\n", "15\n", "<xml-tree>\n", "\n", "\n", "\n", "11->15\n", "\n", "\n", "\n", "\n", "\n", "13\n", "<text>\n", "\n", "\n", "\n", "12->13\n", "\n", "\n", "\n", "\n", "\n", "14\n", "ex\n", "\n", "\n", "\n", "13->14\n", "\n", "\n", "\n", "\n", "\n", "16\n", "<text>\n", "\n", "\n", "\n", "15->16\n", "\n", "\n", "\n", "\n", "\n", "17\n", "t (116)\n", "\n", "\n", "\n", "16->17\n", "\n", "\n", "\n", "\n", "\n", "19\n", "</\n", "\n", "\n", "\n", "18->19\n", "\n", "\n", "\n", "\n", "\n", "20\n", "<id>\n", "\n", "\n", "\n", "18->20\n", "\n", "\n", "\n", "\n", "\n", "22\n", "> (62)\n", "\n", "\n", "\n", "18->22\n", "\n", "\n", "\n", "\n", "\n", "21\n", "html\n", "\n", "\n", "\n", "20->21\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "0\n", "<start>\n", "\n", "\n", "\n", "1\n", "<xml-tree>\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "\n", "\n", "\n", "2\n", "<xml-open-tag>\n", "\n", "\n", "\n", "1->2\n", "\n", "\n", "\n", "\n", "\n", "7\n", "<xml-tree>\n", "\n", "\n", "\n", "1->7\n", "\n", "\n", "\n", "\n", "\n", "22\n", "<xml-close-tag>\n", "\n", "\n", "\n", "1->22\n", "\n", "\n", "\n", "\n", "\n", "3\n", "< (60)\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "\n", "\n", "\n", "4\n", "<id>\n", "\n", "\n", "\n", "2->4\n", "\n", "\n", "\n", "\n", "\n", "6\n", "> (62)\n", "\n", "\n", "\n", "2->6\n", "\n", "\n", "\n", "\n", "\n", "5\n", "html\n", "\n", "\n", "\n", "4->5\n", "\n", "\n", "\n", "\n", "\n", "8\n", "<xml-tree>\n", "\n", "\n", "\n", "7->8\n", "\n", "\n", "\n", "\n", "\n", "11\n", "<xml-tree>\n", "\n", "\n", "\n", "7->11\n", "\n", "\n", "\n", "\n", "\n", "9\n", "<text>\n", "\n", "\n", "\n", "8->9\n", "\n", "\n", "\n", "\n", "\n", "10\n", "T (84)\n", "\n", "\n", "\n", "9->10\n", "\n", "\n", "\n", "\n", "\n", "12\n", "<xml-tree>\n", "\n", "\n", "\n", "11->12\n", "\n", "\n", "\n", "\n", "\n", "19\n", "<xml-tree>\n", "\n", "\n", "\n", "11->19\n", "\n", "\n", "\n", "\n", "\n", "13\n", "<xml-tree>\n", "\n", "\n", "\n", "12->13\n", "\n", "\n", "\n", "\n", "\n", "16\n", "<xml-tree>\n", "\n", "\n", "\n", "12->16\n", "\n", "\n", "\n", "\n", "\n", "14\n", "<text>\n", "\n", "\n", "\n", "13->14\n", "\n", "\n", "\n", "\n", "\n", "15\n", "e (101)\n", "\n", "\n", "\n", "14->15\n", "\n", "\n", "\n", "\n", "\n", "17\n", "<text>\n", "\n", "\n", "\n", "16->17\n", "\n", "\n", "\n", "\n", "\n", "18\n", "x (120)\n", "\n", "\n", "\n", "17->18\n", "\n", "\n", "\n", "\n", "\n", "20\n", "<text>\n", "\n", "\n", "\n", "19->20\n", "\n", "\n", "\n", "\n", "\n", "21\n", "t (116)\n", "\n", "\n", "\n", "20->21\n", "\n", "\n", "\n", "\n", "\n", "23\n", "</\n", "\n", "\n", "\n", "22->23\n", "\n", "\n", "\n", "\n", "\n", "24\n", "<id>\n", "\n", "\n", "\n", "22->24\n", "\n", "\n", "\n", "\n", "\n", "26\n", "> (62)\n", "\n", "\n", "\n", "22->26\n", "\n", "\n", "\n", "\n", "\n", "25\n", "html\n", "\n", "\n", "\n", "24->25\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "0\n", "<start>\n", "\n", "\n", "\n", "1\n", "<xml-tree>\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "\n", "\n", "\n", "2\n", "<xml-open-tag>\n", "\n", "\n", "\n", "1->2\n", "\n", "\n", "\n", "\n", "\n", "7\n", "<xml-tree>\n", "\n", "\n", "\n", "1->7\n", "\n", "\n", "\n", "\n", "\n", "22\n", "<xml-close-tag>\n", "\n", "\n", "\n", "1->22\n", "\n", "\n", "\n", "\n", "\n", "3\n", "< (60)\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "\n", "\n", "\n", "4\n", "<id>\n", "\n", "\n", "\n", "2->4\n", "\n", "\n", "\n", "\n", "\n", "6\n", "> (62)\n", "\n", "\n", "\n", "2->6\n", "\n", "\n", "\n", "\n", "\n", "5\n", "html\n", "\n", "\n", "\n", "4->5\n", "\n", "\n", "\n", "\n", "\n", "8\n", "<xml-tree>\n", "\n", "\n", "\n", "7->8\n", "\n", "\n", "\n", "\n", "\n", "11\n", "<xml-tree>\n", "\n", "\n", "\n", "7->11\n", "\n", "\n", "\n", "\n", "\n", "9\n", "<text>\n", "\n", "\n", "\n", "8->9\n", "\n", "\n", "\n", "\n", "\n", "10\n", "T (84)\n", "\n", "\n", "\n", "9->10\n", "\n", "\n", "\n", "\n", "\n", "12\n", "<xml-tree>\n", "\n", "\n", "\n", "11->12\n", "\n", "\n", "\n", "\n", "\n", "15\n", "<xml-tree>\n", "\n", "\n", "\n", "11->15\n", "\n", "\n", "\n", "\n", "\n", "13\n", "<text>\n", "\n", "\n", "\n", "12->13\n", "\n", "\n", "\n", "\n", "\n", "14\n", "e (101)\n", "\n", "\n", "\n", "13->14\n", "\n", "\n", "\n", "\n", "\n", "16\n", "<xml-tree>\n", "\n", "\n", "\n", "15->16\n", "\n", "\n", "\n", "\n", "\n", "19\n", "<xml-tree>\n", "\n", "\n", "\n", "15->19\n", "\n", "\n", "\n", "\n", "\n", "17\n", "<text>\n", "\n", "\n", "\n", "16->17\n", "\n", "\n", "\n", "\n", "\n", "18\n", "x (120)\n", "\n", "\n", "\n", "17->18\n", "\n", "\n", "\n", "\n", "\n", "20\n", "<text>\n", "\n", "\n", "\n", "19->20\n", "\n", "\n", "\n", "\n", "\n", "21\n", "t (116)\n", "\n", "\n", "\n", "20->21\n", "\n", "\n", "\n", "\n", "\n", "23\n", "</\n", "\n", "\n", "\n", "22->23\n", "\n", "\n", "\n", "\n", "\n", "24\n", "<id>\n", "\n", "\n", "\n", "22->24\n", "\n", "\n", "\n", "\n", "\n", "26\n", "> (62)\n", "\n", "\n", "\n", "22->26\n", "\n", "\n", "\n", "\n", "\n", "25\n", "html\n", "\n", "\n", "\n", "24->25\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "0\n", "<start>\n", "\n", "\n", "\n", "1\n", "<xml-tree>\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "\n", "\n", "\n", "2\n", "<xml-open-tag>\n", "\n", "\n", "\n", "1->2\n", "\n", "\n", "\n", "\n", "\n", "7\n", "<xml-tree>\n", "\n", "\n", "\n", "1->7\n", "\n", "\n", "\n", "\n", "\n", "18\n", "<xml-close-tag>\n", "\n", "\n", "\n", "1->18\n", "\n", "\n", "\n", "\n", "\n", "3\n", "< (60)\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "\n", "\n", "\n", "4\n", "<id>\n", "\n", "\n", "\n", "2->4\n", "\n", "\n", "\n", "\n", "\n", "6\n", "> (62)\n", "\n", "\n", "\n", "2->6\n", "\n", "\n", "\n", "\n", "\n", "5\n", "html\n", "\n", "\n", "\n", "4->5\n", "\n", "\n", "\n", "\n", "\n", "8\n", "<xml-tree>\n", "\n", "\n", "\n", "7->8\n", "\n", "\n", "\n", "\n", "\n", "11\n", "<xml-tree>\n", "\n", "\n", "\n", "7->11\n", "\n", "\n", "\n", "\n", "\n", "9\n", "<text>\n", "\n", "\n", "\n", "8->9\n", "\n", "\n", "\n", "\n", "\n", "10\n", "Te\n", "\n", "\n", "\n", "9->10\n", "\n", "\n", "\n", "\n", "\n", "12\n", "<xml-tree>\n", "\n", "\n", "\n", "11->12\n", "\n", "\n", "\n", "\n", "\n", "15\n", "<xml-tree>\n", "\n", "\n", "\n", "11->15\n", "\n", "\n", "\n", "\n", "\n", "13\n", "<text>\n", "\n", "\n", "\n", "12->13\n", "\n", "\n", "\n", "\n", "\n", "14\n", "x (120)\n", "\n", "\n", "\n", "13->14\n", "\n", "\n", "\n", "\n", "\n", "16\n", "<text>\n", "\n", "\n", "\n", "15->16\n", "\n", "\n", "\n", "\n", "\n", "17\n", "t (116)\n", "\n", "\n", "\n", "16->17\n", "\n", "\n", "\n", "\n", "\n", "19\n", "</\n", "\n", "\n", "\n", "18->19\n", "\n", "\n", "\n", "\n", "\n", "20\n", "<id>\n", "\n", "\n", "\n", "18->20\n", "\n", "\n", "\n", "\n", "\n", "22\n", "> (62)\n", "\n", "\n", "\n", "18->22\n", "\n", "\n", "\n", "\n", "\n", "21\n", "html\n", "\n", "\n", "\n", "20->21\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "0\n", "<start>\n", "\n", "\n", "\n", "1\n", "<xml-tree>\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "\n", "\n", "\n", "2\n", "<xml-open-tag>\n", "\n", "\n", "\n", "1->2\n", "\n", "\n", "\n", "\n", "\n", "7\n", "<xml-tree>\n", "\n", "\n", "\n", "1->7\n", "\n", "\n", "\n", "\n", "\n", "22\n", "<xml-close-tag>\n", "\n", "\n", "\n", "1->22\n", "\n", "\n", "\n", "\n", "\n", "3\n", "< (60)\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "\n", "\n", "\n", "4\n", "<id>\n", "\n", "\n", "\n", "2->4\n", "\n", "\n", "\n", "\n", "\n", "6\n", "> (62)\n", "\n", "\n", "\n", "2->6\n", "\n", "\n", "\n", "\n", "\n", "5\n", "html\n", "\n", "\n", "\n", "4->5\n", "\n", "\n", "\n", "\n", "\n", "8\n", "<xml-tree>\n", "\n", "\n", "\n", "7->8\n", "\n", "\n", "\n", "\n", "\n", "15\n", "<xml-tree>\n", "\n", "\n", "\n", "7->15\n", "\n", "\n", "\n", "\n", "\n", "9\n", "<xml-tree>\n", "\n", "\n", "\n", "8->9\n", "\n", "\n", "\n", "\n", "\n", "12\n", "<xml-tree>\n", "\n", "\n", "\n", "8->12\n", "\n", "\n", "\n", "\n", "\n", "10\n", "<text>\n", "\n", "\n", "\n", "9->10\n", "\n", "\n", "\n", "\n", "\n", "11\n", "T (84)\n", "\n", "\n", "\n", "10->11\n", "\n", "\n", "\n", "\n", "\n", "13\n", "<text>\n", "\n", "\n", "\n", "12->13\n", "\n", "\n", "\n", "\n", "\n", "14\n", "e (101)\n", "\n", "\n", "\n", "13->14\n", "\n", "\n", "\n", "\n", "\n", "16\n", "<xml-tree>\n", "\n", "\n", "\n", "15->16\n", "\n", "\n", "\n", "\n", "\n", "19\n", "<xml-tree>\n", "\n", "\n", "\n", "15->19\n", "\n", "\n", "\n", "\n", "\n", "17\n", "<text>\n", "\n", "\n", "\n", "16->17\n", "\n", "\n", "\n", "\n", "\n", "18\n", "x (120)\n", "\n", "\n", "\n", "17->18\n", "\n", "\n", "\n", "\n", "\n", "20\n", "<text>\n", "\n", "\n", "\n", "19->20\n", "\n", "\n", "\n", "\n", "\n", "21\n", "t (116)\n", "\n", "\n", "\n", "20->21\n", "\n", "\n", "\n", "\n", "\n", "23\n", "</\n", "\n", "\n", "\n", "22->23\n", "\n", "\n", "\n", "\n", "\n", "24\n", "<id>\n", "\n", "\n", "\n", "22->24\n", "\n", "\n", "\n", "\n", "\n", "26\n", "> (62)\n", "\n", "\n", "\n", "22->26\n", "\n", "\n", "\n", "\n", "\n", "25\n", "html\n", "\n", "\n", "\n", "24->25\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "parser = EarleyParser(XML_GRAMMAR, tokens=XML_TOKENS)\n", "\n", "for tree in parser.parse(\"Text\"):\n", " display(display_tree(tree))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "As we can see, the input starts with an opening tag, contains some text, and ends with a closing tag. Excellent. This is a structure that we can work with." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Building the Fragment Pool\n", "We are now ready to implement our first input-structure-aware mutator. Let's initialize the mutator with the dictionary `fragments` representing the empty fragment pool. It contains a key for each symbol in the grammar (and the empty set as value)." ] }, { "cell_type": "code", "execution_count": 29, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:57.866096Z", "iopub.status.busy": "2025-10-26T13:27:57.865973Z", "iopub.status.idle": "2025-10-26T13:27:57.868221Z", "shell.execute_reply": "2025-10-26T13:27:57.867997Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "class FragmentMutator(Mutator):\n", " \"\"\"Mutate inputs with input fragments from a pool\"\"\"\n", "\n", " def __init__(self, parser: EarleyParser) -> None:\n", " \"\"\"Initialize empty fragment pool and add parser\"\"\"\n", " self.parser = parser\n", " self.fragments: Dict[str, List[DerivationTree]] = \\\n", " {k: [] for k in self.parser.cgrammar}\n", " super().__init__()" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "The `FragmentMutator` adds fragments recursively. A *fragment* is a subtree in the parse tree and consists of the symbol of the current node and child nodes (i.e., descendant fragments). We can exclude fragments starting with symbols that are tokens, terminals, or not part of the grammar." ] }, { "cell_type": "code", "execution_count": 30, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:57.869591Z", "iopub.status.busy": "2025-10-26T13:27:57.869498Z", "iopub.status.idle": "2025-10-26T13:27:57.871091Z", "shell.execute_reply": "2025-10-26T13:27:57.870754Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from Parser import terminals" ] }, { "cell_type": "code", "execution_count": 31, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:57.872446Z", "iopub.status.busy": "2025-10-26T13:27:57.872364Z", "iopub.status.idle": "2025-10-26T13:27:57.874723Z", "shell.execute_reply": "2025-10-26T13:27:57.874495Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class FragmentMutator(FragmentMutator):\n", " def add_fragment(self, fragment: DerivationTree) -> None:\n", " \"\"\"Recursively adds fragments to the fragment pool\"\"\"\n", " (symbol, children) = fragment\n", " if not self.is_excluded(symbol):\n", " self.fragments[symbol].append(fragment)\n", " assert children is not None\n", " for subfragment in children:\n", " self.add_fragment(subfragment)\n", "\n", " def is_excluded(self, symbol: str) -> bool:\n", " \"\"\"Returns true if a fragment starting with a specific\n", " symbol and all its decendents can be excluded\"\"\"\n", " return (symbol not in self.parser.grammar() or\n", " symbol in self.parser.tokens or\n", " symbol in terminals(self.parser.grammar()))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Parsing can take a long time, particularly if there is too much ambiguity during the parsing. In order to maintain the efficiency of mutational fuzzing, we will limit the parsing time to 200ms." ] }, { "cell_type": "code", "execution_count": 32, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:57.876139Z", "iopub.status.busy": "2025-10-26T13:27:57.876055Z", "iopub.status.idle": "2025-10-26T13:27:57.877535Z", "shell.execute_reply": "2025-10-26T13:27:57.877319Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from Timeout import Timeout" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "The function `add_to_fragment_pool()` parses a seed (no longer than 200ms) and adds all its fragments to the fragment pool. If the parsing of the `seed` was successful, the attribute `seed.has_structure` is set to `True`. Otherwise, it is set to `False`." ] }, { "cell_type": "code", "execution_count": 33, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:57.878806Z", "iopub.status.busy": "2025-10-26T13:27:57.878735Z", "iopub.status.idle": "2025-10-26T13:27:57.880500Z", "shell.execute_reply": "2025-10-26T13:27:57.880241Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "class SeedWithStructure(Seed):\n", " \"\"\"Seeds augmented with structure info\"\"\"\n", "\n", " def __init__(self, data: str) -> None:\n", " super().__init__(data)\n", " self.has_structure = False\n", " self.structure: DerivationTree = (\"\", [])" ] }, { "cell_type": "code", "execution_count": 34, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:57.881816Z", "iopub.status.busy": "2025-10-26T13:27:57.881733Z", "iopub.status.idle": "2025-10-26T13:27:57.883703Z", "shell.execute_reply": "2025-10-26T13:27:57.883448Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class FragmentMutator(FragmentMutator):\n", " def add_to_fragment_pool(self, seed: SeedWithStructure) -> None:\n", " \"\"\"Adds all fragments of a seed to the fragment pool\"\"\"\n", " try: # only allow quick parsing of 200ms max\n", " with Timeout(0.2):\n", " seed.structure = next(self.parser.parse(seed.data))\n", " self.add_fragment(seed.structure)\n", " seed.has_structure = True\n", " except (SyntaxError, TimeoutError):\n", " seed.has_structure = False" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Let's see how `FragmentMutator` fills the fragment pool for a simple HTML seed input. We initialize mutator with the `EarleyParser` which itself is initialized with our `XML_GRAMMAR`." ] }, { "cell_type": "code", "execution_count": 35, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:57.885024Z", "iopub.status.busy": "2025-10-26T13:27:57.884946Z", "iopub.status.idle": "2025-10-26T13:27:57.886392Z", "shell.execute_reply": "2025-10-26T13:27:57.886177Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from GrammarFuzzer import tree_to_string" ] }, { "cell_type": "code", "execution_count": 36, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:57.887729Z", "iopub.status.busy": "2025-10-26T13:27:57.887611Z", "iopub.status.idle": "2025-10-26T13:27:57.919013Z", "shell.execute_reply": "2025-10-26T13:27:57.918715Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "|-HelloWorld
\n", "\n", "|-HelloWorld
\n", "|-HelloWorld
\n", "|-Hello\n", "|-Hello\n", "|-Hello\n", "|-World
\n", "|-World
\n", "|-World\n", "|-
\n", "\n", "|-\n", "|-\n", "|-\n", "|-<body>\n", "<xml-openclose-tag>\n", "|-<br/>\n", "<xml-close-tag>\n", "|-\n", "|-\n", "|-\n", "|-\n", "\n", "\n", "\n", "\n", "\n" ] } ], "source": [ "valid_seed = SeedWithStructure(\n", " \"HelloWorld
\")\n", "fragment_mutator = FragmentMutator(EarleyParser(XML_GRAMMAR, tokens=XML_TOKENS))\n", "fragment_mutator.add_to_fragment_pool(valid_seed)\n", "\n", "for key in fragment_mutator.fragments:\n", " print(key)\n", " for f in fragment_mutator.fragments[key]:\n", " print(\"|-%s\" % tree_to_string(f))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "For many symbols in the grammar, we have collected a number of fragments. There are several open and closing tags and several interesting fragments starting with the `xml-tree` symbol.\n", "\n", "***Summary***. For each interesting symbol in the grammar, the `FragmentMutator` has a set of fragments. These fragments are extracted by first parsing the inputs to be mutated." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Fragment-Based Mutation\n", "\n", "We can use the fragments in the fragment pool to generate new inputs. Every seed that is being mutated is disassembled into fragments, and memoized – i.e., disassembled only the first time around." ] }, { "cell_type": "code", "execution_count": 37, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:57.920574Z", "iopub.status.busy": "2025-10-26T13:27:57.920447Z", "iopub.status.idle": "2025-10-26T13:27:57.922513Z", "shell.execute_reply": "2025-10-26T13:27:57.922279Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class FragmentMutator(FragmentMutator):\n", " def __init__(self, parser: EarleyParser) -> None:\n", " \"\"\"Initialize mutators\"\"\"\n", " super().__init__(parser)\n", " self.seen_seeds: List[SeedWithStructure] = []\n", "\n", " def mutate(self, seed: SeedWithStructure) -> SeedWithStructure:\n", " \"\"\"Implement structure-aware mutation. Memoize seeds.\"\"\"\n", " if seed not in self.seen_seeds:\n", " self.seen_seeds.append(seed)\n", " self.add_to_fragment_pool(seed)\n", "\n", " return super().mutate(seed)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Our first structural mutation operator is `swap_fragments()`, which choses a random fragment in the given seed and substitutes it with a random fragment from the pool. We make sure that both fragments start with the same symbol. For instance, we may swap a closing tag in the seed HTML by another closing tag from the fragment pool.\n", "\n", "In order to choose a random fragment, the mutator counts all fragments (`n_count`) below the root fragment associated with the start-symbol." ] }, { "cell_type": "code", "execution_count": 38, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:57.924101Z", "iopub.status.busy": "2025-10-26T13:27:57.924000Z", "iopub.status.idle": "2025-10-26T13:27:57.925965Z", "shell.execute_reply": "2025-10-26T13:27:57.925685Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class FragmentMutator(FragmentMutator):\n", " def count_nodes(self, fragment: DerivationTree) -> int:\n", " \"\"\"Returns the number of nodes in the fragment\"\"\"\n", " symbol, children = fragment\n", " if self.is_excluded(symbol):\n", " return 0\n", "\n", " assert children is not None\n", " return 1 + sum(map(self.count_nodes, children))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "In order to swap the chosen fragment – identified using the \"global\" variable `self.to_swap` – the seed's parse tree is traversed recursively." ] }, { "cell_type": "code", "execution_count": 39, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:57.927513Z", "iopub.status.busy": "2025-10-26T13:27:57.927399Z", "iopub.status.idle": "2025-10-26T13:27:57.929611Z", "shell.execute_reply": "2025-10-26T13:27:57.929377Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class FragmentMutator(FragmentMutator):\n", " def recursive_swap(self, fragment: DerivationTree) -> DerivationTree:\n", " \"\"\"Recursively finds the fragment to swap.\"\"\"\n", " symbol, children = fragment\n", " if self.is_excluded(symbol):\n", " return symbol, children\n", "\n", " self.to_swap -= 1\n", " if self.to_swap == 0: \n", " return random.choice(list(self.fragments[symbol]))\n", "\n", " assert children is not None\n", " return symbol, list(map(self.recursive_swap, children))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Our structural mutator chooses a random number between 2 (i.e., excluding the `start` symbol) and the total number of fragments (`n_count`) and uses the recursive swapping to generate the new fragment. The new fragment is serialized as string and returned as new seed." ] }, { "cell_type": "code", "execution_count": 40, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:57.931352Z", "iopub.status.busy": "2025-10-26T13:27:57.931124Z", "iopub.status.idle": "2025-10-26T13:27:57.933780Z", "shell.execute_reply": "2025-10-26T13:27:57.933505Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class FragmentMutator(FragmentMutator):\n", " def __init__(self, parser: EarleyParser) -> None: # type: ignore\n", " super().__init__(parser)\n", " self.mutators = [self.swap_fragment] # type: ignore\n", "\n", " def swap_fragment(self, seed: SeedWithStructure) -> SeedWithStructure:\n", " \"\"\"Substitutes a random fragment with another with the same symbol\"\"\"\n", " if seed.has_structure: # type: ignore\n", " n_nodes = self.count_nodes(seed.structure)\n", " self.to_swap = random.randint(2, n_nodes)\n", " new_structure = self.recursive_swap(seed.structure)\n", "\n", " new_seed = SeedWithStructure(tree_to_string(new_structure))\n", " new_seed.has_structure = True\n", " new_seed.structure = new_structure\n", " return new_seed\n", "\n", " return seed" ] }, { "cell_type": "code", "execution_count": 41, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:57.935561Z", "iopub.status.busy": "2025-10-26T13:27:57.935444Z", "iopub.status.idle": "2025-10-26T13:27:57.967917Z", "shell.execute_reply": "2025-10-26T13:27:57.967598Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "HelloWorld
\n" ] }, { "data": { "text/plain": [ "World
" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "valid_seed = SeedWithStructure(\n", " \"HelloWorld
\")\n", "lf_mutator = FragmentMutator(parser)\n", "print(valid_seed)\n", "lf_mutator.mutate(valid_seed)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "As we can see, one fragment has been substituted by another. \n", "\n", "We can use a similar recursive traversal to *remove* a random fragment." ] }, { "cell_type": "code", "execution_count": 42, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:57.969458Z", "iopub.status.busy": "2025-10-26T13:27:57.969352Z", "iopub.status.idle": "2025-10-26T13:27:57.971333Z", "shell.execute_reply": "2025-10-26T13:27:57.971096Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class FragmentMutator(FragmentMutator):\n", " def recursive_delete(self, fragment: DerivationTree) -> DerivationTree:\n", " \"\"\"Recursively finds the fragment to delete\"\"\"\n", " symbol, children = fragment\n", " if self.is_excluded(symbol):\n", " return symbol, children\n", "\n", " self.to_delete -= 1\n", " if self.to_delete == 0:\n", " return symbol, []\n", "\n", " assert children is not None\n", " return symbol, list(map(self.recursive_delete, children))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "We should also define the corresponding structural deletion operator, as well." ] }, { "cell_type": "code", "execution_count": 43, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:57.972841Z", "iopub.status.busy": "2025-10-26T13:27:57.972750Z", "iopub.status.idle": "2025-10-26T13:27:57.974847Z", "shell.execute_reply": "2025-10-26T13:27:57.974628Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class FragmentMutator(FragmentMutator):\n", " def __init__(self, parser): # type: ignore\n", " super().__init__(parser)\n", " self.mutators.append(self.delete_fragment)\n", "\n", " def delete_fragment(self, seed: SeedWithStructure) -> SeedWithStructure:\n", " \"\"\"Delete a random fragment\"\"\"\n", " if seed.has_structure:\n", " n_nodes = self.count_nodes(seed.structure)\n", " self.to_delete = random.randint(2, n_nodes)\n", " new_structure = self.recursive_delete(seed.structure)\n", "\n", " new_seed = SeedWithStructure(tree_to_string(new_structure))\n", " new_seed.has_structure = True\n", " new_seed.structure = new_structure\n", " # do not return an empty new_seed\n", " if not new_seed.data:\n", " return seed\n", " else:\n", " return new_seed\n", "\n", " return seed" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "***Summary***. We now have all ingredients for structure-aware fuzzing. Our mutator disassembles all seeds into fragments, which are then added to the fragment pool. Our mutator swaps random fragments in a given seed with fragments of the same type. And our mutator deletes random fragments in a given seed. This allows maintaining a high degree of validity for the generated inputs w.r.t. the given grammar.\n", "\n", "***Try it***. Try adding other structural mutation operators. How would an *add-operator* know the position in a given seed file, where it is okay to add a fragment starting with a certain symbol?" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Fragment-Based Fuzzing\n", "\n", "We can now define an input-structure aware fuzzer as pioneered in LangFuzz. To implement LangFuzz, we modify our [blackbox mutational fuzzer](GreyboxFuzzer.ipynb#Blackbox-Mutation-based-Fuzzer) to stack up to four structural mutations." ] }, { "cell_type": "code", "execution_count": 44, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:57.976443Z", "iopub.status.busy": "2025-10-26T13:27:57.976349Z", "iopub.status.idle": "2025-10-26T13:27:57.978121Z", "shell.execute_reply": "2025-10-26T13:27:57.977892Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class LangFuzzer(AdvancedMutationFuzzer):\n", " \"\"\"Blackbox fuzzer mutating input fragments. Roughly based on `LangFuzz`.\"\"\"\n", "\n", " def create_candidate(self) -> Seed: # type: ignore\n", " \"\"\"Returns an input generated by fuzzing a seed in the population\"\"\"\n", " candidate = self.schedule.choose(self.population)\n", " trials = random.randint(1, 4)\n", " for i in range(trials):\n", " candidate = self.mutator.mutate(candidate)\n", "\n", " return candidate" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Okay, let's take our first input-structure aware fuzzer for a spin. Being careful, we set n=300 for now." ] }, { "cell_type": "code", "execution_count": 45, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:27:57.979502Z", "iopub.status.busy": "2025-10-26T13:27:57.979397Z", "iopub.status.idle": "2025-10-26T13:28:06.796186Z", "shell.execute_reply": "2025-10-26T13:28:06.795821Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "'It took LangFuzzer 8.81 seconds to generate and execute 300 inputs.'" ] }, "execution_count": 45, "metadata": {}, "output_type": "execute_result" } ], "source": [ "n = 300\n", "runner = FunctionCoverageRunner(my_parser)\n", "mutator = FragmentMutator(EarleyParser(XML_GRAMMAR, tokens=XML_TOKENS))\n", "schedule = PowerSchedule()\n", "\n", "lang_fuzzer = LangFuzzer([valid_seed.data], mutator, schedule)\n", "\n", "start = time.time()\n", "lang_fuzzer.runs(runner, trials=n)\n", "end = time.time()\n", "\n", "\"It took LangFuzzer %0.2f seconds to generate and execute %d inputs.\" % (end - start, n)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "We observe that structural mutation is *sooo very slow*. This is despite our time budget of 200ms for parsing. In contrast, our blackbox fuzzer alone can generate about 10k inputs per second!" ] }, { "cell_type": "code", "execution_count": 46, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:28:06.797857Z", "iopub.status.busy": "2025-10-26T13:28:06.797738Z", "iopub.status.idle": "2025-10-26T13:28:06.882141Z", "shell.execute_reply": "2025-10-26T13:28:06.881796Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "'It took a blackbox fuzzer 0.08 seconds to generate and execute 300 inputs.'" ] }, "execution_count": 46, "metadata": {}, "output_type": "execute_result" } ], "source": [ "runner = FunctionCoverageRunner(my_parser)\n", "mutator = Mutator()\n", "schedule = PowerSchedule()\n", "\n", "blackFuzzer = AdvancedMutationFuzzer([valid_seed.data], mutator, schedule)\n", "\n", "start = time.time()\n", "blackFuzzer.runs(runner, trials=n)\n", "end = time.time()\n", "\n", "\"It took a blackbox fuzzer %0.2f seconds to generate and execute %d inputs.\" % (end - start, n)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Indeed, our blackbox fuzzer is done in the blink of an eye.\n", "\n", "***Try it***. We can deal with this overhead using [deferred parsing](https://arxiv.org/abs/1811.09447). Instead of wasting time in the beginning of the fuzzing campaign when a byte-level mutator would make efficient progress, deferred parsing suggests to invest time in structural mutation only later in the fuzzing campaign when it becomes viable." ] }, { "cell_type": "code", "execution_count": 47, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:28:06.883972Z", "iopub.status.busy": "2025-10-26T13:28:06.883845Z", "iopub.status.idle": "2025-10-26T13:28:06.886186Z", "shell.execute_reply": "2025-10-26T13:28:06.885907Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "'During this fuzzing campaign, the blackbox fuzzer covered 101 statements.'" ] }, "execution_count": 47, "metadata": {}, "output_type": "execute_result" } ], "source": [ "blackbox_coverage = len(runner.coverage())\n", "\"During this fuzzing campaign, the blackbox fuzzer covered %d statements.\" % blackbox_coverage" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Let's print some stats for our fuzzing campaigns. Since we'll need to print stats more often later, we should wrap this into a function. In order to measure coverage, we import the [population_coverage](Coverage.ipynb#Coverage-of-Basic-Fuzzing) function. It takes a set of inputs and a Python function, executes the inputs on that function and collects coverage information. Specifically, it returns a tuple `(all_coverage, cumulative_coverage)` where `all_coverage` is the set of statements covered by all inputs, and `cumulative_coverage` is the number of statements covered as the number of executed inputs increases. We are just interested in the latter to plot coverage over time." ] }, { "cell_type": "code", "execution_count": 48, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:28:06.887631Z", "iopub.status.busy": "2025-10-26T13:28:06.887495Z", "iopub.status.idle": "2025-10-26T13:28:06.889390Z", "shell.execute_reply": "2025-10-26T13:28:06.889001Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from Coverage import population_coverage" ] }, { "cell_type": "code", "execution_count": 49, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:28:06.890885Z", "iopub.status.busy": "2025-10-26T13:28:06.890758Z", "iopub.status.idle": "2025-10-26T13:28:06.893376Z", "shell.execute_reply": "2025-10-26T13:28:06.893064Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def print_stats(fuzzer, parser: Parser) -> None:\n", " coverage, _ = population_coverage(fuzzer.inputs, my_parser)\n", "\n", " has_structure = 0\n", " for seed in fuzzer.inputs:\n", " # reuse memoized information\n", " if hasattr(seed, \"has_structure\"):\n", " if seed.has_structure: \n", " has_structure += 1\n", " else:\n", " if isinstance(seed, str):\n", " seed = Seed(seed)\n", " try:\n", " with Timeout(0.2):\n", " next(parser.parse(seed.data)) # type: ignore\n", " has_structure += 1\n", " except (SyntaxError, TimeoutError):\n", " pass\n", "\n", " print(\"From the %d generated inputs, %d (%0.2f%%) can be parsed.\\n\"\n", " \"In total, %d statements are covered.\" % (\n", " len(fuzzer.inputs),\n", " has_structure,\n", " 100 * has_structure / len(fuzzer.inputs),\n", " len(coverage)))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "For LangFuzzer, let's see how many of the inputs generated by LangFuzz are valid (i.e., parsable) and how many statements were covered." ] }, { "cell_type": "code", "execution_count": 50, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:28:06.895015Z", "iopub.status.busy": "2025-10-26T13:28:06.894865Z", "iopub.status.idle": "2025-10-26T13:28:06.969715Z", "shell.execute_reply": "2025-10-26T13:28:06.969381Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "From the 300 generated inputs, 171 (57.00%) can be parsed.\n", "In total, 93 statements are covered.\n" ] } ], "source": [ "print_stats(lang_fuzzer, EarleyParser(XML_GRAMMAR, tokens=XML_TOKENS))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "What are the stats for the mutational fuzzer that uses only byte-level mutation (and no grammars)?" ] }, { "cell_type": "code", "execution_count": 51, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:28:06.971427Z", "iopub.status.busy": "2025-10-26T13:28:06.971289Z", "iopub.status.idle": "2025-10-26T13:28:08.734624Z", "shell.execute_reply": "2025-10-26T13:28:08.734327Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "From the 300 generated inputs, 30 (10.00%) can be parsed.\n", "In total, 165 statements are covered.\n" ] } ], "source": [ "print_stats(blackFuzzer, EarleyParser(XML_GRAMMAR, tokens=XML_TOKENS))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "***Summary***. Our fragment-level blackbox fuzzer (LangFuzzer) generates *more valid inputs* but achieves *less code coverage* than a fuzzer with our byte-level fuzzer. So, there is some value in generating inputs that do not stick to the provided grammar. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Integration with Greybox Fuzzing\n", "\n", "In the following we integrate fragment-level blackbox fuzzing (LangFuzz-style) with [byte-level greybox fuzzing](GreyboxFuzzer.ipynb#Greybox-Mutation-based-Fuzzer) (AFL-style). The additional coverage-feedback might allow us to increase code coverage more quickly.\n", "\n", "A [greybox fuzzer](GreyboxFuzzer.ipynb#Greybox-Mutation-based-Fuzzer) adds to the seed population all generated inputs which increase code coverage. Inputs are generated in two stages, stacking up to four structural mutations and up to 32 byte-level mutations." ] }, { "cell_type": "code", "execution_count": 52, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:28:08.736267Z", "iopub.status.busy": "2025-10-26T13:28:08.736150Z", "iopub.status.idle": "2025-10-26T13:28:08.739361Z", "shell.execute_reply": "2025-10-26T13:28:08.739070Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class GreyboxGrammarFuzzer(GreyboxFuzzer):\n", " \"\"\"Greybox fuzzer using grammars.\"\"\"\n", "\n", " def __init__(self, seeds: List[str],\n", " byte_mutator: Mutator, tree_mutator: FragmentMutator,\n", " schedule: PowerSchedule) -> None:\n", " \"\"\"Constructor.\n", " `seeds` - set of inputs to mutate.\n", " `byte_mutator` - a byte-level mutator.\n", " `tree_mutator` = a tree-level mutator.\n", " `schedule` - a power schedule.\n", " \"\"\"\n", " super().__init__(seeds, byte_mutator, schedule)\n", " self.tree_mutator = tree_mutator\n", "\n", " def create_candidate(self) -> str:\n", " \"\"\"Returns an input generated by structural mutation \n", " of a seed in the population\"\"\"\n", " seed = cast(SeedWithStructure, self.schedule.choose(self.population))\n", "\n", " # Structural mutation\n", " trials = random.randint(0, 4)\n", " for i in range(trials):\n", " seed = self.tree_mutator.mutate(seed)\n", "\n", " # Byte-level mutation\n", " candidate = seed.data\n", " if trials == 0 or not seed.has_structure or random.randint(0, 1) == 1:\n", " dumb_trials = min(len(seed.data), 1 << random.randint(1, 5))\n", " for i in range(dumb_trials):\n", " candidate = self.mutator.mutate(candidate)\n", "\n", " return candidate" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Let's run our integrated fuzzer with the [standard byte-level mutator](GreyboxFuzzer.ipynb#Mutator-and-Seed) and our [fragment-based structural mutator](#Fragment-based-Mutation) that was introduced above." ] }, { "cell_type": "code", "execution_count": 53, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:28:08.740799Z", "iopub.status.busy": "2025-10-26T13:28:08.740705Z", "iopub.status.idle": "2025-10-26T13:28:09.546158Z", "shell.execute_reply": "2025-10-26T13:28:09.545860Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "'It took the greybox grammar fuzzer 0.80 seconds to generate and execute 300 inputs.'" ] }, "execution_count": 53, "metadata": {}, "output_type": "execute_result" } ], "source": [ "runner = FunctionCoverageRunner(my_parser)\n", "byte_mutator = Mutator()\n", "tree_mutator = FragmentMutator(EarleyParser(XML_GRAMMAR, tokens=XML_TOKENS))\n", "schedule = PowerSchedule()\n", "\n", "gg_fuzzer = GreyboxGrammarFuzzer([valid_seed.data], byte_mutator, tree_mutator, schedule)\n", "\n", "start = time.time()\n", "gg_fuzzer.runs(runner, trials=n)\n", "end = time.time()\n", "\n", "\"It took the greybox grammar fuzzer %0.2f seconds to generate and execute %d inputs.\" % (end - start, n)" ] }, { "cell_type": "code", "execution_count": 54, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:28:09.547525Z", "iopub.status.busy": "2025-10-26T13:28:09.547419Z", "iopub.status.idle": "2025-10-26T13:28:10.259020Z", "shell.execute_reply": "2025-10-26T13:28:10.258636Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "From the 300 generated inputs, 3 (1.00%) can be parsed.\n", "In total, 169 statements are covered.\n" ] } ], "source": [ "print_stats(gg_fuzzer, EarleyParser(XML_GRAMMAR, tokens=XML_TOKENS))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "***Summary***. Our structural greybox fuzzer \n", "* runs faster than the fragment-based LangFuzzer,\n", "* achieves more coverage than both the fragment-based LangFuzzer and the vanilla blackbox mutational fuzzer, and\n", "* generates fewer valid inputs than even the vanilla blackbox mutational fuzzer." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" }, "toc-hr-collapsed": false }, "source": [ "## Fuzzing with Input Regions\n", "\n", "In the previous section, we have seen that most inputs that are added as seeds are *invalid* w.r.t. our given grammar. Yet, in order to apply our fragment-based mutators, we need it to parse the seed successfully. Otherwise, the entire fragment-based approach becomes useless. The question arises: *How can we derive structure from (invalid) seeds that cannot be parsed successfully?*\n", "\n", "To this end, we introduce the idea of _region-based mutation_, first explored with the [AFLSmart](https://github.com/aflsmart/aflsmart) structural greybox fuzzer \\cite{Pham2018aflsmart}. AFLSmart implements byte-level, fragment-based, and region-based mutation as well as validity-based power schedules. We define *region-based mutators*, where a *region* is a consecutive sequence of bytes in the input that can be associated with a symbol in the grammar." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "The basic idea of fuzzing with input regions is shown in the following diagram. After _parsing_ an input (into a derivation tree), we can identify _regions_ associated with specific subtrees of the derivation tree. These regions can then be deleted or swapped.\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Such regions can also be determined even if the input is incomplete or invalid, allowing for robust parsing." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Determining Symbol Regions\n", "\n", "How can we obtain regions for a given input? The function `chart_parse()` of the [Earley parser](Parser.ipynb#The-Parsing-Algorithm) produces a _parse table_ for a string. For each letter in the string, this table gives the potential symbol and a *region* of neighboring letters that might belong to the same symbol." ] }, { "cell_type": "code", "execution_count": 55, "metadata": { "code_folding": [], "execution": { "iopub.execute_input": "2025-10-26T13:28:10.261059Z", "iopub.status.busy": "2025-10-26T13:28:10.260935Z", "iopub.status.idle": "2025-10-26T13:28:10.268263Z", "shell.execute_reply": "2025-10-26T13:28:10.267784Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "None chart[0]\n", "\n", "---\n", "< chart[1]\n", "\n", "---\n", "h chart[2]\n", ":= h |(1,2)\n", ":= |(1,2)\n", "---\n", "t chart[3]\n", ":= t |(2,3)\n", ":= |(1,3)\n", "---\n", "m chart[4]\n", ":= m |(3,4)\n", ":= |(1,4)\n", "---\n", "l chart[5]\n", ":= l |(4,5)\n", ":= |(1,5)\n", "---\n", "> chart[6]\n", ":= < > |(0,6)\n", "---\n", "< chart[7]\n", "\n", "---\n", "b chart[8]\n", ":= b |(7,8)\n", ":= |(7,8)\n", "---\n", "o chart[9]\n", ":= o |(8,9)\n", ":= |(7,9)\n", "---\n", "d chart[10]\n", ":= d |(9,10)\n", ":= |(7,10)\n", "---\n", "y chart[11]\n", ":= y |(10,11)\n", ":= |(7,11)\n", "---\n", "> chart[12]\n", ":= < > |(6,12)\n", "---\n", "< chart[13]\n", "\n", "---\n", "i chart[14]\n", ":= i |(13,14)\n", ":= |(13,14)\n", "---\n", "> chart[15]\n", ":= < > |(12,15)\n", "---\n", "W chart[16]\n", ":= W |(15,16)\n", ":= |(15,16)\n", ":= |(15,16)\n", "---\n", "o chart[17]\n", ":= o |(16,17)\n", ":= |(15,17)\n", ":= |(16,17)\n", ":= |(15,17)\n", ":= |(16,17)\n", ":= |(15,17)\n", "---\n", "r chart[18]\n", ":= r |(17,18)\n", ":= |(15,18)\n", ":= |(16,18)\n", ":= |(17,18)\n", ":= |(15,18)\n", ":= |(16,18)\n", ":= |(17,18)\n", ":= |(15,18)\n", ":= |(16,18)\n", "---\n", "l chart[19]\n", ":= l |(18,19)\n", ":= |(15,19)\n", ":= |(16,19)\n", ":= |(17,19)\n", ":= |(18,19)\n", ":= |(15,19)\n", ":= |(16,19)\n", ":= |(17,19)\n", ":= |(18,19)\n", ":= |(15,19)\n", ":= |(16,19)\n", ":= |(17,19)\n", "---\n", "d chart[20]\n", ":= d |(19,20)\n", ":= |(15,20)\n", ":= |(16,20)\n", ":= |(17,20)\n", ":= |(18,20)\n", ":= |(19,20)\n", ":= |(15,20)\n", ":= |(16,20)\n", ":= |(17,20)\n", ":= |(18,20)\n", ":= |(19,20)\n", ":= |(15,20)\n", ":= |(16,20)\n", ":= |(17,20)\n", ":= |(18,20)\n", "---\n", "< chart[21]\n", "\n", "---\n", "/ chart[22]\n", "\n", "---\n", "i chart[23]\n", ":= i |(22,23)\n", ":= |(22,23)\n", "---\n", "> chart[24]\n", ":= < / > |(20,24)\n", ":= |(12,24)\n", "---\n", "< chart[25]\n", "\n", "---\n", "b chart[26]\n", ":= b |(25,26)\n", ":= |(25,26)\n", "---\n", "r chart[27]\n", ":= r |(26,27)\n", ":= |(25,27)\n", "---\n", "/ chart[28]\n", "\n", "---\n", "> chart[29]\n", ":= < / > |(24,29)\n", ":= |(24,29)\n", ":= |(12,29)\n", "---\n", "> chart[30]\n", "\n", "---\n", "/ chart[31]\n", "\n", "---\n", "b chart[32]\n", "\n", "---\n", "o chart[33]\n", "\n", "---\n", "d chart[34]\n", "\n", "---\n", "y chart[35]\n", "\n", "---\n", "> chart[36]\n", "\n", "---\n", "< chart[37]\n", "\n", "---\n", "/ chart[38]\n", "\n", "---\n", "h chart[39]\n", "\n", "---\n", "t chart[40]\n", "\n", "---\n", "m chart[41]\n", "\n", "---\n", "l chart[42]\n", "\n", "---\n", "> chart[43]\n", "\n", "---\n" ] } ], "source": [ "invalid_seed = Seed(\"World
>/body>\")\n", "parser = EarleyParser(XML_GRAMMAR, tokens=XML_TOKENS)\n", "table = parser.chart_parse(invalid_seed.data, parser.start_symbol())\n", "for column in table:\n", " print(column)\n", " print(\"---\")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "The number of columns in this table that are associated with potential symbols correspond to the number of letters that could be parsed successfully. In other words, we can use this table to compute the longest parsable substring." ] }, { "cell_type": "code", "execution_count": 56, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:28:10.270142Z", "iopub.status.busy": "2025-10-26T13:28:10.270024Z", "iopub.status.idle": "2025-10-26T13:28:10.273970Z", "shell.execute_reply": "2025-10-26T13:28:10.273237Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "'World
>/body>'\n" ] }, { "data": { "text/plain": [ "'World
'" ] }, "execution_count": 56, "metadata": {}, "output_type": "execute_result" } ], "source": [ "cols = [col for col in table if col.states]\n", "parsable = invalid_seed.data[:len(cols)-1]\n", "\n", "print(\"'%s'\" % invalid_seed)\n", "parsable" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "From this, we can compute the *degree of validity* for an input." ] }, { "cell_type": "code", "execution_count": 57, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:28:10.276745Z", "iopub.status.busy": "2025-10-26T13:28:10.276603Z", "iopub.status.idle": "2025-10-26T13:28:10.279706Z", "shell.execute_reply": "2025-10-26T13:28:10.278836Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "'67.4% of the string can be parsed successfully.'" ] }, "execution_count": 57, "metadata": {}, "output_type": "execute_result" } ], "source": [ "validity = 100 * len(parsable) / len(invalid_seed.data)\n", "\n", "\"%0.1f%% of the string can be parsed successfully.\" % validity" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "***Summary***. Unlike input fragments, input regions can be derived even if the parser fails to generate the entire parse tree." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" }, "tags": [] }, "source": [ "### Region-Based Mutation\n", "\n", "To fuzz invalid seeds, the region-based mutator associates symbols from the grammar with regions (i.e., indexed substrings) in the seed. The [overridden](#Building-the-Fragment-Pool) method `add_to_fragment_pool()` first tries to mine the fragments from the seed. If this fails, the region mutator uses [Earley parser](Parser.ipynb#The-Parsing-Algorithm) to derive the parse table. For each column (i.e., letter), it extracts the symbols and corresponding regions. This allows the mutator to store the set of regions with each symbol." ] }, { "cell_type": "code", "execution_count": 58, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:28:10.282044Z", "iopub.status.busy": "2025-10-26T13:28:10.281935Z", "iopub.status.idle": "2025-10-26T13:28:10.284908Z", "shell.execute_reply": "2025-10-26T13:28:10.284023Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class SeedWithRegions(SeedWithStructure):\n", " \"\"\"Seeds augmented with structure info\"\"\"\n", "\n", " def __init__(self, data: str) -> None:\n", " super().__init__(data)\n", " self.has_regions = False\n", " self.regions: Dict[str, Set] = {}" ] }, { "cell_type": "code", "execution_count": 59, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:28:10.288504Z", "iopub.status.busy": "2025-10-26T13:28:10.288316Z", "iopub.status.idle": "2025-10-26T13:28:10.291517Z", "shell.execute_reply": "2025-10-26T13:28:10.291190Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class RegionMutator(FragmentMutator):\n", " def add_to_fragment_pool(self, seed: SeedWithRegions) -> None: # type: ignore\n", " \"\"\"Mark fragments and regions in a seed file\"\"\"\n", " super().add_to_fragment_pool(seed)\n", " if not seed.has_structure:\n", " try:\n", " with Timeout(0.2):\n", " seed.regions = {k: set() for k in self.parser.cgrammar}\n", " for column in self.parser.chart_parse(seed.data,\n", " self.parser.start_symbol()):\n", " for state in column.states:\n", " if (not self.is_excluded(state.name) and\n", " state.e_col.index - state.s_col.index > 1 and\n", " state.finished()):\n", " seed.regions[state.name].add((state.s_col.index,\n", " state.e_col.index))\n", " seed.has_regions = True\n", " except TimeoutError:\n", " seed.has_regions = False\n", " else:\n", " seed.has_regions = False" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "This is how these regions look like for our invalid seed. A region consists of a start and end index in the seed string." ] }, { "cell_type": "code", "execution_count": 60, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:28:10.293584Z", "iopub.status.busy": "2025-10-26T13:28:10.293472Z", "iopub.status.idle": "2025-10-26T13:28:10.371775Z", "shell.execute_reply": "2025-10-26T13:28:10.371529Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "\n", "|-(16,20) : orld\n", "|-(12,24) : World\n", "|-(17,20) : rld\n", "|-(18,20) : ld\n", "|-(16,19) : orl\n", "|-(15,17) : Wo\n", "|-(12,29) : World
\n", "|-(17,19) : rl\n", "|-(15,20) : World\n", "|-(24,29) :
\n", "|-(15,19) : Worl\n", "|-(16,18) : or\n", "|-(15,18) : Wor\n", "\n", "|-(6,12) : \n", "|-(12,15) : \n", "|-(0,6) : \n", "\n", "|-(24,29) :
\n", "\n", "|-(20,24) : \n", "\n", "\n", "\n", "\n", "\n" ] } ], "source": [ "invalid_seed = SeedWithRegions(\"World
>/body>\")\n", "mutator = RegionMutator(parser)\n", "mutator.add_to_fragment_pool(invalid_seed)\n", "for symbol in invalid_seed.regions: # type: ignore\n", " print(symbol)\n", " for (s, e) in invalid_seed.regions[symbol]: # type: ignore\n", " print(\"|-(%d,%d) : %s\" % (s, e, invalid_seed.data[s:e]))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Now that we know which regions in the seed belong to which symbol, we can define region-based swap and delete operators." ] }, { "cell_type": "code", "execution_count": 61, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:28:10.373500Z", "iopub.status.busy": "2025-10-26T13:28:10.373389Z", "iopub.status.idle": "2025-10-26T13:28:10.376619Z", "shell.execute_reply": "2025-10-26T13:28:10.376235Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class RegionMutator(RegionMutator):\n", " def swap_fragment(self, seed: SeedWithRegions) -> SeedWithRegions: # type: ignore\n", " \"\"\"Chooses a random region and swaps it with a fragment\n", " that starts with the same symbol\"\"\"\n", " if not seed.has_structure and seed.has_regions:\n", " regions = [r for r in seed.regions\n", " if (len(seed.regions[r]) > 0 and\n", " len(self.fragments[r]) > 0)]\n", " if len(regions) == 0:\n", " return seed\n", "\n", " key = random.choice(list(regions))\n", " s, e = random.choice(list(seed.regions[key]))\n", " swap_structure = random.choice(self.fragments[key])\n", " swap_string = tree_to_string(swap_structure)\n", " new_seed = SeedWithRegions(seed.data[:s] + swap_string + seed.data[e:])\n", " new_seed.has_structure = False\n", " new_seed.has_regions = False\n", " return new_seed\n", " else:\n", " return super().swap_fragment(seed) # type: ignore" ] }, { "cell_type": "code", "execution_count": 62, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:28:10.378324Z", "iopub.status.busy": "2025-10-26T13:28:10.378216Z", "iopub.status.idle": "2025-10-26T13:28:10.381231Z", "shell.execute_reply": "2025-10-26T13:28:10.380888Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class RegionMutator(RegionMutator):\n", " def delete_fragment(self, seed: SeedWithRegions) -> SeedWithRegions: # type: ignore\n", " \"\"\"Deletes a random region\"\"\"\n", " if not seed.has_structure and seed.has_regions:\n", " regions = [r for r in seed.regions\n", " if len(seed.regions[r]) > 0]\n", " if len(regions) == 0:\n", " return seed\n", "\n", " key = random.choice(list(regions))\n", " s, e = (0, 0)\n", " while (e - s < 2):\n", " s, e = random.choice(list(seed.regions[key]))\n", "\n", " new_seed = SeedWithRegions(seed.data[:s] + seed.data[e:])\n", " new_seed.has_structure = False\n", " new_seed.has_regions = False\n", " return new_seed\n", " else:\n", " return super().delete_fragment(seed) # type: ignore" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Let's try our new region-based mutator. We add a simple, valid seed to the fragment pool and attempt to mutate the invalid seed." ] }, { "cell_type": "code", "execution_count": 63, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:28:10.384705Z", "iopub.status.busy": "2025-10-26T13:28:10.384340Z", "iopub.status.idle": "2025-10-26T13:28:10.518854Z", "shell.execute_reply": "2025-10-26T13:28:10.518389Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "World
>/body>\n" ] }, { "data": { "text/plain": [ "World
>/body>" ] }, "execution_count": 63, "metadata": {}, "output_type": "execute_result" } ], "source": [ "simple_seed = SeedWithRegions(\"Text\")\n", "mutator = RegionMutator(parser)\n", "mutator.add_to_fragment_pool(simple_seed)\n", "\n", "print(invalid_seed)\n", "mutator.mutate(invalid_seed)" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "***Summary***. We can use the Earley parser to generate a parse table and assign regions in the input to symbols in the grammar. Our region mutators can substitute these regions with fragments from the fragment pool that start with the same symbol, or delete these regions entirely.\n", "\n", "***Try it***. Implement a region pool (similar to the fragment pool) and a `swap_region()` mutator.\n", "You can execute your own code by opening this chapter as Jupyter notebook." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Integration with Greybox Fuzzing\n", "\n", "Let's try our shiny new region mutator by integrating it with our [structure-aware greybox fuzzer](#Integration-with-Greybox-Fuzzing)." ] }, { "cell_type": "code", "execution_count": 64, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:28:10.520730Z", "iopub.status.busy": "2025-10-26T13:28:10.520609Z", "iopub.status.idle": "2025-10-26T13:28:28.812217Z", "shell.execute_reply": "2025-10-26T13:28:28.811938Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "'\\nIt took the structural greybox fuzzer with region mutator\\n18.29 seconds to generate and execute 300 inputs.\\n'" ] }, "execution_count": 64, "metadata": {}, "output_type": "execute_result" } ], "source": [ "runner = FunctionCoverageRunner(my_parser)\n", "byte_mutator = Mutator()\n", "tree_mutator = RegionMutator(EarleyParser(XML_GRAMMAR, tokens=XML_TOKENS))\n", "schedule = PowerSchedule()\n", "\n", "regionFuzzer = GreyboxGrammarFuzzer([valid_seed.data], byte_mutator, tree_mutator, schedule)\n", "\n", "start = time.time()\n", "regionFuzzer.runs(runner, trials = n)\n", "end = time.time()\n", "\n", "\"\"\"\n", "It took the structural greybox fuzzer with region mutator\n", "%0.2f seconds to generate and execute %d inputs.\n", "\"\"\" % (end - start, n)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "We can see that the structural greybox fuzzer with region-based mutator is slower than the [fragment-based mutator alone](#Fragment-based-Fuzzing). This is because region-based structural mutation is applicable for *all seeds*. In contrast, fragment-based mutators were applicable only for tiny number of parsable seeds. Otherwise, only (very efficient) byte-level mutators were applied.\n", "\n", "Let's also print the average degree of validity for the seeds in the population." ] }, { "cell_type": "code", "execution_count": 65, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:28:28.813634Z", "iopub.status.busy": "2025-10-26T13:28:28.813550Z", "iopub.status.idle": "2025-10-26T13:28:28.815773Z", "shell.execute_reply": "2025-10-26T13:28:28.815552Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def print_more_stats(fuzzer: GreyboxGrammarFuzzer, parser: EarleyParser):\n", " print_stats(fuzzer, parser)\n", " validity = 0.0\n", " total = 0\n", " for seed in fuzzer.population:\n", " if not seed.data: continue\n", " table = parser.chart_parse(seed.data, parser.start_symbol())\n", " cols = [col for col in table if col.states]\n", " parsable = invalid_seed.data[:len(cols)-1]\n", " validity += len(parsable) / len(seed.data)\n", " total += 1\n", "\n", " print(\"On average, %0.1f%% of a seed in the population can be successfully parsed.\" % (100 * validity / total))" ] }, { "cell_type": "code", "execution_count": 66, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:28:28.817104Z", "iopub.status.busy": "2025-10-26T13:28:28.817000Z", "iopub.status.idle": "2025-10-26T13:28:29.590824Z", "shell.execute_reply": "2025-10-26T13:28:29.590459Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "From the 300 generated inputs, 2 (0.67%) can be parsed.\n", "In total, 177 statements are covered.\n", "On average, 10.0% of a seed in the population can be successfully parsed.\n" ] } ], "source": [ "print_more_stats(regionFuzzer, parser)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "***Summary***. Compared to fragment-based mutation, a greybox fuzzer with region-based mutation achieves *higher coverage* but generates a *smaller number of valid inputs*. The higher coverage is explained by leveraging at least *some* structure for seeds that cannot be parsed successfully.\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Focusing on Valid Seeds\n", "\n", "In the previous section, we have a problem: The low (degree of) validity. To address this problem, a _validity-based power schedule_ assigns more [energy](GreyboxFuzzer.ipynb#Power-Schedules) to seeds that have a higher degree of validity. In other words, the fuzzer _spends more time fuzzing seeds that are more valid_." ] }, { "cell_type": "code", "execution_count": 67, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:28:29.592547Z", "iopub.status.busy": "2025-10-26T13:28:29.592428Z", "iopub.status.idle": "2025-10-26T13:28:29.594035Z", "shell.execute_reply": "2025-10-26T13:28:29.593792Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import math" ] }, { "cell_type": "code", "execution_count": 68, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:28:29.595409Z", "iopub.status.busy": "2025-10-26T13:28:29.595322Z", "iopub.status.idle": "2025-10-26T13:28:29.598309Z", "shell.execute_reply": "2025-10-26T13:28:29.598054Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class AFLSmartSchedule(PowerSchedule):\n", " def __init__(self, parser: EarleyParser, exponent: float = 1.0):\n", " self.parser = parser\n", " self.exponent = exponent\n", "\n", " def parsable(self, seed: Seed) -> str:\n", " \"\"\"Returns the substring that is parsable\"\"\"\n", " table = self.parser.chart_parse(seed.data, self.parser.start_symbol())\n", " cols = [col for col in table if col.states]\n", " return seed.data[:len(cols)-1]\n", "\n", " def degree_of_validity(self, seed: Seed) -> float:\n", " \"\"\"Returns the proportion of a seed that is parsable\"\"\"\n", " if not hasattr(seed, 'validity'):\n", " seed.validity = (len(self.parsable(seed)) / len(seed.data) # type: ignore\n", " if len(seed.data) > 0 else 0)\n", " return seed.validity # type: ignore\n", "\n", " def assignEnergy(self, population: Sequence[Seed]):\n", " \"\"\"Assign exponential energy proportional to degree of validity\"\"\"\n", " for seed in population:\n", " seed.energy = ((self.degree_of_validity(seed) / math.log(len(seed.data))) ** self.exponent\n", " if len(seed.data) > 1 else 0)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Let's play with the degree of validity by passing in a valid seed ..." ] }, { "cell_type": "code", "execution_count": 69, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:28:29.599723Z", "iopub.status.busy": "2025-10-26T13:28:29.599624Z", "iopub.status.idle": "2025-10-26T13:28:29.606110Z", "shell.execute_reply": "2025-10-26T13:28:29.605811Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Entire seed: Text\n", " Parsable: Text\n" ] }, { "data": { "text/plain": [ "'Degree of validity: 100.00%'" ] }, "execution_count": 69, "metadata": {}, "output_type": "execute_result" } ], "source": [ "smart_schedule = AFLSmartSchedule(parser)\n", "print(\"%11s: %s\" % (\"Entire seed\", simple_seed))\n", "print(\"%11s: %s\" % (\"Parsable\", smart_schedule.parsable(simple_seed)))\n", "\n", "\"Degree of validity: %0.2f%%\" % (100 * smart_schedule.degree_of_validity(simple_seed))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "... and an invalid seed." ] }, { "cell_type": "code", "execution_count": 70, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:28:29.607480Z", "iopub.status.busy": "2025-10-26T13:28:29.607387Z", "iopub.status.idle": "2025-10-26T13:28:29.617376Z", "shell.execute_reply": "2025-10-26T13:28:29.617124Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Entire seed: World
>/body>\n", " Parsable: World
\n" ] }, { "data": { "text/plain": [ "'Degree of validity: 67.44%'" ] }, "execution_count": 70, "metadata": {}, "output_type": "execute_result" } ], "source": [ "print(\"%11s: %s\" % (\"Entire seed\", invalid_seed))\n", "print(\"%11s: %s\" % (\"Parsable\", smart_schedule.parsable(invalid_seed)))\n", "\n", "\"Degree of validity: %0.2f%%\" % (100 * smart_schedule.degree_of_validity(invalid_seed))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Excellent. We can compute the degree of validity as the proportion of the string that can be parsed. \n", "\n", "Let's plug the validity-based power schedule into the structure-aware greybox fuzzer." ] }, { "cell_type": "code", "execution_count": 71, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:28:29.618782Z", "iopub.status.busy": "2025-10-26T13:28:29.618703Z", "iopub.status.idle": "2025-10-26T13:29:01.145733Z", "shell.execute_reply": "2025-10-26T13:29:01.145422Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "'It took AFLSmart 31.52 seconds to generate and execute 300 inputs.'" ] }, "execution_count": 71, "metadata": {}, "output_type": "execute_result" } ], "source": [ "runner = FunctionCoverageRunner(my_parser)\n", "byte_mutator = Mutator()\n", "tree_mutator = RegionMutator(EarleyParser(XML_GRAMMAR, tokens=XML_TOKENS))\n", "schedule = AFLSmartSchedule(parser)\n", "\n", "aflsmart_fuzzer = GreyboxGrammarFuzzer([valid_seed.data], byte_mutator, \n", " tree_mutator, schedule)\n", "\n", "start = time.time()\n", "aflsmart_fuzzer.runs(runner, trials=n)\n", "end = time.time()\n", "\n", "\"It took AFLSmart %0.2f seconds to generate and execute %d inputs.\" % (end - start, n)" ] }, { "cell_type": "code", "execution_count": 72, "metadata": { "execution": { "iopub.execute_input": "2025-10-26T13:29:01.147579Z", "iopub.status.busy": "2025-10-26T13:29:01.147449Z", "iopub.status.idle": "2025-10-26T13:29:02.358958Z", "shell.execute_reply": "2025-10-26T13:29:02.358608Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "From the 300 generated inputs, 3 (1.00%) can be parsed.\n", "In total, 173 statements are covered.\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "On average, 19.7% of a seed in the population can be successfully parsed.\n" ] } ], "source": [ "print_more_stats(aflsmart_fuzzer, parser)" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "***Summary***. Indeed, by spending more time fuzzing seeds with a higher degree of validity, we also generate inputs with a higher degree of validity. More inputs are entirely valid w.r.t. the given grammar.\n", "\n", "***Read up***. Learn more about region-based fuzzing, deferred parsing, and validity-based schedules in the original AFLSmart paper: \"[Smart Greybox Fuzzing](https://arxiv.org/abs/1811.09447)\" by Pham and co-authors. Download and improve AFLSmart: [https://github.com/aflsmart/aflsmart](https://github.com/aflsmart/aflsmart)." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Mining Seeds\n", "\n", "By now, it should have become clear that the _choice of seeds_ can very much influence the success of fuzzing. One aspect is _variability_ – our seeds should cover as many different features as possible in order to increase coverage. Another aspect, however, is the _likelihood of a seed to induce errors_ – that is, if a seed was involved in causing a failure before, then a mutation of this very seed may be likely to induce failures again. This is because fixes for past failures typically are successful in letting the concrete failure no longer occur, but sometimes may fail to capture all conditions under which a failure may occur. Hence, even if the original failure is fixed, the likelihood of an error in the _surroundings_ of the original failure-inducing input is still higher. It thus pays off to use as seeds _inputs that are known to have caused failures before_.\n", "\n", "To put things in context, Holler's _LangFuzz_ fuzzer used as seeds JavaScript inputs from CVE reports. These were published as failure-inducing inputs at a time when the error already had been fixed; thus they could do no harm anymore. Yet, by using such inputs as seeds, LangFuzz would create plenty of mutations and recombinations of all their features, many of which would (and do) find errors again and again." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": true, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Lessons Learned\n", "\n", "* A **dictionary** is useful to inject important keywords into the generated inputs.\n", "\n", "* **Fragment-based mutation** first disassembles seeds into fragments, and reassembles these fragments to generate new inputs. A *fragment* is a subtree in the seed's parse tree. However, fragment-based mutation requires that the seeds can be parsed successfully, which may not be true for seeds discovered by a coverage-based greybox fuzzer.\n", "\n", "* **Region-based mutation** marks regions in the input as belonging to a certain symbol in the grammar. For instance, it may identify a substring '' as closing tag. These regions can then be deleted or substituted by fragments or regions belonging to the same symbol. Unlike fragment-based mutation, region-based mutation is applicable to *all* seeds - even those that can be parsed only partially. However, the degree of validity is still quite low for the generated inputs.\n", "\n", "* A **validity-based power schedule** invests more energy into seeds with a higher degree of validity. The inputs that are generated also have a higher degree of validity.\n", "\n", "* **Mining seeds** from repositories of previous failure-inducing inputs results in input fragments associated with past failures, raising the likelihood to find more failures in the vicinity." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" }, "tags": [] }, "source": [ "## Background\n", "\n", "This chapter builds on the following two works:\n", "\n", "* The _LangFuzz_ fuzzer \\cite{Holler2012} is an efficient (and effective!) grammar-based fuzzer for (mostly) JavaScript. It uses the grammar for parsing seeds and recombining their inputs with generated parts and found 2,600 bugs in JavaScript interpreters to date.\n", "\n", "* Smart greybox fuzzing ([AFLSmart](https://github.com/aflsmart/aflsmart)) brings together coverage-based fuzzing and grammar-based (structural) fuzzing, as described in \\cite{Pham2018aflsmart}. The resulting AFLSMART tool has discovered 42 zero-day vulnerabilities in widely-used, well-tested tools and libraries; so far 17 CVEs were assigned." ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" }, "tags": [] }, "source": [ "Recent fuzzing work also brings together grammar-based fuzzing and coverage.\n", "\n", "* _Superion_ \\cite{Wang2019superion} is equivalent to our section \"Integration with Greybox Fuzzing\", as above – that is, a combination of LangFuzz and Greybox Fuzzing, but no AFL-style byte-level mutation. Superion can improve the code coverage (i.e., 16.7% and 8.8% in line and function coverage) and bug-finding capability over AFL and jsfunfuzz. According to the authors, they found 30 new bugs, among which they discovered 21 new vulnerabilities with 16 CVEs assigned and 3.2K USD bug bounty rewards received.\n", "\n", "* _Nautilus_ \\cite{Aschermann2019nautilus} also combines grammar-based fuzzing with coverage feedback. It maintains the parse tree for all seeds and generated inputs. To allow AFL-style byte-level mutations, it \"collapses\" subtrees back to byte-level representations. This has the advantage of not having to re-parse generated seeds; however, over time, Nautilus degenerates to structure-unaware greybox fuzzing because it does not re-parse collapsed subtrees to reconstitute input structure for later seeds where most of the parse tree is collapsed. Nautilus identified bugs in mruby, PHP, ChakraCore, and in Lua; reporting these bugs was awarded with a sum of 2600 USD and 6 CVEs were assigned.\n", "\n", "* [FormatFuzzer](https://uds-se.github.io/FormatFuzzer/) is a framework for high-efficiency, high-quality generation and parsing of binary inputs. It takes a binary template that describes the format of a binary input and generates an executable that produces and parses the given binary format. From a binary template for GIF, for instance, FormatFuzzer produces a GIF generator - also known as GIF fuzzer. Generators produced by FormatFuzzer are highly efficient, producing thousands of valid test inputs per second. FormatFuzzer operates in black-box settings, but can also integrate with AFL to produce valid inputs that also aim for maximum coverage." ] }, { "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 closes our discussion of syntactic fuzzing techniques.\n", "\n", "* In the [next chapter](Reducer.ipynb), we discuss how to _reduce failure-inducing inputs_ after a failure, keeping only those portions of the input that are necessary for reproducing the failure.\n", "* The [next part](04_Semantical_Fuzzing.ipynb) will go from syntactical to _semantical_ fuzzing, considering code semantics for targeted test generation." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": true, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Exercises\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" }, "solution2": "hidden", "solution2_first": true }, "source": [ "### Exercise 1: The Big Greybox Fuzzer Shoot-Out\n", "\n", "Use our implementations of greybox techniques and evaluate them on a benchmark. Which technique (and which sub-technique) has which impact and why? Also take into account the specific approaches of Superion \\cite{Wang2019superion} and Nautilus \\cite{Aschermann2019nautilus}, possibly even on the benchmarks used by these approaches." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "source": [ "**Solution.** To be added." ] } ], "metadata": { "ipub": { "bibliography": "fuzzingbook.bib", "toc": true }, "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.13.4" }, "toc": { "base_numbering": 1, "nav_menu": {}, "number_sections": true, "sideBar": true, "skip_h1_title": true, "title_cell": "", "title_sidebar": "Contents", "toc_cell": false, "toc_position": {}, "toc_section_display": true, "toc_window_display": true }, "toc-autonumbering": false, "varInspector": { "cols": { "lenName": 16, "lenType": 16, "lenVar": 40 }, "kernels_config": { "python": { "delete_cmd_postfix": "", "delete_cmd_prefix": "del ", "library": "var_list.py", "varRefreshCmd": "print(var_dic_list())" }, "r": { "delete_cmd_postfix": ") ", "delete_cmd_prefix": "rm(", "library": "var_list.r", "varRefreshCmd": "cat(var_dic_list()) " } }, "types_to_exclude": [ "module", "function", "builtin_function_or_method", "instance", "_Feature" ], "window_display": false }, "vscode": { "interpreter": { "hash": "4185989cf89c47c310c2629adcadd634093b57a2c49dffb5ae8d0d14fa302f2b" } } }, "nbformat": 4, "nbformat_minor": 4 }