In this page we describe the experiments performed to improve bug finding using the learned invariants. We used a scheduler implementation took from the SIR repository, an implementation of n-ary trees that is part of the ANTLR parser generator, a red black tree implementation from KodKod, binary search trees and binomial heaps used in the empirical evaluation in [Galeotti et. al (2010)] containing one real bug each, and a fibonacci heap implementation taken from the GraphMaker library, containing a real bug.

Before running each case, we assume that you are positioned in the root folder dsclassifier.

Case1 - Scheduler

Invariant generation

1. Go to the datastructures folder

2. Run the following script:

./experiments/bugfinding/gen-invariant-schedule.sh

This will generate the positive and negative instances in the file sched-instances.data in the folder bugfinding/schedule/invariant/. These will then be used to train a neural network, that i'll be stored in the file mlpclassifier.joblib.pkl in the same folder. You may also skip this step and go directly to bug finding (we already provide a generated neural net in the folder bugfinding/schedule/invariant/).

Performing bug finding with Randoop

1. Go to the datastructures folder

2. Run the two following commands:

python flask-server-classifier.py bugfinding/schedule/invariant/mlpclassifier.joblib.pkl 

./experiments/bugfinding/findbugs-randoop-schedule-orig.sh 

The first script will just run a flask server in order the provide an endpoint to call the classifier. The second script will perform bug finding by calling the that classifier. You can also run the scripts findbugs-randoop-schedule-v1.sh (or v2,v3,..,v8) to perform bug finding on the buggy versions (Notice that as we reported in the paper, this will not find bugs that break the invariant, it will only find some null pointers exceptions). Running the script findbugs-randoop-schedule-orig.sh you should be able to obtain tests that reveal the bug in the upgradeProcessPrio routine. To fix the bug and check that after that the tests pass, you should change the line proc.setPriority((short)prio); by the line proc.setPriority((short)prio+1); in the class datastructures/src/main/java/bugfinding/schedule/upgrade/Schedule.java

The generated tests will be stored in the folder datastructures/src/test/java/bugfinding/schedule/upgrade/

Case2 - ANTLR CommonTree

Invariant generation

1. Go to the datastructures folder

2. Run the following script:

   ./experiments/bugfinding/gen-invariant-antlr-commontree.sh

This script will generate the positive and negative instances in the file commontree-instances.data in the folder bugfinding/antlrcommontree/invariant/. Then it will train the neural network and store it in the file mlpclassifier.joblib.pkl in the same folder. Again, you can skip this step and go directly to bug finding (we already provide a generated network in the folder bugfinding/antlrcommontree/invariant/).

Performing bug finding with Randoop

1. Go to the datastructures folder

2. Run the two following commands:

 python flask-server-classifier.py bugfinding/antlrcommontree/invariant/mlpclassifier.joblib.pkl

./experiments/bugfinding/findbugs-randoop-antlr-commontree.sh

NOTE: After running the second script you will probably get some tests in which the invariant fails. If you check the tests, you will see that these are spurious, because the invariant is checked from an object which is not the root of the tree (this is a problem implied by the class design in this case study). The generated tests will be stored in the folder datastructures/src/test/java/bugfinding/antlr/orig. As we mention in the paper, randoop is not able to generate the test in which the error is reproduced. To reproduce the error you can run the following manual test: datastructures/src/test/java/bugfinding/antlr/orig/ManualTest.java

To fix the bug you can uncomment the code in the routine addChild in the class datastructures/src/main/java/bugfinding/antlr/orig/BaseTree.java

Case3 - KodKod IntTreeSet

Invariant generation

1. Go to the datastructures folder

2. Run the following script:

./experiments/bugfinding/gen-invariant-kodkod-inttreeset.sh

This script will generate the positive and negative instances in the file inttreeset-instances.data in the folder bugfinding/kodkodinttreeset/invariant/. Then the neural network will be trained and stored in the file mlpclassifier.joblib.pkl in the same folder. Again, you can directly perform bug finding (we already provided a generated network in the folder bugfinding/kodkodinttreeset/invariant/).

Performing bug finding with Randoop

1. Go to the datastructures folder

2. Run the two following commands:

python flask-server-classifier.py bugfinding/kodkodinttreeset/invariant/mlpclassifier.joblib.pkl

./experiments/bugfinding/findbugs-randoop-inttreeset-err1.sh

The scripts that you can run with the buggy versions of the insert routine are the following:

findbugs-randoop-inttreeset-err1.sh -> Creates a cycle of length one

findbugs-randoop-inttreeset-err2.sh -> Sets the color of a node to Black instead of Red

findbugs-randoop-inttreeset-err3.sh -> Adds the new element as right child instead of left

findbugs-randoop-inttreeset-err4.sh -> Violates key contraints due to a branch condition error

findbugs-randoop-inttreeset-err5.sh -> Skip balancing of the tree after insertion

For each script you will be able to find tests for which the invariant fails due to the bug. The generated tests will be stored in the folder datastructures/src/test/java/bugfinding/inttreeset/err*. The bugs are all inserted in the insert routine in the class datastructures/src/main/java/bugfinding/inttreeset/err*/IntTree.java

Case4 - Binary Search Tree

Invariant generation

1. Go to the datastructures folder

2. Run the following script

./experiments/bugfinding/gen-invariant-bstree.sh        

This script will generate the positive and negative instances in the file bstree-instances.data in the folder bugfinding/bstree/invariant/. Then the neural network will be trained and stored in the file mlpclassifier.joblib.pkl in the same folder. Again, you can directly perform bug finding.

Performing bug finding with Randoop

1. Go to the datastructures folder

2. Run the two following commands

python flask-server-classifier.py bugfinding/bstree/invariant/mlpclassifier.joblib.pkl

./experiments/bugfinding/findbugs-randoop-bstree.sh

The generated tests will be stored in the folder datastructures/src/test/java/bugfinding/bstree/buggy. The bugs is in the remove routine in the class datastructures/src/main/java/bugfinding/bstree/buggy/BinTree.java

Case5 - Binomial Heap

Invariant generation

1. Go to the datastructures folder

2. Run the following script

./experiments/bugfinding/gen-invariant-binheap.sh        

This script will generate the positive and negative instances in the file binheap-instances.data in the folder bugfinding/binheap/invariant/. Then the neural network will be trained and stored in the file mlpclassifier.joblib.pkl in the same folder. Again, you can directly perform bug finding (NOTE: we recommend to directly perform bug finding in this particular case, since the neural is generated for the structure Binomial Heap with at most 13 nodes, which takes a long time to be generated).

Performing bug finding with Randoop

1. Go to the datastructures folder

2. Run the following two commands

python flask-server-classifier.py bugfinding/binheap/invariant/mlpclassifier.joblib.pkl

./experiments/bugfinding/findbugs-randoop-binheap.sh

The generated tests will be stored in the folder datastructures/src/test/java/bugfinding/binheap/buggy. The bugs is in the extractMin routine in the class datastructures/src/main/java/bugfinding/binheap/buggy/BinomialHeap.java . If randoop is not able to generate a failing test, you can run the test in the file datastructures/src/test/java/bugfinding/binheap/buggy/ManualTest.java

Case6 - Fibonacci Heap

Invariant generation

1. Go to the datastructures folder

2. Run the following script

./experiments/bugfinding/gen-invariant-fibheap.sh

This script will generate the positive and negative instances in the file fibheap-instances.data in the folder bugfinding/fibheap/invariant/. Then the neural network will be trained and stored in the file mlpclassifier.joblib.pkl in the same folder. Again, you can directly perform bug finding.

Performing bug finding with Randoop

1. Go to the datastructures folder

2. Run the two following commands

python flask-server-classifier.py bugfinding/fibheap/invariant/mlpclassifier.joblib.pkl

./experiments/bugfinding/findbugs-randoop-fibheap.sh

The generated tests will be stored in the folder datastructures/src/test/java/bugfinding/fibheap/buggy. The bugs is in the removeMin routine in the class datastructures/src/main/java/bugfinding/fibheap/buggy/FibonacciHeap.java. If randoop is not able to generate a failing test, you can run the test in the file datastructures/src/test/java/bugfinding/fibheap/buggy/ManualTest.java