{ "cells": [ { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "# Getting Coverage\n", "\n", "In the [previous chapter](Fuzzer.ipynb), we introduced _basic fuzzing_ – that is, generating random inputs to test programs. How do we measure the effectiveness of these tests? One way would be to check the number (and seriousness) of bugs found; but if bugs are scarce, we need a _proxy for the likelihood of a test to uncover a bug._ In this chapter, we introduce the concept of *code coverage*, measuring which parts of a program are actually executed during a test run. Measuring such coverage is also crucial for test generators that attempt to cover as much code as possible." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "source": [ "**Prerequisites**\n", "\n", "* You need some understanding of how a program is executed.\n", "* You should have learned about basic fuzzing in the [previous chapter](Fuzzer.ipynb)." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## A CGI Decoder\n", "\n", "We start by introducing a simple Python function that decodes a CGI-encoded string. CGI encoding is used in URLs (i.e., Web addresses) to encode characters that would be invalid in a URL, such as blanks and certain punctuation:\n", "\n", "* Blanks are replaced by `'+'`\n", "* Other invalid characters are replaced by '`%xx`', where `xx` is the two-digit hexadecimal equivalent.\n", "\n", "In CGI encoding, the string `\"Hello, world!\"` would thus become `\"Hello%2c+world%21\"` where `2c` and `21` are the hexadecimal equivalents of `','` and `'!'`, respectively.\n", "\n", "The function `cgi_decode()` takes such an encoded string and decodes it back to its original form. Our implementation replicates the code from \\cite{Pezze2008}. (It even includes its bugs – but we won't reveal them at this point.)" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def cgi_decode(s):\n", " \"\"\"Decode the CGI-encoded string `s`:\n", " * replace \"+\" by \" \"\n", " * replace \"%xx\" by the character with hex number xx.\n", " Return the decoded string. Raise `ValueError` for invalid inputs.\"\"\"\n", "\n", " # Mapping of hex digits to their integer values\n", " hex_values = {\n", " '0': 0, '1': 1, '2': 2, '3': 3, '4': 4,\n", " '5': 5, '6': 6, '7': 7, '8': 8, '9': 9,\n", " 'a': 10, 'b': 11, 'c': 12, 'd': 13, 'e': 14, 'f': 15,\n", " 'A': 10, 'B': 11, 'C': 12, 'D': 13, 'E': 14, 'F': 15,\n", " }\n", "\n", " t = \"\"\n", " i = 0\n", " while i < len(s):\n", " c = s[i]\n", " if c == '+':\n", " t += ' '\n", " elif c == '%':\n", " digit_high, digit_low = s[i + 1], s[i + 2]\n", " i += 2\n", " if digit_high in hex_values and digit_low in hex_values:\n", " v = hex_values[digit_high] * 16 + hex_values[digit_low]\n", " t += chr(v)\n", " else:\n", " raise ValueError(\"Invalid encoding\")\n", " else:\n", " t += c\n", " i += 1\n", " return t\n" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Here is an example of how `cgi_decode()` works:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "'Hello world'" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "cgi_decode(\"Hello+world\")" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "If we want to systematically test `cgi_decode()`, how would we proceed?" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "source": [ "The testing literature distinguishes two ways of deriving tests: _Black-box testing_ and _White-box testing._" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Black-Box Testing\n", "\n", "The idea of *black-box testing* is to derive tests from the _specification_. In the above case, we thus would have to test `cgi_decode()` by the features specified and documented, including\n", "\n", "* testing for correct replacement of `'+'`;\n", "* testing for correct replacement of `\"%xx\"`;\n", "* testing for non-replacement of other characters; and\n", "* testing for recognition of illegal inputs.\n", "\n", "Here are four assertions (tests) that cover these four features. We can see that they all pass:" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "assert cgi_decode('+') == ' '\n", "assert cgi_decode('%20') == ' '\n", "assert cgi_decode('abc') == 'abc'\n", "\n", "try:\n", " cgi_decode('%?a')\n", " assert False\n", "except ValueError:\n", " pass" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "The advantage of black-box testing is that it finds errors in the _specified_ behavior. It is independent from a given implementation, and thus allows to create test even before implementation. The downside is that _implemented_ behavior typically covers more ground than _specified_ behavior, and thus tests based on specification alone typically do not cover all implementation details." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## White-Box Testing\n", "\n", "In contrast to black-box testing, *white-box testing* derives tests from the _implementation_, notably the internal structure. White-Box testing is closely tied to the concept of _covering_ structural features of the code. If a statement in the code is not executed during testing, for instance, this means that an error in this statement cannot be triggered either. White-Box testing thus introduces a number of *coverage criteria* that have to be fulfilled before the test can be said to be sufficient. The most frequently used coverage criteria are\n", "\n", "* *Statement coverage* – each statement in the code must be executed by at least one test input.\n", "* *Branch coverage* – each branch in the code must be taken by at least one test input. (This translates to each `if` and `while` decision once being true, and once being false.)\n", "\n", "Besides these, there are far more coverage criteria, including sequences of branches taken, loop iterations taken (zero, one, many), data flows between variable definitions and usages, and many more; \\cite{Pezze2008} has a great overview." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Let us consider `cgi_decode()`, above, and reason what we have to do such that each statement of the code is executed at least once. We'd have to cover\n", "\n", "* The block following `if c == '+'`\n", "* The two blocks following `if c == '%'` (one for valid input, one for invalid)\n", "* The final `else` case for all other characters.\n", "\n", "This results in the same conditions as with black-box testing, above; again, the assertions above indeed would cover every statement in the code. Such a correspondence is actually pretty common, since programmers tend to implement different behaviors in different code locations; and thus, covering these locations will lead to test cases that cover the different (specified) behaviors.\n", "\n", "The advantage of white-box testing is that it finds errors in _implemented_ behavior. It can be conducted even in cases where the specification does not provide sufficient details; actually, it helps in identifying (and thus specifying) corner cases in the specification. The downside is that it may miss _non-implemented_ behavior: If some specified functionality is missing, white-box testing will not find it." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Tracing Executions\n", "\n", "One nice feature of white-box testing is that one can actually automatically assess whether some program feature was covered. To this end, one _instruments_ the execution of the program such that during execution, a special functionality keeps track of which code was executed. After testing, this information can be passed to the programmer, who can then focus on writing tests that cover the yet uncovered code." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "In most programming languages, it is rather difficult to set up programs such that one can trace their execution. Not so in Python. The function `sys.settrace(f)` allows to define a *tracing function* `f()` that is called for each and every line executed. Even better, it gets access to the current function and its name, current variable contents, and more. It is thus an ideal tool for *dynamic analysis* – that is, the analysis of what actually happens during an execution." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "To illustrate how this works, let us again look into a specific execution of `cgi_decode()`." ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "'a b'" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "cgi_decode(\"a+b\")" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "To track how the execution proceeds through `cgi_decode()`, we make use of `sys.settrace()`. First, we define the _tracing function_ that will be called for each line. It has three parameters: \n", "\n", "* The `frame` parameter gets you the current _frame_, allowing access to the current location and variables:\n", " * `frame.f_code` is the currently executed code with `frame.f_code.co_name` being the function name;\n", " * `frame.f_lineno` holds the current line number; and\n", " * `frame.f_locals` holds the current local variables and arguments.\n", "* The `event` parameter is a string with values including `\"line\"` (a new line has been reached) or `\"call\"` (a function is being called).\n", "* The `arg` parameter is an additional _argument_ for some events; for `\"return\"` events, for instance, `arg` holds the value being returned." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "We use the tracing function for simply reporting the current line executed, which we access through the `frame` argument." ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "coverage = []" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def traceit(frame, event, arg):\n", " if event == \"line\":\n", " global coverage\n", " function_name = frame.f_code.co_name\n", " lineno = frame.f_lineno\n", " coverage.append(lineno)\n", " return traceit" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "We can switch tracing on and off with `sys.settrace()`:" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import sys" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def cgi_decode_traced(s):\n", " global coverage\n", " coverage = []\n", " sys.settrace(traceit) # Turn on\n", " cgi_decode(s)\n", " sys.settrace(None) # Turn off" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "When we compute `cgi_decode(\"a+b\")`, we can now see how the execution progresses through `cgi_decode()`. After the initialization of `hex_values`, `t`, and `i`, we see that the `while` loop is taken three times – one for every character in the input." ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[9, 10, 11, 12, 15, 16, 17, 18, 19, 21, 30, 31, 17, 18, 19, 20, 31, 17, 18, 19, 21, 30, 31, 17, 32]\n" ] } ], "source": [ "cgi_decode_traced(\"a+b\")\n", "print(coverage)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Which lines are these, actually? To this end, we encode the source code into an array `cgi_decode_lines`. (An actual coverage tool could also access the source code file directly.)" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "cgi_decode_code = \"\"\"\n", "def cgi_decode(s):\n", " \\\"\\\"\\\"Decode the CGI-encoded string `s`:\n", " * replace \"+\" by \" \"\n", " * replace \"%xx\" by the character with hex number xx.\n", " Return the decoded string. Raise `ValueError` for invalid inputs.\\\"\\\"\\\"\n", "\n", " # Mapping of hex digits to their integer values\n", " hex_values = {\n", " '0': 0, '1': 1, '2': 2, '3': 3, '4': 4,\n", " '5': 5, '6': 6, '7': 7, '8': 8, '9': 9,\n", " 'a': 10, 'b': 11, 'c': 12, 'd': 13, 'e': 14, 'f': 15,\n", " 'A': 10, 'B': 11, 'C': 12, 'D': 13, 'E': 14, 'F': 15,\n", " }\n", "\n", " t = \"\"\n", " i = 0\n", " while i < len(s):\n", " c = s[i]\n", " if c == '+':\n", " t += ' '\n", " elif c == '%':\n", " digit_high, digit_low = s[i + 1], s[i + 2]\n", " i += 2\n", " if digit_high in hex_values and digit_low in hex_values:\n", " v = hex_values[digit_high] * 16 + hex_values[digit_low]\n", " t += chr(v)\n", " else:\n", " raise ValueError(\"Invalid encoding\")\n", " else:\n", " t += c\n", " i += 1\n", " return t\n", "\"\"\"\n", "cgi_decode_lines = cgi_decode_code.splitlines()" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "We see that the first line (9) executed is actually the initialization of `hex_values`..." ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "[\" '0': 0, '1': 1, '2': 2, '3': 3, '4': 4,\",\n", " \" '5': 5, '6': 6, '7': 7, '8': 8, '9': 9,\",\n", " \" 'a': 10, 'b': 11, 'c': 12, 'd': 13, 'e': 14, 'f': 15,\",\n", " \" 'A': 10, 'B': 11, 'C': 12, 'D': 13, 'E': 14, 'F': 15,\"]" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "cgi_decode_lines[9:13]" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "... followed by the initialization of `t`:" ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "' t = \"\"'" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "cgi_decode_lines[15]" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "To see which lines actually have been covered at least once, we can convert `coverage` into a set:" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{32, 9, 10, 11, 12, 15, 16, 17, 18, 19, 20, 21, 30, 31}\n" ] } ], "source": [ "covered_lines = set(coverage)\n", "print(covered_lines)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Let us print out the code, annotating lines not covered with '#':" ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "# 1 def cgi_decode(s):\n", "# 2 \"\"\"Decode the CGI-encoded string `s`:\n", "# 3 * replace \"+\" by \" \"\n", "# 4 * replace \"%xx\" by the character with hex number xx.\n", "# 5 Return the decoded string. Raise `ValueError` for invalid inputs.\"\"\"\n", "# 6 \n", "# 7 # Mapping of hex digits to their integer values\n", "# 8 hex_values = {\n", " 9 '0': 0, '1': 1, '2': 2, '3': 3, '4': 4,\n", " 10 '5': 5, '6': 6, '7': 7, '8': 8, '9': 9,\n", " 11 'a': 10, 'b': 11, 'c': 12, 'd': 13, 'e': 14, 'f': 15,\n", " 12 'A': 10, 'B': 11, 'C': 12, 'D': 13, 'E': 14, 'F': 15,\n", "# 13 }\n", "# 14 \n", " 15 t = \"\"\n", " 16 i = 0\n", " 17 while i < len(s):\n", " 18 c = s[i]\n", " 19 if c == '+':\n", " 20 t += ' '\n", " 21 elif c == '%':\n", "# 22 digit_high, digit_low = s[i + 1], s[i + 2]\n", "# 23 i += 2\n", "# 24 if digit_high in hex_values and digit_low in hex_values:\n", "# 25 v = hex_values[digit_high] * 16 + hex_values[digit_low]\n", "# 26 t += chr(v)\n", "# 27 else:\n", "# 28 raise ValueError(\"Invalid encoding\")\n", "# 29 else:\n", " 30 t += c\n", " 31 i += 1\n", " 32 return t\n" ] } ], "source": [ "for lineno in range(1, len(cgi_decode_lines)):\n", " if lineno not in covered_lines:\n", " print(\"# \", end=\"\")\n", " else:\n", " print(\" \", end=\"\")\n", " print(\"%2d\" % lineno, cgi_decode_lines[lineno])" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "We see that a number of lines (notably comments) have not been executed, simply because they are not executable. However, we also see that the lines under `if c == '%'` have _not_ been executed yet. If `\"a+b\"` were our only test case so far, this missing coverage would now encourage us to create another test case that actually covers these lines." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## A Coverage Class\n", "\n", "In this book, we will make use of coverage again and again – to _measure_ the effectiveness of different test generation techniques, but also to _guide_ test generation towards code coverage. Our previous implementation with a global `coverage` variable is a bit cumbersome for that. We therefore implement some functionality that will help us measuring coverage easily." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "The key idea of getting coverage is to make use of the Python `with` statement. The general form\n", "\n", "```python\n", "with OBJECT [as VARIABLE]:\n", " BODY\n", "```\n", "\n", "executes `BODY` with `OBJECT` being defined (and stored in `VARIABLE`). The interesting thing is that at the beginning and end of `BODY`, the special methods `OBJECT.__enter__()` and `OBJECT.__exit__()` are automatically invoked; even if `BODY` raises an exception. This allows us to define a `Coverage` object where `Coverage.__enter__()` automatically turns on tracing and `Coverage.__exit__()` automatically turns off tracing again. After tracing, we can make use of special methods to access the coverage. This is what this looks like during usage:\n", "\n", "```python\n", "with Coverage() as cov:\n", " function_to_be_traced()\n", "c = cov.coverage()\n", "```\n", "\n", "Here, tracing is automatically turned on during `function_to_be_traced()` and turned off again after the `with` block; afterwards, we can access the set of lines executed." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Here's the full implementation with all its bells and whistles. You don't have to get everything; it suffices that you know how to use it:" ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class Coverage(object):\n", " # Trace function\n", " def traceit(self, frame, event, arg):\n", " if self.original_trace_function is not None:\n", " self.original_trace_function(frame, event, arg)\n", "\n", " if event == \"line\":\n", " function_name = frame.f_code.co_name\n", " lineno = frame.f_lineno\n", " self._trace.append((function_name, lineno))\n", "\n", " return self.traceit\n", "\n", " def __init__(self):\n", " self._trace = []\n", "\n", " # Start of `with` block\n", " def __enter__(self):\n", " self.original_trace_function = sys.gettrace()\n", " sys.settrace(self.traceit)\n", " return self\n", "\n", " # End of `with` block\n", " def __exit__(self, exc_type, exc_value, tb):\n", " sys.settrace(self.original_trace_function)\n", "\n", " def trace(self):\n", " \"\"\"The list of executed lines, as (function_name, line_number) pairs\"\"\"\n", " return self._trace\n", "\n", " def coverage(self):\n", " \"\"\"The set of executed lines, as (function_name, line_number) pairs\"\"\"\n", " return set(self.trace())" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Let us put this to use:" ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{('cgi_decode', 11), ('cgi_decode', 17), ('cgi_decode', 10), ('cgi_decode', 31), ('cgi_decode', 16), ('cgi_decode', 30), ('cgi_decode', 19), ('cgi_decode', 18), ('cgi_decode', 12), ('__exit__', 25), ('cgi_decode', 15), ('cgi_decode', 32), ('cgi_decode', 21), ('cgi_decode', 20), ('cgi_decode', 9)}\n" ] } ], "source": [ "with Coverage() as cov:\n", " cgi_decode(\"a+b\")\n", "\n", "print(cov.coverage())" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "As you can see, the `Coverage()` class not only keeps track of lines executed, but also of function names. This is useful if you have a program that spans multiple files." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Comparing Coverage\n", "\n", "Since we represent coverage as a set of executed lines, we can also apply _set operations_ on these. For instance, we can find out which lines are covered by individual test cases, but not others:" ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "{('cgi_decode', 20)}" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "with Coverage() as cov_plus:\n", " cgi_decode(\"a+b\")\n", "with Coverage() as cov_standard:\n", " cgi_decode(\"abc\")\n", "\n", "cov_plus.coverage() - cov_standard.coverage()" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "This is the single line in the code that is executed only in the `'a+b'` input." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "We can also compare sets to find out which lines still need to be covered. Let us define `cov_max` as the maximum coverage we can achieve. (Here, we do this by executing the \"good\" test cases we already have. In practice, one would statically analyze code structure, which we introduce in [the chapter on symbolic testing](SymbolicFuzzer.ipynb).)" ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import fuzzingbook_utils" ] }, { "cell_type": "code", "execution_count": 19, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "with Coverage() as cov_max:\n", " cgi_decode('+')\n", " cgi_decode('%20')\n", " cgi_decode('abc')\n", " try:\n", " cgi_decode('%?a')\n", " except:\n", " pass" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "Then, we can easily see which lines are _not_ yet covered by a test case:" ] }, { "cell_type": "code", "execution_count": 20, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "{('cgi_decode', 22),\n", " ('cgi_decode', 23),\n", " ('cgi_decode', 24),\n", " ('cgi_decode', 25),\n", " ('cgi_decode', 26),\n", " ('cgi_decode', 28)}" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "cov_max.coverage() - cov_plus.coverage()" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "Again, these would be the lines handling `\"%xx\"`, which we have not yet had in the input." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Coverage of Basic Fuzzing\n", "\n", "We can now use our coverage tracing to assess the _effectiveness_ of testing methods – in particular, of course, test _generation_ methods. Our challenge is to achieve maximum coverage in `cgi_decode()` just with random inputs. In principle, we should _eventually_ get there, as eventually, we will have produced every possible string in the universe – but exactly how long is this? To this end, let us run just one fuzzing iteration on `cgi_decode()`:" ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from Fuzzer import fuzzer" ] }, { "cell_type": "code", "execution_count": 22, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "'!7#%\"*#0=)$;%6*;>638:*>80\"=(/*:-(2<4 !:5*6856&?\"\"11<7+%<%7,4.8,*+&,,$,.\"'" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sample = fuzzer()\n", "sample" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Here's the invocation and the coverage we achieve. We wrap `cgi_decode()` in a `try...except` block such that we can ignore `ValueError` exceptions raised by illegal `%xx` formats." ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "{('__exit__', 25),\n", " ('cgi_decode', 9),\n", " ('cgi_decode', 10),\n", " ('cgi_decode', 11),\n", " ('cgi_decode', 12),\n", " ('cgi_decode', 15),\n", " ('cgi_decode', 16),\n", " ('cgi_decode', 17),\n", " ('cgi_decode', 18),\n", " ('cgi_decode', 19),\n", " ('cgi_decode', 21),\n", " ('cgi_decode', 22),\n", " ('cgi_decode', 23),\n", " ('cgi_decode', 24),\n", " ('cgi_decode', 28),\n", " ('cgi_decode', 30),\n", " ('cgi_decode', 31)}" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "with Coverage() as cov_fuzz:\n", " try:\n", " cgi_decode(sample)\n", " except:\n", " pass\n", "cov_fuzz.coverage()" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Is this already the maximum coverage? Apparently, there are still lines missing:" ] }, { "cell_type": "code", "execution_count": 24, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "{('cgi_decode', 20),\n", " ('cgi_decode', 25),\n", " ('cgi_decode', 26),\n", " ('cgi_decode', 32)}" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "cov_max.coverage() - cov_fuzz.coverage()" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Let us try again, increasing coverage over 100 random inputs. We use an array `cumulative_coverage` to store the coverage achieved over time; `cumulative_coverage[0]` is the total number of lines covered after input 1, \n", "`cumulative_coverage[1]` is the number of lines covered after inputs 1–2, and so on." ] }, { "cell_type": "code", "execution_count": 25, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "trials = 100" ] }, { "cell_type": "code", "execution_count": 26, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def population_coverage(population, function):\n", " cumulative_coverage = []\n", " all_coverage = set()\n", "\n", " for s in population:\n", " with Coverage() as cov:\n", " try:\n", " function(s)\n", " except:\n", " pass\n", " all_coverage |= cov.coverage()\n", " cumulative_coverage.append(len(all_coverage))\n", "\n", " return all_coverage, cumulative_coverage" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Let us create a hundred inputs to determine how coverage increases:" ] }, { "cell_type": "code", "execution_count": 27, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def hundred_inputs():\n", " population = []\n", " for i in range(trials):\n", " population.append(fuzzer())\n", " return population" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Here's how the coverage increases with each input:" ] }, { "cell_type": "code", "execution_count": 28, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "all_coverage, cumulative_coverage = population_coverage(\n", " hundred_inputs(), cgi_decode)" ] }, { "cell_type": "code", "execution_count": 29, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "%matplotlib inline" ] }, { "cell_type": "code", "execution_count": 30, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import matplotlib.pyplot as plt" ] }, { "cell_type": "code", "execution_count": 31, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "Text(0,0.5,'lines covered')" ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" }, { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYwAAAEWCAYAAAB1xKBvAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4zLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvIxREBQAAIABJREFUeJzt3XmcXFWd9/HPNwkJkIQ1gSEhMYKIxIUgLbKoMIgIEQWdQRZxosJkdHAEx9FhfBxQ3HAZBn25MHkgBpWJMICKyog8yCIKSFhkMSDIGgMkrB0gabrTv+ePcyq5aaqqb5Kurq6q7/v16lfX3c+tW3V+dc659xxFBGZmZoMZ1ewEmJlZa3DAMDOzUhwwzMysFAcMMzMrxQHDzMxKccAwM7NSHDCsYSS9W9Ijkp6TtMcQ7vcuSQes5zYHSFoyVGkoeczPSvrheqz/D5LOyq+3l7RY0rghSMf/SppTZ/kCSV/Y2OMMFUlXSzphGI7zaUnnNPo47cQBYwhJOlbSopxBPpq/qG9qdrqa6OvARyNiQkTcOlQ7jYhXR8TVQ7W/kUDSWOAzwNcAIuJx4Cpg7sbuOyIOjYjz8nE+IOm6jd1nO4iIL0XEcASmYf+x0igOGENE0j8DZwFfArYHpgPfAQ4fxjRI0ki6pi8D7mp2IlrE4cDdEfGXwrzzgX9oUnpKkTSm2Wmw4TOSMpeWJWlL4HTgxIi4JCKej4jeiPhZRHwyrzNO0lmSlua/syrVDbnq4bDC/sZIekLS6/P03pJ+J+kZSX8oVsfk4vsXJf0WeAHYSdIH8z5XSLpf0jqZjqRP5RLQUkknSApJryik8+uSHpb0uKSzJW1W47xHSfqMpIckLZP0fUlb5n08B4wG/iDpzzW2f7WkKyQ9lY/16Tx/M0nnSXo6n8enir/QJD0o6aBBrslmuarlaUl/BN4wYPkUSRdLWi7pAUkfKywbnasr/pzfw5slTcvL9pV0k6Rn8/99C9u9XNI1eZsrgEkDjlnzOgKHAtcMOI0bSdfzZVXO7+V5P6Py9DmSlhWW/1DSyfn11fk67wacDeyTS8HPFHa5taRf5LTfKGnnGu/rjPx5OV7Sw8Cv8/z/kfRYfl+ulfTqwjYLJH271v4lvU3S3XnbbwEqLKv6GRuQlg8qVX0+LenDkt4g6fb8/nyr2nnk7ddUGRb2NSd/9p+Q9H8GrHuRpAvyOdwiaffC8jXfocI5f0HSeOB/gSn5PX8uf/b2UqqN6M6f/TNrpXNEiQj/beQfcAjQB4yps87pwA3AdsBk4HfA5/OyU4HzC+u+g/RrE2Aq8CQwmxTg35anJ+flVwMPA68GxgCb5O13Jn3x9icFktcX0vpYXn9z4AdAAK/Iy88CLgW2ASYCPwO+XOOcPgTcB+wETAAuAX5QWL5mv1W2nQg8CnwC2DRPvzEvO4OUeW4N7AjcDiwpbPsgcNAg1+QM4Df5PKYBd1b2kd/Hm/P7Pjan/37g7Xn5J4E7gF3ze7g7sG3e19PA+/N7fUye3jZvdz1wJjAOeAuwAvhhyet4E3BklfO4HXhXjXN8GNgzv74nn8NuhWV7FD4jJ+TXHwCuG7CfBcBTwF75vM4HflTjmDPydf0+MB7YrPBZmJjP/SzgtjL7JwXVbuBvSZ/dj5O+SycU9lv1M1ZIy9mkz9DBwCrgJ6Tv2VRgGbB/jXP5bOH6VPb1f4HN8jXvKbyfnwV6C+n8F+ABYJNqn/V8zl/Irw+g8PktfFben19PAPZudj5WKq9rdgLa4Q94H/DYIOv8GZhdmH478GB+/QpS5rJ5nj4fODW//lcKmXCedzkwJ7++Gjh9kGP/BDgpv55PIQDkY0f+L+B5YOfC8n2AB2rs90rgHwvTu+Yv1Zg8XS9gHAPcWmPZmsw7T5/A+geM+4FDCtNzWRsw3gg8PGD9fwO+l1/fAxxeZZ/vB34/YN71pEx4OimjG19Y9t+FDGmw63hvMb2FdX4L/F2Nc/wB8M/AX+U0fxX4MPBy4BlgVOEzMljAOKcwPZv8g6XKMWfk67pTnfd+q7zOloPtH/g74IbCMgFLCumt+RkrpGVqYfmTwFGF6YuBk2uk87O8NGDsWFj+e+DowrrFdI4i/eB5c7XPOoMHjGuBzwGT6n2OR9qfq6SGxpPAJNWvz50CPFSYfijPIyLuAxYD75S0OfAuUmYDqR3gyFy8fiZXI7wJ2KGwr0eKB5J0qKQblKp6niF9QSvVI1MGrF98PZlU6ri5cKxf5vllz2kMqQ1nMNNIQbTWfmulsayB+yim82WkKoLie/pp1qa7VtoGnm9lv1Pzsqcj4vk6x6x3HZ8m/UIfaCIp86/mGlJm9BZSBnQ1qUS5P/CbiOivsV01jxVev0D61VvPmvc2V+GdkavwukkBHdatkqu1/3WuU6TctHjdynzGHi+8XlllerBzKar3PhTT2U8KbFPWY99FxwOvBO7OVZuHDbbBSOCAMTSuJxWFj6izzlJSplExPc+rWEj61X048MccRCB9SH8QEVsV/sZHxBmFbdd0OazULnIx6Q6l7SNiK+Ay1tYLP0qq5qmYVnj9BOkL9urCsbaMiFpfuGrn1Me6X9haHiFVm1VTL41lPTpgu+kDjv3AgPd0YkTMHiRtA8+3st+/5ONtneusax2z3nW8nZSBrJF/gLwC+EONc7wGeDMpaFwDXAfsRwoYA9tDKoaqe+rifo4lfW4PArYk/VqHQltEHetcJ0li3eu2MZ+xoVZM5yjSZ7TyHX6B9GOr4q8Kr1/ynkfEvRFxDKnq7CvARQM+OyOSA8YQiIhnSfXh35Z0hKTNJW2Sf+l/Na+2EPiMpMmSJuX1i/fo/4hUB/sR1pYuyOu8U9Lb8y+5TZVu0ytmqEVjSfXIy4E+SYfm/VZcCHxQ0m65NHNq4Tz6SXW4/ylpOwBJUyW9vcaxFgIfV2qAnUC6Q+yCiOir935lPwf+StLJSo3kEyW9sZDGf5O0taSpwEdL7G+g4j52BP6psOz3QLekf1VqHB8t6TWSKg3j5wCfl7SLktdJ2pYUeF+pdPv0GElHATOBn0fEQ8Ai4HOSxirdTv3OwjEHu46XkTL6or1I1ZYDSzVAynRIAf444NqI6CZlpH9D7YDxOLCj0m28Q2Uiqb7/SVKm+aX12PYXwKslvScHyI+xbma7MZ+xobZnIZ0nk875hrzsNuDYfG0PYd1r+TiwrXJjPYCk4yRNzt+5SglydeNPYeM4YAyRiDiTVJ/8GVJm/Qgpo/tJXuULpAzldlKD6i15XmX7R0kllX2BCwrzHyH9evt0Yb+fpMa1i4gVpC/dhaRqjmNJjdiV5f8LfJN0j/99+ZiQPvyQ6trvA27I1Qv/j1RvXM18Uj36taQGwFWsmzHXlNP5NlKm+hipDv+v8+LTScX9B/LxLyqkr6zPkaovHgB+ldNZOfbqfNxZefkTpCBR+UKfSXr/fkVqkD2X1Lj7JHAYqaH+SeBTwGER8UTe7lhS+8hTwGmkhuHKMQe7jj8DXiWpWMXxPlKDbj3XAE9GxMOFaQG1nnv5NelW58ckPVFjnfX1fdJ7/Rfgj6zNRAeV37sjSTcpPAnsQmq3qdjgz1gD/BQ4irU3PrwnInrzspNIn6lnSNet8r0nIu4mBb77c3XkFNLNJ3cp3U34DVJbyaphO5MNpNwAYx1K6VbLO4FxTfrVNihJHyF9oQb+Am8rkuYCMyPi5FzCu4Z0p9OIz0janaTPkhq1j2t2WprJD910IEnvJlUFjCfVn/5sJAULSTuQbqO8nvSL8xNAzfvp20VEzCu8Xgbs1sTkmL2Eq6Q60z+QqkX+TKo3/Uhzk/MSY4H/It1q/GtSVcB3Bq6k1PXKc1X+Pj3M6TXrCK6SMjOzUlzCMDOzUtqqDWPSpEkxY8aMZifDzKxl3HzzzU9ERK2Hc9fRVgFjxowZLFq0qNnJMDNrGZKqPudTjaukzMysFAcMMzMrxQHDzMxKccAwM7NSHDDMzKyUhgUMSdMkXaU0xOZdkk7K84/M0/2Suupsf4ikeyTdJ+mURqXTzMzKaWQJow/4RETsBuwNnChpJqmju/eQep+sStJo4NukcY5nAsfkbc3MrEka9hxG7q770fx6haTFpKEUrwBI46TUtBdwX0Tcn9f9EXlgoUaltxn6Vvfzvd8+yIpVvYOvbGZWw+bjxvDh/WuNRzZ0huXBPUkzgD2AG0tuMpV1h2lcQhpnoNq+55LGa2b69OnVVhmx7vjLs3zxssUA1I+fZma1TZowrj0CRh4lqzIQe3fZzarMq9pLYu4Seh5AV1dXS/WkuLI3DbD1o7l7s/dO2zY5NWZm9TX0LilJm5CCxfkRccl6bLqEdcf1LY6d2zZ6+voBGDfGN6uZ2cjXyLukRBracnEevnR93ATsksfxHQscTWGY0XbR05sCxlgHDDNrAY3MqfYjjXt7oKTb8t9sSe+WtATYB/iFpMsBJE2RdBlAHv3to8DlwGLgwoi4q4FpbYqevlQlNW7M6CanxMxscI28S+o6qrdFAPy4yvpLgdmF6cuAyxqTupHBVVJm1kqcUzXRmoCxiS+DmY18zqmaqKfXVVJm1jocMJrIVVJm1kqcUzXRiw4YZtZCnFM1UU9fP2PHjBqsmxQzsxHBAaOJevpWu3RhZi3DuVUT9fT1u8HbzFqGA0YT9fT2u4RhZi3DuVUT9fSt9jMYZtYynFs1kaukzKyVOGA0UQoYvgRm1hqcWzVRT6/vkjKz1uHcqol6+voZt4mrpMysNThgNJGrpMyslTi3aiI/uGdmrcS5VROl5zBcJWVmraGRQ7ROk3SVpMWS7pJ0Up6/jaQrJN2b/29dY/vVhZH62m54Vqi0YThmm1lraGRu1Qd8IiJ2A/YGTpQ0EzgFuDIidgGuzNPVrIyIWfnvXQ1MZ9O4SsrMWknDcquIeDQibsmvV5DG5p4KHA6cl1c7DziiUWkY6fzgnpm1kmH5eStpBrAHcCOwfUQ8CimoANvV2GxTSYsk3SCpZlCRNDevt2j58uVDnPLGiQhe9F1SZtZCGp5bSZoAXAycHBHd67Hp9IjoAo4FzpK0c7WVImJeRHRFRNfkyZOHIMXDw+N5m1mraWhuJWkTUrA4PyIuybMfl7RDXr4DsKzathGxNP+/H7iaVEJpG2uHZ3WVlJm1hkbeJSXgXGBxRJxZWHQpMCe/ngP8tMq2W0sal19PAvYD/tiotDZDT99qwMOzmlnraGRutR/wfuDAwu2xs4EzgLdJuhd4W55GUpekc/K2uwGLJP0BuAo4IyLaK2D0ejxvM2stYxq144i4Dqg1WPVbq6y/CDghv/4d8NpGpW0kWNuG4SopM2sN/nnbJK6SMrNW49yqSdY2evsSmFlrcG7VJGvbMFwlZWatwQGjSdZUSfk5DDNrEc6tmsRVUmbWapxbNYkf3DOzVuOA0SQ9vb5Lysxai3OrJnGVlJm1GudWTeIqKTNrNQ4YTeK7pMys1Ti3apLKcxhjR/sSmFlrcG7VJD19/YwdPYpRo2p1t2VmNrI4YDSJR9szs1bjHKtJevpWu/3CzFqKc6wm6enr9x1SZtZSHDCapMdVUmbWYho5ROs0SVdJWizpLkkn5fnbSLpC0r35/9Y1tp+T17lX0pxq67Synt7VjHXAMLMW0sgcqw/4RETsBuwNnChpJnAKcGVE7AJcmafXIWkb4DTgjcBewGm1Akur6unr92h7ZtZSGhYwIuLRiLglv14BLAamAocD5+XVzgOOqLL524ErIuKpiHgauAI4pFFpbYaevtWukjKzljIsOZakGcAewI3A9hHxKKSgAmxXZZOpwCOF6SV5XrV9z5W0SNKi5cuXD2WyG8ptGGbWahqeY0maAFwMnBwR3WU3qzIvqq0YEfMioisiuiZPnryhyRx2Pb2+S8rMWktDA4akTUjB4vyIuCTPflzSDnn5DsCyKpsuAaYVpncEljYyrcPNz2GYWatp5F1SAs4FFkfEmYVFlwKVu57mAD+tsvnlwMGSts6N3QfneW3DVVJm1moamWPtB7wfOFDSbflvNnAG8DZJ9wJvy9NI6pJ0DkBEPAV8Hrgp/52e57UNP7hnZq1mTKN2HBHXUb0tAuCtVdZfBJxQmJ4PzG9M6pqvp9d3SZlZa3GO1STpOQy//WbWOpxjNUFEuErKzFqOA0YTvLja43mbWetxjtUEa8fz9ttvZq3DOVYTVIZndV9SZtZKHDCaoKdvNeAShpm1FudYTeAqKTNrRc6xmmBNlZTvkjKzFuKA0QRrqqT8HIaZtRDnWE3gKikza0XOsZpgbcBwlZSZtQ4HjCbo6fVdUmbWemp2PijpDmoMWgQQEa9rSIo6QKWEsanbMMyshdTrrfaw/P/E/P8H+f/7gBcalqIO4CopM2tFNQNGRDwEIGm/iNivsOgUSb8FTm904tqVH9wzs1ZUJscaL+lNlQlJ+wLjB9tI0nxJyyTdWZi3u6TrJd0h6WeStqix7YN5ndskLSpzIq2k8hzGWAcMM2shZXKs44Fv50z8AeA7wIdKbLcAOGTAvHOAUyLitcCPgU/W2f6vI2JWRHSVOFZLcZWUmbWiQUfci4ibgd1zaUAR8WyZHUfEtZJmDJi9K3Btfn0FaZzufy+d2jZRqZJyCcPMWsmgOZak7SWdC1wQEc9Kminp+A083p3Au/LrI4FpNdYL4FeSbpY0d5D0zZW0SNKi5cuXb2CyhldPXz+bjBajR9UawdbMbOQp8xN3AakkMCVP/wk4eQOP9yHgREk3AxOBF2ust19EvB44NK//llo7jIh5EdEVEV2TJ0/ewGQNr55ej7ZnZq2nTMCYFBEXAv0AEdEHrN6Qg0XE3RFxcETsCSwE/lxjvaX5/zJSW8deG3K8kaqnb7XvkDKzllMm13pe0rbkh/gk7Q2UascYSNJ2+f8o4DPA2VXWGS9pYuU1cDCpKqttvNjX74BhZi1n0EZv4J+BS4Gd8/MXk4G/HWwjSQuBA4BJkpYApwETJFUeBLwE+F5edwpwTkTMBrYHfiypkr7/johfrs9JjXQ9ff0ebc/MWk7dgJFLApsC+5PucBJwT0T0DrbjiDimxqJvVFl3KTA7v74f2H2w/bcyV0mZWSuqGzAiol/Sf0TEPsBdw5SmttfjKikza0Flcq1fSfob5Toi23i+S8rMWlHZNozxwGpJK0nVUhERVbv1sMH19K1m/Lgyb72Z2chR5knvicORkE7S09fPNuNdJWVmraXMk96SdJykf8/T0yS11XMRwy21YbhKysxaS5mfud8B9gGOzdPPAd9uWIo6gO+SMrNWVKYi/Y0R8XpJtwJExNOSxjY4XW2tp7efcR5tz8xaTJlcq1fSaNY+6T2Z3E2IbRhXSZlZKyoTML5J6s9pO0lfBK4DvtTQVLU5V0mZWSsqc5fU+bl32beSbqk9IiIWNzxlbSoi/OCembWkQQOGpG+QxsJwQ/cQ6F0dROC+pMys5ZT5mXsL8BlJ90n6mqS2GzJ1OFVG23MJw8xazaC5VkScl3uR3Ys0eNJXJN3b8JS1qbXjeTtgmFlrWZ9c6xXAq4AZwN0NSU0HWBswXCVlZq2lzJPelRLF6aQea/eMiHc2PGVtqqc3V0n5OQwzazFlHtx7ANgnIp5odGI6gaukzKxVlWnDOBvYV9LX81+p0oWk+ZKWSbqzMG93SddLukPSzyRV7fFW0iGS7skN7aeUPpsW4CopM2tVZaqkvgycBPwx/30szxvMAuCQAfPOAU6JiNeSHgb8ZJXjjSb1VXUoMBM4RtLMEsdrCWuqpFzCMLMWU6ZK6h3ArIjoB5B0HnAr8G/1NoqIayXNGDB7V+Da/PoK4HLg3wessxdwXx6qFUk/Ag4nBaum+cXtj/Lz25du9H6efO5FwG0YZtZ6yo7isxXwVH695UYc707gXcBPgSOBaVXWmQo8UpheAryx1g4lzQXmAkyfPn0jklbfgt89wF1Lu9lx6802el97vmxrdpo0YQhSZWY2fMoEjC8Dt0q6itQ1yFsYpHRRx4eAb0o6FbgUeLHKOtWGgo1aO4yIecA8gK6urprrbazulX28eZdJ/Nf7/dyimXWmMn1JLZR0NfAGUmb+rxHx2IYcLCLuBg4GkPRKUnXXQEtYt+SxI7DxdUEbqXtVL1tsukmzk2Fm1jRlGr3fDbwQEZdGxE+BVZKO2JCDSdou/x8FfAY4u8pqNwG7SHp5HnfjaFJppKm6V/ayxWYOGGbWucq0vJ4WEc9WJiLiGeC0wTaStBC4HthV0hJJx5PuePoT6UnxpcD38rpTJF2W998HfJTUIL4YuDAi7lq/0xpafav7ef7F1S5hmFlHK9OGUS2olKnKOqbGom9UWXcpMLswfRlwWYm0DYsVq/oA2GKzsvcImJm1nzIljEWSzpS0s6SdJP0ncHOjEzaSdK/qBXAJw8w6WpmA8U+ku5kuAC4EVgInNjJRI83aEoYDhpl1rjJVS88DbdU9x/rqXlkpYbhKysw6lx83LmFNlZRLGGbWwRwwSuhe6SopMzMHjBIqJYyJrpIysw5W5sG9r0raQtImkq6U9ISk44YjcSNF98peJJgw1gHDzDpXmRLGwRHRDRxG6rbjlVTplrydda/qY+K4MYwaVa2bKzOzzlAmYFQq7mcDCyPiqXortyN3C2JmVu5J759Jupv0/MU/SpoMrGpsskYWdzxoZlZuiNZTgH2ArojoBV4gDWjUMbpX9rlbEDPreGUavTcnPdn93TxrCtBRg0K4hGFmVq4N43ukrkH2zdNLgC80LEUjkNswzMzKBYydI+KrQC9ARKyk+qh4bat7VZ9LGGbW8coEjBclbUYeJlXSzkBPQ1M1gqzuD57rcRuGmVmZXPA04JfANEnnA/sBH2hkokaS5yo91bqEYWYdrkxvtVdIugXYm1QVdVJEPDHYdpLmkx72WxYRr8nzZpGGZd0U6AP+MSJ+X2Xb1cAdefLhiHhXyfMZcu540MwsKduX1KbA00A3MFPSW0psswA4ZMC8rwKfi4hZwKl5upqVETEr/zUtWAA8667NzcyAEiUMSV8BjgLuAvrz7ACurbddRFwracbA2cAW+fWWpHG9RzSXMMzMkjI/m48Ado2IoWjoPhm4XNLXSaWbfWust6mkRaRqqzMi4ie1dihpLjAXYPr06UOQxHVVujZ3T7Vm1unKVEndz9r+pDbWR4CPR8Q04OPAuTXWmx4RXcCxwFn5zqyqImJeRHRFRNfkyZOHKJlreTxvM7OkzM/mF4DbJF1J4XbaiPjYBhxvDnBSfv0/wDnVVoqIpfn//ZKuBvYA/rwBx9toa4ZndZWUmXW4MgHj0vw3FJYC+wNXAwcC9w5cQdLWwAsR0SNpEuk23lqN4w3XvaoPCSaOc5WUmXW2MrfVnrchO5a0EDgAmCRpCel5jr8HviFpDKnH27l53S7gwxFxArAb8F+S+klVZmdExB83JA1DoXtlLxM8FoaZWe2AIenCiHivpDvIT3kXRcTr6u04Io6psWjPKusuAk7Ir38HvLbevoeTOx40M0vqlTAqbQ2HDUdCRqrUtbkDhplZzYAREY/m/w8NX3JGnlTCcPuFmVm9KqkVVKmKInUPEhGxRZVlbad7ZS/Tttm82ckwM2u6eiWMicOZkJFqhbs2NzMDyvcl1bG6V/W6a3MzMxww6uqvjIXhEoaZmQNGPSt6+ojwU95mZuCAUVe3uzY3M1vDAaOOSseDE10lZWbmgFFPpWtzN3qbmTlg1OWuzc3M1nLAqKPShrGlG73NzBww6ulelaukXMIwM3PAqKdSwpjgu6TMzBww6ule1cvEcWMY7bEwzMwaGzAkzZe0TNKdhXmzJN0g6TZJiyTtVWPbOZLuzX9zGpnOWty1uZnZWo0uYSwADhkw76vA5yJiFnAqVYZflbQNaYS+NwJ7AafloVuHVfeqXia6OsrMDCg3pvcGi4hrJc0YOBuodI2+JWmc74HeDlwREU8BSLqCFHgWNialay19ZiUPPfkCAH95eqVLGGZmWTN+Pp8MXC7p66QSzr5V1pkKPFKYXpLnvYSkueSxwadPn77RiTvu3Bu5f/nza6bfufuUjd6nmVk7aEbA+Ajw8Yi4WNJ7gXOBgwasU62VudpgTkTEPGAeQFdXV9V11sfjz67iHa/dgeP2fhkAM6d0xDhRZmaDasZdUnOAS/Lr/yG1UQy0BJhWmN6R6lVXQ6pvdT/Pv7iaXbafwD47b8s+O2/rh/bMzLJmBIylwP759YHAvVXWuRw4WNLWubH74DyvoVb4QT0zs5oaWiUlaSFwADBJ0hLSnU9/D3xD0hhgFbn9QVIX8OGIOCEinpL0eeCmvKvTKw3gjbSm7yiXKszMXqLRd0kdU2PRnlXWXQScUJieD8xvUNKqWtM7rW+lNTN7CT/pXeAShplZbQ4YBWtH2HPAMDMbyAGjYG0Jw1VSZmYDOWAUrLlLylVSZmYv4YBR0L2yFwkmjHUJw8xsIAeMgu5VfUwcN4ZR7s7czOwlHDAKulf2ujrKzKwGB4yC7lW9vkPKzKwGB4yCNGCS2y/MzKpxwChIAya5hGFmVo0DRkH3SldJmZnV4oBR0L3KVVJmZrU4YGR9q/t5rqfPJQwzsxocMLLnevyUt5lZPQ4Y2drBk1wlZWZWjQNG9uxKd21uZlZPw35OS5oPHAYsi4jX5HkXALvmVbYCnomIWVW2fRBYAawG+iKiq1HprFjTU63bMMzMqmpk/csC4FvA9yszIuKoymtJ/wE8W2f7v46IJxqWugHWjLbnu6TMzKpqWO4YEddKmlFtmSQB7wUObNTx15dLGGZm9TWrDePNwOMRcW+N5QH8StLNkubW25GkuZIWSVq0fPnyDU5Qt9swzMzqalbAOAZYWGf5fhHxeuBQ4ERJb6m1YkTMi4iuiOiaPHnyBieoe1UfEkwc5yopM7Nqhj1gSBoDvAe4oNY6EbE0/18G/BjYq9Hp6l7ZywSPhWFmVlMzShgHAXdHxJJqCyWNlzSx8ho4GLiz0Yly1+ZmZvU1LGBIWghcD+wqaYmk4/OioxlQHSVpiqTL8uT2wHWS/gD8HvhFRPyyUemsSF2bO2CYmdXSyLukjqkx/wNV5i0FZufX9wO7NypdtaSuzd1+YWZWi5/0zlascseDZmb1OGBkaTxvlzBFtOKrAAAIbUlEQVTMzGpxwMjc6G1mVp8DBtDfH2ksDDd6m5nV5IABrOjpI8Jdm5uZ1eOAgbsFMTMrwwEDdzxoZlaGAwbu2tzMrAwHDFzCMDMrwwGDtW0YW7oNw8ysJgcMUtfm4BKGmVk9DhjAilwlNcG31ZqZ1eSAQWr0njhuDKM9FoaZWU0OGORuQdx+YWZWlwMGqdHbXZubmdXngIE7HjQzK6ORI+7Nl7RM0p2FeRdIui3/PSjpthrbHiLpHkn3STqlUWmsSKPtuYRhZlZPI0sYC4BDijMi4qiImBURs4CLgUsGbiRpNPBt4FBgJnCMpJkNTKdLGGZmJTQsYETEtcBT1ZZJEvBeBoztne0F3BcR90fEi8CPgMMblU6oDJ7kgGFmVk+z2jDeDDweEfdWWTYVeKQwvSTPq0rSXEmLJC1avnz5BiXmwFdtx+t23HKDtjUz6xTNqrg/huqlC4BqD0NErR1FxDxgHkBXV1fN9eo56+g9NmQzM7OOMuwBQ9IY4D3AnjVWWQJMK0zvCCxtdLrMzKy+ZlRJHQTcHRFLaiy/CdhF0ssljQWOBi4dttSZmVlVjbytdiFwPbCrpCWSjs+LjmZAdZSkKZIuA4iIPuCjwOXAYuDCiLirUek0M7NyFLFB1f4jUldXVyxatKjZyTAzaxmSbo6IrjLr+klvMzMrxQHDzMxKccAwM7NSHDDMzKyUtmr0lrQceGgDN58EPDGEyWkFnXjO0Jnn3YnnDJ153ut7zi+LiMllVmyrgLExJC0qe6dAu+jEc4bOPO9OPGfozPNu5Dm7SsrMzEpxwDAzs1IcMNaa1+wENEEnnjN05nl34jlDZ553w87ZbRhmZlaKSxhmZlaKA4aZmZXS8QFD0iGS7pF0n6RTmp2eRpE0TdJVkhZLukvSSXn+NpKukHRv/r91s9M61CSNlnSrpJ/n6ZdLujGf8wW5G/22ImkrSRdJujtf833a/VpL+nj+bN8paaGkTdvxWkuaL2mZpDsL86peWyXfzPnb7ZJevzHH7uiAIWk08G3gUGAmcIykmc1NVcP0AZ+IiN2AvYET87meAlwZEbsAV+bpdnMSqav8iq8A/5nP+Wng+KpbtbZvAL+MiFcBu5POv22vtaSpwMeAroh4DTCaNJRCO17rBcAhA+bVuraHArvkv7nAdzfmwB0dMIC9gPsi4v6IeBH4EXB4k9PUEBHxaETckl+vIGUgU0nne15e7TzgiOaksDEk7Qi8AzgnTws4ELgor9KO57wF8BbgXICIeDEinqHNrzVpBNHN8qiemwOP0obXOiKuBZ4aMLvWtT0c+H4kNwBbSdphQ4/d6QFjKvBIYXpJntfWJM0A9gBuBLaPiEchBRVgu+alrCHOAj4F9OfpbYFn8kBd0J7XfCdgOfC9XBV3jqTxtPG1joi/AF8HHiYFimeBm2n/a11R69oOaR7X6QFDVea19X3GkiYAFwMnR0R3s9PTSJIOA5ZFxM3F2VVWbbdrPgZ4PfDdiNgDeJ42qn6qJtfZHw68HJgCjCdVxwzUbtd6MEP6ee/0gLEEmFaY3hFY2qS0NJykTUjB4vyIuCTPfrxSRM3/lzUrfQ2wH/AuSQ+SqhsPJJU4tsrVFtCe13wJsCQibszTF5ECSDtf64OAByJieUT0ApcA+9L+17qi1rUd0jyu0wPGTcAu+U6KsaRGskubnKaGyHX35wKLI+LMwqJLgTn59Rzgp8OdtkaJiH+LiB0jYgbp2v46It4HXAX8bV6trc4ZICIeAx6RtGue9Vbgj7TxtSZVRe0tafP8Wa+cc1tf64Ja1/ZS4O/y3VJ7A89Wqq42RMc/6S1pNulX52hgfkR8sclJaghJbwJ+A9zB2vr8T5PaMS4EppO+dEdGxMAGtZYn6QDgXyLiMEk7kUoc2wC3AsdFRE8z0zfUJM0iNfSPBe4HPkj6gdi211rS54CjSHcE3gqcQKqvb6trLWkhcACpG/PHgdOAn1Dl2ubg+S3SXVUvAB+MiEUbfOxODxhmZlZOp1dJmZlZSQ4YZmZWigOGmZmV4oBhZmalOGCYmVkpDhjW8SR9WdIBko5Y3x6LJU3OvaHeKunNA5ad04jOLCV9eqj3aVaGb6u1jifp16QOCr8EXBQRv12PbY8GDo2IOYOuPEQkPRcRE4breGYVLmFYx5L0NUm3A28Aric96PVdSadWWfdlkq7MYwpcKWl6fjjuq8BsSbdJ2mzANldL6sqvn5P0RUl/kHSDpO3z/AWSzpb0G0l/yv1fIekDkr5V2NfPcynoDFKPrLdJOl/SeEm/yPu9U9JRDXq7zBwwrHNFxCdJQWIBKWjcHhGvi4jTq6z+LVI30a8Dzge+GRG3AacCF0TErIhYWedw44EbImJ34Frg7wvLZgD7k0o5Z0vatE6aTwFW5uO9j/QE79KI2D2PA/HLMudutiEcMKzT7QHcBryK1PdQLfsA/51f/wB403oe50Xg5/n1zaQgUXFhRPRHxL2kbjxetR77vQM4SNJXJL05Ip5dz3SZlTZm8FXM2k+uTlpA6r3zCdKAO5J0G7DPIKUFWP8uontjbYPhatb97g3cV5D6Qyr+oKta6oiIP0naE5gNfFnSr2qUkMw2mksY1pEi4raImAX8iTQ876+Bt9epWvodqcdbgPcB1w1hco6UNErSzqTBj+4BHgRm5fnTSKNDVvTmruqRNAV4ISJ+SBpAaKPGbDarxyUM61iSJgNPR0S/pFdFRL0qqY8B8yV9kjSa3QeHMCn3ANcA2wMfjohVkn4LPECqcroTuKWw/jzgdkm3AN8HviapH+gFPjKE6TJbh2+rNWsiSQuAn0fERYOta9ZsrpIyM7NSXMIwM7NSXMIwM7NSHDDMzKwUBwwzMyvFAcPMzEpxwDAzs1L+P56ckn3d0bv1AAAAAElFTkSuQmCC\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "plt.plot(cumulative_coverage)\n", "plt.title('Coverage of cgi_decode() with random inputs')\n", "plt.xlabel('# of inputs')\n", "plt.ylabel('lines covered')" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "This is just _one_ run, of course; so let's repeat this a number of times and plot the averages." ] }, { "cell_type": "code", "execution_count": 32, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "runs = 100\n", "\n", "# Create an array with TRIALS elements, all zero\n", "sum_coverage = [0] * trials\n", "\n", "for run in range(runs):\n", " all_coverage, coverage = population_coverage(hundred_inputs(), cgi_decode)\n", " assert len(coverage) == trials\n", " for i in range(trials):\n", " sum_coverage[i] += coverage[i]\n", "\n", "average_coverage = []\n", "for i in range(trials):\n", " average_coverage.append(sum_coverage[i] / runs)" ] }, { "cell_type": "code", "execution_count": 33, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "Text(0,0.5,'lines covered')" ] }, "execution_count": 33, "metadata": {}, "output_type": "execute_result" }, { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYIAAAEWCAYAAABrDZDcAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4zLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvIxREBQAAIABJREFUeJzt3XmcXFWZ//HPN/u+kZAQkhCWQBKQNSyRRRFEFhUcBWVkAGUZHR3FcZxBx3H7qYjiNuMooKwKCC4oOm5hFwaQJAQIJKxZCEk6+9addKe7n98f9xQpmq7u6qSrq7vq+369+tV1l7r3OXVv3afOOXdRRGBmZtWrV7kDMDOz8nIiMDOrck4EZmZVzonAzKzKORGYmVU5JwIzsyrnRGDdlqQDJD0habOkT3Ticq+W9J878b6QtF9nxVHE+t4qaVkH5p8uaXbe8N8kHdgJcXxO0k/amH6hpId2dT2dRdKXJP2sC9ZzvKTnSr2ertCn3AHsKkn3A4cA4yKivszhWOf6N+D+iDisMxcaER/pzOV1I/8PuCpv+CrgK8B7d2WhEfH13GtJk4FFQN+IaNyV5fZ0EfFX4ICuWJekAKZExIulWH6PrhGknfJ4IIB3l2gdPT5ZdkQ3K+9ewDPlDqInkLQHcCLwm7zRdwEnpmndUjfb36pWj04EwPnAo8CNwAW5kZKOkbRSUu+8ce+R9FR63UvS5ZJekrRW0h2SRqVpk1MTwEWSlgL3pvG/SMvcKOnB/Cq3pN0k/U7SJkmPS/pqflVZ0lRJsyStk/ScpHMKFUjSKEk3SFouab2k3+RNu0TSi2k5d0kan8ZfLemqFsv5raR/Sa/HS/qVpNWSFuU3s6Rq9C8l/UzSJuBCSUdJekTSBkkrJP1AUr+895ySyrFR0g8lPSDp4rzpH5a0IMX/Z0l7tVHed0t6Jq3rfknT0vh7yQ5sP5C0RdL+Hfys/i3FvlzSxfnNOpJulPTVQjHlLeMzecv4cItp/SVdJWmppJq0DQbmTT9T0ry0T7wk6dS8bXFX2oYvSrok7z0DU2zrJT0LHNlinQW3I/B2YG5EbMuNSK/nAKcUKN8SSUek1+elz2h6Gr4493nq9U0tD6b/G9J2mZm3vKtS7IskndbG57pY0r8r+z7WSuqjHd/HzZKelfSevPkvlPRQoeVL2jvtg5slzQJGt1hfq/tYXiyfkfSUpFpJ10kaK+mPaXl3SxpZoByva7pLy/rXtKyNkm6XNCB/XmXNbGvSvB/Me+/9Lb5DrzW3Scp95k+mz/z9kkZL+n0q0zpJf5W088fziOixf8CLwD8BRwDbgbF5014C3p43/Avg8vT6MrIEMgHoD1wD3JamTSarYdwMDAYGpvEfBoam+b8HzMtb9s/T3yBgOvAK8FCaNjgNf4isKe5wYA1wYIEy/S9wOzAS6Au8JY1/W3rf4SmG/wYeTNNOSOtQGh4JbAXGkyX7OcAXgH7APsDLwDvSvF9Kn91Zad6B6fM8JsU7GVgAXJbmHw1sAv4uTf9kev/FafpZabtMS9M/D/xfgbLuD9SSHcT6kjUFvQj0S9Pvzy23g5/VqcBK4MC0TX6atul+afqNwFfb2bdOBWqAg9I2vLXFMr5H9ot7VNovfgdckaYdBWxM5eoF7AlMTdMeAH4IDAAOBVYDJ6Vp3wD+mpY5EZgPLEvT2tuO3wL+p5Vy/BfwnQJlvBn4dHp9Ldl35qN50z6Vt4/8rMX3o0/eci5M+8AlQG/go8By0v7YynoXA/NSGXPfr7PZsb++P+0XexSzfOAR4Dtk34sTgM158ba3jy0mOxaMTdtpFTAXOCwt717giwXK8dbc9slb1t9SOUaRfW8+kjdvY16cb0lxHdDavp7K/FDe8Gv7Xhq+Arg6lakvWctIq593UcfSUh6oS/kHHJd2jtFpeGFux03DXwWuT6+Hpg99rzS8gPTlS8N7pGXlDnwB7NPGukekeYanHXN7boPmrTuXCN4P/LXF+69pbedKcTQDI1uZdh3wzbzhIWm9kwEBS4ET0rRLgHvT66OBpS2W9Vnghrwv+YPtfNaXAXem1+cDj+RNE1kSyiWCPwIX5U3vBdTlPvsWy/1P4I4W874KvLW1L0cHPqvrSQflNLwfHU8E1wPfyBveP7eMVOZaYN+86TOBRXnb97utLHMi0AQMzRt3BXBjev0ycGretEvZkQja244/zo83b56vkb4HrUy7CLgr7ztxMfDzNLwEODxvH2kvEbyYNzwozTOuwHoXAx9u5/OfB5zZ3vKBSWQH2MF502/Ni7e9fWwx8MG86b8CfpQ3/M/AbwrE+FbemAjOyxv+JnB13rwt47wD+M/W9nXaTwRfAX6bP25X/npy09AFwF8iYk0avpW85qE0/HeS+pP9ep0bEUvStL2AO1O1agPZl6CJ7FdBziu5F5J6S/pGqrpuItvgkP06HkOWQF5p7b1pXUfn1pXW90GynbilicC6iFjfyrTxZF9OACJiC7AW2DOyPePnwLlp8t8Dt+Stf3yL9X+uUFlTefdP1c6VqbxfZ0d1e3z+/Gnd+We27AV8P29d68gOnHsWUabmtOzW5m2pvc+q0PYoVstlLMl7PYbsYDQnr5x/SuNzsb1UYJnrImJzi+XumTe90Drb247ryX7wtDQU2NB6EXkAOF7SOLIfNLcDxyrrextOdjAu1srci4ioSy+HtDF/y33u/NSUlivbQby+iafQ8scD6yOiNm/e/M+tmH2sJu/11laG2ypHSyvzXte1eG9rcY7vwLLzfYusZvMXSS9LunwnlwP00D4CZW2x5wBvSQerlcCngEMkHQIQEc+SfdCnkR0Yb81bxCvAaRExIu9vQES8mjdP5L3+e+BM4GSyL8jkXChkVftGsmamnIkt1vVAi3UNiYiPtlK0V4BRkka0Mm052cEg9xkMBnYj+3UDcBvwPmXt8UeT/bLJLXNRi/UPjYjTC5QV4EdkNawpETGM7ICjNG1FflklqUXZXwH+scX6BkbE/xVRJpF9dq+2Mm9LbX1Wr4uR12+PYq1o8b5Jea/XkB0gDswr4/CIyH3pXwH2bWWZy1PM+QfsSewob1vrbG87PkVWa2lpGvBkawWM7AyUOuATZLXCzWQHskvJfo02t/a21pa1E15bTtpnfwx8HNgtIkaQNYupwHvzrQBGpu9DTv7ntiv7WGdrLc7l6XUt2Y+LnNZ+KL4mIjZHxKcjYh/gXcC/SDppZwPrkYmArB26iaw9/tD0N42sffX8vPluJdvJTyDrI8i5Gvha2gGRNEbSmW2sbyhQT/YLfBDZL2QAIqIJ+DXwJUmDJE1tEcPvgf0l/YOkvunvyPwOq7xlrSBrWvmhpJFp3hPyyvIhSYemWs7XgcciYnF67xNkSeknwJ8jIvcr8G/AJmWdcwNT7eYgSa/riGylvJuALak8+Unrf4E3STpL2RkfH+P1O+3VwGeVOtMlDZd0doH13AGcIekkSX2BT5N9zq0ljddp57O6g+yzmiZpEFm7ekfdQdZxPj0t44t5624mO3B9V9LuqZx7SnpHmuW6tP6TlJ2YsKekqRHxSirbFZIGSDqYrHnmlrx1fjaVZwJZs0ROe9txFnB4rnMyxdSfrL9nVhvlfIDsAPxAGr6/xXBLq8ma5PZpY5kdNZgsMawGkPQhshpBu1ItfzbwZUn9JB1HdmDM2el9rERycR4PvJMdx6V5ZC0Yg5Sd1HBRi/fVkPeZS3qnpP1SYttEdjxs2tmgemoiuICsbXRpRKzM/QE/AD6oHaek3UbWNndvXhMSwPfJOvr+ImkzWWfR0W2s72ay2sWrwLNp/nwfJ6sprCTrmLyNbGcj/co6BfgAWfZfCVxJ1mHUmn8ga/tfSNZxdVlazj1k7Z2/IvsVtG9aZr7byGotr9V+UqJ6F1myXET2a/YnKd5C/pWsFrSZ7IB3e97y1pB17H2TLDFOJ/si5sp7Zyrfz1Oz0nyyWtkbRMRzwHlkHd9rUpzvioiGNmLLV+iz+iNZJ+l9ZNXnR9L8RV9nkpbxPbLOwhfT/3z/nsY/msp5N+mc8oj4G9nJAd8l6zR+gB2/Ss8lq1EuB+4k6yvKHai/TLafLQL+QrYv5eJpcztGRE2KMf8HzbvJrsNYTmEPkCX+BwsMt/xc6sj6HR5OzTjHtLHsoqTa+7fJtlMN8Cbg4Q4s4u/Jvr/ryBL2zXnL3tV9rDOtJGvCW06W/D8SEQvTtO8CDWTlv4kdPw5yvgTclD7zc4ApZPvcFrLP7YcRcf/OBpbrdbdOJOlKso6yC9qduYdTdsraMrIOt/vKHU9rUu1rPtA/KvgiKGWnft4EHBURIekxso77+WUOrepJeitZB/aE9uYth55aI+hWlF0ncLAyR5FV6+4sd1ylIukdkkakpodc/0HLWlJZKbtupJ+yc8CvBH5XyUkAsl/WEXFk5E4ziTjaScCK4UTQOYaS9RPUkrVJfpvs1K5KNZPsrJhcVfusiNha3pDe4B/J2pxfIms7fUPnvLKLe7a08vfHrg7WrJzcNGRmVuVcIzAzq3I94oZPo0ePjsmTJ5c7DDOzHmXOnDlrImJMe/P1iEQwefJkZs+e3f6MZmb2GklL2p/LTUNmZlXPicDMrMo5EZiZVTknAjOzKudEYGZW5UqWCCRNlHSfskcWPiPpk2n82Wm4WdKMUq3fzMyKU8rTRxvJHoM3N91/fY6y54nOJ3tQzDUlXLeZmRWpZIkg3S9+RXq9WdICsqdpzQLIbqNtZmYAjU3NPL54PY8vXkdj045nAr3n8AnsPXpwG+/cdV1yQZmyR98dBjzWgfdcSvakJCZNmtTO3GbWUkSwYMVm7ntuFWu2FP0oBiuDtVsaeOD51Wzcuh2A/N/Jh+81sucnAklDyB6mcllEbCr2fRFxLXAtwIwZM3xnPKtKG7du5/7nVvHYotf/SmxPY1Pwt8XrWLZ+KxIM6d8jbiJQtQb27c1J03bnlOljOX7KGAZ38fYq6drSo+F+BdwSEb8u5brMuoum5mDu0vXc/WwNr6yva/8NBayrbWD24vU0NgfDBvTp8MFh+h7D+PiJ+3HStLGMGVrogXhmJUwE6Vma1wELIuI7pVqPWXdQ19DIX19Yw6xna7h34SrW1TbQt7fYa7fBRT2BvTUD+vbmkhP24eRpYzls4gh69XK/mpVGKWsEx5I9U/ZpSfPSuM+RPav3v4ExwP9KmhcR7yiwDLOSiQjmv7qJWQtqePTltWzvQNNLvubmYOHKzdQ3NjN0QB/eNnV33j59LCfsP4ZhA/p2ctRmna+UZw09BAV/DFXsYxytYyKC52u2cPeCGu5buOq1zrKusGHrdlZvrqeX4E0TRjBswM5/Hc49ahJvnz6Wo/YeRd/evk7Tehb3IFmXaGhs5rFFa5n1bA0PvbCGrdubXhu/trYBgEMmDGfK2CFdFlP/Pr2Zue9unDR1d3Yb4jZ0q15OBNbpGhqb+fFfX+aGhxdRvz1rbqlvbKahqZkBfXtx3H6jGTW4HwBCHDxxOCdPG8vYYQPKGbZZ1XIisF22taGJ5vTs6yeXbeALv32GF1dt4cQDxrD36OwXfp/e4qjJozhuymgG9O1dznDNrAUnAuuw5ubgyWUbmPVsDbOereGFVVteN33iqIHccOGRnDh19zJFaGYd4URgr7N523ZqNrV+FerSdbXMeraGuxesYvXmenr3EkfvPYp3HzKe/n2zDtKhA/py1qF7MrCff/Wb9RROBMbyDVu5e0H26z47jbLwhdxD+vfhLfuP4e3Tx3LiAbszfJBPjzTr6ZwIqsiy9XUsXpNd6doUwRNL13P3ghrmv5rd+WOf0YP58LF7M338sFZvCjhqUD+O3Hsk/fv4175ZJXEiqBKL1tRy2vcfZNv2HRdNSXD4pJFcftpUTp42lv1277pTN82s+3AiqALNzcHlv3qKvr178ePzZ7x21s7k3Qb7HjRm5kRQDW57fCmPLVrHle99E8dPGVPucMysm/G18BVu+YatXPGHhRy7326cM2NiucMxs27IiaCCNTUHn7vzaZqagyvec7CfCmdmrXIiqFD1jU38821zuf+51Xz29KlM2m1QuUMys27KfQQVqLa+kY/8bA5/fWENnz9jGufPnFzukMysG3MiqADraxv42h8WsD7dxXPR2lqWrK3jqrMP4X1HTChzdGbW3TkR9HCNTc187Na5zF68nv3HZdcBDB/Yl2vOO4KTp48tc3Rm1hM4EfRwX/vDAv7vpbV8++xDeK9//ZvZTnBncQ92x+xXuOHhxVx03N5OAma205wIeqi5S9fz+Tvnc9x+o/nsaVPLHY6Z9WBOBD1QzaZtfOSncxg3fAD/fe5h9PEzcs1sF/gI0sNs297EpT+dQ219Iz8+fwYj0yMfzcx2ljuLe5CI4HO/fponX9nANf9wBAeMG1rukMysAjgR9BDL1tfxpbue5e4FNXzq5P15x4Hjyh2SmVUIJ4JubntTM9c9tIjv3/0CAJ87fSoXH7dPmaMys0riRNCNbW1o4p9umcN9z63mlOlj+eK7D2TPEQPLHZaZVRgngm5q49btXHzT48xesp6vnnUQ5x2zV7lDMrMK5UTQDa3atI3zr/8bL63ewg/OPZwzDt6j3CGZWQVzIuhmHn15LR+/9QnqGhq57oIjOWF/P1HMzErLiaCbiAiufuBlvvXnhUwePZhbLj7ap4eaWZdwIiijpuZg9uJ1zHq2hlkLaliyto4z3rQHV77vYIb096Yxs67ho02ZzFmyjv+4cz4LV26mX+9ezNx3Ny47eQpnHbqnHylpZl3KiaCLbahr4Bt/XMjPH3+F8cMH8J1zDuGUA8e5BmBmZeOjTxdasraW8657jOUbtnHpCfvwyZOmMNgJwMzKzEehLrJgxSbOv/5vbG9q5hcfmcnhk0aWOyQzM8CJoEvMWbKOC294nMH9+nDrP85kylifDWRm3YcTQYktWlPLh254nNFD+vPTi45iwshB5Q7JzOx1/DyCEtq8bTuX3Dyb3r3EzR92EjCz7sk1ghJpbg4+dfs8Fq2p5acXHcXEUU4CZtY9laxGIGmipPskLZD0jKRPpvGjJM2S9EL6X5G9pt+7+3nuXrCKL7xzOm/ed3S5wzEzK6iUTUONwKcjYhpwDPAxSdOBy4F7ImIKcE8arihPLF3PD+57kfcePoHzZ/quoWbWvZUsEUTEioiYm15vBhYAewJnAjel2W4CzipVDOVQ39jEv//qKcYOG8CX3j3dVwmbWbfXJZ3FkiYDhwGPAWMjYgVkyQLYvSti6Co/vO8lnq/ZwtfecxBDB/QtdzhmZu0qeSKQNAT4FXBZRGzqwPsulTRb0uzVq1eXLsBOtHDlJn54/4ucdeh43jZ1bLnDMTMrSkkTgaS+ZEngloj4dRpdI2mPNH0PYFVr742IayNiRkTMGDOm+9+Tf0NdA/9y+5MMG9CXL7zrwHKHY2ZWtFKeNSTgOmBBRHwnb9JdwAXp9QXAb0sVQ1ep2bSN91/zKC+u2sJVZx/CqMH9yh2SmVnRSnkdwbHAPwBPS5qXxn0O+AZwh6SLgKXA2SWMoeQWr8luJLe+toEbP3Qkb97Pp4qaWc9SskQQEQ8BhU6ZOalU6+1KqzfXc841j7C9qZlbLzmGQyaOKHdIZmYd5iuLd1Jzc/Cvv3iSjVu3c+c/Hcv08cPKHZKZ2U7xvYZ20vUPL+KB51fz+TOmOQmYWY/mRLAT5r+6kSv/tJC3Tx/Lecf4ymEz69mcCDqoobGZT/z8CUYN7seV7z3YVw6bWY/nPoIO+s28V3l5dS0/OX+GTxM1s4rgGkEHNDcH1zzwEtP2GMZJ0yrqzhhmVsWcCDrg7gU1vLS6lo+8ZR83CZlZxXAi6IBrHnyZCSMHcsab9ih3KGZmncaJoEiPL17HnCXrueT4fejT2x+bmVUOH9GKdPX9LzFqcD/OmTGx3KGYmXUqJ4IiLFlbyz0LV3HBzMkM7Ne73OGYmXUqJ4Ii/OHplQC8b8aEMkdiZtb5nAiK8Kf5KzhkwnD2HDGw3KGYmXU6J4J2LFtfx5PLNnLqQT5TyMwqkxNBO/40P2sWOu2gcWWOxMysNAreYkLS00AUmh4RB5ckom7mT/NXMm2PYUwePbjcoZiZlURb9xp6Z/r/sfT/p+n/B4G6kkXUjazatI05S9fzqZP3L3coZmYlUzARRMQSAEnHRsSxeZMul/Qw8JVSB1duf35mJRFuFjKzylZMH8FgScflBiS9GaiKdpI/zl/JvmMGM2Xs0HKHYmZWMsXchvoi4HpJw8n6DDYCHy5pVN3A2i31PPryWj524n7lDsXMrKTaTQQRMQc4RNIwQBGxsfRhld8fnl5Bc8DpvsGcmVW4dpuGJI2VdB1we0RslDRd0kVdEFtZ3fnEq0wdN5Rpe/h5xGZW2YrpI7gR+DMwPg0/D1xWqoC6g8Vrapm7dANnHbZnuUMxMyu5YhLB6Ii4A2gGiIhGoKmkUZXZb+a9igRnHjq+/ZnNzHq4YhJBraTdSBeXSTqGrMO4IkUEdz7xKjP32Y09hvveQmZW+Yo5a+hfgLuAfdP1A2OA95U0qjJ64pUNLFlbx8d9tpCZVYk2E4GkXsAA4C3AAYCA5yJiexfEVhZ3zn2V/n16caovIjOzKtFmIoiIZknfjoiZwDNdFFPZNDQ28/unlnPKgeMYOqBvucMxM+sSxfQR/EXSeyWp5NGU2cMvrmF93XbOciexmVWRYvsIBgNNkraSNQ9FRFTcCfZ3L6hhUL/eHDdldLlDMTPrMsVcWVwVN9qJCO5duIrjp4ymfx8/l9jMqkcxVxZL0nmS/jMNT5R0VOlD61oLV25mxcZtvG3q7uUOxcysSxXTR/BDYCbw92l4C/A/JYuoTO5duAqAEw9wIjCz6lJMH8HREXG4pCcAImK9pH4ljqvL3bOghoMnDGf3YQPKHYqZWZcqpkawXVJvdlxZPIZ0u4lKsa62gSde2eDagJlVpWISwX8BdwK7S/oa8BDw9ZJG1cXuf24VEXDSNCcCM6s+xZw1dIukOcBJZKeOnhURC0oeWRe6Z+Eqxgztz0Hjh5c7FDOzLtduIpD0fbJnEVRcBzHA9qZmHnx+NacftAe9elX8NXNmZm9QTNPQXODzkl6U9C1JM0odVFeavXg9m7c1cqJPGzWzKtVuIoiImyLidOAosofSXCnphfbeJ+l6Saskzc8bd4ikRyQ9Lel36fGXZfXIy2vpJTh2v93KHYqZWVkUUyPI2Q+YCkwGFhYx/43AqS3G/QS4PCLeRNYB/ZkOrL8k5ixZx9Rxw3yTOTOrWsVcWZyrAXyF7A6kR0TEu9p7X0Q8CKxrMfoA4MH0ehbw3o6F27kam5p5YukGZkweWc4wzMzKqpgLyhYBMyNiTSesbz7wbuC3wNnAxEIzSroUuBRg0qRJnbDqN1qwYjN1DU3MmDyqJMs3M+sJiukjuBp4s6Sr0l+7tYE2fBj4WDoddSjQ0MZ6r42IGRExY8yYMbuwysJmL8kqLDP2co3AzKpXMaePXkHWUXxLGvUJSW+OiM92dGURsRA4JS13f+CMji6jM81evJ49Rwxk/Ag/m9jMqlcxTUNnAIdGRDOApJuAJ4AOJwJJu0fEqvQIzM8DV3d0GZ0lIpi9ZB1H7+2zhcysuhV71tCIvNdFXX4r6TbgEeAAScskXQScK+l5srOOlgM3dCTYzrRs/VZqNtW7o9jMql4xNYIrgCck3Ud2i4kTKKI2EBHnFpj0/eLDK50d/QPuKDaz6lbMvYZuk3Q/cCRZIvj3iFhZ6sBKbfbi9Qzt34cDxlXFA9jMzAoq5jqC9wB1EXFXRPwW2CbprNKHVlqzF6/nsL1G0tv3FzKzKldMH8EXI2JjbiAiNgBfLF1IpbexbjvPr9rs00bNzCguEbQ2TzF9C93W3KXricAdxWZmFJcIZkv6jqR9Je0j6bvAnFIHVkoLVm4C4OAJI9qZ08ys8hWTCP6Z7Arg24E7gK3Ax0oZVKnVbNzG0AF9GNK/R1dszMw6RTFnDdUCl3dBLF1m5aZtjPND6s3MgI7dhrpirNxUz7jhTgRmZlCliaBm4zZ2H+pEYGYGVZgImpqD1VvqGTe8f7lDMTPrFoq5oOybkoZJ6ivpHklrJJ3XFcGVwtot9TQ1h/sIzMySYmoEp0TEJuCdwDJgf7rBIyZ31spN2wAY60RgZgYUlwhyD/M9HbgtIlo+frJHWbkxSwTuLDYzyxRzIv3vJC0ku37gnySNAbaVNqzSqUk1AjcNmZllinlU5eXATGBGRGwH6oAzSx1YqazctI3evcRuQ9xZbGYGxXUWDyK7kvhHadR4YEYpgyqlmk31jBnS33cdNTNLiukjuIHsFhNvTsPLgK+WLKISq9m0jbHuHzAze00xiWDfiPgmsB0gIraSPaCmR1q5cRvjhrlZyMwsp5hE0CBpIBAAkvYF6ksaVQn5PkNmZq9XzFlDXwT+BEyUdAtwLHBhKYMqlbqGRjZva3TTkJlZnmLuPjpL0lzgGLImoU9GxJqSR1YCNZuyisxY32fIzOw1xd6QfwCwPs0/XRIR8WDpwioNX0xmZvZG7SYCSVcC7weeAZrT6AB6XCKo8e0lzMzeoJgawVnAARHRYzuIc3L3GXKNwMxsh2LOGnqZHfcb6tFWbtzGkP5+RKWZWb5ijoh1wDxJ95B32mhEfKJkUZVIzaZtjPU1BGZmr1NMIrgr/fV4WSJws5CZWb5iTh+9qSsC6Qo1m+o5eu9R5Q7DzKxbKZgIJN0REedIepp0VXG+iDi4pJF1subm8H2GzMxa0VaN4JPp/zu7IpBSW1vbQKMfUWlm9gYFE0FErEj/l3RdOKXjawjMzFrXVtPQZlppEiK7zURExLCSRVUCNb6GwMysVW3VCIZ2ZSCltuOh9T591MwsXzEXlFWEVemGc2P8iEozs9epmkSwpb6Rwf1606d31RTZzKwoVXNUrK1vZLBvLWFm9gbVkwgampwIzMxaUT2JoL6Rwf17lzsMM7Nup2SJQNL1klZJmp837lBJj0qaJ2m2pKNKtf6WausbGdTPNQIzs5ZKWSO4ETi1xbhvAl+OiEOBL6ThLlHX0MTgfq4RmJm1VLJEkB5lua7laCB3IdpwYHmp1t+SO4vNzFrX1UfGy4A/S7qKLAmbA/g5AAAKP0lEQVS9udCMki4FLgWYNGnSLq+4tqGRwW4aMjN7g67uLP4o8KmImAh8Criu0IwRcW1EzIiIGWPGjNnlFdfW+6whM7PWdHUiuAD4dXr9C6BLOosjIqsR+KwhM7M36OpEsBx4S3r9NuCFrljp1u1NROAagZlZK0p2ZJR0G/BWYLSkZcAXgUuA70vqA2wj9QGUWm19E4DPGjIza0XJEkFEnFtg0hGlWmchdQ2NAL6OwMysFVVxZfGW+iwRuGnIzOyNqiIR1DWkpiF3FpuZvUFVJALXCMzMCquKRFD3WmexE4GZWUtVkQhqG3I1AjcNmZm1VB2JINc05BqBmdkbVEUiyHUWD3KNwMzsDaoiEWypb6Rvb9G/jxOBmVlLVZEI6vxQGjOzgqoiEWypb2KITx01M2tVVSSCuoZGBvk+Q2ZmraqKRFDb0MQg1wjMzFpVHYmgvpEhPmPIzKxVVZMI3FlsZta66kgEDY3uLDYzK6AqEkFdfZM7i83MCqiKRLCl3jUCM7NCKj4RNDY1U9/Y7D4CM7MCKj4R1G33Q2nMzNpS8Ymg1g+lMTNrUxUkgnTnUXcWm5m1qgoSQVYjcGexmVnrKj8RpKeTubPYzKx1lZ8I6t1ZbGbWlopPBHUN7iw2M2tLxSeC12oEbhoyM2tVFSSCXI3ATUNmZq2p/ETgzmIzszZVfiKob2Rg39707qVyh2Jm1i1VfiJoaHKzkJlZGyo/EfihNGZmbaqCRNDkU0fNzNpQ8YmgrqGRwb7PkJlZQRWfCGrrG10jMDNrQ+UnAncWm5m1qfITgTuLzczaVBWJwLegNjMrrKITQURQ29Dkh9KYmbWhZIlA0vWSVkmanzfudknz0t9iSfNKtX6A+sZmmprDncVmZm0o5RHyRuAHwM25ERHx/txrSd8GNpZw/dQ15O486hqBmVkhJUsEEfGgpMmtTZMk4BzgbaVaP/jB9WZmxShXH8HxQE1EvFBoBkmXSpotafbq1at3aiW1fiiNmVm7ypUIzgVua2uGiLg2ImZExIwxY8bs1EpyNQJ3FpuZFdblP5Ul9QH+Djii1OvKPZ3Mp4+amRVWjhrBycDCiFhW6hXtqBE4EZiZFVLK00dvAx4BDpC0TNJFadIHaKdZqLPUNrhGYGbWnlKeNXRugfEXlmqdLdXlHlPpew2ZmRVU0VcWb0lNQ64RmJkVVtGJoK6+iV6C/n0quphmZrukoo+QW+obGdyvD9n1a2Zm1pqKTgRTxw3ltDeNK3cYZmbdWkU3nn/gqEl84KhJ5Q7DzKxbq+gagZmZtc+JwMysyjkRmJlVOScCM7Mq50RgZlblnAjMzKqcE4GZWZVzIjAzq3KKiHLH0C5Jq4ElO/n20cCaTgynp6jGcldjmaE6y12NZYaOl3uviGj3EY89IhHsCkmzI2JGuePoatVY7mosM1RnuauxzFC6crtpyMysyjkRmJlVuWpIBNeWO4AyqcZyV2OZoTrLXY1lhhKVu+L7CMzMrG3VUCMwM7M2OBGYmVW5ik4Ekk6V9JykFyVdXu54SkHSREn3SVog6RlJn0zjR0maJemF9H9kuWPtbJJ6S3pC0u/T8N6SHktlvl1Sv3LH2NkkjZD0S0kL0zafWenbWtKn0r49X9JtkgZU4raWdL2kVZLm541rddsq81/p2PaUpMN3Zd0Vmwgk9Qb+BzgNmA6cK2l6eaMqiUbg0xExDTgG+Fgq5+XAPRExBbgnDVeaTwIL8oavBL6byrweuKgsUZXW94E/RcRU4BCy8lfstpa0J/AJYEZEHAT0Bj5AZW7rG4FTW4wrtG1PA6akv0uBH+3Kiis2EQBHAS9GxMsR0QD8HDizzDF1uohYERFz0+vNZAeGPcnKelOa7SbgrPJEWBqSJgBnAD9JwwLeBvwyzVKJZR4GnABcBxARDRGxgQrf1mSP1B0oqQ8wCFhBBW7riHgQWNdidKFteyZwc2QeBUZI2mNn113JiWBP4JW84WVpXMWSNBk4DHgMGBsRKyBLFsDu5YusJL4H/BvQnIZ3AzZERGMarsTtvQ+wGrghNYn9RNJgKnhbR8SrwFXAUrIEsBGYQ+Vv65xC27ZTj2+VnAjUyriKPVdW0hDgV8BlEbGp3PGUkqR3AqsiYk7+6FZmrbTt3Qc4HPhRRBwG1FJBzUCtSW3iZwJ7A+OBwWTNIi1V2rZuT6fu75WcCJYBE/OGJwDLyxRLSUnqS5YEbomIX6fRNbmqYvq/qlzxlcCxwLslLSZr8nsbWQ1hRGo+gMrc3suAZRHxWBr+JVliqORtfTKwKCJWR8R24NfAm6n8bZ1TaNt26vGtkhPB48CUdHZBP7IOprvKHFOnS23j1wELIuI7eZPuAi5Iry8AftvVsZVKRHw2IiZExGSy7XpvRHwQuA94X5qtosoMEBErgVckHZBGnQQ8SwVva7ImoWMkDUr7eq7MFb2t8xTatncB56ezh44BNuaakHZKRFTsH3A68DzwEvAf5Y6nRGU8jqxK+BQwL/2dTtZmfg/wQvo/qtyxlqj8bwV+n17vA/wNeBH4BdC/3PGVoLyHArPT9v4NMLLStzXwZWAhMB/4KdC/Erc1cBtZP8h2sl/8FxXatmRNQ/+Tjm1Pk51VtdPr9i0mzMyqXCU3DZmZWRGcCMzMqpwTgZlZlXMiMDOrck4EZmZVzonAKpqkKyS9VdJZHb0DraQx6Q6XT0g6vsW0n5TiJoaSPtfZyzRrj08ftYom6V6ym9N9HfhlRDzcgfd+ADgtIi5od+ZOImlLRAzpqvWZgWsEVqEkfUvSU8CRwCPAxcCPJH2hlXn3knRPuq/7PZImSToU+CZwuqR5kga2eM/9kmak11skfU3Sk5IelTQ2jb9R0tWS/irp+XSPJCRdKOkHecv6faq1fIPsLpvzJN0iabCk/03LnS/p/SX6uKzKORFYRYqIz5Ad/G8kSwZPRcTBEfGVVmb/AdktfQ8GbgH+KyLmAV8Abo+IQyNiaxurGww8GhGHAA8Cl+RNmwy8haxWcrWkAW3EfDmwNa3vg2T3pl8eEYdEdi/+PxVTdrOOciKwSnYY2S03ppLdn6aQmcCt6fVPyW7b0RENwO/T6zlkB/+cOyKiOSJeAF5OsRTraeBkSVdKOj4iNnYwLrOi9Gl/FrOeJTXr3Eh2R8Y1ZA8zkaR5wMx2ft1Dx2/nuz12dLY18frvVctlBdlT5fJ/hLVaS4iI5yUdQXbvqCsk/aVAjcZsl7hGYBUnIuZFxKFkNxycDtwLvKONJp7/I7uLKcAHgYc6MZyzJfWStC/ZjdKeAxYDh6bxE8meppezPd1WHEnjgbqI+BnZw1l26bm0ZoW4RmAVSdIYYH1ENEuaGhFtNQ19Arhe0mfIngD2oU4M5TngAWAs8JGI2CbpYWARWdPPfGBu3vzXAk9JmgvcDHxLUjPZHSk/2olxmb3Gp4+alYikG8lukf3L9uY1Kyc3DZmZVTnXCMzMqpxrBGZmVc6JwMysyjkRmJlVOScCM7Mq50RgZlbl/j9TZH7GMpSkQwAAAABJRU5ErkJggg==\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "plt.plot(average_coverage)\n", "plt.title('Average coverage of cgi_decode() with random inputs')\n", "plt.xlabel('# of inputs')\n", "plt.ylabel('lines covered')" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "We see that on average, we get full coverage after 40–60 fuzzing inputs." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Getting Coverage from External Programs\n", "\n", "Of course, not all the world is programming in Python. The good news is that the problem of obtaining coverage is ubiquitous, and almost every programming language has some facility to measure coverage. Just as an example, let us therefore demonstrate how to obtain coverage for a C program." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Our C program (again) implements `cgi_decode`; this time as a program to be executed from the command line:\n", "\n", "```shell\n", "$ ./cgi_decode 'Hello+World'\n", "Hello World\n", "```" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Here comes the C code, first as a Python string. We start with the usual C includes:" ] }, { "cell_type": "code", "execution_count": 34, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "cgi_c_code = \"\"\"\n", "/* CGI decoding as C program */\n", "\n", "#include \n", "#include \n", "#include \n", "\n", "\"\"\"" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Here comes the initialization of `hex_values`:" ] }, { "cell_type": "code", "execution_count": 35, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "cgi_c_code += r\"\"\"\n", "int hex_values[256];\n", "\n", "void init_hex_values() {\n", " for (int i = 0; i < sizeof(hex_values) / sizeof(int); i++) {\n", " hex_values[i] = -1;\n", " }\n", " hex_values['0'] = 0; hex_values['1'] = 1; hex_values['2'] = 2; hex_values['3'] = 3;\n", " hex_values['4'] = 4; hex_values['5'] = 5; hex_values['6'] = 6; hex_values['7'] = 7;\n", " hex_values['8'] = 8; hex_values['9'] = 9;\n", "\n", " hex_values['a'] = 10; hex_values['b'] = 11; hex_values['c'] = 12; hex_values['d'] = 13;\n", " hex_values['e'] = 14; hex_values['f'] = 15;\n", "\n", " hex_values['A'] = 10; hex_values['B'] = 11; hex_values['C'] = 12; hex_values['D'] = 13;\n", " hex_values['E'] = 14; hex_values['F'] = 15;\n", "}\n", "\"\"\"" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Here's the actual implementation of `cgi_decode()`, using pointers for input source (`s`) and output target (`t`):" ] }, { "cell_type": "code", "execution_count": 36, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "cgi_c_code += r\"\"\"\n", "int cgi_decode(char *s, char *t) {\n", " while (*s != '\\0') {\n", " if (*s == '+')\n", " *t++ = ' ';\n", " else if (*s == '%') {\n", " int digit_high = *++s;\n", " int digit_low = *++s;\n", " if (hex_values[digit_high] >= 0 && hex_values[digit_low] >= 0) {\n", " *t++ = hex_values[digit_high] * 16 + hex_values[digit_low];\n", " }\n", " else\n", " return -1;\n", " }\n", " else\n", " *t++ = *s;\n", " s++;\n", " }\n", " *t = '\\0';\n", " return 0;\n", "}\n", "\"\"\"" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Finally, here's a driver which takes the first argument and invokes `cgi_decode` with it:" ] }, { "cell_type": "code", "execution_count": 37, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "cgi_c_code += r\"\"\"\n", "int main(int argc, char *argv[]) {\n", " init_hex_values();\n", "\n", " if (argc >= 2) {\n", " char *s = argv[1];\n", " char *t = malloc(strlen(s) + 1); /* output is at most as long as input */\n", " int ret = cgi_decode(s, t);\n", " printf(\"%s\\n\", t);\n", " return ret;\n", " }\n", " else\n", " {\n", " printf(\"cgi_decode: usage: cgi_decode STRING\\n\");\n", " return 1;\n", " }\n", "}\n", "\"\"\"" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Let us create the C source code:" ] }, { "cell_type": "code", "execution_count": 38, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "with open(\"cgi_decode.c\", \"w\") as f:\n", " f.write(cgi_c_code)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "We can now compile the C code into an executable. The `--coverage` option instructs the C compiler to instrument the code such that at runtime, coverage information will be collected. (The exact options vary from compiler to compiler.)" ] }, { "cell_type": "code", "execution_count": 39, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "!cc --coverage -o cgi_decode cgi_decode.c" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "When we now execute the program, coverage information will automatically be collected and stored in auxiliary files:" ] }, { "cell_type": "code", "execution_count": 40, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Send mail to me@fuzzingbook.org\r\n" ] } ], "source": [ "!./cgi_decode 'Send+mail+to+me%40fuzzingbook.org'" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "The coverage information is collected by the `gcov` program. For every source file given, it produces a new `.gcov` file with coverage information." ] }, { "cell_type": "code", "execution_count": 41, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "File 'cgi_decode.c'\r\n", "Lines executed:91.89% of 37\r\n", "cgi_decode.c:creating 'cgi_decode.c.gcov'\r\n", "\r\n" ] } ], "source": [ "!gcov cgi_decode.c" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "In the `.gcov` file, each line is prefixed with the number of times it was called (`-` stands for a non-executable line, `#####` stands for zero) as well as the line number. We can take a look at `cgi_decode()`, for instance, and see that the only code not executed yet is the `return -1` for an illegal input." ] }, { "cell_type": "code", "execution_count": 42, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " -: 26:int cgi_decode(char *s, char *t) {\n", " 64: 27: while (*s != '\\0') {\n", " 31: 28: if (*s == '+')\n", " 3: 29: *t++ = ' ';\n", " 28: 30: else if (*s == '%') {\n", " 1: 31: int digit_high = *++s;\n", " 1: 32: int digit_low = *++s;\n", " 2: 33: if (hex_values[digit_high] >= 0 && hex_values[digit_low] >= 0) {\n", " 1: 34: *t++ = hex_values[digit_high] * 16 + hex_values[digit_low];\n", " 1: 35: }\n", " -: 36: else\n", " #####: 37: return -1;\n", " 1: 38: }\n", " -: 39: else\n", " 27: 40: *t++ = *s;\n", " 31: 41: s++;\n", " -: 42: }\n", " 1: 43: *t = '\\0';\n", " 1: 44: return 0;\n", " 1: 45:}\n" ] } ], "source": [ "lines = open('cgi_decode.c.gcov').readlines()\n", "for i in range(30, 50):\n", " print(lines[i], end='')" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Let us read in this file to obtain a coverage set:" ] }, { "cell_type": "code", "execution_count": 43, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def read_gcov_coverage(c_file):\n", " gcov_file = c_file + \".gcov\"\n", " coverage = set()\n", " with open(gcov_file) as file:\n", " for line in file.readlines():\n", " elems = line.split(':')\n", " covered = elems[0].strip()\n", " line_number = int(elems[1].strip())\n", " if covered.startswith('-') or covered.startswith('#'):\n", " continue\n", " coverage.add((c_file, line_number))\n", " return coverage" ] }, { "cell_type": "code", "execution_count": 44, "metadata": { "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "coverage = read_gcov_coverage('cgi_decode.c')" ] }, { "cell_type": "code", "execution_count": 45, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "[('cgi_decode.c', 53),\n", " ('cgi_decode.c', 35),\n", " ('cgi_decode.c', 16),\n", " ('cgi_decode.c', 14),\n", " ('cgi_decode.c', 38)]" ] }, "execution_count": 45, "metadata": {}, "output_type": "execute_result" } ], "source": [ "list(coverage)[:5]" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "With this set, we can now do the same coverage computations as with our Python programs." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Finding Errors with Basic Fuzzing\n", "\n", "Given sufficient time, we can indeed cover each and every line within `cgi_decode()`, whatever the programming language would be. This does not mean that they would be error-free, though. Since we do not check the result of `cgi_decode()`, the function could return any value without us checking or noticing. To catch such errors, we would have to set up a *results checker* (commonly called an *oracle*) that would verify test results. In our case, we could compare the C and Python implementations of `cgi_decode()` and see whether both produce the same results." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Where fuzzing is great at, though, is in finding _internal errors_ that can be detected even without checking the result. Actually, if one runs our `fuzzer()` on `cgi_decode()`, one quickly finds such an error, as the following code shows:" ] }, { "cell_type": "code", "execution_count": 46, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "from ExpectError import ExpectError" ] }, { "cell_type": "code", "execution_count": 47, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "Traceback (most recent call last):\n", " File \"\", line 5, in \n", " cgi_decode(s)\n", " File \"\", line 22, in cgi_decode\n", " digit_high, digit_low = s[i + 1], s[i + 2]\n", "IndexError: string index out of range (expected)\n" ] } ], "source": [ "with ExpectError():\n", " for i in range(trials):\n", " try:\n", " s = fuzzer()\n", " cgi_decode(s)\n", " except ValueError:\n", " pass" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "So, it is possible to cause `cgi_decode()` to crash. Why is that? Let's take a look at its input:" ] }, { "cell_type": "code", "execution_count": 48, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "'82 202*&<1&($34\\'\"/\\'.<5/!8\"\\'5:!4))%;'" ] }, "execution_count": 48, "metadata": {}, "output_type": "execute_result" } ], "source": [ "s" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "The problem here is at the end of the string. After a `'%'` character, our implementation will always attempt to access two more (hexadecimal) characters, but if these are not there, we will get an `IndexError` exception. " ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "This problem is also present in our C variant, which inherits it from the original implementation \\cite{Pezze2008}:\n", "\n", "```c\n", "int digit_high = *++s;\n", "int digit_low = *++s;\n", "```\n", "\n", "Here, `s` is a pointer to the character to be read; `++` increments it by one character.\n", "In the C implementation, the problem is actually much worse. If the `'%'` character is at the end of the string, the above code will first read a terminating character (`'\\0'` in C strings) and then the following character, which may be any memory content after the string, and which thus may cause the program to fail uncontrollably. The somewhat good news is that `'\\0'` is not a valid hexadecimal character, and thus, the C version will \"only\" read one character beyond the end of the string." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "Interestingly enough, none of the manual tests we had designed earlier would trigger this bug. Actually, neither statement nor branch coverage, nor any of the coverage criteria commonly discussed in literature would find it. However, a simple fuzzing run can identify the error with a few runs – _if_ appropriate run-time checks are in place that find such overflows. This definitely calls for more fuzzing!" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Lessons Learned\n", "\n", "* Coverage metrics are a simple and fully automated means to approximate how much functionality of a program is actually executed during a test run.\n", "* A number of coverage metrics exist, the most important ones being statement coverage and branch coverage.\n", "* In Python, it is very easy to access the program state during execution, including the currently executed code." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "At the end of the day, let's clean up:" ] }, { "cell_type": "code", "execution_count": 49, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import os\n", "import glob" ] }, { "cell_type": "code", "execution_count": 50, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "for file in glob.glob(\"cgi_decode\") + glob.glob(\"cgi_decode.*\"):\n", " os.remove(file)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "source": [ "## Next Steps\n", "\n", "Coverage is not only a tool to _measure_ test effectiveness, but also a great tool to _guide_ test generation towards specific goals – in particular uncovered code. We use coverage to\n", "\n", "* [guide _mutations_ of existing inputs towards better coverage in the chapter on mutation fuzzing](MutationFuzzer.ipynb)\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Background\n", "\n", "Coverage is a central concept in systematic software testing. For discussions, see the books in the [Introduction to Testing](Intro_Testing.ipynb)." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Exercises" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" }, "solution": "hidden", "solution2": "hidden", "solution2_first": true, "solution_first": true }, "source": [ "### Exercise 1: Fixing cgi_decode\n", "\n", "Create an appropriate test to reproduce the `IndexError` discussed above. Fix `cgi_decode()` to prevent the bug. Show that your test (and additional `fuzzer()` runs) no longer expose the bug. Do the same for the C variant." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" }, "solution": "hidden", "solution2": "hidden" }, "source": [ "**Solution.** Here's a test case:" ] }, { "cell_type": "code", "execution_count": 51, "metadata": { "slideshow": { "slide_type": "fragment" }, "solution2": "hidden" }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "Traceback (most recent call last):\n", " File \"\", line 2, in \n", " assert cgi_decode('%') == '%'\n", " File \"\", line 22, in cgi_decode\n", " digit_high, digit_low = s[i + 1], s[i + 2]\n", "IndexError: string index out of range (expected)\n" ] } ], "source": [ "with ExpectError():\n", " assert cgi_decode('%') == '%'" ] }, { "cell_type": "code", "execution_count": 52, "metadata": { "slideshow": { "slide_type": "fragment" }, "solution2": "hidden" }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "Traceback (most recent call last):\n", " File \"\", line 2, in \n", " assert cgi_decode('%4') == '%4'\n", " File \"\", line 22, in cgi_decode\n", " digit_high, digit_low = s[i + 1], s[i + 2]\n", "IndexError: string index out of range (expected)\n" ] } ], "source": [ "with ExpectError():\n", " assert cgi_decode('%4') == '%4'" ] }, { "cell_type": "code", "execution_count": 53, "metadata": { "slideshow": { "slide_type": "fragment" }, "solution2": "hidden" }, "outputs": [], "source": [ "assert cgi_decode('%40') == '@'" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" }, "solution2": "hidden" }, "source": [ "Here's a fix:" ] }, { "cell_type": "code", "execution_count": 54, "metadata": { "slideshow": { "slide_type": "fragment" }, "solution2": "hidden" }, "outputs": [], "source": [ "def fixed_cgi_decode(s):\n", " \"\"\"Decode the CGI-encoded string `s`:\n", " * replace \"+\" by \" \"\n", " * replace \"%xx\" by the character with hex number xx.\n", " Return the decoded string. Raise `ValueError` for invalid inputs.\"\"\"\n", "\n", " # Mapping of hex digits to their integer values\n", " hex_values = {\n", " '0': 0, '1': 1, '2': 2, '3': 3, '4': 4,\n", " '5': 5, '6': 6, '7': 7, '8': 8, '9': 9,\n", " 'a': 10, 'b': 11, 'c': 12, 'd': 13, 'e': 14, 'f': 15,\n", " 'A': 10, 'B': 11, 'C': 12, 'D': 13, 'E': 14, 'F': 15,\n", " }\n", "\n", " t = \"\"\n", " i = 0\n", " while i < len(s):\n", " c = s[i]\n", " if c == '+':\n", " t += ' '\n", " elif c == '%' and i + 2 < len(s): # <--- *** FIX ***\n", " digit_high, digit_low = s[i + 1], s[i + 2]\n", " i += 2\n", " if digit_high in hex_values and digit_low in hex_values:\n", " v = hex_values[digit_high] * 16 + hex_values[digit_low]\n", " t += chr(v)\n", " else:\n", " raise ValueError(\"Invalid encoding\")\n", " else:\n", " t += c\n", " i += 1\n", " return t\n" ] }, { "cell_type": "code", "execution_count": 55, "metadata": { "slideshow": { "slide_type": "subslide" }, "solution2": "hidden" }, "outputs": [], "source": [ "assert fixed_cgi_decode('%') == '%'" ] }, { "cell_type": "code", "execution_count": 56, "metadata": { "slideshow": { "slide_type": "fragment" }, "solution2": "hidden" }, "outputs": [], "source": [ "assert fixed_cgi_decode('%4') == '%4'" ] }, { "cell_type": "code", "execution_count": 57, "metadata": { "slideshow": { "slide_type": "fragment" }, "solution2": "hidden" }, "outputs": [], "source": [ "assert fixed_cgi_decode('%40') == '@'" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" }, "solution2": "hidden" }, "source": [ "Here's the test:" ] }, { "cell_type": "code", "execution_count": 58, "metadata": { "slideshow": { "slide_type": "fragment" }, "solution2": "hidden" }, "outputs": [], "source": [ "for i in range(trials):\n", " try:\n", " s = fuzzer()\n", " fixed_cgi_decode(s)\n", " except ValueError:\n", " pass" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" }, "solution2": "hidden" }, "source": [ "For the C variant, the following will do:" ] }, { "cell_type": "code", "execution_count": 59, "metadata": { "slideshow": { "slide_type": "fragment" }, "solution2": "hidden" }, "outputs": [], "source": [ "cgi_c_code = cgi_c_code.replace(\n", " r\"if (*s == '%')\", # old code\n", " r\"if (*s == '%' && s[1] != '\\0' && s[2] != '\\0')\" # new code\n", ")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" }, "solution2": "hidden" }, "source": [ "Go back to the above compilation commands and recompile `cgi_decode`." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "### Exercise 2: Branch Coverage\n", "\n", "Besides statement coverage, _branch coverage_ is one of the most frequently used criteria to determine the quality of a test. In a nutshell, branch coverage measures how many different _control decisions_ are made in code. In the statement\n", "\n", "```python\n", "if CONDITION:\n", " do_a()\n", "else:\n", " do_b()\n", "```\n", "\n", "for instance, both the cases where `CONDITION` is true (branching to `do_a()`) and where `CONDITION` is false (branching to `do_b()`) have to be covered. This holds for all control statements with a condition (`if`, `while`, etc.).\n", "\n", "How is branch coverage different from statement coverage? In the above example, there is actually no difference. In this one, though, there is:\n", "\n", "```python\n", "if CONDITION:\n", " do_a()\n", "something_else()\n", "```\n", "\n", "Using statement coverage, a single test case where `CONDITION` is true suffices to cover the call to `do_a()`. Using branch coverage, however, we would also have to create a test case where `do_a()` is _not_ invoked." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Using our `Coverage` infrastructure, we can simulate branch coverage by considering _pairs of subsequent lines executed_. The `trace()` method gives us the list of lines executed one after the other:" ] }, { "cell_type": "code", "execution_count": 60, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "[('cgi_decode', 9),\n", " ('cgi_decode', 10),\n", " ('cgi_decode', 11),\n", " ('cgi_decode', 12),\n", " ('cgi_decode', 15)]" ] }, "execution_count": 60, "metadata": {}, "output_type": "execute_result" } ], "source": [ "with Coverage() as cov:\n", " cgi_decode(\"a+b\")\n", "trace = cov.trace()\n", "trace[:5]" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" }, "solution2": "hidden", "solution2_first": true }, "source": [ "#### Part 1: Compute branch coverage\n", "\n", "Define a function `branch_coverage()` that takes a trace and returns the set of pairs of subsequent lines in a trace – in the above example, this would be \n", "\n", "```python\n", "set(\n", "(('cgi_decode', 9), ('cgi_decode', 10)),\n", "(('cgi_decode', 10), ('cgi_decode', 11)),\n", "# more_pairs\n", ")\n", "```\n", "\n", "Bonus for advanced Python programmers: Define `BranchCoverage` as a subclass of `Coverage` and make `branch_coverage()` as above a `coverage()` method of `BranchCoverage`." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" }, "solution": "hidden", "solution2": "hidden" }, "source": [ "**Solution.** Here's a simple definition of `branch_coverage()`:" ] }, { "cell_type": "code", "execution_count": 61, "metadata": { "slideshow": { "slide_type": "fragment" }, "solution2": "hidden" }, "outputs": [], "source": [ "def branch_coverage(trace):\n", " coverage = set()\n", " past_line = None\n", " for line in trace:\n", " if past_line is not None:\n", " coverage.add((past_line, line))\n", " past_line = line\n", "\n", " return coverage" ] }, { "cell_type": "code", "execution_count": 62, "metadata": { "slideshow": { "slide_type": "subslide" }, "solution2": "hidden" }, "outputs": [ { "data": { "text/plain": [ "{(('cgi_decode', 9), ('cgi_decode', 10)),\n", " (('cgi_decode', 10), ('cgi_decode', 11)),\n", " (('cgi_decode', 11), ('cgi_decode', 12)),\n", " (('cgi_decode', 12), ('cgi_decode', 15)),\n", " (('cgi_decode', 15), ('cgi_decode', 16)),\n", " (('cgi_decode', 16), ('cgi_decode', 17)),\n", " (('cgi_decode', 17), ('cgi_decode', 18)),\n", " (('cgi_decode', 17), ('cgi_decode', 32)),\n", " (('cgi_decode', 18), ('cgi_decode', 19)),\n", " (('cgi_decode', 19), ('cgi_decode', 20)),\n", " (('cgi_decode', 19), ('cgi_decode', 21)),\n", " (('cgi_decode', 20), ('cgi_decode', 31)),\n", " (('cgi_decode', 21), ('cgi_decode', 30)),\n", " (('cgi_decode', 30), ('cgi_decode', 31)),\n", " (('cgi_decode', 31), ('cgi_decode', 17)),\n", " (('cgi_decode', 32), ('__exit__', 25))}" ] }, "execution_count": 62, "metadata": {}, "output_type": "execute_result" } ], "source": [ "branch_coverage(trace)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" }, "solution2": "hidden" }, "source": [ "Here's a definition as a class:" ] }, { "cell_type": "code", "execution_count": 63, "metadata": { "slideshow": { "slide_type": "fragment" }, "solution2": "hidden" }, "outputs": [], "source": [ "class BranchCoverage(Coverage):\n", " def coverage(self):\n", " \"\"\"The set of executed line pairs\"\"\"\n", " coverage = set()\n", " past_line = None\n", " for line in self.trace():\n", " if past_line is not None:\n", " coverage.add((past_line, line))\n", " past_line = line\n", "\n", " return coverage" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" }, "solution2": "hidden", "solution2_first": true }, "source": [ "#### Part 2: Comparing statement coverage and branch coverage\n", "\n", "Use `branch_coverage()` to repeat the experiments in this chapter with branch coverage rather than statement coverage. Do the manually written test cases cover all branches?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" }, "solution2": "hidden" }, "source": [ "**Solution.** Let's repeat the above experiments with `BranchCoverage`:" ] }, { "cell_type": "code", "execution_count": 64, "metadata": { "slideshow": { "slide_type": "fragment" }, "solution2": "hidden" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{(('cgi_decode', 19), ('cgi_decode', 20)), (('cgi_decode', 20), ('cgi_decode', 31)), (('cgi_decode', 10), ('cgi_decode', 11)), (('cgi_decode', 18), ('cgi_decode', 19)), (('cgi_decode', 19), ('cgi_decode', 21)), (('cgi_decode', 17), ('cgi_decode', 32)), (('cgi_decode', 9), ('cgi_decode', 10)), (('cgi_decode', 17), ('cgi_decode', 18)), (('cgi_decode', 12), ('cgi_decode', 15)), (('cgi_decode', 11), ('cgi_decode', 12)), (('cgi_decode', 30), ('cgi_decode', 31)), (('cgi_decode', 21), ('cgi_decode', 30)), (('cgi_decode', 15), ('cgi_decode', 16)), (('cgi_decode', 31), ('cgi_decode', 17)), (('cgi_decode', 16), ('cgi_decode', 17)), (('cgi_decode', 32), ('__exit__', 25))}\n" ] } ], "source": [ "with BranchCoverage() as cov:\n", " cgi_decode(\"a+b\")\n", "\n", "print(cov.coverage())" ] }, { "cell_type": "code", "execution_count": 65, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" }, "solution2": "hidden" }, "outputs": [ { "data": { "text/plain": [ "{(('cgi_decode', 19), ('cgi_decode', 20)),\n", " (('cgi_decode', 20), ('cgi_decode', 31))}" ] }, "execution_count": 65, "metadata": {}, "output_type": "execute_result" } ], "source": [ "with BranchCoverage() as cov_plus:\n", " cgi_decode(\"a+b\")\n", "with BranchCoverage() as cov_standard:\n", " cgi_decode(\"abc\")\n", "\n", "cov_plus.coverage() - cov_standard.coverage()" ] }, { "cell_type": "code", "execution_count": 66, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" }, "solution2": "hidden" }, "outputs": [], "source": [ "with BranchCoverage() as cov_max:\n", " cgi_decode('+')\n", " cgi_decode('%20')\n", " cgi_decode('abc')\n", " try:\n", " cgi_decode('%?a')\n", " except:\n", " pass" ] }, { "cell_type": "code", "execution_count": 67, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" }, "solution2": "hidden" }, "outputs": [ { "data": { "text/plain": [ "{(('cgi_decode', 21), ('cgi_decode', 22)),\n", " (('cgi_decode', 22), ('cgi_decode', 23)),\n", " (('cgi_decode', 23), ('cgi_decode', 24)),\n", " (('cgi_decode', 24), ('cgi_decode', 25)),\n", " (('cgi_decode', 24), ('cgi_decode', 28)),\n", " (('cgi_decode', 25), ('cgi_decode', 26)),\n", " (('cgi_decode', 26), ('cgi_decode', 31)),\n", " (('cgi_decode', 28), ('__exit__', 25)),\n", " (('cgi_decode', 32), ('cgi_decode', 9))}" ] }, "execution_count": 67, "metadata": {}, "output_type": "execute_result" } ], "source": [ "cov_max.coverage() - cov_plus.coverage()" ] }, { "cell_type": "code", "execution_count": 68, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" }, "solution2": "hidden" }, "outputs": [ { "data": { "text/plain": [ "'!7#%\"*#0=)$;%6*;>638:*>80\"=(/*:-(2<4 !:5*6856&?\"\"11<7+%<%7,4.8,*+&,,$,.\"'" ] }, "execution_count": 68, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sample" ] }, { "cell_type": "code", "execution_count": 69, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" }, "solution2": "hidden" }, "outputs": [ { "data": { "text/plain": [ "{(('cgi_decode', 9), ('cgi_decode', 10)),\n", " (('cgi_decode', 10), ('cgi_decode', 11)),\n", " (('cgi_decode', 11), ('cgi_decode', 12)),\n", " (('cgi_decode', 12), ('cgi_decode', 15)),\n", " (('cgi_decode', 15), ('cgi_decode', 16)),\n", " (('cgi_decode', 16), ('cgi_decode', 17)),\n", " (('cgi_decode', 17), ('cgi_decode', 18)),\n", " (('cgi_decode', 18), ('cgi_decode', 19)),\n", " (('cgi_decode', 19), ('cgi_decode', 20)),\n", " (('cgi_decode', 19), ('cgi_decode', 21)),\n", " (('cgi_decode', 20), ('cgi_decode', 31)),\n", " (('cgi_decode', 21), ('cgi_decode', 22)),\n", " (('cgi_decode', 21), ('cgi_decode', 30)),\n", " (('cgi_decode', 22), ('cgi_decode', 23)),\n", " (('cgi_decode', 23), ('cgi_decode', 24)),\n", " (('cgi_decode', 24), ('cgi_decode', 28)),\n", " (('cgi_decode', 28), ('__exit__', 25)),\n", " (('cgi_decode', 30), ('cgi_decode', 31)),\n", " (('cgi_decode', 31), ('cgi_decode', 17))}" ] }, "execution_count": 69, "metadata": {}, "output_type": "execute_result" } ], "source": [ "with BranchCoverage() as cov_fuzz:\n", " try:\n", " cgi_decode(s)\n", " except:\n", " pass\n", "cov_fuzz.coverage()" ] }, { "cell_type": "code", "execution_count": 70, "metadata": { "slideshow": { "slide_type": "subslide" }, "solution2": "hidden" }, "outputs": [ { "data": { "text/plain": [ "{(('cgi_decode', 17), ('cgi_decode', 32)),\n", " (('cgi_decode', 24), ('cgi_decode', 25)),\n", " (('cgi_decode', 25), ('cgi_decode', 26)),\n", " (('cgi_decode', 26), ('cgi_decode', 31)),\n", " (('cgi_decode', 32), ('cgi_decode', 9))}" ] }, "execution_count": 70, "metadata": {}, "output_type": "execute_result" } ], "source": [ "cov_max.coverage() - cov_fuzz.coverage()" ] }, { "cell_type": "code", "execution_count": 71, "metadata": { "slideshow": { "slide_type": "subslide" }, "solution2": "hidden" }, "outputs": [], "source": [ "def population_branch_coverage(population, function):\n", " cumulative_coverage = []\n", " all_coverage = set()\n", "\n", " for s in population:\n", " with BranchCoverage() as cov:\n", " try:\n", " function(s)\n", " except:\n", " pass\n", " all_coverage |= cov.coverage()\n", " cumulative_coverage.append(len(all_coverage))\n", "\n", " return all_coverage, cumulative_coverage" ] }, { "cell_type": "code", "execution_count": 72, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" }, "solution2": "hidden" }, "outputs": [], "source": [ "all_branch_coverage, cumulative_branch_coverage = population_branch_coverage(\n", " hundred_inputs(), cgi_decode)" ] }, { "cell_type": "code", "execution_count": 73, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [], "source": [ "%matplotlib inline" ] }, { "cell_type": "code", "execution_count": 74, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [], "source": [ "import matplotlib.pyplot as plt" ] }, { "cell_type": "code", "execution_count": 75, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" }, "solution2": "hidden" }, "outputs": [ { "data": { "text/plain": [ "Text(0,0.5,'line pairs covered')" ] }, "execution_count": 75, "metadata": {}, "output_type": "execute_result" }, { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYIAAAEWCAYAAABrDZDcAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4zLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvIxREBQAAIABJREFUeJzt3Xm8HFWZ//HPNxskJAhIEAwJEUUGVAySQRAXxAXFDR0dZVBwmYmOOoDDuIE/13HcER3XKBhQRFRQIW4gqyigCYY1IMoyBCIESUgg93K35/fHOZ10Ot19+ya3bt/q/r5fr/u6XftTXdX1VJ2qOkcRgZmZda8J7Q7AzMzay4nAzKzLORGYmXU5JwIzsy7nRGBm1uWcCMzMupwTQQEkhaQntTuOspE0VdIFkh6S9KNRnO/Rki7cgukuk/SvoxVHi8tsed+RtI2kmyXtmrtPkfSOUYjhOZJubTJ8bo5z0tYuazRIOlTSijFa1sOS9hyLZY2ljkkEku6U1JM31GpJP5c0u91x2Yi8Fngc8NiIeN1ozTQizoqIF4/W/MaRBcAVEfG33P054GRJU7ZmphHx24jYu9Kdf1sv3Jp5doqImB4Rtxe9nLE+CemYRJC9IiKmA7sB9wH/22hESRPHLKpxbLyc1WV7AH+OiIF2B1ISbwe+W+mIiJXALcAr2xZRC/zbG4cioiP+gDuBF1Z1H0E6qFS6FwFfB34BPAK8EHgZ8CdgLXA38NGq8ecCARwL/B/wAHBy1fCJwEnAX4F1wFJgdh4WwDuA24DVwFcBNYi72XyeBfwReCj/f1bu/wZgSc183gOcnz9vA3w+x30f8A1gah52KLACeD/wN9KBZEdgMbAqx7sY2L1q3k8Arsjx/Savz/eqhh8E/B5YA1wHHNpkO+0DXJbHvQl4Ze7/MaAP6AceBt42wu/qxcCt+bv6GnA58K952JuBK1vYh15EOpA+BHyleh55+FuB5fk7+jWwR9WwpwAXAQ/m7/ykqm1xKnBv/jsV2KZquvcCK/Owt+Z950ktbMc5QA8wqWYdTga+02D9zgBOzJ9n5WW9M3c/Kceuyj6S+38XGMrLehh4H8P8NuosdxGj+9ubmue5Grg5f4crhtvHqmL5GvDLvD6/A3bN22V13v77N1mX6u2ziPRb+Dlpf7wGeGLNuMcBt+d1+BwwIQ/7KJv+hirrPAn4JDAI9OYYv5K3yxeB+0n75/XAU0ft+DlaM2r3H1WJAJiWd/oza3aAh4BDSFdC2+Yd/mm5ez/Sj+3Img3zrbzjPR14FNin6gd8A7B33khPJxVpVHaAxcAOpB/sKuAlDeKuOx9gp7xjvinvHEfl7sfm9VsH7FU1nz8Cb8ifTwXOz/OYAVwAfCoPOxQYAD5DOtBMzfP8pzzfGcCPgJ9Wzfsq0gFpCvBs0o/3e1UHlL+TEu8E0sH078DMOus6GfgL6WA+BTgsr8fe9X4cI/iuds4xvSZ/V8eTEkrLiaBqHq/Ncb4nf0+VeRyZY98nL+NDwO/zsBmkg/mJpP1qBvDMPOzjwNXALsBMUsL8RB72EtI+91RgO+D7bHqgabYdXwbcVGc9XgNc22Ad3wpckD//CymhnlM17GdV+0j1gfVONj3JmkuT30ad5S5idH97nwZ+m7+X2cCNbExcw+1ji0gH5QNyHJcAdwDHkE40/hu4tMl+UpsIHgQOzPvEWcAPasa9NMc5B/gzG/enj9IgEeTuy9j0JORw0onPDqR9fx9gt1E7fo7Vgbrov7yzPkw6CxggnWE9rWZnPHOYeZwKfLFmw1SfGf+BjQfbW4FXNdlZnl3V/UPgAw3GrTsfUgL4Q02/q4A358/fAz6cP++Vd/ZpeSd5hE3PTA4G7sifDyWdeW/b5HuYB6zOn+fk73Na1fDvsTERvB/4bs30vwaOrTPf55CuQiZU9TubfDZY++MYwXd1DHBVVbdIZ5kjSQTHAFfXzGNF1Tx+SdVVCukAtp5UnHUU8KcG8/0rcERV9+HAnfnz6cCnq4Y9Oe87T2phOx5dHW/VOC8Cbm8QyxNJv48JpKuLt7PxAHoG8J9V+0griaDub6POchcxur+926k6sSLdK6msx3D72CLgW1XD/gNYXtX9NGBNkzhrE8G3q4YdAdxSM251nO8ELq63rzN8IjiMlEgOql630frrtHsER0bEDqQz3XcDl1eeqMjurh5Z0jMlXSpplaSHSMU5O9fM829Vn9cD0/Pn2aQfeSONpqvVaD6PB+6q6XcX6Qwc0tnjUfnzv5DO4NeTzjqnAUslrZG0BvhV7l+xKiJ6Kx2Spkn6pqS7JK0lFQPtkMtyHw88mOddUf097gG8rrKsvLxnk+7T1FunuyNiqME6DafZd7Uhpki/nJE+RVJvHrXr+aWqdawUo8xqEldlvtXb8a7cb7Nl1ow33HZcTbpKqDWDdLDfTET8lXSyNI90wFwM3Ctpb+B5pKKwkWh1H4fR/e01+95a2cfuq/rcU6e72XrUGu47qI3z8WyBiLiEVET0VeA+SQslbb8l86qn0xIBABExGBHnkcrZnl09qGbU75MuvWdHxGNIZ0lqcTF3k86wtlaj+dxLOvhUmwPckz9fCOwsaR4pIXw/93+AtDM/JSJ2yH+PiXQTvaL2eziRVNzyzIjYHnhu7i9SkcdOkqZVjV/9NNbdpCuCHar+touITzdYp9mSqve76nUaTqPvaiWwe6VDkqq7W7SSqvXK86hdz7fXrOfUiPh9k7hg8+04J/fbbJl5WMVw2/F6YM86N/v3Id2naeRyUvHXlIi4J3cfQ7pPtKzBNLX7y5YYzd9es+9ta/ex0VYbZ2XbP0JK9BXVJ6xQ5zuPiC9HxAGk+1FPJhWVjoqOTARKXkXauZc3GXUG6Wy3V9KBpDPrVn0b+ISkvfLy9pP02C0It9F8fgE8WdK/SJok6fXAvqSzOCI9WfNj0g2onUg3KslnQt8CvihpFwBJsyQd3iSGGaSDzhpJOwEfqQyIiLuAJcBHJU2RdDDwiqppvwe8QtLhkiZK2jY/113vQHwN6QfwPkmTJR2a5/WDrfyufg48TdKR+cD4Ljb/YQ3n58BTJL0mz+O4mnl8A/igpKcASHqMpMojrouBXSWdkJ/tnyHpmXnY2cCHJM2UtDPwYdJ3BqnI8M2S9s2Jtvp7b7odI2IF6WGEA2vW43mkYqxGLiddLV+Ruy8jFY9cGRGDDaa5DxjtZ+e35rf3Q9K22DHvZ/9RNWxr97HR9t4c52zSvatzcv9lwHMlzZH0GOCDNdNt8p1L+sd8FTWZtH69pBPdUdFpieACSQ+Tbvp9klROfVOT8d8JfFzSOtIP9IcjWNYpefwL8/JOI93YGqm684mIvwMvJ52t/530tMbLI+KBqmm/T3oC40ex6SOX7yfdMLs6F/X8hnTG38ipOfYHSDc2f1Uz/GhS+fTfSTfTziHdvCMi7gZeRbo5t4p0dvxe6uxbEdFHerTxpXlZXwOOiYhbmsRWrdF39QDwOuCzOcZ9Scnr0RbnS9U8Pp3nsRfpiZLK8J+QbrD/IH+nN+b1ICLWkcrmX0EqKrgNeH6e9L9zLNeTbnRfm/sREb8kffeXkLbXJTVhDbcdv0m6lwSApN3yuv+0yapeTjoIVxLBlaQz0ysaTgGfIiWzNZL+q8l4I7E1v72PkYpZ7iDtC9WP0G7tPjbafka6ybuMdLJxWo7zItLv6Po8fHHNdF8CXqv0TtSXge1JJwarSev+d9IDHKNC+UaEWcsknUO6KfaRYUdug1wssAI4OiIubXc8RZG0DekRzBdExEpJXwD+GhFfa3NoRnpLnPRk31/aHctwnAhsWJL+kXRz9A7S8/o/BQ6OiD+1NbAqucjkGlIR13tJxUN7RkRPWwOzrlWmRDCe3iq18WtX4DzSM/srgH8fT0kgO5hUVDaF9JLRkbVJQNJzaFB+XnMz3ayr+IrAzKzLddrNYjMzG6FSFA3tvPPOMXfu3HaHYWZWKkuXLn0gImYON14pEsHcuXNZsmRJu8MwMysVSbW1E9TloiEzsy7nRGBm1uWcCMzMupwTgZlZl3MiMDPrcoUlAkmzc33jyyXdJOn43P+jku6RtCz/HVFUDGZmNrwiHx8dILWPeq2kGaQGNi7Kw74YEaNWc56ZmW25whJBRKwkNSBBRKyTtJzWW6KyDjIwOMTpv7uDh3sHhh/ZzDbx6mfszhN23q7QZYzJC2WS5gL7k2qHPAR4t6RjSPW0nxgRq+tMs4DUFilz5sypHWwl8qe71/A/v0jVwavVNqjMDIBn7LFj+ROBpOnAucAJEbFW0teBT5CaYvsE8AXgrbXTRcRCYCHA/PnzXTNeid39YGru+NL/OrTwHdrMRq7Qp4Zys2rnAmflNoSJiPtym8KVpvhqm9qzDrNidaoNerfHbNvmSMysniKfGhKpWbblEXFKVf/dqkZ7NanJP+tgK1avZ5cZ27Dt5IntDsXM6iiyaOgQUnuqN0halvudBBwlaR6paOhO4O0FxmDjwIrVPey+45Y052xmY6HIp4auBOrdGvxFUcu08WnF6h7mzd6h3WGYWQN+s9gKNTgU3LvGVwRm45kTgRXqvrW9DAwFu+84rd2hmFkDTgRWqHvWpCeGfEVgNn45EVihVqxO7xDMciIwG7ecCKxQKx5MVwSzdnAiMBuvnAisUCtW9zDT7xCYjWtOBFaoFWvW+/6A2TjnRGCFSi+T+Ykhs/HMicAKM+R3CMxKwYnACnP/ukfpHwzfKDYb55wIrDCVR0d9RWA2vjkRWGEq1U/7HoHZ+OZEYIXxFYFZOTgRWGFWrO5h5+l+h8BsvHMisMK4HQKzcnAisMLcs6bHdQyZlUCRTVXOlnSppOWSbpJ0fM3w/5IUknYuKgZrn6Gh4B5fEZiVQpFNVQ4AJ0bEtZJmAEslXRQRN0uaDbwI+L8Cl29ttOrhR+kbHPITQ2YlUGRTlSuBlfnzOknLgVnAzcAXgfcBPytq+e12yoW3cumtq9odRtv09A8CfmLIrAyKvCLYQNJcYH/gGkmvBO6JiOukek0ab5hmAbAAYM6cOWMQ5ej66bJ76RsYYt/Hb9/uUNpmn92254A9dmx3GGY2jMITgaTpwLnACaTiopOBFw83XUQsBBYCzJ8/P4qMsQjr+wZ50b6P41OveVq7QzEza6rQp4YkTSYlgbMi4jzgicATgOsk3QnsDlwradci42iH3v5Bpvr5eTMrgcKuCJTKfU4DlkfEKQARcQOwS9U4dwLzI+KBouJoh4hgfd8A06Y4EZjZ+FfkFcEhwJuAwyQty39HFLi8caNvcIihgKlOBGZWAkU+NXQl0PhucBpnblHLb6eevvTEjIuGzKwM/GZxAdbnROCiITMrAyeCAlSeoXfRkJmVgRNBAVw0ZGZl4kRQgI1FQ2Pyvp6Z2VZxIijAxqIhf71mNv75SFWAnr4BAKZO9hWBmY1/TgQFqFwR+KkhMysDJ4ICVO4R+KkhMysDJ4IC9DgRmFmJOBEUwI+PmlmZOBEUYH3/IJMniskT/fWa2fjnI1UBevpcBbWZlYcTQQF6+gZ9f8DMSsOJoADr+wf9VrGZlYYTQQFcNGRmZeJEUICe/gEXDZlZaRSWCCTNlnSppOWSbpJ0fO7/CUnX5xbLLpT0+KJiaJf1fYN+q9jMSqPIK4IB4MSI2Ac4CHiXpH2Bz0XEfhExD1gMfLjAGNqip2+QbV00ZGYlUVgiiIiVEXFt/rwOWA7Mioi1VaNtB0RRMbRLT7+vCMysPMbk0RZJc4H9gWty9yeBY4CHgOc3mGYBsABgzpw5YxHmqHHRkJmVSeE3iyVNB84FTqhcDUTEyRExGzgLeHe96SJiYUTMj4j5M2fOLDrMUdXroiEzK5FCE4GkyaQkcFZEnFdnlO8D/1RkDGMtIvJ7BE4EZlYORT41JOA0YHlEnFLVf6+q0V4J3FJUDO3QPxgMDoVfKDOz0ijyaHUI8CbgBknLcr+TgLdJ2hsYAu4C3lFgDGOuUvOoi4bMrCwKSwQRcSWgOoN+UdQyx4P1/amZShcNmVlZ+M3iUea2CMysbBpeEUh6TbMJG9z87XpuptLMyqZZ0dAr8v9dgGcBl+Tu5wOXAU4EdbjhejMrm4aJICLeAiBpMbBvRKzM3bsBXx2b8MrHRUNmVjat3COYW0kC2X3AkwuKp/RcNGRmZdPKU0OXSfo1cDapXqA3AJcWGlWJ9W4oGvJ7BGZWDsMerSLi3ZJeDTw391oYET8pNqzyWu+iITMrmVZPW68F1kXEbyRNkzQj1yhqNdb3pfcIXDRkZmUx7D0CSf8G/Bj4Zu41C/hpkUGVWaVoyFcEZlYWrdwsfhepuohKzaG3kR4ptTrW9w0yaYKYMsnv6plZObRytHo0IvoqHZIm0YGNyYyW9X2DLhYys1JpJRFcLukkYKqkFwE/Ai4oNqzy6u0fdLGQmZVKK4ngA8Aq4Abg7aRK4z5UZFBl5tbJzKxsmj41JGkicEZEvBH41tiEVG49/YNM9TsEZlYiTa8IImIQmClpyhjFU3o9fYNMnewbxWZWHq2cut4J/E7S+cAjlZ7VrY7VI2k2cCawK6kRmoUR8SVJnyNVaNcH/BV4S0Ss2bLwx5/1fQN+q9jMSqWVU9d7gcV53BlVf8MZAE6MiH2Ag4B3SdoXuAh4akTsB/wZ+OCWBD5e9fQPuXUyMyuVVqqY+BiApO0i4pHhxq+abiWwMn9eJ2k5MCsiLqwa7WrgtSMLeXzr6RvwzWIzK5VW3iw+WNLNwPLc/XRJXxvJQiTNBfYHrqkZ9Fbglw2mWSBpiaQlq1atGsni2spPDZlZ2bRSNHQqcDjwd4CIuI6NFdANS9J04FzghIhYW9X/ZFLx0Vn1pouIhRExPyLmz5w5s9XFtV1P/6CLhsysVFq6qxkRd0ubtEM/2Mp0kiaTksBZ1U1bSjoWeDnwgojoqLeUe3xFYGYl00oiuFvSs4DIj5EeRy4makYpc5wGLK9+wkjSS4D3A8+LiPVbFvb41D84xMBQOBGYWam0UjT0DlLFc7OAFcC83D2cQ4A3AYdJWpb/jgC+Qnrq6KLc7xtbFvr4U2mLwEVDZlYmrVwRKCKOHumMI+JKQHUG/WKk8yqLSnvFfo/AzMqklSuC30u6UNLbJO1QeEQl1lNpi2CK3yw2s/IY9ogVEXuRKpl7CnCtpMWS3lh4ZCW0oXWyyb4iMLPyaOnUNSL+EBH/CRwIPAicUWhUJbWxaMj3CMysPFp5oWx7ScdK+iXwe9LbwgcWHlkJbSwaciIws/JopQzjOlIbxR+PiKsKjqfUKk8NuWEaMyuTVhLBnhERkmZImh4RDxceVUm5aMjMyqiVewRPkfQn4EbgZklLJT214LhKyUVDZlZGrSSChcB/RsQeETEHODH3sxqVoqFpfmrIzEqklUSwXURcWumIiMuA7QqLqMR68xXBtn6PwMxKpJVT19sl/T/gu7n7jcAdxYVUXuv7Bpg4QUyZ6ERgZuXRyhHrrcBM4Lz8tzPwliKDKqv1fYNMmzyRmppazczGtVZaKFtNqnHUhtHbP8i2vlFsZiXTygtlF1XXMSRpR0m/LjascnLrZGZWRq0UDe0cEWsqHfkKYZfiQiqv9X2DfpnMzEqnlUQwJGlOpUPSHkBHtSo2Wnr7B/0OgZmVTitPDZ0MXCnp8tz9XGBBcSGVl4uGzKyMWqmG+lfAM4BzgB8CB0TEsPcIJM2WdKmk5ZJuknR87v+63D0kaf7WrsB40uOiITMroVYbr38AWDzCeQ8AJ0bEtZJmAEslXUSqquI1wDdHOL9xr6d/kKlunczMSqawo1ZErCRVWU1ErJO0HJgVERcBbX3W/q+rHubU39zGwODQqM535UM9HDh3p1Gdp5lZ0cbk9FXSXGB/4JoRTLOAfC9izpw5w4w9MhfdfB8XXHcve+0yndHMR3vstB3PffLM0ZuhmdkYGDYRSHoisCIiHpV0KLAfcGb1I6XDTD8dOBc4ISLWthpYRCwkV243f/78UX1KaW1PP5MmiAvf81y/BWxmXa+Vx0fPBQYlPQk4DXgC8P1WZi5pcp7+rIg4b4ujHGVre/vZfupkJwEzM1p8jyAiBoBXA6dGxHuA3YabSOkoexqwPCJO2bowR9fangG239Y3dc3MoLV7BP2SjgKOBV6R+01uYbpDgDcBN0halvudBGwD/C+pIrufS1oWEYePLOytU7kiMDOz1hLBW4B3AJ+MiDskPQH43nATRcSVQKOyl5+0HuLoW9vTz/bbOhGYmcEwiUDSROCkiHhjpV9E3AF8uujAirS2d4BdH7Ntu8MwMxsXmt4jiIhBYKakKWMUz5jwFYGZ2UatFA3dCfxO0vnAI5We4+0G8Ej4HoGZ2UatJIJ7898EYEax4RSvb2CI3v4hPzVkZpa10kLZx8YikLGyrrcfwFcEZmZZw0Qg6dSIOEHSBdRpfyAiXlloZAVZ2zsAwAxfEZiZAc2vCL6b/39+LAIZK2t78hWBbxabmQFNEkFELM3/L280ThmtddGQmdkmWql0bi/gU8C+wIaH7yNizwLjKszanlQ05CsCM7OklbqGvgN8ndTQzPOBM9lYbFQ6G68IfI/AzAxaSwRTI+JiQBFxV0R8FDis2LCK43sEZmabauW0uFfSBOA2Se8G7gF2KTas4qzt7WfiBLmReTOzrJUrghOAacBxwAGkGkWPLTKoIlWqoHZbBGZmSSsvlP0RIF8VHBcR6wqPqkCuXsLMbFPDXhFImi/pBuB6UtsC10k6oPjQiuEK58zMNtXKPYLTgXdGxG8BJD2b9CTRfkUGVpS1vQN+YsjMrEor9wjWVZIAbGhwZtjiIUmzJV0qabmkmyQdn/vvJOkiSbfl/ztuefgj5ysCM7NNtZII/iDpm5IOlfQ8SV8DLpP0DEnPaDLdAHBiROwDHAS8S9K+wAeAiyNiL+Di3D1m1vY6EZiZVWuljGRe/v+Rmv7PIlVGV/edgohYCazMn9dJWg7MAl4FHJpHOwO4DHj/SILeGmt7XDRkZlatlaeGnr+1C5E0F9gfuAZ4XE4SRMRKSXXfSZC0AFgAMGfOnK0NAUhtEfT0DzLDVwRmZhu0UjS0VSRNB84FToiIta1OFxELI2J+RMyfOXPmqMSyoS0CV0FtZrZBoYlA0mRSEjgrIs7Lve+TtFsevhtwf5ExVFuX2yLwewRmZhsVlgiUXt09DVhe077x+Wx8M/lY4GdFxVBrQ4VzLhoyM9uglRfKpkn6f5K+lbv3kvTyFuZ9CKk6isMkLct/RwCfBl4k6TbgRbl7TGyogtpXBGZmG7RSWP4dYClwcO5eAfwIWNxsovy+QaMKfV7QaoCjyVVQm5ltrpWioSdGxGeBfoCI6KHxAX5ccxXUZmabayUR9EmaSm7AXtITgUcLjaogbqbSzGxzrZSRfAT4FTBb0lmksv83FxlUUdb2DDBBsJ3bIjAz26CVF8ouknQtqZoIAcdHxAOFR1aAShXUbovAzGyjVu+abguszuPvK4mIuKK4sIrhCufMzDY3bCKQ9Bng9cBNwFDuHUD5EoGroDYz20wrR8Ujgb0jopQ3iKv5isDMbHOtPDV0O9ARR09XQW1mtrlWrgjWA8skXUzVY6MRcVxhURVkbc8AM1zhnJnZJlo5Kp6f/0rPDdebmW2ulcdHzxiLQIrWPzjE+r5BFw2ZmdVomAgk/TAi/lnSDeS3iqtFRKkar99YBbWLhszMqjU7Kh6f/7dS0+i453qGzMzqa5gIqpqTvGvswimO6xkyM6uvWdHQOuoUCZGqmYiI2L6wqAqwoWjITw2ZmW2i4XsEETEjIrav8zejlSQg6XRJ90u6sarf0yVdJekGSRdIGrNksqFoyFcEZmabKLLN4kXAS2r6fRv4QEQ8DfgJ8N4Cl78JFw2ZmdVXWCLIldI9WNN7bzbWUXQR8E9FLb/WhmYqXTRkZraJIq8I6rkReGX+/DpgdqMRJS2QtETSklWrVm31gtf29iPBdlOcCMzMqo11Ingr8C5JS4EZQF+jESNiYUTMj4j5M2fO3OoFVyqcmzDBbRGYmVUb09PjiLgFeDGApCcDLxurZbsKajOz+sb0ikDSLvn/BOBDwDfGatmugtrMrL7CEoGks4GrgL0lrZD0NuAoSX8GbgHuBb5T1PJrre3td82jZmZ1FHZkjIijGgz6UlHLbGZtzwB7PHZaOxZtZjaujfXN4rZxFdRmZvV1TyLwPQIzs7q6IhEMDA7xSN+gnxoyM6ujKxLBw49W3ir2FYGZWa2uSAQbqpfwPQIzs810RyKoVDjnx0fNzDbTHYnAVVCbmTXUHYmg181Umpk10h2JoMcN15uZNdIdicCN0piZNdQdiaAntUUw3W0RmJltpjsSQe8AM7aZ5LYIzMzq6I5E0NPPDN8oNjOrqzsSgSucMzNrqEsSwYBfJjMza6A7EkGPrwjMzBopsoWy0yXdL+nGqn7zJF0taZmkJZIOLGr51db1DvhlMjOzBoq8IlgEvKSm32eBj0XEPODDubtw6YrARUNmZvUUlggi4grgwdrewPb582NI7RYXanAoWPeorwjMzBoZ69PkE4BfS/o8KQk9q9GIkhYACwDmzJmzxQt8uNdVUJuZNTPWN4v/HXhPRMwG3gOc1mjEiFgYEfMjYv7MmTO3eIGugtrMrLmxTgTHAuflzz8CCr9Z/JCroDYza2qsE8G9wPPy58OA24peoKugNjNrrrDyEklnA4cCO0taAXwE+DfgS5ImAb3kewBFchXUZmbNFXZ0jIijGgw6oKhl1uMrAjOz5jr+zeJ1fmrIzKypjk8ElfaKp2/joiEzs3o6PxH09jNjm0lMdFsEZmZ1dX4i6BlwsZCZWROdnwh6+5nhl8nMzBrq/ETgKqjNzJrq/ETgKqjNzJrq/ETgKqjNzJrq/ETQ2+8rAjOzJjo6EQwNBQ8/6qeGzMya6ehEsO7RASJcBbWZWTOdnQh6XQW1mdlwOjoRbKh51PcIzMwa6uxEsOGKwEVDZmaNdHYi6HEV1GZmw+nsRNDroiEzs+EUlggknS7pfkk3VvU7R9Ky/HenpGVFLR+qrghcNGRm1lCRR8hFwFeAMys9IuL1lc+SvgA8VODyN9wjcFsEZmaNFdlU5RWS5tYbJknAP5MasC+tCZ9RAAAHFklEQVTM2p4Bpm8ziUkTO7oEzMxsq7TrCPkc4L6IuK3RCJIWSFoiacmqVau2aCFPftx0jnjarlsao5lZV1BEFDfzdEWwOCKeWtP/68BfIuILrcxn/vz5sWTJktEP0Mysg0laGhHzhxtvzAvPJU0CXgMcMNbLNjOzzbWjaOiFwC0RsaINyzYzsxpFPj56NnAVsLekFZLelge9ATi7qOWamdnIFPnU0FEN+r+5qGWamdnI+blKM7Mu50RgZtblnAjMzLqcE4GZWZcr9IWy0SJpFXDXFk6+M/DAKIZTFt243t24ztCd692N6wwjX+89ImLmcCOVIhFsDUlLWnmzrtN043p34zpDd653N64zFLfeLhoyM+tyTgRmZl2uGxLBwnYH0CbduN7duM7QnevdjesMBa13x98jMDOz5rrhisDMzJpwIjAz63IdnQgkvUTSrZL+IukD7Y6nCJJmS7pU0nJJN0k6PvffSdJFkm7L/3dsd6yjTdJESX+StDh3P0HSNXmdz5E0pd0xjjZJO0j6saRb8jY/uNO3taT35H37RklnS9q2E7e1pNMl3S/pxqp+dbetki/nY9v1kp6xNcvu2EQgaSLwVeClwL7AUZL2bW9UhRgAToyIfYCDgHfl9fwAcHFE7AVcnLs7zfHA8qruzwBfzOu8Gnhb3anK7UvAryLiH4Cnk9a/Y7e1pFnAccD83NLhRFJV9p24rRcBL6np12jbvhTYK/8tAL6+NQvu2EQAHEhqDvP2iOgDfgC8qs0xjbqIWBkR1+bP60gHhlmkdT0jj3YGcGR7IiyGpN2BlwHfzt0CDgN+nEfpxHXeHngucBpARPRFxBo6fFuTqsufmls3nAaspAO3dURcATxY07vRtn0VcGYkVwM7SNptS5fdyYlgFnB3VfeK3K9j5Tai9weuAR4XESshJQtgl/ZFVohTgfcBQ7n7scCaiBjI3Z24vfcEVgHfyUVi35a0HR28rSPiHuDzwP+REsBDwFI6f1tXNNq2o3p86+REoDr9OvZZWUnTgXOBEyJibbvjKZKklwP3R8TS6t51Ru207T0JeAbw9YjYH3iEDioGqieXib8KeALweGA7UrFIrU7b1sMZ1f29kxPBCmB2VffuwL1tiqVQkiaTksBZEXFe7n1f5VIx/7+/XfEV4BDglZLuJBX5HUa6QtghFx9AZ27vFcCKiLgmd/+YlBg6eVu/ELgjIlZFRD9wHvAsOn9bVzTatqN6fOvkRPBHYK/8dMEU0g2m89sc06jLZeOnAcsj4pSqQecDx+bPxwI/G+vYihIRH4yI3SNiLmm7XhIRRwOXAq/No3XUOgNExN+AuyXtnXu9ALiZDt7WpCKhgyRNy/t6ZZ07eltXabRtzweOyU8PHQQ8VClC2iIR0bF/wBHAn4G/Aie3O56C1vHZpEvC64Fl+e8IUpn5xcBt+f9O7Y61oPU/FFicP+8J/AH4C/AjYJt2x1fA+s4DluTt/VNgx07f1sDHgFuAG4HvAtt04rYGzibdB+knnfG/rdG2JRUNfTUf224gPVW1xct2FRNmZl2uk4uGzMysBU4EZmZdzonAzKzLORGYmXU5JwIzsy7nRGAdTdKnJB0q6ciR1kAraWau4fJPkp5TM+zbRVRiKOmk0Z6n2XD8+Kh1NEmXkCqn+x/gxxHxuxFM+wbgpRFx7LAjjxJJD0fE9LFanhn4isA6lKTPSboe+EfgKuBfga9L+nCdcfeQdHGu1/1iSXMkzQM+CxwhaZmkqTXTXCZpfv78sKRPSrpO0tWSHpf7L5L0DUm/lfTnXEcSkt4s6StV81qcr1o+Taplc5mksyRtJ+nneb43Snp9QV+XdTknAutIEfFe0sF/ESkZXB8R+0XEx+uM/hVSlb77AWcBX46IZcCHgXMiYl5E9DRZ3HbA1RHxdOAK4N+qhs0Fnke6KvmGpG2bxPwBoCcv72hS3fT3RsTTI9XF/6tW1t1spJwIrJPtT6py4x9I9dM0cjDw/fz5u6RqO0aiD1icPy8lHfwrfhgRQxFxG3B7jqVVNwAvlPQZSc+JiIdGGJdZSyYNP4pZueRinUWkGhkfIDVmIknLgIOHObuHkVfn2x8bb7YNsunvqnZeQWpVrvokrO5VQkT8WdIBpLqjPiXpwgZXNGZbxVcE1nEiYllEzCNVOLgvcAlweJMint+TajEFOBq4chTDeZ2kCZKeSKoo7VbgTmBe7j+b1JpeRX+uVhxJjwfWR8T3SI2zbFW7tGaN+IrAOpKkmcDqiBiS9A8R0axo6DjgdEnvJbUA9pZRDOVW4HLgccA7IqJX0u+AO0hFPzcC11aNvxC4XtK1wJnA5yQNkWqk/PdRjMtsAz8+alYQSYtIVWT/eLhxzdrJRUNmZl3OVwRmZl3OVwRmZl3OicDMrMs5EZiZdTknAjOzLudEYGbW5f4/Y58NrloIxxAAAAAASUVORK5CYII=\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "plt.plot(cumulative_branch_coverage)\n", "plt.title('Branch coverage of cgi_decode() with random inputs')\n", "plt.xlabel('# of inputs')\n", "plt.ylabel('line pairs covered')" ] }, { "cell_type": "code", "execution_count": 76, "metadata": { "slideshow": { "slide_type": "subslide" }, "solution2": "hidden" }, "outputs": [ { "data": { "text/plain": [ "24" ] }, "execution_count": 76, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(cov_max.coverage())" ] }, { "cell_type": "code", "execution_count": 77, "metadata": { "slideshow": { "slide_type": "fragment" }, "solution2": "hidden" }, "outputs": [ { "data": { "text/plain": [ "{(('cgi_decode', 22), ('__exit__', 25)),\n", " (('cgi_decode', 32), ('__exit__', 25))}" ] }, "execution_count": 77, "metadata": {}, "output_type": "execute_result" } ], "source": [ "all_branch_coverage - cov_max.coverage()" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" }, "solution2": "hidden" }, "source": [ "The additional coverage comes from the exception raised via an illegal input (say, `%g`)." ] }, { "cell_type": "code", "execution_count": 78, "metadata": { "slideshow": { "slide_type": "fragment" }, "solution2": "hidden" }, "outputs": [ { "data": { "text/plain": [ "{(('cgi_decode', 32), ('cgi_decode', 9))}" ] }, "execution_count": 78, "metadata": {}, "output_type": "execute_result" } ], "source": [ "cov_max.coverage() - all_branch_coverage" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" }, "solution2": "hidden" }, "source": [ "This is an artefact coming from the subsequent execution of `cgi_decode()` when computing `cov_max`." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" }, "solution2": "hidden", "solution2_first": true }, "source": [ "#### Part 3: Average coverage\n", "\n", "Again, repeat the above experiments with branch coverage. Does `fuzzer()` cover all branches, and if so, how many tests does it take on average?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" }, "solution2": "hidden" }, "source": [ "**Solution.** We repeat the experiments we ran with line coverage with branch coverage." ] }, { "cell_type": "code", "execution_count": 79, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" }, "solution2": "hidden" }, "outputs": [], "source": [ "runs = 100\n", "\n", "# Create an array with TRIALS elements, all zero\n", "sum_coverage = [0] * trials\n", "\n", "for run in range(runs):\n", " all_branch_coverage, coverage = population_branch_coverage(\n", " hundred_inputs(), cgi_decode)\n", " assert len(coverage) == trials\n", " for i in range(trials):\n", " sum_coverage[i] += coverage[i]\n", "\n", "average_coverage = []\n", "for i in range(trials):\n", " average_coverage.append(sum_coverage[i] / runs)\n" ] }, { "cell_type": "code", "execution_count": 80, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" }, "solution2": "hidden" }, "outputs": [ { "data": { "text/plain": [ "Text(0,0.5,'line pairs covered')" ] }, "execution_count": 80, "metadata": {}, "output_type": "execute_result" }, { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZEAAAEWCAYAAACnlKo3AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4zLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvIxREBQAAIABJREFUeJzt3Xl4XWW5/vHvnTQd05YOaQulpdCWoUWGUlFAFAcEPArCcWJQxKGOP4aDehA9itNxRuDghIIMIg6AgKgoMgoy2EIZW2ihBQqdxyRtmiZ5fn+slbIJ2clOuld2snN/ritX9pqftdbe61nv+65BEYGZmVl3VJQ6ADMz67ucRMzMrNucRMzMrNucRMzMrNucRMzMrNucRMzMrNucRLpB0p2SPtYL4jhP0q9LHUdfJOl4SS9IqpN0YBHn+4SkI7o4zRGSlhUrhgKX2aXvjqRPSLog/Txe0gJJg4oQx18lndrB8MslfXNHl1MsPfXbl3SupF9mvZxi6JEkkm749cX40pkVyQ+Az0ZEdUQ8XKyZRsTMiLizWPPrDSQNBL4MfB8gIlYCdwBzdnTeEXFMRFyRLufDku7Z0XmWg4j434joiWS1wycwmScRSVOAw4EAjs1oGQOymG8x9ObYepISvankuxvwRKmD6COOAxZGxIs5/a4GPlGieAri317P6Ikf9YeA+4HLge3FVkmvl7RCUmVOv+MlPZp+rpB0jqRnJK2V9HtJo9NhUySFpI9Keh64Pe3/h3SeGyXdLWlmzrzHSPqTpE2S/i3pm7lnPZL2lnSrpHWSnpL0vk7Wa6qkB9Nl3biDsV0u6ceS/iypVtIDkqbmDJ+ZE9tKSefmxDFQ0pXpdE9Imp0v4HzzkTRI0gWSXkr/LmgtNabVFu/MmccASWskzcrZj/+StEHSI7lVOWkJ9FuS7gU2A3tIOi2dZ62kZyV9ok2MX5C0PI3jY+m2nJYT5w8kPZ/G/zNJQ/Ksa4WkL0t6TtKqdBuNTOdRB1QCj0h6povbaoikK5SUrBek8S7LmW6ppLfl2wc587g8nceTwGvbDN9F0nWSVktaIun0nGGVSqo6nkm34TxJk9Jhh6bf7Y3p/0Nzpttd0l3pNLcCY9ssM+9+BI4B7mqzGg+Q7M/d2lm/3dP5VKTdv5S0Kmf4ryWdmX6+M93P+wA/Aw5RUsW4IWeWo/L9NtosN4vf3pGSFqbTXgwoZ1i737E2sZympNp0vaRPSnqtpEfT7XNxe+uRTr+9ujFnXqem3/01kr7UZtxrJf0uXYeHJO2fM3z7byhnnb8paRjwV2CXdJvXpd+9gyXNVXKsXCnp/HxxAhARmf4Bi4FPAwcB24DxOcOeAY7M6f4DcE76+UyS5LMrMAj4OXBNOmwKScnmSmAYMCTt/xFgeDr+BcD8nHn/Nv0bCswAXgDuSYcNS7tPAwYAs4A1wMw863Qn8CKwbzrtdcCvdyC2y4F1wMHp8q8GfpsOGw4sB84GBqfdr0uHnQc0AO8gOSh+G7g/T8wdzefr6bYeB9QA/wK+kQ77CnB1znz+g+SsFGAisDZdfgVwZNpdk7OdngdmputVlU4/leTH+CaS5DIrHf9oYEU6/lDgqnRbTkuHXwDcBIxO4/8T8O086/sRku/eHkA1cD1wVc7w7fPt4rb6DskBdRTJd/NRYFnOtEuBt3Xym/gO8M90PSYBj7fOI92O89LtPjCN/1ngqHT454HHgL3Sbbg/MCad13rgg+m2PjHtHpNOdx9wPsn3741ALS9/Zzvbj/8G3tvOejwKHJtnHZ8HDko/P5Wuwz45ww7M+Y58LP38YdLfZCG/jXaWOYXi/vbGApuA95B8d88CmnLizfsdy4nlZyTfobeT/FZvIPmdTQRWAW/Ksy7n8epjyi+AIek+35qzPc8jOba2xvk5YAlQ1d53PV3nb6afjyDn+5vzXflg+rkaeH2H3+diJIoOfixvSFdubNq9EDgrZ/g3gctyfrj1wG5p9wLgrTnj7pzOa0DORt2jg2XvlI4zkuQAuw3Yq82yW5PI+4F/tpn+58BX88z7TuA7Od0zgMZ0OV2KLWen/jJn+Dt4+UB9IvBwB1+0f7SJY0uecTuazzPAO3K6jwKWpp+nkRxwhqbdVwNfST//NzkH5rTf34BTc7bT1zv5jtwAnJF+voycpJAuO9L/Sr8fU3OGHwIsyTPf24BP53Tv1fr9ae+H1YVttf2AnnZ/jK4nkWeBo3O65/ByEnkd8Hyb8b8I/Cr9/BRwXDvz/CDwYJt+95EcmCeTHPyG5Qz7DS8fpDrbj4ty480Z517gQ3nW8Srgv4AJaczfAz4J7A5sACpyviOdJZF2fxvtLHMKxf3tfYick7L0O7gsJ96837GcWCbmDF8LvD+n+zrgzDxxnserk8iuOcMfBD6QM25unBUkJ0GHt/ddp/MkcjfwNdLjdmd/WVdnnQr8PSLWpN2/IadKK+0+QUnVyQnAQxHxXDpsN+CPabFvA0lSaQbG50z/QuuHtJj/nbSYv4nkxwzJ2UQNyY59ob1p02W9rnVZ6fJOJvkB5JM7/XMkZwBj2xveSWytVuR83kxyBgDJmWq7VS55phus9uuCO5rPLuk6tHou7UdELCbZ9u+SNJSkXes36Xi7Ae9ts93eQJLwW+VuJyQdI+l+JdVEG0h+tK3bYRfy76MaktLJvJxl3ZL2L3SdBvDK708+nW2rfDEWqu08cuPcjaR6IXebnsvLceeLre36ts53YjpsfUTUd7DMjvbjepKTvLaGkySE9txFcoB6I8lB6U6SkuebSE7YWvJM1558v418ivXbe8V+iuQIm7vfCvmOrcz5vKWd7s7WJVdH2yE3zhaSZLdLF+ad66PAnsBCJdWi7+xo5MwanpTUVb8PqJTUuvKDgJ0k7R8Rj0TEk5KeI6lzPYmXD06QbJSPRMS97cx7SvoxcnqfRNIA+DaSL8pIki+/gNUkZ2K7Ak+n409qs6y7IuLILqxi7vSTSc5A1uT0LzS2zrxAcma8ozqaz0u8sqF5ctqv1TXptBXAk2liaZ3nVRHx8Q6Wu307pCcL15Gc4d0YEdsk3cDL22E5yT5qlbuN15D86GbGKxt482ldp1atZ+Mr2x/9FTraVq0xPtlOjIVank6Xu71zl70kIqZ3ENtUkiqwXG3Xt3W+t6TLGyVpWE4imczL+6az/fgoyUFlu/REZRrwSJ5p7iK5mmtZ+vkekqqdBl7dvtIq8vTvqmL99lr3E5BcHMIr93dH37Hc73FPyI2zIl1+6294M8kJWKsJJPsF2tnmEbEIODGdzwnAtZLGtDkJ2S7Lksi7SUoOM4AD0r99SOqCP5Qz3m+A00nOWP6Q0/9nwLeUNtxJqpF0XAfLG05ST7iWZIP9b+uAiGgmqa88T9JQSXu3ieFmYE9JH5RUlf69VkljXz6nSJqRnp1/Hbg2XU6XYivAzcAESWcqaRQeLul1XZi+kPlcA3w53cZjSerjc+8h+C1Jne6neGWi/zVJCeWo9IxvsJJLBvP9gAaSnEisBpokHZPOt9XvgdMk7ZNu16+0DkjPrn4B/EjSOABJEyUdlWdZ1wBnKWnkrSbZ5r+LiKYOt1Kio231e+CLkkZJmgh8toD5tZU7j12B/5cz7EFgk6T/VtIAXylpX0mtje+/BL4haboS+0kaA/yF5Dt8kpKLH95P8tu7OS3dzwW+JmmgpDcA78pZZmf78S8kJYhcB5NUebYt/QDbD0RbgFOAuyNiE8nB9T/Jn0RWArsquaS4WHbkt/dnYKakE9KkeTqvrJ3Yke9YsR2UE+eZJOt8fzpsPnBSum+P5pX7ciUwRukFAQCSTpFUk/7mWkua+Y5tmSaRU0nqcZ+PiBWtf8DFwMk5VS7XkBR7b8+p9gK4kKQR9e+Sakk2SEcHzytJipMvkpwl3t9m+GdJzkJWkNTXXkOyoYmIWpKD2QdIsvcK4LskB7x8riKpW1xB0nB2egfjdhZbXmlsR5L86FeQ1E+/udDpC5zPN0kOMo+SNNo+lPZrnXY5Sf36ocDvcvq/QHKWdy5JYniBpOG33e9VGsPpJAfR9SRniTflDP8rcBHJPQiL02VCup9I6u4XA/enVRP/IKmHbs9lJPvobpJGxgZeebDOq5Nt9XWSs7gl6fKvzYmvUF8j+T4sAf6extm67OZ0uQekw9eQJI7WH/n5JNvv7ySNvpeSNCCvBd5JcjHAWuALwDtzflMnkfx+1gFfJflOti6zs/34J2BvSbnVIyeTnOh15C5gbUQ8n9MtIN99ObeTlM5WSFqTZ5yu2pHf3hrgvSQXQqwFppO0A7Xq9ncsAzeStO22XlxxQkRsS4edQfKdaq2mv6F1oohYSHIsfDatytyF5AKXJ5RcxXghSdtLQ74FK21I6XckfReYEBGndjqylURaEnwcGFSis7tOSfoUyY+s7Zl6WZE0B5gREWemJcG7SK6wyntwsZ4h6TyShvNTSrH8fnMzTlqFNZDkTPu1JI1HJX90ib2SpONJqhGGkZQG/9SbEoiknUku6byP5Mz0bJLSdVmLiEtyPq8iqZo261fPzhpO0i5ST1Id8EOSIqD1Lp8gqVJ5hqQe9lOlDedVBpJc/l1LUv1yI/CTtiMpeSZUXTt/57Yd16wv67fVWWZmtuP6U0nEzMyKrE+0iYwdOzamTJlS6jDMzPqUefPmrYmIfDfkFkWfSCJTpkxh7ty5pQ7DzKxPSW/mzpSrs8zMrNucRMzMrNsySyKSJkm6Q8k7F56QdEba/zxJL0qan/69I6sYzMwsW1m2iTQBZ0fEQ5KGkzx99dZ02I8i4gcZLtvMzHpAZkkkfd7S8vRzraQFJI+lNjOzMtEjbSJKHt1+IMkrNQE+q+QVkZdJGpVnmjlKXtE4d/Xq1T0RppmZdVHmSSR9RHLrG7w2AT8leR/CASQllR+2N11EXBIRsyNidk1Nppc5m5lZN2V6n4ikKpIEcnVEXA8QEStzhv+C5N0NZmZ9UsO2Zp5ZXcfGzdu299uyrZm19Y2sq29k89Yde37o8bN2Zfexw3Y0zMxk+WZDkbzrYEFEnJ/Tf+e0vQTgeF79hjYzsx6xrbmF9ZuTg/2a2kaWrKlj0ao6lqypZ+u2jt/gGwQrN23lhfWb6ewRhCrkPYp5zNptVP9MIsBhJC9HeUzS/LTfuSSvXTyA5LWMS0me2mpmVnQtLcGy9VtYvLqWRSvrWLyqjqVr61lT18jauq1sanh1KaF60ACm1gxj6MDODo/iNbuO5IRZE5k+bjhjqgduf+fuoKpKxgwbyOhhAxk6sBLtSBbp5bK8Ouse2n+P8V+yWqaZ9W4N25p5dNlG5j63jvouVvNsbmxmXWsVUWPet7W+Yvwla+poyClRjK0exB41w5i5ywjGDBvIqGED04P9IEYPG8iUsUOZMGJwWR/0i61PPDvLzLIVEWxr7vy1ENuaW7YfyDc1bGu3Gqc5gg2bG1lXv4119VtZV9/I2rpGVtVu5cnlm2hsSg7qAyq6dqAeXFXJ6PTsftigStTuOerLRg6p4tCpY5g2rppp46qZPq6anYYW8/XtBk4iZv1ac0vw58eW85M7FrNwRW3R519ZIUYNHbi9aufUQ3bj4N3H8Nopo3xALxNOIma9wLbmFp5bW8+LGxroyoviImDDluSsf319I00tXZk2uPXJlTy7pp5p46o56217MqCy47P7ygoxemiSEEYOraK9woQkdhpSxZhhgxgxZICrhsqck4hZETU1t7yiWmhzY9P26p8XN2xh8aqkcXdl7dbt49Q1bOO5tZu7lADaUyEYUNm1W7/2HF/NT0+exVEzJ1DRxeolM3ASMWtXbcM25j23noef30DDtlc34kY6ztq6RtZvbtx+T8DGLe23E7QaUCGmjB3GziMHU5GeoU8YMYijZk5g2rhqJo0eSmUXDuYiqfsfPWwgIwZXORFYj3MSsX4lInh02Ub++vgKHliyluZ2zv63bmth0apaWiI5ux84oP2z++pBVekVPlXsM2HE9kbfIQMrt48zeEAFo6sHMWbYQMaPGMxuY4ZS1cXSgllv5iRifUZE8NTKWpat27K935ZtuZd9vnzJaGNTy/bSQW3OvQBr6rayfGMDAyrErMmj2GlIJW1VVoijZo7n4N3HMGu3nQq4X8Cs//Kvw3q9p1bU8seHX+SWx5ezdO3mvOMNqarcfmdwVWXF9pLB2OqB2xt3J48ZyhF71nDkjPG+OsisCJxErNdatamB7//tKa59aBmVEodMHcOcN05l34kjtt8jMKgqSRY7DanqcqOyme04JxHrVbY0NvPw8+u5e9EarrxvKduaW/jYG3bn00dMY9QwlxzMehsnESuJjZu3Mfe5dcx9bj0rNjYkD8Cr28rTK2vZ1hxUCI6cMZ4vHrMPU3rxw+fM+jsnEctMRPDES5v46+PLuWfRGramj7tobGphydp6IqCqUowbPpgx1QOpGT6IN+5Zw8G7j+ag3UYxYnBVidfAzDrjJGJF1dISPPzCBm55fDm3PLGCF9ZtobJCHDR5FONHDAaSq5/efeBEDt59NAdM2onBVa++QsrM+gYnESua2xas5Et/fJwVmxqoqhRvmDaW//fm6bxtxnhGuz3DrCw5iVhRXPPg83zpj4+x94QRnHPM3rxln3GujjLrB5xEbIdEBD/6xyIuum0RR+xVw49PmsWwQf5amfUXmV1YL2mSpDskLZD0hKQz2gz/nKSQNDarGCxbyzdu4WNXzOWi2xbx3oN25Rcfmu0EYtbPZPmLbwLOjoiHJA0H5km6NSKelDQJOBJ4PsPlW0a2NDZz/cPL+PZfFtLU0sL/vHMGHzlsih/5bdYPZfl63OXA8vRzraQFwETgSeBHwBeAG7NavhXXpfcs4bJ7lrC2fuv2140eOnUM3zlhPyaPGVri6MysVHqk7kHSFOBA4AFJxwIvRsQjHZ25SpoDzAGYPHlyD0Rp+Vx2zxK+cfOTvG730Ryz7wRGVw9kWk01R84Y79KHWT+XeRKRVA1cB5xJUsX1JeDtnU0XEZcAlwDMnj17x97WY932+3+/wNdvfpKjZo7nxyfN8vOpzOwVMj0iSKoiSSBXR8T1wFRgd+ARSUuBXYGHJE3IMg7ruuaW4Kr7lvLf1z/KG/es4aITD3QCMbNXyawkoqSe41JgQUScDxARjwHjcsZZCsyOiDVZxWFd969n1vDNmxfw5PJNHD59LD8/5SAGDfBd5Wb2allWZx0GfBB4TNL8tN+5EfGXDJdp3bRqUwN/e2IFNz+6nAeWrGPiTkO46MQDedd+O7vdw8zyyvLqrHuADo8+ETElq+Vbx+Y9t457F69l8ao6Fq2qY+GKTUTA1Jph/PfRe3PaYVP8TCsz65TvDOtnGpta+N4tC/nlPUsA2HXUEKaNq+aYfffkmH0nMH388BJHaGZ9iZNIPxERLF5Vx3/9/hEee3EjHzpkN75w9N5U+w5zM9sBPoKUqRc3bOHBJWt5cMl6nlqxicWr6tjU0MTIIVX8/IMHcdRMXxBnZjvOSaTM3LFwFd+4+UmeXVMPwPDBA5ix8wiOPWAXptVUc8xrdt7+Xg8zsx3lJFIm1tU38vU/PcEN819i+rhqznvXDA7efQx7TRhOZYWvrjKzbDiJ9GGLV9Xyr2fW8sCSdfzz6dVsbmzmjLdO59Nvnur7OsysRziJ9FE/uXMx37vlKQAmjBjMW/YexyePmMreE0aUODIz60+cRPqYiOCCfyziwtsWcez+u/D5o/Zi11FDfEOgmZWEk0gfEhF8729P8dM7n+E9B+3Kd/9zP7d3mFlJOYn0If93+2J+eucznPS6yXzzuH2pcAIxsxJzEukj/jD3Bc6/9WlOmDWRb717X1dfmVmv4Gd79wF3Pb2aL17/GIdPH8t3TtjPCcTMeg0nkV7uvmfW8ulfz2P6+OH85ORZDBzgXWZmvYers3qppuYWLrp9MRffvogpY4Zx+WmvZfjgqlKHZWb2Ck4ivdCLG7Zw5m8f5t9L1/Ofs3bla8fN9IMSzaxX8pGpl7nl8eV84dpHaW4JfvT+/Tn+wF1LHZKZWV5Zvh53EnAlMAFoAS6JiAslfQM4Lu23CvhwRLyUVRx9xebGJr715wVc/cDz7LfrSP7vxAPZbcywUodlZtahLEsiTcDZEfGQpOHAPEm3At+PiP8BkHQ68BXgkxnG0astXlXL1Q88z3XzlrGpoYlPvHEPzn77Xm5AN7M+IcvX4y4HlqefayUtACZGxJM5ow0DIqsYerPFq2r5378s5PaFq6iqFMfsuzOnHjqFg3YbVerQzMwK1iNtIpKmAAcCD6Td3wI+BGwE3pxnmjnAHIDJkyf3RJg9Yn19Ixfetoir7n+OoVWVfO7te/KBgycztnpQqUMzM+syRWRbEJBUDdwFfCsirm8z7IvA4Ij4akfzmD17dsydOzfDKLPX2NTClfct5aLbFlG3tYmTXjeZs962J2OcPMwsI5LmRcTsLJeRaUlEUhVwHXB12wSS+g3wZ6DDJNLX/WvxGr50w+MsWVPP4dPH8uX/mMFeE4aXOiwzsx2W5dVZAi4FFkTE+Tn9p0fEorTzWGBhVjH0Bo+8sIHTLv83E3cawq8+/FqO2KvGjy0xs7KRZUnkMOCDwGOS5qf9zgU+Kmkvkkt8n6OMr8xauamBOVfNZWz1IP7wyUNcdWVmZSfLq7PuAdo75f5LVsvsTRq2NTPnqnnUNjRx3acOdQIxs7LkO9YzEBGcc92jPPLCBn52ykHss7NfWWtm5cl3tGXgh39/mhvmv8Tn3r4nR+87odThmJllxkmkyH7zwPNcfMdiTjx4Ep9587RSh2NmlilXZxVJRPC3J1by5Rse48171fCN4/z2QTMrf3mTiKQTOpowz30f/c5TK2r548Mvcsvjy1m6djOvmTiSi0+axYBKF/LMrPx1VBJ5V/p/HHAocHva/WbgTqDfJ5F7Fq3hw796EIBDpo7h42/cg2P334VhfveHmfUTeY92EXEagKSbgRnpAxWRtDPw454Jr/d68qVNfPLX85haU83VH3+dn31lZv1SIXUuU1oTSGolsGdG8fQJL23YwmmXP0j1oAFc/pHXOoGYWb9VSL3LnZL+BlxD8tj2DwB3ZBpVLxUR/HPRGs770xNs3trMHz51CDuPHFLqsMzMSqbTJBIRn5V0PPDGtNclEfHHbMPqfe54ahUX3Po0jyzbyM4jB/OLU2ez9wTfRGhm/VuhLcAPAbUR8Q9JQyUNj4jaLAPrTR5/cSOn/erfTBo9hG+f8BpOmDWRQQMqSx2WmVnJdZpEJH2c5OVQo4GpwETgZ8Bbsw2t9/jD3BcYOKCCmz97OCOHVpU6HDOzXqOQhvXPkDyRdxNA+hj3cVkG1ZtsbWrmxkde4u0zxjuBmJm1UUgS2RoRja0dkgbQj96LfsfCVWzYvI33HLRrqUMxM+t1Ckkid0k6Fxgi6UjgD8Cfsg2r97h23jLGDR/E4dNrSh2KmVmvU0gSOQdYDTwGfILkfSBfzjKo3mJ17VbueGo1x8+aSGWFn4NlZtZWhw3rkiqBKyLiFOAXXZmxpEnAlcAEkrcYXhIRF0r6PskjVRqBZ4DTImJDd4LP2o3zX6S5JXjPLFdlmZm1p8OSSEQ0AzWSBnZj3k3A2RGxD/B64DOSZgC3AvtGxH7A08AXuzHvzEUE185bxv6TdmL6+OGlDsfMrFcq5D6RpcC9km4C6lt7RsT5HU2UPiplefq5VtICYGJE/D1ntPuB93Q16J7w0PMbWLiilm8cN7PUoZiZ9VqFJJGX0r8KoFun5JKmAAcCD7QZ9BHgd3mmmUNyfwqTJ0/uzmK7LSL43i0LGVs9kONdlWVmllchjz35GoCkYRFR39n4bUmqBq4DzoyITTn9v0RS5XV1nuVeAlwCMHv27B69pPjOp1fzwJJ1fO3YmVT7se5mZnl1enWWpEMkPQksSLv3l/STQmYuqYokgVyd+xIrSacC7wROjohedc9JS0vw3b8uZPLooZx4cM+WgMzM+ppCLvG9ADgKWAsQEY/w8sMY81LybthLgQW57SeSjgb+Gzg2IjZ3J+gs3fjIiyxcUcvZb9+TgQP8dkIzs44UVFcTES+0eV94cwGTHQZ8EHhM0vy037nARcAg4NZ0nvdHxCcLjjhDW5ua+eHfn2bmLiN41367lDocM7Ner5Ak8oKkQ4FIL/U9nbRqqyMRcQ/Q3h16f+laiD3nH0+uYtn6LXzjuH2p8M2FZmadKqS+5pMkD2GcCCwDDki7y849i1czfPAADp8+ttShmJn1CYWURBQRJ2ceSYm1vrXwkD3GMKDSbSFmZoUo5Gj5L0l/l/RRSTtlHlGJPLd2M8vWb3EpxMysCzpNIhExneSBizOBhyTdLOmUzCPrYf9cvAaAw6Y5iZiZFaqgepuIeDAi/gs4GFgHXJFpVCVw76I1TNxpCLuPHVbqUMzM+oxCbjYcIelUSX8F/kXyPKyDM4+sBzW3BP96Zg1vmDaWNpcym5lZBwppWH8EuAH4ekTcl3E8JfHosg1samjiDW4PMTPrkkKSyB4REZKGS6qOiLrMo+ph96btIYdOHVPiSMzM+pZC2kRmSnoYeBx4UtI8SftmHFeP+ueiNczcZQRjqgeVOhQzsz6lkCRyCfBfEbFbREwGzk77lYX6rU089Px6V2WZmXVDIUlkWETc0doREXcCZXMJ07+XrmNbc3D4tJpSh2Jm1ucU0ibyrKT/Aa5Ku08BlmQXUs964qXkFSf7TxpZ4kjMzPqeQkoiHwFqgOvTv7HAaVkG1ZOeWVXHhBGDGT64qtShmJn1OYW82XA9yZN7y9Li1XVMG1dd6jDMzPqkQm42vDX3mVmSRkn6W7Zh9YyI4JlVTiJmZt1VSHXW2IjY0NqRlkzGdTaRpEmS7pC0QNITks5I+7837W6RNLv7oe+45RsbqG9sZqqTiJlZtxSSRFokbX/ZuKTdgELei94EnB0R+wCvBz4jaQbJ/SYnAHd3I96iWrwquW9yWo2TiJlZdxRyddaXgHsk3ZV2vxGY09lEEbGc5DlbREStpAXAxIi4FegVz6jankRcEjEz65ZCGtZvkTSLpDQh4KyIWNOVhUiaAhwIPNCNGDOzeHUdI4dUMbZ6YKlDMTPrkwopiZAmjZu7swCLnZq5AAARR0lEQVRJ1cB1wJkRsakL080hLfFMnjy5k7G7Z3HaqN4bSkVmZn1Rpu+BlVRFkkCujojruzJtRFwSEbMjYnZNTTZ3kz+zqs7tIWZmOyCzJKLk9P5SYEFEnJ/VcrprfX0ja+sbmT7eScTMrLsKuU9kqqRB6ecjJJ1e4LvWDwM+CLxF0vz07x2Sjpe0DDgE+HOp7jlZvDppVPflvWZm3VdIm8h1wGxJ00hKFjcBvwHe0dFEEXEPSUN8e/7YlSCz4Mt7zcx2XEH3iUREE3A8cEFEnAXsnG1Y2Vu8qo4hVZVM3GlIqUMxM+uzCkki2ySdCJzKy1do9fmnFS5aVcceNcOoqPCVWWZm3VVIEjmNpP3iWxGxRNLuwK+zDSt7fmaWmdmO67BNRFIlcG5EnNLaLyKWAN/JOrAs1W9t4sUNW/hAzaRSh2Jm1qd1WBKJiGagRlJZ3dL97Op6wI87MTPbUYVcnbUUuFfSTUB9a8/eeO9HoRavrgWcRMzMdlQhSeSl9K8CGJ5tOD3jhXVbAJg0emiJIzEz69sKeQDj13oikJ60YlMDo4cNZHBVZalDMTPr0/ImEUkXRMSZkv5EO+8PiYhjM40sQys2NjB+xOBSh2Fm1ud1VBK5Kv3/g54IpCet2NjAziOdRMzMdlTeJBIR89L/d+Ubp69auamB/ScV8vgvMzPrSKdtIpKmA98GZgDbT98jYo8M48rM1qZm1tY3MsHVWWZmO6yQO9Z/BfyU5J3pbwau5OWqrj5n1aatAEwYOajEkZiZ9X2FJJEhEXEboIh4LiLOA96SbVjZWbGpAYAJI/3gRTOzHVXIfSINkiqARZI+C7wIjMs2rOys2JgmEVdnmZntsEJKImcCQ4HTgYNIXjR1apZBZWnlJicRM7NiKeRmw38DpKWR0yOitpAZS5pE0n4yAWgBLomICyWNBn4HTCF5pMr7ImJ9t6LvhuUbGxhcVcGIIYUUwszMrCOFvB53tqTHgEeBxyQ9IumgAubdBJwdEfsArwc+I2kGcA5wW0RMB25Lu3vMik0N7DxyCMkr4M3MbEcUUp11GfDpiJgSEVOAz5BcsdWhiFgeEQ+ln2uBBcBE4DjginS0K4B3dyPublu5sYHxI3xllplZMRSSRGoj4p+tHem70wuq0molaQpwIPAAMD4ilqfzWk6eRnpJcyTNlTR39erVXVlch1ZsanB7iJlZkRSSRB6U9HNJR0h6k6SfAHdKmiVpVmcTS6oGrgPOjIhNhQYWEZdExOyImF1TU1PoZB1qaQlWbmpgvB95YmZWFIW0Lh+Q/v9qm/6HkjyYMe89I5KqSBLI1RFxfdp7paSdI2K5pJ2BVV2MudvWbW5kW3Ows0siZmZFUcjVWW/uzoyVtFxfCixo8wKrm0guEf5O+v/G7sy/O7bfI+KSiJlZUWR5nethJPeUPCZpftrvXJLk8XtJHwWeB96bYQyv0HqPiB8Db2ZWHJklkbQBPt91tG/NarkdWe6SiJlZURXSsF42Vm5qoEJQU+1LfM3MiqGQmw2HSvofSb9Iu6dLemf2oRXfio0N1AwfxIDKfpU7zcwyU+ij4LcCh6Tdy4BvZhZRhnyPiJlZcRWSRKZGxPeAbQARsYX8bR292oqNDW4PMTMrokKSSKOkIST3hCBpKknJpM9xScTMrLgKuTrrq8AtwCRJV5NcuvvhLIPKwubGJmobmny3uplZERVys+Gtkh4ieRKvgDMiYk3mkRWZX0ZlZlZ8hd4nMhhYn44/QxIRcXd2YRXfy6/FdRIxMyuWTpOIpO8C7weeIHm5FCTtI30ribgkYmZWdIWURN4N7BURfbIxvZVLImZmxVfI1VnPAlVZB5K1jZu3MWhABUMH+rW4ZmbFUsgRdTMwX9Jt5FzaGxGnZxZVBuq2NlE9yAnEzKyYCjmq3pT+9Wn1W5sY5iRiZlZUhVzie0Vn4/QFdVubGTqwstRhmJmVlbxJRNLvI+J9kh4jvVs9V0Tsl2lkRVbv6iwzs6Lr6Kh6Rvq/Tz6xt636xiZGDR1Y6jDMzMpK3iQSEcvT/891Z8aSLiNJQKsiYt+03/7Az4BqYClwckRs6s78u6puaxOTRg3tiUWZmfUbeS/xlVQraVM7f7WSCjnwXw4c3abfL4FzIuI1wB+Bz3c78i7avLWZYYPcJmJmVkx5k0hEDI+IEe38DY+IEZ3NOH0syro2vffi5TvdbwX+s9uRd5GvzjIzK76efsXf48Cx6ef3ApPyjShpjqS5kuauXr16hxYaEdQ3umHdzKzYejqJfAT4jKR5wHCgMd+IEXFJRMyOiNk1NTU7tNAt25ppCVwSMTMrsh49qkbEQuDtAJL2BP6jJ5Zbt7UJcBIxMyu2Hi2JSBqX/q8AvkxypVbm6rc2A1DthnUzs6LKLIlIuga4D9hL0jJJHwVOlPQ0sBB4CfhVVsvPVd9aEvHDF83Miiqzo2pEnJhn0IVZLTOf1uosN6ybmRVXTzesl0RrSWSok4iZWVH1iyTycknEbSJmZsXUL5JIa8O6r84yMyuufpFENjf6El8zsyz0iyRS56uzzMwy0S+SSP3WJoZUVVJZoVKHYmZWVvpFEqnb2uyqLDOzDPSLJJK81dBXZpmZFVu/SSIuiZiZFV+/SCJ1TiJmZpnoF0nE7xIxM8tG/0giW5sZOtBtImZmxdYvkkjdVpdEzMyy0C+SyGa3iZiZZaLsk0hLS1Df6PtEzMyyUPZJZPM2v9XQzCwrWb7Z8DJJqyQ9ntPvAEn3S5ovaa6kg7Nafqt6v1/dzCwzWZZELgeObtPve8DXIuIA4Ctpd6b8VkMzs+xklkQi4m5gXdvewIj080iS96xnyu9XNzPLTk8fWc8E/ibpByQJ7NB8I0qaA8wBmDx5crcXWOfqLDOzzPR0w/qngLMiYhJwFnBpvhEj4pKImB0Rs2tqarq9wNa3Gro6y8ys+Ho6iZwKXJ9+/gPQgw3rvjrLzKzYejqJvAS8Kf38FmBR1gt0w7qZWXYyO7JKugY4AhgraRnwVeDjwIWSBgANpG0eWWotiQx1EjEzK7rMjqwRcWKeQQdltcz21DcmbSJDq1ydZWZWbGV/x3r91iaGDaykwu9XNzMruv6RRFyVZWaWibJPIn4MvJlZdso+ibgkYmaWnX6QRJp9j4iZWUbKPom4OsvMLDtln0TqG12dZWaWlfJPIm4TMTPLTNknEVdnmZllp6yTSHNL0LCthaED3bBuZpaFsk4i9Y1++KKZWZbKO4n4hVRmZplyEjEzs24r6yRSt/2thm4TMTPLQlknke0lkYEuiZiZZaGsk0idq7PMzDKVWRKRdJmkVZIez+n3O0nz07+lkuZntXx4uSTiq7PMzLKR5dH1cuBi4MrWHhHx/tbPkn4IbMxw+W5YNzPLWJavx71b0pT2hkkS8D7gLVktH3Ib1p1EzMyyUKo2kcOBlRGxKN8IkuZImitp7urVq7u1kM2NTVQIBleVddOPmVnJlOroeiJwTUcjRMQlETE7ImbX1NR0ayF16cMXk4KPmZkVW4/X80gaAJwAHJT1svYaP5xj9p2Q9WLMzPqtUjQWvA1YGBHLsl7QBw6ezAcOnpz1YszM+q0sL/G9BrgP2EvSMkkfTQd9gE6qsszMrG/I8uqsE/P0/3BWyzQzs57ly5bMzKzbnETMzKzbnETMzKzbnETMzKzbnETMzKzbnETMzKzbFBGljqFTklYDz3Vz8rHAmiKG01f0x/Xuj+sM/XO9++M6Q9fXe7eI6N5zowrUJ5LIjpA0NyJmlzqOntYf17s/rjP0z/Xuj+sMvXO9XZ1lZmbd5iRiZmbd1h+SyCWlDqBE+uN698d1hv653v1xnaEXrnfZt4mYmVl2+kNJxMzMMuIkYmZm3VbWSUTS0ZKekrRY0jmljicLkiZJukPSAklPSDoj7T9a0q2SFqX/R5U61mKTVCnpYUk3p927S3ogXeffSRpY6hiLTdJOkq6VtDDd54eU+76WdFb63X5c0jWSBpfjvpZ0maRVkh7P6dfuvlXiovTY9qikWaWKu2yTiKRK4MfAMcAM4ERJM0obVSaagLMjYh/g9cBn0vU8B7gtIqYDt6Xd5eYMYEFO93eBH6XrvB74aLtT9W0XArdExN7A/iTrX7b7WtJE4HRgdkTsC1SSvNiuHPf15cDRbfrl27fHANPTvznAT3soxlcp2yQCHAwsjohnI6IR+C1wXIljKrqIWB4RD6Wfa0kOKhNJ1vWKdLQrgHeXJsJsSNoV+A/gl2m3gLcA16ajlOM6jwDeCFwKEBGNEbGBMt/XJC/PGyJpADAUWE4Z7uuIuBtY16Z3vn17HHBlJO4HdpK0c89E+krlnEQmAi/kdC9L+5UtSVOAA4EHgPERsRySRAOMK11kmbgA+ALQknaPATZERFPaXY77ew9gNfCrtBrvl5KGUcb7OiJeBH4APE+SPDYC8yj/fd0q377tNce3ck4iaqdf2V7PLKkauA44MyI2lTqeLEl6J7AqIubl9m5n1HLb3wOAWcBPI+JAoJ4yqrpqT9oGcBywO7ALMIykKqetctvXnek13/dyTiLLgEk53bsCL5UolkxJqiJJIFdHxPVp75Wtxdv0/6pSxZeBw4BjJS0lqaZ8C0nJZKe0ygPKc38vA5ZFxANp97UkSaWc9/XbgCURsToitgHXA4dS/vu6Vb5922uOb+WcRP4NTE+v4hhI0hh3U4ljKrq0LeBSYEFEnJ8z6Cbg1PTzqcCNPR1bViLiixGxa0RMIdmvt0fEycAdwHvS0cpqnQEiYgXwgqS90l5vBZ6kjPc1STXW6yUNTb/rretc1vs6R759exPwofQqrdcDG1urvXpaWd+xLukdJGeolcBlEfGtEodUdJLeAPwTeIyX2wfOJWkX+T0wmeSH+N6IaNto1+dJOgL4XES8U9IeJCWT0cDDwCkRsbWU8RWbpANILiYYCDwLnEZyMli2+1rS14D3k1yJ+DDwMZL6/7La15KuAY4gedz7SuCrwA20s2/ThHoxydVcm4HTImJuSeIu5yRiZmbZKufqLDMzy5iTiJmZdZuTiJmZdZuTiJmZdZuTiJmZdZuTiJU1Sd+WdISkd3f1Sc6SatInxT4s6fA2w36ZxQM9JZ1b7HmaZcmX+FpZk3Q7yYMa/xe4NiLu7cK0HwCOiYhTOx25SCTVRUR1Ty3PbEe5JGJlSdL3JT0KvBa4j+QGtZ9K+ko74+4m6bb0vQy3SZqc3tT3PeAdkuZLGtJmmjslzU4/10n6lqRHJN0vaXza/3JJP5P0T0lPp8/8QtKHJV2cM6+b09LSd0ieVjtf0tWShkn6czrfxyW9P6PNZdZtTiJWliLi8ySJ43KSRPJoROwXEV9vZ/SLSR6rvR9wNXBRRMwHvgL8LiIOiIgtHSxuGHB/ROwP3A18PGfYFOBNJKWhn0ka3EHM5wBb0uWdTHI38ksRsX/6Lo1bCll3s57kJGLl7EBgPrA3yfOW8jkE+E36+SrgDV1cTiNwc/p5HkniaPX7iGiJiEUkjynZuwvzfQx4m6TvSjo8IjZ2MS6zzA3ofBSzviWtirqc5Mmma0heZCRJ84FDOilVQNcfqb0tXm5cbOaVv6u28wqSZ0DlnsC1WzqJiKclHQS8A/i2pL/nKUmZlYxLIlZ2ImJ+RBwAPE3yauTbgaM6qJb6F8nTgAFOBu4pYjjvlVQhaSrJS6WeApYCB6T9J5G8hbPVtvTR/kjaBdgcEb8meTFTyd6jbZaPSyJWliTVAOsjokXS3hHRUXXW6cBlkj5P8ubA04oYylPAXcB44JMR0SDpXmAJSXXV48BDOeNfAjwq6SHgSuD7klqAbcCnihiXWVH4El+zjEi6HLg5Iq7tbFyzvsrVWWZm1m0uiZiZWbe5JGJmZt3mJGJmZt3mJGJmZt3mJGJmZt3mJGJmZt32/wEUAkIY+nTodQAAAABJRU5ErkJggg==\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "plt.plot(average_coverage)\n", "plt.title('Average branch coverage of cgi_decode() with random inputs')\n", "plt.xlabel('# of inputs')\n", "plt.ylabel('line pairs covered')" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" }, "solution2": "hidden" }, "source": [ "We see that achieving branch coverage takes longer than statement coverage; it simply is a more difficult criterion to satisfy with random inputs." ] } ], "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.6.6" }, "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 } }, "nbformat": 4, "nbformat_minor": 2 }