In this page we compare the results of performing bug finding with our approach (described here) , against the results obtained in the same task using Daikon and the same case studies, namely the scheduler implementation from the SIR repository, the implementation of n-ary trees that is part of the ANTLR parse generator, the red black tree implementation from KodKod, binary search trees and binomial heaps from [Galeotti et. al (2010)], and the fibonacci heap implementation taken from the GraphMaker library. For this experiment, in all the cases we generated the invariant using Daikon and the same tests used to create the valid structures in our approach.

In the following table are expressed the general results and below you can find the details of each case:

* The scenario in which the bug is reproduced was provided manually.

As you can see, the Daikon generated invariant commonly is not able to find bugs. But, as we explain below, if we take the trouble of manually change the generated invariant by keeping just the valid discovered properties, we can increase the accuracy of the invariant when trying to find bugs. In contrast, our approach can achieve very good precision when finding bugs with no manual inspection required.

Case1 - Scheduler

In this page is shown the invariant generated by Daikon as well as the refined invariant (i.e., an improvement of the generated invariant by removing the invalid and the redundant parts).

In this case, we used the generated invariant against some buggy versions of the Scheduler. Three of them are bugs in which the code fails due to a null pointer exception, and thus can be detected even without using invariants. An interesting bug that we were able to find is one present in the upgradeProcessPrio routine (which can be fixed by changing the line

proc.setPriority((short)prio); by the line proc.setPriority((short)prio+1));)

When using the Daikon generated invariant all the tests generated with Randoop will fail due to the inconsistency of the invariant. If we manually refine the invariant, the generated tests will fail in the buggy versions which bugs are the null pointer exception, and also the bug in the upgradeProcessPrio routine can be detected.

Case2 - ANTLR CommonTree

In this page you can find the invariant generated by Daikon as well as the refined invariant.

The bug present in this code allows to add a node as a child of itself. As we show in the page Improving bug finding, if we

manually create the buggy scenario (remember that randoop is not able to generate this scenario), our generated neural network is able to detect the bug.

Regarding Daikon, the generated invariant fails due to the invalid inferred property this.startIndex == this.childIndex (which is not true in CommonTree's with child nodes). However, if we refine the generated invariant by manually filtering the properties that are part of the class invariant we get only the property this.parent == null. With only this property the bug can be detected when the root structure is a child of itself (i.e., the parent of the root node is the root node). But if the cycle is present in a deeper node of the tree, that Daikon refined invariant will not be able to detect the bug, while our generated neural network is still able to detect it.

To reproduce this, please see the tests in datastructures/src/test/java/bugfinding/antlr/orig/ManualTest.java

Case3 - KodKod IntTreeSet

In this page you will see the invariant generated by Daikon.

For this case we introduced 5 different bugs in the insertion routine and then we tried to find them using the

inferred invariants:

As you can see, our trained neural network is able to detect all the invalid IntTreeSet instances produced by these bugs.

Regarding the Daikon invariant is important to note that, although it is able to find 3 out of 5 bugs, it depends in which order the properties generated by Daikon were checked. This is because Daikon sometimes generates some invalid properties, for instance, the property this.root.left.left == this.root.right.left which is not valid.

By manually refining the Daikon invariant, we can effectively find 3 out of 5 bugs.

Case4 - Binary Search Tree

In this page you can see the invariant generated by Daikon.

In this case the bug is in the remove routine of the class

datastructures/src/main/java/bugfinding/bstree/buggy/BinTree.java

Again, if we manually refine the invariant generated by Daikon, we can detect the bug.

Case5 - Binomial Heap

The invariant generated by Daikon can be found in this page.

For the class datastructures/src/main/java/bugfinding/binheap/buggy/BinomialHeap.java the bug was in the method extractMin. For this particular bug, neither the generated invariant nor the manually refined invariant were able to catch the bug.

Case6 - Fibonacci Heap

In this page you can see the invariant generated by Daikon.

In this case the bug is in the removeMin routine of the class

datastructures/src/main/java/bugfinding/fibheap/buggy/FibonacciHeap.java

Again, if we manually refine the invariant generated by Daikon, we can detect the bug.