日本ソフトウェア科学会第 39 回大会 (2022 年度) 講演論文集

プログラム実行履歴を用いたリグレッションの原因検
出に向けて
石部 大夢

山崎 徹郎

千葉 滋

プログラムを修正した際に今まで正しく動いていた部分が意図せず動かなくなることをリグレッションという．リグ
レッションを早期に検出するにはリグレッションテストが有効であるが修正するには原因を特定する必要がある．本
論文ではテストが失敗した時その原因がプログラム中のどの関数にあるのかを絞り込む手法を提案する．過去のテス
トの実行履歴を保存し，現在の実行履歴と比較することで原因を絞り込む．本手法では二つのテストの間で振る舞いが変わった関数を失敗の原因の候補とする．この時引数などが同じ呼び出しにも関わらず結果が変わることを振る舞いが変わったとみなす．また一つの関数の振る舞いが変わるとそれを呼び出している関数の振る舞いも変わる．そのように結果が変わった関数呼び出しは候補から除外する．これにより精度は劣るものの関数ごとに多数のテストを用意しなくてもリグレッションの原因を絞り込めるようにすることを目指す．

起きているかどうかとその原因となった関数がどこで1 はじめにあるかを突き止める．我々は提案手法を JavaScript

ソフトウェア開発においてしばしば機能追加やバグで実装をし Bugbear と名付けた．Bugbear が正しく修正の際に意図せず昔は正常に動いていた機能を破リグレッションの原因を提案できるかを確認するため壊してしまうことがある．これをリグレッションと言バグベンチマークスイートを利用して実験を行った．

い早期に発見及び修正することが望ましい．リグレッ

その結果 2 つのバグケースのうち 2 つに対して正しションを発見する既存手法としてリグレッションテス

くリグレッションの原因を提示することができた．

トが存在する．しかし修正をする上ではどの変更がリグレッションを引き起こしたかを見つける必要があり2 リグレッションの発見と修正

既存手法ではそれが容易でない．

リグレッションの修正は既存の手法では容易でな

本研究ではプログラムの実行履歴を用いてリグレッ

い．リグレッションとはプログラムを修正した際に意ションの原因となっている関数を見つける手法を提案

図せず今まで正しく動いていた部分が動かなくなるする．この手法ではプログラムを実際に実行するコーことである．ソフトウェア開発においてリグレッショ

ドを統合テストのテストコードのように利用し，過去ンは早期に発見及び修正した方がいい．リグレッショのプログラムと現在のプログラムでそのコードをそれンの修正にはリグレッションを発見することとその原ぞれ実行する．統合テストとの違いはテストコードの因を突き止めることが必要である．機械的なリグレッ

正解を利用者が書くのではなく過去のプログラムの振ションへの対処法としてはリグレッションテストなどる舞いを正解とする点である．実行時の各関数呼び出が知られているが，これはリグレッションの発見までしの振る舞いの差分を取ることで，リグレッションがのみを行い，原因の特定は支援しない．
そこで本研究ではリグレッションの修正を容易にす

Concurrent Operations on Splay Trees.
Hiromu Ishibe Tetsuro Yamazaki Shigeru Chiba, 東京大学 大学院 情報理工学系研究科, Graduate School ofInformation Science and Technology.

るため，プログラム実行履歴からリグレッションの原因を特定するツールの開発を目指している．図 1 と図2 のコード例を用いて既存のリグレッションテストでは

const wordConversion = (word) => {2
const dict = {'かん': '勘',
3
4'が': 'が',5'いい': 'いい'6}
7
return dict[word];
8 }1

const wordConversion = (word) => {const dict = {3'かん': ['勘', '缶'],
4'が': ['が'],'いい': ['いい', '良い']56}
7
return dict[word];
8 }
1
2

9

const sentenceConversion = () => {11
const words = ['かん', 'が', 'いい'];12
return words.map((word) => {13
return wordConversion(word);14}).join("");
15 }

図2

変更後コード10

図1

変更前コード原因の絞り込みが難しい．この例だと返す値が array型に変わった WordConversion が失敗するだけでなく，それを呼び出している SentenceConversion，さらに SentenceConversion を呼び出している関数があればそれらも連鎖的に失敗するようになる．単体テストではなく統合テストを用いると，失敗するテスト原因を見つけることが困難なことを説明する．図 1 はの数は減る．しかし統合テストは上位の関数だけを呼漢字変換を行うコードで図 2 はそれを変更した結果リぶので，下位のどの関数が原因であるかを絞り込むのグレッションを起こしているコードである．説明のたは難しい．

め現実的なものを簡略化している．WordConversion

リグレッションの原因を絞り込むために関数の挙動

はひらがなの単語を受け取り漢字に変換をして stringを書き出すデバッグ手法が職人芸的に知られている型で返す．SentenceConversion はひらがなの文を単が，これを手動でやるには手間と知識が必要である．

語に区切り，単語ごとに WordConversion を呼び出し各関数中に引数や戻り値を出力する print 文を挿入すて漢字変換した後，変換された単語を結合して stringることで実行時の各関数の挙動を書き出すことができ型で返す．ここで，入力補完機能 InputCompletion

る．これを利用して元のプログラムと変更後のプログを加えることとなったとする．この機能は変換の候ラムでそれぞれテストコードを実行した際に出力を補を複数要求するため WordConversion による漢字書き出し，それらの差分を取ることでリグレッション

変換も図 2 のように複数の変換結果を array 型での原因を探ることが出来る．しかしこのデバッグ手法返すよう変更する．しかし SentenceConversion はは print 文を埋め込む手間と書き出された出力の差分

WordConversion が string 型で単一の変換結果を返を人が解釈する必要があり手間と知識が要求される．

す前提で作られているため WordConversion が array型を返すよう更新した今，エラーとなる．このような3 Bugbear の提案

変更の際に意図せず既存コードを破壊してしまうこ

本研究は元のプログラムのテストコードと変更後とをリグレッションという．のプログラムのテストコードを実行した際の各関数

このリグレッションを単体テストと統合テストで検呼び出しへの入出力の履歴を比較することでリグレッ証しただけではテストが失敗することはわかるが原因ションの原因を特定するツール Bugbear を提案する．

を絞り込むことは難しい．まず全ての関数に単体テス

Bugbear は JavaScript で実装されており NodeJS でトが用意されている場合について考える．変更前コー動く．バージョン管理システムとして git を採用してド用に作られた単体テストで変更後コードをテストいるプロジェクトでの利用を想定しており，比較したすると変化した関数だけでなくそれを呼び出していいプロジェクトの過去と現在のコミット ID を指定する関数も連鎖的に失敗して大量のテストが失敗してる．本ツールは 3 つの主要なコンポーネントによって構成されている．(1) トレーサー (2) コンパレーター(3) ディテクターである．

3. 2 コンパレーター
コンパレーターは変更後のプログラムをトレースした結果、元のプログラムと比較して挙動が変わった

3. 1 トレーサー

関数をリグレッションの原因の候補とする．この際，トレーサーはプロジェクトを実行した際の各関数呼元のプログラムのテストコードのトレース結果を保び出しの入出力として以下の情報の値を記録する．

存しておき変更後のプログラムでテストコードを実• 関数名行した際に動的にトレース結果が過去と変わっていな• その関数呼びだしを呼び出している関数呼び出しいか比較する．

• 関数実行前の引数コンパレーターは同じ条件で呼び出されたにも関わ• 関数実行前の this

らず違う振る舞いをするようになった関数をリグレッ• 戻り値ションの原因の候補とする．同じ条件で呼び出されて• 関数実行後の引数いるかを判別するために各関数呼び出しには呼び出し• 関数実行後の thisの条件によって定まる識別子を付与する．識別子は関

this とは JavaScript のどのように関数が呼ばれた数名，その関数を呼び出している関数呼び出し，関数かによって決定される値 [2] である．this はクラス内実行前の引数，関数実行前の this のハッシュ値を連でインスタンスを参照するために利用されることが結して生成する．関数の振る舞いは戻り値，関数実行あり，Bugbear ではインスタンス変数にアクセスす後の引数，関数実行後の this の中から実行時にツーるために this を保存している．

ルに与える設定で決めた項目が一致すれば同一性の実装にあたってソースコードを変換して元の関数を振る舞いをするとみなす．どの項目を振る舞いの判断囲むトレース用関数を挿入するトレーサーを作成しに採用するかは設定で決められる他，Bugbear の機た．変換後は図 3 のように 2 行目のトレース用関数能で全ての設定を総当たりで調べることもできる．

global.tracer.wrapCallback が 3 行目から始まる

コンパレーターの制限として，識別子が変わってしコードブロックを囲んでいる．

まう変更は追跡できない点がある．例えば関数名が変トレーサーはトレースした変数の値を JSON 形式

わると別の関数呼び出しとして扱われるため関数呼で保存する．実装にあたっては変数の値を JSON 形

び出しの識別子が変わる．したがってコンパレーター式に変換することが出来る JSON.stringify を利用での比較がなされずリグレッションの原因特定の精度した．例外的に循環参照が行われているオブジェクトが下がってしまう．

は JSON.stringify で変換することが出来ないので循環参照を引き起こしているプロパティは -pruned-

3. 3 ディテクターという文字列に置き換えた．

ディテクターは関数の呼び出し関係を利用してリグ全ての情報を保存するとログが膨大になるため性レッションの大元の原因となった関数を絞り込む．

能に影響が出ない範囲で保存するデータの取捨選択

リグレッションが発生した際，一つの関数が原因でをおこなう．具体的には this がグローバルオブジェあったとしても振る舞いが変わる関数は一つである

クトやモジュールオブジェクトであるときは保存をしとは限らない．ある関数の振る舞いが変化すると，そない．理由は大域変数を全て含み参照しないプロパの関数を呼び出す関数も連動して振る舞いが変わる．

ティが多いと予想されることに加えてデータ量が多い

しかし，リグレッションの原因である関数は大元の呼からである．また関数呼び出しの ID 生成に使っていび出されている関数のみであると考えられる．

る関数実行前の引数の値などは値が一致するかどう

振る舞いが変わっている関数が全てリグレッション

かだけわかれば良いのでハッシュ化しデータ量を削減に関係しているとは限らない．意図した機能追加，バしている．

グ修正，リファクタリングなど，リグレッションでは

const sentenceConversion = () => {return global.tracer.wrapCallback("conversion.js:sentenceConversion", this, () => {const words = ['かん', 'が', 'いい'];3
4
return words.map(word => {5
return wordConversion(word);6}).join("");7})();
8 };
12

図3

1

トレース用関数を挿入したソースコード

sentenceConversion('かんがいい');1{"id":"d56b:dca6:6853:----","functionName":"conversion.js:wordConversion","caller":"42db:7423:4f53:----","result":"勘"

23

図4

実行コード

45
6

なくとも関数の振る舞いが変わることはある．リファ

7}

クタリングの場合は最終的な結果が変化しないので

図5

wordConversion のトレースデータ

実行したプログラムの結果が変わっていない場合はリグレッションとして扱わないと機械的に判断することが出来る．一方で意図した機能追加やバグ修正とリグ

12
3

レッションを機械的に区別することは出来ないため， 45

Bugbear はプログラムの振る舞いが変わったこととその原因だけを提示し，その変更が意図したものであるかどうかは利用者が判断する．

67891011123. 4 利用例

1314

本節では図 1 と図 2 に Bugbear を適用した例を紹

1516介する．テストコードとして図 4 を実行したとする． 17
関数の振る舞いを表す値には戻り値を使った．

1819

図 5 は図 1 の wordConversion を引数「かん」で20呼び出した際のトレース結果である．id は 3. 1 で記222123

述した方法で生成した関数呼び出しの識別子でハッ 24
シュ値の長さを 64 文字から 4 文字に省略して記述し25ている．同じ関数呼び出しであることを判定する上27で this や引数といった直接保存するとデータサイズ29が大きくなるものを利用している．それらを識別子に

26

28

{
"null": [{"id": "42db:7423:4f53:----","functionName":"conversion.js:sentenceConversion","result": "勘がいい","newResult": "勘, 缶がいい, 良い","callees": [{"id": "d56b:dca6:6853:----","functionName":"conversion.js:wordConversion","result": "勘","newResult": ["勘","缶"]},...
{"id": "d56b:dca6:f93b:----","functionName":"conversion.js:wordConversion","result": "いい","newResult": ["いい","良い"]}]}]}
図6

ツール適用結果する際にそれらをハッシュ化することで大幅にデータサイズを削減出来ている．また複数の情報を一つのid の中に保持できているので同じ関数呼び出しの検ある．result はこの関数呼び出しの戻り値である．
関数の呼び出し関係を考慮して挙動が変わったと判索が関数呼び出しの件数に対して O(1) で出来るよう定される関数は図 6 に示す通りである．結果を見るになっていることもメリットである．caller はこのと振る舞いが変わった関数は sentenceConversion

関数呼び出しを呼び出した関数呼び出しの識別子でと wordConversion であることがわかる．複数の関数の振る舞いが変わった際に大元の原因となった関数はコールグラフ中の一番深い関数であると思われる．この場合，sentenceConversion の振る舞いが変わっているのは wordConversion の振る舞いの変化に連鎖的に影響を受けたことが理由である．つまりdescribe('map.test.js', function() {it('should ~~~', function() {3var data = new Buffer([77, 116, ~~~]);
4var rv = hessian.decode(data);
5rv.should.eql({null: 'null'});~~~~~~
67});
8 });
12

wordConversion が原因でリグレッションが発生して

図7

BugID2：テストコードいると判定する．

4 実験

1AssertionError: expected Object {} to equal,→
Object {null: 'null'}

2

本節では実施した実験について述べる．

at Assertion.fail (~~~/should.js:326:17)
at Assertion.value (~~~/should.js:398:19)
5 at Context.<anonymous> (~~~/map.test.js:168:15)
6 at process.processImmediate (~~~/timers:471:21)
3
4

4. 1 実験の内容
リグレッションの原因を正しく検出できるかを実際

図8

BugID2：エラーメッセージのリグレッションを起こしているソースコードに本ツールを適用して確認した．対象とするプログラムとション，BugID9 は大きすぎる数字を number 型にエしてバグベンチマークスイートの BugsJS [5] からバンコードすると情報が欠損するため string 型で返す

グの種類がリグレッションであるものだけを抜き出し仕様にしていたが，number 型を返してしまっているて利用した．BugsJS は実際に Github で開発されたというリグレッションである．

10 の OSS プロジェクト中からバグが発生しているコ

Hessian.js には図 7 のようなテストコードが用意さミットを選びラベルをつけたものである．本実験ではれている．テストコードは統合テストに近いものでこの中の Hessian.js [1] というシリアライズツールを実行するとテストが失敗し図 8 のエラーメッセージ対象とした．Hessian.js はデータを Hessian という形が表示される．このエラーメッセージからはどういっ式のバイナリ・ウェブサービス・プロトコルにシリアた条件でリグレッションが発生するかまではわかってライズする．

も，どの関数が原因であるかを判断するのは難しいだ

BugsJS はリグレッションに特化したものではないろう．

ため，我々はバグの中からリグレッションであるものだけを抽出した．バグを引き起こす前後のコミットで4. 2 実験の結果はプログラムが正しく動いている場合，リグレッショ本ツールを用いると 2 つのリグレッションについンであると判定する．バグを修正した後のコミットでてリグレッションの原因を正しく絞り込むことができ作られたバグが直ったことを確認するためのテストた．BugID2 では変更されたファイルが 25 個で書きを使い，プログラムが正しく動くかを判定する．バグ

換えられた関数は 4 つ，振る舞いが変わった関数は 2を引き起こすコミットより前のコミットにそのテストつ，という中から原因となっている関数を見つけるこを適用してテストが成功していた場合，そのバグはとができた．BugID8 では変更されたファイルが 7 個

過去動いていたコードがバグにより動かなくなった，で書き換えられた関数は 3 つ，振る舞いが変わった

つまりリグレッションと判定する．

関数は 3 つ，という中から原因となっている関数を

Hessian.js には 9 つのバグケースがあったがそのう見つけることができた．このことからプログラムの変

ち表 1 の 2 つがリグレッションであった．どちらのバ更が複数箇所で起きている場合でも機械的にリグレッ

グも if 文の条件式を変更することで修正されている．

ションの原因を見つけることが出来たと言える．またBugID2 は機能追加に伴いデータの key が null だっ

リグレッションを直したコミットで変更された関数はた時の挙動が後方互換性を失っているというリグレッ

本ツールが提示した関数と同じであった．本ツールが

BugID変更されたファイル

書き換えられた関数

振る舞いが変わった関数

追加行数

削除された行数

225

42187

8787332714

表1

リグレッションの実験ケース提示する関数は実際の修正に役立つ情報であると考ションの原因を絞り込んでいる．これは呼び出されるえられる．

側が呼び出した側に振る舞いの変化が連鎖することはあっても逆は起きないと考えているからである．今5 関連研究後はこの仮説の再評価を行う．

テストを自動で行うことを目的としてテストケース自動生成の研究が行われている．例として Evosuite

参 考 文 献[4] は高いカバレッジのテストコードを生成し現在の[1] : hessian.js. https://github.com/node-modules/hessian.js.
[2] : this - JavaScript — MDN. https://developer.mozilla.org/ja/docs/Web/J[3] : Time Travel Debugging - 概 要 - Windows
drivers. https://docs.microsoft.com/ja-jp/windowshardware/drivers/debugger/time-travel-debugging-overview.
[4] Fraser, G. and Arcuri, A.: EvoSuite: Automatic
Test Suite Generation for Object-Oriented Software,
Proceedings of the 19th ACM SIGSOFT Symposium and the 13th European Conference on Foundations of Software Engineering, ESEC/FSE ’11,
New York, NY, USA, Association for Computing
Machinery, 2011, pp. 416–419.
[5] Gyimesi, P., Vancsics, B., Stocco, A., Mazinanian, D., Beszédes, c., Ferenc, R., and Mesbah, A.:
BugsJS: a Benchmark of JavaScript Bugs, 2019 12th
IEEE Conference on Software Testing, Validation
and Veriﬁcation (ICST), 2019, pp. 90–101.

振る舞いの記述と将来の不具合の検出が出来る．本研
究もテストを自動化するが，テストケース自動生成と比較するとバグの原因の特定までを自動化しようとしている点で異なる．
プログラムを実行した際の履歴を保存してデバッグに活用する研究として Time Travel Debugging(TTD) が挙げられる．TTD は実行中のプロセスの実行を全て記録し，後で実行を再現できるようにするツールである [3]．TTD はデバッグを支援するもので原因の特定自体はユーザーが行うが，本研究はツールが原因を特定することを狙っている．

6 まとめと今後の課題
本論文では過去と現在のプロジェクトのテストコードの実行履歴を比較してリグレッションが発生した原因となる関数を提案する手法について述べた．
今後は実験ケースを充実させること，Bugbear の出力を利用者に分かりやすくすること，仮説の検証を行う予定である．実験ケースについては対象とするバグケースを増やし検出精度の指標を用意して定量的な評価を行う．また出力については現在はリグレッションの原因の候補を json 形式で出力しているが，利用者がみた時にわかりやすいような形式で出力する．例えば同じ関数で振る舞いが変わった関数呼び出しは引数と出力を整理して提示するなどの工夫が考えられる．また本研究では複数の関数の振る舞いが変わった時，コールグラフ中の一番深いところにある関数が大元の原因であるという仮説の元でリグレッ