(57)【要約】【課題】プログラムの修正前のテスト資産を利用して、プログラム修正後のテストのコストを削減する。【解決手段】テストデータ生成装置は、修正前のプログラムのテストで用いる第１のテストデータと、修正後のプログラムのソースコードに含まれる条件により分岐されて通過する処理経路の組み合わせで示される実行経路を論理式により表した経路条件を示す経路条件情報とを取得し、取得した第１のテストデータをテストデータ格納部に格納し、取得した経路条件情報を経路条件格納部に格納し、経路条件格納部に格納した経路条件情報から、テストデータ格納部に格納した第１のテストデータと論理的に同値でない経路条件情報を抽出し、抽出した経路条件情報が示す経路条件を充足する第２のテストデータを生成することにより、上記課題の解決を図る。【選択図】図１
2014021686.tif 000002
【特許請求の範囲】
【請求項１】
修正前のプログラムのテストで用いる第１のテストデータと、修正後の該プログラムのソースコードに含まれる条件により分岐されて通過する処理経路の組み合わせで示される実行経路を論理式により表した経路条件を示す経路条件情報とを取得する入力情報取得部と、
取得した前記第１のテストデータを格納するテストデータ格納部と、
取得した前記経路条件情報を格納する経路条件格納部と、
前記経路条件格納部に格納した経路条件情報から、前記テストデータ格納部に格納した第１のテストデータと論理的に同値でない経路条件情報を抽出する抽出部と、
抽出した前記経路条件情報が示す経路条件を充足する第２のテストデータを生成する生成部と、
を備えることを特徴とするテストデータ生成装置。
【請求項２】
前記入力情報取得部は、修正前のソースコードに含まれる条件により分岐されて通過する処理経路の組み合わせで示される実行経路を論理式により表した経路条件を充足する前記第１のテストデータを取得する
ことを特徴とする請求項１に記載のテストデータ生成装置。
【請求項３】
前記抽出部は、前記経路条件格納部に格納した経路条件情報が前記第１のテストデータと論理的に同値である第１の経路条件情報であるかを判定し、
前記テストデータ生成装置は、さらに、
前記経路条件格納部に格納された経路条件情報を、前記論理的に同値である情報、同値でない情報の順に並び替え、該並び替えた経路条件情報を、１以上の原子論理式を含む論理式である目標論理式に、分解する分解部と、
分解された前記目標論理式を前記経路条件情報毎に関係付けた情報である経路分解情報を格納する分解格納部と、
前記目標論理式を格納する目標論理式格納部と、
前記分解格納部から前記経路分解情報を取得し、該取得した経路分解情報が前記目標論理式格納部に格納された前記目標論理式以外の目標論理式である差分の論理式を含む場合、該差分の論理式を抽出して前記目標論理式格納部に格納する目標論理式取得部と、
前記取得した経路条件情報から、前記差分の論理式が抽出された前記経路分解情報に対応する第２の経路条件情報を選択する選択部と、
選択された前記第２の経路条件情報と前記第1の経路条件情報との差分を取得する差分取得部と、
を備え、
前記生成部は、前記差分として取得した経路条件情報から、前記第２のテストデータを生成する
ことを特徴とする請求項１または２に記載のテストデータ生成装置。
【請求項４】
コンピュータに、
修正前のプログラムのテストで用いる第１のテストデータと、修正後の該プログラムのソースコードに含まれる条件により分岐されて通過する処理経路の組み合わせで示される実行経路を論理式により表した経路条件を示す経路条件情報とを取得し、
取得した前記第１のテストデータをテストデータ格納部に格納し、
取得した前記経路条件情報を経路条件格納部に格納し、
前記経路条件格納部に格納した経路条件情報から、前記テストデータ格納部に格納した第１のテストデータと論理的に同値でない経路条件情報を抽出し、
抽出した前記経路条件情報が示す経路条件を充足する第２のテストデータを生成する、
処理を実行させることを特徴とするテストデータ生成プログラム。
【請求項５】
前記経路条件情報の取得において、修正前のソースコードに含まれる条件により分岐されて通過する処理経路の組み合わせで示される実行経路を論理式により表した経路条件を充足する前記第1のテストデータを取得する
ことを特徴とする請求項４に記載のテストデータ生成プログラム。
【請求項６】
前記経路条件情報の抽出において、前記経路条件格納部に格納した経路条件情報が前記第１のテストデータと論理的に同値である第1の経路条件情報であるかを判定し、
前記コンピュータは、さらに、
前記経路条件格納部に格納された経路条件情報を、前記論理的に同値である情報、同値でない情報の順に並び替え、該並び替えた経路条件情報を、１以上の原子論理式を含む論理式である目標論理式に、分解し、
前記分解された目標論理式を前記経路条件情報毎に関係付けた情報である経路分解情報を分解格納部に格納し、
前記分解格納部から前記経路分解情報を取得し、該取得した経路分解情報が前記目標論理式が格納された目標論理式格納部に格納された前記目標論理式以外の目標論理式である差分の論理式を含む場合、該差分の論理式を抽出して前記目標論理式格納部に格納し、
前記取得した経路条件情報から、前記差分の論理式が抽出された前記経路分解情報に対応する経路条件情報を選択し、
選択された前記第２の経路条件情報と前記第1の経路条件情報との差分を取得する
処理を実行させ、
前記テストデータの生成において、前記差分として取得した経路条件情報から、前記第２のテストデータを生成する
ことを特徴とする請求項４または５に記載のテストデータ生成プログラム。
【請求項７】
コンピュータにより実行されるテストデータ生成方法であって、
前記コンピュータは、
修正前のプログラムのテストで用いる第１のテストデータと、修正後の該プログラムのソースコードに含まれる条件により分岐されて通過する処理経路の組み合わせで示される実行経路を論理式により表した経路条件を示す経路条件情報とを取得し、
取得した前記第１のテストデータをテストデータ格納部に格納し、
取得した前記経路条件情報を経路条件格納部に格納し、
前記経路条件格納部に格納した経路条件情報から、前記テストデータ格納部に格納した第１のテストデータと論理的に同値でない経路条件情報を抽出し、
抽出した前記経路条件情報が示す経路条件を充足する第２のテストデータを生成する、
処理を実行させるテストデータ生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本技術は、プログラムの動作をテストするためのテストデータを生成する技術に関する。
【背景技術】
【０００２】
業務システムが仕様通りに設計されているかを検証するためにテストが行われる。そのようなテストは、業務仕様（業務として意味のある項目間の関係や変化）に関するチェックや、境界値テスト等のプログラムのエラーがデータの境界で起こりやすいという経験則からのチェックなど、様々な観点より行われる。そのため、チェック内容に応じて、１つの業務仕様に対して複数のテストデータが用意される。
【０００３】
業務仕様からテストデータを自動的に生成するための技術として、テストしたい状況が表現された制約式（画面、データベース（DB）項目やプログラム変数を用いた論理式）の充足可能性判定問題を解くことで充足値をテストデータとして用いる技術がある。そのようなプログラムのテストを行う際のテストデータを作成する技術の１つに、シンボリック実行（symbolic execution）がある。シンボリック実行とは、変数を具体的な値としてではなく、シンボル値という値を１つに特定しないで実行する仕組みをいう。シンボリック実行では、ある一連の遷移についてその遷移を流れることになるテストデータを、そのプログラムが取り得る一連の遷移の各々について作成することができる。
【０００４】
ところで、既存のプログラムを改修した際は、そのプログラムのテストを行う。テストでは、テスト対象の処理に与えるデータ（入力データ）と、そのデータが与えられた際にプログラムが処理をして得られる値（出力データ）とを準備しておく。そして、その入力データをそのテスト対象の処理に与えた場合に、仕様の上で、処理によって得られる値と、準備していた出力データを対比することで、そのプログラムが仕様の通りの処理を実行しているかを判断する。
【０００５】
また、プログラムのテストを行う際に、全ての処理フローを網羅したテストが出来るように、プログラムの開始から終了までを処理で用いられる変数の値を変更して、１〜複数回、テストを実行することがある。
【０００６】
このような、ソフトウェア開発では、実装されたプログラムの動作テストを効率よく行うため、例えば、次のようなソフトウェア試験支援技術がある。
【０００７】
第１の技術としては、入力された状態変数に基づいて、ソースコードの解析結果から状態遷移情報を抽出し、試験シナリオによって提供される設計情報に基づく状態遷移情報との比較により、両者の異同を検出する技術がある。
【０００８】
第２の技術としては、次の技術がある。ユーザ端末より、ＵＭＬクラス図とアクティビティ図のみで記述した設計モデルを読み込み、設計モデルからアクティビティ図をテスト対象として抽出し、テスト対象から実行経路を抽出する。抽出された各実行経路の制約条件に基づいて、テストデータ仕様を更新する。テストデータ仕様を読み込み、因子毎に、「水準」を生成し、因子と水準の組み合わせである「入力」に対する実行経路を取得する。「入力」が実行経路にとって許容する入力である正常入力、または、該実行経路にとって許容しない入力である異常入力のいずれであるか、及び、実行経路中に事後条件が含まれるか否かにより期待値を求め、「入力」に該期待値を付与したテストデータを生成する。
【０００９】
第３の技術としては、過去に行われたテストのテストケースについての情報を保存しておき、その情報と対象プログラムを解析して得られた依存関係を組み合わせることによりテストを行うリグレッションシステムがある。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２００５−３１６７１０号公報
【特許文献２】特開２０１０−２６７０２３号公報
【特許文献３】特開２００８−２０４４０５号公報
【発明の概要】
【発明が解決しようとする課題】
【００１１】
修正をしたプログラムについて、シンボリック実行で網羅的にテストをする際に、そのプログラムについて新たにシンボリック実行を行い、得られたテストケースに対応するテストデータを用いてテストをする。
【００１２】
このとき、そのテストケースでそのテストデータが与えられた際に、前述の仕様の上で得られるべき値（出力値）については、手計算で求めているので、工数が掛かる。
しかしながら、得られたテストケースには、修正の影響を受けないものもあり、そのようなテストケースに対応するテストデータ及びその出力値を再度生成することは工数的に無駄である。
【００１３】
そこで、プログラムの修正前のテスト資産を利用して、プログラム修正後のテストのコストを削減する技術を提供する。
【課題を解決するための手段】
【００１４】
本実施形態の１つの側面にかかるテストデータ生成装置は、入力情報取得部、テストデータ格納部、経路条件格納部、抽出部、生成部を含む。入力情報取得部は、第１のテストデータと、経路条件情報とを取得する。第１のテストデータは、修正前のプログラムのテストで用いる。経路条件情報は、修正後の該プログラムのソースコードに含まれる条件により分岐されて通過する処理経路の組み合わせで示される実行経路を論理式により表した経路条件を示す。テストデータ格納部は、取得した第１のテストデータを格納する。経路条件情納部は、取得した経路条件情報を格納する。抽出部は、経路条件格納部に格納した経路条件情報から、テストデータ格納部に格納した第１のテストデータと論理的に同値でない経路条件情報を抽出する。生成部は、抽出した経路条件情報が示す経路条件を充足する第２のテストデータを生成する。
【発明の効果】
【００１５】
本実施形態の１つの観点によればプログラムの修正前のテスト資産を利用して、プログラム修正後のテストのコストを削減することができる。
【図面の簡単な説明】
【００１６】
【図１】ソースコードの一例である。
【図２】シンボリック実行によるテストケース生成を説明するための図である。
【図３】プログラムの修正に伴う再テストについて説明するための図（その１）である。
【図４】プログラムの修正に伴う再テストについて説明するための図（その２）である。
【図５】修正前後のパスコンディションの対応付けについて説明するための図である。
【図６】本実施形態におけるテストデータ生成装置の一例を示す。
【図７】本実施形態（実施例１）におけるテストデータ生成装置の構成の一例を示す。
【図８】本実施形態（実施例１）における入力データを説明するための図である。
【図９】本実施形態（実施例１）におけるテストデータ条件テーブルの一例を示す。
【図１０】本実施形態（実施例１）におけるパスコンディションテーブルの一例を示す。
【図１１】本実施形態（実施例１）におけるマッチング部の処理について説明するための図である。
【図１２】図１０のパスコンディションテーブルにデータ項目「マッチフラグ」を追加した一例を示す。
【図１３】図１２に示すパスコンディションテーブルから、マッチフラグが付与されていないパスコンディションを抽出して得られたパスコンディション情報の一例を示す。
【図１４】本実施形態（実施例１）において、生成されるテストデータの一例を示す。
【図１５】本実施形態（実施例１）におけるテストデータ生成フロー（その１）の一例を示す。
【図１６】本実施形態（実施例１）におけるテストデータ生成フロー（その２）の一例を示す。
【図１７】本実施形態（実施例１）におけるテストデータ生成フロー（その３）の一例を示す。
【図１８】本実施形態（実施例２）におけるテストデータ生成装置の構成の一例を示す。
【図１９】図１２のパスコンディションテーブル１９において、マッチフラグが付与されたパスコンディションがテーブルの先頭側になるように並べ替えた様子を示す。
【図２０】本実施形態（実施例２）におけるテストケース選択部の処理内容を説明するための図である。
【図２１】本実施形態（実施例２）のテストケース選択処理を説明するための図である。
【図２２】本実施形態（実施例２）における原子論理式テーブルの一例を示す。
【図２３】図２２の原子論理式テーブルにデータ項目「選択」５１３を追加した一例を示す。
【図２４】本実施形態（実施例２）における目標論理式テーブルの一例を示す。
【図２５】本実施形態（実施例２）における選択パスコンディションテーブルの一例を示す。
【図２６】本実施形態（実施例２）における選択パスコンディションテーブルに格納されたパスコンディションと、マッチフラグが付与されたパスコンディションとの差分について説明するための図である。
【図２７】本実施形態（実施例２）におけるデータ生成部１５の処理を説明するための図である。
【図２８】本実施形態（実施例２）におけるテストデータ生成フロー（その１）の一例を示す。
【図２９】本実施形態（実施例２）におけるテストデータ生成フロー（その２）の一例を示す。
【図３０】本実施形態（実施例２）におけるテストデータ生成フロー（その３）の一例を示す。
【図３１】本実施形態（実施例２）におけるテストケース選択フロー（その１）の一例を示す。
【図３２】本実施形態（実施例２）におけるテストケース選択フロー（その２）の一例を示す。
【図３３】本実施形態（実施例２）におけるテストケース選択フロー（その３）の一例を示す。
【図３４】本実施形態を適用したコンピュータのハードウェア環境の構成ブロック図である。
【発明を実施するための形態】
【００１７】
上述したように、プログラムを解析し、実行可能なパスを抽出する技術として、シンボリック実行がある。実行可能なパスとは、ソースコードについてシンボリック実行を行った場合に、条件判定に応じてそれぞれの遷移先へ分岐する実行経路のことである。シンボリック実行が抽出した各パスは、パスコンディションと呼ばれるプログラム変数に関する条件式（変数が関わる分岐条件や、代入式等に関する条件式）を保持しており、このパスコンディションからテストケース（テストデータ）を生成することができる。ここで、図１及び図２を用いて、シンボリック実行について説明する。
【００１８】
図１は、ソースコードの一例である。図２は、シンボリック実行によるテストケース生成を説明するための図である。シンボリック実行は、そのプログラムに含まれる変数に具体的な数値を入力する代わりに、数値を代表するシンボルでプログラムを模擬的に実行し、その結果を評価する技術である。プログラムにおいてシンボル値が分岐等の判定条件に利用された場合、シンボリック実行を行うと、論理的に可能なシンボル値の組み合わせを加味しながらプログラムが実行される（シンボリック実行ツリーの生成）。
【００１９】
例えば、図１に示すようなソースコードをシンボリック実行する場合を考える。図１のソースコードでは、２つのｉｆ文が記述されている。図１のソースコードについてシンボリック実行を行う。すると、変数a、ｂ、ｃの値に対応するシンボル値Sa、Sb、Scについて、図２に示すように、シンボリック実行ツリーが生成される。例えば、図１に記述されたコード「a >= 0  & a <= 5」は、「Sa >= 0  ∧ Sa <= 5」で表される。また、図１に記述されたコード「b>0 & c > 0」は、「Sb>0 ∧ Sc > 0」で表される。
【００２０】
シンボリック実行ツリーにおいて判定条件より分岐する経路は、シンボリック実行で代入文や条件文などを通過したときに満たすべき論理的な制約（すなわちパスコンディション）を表している。シンボリック実行では、パスコンディションを代入文や条件文などを通過する毎に積み上げる処理を行う。
【００２１】
シンボリック実行ツリー内の根（ルート）から葉（リーフ）までの経路を実行パスという。実行パスは、各シンボルに対する条件（パスコンディション）を有している。例えば、図２のシンボリックツリーにおいて、実行パスＰのパスコンディション（破線で囲まれた部分）は、「Sa >= 0  ∧ Sa <= 5 ∧ Sb>0 ∧ Sc > 0」で示される。
【００２２】
このようなシンボリック実行の後に、パスコンディションを充足する値があるか否かの判定は、すなわち、論理式が矛盾していないことを示すための判定は、論理式全体を真とするような各部分論理式の真偽時の組み合わせが存在することを示せばよい。論理式の無矛盾性を調べる処理として、論理式を充足可能であるか（真に成り得るか）否かを判定するためには充足可能性判定処理器、すなわち、ＳＡＴ（satisfiability）又はＳＭＴ（satisfiability modulo theory）ソルバ等の制約ソルバが利用される。制約ソルバは、複数の変数を含む数式を制約条件とし、制約条件の範囲内で目標値を得るための解の組み合わせを求めることができる。なお、シンボリック実行は、ＪＰＦ（Java（登録商標） Path Finder）などのモデル検査エンジンと組み合わせて使用される場合もある。
【００２３】
ここで、実行パスは、テストケースとして示すことができる。また、パスコンディション内のシンボル値の充足値は、テストデータとして示すことができる。このように、シンボリック実行を用いることにより、論理的に可能なパスコンディションの組み合わせの範囲でテストケースのバリエーションを生成することができる。
【００２４】
そこで、シンボリック実行では、条件分岐においてその充足可能な全ての実行パスを自動的に発生させて、プログラムの網羅的な実行を可能としている。このとき、主に冗長で膨大になりがちなテストケース自動生成技術により生成されたテストケースから、ある観点・価値（コードカバレッジ、類似性等）に基づきテストケースを選択し、テストケース数を削減することが要求される。
【００２５】
コードカバレッジには、たとえば、ステートメントカバレッジ、ブランチカバレッジ、条件カバレッジ、マルチ条件カバレッジ、パスカバレッジ等がある。シンボリック実行により生成されるテストケースはパスカバレッジに基づくものである。
【００２６】
ところで、開発が完了しているプログラムの修正を行った場合は、プログラムの再テストが行われる。再テストにおいては、プログラムが変更されなかった部分については、それまでの機能がそのまま同様に動作することを確認し、プログラムが変更された部分については、変更された機能についてテスト仕様書を作成して、テストすることが要求される。
【００２７】
そこで、このシンボリック実行技術を利用して、プログラムが変更された部分についてテストをするための差分テストケース（テストデータ）を抽出する方法が考えられる。具体的には、プログラムの修正前後のパスコンディションを生成し、修正前のパスコンディションに一致しない修正後のパスコディションを差分と捉え、追加テストケースを生成するという方法が考えられる。
【００２８】
図３及び図４は、プログラムの修正に伴う再テストについて説明するための図である。図３（Ａ）は、修正前のプログラムの実行パスを示し、図３（Ｂ）は、その実行パスに対応するテストケースを示す。図３において、実行パスは４つ存在する（No.1, No.2, No.3, No.4）。
【００２９】
テストケースNo.1のテストデータは「a=-1, b=0, c=0, d=null」である。テストケースNo.2のテストデータは「a=0, b=5, c=0, d=null」である。テストケースNo.3のテストデータは「a=0, b=5, c=1, d=””」である。テストケースNo.4のテストデータは「a=0, b=4, c=0, d=null」である。図３のプログラムは、これらのテストケース（ブランチカバレッジ）を用いて、既にテストが完了しているものとする。
【００３０】
図４（Ａ）は、図３の修正後のプログラムを示し、図４（Ｂ）は、その実行パスに対応するテストケースを示す。図３において、条件「b>=5」「b<=5」が、図４では、条件「b>=10」「b<=10」と変更されている。また、図３と比較して、図４では、条件「d.length<5」、「d.length>=5」が追加されている。ここで、テストケースNo.1〜No.4については再利用することができる。この場合、テストケースNo.1〜No.4でカバーされないパス（星印）を通過するテストケースを追加することが要求される。
【００３１】
このように、開発が完了しているプログラムの修正を新たに行った場合は、その修正部分について再テストする必要がある。このとき、修正前プログラムに対するテストケースに対して、新たに追加すべきテストケースを特定して再テストするのが効率的である。
【００３２】
そこで、修正プログラムに対して追加テストケースを生成するためには、修正前後のパスコンディションを生成し、修正前のパスコンディションに対応付かない修正後のパスコディションを差分と捉え、追加テストケースを生成するという方法が考えられる。しかしながら、図５で説明するように、再利用可能なテストケースを対応づけることができないことが考えられる。
【００３３】
図５は、修正前後のパスコンディションの対応付けについて説明するための図である。図５に示すように、修正前後のパスコンディションにおいて、文字列が同一なもの同士については対応付けすることができる。しかしながら、修正前後のパスコンディションにおいて、文字列が同一でないもの同士の対応づけは容易ではない。例えば、パスコンディションPC2（テストデータ： a=-1, b=0, c=0, d=“”）は、文字列の比較でPC’2, PC’3と部分的に対応していると判断可能である。しかし、パスコンディションPC2がPC’2, PC’3のどちらのパスコンディションに対応するかまではパスコンディションの比較では判断することはできない。
【００３４】
また、実際には修正前後のパスコンディション間で対応しているにも関わらず、文字列の比較によっては対応付けができなかったパスコンディションを新たにテストケースとして追加すると、既存のテストケースを追加することとなり、テストの効率が悪くなる。
【００３５】
そこで、本実施形態では、プログラムの修正前のテスト資産を利用して、プログラムが変更された部分についてテストするための差分テストケース（テストデータ）を生成する技術を説明する。
【００３６】
図６は、本実施形態におけるテストデータ生成装置の一例を示す。テストデータ生成装置１は、入力情報取得部１−１、抽出部１−２、生成部１−３、テストデータ格納部１−８、経路条件格納部１−９を含む。
【００３７】
入力情報取得部１−１は、第１のテストデータ２と、経路条件情報３とを取得する。第1のテストデータ２は、修正前のプログラムのテストで用いるデータである。経路条件情報３は、修正後の該プログラムのソースコードに含まれる条件により分岐されて通過する処理経路の組み合わせで示される実行経路を論理式により表した経路条件（パスコンディション）を示す。入力情報取得部１−１は、修正前のソースコードに含まれる条件により分岐されて通過する処理経路の組み合わせで示される実行経路を論理式により表した経路条件を充足する第1のテストデータを取得する。入力情報取得部１−１の一例としては、取得部１３が挙げられる。
【００３８】
テストデータ格納部１−８は、取得した第１のテストデータを格納する。テストデータ格納部１−８の一例としては、テストデータ条件テーブル１８が挙げられる。
【００３９】
経路条件格納部１−９は、取得した経路条件情報を格納する。経路条件格納部１−９の一例としては、パスコンディションテーブル１９が挙げられる。
【００４０】
抽出部１−２は、経路条件格納部１−９に格納した経路条件情報から、テストデータ格納部１−８に格納した第１のテストデータと論理的に同値でない経路条件情報を抽出する。抽出部１−２の一例としては、マッチング部１４が挙げられる。
【００４１】
生成部１−３は、抽出した経路条件情報が示す経路条件を充足する第２のテストデータ４を生成する。
【００４２】
このように構成することにより、プログラムの修正前のテスト資産を利用して、プログラムが変更された部分についてテストするための差分テストケース（テストデータ）を生成することができる。その結果、シンボリック実行で得られた全テストケースのうち、その差分テストデータに対応する出力値を用意すればよいので、出力値を生成する工数を節約することができる。よって、プログラムの修正前のテスト資産を利用して、プログラム修正後のテストのコストを削減することができる。
【００４３】
また、抽出部は、経路条件格納部１−９に格納した経路条件情報が第１のテストデータ２と論理的に同値である第１の経路条件情報であるかを判定する。このとき、テストデータ生成装置１は、さらに、分解部１−４、目標論理式取得部１−５、選択部１−６、差分取得部１−７を含む。
【００４４】
分解部１−４は、経路条件格納部１−９に格納された経路条件情報を、論理的に同値である情報、同値でない情報の順に並び替える。それから、分解部１−４は、並び替えた経路条件情報を、１以上の原子論理式を含む論理式である目標論理式に、分解する。分解部１−４の一例としては、分解部４１が挙げられる。
【００４５】
分解格納部１−１０は、分解された目標論理式を経路条件情報毎に関係付けた情報である経路分解情報を格納する。分解格納部１−１０の一例としては、原子論理式テーブルが挙げられる。
【００４６】
目標論理式格納部１−１１は、目標論理式を格納する。目標論理式格納部１−１１の一例としては、目標論理式テーブル５２が挙げられる。
【００４７】
目標論理式取得部１−５は、分解格納部１−１０から経路分解情報を取得する。それから、目標論理式取得部１−５は、取得した経路分解情報が目標論理式格納部１−１１に格納された目標論理式以外の目標論理式である差分の論理式を含む場合、差分の論理式を抽出して目標論理式格納部１−１１に格納する。目標論理式取得部１−５の一例としては、抽出部４２が挙げられる。
【００４８】
選択部１−６は、取得した経路条件情報から、差分の論理式が抽出された経路分解情報に対応する第２の経路条件情報を選択する。選択部１−６の一例としては、選択部４３が挙げられる。
【００４９】
差分取得部１−７は、選択された第２の経路条件情報と第1の経路条件情報との差分を取得する。差分取得部の一例としては、差分取得部４４が挙げられる。
【００５０】
生成部１−３は、差分として取得した経路条件情報から、第２のテストデータ４を生成する。
【００５１】
このように構成することにより、追加すべきテストケース（パスコンディション）のうち、目標論理式格納部１−１１内に含まれる原子論理式から構成されるテストケースを選択しないようにすることができる。これにより、冗長なテストケースを排除することができる。
【００５２】
以下に、本実施形態（実施例１）について詳述する。
（実施例１）
図７は、本実施形態（実施例１）におけるテストデータ生成装置の構成の一例を示す。テストデータ生成装置１１は、制御部１２、記憶部１７を含む。記憶部１７は、テストデータ条件テーブル１８、パスコンディションテーブル１９、抽出パスコンディションテーブル２０を含む。
【００５３】
テストデータ条件テーブル１８には、修正前のプログラムのテストで用いたテストケース毎に、そのテストケースに含まれるテストデータ（条件）が格納される。パスコンディションテーブル１９には、修正したプログラムのソースコードについてシンボリック実行を行うことにより得られた実行パスの組み合わせ、すなわちパスコンディションの組み合わせ（テストケース）が格納される。抽出パスコンディションテーブル２０には、パスコンディションテーブル１９に含まれるパスコンディションのうち、データ生成部１５により抽出されたパスコンディションが格納される。
【００５４】
制御部１２は、取得部１３、マッチング部１４、データ生成部１５、出力部１６を含む。取得部１３は、入力装置（不図示）により、テストデータ３１、パスコンディション情報（テストケース）３４を取得し、それぞれ、テストデータ条件テーブル１８、パスコンディションテーブル１９に格納する。テストデータ３１は、修正前のプログラムのテストで用いたテストケース毎のテストデータである。パスコンディション情報３４は、修正したプログラムのソースコードについてシンボリック実行を行うことにより得られた実行パスの組み合わせ、すなわちパスコンディションの組み合わせ（テストケース）を含む情報である。
【００５５】
マッチング部１４は、パスコンディションテーブル１９から、各テストデータ条件と論理的同値の関係にあるパスコンディションを選択し、その選択したパスコンディションにマッチフラグを付与する。論理的同値の関係については後述する。
【００５６】
データ生成部１５は、パスコンディションテーブル１９から、マッチフラグが立っていないパスコンディションを抽出し、抽出パスコンディションテーブル２０に格納する。データ生成部１５は、制約ソルバを用いて、抽出パスコンディションテーブル２０に格納されたパスコンディションから、テストケース３５を生成する。
【００５７】
出力部１６は、生成されたテストケース３５をディスプレイ、プリンタ等の出力装置に出力する。テストケース３５は、修正後のプログラムのテストについて、新たに追加すべきテストケースである。
【００５８】
図８は、本実施形態（実施例１）における入力データを説明するための図である。テストデータ生成装置１１に対する入力データとして、テストデータ３１と、パスコンディション３４を用いる。テストデータ３１は、修正前のプログラム３２のテストで用いたテストデータであり、ブランチカバレッジを確保している。ここで、修正したプログラム３３は、例えば、図３（Ａ）で示すプログラムである。テストケース１（TC1：a=-1, b=0, c=0, d=null）は、プログラム３２の実行パスNo.01（図３（Ａ））を通過させるためのテストデータである。テストケース２（TC2：a=0, b=5, c=0, d=null）は、プログラム３２の実行パスNo.02（図３（Ａ））を通過させるためのテストデータである。テストケース３（TC3：a=0, b=5, c=1, d=“”）は、プログラム３２の実行パスNo.03（図３（Ａ））を通過させるためのテストデータである。テストケース４（TC4：a=0, b=4, c=0, d=null）は、プログラム３２の実行パスNo.04（図３（Ａ））を通過させるためのテストデータである。
【００５９】
パスコンディション情報３４は、プログラム３２を修正したプログラム３３についてシンボリック実行を行うことにより得られる。ここで、修正したプログラム３３は、例えば、図４（Ａ）で示すプログラムである。パスコンディション情報３４には、パスコンディション１〜１２（PC1〜PC12）で示される１２個のパスコンディション情報が含まれる。パスコンディション情報３４において、PC1〜PC12は、パスコンディションを識別する識別情報である。
【００６０】
図９は、本実施形態（実施例１）におけるテストデータ条件テーブルの一例を示す。テストデータ条件テーブル１８は、取得部１３により、テストデータ３１の各テストケースに含まれるテストデータの条件（論理式）を論理積∧で連結した式が格納される。
【００６１】
テストデータ条件テーブル１８は、データ項目「No.」１８１、「テストデータ条件」１８２を含む。「No.」１８１には、テストデータ条件を識別する情報に対応するNo.が格納される。「テストデータ」１８２には、「No.」１９１に格納されたNo.に対応するテストデータ条件情報が格納される。
【００６２】
図１０は、本実施形態（実施例１）におけるパスコンディションテーブルの一例を示す。パスコンディション情報３４は、取得部１３によりパスコンディションテーブル１９に格納されたパスコンディション集合である。なお、図１０では、パスコンディションに含まれる原子論理式間を連結する記号が、論理積「∧」で示されている。ここで、原子論理式とは、論理式の最小単位（単独の条件）またはその否定である。論理式とは、条件（事前条件または事後条件）を表す式である。論理式の否定とは、論理式にＮＯＴを結合した論理式である。
【００６３】
パスコンディションテーブル１９は、データ項目「No.」１９１、「パスコンディション」１９２を含む。「No.」１９１には、パスコンディションを識別する情報に対応するNo.が格納される。「パスコンディション」１９２には、「No.」１９１に格納されたNo.に対応するパスコンディション情報が格納される。
【００６４】
図１１は、本実施形態（実施例１）におけるマッチング部の処理について説明するための図である。マッチング部１４は、テストデータ条件テーブル１８から、１つのテストケース（例えば、「(a==-1)∧(b==0)∧(c==0)∧(d==null)」）を取り出す（Ｓ１）。
【００６５】
次に、マッチング部１４は、パスコンディションテーブル１９内の１つのパスコンディション（例えば、「(a<0)∧(d==null)」）を取り出す。マッチング部１４は、制約ソルバを用いて、取り出したテストデータ条件と、取り出したパスコンディションとが論理的に同値であるか否かを判定する（Ｓ２）。ここで、論理式Ａと論理式Ｂが論理的に同値であるとは、「（ＡならばＢ）かつ（ＢならばＡ）が成り立つ」ことを表す。したがって、上記の例の場合、「(a==-1)∧(b==0)∧(c==0)∧(d==null)  →   (a<0)∧(d==null)  ∧  (a<0)∧(d==null)  →  (a==-1)∧(b==0)∧(c==0)∧(d==null)」の要件を充足するかが判定される。
【００６６】
テストデータ条件とパスコンディションとが論理的に同値となる要件を充足可能であると判定した場合、マッチング部１４は、パスコンディションテーブル１９内の対応するパスコンディションに、マッチしたことを示すマッチフラグを付与する（Ｓ３）。テストデータ条件とパスコンディションとが論理的に同値となる要件を充足不能であると判定した場合、マッチング部１４は、パスコンディションテーブル１９から、次のパスコンディションを取り出す。
【００６７】
図１２は、図１０のパスコンディションテーブルにデータ項目「マッチフラグ」１９３を追加した一例を示す。図１１で説明したように、マッチング部１４は、テストデータ条件テーブル１８から取り出したテストデータ条件と、パスコンディションテーブル１９から取り出したパスコンディションとが論理的に同値であるか否かを判定する。その結果、論理的に同値となる要件を充足可能であると判定した場合、マッチング部１４は、図１２に示すように、パスコンディションテーブル１９において、対応するパスコンディションに、マッチしたことを示すマッチフラグを付与する。
【００６８】
図１２では、テストケースＴＣ０１と、パスコンディション０１とがマッチしたことにより、No.1のパスコンディションにマッチフラグが付与されている。また、テストケースＴＣ０２，ＴＣ０４と、パスコンディション１０とがマッチしたことにより、No.10のパスコンディションにマッチフラグが付与されている。また、マッチフラグに基づいて、テストケースＴＣ０３とパスコンディション１１とがマッチしたことにより、No.11のパスコンディションにマッチフラグが付与されている。
【００６９】
図１３は、抽出パスコンディションテーブルの1一例を示す。抽出パスコンディションテーブルには、図１２に示すパスコンディションテーブルから、マッチフラグが付与されていないパスコンディションを抽出して得られたパスコンディション情報が格納される。データ生成部１５は、図１２に示すパスコンディションテーブルから、マッチフラグが付与されていないパスコンディションを抽出する。図１２の場合、Ｎｏ．０２〜０９，１２で示すパスコンディションが抽出される。その抽出結果が、図１３である。
【００７０】
図１４は、本実施形態（実施例１）において、生成されるテストデータの一例を示す。データ生成部１５は、制約ソルバを用いて、図１３において抽出されたパスコンディションからテストデータ３５を生成する。テストデータ３５は、修正後のプログラムのテストにおいて、修正前のプログラムのテストで用いたデータの他に、新たに追加されるテストデータである。ここで、パスコンディションに現れない変数については、予め決められたデフォルト値とする。例えば、図１３の１つ目のパスコンディションには「ｂ」と「ｃ」が現れないので、予め決められたデフォルト値０が設定されることとなる。
【００７１】
図１５−図１７は、本実施形態（実施例１）におけるテストケース選択フローの一例を示す。ユーザは、修正前プログラムのテストで用いたテストデータ３１、修正後のプログラムのソースコードに対して行ったシンボリック実行により得られたパスコンディション情報３４を、入力装置を用いて、テストデータ生成装置１１に入力する。
【００７２】
取得部１３は、テストデータ３１から１レコードのテストケースのテストデータを取り出す（Ｓ１１，Ｓ１２）。取得部１３は、テストデータの条件（論理式）を論理積∧で連結した論理式（テストデータ条件式）に変換し（Ｓ１３）、テストデータ条件テーブル１８に格納する（Ｓ１４）。取得部１３は、入力されたテストデータ３１に含まれるテストケースのテストデータについてＳ１１〜Ｓ１４の処理を繰り返す。
【００７３】
取得部１３は、入力されたパスコンディション情報をパスコンディションテーブル１９に格納する（Ｓ１５）。
【００７４】
次に、マッチング部１４は、テストデータ条件テーブル１８から１レコードのテストデータ条件式を取り出す（Ｓ１６で「Ｙｅｓ」，Ｓ１７）。また、マッチング部１４は、パスコンディションテーブル１９から１レコードのパスコンディションを取り出す（Ｓ１８で「Ｙｅｓ」、Ｓ１９）。
【００７５】
マッチング部１４は、取り出したテストデータ条件式と、取り出したパスコンディションから、図１１で説明したように、両者が論理的に同値であるかを判定する判定式を作成する（Ｓ２０）。
【００７６】
マッチング部１４は、制約ソルバを用いて、Ｓ２０で作成した判定式から、そのテストデータ条件式とパスコンディションが論理的に同値であるかを判定する（Ｓ２１）。そのテストデータ条件式とパスコンディションが論理的に同値でない場合（Ｓ２１で「Ｎｏ」）、マッチング部１４は、パスコンディションテーブル１９から次のパスコンディションのレコードを取り出し（Ｓ１８）、Ｓ１９−Ｓ２１の処理を行う。パスコンディションテーブル１９に、未処理のパスコンディションがない場合（Ｓ１８で「Ｎｏ」）、マッチング部１４は、テストデータ条件テーブル１８から次のテストデータ条件式のレコードを取り出し（Ｓ１６で「Ｙｅｓ」，Ｓ１７）、Ｓ１８以降の処理を行う。
【００７７】
そのテストデータ条件式とパスコンディションが論理的に同値である場合（Ｓ２１で「Ｙｅｓ」）、マッチング部１４は、図１２で説明したように、パスコンディションテーブル１９において、対応するパスコンディションにマッチフラグを付与する（Ｓ２２）。その後、マッチング部１４は、テストデータ条件テーブル１８から次のテストデータ条件式のレコードを取り出し（Ｓ１６で「Ｙｅｓ」，Ｓ１７）、Ｓ１８以降の処理を行う。
【００７８】
テストデータ条件テーブル１８に含まれる全テストデータ条件式について、Ｓ１７−Ｓ２２の処理が終了した場合（Ｓ１６で「Ｎｏ」）、Ｓ２３の処理へ進む。
【００７９】
データ生成部１５は、パスコンディションテーブル１９から１つのパスコンディションのレコードを選択する（Ｓ２３で「Ｙｅｓ」、Ｓ２４）。選択したパスコンディションにマッチフラグが付与されている場合（Ｓ２５で「Ｎｏ」）、データ生成部１５は、パスコンディションテーブル１９から次のパスコンディションのレコードを選択する（Ｓ２３で「Ｙｅｓ」、Ｓ２４）。選択したパスコンディションにマッチフラグが付与されていない場合（Ｓ２５で「Ｙｅｓ」）、データ生成部１５は、そのパスコンディションを抽出し、抽出パスコンディションテーブル２０へ格納する（Ｓ２６）。
【００８０】
テストデータ条件テーブル１８に含まれる全テストデータ条件式について、Ｓ２４−Ｓ２６の処理が終了した場合（Ｓ２３で「Ｎｏ」）、データ生成部１５は、次の処理を行う。すなわち、データ生成部１５は、抽出パスコンディションテーブル２０に格納されたパスコンディションを、制約ソルバに入力する（Ｓ２７）。
【００８１】
すると、データ生成部１５は、制約ソルバからパスコンディションの充足値（テストデータ３５）を取得する（Ｓ２８）。ここで、得られたテストデータ３４は、修正後のプログラムのテストデータであって、修正前のプログラムのテストケースで用いたテストデータに対して追加すべきテストデータである。
【００８２】
本実施形態（実施例１）によれば、修正／変更後のプログラムのソースコードについてのシンボリック実行から得られるパスコンディションと修正前に用いたテストデータとのマッチングを行う。これにより、テスト資産内の再利用可能なテストケースを特定することができる。すなわち、本実施形態（実施例１）によれば、修正／変更後の差分に対応するテストケース（テストデータ）が抽出され、再テストのコスト削減の効果が得られる。
【００８３】
（実施例２）
実施例１では、修正後のプログラムのソースコードについてシンボリック実行を行って得られたパスコンディションのうち、修正前のプログラムのテストデータでは対応できない部分を補完できるテストデータを追加した。
【００８４】
しかしながら、シンボリック実行は、実行可能な全てのパスコンディションを生成するため、パスコンディションの組み合わせが膨大になる。その結果、パスカバレッジに基づくテストケースの数も膨大になる。
【００８５】
この場合、それらのテストケースには、コードカバレッジの観点から、冗長なテストケースを多く含む可能性がある。
そこで、実施例２では、実施例１において追加すべきテストケースとして判定されたテストケースのうち、コードカバレッジを確保しながら、冗長なテストケースを排除した、テストケースを選択することについて説明する。
【００８６】
本実施形態（実施例２）では、実施例１でシンボリック実行により生成されるパスコンディション（テストケース）を原子論理式に分解して、パスコンディションに含まれる全種類の原子論理式を実行できるようにパスコンディション（テストケース）を選択する。このとき、テストケースの選択に際して、既に選択したいずれのパスコンディションにも含まれていない原子論理式を含むパスコンディションを選択する。この選択したパスコンディションと、実施例１でマッチフラグが付与されていないパスコンディションとの差分のパスコンディションを抽出する。制約ソルバを用いて、この差分のパスコンディションから追加すべきテストデータが得られる。
【００８７】
図１８は、本実施形態（実施例２）におけるテストデータ生成装置の構成の一例を示す。図１８のテストデータ生成装置１１は、図７のテストデータ生成装置１１に、テストケース選択部４０、原子論理式テーブル５１、目標論理式テーブル５２、選択パスコンディションテーブル５３を追加したものである。
【００８８】
図１８のテストデータ生成装置１１は、制御部１２、記憶部１７を含む。記憶部１７は、テーブルデータ条件テーブル１８、パスコンディションテーブル１９、抽出パスコンディションテーブル２０、原子論理式テーブル５１、目標論理式テーブル５２、選択パスコンディションテーブル５３を含む。
【００８９】
テーブルデータ条件テーブル１８、パスコンディションテーブル１９、抽出パスコンディションテーブル２０は、実施例１で説明しているので、その説明を省略する。
【００９０】
原子論理式テーブル５１には、パスコンディション毎に、パスコンディションに含まれる原子論理式が格納される。目標論理式テーブル５２には、パスコンディションを構成する原子論理式が種類毎に格納される。選択パスコンディションテーブル５３には、パスコンディションテーブル１９に含まれるパスコンディションのうち、選択部４３により選択されたパスコンディションが格納される。
【００９１】
制御部１２は、取得部１３、マッチング部１４、テストケース選択部４０、データ生成部１５、出力部１６を含む。取得部１３は、入力装置（不図示）により、テストデータ３１、パスコンディション情報（テストケース）３４を取得し、それぞれ、テストデータ条件テーブル１８、パスコンディションテーブル１９に格納する。テストデータ３１は、修正前のプログラムのテストで用いたテストケース毎のテストデータである。パスコンディション情報３４は、修正したプログラムのソースコードについてシンボリック実行を行うことにより得られた実行パスの組み合わせ、すなわちパスコンディションの組み合わせ（テストケース）を含む情報である。
【００９２】
マッチング部１４は、パスコンディションテーブル１９から、各テストデータ条件と論理的同値の関係にあるパスコンディションを選択し、その選択したパスコンディションにマッチフラグを付与する。
【００９３】
テストケース選択部４０は、分解部４１、抽出部４２、選択部４３、差分取得部４４を含む。分解部４１は、パスコンディションテーブル１９において、マッチフラグが付与されたパスコンディションがテーブルの先頭側になるようにソートする。分解部４１は、ソート処理が終わったパスコンディションテーブル１９に格納した各パスコンディションを原子論理式に分解する。分解部４１は、その原子論理式を、パスコンディション毎に、原子論理式テーブル５１に格納する。
【００９４】
抽出部４２は、原子論理式テーブル５１において、着目しているパスコンディションの原子論理式から、目標論理式テーブル５２にそれまでに保持した原子論理式以外の原子論理式を抽出する。抽出部４２は、その抽出した原子論理式を目標論理式テーブル５２に格納する。また、抽出部４２は、その抽出された原子論理式を含んでいたパスコンディションを特定するために、原子論理式テーブル５１において、そのパスコンディションに選択フラグを立てる。
【００９５】
選択部４３は、原子論理式テーブル５１から、選択フラグの立っているパスコンディションを検出する。選択部４３は、パスコンディションテーブル１９から、その検出したパスコンディションに対応するパスコンディションを選択し、選択パスコンディションテーブル５３に格納する。
【００９６】
差分取得部４４は、パスコンディションテーブル１９において、マッチフラグが付与されたパスコンディションと、選択パスコンディションテーブル５３に格納したパスコンディションとの差分を取得し、抽出パスコンディションテーブル２０に格納する。
【００９７】
データ生成部１５は、データ生成部１５は、制約ソルバを用いて、抽出パスコンディションテーブル２０に格納されたパスコンディションから、テストケース３５を生成する。
【００９８】
出力部１６は、生成されたテストケース３５をディスプレイ、プリンタ等の出力装置に出力する。テストケース３５は、修正後のプログラムのテストについて、新たに追加すべきテストケースである。
【００９９】
分解部４１、抽出部４２、選択部４３、差分取得部４４の機能について、以下に詳述する。
図１９は、図１２のパスコンディションテーブル１９において、マッチフラグが付与されたパスコンディションがテーブルの先頭側になるように並べ替えた様子を示す。上述したように、分解部４１は、マッチフラグが付与されたパスコンディションがパスコンディションテーブル１９の先頭側にくるようにソートする。
【０１００】
図２０は、本実施形態（実施例２）におけるテストケース選択部の処理内容を説明するための図である。テストケース選択部４０は、マッチフラグの有無によって、ソートされたパスコンディション（図１９）からコードカバレッジを確保したパスコンディションを選択する。
【０１０１】
図２１は、本実施形態（実施例２）のテストケース選択処理を説明するための図である。テストケース選択部４０は、各テストケースが有するパスコンディションを解析することで、テストケースを実際に実行することなく、全テストケースから、あるカバレッジを満たすテストケースを探す。すなわち、テストケース選択部４０は、パスコンディションに含まれる原子論理式をプログラム上の条件式として、各パスコンディションが全種類の原子論理式（もしくはその組み合わせ）のうちどれだけの原子論理式を充足したかをパスコンディション上で解析する。コードカバレッジは、プログラム中の条件式内の原子条件と密接な関係がある。ここで、原子条件とは、原子論理式に対応するソースコード上の条件である。
【０１０２】
図２１の表は、マッチフラグの有無によってソートされたパスコンディション（テストケース）を、原子論理式に分解してテーブル化したものである。図２１の表の列方向には、パスコンディション上の原子論理式が並べられている。No.01のパスコンディションが「(a<0)∧(d==null)」であると、図２１の表では、「a<0」、「d==null」に「〇」が付されている。
【０１０３】
まず、No.01のパスコンディションを選択する。No.01のパスコンディションは、上述の通り、原子論理式「a<0」、「d==null」を含む。
【０１０４】
次にNo.10のパスコンディションに着目する。No.10のパスコンディションは、No.01のパスコンディションに含まれない原子論理式「a>=0」、「b<10」を含むので、No.10のパスコンディションを選択する。
【０１０５】
次にNo.11のパスコンディションに着目する。No.11のパスコンディションは、No.01及びNo.10のパスコンディションのいずれにも含まれない原子論理式「d!=null」「d.length<5」を含むので、No.11のパスコンディションを選択する。
【０１０６】
次にNo.02のパスコンディションに着目する。No.02のパスコンディションに含まれる原子論理式はいずれも、No.01,No.10,No11のパスコンディションのいずれかに含まれるものなので、No.02のパスコンディションについては選択しない。
【０１０７】
次にNo.03のパスコンディションに着目する。No.03のパスコンディションは、No.01,No.10,No11, No.02のパスコンディションのいずれにも含まれない原子論理式「d.length>=5」を含むので、No.03のパスコンディションを選択する。
【０１０８】
No.04のパスコンディション以降についても同様に、着目しているパスコンディションがそれまでに選択したパスコンディションに含まれる原子論理式と異なる原子論理式を含む場合に、その着目しているパスコンディションを選択する。そうすると、図２１の表の場合には、１２個のテストケースから６個のNo.01, No.10, No.11, No.03, No.04, No.07のパスコンディションが選択される。これにより、No.01, No.10, No.11, No.03, No.04, No.07のパスコンディションを用いれば、全パスコンディションの原子論理式を全て充足することができるテストを実行することができる。
【０１０９】
図２２は、本実施形態（実施例２）における原子論理式テーブルの一例を示す。原子論理式テーブル５１は、データ項目「No.」５１１、「原子論理式」５１２を含む。「No.」５１には、パスコンディションの識別情報に対応するNo.が格納される。「原子論理式」５１２には、「No.」５１に格納されたNo.に対応するパスコンディション情報に含まれる原子論理式が格納される。
【０１１０】
ここで、原子論理式テーブル５１に関する分解部４１の動作について説明する。分解部４１は、マッチフラグの有無によって、ソートされたパスコンディションテーブル１９（図１９）からパスコンディション情報を読み出し、読み出したパスコンディション情報を原子論理式に分解する。分解部４１は、その原子論理式を、パスコンディション毎に、原子論理式テーブル５１に格納する。
【０１１１】
図２３は、図２２の原子論理式テーブルにデータ項目「選択」５１３を追加した一例を示す。図２４は、本実施形態（実施例２）における目標論理式テーブルの一例を示す。目標論理式テーブル５２には、原子論理式テーブル５１において、着目しているパスコンディションに含まれる原子論理式のうち、それまでに保持した原子論理式以外の原子論理式が保持される。これにより、目標論理式テーブル５２には、最終的に、原子論理式テーブル５１に含まれる全ての種類の原子論理式が格納される。すなわち、目標論理式テーブル５２には、最終的に、全パスコンディションに含まれる原子論理式が種類毎に格納される。
【０１１２】
ここで、目標論理式テーブル５２に関する抽出部４２の動作について説明する。抽出部４２は、原子論理式テーブル５１において、着目しているパスコンディションの原子論理式から、目標論理式テーブル５２に保持されていない原子論理式を抽出する。抽出部４２は、その抽出した原子論理式を目標論理式テーブル５２に格納する。また、抽出部４２は、原子論理式テーブル５１において、その抽出された原子論理式を含んでいたパスコンディションに対応する「選択」５１３にフラグ（選択フラグ）を立てる。
【０１１３】
図２５は、本実施形態（実施例２）における選択パスコンディションテーブルの一例を示す。選択部４３は、原子論理式テーブル５１から、フラグの立っているパスコンディションを検出する。選択部４３は、パスコンディションテーブル１９から、その検出したパスコンディションに対応するパスコンディションを選択し、選択パスコンディションテーブル５３に格納する。
【０１１４】
図２６は、本実施形態（実施例２）における選択パスコンディションテーブルに格納されたパスコンディションと、マッチフラグが付与されたパスコンディションとの差分について説明するための図である。選択パスコンディションテーブル５３に格納されたパスコンディションは、No.＝01, 10, 11, 03, 04, 07である。マッチフラグが付与されたパスコンディションは、No.＝01, 10, 11である。差分取得部４４は、選択パスコンディションテーブル５３に格納されたパスコンディションと、マッチフラグが付与されたパスコンディションとの差分No.＝03, 04, 07のパスコンディション（差分パスコンディション）を取得する。差分取得部４４は、その差分パスコンディションを、抽出パスコンディションテーブル２０に格納する。
【０１１５】
図２７は、本実施形態（実施例２）におけるデータ生成部１５の処理を説明するための図である。データ生成部１５は、制約ソルバを用いて、抽出パスコンディションテーブル２０に格納された差分パスコンディションからテストデータ３５を生成する。
【０１１６】
図２８−図３０は、本実施形態（実施例２）におけるテストデータ生成フローの一例を示す。図１５、図１６の処理後に、図２８−図３０の処理が行われる。
【０１１７】
テストケース選択部４０（分解部４１）は、マッチフラグが付与されたパスコンディションがパスコンディションテーブル１９の先頭側にくるようにソートする（Ｓ３１）。テストケース選択部４０は、テストケース選択処理を行う（Ｓ３２）。Ｓ３２の処理については、図３１−図３３を用いて詳述する。これにより、選択パスコンディションテーブル５３（図２５）に、ブランチカバレッジが確保されたパスコンディション（テストケース）が格納される。
【０１１８】
差分取得部４４は、選択パスコンディションテーブル５３から１レコードのパスコンディション（「対象パスコンディションＴ１」と呼ぶ）を取り出す（Ｓ３３で「Ｙｅｓ」、Ｓ３４）。
【０１１９】
差分取得部４４は、パスコンディションテーブル１９から１レコードのパスコンディション（「対象パスコンディションＴ２」と呼ぶ）を取り出す（Ｓ３５で「Ｙｅｓ」、Ｓ３６）。
【０１２０】
差分取得部４４は、対象パスコンディションＴ１と対象パスコンディションＴ２が同一の式で、かつ対象パスコンディションＴ２のマッチフラグが立っていないかを判定する（Ｓ３７）。
【０１２１】
対象パスコンディションＴ１と対象パスコンディションＴ２が同一の式でないか、または対象パスコンディションＴ２のマッチフラグが立っている場合（Ｓ３７で「Ｎｏ」）、差分取得部４４は、次の処理を行う。すなわち、差分取得部４４は、パスコンディションテーブル１９から次のパスコンディションを取り出し、Ｓ３６以降の処理を行う。パスコンディションテーブル１９に未処理のパスコンディションがない場合、Ｓ３３の処理へ戻る。
【０１２２】
対象パスコンディションＴ１と対象パスコンディションＴ２が同一の式で、かつ対象パスコンディションＴ２のマッチフラグが立っていない場合、差分取得部４４は、パスコンディションテーブル内の対象パスコンディションＴ２に差分フラグを立てる（Ｓ３８）。その後、Ｓ３５の処理へ戻る。
【０１２３】
選択パスコンディションテーブル５３に格納された全パスコンディションについてＳ３４〜Ｓ３８の処理が完了した場合（Ｓ３３で「Ｎｏ」）、Ｓ３９の処理へ進む。
【０１２４】
データ生成部１５は、パスコンディションテーブル１９から１レコードのパスコンディションを選択する（Ｓ３９で「Ｙｅｓ」、Ｓ４０）。選択したパスコンディションに差分フラグが付与されていない場合（Ｓ４１で「Ｎｏ」）、データ生成部１５は、パスコンディションテーブル１９から次のパスコンディションを選択する（Ｓ３９で「Ｙｅｓ」、Ｓ４０）。選択したパスコンディションに差分フラグが付与されている場合（Ｓ４１で「Ｙｅｓ」）、データ生成部１５は、そのパスコンディションを抽出し、抽出パスコンディションテーブル２０へ格納する（Ｓ４２）。
【０１２５】
パスコンディションテーブル１９に含まれる全パスコンディションについて、Ｓ４０−Ｓ４２の処理が終了した場合（Ｓ３９で「Ｎｏ」）、データ生成部１５は、次の処理を行う。すなわち、データ生成部１５は、抽出パスコンディションテーブル２０に格納されたパスコンディションを、制約ソルバに入力する（Ｓ４３）。
【０１２６】
すると、データ生成部１５は、制約ソルバからパスコンディションの充足値（テストデータ）を取得する（Ｓ２８）。ここで、得られたテストデータは、修正後のプログラムのテストデータであって、修正前のプログラムのテストケースで用いたテストデータに対して追加すべきテストデータである。
【０１２７】
図３１−図３３は、本実施形態（実施例２）におけるテストケース選択フローの一例を示す。図３１−図３３は、図２８のＳ３２の詳細なフローを示す。
【０１２８】
分解部４１は、パスコンディションテーブル１９からレコードを読み出す（Ｓ５１で「Ｙｅｓ」、Ｓ５２）。分解部４１は、読み出したレコードのパスコンディションに原子論理式が存在するか否かを判定する（Ｓ５３）。読み出したレコードのパスコンディションに原子論理式が存在する場合（Ｓ５３で「Ｙｅｓ」）、分解部４１はそのレコードのパスコンディションに含まれる原子論理式を取り出し、原子論理式テーブル５１に格納する（Ｓ５４）。そのレコードのパスコンディションから全ての原子論理式を取り出し終わるまで、分解部４１はＳ５４の処理を繰り返す。
【０１２９】
読み出したレコードのパスコンディションに原子論理式が存在しない場合（Ｓ５３で「Ｎｏ」）、パスコンディションテーブル１９に未処理のレコードが存在すれば（Ｓ５１で「Ｙｅｓ」）、分解部４１は、次の処理を行う。すなわち、分解部４１は、パスコンディションテーブル１９から次のレコードを読み出し、Ｓ５３〜Ｓ５４の処理を行う。パスコンディションテーブル１９に未処理のレコードが存在しなければ（Ｓ５１で「Ｎｏ」）、図３０のＳ５５の処理へ処理が遷移する。
【０１３０】
次に、抽出部４２は、原子論理式テーブル５１からレコードを読み出す（Ｓ５５で「Ｙｅｓ」、Ｓ５６）。抽出部４２は、Ｓ５６で読み出したレコードに含まれる原子論理式のうち、目標論理式テーブル５２に存在しない原子論理式が存在するか否かを判定する（Ｓ５７）。
【０１３１】
Ｓ５６で読み出したレコードに含まれる原子論理式のうち、目標論理式テーブル５２に存在しない原子論理式（差分）が存在する場合、抽出部４２は、その差分の原子論理式を目標論理式テーブル５２に追加する（Ｓ５８）。このとき、抽出部４２は、原子論理式テーブル５１において、読み出したレコードのデータ項目「選択」５１３にフラグを立てる。
【０１３２】
一方、Ｓ５７において、読み出したレコードに含まれる全ての原子論理式が目標論理式テーブル５２に存在する場合（Ｓ５７で「Ｎｏ」）、または、Ｓ５９の処理が終了した場合、処理がＳ５５へ戻る。原子論理式テーブル５１に未処理のレコードが存在する間（Ｓ５５で「Ｙｅｓ」）、抽出部４２は、原子論理式テーブル５１から次のレコードを読み出し、Ｓ５６〜Ｓ５９の処理を行う。原子論理式テーブル５１に未処理のレコードが存在しない間（Ｓ５５で「Ｎｏ」）、図３２のＳ６０の処理へ処理が遷移する。
【０１３３】
次に、選択部４３は、原子論理式テーブル５１からレコードを読み出す（Ｓ６０で「Ｙｅｓ」、Ｓ６１）。選択部４３は、その読み出したレコードの選択フラグが立っているか否かを判定する（Ｓ６２）。
【０１３４】
Ｓ１３において、その読み出したレコードの選択フラグが立っていると判定した場合（Ｓ６２で「Ｙｅｓ」）、選択部４３は、パスコンディションテーブル１９から、選択フラグの立っているレコードと同じNo.のパスコンディションを取得する。選択部４３は、その取得したパスコンディションを選択パスコンディションテーブル５３に追加する（Ｓ６３）。
【０１３５】
Ｓ６２において、対象レコードの選択フラグが立っていないと判定した場合（Ｓ６２で「Ｎｏ」）、または、Ｓ６３の処理が終了した場合、処理がＳ６０へ戻る。原子論理式テーブル５１にＳ６１〜Ｓ６３の処理について未処理のレコードが存在する間（Ｓ６０で「Ｙｅｓ」）、抽出部４２は、原子論理式テーブル５１から次のレコードを読み出し（Ｓ６１）、Ｓ６２〜Ｓ６３の処理を行う。原子論理式テーブル５１の全レコードについて処理が完了すれば（Ｓ６０で「Ｎｏ」）、本フローは終了する。
【０１３６】
本実施形態（実施例２）によれば、実施例１において追加すべきテストケース（パスコンディション）のうち、目標論理式テーブル内に含まれる原子論理式から構成されるテストケースを選択しないようにすることができる。これにより、冗長なテストケースを排除することができる。そのため、目標論理式テーブル内に含まれる原子論理式から構成されるテストケースが多いほど、テストケースを１つずつ実行しながらカバレッジ測定する方法よりもテストケース数を削減することができる。つまり、実施例１において追加すべきテストケースに着目すれば、追加すべきテストケース数が多いほど、テストケース数の削減率が向上する。その結果、プログラムの修正前のテスト資産を利用して、プログラム修正後のテストのコストを削減することができる。
【０１３７】
また、本実施形態（実施例２）によれば、修正前のテストケースに対応するパスコンディションの選択優先順位を高くする。これにより、修正後プログラムのあるカバレッジに即したテストケース選択において、既存のテストケースを最大限に再利用しつつカバレッジも保証するための追加すべきテストケースが得られる。
【０１３８】
図３４は、本実施形態を適用したコンピュータのハードウェア環境の構成ブロック図である。コンピュータ６０は、本実施形態（実施例１または２）の処理（図１５〜図１７、図２８〜図３３）を行うプログラムを読み込むことにより、テストデータ生成装置１１として機能する。
【０１３９】
コンピュータ６０は、出力Ｉ／Ｆ６１、ＣＰＵ６２、ＲＯＭ６３、通信Ｉ／Ｆ６４、入力Ｉ／Ｆ６５、ＲＡＭ６６、記憶装置６７、読み取り装置６８、バス６９を含む。コンピュータ６０は、出力機器７１、及び入力機器７２と接続可能である。
【０１４０】
ここで、ＣＰＵは、中央演算装置を示す。ＲＯＭは、リードオンリメモリを示す。ＲＡＭは、ランダムアクセスメモリを示す。Ｉ／Ｆは、インターフェースを示す。バス６９には、出力Ｉ／Ｆ６１、ＣＰＵ６２、ＲＯＭ６３、通信Ｉ／Ｆ６４、入力Ｉ／Ｆ６５、ＲＡＭ６６、記憶装置６７、読み取り装置６８が接続されている。読み取り装置６８は、可搬型記録媒体を読み出す装置である。出力機器７１は、出力Ｉ／Ｆ６１に接続されている。入力機器７２は、入力Ｉ／Ｆ６５に接続されている。
【０１４１】
記憶装置６７としては、ハードディスクドライブ、フラッシュメモリ装置、磁気ディスク装置など様々な形式の記憶装置を使用することができる。
記憶装置６７またはＲＯＭ６３には、例えば、本実施形態で説明した処理を実現するプログラムが格納されている。または、記憶装置６７またはＲＯＭ６３には、テストデータ条件テーブル１８、パスコンディションテーブル１９、抽出パスコンディションテーブル２０、原子論理式テーブル５１、目標論理式テーブル５２、選択パスコンディションテーブル５３が格納されている。
【０１４２】
ＣＰＵ６２は、記憶装置６７等に格納した本実施形態（実施例１または２）で説明した処理を実現するプログラムを読み出し、当該プログラムを実行する。具体的には、ＣＰＵ６２は、当該プログラムを実行することにより、制御部１２（取得部１３、マッチング部１４、テストデータ選択部４０、データ生成部１５、出力部１６）として機能する。
【０１４３】
本実施形態で説明した処理を実現するプログラムは、プログラム提供者側から通信ネットワーク７０、および通信Ｉ／Ｆ６４を介して、例えば記憶装置６７に格納してもよい。また、本実施形態で説明した処理を実現するプログラムは、市販され、流通している可搬型記憶媒体に格納されていてもよい。この場合、この可搬型記憶媒体は読み取り装置６８にセットされて、ＣＰＵ６２によってそのプログラムが読み出されて、実行されてもよい。可搬型記憶媒体としてはＣＤ−ＲＯＭ、フレキシブルディスク、光ディスク、光磁気ディスク、ＩＣ（integrated circuit）カード、ＵＳＢ（Universal Serial Bus）メモリ装置など様々な形式の記憶媒体を使用することができる。このような記憶媒体に格納されたプログラムが読み取り装置６８によって読み取られる。
【０１４４】
また、入力機器７２には、キーボード、マウス、電子カメラ、ウェブカメラ、マイク、スキャナ、センサ、タブレット、タッチパネルなどを用いることが可能である。また、出力機器７１には、ディスプレイ、プリンタ、スピーカなどを用いることが可能である。また、ネットワーク７０は、インターネット、ＬＡＮ、ＷＡＮ、専用線、有線、無線等の通信網であってよい。
【０１４５】
なお、本実施形態は、以上に述べた実施の形態に限定されるものではなく、本実施形態の要旨を逸脱しない範囲内で種々の構成または実施形態を取ることができる。
【符号の説明】
【０１４６】
１      テストデータ生成装置
１−１  入力情報取得部
１−２  抽出部
１−３  生成部
１−４  分解部
１−５  目標論理式取得部
１−６  選択部
１−７  差分取得部
１−８  テストデータ格納部
１−９  経路条件格納部
２      第１のテストデータ
３      経路条件情報
４      第２のテストデータ
１１    テストデータ生成装置
１２    制御部
１３    取得部
１４    マッチング部
１５    データ生成部
１６    出力部
１７    記憶部
１８    テストデータ条件テーブル
１９    パスコンディションテーブル
２０    抽出パスコンディションテーブル
４０    テストケース選択部
４１    分解部
４２    抽出部
４３    選択部
４４    差分取得部
５１    原子論理式テーブル
５２    目標論理式テーブル
５３    選択パスコンディションテーブル
【図１】
2014021686.tif 000003
【図２】
2014021686.tif 000004
【図３】
2014021686.tif 000005
【図４】
2014021686.tif 000006
【図５】
2014021686.tif 000007
【図６】
2014021686.tif 000008
【図７】
2014021686.tif 000009
【図８】
2014021686.tif 000010
【図９】
2014021686.tif 000011
【図１０】
2014021686.tif 000012
【図１１】
2014021686.tif 000013
【図１２】
2014021686.tif 000014
【図１３】
2014021686.tif 000015
【図１４】
2014021686.tif 000016
【図１５】
2014021686.tif 000017
【図１６】
2014021686.tif 000018
【図１７】
2014021686.tif 000019
【図１８】
2014021686.tif 000020
【図１９】
2014021686.tif 000021
【図２０】
2014021686.tif 000022
【図２１】
2014021686.tif 000023
【図２２】
2014021686.tif 000024
【図２３】
2014021686.tif 000025
【図２４】
2014021686.tif 000026
【図２５】
2014021686.tif 000027
【図２６】
2014021686.tif 000028
【図２７】
2014021686.tif 000029
【図２８】
2014021686.tif 000030
【図２９】
2014021686.tif 000031
【図３０】
2014021686.tif 000032
【図３１】
2014021686.tif 000033
【図３２】
2014021686.tif 000034
【図３３】
2014021686.tif 000035
【図３４】
2014021686.tif 000036