2011 15th European Conference on Software Maintenance and Reengineering

Code Clone Detection on Specialized PDGs with Heuristics
Yoshiki Higo
Shinji Kusumoto
Graduate School of Information Science and Technology Graduate School of Information Science and Technology
Osaka University
Osaka University
Suita, Osaka, Japan
Suita, Osaka, Japan
Email: higo@ist.osaka-u.ac.jp
Email: kusumoto@ist.osaka-u.ac.jp

Abstract—PDG-based code clone detection is suitable fordetecting non-contiguous code clones while other detection
techniques, line-, token-, or AST-based techniques are not.
However, PDG-based detection has lower performance fordetecting contiguous code clones than the other techniques.
Moreover, PDG-based detection is time consuming, so thatapplication to actual software systems is not feasible. The
present paper proposes PDG specializations and detection
heuristics for enhancing PDG-based code clone detection.
The experiment in this paper shows that the proposed
methods are effective for PDG-based code clone detection
by applying them to 4 open source systems.

detecting non-contiguous code clones is of great
importance for detecting incorrectly modified code.
• Disadvantage: The ability of PDG-based techniques
to detect contiguous code clones is inferior to theother techniques [1]. In addition, the application of
PDG-based detection to practical software systems is
not feasible because doing so is time consuming [4],[5]The present paper proposes PDG specializations forcode clone detection. The specializations are as follows:• Introducing execution-next link expands the rangeof program slicing, so that the ability to detect
contiguous code clones is improved.
• Merging nodes reduces the computational cost ofcode clone detection. There are two reasons why
PDG-based detection is time consuming. First, an
enormous number of node pairs are used as slice
points. Second, identifying similar subgraphs requires
highly computational cost. This specialization reduces both the costs.
The present paper also uses the following heuristics forenhancing code clone detection.
• Two-way slicing enlarges code clone detection result
because there are similar subgraphs that cannot be
detected by only forward or backward slicing.
• Reducing slice points reduces the number of program slicing to detect code clones. Unnecessary slice
points are identified and removed by this heuristics.
• Neglecting small methods also reduces the numberof program slicing. Given a minimum size of code
clone to be detected, no code clone is detected from
PDGs that is smaller than the size.

Keywords-code clone, program dependency graph,

I. I NTRODUCTION
A number of code clone detection tools have been developed before now. The detection tools reveal the positionof the detected code clones in the source code. Since thereis neither a generic nor a strict definition of code clone,each detection tool has its own unique definition for code
clones that it uses to detect code clones. Consequently,
different code clones are detected by different detection
tools for the same source code.
Detection tools can be categorized based on the kinds ofdetection techniques that they employ, with the main categories including line-, token-, metrics-, Abstract-SyntaxTree- (in short, AST), and Program-Dependency-Graph(in short, PDG) based detection techniques. Each detection
technique has its own relative advantages and disadvantages, and no technique is superior to any of the othertechniques in all aspects [1], [2]. It is therefore necessary
to understand the features of each detection technique andto use appropriate techniques in the context of code clone
detection. The advantages and disadvantages of PDGbased detection are as follows:•

II. P RELIMINARIES
A. Program Dependency Graph

Advantage: PDG-based detection can detect noncontiguous code clones, whereas other detection techniques are less effective at detecting them [1]. A
non-contiguous code clone is a code clone having
elements that are not consecutively located on thesource code. It has been reported that, after copyand-pasting a code fragment, the pasted code issometimes incorrectly changed or forgotten to bechanged [3]. Modifications after copy and paste yieldnon-contiguous code clones if the modifications arelarger than token level (split clones). Consequently,

1534-5351/11 $26.00 © 2011 IEEE
DOI 10.1109/CSMR.2011.12

A PDG is a directed graph representing the dependencies between program elements (statements). A PDG
node is a program element, and a PDG edge indicatesa dependency between two nodes. There are two typesof dependencies in the traditional PDG, namely, control
dependency and data dependency [6]. When all of thefollowing conditions are satisfied, a control dependency
from statement s1 to s2 exists:• s1 is a conditional predicate, and• the result of s1 determines whether s2 is executed.
7675

built based on Komondoor’s Method [4].
In STEP 1, all nodes in PDGs are hashed based on
their contents. Nodes having the same hash value areclassified as an equivalence class. Variables and literals
used in the node are converted to their type names before
hashing. Consequently, the same hash value is generated
from syntactically identical program elements, even if thevariables are different. In the case of Figure 1, the program
elements in the 8th, 9th, 10th, and 11th lines have the samehash value, even though every of the lines uses a different
literal.
In STEP 2, a pair of nodes, (r1,r2), is selected fromeach equivalence class, and pairs of similar subgraphs that
include r1 and r2 are identified. The starting points ofthe slicings are (r1, r2), and slicing is performed in lockstep. If both predecessors (successors) have the same hashvalue, they are added to the pair of slices. In the following
situations, predecessors are not added to the pair of slices,and the slicings stop:• Predecessors (p1, p2) have different hash values.
• Predecessors (p1, p2) have the same hash value.
However, p1 (p2) already exists in the slice of r1(r2). This processing is intended to prevent an infinite
loop.
• Predecessors (p1, p2) have the same hash value.
However, p1 (p2) already exists in the slice p2 (p1).
This processing is intended to prevent the two slices
from sharing the same node.
Pairs of identified similar subgraphs are clone pairs in thebasic algorithm.
In STEP 3, if a clone pair (s1, s2), which is a pairof similar subgraphs identified in STEP2, is subsumed
by another clone pair (s10 , s20 ) (s1 ⊆ s10 ∩ s2 ⊆s20 ), it is removed from the set of detected clone pairs
because reporting the subsumed clone pairs is not useful.
The existence of such subsumed clone pairs enlarges thedetection results unnecessarily.
In STEP 4, a clone set is formed from clone pairs
sharing the same subgraphs. For example, two clone pairs(s1, s2) and (s2, s3) would be merged into one clone set{s1, s2, s3}.

1: String sample1(){2:
if(this.trueOrFalse()){
3:
if(null == this.getPath()){
4:
Project proj = this.getProject();
5:
this.setPath(proj.getBaseDir());
6:}
7:StringBuilder text = new StringBuilder();8:
text.append("String A");9:
text.append("String B");10:
text.append("String C");11:
text.append("String D");
12:
return text.toString();
13:}else{
14:
return "";
15:
}
16: }
(a) original source code
<1>

<2>
<3>

<14>

<4>

<5>
<7>
<8>
<9>
<10>
<11>

controldata<12>(b) generated PDG
Figure 1.

Example of traditional PDG

When all the following conditions are satisfied, there isa data dependency from statement s3 to s4 via variable v:• s3 defines v, and• s4 references v, and• there is at least one execution path from s3 to s4
without redefining v.
Figure 1 is a simple example of source code and a PDG
generated from the source code. Labels attached to thenodes mean the lines where their elements locate in thesource code. The node labeled <1> is the enter node of
the PDG. In this example, there are data dependencies between nodes using variables (“prog” or “text”), and there
are control dependencies between the control predicatesof the if-statements and their inner statements.

C. Weaknesses of existing PDG-based detection methods
Previous studies revealed that PDG-based detection has
the following weaknesses [1], [4], [5].
Compared to other detection techniques, the first weakness is that PDG-based detection has lower performancefor the detection of contiguous code clones. This is because consecutive program elements in the source code
do not necessarily have data dependency or control dependency. On the other hand, line- or token-based detection
methods do not consider such dependencies but rather
compare program elements textually, so that these methods
are good at detecting contiguous code clones. For example,
assume that we detect code clones from the source codeof Figures 1(a) and 2. The region from the 3rd line to the11th line of Figure 1(a) is duplicate to the same region of
Figure 2. However, if the traditional PDG is used for clone

B. Basic algorithm for code clone detection
This section describes the basic algorithm that we use
for detecting code clones with PDGs. The algorithm was

76
77

1: String sample2(){2:while(this.goOrStop()){
3:
if(null == this.getPath()){
4:
Project proj = this.getProject();
5:
this.setPath(proj.getBaseDir());
6:}
7:StringBuilder text = new StringBuilder();8:
text.append("String A");9:
text.append("String B");10:
text.append("String C");11:
text.append("String D");
12:
System.out.println(text.toString());
13:
}
14: }

<1>

<2>
<3>

<14>

<4>

<5>
<7>

Figure 2.

compared source code<8>

detection, the region from the 3rd line to the 6th line andthe region from the 7th line to the 11th line are detected
as different code clones. The two regions are connected
via the node <2> in the traditional PDG. However, thenodes <2> of the both PDGs do not have the same hashvalue, so that program slicings stop at the nodes.
The second weakness is that PDG-based detection has
a high computational complexity, which means that it
is not realistic to apply PDG-based detection to actual
software systems. There are two reasons why PDG-based
detection has a high computational complexity. The firstreason is that the number of nodes used as slice points is
considerably too high, which means that a large numberof slicings are performed in code clone detection. The
second reason is that identifying similar subgraphs is an
NP-complete problem.

<9>
<10>
control<11>

data
execution<12>

Figure 3.

PDG with execution-next linkpresented in the next subsection. Application of both thespecializations poses no problem for computational cost(see Section VII).
B. Merging directly-connected equivalence nodes

III. PDG S PECIALIZATIONS FOR C ODE C LONE
D ETECTION
This section proposes methods of PDG specializations
for code clone detection, which overcome the weaknesses
associated with PDG-based detection.

The second specialization is merging multiple nodes asa single node. This specialization also allows improvementof detection capability, so that consecutive duplicate statements in the source code are the target of merging. One
example of consecutive duplicate statements is the region
from the 8th line to the 11th line in Figure 1(a). Almost allcode clones detected from such a region is false positives[7]. For example, the region from the 8th line to the 9thline are identified as a code clone of the region from the10th line to the 11th line by forward slicing on executionnext link from the pair of nodes (<8>,<10>) in Figure 3.
However, human will never need such code clones. One
method for not detecting such false positives is that we
generate only a single node from the region, not generatenodes for every statement in the region. The number ofnodes on PDGs is decreased by this method, so that
required computational cost for detection is reduced. Notethat this specialization does not decrease the ability of thealgorithm to detect code clones because graph reachability
is preserved in the specialization, so that the ability todetect non-contiguous code clones is not decreased.
A set of consecutive nodes R = {s · · · t} are merged
into a single node if they satisfy the following conditions.
• Condition 1: There is a path from statement s tostatement t, which is formed from only executionnext link.
• Condition 2: There is no execution branch in R.

A. Introducing execution-next link
The first specialization is the introduction of executionnext link. An execution-next link is an edge that represents
the order of execution of program elements. That is, there
is an execution-next link between two nodes if the program
element represented by one of the nodes may only be
executed after the program element represented by theother node is executed. An execution-next link is exactly
equivalent to the edge of a control flow graph. Executionnext link makes it possible to detect consecutive statements
as code clones, even if they have neither data nor control
dependency.
Figure 3 shows the PDG including execution-next links
for the source code shown in Figure 1(a). In Figure 3,
the region from the 3rd line to the 6th line is directly
connected with the region from the 7th line to the 11th
line by execution-next link. Consequently, it is possible todetect the two regions as a single code clone from two
methods in Figures 1(a) and 2.
Introducing execution-next link increases the cost ofcode clone detection because it leads to more edges. However, it makes it possible to merge multiple nodes, which is7778

In other word, none of nodes in R is conditional
predicate.
• Condition 3: All the nodes in R have the same hashvalue.
• Condition 4: Any path (node set) subsuming R does
not satisfy both the conditions 2 and 3.
We herein assume that node m was generated by merging all the nodes in R. The following explains how weconstruct data, control, and execution-next links from/tothe node m.
Data Dependency: Assume that datato (p) is the set ofnodes having data dependencies to node p, and P is the setof nodes included in path R, the set of node having data
dependencies to node m is defined the following formula:∪datato (m) =datato (p) ∩ P
(1)

<1>

<2>
<3>

<14>

<4>

<5>
<7>

<8,9,10,11>
control
data

p∈P

<12>

Herein, P means a complement set of P , so that P ∪P is
all the nodes in the PDG. In the same way, the set of node
having data dependencies from node m, dataf rom (m), is
defined the following formula:∪dataf rom (m) =dataf rom (p) ∩ P(2)

Figure 4. Result of applying the mergind method to the PDG in Fig. 3•

p∈P

Control Dependency: Condition 2 ensures that all thenodes in P have control dependencies from the same node.
In the proposed method, we define that the merged nodem also has a control dependency from the same node.
Consequently, a set of nodes having control dependencies
to m is defined as the following formula:controlto (m) =controlto (s)(3)

Also, Condition 2 ensures that there is no conditional
predicate in P . Consequently, the set of control dependencies from controlf rom (m) always becomes empty:
controlf rom (m)

=

∅

(4)

Execution-next Link: Condition 2 ensures that there
is no execution branch in R, so that it is very easy todefine the sets of execution-next links from/to the nodem, executionto (m), and executionf rom (m).
executionto (m) =executionto (s)(5)

executionf rom (m) =executionf rom (t)(6)

execution

The merging method reduces the number of equivalence nodes, so that the number of program slicing
from the nodes is reduced. For example, in thecase that we detect code clones from the sourcecode shown in Figure 1(a) and 2, the nodes locatedbetween the 8th line and the 11th line of both themethods have the same hash value. If the merging
method is not applied, 8 C2 = 28 pairs of program
slicing are performed. However, most of the pairs
are consecutive statements in the source code, andpairwise program slicing from such pair does notdetect human-wanted code clones. Meanwhile if themerging method is applied to the PDGs, the consecutive 4 nodes of both the methods are merged asa single node. Consequently, only a single pair ofprogram slicing is performed from the nodes.
IV. H EURISTICS FOR E NHANCING C ODE C LONE
D ETECTION

This section introduces some heuristics for enhancing
code clone detection.
A. Two-way slicing

Figure 4 shows the PDG that the PDG shown in Figure
3 was converted with the proposed merging method. In
Figure 4, 4 nodes located between the 8th line and the11th line in the source code satisfy the 4 conditions, sothat they were merged as a single node. This specialization
reduces the following 2 kinds of computational cost.
• If the merged node appears in the path of program
slicing, the slicing cost is reduced. For example, we
assume that a program slicing is performed fromthe node <7> in Figures 3 and 4. In Figure 3, 4
hops are needed to reach the node <11> from <7>.
Meanwhile, in the case of Figure 4, only 1 hop is
required to reach the node <11>.

The first heuristics is that both forward and backward
slicings are used to identify similar subgraphs, whereas
previous approaches primarily used either forward or
backward slicing, but not both [4], [5], because a pair ofsimilar subgraphs identified by forward slicing cannot be
identified by backward slicing, and vice versa. Figures 5
and 6 show simple examples of such subgraphs with threeprogram elements (<4>,<6>, and <8>).
In Figure 5, one variable (“r”) is referenced twice ineach code clone, so that there are two data dependencies.
For example, “<4> → <6>” and “<4> → <8>” arecontained in the code clone <4,6,8>. In this instance,
backward slicings cannot detect the code clones, whereas

78
79

1:void sample3(){
2: if(this.trueOrFalse()){
3: ...
4: float r = 0.05;//tax rate
5: ...
6: float taxA = priceA * r;
7: ...
8: float taxB = priceB * r;
9: ...
10: }11:}

1:void sample4(){2: while(this.goOrStop()){
3: ...
4: float r = 0.05//tax rate;
5: ...
6: float taxA = priceA * r;
7: ...
8: float taxB = priceB * r;
9: ...
10: }11:}

1:void sample5(){2: if(this.trueOrFalse()){
3: ...
4: int price = getPrice();
5: ...
6: int tax = getTax();
7: ...
8: int amount = price + tax;
9: ...
10: }11:}

1:void sample6(){2: while(this.goOrStop()){
3: ...
4: int price = getPrice();
5: ...
6: int tax = getTax();
7: ...
8: int amount = price + tax;
9: ...
10: }11:}(a) Sample code 3(b) Sample code 4(a) Sample code 5(b) Sample code 6

<1>

<1>

<2>

<2>

<4>

<4>

control

control

<6>

<6>
data

<8>

data

<8>

execution(c) generated PDG

Figure 5.
subgraphs

execution(c) generated PDG

Example code that backward slice cannot detect similar

Figure 6.
subgraphs

forward slicings from the element <4> are able to detectthem.
In Figure 6, two variables (“price” and “tax”) arereferenced in a single statement in each code clone, so that
there are two data dependencies of the reference nodes.
For example, “<4> → <8>” and “<6> → <8>” arecontained in the code clone <4,6,8>. In this instance,
forward slicings cannot detect the code clones, whereas
backward slicings from element <8> can detect them.
Komondoor et al. showed that backward slicing is notalways helpful to detect code clones [4], which meansthat the proposed method performs unnecessary executions of backward slicing. They increase computationalcost. However, it is quite difficult to investigate all thesituations that backward slicing is not helpful and all thesituations that forward slicing is not helpful. That is why
the proposed method always performs two-way slicings.
The purpose of the proposed method is to detect manyand large similar subgraphs as much as possible. The
unnecessary executions of backward and forward slicingsincrease computational cost, but they neither reduce thenumber of detected similar subgraphs nor minify the sizeof detected similar subgraphs.

Example code that forward slice cannot detect similar

However, such large equivalence classes can occur,not because instances of such classes are generated bycopy-and-paste programming, but rather because such instances are stereotyped instructions. For example, variabledeclarations, such as int i; or int j;, and returnstatements, such as return a; or return b;, aretypical stereotyped instructions. Consequently, the second
heuristics is a size threshold for equivalence classes. If thesize of an equivalence class is larger than the threshold,then instances of that class are not used as slice points.
C. Small methods are not hashed
When we use code clone detection tools, we configure
the threshold to specify the minimum size of code clones
detected. Intraprocedural PDG is generally used in thefield of code clone detection, so that if the size of theentire PDG of a method is smaller than the threshold,code clone is never detected from it. Consequently, thethird heuristics is that small methods are not hashed in
STEP 1 of the detection process. This method prevents
program slicing from being performed on the PDGs of
small methods.
V. I MPLEMENTATION

B. Do not use excessively large equivalence classes

We developed a software tool, Scorpio, based on the
proposed methods [8]. In the detection process, STEP 2 isthe most time consuming. In STEP 2, a large number ofprogram slicings are performed in order to identify similar
subgraphs. We focus on the fact that every slicing is independent from one another, which means that the slicings
can be performed in parallel. Consequently, Scorpio identifies similar subgraphs with multithreads. We can specify
the number of threads to perform program slicing as a

In STEP 2 of the detection process, if n nodes areincluded in an equivalence class, then n(n−1)/2 pairwise
slicings are performed from the equivalence class. In thecase of actual software systems, several thousand or morenodes may have the same hash value, so that an enormous
number of pairwise slicings are performed, which is verytime consuming.

79
80

command line option of Scorpio. Parallel performanceefficiently uses the resource of multiple physical CPUs
and multi-core CPUs, so that the detection time can beshortened.
Currently, Scorpio can handle only Java source code.
However, both the basic algorithm for clone detection andthe proposed methods can be applied other programming
languages such as C/C++.

Recall can be used only for relatively comparing
detection results. For the same reason, precision is
not used for evaluation.
• In the present experiments, the locations of detectedcode clones are managed with triplet (f ,s,e) as well
as Bellon’s experiments. f is the absolute path of thefile including a given code clone, s is the start lineof the code clone, and e is the end line of the code
clone. Consequently, if a detected code clone is noncontiguous, 1 or more lines of non-duplicated code
is incorrectly counted as duplicated code.

VI. M ETHODOLOGY FOR E VALUATIONThis section introduces methodologies for evaluating the
proposed specialization and heuristics.

D. Content rate of detection result

A. Clone Reference
We use freely available code clone data from [9] as areference (a set of code clones that should be detected). In
the experiment of this paper, we use the following terms:• clone candidates: duplicated code detected by Scorpio.
• clone references: duplicated code included in thereference.
Instances of clone references are manually classified
into the following three groups:• Type 1: code clones that are identical to their correspondents. This type permits only differences inspaces and tabs.
• Type 2: code clones that include different identifiers
from their correspondents.
• Type 3: code clones that include differences beyond
Type 2 code clones. Pasted code including statement
insertions, deletions, or modifications is classified inthis type.
Types 1 and 2 code clones are contiguous, and Type 3
code clones are non-contiguous.

We used the following content rate to quantitatively
compare detection results:
CR(R1 , R2 ) = 100 ×| S(R1 ) ∩ S(R2 ) || S(R1 ) |(9)where:• R1 ,R2 : detection result, which is a set of clone
candidates. A clone candidate consists of a pair ofsimilar graphs. A graph is formed from a set ofprogram elements.
• S(R): program elements included in detection result
R. In the proposed method, the unit of program
elements is PDG nodes (statements in the sourcecode).
When the detection result R1 includes all of the program
elements in R2 , CR(R1 , R2 ) becomes maximum, 100%.
When R1 does not include any of the program elements
in R2 , CR(R1 , R2 ) becomes minimum, 0%.
E. Number of node comparisons
In order to quantitatively evaluate the computationalcost, we investigated the number of node comparisons in
STEP 2 of the detection process. The greater the numberof node comparisons, the higher the computational cost.

B. Good value, Ok value
We use the good value and the ok value[1] to decide
whether clone candidates match clone references. In theexperiment, We use 0.7 as the threshold, which is the samevalue used in the literature [1].

VII. E VALUATION OF EACH PROPOSED METHOD
In order to evaluate the effectiveness and efficiency ofeach of the proposed methods, we conducted experiments
on 4 open-source systems. Specifically, we evaluated theeffectiveness of the following items:• s1: effectiveness of execution-next link
• s2: effectiveness of merging nodes• h1: effectiveness of two-way slicing• h2: effectiveness of neglecting excessively large
equivalence classes• h3: effectiveness of neglecting small methods

C. Recall
We calculate recall for evaluating detection capability.
Assume that R is a detection result, Sref s is the setof clone references, and Sgood (R) and Sok (R) are setsof detected clones whose good or ok value with an
instance of clone references is equal to or greater than
the threshold in R. Recalls of R by using good and okvalues (Recallgood (R) and Recallok (R)) are defined asfollows:|Sgood (R)|
Recallgood (R) =(7)|Sref s ||Sok (R)|
Recallok (R) =(8)|Sref s |Table ITARGET SOFTWARE
Softwarenetbeans-javadoc
eclipse-ant
eclipse-jdtcore
j2sdk1.4.0-javax-swing

This experiment has two limitations related to recall.
• The clone references used in the experiments are not
all code clones included in the target systems. Consequently, the absolute values of recall are meaningless.

80
81

Short namenetbeans
ant
jdtcoreswing

Lines of code
14,36034,744
147,634
204,037

Table IV
N UMBER OF DETECTED CLONE REFERENCES
ID
clone references
A1 good
A1 ok
A2 good
A2 ok
A3 good
A3 ok
B1 good
B1 ok
B2 good
B2 ok
B3 good
B3 ok

Type 1
6
1
2
3
4
3
4
3
5
3
4
3
5

netbeans
Type 2
33
3
5
4
13
5
16
8
18
8
18
9
19

Type 3
16
2
2
3
3
3
3
4
13
5
13
4
13

Type 1
4
1
2
1
3
0
3
1
3
1
3
0
3

ant
Type 2
24
2
2
3
6
3
6
5
6
6
8
5
8

Type 3
2
0
0
1
1
1
1
0
0
1
1
1
1

The experimental targets are the software systems listed
in Table I. The exact versions of the systems that weused are available on [9]. In the remainder of this section,
every software is called by the name of ‘Short name’
column. The ‘Lines of code’ column indicates the total
number of lines of code in the .java files. We detectedcode clones (similar subgraphs) having six or more nodes
in this experiment.

Type 1
120
19
76
40
92
29
94
37
99
51
98
34
100

jdtcoreType 2
866
29
221
179
370
148
390
251
459
196
456
170
472

Type 3
359
8
50
62
126
60
135
61
143
67
138
60
153

swing
Type 2
595
34
54
47
89
68
357
59
326
71
354
71
360

Type 1
145
22
39
29
46
32
56
31
54
36
58
34
58

Type 3
37
6
12
11
16
12
21
12
19
13
20
12
23

Next, we investigated the effect of two-way slicingson the detection of clone references. Table IV shows theresults. The result indicates that, in most cases, two-way
slicings could detect more clone references than one-way
slicing in isolation. In a few cases, some code clones thatwere detected using one-way slicing were not detectedby two-way slicings (e.g., the Type 1 clone in ant).
This is because some code clones were inappropriately
enlarged by two-way slicings; inappropriate enlargement
yields lower good and ok values, so that the code clones
did not match the clone references.
Finally, we investigated the degree to which two-way
slicings increased the computational cost. Table V showsthat the order of computational cost is “ backward slicings< forward slicings < two-way slicings”, with the magnitude of the increase differing among targets. The largest
increase, approximately 800-fold, is between A1 and A3

A. h1: Effectiveness of two-way slicing
First, we evaluated the degree to which detected code
clones were enlarged with two-way slicings with Eq. 9.
Table II lists the configurations of the detections. For
example, detection A1 uses backward slicing, however,it does not use forward slicing and execution-next link.
The content rates of the detections are shown in Table III.
Table III shows that two-way slicings enlarged the size of
detected code clones for all the systems. This is because
there often exist code clones that cannot be detected only
by backward or forward slicing.

Table VN UMBER OF NODE COMPARISONS
Table IID ETECTION CONFIGURATION
ID
A1
A2
A3
B1
B2
B3

SoftwareDetection configuration
backward slicing forward slicing
execution-next link
×
×
×
×
×
×
×

netbeans

jdtcoreTable IIIC ONTENT RATES BETWEEN DETECTION METHODS USING TWO - WAY
AND ONE - WAY SLICING
Softwarenetbeans

jdtcoreContent rate
CR(A3,A1) = 21.6 %CR(A3,A2) = 50.7 %CR(B3,B1) = 75.8 %CR(B3,B2) = 82.3 %CR(A3,A1) = 55.0 %CR(A3,A2) = 65.7 %CR(B3,B1) = 77.7 %CR(B3,B2) = 80.3 %Software
ant

swing

ID
A1
A2
A3
B1
B2
B3
A1
A2
A3
B1
B2
B3

# of node cmpr.
135,385
551,331
110,356,247
327,889
663,348
101,104,540
58,155,404
346,223,464
1,382,195,451
118,144,589
408,615,802
1,431,922,235

Software

ant

swing

ID
A1
A2
A3
B1
B2
B3
A1
A2
A3
B1
B2
B3

# of node cmpr.
567,891
4,942,013
10,388,934
951,183
5,289,877
11,295,018
16,123,841
331,698,602
525,716,585
28,427,935
342,132,984
528,963,280

Table VI
C ONTENT RATES BETWEEN DETECTION WITH AND WITHOUTEXECUTION - NEXT LINK

Content rate
CR(A3,A1) = 44.6 %CR(A3,A2) = 55.5 %CR(B3,B1) = 64.1 %CR(B3,B2) = 70.3 %CR(A3,A1) = 45.6 %CR(A3,A2) = 56.8 %CR(B3,B1) = 73.6 %CR(B3,B2) = 75.8 %Softwrenetbeans

jdtcore81
82

Content rate
CR(B1,A1) = 25.8 %CR(B2,A2) = 59.2 %CR(B3,A3) = 96.1 %CR(B1,A1) = 65.0 %CR(B2,A2) = 76.9 %CR(B3,A3) = 94.0 %Software
ant

swing

Content rate
CR(B1,A1) = 57.4 %CR(B2,A2) = 74.1 %CR(B3,A3) = 93.9 %CR(B1,A1) = 60.9 %CR(B2,A2) = 71.5 %CR(B3,A3) = 95.7 %Table VII
C HANGE IN THE NUMBER OF NODE COMPARISONS BY INTRODUCING COMPUTATIONAL COST REDUCTION METHODS ( NUMBERS IN PARENTHESESINDICATE THE RATE OF DETECTION WITHOUT APPLYING THE PROPOSED METHODS )Softwarenetbeans
ant
jdtcoreswing

s2: merging
nodes
39,507(39.1%)
9,818(86.9%)
1,031,635(72.0%)
408,196(77.2%)

thrs.100
46,276(45.8%)
2,056(18.2%)
42,941(3.0%)
16,584(3.1%)# of node comparisons (×103 )h2: equivalence classthrs.200 thrs.300 thrs.500
100,713 100,713
100,713(99.6%)(99.7%)(99.6%)
4,436
7,388
7,388
(39.3%)(65.4%)(65.4%)
344,209 393,344 615,456(24.0%)(27.5%)(43.0%)
35,86041,774 100,153(6.6%)(7.9%)(18.9%)of netbeans. The above evaluation confirmed that:• two-way slicings can detect more clone references
than one-way slicings in isolation;• however, this increases the computational cost.

thrs.1,000
101,104(100.0%)7,388(65.4%)
699,470(48.8%)
137,676(26.0%)

h3: small
methods
100,755(99.7%)
8,844(78.3%)
1,380,464(96.4%)
438,090(82.8%)by less than 2-fold. When two-way slicings were used, it
remained approximately unchanged.
The above evaluation indicates that:• Execution-next link enables the detection of both thecontiguous and non-contiguous clone references;• however, this increases the computational cost. The
degree of increase depends on which slicing is used
for detection.

B. s1: Effectiveness of execution-next linkFirst, we evaluated the degree to which detected code
clones were enlarged by execution-next link. In this evaluation, we calculated the content rate using Eq. 9, where
R1 is the detection result with execution-next link and E2
is the detection result without it. The results are shown in
Table VI, which indicates that:1) content rates were relatively low when only backward slicings were used, and2) content rates were relatively high when two-way
slicings were used.
The reason for 1) is that fewer nodes can be reached using
only backward slicings compared to forward slicings. The
small number of node comparisons obtained with only
backward slicings as shown in Table V support this assertion. In addition, execution-next link drastically increased
the number of reachable nodes. The reason for 2) is that
more nodes were reachable using two-way slicings, andexecution-next link did not drastically increase the numberof reachable nodes. In all cases, the content rates wereconsiderably less than 100%, indicating that executionnext link always enlarged the detected code clones.
Next, we investigated the effect of execution-next linkon the detection of clone references. Table IV shows theresult. In most cases, more clone references were detectedwith execution-next link. However, in other cases, inappropriately enlarged code clones were identified, which meansthat the number of detected clone references decreased.
The purpose of execution-next link is to improve theability to detect contiguous code clones. However, the results of this investigation indicate that execution-next linkincreased the number of detected non-contiguous clone
references in addition to contiguous clone references.
Table V shows the number of node comparisons forthe cases in which execution-next link was either used
or not used. The difference between detection with andwithout execution-next link has the same appearance inall the target systems. When only backward slicings wereused, the number of comparisons increased by 2- or 3fold. When only forward slicings were used, it increased

C. s2,h2,h3: Effectiveness of merging nodes, neglecting
excessively equivalence classes, and neglecting small
methods
In this evaluation, we used the B3 configuration because
it has the highest computational cost.
Table VII shows the degree to which each proposedcost reduction method affected the number of node comparisons. The magnitude of reduction was varied fromsoftware when the Merging Directly-Connected Equivalence Nodes rule was applied and the number of node
comparisons decreased by 39% to 87%. Table VIII shows
how much the numbers of nodes and edges are decreased
by applying the method. The method reduced a small
percent of nodes and edges, so that it merged bottleneck
parts of PDGs for node comparisons. When the Do not use
excessively large equivalence classes rule was applied, i.e.,a smaller threshold or a larger target software systems was
Table VIIIT HE SIZE OF PDG S . (H EREIN , traditional MEANS THE PDG THATCONTAIN DATA AND CONTROL DEPENDENCIES . execution MEANS THE
PDG THAT CONTAIN DATA , CONTROL , AND EXECUTION - NEXT LINKS .
merged MEANS THE PDG WHERE CONSECUTIVE EQUIVALENCENODES ARE MERGED )Softwarenetbeans

ant

jdtcore

swing

82
83

PDG
traditional
execution
mergedtraditional
execution
mergedtraditional
execution
mergedtraditional
execution
merged# of nodes
6,557
6,557
6,060
12,505
12,505
12,12677,49377,49373,88582,824
82,82478,783

data
4,700
4,700
4,362
11,26911,26910,99891,617
91,61788,44375,56075,55073,026# of edges
control execution
5,626
0
5,626
6,144
5,131
5,647
10,4230
10,423
12,37910,073
12,00264,701064,701
77,98061,26374,59568,310068,31078,11064,37074,050Table IX
C ONTENT RATES BETWEEN DETECTIONS USING THE COMPUTATIONAL COST REDUCTION METHODS AND DETECTIONS PERFORMED WITHOUTTHE COMPUTATIONAL COST REDUCTION METHODS

Softwarenetbeans
ant
jdtcoreswing

s2: merging
nodes
98.45 %
99.15 %
99.40 %
98.45 %

thrs.100
100 %96.58 %
91.25 %
93.94 %

Content rate
h2: equivalence classthrs.200
thrs.300
thrs.500
100 %
100 %
100 %
99.48 % 99.82 % 99.82 %94.62 % 96.49 % 97.35 %96.43 % 97.34 % 98.52 %thrs.1,000
100 %99.82 %
99.00 %
99.70 %

h3: small
methods
100 %
100 %
100 %
100 %

Table XN UMBER OF DETECTED CLONE REFERENCES USING THE COMPUTATIONAL COST REDUCTION METHODS

Softwarenetbeans

ant

jdtcore

swing

Type
Type 1
Type 2Type 3
Type 1
Type 2Type 3
Type1
Type2
Type3
Type1
Type2
Type3

without
the methods
good
ok
2
5
9
22
8
14
0
3
6
10
1
1
33
101
314
619
130
214
31
55
74
360
12
22

s2: merging
nodes
good
ok
2
5
10
22
9
14
0
3
6
10
1
1
36
102
322
624
130
214
31
56
72
360
13
23

thrs.100
good
ok
2
5
9
22
8
14
0
3
6
10
1
1
22
97
131
398
56
128
31
55
70
358
12
21

h2: equivalence classthrs.200
thrs.300
thrs.500
good
ok good
ok
good
ok
2
5
2
5
2
5
9
22
9
22
9
22
8
14
8
14
8
14
0
3
0
3
0
3
6
10
6
10
6
10
1
1
1
1
1
1
26
98
28 10028 100184 450
297 598
298 599
73 149128 205
128 205
31
55
31
55
31
55
72 35972 35973 360
12
22
12
22
12
22

thrs.1,000
good
ok
2
5
9
22
8
14
0
3
6
10
1
1
32 101
313 619
129 21031
55
73 3601222

h3: small
methods
good
ok
2
5
9
22
8
14
0
3
6
10
1
1
33
101
314 619130 21431
55
74 36012
22

are not hashed rule was applied, the number of detectedclone references was not affected at all.
Based on the above evaluation, we draw the following
conclusions:• The Merging Directly-Connected Equivalence Nodes
rule decreases the computational cost. The degree of
decreasing is varied from software. In addition, themethod is partly-effective to improve recall of clone
detection.
• The Do not use excessively large equivalence classes
rule was effective in reducing the computational costproducing very few false negatives.
• The Small methods are not hashed rule had little
impact on the computational cost. However, the application of this method did not produce any true
negatives.

used, the more drastically the number of node comparisonsdecreased. For example, for the case in which the threshold
was 100 on jdtcore, the number of node comparisons was
3.0% of the value for the case in which it was not applied.
When the Small methods are not hashed rule was applied,the number of comparisons decreased by 78% to 99%.
Next, using Eq. 9, we investigated the effect of the
proposed cost reduction methods on the number of clone
candidates. Table IX summarizes the content rates of thedetections. When the Merging Directly-Equivalence Nodes
rule was applied, the content rates exceed 98% for all thetarget systems. That means that the rule hardly had an
impact on detection result. When the Do not use excessively large equivalence classes rule was applied, all of thecontent rates exceeded 90% for every target. In addition,
the greater the threshold, the higher the content rate. When
the Small methods are not hashed rule was applied, thecontent rates were 100% for all of the detections. This isbecause this rule filtered out only small methods in which
no clone candidates was detected.
Third, we investigated the effect of the proposed cost
reduction method on the detected clone references. Table
X shows the result. When Merging Directly-Connected
Equvalence Nodes rule was applied, the detected clone
references were equal to or greater than the detection
where it was not applied. Consequently, it has a small
contribution to improve recall of clone detection. When
the Do not use excessively large equivalence classes rule
was applied, the number of detected clone references did
not decrease for netbeans, ant, or swing. However, in thecase of jdtcore, the number of detected clone references
decreased at all of the thresholds. When the Small methods

VIII. R ELATED R ESEARCH
Komondoor et al. first applied program slicing to code
clone detection [4]. In their method, program statements
and control predicates are nodes of PDGs. Backward
slicing is mainly used in the identification, and forward
slicing is performed only from matching predicates. Theirmethod was applied to several open-source software systems written in the C language. The application result
demonstrated the capability of program slicing to detect
non-contiguous code clones.
Krinke proposed a fine-grained PDG, which he applied
to code clone detection [5]. In the fine-grained PDG,
nodes are mapped one-to-one onto nodes of an abstract
syntax tree, which means that the number of nodes infine-grained PDGs is much greater than the number of8384nodes in traditional PDGs. Consequently, it takes longer
to detect code clones using fine-grained PDGs. In order toalleviate this problem, Krinke proposed a k-limited searchin which similar subgraphs are searched within k hops.
Jia et al. proposed a hybrid method to detect noncontiguous code clones [10]. In this method, contiguous
code clones are firstly detected using a suffix-comparison
algorithm as string- and token-based detection tools. Second, surrounding statements having control or data dependency with the detected code clones are merged if thecorresponding code clones also have the same surrounding
statements. A case study revealed that their hybrid method
could rapidly detect more non-contiguous code clones thanDuplix, which is an implementation of Krinke’s method[5]. The hybrid method of Jia et al. is suitable for detecting
both contiguous and non-contiguous code clones [10]. The
difference between their hybrid method and the method
proposed herein is that their method requires core parts(contiguous code clones of a certain length) to detect
non-contiguous code clones, whereas the proposed method
does not.
Gabel et al. proposed a scalable detection method forsemantic code clones [11]. Their method is an enhanced
version of an AST-based detection method, Deckard [12].
They defined the semantic thread, which was used formapping and detecting similar subgraphs in PDGs, andfor detecting similar subtrees in ASTs.
Roy et al. proposed a lightweight detection method
for near-miss clones, which are intentionally copied andpasted codes [13]. Their method relies extensively on TXL[14] to realize the following:• detect code clones in meaningful units,• absorb the differences of source code formats, and• flexibly normalize tokens and structures.
We are especially interested in the differences amongcode clones detected by the proposed methods, Jia’s
method [10], Gabel’s method [11], and Roy’s method [13],because all of these methods are able to successfully detectboth contiguous and non-contiguous code clones and havehigh scalabilities.

IT Infrastructure, supported by the Ministry of Education,
Culture, Sports, Science, and Technology of Japan. This
study has been supported in part by Grants-in-Aid for Scientific Research (A)(21240002) and (C)(20500033) fromthe Japan Society for the Promotion of Science, and Grantin-Aid for Young Scientists (B)(22700031) from Ministryof Education, Science, Sports and Culture.
R EFERENCES[1] 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.
[2] E. Burd and J. Bailey, “Evaluating Clone Detection Tools
for Use during Preventative Maintenance,” in Proc. of the
2nd IEEE International Workshop on Source Code Analysis
and Manipulation, Oct. 2002, pp. 36–43.
[3] M. Balint, T. Girba, and R. Marinescu, “How Developers
Copy,” in Proc. of the 14th IEEE International Conference
on Program Conprehension, June 2006, pp. 56–68.
[4] R. Komondoor and S. Horwitz, “Semantics-preserving procedure extraction,” in Proc. of the 27th ACM SIGPLANSIGACT on Principles of Programming Languages, Jan.
2000, pp. 155–169.
[5] J. Krinke, “Identifying Similar Code with Program Dependence Graphs,” in Proc. of the 8th Working Conference on
Reverse Engineering, Oct. 2001, pp. 301–309.
[6] M. Weiser, “Program slicing,” pp. 439–449, May 1981.
[7] Y. Higo, T. Kamiya, S. Kusumoto, and K. Inoue, “Method
and Implementation for Investigating Code Clones in a
Software System,” Information and Software Technology,
vol. 49, no. 9-10, pp. 985–998, Sep. 2007.
[8] “Scorpio,” http://sdl.ist.osaka-u.ac.jp/∼higo/cgi-bin/moin.
cgi/scorpio-e/.
[9] “Detection of Software Clones,” http://bauhaus-stuttgart.de/clones/.
[10] Y. Jia, D. Binkley, M. Harman, J. Krinke, and M. Matsusita,“KClone: A Proposed Approach to Fast Precise Code Clone
Detection,” in Proc. of the 3rd International Conference on
Software Clones, Mar. 2009.

IX. C ONCLUSION
In the present paper we have proposed PDG specializations and heuristics for enhancing code clone detection.
In addition, we experimentally confirmed that each of the
proposed methods is effective either for improving thestringency of detection or for reducing detection time.
In the future, we intend to use interprocedural PDGs todetect code clones. Although using interprocedural PDGs
is more time consuming, more interesting and more beneficial code clones will be detected, because if functionalities
straddling two or more methods are identical, they aredetected as a single clone set. We can therefore recognize
larger identical functionalities in the system.

[11] M. Gabel, L. Jiang, and Z. Su, “Scalable Detection of
Semantic Clones,” in Proc. of the 30th International Conference on Software Engineering, May 2008, pp. 321–330.
[12] L. Jiang, G. Misherghi, Z. Su, and S. Glondu, “DECKARD:
Scalable and Accurate Tree-based Detection of CodeClones,” in Proc. of the 29th Intenational Conference on
Software Engineering, May 2007, pp. 96–105.
[13] C. K. Roy and J. R. Cordy, “Nicad: Accurate detection ofnear-miss intentional clones using flexible pretty-printing
and code normalization,” in Proc. of the 16th IEEE International Conference on Program Comprehension, June
2008.

ACKNOWLEDGMENTS[14] J. R. Cordy, “The txl source transformation language,” inProc. of the 4th workshop on Language Description, Tools,
and Applications, 2006, pp. 190–210.

The present research is being conducted as a part of
the Stage Project, the Development of Next Generation

84
85