06 TESTING AND DEBUGGING

What is testing and debugging?

Testing is the process of running a program to try and ascertain whether or not it works as intended. Debugging is the process of trying to fix a program that you already know does not work as intended.

How to design problems in ways that make them easier to test and debug?

The key to doing this is break- ing the program up into separate components that can be implemented, tested, and debugged independently of other components.

6.1 Testing

What is the most important thing to say about testing?

The most important thing to say about testing is that its purpose is to show that bugs exist, not to show that a program is bug-free. To quote Edsger Dijkstra, “Program testing can be used to show the presence of bugs, but never to show their absence!”39 Or, as Albert Einstein reputedly said, “No amount of experi- mentation can ever prove me right; a single experiment can prove me wrong.”

What is the key to testing?

The key to testing is finding a collection of inputs, called a test suite, that has a high likelihood of revealing bugs, yet does not take too long to run. The key to doing this is partitioning the space of all possible inputs into subsets that provide equivalent information about the correctness of the program, and then con- structing a test suite that contains at least one input from each partition. (Usually, constructing such a test suite is not actually possible. Think of this as an unachievable ideal.)

How to partition the set of possible inputs?

A partition of a set divides that set into a collection of subsets such that each element of the original set belongs to exactly one of the subsets. If one tested the implementation on at least one value from each of these subsets, there would be reasonable probability (but no guarantee) of exposing a bug if one exists.

For most programs, finding a good partitioning of the inputs is far easier said than done. Typically, people rely on heuristics¹ based on exploring different paths through some combination of the code and the specifications. Heuristics based on exploring paths through the code fall into a class called glass-box testing. Heuristics based on exploring paths through the specification fall into a class called black-box testing.

What are the positive features of the independence of black-box testing?

1. It reduces the likelihood of generating test suites that exhib- it mistakes that are correlated with mistakes in the code.
2. It is robust with respect to implementation changes.

What boundary condition should be tested?

When looking at lists, this often means looking at the empty list, a list with exactly one element, and a list con- taining lists. When dealing with numbers, it typically means looking at very small and very large values as well as “typical” values.

For sqrt, for example, it might make sense to try values of x and epsilon similar to those in here:

X	Epsilon
0.0	0.0001
25.0	0.0001
0.5	0.0001
2.0	0.0001
2.0	1.0/2.0**64
1.0/2.0**64	1.0/2.0**64
2.0**64.0	1.0/2.0**64
1.0/2.0**64	2.0**64.0
2.0**64.0	2.0**64.0

Another important boundary condition to think about is aliasing. Consider, for example, the code

def copy(L1, L2):
    """ Assumes L1, L2 are lists
        Mutates L2 to be a copy of L1"""
    while len(L2) > 0: #remove all elements from L2
        L2.pop() #remove last element of L2
    for e in L1: #append L1's elements to initially empty L2
        L2.append(e)
        
L = [1, 2, 3]
copy(L, L)
print(L)

If any of these tests fail, something needs to be fixed. Where do those “something” lie?

Perhaps there is a bug in the code that needs to be fixed, or perhaps the specification needs to be changed so that it is easier to meet. It might, for example, be unreasonable to expect to find an approximation of a square root when epsilon is ridiculously small.

Why it is rarely sufficient to do black-box testing?

Without looking at the internal structure of the code, it is impossible to know which test cases are likely to provide new information. Consider the trivial example:

def isPrime(x):
    """ Assumes x is a nonnegative int
        Returns True if x is prime; False otherwise""" 
    if x <= 2:
        return False
    for i in range(2, x):
        if x%i == 0: 
            return False
    return True

---

1. heuristics: [Computing] proceeding to a solution by trial and error or by rules that are only loosely defined.↩