(57)【要約】【課題】シンボリック実行によるプログラムのテストケースの生成において、シンボリック実行の効率化を実現する。【解決手段】同一要素インデックス情報生成部１８は、同一要素判定部２０の判定結果に基づいて、予め定められた判定基準に基づいて同一要素毎に、インデックス値をまとめた同一要素インデックス情報３０を生成する。インデックス等価判定部２４、は、同一要素インデックス情報３０を参照し、パス条件を生成した要素と同一要素に対応する未選択のインデックス値を選択する。インデックス等価判定部２４は、インデックス等価条件３２を生成する。インデックス等価判定部２４は、選択したインデックス値がインデックス等価条件３２を充足可能か判定し、充足可能である場合は、インデックス選択情報２８において選択済とすることにより探索範囲から除外する。【選択図】図１
2015228085.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、
配列を構成する複数の要素の各々の位置を表すシンボル変数であるインデックス値で、除外されていない未選択のインデックス値を選択対象として、該選択対象からインデックス値を選択し、
対象プログラムをシンボリック実行することにより、選択したインデックス値に対応する要素が通過するパスを表すパス条件を生成し、生成したパス条件及び該生成したパス条件が表すパスを通過するテストデータをテストケースとして出力し、
前記選択対象に含まれるインデックス値であり、パス条件を生成した要素と同一の要素に対応するインデックス値が、生成した該パス条件からインデックス値に由来する制約を除外したインデックス等価条件を充足可能か判定し、充足可能なインデックス値を前記選択対象から除外する、
ことを含む処理を実行させるテストケース生成プログラム。
【請求項２】
コンピュータに、
前記対象プログラム中の命令がインデックス値をシンボル変数とした配列の要素へのアクセス命令か否かを検出し、
同一であると判定した要素毎に、インデックス値をまとめた同一要素インデックス情報を生成し、
生成した前記同一要素インデックス情報に基づき、パス条件を生成した要素と同一の要素に対応する前記選択対象に含まれるインデックス値を検出する
ことを含む処理を実行させる請求項１に記載のテストケース生成プログラム。
【請求項３】
コンピュータに、
前記アクセス命令を検出した場合に、予め定められた判定基準に基づいて同一であると判定し、
判定結果に基づいて、同一であると判定した要素毎に、インデックス値をまとめた同一要素インデックス情報を生成する、
ことを含む処理を実行させる請求項２に記載のテストケース生成プログラム。
【請求項４】
コンピュータに、
前記インデックス等価条件を、生成したパス条件からインデックス値に由来する制約を除くことにより生成する、
ことを含む処理を実行させる請求項１から請求項３のいずれか１項に記載のテストケース生成プログラム。
【請求項５】
配列を構成する複数の要素の各々の位置を表すシンボル変数であるインデックス値で、除外されていない未選択のインデックス値を選択対象として、該選択対象からインデックス値を選択する選択部と、
対象プログラムをシンボリック実行することにより、前記選択部が選択したインデックス値に対応する要素が通過するパスを表すパス条件を生成し、生成したパス条件及び該生成したパス条件が表すパスを通過するテストデータをテストケースとして出力する実行部と、
前記選択対象に含まれるインデックス値であり、前記実行部でパス条件を生成した要素と同一の要素に対応するインデックス値が、生成した該パス条件からインデックス値に由来する制約を除外したインデックス等価条件を充足可能か判定し、充足可能なインデックス値を前記選択対象から除外する判定部と、
を備えた、テストケース生成装置。
【請求項６】
前記実行部で実行する命令がインデックス値をシンボル変数とした配列の要素へのアクセス命令か否かを検出する検出部と、
前記検出部が前記アクセス命令であると検出した場合に、予め定められた判定基準に基づいて同一であると判定した要素毎に、インデックス値をまとめた同一要素インデックス情報を生成する生成部と、
を備え、前記判定部は、前記同一要素インデックス情報に基づき、前記実行部によりパス条件を生成した要素と同一の要素に対応する前記選択対象に含まれるインデックス値を検出する、
請求項５に記載のテストケース生成装置。
【請求項７】
コンピュータに、
配列を構成する複数の要素の各々の位置を表すシンボル変数であるインデックス値で、除外されていない未選択のインデックス値を選択対象として、該選択対象からインデックス値を選択し、
対象プログラムをシンボリック実行することにより、選択したインデックス値に対応する要素が通過するパスを表すパス条件を生成し、生成したパス条件及び該生成したパス条件が表すパスを通過するテストデータをテストケースとして出力し、
前記選択対象に含まれるインデックス値であり、パス条件を生成した要素と同一の要素に対応するインデックス値が、生成した該パス条件からインデックス値に由来する制約を除外したインデックス等価条件を充足可能か判定し、充足可能なインデックス値を前記選択対象から除外する、
ことを含む処理を実行させるテストケース生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、テストケース生成プログラム、テストケース生成装置、及びテストケース生成方法に関する。
【背景技術】
【０００２】
従来から、コンピュータのプログラムを実行し、正しく動作するかどうか確認する作業が行われている。
【０００３】
プログラムのテストを実行するためには、入力データ(テストデータ)及び期待結果等を含むテストケースが必要となる。テストで実行する一連のテストケースの集合をここではテストケースセットと呼ぶ。テストでは、確認すべき観点を全て網羅するようにテストケースセットを準備する必要がある。
【０００４】
ここでは、テストの中でも、特にプログラムのホワイトボックステストに注目する。ホワイトボックステストでは、コードカバレッジの指標に従って、プログラム中の命令や分岐、あるいは実行パスを網羅するようにテストケースを準備してテストを実行する。
【０００５】
テストケースの準備、特に入力データの作成は、多くの場合は人手でなされており、大きな労力を要している。この労力を解決する方法として、近年注目されているのが、シンボリック実行（Symbolic execution）によるテストデータ生成技術である。
【０００６】
シンボリック実行を効率化する技術として、例えば、特許文献１及び特許文献２に記載された技術が知られている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２０１１−１９１９８５号公報
【特許文献２】特開２０１３−１４３０６７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
シンボリック実行では、パス条件を生成するために探索及び実行するパスの範囲が広くなり、実用的な時間及び空間計算量で扱えなくなる、いわゆる組合せ爆発を引き起こす懸念がある。組合せ爆発を抑制するために、シンボリック実行を効率化することが望まれる。
【０００９】
本発明は一つの側面として、シンボリック実行によるプログラムのテストケースの生成において、シンボリック実行の効率化を実現することを目的とする。
【課題を解決するための手段】
【００１０】
１つの態様では、配列を構成する複数の要素の各々の位置を表すシンボル変数であるインデックス値で、除外されていない未選択のインデックス値を選択対象として、該選択対象からインデックス値を選択する。また、対象プログラムをシンボリック実行することにより、選択したインデックス値に対応する要素が通過するパスを表すパス条件を生成する。さらに、生成したパス条件及び該生成したパス条件が表すパスを通過するテストデータをテストケースとして出力する。また、前記選択対象に含まれるインデックス値であり、パス条件を生成した要素と同一の要素に対応するインデックス値が、生成した該パス条件からインデックス値に由来する制約を除外したインデックス等価条件を充足可能か判定する。さらに、充足可能なインデックス値を前記選択対象から除外する。
【発明の効果】
【００１１】
一つの側面として、シンボリック実行によるプログラムのテストケースの生成において、シンボリック実行の効率化を実現することができる、という効果を有する。
【図面の簡単な説明】
【００１２】
【図１】本実施形態のテストケース生成装置の一例の概略構成を示すブロック図である。
【図２】本実施形態のシンボリック実行対象となるプログラム（TargetClass.method1）の具体例を示す図である。
【図３】図２に示したプログラムのフローを表したフロー図である。
【図４】本実施形態のテストケース生成装置によるテストケースの生成を説明するための図である。
【図５】本実施形態のテストケース生成装置によるシンボリック実行における図２に示したプログラムの実行空間を表した図である。
【図６】本実施形態のテストケース生成装置で生成されるテストケースの具体例を説明するための図である。
【図７】本実施例のテストケース生成装置の一例の概略構成を示すブロック図である。
【図８】テストケース生成装置として機能するコンピュータの概略構成を示すブロック図である。
【図９】本実施例に係るシンボリック実行対象となるプログラム（TargetClass.method1）の具体例を示す図である。
【図１０】図９に示したプログラムのフローを表したフロー図である。
【図１１】テストケース生成装置で実行されるテストケース生成処理の一例を示すフローチャートである。
【図１２】本実施例のテストケース生成装置で生成されるテストケースの具体例を説明するための図である。
【図１３】本実施例のテストケース生成装置で実行されるシンボリック実行処理の一例を示すフローチャートである。
【図１４】本実施例のテストケース生成装置で実行される手順１を説明するための図である
【図１５】本実施例のテストケース生成装置で実行される分岐選択処理の一例を示すフローチャートである。
【図１６】本実施例のテストケース生成装置で実行される手順２を説明するための図である。
【図１７】本実施例のテストケース生成装置で実行される手順３を説明するための図である。
【図１８】同一要素インデックス情報のその他の例について説明した図である。
【図１９】本実施例のテストケース生成装置で実行される手順４を説明するための図である。
【図２０】本実施例のテストケース生成装置で実行される情報更新処理の一例を示すフローチャートである。
【図２１】本実施例のテストケース生成装置で実行される手順５を説明するための図である。
【図２２】本実施例のテストケース生成装置で実行される手順６を説明するための図である。
【図２３】本実施例のテストケース生成装置で実行されるバックトラック先判定処理の一例を示すフローチャートである。
【図２４】本実施例のテストケース生成装置で実行される手順７を説明するための図である。
【図２５】本実施例のテストケース生成装置で実行される手順４（２回目）を説明するための図である。
【図２６】本実施例のテストケース生成装置で実行される手順５（２回目）を説明するための図である。
【図２７】本実施例のテストケース生成装置で実行される手順６（２回目）を説明するための図である。
【図２８】本実施例のテストケース生成装置で実行される手順７（２回目）を説明するための図である。
【図２９】本実施例のテストケース生成装置で実行される手順４（３回目）を説明するための図である。
【図３０】本実施例のテストケース生成装置で実行される手順５（３回目）を説明するための図である。
【図３１】本実施例のテストケース生成装置で実行される手順６（３回目）を説明するための図である。
【図３２】本実施例のテストケース生成装置で実行される手順７（３回目）を説明するための図である。
【図３３】本実施例のテストケース生成装置で実行される手順４（４回目）を説明するための図である。
【図３４】本実施例のテストケース生成装置で実行される手順５（４回目）を説明するための図である。
【図３５】本実施例のテストケース生成装置で実行される手順６（４回目）を説明するための図である。
【図３６】本実施例のテストケース生成装置で実行される手順７（４回目）を説明するための図である。
【図３７】同一パス上に複数の配列アクセスが存在する場合のシンボリック実行の例を説明するための図である。
【図３８】比較例のシンボリック実行の手法を説明するための図である。
【図３９】比較例のテストケース生成装置によるシンボリック実行における図２に示したプログラムの実行空間を表した図である。
【発明を実施するための形態】
【００１３】
以下、図面を参照して開示の技術の一例を詳細に説明する。
【００１４】
まず、開示の技術の一例の概略について説明する。図１は、本実施形態に係るテストケース生成装置１０の一例の概略構成を示すブロック図である。図１に示すように、テストケース生成装置１０は、シンボリック実行部１２、インデックスアクセス検出部１４、及びインデックス選択部１６を備える。さらに、テストケース生成装置１０は、同一要素インデックス情報生成部１８、同一要素判定部２０、インデックス等価条件生成部２２、及びインデックス等価判定部２４を備える。
【００１５】
本実施形態のテストケース生成装置１０は、配列を構成する複数の要素の位置を表すインデックスをシンボル変数としたシンボリック実行を行う機能を有する。
【００１６】
シンボリック実行とは、プログラム中の変数を具体化せず、シンボル値という特殊な値を持たせたまま実行する技術である。このシンボル値を保持する変数のことをシンボル変数という。
【００１７】
シンボリック実行では、シンボル変数が分岐等の判定条件に利用された場合に、判定条件が成立する場合及び成立しない場合のそれぞれのパターンを網羅的に実行する。この場合、現在のパターンを実行するために、すなわち、判定条件を成立させる及び成立させないために、シンボル値が満たさなければならない条件を保持する。シンボル値が満たさなければならない条件をパス条件という。パス条件は、シンボリック実行によって実行された各実行パス毎に保持される。あるパス条件を充足するようなシンボル値が存在しない場合、そのパス条件を保持する実行パスは実行不可能であるため、テスト対象から除外できる。充足可能なパス条件を保持する実行パスについては、パス条件の充足値をテストデータとみなすことで、テストデータを生成することができる。また、各テストデータが満たすパス条件は、テストデータがどのような実行経路を通過したかを示しており、テストデータに対するある面からの意味づけを与えている。
【００１８】
なお、シンボリック実行に関する基礎的な事項は、非特許文献である玉井哲雄、福永光一、「記号実行システム」、情報処理、pp.18-28等に記載されている。また、Java（登録商標）プログラムに対するシンボリック実行エンジンとしては、http://babelfish.arc.nasa.gov/trac/jpfに、Java（登録商標） PathFinder等が開示されている。また、シンボリック実行技術の公知例としては、特開２００９−０８７３５５号公報に記載された技術等が挙げられる。そのため、ここでは、シンボリック実行に関する基礎的な事項の詳細な説明を省略する。
【００１９】
開示の技術の実行部の一例であるシンボリック実行部１２は、シンボリック実行対象であるプログラム１１（以下、「対象プログラム」という）に対して、シンボリック実行を行う機能を有する。また、シンボリック実行部１２は、シンボル変数に関するテストデータとパス条件２６とを含むテストケース３３を生成して出力する機能を有する。具体的には、シンボリック実行部１２は、シンボリック実行を行い、インデックス選択部１６により選択されたインデックス値に対応する要素（シンボル値）が通過するパスを表すパス条件２６を生成する。さらに、シンボリック実行部１２は、生成したパス条件２６を充足するテストデータと、前記パス条件とを含むテストケース３３を出力する。
【００２０】
なお、シンボリック実行においては、配列のアクセスに関するパス条件を制約ソルバが扱える形で表現することが必要となる。制約ソルバが扱える条件式は、数値、文字列等のプリミティブ、あるいはそれに準ずるデータ型に関するものであり、データ型がinstanceof等の一般のオブジェクト型（Object型）である条件式は扱えない。そのため、シンボリック実行部１２では、データ型がint型のパス条件２６を生成する。
【００２１】
インデックスアクセス検出部１４は、シンボリック実行部１２で実行する命令が、シンボル変数をインデックスとした配列を構成する要素へのアクセス命令か否かを検出する機能を有する。インデックスアクセス検出部１４は、開示の技術の検出部の一例である。
【００２２】
開示の技術の選択部の一例であるインデックス選択部１６は、インデックス値の中から、現在の命令の後続の処理を継続するインデックス値を選択する機能を有する。シンボリック実行部１２では、選択されたインデックス値に対応するパス条件２６を生成する。そのため、具体的には、インデックス選択部１６は、シンボリック実行部１２によってパス条件を生成するインデックス値を選択してシンボリック実行部１２に出力する機能を有する。より具体的には、インデックス選択部１６は、選択済のインデックス値と未選択のインデックス値とを表す情報であるインデックス選択情報２８を生成する。インデックス選択情報２８の未選択のインデックス値がインデックス値の選択対象となる。そして、インデックス選択部１６は、生成したインデックス選択情報２８から、未選択のインデックス値を選択してシンボリック実行部１２に出力する機能を有する。
【００２３】
同一要素判定部２０は、命令を実行する際の配列に存在する要素同士が同一で有るか否かを判定する機能を有する。
【００２４】
同一要素インデックス情報生成部１８は、シンボル変数をインデックスとした配列のアクセス命令に対して、同一要素が格納されているインデックス値をまとめた同一要素インデックス情報３０を生成する機能を有する。具体的には、同一要素インデックス情報生成部１８は、同一要素判定部２０の判定結果に基づいて、同一要素インデックス情報３０を生成する。同一要素インデックス情報生成部１８は、開示の技術の生成部の一例である。
【００２５】
インデックス等価条件生成部２２は、シンボル変数をインデックスとした配列のアクセス命令を含む実行パスに関し、対応するパス条件からインデックス等価条件３２を生成する機能を有する。具体的には、インデックス等価条件３２とは、シンボリック実行部１２が生成したパス条件２６から選択したインデックス値に由来する制約式を除いたものである。すなわち、インデックス等価条件３２とは、同一要素を有し、インデックス値が同じパスを通過するための条件である。
【００２６】
インデックス等価判定部２４は、シンボリック実行部１２で使用したインデックス値の要素と同一の要素に対応する未選択のインデックス値が、インデックス等価条件３２を充足可能か否かを判定する機能を有する。具体的には、同一要素インデックス情報３０に基づいて、シンボリック実行部１２で使用したインデックス値の要素と同一の要素を検出して、判定を行う。また、インデックス等価判定部２４は、インデックス値がインデックス等価条件３２を充足可能と判定した場合は、判定したインデックス値をインデックス選択情報２８において未選択のインデックス値から除外する機能を有する。すなわち、インデックス等価判定部２４は、インデックス等価条件３２を充足可能なインデックス値を選択対象のインデックス値から除外する機能を有する。具体的には、インデックス等価判定部２４は、除外するインデックス値を、インデックス選択情報２８において未選択から選択済に変更することにより選択対象から除外して更新を行う。
【００２７】
このように、インデックス等価判定部２４がインデックス値を未選択から選択済に変更する更新を行うことにより、インデックス値が選択対象から除外されるため、インデックス選択部１６は、除外されたインデックス値を選択することがなくなる。このため、シンボリック実行部１２では、間引かれたインデックス値に対するパス条件の生成（後続処理の実行）を行わない。
【００２８】
テストケース生成装置１０の動作について説明する。具体例として、TargetClass.method1に対して、テストケース生成装置１０がシンボリック実行を行い、テストケース３３を生成する場合について説明する。図２には、プログラム（TargetClass.method1）の具体例を示す。また、図３には、図２に示したプログラムのフローを表したフロー図を示す。なお、図３に示したフロー図の記号内の数字は、プログラムの行に対応している。さらに、図４には、テストケース生成装置１０によるテストケースの生成を説明するための図を示す。
【００２９】
テストケース生成装置１０により、図２及び図３に示した、プログラム（TargetClass.method1）のシンボリック実行を実行する。TargetClass.method1では、シンボル変数としてｉｄｘが指定されている。このｉｄｘに対するシンボル値をαとした場合、シンボリック実行では、図５に示した実行空間を探索する。
【００３０】
シンボリック実行開始後、シンボリック実行部１２はプログラムの０６行目の命令を実行する。ここではシンボル変数に関する操作はないので実行空間上で分岐は生成されず、シンボリック実行部１２は、引き続き０７行目を実行する。０７行目の命令の「value = array[α]」は配列へのアクセスを行う。この場合、アクセスに使用するインデックス値はシンボル値であり、シンボル値の条件によって返却される配列の要素が異なってくるので実行空間に分岐が発生する。実行空間の０７行目から続く各エッジが発生する分岐に対応している。エッジに付与した「α＝＝０」及び「α＝＝１」といったラベルはそれぞれインデックス値が「０」の場合及び「１」の場合といった場合分けを示唆している。ここで、０７行目の実行時点において、配列（ａｒｒａｙ）には６つの要素（「ａ１」、「ｂ１」、「ａ２］、「ｂ１」、「ｂ１」、及び「ａ１」）が格納されている。
【００３１】
インデックスアクセス検出部１４は、０７行目の「value=array[α]」がシンボル変数を使用した配列へのアクセス命令であることを検出する。
【００３２】
同一要素インデックス情報生成部１８及び同一要素判定部２０は、この配列に基づいて、同一要素インデックス情報３０を生成する。図４及び図５には、生成される同一要素インデックス情報３０の具体例が示されている。
【００３３】
インデックス選択部１６は、インデックス選択情報２８を生成する。図４に示した更新前のインデックス選択情報２８は、既に、インデックス値「０」及び「５」が選択済であり、新たに、インデックス選択部１６がインデックス値「１」を選択して、シンボリック実行部１２に出力した状態を示している。
【００３４】
シンボリック実行部１２では、インデックス値「１」に応じたパス条件２６を生成する。ここでは、図４及び図５に示したように、パス条件２６として、「α＝＝１  ＆＆  α＜４」が生成される。シンボリック実行部１２は、テスト入力が「ｉｄｘ（α）：１」、及びパス条件が「α＝＝１  ＆＆  α＜４」のテストケースをテストケース３３の１つとして出力する。
【００３５】
インデックス等価条件生成部２２は、生成されたパス条件２６からインデックス値（ｉｄｘ）に由来した制約を除いたインデックス等価条件３２を生成する。パス条件２６が「α＝＝１  ＆＆  α＜４」の場合、「α＝＝１」を除くため、インデックス等価条件３２は、「α＜４」となる。
【００３６】
インデックス等価判定部２４は、同一要素インデックス情報３０に基づいて、インデックス等価条件３２を充足可能なインデックス値を判定する。上記具体例の場合、インデックス値が１と同じ要素を有するインデックス値は、同一要素インデックス情報３０によると、「３」及び「４」である。インデックス値が「３」の場合は、インデックス等価条件３２である「α＜４」を充足する。一方、インデックス値が「４」の場合は、インデックス等価条件３２である「α＜４」を充足できない。そのため、インデックス等価判定部２４は、インデックス値「３」を充足可能であると判定する。すなわち、インデックス値「３」の場合は、パス条件２６がインデックス値「１」の場合と同様になるため、テストケースを生成せずとも（テストを行わなくとも）、プログラムの動作確認には支障がない。そこで、インデックス等価判定部２４は、インデックス値「３」を未選択から選択済に変更し、インデックス選択情報２８の更新を行う。インデックス値「３」が選択済となったため、インデックス選択部１６は、インデックス値「３」を選択しない。そのため、シンボリック実行部１２では、インデックス値「３」に応じたパス条件２６は生成しない。
【００３７】
図６には、上述のようにしてテストケース生成装置１０により形成されるテストケース３３を示す。テストケース生成装置１０では、図５に示したように、インデックス値が「０」及び「５」の場合は、生成されるテストケースを１つにまとめることができる。また、テストケース生成装置１０では、図５に示したように、インデックス値が「１」及び「３」の場合は、生成されるテストケースを１つにまとめることができる。従って、テストケース生成装置１０では、図６に示したように、Ｎｏ．１〜４まで、４つのテストケースを含むテストケース３３が生成される。
【００３８】
（比較例）
ここで、比較例として、従来のテストケース生成装置によりシンボリック実行を行う場合について説明する。
【００３９】
シンボリック実行ではシンボル変数が関係する各分岐に関して、分岐条件成立の場合と非成立の場合のそれぞれの場合を探索・実行する。すなわち、各分岐条件の成立・非成立の組合せを行うことに等しい。この組合せの数はシンボル変数が関係する分岐条件数に対して幾何級数的に増加するため、ある程度規模の大きいプログラムになると組合せ数が多くなりすぎてシンボリック実行に要する計算資源が用意されたものを超えてしまう。例えば、図３８に示すように、ｎ個の独立した分岐が存在するプログラムを考える。図３８に示したプログラムは分岐の組合せとして、２ｎのパスを持つため、容易に組合せ爆発を引き起こす懸念がある。
【００４０】
配列へのアクセスが含まれるプログラムに対するシンボリック実行の従来技術として、次に述べる手法を比較例として説明する。比較例の手法では、シンボリック実行中にシンボル変数による配列へのインデックスアクセスに遭遇した場合、配列を構成する全要素に関して、各要素を選択した場合のパスを解析する。例えば、配列に３要素ある場合、０番目、１番目、２番目をそれぞれ選択した場合の実行パターンをすべて解析する。
【００４１】
実施形態で示したプログラム（図２参照）に対して比較例の手法を適用した場合について説明する。命令の０７行目を実行する時点において、配列（ａｒｒａｙ）には６つの要素が格納されており、比較例ではそれにしたがって「α＝＝０」から「α＝＝５」までの６通りの分岐を発生させる。シンボリック実行エンジンはこれら６通りの分岐を解析し、最終的には図３９に示す実行空間を探索してＮｏ．１〜６までのテストケースを含んだテストケースを得る。ここで、探索した実行パターンは９パターンであるが、そのうちの３パターンは実際には通過し得ない分岐の組合せを経ていることがパス条件から分かり、対応するテストケースもそれらのパターンを除いたものとなっている。
【００４２】
比較例のテストケース生成装置では、９パターンを探索した結果、６つのテストケースを生成している。一方、上述したように本実施形態のテストケース生成装置１０では、６パターンを探索した結果、４つのテストケースを含むテストケース３３を生成している。このように、本実施形態のテストケース生成装置１０では、探索するパターンの数を少なくし、シンボリック実行の効率化を図ることができる。そのため、本実施形態のテストケース生成装置１０では、組合せ爆発の発生を抑制することができる。
【００４３】
（実施例）
次に、開示の技術について、実施例を参照して詳細に説明する。なお、本実施例は、上述したテストケース生成装置１０と同様の技術に関して詳細に説明するためのものであるため、テストケース生成装置１００において上述と同様の構成及び動作については、詳細な説明を省略する場合がある。
【００４４】
図７は、本実施例に係るテストケース生成装置１００の一例の概略構成を示すブロック図である。図７に示すように、テストケース生成装置１００は、シンボリック実行部１１２、インデックスアクセス検出部１１４、及びインデックス選択部１１６を備える。さらに、テストケース生成装置１００は、同一要素インデックス情報生成部１１８、同一要素判定部１２０、インデックス等価条件生成部１２２、及びインデックス等価判定部１２４を備える。
【００４５】
シンボリック実行部１１２は、上述したテストケース生成装置１０のシンボリック実行部１２（図１参照）に対応している。なお、シンボリック実行部１１２は、シンボリック実行部１２と有している機能は同じであるが、有している種々の機能を実現するための機能部を備える。本実施例のシンボリック実行部１１２は、プログラム実行部１４０、パス条件計算部１４２、及び充足可能性判定部１４４を備えている。
【００４６】
プログラム実行部１４０は、シンボリック実行対象であるプログラム１１１（以下、「対象プログラム」という）に対して、シンボリック実行を行う機能を有する。パス条件計算部１４２は、インデックス選択部１１６により選択されたインデックス値に対応する要素（シンボル値）が通過するパスを表すパス条件１２６を計算することによりパス条件１２６を生成する機能を有する。充足可能性判定部１４４は、インデックス選択部１１６により選択されたインデックス値がパス条件１２６を充足する可能性の有無を判定する機能を有する。シンボリック実行部１１２は、パス条件１２６と充足可能性判定結果１４６とを含むテストケース１３３を出力する。
【００４７】
インデックスアクセス検出部１１４は、上述したテストケース生成装置１０のインデックスアクセス検出部１４（図１参照）に対応している。また、インデックス選択部１１６は、上述したテストケース生成装置１０のインデックス選択部１６（図１参照）に対応している。また、同一要素インデックス情報生成部１１８は、上述したテストケース生成装置１０の同一要素インデックス情報生成部１８（図１参照）に対応している。また、同一要素判定部１２０は、上述したテストケース生成装置１０の同一要素判定部２０（図１参照）に対応している。さらに、インデックス等価条件生成部１２２は、上述したテストケース生成装置１０のインデックス等価条件生成部２２（図１参照）に対応している。テストケース生成装置１００が有するこれらの各機能部は、それぞれ対応するテストケース生成装置１０の各機能部と同様の機能を有している。
【００４８】
また、インデックス等価判定部１２４は、上述したテストケース生成装置１０のインデックス等価判定部２４（図１参照）に対応している。なお、インデックス等価判定部１２４は、インデックス等価判定部２４と有している機能は同じであるが、有している種々の機能を実現するための機能部を備える。本実施例のインデックス等価判定部１２４は、チェック対象インデックス特定部１５０、シンボルインデックス具体化部１５２、充足可能性判定部１５４、結果集計部１５６、及びインデックス選択情報更新部１５８を備えている。
【００４９】
チェック対象インデックス特定部１５０は、同一の要素に対応する未選択のインデックス値をインデックス選択情報１２８及び同一要素インデックス情報１３０に基づいて特定する機能を有する。シンボルインデックス具体化部１５２は、インデックス等価条件１３２に対してシンボル化されたインデックス（シンボルインデックス）を具体化して制約ソルバとする機能を有する。充足可能性判定部１５４は、未選択のインデックス値が、制約ソルバ（インデックス等価条件１３２）を全て充足可能か否かを判定する機能を有する。結果集計部１５６は、充足可能性判定部１５４の判定結果を集計する機能を有する。また、インデックス選択情報更新部１５８は、結果集計部１５６で集計した集計結果に基づいて、インデックス選択情報１２８を更新する機能を有する。
【００５０】
なお、テストケース生成装置１００及び上述したテストケース生成装置１０は、例えば図８に示すコンピュータ６０で実現することができる。コンピュータ６０はＣＰＵ（Central Processing Unit）６２、メモリ６４、不揮発性の記憶部６６、入出力インターフェース（Ｉ／Ｆ）６８、及びネットワークＩ／Ｆ７０を備える。ＣＰＵ６２、メモリ６４、記憶部６６、入出力Ｉ／Ｆ６８、及びネットワークＩ／Ｆ７０は、バス７１を介して互いに接続されている。入出力Ｉ／Ｆ６８は、外部の入力装置及び出力装置に接続されている。入力装置は、テストケースを生成するための種々の情報を入力するための機能を有する装置であり、具体例としては、キーボードや、マウス等が挙げられる。また、出力装置は、生成されたテストケース１３３、３３等を出力する機能を有する装置であり、具体例としては、ディスプレイ等の各種表示装置やプリンタ等が挙げられる。
【００５１】
記憶部６６はＨＤＤ（Hard Disk Drive）やフラッシュメモリ等によって実現できる。記憶媒体としての記憶部６６には、コンピュータ６０をテストケース生成装置１００、１０として機能させるためのテストケース生成プログラム７２が記憶されている。ＣＰＵ６２は、テストケース生成プログラム７２を記憶部６６から読み出してメモリ６４に展開し、テストケース生成プログラム７２が有する各プロセスを順次実行する。
【００５２】
テストケース生成プログラム７２は、シンボリック実行プロセス７４、インデックスアクセス検出プロセス７６、インデックス選択プロセス７８、及び同一要素インデックス情報生成プロセス８０を有する。また、テストケース生成プログラム７２は、同一要素判定プロセス８２、インデックス等価条件生成プロセス８４、及びインデックス等価判定プロセス８６を有する。
【００５３】
ＣＰＵ６２は、シンボリック実行プロセス７４を実行することで、シンボリック実行部１１２、１２として動作する。また、ＣＰＵ６２は、インデックスアクセス検出プロセス７６を実行することで、インデックスアクセス検出部１１４、１４として動作する。また、ＣＰＵ６２は、インデックス選択プロセス７８を実行することで、インデックス選択部１１６、１６として動作する。また、ＣＰＵ６２は、同一要素インデックス情報生成プロセス８０を実行することで、同一要素インデックス情報生成部１１８、１８として動作する。また、ＣＰＵ６２は、同一要素判定プロセス８２を実行することで、同一要素判定部１２０、２０として動作する。また、ＣＰＵ６２は、インデックス等価条件生成プロセス８４を実行することで、インデックス等価条件生成部１２２、２２として動作する。さらに、ＣＰＵ６２は、インデックス等価判定プロセス８６を実行することで、インデックス等価判定部１２４、２４として動作する。
【００５４】
これにより、テストケース生成プログラム７２を実行したコンピュータ６０が、テストケース生成装置１００、１０として機能する。
【００５５】
なお、テストケース生成装置１００、１０は、例えば半導体集積回路、より詳しくはＡＳＩＣ（Application Specific Integrated Circuit）等で実現することも可能である。
【００５６】
次に、本実施例に係るテストケース生成装置１００による作用を、具体例として、図９に示したプログラム（TargetClass.method1）のテストケース１３３を生成する場合について説明する。図９には、プログラム（TargetClass.method1）の具体例を示す。また、図１０には、図９に示したプログラムのフローを表したフロー図を示す。なお、図１０に示したフロー図の記号内の数字は、プログラムの行に対応している。
【００５７】
まず、テストケース生成装置１００で実行されるテストケース生成処理の全体の流れについて説明する。図１１は、テストケース生成装置１００で実行されるテストケース生成処理の一例を示すフローチャートである。図１１に示したテストケース生成処理は、入出力Ｉ／Ｆ６８等を介して、ユーザ等からテストケースの生成を指示された場合に実行される。
【００５８】
ステップＳ１００では、詳細を後述するシンボリック実行処理を、テストケース生成装置１００の各機能部が、シンボリック実行対象１１１のプログラム（図９参照）に対して行う。シンボリック実行処理により、テストケース１３３が生成される。
【００５９】
なお、本実施例では、具体例として、対象プログラムは、入出力Ｉ／Ｆ６８または、ネットワークＩ／Ｆ７０を介してメモリ６４に格納される。
【００６０】
次のステップＳ１０２では、テストケース生成装置１００が、入出力Ｉ／Ｆ６８等を介して生成されたテストケース１３３を出力した後、本処理を終了する。
【００６１】
本実施例のテストケース生成装置１００で、生成されて出力される図９に示したプログラムのテストケース１３３を図１２に示す。
【００６２】
次に、テストケース生成処理のステップＳ１００のシンボリック実行処理について説明する。図１３は、テストケース生成装置１００で実行されるシンボリック実行処理（図１１、ステップＳ１００）の一例を示すフローチャートである。
【００６３】
まず、ステップＳ２００では、シンボリック実行部１１２が、シンボリック実行を開始するための処理として初期化を行う。初期化の手順を手順１として説明する。図１４は、本実施例のテストケース生成装置１００で実行される手順１を説明するための図である。
【００６４】
対象プログラムでは、具体例として、０６行目までは、シンボル変数が関係しないため、実行パスの分岐が生じない。そのため、シンボリック実行部１１２が、対象プログラムを０６行目まで実行する。
【００６５】
次のステップＳ２０２では、シンボリック実行部１１２が対象プログラムに後続の命令が存在するか否かを判定し、後続する命令が有る場合は、ステップＳ２０４へ移行する。
【００６６】
ステップＳ２０４では、シンボリック実行部１１２が対象プログラムの命令を解析し、さらに次のステップＳ２０６では、各機能部により分岐選択処理が実行される。図１５は、ステップＳ２０６の分岐選択処理の一例を示すフローチャートである。
【００６７】
ステップＳ３００では、インデックスアクセス検出部１１４が、シンボル変数による配列アクセスであるか否かを判定する。シンボル変数ではない場合は、ステップＳ３１０へ移行する。シンボル変数である場合は、ステップＳ３０２へ移行する。ステップＳ３００の処理の手順を手順２として説明する。図１６は、本実施例のテストケース生成装置１００で実行される手順２を説明するための図である。
【００６８】
シンボリック実行部１１２は、０７行目の命令「07:value = array[α]」が配列アクセス命令のオペランドがシンボル値であるか否かを確認する。なお、簡略化のため、array[α]と記載しているが、配列（ａｒｒａｙ）のメモリ状態は、｛ａ１，ｂ１，ｂ２，ｂ１，ｂ１，ａ１｝であるため、正確には、｛ａ１，ｂ１，ｂ２，ｂ１，ｂ１，ａ１｝［α］と記載すべきである。より正確には、ａ１，ｂ１，ｂ２もヒープへの参照ＩＤとすべきであるが、説明の便宜上、上記のように簡略化する。
【００６９】
シンボル変数を使用しないアクセスであれば、シンボリック実行部１１２は、通常のシンボリック実行を継続するため、ステップＳ３００からステップＳ３１０へ移行する。ステップＳ３１０では、分岐発生の有無を判定し、分岐が発生していない場合は、本分岐選択処理を終了する。一方、分岐が発生している場合は、ステップＳ３１２へ移行する。ステップＳ３１２でシンボリック実行部１２は、命令に従い分岐を選択した後、本分岐選択処理を終了する。
【００７０】
一方、シンボリック実行部１１２が、シンボル変数を使用するアクセスであると判定した場合は、ステップＳ３０２へ移行する。
【００７１】
ステップＳ３０２では、テストケース生成装置１００がインデックス情報の有無を判定する。具体的には、テストケース生成装置１００は、インデックス選択情報１２８及び同一要素インデックス情報１３０の両方が存在するか否かを判定する。インデックス選択情報１２８及び同一要素インデックス情報１３０の少なくとも一方が存在しない場合は、ステップＳ３０４へ移行する。ステップＳ３０４では、同一要素インデックス情報生成部１１８が同一要素インデックス情報１３０を生成する。次のステップＳ３０６では、インデックス選択部１６がインデックス選択情報１２８を生成する。ステップＳ３０４及びＳ３０６の処理の手順を手順３として説明する。図１７は、本実施例のテストケース生成装置１００で実行される手順３を説明するための図である。
【００７２】
同一要素インデックス情報生成部１１８は、同一要素判定部１２０の判定結果に基づいて、ヒープ上の同じオブジェクトを参照しているものをまとめることにより、同一要素インデックス情報１３０を生成する。本実施例の同一要素インデックス情報生成部１１８は、配列の各要素の中で、インデックス値が同じものとして、ヒープ上の同じオブジェクトを参照しているものをまとめる。同一要素インデックス情報１３０のＮｏ．１は、配列（ａｒｒａｙ）の０番目と５番目は、内容的に同じ要素を有することを表している。また、Ｎｏ．２は、配列（ａｒｒａｙ）の１番目、３番目、及び４番目は、内容的に同じ要素を有することを表している。さらにＮｏ．３は、配列（ａｒｒａｙ）の２番目は、内容的に同じ要素を有するものがないことを表している。
【００７３】
なお、ここで、同一要素判定部１２０が同一要素であるか否かについて判定する判定基準は予め定めておき、記憶部６６やメモリ６４等に記憶しておけばよい。判定基準は、本実施例に限らず、属性やオブジェクト等に応じて可変であり、対象プログラムのテストを行いたい観点等に基づいて定めることができる。例えば、要素「ａ」、「ｂ」という観点を判定基準として、同一要素インデックス情報生成部１１８が同一要素インデックス情報を生成した場合は、図１８に示した同一要素インデックス情報１３０Ａが生成される。
【００７４】
また、インデックス選択部１１６は、インデックス選択情報１２８を生成する。ここでは、インデックス選択情報１２８を生成したばかりであり、いずれのインデックス値も選択されていないため、インデックス選択情報１２８は、全てのインデックス値が未選択（初期化）の状態となる。
【００７５】
ステップＳ３０６の次、または、ステップＳ３０２でインデックス情報が有ると判定した場合に移行するステップＳ３０８では、インデックス選択部１１６が未選択のインデックス値を選択した後、本分岐選択処理を終了する。ステップＳ３０８の処理の手順を手順４として説明する。図１９は、本実施例のテストケース生成装置１００で実行される手順４を説明するための図である。
【００７６】
インデックス選択部１１６は、インデックス選択情報１２８を参照し、未選択のインデックス値の中から一つ選択し、選択したインデックス値を選択済とする。図１９は、インデックス選択部１１６がインデックス値「０」を選択した状態を示している。インデックス選択部１１６は、選択したインデックス値をシンボリック実行部１１２に出力する。なお、インデックス選択部１１６がいずれのインデックス値を選択するかは任意である。シンボリック実行部１１２は、インデックス選択部１１６が選択したインデックス値に対応する分岐を作成し、実行する。
【００７７】
このようにしてステップＳ２０６の分岐選択処理が終了すると、ステップＳ２０８へ進む。
【００７８】
ステップＳ２０８では、シンボリック実行部１１２が、インデックス選択部１１６により選択されたインデックス値に応じたパス条件を計算して生成する。シンボリック実行部１１２は、計算したパス条件に基づいて、各制約（制約ソルバ）がどの分岐に由来するものかを表す対応関係をメモリ６４等に記憶しておく。
【００７９】
次のステップＳ２１０では、シンボリック実行部１１２は、ステップＳ２０８で得たパス条件を充足可能であるか否かを判定する。充足不可能である場合は、ステップＳ２１８へ移行する。一方、充足可能である場合は、ステップＳ２１２へ移行する。ステップＳ２１２では、シンボリック実行部１２が対象プログラムの命令を実行した後、ステップＳ２０２に戻る。
【００８０】
ステップＳ２０２で、後続の命令が存在しない場合は、ステップＳ２１４へ移行する。ステップＳ２１４では、シンボリック実行部１１２が、テストケースを生成する。具体的には、シンボリック実行部１１２は、インデックス選択部１１６で選択されたインデックス値に対応するテストケースを生成する。
【００８１】
次のステップＳ２１６では、インデックス情報更新処理を行う。図２０は、ステップＳ２１６の情報更新処理の一例を示すフローチャートである。
【００８２】
ステップＳ４００では、インデックス等価条件生成部１２２が、ステップＳ２１４で生成したテストケースがシンボル変数による配列アクセスが関係するテストケースであるか否かを判定する。本実施例では、シンボリック実行部１１２は、上記ステップＳ２０８の処理で記憶しておいた、対応関係に基づいて、パス条件の各制約式が由来する命令を取得し、取得した命令が配列アクセス命令であるか否かを確認する。配列アクセスが関係するテストケースではない場合は、本インデックス情報更新処理を終了する。一方、配列アクセスが関係するテストケースである場合は、ステップＳ４０２へ移行する。
【００８３】
ステップＳ４０２では、インデックス等価条件生成部１２２がインデックス等価条件１３２を計算する。本実施例では、計算したインデックス等価条件１３２は、少なくとも、下記のステップＳ４０６の処理まで、保持する必要があるため、メモリ６４等に記憶しておく。テップＳ４０２の処理の手順を手順５として説明する。図２１は、本実施例のテストケース生成装置１００で実行される手順５を説明するための図である。インデックス等価条件生成部１２２は、インデックス選択を含むパス毎に、インデックス等価条件１３２を計算する。具体的には、パス条件からインデックス値によるアクセス由来の制約を除いたものがインデックス等価条件１３２である。図２１に示した例では、インデックス値「０」の場合、Ｎｏ．１のテストケースは、テスト入力が「ｉｄｘ（α）：０、ｎ（β）：４」、「パス条件が「α＝＝０  ＆＆  β＞３」である。この場合は、インデックス値に由来する「α＝＝０」を除いたものがインデックス等価条件１３２となるため、インデックス等価条件１３２は、「β＞３」となる。また、Ｎｏ．２のテストケースは、テスト入力が「ｉｄｘ（α）：０、ｎ（β）：０」、「パス条件が「α＝＝０  ＆＆  β＜＝３」である。この場合は、インデックス値に由来する「α＝＝０」を除いたものがインデックス等価条件１３２となるため、インデックス等価条件１３２は、「β＜＝３」となる。
【００８４】
次のステップＳ４０４では、インデックス等価判定部１２４は、注目するインデックス値選択について以降の全状態を探索済みであるか否かを判定する。すなわち、インデックス等価判定部１２４は、インデックス選択部１１６で選択し、テストケースを生成したインデックス値について、全状態の探索が済んでいるか否かを判定する。探索済みでない場合は、本インデックス情報更新処理を終了する。一方、探索済みの場合は、ステップＳ４０６へ移行する。
【００８５】
ステップＳ４０６では、インデックス等価判定部１２４が、未選択かつ注目するインデックス値と同じ要素が格納されているインデックス値を取得する。次のステップＳ４０８では、インデックス等価判定部１２４が、インデックス選択情報１２８において、取得したインデックス値のうち、インデックス等価条件１３２を満たすものを選択済にする。ステップＳ４０８の処理によりインデックス等価判定部１２４がインデックス選択情報１２８を更新した後、本インデックス情報更新処理を終了する。
【００８６】
ステップＳ４０６及びＳ４０８の処理の手順を手順６として説明する。図２２は、本実施例のテストケース生成装置１００で実行される手順６を説明するための図である。インデックス等価判定部１２４は、同一要素インデックス情報１３０を参照し、選択（注目）したインデックス値と要素が同一のインデックス値を取得する。上述した具体例のように、インデックス値「０」を選択（注目）している場合、インデックス等価判定部１２４は、同一要素インデックス情報１３０を参照し、同じ「ａ１」を要素とする、インデックス値「５」を取得する。なお、この時点では、インデックス選択情報１２８において、インデックス値「５」は、未選択状態である。
【００８７】
さらに、インデックス等価判定部１２４は、上記ステップＳ４０２（手順５）で計算したインデックス等価条件１３２の全てをインデックス値「５」の場合に充足可能か否かを判定する。具体的には、インデックス等価判定部１２４は、インデックス等価条件１３２に、インデックス値に由来する制約である「α＝＝５」を付加して制約ソルバを生成する。そして、インデックス等価判定部１２４は、インデックス値「５」の場合に、生成した全ての制約ソルバを充足可能か否かを判定する。インデックス値「５」の場合は、全ての制約ソルバを充足する。これは、インデックス値「０」の場合と、インデックス値「５」の場合とでは、同じパスを通過することを意味している。そのため、本実施例のテストケース生成装置１００では、インデックス値「５」については、探索を行わず、テストケースを生成しない。そのため、インデックス等価判定部１２４は、インデックス選択情報１２８において、インデックス値「５」を選択済にして更新する。
【００８８】
このようにしてステップＳ２１６のインデックス情報更新処理が終了すると、ステップＳ２１８へ進む。
【００８９】
ステップＳ２１８では、シンボリック実行部１１２がバックトラック先の有無を判定する。図２３は、ステップＳ２１８におけるバックトラック先判定処理の一例を示すフローチャートである。
【００９０】
ステップＳ５００では、シンボリック実行部１１２が、対象プログラムが開始状態であるか否かを判定する。開始状態である場合は、バックトラック先が無いとして、本バックトラック先判定処理を終了する。一方、開始状態ではない場合は、ステップＳ５０２へ移行する。
【００９１】
ステップＳ５０２では、シンボリック実行部１１２がシンボル変数による配列アクセスであるか否かを判定する。シンボル変数による配列アクセスである場合は、ステップＳ５０４へ移行する。ステップＳ５０２及びＳ５０４の処理の手順を手順７として説明する。図２４は、本実施例のテストケース生成装置１００で実行される手順７を説明するための図である。図２４（１）は、上述した具体例のように、インデックス値「０」、「５」が選択済となっている場合のインデックス選択情報１２８を示している。また、図２４（２）は、具体例として、全てのインデックス値が選択済となっている場合のインデックス選択情報１２８を示している。
【００９２】
シンボル変数による配列アクセスであり、未選択のインデックス値がある場合、すなわち、図２４（１）の場合は、ステップＳ５０４の判定により、バックトラック先が有るとして本バックトラック先判定処理を終了する。一方、シンボル変数による配列アクセスであり、未選択のインデックス値が無い場合、すなわち、図２４（２）の場合は、配列アクセスの前の命令までバックトラックするために、ステップＳ５０６へ移行する。
【００９３】
ステップＳ５０６で、シンボリック実行部１１２が、直前の状態に戻った後、ステップＳ５００に戻る。ステップＳ５００でプログラム開始状態ではなく、また、ステップＳ５０２でシンボル変数による配列アクセスでは無い場合は、ステップＳ５０８へ移行する。ステップＳ５０８では、シンボリック実行部１１２が、未選択の分岐の有無を判定する。全て選択済の場合等は、ステップＳ５０６へ移行し、本バックトラック先判定処理を繰り返す。一方、未選択の分岐がある場合は、バックトラック先が有るとして本バックトラック先判定処理を終了する。
【００９４】
このようにしてステップＳ２１８のバックトラック先判定処理が終了すると、バックトラック先が無い場合は、対象プログラムの全てのテストケース（テストケース１３３）を生成したため、本シンボリック実行処理を終了する。一方、パックトラック先がある場合は、ステップＳ２２０へ移行し、シンボリック実行部１１２が、バックトラック先にバックトラックした後、ステップＳ２０４へ移行し、本シンボリック実行処理を繰り返す。
【００９５】
上記では具体例として、インデックス値「０」、「５」が選択済となった状態について説明した。この具体例の場合は、ステップＳ２１８からステップＳ２２０、ステップＳ２０４を経由してステップＳ２０６の分岐選択処理を再び行う。分岐選択処理（図１５参照）では、ステップＳ３００で肯定され、さらにステップＳ３０２で肯定されるため、ステップＳ３０８に移行する。この場合の、ステップＳ３０８の処理である手順４（２回目）について説明する。図２５は、本実施例のテストケース生成装置１００で実行される手順４（２回目）を説明するための図である。上述の処理により、インデックス値「０」については、テストケースが生成されており、パス条件１２６を満たすインデックス値「５」も選択状態となっている。インデックス選択部１１６は、インデックス選択情報１２８を参照し、未選択のインデックス値「１」を選択し、選択済にする。
【００９６】
このように未選択のインデックス値をインデックス選択部１１６が選択することにより、シンボリック実行部１１２は、新たにインデックス値「０」に対応するパスを実行し、テストケースを生成する。そのため、シンボリック実行処理（図１３参照）を継続し、ステップＳ２１４において、インデックス値「０」に対応するテストケースを生成する。具体的には、シンボリック実行部１１２は、図１２に示したテストケース１３３のうち、Ｎｏ．３のテストケースを生成する。テストケースの生成後、ステップＳ２１６に進み、インデックス情報更新処理を行う。インデックス情報更新処理では、インデックス等価条件生成部１２２が上述した手順５（図２０、ステップＳ４０２）によりインデックス等価条件１３２を生成する。図２６は、本実施例のテストケース生成装置１００で実行される手順５（２回目）を説明するための図である。
【００９７】
図２６に示した例では、インデックス値「１」の場合、Ｎｏ．３のテストケースは、テスト入力が「ｉｄｘ（α）：１、ｎ（β）：０」、「パス条件が「α＝＝１  ＆＆  α＜４」である。この場合は、インデックス値に由来する「α＝＝１」を除いたものがインデックス等価条件１３２となるため、インデックス等価条件１３２は、「α＜４」となる。
【００９８】
このようにしてインデックス等価条件１３２が生成されると、インデックス等価判定部１２４が、手順６（図２０、ステップＳ４０６及びＳ４０８）を行う。図２７は、本実施例のテストケース生成装置１００で実行される手順６（２回目）を説明するための図である。インデックス等価判定部１２４は、同一要素インデックス情報１３０を参照し、選択（注目）したインデックス値と要素が同一のインデックス値を取得する。ここでは、インデックス値「１」を選択（注目）しているため、インデックス等価判定部１２４は、同一要素インデックス情報１３０を参照し、同じ「ｂ１」を要素とするインデックス値を取得する。具体的には、インデックス値「３」及び「４」を取得する。なお、この時点では、インデックス選択情報１２８において、インデックス値「３」、「４」は、未選択状態である。
【００９９】
さらに、インデックス等価判定部１２４は、上記ステップＳ４０２（手順５（２回目））で計算したインデックス等価条件１３２の全てをインデックス値「３」及び「４」の場合に、充足可能か否かを判定する。具体的には、インデックス等価判定部１２４は、インデックス値「３」の場合は、インデックス等価条件１３２に、インデックス値に由来する制約である「α＝＝３」を付加して制約ソルバを生成する。そして、インデックス等価判定部１２４は、生成した全ての制約ソルバをインデックス値「３」の場合に充足可能か否かを判定する。インデックス値「３」の場合は、全ての制約ソルバを充足する。これは、インデックス値「１」の場合と、インデックス値「３」の場合とでは、同じパスを通過することを意味している。そのため、本実施例のテストケース生成装置１００では、インデックス値「３」については、探索を行わず、テストケースを生成しない。そのため、インデックス等価判定部１２４は、インデックス選択情報１２８において、インデックス値「３」を選択済にして更新する。
【０１００】
一方、インデックス値「４」の場合は、インデックス等価条件１３２に、インデックス値に由来する制約である「α＝＝４」を付加して制約ソルバを生成する。そして、インデックス等価判定部１２４は、生成した全ての制約ソルバをインデックス値「４」の場合に充足可能か否かを判定する。インデックス値「４」の場合は、充足不能の場合がある。これは、インデックス値「１」の場合と、インデックス値「４」の場合とでは、異なるパスを通過することを意味している。そのため、本実施例のインデックス等価判定部１２４では、インデックス値「４」については、未選択のままとする。
【０１０１】
このようにしてインデックス等価判定部１２４がインデックス選択情報１２８を更新すると、シンボリック実行部１１２が、手順７（図２３、ステップＳ５０２及びＳ５０４）を行う。図２８は、本実施例のテストケース生成装置１００で実行される手順７（２回目）を説明するための図である。図２８に示したように、インデックス選択情報１２８には、未選択のインデックス値があるため、上述したように、バックトラックを行い、手順４に戻る。具体例の移行の処理について、上述と同様に、手順４〜７を繰り返すため、以降の処理については、手順に従って、簡略に説明する。
【０１０２】
図２９は、本実施例のテストケース生成装置１００で実行される手順４（３回目）を説明するための図である。上述の処理により、インデックス値「０」、「１」、「３」、及び「５」が選択状態となっている。インデックス選択部１１６は、インデックス選択情報１２８を参照し、未選択のインデックス値「２」を選択し、選択済にする。シンボリック実行部１１２は、新たにインデックス値「２」に対応するパスを実行し、テストケースを生成する。シンボリック実行部１１２は、インデックス値「２」に対応して、図１２に示したテストケース１３３のうち、Ｎｏ．４及び５のテストケースを生成する。
【０１０３】
テストケースの生成後、手順５（３回目）によりインデックス等価条件１３２を生成する。図３０は、本実施例のテストケース生成装置１００で実行される手順５（３回目）を説明するための図である。
【０１０４】
図３０に示した例では、インデックス値「２」の場合、Ｎｏ．４のテストケースは、テスト入力が「ｉｄｘ（α）：２、ｎ（β）：３」、「パス条件が「α＝＝２  ＆＆  β＞３」である。この場合は、インデックス値に由来する「α＝＝２」を除いたものがインデックス等価条件１３２となるため、インデックス等価条件１３２は、「β＞３」となる。また、Ｎｏ．５のテストケースは、テスト入力が「ｉｄｘ（α）：２、ｎ（β）：０」、「パス条件が「α＝＝２  ＆＆  β＜＝３」である。この場合は、インデックス値に由来する「α＝＝２」を除いたものがインデックス等価条件１３２となるため、インデックス等価条件１３２は、「β＜＝３」となる。
【０１０５】
このようにしてインデックス等価条件１３２が生成されると、インデックス等価判定部１２４が、手順６（３回目）を行う。図３１は、本実施例のテストケース生成装置１００で実行される手順６（３回目）を説明するための図である。インデックス等価判定部１２４は、同一要素インデックス情報１３０を参照し、選択（注目）したインデックス値と要素が同一のインデックス値を取得する。インデックス値「２」と要素が同一のインデックス値は存在しない。そのため、インデックス等価判定部１２４は、インデックス値を取得せず、また、上述した処理も行わない。そのため、インデックス選択情報１２８は更新前と更新後とで変化しない。
【０１０６】
続いてシンボリック実行部１１２は手順７（３回目）を行う。図３２は、本実施例のテストケース生成装置１００で実行される手順７（３回目）を説明するための図である。図３１に示したように、インデックス選択情報１２８には、未選択のインデックス値があるため、上述したように、バックトラックを行い、手順４に戻る。
【０１０７】
図３３は、本実施例のテストケース生成装置１００で実行される手順４（４回目）を説明するための図である。上述の処理により、インデックス値「０」、「１」、「２」、「３」、及び「５」が選択状態となっている。インデックス選択部１１６は、インデックス選択情報１２８を参照し、未選択のインデックス値「４」を選択し、選択済にする。シンボリック実行部１１２は、新たにインデックス値「４」に対応するパスを実行し、テストケースを生成する。シンボリック実行部１１２は、インデックス値「４」に対応して、図１２に示したテストケース１３３のうち、Ｎｏ．６及び７のテストケースを生成する。
【０１０８】
テストケースの生成後、手順５（４回目）によりインデックス等価条件１３２を生成する。図３４は、本実施例のテストケース生成装置１００で実行される手順５（４回目）を説明するための図である。
【０１０９】
図３４に示した例では、インデックス値「４」の場合、Ｎｏ．６のテストケースは、テスト入力が「ｉｄｘ（α）：４、ｎ（β）：５」、「パス条件が「α＝＝４  ＆＆  α＞＝４  ＆＆  α＜β」である。この場合は、インデックス値に由来する「α＝＝４」を除いたものがインデックス等価条件１３２となるため、インデックス等価条件１３２は、「α＞＝４  ＆＆  α＜β」となる。また、Ｎｏ．７のテストケースは、テスト入力が「ｉｄｘ（α）：４、ｎ（β）：０」、「パス条件が「α＝＝４  ＆＆  α＞＝４  ＆＆  α＞＝β」である。この場合は、インデックス値に由来する「α＝＝４」を除いたものがインデックス等価条件１３２となるため、インデックス等価条件１３２は、「α＞＝４  ＆＆  α＞＝β」となる。
【０１１０】
このようにしてインデックス等価条件１３２が生成されると、インデックス等価判定部１２４が、手順６（４回目）を行う。図３５は、本実施例のテストケース生成装置１００で実行される手順６（４回目）を説明するための図である。インデックス等価判定部１２４は、同一要素インデックス情報１３０を参照し、選択（注目）したインデックス値と要素が同一のインデックス値を取得する。インデックス値「４」と要素が同一で未選択のインデックス値は存在しない。そのため、インデックス等価判定部１２４は、インデックス値を取得せず、また、上述した処理も行わない。そのため、インデックス選択情報１２８は更新前と更新後とで変化しない。
【０１１１】
続いてシンボリック実行部１１２は手順７（４回目）を行う。図３６は、本実施例のテストケース生成装置１００で実行される手順７（４回目）を説明するための図である。図３６に示したように、インデックス選択情報１２８には、未選択のインデックス値がない。すなわち、配列アクセスのインデックス値に対応するパスは全て探索済みとなった。そのため、配列アクセスの前までバックトラックを行う。
【０１１２】
上述の処理により、テストケース１３３の生成が完了したため、テストケース生成処理では、ステップ１００が終了したことになる。このようにして生成されたテストケース１３３（図１２参照）では、Ｎｏ．１〜７まで７つのテストケースが生成される。テストケース生成装置１００では、インデックス値「５」の場合は、インデックス値「０」にまとめられ、インデックス値「３」の場合は、インデックス値「１」にまとめられる。そのため、テストケース生成装置１００では、これらのインデックス値に対する探索を間引くことにより、シンボリック実行の効率化を図ることができる。テストケース生成装置１００では、このようにシンボリック実行を効率化することにより、組合せ爆発の発生を抑制することができる。
【０１１３】
以上説明したように、テストケース生成装置１０及びテストケース生成装置１００によれば、インデックス選択部１６、１１６が配列を構成する複数の要素の位置を表すインデックスのインデックス値の中から、パス条件を生成するインデックス値を選択する。シンボリック実行部１２、１１２は、対象プログラムを、シンボリック実行する。シンボリック実行部１２、１１２は、インデックス選択部１６、１１６が選択したインデックス値に対応する要素が通過するパスを表すパス条件を生成して生成したパス条件を充足するテストデータと、前記パス条件とをテストケースとして出力する。
【０１１４】
同一要素インデックス情報生成部１８、１１８は、同一要素判定部２０、１２０の判定結果に基づいて、予め定められた判定基準に基づいて同一要素毎に、インデックス値をまとめた同一要素インデックス情報３０、１３０を生成する。インデックス等価判定部２４、１２４は、同一要素インデックス情報３０、１３０を参照し、パス条件を生成した要素と同一要素に対応する未選択のインデックス値を選択する。また、インデックス等価判定部２４、１２４は、パス条件からインデックス値に由来する制約を除いたインデックス等価条件３２、１３２を生成する。インデックス等価判定部２４、１２４は、選択したインデックス値の場合に、インデックス等価条件３２、１３２を充足可能か判定し、充足可能である場合は、インデックス選択情報２８、１２８において選択済として選択対象から除外する。
【０１１５】
このように、テストケース生成装置１０、１００では、シンボリック実行によるテストケースの生成において、テストケースを生成したインデックス値と同一要素であり、パス条件が同一のインデックス値を選択済とする。これにより、選択済としたインデックス値については探索を間引く（除外する）ことができるため、パスの発生を抑制することができ、シンボリック実行の効率化を図ることができる。従って、テストケース生成装置１０、１００では、シンボリック実行に要する時間及び空間計算量を抑制することができ、組合せ爆発の発生を抑制することができる。
【０１１６】
なお、上記実施形態及び実施例で説明したシンボリック実行（テストケース）は、同一パス上に配列アクセスが複数存在するプログラムに対しても適用可能であることはいうまでもない。この場合のテストケース生成装置の動作の概略について図３７に示した具体例を参照して説明する。図３７に示した具体例では、対象プログラムの０１行目（図３７、Ｓ１参照）と０３行目（図３７、Ｓ２、Ｓ３参照）に配列アクセスが存在するため、同一パス上に、２つの配列アクセスが存在している。インデックスは、ｉｄｘ１＝α１と、ｉｄｘ２＝α２と２種類存在する。このような場合では、インデックス選択情報及び同一要素インデックス情報を実行空間の状態毎にもたせることで対応することができる。図３７に示した場合では、状態Ｓ１、Ｓ２、及びＳ３毎に、インデックス選択情報及び同一要素インデックス情報をもたせればよい。また、生成されたパス条件（インデックス等価条件）には、状態Ｓ１と、状態Ｓ２またはＳ３と、に応じた条件式が含まれる。例えば、図３７に示した場合において、「α１＝＝０」、「α２＝＝０」を選択した場合では、パス条件が「α１＝＝０  ＆＆  α１＜４  ＆＆  α２＝＝０  ＆＆  α２＜２  ＆＆  α１＜２」となる。このうち、「α２＜２  ＆＆  α１＜２」は、「α２＝＝０」を選択した場合の状態Ｓ２のインデックス等価条件である。また、「α１＜４  ＆＆  α２＝＝０  ＆＆  α２＜２  ＆＆  α１＜２」は、「α２＝＝１」を選択した場合の状態Ｓ１のインデックス等価条件である。このようにインデックス等価条件も独立して計算することができるため、上記実施形態及び実施例で説明したシンボリック実行（テストケース）が適用可能となる。
【０１１７】
なお、上記実施形態及び実施例では、対象プログラムとして、プログラミング言語としてＪａｖａ（登録商標）を用いたプログラムを用いたが、プログラミング言語はこれに限定されず、どのようなものであってもよい。
【０１１８】
また、上記では、テストケース生成プログラム７２が記憶部６６に予め記憶（インストール）されている態様を説明したが、テストケース生成プログラム７２を記憶媒体に記録された形態で提供することも可能である。記憶媒体としては、例えば、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＤＶＤ−ＲＯＭ（Digital Versatile Disk Read Only Memory）、及びＵＳＢ（Universal Serial Bus）等が挙げられる。
【０１１９】
以上の上記実施形態に関し、更に以下の付記を開示する。
【０１２０】
（付記１）
コンピュータに、
配列を構成する複数の要素の各々の位置を表すシンボル変数であるインデックス値で、除外されていない未選択のインデックス値を選択対象として、該選択対象からインデックス値を選択し、
対象プログラムをシンボリック実行することにより、選択したインデックス値に対応する要素が通過するパスを表すパス条件を生成し、生成したパス条件及び該生成したパス条件が表すパスを通過するテストデータをテストケースとして出力し、
前記選択対象に含まれるインデックス値であり、パス条件を生成した要素と同一の要素に対応するインデックス値が、生成した該パス条件からインデックス値に由来する制約を除外したインデックス等価条件を充足可能か判定し、充足可能なインデックス値を前記選択対象から除外する、
ことを含む処理を実行させるテストケース生成プログラム。
【０１２１】
（付記２）
コンピュータに、
前記対象プログラム中の命令がインデックス値をシンボル変数とした配列の要素へのアクセス命令か否かを検出し、
同一であると判定した要素毎に、インデックス値をまとめた同一要素インデックス情報を生成し、
生成した前記同一要素インデックス情報に基づき、パス条件を生成した要素と同一の要素に対応する前記選択対象に含まれるインデックス値を検出する
ことを含む処理を実行させる付記１に記載のテストケース生成プログラム。
【０１２２】
（付記３）
コンピュータに、
前記アクセス命令を検出した場合に、予め定められた判定基準に基づいて同一であると判定し、
判定結果に基づいて、同一であると判定した要素毎に、インデックス値をまとめた同一要素インデックス情報を生成する、
ことを含む処理を実行させる付記２に記載のテストケース生成プログラム。
【０１２３】
（付記４）
コンピュータに、
前記インデックス等価条件を、生成したパス条件からインデックス値に由来する制約を除くことにより生成する、
ことを含む処理を実行させる付記１から付記３のいずれか１項に記載のテストケース生成プログラム。
【０１２４】
（付記５）
配列を構成する複数の要素の各々の位置を表すシンボル変数であるインデックス値で、除外されていない未選択のインデックス値を選択対象として、該選択対象からインデックス値を選択する選択部と、
対象プログラムをシンボリック実行することにより、前記選択部が選択したインデックス値に対応する要素が通過するパスを表すパス条件を生成し、生成したパス条件及び該生成したパス条件が表すパスを通過するテストデータをテストケースとして出力する実行部と、
前記選択対象に含まれるインデックス値であり、前記実行部でパス条件を生成した要素と同一の要素に対応するインデックス値が、生成した該パス条件からインデックス値に由来する制約を除外したインデックス等価条件を充足可能か判定し、充足可能なインデックス値を前記選択対象から除外する判定部と、
を備えた、テストケース生成装置。
【０１２５】
（付記６）
前記実行部で実行する命令がインデックス値をシンボル変数とした配列の要素へのアクセス命令か否かを検出する検出部と、
前記検出部が前記アクセス命令であると検出した場合に、予め定められた判定基準に基づいて同一であると判定した要素毎に、インデックス値をまとめた同一要素インデックス情報を生成する生成部と、
を備え、前記判定部は、前記同一要素インデックス情報に基づき、前記実行部によりパス条件を生成した要素と同一の要素に対応する前記選択対象に含まれるインデックス値を検出する、
付記５に記載のテストケース生成装置。
【０１２６】
（付記７）
前記アクセス命令を検出した場合に、予め定められた判定基準に基づいて同一であると判定する同一要素判定部を備え、
前記生成部は、前記同一要素判定部の判定結果に基づいて、同一であると判定した要素毎に、インデックス値をまとめた同一要素インデックス情報を生成する、
付記６に記載のテストケース生成装置。
【０１２７】
（付記８）
前記インデックス等価条件を、生成したパス条件からインデックス値に由来する制約を除くことにより生成する等価条件生成部を備えた、
付記５から付記７のいずれか１項に記載のテストケース生成装置。
【０１２８】
（付記９）
コンピュータに、
配列を構成する複数の要素の各々の位置を表すシンボル変数であるインデックス値で、除外されていない未選択のインデックス値を選択対象として、該選択対象からインデックス値を選択し、
対象プログラムをシンボリック実行することにより、選択したインデックス値に対応する要素が通過するパスを表すパス条件を生成し、生成したパス条件及び該生成したパス条件が表すパスを通過するテストデータをテストケースとして出力し、
前記選択対象に含まれるインデックス値であり、パス条件を生成した要素と同一の要素に対応するインデックス値が、生成した該パス条件からインデックス値に由来する制約を除外したインデックス等価条件を充足可能か判定し、充足可能なインデックス値を前記選択対象から除外する、
ことを含む処理を実行させるテストケース生成方法。
【０１２９】
（付記１０）
コンピュータに、
前記対象プログラム中の命令がインデックス値をシンボル変数とした配列の要素へのアクセス命令か否かを検出し、
同一であると判定した要素毎に、インデックス値をまとめた同一要素インデックス情報を生成し、
生成した前記同一要素インデックス情報に基づき、パス条件を生成した要素と同一の要素に対応する前記選択対象に含まれるインデックス値を検出する
ことを含む処理を実行させる付記９に記載のテストケース生成方法。
【０１３０】
（付記１１）
コンピュータに、
前記アクセス命令を検出した場合に、予め定められた判定基準に基づいて同一であると判定し、
判定結果に基づいて、同一であると判定した要素毎に、インデックス値をまとめた同一要素インデックス情報を生成する、
ことを含む処理を実行させる付記１０に記載のテストケース生成方法。
【０１３１】
（付記１２）
コンピュータに、
前記インデックス等価条件を、生成したパス条件からインデックス値に由来する制約を除くことにより生成する、
ことを含む処理を実行させる付記９から付記１１のいずれか１項に記載のテストケース生成方法。
【符号の説明】
【０１３２】
１０、１００  テストケース生成装置
１２、１１２  シンボリック実行部
１４、１１４  インデックスアクセス検出部
１６、１１６  インデックス選択部
１８、１１８  同一要素インデックス情報生成部
２０、１２０  同一要素判定部
２２、１２２  インデックス等価条件生成部
２４、１２４  インデックス等価判定部
６２  ＣＰＵ
６４  メモリ
６６  記憶部
７２  テストケース生成プログラム
７４  シンボリック実行プロセス
７６  インデックスアクセス検出プロセス
７８  インデックス選択プロセス
８０  同一要素インデックス情報生成プロセス
８２  同一要素判定プロセス
８４  インデックス等価条件生成プロセス
８６  インデックス等価判定プロセス
【図１】
2015228085.tif 000003
【図２】
2015228085.tif 000004
【図３】
2015228085.tif 000005
【図４】
2015228085.tif 000006
【図５】
2015228085.tif 000007
【図６】
2015228085.tif 000008
【図７】
2015228085.tif 000009
【図８】
2015228085.tif 000010
【図９】
2015228085.tif 000011
【図１０】
2015228085.tif 000012
【図１１】
2015228085.tif 000013
【図１２】
2015228085.tif 000014
【図１３】
2015228085.tif 000015
【図１４】
2015228085.tif 000016
【図１５】
2015228085.tif 000017
【図１６】
2015228085.tif 000018
【図１７】
2015228085.tif 000019
【図１８】
2015228085.tif 000020
【図１９】
2015228085.tif 000021
【図２０】
2015228085.tif 000022
【図２１】
2015228085.tif 000023
【図２２】
2015228085.tif 000024
【図２３】
2015228085.tif 000025
【図２４】
2015228085.tif 000026
【図２５】
2015228085.tif 000027
【図２６】
2015228085.tif 000028
【図２７】
2015228085.tif 000029
【図２８】
2015228085.tif 000030
【図２９】
2015228085.tif 000031
【図３０】
2015228085.tif 000032
【図３１】
2015228085.tif 000033
【図３２】
2015228085.tif 000034
【図３３】
2015228085.tif 000035
【図３４】
2015228085.tif 000036
【図３５】
2015228085.tif 000037
【図３６】
2015228085.tif 000038
【図３７】
2015228085.tif 000039
【図３８】
2015228085.tif 000040
【図３９】
2015228085.tif 000041