Extracting Code Clones for Refactoring
Using Combinations of Clone Metrics
Eunjong Choi1 , Norihiro Yoshida2 , Takashi Ishio1 , Katsuro Inoue1 , Tateki Sano3
1

2

Graduate School of Information Science and Technology, Osaka University, Japan{ejchoi, ishio, inoue}@ist.osaka-u.ac.jp
Graduate School of Information Science, Nara Institute of Science and Technology, Japan3

yoshida@is.naist.jp
Software Process Innovation and Standardization Division, NEC Corporation, Japant-sano@cp.jp.nec.com
ABSTRACT

1. INTRODUCTION

Code clone detection tools may report a large number ofcode clones, while software developers are interested in only
a subset of code clones that are relevant to software development tasks such as refactoring. Our research group has
supported many software developers with the code clone detection tool CCFinder and its GUI front-end Gemini. Gemini shows clone sets (i.e., a set of code clones identical orsimilar to each other) with several clone metrics including
their length and the number of code clones; however, it is
not clear how to use those metrics to extract interesting code
clones for developers. In this paper, we propose a method
combining clone metrics to extract code clones for refactoring activity. We have conducted an empirical study on a web
application developed by a Japanese software company. The
result indicates that combinations of simple clone metric is
more eﬀective to extract refactoring candidates in detectedcode clones than individual clone metric.

Many code clone detection tools[5, 6, 8] have been proposed to capture various aspects of source code similarity[11]. A code clone detection tool generally ﬁnds all sourcecode clones that match its own deﬁnition of code clone;
therefore, a tool may report a large number of code clones
for large scale software. On the other hand, software developers are interested in only the subset of code clones thatare relevant to their activities.
Refactoring[2] is one promising activity to improve themaintainability of code clones. Code clone is not always appropriate for refactoring because developers sometimes haveto repeatedly write code clones that cannot be merged due
to language limitations[4, 9, 10]. However, a clone set (i.e.,a set of code clones identical or similar to each other) indicates considerable opportunities for developers to merge
code clones into one or a few program units(e.g., Java methods) by refactoring[4, 9, 10].
In this research, we focus on code clones that should bechecked for refactoring before a software system is released.
Although code clones are not always appropriate for refactoring, developers would like to ﬁnd and modularize common functionalities in an important system because such asystem will be maintained in next 10 years as a part of theinfrastructure of a company. Due to the limited development time and cost, it is not acceptable for developers tomanually check all the code clones detected by a tool. We
propose a ﬁltering approach to extracting code clones forrefactoring from a large amount of code clones.
Our research group has developed a code clone analysis
tool named Gemini[3, 12]. Gemini is a GUI front-end for
CCFinder[8]; it takes as input a list of code clones generated
by CCFinder and shows developers quantitative information
on clone sets by clone metrics. Its clone metrics include LEN(the average LENgth of token sequences of code clones in aclone set[3]), POP (the POPulation of code clones in a cloneset), and RNR (the Ratio of Non-Repeated token sequencesof code clones in a clone set). Using these metrics, developers can extract a subset of code clones for their purpose.
However, little is known about how using these metrics whendevelopers extract interesting code clones for refactoring activity.
We have analyzed many industrial software and received
feedback from the developers. From these experiences, werecognized that clone sets extracted by a combination of

Categories and Subject Descriptors
D.2.7 [Software Engineering]: Distribution, Maintenance,and Enhancement—Restructuring, reverse engineering, andreengineering; D.2.8 [Software Engineering]: Metrics—
Product metrics

General Terms
Experimentation

Keywords
Code clone, Refactoring, Industrial case study

Permission to make digital or hard copies of all or part of this work for
Permission
to make digital
hard without
copies offeeallprovided
or part ofworkarefor
personal
or classroom
use is or
grantedthatthiscopiespersonal
or distributedclassroom for
useproﬁt
is granted
without fee
providedandthatthatcopiesarenotmade oror commercial
advantage
copiesnot thismadenoticeor distributed
forcitation
profit oroncommercial
advantagethat copies
bear
and the full
the ﬁrst page.
To copyand
otherwise,
tobear this notice
the fullor
citationon the first
page.requires
To copypriorotherwise,
republish,
to postandon servers
to redistributeto lists,
speciﬁcto
republish, to post on servers or to redistribute to lists, requires prior specificpermission
permissionand/or
and/oraafee.
fee.
IWSC
2011May
May23,
23,2011,2011, Waikiki,
Waikiki, Honolulu,
Hawaii, USA
IWSC’11,
HI, USA
Copyright
Copyright2011
2011ACMACM978-1-4503-0588-4/11/05
978-1-4503-0588-4/11/05...$10.00.
...$10.00

7Here, we give an example of the compute RNR(S)value. We assume that we detect code clones fromthree source ﬁles(F1 , F2 , F3 ). Each source ﬁle consistsof following ﬁve tokens. (Superscript * indicated thatthe token is in a repeated token sequence.)

multiple clone metrics are more appropriate for refactoring
than clone sets extracted by extremely higher values of individual clone metric. However, we have not evaluated whatmakes them relevant for refactoring. In this study, we evaluate clone sets extracted by a combination of clone metrics.
The contributions of this study are as follows.

F1 : a b c a b
F2 : c c∗ c∗ a b
F3 : c c∗ a b c• Using clone metrics, we propose a method to extract
refactoring candidate code clones from CCFinder’s output.
• We conﬁrm the eﬀectiveness of our method with a survey in the form of a questionnaire for a software developer in a company.

Here, we assume that at least two tokens are needed
to be identiﬁed as a code clone. With this assumption, the following two clone sets are detected fromthe source ﬁles. We use label C(Fi , j, k) to represent
a fragment. Fragment label C(Fi , j, k) starts at thej th token and ends at the k th token in source ﬁle Fi(j must be less than k ).)The rest of paper is organized as follows: Section 2 provides a brief description of Gemini. In Section 3, we describe
our proposed method. In Section 4, we describe a case study
and its results, and discuss threats to validity. In Section 5,
we present some related work. Section 6 concludes our paperwith ﬁnal remarks and indications about our future work.

2.

S1 : C(F1 , 1, 2), C(F1 , 4, 5), C(F2 , 4, 5), C(F3 , 3, 4)
S2 : C(F2 , 1, 2), C(F2 , 2, 3), C(F3 , 1, 2)

BACKGROUND

2.1 Code Clone Visualization Tool: Gemini

In this case, RNR(S) values are computed as following:

We have developed a GUI front-end for CCFinder[8], Gemini[3, 12]. CCFinder and Gemini are distributed to hundreds
of Japanese and international companies and universities.
Also, we have often analyzed industrial code clones with
Gemini through industry-university collaborations.
CCFinder detects a large number of code clones in large
scale systems. To support code clone analysis, Gemini has
several functionalities to extract clone sets from CCFinder’soutput. One major functionality of Gemini is the Metric
Graph. The Metric Graph visualizes the clone metrics andenables the user to select a part of the clone sets using clone
metrics. For example, POP(S) is a clone metric representing
the number of code clones in clone set S. If a user is interested in clone sets that appear in more than 5 locations, heor she can select the clone sets using a ﬁlter “POP(S) ≥ 5”.
Gemini supports clone metrics including LEN(S), RNR(S)and POP(S).

0+0+0+0) × 100 = 100
2+2+2+2
1+2+1) × 100 = 30
RN R(S2 ) = (1 −2+2+2
RN R(S1 ) = (1 −Here, we exaplain the clone sets whose RNR is higher,
and lower with Figure 1. 1
Higher RNR(S) values mean that each code clone ina clone set S consists of more non-repeated token sequences(Figure 1(a)). Contrary to this, lower RNR(S)values means that each code clone in a clone set S consists of more repeated token sequences(Figure 1(b)).
In most cases, repeated code sequences are involved inlanguage-dependent code clones (e.g., code clones thatinvolve consecutive if (or if-else) blocks, case entries ofswitch statements, consecutive variable declarations).

LEN(S)[3, 12] : LEN(S) is the average length of token
sequences of code clones in clone set S. Higher LEN(S)values mean that each code clone in a clone set S consists of more token sequences. Contrary to this, lower
LEN(S) values mean that each code clone in a clone
set S consists of less token sequences, and the size ofcode fragments are smaller.

POP(S)[3, 12] : POP(S) is the number of code clones ina clone set S. Higher POP(S) values mean that code
clones in a clone set appear more frequently in thesystem. Contrary to this, lower POP(S) values meanthat code clones in a clone set appear in fewer placesis the system.

RNR(S)[3] : RNR(S) is the ratio of non-repeated token
sequences of code clones in clone set S.
We assume that the clone set S includes n code clones,
c1 , c2 . . . , cn , LOSwhole (fi ) represents the Length Of
the whole token Sequence of code clone ci , and
LOSrepeated (fi ) represents the Length Of repeated token Sequence of code clone ci , then,0nX

The Metric Graph in Gemini is designed to enable theusers to quantitatively select clone sets. Here, we explain
the Metric Graph using Figure 2. In the Metric Graph,each clone metric has a parallel coordinate axis. The clone
set is shown by a polygonal line connecting clone metric values. Two lines for clone sets S1 and S2 show that LEN(S1 )and RNR(S1 ) are higher than LEN(S2 ) and RNR(S2 ), respectively, while POP(S1 ) is lower than POP(S2 ).
Users can specify the upper and lower limits of each clone
metric. The grey area shows the range bounded by clone
metrics upper and lower limits. In Figure 2(a), all the clone

1

LOSrepeated (ci ) C
B
C
B
i=1
C × 100
B
RN R(S) = B1 − nCXA@
LOSwhole (ci )1
The examples in Figure 1 are picked from Ant 1.7.0 since
the the subject source code used in Section 4. The sourcecode clones are similar to these examples.

i=18ŝĨ;ĂƐƐƵŵĞ:ĂǀĂϭϭ;ͿͿ΂WĂƚŚĐƉсŶĞǁWĂƚŚ;ƉƌŽũĞĐƚͿ͖WĂƚŚďƉ сŐĞƚŽŽƚůĂƐƐWĂƚŚ;Ϳ͖ŝĨ;ďƉ͘ƐŝǌĞ;ͿхϬͿ΂ĐƉ͘ĂƉƉĞŶĚ;ďƉͿ͖΃ŝĨ;ĞǆƚĚŝƌƐ ͊сŶƵůůͿ΂ĐƉ͘ĂĚĚǆƚĚŝƌƐ;ĞǆƚĚŝƌƐͿ͖΃ĐƉ͘ĂƉƉĞŶĚ;ĐůĂƐƐƉĂƚŚͿ͖ĐƉ͘ĂƉƉĞŶĚ;ƐŽƵƌĐĞƉĂƚŚͿ͖

S1

S1

S2

S2

LEN

RNR
(a) before(a) Code fragment in a clone set whose RNR(S) is 97, thehighest RNR(S) value in Ant 1.7.0.

Figure 2:GraphƉƌŝŶƚWƌŽƉĞƌƚǇ;ŽƵƚ͕WƌŽǆǇ^ĞƚƵƉ͘,ddWͺWZKyzͺWKZdͿ͖ƉƌŝŶƚWƌŽƉĞƌƚǇ;ŽƵƚ͕WƌŽǆǇ^ĞƚƵƉ͘,ddWͺWZKyzͺh^ZEDͿ͖ƉƌŝŶƚWƌŽƉĞƌƚǇ;ŽƵƚ͕WƌŽǆǇ^ĞƚƵƉ͘,ddWͺWZKyzͺW^^tKZͿ͖ƉƌŝŶƚWƌŽƉĞƌƚǇ;ŽƵƚ͕WƌŽǆǇ^ĞƚƵƉ͘,ddWͺEKEͺWZKyzͺ,K^d^Ϳ͖ƉƌŝŶƚWƌŽƉĞƌƚǇ;ŽƵƚ͕WƌŽǆǇ^ĞƚƵƉ͘,ddW^ͺWZKyzͺ,K^dͿ͖ƉƌŝŶƚWƌŽƉĞƌƚǇ;ŽƵƚ͕WƌŽǆǇ^ĞƚƵƉ͘,ddW^ͺWZKyzͺWKZdͿ͖ƉƌŝŶƚWƌŽƉĞƌƚǇ;ŽƵƚ͕WƌŽǆǇ^ĞƚƵƉ͘,ddW^ͺEKEͺWZKyzͺ,K^d^Ϳ͖ƉƌŝŶƚWƌŽƉĞƌƚǇ;ŽƵƚ͕WƌŽǆǇ^ĞƚƵƉ͘&dWͺWZKyzͺ,K^dͿ͖

POP

LEN

RNR

POP

(b) after

Filtering clone sets using the Metric

Clone sets whose LEN(S) is higher than others
As described in Section 2.1, clone sets whose LEN(S)is higher than other clone sets(Figure 3(a)) means thateach code clone in a clone set S consists of more token
sequences. However, in our observation, these clone
sets include many consecutive if (or if-else) blocks thatinvolve similar but diﬀerent conditional expressions.
Therefore, it takes eﬀort to perform refactoring thesecode clones.

(b) Code fragment in a clone set whose RNR(S) is 2, thelowest RNR(S) value in Ant 1.7.0.

Clone sets whose RNR(S) is higher than others
As described in Section 2.1, clone sets whose RNR(S)is higher than other clone sets(Figure 3(b)) means thateach code clone in a clone set S consists of more nonrepeated code sequences. However, in our observation, clone metric RNR(S) distinguishes only “nonrepeated” token sequences from “repeated” token sequences of code clones. The clone sets whose RNR(R)is higher have the tendency of including a procedurecorresponding to a semantic unit. (e.g., just only a
few lines of code clones, if (or if-else) blocks with a few
lines)

Figure 1: Example of code fragments in clone set
whose RNR(S) is the highest, and lowest
metric values are included in the grey part. As such, all clone
sets are selected. In Figure 2(b), the values of LEN(S2 ) issmaller than the lower limit of LEN, S2 is not selected. Thismeans that we can get “long” code clones by changing thelower limit of LEN. Thus the Metric Graph enables users
to choose arbitrary clone sets based on clone metric values
with AND operators.
The Metric Graph of Gemini provides clone sets which
satisfy clone metrics values in the range speciﬁed by developers. However, research has not been done on the appropriate combinations of clone metric values range for eﬀective
clone sets ﬁltering. Consequently, it is diﬃcult for developers to give Gemini appropriate clone metric-value ranges foreﬀective ﬁltering.

Clone sets whose POP(S) is higher than others
As described in Section 2.1, clone sets whose POP(S)is higher than other clone sets(Figure 3(c)) means thatcode clones in a clone set S appear more frequently inthe system. However, in our observation, these clone
sets include many small size code clones. It takes more
eﬀort to perform refactoring the smaller code clones
than longer code clones. Moreover, these clone sets include a lot of language-dependent code clones. Therefore, it is ineﬃcient to perform refactoring theses clonesets.

2.2 Filtering Clone Sets Using Individual Clone
MetricUsing Gemini, we have suggested to industrial softwaredevelopers code clones that should be checked for refactoring
and received signiﬁcant feedback. According to their opinion, many clone sets whose individual clone metric value ishigh are inappropriate for refactoring. Based on the feedback, we have analyzed the clone sets whose individual clone
metric value is high. Here is features of clone sets whose
individual clone metric value is high that we observed andthe obstacles that we recognized to perform refactoring with
Figure 3 2 .

Therefore, we also recognized the following characteristic.
• It was observed that if a clone set whose one clone
metric value is high, the other clone metrics values
are low. Therefore, we might conjecture that using
combined clone metrics can be a feasible method to get
refactoring candidate code clones than using individualclone metric .
• Combining clone metrics might cover defects of clone
sets whose individual clone metric value is high.

2
The examples in Figure 3 are picked from Ant 1.7.0 since
the the subject source code used in Section 4. The sourcecode clones are similar to these examples.

9• Only if code clones in a clone set have similaror same constructs of token sequence, the clone
metric POP(S) value increases. Therefore, clone
metric POP(S) eliminates consecutive if blocks
detected by higher LEN(S) values.

ŝĨ;;ƉсŐĞƚWƌŽũĞĐƚ;Ϳ͘ŐĞƚWƌŽƉĞƌƚǇ;ΗĂŶƚ͘ŶĞƚƌĞǆǆĐ͘ďŝŶĂƌǇΗͿͿ͊сŶƵůůͿ΂ƚŚŝƐ͘ďŝŶĂƌǇ сWƌŽũĞĐƚ͘ƚŽŽŽůĞĂŶ;ƉͿ͖΃ͬͬĐůĂƐƐƉĂƚŚ ŵĂŬĞƐŶŽƐĞŶƐĞ
ŝĨ;;ƉсŐĞƚWƌŽũĞĐƚ;Ϳ͘ŐĞƚWƌŽƉĞƌƚǇ;ΗĂŶƚ͘ŶĞƚƌĞǆǆĐ͘ĐŽŵŵĞŶƚƐΗͿͿ͊сŶƵůůͿ΂ƚŚŝƐ͘ĐŽŵŵĞŶƚƐ сWƌŽũĞĐƚ͘ƚŽŽŽůĞĂŶ;ƉͿ͖΃ŝĨ;;ƉсŐĞƚWƌŽũĞĐƚ;Ϳ͘ŐĞƚWƌŽƉĞƌƚǇ;ΗĂŶƚ͘ŶĞƚƌĞǆǆĐ͘ĐŽŵƉĂĐƚΗͿͿ͊сŶƵůůͿ΂ƚŚŝƐ͘ĐŽŵƉĂĐƚ сWƌŽũĞĐƚ͘ƚŽŽŽůĞĂŶ;ƉͿ͖΃dŚĞƌĞƐƚŝƐŽŵŝƚƚĞĚ
͘͘• Clone metric LEN(S) eliminates small size clone
sets detected by higher POP(S) values.
3. Clone sets whose RNR(S) and POP(S) are higher thanother clone sets
• Clone metric RNR(S) eliminates language dependent code clones detected by higher POP(S) values. Therefore, It is highly possible that theseclone sets include speciﬁc logics, because consecutive if (or if-else) blocks, case entries of switch
statements, consecutive variable declarations are
not included.

(a) Code fragment in a clone set whose LEN(S) is 455, thehighest LEN(S) value in Ant 1.7.0.
΃΃ĞůƐĞ΂ͬͬŝƐƚŚĞǌŝƉĨŝůĞŝŶƚŚĞĐĂĐŚĞ
ŝƉ&ŝůĞ ǌŝƉ&ŝůĞ с;ŝƉ&ŝůĞͿǌŝƉ&ŝůĞƐ͘ŐĞƚ;ĨŝůĞͿ͖ŝĨ;ǌŝƉ&ŝůĞ ссŶƵůůͿ΂
ǌŝƉ&ŝůĞ сŶĞǁŝƉ&ŝůĞ;ĨŝůĞͿ͖
ǌŝƉ&ŝůĞƐ͘ƉƵƚ;ĨŝůĞ͕ǌŝƉ&ŝůĞͿ͖΃ŝƉŶƚƌǇ ĞŶƚƌǇсǌŝƉ&ŝůĞ͘ŐĞƚŶƚƌǇ;ƌĞƐŽƵƌĐĞEĂŵĞͿ͖ŝĨ;ĞŶƚƌǇ͊сŶƵůůͿ΂ƌĞƚƵƌŶǌŝƉ&ŝůĞ͘ŐĞƚ/ŶƉƵƚ^ƚƌĞĂŵ;ĞŶƚƌǇͿ͖• higher POP(S) values mean code clones in a clone
set appear more frequently in software. Therefore, it improves the maintainability to perform
refactoring to these clone sets.
4. Clone sets whose LEN(S), RNR(S), and POP(S) arehigher than other clone sets(b) Code fragment in a clone set whose RNR(S) is 97, thesecond highest RNR(S) value in Ant 1.7.0.

• Clone metric RNR(S) eliminates language dependent code clones.

ŽƵƚ͘ƉƌŝŶƚ;Ηф͊>DEdƚĂƌŐĞƚ;ΗͿ͖ŽƵƚ͘ƉƌŝŶƚ;d^<^Ϳ͖ŽƵƚ͘ƉƌŝŶƚ;ΗͮΗͿ͖ŽƵƚ͘ƉƌŝŶƚ;dzW^Ϳ͖ŽƵƚ͘ƉƌŝŶƚůŶ;ΗͿΎхΗͿ͖ŽƵƚ͘ƉƌŝŶƚůŶ;ΗΗͿ͖• Clone sets whose higher POP(S) apply good motivation for refactoring to developers because toperform refactoring to code clones in a clone set
appear more frequently in software improves themaintainability.

ŽƵƚ͘ƉƌŝŶƚůŶ;Ηф͊dd>/^dƚĂƌŐĞƚΗͿ͖ŽƵƚ͘ƉƌŝŶƚůŶ;ΗŝĚ/ η/DW>/ΗͿ͖ŽƵƚ͘ƉƌŝŶƚůŶ;ΗŶĂŵĞdηZYh/ZΗͿ͖ŽƵƚ͘ƉƌŝŶƚůŶ;ΗŝĨdη/DW>/ΗͿ͖ŽƵƚ͘ƉƌŝŶƚůŶ;ΗƵŶůĞƐƐdη/DW>/ΗͿ͖ŽƵƚ͘ƉƌŝŶƚůŶ;ΗĚĞƉĞŶĚƐdη/DW>/ΗͿ͖

• Clone metric LEN(S) eliminates small size clonesets.

4. INDUSTRIAL CASE STUDY
To validate our proposal method, we performed a casestudy. Our case study subject is an industrial softwarethat was developed by NEC, a Japanese multinational IT
company. This section describes the study steps and study
subjects. Results of case study are then reported. Finally,
threats to validity are discussed.

(c) Code fragment in a clone set whose POP(S) is 21, thehighest POP(S) value in Ant 1.7.0.

Figure 3: Examples of code fragments in clone set
in Ant 1.7.0

3.

4.1 Study Steps
The steps of the case study and its explanation are thefollowing:

PROPOSED METHOD

Based on observation described in Section 2.2, we propose
a method for extracting code clones using combinations ofclone metrics in this study.
The details regarding the proposed method and its advantages that we expect are the followings:

1. Gemini extracted clone sets from CCFinder’s output.
The input of CCFinder was software developed byNEC. NEC plans to maintain the software forthe next 10 years. Developers wanted to perform
refactoring of this software for maintenance eﬃciency. Therefore, it was adequate software to
extract clone sets for refactoring.

1. Clone sets whose LEN(S) and RNR(S) are higher thanother clone sets
• Clone metric RNR(S) eliminates types of if (orif-else) blocks detected by higher LEN(S) values.
• Clone Metric LEN(S) eliminates small size code
clones detected by higher RNR(S) values.

2. We selected clone sets from Gemini’s output using clone
metrics.

2. Clone sets whose LEN(S) and POP(S) are higher thanother clone sets

• Based on following assumptions, we selected metrics LEN(S), RNR(S), and POP(S).

10– To perform refactoring small size clone sets,
and a few code clones is more ineﬀective thanlong size clone sets, and numerous number ofcode clones.
– It is ineﬀective to check language-dependentcode clones for refactoring.
• We selected clone sets detected by higher combined clone metrics values. To compare a resultof these clone sets, clone sets whose individualclone metric value is higher are also selected.

Table 1: Correlation between clone metrics LEN,
RNR, and POP

LEN
RNR
POP

LEN
−0.02
−0.20

RNR

POP

−0.12

-

SRNR·P OP : 18 clone sets whose RNR(S) and POP(S) values are high rank in the top 15.

3. We conducted a survey about these clone sets and got
feedback from a developer.

SLEN·RNR·P OP : 1 clone set whose LEN(S), RNR(S) · POP(S)value are high rank in the top 15.

• The developer is a project manager with 10 yearsof development experiences with Java.
• We asked him to ﬁll out surveys considering feasibility of performing refactoring and cost in maintenance.
• The survey includes a list of selected code clones
and a question for each clone set. The question
asks whether developers would perform refactoring or not. The developer answered using thefollowing options:– Perform refactoring.
– Write comments about code clones, but don’t
perform refactoring.
– Change nothing.
– Others.

Note that the intersection of the set SLEN ∪ SP OP ∪ SRNR
and the set SLEN·RNR ∪ SLEN·P OP ∪ SRNR·P OP is only 5in all of 62 surveyed clone sets.
Here, we determined the correlation between metrics LEN,
RNR, and POP To conﬁrm our proposal method. Table 1
describes Spearman correlation coeﬃcient. As shown in Table 1, all correlations were smaller than 0.50 Therefore, there
is no signiﬁcant relationship among the clone metrics LEN,
RNR and POP.

4.3 Result of Survey
To analyze the result, we use precision and average precision. Here, purpose of using precision and average precision
are described below:

4. We analyzed the result of survey.

Precision : To investigate the question “How many refactoring candidates were accepted by developer?”• If clone sets were marked as “Write comments
about code clones, but don’t perform refactoring” or “Change nothing” or “Others”, we regarded
those clone sets as inappropriate clone sets forrefactoring.

Average precision : To investigate the question “Are refactoring candidates shown in high rank?”. It takes value
0 and 1, with higher values indicating that clone sets ofhigher metrics values are more accepted as refactoring
candidates.

• If clone sets detected by higher combined clone
metrics were more marked as “Perform refactoring” than clone sets detected by higher individual clone metric value, we can say our proposed
method successfully to selected the clone sets forrefactoring.

Let SAll represent ALL clone sets that are selected by eachmethod, SARC represents clone sets Accepted as Refactoring
Candidates by a developer.
P recision =4.2 Study Subject
The subject of this case study was a web-application software implemented in Java. It is 110KLOC across 296 ﬁles.
In this study, we set 30 tokens as the minimum token lengthof a code clone. As CCFiner’s output, 736 clone sets are detected. Due to the limitation of time and eﬀort, we selectedeach 62 clone sets detected by higher individual clone metricvalue, and combined clone metrics values. The following aredetails of subject clone sets:|SARC |
|SAll |

Additionally, let |SARC | = N , P recision(r) represents thePrecision of a clone set who accepted as a refactoring candidate at rank r.
N
X

Average P recision =P recision(r)i=1NTable 2 and Table 3 describe the result of the survey. 3
In Table 2 and Table 3, column Clone Sets shows name ofsubject clone sets. #Selected Clone Sets and #Refactoringshows the number of selected clones and the number of clone
sets marked as “Perform refactoring” respectively.

SLEN : Clone sets whose LEN(S) value are top 10 high.
SRNR : Clone sets whose RNR(S) value are top 10 high.
SP OP : Clone sets whose POP(S) value are top 10 high.
SLEN·RNR : 15 clone sets whose LEN(S) and RNR(S) values are high rank in the top 15.

3

In Table 2, LEN(S), and LEN(S) · POP(S) have two marks“Perform refactoring” and “Write comments” since thoseclone sets comprise two parts: one is a refactoring target
and another should be commented. They were counted as“Perform refactoring.”

SLEN·P OP : 7 clone sets whose LEN(S) and POP(S) values
are high rank in the top 15.

11

Table 2: Results, precision, and average precision of each clone set in the survey
Clone Sets
#Selected Clone Sets #Refactoring Precision Average Precision
SLEN
10
7
0.70
0.57
10
4
0.40
0.32
SRNR
SP OP
10
3
0.30
0.26
15
13
0.87
0.95
SLEN·RNR
SLEN·P OP
7
6
0.86
0.92
18
14
0.78
0.97
SRNR·P OP
SLEN·RNR·P OP
1
1
1.00
1.00

Table 3: Results of clone sets detected by higer individual clone metric, and combined metrics in the survey
Filtering Method#Selected Clone Sets #Refactoring Precision
Individual Clone Metric
30
14
0.47
Combined Clone Metrics
41
34
0.83

4.4 Threats to Validity

As shown in the column “Precision” in Table 2, a clone set
who has the lowest precision(0.30) is SP OP , and a clone set
who has the highest precision(1.00) is SLEN·RNR·P OP . Thismeans using metrics LEN(S), RNR(S), and POP(S) are themost acceptable for refactoring, and using metric RNR is
unacceptable to extract clone sets for refactoring. However,number of LEN(S) · RNR(S) · POP(S) are only one, weneed a further investigation that these clone sets are reallythe most the most appropriate clone sets for refactoring.
The details of precision are the followings. The precisionsof SRNR , SP OP are smaller than 0.50. This means thatthese clone sets are appropriate for refactoring. However,the precisions of SLEN , SLEN·RNR , SLEN·P OP , SRNR·P OP ,and SLEN·RNR·P OP are more than 0.70 (They are shown inbold in column “Precision” in table 2), this means that theseclone sets are inappropriate for refactoring.
Nevertheless, we had a strong concern that SLEN are really appropriate clone sets for refactoring. Therefore, we introduced average precision to conﬁrm that using clone metric LEN(S) is really acceptable to extract clone sets for refactoring. As shown in Table 2, average precision of SLEN is
0.57. Contrary to this, the average precisions of all clone
sets detected by higher combined clone metrics are over0.90(They are shown in bold in column “Average Precision”
in table 2). Clone sets who has higher average precisions
mean that clone sets detected by higher clone metric values
are more appropriate for refactoring than clone sets detectedby lower clone metric values . In fact, top 2 clone sets of
SLEN were not marked as “Perform refactoring” in the survey. However, top 2 clone sets of all clone sets detectedby high combined clone metrics were marked as “Perform
refactoring” by a developer. Hence, to extract refactoring
candidate clone sets, using clone metric LEN(S) is unacceptable.
Moreover, as shown in Table 3, Precision of clone sets
detected by higher combined clone metrics (They are shownin bold in column “Precision” in table 3) are higher than
precision of clone sets detected by higher individual clone
metric. In conclusion, using higher combined clone metrics
is more appropriate to extract clone sets for refactoring thanusing each individual clone metric.

Because of the limitation of developer’s time and eﬀort,
the survey included 10 clone sets for higher individual clone
metric, and 41 clone sets selected by the combinations ofhigher clone metrics. If we selected all clone sets in software
for survey, we might get diﬀerent results. In addition, It ishighly possible to lost relevant clone sets for refactoring due
to ﬁltering. However, as we mentioned Section 4.3, clone sets
whose combined clone metrics values are higher were more
accepted as refactoring candidates in the survey. Thus, we
believe that the result of survey dose not signiﬁcantly change
if we checked all code clone sets in software.
Moreover, our case study is conducted on a single system
and got feedback from one developer. Therefore, although
we could successfully validate our method in this study, ourmethod may not generalize to other software. To improvegenerality, we need to investigate other software. We areplanning to assess our method with open source software
based on their changed history, investigate recall. However,there is a small chance to analyze industrial software in a
refactoring phase prior to its release.

5. RELATED WORK
Jiang et al.[6] and Kapser et al.[9] pointed out that code
clone detection tools using parameterized matching detected
a lot of false positives. Jiang et al.[6] used textual ﬁltering
techniques to remove false positives from CCFinder’s output. They removed code clones whose textual similarity
falls below a certain threshold. Kapser et al.[9] proposed
the following techniques to remove false positives from theoutput of their token-based clone detection tool.
• Identiﬁer names outside functions (e.g., Java methods,
C functions) are not parameterized. For example, declarations of ﬁeld variables in Java programs and external variables in C programs are often duplicated but
most of them are false positives.
• Simple method calls are matched only if Levenshtein
Disitance of those method names is small.
• Logical structures (e.g., switch statements, if (or ifelse) blocks) are matched if 50% of tokens in thesestructures are identical.

12• Number and type of diﬀerences between code clones

There is the possibility to make our method more eﬀective
by applying the ﬁltering techniques proposed by Jiang et al.
and Kapser et al. as the preprocessor or the postprocessorof our method.
CCFinderX[7] developed by Kamiya provides the metric
TKS(S) that means the number of token types in code clones
belonging clone set S. The metric TKS is eﬀective to remove
clone sets not in need of developer’s investigation (e.g., consecutive variable declarations) because those clones tend tohave small numbers of token types. This means that there is
the possibility of improving the eﬀectiveness of our methodby use of the metric TKS in addition to the use of the metric
RNR. However, clone sets with low RNR value include a lotof consecutive parts. They tend to have small number of token types and low TKS value. This correlation means thatthe use of both TKS and RNR are not signiﬁcantly eﬀective.
Balazinska [1] et al. and Higo [4] et al. characterize clone
sets according to the ease of refactoring. Balazinska et al.
characterize clone sets by analyzing the following information:• Location of the code clones in the software• Ownership issues• Test coverage

Acknowledgments
We express our great thanks to Ms. Fusako Mitsuhashi and
Mr. Shin’ichi Iwasaki of NEC Corporation for data collection, and Dr. Daniel German of the University of Victoria
for helpful comments on earlier revisions of this paper. We
also thank Dr. Simone Livieri of Osaka University for proofreading this paper. This work is being conducted as a partof Stage Project. Also, this work is partially supported by
JSPS, Grant-in-Aid for Scientiﬁc Research (A) (21240002)
and Grant-in-Aid for Research Activity start-up(22800040).

7. REFERENCES[1] M. Balazinska, E. Merlo, M. Dagenais, B. Lagüe, andK. Kontogiannis. Advanced clone-analysis to support
object-oriented system refactoring. In Proc. of WCRE
2000, pages 98–107, 2000.
[2] M. Fowler. Refactoring: improving the design ofexisting code. Addison Wesley, 1999.
[3] Y. Higo, T. Kamiya, S. Kusumoto, and K. Inoue.
Method and Implementation for Investigating CodeClones in a Software System. Information and
Software Technology, 49(9-10):985–998, 2007.
[4] Y. Higo, S. Kusumoto, and K. Inoue. A metric-based
approach to identifying refactoring opportunities for
merging code clones in a Java software system. J.
Softw. Maint. Evol.: Res. Pract., 20:435–461, 2008.
[5] L. Jiang, G. Misherghi, Z. Su, and S. Glondu.
DECKARD: Scalable and accurate tree-based
detection of code clones. In Proc. of ICSE 2007, pages
96–105, 2007.
[6] Z. M. Jiang and A. E. Hassan. A framework forstudying clones in large software systems. In Proc. of
SCAM 2007, pages 203–212, 2007.
[7] T. Kaimiya. Tutorial of CLI Tool ccfx, 2008.
http://www.ccfinder.net/doc/10.2/en/
tutorial-ccfx.html.
[8] 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.
[9] C. J. Kapser and M. W. Godfrey. “Cloning consideredharmful” considered harmful: patterns of cloning insoftware. Empir Software Eng, 13:645–692, 2008.
[10] M. Kim, V. Sazawal, D. Notkin, and G. Murphy. An
empirical study of code clone genealogies. In Proc. of
ESEC/FSE 2005, pages 187–196, 2005.
[11] C. Roy and J. Cordy. Scenario-based comparison ofclone detection techniques. In Proc. of ICPC 2008,
pages 153–162, 2008.
[12] Y. Ueda, T. Kamiya, S. Kusumoto, and K. Inoue.
Gemini: Maintenance support environment based oncode clone analysis. In Proc. of METRICS 2002, pages
67–76, 2002.

• Diﬀerences among the code clones belonging to a cloneset• Dependencies between the code clone belonging to aclone set and its surrounding code
Higo [4] et al. proposed two metrics to represent the average number of the externally deﬁned variables respectively
referenced and assigned in the code clones belonging to aclone set. The combination of our method and the techniques focusing on the ease of refactoring has the possibility
to improve the eﬀectiveness of clone set ﬁltering.
Here, we summarize the main originality of our work.
• To remove false positives, we propose a method thatcombines multiple metrics. Those metrics are categorized into two types. LEN(S) and POP(S) metrics
focus on the amount of code duplication. On the other
hand, RNR(S) metric focuses onwhether or not code
clones belonging to a clone set are language-dependentcode.
• In the case studies, our method extracted a lot of clone
sets that are evaluated as refactoring candidates by a
NEC developer.

6.

CONCLUSION AND FUTURE WORKIn this paper, we proposed a method to extract appropriate clone sets for refactoring from the output of CCFinder.
Also, we showed the usefulness of the proposed method withan industrial case study using the source code developed byNEC. The case study indicates the proposed method is more
eﬃcient than using individual clone metric to extract clone
sets for refactoring.
As future work, we are planning to perform case studies of open source software and investigate the usefulnessof proposed method. Moreover, we would like to improve
our proposed method by taking previous ﬁltering and clone
metrics described in 5 section to proposed method. Finally,
we would like to check the following factors, for the reason
that these factors mainly inﬂuence the estimated trade oﬀ
between eﬀort for clone removal and estimated savings due
to better future maintainability.

13