(57)【要約】【課題】より少数のパスで分岐網羅度を向上させることができるパス集合を被検査プログラムから抽出する。【解決手段】テストケース生成装置１０は、被検査プログラム３０に含まれる条件分岐の分岐先への分岐実行回数を管理し、分岐実行回数から得られる経路候補に対応した分岐情報、及び既に抽出された被検査プログラム３０の既出経路に対応した分岐情報を比較して、経路候補が既出経路に含まれる重複経路か否かを検出し、経路候補が重複経路ではないと検出された場合に、条件分岐の分岐実行回数に応じた予め定めた規則に基づいて分岐先を決定して、被検査プログラム３０の開始から終了までの経路を選択し、選択された経路に対応した分岐情報を、既出経路に対応した分岐情報として生成する。【選択図】図７
2015176230.tif 000002
【特許請求の範囲】
【請求項１】
被検査プログラムに含まれる条件分岐の分岐先への分岐実行回数を管理する管理部と、
前記管理部により管理された前記分岐実行回数から得られる経路候補に対応した分岐情報と、既に抽出された前記被検査プログラムの既出経路に対応した分岐情報と、を比較して、前記経路候補が前記既出経路に含まれる重複経路か否かを検出する検出部と、
前記条件分岐の前記分岐実行回数に応じた予め定めた規則に基づいて分岐先を決定して、前記被検査プログラムの開始から終了までの経路を選択する選択部と、
前記選択部により選択された前記経路に対応した分岐情報を、前記既出経路に対応した分岐情報として生成する生成部と、
前記検出部により前記経路候補が前記重複経路ではないと検出された場合、前記選択部及び前記生成部の各々による処理が実行され、前記検出部により前記経路候補が前記重複経路であると検出された場合、前記選択部及び前記生成部の各々による処理が実行されないように、前記選択部及び前記生成部を制御する制御部と、
を有するテストケース生成装置。
【請求項２】
前記管理部は、前記条件分岐が前記被検査プログラムの呼出元から呼び出されるサブルーチンに含まれる条件分岐である場合には、前記条件分岐の各々について、前記条件分岐に対応した前記分岐実行回数を管理すると共に、前記サブルーチンの呼出元毎に前記条件分岐に対応した前記分岐実行回数を管理する
請求項１記載のテストケース生成装置。
【請求項３】
前記制御部は、前記管理部で管理される前記分岐実行回数に基づいて算出される、前記選択部による新たな前記経路の選択前の分岐網羅度と、前記管理部で管理される前記分岐実行回数に基づいて算出される、前記選択部による新たな前記経路の選択後の分岐網羅度と、を比較し、新たな前記経路の選択後の分岐網羅度が新たな前記経路の選択前の分岐網羅度と同じ場合には、前記選択部により選択された新たな前記経路に対応した分岐情報を、前記既出経路に対応した分岐情報として生成しないように前記生成部を制御する
請求項１又は請求項２記載のテストケース生成装置。
【請求項４】
被検査プログラムに含まれる条件分岐の分岐先への分岐実行回数を管理し、
前記分岐実行回数から得られる経路候補に対応した分岐情報と、既に抽出された前記被検査プログラムの既出経路に対応した分岐情報と、を比較して、前記経路候補が前記既出経路に含まれる重複経路か否かを検出し、
前記経路候補が前記重複経路ではないと検出された場合、前記条件分岐の前記分岐実行回数に応じた予め定めた規則に基づいて分岐先を決定して、前記被検査プログラムの開始から終了までの経路を選択し、前記経路に対応した分岐情報を、前記既出経路に対応した分岐情報として生成し、前記経路候補が前記重複経路であると検出された場合、前記経路候補に対応した前記経路を選択せずに、且つ、前記経路に対応した分岐情報を、前記既出経路に対応した分岐情報として生成しないように制御する
ことを含むテストケース生成方法。
【請求項５】
コンピュータに、
被検査プログラムに含まれる条件分岐の分岐先への分岐実行回数を管理し、
前記分岐実行回数から得られる経路候補に対応した分岐情報と、既に抽出された前記被検査プログラムの既出経路に対応した分岐情報と、を比較して、前記経路候補が前記既出経路に含まれる重複経路か否かを検出し、
前記経路候補が前記重複経路ではないと検出された場合、前記条件分岐の前記分岐実行回数に応じた予め定めた規則に基づいて分岐先を決定して、前記被検査プログラムの開始から終了までの経路を選択し、前記経路に対応した分岐情報を、前記既出経路に対応した分岐情報として生成し、前記経路候補が前記重複経路であると検出された場合、前記経路候補に対応した前記経路を選択せずに、且つ、前記経路に対応した分岐情報を、前記既出経路に対応した分岐情報として生成しないように制御する
ことを含む処理を実行させるためのテストケース生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
開示の技術は、テストケース生成装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
ソフトウエア開発において、開発対象であるプログラム（被検査プログラム）から、被検査プログラムの開始から終了までに至る経路（パス）を網羅的に抽出し、被検査プログラムの動作を検証する手法が知られている。
【０００３】
パスの抽出法として、例えば、被検査プログラムに含まれる全てのパスを網羅的に抽出するパス網羅、及び被検査プログラムに含まれる全ての条件分岐命令の分岐先を１回以上実行するパス集合を抽出する分岐網羅等が存在する。
【０００４】
そして、このようにして抽出されたパスに基づいて被検査プログラムを網羅的に実行し、被検査プログラムが目的とする動作を行うか否かを判定することで、被検査プログラムの動作を検証する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平１１−２３２１３７号公報
【特許文献２】特開平９−１２８２６６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、パス網羅によるパス抽出では、被検査プログラムに含まれるループ終了条件が具体的な数値でなく、例えばα等のシンボル値を含んで表されている場合、ループ終了条件が不定値となる。従って、ループを継続するパスが無限に存在し、それに伴い抽出されるパスが膨大になる、所謂パス爆発が発生することがある。
【０００７】
パス爆発の防止策として、例えば、パス抽出の方法を分岐網羅とすることで、抽出されるパス数を、パス網羅によって被検査プログラムから抽出されるパス数より減少させる方法が採られる。
【０００８】
しかし、例えば、ＤＡＲＴ（Directed Auto-mated Random Testing）等の公知の分岐網羅では、分岐網羅を実現する最小数のパスよりも、多くのパスが抽出される場合がある。
【０００９】
そこで、開示の技術は、より少数のパスで分岐網羅度を向上させることができるパス集合を被検査プログラムから抽出することを目的とする。
【課題を解決するための手段】
【００１０】
開示の技術は、管理部は、被検査プログラムに含まれる条件分岐の分岐先への分岐実行回数を管理する。検出部は、分岐実行回数から得られる経路候補に対応した分岐情報と、既に抽出された被検査プログラムの既出経路に対応した分岐情報と、を比較して、経路候補が既出経路に含まれる重複経路か否かを検出する。選択部は、条件分岐の分岐実行回数に応じた予め定めた規則に基づいて分岐先を決定して、被検査プログラムの開始から終了までの経路を選択する。生成部は、選択された経路に対応した分岐情報を、既出経路に対応した分岐情報として生成する。制御部は、検出部により経路候補が重複経路ではないと検出された場合、選択部及び生成部の各々による処理を実行し、検出部により経路候補が重複経路であると検出された場合、選択部及び生成部の各々による処理を実行しないように選択部及び生成部を制御する。
【発明の効果】
【００１１】
開示の技術は、一つの側面として、より少数のパスで分岐網羅度を向上させることができるパス集合を被検査プログラムから抽出する効果を有する。
【図面の簡単な説明】
【００１２】
【図１】図１は、被検査プログラムの一例を示した図である。
【図２】図２は、被検査プログラムに係るフローチャートの一例を示した図である。
【図３】図３は、被検査プログラムから抽出されるパスの一例を示した図である。
【図４】図４は、繰り返し処理を含む被検査プログラムの一例を示した図である。
【図５】図５は、外部処理呼び出しを含む被検査プログラムの一例を示した図である。
【図６】図６は、パス爆発の説明に用いられる被検査プログラムの一例を示した図である。
【図７】図７は、第１実施形態に係るテストケース生成装置の機能ブロック図である。
【図８】図８は、深さ優先探索の説明に用いられるパスツリーの一例を示した図である。
【図９】図９は、第１実施形態に係る被検査プログラムの一例を示した図である。
【図１０】図１０は、第１実施形態に係る被検査プログラムのフローチャートの一例を示した図である。
【図１１】図１１は、分岐実行回数の管理について説明するための図である。
【図１２】図１２は、多分岐命令を含む被検査プログラムの一例を示した図である。
【図１３】図１３は、パス選択規則について説明するための図である。
【図１４】図１４は、重複パス検出ルールの生成方法について説明するための図である。
【図１５】図１５は、重複パスの検出について説明するための図である。
【図１６】図１６は、重複パスの検出について説明するための図である。
【図１７】図１７は、テストケース生成装置として機能するコンピュータのブロック図である。
【図１８】図１８は、テストケース生成処理の流れを示すフローチャートである。
【図１９】図１９は、重複パス検出処理の流れを示すフローチャートである。
【図２０】図２０は、第１実施形態に係る分岐実行回数管理処理の流れを示すフローチャートである。
【図２１】図２１は、分岐選択処理の流れを示すフローチャートである。
【図２２】図２２は、第２実施形態に係るテストケース生成装置の機能ブロック図である。
【図２３】図２３は、外部処理内に条件分岐命令を含む被検査プログラムの一例を示した図である。
【図２４】図２４は、第２実施形態に係る分岐実行回数管理処理の流れを示すフローチャートである。
【発明を実施するための形態】
【００１３】
以下、図面を参照して、開示の技術の実施形態の一例を詳細に説明する。
【００１４】
（第１実施形態）
【００１５】
ソフトウエア開発において、シンボリック実行（symbolic execution）技術を利用して、被検査プログラムの動作を検証する手法がある。
【００１６】
シンボリック実行技術とは、被検査プログラムに含まれる変数に具体的な数値を代入する代わりに、数値を代表するシンボル値を代入することで被検査プログラムを疑似的に実行し、被検査プログラムの実行結果を評価する技術である。
【００１７】
そこで、まず被検査プログラムのシンボリック実行について簡単に説明する。
【００１８】
図１は、一例としてＣＯＢＯＬ言語で記述された被検査プログラムを示した図である。なお、以降、被検査プログラムを例示する場合、ＣＯＢＯＬ言語で記述された被検査プログラムを示すものとするが、被検査プログラムがＣＯＢＯＬ言語以外の他のプログラム言語で記述されていてもよいことは言うまでもない。
【００１９】
図１の１３行目のＩＦ文は、変数である性別が‘男性’の場合には１５行目に処理を分岐させ、性別が‘男性’でない場合には１７行目に処理を分岐させる、条件分岐命令の一例である。
【００２０】
また、図１に示した被検査プログラムには、１９行目にもＩＦ文が記述されており、１９行目のＩＦ文では、性別が‘女性’の場合には２１行目に処理を分岐させ、性別が‘女性’ではない場合には２３行目に処理を分岐させる。
【００２１】
図２は、図１の被検査プログラムをフローチャートで示した図である。
【００２２】
このような被検査プログラムに対してシンボリック実行を行うと、変数である性別の値は、被検査プログラムの外部から与えられるため、シンボリック実行の際には不定であり、変数である性別の値はシンボル値として指定される。なお、このように、シンボリック実行の際、シンボル値に置き換えられる変数を外部変数という。
【００２３】
そして、シンボリック実行の結果、図３に示すような実行可能なパス１、パス２、及びパス３を含む３個のパス、及びパス毎のパス条件が抽出される。ここで、パス条件とは、パスが終了するまでに経由する条件分岐のうち、シンボル値を含む全ての条件を積（ＡＮＤ条件：以下、記号∧で表示する）で連結した条件である。換言すれば、パス条件とは、パスに含まれる条件分岐を通過する際に満たすべき論理的な制約ということができる。また、パスが実行可能とは、パス条件が充足可能であることをいう。
【００２４】
パス１は、図２のステップＳ１０、ステップＳ１２、ステップＳ１６、及びステップＳ２０を経由するパスであり、パス２は、図２のステップＳ１０、ステップＳ１４、ステップＳ１６、及びステップＳ１８を経由するパスである。更に、パス３は、図２のステップＳ１０、ステップＳ１４、ステップＳ１６、及びステップＳ２０を経由するパスである。
【００２５】
パス１、パス２、及びパス３の各々のパス条件は、論理的に成立するため、充足可能である。なお、パス条件において、‘！’はＮＯＴ条件を表す。すなわち、‘！＝’は右辺と左辺がイコールでないことを表している。
【００２６】
一方、パス４は、図２のステップＳ１０、ステップＳ１２、ステップＳ１６、及びステップＳ１８を経由するパスであるが、この際、パス４のパス条件は、（性別＝男性）∧（性別＝女性）となる。従って、パス４のパス条件は論理的に成立しない。すなわち、パス４のパス条件は充足可能でないためパス４は実行可能と判定されず、パスとして抽出されない。
【００２７】
なお、パス条件の充足可能性の判定には、例えばＳＡＴ（satisfiability）、又はＳＭＴ（satisfiabilitymodulo theory）ソルバ等の制約ソルバが利用される。
【００２８】
このようにしてシンボリック実行により抽出された実行可能なパスの各々がテストケースとして生成され、パス毎のパス条件を充足する外部変数の値が、各テストケースに対応した被検査プログラムのテストデータとなる。
【００２９】
シンボリック実行におけるパス探索のアルゴリズムとして、パス網羅を実現するパス抽出法の１つである、深さ優先探索アルゴリズムが用いられることがある。
【００３０】
深さ優先探索アルゴリズムは、被検査プログラムの開始点から終了点に向かって１つのパスを探索した後、探索したパス上をパスの分岐点がある地点まで遡り、当該分岐点でまだ選択されていない分岐先の経路を順次辿ることを繰り返すアルゴリズムである。
【００３１】
シンボリック実行では、深さ優先探索アルゴリズムにより探索されたパスに対応するパス条件に対して、既に説明した制約ソルバを用いてパスの充足可能性を判定し、実行可能なパスを抽出する。
【００３２】
しかし、シンボリック実行時のパスの探索に深さ優先探索アルゴリズムを用いた場合、抽出されるパスの個数が、現実的には処理しきれない程度の膨大な数になる、所謂パス爆発が発生することがある。
【００３３】
パス爆発が発生する原因としては、以下の２つの場合が考えられる。
【００３４】
パス爆発の１つ目の原因は、被検査プログラムの実行しうるパスの個数が無限にある場合である。例えば、被検査プログラムに繰り返し処理が含まれ、且つ、繰り返し終了条件にシンボル値が含まれる場合がこのケースに相当する。
【００３５】
例えば、図４に示した被検査プログラムは、１０行目から１４行目にかけて繰り返し処理が含まれており、繰り返し処理を実行する度に、カウンタ変数の値を１ずつ増加させ、カウンタ変数の値が閾値変数より大きくなった場合に、繰り返し処理を終了する。
【００３６】
ここで、閾値変数は外部変数であるため、シンボリック実行の際、シンボル値として実行される。すなわち、シンボリック実行の際には閾値変数の値が不定となることから、繰り返し処理を継続するパスが常に存在し、パスの個数が無限となる。
【００３７】
また、図５に示した被検査プログラムは、１５行目に実行先を外部処理に分岐させるＰＥＲＦＯＲＭ文を含んでおり、１６行目に、外部処理に含まれるＣＡＬＬ文の戻り値に従って実行先を決定する条件分岐を含んでいる。なお、外部処理はサブルーチンとも称される場合がある。
【００３８】
１６行目の条件分岐では、戻り値が０の場合に外部処理を再帰呼び出しするため、ＣＡＬＬ文の戻り値がシンボル値である場合、ＣＡＬＬ文の戻り値が不定となることから、再帰呼び出し処理を継続するパスが常に存在し、パスの個数が無限となる。
【００３９】
パス爆発の２つ目の原因は、シンボリック実行におけるパス抽出の際、パス抽出に要する分析時間が現実的な時間を超過したり、パス抽出に要するメモリ量が、コンピュータに実装されているメモリ量を超過したりする場合である。例えば、被検査プログラムに、条件分岐命令が連続して多用されている場合がこのケースに相当する。
【００４０】
ここで、パス抽出に要する分析時間が現実的な時間を超過するとは、例えば、被検査プログラムに含まれるパスを抽出し終えるまでに要する時間が、予め予定された被検査プログラムの動作検証工程期間内に収まらない場合等をいう。
【００４１】
例えば、図６に示した被検査プログラムは、独立したＩＦ文を２０個含んでいる。このような独立したＩＦ文がＮ個連続する場合、パス数は２のＮ乗個となり、図６の例では２の２０乗個、すなわち１０４８５７６個のパスが被検査プログラムから抽出される。
【００４２】
一例として、コンピュータに実装されているメモリ量が１ＧＢ（ギガバイト）である場合、独立したＩＦ文を１５個含む被検査プログラムのパスを抽出することができる。しかし、独立したＩＦ文を１６個含む被検査プログラムのパスを抽出しようとすると、メモリ不足が発生し、被検査プログラムからパスを抽出できない。
【００４３】
この場合、コンピュータに実装するメモリ量を６倍の６ＧＢに増設しても、独立したＩＦ文を１８個含む被検査プログラムのパスまでしか抽出することができない。この例からもわかるように、独立したＩＦ文が連続することで、容易にパス爆発が発生することが理解される。
【００４４】
そこで、シンボリック実行におけるパス爆発を防止するパス抽出法として、深さ優先探索アルゴリズムに代表されるパス網羅より抽出パス数が抑制される分岐網羅、命令網羅等が用いられる場合がある。なお、命令網羅とは、被検査プログラムに含まれる全ての命令を実行するパス集合を抽出するパス抽出法である。
【００４５】
従来のパス爆発を防止するパス抽出法として、例えば、分岐ランダム探索方式、制御フローグラフ（Control Flow Graph：ＣＦＧ）を利用する方式、及びＤＡＲＴ等が存在する。
【００４６】
分岐ランダム探索方式とは、シンボリック実行で到達した条件分岐が分岐可能ならば、分岐先をランダムに選択して被検査プログラムからパスを抽出する方法である。ＣＦＧを利用する方式とは、まず、シンボリック実行する際に通過する可能性のある被検査プログラムの全経路をグラフで表した、所謂ＣＦＧを生成する。そして、生成したＣＦＧ上の未通過の命令文にシンボリック実行ラインが到達するように条件分岐の重み付けを行い、条件分岐の分岐先を、分岐条件の重み付けに基づいて決定する方法である。
【００４７】
また、ＤＡＲＴとは、分岐ランダム探索方式の改良版であり、まず、外部変数に具体的な値をランダムに設定した上で被検査プログラムを実行し、当該パス上のパス条件を収集する。次に、収集したパス条件から、既に通過したパスと異なるパスを通過する値を生成して、被検査プログラムから順次パスを抽出する。
【００４８】
以下に、図６に示した被検査プログラムから、ＤＡＲＴを用いてパスを抽出する例について説明する。
【００４９】
手順Ａ：項目１〜項目２０の各々の外部変数の値を、仮に‘１’として設定する。
手順Ｂ：項目１〜項目２０の各々の外部変数の値によりパス条件を収集する。例えば、手順Ａで設定した外部変数値を用いた場合、「（項目１＝１）∧（項目２＝１）∧・・・∧（項目２０＝１）」のパス条件が収集される。
手順Ｃ：次に、手順Ｂで収集したパス条件の一部を否定したパス条件、例えば「！（項目１＝１）∧（項目２＝１）∧・・・∧（項目２０＝１）」を作成し、パス条件を充足する値を導き出す。本例の場合、例えば、項目１＝‘２’、項目２〜項目２０＝‘１’の値が得られる。
【００５０】
以降、パス抽出に関する終了条件、例えば分岐網羅を満たすまで手順Ｂ及び手順Ｃを繰り返し、被検査プログラムからパスを抽出する。
【００５１】
しかしながら、分岐ランダム探索方式、ＣＦＧを利用する方式、及びＤＡＲＴには、以下に示すような問題点が存在する。
【００５２】
分岐ランダム探索方式では、条件分岐の分岐先をランダムに選択するため、未通過の分岐先を意図的に選択することができない。従って、分岐網羅を実現するテストケースを得ようとした場合、パス探索の繰り返し回数が増大する上、被検査プログラムから抽出されるパス数も偶然性に左右されるという問題点が存在する。
【００５３】
ＣＦＧを利用する方式では、被検査プログラムを静的解析して、被検査プログラムに含まれる全経路を予めグラフ化した上で、更に、条件分岐の重み付けを実施する必要がある。従って、１つのパスに数十程度の条件分岐が含まれるような大規模な被検査プログラムへＣＦＧを利用する方法を適用した場合、被検査プログラムの静的解析に要する計算量が増大し、計算時間及びメモリ量等の制約から適用困難となる場合がある。
【００５４】
また、ＤＡＲＴでは、分岐網羅を実現するパス集合を生成する際、分岐網羅を実現する最小のパス集合に比べて、より多くのパスを含んだパス集合を生成してしまうという問題点が存在する。
【００５５】
例えば、既に説明したように、ＤＡＲＴによって図６に示した被検査プログラムからパスを抽出する場合、まず、手順Ａで収集したパス条件に対応したパスが１つ抽出される。そして、手順Ａで収集したパス条件に対して、（項目１＝１）から（項目２０＝１）までの各分岐条件を順次否定しながら２０個のパスを抽出することから、手順Ａで抽出したパスと合わせて、合計２１個のパスが抽出されることになる。
【００５６】
しかし、図６に示した被検査プログラムの場合、例えば、各条件分岐において全てＴＨＥＮ側に分岐するパスと、全てＥＬＳＥ側に分岐するパスとの２つのパスで分岐網羅を実現することができるため、分岐網羅を実現する最小のパス数は２となる。
【００５７】
一方、開示の技術は、従来の分岐網羅に用いられるパス抽出法と比較して、より少数のパスで分岐網羅度を向上させることができるパス集合を被検査プログラムから抽出する。
【００５８】
図７には、本実施の形態に係るテストケース生成装置１０が示されている。テストケース生成装置１０は、入力部１２、シンボリック実行部１４、制御部１６、深さ優先探索部１８、管理部２０、選択部２２、生成部２４、検出部２６、及び出力部２８を含む。
【００５９】
テストケース生成装置１０は、シンボリック実行技術により被検査プログラム３０を実行し、被検査プログラム３０の動作を検証するためのテストケース３２を生成するための装置である。
【００６０】
入力部１２は、被検査プログラム３０を受け付け、被検査プログラム３０をテストケース生成装置１０内部に取り込む。
【００６１】
シンボリック実行部１４は、入力部１２を介して受け付けた被検査プログラム３０に含まれる外部変数に具体的な値を設定する代わりにシンボル値を設定する。そして、外部変数をシンボル値としたまま、制御部１６によって探索された被検査プログラム３０に含まれるパスを模擬的に実行し、被検査プログラム３０からパスを抽出する。そして、実行したパス毎にパス条件を抽出し、１つのパスと当該パスに対応したパス条件の組み合わせを１つのテストケースとして、複数のテストケースを生成する。また、各テストケースのパス条件を充足する外部変数の値を生成し、テストケースに対応した被検査プログラム３０のテストデータとする。
【００６２】
制御部１６は、シンボリック実行の際に、後述する深さ優先探索部１８、管理部２０、選択部２２、生成部２４、及び検出部２６の各機能部を制御して、被検査プログラム３０に含まれるパスの探索を実行する。そして、制御部１６は、探索したパスをシンボリック実行部１４に引き渡す。
【００６３】
深さ優先探索部１８は、深さ優先探索アルゴリズムに基づいて、被検査プログラム３０から網羅的にパスを探索する。
【００６４】
図８は、深さ優先探索部１８において実行される、図６に示した被検査プログラムのパス探索のアルゴリズムを説明した図である。
【００６５】
任意のパス１が探索されると、パス１終点から（項目２０＝１）の分岐点まで遡り、未選択の分岐側を選択してパス２を探索する。次に、パス２終点から未選択の分岐先を有する分岐点、この場合（項目１９＝１）の分岐点まで遡り、未選択の分岐側を選択してパス３を探索する。以後、同様の処理を繰り返して、被検査プログラム３０に含まれるパスを網羅的に探索する。
【００６６】
なお、深さ優先探索部１８は、被検査プログラム３０からパスを網羅的に探索する場合に制御部１６によって呼び出される機能部であり、テストケース生成装置１０が分岐網羅によるパス抽出を実行する場合には、必須の機能部ではない。
【００６７】
管理部２０は、制御部１６によって探索されたパスの実行順に基づいて、被検査プログラム３０に含まれる条件分岐毎に、分岐先への分岐実行回数を管理する。以下では、管理部２０の機能について詳細に説明する。
【００６８】
図９は、本実施の形態に係る被検査プログラム３０の一例を示した図である。図９に示した被検査プログラム３０には、条件分岐命令であるＩＦ文が１３行目、１９行目、及び２５行目の合計３箇所に存在する。また、１６行目、２０行目、２６行目、及び３６行目に、被検査プログラム３０の終了を意味する「ＥＸＩＴ  ＰＲＯＧＲＡＭ」が存在する。
【００６９】
図１０は、図９に示した被検査プログラム３０をフローチャートで示した図である。ステップＳ３０、ステップＳ３４、及びステップＳ３８の各処理が、それぞれ図９の被検査プログラム３０の１３行目、１９行目、及び２５行目の条件分岐に対応する。また、ステップＳ３２、ステップＳ３６、及びステップＳ４０の各処理が、それぞれ図９の被検査プログラム３０の１４行目、２２行目、及び２８行目の処理に対応する。
【００７０】
図１１は、管理部２０で実行される、図９に示した被検査プログラム３０の管理内容を示した図である。まず、管理部２０は、被検査プログラム３０から条件分岐命令であるＩＦ文を取得する。そして、管理部２０は、制御部１６によって初めて被検査プログラム３０のパス探索が開始される前の状態、すなわち初期状態において、各ＩＦ文の分岐実行回数を、例えば「直接＝（０、０）」のように初期化する。ここで、「直接」とは、対応するＩＦ文がＰＥＲＦＯＲＭ文等で呼び出される外部処理のＩＦ文として実行されるものではないことを意味している。また、（０、０）とは、並び順に、ＩＦ文におけるＴＨＥＮ側の分岐実行回数、ＥＬＳＥ側の分岐実行回数を表している。
【００７１】
例えば、制御部１６によって、図１０に示すステップＳ３０→ステップＳ３２→ステップＳ３４→エンドで表されるパスが探索されたとする。この場合、１３行目のＩＦ文ではＴＨＥＮ側の分岐（ＴＨＥＮ分岐）が選択されたため、ＩＦ文（１３行目）のＴＨＥＮ側の分岐実行回数を１増やして、「直接＝（１、０）」とする。また、１９行目のＩＦ文でもＴＨＥＮ分岐が選択されたため、ＩＦ文（１９行目）の分岐実行回数を、「直接＝（１、０）」とする。
【００７２】
次に、制御部１６によって、例えば、ステップＳ３０→エンドで表されるパスが探索されたとする。この場合、１３行目のＩＦ文ではＥＬＳＥ側の分岐（ＥＬＳＥ分岐）が選択されたため、ＩＦ文（１３行目）のＥＬＳＥ側の分岐実行回数を１増やして、「直接＝（１、１）」とする。
【００７３】
引き続き、制御部１６によって、例えば、ステップＳ３０→ステップＳ３２→ステップＳ３４→ステップＳ３６→ステップＳ３８→エンドで表されるパスが探索されたとする。この場合、上記と同様の方法により、ＩＦ文（１３行目）の分岐実行回数を「直接＝（２、１）」、ＩＦ文（１９行目）の分岐実行回数を「直接＝（１、１）」、ＩＦ文（２５行目）の分岐実行回数を「直接＝（１、０）」とする。
【００７４】
以下、制御部１６によってパスが探索される度に、上記に説明した方法に従って、探索されたパスによって実行されたＩＦ文の分岐実行回数を更新する。
【００７５】
なお、条件分岐命令には、ＩＦ文の他に、複数の異なる処理の中から条件に合った処理を選択するＥＶＡＬＵＡＴＥ文のような多分岐命令も含まれる。
【００７６】
図１２は、ＥＶＡＬＵＡＴＥ文が含まれる被検査プログラム３０の例を示した図である。
【００７７】
図１２に示した被検査プログラム３０には、１２行目及び２３行目に２つのＥＶＡＬＵＡＴＥ文が含まれている。
【００７８】
管理部２０は初期状態において、１２行目のＥＶＡＬＵＡＴＥ文の分岐実行回数を、例えば「直接＝（０、０、０、０）」のように初期化する。ここで（０、０、０、０）とは、並び順に、変数１が‘Ａ’の場合の分岐実行回数、変数１が‘Ｂ’の場合の分岐実行回数、変数１が‘Ｃ’の場合の分岐実行回数、変数１が‘Ａ’、‘Ｂ’、‘Ｃ’の何れの場合にも該当しない場合の分岐実行回数を表している。
【００７９】
また、管理部２０は初期化状態において、２３行目のＥＶＡＬＵＡＴＥ文の分岐実行回数を、例えば「直接＝（０、０、０）」のように初期化する。
【００８０】
そして、管理部２０は、ＩＦ文における分岐実行回数の管理と同様に、ＥＶＡＬＵＡＴＥ文の分岐実行回数を管理する。例えば制御部１６によって、１４行目及び２５行目のＤＩＳＰＬＡＹ文を実行するパスが探索された場合、ＥＶＡＬＵＡＴＥ文（１２行目）の分岐実行回数は、「直接＝（１、０、０、０）」となる。また、ＥＶＡＬＵＡＴＥ文（２３行目）の分岐実行回数は、「直接＝（１、０、０）」となる。
【００８１】
選択部２２は、制御部１６が被検査プログラム３０からパスを探索する際に、制御部１６から呼び出される機能部であり、パスが条件分岐に到達する毎に予め定めたパス選択規則に従って、分岐先を選択する。ここで、パス選択規則とは、条件分岐における分岐先を選択するための規則である。
【００８２】
パス選択規則の一例として、例えば、選択部２２は、パス上の条件分岐命令が分岐可能である場合に、管理部２０によって管理される条件分岐毎の分岐実行回数に基づいて、分岐実行回数が少ない方の分岐を選択する。なお、条件分岐の分岐実行回数が同数である場合には、予め定めた選択規則に従って、分岐先を選択する。
【００８３】
ここで、予め定めた選択規則とは、例えば条件分岐命令における最初の分岐を選択する等の規則をいう。具体的には、一例として、ＩＦ文の分岐実行回数が同数である場合、ＴＨＥＮ分岐を選択する。なお、予め定めた選択規則はこれに限定されるものではなく、例えば、ＥＬＳＥ分岐を選択するようにしてもよい。
【００８４】
また、条件分岐命令が分岐可能とは、条件分岐命令における各々の分岐の分岐条件が、共に充足可能である状態をいう。
【００８５】
例えば、図９に示した被検査プログラム３０の１３行目のＩＦ文は、（項目１＝１）か否かが分岐条件となる。この場合、ＴＨＥＮ分岐は分岐条件：（項目１＝１）がＴＲＵＥの場合に選択される。一方、ＥＬＳＥ分岐は分岐条件：（項目１＝１）がＦＡＬＳＥの場合に選択されるが、これは、分岐条件：！（項目１＝１）がＴＲＵＥの場合に選択されると解釈することができる。
【００８６】
分岐条件に含まれる変数：項目１は外部変数であるため、図９に示した被検査プログラム３０単体でシンボリック実行した場合には、変数：項目１はシンボル値に置き換えられる。従って、分岐条件：（項目１＝１）の真偽値を確定することができない。
【００８７】
そこで選択部２２は、ＴＨＥＮ分岐の分岐条件：（項目１＝１）、及びＥＬＳＥ分岐の分岐条件：！（項目１＝１）の充足可能性を判断する。この場合、ＴＨＥＮ分岐の分岐条件とＥＬＳＥ分岐の分岐条件は共に充足可能であることから、選択部２２は、図９に示した被検査プログラム３０の１３行目のＩＦ文を分岐可能と判定し、ＴＨＥＮ分岐とＥＬＳＥ分岐の２つの分岐の中から分岐先を選択する。
【００８８】
図１３は、選択部２２において、既に説明したパス選択規則のみに従って、図９に示した被検査プログラム３０から探索されたパスの一例を示した図である。
【００８９】
図１１に示したように、１回目のパス探索前では、管理部２０によって管理される条件分岐毎の分岐実行回数は初期状態にある。
【００９０】
従って、１回目のパス探索では、ＩＦ文（１３行目）は分岐可能であり、且つ、分岐実行回数が（０、０）であることから、ＴＨＥＮ分岐が選択される。そして、ＩＦ文（１９行目）も分岐可能であり、且つ、分岐実行回数が（０、０）であることから、ＴＨＥＮ分岐が選択され、図１０におけるステップＳ３０→ステップＳ３２→ステップＳ３４→エンドで表されるパス１が選択される。
【００９１】
次いで、２回目のパス探索では、ＩＦ文（１３行目）の分岐実行回数が管理部２０によって（１、０）に更新されていることから、分岐実行回数がより少ないＥＬＳＥ分岐が選択され、図１０におけるステップＳ３０→エンドで表されるパス２が選択される。
【００９２】
次いで、３回目のパス探索では、ＩＦ文（１３行目）の分岐実行回数が管理部２０によって（１、１）に更新されていることから、ＴＨＥＮ分岐が選択される。そして、ＩＦ文（１９行目）の分岐実行回数も管理部２０によって（１、０）に更新されていることから、分岐実行回数がより少ないＥＬＳＥ分岐が選択される。そして、ＩＦ文（２５行目）の分岐実行回数は初期状態のまま（０、０）であることから、ＴＨＥＮ分岐が選択され、図１０におけるステップＳ３０→ステップＳ３２→ステップＳ３４→ステップＳ３６→ステップＳ３８→エンドで表されるパス３が選択される。
【００９３】
以降、分岐網羅が実現されるまで、選択部２２において同様のパス選択規則を繰り返すことで、図１３におけるパス１からパス７までの７個のパスが選択される。
【００９４】
生成部２４は、選択部２２によって選択された被検査プログラム３０のパスに対して、既に選択部２２によって選択されたパス（既出パス）であることを示すための、パスの重複を検出するためのルール（重複パス検出ルール）を生成する。
【００９５】
図１４は、図９に示した被検査プログラム３０を例にして、生成部２４における重複パス検出ルールの生成方法の一例を示した図である。
【００９６】
生成部２４は、後述する検出部２６により生成される優先分岐番号と、選択部２２でパス選択規則に従って選択されたパスと、に基づいて、重複パス検出ルールを生成する。ここで、優先分岐番号とは、選択部２２がパス選択規則に従った場合に、次に選択される条件分岐毎の分岐先を表す番号である。
【００９７】
図１４に示すように、初期状態では管理部２０によって管理される全ての条件分岐の分岐実行回数は（０、０）となるため、条件分岐の各々では、パス選択規則に基づいてＴＨＥＮ分岐が選択されることになる。従って、例えばＴＨＥＮ分岐を‘０’、ＥＬＳＥ分岐を‘１’で表した場合、検出部２６では、ＩＦ文（１３行目）、ＩＦ文（１９行目）、ＩＦ文（２５行目）の各々の条件分岐の分岐先を‘０’に設定した優先分岐番号を生成する。
【００９８】
一方、シンボリック実行部１４によって、選択部２２で選択されたパスに沿ってシンボリック実行が行われ、被検査プログラム３０からパスが抽出されると、管理部２０によって管理される条件分岐毎の分岐実行回数が、抽出されたパスの実行に伴い更新される。
【００９９】
生成部２４は、抽出されたパスによって被検査プログラム３０の分岐網羅度が向上した場合に、抽出されたパスによって実行された条件分岐に対応した優先分岐番号を重複パス検出ルールとして生成する。
【０１００】
例えば、生成部２４は、図１４において、１回目のシンボリック実行により図１３に示すパス１が抽出された場合、「優先分岐番号が｛（ＩＦ文（１３行目）＝０）∧（ＩＦ文（１９行目）＝０）｝ならば、パス１と重複する」というルール１を生成する。
【０１０１】
図１４では、説明を簡略化するため、例えば、被検査プログラム３０に含まれる各々の条件分岐に対応した優先分岐番号のうち、何れの優先分岐番号が重複パス検出ルールに適用されるのかを示す識別子‘＊’を優先分岐番号に対応した判定欄に付与している。
【０１０２】
１回目のシンボリック実行後、検出部２６は、管理部２０によって管理される条件分岐毎の分岐実行回数に基づいて、優先分岐番号を生成する。１回目のシンボリック実行後、ＩＦ文毎の分岐実行回数は図１４に示すように、｛（１、０）、（１、０）、（０、０）｝となる。ここで、１番目の小括弧はＩＦ文（１３行目）の分岐実行回数、２番目の小括弧はＩＦ文（１９行目）の分岐実行回数、３番目の小括弧はＩＦ文（２５行目）の分岐実行回数を表す。
【０１０３】
従って、パス選択規則に基づいて、１回目のシンボリック実行後に生成される優先分岐番号は（１、１、０）となる。ここで、１番目の数値はＩＦ文（１３行目）の優先分岐番号、２番目の数値はＩＦ文（１９行目）の優先分岐番号、３番目の数値はＩＦ文（２５行目）の優先分岐番号を表す。
【０１０４】
そして生成部２４は、２回目のシンボリック実行により図１３に示すパス２が抽出された場合、「優先分岐番号が（ＩＦ文（１３行目）＝１）ならば、パス２と重複する」というルール２を生成する。
【０１０５】
２回目のシンボリック実行後、管理部２０によって管理される条件分岐毎の分岐実行回数は、図１４に示すように、｛（１、１）、（１、０）、（０、０）｝となる。従って、パス選択規則に基づいて、２回目のシンボリック実行後に生成される優先分岐番号は、（０、１、０）となる。そして生成部２４は、３回目のシンボリック実行により図１３に示すパス３が抽出された場合、「優先分岐番号が｛（ＩＦ文（１３行目）＝０）∧（ＩＦ文（１９行目）＝１）∧（ＩＦ文（２５行目）＝０）｝ならば、パス３と重複する」というルール３を生成する。
【０１０６】
以降、同様の処理に従って、生成部２４は、シンボリック実行によるパスの抽出が終了するまで、重複パス検出ルールを生成する。なお、優先分岐番号は、分岐情報の一例である。
【０１０７】
既に説明したように、選択部２２でパス選択規則のみに従って図９に示した被検査プログラム３０からパスの選択をした場合、例えば、図１３に示すような分岐網羅を実現する７つのパスが選択される場合がある。
【０１０８】
しかし、この場合、パス４及びパス６はパス２と重複したパスであり、パス５はパス１と重複したパスである。従って、パス４、パス６、及びパス５に基づいたシンボリック実行から新たなテストケースが生成されることはなく、テストケースの生成時間が無駄になるばかりか、被検査プログラム３０の品質向上に寄与しない重複したテストケースが生成されることになる。
【０１０９】
従って、検出部２６は、管理部２０によって管理される条件分岐毎の分岐実行回数に基づき、パス探索前にパス選択規則に従って優先分岐番号を生成し、優先分岐番号によって表されるパス候補を取得する。そして、検出部２６は、選択部２２によるパスの選択前に、パス候補に対応した優先分岐番号と、生成部２４で生成された重複パス検出ルールとを比較して、次のシンボリック実行により抽出される予定のパスが、既出パスと一致するか否かを検出する。
【０１１０】
図１５及び図１６は、図９に示した被検査プログラム３０に対する検出部２６の処理を示した図である。
【０１１１】
検出部２６は、初期状態における条件分岐毎の分岐実行回数に基づいて、パス選択規則に従い、優先分岐番号を生成する。この際に生成される優先分岐番号は（０、０、０）となる。そして、検出部２６は、生成された優先分岐番号と、生成部２４によって生成された重複パス検出ルールとを比較して、重複パス検出ルールの中に、生成された優先分岐番号によって表されるパス候補と重複するルールが存在するか否かを判定する。
【０１１２】
そして、検出部２６は、生成された優先分岐番号によって表されるパス候補と重複するルールが存在する場合には、シンボリック実行部１４でのシンボリック実行によるパス抽出処理が行われないようにする。一方、検出部２６は、生成された優先分岐番号によって表されるパス候補と重複するルールが存在しない場合には、シンボリック実行部１４でのシンボリック実行によるパス抽出処理が行われるようにする。
【０１１３】
具体的には、テストケース生成装置１０が初期状態の場合、まだ重複パス検出ルールが存在しないため、選択部２２において図１３のパス１が選択され、生成部２４においてパス１に対応した重複パス検出ルール：ルール１が生成される。
【０１１４】
１回目の重複パス検出処理後、管理部２０によって管理される条件分岐毎の分岐実行回数は、図１５に示すように、｛（１、０）、（１、０）、（０、０）｝となる。従って、次に検出部２６によって生成される優先分岐番号は、（１、１、０）となる。この場合、重複パス検出ルールにはルール１しか存在しないため、生成された優先分岐番号によって表されるパス候補と重複するルールは存在しない。従って、選択部２２において図１３のパス２が選択され、生成部２４においてパス２に対応した重複パス検出ルール：ルール２が生成される。
【０１１５】
２回目の重複パス検出処理後、管理部２０によって管理される条件分岐毎の分岐実行回数は、図１５に示すように、｛（１、１）、（１、０）、（０、０）｝となる。従って、次に検出部２６によって生成される優先分岐番号は、（０、１、０）となる。この場合、重複パス検出ルールにはルール１及びルール２が存在するが、生成された優先分岐番号によって表されるパス候補と重複するルールは存在しない。従って、選択部２２において図１３のパス３が選択され、生成部２４においてパス３に対応した重複パス検出ルール：ルール３が生成される。
【０１１６】
３回目の重複パス検出処理後、管理部２０によって管理される条件分岐毎の分岐実行回数は、図１５に示すように、｛（２、１）、（１、１）、（１、０）｝となる。従って、次に検出部２６によって生成される優先分岐番号は、（１、０、１）となる。この場合、重複パス検出ルールにはルール１、ルール２、及びルール３が存在し、生成された優先分岐番号によって表されるパス候補とルール２が一致する。従って、重複パス検出ルールと一致するパス候補に従ったシンボリック実行によるパス抽出処理が省略される。具体的には、選択部２２におけるパスの選択処理、及び生成部２４における重複パス検出ルールの生成処理が省略される。ただし、生成された優先分岐番号によって表されるパス候補と、重複パス検出ルールとが一致した場合であっても、管理部２０は、パス候補の生成に伴って、条件分岐毎の分岐実行回数を更新する。
【０１１７】
４回目の重複パス検出処理後、管理部２０によって管理される条件分岐毎の分岐実行回数は、図１６に示すように、｛（２、２）、（１、１）、（１、０）｝となる。従って、次に検出部２６によって生成される優先分岐番号は、（０、０、１）となる。この場合、重複パス検出ルールにはルール１、ルール２、及びルール３が存在し、生成された優先分岐番号によって表されるパス候補とルール１が一致する。従って、重複パス検出ルールと一致するパス候補に従ったシンボリック実行によるパス抽出処理が省略される。
【０１１８】
５回目の重複パス検出処理後、管理部２０によって管理される条件分岐毎の分岐実行回数は、図１６に示すように、｛（３、２）、（２、１）、（１、０）｝となる。従って、次に検出部２６によって生成される優先分岐番号は、（１、１、１）となる。この場合、重複パス検出ルールにはルール１、ルール２、及びルール３が存在し、生成された優先分岐番号によって表されるパス候補とルール２が一致する。従って、重複パス検出ルールと一致するパス候補に従ったシンボリック実行によるパス抽出処理が省略される。
【０１１９】
６回目の重複パス検出処理後、管理部２０によって管理される条件分岐毎の分岐実行回数は、図１６に示すように、｛（３、３）、（２、１）、（１、０）｝となる。従って、次に検出部２６によって生成される優先分岐番号は、（０、１、１）となる。この場合、重複パス検出ルールには、生成された優先分岐番号によって表されるパス候補と重複するルールは存在しない。従って、選択部２２において図１３のパス７が選択され、生成部２４においてパス７に対応した重複パス検出ルール：ルール４が生成される。なお、ルール４は、「優先分岐番号が｛（ＩＦ文（１３行目）＝０）∧（ＩＦ文（１９行目）＝１）∧（ＩＦ文（２５行目）＝１）｝ならば、パス７と重複する」というルールとなる。
【０１２０】
７回目の重複パス検出処理後、管理部２０によって管理される条件分岐毎の分岐実行回数は、図１６に示すように、｛（４、３）、（２、２）、（１、１）｝となる。この場合、被検査プログラム３０に含まれる条件分岐毎の分岐実行回数の各々が１以上であることから、パス１、パス２、パス３、及びパス７によって分岐網羅が実現されることになる。従って、検出部２６は重複パスの検出処理を終了する。
【０１２１】
以上に説明したテストケース生成装置１０は、例えば、図１７に示すコンピュータ４０で実現することができる。コンピュータ４０は、ＣＰＵ４２、メモリ４４、及び不揮発性の記憶部４６を含み、これらはバス４８を介して互いに接続される。
【０１２２】
また、記憶部４６はＨＤＤ（Hard Disk Drive）又はフラッシュメモリ等によって実現できる。記憶媒体としての記憶部４６には、コンピュータ４０を被検査プログラム３０に対するテストケース生成装置１０として機能させるためのテストケース生成プログラム５０が記憶されている。ＣＰＵ４２は、テストケース生成プログラム５０を記憶部４６から読み出してメモリ４４に展開し、テストケース生成プログラム５０に含まれる各種プロセスを順次実行する。
【０１２３】
テストケース生成プログラム５０は、シンボリック実行プロセス５２、制御プロセス５４、管理プロセス５６、選択プロセス５８、生成プロセス６０、検出プロセス６２、深さ優先探索プロセス６４、入力プロセス６６、及び出力プロセス６８を含む。
【０１２４】
ＣＰＵ４２は、シンボリック実行プロセス５２を実行することで、図７に示すシンボリック実行部１４として動作する。また、ＣＰＵ４２は、制御プロセス５４を実行することで、図７に示す制御部１６として動作する。また、ＣＰＵ４２は、管理プロセス５６を実行することで、図７に示す管理部２０として動作する。また、ＣＰＵ４２は、選択プロセス５８を実行することで、図７に示す選択部２２として動作する。また、ＣＰＵ４２は、生成プロセス６０を実行することで、図７に示す生成部２４として動作する。また、ＣＰＵ４２は、検出プロセス６２を実行することで、図７に示す検出部２６として動作する。また、ＣＰＵ４２は、深さ優先探索プロセス６４を実行することで、図７に示す深さ優先探索部１８として動作する。また、ＣＰＵ４２は、入力プロセス６６を実行することで、図７に示す入力部１２として動作する。また、ＣＰＵ４２は、出力プロセス６８を実行することで、図７に示す出力部２８として動作する。
【０１２５】
以上により、テストケース生成プログラム５０を実行したコンピュータ４０が、テストケース生成装置１０として動作する。なお、テストケース生成プログラム５０は、開示の技術におけるテストケース生成プログラムの一例を示したものである。
【０１２６】
なお、テストケース生成装置１０は、例えば半導体集積回路、より詳しくはＡＳＩＣ（Application Specific Integrated Circuit)等で実現することも可能である。
【０１２７】
次に、本実施の形態に係るテストケース生成装置１０の作用を説明する。本実施の形態に係るテストケース生成装置１０は、入力部１２に被検査プログラム３０が入力されると、図１８に示すテストケース生成処理を実行する。なお、以下では、入力部１２に入力される被検査プログラム３０として、図９に示した被検査プログラム３０を例に説明するものとする。また、テストケース生成プログラム５０を記憶部４６から読み出してメモリ４４に展開する際、メモリ４４の予め定めた領域に記憶される、被検査プログラム３０の条件分岐毎の分岐実行回数は、｛（０、０）、（０、０）、（０、０）｝に初期化される。また、生成部２４によって生成される重複パス検出ルールも、何れのルールも含まないように初期化される。
【０１２８】
ステップＳ１００では、入力部１２が、入力部１２に入力された被検査プログラム３０を取得して、例えばメモリ４４に記憶する。更に、入力部１２は、被検査プログラム３０が入力されたことをシンボリック実行部１４に通知する。
【０１２９】
ステップＳ１０２では、シンボリック実行部１４が、被検査プログラム３０に対するパス探索の終了条件を満たしたか否かを判定する。
【０１３０】
ここで、パス探索の終了条件とは、以下の３つの条件のうち、何れか１つの条件が成立することを言う。
【０１３１】
（終了条件１）既出パスにより分岐網羅が達成されること。
（終了条件２）分岐網羅度が収束回数に亘って変化しないこと。
（終了条件３）パスの探索回数が、パス探索回数に達すること。
【０１３２】
（終了条件１）は、例えば、管理部２０によってメモリ４４に記憶された、被検査プログラム３０に含まれる条件分岐毎の分岐実行回数の各々が１以上となっている場合に、パス探索を終了する条件である。
【０１３３】
（終了条件２）は、例えば、被検査プログラム３０に含まれる全ての分岐数に対する実際にパス探索された分岐数の割合が、予め定めた収束回数に亘って連続して変化しない場合に、パス探索を終了する条件である。
【０１３４】
具体的には、条件分岐毎の分岐実行回数が｛（１、１）、（１、０）、（０、０）｝であれば、被検査プログラム３０に含まれる全ての分岐数は６であり、実際にパス探索された分岐数は３であるので、分岐網羅度は５０％となる。この分岐網羅度の状態からパス探索を繰り返しても、収束回数連続して分岐網羅度が５０％のまま変化しない場合に、条件が成立したものとして判定される。
【０１３５】
（終了条件３）は、シンボリック実行部１４が制御部１６へパス探索指示を通知して制御部１６にパスの探索を実施させた回数が、予め定めたパス探索回数に達した場合に、パス探索を終了する条件である。
【０１３６】
なお、収束回数及びパス探索回数は、予め記憶部４６に記憶されているものとするが、例えば、入力部１２を介して取得し、記憶部４６に記憶するようにしてもよい。
【０１３７】
シンボリック実行部１４によってパス探索の終了条件が成立したと判定された場合には、シンボリック実行を終了してステップＳ１０４へ移行する。パス探索の終了条件がまだ成立していないと判定された場合には、シンボリック実行部１４が制御部１６へパス探索指示を通知し、ステップＳ１０６へ移行する。
【０１３８】
ステップＳ１０６では、制御部１６は、シンボリック実行部１４からのパス探索指示によってパス探索を開始する。まず、制御部１６は、検出部２６へ重複パス検出処理の実行指示を通知し、検出部２６に重複パス検出処理を実行させる。
【０１３９】
図１９は、ステップＳ１０６の重複パス検出処理の内容を示したフローチャートである。
【０１４０】
ステップＳ２００で、検出部２６は、メモリ４４の予め定めた領域に記憶されている、被検査プログラム３０の条件分岐毎の分岐実行回数を参照し、パス選択規則に基づいて優先分岐番号を生成する。
【０１４１】
例えば、テストケース生成装置１０が初期状態にある場合、被検査プログラム３０の条件分岐毎の分岐実行回数は｛（０、０）、（０、０）、（０、０）｝であるから、パス選択規則に基づいて生成される優先分岐番号は（０、０、０）となる。
【０１４２】
そして、ステップＳ２０２で、検出部２６は、ステップＳ２００で生成した優先分岐番号と、後述するステップＳ１２４の処理によって生成部２４により生成される重複パス検出ルールとを比較する。そして、重複パス検出ルールの中に、ステップＳ２００で生成した優先分岐番号の少なくとも一部と一致するルールが存在する場合、検出部２６は、生成した優先分岐番号によって表されるパス候補が既出パスと重複することを、制御部１６に通知する。
【０１４３】
そして、ステップＳ１０８では、制御部１６は、検出部２６から重複パス検出処理の結果を受け取り、重複パス検出処理の結果に基づいて、今回のパス探索によって抽出される予定のパス候補が、既出パスと重複するか否かを判定する。
【０１４４】
そして、パス候補が既出パスと重複する場合にはステップＳ１１０へ移行し、パス候補が既出パスと重複しない場合にはステップＳ１１２へ移行する。
【０１４５】
ステップＳ１１０では、制御部１６が、管理部２０へ被検査プログラム３０に含まれる条件分岐毎の分岐実行回数の更新を要求する。管理部２０は、検出部２６で生成されたパス候補に対応した優先分岐番号の値に基づいて、例えばメモリ４４の予め定めた領域に記憶された条件分岐毎の分岐実行回数を更新する。そして、ステップＳ１０２へ移行して、被検査プログラム３０に含まれるパスの探索を繰り返す。
【０１４６】
一方、ステップＳ１１２では、制御部１６が、メモリ４４に記憶された被検査プログラム３０から命令文を１行読み込む。そして、ステップＳ１１４では、制御部１６が、ステップＳ１１２において読み込んだ命令文と共に、選択部２２へ分岐選択処理の実行指示を通知し、選択部２２に分岐選択処理を実行させる。
【０１４７】
ステップＳ１１４では、選択部２２は、制御部１６から通知された命令文が条件分岐命令であれば、条件分岐命令が分岐可能か否かを判断する。そして、選択部２２は条件分岐命令が分岐可能である場合に、既に説明したパス選択規則に従って分岐先を選択する。なお、ステップＳ１１４の分岐選択処理の詳細については後ほど説明する。
【０１４８】
ステップＳ１１６では、制御部１６が、管理部２０へ被検査プログラム３０に含まれる条件分岐毎の分岐実行回数の更新を要求する。
【０１４９】
図２０は、管理部２０で実施される、ステップＳ１１６における分岐実行回数管理処理の内容を示したフローチャートである。
【０１５０】
ステップＳ４００では、管理部２０は、ステップＳ１１２の処理で制御部１６が読み込んだ命令文が条件分岐命令か否かを判定し、否定判定の場合には分岐実行回数管理処理を終了する。一方、肯定判定の場合には、ステップＳ４０２へ移行する。
【０１５１】
ステップＳ４０２では、管理部２０は、ステップＳ１１４での分岐選択処理の結果、選択部２２が選択した条件分岐命令の分岐先を、メモリ４４の予め定めた領域から取得する。条件分岐命令がＩＦ文である場合、選択部２２によってメモリ４４の予め定めた領域には、例えば‘ＴＲＵＥ’又は‘ＦＡＬＳＥ’が記憶され、条件分岐命令がＥＶＡＬＵＡＴＥ文であれば、分岐先番号が記憶されている。この場合、例えば分岐先番号が‘１’の場合には、ＥＶＡＬＵＡＴＥ文の最初のＷＨＥＮ文が実行されたことを意味し、分岐先番号が‘２’の場合には、ＥＶＡＬＵＡＴＥ文の２番目のＷＨＥＮ文が実行されたことを意味する。
【０１５２】
ステップＳ４０４では、管理部２０は、ステップＳ４０２の処理で取得した条件分岐命令の分岐先に基づいて、対応する条件分岐命令の分岐実行回数を１つ増加して、例えばメモリ４４の予め定めた領域に記憶する。
【０１５３】
以上、ステップＳ４００〜ステップＳ４０４の処理によって、ステップＳ１１６の分岐実行回数管理処理が実行される。
【０１５４】
次に、ステップＳ１１８では、制御部１６が、ステップＳ１１２の処理で読み込んだ命令文が被検査プログラム３０の終了を示す命令文、例えば「ＥＸＩＴ  ＰＲＯＧＲＡＭ」であるか否かを判定する。否定判定の場合には、ステップＳ１２０へ移行する。ステップＳ１２０では、まだ１つのパスの探索が終了していない状態であるため、制御部１６は、次に読み込むべき命令文が格納されているメモリ４４上のアドレスを更新する。そして、ステップＳ１１２へ移行し、ステップＳ１１２〜ステップＳ１２０の処理を繰り返すことによって、被検査プログラム３０から１つのパスを探索する。
【０１５５】
なお、ステップＳ１２０では、制御部１６が、例えば被検査プログラム３０から次に読み込むべき命令文の行番号を順次メモリ４４に記憶して、パス探索の終了後に被検査プログラム３０の実行経路が特定できるようにしておく。
【０１５６】
一方、ステップＳ１１８の処理において肯定判定となった場合には、ステップＳ１２２へ移行する。なお、ステップＳ１１８の処理が肯定判定になるということは、被検査プログラム３０から１つのパスが探索されたことを表している。また、ステップＳ１２２へ移行する際、制御部１６は、探索されたパスに対応する条件分岐毎の分岐実行回数をパス探索回数と関連付けて、メモリ４４の予め定めた領域に待避する。
【０１５７】
ステップＳ１２２では、制御部１６は、ステップＳ１１２〜ステップＳ１２０の処理によって新たに探索されたパスを考慮した被検査プログラム３０の分岐網羅度（最新分岐網羅度）を算出する。なお、既にステップＳ１０２の処理で説明したように、被検査プログラム３０の分岐網羅度は、例えばメモリ４４に記憶されている条件分岐毎の分岐実行回数を参照することで算出される。
【０１５８】
そして、制御部１６は、最新分岐網羅度と、例えばメモリ４４に記憶されている既出パスによって算出された被検査プログラム３０の分岐網羅度（既出パス分岐網羅度）とを比較して、分岐網羅度が向上したか否かを判定する。
【０１５９】
分岐網羅度が向上しない、すなわち最新分岐網羅度が既出パス分岐網羅度と等しい場合には、後述するステップＳ１２４及びステップＳ１２６の処理を行わずに、ステップＳ１０２へ移行し、被検査プログラム３０から次のパスを探索する。一方、分岐網羅度が向上した、すなわち最新分岐網羅度が既出パス分岐網羅度よりも大きい場合には、ステップＳ１２４へ移行する。
【０１６０】
ステップＳ１２４では、制御部１６は、生成部２４へ重複パス検出ルールの生成指示を通知する。この場合、生成部２４は、新たに探索したパスに対応する条件分岐毎の分岐実行回数と、前回探索したパスに対応する分岐条件毎の分岐実行回数と、の差分から、新たに探索したパスに含まれる条件分岐毎の分岐先を特定する。そして、生成部２４は、特定した新たに探索したパスに含まれる条件分岐毎の分岐先と、図１９のステップＳ２００で検出部２６によって生成された優先分岐番号とに基づいて、新たに探索したパスに対応した重複パス検出ルールを生成する。
【０１６１】
具体的には、図１４に示したように、例えば条件分岐毎の優先分岐番号のうち、新たに探索したパスが通過した条件分岐の優先分岐番号を重複パス検出ルールとして、メモリ４４の予め定めた領域に記憶する。
【０１６２】
このようにして生成された重複パス検出ルールは、前述したステップＳ１０６の重複パス検出処理で用いられる。
【０１６３】
なお、新たに探索したパスの特定方法はこれに限らず、探索したパスが特定できる方法であれば何れの方法を用いてもよい。
【０１６４】
ステップＳ１２６では、シンボリック実行部１４は、探索されたパスに基づいてシンボリック実行を行い、探索されたパスが実行可能である場合に、被検査プログラム３０から探索されたパスに対応するパス条件を抽出する。そして、シンボリック実行部１４は、シンボリック実行によって抽出したパス及び当該パスに対応するパス条件を組み合わせた情報を、テストケースとして生成し、例えばメモリ４４の予め定めた領域に記憶する。
【０１６５】
テストケース生成後、ステップＳ１０２へ移行して、被検査プログラム３０から次のテストケースを生成する処理を繰り返す。
【０１６６】
そして、ステップＳ１０２の処理において、シンボリック実行部１４によってパス探索の終了条件が成立したと判定された場合、出力部２８は、ステップＳ１０４の処理において、生成されたテストケースを、例えばメモリ４４等にまとめて出力する。
【０１６７】
なお、テストケースの出力先はメモリ４４に限定されず、例えば、コンピュータ４０と有線回線又は無線回線で接続された図示しない端末装置や、ＵＳＢ（Universal Serial Bus）メモリ等の可搬型記憶装置等であってもよい。
【０１６８】
このように、本実施の形態に係るテストケース生成装置１０は、新たなパスが探索されたとしても分岐網羅度が向上しなければ、新たなパスに対応した優先分岐番号が重複パス検出ルールとして使用されることがない上、シンボリック実行が行われることもない。
【０１６９】
従って、探索された全てのパスに対応した優先分岐番号から重複パス検出ルールを生成し、シンボリック実行を行う場合と比較して、分岐網羅度の向上につながらない無駄なテストケースを予め排除することができる。また、分岐網羅度の向上につながらない無駄なテストケースを予め排除することから、テストケースの生成に要する時間を短縮することができる。
【０１７０】
次に、ステップＳ１１４における分岐選択処理の内容について説明する。
【０１７１】
図２１は、選択部２２で実施される、ステップＳ１１４における分岐選択処理の内容を示したフローチャートである。
【０１７２】
ステップＳ３００では、選択部２２は、図１８のステップＳ１１２の処理で制御部１６が読み込んだ命令文が条件分岐命令か否かを判定し、否定判定の場合には分岐選択処理を終了する。一方、肯定判定の場合には、ステップＳ３０２へ移行する。
【０１７３】
ステップＳ３０２では、選択部２２は、読み込まれた条件分岐命令から分岐条件を取得し、例えばメモリ４４の予め定めた領域に記憶する。なお、ステップＳ３０２の処理によって、探索中のパスに含まれる条件分岐命令の分岐条件が、順にメモリ４４の予め定めた領域に記憶される。
【０１７４】
ステップＳ３０４では、選択部２２は、被検査プログラム３０を参照して、ステップＳ３０２の処理で取得した分岐条件の真偽値を確定することができるか否かを評価する。例えば、分岐条件が（項目１＝１）である場合、被検査プログラム３０において項目１の値が具体的な数値として確定しているならば、分岐条件の真偽値を確定することができる。
【０１７５】
ステップＳ３０６では、選択部２２は、ステップＳ３０４の処理によって評価された分岐条件の真偽値が確定するか否かを判定する。そして、肯定判定の場合にはステップＳ３０８へ移行する。
【０１７６】
ステップＳ３０８では、ステップＳ３０２で取得した分岐条件の真偽値を確定し、選択部２２は、ステップＳ３０２の処理で取得した分岐条件と、当該分岐条件での確定した真偽値とを関連付けて、例えばメモリ４４の予め定めた領域に記憶する。そして、図２１に示した分岐選択処理を終了する。
【０１７７】
一方、ステップＳ３０６の処理において、ステップＳ３０４の処理によって評価された分岐条件の真偽値を確定できないと判定された場合には、ステップＳ３１０へ移行する。
【０１７８】
ステップＳ３１０では、選択部２２は、ステップＳ３０２の処理でメモリ４４に記憶した、現在探索中のパスに含まれる全ての分岐条件の充足可能性を評価する。
【０１７９】
例えば、現在探索中のパスに含まれる過去の分岐条件の中に、（性別＝‘男性’）という分岐条件が存在して、当該分岐条件に対応する真偽値が‘ＴＲＵＥ’であったとする。この場合、単独の分岐条件では真偽値を確定させることができない（性別＝‘女性’）という分岐条件がステップＳ３０２の処理で取得されたとしても、過去の分岐条件の真偽値から、真偽値を‘ＦＡＬＳＥ’に確定させることができる。
【０１８０】
このようにして、ステップＳ３１２では、選択部２２は、ステップＳ３０２の処理で取得した分岐条件の分岐先が確定可能か否かを判定する。そして、肯定判定の場合にはステップＳ３１４へ移行する。
【０１８１】
ステップＳ３１４では、ステップＳ３０２で取得した分岐条件の真偽値を確定し、選択部２２は、ステップＳ３０２の処理で取得した分岐条件と、当該分岐条件の真偽値とを関連付けて、例えばメモリ４４の予め定めた領域に記憶する。そして、図２１に示した分岐選択処理を終了する。
【０１８２】
一方、ステップＳ３１２の処理において否定判定となった場合には、ステップＳ３１６へ移行し、選択部２２は、既に説明したパス選択規則に従って、ステップＳ３０２の処理で取得した分岐条件の分岐先を選択する。そして、選択部２２は、ステップＳ３０２の処理で取得した分岐条件と、選択した真偽値とを関連付けて、例えばメモリ４４の予め定めた領域に記憶する。そして、図２１に示した分岐選択処理を終了する。
【０１８３】
以上のようにして、コンピュータ４０上で図１８に示すテストケース生成処理が実行される。
【０１８４】
この様に、本実施の形態に係るテストケース生成装置１０は、検出部２６によりパス探索前に既出パスと重複するパス候補を検出し、重複するパス候補をパス探索前に予め排除する。従って、本実施の形態に係るテストケース生成装置１０は、検出部２６を含まない場合と比較して、テストケース生成時間を短縮することができる。また、検出部２６は重複するパス候補を予め排除するため、本実施の形態に係るテストケース生成装置１０は、ＤＡＲＴ等の従来のパス抽出法と比較して、より少ないパス数で分岐網羅を実現するパスを抽出することができる。
【０１８５】
（第２実施形態）
【０１８６】
次に、開示の技術の第２実施形態について説明する。なお、第１実施形態と同一の部分には同一の符号を付して説明を省略し、第１実施形態と異なる部分を中心に説明する。
【０１８７】
図２２に、本実施の形態に係るテストケース生成装置１０Ａを示す。
【０１８８】
本実施の形態に係るテストケース生成装置１０Ａが、図７に示した第１実施形態におけるテストケース生成装置１０と異なる点は、管理部２０が管理部２０Ａになった点であり、その他は同一であるので説明は省略する。
【０１８９】
図２３は、外部処理に条件分岐命令が含まれた被検査プログラム３０の一例を示した図である。
【０１９０】
図２３に示した被検査プログラム３０は、１９行目から２６行目までが外部処理であり、２０行目にＩＦ文が含まれている。そして、外部処理は、１２行目、１４行目、及び１６行目の３個のＰＥＲＦＯＲＭ文から呼び出される。
【０１９１】
この場合、管理部２０Ａは、初期状態において被検査プログラム３０を解析し、２０行目にＩＦ文を検出した場合、第１実施形態における管理部２０と同様に、ＩＦ文の分岐実行回数を、例えば「直接＝（０、０）」のように初期化する。
【０１９２】
そして、制御部１６によって被検査プログラム３０のパスが探索されると、まず、１２行目のＰＥＲＦＯＲＭ文から外部処理が呼び出される。そして、パス選択規則に従って、２０行目のＩＦ文のＴＨＥＮ分岐が実行され、外部処理の呼出元に実行先が復帰する。
【０１９３】
この際、管理部２０Ａは、外部処理の呼出元毎にＩＦ文の分岐実行回数を管理する。具体的には、初めての呼出元から外部処理呼び出しによってＩＦ文を実行した場合に、例えば「Ｐｅｒｆｏｒｍ＃１２＝（１、０）」といった分岐実行回数を記録する。ここで、‘＃’の前の‘Ｐｅｒｆｏｒｍ’は外部処理を呼び出した命令文を表し、‘＃’の後ろに続く‘１２’の数値は、外部処理の呼出元行番号を示す。
【０１９４】
引き続き、１４行目のＰＥＲＦＯＲＭ文から外部処理が呼び出されると、パス選択規則に従って、２０行目のＩＦ文のＴＨＥＮ分岐が実行され、外部処理の呼出元に処理が復帰する。この際、管理部２０Ａは、外部処理がこれまでとは異なる呼出元から呼び出されたことから、例えば「Ｐｅｒｆｏｒｍ＃１４＝（１、０）」といった分岐実行回数を記録する。
【０１９５】
更に、１６行目のＰＥＲＦＯＲＭ文から外部処理が呼び出されると、パス選択規則に従って、２０行目のＩＦ文のＴＨＥＮ分岐が実行され、外部処理の呼出元に処理が復帰する。この際、管理部２０Ａは、外部処理がこれまでとは異なる呼出元から呼び出されたことから、例えば「Ｐｅｒｆｏｒｍ＃１６＝（１、０）」といった分岐実行回数を記録する。
【０１９６】
すなわち、図２３に示した被検査プログラム３０の２０行目のＩＦ文に対して、直接＝（０、０）、Ｐｅｒｆｏｒｍ＃１２＝（１、０）、Ｐｅｒｆｏｒｍ＃１４＝（１、０）、及びＰｅｒｆｏｒｍ＃１６＝（１、０）の４つの分岐実行回数が管理される。
【０１９７】
次に、本実施の形態に係るテストケース生成装置１０Ａの作用を説明する。テストケース生成装置１０Ａのテストケース生成処理は、図１８に示す第１実施形態におけるテストケース生成装置１０のテストケース生成処理と同一である。ただし、ステップＳ１１６の分岐実行回数管理処理の内容が異なるため、以下に、本実施の形態に係る分岐実行回数管理処理について説明する。
【０１９８】
図２４は、管理部２０Ａで実施される、分岐実行回数管理処理の内容を示したフローチャートである。図２４に示す分岐実行回数管理処理が図２０に示す分岐実行回数管理処理と異なるのは、ステップＳ４０３、ステップＳ４０６、及びステップＳ４０８の処理が追加された点である。その他の処理は図２０に示す分岐実行回数管理処理と同一であるため、説明を省略する。
【０１９９】
ステップＳ４０３では、管理部２０Ａは、制御部１６が図１８に示すステップＳ１１２の処理で読み込んだ条件分岐命令が、外部処理呼び出しによって読み込まれた条件分岐命令か否かを判定する。具体的には、ステップＳ１２０の処理でメモリ４４に記録された被検査プログラム３０の実行経路を参照して判定すればよい。
【０２００】
そして、ステップＳ４０３の処理による判定が否定判定の場合には、既に説明したステップＳ４０４へ移行する。一方、肯定判定の場合には、ステップＳ４０６へ移行する。
【０２０１】
ステップＳ４０６では、管理部２０Ａは、ステップＳ１２０の処理でメモリ４４に記録された被検査プログラム３０の実行経路を参照して、図１８に示すステップＳ１１２の処理で読み込んだ条件分岐命令のサブルーチン階層を取得する。
【０２０２】
ここで、条件分岐命令のサブルーチン階層とは、条件分岐命令に至るまでの外部処理の呼出過程を示すものである。
【０２０３】
例えば、Ｎ１行目のＰＥＲＦＯＲＭ文から外部処理Ａが呼び出され、外部処理Ａに含まれるＮ２行目のＰＥＲＦＯＲＭ文から外部処理Ｂが更に呼び出され、外部処理Ｂに条件分岐命令が含まれる場合のサブルーチン階層について説明する。
【０２０４】
この場合、条件分岐命令は、外部処理Ａ、外部処理Ｂの順に呼び出されるため、条件分岐命令のサブルーチン階層は、例えば外部処理の呼出元の行番号を用いて、「Ｐｅｒｆｏｒｍ＃（Ｎ１、Ｎ２）」と取得される。
【０２０５】
なお、Ｎ１行目にあるＰＥＲＦＯＲＭ文から呼び出された外部処理Ａの中に条件分岐命令が含まれる場合には、図２３で既に説明したように、条件分岐命令のサブルーチン階層は、「Ｐｅｒｆｏｒｍ＃Ｎ１」と取得される。
【０２０６】
そして、ステップＳ４０８では、管理部２０Ａは、ステップＳ４０２の処理で取得した条件分岐命令の分岐先に基づいて、サブルーチン階層に対応する条件分岐命令の分岐実行回数を１つ増加して、例えばメモリ４４の予め定めた領域に記憶する。
【０２０７】
以上、ステップＳ４００〜ステップＳ４０８の処理によって、図１８に示すステップＳ１１６の分岐実行回数管理処理が実行される。
【０２０８】
このように、本実施の形態に係る管理部２０Ａは、条件分岐毎に分岐実行回数を管理するのに加え、更に、条件分岐命令が外部処理に含まれる場合、条件分岐命令に到達するまでに経由した外部処理の呼出元毎に条件分岐の分岐実行回数を管理する。
【０２０９】
従って、被検査プログラム３０が外部処理の中に条件分岐を含む場合、単に条件分岐毎に分岐実行回数を管理する場合と比較して、効率よく分岐網羅を実現するテストケースを生成することができる。
【０２１０】
以上、開示の技術を実施の形態を用いて説明したが、開示の技術は上記実施の形態に記載の範囲には限定されない。開示の技術の要旨を逸脱しない範囲で上記実施の形態に多様な変更または改良を加えることができ、当該変更または改良を加えた形態も開示の技術の技術的範囲に含まれる。例えば、開示の技術の要旨を逸脱しない範囲で、図１８〜図２１、及び図２４に示した処理の順序を変更してもよい。
【０２１１】
また、上記では開示の技術に係るテストケース生成プログラムの一例であるテストケース生成プログラム５０が記憶部４６に予め記憶（インストール）されている態様を説明したが、これに限定されるものではない。開示の技術に係るテストケース生成プログラムは、コンピュータ読取可能な記録媒体に記録されている形態で提供することも可能である。例えば、開示の技術に係るテストケース生成プログラムは、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、及びＵＳＢメモリ等の可搬型記録媒体、並びに、フラッシュメモリ等の半導体メモリ等に記録されている形態で提供することも可能である。
【０２１２】
また、実施形態に開示したテストケース生成装置１０、１０Ａは、単一のコンピュータ４０上で実現されるものとして説明した。しかし、プロセスを異なるコンピュータの記憶部４６に記憶させ、各々のコンピュータを有線又は無線の通信回線で接続した分散処理の形態で、テストケース生成装置１０、１０Ａを実現するようにしてもよい。
【０２１３】
また、実施形態に開示したテストケース生成装置１０、１０Ａは、ネットワークを経由して被検査プログラム３０を受け付け、生成したテストケースをネットワークを経由して出力する、所謂ネットサービスの態様をとるようにしてもよい。
【０２１４】
以上の第１実施形態及び第２実施形態を含む実施形態に関し、更に以下の付記を開示する。
【０２１５】
（付記１）
被検査プログラムに含まれる条件分岐の分岐先への分岐実行回数を管理する管理部と、
前記管理部により管理された前記分岐実行回数から得られる経路候補に対応した分岐情報と、既に抽出された前記被検査プログラムの既出経路に対応した分岐情報と、を比較して、前記経路候補が前記既出経路に含まれる重複経路か否かを検出する検出部と、
前記条件分岐の前記分岐実行回数に応じた予め定めた規則に基づいて分岐先を決定して、前記被検査プログラムの開始から終了までの経路を選択する選択部と、
前記選択部により選択された前記経路に対応した分岐情報を、前記既出経路に対応した分岐情報として生成する生成部と、
前記検出部により前記経路候補が前記重複経路ではないと検出された場合、前記選択部及び前記生成部の各々による処理が実行され、前記検出部により前記経路候補が前記重複経路であると検出された場合、前記選択部及び前記生成部の各々による処理が実行されないように、前記選択部及び前記生成部を制御する制御部と、
を有するテストケース生成装置。
【０２１６】
（付記２）
前記管理部は、前記条件分岐が、前記被検査プログラムの呼出元から呼び出されるサブルーチンに含まれる条件分岐である場合には、前記条件分岐の各々について、前記条件分岐に対応した前記分岐実行回数を管理すると共に、前記サブルーチンの呼出元毎に前記条件分岐に対応した前記分岐実行回数を管理する
付記１記載のテストケース生成装置。
【０２１７】
（付記３）
前記制御部は、前記管理部で管理される前記分岐実行回数に基づいて算出される、前記選択部による新たな前記経路の選択前の分岐網羅度と、前記管理部で管理される前記分岐実行回数に基づいて算出される、前記選択部による新たな前記経路の選択後の分岐網羅度と、を比較し、新たな前記経路の選択後の分岐網羅度が新たな前記経路の選択前の分岐網羅度と同じ場合には、前記選択部により選択された新たな前記経路に対応した分岐情報を、前記既出経路に対応した分岐情報として生成しないように前記生成部を制御する
付記１又は付記２記載のテストケース生成装置。
【０２１８】
（付記４）
被検査プログラムに含まれる条件分岐の分岐先への分岐実行回数を管理し、
前記分岐実行回数から得られる経路候補に対応した分岐情報と、既に抽出された前記被検査プログラムの既出経路に対応した分岐情報と、を比較して、前記経路候補が前記既出経路に含まれる重複経路か否かを検出し、
前記経路候補が前記重複経路ではないと検出された場合、前記条件分岐の前記分岐実行回数に応じた予め定めた規則に基づいて分岐先を決定して、前記被検査プログラムの開始から終了までの経路を選択し、前記経路に対応した分岐情報を、前記既出経路に対応した分岐情報として生成し、前記経路候補が前記重複経路であると検出された場合、前記経路候補に対応した前記経路を選択せずに、且つ、前記経路に対応した分岐情報を、前記既出経路に対応した分岐情報として生成しないように制御する
ことを含むテストケース生成方法。
【０２１９】
（付記５）
前記条件分岐が、前記被検査プログラムの呼出元から呼び出されるサブルーチンに含まれる条件分岐である場合には、前記条件分岐の各々について、前記条件分岐に対応した前記分岐実行回数を管理すると共に、前記サブルーチンの呼出元毎に前記条件分岐に対応した前記分岐実行回数を管理する
付記４記載のテストケース生成方法。
【０２２０】
（付記６）
前記分岐実行回数に基づいて算出される、新たな前記経路の選択前の分岐網羅度と、前記分岐実行回数に基づいて算出される、新たな前記経路の選択後の分岐網羅度と、を比較し、新たな前記経路の選択後の分岐網羅度が新たな前記経路の選択前の分岐網羅度と同じ場合には、新たな前記経路に対応した分岐情報を、前記既出経路に対応した分岐情報として生成しないように制御する
付記４又は付記５記載のテストケース生成方法。
【０２２１】
（付記７）
コンピュータに、
被検査プログラムに含まれる条件分岐の分岐先への分岐実行回数を管理し、
前記分岐実行回数から得られる経路候補に対応した分岐情報と、既に抽出された前記被検査プログラムの既出経路に対応した分岐情報と、を比較して、前記経路候補が前記既出経路に含まれる重複経路か否かを検出し、
前記経路候補が前記重複経路ではないと検出された場合、前記条件分岐の前記分岐実行回数に応じた予め定めた規則に基づいて分岐先を決定して、前記被検査プログラムの開始から終了までの経路を選択し、前記経路に対応した分岐情報を、前記既出経路に対応した分岐情報として生成し、前記経路候補が前記重複経路であると検出された場合、前記経路候補に対応した前記経路を選択せずに、且つ、前記経路に対応した分岐情報を、前記既出経路に対応した分岐情報として生成しないように制御する
ことを含む処理を実行させるためのテストケース生成プログラム。
【０２２２】
（付記８）
コンピュータに、
被検査プログラムに含まれる条件分岐の分岐先への分岐実行回数を管理し、
前記分岐実行回数から得られる経路候補に対応した分岐情報と、既に抽出された前記被検査プログラムの既出経路に対応した分岐情報と、を比較して、前記経路候補が前記既出経路に含まれる重複経路か否かを検出し、
前記経路候補が前記重複経路ではないと検出された場合、前記条件分岐の前記分岐実行回数に応じた予め定めた規則に基づいて分岐先を決定して、前記被検査プログラムの開始から終了までの経路を選択し、前記経路に対応した分岐情報を、前記既出経路に対応した分岐情報として生成し、前記経路候補が前記重複経路であると検出された場合、前記経路候補に対応した前記経路を選択せずに、且つ、前記経路に対応した分岐情報を、前記既出経路に対応した分岐情報として生成しないように制御する
ことを含む処理を実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【符号の説明】
【０２２３】
１０、１０Ａ  テストケース生成装置
１２  入力部
１４  シンボリック実行部
１６  制御部
１８  深さ優先探索部
２０、２０Ａ  管理部
２２  選択部
２４  生成部
２６  検出部
２８  出力部
３０  被検査プログラム
３２  テストケース
４０  コンピュータ
４４  メモリ
４６  記憶部
４８  バス
【図１】
2015176230.tif 000003
【図２】
2015176230.tif 000004
【図３】
2015176230.tif 000005
【図４】
2015176230.tif 000006
【図５】
2015176230.tif 000007
【図６】
2015176230.tif 000008
【図７】
2015176230.tif 000009
【図８】
2015176230.tif 000010
【図９】
2015176230.tif 000011
【図１０】
2015176230.tif 000012
【図１１】
2015176230.tif 000013
【図１２】
2015176230.tif 000014
【図１３】
2015176230.tif 000015
【図１４】
2015176230.tif 000016
【図１５】
2015176230.tif 000017
【図１６】
2015176230.tif 000018
【図１７】
2015176230.tif 000019
【図１８】
2015176230.tif 000020
【図１９】
2015176230.tif 000021
【図２０】
2015176230.tif 000022
【図２１】
2015176230.tif 000023
【図２２】
2015176230.tif 000024
【図２３】
2015176230.tif 000025
【図２４】
2015176230.tif 000026