2018 25th Asia-Pacific Software Engineering Conference (APSEC)

Investigating Vector-based Detection ofCode Clones Using BigCloneBench
Kazuki Yokoi∗ , Eunjong Choi† , Norihiro Yoshida‡ and Katsuro Inoue∗∗ Osaka University, Japan, {k-yokoi, inoue}@ist.osaka-u.ac.jp† Nara Institute of Science and Technology, Japan, choi@is.naist.jp‡ Nagoya University, Japan, yoshida@ertl.jp

II. P RELIMINARLY I NVESTIGATION

Abstract—In a vector-based approach to detecting code clones
from source code, all code fragments in the source are mappedto a vector space and then code fragments are detected ascode clones if they are neighbors in the vector space. So far,our research group has developed a vector-based approach
using TF-IDF and cosine similarity. For the improvement of
the vector-based approach, we preliminary investigated whatkind of vectorization algorithms and similarity measurements are
effective in terms of recall and detection time. In this paper, we
present preliminary investigation results using BigCloneBench, alarge-scale code clone benchmark.
Index Terms—code clone, software maintenance, information
retrieval

A. Vectorisation Algorithms and Similarity Measurements
Algorithms to vectorize documents are frequently used in
the ﬁeld of information retrieval. Note that, in this study,
each function in the source code was regarded as a document
and vectorized. We selected seven vectorization algorithms,
namely BoW (Bag-of-Words), TF-IDF, LSI (Latent SemanticIndexing), LDA (Latent Dirichlet Allocation), Word2Vec [7],[8], FastText [9], Doc2Vec [10]. Among these algorithms,
BoW and TF-IDF have a high possibility that generate highdimensional vectors, whereas LSI and LDA represent documents as low-dimensional vectors by adopting dimension
compression. Word2Vec and FastText generate vectors that can
express the meaning of words using deep neural networks.
In this study, we deﬁned the average vectors of Word2Vec
as WV-avg and the average vectors of FastText as FT-avg
respectively. Doc2Vec extends Word2Vec to entire documents.
Furthermore, to measure the similarity of vectors, we choose
cosine similarity and WMD (Word Mover’s Distance) [11]. In
this study, the parameters for each algorithm are determinedbased on the default values of gensim [12]1 , a python librarythat is used for implementing the algorithms in this study.

I. M OTIVATION
Programmers often copy and paste code fragment so thatthey can reuse existing code fragments. This causes code
clones (i.e, code fragments that are identical or similar codefragments to each other). Generally, a code clone is regarded
as a factor that hinders software maintainability [1]. However,
it is difﬁcult for developers to manually identify all code clone
from large-scale software systems.
To alleviate this problem, a multitude of code clone detection approaches have been proposed [2], [3], [4]. One of
the representative approaches for detecting code clones is
a vector-based approach. The advantage of this approach isthat it detects syntactically dissimilar code clones. It also
can detect clones at high speed by clustering similar codefragments. Our research group proposed a vector-based code
clone approach that detects similar functions in the source code
namely FLCCFinder (Function Level Code Clone Finder) [5].
FLCCFinder generates a feature vector from each function
based on the occurrence of identiﬁers and reserved keywords
using TF-IDF (Term FrequencyInverse Document Frequency).
It then clusters the generated vectors by means of localitysensitive hashing. Finally, it detects clones based on thesimilarities between each pair of feature vectors using cosine
similarity. However, FLCCFinder has possibilities that thegenerated vectors are high-dimensional vectors and vectors ofpolysemy and synonym are missed.
To improve FLCCFinder, we preliminary investigated whatkind of vectorization algorithms and distance measures are
effective in terms of recall and detection time. In this paper, we present preliminary investigation results using BigCloneBench [6], a large-scale code clone benchmark.
978-1-7281-1970-0/18/$31.00 ©2018 IEEE
DOI 10.1109/APSEC.2018.00095

B. Research Questions and Results
To investigate the impact of vectorization algorithms andsimilarity measurements for detecting code clones, we set up
two research question(RQ)s as follows.
1) RQ1: Does the recall of code clone detection vary withvectorization algorithms?: We set up this RQ to ﬁnd out
vectorization algorithms that can accurately detect code clones.
To answer this RQ, we applied an approach using each selected
vectorization algorithm with FLCCFinder to 25,000 opensource projects in BigCloneBench, consisting of 2.3 million
Java source ﬁles (365MLOC), and compared the recall ofeach approach. In this study, we set the threshold of 0.9 forcosine similarity because this threshold achieved high accuracy
in the previous study [5]. Note that we only used cosine
similarity to measure the similarity of vectors because it takes
approximately three months for WMD to detect code clones
from target projects. The results of the caparison are shownin Table I. With respect to the deﬁnition of each clone type,please refer to [6].
1 https://radimrehurek.com/gensim/699

TABLE IR ECALL FOR EACH VECTORIZATION ALGORITHM
Clone Type
Type-1 (T1)
Type-2 (T2)
Very-Strongly Type-3 (VST3)
Strongly Type-3 (ST3)Moderately Type3 (MT3)
Weakly Type-3/Type-4 (WT3/T4)

BoW
0.99
0.84
0.90
0.45
0.06
0.00

TF-IDF
0.990.82
0.82
0.37
0.03
0.00

LSI
0.99
0.92
0.91
0.61
0.09
0.00

LDA
0.99
0.85
0.95
0.61
0.23
0.02

Doc2Vec
0.99
0.91
0.83
0.46
0.04
0.00

WV-avg
0.99
0.95
0.97
0.84
0.55
0.08

FT-avg
0.99
0.94
0.93
0.79
0.43
0.05

TABLE IIC ALCULATION TIME FOR EACH VECTORIZATION ALGORITHM ( IN SECONDS )vectorisation algorithms
similarity measurements
generation time (seconds)
similarity calculation time (seconds)

BoW

TF-IDF

5.1
5.5

10.0
5.1

LSI

LDA
Doc2Vec
Cosine similarity
9.7
60.3
44.7
1.1
1.1
1.6

WV-avgFT-avg

42.7
1.1

196.1
1.1

Word2Vec
FastText
WMD
29.5
187.7
497.5
538.1

pression showed the highest speed. On the other hand, WMD
is much slower than the cosine similarity. In particular, thesimilar calculation time calculates the time to measures thesimilarity between one function and all other functions, that is,calculation of O(n). However, actual clone detection requires
the similar calculation of all functions and all functions, thatis, calculation of O(n2 ). This revealed that it is not practicalto use WMD for detecting code clones.

2) RQ2: Does the selection of vectorization algorithms
and distance scale affect detection speed?: We set up thisRQ to identify the algorithms that detect code clones withhigh speed. To investigate the speed of calculation vector,
we built 1MLOC dataset by randomly selecting ﬁles from
BigCloneBench. We then measured the time to generate thevectors (i.e., generation time) and the time to calculate thesimilarity between one function and all other functions in thesource code (i.e., similarity calculation time) with different
algorithms and similarity measurements with FLCCFinder.
The results are shown in Table II.

ACKNOWLEDGMENT
This work was supported by JSPS KAKENHI Grant Numbers JP25220003, JP18H04094 and JP16K16034.

III. D ISCUSSIONR EFERENCES

Regarding RQ1, T2 clones were detected with a recall of
more than 0.9 in LSI, Doc2Vec, WV-avg and FT-avg. Fromthese results, we can assume that T2 clones can be accurately
detected by using dimensional compression and deep neuralnetworks. Surprisingly, the recall of TF-IDF was lower than
BoW except for T1 clones. This is because the weights ofidentiﬁers tend to be higher than reserved words in TF-IDF,
and these code clones contain different identiﬁer names. Dueto the difference in the dimensional compression, LSI detects
T2 clones with high recall, meanwhile LDA detects MT3clones with high recall. Doc2Vec had relatively high recall indetecting T2 clones, however, it was not able to detect many
Type-3 code clones such as ST3 and MT3 clones. WV-avg
and FT-avg had the highest recall, but there is a possibility
that these algorithms achieved the highest recall due to thelarge numbers of detected clones.
Regarding RQ2, BoW is the fastest in the generation time
followed by LSI and TF-IDF. Meanwhile, algorithms using
deep neural networks such as FastText are slower than otheralgorithms. Word2Vec achieved the highest speed among algorithms using deep neural networks. In the algorithms using
dimensional compression, LDA is the slowest, whereas LSI
is the fastest. In the algorithms using deep neural networks,WV-avg is the fastest. FT-avg is slower than WV-avg (TableI) even though they achieved the the same recall. In thesimilarity calculation time, algorithms using dimension com-

[1] Z. Li, S. Lu, S. Myagmar, and Y. Zhou, “Cp-miner: ﬁnding copy-paste
and related bugs in large-scale software code,” IEEE Transactions on
Software Engineering, vol. 32, no. 3, pp. 176–192, 2006.
[2] 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.
[3] L. Jiang, G. Misherghi, Z. Su, and S. Glondu, “Deckard: Scalable andaccurate tree-based detection of code clones,” in Proc. of ICSE, 2007,
pp. 96–105.
[4] H. Sajnani, V. Saini, J. Svajlenko, C. K. Roy, and C. V. Lopes,“Sourcerercc: Scaling code clone detection to big-code,” in Proc. ofICSE, 2016, pp. 1157–1168.
[5] S. Numata, N. Yoshida, E. Choi, and K. Inoue, “On the effectiveness ofvector-based approach for supporting simultaneous editing of softwareclones,” in Proc. of PROFES, 2016, pp. 560–567.
[6] J. Svajlenko and C. K. Roy, “Evaluating clone detection tools withbigclonebench,” in Proc. of ICSME, 2015, pp. 131–140.
[7] T. Mikolov, K. Chen, G. Corrado, and J. Dean, “Efﬁcient estimation ofword representations in vector space,” Proc. of ICLR, 2013.
[8] T. Mikolov, I. Sutskever, K. Chen, G. Corrado, and J. Dean, “Distributedrepresentations of words and phrases and their compositionality,” Proc.
of NIPS, 2013.
[9] P. Bojanowski, E. Grave, A. Joulin, and T. Mikolov, “Enriching word
vectors with subword information,” Transactions of the Association for
Computational Linguistics, vol. 5, pp. 135–146, 2017.
[10] Q. Le and T. Mikolov, “Distributed representations of sentences anddocuments,” in Proc. of ICML, 2014, pp. 1188–1196.
[11] M. J. Kusner, Y. Sun, N. I. Kolkin, and K. Q. Weinberger, “From wordembeddings to document distances,” in Proc. of ICML, vol. 37, 2015,
pp. 957–966.
[12] R. Řehůřek and P. Sojka, “Software Framework for Topic Modellingwith Large Corpora,” in Proc. of LREC , May 2010, pp. 45–50.

700