(57)【要約】      （修正有）【課題】網羅性があるテストデータを効率的に生成する。【解決手段】シンボリック実行の対象範囲のうち一部の範囲を省略してシンボリック実行を行い、当該シンボリック実行について網羅率を算出する第１処理Ｓ７、Ｓ９と、算出された網羅率が所定の値を超えたか判断する第２処理Ｓ１１と、算出された網羅率が所定の値を超えていない場合、省略された一部の範囲のうち少なくとも一部が省略の対象外になるように設定し、第１処理以降の処理を再度実行する第３処理Ｓ１３と、算出された網羅率が所定の値を超えた場合に、シンボリック実行により得られたパスの条件を満たす値を、第１データ格納部に格納する第４処理Ｓ１５とを含む。【選択図】図３
2014127091.tif 000002
【特許請求の範囲】
【請求項１】
シンボリック実行の対象範囲のうち一部の範囲を省略して前記シンボリック実行を行い、当該シンボリック実行について網羅率を算出する第１処理と、
算出された前記網羅率が所定の値を超えたか判断する第２処理と、
算出された前記網羅率が前記所定の値を超えていない場合、省略された前記一部の範囲のうち少なくとも一部が省略の対象外になるように設定し、前記第１処理以降の処理を再度実行する第３処理と、
算出された前記網羅率が前記所定の値を超えた場合に、前記シンボリック実行により得られたパスの条件を満たす値を、第１データ格納部に格納する第４処理と、
をコンピュータが実行するテストデータ生成方法。
【請求項２】
前記第１処理において、
プログラム内の分岐によって生じる複数の分岐先の各々において未実行の命令が無い場合には前記分岐に関連するパスについて前記シンボリック実行を終了することにより、前記一部の範囲を省略して前記シンボリック実行を行う
ことを特徴とする請求項１記載のテストデータ生成方法。
【請求項３】
前記第３処理において、
省略した前記一部の範囲に含まれる関数のうち所定の方法によって特定された関数を省略の対象外に決定する
ことを特徴とする請求項１又は２記載のテストデータ生成方法。
【請求項４】
前記所定の方法が、
関数の呼び出し関係に基づき生成されるコールグラフにおいて最も下の階層に属する関数から順に特定するという方法である
ことを特徴とする請求項３記載のテストデータ生成方法。
【請求項５】
シンボリック実行の対象範囲のうち一部の範囲を省略して前記シンボリック実行を行い、当該シンボリック実行について網羅率を算出する第１処理と、
算出された前記網羅率が所定の値を超えたか判断する第２処理と、
算出された前記網羅率が前記所定の値を超えていない場合、省略された前記一部の範囲のうち少なくとも一部が省略の対象外になるように設定し、前記第１処理以降の処理を再度実行する第３処理と、
算出された前記網羅率が前記所定の値を超えた場合に、前記シンボリック実行により得られたパスの条件を満たす値を、第１データ格納部に格納する第４処理と、
をコンピュータに実行させるためのテストデータ生成プログラム。
【請求項６】
シンボリック実行の対象範囲のうち一部の範囲を省略して前記シンボリック実行を行い、当該シンボリック実行について網羅率を算出すると共に、算出された前記網羅率が所定の値を超えたか判断する第１処理部と、
算出された前記網羅率が前記所定の値を超えていない場合、省略された前記一部の範囲のうち少なくとも一部が省略の対象外になるように設定し、前記第１処理部に処理を再度実行させる第２処理部と、
算出させた前記網羅率が前記所定の値を超えた場合に、前記シンボリック実行により得られたパスの条件を満たす値を、第１データ格納部に格納する第３処理部と、
を有するテストデータ生成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラムのテストに使用するテストデータの生成技術に関する。
【背景技術】
【０００２】
シンボリック実行とは、プログラム内の変数を具体化せず、変数をシンボル化して（すなわち、記号のまま）プログラムを実行する技術である。シンボル化される変数は、シンボル変数と呼ばれる。シンボリック実行中においては、具体値ではなくシンボル変数が満たすべき条件（以下、パス条件と呼ぶ）がシンボル変数の値としてメモリ等に保持される。そして、シンボリック実行が完了すると、プログラムにおける各パスについてパス条件が得られるため、パス条件を満たすシンボル変数の具体値を求めることで、プログラムをテストするためのテストデータを得ることができる。
【０００３】
例えば、図１に示した、絶対値取得関数として問題があるプログラムについてシンボリック実行を行うことを考える。図１には、シンボリック実行の対象になるプログラムのコードと、そのプログラムの制御構造とが示されている。このプログラムには変数Ｘが含まれている。このプログラムを対象としてシンボリック実行を行うと、Ｘ＝−２というテストデータ（パス条件はＸ＜０）と、Ｘ＝１２３４というテストデータ（パス条件はＸ≧０且つＸ＝１２３４）と、Ｘ＝３というテストデータ（パス条件はＸ≧０且つＸ≠１２３４）とを得ることができる。
【０００４】
但し、上で述べたように、通常のシンボリック実行はプログラム内の全パスを対象範囲としているため、無駄な実行をしてしまうことがある。例えば、プログラム内の全パスを対象範囲としなくても、プログラム内の全命令を対象範囲とすればよいという場合には、通常のシンボリック実行を行うと、命令カバレッジの向上に寄与しないパスを実行することになる。その結果、シンボリック実行の完了までに余計な時間がかかり、またメモリ等の資源を無駄に消費する。
【０００５】
このような問題に着目した従来技術は存在する。しかしながら、従来技術においては、複数のシンボル変数が存在することを前提としているため、シンボル変数が１つしか存在しないような場合は考慮されていない。また、場合によっては、この従来技術を利用したとしてもテストデータの生成を効率的に行えないことがある。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０１２−０６８８６９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
１つの側面では、本発明の目的は、網羅性があるテストデータを効率的に生成するための技術を提供することである。
【課題を解決するための手段】
【０００８】
本発明に係るテストデータ生成方法は、シンボリック実行の対象範囲のうち一部の範囲を省略してシンボリック実行を行い、当該シンボリック実行について網羅率を算出する第１処理と、算出された網羅率が所定の値を超えたか判断する第２処理と、算出された網羅率が所定の値を超えていない場合、省略された一部の範囲のうち少なくとも一部が省略の対象外になるように設定し、第１処理以降の処理を再度実行する第３処理と、算出された網羅率が所定の値を超えた場合に、シンボリック実行により得られたパスの条件を満たす値を、第１データ格納部に格納する第４処理とを含む。
【発明の効果】
【０００９】
網羅性があるテストデータを効率的に生成できるようになる。
【図面の簡単な説明】
【００１０】
【図１】図１は、シンボリック実行について説明するための図である。
【図２】図２は、シンボリック実行装置の機能ブロック図である。
【図３】図３は、メインの処理フローを示す図である。
【図４】図４は、対象プログラムの一例を示す図である。
【図５】図５は、目標カバレッジ格納部に格納されるデータの一例を示す図である。
【図６】図６は、シンボリック実行の処理フローを示す図である。
【図７】図７は、第２命令データ格納部に格納されるデータの一例を示す図である。
【図８】図８は、コールグラフの一例を示す図である。
【図９】図９は、シンボリック実行の処理フローを示す図である。
【図１０】図１０は、第１関数データ格納部に格納されるデータの一例を示す図である。
【図１１】図１１は、判定処理の処理フローを示す図である。
【図１２】図１２は、判定処理の処理フローを示す図である。
【図１３】図１３は、第１命令データ格納部に格納されるデータの一例を示す図である。
【図１４】図１４は、第２関数データ格納部に格納されるデータの一例を示す図である。
【図１５】図１５は、基準になる葉ノードの特定方法について説明するための図である。
【図１６】図１６は、再帰呼び出しに対する対処方法について説明するための図である。
【図１７】図１７は、本実施の形態の処理によるパス刈りについて説明するための図である。
【図１８】図１８は、パス刈りの範囲を制御しない場合におけるメインの処理フローを示す図である。
【図１９】図１９は、パス刈りの範囲を制御しない場合におけるシンボリック実行の処理フローを示す図である。
【図２０】図２０は、対象プログラムの他の例を示す図である。
【図２１】図２１は、パス刈りの範囲を制御しない場合における結果を示す図である。
【図２２】図２２は、パス刈りの範囲を制御しない場合における結果を示す図である。
【図２３】図２３は、コンピュータの機能ブロック図である。
【発明を実施するための形態】
【００１１】
図２に、本実施の形態におけるシンボリック実行装置１の機能ブロック図を示す。シンボリック実行装置１は、入力部１００と、目標カバレッジ格納部１０１と、対象プログラム格納部１０２と、範囲制御部１０３と、実行部１１２及び生成部１１３を含む実行エンジン１０４と、判定部１０５と、第１命令データ格納部１０６と、第２命令データ格納部１０７と、状態データ格納部１０８と、第１関数データ格納部１０９と、第２関数データ格納部１１０と、コールグラフデータ格納部１１１と、テストデータ格納部１１４とを含む。
【００１２】
入力部１００は、対象プログラムの入力をユーザから受け付け、対象プログラム格納部１０２に格納する。また、入力部１００は、目標のカバレッジの入力をユーザから受け付け、目標カバレッジ格納部１０１に格納する。
【００１３】
範囲制御部１０３は、第２関数データ格納部１１０におけるパス刈りを実施した関数のリスト及びコールグラフデータ格納部１１１に格納されているコールグラフのデータに基づき処理を行い、処理結果を第１関数データ格納部１０９に格納する。なお、本実施の形態において、「パス刈りを実施する」とは、パスについてのシンボリック実行を途中で終了する（すなわち、パスについてそれ以上シンボリック実行を行わない）ことを意味する。
【００１４】
実行エンジン１０４は、シンボリック実行を行うモジュールであり、例えばＪａｖａ（登録商標） ＰａｔｈＦｉｎｄｅｒである。実行部１１２は、対象プログラム格納部１０２に格納されている、シンボリック実行の対象になるプログラムに対してシンボリック実行を行い、実行済みである命令を第２命令データ格納部１０７に格納する。また、実行部１１２は、プログラムの実行状態に関するデータ（例えば、実行位置を示すプログラムカウンタの値、コールスタックの内容、シンボル変数についての情報、及びパス条件等）を状態データ格納部１０８において管理する。また、実行部１１２は、パス刈りを実施した関数を第２関数データ格納部１１０に格納する。また、実行部１１２は、コールグラフのデータを生成し、コールグラフデータ格納部１１１に格納する。生成部１１３は、シンボリック実行により得られるパス条件を満たすテストデータを生成し、テストデータ格納部１１４に格納する。
【００１５】
判定部１０５は、第２命令データ格納部１０７に格納されている実行済みである命令のリスト及び状態データ格納部１０８に格納されているデータに基づき、分岐先において未実行の命令が有るか否かを判定する処理を実行する。また、判定部１０５は、探索済みである分岐の命令を第１命令データ格納部１０６に格納する。
【００１６】
次に、図３乃至図１７を用いて、シンボリック実行装置１の動作について説明する。まず、シンボリック実行装置１における入力部１００は、シンボリック実行の対象になる対象プログラム及び目標カバレッジの入力をユーザから受け付ける（図３：ステップＳ１）。入力部１００は、対象プログラムを対象プログラム格納部１０２に格納し、目標カバレッジを目標カバレッジ格納部１０１に格納する。目標カバレッジは、例えば、命令カバレッジ、条件カバレッジ及び分岐カバレッジの少なくともいずれかについての目標値である。
【００１７】
図４に、対象プログラムの一例を示す。図４に示す対象プログラムは、メインの処理を表すコードにおいて関数「ｉｎｔ  ｃｈｋ２ｎｄ（ｓ）」を呼び出し、関数「ｉｎｔ  ｃｈｋ２ｎｄ（ｓ）」において関数「ｉｎｔ  ｓｔｒｌｅｎ（ｃｈａｒ＊ｓ）」を呼び出すプログラムである。命令の数は１９である。
【００１８】
目標カバレッジ格納部１０１には、例えば図５に示すように目標カバレッジが格納される。なお、異なる種類の目標カバレッジが複数格納される（例えば、命令カバレッジについての目標値と分岐カバレッジについての目標値とが格納される）場合もある。
【００１９】
実行エンジン１０４における実行部１１２は、対象プログラム格納部１０２に対象プログラムが格納されると、コールグラフにおける階層を特定するための整数ｎ（初期値は０）をインクリメントする（ステップＳ３）。
【００２０】
実行部１１２は、状態データ格納部１０８に格納されている実行状態に関するデータを初期化することにより、実行状態ｐを初期化する（ステップＳ５）。初期化とは、例えば、プログラムカウンタの値を１に戻し、コールスタックの内容をクリアし、メモリにおけるシンボル変数の状態についての情報をクリアし、またパス条件をクリアすることである。
【００２１】
実行部１１２は、シンボリック実行（ｎｕｌｌ，ｐ）を行う（ステップＳ７）。シンボリック実行（ｓ，ｐ）については、図６乃至図１４を用いて説明する。なお、括弧内における１番目の文字列は実行済みである命令のリストを表しており、括弧内における２番目の文字列は実行状態を表す文字列である。ここでは、（ｎｕｌｌ，ｐ）は、実行済みである命令のリスト（すなわち、第２命令データ格納部１０７におけるリスト）が空である場合において、実行状態ｐが初期の状態からシンボリック実行を行うことを表している。
【００２２】
まず、実行部１１２は、実行状態ｐのプログラムカウンタに基づき１つの命令を対象プログラム格納部１０２に格納されている対象プログラムから読み出し、第２命令データ格納部１０７に追加する（図６：Ｓ２１）。第２命令データ格納部１０７には、例えば図７に示すように、実行済みである命令のリストが格納される。
【００２３】
実行部１１２は、読み出した命令が関数の呼び出しの命令であるか判断する（ステップＳ２３）。
【００２４】
関数の呼び出しの命令ではない場合（ステップＳ２３：Ｎｏルート）、ステップＳ２７の処理に移行する。関数の呼び出しの命令である場合（ステップＳ２３：Ｙｅｓルート）、実行部１１２は、コールグラフデータ格納部１１１に格納されているデータに基づき特定されるコールグラフに、呼び出す関数を追加する（ステップＳ２５）。
【００２５】
図８に、コールグラフの一例を示す。図８の例は、図４に示したプログラムについて生成されたコールグラフを示している。コールグラフは、関数の呼び出し関係を表している。以下では、コールグラフにおける各関数のことをノードと呼び、最も新しく呼び出された関数を葉ノードと呼ぶ。図８の例では、関数「ｉｎｔ  ｓｔｒｌｅｎ（ｃｈａｒ＊ｓ）」が葉ノードである。コールグラフにおいては、葉ノードを最も下の階層のノードとする。
【００２６】
実行部１１２は、読み出した命令がシンボル変数に関わる分岐であるか判断する（ステップＳ２７）。シンボル変数に関わる分岐は、例えば、図４における行番号が９における「ｉｆ（ｓｔｒｌｅｎ（ｓ）＜＝１）」である。
【００２７】
シンボル変数に関わる分岐である場合（ステップＳ２７：Ｙｅｓルート）、処理は端子Ａを介して図９のステップＳ４１に移行する。
【００２８】
図９の説明に移行し、実行部１１２は、実行状態Ｐに実行状態ｐをコピーし、分岐において未処理の分岐先（実行状態をＰとする）を１つ特定する（図９：ステップＳ４１）。なお、例えば分岐がｉｆ文である場合、分岐先としてＹｅｓのパスとＮｏのパスとがある。
【００２９】
実行部１１２は、実行中の関数（すなわち、コールグラフにおいて最も新しく呼び出された関数）はパス刈りの対象外であるか判断する（ステップＳ４３）。ステップＳ４３における判断は、第１関数データ格納部１０９におけるパス刈りの対象外になる関数のリストに実行中の関数が含まれるか否かによって行う。第１関数データ格納部１０９には、例えば図１０に示すようなデータが格納される。
【００３０】
パス刈りの対象外である場合（ステップＳ４３：Ｙｅｓルート）、パスについてシンボリック実行を終了させなくてもよいので、実行部１１２は、シンボリック実行（ｓ，Ｐ）を行う（ステップＳ５１）。ここでは、（ｓ，Ｐ）は、実行済みである命令のリスト（すなわち、第２命令データ格納部１０７におけるリスト）がｓという状態である場合において、実行状態Ｐについてシンボリック実行を行うことを表している。
【００３１】
一方、実行中の関数はパス刈りの対象外ではない場合（ステップＳ４３：Ｎｏルート）、実行部１１２は、判定部１０５に判定処理の実行を要求する。これに応じ、判定部１０５は、判定処理（ｓ，Ｐ，ｎｕｌｌ）を実行する（ステップＳ４５）。判定処理については、図１１乃至図１３を用いて説明する。なお、括弧内における１番目の文字列は実行済みである命令のリストを表しており、括弧内における２番目の文字列は実行状態を表す文字列であり、括弧内における３番目の文字列は探索済みである分岐の命令のリストを表す文字列である。ここでは、（ｓ，Ｐ，ｎｕｌｌ）は、実行済みである命令のリスト（すなわち、第２命令データ格納部１０７におけるリスト）がｓという状態であり且つ探索済みである分岐の命令のリスト（すなわち、第１命令データ格納部１０６におけるリスト）が空である状態において、実行状態Ｐについて判定処理を行うことを表している。
【００３２】
まず、判定部１０５は、実行状態ｐの命令を１つ読み出す（図１１：ステップＳ６１）。
【００３３】
判定部１０５は、読み出した命令が第２命令データ格納部１０７における実行済みである命令のリストに格納されているか判断する（ステップＳ６３）。含まれていない場合（ステップＳ６３：Ｎｏルート）、処理は端子Ｃを介して図１２のステップＳ８１に移行する。そして、判定部１０５は、分岐先のパスにおける命令が「未実行」であることを示す値を返り値に設定する（図１２：ステップＳ８１）。そして元の処理に戻る。
【００３４】
一方、読み出した命令が第２命令データ格納部１０７における実行済みである命令のリストに格納されている場合（ステップＳ６３：Ｙｅｓルート）、読み出した命令が「リターン」であるか判断する（ステップＳ６５）。「リターン」である場合（ステップＳ６５：Ｙｅｓルート）、パスの全ての命令を実行済みであると考えられるので、処理は端子Ｄを介して図１２のステップＳ８３に移行する。そして、判定部１０５は、分岐先のパスにおける命令が「実行済み」であることを示す値を返り値に設定する（図１２：ステップＳ８３）。そして元の処理に戻る。
【００３５】
一方、読み出した命令が「リターン」ではない場合（ステップＳ６５：Ｎｏルート）、判定部１０５は、読み出した命令は分岐の命令であり且つ探索済みである分岐の命令のリストに含まれていないか判断する（ステップＳ６７）。探索済みである分岐の命令のリストに含まれていないか判断するのは、ループを防ぐためである。第１命令データ格納部１０６における探索済みである分岐の命令のリストには、例えば図１３に示すようなデータが格納される。
【００３６】
読み出した命令は分岐であり且つ探索済みである分岐の命令のリストに含まれていない場合（ステップＳ６７：Ｙｅｓルート）、判定部１０５は、第１命令データ格納部１０６における、探索済みである分岐の命令のリストに読み出した命令を追加する（ステップＳ７１）。
【００３７】
判定部１０５は、分岐において未処理の分岐先（実行状態をＰとする）を１つ特定する（ステップＳ７３）。
【００３８】
判定部１０５は、判定処理（ｓ，Ｐ，ｂ）を実行する（ステップＳ７５）。ここでは、（ｓ，Ｐ，ｂ）は、実行済みである命令のリスト（すなわち、第２命令データ格納部１０７におけるリスト）がｓという状態であり且つ探索済みである分岐の命令のリスト（すなわち、第１命令データ格納部１０６におけるリスト）がｂという状態である場合において、実行状態Ｐについて判定処理を行うことを表している。
【００３９】
判定処理の結果、実行状態Ｐのパスにおける命令を実行済みではないと判定された場合（ステップＳ７７：Ｎｏルート）、処理は端子Ｃを介して図１２のステップＳ８１に移行する。
【００４０】
実行状態Ｐのパスにおける命令を実行済みであると判定された場合（ステップＳ７７：Ｙｅｓルート）、判定部１０５は、未処理の分岐先が有るか判断する（ステップＳ７９）。未処理の分岐先が有る場合（ステップＳ７９：Ｙｅｓルート）、次の分岐先について処理するため、ステップＳ７３の処理に戻る。一方、未処理の分岐先が無い場合（ステップＳ７９：Ｎｏルート）、ステップＳ６９の処理に移行する。
【００４１】
一方、ステップＳ６７において、読み出した命令は分岐ではない又は探索済みである分岐の命令のリストに含まれると判断された場合（ステップＳ６７：Ｎｏルート）、判定部１０５は、実行状態ｐの次の命令が有るか判断する（ステップＳ６９）。実行状態ｐの次の命令が無い場合（ステップＳ６９：Ｎｏルート）、処理は端子Ｄを介して図１２のステップＳ８３に移行する。一方、実行状態ｐの次の命令が有る場合（ステップＳ６９：Ｙｅｓルート）、次の命令について処理するため、ステップＳ６１の処理に戻る。
【００４２】
以上のような処理を実行すれば、分岐先において未実行の命令が有るか否かがわかるので、パス刈りを実施してもよいか（すなわち、パスについてのシンボリック実行を途中で終了してもよいか）否かがわかるようになる。
【００４３】
図９の説明に戻り、実行エンジン１０４における実行部１１２は、判定処理の結果が、実行状態Ｐのパスにおける命令を「実行済み」であることを表しているか判断する（ステップＳ４７）。実行状態Ｐのパスにおける命令を実行済みではない場合（ステップＳ４７：Ｎｏルート）、ステップＳ５１の処理に移行する。
【００４４】
一方、実行状態Ｐのパスを実行済みである場合（ステップＳ４７：Ｙｅｓルート）、実行部１１２は、パスについてシンボリック実行を終了し、実行中の関数を、第２関数データ格納部１１０に追加する（ステップＳ４９）。第２関数データ格納部１１０には、例えば図１４に示すように、パス刈りを実施した関数のリストが格納される。
【００４５】
実行部１１２は、未処理の分岐先が有るか判断する（ステップＳ５３）。未処理の分岐先が有る場合（ステップＳ５３：Ｙｅｓルート）、次の分岐先について処理するため、ステップＳ４１の処理に戻る。一方、未処理の分岐先が無い場合（ステップＳ５３：Ｎｏルート）、処理は端子Ｂを介して図６の処理に戻る。
【００４６】
一方、ステップＳ２７において、読み出した命令はシンボル変数に関わる分岐ではないと判断された場合（ステップＳ２７：Ｎｏルート）、実行部１１２は、命令を実行し、プログラムカウンタを進める（すなわち、インクリメントする）（ステップＳ２９）。
【００４７】
実行部１１２は、実行状態ｐは終了の状態であるか判断する（ステップＳ３１）。終了の状態とは、例えば、プログラムカウンタの値がプログラムにおける最後の行の番号に達している状態である。終了の状態ではない場合（ステップＳ３１：Ｎｏルート）、次の命令について処理するため、ステップＳ２１の処理に戻る。
【００４８】
一方、実行状態ｐは終了の状態である場合（ステップＳ３１：Ｙｅｓルート）、生成部１１３は、シンボリック実行により得られたパス条件を満たす具体値をテストデータとして生成し（ステップＳ３３）、メインメモリ等の記憶装置に格納する。そして元の処理に戻る。
【００４９】
以上のような処理を実行すれば、諸条件が満たされた場合にパス刈りを実行するので、全パスを対象範囲としてシンボリック実行を行うことはなくなり、シンボリック実行に要する時間を減らすことができると共に、メモリ等の資源の消費を抑制できる。
【００５０】
図３の説明に戻り、実行エンジン１０４における実行部１１２は、カバレッジを算出する（ステップＳ９）。例えば目標カバレッジとして命令カバレッジについての目標値の入力を受け付けた場合には、ステップＳ９においては命令カバレッジを算出する。
【００５１】
実行部１１２は、算出されたカバレッジが目標カバレッジより大きいか判断する（ステップＳ１１）。目標カバレッジ以下である場合（ステップＳ１１：Ｎｏルート）、実行部１１２は、範囲制御部１０３にシンボリック実行の対象範囲の拡大を要求する。これに応じ、範囲制御部１０３は、コールグラフデータ格納部１１１に格納されているデータに基づき特定されるコールグラフにおける葉ノードから（ｎ−１）段上の階層に属するノードであり且つ前回のパス刈りの対象である関数を、第１関数データ格納部１０９におけるパス刈りの対象外になる関数のリストに追加する（ステップＳ１３）。また、範囲制御部１０３は、実行エンジン１０４に、再度シンボリック実行を行うことを要求する。そしてステップＳ３の処理に戻る。
【００５２】
なお、例えば図１５に示すようなコールグラフが得られたとする。図１５におけるｆｕｎｃ１のように、階層が異なる複数の関数を呼び出す関数が存在する場合には、葉ノードから（ｎ−１）段上の階層に属するノードを特定する方法が複数存在することになる。このような場合には、最も下の階層に属する葉ノードを基準として考えることにする。図１５の例では、ｆｕｎｃ４ではなくｆｕｎｃ３を基準として考えることにするので、ｆｕｎｃ１は葉ノードから２段上の階層に属するノードであるということになる。
【００５３】
また、プログラム内に再帰呼び出しが存在する場合には、図１６の左に示すように、コールグラフに葉ノードが無くなる。そこで、再帰呼び出しが存在することを検出した場合には、図１６の右に示すように、再帰呼び出しに相当するエッジを削除する。再帰呼び出しが存在することを検出するには、例えば、コールグラフの生成時にコールスタック中にこれから呼び出す関数がないか確認すればよい。
【００５４】
一方、目標カバレッジより大きい場合（ステップＳ１１：Ｙｅｓルート）、実行エンジン１０４における生成部１１３は、ステップＳ３３において生成されたテストデータをテストデータ格納部１１４に格納する（ステップＳ１５）。テストデータ格納部１１４に格納されたテストデータが、最終的に採用されるテストデータとなる。そして処理を終了する。
【００５５】
以上のような処理を実行すれば、パス刈りの範囲を徐々に縮小しつつ繰り返しシンボリック実行を行い、カバレッジが目標カバレッジを越えた時点におけるテストデータを採用できる。これにより、網羅性があるテストデータを効率的に生成できるようになる。
【００５６】
ここで、図４に示したプログラムを対象プログラムとして本実施の形態の処理を実行した場合について具体的に説明する。目標カバレッジは、命令カバレッジの目標値であり、９０％であるとする。
【００５７】
最初のシンボリック実行においては、パス刈りの対象外にする関数のリストが空であるため、プログラムにおける全パスがパス刈りの対象範囲になる。そして、シンボリック実行の途中において行番号１５乃至１９の命令は全て実行済みになるため、「ｉｎｔ  ｓｔｒｌｅｎ（ｃｈａｒ＊ｓ）」についてパス刈りが実施される。この結果、行番号１１乃至１４の命令は実行されなくなる。ここで命令カバレッジを計算すると、命令カバレッジは「（１９−４）／１９＊１００≒７９（％）になり、目標カバレッジ以下である。従って、パス刈りの対象範囲を狭めて再度シンボリック実行を行うことになる。
【００５８】
パス刈りの対象外になる関数は、コールグラフ（図８）において葉ノード（ｉｎｔ  ｓｔｒｌｅｎ（ｃｈａｒ＊ｓ））から（１−１＝）０段上の階層に属するノードであり且つ前回パス刈りされている関数であるので、「ｉｎｔ  ｓｔｒｌｅｎ（ｃｈａｒ＊ｓ）」である。
【００５９】
２回目のシンボリック実行においては、「ｉｎｔ  ｓｔｒｌｅｎ（ｃｈａｒ＊ｓ）」がパス刈りの対象外になるため、命令１１乃至１４も実行されるようになる。ここで命令カバレッジを計算すると、命令カバレッジは１９／１９＊１００＝１００（％）になり、目標カバレッジより大きい。従って、２回目のシンボリック実行により得られたパス条件を満たす具体値がテストデータとして採用される。
【００６０】
なお、目標カバレッジとして分岐カバレッジ又は条件カバレッジの目標値の入力を受け付けた場合も同様である。例えば、分岐カバレッジの目標値が９０（％）であるとする。最初のシンボリック実行の後に分岐カバレッジを計算すると、４／６＊１００≒６７（％）になり、目標カバレッジ以下である。従って、命令カバレッジの場合と同様にパス刈りの対象外になる関数を「ｉｎｔ  ｓｔｒｌｅｎ（ｃｈａｒ＊ｓ）」として再度シンボリック実行を行う。すると、分岐カバレッジは６／６＝１００（％）になり、目標カバレッジより大きい。従って、２回目のシンボリック実行により得られたパス条件を満たす具体値がテストデータとして採用される。
【００６１】
図１７の左に、図４に示したプログラムの実行木を示す。図１７の左に示すように、図４に示したプログラムには６つのパスが存在する。これに対し、本実施の形態の処理を実行すると、図１７の右に示すように、２つのパスについてはパス刈りにより途中で終了する。このようにパス刈りを行うとパスカバレッジは１００（％）にはならないが、上で説明したように、命令カバレッジは１００（％）である。
【００６２】
以上においては、パス刈りの範囲を制御する方法について説明したが、以下では、パス刈りの範囲を制御せず、プログラムにおける全パスをパス刈りの対象範囲とする場合について検討する。
【００６３】
図１８に、パス刈りの範囲を制御しない場合におけるメインの処理フローを示す。まず、シンボリック実行装置１における入力部１００は、シンボリック実行の対象になる対象プログラムの入力をユーザから受け付ける（図１８：ステップＳ９１）。入力部１００は、対象プログラムを対象プログラム格納部１０２に格納する。
【００６４】
実行エンジン１０４における実行部１１２は、状態データ格納部１０８に格納されている実行状態に関するデータを初期化することにより、実行状態ｐを初期化する（ステップＳ９３）。初期化とは、例えば、プログラムカウンタの値を１に戻し、コールスタックの内容をクリアし、シンボル変数の状態についての情報をメモリからクリアし、またパス条件をクリアすることである。
【００６５】
実行部１１２は、シンボリック実行（ｎｕｌｌ，ｐ）を行う（ステップＳ９５）。ここで行われるシンボリック実行（ｓ，ｐ）については、図１９を用いて説明する。なお、括弧内における１番目の文字列は実行済みである命令のリストを表しており、括弧内における２番目の文字列は実行状態を表す文字列である。ここでは、（ｎｕｌｌ，ｐ）は、実行済みである命令のリスト（すなわち、第２命令データ格納部１０７におけるリスト）が空である場合において、実行状態ｐが初期の状態からシンボリック実行を行うことを表している。
【００６６】
まず、実行部１１２は、実行状態ｐのプログラムカウンタに基づき１つの命令を対象プログラム格納部１０２に格納されている対象プログラムから読み出し、第２命令データ格納部１０７に追加する（図１９：Ｓ１０１）。
【００６７】
実行部１１２は、読み出した命令がシンボル変数に関わる分岐であるか判断する（ステップＳ１０３）。シンボル変数に関わる分岐とは、例えば、図４における行番号が９における「ｉｆ（ｓｔｒｌｅｎ（ｓ）＜＝１）」である。
【００６８】
シンボル変数に関わる分岐ではない場合（ステップＳ１０３：Ｎｏルート）、実行部１１２は、命令を実行し、プログラムカウンタを進める（すなわち、インクリメントする）（ステップＳ１１７）。
【００６９】
実行部１１２は、実行状態ｐは終了の状態であるか判断する（ステップＳ１１９）。終了の状態とは、例えば、プログラムカウンタの値がプログラムにおける最後の行の番号に達している状態である。終了の状態ではない場合（ステップＳ１１９：Ｎｏルート）、次の命令について処理するため、ステップＳ１０１の処理に戻る。
【００７０】
一方、実行状態ｐは終了の状態である場合（ステップＳ１１９：Ｙｅｓルート）、生成部１１３は、シンボリック実行により得られたパス条件を満たす具体値をテストデータとして生成し（ステップＳ１２１）、メインメモリ等の記憶装置に格納する。そして元の処理に戻る。
【００７１】
一方、ステップＳ１０３において、読み出した命令はシンボル変数に関わる分岐であると判断された場合（ステップＳ１０３：Ｙｅｓルート）、実行部１１２は、分岐において未処理の分岐先（実行状態をＰとする）を１つ特定する（ステップＳ１０５）。
【００７２】
実行部１１２は、判定部１０５に判定処理の実行を要求する。これに応じ、判定部１０５は、判定処理（ｓ，Ｐ，ｎｕｌｌ）を実行する（ステップＳ１０７）。判定処理については、図１１乃至図１３を用いて説明したとおりである。なお、括弧内における１番目の文字列は実行済みである命令のリストを表しており、括弧内における２番目の文字列は実行状態を表す文字列であり、括弧内における３番目の文字列は探索済みである分岐の命令のリストを表している。ここでは、（ｓ，Ｐ，ｎｕｌｌ）は、実行済みである命令のリスト（すなわち、第２命令データ格納部１０７におけるリスト）がｓという状態であり且つ探索済みである分岐の命令のリスト（すなわち、第１命令データ格納部１０６におけるリスト）が空である状態において、実行状態Ｐについて判定処理を行うことを表している。
【００７３】
実行エンジン１０４における実行部１１２は、判定処理の結果が、実行状態Ｐのパスにおける命令を「実行済み」であることを表しているか判断する（ステップＳ１０９）。実行状態Ｐのパスにおける命令を実行済みである場合（ステップＳ１０９：Ｙｅｓルート）、実行部１１２は、パスについてシンボリック実行を終了する（ステップＳ１１１）。
【００７４】
一方、実行状態Ｐのパスにおける命令を未実行である場合（ステップＳ１０９：Ｎｏルート）、実行部１１２は、シンボリック実行（ｓ，Ｐ）を行う（ステップＳ１１３）。ここでは、（ｓ，Ｐ）は、実行済みである命令のリスト（すなわち、第２命令データ格納部１０７におけるリスト）がｓという状態である場合において、実行状態Ｐについてシンボリック実行を行うことを表している。
【００７５】
実行部１１２は、未処理の分岐先が有るか判断する（ステップＳ１１５）。未処理の分岐先が有る場合（ステップＳ１１５：Ｙｅｓルート）、次の分岐先について処理するため、ステップＳ１０５の処理に戻る。一方、未処理の分岐先が無い場合（ステップＳ１１５：Ｎｏルート）、処理は図１８に戻り終了する。
【００７６】
以上のようにすれば、パス刈りの範囲を制御せず、プログラムにおける全パスをパス刈りの対象範囲とすることができる。
【００７７】
このような処理を行ったとしても、命令カバレッジの低下を抑えつつ一部のパスについては省略を実行できる場合がある。例えば図２０に示す対象プログラムの場合は、命令カバレッジの低下を抑えつつ一部のパスについては省略を実行できる。図２０に示した対象プログラムは、メインの処理を表すコードにおいて関数「ｉｎｔ  ｆｕｎｃＡ（ｉｎｔ  ａ，ｉｎｔ  ｂ）」を呼び出し、関数「ｉｎｔ  ｆｕｎｃＡ（ｉｎｔ  ａ，ｉｎｔ  ｂ）」において関数「ｉｎｔ  ａｂｓ（ｉｎｔ  ｘ）」を呼び出すプログラムである。命令の数は１９である。なお、命令１乃至７におけるいずれかの命令を実行中におけるコールスタックは「ｓｔａｃｋ３」のようになっており、命令８乃至１５におけるいずれかの命令を実行中におけるコールスタックは「ｓｔａｃｋ２」のようになっており、命令１６乃至１９におけるいずれかの命令を実行中におけるコールスタックは「ｓｔａｃｋ１」のようになっている。
【００７８】
図２１に、図２０に示した対象プログラムの実行木を示す。図２１における実行木においては、各実行状態について、プログラムカウンタの値、コールスタックの識別情報（図２０における識別情報に対応している）、シンボル変数の状態についての情報及びパス条件が示されている。図２０に示した対象プログラムに対して図１８及び図１９で説明した処理によってパス刈りを実行すると、実行状態６及び７に対応するパスについては、ａ＜０という条件に関連するパスによって命令が実行済みとなっているため、パス刈りが実施される。但し、命令カバレッジが低下することはない。
【００７９】
しかし、対象プログラムの構造によっては、命令カバレッジが低下することがある。例えば、図４に示した対象プログラムの場合には命令カバレッジが低下する。図２２の右には、図４に示した対象プログラムに対して図１８及び図１９で説明した処理によってパス刈りを実行した場合の結果を示す。シンボリック実行中、「！ｓ［０］」のパスにおいて命令１５乃至１９が実行済みになるため、バツ印を付した部分に対してパス刈りが実施される。そのため、点線で囲った部分に相当するパスについては実行されなくなる。この際の命令カバレッジは、パス刈りの範囲を制御した場合における初回のシンボリック実行についての命令カバレッジと同じであり、「（１９−４）／１９＊１００≒７９（％）」である。
【００８０】
このように、パス刈りの範囲を制御せず、プログラムにおける全パスをパス刈りの対象範囲とする場合には、命令カバレッジ（条件カバレッジ及び分岐カバレッジも同様）が低下する場合がある。従って、図３乃至図１７を用いて説明したようにパス刈りの対象範囲を制御した方が、命令カバレッジ（条件カバレッジ及び分岐カバレッジも同様）が目標値以上になるようにパス刈りを行うことができるため有効である。
【００８１】
以上本発明の一実施の形態を説明したが、本発明はこれに限定されるものではない。例えば、上で説明したシンボリック実行装置１の機能ブロック構成は実際のプログラムモジュール構成に一致しない場合もある。
【００８２】
また、上で説明した各テーブルの構成は一例であって、上記のような構成でなければならないわけではない。さらに、処理フローにおいても、処理結果が変わらなければ処理の順番を入れ替えることも可能である。さらに、並列に実行させるようにしても良い。
【００８３】
なお、上で述べたシンボリック実行装置１は、コンピュータ装置であって、図２３に示すように、メモリ２５０１とＣＰＵ（Central Processing Unit）２５０３とハードディスク・ドライブ（ＨＤＤ：Hard Disk Drive）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。ＣＰＵ２５０３は、アプリケーション・プログラムの処理内容に応じて表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、所定の動作を行わせる。また、処理途中のデータについては、主としてメモリ２５０１に格納されるが、ＨＤＤ２５０５に格納されるようにしてもよい。本発明の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及びアプリケーション・プログラムなどのプログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【００８４】
以上述べた本発明の実施の形態をまとめると、以下のようになる。
【００８５】
本実施の形態に係るテストデータ生成方法は、（Ａ）シンボリック実行の対象範囲のうち一部の範囲を省略してシンボリック実行を行い、当該シンボリック実行について網羅率を算出する第１処理と、（Ｂ）算出された網羅率が所定の値を超えたか判断する第２処理と、（Ｃ）算出された網羅率が所定の値を超えていない場合、省略された一部の範囲のうち少なくとも一部が省略の対象外になるように設定し、第１処理以降の処理を再度実行する第３処理と、（Ｄ）算出された網羅率が所定の値を超えた場合に、シンボリック実行により得られるパスの条件を満たす値を、第１データ格納部に格納する第４処理とを含む。
【００８６】
このようにすれば、網羅率が所定の値を超えるために最低限のシンボリック実行を行えば済むので、網羅性があるテストデータを効率的に生成できるようになる。
【００８７】
また、上で述べた第１処理において、（ａ１）プログラム内の分岐によって生じる複数の分岐先の各々において未実行の命令が無い場合には分岐に関連するパスについてシンボリック実行を終了することにより、一部の範囲を省略してシンボリック実行を行うようにしてもよい。このようにすれば、網羅率の向上に寄与しない可能性が高いパスを省略できるので、シンボリック実行に要する時間を短縮し、またコンピュータの資源の消費を抑制できるようになる。
【００８８】
また、上で述べた第３処理において、（ｃ１）省略した一部の範囲に含まれる関数のうち所定の方法によって特定された関数を省略の対象外に決定するようにしてもよい。このように、関数の単位で省略の対象外を定めれば、省略の対象外にする範囲を適切に定めることができる。
【００８９】
また、上で述べた所定の方法が、関数の呼び出し関係に基づき生成されるコールグラフにおいて最も下の階層に属する関数から順に特定するという方法であってもよい。このようにすれば、省略範囲が徐々に減るようにすることができるようになる。
【００９０】
また、上で述べた網羅率が、命令網羅率、条件網羅率及び分岐網羅率のうち少なくともいずれかを含むようにしてもよい。通常のシンボリック実行は経路網羅率が１００％になるように行われるが、命令網羅率、条件網羅率又は分岐網羅率が所定の値であればよいという場合には、通常のシンボリック実行を行うと無駄が多い。そこで、網羅率として上で述べたような網羅率を採用すれば、無駄にシンボリック実行を行わなくて済む。
【００９１】
なお、上記方法による処理をコンピュータに行わせるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブルディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。尚、中間的な処理結果はメインメモリ等の記憶装置に一時保管される。
【００９２】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【００９３】
（付記１）
シンボリック実行の対象範囲のうち一部の範囲を省略して前記シンボリック実行を行い、当該シンボリック実行について網羅率を算出する第１処理と、
算出された前記網羅率が所定の値を超えたか判断する第２処理と、
算出された前記網羅率が前記所定の値を超えていない場合、省略された前記一部の範囲のうち少なくとも一部が省略の対象外になるように設定し、前記第１処理以降の処理を再度実行する第３処理と、
算出された前記網羅率が前記所定の値を超えた場合に、前記シンボリック実行により得られたパスの条件を満たす値を、第１データ格納部に格納する第４処理と、
をコンピュータが実行するテストデータ生成方法。
【００９４】
（付記２）
前記第１処理において、
プログラム内の分岐によって生じる複数の分岐先の各々において未実行の命令が無い場合には前記分岐に関連するパスについて前記シンボリック実行を終了することにより、前記一部の範囲を省略して前記シンボリック実行を行う
ことを特徴とする付記１記載のテストデータ生成方法。
【００９５】
（付記３）
前記第３処理において、
省略した前記一部の範囲に含まれる関数のうち所定の方法によって特定された関数を省略の対象外に決定する
ことを特徴とする付記１又は２記載のテストデータ生成方法。
【００９６】
（付記４）
前記所定の方法が、
関数の呼び出し関係に基づき生成されるコールグラフにおいて最も下の階層に属する関数から順に特定するという方法である
ことを特徴とする付記３記載のテストデータ生成方法。
【００９７】
（付記５）
前記網羅率が、
命令網羅率、条件網羅率及び分岐網羅率のうち少なくともいずれかを含む
ことを特徴とする付記１乃至４のいずれか１つ記載のテストデータ生成方法。
【００９８】
（付記６）
シンボリック実行の対象範囲のうち一部の範囲を省略して前記シンボリック実行を行い、当該シンボリック実行について網羅率を算出する第１処理と、
算出された前記網羅率が所定の値を超えたか判断する第２処理と、
算出された前記網羅率が前記所定の値を超えていない場合、省略された前記一部の範囲のうち少なくとも一部が省略の対象外になるように設定し、前記第１処理以降の処理を再度実行する第３処理と、
算出された前記網羅率が前記所定の値を超えた場合に、前記シンボリック実行により得られたパスの条件を満たす値を、第１データ格納部に格納する第４処理と、
をコンピュータに実行させるためのテストデータ生成プログラム。
【００９９】
（付記７）
シンボリック実行の対象範囲のうち一部の範囲を省略して前記シンボリック実行を行い、当該シンボリック実行について網羅率を算出すると共に、算出された前記網羅率が所定の値を超えたか判断する第１処理部と、
算出された前記網羅率が前記所定の値を超えていない場合、省略された前記一部の範囲のうち少なくとも一部が省略の対象外になるように設定し、前記第１処理部に処理を再度実行させる第２処理部と、
算出させた前記網羅率が前記所定の値を超えた場合に、前記シンボリック実行により得られたパスの条件を満たす値を、第１データ格納部に格納する第３処理部と、
を有するテストデータ生成装置。
【符号の説明】
【０１００】
１  シンボリック実行装置    １００  入力部
１０１  目標カバレッジ格納部    １０２  対象プログラム格納部
１０３  範囲制御部    １０４  実行エンジン
１０５  判定部    １０６  第１命令データ格納部
１０７  第２命令データ格納部    １０８  状態データ格納部
１０９  第１関数データ格納部    １１０  第２関数データ格納部
１１１  コールグラフデータ格納部    １１２  実行部
１１３  生成部    １１４  テストデータ格納部
【図１】
2014127091.tif 000003
【図２】
2014127091.tif 000004
【図３】
2014127091.tif 000005
【図４】
2014127091.tif 000006
【図５】
2014127091.tif 000007
【図６】
2014127091.tif 000008
【図７】
2014127091.tif 000009
【図８】
2014127091.tif 000010
【図９】
2014127091.tif 000011
【図１０】
2014127091.tif 000012
【図１１】
2014127091.tif 000013
【図１２】
2014127091.tif 000014
【図１３】
2014127091.tif 000015
【図１４】
2014127091.tif 000016
【図１５】
2014127091.tif 000017
【図１６】
2014127091.tif 000018
【図１７】
2014127091.tif 000019
【図１８】
2014127091.tif 000020
【図１９】
2014127091.tif 000021
【図２０】
2014127091.tif 000022
【図２１】
2014127091.tif 000023
【図２２】
2014127091.tif 000024
【図２３】
2014127091.tif 000025