Program Repair via Direct State Manipulation
Qinheping Hu1 , Isaac Evavold1 , Roopsha Samanta2 ,
Rishabh Singh3 , Loris D’Antoni1

arXiv:1803.07522v1 [] 20 Mar 2018

1

University of Wisconsin-Madison
2
Purdue University
3
Microsoft
Abstract. The goal of program repair is to automatically fix programs
to meet a specification. We propose a new specification mechanism, direct manipulation, in which the programmer can visualize the trace of
a buggy program on a failing input and convey the intended program
behaviour by manipulating variable values at some location. The repair
problem is to find a program that, on the same input, reaches the location identified by the programmer with variable values equal to the
manipulated ones. Since a single program execution under-specifies the
overall program behavior, we augment our repair problem with quantitative objectives to find the program that agrees with the specification and
is closest to the original one with respect to some distance. We formalize the repair problem, build a program repair tool JDial based on the
Sketch synthesizer, and show the effectiveness of JDial on representative buggy benchmarks from introductory programming assignments.

1

Introduction

The goal of program repair [19] is to automatically fix buggy programs to meet
a specification that is typically provided in the form of assertions or a set of test
cases. In this paper, we propose a new complementary specification mechanism
called direct manipulation, in which users can specify the intended program behavior by directly manipulating intermediate variable values in buggy program
traces. We propose a workflow in which the user traverses the step-by-step visualization of the execution of the buggy program on a certain input to identify a
location where the values of the program variables do not correspond to the ones
she expects. At this point, we allow the user to manipulate the variable values
at the identified location and modify them. We then treat this manipulation as
a specification and use it to find a program that, on the same input, can reach
the location identified by the user with the new variable values she provided.
We formalize our repair problem and present a constraint-based synthesis
technique for computing program repairs based on direct manipulations. To repair programs in this setting we need to address two key challenges. First, the
execution step manipulated by the user in the buggy trace might appear at a
completely different point in the trace of the repaired program—e.g., when the
repaired program uses a different number of loop iterations from the original
program. Second, since a single program execution under-specifies the overall
program behavior, there can be many possible repaired programs that agree
with the manipulated trace. To address the first challenge, given a manipulated

2

location `, we design an encoding that “guesses” in what occurrence of the location ` in the trace of the repaired program the desired variable values are
produced. To address the second challenge, we augment our repair problem with
quantitative objectives [5] to prefer repairs that produce execution traces similar
to those of the original program.
We implemented our synthesis technique in a tool called JDial, which is built
on top of the Sketch [28] synthesizer. JDial supports several repair models
and program distances, and can repair Java programs containing loops, arrays,
and recursion. We also introduce an algorithm that uses concrete executions
to “discover” interpretations of external functions and allows JDial to repair
programs containing library functions such as Math.pow. Additinally, JDial also
allows users to specify input-output test cases in addition to direct manipulations
and is therefore compatible with repair tools like Qlose [5].
We evaluated JDial on representative benchmarks obtained from Qlose [5]
and several new benchmarks. Our evaluation shows that JDial can quickly repair small Java programs and it produces more accurate repairs than techniques
based only on test cases. In particular, even when provided with a single input
trace, JDial is able to compute correct repairs for 66% of the programs while
techniques based on only test cases always fail.
Contributions. We make the following key contributions.
– We introduce a specification mechanism called direct manipulation together
with a corresponding repair problem (§ 3).
– We propose a modular framework based on sketching for repairing programs
using direct manipulations (§ 4).
– We instantiate our framework in JDial, a tool that can repair simple Java programs. JDial supports a new algorithm for repairing programs with external
functions and an optimized repair technique based on slicing (§ 5).
– We evaluate JDial on 17 representative benchmarks and show JDial computes correct repairs in cases where techniques based on test cases fail (§ 6).

2

Illustrative Example

In this section, we illustrate our approach using an example student attempt
to an introductory programming exercise. In this domain, automatic program
repair can be used to provide personalized feedback to students [26, 36, 30].
Consider the example in Fig. 1 (a) where a student is trying to write a program largestGap for finding the largest gap in a non-empty array of integers—
i.e., the difference between the maximum and minimum values in the array. In
the following, we assume that the student has discovered that the program behavior on test [9,5,4] is incorrect and is trying to get a suggestion from the
repair tool on how she could fix the program.
Repairing via test cases Several program repair tools support test cases as a way
to express the correct behaviour of the program. In this case, the student can
specify that on the input [9,5,4], the correct output should be 5. However, even

3
1 int largestGap ( int [] x ){
2 int N = x . length ;
3 int max = x [N -1];
4 int min = x [N -1];
5 for ( int i =1; i <N -1; i ++){
6
if ( max < x [ i ])
7
max = x[i];
max min
‘8
if(min > x[i]) value
5 4
9
min = x [ i ]; change to 9 ?
10 }
11 int res = max - min ;
12 return res ; }

i
1
?

Test case: largestsGap([9,5,4]) = 5

int largestGapFix ( int [] x ){
int N = x . length ;
int max = x [N -1];
int min = x [N -1];
- for ( int i =1; i <N -1; i ++){
+ for ( int i =0; i <N -1; i ++){
if ( max < x [ i ])
JDial
−−−−→
max = x [ i ];
if ( min > x [ i ])
min = x [ i ];
}
int res = max - min ;
return res ; }

a) Direct manipulation on failing test case b) Repair computed by JDial

Fig. 1: Examples of repair using direct manipulation in JDial.
the tool Qlose [5], which can often find correct repairs using a small number of
test cases, will return the following wrong modification to line 11:
int res = max - min ; −→ int res = max - min + 4;

Qlose requires two additional test cases to find the correct repair.
Repairing via direct manipulation Direct manipulations allow programmers to
convey more information about the behavior of a test case, rather than only its final output. Our technique is inspired by Guo’s observation [9] that students find
it beneficial to visualize concrete program executions and observe discrepancies
between the variable values they observe and those they expect. For example,
while debugging the largestGap program, the student notices that in the first
iteration of the loop, right before executing line 8, variable max has value 5
instead of the expected value 9. While visualizing the trace, the student can directly modify the value of max as shown in the figure and JDial will synthesize
the program largestGapFix consistent with the manipulation (Fig. 1(b))—i.e.,
when running largestGapFix with input [9,5,4], there is a point in the execution where the variable max contains value 9 right before executing line 8. Why
does this new specification mechanism lead to the desired repair? First, by modifying the program’s trace and its value at line 8, the student implicitly states
that certain lines do not need modification—e.g., lines 11 and 12. Second, the
modification provides information about an intermediate state of the program
that a tool cannot access through just an input/output example. Besides the
variable max, the student can modify the value of i from 1 to 0 or the values of
both i and max at the same position and JDial will produce the same repair.
Remarkably, direct manipulation can also help debug partial implementations. Consider, for example, an incomplete version of the program largestGap
in which lines 8–9 are missing because the student has not implemented the logic
for min yet. The test case in Fig. 1(a) is essentially useless. On the other hand,
the same direct manipulation shown in Fig. 1(a) will yield a good repair.

4

3

Problem definition

In this section, we define the class of programs we consider, the notion of direct
manipulation, and our program repair problem.
3.1

Programs and Traces

We consider a simple imperative language in which a program P consists of
a function definition f (i1 , . . . , iq ) : o with input variables I = {i1 , . . . , iq } and
output variable o (NULL for void functions), a set of program variables V such
that V ∩ I = ∅, and a sequence of labeled statements σ = s1 . . . sn . A statement
is one of the following: return, assignment, conditional or loop statement. Each
statement in σ is labeled with a unique location identifier from the set L =
{`0 , `1 , . . . , `p , exit}. We assume a universe U of values. We also assume variables
are associated with types and assignments are consistent with these types.
Without loss of generality, we assume that executing a return statement
assigns a value to the output variable and transfers control to a designated
location exit. A program configuration η is a pair (`, ν) where ` ∈ L is a location
and ν : I ∪ {o} ∪ V 7→ U ∪ {⊥} is a valuation function that assigns values to all
variables. The element ⊥ indicates that a variable has not been assigned a value
yet or is out of scope. We write (`, ν) → (`0 , ν 0 ) if executing the statement at
location ` under variable valuation ν transfers control to location `0 with variable
valuation ν 0 . The execution trace πP (ν0 ) of the program P on an initial valuation
ν0 is a sequence of configurations η0 , η1 , . . . , where η0 = (`0 , ν0 ) and for each h,
we have ηh → ηh+1 . An execution terminates once the location exit is reached
and we only consider programs that terminate on all inputs. We use πP (ν0 )l = ηl
to denote the configuration at index l and πP (ν0 )[l,h] to denote the subsequence
of configurations between index l and h—e.g., πP (ν0 )[3,5] = η3 η4 η5 .
Consider the program largestGap in Fig. 1. The input variable set I is
{x} and the designated output variable is res. The set of program variables is
{i,max,min}. Let ν0 be the initial valη0 η1 η2 η3 η4 η5 η6 η7 η8 η9 η10
uation such that ν0 (x) = {9, 5, 4} and
loc 2 3 4 5 6 7 8 5 10 11 exit
ν0 (w) = ⊥ for every other variable w.
N ⊥ 3 3 3 3 3 3 3 3 3 3
The execution of largestGap on ν0
i ⊥ ⊥ ⊥ ⊥ 1 1 1 1 ⊥ ⊥ ⊥
max ⊥ ⊥ 4 4 4 4 5 5 5 5 5
is illustrated on the right (we do not
min ⊥ ⊥ ⊥ 4 4 4 4 4 4 4 4
show valuations of the input variable
res ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ 1
x as νh (x) = ν0 (x) for all h).
3.2

Repair via Direct Manipulation

We first define the notion of direct manipulation, which allows users to express
their intent by modifying variable values in intermediate configurations. We assume a fixed program P . A direct manipulation M is a tuple (ν0 , k, ν 0 ) where ν0
is an initial valuation, k is an index s.t. k ≤ |πP (ν0 )|, and ν 0 : V ∪ {o} 7→ U ∪ {?}
is a new partial variable valuation. Intuitively, the manipulation replaces the

5

configuration πP (ν0 )k = (`, ν) at location ` with the the new partial configuration (`, ν 0 ). Notice that a partial configuration cannot change the values of
the input variables in I and it can assign a special value ? to certain variables.
This value is used to denote that the manipulation “does not care” about the
specific values of certain variables. We say that a valuation ν satisfies a partial
valuation ν 0 , denoted ν ` ν 0 , iff for every variable x ∈ V ∪ {o}, if ν(x) 6= ? then
ν(x) = ν 0 (x).
Example 1. The direct manipulation in Fig. 1(a) is formally defined as the pair
(ν0 , 6, ν 0 ) where ν0 is the same as at the end of Section 3.1, ν 0 (max) = 9 and
ν 0 (i) = ν 0 (min) = ν 0 (o) = ?. This manipulation, which modifies η6 , only sets
the value of max to 9 at location 8 and leaves all other variables unconstrained.
Given a program P , a direct manipulation M = (ν0 , k, ν 0 ) such that πP (ν0 )k =
(`, ν), we say that a program P 0 satisfies the manipulation M, if there exists
some index j such that πP 0 (ν0 )j = (`, νj ) and νj ` ν 0 . In other words, a program P 0 satisfies a direct manipulation if there exists some configuration in the
execution trace of P 0 satisfying the manipulated valuation ν 0 at location `.
The goal of our repair problem is to find a program that satisfies a given
manipulation. In what follows, we fix a repair model, which is a function RM that
assigns to a program a corresponding repair space P. The repair space represents
a set of programs from which we can draw candidate repaired programs.
Definition 1 (Repair via Direct Manipulation). Given a program P and a
direct manipulation M = (ν0 , k, ν 0 ), the program repair via direct manipulation
problem is to find a program P 0 ∈ RM(P ) that satisfies the manipulation M.
Informally, a direct manipulation (ν0 , k, ν 0 ) at location ` is a reachability
specification requiring that a configuration (`, ν 0 ) is eventually reached along an
execution from the initial valuation ν0 . This specification mechanism is orthogonal to that provided by assertions, which require a property ϕ at location ` to
be an invariant specification—i.e., each time an execution reaches location `, the
property ϕ should hold. For instance, in Figure 1 (a), placing the assertion max
= 9 at location 8 would specify that the value of max should be 9 at location 8
across all loop iterations in an execution. The astute reader may suggest that for
some suitably chosen predicate condition over the loop counter, an assertion of
the form condition ⇒ (max = 9) at location 8 could encode the direct manipulation in Figure 1. However, a direct manipulation does not explicitly indicate
what such a predicate condition should be. In particular, a direct manipulation
does not specify what the manipulation-satisfying index j should be.
Handling test cases Definition 1 can be generalized to the problem of repairing
a program P given a direct manipulation and a set of tests. A test t is a pair
(ν I , ν O ), where ν I is a valuation over the input variables I and ν O is a valuation
over the output variable o . Let ν0I denote an initial valuation such that ν0I (w) =
ν I (w) if w ∈ I and ⊥ otherwise. Program P satisfies a test t if the value of the
output variable o at the end of an execution πP (ν0I ) of P on initial valuation ν0I
is ν O , i.e., if j = |πP (ν0I )| − 1, ηj = (`, ν) and ν(o) = ν O . Program P satisfies a

6

set of tests T if it satisfies all the tests t ∈ T . The repair problem is then to find
a program that satisfies both the direct manipulation and the tests.
Cost-aware Repair Among the many programs that satisfy a given manipulation we would like to pick the “best” one. To define what it means for a candidate repaired program to be better than another, we draw upon the notions of
program distances proposed in [5]. We define two types of distances: syntactic
and semantic distances. Given a program P , a syntactic distance is a function
P
fsyn
: P → N that maps each program in the repair space to a quantity capturing
its syntactic similarity to the original program P . We define semantic distances
using distance functions over execution traces. Let dist(π, π 0 ) denote a distance
function mapping a pair of traces to a non-negative integer. Intuitively, dist captures the similarity between execution traces of P and P 0 on the same initial
valuation ν0 . Given a program P and a direct manipulation M = (ν0 , k, ν 0 ),
P,M
: P → N maps a repaired program P 0
a semantic distance function fsem
0
to dist(πP (ν0 )[0,k] , πP (ν0 )[0,j] ) capturing the similarity between the manipulated trace πP (ν0 )[0,k] of P and the corresponding manipulation-satisfying trace
πP 0 (ν0 )[0,j] of P 0 with manipulation-satisfying index j. An aggregation function
Aggr : N × N → N is used to combine the two distance functions.
Example 2. An example of syntactic distance between two programs P and P 0
is the number of node edits needed to transform the abstract syntax tree P into
the one P 0 . According to this distance, the change from i=1 to i=0 showed in
Figure 1 has syntactic distance 1. An example semantic distance is the sum of
the differences in variable valuations in program configurations of the execution
traces πP (ν0 )[0,k] and πP 0 (ν0 )[0,j] (with j as defined above).
For a program P and direct manipulation M, we can define the cost of a repaired
P,M
P
(P 0 )). The following definition
(P 0 ), fsem
program P 0 as cost(P 0 ) = Aggr(fsyn
can be generalized to incorporate a set of tests.
Definition 2 (Cost-aware Repair via Direct Manipulation). Given a program P and a direct manipulation M, the cost-aware program repair via direct
manipulation problem is to find a program P 0 ∈ RM(P ) that satisfies the manipulation M and such that, for every P 00 ∈ RM(P ) that satisfies the manipulation
M, we have cost(P 0 ) ≤ cost(P 00 ).

4

JDial’s architecture

In this section, we describe the architecture of JDial and the sketching-based
approach JDial employs to repair programs (Figure 2).
JDial takes as input a buggy program, a direct manipulation on an input
trace, and (optionally) a set of test cases (left of Figure 2). As described in Section 3, the repair problem is defined using four components: a repair model, a
syntactic distance function, a semantic distance function, and a cost-aggregation
function. In JDial, these components are modular and defined independently

7
Buggy Program
1.

16.
20.

JDial Backend

Prog(input) {
…
…
x = 5y+2;
…
y = y+2
…

GetRepairSpace(){
// returns a sketched version
// of Prog that encodes
// the repair space
e.g., replace constants with ??
}

}

SyntacticDistance( ){
// computes syntactic
// distance from original
// program based on holes
if (??1 != 1) dist += ??1;
…
}

TraceDistance(t1, t2){
// computes semantic
// distance between
// traces t1 and t2
return Hamming(t1, t2)
}

Aggregate(d1, d2){
// combines the
// two distances
return d1+ d2;
}

Sketch
Specification
Trace +
Manipulation
input: 9
-----line 16
---> x: 0 -> 3

y: 2 -> ?

Test cases
input output
2
12
4
42
...
...

// Instrumentation variables
counter, line[], valx[], valy[], ret_val
// Instrumented program
SkProg(input) {
// Adds holes to encode repair
// space and to compute traces
...
counter++;
y = ??1 x + ??2 y + ??3;
line[counter] = 20;
valx[counter] = x;
…
}

// Functional assertions + distance computations
// Direct manipulation
SkProg(9);
assert(line[...]=16);
assert(valx[...]=3);
semDist += TraceDistance(..., ...)
// Test Cases
assert(SkProg(2)=12);
semDist += TraceDistance(..., ...)
assert(SkProg(4)=42);
semDist += TraceDistance(..., ...)
...
synDist = SyntacticDistance()
minimize(Aggregate(synDist, semDist));

Fixed Program
1.

16.
20.

Prog(input) {
…
…
x = 5y+2;
…
y = x-1;
…
}

Fig. 2: Architecture of JDial.
from the underlying synthesis engine (grey boxes at the top of Figure 2). The repair model is given as a program GetRepairSpace that, given a program, returns
a sketched version of it—i.e., a program with unknown holes of the form ??. In
Figure 2, this program simply replaces each constant with a hole. By instantiating the holes in the sketched program with concrete values we obtain a program
in the repair space. The syntactic distance is given as a program that computes a
non-negative integer based on the values of the holes in the sketched program—
e.g., how many constants were changed or by how much they were changed. The
semantic distance is given as a program that computes a non-negative integer
based on the value of two traces—e.g., the Hamming distance.
4.1

From Program Repair to Sketching

To solve the repair problem, JDial computes a sketched program together with a
set of assertions (blue box in Figure 2). The solution to this sketched program—
i.e., values for the holes that satisfy the assertions and minimize the given objective function—is the solution to the program repair problem.
Background on sketching Program sketching is a technique for specifying a parametric set of programs. This is done by allowing programs to contain holes (denoted by ??). When one provides a specification—e.g., test cases, assertions,
minimization objectives—the sketching problem is to find (typically integer)
values of the holes that satisfy the given specification. State-of-the-art sketching
tools support complex program constructs, such as arrays, strings, and recursive
functions, as well as complex specification mechanisms, such as Boolean assertions and quantitative optimization constraints over the values of the holes [28].
Computing distances and guessing trace lengths The GetRepairSpace component, given the buggy program, adds holes to generate a sketched program encoding the repair space—e.g., y = ??_1 * x + ??_2 * y + ??_3 in Figure 2
(blue-box). JDial then generates a function that uses the values placed in the
holes to compute the syntactic distance (Figure 2(top)).

8

To compute the semantic distance JDial symbolically extracts program
traces by instrumenting the sketched program with a counter to measure the
length of the trace, an array to record the values of each variable in the original program, and an array for the line numbers.1 After executing each sketched
instruction, the arrays are updated to reflect the current variable values (Figure 2(blue-box)). JDial then extract the traces from such arrays and uses them
to compute the semantic distance.
The key difficulty in encoding our repair problem is that there can be many
ways to “align” the location manipulated by the user with a location in the
sketched program—e.g., the execution of one repaired program might reach the
desired manipulated value the second time the manipulated location is visited,
while another repair might reach the desired value the tenth time the manipulated location is visited. JDial must be able to consider all these possibilities.
Example 3. Consider the manipulation described in Fig. 1(a). The execution of
the repaired program largestGapFix presented in Fig. 1(b) on input [9, 5, 4] hits
the manipulated location with max=9 the first time line 8 is traversed. However,
another correct repair which changes the loop in line 5 to i=N-2; i>=0; i--,
hits the manipulated location with max=9 the second time line 8 is traversed.
Our key idea is to introduce an existential un- ...
visit_time == 0) {
known variable—i.e., another hole—in our sketched if ( //
record state
return ;
program to guess at what visit time the manipulated line is reached with the variable values provided }else
visit_time - -;
by the user. Concretely, we define a global variable
Sketched version of
int visit_time = ?? to guess the number of visits //
// manipulated line
of the manipulated line and modify the sketched pro- ...
gram right before the sketched version of the manipulated line to interrupt the trace at the correct time Fig. 3: Instrumentation
(see Fig. 3). Thus, every time the manipulated line to guess visiting times.
is reached, visit_time is decremented and, when the
counter hits zero, the execution has reached the guessed number of visit times.
Finally, JDial adds assertions to guarantee the sketch solution satisfies the
manipulation and a minimization objective to ensure the returned solution is
optimal with respect to the given distances (see right of blue box in Fig. 2).

5

Implementation and optimizations

JDial is composed of a frontend, which allows to visualize program traces and
manipulate intermediate states, and a backend, which repairs the manipulated
programs. JDial’s frontend uses the tool java_jail to extract program traces
and JavaScript, together with the library CodeMirror, to render the user interface and communicate with the backend. JDial’s backend uses the synthesizer
1

We assume that the length of the trace in the repaired program is at most twice the
length of the original trace and we use this assumption to initialize the length of the
arrays. This constant is parametric and can be modified.

9

Sketch [28] to solve the sketched programs we generate using the technique proposed in Section 4. JDial can repair Java programs over integers, characters,
Booleans, and arrays over these basic types. In its default mode, JDial only
tries to repair statements in the function in which the manipulated line appears.
In this section, we describe the concrete repair model and distance functions
JDial uses as well as several optimizations employed by JDial.
5.1

Repair Model and Syntactic Distance

JDial supports complex repair models—e.g., it can allow statements to be added
to the program. However, overly expressive repair models will often lead to undesired repairs that overfit to the given manipulation. In fact, existing repair
tools for introductory programming assignments typically employ several repair
models, each tailored to a particular programming assignment [26, 22].
Since in our application domain we do not know a priori what program
the programmer is trying to write, JDial’s default repair model only allows to
rewrite constants in linear arithmetic expressions (see Appendix A for details).
First, any variable in any expression is multiplied by a hole ??b that can only
take values from the set {−1, 0, 1}. These holes can
P be used to remove variables
and negate their coefficients. Second, the term v∈V ??b v+??, where V is the
set of variables, is added to each expression appearing in an assignment or in
a Boolean comparison. These terms can be used to add new variables, further
increase/decrease the coefficients of variables appearing in the expression, or
add new constants—e.g., turn x<0 into x>y. This repair model permits modifications of multiple expressions and it subsumes the default error model of the
AutoGrader tool, which, despite its simplicity, was shown to be able to repair
30%-60% of edX student submissions depending on the problem type [26].
JDial’s syntactic distance computes the difference between the synthesized
hole
P values and the original ones. For example, in the expression ??b x < 0 +
v∈V ??b v+?? (corresponding to original expression x<0), the original value of
the first hole ??b is 1, while the original value of all the other holes is 0. The syntactic distance is the sum of the absolute difference between each hole’s synthesized value and the original one. Intuitively, this distance penalizes modifications
that introduce new variables and modify constants by large amounts.
5.2

Semantic Distance over Traces

When computing the distance from the original program traces, JDial ignores
the variables that have been manipulated because they are likely to contain
“incorrect” values that are not necessary to preserve. JDial first computes the
restricted traces where the values of the manipulated variables are omitted and
then uses a modified version of the Hamming distance to compute their distance.
In the following definitions, we assume Boolean tests return 1 when true and 0
when false. Given two configurations η = (l, ν) and η 0 = (l0 , ν 0 ) over a set of
variablesP
V , the distance between the two configurations is defined as H(η, η 0 ) =
0
(l 6= l )+ w∈V ν(w) 6= ν 0 (w). Finally, JDial computes the distance between two

10

r

// Test case
// Partial i nterpr etatio n
// sumPow (3)=15
// of Mathpow
int sumPow ( int x ){
int Mathpow (a , b ){
int sum = 1;
if ( a ==2 && b ==1)
for ( int i =1; i < x ; i ++){
return 2;
sum += Math . pow (2 , i );
if ( a ==2 && b ==2)
}
return 4;
return sum ;
if ( a ==?? && b ==??)
}
return ??; }

(a)

(b)

1. JDial guesses Mathpow(2,3)=14
2. Is Math.pow(2,3)=14?
3. No, modify Mathpow

(c)

Fig. 4: Given an example with an incorrect for-condition and an input test (a),
JDial uses the execution of sumPow on the test to learn an initial partial interpretation of the function Math.pow (b). JDial then produces a proposed repair
and guesses the interpretation of Math.pow to be such that Math.pow(2,3)=14
(c). After executes Math.pow in Java, JDial discovers that Math.pow(2,3)=8,
and refines the interpretation of Math.pow for the next round of repair.

traces π = η1 · · · ηs and π 0 = η10 · · · ηt0 , where m = min(s, t) and M = max(s, t)
0
) + M − m.
as the quantity H(η1 , η10 ) + · · · + H(ηm , ηm
Example 4. Consider again the example described in Figure 1. The restricted
trace of the repaired program up to the manipulation-satisfying index has distance 3 from the original trace since it only changes the value of the variable i
in the last three steps and it has the same length as the original program trace.
JDial contains other implementations of trace distances—e.g., longest common subsequences. Since the distance presented above yields good results and
performance in practice, we use it as default and use it in our experiments.
JDial aggregates the syntactic and semantic distances by taking their sum.
5.3

Handling External Functions

JDial employs a new Counterexample-Guided Inductive Synthesis (CeGIS)
scheme to repair programs that contain external functions for which semantics
might be unknown or expensive to encode directly in Sketch. Given the input
program with an external function ext and the manipulated trace, JDial creates
a sketched program that assigns a partial interpretation to the external function
using the set of concrete values obtained from the input trace execution—i.e.,
for every call of the function observed in the input trace. JDial then computes
a repair for the sketched program using the partial definition of ext it obtained
from the trace. If repairing the program requires knowing the interpretation of
ext on inputs that have not been observed yet, JDial lets Sketch “guess”
an interpretation for the function ext on such inputs. JDial can then execute
the function ext and check whether the guesses were correct. If they are not
correct, JDial modifies the new sketched program to incorporate the partial
interpretation to the external function ext on the newly discovered inputs. The
process continues until JDial finds a repair that respects the semantics of ext.

11

Example 5. Consider the program sumPow in Fig. 4(a), which should compute
the sum of powers of 2 up to x, but instead it only computes the sum up to x-1.
By running the program on the given input 3, JDial can obtain the output of the
Math.pow function on input values 1 and 2, and constructs a Sketch function
that describes a partial interpretation of Math.pow as shown in Figure 4(b). To
repair the program, JDial needs to change the condition of the for loop, but this
repair requires knowing the output of the function Math.pow on arguments (2,3)
and our partial interpretation of Math.pow does not contain this information.
JDial synthesizes a repair for the function sumPow and, while doing so, it assigns
an interpretation to the inputs for which the behaviour of the function Math.pow
is unknown (Figure 4(c)). JDial then uses the concrete execution of the function
Math.pow to check whether the synthesized interpretation is incorrect, and in this
case it modifies the partial interpretation of Math.pow in the sketched program.
5.4

Additional Features and Optimizations

We discuss additional features and optimizations supported by JDial.
Specified repair range Since the programmer might want to prevent JDial from
modifying certain program statements, JDial’s frontend allows the programmer
to specify what statements the tool is allowed to modify.
Single statement repairs Since most
repairs only require to modify a
single statement, JDial supports
this restricted repair model and it
uses an optimized solver that, for
each line of code, builds a separate
sketched program that is only allowed to modify that line. The separate sketched programs are then
solved in parallel and JDial outputs
the repair with the least aggregate
cost.
For each individual sketch that
can only modify a certain line of
code, JDial uses a data flow analysis based on program slicing [35] to
summarize parts of the program for
which the corresponding traces will
not be affected by the code modification. Concretely, let `M be the
location at which the manipulation
is performed and `R be the location JDial is allowed to modify. By
computing a backward slice of the
manipulated location `M , we obtain

1
2
3
4
5
6
7
8
9
10
11
12
1
2
3
4
5
6

// input : [3 ,2 ,7]
int [] subLargestGap ( int [] a ){
int N = a . length ;
int min = max = a [0];
for ( int i =0; i < N ; i ++){
if ( max < a [ i ]) max = a [ i ];
if ( min > a [ i ]) min = a [ i ];}
int largestgap = max - min ;
R:for(int i=1; i<N; i++){
a [ i ] = a [ i ] - largestgap ;
M:}
return a ; }
void sliced ( int [] a ){
int N = 3;
int largestgap = 5;
for ( int i = 1; i < N ; i ++)
a [ i ] = a [ i ] - largestgap ;
return a ; }

Fig. 5: Program subLargestGap and its
sliced version when the manipulation
happens at line 13 and only line 11 can
be modified.

12

the statements that can affect the values of the manipulated variables. Similarly,
only statements that are reachable from location `R in the control-flow graph of
the program are affected by modifications to line `R . Finally, the intersection of
the two sets gives us the statements where variable values may vary as a result of
a repair. All other statements are irrelevant and can be removed or summarized.
Example 6 Consider the program subLargestGap in Fig. 5 that returns a new
array obtained by subtracting the largest gap of the input array from all its
elements. This program contains a mistake in the second for loop. Assume a student is trying to fix it by manipulating the variable a[0] at location 11 on input
[3,2,7] and that the repair model only allows modification to location 9. The
backward slice of location 11 contains all the statements in the program except
the return statement and the lines 9 to 12 are the only lines reachable from location 9. Using this information, JDial summarizes all other statements’ values.
For example, the whole computation of the variable largestGap is replaced by
the constant assignment largestGap=5.

6

Evaluation

We evaluate the effectiveness of JDial through the following questions.
Q1
Q2
Q3
Q4

Can JDial produce good repairs more often than test-based techniques?
Is the optimized version of JDial presented in Sec. 5.4 effective?
How sensitive is JDial w.r.t. the location of the manipulation?
Can JDial repair programs that contain external functions?

We perform our evaluation on 17 Java programs: 12 from Qlose [5] and
5 new programs. The programs from [5] are small introductory programming
assignments and programs from repair literature (see Appendix B for details).
Table 1 shows detailed metrics for each benchmark and the average runtime
of JDial when performing repair on five randomly generated failing inputs. All
experiments were performed on an Intel Core i7 4.00GHz CPU with 32GB/RAM.
Comparison to Test-based Repair. We compare JDial against the tool
Qlose to see if repair via direct manipulation can find correct repairs more often
than test-based repair. We compare against Qlose because it is the only repair
tool that uses semantic distances and it produces accurate repairs from a small
number of test cases more often than tools that only use syntactic distances [5].
For each benchmark, we randomly generate 5 input tests that result in incorrect outputs. For each failing test, we run Qlose using the test as a specification
and run JDial by manually constructing a manipulation: we identify the first
location in the execution trace where a variable has the wrong value and modify
it to the correct one. Figure 6 illustrates the results of this comparison (JDial
and Qlose bars). JDial generates the intended repairs in 66% (56/85) of the
cases while Qlose never produces a correct repair. In particular, when given
only one test case, Qlose always modifies the return statement of the program.
We perform another study where, for each previous experiment, we provide
JDial and Qlose with an additional (failing or passing) test—i.e., we provide

13

Table 1: Effectiveness and performance of JDial. Success denotes the number
of tests (out of 5) for which we get a desired repair. 7 denotes out of memory.

Succesful tests

New

Qlose [5]

Problem
largestGap-1.1
largestGap-1.2
largestGap-2
largestGap-3.1
largestGap-3.2
tcas
max3
iterPower-1
iterPower-2
ePoly-1
ePoly-2
multIA
ePoly-3
max4
bubbleSort
subLargestGap
maxMin
6

LOC Vars Success
7
7
7
7
7
10
5
5
5
6
6
4
7
7
7
13
13

4
4
4
4
4
4
3
3
3
4
4
4
4
4
5
6
6
Qlose

3
4
2
4
4
0
5
4
5
4
3
5
4
5
4
7
7

Trace Time Time single line [sec]
Length [sec]
JDial1
JDialo1
11
3.8
1.6
1.0
10
2.2
0.8
0.6
15
4.2
1.1
0.5
10
1.8
1.1
0.5
10
2.8
1.0
0.6
7
0.8
0.4
0.4
3
0.5
0.3
0.3
14
0.4
0.6
0.4
14
0.7
0.4
0.3
12
4.6
3.7
1.3
12
2.5
1.7
0.9
9
1.3
0.8
1.1
13
2.9
2.8
2.5
4
0.3
0.2
0.3
12
3.1
1.3
0.6
35
7
7
0.7
37
7
7
0.9

JDial

Qlose+

JDial+

4
2
0
.1 .2 -2 .1 .2 cas ax3 r-1 r-2 y-1 y-2 tIA y-3 ax4 ort Gap Min
l
-1 -1 ap -3 -3
t
m we we ol ol
m eS st
l
x
e
ap Gap stG Gap Gap
l
mu ePo
ma
o eP eP
o
G
t st ge st st
bb arg
rP erP
s
u
e
r
e
e
e
e
b bL
it it
rg rg la arg arg
su
la la
l
l

Fig. 6: JDial vs Qlose. Additional test provided in JDial+ and Qlose+.
Qlose with two tests and JDial with one test and one manipulation. Figure 6
illustrates the results of this comparison (cf. JDial+ and Qlose+ bars). JDial
generates the intended repairs for 75% (64/85) of the cases while Qlose produces
the correct repairs on 58% (49/85) of the cases. While Qlose performs better
than when given a single test, for every input on which Qlose produces the
correct repair, JDial also does so. Remarkably, when given a single manipulation and nothing more, JDial produces correct repairs more often than Qlose,
even when the latter is provided with 2 tests. To answer Q1, JDial produces
meaningful repairs more often than techniques that only use tests.
Before concluding, we explain why both tools performed poorly on some
benchmarks. For the tcas program, the desired fix modifies an expression by
adding a large constant that can only be synthesized from a very specific test
case. subLargestGap and maxMin are too large. For the instances for which

14

JDial produces the incorrect repair, we evaluate whether JDial produces correct repairs if it is allowed further “attempts”. Whenever an undesired repair is
generated at a location `, we disallow JDial to repair location ` again or reject
the proposed repair and ask for a different one. This approach repairs an additional 6 failing tests across all programs with an average of 2.2 user interactions.
Optimizations for Single-line Repairs. We repeat the previous experiment
using the single-line repair model described in Sec. 5.4. We refer to the version of
JDial with this restricted repair model as JDial1 and its optimized version as
JDialo1 . Since in our previous experiments JDial always finds a repair that only
involves a single line, both JDial1 and JDialo1 find the same repair. The last
two columns of Table 1 show the running times. JDial1 is generally faster than
the version of JDial that uses the more complex repair model. However, the
optimized version JDialo1 is on average 1.37x faster than JDial1 . Moreover, for
subLargestGap and maxMin, JDialo1 finds repairs in <1 second while JDial1
times out. The improvement is due to the slicing-based data-flow analysis, which,
can reduce the number of lines in the sketched program from 25 to 8.
To answer Q2, the optimization from Sec. 5.4 is beneficial for singleline repairs. This repair model is very practical and our results hint that our
slicing technique can make JDial scale to larger programs.

% preser. repair

Sensitivity of Manipulated Location. One of the key aspects of JDial
is that the user has to find a “good” location to perform the desired repair.
In this experiment, we evaluate how sen100
sitive JDial is with respect to the location choice. We consider the experiment
JDial
50
we performed against test-based repair and
JDial+
for each test case on which JDial and
0
JDial+ successfully found a correct re0
2
4
pair, we then perform the following analysis: if the manipulation was performed at
k : steps after manipulation
step i in the program trace, we measure afFig. 7: Correct repair if manipulater how many steps the generated repair is
tion is performed k steps later.
“lost”—i.e., we compute the smallest k for
which performing the manipulation at position i + k would yield a wrong repair.
Figure 7 shows the results. In 80% of the cases, if JDial is provided only
with a manipulation and the manipulation is performed one step later, JDial
returns an incorrect repair. However, when provided with one additional test
case JDial returns the correct repair in 80% of the cases, even when the manipulation is performed 5 steps after the ideal location. Even in these extreme
conditions, JDial returns correct repairs more often than Qlose does when provided with two test cases. To answer Q3, JDial is sensitive with respect
to the manipulation location only if no additional tests are provided,
but it is still more precise than repair via test cases.
Ability to Handle External Functions. We evaluate if JDial can repair
programs with external functions. ePoly-1 and ePoly-2, contain the function

15

Math.pow and JDial is able to produce a repair for them using between 2 and
5 iterations (average 4.2), of the CeGIS algorithm presented in Sec. 5.3.
To better evaluate the algorithm, we design two families of benchmarks
that
Pn use auxiliary functions. The first family of programs tries to compute
i=0 Math.pow(2, i) for values of n between 2 and 8. The bug in this benchmark is the one shown in Figure 4. For inputs 2 and 3, JDial can find the
correct repair that is compliant with the external function after 2 CeGIS iterations, while for inputs 4 through 8, JDial requires 3 iterations. The second
family of programs computes the maximum value in an array using the Math.max
function for different incorrect initializations of the variable max. In this case,
the size of the initial constant affects the number of required CeGIS iterations.
While incorrectly initializing max to 2 only requires a couple of iterations to
produce the correct repair, if we incorrectly initialize max to 100, computing the
repair requires guessing many new interpretations of the function Math.max that
did not appear in the original trace, resulting in more than 90 iterations.
To answer Q4, JDial can repair programs that contain external
functions, but in certain pathological cases it requires many CeGIS iterations.

7

Related Work

Direct manipulation Direct manipulation is an old concept [25] and several drawing editors [33, 24, 11] provide programming capabilities and at the same time
allow the user to interact with the graphics being displayed by the code. Sketchn-Sketch [4, 10] uses a simple form of program synthesis to combine direct and
programmatic manipulation of scalable vector graphics (SVG), where constants
in the program can be modified conforming to the direct manipulations. Sketchn-Sketch and JDial are somewhat incomparable due to the different domains,
but we describe some high-level differences between the two tools. Sketchn-Sketch can only rename constants defined at the top of the program and,
unlike JDial, cannot handle complex updates involving changes in the program
structure—e.g., replacing x = y with x = y − z. Moreover, Sketch-n-Sketch
employs heuristics to identify the “right” fix, while JDial identifies fixes that
are optimal with respect to syntactic and semantic distances.
Wolverine [32] allows direct manipulation of data-structure transformations.
In Wolverine, the user can modify a graphical abstract representation of a data
structure such as a linked list and the tool will attempt to find a program modification consistent with the modification. Similar to Sketch-n-Sketch, Wolverine’s technique is specific to certain families of data structure transformations
and relies on the graphical abstraction used for the manipulation.
CodeHint [7] synthesizes simple Java expressions—e.g., library calls—at
user-set breakpoints using partial specifications—e.g., variable types. It uses information from the execution to construct expressions of a user-provided type.
CodeHint is different from JDial in three main aspects: (i ) CodeHint helps
programmers auto-complete function calls given some expected type at a given
location, whereas JDial repairs the original program using a global analysis.

16

(ii ) CodeHint can only synthesize one expression at a time due to its specific
interaction mode. (iii ) CodeHint performs brute-force search while JDial uses
constraint-based search with optimization objectives.
Personalized education There are many tools for teaching programming that
help with grading (see [29] for a survey), personalized feedback [21, 8, 13, 26, 5,
22], and visualization [9]. Several works have dealt with transforming repair tools
into feedback generators [30]. Here, we discuss tools relevant to our work.
AutoGrader [26] and Qlose [5] can compute program repairs for incorrect student solutions to introductory programming assignments. These systems
require the teacher to provide a reference implementation or a comprehensive
set of test cases while JDial also allows students to discover potential repairs
using direct manipulations. AutoGrader [26] computes syntactically minimal
repairs while Qlose computes syntactically and semantically minimal repairs
based on a set of test cases. JDial extends Qlose’s technique to compute minimal program repairs based on prefix traces and manipulated states. In particular, JDial encodes the problem of finding good stop points for aligning partial
program traces that is novel in our setting of direct manipulation of variables.
Program repair This topic has been studied extensively and researchers have proposed techniques based on constraint-solving [20], abstractions [17], and genetic
algorithms [1, 16]. JDial falls in the first category, but it would be interesting
to investigate the effectiveness of the other techniques in our domain. There are
approaches that find repaired programs that are syntactically close [23, 18] or
semantically close [34] to the original program. It was demonstrated in [5] that
repairs generated using a combination of syntactic and semantic program distances are, in general, more desirable. Hence, JDial chooses this last approach.
Existing tools use test cases [20, 5], logic specifications [15], or reference
programs [26]. Direct manipulation “augments” a test case by allowing the user
to specify intermediate information about the run of the program on a certain
input. Moreover, direct manipulations can be used to debug partially written
implementations. Finally, it is important to note that direct manipulation is
not directly expressible using assertions or test cases: while an assertion at a
certain location is valid if every time the location is traversed the predicate in
the assertion is true, a direct manipulation at a certain location only requires
that at some point in the trace the variables evaluate to the manipulated values
at that location.
Several repair tools use fault localization to find likely locations to modify [2,
12, 3, 14]. Extending fault localization techniques to our setting is another interesting research direction. The work on angelic debugging [3] is particularly
relevant to JDial, where the technique infers possible faulty expressions in a
program by replacing them with an alternate concrete value (oracle) that makes
all the tests pass. However, the burden on repairing the program with the correct
expression still lies with the programmer.
The CeGIS refinement of external functions presented in Sec. 5.3 is related to
the notion of Sketch models [27], which allow one to specify certain properties
(such as associativity, idempotence, etc.) to provide richer interpretations to

17

uninterpreted functions. In contrast, JDial iteratively builds a model of the
auxiliary function directly from the repair process.

8

Conclusion

We presented a new specification mechanism called direct manipulation, which
allows programmers to modify variable values at an intermediate point in a failing trace to indicate what variable values were expected. We built the tool JDial
that can repair simple Java programs to satisfy direct manipulations specified
by the programmer. Finally, we showed that direct manipulations lead to more
accurate repairs than those computed using only test cases. While our approach
has shown promising results on simple programs appearing in introductory programming assignments, this paper is just the first step towards a new, exciting
direction and many research questions remain open. Our next steps include investigating more complex manipulation techniques that can be used by real programmers on large scale programs and designing user studies to assess whether
students/programmers are receptive to this novel specification paradigm.

References
1. Arcuri, A.: On the automation of fixing software bugs. In: Companion of the 30th
international conference on Software engineering. pp. 1003–1006. ACM (2008)
2. Ball, T., Naik, M., Rajamani, S.K.: From symptom to cause: localizing errors in
counterexample traces. In: ACM SIGPLAN Notices. vol. 38, pp. 97–105. ACM
(2003)
3. Chandra, S., Torlak, E., Barman, S., Bodik, R.: Angelic debugging. In: Software
Engineering (ICSE), 2011 33rd International Conference on. pp. 121–130. IEEE
(2011)
4. Chugh, R., Hempel, B., Spradlin, M., Albers, J.: Programmatic and direct manipulation, together at last. In: Proceedings of the 37th ACM SIGPLAN Conference
on Programming Language Design and Implementation. pp. 341–354. ACM (2016)
5. D’Antoni, L., Samanta, R., Singh, R.: Qlose: Program repair with quantitative
objectives. In: International Conference on Computer Aided Verification. pp. 383–
401. Springer (2016)
6. edX: Introduction to computer science and programming using python (2017),
https://www.edx.org/course/introduction-computer-science-mitx-6-00-1x-10
7. Galenson, J., Reames, P., Bodik, R., Hartmann, B., Sen, K.: Codehint: Dynamic
and interactive synthesis of code snippets. In: Proceedings of the 36th International
Conference on Software Engineering. pp. 653–663. ACM (2014)
8. Gulwani, S., Radiček, I., Zuleger, F.: Automated clustering and program repair for
introductory programming assignments. arXiv preprint arXiv:1603.03165 (2016)
9. Guo, P.J.: Online python tutor: embeddable web-based program visualization for
cs education. In: Proceeding of the 44th ACM technical symposium on Computer
science education. pp. 579–584. ACM (2013)
10. Hempel, B., Chugh, R.: Semi-automated svg programming via direct manipulation.
In: Proceedings of the 29th Annual Symposium on User Interface Software and
Technology. pp. 379–390. ACM (2016)

18
11. Hottelier, T., Bodik, R., Ryokai, K.: Programming by manipulation for layout. In:
UIST. pp. 231–241 (2014)
12. Jose, M., Majumdar, R.: Cause clue clauses: error localization using maximum
satisfiability. ACM SIGPLAN Notices 46(6), 437–446 (2011)
13. Kim, D., Kwon, Y., Liu, P., Kim, I.L., Perry, D.M., Zhang, X., Rodriguez-Rivera,
G.: Apex: Automatic programming assignment error explanation. In: ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications. pp. 311–327. OOPSLA 2016, ACM (2016)
14. Könighofer, R., Bloem, R.: Automated error localization and correction for imperative programs. In: Formal Methods in Computer-Aided Design (FMCAD), 2011.
pp. 91–100. IEEE (2011)
15. Koukoutos, M., Kneuss, E., Kuncak, V.: An update on deductive synthesis and
repair in the leon tool. arXiv preprint arXiv:1611.07625 (2016)
16. Le Goues, C., Dewey-Vogt, M., Forrest, S., Weimer, W.: A Systematic Study of Automated Program Repair: Fixing 55 out of 105 Bugs for $8 Each. In: International
Conference on Software Engineering (ICSE). pp. 3–13. IEEE Press (2012)
17. Logozzo, F., Ball, T.: Modular and verified automatic program repair. In: ACM
SIGPLAN Notices. vol. 47, pp. 133–146. ACM (2012)
18. Mechtaev, S., Yi, J., Roychoudhury, A.: Directfix: Looking for simple program repairs. In: Proceedings of the 37th International Conference on Software
Engineering-Volume 1. pp. 448–458. IEEE Press (2015)
19. Monperrus, M.: Automatic software repair: a bibliography. University of Lille, Tech.
Rep. hal-01206501 (2015)
20. Nguyen, H.D.T., Qi, D., Roychoudhury, A., Chandra, S.: Semfix: Program repair
via semantic analysis. In: Proceedings of the 2013 International Conference on
Software Engineering. pp. 772–781. IEEE Press (2013)
21. Rivers, K., Koedinger, K.R.: Data-driven hint generation in vast solution spaces:
a self-improving python programming tutor. International Journal of Artificial Intelligence in Education pp. 1–28 (2015)
22. Rolim, R., Soares, G., D’Antoni, L., Polozov, O., Gulwani, S., Gheyi, R., Suzuki, R.,
Hartmann, B.: Learning syntactic program transformations from examples (2016)
23. Samanta, R., Olivo, O., Emerson, E.A.: Cost-aware automatic program repair. In:
International Static Analysis Symposium. pp. 268–284. Springer (2014)
24. Schachman, T.: Apparatus (2015), http://aprt.us/
25. Shneiderman, B.: Direct manipulation: A step beyond programming languages.
ACM SIGSOC Bulletin 13(2-3), 143 (1982)
26. Singh, R., Gulwani, S., Solar-Lezama, A.: Automated feedback generation for introductory programming assignments. ACM SIGPLAN Notices 48(6), 15–26 (2013)
27. Singh, R., Singh, R., Xu, Z., Krosnick, R., Solar-Lezama, A.: Modular synthesis of sketches using models. In: International Conference on Verification, Model
Checking, and Abstract Interpretation. pp. 395–414. Springer (2014)
28. Solar-Lezama, A.: Program sketching. International Journal on Software Tools for
Technology Transfer 15(5-6), 475–495 (2013)
29. Striewe, M., Goedicke, M.: A review of static analysis approaches for programming
exercises. In: International Computer Assisted Assessment Conference, pp. 100–113
(2014)
30. Suzuki, R., Soares, G., Head, A., Glassman, E., Reis, R., Mongiovi, M., D’Antoni,
L., Hartmann, B.: Tracediff: Debugging unexpected codebehavior using synthesized
code corrections. In: VL/HCC 2017 (2017)

19
31. Tillmann, N., De Halleux, J., Xie, T., Bishop, J.: Code hunt: Gamifying teaching and learning of computer science at scale. In: Proceedings of the first ACM
conference on Learning@ scale conference. pp. 221–222. ACM (2014)
32. Verma, S., Roy, S.: Synergistic debug-repair of heap manipulations. In: Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering. pp. 163–173. ESEC/FSE 2017, ACM, New York, NY, USA (2017),
http://doi.acm.org/10.1145/3106237.3106263
33. Victor, B.: Drawing dynamic visualizations (2013), http://worrydream.com/
34. Von Essen, C., Jobstmann, B.: Program repair without regret. vol. 47, pp. 26–50.
Springer (2015)
35. Weiser, M.: Program slicing. In: Proceedings of the 5th international conference
on Software engineering. pp. 439–449. IEEE Press (1981)
36. Yi, J., Ahmed, U.Z., Karkare, A., Tan, S.H., Roychoudhury, A.: A feasibility
study of using automated program repair for introductory programming assignments. In: Proceedings of the 2017 11th Joint Meeting on Foundations of Software
Engineering. pp. 740–751. ESEC/FSE 2017, ACM, New York, NY, USA (2017),
http://doi.acm.org/10.1145/3106237.3106262

A

Repair Model

Figure 8 illustrates JDial’s default repair model and Figure 9 illustrates an
example of how the repair model generates a Sketch from a program.

r(x = e)
r(e1 bop e2 )
r(return e)
r(e1 +e2 )
r(c*e)
r(c)
r(x)
r(x[e])
r(f(e))

→
→
→
→
→
→
→
→
→

P
x = r(e) + ( v∈V ??
Pb v+??)
r(e1 ) bop P
r(e2 ) + ( v∈V ??b v+??)
r(e) + ( v∈V ??b v+??)
r(e1 ) + r(e2 ) P
c * (r(e) + ( v∈V ??b v+??))
c
??b x
??b x[??b *e+??]
??b f(e)

Fig. 8: JDial’s repair model.

B

Detailed Benchmark Description

All benchmarks and the corresponding Sketch files are available at this url:
https://tinyurl.com/yd6bp3dx. The set contains three variants of largestGap
(§ 2), which is used in the Microsoft CodeHunt platform [31]. For two of the
largestGap benchmarks, largestGap-1 and largestGap-3, we further split
the programs into two sub-benchmarks denoted with the suffixes .1 and .2.
These are benchmarks in which the students has two logically separate errors
that would require many test cases to be fixed. We use .1 to denote the original

20
int triple ( int x ) {
int y = 3 * x ;
if ( x == 10)
y = 30;
return y ;
}

R

−
→

int SkTriple ( int x ) {
int y = 3*(?? b x +(?? b x +??) ) +(?? b * x +??) ;
if (?? b x == 10 + (?? b x +?? b y +??) )
y = 30 + (?? b x +?? b y +??) ;
return ?? b y + (?? b x +?? b y +??) ;
}

Fig. 9: A sketched program obtained from applying the repair model to a program. Holes of the form ?? can be instantiated with arbitrary integers. Holes of
the form ??b can only be instantiated with values in {−1, 0, 1}.

version of the benchmark and assume the task is to fix the first error in the
program and .2 to denote the same benchmark in which the first bug has been
fixed and the task is to fix the second error. The tcas-semfix program is a
toy traffic collision avoidance system from [20]. The max, iterPower, ePoly,
and multIA problems are taken from the Introduction to Python Programming
course taught on edX [6]. Two of the new programs we consider are variations of
Qlose benchmarks. The other three bubbleSort, subLargestGap, and maxMin
are larger programs that contain multiple loops, which are more complex than
the benchmarks considered in [5].

