Vol.2017-SE-196 No.19
2017/7/20

৘ใॲཧֶձ‫ڀݚ‬ใࠂ
IPSJ SIG Technical Report৘ใ‫ٕࡧݕ‬ज़ʹ‫ͮ͘ج‬ϒϩοΫΫϩʔϯ‫ݕ‬ग़ԣҪ Ұً1,a)ቐ Ըಬ2٢ా ଇ༟3Ҫ্ ࠀ࿠1֓ཁɿιϑτ΢ΣΞอकʹ͓͚Δ໰୊ͷ̍ͭͱͯ͠ίʔυΫϩʔϯʢιʔείʔυதʹଘࡏ͢ΔಉҰ·ͨ͸ྨࣅͨ͠෦෼Λ࣋ͭίʔυยʣ͕ࢦఠ͞Ε͍ͯΔɽ‫ط‬ଘͷ‫͍͓ͯʹڀݚ‬ɼ৘ใ‫ٕࡧݕ‬ज़ʹ‫਺͍ؔͯͮج‬୯ҐͰίʔυΫϩʔϯΛ‫ݕ‬ग़͢Δख๏͕ఏҊ͞Ε͕ͨɼ‫ݕ‬ग़ཻ౓͕େ͖͍ͨΊ‫ݕ‬ग़࿙ΕΛ‫͏͍ͱ͢͜ى‬໰୊఺͕͋Δɽͦ͜Ͱຊ‫Ͱڀݚ‬͸ɼ৘ใ‫ٕࡧݕ‬ज़Λར༻ͨ͠ϒϩοΫΫϩʔϯʢίʔυϒϩοΫ୯ҐͷίʔυΫϩʔϯʣͷ‫ݕ‬ग़ख๏ΛఏҊ͢Δɽ͜ΕʹΑΓɼैདྷͷؔ਺୯ҐͷίʔυΫϩʔϯʹՃ͑ͯΑΓཻ౓ͷখ͍͞ίʔυΫϩʔϯ͕‫ݕ‬ग़Ͱ͖Δͱߟ͑ΒΕΔɽຊख๏Ͱ͸ɼιʔείʔυதͷࣝผࢠ΍༧໿‫ʹޠ‬ར༻͞ΕΔ୯‫ʹޠ‬ରͯ͠ॏΈ෇͚Λߦ͍ɼίʔυϒϩοΫΛಛ௃ϕΫτϧʹม‫͢׵‬Δɽͦͯ͠ɼಛ௃ϕΫτϧؒͷྨࣅ౓Λ‫ٻ‬ΊɼϒϩοΫΫϩʔϯͷ‫ݕ‬ग़Λߦ͏ɽ·ͨධՁ࣮‫Ͱݧ‬͸ɼ‫ط‬ଘͷίʔυΫϩʔϯ‫ݕ‬ग़ख๏ͱൺֱΛߦ͍ɼߴ଎ʹߴ͍ਫ਼౓Ͱ‫ݕ‬ग़Λߦ͏͜ͱ͕Ͱ͖ͨɽ
ΩʔϫʔυɿίʔυΫϩʔϯɼιϑτ΢ΣΞอकɼ৘ใ‫ࡧݕ‬

Block Clone Detection Based on Information Retrieval Techniques
Kazuki Yokoi1,a)Eunjong Choi2

Norihiro Yoshida3

1. ·͕͖͑

Katsuro Inoue1

ຯతʹॲཧ͕ྨࣅͨؔ͠਺୯ҐͷίʔυΫϩʔϯʢؔ਺ΫϩʔϯʣΛ‫ݕ‬ग़͢Δख๏ΛఏҊͨ͠ [13]ɽ৘ใ‫ٕࡧݕ‬ज़ͱιϑτ΢ΣΞͷอकʹ͓͚Δ໰୊ͷͻͱͭͱͯ͠ɼίʔ͸ɼେྔͷσʔλ‫͔܈‬Β໨తʹ߹கͨ͠΋ͷΛऔΓग़͢υΫϩʔϯ͕ࢦఠ͞Ε͍ͯΔ [3]ɽίʔυΫϩʔϯͱ͸ɼ͜ͱͰ͋Γɼࣗવ‫͔ॻͰޠݴ‬ΕͨจॻͷॲཧͳͲʹར༻ιʔείʔυதʹ‫·ؚ‬ΕΔ‫ʹ͍ޓ‬Ұக·ͨ͸ྨࣅͨ͠෦෼

͞ΕΔ [2]ɽίʔυย୯ҐͰ‫ݕ‬ग़Λߦ͏৔߹ɼߏจͷෆ‫׬‬Λ࣋ͭίʔυยͷ͜ͱͰ͋ΓɼҰൠతʹɼίʔυΫϩʔϯશͳ෦෼Ͱऴྃ͢ΔίʔυยͳͲɼू໿Λߦ͏͜ͱ͕ࠔ

ͷଘࡏ͸ιϑτ΢ΣΞͷอकΛࠔ೉ʹ͢Δͱ‫ݴ‬ΘΕ͍ͯΔɽ೉ͳίʔυΫϩʔϯ͕ଟ͘‫ݕ‬ग़͞ΕΔ͜ͱ͕͋Δ [14]ɽҰίʔυΫϩʔϯʹର͢Δ༷ʑͳอक΍؅ཧͷํ๏͕ఏҊํɼؔ਺Ϋϩʔϯ͸ॲཧͷ಺༰͕·ͱ·͍ͬͯΔͨΊɼ։͞Ε͍ͯΔ͕ɼιʔείʔυͷ‫ن‬໛͕େ͖͘ͳΔͱιʔεൃऀʹͱͬͯू໿ͷର৅ʹͳΓ΍͍͢ίʔυΫϩʔϯΛ‫ݕ‬ίʔυதʹ‫·ؚ‬ΕΔίʔυΫϩʔϯ΋๲େͳྔͱͳΓɼख

ग़Ͱ͖ΔɽࢁதΒͷख๏Ͱ͸ɼ৘ใ‫ٕࡧݕ‬ज़ͷҰछͰ͋Δ

࡞‫ͦͰۀ‬ΕΒΛ؅ཧ͢Δ͜ͱ͸ࠔ೉ͱͳΔɽͦ͜Ͱɼίʔ

TF-IDF ๏ [2] Λ༻͍ͯɼιʔείʔυதͷࣝผࢠ΍༧໿‫ޠ‬υΫϩʔϯΛࣗಈతʹ‫ݕ‬ग़͢Δ͜ͱΛ໨తͱ༷ͨ͠ʑͳ

ʹར༻͞ΕΔ୯‫ʹޠ‬ରͯ͠ॏΈ෇͚Λߦ͏ɽͦͯ͠ɼॏΈίʔυΫϩʔϯ‫ݕ‬ग़ख๏͕ఏҊ͞Ε͍ͯΔ [5], [11]ɽ

෇͚ʹ‫਺֤͍ؔͯͮج‬Λಛ௃ϕΫτϧʹม‫͠׵‬ɼಛ௃ϕΫࢁதΒ͸৘ใ‫ٕࡧݕ‬ज़ [2] Λར༻͢Δ͜ͱʹΑͬͯɼҙτϧؒͷྨࣅ౓Λ‫͢ࢉܭ‬Δ͜ͱʹΑͬͯɼؔ਺Ϋϩʔϯͷ‫ݕ‬ग़Λߦ͏ɽ·ͨɼۙࣅ࠷ۙ๣୳ࡧΞϧΰϦζϜͷҰछͰ

1

େࡕେֶOsaka Universityಸྑઌ୺Պֶٕज़େֶӃେֶ
Nara Institute of Science and Technology໊‫ݹ‬԰େֶ
Nagoya University
k-yokoi@ist.osaka-u.ac.jp

͋Δ LSHʢLocality-Sensitive HashingʣΞϧΰϦζϜ [6]c 2017 Information Processing Society of Japan


1

2
3
a)

Λ༻͍ͯɼಛ௃ϕΫτϧΛΫϥελϦϯά͢Δ͜ͱʹΑΓɼ‫ݕ‬ग़ͷߴ଎ԽΛߦ͍ͬͯΔɽ
͔͠͠ɼࢁதΒͷख๏Ͱ͸‫ݕ‬ग़ཻ౓͕ؔ਺୯ҐͷͨΊɼVol.2017-SE-196 No.19
2017/7/20

৘ใॲཧֶձ‫ڀݚ‬ใࠂ
IPSJ SIG Technical Report௕͍ؔ਺಺ͷҰ෦ʹίʔυΫϩʔϯ͕‫·ؚ‬Εͨ৔߹ɼ‫ݕ‬ग़࿙Ε͕ੜ͡ΔՄೳੑ͕͋Δɽ͜ͷΑ͏ͳ‫ݕ‬ग़࿙ΕΛ‫ݮ‬Βͨ͢Ίʹ͸ɼؔ਺୯ҐΑΓখཻ͍͞౓ͰίʔυΫϩʔϯͷ‫ݕ‬ग़Λߦ͏΂͖Ͱ͋Δɽͦ͜Ͱɼຊ‫Ͱڀݚ‬͸ίʔυϒϩοΫ
୯ҐͷίʔυΫϩʔϯʢϒϩοΫΫϩʔϯʣΛ‫ݕ‬ग़͢Δख๏ΛఏҊ͢Δɽ͜͜Ͱ͸ίʔυϒϩοΫΛɼؔ਺ͱɼؔ਺
಺෦ͷ ifɼforɼwhile จ౳ͷத‫Ͱހׅ‬ғ·Εͨ෦෼ͱఆٛ͢
Δɽຊख๏Ͱ͸ɼ·ͣιʔείʔυʹରͯ͠ߏจղੳΛߦ

λΠϓ 3 λΠϓ 2 ͷҧ͍ʹՃ͑ͯɼจͷૠೖ΍࡟আɼมߋͳͲ͕ߦΘΕ͍ͯΔίʔυΫϩʔϯɽ
λΠϓ 4 ྨࣅͨ͠ॲཧΛ࣮ߦ͢Δ͕ɼߏจ্ͷ࣮૷͕ҟͳΔίʔυΫϩʔϯ
λΠϓ 4 ͷίʔυΫϩʔϯͱͯ͠ɼҎԼͷ΋ͷ͕‫͛ڍ‬ΒΕΔɽ• ৚݅෼‫ॲذ‬ཧ΍‫܁‬Γฦ͠ॲཧͳͲͷ੍‫ߏޚ‬଄ͷ࣮૷͕ҟͳΔɽ͍ɼίʔυϒϩοΫͷநग़Λߦ͏ɽͦͷ‫ޙ‬ɼநग़֤ͨ͠ίʔ• தؒഔհม਺ͷར༻ͷ༗ແ͕ଘࡏ͍ͯ͠Δɽ

υϒϩοΫʹରͯ͠ TF-IDF ๏Λ༻͍ͯಛ௃ϕΫτϧʹม• จͷฒͼସ͕͑ൃੜ͍ͯ͠Δɽ‫͠׵‬ɼಛ௃ϕΫτϧؒͷྨࣅ౓Λ‫͢ࢉܭ‬Δ͜ͱͰϒϩοΫΫϩʔϯͷ‫ݕ‬ग़Λߦ͏ɽ·ͨɼMulti-Probe LSH [9] Λ࢖༻

2.1 ؔ਺Ϋϩʔϯ‫ݕ‬ग़๏ͯ͠ಛ௃ϕΫτϧͷΫϥελϦϯάΛߦ͏ɽMulti-ProbeࢁதΒ͸৘ใ‫ٕࡧݕ‬ज़Λར༻͢Δ͜ͱʹΑͬͯɼҙຯత

LSH ͱ͸ɼैདྷͷ LSH ͷϝϞϦ࢖༻ྔ͕ଟ͍ͱ͍͏໰୊

ʹॲཧ͕ྨࣅͨؔ͠਺ΫϩʔϯΛ‫ݕ‬ग़͢Δख๏ΛఏҊ͠఺Λվྑͨ͠ΞϧΰϦζϜͰ͋ΔɽʢҎ߱ɼ୯ʹ“LSH”ͱදͨɽίʔυย୯ҐͰίʔυΫϩʔϯͷ‫ݕ‬ग़Λߦ͏৔߹ɼߏ

‫ͨ͠ه‬৔߹͸ LSH ΞϧΰϦζϜશൠΛࢦ͠ɼLSH Ξϧΰจͷෆ‫׬‬શͳ෦෼Ͱऴྃ͢ΔίʔυยͳͲɼू໿Λߦ͏͜ϦζϜΛ۠ผ͢Δࡍ͸“Multi-Probe LSH”ɼ“ैདྷͷ LSH”

ͱ͕ࠔ೉Ͱ͋ΔίʔυΫϩʔϯ͕ଟ͘‫ݕ‬ग़͞ΕΔ‫ڪ‬Ε͕͋ͱ͍͏ද‫ه‬Λ༻͍Δʣ͜ͷ͜ͱͰɼΑΓগͳ͍ϝϞϦ࢖༻Δ [14]ɽҰํɼؔ਺Ϋϩʔϯ͸ॲཧͷ಺༰͕·ͱ·͍ͬͯྔͰߴ଎ͳ‫ݕ‬ग़Λ࣮‫ͨ͠ݱ‬ɽΔͨΊɼ։ൃऀʹͱͬͯू໿ͷର৅ʹͳΓ΍͍͢ίʔυΫධՁ࣮‫Ͱݧ‬͸ɼؔ਺Ϋϩʔϯ‫ݕ‬ग़๏ [13] ͱ CCFinder [7]ϩʔϯ͕‫ݕ‬ग़Ͱ͖Δɽ·ͨؔ਺Ϋϩʔϯ‫ݕ‬ग़๏͸ɼλΠϓ

ͷ 2 ͭͱ‫ݕ‬ग़ਫ਼౓ͱ‫ݕ‬ग़࣌ؒͷ‫͔఺؍‬ΒൺֱΛߦͬͨɽ1 ͔ΒλΠϓ 4 ·ͰͷίʔυΫϩʔϯΛ‫ݕ‬ग़ՄೳͰ͋Δɽ

CCFinder ͸ਆ୩Β͕։ൃͨ͠ίʔυΫϩʔϯ‫ݕ‬ग़πʔϧ͜ͷख๏͸ɼ·ͣɼೖྗ͞ΕͨιʔείʔυதͷϫʔυʹͰ͋Γɼࣈ۟୯ҐͷίʔυΫϩʔϯ‫ݕ‬ग़͕ՄೳͰ͋Δɽ3‫਺֤͍ؔͯͮج‬Λಛ௃ϕΫτϧʹม‫͢׵‬Δɽ͜͜Ͱϫʔυͭͷ C ‫ޠݴ‬ͷϓϩδΣΫτʹରͯ͠ద༻ͨ݁͠Ռɼຊख๏

ͱ͸ɼҎԼͷ 2 ͭΛର৅ͱ͢Δɽ

͕૯߹తʹߴ͍ਫ਼౓ͰΑΓଟ͘ͷίʔυΫϩʔϯΛ‫ݕ‬ग़͢• ม਺΍ؔ਺ͳͲʹ͚ͭΒΕͨࣝผࢠ໊Λߏ੒͢Δ୯‫ޠ‬Δ͜ͱ͕Ͱ͖ͨɽ·ͨɼຊख๏ͷ‫ݕ‬ग़ʹ͔͔Δ࣌ؒ͸ 3 ෼• ৚݅จ΍‫܁‬Γฦ͠จͳͲͷߏจʹར༻͞ΕΔ༧໿‫ޠ‬ҎԼͱͳΓɼؔ਺Ϋϩʔϯ‫ݕ‬ग़๏ͱ CCFinder ΑΓ΋ߴ଎ͦͯ͠ɼಛ௃ϕΫτϧؒͷྨࣅ౓Λ‫ٻ‬ΊΔ͜ͱʹΑͬͯΫʹίʔυΫϩʔϯΛ‫ݕ‬ग़͢Δ͜ͱ͕Ͱ͖ͨɽ·ͨɼ‫ݕ‬ग़࣌ϩʔϯϖΞͷू߹ΛϦετͱͯ͠ग़ྗ͢Δɽ·ͨɼྨࣅ౓

ؒͱεέʔϥϏϦςΟͷධՁ΋ߦ͍ɼ100MLOC ͷେ‫ن‬໛ͷ‫ࢉܭ‬ͷ௚લʹ LSH [6] Λར༻͠ɼಛ௃ϕΫτϧͷΫϥε

ϓϩδΣΫτʹରͯ͠ 4 ࣌ؒఔ౓Ͱ‫ݕ‬ग़Ͱ͖Δ͜ͱΛ֬ೝλϦϯάΛߦ͏͜ͱʹΑͬͯɼ‫ݕ‬ग़ͷߴ଎ԽΛߦ͍ͬͯΔɽͨ͠ɽҎ߱ɼ2 ষͰ͸ɼίʔυΫϩʔϯͱؔ਺Ϋϩʔϯ‫ݕ‬ग़๏

2.2 ؔ਺Ϋϩʔϯ‫ݕ‬ग़๏ͷ໰୊఺ʹ͍ͭͯड़΂Δɽ3 ষͰ͸ɼຊ‫Ͱڀݚ‬ఏҊ͢ΔϒϩοΫΫ

2.1 અͰ͸ɼؔ਺Ϋϩʔϯ‫ݕ‬ग़๏ͷ֓ཁʹ͍ͭͯઆ໌͠

ϩʔϯ‫ݕ‬ग़๏ʹ͍ͭͯड़΂Δɽ4 ষͰ͸ɼຊख๏ͷධՁ࣮ͨɽ͔͠͠ɼؔ਺Ϋϩʔϯ‫ݕ‬ग़๏ʹରͯ͠ҎԼͷ 2 ͭͷ໰‫͍ͯͭʹݧ‬ड़΂Δɽ࠷‫ʹޙ‬ɼ5 ষͰ·ͱΊͱࠓ‫ޙ‬ͷ՝୊ʹ୊఺͕‫͛ڍ‬ΒΕΔɽ

͍ͭͯड़΂Δɽ

2. ίʔυΫϩʔϯຊষͰ͸ɼຊ‫ڀݚ‬ͷഎ‫ͯ͠ͱܠ‬ίʔυΫϩʔϯɼ͓ΑͼࢁதΒͷؔ਺Ϋϩʔϯ‫ݕ‬ग़๏ͱɼͦͷ໰୊఺ʹ͍ͭͯड़΂

1 ͭ໨͸ɼؔ਺୯Ґͷ‫ݕ‬ग़ʹΑΔ໰୊఺Ͱ͋Δɽ͜ͷख๏͸ɼؔ਺શମͰ͸ͳ͘ɼҰ෦ͷΈ͕ίʔυΫϩʔϯʹͳ͍ͬͯΔ΋ͷΛ‫ݕ‬ग़͢Δ͜ͱ͕Ͱ͖ͳ͍ɽྫ͑͹ਤ 1 ͷΑ͏ʹɼ௕͍ؔ਺಺ͷҰ෦ʹίʔυΫϩʔϯ͕‫·ؚ‬ΕΔ৔߹ɼ‫ݕ‬ग़࿙Ε͕ੜ͡ΔՄೳੑ͕͋Δɽ

ΔɽRoy Β͸ίʔυΫϩʔϯͷఆٛͱͯ͠ɼίʔυΫϩʔ

2 ͭ໨͸ɼϝϞϦ࢖༻ྔ͕ଟ͍ͱ͍͏໰୊఺Ͱ͋Δɽؔϯؒͷҧ͍ͷ౓߹͍ʹ‫͖ͮج‬ҎԼͷ 4 ͭͷλΠϓʹ෼ྨ͠਺Λಛ௃ϕΫτϧʹม‫͢׵‬Δํ๏ͱͯؔ͠਺Ϋϩʔϯ‫ݕ‬ग़͍ͯΔ [12]ɽ

๏͸ TF-IDF ๏Λ༻͍͍ͯΔ͕ɼTF-IDF ๏Ͱ͸શؔ਺ͰλΠϓ 1ۭന΍λϒͷ༗ແɼίʔσΟϯάελΠϧɼίग़‫ͨ͠ݱ‬ϫʔυͷछྨ਺͕࣍‫ͳͱ਺ݩ‬ΔͨΊɼಛ௃ϕΫτϝϯτͷ༗ແͳͲͷҧ͍Λআ͖‫׬‬શʹҰக͢Δίʔυϧͷ࣍‫͕਺ݩ‬ඇৗʹେ͖͘ͳΔ܏޲ʹ͋Δɽಛ௃ϕΫτϧΫϩʔϯ.

͸֤ؔ਺ʹ 1 ‫ͭͣݸ‬༩͑ΔͨΊɼ࣍‫਺ݩ‬ͷେ͖͍ಛ௃ϕΫ

λΠϓ 2

λΠϓ 1 ͷҧ͍ʹՃ͑ͯɼม਺໊ͳͲͷϢʔβʔఆ໊ٛɼม਺ͷ‫͕Ͳͳܕ‬ҟͳΔίʔυΫϩʔϯ.

c 2017 Information Processing Society of JapanτϧΛଟ਺อ࣋͢Δ͜ͱʹͳΓɼϝϞϦ࢖༻ྔ͕େ͖͘ͳ
Δɽ·ͨɼߴ଎ʹ‫ݕ‬ग़Λߦ͏ͨΊʹ LSH Λ༻͍ͯΫϥελ2

Vol.2017-SE-196 No.19
2017/7/20

৘ใॲཧֶձ‫ڀݚ‬ใࠂ
IPSJ SIG Technical Report Ƈ Ƈ㛗ſ ƀƇʰɥŚ
ʰɨŚ
ƈ厦㛵ſ ƀƇʰɥŚ
ʰɨŚ
ƈ

୍⮴㒊ศ

ᩘ
ƈ

ਤ 1

ͦͷͨΊɼಛ௃ϕΫτϧͷΫϥελϦϯάͰ͸ɼLSH [6] ͷҰछͰ͋Γɼۭؒ‫ྔࢉܭ‬ͷվྑΛߦͬͨ Multi-Probe LSH[9] Λద༻ͨ͠ɽ
3.1 ༻‫ޠ‬ͷఆٛƈ௕͍ؔ਺಺ͷҰ෦ʹίʔυΫϩʔϯΛ‫ؚ‬Ήྫ

Fig. 1 An example of parts oflong function containing code clones

3.1.1 ίʔυϒϩοΫ
ϓϩάϥϛϯά‫͍͓ͯʹޠݴ‬ɼෳ਺ͷ໋ྩจΛҰ‫ׅ‬Γʹ·ͱΊͨ΋ͷΛίʔυϒϩοΫͱ͍͏ɽଟ͘ͷϓϩάϥϛ
ϯά‫Ͱޠݴ‬͸ɼίʔυϒϩοΫΛೖΕࢠߏ଄ʹ͢Δ͜ͱ͕
Ͱ͖ɼม਺ͷείʔϓͱͯ͠ͷҙຯΛ࣋ͭ͜ͱ͕͋Δɽ

ϦϯάΛߦ͍ͬͯΔ͕ɼLSH ͸ਫ਼౓Λ্͛ΔͱϝϞϦ࢖༻ຊख๏Ͱ͸ɼҎԼͷ 2 ͭͷ৚݅ͷ͍ͣΕ͔Λຬͨ͢ίʔྔ͕େ͖͘ͳΔಛ௃͕͋ΔɽΑͬͯɼେ‫ن‬໛ϓϩδΣΫτ

υϒϩοΫΛ‫ݕ‬ग़ର৅ͱ͢Δɽର৅‫ޠݴ‬͸ C ‫ ͱޠݴ‬Java

ʢLinux Kernel ౳ʣʹରͯ͠ίʔυΫϩʔϯͷ‫ݕ‬ग़Λߦͬ‫͢ͱޠݴ‬Δɽ

ͨ৔߹ɼϝϞϦෆ଍Ͱ‫ݕ‬ग़Λ‫ڪ͍ͳ͖Ͱྃ׬‬Ε͕͋Δɽ

৚݅ 1 ؔ਺ͷ“{ }”Ͱғ·Εͨൣғͦ͜Ͱɼ্ͷ 2 ͭͷ໰୊఺Λ౿·͑ͨ৽͍͠ίʔυΫϩʔϯ‫ݕ‬ग़๏ͷඞཁੑ͕ߟ͑ΒΕΔɽຊ‫Ͱڀݚ‬͸ؔ਺୯Ґ

৚݅ 2 ifɼelseɼforɼwhileɼdo-whileɼswitch จͷ“{ }”Ͱғ·ΕͨൣғΑΓ‫ݕ‬ग़ཻ౓Λখͨ͘͞͠ɼίʔυϒϩοΫ୯Ґͷίʔυͨͩ͠ɼ‫ݱ͕”} {“ʹޙ‬Εͳ͍୯จͷ໋ྩจ͸ίʔυϒϩοΫϩʔϯ‫ݕ‬ग़๏ΛఏҊͨ͠ɽίʔυϒϩοΫ୯ҐͰ‫ݕ‬ग़ΛΫͱͯ͠ͷవ·Γ͕ͳ͍ͨΊ‫ݕ‬ग़ର৅ͱ͠ͳ͍ɽ·ͨਤ 3ߦ͏͜ͱͰɼؔ਺Ϋϩʔϯ‫ݕ‬ग़๏Ͱ͸‫ݕ‬ग़Ͱ͖ͳ͔ͬͨ

ͷ Block A ʹର͢Δ Block B ΍ Block C ͷΑ͏ʹɼೖΕίʔυΫϩʔϯΛ‫ݕ‬ग़͕ՄೳʹͳΔɽ·ͨɼۭؒ‫ྔࢉܭ‬ͷࢠߏ଄ͷ಺ଆͷίʔυϒϩοΫ΋‫ݕ‬ग़ՄೳͰ͋Γɼ‫ݕ‬ग़ରগͳ͍ಛ௃ϕΫτϧͷ࣮૷ํ๏΍ LSH ʹมߋ͢Δ͜ͱͰɼ৅Λ࠶‫ؼ‬తʹ୳ࡧ͢Δɽେ‫ن‬໛ϓϩδΣΫτ΁ͷద༻͕ՄೳͱͳΔɽ

3.1.2 ϫʔυ

3. ఏҊ͢Δ‫ݕ‬ग़ख๏ຊ‫Ͱڀݚ‬͸ɼ2.1 અͰઆ໌ͨ͠ࢁதΒͷؔ਺Ϋϩʔϯ‫ݕ‬ग़๏Λ‫ʹج‬ɼίʔυϒϩοΫ୯ҐͷΫϩʔϯ‫ݕ‬ग़ʹରԠ͢
ΔΑ͏มߋͨ͠ख๏ʢϒϩοΫΫϩʔϯ‫ݕ‬ग़๏ʣΛఏҊ͢Δɽຊख๏ͷ֓ཁΛਤ 2 ʹࣔ͢ɽຊख๏͸ओʹҎԼͷ 5 ͭͷεςοϓͰ࣮ߦ͞ΕΔɽ

STEP 1 ߏจղੳΛߦ͍ιʔείʔυ͔Βந৅ߏจ໦
Λੜ੒͠ɼੜ੒ͨ͠ந৅ߏจ໦͔ΒίʔυϒϩοΫ
ʢ3.1.1 અࢀরʣΛऔΓग़͢ɽ

STEP 2 STEP 1 Ͱநग़֤ͨ͠ίʔυϒϩοΫ͔Βɼϫʔυʢ3.1.2 અࢀরʣͷநग़Λߦ͏ɽຊख๏Ͱ͸ҎԼͷ৚݅ 3ɼ4 ͷ͍ͣΕ͔Λຬͨ͢΋ͷΛϫʔυͱͯ͠ఆٛ͢Δɽ
৚݅ 3 ༧໿‫ޠ‬
৚݅ 4 ࣝผࢠ໊Λߏ੒͢Δ୯‫ޠ‬ࣝผࢠ໊͕ෳ਺ͷ୯‫͔ޠ‬Βߏ੒͞ΕΔ৔߹ɼҎԼͷํ๏Ͱϫʔυ୯Ґʹ෼ׂ͢Δɽ• ϋΠϑϯ΍ΞϯμʔείΞͳͲͷ۠੾Γ‫ʹ߸ه‬ΑΔ෼ׂ• ࣝผࢠ໊தͷେจࣈʹͳ͍ͬͯΔΞϧϑΝϕοτʹΑΔ෼ׂ·ͨɼ2 จࣈҎԼͷࣝผࢠ͸ɼͦΕΒΛ·ͱΊͯಉҰͷϝλϫʔυͱͯ͠ѻ͏ɽྫ͑͹ɼ‫܁‬Γฦ͠จ౳ͰΑ͘ར༻͞

STEP 3 TF-IDF ๏Λར༻͠ɼSTEP 2 Ͱநग़ͨ͠ϫʔ

ΕΔ i ΍ j ͱ͍ͬͨม਺͸ɼҙຯ৘ใ͕ࠐΊΒΕ͍ͯͳ͍υʹॏΈ෇͚Λߦ͍ɼ֤ίʔυϒϩοΫΛಛ௃ϕΫτม਺ͱͯ͠ѻ͏ͨΊͰ͋Δɽ͞Βʹɼ৚݅෼‫͍༻ʹذ‬ΒΕϧʹม‫͢׵‬Δɽ

Δ if ΍ whileɼ‫܁‬Γฦ͠ʹ༻͍ΒΕΔ for ΍ while ౳ͷ༧໿STEP 4 LSH Λར༻͠ɼSTEP 3 Ͱ‫ٻ‬Ί֤ͨίʔυϒϩοΫʹର͢Δಛ௃ϕΫτϧͷΫϥελϦϯάΛߦ͏ɽ

STEP 5 STEP 4 Ͱ‫ٻ‬ΊͨίʔυϒϩοΫͷ֤ΫϥελͷதͰɼಛ௃ϕΫτϧؒͷྨࣅ౓ͷ‫ࢉܭ‬Λߦ͍ɼϒϩοΫΫϩʔϯʢ3.1.3 અࢀরʣΛ‫ݕ‬ग़͢Δɽ
ຊख๏ͱؔ਺Ϋϩʔϯ‫ݕ‬ग़๏ͷओͳ૬ҧ఺͸ɼίʔυΫϩʔϯͷ‫ݕ‬ग़ཻ౓Ͱ͋Δɽؔ਺Ϋϩʔϯ‫ݕ‬ग़๏Ͱ͸ؔ਺ͷ‫ݕ‬ग़ͷΈΛߦ͏͕ɼຊख๏Ͱ͸ಛ௃ϕΫτϧͷ‫ํࢉܭ‬๏΋มߋ͠ɼؔ਺ͱؔ਺಺ͷίʔυϒϩοΫͷ྆ํΛ‫ݕ‬ग़͢Δɽ

‫ޠ‬΋ϫʔυͱͯ͠ѻ͏ɽͳ͓ɼ֤ϫʔυͷେจࣈͱখจࣈ
ʹΑΔ۠ผ͸͚ͭͣɼಉҰͷϫʔυͱͯ͠ѻ͏ɽ

3.1.3 ϒϩοΫΫϩʔϯ
৚݅ 5 ίʔυϒϩοΫؒͷྨࣅ౓͕ᮢ஋Ҏ্sim(CB1 , CB2 ) ≥ p(0 ≤ p ≤ 1)

৚݅ 6 ίʔυϒϩοΫؒʹ‫ڞ‬௨෦෼͕ͳ͍

CB1 ∩ CB2 = φ͔͠͠ɼຊख๏͸‫ݕ‬ग़ཻ౓Λখ͘͢͞Δ͜ͱͰ‫ݕ‬ग़ର৅

CB1 ɼCB2 ͦΕͧΕΛਅʹแ‫ؚ͢‬Δ೗ԿͳΔίʔυϒ਺͕૿͑ɼͦΕʹ൐͍‫ݕ‬ग़࣌ؒɼϝϞϦ࢖༻ྔ͕૿େ͢Δɽ

ϩοΫ΋ϒϩοΫΫϩʔϯϖΞͰͳ͍ͱ͖ɼCB1 ɼCB2 Λ

c 2017 Information Processing Society of Japan

3

Vol.2017-SE-196 No.19
2017/7/20

৘ใॲཧֶձ‫ڀݚ‬ใࠂ
IPSJ SIG Technical Report

^dWϭ

^dWϮ

^dWϯ

^dWϰ

^dWϱ

䝤䝻䝑䜽 ὁὊἛ ‫ׅ‬ૠ
ᶖᶖᶖ ᵑ
ᶗᶗᶗ ᵐ
Ḡ
Ḡ

䝤䝻䝑䜽 
ଵ , ଶ , ଷ , ⊃

䝤䝻䝑䜽
䝤䝻䝑䜽

䝤䝻䝑䜽

䝋䞊䝇䝁䞊䝗ὁὊἛ ‫ׅ‬ૠ
ᶖᶖᶖ ᵒ
ᶗᶗᶗ ᵐ
Ḡ
Ḡ

ᢳ㇟ᵓᩥᮌ

䝤䝻䝑䜽
䝤䝻䝑䜽
䝤䝻䝑䜽

䝤䝻䝑䜽
ଵ , ଶ , ଷ , ⊃䝽䞊䝗䝸䝇䝖 ≉ᚩ䝧䜽䝖䝹
ਤ 2

䜽䝷䝇䝍

᫏˩ࡇ ⇼∓⇩⇕‫⇕ݣ‬∓∞∙⇼∓⇩⇕″ ‫ݱ‬•†‫‧‫‬
⇼∓⇩⇕‴
⇼∓⇩⇕‵
•† •
⇼∓⇩⇕‶
⇼∓⇩⇕‶ ‫ݱ‬•†‫•‫‬⇼∓⇩⇕‷⃴⃴⃴

䜽䝻䞊䞁䝨䜰䝸䝇䝖ఏҊख๏ͷ֓ཁ

Fig. 2 An overview of our detection approachůŽĐŬ Ƈ ƇſƀƇſƀƇƈůŽĐŬ ůŽĐŬ

ſƀƇʰɥŚƈůŽĐŬ

ſƀƇ
ʰɥŚ
ƈ

ʰɨŚ

ƈ

ƈ

ਤ 3

3.2 ίʔυϒϩοΫͱϫʔυͷநग़ຊख๏Ͱ͸ߏจղੳΛߦ͍ɼίʔυϒϩοΫͷநग़ΛߦůŽĐŬ ͏ɽίʔυϒϩοΫநग़ͷख๏͸ҎԼͷ 6 ͭͷεςοϓʹ
෼͚ΒΕΔɽຊख๏Ͱ͸ɼߏจղੳʹ ANTLR v4*1 Λར༻

ʰɨŚ

ͨ͠ɽ

ƈ

STEP I ιʔείʔυʹରͯ͠ߏจղੳΛߦ͍ɼந৅ߏ

ਤ 4ೖΕࢠߏ଄ʹ͋Δ‫ڞ‬௨෦෼͕͋Δ

ίʔυϒϩοΫ

จ໦Λੜ੒͢ΔɽίʔυϒϩοΫϖΞ

Fig. 3 Code blocks in

Fig. 4 Code block pairnested structure

STEP II ந৅ߏจ໦͔Βؔ਺ʢ3.1.1 અͷ৚݅ 1 Λຬͨ͢ίʔυϒϩοΫʣͷ෦෼໦ΛऔΓग़͢ɽsharing a common part

STEP III STEP II ͰऔΓग़ͨ͠෦෼໦Λ࠷΋֎ଆͷίʔ ƇſƀƇſƀƇ
ʰɥŚ
ƈ
ƈ
ƈ

ਤ 5

υϒϩοΫͱͯ͠நग़͢Δɽ Ƈ

STEP IV STEP II ͰऔΓग़ͨ͠෦෼໦͔ΒɼίʔυϒſƀƇſƀƇ
ʰɥŚ
ƈ



ʰɨŚ

ƈ



ϩοΫʢ3.1.1 અͷ৚݅ 2 Λຬͨ͢ίʔυϒϩοΫʣͷ



ʰɨŚ

෦෼໦ΛऔΓग़͢ɽ

STEP V STEP IV ͰऔΓग़ͨ͠෦෼໦ΛೖΕࢠؔ܎ʹ͋ΔίʔυϒϩοΫͱͯ͠நग़͢Δɽƈ‫ۃ‬େίʔυϒϩοΫϖΞͱॏෳͨ͠ίʔυϒϩοΫϖΞ

STEP VI Ҏ߱ɼਂ͞༏ઌ୳ࡧͰந৅ߏจ໦͔ΒίʔυϒϩοΫΛநग़͢Δɽ

Fig. 5 Code block pair overlappedίʔυϒϩοΫͷநग़‫ޙ‬ɼ֤ίʔυϒϩοΫ಺ʹ‫·ؚ‬Εwith a maximam code block pairΔϫʔυͷநग़Λߦ͏ɽ‫ۃ‬େϒϩοΫΫϩʔϯͱ‫Ϳݺ‬ɽຊख๏Ͱ͸ɼ‫ۃ‬େϒϩοΫΫϩʔϯΛϒϩοΫΫϩʔϯͱఆٛ͢Δɽ

3.3 ಛ௃ϕΫτϧͷ‫ࢉܭ‬

৚݅ 6 Ͱࣔͨ͠Α͏ʹɼϒϩοΫΫϩʔϯϖΞ͸ίʔυಛ௃ϕΫτϧͷ‫Ͱࢉܭ‬͸ɼϫʔυʹର͠ TF-IDF ๏ [2]ϒϩοΫؒʹ‫ڞ‬௨෦෼͕ͳ͍͜ͱ͕৚݅Ͱ͋ΔɽίʔυϒΛར༻ͯ͠ॏΈΛ‫͠ࢉܭ‬ɼͦͷ஋Λಛ௃ྔͱ֤ͯ͠ίʔυϩοΫؒʹ‫ڞ‬௨෦෼͕ଘࡏ͢Δ৔߹ɼҰํͷίʔυϒϩοϒϩοΫΛಛ௃ϕΫτϧʹม‫͢׵‬ΔɽΑͬͯɼ֤ίʔυϒΫ͕ଞํΛแ‫ؚ͍ͯ͠‬Δ͜ͱΛ͍ࣔͯ͠Δɽྫ͑͹ɼਤ 4ϩοΫͷಛ௃ϕΫτϧͷ࣍‫਺ݩ‬͸ιʔείʔυதʹଘࡏ͢ͷίʔυϒϩοΫ A ͱ B ͸‫ڞ‬௨෦෼͕ଘࡏ͠ɼแ‫܎ؚؔ‬Δશϫʔυͷछྨ਺ͱͳΔɽຊख๏Ͱ͸ɼtf ஋͸ίʔυϒʹ͋ΔͨΊϒϩοΫΫϩʔϯϖΞͰͳ͍ɽϩοΫதͷϫʔυͷग़‫ݱ‬ස౓Λɼidf ஋͸ιʔείʔυத

·ͨɼ‫ۃ‬େϒϩοΫΫϩʔϯΛϒϩοΫΫϩʔϯͱఆٛ
͢Δͱ͸ɼ‫͑׵͍ݴ‬ΔͱͦΕͧΕೖΕࢠؔ܎ʹ͋Δίʔυͷϫʔυͷ‫ر‬গ͞Λද͍ͯ͠Δɽtf ஋͸ࣜ (1)ɼidf ஋͸ࣜ(2) Ͱ༩͑ΒΕΔɽ

ϒϩοΫͷྨࣅ౓͕ᮢ஋Ҏ্ͷ৔߹ɼ࠷΋֎ଆͷίʔυϒ

tf i,j = ϩοΫϖΞΛϒϩοΫΫϩʔϯͱ͢Δͱ͍͏ҙຯͰ͋Δɽྫ͑͹ɼਤ 5 ͷίʔυϒϩοΫ A ͱ CɼB ͱ D ͦΕͧΕc 2017 Information Processing Society of Japan


(1)

|F |
|{f : f  wi }|(2)

idf i = logͷྨࣅ౓͕ᮢ஋Ҏ্ͱͳΔ৔߹ɼ࠷΋֎ଆͷίʔυϒϩοΫ A ͱ C ΛϒϩοΫΫϩʔϯͱ͢Δɽ

ni,jk∈bj nk,j*1

http://www.antlr.org/

4Vol.2017-SE-196 No.19
2017/7/20

৘ใॲཧֶձ‫ڀݚ‬ใࠂ
IPSJ SIG Technical Reportද 1͜͜Ͱ͸ɼni,j ͸ίʔυϒϩοΫ bj ಺ʹ͓͚Δϫʔυ wiͷग़‫ݱ‬ճ਺ɼ k∈bj nk,j ͸ίʔυϒϩοΫ bj ʹ͓͚Δશ

‫ݕ‬ग़ର৅ϓϩδΣΫτ

Table 1 Target projectsϫʔυͷग़‫ݱ‬ճ਺ͷ࿨ɼ|F | ͸શؔ਺ͷ਺ɼ|{f : f  wi }|͸ϫʔυ wi ͕ग़‫͢ݱ‬Δؔ਺ͷ਺Λ͍ࣔͯ͠Δɽؔ਺Ϋϩʔϯ‫ݕ‬ग़๏ͱൺֱͯ͠ɼtf ஋ͷ‫ٻ‬ΊํΛίʔυϓϩδΣΫτ

όʔδϣϯ

‫ޠݴ‬

‫ن‬໛

Apache HTTPD*3

2.2.14C/C++

343 KLOC

PostgreSQL*4

8.5.1

C/C++

937 KLOC

Python*5

2.5.1

C/C++

435 KLOC

ϒϩοΫ୯Ґʹมߋ͕ͨ͠ɼidf ஋ͷ‫ٻ‬Ίํ͸ίʔυϒϩοΫ୯Ґʹมߋͤͣؔ਺୯Ґͷ··Ͱ͋ΔɽͳͥͳΒɼίʔυϒϩοΫ୯ҐͰ idf ஋Λ‫ٻ‬ΊΔͱϫʔυͷॏΈ෇͚ʹภ

LSH ͷ࣮૷ͱͯ͠ FALCONN [1]*2 ϥΠϒϥϦΛར༻ͨ͠ɽ

Γ͕ੜͯ͡͠·͏͔ΒͰ͋Δɽ͋Δϫʔυ͕͍ͭ͘ͷίʔυϒϩοΫʹ‫·ؚ‬ΕΔ͔͸ग़‫ݱ‬৔ॴʹΑͬͯҟͳΔɽྫ͑

3.5 ಛ௃ϕΫτϧͷྨࣅ౓ͷ‫ࢉܭ‬͹ɼਤ 4 ͷؔ਺಺ͷม਺ a ͸ϒϩοΫ A ͱ B ͷ 2 ‫ݸ‬ͷίʔຊख๏Ͱ͸ίαΠϯྨࣅ౓Λ༻͍ͯΫϩʔϯϖΞͷ൑ఆυϒϩοΫʹ‫·ؚ‬ΕΔ͕ɼม਺ b ͸ϒϩοΫ A ͷΈʹ͔͠‫·ؚ‬Εͳ͍ɽͦͷͨΊɼιʔείʔυதͷग़‫ݱ‬ճ਺͸ಉ͡Λߦ͏ɽίαΠϯྨࣅ౓͸ଟ࣍‫ݩ‬ϕΫτϧͷྨࣅ౓Λද͢ई౓Ͱ͋Γɼ࣍‫ ͕ݩ‬V Ͱ͋Δ 2 ͭͷಛ௃ϕΫτϧ a, b ؒͷʹ΋ؔΘΒͣɼग़‫͢ݱ‬ΔίʔυϒϩοΫͷ਺͕ҟͳͬͯ͠ྨࣅ౓͸ҎԼͷࣜ (3) Ͱ༩͑ΒΕΔɽ

·͏ɽidf ஋͸ϫʔυͷ‫ر‬গੑʹ‫͍ͯͮج‬ॏΈ෇͚Λߦͬ

sim(a, b) = cos(a, b) = ͍ͯΔͨΊɼภΓΛແͨ͘͢Ίʹؔ਺୯ҐͰ‫ٻ‬Ίͨɽ

3.4 ಛ௃ϕΫτϧͷΫϥελϦϯά

|V |i=1 ai bi|V | 2
|V |
2
a
i=1 i
i=1 bi(3)

TF-IDF ๏ͷ‫ࣜࢉܭ‬ΑΓɼಛ௃ྔ͸ৗʹਖ਼ͷ஋ΛऔΔͨΊɼಛ௃ϕΫτϧͷΫϥελϦϯάͱͯ͠ɼؔ਺Ϋϩʔϯ‫ݕ‬ίαΠϯྨࣅ౓͸ 0 ͔Β 1 ͷൣғͱͳΔɽίαΠϯྨࣅग़๏ͱಉ༷ʹ LSH Λ༻͍ͨɽΫϥελϦϯάΛߦ͏͜ͱ౓͕ᮢ஋Ҏ্Ͱ͋Ε͹ɼͦΕΒ 2 ͭͷίʔυϒϩοΫ͸Ϋ

ʹΑͬͯɼΫϩʔϯϖΞͱͳΓ͏ΔީิΛߜΔ͜ͱ͕Ͱ͖ɼ

ϩʔϯϖΞͰ͋Δͱ൑ఆ͢Δɽ

ߴ଎ͳΫϩʔϯϖΞͷ‫ݕ‬ग़͕ՄೳͱͳΔɽ͔͠͠ɼେ‫ن‬໛ͷσʔληοτΛ LSH ΞϧΰϦζϜΛ༻͍ͯߴ͍ਫ਼౓Ͱ

4. ධՁ࣮‫ݧ‬ຊষͰ͸ɼຊ‫Ͱڀݚ‬ఏҊͨ͠ϒϩοΫΫϩʔϯ‫ݕ‬ग़๏ͷ‫ٻ‬ΊΑ͏ͱ͢ΔͱɼϝϞϦ࢖༻ྔ͕ඇৗʹେ͖͘ͳΔͱ͍
͏໰୊఺͕͋Δ [8], [9].

LSH ͷΞϧΰϦζϜ͸ɼۭؒతʹۙ઀ͨ͠ೋ఺͕ಉ͡
ϋογϡ஋ʹͳΔ֬཰͕ߴ͘ͳΔΑ͏ͳϋογϡؔ਺ΛධՁ࣮‫͍ͯͭʹݧ‬ड़΂ΔɽධՁ࣮‫Ͱݧ‬͸ɼຊख๏ͱ‫ط‬ଘख๏ͱͷൺֱͱɼຊख๏ͷ‫ݕ‬ग़࣌ؒͱεέʔϥϏϦςΟͷධՁΛߦͬͨɽ

༻͍ɼಉ͡ϋογϡ஋ΛऔΔ఺Λಉ͡όέοτʹೖΕΔ͜
ͱͰΫϥελϦϯάΛߦ͏ɽ͔͠͠ LSH ͸֬཰తख๏Ͱ

4.1 ؔ਺Ϋϩʔϯ‫ݕ‬ग़๏ͱ CCFinder ͱͷൺֱ

͋ΔͨΊɼۙ઀ͨ͠ೋ఺͕‫ۮ‬વʹผͷόέοτʹೖΔՄೳ

ຊઅͰ͸ؔ਺Ϋϩʔϯ‫ݕ‬ग़๏ͱ CCFinder [7] ͷ 2 ͭͷੑ͕͋Δɽैདྷͷ LSH Ͱ͸ෳ਺ͷϋογϡؔ਺Λ༻͍Δ‫ط‬ଘख๏ͱͷൺֱ࣮‫͍ͯͭʹݧ‬ड़΂Δɽຊ࣮‫Ͱݧ‬͸ɼର৅͜ͱͰ֬཰తͳ‫ࠩޡ‬Λগͳ͘͠ਫ਼౓Λ্͍͛ͯΔɽͦͷͨϓϩδΣΫτ͔Β࡞੒ͨ͠ϕϯνϚʔΫʹର͢Δ‫ݕ‬ग़ਫ਼Ίɼେ‫ن‬໛ͳσʔληοτʹରͯ͠͸ΑΓଟ਺ͷϋογϡ

౓ͱ‫ݕ‬ग़࣌ؒͷ‫͔఺؍‬ΒൺֱΛߦͬͨɽCCFinder ͸ࠃ಺ؔ਺͕ඞཁͱͳΓɼ͜ΕʹΑΓ LSH ͷϝϞϦ࢖༻ྔͷ૿֎ͷ‫ۀا‬ɾେֶͰ࢖༻͞Ε͍ͯΔͨΊɼൺֱର৅ʹ௥Ճ͠େʹͭͳ͕͍ͬͯΔɽ

ͨɽຊ࣮‫ݕͰݧ‬ग़ର৅ͱͨ͠ϓϩδΣΫτͷҰཡΛද 1 ʹ

ͦ͜ͰɼLv Β͸ϝϞϦ࢖༻ྔͷվྑΛߦͬͨ Multi-Probe

LSH[9] ΛఏҊͨ͠ɽMulti-Probe LSH ͸ɼ͋Δ఺͕ೖΔόࣔ͢ɽ

4.1.1 ϕϯνϚʔΫͷ࡞੒ํ๏έοτ͚ͩͰͳ͘ɼۭؒతʹۙ઀ͨ͠όέοτ‫܈‬΋ௐ΂ΔϕϯνϚʔΫͷ࡞੒͸ҎԼͷ 3 εςοϓͰߦͬͨɽ

ͱ͍͏΋ͷͰ͋Δɽ͜ΕʹΑΓɼগͳ͍ϋογϡؔ਺Ͱ΋( 1 ) ද 1 ͷϓϩδΣΫτʹର͠ɼຊख๏ɼؔ਺Ϋϩʔϯ‫ۮ‬વผͷόέοτʹೖͬͨ఺ͷ‫ݟ‬མͱ͠Λ๷͍Ͱ͍Δɽ࣮‫ݕ‬ग़๏ɼCCFinder ͷ 3 ͭͷख๏ͰίʔυΫϩʔϯΛࡍʹɼ192 ࣍‫ݩ‬ͷσʔληοτʹରͯ͠ಉ͡࠶‫( ཰ݱ‬0.90)‫ݕ‬ग़ɽΛಘΔͨΊʹɼैདྷͷ LSH ͸ 49 ‫ݸ‬ͷϋογϡؔ਺͕ඞཁ

( 2 ) ֤ख๏͕֤ϓϩδΣΫτ͔Β‫ݕ‬ग़ͨ͠ΫϩʔϯϖΞ͔ͩͬͨͷʹର͠ɼMulti-Probe LSH ͸ 3 ‫ݸ‬ͷϋογϡؔ਺Βɼ30 ‫ݸ‬ͷΫϩʔϯϖΞΛϥϯμϜαϯϓϦϯά͠ɼͰ‫ؒ࣌ࡧݕ‬Λ΄΅མͱͣ͞ʹୡ੒ͨ͠ͱ͍͏݁Ռ͕ใࠂ͞߹‫ ܭ‬270 ‫ݸ‬ͷΫϩʔϯϖΞू߹Λ࡞੒ɽΕ͍ͯΔ [9]ɽ
ຊख๏Ͱ͸ϝϞϦ࢖༻ྔͷվྑΛߦ͏ͨΊɼMulti-Probe

LSH Λ༻͍ͯΫϥελϦϯάΛߦ͏ɽͳ͓ɼMulti-Probe( 3 ) (2) Ͱ࡞੒ͨ͠ 270 ‫ݸ‬ͷΫϩʔϯϖΞʹର͠ɼ໨ࢹͰ
*2
*3
*4
*5

c 2017 Information Processing Society of Japan

https://falconn-lib.org/
http://httpd.apache.org/
http://www.postgresql.org/
http://www.python.org/

5Vol.2017-SE-196 No.19
2017/7/20

৘ใॲཧֶձ‫ڀݚ‬ใࠂ
IPSJ SIG Technical Reportද 2ू໿·ͨ͸ಉ࣌मਖ਼ͷอकର৅ͱͳΔίʔυΫϩʔϯ

Table 2 Evaluation of detection accuracy͔ͷ൑அΛߦ͍ɼϕϯνϚʔΫΛ࡞੒ɽͳ͓ɼϕϯνϚʔΫʹ٬‫؍‬ੑΛ࣋ͨͤΔͨΊɼΞϯέʔ‫ݕ‬ग़ख๏

‫ݕ‬ग़ର৅

ద߹཰

࠶‫཰ݱ‬

F஋

Apache HTTPD

0.90

0.74

0.81

PostgreSQL

0.57

0.87

0.69

Python

0.90

0.53

0.67

߹‫ܭ‬

0.68

0.70

0.69

Apache HTTPD

0.87

0.53

0.66

ؔ਺Ϋϩʔϯ

PostgreSQL

0.83

0.74

0.78

‫ݕ‬ग़๏

Python

0.30

0.21

0.25

߹‫ܭ‬

0.67

0.47

0.55

Apache HTTPD

0.70

0.55

0.62

PostgreSQL

0.13

0.33

0.19

Python

0.87

0.63

0.73

߹‫ܭ‬

0.57

0.52

0.54

τʹΑΓୈࡾऀʹίʔυΫϩʔϯͷ൑அΛґཔͨ͠ɽΞϯຊख๏έʔτͷ֓ཁΛҎԼʹࣔ͢ɽௐࠪର৅ҎԼͷ 3 ໊ʹґཔ• ίʔυΫϩʔϯͷ‫ ऀڀݚ‬1 ໊• ίʔυΫϩʔϯͷ‫͍ͯ͠ࣄैʹڀݚ‬ΔେֶӃੜ 2 ໊࣭໰಺༰ू໿·ͨ͸ಉ࣌मਖ਼ͷอकର৅ͱͳΔ͔ճ౴ํࣜೋ୒ʢ͸͍/͍͍͑ʣ্‫ه‬ͷ࣭໰Λɼ‫ݕ‬ग़݁Ռ͔ΒαϯϓϦϯάͨ͠ 270 ‫ݸ‬ͷΫ
CCFinderϩʔϯϖΞʹରͯ͠ߦͬͨɽͦͯ͠ɼա൒਺Ͱ͋Δ 2 ਓҎ্͕ʮ͸͍ʯͱճ౴ͨ͠ΫϩʔϯϖΞΛਖ਼ղͱ͠ɼຊ࣮‫Ͱݧ‬
༻͍Δਖ਼ղΫϩʔϯϖΞू߹ͱͯ͠ϕϯνϚʔΫΛ࡞੒ͨ͠ɽຊ࣮‫Ͱݧ‬͸ɼ֤ϓϩδΣΫτͷਖ਼ղΫϩʔϯϖΞ਺͸ɼද 3Apache HTTPD ͕ 74 ‫ݸ‬ɼPostgreSQL ͕ 46 ‫ݸ‬ɼPythonຊઅͰ͸ɼؔ਺Ϋϩʔϯ‫ݕ‬ग़๏ͱ CCFinder ͱͷൺֱ࣮‫ݕ‬ग़࣌ؒͷൺֱ

Table 3 Comparison of detection time͕ 62 ‫ͨͬͳͱݸ‬ɽ

4.1.2 ൺֱ݁Ռ‫ݕ‬ग़ਫ਼౓ͷධՁ‫ݕ‬ग़ର৅

ຊख๏ؔ਺Ϋϩʔϯ‫ݕ‬ग़๏

CCFinderApache HTTPD

1m 39s

4m 7s

2m 1s

PostgreSQL

2m 27s

8m 47s

5m 30sPython

1m 15s

3m 33s

3m 10s‫ݧ‬ͷ݁Ռʹ͍ͭͯड़΂Δɽຊ࣮‫Ͱݧ‬͸ɼϕϯνϚʔΫΛ༻͍ͨ‫ݕ‬ग़ਫ਼౓ͱ‫ݕ‬ग़࣌ؒͷ‫͔఺؍‬ΒൺֱΛߦͬͨɽ‫ݕ‬ग़ਫ਼౓ͷࢦඪͱͯ͠ɼద߹཰ɼ࠶‫཰ݱ‬ɼF ஋ͷ 3 ͭͷࢦඪΛ༻૯߹తʹ࠶‫͕֬ͱ͍͜ߴ͕཰ݱ‬ೝͰ͖ͨɽ

͍ͨɽຊ࣮‫͚͓ʹݧ‬Δ 3 ͭͷࢦඪΛද 2 ʹࣔ͢ɽ‫ݕ‬ग़࣌ؒ

ద߹཰ຊख๏Ͱ͸ɼApache HTTPD ͱ Python ʹ͓͍ͯɼؔ਺

‫ݕ‬ग़࣌ؒͷൺֱͰ͸ɼද 1 ͷ 3 ͭͷϓϩδΣΫτʹର͢Δ‫ݕ‬ग़࣌ؒΛଌఆͨ͠ɽຊ࣮‫ݧ‬ͷ࣮ߦ‫ڥ؀‬͸ɼCPU IntelΫϩʔϯ‫ݕ‬ग़๏΍ CCFinder ΑΓߴ͍ద߹཰͕ಘΒΕͨɽ

Xeon 2.80GHz 4coreɼϝϞϦ 16GBɼϋʔυσΟεΫυϥ

·ͨɼPostgreSQL ʹ͓͍ͯ͸ɼCCFinder ΑΓ͸ߴ͍దΠϒɼOS Windows 10 64bit Ͱ͋Δɽ߹཰͕ಘΒΕ͕ͨɼؔ਺Ϋϩʔϯ‫ݕ‬ग़๏ΑΓ௿͍ద߹཰ͱ

‫ݕ‬ग़࣌ؒͷൺֱ݁ՌΛද 3 ʹࣔ͢ɽຊख๏Ͱ͸ɼ‫ݕ‬ग़ରͳͬͨɽ3 ͭͷશͯͷϓϩδΣΫτͷ߹‫Ͱܭ‬͸ద߹཰ 0.68

৅શͯͷϓϩδΣΫτʹରͯ͠ 3 ෼ҎԼͰίʔυΫϩʔϯͱɼؔ਺Ϋϩʔϯ‫ݕ‬ग़๏ͱಉఔ౓ͷద߹཰ɼCCFinder ΑΛ‫ݕ‬ग़͕Ͱ͖ͨɽ·ͨɼؔ਺Ϋϩʔϯ‫ݕ‬ग़๏ʹରͯ͠ 3∼4Γߴ͍ద߹཰Ͱ͋Δ͜ͱ͕֬ೝͰ͖ͨɽׂఔ౓ɼCCFinder ʹରͯ͠ 4∼8 ׂఔ౓ͱɼൺֱख๏ΑΓ࠶‫཰ݱ‬΋୹࣌ؒͰ‫ݕ‬ग़͢Δ͜ͱ͕֬ೝͰ͖ͨɽ

ຊख๏Ͱ͸ɼApache HTTPDɼPostgreSQL ʹ͓͍ͯɼؔ਺Ϋϩʔϯ‫ݕ‬ग़๏΍ CCFinder ΑΓߴ͍࠶‫͕཰ݱ‬ಘΒΕͨɽ·ͨɼPython ʹ͓͍ͯ͸ɼؔ਺Ϋϩʔϯ‫ݕ‬ग़๏ΑΓ͸ߴ͍࠶‫͕཰ݱ‬ಘΒΕ͕ͨɼCCFinder ΑΓ௿͍࠶‫཰ݱ‬

4.2 ‫ݕ‬ग़࣌ؒͱεέʔϥϏϦςΟͷධՁຊઅͰ͸ɼఏҊख๏ͷ‫ݕ‬ग़‫ن‬໛͝ͱͷ‫ݕ‬ग़࣌ؒͱεέʔϥϏϦςΟͷධՁʹ͍ͭͯड़΂Δɽ‫ݕ‬ग़ର৅ͷ‫ن‬໛ͷࢦඪͱͳͬͨɽ3 ͭͷશͯͷϓϩδΣΫτͷ߹‫Ͱܭ‬͸ɼ࠶‫཰ݱ‬ʹ͸ίϝϯτ΍ۭߦΛআ͍ͨ LOC Λ༻͍Δ͜ͱͱͨ͠ɽ

0.70 ͱɼؔ਺Ϋϩʔϯ‫ݕ‬ग़๏ͱ CCFinder ΑΓ૯߹తʹ࠶‫ܭ‬ଌʹ͸ cloc*6 Λ༻͍ͨɽ‫ݕ‬ग़ର৅͸ɼIJaDataset 2.0*7 ͔‫͕֬ͱ͍͜ߴ͕཰ݱ‬ೝͰ͖ͨɽ

ΒϥϯμϜʹϑΝΠϧΛબ୒͠ɼද 4 ʹࣔͨ͠ LOC ͝ͱ

F஋ͷαϒηοτγεςϜΛ࡞੒ͨ͠ɽຊ࣮‫ݧ‬ͷ࣮ߦ‫ڥ؀‬͸ɼຊख๏Ͱ͸ɼApache HTTPD ʹ͓͍ͯ F ஋ 0.81 ͱɼؔ

CPU Intel Xeon 2.80GHz 4coreɼϝϞϦ 32GBɼιϦο਺Ϋϩʔϯ‫ݕ‬ग़๏΍ CCFinder ΑΓߴ͍ F ஋͕ಘΒΕͨɽυεςʔτυϥΠϒɼOS Windows 10 64bit Ͱ͋Δɽ·

PostgreSQL ʹ͓͍ͯ͸ F ஋ 0.69 ͱɼCCFinder ΑΓ͸ߴ

ͨɼJava Ծ૝ϚγϯͷελοΫྖҬΛ 1GBɼώʔϓྖҬ͍ F ஋͕ಘΒΕ͕ͨɼؔ਺Ϋϩʔϯ‫ݕ‬ग़๏ΑΓ௿͍ F ஋

Λ 15GB ͱઃఆ࣮ͯ͠ߦͨ͠ɽ

ͱͳͬͨɽ·ͨɼPython ʹ͓͍ͯ͸ F ஋ 0.67 ͱɼؔ਺Ϋ‫ݕ‬ग़࣌ؒͷධՁ݁ՌΛද 4 ʹࣔ͢ɽ͜ΕʹΑΓɼຊख๏ϩʔϯ‫ݕ‬ग़๏ΑΓ͸ߴ͍ F ஋͕ಘΒΕ͕ͨɼCCFinder ΑͰ͸ 100MLOC ͷ‫ݕ‬ग़ର৅ʹରͯ͠ 4 ࣌ؒఔ౓Ͱ‫ݕ‬ग़ՄೳΓ௿͍ F ஋ͱͳͬͨɽ3 ͭͷશͯͷϓϩδΣΫτͷ߹‫ܭ‬ͷF ஋͸ 0.69 ͱͳΓɼؔ਺Ϋϩʔϯ‫ݕ‬ग़๏ͱ CCFinder ΑΓc 2017 Information Processing Society of Japan


*6
*7

http://cloc.sourceforge.net
http://secold.org/projects/seclone

6Vol.2017-SE-196 No.19
2017/7/20

৘ใॲཧֶձ‫ڀݚ‬ใࠂ
IPSJ SIG Technical Reportද 4‫ݕ‬ग़‫ن‬໛͝ͱͷ‫ݕ‬ग़࣌ؒ

Table 4 Detection time for varying input size
LOC

1K

10K

100K

1M

10M

100M

࣌ؒ

1s

2s

15s

2m 53s32m 59s

4h 5m 17s

Ͱ͋Δ͜ͱ͕֬ೝͰ͖ͨɽ

ɪɪɫśɏſɏɏƀɏɏſɏɏ ƋƀɪɪɬśƇ
ɪɪɭśɏɏ  ʰɏŚɪɪɮśɪɪɯśſŞʴƀƇɪɪɰśɏ ſƀŚɪɫɥś ʰɏɏɏ ſƀŚɪɫɨśɏ ſƀŚɪɫɩśƈɪɫɪśŵƋɪɫɫśƋ 䠄䝁䝯䞁䝖┬␎䠅ɪɫɬśƋŵɪɫɭśŚɪɫɮśƈ

4.3 ϒϩοΫΫϩʔϯͷ࣮ྫຊઅͰ͸ɼΞϯέʔτʹͯอकର৅ͷίʔυΫϩʔϯͱ(a) httpd/srclib/apr/ﬁle io/unix/readwrite.c൑அ͞ΕͨΫϩʔϯϖΞͷத͔Βɼຊख๏ʹΑͬͯ‫ݕ‬ग़ͨ͠ϒϩοΫΫϩʔϯͷ࣮ྫΛࣔ͢ɽಉؔ͡਺಺ʹଘࡏ͢ΔϒϩοΫΫϩʔϯؔ਺Ϋϩʔϯ‫ݕ‬ग़๏Ͱ͸ؔ਺୯Ґͷ‫ݕ‬ग़ͷͨΊɼಉؔ͡਺಺ͰίϐʔΞϯυϖʔετΛߦ͏ͳͲͯؔ͠਺಺Ͱൃੜ
ͨ͠ίʔυΫϩʔϯΛ‫ݕ‬ग़Ͱ͖ͳ͔͕ͬͨɼຊख๏Ͱ͸‫ݕ‬ग़ՄೳͰ͋ΔྫΛ֬ೝͰ͖ͨɽ
௕͍ؔ਺಺ͷҰ෦͕Ұக͢ΔϒϩοΫΫϩʔϯ90 ߦҎ্ͷ௕͍ؔ਺಺ͷҰ෦͕Ұக͢ΔϒϩοΫΫϩʔϯͰ͋Δɽؔ਺୯ҐͰ͸ҟͳΔॲཧΛߦ͍ͬͯΔͨΊɼؔ਺Ϋϩʔϯ‫ݕ‬ग़๏Ͱ͸͜ͷΑ͏ͳίʔυΫϩʔϯΛ‫ݕ‬ग़Ͱ͖ͳ͔ͬͨɽ͔͠͠ɼຊख๏Ͱ͸‫ݕ‬ग़ՄೳͰ͋ΔྫΛ֬ೝͰ͖ͨɽจͷૠೖ͕ߦΘΕͨϒϩοΫΫϩʔϯؔ਺୯ҐͰ͸ɼྨࣅͨ͠ॲཧΛߦ͏λΠϓ 4 ͷίʔυΫɪɫɰśɏſɏɏƀɏɏ ſɏɏ ƋƀɪɬɥśƇ
ɪɬɨśɏɏ  ʰɏŚɪɬɩśɪɬɪśɏ ſƀŚɪɬɫśɪɬɬśſŞʴƀƇɪɬɭś ʰɏɏɏ ſƀŚɪɬɮśɪɬɯśſ ŠʰɏƀƇɪɬɰśɏ ſƀŚɪɭɥśŚɪɭɨśƈɪɭɩśƈɪɭɪśɪɭɫśſ ſŞʴƀƀƇɪɭɬś ʰɏɏɏſƀŚɪɭɭśƈɪɭɮśɪɭɯśɏ ſƀŚɪɭɰśɪɮɥśŚɪɮɨśƈ

(b) httpd/srclib/apr/ﬁle io/unix/readwrite.cਤ 6ϑΝΠϧͷग़ྗॲཧΛߦ͏ϒϩοΫΫϩʔϯ

Fig. 6 Block clones writing data to a ﬁleϩʔϯͰ͋Δ͕ɼؔ਺Ϋϩʔϯ‫ݕ‬ग़๏Ͱ͸࣮ࡍʹ‫ݕ‬ग़Ͱ͖ͳ͔ͬͨɽ͔͠͠‫ݕ‬ग़ཻ౓ΛԼ͛Δ͜ͱͰɼຊख๏Ͱ͸‫ݕ‬‫ݕ‬ग़๏ͷ༗༻ੑ͕֬ೝͰ͖Δ [10]ɽ͔͠͠ɼؔ਺Ϋϩʔϯग़ՄೳͰ͋ΔྫΛ֬ೝͰ͖ͨɽ

‫ݕ‬ग़๏Ͱ͸ؔ਺୯Ґͷ‫ݕ‬ग़ͷͨΊʹ‫ݕ‬ग़࿙Ε͕ੜ͍ͯ͡Δ

ྨࣅͨ͠ॲཧΛߦ͏ϒϩοΫΫϩʔϯՄೳੑΛߟ͑ɼ‫ݕ‬ग़ཻ౓ΛίʔυϒϩοΫ୯Ґʹখ͘͞͠ਤ 6 ͸ɼϑΝΠϧͷग़ྗॲཧΛߦ͏λΠϓ 4 ͷϒϩοΫ

ͨຊख๏ΛఏҊͨ͠ɽຊ࣮‫ݧ‬ͷ݁Ռɼ3 ͭͷϓϩδΣΫτ

ΫϩʔϯͰ͋Δɽ੺৭ͷίʔυยͱ྘৭ͷίʔυย͕Ұகͷ߹‫ʹܭ‬ରͯ͠ద߹཰ɼ࠶‫཰ݱ‬ɼF ஋ͷ 3 ͭͷࢦඪͰؔ਺

ՕॴΛද͍ͯ͠ΔɽͲͪΒ΋ϑΝΠϧͷೖग़ྗؔ࿈ͷॲཧΫϩʔϯ‫ݕ‬ग़๏΍ CCFinder ΑΓߴ͍஋͕ಘΒΕɼ‫ݕ‬ग़ਫ਼Λߦ͏ؔ਺͕ͩɼਤ 6(b) ͷ apr ﬁle sync ؔ਺͕ɼਤ 6(a)౓ͷ‫Ͱ఺؍‬ຊख๏ͷ༗༻ੑΛ֬ೝͰ͖ͨɽ

ͷ apr ﬁle ﬂush ؔ਺ʹՃ͑ͯಠࣗͷॲཧΛߦ͏ͨΊɼؔ਺‫ݕ‬ग़࣌ؒͱεέʔϥϏϦςΟ

Ϋϩʔϯ‫ݕ‬ग़๏Ͱ͸‫ݕ‬ग़Ͱ͖ͳ͔ͬͨɽ͔͠͠‫ݕ‬ग़ཻ౓Λຊख๏͸ؔ਺Ϋϩʔϯ‫ݕ‬ग़๏΍ CCFinder ΑΓߴ଎ʹ‫ݕ‬Լ͛Δ͜ͱͰ֤ؔ਺ͷ‫ڞ‬௨෦෼Λ‫͚ͭݟ‬ग़͠ɼਤ 6 ͷΑ͏ग़Ͱ͖Δ͜ͱ͕֬ೝͰ͖ͨɽ·ͨɼ100MLOC ͱ͍͏େ‫ن‬ʹ‫ݕ‬ग़ՄೳͰ͋ΔྫΛ֬ೝͰ͖ͨɽ

໛ϓϩδΣΫτʹରͯ͠ 4 ࣌ؒఔ౓Ͱ‫ݕ‬ग़Ͱ͖Δ͜ͱ΋֬ೝͰ͖ͨɽ‫ݕ‬ग़ͷߴ଎Խͷཧ༝ͱͯ͠ɼMulti-Probe LSH

4.4 ߟ࡯
ຊઅͰ͸ɼఏҊख๏ɼ͓ΑͼධՁ࣮‫ݧ‬ͷ݁Ռʹ͍ͭͯͷΛ༻͍ͯΫϥελϦϯάΛߦ͏͜ͱͰɼϝϞϦ࢖༻ྔ͕‫ݮ‬ΓɼΑΓޮ཰తͳ‫͑ߦ͕ࢉܭ‬Δ͜ͱʹΑΓߴ଎Խʹ‫͕ͬܨ‬ٞ࿦Λߦ͍ɼຊख๏ͷ༗༻ੑɼ֦ுੑɼ͓ΑͼධՁ࣮‫ݧ‬ͷͨͱߟ͑ΒΕΔɽଥ౰ੑʹ͍ͭͯͷߟ࡯Λߦ͏ɽϒϩοΫΫϩʔϯͷ࣮ྫ‫ݕ‬ग़ਫ਼౓

ϒϩοΫΫϩʔϯͷ࣮ྫʹΑͬͯɼ௕͍ؔ਺಺ͷҰ෦͕ࢁதΒ͕ߦͬͨ Tempero ΒͷίʔύεΛ༻͍ͨධՁ࣮

Ұக͢ΔίʔυΫϩʔϯ΍ɼಉؔ͡਺಺ʹଘࡏ͢Δίʔυ‫Ͱݧ‬͸ɼؔ਺Ϋϩʔϯ‫ݕ‬ग़๏͸ద߹཰͕ 90%Λ௒͑Δͱ͍ΫϩʔϯͳͲɼؔ਺Ϋϩʔϯ‫ݕ‬ग़๏Ͱ͸‫ݕ‬ग़Ͱ͖ͳ͔ͬͨ

͏ใࠂ͕͞Ε͍ͯΔ [13]ɽ·ͨɼপాΒ͕ߦͬͨόάΛ‫ؚ‬ίʔυΫϩʔϯΛ֬ೝͰ͖ͨɽΑͬͯɼؔ਺Ϋϩʔϯ‫ݕ‬ग़Ήίʔυยʹର͢Δؔ਺Ϋϩʔϯ‫ݕ‬ग़ख๏ͱ CCFinder ͷ๏ʹΑΔ‫ݕ‬ग़࿙Εͷ࡟‫ݮ‬Λࣔͤͨɽൺֱ࣮‫ʹݧ‬ΑΓɼؔ਺Ϋϩʔϯ‫ݕ‬ग़๏͕ CCFinder ΑΓߴຊख๏ͷ֦ுੑ

͍ద߹཰ΛಘΒΕΔ͜ͱ΋ใࠂ͞Ε͓ͯΓɼؔ਺Ϋϩʔϯc 2017 Information Processing Society of Japanຊख๏ͷ࣮૷͸ɼ‫ ࡏݱ‬C ‫ ͱޠݴ‬Java ‫ʹޠݴ‬ͷΈରԠ͠7

Vol.2017-SE-196 No.19
2017/7/20

৘ใॲཧֶձ‫ڀݚ‬ใࠂ
IPSJ SIG Technical Report͍ͯΔɽ͔͠͠ɼຊख๏Ͱ͸ ANTLR Λ༻͍ͯߏจղੳΛ༻ੑΛධՁ͢Δඞཁ͕͋Δɽ͞ΒʹɼMeCC ͳͲͷଞߦ͓ͬͯΓɼANTLR ʹͯߏจղੳΛߦ͏ͨΊͷจ๏ϑΝͷπʔϧͱͷൺֱΛߦ͏ඞཁ͕͋ΔɽΠϧ͕ 100 छྨҎ্༻ҙ͞Ε͍ͯΔ͜ͱ͔Βɼଞͷ‫΁ޠݴ‬ͷ֦ு͕༰қʹՄೳՄೳͰ͋Δɽ
·ͨɼຊख๏Ͱ͸ίʔυϒϩοΫΛ“{ }”ʹғ·ΕͨൣғʹΑͬͯநग़͍ͯ͠Δɽ͔͠͠ɼࣈԼ͛ʹΑΔίʔυϒँࣙ ຊ‫༷͍͓ͯʹڀݚ‬ʑͳ͝‫ྗڠ‬Λ͍͍ͨͩͨ೔ຊి
‫ࣜגؾ‬ձࣾ લా௚ਓࢯɼौ୩݈հࢯʹਂ͘‫͢ँײ‬Δɽຊ‫ݚ‬‫ڀ‬͸ JSPS Պ‫ݚ‬අ 25220003ɼ16K16034ɼ15H06344 ͷॿ੒Λड͚ͨɽ

ϩοΫͷநग़΍ɼ͋ΔҰఆߦ਺ͷ·ͱ·ΓΛίʔυϒϩοΫͱͯ͠நग़͢ΔͳͲɼநग़ํ๏ʹଞͷख๏Λద༻͢Δ͜ࢀߟจ‫ݙ‬

ͱ΋ՄೳͰ͋Δɽ

[1]ධՁ࣮‫ݧ‬ͷଥ౰ੑຊ࣮‫Ͱݧ‬͸ɼ3 ͭͷ C ‫ޠݴ‬ͷϓϩδΣΫτͷΈʹରͯ͠ൺֱΛߦ͏͜ͱʹΑͬͯຊख๏ͷ༗༻ੑΛࣔͨ͠ɽ͔͠
͠ɼࠓ‫ޙ‬ɼଞͷ‫͞૷࣮Ͱޠݴ‬Εͨଟ͘ͷϓϩδΣΫτʹର

[2]ͯ͠ద༻͠ɼҰൠੑΛࣔ͢ඞཁੑ͕͋Δɽ·ͨɼࠓճ͸ϕϯνϚʔΫͷ࡞੒ʹ͓͍ͯɼΞϯέʔτʹͯա൒਺Ͱ͋Δ[3]

2 ਓҎ্͕อकର৅ͱͳΓ͏ΔίʔυΫϩʔϯͱ൑ఆͨ͠
৔߹Λਖ਼ղͱͯ͠ѻͬͨɽ͔͠͠ɼΑΓਖ਼֬ੑΛ্͛ΔͨΊʹ͸ɼҙ‫ׂ͕ݟ‬ΕͨΫϩʔϯϖΞʹ͍ͭͯٞ࿦Λߦ͏ඞ[4]ཁੑ΋ߟ͑ΒΕΔɽ

5. ·ͱΊͱࠓ‫ޙ‬ͷ՝୊ຊ‫Ͱڀݚ‬͸ɼ৘ใ‫ٕࡧݕ‬ज़Λར༻ͨ͠ϒϩοΫΫϩʔϯ

[5]

[6]

‫ݕ‬ग़ख๏ͷఏҊΛߦͬͨɽຊख๏Ͱ͸ɼߏจղੳΛߦ͍ίʔυϒϩοΫͷநग़Λߦ͍ɼίʔυϒϩοΫதͷࣝผࢠ΍༧໿‫ʹޠ‬ར༻͞Ε͍ͯΔ୯‫͔ޠ‬ΒϫʔυΛநग़͢Δɽͦ

[7]

ͯ͠ɼTF-IDF Λར༻֤ͯ͠ϫʔυʹର͢ΔॏΈΛ‫͠ࢉܭ‬ɼͦͷॏΈΛಛ௃ྔͱ֤ͯ͠ίʔυϒϩοΫΛಛ௃ϕΫτϧʹม‫͢׵‬Δɽͦͷ‫ޙ‬ɼಛ௃ϕΫτϧؒͷྨࣅ౓Λ‫͢ࢉܭ‬[8]Δ͜ͱʹΑͬͯɼҙຯతʹॲཧ಺༰͕ྨࣅͨ͠ϒϩοΫΫ
ϩʔϯͷ‫ݕ‬ग़Λߦ͏ɽ·ͨɼLSH ΞϧΰϦζϜΛ༻͍ͯ͋[9]Β͔͡Ίಛ௃ϕΫτϧͷΫϥελϦϯάΛߦ͏͜ͱʹΑͬͯɼߴ଎ͳϒϩοΫΫϩʔϯͷ‫ݕ‬ग़Λ࣮‫ͨ͠ݱ‬ɽධՁ࣮‫Ͱݧ‬͸ɼ3 ͭͷ C ϓϩδΣΫτʹର͠ɼ‫ݕ‬ग़ਫ਼౓ͱ‫ݕ‬ग़࣌ؒͷ‫͔఺؍‬Βɼؔ਺Ϋϩʔϯ‫ݕ‬ग़๏ͱ CCFinder[10]

ͷ 2 ͭͷख๏ͱൺֱΛߦͬͨɽͦͷ݁Ռɼຊख๏͕૯߹త
ʹߴ͍ਫ਼౓Ͱଟ͘ͷίʔυΫϩʔϯΛ‫ݕ‬ग़Ͱ͖Δ͜ͱ͕֬ೝͰ͖ͨɽ·ͨɼ‫ݕ‬ग़࣌ؒ͸ 3 ෼ҎԼͱͳΓɼؔ਺Ϋϩʔ[11]ϯ‫ݕ‬ग़๏ͱ CCFinder ΑΓߴ଎ʹίʔυΫϩʔϯΛ‫ݕ‬ग़Ͱ͖ͨɽ͞Βʹɼؔ਺Ϋϩʔϯ‫ݕ‬ग़๏Ͱ͸‫ݕ‬ग़Ͱ͖ͳ͔ͬͨ

[12]ίʔυϒϩοΫ୯ҐͷίʔυΫϩʔϯΛ‫ݕ‬ग़Ͱ͖ͨɽ
ࠓ‫ޙ‬ͷ՝୊ͱͯ͠ɼҎԼ͕‫͛ڍ‬ΒΕΔɽ• ϫʔυͷॏΈͷ‫ʹࢉܭ‬ɼLSIʢLatent Semantic Index-[13]

ingʣ[2] ΍ɼLDAʢLatent Dirichlet Allocationʣ[4] Λ༻͍ͨख๏ͱൺֱΛߦ͏ඞཁ͕͋Δɽ• ຊख๏Ͱ͸“{ }”ʹΑͬͯίʔυϒϩοΫͷఆٛΛߦͬ
͍ͯΔ͕ɼίʔυϒϩοΫͷఆٛ΍நग़ํ๏Λ࠶ߟ͢
Δඞཁ͕͋Δɽ

[14]

Andoni, A., Indyk, P., Laarhoven, T., Razenshteyn, I.
and Schmidt, L.: Practical and Optimal LSH for Angular Distance, Proceedings of the 28th International
Conference on Neural Information Processing Systems,
pp. 1225–1233 (2015).
Baeza-Yates, R. and Ribeiro-Neto, B.: Modern information retrieval: The concepts and technology behindsearch, Addison-Wesley (2011).
Baxter, I. D., Yahin, A., Moura, L., Anna, M. S. andBier, L.: Clone detection using abstract syntax trees,
Proceedings of International Conference on Software
Maintenance, pp. 368–377 (1998).
Blei, D. M., Ng, A. Y. and Jordan, M. I.: Latent dirichlet allocation, Journal of machine Learning research,
Vol. 3, No. Jan, pp. 993–1022 (2003).
ං‫ޙ‬๕थɼೇຊਅೋɼҪ্ࠀ࿠ɿίʔυΫϩʔϯ‫ݕ‬ग़ͱͦͷؔ࿈ٕज़ɼిࢠ৘ใ௨৴ֶձ࿦จࢽɼVol. J91-D, No. 6,
pp. 1465–1481 (2008).
Indyk, P. and Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the 30th annual ACM symposium on Theoryof computing, pp. 604–613 (1998).
Kamiya, T., Kusumoto, S. and Inoue, K.: CCFinder: amultilinguistic token-based code clone detection system
for large scale source code, IEEE Transactions on Software Engineering, Vol. 28, No. 7, pp. 654–670 (2002).
‫ݹ‬լ‫ࢤٱ‬ɿϋογϡΛ༻͍ͨྨࣅ‫ٕࡧݕ‬ज़ͱͦͷԠ༻ɼిࢠ৘ใ௨৴ֶձ‫ૅج‬ɾ‫ڥ‬քιαΠΤςΟ Fundamentals
Reviewɼ Vol. 7, No. 3, pp. 256–268 (2014).
Lv, Q., Josephson, W., Wang, Z., Charikar, M. and
Li, K.: Multi-probe LSH: eﬃcient indexing for highdimensional similarity search, Proceedings of the 33rd
international conference on Very large data bases, pp.
950–961 (2007).
Numata, S., Yoshida, N., Choi, E. and Inoue, K.: On theEﬀectiveness of Vector-Based Approach for Supporting
Simultaneous Editing of Software Clones, pp. 560–567,
Springer International Publishing (2016).
Rattan, D., Bhatia, R. and Singh, M.: Software clone detection: A systematic review, Information and Software
Technology, Vol. 55, No. 7, pp. 1165–1199 (2013).
Roy, C. K., Cordy, J. R. and Koschke, R.: 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).
ࢁத༟थɼቐɹԸಬɼ٢ాଇ༟ɼҪ্ࠀ࿠ɿ৘ใ‫ٕࡧݕ‬ज़ʹ‫ߴͮ͘ج‬଎ͳؔ਺Ϋϩʔϯ‫ݕ‬ग़ɼ৘ใॲཧֶձ࿦จࢽɼ
Vol. 55, No. 10, pp. 2245–2255 (2014).
Yamanaka, Y., Choi, E., Yoshida, N., Inoue, K. andSano, T.: Applying clone change notiﬁcation system into
an industrial development process, Proceedings of the
21st International Conference on Program Comprehension, pp. 199–206 (2013).

• ଞͷେ‫ن‬໛ϓϩδΣΫτʹରͯ͠ద༻͠ɼຊख๏ͷ༗c 2017 Information Processing Society of Japan

8