GenProg Meets Cluster Computing
Junnosuke Matsumoto, Yoshiki Higo, Hiroyuki Matsuo,
Ryo Arima, Shinsukue Matsumoto and Shinji Kusumoto
Graduate School of Information Science and Technology, Osaka University, Japan{j-matumt, higo, h-matuo, r-arima, shinsuke, kusumoto}@ist.osaka-u.ac.jp

Abstract—GenProg is an automated program repair tool thatleverages genetic algorithm. In the repairing process of GenProg,a larger number of mutated programs are generated, built, andtested. If none of mutated programs passes all the test cases,
GenProg redos the loop of generation, build and test. The build
and test occupy over 90% of GenProg’s execution. In this paper,
we introduce our cluster-based GenProg, which builds and tests
in parallel with many computers. We have implemented thecluster-based GenProg with Kubernetes environment and applied
it to real bugs in Defects4J dataset. As a result, we confirmedthat the time required for program repair is reduced according
to the number of computers in the cluster.
Index Terms—automated program repair, GenProg, clustercomputinga cluster computing. In our proposed framework, unlimited
number of computers can be joined to the cluster as a nodeof compiling mutated programs and executing test cases forthem. We implemented our cluster computing in our IaaS
environment and we confirmed that our cluster computing
dramatically shortened the time required to find repaired
programs for real bugs in open source software.
II. T ERMINOLOGY
Herein, we introduce several terminologies used in thispaper.
A. Fault Localization

I. I NTRODUCTION
Software developers spend long time for debugging [1],[2]. A variety of research has been conducted to support
debugging. GenProg [3], which is an automated program
repair (in short, APR) tool, made a breakthough. It succeededin removing real bugs from OSS without any developer intervention [4]. GenProg leverage genetic algorithm to generate
a repaired program from a given faulty program. GenProg
generates some mutated programs and executes all given test
cases for each of them. If a mutated program passes all test
cases, the mutated program is returned as a repaired program.
If not, GenProg selects some of the mutated programs andthen, generates new mutated programs and executes test cases.
This loop (selection, generation, and execution) is repeateduntil finding a solution or reaching time limit or maximum
number of generations.
A serious issue in GenProg is its long execution time.
GenProg naturally takes long time to find a repaired program if
the loop is repeated many times. We run kGenProg1 [5], which
is a Java edition of GenProg, for bugs of Apache Commons
Math, so that we found that compiling mutated programs andexecuting test cases occupy over 90% of execution time. Long
execution time is a serious issue for practical use for bothpractioners who want to use GenProg on their projects andresearchers who want to improve GenProg.
In this paper, we propose to parallel compilation and test
execution to shorten GenProg’s execution time. However, a
simple parallelization in a single computer has a limited
capability for shortening execution time. Thus, we develop
a framework2 to execute compilation and test execution with
1 https://github.com/kusumotolab/kGenProg
2 https://github.com/kusumotolab/clustered-kGenProg

Fault localization is a technique to infer which lines of agiven program include the bug. APR techniques require fault
localization because they need to decide which lines to change.
In the context of APR, spectrum-based fault localization
technqiues are used. Several studies reported that Ochiai [6]outperforms other spectrum-based techniques [7].
B. GenProg
GenProg is an APR technqiue that leverages genetic algorithm [3]. Firstly, GenProg identifies suspicious lines by using
a fault localization technique. Secondly, GenProg generates
multiple mutated programs by changing the suspicious lines.
The program mutations include three operations: insertion,
deletion, and replacement. Thirdly, GenProg builds and executes given test cases for all the mutated programs. If amutated program succeeded in passing all the test cases,
GenProg outputs it as a repaired program. If not, GenProg
picks up some better programs and generate new mutatedprograms of the next generation. This processing is repeateduntil finding a repared program or reaching time limit ormaximum number of generations.
In the operations of insertion and replacement, GenProg
uses a program statement in a given program. Selecting
an operation and selecting a program statement in case of
insertion and repalcement are randomly decided.
C. kGenProg
kGenProg [5] is a Java implementation of GenProg. kGenProg has a high portability, only a single JAR file of kGenProg is required to repair target programs. kGenProg equips
interfaces for many operations such as fault localization andprogram mutation. Thus, kGenProg users easily add new features for such operations. kGenProg builds mutated programs

Buggy Program

Test Cases
kGenProg

Fault Localization

Cluster

Generation
Delegate
Build & Test

Build
Test
SelectionNozDelegate
Build & Test

Client

Test Results

Coordinator

Repaired?
Yes

Workers
Test Results

Repaired Program
Fig. 1. Overview
Apply an Edit Script,
Build and Test

kGenProgan Edit Script

an Edit Script

Client

Test Resultsand Coverages

an Edit Script
Coordinator

Test Resultsand Coverages

WorkerTest Resultsand Coverages

Fig. 2. The flow of a mutated programand execute test cases on memory to avoid file IO as much as
possible. kGenProg’s compilation is a differential one, which
is very effective for large programs.
D. Kubernetes
Kubernetes3 is a container orchestration system for automating application deployment, scaling, and management.
It works with a range of container tools, including Docker. To
utilize Kubernetes, we prepare a master node firstly, and thenwe register multiple computers to the master node. Kubernetes
distributes a Docker image container to each of the registeredcomputers and we can execute a program on them with only asingle command. Kubernetes monitors each of the registeredcomputers during program execution. If some errors happen
in a container of a registerd computer, Kubernetes dispose it
and launch a new container automatically.
3 http://kubernetes.io

III. P ROPOSED TECHNIQUE
To improve the performance of GenProg, we focus on
the build phase and the test phase that mainly impact theperformance. While multiple mutated programs can be built
and tested in parallel, if these phases are simply executed in
multiple threads in only a machine, the performance is limitedby the specification of the machine.
Thus, we implemented a tool that improves the performanceof GenProg by distributing its build phase and test phase.
Our tool runs on many computers that execute build and test.
Our tool is implemented as an extension of kGenProg [5]because it is easy to extract the build phase and test phasefrom kGenProg.
Figure 1 shows our tool’s overview. It consists of threenodes.
Client: the node is the implementation of the interface in
kGenProg that it is responsible for executing build

and test.
Worker: the node actually executes build and test.
Coordinator: the node has responsibility for relaying between the client and workers and balancing loads.
These nodes communicate with TCP/IP network.
Figure 2 shows the flow that kGenProg generates an edit
script (a set of editing actions), the client sends the edit script
to a worker via the coordinator and it receives the test results
and the coverages. The coverages are used in kGenProg todetermine which program statements are the targets of next
editing actions. kGenProg generates edit scripts from the input
program and sends each of them to a different worker. Then,each worker mutates the input program based on the edit
script that it received. Herein, the mutated program means
the program that the worker executes build and test. After
executing build and test, each worker sends the test results
and the coverages.
A. Communication between nodes

V

ClientCoordinator(1) Register

Setting Upa Cluster

Registering
a Project

Worker(s)(2) Send Files(3) Send Files(4) Notify Build
Completion(5) Notify Build
Completion

Repairinga Program(6) Sendan Edit Script

Figure 3 shows the communication flow.
(7) Sendan Edit Script(1) Registering a worker: when a worker is launched, it
notifies the coordinator of the IP and the port of theLoop(8) Return Test
worker, and the coordinator recognizes them.
Results & Coverages(2), (3) Sending files to the coordinator and the workers:
when kGenProg is launched, the client sends files to(9) Return Test
Results & Coverages
the registerd workers via the coordinator for build
and test.
(4), (5) Notifying build completion: the worker builds thereceived files and notifies the coordinator of build
completion. After receiving the notification from all
Fig. 3. The communication flow
workers, the coordinator notifies the client of build
completion.
(6), (7) Sending an edit script to the worker: after kGeC. Coordinator
nProg calculates an edit script, the client sends it to
A coordinator is a node which relays from the client tothe coordinator. The coordinator relays the received
workers
which execute build and test. The coordinator does
edit script to an idle worker.
thefollowings:(8), (9) Returning the test results and the coverages:
the worker mutates the program based on the re• registering workers ((1) in Figure 3),
ceived edit script, and then, it builds and tests the• registering a project ((2)∼(5) in Figure 3), andmutated program. The worker returns the test results• receiving a delegation for build and test ((6)∼(9) inand the coverages to the coordinator, and then, theFigure 3).
coordinator relays the received test results and the1) Registering workers: The coordinator always receives acoverages to the client.
request for registering a worker. After receiving a notification
The flow of (6)∼(9) is executed in parallel. kGenProg calcu- which a worker has been launched, the coordinator connects
lates edit scripts and iterates the loop of (6)∼(9) until finding to the worker.
a solution.
2) Registering a project: The coordinator always receives arequest for registering a project. The coordinator provides an
B. Client
ID to a given project, and the coordinator sends the binary andA client is imported to kGenProg as a strategy which ID to all registered workers. After receiving responses from all
executes build and test. kGenProg delegates build and test to workers, the coordinator returns the project ID to the client.
The coordinator keeps the pair of the binary and the ID,
the client. The client uses the following information: (a) files
required to build and test target projects, and (b) edit scripts. because a new worker may be registered after registering
The client compresses the files, which are necessary for build projects.
and test, to a zip file, and the client sends the binary to the3) Receiving a delegation for build and test: The coordicoordinator.
nator receives a delegation for build and test from the client.

The coordinator receives a request which contains a project
ID and an edit script from the client and sends the request to
an idle worker.
The requests from the client are kept in the coordinator.
The coordinator manages which worker is delegated build andtest, and sends the next request to a worker which has finishedbuild and test. If a worker halts unexpectedly, another worker
is delegated.

# launch a coordinator$ coordinator −−port 50051# launch a worker (as many as you want)$ worker −−host <Coordinator IP> −−port 50051# launch kGenProg with a client$ client −−host <Coordinator IP> −−port 50051 \−−kgp−args ’−−config kGP.toml’(a) launching nodes manually

D. Worker
A worker is a node which actually executes build and test.
The coordinator sends a project ID and an edit script to aworker. The worker mutates the project based on the edit scriptand executes build and test. All files in the project are built at
first build, after this, only edited files are built.
After finishing the build and test, the worker sends thetest results and the coverages to the coordinator. The reason
why the worker sends the coverages is that the coverages arenecessary for the fault localization in kGenProg.

# in k8s master node
$ kubectl apply −f kubernetes/deploy.yml# launch kGenProg with a client$ client −−host <k8s master IP> −−port 50051 \−−kgp−args ’−−config kGP.toml’(b) launching nodes with k8s
Fig. 4. The command that launches our tool

E. Deployment

IV. E VALUATION

While we can launch each node one by one, the moreworkers is launched the more difficult it is to manage all nodes.
Thus, our tool adopts k8s for the deployment. We prepared
the Docker images for the coordinator and the workers. By
editing the configuration file of k8s, a user can easily change
the configuration of the coordinator and the workers (e.g., thenumber of workers, the specification of each node). k8s checks
the status of each worker. If a worker unexpectedly exits (e.g.,out of memory, network error), the container is restarted by
k8s automatically, and the worker connects to the coordinatoragain soon. Our tool can always keep the number of workers
which a user wants.
F. How to Use
Figure 4 (a) shows an example of the command which
launches our tool manually without k8s. At first, a user
launches a coordinator. The user launches a worker, and then,the user registers the worker to the coordinator. The user has
to execute the command which launches a worker as many as
the user wants.
By using k8s, the user can more easily launch our tool.
Figure 4 (b) shows the commands. After setting up k8s, theuser can set up a cluster only by executing one command.
deploy.yml has information about the cluster (e.g., the numberof workers, the specification of each node, the port of thecoordinator). If the user wants to increase the number ofworkers, all the user has to do are only modifying the files
and executing the command.

TABLE IT HE SPECIFICATIONS OF EACH NODENode
kGenProg ( including Client)
Coordinator
WorkerCPU
2
2
1

Memory
32GB
16GB
6GB

We evaluate the performance of our tool by applying it
to OSS. We expect that the performance of our tool can be
improved by adding workers. Thus, the purpose of this experiment is that we confirm how the performance is improved byadding the workers.
A. Dataset
We use the Apache Commons Math (in short, Math) included in Defects4J [8] for the evaluation. Defects4J is adataset which contains information of real bugs occurred in
the development of some projects. Math has 106 bugs. The
main reason why we use Math is that it is used as benchmarks
in many papers of APR [9], [10].
B. Environment
In the experiment, six IaaS servers were used. Each IaaS
server has 12 CPUs and 100GB memories, and all the IaaS
servers are connected to the same LAN.
We launched the virtual machines which has specifications
as much as their IaaS servers. The virtual machines wereregistered k8s as a slave node. A coordinator and workers
were launched in the k8s.
Table I shows each node specification. The client is imported to kGenProg, thus, the table shows the specification of
kGenProg and the client.
C. Configuration
We expect that the more workers are added the more
the performance is improved. Thus, in the experiment, we
compared the performances of stand-alone kGenProg (in short,SA) and our tool when 1, 4, 16 and 32 workers were launched.
Our tool distributes build and test in a generation. We
considered that, when the number of workers in a generation
is low, our tool cannot evaluate enough because the advantage
of distributing build and test is not large. Thus, we set 1,000

2,000300,000
1,750
250,000

mutated programs

1,500

time(s)

1,250

1,000

750

200,000

150,000

100,000
500
50,000250

0kGenProg

1

4

16

32

0

kGenProg

workers

1

4

16

32

workers(a) Execution time(b) # mutated programs
Fig. 5. The results of the experimentas the number which kGenProg generates programs in a
generation.
The time limitation for each bug was set 30 minutes, themaximum generation was set unlimited and the termination
condition was set time out or finding a solution.
D. Results
Table II shows the number of found solutions according to
the number of workers. In the case that multiple workers werelaunched, the more bugs were repaired than the case of SA.
Figure 5(a) shows the execution time in the case that
kGenProg found a solution with any of SA and 1 ∼ 32
workers. The time of 4 workers is shorter than the time of
1 worker and the time of 16 workers is shorter than the timeof 4 workers. The reason why the time of 32 workers is longer
than the time of 16 workers is that the client takes longer timeto send the project files to more workers.
Generating more mutated programs increases the possibilityof finding a solution. Thus, the number of mutated programs isessential. Figure 5 (b) shows the number of mutated programsin the case of time out. The number of mutated programs
generated by 4 workers is higher than 1 worker and the numberof mutated programs generated by 16 workers is higher than
the 4 workers. The reason why the performances of 16 workers
and 32 workers do not change significantly is that the ratio
of non-distributed processing gets larger, and the effect of
distributing build and test gets smaller.
V. T HREATS TO VALIDITY
Each node can also communicate with others via a global
network. In such a situation, we expect the performance will

TABLE II
T HE NUMBER OF SOLUTIONS WHICH K G EN P ROG FOUNDSA
25

1 worker
29

4 workers
36

16 workers
36

32 workers
36

be lower than the measured performance. However, we do
not know the impact because we have not measured theperformance in such a situation.
kGenProg mutates a program based on a random seed. In theexperiment, we used only one seed. Thus if we used multiple
difference seeds, the results (the performance and the numberof solutions) will be changed.
VI. D ISCUSSION
In this paper, we mainly presented our tool, which distributes the builds and the tests. On the other hand, our tool
does not execute the other phases (e.g., the generation phase)in parallel. It is not realistic to parallelly execute such phases
in kGenProg due to its architecture. For example, in the case of
the generation phase, the reason is that kGenProg remembers
all mutated programs to avoid generating the same mutatedprograms, and so, the order that kGenProg mutates programs
is important.
However, this is an implementation problem of kGenProg.
While we adopted kGenProg because it is easy to distributethe builds and tests that mainly impact the performance, theother implementations of GenProg may be able to execute thefault localization and the generation in parallel. We consider
that the selection cannot be executed in parallel regardless of
the implementation of GenProg, because GenProg selects afixed number of programs from many mutated programs.
VII. R ELATED W ORK
Claire Le Goues et al. [11] proposed a technique which
executes GenProg in parallel using cloud computing resource.
However, the technique simply executes GenProg in parallelusing different random seeds. Thus, the tool generates thesame mutated programs many times between different random
seeds, and the performance per a single random seed is not
improved. Since our technique executes kGenProg in parallelusing a single random seed, the performance per a single
random seed is improved.

VIII. C ONCLUSION
We proposed a tool which improves the performance of
GenProg. Our tool improves the performance by distributing
the build and test. By applying the tool to open source
software, we confirmed that multiple workers improve theperformance than a single worker.
As future work, we will propose more intelligent mutationby using our tool. While GenProg mutates programs perstatement, our tool can mutate programs per node of abstract
syntax tree because the number of programs which our tool
can build and test is larger than the one of GenProg within
the same time.
ACKNOWLEDGMENT
This work was supported by MEXT/JSPS KAKENHI
17H01725.
R EFERENCES[1] T. Britton, L. Jeng, G. Carver, P. Cheak, and T. Katzenellenbogen,“Reversible debugging software - quantify the time and cost saved using
reversible debuggers,” 2013.
[2] B. Hailpern and P. Santhanam, “Software debugging, testing, andverification,” IBM Systems Journal, vol. 41, no. 1, pp. 4–12, 2002.
[3] W. Weimer, T. Nguyen, C. Le Goues, and S. Forrest, “Automaticallyfinding patches using genetic programming,” in In Proc. International
Conference on Software Engineering, 2009, pp. 364–374.
[4] 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 $8
each,” in In Proc. International Conference on Software Engineering,
2012, pp. 3–13.
[5] Y. Higo, S. Matsumoto, R. Arima, A. Tanikado, K. Naitou, J. Matsumoto, Y. Tomida, and S. Kusumoto, “kgenprog: A high-performance,high-extensibility and high-portability apr system,” in the 25th AsiaPacific Software Engineering Conference, 12 2018, pp. 697–698.
[6] A. da Silva, Meyer, A. Augusto, Franco Garcia, A. Pereira, de Souza,
and C. L. de Souza, Jr., “Comparison of similarity coefficients used forcluster analysis with dominant markers in maize (zea mays l),” Genetics
and Molecular Biology, vol. 27, no. 1, pp. 83–91, 2004.
[7] R. Abreu, P. Zoeteweij, R. Golsteijn, and A. J. C. van Gemund, “Apractical evaluation of spectrum-based fault localization,” Journal of
Systems and Software, vol. 82, no. 11, pp. 1780–1792, 2009.
[8] R. Just, D. Jalali, and M. D. Ernst, “Defects4J: A database of existingfaults to enable controlled testing studies for java programs,” in In Proc.
International Symposium on Software Testing and Analysis, 2014, pp.
437–440.
[9] M. Martinez, T. Durieux, R. Sommerard, J. Xuan, and M. Monperrus,“Automatic repair of real bugs in java: A large-scale experiment on thedefects4j dataset,” Springer Empirical Software Engineering, vol. 22,
no. 4, pp. 1936–1964, 2016.
[10] M. Martinez and M. Monperrus, “ASTOR: A program repair libraryfor java,” in In Proc. International Symposium on Software Testing andAnalysis, 2016, pp. 441–444.
[11] 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 $8
each,” in Proceedings of the 34th International Conference on Software
Engineering, ser. ICSE ’12. Piscataway, NJ, USA: IEEE Press, 2012,
pp. 3–13.