Finding File Clones in FreeBSD Ports Collection
Yusuke Sasaki∗ Tetsuo Yamamoto† Yasuhiro Hayase∗ Katsuro Inoue∗∗ Graduate School of Information Science and Technology, Osaka University

1-5 Yamadaoka, Suita, Osaka, 565-0871, Japan
Email: {ysk-ssk,y-hayase,inoue}@ist.osaka-u.ac.jp† College of Information Science and Engineering, Ritsumeikan University
1-1-1 Nojihigashi, Kusatsu, Shiga, 525-8577, Japan
Email: tetsuo@cs.ritsumei.ac.jp

Abstract—In Open Source System (OSS) development, software components are often imported and reused; for thisreason we might expect that files are copied in multiple projects(file clones). In this paper, we propose a file clone detection tool
called FCFinder and show the analysis performed with it on
the FreeBSD Ports Collection, a large OSS project collection.
We found many file clones among similar or related projects,
which are systematically introduced from base projects.
Keywords-File clone; hashing; power law; open source system.

I. I NTRODUCTION
These days, researches on code clones are very active, andvarious code clone analysis applications have been exploredincluding bug finding, refactoring, code evolution trace, andplagiarism detection[1].
In the past, our laboratory performed an experiment onlarge-scale code clone analysis using the distributed code
clone detection system D-CCFinder[2]. One of the targetsof the experiment was the FreeBSD Ports Collection, whichis the set of all the applications of FreeBSD and contains
about 10 GB source code.
In this experiment, we found many cases in which files ofa project are simply copied into another project without any(or just slight) modifications in comments or headers. We
call these copied files file clones. The characteristics of thefile clones found in a large collection of source code havenot been explored yet.
File clones can be detected using tools such as
CCFinder[3]. However, even with a fast and distributed
environment, code clone detection is still a very resource
intensive process requiring precise string matching.
In this paper, we propose an efficient file clone detection
method using comparison of the tokenized files’ hash values,
and show its implementation as a tool named FCFinder(File Clone Finder). Using FCFinder, we have analyzed
the FreeBSD’s Ports Collection and found several interestingdetails on the nature of the file clones in that collection. Ourfindings are summarized in such a way that the distributionsof the file size and file clone set size almost follow the socalled “power law”, with several anomalous points which
are made by systematical file duplication among projects.

The contributions of this paper are as follows.
1) A hash-based efficient file clone detection method isproposed and implemented as a tool (FCFinder).
2) A large collection of Open Source Systems (OSS)
is analyzed and visualized from a view point of fileclone.
In Section II, we will show the related works. In Section
III, the approach of FCFinder will be described. Section
IV will discuss the application result of FCFinder to theFreeBSD Ports Collection. Section V will conclude ourdiscussion with future works.
II. BACKGROUND
There are various code clone detection methods proposed
as research trials or as practical implemented tools[3], [4] but
their scalability is mostly limited by the amount of available
memory. Livieri et al. have overcome this limitation bypartitioning the source code into small pieces and detecting
the code clones between each pair of pieces[2], [5].
Mayrand et al. proposed a method for code clone detection at function level using 21 metrics[6]. Successively,
they extended their approach to object oriented programs toefficiently find similar classes[7].
To the best of our knowledge, there is no research aiming
to find file clones in an efficient and scalable way; also, thedistribution of file clones in a large source code collectionis unknown.
III. FCF I N D E R : F ILE C LONE D ETECTION T OOL
FCFinder receives in input a collection of source files
and reports the file clones in it. Figure 1 shows the overall
FCFinder’s process.
1) Indexing: for each .h and .c file in the input collection, FCFinder extract and store several information(e.g., file sizes and project names).
2) Tokenization: each file is parsed into a token sequence;comments, redundant white spaces, line breaks, andcarriage returns are removed. During this step, files
shorter than 15 tokens are removed from the inputlist.

1) Indexing2) Tokenization

3) MD5 Hash

4) Hash Table

Calculation
sourceraw filefilesdataProject separation.c, .h file extraction

Creationhash datatoken data

5) Exact Matching
Checkhashfileclonetable

Comment removal,etc.

Figure 1.

setOverview of FCFinder

Table IM INING TARGET C HARACTERISTICS
Number of files (.c, .h)1,355,098

Number of projects
Total size

7,209
11.2 GBytes

3) MD5 Hash Calculation: an MD5 hash value[8] iscomputed for each tokenized file.
4) Hash Table Creation: a hash table is created with thecomputed hash values as keys and the corresponding
file paths as values; files with the same MD5 value
are grouped together.
5) Exact Matching Check: for each key in the table,
the token sequences of the corresponding files arecompared using a simple exact matching; matchingfiles are reported as a file clone set; the files in a fileclone set have exactly same token sequences.
IV. E XPERIMENTIn this section, we describe the experiment performed
applying FCFinder to the FreeBSD Ports Collection (hereinafter referred as target), a source code collection usedin one of our previous experiments[2]. These files weredownloaded on Sep. 6th in 2007.The target’s characteristics
are shown in Table I. The target is divided into 45 categories(database, multimedia, etc. ) and each category consistsof multiple projects (PHP5, emacs, etc.); there are 7,209
projects in the target. As described in III, we used only .cand .h files in our experiment.
The experiment was performed on a 64 bits FreeBSD
workstation equipped with 2.5GHz CPU and 16 gigabytes
of main memory. During the experiment, the maximum
memory usage was four gigabytes.
A. Preliminary Analysis of the Target
We have analyzed the target in order to expose various
characteristics. Figure 2 shows the size distribution of thefiles in the target; the x-axis displays the file size in 10
kilobytes intervals; the y-axis displays the number of files
whose size falls into each interval; both axes use a logarithmic scale.
Figure 2 shows that the number of files decreases with theincreasing of the file size. The relationship is almost linear
and it is a case of so-called power law[9], [10] characteristicof file size distribution. We did a linear regression analysissleifforebmun001A

150,000

500,000 5,000,000

file size (Bytes)

Figure 2.

File size distribution of the target

for figure 2, and its coefficient of determination adjusted forthe degrees of freedom R∗2 becomes about 0.9024.
Area A presents some interesting findings. The area is ananomaly and does not fit the general power law profile ofthe file size distribution. We performed a detailed analysis of
this area finding 59 file clones of some PHP5’s files related
to the time zone management; these files have a size of about
1.6 megabytes, and their clones increased the frequency ofthe corresponding size interval.
Figure 3 shows the distribution of the number of .c and.h files in each project; the x-axis represents the numberof files inside a project; the y-axis shows the number ofprojects; both axes use a logarithmic scale.
Area B highlights 59 projects that have 1,316 files and61 projects that have 1,070 files which are outliers withrespect to the power law distribution. We found that theseprojects have many file clones of files in the PHP4 and PHP5projects.
Similarly, area C highlights 14 projects, each one having 6,506 files of cross compilers for RTEMS (Real-Time
Executive for Multiprocessor Systems). A part of the files
in these projects are customized depending on their target
architectures.
B. File Clone Analysis of the Target
We have extracted the file clone information for the target
using FCFinder.
The number of elements in a file clone set is called“population” of the file clone set.
Figure 4 shows the distribution of the population for eachfile clone set in the target; the x-axis displays the population

tscejropforebmu
n

002

B02C

5
15 1050 100

500

5,000

tsesenolceilfforebmun

Distribution of the number of files in project

D00
1

E
F

1

5

1050

100

population of file clone set

Figure 4.

005

G

0
5H

5
1

5 1050 100

500 1,000 5,000

number of file clones in projects (clones inside project are excluded)

number of files inside project

Figure 3.

senlocilef
htiw
stcejropforebmunDistribution of population of file clone setof file clone set; the y-axis displays the number of the fileclone sets; both axes use a logarithmic scale.
In the target we found 915,409 file clones, with a total
size of 7,6 Gigabytes; about 68% of the files in the target
are file clones. The reason why the target files have large
numbers of file clones is that large numbers of projects inthe target use many common files among them.
The general tendency is that small population sets are
more frequent than the large population sets. And thecoefficient of determination R∗2 for figure 4 with a linear regression analysis becomes about 0.8508.There are, however,several exceptions.
Area D highlights the file clone sets containing the files
corresponding to area A in Figure 2.
Area E marks the file clone sets of 419 different files
belonging to the PHP4 project or PHP5 project; each of thesefiles has 120 copies. Area F corresponds to PHP project’s
files duplicated 240 times.
Figure 5 presents the distribution of the file clones in eachproject. The x-axis displays the number of file clones ina project; intra-project file clones are ignored. The y-axis
displays the number of projects with such amount of fileclones. The average number of file clones per project is 126.

Figure 5.

Distribution of file clones in projectThis graph shows that the number of projects with a specified
amount of file clones decreases as the number of file clones
increases. The coefficient of determination R∗2 for figure 4
with a linear regression analysis becomes about 0.8263.
Area G marks PHP related projects corresponding to area
B in Figure 3 and area D in Figure 4.
Figure 6 shows some of the relations between the projects
corresponding to area H. Each node represents a project andeach edge represents the number of file clones between twoprojects.
Figure 6 (a) shows the case of GNU Compiler Collection
projects: gcc41, gcc41-withgcjawt (java), gcc42, and gfortran. Three of those share 7,764 file clones.
Figure 6 (b) shows the case of OpenOffice.org where three
related projects share between 7,440 and 8,101 files.
Figure 6 (c) shows that Thunderbird, Firefox, Firefoxdevel, Seamonkey (an integrated network tool), and XULRunner (application development kit) share about 6,000 files;
these are different projects sharing the same code base.
C. Evaluation of FCFinder output
We have randomly chosen 50 file clone sets from theanalysis result of the target, and performed a manual investigation. We have found that those file clones correspondto files that are syntactically identical after they have been
tokenized.
We have also randomly chosen 83 file clone pairs fromthe CCFinder result for the same target. We verified that allof those file pairs have been detected by FCFinder. Bothprecision and recall of FCFinder are 100% with respect
to the results of CCFinder; however, we need to extend thenumber of samples to strengthen this evaluation.
D. Analysis Time
Table II shows the running time for the different stagesof our experiment. In our previous experiment using 80 PC
cluster machines for the same target analysis, it took about
51 hours to complete[2]. Assuming a linear relationshipbetween the number of computers used and the running time,characteristics of the file sizes and file clones distributions.
Our findings have been summarized in such a way that thedistributions of the file size, file clone set population, andproject’s file clones are shown to follow the power law;anomalies in the distribution have been proven to be causedby systematic duplication of file among projects.
File clone analysis is very important in order to know therelationships between different software projects. Throughfile clones, we can investigate the evolution of projects andmigration of legacy files.
As a future work, we plan to improve the file tokenization
process to allow for small differences in the source code’s
syntax, such as differences in identifiers and constants naming.

(a)

(b)

ACKNOWLEDGMENT(c)

We are grateful to Dr. Simone Livieri and Dr. Makoto Ichii
for their useful comments.This work has been partially supported
by Japan Society for the Promotion of Science, Grant-in-Aid for
Scientific Research (A) (No.21240002), and also by MEXT Stage
Project, the Development of Next Generation IT Infrastructure.

R EFERENCES••

Nodes show the projects.
Edges between projects show the number of file clones between two projects.

Figure 6.

Project relations with file clones
Table IIA NALYSIS T IMEStepTimeIndexingTokenization

9.42h

MD5 Hash Calculation
Hash Table Creation

1.13hExact Matching Check

6.61 hTotal

17.16 hthe same analysis performed with a single computer will
require about 40 days. In the experiment with FCFinder,
it took only 17.16 hours with a single workstation, as
shown in Table II. This is due to the difference of analysis
objectives such that D-CCFinder computes all the code
clones including code fragments, while FCFinder finds
only file clones. This reduced the computation complexity,
and allowed a light-weight implementation using existinghashing and database tools. Further improvement of theFCFinder’s performance will require intensive usage ofthe cache of the database with careful tuning.
V. C ONCLUSION
We have implemented an efficient file clone detector
called FCFinder, and applied it to the FreeBSD Ports Collection. The experiment allowed us to find several interesting[1] 3rd International Workshop on Software Clones,
Kaiserslautern, Germany, 2009. [Online]. Available:
http://www.informatik.uni-bremen.de/st/IWSC/[2] S. Livieri, Y. Higo, M. Matushita, and K. Inoue, “Very-large
scale code clone analysis and visualization of open source
programs using distributed CCFinder: D-CCFinder,” in 29th
IEEE International Conference on Software Engineering,
Minneapolis, MN, 2007, pp. 106–115.
[3] T. Kamiya, S. Kusumoto, and K. Inoue, “CCFinder: A
multilinguistic token-based code clone detection system forlarge scale source code,” IEEE Transactions on SoftwareEngineering, vol. 28, no. 7, pp. 654–670, 2002.
[4] S. Bellon, R. Koschke, G. Antoniol, J. Krinke, and E. Merlo,“Comparison and evaluation of clone detection tools,” IEEE
Transactions on Software Engineering, vol. 33, no. 9, pp.
577–591, 2007.
[5] S. Livieri, Y. Higo, M. Matsushita, and K. Inoue, “Analysisof the linux kernel evolution using code clone coverage,” in4th International Workshop on Mining Software Repositories,
Minneapolis, MN, 2007, pp. 22.1–4.
[6] J. Mayrand, C. Leblanc, and E. M. Merlo, “Experiment on theautomatic detection of function clones in a software systemusing metrics,” in 12th IEEE International Conference onSoftware Maintenance, Monterey, CA, 1996, pp. 244–253.
[7] E. Merlo, G. Antoniol, M. D. Penta, and V. F. Rollo, “Linearcomplexity object-oriented similarity for clone detection andsoftware evolution analyses,” in 20th IEEE International
Conference on Software Maintenance, Illinois, CA, 2004, pp.
412–416.
[8] R. Rivest, “The MD5 Message-Digest Algorithm,” RFC
1321 (Informational), Internet Engineering Task Force, Apr.
1992. [Online]. Available: http://www.ietf.org/rfc/rfc1321.txt[9] M. Mitzenmacher, “A brief history of generative models forpower law and lognormal distributions,” Internet Mathematics, vol. 1, no. 2, pp. 226–251, 2003.
[10] G. Concas, M. Marchesi, S. Pinna, and N. Serra, “Power-lawsin a large object-oriented software system,” IEEE Transactions on Software Engineering, vol. 33, pp. 687–708, 2007.