社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,
INFORMATION AND COMMUNICATION ENGINEERS

信学技報
TECHNICAL REPORT OF IEICE.

自動テスト生成を利用した自動プログラム修正出力パッチ分類の試み
藤本 章良†

肥後 芳樹†

柗本

真佑†

楠本

真二†

安田 和矢††† 大阪大学大学院情報科学研究科〒 565-0871 大阪府吹田市山田丘 1-5†† (株) 日立製作所 研究開発グループ 社会システムイノベーションセンタ
〒 244-0817 神奈川県横浜市戸塚区吉田町 292 番地
E-mail: †{a-fujimt,higo,shinsuke,kusumoto}@ist.osaka-u.ac.jp, ††kazuya.yasuda.fd@hitachi.com
あらましソフトウェア開発において効率的なデバッグを行うため，自動でプログラムを修正するツールが数多く提案されている．自動プログラム修正ツールは，バグを含むプログラムとテストスイートを与えると，そのテストスイート
を通過するようにプログラムを修正したパッチを出力する．しかし，与えられたテストスイートに過剰に適合した結果，完全にバグを修正しきれていない状態のパッチが出力される場合が多く，開発者によるパッチの確認が必要である．また自動プログラム修正ツールは，修正候補として複数のパッチを出力する場合があり，パッチ数が多い場合はそれらの確認に多大なコストを要する．そこで本研究では，パッチの確認コスト削減を目的とし，自動テスト生成技術を利用して，パッチを振る舞いごとにグループ化する手法を提案する．振る舞いが同じパッチのグループの中から 1 つのパッチを選択し確認することで，そのグループに含まれるパッチ全ての正誤を判断でき，目視によるパッチの確認回数を削減可能である．提案手法では，各パッチに対して自動テスト生成を行い，パッチと生成したテストを相互に実行し，この結果を用いて分類を行う．本稿では，提案手法の評価のため 1) 確認すべきパッチ数の削減割合，2) 正誤の異なるパッチの別グループへの分離可能性について調査を行なった．その結果，提案手法は確認すべきパッチ数を平均で 90%削減し，調査対象とした 41 個の題材のうち，26 個で分離に成功した．
キーワード

自動プログラム修正，パッチ評価，自動テスト生成

1. ま え が きも，必ずしもデバッグ作業を効率化できるとはいえない．
真にデバッグを効率化するには，オーバーフィットなパッチ

自動プログラム修正（Automated Program Repair: APR）とを生成しないこと，APR ツールが出力するパッチの確認コスト

は，バグを含むプログラムから自動的にバグを取り除く技術であを削減することの 2 通りの方法が考えられる．しかし現時点でる．ソフトウェア開発に必要なコストのうち，半分以上をデバッ

は，APR ツールが出力するパッチの大半をオーバーフィットなグ作業が占めているという報告もある [1] [2]．APR ツールの利パッチが占めており [6] [7]，オーバーフィットのない APR ツー

用によって，こうしたデバッグ作業を効率化する試みがなされてルの実現はまだまだ難しい．

いる．現在，様々な APR ツールが提案されている [3] [4]．これ

そこで本研究では，パッチ確認コストの削減を目的とし，APRらのうちテストベースの APR ツールは入力としてバグを含むプ

ツールが出力したパッチを振る舞いごとにグループ化する手法

ログラムの他にテストスイートを必要とする．入力するテストを提案する．振る舞いが同じパッチのグループから 1 つのパッ

スイートをそのプログラムが満たすべき仕様とし，APR ツール

チを選択し確認することで，そのグループに属する他の全てのはそのテストスイートを通過するようにプログラムを修正したパッチが正しいか否かについても同時に判断でき，確認すべき

パッチを出力する．

パッチの個数を削減できる．提案手法ではパッチのグループ化

これらの APR ツールは，入力するテストスイートに過剰に適に自動テスト生成技術を用いる．自動テスト生成技術は，与えた合した結果，全てのテストケースに通過するものの，完全にバグプログラムの振る舞いからテストを生成するため，生成されたテを修正しきれていない状態であるオーバーフィットなパッチをストに他のパッチが通過可能かどうかで振る舞いの一致を判断出力する場合が多い [5] [6]．したがって，APR ツールの利用者できると著者らは考えた．全てのパッチからテストを自動生成

は，出力されたパッチが真に正しいかを目視で確認する必要がし，パッチと生成テストの全ての組を相互に実行する．この結果ある．しかしながら，APR ツールが大量のパッチを出力する場を用いて，パッチのグループ化を行う．

合，あるいは複数の APR ツールを同時に利用する場合に確認す

本稿では，Defects4J Math プロジェクトのバグに APR ツー

べきパッチの数が非常に多くなり，全てのパッチを確認するため

ルを適用して得られたパッチに対して提案手法を適用し，1) 確認に多大なコストが生じる．そのため APR ツールを用いたとしてすべきパッチ数の削減割合，2) 正誤の異なるパッチの別グルー—1—

プへの分離可能性 の 2 点について評価実験を行なった．その結されたグループ化の結果を目視で確認したところ，半数以上の題

public Complex add(Complex rhs)
throws NullArgumentException {MathUtils.checkNotNull(rhs);+ if (isNaN || rhs.isNaN) {+return NaN;
+ }return createComplex(real + rhs.getReal(),imaginary + rhs.getImaginary());

public Complex add(Complex rhs)
throws NullArgumentException {+ if (isNaN || rhs.isNaN) {+return NaN;
+ }MathUtils.checkNotNull(rhs);
return createComplex(real + rhs.getReal(),imaginary + rhs.getImaginary());

材において，正誤の異なるパッチを別のグループに分離すること(a) 正しい修正パッチ(b) オーバーフィットなパッチ 1

果，提案手法により確認すべきパッチの数が，平均で 84%，中央値で 90%削減可能であることが明らかになった．また，出力ができた．

2. 背景と関連研究
2. 1 自動テスト生成
自動テスト生成とは，与えたプログラムに対してその振る舞い
を最大限網羅できるような入力値を持つテストを生成する技術

public Complex add(Complex rhs)
throws NullArgumentException {- MathUtils.checkNotNull(rhs);+ if (isNaN || rhs.isNaN) {+return NaN;
+ }return createComplex(real + rhs.getReal(),imaginary + rhs.getImaginary());(c) オーバーフィットなパッチ 2(d) オーバーフィットなパッチ 3である．現在多くの自動テスト生成技術が研究されており，ランダムな入力からテストを生成する Randoop [8] や遺伝的アルゴ

public Complex add(Complex rhs)
throws NullArgumentException {MathUtils.checkNotNull(rhs);
if (isNaN || rhs.isNaN) {return NaN;}
MathUtils.checkNotNull(rhs);
if (isNaN) {return NaN;}
return createComplex(real + rhs.getReal(),imaginary + rhs.getImaginary());

+
+
+
+
+
+
+

図 1 Math 53 のバグに対し APR が出力したパッチ

リズムを用いる EvoSuite [9] など様々な手法が提案されている．

2. 2 自動プログラム修正（APR）

敗するパッチをオーバーフィットと判断する．Ye らは，OSS で

自動プログラム修正とは，バグを含むプログラムから自動で発生したバグに対して APR が出力したパッチの成否を，RGT

バグを取り除く技術である．言い換えれば，一部の仕様を満たしを用いて分類した [13]．DiﬀTGen [14] は，バグを含むプログラていないプログラムに対して，APR は全ての仕様を満たすよう

ムからテストケースを生成し，パッチの適用前後で結果が異なるにプログラムの振る舞いを変更する．APR はソースコードを改

テストケースを得る．正解パッチと生成パッチのテスト実行結果

変しプログラムの振る舞いを変更する Behavioral repair と，実が異なれば，そのパッチをオーバーフィットであると判断する．

行中のプログラムに変更を加える State repair の 2 種類に大別

3. 研 究 動 機

される [4]．例えば前者は，バグを含むプログラムとともにテス
トスイートやステートマシンを仕様として与えると，これらを先行研究 [15] において，Defects4J データセット [16] に含ま満たすように変更を加えたプログラムをパッチとして出力する．

れるバグ（Math 53）に対して複数の APR ツールを適用したと

本研究では特に，テストスイートを仕様として利用する APR をころ，複数のパッチが得られた．出力されたパッチには，正し想定する．

いパッチとオーバーフィットなパッチの両方が含まれる．一部

2. 3 オーバーフィットなパッチのパッチを図 1 に示す．図 1(a) は，実際に行われた修正と一APR が出力するパッチの中で，与えた仕様に過剰に適合し完致する正解のパッチであり，図 1(b)(c)(d) はオーバーフィット

全にバグを修正しきれていない，または別のバグが混入したパッなパッチである．オーバーフィットなパッチは引数 rhs の null

チをオーバーフィットなパッチと呼ぶ．テストベースの APR のチェックを行う前に rhs を参照しているため，引数に null を与場合，オーバーフィットなパッチは与えたテストスイートは全てえると例外が発生する．同様に null を与えると例外が発生する

通過するが，十分に一般化ができていない状態である [5]．オー

パッチが複数確認された．これらのパッチは “引数に null を与バーフィットなパッチの存在は APR において大きな問題とされえると例外が発生する” 振る舞いを持つパッチであるといえる．

ている．オーバーフィットなパッチは，APR が出力するパッチ

このような同様の振る舞いを持つパッチをひとつのグループとの大多数を占めており [6] [7]，バグが修正されるよりもオーバー

して利用者に提示することで，確認すべきパッチの数を削減でき

フィットによって既存の正しい機能が破壊される場合が多いこる．すなわち，あるグループに属するパッチが “引数に null をと [10] が調査によって明らかになっている．

与えると例外が発生する” オーバーフィットなパッチであること

2. 4 APR 生成パッチ評価が分かれば，そのグループの他のパッチも同様にオーバーフィッ

APR 利用者の負担を軽減するため，本研究以外にも APR 出トであることがわかるため，他のパッチは確認する必要がなくな

力パッチの評価に関する研究が存在する．特に個々のパッチがる．出力された大量のパッチをいくつかの少数のグループに分

オーバーフィットかを評価する研究が広く行われている [11]．そ

割できれば，利用者の確認コストは大幅に削減可能である．

れらの研究は，正解パッチの利用の有無で 2 つに分けられる．

4. 提 案 手 法

正解パッチを用いない手法として，Xiong らはバグを含むプ
ログラムから自動テスト生成技術を用いてテストスイートを生本研究の目的は，APR が出力するパッチの確認に必要なコス成し，パッチの正誤を分類した [12]．各パッチに生成したテスト

トの削減である．本研究では，振る舞いが同じパッチをグループを適用し，バグを含む状態のプログラムとの実行時の振る舞いの化する手法を提案する．各グループから 1 つのパッチを選択し確

類似度，およびテストの実行経路を利用する．

認することで，確認すべきパッチの数を削減することを目指す．

正解パッチを利用する手法には，RGT（Random testing in

提案手法の概要を図 2 に示す．提案手法への入力は APR がGround Truth）を用いたパッチ評価手法がある．RGT とは，正出力したパッチであり，出力はグループ化されたパッチである．

解パッチから自動生成されたテストスイートであり，RGT に失グループ化のプロセスは以下の 3 つのステップで構成される．

—2—

ステップ1

ステップ2

テスト生成

入力

ステップ3

相互実行

グループ化

APR出力パッチ[OK, OK, Fail, … ]出力

グループ化パッチ[OK, OK, Fail, … ][Fail, OK, Fail, … ]

図2

t1

t2

t3

t4

t2

t1

t3

提案手法の概要

t4

ら生成したテスト tk ，tl を互いに通過すれば，パッチ pk および

p1

OK

OK

Fail

OK

pl は同じ振る舞いを持つパッチであるとみなせる．一方，パッ

p2

OK

OK

Fail

OK

チ pk がテスト tl に失敗，またはパッチ pl がテスト tk に失敗し

Fail

p3

Fail

Fail

OK

Fail

た場合，pk と pl は異なる振る舞いを持つパッチであると判定す

OK

p4

OK

Fail

Fail

OK

p1

OK

OK

Fail

OK

p2

OK

OK

Fail

OK

p3

Fail

Fail

OK

p4

OK

Fail

Fail

行ベクトルでグループ化

る．パッチの振る舞いが異なる場合でも，必ずしも互いに失敗するテストが生成される訳ではないため，どちらか一方のみが失敗

図3

パッチの相互実行とグループ化

した場合でも振る舞いが異なるパッチとして扱う．
グループ化には，パッチ pk とテストスイート t1 , ..., tn の成否ステップ 1 各パッチからテストスイート生成を用いる．pk と各テストの成否は，要素数 n で通過または失敗

ステップ 2 パッチと生成テストスイートの相互実行の 2 値を持つベクトルであるとみなすことができ，相互実行結果

ステップ 3 パッチのグループ化の行に対応する．このベクトルは，pk がどのような特徴を持つ

以降では，各ステップについて説明する．

かを示すベクトルと見ることができる．すなわちベクトルの各ステップ 1：各パッチからテストスイート生成

要素について，テストスイート tj がある振る舞いの特徴を表し

入力として与えられたパッチ p1 , ..., pn をそれぞれ修正前のプており，pk が tj に通過した場合その特徴を持ち，失敗した場合ログラムに対して適用し，全てのパッチ適用済みプログラム（以はその特徴を持たない．pk と pl のテスト実行結果のベクトルが降では，パッチ適用済みプログラムを単にパッチと呼ぶ）から自完全に一致する場合，pk と pl は同じ振る舞いの特徴を持つパッ動テスト生成技術を用いてテストスイートを生成する．生成さチであると判定する．pk が tk に通過するため，pk と pl のベク

れたテストスイートをそれぞれ t1 , ..., tn とする．

トルが完全一致すれば pk と pl が互いのテストに通過すること

次に，生成された各テストスイートに対して ﬂaky test を含が保証される．最終的にベクトルが一致するパッチの組を全てむかどうかチェックする．ﬂaky test とは，同じプログラムであ探し，グループ化したパッチとして結果を出力する．図 3 の例

るにも関わらず，実行するたびにテストの成否が変化するテス

では p1 と p2 の行ベクトルが一致し，これらは同じグループにトである．ﬂaky test は開発に悪影響を与えるテストであること分類される．一方 p3 と p4 のベクトルはそれぞれ異なっており，が知られており [17]，本手法の有効性が低下する可能性があるた

出力されるグループ数は 3 となる．

め，相互実行するテストから取り除く．pi が ti に含まれるテス
トケースに失敗した場合，そのテストケースを ﬂaky test であると判断する．各パッチは自身から生成した全てのテストケースに通過するはずであるが，失敗するのは実行ごとの成否の変化が原因と考えられるためである．

5. Research Questions
提案手法の評価を行うにあたり，以下 3 つの Research Question（RQ）を設定した．

RQ1: 提案手法により確認すべきパッチ数はどの程度減少すステップ 2：生成テストとパッチの相互実行

るか？

ステップ 1 で自動生成したテストと APR が出力したパッチ入力として与えたパッチ数と，出力されるパッチのグループ

を全ての組み合わせで相互に実行し，結果を記録する．最終的に数の関係について調査する．入力パッチ数と出力グループ数が

図 3 左のように，パッチと自動生成テストの実行結果が記録さ同じであれば，パッチの確認コストは削減されない．提案手法

れる．図中の “OK” は ti に含まれるテストケースを全て通過，がパッチをある一定程度のグループ数に分割できる能力を持ち，“Fail” は 1 つ以上のテストケースに失敗したことを表す．

確認コストを削減可能であることを示すため，パッチ数に対してステップ 3：パッチのグループ化
ステップ 2 で得た相互実行の結果からパッチのグループ分け

どの程度のグループ数になるかを調査する．

RQ2: 提案手法は正解・オーバーフィットなパッチをそれぞを行う．自動テスト生成技術を用いて得られるテストは，与えたれ別のグループに分離できるか？

プログラムの振る舞いをテストスイートとして規定していると提案手法を利用してパッチを確認する場合，各グループから捉えることができる．したがって，パッチ pk ，pl がそれぞれか代表パッチを 1 つ選びそのパッチのみ確認を行う．そのためグ—3—

ループ全体が正解かどうかを判定するためには，各グループを構が必要である．この RQ では提案手法の有効性を示すため，出力された各グループが全て正解またはオーバーフィットなパッ
チのみから構成されているかを目視で調査する．

削減率(%)

成する全てのパッチが正解またはオーバーフィットであること

RQ3: 正誤の異なるパッチ分類に影響を与える特徴はあるか？

M
at
h
M -2
at
h
M -5
a
M th-8
at
h
M -22
at
h
M -50
at
h
M -53
at
h
M -70
at
h
M -71
at
h
M -73
at
h
M -82
at
h
M -85
at
h
M -95
at
h
M -98
at
h
M -28
at
h
M -31
at
h
M -39
at
h
M -49
at
h
M -58
a
M th-8at 4
h10
3

バグの種類や修正方法，修正対象のプログラムのメトリクスと

100
90
80
70
60
50
40
30
20
10
0

いった特徴が，グループ化に影響を与えるかどうかを調査する．

正誤の異なるパッチの分離に成功

特に，正解パッチの分離可能性との関連性について分析する．

正誤の異なるパッチの分離に失敗

図 4 題材ごとの確認すべきパッチの削減率

6. 評 価 実 験700600

実験対象は Defects4J [16] の Math プロジェクトに含まれるバ500

グである．APR ツールが出力したパッチとして，Durieux らの（注 1）

先行研究 [15] の過程で生成したパッチのデータセット

を利用

パッチ数

6. 1 実 験 対 象

400
300
200

て生成されたパッチが収録されており，1 つのバグに対して複数100のパッチが生成されたケースも含まれている．本評価実験では，

0Defects4J Math プロジェクトにおいて，いずれかの APR ツー
ルで 1 つ以上の修正パッチが生成されたバグを題材とした．タ
イムアウトにより EvoSuite でテストを生成できなかった Math

M
at
h
M -2
at
h
M -5
at
M h-8
at
h
M -22
at
h
M -50
at
h
M -53
at
h
M -70
at
h
M -71
at
h
M -73
at
h
M -82
at
h
M -85
at
h
M -95
at
h
M -98
at
h
M -28
at
h
M -31
at
h
M -39
at
h
M -49
at
h
M -58
at
M h-8
at 4
h10
3

した．このデータセットには，11 種類の APR ツールを適用し正誤の異なるパッチの分離に成功

正誤の異なるパッチの分離に失敗

図 5 グループの分割状況

80, 81 は除外した．対象の題材は合計で 41 個である．
また各題材について，正解パッチとして人の手によって行われた実際の修正パッチも加えて実験を行なった．これは，APRが出力するパッチに正解が含まれていない場合が往々にして存在するためである．正解パッチを加えることで，正解とオーバーフィットなパッチの両方を含むバグ修正事例を増やし，特に RQ2で調査する正解パッチの分離可能性を評価しやすくする．正解
パッチとして，Sobreira ら [18] のデータセット（注 2）を利用した．

果を確認したところ，テストのタイムアウトが影響していると考察された．テストの実行時間がタイムアウト時間と同程度の場合，振る舞いの同じパッチが同じテストを実行したにもかかわらず，実行時間のわずかな差によりテスト結果が異なる場合がある．実際に，1 つのパッチに対し複数回同じテストを実行す
ると，通過する場合とタイムアウトにより失敗する場合の両方がみられた．これにより，同じ振る舞いのパッチが別のグルー

6. 2 実 験 設 定

プに分類された可能性が高い．タイムアウトの上限値を増やす，提案手法では自動テスト生成ツールとして，EvoSuite [9] を利またはタイムアウトを無くすことにより，少数のグループを形成用した．ステップ 1 で EvoSuite にシード値 1 から 5 を与え，各パッチあたり 5 回分テストを生成した．ﬂaky test のチェックは
各テストケースにつき 1 回実行した．合計で 808,218 個のテス
トケースを生成し，うち 1,216 個（0.15%）が ﬂaky test だった．

6. 3 実 験 結 果
RQ1: 確認すべきパッチ数はどの程度減少するか？
各題材について，削減率 = 1 - (提案手法が出力するグループ
数 / 生成パッチ数) を求める．これは，確認すべきパッチ数をどの程度削減できるか示す値である．この値が大きいほど確認すべきパッチ数が減少していることを示す．この RQ では，生成されたパッチ数が 10 個より多い題材のみを対象とした．これ
は，出力パッチ数が多く利用者による確認がより困難な場合に，提案手法が有効に働くことを示すためである．その結果を図 4に示す．削減率は平均で 84%，中央値 90%であり，確認すべき
パッチ数を大幅に削減できることがわかった．

できる可能性がある．
次に各題材で生成されたパッチを提案手法を用いて分割した状況を図 5 に示す．グラフの各色が 1 つのグループを表している．各題材で，いくつかのグループに分割されていることがわ
かる．特に，各グループに含まれるパッチ数は一定ではなく，1つの大きいグループと複数の小さいグループに分割されている．
これは，APR ツールが出力するパッチは共通する部分が多いことが原因として考えられる．バグを含むプログラムを修正するには，失敗するテストを通過させるために特定の処理が行われやすい．例えば Math 85 のほとんどのパッチは，例外を発生させないようスロー文を削除する操作が共通している．パッチによってはそれ以外の箇所も変更しているが，それは必ずしも振る舞いに影響を与えない．よって，大部分のパッチが同じ振る舞いをし，一部のパッチが異なる振る舞いをすることにより，図 5のような結果になったと考えられる．

Math 58 は他の題材に比べて削減率が低い．テストの実行結
RQ1 への回答：提案手法は確認すべきパッチの数を，平均で（注 1）：https://github.com/program-repair/RepairThemAll_experiment（注 2）：https://github.com/program-repair/defects4j-dissection

84%，中央値で 90%削減可能であり，APR ツールの利用者がパッチを確認するコストを大幅に削減可能である．

—4—

RQ2: 正解・不正解パッチを別のグループに分離できるか？
各題材について，提案手法を適用し得られた各グループに含

14
12
10

まれるパッチが正解かどうか目視で確認する．しかし生成され8

たパッチは非常に多いため，全てを目視確認することは現実的

6でない．そこで，グループに含まれるパッチ数が 10 個以下であればその全てを確認し，10 個以上の時は 10 個を下限としその10%を確認した．また，予め加えた正解パッチと同じグループに属するパッチは全て目視で確認を行った．

4
2
0[0,60](60,65](65,70](70,75]分離に失敗

図7(75,80](80,85](85,90](90,95]

分離に成功

分離の成否と EvoSuite のテストカバレッジの分布

目視確認の結果を表 1 に示す．また，図 6 に表 1(a)〜(e) の各分割状況を示す．例として (a) は，APR ツールはオーバーフィットなパッチのみ生成しており，あらかじめ加えた実際の修正パッチは，オーバーフィットなパッチとは別のグループに分離されている．表 1 の通り，全 41 個の題材のうち 26 個の題材において生成されたパッチの正誤による分離に成功した．分離ができなかった題材について，正解の振る舞いを持つパッチが 2グループ以上に分けられた事例 (e) は Math 58 の 1 つのみだった．RQ1 で調査したように，同じテストが成功したり失敗した
りするため，振る舞いが同じでも異なるグループに分けられることが原因と考えられる．

RQ3: 正誤の異なるパッチ分離に影響を与える特徴はあるか？
正誤の異なるパッチの分離に影響を与える要素を調査した．調
査項目として，各題材におけるバグの修正行数および修正箇所・

EvoSuite が生成したテストのカバレッジ・修正対象メソッドのメトリクス（行数・循環的複雑度・NPath 数）を計測した．
正誤の異なるパッチの分離について，分離に成功した題材と失敗した題材別でまとめた結果を表 2 に示す．EvoSuite のテス
トカバレッジに注目すると，テストカバレッジが高いほど分離しやすくなることがわかる．図 7 は各題材ごとのテストカバレッ
ジのヒストグラムを示している．分離に失敗した題材よりも，分(c)，(d) の 14 個の題材について調査したところ，APR ツー
ルが修正すべき箇所を含むクラス以外も変更している題材が 7個存在した．今回の実験では，修正すべき箇所を含むクラスのみ
からしかテストを生成しなかったため，それ以外の箇所の変更
による振る舞いの違いを検出できなかったと考えられる．APR
ツールが修正した全てのクラスを対象にテストを生成すれば，適切にパッチを分類できる可能性がある．

離に成功した題材の方がカバレッジの分布が高い．85%〜90%が最も多く，失敗に分離した題材より 3 倍多いことがわかった．
テストのカバレッジが高いことは，テストがパッチの振る舞いを十分に網羅できていることを表しており，正解パッチとオーバーフィットなパッチを分離しやすくなっていると考えられる．
次に，生成パッチ数に注目すると分離に成功した題材の方が，パッチ数が多い．パッチ数が多いことにより，生成するテストの分離に失敗する題材はほとんどが APR ツールによって正解を出力できないバグ (c) であった．APR ツールが正解パッチを出力できた題材である (b), (d) を比較すると分離に成功できた題
材 (b) の方が多い．この結果から APR ツールが修正しやすいプ
ログラムは，振る舞いの違いを検出しやすいと考察される．

RQ2 への回答：提案手法は半数以上の題材で正解パッチとオーバーフィットな題材を別のグループに分離することがで数も多くなった結果，分割が細分化され正誤の異なるパッチが別のグループに分離されやすくなった可能性がある．
表中の “修正の特徴” は，正解パッチで行われた修正内容から得た値である．分離に失敗する題材は修正行数が多いが，修正箇所に差はなかった．バグに行われた修正の特徴がパッチの分離に与える影響は大きくないと考えられる．

“メソッドのメトリクス” は，バグを含むメソッドを対象に計きた．さらにテスト生成対象を拡大することにより，分離精測した値である．NPath とは，実行可能な経路の総数であり，度を改善する余地も残されている．

分岐が増えるほど値が大きくなる．こちらは分離に成功する題材の方が，行数，循環的複雑度，NPath の全てで高い値となっ

表1

正誤の異なるパッチの分離結果た．より複雑なメソッドの方が入力に対して様々な振る舞いを(a)APR 正解なし

20持つようになり，自動生成したテストも異なる振る舞いを網羅で(b)APR 正解あり

6(c)APR 正解なし

きるようになるため，分離がしやすくなった可能性がある．

13(d)APR 正解あり

1

分離に成功

分離に失敗

(e) 正解が複数に分割
合計
(a)

(b)

1
41

実際の修正パッチ(d)

した．図 4，5 中の点線の左側は正誤の異なるパッチの分離に成功した題材，右側は失敗した題材である．パッチの削減率，分割APRのオーバーフィットなパッチ
APRの正解パッチ(c)

最後に，RQ1 で調査した確認すべきパッチの削減率やグループの分割状況と，正誤の異なるパッチの分離可能性の関係を調査(e)

状況ともに目立った特徴は得られなかった．したがってパッチの削減率や分割状況から，正誤の異なるパッチの分離が適切に行われているかどうかを推定することは，難しいといえる．

RQ3 への回答：自動生成したテストのカバレッジ，および修正対象のメソッドのメトリクスが，正誤の異なるパッチの分離
図 6 表 1(a)〜(e) と分割結果の対応に影響を及ぼす可能性があることが調査結果より示唆された．

—5—

7. 妥当性の脅威
本研究の評価実験では，テストの生成に EvoSuite を用いた．
他の自動テスト生成技術，あるいは手動でテストケースを追加した場合には異なる実験結果が得られる可能性がある．

RQ2 において，出力された各グループが正解パッチまたはオー
バーフィットなパッチのみで構成されるかを，目視で確認した．
そのため著者の主観に大きく依存する．他の APR ツール利用者が判断した場合，異なる結果となる可能性がある．
本提案手法は，パッチを生成する APR ツール全てに対して利用可能である．しかし，限られた種類の APR ツールが出力したパッチに対して実験を行ったため，それ以外の APR ツールが出力したパッチで提案手法が有効に働くかどうかは不明である．
また，バグの題材として Defects4J を用いたが，別のバグに対して適用した場合，同様の結果が得られるとは限らない．

8. あ と が き
本研究では，APR が出力したパッチの確認コスト削減を目的に，パッチを振る舞いごとにグループ化する手法を提案した．提案手法では，自動テスト生成技術を用いて各パッチからテストを生成し，全てのパッチと生成したテストの組み合わせで相互に実行した結果を用いて分類を行う．評価実験を行った結果，提案手法は確認すべきパッチ数を平均で 84%，中央値で 90%削減できた．また，半数以上の題材で正解のパッチとオーバーフィットなパッチを別のグループに分離することができた．
今後の研究課題として，どのグループがよりオーバーフィッ
トを起こしている可能性が高いか，またあるグループの中でどのパッチを優先的に確認すべきかを提示できるようにすることを考えている．これらの情報を利用者に提示することで，確認のコ
ストをさらに削減できる可能性がある．これを実現するために，分離精度の更なる向上，および提示すべきパッチを選択するために，グループ化や正解パッチの分離に影響を与える特徴の分析を考えている．特徴の分析については，本研究で扱った題材の特徴
以外に，収集対象を拡大することやパッチ適用前後の各種メトリ
クスの変化も考慮することを検討している．
文

献[1] B. Hailpern and P. Santhanam, “Software debugging, testing,and veriﬁcation,” IBM Systems Journal, vol.41, no.1, pp.4–
12, 2002.
[2] T. Britton, L. Jeng, G. Carver, and P. Cheak, “Quantify thetime and cost saved using reversible debuggers,” Technicalreport, Cambridge Judge Business School, 2012.
[3] L. Gazzola, D. Micucci, and L. Mariani, “Automatic software
repair: A survey,” IEEE Transactions on Software Engineering, vol.45, no.1, pp.34–67, 2019.

[4] M. Monperrus, “Automatic software repair: A bibliography,”
ACM Computing Surveys, vol.51, no.1, pp.1–24, 2018.
[5] E.K. Smith, E.T. Barr, C. Le Goues, and Y. Brun, “Is thecure worse than the disease? overﬁtting in automated program repair,” Proc. Foundations of Software Engineering,pp.532–543, 2015.
[6] Z. Qi, F. Long, S. Achour, and M. Rinard, “An analysis ofpatch plausibility and correctness for generate-and-validate
patch generation systems,” Proc. International Symposium
on Software Testing and Analysis, pp.24–36, 2015.
[7] X.-B.D. Le, F. Thung, D. Lo, and C.L. Goues, “Overﬁtting insemantics-based automated program repair,” Empirical Software Engineering, vol.23, pp.3007–3033, 2018.
[8] C. Pacheco and M.D. Ernst, “Randoop: Feedback-directed
random testing for java,” Proc. Companion to the Conference
on Object-Oriented Programming Systems and Applications
Companion, pp.815–816, 2007.
[9] G. Fraser and A. Arcuri, “Evosuite: Automatic test suite generation for object-oriented software,” Proc. Symposium andthe European Conference on Foundations of Software Engineering, pp.416–419, 2011.
[10] M. Motwani, M. Soto, Y. Brun, R. Just, and C. Le Goues,“Quality of automated program repair on real-world defects,”
IEEE Transactions on Software Engineering, 2020.
[11] S. Wang, M. Wen, B. Lin, H. Wu, Y. Qin, D. Zou, X. Mao,and H. Jin, “Automated patch correctness assessment: How
far are we?,” Proc. International Conference on AutomatedSoftware Engineering, pp.968–980, 2020.
[12] Y. Xiong, X. Liu, M. Zeng, L. Zhang, and G. Huang, “Identifying patch correctness in test-based program repair,” Proc.
International Conference on Software Engineering, pp.789–
799, 2018.
[13] H. Ye, M. Martinez, and M. Monperrus, “Automated patch
assessment for program repair at scale,” Empirical Software
Engineering, vol.26, no.2, 2021.
[14] Q. Xin and S.P. Reiss, “Identifying test-suite-overﬁtted
patches through test case generation,” Proc. International
Symposium on Software Testing and Analysis, pp.226–236,
2017.
[15] T. Durieux, F. Madeiral, M. Martinez, and R. Abreu, “Empirical review of java program repair tools: A large-scale experiment on 2,141 bugs and 23,551 repair attempts,” Proc.
European Software Engineering Conference and Symposiumon the Foundations of Software Engineering, pp.302–313,
2019.
[16] R. Just, D. Jalali, and M.D. Ernst, “Defects4j: A databaseof existing faults to enable controlled testing studies for java
programs,” Proc. International Symposium on Software Testing and Analysis, pp.437–440, 2014.
[17] Q. Luo, F. Hariri, L. Eloussi, and D. Marinov, “An empiricalanalysis of ﬂaky tests,” Proc. International Symposium on
Foundations of Software Engineering, pp.643–653, 2014.
[18] V. Sobreira, T. Durieux, F. Madeiral, M. Monperrus, andM. deAlmeida Maia, “Dissection of a bug dataset: Anatomyof 395 patches from defects4j,” Proc. the International Conference on Software Analysis, Evolution and Reengineering,pp.130–140, 2018.

表 2 分離の正誤と題材の特徴

分離に成功
分離に失敗

修正の特徴

カバレッジ

生成パッチ数

平均値

0.816

118.4

4.66

中央値

0.867

10.5

3

平均値

0.728

75.7

8

中央値

0.798

5

7

修正行数

メソッドのメトリクス

修正箇所

行数

2.46 36.54
2

循環的複雑度

NPath

12.52 4820203.3

18

6

16

2.4 25.75

8.213132.3

4

4

2

12

—6—