Background

During the Fall 2017 semester, I was fortunate to have enrolled in a software analysis and testing course offered by Prof. Mayur Naik. The class was a survey on the field of software analysis and testing. An integral part of the course was to undertake a project that goes deeper into a certain topic explored during the semester. I was intrigued by a tool called Randoop.

Randoop is a feedback-directed random testing tool. Given a timeout, it tries generating and executing many JUnit test cases. Based on the outcome of the execution, it either discards the test, outputs it to the user, or uses the test to influence further test generation. It is feedback-directed in the sense that it extends upon previously generated tests to explore interesting behaviors. The following section provides an example usage of Randoop.

Motivation

Consider the following RingBuffer Java class. A ring buffer is a buffer that is implemented using an underlying fixed-sized array and wrapping around indices. Although understanding of how exactly the ringbuffer works is not necessary for this section, feel free to read up on the data structure here. It has boolean isFull and isEmpty. It also has a method to enqueue a double into the buffer and a method to dequeue the first entry in the buffer. This data structure is useful in many applications, such as queues, media processing, and data compression.

Assume that all methods are correct, except enqueue where it throws a Null Pointer Exception when the input is -1.

public class RingBuffer {
  public boolean isEmpty() { /* Assume correct */ }
  public boolean isFull() { /* Assume correct */ }
  public void enqueue(double d) {
    //...
    if (d == -1.0) {
      String s = null;
      s.hashCode();
    }
  }
  public double dequeue() { /* Assume correct */ }
  public double peek() { /* Assume correct */ }
}

We can run Randoop on this class and it will generate a files called ErrorTest0.java, ErrorTest1.java, and so on based on how many failing test cases it finds. By examining the generated files, one would immediately notice that the the tests are redundant. Two tests are considered redundant if the source of the bug is the same. Here is a test that Randoop generated.

@Test
public void test001() throws Throwable {
  RingBuffer ringBuffer1 = new RingBuffer((int)'a');
  ringBuffer1.enqueue((double)(short)-1);
}

The last line, which is ringBuffer1.enqueue((double)(short)-1);, is the cause of the bug. This test case is clear and concise, which makes the job of the debugger easier. However, Randoop also generates the following test case.

@Test
public void test010() throws Throwable {
  RingBuffer ringBuffer1 = new RingBuffer((int)'a');
  ringBuffer1.enqueue(0.0d);
  boolean b2 = ringBuffer1.isFull();
  boolean b3 = ringBuffer1.isFull();
  double d4 = ringBuffer1.peek();
  boolean b5 = ringBuffer1.isFull();
  double d6 = ringBuffer1.dequeue();
  boolean b7 = ringBuffer1.isFull();
  boolean b8 = ringBuffer1.isFull();
  boolean b9 = ringBuffer1.isFull();
  ringBuffer1.enqueue((double)(short)-1);
}

This test case is redundant with the previous one. Reducing the number of redundant test cases allows the debugger to focus on distinct bugs, which increases their productivity.

Motivation: reducing the number of redundant test cases increases the productivity of debuggers.

Anatomy of Randoop

In order for the following sections to be understood at a deeper level, the reader will find it helpful to be be more familiar with how Randoop works internally.

What is a Unit Test?

A unit test in Randoop has to parts.

• Test input: code that sets up the test (constructor and method calls)
• Checks: code that asserts that test input behaved as expected.

Randoop generates test inputs randomly, but it generates the checks deterministically. In the following unit test, the assert statements are checks, and the constructor call and add method call are test inputs. The assert statements were generated deterministically, that is Randoop adds a check based on the statement that is being added to the sequence.

public void testAdd() {
  LinkedList<Integer> l = new LinkedList<>();
  assertTrue(l.equals(l));
  boolean b = l.add(0);
  assertTrue(l.size() == 1);
  assertTrue(l.equals(l);
}

The way Randoop checks redundancy (as of 3.1.15) is using equality. The following code is from the class randoop.generation.ForwardGenerator and it checks if the new sequence has already been generated.

private ExecutableSequence createNewUniqueSequence() {
  if (this.allSequences.contains(newSequence)) {
  return null;
  }
}

As we defined in the table, a statement in Randoop is a TypedOperation and a list of inputs. The inputs are actually represented by relative negative indices. The reason Randoop developers chose that was due to memory and performance concerns. In Randoop, all inputs are variables previously generated in the test sequence. For example, in the following test sequence, the inputs for enqueue is represented by the integer -2. Since the value of d1 is stored in the variable 2 lines above the enqueue statement.

@Test
public void test() {
RingBuffer ringBuffer1 = new RingBuffer((int)'a');
  double d1 = 0.0;
  double d2 = 1.0;
  ringBuffer1.enqueue(d1);
}

It is also worth noting that instance methods have their own instance as an input. For example, the statement x.m(f, b) has the input (x, f, b).

Dead Variables Heuristic

This section was written so that it offers an overview of the heuristic. For more formal details, please check the this section. Upon examining the redundant test cases, we notice that the majority of the code before the failing line is not involved in the cause of the bug. Specifically, the variables b2, b3, d4, b5, d6, b7, b8, b9. The intuition behind this heuristic is that variables not being used in the final failing statement are highly likely to not have an effect on the cause of failure.

@Test
public void test010() throws Throwable {
  RingBuffer ringBuffer1 = new RingBuffer((int)'a');
  ringBuffer1.enqueue(0.0d);
  boolean b2 = ringBuffer1.isFull();
  boolean b3 = ringBuffer1.isFull();
  double d4 = ringBuffer1.peek();
  boolean b5 = ringBuffer1.isFull();
  double d6 = ringBuffer1.dequeue();
  boolean b7 = ringBuffer1.isFull();
  boolean b8 = ringBuffer1.isFull();
  boolean b9 = ringBuffer1.isFull();
  ringBuffer1.enqueue((double)(short)-1);
}

Of course this is not always the cause, so this heuristic comes with assumptions. One of which is that dead variables have no effect on the objects involved in the final statement. This assumption is not true always, which makes the next heuristic more powerful.

Purity Analysis Heuristic

Looking at the previous heuristic, we notice that some statements would be considered "dead" but they modify the state of the ringBuffer. These statements are ringBuffer1.enqueue(0.0d) As debuggers, we would not want such statements to be considered dead by Randoop. However, we also want statements like boolean b5 = ringBuffer1.isFull(); to be considered dead since they do not affect the state of the RingBuffer. We can simply only consider the subset of statements with names following the format of isFull() or isEmpty(), however that incurs a lot of assumptions with regard to the reasonability of the programmer implementing those functions. If a programmer implements those functions incorrectly, this heuristic will not catch the bugs associated with those methods since it'll consider their addition redundant.

A better solution would be to run a purity analysis on the methods of the classes being instrumented. Then we can only consider the methods which are found to be pure and not used in the final statement as dead.

This heuristic will consider the addition of boolean b5 = ringBuffer1.isFull(); as redundant but not the addition of ringBuffer1.enqueue(0.0d).

Formal Explination

We define \(\Sigma\) as the set of all statements and \(\Sigma^*\) as the set of all sequences. We also define \(O\) to be the set of all operations. For example, constructor calls and method calls are \(\in O\). An operation \(o \in O\) is a function of type \(\underbrace{V \times \dots \times V}_{m} \rightarrow V\), where \(V\) as the set of all variables. Since we are dealing with Java, variables can be thought of as objects. We define a sequence \(S = (s_1, s_2, \dots, s_n)\) where \(s_i \in \Sigma \) for \(1 \leq i \leq n\) and \(s_n\) is the final failing statement. We define a statement \(s = (o, (s_i, \dots, s_m))\) to be a tuple where \(o \in O\) and \(s_1, \dots, s_m\) are statements.

We can think of statements as inputs since a variable is created by applying the operation function to the list of inputs. For statements with primitive values as inputs, we consider the primitive value as a statement with an operation and no inputs. For example, ArrayList<> list = new ArrayList<>(0) to be a statement of the following form \((constructor, (\mathbf{(int_0, ())}))\). Since Randoop uses a set of seed values, we represent those as operations with no inputs of the form \({int_0, int_{-1}, double_0, double_{-1}, \dots}\).

Dead Variables Heuristic

For a given sequence \(S = (s_1, \dots, s_n)\), we define a function $$isDead_{s_n} : \Sigma \rightarrow \{true, false\}$$ This function operates in the context where \(s_n = (o, (s_1, \dots, s_m))\) $$isDead_{s_n}(s_i) = \begin{cases} false & i = n \\ false & \exists s_j \in (s_1, \dots, s_m), \ s_j = s_i \lor isDead_{s_j}(s_i) = false \\ true & \text{otherwise} \end{cases} $$ The first case is when the input is the function itself, which should return false since the statement is alive. The second case is when at least one of the inputs to the final statement is the sequence \(s_i\) or if the statement \(s_i\) is not dead with regards to one of the input statements of the final one.

We then define a function $$clean : \Sigma^* \rightarrow \Sigma^*$$ This function takes in a sequence and returns a cleaned statement with all the dead statements removed.

We define two sequences \(S_i\) and \(S_j\) to be redundant if and only if \(S_i = clean(S_j) \land clean(S_i) = S_j\)

Purity Analysis Heuristics

For a given operation \(o \in O\), we define a function $$isPure : O \rightarrow \{true, false\}$$ $$isPure(o) = \begin{cases} false & \text{operation \(o\) has some effect on the state} \\ true & \text{operation \(o\) has no effect on the state} \end{cases}$$

We then define a function $$clean : \Sigma^* \rightarrow \Sigma^*$$ This function takes in a sequence and returns a cleaned statement where for a given statement \(s_i = (o, (s_1, \dots, s_m))\) that was in the input sequence, it is preserved in the output sequence if and only if \(isPure(o) = true \land isDead(s_i) = false\)

We define two sequences \(S_i\) and \(S_j\) to be redundant if and only if \(S_i = clean(S_j) \land clean(S_i) = S_j\)