2018 25th Asia-Pacific Software Engineering Conference (APSEC)

kGenProg: A High-performance, High-extensibilityand High-portability APR System
Yoshiki Higo, Shinsuke Matsumoto, Ryo Arima, Akito Tanikado,
Keigo Naitou, Junnosuke Matsumoto, Yuya Tomida, Shinji Kusumoto
Graduate School of Information Science and Technology, Osaka University
1-5 Yamadaoka, Suita, Osaka 565-0871, Japan
II. K G EN P ROG

Abstract—In this paper, we introduce our tool, kGenProg,
which is a new automated program repair system. kGenProg has
several remarkable features. Thanks to the features, kGenProg
got achieved high performance, high extensibility and highportability.
Index Terms—Automated program repair, Tool development,Fault localization

We call the new sytem kGenProg. The system is publicly
available at GitHub1 . As its name represents, kGenProg isa successor APR system to GenProg [1] and jGenProg [6].
kGenProg (and the other two tools) ﬁrstly localize code linesthat are likely causes of a given faults. Then, kGenProg
changes the localized code lines with simple manipulations
such as code insertion, deletion, and replacement. In thisprocessing, kGenProg generates not a single mutated program
but a multitude of mutated programs. Each mutated programis validated with given test cases. If a mutated program passes
all the test cases, it is output as a modiﬁed version. kGenProg
iterates this generate-and-validate process until a modiﬁed
version is generated.
At this moment, kGenProg’s target programming language
is Java because many existing tools have been developed forJava language.

I. I NTRODUCTION
Automated program repair (in short, APR) has been a hot
topic in the research ﬁeld of software engineering during thelast decade. From the viewpoint of reducing the debugging
cost, APR is extreme support because exposed faults are
fully-automatically ﬁxed by APR techniques. It means thatno human resources are required to ﬁx exposed faults.
Various APR techniques have been proposed before now.
A most famous technique should be GenProg [1]. GenProg
leverages the genetic algorithm to ﬁnd a modiﬁed version ofa given faulty program. A following research reported thatGenProg was able to generate modiﬁed versions that pass all
the given test cases for 55 out of 105 faulty programs [2].
An issue of GenProg is that it can ﬁx a given fault only
if the fault can be ﬁxed by reusing already-existing program
statements. Another research showed that only 10% faults canbe ﬁxed with already-existing program statements in the same
program [3].
There is another approach that synthesizes a modiﬁed version by leveraging semantic information of a given faulty program. Symbolic execution and constraint solving techniques
are often used in this approach [4], [5]. This approach canﬁx faults that require non-existing program elements in faulty
programs. However, due to calculation cost, this approachtargets only faults in conditional predicates such as if-statement
and while-statement.
Currently, the authors are developing a new system to implement and evaluate APR techniques. The developing system
has the following features:

A. In Memory computation
kGenProg performs the following computations in the process of APR for a given faulty program:
1) building programs,2) inserting logging instruments to Java bytecode, and3) executing test cases with the instrumented bytecode.
Java compiler usually outputs bytecode in the ﬁle system.
However if we do so, the computation performance in 1)
will not be good because a large number of compilations are
performed and a bunch of ﬁle I/O happens in the iteration ofgenerate-and-validate. Consequently, we designed kGenProg
not to trigger ﬁle I/O as much as possible. In kGenProg,bytecode is generated as a byte array in memory. Then, thebyte array gets instrumented for logging in memory. Theselogging instruments are required for fault localization. After
that, kGenProg loads the classes of the byte array with a
specialized class loader and performs the given test cases
for the classes. In summary, kGenProg performs all the threecomputations 1), 2), and 3) in memory with a single JavaVM process. Consequently, kGenProg get achieved a highperformance to execute the iteration of generate-and-validate
process.

in-memory computation,
designed with Strategy pattern,• high Portability, and• visualizing the process of fault modiﬁcation••

1 https://github.com/kusumotolab/kGenProg

In the next section, we introduce each of the above features.
978-1-7281-1970-0/18/$31.00 ©2018 IEEE
DOI 10.1109/APSEC.2018.00094

697

B. Implementation with Strategy-pattern
A big reason why the authors selected the iteration ofgenerate-and-validate process of the genetic algorithm as
our target is that many algorithms in the iteration can be
replaced with other different algorithms. For example, currently, kGenProg uses ochiai algorithm [7] to localize faulty
code. However, there are other different algorithms for fault
localization. Another example is a selection of program statements for insert operation. GenProg and jGenProg randomly
select already-existing program statements in a given faulty
program. On the other hand, more recent research proposed
effective strategies for selection [8], [9]. Consequently, it isimportant to easily switch to different algorithms and evaluate
them. kGenProg is designed to use the Strategy pattern in theselection points so as to easily switch to different algorithms
and even add new algorithms if necessary.

!
"#     %%
$$   &
 $$
    (a) Faulty program+# ,    $% 
-  -      "" %$%$!
%% # %&    $& %'  --      "" %$$%( !
%) # %*    $'  %+  $      "" $%, !
%- # &$    $( &%  -      "" %$&& !

C. High Portability
At present, there is no APR technique that is superior toany other techniques. Thus, comparing and evaluating thedifferences among APR techniques. Authors of some APR
tools have published their tools. However, such published
APR tools are in the minority. Thus, if a research groupgets a new idea of APR techniques and implements it, it is
difﬁcult to compare it with other already-proposed techniques.
We have actually faced this problem. To get APR tools,
we sent emails to authors of already-proposed techniques.
In most cases, we received no reply or the authors said
that the tools were unavailable. To promote easy-use andeasy-evaluation atmosphere, we made kGenProg’s source code
publicly available and also we made kGenProg as a single-jar
system. Only the jar ﬁle is required to execute kGenProg.

(b) Test cases   
(((  ##%&'(%&&##!
   "" ))$((    *$ (c) Generated PatchFig. 1: A simple program modiﬁcation with kGenProg
IV. C ONCLUSION

D. Visualizing APR processing
We are trying to improve kGenProg as a practical APR tool.
In such a development process, it is important to understandwhat kinds of program changes contribute to ﬁx a given fault.
In other words, the mutation genealogy of a given faulty
program is truly informative for improving the used algorithms
and inventing brand new algorithms. To obtain the genealogy
information, kGenProg preserves information of all generated
programs and their parent-child relationships. Currently, weare implementing a visualization feature for the mutation
genealogy information.

In this paper, we presented a new APR tool kGenProg.
Even kGenProg is still under development, we have alreadysucceeded in modifying some real faults in the Detect4J
dataset. In the future, we are going to invest more effective
algorithms for fault localization, selection for insert operationand ﬁtness function for the genetic algorithm.
R EFERENCES[1] W. Weimer, T. Nguyen, C. Le Goues, and S. Forrest, “AutomaticallyFinding Patches Using Genetic Programming,” in Proc. of ICSE2009.
[2] 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 Proc. of ICSE2012.
[3] E. T. Barr, Y. Brun, P. Devanbu, M. Harman, and F. Sarro, “The Plastic
Surgery Hypothesis,” in Proc. of FSE2014.
[4] S. Mechtaev, J. Yi, and A. Roychoudhury, “Angelix: Scalable Multiline
Program Patch Synthesis via Symbolic Analysis,” in Proc. of ICSE2016.
[5] J. Xuan, M. Martinez, F. DeMarco, M. Clement, S. L. Marcote,T. Durieux, D. Le Berre, and M. Monperrus, “Nopol: Automatic Repairof Conditional Statement Bugs in Java Programs,” IEEE TSE2017.
[6] M. Martinez and M. Monperrus, “ASTOR: A Program Repair Libraryfor Java,” in Proc. of ISSTA2016.
[7] R. Abreu, P. Zoeteweij, and A. J. C. van Gemund, “On the Accuracy of Spectrum-based Fault Localization,” in Proc. of TAICPRTMUTATION2007.
[8] C. L. G. Xuan-Bach D. Le, David Lo, “History driven program repair,”in Proceedings of SANER2016.
[9] M. Wen, J. Chen, R. Wu, D. Hao, and S.-C. Cheung, “Context-aware
Patch Generation for Better Automated Program Repair,” in Proc. ofICSE2018.

III. M ODIFICATION E XAMPLE
Figures 1(a) and 1(b) are a simple faulty program and its
test cases that are attached to the package of kGenProg. Thisprogram takes an integer value as input and outputs an integer
value that is close to zero by 1. A fault is exposed by thesecond test case in Figure 1(b). If we input the faulty program
and the test cases to kGenProg, it outputs a patch shown inFigure 1(c) within a second.
Moreover, kGenProg has a command line option for thenumber of patches to generate. If we set this option to100, kGenProg generates 100 different patches for this faulty
program within a minute.

698