ソフトウェア・シンポジウム 2015 in 和歌山

報酬構造を考慮したテストケース生成と信頼性評価の効率性
小澤 公貴
広島大学 大学院工学研究科
ozawa@s.rel.hiroshima-u.ac.jp

土肥 正
広島大学 大学院工学研究院
dohi@rel.hiroshima-u.ac.jp

要旨

断基準を持たずにプログラムを実行するだけでは入出力の正誤判定が行えないため，ソフトウェアへの入力と正

本稿では, マルコフ使用モデル (Markov Usage Model)

しい期待出力の組から構成されるテストケースを投入すとシステムの運用プロファイル (Operational Profile) にることで入出力の正誤判定を行う. 特別に大規模なソフ基づいてテストケースを自動生成するための統計的方法

トウェアでなくても, この入出力関係を規定する組合わについて考察する. 特にソフトウェアの設計情報を報酬せ数は膨大となり, ソフトウェアの全ての実行パスを網構造として導入することでマルコフ報酬過程を定義し,羅するテストケースを生成することは現実的に不可能でソフトウェアテストの効率化とソフトウェアの信頼性評ある．よって動的テストでは，テストケースの効率的な価尺度の算出を行う．最終的に, 実際のソフトウェアプ

自動生成が重要な問題となっている.

ログラムにフォールトを埋め込んでテスト実験を行った

動的テストは，さらにホワイトボックステストとブラッ

結果，ソフトウェアメトリクスを報酬として与えたテス

クボックステストに大別される．ホワイトボックステス

トケース生成アルゴリズムは, 従来の報酬なしのアルゴ

トとは，プログラムの内部構造を理解した上で，それらリズムと比較して数多くのフォールトを検出でき，しか一つ一つが意図した通りに動作しているかを検証するテも規定の信頼度に達する為に必要とされるテストケース

スト技法である．ホワイトボックステストにおけるテス数を効率的に削減できることが示される．

トケースは，命令の網羅性や判定条件の網羅性などの内部構造を注意深く検査しながら設計されるため, テスト
ケースの生成には非常にコストがかかる．一方, ブラッ

1. はじめにクボックステストはプログラムの内部構造には着目せず，与えられた入力に対して正しい出力がなされたかどうか

ソフトウェア開発は主に,「要件定義」,「基本設計」,の確認のみを行うテスト技法である．ブラックボックス「詳細設計」「コーディング」,「テスト」の各工程から構テストに基づいたテストケースは，同値分割や限界値分成されている. ソフトウェアテストはテスト工程で行わ析を通じて, 入力データを考慮しながら設計される．

れ，ソフトウェア内に潜在するフォールトの発見・除去

ブラックボックステストの興味深い研究テーマとして,を通じて，要求される機能を満たしているかどうかを確

設計情報をテストケース生成に活用するモデルベーステ

認する．よって，テスト工程は製品の信頼性・品質を保スト (Model-based Test; MBT) が挙げられる. これは,証するために必要不可欠であり, 他の工程と比較して最テスト対象となるソフトウェアの振る舞いや機能を抽象も多くのコストがかかることが知られている. 特に, 大的モデルを用いて表現し，モデル上で表現されたソフト

規模・複雑化するソフトウェア開発の現状において，よ

ウェア・アーキテクチャの情報をテストケース生成に利り安価でかつ効果的なテストを実施することでテストの用するものである．このような形式的モデルを用いるこ質を向上させることが要求されている.

との利点として, 設計されたテストケースがモデル上で一般に, プログラムを実際に実行するテストを動的テ規定された各状態や遷移をどれだけ網羅できたのかを明ストと呼び，コードレビューのように実行を伴わないテ

確にすることが挙げられる．形式的モデルの例として,

ストを静的テストと呼ぶ．動的テストを行う際，何も判

99

SEA

ソフトウェア・シンポジウム 2015 in 和歌山

UML (Unified Modeling Laungage) などの設計記述言語を用いるものや, 木構造や有限状態機械 [3],[5] などのグラフモデルを利用するもの, マルコフ連鎖 [16], [17] やウェア障害が発生しない確率であるソフトウェア信頼度

確率オートマトンなどの確率モデルを用いるものが代表を, テストケースの投入履歴から統計的に推論すること

的である.

ができる.

意回数実行中に障害に至る確率を推定する方法について議論している. これより, プログラムの実行中にソフト

確率モデルを用いたテストケース生成について，今富

以上の統計的テストケース自動生成法を踏まえ，今富ら [7] は，MBT の一種でありソフトウェアの運用プロら [7] は，従来までの多くの研究ではプログラムの振る

ファイル（Operational Profile）を用いてテストケース

舞いを表現するためにモデルの表現能力の向上だけに注を生成する運用プロファイルベーステスト (Operational

力しており, ソフトウェアの設計情報や各モジュールを

Profile-based Test; OPBT) に着目した．MBT がテス構成するソースコードの定量的性質に着目していないこ

ト網羅性のみを志向してテストケースを設計するのに対とを指摘した．そこで，パフォーマビリティ [12] もしし，OPBT では運用プロファイルを用いることにより

くは報酬過程の概念を導入することで, より集中してテテスト網羅性とユーザの使用環境を同時に考慮してテスストを行うべきモジュールをソフトウェアメトリクスにトケースを設計する．本稿では，今富ら [7] の方法を拡よって特徴づけた上で，テストケースの効率的な生成方張し，規定のソフトウェア信頼度に到達したらテストを法を提案している．最近 Avritzer ら [2] は, この報酬打ち切る方策の下で，報酬構造を考慮したテストケース

過程の概念を導入し，実在するミッションクリティカル

生成法の有効性を評価する．

なシステムに対するテストケースの自動生成問題を取扱
い，ソフトウェア信頼度の推定問題を考察している.

2. 関連研究

一方で, Avritzer ら [2] の論文は連続時間マルコフ連
鎖 (Continuous-time Markov Chain; CTMC) の過渡解テストケース生成法に関する従来研究として，Whit-

析の結果を用いており, 連続時間で駆動するシステムにtaker and Thomason [17] により提案され, 後に Avritzer
and Weyuker [1], Gutjahr [6], Kallepalli and Tian [8],対するテストケース生成と信頼度推定に主眼を置いてい

Poore ら [13], Whittaker ら [18] によって精緻化された
マルコフ連鎖に基づく統計的テストケース自動生成法がな離散時間マルコフ連鎖 (Discrete-time Markov Chain;ある．これは，ソフトウェアの機能や構造に着目した振示的に述べていなかった報酬の決め方について実証的なる舞いを確率モデルによって表現し, それをシミュレー

アプローチを展開している．すなわち，ソフトウェアのトすることでテストケースの自動生成を可能にしている.

各モジュールを構成するプログラムを, ソフトウェア設計プログラムの挙動をモデル化するための表現能力に関しメトリクスを用いて報酬の形で与えることを提案していて, 有限状態機械 [3],[5] やマルコフ性を持たないより一る．これにより, プログラムの振る舞いを表す形式モデ

般的な確率モデル [4] など他にも優れた方法が存在する

ルは離散時間マルコフ報酬過程 (Discrete-time Markov

が, パラメータの物理的性質の同定や統計的推論の簡便性から, マルコフ連鎖に基づく方法は最も汎用性が高い

Reward Process; DTMRP) として表現される．
本稿では今富ら [7] の手法をもとに，単にテストケーと言える.

スを生成するだけでなく，ソフトウェア信頼度の定量的る．今富ら [7] はテスト工程においてより取扱いの簡便

DTMC) を仮定し, さらに Avritzer ら [2] が論文中に明テストケースの自動生成とは離れて, マルコフ連鎖にな推定も併せて行う．最終的に, 実際のソフトウェアプ

基づく統計的方法では, テストケース投入後のフォールト

ログラムにフォールトを埋め込んでテスト実験を行った検出に関する実績データからソフトウェアの信頼性を定結果, ソフトウェアメトリクスを報酬として与えたテス

量的に評価できることが特徴として挙げられる. Avritzer

トケース生成アルゴリズムは，従来の報酬なしのアルゴ

and Weyuker [1], Gutjahr [6], Kallepalli and Tian [8],Prowell and Poore [14], Weyuker [15], Whittaker ら

リズムと比較して数多くのフォールトを検出でき，しか[18] はプログラムの振る舞いを表すマルコフ連鎖の状態
推移図に故障状態を導入し, テストケース実行中にフォールトが検出される確率を推定し, さらにプログラムを任ス数を効率的に削減できることを示す．

も規定の信頼度に達するために必要とされるテストケー

100

SEA

ソフトウェア・シンポジウム 2015 in 和歌山

図 1 に, 有限状態機械によって表現されたソフトウェ
アの振る舞い図の例を示す．ここで, 図中のノードはソフトウェア機能の種類を表す状態を意味し，アークは状態間の遷移をそれぞれ表している．各遷移に付加された

event は遷移の発火条件を表し，黒丸は実行開始状態，
二重丸は実行終了状態をそれぞれ表す．図中のアーク上に割当てられた数値は状態推移確率を表しており, 例えば “State2” に対応するソフトウェア機能を実行した後,確率 50% で “event e” が生じるとプロセスの実行は終了し, 確率 50% で “event c” が生じると状態は “State3”に移行し, さらに 100% の確率で状態は “State1” に移る. テストケースの生成は, この状態機械を実行（シミュレート）することで実現される. すなわち, 実行開始状態
から実行終了状態に至るサンプルパスをモンテカルロ・
シミュレーションを通じて生成し, 各テストケースを構成する入出力値を定める.

4. マルコフ報酬過程
図 1. 有限状態機械によるモデル表現の一例．

4.1. 離散時間マルコフ連鎖
本論文では, 有限状態機械のサブクラスである DTMC

3. 運用プロファイルベーステストを用いる. 状態の表現能力に関してはオートマトンなど

運用プロファイルとは, 開発対象であるソフトウェア

他にも有力な有限状態機械が存在するが, マルコフ連鎖

が実際の運用環境においてどのように使用されるかを規を用いる利点としてモデルパラメータの物理的意味が明定した仕様であり, ソフトウェアの各機能や命令を使用

確であり，かつ実際のデータからパラメータを統計的にする頻度を予め想定することでユーザの運用環境を予測推定することが容易である点が挙げられる. また, ソフ

するために用いられる. Musa [10], [11] は, ソフトウェトウェア信頼度に代表される信頼性評価尺度を算出する

アの各機能の使用確率を要求仕様段階において仮定する

ためには, 必然的に解析的取扱いが可能な確率過程を適ことで, ユーザの運用環境を考慮した設計, テスト, 検用する必要がある.
今, 離散時刻 n = 0, 1, 2, · · · において非負値状態空間

証を行うべきであることを主張している. 運用プロファ
イルの定量的な取扱いでは, ソフトウェアにおける各機上で値をとる確率過程 {X(n), n = 0, 1, 2, · · · } を考え

能の使用確率 (Usage Probability) を過去のバージョン

る．任意の状態 i, j, in に対して，の使用履歴や類似ソフトウェアの開発データから推定し

P {X(n + 1) = j | X(0) = i0 , X(1) = i1 , · · · ,X(n − 1) = in−1 , X(n) = i}たり，ユーザの使用振る舞いを開発者が主観的に見積もることにより割当てられる．この使用確率は有限状態機= P {X(n + 1) = j | X(n) = i} = pij

械の推移確率に対応しており, 運用プロファイルを規定することで形式的モデルの振る舞いが定量的に表現できのような関係が成立するならば, X(n) はマルコフ性をる. 運用プロファイルを MBT に適用するテストである

有し, DTMC に従うと言う. ここで状態 i から状態 j

OPBT は, 従来の MBT で作成したモデルに対して, 運に推移する条件付き確率 pi,j は推移率と呼ばれる．図 1

用プロファイルから各状態の遷移確率を付加することでの実行開始状態を除いた 4 つの状態の内，実行終了状態

ユーザの運用環境を記述した動的モデルであると解釈でのようにこれ以上推移が起こらない状態を吸収状態, 以きる．

降も推移可能な状態を過渡状態と呼ぶ. 過渡状態の数が

101

SEA

ソフトウェア・シンポジウム 2015 in 和歌山

フトウェアには m 個の機能が備わっており, フォールトが全く含まれていない場合には, 1 回のテスト実行で状
態 1 から任意の過渡状態を経由して実行終了状態である吸収状態に至る. もし各機能を実現するモジュールに
フォールトが潜在的に含まれるならば, 各状態からもうひとつの吸収状態である “Failure” 状態に推移が発生する. 図 2 は m = 3, l = 2 の場合の DTMC の推移図の例を表している．OPBT においてテストケースを生成する場合, 図 1 のようにフォールトの検出を想定することなく, 実行開始状態から実行終了状態までの経路をシミュレートし, 各機能が順に実行される遷移系列を求める. 求められた遷移系列の入力値と期待出力値を予め用意することで, 当該テストケースによる正誤判定を行う
ことができる. 十分なテストケースが投入された後, 図 2の過渡状態 j への累積訪問回数を sj (j = 1, 2, · · · , m),
各過渡状態においてフォールトが検出された回数を fjとすれば, モジュール j の信頼度は

Rj = 1 − (fj /sj )(5)

図 2. 障害状態を追加したモデル表現．
によって求められる. よって, 任意回数のテスト実行でフォールトが検出されることなく終了する確率であるソm で吸収状態の数が l の DTMC において, 推移確率行
列を
(
)
Q C
P=
(1)
O I

フトウェア信頼度を, 基本行列の要素から容易に算出することができる. これにより, DTMC を用いてテストケースの自動生成とソフトウェア信頼度の推定を同時に行うことが可能となる.

によって定義する. ここで, Q, C は, 過渡状態から過渡

4.2. マルコフ報酬過程とソフトウェアメトリクス

状態への推移と, 過渡状態から吸収状態への推移を表す
部分行列であり, O, I はそれぞれ零行列と単位行列を表先に述べた DTMC に基づいた OPBT の問題点とししている. よく知られた DTMC の結果より, DTMC のて, 仕様の段階で類推される運用プロファイル（DTMCn ステップ推移確率行列は
(
(n)

P

n

=P =

Qn
O

Cn
I

)

における過渡状態間の推移確率）を予め正確に知ることが困難である点が挙げられる. 一般に, 不特定多数のユー(2)

ザがどの機能をどのような頻度で使用するかを正確に予測することは容易でなく, 運用プロファイルを利用したによって与えられる. ここで部分行列 Cn は定量化技術にも自ずから限界がある. また, 運用プロファ

Cn = (I + Q + · · · + Qn−1 )C

イルはあくまでユーザの動作環境を想定したものであり,(3)

ユーザによるソフトウェアの使用環境を正確にモデル化となる. Q は列ベクトルの総和が 1 となる非負値行列できたとしても, 必ずしも潜在するフォールトが多数検であり,出されるテストケースを生成できる保証はない. 換言す

lim {I + Q + Q + · · · + Q
2

n→∞

n−1

−1

} = (I − Q)
−1の関係を満足する. この M = (I − Q)

れば, 頻繁に使用される機能を実現したモジュールに常(4)に多くのフォールトが含まれているわけではないため,

は基本行列

なるべく多くのフォールトを検出したいというテスト効(fundamental matrix) と呼ばれる．テスト対象とするソ率の観点から通常の OPBT が適しているとは言えない.

102

SEA

ソフトウェア・シンポジウム 2015 in 和歌山

ここでは, DTMC の各状態を訪問する度に ri (i =• n1 : プログラム内のオペレータの種類数

1, 2, · · · , m) の報酬が与えられるものとし, DTMC の拡張である DTMRP を導入する. マルコフ報酬過程はパ• n2 : プログラム内のオペランドの種類数

フォーマビリティの概念と共に Meyer [12] によって導• N1 : プログラム内でのオペレータの総出現数

入され, 最近 Avritzer ら [2] によってテストケースの自動生成に応用されている. テストにおいて探索すべき• N2 : プログラム内でのオペランドの総出現数（フォールトプローンな）モジュールが存在し, その探索

これらはプログラムのソースコードから容易に計測可能

優先順位が予め定められているならば, 優先順位ごとにであり, これら 4 つの基本的尺度を用いてプログラムの大きくなる報酬値を割振り, 1 回のテストケースの実行

ボリュームメトリクスを算出する．

が終了するまでの単位ステップ当たりの累積報酬を求め,報酬値として用いる評価尺度の例を表 1 に示す．表中その値が大きいテストケースから順に実行すればよい.

のプログラムの大きさ V ∗ は予測値であり，正確な値がしかしながら, 問題は各モジュールをテストする際に割求められないため, 本稿では与えられる報酬値をどのように決定するかにある. 最も簡便な方法は, 単体テストにおいてフォールトプローン• プログラムの長さ Nモジュールの相対順位を決定し, 優先順位の低い（フォー• プログラムの大きさ V

ルトがより多く含まれない傾向にある）モジュールから,• プログラムの水準の推定値 L̂

1, 2, · · · のような整数値を割振ることであろう. しかし,単体テストの成果として類推されたフォールトプローン• プログラミングの困難さの推定値 D̂

モジュールの相対順位さえも, 必ずしもシステムテスト
において重点的に探索されるべきモジュールであるかど• プログラミング労力の推定値 Ê

うか定かではない.

• プログラミング言語水準の推定値 λ̂

本稿では, ソフトウェアの各モジュールを特徴付ける
報酬値として，ソフトウェアの複雑性メトリクスの相対の 6 つを用いた．McCabe によるサイクロマチック数は，順位を用いることを提案する．複雑性メトリクスとは,プログラムの複雑度をソースコードから測定する手法

プログラムを構成するソースコードから計測される形式である．ソースコードから制御フローを有向グラフで表的構造の複雑性を表す評価尺度である．本研究では単純現することで，グラフを網羅するパスの数がサイクロマ

なコード行数， Halstead によるソフトウェアサイエン

チック数として算出される．制御フローグラフが e 個のス理論 (例えば [19] を参照) に基づいたボリュームメト

枝，n 個の節点を持つとき，サイクロマチック数 M は

リクス，および McCabe [9] によるサイクロマチック数

M =e−n+1を採用した．コード行数は, 開発規模の見積もり方法と(6)

して最も計測が簡単な尺度である．一方, ソフトウェアと求めることができる．各モジュールごとにこれら 6 つサイエンス理論とは, 複雑性の尺度をオペレータおよびのボリュームメトリクスもしくは複雑性メトリクスを算

オペランドの数による関数によって定義する複雑性メト出し, 優先順位の低い (メトリクスの値が小さい) 順に

リクスの枠組みである．ここで, オペレータとは算術演
読点, 区切り符号などで構成され，オペランドとは変数,

1, 2, · · · の整数値を割振った相対順位を報酬として与える. DTMC に基づいて生成された各テストケースごとに単位ステップ当たりの累積報酬を計算し, その値が大定数, ラベルなどを含む．オペレータとオペランドの種

きいものから優先的にテストに使用する．

算子, 比較演算子, 理論演算子, 関数名, コマンド名, 句類および総出現回数を計測することにより，プログラム
開発に要する時間やプログラムがメモリ上に占める大き5. 実験

さなどの指標が計算できる．

Halstead によるソフトウェアサイエンス理論における基本的尺度は以下の 4 つである．

ここでは実際のプログラムに予めフォールトを挿入し,生成されたテストケースに基づいてフォールトを発見・除去する実験を行うことで報酬に基づいたテストケース

103

SEA

ソフトウェア・シンポジウム 2015 in 和歌山

分類

表 1. ソフトウェアサイエンス理論における評価尺度 (文献 [19] から抜粋).
尺度
公式

プログラムの長さプログラムの大きさ

プログラムの長さプログラムの長さ N の推定値

N = N1 + N2
N̂ = N1 + N2

プログラムを実現したときの大きさを記述に必V = N log2 (n1 + n2 )要とされるビット数により表したもの
アルゴリズムを表現したときの最小の大きさ

V ∗ = (2n∗2 )log2 (2 + n∗2 )(n∗2 ) = アルゴリズムの入出力パラメータ数

プログラムの水準

プログラムの水準を実現された大きさ V と最L = V ∗ /V

も簡潔な大きさ V ∗ との比で表したもの
プログラミングの困難さ
プログラミング労力プログラムの水準 L の推定値

L̂ = 2n2 /(n1 N1 )プログラミングをするのに伴う困難さ

D = 1/L

プログラミングの困難さ D の推定値

D̂ = 1/L̂ = 2n2 /(n1 N1 )アルゴリズムを実現するときの理解に必要とさE = V /L = V 2 /V ∗れる労力
プログラミング言語水準

プログラミング労力 E の推定値

Ê = V /L̂

使用するプログラミング言語の言語水準

λ = LV ∗λ̂ = L̂2 V

言語水準 λ の推定値

アの振る舞いを有限状態機械で表したものを図 3 に示
す．プロセスの開始, 終了, 優先度の変更など 7 つの機能によって状態が構成されていることが分かる. このソフ
トウェアに実際のテスト工程で発見された 7 つのフォー
ルトを事前に埋め込み，用意されたテストケースを実行することで実際のソフトウェアテスト環境を再現した．
ここでフォールトはプログラム中の 7 箇所に対応しており，1 つの故障が複数箇所の原因から引き起こされた場
合，原因箇所それぞれが発見されたフォールトとしてカウントされる．本稿では以下のように運用プロファイル
図 3. ‘schedule’ の状態遷移図．

を想定し，テスト実験を行った．

• DTMC に お け る 状 態 推 移 確 率 を 確 率 の 公 理
生成法の性能評価を行う. 実験対象とするソフトウェア

を( 満たすようランダムは ‘schedule’ と呼ばれるプロセス管理ソフトウェア 1 で

p12 = 0.13
p16 = 0.13

あり, C 言語で記述され, コード行数は約 400 行, 18 の関数から構成されているプログラムである．このプログ

こ こ で,

ラムを起動するとまず待機状態になり, 次に入力を受け

p13 = 0.14
p17 = 0.15

各 モ ジュー ル(一 様 乱 数)

p14 = 0.15
p18 = 0.10

IDLE,に 設 定):

p15 = 0.11
p1end = 0.09

NEW JOB,UP-GRADE PRIO, BLOCK, UNBLOCK, QUANTUM EXPIRE, FINISH, FLUSH にそれぞれ 1 ∼ 8 ま付ける. 入力された値によって各機能を実行し，機能実行が終了すると再び待機状態となる. 終了命令が入力さでの状態番号を割当て, 推移率 p1,j (j = 2, · · · , 8) とれるまで上述の動作を繰り返す. テスト対象ソフトウェ

p1,end を与えている. また， pj,1 (j = 2, · · · , 8) および

1 http://sir.unl.edu/content/sir.php

104

SEA

ソフトウェア・シンポジウム 2015 in 和歌山

pend,1 に関しては(
p21 = 1 p31 = 1
p61 = 1 p71 = 1

p41 = 1
p81 = 1

p51 = 1
pend1 = 0)

図 4. 各テストケース生成アルゴリズムに基づいて算出された累積発見フォールト数の比較．
7
6.5

次にソフトウェア設計メトリクスに基づいて報酬として

6

Average number of detected faultsのように設定した．一旦運用プロファイルが定まると，の相対順位を決定する．表 1 において，プログラムの水
準およびプログラミング言語水準に関しては，それらのメトリクス値が大きいものほどフォールトは検出されにくいと考えられる。そのため各機能のメトリクス値を算

5.5
5
4.5
LOC
effortProgram length
VolumeDifficulty
Program level
Language level
Cyclomatic complexity
Without rewards

4

出したのち逆数をとったものを用いることで，フォール
3.5

トが潜在すると想定されるモジュールをテストするため

3のテストケース生成を行った。各テストにおいて，実行

0

100

200

300

開始状態から実行終了状態に至るステップ数（推移の回

400
500
600
Number of test cases

700

800

900

1000

900

1000

(i) 平均値.

数）と，その間に訪問するモジュールのメトリクス値に対する相対順位の累積値をカウントする．次に相対順位

2

LOC
effortProgram length
VolumeDifficulty
Program level
Language level
Cyclomatic complexity
Without rewardsの累積値をステップ数で割ることで, 単位ステップ当りの報酬を求める. DTMRP を 10,000 回シミュレートす1.5
Variance of detected faults

ることで 10,000 本の状態遷移列をテストケースとして生成し，全てのテストケースの中で単位ステップ当たりの報酬値が高い順に並び換えた 1,000 本のテストケースを，1 つのテストスイートとする．この実験では上述のテストスイートを独立に 1,000 本用意し，それらを順次

1

0.5

実行することで，1,000 本のフォールト検出過程を観測する. 各テストケース実行中にフォールトが検出される

00と, それを修正した後に同じテストケースが再度実行され, 終了するまで繰り返される．ここで，フォールトの

100

200

300

400
500
600
Number of test cases

700

800

(ii) 分散.

修正によってメトリクス値が変化することが考えられるが，本実験では修正による報酬値の変化を考慮しないも早い段階で安定して検出することが可能であることが分

のとする．

かった．

図 4 は，想定した運用プロファイルを仮定した 1,000
本のテストスイートに対して，発見フォールト数の平均

次に, より詳細に報酬値の種類に応じたテスト効率の値と分散を消化テストケース数ごとにプロットしたもの比較を行う．表 2 はテスト効率の比較結果を示しており，である．発見フォールト数の平均値はテストケースが消数の値である 7 に近づく傾向がある．しかしながら，報1,000 本のテストスイートの中ですべてのフォールトを発見・除去することができたテストスイート数と，各テストスイート内で 7 つすべてのフォールトを発見・除去

酬を伴わない方法では，報酬を伴う場合と比較して平均するまでに要したテストケース数の最小値, 平均, 分散を発見フォールト数が若干少なくなっている．分散に関しそれぞれ求めたものである．これより，報酬を伴わないては，テスト初期段階で大きくなり，その後で徐々に減方法で生成したテストスイートでは，全体の 67% しか少する傾向を読み取ることができる．報酬を伴わない場

すべてのフォールトを発見・除去することができなかっ合の分散は他と比較して大きくなり，その結果かなりのた．一方，報酬を伴った方法で生成したテストスイート

バラツキが見える．これより，何らかの報酬に基づいてではすべて 98% 以上となり，報酬としてプログラム水

テストケースを自動生成する方が，多くのフォールトを準を導入した場合はすべてのフォールトを検出できたテ化されるにつれて指数関数的に増加し，潜在フォールト

105

SEA

ソフトウェア・シンポジウム 2015 in 和歌山

表 2. 報酬値の種類に応じたテスト効率の比較．
全フォールトを発 全フォールトを発 全フォールトを発見するまで

報酬なし
コード行数
プログラミング労力プログラムの長さプログラムの大きさ
プログラムの水準
プログラミングの困難さ
プログラミング言語水準
サイクロマチック数見した

見できなかったのテストケース数の統計量

テストスイート数

テストスイート数

最小

平均

分散

668
982

332
18

2
8

408.8
215.0

73343.338800.7

994
994
995

6
6
5

3
6
5

205.2
204.2
216.9

33069.032846.2
34648.8

998
990

2
10

4
4

179.0
212.2

26386.634879.7

980
997

20
3

7
4

244.0
192.3

43767.729035.1

ストスイート数は 98.8% となった．さらに，この傾向

次に，ソフトウェア信頼度が規定の値に達した時点では 7 つすべてのフォールトを発見・除去するまでに要し

ソフトウェアテストを打ち切る状況を考える．表 3 は目たテストケース数に対しても同様に観測され，特にプロ

標信頼度を 99%とした場合に，目標を達成するのに要しグラム水準をメトリクスとして用いた場合にテストケー

たテストケース数の平均と分散を比較したものであり，ス数が最小となっている．以上の結果より，どのメトリ目標を達成した時点での発見フォールト数の平均と分クスを報酬値として用いた場合でも，報酬値を用いない

散をそれぞれ求めた結果である．ソフトウェア信頼度がテストケースよりフォールト検出力は格段に向上するこ

99%に達するまでに必要なテストケース数について，いずれかのメトリクスを報酬として用いた場合の方が，用とが分かった．
図 5 は，生成したテストケースを用いてソフトウェア

いない場合と比較して平均と分散が共に小さいことが確テストを実行する際に算出されるソフトウェア信頼度の認された．中でも，サイクロマチック数を報酬として用平均値と分散を消化テストケースごとにプロットしたもいた場合，平均と分散が共に最小となり，目標信頼度にのである．信頼度の平均値はテストケース消化と共にテ到達するためにはサイクロマチック数を報酬として与え

ストの初期段階から大きく増加し，上限である 100 にることでテストケースを生成すれば良いという結論を得

近づいてゆくことがわかる．しかし，報酬を伴わない方た．一方，ソフトウェア信頼度が 99%に達成した時点で法では報酬を伴うテストケース生成法と比較して，平均最も多くのフォールトが発見できているメトリクスはプ

ソフトウェア信頼度の値が小さいことが示される．ソフ

ログラムの水準であった．しかし，99%の目標水準に達トウェア信頼度の分散では，テスト開始時点では分散値

した時点での平均発見フォールト数は，どのメトリクス

は極端に大きいが，テストの進捗が進むにつれて 0 に収を用いたとしてもほぼ全てのフォールトを検出できてい束する様子を確認できる．分散に関する結果から，報酬るため，メトリクスの種類による違いはほとんどないとを用いないテストケース生成法は，報酬を用いた場合と言ってよい．また，報酬なしの場合のテストケース生成

比較して，バラツキが収束するまでにより多くのテスト法で発見された平均発見フォールト数は，報酬を用いた

ケース数が必要であることが示されている．この結果よものと比較すると若干小さいことが分かる．本稿で提案

り，いずれかの報酬を用いてテストケースを生成するこ

した信頼度基準に基づいてテストの打ち切りを行う場合，とにより，テストの早期からフォールトを効率的に検出

どのメトリクスを報酬として用いたとしてもフォールトすることが可能であり，ソフトウェア信頼度の値が早い検出に有効なテストケースを生成できることが分かる．

段階で安定することが分かる．

詳細な実験結果は割愛するが，DTMC における状態
推移確率を変更した実験において，全ての場合において

106

SEA

ソフトウェア・シンポジウム 2015 in 和歌山

表 3. 信頼度基準に基づいたテスト効率の比較．
信頼度が 99% を超える
信頼度が 99% を超えた

報酬なし
コード行数
プログラミング労力プログラムの長さプログラムの大きさ
プログラムの水準
プログラミングの困難さ
プログラミング言語水準
サイクロマチック数までにに要したテストケース数

時点での発見フォールト数

平均

平均

分散

分散

645.4
344.0

3146.3
641.1

6.5
6.8

0.2
0.2

343.1
375.9
344.6

464.7
517.2
628.7

6.8
6.8
6.8

0.2
0.1
0.2

402.6
342.2

542.9
492.0

6.8
6.9

0.2
0.1

352.7
286.1

970.6
368.9

6.7
6.7

0.2
0.2

参考文献

報酬なしと比較した結果，報酬を与えたテストケース生
成が良好な結果をもたらすことが示された．その中でも，プログラム水準とサイクロマチック数を報酬として用いた場合が，概ね良い結果を示していることが観測できた．

[1] A. Avritzer and E. J. Weyuker, The automatic generation of load test suites and the assessment of theresulting software, IEEE Transactions on Software
Engineering, vol. 21, no. 9, pp.705–716 (1995).

6. おわりに[2] A. Avritzer, E. de Souza e Silva, R. M. M. Leao

効率的なテストケースの自動生成が可能であることをand E. J. Weyuker, Automated generation of test
cases using a performability model, IET Software,

示した．特に，報酬として与えたボリュームメトリクス

vol. 5, no. 2, pp.113–119 (2011).

本稿では OPBT に報酬構造を導入することで，よりおよび複雑性メトリクスの中でも，プログラム水準とサ[3] T. S. Chow, Testing design modeled by finite-statemachines, IEEE Transactions on Software Engi-

イクロマチック数の意味で，複雑度の高いモジュールを優先的にテストするようなテストケースを生成すること

neering, vol. 4, no. 3, pp.178–187 (1978).

が効率性の観点から好ましいことが分かった．今回得られた結果は一つのプログラムに対してのみ実験を行った[4] K. Doerner and W. J. Gutjahr, Representation

ものであるため，実験結果が他の種類のソフトウェアにうな報酬構造がテストケースの効率性に寄与するかを包and optimization of software usage models with
non-Markovian state transitions, Information and
Software Technology, vol. 42, no. 12, pp. 815–824

括的に調べるためには，今後さらに他の種類のプログラ(2000).

対しても成立するか調べる必要がある．よって，どのよ

ムを用いたテスト実験を行う必要がある．また，テスト[5] S. Fujiwara, G. V. Bochmann, F. Khendek, M.

ケースの自動生成を通じてソフトウェア信頼度を推定す

Amalou and A. Chedamsi, Test selection based on
finite state models, IEEE Transactions on Software
Engineering, vol. 17, no. 6, pp.591–603 (1991).

ることは，テスト技術者がテスト進捗状況を逐次把握するためには有益な情報に繋がるものと考えられる．その際，ソフトウェア信頼性だけでなく，期待報酬に基づい[6] W. J. Gutjahr, Software dependability evaluation
based on Markov usage models, Performance Eval-

た信頼性評価尺度を求めることにより，異なる視点からテスト終了後の品質評価を行うことは興味深いものと思uation, vol. 402, pp. 199–222 (2000).

われる．

107

SEA

ソフトウェア・シンポジウム 2015 in 和歌山

reliability engineering, IEEE Software, vol. 10, no.
2, pp. 14–32 (1993).

図 5. 報酬値の種類に応じた信頼度のモーメント

Average reliability

比較．
100

[11] J. D. Musa, Software-reliability-engineered test-

99

ing, IEEE Computer, vol. 29, no. 11, pp. 61–68(1996).
[12] J. Meyer, On evaluating the performability of
degradable computing systems, IEEE Transactions
on Computer, vol. C-29, no. 8, pp. 720–731 (1980).

98

97
LOC
effortProgram length
VolumeDifficulty
Program level
Language level
Cyclomatic complexity
Without rewards

96

95
0

100

200

300

400
500
600
Number of test cases

700

800

[13] J. H. Poore, G. H. Walton and J. A. Whittaker, A
constraint-based approach to the representation of
900

software usage models, Information and Software
Technology, vol. 42, pp. 825–833 (2000).

1000(i) 平均値.
2relaibility uising Markov chain usage models, Journal of Systems and Software, vol. 73, pp. 219–225

LOC
effortProgram length
VolumeDifficulty
Program level
Language level
Cyclomatic complexity
Without rewards

1.5
Variance of reliability[14] S. J. Prowell and J. H. Poore, Computing system(2004).
[15] E. J. Weyuker, Using failure cost information for
testing and reliability assessment, ACM Transac-

1

tions on Software Engineering and Methodology,
vol. 5, pp. 87–98 (1996).
0.5[16] J. A. Whittaker and J. H. Poore, Markov analysis of software specifications, ACM Transactions on
Software Engineering and Methodology, vol. 2, no.

0
0

50

100

150
Number of test cases

200

250

300

1, pp. 93–106 (1993).

(ii) 分散.

[17] J. A. Whittaker and M. G. Thomason, A Markov
chain model for statistical software testing, IEEE
Transactions on Software Engineering, vol. 20, no.
10, pp. 812–824 (1994).

[7] 今富政喜，土肥正, 運用プロファイルと報酬構造を考慮したテストケース生成法, ソフトウェアシンポジ
ウム ’14 論文集, ソフトウェア技術者協会, 10 pages,
秋田 (June 9–11, 2014).

[18] J. A. Whittaker, K. Rekab and M. G. Thomason,
A Markov chain model for predicting the reliability[8] C. Kallepalli and J. Tian, Measuring and modeling usage and reliability for statistical web testing,IEEE Transactions on Software Engineering, vol.

of multi-build software, Information and Software
Technology, vol. 42, pp. 889–894 (2000).

27, no. 11, pp. 1023–1036 (2001).

[19] 山田茂，高橋宗雄，ソフトウェアマネジメントモデ
ル入門−ソフトウェア品質の可視化と評価法−，共[9] T. J. McCabe, A complexity measure, IEEE Trans-

立出版，東京，1993.

actions on Software Engineering, vol. SE-2, no. 4,
pp. 308-320 (1976).
[10] J. D. Musa, Operational profiles in software-

108

SEA