Identifying Source Code Reuse across Repositories
using LCS-based Source Code Similarity
Naohiro Kawamitsu∗ , Takashi Ishio∗ , Tetsuya Kanda∗ , Raula Gaikovina Kula∗ , Coen De Roover∗† , Katsuro Inoue∗∗ Graduate School of Information Science and Technology† Software Languages Lab

Osaka University
1–5 Yamadaoka, Suita, Osaka 565–0871, Japan
Email: {n-kawamt, ishio, t-kanda, raula-k, coen, inoue}@ist.osaka-u.ac.jp

Vrije Universiteit Brussel
Pleinlaan 2, 1050 Brussels, Belgium
Email: cderoove@vub.ac.be

Abstract—Developers often reuse source files developed foranother project. In order to update a reused file to a newer
version released by the original project, developers have to track
which revision of a file was reused and how its content was
modified. However, such tracking is tedious for developers. Many
projects keep older versions of files whose bugs are already fixedin the original project. In this paper, we propose a technique toautomatically identify source code reuse relationships between
two repositories. Using a similarity metric based on longest
common subsequence, we identify pairs of similar revisions offiles across the repositories. To evaluate our approach, we haveanalyzed eight project pairs of open source software projects
and compared the result with the recorded information in therepositories. As a result, we have identified 1394 file revisions as
instances of source code reuse. While 75.3% of the instances
are recorded in the repositories, 20.1% of the instances are
unrecorded but recovered by our approach.

I.

I NTRODUCTION

Clone-and-own is one of the popular approaches to sourcecode reuse [1][2]. Developers copy source files developedby another project into their own. Reusing existing libraries
reduces cost and enables quick software development. Thiseven happens for libraries which are intended to be shared
between projects. Rather than linking against a compiled
version of the library, developers sometimes copy its sourcecode into the project’s. For instance, when a project-specificenhancement is required.
Developers should keep track of the library version they
copied from. This facilitates keeping copies up-to-date. For
instance, to patch newly discovered security vulnerabilities.
Nevertheless, 18.7% of the projects studied in [3] had norecords of the actual versions of the third-party code that they
are reusing. A simple diff is often insufficient to identify
the origin of a copy, because it cannot distinguish projectspecific changes from updates to the original project. Indeed,
many copies are modified for project-specific enhancements.
The practice of clone-and-own reuse therefore requires tool
support for identifying the original version of the copy.
In general, there are two approaches to the problem.
Forward engineering approaches aim to provide tool support
for a more systematic clone-and-own reuse. Jablonski et al.,for instance, proposed an extension of the Eclipse IDE that
automatically records copy-and-paste activities [4]. Reverse
engineering approaches, in contrast, aim to identify instances

Sourcerepository

Versions of origin file

File 𝑓𝑓

𝑅𝑅𝑠𝑠

Origin

𝑓𝑓1

𝑓𝑓2

𝑓𝑓3

Destination
repository

𝑅𝑅𝑑𝑑
Fig. 1.

similarFile 𝑓𝑓𝑓

Copy

𝑓𝑓𝑓1

𝑓𝑓𝑓2

𝑓𝑓𝑓3

time

Separate evolutions of a copy and the origin file.

of reused code in given code bases. Our approach is one ofthese.
We propose a file-level analysis technique for detecting
copies and the origin files they are copied from across project
repositories. For each revision of a source file in a project, we
determine the file revision it originated from in another project—while accounting for project-specific changes to the copy.
Figure 1 depicts separate evolutions of a copy and theorigin file it is copied from. The file f in the source repository
Rs is copied into the destination repository Rd as file f 0 . A
version f1 of f is updated in the source repository to f2 ,which is copied to the destination repository as f20 . Next, thedestination repository adds a new feature to f20 resulting in
a new revision f30 . As f30 is newer than f3 , it might seem
up-to-date upon a casual inspection. In reality, however, it
contains outdated source code that still stems from f2 . This
example illustrates that commit timestamps do not suffice fordetermining which revision in a source repository is copied.
Our approach therefore detects instances of clone-and-own
reuse based on the similarity between a copy and a candidate
origin file revision instead. More concretely, we use Longest
Common Subsequence (LCS) [5] as a similarity metric. LCS iscommon in clone detection [6] and product evolution analyses[7]. We implemented our approach as a tool. Given a source
repository and a destination repository, our tool identifies pairsof similar versions of files across the repositories. For eachcopy in a destination repository, our tool reports project version
numbers of the original file revision in a source repository.

To evaluate our approach, we applied our tool to eight
open source software projects of which six are known to havereused libpng and two are known to have reused libcurl. The
tool reported 1394 file revisions in a destination project andtheir origin file versions in a source project. We manually
verified the reported revisions using the directory structureof the source and destination projects, the commit log of thedestination project, and the contents of the copy and the origin
file. As a result, 1004 file revisions are correctly recorded in
the destination projects. 46 of the reported origin file revisions
revealed potential problems that developers recorded different
version numbers from actual origin file revisions. Furthermore,
201 of the reported instances are not recorded in the destination
projects, even though the instances have the same contents
except for white space and code comments. Note that the
instances of source code reuse are included in 73 commits
in the repositories. Because 23 (31.5%) of them do not record
version numbers, our automatic analysis is important to recoversource code reuse information across repositories.
The contributions of the paper are summarized as follows.
•

An automated analysis method is proposed to detect instances of source code reuse between software
repositories.

•

The approach is evaluated using the source code reuse
information recorded in publicly available software
repositories.

•

Actual instances of source code reuse in eight projects
are analyzed.

Section II shows motivating examples of our approach.
The approach itself is detailed in Section III. Section IV
presents the evaluation of our approach using a prototype
implementation and the aforementioned open source projects.
Before concluding in Section VI, we describe related work in
Section V.
II.

M OTIVATING E XAMPLES

When reusing source files from another project, developers
may modify these files for their own purpose. An example
is found in the V8Monkey project. The project includes afile pngget.c which stems from the libpng project. The
V8Monkey project modified this file to support PNG animations. When the libpng project released a new versionof pngget.c, the V8Monkey project merged these changes
with theirs. Another example is found in the source code of
Wolfenstein: Enemy Territory. The project includes variantsof libcurl files that have been modified to satisfy the project’s
own code formatting conventions.
To maintain all of these copies, knowing the project a fileoriginates from does not suffice. Developers require knowledge
about the concrete revision each copy was copied from.
Otherwise, it is not clear what revision to update each copy
to, since two or more releases of a library may be available atthe same time. For example, Cocos2D-iPhone project tried to
update their libpng files from 1.2.38 to 1.4.1, but downgradedto 1.2.43 because of source incompatibility. This traceability
information is recorded in several manners in practice. Commit
messages in the repository of V8Monkey indicate project
version numbers of libpng files. For example, the message ofcommit ID 9def47a86c95fd5f1 says “updated libpng to
1.4.3.” In the source code of Wolfenstein, on the other hand,the name of directory curl-7.12.2 hints at the included
version of libcurl.
However, traceability information recorded in this manner is not always available. Xia et al. [3] reported
18.7% of projects had no version information of thethird-party code. Even if traceability information has beenrecorded when files are copied, the history may not bedirectly visible to developers. For example, the commit
3a6c8755c4b08c2c in V8Monkey project records “Movelibpng to media/libpng.” Hence, an older version must
be analyzed to identify what version of libpng are used in
the project. In addition, incorrect traceability information may
be recorded in the repository. For example, the git repository of the Haiku-services-branch project includes a commit
cc57c65424afbcb7 of which the message states “updated
libpng to 1.2.31.” The commit updated three files. While twoof them are exactly the same as files involved in libpng
1.2.31, one file named png.h is the same as png.h in
libpng 1.2.30 except for additional code comments. While
this case does not cause a serious problem, a newer version
number incorrectly recorded may prevent developers fromupdating their vulnerable copy. To avoid manual error-prone
recording of traceability information, an automated technique
for tracking source code reuse between repositories is required.
Two clues for recovering traceability of source code reuse
are the time the copy is made and the content of the copy. A
simple heuristic is that developers copied the latest version at
the time. However, developers sometimes intentionally copy anolder version. For example, fs2open project started to use files
copied from libpng 1.2.42, although the latest version 1.4.0
has been also available.
Another clue is the content of a copy. Since developers
may modify the copy, developers have to compare a copy
with candidates of the original version. Identifiers play animportant role in this comparison, because most of bug fixes
are implemented in a small number of lines of code [8]. For
example, commit f2e2833f28fa11ba of libpng patched a
bug using the following string replacement:- png_ptr->transformations |= PNG_STRIP_ALPHA;+ png_ptr->flags |= PNG_FLAG_STRIP_ALPHA;

Small differences are therefore often vital to identifying
which revision a copy stems from. Unfortunately, these areexactly the differences code clone detection tools are intentionally oblivious to [9].
It should be noted that code comment in a copy may indicate a different version from its actual version. For example,
the header comment of png.c in libpng 1.2.31 says that thefile is 1.2.30. The header comment of pngmem.c in libpng
1.0.38 also says that the file is 1.2.30. A correct version numberof a copy must be verified by the content of the copy.
III.

O UR A PPROACH

Our approach determines which source code from a source
repository S (e.g., a library project) is reused into a destination
1 In this paper, a commit ID for a git repository is represented by its first
16 characters that uniquely specify the commit.

r1

r2

r3

f1

s1

s2

r4

0.6

r5

0.8

0.9
0.5

0.7

f2
r7

r8

r6

0.8

d
d1

f3
Fig. 2.

s3

sd2

An example repository including three files f1 , f2 , and f3 .

time
Fig. 3.

repository D (e.g., an application project). An instance ofsource code reuse is a link between a file revision (a version
of a file) in S and a file revision in D. The approach is basedon the following assumptions about source code reuse:

An example of a file pair (s, d).

•Developers copy a file from a release version of alibrary.

and also versions weakly connected to them. For example,
in Figure 2, Rk (f1 ) = {r1 , r2 , r3 }, Rk (f2 ) = {r4 , r5 , r6 },Rk (f3 ) = {r4 , r5 , r6 , r7 , r8 }. Although Rk (f ) may include afile revision whose name is not f , we denote the file revisions
in Rk (f ) as fi for simplicity.

•

Version numbers are available as tags in a source
repository.

A. File Pair Extraction•

Developers do not modify the content of a copy
significantly.

•

An origin file exists in a source repository before a
copy appears in a destination repository.

Based on these assumptions, instances of source code reusecan be detected using the following step-wise approach:
1)
2)
3)

Identify file pairs (s, d) such that a revision of s in
S is similar to a revision of d in D.
Exclude file pairs (s, d) for which d is older than s.
Identify the most similar revision i of s for eachrevision j of d. Output project version numbers
corresponding to si as the origin of dj .

The resulting set includes all instances of source code reuse
between the repositories. It enables developers of a destination
project to know which file revisions have been derived fromthe source project and should be updated. It also enables
developers of a source project to understand how their files areused and extended in the destination project and to improvefunctionalities in origin files.
We regard a repository as a directed graph of which thevertices represent revisions of files, and of which the edges
represent successors of revisions. Figure 2 shows an example
of a repository including three files f1 , f2 , and f3 . In the figure,a circle represents a file revision. In the repository, r1 is thefirst revision of file f1 . r2 and r3 are modified revisions of r1 .
The file f2 is modified once and renamed to f3 . The edge r4
to r5 represents the modification, the edge r5 to r6 represents
the rename, respectively. The lack of an edge from revision r8
to r6 indicates that file revision r8 has been deleted and thenreplaced by r6 .
Rk (f ) refers to all file revisions related to file f in
the repository k. To include renamed files in the analysis,
Rk (f ) includes versions in which the file is named to f

A file d is likely a reuse of a file s if a similarity between arevision of s and a revision of d is above certain predeterminedthreshold. We extract a set of file pairs C that are likely
instances of source code reuse as follows.
C = {(s, d) | ∃si ∈ RS (s) ∃dj ∈ RD (d) : sim(si , dj ) ≥ th}sim(si , dj ) is a similarity metric between revisions. For sim,
our technique employs a metric that stems from productevolution analysis [7]. This token-based metric is computed
as follows:sim(si , dj )=|LCS(si , dj )||si | + |dj | − |LCS(si , dj )|where |si | and |dj | are the numbers of tokens in the filerevisions, |LCS(si , dj )| is the length of the LCS of tokens
in the file revisions. In this comparison, each file revision isnormalized to a sequence of tokens excluding code comments
and white space. All other tokens including keywords, macros,and identifiers are kept as is. A threshold th is a configurable parameter of the metric, but we have arbitrarily chosen
th = 0.8 for our implementation.
This step compares all the file revision pairs between therepositories. To avoid unnecessary computation of LCS for apair of less similar files, we have employed an optimization. In
short, we compare term-frequency vectors of two file revisions
to estimate the similarity. If two file revisions have only asmall number of common tokens, we do not need to computethe LCS for the revisions, as they cannot have a long common
subsequence. By normalizing identifiers in source code, eachfile is translated into a fixed-length vector representing thefrequencies of each lexical element such as keywords andoperators in a programming language. In addition to the
optimization, we have employed a LCS algorithm suitable forsimilar strings [10] in order to efficiently compare many similar
file revisions.

s1

s2

s3

s

s1

s2

s3

s
0.9

0.9

0.8
0.8

0.7

d

d
d2

d1

time
Fig. 4.

An example of files that have similar revisions.

Figure 3 shows an example of a pair of a file s in asource repository and a file d in a destination repository. In
the figure, the file s has three revisions s1 , s2 , and s3 , the filed has two revisions d1 and d2 . The directed edges between
revisions indicate the successor relationship between revisions.
The revisions are placed left to right according to their commit
time. Cross-repository links between a revision of s and arevision of d carry the similarity between the file revisions.
For example, sim(s1 , d1 ) = 0.7, sim(s1 , d2 ) = 0.8, and soon. Note that these links are undirected. We regard the file pair(s, d) as a candidate instance of source code reuse, because
there are several links whose similarity values are equal to or
greater than our 0.8 threshold.
B. Filtering by Commit Time
Having computed the set C of pairs (s, d) of files whose
revisions are similar to each other, we filter out file pairs in C
that are less likely reuse instances using a heuristic involving
commit times. If a file d in D has been created by reusing s,
the oldest revision of s that is similar to a revision of d shouldhave been committed earlier than the revision of d.

time
Fig. 5. An example of the result of the final step. Each file revision in thedestination repository is linked to its most similar file revision in the source
repository. Two revision pairs (s1 , d1 ) and (s2 , d2 ) are the output of ourapproach for this file pair.

removing the revisions which have no links. In the figure, theoldest revisions of file s and d are s1 and d2 , respectively.
According to their commit time, s1 is older than the oldest
revision d2 , i.e., t(s1 ) < t(d2 ). Hence, the pair (s, d) is kept
for the next step.
C. Identify Revision Pairs
We identify similar file revision pairs in the history of filepair (s, d) in Cf iltered and translate the source file revisions
into version numbers of the source project. For each revision
dj ∈ RD (d), we identify the most similar revisions si in RS (s)as the original revision corresponding to dj using the following
criteria. While these criteria rely on the same similarity metricas before, they incorporate additional criteria for tie-breaking:1)
2)

To compare the commit time, we identify the oldest similar
file revisions of s and d. We select file revisions in both
repositories that are similar to each other. Formally, we selectthe following revisions.
TS (s) = {si ∈ RS (s) | ∃dj ∈ RD (d) : sim(si , dj ) ≥ th}
TD (d) = {dj ∈ RD (d) | ∃si ∈ RS (s) : sim(si , dj ) ≥ th}3)
We compare the oldest revisions of s and d in the sets. If theoldest revision of d is older than the oldest revision of s, thefile pair (s, d) is removed from C. The filtered file pair set
Cf iltered is obtained as follows.
Cf iltered = {(s, d) ∈ C |∃si ∈ TS (s) ∀dj ∈ TD (d) : t(si ) ≤ t(dj ) }where t(r) is the commit time of a file revision r.
The selected revisions have at least one similar revisionin the peer repository. In the case of the pair (s, d) shownin Figure 3, TS (s) = {s1 , s2 , s3 }, TD (d) = {d2 }. Figure 4
shows the selected revisions. This figure can be obtained byremoving links whose similarity is less than the threshold, andd2

Select source revisions that are the most similar to
dj .
If two or more source revisions have the same similarity to dj , select revisions that are most similar
to dj using a text-based similarity metric that is avariant of sim using lines instead of tokens. It takes
into account code comments and white space, while
it ignores line separators. This rule focuses on filerevisions in a source repository whose difference isonly code comments, e.g. version numbers in theirheaders. We still ignore line separators because two
projects may use different line separators.
If two or more source revisions still have the same
similarity to dj , select the oldest one.

This step generates a set of reuse instances (si , dj ) between
two repositories. Finally, we translate si into version numbers
Vi by extracting tags associated with si . Since multiple filerevisions have the same content in several branches, we list up
all file revisions having the same content as si and their tags
as version numbers corresponding to si . We output (Vi , dj )representing that dj is likely a copy of the original file revisionin versions Vi . If tags are unavailable, we output the commit
ID of si as an original file revision of dj . An example is shownin Figure 5, which is computed for the file pair from Figure 3
and Figure 4. Two links {(s1 , d1 ), (s2 , d2 )} are produced by
the step. If version numbers v1 and v2 are available for s1 ands2 , the final output is {({v1 }, d1 ), ({v2 }, d2 )}.

D. Implementation
We have implemented our approach as a tool for C programs under version management by Git. The tool takes as
input a pair of Git repositories and compares .c and .h files
in the repositories.
The similarity metric is not defined for a file without sourcecode such as an empty file. Hence, the tool excludes such files
from analysis.
The output of the tool are pairs of a destination file revisionand the source file revision from which it was copied. A filerevision is identified by a file path and a commit ID in a
repository. The tool also outputs similarity values between
revisions to facilitate subsequent analyses. A similarity valueless than 1 indicates a destination file revision modified fromthe original so that developers can compare the contents of
the revision pair. Below we list an extract of the results for asource repository libpng and a destination repository fs2open:
Source
Path
png.c
png.c
png.c
png.h
png.h
png.h
pngrio.c

Tags
v1.2.42v1.5.2v1.5.7v1.2.42v1.5.2v1.5.7v1.0.52,v1.2.42

DestinationPathlibpng/png.c
libpng/png.c
libpng/png.c
libpng/png.h
libpng/png.h
libpng/png.h
libpng/pngrio.cCommit101018d
623b6ad
58f9e77
101018d
623b6ad
58f9e77
101018d

sim
1
1
1
1
1
1
1

Due to the limited space, the commit IDs in the list
are shortened. The first line indicates that png.c tagged
as version 1.2.42 in the libpng repository is similar tolibpng/png.c in the commit 101018d in the fs2open
repository. The full result indicates that developers of the
fs2open project copied files in libpng to their repository threetimes. Because the similarity values are always 1.0, it is likelythat the copies remained unmodified afterwards (though code
comments could have been modified). In the repository of
fs2open, the three commits record the version numbers oflibpng in the messages: 1.2.42, 1.5.2, and 1.5.7. We can verify
the correctness of the recorded version numbers from theoutput of the tool. Note that the tool outputs a number oftags for a destination file revision, if the same file content has
been included in several releases. For example, the tool reportsthat libpng/pngrio.c in the commit 101018d is a copyof pngrio.c in the versions 1.0.52, 1.2.42, and several otherversions (omitted in the above list).
IV.

E VALUATION

To evaluate the effectiveness of our approach, we haveapplied our tool to 10 of the projects in Xia’s work [11]which identified projects of which files are potentially copied
between projects. Two projects libpng and libcurl are selected
as source repositories of reused code. Six projects using libpng
and two projects using libcurl are selected as destination
repositories. Table I shows the project names, URLs, and thesummary of the repository attributes. We have assigned IDs
for referring to the destination repositories in this section. The
columns “Duration,” “Latest commit ID,” and “#Commits”
show the analyzed history of the repositories. The column“LOC” indicates the number of lines of code of .c and .h in
the latest version. Although several destination projects include.cpp files, we have analyzed only C files because the source
repositories use .c files for their implementation.
We have evaluated precision of the output of our toolby comparing with instances of source code reuse that arerecorded by developers. As the ground truth, we identify
project version numbers of origin files as follows.
•In destination repositories 1-6, we identify a version
number from the commit message recorded when the
copy has been committed. For example, the version
number of a destination file revision committed witha message “Updated to libpng 1.2.31” is 1.2.31.

•

In destination repository 7, all files are located ina curl-7.12.2 directory. Hence, we assume thata destination revision committed in the directory is
copied from version 7.12.2.

•

In destination repository 8, all files are located in acurl directory. We identify a version number in afile named CHANGES in the curl directory that iscommitted with other source files at the same time.

Since it is hard to analyze the whole repository, we haveanalyzed only commits and directories including an instanceof source code reuse reported by our tool.
A. Research Method
An instance of source code reuse reported by our tool
is correct if the same information is recorded in the destination repository, i.e. the reuse instance is consistent withthe recorded information. We classified instances of sourcecode reuse reported by our tool into four groups: consistent,
inconsistent, unrecorded, and redundant.
•

A reported instance is consistent with the recorded
information if the reported destination file revision has
been recorded as a copy of version v, and the reported
version numbers include the version v.

•

A reported instance is inconsistent with the recorded
information if the reported version numbers have notincluded the version recorded by developers.

•

A reported instance is unrecorded if no version number is identified for the reported destination file revision.

•

A reported instance is redundant if another reportlinks the destination file revision to another source
file version that is more appropriate. For example, if
two similar files A and B are copied to a destination
repository as A’ and B’, our tool reports four pairs (A,A’), (B, B’), (A, B’), and (B, A’). In this case, (A, B’)and (B, A’) are regarded as redundant pairs.

The classification process compares the output of the toolwith the ground truth. When a destination file revision is similar to revisions of two or more files in a source repository, we
manually check source file revisions in the reported versions
to identify redundant instances. We select the most similar filerevision based on their file paths and a visual inspection as theoriginal revision.

TABLE I.
#ID

1
2
3
4
5
6
7
8

Project namelibpnglibcurlcocos2d-iphone
apitrace
guliverkli2
fs2openv8monkey
Haiku-services-branch
Enemy-Territory
doom3.gpl

Repository URL
git://libpng.git.sourceforge.net/gitroot/libpng/libpng
https://github.com/bagder/curl
https://github.com/hansoninteractive/cocos2d-iphone.git
https://github.com/apitrace/apitrace
https://github.com/athomasm/guliverkli2.git
https://github.com/sobczyk/fs2open.git
https://github.com/zpao/v8monkey.git
git://github.com/Barrett17/Haiku-services-branch.git
https://github.com/id-Software/Enemy-Territory.git
https://github.com/TTimo/doom3.gpl.git

TABLE II.
#ID
1
2
3
4
5
6
7
8

TABLE III.
#ID
1
2
3
4
5
6
7
8
Total

Sourcelibpnglibpnglibpnglibpnglibpnglibpnglibcurl
libcurl

A NALYZED P ROJECTS

Destination
cocos2d-iphone
apitrace
guliverkli2
fs2openv8monkey
Haiku-services-branch
Enemy-Territory
doom3.gpl
Total

Not Modified
127
39
68
57
63
218
54
156
782

Latest commit ID
0e60f06b7c14e698
72f850571d24ae48
b47eab8e90f6ba3f
a2ad18752c5692a0
5e6d5d4caa2cf74d
156565c8e94b1f58
0280cf71d2c36e0e
85e3cb0c85752c45
40342a9e3690cb5b
8047099afdfc5c97#Commits
3517
16891
3754
2694
107
8423
87435
44842
1
39

LOC
76419
15251583111
113472420486
19753227099195205544553309252618T HE A NALYSIS R ESULT

Reported
147
78
131
57
275
306
210
190
1394

T HE RESULT OF CONTENT COMPARISON OF CONSISTENTREUSE INSTANCES .
Destination
cocos2d-iphone
apitrace
guliverkli2
fs2openv8monkey
Haiku-services-branch
Enemy-Territory
doom3.gpl

Duration
Jul 1995 - Nov 2013
Dec 1999 - Oct 2013
Jun 2008 - Jul 2010
Jul 2008 - Oct 2013
Sep 2007 - Feb 2010
Jun 2002 - Jul 2013
Mar 2007 - Feb 2012
Jul 2002 - Feb 2013
Jan 2012
Nov 2011 - Apr 2012

Modified
0
0
3
0
120
0
96
3
222

B. Results
We have applied our tool to eight project pairs. Table II shows the result of the classification. The column“Reported” shows the number of reuse instances extracted
by our approach. The columns “Consistent,” “Inconsistent,”“Unrecorded,” and “Redundant,” show the classified result. Our
tool reported 1394 pairs as instances of source code reuse.
1) Consistent Instances: 1004 instances (72.0%) of thereported 1394 instances are consistent with the recorded
information. To analyze how often developers modified filerevisions after copying, we have compared the contents ofsource file revisions and destination revisions. In Table III,the consistent instances are classified into two groups: Not
Modified and Modified. A reuse instance is classified as Not
Modified if the similarity metric value of the pair is 1.0. In
other words, the differences are limited to code comments
and white space. Otherwise, a reuse instance is classified as
Modified. Our results indicate that projects #5 (V8Monkey)
and #7 (Wolfenstein: Enemy Territory) often modify the sourcecode after copying from the source repositories. As describedin Section 2, V8Monkey modified copied revisions to handle
Animation PNG. Wolfenstein also modified various functionsin the files. Except for these projects, developers tend to reuse
source code as is.
2) Inconsistent Instances: 46 instances (3.3%) are inconsistent with the recorded information. While this group may
include reuse instances incorrectly reported by the tool, it also

Consistent127(86.4%)
39(50.0%)
71(54.2%)
57(100.0%)183(66.5%)
218(71.2%)
150(71.4%)
159(83.7%)
1004(72.0%)TABLE IV.

#ID
1
2
3
4
5
6
7
8
Total

Inconsistent0(0.0%)
0(0.0%)
0(0.0%)
0(0.0%)
18(6.5%)
1(0.3%)
26(12.4%)
1(0.5%)
46(3.3%)

Unrecorded
20(13.6%)
39(50.0%)
60(45.8%)
0(0.0%)
74(26.9%)
87(28.4%)
0(0.0%)
0(0.0%)
280(20.1%)

Redundant
0(0.0%)
0(0.0%)
0(0.0%)
0(0.0%)
0(0.0%)
0(0.0%)
34(16.2%)
30(15.8%)
64(4.6%)

T HE RESULT OF CONTENT COMPARISON OF UNRECORDED
REUSE INSTANCES .
Reuse w/o Version Number
Not Modified
Modified
0
0
39
0
0
0
0
0
14
38
21
0
0
0
0
0
74
38

OthersNot Modified
Modified
20
0
0
0
56
4
0
0
9
13
42
24
0
0
0
0
127
41

includes reuse instances incorrectly recorded by developers. By
analyzing the instances, we have identified potential problems
in the destination repositories. The first example is found inproject #5. A commit message says that files are updated tolibpng 1.2.31, whereas some of the committed file revisions areincluded in either 1.0.38 or 1.2.30. Those files are regarded as
1.2.31 partly because the files in the versions have the samecontents except for code comments. The second example ispng.h in the project #6 that is described in Section 2. The
content of the file is the same as 1.2.30 but recorded as 1.2.31.
3) Unrecorded Instances: 280 instances (20.1%) are unrecorded because of the lack of version numbers in commit
messages. 112 of them are recorded as source code reuse in thecommit message, although there are no version numbers. The
remaining 168 instances have no explicit information aboutsource code reuse. We have compared the contents of source
revisions and destination revisions and classified the instances
to two categories: Not Modified and Modified. A reported
reuse instance is Not Modified if the similarity of the source
revision and the destination revision is 1.0. Otherwise, a reuse
instance is Modified. The result is shown in Table IV. The
columns “Reuse w/o Version Number” show the number ofreuse instances whose commit message mentioned source code
reuse. The columns “Others” show the number of other reuse
instances. 201 “Not Modified” instances are likely represent
instances of source code reuse, since the file revisions have thesame contents between repositories. Although some instances
may point to different source versions from actual versions,we expect that most of them are likely correct as the numberof consistent instances are 22 times greater than the numberof inconsistent instances.
Developers did not record version numbers for these instances partly because the developers focused on source code
management issues rather than source code reuse. For example,
project #1 updated libpng copies with a message “v0.99.1 release tag.” The project #3 has a similar commit updating libpng
files with a message “Guliverkli revision 611.” In addition,
developers did not record version numbers when they did notchange the contents of revisions. For example, project #2 and#5 moved libpng copies in their repositories. They recorded
only what they did, e.g. “Move libpng to media/libpng,”
without version numbers. The version numbers of those files
recovered by our tool would help developers to understandwhat files are included in the repositories.
4) Redundant Instances: We have identified 64 redundant
reuse instances in projects #7 and #8. One cause is the lack ofhistory of file moving and renaming in the libcurl repository.
For example, a file getpass.c is located in lib directoryin libcurl 7.10.6 and located in src directory in libcurl 7.11.2.
Our tool could not identify the revision in src as a successor
version of the file in the lib directory. Hence, our tool
reported two instances of source code reuse for a single versionof the file getpass.c in the project #7. In the analysis, we
manually identified the correct version, because the project #7
stores the file revision in libcurl-7.12.2/src directory.
In addition, the file content is the same as src/getpass.cin 7.11.2.
Redundant instances are also reported when two or moresimilar files are included in a source repository. For example,
lib500.c and lib501.c in libcurl 7.12.2 defined test
functions whose contents are almost the same except for twolines. Since the files are not linked in a repository, our tool
reported two redundant reuse instances: lib500.c is reusedas lib501.c, and vice versa. As similar to the first case, wehave manually identified correct reuse instances by file paths.
C. Precision
We calculate precision of our tool by comparing thereported instances with the recorded information as follows.
c
P =
c+i+r
where c is the number of consistent reuse instances (1004),
i is the number of inconsistent reuse instances (46), and r
is the number of redundant reuse instances (64). The resulting
value is P = 0.901. The number of unrecorded reuse instances
is excluded from this calculation because we cannot verify
whether they are actual source code reuse or not.
We have assumed that similar source files are source code
reuse, but the assumption is not always true. One example
is md4.c in the project #7. While all the analyzed projects
put their library copies in directories having special names,
e.g. external/libpng/ and thirdparty/libpng, itis the only one case reported for a file revision outside of sucha directory. Hence, the file is likely a third party code usedby the project #7 and libcurl. Another case is a file named
lib/getdate.c in the project #8. The file is generated by

TABLE V.

T HE NUMBER OF UNREPORTED FILE REVISIONS INCLUDEDIN DIRECTORIES THAT CONTAIN COPIES FROM LIBRARIES
#ID
1
2
3
4
5
6
7
8
Total

#Revisions
5
3
0
2
19
9
6
3
47

Source
5
0
0
0
1
9
6
3
24

No Source
0
3
0
2
18
0
0
0
23

a code generator during the build process of libcurl. Since
the file is involved in both source and destination repositories,
our tool reported the file as an instance of reuse even if
developers did not directly copy the file. We think these arefalse positives of our approach. However, we could not verify
the latter case in the experiment. In the case, two file revisions
are involved in both repositories and marked as reuse by
developers. There are no differences from other consistent
instances. We accidentally identified the case simply because
the source repository included a commit message telling thefile is generated one and removed in the future release. We
could not count the number of this kind of false positives
because of our limited effort.
D. Recall
Although we cannot know the number of files actuallyreused, developers tend to put copies of a library in the same
directory. Indeed, only 12 directories and their subdirectories
are used for the 8 projects. We have analyzed all the filerevisions in the directories, because they are also likely copies
from the library. Table V shows the result. The column“#Revisions” shows the number of file revisions that are notreported by our tool. The file revisions are classified into
“Source” and “No Source” according to whether the same filename is found in a source repository or not.
The file names of 24 file revisions are found in source
repositories. 12 of 24 revisions include only comments insteadof source code. Our tool simply removed such files from theanalysis. One example is pnggvrd.c found in the project#1. The file includes only a single comment as follows.
/* pnggvrd.c was removed
from libpng-1.2.20. */Other file revisions are modified from the original version andsimilarity metric values for them are less than the threshold.
For example, the similarity between a copy of pngconf.h in
the project #6 and its most similar revision in libpng is 0.77.
14 of those 24 revisions are recorded as reuse in their commits.
Hence, they are likely false negatives accidentally missed byour tool.
23 file revisions are not found in source repositories. The
file revisions are associated with two files: pnglibconf.hand mozpngconf.h. The former file is created by a scriptin libpng project, although the project #4 recorded the revisions as source code reuse from libpng. The latter file iscreated by Mozilla project to replace function names for reuseTABLE VI.

T HE NUMBER OF COMMITS INCLUDING INSTANCES OF
SOURCE CODE REUSE

#ID
1
2
3
4
5
6
7
8
Total

#Total
8
4
8
3
25
23
1
1
73

#Consistent
7
2
4
3
10
17
0
0
43

#Inconsistent
0
0
0
0
4
1
1
1
7

#Unrecorded
1
2
4
0
11
5
0
0
23

TABLE VII.
#ID
1
2
3
4
5
6
7
8

T HE EXECUTION TIME

Execution Time
40min51sec
55min6sec
38min13sec
23min43sec
225min33sec
139min45sec
5min26sec
4min35sec#LCS Computed
87,28076,066
77,52528,378
307,910
175,588
10,691
10,162Ratio

F. Performance
0.35
0.30
0.25
0.20
0.15
0.10
0.05
0.00

Fig. 6.
The ratio of inconsistent instances against the number of reuse
instances in a commit

in the project. For example, a macro replaces a function
png_read_data in libpng with MOZ_PNG_read_data.
We do not regard these file revisions as false negatives because
they are not copied from source repositories.
By assuming there are no potential copies in other directories, recall of our tool can be estimated as follows:c
Restimated =c+i+nwhere c is the number of consistent pairs (1004), i is thenumber of inconsistent pairs (46), and n is the number offalse negatives we identified (14). The resultant value is
Restimated = 0.943.
E. Commit-level Analysis
Since developers may copy a number of files at oncefrom a source repository, we have analyzed the number ofcommits including reuse instances for each project. Table VI
shows the result. The column “#Total” indicates the number ofcommits that include at least one reuse instance. The column“#Consistent” indicates the number of commits with correct
version numbers. The column “#Inconsistent” indicates thenumber of commits including at least one inconsistent reuse
instance. The column “#Unrecorded” indicates the numberof commits without version numbers. The result shows that
an automatic analysis is important for developers, since 23(31.5%) of 73 commits do not include version numbers.
Inconsistent reuse instances are always committed withseveral consistent reuse instances. Figure 6 shows the ratio ofinconsistent instances against the number of reuse instances
in a commit. For example, if a commit updated three files
obtained from a library but one of them was copied fromanother version of the library, the ratio is 0.33. The resultshows that 7 (9.6%) of 73 commits include 18.1% of files
from different versions of a library accidentally. In such a case,our tool reports different version numbers for each file in acommit. Consequently, developers can recognize such potential
problems using our tool.

Our tool compares all file revision pairs between repositories in the worst case, while we have employed an optimization. Table VII shows the time taken to execute theanalysis using a single thread on Intel(R) Xeon(R) CPU E51603 2.80GHz. The time does not include the time to copy Git
repositories to a local storage. We have two large repositories
in the analysis. Repository #5 involves 87,435 commits. The
total amount of code we have analyzed is 62.9 MLOC. Repository #6 involves 44,842 commits. The total amount of code
we have analyzed is 37.8 MLOC. Our tool finished analysis
for those large products in several hours. The time depends
on the number of similar file pairs between repositories that
require computing the longest common subsequence between
file revisions. Table VII indicates the number of computed
longest common subsequences. The numbers are much smaller
than the number of possible revision pairs between repositories
because of our optimization. In addition, the computed results
can be reused for an incremental analysis, since similarity
values between existing file revisions do not change in the
future.

G. Threats to Validity
The precision of our approach is computed against the
information recorded in the repositories. If developers of theanalyzed projects often copied file revisions without recording
this and subsequently modified most copies significantly, suchmodified files are not taken into account. As described in
Section IV-E, several false positives may be regarded as true
positives in our analysis. On the other hand, inconsistentreuse instances are regarded as false positives. Some of them
could not be identified because of incorrectly recorded version
numbers.
We have used a single threshold value th = 0.8 in our
implementation. While another threshold value may change thedetection result, we believe that the value is not so significant
because most of the consistent reuse instances are file copies
without modification. Indeed, our manual analysis of directories identified only 14 false negatives that are accidentallyfiltered out.
We have selected two library projects for source repositories: libpng for manipulating image files and libcurl fortransferring data using various protocols. Both of them are
utilities to implement features of applications. The source code
reuse activities of developers in eight projects may be limited
to a particular style for using such a utility library.

V.

R ELATED W ORK

A. Software Product Lines
Software Product Line Engineering involves much forking
and copying of files across variants of a software product.
Tracing similarities between variants has its benefits for selection of the most appropriate variant. Duszynski [12] proposed
Variant Analysis to compare source code of product variants
to understand product-specific features and common (reused)features.
Hemel [13] showed that the tracing of the evolution also
has reverse and forward engineering benefits. Nonaka [14]visualized the relationships of variants and analyzed corrective
maintenance data for a particular product family. Yamamoto[15] defined similarity between source code of software products. Kanda [7] defined similarity between software products
using a file-level similarity metric to identify the origin of
the variants with their evolution. We have employed the filesimilarity metric to compare file revisions. Kanda [7] also introduced an optimization using term frequency vectors to avoid
unnecessary comparison of files. We normalize identifiers tocompute fixed-length term frequency vector for source code.
Software Product Line targets reuse between variants ofthe same products or from projects originating from the samefamily. Ray [16] analyzed how forked projects import sourcecode changes from other projects. While the analysis compare
patches between projects, our analysis compares file revisions
between projects. One reason is that files copied from a library
are updated less frequently.
B. Code Clones and Origin Analysis
Similar fragments of code are considered to be code clones.
The longest common subsequence has also been implemented
for ’suffix’ based clone detection tools. Recently, clone detection work efforts have concentrated around the improvement of
the state of the art through scalability, speed and precision [17],[18].
Other studies have done cross-project clone detection,
however with different intentions. Bauer [19] investigated theextraction of similar pairs of files between projects to createa library. Our approach extracts source files copied from alibrary. Kim [20] coined clone genealogy to help understandclone management and refactoring. Our analysis might enablea genealogy analysis between projects, since the output of ourtool links the history of files in a library and their copies in an
application. Krinke [21] proposed to use version informationin repositories to distinguish original code from its clones
across projects. We employs source code similarity withoutnormalizing identifiers differently from code clone detection
tools as described in Section II. Al-Ekram [22] and Kawaguchi[23] all studied cloning for patterns. Ichi-tracker [24] is an
example of the many code search research that search forclones across various repositories on the Internet. While Ichitracker extracts similar file revisions in repositories, it does
not tell which one is likely the original revision. Our analysis
employs heuristics for identifying an original file revision.
According to Godfrey [25], the merge and splitting ofsource code entities is a common activity during the lifespanof a software system. During this process, the original context

may be lost over time. They then show how tracking origins
is beneficial for ownership, code comprehension, refactoringand software evolution research. Hashimoto [26] proposed an
AST-based comparison of file revisions to track co-evolutionof two branches in a project. Our analysis enables to track thehistory of source code reuse between two projects. German
and colleagues [27] proposed Software Bertillonage tracing
licensing implications of copied code fragments.
C. Software Reuse
Software reuse has been becoming standard practice insoftware engineering. Most research has focused on social,extent and nature of software reuse. Most studies borrow code
clone detection tools for identifying actual source code reuse.
Due to the complex nature of white-box reuse, a manual verification aspect is usually required. For example, Heinemann [28]analyzed white-box source code reuse among Java projects bymanually inspecting source code with the result of a code clone
detection tool. Xia [3], [11] also manually analyzed how sourcecode is reused, while the source code was obtained by a clone
detection technique. In this study, we present and evaluate
an automatic detection technique for white-box reuse. The
manual analyses conducted in [3], [11] can be automated byour tool. In those work, an original file revision was manually
identified in files reported by a clone detection tool. Our tool
can automatically identify the most similar file revision as theorigin of the reused file.
German et al. [29] analyzed code siblings copied acrossopen source software projects. They detected code clones
for certain releases and then investigated their history when
the code clones are introduced. Our tool analyzes the entire
repository of projects so that developers can analyze filerevisions that are modified after copy.
VI.

C ONCLUSION

Developers often reuse source code developed by anotherproject. Using a source code similarity metric, we have automatically extracted revision pairs that are likely source code
reuse. In the experiment, we have extracted 1394 revision pairs
from eight project pairs. The estimated precision and recall of
the tool are 0.901 and 0.943. 1004 (72.0%) of the pairs are
consistent with the information recorded in the repositories.
We have identified several inconsistent pairs that are caused byincorrect information in the repositories. 201 unrecorded reuse
instances pointed to file revisions in source repositories whose
contents are the same as revisions in destination repositories.
31.5% of commits for source code reuse have no version
numbers in the commit messages.
Developers may use the tool as a static checker before arelease to avoid security vulnerability and known issues of alibrary in their software. Even if developers did not record aversion number of a library, our tool reports version numbersof the library using the source code in their repository. The
version numbers help developers to decide whether files reused
from the library should be updated or not. The tool also reports
a similarity between a reused file and its original file so thatdevelopers can integrate their project-specific enhancement
into the latest version of the library.

In the future work, we are planning to improve the execution time of the tool. We also would like to automatically
identifying how a file revision is modified in a destination
repository. Since developers may import small changes such as
security fixes without changing the other source code, automatically generating an explanation how a copy has been modified
from the most similar revision is valuable for developers to analyze the current status of source code of their project. Finally,
we are also interested in cross-project analysis including morethan two projects. Because our current implementation reports
the same library file used in two projects as source code reuse,
we would like to include multiple projects in analysis so that
our tool can report more accurate and useful results.

[15]

[16]

[17]

[18]

[19]

ACKNOWLEDGMENT
We would like to thank Dr. Daniel M. German for his
valuable comments on this research.
The work was supported by JSPS KAKENHI No.25220003
and Osaka University Program for Promoting International
Joint Research.
R EFERENCES
[1]

[2]

[3]

[4]

[5]
[6]

[7]

[8]

[9]

[10]

[11]
[12]

[13]

[14]

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.
T. Mende, R. Koschke, and F. Beckwermert, “An evaluation of code
similarity identification for the grow-and-prune model,” Journal of
Software Maintenance and Evolution, vol. 21, no. 2, pp. 143–169, 2009.
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.
P. Jablonski and D. Hou, “Aiding software maintenance with copyand-paste clone-awareness,” in Proceedings of the 18th International
Conference on Program Comprehension, 2010, pp. 170–179.
D. Gusfield, Algorithms on Strings, Trees, and Sequences. Cambridge
University Press, 1997.
C. K. Roy and J. R. Cordy, “NiCad: Accurate detection of near-missintentional clones using flexible pretty-printing and code normalization,”in Proceedings of the 16th International Conference on Program
Comprehension, 2008, pp. 172–181.
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.
Lucia, F. Thung, D. Lo, and L. Jiang, “Are faults localizable?” inProceedings of the 9th Working Conference on Mining Software Repositories, 2012, pp. 74–77.
C. K. Roy and J. R. Cordy, “Scenario-based comparison of clone detection techniques,” in Proceedings of the 16th International Conference
on Program Comprehension, 2008, pp. 153–162.
S. Wu, U. Mamber, and G. Myers, “An o(np) sequence comparison
algorithm,” Information Processing Letters, vol. 35, no. 6, pp. 317–323,
1990.
P. Xia, “An empirical study of out-dated third-party code in open source
software,” Master’s thesis, Osaka University, 2013.
S. Duszynski, J. Knodel, and M. Becker, “Analyzing the source codeof multiple software variants for reuse potential,” in Proceedings of the
18th Working Conference on Reverse Engineering, 2011, pp. 303–307.
A. Hemel and R. Koschke, “Reverse engineering variability in sourcecode using clone detection: A case study for Linux variants of consumer
electronic devices,” in Proceedings of the 19th Working Conference on
Reverse Engineering, 2012, pp. 357–366.
M. Nonaka, K. Sakuraba, and K. Funakoshi, “A preliminary analysis
on corrective maintenance for an embedded software product family,”
IPSJ SIG Technical Report, vol. 2009-SE-166, no. 13, pp. 1–8, 2009.

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

T. Yamamoto, M. Matsushita, T. Kamiya, and K. Inoue, “Measuring
similarity of large software systems based on source code correspondence,” in Proceedings of the 6th International Conference on Product
Focused Software Process Improvement, 2005, pp. 530–544.
B. Ray and M. Kim, “A case study of cross-system porting in forked
projects,” in Proceedings of the ACM SIGSOFT 20th International
Symposium on the Foundations of Software Engineering, 2012, pp. 1–
11.
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.
N. Schwarz, M. Lungu, and R. Robbes, “On how often code iscloned across repositories,” in Proceedings of the 34th International
Conference on Software Engineering, 2012, pp. 1289–1292.
V. Bauer and B. Hauptmann, “Assessing cross-project clones for reuse
optimization,” in Proceedings of the 8th International Worskhop on
Software Clones, 2013, pp. 60–61.
M. Kim, V. Sazawal, D. Notkin, and G. Murphy, “An empirical studyof code clone genealogies,” in Proceedings of the 10th European
Software Engineering Conference Held Jointly with 13th International
Symposium on Foundations of Software Engineering, 2005, pp. 187–
196.
J. Krinke, N. Gold, Y. Jia, and D. Binkley, “Cloning and copying between GNOME projects,” in Proceedings of the 7th Working Conferenceon Mining Software Repositories, May 2010, pp. 98–101.
R. Al-Ekram, C. Kapser, R. C. Holt, and M. W. Godfrey, “Cloning byaccident: an empirical study of source code cloning across software systems,” in Proceedings of the 4th International Symposium on Empirical
Software Engineering, 2005, pp. 376–385.
S. Kawaguchi, P. K. Garg, M. Matsushita, and K. Inoue, “MUDABlue:an automatic categorization system for open source repositories,” Journal of Systems and Software, vol. 79, no. 7, pp. 939–953, 2006.
K. Inoue, Y. Sasaki, P. Xia, and Y. Manabe, “Where does this code
come from and where does it go? – integrated code history tracker
for open source systems –,” in Proceedings of the 34th International
Conference on Software Engineering, 2012, pp. 331–341.
M. 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.
M. Hashimoto and A. Mori, “A method for analyzing code homology in genealogy of evolving software,” in Proceedings of the 13th
International Conference on Fundamental Approaches to Software
Engineering, 2010, pp. 91–106.
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.
L. Heinemann, F. Deissenboeck, M. Gleirscher, B. Hummel, and
M. Irlbeck, “On the extent and nature of software reuse in open source
java projects,” in Proceedings of the 12th International Conference on
Top Productivity Through Software Reuse, 2011, pp. 207–222.
D. M. German, M. D. Penta, Y.-G. Gueheneuc, 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.