ಛผ‫ڀݚ‬ใࠂ୊໨ࣗಈϓϩάϥϜमਖ਼ʹ͓͚Δߋ৽ཤྺσʔλΛ༻͍ͨૠೖީิબ୒ख๏

ࢦಋ‫ڭ‬һೇຊ ਅೋ ‫ڭ‬त

ใࠂऀ
ࢁຊ ক߂

ฏ੒ 28 ೥ 2 ݄ 16 ೔େࡕେֶ ‫ֶ޻ૅج‬෦ ৘ใՊֶՊ

ฏ੒ 27 ೥౓ ಛผ‫ڀݚ‬ใࠂࣗಈϓϩάϥϜमਖ਼ʹ͓͚Δߋ৽ཤྺσʔλΛ༻͍ͨૠೖީิબ୒ख๏
ࢁຊ ক߂

಺༰ߎ֓
ιϑτ΢ΣΞ։ൃʹ͓͍ͯɼϓϩάϥϜͷ৴པੑΛ޲্ͤ͞ΔͨΊʹσόοάΛߦ͏ඞཁ͕͋Δɽ
σόοά͸࡞‫ۀ‬ίετ͕͔͔ΔͨΊɼࢧԉ͢ΔͨΊʹϓϩάϥϜमਖ਼ΛࣗಈԽ͢Δ͜ͱ͕๬·͍͠ɽࣗಈϓϩάϥϜमਖ਼ͷ‫͍͓ͯʹڀݚ‬ɼ‫ط‬ଘͷιʔείʔυதͷߦΛ࠶ར༻ͯܽؕ͠ͷमਖ਼Λߦ͏‫ڀݚ‬͕ߦΘΕɼ༷ʑͳख๏͕ఏҊ͞Ε͍ͯΔɽͦͷΑ͏ͳ࠶ར༻ʹ‫ࣗͮ͘ج‬ಈϓϩάϥϜमਖ਼ख๏Ͱ͸ɼ
ૠೖ͢ΔߦΛमਖ਼ର৅ϓϩάϥϜͷιʔείʔυશମ͔ΒϥϯμϜʹબ୒͢ΔɽϥϯμϜͳબ୒Ͱ͸ɼϓϩάϥϜͷ‫ن‬໛͕֦େ͢ΔʹͭΕͯܽؕͷमਖ਼ʹ‫د‬༩͠ͳ͍ߦ͕બ୒͞ΕΔճ਺͕ଟ͘ͳΓɼमਖ਼͕‫ྃ͢׬‬Δͷʹ͕͔͔࣌ؒͬͯ͠·͏Մೳੑ͕͋ΔɽͦͷͨΊɼܽؕͷमਖ਼ʹ‫د‬༩͢ΔߦΛ༏ઌͯ͠બ୒͢ΔΑ͏ͳ‫ج‬४ΛఏҊ͢Δඞཁ͕͋Δɽ‫ط‬ଘ‫Ͱڀݚ‬͸ྨࣅ౓ॱͱ͍͏‫ج‬४͕ఏҊ͞Ε͍ͯ
Δɽྨࣅ౓ॱͱ͸ɼιʔείʔυதͷ֤ߦΛɼͦͷߦͷपลίʔυͱ͕ܽؕଘࡏ͢ΔՕॴͷपลίʔυͷྨࣅ౓͕ߴ͍ॱͰબ୒͢Δ‫ج‬४Ͱ͋Δɽ‫ط‬ଘ‫͚͓ʹڀݚ‬Δௐࠪͷ݁Ռɼྨࣅ౓ॱ͕༗༻Ͱ͋Δ͜ͱ͕Θ͔͍ͬͯΔɽ͔͠͠ɼܽؕͷमਖ਼ʹ‫د‬༩͢ΔߦͰ͋Δʹ΋ؔΘΒͣɼྨࣅ౓ॱͰ͸ͦͷߦͷ༏ઌ౓͕௿͘ͳͬͯ͠·͏৔߹͕͋Δ͜ͱ͕֬ೝ͞Ε͍ͯΔɽͦͷͨΊɼྨࣅ౓ॱͱ͸ผͷ‫ج‬४ΛఏҊ͢Δඞཁ͕͋Δɽ
ͦ͜Ͱຊ‫Ͱڀݚ‬͸ɼߋ৽ॱͱ͍͏‫ج‬४ΛఏҊ͢Δɽߋ৽ॱͱ͸ɼιʔείʔυதͷ֤ߦΛߋ৽೔࣌ͷ৽͍͠ॱͰબ୒͢Δ‫ج‬४Ͱ͋Δɽ֤ߦͷߋ৽೔࣌͸όʔδϣϯ؅ཧγεςϜΑΓऔಘ͢Δɽຊ‫ݚ‬‫Ͱڀ‬͸ɼΦʔϓϯιʔειϑτ΢ΣΞͰա‫ߦʹڈ‬ΘΕͨܽؕͷमਖ਼ʹ͓͍ͯૠೖ͞ΕͨߦΛ༻͍ͯɼߋ৽ॱͷ༗༻ੑΛௐࠪͨ͠ɽௐࠪͰ͸ɼܽؕͷमਖ਼ʹ͓͍ͯૠೖ͞Εͨߦͷ͏ͪɼߦͷ࠶ར༻ʹΑΓબ୒Ͱ͖ΔߦΛର৅ͱͨ͠ɽௐࠪͷ݁Ռɼର৅ͷߦͷ͏ͪ໿ 6 ׂͷߦ͕ߋ৽ॱͰૠೖީิͷ 10%ͷߦΛબ୒͢Δ·Ͱʹબ୒͞Ε͍ͯΔ͜ͱ͕Θ͔ͬͨɽ·ͨɼಉ͡ௐࠪର৅Λ༻͍ͯߋ৽ॱͱྨࣅ౓ॱ
ͷൺֱΛߦ͍ɼྨࣅ౓ॱͰ͸༏ઌతʹબ୒͞Εͳ͍͕ߋ৽ॱͰ͸༏ઌతʹબ୒͞ΕΔߦ͕ଟ਺ଘࡏ
͢Δ͜ͱ͕Θ͔ͬͨɽओͳ༻‫ޠ‬
σόοάɼࣗಈϓϩάϥϜमਖ਼ɼίʔυ࠶ར༻

໨࣍
1

·͕͖͑

1

2

ؔ࿈‫ڀݚ‬

3

2.1

GenProg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

2.2

RSRepair . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

2.3

ԣࢁΒͷ‫ ڀݚ‬. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.4

ྨࣅ౓ॱʹΑΔબ୒ͷ՝୊఺ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

3

Ξϓϩʔν

9

4

ௐࠪ

10

5

4.1

ௐࠪ໨త . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

4.2

ௐࠪखॱ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

4.3

ௐࠪର৅ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12
13

݁Ռͱߟ࡯

5.1

ߋ৽ॱͷ༗༻ੑͷධՁ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

5.2

ߋ৽ॱͱྨࣅ౓ॱͷൺֱ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

6

ଥ౰ੑ΁ͷ‫ڴ‬Җ

20

7

͋ͱ͕͖

21

ँࣙ

22

ࢀߟจ‫ݙ‬

23

i

ਤ໨࣍
1

GenProg ͷಈ࡞ͷྲྀΕ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32ྨࣅ౓ॱͰૠೖ͢ΔߦΛબ୒͢Δͷ͕ద͞ͳ͍ܽؕͷमਖ਼ͷྫ . . . . . . . . . . . .

83

मਖ਼ίϛοτ͝ͱͷॲཧ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

114

ߋ৽ॱͷΧόϨοδͷ෼෍ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

145ߋ৽ॱͱྨࣅ౓ॱͷؔ܎ʢApache httpdʣ . . . . . . . . . . . . . . . . . . . . . . .

156֤‫ج‬४ͰΧόϨοδͷখ͍͞ૠೖߦͷू߹ʹΑΔϕϯਤʢApache httpdʣ

. . . . .

15

7ߋ৽ॱͱྨࣅ౓ॱͷؔ܎ʢCBMCʣ . . . . . . . . . . . . . . . . . . . . . . . . . . .

168֤‫ج‬४ͰΧόϨοδͷখ͍͞ૠೖߦͷू߹ʹΑΔϕϯਤʢCBMCʣ . . . . . . . . .

16

9ߋ৽ॱͱྨࣅ౓ॱͷؔ܎ʢJabRefʣ . . . . . . . . . . . . . . . . . . . . . . . . . . .

1710֤‫ج‬४ͰΧόϨοδͷখ͍͞ૠೖߦͷू߹ʹΑΔϕϯਤʢJabRefʣ . . . . . . . . .

1711ߋ৽ॱͱྨࣅ౓ॱͷؔ܎ʢjEditʣ . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1812֤‫ج‬४ͰΧόϨοδͷখ͍͞ૠೖߦͷू߹ʹΑΔϕϯਤʢjEditʣ . . . . . . . . . .

18

ii

ද໨࣍
1

ԣࢁΒͷ‫ڀݚ‬ͷௐࠪର৅ιϑτ΢ΣΞ . . . . . . . . . . . . . . . . . . . . . . . . . .

62

ຊ‫ڀݚ‬ͷௐࠪର৅ιϑτ΢ΣΞ . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

123

֤ιϑτ΢ΣΞʹ͓͚Δૠೖߦͷ਺ . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

4ߋ৽ॱͱྨࣅ౓ॱͷ૊Έ߹ΘͤʹΑΔૠೖߦͷׂ߹ . . . . . . . . . . . . . . . . . .

19

iii

1

·͕͖͑
ιϑτ΢ΣΞ։ൃʹ͓͍ͯɼϓϩάϥϜͷ৴པੑΛ޲্ͤ͞ΔͨΊʹ͸ɼϓϩάϥϜͷܽؕΛऔΓআ͘σόοάΛߦ͏͜ͱ͕ඞཁͰ͋Δɽσόοάʹ͸ɼςετʹΑΔϓϩάϥϜͷܽؕͷ‫ݕ‬ग़ɼܽؕՕॴͷಛఆɼܽؕՕॴͷमਖ਼ͱ͍ͬͨ޻ఔ͕‫·ؚ‬ΕΔɽιϑτ΢ΣΞ։ൃͷաఔʹ͓͍ͯܽؕ͸සൟʹൃੜ͢ΔͨΊɼσόοά͸ඞཁෆՄܽͳ࡞‫͋Ͱۀ‬Δɽσόοά͸ଟେͳίετΛඞཁͱ͠ɼจ‫[ ݙ‬1] Ͱ͸ιϑτ΢ΣΞ։ൃऀ͸։ൃ࣌ؒͷ൒෼Λσόοάʹඅ΍͢ͱใࠂ͞Ε͍ͯΔɽσόοά͸
ඞཁෆՄܽͳ࡞‫͋Ͱۀ‬Δʹ΋ؔΘΒͣɼଟେͳίετΛཁ͢ΔͨΊɼίετΛ࡟‫͢ݮ‬ΔΑ͏ͳࢧԉ͕‫ٻ‬ΊΒΕΔɽ
σόοάͷࢧԉΛߦ͏ͨΊɼσόοάͷ޻ఔͷࣗಈԽʹؔ͢Δ༷ʑͳ‫ߦ͕ڀݚ‬ΘΕ͍ͯΔɽςετΛ࣮ࢪ͢Δ޻ఔʹ͓͍ͯɼιϑτ΢ΣΞ։ൃऀ͸ܽؕͷ‫ݕ‬ग़ʹςετέʔεΛར༻͍ͯ͠Δɽςετέʔεʹ͸։ൃऀ͕ϓϩάϥϜʹ‫ظ‬଴͢Δಈ࡞ͷೖग़ྗͷ૊Έ߹Θ͕ͤ‫ه‬ड़͞Ε͍ͯΔɽϓϩάϥϜ͕ςετέʔεΛ௨ա͢Δͱ͍͏͜ͱ͸ɼͦͷϓϩάϥϜ͕։ൃऀͷ‫ظ‬଴͢Δಈ࡞Λߦ͏͜ͱΛࣔ͢ɽ·ͨɼϓϩάϥϜ͕ςετέʔεΛ௨ա͠ͳ͍ͱ͍͏͜ͱ͸ɼͦͷϓϩάϥϜ͕։ൃऀͷ‫ظ‬଴͢Δಈ࡞Λ͠ͳ͍͜ͱΛࣔ͢ɽϓϩάϥϜ͕։ൃऀͷ‫ظ‬଴͢Δಈ࡞Λ͠ͳ͍ͱ͍͏͜ͱ͸ɼϓϩάϥϜ͕ܽؕΛ‫ؚ‬ΜͰ͍Δͱ͍͏͜ͱͰ͋ΔɽϓϩάϥϜͷܽؕͷ‫ݕ‬ग़Λे෼ʹߦ͏ͨΊʹ͸ɼലେͳ਺ͷςετέʔεΛ࡞੒͢Δඞཁ͕͋Γɼ͜ΕΛखಈͰߦ͏ͱଟେͳίετ͕͔͔ΔɽͦͷͨΊɼςετέʔεΛࣗಈੜ੒͢Δ‫ߦ͕ڀݚ‬ΘΕ͍ͯΔ [2–5]ɽ։ൃऀ͸ςετέʔεΛ༻͍ͯϓϩάϥϜ
ͷܽؕΛ‫ݕ‬ग़ͨ͠‫ޙ‬ɼܽؕՕॴͷಛఆΛߦ͏ඞཁ͕͋ΔɽܽؕՕॴ͸ϓϩάϥϜதʹෳ਺ଘࡏ͢Δ͜ͱ΋͋ΔͨΊɼखಈͰܽؕՕॴͷಛఆΛߦ͏ʹ͸ίετ͕͔͔ΔɽͦͷͨΊɼܽؕՕॴͷಛఆΛࣗಈతʹߦ͏‫ߦ͕ڀݚ‬ΘΕ͍ͯΔ [6–8]ɽܽؕͷमਖ਼Λߦ͏աఔͰ͸ɼ։ൃऀ͕ϓϩάϥϜͷಈ࡞Λཧղ͠ɼͲͷΑ͏ʹιʔείʔυΛมߋ͢Ε͹ܽؕΛऔΓআ͘͜ͱ͕Ͱ͖Δ͔Λ൑அ͢Δඞཁ͕͋Δɽܽؕͷमਖ਼ʹ΋ίετ͕͔͔ΔͨΊɼܽؕͷमਖ਼ͷࣗಈԽ͕‫ٻ‬ΊΒΕ͍ͯΔɽ
ۙ೥ɼܽؕͷमਖ਼ͷࣗಈԽʹؔ͢Δ‫͕ڀݚ‬੝ΜʹߦΘΕ͍ͯΔ [9–12]ɽܽؕͷमਖ਼ͷࣗಈԽΛߦ͏ख๏͸ 2 ͭʹେผ͞ΕΔɽ1 ͭ͸ώϡʔϦεςΟοΫͳΞϧΰϦζϜΛ༻͍ͯܽؕͷमਖ਼Λߦ͏֬཰తͳख๏Ͱ͋Δɽ΋͏ยํ͸ϓϩάϥϜ͕ຬͨ͢΂͖ੑ࣭Λද͢࿦ཧࣜΛ‫ؕܽͯ͠ʹج‬ͷमਖ਼Λߦ͏ख๏Ͱ͋Δɽ࿦ཧࣜΛ‫͢ʹج‬Δमਖ਼ख๏Ͱ͸ɼෳࡶͳ࿦ཧࣜΛ SMT ιϧό [13] Ͱղ͘ඞཁ͕͋
ΔɽͦͷͨΊɼ‫ࡏݱ‬ͷ CPU ͷॲཧೳྗͰ͸ɼ‫࣮ݱ‬తͳ࣌ؒ಺ʹ࿦ཧࣜΛղ͘͜ͱ͸ࠔ೉Ͱ͋Δͱ͍
͏՝୊఺͕ଘࡏ͢Δɽ
֬཰తͳख๏ͷ͏ͪɼGenProg [9] ͕༗๬ࢹ͞Ε͍ͯΔɽGenProg ͸ιʔείʔυதͷߦΛར༻ͯ͠ɼҨ఻తΞϧΰϦζϜʹΑΔࣗಈϓϩάϥϜमਖ਼Λߦ͏ɽͦΕʹରͯ͠ Qi Β͸ɼࣗಈϓϩάϥϜमਖ਼ʹ͓͚ΔҨ఻తΞϧΰϦζϜͷඞཁੑΛٙ໰ࢹ͠ɼRSRepair ΛఏҊͨ͠ [10]ɽRSRepair ͸Ҩ఻తΞϧΰϦζϜΛ༻͍ͣɼϥϯμϜʹιʔείʔυΛมߋ͢Δ࡞‫ۀ‬Λ‫܁‬Γฦ͢͜ͱͰϓϩάϥϜ
ͷमਖ਼Λߦ͏ɽҎ߱ɼຊ‫Ͱڀݚ‬͸ GenProg ΍ RSRepair ͳͲͷɼιʔείʔυதͷߦΛ༻͍ͯܽؕ
ͷमਖ਼Λߦ͏ख๏Λɼ࠶ར༻ʹ‫ࣗͮ͘ج‬ಈϓϩάϥϜमਖ਼ख๏ͱΑͿ͜ͱʹ͢Δɽ

1࠶ར༻ʹ‫ࣗͮ͘ج‬ಈϓϩάϥϜमਖ਼ख๏͸ιʔείʔυதͷߦΛϥϯμϜʹબ୒ͯ͠༻͍ΔɽϥϯμϜͳબ୒Ͱ͸ɼमਖ਼ର৅ͷϓϩάϥϜͷ‫ن‬໛͕େ͖͘ͳΔʹͭΕͯܽؕͷमਖ਼ʹ‫د‬༩͠ͳ͍ߦΛબ୒͢Δճ਺͕ଟ͘ͳΓɼमਖ਼͕‫ྃ͢׬‬Δͷʹ͕͔͔࣌ؒͬͯ͠·͏Մೳੑ͕͋ΔɽͦͷͨΊɼܽؕͷमਖ਼ʹ‫د‬༩͢Δߦ͕Մೳͳ‫ݶ‬Γૣ͘બ୒͞ΕΔΑ͏ͳ‫ج‬४͕ඞཁͱ͞Ε͍ͯΔɽԣࢁΒ͸ɼྨࣅ౓ॱͱ͍͏‫ج‬४ΛఏҊͨ͠ [14]ɽྨࣅ౓ॱͱ͸ɼιʔείʔυதͷ֤ߦΛɼͦͷߦͷपลίʔυͱ͕ܽؕଘࡏ͢ΔՕॴͷपลίʔυͷྨࣅ౓͕ߴ͍ॱͰબ୒͢Δ‫ج‬४Ͱ͋ΔɽԣࢁΒͷ‫Ͱڀݚ‬͸Φʔϓϯιʔειϑτ΢ΣΞͰա‫ߦʹڈ‬ΘΕͨܽؕͷमਖ਼ʹ͓͍ͯૠೖ͞ΕͨߦΛ༻͍ͯɼྨࣅ౓ॱͷ༗༻ੑΛௐࠪͨ͠ɽௐࠪͷ݁Ռɼྨࣅ౓ॱ͕ߦΛબ୒͢Δ‫ج‬४ͱͯ͠༗༻Ͱ͋Δ͜ͱΛࣔͨ͠ɽ͔͠͠ɼ
ܽؕͷमਖ਼ʹ‫د‬༩͢ΔߦͰ͋Δʹ΋ؔΘΒͣɼͦͷߦͷपลίʔυͱܽؕͷଘࡏ͢ΔՕॴͷपลίʔυ͕ྨࣅ͍ͯ͠ͳ͍৔߹͕͋Δ͜ͱ͕֬ೝ͞Ε͍ͯΔɽ
ຊ‫Ͱڀݚ‬͸ߋ৽ॱͱ͍͏‫ج‬४ΛఏҊ͠ɼ༗༻ੑͷௐࠪΛߦͬͨɽߋ৽ॱͱ͸ɼιʔείʔυதͷ֤ߦΛߋ৽೔࣌ͷ৽͍͠ॱͰબ୒͢Δ‫ج‬४Ͱ͋Δɽௐࠪ͸ԣࢁΒͷ‫ͱڀݚ‬ಉ༷ʹɼΦʔϓϯιʔειϑτ΢ΣΞͰա‫ߦʹڈ‬ΘΕͨܽؕͷमਖ਼ʹ͓͍ͯૠೖ͞ΕͨߦΛ༻͍ͯߦͬͨɽௐࠪͷ݁Ռɼର৅ͷߦͷ͏ͪͷ 60%͕ߋ৽ॱͰૠೖީิͷ 10%ͷߦΛબ୒͢Δ·Ͱʹબ୒Ͱ͖Δ͜ͱ͕Θ͔ͬͨɽ·ͨɼಉ͡ର৅ʹରͯ͠ԣࢁΒͷख๏Λద༻͠ɼൺֱΛߦͬͨɽͦͷ݁Ռɼྨࣅ౓ॱͰ͸༏ઌతʹબ୒͞Εͳ͍͕ߋ৽ॱͰ͸༏ઌతʹબ୒͞ΕΔߦ͕ଟ਺ଘࡏ͢Δ͜ͱ͕Θ͔ͬͨɽҎ߱ɼ2 ষͰ͸ɼຊ‫ؔʹڀݚ‬࿈ͨ͠‫ط‬ଘ‫͍ͯͭʹڀݚ‬ड़΂Δɽ3 ষͰ͸ɼ‫ط‬ଘ‫ڀݚ‬ͷ՝୊఺ʹର͢ΔΞϓϩʔνΛड़΂Δɽ4 ষͰ͸ɼௐࠪͷ໨తɼखॱɼର৅ʹ͍ͭͯड़΂Δɽ5 ষͰ͸ɼௐࠪ݁Ռʹ͍ͭͯड़΂ɼߟ࡯Λߦ͏ɽ6 ষͰ͸ɼຊ‫͚͓ʹڀݚ‬Δଥ౰ੑ΁ͷ‫ڴ‬Җʹ͍ͭͯड़΂Δɽ࠷‫͕ͱ͋ʹޙ‬͖ʹ͓͍ͯຊ‫ڀݚ‬Λ·ͱΊΔɽ

2ධຊ 䠖 Ḟ㝗䜢ྵ䜐䝥䝻䜾䝷䝮䛸䝔䝇䝖䜿䞊䝇

㑅ᢥฎ⌮

஺ཫฎ⌮

ኚ␗ฎ⌮

⤊஢ุᐃ

NO

YES
ฟຊ 䠖 ಟṇ䝥䝻䜾䝷䝮ਤ 1: GenProg ͷಈ࡞ͷྲྀΕ

2ؔ࿈‫ڀݚ‬
ຊষͰ͸ຊ‫ؔʹڀݚ‬࿈͢Δ‫͍ͯͭʹڀݚ‬ड़΂Δɽ·ͣ͸͡Ίʹɼ࠶ར༻ʹ‫ࣗͮ͘ج‬ಈϓϩάϥϜमਖ਼ͷ‫ͯ͠ͱڀݚ‬ɼGenProg [9] ͱ RSRepair [10] Λ঺հ͢Δɽͦͷ‫ޙ‬ɼ࠶ར༻ʹ‫ࣗͮ͘ج‬ಈϓϩάϥϜमਖ਼๊͕͑Δ՝୊఺ʹؔ͢Δ‫ط‬ଘ‫[ ڀݚ‬14] ʹ͍ͭͯઆ໌͢Δɽ࠷‫ͦʹޙ‬ͷ‫ط‬ଘ‫͍͓ͯʹڀݚ‬ఏҊ͞Εͨख๏ͷ՝୊఺ʹ͍ͭͯड़΂Δɽ

2.1

GenProg

GenProg [9] ͸Ҩ఻తϓϩάϥϛϯά [15] Λ༻͍ͯ࠶ར༻ʹ‫ࣗͮ͘ج‬ಈϓϩάϥϜमਖ਼Λߦ͏ख
๏Ͱ͋ΔɽGenProg ͸ೖྗͱͯܽؕ͠Λ‫ؚ‬ΉϓϩάϥϜͱςετέʔεΛड͚औΓɼશͯͷςετέʔεΛ௨ա͢Δमਖ਼ϓϩάϥϜΛग़ྗ͢Δɽਤ 1 ʹ GenProg ͷಈ࡞ͷྲྀΕΛࣔ͢ɽҨ఻తϓϩάϥϛϯά͸ɼબ୒ɾมҟɾަࠥͷ 3 ͭͷॲཧΛ‫܁‬Γฦ͠ߦ͏͜ͱʹΑΓ༏लͳ‫ݸ‬ମΛੜ੒͢Δɼੜ෺ͷਐԽΛ໛ͨ͠ख๏Ͱ͋Δɽબ୒ɾมҟɾަࠥͷ 3 ͭͷॲཧ͸ɼ৚݅Λຬͨ͢‫ݸ‬ମ͕ੜ੒͞ΕΔ·Ͱ‫܁‬Γฦ͠ద༻͞ΕΔɽGenProg Ͱ͸ɼϓϩάϥϜΛ‫ݸ‬ମͱΈͳ͠ɼશͯͷςετέʔεΛ௨ա͢ΔϓϩάϥϜ͕ੜ੒͞ΕΔ·Ͱɼ3 ͭͷॲཧΛ‫܁‬Γฦ͠ద༻͢Δɽ
બ୒ॲཧͰ͸ɼ֤‫ݸ‬ମͷςετέʔε௨աঢ়‫گ‬Λ‫ʹج‬ద߹஋Λ‫ٻ‬Ίɼద߹஋͕ߴ͍ॱʹҰఆ਺ͷ‫ݸ‬ମΛऔΓग़͢ɽ
มҟॲཧͰ͸ɼ֤‫ݸ‬ମʹରͯ͠มߋΛߦ͏ɽมߋΛߦ͏Օॴ͸ܽؕͷ‫ݪ‬Ҽͱͯ͠‫͞ہݶ‬ΕͨߦͰ͋Δɽॳ‫ظ‬ͷ GenProg [16] Ͱ͸ɼมߋ͸࡟আɾૠೖɾަ‫׵‬ͷ 3 छྨͷૢ࡞Ͱ͋Δɽ࡟আૢ࡞Ͱ͸‫ہݶ‬͞ΕͨߦΛ࡟আ͢Δɽૠೖૢ࡞Ͱ͸ιʔείʔυத͔ΒϥϯμϜʹબ୒͞ΕͨߦΛ‫͞ہݶ‬Εͨߦͷ͋

3ͱʹૠೖ͢Δɽަ‫Ͱ࡞ૢ׵‬͸ιʔείʔυத͔ΒϥϯμϜʹબ୒͞Εͨߦͱ‫͞ہݶ‬ΕͨߦͷҐஔΛަ‫͢׵‬Δɽ͜ͷ͏ͪɼަ‫࡞ૢ׵‬͸ଞͷ 2 ͭʹൺ΂ͯܽؕͷमਖ਼ʹ‫د‬༩͢ΔՄೳੑ͕௿͍͜ͱ͕෼͔ͬ
͍ͯΔ [17]ɽͦͷͨΊɼվྑ͞Εͨ GenProg [9] ͷมߋ͸࡟আɼૠೖɼஔ‫׵‬ͷ 3 छྨͷૢ࡞ʹͳͬͯ
͍Δɽஔ‫Ͱ࡞ૢ׵‬͸ιʔείʔυத͔ΒϥϯμϜʹબ୒͞ΕͨߦͰܽؕͷ‫ݪ‬ҼͱͳΔߦΛ্ॻ͖͢Δɽ͢ͳΘͪɼ͜ͷஔ‫ʹ࡞ૢ׵‬ΑΔมߋ͸࡟আૢ࡞Λߦͬͨͷͪૠೖૢ࡞Λߦͬͨ͜ͱͱ౳͍͠ɽ
ަࠥॲཧͰ͸ɼ2 ͭͷ‫ݸ‬ମΛࠞͥ͋ΘͤΔ͜ͱʹΑΓɼ৽ͨͳ‫ݸ‬ମΛੜ੒͢Δɽ2 ‫ݸ‬ମ͸‫ݸ‬ମͷू߹͔ΒϥϯμϜʹબ୒͞ΕΔɽ

GenProg ͸Φʔϓϯιʔειϑτ΢ΣΞͰա‫ʹڈ‬मਖ਼͕ߦΘΕͨ 105 ‫ݸ‬ͷܽؕͷ͏ͪɼ55 ‫ݸ‬Λࣗಈతʹमਖ਼Ͱ͖Δ͜ͱʹ੒ޭͨ͠ [9]ɽGenProg Ͱ͸ɼιʔείʔυதʹଘࡏ͢ΔߦΛ༻͍ͯܽؕΛमਖ਼Ͱ͖ΔͱԾఆ͍ͯ͠ΔɽBarr Β͸࣮ࡍʹߦΘΕͨมߋΛ‫ʹج‬Ծఆͷਖ਼͠͞Λ‫͢ূݕ‬ΔͨΊʹௐࠪΛߦͬͨ [18]ɽௐࠪͷ݁ՌɼιʔείʔυதͷߦΛ༻͍Δ͜ͱͰɼ10%ͷมߋʹ͓͍ͯ௥Ճ͞ΕͨશͯͷߦΛ‫ه‬ड़͢Δ͜ͱ͕Ͱ͖ɼ42%ͷ
มߋʹ͓͍ͯ௥Ճ͞Εͨ൒਺Ҏ্ͷߦΛ‫ه‬ड़Ͱ͖Δ͜ͱ͕Θ͔ͬͨɽ

2.2

RSRepair

GenProg ͸ͦͷ༗༻ੑΛΦʔϓϯιʔειϑτ΢ΣΞͷܽؕΛमਖ਼͢Δ͜ͱͰࣔͨ͠ɽ͔͠͠ͳ
͕ΒɼGenProg ͷ༗༻ੑ͕Ҩ఻తΞϧΰϦζϜʹΑΔ΋ͷͰ͋Δ͔Ͳ͏͔͸͍ࣔͯ͠ͳ͍ɽQi Β͸ࣗಈϓϩάϥϜमਖ਼ʹ͓͚ΔҨ఻తΞϧΰϦζϜͷඞཁੑΛٙ໰ࢹ͠ɼRSRepair ΛఏҊͨ͠ [10]ɽ

RSRepair ͸Ҩ఻తΞϧΰϦζϜΛ༻͍ͣɼGenProg ͷมҟॲཧͱಉ༷ʹιʔείʔυΛมߋ͢Δ࡞‫ۀ‬Λ‫܁‬Γฦ͢͜ͱͰϓϩάϥϜͷमਖ਼Λߦ͏ɽGenProg ͸‫ݸ‬ମͷධՁΛߦ͏ͨΊɼςετέʔεͷ࣮ߦʹଟ͘ͷ࣌ؒΛཁ͢Δͱ͍͏՝୊఺͕͋ΔɽRSRepair Ͱ͸Ҩ఻తΞϧΰϦζϜΛ༻͍ͳ͍ͨΊ‫ݸ‬ମͷධՁΛߦ͏ඞཁ͕ແ͍ɽͦͷͨΊɼςετέʔεΛ௨աͰ͖ͳ͔ͬͨ࣌఺Ͱ‫ݸ‬ମΛഁ‫͠غ‬ɼ࢒ΓͷςετέʔεΛ࣮ߦ͢Δ࣌ؒΛ࡟‫͖Ͱݮ‬Δɽ͞Βʹɼςετέʔεʹ༏ઌॱҐΛ͚ͭΔख๏ [19]Λ༻͍ͯςετέʔεͷ࣮ߦʹཁ͢Δ࣌ؒͷ୹ॖΛਤ͍ͬͯΔɽ

RSRepair ͷೖྗͱग़ྗ͸ GenProg ͱಉ༷Ͱ͋Γɼೖྗͱͯܽؕ͠Λ‫ؚ‬ΉϓϩάϥϜͱςετέʔεΛड͚औΓɼશͯͷςετέʔεΛ௨ա͢Δमਖ਼ϓϩάϥϜΛग़ྗ͢ΔɽRSRepair Ͱ͸ɼϓϩάϥϜमਖ਼Λߦ͏ͱ͖ɼશͯͷςετέʔεʹ੔਺Λ෇༩͢Δɽ‫ݸ‬ମ͕ςετέʔεΛ௨ա͠ͳ͔ͬͨ
৔߹ɼςετέʔεʹ෇༩ͨ͠੔਺Λ 1 ૿΍͢ɽ͜ͷ੔਺͸ܽؕͷ‫ݕ‬ग़͠΍͢͞Λࣔ͠ɼ஋͕େ͖͍
ςετέʔε͕༏ઌ࣮ͯ͠ߦ͞ΕΔɽ͜Ε͸ɼଟ͘ͷ‫ݸ‬ମ͕௨ա͠ͳ͍ςετέʔε΄Ͳɼ৽ͨͳ‫ݸ‬ମ΋௨ա͠ͳ͍Մೳੑ͕ߴ͍ͷͰ͸ͳ͍͔ͱ͍͏ߟ͑ʹ‫͍͍ͯͮج‬Δɽ‫ݩ‬ͷιʔείʔυ͔ΒมҟॲཧʹΑΓ‫ݸ‬ମΛੜ੒͠ɼ෇༩ͨ͠੔਺͕େ͖͍ॱʹςετέʔεΛ࣮ߦ͢Δɽ‫ݸ‬ମ͕શͯͷςετέʔεΛ௨ա͢Ε͹ɼͦͷ‫ݸ‬ମΛमਖ਼ϓϩάϥϜͱͯ͠ग़ྗ͠ɼमਖ਼Λऴྃ͢Δɽ1 ͭͰ΋௨ա͠ͳ͍ςετέʔε͕͋Ε͹ɼ‫ݸ‬ମΛഁ‫࣍ͯ͠غ‬ͷ‫ݸ‬ମͷੜ੒Λߦ͍ɼ͜ΕΒͷॲཧΛ‫܁‬Γฦ͢ɽ

RSRepair ͕มҟΛߦ͏ͷ͸ 1 ՕॴͷΈͰ͋ΔͨΊɼ2 ՕॴҎ্ͷमਖ਼Λඞཁͱ͢ΔܽؕΛमਖ਼͢
Δ͜ͱ͕Ͱ͖ͳ͍ɽQi Β͸ɼRSRepair ͷ༗༻ੑΛ֬ೝ͢ΔͨΊʹɼGenProg [9] Ͱର৅ͱͨܽؕ͠

4ͷ͏ͪ 2 ՕॴҎ্ͷमਖ਼Λඞཁͱ͢ΔܽؕΛআ͍ͨ 24 ‫ݸ‬ͷܽؕʹରͯ͠ RSRepair Λ༻͍ͯϓϩάϥϜमਖ਼ΛߦͬͨɽϓϩάϥϜमਖ਼ͷ݁Ռɼ24 ‫ݸ‬த 23 ‫ݸ‬ͷܽؕʹ͓͍ͯ RSRepair ͷํ͕ GenProg
ΑΓ΋ੜ੒͞Εͨ‫ݸ‬ମ਺͕গͳ͍͜ͱΛࣔͨ͠ɽ·ͨɼ24 ‫ݸ‬த 23 ‫ݸ‬ͷܽؕʹ͓͍ͯ RSRepair ͷํ͕ GenProg ΑΓ࣮ߦͨ͠ςετέʔεͷ਺͕গͳ͍͜ͱΛࣔͨ͠ɽ

2.3

ԣࢁΒͷ‫ڀݚ‬ຊઅͰ͸ɼ࠶ར༻ʹ‫ࣗͮ͘ج‬ಈϓϩάϥϜमਖ਼๊͕͑Δ՝୊఺ʹؔ͢ΔԣࢁΒͷ‫[ ڀݚ‬14] ʹ͍ͭͯઆ໌͢Δɽ͸͡ΊʹԣࢁΒͷ‫͍༻Ͱڀݚ‬ΒΕͨ༻‫ޠ‬ͷఆٛΛࡌͤΔɽ
ૠೖީิ มҟॲཧʹ͓͍ͯૠೖͷର৅ͱͳΓ͏Δߦͷू߹ૠೖߦ ૠೖީิͷ͏ͪɼ࣮ࡍʹૠೖ͞ΕͨߦपลྖҬ ͋ΔߦΛத৺ͱͨ͠લ‫ߦ਺ޙ‬࠶ར༻ʹ‫ࣗͮ͘ج‬ಈϓϩάϥϜमਖ਼ख๏͸ιʔείʔυதͷߦΛϥϯμϜʹબ୒ͯ͠༻͍ΔɽϥϯμϜͳબ୒Ͱ͸ɼϓϩάϥϜͷ‫ن‬໛͕େ͖͘ͳΔʹͭΕɼૠೖީิͷ਺͕૿େܽؕ͠ͷमਖ਼ʹ‫د‬༩͠ͳ͍ߦΛબ୒͢Δճ਺͕૿͑ΔɽͦͷͨΊɼେ‫ن‬໛ͳϓϩάϥϜʹରͯ͠͸ɼϓϩάϥϜमਖ਼ʹ࣌ؒΛཁͯ͠͠·͏ͱ͍͏՝୊఺͕ଘࡏ͢Δɽ͜ͷ՝୊఺Λվળ͢ΔͨΊʹɼԣࢁΒͷ‫Ͱڀݚ‬͸ɼιʔείʔυͷ֤ߦʹ༏ઌ౓෇͚Λߦ͍ɼ༏ઌ౓ॱʹૠೖ͢Δඞཁੑ͕͋Δ͜ͱΛड़΂ͨɽԣࢁΒ͸ɼ࣮ࡍʹߦΘΕͨܽؕͷमਖ਼ͷྫΛ‫ʹݩ‬ɼιʔείʔυͷߦͷ͏ͪɼͦͷपลྖҬͱ͕ܽؕଘࡏ͍ͯ͠ΔߦͷपลྖҬ͕ྨࣅ͍ͯ͠Δ৔߹͸ɼ͕ܽؕमਖ਼Ͱ͖ΔՄೳੑ͕ߴ͍ͱߟ͑ͨɽܽؕͷଘࡏ͢ΔՕॴͱपลྖҬ͕ྨࣅ͍ͯ͠Δߦ͕ܽؕΛमਖ਼Ͱ͖Δ܏޲͕͋Ε͹ɼૠೖީิͷ༏ઌ౓෇͚Λߦ͏ͨΊʹྖҬؒͷྨࣅ౓Λ༻͍Δ͜ͱ͕༗༻ͱͳΔɽԣࢁΒ͸ɼྖҬؒͷྨࣅ౓Λ༻͍ͯ༏ઌ౓෇͚Λߦ͏͜ͱ͕༗༻Ͱ͋Δ͔֬ೝ͢ΔͨΊʹҎԼͷΑ͏ͳௐ߲ࠪ໨Λઃఆ͠ɼௐࠪΛߦͬͨɽ

RQ: ૠೖߦΛ‫ؚ‬ΉྖҬͱܽؕͷ‫ݪ‬ҼͱͳΔߦͷपลྖҬͷྨࣅ౓͸ૠೖߦΛ‫ྖ͍ͳ·ؚ‬Ҭͱܽؕͷ‫ݪ‬ҼͱͳΔߦͷपลྖҬͷྨࣅ౓ΑΓ΋ߴ͘ͳΔ܏޲͸͋Δ͔ɽ
ௐࠪͰ͸࣮ࡍʹߦΘΕͨܽؕͷमਖ਼ͷ৘ใΛ༻͍ͯྨࣅ౓ͷൺֱΛߦͬͨɽ࣮ࡍʹߦΘΕͨܽؕͷमਖ਼ͷ৘ใ͸Φʔϓϯιʔειϑτ΢ΣΞͷιʔείʔυϦϙδτϦ͔Βऔಘ͢Δɽܽؕͷमਖ਼͕ߦΘΕ͔ͨͲ͏͔ʹ͍ͭͯ͸ɼίϛοτϩά͔Β൑அ͢Δɽमਖ਼ʹؔ͢ΔΩʔϫʔυͰ͋Δɼ“ﬁx”,“ﬁxed”,“ﬁxing”͕ίϛοτϩάʹ‫·ؚ‬Ε͍ͯΔͱ͖ɼͦͷίϛοτΛमਖ਼ίϛοτͱ‫͢ʹͱ͜Ϳݺ‬Δɽ͞Βʹɼमਖ਼ίϛοτʹ͓͍ͯ௥Ճ͞ΕͨߦΛɼૠೖߦͱ͢ΔɽԣࢁΒͷ‫͍͓ͯʹڀݚ‬ɼमਖ਼ίϛοτʹ͓͍ͯ௥Ճ͞Εͨશͯͷߦ͸ܽؕͷमਖ਼ʹ༻͍ΒΕͨ΋ͷͱͯ͠Ծఆ͍ͯ͠Δɽྨࣅ౓ͷࢉग़ํ๏ʹ͍ͭͯड़΂ΔɽԣࢁΒͷௐࠪͰ͸ྨࣅ౓ΛϨʔϕϯγϡλΠϯ‫[ ཭ڑ‬20] Λ༻͍ͯࢉग़͍ͯ͠ΔɽϨʔϕϯγϡλΠϯ‫ͱ཭ڑ‬͸ɼ2 ͭͷจࣈྻʹରͯ͠ยํͷจࣈྻ͔Β΋͏ยํͷจࣈྻ΁ͷฤूʹ͔͔Δ࠷খख਺Λද͢ɽจࣈྻͷฤूʹ͸จࣈͷૠೖɼ࡟আɼஔ‫͕͋׵‬Γɼ֤ૢ5

࡞͸ 1 ճʹ͖ͭ 1 खͱͯ͠ख਺ΛΧ΢ϯτ͢ΔɽԣࢁΒͷ‫Ͱڀݚ‬͸ɼจࣈྻͰ͸ͳ͘τʔΫϯྻͷϨʔϕϯγϡλΠϯ‫཭ڑ‬Λߟ͑ɼจࣈͷ୅ΘΓʹτʔΫϯΛ༻͍͍ͯΔɽϨʔϕϯγϡλΠϯ‫཭ڑ‬͸ର৅ͱ͢ΔจࣈྻʢτʔΫϯྻʣ͕௕͘ͳΔʹͭΕͯେ͖͘ͳΔɽͦͷͨΊɼ༷ʑͳจࣈྻʢτʔΫϯྻʣʹ͓͚Δྨࣅ౓Λެฏʹൺֱ͢Δʹ͸ɼ஋ͷਖ਼‫ن‬ԽΛߦ͏ඞཁ͕͋Δɽ·ͨɼϨʔϕϯγϡλ
Πϯ‫͕཭ڑ‬খ͍͞΄Ͳྨࣅ౓͸ߴ͘ͳΔ΂͖ͳͷͰɼϨʔϕϯγϡλΠϯ‫཭ڑ‬Λਖ਼‫ن‬Խͨ͠஋ͷେখΛ‫ٯ‬సͤ͞Δඞཁ͕͋Δɽ͜ΕΒͷ͜ͱΛߟྀͯ͠ 2 ͭͷτʔΫϯྻ t1 ɼt2 ʹର͢Δྨࣅ౓ s(t1 , t2 )͸ҎԼͷΑ͏ʹఆΊΔɽs(t1 , t2 ) = 1 −dist(t1 , t2 )max{len(t1 ), len(t2 )}͜͜Ͱɼdist(t1 , t2 ) ͸ t1 ͱ t2 ͷϨʔϕϯγϡλΠϯ‫཭ڑ‬ɼlen(t1 )ɼlen(t2 ) ͸ͦΕͧΕ t1 ɼt2 ͷτʔΫϯྻͷ௕͞Λද͢ɽdist(t1 , t2 ) ͷൣғ͸ɼ0 < dist(t1 , t2 ) < max{len(t1 ), len(t2 )} Ͱ͋ΔͨΊɼs(t1 , t2 ) ͷൣғ͸ 0 < s(t1 , t2 ) < 1 ͱͳΔɽ2 ͭͷτʔΫϯྻͷϨʔϕϯγϡλΠϯ‫͕཭ڑ‬খ͘͞ͳΔ΄Ͳ s(t1 , t2 ) ͸ 1 ʹۙͮ͘͜ͱʹͳΔɽRQ ʹର͢Δௐࠪ͸ද 1 ͷ 4 ͭͷΦʔϓϯιʔειϑτ΢ΣΞͷιʔείʔυϦϙδτϦΛର৅ʹߦΘΕͨɽௐࠪʹ͓͍ͯྖҬͷߦ਺͸ૠೖߦΛத৺ͱ͢Δલ‫ ޙ‬5 ߦͱ͞Εͨɽྨࣅ౓Λࢉग़ͨ݁͠
ՌɼApache httpdɼ CBMCɼJabRef ʹ͓͍ͯ͸໌֬ͳ͕ࠩ‫ݟ‬ΒΕͨɽjEdit ʹؔͯ͠͸౷‫ݕܭ‬ఆΛ༻͍ͯ༗ҙࠩΛ֬ೝͨ͠ɽԣࢁΒ͸ௐࠪͷ݁Ռ͔Β RQ ʹରͯ͠ Yes ͱճ౴ͨ͠ɽ
͞ΒʹԣࢁΒ͸ɼૠೖީิͷߦͷपลྖҬͱܽؕՕॴͷपลྖҬͷྨࣅ౓͕ߴ͍ॱͰબ୒͢Δྨ
ࣅ౓ॱ͕ɼ‫ج‬४ͱͯ͠༗༻Ͱ͋Δ͔Ͳ͏͔֬ೝ͢ΔͨΊʹ௥ՃௐࠪΛ࣮ࢪͨ͠ɽ௥ՃௐࠪͰ͸ɼૠೖߦͷΧόϨοδΛࢉग़ͨ͠ɽΧόϨοδͱ͸ɼૠೖߦΛબ୒͢Δ·Ͱ‫ج‬४ʹΑͬͯॱ൪ʹબ୒ͨ͠ߦ
ͷ਺Λɼιʔείʔυͷ૯ߦ਺Ͱׂͬͨ஋Ͱ͋ΔɽΧόϨοδΛࢉग़͢Δ͜ͱͰ‫ج‬४ʹΑͬͯૠೖީ
ิͷԿ%Λબ୒͢Δͱૠೖߦ͕બ୒Ͱ͖Δ͔͕Θ͔Δɽ௥Ճௐࠪͷର৅͸ɼRQ ͷௐࠪͰର৅ʹͨ͠ϓϩάϥϜʹ͓͚Δมߋͷ͏ͪɼ࣮ࡍʹܽؕͷमਖ਼͕ߦΘΕͨ͜ͱΛࢹೝʹΑΓ֬ೝͨ͠ίϛοτʹ
͓͚ΔૠೖߦͰ͋Δɽ
௥Ճௐࠪͷ݁Ռɼྨࣅ౓ॱΛ༻͍Δ͜ͱͰɼର৅ͷߦͷ͏ͪ 75%ͷߦ͕ૠೖީิͷ 10%ͷߦΛબ୒͢Δ·Ͱʹબ୒͞Ε͍ͯΔ͜ͱ͕Θ͔ͬͨɽද 1: ԣࢁΒͷ‫ڀݚ‬ͷௐࠪର৅ιϑτ΢ΣΞ
ιϑτ΢ΣΞ

‫ޠݴ‬։࢝ϦϏδϣϯʢ೔෇ʣ

Apache httpdC1,410,755 (2012/11/18ʣ 1,421,851 (2012/12/14)

CBMC

C++

3,602 (2014/02/22)

3,719 (2014/04/14)

JabRefJava

3,349 (2010/11/01)

3,474 (2011/03/18)

jEdit

Java

19,812 (2011/08/19)

20,292 (2011/11/11ʣ

6ऴྃϦϏδϣϯʢ೔෇ʣ

2.4

ྨࣅ౓ॱʹΑΔબ୒ͷ՝୊఺ྨࣅ౓ॱʹΑΓૠೖߦΛબ୒͢Δ͜ͱ͕ޮՌతͳͷ͸ɼ͕ܽؕଘࡏ͍ͯ͠ΔߦͷपลྖҬͱྨࣅͨ͠ίʔυยʹͦͷܽؕͷमਖ਼ʹ‫د‬༩͢Δߦ͕ଘࡏ͍ͯ͠Δ৔߹Ͱ͋Δɽܽؕͷमਖ਼ʹ‫د‬༩͢Δߦ
͕ྨࣅͨ͠ίʔυยʹଘࡏ͍ͯ͠ͳ͍৔߹͸ɼྨࣅ౓ॱ͸ޮՌతͰ͸ͳ͍ɽਤ 2 ʹྫΛ‫͛ڍ‬Δɽ͜ͷྫ͸ɼΦʔϓϯιʔειϑτ΢ΣΞͷ Apache httpd ͷϓϩάϥϜʹର࣮ͯ͠ࡍʹߦΘΕͨܽؕͷमਖ਼Ͱ͋Δɽ
ਤ 2 Ͱ͸ɼ͋Δܽؕʹରͯ͠ɼ୅ೖจʢփ৭ͷߦʣΛଞͷϝιουʹҠಈ͢Δ͜ͱͰमਖ਼Λߦ͍ͬͯΔɽͭ·ΓɼҠಈઌʹର͢Δߦͷૠೖૢ࡞ͱҠಈ‫ݩ‬ͷߦͷ࡟আૢ࡞ʹΑΓܽؕͷमਖ਼͕‫ྃ͢׬‬Δɽ
͜ͷ୅ೖจͷҠಈ‫ͱݩ‬Ҡಈઌͷपลίʔυ͸ྨࣅ౓͕ߴ͘ͳ͘ɼԣࢁΒͷख๏Ͱ͸ޮՌతʹܽؕͷमਖ਼Λ‫ͤྃ͞׬‬Δ͜ͱ͕Ͱ͖ͳ͍ɽ͜ͷΑ͏ͳ՝୊఺͕͋ΔͨΊɼผͷ‫ج‬४ʹΑΔΞϓϩʔνΛߦ͏ඞ
ཁ͕͋Δɽ

7

mod_log_config.c
212

static apr_hash_t *log_hash;…
1154 static void log_pre_config(apr_pool_t *p, apr_pool_t *plog, apr_pool_t *ptemp)
1155 {
1156
static APR_OPTIONAL_FN_TYPE(ap_register_log_handler) *log_pfn_register;
1157
1158
log_hash = apr_hash_make(p);1159
log_pfn_register = APR_RETRIEVE_OPTIONAL_FN(ap_register_log_handler);1160
if (log_pfn_register) {1161
log_pfn_register(p, "h", log_remote_host, 0);…
1188}
1189 }
1190
1191 static void register_hooks(apr_pool_t *p)1192 {
1193
ap_hook_pre_config(log_pre_config,NULL,NULL,APR_HOOK_REALLY_FIRST);1194
ap_hook_child_init(init_child,NULL,NULL,APR_HOOK_MIDDLE);
1195
ap_hook_open_logs(init_config_log,NULL,NULL,APR_HOOK_MIDDLE);
1196
ap_hook_log_transaction(multi_log_transaction,NULL,NULL,APR_HOOK_MIDDLE);
1197
1198
APR_REGISTER_OPTIONAL_FN(ap_register_log_handler);
1199 }(a) मਖ਼લʢr88903ʣ

mod_log_config.c
212

static apr_hash_t *log_hash;…
1154 static void log_pre_config(apr_pool_t *p, apr_pool_t *plog, apr_pool_t *ptemp)
1155 {
1156
static APR_OPTIONAL_FN_TYPE(ap_register_log_handler) *log_pfn_register;
1157
1158
log_pfn_register = APR_RETRIEVE_OPTIONAL_FN(ap_register_log_handler);1159
if (log_pfn_register) {1160
log_pfn_register(p, "h", log_remote_host, 0);…
1187}
1188 }
1189
1190 static void register_hooks(apr_pool_t *p)
1191 {
1192
ap_hook_pre_config(log_pre_config,NULL,NULL,APR_HOOK_REALLY_FIRST);1193
ap_hook_child_init(init_child,NULL,NULL,APR_HOOK_MIDDLE);
1194
ap_hook_open_logs(init_config_log,NULL,NULL,APR_HOOK_MIDDLE);
1195
ap_hook_log_transaction(multi_log_transaction,NULL,NULL,APR_HOOK_MIDDLE);
1196
1197
/* Init log_hash before we register the optional function. It is
…
1202
*/
1203
log_hash = apr_hash_make(p);1204
APR_REGISTER_OPTIONAL_FN(ap_register_log_handler);
1205 }(b) मਖ਼‫ޙ‬ʢr88904ʣ

ਤ 2: ྨࣅ౓ॱͰૠೖ͢ΔߦΛબ୒͢Δͷ͕ద͞ͳ͍ܽؕͷमਖ਼ͷྫ

8

3

Ξϓϩʔν
લষʹ͓͍ͯɼԣࢁΒͷ‫͚͓ʹڀݚ‬Δ‫ج‬४Ͱ͋Δྨࣅ౓ॱͱ͸ผͷ‫ج‬४Λઃ͚ΔඞཁੑΛड़΂ͨɽͦ͜Ͱຊ‫Ͱڀݚ‬͸ɼߦΛબ୒͢Δ‫ج‬४ͱͯ͠ɼߋ৽ॱͱ͍͏΋ͷΛఏҊ͢Δɽߋ৽ॱͷఆٛ͸ҎԼͷ௨ΓͰ͋Δɽߦͷߋ৽೔࣌͸ɼόʔδϣϯ؅ཧγεςϜΛར༻ͯ͠औಘ͢Δɽߋ৽ॱ ιʔείʔυதͷ֤ߦΛߋ৽೔࣌ͷ৽͍͠ॱͰબ୒͢Δ‫ج‬४ྫ͑͹ɼ‫ط‬ଘͷιʔείʔυʹରͯ͠ɼ͋Δ 1 ߦ͕௥Ճ͞Εͨ৔߹Λߟ͑Δɽ௥Ճ͞Εͨߦ͸ߋ৽೔͕࣌ଞͷߦΑΓ΋৽͍ͨ͠Ίɼ௚‫ॱ৽ߋʹޙ‬Λ༻͍ͯܽؕͷमਖ਼Λߦ͏ͱ͖͸࠷ॳʹબ୒͞ΕΔɽ
࣮ࡍʹߋ৽ॱʹΑΓॱʹૠೖީิ͔ΒߦΛબ୒͢Δ͜ͱͰ͏·͍͘͘ྫͱͯ͠ɼલষͷ‫ط‬ଘ‫ڀݚ‬ͷ՝୊఺ͷྫ͕‫͛ڍ‬ΒΕΔɽਤ 2 Ͱ͸ɼ୅ೖจʢփ৭ͷߦʣΛଞͷϝιουʹҠಈ͢Δ͜ͱͰܽؕͷमਖ਼Λߦ͍ͬͯΔɽ͜ͷߦ͸ਤͷमਖ਼ͷগ͠લͷίϛοτʹ͓͍ͯ৽ͨʹ௥Ճ͞ΕͨߦͰ͋ΓɼͦΕҎ߱ɼਤͷमਖ਼͕ߦΘΕͨίϛοτ·Ͱʹιʔείʔυ͸਺ेߦ͔͠ߋ৽͞Ε͍ͯͳ͍ɽιʔείʔυશମͷߦ਺͸਺ສߦͰ͋ΔͨΊɼߋ৽ॱʹΑͬͯ༏ઌతʹબ୒͢Δ͜ͱ͕Ͱ͖Δɽ͜ͷΑ͏ʹɼ࠷ۙ௥Ճ͞Εͨ͋ΔՕॴ͕ܽؕͷ‫ݪ‬ҼͰ͋ΓɼͦͷՕॴΛҠಈ͢Δ͜ͱͰܽؕͷमਖ਼͕࣮‫͖Ͱݱ‬ΔΑ͏ͳ৔߹ɼߋ৽ॱʹΑΔબ୒͸ద͍ͯ͠Δɽͦͷଞʹ΋ߋ৽ॱʹΑΔબ୒͕༗༻Ͱ͋Δྫͱͯ͠ɼ2 Օॴ͋Δಉ༷ͷܽؕʹରͯ͠ͲͪΒ͔ҰํͷΈܽؕͷमਖ਼͕ߦΘΕͨ৔߹ͳͲ͕‫͛ڍ‬ΒΕΔɽ͜ͷ৔߹ɼҰํͷमਖ਼௚‫͋Ͱޙ‬Ε͹ɼߋ৽ॱΛ༻
͍Δͱ΋͏Ұํͷमਖ਼ʹඞཁͳߦ͸༏ઌతʹબ୒͞ΕΔͨΊɼ༗༻Ͱ͋Δɽ

9

4

ௐࠪ
ຊষͰ͸ௐࠪͷ಺༰Λड़΂Δɽຊ‫Ͱڀݚ‬͸ɼߋ৽ॱͷ༗༻ੑͷௐࠪΛߦ͏ɽௐࠪ͸ա‫ߦʹڈ‬ΘΕͨܽؕͷमਖ਼ʹ͓͍ͯ༻͍ΒΕͨߦΛର৅ʹͯ͠ߦ͏ɽ֤અʹ͓͍ͯɼௐࠪͷ໨తɼखॱɼର৅ʹ͍ͭ
ͯड़΂Δɽ

4.1

ௐࠪ໨త

લষʹ͓͍ͯɼߋ৽ॱͱ͍͏‫ج‬४ΛఏҊͨ͠ɽຊ‫Ͱڀݚ‬͸ɼ࠶ར༻ʹ‫ࣗͮ͘ج‬ಈϓϩάϥϜमਖ਼ख๏ʹߋ৽ॱʹΑΔߦͷબ୒Λ࣮૷͢Δલʹɼߋ৽ॱ͕ߦΛબ୒͢Δ‫ج‬४ͱͯ͠༗༻Ͱ͋Δ͔Ͳ͏͔Λௐࠪ͢Δɽߋ৽ॱʹ͓͍ͯϓϩάϥϜΛमਖ਼͢Δߦ͕༏ઌతʹબ୒͞ΕΕ͹ɼߋ৽ॱ͕༗༻Ͱ͋Δ
ͱ͍͏͜ͱΛࣔͤΔɽௐࠪͷ݁Ռɼߋ৽ॱ͕༗༻Ͱ͋Δ͜ͱ͕ࣔͤΕ͹ɼࠓ‫ޙ‬ͷ‫࠶Ͱڀݚ‬ར༻ʹ‫ͮج‬ࣗ͘ಈϓϩάϥϜमਖ਼ख๏ʹߋ৽ॱΛ࣮૷͢ΔՁ஋͕༗Δ͜ͱʹͳΔɽ

4.2

ௐࠪखॱ

ຊ‫Ͱڀݚ‬͸Φʔϓϯιʔειϑτ΢ΣΞͰա‫ߦʹڈ‬ΘΕͨܽؕͷमਖ਼ʹରͯ͠ௐࠪΛߦ͏ɽա‫ʹڈ‬ߦΘΕͨܽؕͷमਖ਼ͷ৘ใ͸Φʔϓϯιʔειϑτ΢ΣΞͷιʔείʔυϦϙδτϦΛղੳ͢Δ͜ͱʹΑΓऩू͢Δɽௐࠪର৅ͱͨ͠ιϑτ΢ΣΞʹ͍ͭͯ͸ 4.3 અͰड़΂ΔɽԣࢁΒͷ‫Ͱڀݚ‬આ໌ͨ͠༻‫ޠ‬ͷ͏ͪɼૠೖީิɼૠೖߦɼमਖ਼ίϛοτΛຊ‫Ͱڀݚ‬΋༻͍Δɽ
ௐࠪͷखॱʹ͍ͭͯड़΂Δɽ·ͣ͸͡ΊʹɼιʔείʔυϦϙδτϦͷશίϛοτʹରͯ͠ίϛοτϩάΛௐ΂ɼमਖ਼ίϛοτΛಛఆ͢Δɽಛఆͨ͠શͯͷमਖ਼ίϛοτʹରͯ͠ɼҎԼͷ 4 ͭͷॲཧΛߦ͏ɽεςοϓ 1 मਖ਼લ‫ޙ‬ͷϦϏδϣϯͷιʔείʔυऔಘεςοϓ 2 ૠೖߦͷநग़εςοϓ 3 ߋ৽ॱҐදͷ࡞੒εςοϓ 4 ૠೖߦͷߋ৽ॱͷॱҐऔಘ্‫ه‬ͷ֤εςοϓΛਤ 3 ʹࣔ͢ɽͦΕͧΕͷεςοϓʹ͍ͭͯઆ໌͢Δɽ
εςοϓ 1ɿमਖ਼લ‫ޙ‬ͷϦϏδϣϯͷιʔείʔυͷऔಘमਖ਼ίϛοτͰߦΘΕͨमਖ਼ͷલ‫ޙ‬ͷϦϏδϣϯ͔ΒιʔείʔυΛऔಘ͢Δɽमਖ਼લͷϦϏδϣ
ϯͰ͸ɼ֤ߦͷߋ৽೔࣌΋औಘ͢Δɽ

10

䝇䝔䝑䝥
2
ᤄධ⾜
4

ಟṇᚋ䝸䝡䝆䝵䞁䛾䝋䞊䝇䝁䞊䝗

...

䝇䝔䝑䝥
1

䝇䝔䝑䝥
4

䝇䝔䝑䝥
3

ಟṇ๓䝸䝡䝆䝵䞁䛾䝋䞊䝇䝁䞊䝗

1.
2.
3.

ฟຊ䝣䜯䜲䝹
䠄᭦᪂㡰䛾㡰఩䛺䛹䠅

...

ಟṇᑐ㇟
䝸䝫䝆䝖䝸

᭦᪂㡰఩⾲

ਤ 3: मਖ਼ίϛοτ͝ͱͷॲཧεςοϓ 2ɿૠೖߦͷநग़मਖ਼લ‫ޙ‬ͷϦϏδϣϯʹ͓͚Διʔείʔυͷࠩ෼ΛऔΓɼૠೖߦΛநग़͢Δɽࠩ෼͸ߦ୯Ґͷ௥Ճɾ࡟আͰද͞ΕΔɽͦͷ͏ͪɼ௥Ճ͞ΕͨߦΛૠೖߦͱ͢Δɽ
εςοϓ 3ɿߋ৽ॱҐදͷ࡞੒मਖ਼લͷϦϏδϣϯʹ͓͚ΔιʔείʔυதͷશͯͷߦΛߋ৽೔࣌ͷ৽͍͠ॱͰฒͼସ͑ͯදΛ
࡞੒͢Δɽ͜ͷͱ͖ɼಉ͡ߋ৽೔࣌ͷߦͷॱ൪͸ϥϯμϜʹܾΊΔɽ࡞੒ͨ͠දΛߋ৽ॱҐදͱΑͿ͜ͱʹ͢Δɽ
εςοϓ 4ɿૠೖߦͷߋ৽ॱͷॱҐऔಘॱҐදΛ‫ͦʹج‬ΕͧΕͷૠೖߦͷߋ৽ॱͷॱҐΛऔಘ͢Δɽ͜ͷॱҐ͸ɼߋ৽ॱʹΑΓૠೖީิΛ
બ୒͢Δͱ͖ɼૠೖߦΛબ୒͢Δ·Ͱʹબ୒͢Δߦͷ਺Λද͢ɽಘΒΕͨॱҐ͸ධՁʹ༻͍ΔͨΊιʔείʔυͷ૯ߦ਺ͱͱ΋ʹϑΝΠϧʹग़ྗ͢ΔɽҎ্Ͱ 1 ͭͷमਖ਼ίϛοτʹର͢ΔॲཧΛऴྃ͢Δɽશͯͷमਖ਼ίϛοτʹ͓͚Δૠೖߦͷߋ৽ॱͷॱҐΛऔಘͨ͠‫ޙ‬ɼධՁΛߦ͏ɽධՁͷͨΊʹɼΧόϨοδΛఆٛ͢ΔɽΧόϨοδ͸ҎԼͷࣜͰࢉग़͞ΕΔɽ

ΧόϨοδ =

ߋ৽ॱͷॱҐ (=ߋ৽ॱͰૠೖߦΛબ୒͢Δ·Ͱʹબ୒͢Δߦͷ਺)ιʔείʔυͷ૯ߦ਺ΧόϨοδ͸ 0 ΑΓେ͖͘ 1 ҎԼͰ͋ΔΑ͏ͳ஋ΛऔΔɽ஋͕ 0 ʹ͍ۙ΄Ͳߋ৽ॱͰ༏ઌతʹૠೖ11ߦ͕બ୒͞ΕΔ͜ͱΛࣔ͠ɼͦͷૠೖߦʹରͯ͠͸ߋ৽ॱΛ༻͍ͨૠೖީิͷબ୒͕ద͍ͯ͠Δͱ
͍͑Δɽશͯͷૠೖߦʹରͯ͠ΧόϨοδΛࢉग़͠ɼධՁΛߦ͏ɽ͞Βʹɼߋ৽ॱͱԣࢁΒͷख๏ [14] ʹ͓͚Δ‫ج‬४Ͱ͋Δྨࣅ౓ॱͷൺֱΛߦ͏ɽಉ͡ௐࠪର৅ʹରͯ͠ԣࢁΒͷख๏Λద༻͠ɼྨࣅ౓ॱͰಉ༷ʹ֤ͯ͠ૠೖߦͷΧόϨοδΛࢉग़͢Δɽͦͷ‫ޙ‬ɼߋ৽ॱʹΑΓࢉग़ͨ͠ΧόϨοδͱൺֱΛߦ͏ɽ

4.3

ௐࠪର৅

ௐࠪର৅ͷιϑτ΢ΣΞΛද 2 ʹࣔ͢ɽௐࠪର৅͸όʔδϣϯ؅ཧγεςϜ Subversion Ͱ؅ཧ͞Εͨ 4 ͭͷΦʔϓϯιʔειϑτ΢ΣΞͰ͋ΓɼԣࢁΒͷ‫[ ڀݚ‬14] ʹ͓͚Δௐࠪର৅ͱಉ͡Ͱ͋Δɽຊ
‫Ͱڀݚ‬͸ϦϏδϣϯͷൣғΛॳ‫ظ‬ϦϏδϣϯ͔Β 2015/12/31 ·ͰͷϦϏδϣϯͱఆΊɼશͯͷૠೖߦΛௐࠪ͢Δɽͳ͓ɼJabRef ʹؔͯ͠͸‫ ࡏݱ‬Git ͷΈͷόʔδϣϯ؅ཧͱͳ͍ͬͯΔͨΊɼSubversionͰόʔδϣϯ؅ཧ͞Ε͍ͯͨϦϏδϣϯ·ͰΛൣғͱ͢ΔɽApache httpd ͷॳ‫ظ‬ϦϏδϣϯ͕ r1 Ͱͳ͍ͷ͸ɼಉ͡ιʔείʔυϦϙδτϦͰෳ਺ͷιϑτ΢ΣΞ͕؅ཧ͞Ε͓ͯΓɼ్த͔Β Apache

httpd ͕௥Ճ͞ΕͨͨΊͰ͋Δɽ
ௐࠪର৅ͷϓϩάϥϜ͸ C ‫ܥ‬ͷ‫ ͱޠݴ‬Java ͔ΒͦΕͧΕ 2 ͭͣͭ࠾༻͍ͯ͠Δɽ͜ΕʹΑΓɼ݁Ռ͕‫ʹޠݴ‬ґଘ͢Δ͔Ͳ͏͔Λ‫ݟ‬Δ͜ͱ͕Ͱ͖Δɽද 2: ຊ‫ڀݚ‬ͷௐࠪର৅ιϑτ΢ΣΞ
ιϑτ΢ΣΞ

‫ޠݴ‬։࢝ϦϏδϣϯʢ೔෇ʣऴྃϦϏδϣϯʢ೔෇ʣ

Apache httpdC76,295 (2004/11/19)

1,722,377 (2015/12/31)

CBMC

C++

1 (2011/05/08)

6,211 (2015/12/30)

JabRefJava

1 (2003/10/15)

3,718 (2011/11/11)

jEdit

Java

1 (2006/07/01)

24,280 (2015/12/31)

12

5

݁Ռͱߟ࡯
ຊষͰ͸ɼௐࠪͷ݁ՌΛਤʹ·ͱΊͨ‫ޙ‬ɼߟ࡯Λߦ͏ɽ5.1 અʹ͓͍ͯɼૠೖߦ͔Βࢉग़ͨ͠ߋ৽

ॱͷΧόϨοδΛ෼෍ʹͯ͠ਤʹ·ͱΊͨ‫ޙ‬ɼߋ৽ॱͷ༗༻ੑͷධՁΛߦ͏ɽ5.2 અʹ͓͍ͯɼૠೖ
ߦͷߋ৽ॱͱྨࣅ౓ॱͷΧόϨοδΛࢄ෍ਤʹ·ͱΊͨ‫ޙ‬ɼߋ৽ॱͱྨࣅ౓ॱͷൺֱΛߦ͏ɽ

5.1

ߋ৽ॱͷ༗༻ੑͷධՁ͸͡Ίʹɼ֤ιϑτ΢ΣΞʹ͓͚Δૠೖߦͷ਺Λද 3 ʹ·ͱΊΔɽૠೖߦͷ਺͸ 4.2 અͷௐࠪखॱͰड़΂ͨૠೖߦͷநग़ʹ͓͍ͯநग़ͨ͠ߦͷ਺Ͱ͋ΔɽΧόϨοδΛࢉग़ͨ͠ૠೖߦͷ਺͸ૠೖߦͷ͏ͪमਖ਼લͷϦϏδϣϯͷιʔείʔυதʹૠೖߦ͕ଘࡏ͢Δ΋ͷͷ਺Ͱ͋Δɽ
ද 3 ͷ֤ૠೖߦͰࢉग़͞ΕͨΧόϨοδΛ෼෍ʹͯ͠·ͱΊͨ΋ͷ͕ਤ 4 Ͱ͋Δɽਤ͕ෳࡶʹͳΔͷΛ๷͙ͨΊʹΧόϨοδ͕ 0.5 Ҏ্ͷൣғ͸ 1 ͭʹ·ͱΊ͍ͯΔɽ
ਤ 4 ͔ΒͦΕͧΕͷௐࠪର৅ͷιϑτ΢ΣΞʹ͓͍ͯૠೖީิͷ 10 ෼ͷ 1ʢΧόϨοδ͕ 0.1 ҎԼʣʹ໿ 60%ͷૠೖߦ͕ूத͍ͯ͠Δͱ͍͏͜ͱ͕Θ͔ΔɽJabRef ʹ͓͍ͯ͸ 70%ۙ͘ͷૠೖߦ͕ूத͍ͯ͠Δɽ·ͨɼૠೖީิͷ൒෼Λ‫ݟ‬Δ͜ͱͰ໿ 90%ͷૠೖߦΛબ୒͢Δ͜ͱ͕Ͱ͖Δɽͭ·Γɼߋ৽ॱͰબ୒ͨ͠৔߹ɼૠೖީิͷ൒෼Ҏ্Λબ୒͢Δඞཁ͕͋Δૠೖߦ͸ 10 ߦத 1 ߦ͔͠ͳ͍ͱ͍͏͜ͱͰ͋Δɽ
ௐࠪର৅ͷιϑτ΢ΣΞ͸ C ‫ܥ‬ͷ‫هͰޠݴ‬ड़͞Εͨιϑτ΢ΣΞͱ Java Ͱ‫ه‬ड़͞Εͨιϑτ΢Σ
Ξ͔ΒͦΕͧΕ 2 ͭͣͭબ୒ͨ͠ɽApache httpdɼCBMC ͸ C ‫ܥ‬ͷ‫هͰޠݴ‬ड़͞Εͨιϑτ΢ΣΞɼ

JabRefɼjEdit ͸ Java Ͱ‫ه‬ड़͞Εͨιϑτ΢ΣΞͰ͋ΔɽૠೖߦͷΧόϨοδ͕஋ͷখ͍͞ൣғʹ
ूத͢Δׂ߹Ͱιϑτ΢ΣΞͷେখΛද͢ͱɼJabRefɼCBMCɼApache httpdɼjEdit ͷॱ൪ʹͳ
ΔɽҰํͷ‫ूʹ୺ۃ͕߹ׂ͍͓ͯʹޠݴ‬த͢Δͱ͍ͬͨภΓ͕ͳ͍ͨΊɼຊ‫ڀݚ‬ͷௐࠪର৅ʹ͓͍ͯ͸ɼߋ৽ॱ͕‫ʹޠݴ‬େ͖͘͸ґଘ͍ͯ͠ͳ͍ͱ൑அͰ͖Δɽද 3: ֤ιϑτ΢ΣΞʹ͓͚Δૠೖߦͷ਺ιϑτ΢ΣΞ

ૠೖߦͷ਺ΧόϨοδΛࢉग़ͨ͠ૠೖߦͷ਺

Apache httpd26,679

7,807

CBMC

4,890

1,642

JabRef

12,260

4,116

jEdit

21,1617,672

13

0.1-0.2

0.2-0.3

0.3-0.4

0.4-0.5

0.5-1.0

0

20

40

60

80

100

0.0-0.1

Apache httpd

CBMC

JabRefjEdit

ਤ 4: ߋ৽ॱͷΧόϨοδͷ෼෍

5.2

ߋ৽ॱͱྨࣅ౓ॱͷൺֱ

ਤ 5 ͔Βਤ 12 ΑΓɼߋ৽ॱͱྨࣅ౓ॱͷؔ܎Λ 4 ͭͷର৅ιϑτ΢ΣΞͦΕͧΕʹ͍ͭͯ 3 ͭͷਤΛ༻͍ͯௐࠪͷ݁ՌΛ‫͢ࡌه‬Δɽ
্෦ʹଘࡏ͢Δਤ͸ߋ৽ॱͱྨࣅ౓ॱͷͦΕͧΕͷΧόϨοδΛૠೖߦʹରͯ͠ϓϩοτͨ͠ࢄ෍
ਤͰ͋ΔɽλΠτϧͷӈʹ‫ه‬ड़͞Εͨ n ͸ߋ৽ॱͱྨࣅ౓ॱͷΧόϨοδΛൺֱͨ͠ૠೖߦͷ਺Ͱ
͋Δɽॎ࣠ํ޲ʹߋ৽ॱʢFreshnessʣͷΧόϨοδɼԣ࣠ํ޲ʹྨࣅ౓ॱʢSimilarityʣͷΧόϨο
δΛऔΔɽϓϩοτ͞Εͨ఺͕Լʹ͋Δ΄Ͳͦͷૠೖߦ͕ߋ৽ॱʹ͓͍ͯ༏ઌతʹબ୒͞ΕΔ͜ͱ
Λࣔ͢ɽϓϩοτ͞Εͨ఺͕ࠨʹ͋Δ΄Ͳͦͷૠೖߦ͕ྨࣅ౓ॱʹ͓͍ͯ༏ઌతʹબ୒͞ΕΔ͜ͱΛࣔ͢ɽ֤ทʹ͓͍ͯԼ෦ʹଘࡏ͢Δ 2 ͭͷਤ͸ߋ৽ॱͱྨࣅ౓ॱΛ૊Έ߹ΘͤΔ͜ͱͰͲΕ͘Β͍ͷૠೖߦ͕બ୒Ͱ͖Δ͔Λදͨ͠ਤͰ͋Γɼࢄ෍ਤΛ‫࡞ʹج‬੒͍ͯ͠Δɽࠨ͸ͦΕͧΕͷ‫ج‬४ͷΧόϨο
δ͕ 0.1 ҎԼͰ͋Δૠೖߦͷू߹ʹΑΔϕϯਤͰ͋Δɽӈ͸ͦΕͧΕͷ‫ج‬४ͷΧόϨοδ͕ 0.2 ҎԼͰ͋Δૠೖߦͷू߹ʹΑΔϕϯਤͰ͋ΔɽFreshness0.1ɼFreshness0.2 ͸ͦΕͧΕߋ৽ॱͷΧόϨο
δ͕ 0.1 ҎԼɼ0.2 ҎԼͰ͋Δૠೖߦͷू߹Λද͢ɽSimilarity0.1ɼSimilarity0.2 ͸ͦΕͧΕྨࣅ౓ॱͷͷΧόϨοδ͕ 0.1 ҎԼɼ0.2 ҎԼͰ͋Δૠೖߦͷू߹Λද͢ɽ

14

0.6
0.4
0.0

0.2

Freshness

0.8

1.0

Apache httpd (n=4729)

0.0

0.2

0.4

0.6

0.8

1.0

Similarityਤ 5: ߋ৽ॱͱྨࣅ౓ॱͷؔ܎ʢApache httpdʣ

Freshness0.1

1,079

1,715

Similarity0.1

Freshness0.2

734

1,083

(a) ΧόϨοδ 0.1 ҎԼSimilarity0.2

2,186

609

(b) ΧόϨοδ 0.2 ҎԼਤ 6: ֤‫ج‬४ͰΧόϨοδͷখ͍͞ૠೖߦͷू߹ʹΑΔϕϯਤʢApache httpdʣ

15

0.6
0.4
0.2
0.0

Freshness

0.8

1.0

CBMC (n=1209)

0.0

0.2

0.4

0.6

0.8

1.0

Similarity

ਤ 7: ߋ৽ॱͱྨࣅ౓ॱͷؔ܎ʢCBMCʣ

Freshness0.1

280

483

Similarity0.1

Freshness0.2

204

271

(a) ΧόϨοδ 0.1 ҎԼSimilarity0.2

610

174

(b) ΧόϨοδ 0.2 ҎԼਤ 8: ֤‫ج‬४ͰΧόϨοδͷখ͍͞ૠೖߦͷू߹ʹΑΔϕϯਤʢCBMCʣ

16

0.6
0.4
0.2
0.0

Freshness

0.8

1.0

JabRef (n=1675)

0.0

0.2

0.4

0.6

0.8

1.0

Similarity

ਤ 9: ߋ৽ॱͱྨࣅ౓ॱͷؔ܎ʢJabRefʣ

Freshness0.1

387

569

Similarity0.1

Freshness0.2

267

397

(a) ΧόϨοδ 0.1 ҎԼSimilarity0.2

778

186

(b) ΧόϨοδ 0.2 ҎԼਤ 10: ֤‫ج‬४ͰΧόϨοδͷখ͍͞ૠೖߦͷू߹ʹΑΔϕϯਤʢJabRefʣ

17

0.6
0.4
0.2
0.0

Freshness

0.8

1.0

jEdit (n=5996)

0.0

0.2

0.4

0.6

0.8

1.0

Similarity

ਤ 11: ߋ৽ॱͱྨࣅ౓ॱͷؔ܎ʢjEditʣ

Freshness0.1

1,779

1,577

Similarity0.1

Freshness0.2

693

1,932

(a) ΧόϨοδ 0.1 ҎԼSimilarity0.2

2,008

641

(b) ΧόϨοδ 0.2 ҎԼਤ 12: ֤‫ج‬४ͰΧόϨοδͷখ͍͞ૠೖߦͷू߹ʹΑΔϕϯਤʢjEditʣ

18ߋ৽ॱͱྨࣅ౓ॱͷؔ܎ੑʹ͍ͭͯߟ࡯͢Δɽ֤ιϑτ΢ΣΞͷࢄ෍ਤʹ͓͍ͯ࣠෇ۙʹଟ͘ͷ఺͕ϓϩοτ͞Ε͍ͯΔ͜ͱ͕෼͔ΔɽSimilarity ࣠෇ۙͷ఺͸ߋ৽ॱͰ༏ઌతʹબ୒͞ΕΔૠೖߦ
Λද͢ɽFreshness ࣠෇ۙͷ఺͸ྨࣅ౓ॱͰ༏ઌతʹબ୒͞ΕΔૠೖߦΛද͢ɽ࣠෇ۙͷ఺Ͱ͋Δૠೖߦͷ਺͸ͦΕͧΕͷιϑτ΢ΣΞͷϕϯਤ͔ΒಡΈऔΔ͜ͱ͕Ͱ͖ΔɽΧόϨοδ͕ 0.1 ҎԼͷૠೖߦͷू߹ʹΑΔϕϯਤʹ஫໨͢ΔɽͲͷιϑτ΢ΣΞʹ͓͍ͯ΋ɼߋ৽ॱͰΧόϨοδ͕ 0.1 ҎԼͰ͋Γɼྨࣅ౓ॱͰΧόϨοδ͕ 0.1 ΑΓେ͖͍ૠೖߦ͕ଟ਺ଘࡏ͢ΔɽΧόϨοδ͕ 0.2 ҎԼͷૠೖߦͷू߹ͷϕϯਤͰ΋ಉ༷ͷ͜ͱ͕͍͑ΔɽΑͬͯɼߋ৽ॱͰ͸༏ઌతʹબ୒͞ΕΔ͕ɼྨࣅ౓ॱ
Ͱ͸༏ઌతʹબ୒͞Εͳ͍ૠೖߦ͕ଟ਺ଘࡏ͢Δ͜ͱ͕Θ͔ͬͨɽߋ৽ॱͱྨࣅ౓ॱΛ૊Έ߹ΘͤͯߦΛબ୒͢Δ‫ج‬४ʹ͍ͭͯߟ͑Δɽ֤ϕϯਤ಺ͷ਺஋Λ଍͋͠ΘͤΔͱද 4 ͷΑ͏ʹͳΔɽൺֱͨ͠ૠೖߦͷ਺͸ɼߋ৽ॱͱྨࣅ౓ॱͷΧόϨοδΛൺֱͨ͠ૠೖ
ߦͷ਺Ͱ͋ΔɽΧόϨοδ͕ 0.1 ҎԼͷ࿨ɼ0.2 ҎԼͷ࿨͸ɼߋ৽ॱͱྨࣅ౓ॱͷͲͪΒ͔Ұํͷ‫ج‬४ͰΧόϨοδ͕ 0.1 ҎԼɼ0.2 ҎԼͰ͋ΔΑ͏ͳૠೖߦͷ਺Ͱ͋Δɽߋ৽ॱͱྨࣅ౓ॱͷͲͪΒ͔Ұํͷ‫ج‬४ͰΧόϨοδ͕ 0.1 ҎԼͰ͋ΔΑ͏ͳૠೖߦ͸શମͷ໿ 70%ɼ0.2 ҎԼͰ͋ΔΑ͏ͳૠೖߦ͸શମͷ໿ 80%ଘࡏ͢ΔɽϕϯਤΑΓɼยํͷ‫ج‬४ͰͷΈΧόϨοδ͕খ͍͞ૠೖߦ͕ଟ਺ଘࡏ
͢ΔͷͰɼ‫͍ޓ‬ͷ‫ج‬४͕૬खͷ‫ج‬४ͷܽ఺Λิ͍ͬͯΔ͜ͱ͕෼͔ΔɽΑͬͯɼߋ৽ॱͱྨࣅ౓ॱΛ૊Έ߹ΘͤͯߦΛબ୒͢Δ‫ج‬४Λ࠶ར༻ʹ‫ࣗͮ͘ج‬ಈϓϩάϥϜमਖ਼ख๏ʹ࣮૷͢Δ͜ͱͰɼܽؕ
ͷमਖ਼ʹ͔͔Δ࣌ؒΛ୹ॖͰ͖ΔՄೳੑ͕͋Δɽ͜ͷͱ͖ɼߋ৽ॱͱྨࣅ౓ॱΛ૊Έ߹ΘͤΔ‫ج‬४ʹΑΔख๏͸ɼࣗಈϓϩάϥϜमਖ਼ͷ࠷ॳʹͦΕͧΕͷ‫ج‬४ʹΑͬͯૠೖީิΛॱҐ෇͚͢ΔॲཧΛߦ͏ඞཁ͕͋ΓɼͦΕͧΕͷ‫ج‬४Λ୯ಠͰ࢖༻͢ΔΑΓ࣌ؒΛཁͯ͠͠·͏ͱ͍͏σϝϦοτ͕͋Δɽ‫ج‬४Λ૊Έ߹Θͤͯ࠶ར༻ʹ‫ࣗͮ͘ج‬ಈϓϩάϥϜमਖ਼ख๏ʹ࣮૷Λ͢Δͱ͖͸ɼͦΕͧΕͷॱҐ෇͚ͷॲཧΛฒྻϓϩάϥϛϯάΛ༻͍ͯߦ͏ͳͲɼσϝϦοτΛߟྀ࣮ͨ͠૷͕ඞཁʹͳΔɽද 4: ߋ৽ॱͱྨࣅ౓ॱͷ૊Έ߹ΘͤʹΑΔૠೖߦͷׂ߹ϓϩάϥϜൺֱͨ͠ૠೖߦͷ਺ΧόϨοδ 0.1 ҎԼͷ࿨ΧόϨοδ 0.2 ҎԼͷ࿨

Apache httpd

4,729

3,528 (74.6%)

3,878 (81.8%)

CBMC

1,209

967 (80.0%)

1,055 (87.2%)

JabRef

1,675

1,223 (73.0%)

1,361 (81.3%)

jEdit

5,996

4,049 (67.5%)

4,582 (76.4%)

19

6ଥ౰ੑ΁ͷ‫ڴ‬Җ͜ͷষͰ͸ຊ‫ڀݚ‬ͷௐࠪʹ͓͚Δଥ౰ੑ΁ͷ‫ڴ‬Җʹ͍ͭͯड़΂Δɽຊ‫Ͱڀݚ‬͸ɼܽؕͷमਖ਼͕ߦΘΕͨίϛοτΛද͢मਖ਼ίϛοτΛɼίϛοτϩάʹಛఆͷमਖ਼ʹؔ͢ΔΩʔϫʔυΛ‫ؚ‬ΉίϛοτɼͱఆΊ͍ͯΔɽͦͷͨΊɼΩʔϫʔυΛ‫͕͍ؕܽͳ·ؚ‬ͷमਖ਼ΛߦͬͨίϛοτΛର৅ʹ͢Δ͜ͱ͕Ͱ͖͍ͯͳ͍ɽ·ͨɼΩʔϫʔυΛ‫ؚ‬Ή͕ܽؕͷमਖ਼Λߦ͍ͬͯͳ͍ίϛοτΛର৅ʹͯ͠͠·͍ͬͯΔՄೳੑ͕ߟ͑ΒΕΔɽ
ຊ‫Ͱڀݚ‬͸ɼܽؕͷमਖ਼ʹ༻͍ΒΕͨߦΛද͢ૠೖߦΛमਖ਼ίϛοτʹ͓͍ͯߋ৽͞Εͨશͯͷߦͱ͍ͯ͠Δɽ͔͠͠ɼܽؕͷमਖ਼ͷࡍʹ͸मਖ਼ͱ͸ແؔ܎ͷߦΛಉ࣌ʹίϛοτ͢Δ͜ͱ͕ߟ͑Β
ΕΔɽͦͷΑ͏ͳ৔߹ɼૠೖߦʹमਖ਼ͱ͸ແؔ܎ͳߦ͕‫·ؚ‬ΕΔՄೳੑ͕͋Δɽຊ‫Ͱڀݚ‬͸ɼ࣮‫ݧ‬ର৅ͱͯ͠ 4 ͭͷιϑτ΢ΣΞͷιʔείʔυϦϙδτϦΛௐࠪͨ͠ɽ࣮‫ݧ‬ର৅ͷιʔείʔυϦϙδτϦΛมߋ͢Δͱௐࠪͷ݁Ռ͕มΘΔՄೳੑ͕͋ΔɽϓϩάϥϜ͸ C ‫ܥ‬ͷ‫ݴ‬‫͔ޠ‬Β 2 ͭɼJava ͔Β 2 ͭબ୒ͯ͠ର৅ͱ͍ͯ͠ΔɽͦΕҎ֎ͷ‫ޠݴ‬ͷϓϩάϥϜͰ͸ௐࠪΛߦ͍ͬͯͳ͍ɽͦͷΑ͏ͳ‫ޠݴ‬Λର৅ͱͨࣗ͠ಈϓϩάϥϜमਖ਼ख๏ʹߋ৽ॱΛ࣮૷͢Δࡍʹ͸࠶౓ௐࠪΛߦ͏΂͖Ͱ͋Δɽ

20

7

͋ͱ͕͖
ຊ‫Ͱڀݚ‬͸ɼ࠶ར༻ʹ‫ࣗͮ͘ج‬ಈϓϩάϥϜमਖ਼ʹ͓͚Δૠೖީิͷબ୒ख๏ͱͯ͠ɼߋ৽ॱͱ͍

͏‫ج‬४Λ༻͍Δ͜ͱΛఏҊͨ͠ɽߋ৽ॱͷ༗༻ੑΛௐ΂ΔͨΊʹɼΦʔϓϯιʔειϑτ΢ΣΞͰա‫ߦʹڈ‬ΘΕͨܽؕͷमਖ਼ʹ͓͍ͯૠೖ͞ΕͨߦΛ༻͍ͯௐࠪΛߦͬͨɽௐࠪͷ݁Ռɼର৅ͷߦͷ͏ͪ
໿ 6 ׂͷߦ͕ߋ৽ॱͰૠೖީิͷ 10%ͷߦΛબ୒͢Δ·Ͱʹબ୒͞Ε͍ͯΔ͜ͱ͕Θ͔ͬͨɽ͞Βʹɼ‫ط‬ଘ‫ڀݚ‬ͷ‫ج‬४Ͱ͋Δྨࣅ౓ॱʹΑΔख๏Λಉ༷ͷର৅ʹద༻͢Δ͜ͱͰɼྨࣅ౓ॱͱߋ৽ॱͷൺֱΛߦͬͨɽͦͷ݁Ռɼྨࣅ౓ॱͰ͸༏ઌతʹબ୒͞Εͳ͍͕ߋ৽ॱͰ͸༏ઌతʹબ୒͞ΕΔߦ͕
ଟ਺ଘࡏ͢Δ͜ͱ͕Θ͔ͬͨɽࠓ‫ޙ‬ͷ՝୊͸ɼૠೖީิ͔ΒߦΛબ୒͢Δ‫ج‬४ͱͯ͠ɼߋ৽ॱ୯ಠ·ͨ͸ߋ৽ॱͱྨࣅ౓ॱΛ૊Έ߹Θͤͨ‫ج‬४Λ࠶ར༻ʹ‫ࣗͮ͘ج‬ಈϓϩάϥϜमਖ਼ख๏ʹ࣮૷ͯ͠ɼࣗಈϓϩάϥϜमਖ਼ʹཁ͢Δ
࣌ؒΛ୹ॖͰ͖Δ͔Ͳ͏͔ௐ΂Δ͜ͱͰ͋Δɽ

21ँࣙຊ‫ڀݚ‬Λߦ͏ʹ͋ͨΓɼཧղ͋Δ͝ࢦಋΛࣀΓɼஆ͔͘ྭ·ͯ͠௖͖·ͨ͠ೇຊਅೋ‫ڭ‬तʹ৺ΑΓ‫ँײ‬ਃ্͛͠·͢ɽຊ‫ڀݚ‬ͷશաఔΛ௨ͯ͠ɼ‫ʹڀݚ‬ର͢Δߟ͑ํ΍ํ޲ੑͳͲɼஸೡͳ͝ࢦಋ͔ͭత֬ͳ͝ॿ‫ݴ‬Λ௖͖·ͨ͠ං‫ޙ‬๕थ।‫ڭ‬तʹ৺ΑΓ‫ँײ‬ਃ্͛͠·͢ɽຊ‫ڀݚ‬Λߦ͏ʹ͋ͨΓɼٞ࿦ͷதͰ‫و‬ॏͳ͝ॿ‫ࢦ͝ݴ‬ಋΛ௖͖·ͨ͠㤟ຊਅ༎ॿ‫ʹڭ‬৺ΑΓ‫ँײ‬ਃ্͛͠·͢ɽ
ຊ‫ڀݚ‬ͷશաఔΛ௨ͯ͠ɼ೔ৗͷதͰ੠Λ͔͚ͯ௖͖ɼ‫ڀݚ‬ͷ‫ૅج‬ΛҰ͔Βࢦಋͯ͠௖͖·ͨ͠େࡕେֶେֶӃ৘ใՊֶ‫ڀݚ‬ՊίϯϐϡʔλαΠΤϯεઐ߈ത࢜લ‫ظ‬՝ఔ 1 ೥ͷԣࢁ੖थࢯʹਂ͘‫ײ‬ँਃ্͛͠·͢ɽͦͷଞͷೇຊ‫ࣨڀݚ‬ͷօ༷ͷ͝‫ʹྗڠ‬৺ΑΓ‫ँײ‬க͠·͢ɽ࠷‫ʹޙ‬ɼຊ‫ࢸʹڀݚ‬Δ·Ͱʹɼߨٛɼԋशɼ࣮‫ݧ‬౳Ͱ͓ੈ࿩ʹͳΓ·ͨ͠େࡕେֶ‫ֶ޻ૅج‬෦৘ใՊֶՊͷॾઌੜํʹɼ͜ͷ৔ΛआΓͯ৺͔Β‫ྱޚ‬ਃ্͛͠·͢ɽ22ࢀߟจ‫ݙ‬[1] Tom Britton, Lisa Jeng, Graham Carver, Paul Cheak, and Tomer Katzenellenbogen. Reversible debugging software. University of Cambridge-Judge Business School, Tech. Rep, 2013.
[2] L. A. Clarke. A system to generate test data and symbolically execute programs. IEEE Trans.
Softw. Eng., pp. 215–222, 1976.
[3] Carlos Pacheco, Shuvendu K. Lahiri, Michael D. Ernst, and Thomas Ball. Feedback-directed
random test generation. In ICSE ’07, pp. 75–84, 2007.
[4] Carlos Pacheco. Directed Random Testing. PhD thesis, MIT Department of Electrical Engineering and Computer Science, 2009.
[5] Rupak Majumdar and Koushik Sen. Hybrid concolic testing. In ICSE ’07, pp. 416–426, 2007.
[6] James A. Jones, Mary Jean Harrold, and John Stasko. Visualization of test information toassist fault localization. In ICSE ’02, pp. 467–477, 2002.
[7] Xinming Wang, S. C. Cheung, W. K. Chan, and Zhenyu Zhang. Taming coincidental correctness: Coverage reﬁnement with context patterns to improve fault localization. In ICSE ’09,
pp. 45–55, 2009.
[8] Rui Abreu, Peter Zoeteweij, and Arjan JC Van Gemund. On the accuracy of spectrum-based
fault localization. In Testing: Academic and Industrial Conference Practice and ResearchTechniques-MUTATION, 2007. TAICPART-MUTATION 2007, pp. 89–98, 2007.
[9] Claire Le Goues, Michael Dewey-Vogt, Stephanie Forrest, and Westley Weimer. A systematic
study of automated program repair: Fixing 55 out of 105 bugs for $8 each. In ICSE ’12, pp.
3–13, 2012.
[10] Yuhua Qi, Xiaoguang Mao, Yan Lei, Ziying Dai, and Chengsong Wang. The strength of
random search on automated program repair. In ICSE ’14, pp. 254–265, 2014.
[11] Hoang Duong Thien Nguyen, Dawei Qi, Abhik Roychoudhury, and Satish Chandra. Semﬁx:
Program repair via semantic analysis. In ICSE ’13, pp. 772–781, 2013.
[12] Dongsun Kim, Jaechang Nam, Jaewoo Song, and Sunghun Kim. Automatic patch generation
learned from human-written patches. In ICSE ’13, pp. 802–811, 2013.
[13] Leonardo De Moura and Nikolaj Bjørner.
TACAS’08/ETAPS’08, pp. 337–340, 2008.

23

Z3:

An eﬃcient smt solver.

In[14] ԣࢁ੖थ, େాਸ࢙, ງా‫ܓ‬༎, ං‫ޙ‬๕थ, Ԭ໺ߒࡾ, ೇຊਅೋ. ࠶ར༻ʹ‫ࣗͮ͘ج‬ಈόάमਖ਼ʹ
͓͚Δ࠶ར༻ީิͷߜࠐʹ޲͚ͨௐࠪ. ిࢠ৘ใ௨৴ֶձٕज़‫ڀݚ‬ใࠂ, ୈ 115 ‫ר‬, pp. 047–052,

2015.
[15] John R Koza. Genetic Programming: On the Programming of Computers by Means of Natural
Selection, Vol. 1. MIT press, 1992.
[16] Westley Weimer, ThanhVu Nguyen, Claire Le Goues, and Stephanie Forrest. Automaticallyﬁnding patches using genetic programming. In ICSE ’09, pp. 364–374, 2009.
[17] Stephanie Forrest, ThanhVu Nguyen, Westley Weimer, and Claire Le Goues. A genetic programming approach to automated software repair. In Proceedings of the 11th Annual conference on Genetic and evolutionary computation, pp. 947–954, 2009.
[18] Earl T. Barr, Yuriy Brun, Premkumar Devanbu, Mark Harman, and Federica Sarro. The
plastic surgery hypothesis. In FSE ’14, pp. 306–317, 2014.
[19] Gregg Rothermel, Roland H Untch, Chengyun Chu, and Mary Jean Harrold. Prioritizing
test cases for regression testing. Software Engineering, IEEE Transactions on, Vol. 27, pp.
929–948, 2001.
[20] Robert A. Wagner and Michael J. Fischer. The string-to-string correction problem. J. ACM,
Vol. 21, pp. 168–173, 1974.

24