Toward Eﬃcient Code Clone Detection on Grid Environment
Yuki Manabe††Yoshiki Higo†

Graduate School of Information Science and Technology, Osaka University
1-3 Machikaneyama, Toyonaka, Osaka 560-8531, Japan{y-manabe, higo, inoue}@ist.osaka-u.ac.jp
Abstract

Code clone detection technique originally was developed for investigating duplicated code in a single software system or between two or three ones. If it canbe applied to a large amount set of software systems,
we should identify useful duplicate in it. This paper
describes how we are going to scale up code clone detection technique for handling many software systems.

together.
In order to satisfy this requirement, we are trying
to applying existing code clone detection technique ingrid environment. We have already implemented DCCFinder, which is a code clone detection system in a
distributed environment [4], and have conducted casestudies on a large set of software systems [3]. But, we
believe that grid-based CCFinder can achieve furtherusability, portability, and scalability.

21Katsuro Inoue†

Introduction and Motivation

Recently, code clone detection technique attracts
much attention. A code clone is a code fragment having
code fragments identical or similar to it in the sourcecode. It is widely accepted that automated code clone
detection can help software development and maintenance. For example, in the debugging process, code
clone detection prevents us from overlooking some ofcode fragments simultaneously.
In oﬀshore developments, diﬀerent teams tend tocreate similar libraries independently because of thelack of inter-team communication. For eﬃcient oﬀshoredevelopment, developers in diﬀerent teams shouldshare these libraries. Duplicated functions (Codeclones) between existing software systems will be required by software systems under development or ones
developed in the future. In other words, Code clones
between existing software systems should be useful libraries for future developments.
However, there is a big problem in applying code
clone detection technique to a large set of softwaresystems; the scalability of code clone detection is notenough. Since, code clone detection technique was originally developed for investigating duplicated code in asingle software system, or catching plagiarism between
two or three software systems. We need to handle hundreds of software systems (billions lines of code) all

Code Clone Detection on Grid Environment

This section describes our prototype of a code clone
detection system on grid environment. Our systemcomprises a single master node and many slave nodes
working on OurGrid [1], which is one of the popular
grid middleware systems. Fig 1 shows the relation between the master node and slave nodes.
The following describes the code clone detection process of our system. The numbers in the process boxesof Fig 1 correspond to the following items.
1. The master node receives target source ﬁles, anddivides them into groups that include a speciﬁednumber of the source ﬁles. Fig 2 illustrates therelation between source ﬁles, software and groups.
2. The master node sends a pair of the groups to an
idle slave node.
3. A slave node detects code clones from the assigned
pair using CCFinder [2].
4. The slave node returns the detection result to themaster node.
5. After detecting code clones all the pair of thegroups, the master node merges the detection results as a single detection result.

clones intarget files

target files
1. divide
MasterNode

5. merge
clones in
the groups

groups
2. send

3.2

4. collecta pair ofgroups

Slave
Nodes

kinds of functions. If we could identify duplicated functions, the duplicated functions may be able to be usefullibraries. Creating useful libraries can prevent the department from writing the same kinds of code in thefuture, and can reduce the development cost.

Code clone detection from a large set of softwaresystems is able to catch license violations of sourcecode. For example, if we write source code based on
GPL’ed software, the source code must be licensed under GPL. If many code clones are detected between
GPL’ed source code and non-GPL’ed source code, nonGPL’ed source code may violate the GPL license.

clones in
3. CCFinder the groups

process:data:

Catching licensing violations of sourcecodedata flow:

4
Figure 1. Relation between the master nodeand slave nodes

Conclusion

In this paper, we describe code clone detection on
grid environment for handling a large set of softwaresystems and also discussed its applications.

a pair of groups

Acknowledgements

group iclones in
the groups

CCFindergroup jgroups

1

output

input

2

ijn

source files
softwareAB

N

Figure 2. Relation between source ﬁles, software and groups

In order to detect code clones in a large ﬁle set
quickly, we need a method to merge slave node’s detection results eﬃciently.

3Applications

At present, we are developing a system running on
the grid environment, and so have no case study. The
remainder of this section describes some assumed applications of our developing tool.

3.1Creating useful libraries

It may be possible that a single software development department in diﬀerent projects or software develop departments in a same project develop the sameThis work is being conducted as a part of EASE
Project, Comprehensive Development of e-Society
Foundation Software Program, and Grant-in-Aid for
Exploratory Research(186500006), both supported by
Ministry of Education, Culture, Sports, Science andTechnology of Japan. Also it is being performed under Grant-in-Aid for Scientiﬁc Research (A)(17200001)
supported by Japan Society for the Promotion of Science.

References[1] Ourgrid. http://www.ourgrid.org/.
[2] T. Kamiya, S. Kusumoto, and K. Inoue. Ccﬁnder: Amulti-linguistic token-based code clone detection system for large scale source code. IEEE Transactions onSoftware Engineering, 28(7):654–670, Jul 2002.
[3] S. Livieri, Y. Higo, M. Matsushita, and K. Inoue. Analysis of the linux kernel evolution using code clone coverage. In Proc. of the 4th Workshop on Mining Software
Repositories, pages 22.1–22.4, May 2007.
[4] S. Livieri, Y. Higo, M. Matsushita, and K. Inoue. Verylarge scale code clone analysis and visualization of open
source program using distributed ccﬁnder: D-ccﬁnder.
In Proc. of the 29th International Conference on Software Engineering, pages 106–115, May 2007.