1. Tracking causes and effects

The following method intends to compute the n-th Fibonacci number, but contains a bug for the first two numbers (Java source).

 0: static int fib(int n) {
 1:   int f = 0; 
 2:   int f0 = 1;
 3:   int f1 = 1;
 4:   while (n > 1) {
 5:     n--;
 6:     f = f0 +f1;
 7:     f0 = f1;
 8:     f1 = f; }
 9:   return f; }

1. For each statement, determine the statements that are data-dependent on it.
2. For each statement, determine the statements that are control-dependent on it.
3. Assume we are on line 8 in the computation of fib(2). Successively compute the backward-dependent statements. Does this explain why the defect in this program shows only for the first two Fibonacci numbers?

2. Ordinary debugging

The Merge sort is one of the most common algorithms used to sort arrays. The class MergeSort implements this algorithm. However, there is a bug in the implementation of the method sort. Debug the previous implementation using the debugging options of your favourite IDE (e.g. eclipse), in order to find the error.

3. Input minimisation

In this exercise we take a look at one particular algorithm for minimising a (failing) test input: the ddmin algorithm (published here).

Your task is the following:

1. Read the javadoc on the DDMin and DDTest class.
2. Read the source code of the Buggy class.
3. Read the source code of the BuggyFail class and run its main method.
4. Answer the question the main method.

4. When was this bug introduced?

In this scenario, we will pretend that we are working on a little software project, implementing a merge sort function. Like in any project, we work with a version control system.

The merge function has seen many improvements, and has been constantly tested. Everything seems to be working well. However, one day someone reports a bug to your project, observing that the following list is not sorted correctly:

{3, 6, 8, 7, 1, 5, 2}

Since we never tested this input, the corresponding bug might have been introduced in any of the earlier versions of the merge function. We will use our version-controlled system to find out where the bug originated.

1. Write a unit test for the reported bug. Do not extend SortTest, but instead create a new file (e.g. SortTestNew.java). We will move the test to SortTest once the bug is fixed.
2. Create a copy of runTest.sh to run SortTestNew instead, verifying that we indeed have a bug.
3. Now, use git bisect to find the change that introduced the bug. You can assume that the bug was not present in the very first commit of the repository, i.e. the first commit was good. You might need to learn a little about git first. Try to use git bisect run the automate the search!
4. Once you found the change that caused the bug, identifying the mistake and fixing it should be straightforward. Do so.
5. Add the new unit test to SortTest and remove SortTestNew. You can commit the fix if you want to. Congratulations!

5. Additional quiz-questions from the exercise session:

1) x = 4;
2) if (y == 2)
3)   x = 7;
4) z = x;

1) x = 4;
2) if (y == 2)
3)   x = 7;
4) else
5)   x = 5;
6) z = x;

1) if (y == 4)
2)   x = 3;
3) x = x + 1;

Bugfinding tools

• FindBugs - eclipse update page at http://findbugs.cs.umd.edu/eclipse/.
• Checkstyle - eclipse update page at http://eclipse-cs.sf.net/update/, instructions here.
• Google's CodePro - eclipse update (Indigo, works for Juno too) at http://dl.google.com/eclipse/inst/codepro/latest/3.7.
• PMD - eclipse update page at http://pmd.sf.net/eclipse.
• Soot - eclipse update page at http://www.sable.mcgill.ca/soot/eclipse/updates/.