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

信学技報
TECHNICAL REPORT OF IEICE.

企業におけるソフトウェア開発に対する自動プログラム修正技術
内藤圭吾†

谷門 照斗†

柗本 真佑†

肥後芳樹†

切貫 弘之††

倉林利行††

丹野治門††

楠本 真二†† 大阪大学大学院情報科学研究科 吹田市†† 日本電信電話株式会社 港区
あらまし

近年多くの自動プログラム修正の研究が行われている．その修正対象はほとんどの場合オープンソースソ

フトウェアや自動プログラム修正技術の評価用に用意されたデータセットであり，企業におけるソフトウェア開発においてそのツールおよびアルゴリズムが有効であるかどうかは示されていない．そこで本稿では，実際に企業内で開発，利用されているシステムに対して既存の自動プログラム修正ツールを適用することで，企業のソフトウェア開発で発生したバグに対する自動プログラム修正ツールの有効性を調査した．また，本稿ではその調査結果と企業のソフトウェア開発に対する自動プログラム修正ツール適用の障壁についても議論する．
キーワード デバッグ，プログラム自動修正，コード再利用

1. は じ め に以上より，本研究では企業で開発運用されているシステムに対して自動プログラム修正技術を適用し，その有効性及び実用ソフトウェア開発には様々な工程があり，その中でもデバッ化に向けての障壁を調査した．調査の結果，一つのバグについグ作業に必要な時間はプログラミング工程の 50%以上を占めるて開発者の修正と同等の修正を自動プログラム修正によって行といわれている [1]. そこで，開発工程を短縮するためにデバッうことができた．また実用化に向けて三つの障壁を明らかにしグ支援の研究が盛んに行われている．デバッグはバグ同定とバた．以降 2. では関連研究のアルゴリズムやその有効性についグ修正の二つに分けられる．これまでに，デバッグ支援のためて述べる．3. では本研究の研究背景および調査項目について述にバグ同定の自動化 [2] [3] [4] や，バグの理解支援の研究 [5] がべる．4. では調査対象と，調査方法について述べる．5. では，行われてきた．そして近年，バグの特定及び修正を自動で行う実験，調査の結果および考察について述べる．6. では妥当性の自動プログラム修正技術の研究が盛んに行われている．

脅威について述べ，最後に 7. で本研究のまとめと今後の課題に自動プログラム修正技術の一つに，ソースコードの再利用に基づく手法である GenProg がある [6]．GenProg は，バグを含むプログラムと，失敗テストを含むテストスイートを入力とし，全てのテストケースを通過するプログラムを出力する．その動作はバグ同定された箇所に対して行の挿入や削除，置換を遺伝ついて述べる．

2. 関 連 研 究
近年多くの自動プログラム修正の研究が行われており，それらは以下のように分類できる．

的アルゴリズムに基づいて繰り返し行うことによってプログラ•

再利用に基づく手法ムの修正を行う，というものである．Le Goues らは GenProg•

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

を 8 個のオープンソースソフトウェアのバグ，合計 105 個に対•

修正パターンに基づく手法して適用し，そのうち 55 個のバグについて修正に成功することこれらの手法はいずれも，バグを含むプログラムと，失敗テでその有効性を示した [6]．その後も，GenProg を評価する研ストを含むテストスイートを入力とし，修正が完了したプログ

究や，その他の自動プログラム修正技術の研究が行われてきた．

ラムを出力する．バグ同定及び，終了判定にはテストスイート

その評価にはいずれも GenProg の評価同様オープンソースソを用いる．以下で，これらの手法の代表的なものが，どういっフトウェアや，既存のデータセットが用いられている [7] [8]．つた方法で修正を行うのかを紹介する．

まり，現在企業におけるソフトウェア開発に対して自動プログ

2. 1 GenProg

ラム修正技術を適用し評価した研究は未だにない．そのため，まず，再利用に基づく手法の一つである GenProg の修正方

現在の自動プログラム修正技術が企業におけるソフトウェア開法を説明する．GenProg は修正対象プログラム中のソースコー発において有効であるのか，また有効でない場合どういった問

ドを用いて，バグ同定された箇所を変更したプログラム (以下，題があり，解決すべきなのかが判明していない．

—1—

入力 : バグを含むプログラム
テストスイート

バグを含むプログラム90%

80%

初期変異プログラム群生成

コピー
交叉

第0世代
XX%

100%

85%

95%

75%

90%

変異

変異70%

評価関数による評価，選択

90%

第1世代

第2世代 第n世代: その変異プログラムのテスト通過割合

次世代の変異プログラム生成

図 2 遺伝的アルゴリズムによるの修正の流れ
終了判定

No

Qi らは失敗するテストケースが見つかった場合，その段階でYes
出力：全てのテストケースを通過するプログラム

テストケースの実行を打ち切り，次の変異プログラムを生成することで修正を行う手法，RSRepair を提案した [9]．Qi らは

GenProg と同様の 8 個のオープンソースソフトウェアのバグを用いて RSRepair を評価し，GenProg と比較してより多くのバグを修正できたと報告している．しかし，一つでも失敗す
図 1 GenProg の修正の流れるテストケースが見つかった段階でテストケースの実行を打ち切るため，GenProg とは異なり RSRepair は単一行の修正し変異プログラム) を繰り返し生成，評価を行うことでバグの修か行うことができない．

正を行う．GenProg の修正の流れを図 1 に示す．プログラム

2. 2 その他の手法の変更の方法は以下の 3 通りがある．

次にプログラム意味論に基づく手法である SemFix は，テス

挿入 バグ同定行の次の行に新たにソースコードを挿入する．

トスイートからバグ同定された箇所が満たすべき制約を導出し，削除 バグ同定行を削除する．

その制約を満たすプログラム文を生成する [7]. Nguyen らはこ

置換 バグ同定行を削除し，その行に新たにソースコードを挿の手法を 5 つのソフトウェアのバグに対して適用し， GenProg入する．

よりも多くのバグを修正できたことを報告している．再利用に

GenProg では，より効率的に修正を行うためにプログラム基づく手法は既存のプログラム中に存在しないソースコードにの変更に遺伝的アルゴリズムを用いている．遺伝的アルゴリズよる修正を行うことができないことに対し，プログラム中にムによる修正の流れを図 2 に示す．以下，遺伝的アルゴリズムソースコードが存在しなくても修正が可能であることがプログによる修正について述べる．

ラム意味論に基づく手法の利点である．この手法では，バグ同まず，バグを含むプログラムから複数の変異プログラムを生定された箇所が満たすべき論理式を，SMT ソルバを用いて解成する．その後，それぞれの変異プログラムに対して全てのテく．しかし，SMT 問題は NP-完全であるため，論理式が複雑ストケースを実行し，成功したテストケースの数をその変異プな場合は現実的な時間で解くことができないことが欠点の一つ

ログラムの評価として与える．そして，評価の良いものだけかである．また，複数行の変更を必要とするバグの修正を行うこら次の世代を生み出す．次の世代の生成は以下の 3 通りの方法ともできないという欠点も存在する．

がある．
コピー 何も変更を加えずに次の世代に同じ変異プログラムを残す．

最後に修正パターンに基づく手法である PAR の修正方法を説明する．PAR ではあらかじめ 10 個の修正パターンを作成しておき，それを用いて修正を行う．Kim らは PAR を 5 つの変異 変更を追加して新たな変異プログラムを生成する．

オープンソースソフトウェアのバグに対して適用し，GenProg

交叉 二つの変異プログラムの変更内容を組み合わせて新たなよりも多くのバグを可読性の高い形で修正に成功したことを報変異プログラムを生成する．
世代の生成を，全てのテストケースを通過する変異プログラムが生成されるか，世代数が上限に達するまで繰り返す．

Le Goues らは GenProg を 8 個のオープンソースソフトウェ告している．しかし，用意されたパターンに当てはまらないバグは修正できないことや，修正パターンの作成に技術的に難しいものが存在することが問題点として挙げられている [10]．また，実験対象や実験内容に対する批判も存在している [11]．

アのバグ，合計 105 個に対して適用し，そのうち 55 個のバ本研究では，自動プログラム修正ツールを企業で開発運用さグについて修正を成功させることによってその有効性を示しれているシステムのバグに対して適用する. その際に複数行のた [6]．しかし，GenProg は変異プログラムの評価時に全ての修正が必要不可欠であるため，再利用に基づく手法を対象としテストケースを実行するため，計算コストがかかる．そこで，て調査を行う．

—2—

2. 3 自動バグ同定手法の中は，そのフィルタリングを行った後，残ったバグの数で今回実験に使用したツールは自動バグ同定に Ochiai というある．

フレームワークを用いているため，以下で Ochiai の自動バグ同•提供されたバグ (327 個)定の方法を説明する [12]．Ochiai はバグを含むプログラムと，•単体テストで発見されたバグ (上記の内 132 個)

失敗するテストケースを含むテストスイートを入力として与•バグ修正情報を取得できるバグ (上記の内 79 個)

え，出力には各行のバグが存在している怪しさを出力する．失•修正が Java ファイルのみのバグ (上記の内 23 個)

敗テストケースと成功テストケースの実行経路を用いて怪しさ

以下では，それぞれのフィルタリングの必要性とその方法にを 0〜1 の数値で計測する．i 行を実行する失敗テストケースの数を f ail(i)，i 行を実行する成功テストケースの数を pass(i)，ついて述べる．
まず， 単体テストで発見されたバグについて述べる．ソ

失敗するテストケースの総数を totalf ail とおくと，i 行の怪し

フトウェアの開発中にバグを発見する方法としては，単体テス

さ suspicious(i) は以下の様になる．

トや結合テストなどが挙げられる．今回対象言語として選んだ

suspicious(i) = √f ail(i)totalf ail ∗ (f ail(i) + pass(i))

Ochiai はこのメトリクスで，各行の怪しさを計測し，全てのJava において，単体テストは JUnit というテストの自動化を行うためのフレームワークが実装されているが，結合テストは自動化がされていない．GenProg は前述のアルゴリズムの通り，変異プログラムを生成するたびに全てのテストケースを実行の怪しさを出力する．

行し，テストケースが成功しているか判定を行うため，テスト

3. 調査の目的は実行と成功か失敗かの判定が自動化されている必要がある．

本章では自動プログラム修正技術の課題を示し，課題解決にグを選択した．今後，結合テストの自動化が実装された場合，向けた調査項目について述べる．

そこで，今回は対象バグとして単体テストで発見されているバ
結合テストで発見されたバグについても対象として実験を行う

3. 1 自動プログラム修正技術の課題ことができると考えられる．対象システムにおいてバグはバグ関連研究で述べた通り，再利用に基づく手法の一つである票で管理されており，そこにどのようにしてそのバグが発見さ

GenProg を含む様々な自動プログラム修正技術はオープンソーれたかも記載してあったため，その記述を参考にフィルタリン

スソフトウェアを用いることによって，手法の有効性を評価しグを行った．ている．つまり，先行研究では本来の目的である企業のシステ

次に， バグ修正情報が取得できるバグについて述べる．

ムに対する修正の可否や，その有効性が示されていない．オー

GenProg の出力は全てのテストケースを通過する修正プログ

プンソースソフトウェアと企業で開発されたシステムでは，テラムである．ここで気をつけなければならないことは，全てのストの方法や開発フローなどの点で違いがあるため，オープンテストケースを通過することと，バグが修正されたことは等価

ソースソフトウェアで有効であるからといって，必ずしも企業ではないということである．テストスイートが不十分であったで利用可能であるとはいえないと著者らは考えた．

場合，バグが修正されていないがテストケースは全て通過する，

3. 2 調 査 項 目というプログラムが出力されることもある．つまり，自動プロ

本研究の目的は，企業におけるソフトウェア開発に対する自グラム修正ツールが出力した修正プログラムが全てのテスト

動プログラム修正技術が有効であるかどうか，および自動プロケースを通過するだけの修正プログラムなのか，バグが正しくグラム修正技術の実用化に向けた障壁を明らかにすることであ修正された修正プログラムなのかを評価する必要があるというる．そのため以下の調査項目を設定する．

ことである．そこで，企業で利用されているバージョン管理シ

RQ1 自動プログラム修正は実開発環境でも有効であるかステムから，そのバグの修正内容が取得できるかどうかでフィ

RQ2 実用化にはどのような障壁が存在するかルタリングを行った．バージョン管理システムには以下の情報

4. 調が管理されている．

査

•

修正日時

本章では調査の方法について述べる．

•修正した開発者名

4. 1 調 査 対 象•修正したファイル名

本調査は企業から提供されたシステムのバグ，合計 327 個を•修正内容対象に行う．システムの詳細は以下の通りである．

バグ票記載のバグには，バージョン管理システムで修正した開発言語 Java

リビジョンが確認できないもの，複数のバグが一つのリビジョ

総行数 約 19 万行

ンで修正され修正内容とバグが紐付けられないものが存在して自動プログラム修正のツールとして，自動バグ同定のフレーいたため，手作業でそのバグの修正内容が取得できるかどうか

ムワーク Ochiai および， GenProg を Java に使用できるように改変した jGenProg の二つを実装したツール Astor を用いた [8]．

確認することでフィルタリングを行った．
最後に 修正が Java ファイルのみのバグ について述べる．
今回利用したツールには修正対象が Java ファイルのみという実験，評価を行うために次のフィルタリングを行った．括弧

—3—

11:
12:
13:
14:
15:
16:

for(int i; i < num; i++){if(checkNum(num)) {list = new ArrayList<String>();+break; //開発者修正+
return list; // GenProg 修正}
list.add(num);}
return list;

int b = 5;
if (a > b){a = b;}else{
a = b – a;}(a)成功テストケース

11:
12:
13:
14:
15:
16:

int b = 5;
if (a > b){a = b;}else{
a = b – a;}(b)失敗テストケース

図 4 テストによるプログラムの実行経路．網掛け部分が実行された
コード．

図3 修正結果

残りの 3 件は，バグ同定の失敗，自動プログラム修正の失敗により，修正を行うことができなかった．バグ同定の失敗の原制約がある．しかし，今回実験対象としたシステムには，ソースコードである Java ファイル以外にも，設定ファイルである.property ファイルや，入出力ファイルである .xml ファイルなどが含まれていた．そこで，修正内容が Java ファイルのみであるかどうかのフィルタリングが必要である．前述した因については後に議論する．

5. 2 調 査 結 果
実験及び企業とのミーディングを通して，次の 3 点における障壁が確認された．

バグ•

修正可能なバグの数のフィルタリングと同様に，バー•

パラメータの調整

ジョン管理システムから，その修正ファイルが Java ファイル•

テストケースの数のみかどうか手作業でフィルタリングを行った．

以下では，それぞれの障壁に関する詳細を述べていく．

修正情報が取得できるバグ

4. 2 調 査 方 法

修正可能なバグの数

本研究では各 RQ に回答するために以下の実験と調査を

4. 1 で述べた通り，今回用いたツールには適用するうえでの行った．

制約がいくつかある．そこでフィルタリングを行うことで対象

実験 企業で開発されたシステムのバグに対して GenProg を適用し，その修正可能性を調査する．
調査 企業とのミーティングを通して実用化に向けての障壁を調査する．

バグの数が 23 個まで減少した．これは，全体のバグの数に対してわずか 7% である．バグ修正情報を取得できるかどうかで，53 個のバグがフィルタリングされたが，これは実験，調査を行う上で Astor が出力した修正内容を評価するためのフィル

今回，題材としたシステムでは，バグの修正内容についてはタリングであるため，その 53 個が修正可能であるかは未確認

バージョン管理ツールで保存されているが，バグを発現させるである．しかし，その 53 個全てが修正可能なバグであった場テストケースの存在しないバグも存在した．そこで，本研究で合でも，修正可能なバグの数は 23% にとどまる．この修正可はバグを含むリビジョンのテストスイートにバグを発現させる能なバグの数の少なさが，実用化に向けての障壁の一つである．

テストケースを新たに追加することで，テストスイートの補完パラメータの調整を行い，実験を実施した．

今回用いた自動プログラム修正のツール Astor には，様々な

5. 結果

この章では実験，調査の結果と結果に対する考察について述べる．

パラメータが存在する．以下のパラメータはその一部である．

•ランダムに行を取得するシード値•

遺伝的アルゴリズムにおける，一世代あたりの変異プログラムの数．

5. 1 実 験 結 果•

現在，23 件のバグのうち，4 件について実験を行っている．

こういったパラメータが合計 70 個存在し，最適な値が容易

実験を通して一つのバグについて修正を行うことができた．に求められないものも多く存在する．本来自動プログラム修正

修正内容を図 3 に示す．ただし，企業内で運用されているシ技術の目的は開発工程の短縮であるにも関わらず，パラメータステムであるため，図 3 のコードは実際のコードとは変数名の調整に時間がかかってしまっては本末転倒である．したがっや，バグとは関係のない処理など一部異なる．図 3 を見ると，て，このパラメータの調整の難度が二つ目の障壁である．

GenProg の修正は開発者の修正と同等の動作を行うことが分遺伝的アルゴリズムにおける，最大世代数．

テストケースの数かる．また，その修正コードの可読性も十分なものといえる．

企業においてテストケース作成の基準の一つにカバレッジがよって，企業のソフトウェア開発においても既存の自動プログある．カバレッジとはプログラム全体のうち，テストケースにラム修正技術で修正可能なバグが存在し，有効であることが分よって実行された命令や分岐の割合のことである．テストケー

かった．

スによって実行された命令の割合を命令カバレッジ，テスト—4—

ケースによって実行された分岐の組み合わせの割合を分岐カバ

RQ1 への回答 企業で開発されたシステムのバグにおいても，レッジという．カバレッジを指標としてテストケースを作成し自動プログラム修正技術によって修正可能なバグは存在する．

た場合，一定数のテストケースが作成されるが，自動プログラ

RQ2 への回答 自動プログラム修正技術についての障壁としム修正を行うためにはテストケースの数が不十分な場合がある．て，修正可能なバグの数の少なさ，パラメータ調整の難度とい2. で自動バグ同定のフレームワークである Ochiai のメトリク

う 2 点の障壁が明らかになった．また，開発者側の自動プログスを紹介したが，自動バグ同定のメトリクスでは失敗か成功か

ラム修正技術導入に向けた障壁として，人がソフトウェアの品に関わらずテストケースの数が怪しさを決定する重要なファク質を確保するためのテストケースと自動プログラム修正技術のターになっている．以下で，テストケースの数が怪しさに大きためのテストケースに乖離があることが明らかになった．

く寄与する例を述べる．図 4 に二つのテストケースによる実行経路を示す．テストケースがこの二つだけの場合と，(a) の成

6. 妥当性の脅威

功テストケースと同様の実行経路の成功テストケースが 9 個，

本研究ではバグを発現させるテストケースを追加して，実験99 個の場合についての各行怪しさを表 1 にまとめる．図 4 のを実施した．その新たなテストケースの作成は，バグの内容や二つのテストケースだけで，命令カバレッジと分岐カバレッジバグの修正内容を把握したうえで，恣意的にバグを発現させるはともに 100% になっている．しかし，表 1 を見ると，テストテストケースの作成を行ったため，実際に開発者が手元でバグケース二つだけでは，失敗テストケースのみで実行されているを発見した際のテストケースとは乖離している可能性がある．

13 行目に加えて，11 行目と 12 行目の怪しさも高い値を示して開発者が手元でバグを発見した際のテストケースを用いて実験いる．11 行目，12 行目は成功テストケース，失敗テストケーを行った場合，今回とは異なる実験結果や，障壁が明らかになスともに実行されているため，直感的にはそこまで怪しくはなる可能性がある．

いが，テストケースが少ないため，11，12 行目も高い怪しさになってしまっている．表 1 を見ると，成功テストケースを 9

7. お わ り に個，99 個に増やすと，11，12 行目の怪しさが減っていくこと

本研究では，既存の再利用に基づく自動プログラム修正技術が分かる．以上の例から分かるように，テストケースの数が怪が，企業におけるソフトウェア開発に適用した際に有効であるしさを決定する大きなファクターとなっている．そのため，テかどうか，実用化に向けてどのような障壁が存在しているかをストケースの数が不十分であった場合，自動バグ同定が正しく調査した．調査の結果，企業で開発運用されているシステムの行われない．今回実験を行ったバグについても，自動バグ同定バグのうち一つのバグについて開発者による修正と同等の修正がうまくいっていないために自動プログラム修正が行えなかっを行うことに成功した．また実用化に向けて三つの障壁を明らたバグも存在する．

かにした．今後は，引き続き GenProg の評価を行うとともに，この障壁は少ないテストケースで高いカバレッジを達成する，その他の自動プログラム修正ツールの評価も行っていく．また，という戦略をとっている場合のみに限った話ではない．例とし今回明らかになった障壁の解消に向けたツールの実装などを行て，0〜9 の自然数を入力として，入力の値を四捨五入するプロうことが今後の課題である．

グラムを作成したとする．そのプログラムに対して，代表的な

文テスト技法である同値分割や，境界値分析に基づきテストケースを作成したとする．その場合，正常系のテストケースとしては，0〜4 の範囲に含まれる自然数を入力とするテストケースと，5〜9 の範囲に含まれる自然数を入力とするテストケースを高々二つずつ用意すると十分である．しかしこれは，あくまで人間が正しく機能を実装できているか，バグが存在していないかを確かめるためのテストケースであるので，自動プログラム修正を行うためには不十分である可能性がある．つまり，人間がプログラムの正しさを確かめるためのテストスイートと，自動プログラム修正において，正しくバグ同定を行うためのテストスイートは異なる，ということがこの障壁の本質である．
以上より，各 RQ に対する回答は次の通りである．

表 1 テストケースの数の違いによる怪しさの値の変化
ソース \成功テストケース数

1

11: int b = 5;

0.7 0.3 0.1

12: if(a > b){0.7 0.3 0.1

13: a = b;111

15: a = b - a;000999献[1] J. Baker, “Experts battle l192bn loss to computerbugs,” 2012. http://www.cambridgenews.co.uk/Expertsbattle192bn-loss-bugs/story-22514741-detail/story.html.
[2] D. Saha, M.G. Nanda, P. Dhoolia, V.K. Nandivada, V.
Sinha, and S. Chandra, “Fault localization for data-centricprograms,” Proceedings of the 19th ACM SIGSOFT symposium and the 13th European conference on Foundationsof software engineering, pp.157–167, 2011.
[3] J.A. Jones and M.J. Harrold, “Empirical evaluation of thetarantula automatic fault-localization technique,” Proceedings of the 20th IEEE/ACM international Conference on
Automated software engineering, pp.273–282, 2005.
[4] M.Y. Chen, E. Kiciman, E. Fratkin, A. Fox, and E. Brewer,“Pinpoint: Problem determination in large, dynamic internet services,” Dependable Systems and Networks, 2002.
DSN 2002. Proceedings. International Conference on IEEE,pp.595–604, 2002.
[5] D. Zuddas, W. Jin, F. Pastore, L. Mariani, and A. Orso,“Mimic: locating and understanding bugs by analyzing
mimicked executions,” Proceedings of the 29th ACM/IEEE
international conference on Automated software engineering, pp.815–826, 2014.
[6] 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,” Software Engineering—5—[7]

[8]

[9]

[10]

[11]

[12]

(ICSE), 2012 34th International Conference on IEEE, pp.3–13, 2012.
H.D.T. Nguyen, D. Qi, A. Roychoudhury, and S. Chandra,“Semfix: Program repair via semantic analysis,” Proceedings of the 2013 International Conference on Software Engineering, pp.772–781, 2013.
M. Martinez and M. Monperrus, “Astor: a program repair
library for java,” Proceedings of the 25th International Symposium on Software Testing and Analysis, pp.441–444, 2016.
Y. Qi, X. Mao, Y. Lei, Z. Dai, and C. Wang, “The strengthof random search on automated program repair,” Proceedings of the 36th International Conference on Software Engineering, pp.254–265, 2014.
D. Kim, J. Nam, J. Song, and S. Kim, “Automatic patch
generation learned from human-written patches,” Proceedings of the 2013 International Conference on Software Engineering, pp.802–811, 2013.
M. Monperrus, “A critical review of automatic patch generation learned from human-written patches: essay on theproblem statement and the evaluation of automatic software
repair,” Proceedings of the 36th International Conference onSoftware Engineering, pp.234–242, 2014.
R. Abreu, P. Zoeteweij, and A.J. Van Gemund, “An evaluation of similarity coeﬃcients for software fault localization,”
Dependable Computing, 2006. PRDC’06. 12th Pacific Rim
International Symposium on IEEE, pp.39–46, 2006.

—6—