Source File Set Search forClone-and-Own Reuse Analysis
Takashi Ishio∗† , Yusuke Sakaguchi∗ , Kaoru Ito∗ , Katsuro Inoue∗∗ Graduate School of Information Science and Technology, Osaka University, Osaka, Japan† Graduate School of Information Science, Nara Institute of Science and Technology, Nara, Japan

Email: {ishio, s-yusuke, ito-k, inoue}@ist.osaka-u.ac.jp
Abstract—Clone-and-own approach is a natural way of sourcecode reuse for software developers. To assess how known bugs
and security vulnerabilities of a cloned component affect anapplication, developers and security analysts need to identify
an original version of the component and understand how thecloned component is different from the original one. Althoughdevelopers may record the original version information in a
version control system and/or directory names, such information
is often either unavailable or incomplete. In this research, we
propose a code search method that takes as input a set ofsource ﬁles and extracts all the components including similarﬁles from a software ecosystem (i.e., a collection of existingversions of software packages). Our method employs an efﬁcientﬁle similarity computation using b-bit minwise hashing technique.
We use an aggregated ﬁle similarity for ranking components. To
evaluate the effectiveness of this tool, we analyzed 75 cloned
components in Firefox and Android source code. The tool took
about two hours to report the original components from 10
million ﬁles in Debian GNU/Linux packages. Recall of the topﬁve components in the extracted lists is 0.907, while recall of abaseline using SHA-1 ﬁle hash is 0.773, according to the groundtruth recorded in the source code repositories.
Keywords-Software reuse, origin analysis, source code search,ﬁle clone detection

I. I NTRODUCTION
Software developers often reuse source code of existingproducts to develop a new software product [1]. Mohagheghi
et al. reported that reused components are more reliable than
non-reused code [2]. While open source software projects
reuse code from other OSS projects, industrial developers
also use open source systems due to their reliability and costbeneﬁts [3].
Clone-and-own approach is one of the popular approaches
to source code reuse [4], [5]. Dubinsky et al. [1] reported
that cloning is perceived as a natural reuse approach by
the majority of practitioners in the industry. Although many
reusable components are available online in binary forms forvarious operating systems, developers copy source code ofan existing component into their project’s so that they canbuild and test their product using a particular version of acomponent or modify it for their own purpose. For example,
Mozilla Firefox 45.0 includes a modiﬁed version of zlib 1.2.8
in its modules/zlib directory; a developer added a header
ﬁle mozzconf.h in order to rename functions deﬁned in
the library. Koschke et al. [6] reported that copies of speciﬁc
libraries are involved in a relatively large number of projects.

Cloned components may introduce potential defects into an
application. Sonatype reported that many applications include
severe or critical ﬂaws inherited from their components [7].
Hemel et al. [8] reported that each of Linux variants embeddedin electronic devices has its own bug ﬁxes.
To investigate known bugs and security vulnerabilities of acloned component, developers and security analysts need to
identify an original version of the component and understandhow the cloned component is different from the original one.
However, in general identifying the original version is tediousand time-consuming. The main reason is that original component names and version numbers are often unrecorded [9].
Another reason is that a cloned component may be a derived
version in a different project. For example, Firefox includes
another copy of zlib in security/nss/lib/zlib directory; the version is a part of the NSS component. To identify
an original version of a cloned component, an analyst has
to compare its source code with all the existing versions ofcomponents in its software ecosystem.
A baseline method to analyze a cloned component is code
comparison using ﬁle hash values such as SHA-1 and MD5.
Since the method cannot detect modiﬁed ﬁles, Kawamitsu
et al. [10] proposed a code comparison technique that identiﬁes
the most similar ﬁle revision in a repository as an original version of a ﬁle. The experiment reported 20% of cloned ﬁles are
modiﬁed in eight projects. Although the method is effective, its
simple pairwise comparison of ﬁles is inefﬁcient to analyze anentire software ecosystem, which includes millions of source
ﬁles.
In this research, we propose a code search method tailored
for analyzing a cloned component. It takes as input a setof source ﬁles, and reports existing components includingﬁles that are similar to the input ﬁles. The method ranks
components using aggregated ﬁle similarity, assuming a cloned
component is the most similar to the original component. A
reported list of components enables developers and security
analysts to compare their cloned component with its original
version.
Our code search method employs the b-bit minwise hashing technique [11] that is an extension of Min-Hash technique [12], [13]; in summary, the technique enables to estimate
ﬁle similarity using hash signatures. Our method constructs a
database of hash values for each ﬁle in a software ecosystem.
Using the database, our method then extracts a subset of ﬁleslikely similar to a query and then computes actual similarity
for the subset. Although a database construction takes time,
we can search similar ﬁles within a practical time.
We also deﬁne a ﬁltering method for components using ﬁlesimilarity. Since different versions of a library often include
similar ﬁles, we select components having the most similarﬁles as a representative set.
We conducted an experiment to evaluate the effectiveness ofthe tool. As the ground truth, we manually identiﬁed original
versions of 75 cloned components included in source codeof Firefox 45.0 and Android 4.4.2 rc1. We then analyzed thecomponents with a database of Debian GNU/Linux packages
including 10 million source ﬁles. Recall of the top-ﬁve components in the extracted lists is 0.907, while recall of a baseline
using SHA-1 ﬁle hash is 0.773. To obtain all the originalcomponents, a user needs to investigate 551 components inthe lists. It is smaller than 931 components reported by thebaseline method. The result shows that our method ranks theoriginal components at higher positions and reduces manual
effort of a user.
The contributions of the paper are summarized as follows.
• We deﬁned a code search method to extract similar ﬁlesfrom a huge amount of source ﬁles efﬁciently.
• We deﬁned a component ﬁltering method to select likely
original components.
• We created the ground truth dataset of actual clone-andown reuse instances for two major OSS projects, andevaluated our method using the dataset.
Section II shows related work of our approach. The approach itself is detailed in Section III. Section IV presents
the evaluation of our approach using OSS projects. Section V
describes the threats to validity of the work. Section VI
describes the conclusion and future work.
II. R ELATED W ORK
A. Code Clone Detection
Code clone detection has been used to analyze sourcecode reuse between projects. Kamiya et al. [14] proposed
CCFinder to detect similar code fragments between ﬁles.
German et al. [15] used CCFinder to detect code siblings
reused across FreeBSD, OpenBSD and Linux kernels. They
identify the original project of a code sibling by investigating
the source code repositories of the projects. Hemel et al. [8]analyzed vendor-speciﬁc versions of Linux kernel using theirown clone detection tool. Their analysis showed that eachvendor created a variant of Linux kernel and customized manyﬁles in the variant.
Koschke et al. [6] also used a clone detection technique toanalyze code clone rates in 7,800 OSS projects. They foundthat a relatively large number of projects included copies oflibraries. They excluded the copies from analysis, because theanalysis did not focus on inter-project code reuse.
Krinke et al. [16] proposed to distinguish copies fromoriginals using the version information recorded in source code
repositories. Krinke et al. [17] used the approach to analyze

GNOME Desktop Suite projects. The result shows that there isa lot of code reuse between the projects. Although the version
information is useful to select older ﬁles as candidates ofreused ﬁles, our method does not use it because source code
repositories are not always available.
Sajnani et al. [18] proposed SourcererCC, a scalable code
clone detection tool. They optimized comparison of two codefragments, based on an observation that most of ﬁles aredifferent from one another. We employ b-bit minwise hashing technique to avoid unnecessary code comparison. Our
approach can be combined with SourcererCC’s optimization.
Sasaki et al. [19] proposed a ﬁle clone detection tool named
FCFinder. The tool normalizes source ﬁles by removing code
comments and white space, and compare the resultant ﬁlesusing MD5 hash. This method is not directly applicable to our
problem, because it cannot detect similar but modiﬁed ﬁles.
Hummel et al. [20] proposed to use an index databasefor instant code clone detection. While it is similar to ourapproach, the clone index is designed to report source code
locations. It is not suitable to compute source ﬁle similarity.
Jiang et al. [21] proposed DECKARD, a code clone detection tool using a vector representation of an abstract syntax
tree of source code. Nguyen et al. [22] extended a vector
representation for a dependence graph and proposed a code
clone detection tool named Exas. The tool has been used
to detect common patterns in source code [23], rather thanidentiﬁcation of similar ﬁles.
Detected instances of source code reuse are clues to extract the common functionalities in software products. Rubinet al. [24] reported that industrial developers extract reusable
components as core assets from existing software products.
Bauer et al. [25] proposed to extract code clones acrossproducts as a candidate of a new library. Ishihara et al. [26]proposed a function-level clone detection to identify common
functions in a number of projects. Our method can be seen as
a ﬁle-level detection of cloned components.
While our method enables a user to select original components for comparison, it does not directly support a source code
comparison activity itself. Duszynski [27] proposed a code
comparison tool to analyze source code commonalities froma number of similar product variants. Sakaguchi et al. [28]also proposed a code comparison tool that visualizes a uniﬁed
directory tree for source ﬁles of several products. Fischer
et al. [29] proposed to extract common components fromexisting product variants and compose a new product.
B. Origin Analysis
Godfrey et al. [30] proposed origin analysis to identify
merged and split functions between two versions of sourcecode. The method compares identiﬁers used in functions to
identify original functions. Steidl et al. [31] proposed todetect source code move, copy, and merge in a source code
repository. The method identiﬁes a similar ﬁle in a repository
as a candidate of an original version.
Kawamitsu et al. [10] proposed to identify an original
version of source code in a library’s source code repository.

It is an extension of origin analysis across two source code
repositories. A user of the method must know what libraryis included in the program. Our method does not need suchknowledge, because it compares input ﬁles with all the existing
components in a software ecosystem.
Sojer et al. [32] pointed out that ad-hoc code reuse fromthe Internet has a risk of a license violation. Inoue et al. [33]proposed a tool named Ichi-tracker to identify the origin of adhoc reuse. It is a meta-search engine to obtain similar source
ﬁles on the Internet and visualizes the similarities. While Ichitracker takes a single ﬁle as a query, our method enables a user
to analyze a set of ﬁles as a component.
Kanda et al. [34] proposed a method to recover an evolution
history of a product and its variants from their source codearchives without a version control. The approach also compares the full contents of source ﬁles, using a heuristic thatdevelopers tend to enhance a derived version and do not often
remove code from the derived version. It might complement
our approach, because it helps to understand an evolution
history of components reported by our method.
Antoniol et al. [35] proposed a method to recover the
traceability links between design documents and source ﬁles.
The method computes similarity of classes by aggregating
similarity of their attribute names to identify an original classdeﬁnition in design documents. Our method can be seen asa coarse-grained extension that identiﬁes original components
using aggregated ﬁle similarity.
Hemel et al. [36] proposed a binary code clone detection to
identify code reuse violating software license of a component.
The method compares the contents of binary ﬁles between atarget program and each of existing components. Sæbjørnsen
et al. [37] proposed a clone detection for binary code. It uses
a locality sensitive hashing to extract similar code fragments
in binary ﬁles. Qiu et al. [38] proposed a code comparison
method for a binary form to identify library functions included
in an executable ﬁle.
For Java software, Davies et al. [39], [40] proposed a ﬁlesignature to identify the origin of a jar ﬁle using classes andtheir methods in the ﬁle ignoring the details of code. German
et al. [41] demonstrated the approach can detect OSS jar ﬁlesincluded in proprietary applications. Mojica et al. [42] used
the same approach to analyze code reuse among Android
applications. Ishio et al. [43] extended the analysis to automatically identify libraries copied in a product. Differently
from those approaches, our method directly compares source
ﬁles because small changes in ﬁles might be important tounderstand differences between a cloned component and its
original version.
Luo et al. [44] proposed a code plagiarism detection applicable to obfuscated code. The detection method identiﬁes
semantically equivalent basic blocks in two functions. Chenet al. [45] proposed a technique to detect clones of Android
applications. The analysis uses similarity between control-ﬂow
graphs of methods. Obfuscated code is out of scope of our
method. Ragkhitwetsagul et al. [46] evaluated the performanceof code clone detection and relevant techniques for source ﬁles*










%
)
$%

 



    !
 "  
#$%&'!(#)&'!(
 
 

 
 

 
    

Fig. 1. An example input and output of our method. Two components are
selected to cover four ﬁles. They are sorted by aggregated ﬁle similarity.

modiﬁed by code obfuscators and optimizations.
III. O UR A PPROACH
Our method takes as input a set of source ﬁles and reports
a list of components that likely include the original versionof the ﬁles in a software ecosystem. In this paper, a software
ecosystem is a collection of components {C1 , C2 , · · · , Cn }.
Each component comprises a set of ﬁles. Our implementation
assumes that each component has a unique name such as “zlib1.2.8” and “libpng-1.6.9”.
We use source ﬁle similarity, because popular libraries
written in C/C++ are used by many projects. While the main
target of our method is C/C++, our implementation supports
C/C++ and Java. Our method is language independent except
for the lexical analysis step. The lexical analysis assumes thateach source ﬁle has a correct ﬁle extension representing a
programming language.
Our method comprises two steps: component search andcomponent-ranking. The ﬁrst step extracts a set of components
R including ﬁles similar to query ﬁles Q. The second stepﬁlters and ranks components according to aggregated ﬁlesimilarity. We use a simple assumption: A component in a
database is likely original if it has the most similar ﬁle to aquery ﬁle.
Fig. 1 shows an example input and output of our method.
The example query Q includes ﬁve ﬁles: P.c, P.h, Q.c,
R.c, and S.c. Our method compares each query ﬁle withﬁles in a component database. In the example, our component
search step detects similar ﬁles in three components X-1.0,
X-1.1, and Y-0.2. Three edges connecting a product andcomponents have labels indicating the sum of similarity values.
Using ﬁle similarity and the aggregated similarity, our methodranks Y-0.2 at the top and X-1.1 at the second. Y-0.2 isthe most likely original component, because it has four similar

Example code:
a: while ((*dst++ = *src++) != ’\0’);b: while (*dst++ = *src++);trigrams(a)trigrams(b) _, _, while ,  _, while, ( , _, _, while ,  _, while, ( , while, (, ( ,  (, (, * , while, (, * , (, *, dst ,  *, dst, ++ , (, *, dst ,  *, dst, ++ , dst, ++, = ,  ++, =, * , dst, ++, = ,  ++, =, * , =, *, src ,  *, src, ++ , =, *, src ,  *, src, ++ , src, ++, ) ,

 src, ++, ) ,

 ++, ), != ,  ), !=, ’\0’ , ++, ), ; , !=, ’\0’, ) ,  ’\0’, ), ; , ), ;, _ ,  ;, _, _ 

sim(a, b) = ), ;, _ ,  ;, _, _ |trigrams(a) ∩ trigrams(b)|11== 0.579|trigrams(a) ∪ trigrams(b)|19Fig. 2. An example of similarity value. A bold trigram is unique to a codefragment.

ﬁles. X-1.1 is the second, because its two ﬁles P.h and Q.c
are more similar than ﬁles in Y-0.2. Those ﬁles are also
likely original ﬁles. Our method ﬁlters out X-1.0, because
it does not have a ﬁle whose similarity is higher than othercomponents.
A. Component Search
Our component search uses a ﬁle-by-ﬁle comparison. Givena query set of source ﬁles Q, we extract candidates of originalcomponents R from a collection of components as follows.
R = {Ci | ∃q ∈ Q, f ∈ Ci . sim(q, f ) ≥ th}where sim is a similarity function and th is a similarity
threshold, respectively. It should be noted that the deﬁnition
does not use release date of components, because there isa time lag between an ofﬁcial release of a project and its
packaging for a software ecosystem. If accurate timestamps
are available for both query ﬁles and components, our method
can use a subset of components older than query ﬁles.
Our similarity of source ﬁles is Jaccard index of token
trigrams deﬁned as follows.
sim(f1 , f2 ) =|trigrams(f1 ) ∩ trigrams(f2 )||trigrams(f1 ) ∪ trigrams(f2 )|where trigrams(f ) is a multiset of trigrams extracted from aﬁle f . We employ the Jaccard index because it approximatesthe edit distance [47]. A higher similarity indicates that a larger
amount of source code could be reused. Compared with thelongest common subsequence, it is less affected by moved
code in a ﬁle. Furthermore, it can be efﬁciently estimated using
the Min-Hash technique [12], [13].
We use a token as a trigram element to ignore the lengthof identiﬁer names. A lexer extracts a token sequence by removing comments and white space. The lexer keeps identiﬁers

Algorithm 1 Component Search
Inputs
Q: A set of ﬁles to be analyzed.
F : A set of existing ﬁles in a software ecosystem.
Owners(f ): A mapping from a ﬁle f to components
including the ﬁle.
Outputs
R: A set of components including query ﬁles.
S(q, C): Similarity of a query ﬁle q and its most similarﬁle in a component C.
1: Initialize R ← φ
2: Initialize S(q, C) ← 0 for all possible q and C.
3: for q ∈ Q do
4:for f ∈ F domin(|trigrams(q)|,|trigrams(f )|)5:
if max(|trigrams(q)|,|trigrams(f)|) ≥ th then6:
if sime (q, f ) ≥ th − m then7:
if sim(q, f ) ≥ th then8:
for Ci ∈ Owners(f ) do
9:R ← R ∪ Ci
10:
if S(q, Ci ) < sim(q, f ) then11:
S(q, Ci ) ← sim(q, f )12:
end ifend for13:
14:
end if15:
end if16:
end if17:
end for
18: end foras they are, because identiﬁers are important clues to identify
a version [10]. Our lexer also keeps preprocessor directives
in C/C++ source ﬁles. Fig. 2 shows a pair of example codefragments, their trigrams, and a similarity value obtained fromthe trigrams. In the ﬁgure, a trigram  A, B, C indicates
three consecutive tokens in a code fragment. A symbol “ ” ina trigram indicates the beginning and end of a ﬁle.
Algorithm 1 shows an entire process of the component
search step. The algorithm starts with a query Q and a ﬁlecollection F . Since the same ﬁle may be included in multiple
components, we use F to represent a set of existing uniqueﬁles in a software ecosystem, and Owners(f ) to represent a
set of components including the ﬁle f . Our implementation
uses SHA-1 ﬁle hash to detect ﬁles shared by components.
The algorithm computes similarity values S(q, C) between
query ﬁles and their most similar ﬁles in C deﬁned as follows.
S(q, C) = max {sim(q, f ) | f ∈ C}
The line 2 initializes S(q, C) to zero and the lines 10 and
11 update it. A ﬁle f ∈ C may update similarity values ofmultiple query ﬁles, because a developer could copy the ﬁlef to create the ﬁles.
The whole process compares all the pairs of q ∈ Q andf ∈ F with two optimizations. First, it compares the size oftrigram sets at the line 5. The statement uses the followingmin(|X|, |Y |)|X ∩ Y |< th =⇒< thmax(|X|, |Y |)|X ∪ Y |The property is derived from min(|X|, |Y |) ≥ |X ∩ Y | andmax(|X|, |Y |) ≤ |X ∪ Y |. Secondly, the process computes
sime (q, f ) that is an estimated similarity computed by bbit minwise hashing technique [11]. Since it may have amargin of error, line 6 uses th − m as a threshold, wherem speciﬁes allowable errors. Finally, the process computes anactual similarity metric sim(q, f ) to compare trigrams. If it ishigher than a threshold, components including f are added
to R in the component-ranking step. The lines 10 and 11
record the highest similarity of a query ﬁle q and a component
Ci . The recorded similarity values S(q, Ci ) are used in thecomponent-ranking step.
The algorithm works efﬁciently because sime (q, f ) avoids
unnecessary actual similarity computation. In summary, b-bit
minwise hashing technique approximates a similarity of ﬁlesby comparing k pairs of b-bit signatures. Each signature represents a trigram sample in a ﬁle. In case of our implementation,
we chose parameters b = 1, k = 2048; 2048 trigram samples
in a source ﬁle are selected and then translated into 1-bit
signatures. Consequently, a ﬁle is represented by a 2048-bit
vector.
To compute sime (q, f ), we use k independent hash functions hi (t) (1 ≤ i ≤ k). Each function translates a trigram t ina ﬁle into an integer. Our implementation uses 64-bit integers
as described in the Appendix. Using the hash functions, minhash signatures mi (f ) (1 ≤ i ≤ k) for a ﬁle f are computed
as follows [13].
mi (f ) = min {hi (t) | t ∈ trigrams(f )}A min-hash signature mi (f ) represents a trigram sample
selected from a ﬁle. If two ﬁles f1 and f2 are more similar,
more likely mi (f1 ) and mi (f2 ) select the same trigram andresult in the same value. The probability of mi (f1 ) = mi (f2 )is represented by the similarity of ﬁles [13]:P (mi (f1 ) = mi (f2 )) = sim(f1 , f2 )We use b-bit min-hash signatures bi (f ) (1 ≤ i ≤ k) extracted
from min-hash signatures. In case of b = 1, the signatures arecomputed as follows [11].
bi (f ) = LSB(mi (f ))where LSB is the least signiﬁcant bit; i.e., bi (f ) ∈ {0, 1}.
The probability of bi (f1 ) = bi (f2 ) is represented by
P (bi (f1 ) = bi (f2 )) = sim(f1 , f2 ) +1 − sim(f1 , f2 )2because the condition is satisﬁed when mi (f1 ) = mi (f2 ) or
two different signatures have the same LSB by chance.
We estimate a similarity of ﬁles q and f using their b-bit
min-hash signatures bi (q) and bi (f ) (1 ≤ i ≤ k). Since theprobability of bi (q) = bi (f ) is dependent on a similarity, we

Density (%)

property to avoid unnecessary comparison.
20
15
10
5
0
−0.10

−0.05

0.00

0.05

0.10

Actual Similarity − Estimated Similarity

Fig. 3. The distribution of errors obtained by randomly created samples forsim(f1 , f2 ) = 0.6.

compute an estimated similarity sime (q, f ) from an observed
probability as follows.
sime (q, f )=Po (q, f )=1(Po (q, f ) − ) × 2
2
k
1
1−
XOR(bi (q), bi (f ))k i=1

where Po (q, f ) is an observed probability of bi (q) = bi (f )on k (2048) samples. The maximum value of sime (f1 , f2 )is 1.0. If two ﬁles are the same, their estimated similarity isalways 1.0. Although the sime (f1 , f2 ) could be negative, we
simply regard them as zero. It should be noted that this is a
simpliﬁed version for ease of implementation, compared withthe original (strict) estimation that was conducted in [11].
Computation of sime is O(1), because it uses XOR bitoperations and bit counting. It is much efﬁcient than Jaccard
index computation that requires O(n) depending on ﬁle sizen. Since a signature does not change, we compute b-bit minhash signatures for each f ∈ F and store them in a database.
The tool loads the entire database on memory because it is
sufﬁciently compact; 1 GB memory can store signatures forfour million ﬁles. For each query, we then compute signatures
for q ∈ Q and compare them with signatures in the database.
The line 6 in Algorithm 1 uses th − m, where m speciﬁes
allowable errors. We use m = 0.1 for our implementation.
Fig. 3 shows the distribution of errors of 108 randomly created
Po samples under the condition sim(f1 , f2 ) = 0.6. In theﬁgure, sim(f1 , f2 ) − sime (f1 , f2 ) is always less than 0.1. Inother words, sime (f1 , f2 ) > th−m. We conﬁrmed that it was
sufﬁcient in the experiment.
B. Component Ranking
The second step ﬁlters and ranks extracted components R to
enable a user to identify an original component easily. To ﬁlter
components, we consider that C1 is a better candidate thanC2 if C1 provides more similar ﬁles than their correspondingTABLE I
T HE SEARCH RESULT FOR THE EXAMPLE INPUT IN F IG . 1
Q
P.c
P.h
Q.c
R.c
S.c
SQ (C)
|C|

X-1.0
1.0
0.9
0.9
0.0
0.0
2.8
3

X-1.1
0.7
1.0
1.0
0.0
0.0
2.7
3

Y-0.2
1.0
0.9
0.9
1.0
0.0
3.8
5

TABLE IIA N EXCERPT OF A SEARCH RESULT FOR M O D U L E S / Z L I B DIRECTORY OF
F IREFOX 45.0.
Q
gzlib.cinﬂate.cmozzconf.hzconf.hzlib.hzutil.c
SQ (C)|C|

zlib 1.2.8
1.000 (gzlib.c)
0.995 (inﬂate.c)
0.000
0.985 (zconf.h)
0.997 (zlib.h)
1.000 (zutil.h)25.971
51

MongoDB 3.2.8
0.000
0.999 (third party/zlib-1.2.8/inﬂate.c)
0.000
0.985 (third party/zlib-1.2.8/zconf.h)
0.997 (third party/zlib-1.2.8/zlib.h)
1.000 (third party/zlib-1.2.8/zutil.h)19.9509351

source ﬁles in C2 . We deﬁne this relation C1 ⊃S C2 ,C1 ⊃ S C2⇐⇒(∀q.S(q, C1 ) ≥ S(q, C2 ) ∧∃q.S(q, C1 ) > S(q, C2 ) ) ∨(∀q.S(q, C1 ) = S(q, C2 ) ∧ |C1 | < |C2 |)where S(q, C) represents similarity values recorded in Algorithm 1. We then select a smaller component (in terms ofthe number of ﬁles) if two components have tied similarity,
because it is likely a simpler version. Using the relation, we
select a subset of components RS from R:
RS = {C ∈ R | Ci ∈ R. Ci ⊃S C}
Table I shows example similarity values S(q, C) for theexample input in Fig. 1. Since the similarity values satisfy
the condition of Y-0.2 ⊃S X-1.0, we obtain RS ={Y-0.2, X-1.1} excluding X-1.0.
We assign a higher rank to a component that could provide
a larger amount of code to the query ﬁles. To measure thedegree of potential code reuse, we use the sum of ﬁle similarity
SQ (C) deﬁned as follows.

S(q, C)SQ (C) =q∈Q

We rank components in the descending order of SQ (C).
Our method provides the following information to a user.
• A list of components RS sorted by SQ (C). Each component is reported with attributes SQ (C), |Q|, and |C|.
The result for the example input is following.
Y-0.2 (3.8 / 5) 5 files
X-1.1 (2.7 / 5) 3 files
A pair of SQ (C) and |Q| indicates the amount of reusedcode in Q. |C| is also important to analyze whether Q isa complete copy of C or not.
• A full list of components R in the descending order of
SQ (C). We provide this list because our ﬁltering may
accidentally exclude an original component from RS . A
user can analyze all the components if necessary.
• A table of similarity S(q, C). Although the component
search step does not need ﬁle names, our implementation
uses ﬁle names for this report. Table II shows an excerptof a similarity table for modules/zlib directory ofFirefox 45.0. It shows that the analyzed directory is likely
a clone of zlib 1.2.8 with some modiﬁcation. It also
shows that ﬁle inflate.c in Firefox likely includes
a similar change as MongoDB 3.2.8.

These information enables a user to easily focus on candidatesof original components and investigate actual source ﬁles in
the components.
IV. E VALUATION
We investigate two research questions to evaluate the effectiveness of our method.
RQ1. Does our method accurately report an original component?
RQ2. Is our method efﬁcient?
To answer the questions, we analyze actual clone-and-own
instances in two products: Firefox 45.0 and Android 4.4.2 rc1.
These projects reuse components in a well-organized manner.
Firefox developers often record version numbers of reusedcomponents in commit messages in their source code repository. Android developers manage their own git repositories forcloned components and record Change-Id to identify changesof the original components. We manually analyzed directories whose names are likely cloned component names, andidentiﬁed original versions using the commit-log messages.
We then excluded components whose original versions areunidentiﬁable. We spent about one week for the analysis.
Our database of components is the Snapshot Archive of
Debian GNU/Linux [48]. We regard a version of a Debianpackage as a component. The archive includes all the existingsource code packages released for Debian from 2005 until thepresent. We automatically downloaded ﬁles through its machine usable interface [49]. While Debian package maintainers
sometimes apply their own patches, we included only original
source tarballs whose names matched a pattern “*.orig.*”.
The database includes 200,018 package ﬁles (868 GB in
total). The resultant dataset includes 9,730,689 C/C++ ﬁlesand 1,310,235 Java ﬁles. The total size is 5,733 MLOC (185GB) including comments and white space.
Our queries comprise 21 directories in Firefox and 54
directories in Android whose original versions are available
as Debian packages. The directory names and corresponding
Debian package names are included in the Appendix. Fig. 4
plots the distributions of the numbers of ﬁles in each of
directories. The queries include various size of components;
the minimum one comprises two ﬁles, while the maximum one
comprises 1,163 ﬁles. The medians of Firefox and Android
queries are 76 and 79.5, respectively. Their total number is
13,720. Since the database includes copies of Firefox and1200#Selected Components

30

1000
800
600
400
200

25
20
15
10
5
0

0

Baseline

Firefoxth=0.9th=0.8th=0.7th=0.6

Android

Fig. 6.
Fig. 4.

th=1.0The number of selected components for each query (|RS |).

The number of ﬁles in each query (|Q|).

A. Accuracy

8000
6000
4000
2000
0
Baseline th=1.0

Fig. 5.

th=0.9th=0.8th=0.7th=0.6

The number of components reported for each query (|R|).

Android themselves, we exclude their related packages fromthe search space.
The baseline of evaluation is a simple ﬁle search using
SHA-1 ﬁle hash instead of our similarity function (i.e.,
R = {C | Q ∩ C = φ}). We sort the extracted components
in the descending order of |Q ∩ C| that is equivalent to
SQ (C). Our method uses ﬁve threshold for component search:
th = 0.6, 0.7, 0.8, 0.9, and 1.0 in order to evaluate the effectof threshold. The parameter th = 1 ignores white space andcomments, differently from the baseline.
For each query, we obtain the rank of the original version
in an extracted list. The rank approximates manual effort of auser. To evaluate the effect of our ﬁltering method separatelyfrom search method, we use both our ﬁltering result RS and afull result without ﬁltering R. In case of RS , we assume that auser investigates all the elements in RS , and then investigates
R if RS does not include an original component.

Fig. 5 shows the distribution of the size of |R|, i.e. thenumber of reported components for each query. It showsthat many similar ﬁles are included in various components.
In case of the baseline method, the median of |R| is 60.
Since our method detects similar ﬁles, a lower thresholdresults in a larger number of components. The medians of|R| are 145, 318, 367, 375, and 500 in cases of th = 1.0
through th = 0.6, respectively. It should be noted that theplots exclude queries that report no components. The baseline
method reports no component for three queries. One of themis the smallest component whose ﬁles are modiﬁed. The othertwo components have differences in comments and whitespace.
Fig. 6 plots the number of selected components (|RS |) for
each query. As shown in this ﬁgure, the size is less than ﬁvecomponents for most of queries. The median is 1 in casesof the baseline and th = 1.0. The median is 2 in cases ofth = 0.9 through th = 0.6. While a lower threshold results
in a larger RS , the difference is not statistically signiﬁcant.
Wilcoxon rank sum test results in p = 0.244 for two cases
th = 0.9 and th = 0.6. Our ﬁltering approach successfully
selects a small number of components.
Table III summarizes recall of components appeared in the
top-k elements of resultant lists. For example, the baseline
method ranks 64% of original components at the top of lists.
The column “All” shows recall of components in the entire
lists. The column “Rank Total” shows the sum of positionsof the original components in the results. It approximates theeffort to identify all the original components in the lists. Eachrow shows the result of a conﬁguration. Each conﬁguration
uses a search method in the ﬁrst column. The top six conﬁgurations simply reports a full list of R without our ﬁltering. The
bottom six conﬁgurations use a ﬁltered list of RS . The resultshows that our method with th = 0.9, RS performs the best
among the conﬁgurations. A user can identify all the originalcomponents in the top-5 components for 90.7% cases and 551

TABLE III
R ECALL OF ORIGINAL COMPONENTS IN TOP -k SEARCH RESULTS .
Search Method
Baselineth = 1th = 0.9
th = 0.8
th = 0.7
th = 0.6
Baselineth = 1th = 0.9
th = 0.8
th = 0.7
th = 0.6

Ranking
R
R
R
R
R
R
RS
RS
RS
RS
RS
RS

Top-1
0.640
0.653
0.680
0.680
0.627
0.613
0.707
0.733
0.733
0.733
0.680
0.667

Top-3
0.760
0.773
0.800
0.813
0.773
0.760
0.840
0.867
0.893
0.880
0.853
0.853

Top-5
0.773
0.787
0.827
0.827
0.787
0.773
0.840
0.867
0.907
0.893
0.880
0.880

Top-10
0.827
0.853
0.867
0.867
0.840
0.840
0.867
0.893
0.920
0.920
0.907
0.907

All
0.960
0.987
1.000
1.000
1.000
1.000
0.960
0.987
1.000
1.000
1.000
1.000

Rank Total
931
1017
759
818
930
928
719
785
551
627
692
689

Query ﬁles
png.c
png.h
pngpread.c
pngrtran.c
pngrutil.c
pngset.cpngtest.cSQ (C)|C|

libpng 1.2.46
0.962
0.982
1
1
0.985
0.987
1
41.90245

libpng 1.2.49
0.958
0.980
0
0.999
0.978
1.000
0.999
39.90045

components in total. Our method reduces 40% of user’s effort
compared with the baseline reporting 931 components. The
baseline method also requires additional effort to analyze threequeries that resulted in no components.
The result shows that modiﬁed ﬁles are important to identify
original components. A simple exclusion of white space andcomments does not improve the result; our similar ﬁle searchwith th = 1 and R results in a longer list of components,
although it slightly improves recall. Our method with th < 1
performs better than the baseline and th = 1, because
modiﬁed ﬁles provide a clue to sort components and identify
an original version. A lower threshold does not improve a
result, because it also detects various versions of the same
components affecting the results.
Our ﬁltering method successfully improves results in all
the cases. In case of th = 0.9, it reduces 27% of manual
effort to investigate the reported lists. This is because themost similar version of a library among several versions in
R is actually the original version. In this experiment, only
882 out of 13720 query ﬁles (6.4%) are modiﬁed in Firefox
and Android. Developers tend to reuse source ﬁles without
modiﬁcation.
We do not regard other components in RS as false positives,because some of them are also informative. For example,
Android includes a modiﬁed version of libpng 1.2.46. Our
method ranks the original version at the top. Our method alsoranks libpng 1.2.49 at the second. Table IV shows an excerpt

Time for each query (sec.)

TABLE IVA N EXCERPT OF A SEARCH RESULT OF LIBPNG COMPONENT IN
A NDROID 4.4.2 RC 1 WITH th = 0.9.
1500

1000

500

0
th=1.0th=0.9Fig. 7.

th=0.8th=0.7th=0.6Time spent for each query.

from the reported similarity values for them. It shows that ﬁlepngset.c in Android is the same as a ﬁle in libpng 1.2.49.
The ﬁle includes a security ﬁx for CVE-2011-3048 [50] foundin 1.2.x before 1.2.49. Our method successfully reports thatthe cloned component includes a part of the newer version.
Our ﬁltering method excluded some original components
from RS . An example is the Expat XML parser libraryin Android. Our method reports node-expat-2.3.12 that is a
NodeJS binding component instead of the original version,
because both Android and the component includes all theﬁles in the original Expat library and an additional header
ﬁle expat_config.h generated by configure script.
Another example is zlib 1.2.8 in Android. In this case, zlib
1.2.8 component in the database does not include contrib
ﬁles because of a license issue. Hence, our method accidentally
reports another component including a full copy of the original
version. This is a limitation of our repository-based approach.
Our ﬁle search cannot identify any origins for 1240 ﬁles
(9.04%) using th = 0.6. They are likely added by the projects.
We believe that this is also useful for a user to understand how
a cloned component is modiﬁed. The baseline method does notprovide this additional information.

TABLE V
T IME FOR 75 QUERIES AND THE NUMBERS OF COMPUTED SIMILARITYVALUES .

#sime (q, f )N/A
93,836,051
5,468,450,021
11,463,856,656
18,229,604,035
25,967,936,034#sim(q, f )N/A
27,30072,84898,512
125,520
189,043

10000

25000

Time (sec.)
Median
Total
2.0
270
23.7
5,013
50.1
7,719
51.4
8,956
74.3 11,951
77.7 12,595

0Frequency

MethodBaselineth = 1th = 0.9
th = 0.8
th = 0.7
th = 0.6

−0.25

−0.20

−0.15

−0.10

−0.05

0.00

0.05

0.10

Actual Similarity − Estimated Similarity

Fig. 8.
The distribution of errors for ﬁle pairs compared during theexperiment with th = 0.6.

B. Performance
Our experiment is performed on a workstation equippedwith Intel Xeon E5-2690 v3 (2.6 GHz), 64 GB RAM, and
2 TB HDD. We use a single thread to execute a query.
Figure 7 shows the time spent for each query with different
threshold. A lower threshold takes longer time, because it
affects a size-based optimization of Algorithm 1 (Line 5). The
median is 77.7 seconds for th = 0.6. The longest query takes
25 minutes. Table V shows the median time required for eachquery and the total time for 75 queries for each parameter.
The baseline method takes about 200 seconds to read ﬁles andcompute SHA-1 ﬁle hash values. Comparison of SHA-1 ﬁlehash takes 70 seconds. While our method takes signiﬁcantly
longer time than the baseline, the time is still practical because
a user can analyze a result of a query during execution of otherqueries. It should be noted that the query time is strongly
dependent on component search. The component-ranking step
takes less than 2 seconds in all the conﬁgurations.
Our method compares each query ﬁle with a databaseof ﬁles. Since the total number of query ﬁles is 13,720,
our method takes at most a few seconds to compare a ﬁlewith 10 million ﬁles. This performance is achieved by b-bit
minwise hashing technique. To analyze the effect of similarity
estimation, we count the numbers of computed estimatedand actual similarity values. They are shown in the columns#sime (q, f ) and #sim(q, f ) of Table V. The table clearlyshows that sime (q, f ) enables us to avoid the computationof sim(q, f ). The ratio of #sim(q, f ) is reported to be lessthan 0.03% in all cases.
The experiment uses m = 0.1 in Algorithm 1. We executed
the same experiment with m = 0.2 and conﬁrmed the same
result. Hence, m = 0.1 is sufﬁciently large. Fig. 8 shows the
distribution of errors between actual and estimated similarity.
The lowest estimated similarity satisfying the sim(q, f ) ≥ 0.6
is sime (q, f ) = 0.513.
Our implementation constructs a database of components inprior to search. We took about 5 days to extract all the ﬁlesfrom package archives, remove duplicated ﬁles, and computeﬁle signatures. The archive extraction step is the bottleneck,because the step has to process 2 TB of ﬁles in archives.
Our database uses 4 GB for ﬁle signatures and 20 GB for
component names and ﬁle names. Our implementation keeps
ﬁle signatures on memory. Our database can be incrementally
updated, by simply adding ﬁle signatures. A larger databasecan be hosted by multiple servers, because we can search
multiple component sets independently and later merge theﬁnal result.
V. T HREATS TO VALIDITY
We analyzed Firefox and Android source code repositories,
because developers in the projects keep their record of code
reuse. Our result might be dependent on code reuse strategiesof the projects.
We manually analyzed commit messages recorded in therepositories. Since the version information is veriﬁed by two
authors but no developers of the projects, the result has a riskof human error.
The result is dependent on components included in a
database. Our database represents a single software ecosystem:
Debian GNU/Linux source code packages. Since we usedoriginal source code provided by each project, we believe thepackages reﬂect activities of various projects. On the other
hand, our analysis does not reﬂect source code modiﬁed bypackage maintainers of the operating system.
The collection of software packages may miss important
packages. For example, libpng project maintains a numberof branches: libpng 0.x, 1.0.x, 1.2.x, 1.4.x, 1.5.x, 1.6.x, and1.7.x. Since package maintainers selected major branches tocreate Debian packages, our dataset includes a subset ofofﬁcial versions. It may affect the analysis of variants in theexperiment.
While the Debian Snapshot Archive is publicly available, we
found several errors (i.e., 404 not found) and corrupted archiveﬁles during our analysis. Since the entire dataset is large, theresult might be affected by this accidental data corruption.
The performance of b-bit minwise hashing signature isdependent on underlying hash functions. It may miss a similar
ﬁle with a very low probability. We conﬁrmed that we did
not miss any ﬁles during the experiment. For replicability, ourstrategy to deﬁne 2048 hash functions is included in Appendix.
VI. C ONCLUSION
This paper proposed a code search method to extract original components from a software ecosystem. In the experiment, our method successfully reported original components

compared with the baseline method. Our implementation also
reports the computed similarity values to enable further analysis.
To implement an efﬁcient code search, we used b-bit minwise hashing technique. It enabled us to extract less than
0.03% of likely similar ﬁles from a database in a second. Our
method also introduced a component ﬁltering method using
aggregated ﬁle similarity. It reduces manual effort to analyze
reported components.
In future work, we would like to apply our method to analyze clone-and-own reuse activity in various projects including
industrial organizations. We are also interested in a systematic
method to analyze known issues and vulnerabilities caused bycloned components in a software product.
ACKNOWLEDGMENT
This work was supported by JSPS KAKENHI Grant Numbers JP25220003, JP26280021, and JP15H02683.
We are grateful to Naohiro Kawamitsu for the implementation of hash functions and Raula Gaikovina Kula for hiscomments to improve the manuscript.

TABLE VIA NALYZED DIRECTORIES IN F IREFOX 45.0
Package Namecairo-1.10
double-conversion-1.1.1
graphite2-1.3.6
gtest-1.6.0
hunspell-1.3.3
libav-11.3
libevent-2.0.21
libfﬁ-3.1
libjpeg-turbo1.4.2
libpng1.6-1.6.19
libsoundtouch-1.9.0
libspeex-1.2
libvorbis-1.3.5
libvpx-1.4.0
nspr-4.12,
nss-3.21.1
opus-1.1
snappy-1.0.4
srtp-1.4.4
stlport-5.2.1
zlib-1.2.8

Directory
gfx/cairo
mfbt/double-conversion
gfx/graphite2
testing/gtest
extensions/spellcheck/hunspell
media/libav
ipc/chromium/src/third party/libevent
js/src/ctypes/libfﬁ
media/libjpeg
media/libpng
media/libsoundtouch,media/libspeex resampler
media/libvorbis
media/libvpx
nsprpub
security/nss
media/libopus
other-licenses/snappy
netwerk/srtp
build/stlport
modules/zlib

A PPENDIX
Hash Function. Our implementation uses 2048 hashfunctions to translate a ﬁle into a ﬁle signature. We use thefollowing hash functions on 64-bit integer:hi (t) = ai × base(t) + bi
where 1 ≤ i ≤ 2048, ai and bi are randomly generated 64-bit
integers. The base(t) function translates a trigram into a 64bit integer. Since a trigram in a multiset is identiﬁed by four
elements A, B, C, and i (i-th occurrence of a trigram ABC),the base function is deﬁned as follows.
base(A, B, C, i) =(((i × 65537) + A.hashCode())×65537 + B.hashCode())×65537 + C.hashCode()

where hashCode() is String.hashCode method in
Java.
Component List. Table VI and Table VII show analyzed
directories in Firefox and Android, respectively. The package
names are deﬁned by Debian GNU/Linux package maintainers; some of them are different from ofﬁcial project names.

TABLE VIIA NALYZED DIRECTORIES IN A NDROID 4.4.2 RC 1
Package Namearduino-0022
blktrace-1.0.1
bouncycastle-1.49
bsdiff-4.3
bzip2-1.0.6
checkpolicy-2.1.11
dnsmasq-2.51
dropbear-0.49
e2fsprogs-1.41.14
easymock-2.5.2
expat-2.1.0
ﬂac-1.2.1
genext2fs-1.4.1
grub-0.97
guava-libraries11.0.2 6
harfbuzz-0.9.14
ipsec-tools-0.7.3
iptables-1.4.11.1
iputils-3:20121221
jhead-2.86
jpeg-6b
jsilver-1.0.0
junit4-4.10

Directory†
arduinoblktracebouncycastle
bsdiffbzip2
checkpolicy
dnsmasq
dropbear
e2fsprogs
easymockexpat
ﬂac
genext2fs
grub
guava

Package Namelibogg-1.2.0
libpng-1.2.46
libsepol-2.2
libusb-1.0.8
libvorbis-1.3.1
libvpx-1.3.0
libxml2-2.7.8
libxslt-1.1.26
mksh-43
netperf-2.4.4
openfst-1.3.3
openssh-5.9
openssl-1.0.1e
oproﬁle-0.9.6
pixman-0.30.0

Directory†
libogglibpnglibsepollibusblibvorbis
libvpxlibxml2
libxsltmksh
netperf
openfstopensshopensshoproﬁlepixmanharfbuzz ng
ipsec-tools
iptables
iputilsjhead
jpeg
jsilverjunit

ppp-2.4.5
protobuf-2.3.0
safe-iop-0.3.1
scrypt-1.1.6
speex-1.2rc1
srtp-1.4.4
stlport-5.2.1
stressapptest1.0.4
tagsoup-1.2
tcpdump-3.9.8

ppp
protobuf
safe-iopscryptspeex
srtp
stlportstressapptest

libgsm-1.0.13
libgsmtagsouplibhamcrest-javahamcrest
tcpdump1.1
libmtp-1.0.1
libmtpvalgrind-3.8.1
calgrindlibnl-2.0
libnl-headers zlib-1.2.8
zlib† All the component directories are located in external directory.

R EFERENCES[1] Y. Dubinsky, J. Rubin, T. Berger, S. Duszynski, M. Becker, andK. Czarnecki, “An Exploratory Study of Cloning in Industrial Software
Product Lines,” in Proceedings of the 17th European Conference on
Software Maintenance and Reengineering, 2013, pp. 25–34.
[2] P. Mohagheghi, R. Conradi, O. Killi, and H. Schwarz, “An empirical
study of software reuse vs. defect-density and stability,” in Proceedingsof the 26th International Conference on Software Engineering, 2004,
pp. 282–291.
[3] C. Ebert, “Open source software in industry,” IEEE Software, vol. 25,
no. 3, pp. 52–53, 2008.
[4] J. Rubin, A. Kirshin, G. Botterweck, and M. Chechik, “Managing forked
product variants,” in Proceedings of the 16th International Software
Product Line Conference, 2012, pp. 156–160.
[5] T. Mende, R. Koschke, and F. Beckwermert, “An evaluation of code
similarity identiﬁcation for the grow-and-prune model,” Journal of
Software Maintenance and Evolution, vol. 21, no. 2, pp. 143–169, 2009.
[6] R. Koschke and S. Bazrafshan, “Software-clone rates in open-source
programs written in C or C++,” in Proceedings of the 10th International
Workshop on Software Clones, 2016, pp. 1–7.
[7] L. Constantin, “Developers often unwittingly use components that
contain ﬂaws,” iTWorld.com, http://www.itworld.com/article/2936575/
security/software-applications-have-on-average-24-vulnerabilitiesinherited-from-buggy-components.html [Posted June 16, 2015].
[8] A. Hemel and R. Koschke, “Reverse Engineering Variability in Source
Code Using Clone Detection: A Case Study for Linux Variants ofConsumer Electronic Devices,” in Proceedings of the 19th IEEE Working
Conference on Reverse Engineering, 2012, pp. 357–366.
[9] P. Xia, M. Matsushita, N. Yoshida, and K. Inoue, “Studying reuse ofout-dated third-party code in open source projects,” JSSST Computer
Software, vol. 30, no. 4, pp. 98–104, 2013.
[10] N. Kawamitsu, T. Ishio, T. Kanda, R. G. Kula, C. De Roover, andK. Inoue, “Identifying source code reuse across repositories using LCSbased source code similarity,” in Proceedings of the 14th International
Working Conference on Source Code Analysis and Manipulation, 2014,
pp. 305–314.
[11] P. Li and A. C. Konig, “b-bit minwise hashing,” in Proceedings of the
19th International Conference on World Wide Web, 2010, pp. 671–680.
[12] J. Leskovec, A. Rajaraman, and J. Ullman, Mining of Massive Datasets.
Cambridge University Press, 2011.
[13] A. Z. Broder, “On the resemblance and containment of documents,” inProceedings of the Compression and Complexity of Sequences, 1997,
pp. 21–29.
[14] 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, vol. 28, no. 7, pp. 654–670,
2002.
[15] D. M. German, M. D. Penta, Y.-G. Guéhéneuc, and G. Antoniol, “Codesiblings: Technical and legal implications of copying code between
applications,” in Proceedings of the 6th Working Conference on Mining
Software Repositories, 2009, pp. 81–90.
[16] J. Krinke, N. Gold, Y. Jia, and D. Binkley, “Distinguishing copies fromoriginals in software clones,” in Proceedings of the 4th International
Workshop on Software Clones, 2010, pp. 41–48.
[17] ——, “Cloning and copying between GNOME projects,” in Proceedingsof the 7th IEEE Working Conference on Mining Software Repositories,
2010, pp. 98–101.
[18] H. Sajnani, V. Saini, J. Svajlenko, C. K. Roy, and C. V. Lopes,“SourcererCC: Scaling code clone detection to big-code,” in Proceedingsof the IEEE/ACM 38th IEEE International Conference on Software
Engineering, 2016, pp. 1157–1168.
[19] Y. Sasaki, T. Yamamoto, Y. Hayase, and K. Inoue, “Finding ﬁle clones
in FreeBSD Ports Collection,” in Proceedings of the 7th IEEE Working
Conference on Mining Software Repositories, 2010, pp. 102–105.
[20] B. Hummel, E. Juergens, L. Heinemann, and M. Conradt, “Index-based
code clone detection: Incremental, distributed, scalable,” in Proceedingsof the 26th IEEE International Conference on Software Maintenance,
2010, pp. 1–9.
[21] L. Jiang, G. Misherghi, Z. Su, and S. Glondu, “DECKARD: Scalable
and accurate tree-based detection of code clones,” in Proceedings ofthe 29th International Conference on Software Engineering, 2007, pp.
96–105.

[22] H. A. Nguyen, T. T. Nguyen, N. H. Pham, J. M. Al-Kofahi, andT. N. Nguyen, “Accurate and efﬁcient structural characteristic feature
extraction for clone detection,” in Proceedings of the 12th International
Conference on Fundamental Approaches to Software Engineering, 2009,
pp. 440–455.
[23] A. T. Nguyen, H. A. Nguyen, and T. N. Nguyen, “A large-scale study
on repetitiveness, containment, and composability of routines in opensource projects,” in Proceedings of the 13th International Conferenceon Mining Software Repositories, 2016, pp. 362–373.
[24] J. Rubin, K. Czarnecki, and M. Chechik, “Managing cloned variants:
A framework and experience,” in Proceedings of the 17th International
Software Product Line Conference, 2013, pp. 101–110.
[25] V. Bauer and B. Hauptmann, “Assessing Cross-Project Clones for
Reuse Optimization,” in Proceedings of the International Workshop on
Software Clones, 2013, pp. 60–61.
[26] T. Ishihara, K. Hotta, Y. Higo, H. Igaki, and S. Kusumoto, “Inter-projectfunctional 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.
[27] S. Duszynski, J. Knodel, and M. Becker, “Analyzing the source code ofmultiple software variants for reuse potential,” in Proceedings of the 18th
IEEE Working Conference on Reverse Engineering, 2011, pp. 303–307.
[28] Y. Sakaguchi, T. Ishio, T. Kanda, and K. Inoue, “Extracting a uniﬁed
directory tree to compare similar software products,” in Proceedings ofthe 3rd IEEE Working Conference on Software Visualization, 2015, pp.
165–169.
[29] S. Fischer, L. Linsbauer, R. E. Lopez-Herrejon, and A. Egyed, “Enhancing clone-and-own with systematic reuse for developing software
variants,” in Proceedings of the 30th IEEE International Conference on
Software Maintenance and Evolution, 2014, pp. 391–400.
[30] M. W. Godfrey and L. Zou, “Using Origin Analysis to Detect Merging
and Splitting of Source Code Entities,” IEEE Transactions on Software
Engineering, vol. 31, no. 2, pp. 166–181, 2005.
[31] D. Steidl, B. Hummel, and E. Juergens, “Incremental Origin Analysis
of Source Code Files,” in Proceedings of the 11th Working Conferenceon Mining Software Repositories, 2014, pp. 42–51.
[32] M. Sojer and J. Henkel, “License risks from ad hoc reuse of code fromthe internet,” Communications of the ACM, vol. 54, no. 12, pp. 74–81,
2011.
[33] K. Inoue, Y. Sasaki, P. Xia, and Y. Manabe, “Where does this code comefrom and where does it go? – integrated code history tracker for open
source systems –,” in Proceedings of the 34th IEEE/ACM International
Conference on Software Engineering, 2012, pp. 331–341.
[34] T. Kanda, T. Ishio, and K. Inoue, “Extraction of product evolution
tree from source code of product variants,” in Proceedings of the 17th
International Software Product Line Conference, 2013, pp. 141–150.
[35] G. Antoniol, B. Caprile, A. Potrich, and P. Tonella, “Design-code traceability for object-oriented systems,” Annals of Software Engineering,
vol. 9, no. 1-4, pp. 35–58, Jan. 2000.
[36] A. Hemel, K. T. Kalleberg, R. Vermaas, and E. Dolstra, “Finding
software license violations through binary code clone detection,” inProceedings of the 8th Working Conference on Mining Software Repositories, 2011, pp. 63–72.
[37] A. Sæbjørnsen, J. Willcock, T. Panas, D. Quinlan, and Z. Su, “Detectingcode clones in binary executables,” in Proceedings of the 18th ACM
International Symposium on Software Testing and Analysis, 2009, pp.
117–128.
[38] J. Qiu, X. Su, and P. Ma, “Library functions identiﬁcation in binary
code by using graph isomorphism testings,” in Proceedings of the 22ndIEEE International Conference on Software Analysis, Evolution, andReengineering, 2015, pp. 261–270.
[39] J. Davies, D. M. German, M. W. Godfrey, and A. Hindle, “Software
bertillonage: Finding the provenance of an entity,” in Proceedings of
the 8th Working Conference on Mining Software Repositories, 2011, pp.
183–192.
[40] ——, “Software bertillonage: Determining the provenance of softwaredevelopment artifacts,” Empirical Software Engineering, vol. 18, pp.
1195–1237, 2013.
[41] D. M. German and M. D. Penta, “A Method for Open Source License
Compliance of Java Applications,” IEEE Software, vol. 29, no. 3, pp.
58–63, 2012.
[42] I. J. Mojica, B. Adams, M. Nagappan, S. Dienst, T. Berger, and
A. Hassan, “A large-scale empirical study on software reuse in mobile
apps,” IEEE Software, vol. 31, no. 2, pp. 78–86, 2014.

[43] T. Ishio, R. G. Kula, T. Kanda, D. M. German, and K. Inoue, “Software
ingredients: Detection of third-party component reuse in Java software
release,” in Proceedings of the 13th International Conference on Mining
Software Repositories, 2016, pp. 339–350.
[44] L. Luo, J. Ming, D. Wu, P. Liu, and S. Zhu, “Semantics-based
obfuscation-resilient binary code similarity comparison with applications to software plagiarism detection,” in Proceedings of the 22nd
ACM SIGSOFT International Symposium on Foundations of Software
Engineering, 2014, pp. 389–400.
[45] K. Chen, P. Liu, and Y. Zhang, “Achieving Accuracy and Scalability
Simultaneously in Detecting Application Clones on Android Markets,”in Proceedings of the 36th IEEE/ACM International Conference on
Software Engineering, 2014, pp. 175–186.
[46] C. Ragkhitwetsagul, J. Krinke, and D. Clark, “Similarity of sourcecode in the presence of pervasive modiﬁcations,” in Proceedings of the
16th International Working Conference on Source Code Analysis andManipulation, 2016, pp. 117–126.
[47] E. Ukkonen, “Approximate string-matching with q-grams and maximal
matches,” Theoretical Computer Science, vol. 92, no. 1, pp. 191–211,
January 1992.
[48] Debian GNU/Linux, “The snapshot archive,” http://snapshot.debian.org/(Accessed August 19, 2016).
[49] ——, “Machine-usable interface of the snapshot archive,” https://anonscm.debian.org/cgit/mirror/snapshot.debian.org.git/plain/API (Accessed August 19, 2016).
[50] National Vulnerability Database, “CVE-2011-3048,” 2011, https://web.
nvd.nist.gov/view/vuln/detail?vulnId=CVE-2011-3048.