Testing, Debugging, and Verification TDA567/DIT082, LP2, HT2018
Exercises Week 3

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.
    Remember we only need to consider those statements that perform a write. Below A --> B means that B is data-dependent on A (we only focus on the body of the method).
    • 0 --> 4
    • 5 --> 4
    • 0 --> 5
    • 5 --> 5
    • 2 --> 6
    • 3 --> 6
    • 7 --> 6
    • 8 --> 6
    • 3 --> 7
    • 8 --> 7
    • 6 --> 8
    • 1 --> 9
    • 6 --> 9
    You can use the control flow graph for the previous method to easily track these depencies. CFG.
  2. For each statement, determine the statements that are control-dependent on it.
    The statements {5,6,7,8} are control-dependent on 4, and the statements {1,2,3,4,9} are control-dependent on 0.
  3. Assume we are on line 8 in the computation of fib(2). Successively compute the backward-dependent statements.
    It depends on {6,4,2,3,7,5}
    Does this explain why the defect in this program shows only for the first two Fibonacci numbers?
    Indirectly, one can see that when executing within the loop, if one walks backwards the dependencies (control and data), the initialization of f at line 1 is not among the dependencies walked. This means that the cause of infection is removed since the bad initialization value is not propagated inside the loop. So there will not be a failure whenever the loop is entered, but there will be a failure if it is not entered, that is, when n=0 or n=1.

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.

The bug is in the manner the indexes are handle when performing the recursive calls, i.e. one value in the array is missed every time. Replacing sort(array, from, m - 1) by, for instace, sort(array, from, m) would fix this method.

Input minimisation

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

Download the following archive: DDMin.zip

In eclipse, import the project by choosing File -> Import ... -> Existing Project into Workspace.
Select archive file, browse to the downloaded zip and click Finish.

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.

If you have AspectJ installed, you can instead download this version which uses aspects for logging, to avoid cluttering of the code: DDMinAspects.zip

A short annotation on the debugging output: 
ddmin 2 - [a,  , d, e, b, u, g, g, i, n, g,  , t, e, s, t]
We started ddmin with chunk size 2. Thus, we split into two halves. The first test is when we removed the first chunk (half), and then the test when we removed the second chunk: 
  test [i, n, g,  , t, e, s, t] PASS
  test [a,  , d, e, b, u, g, g] PASS
Both passed, so we are not that lucky that we can minimise the failing input a lot in one go. Instead, ddmin now tries to remove a shorter chunk, by dividing the input into 4 parts (doubling the current size). 
ddmin 4 - [a,  , d, e, b, u, g, g, i, n, g,  , t, e, s, t]
We now remove the first chunk, that is 1/4 of the whole input, [a, , d, e]: 
  test [b, u, g, g, i, n, g,  , t, e, s, t] FAIL
Now ddmin was succesful, and 'already did its job': it reduced the original input and still found a failing test case. However, the goal is to minimise as much as possible so we go further on this failed input. Having removed one chunk, we also continue on a chunk size of one shorter (4-1=3). We thus get the three chunks [b, u, g, g], [i, n, g, ] and [t, e, s, t]: 
ddmin 3 - [b, u, g, g, i, n, g,  , t, e, s, t]
  test [i, n, g,  , t, e, s, t] PASS
  test [b, u, g, g, t, e, s, t] PASS
  test [b, u, g, g, i, n, g,  ] FAIL
Another chunk can be removed succesfully! Again, we continue on that smaller input and continue on chunk size (3-1=2): 
ddmin 2 - [b, u, g, g, i, n, g,  ]
  test [i, n, g,  ] PASS
  test [b, u, g, g] PASS
Both succeeded, so we again double the number of chunks, reducing the size of each chunk and making it more possible that the remaining input still fails: 
ddmin 4 - [b, u, g, g, i, n, g,  ]
  test [g, g, i, n, g,  ] FAIL
The rest of the algorithm goes on similarly: 
ddmin 3 - [g, g, i, n, g,  ]
  test [i, n, g,  ] PASS
  test [g, g, g,  ] FAIL
ddmin 2 - [g, g, g,  ]
  test [g,  ] PASS
  test [g, g] PASS
ddmin 4 - [g, g, g,  ]
  test [g, g,  ] PASS
  test [g, g,  ] PASS
  test [g, g,  ] PASS
  test [g, g, g] FAIL
ddmin 3 - [g, g, g]
  test [g, g] PASS
  test [g, g] PASS
  test [g, g] PASS
At this point the number of chunks is 3, but that is also the length of the array. So increasing the number of chunks is not possible, since we cannot make chunks that small (the smallest ones contain at least one element, otherwise we don't make the input shorter). Therefore the algorithm concludes: 
Minimalised version of 'a debugging test' is 'ggg'.
However, due to our 'greedyness', we first dropped the first four elements of the array [a, , d, e, b, u, g, g, i, n, g, , t, e, s, t], thereby removing the possibility of arriving at minimal input [e,e]. This demonstrates that the algorithm gets a local optimal, but not a global optimal.

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.

Download the archive: bisect.zip

Unzip this archive on your computer. It contains a git repository.

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.
    SortTestNew.java: 
    import static org.junit.Assert.*;
import org.junit.Test;
public class SortTestNew {
  @Test
  public void testReportedBug() {
    int[] input = {3, 6, 8, 7, 1, 5, 2};
    int[] expected = {1, 2, 3, 5, 6, 7, 8};
    Sort.sort(input);
    assertArrayEquals(expected, input);
  }
}
  2. Create a copy of runTest.sh to run SortTestNew instead, verifying that we indeed have a bug.
    runTestNew.sh: 
    #!/bin/bash
javac -cp /usr/share/java/junit4.jar:. SortTestNew.java
java -cp /usr/share/java/junit4.jar:. org.junit.runner.JUnitCore SortTestNew
  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!
    Start the bisection: 
    git bisect start
    Mark the last commit as bad: 
    git bisect bad HEAD
    Mark the first commit as good: 
    git bisect good 3c4b7609242879c72fa052df15b3d5039a1a0481
    Git bisect has no checked out the commit halfway the known bad and good version. You can either continue to manually mark commits as bad or good (run the test and then run git bisect bad or good depending on the outcome. Or you can use the script: 
    git bisect run ./runTestNew.sh
  4. Once you found the change that caused the bug, identifying the mistake and fixing it should be straightforward. Do so.
    The problem is that we no longer treat arrays of odd length specially. We should write: 
    int rightLength = array.length / 2;
if (array.length % 2 == 1)
  rightLength += 1;
int[] right = new int[rightLength];
  5. Add the new unit test to SortTest and remove SortTestNew. You can commit the fix if you want to. Congratulations!

Additional quiz-questions from the exercise session:

1) x = 4;
2) if (y == 2)
3)   x = 7;
4) z = x;
1. On which lines is line 4 data-dependent? 
1) x = 4;
2) if (y == 2)
3)   x = 7;
4) else
5)   x = 5;
6) z = x;
2. On which lines is line 6 data-dependent? 
1) if (y == 4)
2)   x = 3;
3) x = x + 1;
3. On which lines is line 2 control-dependent?
4. On which lines is line 3 control-dependent?
5. On which lines is line 3 backward-dependent?

6. Given a test on arrays of numbers, that fails if we have two consequetive values. We are given the failing input [1,2,2,3]. What is the first smaller array on which ddmin([1,2,2,3], 2) performs the test that returns fail? (note: we are not asking for the final result of ddmin, although that is also a good exercise).

Bugfinding tools

Below you can find a list of several tools which you can use to debug your (Java) programs.


Home | Course | Schedule | Exam | Exercises | Labs | Evaluation | Tools | Links Srinivas Pinisetty, Nov 9, 2018