<jupyter_start><jupyter_text>Probabilistic Grammar FuzzingLet us give grammars even more power by assigning _probabilities_ to individual expansions.  This allows us to control how many of each element should be produced, and thus allows us to _target_ our generated tests towards specific functionality.  We also show how to learn such probabilities from given sample inputs, and specifically direct our tests towards input features that are uncommon in these samples. **Prerequisites*** You should have read the [chapter on grammars](Grammars.ipynb).* Our implementation hooks into the grammar-based fuzzer introduced in ["Efficient Grammar Fuzzing"](GrammarFuzzer.ipynb)* For learning probabilities from samples, we make use of [parsers](Parser.ipynb)  The Law of Leading Digits In all our examples so far, you may have noted that inputs generated by a program differ quite a bit from "natural" inputs as they occur in real life.  This is true even for innocuous elements such as numbers – yes, the numbers we have generated so far actually _differ_ from numbers in the real world.  This is because in real-life sets of numerical data, the _leading significant digit_ is likely to be small: Actually, on average, the leading digit `1` occurs more than _six times_ as often as the leading digit `8` or `9`.  It has been shown that this result applies to a wide variety of data sets, including electricity bills, street addresses, stock prices, house prices, population numbers, death rates, lengths of rivers, physical and mathematical constants (Wikipedia). This law, first observed by Newcomb \cite{Newcomb1881), was formalized by Benford in \cite{Benford1938).  Let us take a look at the conditions that determine the first digit of a number.  We can easily compute the first digit by converting the number into a string and take the first character:<jupyter_code>def first_digit_via_string(x):
    return ord(repr(x)[0]) - ord('0')
first_digit_via_string(2001)<jupyter_output><empty_output><jupyter_text>To do this mathematically, though, we have to take the fractional part of their logarithm, or formally$$d = 10^{\{\log_{10}(x)\}}$$where $\{x\}$ is the fractional part of $x$ (i.e. $\{1.234\} = 0.234$).<jupyter_code>import math
def first_digit_via_log(x):
    frac, whole = math.modf(math.log10(x))
    return int(10 ** frac)
first_digit_via_log(2001)<jupyter_output><empty_output><jupyter_text>Most sets of "naturally" occurring numbers should not have any bias in the fractional parts of their logarithms, and hence, the fractional part $\{\log_{10}(x)\}$ is typically uniformly distributed.  However, the fractional parts for the individual digits are _not_ evenly distributed.   For a number to start with a digit $d$, the condition $d < 10^{\{\log_{10}(x)\}} < d + 1$ must hold.  To start with the digit 1, the fractional part $\{\log_{10}(x)\}$ must thus be in the range<jupyter_code>(math.log10(1), math.log10(2))<jupyter_output><empty_output><jupyter_text>To start with the digit 2, though, it must be in the range<jupyter_code>(math.log10(2), math.log10(3))<jupyter_output><empty_output><jupyter_text>which is much smaller.  Formally, the probability $P(d)$ for a leading digit $d$ (again, assuming uniformly distributed fractional parts) is known as Benford's law:$$P(d) = \log_{10}(d + 1) - \log_{10}(d)$$which gives us:<jupyter_code>def prob_leading_digit(d):
    return math.log10(d + 1) - math.log10(d)<jupyter_output><empty_output><jupyter_text>Let us compute these probabilities for all digits:<jupyter_code>digit_probs = [prob_leading_digit(d) for d in range(1, 10)]
[(d, "%.2f" % digit_probs[d - 1]) for d in range(1, 10)]
import matplotlib.pyplot as plt
labels = range(1, 10)
fig1, ax1 = plt.subplots()
ax1.pie(digit_probs, labels=labels, shadow=True, autopct='%1.1f%%',
        counterclock=False, startangle=90)
ax1.axis('equal')<jupyter_output><empty_output><jupyter_text>We see that a leading 1 is indeed six times a probable than a leading 9. Benford's law has a number of applications.  Most notably, it can be used to detect "non-natural" numbers, i.e. numbers that apparently were created randomly rather than coming from a "natural" source.  if you write a scientific paper and fake data by putting in random numbers (for instance, [using our grammar fuzzer](GrammarFuzzer.ipynb) on integers), you will likely violate Benford's law, and this can indeed be spotted.  On the other hand, how would we proceed if we _wanted_ to create numbers that adhere to Benson's law?  To this end, we need to be able to _encode_ probabilities such as the above in our grammar, such that we can ensure that a leading digit is indeed a `1` in 30% of all cases.  Specifying ProbabilitiesThe goal of this chapter is to assign _probabilities_ to individual expansions in the grammar, such that we can express that some expansion alternatives should be favored over others.  This is not only useful to generate "natural"-looking numbers, but even more so to _direct_ test generation towards a specific goal.  If you recently have changed some code in your program, you would probably like to generate inputs that exercise precisely this code.  By raising the probabilities on the input elements associated with the changed code, you will get more tests that exercise the changed code. Our concept for expressing probabilities is to _annotate_ individual expansions with attributes such as probabilities.  To this end, we allow that an expansion cannot only be a string, but also a _pair_ of a string and a set of attributes, as in```python    "":        [(" + ", opts(prob=0.1)),         (" - ", opts(prob=0.2)),         ""]```Here, the `opts()` function would allow us to express probabilities for choosing the individual expansions.  The addition would have a probability of 10%, the subtraction of 20%.  The remaining probability (in this case 70%) is equally distributed over the non-attributed expansions (in this case the single last one). Our `opts()` helper function returns a mapping of its arguments to values:<jupyter_code>def opts(**kwargs):
    return kwargs
opts(prob=0.50)<jupyter_output><empty_output><jupyter_text>We can now use pairs with `opts()` to assign probabilities to our expression grammar:<jupyter_code>import fuzzingbook_utils
from GrammarFuzzer import GrammarFuzzer, all_terminals
from Grammars import is_valid_grammar, EXPR_GRAMMAR, START_SYMBOL, crange
PROBABILISTIC_EXPR_GRAMMAR = {
    "<start>":
        ["<expr>"],

    "<expr>":
        [("<term> + <expr>", opts(prob=0.1)),
         ("<term> - <expr>", opts(prob=0.2)),
         "<term>"],

    "<term>":
        [("<factor> * <term>", opts(prob=0.1)),
         ("<factor> / <term>", opts(prob=0.1)),
         "<factor>"
         ],

    "<factor>":
        ["+<factor>", "-<factor>", "(<expr>)",
            "<leadinteger>", "<leadinteger>.<integer>"],

    "<leadinteger>":
        ["<leaddigit><integer>", "<leaddigit>"],

    # Benford's law: frequency distribution of leading digits
    "<leaddigit>":
        [("1", opts(prob=0.301)),
         ("2", opts(prob=0.176)),
         ("3", opts(prob=0.125)),
         ("4", opts(prob=0.097)),
         ("5", opts(prob=0.079)),
         ("6", opts(prob=0.067)),
         ("7", opts(prob=0.058)),
         ("8", opts(prob=0.051)),
         ("9", opts(prob=0.046)),
         ],

    # Remaining digits are equally distributed
    "<integer>":
        ["<digit><integer>", "<digit>"],

    "<digit>":
        ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"],
}
assert is_valid_grammar(PROBABILISTIC_EXPR_GRAMMAR)<jupyter_output><empty_output><jupyter_text>This is how the grammar expansions are represented internally:<jupyter_code>PROBABILISTIC_EXPR_GRAMMAR["<leaddigit>"]<jupyter_output><empty_output><jupyter_text>However, we typically access the expansion string and the associated probability via designated helper functions, `exp_string()` and `exp_prob()`:<jupyter_code>def exp_string(expansion):
    """Return the string to be expanded"""
    if isinstance(expansion, str):
        return expansion
    return expansion[0]
leaddigit_expansion = PROBABILISTIC_EXPR_GRAMMAR["<leaddigit>"][0]
leaddigit_expansion
exp_string(leaddigit_expansion)
def exp_opts(expansion):
    """Return the options of an expansion"""
    if isinstance(expansion, str):
        return None
    return expansion[1]
exp_opts(leaddigit_expansion)
def exp_prob(expansion):
    """Return the specified probability, or None if unspecified"""
    if isinstance(expansion, str):
        return None
    return exp_opts(expansion)['prob']
exp_prob(leaddigit_expansion)<jupyter_output><empty_output><jupyter_text>Fortunately, our existing fuzzers have been set up to work well with grammars annotated this way.  They simply ignore all annotations:<jupyter_code>f = GrammarFuzzer(PROBABILISTIC_EXPR_GRAMMAR)
f.fuzz()
from GrammarCoverageFuzzer import GrammarCoverageFuzzer
f = GrammarCoverageFuzzer(PROBABILISTIC_EXPR_GRAMMAR)
f.fuzz()<jupyter_output><empty_output><jupyter_text>Computing ProbabilitiesLet us define functions that access probabilities for given expansions.  While doing so, they also check for inconsistencies.  Distributing ProbabilitiesHere is how we distribute probabilities for expansions without specified probabilities. Given an expansion rule$$S ::= a_1\:|\: a_2 \:|\: \dots \:|\: a_n \:|\: u_1 \:|\: u_2 \:|\: \dots u_m$$with $n \ge 0$ alternatives $a_i$ for which the probability $p(a_i)$ is _specified_ and$m \ge 0$ alternatives $u_j$ for which the probability $p(u_j)$ is _unspecified_, the "remaining" probability is distributed equally over all $u_j$; in other words,$$p(u_j) = \frac{1 - \sum_{i = 0}^{n}p(a_i)}{m}$$If no probabilities are specified ($n = 0$), then all expansions have the same probability.The overall sum of probabilities must be 1:$$\sum_{i = 0}^{n} p(a_i) + \sum_{j = 0}^{m} p(u_i) = 1$$We check these properties while distributing probabilities. The function `exp_probabilities()` returns a mapping of all expansions in a rule to their respective probabilities.<jupyter_code>def exp_probabilities(expansions, nonterminal="<symbol>"):
    probabilities = [exp_prob(expansion) for expansion in expansions]
    prob_dist = prob_distribution(probabilities, nonterminal)

    prob_mapping = {}
    for i in range(len(expansions)):
        expansion = exp_string(expansions[i])
        prob_mapping[expansion] = prob_dist[i]

    return prob_mapping<jupyter_output><empty_output><jupyter_text>The gist of `exp_probabilities()` is handled in `prob_distribution()`, which does the actual checking and computation.<jupyter_code>def prob_distribution(probabilities, nonterminal="<symbol>"):
    epsilon = 0.00001

    number_of_unspecified_probabilities = probabilities.count(None)
    if number_of_unspecified_probabilities == 0:
        assert abs(sum(probabilities) - 1.0) < epsilon, \
            nonterminal + ": sum of probabilities must be 1.0"
        return probabilities

    sum_of_specified_probabilities = 0.0
    for p in probabilities:
        if p is not None:
            sum_of_specified_probabilities += p
    assert 0 <= sum_of_specified_probabilities <= 1.0, \
        nonterminal + ": sum of specified probabilities must be between 0.0 and 1.0"

    default_probability = ((1.0 - sum_of_specified_probabilities)
                           / number_of_unspecified_probabilities)
    all_probabilities = []
    for p in probabilities:
        if p is None:
            p = default_probability
        all_probabilities.append(p)

    assert abs(sum(all_probabilities) - 1.0) < epsilon
    return all_probabilities<jupyter_output><empty_output><jupyter_text>Here's the mapping `exp_probabilities()` returns for the annotated `` element:<jupyter_code>print(exp_probabilities(PROBABILISTIC_EXPR_GRAMMAR["<leaddigit>"]))<jupyter_output>{'1': 0.301, '2': 0.176, '3': 0.125, '4': 0.097, '5': 0.079, '6': 0.067, '7': 0.058, '8': 0.051, '9': 0.046}<jupyter_text>If no expansion is annotated, all expansions have the same likelihood of being selected, as in our previous grammar fuzzers.<jupyter_code>print(exp_probabilities(PROBABILISTIC_EXPR_GRAMMAR["<digit>"]))<jupyter_output>{'0': 0.1, '1': 0.1, '2': 0.1, '3': 0.1, '4': 0.1, '5': 0.1, '6': 0.1, '7': 0.1, '8': 0.1, '9': 0.1}<jupyter_text>Here's how `exp_probabilities()` distributes any remaining probability across non-annotated expansions:<jupyter_code>exp_probabilities(PROBABILISTIC_EXPR_GRAMMAR["<expr>"])<jupyter_output><empty_output><jupyter_text>Checking Probabilities We can use the checking capabilities of `exp_probabilities()` to check a probabilistic grammar for consistency:<jupyter_code>def is_valid_probabilistic_grammar(grammar, start_symbol=START_SYMBOL):
    if not is_valid_grammar(grammar, start_symbol):
        return False

    for nonterminal in grammar:
        expansions = grammar[nonterminal]
        prob_dist = exp_probabilities(expansions, nonterminal)

    return True
assert is_valid_probabilistic_grammar(PROBABILISTIC_EXPR_GRAMMAR)
assert is_valid_probabilistic_grammar(EXPR_GRAMMAR)
from ExpectError import ExpectError
with ExpectError():
    assert is_valid_probabilistic_grammar({"<start>": [("1", opts(prob=0.5))]})
with ExpectError():
    assert is_valid_probabilistic_grammar(
        {"<start>": [("1", opts(prob=1.5)), "2"]})<jupyter_output>Traceback (most recent call last):
  File "<ipython-input-40-79fe851796f9>", line 3, in <module>
    {"<start>": [("1", opts(prob=1.5)), "2"]})
  File "<ipython-input-35-c1c25dbf0315>", line 7, in is_valid_probabilistic_grammar
    prob_dist = exp_probabilities(expansions, nonterminal)
  File "<ipython-input-30-9042a394542d>", line 3, in exp_probabilities
    prob_dist = prob_distribution(probabilities, nonterminal)
  File "<ipython-input-31-57a3f95cf4ed>", line 13, in prob_distribution
    assert 0 <= sum_of_specified_probabilities <= 1.0,         nonterminal + ": sum of specified probabilities must be between 0.0 and 1.0"
AssertionError: <start>: sum of specified probabilities must be between 0.0 and 1.0 (expected)<jupyter_text>Expanding by ProbabilityNow that we have seen how to specify probabilities for a grammar, we can actually implement probabilistic expansion.  In our `ProbabilisticGrammarFuzzer`, it suffices to overload one method, namely `choose_node_expansion()`.  For each of the children we can choose from (typically all expansions of a symbol), we determine their probability (using `exp_probabilities()` defined above), and make a weighted choice using `random.choices()` with a `weight` argument.<jupyter_code>import random
class ProbabilisticGrammarFuzzer(GrammarFuzzer):
    def choose_node_expansion(self, node, possible_children):
        (symbol, tree) = node
        expansions = self.grammar[symbol]
        probabilities = exp_probabilities(expansions)

        weights = []
        for child in possible_children:
            expansion = all_terminals((node, child))
            child_weight = probabilities[expansion]
            if self.log:
                print(repr(expansion), "p =", child_weight)
            weights.append(child_weight)

        if sum(weights) == 0:
            # No alternative (probably expanding at minimum cost)
            weights = None

        return random.choices(range(len(possible_children)), weights=weights)[0]<jupyter_output><empty_output><jupyter_text>Our probabilistic grammar fuzzer works just like the non-probabilistic grammar fuzzer, except that it actually respects probability annotations.  Let us generate a couple of "natural" numbers that respect Benford's law:<jupyter_code>natural_fuzzer = ProbabilisticGrammarFuzzer(
    PROBABILISTIC_EXPR_GRAMMAR, start_symbol="<leadinteger>")
print([natural_fuzzer.fuzz() for i in range(20)])<jupyter_output>['2588', '106', '10', '2', '7', '1', '95', '4', '192', '8', '2', '1', '1', '2', '2', '208', '1036', '5592', '157', '1442']<jupyter_text>In contrast, these numbers are pure random:<jupyter_code>integer_fuzzer = GrammarFuzzer(
    PROBABILISTIC_EXPR_GRAMMAR, start_symbol="<leadinteger>")
print([integer_fuzzer.fuzz() for i in range(20)])<jupyter_output>['3', '1', '56', '5', '408251024', '7', '27', '2', '9', '6456', '7', '32', '1', '4', '7', '19', '2', '6', '2', '5']<jupyter_text>Are the "natural" numbers really more "natural" than the random ones?  To show that `ProbabilisticGrammarFuzzer` indeed respects  the probabilistic annotations, let us create a specific fuzzer for the lead digit:<jupyter_code>leaddigit_fuzzer = ProbabilisticGrammarFuzzer(
    PROBABILISTIC_EXPR_GRAMMAR, start_symbol="<leaddigit>")
leaddigit_fuzzer.fuzz()<jupyter_output><empty_output><jupyter_text>If we generate thousands of lead digits, their distribution should again follow Benford's law:<jupyter_code>trials = 10000

count = {}
for c in crange('0', '9'):
    count[c] = 0

for i in range(trials):
    count[leaddigit_fuzzer.fuzz()] += 1

print([(digit, count[digit] / trials) for digit in count])<jupyter_output>[('0', 0.0), ('1', 0.3003), ('2', 0.1756), ('3', 0.1222), ('4', 0.0938), ('5', 0.0816), ('6', 0.0651), ('7', 0.06), ('8', 0.0537), ('9', 0.0477)]<jupyter_text>Quod erat demonstrandum! The distribution is pretty much exactly as originally specified.  We now have a fuzzer where we can exercise control by specifying probabilities.  Directed FuzzingAssigning probabilities to individual expansions gives us great control over which inputs should be generated.  By choosing probabilities wisely, we can _direct_ fuzzing towards specific functions and features – for instance, towards functions that are particularly critical, prone to failures, or that have been recently changed. As an example, consider the URL grammar from the [chapter on grammars](Grammars.ipynb).  Let us assume we have just made a change to our implementation of the secure FTP protocol.  By assigning a higher probability to the `ftps` scheme, we can generate more URLs that will specifically test this functionality. First, let us define a helper function that sets a particular option:<jupyter_code>from Grammars import URL_GRAMMAR
def set_opts(grammar, symbol, expansion, opts=None):
    """Set the options of the given expansion of grammar[symbol] to opts"""
    expansions = grammar[symbol]
    for i in range(len(expansions)):
        exp = expansions[i]
        if exp_string(exp) == expansion:
            new_opts = exp_opts(exp)
            if opts is None or new_opts is None:
                new_opts = opts
            else:
                for key in opts:
                    new_opts[key] = opts[key]
            if new_opts is None:
                grammar[symbol][i] = exp_string(exp)
            else:
                grammar[symbol][i] = (exp_string(exp), new_opts)
            return<jupyter_output><empty_output><jupyter_text>Here's a specialization just for probabilities:<jupyter_code>def set_prob(grammar, symbol, expansion, prob):
    """Set the probability of the given expansion of grammar[symbol]"""
    set_opts(grammar, symbol, expansion, opts(prob=prob))<jupyter_output><empty_output><jupyter_text>Let us use `set_prob()` to give the `ftps` expansion a probability of 80%:<jupyter_code>import copy
probabilistic_url_grammar = copy.deepcopy(URL_GRAMMAR)
set_prob(probabilistic_url_grammar, "<scheme>", "ftps", 0.8)
assert is_valid_probabilistic_grammar(probabilistic_url_grammar)
probabilistic_url_grammar["<scheme>"]<jupyter_output><empty_output><jupyter_text>If we use this grammar for fuzzing, we will get plenty of `ftps:` prefixes:<jupyter_code>prob_url_fuzzer = ProbabilisticGrammarFuzzer(probabilistic_url_grammar)
for i in range(10):
    print(prob_url_fuzzer.fuzz())<jupyter_output>ftps://cispa.saarland:80
ftps://user:password@cispa.saarland/
ftps://fuzzingbook.com/abc
ftps://fuzzingbook.com/x48
ftps://user:password@fuzzingbook.com/
ftps://www.google.com:2?x18=8
ftps://user:password@www.google.com:6
ftps://user:password@cispa.saarland/def
ftps://user:password@cispa.saarland/def?def=52
ftps://user:password@cispa.saarland/<jupyter_text>In a similar vein, we can direct URL generation towards specific hosts or ports; we can favor URLs with queries, fragments, or logins – or URLs without these.  All it takes is to set appropriate probabilities. By setting the probability of an expansion to zero, we can effectively disable specific expansions:<jupyter_code>set_prob(probabilistic_url_grammar, "<scheme>", "ftps", 0.0)
assert is_valid_probabilistic_grammar(probabilistic_url_grammar)
prob_url_fuzzer = ProbabilisticGrammarFuzzer(probabilistic_url_grammar)
for i in range(10):
    print(prob_url_fuzzer.fuzz())<jupyter_output>ftp://user:password@cispa.saarland/x00
https://user:password@www.google.com/?def=6&def=x18&def=def
https://user:password@fuzz<EMAIL>:7/?def=abc
https://user:password@www.google.com:8080/
ftp://www.google.com/?abc=36&x34=5
http://user:password@cispa.saarland/
https://www.google.com/
https://user:password@www.google.com:85/?def=18
http://user:password@www.google.com:80/
http://fuzzingbook.com:80/?abc=def<jupyter_text>Note that even if we set the probability of an expansion to zero, we may still see the expansion taken. This can happen during the "closing" phase of [our grammar fuzzer](GrammarFuzzer.ipynb), when the expansion is closed at minimum cost.  At this stage, even expansions with "zero" probability will be taken if this is necessary for closing the expansion. Let us illustrate this feature using the `` rule from our expression grammar:<jupyter_code>from Grammars import EXPR_GRAMMAR
probabilistic_expr_grammar = copy.deepcopy(EXPR_GRAMMAR)
probabilistic_expr_grammar["<expr>"]<jupyter_output><empty_output><jupyter_text>If we set the probability of the `` expansion to zero, the string should expand again and again.<jupyter_code>set_prob(probabilistic_expr_grammar, "<expr>", "<term>", 0.0)
assert is_valid_probabilistic_grammar(probabilistic_expr_grammar)<jupyter_output><empty_output><jupyter_text>Still, in the "closing" phase, subexpressions will eventually expand into ``, as it is the only way to close the expansion.  Tracking `choose_node_expansion()` shows that is is invoked with only one possible expansion ``, which has to be taken even though its specified probability is zero.<jupyter_code>prob_expr_fuzzer = ProbabilisticGrammarFuzzer(probabilistic_expr_grammar)
prob_expr_fuzzer.fuzz()<jupyter_output><empty_output><jupyter_text>Probabilities in ContextWhile specified probabilities give us a means to control which expansions are taken how often, this control by itself may not be enough.  As an example, consider the following grammar for IPv4 addresses:<jupyter_code>def decrange(start, end):
    """Return a list with string representations of numbers in the range [start, end)"""
    return [repr(n) for n in range(start, end)]
IP_ADDRESS_GRAMMAR = {
    "<start>": ["<address>"],
    "<address>": ["<octet>.<octet>.<octet>.<octet>"],
    # ["0", "1", "2", ..., "255"]
    "<octet>": list(sorted(decrange(0, 256), reverse=True))
}
IP_ADDRESS_GRAMMAR["<octet>"]
assert is_valid_grammar(IP_ADDRESS_GRAMMAR)<jupyter_output><empty_output><jupyter_text>We can easily use this grammar to create IP addresses:<jupyter_code>ip_fuzzer = ProbabilisticGrammarFuzzer(IP_ADDRESS_GRAMMAR)
ip_fuzzer.fuzz()<jupyter_output><empty_output><jupyter_text>However, if we want to assign a specific probability to one of the four octets, we are out of luck.  All we can do is to assign the same probability distribution for all four octets:<jupyter_code>probabilistic_ip_address_grammar = copy.deepcopy(IP_ADDRESS_GRAMMAR)
set_prob(probabilistic_ip_address_grammar, "<octet>", "127", 0.8)
probabilistic_ip_fuzzer = ProbabilisticGrammarFuzzer(
    probabilistic_ip_address_grammar)
probabilistic_ip_fuzzer.fuzz()<jupyter_output><empty_output><jupyter_text>If we want to assign _different_ probabilities to each of the four octets, what do we do? The answer lies in the concept of _context_, which we already have seen [while discussing coverage-driven fuzzers](GrammarCoverageFuzzer.ipynb).  As with coverage-driven fuzzing, the idea is to _duplicate_ the element whose probability we want to set dependent on its context.  In our case, this means to duplicate the `` element to four individual ones, each of which can then get an individual probability distribution.  We can do this programmatically, using the `duplicate_context()` method:<jupyter_code>from GrammarCoverageFuzzer import duplicate_context
probabilistic_ip_address_grammar = copy.deepcopy(IP_ADDRESS_GRAMMAR)
duplicate_context(probabilistic_ip_address_grammar, "<address>")
probabilistic_ip_address_grammar["<address>"]<jupyter_output><empty_output><jupyter_text>Our original `` definition is now no longer required:<jupyter_code>del probabilistic_ip_address_grammar["<octet>"]<jupyter_output><empty_output><jupyter_text>We can now assign different probabilities to each of the `` symbols.  For instance, we can force specific expansions by setting their probability to 100%:<jupyter_code>set_prob(probabilistic_ip_address_grammar, "<octet-1>", "127", 1.0)
set_prob(probabilistic_ip_address_grammar, "<octet-2>", "0", 1.0)
assert is_valid_probabilistic_grammar(probabilistic_ip_address_grammar)<jupyter_output><empty_output><jupyter_text>The remaining two octets `` and `` have no specific probabilities set.  During fuzzing, all their expansions (all octets) are thus still available:<jupyter_code>probabilistic_ip_fuzzer = ProbabilisticGrammarFuzzer(
    probabilistic_ip_address_grammar)
[probabilistic_ip_fuzzer.fuzz() for i in range(5)]<jupyter_output><empty_output><jupyter_text>Just as with coverage, we can duplicate grammar rules arbitrarily often to get more and more finer-grained control over probabilities.  However, this finer-grained control also comes at the cost of having to maintain these probabilities.  In the next section, we will therefore discuss means to assign and tune such probabilities automatically.  Learning Probabilities from SamplesProbabilities need not be set manually all the time.  They can also be _learned_ from other sources.<jupyter_code>from GrammarFuzzer import display_tree
from Parser import PEGParser
parser = PEGParser(IP_ADDRESS_GRAMMAR)
tree = parser.parse("127.0.0.1")[0]
display_tree(tree)
from Parser import EarleyParser
parser = EarleyParser(IP_ADDRESS_GRAMMAR)
tree = parser.parse("127.0.0.1")[0]
display_tree(tree)<jupyter_output><empty_output><jupyter_text>\todo{FIXME: "127" should be one string} 1. Count individual expansions over a sample as weights.2. Assign these as probabilities to the grammar.  Auto-Tuning Probabilities1. First, generate a set of inputs.2. Then, measure coverage.3. Pick the slice of inputs that satisfies a particular goal (say, coverage).4. Learn probabilities from these.5. Repeat :-)<jupyter_code>from Coverage import Coverage, cgi_decode
from Grammars import CGI_GRAMMAR
cgi_fuzzer = GrammarFuzzer(CGI_GRAMMAR)

trials = 100
coverage = {}

for i in range(trials):
    cgi_input = cgi_fuzzer.fuzz()
    with Coverage() as cov:
        cgi_decode(cgi_input)
    coverage[cgi_input] = cov.coverage()
coverage_slice = [cgi_input for cgi_input in coverage if (
    'cgi_decode', 25) in coverage[cgi_input]]
print(coverage_slice)
len(coverage_slice) / trials<jupyter_output><empty_output><jupyter_text>Now use this sample for setting probabilities.  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)  BackgroundOur exposition of Benford's law follows [this article](https://brilliant.org/wiki/benfords-law/).  ExercisesClose the chapter with a few exercises such that people have things to do.  In Jupyter Notebook, use the `exercise2` nbextension to add solutions that can be interactively viewed or hidden:* Mark the _last_ cell of the exercise (this should be a _text_ cell) as well as _all_ cells of the solution.  (Use the `rubberband` nbextension and use Shift+Drag to mark multiple cells.)* Click on the `solution` button at the top.(Alternatively, just copy the exercise and solution cells below with their metadata.)  Exercise 1Create a class `ProbabilisticGrammarCoverageFuzzer` that extends `GrammarCoverageFuzzer` with probabilistic capabilities.  The idea is to first cover all uncovered expansions (like `GrammarCoverageFuzzer`) and once all expansions are covered, to proceed by probabilities (like `ProbabilisticGrammarFuzzer`).  To this end, define new instances of the `choose_covered_node_expansion()` and `choose_uncovered_node_expansion()` methods that choose an expansion based on the given weights.  If you are an advanced programmer, realize the class via _multiple inheritance_ from `GrammarCoverageFuzzer` and `ProbabilisticGrammarFuzzer` to achieve this. **Solution**.  With multiple inheritance, this is fairly easy; we just need to point the three methods to the right places:<jupyter_code>class ProbabilisticGrammarCoverageFuzzer(GrammarCoverageFuzzer, ProbabilisticGrammarFuzzer):
    # Choose uncovered expansions first
    def choose_node_expansion(self, node, possible_children):
        return GrammarCoverageFuzzer.choose_node_expansion(self, node, possible_children)

    # Among uncovered expansions, pick by (relative) probability
    def choose_uncovered_node_expansion(self, node, possible_children):
        return ProbabilisticGrammarFuzzer.choose_node_expansion(self, node, possible_children)

    # For covered nodes, pick by probability, too
    def choose_covered_node_expansion(self, node, possible_children):
        return ProbabilisticGrammarFuzzer.choose_node_expansion(self, node, possible_children)<jupyter_output><empty_output><jupyter_text>In the first nine invocations, our fuzzer covers one digit after another:<jupyter_code>cov_leaddigit_fuzzer = ProbabilisticGrammarCoverageFuzzer(
    PROBABILISTIC_EXPR_GRAMMAR, start_symbol="<leaddigit>")
print([cov_leaddigit_fuzzer.fuzz() for i in range(9)])<jupyter_output>['1', '6', '3', '2', '4', '9', '8', '7', '5']<jupyter_text>After these, we again proceed by probabilities:<jupyter_code>trials = 10000

count = {}
for c in crange('0', '9'):
    count[c] = 0

for i in range(trials):
    count[cov_leaddigit_fuzzer.fuzz()] += 1

print([(digit, count[digit] / trials) for digit in count])<jupyter_output>[('0', 0.0), ('1', 0.3008), ('2', 0.1743), ('3', 0.1243), ('4', 0.0965), ('5', 0.0798), ('6', 0.0695), ('7', 0.0619), ('8', 0.0488), ('9', 0.0441)]
{'fraction_non_alphanumeric': 0.10448881059568083, 'fraction_numerical': 0.022248319958243622, 'mean_word_length': 5.332369345176616, 'pattern_counts': {'":': 18, '<': 240, '<?xml version=': 0, '>': 232, 'https://': 6, 'lorem ipsum': 0, 'www.': 8, 'xml': 0}, 'pii_count': 14, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '42', 'dir': 'jupyter-structured-clean-dedup', 'id': '35127', 'license': 'MIT', 'n_tokens_mistral': 10175, 'n_tokens_neox': 9404, 'n_words': 3045, 'path': 'docs/beta/notebooks/ProbabilisticGrammarFuzzer.ipynb', 'repo_name': 'GonzaloCastroO/fuzzingbook', 'size': '30658'}