(57)【特許請求の範囲】
【請求項１】
指定のテストシナリオに対するテストデータを生成するテストデータ生成プログラムであって、コンピュータに、
テストデータの生成に用いられる文字列の集合を取得する文字列集合取得機能と、
テスト対象のプログラムに、分岐の判定を定量的に評価するための評価値を含む分岐結果を出力するコードを挿入するコード挿入機能と、
指定のテストシナリオに対するテストデータを生成すると共に、前記挿入されたコードが出力した分岐結果を生成する第１テストデータ生成機能と、
前記生成された分岐結果に対して途中まで経路一致する目標分岐結果を生成し、前記取得された文字列の集合の中から選択された文字列を遺伝的アルゴリズムにおいて用いて、当該目標分岐結果を満たすテストデータを生成する第２のテストデータ生成機能と、
を実現させるためのテストデータ生成プログラム。
【請求項２】
前記文字列集合取得機能は、静的解析、動的解析又は事前準備によって、前記文字列の集合を取得する、請求項１に記載のテストデータ生成プログラム。
【請求項３】
前記第２のテストデータ生成機能は、動的解析又は静的解析によって前記目標分岐結果の最終判定分岐が属するクラス及びメソッドから生成された第１の文字列と、動的解析又は静的解析によって前記目標分岐結果の最終判定分岐が属するクラスから生成されたが異なるメソッドから生成された第２の文字列と、動的解析又は静的解析によって前記目標分岐結果の最終判定分岐が属さないクラスから生成された第３の文字列と、事前準備によって生成された第４の文字列との中から１つの文字列を選択し、前記目標分岐結果を満たすテストデータを生成する、請求項２に記載のテストデータ生成プログラム。
【請求項４】
前記第２のテストデータ生成機能は、前記第１の文字列が選択される確率を前記第２の文字列が選択される確率より高く設定し、前記第２の文字列が選択される確率を前記第３の文字列が選択される確率より高く設定し、前記第３の文字列が選択される確率を前記第４の文字列が選択される確率より高く設定する、請求項３に記載のテストデータ生成プログラム。
【請求項５】
前記コード挿入機能は、テスト対象のプログラムの文字列のデータ型の一致判定の箇所に、文字列を出力するコードを挿入し、
前記文字列集合取得機能は、前記目標分岐結果を満たすテストデータを生成する過程において、前記挿入されたコードによって出力された文字列を取得する、請求項１乃至４のうちいずれか１項に記載のテストデータ生成プログラム。
【請求項６】
テスト対象のプログラムが少なくともView及びControllerで構成される場合、
コンピュータに、
Controllerの情報を用いてViewの遷移図を生成し、当該Viewの遷移図から状態遷移図に対する所定のカバレッジ基準に基づいてView及びControllerの繋がりを表すVCシナリオを生成するVCシナリオ生成機能と、
前記生成されたVCシナリオにView操作情報を追加したテストシナリオを生成するテストシナリオ生成機能と、
を更に実現させ、
前記指定のテストシナリオは、前記テストシナリオ生成機能により生成されたテストシナリオから選択される、請求項１乃至５のうちいずれか１項に記載のテストデータ生成プログラム。
【請求項７】
指定のテストシナリオに対するテストデータを生成するテストデータ生成装置におけるテストデータ生成方法であって、
前記テストデータ生成装置が、テストデータの生成に用いられる文字列の集合を取得するステップと、
前記テストデータ生成装置が、テスト対象のプログラムに、分岐の判定を定量的に評価するための評価値を含む分岐結果を出力するコードを挿入するステップと、
前記テストデータ生成装置が、指定のテストシナリオに対するテストデータを生成すると共に、前記挿入されたコードが出力した分岐結果を生成するステップと、
前記テストデータ生成装置が、前記生成された分岐結果に対して途中まで経路一致する目標分岐結果を生成し、前記取得された文字列の集合の中から選択された文字列を遺伝的アルゴリズムにおいて用いて、当該目標分岐結果を満たすテストデータを生成するステップと、
を有するテストデータ生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、テストデータ生成プログラム及びテストデータ生成方法に関し、特に、SBST（Search-Based Software Testing）の遺伝的アルゴリズムにおいて文字列の分岐条件に対応したテストデータを生成する技術に関する。
【背景技術】
【０００２】
ソフトウェア開発工程におけるテストでは、プログラムが設計通りに実行するか否かを確認するため、テストケースが必要となる。人手に代わり、自動でテストケースを準備できれば、開発コスト改善につながる。
【０００３】
テストケースはテストの手順を表すテストシナリオと、テストシナリオを実現するための具体的なデータであるテストデータから構成されている。
【０００４】
テストケースを生成するために、プログラムの設計に基づきテストシナリオやテストデータを自動的に生成する手法が検討されている。
【０００５】
非特許文献１では、入力値定義及び処理フロー図を入力とし、テストシナリオとテストデータ（整数型、文字列型）を生成することが提案されている。
【０００６】
また、非特許文献２では、SBSTの探索アルゴリズムとして遺伝的アルゴリズムを用いてテストデータを生成することが提案されている。
【０００７】
また、非特許文献３では、Concolic TestingとSBSTとを組み合わせたテストデータ生成技術が提案されている。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】張暁晶，星野隆，"設計モデルを用いたテスト項目抽出とテストデータ生成手法"，信学技報，第109巻，SS2009-7，pp.37-42，2009年
【非特許文献２】"Evolutionary Generation of Whole Test Suites"，2011 11th International Conference on Quality Software，pp.31-40，2011年
【非特許文献３】"A Hybrid Directed Test Suite Augmentation Technique"，2011 22nd International Symposium on Software Reliability Engineering，pp.150-159，2011年
【発明の概要】
【発明が解決しようとする課題】
【０００９】
プログラムが設計通りに実行するか否かを確認するためには、どのような手順でテストを実行するかというテストシナリオと、テストシナリオで用いられる具体的な入力値であるテストデータとの双方が必要となる。ここで、あるテストシナリオが与えられたときに、ソースコード上の分岐を網羅的に通過するテストデータの集合を効率的に生成することが求められる。分岐には数値の比較によって分岐するものと、文字列の比較によって分岐するものが存在するが、文字列の比較による分岐条件についても網羅性を高める必要がある。
【００１０】
非特許文献１の技術によれば、入力値定義や処理フロー図を人手で作成する必要があるため、テストシナリオ及びテストデータを効率的に生成することは困難である。
【００１１】
また、非特許文献２の技術によれば、テスト対象のメソッド内で静的解析によって事前に取得した定数を使用してテストデータを生成するが、結合テストレベルでは網羅性を高めることができない。また、定数の取得場所を考慮していないため、解きたい分岐との関連性の薄い定数を選択する可能性がある。
【００１２】
また、非特許文献３の技術によれば、Concolic Testing及びSBSTの２つの手法が順番に実行されるだけであるため、テストデータの生成に時間がかかる。更に、一般的にSBSTでは文字列のデータ型を含む分岐に対してテストデータを生成することは困難である。
【００１３】
本発明は、あるテストシナリオが与えられたときに、文字列のデータ型を含む分岐に対して網羅性の高いテストデータの集合を効率的に生成することを目的とする。
【課題を解決するための手段】
【００１４】
本発明の一形態に係るテストデータ生成プログラムは、
指定のテストシナリオに対するテストデータを生成するテストデータ生成プログラムであって、コンピュータに、
テストデータの生成に用いられる文字列の集合を取得する文字列集合取得機能と、
テスト対象のプログラムに、分岐の判定を定量的に評価するための評価値を含む分岐結果を出力するコードを挿入するコード挿入機能と、
指定のテストシナリオに対するテストデータを生成すると共に、前記挿入されたコードが出力した分岐結果を生成する第１テストデータ生成機能と、
前記生成された分岐結果に対して途中まで経路一致する目標分岐結果を生成し、前記取得された文字列の集合の中から選択された文字列を遺伝的アルゴリズムにおいて用いて、当該目標分岐結果を満たすテストデータを生成する第２のテストデータ生成機能と、
を実現させることを特徴とする。
【００１５】
また、本発明の一形態に係るテストデータ生成方法は、
指定のテストシナリオに対するテストデータを生成するテストデータ生成装置におけるテストデータ生成方法であって、
前記テストデータ生成装置が、テストデータの生成に用いられる文字列の集合を取得するステップと、
前記テストデータ生成装置が、テスト対象のプログラムに、分岐の判定を定量的に評価するための評価値を含む分岐結果を出力するコードを挿入するステップと、
前記テストデータ生成装置が、指定のテストシナリオに対するテストデータを生成すると共に、前記挿入されたコードが出力した分岐結果を生成するステップと、
前記テストデータ生成装置が、前記生成された分岐結果に対して途中まで経路一致する目標分岐結果を生成し、前記取得された文字列の集合の中から選択された文字列を遺伝的アルゴリズムにおいて用いて、当該目標分岐結果を満たすテストデータを生成するステップと、
を有することを特徴とする。
【発明の効果】
【００１６】
本発明によれば、あるテストシナリオが与えられたときに、文字列のデータ型を含む分岐に対して網羅性の高いテストデータの集合を効率的に生成することが可能になる。
【図面の簡単な説明】
【００１７】
【図１】分岐結果の例を示す図
【図２】分岐網羅率と条件網羅率との関係を示す図
【図３】本発明の実施例に係るテストケース生成装置の機能ブロック図
【図４】Viewの遷移図とVCシナリオの例を示す図
【図５】状態遷移図に対する所定のカバレッジ基準を示す図
【図６】本発明の実施例に係るテストケース生成方法の概略フローチャート
【図７】図６のステップＳ００１の詳細フローチャート
【図８】図６のステップＳ００２の詳細フローチャート
【図９】図６のステップＳ００３の詳細フローチャート
【図１０】図６のステップＳ００４の詳細フローチャート
【図１１】図６のステップＳ００５の詳細フローチャート
【図１２】図６のステップＳ００７の詳細フローチャート
【図１３】図６のステップＳ００８の詳細フローチャート
【図１４】図１３のステップＳ２０５の詳細フローチャート
【図１５】図１４のステップＳ３０５の詳細フローチャート
【図１６】図１４のステップＳ３０６の詳細フローチャート
【図１７】図１６のステップＳ６０２の詳細フローチャート
【発明を実施するための形態】
【００１８】
以下、図面を参照して本発明の実施例について説明する。
【００１９】
本発明の実施例では、プログラムのテストシナリオ及びテストデータの組み合わせであるテストケースを生成するテストケース生成プログラム及びテストケース生成方法について説明する。なお、テストケース生成プログラムに関する説明の便宜上、プログラムの各機能をコンピュータ上に実現したテストケース生成装置を例に挙げて説明する。
【００２０】
以下の実施例ではテストシナリオの生成から説明するが、本発明の実施例は、テストシナリオが指定されたときに、指定のテストシナリオに対するテストデータを生成するテストデータ生成プログラム及びテストデータ生成方法としても実現できる。
【００２１】
テストケース生成装置は、Webアプリケーションのようなユーザインタフェースをもつアプリケーションのプログラムをテスト対象として、テストシナリオを生成する。このようなアプリケーションは、MVC（Model View Controller）に従って設計され、少なくともView及びControllerで構成される。Modelは、アプリケーションが扱うデータ及びロジックを表現するための要素であり、Viewは、入出力や表示を行うための要素であり、Controllerは、Viewからの入力に応じて必要なロジックの実行をModelに依頼し、その結果表示をViewに依頼するための要素である。MVCに従って設計されたプログラムでは、Controllerの情報を用いてView間の繋がりが抽出できる。テストケース生成装置は、View間の繋がりを表すViewの遷移図から状態遷移図に対する所定のカバレッジ基準に基づいてView及びControllerの繋がりを表すVCシナリオを生成する。
【００２２】
テストケース生成装置は、生成されたVCシナリオを満たすようなテストデータを、テスト対象のプログラムを動かしながら生成する。一方、ViewとControllerの名前の羅列から構成されるVCシナリオの情報だけでは、どういった操作を行えば良いかわからない。そこで、テストケース生成装置は、クローラやユーザ操作等によってVCシナリオにView操作情報を加えることで、テストシナリオを生成する。
【００２３】
次に、テストケース生成装置は、生成されたテストシナリオのうち１つのシナリオを指定して、以下のようにテストデータを生成する。
【００２４】
テストケース生成装置は、分岐に対する評価値を解析することによりテストデータを生成するテストデータ生成手法を用いてテストデータを生成する。このようなテストデータ生成手法の具体的な例は、SBSTである。SBSTとは、分岐の判定を定量的に評価するための評価値を解析することによりテストデータを生成するテストデータ生成手法である。例えば、入力値>0という分岐に対して(0-入力値)という評価関数を設計し、評価関数の評価値を解析することで、分岐条件を満たすテストデータを生成する。
【００２５】
以下では、SBSTを用いた具体例を説明する。
【００２６】
SBSTでは、分岐の評価値が用いられるため、まず、テストケース生成装置は、テスト対象のプログラムに、分岐の判定を定量的に評価するための評価値を含む分岐結果を出力するコードを挿入する。そして、テストケース生成装置は、Concolic TestingやSBSTによって、指定のテストシナリオに対するテストデータを生成すると共に、挿入されたコードが出力した分岐結果を生成する。なお、Concolic Testingとは、入力値を記号に置き換えて得られた制約式を解析することによりテストデータを生成するテストデータ生成手法である。例えば、入力値>0という分岐に対して具体的な数値を用いる代わりに、数値を記号xに置き換えてx>0という制約式を解析することにより、分岐条件を満たすテストデータを生成する。
【００２７】
一方、分岐の評価値だけでは文字列のデータ型を含む分岐を解析することが困難である。そこで、テストケース生成装置は、テスト対象のプログラムに対して、静的解析、動的解析又は事前準備によって生成された文字列の集合である、String Poolを作成する。静的解析とは、プログラムのソースコード又はバイトコードにおいて、文字列のデータ型の一致判定に用いられている定数を解析することを意味する。また、動的解析とは、テスト対象のプログラムを実行している際に、文字列のデータ型の一致判定に用いられている定数を解析することを意味する。例えば、A.equals(B)というString型の一致判定がある場合、静的解析又は動的解析によって定数BがString Poolに追加される。事前準備とは、入力値や分岐として使われる可能性がある文字列を予め準備することを意味する。例えば、住所が入力値として使われる場合、事前準備によって「東京都千代田区」等の文字列がString Poolに追加される。
【００２８】
次に、テストケース生成装置は、生成された分岐結果に対して途中まで経路一致する目標分岐結果を生成し、目標分岐結果を満たすテストデータを生成する。この目標分岐結果を満たすテストデータの探索アルゴリズムとして、遺伝的アルゴリズムを用いる。遺伝的アルゴリズムは、テストデータの集合を遺伝子の集合として考え、遺伝子を選択、交叉及び突然変異によって操作することにより新たなテストデータを生成するものである。テストケース生成装置は、遺伝的アルゴリズムの突然変異において、String Poolから選択された文字列を用いて、新しいテストデータを生成する。このとき、String Poolの文字列の取得箇所を考慮することで、分岐との関連性の高い文字列を選択する。
【００２９】
ただし、結合テスト対象となる規模のソースコードに対し、Concolic TestingやSBSTを行うと計算爆発が起きるため、指定されたユーザ記述クラスを解析対象としてテストデータを生成してもよい。すなわち、フレームワークやライブラリ等のユーザが記述していない箇所に対しては、カバレッジを向上させるようなテストケースを生成しないことで、計算爆発を回避してもよい。
【００３０】
最後に、テストケース生成装置は、テストシナリオ及びテストデータの組み合わせであるテストケースを出力する。
【００３１】
＜用語の説明＞
まず、本発明の実施例において用いられる用語について説明する。
【００３２】
テストスイートとは、複数のテストケースと、それぞれのテストケースを実行したときの分岐結果から構成される。本発明の実施例における最終的な出力となるテストケースとそのテストケースの分岐結果から構成されるテストスイートを出力テストスイートと呼び、SBSTを実行するために用いられるテストスイートを素材テストスイートと呼ぶ。例えば、テストスイートは、[テストケース1,分岐結果1],[テストケース2,分岐結果2],…として定義される。
【００３３】
テストケースとは、プログラムのテストを実行するために必要な情報を所持しているものであり、１つのテストシナリオと１つのテストデータから構成される。
【００３４】
テストシナリオとは、テストを実行するための手順を表し、VCシナリオとView操作情報であるステップの集合から構成される。例えば、テストシナリオは、[VCシナリオ],[ステップ1,ステップ2,…]として定義される。
【００３５】
テストデータとは、テストシナリオを実現するための具体的な値の集合である。SBSTにおいて、この具体的な値を求めるために遺伝的アルゴリズムが用いられる場合、テストデータは、遺伝子の集合と考えられる。便宜上、Concolic Testing等が用いられる場合であっても、テストデータを遺伝子の集合として定義する。例えば、テストデータは、遺伝子1,遺伝子2, …として定義される。
【００３６】
Viewの遷移図とは、View間の繋がりを表した遷移図である。MVCに従って設計されたプログラムでは、ControllerはViewからの入力をModelに伝え、Modelの実行結果をViewに伝えるため、Controllerの情報を用いてView間の繋がりであるViewの遷移図が生成できる。
【００３７】
VCシナリオとは、Viewの遷移図から生成されるView名及びController名の羅列である。VCシナリオは、View名で始まり、View名で終わる。例えば、VCシナリオは、View名→Controller名→View名→…→View名として定義される。
【００３８】
ステップとは、テストを実行するための手順であるテストシナリオの最小単位を表し、Webアプリケーションである場合には、htmlにおけるフォームやボタンに付与されるidと、動作を示すprocから構成される。
【００３９】
遺伝子とは、テストデータの各要素を表し、Webアプリケーションである場合には、htmlにおけるフォームのidと、具体的な値であるvalueから構成される。
【００４０】
例えば、View1においてIDとPWを入力して、transmitというidが付与されている「ログイン」ボタンを押下するWebアプリケーションをテストする例を考える。この例では、１つのテストケースは、以下のテストシナリオとテストデータの組み合わせで構成される。
【００４１】
テストシナリオ：
VCシナリオ：View1→Controller1→…
ステップ1：id="ID", proc="入力"
ステップ2：id="PW", proc="入力"
ステップ3：id＝"transmit", proc="押下"
…
テストデータ：
遺伝子1：id="ID", value="aaaa"
遺伝子2：id="PW", value="1234"
…
すなわち、このテストケースは、（１）View1においてid="ID"となっているフォームに"aaaa"を入力し、（２）id="PW"となっているフォームに"1234"を入力し、（３）id="transmit"となっているボタンを押下することを意味する。
【００４２】
分岐結果は、テストケースを実行したときのコード上の各分岐の結果である分岐結果要素から構成される。例えば、分岐結果は、分岐結果要素1,分岐結果要素2,…として定義される。
【００４３】
分岐結果要素は、判定分岐、判定順番、判定結果、及び評価値から構成される。判定分岐は、判定対象の分岐を示し、すなわち、どの分岐を判定したかを表す。判定順番は、判定分岐がプログラムの中の全分岐の中で何番目に判定されたかを表す。判定結果は、判定分岐の判定結果（True/False）を表す。評価値は、分岐の判定を定量的に表す値を表す。
【００４４】
評価値について更に具体的に説明する。評価値は、分岐条件を満たしている度合い又は分岐条件を満たしていない度合いを表し、判定分岐に対して設定された評価関数によって取得できる。例えば、if(x>0)という分岐がある場合、x=1の場合とx=100の場合では同じTrueを返すが、x=100の時の方がx=1の時と比べて0より大きいため、より分岐条件を満たしている度合いは強いと評価することができる。分岐条件を満たしている場合には評価値は負の値を持ち、満たしていない場合には正の値を持つ。評価関数は、分岐に対して設定され、例えば、分岐条件がa==bである場合、評価関数はabs(a-b)として定義されてもよく、分岐条件がa!=bである場合、評価関数は-abs(a-b)として定義されてもよく、分岐条件がa<b又はa<=bである場合、評価関数はa-bとして定義されてもよく、分岐条件がa>b又はa>=bである場合、評価関数はb-aとして定義されてもよい。
【００４５】
最終分岐結果要素とは、ある分岐結果の分岐結果要素のうち、判定順番の値が最も大きい値を持つ分岐結果要素を示す。また、最終分岐結果要素を除いた分岐結果の集合を途中分岐結果と定義する。最終分岐結果要素の判定分岐、判定順番、判定結果、及び評価値を、それぞれ最終判定分岐、最終判定順番、最終判定結果及び最終評価値と定義する。
【００４６】
図１に、分岐結果の例を示す。判定分岐が分岐a、分岐b、分岐cである３つの分岐結果要素から構成される分岐結果αを例に挙げると、最終分岐結果要素は分岐cの分岐結果要素である[c,3,True,-2]であり、途中分岐結果は、分岐a及び分岐bの分岐結果要素である[a,1,True,-1],[b,2,False,1]である。
【００４７】
経路一致とは、分岐結果Aと分岐結果Bが存在するとき、分岐結果Aの各分岐結果要素が全て、分岐結果Bの分岐結果要素のいずれかと、評価値を除いて一致している場合、分岐結果Aは分岐結果Bに対して経路一致していると定義する。
【００４８】
図１に示す分岐結果α、分岐結果β、及び分岐結果γを例に挙げると、分岐結果αの分岐結果要素は、分岐結果βの分岐結果要素のいずれかと、評価値を除いて一致しているため、分岐結果αは分岐結果βに対して経路一致している。また、分岐結果αの分岐結果要素は、分岐結果γのいずれかと、評価値を除いて一致していないため、分岐結果αは分岐結果γに対して経路一致していない。
【００４９】
String Poolとは、遺伝的アルゴリズムの突然変異においてテストデータの生成に用いられる文字列の集合である。遺伝的アルゴリズムの突然変異では、定数をランダムに生成する必要があるが、String Poolに予め分岐を解くために有益であると考えられる定数を記憶しておくことで、突然変異においてString Poolに存在する定数を利用し、String型を含む条件分岐に対して網羅性を向上させることができる。例えば、String Poolは、Pool要素1,Pool要素2…として定義される。
【００５０】
Pool要素とは、String Poolに記憶されている要素であり、定数及び出典から構成される。
【００５１】
定数とは、静的解析、動的解析又は事前準備によって取得した値を記憶する要素である。
【００５２】
出典とは、定数を取得した箇所を示す要素である。静的解析又は動的解析では定数はソースコード又はバイトコードから取得されるため、例えば、「クラス名#メソッド名#行数」で出典を表す。定数が事前準備によって取得している場合、出典は「事前準備」とする。
【００５３】
カバレッジとは、プログラムのソースコードがテストされた割合を示す。単位は%である。カバレッジの基準は複数存在し、例えば、分岐網羅率及び条件網羅率が存在するが、特に明記しない限り、本発明の実施例では分岐網羅率をカバレッジと呼ぶ。カバレッジの高いテストデータの集合のことを網羅的なテストデータ又は網羅性の高いテストデータと呼ぶ。
【００５４】
図２に、分岐網羅率と条件網羅率との関係を示す。分岐網羅率は、C1カバレッジとも呼ばれ、プログラム内の分岐がテストされた割合を示す。例えば、図２のような２つの分岐A及び分岐Bが存在するプログラムにおいてC1カバレッジを100%とするためには、分岐A=False且つ分岐B=Trueの場合と、分岐A=True且つ分岐B=Falseの場合の２つをテストする必要がある。
【００５５】
また、条件網羅率は、C2カバレッジとも呼ばれ、プログラム内の条件がテストされた割合を示す。例えば、図２のような２つの分岐A及び分岐Bが存在するプログラムにおいてC2カバレッジを100%とするためには、分岐A=False且つ分岐B=Trueの場合と、分岐A=True且つ分岐B=Falseの場合と、分岐A=True且つ分岐B=Trueの場合と、分岐A=False且つ分岐B=Falseの場合の４つをテストする必要がある。
【００５６】
＜テストケース生成装置の構成＞
次に、本発明の実施例に係るテストケース生成装置の構成について説明する。図３は、本発明の実施例に係るテストケース生成装置１００の機能ブロック図である。
【００５７】
テストケース生成装置１００は、CPU（Central Processing Unit）等のプロセッサ、RAM（Random Access Memory）やROM（Read Only Memory）等のメモリ装置、ハードディスク等の記憶装置等から構成されたコンピュータでもよい。例えば、テストケース生成装置の機能及び処理は、記憶装置又はメモリ装置に格納されているデータやプログラムをプロセッサが実行することによって実現されてもよい。
【００５８】
テストケース生成装置１００は、ソースコードを入力とし、テストシナリオ及びテストデータの組み合わせであるテストケースを出力する。
【００５９】
テストケース生成装置１００は、VCシナリオ生成部１０１と、テストシナリオ生成部１０３と、テストデータ生成部１０５とを有する。なお、本発明の実施例は、VCシナリオ生成部１０１及びテストシナリオ生成部１０３を含まず、テストデータ生成部１０５を含むテストデータ生成装置として実現されてもよい。例えば、処理フロー図等から生成されたテストシナリオが指定され、テストデータ生成装置が指定のテストシナリオに対するテストデータを生成してもよい。
【００６０】
VCシナリオ生成部１０１は、MVCに従って設計されたアプリケーションのプログラムをテスト対象としたときに、ソースコード内のControllerの情報を用いてViewの遷移図を生成する。図４の左側にViewの遷移図の例を示す。遷移図は、状態と、状態同士の関連性を表す線である遷移で構成される。ソースコードにおけるViewは１つの状態と考えられ、Controllerも１つの状態と考えられる。ControllerはViewからの入力をModelに伝え、Modelの実行結果をViewに伝えるため、Controllerの情報を用いてView間の繋がりであるViewの遷移図が抽出できる。更に、VCシナリオ生成部１０１は、Viewの遷移図から状態遷移図に対する所定のカバレッジ基準に基づいてView及びControllerの繋がりを表すVCシナリオを生成する。図４の左側に示すように、Controller1、Controller2、Controller3によってView1、View2、View3の繋がりであるViewの遷移図が生成できると、図４の右側に示すように、１つのView名から始まり１つのView名で終わる複数のVCシナリオが生成できる。VCシナリオの数は状態の数によって膨大な数となるため、状態遷移図に対する所定のカバレッジ基準に基づいてVCシナリオを生成する。
【００６１】
図５は、状態遷移図に対するカバレッジ基準を示す図である。例えば、状態遷移図に対する所定のカバレッジ基準として、All-states、All-transitions、All-transition-pairs、All-loop-free-paths、All-one-loop-paths、All-paths等が存在する。All-statesとは、全状態がどこかのシナリオに含まれるという基準である。例えば、図５に示す状態遷移図を例に挙げると、状態A→状態B→状態D→状態E→状態B→状態Cのシナリオは、All-statesを満たす。All-transitionsとは、全ての長さが1以下のシナリオ（１遷移）がカバーされるという基準である。例えば、図５に示す状態遷移図を例に挙げると、状態A→状態B、状態B→状態C、状態B→状態D、状態D→状態E、状態E→状態Bのシナリオは、All-transitionsを満たす。All-transition-pairsとは、全ての長さが2以下のパス（遷移ペア）がカバーされるという基準である。例えば、図５に示す状態遷移図を例に挙げると、All-transitionsを満たすシナリオに加えて、状態A→状態B→状態C、状態A→状態B→状態D、状態B→状態D→状態E、状態D→状態E→状態B、状態E→状態B→状態D、状態E→状態B→状態Cのシナリオは、All-transition-pairsを満たす。All-loop-free-pathsとは、同じ状態が2回以上現れず、且つ、他のシナリオに部分的に含まれないようなシナリオ（prime pathと呼ばれる）が全てカバーされるという基準である。なお、All-loop-free-pathsはAll-transitionsを保証するものではない。例えば、図５に示す状態遷移図を例に挙げると、状態A→状態B→状態C、状態A→状態B→状態D→状態Eのシナリオは、All-loop-free-pathsを満たす。All-one-loop-pathsとは、All-loop-free-pathsに加えて、ループ1つのみを1回だけ回るシナリオがカバーされるという基準である。例えば、図５に示す状態遷移図を例に挙げると、状態A→状態B→状態C、状態A→状態B→状態D→状態E→状態B→状態Cのシナリオは、All-one-loop-pathsを満たす。All-pathsとは、全てのシナリオがカバーされるという基準である。なお、通常はループが存在するため、All-pathsを満たすシナリオは無限通り存在するため、有用ではない。
【００６２】
テストシナリオ生成部１０３は、生成されたVCシナリオにView操作情報を追加する。例えば、クローラやユーザ操作等によって、生成されたVCシナリオを満たすようなView操作情報を追加する。View操作情報は、ステップの集合で表される。具体的には、クローラやユーザ操作等によってテスト対象のプログラムを動かすことで、テストシナリオ生成部１０３は、生成されたVCシナリオと同じ遷移をするView操作情報を取得すると共に、View操作情報を取得したときのテストデータである初期テストデータを取得する。テストシナリオ生成部１０３は、VCシナリオにView操作情報及び初期テストデータを追加した初期テストケースを生成する。
【００６３】
テストデータ生成部１０５は、生成されたテストシナリオのうち１つのシナリオを指定してテストデータを生成する。ここでは、最初にConcolic Testingによってテストデータ及び分岐結果を生成し、Concolic Testingによって得られたテストデータ及び分岐結果を用いてSBSTによって新たなテストデータを生成する構成例について説明するが、最初にテストデータ及び分岐結果を生成するためのテストデータ生成手法はConcolic Testingに限定されない。Concolic TestingとSBSTとの組み合わせが用いられる場合、テストデータ生成部１０５は、コード挿入部１１１と、Concolic Testing部１１３と、SBST部１１５とを有する。
【００６４】
コード挿入部１１１は、テスト対象のプログラムに、分岐の判定を定量的に評価するための評価値を含む分岐結果を出力するコードを挿入する。このように、コード挿入部１１１は、Concolic Testingを実行している間にSBSTで必要な情報を予め取得するためのコードを挿入する。コード挿入部１１１は、解析対象のユーザ記述クラス内における分岐の箇所に、分岐結果を出力するコードを挿入してもよい。コード挿入部１１１は、解析対象のユーザ記述クラスに対しては、プログラムの分岐を解析するためのコードを挿入してもよいが、フレームワークやライブラリ等のユーザが記述していない箇所は解析対象外とし、プログラムの分岐を解析するためのコードを挿入しなくてもよい。
【００６５】
また、コード挿入部１１１は、テスト対象のプログラムの文字列のデータ型の一致判定の箇所に、Pool要素を出力するコードを挿入する。このように、コード挿入部１１１は、SBSTを実行している間に動的解析によって文字列を取得するためのコードを挿入する。
【００６６】
Concolic Testing部１１３は、入力値を記号に置き換えて得られた制約式を解析することによりテストデータを生成すると共に、挿入されたコードが出力した分岐結果を生成する。このように、Concolic Testing部１１３は、テストデータを生成している間に、SBSTで必要な情報である分岐結果を収集する。すなわち、Concolic Testing部１１３は、指定のテストシナリオに対してテストデータを生成する過程において、指定のテストシナリオと当該テストデータと分岐結果とを、SBSTを実行するために用いられる素材テストスイートに追加する。素材テストスイートには、経路一致している分岐結果が存在する可能性があるため、Concolic Testing部１１３は、指定のテストシナリオに対して生成されたテストデータによってカバレッジが向上する場合、指定のテストシナリオと当該テストデータと分岐結果とを出力テストスイートに追加する。
【００６７】
SBST部１１５は、テストデータを生成するために遺伝的アルゴリズムを用いる。遺伝的アルゴリズムの選択、交叉、及び突然変異をそれぞれ実施するため、SBST部１１５は、選択部１２１と、交叉部１２３と、突然変異部１２５とを含む。特に、突然変異部１２５は、テスト対象のプログラムに対して、静的解析、動的解析又は事前準備によって、テストデータの生成に用いられる文字列の集合であるString Poolを取得するString Pool部１３１を含む。突然変異部１２５は、突然変異において、String Pool部１３１におけるString Poolから選択された文字列を用いて、新しいテストデータを生成する。具体的には、SBST部１１５は、Concolic Testing部１１３において生成された分岐結果に対して途中まで経路一致する目標分岐結果を生成し、突然変異部１２５において、String Poolから選択された文字列を用いて、目標分岐結果を満たすテストデータを生成する。
【００６８】
このようにして、SBST部１１５は、出力テストスイートの分岐結果に対して途中まで経路一致する目標分岐結果を生成し、目標分岐結果と経路一致するテストデータが出力テストスイートに存在しない場合、素材テストスイートを用いて目標分岐結果を満たすテストデータを生成し、出力テストスイートに追加する。更に、SBST部１１５のString Pool部１３１は、目標分岐結果を満たすテストデータを生成する過程において、コード挿入部１１１において挿入されたコードが出力したPool要素を取得する。
【００６９】
また、SBST部１１５の突然変異部１２５は、String Pool部１３１において取得された文字列の取得箇所を考慮することで、分岐との関連性の高い文字列を選択する。String Pool部１３１のPool要素には文字列を取得した箇所を示す出典も記憶されている。String Pool部１３１の文字列は、出典によって、（１）動的解析又は静的解析によって目標分岐結果の最終判定分岐が属するクラス及びメソッドから生成された第１の文字列、（２）動的解析又は静的解析によって目標分岐結果の最終判定分岐が属するクラスから生成されたが異なるメソッドから生成された第２の文字列、（３）動的解析又は静的解析によって目標分岐結果の最終判定分岐が属さないクラスから生成された第３の文字列、（４）事前準備によって生成された第４の文字列に分類される。この場合、（１）第１の文字列、（２）第２の文字列、（３）第３の文字列、（４）第４の文字列の順に分岐との関連性が高いと考えられる。従って、突然変異部１２５は、第１の文字列が選択される確率を第２の文字列が選択される確率より高く設定し、第２の文字列が選択される確率を第３の文字列が選択される確率より高く設定し、第３の文字列が選択される確率を第４の文字列が選択される確率より高く設定する。
【００７０】
＜テストケース生成方法の手順＞
次に、本発明の実施例に係るテストケース生成方法について説明する。図６は、本発明の実施例に係るテストケース生成方法のフローチャートである。
【００７１】
まず、ステップＳ００１において、VCシナリオ生成部１０１は、テスト対象のプログラムのソースコードを入力として受け取り、ソースコード内のControllerの情報を用いて、View間の繋がりを表すViewの遷移図を生成する。
【００７２】
ステップＳ００１について図７を参照して更に説明する。
【００７３】
ステップＳ１０１において、VCシナリオ生成部１０１は、テスト対象のプログラムのソースコードを入力として受け取り、ソースコード内のViewを抽出する。
【００７４】
ステップＳ１０２において、VCシナリオ生成部１０１は、テスト対象のプログラムのソースコードを入力として受け取り、Controllerの情報を用いてView間の繋がりを検出する。具体的には、VCシナリオ生成部１０１は、抽出されたViewの１つを対象Viewとして選択し、対象View名で指定されたViewの遷移先のControllerを取得する。そして、取得した遷移先のControllerの遷移先のViewを対象Viewの遷移先のViewとする。ステップＳ１０１で抽出した各Viewに上記の処理を繰り返すことで、各対象Viewの全ての遷移先のView名と、これらの間に存在するController名が出力される。
【００７５】
ステップＳ１０３において、VCシナリオ生成部１０１は、各対象Viewの全ての遷移先のView名と、これらの間に存在するController名を入力として受け取り、Viewの遷移図を作成する。Viewの遷移図には、View名だけでなく、Controller名も記録される。Viewの遷移図が生成された場合、図６のステップＳ００２に戻る。
【００７６】
次に、図６のステップＳ００２において、VCシナリオ生成部１０１は、Viewの遷移図を入力として受け取り、Viewの遷移図に対して、状態遷移図に対する所定のカバレッジ基準に基づいてVCシナリオを生成する。
【００７７】
ステップＳ００２について図８を参照して更に説明する。
【００７８】
ステップＳ１０４において、VCシナリオ生成部１０１は、Viewの遷移図を状態遷移図として扱い、All-states等の状態遷移図に対する所定のカバレッジ基準に基づいて、複数のVCシナリオを作成する。VCシナリオが生成された場合、図６のステップＳ００３に戻る。
【００７９】
次に、図６のステップＳ００３において、テストシナリオ生成部１０３は、VCシナリオを入力として受け取り、各VCシナリオに対してVCシナリオを満たすテストケースを、クローラ等の技術を用いて生成する。そして、VCシナリオを実現するテストシナリオ及びテストデータを１件のテストケース（初期テストケース）として出力する。
【００８０】
ステップＳ００３について図９を参照して更に説明する。
【００８１】
ステップＳ１０５において、テストシナリオ生成部１０３は、テスト対象のプログラムとVCシナリオを入力として受け取り、クローラ等によってテスト対象のプログラムを実際に操作し、VCシナリオの先頭のViewが表すhtmlファイルにアクセスするURLに移動する。なお、テスト対象のプログラムの操作は、クローラ等の他にユーザによる操作でも代用可能である。
【００８２】
ステップＳ１０６において、テストシナリオ生成部１０３は、空のテストケースTC0を作成する。空のテストケースTC0には、テストシナリオであるVCシナリオとステップの集合の具体的な値は入っておらず、テストデータも入っていない。
【００８３】
ステップＳ１０７において、テストシナリオ生成部１０３は、テスト対象のプログラムとテストケースTC0を入力として受け取り、クローラ等によってテスト対象のプログラムを実際に操作し、テスト対象のプログラムを操作したときに入力したフォームのidやその値をテストケースTC0のテストデータに追加し、入力したフォームのidや押下したボタンのid等をテストケースTC0のテストシナリオに追加する。なお、テスト対象のプログラムの操作は、クローラ等の他にユーザによる操作でも代用可能である。また、操作中のViewやControllerの遷移も取得し、テストケースTC0のテストシナリオに追加する。新しいViewに遷移したところで次のステップＳ１０８に移行する。
【００８４】
ステップＳ１０８において、テストシナリオ生成部１０３は、テストケースTC0とVCシナリオを入力として受け取り、VCシナリオのView及びControllerの遷移と、テストケースTC0が途中又は最後まで同じ遷移をしているか否かを判断する。同じ遷移をしていない場合、ステップＳ１０９に移行し、同じ遷移をしている場合、ステップＳ１１０に移行する。
【００８５】
ステップＳ１０９において、テストシナリオ生成部１０３は、テストケースTC0を入力として受け取り、VCシナリオの遷移とテストケースTC0の遷移が異なる場合、テストケースTC0はVCシナリオを満たさないため、テストケースTC0を破棄し、ステップＳ１０５に移行する。
【００８６】
ステップＳ１１０において、テストシナリオ生成部１０３は、テストケースTC0とVCシナリオを入力として受け取り、VCシナリオのView及びControllerの遷移と、テストケースTC0が最後まで同じ遷移をしているか否かを判断する。最後まで同じ遷移をしていない場合、すなわち、途中までは同じ遷移をしているが、最後まで同じ遷移をしていない場合には、更にテスト対象のプログラムを操作する必要があるため、ステップＳ１０７に移行する。同じ遷移をしている場合、ステップＳ１１１に移行する。
【００８７】
ステップＳ１１１において、テストシナリオ生成部１０３は、テストケースTC0を入力として受け取り、テストケースTC0を初期テストケースとして出力する。初期テストケースが出力された場合、図６のステップＳ００４に戻る。
【００８８】
次に、図６のステップＳ００４において、テストデータ生成部１０５のString Pool部１３１は、事前準備したコンスタントを入力として受け取り、String Poolを作成し、事前準備したコンスタントをString Poolに追加する。このときの出典は「事前準備」とする。
【００８９】
ステップＳ００４について図１０を参照して更に説明する。
【００９０】
ステップＳ７０１において、String Pool部１３１は、事前準備したコンスタントを入力として受け取り、各コンスタントに対して、定数をコンスタントの値とし、出典を事前準備としたPool要素をString Poolに追加する。事前準備によってPool要素がString Poolに追加された場合、図６のステップＳ００５に戻る。
【００９１】
次に、図６のステップＳ００５において、テストデータ生成部１０５のコード挿入部１１１は、テスト対象のプログラムのバイトコードを入力として受け取り、ユーザ記述クラス内のメソッド上のバイトコードに対して、テストデータ生成に必要な情報を取得するためのコードを挿入する。なお、バイトコードの代わりにソースコードを入力として受け取ってもよい。Concolic Testingでは、入力値を記号に置き換えて得られた制約式を解析する必要があるため、入力値を記号に置き換えるためのコードを挿入する。また、コード挿入部１１１は、Concolic Testingを実行している間にSBSTで必要な情報を予め取得するためのコードを挿入する。SBSTでは、分岐の評価値を解析する必要があるため、分岐に対する評価関数の値を出力するためのコードを挿入する。コード挿入部１１１は、ユーザ記述クラスにコード挿入されたバイトコードを出力する。更に、コード挿入部１１１は、SBSTを実行している間に動的解析によってPool要素を取得するためのコードを挿入する。
【００９２】
なお、コード挿入部１１１は、解析対象のユーザ記述クラス名を入力として受け取ってもよく、解析対象外のユーザ記述クラス名を入力として受け取ってもよい。解析対象のユーザ記述クラス名及び解析対象外のユーザ記述クラス名は、ネームスペースで指定されてもよい。この場合、コード挿入部１１１は、解析対象のユーザ記述クラス内のメソッド上のバイトコードに対して、テストデータ生成に必要な情報を取得するためのコードを挿入する。
【００９３】
ステップＳ００５について図１１を参照して更に説明する。
【００９４】
ステップＳ１１２において、コード挿入部１１１は、ユーザにより入力された解析対象のユーザ記述クラス名を入力として受け取ってもよい。また、コード挿入部１１１は、ユーザにより入力された解析対象外のユーザ記述クラス名を入力として受け取ってもよい。ユーザ記述クラス名がネームスペースで指定された場合、コード挿入部１１１は、指定されたネームスペースを持つクラスの名前をバイトコードを調べて取得する。ただし、解析対象外のユーザクラス名が存在する場合、コード挿入部１１１は、解析対象外のユーザクラス名を持つユーザ記述クラスを除外する。
【００９５】
ステップＳ１１３において、コード挿入部１１１は、解析対象のユーザ記述クラス内のフィールド及びメソッド上のバイトコードの各行を調べ、テストデータ生成に必要な情報を取得するためのコードを挿入する。コード挿入部１１１は、Concolic Testingで必要な情報を取得するために、解析対象のユーザ記述クラス内における入力値に対する演算が施される行及び分岐の行に、入力値を記号に置き換えるためのコードを挿入する。また、コード挿入部１１１は、SBSTで必要な情報を取得するために、解析対象のユーザ記述クラス内における分岐の箇所に、分岐結果を出力するコードを挿入する。ユーザ記述クラス内のメソッド上でコードを挿入する必要がない行に対しては何も実施しない。
【００９６】
ステップＳ１１４において、テストデータ生成部１０５のString Pool部１３１は、解析対象のユーザ記述クラス内のフィールド及びメソッド上のバイトコードの各行に対して静的解析を行い、得られたオペランドやコンスタントをString Poolに追加する。このときの出典は、オペランドやコンスタントを取得した箇所である「クラス名#メソッド名#行数」とする。
【００９７】
ステップＳ１１５において、コード挿入部１１１は、解析対象のユーザ記述クラス内のフィールド及びメソッド上のバイトコードの各行を調べ、String型の一致判定が存在するか否かを判断する。String型の一致判定とは、例えばA.equals(B)という文字列同士を比較する箇所を示す。String型の一致判定が存在しない場合、次の行を調べ、String型の一致判定が存在する場合、ステップＳ１１６に移行する。
【００９８】
ステップＳ１１６において、コード挿入部１１１は、テスト対象のプログラムを実際に操作したときに、文字の比較対象のオペランド（例えば、A.equals(B)の場合のB）と、出典をString Poolに追加できるようなコードを挿入する。このときの出典は、オペランドを取得した箇所である「クラス名#メソッド名#行数」とする。例えば、hogeクラスのfugaメソッド内の10行目がA.equals(B)である場合、コード挿入部１１１は、「定数:B,出典:hoge#fuga#10」となるPool要素をString Poolに追加できるように、コード挿入を実施する。ユーザ記述クラス内のフィールド及びメソッド上でコードを挿入する必要がない行に対しては何も実施しない。コードが挿入された場合、図６のステップＳ００６に戻る。
【００９９】
次に、初期テストケースの中から１つのテストケースを指定し、以下のようにテストデータを生成する。
【０１００】
図６のステップＳ００６において、テストデータ生成部１０５のConcolic Testing部１１３は、空の出力テストスイートを作成する。空の出力テストスイートには、テストシナリオであるVCシナリオとステップの集合の具体的な値は入っておらず、テストデータも分岐結果も入っていない。
【０１０１】
次に、図６のステップＳ００７において、Concolic Testing部１１３は、コード挿入されたバイトコードと、初期テストケースと、出力テストスイートを入力として受け取り、初期テストケースに基づき、Concolic Testingに従ってテストデータを生成し、得られたテストケースを出力テストスイートに追加する。
【０１０２】
ステップＳ００７について図１２を参照して更に説明する。
【０１０３】
ステップＳ１１４において、Concolic Testing部１１３は、初期テストケースを入力として受け取り、初期テストケースを複製してテストケースTCNと定義する。
【０１０４】
ステップＳ１１５において、Concolic Testing部１１３は、テストケースTCN及びコード挿入されたバイトコードを入力として受け取り、Concolic Testingに従って新しいテストデータを生成する。Concolic Testingでは、テストケースTCNを実際に実行する必要があるが、テストケースTCNにはView操作情報を含むテストシナリオや、具体的なテストデータが含まれているため、スクリプトを作成し、スクリプトを実行するツールであるSelenium等を利用することにより自動的にConcolic Testingを実行することができる。また、コード挿入部１１１によってSBSTで必要な情報である分岐結果を出力するコードが挿入されているため、Concolic Testing部１１３は、テストデータと共に分岐結果を取得することができる。
【０１０５】
ステップＳ１１６において、Concolic Testing部１１３は、生成したテストデータと初期テストケースを入力として受け取り、生成したテストデータを初期テストケースの中のテストデータと置き換えて、新しいテストケースTCNを出力する。
【０１０６】
ステップＳ１１７において、Concolic Testing部１１３は、テストケースTCNと分岐結果と素材テストスイートを入力として受け取り、テストケースTCNと分岐結果を素材テストスイートに追加する。
【０１０７】
ステップＳ１１８において、Concolic Testing部１１３は、テストケースTCNと出力テストスイートを入力として受け取り、テストケースTCNを出力テストスイートに加えることでカバレッジが向上するか否かを判断する。カバレッジが向上する場合、ステップＳ１１９に移行し、カバレッジが向上しない場合、ステップＳ１２０に移行する。
【０１０８】
ステップＳ１１９において、Concolic Testing部１１３は、テストケースTCNと分岐結果と出力テストケースを入力として受け取り、テストケースTCNと分岐結果を出力テストスイートに追加する。
【０１０９】
ステップＳ１２０において、Concolic Testing部１１３は、解析が終わっていない場合、ステップＳ１１５に移行し、テストデータの生成を繰り返す。解析が終わった場合、図６のステップＳ００８に戻る。
【０１１０】
次に、図６のステップＳ００８において、テストデータ生成部１０５のSBST部１１５は、SBSTで必要な情報である分岐結果を出力するコードが挿入されたバイトコードと出力テストスイートと素材テストスイートを入力として受け取る。SBST部１１５は、コードが挿入されたバイトコードに対し、テストデータの各遺伝子を入力としてテスト対象のプログラムを実際に動かして解析するSBSTを実行し、Concolic Testing部１１３で生成したテストデータが通過することのできない分岐を通過するようなテストデータを生成する。SBST部１１５は、このようにカバレッジを向上させるテストデータを出力テストスイートに追加して出力テストスイートを強化する。なお、SBST部１１５で用いるテストデータは、素材テストスイートから選択される。
【０１１１】
ステップＳ００８について図１３を参照して更に説明する。
【０１１２】
ステップＳ２０１において、SBST部１１５は、出力テストスイートの各分岐結果BR0に対して、分岐結果BR0の分岐結果要素の数をnとする。
【０１１３】
ステップＳ２０２において、SBST部１１５は、分岐結果BR0を入力として受け取り、分岐結果BR0に対し、判定順番の値がnより大きい分岐結果要素を全て削除した新しい分岐結果BRを作成する。
【０１１４】
ステップＳ２０３において、SBST部１１５は、分岐結果BRを入力として受け取り、分岐結果BRに対し、最終判定結果を反転した新しい分岐結果を作成し、目標分岐結果とする。例えば、分岐結果BRの最終判定結果がTrueである場合、その最終判定結果をFalseとし、分岐結果BRの最終判定結果がFalseである場合、その最終判定結果をTrueとする。
【０１１５】
ステップＳ２０４において、SBST部１１５は、目標分岐結果と経路一致する分岐結果が出力テストスイートに存在するか否かを判断する。図１を参照して説明した通り、ここでは分岐結果の経路一致を判断するため、評価値は異なってもよい。目標分岐結果と経路一致する分岐結果が出力テストスイートに存在しない場合、ステップＳ２０５に移行し、存在する場合、ステップＳ２０６に移行する。
【０１１６】
ステップＳ２０５において、SBST部１１５は、素材テストスイートと目標分岐結果を入力として受け取り、目標分岐結果を満たすようなテストデータをSBSTによって生成する。
【０１１７】
ステップＳ２０５について、図１４を参照して更に説明する。
【０１１８】
ステップＳ３０１において、遺伝的アルゴリズムを用いてSBSTを実行するときの最大世代数をGとし、現在の世代gを1とする。
【０１１９】
ステップＳ３０２において、SBST部１１５は、素材テストスイートと目標分岐結果を入力として受け取り、素材テストスイートの各分岐結果に対し、目標分岐結果の最終判定分岐を持つ分岐結果要素の評価値でソートする。例えば、目標分岐結果の最終判定分岐がTrueである場合、評価値の値が小さいほど優秀であると判断し、目標分岐結果の最終判定分岐がFalseである場合、評価値の値が大きいほど優秀であると判断する。ただし、目標分岐結果の最終判定分岐を持たない分岐結果は、最も優秀でないと判断する。SBST部１１５は、優秀であると判断された分岐結果と、それに対応するテストケースを上から順番に並べてソートする。
【０１２０】
ステップＳ３０３において、SBST部１１５は、空のテストスイートTSを生成する。空のテストスイートTSには、テストケースの具体的な値は入っておらず、分岐結果も入っていない。
【０１２１】
ステップＳ３０４において、SBST部１１５の選択部１２１は、ソートされた素材テストスイートとテストスイートTSとを入力として受け取り、ソートされた素材テストスイートの上から順番に複数のテストケースを選択する。選択されるテストケースの個数は、予め決められた定数とする。選択部１２１は、選択されたテストケースの遺伝子を操作したテストケースを生成する。例えば、選択部１２１は、選択されたテストケースが持つ１つの遺伝子に対し、int型であればランダムで1を加えてもよく、1を引いてもよい。例えば、選択部１２１は、選択されたテストケースが持つ１つの遺伝子に対し、String型であればランダムで１文字を追加してもよく、１文字を削除してもよい。選択部１２１は、この動作を全ての遺伝子に対して実施することで、１つのテストケースに対し、遺伝子の数だけ新しいテストケースを生成し、新しいテストケースをテストスイートTSに追加する。
【０１２２】
ステップＳ３０５において、SBST部１１５の交叉部１２３は、ソートされた素材テストスイートとテストスイートTSとを入力として受け取り、ソートされた素材テストスイートの上から順番に複数のテストケースを選択する。選択されるテストケースの個数は、予め決められた定数とする。交叉部１２３は、選択されたテストケースの遺伝子を配合した新しいテストケースを生成する。例えば、交叉部１２３は、選択されたテストケースの中から２つのテストケースを無作為に抽出し、２つのテストケースが持つ遺伝子をそれぞれランダムに配合した新しいテストケースを生成する。交叉部１２３は、この動作を繰り返すことで、予め決められた一定数の新しいテストケースを生成し、新しいテストケースをテストスイートTSに追加する。
【０１２３】
ステップＳ３０５について、図１４を参照して更に説明する。
【０１２４】
ステップＳ４０１において、交叉部１２３は、ソートされた素材テストスイートを入力として受け取り、ソートされた素材テストスイートの上から順番に複数のテストケースを抽出する。
【０１２５】
ステップＳ４０２において、交叉部１２３は、抽出したテストケース群を入力として受け取り、テストケース群から２つのテストケースを無作為に抽出し、それぞれの遺伝子を無作為に配合した新しいテストケースを生成する。例えば、交叉部１２３は、テストケース群からテストケースA及びテストケースBを抽出する。ここで、テストケースA及びテストケースBのテストシナリオは同じであるため、テストケースA及びテストケースBは同じidを持つ遺伝子をそれぞれ所有している。交叉部１２３は、id毎に遺伝子をテストケースA及びテストケースBから無作為に抽出することで新しいテストケースを作成する。例えば、テストケースAの遺伝子が[[id=1,value=0],[id=2,value=1]]であり、テストケースBの遺伝子が[[id=1,value=10],[id=2,value=5]]であるとすると、[[id=1,value=0],[id=2,value=1]],[[id=1,value=0],[id=2,value=5]],[[id=1,value=10],[id=2,value=1]],[[id=1,value=10],[id=2,value=5]]の４通りのテストケースが生成され得る。
【０１２６】
ステップＳ４０３において、交叉部１２３は、作成したテストケースとテストスイートTSを入力として受け取り、作成したテストケースをテストスイートTSに追加する。
【０１２７】
ステップＳ４０４において、交叉部１２３は、予め決められた一定数の新しいテストケースを作成したか否かを判断し、作成していない場合、ステップＳ４０２に戻り、上記の処理を繰り返す。一定数の新しいテストケースを作成した場合、図１４のステップＳ３０６に戻る。
【０１２８】
次に、図１４のステップＳ３０６において、SBST部１１５の突然変異部１２５は、ソートされた素材テストスイートとテストスイートTSとを入力として受け取り、ソートされた素材テストスイートの上から順番に複数のテストケースを選択する。選択されるテストケースの個数は、予め決められた定数とする。突然変異部１２５は、選択されたテストケースの遺伝子を突然変異した新しいテストケースを生成する。例えば、突然変異部１２５は、選択されたテストケースが持つ１つの遺伝子に対し、一定の確率で新しい値を与え、また、一定の確率でString Poolから引用した値を与えることで、新しいテストケースを生成する。この動作を全ての遺伝子に対して実施し、１つのテストケースに対して遺伝子の数だけ新しいテストケースを生成する。突然変異部１２５は、突然変異によって複数の新しいテストケースを生成し、新しいテストケースをテストスイートTSに追加する。
【０１２９】
ステップＳ３０６について、図１６を参照して更に説明する。
【０１３０】
ステップＳ６０１において、突然変異部１２５は、ソートされた素材テストスイートを入力として受け取り、ソートされた素材テストスイートの上から順番に複数のテストケースを抽出する。
【０１３１】
ステップＳ６０２において、突然変異部１２５は、抽出したテストケースを入力として受け取り、テストケースの各テストデータの各遺伝子に対して、遺伝子のvalueの値を一定確率で２種類の操作のうちどちらかによって変更する。２種類の操作のうち一方は、valueの値をランダムな値に変更する操作である。例えば、突然変異部１２５は、遺伝子のvalue="aaa"を一定確率でvalue="hoge"に変更する。変更する値はどのような値でもよい。２種類の操作のうち他方は、String Poolの中の定数を用いて、valueの値に代入する操作である。
【０１３２】
ステップＳ６０２について、図１７を参照して更に説明する。
【０１３３】
ステップＳ７０２において、突然変異部１２５は、ランダムでステップＳ７０３又はステップＳ７０４に移行する。
【０１３４】
ステップＳ７０３において、突然変異部１２５は、抽出したテストケースを入力として受け取り、テストケースの各テストデータの各遺伝子に対して、遺伝子のvalueの値を一定確率でランダムな値に変更する。例えば、突然変異部１２５は、遺伝子のvalue="aaa"を一定確率でvalue="hoge"に変更する。変更する値はどのような値でもよい。また、残りの確率で遺伝子の変更を行わない。確率は予め決められた定数とする。
【０１３５】
ステップＳ７０４において、突然変異部１２５は、空のString Pool(1)、空のString Pool(2)、空のString Pool(3)、空のString Pool(4)を作成する。
【０１３６】
ステップＳ７０５において、突然変異部１２５は、String Poolを入力として受け取り、String Poolの各Pool要素の出典が「事前準備」であるか否かを判断する。出典が「事前準備」である場合、ステップＳ７０６に移行し、出典が「事前準備」でない場合、ステップＳ７０７に移行する。
【０１３７】
ステップＳ７０６において、突然変異部１２５は、String PoolとString Pool(4)を入力として受け取り、出典が「事前準備」となっている各Pool要素をString Pool(4)に追加する。
【０１３８】
ステップＳ７０７において、突然変異部１２５は、String Poolと目標分岐結果を入力として受け取り、目標分岐結果の最終判定分岐が属するクラスが、String Poolの各Pool要素の出典のクラス名と一致するか否かを判断する。一致しない場合、ステップＳ７０８に移行し、一致する場合、ステップＳ７０９に移行する。
【０１３９】
ステップＳ７０８において、突然変異部１２５は、String PoolとString Pool(3)を入力として受け取り、目標分岐結果の最終判定分岐が属するクラスが出典のクラス名と一致しない各Pool要素をString Pool(3)に追加する。
【０１４０】
ステップＳ７０９において、突然変異部１２５は、String Poolと目標分岐結果を入力として受け取り、目標分岐結果の最終判定分岐が属するメソッドが、String Poolの各Pool要素の出典のメソッド名と一致するか否かを判断する。一致しない場合、ステップＳ７１０に移行し、一致する場合、ステップＳ７１１に移行する。
【０１４１】
ステップＳ７１０において、突然変異部１２５は、String PoolとString Pool(2)を入力として受け取り、目標分岐結果の最終判定分岐が属するクラスが出典のクラス名と一致するが、目標分岐結果の最終判定分岐が属するメソッドが出典のメソッド名と一致しない各Pool要素をString Pool(2)に追加する。
【０１４２】
ステップＳ７１１において、突然変異部１２５は、String PoolとString Pool(1)を入力として受け取り、目標分岐結果の最終判定分岐が属するクラスが出典のクラス名と一致し、且つ、目標分岐結果の最終判定分岐が属するメソッドが出典のメソッド名と一致する各Pool要素をString Pool(1)に追加する。
【０１４３】
ステップＳ７１２において、突然変異部１２５は、String Pool(1)、String Pool(2)、String Pool(3)、String Pool(4)を入力として受け取り、String Pool(1)、String Pool(2)、String Pool(3)、String Pool(4)の中から１つを選択する。
【０１４４】
ステップＳ７１３において、突然変異部１２５は、抽出したテストケースと選択したString Poolを入力として受け取り、テストケースの各テストデータの各遺伝子に対して、選択したString Poolから１つのPool要素を選択し、Pool要素の定数を遺伝子のvalueに代入する。なお、String Poolを選択する確率は、String Pool(1)＞String Pool(2)＞String Pool(3)＞String Pool(4)となるように設定されているため、目標分岐結果の最終判定分岐の行数と近い値を持つPool要素が選択される確率が高くなる。なお、行数の近さと確率との相関は事前に設定する。
【０１４５】
突然変異により遺伝子が操作された場合、図１６のステップＳ６０３に戻る。
【０１４６】
ステップＳ６０３において、突然変異部１２５は、遺伝子操作されたテストケースとテストスイートTSを入力として受け取り、遺伝子操作されたテストケースをテストスイートTSに追加する。遺伝子操作されたテストケースがテストスイートTSに追加された場合、図１４のステップＳ３０７に戻る。
【０１４７】
次に、テストスイートTSの各テストケースに対し、以下のように出力テストスイートを生成する。
【０１４８】
図１４のステップＳ３０７において、SBST部１１５は、テストスイートTS内のテストケースを入力として受け取り、テスト対象のプログラムにテストスイートTS内のテストケースを実行させる。コード挿入部１１１が分岐結果を出力するコードを挿入しているため、テストケースに対し、対応する分岐結果が取得できる。
【０１４９】
ステップＳ３０８において、SBST部１１５のString Pool部１３１は、テストスイートTS内のテストケースを入力として受け取り、テスト対象のプログラムにテストスイートTS内のテストケースを実行させる。コード挿入部１１１がString型の一致判定の箇所にPool要素を出力するコードを挿入しているため、テストケースに対し、対応するPool要素が取得できる。SBST部１１５のString Pool部１３１は、String型の一致判定がある場合、文字列の比較対象のオペランドと、出典をString Poolに追加する。なお、ステップＳ３０８は、ステップＳ３０７と同時に実行されてもよい。
【０１５０】
ステップＳ３０９において、SBST部１１５は、テストスイートTS内のテストケースと、対応する分岐結果と、素材テストスイートを入力として受け取り、テストケースと、対応する分岐結果を素材テストスイートに追加する。
【０１５１】
ステップＳ３１０において、SBST部１１５は、テストスイートTS内のテストケースと、対応する分岐結果と、出力テストスイートを入力として受け取り、SBST部１１５がテストケースを実行して得られた分岐結果と経路一致する分岐結果が出力テストスイートに存在するか否かを判断する。存在しない場合、ステップＳ３１１に移行し、存在する場合、ステップＳ３０７に戻り、次のテストケースに対する処理を実施し、全てのテストケースに対する処理が終了した場合、ステップＳ３１３に移行する。
【０１５２】
ステップＳ３１１において、SBST部１１５は、テストスイートTS内のテストケースと、対応する分岐結果と、出力テストスイートを入力として受け取り、テストケースと、対応する分岐結果を出力テストスイートに追加する。
【０１５３】
ステップＳ３１２において、SBST部１１５は、SBST部１１５がテストケースを実行して得られた分岐結果が目標分岐結果と経路一致しているか否かを判断する。経路一致していない場合、ステップＳ３１３に移行し、経路一致している場合、図１３のステップＳ２０６に戻る。
【０１５４】
ステップＳ３１３においてg=g+1として、ステップＳ３１４においてgが最大世代数GになるまでステップＳ３０２に戻り、上記の処理を繰り返す。gが最大世代数になった場合、図１３のステップＳ２０６に戻る。
【０１５５】
次に、図１３のステップＳ２０６においてn=n-1として、ステップＳ２０７においてnが0になるまでステップＳ２０２に戻り、上記の処理を繰り返す。nが0になった場合、ステップＳ２０１に戻り、次の分岐結果に対する処理を実施し、全ての分岐結果に対する処理が終了した場合、図６のステップＳ００９に戻る。
【０１５６】
次に、図６のステップＳ００９において、テストデータ生成部１０５は、出力テストスイートの中の全てのテストケースをファイル等に出力する。
【０１５７】
以上の手順により、テストケース生成装置１００は、テストシナリオ及びテストデータの組み合わせであるテストケースを出力することができる。
＜本発明の実施例の効果＞
本発明の実施例によれば、あるテストシナリオが与えられたときに、文字列のデータ型を含む分岐に対して網羅性の高いテストデータの集合を効率的に生成することが可能になる。
【０１５８】
特に、SBSTの探索アルゴリズムの１つである遺伝的アルゴリズムの突然変異において、従来は文字列をランダムに生成していたが、分岐を解くために有益であると考えられる文字列をString Poolという保存場所に記憶しておくことで、突然変異においてString Poolに存在する文字列を利用してString型を含む条件分岐に対する網羅性を向上させることが可能になる。
【０１５９】
また、String Poolの文字列の取得箇所が出典として管理されているため、解きたい分岐と関連性の高い文字列がString Poolから選択される可能性が高くなる。
【０１６０】
また、Concolic Testing及びSBSTの性質の異なる２つの手法を組み合わせることで、よりカバレッジの高いテストデータが生成できる。ただし、２つの手法を順番に実行すると、テストデータの生成にかなりの時間を要するため、Concolic Testingを実行している間にSBSTで必要な情報を予め取得することで、SBSTにおけるテストデータの効率的な探索を可能としている。その結果、プログラムの構造的欠陥によるバグの検出能力が向上する。
【０１６１】
また、テストシナリオをViewの遷移図から生成することにより、Webアプリケーションにおける画面遷移に対する網羅性の高いテストケースが自動生成できる。WebアプリケーションにおけるViewは画面に非常に近い粒度を持つため、Viewの遷移図に対して状態遷移図に対する所定のカバレッジ基準を用いてテストシナリオを抽出することで、画面遷移の粒度に近く、また、画面遷移に対する網羅性の高いテストシナリオを自動生成できる。
【０１６２】
更に、Concolic TestingやSBSTによってテストデータを生成するときに、フレームワークやライブラリ等のユーザが記述していない箇所に対して分岐を解析しないことで、計算爆発を回避することができ、従って、結合テストレベルのテストケースも生成できる。フレームワークやライブラリ等のユーザが記述していない箇所に対してカバレッジを向上させるようなテストケースを生成せず、その代わりに、解析対象のユーザ記述クラスに対するカバレッジの高いテストケース生成に計算リソースを割り当てることができる。
【０１６３】
説明の便宜上、本発明の実施例に係るテストケース生成装置は機能的なブロック図を用いて説明しているが、本発明の実施例に係るテストケース生成装置は、ハードウェア、ソフトウェア又はそれらの組み合わせで実現されてもよい。例えば、本発明の実施例は、コンピュータに対して本発明の実施例に係るテストケース生成装置の各機能を実現させるプログラム、コンピュータに対して本発明の実施例に係るテストケース生成方法の各手順を実行させるプログラム等により、実現されてもよい。また、各機能部が必要に応じて組み合わせて使用されてもよい。また、本発明の実施例に係るテストケース生成方法は、実施例に示す順序と異なる順序で実施されてもよい。
【０１６４】
以上、あるテストシナリオが与えられたときに、文字列のデータ型を含む分岐に対して網羅性の高いテストデータの集合を効率的に生成するための手法について説明したが、本発明は、上記の実施例に限定されることなく、特許請求の範囲内において、種々の変更・応用が可能である。
【符号の説明】
【０１６５】
１００  テストケース生成装置
１０１  VCシナリオ生成部
１０３  テストシナリオ生成部
１０５  テストデータ生成部
１１１  コード挿入部
１１３  Concolic Testing部
１１５  SBST部
１２１  選択部
１２３  交叉部
１２５  突然変異部
１３１  String Pool部
【図１】
0006533484.tif 000002
【図２】
0006533484.tif 000003
【図３】
0006533484.tif 000004
【図４】
0006533484.tif 000005
【図５】
0006533484.tif 000006
【図６】
0006533484.tif 000007
【図７】
0006533484.tif 000008
【図８】
0006533484.tif 000009
【図９】
0006533484.tif 000010
【図１０】
0006533484.tif 000011
【図１１】
0006533484.tif 000012
【図１２】
0006533484.tif 000013
【図１３】
0006533484.tif 000014
【図１４】
0006533484.tif 000015
【図１５】
0006533484.tif 000016
【図１６】
0006533484.tif 000017
【図１７】
0006533484.tif 000018