社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,
INFORMATION AND COMMUNICATION ENGINEERS

信学技報
TECHNICAL REPORT OF IEICE.

A Clone Detection Approach for a Collectionof Similar Large-Scale Software Products
Eunjong CHOI† , Norihiro YOSHIDA†† , Yoshiki HIGO† , and Katsuro INOUE†† Graduate School of Information Science and Technology, Osaka University
Yamadaoka 1–5, Suita-shi, Osaka, 565–0871 Japan†† Graduate School of Information Science, Nara Institute of Science and Technology
Takayama-cho 8916–5, Ikoma-shi, Nara, 630–0192 Japan
E-mail: †{ejchoi,higo,inoue}@ist.osaka-u.ac.jp, ††yoshida@is.naist.jp
Abstract Reusing existing software with or without modifications is frequently occurred to develop new large
software at low cost with high quality. So far, many techniques and tools have been proposed for detecting reusedpieces in source code. However, existing tools have low scalability; they spend lots of memory and time to detect
reused pieces on large-scale software. In this paper, we proposed an approach for detecting reused files as well as
reused code fragments, code clones for a collection of similar large-scale software products. For the case study, weapplied our approach to three OSS projects and compared code clone detection time between only using CCFinderand our approach. We found that our approach takes shorter time to detect code clones.
Key words hasing, code clone, open source system

1. Introduction

FreeBSD Ports Collection in 17.16 hours with a single workstation and investigated characteristics of them. However,

Software reuse, using existing software with or without

the goal of this study is not detecting code clones or reused

modifications during the construction of a new software sys-

files but investigating characteristics of sets of reused files.

tem, is frequently occurred to develop large-scale software atThis paper suggests an approach for detecting code clones

low cost with high quality. However, in some ways, these

for a collection of similar large-scale software products. Ourreused pieces occur annoying problems because if a defectapproach is similar to previous study; We also compute hashis found in a reused piece, all of its same pieces should bevalues of files to detect reused files. However, this study ischecked for the same defect. This task takes a lot of time

diﬀerent from the previous study on following two aspects

and eﬀort, especially in large-scale software.

(1) the outputs of our approach are not only reused code

Detecting and managing reused pieces in software is im-

fragments, code clones but also reused file. (2) we only de-portant for not only detecting bugs but also understand-tected sets of files that are reused in other collections without

ing code quality, plagiarism detection, copyright infringe-

modifications.

ment investigation. Many tools have been proposed for de-

To detect code clones, we use CCFinder which detects code

tecting reused pieces in software at code fragment level, so

clones on token-base [7]. As case study, we compare clone

called code clones [5], [6], [7]. However, existing clone detec-

detection time between using our proposed approaches andtion tools have a low scalability, these tools take numerous

only using CCFinder in three Open Source Software (OSS)

times and memory to detect code clones on large-scale of soft-

projects. As a result of the case study, we found that ourware. To overcome this limitation, several tools have been

approach is much faster than only using CCFinder to detect

proposed and implemented but their scalability is still notcode clones on large-scale software.

high.

The rest of this paper is organized as follows. Section

In case of detecting reused files, our previous study sug-

2. explains the background of this study, definition of code

gested an approach for detecting reused file without any (orclone and its related terms, and CCFinder, a token-based code

just slight) modifications in comments or headers on large-

clone detection tool. Section 3. explains our approach. Sec-

scale software [12]. We used hash computation of the tok-tion 4. describes the case study and its results. Section 5.

enized files and implemented a tool named FCFinder (Fileexplains related work. Section 6. summarizes this paper andClone Finder). In case study, we detected reused files in thediscusses future work.
—1—formed, (i.e., tokens are added, removed, or changed based

2. Backgroundon the transformation rules) and then, each identifier relatedThis section explains definition of code clone and its re-to types, variables, and constants is replaced with a special

lated terms, CCFinder, a token-based code clone detection

token. This replacement makes code portions with diﬀerent

tool, to give a clear understanding of this study.

variable names to become clone pairs. At the same time, the2. 1 Code Clone

mapping information from the transformed token sequence

A code clone is a code fragment that has lexically, syntacti-

into the original token sequences is stored for the formatting

cally, or semantically similar code fragments in source code.

step which comes later.

Code clones are created because a programmer sometimes（ 3 ） Match Detection. From all the substrings on theintentionally reuses existing code when she develops a newtransformed token sequence, equivalent pairs are detected as

hardware drivers, or new platforms to improve the maintain-

clone pairs. A suﬃx-tree matching algorithm [3] is used toability of source code. Meanwhile, she unintentionally cre-compute matching, in which the clone location information

ates code clones due to programming idioms or algorithmic

is represented as a tree with sharing nodes for leading iden-

idioms [8]. Many code clones are contained in software sys-tical subsequences and the clone detection is performed bytems. In large-scale software, 13 - 20 percent of code clones

searching the leading nodes on the tree.
（ 4 ） Formatting. Each location of clone pair is con-are contained [1].
Code clones are categorized following types base on the

Moreover, if the total size of source files is too large to build

similarity of text [2]:Type 1:verted into line numbers on the original source files.

Identical code fragments except for variations ina single suﬃx-tree on primary store, it provides a ‘divide andwhitespace, layout and comments.

conquer’ approach. The input source files are divided into

Type 2:

Syntactically identical fragments except for vari-disjoint subsets. For each pair of the subsets, a sub suﬃx-

ations in identifiers, literals, types, whitespace, layout andtree is built to extract clone-pairs. The total collection ofcomments.

clone-pairs is the final output. However, it still takes nu-

Type 3:

Copied fragments with further modifications suchas changed, added or removed statements, in addition tovariations in identifiers, literals, types, whitespace, layout
and comments.

merous time to detect code clones on large-scale software,
especially in building and matching suﬃx-tree.

3. Proposed Approach

We call a pair of code cones as a Clone Pair and a set of

The overview of this approach is described in Figure 1. At

code clones that are identical or similar to each other as afirst, hash values of input files are created. Then two cate-

Clone Set.

gories, identical file sets (i.e.. sets of files that are identical

2. 2 CCFinder

each other), and target files are created. Then, code clones

Many studies suggested code clone detection technics

on target files are detected. Finally, overall clone sets are cre-and its implemented tool [4], [5], [6], [7], [10]. Between them,ated by matching detected clone sets and identical file sets.

token-based techniques have high the recall and scalabil-This approach takes a source files as an input and outputs

ity [2], [9]. One of the famous token-based code clone de-overall clone sets and identical file sets. We will explain eachtection tools is CCFinder which is developed by Kamiya etstep with an example of input files Fi = {F1 , F2 , F3 , · · · , Fn }.

al [7]. It takes a source files as an input and outputs clone（ 1 ） Calculate MD5 Hash. This step creates input

pairs information. It can report Type 1 and Type 2 clones

files’ MD5 hash values [11]. We select MD5 as a hash func-

in several languages (e.g. C, C++, Java, COBOL).

tion because it does not require any large substitution tables

The process of CCFinder consists of following four steps:

can be coded quite compactly. Let us assume that as a re-（ 1 ） Lexical Analysis. Each line of source files is di-vided into tokens corresponding to a lexical rule of the pro-sult of input files F’s MD5 hash computations we obtain aset of hash values H = {Ha , Ha , Hb , · · · , Hk } (k <= n). This

gramming language. The tokens of all source files are con-means that MD5 hash values of files F1 , F2 are the same.

catenated into a single token sequence, so that finding clones

Meanwhile, file F3 has unique MD5 hash value.

in multiple files is performed in the same way as single file（ 2 ） Formatting. In this step, a hash table is createdanalysis. At this step, the white spaces (including “\n” andwith calculated MD5 hash values as keys and its correspond-“\t” and comments) between tokens are removed from theing sets of file as values. If files have same MD5 hash value,

token sequence, but those characters are sent to the format-

they are added to the same value as a set. For example, files

ting step to reconstruct the original source file.

F1 , F2 have Ha as a MD5 hash value, they are added as val-

（ 2 ） Transformation.

ues in hash table whose hash key is Ha . Meanwhile, file F3

The token sequence is trans-—2—Sourcefiles(1) Calculate
MD5 HashHashedfiles(2) Create
Each Set

Targetfiles(3) Detect
Code Clones

Clone
sets

(4) Match
Clone
Information

All clonesets

Identical
file sets

Figure 1 An overview of our research

path is added as a value in a hash table whose hash key is

as code clone cβ in file F1 . Let us assume that code clones

Hb .

in the file F2 is cγ , then, contains code clone cβ , Therefore,（ 3 ） Create Each Set. This step creates target files T

code clone cγ is added to the same clone set where code clone

and identical file sets SI based on the information on a hashcβ is contained. All clone sets C consits of {cα , cβ , cγ · · ·}table. At first, a number of each MD5 hash value in hashtable is checked; If the number of MD5 hash value is more

4. Case Study

than two, their corresponding key in the hash table is added

In case study, we detected code clone on three large-scale

to target files T. Meanwhile, if the number of value is one,

open source software(OSS) projects using our approach andits corresponding key of the hash table is added to identical

only using CCFinder. We used 30 tokens as the minimum

file sets SI. In addition, the first file of each identical file set

length of token sequence of a code clone to CCFinder in bothis added to target files T . This added file will be used in theapproaches. The goal of this case study is to compare code

later step.

clone detection time between our approach and only using

In example, first, files F1 , F2 are added to identical file sets
SI and file F3 is added to target files T. In this situation,
each set contains following files;•

Identical file set SI = {F1 , F2 , · · ·}•Target files T = {F3 , · · ·}Next, F1 ,the first file of each identical file set, is added totarget files. Therefore, final sets contains following files:

CCFinder.
This case study was performed on a 64 bits Windows 7
Professional workstation equipped with 2 processor, 2.67GHz
and 2.66GHx CPUs and 24 gigabytes of main memory.
4. 1 Target System
A summary about the target systems is described in Table
1. We selected three OSS projects, Apache Ant（ 1）, Linux ker-•

Identical file set SI = {F1 , F2 , · · ·}nel（ 2） and GT-B5510 model（ 3）. Apache Ant is a Java library•

Target files T = {F3 , F1 , · · ·}and command-line tool whose mission is to drive processes（ 4 ） Detect Code Clones. A clone set on target files T

described in build files as targets and extension points de-are detected in this step. To detect code clones, we selected

pendent upon each other. We selected only java files in the

CCFinder as a code clone detection tool because it detects

src/main directory from 16 sequence versions (1.5.2-1.8.4).

code clones with high speed. Moreover, it has high accuracy

Linux kernel is a clone of the operating system Unix, writ-for detecting code clones. In example, let us assume that aten from scratch by Linus Torvalds with assistance from aclone set C = {cα , cβ , · · ·} are detected from target files T =loosely-knit team of hackers across the Net. It originally de-{F3 , F1 , · · ·}.

veloped first for 32-bit x86-based PCs (386 or higher), now,（ 5 ） Match Cone Information. This step creates all

it supports multiple architectures(e.g. AMD x86-64, IBMclone sets by matching detected clone sets on added file that

S/390).We selected only c files in the fs directory from 12

is the first file of each identical file set and identical file set SI.

sequence versions (2.6.0-2.6.10). GT-B5510 model is a Sam-assure that that because the files in the same set of identicalsung mobile phone, Samsung Galaxy Y Pro. We selected

files are exact each other, the location of clone of each file

three versions of this model for diﬀerent countries, Euro,should be located in the same location. Therefore, if code

Brazil and China. We selected only c files in the kernel di-clone are detected on the first file of each identical file set, werectory.

added the code fragments in other files of the same identical

4. 2 Result and Discussion

file set to the same clone set.

Target files and identical file sets are created after “Creat-

In example, code clone cβ is detected on file F1 in previous
step. Because files F1 , F2 are identical each other, we sure

（ 1）
：http://ant.apache.org/

that code clone is also located in file F2 in the same location（ 2）：http://www.kernel.org/（ 3）：http://opensource.samsung.com/index.jsp—3—

Table 1 Target Systems
Project Name

project project. Then, we use the output of CCFinder from

Language #Files Lines Of CodeApache ant

Java

11,393

2,971,948

Linux kernel

C

10,673

6,191,838

GT-B5510 modelC

86,986

41,982,594

the same projects. We found that all selected clone sets arealso detected by only using CCFinder.
We also selected 30 identical file sets from each OSS
project. We manually checked all of them and found thatfiles in the same identical file sets are really identical eaching Each Set” Step. The number of created target files andother.

identical file sets are shown in Table 2. The colum Identical Files represents the information of detected identical file

5. Related Work

sets. Apach ant contains 3,083 sets of identical files. Overall

Many technique and its implemented tools have been pro-number of identical files is 8,667 and they are 76.1 percent ofposed for detecting code clones on large-scale software.

input source files. Linux kernel contains 1,967 sets of identi-

Baker proposed a tool named Dup to detect text-based andcal files. Overall number of identical files is 9,712 and theyline based code clones [1]. Dup ignores comments, indenta-

are 91.0 percent of input source files. GT-B5510 model con-tion and white space. It detects exactly same clone pairs

tains 28,181 sets of identical files. Overall number of identicalor parameterized match code fragments (i.e., code fragments

files is 9,712 and they are 99.8 percent of input source files.

that are comprised of neighboring sequences of source lines

Between them, GT-B5510 model contains the most identi-

and variable names or structures member in one code frag-cal files. We assume that this is because many of files arement are consistently changed into other code fragment). sf

reused in GT-B5510 model and only specific functions for

Dup found 20 percent matches of lenght at least 30 lines oneach country are implemented.

the Window System subsystem (SS) which has almos 1.1M

The number of detected clone sets by our approach arelines.. The cpu time of SS was 7.9 minutes on the SS withalso shown in Table 3. 10,692, 21,343 and 148,761 clone sets

one 40MHz R3000 processor (primary I and D cache 64KB,

were detected from Apache ant, Linex kernel, and GT-B5510

secondary 1MB, main 256MB, SGI IRIX 4.1)

model, respectively as a result of our approach. The number

CP-Miner, proposed by Li et al. detects token-based codeof clone sets by only using CCFinder are also shown in Table

clones based on frequent subsequent mining which is an3.

association analysis technique to discover frequent subseHenceforth, We will discuss our results in terms of detec-

quences in a collection of sequences [10]. Enhanced algo-tion time and accuracy of results.

rithm, CloSpan [13] allows CP-Miner to tolerate one to two（ 1 ） Detection Time The code clone detection time ofstatement insertions, deletions, or modifications in copy-

only using CCFinder and our approach is described in Table

pasted code, ignoring an arbitrarily long diﬀerent code seg-

3. As shown in Table 3, in Apache ant, detection time of

ment that is unlikely to be copypasted code. CP-Miner foundCCFinder is 241 seconds. Meanwhile, detection time of our

190,000 and 150,000 copied code clones that account for 20-

approach was 89 seconds. Moreover, in Linux kernel and GT-

22 percent of the source code in Linux and FreeBSD within

B5510 model, the detection time of CCFinder was 1,119 and

20 minutes.

113,445 seconds, respectively. Meanwhile, the detection time

Hummel et al. proposed index-based code clone detectionof our approach was 168 and 113,445 seconds, respectively.

approach [5]. It detects Type 1 and Type 2 clones by using

In Linux kernel and GT-B5510 model, our approach de-

MD5 hash value to calculate hash values from normalized

tects code clones ten time faster than only using CCFinder.

statements for each input file and retrieving code clones from

We believe that our approach detects code clones faster, if

the databases where the hash values are stored. In the casethe scale of target system is more large.

study, 100 machines performed clone detection in 73 MLOC

（ 2 ） Accuracy of Results To determine accuracy ofof open source code in 36 minutes.

the results derived by our approach, we arbitrary selected 30
clone sets that are detected by our approach from each OSS

Table 3 Clone sets and detection time(seconds) from CCFinderand our approach.

Table 2 Target files and outputs for each OSS project
Project Name
Apache ant

Target Files

Identical Files#Files Lines of Code#Files # Sets

3,083

8,667

1,729,505

3,083

Linux kernel

2,928

2,383,758

9,712

1,967

GT-B5510 model

28,327

14,152,711

86,84028,181

Project Name

CCFinder#Clone Sets

Our approach
Time#Clone SetsTime

Apache ant

11,169241

10,692

89

Linux kernel

24,235

1,119

21,343

168

GT-B5510 model

325,274 113,445

148,761 11,902—4—

6. Summary and Future Work
[7]

In this paper, we suggest an approach for detecting code
clones on for a collection of similar large-scale software products. Our approach uses MD5 hash to find identical file sets

[8]and CCFinder to detect code clones. The input of this approach is source files and outputs are overall clone sets andidentical file sets. In case study, we applied our approach to[9]three OSS projects and compared code clone detection time
between only using CCFinder and our approach. We found[10]

that our approach takes shorter time to detect code clones.
There are a number of areas in which we would like toexpand upon this study. At first, our current approach suc-

[11]
[12]

cessfully detected reused identical file sets, but, it cannot
categorize files might be reused with slightly modification(i.e., change identifier name or comments) as identical files.
Therefore, we plan to improve our approach for detecting[13]

Scalable and accurate tree-based detection of code clones.
In Proc. of ICSE, pages 96–105, May 2007.
T. Kamiya, S. Kusumoto, and K. Inoue. CCFinder: A
multilinguistic token-based code clone detection system
for large scale source code. IEEE Trans. Softw. Eng.,
28(7):654–670, 2002.
C. J. Kapser and M. W. Godfrey. “cloning considered harmful” considered harmful: patterns of cloning in software.
Empir Software Eng, 13(6):645–692, 2008.
R. Koschke, R. Falke, and P. Frenzel. Clone detection using abstract syntax suﬃx trees. In Proc. of WCRE, pages
253–262, October 2006.
Z. Li, S. Lu, S. Myagmar, and Y. Zhou. CP-Miner: Finding copy-paste and related bugs in large-scale software code.
IEEE Trans. Softw. Eng., 32(3):176–192, 2006.
R. L. Rivest. The MD5 message digest algorithm. Internet
RFC 1321, April 1992.
Y. Sasaki, T. Yamamoto, Y. Hayase, and K. Inoue. Finding file clones in freebsd ports collection. In Proc. of MSR,
pages 102–105, May 2010.
X. Yan, J. Han, and R. Afshar. CloSpan: Mining Closed
Sequential Patterns in Large Datasets. In Proc. SIAM Int’l
Conf. Data Mining, pages 166–177, May 2003.

reused files with slightly modification as identical file sets.
Although we applied our approach to three OSS projects
and we found that our approach faster than CCFinder to detect code clones in large-scale software. The result might bechanged to other software projects. Therefore, we plant toapply our approach to various size of software in diﬀerent
domains.
Finally, our approach uses CCFinder to detect code clones
and we compared our approach with only CCFinder in thecase study in this paper. Using other code cloning detection
tools might be eﬃcient than CCFinder in detecting large-scale
software and the result of case study also might be changed if
we compare other tools. We believe that CCFinder is appropriate for detecting code clones on large-scale software, but
we consider introducing other code clones detection tools andcompare results from them in the case study.

7. Acknowledgments
This work is partially supported by JSPS, Grant-in-Aid
for Scientific Research (A) (21240002).
References[1] B. S. Baker. On finding duplication and near-duplicationin large software systems. In Proc. of WCRE, pages 86–95,
July 1995.
[2] S. Bellon, R. Koschke, G. Antoniol, J. Krinke, and E. Merlo.
Comparison and evaluation of clone detection tools. IEEE
Trans. Softw. Eng., 33(9):577–591, 2007.
[3] D. Gusfield. Algorithms on strings, trees, and sequences:computer science and computational biology. Cambridge
University Press, 1997.
[4] Y. Higo, Y. Ueda, M. Nishino, and S. Kusumoto. Incremental code clone detection: A PDG-based approach. In Proc.
of WCRE, pages 3–12, October 2011.
[5] B. Hummel, E. Juergens, L. Heinemann, and M. Conradt.
Index-based code clone detection: incremental, distributed,
scalable. In Proc. of ICSM, pages 1–9, September 2010.
[6] L. Jiang, G. Misherghi, Z. Su, and S. Glondu. DECKARD:—5—