Inter-Project Functional Clone Detection toward Building Libraries- An Empirical Study on 13,000 Projects Tomoya Ishihara, Keisuke Hotta, Yoshiki Higo, Hiroshi Igaki, Shinji Kusumoto
Graduate School of Information Science and Technology, Osaka University, Japan
1-5, Yamadaoka, Suita, Osaka, 565-0871, Japan{t-ishihr, k-hotta, higo, igaki, kusumoto}@ist.osaka-u.ac.jp

Abstract—Libraries created from commonly used functionalities offer a variety of benefits to developers. To locate
such widely used functionalities, clone detection on a large
corpus of source code could be useful. However, existingclone detection techniques did not address the creation oflibraries. Therefore, existing clone detectors are sometimes
unbefitting to detect candidates to be included in libraries.
This paper proposes a method-based clone detection techniquefocusing on building libraries. This method-level granularity isappropriate for building libraries because a method composes afunctionally coherent unit, and so it can be easily pulled up into
libraries. Also, such a granularity realizes a scalable detection
on huge data sets. Our experimental results on a huge dataset (360 million lines of code, 13,000 projects) showed that the
proposed technique could detect functional clones which might
be beneficial on the creation of libraries within a short timeframe.
Keywords-Clone detection, Huge data set, Library building

I. I NTRODUTION
Software libraries are useful for development. They could
not only reduce development costs but also increase reliability of software. This is because developers need not implement new functionalities if the functionalities are alreadyincluded in libraries.
In order for developers to gain benefits from libraries, thelibraries should be equipped sufficiently with functionalities
needed by many of them. This indicates requirements forcreating or refining libraries. It is necessary to detect functionalities that are commonly used across multiple software
projects to meet the requirements. To detect library candidates, which means functionalities to be included in libraries,
code clone detection could be beneficial. However, detecting
clones on a large corpus of source code is a problematic task
due to its scalability.
Several research efforts have tackled large-scale clone
detection on huge data sets or across multiple software
projects [1], [2], [3], [4], [5], [6], [7], [8]. These techniques
can be categorized into the following two categories.
File-based Detection: Some research detects clones bycomparing source files [3], [4]. These techniques regard
identical (or similar) files as clones. Such a coarse grain
realizes fast detection on large code bases. However, theymight miss clones that can be detected with fine-grained(such as token- or line-based) detection.
Scalable Fine-Grained Detection: Some research realizes scalable detection on large data sets with some artifices[1], [2], [5], [6], [7], [8]. They can detect many clones
that file-based techniques cannot detect, however, thesetechniques are inferior to file-based techniques in speed,
These techniques open ways to analyze clones acrossmultiple software projects. However, they are not always sufficient for the purpose of building libraries. One of the issues
is that their granularity is not adequate for library creation.
For file-based techniques, they can only detect source files asclones if they are identical or similar in file-level. This meansthat if only a part of source files is a library candidate, filebased techniques miss it. Fine-grained techniques will not
miss such candidates. However, clones detected with finegrained techniques may not be easily extracted as libraries
because they can report a part of functionalities as clones.
In addition, fine-grained techniques detect too many clones
from a massive amount of source code. Identifying librarycandidates from such a large amount of clones may require
many efforts.
This paper proposes a method-based clone detection technique to encourage the creation of software libraries. The
method-level detection resolves the above issues: we canlocate library candidates even if their owner files are notwholly duplicated, and we can easily extract clones because
a method composes a functionally coherent unit. Also, thisapproach can realize a scalable detection on a huge corpus
of source code.
In this paper, we conducted a pilot study to reveal thefollowing two research questions for confirming the effectiveness of the proposed technique.
RQ1: Can the proposed technique complete its detection
in a practical time frame on a huge data set?
RQ2: Can the proposed technique detect method-levelclones that are useful for building libraries?
Hereafter, we use some terms. A file/method clone
means a relationship of duplications among two or morefiles/methods, and a file/method clone set is a set offiles/methods that have file/method clone relationships toeach other in the set. In addition, it uses more two terms,

cloned file and cloned method, which are similar to theabove terms. However, they are different from each other. A
cloned file/method means a file/method that has at least one
file/method clone relationship with other files/methods.
II. R ELATED W ORK
A. File Clone Detection
Sasaki et al. developed a file clone detection tool,
FCFinder, and applied it to software systems included in
FreeBSD Ports Collection [4]. FCFinder generates a hashvalue from every source file after removing white spaces,tabs, and comments. As a result, they found that 68% of all
the source files were instances of cloned files. Also, theyreported that the size of a source file has no impact onwhether it becomes an instance of cloned files or not.
Ossher et al. proposed a file clone detection technique [3].
Their method is a combination of three types of detection
methods, exact, FQN, and fingerprint [3].
Exact: Compare hash values calculated with strings created from every source file treated as a single string.
FQN: Compare fully qualified names (FQN) of the publicclasses in every source file.
Fingerprint: Compare method names and field names insource files.
Their empirical study on about 13,000 software systems
showed that over 10% source files are identified as cloned
files. Also, they reported that using the same libraries andreusing the previous systems for developing new one are
typical situations that file clones occur.
The file-based approach realizes high scalability of detection on very large corpora of code. However, file-level
granularity is not suited to the creation of libraries. This isbecause file-based techniques cannot detect functional clones
if their owner files are not wholly duplicated. Therefore, filebased detection miss many of library candidates.
B. Scalable Fine-Grained Clone Detection
Hummel et al. proposed a clone detection technique using
indexes to achieve incremental and scalable detection [6].
Their technique calculates an index for each statement chunkand compares the indexes. They succeeded to detect clones
in 36 minutes from 73 million lines of code with 100
machines.
Cordy and Roy implemented a tool named DebCheck
that detects clones between input source files and a Debiansource distribution [7]. It requires 10 hours for a preparationof detection on 3 million of C functions. However, thepreparation is required at only once, and it can detect clones
between input source files and prepared functions within a
few minutes after the preparation.
Koschke proposed a scalable clone detection techniquefocused on detecting lisence violations with suffix trees[8]. His basic idea to reduce time required for detection
is to generate a suffix tree for either the subject system or

the source code corpus that is a set of other systems. He
confirmed that the approach is faster than existing indexbased techniques.
These techniques can detect fine-grained clones in apractical time frame on large data sets. This means thatthey can catch duplications that are missed with file-based
techniques. However, these techniques are also not suited forbuilding libraries. Unfortunately, the advantage that they can
detect fine-grained clones adversely affects library creation
due to the following reasons.
• The amount of detected clones with fine-grained techniques becomes huge. Thus, it requires many efforts to
identify library candidates from all the detected clones.
• Clones detected with fine-grained techniques contain
only a part of functionalities very often. Therefore,
it sometimes requires many efforts to extract such apartially functional clone as libraries.
III. M ETHOD -C LONE D ETECTION
Herein, we describe how efficiently the proposed technique identifies method clones from huge data sets. The
process consists of five steps. In the remainder of thissection, we explain every step in detail. The process contains
some specializations for Java; however, it is not difficult toapply it to other programming languages by changing thespecializations.
STEP1 Extract methods: We build ASTs (Abstract Syntax Trees) for every source file, then extract their subtrees
corresponding to methods. Why we build ASTs is to perform
STEP2.
STEP2 Normalize methods: This step removes whitespaces, tabs, blank lines, modifiers, annotations, and comments from every method. In addition, variables and each
literal is replaced with a special token. The purpose of thisstep is to absorb trivial differences between methods.
STEP3 Filter out methods: There are many simple methods that are obviously not suited to the purpose of librarycreation. Getter and setter methods are typical instances ofthem. Many of such simple methods are detected as methodclones; however, we do not need such method clones.
Consequently, in this step, the proposed technique excludes simple methods from the target of clone detection.
More concretely, it removes methods that have no blockstatement. Herein, block statements mean do, for, if, synchronized, switch, try, and white in the case of Java.
STEP4 Generate hash values: ASTs of target methods
are transformed to textual representations, and then a hashvalue is generated from every textual representation. The
hash values are stored into a database for ease of access inthe final step.
STEP5 Make hash groups: Methods are grouped basedon their hash values. A method group consisting of a single
method means that the method is not duplicated with anyother methods. In other words, it is not an instance of cloned

methods. Meanwhile, a method group consists of two or
more methods means that they are duplicated to one another.
This step extracts only the latter method groups.

The calculation of this metric is processed as an additional
computation in STEP5.

IV. A P ILOT S TUDY

We found that 2,937,047 methods become instances ofcloned methods, and the number of method clone sets is814,391. 490,206 out of the 814,391 method clone sets,
which is about 60% of all the method clone sets, are acrossmultiple software projects.
Table II shows the number of detected cloned methods.
This table tells us that the number of cloned methods
included in cloned files is 1,772,488, and the number ofcloned methods not in cloned files is 1,164,559. The former
is also detected by file-based detection meanwhile the lattercan be detected only by the method-based detection. In
other words, the method-based technique retrieved 1,164,559
functional clones that the file-based technique missed.
Table III shows the number of source files that have fileclone relationships or method clone ones to at least one othersource file. The file-based approach reported 791,589 files ascloned files. On the other hand, the method-based approachreported additional 288,200 source files as including at least
one method-level duplication. Such source files were 14%of all the source files.

A. Experimental target
In this research, we selected “UCI source code data sets”(in short, UCI dataset) [3], [9] as the experimental target.
It is a huge set of open source software projects written in
Java, and it was used in the study conducted by Ossher et
al. [3]. Table I shows an overview of the target data set. As
shown in Table I, the target dataset has over 13,000 projects
and 360 million lines of code.
B. Experimental setup
We used a single workstation to conduct this experiment.
It has 4 logical CPUs, 8 GBytes memory, and a SSD(solid state drive). The proposed method was developed as asoftware tool with Java. All the steps except STEP5, which
are described in Section III, were performed in a parallelway. The tool uses a SQL database to store the informationof source files, methods, and detected duplications. The
target data set and the database was located in SSD.
In order to compare the proposed technique with the filebased approach, we implemented a file-based detection tool
based on the literature [4] by ourselves.
C. Metric for Identifying Library Candidates
It is not realistic to investigate all the method clones
detected from a huge data set because of the massive amountof clones. To promote the efficiency to identify suitablelibrary candidates, we use a metric defined as follows.
NOP(m): the Number Of Projects that have one or morecloned methods forming method clone set m.
NOP represents how many projects each method clone
set is distributed in. The use of this metric relies on thefollowing Assumption.
Assumption: The more projects a method clone set is
distributed in, the more it is suitable for a library candidate.
The authors believe that this assumption is valid according
to the following bases.
• If a method clone set is shared by many projects, it
should have high reliability because it is used and tested
by many developers.
• If a method clone set is shared by many projects, alibrary created from it will be used by many developers.
Table IOVERVIEW OF TARGET DATA SET# of .java files# of software projects# of methods
total LOC of .java filessize

2,072,490
13,193
5,953,165
361,663,992
30.6 GBytes

D. An Overview of Detected Method Clones

E. Answer to RQ1
RQ1: Can the proposed technique complete its detection
in a practical time frame on a huge data set?
The answer is Yes.
Table IV shows the detection time of method clones in thispilot study. As shown in the table, the total time required tocomplete the detection is only 3.50 hours. That is to say,the proposed technique could detect method clones from360 million lines of code within 4 hours. Of course, some
artifices such as putting a SQL database on a SSD could
impinge on the detection speed. Although those artifices
could affect positively, we think, the 4 hours are enoughpractical to detect method clones on such a huge data set.
The file-based detection of Sasaki et al. required about 17
hours to finish a file clone detection [4]. The size of data
used in their research is 11.2 GBytes. Both the target and theTable IIN UMBER OF CLONED METHODS

in cloned files
not in cloned files

across projects
1,407,338
658,500

within a system
365,150
506,059

total
1,772,488
1,164,559

Table IIIN UMBER OF SOURCE FILES BEING CLONED FILES OR INCLUDINGMETHOD CLONES

cloned filehaving cloned methods

across projects
592,964
147,532

within a system
198,625
140,668

total
791,589
288,200

	
 :	
 
	
 39	
 public	
 class	 TableSorter	
 extends	
 	
 
	
 	
 	
 	
 	
 	
 	
 	
 	
 	
 	
 	
 	
 	
 	
 	
 	
 	
 	
 	
 	
 	
 	
 AbstractTableModel	
 {	
 
	
 :	
 
213	
 	
 	
 private	
 int[]	
 getModelToView()	
 {	
 
214	
 	
 	
 	
 	
 if	
 (modelToView	
 ==	
 null)	
 {	
 
215	
 	
 	
 	
 	
 	
 	
 int	
 n	
 =	
 getViewToModel().length;	
 
216	
 	
 	
 	
 	
 	
 	
 modelToView	
 =	
 new	
 int[n];	
 
217	
 	
 	
 	
 	
 	
 	
 for	
 (int	
 i	
 =	
 0	
 ;	
 i	
 <	
 n	
 ;	
 i++)	
 {	
 
218	
 	
 	
 	
 	
 	
 	
 	
 	
 	
 modelToView[modelIndex(i)]	
 =	
 i;	
 
219	
 	
 	
 	
 	
 	
 	
 }	
 
220	
 	
 	
 	
 	
 }	
 
221	
 	
 	
 	
 	
 return	 modelToView;	
 
222	
 	
 	
 }	
 
	
 :	
 

	
 :	
 
	
 72	
 public	
 class	 TableSorter	
 extends	
 
	
 	
 	
 	
 	
 	
 	
 	
 	
 	
 	
 	
 	
 	
 	
 	
 	
 	
 	
 AbstractTableModel	
 {	
 
	
 :	
 
272	
 	
 	
 private	
 int[]	
 getModelToView()	
 {	
 
273	
 	
 	
 	
 	
 if	
 (modelToView	
 ==	
 null)	
 {	
 
274	
 	
 	
 	
 	
 	
 	
 int	
 n	
 =	
 getViewToModel().length;	
 
275	
 	
 	
 	
 	
 	
 	
 modelToView	
 =	
 new	
 int[n];	
 
276	
 	
 	
 	
 	
 	
 	
 for	
 (int	
 i	
 =	
 0	
 ;	
 i	
 <	
 n	
 ;	
 i++)	 {	 duplicated 277	
 	
 	
 	
 	
 	
 	
 	
 	
 	
 modelToView[modelIndex(i)]	
 =	
 i;	
 
methods	
 278	
 	
 	
 	
 	
 	
 	
 }	
 
279	
 	
 	
 	
 	
 }	
 
280	
 	
 	
 	
 	
 return	 modelToView;	
 
281	
 	
 	
 }	
 
	
 :	
 

(a) Jug-avis system	

Figure 1.

(b) JPodder system	

An Instance of Method Clone Sets that is Extracted as a Real Library

experimental environments are different between our pilot
study and Sasaki et al.’s experiment, and so it is impossible
to compare the speed of detection directly. However, ourpilot study revealed that the method clone detection is not
so slower than a file clone detection. In Ossher et al.’s paper,
there is no description about the detection time, so that
we cannot compare detection speed between the proposed
method and their method.
F. Answer to RQ2
RQ2: Can the proposed technique detect method-levelclones that are useful for building libraries?
The answer is Yes.
In order to answer this RQ, we browsed the source codeof method clone sets whose NOP(m) values were in the top
100, and judged whether they should be extracted as libraries
or not. The reason why we browsed a part of method clone
sets is that it is impossible to investigate all the 814,391
method clone sets. The top 100 values of NOP(m) fell within
the range of 70 and 277.
As a result of our manual inspection, we judged 56
method clone sets out of 100 as suitable for library candidates. Figure 1 shows an instance of such method clone sets.
The value of NOP(m) for this clone set is 114. These cloned
methods sort rows of JTable instances. The functionalities tosort rows of tables was added to the standard library of Java
when version 1.6 was released. Before the version, usersof JTable needed to implement the sort functionalities bythemselves if they needed it. This is a real example thatfunctionalities implemented in many software projects were
pulled up to libraries.
All of the 44 method clone sets judged as not suitablewere stereotype functions. Herein, a stereotype function
indicates a simple and versatile function such as size() orclose(). Although the proposed technique attempts to filterout such simple methods in STEP3, unfortunately, some of
Table IV
D ETECTION TIME
Processing
Time

Step1

Step2 Step3
2.79h

Step4

Step5
0.71h

Total
3.50h

:
42
43
44
45
46
47
:

Figure 2.

public int size() {if (_ids == null) {return 0;}
return _ids.size();}

An Example of Stereotype Functions

stereotype functions passed the filtering. Figure 2 shows anexample of stereotype functions. The undesirable behaviorof the filtering is mainly caused by presences of error
checkings. The proposed technique filters out methods thathave no block statement, and so stereotype functions having
error checkings tend to pass the filtering because most ofthem include if blocks.
V. T HREATS TO VALIDITY
Assumption: In the pilot study, we hypothesized that amethod clone set is suitable as a library candidate if it isshared by many software projects. Although we believe that
this assumption is valid, there may be other criteria to identify suitable library candidates. For instance a combinationof NOP(m) and complexity metrics, may work well. The
basis of this is that a complex functionality requires manyefforts and much attention for its implementation, and soa library created from it will drastically reduce developers’
efforts and increase reliability. In addition, the information
on how often a method occurs in a single project may bean evidence that the method should be in a library.
Manual Inspection: In order to evaluate the effectivenessof the method-based approach for building libraries, we inspected 100 method clone sets manually and made subjective
judgements whether they are suitable for the creation oflibraries or not. However, criteria of such judgements aredifferent from person to person. Thus, we will get anotherresult if we ask other people to made such judgements.
Hash collision: The proposed technique uses the MD5hashing algorithm to compare methods in source code efficiently. However, if a hash collision occurs, non-duplicatedmethods are accidentally regarded as cloned. In order tocheck how often hash collisions occur, we performed an
automated textual comparison for all the method pairs that

have the same hash values. As a result, we found that hashcollisions did not occur at all.
Code normalization: The proposed technique replaces
each of variables and literals with a special token, whichmeans that the normalization ignores the types of them. If weuse more intelligent normalizations, for example, replacing
variables and literals with their type names, the amountof detected duplications should be decreased. On the other
hand, if we do not normalize source code, trivial differencesof methods prevent them from being detected. Selecting
an appropriate set of code normalization is a considerably
difficult problem.
Method filtering: The proposed technique eliminates
methods that have no block statement not for detecting
simple methods as clones. However, this elimination may
delete methods that should be detected as clones.
Multiple versions: The UCI dataset includes multiple
versions of some software projects. If we use it as it is,
many clones will be detected between different versionsof the same software. However, obviously, such clones
are not desirable for promoting the creation of libraries.
Thus, we removed all the versions except the latest one
before conducting the pilot study. The data cleansing mightoverlook some of redundant versions. However, we foundno clones between different versions of a software systemthrough our manual inspections.
Data set: In this experiment, we targeted only a single
data set. If we perform the same experiment on different data
sets, the rate of duplications will be different. However, theexperimental result, we believe, should be general for Javasource code because of the massive amount of source codein the experimental target.
VI. C ONCLUSION
This paper proposed a method-based clone detection technique to encourage the creation of libraries. We conducteda pilot study on a huge data set written in Java, which
includes about 360 million lines of code among about 13,000
software projects.
Our pilot study proved that the proposed technique could
complete its clone detection in 4 hours from the huge data
set. Also, we manually inspected 100 detected clones andjudged whether they are suitable as library candidates or not.
As a result, we confirmed that the proposed technique could
detect suitable library candidates including real instancesthat are pulled up to libraries. In addition, we found thatabout 40% of method clones were not detected by a filebased approach. This fact shows that the method-based
approach could retrieve many functional clones that the filebased approach missed.
As future work, we are going to conduct more experiments to confirm the effectiveness of the proposed techniquewith human subjects. In addition, the proposed technique
should have a wide range of applications such as detecting

license violations. We plan to look for other usages of it
and customizations for each usage. It may open ways forother usages to detect method clones having some gaps, andso we plan to extend the proposed technique with the LSH
algorithm [10], [11].
ACKNOWLEDGMENT
This work was supported by MEXT/JSPS KAKENHI
21240002, 23650014, 24650011, 24680002, and 24700030.
R EFERENCES[1] Y. Higo, K. Tanaka, and S. Kusumoto, “Toward Identifying
Inter-project Clone Sets for Building Useful Libraries,” inProc. of the 4th International Workshop on Software Clones,
May 2010, pp. 87–88.
[2] S. Livieri, Y. Higo, M. Matsushita, and K. Inoue, “VeryLarge Scale Code Clone Analysis and Visualization of Open
Source Program Using Distributed CCFinder: D-CCFinder,”in Proc. of the 29th International Conference on Software
Engineering, May 2007, pp. 106–115.
[3] J. Ossher, H. Sajnani, and C. V. Lopes, “File Cloning in Open
Source Java Projects: The Good, the Bad, and the Ugly,”in Proc. of the 27th International Conference on Software
Maintenance, Sep. 2011, pp. 283–292.
[4] Y. Sasaki, T. Yamamoto, Y. Hayase, and K. Inoue, “Finding
File Clones in FreeBSD Ports Collection,” in Proc. of the 7th
Working Conference on Mining Software Repositories, May
2010, pp. 102–105.
[5] W. Shang, B. Adams, and A. E. Hassan, “An Experience Report on Scaling Tools for Mining Software Repositories Using
MapReduce,” in Proc. of the 25th International Conference
on Automated Software Engineering, Sep. 2010, pp. 275–284.
[6] B. Hummel, E. Juergens, L. Heinemann, and M. Conradt, “Index-Based Code Clone Detection: Incremental, Distributed, Scalable,” in Proc. of the 26th IEEE International
Conference on Software Maintenance, Sep. 2010, pp. 1–9.
[7] J. R. Cordy and C. K. Roy, “DebCheck: Efficient Checking
for Open Source Code Clones in Software Systems,” in Proc.
of the 19th International Conference on Program Comprehension, June 2011, pp. 217–218.
[8] R. Koschke, “Large-Scale Inter-System Clone Detection Using Suffix Trees,” in Proc. of the 16th European Conference
on Software Maintenance and Reengineering, Mar. 2012, pp.
309–318.
[9] C. Lopes, S. Bajracharya, J.Ossher, and P.Baldi, “UCI Source
Code Data Sets,” http://www.ics.uci.edu/∼lopes/datasets/.
[10] M. Datar, N. Immorlica, P. Indyk, and V. S. Mirrokni,“Locality-Sensitive Hashing Scheme Based on p-Stable Distributions,” in Proc. of the 20th Symposium on Computational
Geometry, June 2004, pp. 253–262.
[11] S. Uddin, C. K. Roy, K. Schneider, and A. Hindle, “On the Effectiveness of Simhashing in Clone Detection on Large Scale
Software System,” in Proc. of the 18th Working Conference
on Reverse Engineering, Oct. 2011, pp. 13–22.