GrammarCoverageFuzzer.py

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# "Grammar Coverage" - a chapter of "The Fuzzing Book"
# Web site: https://www.fuzzingbook.org/html/GrammarCoverageFuzzer.html
# Last change: 2024-04-27 15:44:44+02:00
#
# Copyright (c) 2021-2023 CISPA Helmholtz Center for Information Security
# Copyright (c) 2018-2020 Saarland University, authors, and contributors
#
# Permission is hereby granted, free of charge, to any person obtaining a
# copy of this software and associated documentation files (the
# "Software"), to deal in the Software without restriction, including
# without limitation the rights to use, copy, modify, merge, publish,
# distribute, sublicense, and/or sell copies of the Software, and to
# permit persons to whom the Software is furnished to do so, subject to
# the following conditions:
#
# The above copyright notice and this permission notice shall be included
# in all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
# OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
# IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
# CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
# TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
# SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

r'''
The Fuzzing Book - Grammar Coverage

This file can be _executed_ as a script, running all experiments:

    $ python GrammarCoverageFuzzer.py

or _imported_ as a package, providing classes, functions, and constants:

    >>> from fuzzingbook.GrammarCoverageFuzzer import <identifier>
    
but before you do so, _read_ it and _interact_ with it at:

    https://www.fuzzingbook.org/html/GrammarCoverageFuzzer.html

This chapter introduces `GrammarCoverageFuzzer`, an efficient grammar fuzzer extending `GrammarFuzzer` from the [chapter on efficient grammar fuzzing](GrammarFuzzer.ipynb).  It strives to _cover all expansions at least once,_ thus ensuring coverage of functionality.

In the following example, for instance, we use `GrammarCoverageFuzzer` to produce an expression. We see that the resulting expression covers all digits and all operators in a single expression.

>>> from Grammars import EXPR_GRAMMAR
>>> expr_fuzzer = GrammarCoverageFuzzer(EXPR_GRAMMAR)
>>> expr_fuzzer.fuzz()
'-(2 + 3) * 4.5 / 6 - 2.0 / +8 + 7 + 3'

After fuzzing, the `expansion_coverage()` method returns a mapping of grammar expansions covered.

>>> expr_fuzzer.expansion_coverage()
{' -> 0',
 ' -> 1',
 ' -> 2',
 ' -> 3',
 ' -> 4',
 ' -> 5',
 ' -> 6',
 ' -> 7',
 ' -> 8',
 ' -> 9',
 ' -> ',
 ' ->  + ',
 ' ->  - ',
 ' -> ()',
 ' -> +',
 ' -> -',
 ' -> ',
 ' -> .',
 ' -> ',
 ' -> ',
 ' -> ',
 ' -> ',
 ' ->  * ',
 ' ->  / '}

Subsequent calls to `fuzz()` will go for further coverage (i.e., covering the other area code digits, for example); a call to `reset()` clears the recorded coverage, starting anew.

Since such coverage in inputs also yields higher code coverage, `GrammarCoverageFuzzer` is a recommended extension to `GrammarFuzzer`.

For more details, source, and documentation, see
"The Fuzzing Book - Grammar Coverage"
at https://www.fuzzingbook.org/html/GrammarCoverageFuzzer.html
'''


# Allow to use 'from . import <module>' when run as script (cf. PEP 366)
if __name__ == '__main__' and __package__ is None:
    __package__ = 'fuzzingbook'


# Grammar Coverage
# ================

if __name__ == '__main__':
    print('# Grammar Coverage')



if __name__ == '__main__':
    from .bookutils import YouTubeVideo
    YouTubeVideo('GGb3e5p0HC8')

## Synopsis
## --------

if __name__ == '__main__':
    print('\n## Synopsis')



## Covering Grammar Elements
## -------------------------

if __name__ == '__main__':
    print('\n## Covering Grammar Elements')



if __name__ == '__main__':
    # We use the same fixed seed as the notebook to ensure consistency
    import random
    random.seed(2001)

from .bookutils import quiz

from .Fuzzer import Fuzzer

from typing import Dict, List, Set, Union, Optional

from .Grammars import EXPR_GRAMMAR, CGI_GRAMMAR, URL_GRAMMAR, START_SYMBOL
from .Grammars import is_valid_grammar, extend_grammar, Grammar

if __name__ == '__main__':
    EXPR_GRAMMAR["<factor>"]

if __name__ == '__main__':
    quiz("Which expansions of `EXPR_GRAMMAR` does the expression `1 + 2` cover?",
         [
             "`<start> -> <expr>`",
             "`<integer> -> <digit><integer>`",
             "`<integer> -> <digit>`",
             "`<factor> -> +<factor>`"
         ], [1, 3])

### Tracking Grammar Coverage

if __name__ == '__main__':
    print('\n### Tracking Grammar Coverage')



from .Grammars import Grammar, Expansion
from .GrammarFuzzer import GrammarFuzzer, all_terminals, nonterminals, \
    display_tree, DerivationTree

import random

class TrackingGrammarCoverageFuzzer(GrammarFuzzer):
    """Track grammar coverage during production"""

    def __init__(self, *args, **kwargs) -> None:
        # invoke superclass __init__(), passing all arguments
        super().__init__(*args, **kwargs)
        self.reset_coverage()

#### Keeping Track of Expansions

if __name__ == '__main__':
    print('\n#### Keeping Track of Expansions')



class TrackingGrammarCoverageFuzzer(TrackingGrammarCoverageFuzzer):
    def expansion_coverage(self) -> Set[str]:
        """Return the set of covered expansions as strings SYMBOL -> EXPANSION"""
        return self.covered_expansions

    def reset_coverage(self) -> None:
        """Clear coverage info tracked so far"""
        self.covered_expansions: Set[str] = set()

def expansion_key(symbol: str, 
                  expansion: Union[Expansion,
                                   DerivationTree, 
                                   List[DerivationTree]]) -> str:
    """Convert (symbol, `expansion`) into a key "SYMBOL -> EXPRESSION". 
      `expansion` can be an expansion string, a derivation tree,
         or a list of derivation trees."""

    if isinstance(expansion, tuple):
        # Expansion or single derivation tree
        expansion, _ = expansion

    if not isinstance(expansion, str):
        # Derivation tree
        children = expansion
        expansion = all_terminals((symbol, children))

    assert isinstance(expansion, str)

    return symbol + " -> " + expansion

if __name__ == '__main__':
    expansion_key(START_SYMBOL, EXPR_GRAMMAR[START_SYMBOL][0])

if __name__ == '__main__':
    children: List[DerivationTree] = [("<expr>", None), (" + ", []), ("<term>", None)]
    expansion_key("<expr>", children)

#### Computing Possible Expansions

if __name__ == '__main__':
    print('\n#### Computing Possible Expansions')



class TrackingGrammarCoverageFuzzer(TrackingGrammarCoverageFuzzer):
    def _max_expansion_coverage(self, symbol: str, 
                                max_depth: Union[int, float]) -> Set[str]:
        if max_depth <= 0:
            return set()

        self._symbols_seen.add(symbol)

        expansions = set()
        for expansion in self.grammar[symbol]:
            expansions.add(expansion_key(symbol, expansion))
            for nonterminal in nonterminals(expansion):
                if nonterminal not in self._symbols_seen:
                    expansions |= self._max_expansion_coverage(
                        nonterminal, max_depth - 1)

        return expansions

    def max_expansion_coverage(self, symbol: Optional[str] = None,
                               max_depth: Union[int, float] = float('inf')) \
            -> Set[str]:
        """Return set of all expansions in a grammar 
           starting with `symbol` (default: start symbol).
           If `max_depth` is given, expand only to that depth."""
        if symbol is None:
            symbol = self.start_symbol

        self._symbols_seen: Set[str] = set()
        cov = self._max_expansion_coverage(symbol, max_depth)

        if symbol == START_SYMBOL:
            assert len(self._symbols_seen) == len(self.grammar)

        return cov

if __name__ == '__main__':
    expr_fuzzer = TrackingGrammarCoverageFuzzer(EXPR_GRAMMAR)
    expr_fuzzer.max_expansion_coverage()

#### Tracking Expansions while Fuzzing

if __name__ == '__main__':
    print('\n#### Tracking Expansions while Fuzzing')



class TrackingGrammarCoverageFuzzer(TrackingGrammarCoverageFuzzer):
    def add_coverage(self, symbol: str,
                     new_child: Union[Expansion, List[DerivationTree]]) -> None:
        key = expansion_key(symbol, new_child)

        if self.log and key not in self.covered_expansions:
            print("Now covered:", key)
        self.covered_expansions.add(key)

    def choose_node_expansion(self, node: DerivationTree,
                              children_alternatives: 
                              List[List[DerivationTree]]) -> int:
        (symbol, children) = node
        index = super().choose_node_expansion(node, children_alternatives)
        self.add_coverage(symbol, children_alternatives[index])
        return index

class TrackingGrammarCoverageFuzzer(TrackingGrammarCoverageFuzzer):
    def missing_expansion_coverage(self) -> Set[str]:
        """Return expansions not covered yet"""
        return self.max_expansion_coverage() - self.expansion_coverage()

#### Putting Things Together

if __name__ == '__main__':
    print('\n#### Putting Things Together')



if __name__ == '__main__':
    digit_fuzzer = TrackingGrammarCoverageFuzzer(
        EXPR_GRAMMAR, start_symbol="<digit>", log=True)
    digit_fuzzer.fuzz()

if __name__ == '__main__':
    digit_fuzzer.fuzz()

if __name__ == '__main__':
    digit_fuzzer.fuzz()

if __name__ == '__main__':
    digit_fuzzer.expansion_coverage()

if __name__ == '__main__':
    digit_fuzzer.max_expansion_coverage()

if __name__ == '__main__':
    digit_fuzzer.missing_expansion_coverage()

def average_length_until_full_coverage(fuzzer: TrackingGrammarCoverageFuzzer) -> float:
    trials = 50

    sum = 0
    for trial in range(trials):
        # print(trial, end=" ")
        fuzzer.reset_coverage()
        while len(fuzzer.missing_expansion_coverage()) > 0:
            s = fuzzer.fuzz()
            sum += len(s)

    return sum / trials

if __name__ == '__main__':
    digit_fuzzer.log = False
    average_length_until_full_coverage(digit_fuzzer)

if __name__ == '__main__':
    expr_fuzzer = TrackingGrammarCoverageFuzzer(EXPR_GRAMMAR)
    average_length_until_full_coverage(expr_fuzzer)

### Covering Grammar Expansions

if __name__ == '__main__':
    print('\n### Covering Grammar Expansions')



class SimpleGrammarCoverageFuzzer(TrackingGrammarCoverageFuzzer):
    """When choosing expansions, prefer expansions not covered."""

    def choose_node_expansion(self,
                              node: DerivationTree,
                              children_alternatives: List[List[DerivationTree]]) -> int:
        """Return index of expansion in `children_alternatives` to be selected.
           Picks uncovered expansions, if any."""

        # Prefer uncovered expansions
        (symbol, children) = node
        uncovered_children = [c for (i, c) in enumerate(children_alternatives)
                              if expansion_key(symbol, c)
                              not in self.covered_expansions]
        index_map = [i for (i, c) in enumerate(children_alternatives)
                     if c in uncovered_children]

        if len(uncovered_children) == 0:
            # All expansions covered - use superclass method
            return self.choose_covered_node_expansion(node, children_alternatives)

        # Select from uncovered nodes
        index = self.choose_uncovered_node_expansion(node, uncovered_children)

        return index_map[index]

class SimpleGrammarCoverageFuzzer(SimpleGrammarCoverageFuzzer):
    def choose_uncovered_node_expansion(self,
                                        node: DerivationTree,
                                        children_alternatives: List[List[DerivationTree]]) \
            -> int:
        """Return index of expansion in _uncovered_ `children_alternatives`
           to be selected.
           To be overloaded in subclasses."""
        return TrackingGrammarCoverageFuzzer.choose_node_expansion(
            self, node, children_alternatives)

    def choose_covered_node_expansion(self,
                                      node: DerivationTree,
                                      children_alternatives: List[List[DerivationTree]]) \
            -> int:
        """Return index of expansion in _covered_ `children_alternatives`
           to be selected.
           To be overloaded in subclasses."""
        return TrackingGrammarCoverageFuzzer.choose_node_expansion(
            self, node, children_alternatives)

if __name__ == '__main__':
    f = SimpleGrammarCoverageFuzzer(EXPR_GRAMMAR, start_symbol="<digit>")
    f.fuzz()

if __name__ == '__main__':
    f.fuzz()

if __name__ == '__main__':
    f.fuzz()

if __name__ == '__main__':
    f.expansion_coverage()

if __name__ == '__main__':
    for i in range(7):
        print(f.fuzz(), end=" ")

if __name__ == '__main__':
    f.missing_expansion_coverage()

if __name__ == '__main__':
    f = SimpleGrammarCoverageFuzzer(EXPR_GRAMMAR)
    for i in range(10):
        print(f.fuzz())

if __name__ == '__main__':
    f.missing_expansion_coverage()

if __name__ == '__main__':
    average_length_until_full_coverage(SimpleGrammarCoverageFuzzer(EXPR_GRAMMAR))

## Deep Foresight
## --------------

if __name__ == '__main__':
    print('\n## Deep Foresight')



if __name__ == '__main__':
    CGI_GRAMMAR

if __name__ == '__main__':
    f = SimpleGrammarCoverageFuzzer(CGI_GRAMMAR)
    for i in range(10):
        print(f.fuzz())

if __name__ == '__main__':
    f.missing_expansion_coverage()

if __name__ == '__main__':
    CGI_GRAMMAR["<letter>"]

### Determining Maximum per-Symbol Coverage

if __name__ == '__main__':
    print('\n### Determining Maximum per-Symbol Coverage')



if __name__ == '__main__':
    f = SimpleGrammarCoverageFuzzer(EXPR_GRAMMAR)
    f.max_expansion_coverage('<integer>')

if __name__ == '__main__':
    quiz("How many productions would `f.max_expansion_coverage('<digit>')` return?",
         [
             "10",
             "11",
             "12",
             "13"
         ], "100 / 100")

if __name__ == '__main__':
    f.max_expansion_coverage('<digit>')

### Determining yet Uncovered Children

if __name__ == '__main__':
    print('\n### Determining yet Uncovered Children')



class GrammarCoverageFuzzer(SimpleGrammarCoverageFuzzer):
    """Produce from grammars, aiming for coverage of all expansions."""

    def new_child_coverage(self,
                           symbol: str,
                           children: List[DerivationTree],
                           max_depth: Union[int, float] = float('inf')) -> Set[str]:
        """Return new coverage that would be obtained 
           by expanding (`symbol`, `children`)"""

        new_cov = self._new_child_coverage(children, max_depth)
        new_cov.add(expansion_key(symbol, children))
        new_cov -= self.expansion_coverage()   # -= is set subtraction
        return new_cov

    def _new_child_coverage(self, children: List[DerivationTree],
                            max_depth: Union[int, float]) -> Set[str]:
        new_cov: Set[str] = set()
        for (c_symbol, _) in children:
            if c_symbol in self.grammar:
                new_cov |= self.max_expansion_coverage(c_symbol, max_depth)

        return new_cov

if __name__ == '__main__':
    f = GrammarCoverageFuzzer(EXPR_GRAMMAR, start_symbol="<digit>", log=True)
    f.fuzz()

if __name__ == '__main__':
    f.expansion_coverage()

if __name__ == '__main__':
    f.new_child_coverage("<digit>", [('0', [])])

if __name__ == '__main__':
    f.new_child_coverage("<digit>", [('2', [])])

if __name__ == '__main__':
    for expansion in EXPR_GRAMMAR["<digit>"]:
        children = f.expansion_to_children(expansion)
        print(expansion, f.new_child_coverage("<digit>", children))

### Adaptive Lookahead

if __name__ == '__main__':
    print('\n### Adaptive Lookahead')



#### Excursion: Implementing `new_coverage()`

if __name__ == '__main__':
    print('\n#### Excursion: Implementing `new_coverage()`')



class GrammarCoverageFuzzer(GrammarCoverageFuzzer):
    def new_coverages(self, node: DerivationTree,
                      children_alternatives: List[List[DerivationTree]]) \
            -> Optional[List[Set[str]]]:
        """Return coverage to be obtained for each child at minimum depth"""

        (symbol, children) = node
        for max_depth in range(len(self.grammar)):
            new_coverages = [
                self.new_child_coverage(
                    symbol, c, max_depth) for c in children_alternatives]
            max_new_coverage = max(len(new_coverage)
                                   for new_coverage in new_coverages)
            if max_new_coverage > 0:
                # Uncovered node found
                return new_coverages

        # All covered
        return None

#### End of Excursion

if __name__ == '__main__':
    print('\n#### End of Excursion')



### All Together

if __name__ == '__main__':
    print('\n### All Together')



#### Excursion: Implementing `choose_node_expansion()`

if __name__ == '__main__':
    print('\n#### Excursion: Implementing `choose_node_expansion()`')



class GrammarCoverageFuzzer(GrammarCoverageFuzzer):
    def choose_node_expansion(self, node: DerivationTree,
                              children_alternatives: List[List[DerivationTree]]) -> int:
        """Choose an expansion of `node` among `children_alternatives`.
           Return `n` such that expanding `children_alternatives[n]`
           yields the highest additional coverage."""

        (symbol, children) = node
        new_coverages = self.new_coverages(node, children_alternatives)

        if new_coverages is None:
            # All expansions covered - use superclass method
            return self.choose_covered_node_expansion(node, children_alternatives)

        max_new_coverage = max(len(cov) for cov in new_coverages)

        children_with_max_new_coverage = [c for (i, c) in enumerate(children_alternatives)
                                          if len(new_coverages[i]) == max_new_coverage]
        index_map = [i for (i, c) in enumerate(children_alternatives)
                     if len(new_coverages[i]) == max_new_coverage]

        # Select a random expansion
        new_children_index = self.choose_uncovered_node_expansion(
            node, children_with_max_new_coverage)
        new_children = children_with_max_new_coverage[new_children_index]

        # Save the expansion as covered
        key = expansion_key(symbol, new_children)

        if self.log:
            print("Now covered:", key)
        self.covered_expansions.add(key)

        return index_map[new_children_index]

#### End of Excursion

if __name__ == '__main__':
    print('\n#### End of Excursion')



if __name__ == '__main__':
    f = GrammarCoverageFuzzer(EXPR_GRAMMAR, min_nonterminals=3)
    f.fuzz()

if __name__ == '__main__':
    f.max_expansion_coverage() - f.expansion_coverage()

if __name__ == '__main__':
    average_length_until_full_coverage(GrammarCoverageFuzzer(EXPR_GRAMMAR))

if __name__ == '__main__':
    f = GrammarCoverageFuzzer(CGI_GRAMMAR, min_nonterminals=5)
    while len(f.max_expansion_coverage() - f.expansion_coverage()) > 0:
        print(f.fuzz())

if __name__ == '__main__':
    average_length_until_full_coverage(TrackingGrammarCoverageFuzzer(CGI_GRAMMAR))

if __name__ == '__main__':
    average_length_until_full_coverage(SimpleGrammarCoverageFuzzer(CGI_GRAMMAR))

if __name__ == '__main__':
    average_length_until_full_coverage(GrammarCoverageFuzzer(CGI_GRAMMAR))

## Coverage in Context
## -------------------

if __name__ == '__main__':
    print('\n## Coverage in Context')



if __name__ == '__main__':
    EXPR_GRAMMAR["<factor>"]

### Extending Grammars for Context Coverage Manually

if __name__ == '__main__':
    print('\n### Extending Grammars for Context Coverage Manually')



if __name__ == '__main__':
    dup_expr_grammar = extend_grammar(EXPR_GRAMMAR,
                                      {
                                          "<factor>": ["+<factor>", "-<factor>", "(<expr>)", "<integer-1>.<integer-2>", "<integer>"],
                                          "<integer-1>": ["<digit-1><integer-1>", "<digit-1>"],
                                          "<integer-2>": ["<digit-2><integer-2>", "<digit-2>"],
                                          "<digit-1>":
                                          ["0", "1", "2", "3", "4",
                                              "5", "6", "7", "8", "9"],
                                          "<digit-2>":
                                          ["0", "1", "2", "3", "4",
                                              "5", "6", "7", "8", "9"]
                                      }
                                      )

if __name__ == '__main__':
    assert is_valid_grammar(dup_expr_grammar)

if __name__ == '__main__':
    f = GrammarCoverageFuzzer(dup_expr_grammar, start_symbol="<factor>")
    for i in range(10):
        print(f.fuzz())

### Extending Grammars for Context Coverage Programmatically

if __name__ == '__main__':
    print('\n### Extending Grammars for Context Coverage Programmatically')



from .Grammars import new_symbol, unreachable_nonterminals
from .GrammarFuzzer import expansion_to_children

def duplicate_context(grammar: Grammar, 
                      symbol: str,
                      expansion: Optional[Expansion] = None, 
                      depth: Union[float, int] = float('inf')):
    """Duplicate an expansion within a grammar.

    In the given grammar, take the given expansion of the given `symbol`
    (if `expansion` is omitted: all symbols), and replace it with a
    new expansion referring to a duplicate of all originally referenced rules.

    If `depth` is given, limit duplication to `depth` references
    (default: unlimited)
    """
    orig_grammar = extend_grammar(grammar)
    _duplicate_context(grammar, orig_grammar, symbol,
                       expansion, depth, seen={})

    # After duplication, we may have unreachable rules; delete them
    for nonterminal in unreachable_nonterminals(grammar):
        del grammar[nonterminal]

#### Excursion: Implementing `_duplicate_context()`

if __name__ == '__main__':
    print('\n#### Excursion: Implementing `_duplicate_context()`')



import copy

def _duplicate_context(grammar: Grammar,
                       orig_grammar: Grammar,
                       symbol: str,
                       expansion: Optional[Expansion],
                       depth: Union[float, int],
                       seen: Dict[str, str]) -> None:
    """Helper function for `duplicate_context()`"""

    for i in range(len(grammar[symbol])):
        if expansion is None or grammar[symbol][i] == expansion:
            new_expansion = ""
            for (s, c) in expansion_to_children(grammar[symbol][i]):
                if s in seen:                 # Duplicated already
                    new_expansion += seen[s]
                elif c == [] or depth == 0:   # Terminal symbol or end of recursion
                    new_expansion += s
                else:                         # Nonterminal symbol - duplicate
                    # Add new symbol with copy of rule
                    new_s = new_symbol(grammar, s)
                    grammar[new_s] = copy.deepcopy(orig_grammar[s])

                    # Duplicate its expansions recursively
                    # {**seen, **{s: new_s}} is seen + {s: new_s}
                    _duplicate_context(grammar, orig_grammar, new_s, expansion=None,
                                       depth=depth - 1, seen={**seen, **{s: new_s}})
                    new_expansion += new_s

            grammar[symbol][i] = new_expansion

#### End of Excursion

if __name__ == '__main__':
    print('\n#### End of Excursion')



if __name__ == '__main__':
    dup_expr_grammar = extend_grammar(EXPR_GRAMMAR)
    duplicate_context(dup_expr_grammar, "<factor>", "<integer>.<integer>")
    dup_expr_grammar

if __name__ == '__main__':
    f = GrammarCoverageFuzzer(dup_expr_grammar, start_symbol="<factor>")
    for i in range(10):
        print(f.fuzz())

if __name__ == '__main__':
    dup_expr_grammar = extend_grammar(EXPR_GRAMMAR)
    duplicate_context(dup_expr_grammar, "<factor>", "<integer>.<integer>", depth=1)
    dup_expr_grammar

if __name__ == '__main__':
    assert is_valid_grammar(dup_expr_grammar)

if __name__ == '__main__':
    dup_expr_grammar = extend_grammar(EXPR_GRAMMAR)
    duplicate_context(dup_expr_grammar, "<expr>")

if __name__ == '__main__':
    assert is_valid_grammar(dup_expr_grammar)
    len(dup_expr_grammar)

if __name__ == '__main__':
    f = GrammarCoverageFuzzer(dup_expr_grammar)
    len(f.max_expansion_coverage())

if __name__ == '__main__':
    dup_expr_grammar = extend_grammar(EXPR_GRAMMAR)
    duplicate_context(dup_expr_grammar, "<expr>")
    duplicate_context(dup_expr_grammar, "<expr-1>")
    len(dup_expr_grammar)

if __name__ == '__main__':
    f = GrammarCoverageFuzzer(dup_expr_grammar)
    len(f.max_expansion_coverage())

if __name__ == '__main__':
    dup_expr_grammar["<expr>"]

if __name__ == '__main__':
    dup_expr_grammar["<term-1-1>"]

if __name__ == '__main__':
    dup_expr_grammar["<factor-1-1>"]

## Covering Code by Covering Grammars
## ----------------------------------

if __name__ == '__main__':
    print('\n## Covering Code by Covering Grammars')



### CGI Grammars

if __name__ == '__main__':
    print('\n### CGI Grammars')



#### Excursion: Creating the Plot

if __name__ == '__main__':
    print('\n#### Excursion: Creating the Plot')



from .Coverage import Coverage, cgi_decode

if __name__ == '__main__':
    with Coverage() as cov_max:
        cgi_decode('+')
        cgi_decode('%20')
        cgi_decode('abc')
        try:
            cgi_decode('%?a')
        except:
            pass

if __name__ == '__main__':
    f = GrammarCoverageFuzzer(CGI_GRAMMAR, max_nonterminals=2)
    coverages: Dict[float, List[float]] = {}

    trials = 100
    for trial in range(trials):
        f.reset_coverage()
        overall_cov = set()
        max_cov = 30

        for i in range(10):
            s = f.fuzz()
            with Coverage() as cov:
                cgi_decode(s)
            overall_cov |= cov.coverage()

            x = len(f.expansion_coverage()) * 100 / len(f.max_expansion_coverage())
            y = len(overall_cov) * 100 / len(cov_max.coverage())
            if x not in coverages:
                coverages[x] = []
            coverages[x].append(y)

if __name__ == '__main__':
    xs = list(coverages.keys())
    ys = [sum(coverages[x]) / len(coverages[x]) for x in coverages]

# %matplotlib inline

if __name__ == '__main__':
    import matplotlib.pyplot as plt  # type: ignore

if __name__ == '__main__':
    import matplotlib.ticker as mtick  # type: ignore

if __name__ == '__main__':
    ax = plt.axes(label="CGI coverage")
    ax.yaxis.set_major_formatter(mtick.PercentFormatter())
    ax.xaxis.set_major_formatter(mtick.PercentFormatter())

    plt.xlim(0, max(xs))
    plt.ylim(0, max(ys))

    plt.title('Coverage of cgi_decode() vs. grammar coverage')
    plt.xlabel('grammar coverage (expansions)')
    plt.ylabel('code coverage (lines)')

#### End of Excursion

if __name__ == '__main__':
    print('\n#### End of Excursion')



if __name__ == '__main__':
    plt.scatter(xs, ys);

if __name__ == '__main__':
    import numpy as np

if __name__ == '__main__':
    np.corrcoef(xs, ys)

if __name__ == '__main__':
    from scipy.stats import spearmanr  # type: ignore

if __name__ == '__main__':
    spearmanr(xs, ys)

### URL Grammars

if __name__ == '__main__':
    print('\n### URL Grammars')



from urllib.parse import urlparse

#### Excursion: Creating the Plot

if __name__ == '__main__':
    print('\n#### Excursion: Creating the Plot')



if __name__ == '__main__':
    with Coverage() as cov_max:
        urlparse("http://foo.bar/path")
        urlparse("https://foo.bar#fragment")
        urlparse("ftp://user:password@foo.bar?query=value")
        urlparse("ftps://127.0.0.1/?x=1&y=2")

if __name__ == '__main__':
    f = GrammarCoverageFuzzer(URL_GRAMMAR, max_nonterminals=2)
    coverages: Dict[float, List[float]] = {}

    trials = 100
    for trial in range(trials):
        f.reset_coverage()
        overall_cov = set()

        for i in range(20):
            s = f.fuzz()
            with Coverage() as cov:
                urlparse(s)
            overall_cov |= cov.coverage()

            x = len(f.expansion_coverage()) * 100 / len(f.max_expansion_coverage())
            y = len(overall_cov) * 100 / len(cov_max.coverage())
            if x not in coverages:
                coverages[x] = []
            coverages[x].append(y)

if __name__ == '__main__':
    xs = list(coverages.keys())
    ys = [sum(coverages[x]) / len(coverages[x]) for x in coverages]

if __name__ == '__main__':
    ax = plt.axes(label="URL coverage")
    ax.yaxis.set_major_formatter(mtick.PercentFormatter())
    ax.xaxis.set_major_formatter(mtick.PercentFormatter())

    plt.xlim(0, max(xs))
    plt.ylim(0, max(ys))

    plt.title('Coverage of urlparse() vs. grammar coverage')
    plt.xlabel('grammar coverage (expansions)')
    plt.ylabel('code coverage (lines)')

#### End of Excursion

if __name__ == '__main__':
    print('\n#### End of Excursion')



if __name__ == '__main__':
    plt.scatter(xs, ys);

if __name__ == '__main__':
    np.corrcoef(xs, ys)

if __name__ == '__main__':
    spearmanr(xs, ys)

### Will this always work?

if __name__ == '__main__':
    print('\n### Will this always work?')



#### Equivalent Elements

if __name__ == '__main__':
    print('\n#### Equivalent Elements')



#### Deep Data Processing

if __name__ == '__main__':
    print('\n#### Deep Data Processing')



## Synopsis
## --------

if __name__ == '__main__':
    print('\n## Synopsis')



from .Grammars import EXPR_GRAMMAR

if __name__ == '__main__':
    expr_fuzzer = GrammarCoverageFuzzer(EXPR_GRAMMAR)

if __name__ == '__main__':
    expr_fuzzer.fuzz();

if __name__ == '__main__':
    expr_fuzzer.fuzz()

if __name__ == '__main__':
    expr_fuzzer.expansion_coverage()

from .ClassDiagram import display_class_hierarchy

if __name__ == '__main__':
    display_class_hierarchy([GrammarCoverageFuzzer],
                            public_methods=[
                                Fuzzer.run,
                                Fuzzer.runs,
                                GrammarFuzzer.__init__,
                                GrammarFuzzer.fuzz,
                                GrammarFuzzer.fuzz_tree,
                                TrackingGrammarCoverageFuzzer.max_expansion_coverage,
                                TrackingGrammarCoverageFuzzer.missing_expansion_coverage,
                                TrackingGrammarCoverageFuzzer.reset_coverage,
                                GrammarCoverageFuzzer.__init__,
                                GrammarCoverageFuzzer.fuzz,
                                GrammarCoverageFuzzer.expansion_coverage,
                            ],
                            types={
                                'DerivationTree': DerivationTree,
                                'Expansion': Expansion,
                                'Grammar': Grammar
                            },
                            project='fuzzingbook')

## Lessons Learned
## ---------------

if __name__ == '__main__':
    print('\n## Lessons Learned')



## Next Steps
## ----------

if __name__ == '__main__':
    print('\n## Next Steps')



## Background
## ----------

if __name__ == '__main__':
    print('\n## Background')



## Exercises
## ---------

if __name__ == '__main__':
    print('\n## Exercises')



### Exercise 1: Testing ls

if __name__ == '__main__':
    print('\n### Exercise 1: Testing ls')



LS_EBNF_GRAMMAR: Grammar = {
    '<start>': ['-<options>'],
    '<options>': ['<option>*'],
    '<option>': ['1', 'A', '@',
                 # many more
                 ]
}

if __name__ == '__main__':
    assert is_valid_grammar(LS_EBNF_GRAMMAR)

from .Grammars import convert_ebnf_grammar, srange

LS_EBNF_GRAMMAR: Grammar = {
    '<start>': ['-<options>'],
    '<options>': ['<option>*'],
    '<option>': srange("ABCFGHLOPRSTUW@abcdefghiklmnopqrstuwx1")
}

if __name__ == '__main__':
    assert is_valid_grammar(LS_EBNF_GRAMMAR)

LS_GRAMMAR: Grammar = convert_ebnf_grammar(LS_EBNF_GRAMMAR)

from .Fuzzer import ProgramRunner

if __name__ == '__main__':
    f = GrammarCoverageFuzzer(LS_GRAMMAR, max_nonterminals=3)
    while len(f.max_expansion_coverage() - f.expansion_coverage()) > 0:
        invocation = f.fuzz()
        print("ls", invocation, end="; ")
        args = invocation.split()
        ls = ProgramRunner(["ls"] + args)
        ls.run()
    print()

### Exercise 2: Caching

if __name__ == '__main__':
    print('\n### Exercise 2: Caching')