181

Development of a Code Clone Search Tool forOpen Source Repositories
Pei Xia

Yuki Manabe

Norihiro Yoshida

Katsuro Inoue

Finding code clones in the open source systems is important for eﬃcient and safe reuse of existing open
source software. In this paper, we propose a novel search model, open code clone search, to explore code
clones in open source repositories on the Internet. Based on this search model, we have designed and implemented a prototype system named OpenCCFinder . This system takes a query code fragment as its input,
and returns the code fragments containing the code clones with the query. It utilizes publicly available code
search engines as external resources. Using OpenCCFinder , we have conducted several case studies for Java
code. These case studies show the applicability of our system.

1 Introduction
Nowadays reusing existing source code to build
up new software systems becomes common. Developers can easily get source code of various projects
that hosted in open source repositories on the Internet such as Google code, sourceforge, github andso on. Some previous studies show that even industrial software products are also increasingly reusing
open source code due to their reliability and costbeneﬁts [4].
However, when reusing source codes, some problems about software compliance may happen.
1. When we ﬁnd a useful source code ﬁle, can
we reuse it safely?
2. Are our own open source projects illegally
reused by other people?
For the ﬁrst question, before reusing the source

オープンソースレポジトリに対するコードクローン検索
ツールの開発.
夏 沛, 眞 鍋 雄 貴 , 井 上 克 郎 , 大 阪 大 学 大 学 院 情 報 科 学研究科コンピュータサイエンス専攻, Department ofComputer Science, Graduate School of Information
Science and Technology, Osaka University.
吉田則裕, 奈良先端科学技術大学院大学情報科学研究
科, Graduate School of Information Science, Nara
Institute of Science and Technology.
コンピュータソフトウェア, Vol.29, No.3 (2012),pp.181–187.

[研究論文 (レター)] 2011 年 12 月 12 日受付.

code, developers should make sure that they will
not violate the license. A license violation may
take them to court and cost them a lot. However, to tell the license of a source ﬁle is not easy
because there are many code clones among open
source projects [13]. That means they also copy
and modify source code from other projects. In extremely cases they even change or remove the original license statement in the source ﬁles [1]. Reusing
such source ﬁles is risky. For the second question,even though some other projects had reused sourcecode while violating its license, the original codeowner would hardly know it, since it is hard tocheck other projects by hand.
In order to answer such questions, one solution
is to ﬁnd out all the cloned code in the world, andcompare the related information about them to tell
the reuse relationship between those codes. In thesedays, many code clone detection tools as well as
code search tools have been developed [5][7]. However, none of them can search for code clones fromopen source repositories.
Basing on the code clone detection and code
search technologies, we proposed a novel approachfor open source code clone search, and also implemented a prototype tool named OpenCCFinder[12]. OpenCCFinder takes a code fragment as its
query input, and returns a list of ﬁles from open
source repositories that contain cloned code with
the queried one, along with extra information. This

182

コンピュータソフトウェア

Fig. 1

Architecture of OpenCCFinder .

tool can support us to study the raised problems.
In this paper, we ﬁrst describe the overview of
OpenCCFinder including architecture and search
process in Section 2. Section 3 shows our case studies. Section 4 discusses our approach and Section 5shows the related works. In Section 6, we conclude
our discussions with some future works.

2 Overview of OpenCCFinder
2. 1 Architecture
Figure 1 shows the architecture of OpenCCFinder .
It takes an input query Q and returns an output
results set R. Input query Q is composed of codefragment qc and code attribute qa . qc may be acomplete source ﬁle or a part of a source code ﬁle,which is in question. qa is a set of associated information characterizing qc , such as the ﬁle name. qa
is optional and could be added to improve the quality of the output results. Given an input Query Q,
OpenCCFinder extracts useful information from it
and generates queries for external code search engine (e.g. Google code search, SPARS/R etc.), andthen analyze the returned candidate ﬁles from external search engines, at last form a ﬁnal result as
output R. The detail of this search process will be
introduced in section 2.2.
Output result R is composed of results r1,r2 ...
rn. Each result ri is composed of a code ﬁle ric

and its code attribute ria . ric is a code ﬁle whichis returned by external code search engines, and ria
a set of associated information about ric , including
URL, ﬁle path, LOC, license, copyright, last modiﬁed time, clone cover ratio and clone detail.
For the external code search engines, we use
Google code search and SPARS/R in our tool implementation. Google code search is a famous code
search engine. It provides search service API to
the user, so we can easily integrate it to our tool;
SPARS/R is a Java component search engine withthe keyword input and component rank mechanism
developed by our research group [9]. The Java classrepository of SPARS/R is kept updated by us.
2. 2 Search process
Search process of OpenCCFinder can be devided
into 6 steps, as shown in Figure 2.
(a) Word Extraction. At the beginning, codefragment qc in input query Q is tokenized, andthe words from source code and comments are
separated. User can choose whether to extract
words from source code or from comments, orfrom both.
(b) Keyword Ranking. Next, the keywords
used for query generation are selected fromthe extracted words.
In this step, ﬁrst
OpenCCFinder ﬁlters out the words that con-Vol. 29 No. 3 Aug. 2012

Fig. 2

183

Search process of OpenCCFinder .

sidered being featureless. For example, thereserved words of each source code language,
the words in very short length, and the words
included in customized ﬁlter are ﬁltered out.
After the ﬁltering, a simple words importanceranking strategy is applied on the remaining
words. Currently, there are two strategy implemented in the tool for ranking the words:
frequency strategy and random strategy. Frequency strategy is to rank the keywords by thetimes they appear in the source codes or comment, while random strategy is just to rank thewords randomly.
(c) Searching for Candidates Files. As thesearch engines, here we choose SPARS/R and
Google Code Search. We use diﬀerent combination of high ranked keywords to generate
search queries for each search engine to get appropriate candidate ﬁles. For each query, thereturned results set should not be very large,
so as not to include too many irrelevant results.
If the returned results set are too large, we will
add one more keyword from the ranked keywords list to the query to narrow the results
set. At last, we merge the returned results ofseveral queries as the analysis candidate ﬁles.
(d) Downloading Candidate Files. All the
candidate ﬁles in step (c) are downloaded fromInternet. While downloading the ﬁle, the toolis also crawling the web to extract useful infor-

mation for the code attributes such as ﬁle path,
URL, LOC, License, Copyrights, and last modiﬁed time if available.
(e) Code Clone Analysis. The code clones
between the input query code fragment qc andeach source code ﬁle obtained at Step (d) arecomputed. We have used a code clone detection tool CCFinder [17], with its parameter setting for the minimum token length 15.
(f) Result Forming. All the candidate ﬁlesand their code attributes are combined andpacked as the output result R of this system,
sorted by their similarity to qc . Here we use
coverratio to evaluate their similarity, which
deﬁned as the percentage of reused qc ’s code.

3 Case Study
We have conducted two case studies to explore
applicability of OpenCCFinder approach†1 .
3. 1 Case study 1: base64.java
Case study 1 is designed for the ﬁrst raised question: When we ﬁnd some useful source code, can
we reuse it safely?
Consider such a situation that we have found a†1 All these case studies have been performed under
PC Workstation with dual Xeon X5550 2.66GHz
processors and 24 GB memory between Aug.2011
and Sep.2011.

184

コンピュータソフトウェア

Fig. 4The histogram of #input files in termsof #similar files found by OpenCCFinder .
Fig. 3

Files that contain code clones withier.

base64.java found by OpenCCFinder .

ﬁle named base64.java [3] in Apache ObjectRelationBridge (Apache OJB) open source project [2]and we would like to reuse it. The comments section in the source ﬁle represents that this ﬁle isunder the Apache license. But we wondered if thisﬁle is copied from somewhere else that may be under another license. Then we take this base64.java
ﬁle as input and search for similar ﬁles from open
source repositories using OpenCCFinder .
OpenCCFinder returns 57 other ﬁles from open
source repositories that contain code clone with thebase64.java. For the limited space here, we cannot
present all the detailed data of the 57 ﬁles. Instead
we organized the data and draw a scatterplot view,
as shown in Figure 3. In the ﬁgure, the ﬁles are
distributed by their cover ratio and last modiﬁedtime. Licenses are shown in diﬀerent icons. Fromit, we can observe the following:
1. 55 source ﬁles from other projects containcode clones of base64.java. The last modiﬁed
time is varied from 2004 to current. The earliest ﬁle we can ﬁnd is under Apache license.
2. In these ﬁles, the cover ratios are not thesame, which may indicate these ﬁles reused andmodiﬁed from each other in diﬀerent ways.
3. Most of the licenses are found as public domain, while several ﬁles have been found underMIT, LGPL, GPL, BSD, Apache or AGPL licenses.
After checking the detailed information of eachﬁle by hand, we conﬁrmed that it is safe to keep thisﬁle as Apache license. Another choice is to reuse
the public domain code, which is also safe. Though
OpenCCFinder cannot tell the answer of the ﬁrst
question directly, it helps us to do the analysis eas-

3. 2 Case study 2: SSHTools
Case study 2 is designed for the second question:
Are our own open source projects illegally reusedby other people? In this case study, we investigate
a Java project SSHTools [14], to ﬁnd some ﬁles that
may illegally reused by other projects.
SSHTools is a Java SSH application providing
Java SSH API and terminal, which is under the
GPL license. We choose this project because it
is widely used by other projects and it is a small
project that is easy to analyze.
Ignoring some tiny sized ﬁles, we have selected
339 ﬁles from SSHTools project (version 0.2.9, lastmodiﬁed time is 6-23-2007), and each of themis used as the input of OpenCCFinder .
We
counted the number of similar ﬁles found in open
source repositories for each SSHTools’ ﬁle, and alsocounted the number of diﬀerent licenses of thesesimilar ﬁles. In this case study, we set up a threshold of the cover ratio to ﬁlter out non-similar ﬁles.
Only those ﬁles which cover more than 40% code of
the queried ﬁle would be identiﬁed as similar ﬁle.
The result is shown as Figure 4. The ﬁgure shows
the number of similar ﬁles found in each of the 339
SSHTools’ ﬁles.
From this ﬁgure, we can observe that 305 of the339 ﬁles contain code clones with other ﬁles fromopen source repositories. 275 of them have less than
10 similar ﬁles found for each; several ﬁles have 1030 similar ﬁles found for each; one ﬁle has morethan 30 similar ﬁles. Besides, we also investigatedthe diﬀerent licenses appeared in each similar ﬁle.
SSHTools is under GPL license. However, 285 ﬁlesin SSHTools have similar ﬁles found with 1 diﬀerent license, 10 ﬁles in SSHTools have similar ﬁleswith 2 diﬀerent licenses, and 1 ﬁle in SSHTools haveVol. 29 No. 3 Aug. 2012
Table 1

185

The case that similar files are under 3 other license (partial results)

File path/j2ssh-fork/src/com/sshtools/
common/util/BrowserLauncher.java/de.fzj.unicore.rcp.terminal.ssh.
gsissh/.../sshtools/common/
util/BrowserLauncher.java/openﬁre/launcher/BrowserLauncher.java/dg/hipster/BrowserLauncher.java...

Project namej2ssh-fork

Cover ratio
0.91

LicenseGPL

Last modiﬁed time
2008/6/17

unicore

0.89

LGPL

2010/2/3

openﬁre-tomcat
hipster
...

0.88
0.84
...

ApacheBSD...

2010/4/19
2006/10/12...

similar ﬁles with 3 diﬀerent licenses.
We checked the detailed ﬁles whose cloned ﬁleshave 2 or 3 diﬀerent licenses. There are several unusual source code reuse cases. Here we only state
one case of them as an example.
Table 1 shows the similar ﬁles with 3 other different licenses, along with extra information about
ﬁle path, project name, cover ratio and last modiﬁed time. For the space limitation, we only present
a small part of the results here.
From this table, we can see 4 ﬁles named
BrowserLauncher.java with very high cover ratio.
Beside the GPL license, there are LGPL, Apacheand BSD licenses. It is reasonable for us to supposethat they share the same origine. However, sometimes it is not allowed to release the reused sourcecode under a diﬀerent license. Some reuse activities
in this case are suspicious.
This case study shows that OpenCCFinder is
helpful for answering the second raised question.
We can ﬁnd candidates of the suspicious ﬁles easily
and eﬀectively by using this tool.

4 Discussion
4. 1 Usefulness
As shown in the case studies, OpenCCFinder
is helpful to analyze how source code is reuse.
In case study 1, from the open source repositories we search out many similar ﬁles of Apache
OJB’s ﬁle base64.java. With extra information
about each ﬁle, we can know how the searched
code is used in diﬀerent projects. Then developer’s reuse activity that we focus on becomes easy
and eﬃcient. In case study 2, we have found out
ﬁles from open source repositories containing code
clones with SSHTools ﬁles, among which there areseveral suspicious cases.
However, although this tool provides some clues

to get evidence, the ﬁnal judgment on the legality
issue should be made by human after all.
And due to the keyword based search model,
OpenCCFinder can only ﬁnd out Type 1 clones [5].
4. 2 Performance
It takes about 1-2 minutes for OpenCCFinder tocomplete one search task, including keyword extracting, downloading, collecting information andrunning CCFinder. Most of the time is spend at
downloading step. Network traﬃc and the sizeof ﬁle to be downloaded also aﬀect the executing
time. Case study 1 took about 2 minutes, whilecase study 2 took about 7-8 hours in total.
4. 3 Recall and precision
OpenCCFinder searches for code clones in open
source repositories using external code search engines. So the recall and precision of this tool depends on those search engines. It is diﬃcult toevaluate recall of OpenCCFinder quantitatively because we could never know all the ﬁles in open
source repositories, and OpenCCFinder cannot
download all the ﬁles stored in open source repositories due to the limitation of space and time cost.
The precision of OpenCCFinder has been calculated. In this discussion, it is deﬁned as the ratio ofﬁles containing code clones to all the downloaded
ﬁles. In case study 1, 62 ﬁles have been downloaded, of which 55 ﬁles contain code clone with
the queried ﬁle. The precision can be simply calculated as 0.887; in the case study 2, overall we havedownloaded 17054 ﬁles from the Internet, and 2480
of those ﬁles have been detected as containing code
clone with the ﬁles in SSHTools. So the average
precision is 0.145. The precision in case study 2 islow, but non-cloned ﬁles are ﬁlered out by the later
process.

186コンピュータソフトウェア

5 Related work
There are many research studies on analyzing
and tracing code origin, provenance, evolution, genealogy through code clone analysis [10][11][15][16].
Duala-Ekoko et. al propose Clone Tracker to trace
and manage code clone history [6]. They have developed a tool for supporting clone tracking, with
abstract clone information named clone region descriptor. Davies et al. propose Software Bertillonage for determining the origin of code entities withanchored signature matching method [8]. Thesestudies are closely related to our work. However,their objectives are diﬀerent from ours in the sensethat they analyze various characteristics of codefragment in their local repositories. In our case, we
analyze the query code in the Internet repositories.

6 Conclusion
In this paper, we have proposed a novel concept
for open code clone search, and then presented its
search model and detailed processes for the prototype system OpenCCFinder . We have conducted
two case studies, which show the applicability of
our approach.
Acknowledgements This work was supported
by KAKENHI (No.21240002, No.23650015). Early
version of OpenCCFinder is developed by our earlier student Yusuke Sasaki.
References[ 1 ] Arne, P.H.: Jacobsen v. Katzer - Open Source
License Validation: How Far Does It Go?, The
Computer & Internet Lawyer, Vol. 25 No. 11 (2008),
pp. 27–31.
[ 2 ] Apache ObJectRelationalBridge OJB, http://
db.apache.org/ojb/[ 3 ] Base64: Public Domain Base64 Encoder/Decoder,
http://iharder.sourceforge.net/current/java/base64/[ 4 ] Ebert, C. (ed.): Open Source Software in Industry, IEEE Software, Vol. 25, No. 3(2008), pp. 52–53.
[ 5 ] Roy, C. K., Cordy, J. R. and Koschke, R: Comparison and Evaluation of Code Clone Detection
Techniques and Tools: A Qualitative Approach,
Science of Computer Programming, Vol. 74, No. 7(2009), pp. 470–495.
[ 6 ] Duala-Ekoko, E. and Robillard, M. P.: Clone
Region Descriptors: Representing and Tracking Duplication in Source Code, ACM Tran. on Software
Engineering, Vol. 20, No. 1 (2010), pp. 3.1–3.31.

[ 7 ] Cordy, J., Inoue, K., Koschke, R. and Jarzabek,
S. (eds.): 4th International Workshop on Software
Clones (IWSC 2010), Cape Town, South Africa,
2010.
[ 8 ] Davies, J., German, D. M. and Godfrey, M. W.:
Software Bertillonage: Finding the Provenance ofan Entity, in Proc. of Working Conference on Mining Software Repositories (MSR 2011), Honolulu,
Hawaii, 2011, pp. 183–192.
[ 9 ] Inoue, K., Yokomori, R., Yamamoto, T., Matsushita, M. and Kusumoto, S.: Ranking Signiﬁcance of Software Components Based on Use Relations, IEEE Trans. Softw. Eng., Vol. 31, No. 3(2005), pp. 213–225.
[10] Godfrey, M. and Zou, L.: Using Origin Analysis to Detect Merging and Splitting of Source
Code Entities, IEEE Trans. Softw. Eng., Vol. 31,
No. 2(2005), pp. 166–181.
[11] Kim, M., Sazawal, V., Notkin, D. and Murphy,
G.: An empirical study of code clone genealogies,
in Proc. of the 2005 European Software Engineering Conference and 2005 Foundations of Software
Engineering (ESEC/FSE 2005), Lisbon, Portugal,
2005, pp. 187–196.
[12] Xia, P., Manabe, Y., Yoshida, N. and Inoue, K.:
Development of a Code Clone Search Tool for Open
Source Repositories, IPSJ SIG Technical Reports,
Vol.2011-SE-174, No.2 (2011), pp. 1–8.
[13] Livieri, S., Higo, Y., Matsushita, M. and Inoue, K.: Very-Large Scale Code Clone Analysis andVisualization of Open Source Programs Using Distributed CCFinder: D-CCFinder, in Proc. of 29th
International Conference on Software Engineering(ICSE 2007), Minneapolis, MN, 2007, pp. 106–115.
[14] SSHTools Project,
http://sourceforge.net/
projects/sshtools/.
[15] Kawaguchi, S., Garg, P. K., Matsushita, M. andInoue, K.: MUDABlue: An Automatic Categorization System for Open Source Repositories, Journal of Systems and Software, Vol. 79, No. 7 (2006),
pp. 939–953.
[16] Thummalapenta, S., Cerulo, L., Aversano, L.
and Di Penta, M.: An empirical study on the maintenance of source code clones, Empirical Software
Engineering, Vol. 15, No. 1 (2009), pp. 1–34.
[17] Kamiya, T., Kusumoto, S. and Inoue, K.:
CCFinder: A Multilinguistic Token-Based CodeClone Detection System for Large Scale Source
Code, IEEE Trans. Softw. Eng., Vol. 28, No. 7(2002),
pp. 654–670.

Vol. 29 No. 3 Aug. 2012夏沛2010 年上海交通大学ソフトウェア工学部卒業．現在，大阪大学大学院情報科学研究科博士前期課程 2 年．コー
ドクローン分析やビジュアライゼー
ションに関する研究に従事．
眞鍋雄貴

2006 年大阪大学基礎工学部情報科学科退学．2011 年同大学大学院情報科
学研究科博士課程修了．同年同大学
院情報科学研究科特任助教．博士 (情報科学)．ソフトウェア工学，特にソフトウェア再利用，ソフトウェアライセンスの研究に従事．情報処理学会，ACM 各会員．

187

大学情報科学研究科助教．博士 (情報科学)．コード
クローン分析手法やリファクタリング支援手法に関する研究に従事．ソフトウェア科学会，情報処理学会，
電子情報通信学会，人工知能学会，IEEE，ACM 各
会員．
井上克郎

1984 年大阪大学大学院基礎工学研究科博士後期課程修了 (工学博士)．同年，大阪大学基礎工学部情報工学科
助手．1984〜1986 年，ハワイ大学マノア校コンピュータサイエンス学科助教授．1991 年大阪大学基礎工学部助教授．1995 年同学部教授．2002
年大阪大学大学院情報科学研究科教授．2011 年 8 月
より同研究科研究科長．ソフトウェア工学，特にコー
ドクローンやコード検索などのプログラム分析や再吉田則裕

2004 年九州工業大学情報工学部知能情報工学科卒業．2009 年大阪大学大学院情報科学研究科博士後期課程修了．2010 年奈良先端科学技術大学院

利用技術の研究に従事．