Testing

In CSE1020, we ask you to create an application that solves a problem. You can view the problem statement as a contract: given certain valid inputs your program should produce the corresponding outputs.

If your program is supplied valid inputs, then the program's precondition is satisfied. Testing determines if your program satisfies its postconditions.

Formal Verification

CSE 3341 Introduction to Program Verification

Every program implicitly asserts a theorem to the effect that if certain input conditions are met then the program will do what its specifications or documentation says it will. Making that theorem true is not merely a matter of luck or patient debugging; making a correct program can be greatly aided by a logical analysis of what it is supposed to do, and for small pieces of code a proof that the code works can be produced hand-in-hand with the construction of the code itself. Good programming style works in part because it makes the verification process easier and this in turn makes it easier to develop more complex algorithms from simple ones.

Testing

The basic idea is simple:

1. Create some inputs for your program.
2. Run your program using the inputs.
3. Analyze the outputs.

If you could test every possible input then you could prove that your program was correct, but this is usually infeasible.

Implement Math.sqrt

Heron's method (name after Hero of Alexandria, 1st century Greek mathematician).

To compute the square root of S:

0. Choose a starting value x₀
1. Let x₁ be the average of x₀ and S / x₀
2. Let x₂ be the average of x₁ and S / x₁
3. Let x₃ be the average of x₂ and S / x₂, and so on

Mathematically, Heron's method is guaranteed to converge to the square root of S as the number of iterations approaches infinity.

How do you know when to stop?

Solution

import java.io.PrintStream;
import java.util.Scanner;

public class SquareRoot
{
   public static void main(String[] args)
   {
      PrintStream output = System.out;
      Scanner input = new Scanner(System.in);
      
      final double S = input.nextDouble();
      final double EPSILON = input.nextDouble();
      
      double delta = Double.POSITIVE_INFINITY;
      double x = S;
      
      while (Math.abs(delta) > EPSILON)
      {
         double xi = (x + S / x) / 2.0;
         delta = xi - x;
         x = xi;
      }
      output.println(x);
   }
}

Testing our Solution

To test our solution, we need an oracle: an independent mechanism that can establish correctness in an authoritative way.

Algorithm Oracle

Sometimes, we can find another component that solves the same problem as the one we are trying to solve.

In this case, a suitable algorithm oracle is Math.sqrt.

Test Harness

import java.io.PrintStream;
import type.lib.ToolBox;

public class SquareRootHarness
{
   public static void main(String[] args)
   {
      PrintStream output = System.out;

      // launch SquareRoot with inputs 25.0 and 1E-5
      double s = 25.0;
      double epsilon = 1E-5;
      String in = s + "\n" + epsilon + "\n";
      String out = ToolBox.launch("SquareRoot", in);

      // get the result
      double root = Double.parseDouble(out);

      // compare to oracle
      double oracle = Math.sqrt(s);
      if (Math.abs(oracle - root) < epsilon)
      {
         output.println("passed test");
      }
      else
      {
         output.println("failed test");
      }
   }
}

Verification Oracle

Sometimes, the solution can be verified directly.

In this case, we have the mathematical property that

S

and

sqrt(S) * sqrt(S)

are the same.

Test Harness

import java.io.PrintStream;
import type.lib.ToolBox;

public class SquareRootHarness
{
   public static void main(String[] args)
   {
      PrintStream output = System.out;

      // launch SquareRoot with inputs 25.0 and 1E-5
      double s = 25.0;
      double epsilon = 1E-5;
      String in = s + "\n" + epsilon + "\n";
      String out = ToolBox.launch("SquareRoot", in);

      // get the result
      double root = Double.parseDouble(out);

      // compare to oracle
      double oracle = root * root;
      double precision = 2.0 * epsilon + epsilon * epsilon;
      if (Math.abs(oracle - s) < precision)
      {
         output.println("passed test");
      }
      else
      {
         output.println("failed test");
      }
   }
}

The Test Vector

What values should we use as input? Any value that satisfies the preconditions can be used, but some kinds of values tend to reveal common errors.

Domain Coverage

Test values should cover the entire range of valid inputs. Most values should be in the likely range (if such a range exists).

Boundary values should always be tested.

Choosing values for domain coverage can be done just by looking at the requirements, not the code. This leads to the idea of black box testing, which is testing the code without seeing it.

Execution-Path Coverage

Test values should be chosen to ensure that every statement and every path in the code will execute.

You can only do this if you can see the code, which is called white box testing.