Filtering Clones for Individual User Based on Machine Learning Analysis
Jiachen Yang, Keisuke Hotta, Yoshiki Higo, Hiroshi Igaki, Shinji Kusumoto
Graduate School of Information Science and Technology, Osaka University
1-5, Yamadaoka, Suita, Osaka, 565-0871, Japan
Email: {jc-yang,k-hotta,higo,igaki,kusumoto}@ist.osaka-u.jp
wcstr = 0 ;Abstract—Results from code clone detectors may contain 2717
2718 s l e n = mbstowcs ( w c s t r , s , 0 ) ;plentiful useless code clones, and judging whether a code clone 2719 i f ( s l e n == −1)
is useful varies from user to user based on different purposes of 2720 s l e n = 0 ;them. We are planing a system to study the judgment of each 2721 w c s t r = ( w c h a r t ∗) x m a l l o c ( s i z e o f
mbstowcs ( w c s t r , s , s l e n + 1 ) ;individual user by applying machine learning algorithms on 2722
2723 w c l e n = w c s w i d t h ( w c s t r , s l e n ) ;code clones. We describe the reason why individual judgment 2724 f r e e ( w c s t r ) ;2725 r e t u r n ( ( i n t ) w c l e n ) ;should be respected and how in this paper.

Keywords-filtering, classify, machine learning, code clone
detector, judgment of user, token-based

I. I NTRODUCTION
Huge efforts have been made to detect identical or similarcode fragments from source code of software, with thesecode fragments called as “code clones” or simply “clones”.
Clone Detection Tools(referred as CDT) usually generate along list of clones from source code, among which a small
portion of clones are helpful to user in improving software
quality by applying refactoring or locating similar bugs, but
the rest are not so “interesting”.
Several methods have proposed to filter out those “uninteresting” clones such as metric-based method described in[1]. These methods are useful as they gathered a universal
standard of judging whether a clone is “interesting”, but theyeither require professional knowledges from user such as
what all these metrics mean, or hard to fit to individual use
case of users such as filtering only the code clones that canbe applied extracting-method refactoring on. Tairas and Gray
proposed a classification method in [2]. Compared with ourmethod, they are clustering by identifier names rather thanstructure of the identical clone fragments.
According to a survey we conducted, users of CDTs
tend to classify clones differently based on their individual
use cases, purposes or experience about code clones. With
this observation, we are working on the idea of studying
judgments of each user on clones, which results a new cloneclassifying method, entitled as Fica, Filter for Individual user
on code Clone Analysis.

(a) execute cmd.c1100 i f ( w c h a r l i s t == 0 )1101 {
1102
size t len ;1103
l e n = mbstowcs ( w c h a r l i s t , c h a r l i s t , 0 ) ;1104
i f ( l e n == −1)1105
len = 0;1106
w c h a r l i s t = ( w c h a r t ∗) x m a l l o c ( s i z e o f ( w c h a r t ) . . .
1107
mbstowcs ( w c h a r l i s t , c h a r l i s t , l e n + 1 ) ;1108 }(b) subst.c

Figure 1.

Example of source code in bash-4.2

they are willing to perform refactoring. Table I shows a partof the result. In this table, a code clone set is marked as O
if a student is willing to refactor it or as X if not so. We cansee from this table that their attitudes toward these clones
vary from person to person.
As an example, source of clone with ID 5 is showedin Figure 1. Because their functions are identical, S andU thought they could be merge together. But Y and M
considered the fact that Figure 1b is a code fragment in alarger function which is more than 100 LOC therefore may
be difficult to be refactored.
Also from Table I we can see that Y was more strict
than other three students. In the comment to this survey hementioned that only clones that contains an entire body of C
function are candidates for refactoring. This unique standard
Table IS URVEY OF CLONES IN BASH -4.2Clone ID
12345
Count of O
Count of X

II. M OTIVATING E XAMPLE
We conducted a survey on several students1 , providingthem 105 clone sets from result of CDT on source codes in
C language detected from bash-4.2, asking them whether
1 All of students are from Graduate School of Information Science andTechnology, Osaka University

978-1-4673-1795-5/12/$31.00 c 2012 IEEE( wchar t ) . . .

76

Y
X
X
O
X
X
5100

S
O
X
X
O
O
24
81

IWSC 2012, Zurich, Switzerland

MOO
X
X
X
2382

UOO
OO
O
2580

As the most simple case, users need to tell Fica that theyare interested in certain clones, and wants to find more likethese. Tags typed marks can be considered as possible extension of boolean typed ones that involve multiple choices.
Also user of Fica is allowed to have multiple profiles insystem, with each profile representing a use case of code
clones. Profiles should be trained separately and Fica willtreat them as individual users.
C. Machine Learning

Figure 2.

Fica receives the clones from CDT and marks fromuser, studies the characteristic of the marked clones by
calculating similarity of token sequence of these clones.
This step employs machine learning algorithms which arewidely used in natural language processing or text mining.
The algorithm to be used will be similar with the one GMailused in detecting spam emails. By comparing the similarityof marked clones and unmarked ones, Fica can thus predictthe possibility whether an unmarked clone is interesting or
not to user profile.

Overall Workflow of Fica with CDT

was also reflected in all 5 “interesting” clones he has chosen.
III. W ORKFLOW
In this section, we propose a workflow of Fica, whichranks detected clones based on studying historical behaviorof a particular user, as a complement to existing CDTs thatfiltering unexpected clones.

IV. C ONCLUSION AND F UTURE P LANS
We have shown the fact that users of CDT may havedifferent opinions on whether a code clone is “useful” or“interesting” to them. This observation suggested that filterof code clones should as well take user judgments into
consideration to generate more useful list of code clones.
We are currently building the described system Fica, asa web-based system for proof of concept research purpose.
The system consists of a generalized suffix tree [3] based
CDT and a web-based user interface that allows the usermarks detected code clones and shows ranked result.
We plan to release this system to public domain as soon
as the system is ready. Collected user data and calculated
result will also be released to public domain, which should
be useful for further studies on clone classifying.

A. Overall Workflow
The overall workflow of Fica is described in Figure 2.
1) User submits source code to a CDT.
2) CDT detects a set of clones in the source code.
3) User marks some of these clones as “interesting”
or not according to her/his own judgment, and thensubmits these marked clones to Fica as a profile.
4) Fica records marked clones into its own database.
5) Meanwhile Fica studies characteristics of all thesemarked clones by using machine learning algorithms.
6) Fica ranks other clones remaining unmarked based on
the result of machine learning, predicting the possibility of whether they are “interesting” or not to user.
7) User can further adjust the marks on code clones andre-submit them to Fica to obtain a better prediction.
Fica will also record these patterns that it have learned
into a database associated with the particular user
profile so that further predictions can be made basedon history decisions.

ACKNOWLEDGMENT
This study has been supported in part by Grants-in-Aidfor Scientific Research (A) (21240002) and Grant-in-Aid for
Exploratory Research (23650014) from the Japan Society for
the Promotion of Science.
R EFERENCES[1] Y. Higo, S. Kusumoto, and K. Inoue, “A metric-based approach
to identifying refactoring opportunities for merging code clones
in a java software system,” Journal of Software Maintenanceand Evolution: Research and Practice, vol. 20, no. 6, pp. 435–461, 2008.

B. Marking Clones Manually
User of Fica is required to firstly mark a small set ofclones found by CDT manually, to be used by Fica as an
initial training set. Considered types of marks on clones canbe boolean or tags:
bool Clones are marked as “interesting” or not.
tags Clones are marked as one of several tags or categories by user based on their use cases such as
refactoring procedural, issue tracking id, etc.

[2] R. Tairas and J. Gray, “An information retrieval process to aid
in the analysis of code clones,” Empirical Software Engineering, vol. 14, pp. 33–56, 2009, 10.1007/s10664-008-9089-1.
[3] E. Ukkonen, “On-line construction of suffix trees,” Algorithmica, vol. 14, no. 3, pp. 249–260, 1995.

77