Retrieving Similar Code Fragments based on Identiﬁer
Similarity for Defect Detection
Norihiro Yoshida, Takashi Ishio, Makoto Matsushita, Katsuro Inoue
Graduate School of Information Science and Technorogy, Osaka University
1-3, Machikaneyama-cho, Toyonaka, Osaka, 560-8531, Japan{n-yosida, ishio, matusita, inoue}@ist.osaka-u.ac.jp
ABSTRACT(linux-2.6.6/arch/sparc64/prom/memory.c)
111 for(iter=0; iter<num_regs; iter++) {112 prom_prom_taken[iter].start_adr =113
prom_reg_memlist[iter].phys_addr;
114 prom_prom_taken[iter].num_bytes =115
prom_reg_memlist[iter].reg_size;
116 prom_prom_taken[iter].theres_more =117&prom_phys_total[iter+1];// should be:&prom_prom_taken[iter+1];
118 }Similar source code fragments, known as code clones, may
involve similar defects caused by the same mistake. However, code clone detection tools cannot detect certain codefragments (e.g. modiﬁed after copy-and-pasted). To support
developers who would like to detect such defects, we propose
a method to retrieve similar code fragments in source code
based on the similarity of identiﬁers between a query and atarget code fragment. We present two case studies of similar
defects in open source systems.

(linux-2.6.6/arch/sparc/prom/memory.c)
153 for(iter=0; iter<num_regs; iter++) {154
prom_prom_taken[iter].start_adr =155(char *) prom_reg_memlist[iter].phys_addr;
156
prom_prom_taken[iter].num_bytes =157(unsigned long) prom_reg_memlist[iter].reg_size;158
prom_prom_taken[iter].theres_more =159&prom_phys_total[iter+1];// should be:&prom_prom_taken[iter+1];
160 }Categories 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

Figure 1: Similar defects

General Terms
Algorithms, Experimentation

1. INTRODUCTION
Similar code is generally considered as one of factors thatmake software maintenance more diﬃcult[1, 2, 4]. If developers modify one of similar code fragments, they have todetermine whether or not to apply the same modiﬁcation tothe others. Similar code is also called code clone or duplicated code. Developers often introduce similar code becauseof various reasons (e.g. “copy-and-paste”)[2, 5]. Especially,large-scale software systems, such as Linux and JDK(JavaDevelopment Kit), often involves a large number of similarcode fragments[4].
Similar code fragments sometimes involve similar defects
caused by the same mistake[6, 7]. Therefore, if one of similar code fragments has a defect, developers have to inspect
the others. Figure 1 is an example of such code fragmentsin Linux 2.6.6. The two fragments involve similar defects
caused by accessing incorrect pointer (i.e. &prom phys total).

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 proﬁt or commercial advantage and that copies
bear this notice and the full citation on the ﬁrst page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior speciﬁc
permission and/or a fee.
DEFECTS’08, July 20, 2008, Seattle, Washington, USA.
Copyright 2008 ACM 978-1-60558-051-7/08/07 ...$5.00.

Because type cast operations (e.g. (char *)) are inserted into
the lower fragment, code clone detection tools[1, 2, 4] do nottreat the code fragments as a pair of code clones. Hence,even if developers ﬁnd out that one of the code fragments
has a defect and perform code clone detection, they cannot
detect the other code fragment that has the similar defect.
To detect such similar code fragments involving similar
defects, we propose a new approach that retrieves code fragments similar to a query code fragment. Our approach compares a set of identiﬁers in a query with sets of identiﬁers intarget source code fragments.

2.

PROPOSED METHODAs shown in Figure 2, our method accepts a code fragment
as a query and retrieves similar code fragments in target
source ﬁles. The process comprises three steps as follows.
(1)Lexical Analysis Both the input code fragment andthe target source ﬁles are translated into token sequences. Then, only identiﬁers are extracted from eachtoken sequence. Finally, those identiﬁers are normalized based on several rules (e.g. dividing at underscore,number suﬃx elimination) and are listed as IdentiﬁerLists.
(2)Comparison We compare the input identiﬁer list with
sublists in the target identiﬁer lists. We compute thesimilarity for each sublist and extract Similar Sublists.

41

Input code fragment (Query)CFi

f1

are ranked higher in the result. Since the ranking involves ahuge number of code fragments, developers may investigate
similar code fragments according to their resource.

Target source files
fnf23.

Proposed
Lexical Analysis
methodLexical Analysis

We performed two case studies of software systems, Linux2.6.6 and Canna 3.6[3]. At ﬁrst, we extracted code fragments
sharing similar defects from a software system and enteredeach code fragment into the tool implementing our method.
Then, we manually inspected if the similarity ranking ranks
highly code fragments involving defects.
The arch directory of Linux 2.6.6 has two similar defects(see Figure 1). We used the two code fragments as queries
and then retrieved similar code fragments to each of themin the arch directory. As a result, in both of those queries,
the two code fragments in Figure 1 are detected as the top
two code fragments in the similarity ranking. If one of thosecode fragments is given, we can detect the other one having
similar defect.
The server directory of Canna 3.6 has 19 buﬀer overﬂow
errors. Like the case of Linux, we used the 19 code fragments
as queries and then retrieved similar code fragments in theserver directory. As a result, in all of those queries, 18 or 19
queried code fragments are ranked in the top 30. If one ofthose code fragments is given, we can detect the almost theother code fragments having similar defect.

Target identifier lists
Input identifier list
Li

Ii[0]

Ii[1]

Ii[ni]

Lt1
Lt2

It1[0]

It1[1]

It1[n t1]

It2[0]

It2[1]

It2[n t2]

Ltn

It2[0]

It2[1]

It2[n t2]Comparison
Similar sublists
Ls1

Is1[0]

Is1[1]

Is1[ns1]

Ls2

Is2[0]

Is2[1]

Is2[ns2]

Ranking
Similarity Ranking
Rank

Start line #End line #Similarity

1Lines1

Linee1Sim 1

2

Lines2Linee2Sim 2

Figure 2: The overview of proposed method

Input identifier list LiTarget identifier list Lt

Ii[0]

It[0]

Ii[1]

It[1]

4.

Ii[2]

It[2]

It[3]

CASE STUDYCONCLUSION

In this paper, we proposed a method to retrieve similarcode fragments based on identiﬁer similarity. In the casestudies, by providing a code fragment having a defect, we
could detect most of similar defects. We need further casestudies on other software systems having similar defects.

It[n]Sliding Window
The direction of movementof the sliding window

Acknowledgments
Figure 3: Sliding window

This reseach was supported by JSPS, Grant-in-Aid for Scientiﬁc Research (A) (No.17200001) and Grant-in-Aid for JSPS
Fellows (No.20-1964).

The detail of this step is described later.

5.

(3)Ranking The extracted similar sublists are sorted according to the similarity value. The resultant ranking
is the output of our method. We call the ranking Similarity Ranking.
Figure 3 shows the comparison between an input identiﬁer list and a target identiﬁer list. We call the scope ofcomparison Sliding Window, and it moves through the target identiﬁer list. To reduce computational cost, we ﬁx thelength of the sliding window to the length of the input identiﬁer list. Hence, the length of a similar sublist is ﬁxed to
the length of the input identiﬁer list.
The deﬁnition of the similarity in our method is shown inEquation 1. Let Si be a set of elements in input identiﬁer list
Li , Sw be a set of elements in the sliding window. Then wedeﬁne the similarity in our method as Similarity(Si , Sw ):Similarity(Si , Sw ) =2 ∗ |Si ∩ Sw ||Si | + |Sw |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] 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.
[5] M. Kim, L. Bergman, T. Lau, and D. Notkin. An
ethnographic study of copy and paste programming
practices in OOPL. In Proc. of ISESE 2004, pages
83–92, 2004.
[6] B. Laguë, D. Proulx, J. Mayrand, E. M. Merlo, andJ. Hudepohl. Assessing the beneﬁts of incorporating
function clone detection in a development process. InProc. of ICSM ’97, pages 314–321, 1997.
[7] A. Zeller. Why Programs Fail. Morgan Kaufmann Pub.,
2005.

(1)

In the ranking step, since similar sublists are ranked using the similarity score described above, the code fragments
which share more identiﬁers with the input code fragment

42