IPSJ SIG Technical Report

Scalable Large-Variance Clone Detection
Tasuku Nakagawa1,a)Yoshiki Higo1,b)

Shinji Kusumoto1,c)Abstract: A code clone (in short, clone) is a code fragment that is identical or similar to other code fragments in source code. Clones generated by a large number of changes to copy-and-pasted code fragments
are called large-variance clones. It is diﬃcult for general clone detection techniques to detect such clones
and thus specialized techniques are necessary. In addition, with the rapid growth of software development,
scalable clone detectors that can detect clones in large codebases are required. However, there are no existing
techniques for quickly detecting large-variance clones in large codebases. In this paper, we propose a scalable
clone detection technique that can detect large-variance clones from large codebases and describe its implementation, called NIL. NIL is a token-based clone detector that eﬃciently identiﬁes clone candidates using
an N-gram representation of token sequences and an inverted index. Then, NIL veriﬁes the clone candidates
by measuring their similarity based on the longest common subsequence between their token sequences. We
evaluate NIL in terms of large-variance clone detection accuracy, general Type-1, Type-2, and Type-3 clone
detection accuracy, and scalability. Our experimental results show that NIL has higher accuracy in termsof large-variance clone detection, equivalent accuracy in terms of general clone detection, and the shortest
execution time for inputs of various sizes (1–250 MLOC) compared to existing state-of-the-art tools.

1.

Introduction

A code clone (in short, clone) is a code fragment that is
identical or similar to other code fragments in source code.
Clones are generated by copying, pasting, and modifying
code fragments for reuse. Clones are a major problem insoftware maintenance because they lead to bug propagation.
Therefore, clone detection techniques, which automaticallydetect clones in the target codebase, are essential. Manyclone detection techniques have been proposed [1].
It is important for clone detection techniques to detectclones that have been heavily edited. A clone generated byinserting or deleting a large number of statements in various places in a copy-and-pasted code fragment is called alarge-variance clone. Such clones are common in softwaredevelopment and should thus be detected along with general clones. Wu et al. pointed out that it is diﬃcult forexisting clone detectors to detect large-variance clones; they
proposed a technique for detecting such clones and presented
its implementation, called LVMapper [2].
It is also important for clone detection techniques to bescalable. Highly scalable clone detectors are required for analyzing large-scale projects or source ﬁles in an inter-project
repository. Many scalable clone detectors have been proposed [3, 4]. For example, to achieve scalable clone detection, SourcererCC [3] uses heuristics to reduce the numberof code block comparisons needed to detect clones.
1

a)
b)
c)

Osaka University
Suita, Osaka 565–0871, Japant-nakagw@ist.osaka-u.ac.jp
higo@ist.osaka-u.ac.jp
kusumoto@ist.osaka-u.ac.jp

c 1992 Information Processing Society of Japan⃝

However, clone detectors that can detect clones with alarge number of edits fail for large inputs [5] or require a longtime to detect clones [2]. Scalable clone detectors target only
identical or strongly similar clones (near-miss clones). They
are incapable of detecting large-variance clones, in which
many statements have been inserted or deleted. Therefore,
the scalable detection of large-variance clones is challenging.
In this paper, we propose a scalable technique for detecting large-variance clones and describe its implementation,
called NIL*1 , which uses an N-gram representation, an inverted index, and the longest common subsequence (LCS).
NIL is a token-based clone detector. One of the featuresof large-variance clones is that the order of many tokens
is preserved (i.e., the common subsequence between token
sequences of large-variance clones is long). Hence, to detect large-variance clones, NIL measures the similarity between the token sequences of two code fragments based on
the LCS. In addition, large-variance clones share many consecutive tokens. Hence, for scalable clone detection, NIL
uses an N-gram representation of token sequences and an
inverted index to reduce the number of code block comparisons needed to detect clones. First, NIL transforms code
blocks extracted from source ﬁles into token sequences andcreates an inverted index from the N-gram representation of
the token sequences. Next, it identiﬁes the clone candidates
for each code block using the code block and the inverted
index. Finally, it veriﬁes the clone candidates by measuring
the similarity between the code block and the clone candidates.
*1

A clone detector using N-gram, Inverted index, and LCS. NIL
is available at https://github.com/kusumotolab/nil.

1

IPSJ SIG Technical Report
1 protected String getPrompt(InputRequest request) {2
String prompt = request.getPrompt();3
if (request instanceof MultipleChoiceInputRequest) {4
StringBuffer sb = new StringBuffer(prompt);
5
sb.append("(");
6
Enumeration e = ((MultipleChoiceInputRequest) request).getChoices().elements();
7boolean first = true;
8
while (e.hasMoreElements()) {9if (!first) {10
sb.append(",");
11}
12
sb.append(e.nextElement());
13
first = false;
14}
15
sb.append(")");
16
prompt = sb.toString();
17}
18
return prompt;
19 }1 protected String getPrompt(InputRequest request) {2
String prompt = request.getPrompt();3
String def = request.getDefaultValue();4
if (request instanceOf MultipleInputChoiceRequest) {5
StringBuilder sb = new StringBuilder(prompt).append("(");
6boolean first = true;7for (String next : ((MultipleInputChoiceRequest) request).getChoices()) {8
if (!first) {9
sb.append(",");
10}
11
if (next.equals(def)) {12
sb.append('|');
13}
14
sb.append(next);
15
if (next.equals(def)) {16
ab.append('|');
17}
18
first = false;
19}
20
sb.append(")");
21
return sb.toString();22}
23else if (def != null) {24
return prompt + "[" + def + "]";
25}
26
else {
27
return prompt;
28
}
29 }

(a) Clone A(b) Clone B

Fig. 1: Example of large-variance clones
We evaluate NIL’s (1) large-variance clone detection accuracy, (2) general Type-1, Type-2, and Type-3 clone detection accuracy, and (3) scalability. We compared NIL
with existing state-of-the-art tools, namely LVMapper [2],CCAligner [5], SourcererCC [3], and NiCad [6]. The experimental results show that NIL has a high precision of 87%
in large-variance clone detection. It also has a high recallof 100%, as determined in our evaluation of large-varianceclone detection using a mutation technique. In general clone
detection, the accuracy of NIL is equivalent to that of theexisting tools. In addition, we conﬁrmed that NIL has highscalability; it can detect clones faster than the existing tools
for large inputs (codebases with 250 MLOC).

2.

Preliminaries

2.1 Deﬁnition
A code fragment is a consecutive segment ofsource code.
It can be represented by the tuple(f ile name, start line, end line).
A code block is acode fragment within braces. This study treats a function,
which is a code block, as a clone detection unit, as done inprevious studies [2,3,5]. Clones are code fragments identicalor similar to other code fragments in source code. A pairof similar code fragments is called a clone pair. Clones
are classiﬁed based on the degree of the similarity between
them as follows.
Type-1 is an exact copy without modiﬁcations (except
for white space and comments).
Type-2 is a syntactically identical copy; only variable,
types, or function identiﬁers are diﬀerent.
Type-3 is a copy with further modiﬁcations; statements
have been changed, added, or removed.
The minimum length of clones is the minimum number oflines that a code fragment must be to be treated as a clone.
It is often set to six lines or 50 tokens [1].

c 1992 Information Processing Society of Japan⃝

2.2 Large-variance clone
A large-variance clone is a clone generated by inserting ordeleting a large number of statements in various places in a
copy-and-pasted code fragment. Figure 4 shows an example
of large-variance clones. In this example, statements havebeen inserted into and deleted from various places in Clone A
to create Clone B. Wu et al. pointed out that existing clone
detectors are incapable of large-variance clone detection because most target to the detection of near-miss clones [2].
They deﬁned large-variance clone as follows. Consider twocode blocks c1 and c2 with LOC values of L1 and L2 , respectively, where L1 ≤ L2 . Let λ = Li /Lj (i.e., λ is theratio of the code lengths of two code blocks). If c1 and c2
are Type-3 clones and the corresponding λ ≤ 0.7, then theseclones are large-variance clones. They proposed LVMapper,a large-variance clone detector.
LVMapper detects clones using code windows ((a codefragment composed of k consecutive lines in a code block)).
Its clone detection has three phases, namely the locating, ﬁltering and verifying phases. In the locating phase, LVMapper identiﬁes pairs of code blocks that share at least one code
window as clone candidates. Then, in the ﬁltering phase,it calculates the proportions of common code windows foreach clone candidate and removes clone candidates whose
proportions are lower than ﬁltering threshold θ. Finally, inthe verifying phase, it veriﬁes each clone candidate based on
similarity measured using a common subsequence of lines
between each clone candidate’s code block pair.

3.

Approach

Figure 2 shows an overview of the proposed technique.
The input is a set of source code ﬁles, and the output is theclone pairs in the source code. In the proposed technique,large-variance clones are detected based on the similarity between token sequences based on the LCS, taking advantage

IPSJ SIG Technical Report

Sourcecode

Extract&
Tokenize

Tokenized
code block

Generate
N-grams

CreateN-grams
N-grams
N-grams

Inverted
Index

Preprocessing

Select eachcode block
Tokenized
code block

Generate
N-grams

N-grams
Locate&FilterVerifyClone detection

Clone
candidate

Clone pairFig. 2: Overview of NILof the fact that the order of many tokens in a large-varianceclone pair is preserved. In addition, large-variance clones
share many consecutive tokens. Hence, to achieve scalable
large-variance clone detection, the proposed technique reduces the number of code block comparisons by using an
N-gram representation of token sequences and an inverted
index. The proposed technique transforms code blocks insource code into token sequences in the Preprocessing phaseand detects clones by comparing the token sequences in the
Clone detection phase. In this study, we implemented the
proposed technique as a tool, called NIL. NIL is written in
the Kotlin language and currently targets only Java sourcecode. The following subsections describe the Preprocessing
and Clone detection phases.
3.1 Preprocessing
In the Preprocessing phase, NIL extracts code blocks fromthe target source code and transforms them into token sequences. NIL does not perform lexical analysis but simply divide each code block’s text based on symbols (e.g.,“+”, “−”, or braces), white spaces, or newlines, as done by
SourcererCC. For example, when the code block shown in ﬁgure 1a is transformed into the token sequence, protected,
String, getPrompt, InputRequest, request, .... With
this transformation, lexical analyzers for other languages
do not need to be implemented to extend NIL. The token
sequence transformation is fast because lexical analysis is
not necessary. In addition, NIL has a relatively low rate offalse positives because it does not normalize identiﬁers, suchas variable and function names. However, it may not detect clones whose identiﬁers have been changed (i.e., Type-2
clones). We discuss the impact of the lack of identiﬁer normalization in Section 4.
Next, NIL generates N-grams from each token sequence.
An N-gram is a chunk of consecutive N tokens. Figure 3
shows an example of generating 3-grams from the code blockc 1992 Information Processing Society of Japan⃝

protected String getPrompt(InputRequest request) {Source code

Divideprotected String getPrompt InputRequest request

Token sequence

Generate 3-grams
protected String getPrompt
protected String getPrompt InputRequest
protected

3-grams

getPrompt InputRequest request

Fig. 3: Example of generating 3-grams

shown in ﬁgure 1a. In this example, three 3-grams are
generated from the ﬁve tokens of on the ﬁrst line in thecode block. Even though large-variance clones include many
modiﬁcations (statement insertions and deletions), many tokens other than the statements match consecutively (i.e.,many N-grams match). Therefore, using N-grams is eﬀective for scalable large-variance clone detection.
Then, NIL creates an inverted index from the generated
N-grams. An inverted index is an information retrieval technology that allows the fast retrieval of documents that contains a word given as a query. It is often used in clone
detection techniques [4]. NIL uses a dictionary whose keys
are the hash values of N-grams, and values are the code
blocks containing the corresponding N-gram as an inverted
index. All code blocks containing an N-gram can be quickly
obtained by looking up the hash value of the N-gram in the
inverted index. Therefore, a pair of code blocks that sharean N-gram (i.e., the pair is possibly a large-variance clonepair) can be obtained quickly using the inverted index.
3.2 Clone detection
After the Preprocessing phase, NIL performs Clone detection using the inverted index created in the Preprocessing
phase and all code blocks. Clone detection is divided into
three phases, namely location, ﬁltration, and veriﬁcation,

3

IPSJ SIG Technical Report

Algorithm 1: Clone Detection
Input: C is a list of tokenized code blocks {c1 , c2 , . . . , cn },Inverted Index I of C, N for size of N-gram, θ for ﬁltering
threshold, δ for verifying threshold
Output: All clone pairs CP
1: CP ← ϕ;
2: for all each ci in C do
3:// Location phase4:// CC represents clone candidates
5:
CC ← ϕ6:
for j = 1, 2, . . . , (ci .len − N + 1) do
7:// ci [j] is j-th token in ci ’s token sequence
8:
n gram = concat(ci [j], ci [j + 1], . . . , ci [j + N − 1]);9:
key = hash(n gram);
10:// get is a function that returns values to which a given
key is mapped in a given dictionary11:
CC = CC ∪ get(I, key);12:
end for13:// Filtration phase14:
for all each ccj in CC do
15:/* common ngrams is a functionthat computes the number of common N-grams between
two given code blocks */16:
cn = common ngrams(ci , ccj );17:
m = min(ci .len, ccj .len);18:
f iltration sim = cn/(m − N + 1);
19:
if f iltration sim < θ then20:
CC = CC \ {ccj };21:
end if
22:
end for23:// Veriﬁcation phase24:
for all each ccj in CC do
25:/* lcs is a function that computes the length of the LCS
between token sequences of two given code blocks */26:
lcs len = lcs(ci , ccj );27:
verif ication sim = lcs len/min(ci .len, ccj .len);28:
if verif ication sim ≥ δ then29:
CP = CP ∪ (ci , ccj );30:
end if31:
end for32: end for
33: return CP ;as done by LVMapper [2]. First, NIL selects a code blockfrom all code blocks prepared in the Preprocessing phase as
the target code block. Then, in the location and ﬁltration
phases, NIL identiﬁes the clone candidates of the target code
block using an N-gram and the inverted index. Next, in theveriﬁcation phase, NIL veriﬁes that the target code blockand the clone candidates are clone pairs by calculating the
LCS. These phases are performed for each code block to detect all clone pairs in the target source code. Algorithm 1shows the Clone detection algorithm. The three phases ofClone detection are described in detail below.
3.2.1 Locaion phase
In the location phase, NIL collects the clone candidates of
the target code block using the inverted index. Lines 3–11
in Algorithm 1 are the location phase.
First, NIL generates N-grams from the token sequence of

c 1992 Information Processing Society of Japan⃝the target code block. M−N+1 N-grams are generated froma token sequence with length M . Next, a hash value is calculated for each N-gram. This hash value is used as a querywhen looking up values in the inverted index. Finally, NIL
applies the hash values to the inverted index and collects
code blocks that contain the N-gram whose hash value isthe same as the given hash value. The obtained code blocks
are referred to as the clone candidates of the target code
block.
3.2.2 Filtration phase
In the ﬁltration phase, NIL removes code blocks that unlikely to be clones from the clone candidates collected in thelocation phase. Lines 13–22 in Algorithm 1 are the ﬁltration phase. It is necessary to reduce the number of clone
candidates for scalable and fast clone detection because NIL
performs the LCS calculation, which is a time-consuming
process, in the veriﬁcation phase. NIL ﬁlters clone candidates based on a feature of large-variance clones.
As described in Section 3.1, the two code blocks of alarge-variance clone pair share a certain number of N-grams.
Hence, if two code blocks share few N-grams, the pair is unlikely to be a large-variance clone pair. Based on this feature, NIL calculates f iltration sim, deﬁned below, between
the target code block and each clone candidate.
f iltration sim(c1 , c2 ) =common ngrams(c1 , c2 )min(ngrams(c1 ), ngrams(c2 ))common ngrams(c1 , c2 ) = |ngrams(c1 ) ∩ ngrams(c2 )|where c1 and c2 are two code blocks with lengths |c1 | and|c2 |, respectively. ngrams(c1 ) and ngrams(c2 ) are thenumbers of N-grams generated from code blocks c1 andc2 , respectively. Because of the large number of statement insertions and deletions in large-variance clones, thetwo code blocks may have signiﬁcantly diﬀerent token sequence lengths. We use min in the denominator so thatf iltration sim can be properly calculated even such cases.
NIL removes clone candidates whose f iltration sim is lessthan ﬁltration threshold θ.
3.2.3 Veriﬁcation phase
In the veriﬁcation phase, NIL checks whether the target
code block and each clone candidate are a true large-varianceclone pair. Lines 23–31 in Algorithm 1 are the veriﬁcation
phase. As mentioned in Section 3.2.2, one of the featuresof large-variance clones is that the common subsequence between token sequences of large-variance clones is long even if
there are a large number of insertions and deletions. Therefore, NIL calculates the LCS between the target code blockand each clone candidate and measures the similarity of thepair based on the length of the LCS. The similarity function
verif ication sim(c1 , c2 ) is expressed as following
verif ication sim(c1 , c2 ) =lcs(c1 , c2 )min(|c1 |, |c2 |)where c1 and c2 are token sequences with lengths |c1 | and|c2 |, respectively, and lcs(c1 , c2 ) is the length of the LCS
between c1 and c2 .

IPSJ SIG Technical Report

We use min as the denominator of the similarity function
to detect large-variance clones, as done in the studies on
CCAligner [5] and LVMapper [2] even if the lengths of thetoken sequences diﬀer greatly.

4.

Evaluation

We evaluated NIL in terms of• large-variance clone detection accuracy,• general clone detection accuracy, and• scalability.
In the following subsections, we ﬁrst optimize the N-gramsize based on a balance between recall and execution time.
Next, we evaluate large-variance clone detection accuracy
in terms of precision and recall. Then, we evaluate generalclone detection using two commonly used benchmarks. Finally, we evaluate scalability by measuring execution timefor various input sizes. Additionally, we compare the above
results to those for four state-of-the-art tools [2, 3, 5, 6]. Table 1 shows these clone detectors and their settings. Thesesettings were taken from the prior studies [2,3,5]. Note thatthe threshold δ for veriﬁcation of LVMapper is variable andthat δ takes the following values depending on the numberof the lines of clone l.



0.7
δ = 1 − 0.03 × l



0.4

if 6 < l ≤ 10,
if 10 < l ≤ 20,
if 20 < l

4.1 SummaryFirst, we summarize the results of this evaluation. We
found that NIL has a high precision of 87% and a high recall of 100% in large-variance clone detection. These values
are the highest among the tested large-variance clone detectors [2, 5]. In general Type-1, Type-2, and Type-3 clone
detection, NIL’s accuracy is equivalent to that of the existing clone detectors, including large-variance clone detectors,
and its precision is higher than that of large-variance clone
detectors. Moreover, we conﬁrmed that NIL is the fastest at
detecting clones in large codebases (1–250 MLOC) among
the tested clone detectors.
4.2 Parameter setting
NIL requires three parameters, namely N for N-grams, ﬁltration threshold θ, and veriﬁcation threshold δ. We set δ
Table 1: Settings for various clone detectors
Tool

Settings

LVMapperMin length 6 lines, window size k = 3,
ﬁltering threshold θ = 0.1,
veriﬁcation threshold δ is dynamic.

CCAligner

Min length 6 lines, window size q = 6,
edit distance e = 1, min 60% similarity.

SourcererCC

Min length 6 lines, min 70% similarity.

NiCad

Min length 6 lines, max length 20,000 lines,
blind renaming, identiﬁer abstraction,
min 70% similarity.

c 1992 Information Processing Society of Japan⃝

to 0.7, which is often used in clone detectors [3, 6]. We set θ
to 0.1, as done for LVMapper. N must be carefully selected
because it has a large impact on performance (e.g., execution time and clone detection accuracy). If N is set to a toosmall value, the recall of clone detection will increase because more code blocks will share the same N-grams. However, because more code blocks are identiﬁed as clone candidates in the location phase, the number of comparison
targets in the ﬁltration and veriﬁcation phases increases, resulting in a longer execution time. Therefore, to optimize
the N , we executed NIL with N = 1–9 and measured theexecution time and clone detection recall for each N value.
We used BigCloneEval [7] to measure recall. BigCloneEval
automatically measures the recall of clone detectors using
BigCloneBench [8].
Table 2 shows the results for each N value. For N < 5,an increase in N signiﬁcantly reduces the execution time
without lowering recall by more than one point compared towhen N = 1. For N = 5 and 6, execution time decreases but
recall also decreases. For N > 6, execution time does not
signiﬁcantly decrease. Therefore, considering the balance
between execution time and recall, N = 5 is the optimalvalue.
4.3 Large-variance clone detection
We evaluated the large-variance clone detection accuracyof NIL in terms of precision and recall and compared theresults to those for existing large-variance clone detectors,
namely CCAligner and LVMapper.
4.3.1 Precision
Precision is the ratio of correct clones detected to allclones detected. A clone detector with higher precision provides more accurate results. In general, precision is measured via a manual validation of the clones detected by thetarget tool. In this study, we used Ant and Maven, whichwere used in the prior studies on CCAligner [5] and LVMapper [2] to measure precision. JDK1.2.2 and OpenNLP, also
used in the above studies, were not used here because we
could not ﬁnd the source code for JDK1.2.2, which has been
end-of-lifed and we considered OpenNLP to be unsuitable
for manual validation because it is a machine learning library whose source code is diﬃcult to read (e.g., it includes
repetitive array manipulation code). We used the following
procedure to measure the precision of each tool:( 1 ) we input the target source code into each tool,( 2 ) we randomly selected 100 large-variance clone pairs
with more than 10 lines for each tool and target system, and( 3 ) we manually conﬁrmed whether the clone pairs werecorrect.
To remove bias in the manual validation, the detectedlarge-variance clone pairs of a given tool were validated without knowledge of the tool used for detection. Table 3 shows
the number of ﬁles and total LOC for Ant and Maven.
Table 4 shows the number of large-variance clone pairs

5

IPSJ SIG Technical Report

detected by each tool and the precision for each tool*2 . The
number of large-variance clones detected by NIL detected
was almost same as that of LVMapper and more than thatof CCAligner. The manual validation results indicate that
NIL had a high average precision of 87% whereas LVMapper
and CCAligner had low average precision values of about 60%
and 40%, respectively. We considered this diﬀerence in precision to be due to LVMapper and CCAligner normalizing theidentiﬁers in code blocks. After checking the large-varianceclones detected by LVMapper and CCAligner, we found thatcode blocks with consecutive assignment statements, suchas constructors, and consecutive if-statements were incorrectly detected as large-variance clones. In contrast, NIL detected large-variance clones more precisely because it does
not perform identiﬁer normalization.
In addition, NIL had a higher precision than that of
LVMapper and detected a similar number of large-varianceclone pairs, indicating that it can detect many large-varianceclones that LVMapper cannot. After checking large-varianceclones that NIL detected but LVMapper did not, we foundthat the large-variance clone pairs share a small number ofconsecutive lines. LVMapper regards three consecutive lines
in code blocks as code windows (see Section 2) and identiﬁes
clone candidates based on these code widows. Therefore, if apair of code blocks shares a little or no code window, LVMapper cannot detect the pair as a large-variance clone pair. In
contrast, NIL can detect such large-variance clones because
it uses an N-gram representation of token sequences.

Table 3: Target systems
System# Files

LOC

895
698

109,073
60,471

Ant 1.10.1
Maven 3.5.0

Table 4: Large-variance clone detection results
Tool

System# Large-variance clones

Precision (%)

NIL

Ant
Maven

354
398

86.0
88.0

LVMapper

Ant
Maven

355
389

64.0
60.0

CCAligner

Ant
Maven

184
284

43.0
40.0

4.3.2 Recall
Recall is the ratio of clones detected by a tool to the total number of true clones in the target codebase. A clone
detector with a higher recall can detect true clones moreexhaustively. To evaluate recall, all true clone pairs in thetarget codebase are required. However, it is not realistic tomanually check all code block pairs in a system to determine
the total number of true clone pairs.
Therefore, we generated large-variance clone pairs automatically using mutation techniques to evaluate recall. Mutation techniques are frequently used for clone detector recall evaluation [9]. The studies on CCAligner [5] and LVMapper [10] used them to evaluate large-variance clone detection
recall. In this study, we reproduced large-variance clones
by randomly inserting various numbers of statements into
original code blocks (i.e., the large-variance clones are mutants of the original code blocks). We targeted JDK6 andApache Commons*3 because they were used in the study on
CCAligner [5]. We randomly selected 100 functions with
15–50 lines in these systems as the original code blocks. A
minimum length 15 lines is often used for recall evaluation
using mutation techniques [3,9]. We used a maximum lengthof 50 lines because if the number of lines of the original code
blocks is too large, even if a large number of statements areinserted into the code blocks, the generated clones will not
be large-variance clones. For example, if 20 lines of statements are inserted into an original code block, if the number of lines of a code block is 100, the ratio of lines of theclone pair is 100/120 > 0.7, and thus the clone pair does
not satisfy the large-variance clone deﬁnition. To reproduce
large-variance clone pairs, 1–20 one-line statements were inserted into each code block at random locations. 20 clone
pairs were generated per original code block, for a total of
2,000 clone pairs, including large-variance clone pairs*4 .
Figure 4 shows the recall of NIL, LVMapper, andCCAligner for clone pairs generated by inserting various
numbers of statements. NIL detected all generated clone
pairs. This is because even though many statements areinserted into a code block, the order of many tokens between
the large-variance clone pair is preserved, and thus the clone
pair shares a certain number of N-grams and has a long common subsequence. In summary, using N-gram-based clone
candidate identiﬁcation and token-LCS-based clone validation is eﬀective in large-variance clone detection.
*3*2

Manual validation descriptions are available at https://zenodo.org/record/4490845*4

A project that provides open-source reusable Java components
The generated large-variance clone pairs are available at https://zenodo.org/record/4491016

Table 2: Recall and execution time results for each N value
N

1

2

3

4

5

6

7

8

9

Type-2
Very Strongly Type-3
Strongly Type-3
Moderately Type-3

97.5
93.5
68.4
11.2

97.5
93.5
68.4
11.2

97.5
93.5
68.4
11.2

97.5
93.5
68.3
11.1

96.6
93.5
67.1
10.6

96.3
93.1
65.3
9.9

96.1
92.9
64.6
9.3

95.8
92.7
63.7
8.7

93.3
92.5
62.0
7.8

Execution time

> 24h

2h 13m 52s

21m 42s

5m 56s

2m 58s

1m 13s

1m 4s

1m 2s

57s

c 1992 Information Processing Society of Japan⃝

IPSJ SIG Technical Report

100

NIL

90
80

Recall (%)

70

LVMapper60
50

CCAligner

40
30
20
10
0
1

2

3

4

5

6

7

8

9 10 11 12 13 14 15 16 17 18 19 20# Inserted lines

Fig. 4: Recall results for various numbers of inserted lines
On the other hand, as shown in Figure 4, the recall of
LVMapper and CCAligner decreased with increasing numberof inserted lines. LVMapper can also detect clones in whicha large number of statements are inserted because it veriﬁes
clones based on line-based LCS. However, our evaluation
results show that the recall of LVMapper decreased with increasing number of inserted lines. This is because LVMapper
failed to identify many large-variance clones in its locatingphase. LVMapper identiﬁes a pair of code blocks that sharesome code windows (see Section 2) as a clone pair. Therefore, with increasing number of inserted lines, the number ofshared code windows decreases, and thus LVMapper failed
to identify a pair of code blocks as a large-variance clone
pair. CCAligner uses e-mismatch code windows to identify
clone candidates, and this aﬀects its recall. In addition,
CCAligner uses code windows in veriﬁcation and thus fails
to detect large-variance clones.
4.4 General clone detection
We evaluated the general Type-1, Type-2, and Type3 clone detection accuracy of NIL using two benchmarks,
namely Mutation Framework [9] and BigCloneEval [7]. In
addition, we compared the results of NIL to those of existing state-of-the-art tools, namely CCAligner, LVMapper,
SourcererCC, and NiCad.
4.4.1 Mutation Framework
Mutation Framework automatically generates clone pairs
based on mutation techniques. We executed Mutation
Framework with all the default settings and input the generated clones*5 into each clone detector. Table 5 shows theresults of recall for each tool measured by Mutation Framework. NIL detected all clone pairs generated by Mutation
Framework.
4.4.2 BigCloneEval
BigCloneEval [7] automatically measures the recall ofclone detectors using BigCloneBench [8]. We also measured
precision, as done in the prior studies [2,3,5]. For each tool,
we randomly selected 400 of the detected clone pairs from
BigCloneBench and validated them manually. The clones
were shuﬄed, and the validation was conducted without
knowledge of the clone source.
Table 6 shows the results of recall*6 and precision for eachtool on BigCloneBench*7 . As shown, NIL has a high recall of 96% for Type-2 clone detection even though it does
not normalize identiﬁers in the Preprocessing phase. NIL
had the second highest recall of Moderately Type-3 clones,
which contain large-variance clones, behind only LVMapper.
We considered that this is because normalizing identiﬁers isnecessary to detect most Moderately Type-3 clones.
The precision (see bottom of Table 6) of both LVMapper and CCAligner, which are large-variance clone detectors,
was low. In contrast, that of NIL was very high (94%). Even
though SourcererCC and NiCad also had high precision, they
had poor large-variance clone detection performance. Therefore, compared to the existing tools, NIL has equivalent general clone detection accuracy and higher precision than thatof the existing large-variance clone detectors.
4.5 Scalability
We evaluated the scalability of NIL using codebases withvarious sizes and compared the execution time of NIL to
those of the existing tools. We used IJaDataset [12], alarge inter-project Java dataset, as done in the prior studies [2, 3, 5]. We created datasets with 1, 10, 100, and 250
MLOC*8 . We used CLOC [13] to measure the LOC of thedatasets. A computer with a quad-core CPU and 12 GB ofmemory was used for the evaluation, as done in the priorstudies [3, 5].
Table 7 shows the execution times for each tool for various input sizes. As shown, the execution time of NIL is theshortest for all input sizes. Even though both LVMapper
and SourcererCC detected clones from the 250-MLOC codebases, their execution times are longer than three days, indicating poor scalability. In addition, CCAligner and NiCad
was not able to complete detecting clones from the 100- and
10-MLOC codebases, respectively, indicating their limited
scalability. Therefore, NIL has the highest scalability.

Table 5: Recall results for Mutation Framework
Tool

NIL

LVMapper

CCAligner

SourcererCC

NiCad

*6

Type-1
Type-2Type-3

100.0
100.0
100.0

100.0
100.0
99.9

100.0
100.0
99.9

100.0
100.0
100.0

100.0
100.0
100.0

*7

*5

The generated clone pairs are available at https://zenodo.
org/record/4491052

c 1992 Information Processing Society of Japan⃝*8

Note that in our experiments, BigCloneEval reported diﬀerent
recall of the existing clone detectors from the prior studies.
Type-1 recall of some clone detectors was 99.9% because BigCloneBench contains faulty clone pairs [11].
Manual validation descriptions are available at https://zenodo.org/record/4493069
These datasets and an executable ﬁle of NIL are available athttps://zenodo.org/record/4491208.

7

IPSJ SIG Technical Report5.

and completion, refactoring, and bug propagation for largevariance clones using NIL.
Acknowledgments This work was supported by
MEXT/JSPS KAKENHI 20H04166.

Threats to validity

To measure precision for each tool, we manually validated
clones each tool detected, as done in the prior studies [2,3,5].
Because the clone detector names were not disclosed during
the manual validation, there was no bias in the evaluation.
However, because the criteria for whether a pair of code fragments is a clone pair can vary, manual validation by otherresearchers may yield diﬀerent values. To ensure the validityof this study, the clones used in the manual validation are
made public so that a third party can conduct replication
studies.
In this study, we used the widely used benchmarks, BigCloneEval [7] and Mutation Framework [9] to evaluate therecall of clone detectors. Diﬀerent results may be obtainedusing other benchmarks.
In this study, we targeted only the Java language. Diﬀerent results may be obtained for other languages.
It is known that the accuracy and execution time of aclone detector is greatly inﬂuenced by its settings [14]. In
this study, we optimized the N value for N-grams. However,the ﬁltration threshold θ and the veriﬁcation threshold δwere set based on values used by other clone detectors. The
results can be improved by optimizing these values for NIL.

6.

References
[1]

[2]

[3]

[4]

[5]

[6]
[7]

[8]

Conclusion

In this study, we proposed a clone detection technique forthe scalable detection of large-variance clones from a large
codebase and described its implementation, called NIL. NIL
uses N-grams, an inverted index, and the LCS to detectlarge-variance clones. Our experimental results show that
NIL has higher precision and recall in large-variance clone
detection than those of existing large-variance clone detectors. In addition, the general Type-1, Type-2, and Type-3
clone detection accuracy of NIL is equivalent to that of existing state-of-the-art tools. Moreover, NIL can detect clones
from large codebases more quickly than do existing clone
detectors.
As future works, we consider doing research on software engineering applications such as code recommendation

[9]

[10]
[11]
[12]
[13]
[14]

Bellon, S., Koschke, R., Antoniol, G., Krinke, J. and Merlo,E.: Comparison and Evaluation of Clone Detection Tools,IEEE Transactions on software engineering, Vol. 33, No. 9,
pp. 577–591 (2007).
Wu, M., Wang, P., Yin, K., Cheng, H., Xu, Y. and Roy,C. K.: LVMapper: A Large-Variance Clone Detector Using
Sequencing Alignment Approach, IEEE Access, Vol. 8, pp.
27986–27997 (2020).
Sajnani, H., Saini, V., Svajlenko, J., Roy, C. K. and Lopes,
C. V.: SourcererCC: Scaling Code Clone Detection to BigCode, Proceedings of the 38th International Conference on
Software Engineering, pp. 1157–1168 (2016).
Hummel, B., Juergens, E., Heinemann, L. and Conradt, M.:
Index-based code clone detection: incremental, distributed,
scalable, Proceedings of 2010 IEEE International Conference
on Software Maintenance, pp. 1–9 (2010).
Wang, P., Svajlenko, J., Wu, Y., Xu, Y. and Roy, C. K.:
CCAligner: a token based large-gap clone detector, Proceedings of the 40th International Conference on Software Engineering, pp. 1066–1077 (2018).
Cordy, J. R. and Roy, C. K.: The NiCad Clone Detector,
Proceedings of 2011 IEEE 19th International Conference on
Program Comprehension, pp. 219–220 (2011).
Svajlenko, J. and Roy, C. K.: BigCloneEval: A Clone Detection Tool Evaluation Framework with BigCloneBench, Proceedings of 2016 IEEE International Conference on Software
Maintenance and Evolution, pp. 596–600 (2016).
Svajlenko, J. and Roy, C. K.: Evaluating Clone Detection
Tools with BigCloneBench, Proceedings of 2015 IEEE International Conference on Software Maintenance and Evolution, pp. 131–140 (2015).
Svajlenko, J. and Roy, C.: The Mutation and Injection
Framework: Evaluating Clone Detection Tools with Mutation Analysis, IEEE Transactions on Software Engineering(2019).
Wu, M., Wang, P., Yin, K., Cheng, H., Xu, Y. and Roy,C. K.: LVMapper: A Large-variance Clone Detector Using
Sequencing Alignment Approach (2019).
Inoue, K., Miyamoto, Y., German, D. M. and Ishio, T.: CodeClone Matching: A Practical and Eﬀective Approach to Find
Code Snippets, arXiv preprint arXiv:2003.05615 (2020).
[Online]: Ambient Software Evolution Group: IJaDataset
2.0., http://secold.org/projects/seclone (2021).
[Online]:
CLOC: Count lines of code, http://cloc.
sourceforge.net/ (2021).
Wang, T., Harman, M., Jia, Y. and Krinke, J.: Searchingfor Better Conﬁgurations: A Rigorous Approach to Clone
Evaluation, Proceedings of the 2013 9th Joint Meeting on
Foundations of Software Engineering, pp. 455–465 (2013).

Table 6: Recall and precision results for BigCloneBench
Tool

NIL

LVMapper

CCAligner

SourcererCC

NiCad

Type-1 Recall
Type-2 Recall
Very Strongly Type-3 Recall
Strongly Type-3 Recall
Moderately Type-3 Recall

99.9
96.6
93.5
67.1
10.6

99.9
99.2
98.1
81.8
19.1

99.8
98.9
97.4
69.0
10.0

93.8
96.6
68.2
59.0
4.8

99.9
99.2
98.4
69.7
0.5

Precision

94.0

58.5

33.7

99.2

80.2

Table 7: Scalability results
Tool

NIL

LVMapper

CCAligner

SourcererCC

NiCad

1M
10 M
100 M
250 M

10s
1m 38s1h 38m 29s
7h 40m 7s

29s
13m 38s
17h 23m 39s
3d 13h 47m 39s

52s
26m 3s——3m 1s
27m 37s
19h 38m 5s
5d 6h 55m 1s

1m 48s———c 1992 Information Processing Society of Japan⃝