{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "slide"
},
"tags": []
},
"source": [
"# Grammar Coverage\n",
"\n",
"[Producing inputs from grammars](GrammarFuzzer.ipynb) gives all possible expansions of a rule the same likelihood. For producing a comprehensive test suite, however, it makes more sense to maximize _variety_ – for instance, by not repeating the same expansions over and over again. In this chapter, we explore how to systematically _cover_ elements of a grammar such that we maximize variety and do not miss out individual elements."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"execution": {
"iopub.execute_input": "2024-06-30T20:08:33.474796Z",
"iopub.status.busy": "2024-06-30T20:08:33.474670Z",
"iopub.status.idle": "2024-06-30T20:08:33.562310Z",
"shell.execute_reply": "2024-06-30T20:08:33.561898Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/html": [
"\n",
" \n",
" "
],
"text/plain": [
""
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"from bookutils import YouTubeVideo\n",
"YouTubeVideo('GGb3e5p0HC8')"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"**Prerequisites**\n",
"\n",
"* You should have read the [chapter on grammars](Grammars.ipynb).\n",
"* You should have read the [chapter on efficient grammar fuzzing](GrammarFuzzer.ipynb)."
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"## Synopsis\n",
"\n",
"\n",
"To [use the code provided in this chapter](Importing.ipynb), write\n",
"\n",
"```python\n",
">>> from fuzzingbook.GrammarCoverageFuzzer import \n",
"```\n",
"\n",
"and then make use of the following features.\n",
"\n",
"\n",
"This chapter introduces `GrammarCoverageFuzzer`, an efficient grammar fuzzer extending `GrammarFuzzer` from the [chapter on efficient grammar fuzzing](GrammarFuzzer.ipynb). It strives to _cover all expansions at least once,_ thus ensuring coverage of functionality.\n",
"\n",
"In the following example, for instance, we use `GrammarCoverageFuzzer` to produce an expression. We see that the resulting expression covers all digits and all operators in a single expression.\n",
"\n",
"```python\n",
">>> from Grammars import EXPR_GRAMMAR\n",
">>> expr_fuzzer = GrammarCoverageFuzzer(EXPR_GRAMMAR)\n",
">>> expr_fuzzer.fuzz()\n",
"'-(2 + 3) * 4.5 / 6 - 2.0 / +8 + 7 + 3'\n",
"```\n",
"After fuzzing, the `expansion_coverage()` method returns a mapping of grammar expansions covered.\n",
"\n",
"```python\n",
">>> expr_fuzzer.expansion_coverage()\n",
"{' -> 0',\n",
" ' -> 1',\n",
" ' -> 2',\n",
" ' -> 3',\n",
" ' -> 4',\n",
" ' -> 5',\n",
" ' -> 6',\n",
" ' -> 7',\n",
" ' -> 8',\n",
" ' -> 9',\n",
" ' -> ',\n",
" ' -> + ',\n",
" ' -> - ',\n",
" ' -> ()',\n",
" ' -> +',\n",
" ' -> -',\n",
" ' -> ',\n",
" ' -> .',\n",
" ' -> ',\n",
" ' -> ',\n",
" ' -> ',\n",
" ' -> ',\n",
" ' -> * ',\n",
" ' -> / '}\n",
"```\n",
"Subsequent calls to `fuzz()` will go for further coverage (i.e., covering the other area code digits, for example); a call to `reset()` clears the recorded coverage, starting anew.\n",
"\n",
"Since such coverage in inputs also yields higher code coverage, `GrammarCoverageFuzzer` is a recommended extension to `GrammarFuzzer`.\n",
"\n",
"![](PICS/GrammarCoverageFuzzer-synopsis-1.svg)\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Covering Grammar Elements\n",
"\n",
"The aim of test generation is to cover all functionality of a program – hopefully including the failing functionality, of course. This functionality, however, is tied to the _structure of the input_: If we fail to produce certain input elements, then the associated code and functionality will not be triggered either, nixing our chances to find a bug in there."
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"As an example, consider our expression grammar `EXPR_GRAMMAR` from the [chapter on grammars.](Grammars.ipynb):\n",
"\n",
"* If we do not produce negative numbers, then negative numbers will not be tested.\n",
"* If we do not produce floating-point numbers, then floating-point numbers will not be tested.\n",
"\n",
"Our aim must thus be to _cover all possible expansions_ – and not only by chance, but _by design_."
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"One way to maximize such variety is to _track_ the expansions that occur during grammar production: If we already have seen some expansion, we can prefer other possible expansion candidates out of the set of possible expansions. Consider the following rule in our expression grammar:"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"button": false,
"execution": {
"iopub.execute_input": "2024-06-30T20:08:33.583459Z",
"iopub.status.busy": "2024-06-30T20:08:33.583184Z",
"iopub.status.idle": "2024-06-30T20:08:33.586003Z",
"shell.execute_reply": "2024-06-30T20:08:33.585669Z"
},
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"import bookutils.setup"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"execution": {
"iopub.execute_input": "2024-06-30T20:08:33.587702Z",
"iopub.status.busy": "2024-06-30T20:08:33.587578Z",
"iopub.status.idle": "2024-06-30T20:08:33.589423Z",
"shell.execute_reply": "2024-06-30T20:08:33.589123Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"from bookutils import quiz"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"execution": {
"iopub.execute_input": "2024-06-30T20:08:33.591064Z",
"iopub.status.busy": "2024-06-30T20:08:33.590928Z",
"iopub.status.idle": "2024-06-30T20:08:33.660253Z",
"shell.execute_reply": "2024-06-30T20:08:33.659944Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"from Fuzzer import Fuzzer"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"execution": {
"iopub.execute_input": "2024-06-30T20:08:33.662159Z",
"iopub.status.busy": "2024-06-30T20:08:33.662036Z",
"iopub.status.idle": "2024-06-30T20:08:33.664026Z",
"shell.execute_reply": "2024-06-30T20:08:33.663614Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"from typing import Dict, List, Set, Union, Optional"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"execution": {
"iopub.execute_input": "2024-06-30T20:08:33.666400Z",
"iopub.status.busy": "2024-06-30T20:08:33.666239Z",
"iopub.status.idle": "2024-06-30T20:08:34.131559Z",
"shell.execute_reply": "2024-06-30T20:08:34.131041Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"from Grammars import EXPR_GRAMMAR, CGI_GRAMMAR, URL_GRAMMAR, START_SYMBOL\n",
"from Grammars import is_valid_grammar, extend_grammar, Grammar"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"button": false,
"execution": {
"iopub.execute_input": "2024-06-30T20:08:34.133692Z",
"iopub.status.busy": "2024-06-30T20:08:34.133497Z",
"iopub.status.idle": "2024-06-30T20:08:34.136344Z",
"shell.execute_reply": "2024-06-30T20:08:34.135964Z"
},
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"['+', '-', '()', '.', '']"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"EXPR_GRAMMAR[\"\"]"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Let us assume we have already produced an `` in the first expansion of ``. As it comes to expand the next factor, we would mark the `` expansion as already covered, and choose one of the yet uncovered alternatives such as `-` (a negative number) or `.` (a floating-point number). Only when we have covered all alternatives would we go back and reconsider expansions covered before."
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"execution": {
"iopub.execute_input": "2024-06-30T20:08:34.138469Z",
"iopub.status.busy": "2024-06-30T20:08:34.138231Z",
"iopub.status.idle": "2024-06-30T20:08:34.143607Z",
"shell.execute_reply": "2024-06-30T20:08:34.143215Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"data": {
"text/html": [
"\n",
" \n",
" \n",
" \n",
"
\n",
"
Quiz
\n",
"
\n",
"
Which expansions of EXPR_GRAMMAR does the expression 1 + 2 cover?