# 6.5. Black-box and Glass-box Testing¶

We would like to know that a program works on all possible inputs. The problem
with testing is that it is usually infeasible to try all the possible inputs.
For example, suppose that we are implementing a module that provides an abstract
data type for rational numbers. One of its operations might be an addition
function `plus`

, e.g.:

```
module type RATIONAL = sig
(** A [t] is a rational. *)
type t
(** [create p q] is the rational number [p/q].
Raises: [Invalid_argument "0"] if [q] is 0. *)
val create : int -> int -> t
(** [plus r1 r2] is [r1 + r2] *)
val plus : t -> t -> t
end
module Rational : RATIONAL = struct
(** AF: [(p, q)] represents the rational number [p/q]
RI: [q] is not 0. *)
type t = int * int
let create p q =
if q = 0 then invalid_arg "0" else (p, q)
let plus (p1, q1) (p2, q2) =
(p1 * q2 + p2 * q1, q1 * q2)
end
```

```
module type RATIONAL =
sig type t val create : int -> int -> t val plus : t -> t -> t end
```

```
module Rational : RATIONAL
```

What would it take to exhaustively test just this one function? We’d want to try
all possible rationals as both the `r1`

and `r2`

arguments. A rational is formed
from two ints, and there are \(2^{63}\) ints on a modern OCaml implementation.
Therefore there are approximately \((2^{63})^4 = 2^{252}\) possible inputs to the
`plus`

function. Even if we test one addition every nanosecond, it will take
about \(10^{59}\) years to finish testing this one function.

Clearly we can’t test software exhaustively. But that doesn’t mean we should give up on testing. It just means that we need to think carefully about what our test cases should be so that they are as effective as possible at convincing us that the code works.

Consider our `create`

function, above. It takes in two integers `p`

and `q`

as
arguments. How should we go about selecting a relatively small number of test
cases that will convince us that the function works correctly on all possible
inputs? We can visualize the space of all possible inputs as a large square:

There are about \(2^{126}\) points in this square, so we can’t afford to test them all. And testing them all is going to mostly be a waste of time—most of the possible inputs provide nothing new. We need a way to find a set of points in this space to test that are interesting and will give a good sense of the behavior of the program across the whole space.

Input spaces generally comprise a number of subsets in which the behavior of the code is similar in some essential fashion across the entire subset. We don’t get any additional information by testing more than one input from each such subset.

If we test all the interesting regions of the input space, we have achieved good
*coverage*. We want tests that in some useful sense cover the space of possible
program inputs.

Two good ways of achieving coverage are *black-box testing* and *glass-box
testing*. We discuss those, next.

## 6.5.1. Black-box Testing¶

In selecting our test cases for good coverage, we might want to consider both
the specification and the implementation of the program or module being tested.
It turns out that we can often do a pretty good job of picking test cases by
just looking at the specification and ignoring the implementation. This is known
as **black-box testing**. The idea is that we think of the code as a black box
about which all we can see is its surface: its specification. We pick test cases
by looking at how the specification implicitly introduces boundaries that divide
the space of possible inputs into different regions.

When writing black-box test cases, we ask ourselves what set of test cases that
will produce distinctive behavior as predicted by the specification. It is
important to try out both *typical inputs* and inputs that are *boundary cases*
aka *corner cases* or *edge cases*. A common error is to only test typical
inputs, with the result that the program usually works but fails in less
frequent situations. It’s also important to identify ways in which the
specification creates classes of inputs that should elicit similar behavior from
the function, and to test on those *paths through the specification*. Here are
some examples.

**Example 1.**

Here are some ideas for how to test the `create`

function:

Looking at the square above, we see that it has boundaries at

`min_int`

and`max_int`

. We want to try to construct rationals at the corners and along the sides of the square, e.g.`create min_int min_int`

,`create max_int 2`

, etc.The line

`p=0`

is important because`p/q`

is zero all along it. We should try`(0, q)`

for various values of`q`

.We should try some typical

`(p, q)`

pairs in all four quadrants of the space.We should try both

`(p, q)`

pairs in which`q`

divides evenly into`p`

, and pairs in which`q`

does not divide into`p`

.Pairs of the form

`(1, q)`

,`(-1, q)`

,`(p, 1)`

,`(p, -1)`

for various`p`

and`q`

also may be interesting given the properties of rational numbers.

The specification also says that the code will check that `q`

is not zero. We
should construct some test cases to ensure this checking is done as advertised.
Trying `(1, 0)`

, `(max_int, 0)`

, `(min_int, 0)`

, `(-1, 0)`

, `(0, 0)`

to see that
they all raise the specified exception would probably be an adequate set of
black-box tests.

**Example 2.**

Consider a function `list_max`

:

```
(** Return the maximum element in the list. *)
val list_max: int list -> int
```

What is a good set of black-box test cases? Here the input space is the set of all possible lists of ints. We need to try some typical inputs and also consider boundary cases. Based on this spec, boundary cases include the following:

A list containing one element. In fact, an empty list is probably the first boundary case we think of. Looking at the spec above, we realize that it doesn’t specify what happens in the case of an empty list. Thus, thinking about boundary cases is also useful in identifying errors in the specification.

A list containing two elements.

A list in which the maximum is the first element. Or the last element. Or somewhere in the middle of the list.

A list in which every element is equal.

A list in which the elements are arranged in ascending sorted order, and one in which they are arranged in descending sorted order.

A list in which the maximum element is

`max_int`

, and a list in which the maximum element is`min_int`

.

**Example 3.**

Consider the function `sqrt`

:

```
(** [sqrt x n] is the square root of [x] computed to an accuracy of [n]
significant digits.
Requires: [x >= 0] and [n >= 1]. *)
val sqrt : float -> int -> float
```

The precondition identifies two possibilities for `x`

(either it is 0 or
greater) and two possibilities for `n`

(either it is 1 or greater). That leads
to four “paths through the specification”, i.e., representative and boundary
cases for satisfying the precondition, which we should test:

`x`

is 0 and`n`

is 1`x`

is greater than 0 and`n`

is 1`x`

is 0 and`n`

is greater than 1`x`

is greater than 0 and`n`

is greater than 1.

## 6.5.2. Black-box Testing of Data Abstractions¶

So far we’ve been thinking about testing just one function at a time. But data
abstractions usually have many operations, and we need to test how those
operations interact with one another. It’s useful to distinguish *consumer* and
*producers* of the data abstraction:

A consumer is an operation that takes a value of the data abstraction as input.

A producer is an operation that a value of the data abstraction.

For example, consider this set abstraction:

```
module type Set = sig
(** ['a t] is the type of a set whose elements have type ['a]. *)
type 'a t
(** [empty] is the empty set. *)
val empty : 'a t
(** [size s] is the number of elements in [s]. *
[size empty] is [0]. *)
val size : 'a t -> int
(** [add x s] is a set containing all the elements of
[s] as well as element [x]. *)
val add : 'a -> 'a t -> 'a t
(** [mem x s] is [true] iff [x] is an element of [s]. *)
val mem : 'a -> 'a t -> bool
end
```

```
module type Set =
sig
type 'a t
val empty : 'a t
val size : 'a t -> int
val add : 'a -> 'a t -> 'a t
val mem : 'a -> 'a t -> bool
end
```

The `empty`

and `add`

functions are producers; and the `size`

, `add`

and `mem`

functions are consumers.

When black-box testing a data abstraction, we should test how each consumer of
the data abstraction handles every path through each producer of it. In the
`Set`

example, that means testing the following:

how

`size`

handles the`empty`

set;how

`size`

handles a set produced by`add`

, both when`add`

leaves the set unchanged as well as when it increases the set;how

`add`

handles sets produced by`empty`

as well as`add`

itself;how

`mem`

handles sets produced by`empty`

as well as`add`

, including paths where`mem`

is invoked on elements that have been added as well as elements that have not.

## 6.5.3. Glass-box Testing¶

Black-box testing is a good place to start when writing test cases, but
ultimately it is not enough. In particular, it’s not possible to determine how
much coverage of the implementation a black-box test suite actually
achieves—we actually need to know the implementation source code. Testing
based on that code is known as *glass box* or *white box* testing. Glass-box
testing can improve on black-box by testing *execution paths* through the
implementation code: the series of expressions that is conditionally evaluated
based on if-expressions, match-expressions, and function applications. Test
cases that collectively exercise all paths are said to be *path-complete*. At a
minimum, path-completeness requires that for every line of code, and even for
every expression in the program, there should be a test case that causes it to
be executed. Any unexecuted code could contain a bug if has never been tested.

For true path completeness we must consider all possible execution paths from start to finish of each function, and try to exercise every distinct path. In general this is infeasible, because there are too many paths. A good approach is to think of the set of paths as the space that we are trying to explore, and to identify boundary cases within this space that are worth testing.

For example, consider the following implementation of a function that finds the maximum of its three arguments:

```
let max3 x y z =
if x > y then
if x > z then x else z
else
if y > z then y else z
```

```
val max3 : 'a -> 'a -> 'a -> 'a = <fun>
```

Black-box testing might lead us to invent many tests, but looking at the
implementation reveals that there are only four paths through the code—the
paths that return `x`

, `z`

, `y`

, or `z`

(again). We could test each of those
paths with representative inputs such as: `max3 3 2 1`

, `max3 3 2 4`

,
`max3 1 2 1`

, `max3 1 2 3`

.

When doing glass box testing, we should include test cases for each branch of each (nested) if expression, and each branch of each (nested) pattern match. If there are recursive functions, we should include test cases for the base cases as well as each recursive call. Also, we should include test cases to trigger each place where an exception might be raised.

Of course, path complete testing does not guarantee an absence of errors. We
still need to test against the specification, i.e., do black-box testing. For
example, here is a broken implementation of `max3`

:

```
let max3 x y z = x
```

The test `max 2 1 1`

is path complete, but doesn’t reveal the error.

## 6.5.4. Glass-box Testing of Data Abstractions¶

Look at the abstraction function and representation invariant for hints about
what boundaries may exist in the space of values manipulated by a data
abstraction. The rep invariant is a particularly effective tool for constructing
useful test cases. Looking at the rep invariant of the `Rational`

data
abstraction above, we see that it requires that `q`

is non-zero. Therefore we
should construct test cases to see whether it’s possible to cause that invariant
to be violated.

## 6.5.5. Black-box vs. Glass-box¶

Black-box testing has some important advantages:

It doesn’t require that we see the code we are testing. Sometimes code will not be available in source code form, yet we can still construct useful test cases without it. The person writing the test cases does not need to understand the implementation.

The test cases do not depend on the implementation. They can be written in parallel with or before the implementation. Further, good black-box test cases do not need to be changed, even if the implementation is completely rewritten.

Constructing black-box test cases causes the programmer to think carefully about the specification and its implications. Many specification errors are caught this way.

The disadvantage of black box testing is that its coverage may not be as high as we’d like, because it has to work without the implementation.

## 6.5.6. Bisect¶

Glass-box testing can be aided by *code-coverage tools* that assess how much of
the code has been exercised by a test suite. The bisect_ppx tool for OCaml
can tell you which expressions in your program have been tested, and which have
not. Here’s how it works:

You compile your code using Bisect_ppx (henceforth, just Bisect for short) as part of the compilation process. It

*instruments*your code, mainly by inserting additional expressions to be evaluated.You run your code. The instrumentation that Bisect inserted causes your program to do something in addition to whatever functionality you programmed yourself: the program will now record which expressions from the source code actually get executed at run time, and which do not. Also, the program will now produce an output file that contains that information.

You run a tool called

`bisect-ppx-report`

on that output file. It produces HTML showing you which parts of your code got executed, and which did not.

How does that help with computing coverage of a test suite? If you run your OUnit test suite, the test cases in it will cause the code in whatever functions they test to be executed. If you don’t have enough test cases, some code in your functions will never be executed. The report produced by Bisect will show you exactly what code that is. You can then design new glass-box test cases to cause that code to execute, add them to your OUnit suite, and create a new Bisect report to confirm that the code really did get executed.

**Bisect Tutorial.**

Download the file sorts.ml. You will find an implementation of insertion sort and merge sort.

Download the file test_sorts.ml. It has the skeleton for an OUnit test suite.

Create a

`dune`

file to execute`test_sorts`

:(executable (name test_sorts) (libraries ounit2) (instrumentation (backend bisect_ppx)))

Run:

$ dune exec --instrument-with bisect_ppx ./test_sorts.exe

That will execute the test suite with Bisect coverage enabled, causing some files named

`bisectNNNN.coverage`

to be produced.Run:

`$ bisect-ppx-report html`

to generate the Bisect report from your test suite execution. The report is in a newly-created directory named

`_coverage`

.Open the file

`_coverage/index.html`

in a web browser. Look at the per-file coverage; you’ll see we’ve managed to test a few percent of`sorts.ml`

with our test suite so far. Click on the link in that report for`sorts.ml`

. You’ll see that we’ve managed to cover only one line of the source code.There are some additional tests in the test file. Try un-commenting those, as documented in the test file, and increasing your code coverage. Between each run, you will need to delete the

`bisectNNNN.coverage`

files, otherwise the report will contain information from those previous runs:`$ rm bisect*.coverage`

By the time you’re done un-commenting the provided tests, you should be at 25% coverage, including all of the insertion sort implementation. For fun, try adding more tests to get 100% coverage of merge sort.

**Parallelism.** OUnit will by default attempt to run some of the tests in
parallel, which reduces the time it takes to run a large test suite, at the
tradeoff of making it nondeterministic in what order the tests run. It’s
possible for that to affect coverage if you are testing imperative code. To make
the tests run one at a time, in order, you can pass the flag
`-runner sequential`

to the executable. OUnit will see that flag and cease
parallelization:

```
$ dune exec --instrument-with bisect_ppx ./test_sorts.exe -- -runner sequential
```