2017 IEEE 41st Annual Computer Software and Applications Conference

New Strategies for Selecting Reuse Candidates
on Automated Program Repair
Akito Tanikado, Haruki Yokoyama, Masahiro Yamamoto, Soichi Sumi, Yoshiki Higo and Shinji Kusumoto
Graduate School of Information Science and Technology, Osaka University, Japan
Email: {a-tanikd, y-haruki, m-yamamt, s-sumi, higo, kusumoto}@ist.osaka-u.ac.jp
Abstract—Automated program repair (in short, APR) is atruly desired technique because it can reduce debugging costs
drastically. A well-known technique in APR is a reuse-based
approach, which inserts existing program statements in a given
program to suspicious code for an exposed bug. Some reports
show the reuse-based approach was able to ﬁx many bugs in open
source software. However, the existing approach often takes very
long time to ﬁx bugs. Its main factor is that so many variant
programs are generated by insertions and so many test cases
are executed for the variant programs before a ﬁxed programis generated. In order to shorten ﬁxing time with the reusebased approach, a ﬁxed program must be generated much more
efﬁciently. In this paper, we propose two strategies to generate
a ﬁxed program more efﬁciently. We also implement the twostrategies and conﬁrm that there are real bugs which the twostrategies contribute to shortening ﬁxing time.

Given program

Given program

6LPLODULW\6LPLODULW\RUGHU











Given program

Fig. 1. Overview of similarity-order

I. I NTRODUCTION/DVWXSGDWHWLPHDebugging is an inevitable task in software development,and it takes large costs. Recently, APR attracts much attentiondue to its latent capability to reduce debugging costs drastically. APR takes a buggy program and some test cases, and itoutputs a ﬁxed program, which passes all the given test cases.
GenProg [1], a well-known approach in APR techniques,
performs insertions and deletions to generate variant programs.
In insertions, selected program statements existing in a given
program are added to the suspicious code. Variant programs
are evaluated with the given test cases. If a variant program
passes all the test cases, it is outputted as a ﬁxed program.
Otherwise, next-generation variants are generated in the sameway. Those operations are repeated until a given time limit.
In GenProg, program statements for insertions are randomly selected. Thus, if a given program is not small, so many
program statements exist in the program, and inserting program statements contributing to ﬁxing the bug is unacceptableodds. Consequently, strategies to select contributive program
statements are required.
In this paper, we propose two strategies, similarity-orderand freshness-order. We have implemented the two strategies
and evaluated them with real bugs in open source software. Asa result, we found that there are bugs that the two strategies
were able to ﬁx in a shorter time than the original GenProg.

)UHVKQHVV
RUGHU


*LYHQSURJUDPFig. 2. Overview of freshness-order

preferentially selected. With this strategy, the bugs caused byoverlooking code clones can be efﬁciently repaired.
Fig. 1 describes an overview of similarity-order. First, weconsider a constant-sized region for each program statement
in a given program. Then, we compute a similarity between
each region and the suspicious code region. Finally, we selectprogram statements in order of the similarity.
B. Freshness-order

II. A PROACH

As shown in Fig. 2, in freshness-order, program statements
updated more recently are more preferentially selected. With
this strategy, the bugs caused by failing to reﬂect changes
involved with additions of new features can be efﬁciently ﬁxed.
In freshness-order, development history of a buggy program,
retrieved from version control system, is also given as input.
For each program statement in a buggy program, last update
time is taken from development history. We deﬁne the freshness of a program statement as how recently it is updated.
Then, we select program statements in order of the freshness.

In similarity-order, program statements included in codefragments with high similarity to the suspicious code are

To evaluate the usefulness of similarity-order and freshnessorder, we implemented an APR tool with these strategies

A. Similarity-order0730-3157/17 $31.00 © 2017 IEEE
DOI 10.1109/COMPSAC.2017.175

III. E XPERIMENT

266

by incorporating these strategies into Astor [2], an existing
APR tool. We also evaluated these strategies by comparing
results of using similarity-order and freshness-order with onesof original Astor (random), respectively. Evaluation items are
as follows:• number of repaired bugs, and• repair time.
Experimental objects are 106 bugs1 occurred in developing Apache Commons Math. These bugs are retrieved fromDefects4J [3], a dataset of bugs.

TABLE IR EPAIR TIME ( SEC ) OF 30 BUGS REPAIRED BY AT LEAST ONE STRATEGY.
“–” MEANS THE STRATEGY DID NOT REPAIR THE BUG .
Bug ID
math2
math5
math7
math8
math12
math20
math22
math24
math28math31
math40math44
math49math50
math53
math56
math60
math64
math70
math71
math73
math74
math77
math78
math80
math81
math82
math84
math85
math95

A. Experimental Results1) Number of Repaired Bugs: Random, similarity-order,and freshness-order ﬁxed 27, 22, and 23 bugs, respectively.
These results show neither similarity-order nor freshness-order
ﬁxed more bugs than random.
However, there are some bugs, which were not ﬁxed byrandom but were by similarity-order and/or freshness-order(e.g. math56 and math64 in TABLE I). This means the numberof repaired bugs can be increased by using similarity-order
and/or freshness-order.
2) Repair Time: We conducted Wilcoxon signed-rank testfor 18 bugs which had been ﬁxed with all three strategies,
to determine signiﬁcant differences of repair time between
similarity-order and random, freshness-order and random. The
p-values for pairs of similarity-order and random, freshnessorder and random were approximately 8.2 × 10−1 and 3.3 ×
10−1 , respectively. This means there are no signiﬁcant differences between similarity-order and random, nor freshnessorder and random. Therefore, random is not faster thansimilarity-order nor freshness-order, and vice versa.

canbeseen

Similarity-order
8,110
178
–
265
1,075
–
112
–
199
–
1,089
10,131
277
59
24
408
512
–
60
1,925
111
–
–
82
–
1,089
514
10,951
42
144

In this paper, we proposed two strategies, similarity-orderand freshness-order, to shorten ﬁxing time of APR. We have
implemented the two strategies and evaluated them with realbugs. As a result, we found that the two strategies and therandom-based selection, which is an existing strategy, have acomplementary relationship. From this ﬁnding, we conclude
that round-robin execution of the proposed strategies and theexisting one can reduce ﬁxing time averagely.
In the future, we are going to try to ﬁnd characteristics ofbugs to know an appropriate strategy before ﬁxing bugs formore shortening ﬁxing time. We are also going to implementa round-robin execution tool.

We found there were bugs the similarity-order and/or the
freshness-order were able to ﬁx more efﬁciently than theoriginal Astor. On the other hand, the two strategies were
not effective for other bugs. We conducted statistical tests
and found there were no signiﬁcant differences between thesimilarity-order/freshness-order and the original Astor. TABLE I shows actual time to ﬁx bugs with the three strategies.
We can see that• there are some bugs a strategy was able to ﬁx much morethan the others, and that• there are some bugs only a strategy was able to ﬁx.
Thus, the three strategies have a complementary relationship.
If we can select an appropriate strategy for a given bug, ﬁxing
time can be shortened drastically. However, at present, wehave no standard to select an appropriate strategy and so it
is impossible to know it before ﬁxing bugs. A promising
way to utilize our proposed strategies should be a roundrobin execution, which performs either of the three strategies
by rotation. Round-robin execution should be able to reduceﬁxing time averagely.
bugs

Freshness-order
11,183
625
–
259
8,521
477
115
–
175
–
922
11,469
1,657
62
4,903
854
10,744
4,223
82–
283
–
11,256
775
841
2,298
653
173
–
–

V. C ONCLUSION

IV. D ISCUSSION

1 The
details
ofthesehttps://github.com/rjust/defects4j

Random
198
271
5,798
214
3,330
214
406
13,300164
10,674
8,009
3,145
473
92
31
–
5,588
–
175
8,997
24
13,619
–
246
157
1,273
496
5,649
26
1,315

ACKNOWLEDGMENT
This work was supported by JSPS KAKENHI Grant Number 25220003.
R EFERENCES[1] C. Le Goues, M. Dewey-Vogt, S. Forrest, and W. Weimer, “A systematic
study of automated program repair: Fixing 55 out of 105 bugs for $8each,” in Proceedings of International Conference on Software Engineering (ICSE), 2012, pp. 3–13.
[2] M. Martinez and M. Monperrus, “Astor: a program repair library for java,”in Proceedings of the International Symposium on Software Testing andAnalysis (ISSTA), 2016, pp. 441–444.
[3] R. Just, D. Jalali, and M. D. Ernst, “Defects4j: A database of existingfaults to enable controlled testing studies for java programs,” in Proceedings of the International Symposium on Software Testing and Analysis(ISSTA), 2014, pp. 437–440.

here:267