Technical Report
A needle in the stack: efficient clone
detection for huge collections of source
code
Simone Livieri
Department of Computer Science
Graduate School of Information Science and Technology
Osaka University
Osaka, Japansimone@ist.osaka-u.ac.jp
Daniel M. German
Department of Computer Science
University of Victoria
Victoria, Canada
dmg@uvic.ca
Katsuro Inoue
Department of Computer Science
Graduate School of Information Science and Technology
Osaka University
Osaka, Japaninoue@ist.osaka-u.ac.jp
January 17, 2010

A needle in the stack: efficient clone detection forhuge collections of source code
Simone Livieri

Department of Computer Science
Graduate School ofInformation Science and Technology
Osaka University
Osaka, Japansimone@ist.osaka-u.ac.jp

Daniel M. German

Department of Computer Science
University of Victoria
Victoria, Canada
dmg@uvic.ca

Abstract—One of the important uses of source code clone
detection analysis is plagiarism detection, where a file is compared against a known corpus of source code to try to findpotential matches. As the availability of Free and Open Source
Software (FOSS) continues to increase it has become important
to know if specific source code has been created from copies
of FOSS software. Version 5.0.2 of Debian GNU/Linux contains
approximately 323 millions SLOCs, distributed in approximately
1.45 million files. Current clone detection tools are incapable ofdealing with a corpus of this size, and might either take literally
months to complete a detection run, or might simply crash due
to lack of resources. In this paper we propose a time and space
efficient token-based method to detect clones of a source code fileagainst a known corpus of source code. With an empirical study,
we demonstrate that our method is capable of finding clones of afile in a corpus of 100,000 files source code files in a few seconds.

I. T HE CHALLENGES OF M ASSIVE C LONE D ETECTION
One of the most frequently mentioned uses of clone detection is determining whether a given file has been cloned(partially or as a whole) from another one (for example, by
copying code from one of the many open source projects intoanother one [3]). Open source keeps growing (both in numberof projects, and each project in the size of its source code).
Version 5.0.2 of Debian GNU/Linux contains approximately
323 millions SLOCs, distributed in approximately 1.45 million files. Debian consists of only 12,300 different software
packages. According to the data provided by FlossMole [4],July 2008, SourceForge hosted 69,492 different projects.
Unfortunately finding clones in a massive collection of files
is often a time consuming task. Livieri et al. described a
distributed method for clone detection that scanned for clones
in the source code of the FreeBSD ports (0.75 million files,
approximately 11 Gigabytes of source code): it required 51
hrs, using 80 different computers [7].
In an experiment we performed, CCFinder [5] detectedcode clones in a collection of about 450 thousands C/C++
source code files in 29 days.
If this clone detection is to be run only once, 29 days canbe perceived as an acceptable performance. But, what if anorganization is interested in running this detection frequently

Katsuro Inoue

Department of Computer Science
Graduate School ofInformation Science and Technology
Osaka University
Osaka, Japaninoue@ist.osaka-u.ac.jp(for example, as a service to find the clones of a given source
file within a given reference corpus of source code)?
As Livieri described, this could be done in a distributedmanner using ad-hoc programs (as they did), or using distributed frameworks, such as Apache’s Hadoop (in a manner
similar to the one described in [10]).
In recent years there has been a significant effort to write
efficient clone detection algorithms. Examples of these approaches are [8], [9]. Their analyses and optimizations assume
that the data can fit in memory, and do not take into accountthat, at some point, a massive collection of source code
will eventually exhaust the computer’s memory. Kim andNotkin [6] reflected on the need of tools to perform efficientorigin analysis, and suggested that clone detection can be
useful, but it was constrained by its comparison of n-to-nfiles, and its speed.
II. M ASSIVE C LONE D ETECTION
A. Definitions
Let Σ be a finite alphabet and σ ∈ Σm . A string w ∈ Σn
is an n-gram of σ if it is a substring of σ of length n; that is,if
w = σi , σi+1 , . . . , σi+n−1
for some i, 0 ≤ i ≤ m − n; let wi be the n-gram of σ startingat position i.
Let c = {c0 , . . . , ch−1 } denote a cover of σ, that is
an ordered set of n-grams whose concatenation or partial
concatenation is σ. A cover is a minimal cover of σ ifremoving one member destroys the covering property.
We define a partial concatenation of two strings, denotedwith  as follows. Given two strings x and y, let x = x0 α andy = βy 0 ; definex  y = x0 αy 0
if α = β, undefined otherwise. For example, abcde is a partial
concatenation of abc and cde.
Let ω(σ) = {w0 , . . . , wm−n } be the ordered set of all theUn-grams of σ; ω U (σ) = {w0U , w1U , . . . , wk−1
} be the set ofthe unique n-grams of σ.

Algorithm 1 D ETECT(σ, c, δ)Require: c cover of s
Require: δ distance vector of cK ← pσ (c0 )i←1while i < |c| and K 6= ∅ doK ← M ERGE(K, pσ (ci ), δi )i←i+1
end while
return K
Algorithm 2 M ERGE(K, p, d)
if K = ∅ or p = ∅ thenreturn ∅end ifK0 ← {}
j←0
for i = 0 to |K| − 1 dot←0while j < |p| and t ≤ d dot ← distance(pj , Ki )if t = d thenappend Ki to K0
j ←j+1else if t < d thenj ←j+1
end ifend while
end forreturn K0
Let pσ (w) = {i|wi = w} be the set of positions within σ
at which the n-gram w appears in it.
For a cover c = {c0 , . . . , ch−1 }, let δ(c) = {δ0 , . . . , δh−1 }be its distance vector. Each element of δ is the distances
between the element with the same index in c and c0 . The
distance between two elements is the difference between theposition of the corresponding n-gram in σ.
B. An Algorithm for Massive Code Clone Detection
Finding duplicated code between some source file and alarge repository of source code is a special case of patternmatching, where the input can be considered as a set ofpatterns that need to be exact-matched in the repository.
We first illustrate our algorithm from an abstract and simplified point of view using, as an example, the simple caseof finding the positions in which a specific string (s) occurs
inside a longer string (σ).
Let σ be the string sethesetheses over the alphabet
Σ = {e, h, s, t}; let the size of the n-grams be 4. Thenω(σ) = {seth, ethe, thes, hese, eset, seth,ethe, thes, hese, eses}Uω (σ) = {seth, ethe, thes, hese, eset, eses}andpσ (seth) = {0, 5}
σp (hese) = {3, 8}

pσ (ethe) = {1, 6}
σp (eset) = {4}pσ (thes) = {2, 7}
pσ (eses) = {9}Finding the position in which the string s = heset occurs
inside σ is straightforward. We proceed as follows (see Algorithm 1):
1) determine a minimal cover of s and its corresponding
distance vector:
c = {hese, eset}δ(c) = {0, 1}

2) initialize the clone set with the positions of the firstelement of c in σ:
K = pσ (c0 ) = pσ (hese) = {3, 8}3) merge K and p = pσ (c1 ) = pσ (eset) = {4} (seeAlgorithm 2). Two elements are merged if their distanceis equal to δ1 = 1. In our example, we proceed to merge
K0 = 3 and p0 = 4 because δ1 = 1 = 4 − 3. The result{3} becomes the new value of K.
This step is repeated until all the elements in c have beenprocessed. The final value of K contains the locations
within σ where s occurs, in this case position 3; if K is
empty, the string does not occur in σ.
C. Complexity analysis of the algorithm
The time complexity of searching for clones of a string s
depends primarily of the following factors:
1) the number of tokens in s — let it be n — and the sizeof its cover; for the sake of simplicity we will assume
that the size of the cover is n;2) the size of the n-grams: |w|; the size of the n-gram is
the minimal size of a clone that the algorithm can detect;3) the number of different n-grams in the corpus F:|ω U (F)|;4) the time required to retrieve pF (w) for a given n-gram
w in the database — we will refer to this as τ (w); and5) the expected length of pF (w) for any string w: |pF (w)|
If there is a complete clone of s in the database, the core of
the algorithm is computed n times, but in practice, the size ofK will be reduced after each iteration. For each n-gram w inc, pF (w) is retrieved, and the distance between each elementof K and pF (w) computed in time proportional to |pF (w)|.
The time to compute K — and find the clones of s — isproportional to n × max (|pF (w)|).
w∈ω U (F )If not enough memory is available, τ (w) will depend
primarily on the following factors:
1) the speed of secondary storage;2) the indexing algorithm; a typical database that uses B+
trees (such as a relational DBMS) can find a record inO(log(|ω U (F)|/k)) time, where |ω U (F)| is the numberof keys in the database (the number of different ngrams), and k is the number of keys that can fit in agiven index page (the longer the n-gram, the fewer the
keys per page); andTABLE I
N UMBER OF UNIQUE n- GRAMS ACCORDING TO THEIR SIZE ON A SAMPLE
OF 10,000 FILES
Size
Unique n-grams

3

4

8

16

32

8,305

31,250698,2455,618,612

9,732,138

3) the length of the record to retrieve from secondary
storage into main memory pF (w).
If we consider the size of the n-gram w as a constant, τ (w)will have a complexity O(log(|ω U (F)| + |pF (w)|), hence thetime-complexity of using a database to find the clones in a fileof n tokens isO(n|pF (w)|log(|ω U (F)| + |pF (w)|))(1)

In practice, unless n is too large, the time to retrieve fromsecondary storage the records of the n n-grams might besignificantly larger than the time required to perform the restof the operations. In order to bound the worst case scenario(that n is too large) we only perform clone detections at thefunction/method level: we break the input string into functions,and perform the detection on each substring. Thus, the timerequired to perform this clone detection, using secondary
storage, is proportional to n × (log(|ω U (F)|) + |pF (w)|), thatis, the length of the input string to search multiplied by theaverage time it takes to find and retrieve — if it exists — ann-gram record from the database.
TABLE IID ISTRIBUTION OF THE FREQUENCY OF N - GRAMS FOR DIFFERENT SIZESOF N - GRAMSTABLE IIIT IME IT TOOK TO CREATE THE DATABASE OF EACH CORPUS , AND ITSRESULTING SIZE

# files

1k

10k

100k

Creation Time
Total Size

5 min
60 MBytes

1 hr 8 min
648 MBytes

11 hr 9 min
3.7 GBytes

1) N -grams extraction. The pre-processed files are readand divided into blocks corresponding to functions’bodies. Using a sliding window, groups of 16 tokens (the n-grams) are extracted from each block andsaved in a file together with their positions. Tokens
are stored as 8-bits values; tokens of the same typehave the same value. Positions are stored as triplets
hf ileIndex, blockIndex, tokenIndexi.
2) Database population. The file containing the n-gramsand their position is sorted by n-gram in order togroup n-gram’s positions. Each pair (n-gram, n-gram’s
positions) is stored in a database table; each value isfirst serialized in a byte array. An index is created on
the table using the n-gram as key.
3) Clone detection. Given an input file, the tool extracts
its n-grams and then proceeds to detect all the occurrences of each token sub-sequence with a user-specified
minimum length (see Section II-B).
An advantage of our method is that the corpus’s size canbe easily incremented or decreased: only the data relative tothe files added (or removed) need to be inserted (or deleted)in the database.
Another advantage is the parallel nature of our method.
Most of the tasks performed by our tools are independent fromeach other and could be simultaneously executed.

Size

1st Qu.

MedianMean

3rd Qu.

Max

%≤5

4

1

4.0

165.8

16.0

254,500

50%

8

1

2.0

20.7

6.0

44,46069%

IV. P RELIMINARY R ESULTS

16

1

1.0

2.6

2.0

6,897

92%

32

1

1

1.4

1.0

2,713

99%

We have performed a preliminary evaluation of Yocca. The
intention of this evaluation is to determine how efficient interms of speed and space Yocca is. First, we created 4 different
corpus of 100, 1,000, 10,000 and 100,000 files each (C/C++).
These files were randomly selected from the source code of
Debian 5.0.2. These experiments were performed on a dual
2GHz quad-core CPU workstation equipped with 4 gigabytes
of memory and running Ubuntu Linux 9.10. The databaseresided on a dedicated SATA hard drive.
The time required to create the database is reported intable IV. As it can be seen, the time required to create thedatabase grows linearly with the size of the database, and it
is slightly below linear.
We then searched for clones in 100 different files withineach corpus (we run Yocca, CCFinder, and Simian [1] 100
times against each corpus; in each run we search for clones
within a different file2 ). Table IV shows the resulting running

To understand how much ω U (F) varies with the size ofthe n-grams, we computed the n-grams of a sample of sourcecode files and determined that 16 was a good balance between
the number of different n-grams |ω U (F)| and the average sizeof each n-gram record pF .
III. I MPLEMENTATION : YOCCA
YOCCA and its companion tools implement our approachfor detecting code clones between a file and a large collection of source code. They have been written in the Java
programming language and they provide all the functionalities
needed with the exception of the parsing of source files
into syntactical token sequences. Parsing is achieved throughthe use of CCFinder in pre-processing mode1 . The current
implementation uses PostgreSQL 8.4 as its database back-end.
The core functionalities provided by our tools are:1 Running CCFinder specifying the option “-p”.

2 CCFinder is capable of searching clones across two different sets offiles. If one set is the corpus, and the other the file to process, its functionality
is equivalent to Yocca; Simian, however, does not, and in every run allclones in the union of the corpus and the input file were reported.

TABLE IVRUNNING TIMES ( IN SECONDS ) OF Y O C C A ON DIFFERENT CORPORA
Corpus Size

1st Qu.

MedianMean

3rd Qu.

Max

100

0.270

0.375

0.519

0.495

2.880

1,000

0.260

0.370

0.557

0.530

3.490

10,000

0.260

0.540

0.822

0.865

5.560

100,000

0.308

3.700

9.420

9.535

100.510TABLE VRUNNING TIMES ( IN SECONDS ) OF DIFFERENT CODE CLONE DETECTIONTOOLS ON THE 10 K FILES CORPUS . E ACH WAS RUN 100 TIMES .
Tool

1st Qu.

MedianMean

3rd Qu.

Max

Yocca

0.260

0.540

0.822

0.865

5.560

CCFinder

144.2

144.7

146.0

145.1

272.6

Simian

62.87

63.41

63.57

64.02

67.63

times for Yocca for each of the corpora. As it can be seen, themedian run time of Yocca for the corpus of 100,000 files isless than 4 seconds. For the smaller corpora, the times are very
similar. We speculate this is due to costs not directly related
to the detection (such as opening the database connection,
preparing data structures, and the effect of data caching inside
Yocca).
Table V shows the running times of each tool (run 100
times) against the 10k files corpus. The median and maximum processing times of Yocca were 0.5 and 5.56 seconds,
respectively, while CCFinder took median 145 seconds andmaximum of 273 seconds; as expected, all Simian runs show
approximately the same time (median 63 seconds). Yocca
performed significantly faster.
V. C ONCLUSIONSIn this paper, we have described some of the challenges
that the current clone detection tools face when performing
massive code clone detection on a corpus of several hundredsof thousands of files. These problems range from running outof memory, to taking weeks of run time to complete.
To address this problem we have presented a method forcode clone detection based on n-grams that is time efficientwhen the corpus data must be stored in disk (i.e. the minimum
amount of information to performed the clone detection is readfrom disk).
Yocca is a code clone detection tool for massive collectionsof source code based on the proposed method and implemented using a relational database where the n-grams of the
corpus are stored.
A preliminary study demonstrated that Yocca is capable ofrunning notably faster than other code clone detection tools(the median detection time of clones of a file in a corpus of
10,000 files was 0.5 seconds, compared to 146 seconds it took
CCFinder to do an equivalent detection).
We have shown how persistent memoization — whereintermediate results, whose computation is the most resource

intensive, are persisted on disk and retrieved when needed —greatly helps reducing the running time of expensive analyses.
Intellectual property clearance is one emerging applicationof code clone detection that can greatly benefit from ourapproach. With the growth of the complexity of software, there
are cases in which a software system cannot be completelydeveloped by a single entity and parts of it need to be obtained
from offshore software companies. The increasing availabilityof Free and Open Source Software (FOSS) made it important
to know if specific source code has been created from copies
of FOSS software [2]. The existence of code clones betweena software system and Open Source Software can be used todetermine a possible violation or incompatibility of license’s
terms.
VI. F UTURE W ORK
In our future work we intent to extend or evaluation of
Yocca. In particular, we want to determine the performance ofYocca with collections of more than one million files. We also
want to formally evaluate its accuracy: that it detects at least
as many clones as other token-based clone detection tools, andit does not detect more false positives than them.
ACKNOWLEDGMENT
This work is being conducted as a part of the Stage Project, theDevelopment of Next Generation IT Infrastructure, supported by
Ministry of Education, Culture, Sports, Science and Technology.
Also, this research was supported by Japan Society for the
Promotion of Science, Grant-in-Aid for Scientific Research (A)(No.21240002).

R EFERENCES[1] Simian - Similarity Analyser. http://www.redhillconsulting.com.au/
products/simian/, 2010. Accessed January 13, 2010.
[2] M. J. Foley.
Microsoft admits its GPL violation;
will reissue Windows 7 tool under open-source license.
http://blogs.zdnet.com/microsoft/?p=4547, November 2010. Accessed
January 17, 2010.
[3] D. M. German, M. Di Penta, Y.-G. Guéhéneuc, and G. Antoniol. Codesiblings: Technical and legal implications. In Proc. of the 2009 Working
Conference on Mining Software Repositories, MSR, pages 81–90, 2009.
[4] J. Howison, M. Conklin, and K. Crowston. FLOSSmole: A collaborative
repository for FLOSS research data and analyses. International Journalof Information Technology and Web Engineering, 1(3):17–26, 2006.
[5] T. Kamiya, S. Kusumoto, and K. Inoue. CCFinder: A multilinguistic
token-based code clone detection system for large scale source code.
IEEE Transactions on Software Engineering, 28(7):654–670, July 2002.
[6] M. Kim and D. Notkin. Program element matching for multi-version
program analyses. In Proceedings of the 2006 International Workshop
on Mining Software Repositories, MSR, pages 58–64, 2006.
[7] S. Livieri, Y. Higo, M. Matsushita, and K. Inoue. Very-large scalecode clone analysis and visualization of open source programs using
distributed ccfinder: D-ccfinder. In ”Proceedings of the International
Conference on Software Engineering”, pages 106–115, 2007.
[8] E. Merlo and T. Lavoie. Computing structural types of clone syntactic
blocks. In ”Proceedings of the Working Conference on Reverse Engineering”, pages 274–278, 2009.
[9] N. H. Pham, H. A. Nguyen, T. T. Nguyen, J. M. Al-Kofahi, andT. N. Nguyen. Complete and accurate clone detection in graph-basedmodels. In ”Proceedings of the International Conference on Software
Engineering”, pages 276–286, 2009.
[10] W. Shang, Z. M. Jiang, B. Adams, and A. E. Hassan. MapReduce as a
general framework to support research in Mining Software Repositories(MSR). In Proceedings of the International Working Conference on
Mining Software Repositories, MSR, pages 21–30, 2009.