SUNY Geneseo, Department of Computer Science

Lab 10 -- Testing

CSci 240 , Spring 2007

Prof. Doug Baldwin

Due Tuesday, April 10

Purpose

Background

In this lab you will face and track down some fairly subtle bugs. In particular, they don't always show up -- with some inputs, the buggy programs produce perfectly fine results, with others they produce incorrect ones. In other words, you first need to find test data that reveal the bugs, then you can isolate and correct them.

The first thing to realize is that one test is never enough. Really testing a program requires a whole suite of test cases. Typically each test case consists of one input for the program, and a separate run of the program is needed to test each test case.

Choosing test data is a big concern in all programming. Before a programmer or software company releases a program into the world, they want to be sure that the program doesn't contain any bugs. The best way developers have of verifying that a program is bug-free is still thorough testing (in principle one can mathematically prove that a program is bug-free, but it is a tremendously difficult task given the mathematical techniques presently available). I doubt that there are any significant programs available today that don't contain bugs. This isn't because their developers didn't try to debug the programs, it's because the bug-hunters didn't test the programs on the exact combination of inputs that would have made the bugs show up.

While finding bugs is often as much a matter of luck as of skill, there are some strategies that can at least make your luck better. Here are some of them:

• Test the program on "special" values. A "special" value is any value that is somehow distinguished in the algorithm or problem. There are two approaches to identifying special values, both of which should be used for best results:
  1. In "black box" testing the tester knows nothing about how the program works, only what problem it solves. From this point of view, special values are ones that have unusual properties vis a vis the problem. For example, if the problem is to compute income taxes, special values might include incomes right at the limits of each tax bracket, an income of 0 (special because it's the lowest income you can possibly have), etc.
  2. In "white box" testing, the tester knows how the program works. Here, special values are ones that somehow determine what the program does. For example, values that determine which way a conditional goes, values that distinguish base cases from recursive ones, boundary values (i.e., the smallest or largest values on which an arm of a conditional, method, or other block of code can operate), etc.
• Force the program through all possible execution paths. The term "execution path" refers to the series of statements a program executes -- a typical program has many different execution paths because different arms of conditionals can be chosen for execution, loops or recursions can repeat different numbers of times, etc. In fact, realistic programs have so many execution paths that it isn't practical to execute all of them. However, your test suite should include cases that ensure that every arm of each conditional is executed at least once, that every recursive method is executed at least once with an argument that takes it straight to its base case and at least once with an argument that causes one or more recursions, etc.
• Use the scientific method. When you see a situation in which the program produces the wrong answer, try to form a hypothesis about what the bug is. Make up a new test case that tests this hypothesis, i.e., that will produce a predictable output if the bug is what you think it is. Add this case to your test suite. Try the test and see if you get the predicted result. Even if the bug seems so obvious that you don't need to test your theory, you may still be wrong, the test case may detect related bugs that you don't know about yet, and having the test in your test suite will help keep the bug from coming back later.
• Regression test. "Regression testing" is simply the practice of rerunning an entire test suite through a program after the program has been changed. The changes made to a program to fix one bug often introduce new ones. Even if you think you no longer need to use certain tests on a program, try them anyhow. You'll be surprised.

Exercise

Your job is to test and possibly debug three programs. You can find the programs in the folder named "/ComputerScience/baldwin/CSci240/Testing" on the "OutBox" server. Each program is an XCode project, in its own subfolder of the "Testing" folder.

All the programs are set up to read an input from you and display some result. Most of the programs will then read more inputs and print mor results until you indicate that you want to stop. However, because the programs are of varying ages, they have different methods for reading input and indicating that you want to stop. Exactly what each program expects should be evident from the instructions it prints, however.

All I will tell you right now about the programs is that they might contain bugs. To the best of my knowledge no program contains more than one bug, but some might not contain any. Furthermore, how one counts bugs is somewhat subjective -- what I consider one bug because I made one change to a program to create it might be considered several bugs by someone else, e.g., because the correction they think of involves adding code in several places, because the bug's symptoms show up on several test cases, etc. Your basic job is to test each program until you either know that it has a bug, or are certain that it doesn't. If the program has a bug, you should fix it, and retest to be certain that the bug is completely fixed.

Exercise 1

The first exercise is to test the program named "Root." This program's job is to print the square root of any non-negative real number you give it, accurate to 2 decimal places. For example, if you input 4.0 to "Root", it should print 2.00. Beware, however, that real numbers are notorious for round-off error in computing, and all that "Root" guarantees is an answer that is within +/- 0.01 of the actual root. Thus, it could legally display the square root of 4.0 as 1.99, 2.01, 2.005, etc.

Exercise 2

Test the program named "Sort." This program sorts an array of words into ascending alphabetical order. The program will prompt you for words, one at a time. This is the only program in this exercise that only executes on one input (ie., list of words) each time you run it. You must rerun it in order to test it on a new input.

"Sort" uses a sorting algorithm known as Bubble Sort to sort lists. Comments in the program explain the basic idea behind Bubble Sort.

For up to 2 points extra credit, derive the worst-case asymptotic execution time of Bubble Sort.

Exercise 3

Test the program named "Number." This program converts a string, representing a real number in binary scientific notation, to an equivalent Java double. There are extensive comments at the beginning of the program that explain the expected format for input numbers and how to interpret them.

Note that what "Number" does is roughly what library routines such as Java's parseDouble do, although they typically work in decimal, not binary. Nonetheless, this program gives you a glimpse of what must be going on inside such library methods.

Follow-Up

I will grade this exercise in a face-to-face meeting with you. Make an appointment to meet with me at some time convenient for you, as long as that time is before the end of the due date above. Meetings only need to be 15 minutes long. You can make an appointment by signing up on the copy of my schedule on the bulletin board outside my office.

Be prepared to explain, during your meeting, how you tested each program, whether you found any bugs, and, if so, how you fixed them. Written comments about the test cases you used and corrections you made, either in the programs or on a separate sheet of paper, would be good to have. I would also like to read and run the programs during our meeting. To do this, you can either bring the program to my office on a laptop computer, or we can go to a lab during the meeting.

If you do the extra credit part of this lab, bring your derivation to your meeting.