ソフトウェアテストシンポジウム 2004
JaSST’04: Japan Symposium on Software Testing 2004

ミューテーションスコアを利用した
テストセット評価システム
斉藤孝志†

粕谷英人††

大久保弘崇††

山本晋一郎††† 愛知県立大学大学院 情報科学研究科 〒 480-1198 愛知県愛知郡長久手町大字熊張茨ヶ廻間 1522-3
E-mail: †saito@yamamoto.ist.aichi-pu.ac.jp, ††{kasuya,ohkubo,yamamoto}@ist.aichi-pu.ac.jp
あらましソフトウェアの信頼性を向上させるために，テストセットの品質を高めることは重要である．本稿では，テストセットの品質を測定するために，ミューテーションスコアを用いた方法を提案する．ミューテーションスコアを測定するシステムを実装して，gawk-3.0.1 と gzip-1.2.4 に含まれるテストセットに適用した．gawk-3.0.1 のミューテーションスコアは 36%であり，gzip-1.2.4 のミューテーションスコアは 21%であった．
キーワード

ミュータント，ミューテーションスコア，テストセット

The test set evaluation system which used mutation score
Takashi SAITO† , Hideto KASUYA†† , Hirotaka OHKUBO†† , and Shinichiro YAMAMOTO††† Graduate School of Information Science and Technology, Aichi Prefectural University 1522-3,
Ibaragabasama, Kumabari, Nagakute-cho, Aichi-gun, Aichi, 480-1198, Japan
E-mail: †saito@yamamoto.ist.aichi-pu.ac.jp, ††{kasuya,ohkubo,yamamoto}@ist.aichi-pu.ac.jp
Abstract To make software reliable, it is important to raise the quality of a test set. In this paper, we propose
a method uses the mutation score in order to measure the quality of a test set. We applied our experimental
implimentation to the test sets included in gawk-3.0.1 and gzip-1.2.4 distributions. Their mutation scores are 36%
and 21%, respectively.
Key words mutant, mutation score, test set

1. は じ め に
ソフトウェアのライフサイクルは，開発段階と製品段階の 2つの段階に大きく分けることができる．開発段階には要求分析，言語のプログラムを対象としたテストセットの品質を測定するシステムを提案する．このシステムは，プログラムとそのプログラムに対するテストセットを入力とし，テストセットの品質を測定する．

仕様書の作成，設計，コーディング，テスト等の作業があり，製本システムは 2 つの部分から成り立っている．1 つは，文品段階では保守・運営の作業がある．このソフトウェアのライ

献 [2] で提案されているミューテーション解析の考えを基に，元フサイクルで最も多くのコストを占めているのは，製品段階でのプログラムに混入させる誤りを生成するシステム (以下ミューの保守・運営である．次いで，開発段階で大部分を占めているタント生成システム) である．もう 1 つは，ミュータント生成製品のテストである．テストの役割は，安定したソフトウェアシステムで生成したミュータントをオリジナルプログラムに混をユーザに提供するためにプログラムのバグを発見することで入させて，オリジナルプログラムが持っているテストセットである．しかし，プログラム中に存在する全てのバグを発見するテストするシステムである．この 2 つのシステムを用いて，テことは不可能である．そこで，できるだけ多くのバグを発見すストセットの品質を評価するためのミューテーションスコアをるためには，入力パターンを網羅したテストセットを用いたテ測定する．

ストが有効である．すなわち，このテストセットのバグ発見能力がテストセットの品質と考えられる．テストセットの品質を2. ミューテーション解析測定するために DeMillo, Offutt らによってミューテーション

ミューテーション解析は，ソフトウェアの全体テストに使用スコアを用いる方法が提唱されている [1] [2]．文献 [1] [2] では，されるテストセットの品質を評価・改良するための技術である．

Fortran-77 を対象としている．

また，ミューテーション解析は，ある考えに準じたホワイトボッ

本稿では，今日のソフトウェア開発で広く用いられている C

クステストの技術である．その考えとは，テストセットの品質—1—

表1が，オリジナルプログラムとわずかに異なった誤りを含んでいミューテーションタイプ

Typeる代替プログラムとオリジナルプログラムとを区別する能力とarray for array replacement

関連しているということである．

scalar for array replacement

2. 1 ミューテーション解析のプロセス

absolute value insertion

テスト対象のプログラムを P ，P についてのテストセットを

scalar for constant replacement

T とし，以下にそのプロセスを示す．

array constant replacement（ 1 ） P を T でテストする．

scalar variable replacement

このテストで T 中の全てのテストケースに対して 1 つでもarithmetic operator replacement

意図しない結果を出力するなら，P あるいは T は即座に修正

constant replacementする必要がある．この場合，T はプログラム中のバグを検出す

array for variable replacement
data statement alterationsるという義務を果たしたことになる．

constant for array replacement（ 2 ） プログラム P の代替プログラム Pi (i = 1, 2, … ) を生

goto label replacement

成する．

comparable array replacement

Pi は，P のステートメントの一ヶ所を変更して生成する．例

return statement replacement

えば，a = b + c の式を a = b + d という具合に変更する．Pi

constant for scalar replacementの数は変更個数に応じて決まる．元のプログラム P の一ヶ所をstatement analysis

変更して作られた代替プログラム Pi のことを P のミュータン

DO statement end replacement
statement deletion

トプログラムと呼び，特に変更したステートメントをミュータ

logical connector replacement

ントと呼ぶ．また，オリジナルステートメントを変更すること

source constant replacement

をミューテーションと呼ぶ．

relational operator replacement（ 3 ） 全てのミュータントプログラム Pi を T でテストする．

unary operator insertion

T のあるテストケースでテストしたとき，ミュータントプロ
グラム Pi がオリジナルプログラム P と異なる結果を出すなら

1

int Max(int m, int n)ば，このテストケースは Pi のミュータントを摘出したという．

2{（ 4 ） ミューテーションスコアを測定する．

3(2) で生成したミュータントの個数 M と，(3) で摘出されたミュータントの個数 K からミューテーションスコア M S を以下のように定義する．

KMS =× 100
Mint max;

45max = m;

6if (n > m)7[%]

max = n;8(1)9

2. 1. 1 ミューテーションタイプ

return max;}
図1

関 数 Max

ソースプログラムのステートメントの変更，すなわちミューテーションには様々な方法がある．表 1 に Fortran-77 を対象としたミューテーションタイプの一覧 [3] を示す．

ここで，関数 Max をテストケース : (m = 2, n = 1) でテストする．この時，関数 Max の結果は m と n の最大値であ

この様々なタイプのミューテーションを利用して，P から複る 2 を返す．これに対して，ミュータント : max = n を含む数のミュータントプログラム Pi を作成する．20 行からなる単ミュータントプログラムを Max1 とし，Max1 をテストケース :純なプログラムからでも約 400 個ものミュータントプログラ(m = 2, n = 1) でテストする．この結果として Max1 は 1 を返ムを生成することができる．ミュータントプログラムの個数はすが，これはオリジナルプログラムの結果とは異なる．よって，ミューテーションを行う場所が多いほど増えていく．

テストケース : (m = 2, n = 1) はミュータント : max = n を

2. 1. 2 ミュータントの摘出摘出したということになる．もしプログラマが 5 行目で max = m

あるテストケースがミュータントを摘出するということは，と書くつもりが max = n と誤って書いても，テストセットにそのテストケースがミュータントが表すバグを発見できること(m = 2, n = 1) のテストケースを含んでいれば，テストの段を意味している．

階でこのバグを摘出できる．

図 1 の関数 Max を使ってミュータントを摘出する例を示す．
関数 Max は 2 つの int 型の入力からその最大値を返すものである．
関数 Max から生成されたミュータントの一例を表 2 に示す．

表2関数 Max から生成されたミュータント

line original

max = m max = n7n > mmax = abs(m)ミュータント max = n は，5 行目の式 max = m の右辺 m を nに変更したものである．また，他のミュータントも式の一ヶ所を変更して生成されたものである．

mutant5n < mn >= m—2—また，ミュータント : n >= m を含むミュータントプログラ
ムについて考えてみる．このミュータントプログラムを Max2とする．Max2 にどのようなテストケースを入力しても，Max と異なる結果を出力しない．これは，Max2 が max と関数的に同一の効果を持っているためである．このようなミュータントのことを等価ミュータントと呼ぶ．等価ミュータントを含むミュータントプログラムからミュータントを摘出するテストケースは存在しない．そのため，等価ミュータントは人手によって摘出する．

2. 1. 3 ミューテーションスコア
ミューテーションスコアはテストセットの品質の指標である．プログラム P から生成されたミュータントの数と，テストセット T で摘出することができたミュータントの数からミューテーションスコアを測定する．今，P と T に対して，生成した

図 2 Sapid の概略

ミュータントの総数を M ，摘出されたミュータントの数を K ，等価ミュータントの数を E として，ミューテーションスコアDatabase)，アクセスルーチン (AR : Access Routines) から構

M S(P, T ) を，以下に定義する．

成される．

K
M S(P, T ) =× 100
M −E

[%]

(2)

等価ミュータントを摘出するテストケースは存在しないので，ミューテーションスコアを測定する際，等価ミュータントの数は考えないものとする．

3. ミュータント生成システム
本稿では，オリジナルプログラムに含ませる誤りとなるミュータントを生成する．

• SDB は Sapid の基盤であり，要求されたソフトウェアをソフトウェアモデルに基づいて解析する解析器と解析の結果得られた実体・関連情報を格納するデータベースからなる．

• AR は，SDB のデータにアクセスするための C 言語のAPI である．
図 2 に Sapid の概略を示す．本システムでは，SDB に格納されている前処理された C 言語ソースプログラムに対するソフトウェアモデルからミュータントを生成する．

3. 2 本システムで扱うミューテーションタイプ

ミュータントの生成は，プログラム作成者が間違えやすいと本システムでミューテーションの対象となるのは，代入式思われる部分を想定する．本システムで対象とする言語は C 言の右辺の算術式と，if 文の条件式の算術式である．while 文，語である．そこで本システムでは，C 言語のプログラムで使用

do-while 文，for 文などの繰り返し文の条件式からミュータン頻度の高い算術演算子，関係演算子，等値演算子を含んだ算術トを生成すると，無限ループに陥ってしまう可能性が高くなっ式からミュータントを生成する．てしまうので，現段階の本システムではこれらの条件式を対象

ミュータント生成システムはオリジナルプログラムを入力ととしていない．

して，ミューテーションの対象となる式を取得して，ミュータ以下に本システムで扱うミューテーションタイプを示す．

ントを生成する．全体の流れを，以下に示す．

• 変数を他の変数に置き換える．

（ 1 ） ソースプログラムの解析• 定数を他の定数に置き換える．

（ 2 ） ソースプログラム中に出現するミューテーションの対• 算術演算子を他の算術演算子に置き換える．

象となる式の取得• 関係演算子を他の関係演算子に置き換える．

（ 3 ） ミュータントの生成

式 a < b + 4 に対する各ミューテーションの例を表 3 に示

ソースプログラムの解析には，CASE ツール・プラットフォー

す．この式は変数 a, b, c のスコープ内にあるものとする．そム Sapid [4] を利用する．

れぞれのミューテーションタイプの規則，具体的方法を以下に

3. 1 Sapid
ソースプログラムの解析に利用する Sapid (Sophisticated示す．

a ) 変数置き換え VR (Variable Replacement)

APIs for CASE tool Development) [4] [5] は，細粒度ソフト

変数置き換えでは，算術式に現れる変数を他の変数に置き換

ウェア・リポジトリに基づいた CASE ツール・プラットフォー

える．置き換えられる変数の型は，算術式に多用される int 型，ムである．従来，CASE ツールや研究システムの作成者は，個float 型，double 型とする．置き換える変数は，その式からの別に解析器やリポジトリを実現しなければならなかった．しかスコープ内にある同じ型の変数とする．

し，Sapid によって CASE ツールの基礎的な機能が提供されるため，開発者は本質的な機能の実現に専念できるようになる．

Sapid は C 言語と Java を対象としている．

b ) 定数置き換え CR (Constant Replacement)
定数置き換えでは，置き換えられる定数は整数型とする．置
き換えられる定数を C とすると，置き換える定数の候補は 0,

Sapid は ，ソ フ ト ウェア デ ー タ ベ ー ス (SDB : Software—3—

表3式

タイプ

a < b + 4 VR

ミューテーション例

ミュータントb < b + 4,

c < b + 4,

a < a + 4,

a < c + 4CRa < b + 0,a < b + 5,a < b + 3

AOR

a < b - 4,a < b * 4,a < b / 4,a < b % 4
ROR

a == b + 4,a != b + 4,a > b + 4,a >= b + 4

a <= b + 4,

C + 1，C − 1 とする．例えば，元の定数が 3 であれば，置き換える候補は 0, 4, 2 である．
図3c ) 算術演算子置き換え AOR (Arithmetic Operator Replacement)
算術演算子置き換えでは，算術演算子を他の算術演算子に置き換える．ここでの算術演算子は+, -, *, /, %とする．例えば，置き換えられる演算子が+であれば，-, *, /, %に置き換える．

d ) 関係演算子置き換え ROR (Relational Operator Replacement)
関係演算子の置き換えでは，関係演算子を他の関係演算子で置き換える．ここでの関係演算子は，>, >=, <, <=, ==, !=とする．例えば，置き換えられる演算子が>であれば，>=, <, <=, ==,!=に置き換える．
3. 3 ミュータント生成システムの実現
本システムで生成されるミュータントは，オリジナルプログラムの一ヶ所を変更したものである．複数ヶ所を同時に変更したミュータントは生成しない．これは複数の変更を含んだミュータントから生成されるミュータントプログラムのテスト時に，そのミュータントが摘出される可能性が高くなるからで

ミュータント生成システムの expr は本システムで対象となる式を表し，expri は expr から各ミューテーションを行った結果生成されるミュータントを表す．

4. ミュータントプログラムテストシステム
4. 1 概要

ミュータント生成システムで生成したミュータントからミュータントプログラムを生成して，対象プログラムのテストセットでテストを行う．そして，テストセットの品質の評価するためのミューテーションスコアを測定する．

4. 2 システムの実現
本システムは，ミューテーションスコアを測定するために 2つのフェーズから成り立つ．また，本システムはシェルスクリ
プトで実装されており，200 行程度のものである．

a ) ミュータントプログラムの生成ある．例えば，テストセットがミュータント M1 を摘出できる

3 節のミュータント生成システムで生成されたミュータントが，ミュータント M2 は摘出できない場合，ミュータント M1 とを spdSed を使用してミュータントを含んだソースプログラム

ミュータント M2 を同時に含むミュータントプログラムからそを生成する．spdSed は Sapid アプリケーションで，ファイルのミュータントを摘出できる可能性がある．しかし，そのテスを編集コマンド群に従って編集するストリームエディタである．

トセットではミュータント M2 だけを含むミュータントプログ

そして，ミュータントを含んだソースプログラムをコンパイル

ラムは摘出できない．プログラマが複数の間違いを同時にするすることによりミュータントプログラムを生成する．

場合があっても，そのうちのそれぞれの間違いを発見できるテb ) ミュータントプログラムのテスト

ストセットがあれば，プログラマに間違いを気付かせることがミュータントプログラムを対象プログラムのテストセットでできると考えられる．

テストする．ミュータントプログラムと元のプログラムの各テ

本システムは C 言語で作成しており，トータルで 1417 行でストケースでのテスト結果を比較して，ミュータントが摘出さある．対象となるオリジナルプログラムからミュータント生成れたかどうかを調べる．ミュータントプログラムのテスト時にシステムを使用して，ミュータントを生成する手順を以下に余計に時間がかかってしまうことがある．この場合，正常値の示す．

テスト時にかかる時間の 2 倍以上の時間がかかったものは，強1. 解析対象プログラムを SDB へ格納．

制的にそのテストを打ち切るようにした．このことについては，

2. SDB に格納されたプログラムからミューテーションの4.4 の考察で詳しく述べる．

対象となる式の取得．

3. 取得した式に変数置き換え，定数置き換え，算術演算子置き換え，関係演算子置き換えのうち可能なミューテーションを行う．

4. 2, 3 を繰り返す．
図 3 にミュータント生成システムの概略図を提示する．図中

本システムではミュータントの摘出を以下の場合とする．

• オリジナルプログラムのテスト結果と異なる．
• テスト時間がオリジナルプログラムのテスト時間に比べて 2 倍以上かかる．
以上のフェーズを生成されたミュータントの数だけ繰り返す．
全てのミュータントプログラムに対するテストが終了した時—4—コアは 36%，21%であった．

表 4 gawk-3.0.1, gzip-1.2.4 のプログラムの概要

gawk-3.0.1 gzip-1.2.4
ファイル数 (.c)

19

ファイル数 (.h)

10623,638

8,163

サイズ [KB]

896304

テストセットの数

402

行数

本システムではミュータントプログラムのテスト時間がオリ

14

ジナルプログラムのテスト時間の 2 倍以上かかるものについては強制的にそのテストを打ち切っている．gzip-1.2.4 の正常値のテスト時間は約 0.15s であった．そこで，ミュータントプログラムのテスト時間を 0.15s から 0.15s の 3 倍となる 0.45s まで 0.03s ずつ増やして，摘出できるミュータントについて調べてみた．その結果，打ち切り時間を 0.15s とした場合に摘出さ

表 5 gawk-3.0.1, gzip-1.2.4 のミューテーションスコア

gawk-3.0.1 gzip-1.2.4

れるミュータントの数は打ち切り時間を増やしても変化するこ

8,569

3,036

コンパイル失敗928

33

摘出したミュータント

2,718

627

2,490

615

228

12が多く生成された場合，摘出できるミュータントの数が多くな

ミューテーションスコア

35.6%20.9%る可能性が高くなり，ミューテーションスコアが高くなる．こSDB 生成時間の場合，テストケースの品質がいいものだとは一概に言えない．

生成されたミュータント

結果が異なる
強制終了とはなかった．
ミューテーションスコアは，摘出できるミュータントの数が多ければ高くなる．明らかに間違っているようなミュータント

5m12s

56s

ミュータント生成時間

56s

10s

ミュータントは，多くのプログラマが間違えやすい形になっ正常値のテスト時間

2.5s

0.15s

てるのが理想的である．よって，ミューテーションもそのよう

686m2s

91m38s

テスト時間なミュータントを生成できる規則になっているものが望ましいと考えられる．に，生成されたミュータントの総数，摘出されたミュータントの数からミューテーションスコアを計算する．ミュータントプ

5. お わ り にログラムがコンパイル時にエラーを出力する場合がある．この

本稿では，オープンソースプログラムのテストセットの品質

とき，このミュータントはミューテーションスコアを測定するを評価する手助けとなるミューテーションスコアを測定するシ際には考えない．また，正確なミューテーションスコアを測定すステムを提案した．ミューテーションスコアを測定するために，るためには等価ミュータントの数も必要となる．しかし，ミュー

次の 2 つのシステムを作成した．

タントが等価か否かは人手でなければ判断できないので現段階• ミュータント生成システムの本システムでは考えないものとする．すなわち，プログラム• ミュータントプログラムテストシステム

P のテストセット T のミューテーションスコア M S(P, T ) のこれらによって，gawk-3.0.1 と gzip-1.2.4 のテストセットの計算方法を以下に示す．

ミューテーションスコアを測定した．この測定値から，ユーザ

M S(P, T ) =K
× 100
M −C

[%]

(3)

がテストセットに改良を加える必要があるかどうかを判断する手助けになる．

生成したミュータントの数を M ，摘出されたミュータントの

しかし，現在はミューテーションスコアを測定するだけであ

数 K ，コンパイル時にエラーとなるミュータントの数を C とる．今後，ミューテーションタイプを拡張して，多くのプログする．

ラマが犯しやすい間違いを想定したミュータントを生成できる

4. 3 ミュータントプログラムテストシステムの実行結果ようにしたい．また，gawk-3.0.1, gzip-1.2.4 以外のオープン

gawk-3.0.1, gzip-1.2.4 に本システムを適用した．それぞれのソースプログラムのテストセットのミューテーションスコアをプログラムの概要を表 4 に示す．
それぞれのテストは，Makefile に記載されたテストの規則に従い行ったものである．以下の動作環境で gawk-3.0.1, gzip-1.2.4のテストセットのミューテーションスコアを測定した．

OS: Vine Linux 2.5

CPU: Pentium III 800MHz

メモリ : 128 MB
結果を表 5 に示す．表中の正常値のテスト時間については，オリジナルプログラムを 50 回テストしたうちの最大時間である．
また，テスト時間は全てのミュータントプログラムのテストに要した時間である．

4. 4 考察今回，gawk-3.0.1 と gzip-1.2.4 のテストセットについてミューテーションスコアを測定した．それぞれのミューテーションス測定して，ミューテーションスコアの基準値を求めていきたい．

謝辞

御指導頂く，名古屋大学大学院情報科学研究科 阿草清滋教授，愛知県立大学情報科学部 稲垣康善教授に感謝します．
文

献[1] Richard A.DeMillo and A.Jefferson Offutt. “ExperimentalResults from an Automatic Test Case Generator.” ACM
Transaction on Software Engineering Methodology, Vol2,
pp.109-175, April 1993.
[2] Roland Untch, A.Jefferson Offutt, and Mary Jean Harrold.
“Mutation Analysis Using Mutant Schemata.” ACM International Symposium on Software Testing and Analysis,
pp.139-148, June 1993.
[3] Richard A.DeMillo and A.Jefferson Offutt. “Constraintbased automatic test data generation.” IEEE Transactions
on Software Engineering, 17(9), pp.900-910, September,—5—

1991.
[4] “Sapid” URL: http://www.sapid.org/[5] 福安 直樹, 山本 晋一郎, 阿草 清滋. “細粒度ソフトウェア・リポ
ジトリに基づいた CASE ツール・プラットフォーム Sapid.” 情報処理学会論文誌, Vol.39, No.6, pp.1990–1998 (1998/6)—6—