修士学位論文

題目

ソースコードの変更予測手法を用いた自動プログラム修正の高速化手法

指導教員
楠本

真二

教授

報告者
鷲見

創一

平成 29 年 2 月 7 日

大阪大学 大学院情報科学研究科
コンピュータサイエンス専攻

平成 28 年度 修士学位論文

ソースコードの変更予測手法を用いた自動プログラム修正の高速化手法
鷲見

創一

内容梗概
近年，自動プログラム修正手法が注目されている．自動プログラム修正手法の中に，既存プログラ
ムの再利用に依る手法がある．再利用に基づく自動プログラム手法では，修正対象プログラムからプ
ログラム文を取得して，欠陥であると特定された箇所へそのプログラム文を挿入する．修正対象プロ
グラム中にはプログラム文が大量に存在しており，既存手法ではランダムにそれらの中からプログラ
ム文を取得するため，修正に長い時間を要する．一方で，プログラムの構文情報と開発履歴を入力として，次の変更後にプログラムが持つ構文情報を予測するソースコードの変更予測手法が提案されている．予測結果と予測対象の構文情報を比較することによって次にどのような構文情報を持つプロ
グラム文が追加される可能性が高いかを予測できる．そのようなプログラム文を修正に用いること
により，修正に要する時間を大きく削減できると考えられる．
そこで本研究では，ソースコードの変更予測を用いて自動プログラム修正手法を高速化する手法を提案する．オープンソースソフトウェアの開発過程で発生した欠陥に対して提案手法を適用した結果を報告する．評価実験の結果，83 パターン中 40 パターンで提案手法がより高速に修正を行った．また，既存手法よりも 5 つ多くの欠陥を修正した．平均修正時間で比較すると約 20%の削減であった．

主な用語
デバッグ
プログラム自動修正
コード再利用機械学習
遺伝的プログラミング目次
1 まえがき

1

2 準備

3

2.1

バージョン管理システム . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

2.2

抽象構文木

4

2.3

プログラムのテスト. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 関連研究56

3.1

欠陥箇所の限局 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

3.2

自動プログラム修正. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

3.2.1

再利用に基づく手法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

3.2.2

プログラム意味論に基づく手法 . . . . . . . . . . . . . . . . . . . . . . . . .

8

3.2.3

修正パターンに基づく手法 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

3.2.4

自動プログラム修正手法の比較実験 . . . . . . . . . . . . . . . . . . . . . . .

94 ソースコードの変更予測手法

11

4.1

状態ベクトル . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

4.2

ソースコードの変更予測 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

125 提案手法13

5.1

STEP1:データベースの構築. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

5.2

STEP2:プログラム文の推薦. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

6 実装

15

6.1

変更予測の実装 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

6.2

状態ベクトルの取得方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

6.3

欠陥修正コミットの特定 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

7 評価実験

16

7.1

実験対象 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

7.2

実験条件の統一 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

7.3

実験結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

178 妥当性の脅威

28

9 まとめと今後の課題

29

i

謝辞

30

参考文献

31

ii

図目次
1

バージョン管理システム . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

抽象構文木の例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

3

GenProg の動作の流れ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

74

状態ベクトルの例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

5

ソースコードの変更予測手法の概要 . . . . . . . . . . . . . . . . . . . . . . . . . . .

126

提案手法の概要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

137

提案手法の詳細 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

148

実験結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

189

実験結果 (seed=0) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1910

実験結果 (seed=1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1911

実験結果 (seed=2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

12

開発者と等価な修正パッチの例 (Math-5) . . . . . . . . . . . . . . . . . . . . . . . .

26

13

開発者と等価な修正パッチの例 (Math-22) . . . . . . . . . . . . . . . . . . . . . . . .

26

14

全てのテストケースは通過するが正しくないパッチの例 (Math-53) . . . . . . . . . .

26

15

全てのテストケースを通過するが正しくないパッチの例 (Math-31) . . . . . . . . . .

27

iii

表目次
1

Defects4J の詳細 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

162

実験結果 (seed=0) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

233

実験結果 (seed=1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

244

実験結果 (seed=2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25iv

1 まえがき
デバッグはソフトウェアの信頼性の向上のために避けることのできない作業である．ソフトウェア
開発においてデバッグは多くの労力を必要とする作業であり，開発工数の半数以上を占めると言われている [1]．そのため，デバッグの支援を目的とした多くの研究が行われている．
デバッグを行う際には，欠陥の所在の特定を行い，適切な修正方法を決定し，修正を適用する．デバッグを支援するため，欠陥箇所の限局手法 [7] や欠陥の理解を支援する手法などが提案されている[8]．しかしこれらの手法を用いたとしても，適切な修正方法の決定やプログラムの変更は必要である．そこで，近年欠陥箇所の特定と修正の適用を自動的に行う自動プログラム修正手法が提案されている．
自動プログラム修正手法の 1 つに，修正対象プログラムのプログラム文を用いて欠陥箇所を変更したプログラム (以降，変異プログラムと呼ぶ) の生成，評価を繰り返し行うことによりプログラムを修正する手法がある．この手法の１つとして，Weimer らが開発した GenProg がある [11]．GenProg
は変異プログラムを複数生成し，遺伝的プログラミングに基づいて変異プログラムの評価，選択を繰り返すことにより欠陥の修正を行う．欠陥箇所の変更には修正対象プログラムに存在するプログラム
文を用いる．また，プログラムの修正が完了したかどうかは，変更が加えられたプログラムが全てのテストを通過するかどうかによって判定する．

GenProg は 8 つのオープンソースソフトウェア (以下，OSS と呼ぶ) に対して適用され，105 個中
55 個の欠陥の修正に成功することによってその有効性を示した [11]．しかし，修正対象プログラム
中に存在しないプログラム文が必要な欠陥は修正できないことや，修正に要する時間は修正成功の場
合は平均 1 時間 36 分，修正失敗の場合は平均 11 時間 12 分と，修正に時間を要する事が課題である．

GenProg は変異プログラムを生成する際に修正対象プログラムからプログラム文をランダムに取得して，欠陥箇所の変更に用いる．修正対象プログラムにはプログラム文が大量に存在するため，効率的に修正を行えない場合が多い．
一方で，プログラムの構文情報と開発履歴を入力として，次の変更後にプログラムが持つ構文情報を出力するソースコードの変更予測手法が提案されている [31]．この手法によって得られる構文情報の予測結果と，予測対象の構文情報を比較することによって，次にどのような構文情報を持つプログ
ラム文が追加される可能性が高いか予測できる．追加される可能性が高いプログラム文を変異プロ
グラムの生成に用いることにより，修正に要する時間を大きく削減できると考えられる．
そこで本研究では，ソースコードの変更予測を用いて自動プログラム修正手法を高速化する手法を提案する．提案手法は修正対象プログラム，修正箇所の情報と修正対象プロジェクトの変更履歴を入力として，ソースコードの変更予測手法を用いて，追加されるプログラム要素を持つプログラム文を出力する．出力されたプログラム文は次の変更時に追加される可能性が高いプログラム文である
ため，このプログラム文を変異プログラムの生成に用いることで，全てのテストを通過するまでに生成される変異プログラムの数が減少すると考えられる．そのためテストケースを実行する回数が減1

り，自動プログラム修正を高速化できると考えられる．
また，提案手法を評価するために OSS の開発過程で発生した欠陥に対して提案手法と GenProg を適用した．評価実験の結果，提案手法は平均修正時間を約 20%短縮できていることを確認した．以下に，実験によって得られた結果をまとめる．

• 提案手法は GenProg に対して平均修正時間を約 20%削減し，特に GenProg が修正に長い時間を要する欠陥の修正を早く終えることを確認した• 提案手法と GenProg のどちらか一方のみによって修正された 17 個の欠陥のうち，11 個が提案手法によって，6 個が GenProg によって修正された．提案手法は GenProg よりも 5 つ多くの欠陥を修正した• 提案手法と GenProg の少なくともどちらか一方によって修正された 64 個の欠陥のうち，提案
手法のほうが早く修正を終えたものは 29 個，GenProg のほうが早く修正を終えたものは 35 個であり，早く修正を終える欠陥の個数自体には大きな差は見られなかった
以降，2 章で準備について述べる．3 章で自動プログラム修正の関連研究について述べ，4 章で提案手法が用いるソースコードの変更予測手法について述べる．5 章で提案手法，6 章でその実装について述べる．7 章で提案手法を評価するために行った評価実験について述べ，8 章で実験結果の考察を行う．9 章で妥当性の脅威を述べ，10 章で本研究のまとめについて述べる．

2

リモート

リビジョン1

リビジョン2

リビジョン3

リビジョン4

リモート
リポジトリ
更新

取得

更新

取得

取得

更新

ローカル
リポジトリ

リビジョン1

リビジョン2

リビジョン2

リビジョン3

リビジョン3

リビジョン4

開発者A

開発者B

開発者C

ローカル

ローカル

ローカル

図 1: バージョン管理システム

2 準備
本章では，本論文で使用する用語について述べる．

2.1 バージョン管理システム
バージョン管理システムとは，ソースファイルやドキュメントなどのファイルに行われる変更を管理するシステムのことである．バージョン管理システムとは，ファイルの変更履歴を管理するシステ
ムである．バージョン管理システムの概要を図 1 に示す．バージョン管理の主な機能は以下の 2 つである．バージョン管理システムには，CVS[2], Subversion[3], Git[4] などがあり，ソフトウェア開発において広く用いられている．

• 変更情報の保持バージョン管理システムは，管理対象となっているファイルがいつ，誰によって変更されたかを保持する．例えばソフトウェア開発の際には，ある機能を変更することにより，他の機能が意図通り動作しなくなる場合がある．また，ソフトウェアの開発時に過去に発生した欠陥と似た欠陥が発生する場合がある．これらのような場合に，欠陥がある機能に対応したソースコー
ドが変更前にどのような状態であったか知ることができれば，欠陥の修正が容易となる．これ3

public int max(int x,int y){if(x>=y){return x;}else{
return y;}}(a) ソースコード

METHOD_DECLARATIONMODIFIERPRIMITIVE_TYPE

SIMPLE_NAME

BLOCK
IF_STATEMENTINFIX_EXPRESSIONSIMPLE_NAMESIMPLE_NAME

BLOCK

BLOCK

RETURN_STATEMENTRETURN_STATEMENTSIMPLE_NAMESIMPLE_NAME(b) 抽象構文木
図 2: 抽象構文木の例

らのような場合に変更履歴が管理されていれば，過去の変更を参照することにより欠陥の修正を行いやすい．

• 変更情報の共有
バージョン管理システムは，各変更をリビジョンという単位で保持している．例えばソフトウェ
ア開発では複数人でソフトウェアを開発する場合がある．バージョン管理管理システムは過去に誰がどのような変更を行ったかを保持しているため，開発者が他の開発者がどのような作業を行っているのか把握するのに役立つ．また，多くのバージョン管理システムには複数の開発者が同じファイルに変更を加えた場合，各開発者が行った変更を可視化し，統合を支援する機能が実装されている．

2.2 抽象構文木
抽象構文木とは，プログラムの構造を木構造で表したものである．図 4(a), 図 4(b) にプログラムとその抽象構文木を示す．図 4(b) の抽象構文木は，15 個のノードを持つ．抽象構文木の構造はプログ
ラムの構造に対応しており，根にはメソッド宣言，葉には識別子という構造となっている．抽象構文

4

木の各ノードは型や実際の値，プログラムにおける位置情報を持っており，抽象構文木を解析することによりプログラム中の文や式の情報を取得することが可能である．

2.3 プログラムのテスト
プログラムのテストとは，プログラム全体やその一部の機能が入力に対して正しい出力を返すかを検証する作業のことである．現在多くのプログラムは開発者が手作業で作成しているが，作成されたプログラムが正しいという保証はない．プログラムのテストにより，プログラムが与えた入力に対して正しい出力を行うかどうか確かめる事が可能である．以降，本論文では，テストを実行した結果，期待した結果が得られたテストを通過テスト，期待した結果を得られなかったテストを未通過テストと呼ぶ．

5

3 関連研究3.1 欠陥箇所の限局
欠陥箇所の限局手法は，欠陥である可能性の高い箇所を開発者に掲示する手法である．ここで，欠陥の可能性が高い箇所とは，与えられた入力に対して期待する結果を出力するプログラムを作成するために，変更すべき箇所のことである．現在多くの欠陥箇所の限局手法では，プログラムのテストの実行結果を利用して欠陥限局を行う [7][8][9]．具体的には，プログラムのテストを実行して通過しないテストが存在する場合に，通過テストと未通過テストの割合を用いて欠陥である可能性の高さを算出する．
上記した欠陥限局手法は比較実験が行われている．Xie らの提案した手法はテストカバレッジ (プログラム中の全ての行のうち，テストケースによって実行されるものの割合) が 100%という仮定の下で，理論的に Tarantula[7]，Ochiai[8] よりも少ない行数の調査で欠陥を発見できると報告されている．しかし Xie らの手法の理論的な保証にも関わらず，Le らは Ochiai[8] がもっとも効率よく欠陥箇所を限局することが約 200 個の欠陥への適用実験から分かったと報告している [10]．
また，上記した欠陥箇所の限局手法はほとんどの自動プログラム修正で変更する箇所の特定に用いられている．

3.2 自動プログラム修正
既存の自動プログラム修正手法は再利用に基づく手法 [11][12]，プログラム意味論に基づく手法[16][39]，修正パターンに基づく手法 [17][38][40] の 3 種類に分かれている．これらの手法は修正対象プログラムと失敗テストを含むテストスイートを入力として，修正が完了したプログラムを出力する．修正が完了したかどうかの判断には修正対象プログラムのテストスイートを用いる．以降では，それぞれの手法がどのように修正を行うか説明する．本節では各自動プログラム修正手法とその比較調査結果について述べる．

3.2.1 再利用に基づく手法
Weimer らは，再利用に基づく手法の 1 つである GenProg を提案した [11]．GenProg は修正対象プ
ログラムのプログラム文を用いて欠陥の箇所を変更したプログラム (以降，変異プログラムと呼ぶ)の生成，評価，選択を遺伝的プログラミングに基づいて行う．プログラムの変更はプログラム文単位で行う．図 3 に GenProg の動作の流れを示す．プログラムの変更で行うのは以下の処理のうちの1 つである．

6

入力：欠陥を含むプログ
ラムとテストケース
初期変異プログラム群生成

適応度の評価による選択

交差

変異

終了判定

NO

YES

出力：修正が行われた
プログラム
図 3: GenProg の動作の流れ

挿入 欠陥箇所の前または後ろにプログラム文の挿入を行う処理
削除 欠陥箇所を削除する処理
置換 欠陥箇所の削除と挿入を同時に行う処理

GenProg は OSS の開発過程で発生した欠陥に対して適用され，105 個中 55 個の欠陥を修正することにより，その有用性を示した [11]．しかし GenProg は，変異プログラムを評価する際に全てのテストケースを実行するため，計算コストが高い．そこで，Qi らは実行するテストケースに優先順位付けを行い，失敗したテストが現れた時点でテストの実行を打ち切ることにより高速にプログラムの修正を行う RSRepair を提案した [12]．Qi らは RSRepair を 8 つの OSS に対して適用し，GenProg
よりも多くの欠陥を短い時間で修正に成功したことを報告している．しかし，RSRepair は複数箇所の変更を必要とする欠陥を修正できない．

AE も GenProg を改良した手法である [20]．GenProg は意味的に等価なパッチを複数生成した場合でもテストを実行していた．AE は GenProg の修正過程において 2 つ目以降の等価なパッチが生成された場合にそのパッチのテスト実行をスキップする手法である．AE は GenProg よりも少ないテスト
実行回数でパッチを生成できたと報告されている．

HDRepair は開発者が行う修正と等価な修正が出力されやすくなるよう，GenProg を改良した手法

7

である [24]．HDRepair は 700 個の OSS をマイニングした結果から，GenProg が出力したパッチを
開発者の行った修正と等価な可能性が高い順に並び替える．評価実験から，GenProg は Defects4j[25]のデータセットの 90 個の欠陥に対して１つしか開発者の修正と等価な修正を行えなかったのに対し，HDRepair は 23 個修正したことを報告している．
3.2.2 プログラム意味論に基づく手法
プログラム意味論に基づく手法である SemFix では，テストスイートを用いて欠陥箇所を特定し，欠陥箇所に関わる全ての欠陥であると特定された箇所が満たすべき制約を導出し，制約を満たすプ
ログラム文を生成する [13]．Nguyen らはこの手法を 5 つのソフトウェアに対して適用し，GenProg
よりも多くの欠陥の修正に成功したことを報告している．再利用に基づく手法は既存ソースコードに存在しない記述による修正を行えないことに対し，プログラム意味論に基づく手法は既存ソース
コードに存在しない記述を用いた修正が可能であることが特徴である．この手法はテストスイートから欠陥の箇所が満たすべき論理式を導出し，その論理式を SMT ソルバを用いて解く [15]．SMT 問
題は NP-完全の問題であるため，論理式によっては現実的な時間で解くことができない．
そこで SemFix を改良した DirectFix が提案された [16]．DirectFix は，SemFix よりも修正に時間を要するが，人が理解しやすい修正を生成できると報告されている．

Nopol も SemFix を改良した手法である．Nopol は欠陥箇所が満たすべき制約を導出する際に記号化する文を絞り込むことにより，欠陥の修正を効率的に行えたと報告されている [14]．

Angelix は DirectFix を改良した手法である [39]．Angelix も欠陥箇所が満たすべき制約を導出する
際に記号化する文を絞り込む．この手法は Nopol と似ているが，複数箇所の変更が必要な修正に対応している点が異なっている．評価実験により Angelix は DirectFix と同程度の時間で欠陥の修正を行えたと報告されている．

ACS は Angelix を改良した手法である．ACS の工夫点は次の 3 つである．1 つ目は記号化した部
分に式や値を割り当てる際にどの変数が使われるべきかを判断する基準を設け，その基準に従って変数をソートし，割当時に利用する．2 つ目は修正対象の関数やメソッドに付属のドキュメント情報の利用である．例えば，ドキュメントに例外を吐くことと，その際に関係する変数が記述されており，かつその例外部分の記号へ割り当てを行う場合，ドキュメントに書いてある記号を用いた割り当てを試みる．3 つ目は変数と共に用いられやすい演算の適用である．ある if 文の条件式への記号割り当てを考えた場合を考える．記号に変数 hour を割り当てる事が決まっているときに hour に適用する演算としては < 12 や > 24 が適用されやすいと考えられる．演算の使われ方のマイニングにより，ACS は変数名に対する適用されやすさで演算を優先順位付けする．これらの工夫により，Xi ら
は ACS によって出力される修正パッチが開発者が行うパッチと等価なパッチである可能性を高めた．
既存のプログラム意味論に基づく手法 (Prophet[38], Angelix[39]) が開発者が行った修正と等価であった確率は 40%に満たない程度だったのに対し，ACS は 78.3% であったことを報告している．

8

3.2.3 修正パターンに基づく手法
修正パターンに基づく手法である PAR は Null チェックやオブジェクトの初期化など 10 個の修正パターンを定義しており，それらに基づいて修正を行う [17]．Kim らは 6 つの OSS への適用によって GenProg よりも多くの欠陥を修正することに成功し，理解しやすい修正を生成できたと報告している．SPR も修正パターンに基づく手法の 1 つである [40]．SPR は条件式の変更や値の変更，制御フロー文の導入など，6 つの修正パターンを定義してプログラムの修正を行う．PAR と比べて抽象的な修正パターンが定義されており，より多くの欠陥を修正可能なことや，条件式や値の探索を枝刈りによって効率的に行うことが特徴である．Long らは SPR を 8 つの OSS に対して適用し，開発者が行った修正と等価な修正を GenProg よりも多く行えたと報告している．

Tan らは SPR が開発者が行う修正と似た修正をより高い確率で行えるよう改良した手法である
mSPR を提案している [19]．Tan らは，SPR が意味的な削除の操作を行うときに開発者にとって有用ではないパッチが出力されることに着目した．意味的な削除とは，if 文やブロックの削除だけでなく，関数内への return 文の追加や，条件式中の識別子を操作する文の削除などのことである．mSPR は，

SPR の修正過程における意味的な削除を禁止することにより，より開発者が作成するパッチに近いパッチが修正できたことを報告している．

Prophet はより高い確率で開発者が行った修正と等価な修正 (以下，正しい修正と呼ぶ) が可能となるよう，SPR を改良した手法である [38]．Prophet はまず OSS の開発履歴から欠陥修正コミットを抽出する．そして，修正パターンと修正箇所の周囲の構文情報から SPR によって生成された修正パッチが正しい修正かどうか判定する確率モデルを構築する．最後に構築したモデルを用いて生成されたパッチを並べ替え，もっとも正しい修正である可能性が高い順に出力する．Long らは OSS の開発過程で発生した 69 個の欠陥に対して Prophet を適用し，18 個の欠陥に対して正しい修正を行う事ができたと報告している．しかし，定義された修正パターンに当てはまらないものは修正できないこと
や，複数箇所の変更が必要な欠陥は修正できないことが課題である．

3.2.4 自動プログラム修正手法の比較実験
上記した 3 項で述べた自動プログラム修正手法は全てテストケースを用いてプログラムの修正を行っている．これらの手法は全てのテストケースを通過すればプログラムの修正ができたとするため，生成したパッチが開発者の望む仕様を満たしていない可能性がある．Qi らは GenProg[11]，RSRepair[12]，AE[20] が生成した約 200 個のパッチを目視で調査し，調査対象のツールが出力するほとんどのパッチは開発者の作成したパッチと異なり，開発者には受け入れられないパッチであることを示した [41]．

Long らは GenProg と SPR が生成するパッチの質に関する調査を行った [22]．Long らはこれらのツールが生成したパッチのうち，どの程度が開発者が書いたパッチと等価で，どの程度がテストケー
スを通過するが開発者が生成するパッチとは異なるのかを調査した．GenProg と SPR が調査の結果，ほとんどの欠陥について全てのテストを通過するパッチは 1,000 個から 10,000 個と大量に存在し，開9

発者が書いたパッチと意味的に等しいパッチはそのうち 10 個程度であった．Long らは出力されるパッチが正しいパッチかどうか見分ける方法が必要だと主張した．
本研究は，再利用に基づく手法を対象とした自動プログラム修正の高速化手法を提案する．この手法は複数箇所の変更を必要とする欠陥を修正可能であり，より多くのソースコードを再利用元とする
ことによって，より多くの欠陥を修正可能である．そのため修正に長い時間を要するという課題を解決できればより有用な手法となると考えられる．

10

public int max(int x,int y){if(x>=y){return x;}else{
return y;}}(a) ソースコード

83< 0, … 3, … 1, … 1, … 1, … 1, … 2, … 5, … 1, … 0 >BLOCK
IF_STATEMENTINFIX_EXPRESSIONPRIMITIVE_TYPE

SIMPLE_NAME

METHOD_DECLARATION
RETURN_STATEMENTMODIFIER(b) 状態ベクトル
図 4: 状態ベクトルの例

4 ソースコードの変更予測手法
本章では，提案手法で用いるソースコードの変更予測手法 [31] について述べる．

4.1 状態ベクトル
状態ベクトルとは，ソースコード中に存在するプログラム要素の数のベクトルである．ここで，プログラム要素には if 文や return 文，変数宣言，識別子名などが含まれる．ソースコード中の各プロ
グラム要素の出現回数をカウントしたものが状態ベクトルとなる．
図 4 に状態ベクトルの例を示す．図 4(a) のメソッドを状態ベクトルにしたものが図 4(b) である．
図 4(a) のメソッドには，修飾子，基本型名，メソッド宣言，識別子名，return 文，if 文，２項演算子，ブロックの 8 種類のノードが出現している．状態ベクトルは 83 個の要素を持つため，それらの内の8 つの要素は 1 以上の値を持ち，残りの 75 要素が 0 となる．

11

変更履歴

2nd Stage
変更予測対象

1st Stage

予測結果

小さい
次の状態ベクトルの予測モデル<2, 2, 1, …, 4, 0, 1><4, 3, 1, …, 3, 0, 0>

変更の大きさの予測モデル 大きい

予測不可能

図 5: ソースコードの変更予測手法の概要

4.2 ソースコードの変更予測
本研究で用いるソースコードの変更予測手法について説明する．この手法はプログラムの開発履歴と変更予測対象の状態ベクトルを入力として受け取り，修正が加えられた後の状態ベクトルを出力する．予測結果と予測対象の状態ベクトルの差分を取る事によって，次の変更で追加，削除されるプ
ログラム要素の情報を取得可能である．
図 5 にソースコードの変更予測手法の処理の流れを示す．ソースコードの変更予測手法では，まずはじめに対象プログラムの開発履歴を入力として予測モデルを構築する．構築する予測モデルは 2種類である．1 つ目が次の変更が大きいか小さいかを予測するモデル，2 つ目が次の変更でどのプロ
グラム要素が追加または削除されるかを予測するモデルである．次に 1 つ目のモデルに状態ベクトルを与え，次の変更が大きいか小さいかを予測する．次の変更が小さいなら 2 つ目のモデルに状態ベク
トルを与え，変更後の状態ベクトルを得る．ソースコードの変更予測手法は大きい変更に対して精度良く予測を行う事ができないため，次の変更が大きいなら状態ベクトルの予測は行わない．変更の大きさは，変更前後の状態ベクトルのマンハッタン距離で表され，距離が定められた閾値以下なら変更
が小さいとする．また予測アルゴリズムには，1 つ目に k 近傍法，2 つ目に重回帰分析を用いている．
ソースコードの変更予測手法は 2 つの OSS に対して適用され，変更の大きさの閾値が 3 の場合に約 70%の精度で変更後の状態ベクトルの全ての要素の予測に成功したと報告されている．

12

GenProg

入力

入力

変更履歴

修正対象
プログラム

提案手法

欠陥箇所の限局
初期変異

Yes

プログラムの
変更予測

終了判定

No
選択と変異

次の変更時に追加される可能性が高い文

出力

出力

図 6: 提案手法の概要

5 提案手法
本研究では，自動プログラム修正を高速化する手法を提案する．提案手法の概要を図 6 に示す．提案手法は修正対象プログラム，修正箇所の情報と修正対象プロジェクトの変更履歴を入力として，追加されるプログラム要素を持つプログラム文を出力する．まず，ソースコードの変更予測手法を用いて，修正対象プログラムが次の変更でどのようなプログラム要素が追加されるかを予測する．そして，追加されるプログラム要素を持つプログラム文を修正対象プログラム中から取得する．
提案手法では，次の変更で追加されるプログラム要素の予測や，追加されるプログラム要素を持つプログラム文の検索の際にソースコードやプログラム文をプログラム要素の出現回数を要素としたベクトル (以降では状態ベクトルと呼ぶ) として表現する．本章では提案手法の処理の内容について述べる．
提案手法の詳細を図 7 に示す．提案手法は以下の 2 つの STEP に分かれている．

STEP1:データベースの構築
STEP2:プログラム文の推薦
STEP1 では修正対象プログラムからプログラム文とその状態ベクトルを抽出し，データベースに格納する．STEP2 では，修正対象プログラムと修正対象プロジェクトの変更履歴を入力として，追加されるプログラム要素を持つプログラム文の特定を行う．推薦されたプログラム文を自動プログラ
ム修正に用いることにより全てのテストケースを通過する変異プログラムが生成されるまでに生成される変異プログラムの数を減らし，全てのテストケースを通過する変異プログラムが実行される
テストを減らす事により修正を高速化可能であると考える．以降では各 STEP で行う処理について述
べた後，実装について述べる．

13

InputStep1

変更履歴 修正対象プログラム

プログラム文と状態ベクトルの集合

データベース<2, 2, 1, …, 4, 0, 1>

変更予測<2, 1, 0, …, 6, 1, 1>
予測結果<0, …,0, 2, 1, 0>
追加される要素

Step2

追加される要素を持つプログラム文

Output
図 7: 提案手法の詳細

5.1 STEP1:データベースの構築
STEP1 では，修正対象プログラムから抽象構文木を構築し，プログラム文と状態ベクトルを対応付けてデータベースに格納する．まず，修正対象プログラムから抽象構文木を構築する．そして抽象構文木のノードの内，プログラム文のノードを根とする全ての部分木を辿り，全てのプログラム文とその状態ベクトルを得る．最後に得られた状態ベクトルをキー，プログラム文をバリューとしてデー
タベースに格納する．

5.2 STEP2:プログラム文の推薦
STEP2 では，修正プログラムの状態ベクトル，修正対象プロジェクトの変更履歴を入力として，プ
ログラム修正のために追加されるプログラム要素を持つプログラム文の推薦を行う．
まず，ソースコードの変更予測手法を用いてプログラムの状態ベクトルと変更履歴から，状態ベク
トルが次の変更でどのような状態ベクトルになるかを予測する．その後，修正対象プログラムの次の状態ベクトルと元の状態ベクトルとの差分をとることにより，次の変更で追加されるプログラム要素の状態ベクトルを得る．最後に，追加されるプログラム要素の状態ベクトルをキーとして STEP1 で構築したデータベースに対して問い合わせを行うことにより，次の変更で追加されるプログラム文の集合を取得可能である．

14

6 実装
本節では提案手法の詳細な実装方法について述べる．実験ツールは，GenProg の Java 実装である

jGenProg[42] を一部変更して実装した．
6.1 変更予測の実装
提案手法は jGenProg が修正対象プログラムから挿入候補を選択し，変異プログラムを生成する部
分を変更して実装した．提案手法は jGenProg に組み込むため，本研究においてはソースコードの変更予測手法の実装は R を用いた村上らの実装 [32] とは異なり，Weka[33] を用いて実装した．変更予
測アルゴリズムには．変更の大きさ予測には k 近傍法 [34]，次の変更後の状態ベクトルの予測には線形回帰 [35] を用いた．
実験ツールは Git[4] でバージョン管理されたソフトウェアを対象とする．変更履歴の取得にはJGit[37] を用いた．
6.2 状態ベクトルの取得方法
状態ベクトルはソースコードから抽象構文木を構築して根から葉まで辿り，各プログラム要素の出
現回数をカウントしたものである．抽象構文木の構築には Eclipse JDT(Java Development Tools)[36] を用いた．JDT は抽象構文木の構築や操作が可能であり，各プログラム要素をあらわす 83 種類のノードが定義されている．そのため状態ベクトルの次元は 83 となる．また提案手法の STEP1 では，修正対象プログラムに存在する全てのプログラム文を取得する必要がある．これは抽象構文木のノードのうち，JDT の Statement クラスのサブクラスであるノードを根とする全ての部分木を辿る事により取得した．

6.3 欠陥修正コミットの特定提案手法の STEP2 では，ソースコードの変更予測手法を用いて次の変更でプログラムの状態ベク
トルがどうなるかを予測する．提案手法では，ソースコードの変更予測手法を欠陥の修正に用いるため，変更履歴から欠陥修正に関する変更のみを抽出して変更予測に用いる．これにより，次の欠陥の修正でどのような状態ベクトルになるかを予測可能である．欠陥の修正の特定はコミットコメントがbugfix ， fix などの欠陥の修正を表すキーワードを含んでいるかどうかによって判断した．

15

7 評価実験
本実験の目的は，ソースコードの変更予測手法を用いて，自動プログラム修正を高速化できるかどうかを確かめることである．そのため本実験では，実際の OSS の開発過程で発生した 106 個の欠陥に対して GenProg と提案手法を適用する．修正に用いるプログラム文をランダムに選択した場合と提案手法によって推薦されたプログラム文を用いた場合で修正時間の比較を行う．また，GenProg
は修正に用いるプログラム文だけでなく，修正箇所も欠陥限局された箇所の中からランダムに選択するため，修正時間のばらつきが大きい．同じ実験対象であっても実行のたびに修正時間やパッチが生成されるかどうかが異なるため，実験は各実験対象について 3 回行った．
実験は 2.40GHz Intel Xeon CPU(2 プロセッサ，計 16 コア)，メモリサイズ 128GB の計算機に Docker
コンテナを 7 個同時に立ち上げて行った．各コンテナには CPU コアを 2 つ，メモリを 18GB 割り当てた．タイムアウトは 3 時間とした．また，実験に用いるデータは全て SSD 上に配置した．

GenProg など，全てのテストケースを通過したかどうかで修正が成功したかを判断する自動プログ
ラム修正手法は，開発者の意図とは異なる修正パッチを出力する事があると知られている [41]．そのため GenProg，提案手法によって行われた修正が正しい修正であったかどうかについても調査する．
実験対象が多いため，正しい修正であったかどうかの調査は 1 回目の実行で出力されたパッチに対してのみ行う．修正が正しいかどうかは GenProg や提案手法が開発者が行った修正と同じ修正かど
うかにより判定する．正しい修正に関する情報は Defects4J[25] より修正前のリビジョンと修正後のリビジョンを取得し，差分を取ることにより得た．各修正パッチが正しいかどうかの判定は目視で行った．

7.1 実験対象
実験には Defects4J[25] を用いる．Defects4J とは，Java で記述された 5 つの OSS(jFreechart[26],Closure compiler[27], Apache Commons-Lang[28], Apache Commons-Math[29], Joda-time[30]) の開発過程で発生した 357 個の欠陥を収集したものである．本実験では Defects4J で収集された欠陥の内，Apache Commons-Math の 106 個の欠陥を実験対象とする．Defects4J の詳細を表 1 に示す．Defects4Jに収集されている欠陥は次の特徴を持つ．
表 1: Defects4J の詳細

プログラム

欠陥数

総行数 [LOC]

テスト数

JFreeChart

26

96,0002,205

Closure Compiler

133

90,0007,927

Commons Math106

85,0003,602

Joda-Time27

28,0004,130Commons Lang

65

22,0002,245

16• 課題管理システムで課題と関連付けられており，コミットメッセージで修正されたと述べられている• 修正が 1 つのコミットで完結している• Java のソースコードの変更により修正されている (設定ファイルやテストファイルに関する欠陥は含まない)• 修正前には失敗テストが存在し，修正後には全てのテストを通過する
7.2 実験条件の統一
GenProg は修正箇所や挿入候補の選択などにランダム値を用いているため，同じ欠陥の修正であっても実行時に乱数生成器に与えるシード値によって修正時間が大きく異なる．また同じシード値を乱数生成器に与えたとしても提案手法は挿入候補の選択にランダム値を用いないため，変異プログラ
ムを同じ数だけ生成したとしても，GenProg と提案手法で乱数を取得する回数は異なる．そのため各変異プログラムの修正箇所や適用する操作は異なってしまう．GenProg と提案手法をより厳密に比較するため，本実験では乱数生成器を修正箇所用とその他用に分けることにより，同じシード値を乱数生成器に与えて変異プログラムを同じ数だけ生成した場合に，同じ箇所に同じ操作が加わるよう実
装した．

7.3 実験結果
実験結果を図 8，図 9，図 10，図 11 に示す．図 8 の散布図に示されている実験結果は，106 個の欠陥に対する 3 回の実験のうち，提案手法を用いなかった場合と用いた場合でどちらも修正に成功した場合の実験結果を示している．グラフは対数スケールで表している．縦軸は提案手法の修正時間，
横軸は GenProg の修正時間を示している．修正時間の単位は秒であり，全てのテストケースを通過する変異プログラムが生成されるまでにかかった時間を示している．グラフ中の丸は１つの欠陥に対する修正時間を示している．青色の対角線上に丸があれば提案手法と GenProg の修正時間が等しい
ことを示し，青線よりも右側に丸がある場合は GenProg よりも提案手法のほうが早く修正を終えたことを示す．青線よりも左側に丸がある場合は，提案手法よりも GenProg のほうが早く修正を終えたことを示す．赤線は実験結果の回帰直線である．
図 8 から，GenProg において挿入候補を選択する際に提案手法が提案するプログラム文を用いた
場合に，修正時間に差がある 63 パターン中 29 パターンで提案手法を用いなかった場合よりも高速に修正を行った．このことから修正を早く終えたパターンの数で比較すると提案手法と GenProg はほぼ同数である．しかし，提案手法を用いない場合，用いた場合両方で修正に成功した欠陥に対する
平均修正時間を比較すると，提案手法を使わない場合は 1,379.7 秒，提案手法を用いた場合は 1,127.8

17

10000
提案手法

10000
GenProg

図 8: 実験結果

秒であり，提案手法によって平均修正時間を 18.3%削減した．図 8 の回帰直線に注目すると，修正時間が 700 秒以内では GenProg のほうが早く修正を終えるが，700 秒を超えてからは提案手法のほうが大幅に早く修正を終える傾向があることが分かる．このことから提案手法は特に GenProg が修正に時間がかかる対象の高速化に有用であると言える．
図 9，図 10，図 11 に，GenProg と提案手法の少なくともどちらか一方が修正に成功した場合の実験結果を示している．図 9，図 10，図 11 は順に 1 回目の実行結果，2 回目の実行結果，3 回目の実
行結果を示している．縦軸は修正時間，横軸は実験対象を示している．青色は GenProg の実験結果，
赤色は提案手法の実験結果を示している．各実験対象についている色はどちらの手法が早く修正を終えたかを示している．網状のマスクがかかった実験結果はタイムアウトした実験結果を示している．
図 9，図 10，図 11 において，一方のみが修正できた実験結果に着目すると，GenProg は 6 個，提案
手法は 11 個であり，提案手法は GenProg に比べて 5 個多くの欠陥の修正に成功した．

18

Math2
Math5
Math7
Math8
Math20Math22Math28Math31
Math32
Math40Math44
Math49Math50Math53
Math60Math64
Math70Math71
Math73
Math74
Math78
Math80Math81
Math82
Math84
Math85
Math95
Math103

修正時間[sec]

Math2
Math5
Math7
Math8
Math20Math22Math28Math31
Math40Math44
Math49Math50Math53
Math56
Math60Math70Math71
Math73
Math74
Math78
Math80Math81
Math82
Math84
Math85
Math95
Math103

修正時間[sec]
10000

9000

8000

7000

6000

5000

4000

3000

2000

1000

0

GenProg

GenProg
提案手法

図 9: 実験結果 (seed=0)

10000

9000

8000

7000

6000

5000

4000

3000

2000

1000

0

提案手法

図 10: 実験結果 (seed=1)19

100009000
8000

修正時間[sec]

7000

6000
5000
4000
3000
2000
1000

Math2
Math5
Math8
Math12Math20Math22Math24
Math28Math31
Math40Math44
Math49Math50Math53
Math56
Math60Math64
Math70Math71
Math73
Math78
Math80Math81
Math82
Math84
Math85
Math95
Math103

0

提案手法

GenProg

図 11: 実験結果 (seed=2)

表 2，表 3，表 4 に図 9，図 10，図 11 の詳細な実験結果を示す．提案手法は，推薦されたプログ
ラム文を用いて修正が完了しなかった場合に GenProg と同様，プログラム文をランダムに取得して修正に用いる．各表には修正時間の数値データに加え，5 列目に提案手法で行われた修正が提案手法によって推薦されたプログラム文かどうかを示している．Yes なら提案手法が推薦したプログラム文
によって全てのテストケースを通過するプログラムが生成され，修正に成功したことを示す．No なら，GenProg と同様にランダムに選択されたプログラム文により修正に成功したことを示す．–はどちらかが修正に成功しなかった，プログラム文の削除により修正に成功した，またはソースコードの変更予測の際に次の変更が大きいと予測された場合を示している．
全ての実験結果のうち，推薦されたプログラム文を用いて修正に成功した実験結果の修正時間に注目する．推薦されたプログラム文によって修正に成功した実験結果のうち提案手法のほうが早く修正を終えたものは 28 個，GenProg のほうが早く修正を終えたものは 14 個であり，66.7%の欠陥に対して提案手法手法が早く修正を終えた．また，修正時間がほぼ変わらない大きく変化した場合について考察するため，GenProg と提案手法の修正時間に 100 秒以上の差がある 23 個の実験結果について考える．それらの実験結果について，提案手法のほうが早く修正を終えたものは 18 個，GenProg の20

ほうが早く修正を終えたものは 5 個であり，提案手法が推薦したプログラム文によって修正を終えた
場合に，提案手法は 78.3%の欠陥に対して修正時間を大きく短縮するということが分かった．

GenProg を含めた，テストの通過状態を用いた現在の自動プログラム修正手法が行う修正は，全てのテストを通過するパッチを出力するが開発者が行う修正と意味的に等しいとは限らない [22]．本研
究では，GenProg，提案手法によって行われた修正が開発者が行った修正と意味的に等価かどうかについて調査した．調査は目視で行った．また，3 回行った実験のうち 1 回の実験結果について調査を行った．表 2 の 3 行目，6 行目の正しいパッチという項目は，GenProg，提案手法によって行われた修正が開発者が行った修正と等価かどうかを示している．調査の結果，Math-5 と Math-22 に対して
提案手法，GenProg 共に正しいパッチを生成できた事が分かった．
図 12 に提案手法と GenProg が Math-5 に対して生成したパッチを示す．Math-5 では図 12 の if 文
内で返す値が INF であった為に未通過テストが存在していた．提案手法，GenProg により if 文内から返す値を INF に変更するパッチが生成され，修正に成功した．また，パッチは開発者が作成したパッチと同じであった．
図 13 に提案手法と GenProg が Math-22 に対して作成したパッチを示す．Math-22 では図 13 のisSupportLowerBoundInclusive メソッドと isSupportUpperBoundInclusive メソッド内で返す boolean 値が間違っていた．そのためこの欠陥の修正には複数箇所の変更を正しく行う必要がある．提案手法，

GenProg は各メソッドから返す値を正しいプログラム文に変更するパッチが生成し修正に成功した．
但し提案手法，GenProg が生成したパッチは，プログラムの入出力としては開発者のものとは同じものの，Beta クラス内の logBeta メソッド内に不要な double 型の変数 m を追加していた．
上記した 2 つの例から，自動プログラム修正により全てのテストを通過するパッチを生成することができ，開発者が作成するパッチと等価なパッチを生成する事ができる事が分かる．

Math-5，Math-22 以外の欠陥に対して生成されたパッチは全て開発者が生成したパッチとは異なるパッチであった．全てのテストを通過するが必要な機能が削除されてしまっているパッチの例を 2 つ示す．図 14 に Math-53 に対して開発者が作成したパッチを示す．Math-53 で Complex クラスの add
メソッドにおいて，引数 rhs が NaN である場合の処理が不足しており，テストに失敗していた．開発者はこの欠陥に対して Complex クラスの add メソッド内にメソッドの引数 rhs が NaN かどうかをチェックする処理を記述した．対して，提案手法が作成したパッチでは，MathUtils.checkNotNull メ
ソッドの呼び出しを削除し，開発者と同様の処理を追加していた．その為，テストは通過するが，引数が Null のときに行うべき処理が削除されている．
図 15(a) に Math-31 に対して開発者が作成したパッチを，図 15(b) に GenProg が生成したパッチを示す．Math-31 では ContinuedFraction クラスの開発者が変更した 3 箇所に欠陥があり，テストケー
スの中の 1 つが ConvergenceException の例外を吐いて失敗していた．GenProg では開発者が変更した 3 箇所を変更するのではなく，テストが失敗した原因である ConvergenceException の throw 文を削除し，return 文で置き換えた．このように必要な機能を削除してテストを通過するパッチを生成する場合がある．

21

GenProg が上記したパッチを生成することは Long らが報告している内容と一致する [22]．一方で，
Le らは自動プログラム修正手法によって生成されたパッチを並び替え，開発者によって生成されたパッチである可能性が高いパッチを生成する手法を提案している [24]．本研究で提案した手法を用いてより多くのパッチを生成し，HDRepair[24] と組み合わせる事により，より多くの実験対象に対して，より早く開発者が作成するパッチと等価なパッチを生成できるようになると考える．

22

表 2: 実験結果 (seed=0)

修正対象

提案手法

GenProg

差 [sec]

修正時間 [sec]

正しいパッチ

修正時間 [sec]推薦された文正しいパッチMath-2

196

No

1,350

No

No

1,154

Math-5

268

Yes

325

Yes

Yes

57

Math-7

4,588

No

2,463

Yes

No

-2,125Math-8

218

No

218

No

No

0

Math-20

1,628

No

3,082

–

No

1,454

Math-22

412

Yes

298

Yes

Yes

-114

Math-28

152

No

174

Yes

No

22

Math-31

8,374

No

666

Yes

No

-7,708Math-40

5,286

No

596

No

No

-4,690Math-44

2,976

No

351

Yes

No

-2,625Math-49

432

No

62

Yes

No

-370

Math-50

77

No

41

Yes

No

-36

Math-53

28

No

153

No

No

125

Math-56

–

No

8,091

Yes

No

–

Math-60

3,225

No

2,996

Yes

No

-229

Math-70

175

No

110

Yes

No

-65

Math-71

5,003

No

7,956

–

No

2,953

Math-73

21

No

403

No

No

382

Math-74

7,962

No

–

–

No

–

Math-78

–

No

307

Yes

No

–

Math-80

141

No

146

-

No

5

Math-81

735

No

302

-

No

-433

Math-82

376

No

534

No

No

158

Math-84

3,407

No

267

No

No

-3,140Math-85

25

No

23

Yes

No

-2

Math-95

719

No

619

Yes

No

-100

Math-103

–

No

1,767

No

No

–

1,672.3–

1,005.9–-666.4

平均23

表 3: 実験結果 (seed=1)

修正対象

提案手法

GenProg
修正時間 [sec]修正時間 [sec]推薦された文差 [sec]Math-2

4,845

5,854

No

1,009

Math-5

–

249

Yes

–

Math-7

–

1,244

Yes

–

Math-8

246

267

No

21

Math-20

3,018

1,758

No

-1,260Math-22

712

1,091

Yes

379

Math-28

229

299

Yes

70

Math-31

–

265

Yes

–

Math-32

–

9,688

Yes

–

Math-40

368

1,811

Yes

1,443

Math-44

413

137

Yes

-276

Math-49

199

172

Yes

-27

Math-50

47

5

Yes

-42

Math-53

45

293

No

248

Math-60

1,158

1,936

No

778

Math-64

6,295

–

–

–

Math-70

91

147

Yes

56

Math-71

6,239

–

–

–

Math-73

135

423

No

288

Math-74

3,511

4,720

No

1,209

Math-78

11

21

Yes

10

Math-80

270

1,912

No

1,642

Math-81

5

5

-

0

Math-82

1,182

1,384

No

202

Math-84

5,151

3,033

No

-2,118Math-85

94

110

No

16

Math-95

82

309

Yes

227

Math-103

–

964

Yes

–

1,038.7

1,223.2

–

184.5

平均

24

表 4: 実験結果 (seed=2)

修正対象

提案手法

GenProg
修正時間 [sec]修正時間 [sec]推薦された文差 [sec]Math-2

578

2,924

No

2,346

Math-5

348

516

Yes

168

Math-8

276

280

Yes

4

Math-12

8,066

–

–

–

Math-20

996

288

No

-708

Math-22

1,016

624

Yes

-392

Math-24

609

–

-

–

Math-28

110

128

No

18

Math-31

–

701

Yes

–

Math-40

312

3,994

Yes

3,682

Math-44

7,578

352

Yes

-7,226Math-49

80

68

Yes

-12

Math-50

50

5

No

-45

Math-53

23

108

No

85

Math-56

–

9,218

Yes

–

Math-60

2,166

2,282

Yes

116

Math-64

7,831

–

–

–

Math-70

64

52

Yes

-12

Math-71

4,437

1,970

No

-2,467Math-73

23

537

No

514

Math-78

74

56

Yes

-18

Math-80

129

182

No

53

Math-81

443

648

Yes

205

Math-82

873

834

Yes

-39

Math-84

9,263

4,578

No

-4,685Math-85

88

101

Yes

13

Math-95

482

415

Yes

-67

Math-103

–

3,541

No

–

1,278.7

1,064.5–-214.2

平均25

図 12: 開発者と等価な修正パッチの例 (Math-5)

図 13: 開発者と等価な修正パッチの例 (Math-22)

図 14: 全てのテストケースは通過するが正しくないパッチの例 (Math-53)

26

(a) 開発者のパッチ(b) 提案手法が生成したパッチ
図 15: 全てのテストケースを通過するが正しくないパッチの例 (Math-31)

27

8 妥当性の脅威
実験対象
本研究では提案手法を Java で記述された OSS の開発過程で発生した 106 個の欠陥に対して適用した．他の実験対象や Java 以外の言語で書かれたプログラムを修正対象とした場合に異なった結果が得られる可能性がある．
欠陥修正コミット提案手法で欠陥修正コミットを特定する際に欠陥の修正に関連した bug や fix ， bugfixなどのキーワードを含むコミット全てを欠陥修正コミットとした．そのためキーワードを含むが実際には欠陥修正コミットではないコミットを欠陥修正コミットとして扱っている可能性がある．

jGenProg における抽象構文木
jGenProg では修正対象プログラムの抽象構文木を Eclipse JDT[36] ではなく独自の形式で扱っている．jGenProg における抽象構文木では，プログラム要素を約 40 種類しか定義していない．
提案手法は EclipseJDT を用いているため予測の精度に影響は考えにくいが，予測結果を用いたプログラム文の絞り込みの際により多くプログラム文が推薦されてしまっている可能性がある．JDT を用いて jGenProg を再実装した場合に異なった結果が得られる可能性がある．
機械学習ライブラリ
本研究では，Weka のライブラリを用いて学習モデルを構築している．Weka は学習モデルを構築する際に様々なオプションを設定する事ができる．本研究では，デフォルト設定のまま学習モデルを構築した．異なったオプションや他の機械学習ライブラリを用いた場合に本研究で得られた結果と異なる結果が得られる可能性がある．

28

9 まとめと今後の課題
本研究では，ソースコードの再利用に基づく自動プログラム修正手法を高速化するため，ソース
コードの変更予測手法を用いた自動プログラム修正の高速化手法を提案した．既存のソースコードの再利用に基づく自動プログラム修正手法は欠陥箇所を変更するプログラム文を修正対象のソース
コードからランダムに選択する．プログラム文は修正対象中に大量に存在するためこれは非効率である．そこで提案手法では，ソースコードの変更予測を用いて次に追加されるプログラム要素を特定し，そのプログラム要素を持つプログラム文を修正に用いる．実際の OSS 開発で発生した欠陥に対して提案手法と既存手法を適用した結果から，提案手法は平均修正時間を約 20%短縮できていることを確認した．また，どちらか一方のみによって修正された 17 個の欠陥に着目すると，11 個が提案手法によって，6 個が GenProg によって修正されており，提案手法は GenProg よりも 5 つ多くの欠陥を修正した．
今後の課題は以下の通りである．

• 異なるプログラムの開発過程で発生した欠陥に対して実験を行う• 機械学習ライブラリの設定を変更して実験を行う• jGenProg の抽象構文木構築部分を EclipseJDT に変更して実験を行う• 提案手法が GenProg よりも早く修正に成功した欠陥は小さい変更によって修正可能であったのかどうかの調査29謝辞
本研究を行うにあたり，理解あるご指導を賜り，常に励まして頂きました楠本真二教授に心から感謝申し上げます.
本研究の全過程を通し，終始熱心かつ丁寧なご指導を頂きました肥後芳樹助教に深く感謝申し上げます．
本研究に関して，有益かつ的確なご助言を頂きました柗本 真佑助教授に深く感謝申し上げます．
その他，楠本研究室の皆様のご助言，ご協力に心より感謝致します．
最後に，本研究に至るまでに, 講義などでお世話になりましたコンピュータサイエンス専攻の諸先
生方に，この場を借りて心から御礼申し上げます．

30

参考文献
[1] Tom Britton, Lisa Jeng, Graham Carver, Paul Cheak and Tomer Katzenellenbogen, "Reversible Debugging Software - Quantify the time and cost saved using reversible debuggers," 2013. Universityof Cambridge, http://docplayer.net/11413249-Reversible-debugging-software-quantify-the-time-andcost-saved-using-reversible-debuggers.html, Accessed 2017-01-04.
[2] CVS - Concurrent Versions System, http://www.nongnu.org/cvs/.
[3] Apache subversion, http://subversion.apache.org/.
[4] Git. http://git-scm.com.
[5] Saha, D., Nanda, G. M., Dhoolia, P., Nandivada,V. K., Sinha, V. and Chandra, S. "Fault localization for data-centric programs," In Proceedings of the 19th ACM SIGSOFT International Symposium on Foundations of Software Engineering, pp.157–167. Szeged, Hungary, September 2011.
http://dl.acm.org/citation.cfm?id=2025137[6] Zuddas, D., Jin, W. and Pastore, F. "MIMIC : Locating and Understanding Bugs by Analyzing Mimicked Executions," In proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering, pp.815–826, Hong Kong, November 2014.
http://dl.acm.org/citation.cfm?id=2643014[7] J. Jones and M. Harrold,nique,

Empirical evaluation of the tarantula automatic fault-localization tech-

In Proceedings of the 20th IEEE/ACM international Conference on Automated software

engineering, pp.273–282, November 2005. http://dl.acm.org/citation.cfm?id=1101949[8] R. Abreu, P. Zoeteweij, R. Golsteijn, and A. van Gemund,of spectrum-based fault localization,

A practical evaluation

Journal of Systems and Software, November 2009.

http://dl.acm.org/citation.cfm?id=1630274[9] X. Xie, T. Y. Chen, F. Kuo and B. Xu, "A theoretical analysis of the risk evaluation formulas forspectrum-based fault localization" Journal of ACM Transactions on Software Engineerng and Methodology, volume 22, issue 4, October 2013. http://dl.acm.org/citation.cfm?id=2522924[10] T. B. Le, F. Thung and D. Lo, "Theory and Practice, Do They Match?

A Case with

Spectrum-Based Fault Localization," In Proceedings of the 29th IEEE International Conference on Software Maintenance, pp.380–383, Netherlands, Eindhoven, September 2013.
http://ieeexplore.ieee.org/document/6676912/

31

[11] C. Le Goues, M. Dewey-Vogt, S. Forrest, and W. Weimer, "A Systematic Study of Automated Program Repair: Fixing 55 out of 105 Bugs for $8 Each," In Proceedings of the 34th International
Conference on Software Engineering, pp3–13, Zurich, Switzerland, June 2012. http://dl.acm.org/
citation.cfm?id=2337223.2337225[12] Y. Qi, X. Mao, Y. Lei, Z. Dai, and C. Wang, "The Strength of Random Search on Automated Program
Repair," In Proceedings of the 36th International Conference on Software Engineering, pp.254–265,
Hyderabad, India, May 2014. http://doi.acm.org/10.1145/2568225.2568254[13] H. D. T. Nguyen, D. Qi, A. Roychoudhury, and S. Chandra, "SemFix: Program Repair via Semantic
Analysis," In Proceedings of the 35th International Conference on Software Engineering, pp.802–811,
San Francisco, CA, USA, May 2013. http://dl.acm.org/citation.cfm?id=2486788.2486890[14] J. Xuan, M. Martinez, F. DeMarco, M. Clement, S. L. Marcote, T. Durieux D. Le Berreand M. Monperrus, "Nopol: Automatic Repair of Conditional Statement Bugs in Java Programs", In IEEE Transactions on Software Engineering, Volume 43, Issue 1, Janually 2017.
http://ieeexplore.ieee.org/document/7463060/authors?ctx=authors[15] L. De. Moura and N. Børner, "Z3: An efficient smt solver," In Proceedings of the Theory andpractice of software, 14th international conference on Tools and algorithms for the construction
and analysis of systems, pp337–340, Budapest, Hungary, March 2008. http://dl.acm.org/citation.
cfm?id=1792734.1792766[16] S. Mechtaev. J. Yi and A. Roychoudhury. "DirectFix: Looking for Simple Program Repairs," In Proceedings of the 37th International Conference on Software Engineering, pp.448–458, Florence, Italy,
May 2015. http://dl.acm.org/citation.cfm?id=2818811[17] D. Kim, J. Nam, J. Song, and S. Kim, "Automatic patch generation learned from human-written
patches," In Proceedings of the 35th International Conference on Software Engineering, pp.772–781,
San Francisco, CA, USA, May 2013. http://dl.acm.org/citation.cfm?id=2486893[18] H. Liu, Y. Chen and S. Lu, "Understanding and generating high quality patches for concurrency bugs,"
In Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering, Seattle, WA, USA, November 2016. http://dl.acm.org/citation.cfm?id=2950309[19] S. H. Tan, H. Yoshida, M. R. Prasad and A. Roychoudhury, "Anti-patterns in Search-Based
Program Repair," In Proceedings of the 2016 24th ACM SIGSOFT International Symposium
on Foundations of Software Engineering, pp.727-738, Seattle, WA, USA, November 2016.
http://dl.acm.org/citation.cfm?id=2950295

32

[20] W. Weimer, Z. P. Fry and S. Forrest, "Leveraging program equivalence for adaptive program
repair: Models and first results," In Proceedings of the IEEE/ACM 28th Internatioanl Conference on Automated Software Engineering, pp.103–113, SiliconValley，California, November 2013.
http://ieeexplore.ieee.org/document/6693094/[21] Z. Qi, F. Long, S. Achour and M. Rinard, "An analysis of patch plausibility and correctness for generate-and-validate patch generation systems," In Proceedings of the 2015 International Symposium on Software Testing and Analysis pp.24–36, Baltimore, Maryland, July 2015.
http://dl.acm.org/citation.cfm?id=2771791[22] F. Long and M. Rinard, "An analysis of the search spaces for generate and avalidate patch generation
systems," In Proceedings of the 38th International Conference on Software Engineering, pp.702–713,
Austin, Texas, May 2016. http://dl.acm.org/citation.cfm?id=2884872[23] Y. Xiong, J. Wang, R. Yan, J. Zhang, S. Han, G. Huang and L. Zhang, "Precise Condition Synthesis
for Program Repair," In Proceedings of the 39th International Conference on Software Engineering,
Buenos Aires, Argentina, May 2017. https://arxiv.org/abs/1608.07754[24] X. D. Le, D. Lo and C. Le Goues, "History Driven Program Repair," In proceedings of the IEEE 23rd
international Conference on Software Analysis, Evolution, and Reengineering, Osaka, Japan, March2016. http://ieeexplore.ieee.org/document/7476644/[25] R. Just , D. Jalali and M. D. Ernst, "Defects4J: A Database of existing faults to enable controlled testingstudies for Java programs," In Proceedings of the 36th International Symposium on Software Testingand Analysis, pp.437–440, San Jose, CA, USA, July 2014. http://dl.acm.org/citation.cfm?id=2628055[26] JFreeChart, http://www.jfree.org/jfreechart/[27] Closure Compiler, https://developers.google.com/closure/compiler/[28] Apache Commons Lang, https://commons.apache.org/proper/commons-lang/[29] Apache Commons Math, https://commons.apache.org/proper/commons-math/[30] Joda-time, http://www.joda.org/joda-time/[31] H. Murakami, K. Hotta, Y. Higo and S. Kusumoto, "Predicting Next Changes at the Fine-Grained
Level," In Proceedings of the 21st Asia-Pacific Software Engineering Conference, pp.126–133, Jeju,
Korea, December 2014. http://sdl.ist.osaka-u.ac.jp/pman/pman3.cgi?DOWNLOAD=273[32] The R project for statistical computing, https://www.r-project.org/[33] Weka 3:Data Mining Software in Java, http://www.cs.waikato.ac.nz/ml/weka/33[34] D. W. AHA, D. Kibler and M. K. Albert,"Instance-Based Learning Algorithms,"

https://pdfs.semanticscholar.org/395b/2e9bd23e56394b61b8deab2e0cbc9718f7fd.pdf[35] H. Akaike, "A new look at the statistical model identification", IEEE Transactions on AutomaticControl, pp.716–723, http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=1100705[36] Eclipse Java development tools, http://www.eclipse.org/jdt/[37] Eclipse JGit, https://eclipse.org/jgit/[38] F. Long and M. Rinard, "Automatic Patch Generation by Learning Correct Code," In Proceedings ofthe 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages,
pp.298–312, St. Petersburg, FL, USA, January. 2016. http://dl.acm.org/citation.cfm?id=2837617[39] S. Mechtaev, J. Yi and A. Roychoudhury, "Angelix: Scalable Multiline Program Patch Synthesis via
Symbolic Analysis,"In Proceedings of the 38th International Conference on Software Engineering,
pp.691–701, Austin, Texas, May 2016. http://dl.acm.org/citation.cfm?id=2884807[40] F. Long and M. Rinard, "Staged Program Repair with Condition Synthesis," In Proceedings of the10th Joint Meeting on Foundations of Software Engineering, pp.166–178, Bergamo, Italy, August
2015. http://dl.acm.org/citation.cfm?id=2786811[41] Z. Qi, F. Long, S. Achour and M. Rinard, "An Analysis of Patch Plausibility and Correctness for Generate-and-validate Patch Generation Systems," In Proceedings of the 18th International Symposium on Software Testing and Analysis, pp.24–36, Baltimore, MD, USA, July 2015.
http://dl.acm.org/citation.cfm?id=2771791 .
[42] M. Martinez and M. Monperrus, "ASTOR: A Program Repair Library for Java," In Proceedings ofthe 25th International Symposium on Software Testing and Analysis, SaarbrÃijcken, Germany, July
2016. http://dl.acm.org/citation.cfm?id=2948705

34