<jupyter_start><jupyter_text>Evolutionary Grammar FuzzingIn this chapter, we introduce how to implement [search-based test generation](SearchBasedFuzzing.ipynb) on grammars, using _genetic improvement_ operators such as mutation and cross-over on derivation trees. **Prerequisites*** You should have read the [chapter on search-based test generation](SearchBasedFuzzer.ipynb).* You should have read the [chapter on recombining inputs](LangFuzzer.ipynb).<jupyter_code>import fuzzingbook_utils
import SearchBasedFuzzer
import LangFuzzer<jupyter_output><empty_output><jupyter_text>Grammar-Based MutationGeneral idea: Take a derivation tree and a matching grammar; apply a random mutation.<jupyter_code>from Grammars import EXPR_GRAMMAR
from GrammarFuzzer import display_tree
from Parser import EarleyParser
parser = EarleyParser(EXPR_GRAMMAR)
tree, *_ = parser.parse("1 + 2 * 3")
display_tree(tree)<jupyter_output><empty_output><jupyter_text>1. Pick any node in the tree2. Produce a new expansion.We have seen this for `LangFuzzer` already, right?How about we factor this out (from the Parser notebook), and have two notebook on mutational (and genetic fuzzing):1. `LangFuzzer` – a chapter on    * Mutating trees (randomly)    * Mutating trees from a given population (the LangFuzz approach)    * Tree recombination (and crossover)    2. `EvoGrammarFuzzer` – a chapter on    * Genetic improvement (using coverage only)    * Genetic improvement (using a fitness function from search-based fuzzing)<jupyter_code>def mutate_tree(tree, grammar):
    pass<jupyter_output><empty_output><jupyter_text>Grammar-Based Crossover  Lessons Learned* _Lesson one_* _Lesson two_* _Lesson three_  Next Steps_Link to subsequent chapters (notebooks) here, as in:_* [use _mutations_ on existing inputs to get more valid inputs](MutationFuzzer.ipynb)* [use _grammars_ (i.e., a specification of the input format) to get even more valid inputs](Grammars.ipynb)* [reduce _failing inputs_ for efficient debugging](Reducer.ipynb)  Background_Cite relevant works in the literature and put them into context, as in:_The idea of ensuring that each expansion in the grammar is used at least once goes back to Burkhardt \cite{Burkhardt1967}, to be later rediscovered by <NAME> \cite{Purdom1972}.  Exercises_Close the chapter with a few exercises such that people have things to do.  To make the solutions hidden (to be revealed by the user), have them start with_```markdown**Solution.**```_Your solution can then extend up to the next title (i.e., any markdown cell starting with ``).__Running `make metadata` will automatically add metadata to the cells such that the cells will be hidden by default, and can be uncovered by the user.  The button will be introduced above the solution._  Exercise 1: _Title__Text of the exercise_<jupyter_code># Some code that is part of the exercise
pass<jupyter_output><empty_output><jupyter_text>_Some more text for the exercise_ **Solution.** _Some text for the solution_<jupyter_code># Some code for the solution
2 + 2<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.06908971840209562, 'fraction_numerical': 0.005893909626719057, 'mean_word_length': 5.990846681922196, 'pattern_counts': {'":': 0, '<': 22, '<?xml version=': 0, '>': 22, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '21594', 'license': 'MIT', 'n_tokens_mistral': 921, 'n_tokens_neox': 866, 'n_words': 362, 'path': 'docs/beta/notebooks/EvoGrammarFuzzer.ipynb', 'repo_name': 'unibw-patch/fuzzingbook', 'size': '3059'}