{ "cells": [ { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "# Introduction to Software Testing\n", "\n", "Before we get to the central parts of the book, let us introduce essential concepts of software testing. Why is it necessary to test software at all? How does one test software? How can one tell whether a test has been successful? How does one know if one has tested enough? In this chapter, let us recall the most important concepts, and at the same time get acquainted with Python and interactive notebooks." ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:53.540578Z", "iopub.status.busy": "2024-01-18T17:13:53.539929Z", "iopub.status.idle": "2024-01-18T17:13:53.611159Z", "shell.execute_reply": "2024-01-18T17:13:53.610847Z" }, "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('C8_pjdl7pK0')" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "This chapter (and this book) is not set to replace a textbook on testing; see the [Background](#Background) at the end for recommended reads." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Simple Testing\n", "\n", "Let us start with a simple example. Your co-worker has been asked to implement a square root function $\\sqrt{x}$. (Let's assume for a moment that the environment does not already have one.) After studying the [Newton–Raphson method](https://en.wikipedia.org/wiki/Newton%27s_method), she comes up with the following Python code, claiming that, in fact, this `my_sqrt()` function computes square roots." ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:53.633849Z", "iopub.status.busy": "2024-01-18T17:13:53.633661Z", "iopub.status.idle": "2024-01-18T17:13:53.635858Z", "shell.execute_reply": "2024-01-18T17:13:53.635615Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def my_sqrt(x):\n", " \"\"\"Computes the square root of x, using the Newton-Raphson method\"\"\"\n", " approx = None\n", " guess = x / 2\n", " while approx != guess:\n", " approx = guess\n", " guess = (approx + x / approx) / 2\n", " return approx" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "Your job is now to find out whether this function actually does what it claims to do." ] }, { "cell_type": "markdown", "metadata": { "button": false, "jp-MarkdownHeadingCollapsed": true, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "notes" }, "tags": [] }, "source": [ "### Understanding Python Programs\n", "\n", "If you're new to Python, you might first have to understand what the above code does. We very much recommend the [Python tutorial](https://docs.python.org/3/tutorial/) to get an idea on how Python works. The most important things for you to understand the above code are these three:\n", "\n", "1. Python structures programs through _indentation_, so the function and `while` bodies are defined by being indented;\n", "2. Python is _dynamically typed_, meaning that the type of variables like `x`, `approx`, or `guess` is determined at run-time.\n", "3. Most of Python's syntactic features are inspired by other common languages, such as control structures (`while`, `if`), assignments (`=`), or comparisons (`==`, `!=`, `<`).\n", "\n", "With that, you can already understand what the above code does: Starting with a `guess` of `x / 2`, it computes better and better approximations in `approx` until the value of `approx` no longer changes. This is the value that finally is returned." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Running a Function" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "To find out whether `my_sqrt()` works correctly, we can *test* it with a few values. For `x = 4`, for instance, it produces the correct value:" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:53.637606Z", "iopub.status.busy": "2024-01-18T17:13:53.637385Z", "iopub.status.idle": "2024-01-18T17:13:53.639725Z", "shell.execute_reply": "2024-01-18T17:13:53.639357Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "2.0" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "my_sqrt(4)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "The upper part above `my_sqrt(4)` (a so-called _cell_) is an input to the Python interpreter, which by default _evaluates_ it. The lower part (`2.0`) is its output. We can see that `my_sqrt(4)` produces the correct value." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "The same holds for `x = 2.0`, apparently, too:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:53.641740Z", "iopub.status.busy": "2024-01-18T17:13:53.641610Z", "iopub.status.idle": "2024-01-18T17:13:53.643849Z", "shell.execute_reply": "2024-01-18T17:13:53.643473Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "1.414213562373095" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "my_sqrt(2)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" }, "tags": [] }, "source": [ "### Interacting with Notebooks\n", "\n", "If you are reading this in the interactive notebook, you can try out `my_sqrt()` with other values as well. Click on one of the above cells with invocations of `my_sqrt()` and change the value – say, to `my_sqrt(1)`. Press `Shift+Enter` (or click on the play symbol) to execute it and see the result. If you get an error message, go to the above cell with the definition of `my_sqrt()` and execute this first. You can also run _all_ cells at once; see the Notebook menu for details. (You can actually also change the text by clicking on it, and corect mistaks such as in this sentence.)" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:53.645541Z", "iopub.status.busy": "2024-01-18T17:13:53.645411Z", "iopub.status.idle": "2024-01-18T17:13:53.647083Z", "shell.execute_reply": "2024-01-18T17:13:53.646819Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from bookutils import quiz" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:53.648524Z", "iopub.status.busy": "2024-01-18T17:13:53.648422Z", "iopub.status.idle": "2024-01-18T17:13:53.652792Z", "shell.execute_reply": "2024-01-18T17:13:53.652503Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/html": [ "\n", " \n", " \n", " \n", "
\n", "

Quiz

\n", "

\n", "

What does my_sqrt(16) produce?
\n", "

\n", "

\n", "

\n", " \n", " \n", "
\n", " \n", " \n", "
\n", " \n", " \n", "
\n", " \n", " \n", "
\n", " \n", "
\n", "

\n", " \n", " \n", "
\n", " " ], "text/plain": [ "" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "quiz(\"What does `my_sqrt(16)` produce?\", \n", " [\n", " \"4\",\n", " \"4.0\",\n", " \"3.99999\",\n", " \"None\"\n", " ], \"len('four') - len('two') + 1\")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Try it out for yourself by uncommenting and executing the following line:" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:53.654264Z", "iopub.status.busy": "2024-01-18T17:13:53.654178Z", "iopub.status.idle": "2024-01-18T17:13:53.655759Z", "shell.execute_reply": "2024-01-18T17:13:53.655487Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "# my_sqrt(16)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Executing a single cell does not execute other cells, so if your cell builds on a definition in another cell that you have not executed yet, you will get an error. You can select `Run all cells above` from the menu to ensure all definitions are set." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Also keep in mind that, unless overwritten, all definitions are kept across executions. Occasionally, it thus helps to _restart the kernel_ (i.e. start the Python interpreter from scratch) to get rid of older, superfluous definitions." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Debugging a Function" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "To see how `my_sqrt()` operates, a simple strategy is to insert `print()` statements in critical places. You can, for instance, log the value of `approx`, to see how each loop iteration gets closer to the actual value:" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:53.657703Z", "iopub.status.busy": "2024-01-18T17:13:53.657597Z", "iopub.status.idle": "2024-01-18T17:13:53.659798Z", "shell.execute_reply": "2024-01-18T17:13:53.659493Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def my_sqrt_with_log(x):\n", " \"\"\"Computes the square root of x, using the Newton–Raphson method\"\"\"\n", " approx = None\n", " guess = x / 2\n", " while approx != guess:\n", " print(\"approx =\", approx) # <-- New\n", " approx = guess\n", " guess = (approx + x / approx) / 2\n", " return approx" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:53.661306Z", "iopub.status.busy": "2024-01-18T17:13:53.661203Z", "iopub.status.idle": "2024-01-18T17:13:53.663464Z", "shell.execute_reply": "2024-01-18T17:13:53.663222Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "approx = None\n", "approx = 4.5\n", "approx = 3.25\n", "approx = 3.0096153846153846\n", "approx = 3.000015360039322\n", "approx = 3.0000000000393214\n" ] }, { "data": { "text/plain": [ "3.0" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "my_sqrt_with_log(9)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Interactive notebooks also allow launching an interactive *debugger* – insert a \"magic line\" `%%debug` at the top of a cell and see what happens. Unfortunately, interactive debuggers interfere with our dynamic analysis techniques, so we mostly use logging and assertions for debugging." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Checking a Function" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Let's get back to testing. We can read and run the code, but are the above values of `my_sqrt(2)` actually correct? We can easily verify by exploiting that $\\sqrt{x}$ squared again has to be $x$, or in other words $\\sqrt{x} \\times \\sqrt{x} = x$. Let's take a look:" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:53.665358Z", "iopub.status.busy": "2024-01-18T17:13:53.665245Z", "iopub.status.idle": "2024-01-18T17:13:53.667203Z", "shell.execute_reply": "2024-01-18T17:13:53.666952Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "1.9999999999999996" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "my_sqrt(2) * my_sqrt(2)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "Okay, we do have some rounding error, but otherwise, this seems just fine." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "What we have done now is that we have _tested_ the above program: We have _executed_ it on a given input and _checked_ its result whether it is correct or not. Such a test is the bare minimum of quality assurance before a program goes into production." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Automating Test Execution\n", "\n", "So far, we have tested the above program _manually_, that is, running it by hand and checking its results by hand. This is a very flexible way of testing, but in the long run, it is rather inefficient:\n", "\n", "1. Manually, you can only check a very limited number of executions and their results\n", "2. After any change to the program, you have to repeat the testing process\n", "\n", "This is why it is very useful to _automate_ tests. One simple way of doing so is to let the computer first do the computation, and then have it check the results." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "For instance, this piece of code automatically tests whether $\\sqrt{4} = 2$ holds:" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:53.668810Z", "iopub.status.busy": "2024-01-18T17:13:53.668706Z", "iopub.status.idle": "2024-01-18T17:13:53.670493Z", "shell.execute_reply": "2024-01-18T17:13:53.670259Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Test passed\n" ] } ], "source": [ "result = my_sqrt(4)\n", "expected_result = 2.0\n", "if result == expected_result:\n", " print(\"Test passed\")\n", "else:\n", " print(\"Test failed\")" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "The nice thing about this test is that we can run it again and again, thus ensuring that at least the square root of 4 is computed correctly. But there are still a number of issues, though:\n", "\n", "1. We need _five lines of code_ for a single test\n", "2. We do not care for rounding errors\n", "3. We only check a single input (and a single result)\n", "\n", "Let us address these issues one by one. First, let's make the test a bit more compact. Almost all programming languages do have a means to automatically check whether a condition holds, and stop execution if it does not. This is called an _assertion_, and it is immensely useful for testing." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "In Python, the `assert` statement takes a condition, and if the condition is true, nothing happens. (If everything works as it should, you should not be bothered.) If the condition evaluates to false, though, `assert` raises an exception, indicating that a test just failed.\n", "\n", "In our example, we can use `assert` to easily check whether `my_sqrt()` yields the expected result as above:" ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:53.672160Z", "iopub.status.busy": "2024-01-18T17:13:53.672045Z", "iopub.status.idle": "2024-01-18T17:13:53.673798Z", "shell.execute_reply": "2024-01-18T17:13:53.673476Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "assert my_sqrt(4) == 2" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "As you execute this line of code, nothing happens: We just have shown (or asserted) that our implementation indeed produces $\\sqrt{4} = 2$." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Remember, though, that floating-point computations may induce rounding errors. So we cannot simply compare two floating-point values with equality; rather, we would ensure that the absolute difference between them stays below a certain threshold value, typically denoted as $\\epsilon$ or ``epsilon``. This is how we can do it:" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:53.675722Z", "iopub.status.busy": "2024-01-18T17:13:53.675606Z", "iopub.status.idle": "2024-01-18T17:13:53.677155Z", "shell.execute_reply": "2024-01-18T17:13:53.676900Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "EPSILON = 1e-8" ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:53.678574Z", "iopub.status.busy": "2024-01-18T17:13:53.678485Z", "iopub.status.idle": "2024-01-18T17:13:53.680244Z", "shell.execute_reply": "2024-01-18T17:13:53.679990Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "assert abs(my_sqrt(4) - 2) < EPSILON" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "We can also introduce a special function for this purpose, and now do more tests for concrete values:" ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:53.681697Z", "iopub.status.busy": "2024-01-18T17:13:53.681621Z", "iopub.status.idle": "2024-01-18T17:13:53.683369Z", "shell.execute_reply": "2024-01-18T17:13:53.683128Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def assertEquals(x, y, epsilon=1e-8):\n", " assert abs(x - y) < epsilon" ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:53.684809Z", "iopub.status.busy": "2024-01-18T17:13:53.684724Z", "iopub.status.idle": "2024-01-18T17:13:53.686534Z", "shell.execute_reply": "2024-01-18T17:13:53.686256Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "assertEquals(my_sqrt(4), 2)\n", "assertEquals(my_sqrt(9), 3)\n", "assertEquals(my_sqrt(100), 10)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "Seems to work, right? If we know the expected results of a computation, we can use such assertions again and again to ensure our program works correctly." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "(Hint: a true Python programmer would use the function [`math.isclose()`](https://docs.python.org/3/library/math.html#math.isclose) instead.)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Generating Tests\n", "\n", "Remember that the property $\\sqrt{x} \\times \\sqrt{x} = x$ universally holds? We can also explicitly test this with a few values:" ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:53.688351Z", "iopub.status.busy": "2024-01-18T17:13:53.688237Z", "iopub.status.idle": "2024-01-18T17:13:53.690018Z", "shell.execute_reply": "2024-01-18T17:13:53.689758Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "assertEquals(my_sqrt(2) * my_sqrt(2), 2)\n", "assertEquals(my_sqrt(3) * my_sqrt(3), 3)\n", "assertEquals(my_sqrt(42.11) * my_sqrt(42.11), 42.11)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "Still seems to work, right? Most importantly, though, $\\sqrt{x} \\times \\sqrt{x} = x$ is something we can very easily test for thousands of values:" ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:53.691675Z", "iopub.status.busy": "2024-01-18T17:13:53.691550Z", "iopub.status.idle": "2024-01-18T17:13:53.694622Z", "shell.execute_reply": "2024-01-18T17:13:53.694379Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "for n in range(1, 1000):\n", " assertEquals(my_sqrt(n) * my_sqrt(n), n)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "How much time does it take to test `my_sqrt()` with 100 values? Let's see." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "We use our own [`Timer` module](Timer.ipynb) to measure elapsed time. To be able to use `Timer`, we first import our own utility module, which allows us to import other notebooks." ] }, { "cell_type": "code", "execution_count": 19, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:53.697233Z", "iopub.status.busy": "2024-01-18T17:13:53.697150Z", "iopub.status.idle": "2024-01-18T17:13:53.699702Z", "shell.execute_reply": "2024-01-18T17:13:53.699468Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import bookutils.setup" ] }, { "cell_type": "code", "execution_count": 20, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:53.701117Z", "iopub.status.busy": "2024-01-18T17:13:53.701017Z", "iopub.status.idle": "2024-01-18T17:13:53.723235Z", "shell.execute_reply": "2024-01-18T17:13:53.722917Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "from Timer import Timer" ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:53.725432Z", "iopub.status.busy": "2024-01-18T17:13:53.725317Z", "iopub.status.idle": "2024-01-18T17:13:53.742692Z", "shell.execute_reply": "2024-01-18T17:13:53.742427Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0.015223124995827675\n" ] } ], "source": [ "with Timer() as t:\n", " for n in range(1, 10000):\n", " assertEquals(my_sqrt(n) * my_sqrt(n), n)\n", "print(t.elapsed_time())" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "10,000 values take about a hundredth of a second, so a single execution of `my_sqrt()` takes 1/1000000 second, or about 1 microseconds." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Let's repeat this with 10,000 values picked at random. The Python `random.random()` function returns a random value between 0.0 and 1.0:" ] }, { "cell_type": "code", "execution_count": 22, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:53.744766Z", "iopub.status.busy": "2024-01-18T17:13:53.744650Z", "iopub.status.idle": "2024-01-18T17:13:53.746295Z", "shell.execute_reply": "2024-01-18T17:13:53.746027Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "import random" ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:53.748015Z", "iopub.status.busy": "2024-01-18T17:13:53.747909Z", "iopub.status.idle": "2024-01-18T17:13:53.767809Z", "shell.execute_reply": "2024-01-18T17:13:53.767492Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0.017563624991453253\n" ] } ], "source": [ "with Timer() as t:\n", " for i in range(10000):\n", " x = 1 + random.random() * 1000000\n", " assertEquals(my_sqrt(x) * my_sqrt(x), x)\n", "print(t.elapsed_time())" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "Within a second, we have now tested 10,000 random values, and each time, the square root was actually computed correctly. We can repeat this test with every single change to `my_sqrt()`, each time reinforcing our confidence that `my_sqrt()` works as it should. Note, though, that while a random function is _unbiased_ in producing random values, it is unlikely to generate special values that drastically alter program behavior. We will discuss this later below." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Run-Time Verification\n", "\n", "Instead of writing and running tests for `my_sqrt()`, we can also go and _integrate the check right into the implementation._ This way, _each and every_ invocation of `my_sqrt()` will be automatically checked." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Such an _automatic run-time check_ is very easy to implement:" ] }, { "cell_type": "code", "execution_count": 24, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:53.769508Z", "iopub.status.busy": "2024-01-18T17:13:53.769393Z", "iopub.status.idle": "2024-01-18T17:13:53.771156Z", "shell.execute_reply": "2024-01-18T17:13:53.770839Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def my_sqrt_checked(x):\n", " root = my_sqrt(x)\n", " assertEquals(root * root, x)\n", " return root" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "Now, whenever we compute a root with `my_sqrt_checked()`$\\dots$" ] }, { "cell_type": "code", "execution_count": 25, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:53.772747Z", "iopub.status.busy": "2024-01-18T17:13:53.772622Z", "iopub.status.idle": "2024-01-18T17:13:53.774848Z", "shell.execute_reply": "2024-01-18T17:13:53.774556Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "1.414213562373095" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "my_sqrt_checked(2.0)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "... we already know that the result is correct, and will so for every new successful computation." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "Automatic run-time checks, as above, assume two things, though:\n", "\n", "* One has to be able to _formulate_ such run-time checks. Having concrete values to check against should always be possible, but formulating desired properties in an abstract fashion can be very complex. In practice, you need to decide which properties are most crucial, and design appropriate checks for them. Plus, run-time checks may depend not only on local properties, but on several properties of the program state, which all have to be identified.\n", "\n", "* One has to be able to _afford_ such run-time checks. In the case of `my_sqrt()`, the check is not very expensive; but if we have to check, say, a large data structure even after a simple operation, the cost of the check may soon be prohibitive. In practice, run-time checks will typically be disabled during production, trading reliability for efficiency. On the other hand, a comprehensive suite of run-time checks is a great way to find errors and quickly debug them; you need to decide how many such capabilities you would still want during production." ] }, { "cell_type": "code", "execution_count": 26, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:53.776693Z", "iopub.status.busy": "2024-01-18T17:13:53.776578Z", "iopub.status.idle": "2024-01-18T17:13:53.780165Z", "shell.execute_reply": "2024-01-18T17:13:53.779905Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/html": [ "\n", " \n", " \n", " \n", "
\n", "

Quiz

\n", "

\n", "

Does run-time checking give a guarantee that there will always be a correct result?
\n", "

\n", "

\n", "

\n", " \n", " \n", "
\n", " \n", " \n", "
\n", " \n", "
\n", "

\n", " \n", " \n", "
\n", " " ], "text/plain": [ "" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "quiz(\"Does run-time checking give a guarantee \"\n", " \"that there will always be a correct result?\",\n", " [\n", " \"Yes\",\n", " \"No\",\n", " ], \"1 ** 1 + 1 ** 1\")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "An important limitation of run-time checks is that they ensure correctness _only if there is a result_ to be checked - that is, they do _not_ guarantee that there always will be one. This is an important limitation compared to _symbolic verification techniques_ and program proofs, which can also guarantee that there is a result – at a much higher (often manual) effort, though." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## System Input vs Function Input" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "At this point, we may make `my_sqrt()` available to other programmers, who may then embed it in their code. At some point, it will have to process input that comes from _third parties_, i.e. is not under control by the programmer." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "Let us simulate this *system input* by assuming a _program_ `sqrt_program()` whose input is a string under third-party control:" ] }, { "cell_type": "code", "execution_count": 27, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:53.782644Z", "iopub.status.busy": "2024-01-18T17:13:53.782560Z", "iopub.status.idle": "2024-01-18T17:13:53.784366Z", "shell.execute_reply": "2024-01-18T17:13:53.784112Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def sqrt_program(arg: str) -> None: # type: ignore\n", " x = int(arg)\n", " print('The root of', x, 'is', my_sqrt(x))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "We assume that `sqrt_program` is a program which accepts system input from the command line, as in\n", "\n", "```shell\n", "$ sqrt_program 4\n", "2\n", "```" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "We can easily invoke `sqrt_program()` with some system input:" ] }, { "cell_type": "code", "execution_count": 28, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:53.785785Z", "iopub.status.busy": "2024-01-18T17:13:53.785708Z", "iopub.status.idle": "2024-01-18T17:13:53.787318Z", "shell.execute_reply": "2024-01-18T17:13:53.787018Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The root of 4 is 2.0\n" ] } ], "source": [ "sqrt_program(\"4\")" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "What's the problem? Well, the problem is that we do not check external inputs for validity. Try invoking `sqrt_program(-1)`, for instance. What happens?" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Indeed, if you invoke `my_sqrt()` with a negative number, it enters an infinite loop. For technical reasons, we cannot have infinite loops in this chapter (unless we'd want the code to run forever); so we use a special `with ExpectTimeOut(1)` construct to interrupt execution after one second." ] }, { "cell_type": "code", "execution_count": 29, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:53.789034Z", "iopub.status.busy": "2024-01-18T17:13:53.788940Z", "iopub.status.idle": "2024-01-18T17:13:53.810806Z", "shell.execute_reply": "2024-01-18T17:13:53.810515Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "from ExpectError import ExpectTimeout" ] }, { "cell_type": "code", "execution_count": 30, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:53.812624Z", "iopub.status.busy": "2024-01-18T17:13:53.812524Z", "iopub.status.idle": "2024-01-18T17:13:54.819008Z", "shell.execute_reply": "2024-01-18T17:13:54.818704Z" }, "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 \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_71717/1288144681.py\", line 2, in \n", " sqrt_program(\"-1\")\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_71717/449782637.py\", line 3, in sqrt_program\n", " print('The root of', x, 'is', my_sqrt(x))\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_71717/2661069967.py\", line 5, in my_sqrt\n", " while approx != guess:\n", " File \"/Users/zeller/Projects/fuzzingbook/notebooks/Timeout.ipynb\", line 43, in timeout_handler\n", " raise TimeoutError()\n", "TimeoutError (expected)\n" ] } ], "source": [ "with ExpectTimeout(1):\n", " sqrt_program(\"-1\")" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "The above message is an _error message_, indicating that something went wrong. It lists the *call stack* of functions and lines that were active at the time of the error. The line at the very bottom is the line last executed; the lines above represent function invocations – in our case, up to `my_sqrt(x)`.\n", "\n", "We don't want our code terminating with an exception. Consequently, when accepting external input, we must ensure that it is properly validated. We may write, for instance:" ] }, { "cell_type": "code", "execution_count": 31, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:54.820740Z", "iopub.status.busy": "2024-01-18T17:13:54.820621Z", "iopub.status.idle": "2024-01-18T17:13:54.822538Z", "shell.execute_reply": "2024-01-18T17:13:54.822312Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def sqrt_program(arg: str) -> None: # type: ignore\n", " x = int(arg)\n", " if x < 0:\n", " print(\"Illegal Input\")\n", " else:\n", " print('The root of', x, 'is', my_sqrt(x))" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "and then we can be sure that `my_sqrt()` is only invoked according to its specification." ] }, { "cell_type": "code", "execution_count": 32, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:54.824131Z", "iopub.status.busy": "2024-01-18T17:13:54.824014Z", "iopub.status.idle": "2024-01-18T17:13:54.825773Z", "shell.execute_reply": "2024-01-18T17:13:54.825495Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Illegal Input\n" ] } ], "source": [ "sqrt_program(\"-1\")" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "But wait! What happens if `sqrt_program()` is not invoked with a number?" ] }, { "cell_type": "code", "execution_count": 33, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:54.827971Z", "iopub.status.busy": "2024-01-18T17:13:54.827847Z", "iopub.status.idle": "2024-01-18T17:13:54.831376Z", "shell.execute_reply": "2024-01-18T17:13:54.831063Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/html": [ "\n", " \n", " \n", " \n", "
\n", "

Quiz

\n", "

\n", "

What is the result of sqrt_program('xyzzy')?
\n", "

\n", "

\n", "

\n", " \n", " \n", "
\n", " \n", " \n", "
\n", " \n", " \n", "
\n", " \n", " \n", "
\n", " \n", "
\n", "

\n", " \n", " \n", "
\n", " " ], "text/plain": [ "" ] }, "execution_count": 33, "metadata": {}, "output_type": "execute_result" } ], "source": [ "quiz(\"What is the result of `sqrt_program('xyzzy')`?\",\n", " [\n", " \"0\",\n", " \"0.0\",\n", " \"`None`\",\n", " \"An exception\"\n", " ], \"16 ** 0.5\")" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Let's try this out! When we try to convert a non-number string, this would also result in a runtime error:" ] }, { "cell_type": "code", "execution_count": 34, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:54.833038Z", "iopub.status.busy": "2024-01-18T17:13:54.832952Z", "iopub.status.idle": "2024-01-18T17:13:54.834599Z", "shell.execute_reply": "2024-01-18T17:13:54.834316Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "from ExpectError import ExpectError" ] }, { "cell_type": "code", "execution_count": 35, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:54.836154Z", "iopub.status.busy": "2024-01-18T17:13:54.836067Z", "iopub.status.idle": "2024-01-18T17:13:54.837821Z", "shell.execute_reply": "2024-01-18T17:13:54.837539Z" }, "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 \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_71717/1336991207.py\", line 2, in \n", " sqrt_program(\"xyzzy\")\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_71717/3211514011.py\", line 2, in sqrt_program\n", " x = int(arg)\n", "ValueError: invalid literal for int() with base 10: 'xyzzy' (expected)\n" ] } ], "source": [ "with ExpectError():\n", " sqrt_program(\"xyzzy\")" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Here's a version which also checks for bad inputs:" ] }, { "cell_type": "code", "execution_count": 36, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:54.839409Z", "iopub.status.busy": "2024-01-18T17:13:54.839329Z", "iopub.status.idle": "2024-01-18T17:13:54.841255Z", "shell.execute_reply": "2024-01-18T17:13:54.840938Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def sqrt_program(arg: str) -> None: # type: ignore\n", " try:\n", " x = float(arg)\n", " except ValueError:\n", " print(\"Illegal Input\")\n", " else:\n", " if x < 0:\n", " print(\"Illegal Number\")\n", " else:\n", " print('The root of', x, 'is', my_sqrt(x))" ] }, { "cell_type": "code", "execution_count": 37, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:54.842933Z", "iopub.status.busy": "2024-01-18T17:13:54.842839Z", "iopub.status.idle": "2024-01-18T17:13:54.845065Z", "shell.execute_reply": "2024-01-18T17:13:54.844608Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The root of 4.0 is 2.0\n" ] } ], "source": [ "sqrt_program(\"4\")" ] }, { "cell_type": "code", "execution_count": 38, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:54.846771Z", "iopub.status.busy": "2024-01-18T17:13:54.846672Z", "iopub.status.idle": "2024-01-18T17:13:54.848302Z", "shell.execute_reply": "2024-01-18T17:13:54.848040Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Illegal Number\n" ] } ], "source": [ "sqrt_program(\"-1\")" ] }, { "cell_type": "code", "execution_count": 39, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:54.849812Z", "iopub.status.busy": "2024-01-18T17:13:54.849726Z", "iopub.status.idle": "2024-01-18T17:13:54.851403Z", "shell.execute_reply": "2024-01-18T17:13:54.851150Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Illegal Input\n" ] } ], "source": [ "sqrt_program(\"xyzzy\")" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "We have now seen that at the system level, the program must be able to handle any kind of input gracefully without ever entering an uncontrolled state. This, of course, is a burden for programmers, who must struggle to make their programs robust for all circumstances. This burden, however, becomes a _benefit_ when generating software tests: If a program can handle any kind of input (possibly with well-defined error messages), we can also _send it any kind of input_. When calling a function with generated values, though, we have to _know_ its precise preconditions." ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## The Limits of Testing\n", "\n", "Despite our best efforts in testing, keep in mind that you are always checking functionality for a _finite_ set of inputs. Thus, there may always be _untested_ inputs for which the function may still fail." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "In the case of `my_sqrt()`, for instance, computing $\\sqrt{0}$ results in a division by zero:" ] }, { "cell_type": "code", "execution_count": 40, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:54.852879Z", "iopub.status.busy": "2024-01-18T17:13:54.852800Z", "iopub.status.idle": "2024-01-18T17:13:54.854579Z", "shell.execute_reply": "2024-01-18T17:13:54.854295Z" }, "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 \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_71717/820411145.py\", line 2, in \n", " root = my_sqrt(0)\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_71717/2661069967.py\", line 7, in my_sqrt\n", " guess = (approx + x / approx) / 2\n", "ZeroDivisionError: float division by zero (expected)\n" ] } ], "source": [ "with ExpectError():\n", " root = my_sqrt(0)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "In our tests so far, we have not checked this condition, meaning that a program which builds on $\\sqrt{0} = 0$ will surprisingly fail. But even if we had set up our random generator to produce inputs in the range of 0–1000000 rather than 1–1000000, the chances of it producing a zero value by chance would still have been one in a million. If the behavior of a function is radically different for few individual values, plain random testing has few chances to produce these." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "We can, of course, fix the function accordingly, documenting the accepted values for `x` and handling the special case `x = 0`:" ] }, { "cell_type": "code", "execution_count": 41, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:54.856534Z", "iopub.status.busy": "2024-01-18T17:13:54.856402Z", "iopub.status.idle": "2024-01-18T17:13:54.858374Z", "shell.execute_reply": "2024-01-18T17:13:54.858048Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def my_sqrt_fixed(x):\n", " assert 0 <= x\n", " if x == 0:\n", " return 0\n", " return my_sqrt(x)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "source": [ "With this, we can now correctly compute $\\sqrt{0} = 0$:" ] }, { "cell_type": "code", "execution_count": 42, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:54.860139Z", "iopub.status.busy": "2024-01-18T17:13:54.860032Z", "iopub.status.idle": "2024-01-18T17:13:54.861832Z", "shell.execute_reply": "2024-01-18T17:13:54.861513Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "assert my_sqrt_fixed(0) == 0" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Illegal values now result in an exception:\n" ] }, { "cell_type": "code", "execution_count": 43, "metadata": { "button": false, "execution": { "iopub.execute_input": "2024-01-18T17:13:54.863756Z", "iopub.status.busy": "2024-01-18T17:13:54.863669Z", "iopub.status.idle": "2024-01-18T17:13:54.865515Z", "shell.execute_reply": "2024-01-18T17:13:54.865248Z" }, "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 \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_71717/305965227.py\", line 2, in \n", " root = my_sqrt_fixed(-1)\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_71717/3001478627.py\", line 2, in my_sqrt_fixed\n", " assert 0 <= x\n", "AssertionError (expected)\n" ] } ], "source": [ "with ExpectError():\n", " root = my_sqrt_fixed(-1)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "Still, we have to remember that while extensive testing may give us a high confidence into the correctness of a program, it does not provide a guarantee that all future executions will be correct. Even run-time verification, which checks every result, can only guarantee that _if_ it produces a result, the result will be correct; but there is no guarantee that future executions may not lead to a failing check. As I am writing this, I _believe_ that `my_sqrt_fixed(x)` is a correct implementation of $\\sqrt{x}$ for all finite numbers $x$, but I cannot be certain." ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "With the Newton-Raphson method, we may still have a good chance of actually _proving_ that the implementation is correct: The implementation is simple, the math is well-understood. Alas, this is only the case for few domains. If we do not want to go into full-fledged correctness proofs, our best chance with testing is to \n", "\n", "1. Test the program on several, well-chosen inputs; and\n", "2. Check results extensively and automatically.\n", "\n", "This is what we do in the remainder of this course: Devise techniques that help us to thoroughly test a program, as well as techniques that help us check its state for correctness. Enjoy!" ] }, { "cell_type": "markdown", "metadata": { "run_control": {}, "slideshow": { "slide_type": "slide" } }, "source": [ "## Lessons Learned\n", "\n", "* The aim of testing is to execute a program such that we find bugs.\n", "* Test execution, test generation, and checking test results can be automated.\n", "* Testing is _incomplete_; it provides no 100% guarantee that the code is free of errors." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "source": [ "## Next Steps\n", "\n", "From here, you can move on how to\n", "\n", "* [use _fuzzing_ to test programs with random inputs](Fuzzer.ipynb)\n", "\n", "Enjoy the read!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Background" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "There is a large number of works on software testing and analysis.\n", "\n", "* An all-new modern, comprehensive, and online textbook on testing is [\"Effective Software Testing: A Developer's Guide\"](https://www.effective-software-testing.com) \\cite{Aniche2022}. Much recommended!\n", "\n", "* For this book, we are also happy to recommend \"Software Testing and Analysis\" \\cite{Pezze2008} as an introduction to the field; its strong technical focus very well fits our methodology.\n", "\n", "* Other important must-reads with a comprehensive approach to software testing, including psychology and organization, include \"The Art of Software Testing\" \\cite{Myers2004} as well as \"Software Testing Techniques\" \\cite{Beizer1990}." ] }, { "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": true, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "### Exercise 1: Get Acquainted with Notebooks and Python\n", "\n", "Your first exercise in this book is to get acquainted with notebooks and Python, such that you can run the code examples in the book – and try out your own. Here are a few tasks to get you started." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": true, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "#### Beginner Level: Run Notebooks in Your Browser\n", "\n", "The easiest way to get access to the code is to run them in your browser.\n", "\n", "1. From the [Web Page](__CHAPTER_HTML__), check out the menu at the top. Select `Resources` $\\rightarrow$ `Edit as Notebook`.\n", "2. After a short waiting time, this will open a Jupyter Notebook right within your browser, containing the current chapter as a notebook.\n", "3. You can again scroll through the material, but you click on any code example to edit and run its code (by entering Shift + Return). You can edit the examples as you please.\n", "4. Note that code examples typically depend on earlier code, so be sure to run the preceding code first.\n", "5. Any changes you make will not be saved (unless you save your notebook to disk).\n", "\n", "For help on Jupyter Notebooks, from the [Web Page](__CHAPTER_HTML__), check out the `Help` menu." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": true, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "#### Advanced Level: Run Python Code on Your Machine\n", "\n", "This is useful if you want to make greater changes, but do not want to work with Jupyter.\n", "\n", "1. From the [Web Page](__CHAPTER_HTML__), check out the menu at the top. Select `Resources` $\\rightarrow$ `Download Code`. \n", "2. This will download the Python code of the chapter as a single Python .py file, which you can save to your computer.\n", "3. You can then open the file, edit it, and run it in your favorite Python environment to re-run the examples.\n", "4. Most importantly, you can [import it](Importing.ipynb) into your own code and reuse functions, classes, and other resources.\n", "\n", "For help on Python, from the [Web Page](__CHAPTER_HTML__), check out the `Help` menu." ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "button": false, "new_sheet": true, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "#### Pro Level: Run Notebooks on Your Machine\n", "\n", "This is useful if you want to work with Jupyter on your machine. This will allow you to also run more complex examples, such as those with graphical output.\n", "\n", "\n", "1. From the [Web Page](__CHAPTER_HTML__), check out the menu at the top. Select `Resources` $\\rightarrow$ `All Notebooks`. \n", "2. This will download all Jupyter Notebooks as a collection of `.ipynb` files, which you can save to your computer.\n", "3. You can then open the notebooks in Jupyter Notebook or Jupyter Lab, edit them, and run them. To navigate across notebooks, open the notebook [`00_Table_of_Contents.ipynb`](00_Table_of_Contents.ipynb).\n", "4. You can also download individual notebooks using Select `Resources` $\\rightarrow$ `Download Notebook`. Running these, however, will require that you have the other notebooks downloaded already.\n", "\n", "For help on Jupyter Notebooks, from the [Web Page](__CHAPTER_HTML__), check out the `Help` menu." ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "button": false, "new_sheet": true, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "#### Boss Level: Contribute!\n", "\n", "This is useful if you want to contribute to the book with patches or other material. It also gives you access to the very latest version of the book.\n", "\n", "1. From the [Web Page](__CHAPTER_HTML__), check out the menu at the top. Select `Resources` $\\rightarrow$ `GitHub Repo`. \n", "2. This will get you to the GitHub repository which contains all sources of the book, including the latest notebooks.\n", "3. You can then _clone_ this repository to your disk, such that you get the latest and greatest.\n", "4. You can report issues and suggest pull requests on the GitHub page.\n", "5. Updating the repository with `git pull` will get you updated.\n", "\n", "If you want to contribute code or text, check out the [Guide for Authors](Guide_for_Authors.ipynb)." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "### Exercise 2: Testing Shellsort\n", "\n", "Consider the following implementation of a [Shellsort](https://en.wikipedia.org/wiki/Shellsort) function, taking a list of elements and (presumably) sorting it." ] }, { "cell_type": "code", "execution_count": 44, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:54.867763Z", "iopub.status.busy": "2024-01-18T17:13:54.867656Z", "iopub.status.idle": "2024-01-18T17:13:54.870147Z", "shell.execute_reply": "2024-01-18T17:13:54.869885Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def shellsort(elems):\n", " sorted_elems = elems.copy()\n", " gaps = [701, 301, 132, 57, 23, 10, 4, 1]\n", " for gap in gaps:\n", " for i in range(gap, len(sorted_elems)):\n", " temp = sorted_elems[i]\n", " j = i\n", " while j >= gap and sorted_elems[j - gap] > temp:\n", " sorted_elems[j] = sorted_elems[j - gap]\n", " j -= gap\n", " sorted_elems[j] = temp\n", "\n", " return sorted_elems" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "A first test indicates that `shellsort()` might actually work:" ] }, { "cell_type": "code", "execution_count": 45, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:54.872064Z", "iopub.status.busy": "2024-01-18T17:13:54.871830Z", "iopub.status.idle": "2024-01-18T17:13:54.874317Z", "shell.execute_reply": "2024-01-18T17:13:54.874001Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "[1, 2, 3]" ] }, "execution_count": 45, "metadata": {}, "output_type": "execute_result" } ], "source": [ "shellsort([3, 2, 1])" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "The implementation uses a _list_ as argument `elems` (which it copies into `sorted_elems`) as well as for the fixed list `gaps`. Lists work like _arrays_ in other languages:" ] }, { "cell_type": "code", "execution_count": 46, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:54.876217Z", "iopub.status.busy": "2024-01-18T17:13:54.876072Z", "iopub.status.idle": "2024-01-18T17:13:54.878141Z", "shell.execute_reply": "2024-01-18T17:13:54.877876Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "First element: 5 length: 4\n" ] } ], "source": [ "a = [5, 6, 99, 7]\n", "print(\"First element:\", a[0], \"length:\", len(a))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "The `range()` function returns an iterable list of elements. It is often used in conjunction with `for` loops, as in the above implementation." ] }, { "cell_type": "code", "execution_count": 47, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:54.879860Z", "iopub.status.busy": "2024-01-18T17:13:54.879740Z", "iopub.status.idle": "2024-01-18T17:13:54.881868Z", "shell.execute_reply": "2024-01-18T17:13:54.881564Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1\n", "2\n", "3\n", "4\n" ] } ], "source": [ "for x in range(1, 5):\n", " print(x)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "#### Part 1: Manual Test Cases" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Your job is now to thoroughly test `shellsort()` with a variety of inputs." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" }, "solution2": "hidden", "solution2_first": true }, "source": [ "First, set up `assert` statements with a number of manually written test cases. Select your test cases such that extreme cases are covered. Use `==` to compare two lists." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "source": [ "**Solution.** Here are a few selected test cases:" ] }, { "cell_type": "code", "execution_count": 48, "metadata": { "cell_style": "split", "execution": { "iopub.execute_input": "2024-01-18T17:13:54.883762Z", "iopub.status.busy": "2024-01-18T17:13:54.883541Z", "iopub.status.idle": "2024-01-18T17:13:54.885599Z", "shell.execute_reply": "2024-01-18T17:13:54.885354Z" }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [], "source": [ "# Standard lists\n", "assert shellsort([3, 2, 1]) == [1, 2, 3]\n", "assert shellsort([1, 2, 3, 4]) == [1, 2, 3, 4]\n", "assert shellsort([6, 5]) == [5, 6]" ] }, { "cell_type": "code", "execution_count": 49, "metadata": { "cell_style": "split", "execution": { "iopub.execute_input": "2024-01-18T17:13:54.887003Z", "iopub.status.busy": "2024-01-18T17:13:54.886899Z", "iopub.status.idle": "2024-01-18T17:13:54.888549Z", "shell.execute_reply": "2024-01-18T17:13:54.888264Z" }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [], "source": [ "# Check for duplicates\n", "assert shellsort([2, 2, 1]) == [1, 2, 2]" ] }, { "cell_type": "code", "execution_count": 50, "metadata": { "cell_style": "split", "execution": { "iopub.execute_input": "2024-01-18T17:13:54.890121Z", "iopub.status.busy": "2024-01-18T17:13:54.889999Z", "iopub.status.idle": "2024-01-18T17:13:54.891716Z", "shell.execute_reply": "2024-01-18T17:13:54.891370Z" }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [], "source": [ "# Empty list\n", "assert shellsort([]) == []" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "#### Part 2: Random Inputs" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Second, create random lists as arguments to `shellsort()`. Make use of the following helper predicates to check whether the result is (a) sorted, and (b) a permutation of the original." ] }, { "cell_type": "code", "execution_count": 51, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:54.893694Z", "iopub.status.busy": "2024-01-18T17:13:54.893387Z", "iopub.status.idle": "2024-01-18T17:13:54.895506Z", "shell.execute_reply": "2024-01-18T17:13:54.895226Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def is_sorted(elems):\n", " return all(elems[i] <= elems[i + 1] for i in range(len(elems) - 1))" ] }, { "cell_type": "code", "execution_count": 52, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:54.897006Z", "iopub.status.busy": "2024-01-18T17:13:54.896897Z", "iopub.status.idle": "2024-01-18T17:13:54.898936Z", "shell.execute_reply": "2024-01-18T17:13:54.898701Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 52, "metadata": {}, "output_type": "execute_result" } ], "source": [ "is_sorted([3, 5, 9])" ] }, { "cell_type": "code", "execution_count": 53, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:54.900447Z", "iopub.status.busy": "2024-01-18T17:13:54.900342Z", "iopub.status.idle": "2024-01-18T17:13:54.902178Z", "shell.execute_reply": "2024-01-18T17:13:54.901908Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def is_permutation(a, b):\n", " return len(a) == len(b) and all(a.count(elem) == b.count(elem) for elem in a)" ] }, { "cell_type": "code", "execution_count": 54, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:54.903673Z", "iopub.status.busy": "2024-01-18T17:13:54.903566Z", "iopub.status.idle": "2024-01-18T17:13:54.905844Z", "shell.execute_reply": "2024-01-18T17:13:54.905558Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 54, "metadata": {}, "output_type": "execute_result" } ], "source": [ "is_permutation([3, 2, 1], [1, 3, 2])" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" }, "solution2": "hidden", "solution2_first": true }, "source": [ "Start with a random list generator, using `[]` as the empty list and `elems.append(x)` to append an element `x` to the list `elems`. Use the above helper functions to assess the results. Generate and test 1,000 lists." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "source": [ "**Solution.** Here's a simple random list generator:" ] }, { "cell_type": "code", "execution_count": 55, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:54.907731Z", "iopub.status.busy": "2024-01-18T17:13:54.907588Z", "iopub.status.idle": "2024-01-18T17:13:54.909713Z", "shell.execute_reply": "2024-01-18T17:13:54.909413Z" }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [], "source": [ "def random_list():\n", " length = random.randint(1, 10)\n", " elems = []\n", " for i in range(length):\n", " elems.append(random.randint(0, 100))\n", " return elems" ] }, { "cell_type": "code", "execution_count": 56, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:54.911501Z", "iopub.status.busy": "2024-01-18T17:13:54.911379Z", "iopub.status.idle": "2024-01-18T17:13:54.913382Z", "shell.execute_reply": "2024-01-18T17:13:54.913140Z" }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [ { "data": { "text/plain": [ "[61, 23, 61, 68]" ] }, "execution_count": 56, "metadata": {}, "output_type": "execute_result" } ], "source": [ "random_list()" ] }, { "cell_type": "code", "execution_count": 57, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:54.914850Z", "iopub.status.busy": "2024-01-18T17:13:54.914752Z", "iopub.status.idle": "2024-01-18T17:13:54.916404Z", "shell.execute_reply": "2024-01-18T17:13:54.916162Z" }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[51, 47, 88, 14, 38]\n" ] } ], "source": [ "elems = random_list()\n", "print(elems)" ] }, { "cell_type": "code", "execution_count": 58, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:54.918186Z", "iopub.status.busy": "2024-01-18T17:13:54.918056Z", "iopub.status.idle": "2024-01-18T17:13:54.919807Z", "shell.execute_reply": "2024-01-18T17:13:54.919572Z" }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[14, 38, 47, 51, 88]\n" ] } ], "source": [ "sorted_elems = shellsort(elems)\n", "print(sorted_elems)" ] }, { "cell_type": "code", "execution_count": 59, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:54.921285Z", "iopub.status.busy": "2024-01-18T17:13:54.921173Z", "iopub.status.idle": "2024-01-18T17:13:54.922993Z", "shell.execute_reply": "2024-01-18T17:13:54.922696Z" }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [], "source": [ "assert is_sorted(sorted_elems) and is_permutation(sorted_elems, elems)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "source": [ "Here's the test for 1,000 lists:" ] }, { "cell_type": "code", "execution_count": 60, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:54.924755Z", "iopub.status.busy": "2024-01-18T17:13:54.924577Z", "iopub.status.idle": "2024-01-18T17:13:54.933508Z", "shell.execute_reply": "2024-01-18T17:13:54.933216Z" }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [], "source": [ "for i in range(1000):\n", " elems = random_list()\n", " sorted_elems = shellsort(elems)\n", " assert is_sorted(sorted_elems) and is_permutation(sorted_elems, elems)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Exercise 3: Quadratic Solver" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Given an equation $ax^2 + bx + c = 0$, we want to find solutions for $x$ given the values of $a$, $b$, and $c$. The following code is supposed to do this, using the equation \n", "$$\n", "x = \\frac{-b \\pm \\sqrt{b^2 - 4ac}}{2a}\n", "$$" ] }, { "cell_type": "code", "execution_count": 61, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:54.935392Z", "iopub.status.busy": "2024-01-18T17:13:54.935261Z", "iopub.status.idle": "2024-01-18T17:13:54.937362Z", "shell.execute_reply": "2024-01-18T17:13:54.937095Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def quadratic_solver(a, b, c):\n", " q = b * b - 4 * a * c\n", " solution_1 = (-b + my_sqrt_fixed(q)) / (2 * a)\n", " solution_2 = (-b - my_sqrt_fixed(q)) / (2 * a)\n", " return (solution_1, solution_2)" ] }, { "cell_type": "code", "execution_count": 62, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:54.938991Z", "iopub.status.busy": "2024-01-18T17:13:54.938871Z", "iopub.status.idle": "2024-01-18T17:13:54.941214Z", "shell.execute_reply": "2024-01-18T17:13:54.940897Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "(-0.3333333333333333, -1.0)" ] }, "execution_count": 62, "metadata": {}, "output_type": "execute_result" } ], "source": [ "quadratic_solver(3, 4, 1)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "The above implementation is incomplete, though. You can trigger \n", "\n", "1. a division by zero; and\n", "2. violate the precondition of `my_sqrt_fixed()`.\n", "\n", "How does one do that, and how can one prevent this?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" }, "solution2": "hidden", "solution2_first": true }, "source": [ "#### Part 1: Find bug-triggering inputs\n", "\n", "For each of the two cases above, identify values for `a`, `b`, `c` that trigger the bug." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "source": [ "**Solution**. Here are two inputs that trigger the bugs:" ] }, { "cell_type": "code", "execution_count": 63, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:54.943204Z", "iopub.status.busy": "2024-01-18T17:13:54.943068Z", "iopub.status.idle": "2024-01-18T17:13:54.945162Z", "shell.execute_reply": "2024-01-18T17:13:54.944817Z" }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "Traceback (most recent call last):\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_71717/284450257.py\", line 2, in \n", " print(quadratic_solver(3, 2, 1))\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_71717/597421383.py\", line 3, in quadratic_solver\n", " solution_1 = (-b + my_sqrt_fixed(q)) / (2 * a)\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_71717/3001478627.py\", line 2, in my_sqrt_fixed\n", " assert 0 <= x\n", "AssertionError (expected)\n" ] } ], "source": [ "with ExpectError():\n", " print(quadratic_solver(3, 2, 1))" ] }, { "cell_type": "code", "execution_count": 64, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:54.946776Z", "iopub.status.busy": "2024-01-18T17:13:54.946672Z", "iopub.status.idle": "2024-01-18T17:13:54.948464Z", "shell.execute_reply": "2024-01-18T17:13:54.948221Z" }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "Traceback (most recent call last):\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_71717/273293533.py\", line 2, in \n", " print(quadratic_solver(0, 0, 1))\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_71717/597421383.py\", line 3, in quadratic_solver\n", " solution_1 = (-b + my_sqrt_fixed(q)) / (2 * a)\n", "ZeroDivisionError: division by zero (expected)\n" ] } ], "source": [ "with ExpectError():\n", " print(quadratic_solver(0, 0, 1))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" }, "solution2": "hidden", "solution2_first": true }, "source": [ "#### Part 2: Fix the problem\n", "\n", "Extend the code appropriately such that the cases are handled. Return `None` for nonexistent values." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "source": [ "**Solution.** Here is an appropriate extension of `quadratic_solver()` that takes care of all the corner cases:" ] }, { "cell_type": "code", "execution_count": 65, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:54.950057Z", "iopub.status.busy": "2024-01-18T17:13:54.949955Z", "iopub.status.idle": "2024-01-18T17:13:54.952657Z", "shell.execute_reply": "2024-01-18T17:13:54.952383Z" }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [], "source": [ "def quadratic_solver_fixed(a, b, c):\n", " if a == 0:\n", " if b == 0:\n", " if c == 0:\n", " # Actually, any value of x\n", " return (0, None)\n", " else:\n", " # No value of x can satisfy c = 0\n", " return (None, None)\n", " else:\n", " return (-c / b, None)\n", "\n", " q = b * b - 4 * a * c\n", " if q < 0:\n", " return (None, None)\n", "\n", " if q == 0:\n", " solution = -b / 2 * a\n", " return (solution, None)\n", "\n", " solution_1 = (-b + my_sqrt_fixed(q)) / (2 * a)\n", " solution_2 = (-b - my_sqrt_fixed(q)) / (2 * a)\n", " return (solution_1, solution_2)" ] }, { "cell_type": "code", "execution_count": 66, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:54.954135Z", "iopub.status.busy": "2024-01-18T17:13:54.954011Z", "iopub.status.idle": "2024-01-18T17:13:54.955779Z", "shell.execute_reply": "2024-01-18T17:13:54.955514Z" }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(None, None)\n" ] } ], "source": [ "with ExpectError():\n", " print(quadratic_solver_fixed(3, 2, 1))" ] }, { "cell_type": "code", "execution_count": 67, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:54.957807Z", "iopub.status.busy": "2024-01-18T17:13:54.957665Z", "iopub.status.idle": "2024-01-18T17:13:54.959707Z", "shell.execute_reply": "2024-01-18T17:13:54.959379Z" }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(None, None)\n" ] } ], "source": [ "with ExpectError():\n", " print(quadratic_solver_fixed(0, 0, 1))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" }, "solution2": "hidden", "solution2_first": true }, "source": [ "#### Part 3: Odds and Ends\n", "\n", "What are the chances of discovering these conditions with random inputs? Assuming one can do a billion tests per second, how long would one have to wait on average until a bug gets triggered?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "source": [ "**Solution.** Consider the code above. If we choose the full range of 32-bit integers for `a`, `b`, and `c`, then the first condition alone, both `a` and `b` being zero, has a chance of $p = 1 / (2^{32} * 2^{32})$; that is, one in 18.4 quintillions:" ] }, { "cell_type": "code", "execution_count": 68, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:54.961485Z", "iopub.status.busy": "2024-01-18T17:13:54.961374Z", "iopub.status.idle": "2024-01-18T17:13:54.963420Z", "shell.execute_reply": "2024-01-18T17:13:54.963160Z" }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [ { "data": { "text/plain": [ "18446744073709551616" ] }, "execution_count": 68, "metadata": {}, "output_type": "execute_result" } ], "source": [ "combinations = 2 ** 32 * 2 ** 32\n", "combinations" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "source": [ "If we can do a billion tests per second, how many years would we have to wait?" ] }, { "cell_type": "code", "execution_count": 69, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:54.965001Z", "iopub.status.busy": "2024-01-18T17:13:54.964899Z", "iopub.status.idle": "2024-01-18T17:13:54.967023Z", "shell.execute_reply": "2024-01-18T17:13:54.966723Z" }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [ { "data": { "text/plain": [ "584.5420460906264" ] }, "execution_count": 69, "metadata": {}, "output_type": "execute_result" } ], "source": [ "tests_per_second = 1000000000\n", "seconds_per_year = 60 * 60 * 24 * 365.25\n", "tests_per_year = tests_per_second * seconds_per_year\n", "combinations / tests_per_year" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "source": [ "We see that on average, we'd have to wait for 584 years. Clearly, pure random choices are not sufficient as sole testing strategy." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Exercise 4: To Infinity and Beyond" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" }, "solution2": "hidden", "solution2_first": true }, "source": [ "When we say that `my_sqrt_fixed(x)` works for all _finite_ numbers $x$: What happens if you set $x$ to $\\infty$ (infinity)? Try this out!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "source": [ "**Solution.** `my_sqrt_fixed(` $\\infty$ `)` times out. This is because dividing $\\infty$ by any finite number (as the Newton-Raphson-method does) again yields $\\infty$, so we're stuck in an infinite loop:" ] }, { "cell_type": "code", "execution_count": 70, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:54.968901Z", "iopub.status.busy": "2024-01-18T17:13:54.968785Z", "iopub.status.idle": "2024-01-18T17:13:54.970415Z", "shell.execute_reply": "2024-01-18T17:13:54.970175Z" }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [], "source": [ "from ExpectError import ExpectTimeout" ] }, { "cell_type": "code", "execution_count": 71, "metadata": { "execution": { "iopub.execute_input": "2024-01-18T17:13:54.972220Z", "iopub.status.busy": "2024-01-18T17:13:54.972100Z", "iopub.status.idle": "2024-01-18T17:13:55.979348Z", "shell.execute_reply": "2024-01-18T17:13:55.978932Z" }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "Traceback (most recent call last):\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_71717/3033877499.py\", line 4, in \n", " y = my_sqrt_fixed(infinity)\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_71717/3001478627.py\", line 5, in my_sqrt_fixed\n", " return my_sqrt(x)\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_71717/2661069967.py\", line 5, in my_sqrt\n", " while approx != guess:\n", " File \"/Users/zeller/Projects/fuzzingbook/notebooks/Timeout.ipynb\", line 43, in timeout_handler\n", " raise TimeoutError()\n", "TimeoutError (expected)\n" ] } ], "source": [ "infinity = float('inf') # that's how to get an infinite number\n", "\n", "with ExpectTimeout(1):\n", " y = my_sqrt_fixed(infinity)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "source": [ "Lesson learned: If you test a program with numbers, always be sure to include extreme values." ] } ], "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.10.2" }, "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 }, "toc-autonumbering": false, "toc-showtags": false, "vscode": { "interpreter": { "hash": "4185989cf89c47c310c2629adcadd634093b57a2c49dffb5ae8d0d14fa302f2b" } } }, "nbformat": 4, "nbformat_minor": 4 }