Technical Report, Graduate School of Information Science and Technology, Osaka University

Revisiting Capability of PDG-based
Clone Detection
Yoshiki Higo, Hiroaki Murakami, and Shinji Kusumoto
Graduate School of Information Science and Technology,
Osaka University{higo, h-murakm, kusumoto}@hist.osaka-u.ac.jp

November, 2013
Abstract
Code cloning is an active research topic in the field of software engineering over the last two decades.
Recently, many research efforts have been focusing on detecting clones from very large scale sourcecode and detecting clones incrementally from multiple versions of source code. However, PDG(Program
Dependency Graph)-based detection techniques have not been researched very actively over the last several
years. In this paper, we revisit capability of the PDG-based clone detection and discuss its potential andimportance. Besides, we propose new techniques, which increase capability of the PDG-based clone
detection. The proposed techniques have already been implemented as a software tool, SCORPIO, which
is open to the public. We evaluated the proposed techniques on four open source software by using thetool. The application result showed that the proposed techniques were able to detect more clones to be
detected than conventional techniques without raising the rate of false positives.

I. Introduction
Until just a decade ago, all the people related to software development (e.g., engineer, researcher)thought all the clones in source code have negative impacts on activities of software development
and maintenance. Therefore, many research efforts have been proposed various techniques for
detecting, visualizing, refactoring, and modifying code clones [1, 2].
However, in the last decade, many researcher reported that clones do not necessarily makemischief. For example, Kapser and Godfrey reported their empirical study on device drivers [3].
When a programmer develops a new device driver, s/he usually reuses code of existing drivers
by copy-and-past operations because most of the functionalities required for the new driver are
the same as ones required for the old drivers. In other words, functionalities required for the
new drivers have already been implemented in the old drivers. Consequently, there are plenty ofclones among device drivers. However, Such reused code rarely cause unintended inconsistency
problems because they are very stable. Besides, Kim et al. said that refactoring clones is notnecessarily a good way for avoiding unintended inconsistencies if we consider the future evolution of software systems [4]. They found that there are code fragments that are duplicated withother code fragments only a short period of time. After they become unduplicated, they evolve
differently. Moreover, there are many empirical studies that compared code in clones with code
outside the clones [5, 6, 7, 8]. They revealed that the modification cost on cloned code is notnecessarily higher than the one on non-cloned code.
However, there is a fact that some clones make it more difficult to keep source code consistent[9, 10]. It is important to identify such bad clones efficiently. Besides, clone information canbe utilized for versatile applications such as promoting code reuse or supporting understanding1

Technical Report, Graduate School of Information Science and Technology, Osaka University

architectures of software systems [11, 12, 13, 14]. For these reasons, code cloning is an active
research topic in the field of software engineering still now. In particular, many research efforts
have been conducted on detecting clones from very large scale source code and detecting clones
incrementally in the last couple of years. [15, 16, 14, 17, 18, 19, 20].
On the other hand, PDG(Program Dependency Graph)-based detection techniques have notbeen researched very actively in the last couple of years. Authors think that the result of Bellon’s
study might be one of the reasons why the PDG-based detection is inactive in research related
to clones. In Bellon’s study, the PDG-based detection technique scored lower precision and recall
than other detection techniques [21]. In the paper, there are descriptions that the settings of theempirical study might work against the PDG-based detection. However, the low precision andrecall of the PDG-based detection might be so impressive that negative image of the PDG-based
detection spread over researchers1 .
However, the PDG-based detection has some advantages that the other detections do not have.
If two or more code fragments are detected as clones by the PDG-based technique, they havethe same data and control dependencies. Hence, clones detected by the PDG-based technique
are suited for refactoring. Hotta et al. proposed a technique that supports removing clones
by applying Form Template Method pattern [22], which is a relatively complex procedure amongrefactoring patterns [23]. Besides, the PDG-based technique can detect intertwined clones (Weshow an example of intertwined clones in Section III). Intertwined clones can be detected by noneof the clone detection techniques except the PDG-based one.
As mentioned above, the PDG-based technique has some strong points. If its weak points are
eliminated or released (its precision and recall are improved), we might be able to apply it invarious situations instead of other techniques. In this paper, we firstly consider why the PDGbased technique scored lower precision and recall than other techniques in Bellon’s study. After
that, we propose a new PDG-based detection technique.
There are the following contributions in this paper.
• We revealed why the PDG-based technique scored lower precision and lower recall thanother techniques.
• We proposed a new PDG-based detection technique solving the revealed problems.
• We implemented the proposed technique as a software tool. The tool is open to the public
in Github 2 and anyone can use it.
• We applied the tool to four open source systems, which were used in Bellon’s study. The
application result showed that the precision and recall of the proposed technique were
better than the conventional technique. Note that, in this empirical study, we used gap
information in clones, which was not used in Bellon’s study. That mean the comparison inthis experiment is more precisely than Bellon’s one.
The remainder of this paper is organized as follows: Section II introduces PDGs and PDGbased clone detections; in Section III, we discuss why the PDG-based detection scored lower
precision and recall than other detections in Bellon’s study; in Section IV, we propose a new
PDG-based detection technique that solves the problems shown in Section III; the application
result of four open source software systems and its threats to validities are described in Sections
V and VI, respectively; lastly, we conclude this paper in Section VIII
1 At July 2013, the paper [21] of Bellon’s study has approximately 250 citations by Google Scholar, which mean thepaper has a large impact on subsequent research.
2 https://github.com/YoshikiHigo/TinyPDG

2

Technical Report, Graduate School of Information Science and Technology, Osaka University

2142 public	
  int	
  literalIndexForJavaLangStringBufferDefaultConstructor()	
  {	
  
2143	
  	
  	
  	
  int	  index;	
  
2144	
  	
  	
  	
  int	
  nameAndTypeIndex;	
  
2145	
  	
  	
  	
  int	
  classIndex;	
  
2146	
  	
  	
  	
  //	
  Looking	
  into	  the	
  method	
  ref	
  table	
  
2147	
  	
  	
  	
  if	
  ((index	
  =	
  wellKnownMethods[STRINGBUFFER_DEFAULT_CONSTR_METHOD])	
  ==	
  0)	
  {	
  
2148	
  	
  	
  	
  	
  	
  classIndex	
  =	
  literalIndexForJavaLangStringBuffer();	
  
2149	
  	
  	
  	
  	
  	
  if	
  ((nameAndTypeIndex	
  =	
  ellKnownMethodNameAndTypes[DEFAULT_CONSTR_METHOD_NAME_AND_TYPE])	
  ==	
  0)	
  {	
  
2150	
  	
  	
  	
  	
  	
  	
  	
  int	
  nameIndex	
  =	
  literalIndex(QualifiedNamesConstants.Init);	
  
2151	
  	
  	
  	
  	
  	
  	
  	
  int	  typeIndex	
  =	
  literalIndex(QualifiedNamesConstants.DefaultConstructorSignature);	
  
2152	
  	
  	
  	
  	
  	
  	
  	
  nameAndTypeIndex	
  =	
  wellKnownMethodNameAndTypes[DEFAULT_CONSTR_METHOD_NAME_AND_TYPE]	
  =	
  currentIndex++;	
  
2153	
  	
  	
  	
  	
  	
  	
  	
  writeU1(NameAndTypeTag);	
  
2154	
  	
  	
  	
  	
  	
  	
  	
  writeU2(nameIndex);	
  
2155	
  	
  	
  	
  	
  	
  	
  	
  writeU2(typeIndex);	
  }	
  
2156	
  	
  	
  	
  	
  	
  index	
  =	
  wellKnownMethods[STRINGBUFFER_DEFAULT_CONSTR_METHOD]	
  =	
  currentIndex++;	
  
2157	
  	
  	
  	
  	
  	
  if	
  (index	
  >	
  0xFFFF){	
  
2158	
  	
  	
  	
  	
  	
  	
  	
  this.classFile.referenceBinding.scope.problemReporter()	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  .noMoreAvailableSpaceInConstantPool(this.classFile.referenceBinding.scope.referenceType());	
  }	
  
2159	
  	
  	
  	
  	
  	
  //	
  Write	  the	
  method	
  ref	  constant	
  into	  the	  constant	
  pool	
  
2160	
  	
  	
  	
  	
  	
  //	
  First	  add	  the	
  tag	
  
2161	
  	
  	
  	
  	
  	
  writeU1(MethodRefTag);	
  
2162	
  	
  	
  	
  	
  	
  //	
  Then	  write	  the	
  class	
  index	
  
2163	
  	
  	
  	
  	
  	
  writeU2(classIndex);	
  
2164	
  	
  	
  	
  	
  	
  //	
  The	
  write	  the	
  nameAndType	
  index	
  
2165	
  	
  	
  	
  	
  	
  writeU2(nameAndTypeIndex);	
  }	
  
2166	
  	
  	
  	
  return	
  index;	
  }	
  (a) source code (eclipse-ant/src/zip/ZipEntry.java)data	
  dependency	
control	
  dependency	

2142	

2143	

2144	

2145	

2147	

2148	

2166	

2149	

2161	

2157	

2158	

2150	

2153	

2163	

2151	

2154	

2165	

2152	

2155	

2156	

(b) program dependency graph

Figure 1: Example of program dependency graph (this source code is included in the target of Bellon’s experiment
[21])

II.

Preliminaries

Here, we explain a definition of PDG and introduce a PDG-based clone detection techniquebriefly. If readers already have knowledge about them, please skip this section.

I.

Program Dependency GraphA PDG is a directed graph that represents the dependencies among program elements (statements or conditional predicates). A PDG node is a program element, and a PDG edge shows adependency among two nodes. There are two types of dependencies in PDGs, namely, control
3Technical Report, Graduate School of Information Science and Technology, Osaka University

dependency and data dependency [24].
If all of the following conditions are satisfied, there is a control dependency from statement
s1 to s2 :• s1 is a conditional predicate, and• the result of executing s1 determines directly whether s2 is executed or not.
If all the following conditions are satisfied, there is a data dependency from statement s3 to s4
via variable v:• s3 defines v,• s4 references v, and• there is at least one execution path from s3 to s4 without redefining v.
Figure 1 is an actual Java method and a PDG generated from the source code. Labels attachedto the nodes mean the lines where their elements are located in the source code. In this example,
there are data dependencies between nodes using variables such as classIndex, and there are also
control dependencies between the conditional predicates of the if-statements and their innerstatements. The node labeled 2142 is the enter node of the PDGs. The enter node is regarded asa conditional predicate [25]. We use this example throughout this paper to illustrate differences
between conventional and proposed PDGs.

II.

Basic Algorithm for PDG-based Clone Detection

We show the basic algorithm we use for detecting clones with PDGs. The algorithm was built
based on Komondoor’s technique [26].
STEP1: a hash value is calculated from each node in PDGs based on the syntactic contents of
their program elements. Nodes having the same hash value are grouped together. Variables
and literals in the program elements are converted to special tokens before hashing. Consequently, the same hash value is generated from syntactically identical program elementseven if the variables and the literals are different. In Figure 1, for example, two statements
located in the lines 2150 and 2151 has the same hash value.
STEP2: every pair of nodes, (r1 , r2 ), in all the groups is specified as a start point of a pairwise
program slicing in order to detect a pair of similar subgraphs that include r1 or r2 . Everypair of two slicings are performed in lock step. If predecessors (successors) of both theslicings have the same hash value, they are added to the pair of slices. If any of the following
conditions is satisfied, predecessors are not added to the slices, and slicings stop.
• Predecessors (p1 , p2 ) have different hash values.
• Predecessors (p1 , p2 ) have the same hash value. However, p1 (p2 ) already exists in theslice of r1 (r2 ). This condition is intended to prevent an infinite loop.
• Predecessors (p1 , p2 ) have the same hash value. However, p1 (p2 ) already exists in theslice p2 (p1 ). This condition is intended to prevent the two slices from sharing the samenode.
Pairs of identified similar subgraphs are clone pairs in the basic algorithm.
4Technical Report, Graduate School of Information Science and Technology, Osaka University

STEP3: if a clone pair (s1 , s2 ), which is a pair of similar subgraphs identified in STEP2, is subsumed by another clone pair (s1′ , s2′ ) (s1 ⊆ s1′ ∩ s2 ⊆ s2′ ), it is removed from the set of detectedclone pairs because reporting the subsumed clone pairs is meaningless. The existences ofsuch subsumed clone pairs enlarge the detection results unnecessarily.

III.

Research Motivation

Although some PDG-based detection techniques were proposed a decade ago [26, 27], the PDGbased detection is not an active topic the last couple of years. Authors think that, the result of
Bellon’s study might give a negative image of the PDG-based detection to researchers.
First of all, we describe the overview of Bellon’s experiment [21] briefly.
STEP1 Stefan Bellon, who is not a clone detection developer, selected the target software, which
is open to the public in his web site3 . He asked the developers of several detection tools to
detect clones and to report the results to him.
STEP2 six developers detected clones from the target using their own tools. Table 1 shows thedevelopers cooperated with Bellon, their tool names, and their detection techniques. The
detection results were sent to Bellon in the given format.
STEP3 Bellon selected 2% of the received clone pairs randomly and checked each of the selectedpairs to ensure that it was really a clone pair. He built 4,789 clone references from the fourJava software and the four C software.
In order to understand why the precision and recall of the PDG-based detection were lower
than other detections, we implemented a PDG-based detection tool with the algorithm describedin Subsection II. We detected clones from Bellon’s target software with the tool, and then we
investigated clone references that had not been detected by the tool. As a result, we found thatclone references are not likely to be detected by the PDG-based technique if they are contiguous
code fragments in the source code. For example, in Figure 1(a), we assume that the code fragmentfrom the line 2148 to the line 2165 is duplicated to a code fragment in another method. The codefragment pair should be able to be detected by token-based or line-based detection because they
are contiguous in the source code. On the other hand, the PDG-based technique cannot detect
the pair as clones. This is because the path from the node 2149 to the node 2161 must be routed
through the node 2147 in Figure 1(b). However, the slicing stops at the node 2147. This node is
3 http://www.bauhaus-stuttgart.de/clones/

Table 1: Clone detection tools used in Bellon’s experimentTool
Dup [28]
CloneDR [29]CCFinder [30]Duplix [27]
CLAN [31]Duploc [32]Comparison
Token
AST
Token
PDG
Function Metrics
Text

Developer
Brenda S. Baker
Ira D. Baxter
Toshihiro Kamiya
Jens Krinke
Ettore Merlo
Mattias Riegger

5Technical Report, Graduate School of Information Science and Technology, Osaka University

not included in the duplicated code. Hence, it is impossible to detect a clone including both thenodes 2149 and 2161 with the PDG-based technique.
Fortunately, after we had found this problem by the investigation, we came up an idea: if
there is another link between the nodes 2149 and 2161, they should be able to be detected as aclone pair. Consequently, in this paper, we investigate the following research question.
RQ1 is detection capability improved by adding an edge for each pair of two nodes whose
elements are consecutive in the source code?
Besides, the clone format used in Bellon’s study seems not to have been fit for clones detectedby the PDG-based technique. Precision and recall of the PDG-based technique might not be soaccurate in the experiment. As described in Subsection II, clones are detected by following control
and data dependencies in PDGs. Thus, in detection results of the PDG-based technique, there aremany clones whose elements are not consecutive in the source code. However, the format used in
Bellon’s study consists of a triplet ( f , s, e). f is the absolute path of the file including a given clone,s and e are the start line and the end line of the clone, respectively. Hence, there is no information
about locations of gaps even if a given clone is non-contiguous one. If we use this format for
non-contiguous clones, lines not included in a given non-contiguous clone are regarded as being
included in it. Authors actually checked how many non-contiguous clones are included in the
PDG-based detection by using the tool. Table 2 shows the number of non-contiguous clones andtheir rate in the detection results. Most of the detected clones are non-contiguous ones. However,there is no space to store locations of gaps in Bellon’s format. This fact means that matching
between clone references and detected clones might not be incorrect in the case of non-contiguous
clones. Consequently, in this paper, we investigate the following research question.
RQ2 is the number of clone references detected with gap information different from the numberof ones without it?
A big advantage of the PDG-based technique is its capability to detect intertwined clones.
Intertwined clones are ones that are tangled with their correspondent clones in the source code[26]. However, there have not been investigations on intertwined clones yet. Consequently, inthis paper, we investigate the following research questions.
RQ3 How many intertwined clones are included in detection results of the PDG-based technique?

IV. Proposed Technique
Here, we propose some techniques to improve detection capability of the PDG-based detection.
Subsections I, II, and III explain proposed techniques and then Subsection IV introduce the tool,
SCORPIO, which has been implemented with the proposed techniques.
Table 2: Ratio of non-contiguous clones detected by a PDG-based tool

Softwarenetbeans-javadoc
eclipse-ant
eclipse-jdtcore
j2sdk1.4.0-javax-swing

6# of clones
21
59
3,835
1,723

# of non-contiguous clones
19
54
3,669
1,581

ratio
90%
92%
96%
92%

Technical Report, Graduate School of Information Science and Technology, Osaka Universitydata	
  dependency	
control	
  dependency	
execution	
  dependency	

2142	

2143	

2144	

2145	

2147	

2148	

2166	

2149	

2161	

2157	

2158	

2150	

2153	

2163	

2151	

2154	

2165	

2152	

2155	

2156	

Figure 2: PDG with execution dependencies

I.

Introducing execution-next link

We introduce a new kind of dependency into PDGs, which we call execution-next link. An
execution-next link is an edge representing the order of executions of the program elements.
There is an execution-next from node “v” to node “u” if the program element of “u” may be executed after the program element of “v” is executed. An execution-next link is exactly equivalent
to an edge in control flow graphs. Execution-next links make it possible to detect consecutive
program elements as clones even if they have neither data nor control dependency.
Figure 2 shows a PDG including execution-next links for the conventional PDG shown in
Figure 1(b). By following execution-next links. slicings can reach node 2165 from node 2148
without going through nodes 2147 or 2166. Consequently, a code fragment from the line 2148 tothe line 2165 can be detected as a clone.

II.

Merging directly-connected equivalent nodes

We propose a technique to merge multiple nodes as a single node in PDGs. This technique isintended to reduce computational costs to detect similar subgraphs by decreasing the number ofnodes in PDGs. Nodes that are directly connected via execution-next links are merged in thistechnique. For example, the nodes 2154 and 2155 in Figure 2 are merged by this technique. This
proposed technique can reduce the following two types of the computational costs.
• If a merged node appears in the path of program slicing, the slicing cost is reduced. For
example, in Figure 2, we need 3 hops from the node 2153 to the node 2156 mean while in
Figure 3, only 2 hops are required for the slicing between the two nodes.
• If a merged node is used as a starting point of a slicing, the number of program slicings isdecreased because some of nodes included in the same group are merged in this technique.
For example, in Figure 2, the nodes 2154, 2155, 2163, and 2165 have the same hash values
and they are grouped together. The number of program slicings starting from this groupis 4 C2 = 6. However, most of the pairs are consecutive program statements in the source
7Technical Report, Graduate School of Information Science and Technology, Osaka Universitydata	
  dependency	
control	
  dependency	
execution	
  dependency	

2142	

2147	

2143	
  
2144	
  
2145	

2148	

2150	
  
2051	

2166	

2149	

2163	
  
2065	
2153	

2157	

2156	

2158	

2165	

2152	

2154	
  
2055	

Figure 3: PDG with merged nodes

code, and pairwise slicings from such pairs does not detect human-wanted clones. On theother hand, if this proposed technique is applied to the PDG, each of the two pairs of nodes(2154, 2155) and (2163, 2165) is merged as a single node, respectively. Consequently, only asingle pair of program slicings (2 C2 = 1) is performed from these nodes.
A set of nodes satisfying all the following conditions are merged as a single node in this
proposed technique.
CONDITION1: there is a path from the node s to the node t,and each edge forming the path isexecution-next link. Here, we assume such a path as R.
R= s, · · · , t(1)

CONDITION2: there is neither branch nor confluence on execition-next link in R.
CONDITION3: all the nodes in R have the same hash value.
CONDITION4: any path subsuming R does not satisfy both the CONDITION2 and CONDITION3.
Figure 3 is a PDG where this proposed technique has been applied to the PDG shown in
Figure 2. In this example, the following groups of nodes in Figure 2 were merged.
• 2143, 2144, and 2145.
• 2150 and 2151.
• 2154 and 2155.
• 2163 and 2165.
The remainder of this subsection explains how we construct data, control, and execution-next
links from/to merged nodes. We herein assume that node m was generated by merging all thenodes in R.
8

Technical Report, Graduate School of Information Science and Technology, Osaka University

Data dependency: assume that datato ( p) is the set of nodes having data dependencies to node p,
and P is the set of the nodes consisting of path R, the set of nodes having data dependencies
to the node m is defined the following formula:datato (m)=∪datato ( p) ∩ P

(2)

p∈ P

P means a complement set of P, which means P ∪ P are all the nodes in the PDG. In thesame way, assume that data f rom ( p) is the set of nodes having data dependencies from thenode p, data f rom (m) is defined as the following formula:data f rom (m)

=

∪
p∈ P

data f rom ( p) ∩ P(3)Control dependency: CONDITION2 ensures that all the nodes in P have control dependencies
from the same node. In this proposed technique, we define that the merged node m 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)(4)

CONDITION2 also ensures that there is no conditional predicate in P. Consequently, theset of control dependencies from the merged node m always becomes empty:
control f rom (m)

= ∅

(5)

Execution-next link: CONDITION2 ensures that there is neither branch nor confluence of executionnext link in R, so that it is very easy to define the sets of execution-next links from/to themerged node m:
executeto (m)= executeto (s)execute f rom (m) = execute f rom (t)

(6)
(7)

This proposed technique also deems to be effective for reducing false positives. The nodes
merged in this technique are consecutive program elements in the source code, and they are
repeated instructions. There is a research report that many false positives are detected from thepresence of repeated instructions in automatic clone detection [33]. Murakami et al. proposed atechnique to reduce the amount of false positives by folding repeated instructions in token-based
clone detection [34]. Consequently, even in the PDG-based clone detection, false positives should
be reduced by removing repeated instructions.

III.

Matching by subgraphWe propose calculating a hash value from every subgraph in PDGs not from every node. Herein,a subgraph is an edge and two nodes of its both ends. The number of subgraph in a PDG equals
to the number of edges in the PDG. If given two subgraphs satisfy all of the following conditions,
their hash values become the same:• dependency types of the two subgraphs are the same,• starting nodes of the two subgraphs are identical (starting nodes have the same hash value),and9Technical Report, Graduate School of Information Science and Technology, Osaka University• end nodes of the two subgraphs are identical (end nodes have the same hash value).
The clone detection algorithm using subgraph matching is the same as the basic algorithm
shown in Subsection II except the matching is changed from the node unit to the subgraph unit.
We show the difference between detections by the two units.
STEP1 a hash value is calculated from every of the subgraphs in PDGs not from every node.
Subgraphs having the same hash value are grouped together.
STEP2 pairwise slicings are performed. They start from pairs of subgraphs in the same groupand they follow pairs of the same subgraphs.
Note that, the basic algorithm shown in Subsection II performs a node-based detection, whichmeans the number of nodes in a pair of slices are the same. On the other hand, this proposed
technique performs a subgraph-based detection, so that the number of subgraphs in a pair ofslices are the same, but the number of nodes are not necessarily the same.

IV. Implementation
We have implemented a clone detection tool, SCORPIO, with the proposed techniques. The tool
is open to the public4 . Currently, SCORPIO deals with only Java language. However, it is notdifficult to expand it to other programming languages.

V. Investigation into RQs
We have conducted an experiment in order to answer the three RQs presented in Section III. We
show the RQs again here.
RQ1 is detection capability improved by adding a edge for each pair of two nodes whose elements are consecutive in the source code?
RQ2 is the number of clone references detected with gap information different from the numberof ones without gap information?
RQ3 How many intertwined clones are included in detection results of the PDG-based technique?
4 https://github.com/YoshikiHigo/TinyPDG

Table 3: Target software

10

Softwareshort name

LOC

# of clone references

netbeans-javadoc
eclipse-ant
eclipse-jdtcore
j2sdk1.4.0-javax-swing

netbeans
ant
jdtcoreswing

14,36034,744
147,634
204,037

55
30
1,345
777

Technical Report, Graduate School of Information Science and Technology, Osaka University

I.

Clone references

We used freely available clone data from Bellon’s web site5 as a reference (a set of clones thatshould be detected). In the remainder of this section, we use the following terms:
clone candidates clones detected by SCORPIO, andclone references clones included in the references
As described in Section III, the clone references do not include information about locationsof gaps for non-contiguous clones. Consequently, authors investigated the source code of all the
non-contiguous clones in the references one by one, and added the information of gap locations.
The references with gap locations are open to the public in authors’ web site6 . In this experiment,
we used the clone references with gap locations.

II.

Evaluation Indicators

Investigations into the RQ1 and RQ2 are performed by measuring precision and recall of detections. In order to measure the values, we need to check whether each of the clone candidates
matches either of the clone references or not. We use the good value and the ok value [21] forchecking the matching. The definitions of ok and good values are presented in Appendix. We use
0.7 as the threshold, which is the same value used in the literature [21].
Assume that C is a detection result (a set of clone candidates), R is the set of the clone
references, and R good (C ) and Rok (C ) are sets of clone references whose good or ok value witheither of the clone candidates in C is equal to or greater than the threshold.
Recalls of C by using good and ok values are defined as follows:
Recall good (C )=Recallok (C )=| R good (C )|| R|| Rok (C )|
| R|

(8)
(9)

Precisions of C by using good and ok values are defined as follows:
Precision good (C )=Precisionok (C )=| R good (C )||C || Rok (C )|
|C |

(10)
(11)

This experiment has a limitation related to recall and precision. The clone references usedin this experiment are not all clones included in the target systems. Consequently, the absolutevalues of recall and prevision are meaningless. They can be used only for relatively comparing
multiple detection results.

III.

Investigation for RQ1

In order to investigate RQ1, we detected clone candidates with the following three types of PDGs:
conventional PDG PDGs including data and control dependencies,
5 http://www.bauhaus-stuttgart.de/clones/
6 http://sdl.ist.osaka-u.ac.jp/~h-murakm/2013_clone_references_with_gaps/

11

Technical Report, Graduate School of Information Science and Technology, Osaka University

execution PDG PDGs including execution-next links in addition to data and control dependencies, andmerged PDG PDGs having merged nodes.
In Bellon’s study, each tool detected clones including at least 6 lines. Thus, we specified 6
nodes as the minimum threshold of SCOPIO’s clone detection. Table 4 shows the number ofclone candidates detected from each of the systems. For all of the systems, the execution andmerged PDGs detected much more clone candidates than the conventional PDG. The number ofclone candidates with the execution PDG is roughly the same as the number of clones with themerged PDG.
Table 5 shows clone references detected with each of the PDGs. The number of clone references detected with the execution or merged PDG is much more than the one with the conventional PDG.
Figure 4 shows recall and precision with the three PDGs. The recall values of the execution
and merged PDGs are at least 2-fold higher than the ones of the conventional PDGs for all thesystems. On the other hand, the precision values of the execution and merged PDGs are higher
than the ones of the conventional PDGs in some cases meanwhile the conventional PDGs higher
values than the other two PDGs in the other cases.
We calculated f-measure for comparing the detection accuracy of the three kinds of PDGs.
Figure 5 shows the calculation result. All of the f-measure of the execution and merged PDGs arehigher than the conventional PDG except the execution PDG of jdtcore with ok value. Especially,in the cases of netbeans and swing with ok value, f-measure of the execution and merged PDGs is
2-fold or more than the conventional PDG.
Consequently, our answer to RQ1 is YES. By introducing execution-next links to PDGs, thenumber of detected clone candidates and clone references, so that recall of detection was improved. On the other hand, there were cases that precision of detection was decreased becauseof many clone candidates that are not matched with clone references. In the f-measure comparison, there was only one case that the value of the execution or merged PDG was lower than theconventional PDG. For the other 15 cases, f-measure was improved. Especially, for the 10 casesin them, the value of f-measure became 2-fold or more.
Table 4: Number of clone candidates

conventional
execution
mergednetbeans
21
349
343

ant
59
165
168

jdtcore3,835
12,675
12,030

swing
1,723
5,639
5,568

Table 5: Number of detected clone references (the number in parentheses is the total number of clone references)conventional
execution
merged12

netbeans (55)
good
ok
1
2
11
26
11
26

ant (30)
good ok
1
2
4
7
3
7

jdtcore (1,345)
good
ok
10
181
139
459
148
459

swing (777)
good
ok
16
44
125 384
124 384

Technical Report, Graduate School of Information Science and Technology, Osaka Universityok	
  recall	
  

0.6	
  

good	
  recall	  good	
  precision	
  

0.09	
  

0.5	
  

0.08	
  
0.07	
  

0.4	
  

0.06	
  

0.3	
  

0.05	
  
0.04	
  

0.2	
  

0.03	
  
0.02	
  

0.1	
  

netbeans	
  

ant	
  

jdtcore	  conven5onal	  merged	  execu5on	
  execu5on	
  conven5onal	  merged	  conven5onal	  merged	  netbeans	
  swing	
  execu5on	
  execu5on	
  conven5onal	  merged	  0	
  conven2onal	  merged	  jdtcore	  execu2on	
  execu2on	
  conven2onal	  merged	  execu2on	
  
ant	
  

conven2onal	  merged	  conven2onal	  merged	
  

0.01	
  

execu2on	
  

0	
  

ok	
  precision	
  

0.1	
  

swing	  (b) Precision(a) Recall

Figure 4: Recall and Precision for merged, execution, and conventional PDGsok	
  f-­‐measure	
  

0.14	
  

good	
  f-­‐measure	
  

0.12	
  
0.1	
  
0.08	
  
0.06	
  
0.04	
  

netbeans	
  

ant	
  

jdtcore	  conven1onal	
  execu1on	
  merged	  execu1on	
  conven1onal	  merged	  conven1onal	
  execu1on	
  merged	  conven1onal	
  execu1on	
  

0	
  

merged	
  

0.02	
  

swing	
  Figure 5: F-measure for merged, execution, and conventional PDGs

IV. Investigation for RQ2
In order to answer RQ2, we also investigated how many clone references were detected without
locations of gaps. In the investigation for RQ2, we used the information of the start line and theend line for clone candidates and clone references, and we assume that all the lines between thestart and end lines are included in clones. Table 6 shows the number of detected clone references.
The values in Table 6 are the same or greater than the values in Table 5. That means matching
without locations of gaps sometimes yields incorrect results.
In order to compare the difference between clone references detected with and without locations of gaps quantitatively, we calculated Di f f good and Di f f ok with the following formulae.
13Technical Report, Graduate School of Information Science and Technology, Osaka Universityok	
  12.0%	
  

good	
  

10.0%	
  
8.0%	
  
6.0%	
  
4.0%	
  

ant	
  

jdtcore	  execu2on	
  conven2onal	  merged	  conven2onal	
  execu2on	
  merged	  conven2onal	  merged	  netbeans	
  execu2on	
  execu2on	
  conven2onal	
  

0.0%	
  

merged	
  

2.0%	
  

swing	
  Figure 6: Difference between with-gap and without-gap
nogap

nogap

Herein, we assume that R good (C ) and Rok
locations of gaps.

(C ) are a set of clone references detected without

nogap

Di f f good=

Di f f ok=|| R good (C )| − | R good (C )||
| R|
nogap

|| Rok (C )| − | Rok| R|(C )||

× 100

(12)

× 100

(13)

Figure 6 shows the calculation result. There are only three cases that there is no difference
between the clone references with and without locations of gaps. For the other 21 cases there aredifferences, and in the maximum case, the difference is over 13%.
Consequently, our answer to RQ2 is YES. There are difference between clone references detected with and without locations with gaps in 21 out of 24 cases. In some of such cases, thedifference is over 10%. Hence, we can say that it is important to consider locations of gaps formore accurate evaluation. The Bellon’s references with locations of are open to the public inauthors’ web site7 .
7 http://sdl.ist.osaka-u.ac.jp/~h-murakm/2013_clone_references_with_gaps/

Table 6: Number of detected clone references (without gaps)

Softwareconventional
execution
merged14

netbeans (55)
good
ok
4
6
14
26
13
26

ant (30)
good ok
1
2
2
9
2
9

jdtcore (1,345)
good
ok
115
334
259
606
254
604

swing (777)
good
ok
28
57
135 393
135 392

Technical Report, Graduate School of Information Science and Technology, Osaka University

25.0%	
  20.0%	
  15.0%	
  10.0%	
  netbeans	
  

ant	
  

jdtcore	  conven0onal	  merged	  execu0on	
  execu0on	
  conven0onal	  merged	  conven0onal	  merged	  execu0on	
  conven0onal	  merged	
  

0.0%	
  

execu0on	
  

5.0%	
  

swing	
  Figure 7: Rate of intertwined candidates for all Difference between with-gap and without-gap

V. Investigation for RQ3
In order to answer RQ3, we investigated how many intertwined clones were included for eachof the detection results. Herein, we define that intertwined clones do not satisfy the following
formula.
EL(c1 ) < SL(c2 )∨ SL(c1 ) > EL(c2 )(14)

We counted the number of clones that do not satisfying the formula. Table 7 shows the result.
There are intertwined clones in all the detection results except the conditional PDG of ant.
Figure 7 shows the rate of intertwined clones in the detection results. The rates are different
from system to system, and more than 20% of clone candidates are intertwined clones in the
maximum case.
Figure 8 shows a pair of intertwined clones detected from jdtcore. The lines started with “++”form a clone, and the lines started with –” form its corresponding clone. Each of the clones
implements a procedure for Java field or method, respectively. These clones can be potential
targets of refactoring such as extracting them as a new method [23] or reordering their statements
for improving readability [35].
Consequently, our answer to RQ3 is Depending on target software. There are intertwined
cloned in all the detection results except the conventional PDG of ant. The rates of intertwined
clones in the detection results varied from system to system, the rate was between 3 and 22%.
Table 7: Number of intertwined clone candidates

conventional
execution
mergednetbeans
0
75
46

ant
6
17
24

jdtcore
163
459
365

swing
66
156
143

15

Technical Report, Graduate School of Information Science and Technology, Osaka University

	
  	
  	
  	
  113	  	
  this.interfacesCount	
  =	
  u2At(readOffset);	
  
	
  ++	
  114	  	
  readOffset	
  +=	
  2;	
  
	
  	
  	
  	
  115	  	
  if	  (this.interfacesCount	
  !=	
  0)	
  {	
  
	
  	
  	
  	
  116	  	  	  	
  this.interfaceNames	
  =	
  new	
  char[this.interfacesCount][];	
  
	
  	
  	
  	
  117	  	  	  	
  for	  (int	
  i	
  =	
  0;	
  i	
  <	
  this.interfacesCount;	
  i++)	
  {	
  
	
  	
  	
  	
  118	
  	
  	
  	
  	
  	
  this.interfaceNames[i]	
  =	
  getConstantClassNameAt(u2At(readOffset));	
  
	
  	
  	
  	
  119	
  	
  	
  	
  	
  	
  readOffset	
  +=	
  2;	
  }	
  }	
  
	
  	
  	
  	
  120	  	
  //	  Read	  the	
  this.fields,	
  use	
  exception	
  handlers	
  to	
  catch	  bad	
  format	
  
	
  ++	
  121	  	
  this.fieldsCount	
  =	
  u2At(readOffset);	
  	
  -­‐-­‐	  122	  	
  readOffset	
  +=	
  2;	
  
	
  ++	
  123	  	
  if	  (this.fieldsCount	
  !=	
  0)	
  {	
  
	
  	
  	
  	
  124	  	  	  	
  FieldInfo	  field;	
  
	
  	
  	
  	
  125	  	  	  	
  this.fields	
  =	
  new	
  FieldInfo[this.fieldsCount];	
  
	
  ++	
  126	  	  	  	
  for	  (int	
  i	
  =	
  0;	
  i	
  <	
  this.fieldsCount;	
  i++)	
  {	
  
	
  	
  	
  	
  127	
  	
  	
  	
  	
  	
  field	
  =	
  new	
  FieldInfo(reference,	
  this.constantPoolOffsets,	
  readOffset);	
  
	
  ++	
  128	
  	
  	
  	
  	
  	
  this.fields[i]	
  =	
  field;	
  
	
  ++	
  129	
  	
  	
  	
  	
  	
  readOffset	
  +=	
  field.sizeInBytes();	
  }	
  }	
  
	
  	
  	
  	
  130	
  	
  	
  //	
  Read	  the	
  this.methods	  	
  -­‐-­‐	  131	  	
  	
  this.methodsCount	
  =	
  u2At(readOffset);	
  
	
  	
  	
  	
  132	  	
  	
  readOffset	
  +=	
  2;	
  
	
  -­‐-­‐	
  133	
  	
  	
  if	
  (this.methodsCount	
  !=	
  0)	
  {	
  
	
  	
  	
  	
  134	
  	
  	
  	
  	
  this.methods	
  =	
  new	
  MethodInfo[this.methodsCount];	
  
	
  	
  	
  	
  135	
  	
  	
  	
  	
  MethodInfo	
  method;	
  	
  -­‐-­‐	  136	
  	
  	
  	
  	
  for	  (int	
  i	
  =	
  0;	
  i	
  <	
  this.methodsCount;	
  i++)	
  {	
  
	
  	
  	
  	
  137	
  	
  	
  	
  	
  	
  	
  method	
  =	
  new	
  MethodInfo(reference,	
  this.constantPoolOffsets,	
  readOffset);	
  	
  -­‐-­‐	
  138	
  	
  	
  	
  	
  	
  	
  this.methods[i]	
  =	
  method;	
  	
  -­‐-­‐	
  139	
  	
  	
  	
  	
  	
  	
  readOffset	
  +=	
  method.sizeInBytes();	
  }	
  }	
  
	
  	
  	
  	
  140	
  	
  	
  //	
  Read	  the	
  attributes	
  Figure 8: Intertwined clones detected from jdtcore

VI. Threats To Validity
I.

Locations of gaps

In the experiment of this paper, we used a set of clones that should be detected. The set that
we used is the Bellon’s references, but locations of gaps were added by authors themselves. If
someone else adds locations of gaps, the result (locations of gaps) might be different from ourresult. Our result is open to the public. Anyone can access to them.

II.

No comparison with other detection techniques

In this experiment, we did not compare the proposed technique with other detection techniques
intentionally. There are three reasons for that. The first reason is that the proposed techniques arefor enhancing the PDG-based detection and the authors would like to concentrate on comparing
proposed PDGs and conventional PDGs.
The second reason is that in Bellon’s references, there are some clones each of which consistsof multiple methods. Token-based or line-based detection techniques can detect such clones ifthey ignore boundaries of methods. On the other hand, the PDG-based detection can never findsuch clones. However we do not think incapability of detecting such clones is a drawback of the
PDG-based detection. If we would like to detect such clones, we can use token-based or linebased techniques. That is, the authors would not like to have compared techniques of different
categories in this paper.
The third reason is that Bellon’s references do not include locations of gaps, which means it
16

Technical Report, Graduate School of Information Science and Technology, Osaka University

is impossible to fairly compare our PDG-based detection with the other techniques in the context
of using locations of gaps.
Instead of comparing the proposed technique with other detection techniques such as linebased or token-based ones, we focuses on intertwined clones in this paper. Intertwined clones areincluded in detection result of the PDG-based technique meanwhile other detection techniques
do not detect them. We also showed that intertwined clones can be potential targets of refactoringsuch as extracting them as a new method or reordering program statements in them.

VII. Related Work
Komondoor et al. first applied program slicing to clone detection [26]. In their method, program
statements and control predicates are nodes of PDGs. Backward slicing is mainly used in theidentification, and forward slicing is performed only from matching predicates. Their method
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 clones.
Krinke proposed a fine-grained PDG, which he applied to clone detection [27]. In the finegrained PDG, nodes are mapped one-to-one onto nodes of an abstract syntax tree, which meansthat the number of nodes in fine-grained PDGs is much greater than the number of nodes in
traditional PDGs. Consequently, it takes longer to detect clones using fine-grained PDGs. In
order to release this problem, he proposed a k-limited search in which similar subgraphs aresearched within k hops.
Jia et al. proposed a hybrid method to detect non-contiguous clones [36]. In this method,
contiguous clones are firstly detected using a suffix-comparison algorithm such as the line-based
or token-based detection technique. Secondly, surrounding statements having control or data
dependencies with the detected clones are merged if the corresponding clones also have thesame surrounding statements. Their case study revealed that their hybrid method was able todetect non-contiguous clones more rapidly than Duplix, which is an implementation of Krinke’s
method [27]. The difference between the proposed method and their hybrid method is that
their method requires core parts (contiguous clones being longer than a certain length) to detect
non-contiguous clones, whereas the proposed method does not.
Gabel et al. proposed a scalable detection method for semantic code clones [37]. Their method
is an enhanced version of an AST-based detection method, Deckard [38]. They defined the semantic
thread, which was used for mapping and detecting similar subgraphs in PDGs, and for detecting
similar subtrees in ASTs.

VIII.

Conclusion

In this paper, we revisited characteristics of the PDG-based clone detection, and proposed a
new technique for improving its detection capabilities. The key idea is introducing new links
between every pair of two nodes whose program elements are consecutive in the source code.
We implemented a PDG-based detection tool, SCORPIO, based on the proposed technique, and it
is open to the public. In this paper, we described the result comparing detection results between
the proposed technique and the conventional PDG-based technique. We used Bellon’s references
for the comparison. Before the comparison, we added locations of gaps into Bellon’s references
because they had not included gap locations. Hence, we was able to evaluate detection accuracyof the PDG-based detection with considering gaps in clones.
We confirmed the followings with the experiment: (1) the proposed technique improved detection capability of the PDG-based technique, (2) using clone references with locations of gaps
17

Technical Report, Graduate School of Information Science and Technology, Osaka University

yields different evaluation results from one without them in most case, and (3) intertwined clones
are included in detection results of the PDG-based technique.
In the future, we are going to detect clones whose program elements are included in multiple
methods. In order to archive such detection, we need to detect clones from system dependency
graphs, which is made by connecting PDGs of methods based on method invocations in thesource code. Similar subgraph are detected from the PDG of entire of the system. However, asystem PDG is much larger than a method PDG, which mean we need techniques for reducing
computational costs. We actually built a system PDG from 10000-line software and applied theconventional PDG-based detection technique to it. But, detecting clones lasted more than several
hours. Detecting clones from system dependency graphs is challenging research topic.
We also conduct more deep investigations on intertwined clones. Although many research
efforts conducted experiments on clone evolution, none of them used the PDG-based detection
technique. Thus, in their experiments, intertwined clones were not investigated. Intertwined
clone is a special kinds of clones ant we might find interesting findings from investigations on it.

Acknowledgements
This study has been supported by Grants-in-Aid for Scientific Research (S) (25220003), Grant-inAid for Exploratory Research (24650011) from Japan Society for the Promotion of Science, andGrand-in-Aid for Young Scientists (A) (24680002) from the Ministry of Education, Culture, Sports,
Science and Technology.

References[1] D. Rattan, R. Bhatia, M. Singh, Software clone detection: A systematic review, Informationand Software Technology 55 (7) (2013) 1165 – 1199.
[2] C. K. Roy, J. R. Cordy, R. Koschke, Comparison and evaluation of code clone detection
techniques and tools: A qualitative approach, Science of Computer Programming 74 (7)(2009) 470–495.
[3] C. Kapser, M. W. Godfrey, "Cloning considered harmful" considered harmful: patterns ofcloning in software, Empirical Software Engineering 13 (6) (2008) 645–692.
[4] M. Kim, V. Sazawal, D. Notkin, G. Murphy, An empirical study of code clone genealogies, in:Proceedings of the 10th European Software Engineering Conference held jointly with 13th
International Symposium on Foundations of Software Engineering, 2005, pp. 187–196.
[5] N. Göde, R. Koschke, Frequency and risks of changes to clones, in: Proceedings of the 33rd
International Conference on Software Engineering, 2011, pp. 311–320.
[6] K. Hotta, Y. Sano, Y. Higo, S. Kusumoto, Is duplicate code more frequently modified thannon-duplicate code in software evolution?: an empirical study on open source software,
in: Proceedings of the Joint ERCIM Workshop on Software Evolution and International
Workshop on Principles of Software Evolution, 2010, pp. 73–82.
[7] J. Krinke, Is cloned code older than non-cloned code?, in: Proceedings of the 5th International Workshop on Software Clones, 2011, pp. 28–33.
18

Technical Report, Graduate School of Information Science and Technology, Osaka University[8] M. Mondal, C. K. Roy, M. S. Rahman, R. K. Saha, J. Krinke, K. A. Schneider, Comparative
stability of cloned and non-cloned code: an empirical study, in: Proceedings of the 27th
Annual ACM Symposium on Applied Computing, 2012, pp. 1227–1234.
[9] Y. Higo, S. Kusumoto, How often do unintended inconsistencies happened? –deriving modification patterns and detecting overlooked code fragments–, in: Proceedings of the 28th
International Conference on Software Maintenance, 2012, pp. 222–231.
[10] Z. Li, S. Lu, S. Myagmar, Y. Zhou, Cp-miner: Finding copy-paste and related bugs in largescale software code, IEEE Transactions on Software Engineering 32 (3) (2006) 176–192.
[11] H. A. Basit, U. Ali, S. Haque, S. Jarzabek, Things structural clones tell that simple clones
don’t, in: Proceedings of the 28th International Conference on Software Maintenance, 2012,
pp. 275–284.
[12] H. A. Nguyen, T. T. Nguyen, N. H. Pham, J. Al-Kofahi, T. N. Nguyen, Clone management
for evolving software, IEEE Transactions on Software Engineering 38 (5) (2012) 1008–1026.
[13] T. Yamamoto, M. Matsushita, T. Kamiya, K. Inoue, Measuring similarity of large softwaresystems based on source code correspondence, in: Proceedings of the 6th International Conference on Product Focused Software Process Improvement, 2005, pp. 530–544.
[14] T. Ishihara, K. Hotta, Y. Higo, H. Igaki, S. Kusumoto, Inter-project functional clone detection
toward building libraries - an empirical study on 13,000 projects, in: Proceedings of the 19th
Working Conference on Reverse Engineering, 2012, pp. 387–391.
[15] N. Göde, R. Koschke, Incremental clone detection, in: Proceedings of the 13th European
Conference on Software Maintenance and Reengineering, 2009, pp. 219–228.
[16] B. Hummel, E. Juergens, L. Heinemann, M. Conradt, Index-based code clone detection: incremental, distributed, scalable, in: Proceedings of the 26th International Conference on
Software Maintenance, 2010, pp. 1–9.
[17] R. Koschke, Large-scale inter-system clone detection using suffix trees and hashing, Journalof Software: Evolution and Process (2013) n/a–n/a.
[18] J. Ossher, H. Sajnani, C. Lopes, File cloning in open source java projects: The good, the bad,and the ugly, in: Proceedings of the 27th International Conference on Software Maintenance,
2011, pp. 283–292.
[19] Y. Sasaki, T. Yamamoto, Y. Hayase, K. Inoue, Finding File Clones in FreeBSD Ports Collection,
in: Proceedings of the 7th Working Conference on Minging Software Repositories, 2010, pp.
102–105.
[20] J. Svajlenko, I. Keivanloo, C. K. Roy, Scaling Classical Clone Detection Tools for Ultra-Large
Datasets: An Exploratory Study, in: Proceedings of the 7th International Workshop on
Software Clones, 2013, pp. 16–22.
[21] S. Bellon, R. Koschke, G. Antoniol, J. Krinke, E. Merlo, Comparison and evaluation of clone
detection tools, IEEE Transactions on Software Engineering 33 (9) (2007) 577–591.
[22] K. Hotta, Y. Higo, S. Kusumoto, Identifying, tailoring, and suggesting form template method
refactoring opportunities with program dependence graph, in: Proceedings of the 16th European Conference on Software Maintenance and Reengineering, 2012, pp. 53–62.
19

Technical Report, Graduate School of Information Science and Technology, Osaka University[23] M. Fowler, Refactoring: improving the design of existing code, Addison-Wesley Longman
Publishing Co., Inc., 1999.
[24] M. Weiser, Program slicing, in: Proceedings of the 5th international conference on Software
engineering, 1981, pp. 439–449.
[25] J. Ferrante, K. J. Ottenstein, J. D. Warren, The program dependence graph and its use in
optimization, ACM Transactions on Programming Languages and Systems 9 (3) (1987) 319–
349.
[26] R. Komondoor, S. Horwitz, Using slicing to identify duplication in source code, in: Proceedings of the 8th International Symposium on Static Analysis, 2001, pp. 40–56.
[27] J. Krinke, Identifying similar code with program dependence graphs, in: Proceedings of the
8th Working Conference on Reverse Engineering, 2001, pp. 301–309.
[28] B. S. Baker, On finding duplication and near-duplication in large software systems, in: Proceedings of the 2nd Working Conference on Reverse Engineering, 1995, pp. 86–95.
[29] I. D. Baxter, A. Yahin, L. Moura, M. a. Sant’Anna, L. Bier, Clone detection using abstract
syntax trees, in: Proceedings of the 14th International Conference on Software Maintenance, 1998, pp. 368–377.
[30] T. Kamiya, S. Kusumoto, K. Inoue, CCFinder: A multilinguistic token-based code clone
detection system f or large scale source code, IEEE Transactions on Software Engineering
28 (7) (2002) 654–670.
[31] J. Mayrand, C. Leblanc, E. Merlo, Experiment on the automatic detection of function clones
in a software system using metrics, in: Proceedings of the 12th International Conference on
Software Maintenance, 1996, pp. 244–253.
[32] S. Ducasse, M. Rieger, S. Demeyer, A language independent approach for detecting duplicated code, in: Proceedings of the 15th International Conference on Software Maintenance,
1999, pp. 109–118.
[33] Y. Higo, T. Kamiya, S. Kusumoto, K. a. Inoue, Method and implementation for investigatingcode clones in a software system, Information and Software Technology 49 (9-10).
[34] H. Murakami, K. Hotta, Y. Higo, H. Igaki, S. Kusumoto, Folding Repeated Instructions
for Improving Token-based Code Clone Detection, in: Proceedings of the 12th Working
Conference on Source Code Analysis and Manipulation, 2012, pp. 64–73.
[35] Y. Sasaki, Y. Higo, S. Kusumoto, Reordering program statements for improving readability,
in: Proceedings of the 17th European Conference on Software Maintenance and Reengineering, 2013, pp. 361–364.
[36] Y. Jia, D. Binkley, M. Marman, J. Krinke, M. Matsushita, Kclone: A proposed approach to fast
precise code clone detection, in: Proceedings of the 3rd International Workshop on Software
Clones, 2009.
[37] M. Gabel, L. Jiang, Z. Su, Scalable detection of semantic clones, in: Proceedings of the 30th
international conference on Software engineering, 2008, pp. 321–330.
[38] L. Jiang, G. Misherghi, Z. Su, S. Glondu, Deckard: Scalable and accurate tree-based detectionof code clones, in: Proceedings of the 29th international conference on Software Engineering,
2007, pp. 96–105.
20

Technical Report, Graduate School of Information Science and Technology, Osaka University

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 9: Sample calculation of good and ok values

A. Definitions
Definition1 The rate of overlapping between two code fragments f 1 and f 2 is defined as thefollowing formula. Assume that lines( f ) is a set of lines included in code fragment f .

overlap( f 1 , f 2 ) =|lines( f 1 ) ∩ lines( f 2 )||lines( f 1 ) ∪ lines( f 2 )|(15)

Definition2 The rate how code fragment f 1 is contained by another code fragment f 2 .

contain( f 1 , f 2 ) =|lines( f 1 ) ∩ lines( f 2 )||lines( f 1 )|(16)

Definition3 good value between two clone pairs (p1 and p2 ) is calculated by the following formula.
good( p1 , p2 )= min(overlap( p1 . f 1 , p2 . f 1 ),overlap( p1 . f 2 , p2 . f 2 ))(17)

Figure 9 shows a situation that two clone pairs (p1 and p2 ) exists in the source code. In thissituation, good value becomes 85
5 6
5good( p1 , p2 ) = min( , ) =8 8
8If the threshold is 0.7, the two clone pairs are regarded as unmatched because of 58 ≤ 0.7.

21

Technical Report, Graduate School of Information Science and Technology, Osaka University

Definition4 ok value between two clone pairs (p1 and p2 ) is calculated by the following formula.
ok (CP1 , CP2 )= min(max (contained(CP1 .CF1 , CP2 .CF1 ),contained(CP2 .CF1 , CP1 .CF1 )),max (contained(CP1 .CF2 , CP2 .CF2 ),contained(CP2 .CF2 , CP1 .CF2 )))(18)

In the case of Figure 9, ok value becomes 56
6 6
5
5 5
ok ( p1 , p2 ) = min(max ( , ), max ( , )) =
6 7
6 8
6
If the threshold is 0.7, the two clone pairs are regarded as matched because of 0.7 ≤ 65 .

B.

Effectiveness of merging PDG nodes

Table 8 shows the number of comparisons of pairwise slicings. By introducing execution-next
link, the number of comparisons increased for all of the systems, however the merging techniquerelease the increase in cost.
Table 8: Number of comparisonsconventional
execution
merged22

netbeans
16,992
96,127
81,194ant
140,595
356,357
340,413

jdtcore14,166,700
39,539,472
35,192,633

swing
7,055,758
12,552,543
11,928,501