Problematic Code Clones Identification using Multiple Detection Results
Yoshiki Higo, Ken-ichi Sawa, and Shinji Kusumoto
Graduate School of Information Science and Technology,
Osaka University,
1-5, Yamadaoka, Suita, Osaka, 565-0871, Japan
Email: {higo,k-sawa,kusumoto}@ist.osaka-u.ac.jp

Abstract—Most code clones are generated by copy-and paste
programming. Copy-and-paste programming shortens a timerequired for implementation because pasted code is a templateof the required functionality. However, it sometimes brings
on new bugs to the source code. After copy-and-paste, pasted
code is somewhat changed fitting for the context of the region
surrounding the pasted code. For example, some identifiers are
replaced with other identifiers or a few statements are inserted,
deleted, or changed. If such modifications are incorrectly
performed, bugs occur in code clones. However, not all code
clones are problematic, many code clones have decent reasonsfor their existence. Consequently, simple code clone detection
is inefficient for identifying problematic code clones.
Firstly, this paper proposes a classification scheme fordividing problematic code clones from non problematic ones.
Secondly, it proposes a method for extracting specific code
clones classified as problematic ones. Thirdly, it presents resultsof case studies conducted for evaluating the proposed method.
The proposed method uses multiple code clone detection tools,
and it doesn’t directly analyze program source code. After
multiple detections, simple operations are performed to extract
code clones that are likely to be problematic. In the case studies
conducted on an open source software system, the proposed
method could actually identify 22 problematic code clones.
Keywords-code clone; fault detection;

I. I NTRODUCTION
No software has no duplicate code. Recently, studies
on duplicate code have been active and it attracts muchattention. In the research area of duplicate code, a region
duplicated to another region is called a code clone.
Copy-and-paste programming is the leading cause whycode clones are introduced to program source code. For
example, Kim et al. reported that developers averagely perform copy-and-paste 16 times per hour [1]. Copy-and-paste
is a powerful tool when implementing a new functionality
because it can immediately create a template of the newfunctionality. Developers have only to modify the template
fitting for the context of the pasted region [2], [3].
However, code clones often make negative impacts on
software development and maintenance. One of them isincreasing bug occurrences. For example, if an instance of
copy-and-pasted code is changed for fixing bugs or adding
new features, its correspondents have to be changed simultaneously. If the correspondents are not changed inadvertently,
bugs are newly introduced to them.

If (a > b) { b++; a=1;}

resuedby by‘copy-andpaste’
Code
reuse
copy and paste

Identifier replacement

Statement
insertion
If (i > j){i = i / 2;
j++;
i=0;
}

If (a > b)
{
b++;
a=1;
}

If (i > j)
{
j++;
i=0;
}

Type-1 clone

Type-2 clone

Figure 1.

Statement
deletionIf (i > j)
{
i=0;
}

StatementchangeIf (i > j){
j = j + 1;i=0;}Type-3 clone

Code Reuse by Copy-and-Paste

Another example is small modification after copy-andpaste. Pasted code is often modified fitting for the context
of the pasted region. As shown in Figure 1, identifiers
such as used variables or invoked methods are changed, orsome statements are added, deleted, or changed, or the bothare performed. If such small modifications are incorrectly
performed or forgotten to be performed, bugs are newly
introduced into the pasted code. Here, we assume that avariable is forgotten to be replaced with another variable
after paste: if the pasted code has different namespace fromits original code, compiling the code is aborted and themistake is identified; however, if the pasted code has thesame namespace as the original code, compiling the code
succeeds and the mistake isn’t identified. It is difficult andcostly to identify such a bug.
This paper proposes a new method for efficiently identifying bugs caused by copy-and-paste programming. The
method utilizes the fact that results of different detection
tools are different from one another [4], [5]. At present,
there are various code clone detection methods and implementations [6], and code clones are often operationallydefined by individual detection methods. That is why somecode clones detected by a certain detection method are notdetected by another detection method. The proposed method
detects code clones using multiple detection results, andCode Fragment 1

Code Fragment 2

Code Fragment 3

If (a > b)
{
b++;
a=1;
}

If (i > j)
{
j++;
i=1;
}

If (x > y)
{
x++;
y=1;
}

(a) Original Code
Code Fragment 1

Code Fragment 2

Code Fragment 3

If ($1 > $2)
{
$2++;
$1=1;
}

If ($1 > $2)
{
$2++;
$1=1;
}

If ($1 > $2)
{
$1++;
$2=1;
}

(b) Transformed Code with p-match
Code Fragment 1

Code Fragment 2

Code Fragment 3

If ($ > $)
{
$++;
$=1;
}

If ($ > $)
{
$++;
$=1;
}

If ($ > $)
{
$++;
$=1;
}

(c) Transformed Code without p-match
Figure 2. Example of Code Transformation with and without Parameterized Matchanalyzes their differences. The analysis identifies suspicious
code clones. The analysis is fast and easy to implement, sothat it can easily applied to practical size software systems.
II. P RELIMINARIES
A. Existing Classification Scheme
Bellon et al. classified code clones based on how eachcode clone instance is different from its correspondents [4].
The classification is composed of three types (Figure 1
illustrates processes of each type code clone occurrence).
Type-1: Code clones that are identical to their correspondents. This type permits only the differences ofwhite spaces and tabs.
Type-2: Code clones that include different identifiers
from their correspondents.
Type-3: Code clones that include further differences thanType-2. Pasted code including statement insertion,
deletion, or change is classified into this type.
B. Parameterized Match
Before introducing a new code clone classification
scheme, parameterized match (p-match) must be explained.
P-match is a code transformation rule for detecting moresignificant code clones. It transforms the same identifiers
into the same special tokens before detection process. Figure
2 is an example of the code transformation. If a detection
tool adopts p-match, the code is transformed as shown in

Figure 2(b). In this example, code fragment 1 and codefragment 2 are detected as code clones. However, codefragment 3 is not regarded as a code clone of code fragments
1 and 2 because its special tokens don’t correspond to thespecial tokens of the code fragments 1 and 2. If p-match is
not used, the code is transformed as shown in Figure 2(c).
In this example, each of the code fragments 1, 2, and 3 isdetected as a code clone of the other code fragments.
P-match was initially proposed by Baker [7], and there areseveral detection tools that adopt p-match at present [8], [7].
P-match prevents from detecting code clones whose patternsof identifier use are different from their correspondents.
In this paper, p-match is a key technique that divides
problematic code clones from non problematic ones.
III. N EW C LASSIFICATION S CHEME
The main purpose of a new classification scheme is dividing problematic code clones from non problematic ones.
The new scheme is based on the Bellon’s scheme describedin Section II-A, and it is defined as follows.
Type-1a: Code clones that are exactly identical to theircorrespondents. Any kinds of textual differences
are not permitted.
Type-1b: Code clones that include differences of whitespaces and tabs. Any more differences are notpermitted.
Type-2a: Code clones that include different identifiers.
However, their patterns of identifier use are thesame. This type code clones are detected by pmatch detection tools.
Type-2b: Code clones that include different identifierswith different patterns of identifier use. This typecode clones are not detected by p-match detection
tools.
Type-3: Code clones that include statements insertion,
deletion, or change.
In the new scheme, Bellon’s type-1 is divided into type-1aand type-1b, and Bellon’s type-2 is divided into type-2a andtype-2b. Type-3 of the new scheme is the same as Bellon’s
type-3.
As described above, the new scheme’s purpose is dividing
problematic code clones from non problematic ones. We
consider that type-1b, type-2b, type-3 of the new scheme
are problematic code clones, and type-1a and type-2a are
non problematic ones for the following reasons.
• The presence of type-1b code clones implies that different formats are used for implementing semanticallysame logics. Such format differences make code understanding more difficult.
• The presence of type-2b code clones implies that there
may be incorrect replacements of identifiers after copyand-paste or there may be code clones that were
forgotten to be modified simultaneously when theircorrespondents were modified.

•As well as type-2b code clones, the presence of type3 code clones implies that there may be incorrectstatements insertion, deletion, or change after copyand-paste, or there may be code clones that were
forgotten to be modified simultaneously when theircorrespondents were modified.

/* Abuse this field as a pointer to the directory entry, used tofind the expire list pointers */dentry->d_time = (unsigned long) ent;
if (!dentry->d_inode){
inode = autofs_iget(sb, ent->ino);
if (IS_ERR(inode)){/* Failed, but leave pending for next time */return 1;}
dentry->d_inode = inode;}

IV. P ROPOSED M ETHOD
The purpose of the proposed method is extracting only
problematic code clones such as type-1b, type-2b, and type3. Section IV-A explains the key idea of the proposed
method, and Section IV-B to Section IV-F describe techniques for enhancing accuracy of the proposed method.
A. Key Idea
The key idea for extracting problematic code clones isvery simple. We utilize the fact that the detection result of atool is different from the detection result of another tool. At
present, there are various code clone detection tools and eachof them has a unique definition of code clones, so that thetools detect different regions of the same source code as code
clones. Table I illustrates a model that different detection
methods detect different types of code clones. For example,
the method β detects only type-1a and type-1b code clones
meanwhile the method  detects all types of code clones.
Here, we use this model for explaining our method.
A
In this explanation, we also assume that SB
is a set ofA
type-B code clones detected by method A. Additionally, Sallis a set of all code clones that method A detects. Using thisassumption, the following formula is formed:
A
A
A
A
A
Sall
= S1a
∪ S1b
∪ S2a
∪ S2b
∪ S3A .

If method A doesn’t have a capability to detect type-B codeA
clones, SB
becomes ∅.
Here, we focus on two detection method β and γ in Table
I. Method β detects type-1a and type-1b code clones, andmethod γ detects type-1a, type-1b, and type-2a code clones,βγ
so that Salland Sallare represented as follows:
β
Sall

β
β
= S1a
∪ S1b

γ
Sall

γ
γ
γ
= S1a
∪ S1b
∪ S2a

β
β
γ
γ
If S1aand S1b
are the same as S1aand S1brespectively,γ
S2a can be obtained by the following operation:
γ
S2a

γ
β
= Sall− Sallmethod αmethod βmethod γ
method δ
method 

1aCode Clone Type
1b
2a
2b
×
×
×
×
×
×

dentry->d_time=(unsigned long)ent;
if(!dentry->d_inode){
inode=autofs_iget(sb,ent->ino);if(IS_ERR(inode)){return 1;}
dentry->d_inode=inode;}(b) After Normalization
Figure 4.

Example of Code Normalization

γ
δ
, S2b
and S3 can be obtained by the
In a similar way, S2afollowing operations respectively:
δ
S2b

γ
δ
= Sall− SallS3

δ= Sall− SallHowever, the above formulas are realized if the set ofcertain type code clones detected by a certain tool is equal to
the set of the same type code clones detected by another tool.
Unfortunately, this assumption is not realistic because eachdetection tool has its own definition of code clones, so thatthe same type code clones detected by different detection
tools are always not exactly identical.
The remainder of this section describes countermeasures
for the fact. Figure 3 depicts where each countermeasure is
performed in the proposed method. In this paper, if code
clones detected by different tools satisfy all the following
conditions (Conditions 1 and 2), they are regarded as thesame code clones and they are delisted from candidates of
suspicious code.
B. Preparation 1: Code Normalization

Table IM ODEL OF D ETECTED C ODE C LONE T YPES
Detection Method(a) Before Normalization

3
×
×
×
×

Existing detection tools adopts various algorithms andheuristics for detecting more significant code clones [4].
For example, handling blank lines and comment lines aredifferent between the tools. In order to reduce this problem, acode normalization is used. The code normalization consistsof the following operations:••blank lines and comment lines are removed;
while spaces and tabs before/between/after lexical tokens are removed;preparationcode
normalization

source code

code clone
filtering

subtraction
code clone
merging

Bellon’s
thresholddetection
tool

Figure 3.

inclusion

subtraction
resultOverview of the Proposed Methodlines including just a single open or close brace areremoved, and the brace is joined to its above line.
Figure 4 represents an example of code before and after
applying the code normalization. As shown in Figure 4, thecode normalization reduces lines of code of source files.
Therefore, if we use line-based detection techniques, weshould carefully specify the length of code clones to be detected. We should specify a lower threshold than a value forthe original source code. If we use other kinds of detection
techniques, it is no problem that we use the same thresholdfor both original and normalized code. Other techniques suchas token-based or AST-based are not affected by how eachline consists of lexical tokens.
•

CP1
CP1.CF1

CP1.CF2

CP2.CF1

CP2.CF2
CP2

Clone Pair: CP1, CP2
Code Fragments in CP1: CP1.CF1, CP1.CF2
Code Fragments in CP2: CP2.CF1, CP2.CF2

Figure 5.

An Example for Explaining Bellon’s Threshold

C. Preparation 2: Code Clone Filtering
Not all code clones detected by tools are beneficial for
us. Code clone filtering introduced here is designed to remove unnecessary code clones and reduce false positives ofsubtraction result. We remove code clones in the same files,
which overlap each other more than 30%. The condition is
the same as the Kapser’s study [9].
Code clones satisfying this condition are very like to
be trivial ones such as consecutive variable declarations orconsecutive case entries of switch statement, which are not
worth to be investigated. We assume that a clone pair consists of two code clones, CF1 and CF2 , overlap(CF1 , CF2 )can be defined as follows:
overlap(CF1 , CF2 ) =| lines(CF1 ) ∩ lines(CF2 ) || lines(CF1 ) ∪ lines(CF2 ) |(1)lines(CF1 ) and lines(CF2 ) are sets of lines included incode fragments CF1 and CF2 respectively.
D. Preparation 3: Code Clone Merging
If two clone pairs overlap each other, they are merged as asingle clone pair. For example, we assume that there are twoclone pairs, CP1 and CP2 . Clone pair CP1 (CP2 ) consistsof two code clones CP1 .CF1 (CP2 .CF1 ) and CP1 .CF2
(CP2 .CF2 ). If CP1 .CF1 overlaps CP2 .CF1 and CP1 .CF2
overlaps CP2 .CF2 respectively, the two code clones are
removed from the set of detected clone pairs, and a clone
pair CP3 is added to it. In this case, CP3 consists of twocode clones, CP3 .CF1 and CP3 .CF2 . Here the two code
cones are as follows:
CP3 .CF1=lines(CP1 .CF1 ) ∪ lines(CP2 .CF1 )CP3 .CF2=lines(CP1 .CF2 ) ∪ lines(CP2 .CF2 )E. Condition 1: Bellon’s Threshold
Bellon et al. proposed a threshold for determining whether
code clones detected by different tools are the same or not[4]. Our proposed method also uses the Bellon’s threshold.
Bellon’s threshold represents how a pair of code clones
detected by a certain tool overlaps with a pair of code
clones detected by another tool. Using formula 1, Bellon’s
threshold, good value, is defined as follows:
good(CP1 , CP2 )= min(overlap(CP1 .CF1 , CP2 .CF1 ),overlap(CP1 .CF2 , CP2 .CF2 ))Range of good value is from 0 to 1. If good value is equal
to or greater than threshold p, the two pairs of code clones
are regarded as the same. Bellon et al. said that 0.7 is anappropriate value for good value [4]. In this paper, we use
the same value as threshold p.
Figure 5 depicts an example for good value calculation. In
this figure, there are two pairs of code clones, CP1 and CP2 ,and 4 code fragments (code clones), CP1 .CF1 , CP1 .CF2 ,CP2 .CF1 , and CP2 .CF2 . Code fragment CP1 .CF1 overlaps with CP2 .CF1 , and CP1 .CF2 overlaps with CP2 .CF2
respectively. In this case good values becomes:
5 6
5good(CP1 , CP2 ) = min( , ) = ≤ 0.7
8 8
8
In this case, the good value is less than 0.7, so that thetwo pairs of code clones are not regareded as the same.
F. Condition 2: Including
There is an important principle shared by all of the detection tools, that the tools detect as much region as possible.
The fact implies that, the more different code the tool detects
as code clones, the greater regions are detected as code
clones. Therefore, we introduce the following condition: if
two different tools detect the same code clones, the code
clones detected by high detection capability tool always
include the ones detected by low capability tool.
V. C ASE S TUDY
In order to examine whether the proposed method canefficiently identify problematic code clones, a case study
was conducted.
A. Target
The target of this case study is Linux Kernel (version 2.6.6). Especially, we focused on a directory, linux2.6.6/arch, for closely investigating the result. The directory
consists of 2,699 .c source files, and 769,467 lines of code.
The reason of this choice is that some previous studies
worked on this software [10], [11].
B. Configuration
This case study was intended to efficiently identify two
kinds of bugs caused by copy-and-paste programming. They
are identifier-level and statement-level incorrect modifications after copy-and-paste. We thought that identifier-level
incorrect modifications generate type-2b code clones, andstatement-level incorrect modifications generate type-3 code
clones.
In order to efficiently obtain type-2b and type-3 code
clones, we used two detection tools, CCFinderX [8] andDude [12]. Table II presents the capabilities of the two
detection tools.
Table IID ETECTION C APABILITIES OF D UDE , CCF INDER , AND CCF INDER X

Detection Method(a) CCFinderX with p-match(b) CCFinderX without p-match(c) Dude with gap=0(d) Dude with gap=11aCode Clone Type1b 2a 2b3××××For extracting type-2b code clones, we subtracted thedetection result of (a) CCFinderX with p-match from thedetection result of (b) CCFinderX without p-match. In theremainder of this section, sets of code clones detected by(a) and (b) are represented by S (a) and S (b) respectively,
and the difference set is represented by S (b)−(a) .
For extracting type-3 code clones, we subtracted thedetection result of (c) Dude with gap=0 from the detection
result of (d) Dude with gap=1. In the remainder of thissection, sets of code clones detected by (c) and (d) arerepresented by S (c) and S (d) respectively, and the difference
set is represented by S (d)−(c) .
C. Result
For 4 sets of code clones, S (b) , S (b)−(a) , S (d) , andS, we measured 2 values, the number of the code
clones and the total LOC of the code clones. Table III
summarizes the measurement results. In the case of type2b, the number of code clones is dramatically decreased by
the subtraction (6,980 → 524, decreasing 92%). However,in the case of type-3, the number of code clones is not sodecreased by the subtraction (8,819 → 2,915, decreasing70%).
We browsed the source code of all the code clones
included in S (b)−(a) and S (d)−(c) to check whether eachcode clone falls under the following categories or not:(d)−(c)

(I)
(II)
(III)

known bugs, which have been already fixed in thelater versions,likely to be bugs, which have not been fixed in thelatest version yet,other kinds of issues, such as programming style.

Table III summarizes detection results, subtraction results,
and the number of identified bugs. Note that we could notbrowse all the code clones included in S (d)−(c) because thenumber of them was very large. The subtraction result of(c) and (d) was far from our expectation. We had thoughtthat the number of code clones in S (d)−(c) would be lessthan 1,000 as well as S (b)−(a) .
Table IIIT HE N UMBER OF C LONE PAIRS

Type-2b Clone Identification
S (b)S (b)−(a)LOCs of clone pairs
172,097
10,614# of clone pairs
6,980
524
# of identified problems
11
Type-3 Clone Identification
S (d)S (d)−(c)LOCs of clone pairs
217,794
69,521# of clone pairs
8,819
2,915
# of identified problems
111146:
1147:} else if (number == 2){1153:

MACIO_BIC(KEYLARGO_FCR0, (KL0_USB1_PAD_SUSPEND0 |} else if (number == 4){1154:

MACIO_BIC(KEYLARGO_FCR1, (KL1_USB2_PAD_SUSPEND0 |UNLOCK(flags);

1155:

UNLOCK(flags);

1149:(void)MACIO_IN32(KEYLARGO_FCR0);1156:(void)MACIO_IN32(KEYLARGO_FCR1);

1150:

mdelay(1);1157:mdelay(1);1151:

LOCK(flags);

1158:

LOCK(flags);

1152:

MACIO_BIS(KEYLARGO_FCR0, KL0_USB1_CELL_ENABLE);

1159:

KL0_USB1_PAD_SUBPEND1));
1148:

1153:

} else if (number == 4){

KL1_USB2_PAD_SUBPEND1));

1160:(a) Original Code (linux-2.6.6/arch/ppc/platforms/pmac feature.c)Figure 6.

MACIO_BIS(KEYLARGO_FCR0, KL1_USB1_CELL_ENABLE);} else if (number < 4){(b) Pasted Code (linux-2.6.6/arch/ppc/platforms/pmac feature.c)

A Real Bug in Identified Type-2b Code Clones in the second case study

094: int retval = 0;531: int retval = 0;095: int real_seconds, read_minutes, cmos_minutes;

532: int real_seconds, read_minutes, cmos_minutes;

096: unsigned char save_freq_select;

533: unsigned char save_freq_select;

097:

534:
535: /* irq are locally disabled here */536: spin_lock(&rtc_lock);098: /* Tell the clock it’s being set */537: /* Tell the clock it’s being set */099: save_control = CMOS_READ(RTC_CONTROL);

538: save_control = CMOS_READ(RTC_CONTROL);

100: CMOS_WRITE((save_control(RTC_SET), RTC_CONRTOL);

539: CMOS_WRITE((save_control(RTC_SET), RTC_CONRTOL);(a) Buggy Code (linux-2.6.6/arch/mips/dec/time.c)
Figure 7.

(b) Its Correspondant (linux-2.6.6/arch/alpha/kernel/time.c)

A Real Bug in Identified Type-3 Code Clones in the first case study

1) Type-2b Code Clone Extraction: It took about 5 hours
to check all the code clones included in S (b)−(a) . In thisinvestigation, we could identify a total of 11 problematic
code clones. The number of identified problematic code
clones was much less than the number that we had expected.
Figure 6 shows an identifier-level bug identified in
S (b)−(a) . The bug in Figure 6(a) is in the line 1159 of Figure6(b). Variable KEYLARGO FCR0 has to be replaced with
KEYLARGO FCR1.
2) Type-3 Code Clone Extraction: The large number ofcode clones in S (d)−(c) (2,915) prevented us from browsing
all the code clones. We randomly chose some code clones
from the set (the number of chosen code clones is 524, whichis the same as the number of code clones in S (b)−(a) ). It took
about 5 hours to check the chosen code clones. As a result,
we could identify a total of 11 problematic clone pair.
Figure 7 shows a statement-level bug identified from thechosen code clones. The bug is that, there is no statementthat calls spin lock function in Figure 7(a). We couldn’t
identify which of Figure 7(a) and 7(b) is original code andwhich is pasted code. However, the code clones are very
likely to have been generated by copy-and-paste, and our
method could identify it as problematic one.
D. Discussion
We confirmed that subtraction results were much smaller
than the original one. That means it is costless to use

subtraction result for identifying problematic code clones.
Besides, through this case study, in the case that we used theoriginal results, we could not what kinds of problem were in
the code clones, so that we had to very carefully investigate
each code clone. On the other hand, in the case that used
the subtraction result, we understand what kinds of problem
were in the code clones. For example, if we investigate type2b code clones, we concentrate on only consistency between
code clones. Consequently, it is very likely that the proposed
method shorten investigation time required for investigatinga code clone.
VI. R ELATED W ORK
There are some static analysis tools for finding latentbugs and issues that hinder software development and maintenance [13], [14]. They analyze program source code orJava byte code, and they identify problematic code. Theiridentifications are mainly based on heuristics, and various
kinds of heuristics are adopted. However, such tools cannot
identify bugs that were identified by the proposed method
because the bugs can be identified only by detecting code
clones. Therefore, the proposed method is not a rival of suchstatic analysis tools. We can use the both of the proposed
method and the static analysis tools at the same time forenhancing the quality of the program source code.
Li et al. developed a code clone detection tool, CP-Miner[11]. CP-Miner has a capability for detecting all types ofcode clones of the new classification described in Section III.
CP-Miner also reports copy-and-paste related bugs using ametric UnchangedRatio. Our approach is different from the
CP-Miner in the following points.
• CP-Miner identifies copy-and-paste related bugs from
C/C++ source code. On the other hand, our approachis not restricted to a certain programming language
because our approach doesn’t directly analyze programsource code. Our approach can be applied to sourcecode of any program language if utilized detection tools
can handle it.
• CP-Miner’s bug identification is based on UnchangedRatio. The metric represents mapping relationship of
only identifiers, and statements mapping is not counted.
Hence, CP-Miner cannot detect copy-and-paste bugson the statement-level. On the other hand, our approach can detect both identifier-level and statementlevel bugs.
• CP-Miner uses a UnchangedRatio threshold for reducing false positive on bug identification. However, ourapproach doesn’t use any filtering, so that there are somany false positives. In order to be sophisticated as
more practical approach, some kinds of filtering false
positives are mandatory.
Jiang et al. proposed a method for detecting bugs incode surrounding duplicated regions [10]. Inconsistencies ofsurrounding conditional statements such as if, while, andfor are identified as bug candidates. For example, if thetype of a conditional statement is different from the typeof its corresponding conditional statement, they are bugcandidates. Their approach can identify bugs not only incode clones but also in their surrounding code, which is a
big advantage over other techniques for identifying copyand-paste related bugs.
VII. C ONCLUSION
In this paper, firstly we proposed a new classification
scheme of code clones for dividing problematic code clones
from non problematic ones. The new classification scheme isbased on Bellon’s classification, and it is simple and easy tounderstand. Secondly, we proposed a method for efficiently
extracting a set of code clones falling into each category of
the new classification. We can say that the proposed method
can be applied to various kinds of software systems for thefollowing reasons.
• The proposed method uses existing detection tools, andit doesn’t directly analyze program source code. Thatmeans the proposed method can be applied to sourcecode of any programming language if the used detection
tools can handle the programming language. Currently,
there are many detection tools and they can handle
several popular programming languages such as Java,
C/C++, C#, Visual Basic, and so on.

The proposed method consists of simple operations, andit has high scalability.
Thirdly, the proposed method was applied to a famous realsystem, Linux Kernel. As a result of the application, we
could identify known bugs, likely to be bugs, and other kindsof issues within a relatively short time frame.
Of course, there are so many things to do. As the next
step of this research, we are going to do the followings.
• In the case study described in this paper, we didn’t
investigate false negatives, which are problematic code
clones that were not extracted by the subtraction.
However, for evaluating the usefulness of the proposed
method more faithfully, we have to investigate false
negatives.
• At present, we have used only three detection tools(CCFinder, CCFinderX, and Deckard). For evaluating the versatility of the proposed method, we have to
conduct more case studies using other detection tools.
•

ACKNOWLEDGMENT
This work is being conducted as a part of Stage Project,
the Development of Next Generation IT Infrastructure, supported by Ministry of Education, Culture, Sports, Scienceand Technology. It has been performed under Grant-inAid for Scientific Research (C)(20500033) supported by theJapan Society for the Promotion of Science.
R EFERENCES[1] M. Kim, L. Bergman, T. Lau, and D. Notkin, “An Ethnographic Study of Copy and Paste Programming Practices
in OOPL,” in Proc. of 2004 International Symposium on
Empirical Software Engineering, Aug 2004, pp. 83–92.
[2] I. Baxter, A. Yahin, L. Moura, M. Anna, and L. Bier,“Clone Detection Using Abstract Syntax Trees,” in Proc. ofInternational Conference on Software Maintenance 98, Mar
1998, pp. 368–377.
[3] M. Fowler, Refactoring: improving the design of existingcode. Addison Wesley, 1999.
[4] S. Bellon, R. Koschke, G. Antoniol, J. Krinke, and E. Merlo,“Comparison and Evaluation of Clone Detection Tools,” IEEE
Transactions on Software Engineering, vol. 31, no. 10, pp.
804–818, Oct 2007.
[5] E. Burd and J. Bailey, “Evaluating Clone Detection Tools forUse during Preventative Maintenance,” in Proc. of the 2ndIEEE International Workshop on Source Code Analysis andManipulation, Oct 2002, pp. 36–43.
[6] “Clone Detection Literature,” http://www.cis.uab.edu/tairasr/
clones/literature/.
[7] B. S. Baker, “Parameterized Duplication in Strings: Algorithms and an Application to Software Maintenance,” SIAM
Journal on Computing, vol. 26, no. 5, pp. 1343–1362, Oct
1997.

[8] “CCFinderX,” http://www.ccfinder.net/.
[9] C. Kapser and M. W. Godfrey, “Improved Tool Support for
the Investication of Duplication in Software,” in Proc. of the
21st International Conference on Software Maintenance, Sep
2005, pp. 305–314.
[10] L. Jiang, Z. Su, and E. Chiu, “Context-Based Detection ofClone-Related Bugs,” in Proc. of the the 6th joint meetingof the European software engineering conference and the
ACM SIGSOFT symposium on The foundations of software
engineering, Sep 2007, pp. 55–64.
[11] Z. Li, S. Lu, S. Myagmar, and Y. Zhou, “CP-Miner: Finding
Copy-Paste and Related Bugs in Large-Scale Software Code,”IEEE Transactions on Software Engineering, vol. 32, no. 3,
pp. 176–192, Mar 2006.
[12] R. Wettel and R. Marinescu, “Archeology of Code Duplication: Recovering Duplication Chanins From Small Duplication Fragments,” in Proc. of the 7th International Symposium
on Symbolic and Numeric Algorithms for Scientific Computing, Sep 2005, pp. 63–70.
[13] “FindBugs,” http://findbugs.sourceforge.net/.
[14] “PMD,” http://pmd.sourceforge.net/.