ࣾஂ๏ਓ ిࢠ৘ใ௨৴ֶձ
THE INSTITUTE OF ELECTRONICS,
INFORMATION AND COMMUNICATION ENGINEERS৴ֶٕใTECHNICAL REPORT OF IEICE.

ܽؕͷಉ࣌मਖ਼ࢧԉʹ͓͚Δؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧͷ༗ޮੑௐࠪ
পా

੟໵†

٢ా

ଇ༟††

ቐ

Ըಬ††† Ҫ্ࠀ࿠†† େࡕେֶେֶӃ৘ใՊֶ‫ڀݚ‬Պ ˟ 565–0871 େࡕ෎ਧాࢢࢁాٰ 1–5†† ໊‫ݹ‬԰େֶେֶӃ৘ใՊֶ‫ڀݚ‬Պ ˟ 464–8601 ໊‫ݹ‬԰ࢢઍछ۠ෆ࿝ொ
††† ಸྑઌ୺ٕज़େֶӃେֶ৘ใՊֶ‫ڀݚ‬Պ ˟ 630–0192 ಸྑ‫ݝ‬ੜۨࢢߴࢁொ 8916-5
E-mail: †{s-numata,inoue}@ist.osaka-u.ac.jp, ††yoshida@ertl.jp, †††choi@is.naist.jp͋Β·͠ίʔυΫϩʔϯ (ιʔείʔυதʹଘࡏ͢ΔಉҰ·ͨ͸ྨࣅͨ͠෦෼Λ࣋ͭίʔυย) ͷଘࡏ͸ɼιϑτ΢ΣΞอकΛࠔ೉ʹ͢Δେ͖ͳཁҼͱͳΔɽ։ൃऀ͸ίʔυΫϩʔϯʹ͕ܽؕ‫͔ͨͬͭݟ‬৔߹ɼಉҰΫϩʔϯηοτ(‫ʹ͍ޓ‬ίʔυΫϩʔϯͱͳ͍ͬͯΔίʔυยͷू߹) ಺ʹ‫·ؚ‬ΕΔશͯͷίʔυΫϩʔϯʹରͯ͠ಉҰͷमਖ਼Λ͢Δ͔‫ݕ‬౼͢Δඞཁ͕͋Δɽຊ‫Ͱڀݚ‬͸ɼ৘ใ‫ٕࡧݕ‬ज़ʹ‫਺͍ؔͯͮج‬୯ҐͷίʔυΫϩʔϯΛ‫ݕ‬ग़͢Δπʔϧʹରͯ͠ɼܽؕΛ‫ؚ‬ΉίʔυยͷίʔυΫϩʔϯΛ‫ݕ‬ग़Ͱ͖Δ͔ධՁ͠༗ޮੑΛௐࠪͨ͠ɽͦͷ݁Ռɼؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧ͸ߴ͍ద߹཰Λදͨ͠ɽΩʔϫʔυίʔυΫϩʔϯɼιϑτ΢ΣΞอकɼؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧɼ৘ใ‫ٕࡧݕ‬ज़Investigating the eﬀectiveness of function clone detection tool for simultaneousﬁxing of defects
Seiya NUMATA† , Norihiro YOSHIDA†† , Eunjong CHOI††† , and Katsuro INOUE†† Graduate School of Information Science and Technology, Osaka University 1–5, Yamadaoka, Suita,
Osaka, 565–0871, Japan†† Graduate School of Information Science, Nagoya University Furo-cho, Chikusa-ku, Nagoya, 464-8601,
Japan††† Graduate School of Information Science, Nara Institute of Science and Technology 8916–5, Takayama,
Ikoma, Nara, 630–0192,Japan
E-mail: †{s-numata,inoue}@ist.osaka-u.ac.jp, ††yoshida@ertl.jp, †††choi@is.naist.jp
Abstract Code clone (i.e., code fragment that has identical or similar fragments in source code) is one of thefactors that makes software maintenance more diﬃcult. Once a developer ﬁnds a defect in a code fragment, he/she
has to inspect the all of the code clones of the code fragment. In this study, we investigated the eﬀectiveness ofan IR-based function clone detection tool for detecting code clones that include defects, and then conﬁrmed highprecision of the tool.
Key words Code clone, Software Maintenance, Function clone detection tool, Information retrieval technique

1. · ͑ ͕ ͖৔߹ɼͦͷίʔυยͷίʔυΫϩʔϯʹ΋ಉ༷ͷ͕ܽؕ‫·ؚ‬ΕΔՄೳੑ͕ߴ͍ [17]ɽͦͷͨΊɼ։ൃऀ͸ίʔυΫϩʔϯʹܽίʔυΫϩʔϯͱ͸ɼιʔείʔυதʹଘࡏ͢ΔಉҰɼ͋Δ͍

͕ؕ‫͔ͨͬͭݟ‬৔߹ɼಉҰΫϩʔϯηοτʢ‫ʹ͍ޓ‬ίʔυΫϩʔ͸ྨࣅͨ͠෦෼Λ࣋ͭίʔυยΛҙຯ͠ɼओʹ‫ط‬ଘͷίʔυยϯͱͳ͍ͬͯΔίʔυยͷू߹ʣ಺ʹ‫·ؚ‬ΕΔશͯͷίʔυΫͷίϐʔΞϯυϖʔετʹΑͬͯੜ੒͞ΕΔ [3] [4] [5] [10] [13]ɽ

ϩʔϯରͯ͠ಉ༷ͷमਖ਼Λ͢Δ͔‫ݕ‬౼͢Δඞཁ͕͋Δ͕ɼ͢΂ίʔυΫϩʔϯͷଘࡏ͸ɼιϑτ΢ΣΞอकΛࠔ೉ʹ͍ͯ͠Δ

ͯͷίʔυΫϩʔϯΛ։ൃऀ͕ख࡞‫͚ͯͭݟͰۀ‬؅ཧ͢Δͷ͸େ͖ͳཁҼͷ 1 ͭͱͯ͠‫͛ڍ‬ΒΕ͍ͯΔɽ

ࠔ೉Ͱ͋Δɽͦ͜Ͱɼ։ൃऀΛࢧԉ͢ΔͨΊʹίʔυΫϩʔϯɹίʔυΫϩʔϯʹର͢Δอक࡞‫ۀ‬ͷ 1 ͭͱͯ͠ɼಉ࣌मਖ਼͕

‫ݕ‬ग़πʔϧ͕ར༻͞ΕΔ [9]ɽ‫͛ڍ‬ΒΕΔ [6] [11]ɽྫ͑͹ɼ͋Δίʔυยʹ͕ܽؕ‫͔ͨͬͭݟ‬ɹࢁதΒ͸ɼ৘ใ‫ٕࡧݕ‬ज़ʹ‫਺͍ؔͯͮج‬୯ҐͷίʔυΫϩʔ—1—ϯΛ‫ݕ‬ग़͢ΔπʔϧʢҎ߱ɺؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧͱ‫Ϳݺ‬ʣ໊ɼؔ਺ͷ‫͕Ͳͳܕ‬ҟͳΔ.

Λ։ൃͨ͠ [19]ɽ͔͠͠ɼؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧ͸ɼؔ਺୯λΠϓ 3ҐͷίʔυΫϩʔϯͷ‫ݕ‬ग़ਫ਼౓΍‫ݕ‬ग़࣌ؒʹରͯ͠ͷධՁ͸͞Ͳ͕ߦΘΕ͍ͯΔɽΕ͍ͯΔ͕ɼܽؕͷಉ࣌मਖ਼ࢧԉʹ͓͚Δ༗ޮੑʹ͍ͭͯ͸λΠϓ 4ධՁ͞Ε͍ͯͳ͍ɽͦ͜Ͱɼຊ࿦จͰ͸ܽؕͷಉ࣌मਖ਼ର৅ͷλΠϓ 4 ͷίʔυΫϩʔϯͱͯ͠͸ɼҎԼͷ΋ͷ͕‫͛ڍ‬ΒΕΔɽ

λΠϓ 2 ͷҧ͍ʹՃ͑ͯɼจͷૠೖ΍࡟আɼมߋͳ
ྨࣅͨ͠ॲཧΛ࣮ߦ͢Δ͕ɼߏจ্ͷ࣮૷͕ҟͳΔɽ

৚݅෼‫ॲذ‬ཧ΍‫܁‬ฦ͠ॲཧͳͲͷ੍‫ߏޚ‬଄ͷ࣮૷͕ҟίʔυΫϩʔϯ‫ݕ‬ग़ʹ͓͚Δؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧͷ༗ޮੑ•Λௐࠪͨ͠ɽಉ࣌मਖ਼ର৅ͷίʔυΫϩʔϯΛ‫ݕ‬ग़͢Δ͜ͱʹͳΔɽΑΓɼ։ൃऀͷίʔυΫϩʔϯͷಉ࣌मਖ਼࡞‫ۀ‬ͷࢧԉ͕Ͱ͖•தؒഔհม਺ͷར༻ͷ༗ແ͕ଘࡏ͍ͯ͠Δɽ

Δɽ·ͨɼ‫ݕ‬ग़͞ΕͨίʔυΫϩʔϯ͕ಉ࣌मਖ਼ର৅Λଟ͘‫ؚ‬•จͷฒͼସ͕͑ൃੜ͍ͯ͠Δɽ

Ή৔߹ɼ։ൃऀ͸‫ݕ‬ग़ͨ͠ίʔυΫϩʔϯ͔Βɼಉ࣌मਖ਼ର৅

2. 1. 2 ίʔυΫϩʔϯͷ‫ݕ‬ग़Λ‫͚ͭݟ‬ΔखؒΛ‫ݮ‬Β͢͜ͱ͕Ͱ͖Δɽຊ‫Ͱڀݚ‬͸ɼಉ࣌मਖ਼

ɹ༷ʑͳཻ౓ʹ‫͍ͯͮج‬ίʔυΫϩʔϯΛ‫ݕ‬ग़͢Δπʔϧ͕ର৅ͷίʔυΫϩʔϯ‫ݕ‬ग़ʹ͓͚Δؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧͷ։ൃ͞Ε͖ͯͨɽ[9]ɽҎԼʹຊ࿦จͰར༻ͨ͠πʔϧͷ‫ݕ‬ग़ཻ༗ޮੑΛධՁ͢Δࡍʹɼࣈ۟ղੳϕʔεͷίʔυΫϩʔϯ‫ݕ‬ग़౓ͷྫΛ‫͛ڍ‬Δɽؔ਺୯Ґͷ‫ݕ‬ग़Ͱ͸ɼؔ਺Λ 1 ͭͷཁૉͱ͠ɼ

πʔϧ CCFinder ͱͷൺֱΛߦͬͨ [12]ɽධՁ࣮‫Ͱݧ‬͸ɼLi Β౳ՁͳཁૉରΛ‫͚ͭݟ‬Δ͜ͱͰίʔυΫϩʔϯΛ‫ݕ‬ग़͢Δ [19]ɽ

͕༻ҙͨ͠ධՁηοτΛ༻͍ͨ [14] [15]ɽ͜ͷධՁηοτͰ͸ɼ͜ͷख๏͸ɼؔ਺ͷҰ෦ͷΈ͕ίʔυΫϩʔϯͰ͋Δ΋ͷΛ‫ݕ‬͕ܽؕ‫·ؚ‬Ε͍ͯΔίʔυยͱͦͷίʔυยͱಉܽؕ͡Λ‫ؚ‬Ήग़Ͱ͖ͳ͍ɽίʔυΫϩʔϯ‫ݕ‬ग़ͷͨΊʹɼϓϩάϥϜͷੑ࣭ίʔυΫϩʔϯͷࣄྫ͕‫·ؚ‬Ε͍ͯΔɽ͜ΕΒͷධՁηοτʹΛ‫ܭ‬ଌͨ͠ಛ௃ϕΫτϧΛ༻͍Δɽ

ؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧͱ CCFinder Λద༻͠ɼfalse positiveɹࣈ۟୯Ґͷ‫ݕ‬ग़Ͱ͸ɼϓϩάϥϜͷࣈ۟ղੳΛߦͬͨ‫ޙ‬ɼͦͱ false negative ΍࠶‫཰ݱ‬ɼద߹཰ͱ F ஋ͱ͍͏ධՁࢦඪΛ༻ͷࣈ۟Λཁૉͱͨ͠‫ʹྻܥ‬ରͯ͠ίʔυΫϩʔϯΛ‫ݕ‬ग़͢Δɽ

͍ͯධՁͨ͠ɽͦͷ݁Ռɼؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧ͸ద߹཰ͱࣈ۟ղੳΛߦ͏͜ͱʹΑΓɼۭന΍ίϝϯτΛແࢹ͢Δ͜ͱ͕F ஋ʹ͍ͭͯߴ͍஋Λදͨ͠ɽͰ͖Δɽ·ͨɼࣝผࢠ΍ఆ਺౳ͷಛఆͷछྨͷࣈ۟Λಛघͳ 1ͭͷࣈ۟ʹ‫ݻ‬ఆ͢Δ͜ͱͰɼม਺໊΍ؔ਺໊ͷมߋ͞Εͨίʔ

2. എ

‫ܠ‬

υย΋ίʔυΫϩʔϯͱͯ͠‫ݕ‬ग़͢Δ͜ͱ͕Ͱ͖Δɽɹ CCFinder ͸ࣈ۟୯ҐͷίʔυΫϩʔϯΛ‫ݕ‬ग़͢ΔπʔϧͰ

2. 1 ίʔυΫϩʔϯ

͋Δ [12]ɽ͜ͷπʔϧ͸·ͣɼೖྗ͞ΕͨιʔείʔυΛࣈ۟ίʔυΫϩʔϯͱ͸ɼιʔείʔυதʹଘࡏ͢ΔಉҰɼ͋Δ

୯Ґʹ෼ղ͠ɼม਺໊΍ؔ਺໊౳ͷϢʔβʔఆ໊ٛΛಉҰࣈ͍۟͸ྨࣅͨ͠෦෼Λ࣋ͭίʔυยͷ͜ͱΛҙຯ͢ΔɽҰൠతʹʹมߋ͢Δɽ͜ͷมߋʹΑͬͯɼม਺໊΍ؔ਺໊౳͕ҟͳΔλίʔυΫϩʔϯͷଘࡏ͸ɼιϑτ΢ΣΞͷอकΛࠔ೉ʹͤ͞Δ

Πϓ 2 ·ͰͷίʔυΫϩʔϯΛ‫ݕ‬ग़ՄೳͰ͋Δɽ࠷‫ʹޙ‬ɼҰཁҼͷҰͭͱ‫ݴ‬ΘΕ͍ͯΔ [5]ɽίʔυΫϩʔϯͷൃੜͷओͨΔ

க͢Δࣈ۟ྻΛίʔυΫϩʔϯͱͯ͠‫͚ͭݟ‬ΔɽCCFinder ͸ཁҼ͸ɼ‫ط‬ଘͷιʔείʔυͷίϐʔΞϯυϖʔετʹΑΔ࠶

ίʔυΫϩʔϯΛߴ଎Ͱ‫ݕ‬ग़ՄೳͰ͋Γɼଟ͘ͷ‫ۀا‬΍‫Ͱڀݚ‬

ར༻Ͱ͋ΔɽҰൠతʹɼ‫ʹ͍ޓ‬ίʔυΫϩʔϯʹͳΔίʔυย࢖༻͞Ε͍ͯΔɽͷରͷ͜ͱΛΫϩʔϯϖΞͱ‫ͼݺ‬ɼΫϩʔϯϖΞʹ͓͍ͯਪҠؔ܎͕੒ΓཱͭίʔυΫϩʔϯͷू߹ͷ͜ͱΛΫϩʔϯηοτͱ‫Ϳݺ‬ɽ

2. 2 ؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧ͜ͷઆͰ͸ࢁதΒ͕։ൃͨؔ͠਺Ϋϩʔϯ‫ݕ‬ग़πʔϧ [19] ͷઆ໌Λߦ͏ɽؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧͰ͸৘ใ‫ٕࡧݕ‬ज़Λར༻ɹίʔυΫϩʔϯʹର͢Δอक࡞‫ۀ‬ͷ 1 ͭʹɼιʔείʔυͷ͠ɼλΠϓ 1 ͔ΒλΠϓ 4 ͷ͢΂ͯͷλΠϓͷؔ਺୯Ґͷίʔಉ࣌मਖ਼͕‫͛ڍ‬ΒΕΔ [6] [11]ɽྫ͑͹ɼ͋Δίʔυยʹ͕ܽؕυΫϩʔϯΛ‫ݕ‬ग़͢Δ͜ͱ͕Ͱ͖Δɽ

‫ʹࡍ͔ͨͬͭݟ‬ɼͦͷίʔυยͷίʔυΫϩʔϯʹ΋ಉ༷ͷܽɹؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧ͸ɼೖྗ͞Εͨιʔείʔυதͷ͕ؕ‫·ؚ‬Ε͍ͯΔՄೳੑ͕ߴ͍ɽͦͷͨΊɼ։ൃऀ͸ίʔυยϫʔυʹ‫਺֤͍ؔͯͮج‬Λಛ௃ϕΫτϧʹม‫͢׵‬Δɽ͜͜Ͱʹ͕ܽؕ‫͔ͨͬͭݟ‬৔߹ɼಉҰΫϩʔϯηοτ಺ʹ‫·ؚ‬ΕΔશϫʔυ͸ҎԼͷ 2 ͭΛࣔ͢ɽͯͷίʔυΫϩʔϯʹରͯ͠ಉҰͷमਖ਼Λ͢Δ͔‫ݕ‬౼͢Δඞཁ•ม਺΍ؔ਺ͳͲʹ͚ͭΒΕͨࣝผࢠ໊Λߏ੒͢Δ୯‫ޠ‬͕͋Δɽ͔͠͠ɼ͢΂ͯͷίʔυΫϩʔϯΛ։ൃऀ͕ख࡞‫Ͱۀ‬•৚݅จ΍‫܁‬ฦ͠จͳͲͷߏจʹར༻͞ΕΔ༧໿‫ޠ‬‫͚ͯͭݟ‬؅ཧ͢Δͷ͸ࠔ೉Ͱ͋Δɽͦ͜Ͱɼ։ൃऀΛࢧԉ͢Δͦͯ͠ɼͦͷಛ௃ϕΫτϧؒͷྨࣅ౓Λ‫ͯ͠ࢉܭ‬ɼΫϩʔϯϖͨΊʹίʔυΫϩʔϯ‫ݕ‬ग़πʔϧ͕ར༻͞ΕΔ [9]ɽΞͷू߹ΛϦετͱͯ͠ग़ྗ͢Δɽ·ͨɼ‫ݕ‬ग़ͷߴ଎ԽͷͨΊ

2. 1. 1 ίʔυΫϩʔϯͷఆٛʹɼྨࣅ౓ͷ‫ࢉܭ‬ͷ௚લʹ LSHʢLocality-Sensitive HashingʣίʔυΫϩʔϯʹ͸ɼීวతఆٛ͸ଘࡏ͠ͳ͍ɽຊ࿦จͰ͸ɼΞϧΰϦζϜ [8] Λ༻͍ͯಛ௃ϕΫτϧͷΫϥελϦϯάΛߦͬίʔυΫϩʔϯͷఆٛͱͯ͠ҎԼͷ 4 ͭͷλΠϓͷ෼ྨΛ༻͍

͍ͯΔɽؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧͷίʔυΫϩʔϯ‫ݕ‬ग़ख๏͸Δ [16] [19]ɽ

େ͖͘ 4 ͭͷεςοϓʹ෼͚ΒΕΔɽͦͷؔ਺Ϋϩʔϯ‫ݕ‬ग़λΠϓ 1 ۭനͷ༗ແɼϨΠΞ΢τɼίϝϯτͷ༗ແͳͲͷҧπʔϧͷίʔυΫϩʔϯ‫ݕ‬ग़ϓϩηεΛਤ 1 ʹࣔ͢ɽ͍Λআ͖‫׬‬શʹҰக͢Δ.

STEP1ɿϫʔυͷநग़ ɹ

λΠϓ 2 λΠϓ 1 ͷҧ͍ʹՃ͑ͯɼม਺໊ͳͲͷϢʔβఆٛ͜ͷεςοϓͰ͸ɼιʔείʔυதͷ֤ؔ਺͔Βϫʔυͷநग़—2—^dWϭ

^dWϯ

^dWϮ

^dWϰ

㛵ᩘ
䝽䞊䝗

ಶᩘ

ǆǆǆ

ϯ

ǇǇǇ

Ϯ

䞉䞉䞉

䞉䞉䞉

㛵ᩘ

{a1, a2 , a3 , ࠉ
…}

㛵ᩘ
㛵ᩘ

㛵ᩘ

䝋䞊䝇䝁䞊䝗

䝽䞊䝗

ಶᩘ

ǆǆǆ

Ϯ

ǇǇǇ

ϰ

䞉䞉䞉

䞉䞉䞉

䝽䞊䝗䝸䝇䝖

㛵ᩘ
㛵ᩘ
㛵ᩘ
㛵ᩘ
{b1, b2 , b3 , ࠉ
…}

䜽䝷䝇䝍

㢮ఝᗘ

㛵ᩘᑐ 䜽䝻䞊䞁

Ϭ͘ϵϱ

㛵ᩘ
㛵ᩘ

Ϭ͘ϳϬ

㛵ᩘ
㛵ᩘ

Ϭ͘ϳϬ

㛵ᩘ
㛵ᩘ

Ϭ͘ϵϬ

㛵ᩘ
㛵ᩘ

䞉䞉䞉

䞉䞉䞉

䘠

䘠

䜽䝻䞊䞁䝨䜰䝸䝇䝖≉ᚩ䝧䜽䝖䝹

ਤ 1 ؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧͷίʔυΫϩʔϯ‫ݕ‬ग़ϓϩηεΛߦ͏ɽࣝผࢠ໊͕ෳ਺ͷ୯‫ߏͰޠ‬੒͞Ε͍ͯΔ৔߹ɼ෼ׂΛɹ͜͏ͯ͠ STEP1 ͔Β STEP4 Λ‫ݕͯܦ‬ग़ͨ͠ΫϩʔϯϖΞߦ͍৽ͨʹෳ਺ͷϫʔυͱ͢Δɽͦͷ෼ׂํ๏ʹ͸ɼϋΠϑϯϦετΛ݁Ռͱͯ͠ग़ྗ͢Δɽ౳ͷ۠੾Γ‫߸ه‬ʢσϦϛλʣʹΑΔ෼ׂͱɼࣝผࢠ໊தͷେจɹࢁதΒͷؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧ͸ධՁ࣮‫ͯ͠ͱݧ‬ɼίʔύࣈʹͳ͍ͬͯΔΞϧϑΝϕοτʹΑΔ෼ׂ͕͋Δɽ‫܁‬ฦ͠จ౳ε [18] Λ༻͍ͨ‫ݕ‬ग़ਫ਼౓ͷධՁͱɼ‫ط‬ଘͷؔ਺୯ҐͷΫϩʔϯͰΑ͘༻͍ΒΕΔʠ̸ʡ΍ʠ̹ʡ౳ɼҙຯ৘ใ͕ࠐΊΒΕ͍ͯ‫ݕ‬ग़πʔϧͱͷ‫ݕ‬ग़ਫ਼౓ͱ‫ݕ‬ग़࣌ؒͷൺֱΛߦ͍ͬͯΔɽ͔͠

ͳ͍ม਺΋ಉҰͷ΋ͷͱͯ͠ѻ͏ͨΊʹɼ2 จࣈҎԼͷࣝผࢠ͠ɼ൴Β͸ؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧͷɼܽؕͷಉ࣌मਖ਼ʹ໊͓͚͸͢΂ͯಉҰͷϫʔυͱͯ͠ೝࣝ͢Δɽ

Δπʔϧͷ༗ޮੑͷධՁ͸ߦ͍ͬͯͳ͍ɽͦ͜Ͱຊ࿦จͰ͸ɼSTEP2ɿಛ௃ϕΫτϧͷ‫ ࢉܭ‬ɹؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧ͕ܽؕΛ‫ؚ‬ΉίʔυΫϩʔϯΛ‫ݕ‬ग़Ͱ

STEP1 Ͱநग़ͨ͠ϫʔυʹରͯ͠ TF-IDF ๏ [2] Λར༻֤ͯ͠

͖Δ͔Λௐࠪ͠ɼؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧͷܽؕͷಉ࣌मਖ਼ࢧ

ϫʔυͷॏΈΛ‫͠ࢉܭ‬ɼͦͷ஋Λಛ௃ྔͱͯ͠ར༻ͯ͠ɼ֤ؔ

ԉʹ͓͚Δ༗ޮੑΛௐࠪͨ͠ɽ

਺Λಛ௃ϕΫτϧʹม‫͢׵‬ΔɽTF-IDF ๏ʹΑΔ஋͸ tf ஋ʢؔ਺தͷϫʔυͷग़‫ݱ‬ස౓ʣͱ idf ஋ʢιʔείʔυશମͷϫʔ

3. ௐ ࠪ ख ๏υͷ‫ر‬গ͞ʣͷੵͰ༩͑ΒΕΔɽ͜ͷख๏Ͱ͸ɼશؔ਺தͷ֤

3. 1 ௐࠪର৅ͷධՁηοτϫʔυʹରͯ͠ॏΈΛ‫͠ࢉܭ‬ɼͦΕΒΛಛ௃ྔͱͯ͠༻͍Δ͜Li Β͸ Git, Linux kernel, PostgreSQL ͷ 3 ͭͷΦʔϓϯͱʹΑͬͯಛ௃ϕΫτϧΛ‫ٻ‬Ί͍ͯΔɽͦͷͨΊɼ֤ؔ਺ͷಛιʔειϑτ΢ΣΞ͔ΒɼܽؕΛ‫ؚ‬ΉίʔυยͱͦͷίʔυΫ௃ϕΫτϧͷ࣍‫ݩ‬͸ιʔείʔυதʹଘࡏ͢Δશϫʔυͷ਺ͱϩʔϯΛ‫[ ͚ͨͭݟ‬14] [15]ɽLi Β͕ɼ͜ΕΒͷΦʔϓϯιʔεͳΔɽιϑτ΢ΣΞΛར༻ͨ͠ཧ༝͸ɼ(1) ओʹ C/C++Λ࢖ͬͯॻSTEP3ɿಛ௃ϕΫτϧͷΫϥελϦϯά ɹ͔Ε͓ͯΓɼ(2) όʔδϣϯཤྺ͔ΒܽؕΛ‫ؚ‬Ήίʔυͱͦͷ

STEP2 Ͱ‫਺֤ؔͨ͠ࢉܭ‬ͷಛ௃ϕΫτϧʹରͯ͠ΫϥελϦ

ίʔυΫϩʔϯΛ‫͚ͭݟ‬Δ͜ͱ͕ՄೳͰ͋Γɼ(3)Git ͸ 10 ສϯάΛߦ͏͜ͱʹΑͬͯɼΫϩʔϯϖΞʹ੒ΓಘΔީิΛߜΔɽ

ߦҎ্ɼPostgreSQL ͸ 30 ສߦҎ্ɼLinux kernel ͸ 100 ສߦ͜͜Ͱ͸ɼLSH ΞϧΰϦζϜ [8] Λ༻͍ͯಛ௃ϕΫτϧͷΫϥ

Ҏ্΋ͷίʔυͰ͋ΓɼධՁʹ͓͍ͯे෼ͳεέʔϥϏϦςΟ

ελϦϯάΛߦ͏ɽLSH ΞϧΰϦζϜΛར༻͢Δ͜ͱʹΑͬΛ༗͍ͯ͠Δ͔ΒͰ͋ΔɽLi Β͸ɼܽؕΛ‫ؚ‬ΉίʔυยͱɼͦͯɼΫΤϦͱͯ͠ 1 ͭͷಛ௃ϕΫτϧΛ༩͑Δͱɼಛ௃ϕΫͷίʔυยͱಉܽؕ͡Λ࣋ͭίʔυΫϩʔϯͷࣄྫʢҎ߱ɼධτϧू߹͔ΒͦͷΫΤϦͱۙࣅͨ͠ಛ௃ϕΫτϧू߹ͷΫϥεՁηοτͱ‫Ϳݺ‬ʣΛςΫχΧϧϨϙʔτͰެ։͍ͯ͠Δ [14]ɽ

λΛऔಘ͢Δ͜ͱ͕Ͱ͖ΔɽຊεςοϓͰ͋Β͔͡ΊΫϥελ

͜ͷςΫχΧϧϨϙʔτ͸ܽؕΛ‫ؚ‬Ήίʔυยͷ Git ϦϙδτϦϯάΛߦ͏͜ͱͰΫϩʔϯϖΞͱ੒ΓಘΔީิΛߜΔ͜ͱʹϦͷίϛοτ ID ͱɼಉܽؕ͡Λ࣋ͭίʔυΫϩʔϯͷ Git ϦΑͬͯɼ‫ݕ‬ग़࣌ؒʹ͔͔Δ‫ࢉܭ‬ίετΛ࡟‫͍ͯ͠ݮ‬Δɽͳ͓ɼϙδτϦͷίϛοτ ID Λ‫ؚ‬ΜͰ͍Δɽ

LSH ΞϧΰϦζϜ͕࣮૷͞Ε͍ͯΔ E2LSH [1] Λ͜ͷख๏Ͱɹຊ‫Ͱڀݚ‬͸͜ͷධՁηοτΛ༻͍ͯɼؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔ͸ར༻͍ͯ͠ΔɽϧͷܽؕΛ‫ؚ‬ΉίʔυΫϩʔϯ‫ݕ‬ग़ʹ͓͚Δ༗ޮੑΛௐࠪ͠ɼSTEP4ɿಛ௃ϕΫτϧͷྨࣅ౓ͷ‫ ࢉܭ‬ɹ

CCFinder ͱൺֱͨ͠ɽ͔͠͠ɼͦͷࣄྫͷதʹ͸ܽؕΛ‫ؚ‬Ή࠷‫ʹޙ‬ɼSTEP3 Ͱ‫ٻ‬Ί֤ͨΫϥελதͷؔ਺ͷ͍ͭʹରͯ͠ίʔυยͱͦͷίʔυΫϩʔϯ͕ಉؔ͡਺಺ʹଘࡏ͢Δ΋ͷ΋ίαΠϯྨࣅ౓Λ༻͍ͯΫϩʔϯϖΞͰ͋Δ͔൱͔ͷ൑ఆΛߦଘࡏ͢Δɽؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧ͸ؔ਺୯ҐͷίʔυΫϩʔ͏ɽಛ௃ྔ͸ৗʹਖ਼ͷ஋ΛͱΔͨΊɼίαΠϯྨࣅ౓͸ 0 ͔ΒϯΛ‫ݕ‬ग़͢ΔͨΊɼͦͷΑ͏ͳίʔυΫϩʔϯ͸‫ݕ‬ग़͢Δ͜ͱ

1 ͷൣғͱͳΔɽ΋͠ɼίαΠϯྨࣅ౓͕ᮢ஋Ҏ্Ͱ͋Ε͹ɼ͕Ͱ͖ͳ͍ɽΑͬͯɼͦͷΑ͏ͳίʔυΫϩʔϯ͸ௐࠪର৅͔

ͦͷؔ਺ͷର͸ΫϩʔϯϖΞͰ͋Δͱ൑ఆ͢ΔɽΒऔΓআ͍ͯɼશ 38 छྨͷΫϩʔϯηοτʹ‫·ؚ‬ΕΔ 58 ‫ݸ‬ͷ—3—ίʔυΫϩʔϯͷࣄྫʹରͯ͠ௐࠪΛߦͬͨɽ

3. 2 ௐ ࠪ ख ॱؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧͷੑೳΛൺ΂ΔͨΊʹɼLi Β͕༻ҙͨ͠ධՁηοτΛ༻͍ͯҎԼͷखॱͰௐࠪΛߦͬͨɽCCFinderΛධՁͷࢦඪͱͯ͠༻͍ͨͷ͸ɼCCFinder ͸ଟ͘ͷ࣮‫Ͱݧ‬ར༻͞Ε͓ͯΓɼͦͷ༗ޮੑ͕֬ೝ͞Ε͍ͯΔ͔ΒͰ͋Δɽຊ‫ݚ‬‫ڀ‬ͷௐࠪखॱͷ֓ཁ͸ҎԼͷ௨ΓͰ͋Δɽ

3. 3 ධ Ձ ࢦ ඪ
2 छྨͷධՁࢦඪΛ༻͍ͨɽ۩ମతʹ͸ɼLi Βͷ‫ͱڀݚ‬ಉ༷
ʹ false positive ͱ false neative ʹ‫ࢦͮ͘ج‬ඪ΍࠶‫ͱ཰ݱ‬ద߹཰ͱ F ஋͍͏ධՁࢦඪΛ༻͍ͨ

3. 3. 1 false positive ͱ false negative
false positive ͱ͸ɼධՁηοτͰܽؕΛ‫ؚ‬Ήࣄྫͱͯ͠‫ڍ‬͛ΒΕ͍ͯͳ͍͕ɼධՁର৅ͷπʔϧͰ͸ίʔυΫϩʔϯͱ͠

ʢ 1 ʣ ܽؕΛ‫ؚ‬ΉίʔυยͱɼͦΕͱಉܽؕ͡Λ࣋ͭίʔυͯ‫ݕ‬ग़ͨ͠΋ͷΛࢦ͢ɽfalise negative ͱ͸ɼධՁηοτͰܽΫϩʔϯͷྫͱͯ͠‫͛ڍ‬ΒΕ͍ͯΔίʔυย͕‫·ؚ‬Ε͍ͯΔ֤ؕΛ‫ؚ‬Ήࣄྫͱͯ͠‫͛ڍ‬ΒΕ͍ͯΔ͕ɼධՁର৅ͷπʔϧͰ͸ίϛοτͷεφοϓγϣοτΛ Git ϦϙδτϦ͔Βऔಘ͢ΔɽίʔυΫϩʔϯͱͯ͠‫ݕ‬ग़Ͱ͖ͳ͔ͬͨ΋ͷΛࢦ͢ɽ͜ͷ 2 ͭ

ʢ 2 ʣ ؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧɼCCFinder ͰίʔυΫϩʔͷࢦඪΛ༻͍ͯධՁର৅ͷπʔϧʹΑΔ‫ݕ‬ग़݁ՌΛҎԼͷ 4 ͭϯ‫ݕ‬ग़Λߦ͏ɽʹ෼ྨ͢Δɽ

ʢ 3 ʣ ‫ݕ‬ग़݁ՌͷධՁΛߦ͏ɽ

N1ɿno false positives, no false negatives ɹ·ͣɼGit, Linux kernal, PostgresSQL ͷ Git ϦϙδτϦ͔ධՁηοτʹ‫·ؚ‬Ε͍ͯΔશͯͷίʔυΫϩʔϯ͕‫ݕ‬ग़͞ΕɼΒධՁηοτͷܽؕΛ‫ؚ‬Ήίʔυยͱɼͦͷίʔυยͱಉ͔ͭ͡‫·ؚ‬Εͯͳ͍ίʔυΫϩʔϯ͸̍ͭ΋‫ݕ‬ग़͞Εͯͳ͍ΫܽؕΛ࣋ͭίʔυΫϩʔϯ͕͋ΔίϛοτΛνΣοΫΞ΢τ

ϩʔϯηοτ͕෼ྨ͞ΕΔɽ

͢Δɽ࣍ʹɼؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧͱ CCFinder ͰධՁηοN2ɿno false positives, some false negatives ɹτͷίʔυย΍ίʔυΫϩʔϯͷ‫ݕ‬ग़Λߦ͏ɽͦͷࡍɼGit ͱධՁηοτʹ‫·ؚ‬Ε͍ͯΔίʔυΫϩʔϯʹ‫ݕ‬ग़࿙Ε͕͋Γɼ

PostgreSQL ͸ϓϩδΣΫτશମͷιʔείʔυʹରͯ͠Ϋ͔ͭ‫·ؚ‬Εͯͳ͍ίʔυΫϩʔϯ͸̍ͭ΋‫ݕ‬ग़͞Εͯͳ͍Ϋϩʔϯ‫ݕ‬ग़Λߦͬͨɽ͔͠͠ɼLinux kernel ͸ϓϩδΣΫτ͕ϩʔϯηοτ͕෼ྨ͞ΕΔɽ

େ͖͗ͯ͢ɼϓϩδΣΫτશମʹରͯ͠ίʔυΫϩʔϯ‫ݕ‬ग़Λ

N3ɿsome false positives, no false negatives ɹߦ͏͜ͱ͕Ͱ͖ͳ͔ͬͨͨΊɼίʔυΫϩʔϯ͕ଘࡏ͢ΔσΟධՁηοτʹ‫·ؚ‬Ε͍ͯΔશͯͷίʔυΫϩʔϯ͕‫ݕ‬ग़͞ΕɼϨΫτϦͷपลʹൣғΛߜͬͯίʔυΫϩʔϯ‫ݕ‬ग़Λߦͬͨɽ͔ͭ‫·ؚ‬Εͯͳ͍ίʔυΫϩʔϯ΋‫ݕ‬ग़͞ΕͨΫϩʔϯηοτ

CCFinder ͱؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧؒͰɼద༻ൣғ͸౷Ұ͕͠෼ྨ͞ΕΔɽ

͍ͯΔɽ

N4ɿsome false positives, some false negatives ɹɹؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧͰܽؕΛ‫ؚ‬ΉίʔυΫϩʔϯΛ‫ݕ‬ग़ධՁηοτʹ‫·ؚ‬Ε͍ͯΔίʔυΫϩʔϯʹ‫ݕ‬ग़࿙Ε͕͋Γɼ͢ΔͨΊʹ͸ɼ·ͣɼbuggy.c ͱ͍͏ϑΝΠϧΛ࡞Γɼͦͷதʹ͔ͭ‫·ؚ‬Εͯͳ͍ίʔυΫϩʔϯ΋‫ݕ‬ग़͞ΕͨΫϩʔϯηοτܽؕΛ‫ؚ‬Ήؔ਺ͷίʔυยΛൈ͖औΓอଘ͢Δɽ࣍ʹɼbuggy.c͕෼ྨ͞ΕΔɽΛܽؕΛ‫ؚ‬Ήίʔυยͱಉܽؕ͡Λ࣋ͭίʔυΫϩʔϯ͕‫·ؚ‬

3. 3. 2 ࠶‫ͱ཰ݱ‬ద߹཰ͱ F ஋Ε͍ͯΔόʔδϣϯͷதʹอଘΛ͢Δɽͦͯ͠ɼͦͷόʔδϣ

false positive ͱ false negative ʹΑΔධՁࢦඪͰ͸ɼfalseϯʹରͯ͠ɼؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧΛ͔͚ͯ buggy.c ʹอଘpositive ͱ false negative ͷ਺ྔͷେখΛߟྀ͍ͯ͠ͳ͍ɽͦ

ͨؔ͠਺ͱɼίʔυΫϩʔϯͷྫ͕‫ݕ‬ग़͞ΕΔ͔Ͳ͏͔Λௐ΂͜Ͱɼfalse positive ͱ false negative ͷ਺ྔΛ͸͖ͬΓͱͤͨ͞ɽbuggy.c Λ༻ҙͨ͠ͷ͸ɼܽؕͷ͋ΔίʔυยΛ‫ؚ‬Ήؔ਺

ΔͨΊʹ࠶‫ͱ཰ݱ‬ద߹཰ͱ F ஋͍͏ධՁࢦඪΛ༻͍ͨɽ࠶‫཰ݱ‬ͷ͋Δ৔ॴΛΘ͔Γ΍ͯ͘͢͠ɼ‫ݕ‬ग़݁ՌΛ֬ೝ͢Δͱ͖ʹɼͱద߹཰ͱ F ஋ͷઆ໌ΛҎԼʹࣔ͢ɽ‫ޡ‬Γ͕ੜ͡ͳ͍Α͏ʹ͢ΔͨΊͰ͋Δɽ·ͨɼؔ਺Ϋϩʔϯɹ࠶‫ͱ཰ݱ‬͸ɼਖ਼ղͷ͏ͪ‫ݕ‬ग़͞Εͨ΋ͷΛࢦ͢΋ͷͰ͋Γɼ‫ݕ‬ग़πʔϧͷᮢ஋͸σϑΥϧτͷ 0.9 ͱ 0.5 ͷ 2 छྨͰௐࠪΛ໢ཏੑʹؔ͢Δࢦඪͱͯ͠༻͍ΒΕΔɽຊ‫Ͱڀݚ‬ͷ࠶‫཰ݱ‬͸ɼߦͬͨɽᮢ஋ͷઃఆʹΑΔؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧͷܽؕΛ‫ؚ‬ධՁηοτͰܽؕΛ‫ؚ‬Ήࣄྫͱͯ͠‫͛ڍ‬ΒΕ͍ͯΔίʔυΫΉίʔυΫϩʔϯͷ‫ݕ‬ग़ਫ਼౓ͷҧ͍Λ֬ೝ͢ΔͨΊʹɼᮢ஋Λϩʔϯͷ͏ͪ‫ݕ‬ग़πʔϧ͕‫ݕ‬ग़ͨ͠΋ͷͷׂ߹Λද͢ɽͳ͓ɼ

σϑΥϧτ͚ͩͰͳ͘ 0.5 Ͱ΋‫ݕ‬ग़Λߦͬͨ࠶‫ͦͲ΄͍ߴ͕཰ݱ‬ͷπʔϧ͸ੑೳ͕ྑ͍ͱ൑அͰ͖Δɽɹ CCFinder ͸ Libra Λ༻͍ͯධՁͨ͠ [7]ɽLibra ͸ಛఆͷɹద߹཰ͱ͸ɼ݁Ռʹ͓͍ͯຊ౰ʹਖ਼͔ͬͨ͠΋ͷͷׂ߹ΛࢦίʔυยΛҾ਺ͱͯ͠༩͑ΔͱɼͦͷίʔυΫϩʔϯΛ‫͚ͭݟ‬͢΋ͷͰ͋Γɼਖ਼֬ੑʹؔ͢Δࢦඪͱͯ͠༻͍ΒΕΔɽຊ‫ڀݚ‬ΔπʔϧͰ͋ΔɽLibra ʹɼҾ਺ͱͯܽؕ͠Λ‫ؚ‬ΉίʔυยΛͰͷద߹཰͸ɼ‫ݕ‬ग़πʔϧ͕࣮ࡍʹ‫ݕ‬ग़ͨ͠ίʔυΫϩʔϯͷ༩͑ͯɼܽؕΛ‫ؚ‬Ήίʔυยͱಉܽؕ͡Λ࣋ͭίʔυΫϩʔ͏ͪɼධՁηοτͰܽؕΛ‫ؚ‬Ήࣄྫͱͯ͠‫͛ڍ‬ΒΕ͍ͯΔίʔϯͷྫ͕͋Δόʔδϣϯʹରͯ͠ίʔυΫϩʔϯ‫ݕ‬ग़Λߦ͍ɼυΫϩʔϯͷׂ߹Λද͢ɽͳ͓ɼద߹཰͕ߴ͍΄ͲͦͷπʔϧίʔυΫϩʔϯͷྫΛ‫ݕ‬ग़͢Δ͜ͱ͕Ͱ͖Δ͔Ͳ͏͔Λௐ΂͸ੑೳ͕ྑ͍ͱ൑அͰ͖Δɽ

ͨɽCCFinder ͷ࠷খҰகτʔΫϯ਺͸ɼLi Βͷ࣮‫߹ʹݧ‬Θͤɹ F ஋ͱ͸ɼ࠶‫ͱ཰ݱ‬ద߹཰ͱ͍͏໢ཏੑͱਖ਼֬ੑͷ૯߹తͳͯ 10 ͱͯ͠༻͍ͨɽ

ධՁͷࡍʹར༻͞ΕΔई౓ͱͯ͠༻͍ΒΕΔ΋ͷͰ͋Δɽ࠶‫ݱ‬ɹ࠷‫ʹޙ‬ɼ38 ‫ݸ‬ͷܽؕΛ‫ؚ‬ΉΫϩʔϯηοτͷྫ͢΂ͯʹର͠཰ͱద߹཰͸‫ʹ͍ޓ‬τϨʔυΦϑͷؔ܎Ͱ͋ΔͨΊɼF ஋Λߴ্ͯͰड़΂ͨखॱΛ‫܁‬Γฦ͠ߦ͍ɼ࣍ʹઆ໌͢Δ N1ʙN4 ͷධ͘Ͱ͖Ε͹૯߹తʹྑ͍ධՁͱͳΔɽF ஋͸ɼ࠶‫ͱ཰ݱ‬ద߹཰Ձࢦඪͱɼ࠶‫ͱ཰ݱ‬ద߹཰ͷධՁࢦඪΛ༻͍ͯධՁΛߦͬͨɽͷௐ࿨ฏ‫ʹۉ‬Αͬͯ‫ٻ‬ΊΒΕΔɽ—4—৔߹͸ࣅͨΑ͏ͳ݁Ռͱͳ͍ͬͯΔɽF ஋Λൺ΂Δͱɼؔ਺Ϋ

4. ௐ ࠪ ݁ Ռϩʔϯ‫ݕ‬ग़πʔϧͷᮢ஋ 0.9 ͷ৔߹͕࠷΋ྑ͍஋ʹͳΓɼᮢ஋ද̍͸ɼධՁηοτͷશ 38 छྨͷΫϩʔϯηοτʹ‫·ؚ‬Ε

0.5 ͷ৔߹ͱ CCFinder ͸௿͍஋ͱͳͬͨɽҎ্ͷ͜ͱ͔Βɼ

Δ 58 ‫ݸ‬ͷίʔυΫϩʔϯʹରͯؔ͠਺Ϋϩʔϯ‫ݕ‬ग़πʔϧͱؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧ͸ɼᮢ஋ 0.9 ͷ৔߹ʹద߹཰ͱ F ஋ʹ

CCFinder Λద༻ͯ͠ɼ3.3.1 અͰઆ໌ͨ͠ N1ʙN4 ͷ਺Λ·͓͍ͯྑ͍݁ՌΛࣔͨͨ͠Ίɼόάͷಉ࣌मਖ਼ʹ͓͍ͯे෼ͳ

ͱΊͨ΋ͷΛࣔ͢ɽੑೳΛൃ‫͖Ͱش‬Δ͜ͱ͕Θ͔ͬͨɽද 1 N1ʙN4 ͷ෼ྨ݁Ռؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧ෼ྨ ᮢ஋ 0.9

ද 2 ؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧͱ CCFinder ͷൺֱؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧ

CCFinderᮢ஋ 0.5

ᮢ஋ 0.9ᮢ஋ 0.5

CCFinder

N1

11

10

10

‫ݕ‬ग़਺

41

293

N2

22

13

11

ਖ਼ղ‫ݕ‬ग़਺

24

31

31

N3

4

11

16

࠶‫཰ݱ‬

0.41

0.53

0.53

N4

1

4

1

ద߹཰

0.59

0.11

0.01

F஋

0.48

0.18

0.02

2274

ɹ N1ʙN4 ͷಛੑΛ;·͑ͯ͜ͷ݁Ռ͔ΒΘ͔Δ͜ͱ͸ɼ·ͣɼN1 ͱ N3 ʹ෼ྨ͞Εͨ΋ͷ͸ɼ࿙Εͳ͘‫ݕ‬ग़Ͱ͖ͨΫϩʔϯηοτͰ͋ΔɽΑͬͯɼධՁηοτͷ 38 छྨͷΫϩʔϯηο

5. ߟ

࡯

τͷྫͷ಺ɼؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧͷᮢ஋ 0.9 ͷ৔߹͸ 15ؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧͷ‫ݕ‬ग़݁Ռ͸ɼᮢ஋ʹΑͬͯେ͖͘

‫ݸ‬ɼᮢ஋ 0.5 ͷ৔߹͸ 21 ‫ݸ‬ɼCCFinder ͸ 26 ‫ݸ‬ͷΫϩʔϯηοมΘͬͨɽᮢ஋ΛԼ͛Δͱɼ࠶‫཰ݱ‬͸্͕Γద߹཰͸Լ͕ΔɽτΛ࿙Εͳ͘‫ݕ‬ग़Ͱ͖ͨ͜ͱ͕Θ͔ͬͨɽ·ͨɼN2 ͱ N4 ʹ෼͜ΕΒ 2 ͭ͸τϨʔυΦϑͷؔ܎ʹ͋ΔɽΑͬͯɼద੾ͳᮢ஋

ྨ͞Εͨ΋ͷ͸ɼධՁπʔϧ͕‫ݕ‬ग़Ͱ͖ͳ͔ͬͨίʔυΫϩʔΛఆΊΔඞཁ͕͋Δɽᮢ஋Λ 0.6ɼ0.7ɼ0.8 ͷ৔߹΋ௐ΂ΔͱɼϯΛ‫ؚ‬ΜͰ͍ΔΫϩʔϯηοτͰ͋ΔɽΑͬͯɼؔ਺ΫϩʔΑΓΑ͍ᮢ஋͕‫͔ͭݟ‬Δ͔΋͠Εͳ͍ɽϯ‫ݕ‬ग़πʔϧͷᮢ஋ 0.9 ͷ৔߹͸ 23 ‫ݸ‬ɼᮢ஋ 0.5 ͷ৔߹͸ 17ɹຊ‫Ͱڀݚ‬͸ɼCCFinder ͷ࠷খҰகτʔΫϯ਺Λ Li Βͷௐࠪ‫ݸ‬ɼCCFinder ͸ 12 ‫ݸ‬ͷΫϩʔϯηοτͷίʔυΫϩʔϯΛʹ߹Θͤͯ 10 ʹઃఆͨ͠ɽ։ൃऀ͕όάࣄྫ͝ͱʹɼ࠷খҰগͳ͘ͱ΋‫ݕ‬ग़Ͱ͖ͳ͔ͬͨ͜ͱ͕Θ͔ͬͨɽͦͯ͠ɼN1 ͱகτʔΫϯ਺Λద੾ʹઃఆ͢Δ͜ͱ͕Ͱ͖Ε͹ɼCCFinder ͷN2 ʹ෼ྨ͞Εͨ΋ͷ͸ɼධՁηοτʹ‫·ؚ‬Ε͍ͯΔίʔυΫద߹཰ͱ F ஋͸্ঢ͢Δ͜ͱ͕ߟ͑ΒΕΔɽͦ͜Ͱɼ࠷খҰகϩʔϯͷΈ‫ݕ‬ग़͞ΕͨΫϩʔϯηοτͰ͋ΓɼN3 ͱ N4 ʹ෼τʔΫϯ਺Λ 20ɼ30 ʹઃఆͨ͠ͱ͖΋ௐ΂ͯΈͨɽͦͷ݁Ռྨ͞Εͨ΋ͷ͸ɼධՁηοτʹ‫·ؚ‬Ε͍ͯΔίʔυΫϩʔϯҎΛද 3 ʹࣔ͢ɽਖ਼ղΫϩʔϯ਺͕ಉ͡Ͱͳ͍ͨΊɼ‫ʹີݫ‬͸‫ݴ‬֎ʹ΋‫ݕ‬ग़͞ΕͨΫϩʔϯηοτͰ͋ΔɽΑͬͯɼؔ਺Ϋϩʔ͑ͳ͍͕ɼ࠷খҰகτʔΫϯ਺Λ্͛Ε͹ద߹཰ͱ F ஋΋্͕ϯ‫ݕ‬ग़πʔϧͷᮢ஋ 0.9 ͷ৔߹͸ 5 ‫ݸ‬ɼᮢ஋ 0.5 ͷ৔߹͸ 15

Δ͜ͱ͕෼͔ͬͨɽ

‫ݸ‬ɼCCFinder ͸ 17 ‫ݸ‬ͷΫϩʔϯηοτͰධՁηοτʹ‫·ؚ‬Ε͍ͯΔίʔυΫϩʔϯҎ֎ʹ΋‫ݕ‬ग़͞Εͨ͜ͱ͕Θ͔ͬͨɽ

ද 3 CCFinder ͷᮢ஋Λม͑ͨࡍͷධՁ݁Ռ
ᮢ஋ 10

ᮢ஋ 20

ᮢ஋ 30

ਖ਼ղΫϩʔϯ਺58

74

ᮢ஋ 0.9 ΑΓᮢ஋ 0.5 ͷ৔߹ͷ΄͏͕ɼܽؕࣄྫΛ࣋ͭίʔυ

‫ݕ‬ग़਺

2274

370

10

ΫϩʔϯΛଟ͘‫ݕ‬ग़͢Δ͜ͱ͕Ͱ͖ɼ͔ͭ‫ݕ‬ग़࿙Ε͸গͳ͘ͳਖ਼ղ‫ݕ‬ग़਺

31

6

3Δ͕ɼܽؕࣄྫΛ࣋ͨͳ͍ίʔυΫϩʔϯ΋ଟ͘‫ݕ‬ग़͢Δ͜ͱ

࠶‫཰ݱ‬

0.53

0.86

0.75

͕Θ͔ͬͨɽ·ͨɼCCFinder ͱൺ΂Δͱɼؔ਺Ϋϩʔϯ‫ݕ‬ग़

ద߹཰

0.01

0.16

0.3

F஋

0.02

0.27

0.43

͜ͷ݁ՌΛ·ͱΊΔͱɼؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧʹؔͯ͠͸ɼπʔϧͷᮢ஋ʹؔ܎ͳ͘ CCFinder ͷ΄͏͕ܽؕࣄྫΛ࣋ͭίʔυΫϩʔϯΛଟ͘‫ݕ‬ग़͢Δ͜ͱ͕Ͱ͖Δ͕ɼܽؕࣄྫΛ࣋ͨͳ͍ίʔυΫϩʔϯ΋ଟ͘‫ݕ‬ग़ͨ͜͠ͱ͕Θ͔ͬͨɽ·ͨɼؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧͱ CCFinder ͷ‫ݕ‬ग़݁Ռ͔Βɼɹ N1ʙN4 ͷධՁͰ͸ɼධՁηοτͷίʔυΫϩʔϯରͯ྆͠πʔϧʹ௕ॴɼ୹ॴ͕͋Δ͜ͱ͕෼͔ͬͨɽͦͷͨΊ͜ΕΒfalse positive ͱ false negative ͷ਺ྔతͳධՁ͕Ͱ͖ͳ͍ɽಉ

2 ͭͷπʔϧΛ্ख͘࢖͍෼͚Ε͹ɼܽؕͷಉ࣌मਖ਼Λ༗ޮతҰΫϩʔϯηοτʹ‫ݕ‬ग़͞Εͯͳ͍ίʔυΫϩʔϯͱ‫ݕ‬ग़͞Εʹߦ͑Δ͜ͱ͕Θ͔ΔɽCCFinder ͸λΠϓ 1ɼ2 ͷίʔυΫͨίʔυΫϩʔϯ͕ࠞࡏ͍ͯ͠ΔՄೳੑ΋͋Δɽ͜ͷ໰୊Λղϩʔϯ͔͠‫ݕ‬ग़Ͱ͖ͳ͍͕ɼؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧ͸λΠϓ

ফ͢ΔͨΊʹɼͦΕͧΕͷπʔϧͰ࠶‫཰ݱ‬ɼద߹཰ɼF ஋Λ‫ܭ‬3ɼ4 ͷίʔυΫϩʔϯ·Ͱ‫ݕ‬ग़͢Δ͜ͱ͕Ͱ͖Δɽ͔͠͠ɼؔ

ࢉͨ͠ɽͦͷ݁ՌΛද 2 ʹࣔ͢ɽ͜ͷද͔ΒΘ͔ΔΑ͏ʹɼؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧͰ͸ɼؔ਺୯ҐͰྨࣅ͓ͯ͠Βͣɼؔ਺਺Ϋϩʔϯ‫ݕ‬ग़πʔϧ͸ᮢ஋Λ 0.9 ͔Β 0.5 ʹԼ͛Δͱ࠶‫཰ݱ‬ͷ͘͝Ұ෦͕ྨࣅ͍ͯ͠ΔΑ͏ͳίʔυΫϩʔϯΛ‫ݕ‬ग़͢Δ͜

্͕͕Γɼద߹཰͕େ෯ʹԼ͕͍ͬͯΔɽ·ͨɼCCFinder ͱͱ͕Ͱ͖ͳ͍ɽͦ͜Ͱɼ྆πʔϧΛ૊Έ߹Θͤͯར༻͢Δ͜ͱൺ΂Δͱɼؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧͷᮢ஋͕ 0.9 ͷ৔߹͸ɼ࠶Λߟ͑ͯΈͨɽ྆πʔϧͷ࿨ू߹Λऔͬͨ৔߹ͷɼ࠶‫ͱ཰ݱ‬ద‫͕཰ݱ‬௿͘ͳΓద߹཰͸େ෯ʹߴ͘ͳ͓ͬͯΓɼᮢ஋͕ 0.5 ͷ߹཰ͱ F ஋Λද 4 ʹ·ͱΊͨɽ

—5—

ද 4 ؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧͱ CCFinder ͷ࿨ू߹ͷੑೳ
CCFinder ͱ
CCFinder ͱؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧ ؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧ(ᮢ஋ 0.9)(ᮢ஋ 0.5)
࠶‫཰ݱ‬

0.71

0.76

ద߹཰

0.02

0.02

F஋

0.04

0.05

[5]

[6]

[7]

CCFinder ͱؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧΛ૊Έ߹Θͤͯར༻͢
Δ৔߹ɼද 2 ʹ·ͱΊ͍ͯΔ྆πʔϧΛ୯ମͰར༻ͨ͠ͱ͖ʹ[8]ൺ΂ͯ࠶‫͕཰ݱ‬େ෯ʹ্͕Δɽద߹཰ͱ F ஋ʹؔͯ͠͸ɼؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧ୯ମͷᮢ஋ 0.9 ͷ࣌ʹൺ΂Δͱେ෯ʹԼ[9]͕ͬͯ͠·͏͕ɼᮢ஋ 0.5 ͷ࣌ͱ CCFinder ୯ମͷͱ͖ͱ͸΄ͱΜͲมΘΒͳ͍ɽΑͬͯɼ‫ݕ‬ग़͢Δࡍͷίετ͕‫͞ڐ‬ΕΔͷ

[10]Ͱ͋Ε͹ɼؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧͱ CCFinder ͷ྆ऀΛซ༻
͢Δ͜ͱʹΑΓɼܽؕΛ‫ؚ‬Ήίʔυยʹରͯ͠ಉܽؕ͡Λ‫ؚ‬ΉίʔυΫϩʔϯΛΑΓଟ͘‫͚ͭݟ‬Δ͜ͱ͕Ͱ͖Δͱߟ͑Δɽ

[11]
[12]

6. ·ͱΊͱࠓ‫ޙ‬ͷ՝୊ຊ‫Ͱڀݚ‬͸ɼؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧʹ͍ͭͯɼܽؕΛ‫ؚ‬ΉίʔυΫϩʔϯ‫ݕ‬ग़ʹ͓͚Δ༗ޮੑͷධՁΛߦͬͨɽ۩ମతʹ[13]͸ɼؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧͱ CCFinder Λ࢖ͬͯɼLi Β͕༻ҙͨ͠ධՁηοτ [14] ʹରͯ͠ίʔυΫϩʔϯ‫ݕ‬ग़Λߦͬͨɽͦͷ݁Ռɼؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧ͸ɼ࠶‫Ͱ཰ݱ‬΍΍ CCFinder[14]ʹྼ͕ͬͨɼద߹཰ͱ F ஋ʹ͍ͭͯߴ͍஋Λදͨ͜͠ͱ͕Θ
͔ͬͨɽ

[15]

ɹࠓ‫ޙ‬ͷ՝୊ͱͯ͠͸ɼ·ͣɼؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧͷద੾ͳᮢ஋Λ‫ٻ‬ΊΔ͜ͱ͕ߟ͑ΒΕΔɽຊ‫Ͱڀݚ‬ར༻ͨ͠ධՁηο[16]τʹରͯ͠ɼؔ਺Ϋϩʔϯ‫ݕ‬ग़πʔϧͷᮢ஋Λ 0.6ɼ0.7ɼ0.8ͷͦΕͧΕʹઃఆͨ͠৔߹ʹ͍ͭͯ΋‫ݕ‬ग़Λߦͬͯɼͦͷ݁Ռͷ࠶‫ͱ཰ݱ‬ద߹཰ͱ F ஋Λ‫ٻ‬Ίͯൺ΂Δ༧ఆͰ͋Δɽͦͯ͠ɼ

[17]

CCFinder ͷ࠷খҰகτʔΫϯ਺ʹ͍ͭͯ΋ద੾ͳ஋Λߟ͑Δ
ඞཁ͕͋Δͱߟ͑ΒΕΔɽܽؕࣄྫ͝ͱʹద੾ͳ࠷খҰகτʔΫϯ਺Λઃఆ͢Δ͜ͱ͕Ͱ͖Ε͹ɼద߹཰ͱ F ஋͸্ঢ͢Δͱ
ߟ͑ΒΕΔͨΊɼ։ൃऀʹ࠷খҰகτʔΫϯ਺Λܽؕࣄྫ͝ͱ
ʹઃఆͯ͠΋Β͍ͳ͕Β CCFinder Λར༻ͯ͠΋Β͏ධՁ΋ඞ
ཁͰ͋Δͱߟ͑ΒΕΔɽ

[18]
[19]

Anna, and Lorraine Bier. Clone detection using abstract
syntax trees. In Proc. of ICSM, pp. 368–377, 1998.
ං‫ޙ‬๕थ, ೇຊਅೋ, Ҫ্ࠀ࿠. ίʔυΫϩʔϯ‫ݕ‬ग़ͱͦͷ
ؔ࿈ٕज़. ిࢠ৘ใ௨৴ֶձ࿦จࢽ, Vol. J91-D, No. 6, pp.
1465–1481, 2008.
ං‫ޙ‬๕थ, ٢ాଇ༟. ίʔυΫϩʔϯΛର৅ͱͨ͠ϦϑΝΫλϦ
ϯά. ίϯϐϡʔλιϑτ΢ΣΞ, Vol. 28, No. 4, pp. 43–56,
2011.
Yoshiki Higo, Yasushi Ueda, Shinji Kusumoto, and Katsuro
Inoue. Simultaneous modiﬁcation support based on code
clone analysis. In Proc. of APSEC, pp. 262–269, 2007.
Piotr Indyk and Rajeev Motwani. Approximate nearest
neighbors: towards removing the curse of dimensionality.
In Proc. of STOC, pp. 604–613, 1998.
Ҫ্ࠀ࿠, ਆ୩೥༸, ೇຊਅೋ. ίʔυΫϩʔϯ‫ݕ‬ग़๏. ίϯϐϡʔλιϑτ΢ΣΞ, Vol. 18, No. 5, pp. 47–54, 2001.
Lingxiao Jiang, Ghassan Misherghi, Zhendong Su, andStephane Glondu. Deckard: Scalable and accurate treebased detection of code clones. In Proc. of ICSE, pp. 96–
105, 2007.
ਆ୩೥༸, ං‫ޙ‬๕थ, ٢ాଇ༟. ίʔυΫϩʔϯ‫ݕ‬ग़ٕज़ͷల։.
ίϯϐϡʔλιϑτ΢ΣΞ, Vol. 28, No. 3, pp. 29–42, 2011.
Toshihiro Kamiya, Shinji Kusumoto, and Katsuro Inoue.
CCFinder: a multilinguistic token-based code clone detection system for large scale source code. IEEE Trans. Softw.
Eng., Vol. 28, No. 7, pp. 654–670, 2002.
Bruno Lague, Daniel Proulx, Jean Mayrand, Ettobre M.
Merlo, and John Hudepohl. Assessing the beneﬁts of incorporating function clone detection in a development process.
In Proc. of ICSM, pp. 314–321, 1997.
Jingyue Li and Michael D. Ernst. CBCD:Cloned buggy code
detector. Technical report, Computer Science ˍ Engineering, University of Washington, UW-CSE-11-05-02, 2011.
Jingyue Li and Michael D. Ernst. CBCD: Cloned buggy
code detector. In Proc. of ICSE, pp. 310–320, 2012.
Chanchal K. Roy, James R. Cordy, and Rainer Koschke.
Comparison and evaluation of code clone detection techniques and tools: A qualitative approach. Science of Computer Programming, Vol. 74, No. 7, pp. 470–495, 2009.
Chanchal K. Roy, Minhaz F. Zibran, and Rainer Koschke.
The vision of software clone management: Past, present,
and future (keynote paper). In Proc. of CSMR-WCRE, pp.
18–33, 2014.
Ewan Tempero. Towards a curated collection of code clones.
In Proc. of IWSC, pp. 53–59, 2013.
ࢁத༟थ, ቐԸಬ, ٢ాଇ༟, Ҫ্ࠀ࿠. ৘ใ‫ٕࡧݕ‬ज़ʹ‫ߴͮ͘ج‬଎ͳؔ਺Ϋϩʔϯ‫ݕ‬ग़. ৘ใॲཧֶձ࿦จࢽ, Vol. 55, No. 10,
pp. 2245–2255, 2014.

ँࣙ ຊ‫ڀݚ‬Λ࣮ࢪ͢Δʹ͋ͨΓɼ‫و‬ॏͳ͝ҙ‫ݟ‬Λͩͬͨ͘͞೔ຊి‫ࣜגؾ‬ձࣾ ླ໦ ໌඙ ࢯɼલా ௚ਓ ࢯʹ‫͍ͨ͠ँײ‬·͢ɽຊ‫ڀݚ‬͸ JSPS Պ‫ݚ‬අ 25220003ɼ26730036ɼ15H06344
ͷॿ੒Λड͚ͨ΋ͷͰ͢ɽจ‫ݙ‬[1] Alexandr Andoni and Piotr Indyk. Near-optimal hashingalgorithms for approximate nearest neighbor in high dimensions. In Proc. of FOCS, pp. 459–468, 2006.
[2] Ricardo Baeza-Yates and Berthier Ribeiro-Neto. Modern
information retrieval: The concepts and technology behindsearch. Addison-Wesley, 2011.
[3] Brenda S. Baker. Finding clones with dup: Analysis of anexperiment. IEEE Trans. Softw. Eng., Vol. 33, No. 9, pp.
608–621, 2007.
[4] Ira D. Baxter, Andrew Yahin, Leonardo Moura, Marcelo Sant

—6—