Automatic repair experiment on QuixBugs.

Experimental data about the effectiveness of two representative automatic repair tools Astor and Nopol on repairing QuixBugs benchmark. QuixBugs is a benchmark suite of 40 confirmed bugs from classic algorithms with a bug on a single line of code. The paper is A Comprehensive Study of Automatic Program Repair on the QuixBugs Benchmark.

@article{YE2021110825,
title = "A comprehensive study of automatic program repair on the QuixBugs benchmark",
author = "He Ye and Matias Martinez and Thomas Durieux and Martin Monperrus",
journal = "Journal of Systems and Software",
volume = "171",
pages = "110825",
year = "2021",
issn = "0164-1212",
doi = "https://doi.org/10.1016/j.jss.2020.110825",
url = "http://www.sciencedirect.com/science/article/pii/S0164121220302193"
}

Folder Structure

Buggy Java Programs are 40 buggy programs from QuixBugs and Corresponding Junit Tests
Reference Programs are the ground truth version based on the provided correct Python version from QuixBugs.
Patches contains all patches generated by Astor, Nopol, Arja, RSRepair and NPEFix.
Generated Tests are the independent tests generated based ground truth programs.
Assessment Report are the assessment reports of each patch when running different number tests.
Daikon contains all the patch assessment by invariants on DaiKon.
Repair Execution Row Data contains all the patch generation raw data.

Getting started

Check out the project:

git clone https://github.com/KTH/quixbugs-experiment.git
cd quixbugs-experiment
mvn clean install -DskipTests

Patch correctness assessment:

First, please set root patch as your customized path of the project in the script run.py.

To assess the plausibility of patches, i.e., the generated patches make all original human-written tests pass: A csv file called Plausible_check.csv will be generated in the root directory of this project.

./run.py Plausible_check

To assess patches ,for example, by using 30 seeds Evosuite tests: A csv file called Evosuite_check.csv will be generated in the root directory of this project.

./run.py Evosuite_check

To assess patches ,for example, by using 300 InputSampling tests: A csv file called InputSample_check.csv will be generated in the root directory of this project.

./run.py InputSample_check

Test Coverage Report

QuixBugs_original_tests
Evosuite
InputSampling
EvosuiteAndInputSampling

Reference Patches

BITCOUNT

@@ -12,7 +13,7 @@
     public static int bitcount(int n) {
     int count = 0;
     while (n != 0) {
-        n = (n ^ (n - 1));
+        n = (n & (n - 1));
         count++;
     }
     return count;

BREADTH_FIRST_SEARCH

@@ -21,7 +21,7 @@
 
         nodesvisited.add(startnode);
 
-        while (true) {
+        while (!queue.isEmpty()) {
             Node node = queue.removeFirst();
 
             if (node == goalnode) {
@@ -39,7 +39,7 @@
          * The buggy program always drops into while(true) loop and will not return false
          * Removed below line to fix compilation error
          */
-        // return false;
+         return false;
     }
 
 }

BUCKETSORT

@@ -19,7 +19,7 @@
 
         ArrayList<Integer> sorted_arr = new ArrayList<Integer>(100);
 	int i = 0;
-        for (Integer count : arr) { // arr is counts in fixed version
+        for (Integer count : counts) { 
 	    sorted_arr.addAll(Collections.nCopies(count, i));
 	    i++;
         }

DEPTH_FIRST_SEARCH

@@ -19,6 +21,7 @@
                 } else if (node == goalnode) {
                     return true;
                 } else {
+                  	nodesvisited.add(node);
                     for (Node successornodes : node.getSuccessors()) {
 	                    if (search(successornodes)) { return true; }
                     }

DETECT_CYCLE

@@ -15,7 +17,7 @@
         Node tortoise = node;
 
         while (true) {
-            if (hare.getSuccessor() == null)
+            if (null==hare ||hare.getSuccessor() == null)
                 return false;
 
             tortoise = tortoise.getSuccessor();

FIND_FIRST_IN_SORTED

@@ -16,7 +16,7 @@
         int lo = 0;
         int hi = arr.length;
 
-        while (lo <= hi) {
+        while (lo < hi) {
             int mid = (lo + hi) / 2; // check if this is floor division
 
             if (x == arr[mid] && (mid == 0 || x != arr[mid-1])) {

FIND_IN_SORTED

@@ -17,7 +18,7 @@
         if (x < arr[mid]) {
             return binsearch(arr, x, start, mid);
         } else if (x > arr[mid]) {
-            return binsearch(arr, x, mid, end);
+            return binsearch(arr, x, mid+1, end);
         } else {
             return mid;
         }

FLATTEN

@@ -18,12 +19,12 @@
                 if (x instanceof ArrayList) {
                     result.addAll((ArrayList) flatten(x));
                 } else {
-                    result.add(flatten(x));
+                    result.add((x));
 		}
             }
             return result;
 	} else {
-	    return flatten(arr);
+	    return arr;
 	}
     }
 }

GCD

@@ -16,7 +16,7 @@
         if (b == 0) {
             return a;
         } else {
-            return gcd(a % b, b);
+            return gcd(b, a%b);
         }
     }
 }

GET_FACTORS

@@ -24,6 +24,6 @@
                 return prepend;
             }
         }
-        return new ArrayList<Integer>();        
+        return new ArrayList<Integer>(Arrays.asList(n));
     }
 }

HANOI

@@ -24,7 +24,7 @@
             crap_set.remove(end);
             int helper = crap_set.poll();
             steps.addAll(hanoi(height-1, start, helper));
-            steps.add(new Pair<Integer,Integer>(start, helper));
+            steps.add(new Pair<Integer,Integer>(start, end));
             steps.addAll(hanoi(height-1, helper, end));
         }

IS_VALID_PARENTHESIZATION

@@ -21,6 +22,6 @@
 		if (depth < 0) { return false; }
 	    }
 	}
-	return true;
+	return depth==0;
     }
 }

KHEAPSORT

@@ -24,7 +25,7 @@
         }
 
         ArrayList<Integer> output = new ArrayList<Integer>();
-        for (Integer x : arr) {
+        for (Integer x : arr.subList(k, arr.size())) {
             heap.add(x);
             Integer popped = heap.poll();
             output.add(popped);

KNAPSACK

@@ -27,7 +28,7 @@
                 if (i == 0 || j == 0) {
                     memo[i][j] = 0;
                 }
-                else if (weight < j) {
+                else if (weight <= j) {
                     memo[i][j] = Math.max(memo[i - 1][j], value + memo[i - 1][j - weight]);
                 }
                 else {

KTH

@@ -22,7 +29,7 @@
         if (k < num_less) {
             return kth(below, k);
         } else if (k >= num_lessoreq) {
-            return kth(above, k);
+            return kth(above, k-num_lessoreq);
         } else {
             return pivot;
         }

LCS_LENGTH

@@ -32,9 +32,10 @@
             for (int j=0; j < t.length(); j++) {
                 if (s.charAt(i) == t.charAt(j)) {
 
-                    if (dp.containsKey(i-1)) {)
+                    if (dp.containsKey(i-1)&&dp.get(i-1).containsKey(j-1)) {
                         Map<Integer, Integer> internal_map = dp.get(i);
-                        int insert_value = dp.get(i-1).get(j) + 1;
+                        int insert_value = dp.get(i-1).get(j-1) + 1;
                         internal_map.put(j, insert_value);
                         dp.put(i,internal_map);
                     } else {

LEVENSHTEIN

@@ -14,7 +14,7 @@
         if (source.isEmpty() || target.isEmpty()) {
             return source.isEmpty() ? target.length() : source.length();
         } else if (source.charAt(0) == target.charAt(0)) {
-            return 1 + levenshtein(source.substring(1), target.substring(1));
+            return levenshtein(source.substring(1), target.substring(1));
         } else {
             return 1 + Math.min(Math.min(
                     levenshtein(source,              target.substring(1)),

LIS

@@ -28,7 +28,7 @@
 
             if (length == longest || val < arr[ends.get(length+1)]) {
                 ends.put(length+1, i);
-                longest = length + 1;
+                longest = Math.max(longest,length + 1);
             }
 
             i++;

LONGEST_COMMON_SUBSEQUENCE

@@ -15,7 +15,7 @@
         if (a.isEmpty() || b.isEmpty()) {
             return "";
         } else if (a.charAt(0) == b.charAt(0)) {
-            return a.charAt(0) + longest_common_subsequence(a.substring(1), b);
+            return a.charAt(0) + longest_common_subsequence(a.substring(1), b.substring(1));
         } else {
             String fst = longest_common_subsequence(a, b.substring(1));
             String snd = longest_common_subsequence(a.substring(1), b);

MAX_SUBLIST_SUM

@@ -16,7 +16,7 @@
         int max_so_far = 0;
 
         for (int x : arr) {
-            max_ending_here = max_ending_here + x;
+            max_ending_here = Math.max(0,max_ending_here + x);
             max_so_far = Math.max(max_so_far, max_ending_here);
         }

MERGESORT

@@ -35,7 +35,7 @@
     }
 
     public static ArrayList<Integer> mergesort(ArrayList<Integer> arr) {
-        if (arr.size() == 0) { // <= 1 in correct version
+        if (arr.size() <= 1) { // <= 1 in correct version
             return arr;
         } else {
             int middle = arr.size() / 2;

NEXT_PALINDROME

@@ -32,7 +32,7 @@
 
         ArrayList<Integer> otherwise = new ArrayList<Integer>();
 	otherwise.add(1);
-	otherwise.addAll(Collections.nCopies(digit_list.length, 0));
+	otherwise.addAll(Collections.nCopies(digit_list.length-1, 0));
 	otherwise.add(1);
 
         return String.valueOf(otherwise);

NEXT_PERMUTATION

@@ -16,7 +16,7 @@
         for (int i=perm.size()-2; i!=-1; i--) {
             if (perm.get(i) < perm.get(i+1)) {
                 for (int j=perm.size()-1; j!=i; j--) {
-                    if (perm.get(j) < perm.get(i)) {
+                    if (perm.get(j) > perm.get(i)) {
                         ArrayList<Integer> next_perm = perm;
                         int temp_j = perm.get(j);
                         int temp_i = perm.get(i);

PASCAL

@@ -19,7 +19,7 @@
 
         for (int r=1; r<n; r++) {
             ArrayList<Integer> row = new ArrayList<Integer>();
-            for (int c=0; c<r; c++) {
+            for (int c=0; c<r+1; c++) {
                 int upleft, upright;
                 if (c > 0) {
                     upleft = rows.get(r-1).get(c-1);

POSSIBLE_CHANGE

@@ -14,7 +14,7 @@
         if (total == 0) {
             return 1;
         }
-        if (total < 0) {
+        if (total < 0 ||coins.length==0) {
             return 0;
         }

POWERSET

@@ -20,13 +20,17 @@
 
             ArrayList<ArrayList> output = new ArrayList<ArrayList>(100);
             ArrayList to_add = new ArrayList(100);
-            to_add.add(first);
+
             for (ArrayList subset : rest_subsets) {
-                to_add.addAll(subset);
+            		ArrayList r = new ArrayList();
+				r.add(first);
+				r.addAll(subset);
+				to_add.add(r);
             }
-            output.add(to_add);
+            output.addAll(to_add);
+            rest_subsets.addAll(output);
 
-            return output;
+            return rest_subsets;
         } else {
             ArrayList empty_set = new ArrayList<ArrayList>();
             empty_set.add(new ArrayList());

QUICKSORT

@@ -23,7 +23,7 @@
         for (Integer x : arr.subList(1, arr.size())) {
             if (x < pivot) {
                 lesser.add(x);
-            } else if (x > pivot) {
+            } else if (x >= pivot) {
                 greater.add(x);
             }
         }

REVERSE_LINKED_LIST

@@ -17,6 +19,7 @@
         while (node != null) {
             nextnode = node.getSuccessor();
             node.setSuccessor(prevnode);
+            prevnode = node;
             node = nextnode;
         }
         return prevnode;

RPN_EVAL

@@ -31,7 +31,7 @@
                 Double b = (Double) stack.pop();
 		Double c = 0.0;
 		BinaryOperator<Double> bin_op = op.get(token);
-		c = bin_op.apply(a,b);
+		c = bin_op.apply(b,a);
                 stack.push(c);
             }
         }

SHORTEST_PATH_LENGTH

@@ -35,14 +37,14 @@
                 }
 
                 unvisitedNodes.put(nextnode, Math.min(unvisitedNodes.get(nextnode),
-                        unvisitedNodes.get(nextnode) + length_by_edge.get(Arrays.asList(node, nextnode))));
+                        distance + length_by_edge.get(Arrays.asList(node, nextnode))));
             }
         }
 
         return Integer.MAX_VALUE;
     }

SHORTEST_PATH_LENGTHS

@@ -33,7 +33,7 @@
             for (int i = 0; i < numNodes; i++) {
                 for (int j = 0; j < numNodes; j++) {
                     int update_length = Math.min(length_by_path.get(Arrays.asList(i,j)),
-                            length_by_path.get(Arrays.asList(i,k)) + length_by_path.get(Arrays.asList(j,k)));
+                            length_by_path.get(Arrays.asList(i,k)) + length_by_path.get(Arrays.asList(k,j)));
                     length_by_path.put(Arrays.asList(i,j), update_length);
                 }
             }

SHORTEST_PATHS

@@ -27,37 +31,11 @@
                         weight_by_node.get(edge.get(0))
                                 + weight_by_edge.get(edge),
                         weight_by_node.get(edge.get(1)));
-                weight_by_edge.put(edge, update_weight);            
+                weight_by_node.put(edge.get(1), update_weight);
             }
         }
         return weight_by_node;
     }

SIEVE

@@ -38,7 +38,7 @@
     public static ArrayList<Integer> sieve(Integer max) {
         ArrayList<Integer> primes = new ArrayList<Integer>();
         for (int n=2; n<max+1; n++) {
-            if (any(list_comp(n, primes))) {
+            if (all(list_comp(n, primes))) {
                 primes.add(n);
             }
         }

SQRT

@@ -13,7 +13,7 @@
 public class SQRT {
     public static double sqrt(double x, double epsilon) {
         double approx = x / 2d;
-        while (Math.abs(x-approx) > epsilon) {
+        while (Math.abs(x-approx*approx) > epsilon) {
             approx = 0.5d * (approx + x / approx);
         }
         return approx;

SUBSEQUENCES

@@ -13,7 +13,9 @@
 public class SUBSEQUENCES {
     public static ArrayList<ArrayList> subsequences(int a, int b, int k) {
         if (k == 0) {
-            return new ArrayList();
+        	 ArrayList empty_set = new ArrayList<ArrayList>();
+         empty_set.add(new ArrayList());
+         return empty_set;
         }
 
         ArrayList ret = new ArrayList(50);

TO_BASE

@@ -18,7 +18,7 @@
         while (num > 0) {
             i = num % b;
             num = num / b; // floor division?
-            result = result + String.valueOf(alphabet.charAt(i));
+            result = String.valueOf(alphabet.charAt(i))+result;
         }
 
         return result;

TOPOLOGICAL_ORDERING

@@ -14,7 +16,7 @@
         for (int i = 0; i < listSize; i++) {
             Node node = orderedNodes.get(i);
             for (Node nextNode : node.getSuccessors()) {
-                if (orderedNodes.containsAll(nextNode.getSuccessors()) && !orderedNodes.contains(nextNode)) {
+                if (orderedNodes.containsAll(nextNode.getPredecessors()) && !orderedNodes.contains(nextNode)) {
                     orderedNodes.add(nextNode);
                     listSize++;
                 }

WRAP

@@ -28,7 +28,7 @@
             text = text.substring(end);
             lines.add(line);
         }
-
+        lines.add(text);
         return lines;
     }
 }

Patch Assessments

We give assessment reusults for all 338 patches in the Assessments.md. Our manual assessment considers all patches generated for LIS and Quicksort are correct. We also share our manual tests of LIS to confirm LIS patches correctness and the explaination of Quicksort patches in here.

Our manual assessment consider 4 DETECT_CYCLE patches are overfitting because of the new introduced null pointer exception according to the below updates reported by @ngocpq.

Updates

detect_cycle_NPEFix_3 is an incorrect patch which was assessed as correct. This patch introduces a new null pointer exception. Thanks for the report at issue #11 by @ngocpq. Updated on August 26, 2019.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

README.md

README.md

Automatic repair experiment on QuixBugs.

Folder Structure

Getting started

Check out the project:

Patch correctness assessment:

Test Coverage Report

Reference Patches

Patch Assessments

Updates

Files

README.md

Latest commit

History

README.md

File metadata and controls

Automatic repair experiment on QuixBugs.

Folder Structure

Getting started

Check out the project:

Patch correctness assessment:

Test Coverage Report

Reference Patches

Patch Assessments

Updates