Finding Similar Defects
Using Synonymous Identiﬁer Retrieval
Norihiro Yoshida, Takeshi Hattori, Katsuro Inoue

Graduate School of Information Science and Technorogy, Osaka University
1-5 Yamadaoka, Suita, Osaka, 565-0871, Japan{n-yosida, inoue}@ist.osaka-u.ac.jp
ABSTRACT

ir_debug( Dmsg(10, "ProcWideReq7 start!!\n") );When we encounter a defect in one part of a program, it
is very important to ﬁnd other parts of the program that
may contain similar defects. In this paper, we propose anovel system to ﬁnd similar defects in the large collectionof source code. This system takes a code fragment containing a defect as the query input, and returns code fragments
containing the same or synonymous identiﬁers which appear
in the input fragment. Case studies with two open source
systems and their defect data show the advantages of the
proposed retrieval system, compared to the code-clone based
retrievals.

// buffer overflow check is missing!
buf += HEADER_SIZE;
Request.type7.context = S2TOS(buf);
buf += SIZEOFSHORT;
Request.type7.number = S2TOS(buf);
buf += SIZEOFSHORT;
Request.type7.yomilen =(short)S2TOS(buf);(a) Example of code fragment containing a buﬀer overﬂow
defectir_debug( Dmsg(10, "ProcWideReq14 start!!\n") );// buffer overflow check is missing!
buf += HEADER_SIZE;
Request.type14.mode = L4TOL(buf);
buf += SIZEOFINT;
Request.type14.context = S2TOS(buf);
buf += SIZEOFSHORT;
Request.type14.yomi = (Ushort *)buf;(b) Example of code fragment which is slightly diﬀerent from
Figure 1(a) and also contains a buﬀer overﬂow defectCategories and Subject Descriptors
D.2.5 [Software Engineering]: Testing and Debugging—
Debugging aids and diagnostics; D.2.4 [Software Engineering]: Software/Program Veriﬁcation—Statistical methods

General Terms
Algorithms, Experimentation

Figure 1: Similar defects in Canna 3.6 [3]Keywords
Code Retrieval, Natural Language Processing, Defect Detection
Six days after this incident, a second incidence occurred.
Similar boot-up time failure happened at more than 100 fairadjustment machines in Tokyo’s 65 stations, and about 400
passengers were troubled. Those machines, also made by thesame vendor, share a similar boot-up process as the automatic gate machines, but they used a diﬀerent data format,
causing failure on a diﬀerent day. Just after the ﬁrst incident, the vendor investigated other programs which relate
to the automatic gate machines, but the vendor could not
ﬁnd the similar defect which would have prevent the second
incident.
These incidents indicate the importance and also diﬃculty of ﬁnding similar defects in software product collections. There are various literatures discussing the creation
and removal of similar defect code [14, 15, 22]. We are interested in ﬁnding similar code fragment in a large collectionof source code, to eﬀectively locate similar code defects.
To specify our focus of similar defects, we give an example
in Figure 1, which presents two code fragments of an open
source Japanese input system Canna Ver. 3.6 [3]. These
two fragments involve several buﬀer input operations (e.g.,
buf += HEADER SIZE; . . . = S2TOS(buf);), but there are no

1. INTRODUCTION
In the early morning of October 12th, 2007, more than
4,000 automatic gate machines at Tokyo’s 662 railway stations were unable to start up correctly [20]. Those gatemachines, made by a Japanese vendor, failed to download
daily data from a central data server during their boot-up
process, and this failure caused system crashes. The vendor
tried to resolve this failure immediately, but it took morethan a half day to locate and ﬁx a single-line defect in thesource code, because of its complex logical structure. This
failure inconvenienced approximately 2.6 million passengers.

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that
copies bear this notice and the full citation on the first page. To copy
otherwise, or republish, to post on servers or to redistribute to lists,requires prior specific permission and/or a fee.
IWSC’10, May 8, 2010, Cape Town, South Africa.
Copyright © 2010 ACM 978-1-60558-980-0/10/05…$10.00.

49

2.

buﬀer boundary checks, resulting in implicit buﬀer overﬂow
defects. Suppose that we ﬁrst recognize that code fragment
Figure 1(a) contains the buﬀer overﬂow defect. To preventthe same buﬀer overﬂow failures, we need to ﬁnd and ﬁx
all the similar code fragments such as shown in Figure 1(b),which is slightly diﬀerent from Figure 1(a) but which sharessame variables and macros. The research question we areinterested in here is how eﬀectively we can locate code fragments like Figure 1(b) in a large-scale source code collection
when a reference code fragment like Figure 1(a) is given.
A straightforward approach to this issue, which is widelyused in the practice, would be using search tools such as grep[8]. However, it is not easy for the developers to choose anappropriate identiﬁer as the search keyword [21]. In general,
there are many candidate identiﬁers in the reference codefragment and the choice of the identiﬁers heavily aﬀects thesearch results. For example, in the case of Figure 1(a), we
may choose a variable name buf as the search identiﬁer; however, it will produce many unwanted retrieval results since
buf is widely used in many parts of the system. We probably
need to combine several identiﬁers as the search keys, but it
is a generally diﬃcult task.
Another approach would be to employ more sophisticatedretrieving tools such as code clone detection tool [1, 10, 11,12]. However, most code clone detection tools permit only
minor changes between clones, since they basically dependon string or tree matching algorithms after the input sequence normalization, tokenization, and/or tree construction. In the case of Figure 1, there two fragments are notreported as a code clone pair by a popular code clone tool,
CCFinder signiﬁcant diﬀerences in the last line.
In this paper, we will explore a novel approach which issimpler and more eﬀective in locating similar fault code fragments than existing methods and tools. We propose a synonymous identiﬁer retrieval method. This approach has thefollowing characteristics.

PROPOSED METHODAs shown in Figure 2, the proposed method accepts acode fragment as a query, and then identiﬁes similar codefragments in a target source ﬁles. The process comprises
three steps as follows.
Identiﬁer Extraction We extract identiﬁers from both querycode fragment and target source ﬁles, and apply several normalization rules to extracted identiﬁers. We
may call these normalized identiﬁers simply identiﬁers
if there is no confusion.
Synonymous Identiﬁer Determination Synonyms of eachidentiﬁer are determined by a method commonly usedin natural language processing [4].
Retrieval with Query Code Fragment Code fragments
are extracted as similar code fragments from the target source ﬁles, if those code fragments have the samesynonymous identiﬁers as the query identiﬁers.
We will explain each step in detail through following subsections.

2.1

Identiﬁer Extraction

At ﬁrst, identiﬁers are extracted from both query codefragment and target source ﬁles. To each extracted identiﬁer, several normalization rules are applied (e.g. dividing
at underscore, number elimination), producing a set of normalized identiﬁers.
Next, we create a matrix named identiﬁer matrix, which
represents the occurrence of identiﬁers in each structural unitof the target source ﬁles. A structural unit is a source codefragment obtained by a systematic partition of the target
source ﬁles. A module, a function, or a structural block
would be examples of structural units. We employ functions
as the structural unit hereafter in this paper.
Figure 3 illustrates an example of functions involving identiﬁers. There are three functions f0 , f1 and f2 and they
involve ﬁve identiﬁers ia , ib , ic , id and ie . In the identiﬁer extraction, those ﬁve identiﬁers are extracted from threefunctions as shown in Figure 3.
Figure 4 is the identiﬁer matrix created from the functions in Figure 3. The matrix represents the occurrences ofidentiﬁers ia , ib , ic , id and ie in functions f0 , f1 and f2 .

• A whole code fragment is used as the input to thequery. This allows developers to perform retrieval without careful choice of the query identiﬁers.
• We employ a code fragment retrieval method basedon the occurrence of similar identiﬁers in the queryand target code fragments. This approach is more robust to syntactic diﬀerences of code fragments thansequential or structural matching methods such as thetoken-based code clone detection tools.
• The retrieval is made using extracted identiﬁers. A
pair of identiﬁers frequently co-existing in close proximity are considered as the same identiﬁer, and aretreated as if they where synonyms of each other. The
retrieval is made using extracted identiﬁers and theirsynonyms.

2.2

Synonymous Identiﬁer Determination

In the synonymous identiﬁer determination, we perform
clustering of the identiﬁers based on Dagan’s model [4]. The
clustering procedure is as follows.

Step1: Co-occurrence Matrix Creation.
First, a co-occurrence matrix is created from the identiﬁer matrix. Let N denote the number of diﬀerent identiﬁers. The co-occurrence matrix is represented as an N × N
symmetrical matrix. Each element (ix , iy ) is the numberof functions (i.e, structural units) in which ix and iy cooccur. Figure 5 is the co-occurrence matrix created fromthe identiﬁer matrix in Figure 4. Since ic and ie occur twice
in functions f0 and f2 , then (ic , ie ) and (ie , ic ) become 2.
Diagonal elements are not used in our method, so they are
ﬁlled with symbol “−”.

We have developed SC-Retriever (Synonymous Code Retriever) implementing the proposed method. SC-Retriever
has been applied to ﬁnd defects in two software systems,
Canna and SPARS-J [19]. We have conﬁrmed the advantagesof our approach, compared with CCFinder [11].
In Section 2 we present our retrieval method. Section 3
gives results derived from using this method. In Section
4, several related works and discussions will be presented.
Finally, we will conclude our paper with a few remarks in
Section 5.

50

Proposed method

Query codefragment

Identifier
extraction &normalization

Targetsource files

Similar codefragments

Retrieval

Identifier
extraction &normalization

Synonymous identifier
determination

Figure 2: An overview of proposed method

Step2: Distance Calculation.

ib

ic

ia

ib

id

ic

ic

ic

id

(a) function f0

ie
ic

id

(b) function f1

Distance between each identiﬁer pair is computed by using
Jensen-Shannon divergence method [17]. The computation
is based on the measurement of probability distribution of
two vectors extracted from the co-occurrence matrix. Figure
6 is an example of distance matrix. Each element is nonnegative real number, and it represents the distance of two
identiﬁers, where 0 means no distance.
Jensen-Shannon divergence between two identiﬁers is intuitively calculated as a diﬀerence of two vectors of the cooccurrence matrix. For example, the distance between theidentiﬁers id and ie is represented by the diﬀerence between
two vectors [(ia , id ), (ib , id ), (ic , id )] and [(ia , ie ), (ib , ie ), (ic , ie )](i.e, the diﬀerence between [1, 0, 1] and [0, 0, 2]). If such difference is relatively large, the value of the corresponding
element in the distance matrix is also relatively large.

ie(c) function f2

Figure 3: Example of functions involving identiﬁers

i
0 a
f0
0
f1 @ 1
f2
0

ib
2
0
0

ic
1
2
2

id
0
3
0

ie
1
0
0A
2

Step3: Performing Clustering.
We perform clustering of identiﬁers based on the distanceof identiﬁers. Initially, a set of identiﬁers with distances
between them is given and a threshold for terminating theclustering is determined by the user. The clustering is performed as the following steps.

Figure 4: Example of identiﬁer matrix (created from
Figure 3)ia
ia −ib B 0B
ic B 1
id @ 1
ie
0
0

ib
0
−
1
0
0

ic
1
1
−
1
1

id
1
0
1
−
0

(a) Initial clusters are created for each identiﬁer.

ie
1
0
0C
C
1C
0A
−

(b) For each pair of clusters, a distance value is calculated
by group average method1 , then the closest clusters(i.e., the cluster pairs which have the minimum distance value) are merged into a single one.
(c) The above step(b) is repeated until the minimum distance value between any two clusters falls larger thanthe user-determined threshold or all of clusters are
merged into a single one.

Figure 5: Example of co-occurrence matrix (createdfrom Figure 4)

ia
0
ia
−
ib B 0.30
B
ic B 0.43
id @ 0ie 0.43

ib
0.30
−
0.67
0.30
0.17

ic
0.43
0.67
−
0.43
0.30

id
0
0.30
0.43
−
0.67

After the clustering, an identiﬁer involved in a resulting
cluster is called a synonym of other identiﬁers in the samecluster.
Figure 7 shows the clustering process for the distancematrix in Figure 6. In this example, we assume that theclustering threshold value is 0.30. At ﬁrst, the initial clusters are created for each identiﬁer (Figure7(a)). Then, the

ie
1
0.43
0.17 CC
0.30 C
0.67 A−

1
When two identiﬁer-clusters are given, the group averagemethod obtains the distance value by calculating the average
distance between each pairing of identiﬁers across the twoclusters.

Figure 6: Example of distance matrix

51

Clusteraiaia

Clusterb

ib

ib

Merge
(distance: 0)

distance:
0.43

id

Clusterb

Clusterc

Clusterad

Clusteradid

Clusterbe
ib

ic

distance: 0.49

ic

Merge
(distance: 0.17)

Clusterd

distance: 0.43

ie

Clusterc

Clusterc

ic

ia

id

Clustere

Clustereieie(a) Initial clusters are created(c) Clusterb and Clustere
are merged into Clusterbe(b) Clustera and Clusterd
are merged into Clusterad
Figure 7: Identiﬁer Clusteringclosest pair (Clustera , Clusterd ) is merged into Clusterad(Figure7(b)). Next, the closest pair (Clusterb , Clustere ) is
merged into Clusterbe (Figure7(c)). Here, since the smallest
distance between any two clusters is 0.43 and is larger thanthe clustering threshold 0.30, so the clustering is terminated.
As a result, we determine that ia and id are synonyms eachother, and also ib and ie are synonyms each other.

SC-Retriever performs the detection of C-language function as the code fragment. That is, it retrieves similar functions that are similar to a query code fragment. The advantage of function-wise detection is that developers can easily
spot the defective code portion, and also that partitioning
the target source ﬁles into functions is quite easy.
Also, in order to ﬁt function-wise detection, we employ
functions as the structural units described in Section 2.1.

2.3 Retrieval with Query Code Fragment
In this section, we describe similar code fragment obtainedby the retrieval.
First, we introduce correspondence of identiﬁer as follows.

3.

Deﬁnition 2.1 (Identiﬁer Correspondence) When two
identiﬁers ix and iy are given, if iy is identical or synonymous to ix , we say that iy corresponds to ix (and vice versa).
Now, we deﬁne similar code fragment as follows.
Deﬁnition 2.2 (Similar Code Fragment) We assume thata query code fragment Q and a target code fragment T involve at least one identiﬁer, respectively. Here, if each identiﬁer in Q corresponds to at least one identiﬁer in T , thenT is said similar code fragment to Q.
Figure8 illustrates an example
of comparing the identiﬁerˆ˜list host, alloc, add, host derived from a query code fragˆ
˜
ment and the identiﬁer list node, . . . , alloc, add, . . . , node
derived from a target code fragment. The edge is drawn
when two identiﬁers correspond, i.e, they are identical or
they are in synonym relations. In this case, each identiﬁer in the query code fragment corresponds to at least one
synonymous identiﬁer in the target code fragment. Therefore, we say that the target code fragment is a similar codefragment to the query code fragment (and vice versa).

CASE STUDIES

We have conducted case studies with two tools: (1) SCRetriever, (2) a code clone detection tool CCFinder. Using
these tools, we have retrieved defective functions in two software systems with their defect data, and eﬃciency of theretrieval has been compared.
CCFinder is a fast and scalable code clone detection tool[11]. It generally gets a collection of source code as the
input and generate the report of the locations of code clone
fragments. CCFinder can also report the locations of codefragments for a speciﬁc query code fragments [9]. In thecase study, we use the latter feature to locate the defectivefunctions.

3.1
3.1.1

Experiment
Measures of Retrieval Efﬁciency

We used precision, recall and F-measure as the measuresof retrieval eﬃciency. Let D denote the set of defective codefragments determined by the bug records of the softwaresystem. Also, R denotes the set of retrieved code fragments
by any of the tools. We deﬁne the precision, recall and F-

2.4 Implementation of SC-Retriever
We have developed SC-Retriever (Similar Code Retriever)
implementing the proposed method.

52

host

Identifiers list from a query code fragment
Identifiers list from a target code fragmentwith the normalization and synonym extension(Identifiers in the bracket aresynonyms of identifiers from the query)(node)

alloc

add

alloc

add

host

(node)

Figure 8: Comparison between a query code fragment and a target code fragment (The arrow is drawn fromeach identiﬁer to its corresponding identiﬁers.)

Table 1: Statistics of target programs# offunctions
2361
859

LOC
Canna
SPARS-J

90K
36K# of defectivefunctions
18
50

# of
defects
19
75

measure as follows.
P recision =Recall=F=|D ∩ R||R||D ∩ R||D|
2 · P recision · Recall
P recision + Recall(1)

buf += HEADER_SIZE;
Request.type2.context = S2TOS(buf);(a) Query Code fragment CA (small code fragment)
buf += HEADER_SIZE;
Request.type18.context = S2TOS(buf);
buf += SIZEOFSHORT;
Request.type18.data = (char *)buf;
buf += Request.type18.datalen - SIZEOFSHORT * 2;
Request.type18.size = S2TOS(buf);(b) Query Code fragment CB (large code fragment)
buf += SIZEOFINT;
Request.type10.kouho = (short *)buf;for (i = 0; i < Request.type10.number; i++) {Request.type10.kouho[i] = S2TOS(buf);
buf += SIZEOFSHORT;
ir_debug(Dmsg(10, "req->kouho =%d\n",Request.type10.kouho[i]));}(c) Query Code fragment CC (complicated code fragment)

(2)
(3)

3.1.2 Experimental Step
Our case studies are composed of the following steps.
1. We choose defective code fragments from target source
ﬁles, based on the criteria described later.

Figure 9: Query code fragments for Canna 3.6

2. Using SC-Retriever, and CCFinder, we retrieve functions in the target source ﬁles. In the case of SCRetriever, we give the chosen code fragment as thequery. Also, in the case of CCFinder, we detect thecode clones for the chosen code fragments. The granularity of the code fragments as the output of thoseretrieval is set to function level here due to the implementation constraint mentioned in Section 2.4.

From these defects reported by the bug records, we haveselected three types of the query code fragments:

3. We calculate the precision, recall and F-measure withthe retrieved results and the bug records.

B. Large code fragments (CB for Canna, and SB for SPARSJ)

3.1.4

Query Code Fragments

A. Small code fragments (CA for Canna, and SA for SPARSJ)

3.1.3 Target Software Systems

C. Complicated code fragments (CC for Canna, and SC forSPARS-J)

We applied SC-Retriever, and CCFinder to o two diﬀerent
software systems. Table 1 gives statistics relating to these
two systems.
Canna [3] is an open source client-server Japanese character input system. Canna Ver. 3.6 involves 19 buﬀer overﬂow
defects, and those defects exist in 18 functions.
SPARS-J is Java component retrieval system [19]. The target version of SPARS-J involves 75 defects caused by missing
typecast operations2 , and those defects exist in 50 functions.

Figure 9 and Figure 10 show the selected query code fragments for the case studies of Canna and SPARS-J, respectively.
These code fragments would be considered typical in thatthey contain suﬃcient code related to the faulty operations
while avoiding inclusion of code not related to the faulty
operations. We are interested in the distinction of fragment
sizes which might aﬀect the retrieval eﬃciency, and also weare interested in the eﬀect of the code complexity. We willfurther discuss the requirement and characteristics of thequery code fragment in Section 4.

2
In the source ﬁles implementing the process of software
component registration, there are 75 defects caused by lackof typecasting from the internal data types into the types
supported by the relational database of SPARS-J.

53

statements to the query fragments. However, it presents
very low recalls for CB and CC . Since the retrieval results
are very sensitive to the query code fragments, we have tochoose them very carefully.
Table 2 shows also the eﬀectiveness of the retrieve for three
diﬀerence threshold ratios. As you see, thr = 0.10 generallyshows better F-values than thr = 0.05 and thr = 0.15. If
we would choosing thr = 0.05, the F-value for CA is better,but for cases CB and CC , we get very low F-values. Also,
we would get very low F-value 0.20 for all the cases with
thr = 0.15. Therefore, we think that using thr = 0.10 would
be a reasonable choice.

package_name_length = p - class_name;//should be: = (int)(p - class_name);(a) Query Code fragment SA (small code fragment)
ret->mm_attachments =mime_parsemultipart(bdlc + 1,
len - (bdlc + 1 - msg),//should be: (int) (len - (bdlc + 1 - msg),
bd, &ret->mm_nattachments,&pos, crlfpair);(b) Query Code fragment SB (large code fragment)
pos +=(((char *)((i = memchr(map + pos,// should be: (int) (((char *)((i = memchr(...
’$’, len - pos - 1))? i : map + len))- ((char *)map + pos));(c) Query Code fragment SC (complicated code fragment)

3.3

Figure 10: Query code fragments for SPARS-J

buf += HEADER_SIZE;
Request.type17.dicname = (char *)buf;
Request.type17.mode =(char)*(buf + Request.type17.datalen- SIZEOFCHAR) ;Request.type17.datalen - SIZEOFCHAR) ;Figure 11: Defective code fragment that SC-Retriever
was unable to ﬁnd in Canna

3.1.5 Clustering Threshold
As described before, the identiﬁer clustering is repeateduntil the distance of any two clusters becomes greater than
the threshold value thv . Since the distances of two clusters
changes case by case, then it is fairly diﬃcult to determine
a preﬁxed thv used for any purpose. Instead, we introduce
the threshold ratio thr which deﬁnes thv from the maximum
distance dmax of any two identiﬁers in the target source ﬁles,as follows.
thv = thr · dmax

Experimental Results of SPARS-J

Table 3 shows the results of SPARS-J’s case study. We
also present the result with thr = 0.10 for SC-Retriever here.
In most cases, the precision and recall values in the resultsof SPARS-J were worse than those values in the results ofCanna. We believe that the primary cause is that the defects(missing typecast operations) spread across various kinds of
implementations in the system. In fact, various identiﬁers
are used in the code fragments sharing such defects.
CCFinder shows very good precision and recall for CA .
This means that all the faulty code fragments contain similarstatements to the query fragments. However, it presents
very low recalls for CB and CC . Since the retrieval results
are very sensitive to the query code fragments, we have tochoose them very carefully.
Table 3 shows also the results of SPARS-J with three
threshold ratios. We would think that both threshold ratios thr = 0.10 and thr = 0.15 are promising. If developers
emphasize the precision, an appropriate ratio is thr = 0.10.
Conversely, if developers emphasize the recall, an appropriate ratio is thr = 0.15.
When we set the threshold ratio to thr = 0.05, the retrieval results include almost only the function involving thequery code fragment.

4.

DISCUSSION AND RELATED WORKS

4.1

Effectiveness of SC-Retriever

According to Table 2 and Table 3, SC-Retriever shows relatively better F-values than CCFinder for most cases. In thecases of small code fragments CA and SA , CCFinder shows
better F-values than SC-Retriever. However, it presents very
low recalls for both large and complicated code fragments.
Current implementation of SC-Retriever is a prototype system, and we did not consider its performance seriously. It
takes about 40 minutes on a PC workstation for the wholeprocess of Canna’s case. Most part of this execution time
is for the clustering process, which can be performed only
once before any retrieval. The resulting synonym information can be repeatedly used for later retrievals. We consider
that this clustering process would be further optimized andparallelized for the better performance. For the retrieval
process, we have employed a simple matching algorithm. Its
performance can be also improved greatly if we would use ahash method such as Locality Sensitive Hashing (LSH) [5].
These implementation techniques will further strengthen theadvantages of our approach.

(4)

By introducing the threshold ratio, the eﬀect of the distribution of identiﬁcation distances is complemented. We will use
three threshold ratios thr = 0.05, thr = 0.10, thr = 0.15,
and see the distinction of resulting synonyms.

3.2 Experimental Results of Canna
Table 2 shows the result of Canna’s case study. We present
the result with thr = 0.1 for SC-Retriever here. We would
say that SC-Retriever shows better F-values than CCFinder
for most cases. SC-Retriever has fairly high precision 0.63
for all the cases of CA , CB , and CC , and also has near
perfect recall, 0.94 for all the cases. The only defective codefragment that SC-Retriever was unable to ﬁnd is presented
in Figure 11. In this case, S2T OS is the key identiﬁer ofthe mismatch, which occurs in all of CA , CB , and CC , but
S2TOS and its synonyms (e.g., L4TOL) do not occur in the
fragment of Figure 11 at all.
CCFinder shows very good precision and recall for CA .
This means that all the faulty code fragments contain similar

4.2

54

Comparison with CCFinder

CA
CB
CC

SC-Retriever w/thr = 0.05
precision recall F-value
1.00
0.94
0.97
1.00
0.06
0.11
1.00
0.06
0.11

Table 2: Results of Canna
SC-Retriever w/thr = 0.10
SC-Retriever w/thr = 0.15
precision recall F-value precision recall F-value
0.63
0.94
0.75
0.11
0.94
0.20
0.63
0.94
0.75
0.11
0.94
0.20
0.63
0.94
0.75
0.11
0.94
0.20

precision
1.00
1.00
1.00

CCFinderrecall F-value
0.94
0.97
0.06
0.11
0.06
0.11

SA
SB
SC

SC-Retriever w/thr = 0.05
precision recall F-value
0.66
0.04
0.08
1.00
0.02
0.04
1.00
0.02
0.04

Table 3: Results of SPARS-J
SC-Retriever w/thr = 0.10
SC-Retriever w/thr = 0.15
precision recall F-value precision recall F-value
0.10
0.18
0.13
0.09
0.30
0.14
0.44
0.08
0.14
0.08
0.38
0.13
0.66
0.04
0.08
0.50
0.04
0.07

precision
0.46
1.00
1.00

CCFinderrecall F-value
0.12
0.19
0.02
0.04
0.02
0.04

ing diﬀerent code fragments for the query would aﬀect the
retrieve results. However, as mentioned in Section 3.1.4, wehave chosen code fragments to intend that all bug-related
statements are covered and non-related statements are excluded as much. We guess that this policy will produce
similar results for other query code fragments.

SC-Retriever showed the better eﬃciency than CCFinder inmany cases, but for the small code fragment cases, CCFinder
outperforms SC-Retriever. This suggests that when we needto retrieve code fragments with some a speciﬁc code pattern,
CCFinder is a better choice. On the other hand, if we areunsure of the defective code pattern, SC-Retriever will be theﬁrst choice.
As we will discuss in Section 4.4.1, we would use othercode clone tools with diﬀerence clone detection algorithms.
Some of those tools may allow more ﬂexibility of code structure distinction, but such ﬂexibility would not be much as
given by SC-Retriever.

4.4
4.4.1

Related Works
Code Clone Detection Techniques

So far, a lot of techniques have been developed on code
clone detection [1, 2, 6, 7, 10, 11, 12, 13, 15, 18]. Severalof them are token-based detection techniques [1, 6, 11], andthey are very scalable in terms of time and space complexity.
We have used a token-based detection tool CCFinder [11] forthe case studies.
Tree-based and semantic-based techniques have been also
devised [2, 10]. Jiang et al. have developed an abstract syntax tree (AST) based code clone detection tool DECKARD[10]. It can treat a pair of code fragments as a code clone
when their syntax elements are the same (even if their AST
structures are slightly diﬀerent). Semantic-based techniques
identify code clones using program dependence graphs [7, 12,
13].
Code clone detection tools ﬁnd only structurally similarcode fragments. On the other hand, our method retrieves
similar fragments based on the correspondence of identiﬁers;
thus the retrieved results might not be structurally similar.
This would be a major beneﬁt of our approach for the casesof the retrievals for unknown structured patterns, such as
the case study for SPARS-J where we sought missing type
cast operations.

4.3 Threshold and Fragment
For the determination of the clustering termination, we
have used the threshold value and threshold ratio. We haveinvestigates several threshold ratios and found that threshold ratio 0.10 would be appropriate for our case studies. We
have to further investigate the better threshold ratios which
can be used for various cases. Also, we would explore othermethods to terminate the cluster merging process, such asones using cluster sizes or so.
Granularity of code fragments in the retrieval is an important factor in our approach. We have used a C-language
function as the structured unit of the synonym determination process. We can consider other granularity for this purpose, such as a block. If the single structured unit becomes
smaller, the probability of co-occurring two identiﬁers in thesame structured unit generally decreases, generating fewer
synonyms for each identiﬁer. This would increase the precision, but reduce the recall greatly. We think that the current
choice would be a practical compromise.
Also, we have used a function for the retrieved code fragments as the outputs. This simpliﬁed the implementationof SC-Retriever greatly. We would consider other granularities such as a block as the output, which would reduce theoverhead of focusing defective code portions in a function.
However, without using such ﬁne-grained retrieval methods,
we are able to locate the defective portions eﬀectively if theidentiﬁers corresponding to the query identiﬁers are highlighted in the SC-Retriever output. We will improve SCRetriever in this way.
In the case studies, we have used three types of querycode fragments from the bug records of the systems. Choos-

4.4.2

Defect Detection Techniques

Li et al. proposed a tool named PR-Miner [16]. It extracts frequently occurring pattern of variable and function
names from source code based on frequent item-set mining,then detects the violations of detected patterns. It ﬁnallyprovides code fragments involving such violations as defectcandidates. Also, Li et al. showed identiﬁer naming inconsistencies among code clones of the Linux kernel as thedefect candidates [15].
We believe that by giving SC-Retriever those defect candidates, we can detect more defects that Li’s methods cannot55

[12] R. Komondoor and S. Horwitz. Using slicing to
identify duplication in source code. In Proc. of SAS
2001, pages 40–56, 2001.
[13] J. Krinke. Identifying similar code with program
dependence graphs. In Proc. of WCRE 2001, pages
301–309, 2001.
[14] B. Laguë, D. Proulx, J. Mayrand, E. M. Merlo, andJ. Hudepohl. Assessing the beneﬁts of incorporating
function clone detection in a development process. In
Proc. of ICSM ’97, pages 314–321, 1997.
[15] Z. Li, S. Lu, S. Myagmar, and Y. Zhou. CP-Miner:
Finding copy-paste and related bugs in large-scale
software code. IEEE Trans. Softw. Eng.,32(3):176–192, 2006.
[16] Z. Li and Y. Zhou. PR-Miner: Automaticallyextracting implicit programming rules and detecting
violations in large software code. In Proc. of
ESEC/FSE 2005, pages 306–315, 2005.
[17] J. Lin. Divergence measures based on the shannon
entropy. IEEE Trans. Inf. Theory, 37(1):145–151,
1991.
[18] J. Mayland, C. Leblanc, and E. M. Merlo. Experimenton the automatic detection of function clones in asoftware system using metrics. In Proc. of ICSM ’96,
pages 244–253, 1996.
[19] SPARS Project. http://spars.info/SPARS/.
[20] M. Williams. Systems glitch hits hundreds of Tokyo
stations. washingtonpost.com, 2007.
http://www.washingtonpost.com/wp-dyn/content/
article/2007/10/12/AR2007101200865_pf.html.
[21] T. Yamashina, H. Uwano, K. Fushida, Y. Kamei,
M. Nagura, S. Kawaguchi, and H. Iida. SHINOBI: A
real-time code clone detection tool for software
maintenance. Technical Report NAIST-IS-TR2008005,
Nara Institute of Science and Technology, 2008.
http://isw3.naist.jp/IS/TechReport/report/
2008005.pdf.
[22] A. Zeller. Why Programs Fail. Morgan Kaufmann
Pub., 2005.

detect.

5. CONCLUSION
We have proposed a method for retrieving similar codefragments to a query code fragment. The proposed method
can provide not only code fragments which share all identiﬁers with a query code fragment, but also code fragments
which involve all identical or synonymous identiﬁers.
In the case studies, we have applied SC-Retriever to thesource ﬁles of Canna and SPARS-J, together with CCFinder
for the purpose of comparing the retrieval eﬃciency. In mostcases, the SC-Retriever outperforms CCFinder in the retrievaleﬃciency.

Acknowledgments
We express our great thanks to Mr. Akihiko Matsuo and
Mr. Kenichi Kobayashi of Fujitsu Laboratory for their discussions of SC-Retriever. We also thank Dr. Daniel Germanof the University of Victoria, Dr. Ian Davis of the Universityof Waterloo, and Dr. Stan Jarzabek of the National University of Singapore for helpful comments on earlier revisionsof this paper.
This work is being conducted as a part of Stage Project.
Also, this work is partially supported by JSPS, Grant-in-Aid
for Scientiﬁc Research (A) (21240002) .

6. REFERENCES[1] B. S. Baker. Finding clones with Dup: Analysis of anexperiment. IEEE Trans. Softw. Eng., 33(9):608–621,
2007.
[2] I. D. Baxter, A. Yahin, L. Moura, M. S. Anna, and
L. Bier. Clone detection using abstract syntax trees.
In Proc. of ICSM ’98, pages 368–377, 1998.
[3] Canna. http://canna.sourceforge.jp.
[4] I. Dagan, L. Lee, and F. C. N. Pereira.
Similarity-based models of word cooccurrence
probabilities. Machine Learning, 34(1-3):43–69, 1999.
[5] M. Datar, N. Immorlica, P. Indyk, and V. S. Mirrokni.
Locality-sensitive hashing scheme based on p-stable
distributions. In Proc. of SCG 2004, pages 253–262,
2004.
[6] S. Ducasse, M. Rieger, and S. Demeyer. A language
independent approach for detecting duplicated code.
In Proc. of ICSM ’99, pages 109–118, 1999.
[7] M. Gabel, L. Jiang, and Z. Su. Scalable detection ofsemantic clones. In Proc. of ICSE 2008, pages
321–330, 2008.
[8] GNU grep. http://www.gnu.org/software/grep/.
[9] Y. Higo, Y. Ueda, S. Kusumoto, and K. Inoue.
Simultaneous modiﬁcation support based on code
clone analysis. In Proc. of APSEC 2007, pages
262–269, 2007.
[10] L. Jiang, G. Misherghi, Z. Su, and S. Glondu.
DECKARD: Scalable and accurate tree-based
detection of code clones. In Proc. of ICSE 2007, pages
96–105, 2007.
[11] T. Kamiya, S. Kusumoto, and K. Inoue. CCFinder: A
multilinguistic token-based code clone detection
system for large scale source code. IEEE Trans. Softw.
Eng., 28(7):654–670, 2002.

56