(57)【要約】【課題】対象プログラムに複雑な演算が含まれる場合であっても、ＳＡＴソルバ又はＳＭＴソルバに基づくモデル検査を短時間に実行する。【解決手段】モデル検査装置１は、過大近似対象の指令を過大近似し（Ｓ２）、過大近似後の指令と検証内容を制約式として含む充足可能性問題の解を求め（Ｓ３）、充足可能性問題が充足可能か否かを確認する（Ｓ４）。充足可能の場合（Ｓ４のＹｅｓ）、モデル検査装置１は、充足可能性問題の解における入力を過大近似前の対象プログラムに入力し（Ｓ５）、充足可能性問題の解が、検証内容に対する偽反例か否かを確認する（Ｓ６）。充足可能性問題の解が偽反例の場合（Ｓ６のＹｅｓ）、モデル検査装置１は、充足可能性問題の求解時に割り当てられた入力を含むことを条件として、過大近似対象の指令に対する入力範囲を縮小し（Ｓ７）、縮小後の入力範囲内で過大近似対象の指令を再度過大近似する（Ｓ８）。【選択図】図２
2015022515.tif 000002
【特許請求の範囲】
【請求項１】
ＳＡＴソルバ又はＳＭＴソルバを用いて対象プログラムが特定の検証内容を満たすか否かを検証するモデル検査装置であって、
前記対象プログラムに含まれる一部又は全部のコンピュータに対する指令を過大近似する過大近似手段と、
過大近似後の前記指令と前記検証内容を制約式として含む充足可能性問題が充足可能の場合、前記充足可能性問題の解における入力を過大近似前の前記対象プログラムに入力し、前記解が前記検証内容に対する偽反例か否かを判定する判定手段と、
前記解が偽反例の場合、前記充足可能性問題の求解時に割り当てられた入力を含むことを条件として、前記指令に対する入力範囲を縮小する入力範囲縮小手段と、
縮小後の前記入力範囲内で前記指令を再度過大近似する再過大近似手段と、
を具備することを特徴とするモデル検査装置。
【請求項２】
前記充足可能性問題が充足不可能の場合、現在の前記入力範囲が初期の前記入力範囲と同一でなければ、初期の前記入力範囲内であることを条件として、前記入力範囲を拡大する入力範囲拡大手段、
を更に具備することを特徴とする請求項１に記載のモデル検査装置。
【請求項３】
前記過大近似手段は、前記入力範囲を複数の小区間に分割し、前記小区間ごとに前記指令に対する出力範囲を決定することによって、前記指令を過大近似し、
前記再過大近似手段は、縮小後の前記入力範囲を前記小区間に分割し、前記小区間ごとに前記出力範囲を決定することによって、前記指令を再度過大近似する
ことを特徴とする請求項１又は請求項２に記載のモデル検査装置。
【請求項４】
コンピュータを、ＳＡＴソルバ又はＳＭＴソルバを用いて対象プログラムが特定の検証内容を満たすか否かを検証するモデル検査装置として機能させるためのモデル検査プログラムであって、
前記対象プログラムに含まれる一部又は全部のコンピュータに対する指令を過大近似する過大近似手段と、
過大近似後の前記指令と前記検証内容を制約式として含む充足可能性問題が充足可能の場合、前記充足可能性問題の解における入力を過大近似前の前記対象プログラムに入力し、前記解が前記検証内容に対する偽反例か否かを判定する判定手段と、
前記解が偽反例の場合、前記充足可能性問題の求解時に割り当てられた入力を含むことを条件として、前記指令に対する入力範囲を縮小する入力範囲縮小手段と、
縮小後の前記入力範囲内で前記指令を再度過大近似する再過大近似手段と、
を具備するモデル検査装置として機能させるためのモデル検査プログラム。
【請求項５】
ＳＡＴソルバ又はＳＭＴソルバを用いて対象プログラムのテストデータを生成するテストデータ生成装置であって、
前記対象プログラムに含まれる一部又は全部のコンピュータに対する指令を近似する近似手段と、
近似後の前記指令と前記検証内容を制約式として含む充足可能性問題が充足可能の場合、前記充足可能性問題の解における入力を近似前の前記対象プログラムに入力し、前記解が前記検証内容に対する偽反例か否かを判定する判定手段と、
前記解が偽反例の場合、前記充足可能性問題の求解時に割り当てられた入力を含むことを条件として、前記指令に対する入力範囲を縮小する入力範囲縮小手段と、
縮小後の前記入力範囲内で前記指令を再度近似する再近似手段と、
を具備することを特徴とするテストデータ生成装置。
【請求項６】
前記充足可能性問題が充足不可能の場合、現在の前記入力範囲が初期の前記入力範囲と同一でなければ、初期の前記入力範囲内であることを条件として、前記入力範囲を拡大する入力範囲拡大手段、
を更に具備することを特徴とする請求項１に記載のテストデータ生成装置。
【請求項７】
前記近似手段は、前記入力範囲を複数の小区間に分割し、前記小区間ごとに前記指令に対する出力範囲を決定することによって、前記指令を近似し、
前記再近似手段は、縮小後の前記入力範囲を前記小区間に分割し、前記小区間ごとに前記出力範囲を決定することによって、前記指令を再度近似する
ことを特徴とする請求項１又は請求項２に記載のテストデータ生成装置。
【請求項８】
コンピュータを、ＳＡＴソルバ又はＳＭＴソルバを用いて対象プログラムのテストデータを生成するテストデータ生成装置として機能させるためのテストデータ生成プログラムであって、
前記対象プログラムに含まれる一部又は全部のコンピュータに対する指令を近似する近似手段と、
近似後の前記指令と前記検証内容を制約式として含む充足可能性問題が充足可能の場合、前記充足可能性問題の解における入力を近似前の前記対象プログラムに入力し、前記解が前記検証内容に対する偽反例か否かを判定する判定手段と、
前記解が偽反例の場合、前記充足可能性問題の求解時に割り当てられた入力を含むことを条件として、前記指令に対する入力範囲を縮小する入力範囲縮小手段と、
縮小後の前記入力範囲内で前記指令を再度近似する再近似手段と、
を具備するテストデータ生成装置として機能させるためのテストデータ生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、対象プログラムが特定の検証内容を満たすか否かを検証するモデル検査装置等に関するものである。また、本発明は、対象プログラムのテストデータを生成するテストデータ生成装置等に関するものである。
【背景技術】
【０００２】
近年、ＳＡＴソルバやＳＭＴソルバの性能が向上している。ＳＡＴソルバとは、充足可能性問題（satisfiability problem, SAT）を解き、充足可能性を判定するプログラムである。また、ＳＭＴ（Satisfiability Modulo Theory）ソルバとは、ＳＡＴソルバの拡張であって、一階述語論理に複数の理論を組み込んだ充足可能性問題を解くことが可能なツールや、特定の理論をプラグインのように装着することで様々な理論を組み込んだ充足可能性問題を解決できるツール等が含まれる。
【０００３】
ＳＡＴソルバやＳＭＴソルバの応用技術としては、ソフトウエアのモデル検査手法やテストデータ生成手法等が研究されている。非特許文献１には、ＳＡＴソルバやＳＭＴソルバの応用技術が概説されている。また、特許文献１には、テストデータ生成手法が開示されている。
【０００４】
モデル検査やテストデータ生成のための市販ツールとしては、非特許文献２や３に記載のツールが知られている。非特許文献２に記載のツールは、Simulinkモデルを対象としたモデル検査、テストデータ生成のためのツールである。また、非特許文献３に記載のツールは、ＳＭＴソルバである。
【０００５】
例えば、対象プログラムが特定の検証内容を満たすか否かを検証するために、ＳＡＴソルバ等は、対象プログラムのソースコードの各行（コンピュータに対する各指令）と特定の検証内容を制約式として立式し、その制約式を充足する解が存在するか否かを判定する。充足する解が存在すれば、ＳＡＴソルバ等は、その解を一つ出力する。一方、充足する解が存在しなければ、ＳＡＴソルバ等は、充足不可能と判定し、処理を終了する。ＳＡＴソルバ等をテストデータ生成のためのツールとして利用する場合、ＳＡＴソルバ等が出力する解をテストデータとすれば良い。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０１２−１９４８３３号公報
【非特許文献】
【０００７】
【非特許文献１】梅村晃広著、「ＳＡＴソルバ・ＳＭＴソルバの技術と応用」コンピュータソフトウエア、Vol.27、No.3、pp.24-35、２０１０年
【非特許文献２】Mathworks Inc.,”SimulinkDesign Verifier User’s Guide(R2011b)”
【非特許文献３】L. de Moura and N. Bjorner, “Z3:AnEfficient SMT Solver”, in Tools and Algorithms for the Construction andAnalysis of Systems, 14th International Conference, 2008, pp.337-340
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、対象プログラムに複雑な演算が含まれる場合、非特許文献２や３等の市販ツールでは、結果が得られないか、又は多大な計算時間がかかるという問題がある。複雑な演算の例としては、三角関数、指数関数、平方根、対数関数等の演算や、ルックアップテーブルにおける内挿の演算等が挙げられる。
【０００９】
例えば、非特許文献２に記載のツールでは、上記に挙げた演算に対応していないため、上記に挙げた演算が含まれる場合、結果を得ることができない。また、例えば、非特許文献３に記載のツールでは、非線形多項式の演算に対応しているが、非線形多項式の演算が含まれる場合、計算時間が極端に増大する傾向がある。また、非特許文献３に記載のツールも、三角関数や指数関数等の演算に対応していないため、それらの演算が含まれる場合、結果を得ることができない。
【００１０】
本発明は、前述した問題点に鑑みてなされたものであり、その目的とすることは、対象プログラムに複雑な演算が含まれる場合であっても、ＳＡＴソルバ又はＳＭＴソルバに基づくモデル検査を短時間に実行可能なモデル検査装置等や、ＳＡＴソルバ又はＳＭＴソルバに基づくテストデータ生成を短時間に実行可能なテストデータ生成装置等を提供することである。
【課題を解決するための手段】
【００１１】
前述した目的を達成するための第１の発明は、ＳＡＴソルバ又はＳＭＴソルバを用いて対象プログラムが特定の検証内容を満たすか否かを検証するモデル検査装置であって、前記対象プログラムに含まれる一部又は全部のコンピュータに対する指令を過大近似する過大近似手段と、過大近似後の前記指令と前記検証内容を制約式として含む充足可能性問題が充足可能の場合、前記充足可能性問題の解における入力を過大近似前の前記対象プログラムに入力し、前記解が前記検証内容に対する偽反例か否かを判定する判定手段と、前記解が偽反例の場合、前記充足可能性問題の求解時に割り当てられた入力を含むことを条件として、前記指令に対する入力範囲を縮小する入力範囲縮小手段と、縮小後の前記入力範囲内で前記指令を再度過大近似する再過大近似手段と、を具備することを特徴とするモデル検査装置である。第１の発明によって、対象プログラムに複雑な演算が含まれる場合であっても、ＳＡＴソルバ又はＳＭＴソルバに基づくモデル検査を実行することができる。
【００１２】
第１の発明は、前記充足可能性問題が充足不可能の場合、現在の前記入力範囲が初期の前記入力範囲と同一でなければ、初期の前記入力範囲内であることを条件として、前記入力範囲を拡大する入力範囲拡大手段、を更に具備するようにしても良い。これによって、入力範囲縮小手段によって除外対象となった小区間においても再度精緻に解を探索し、充足可能性問題の充足可否を正確に判定することができる。
【００１３】
また、第１の発明における前記過大近似手段は、前記入力範囲を複数の小区間に分割し、前記小区間ごとに前記指令に対する出力範囲を決定することによって、前記指令を過大近似し、前記再過大近似手段は、縮小後の前記入力範囲を前記小区間に分割し、前記小区間ごとに前記出力範囲を決定することによって、前記指令を再度過大近似するようにしても良い。これによって、対象プログラムに複雑な演算が含まれる場合であっても、モデル検査を短時間に実行することができる。
【００１４】
第２の発明は、コンピュータを、ＳＡＴソルバ又はＳＭＴソルバを用いて対象プログラムが特定の検証内容を満たすか否かを検証するモデル検査装置として機能させるためのモデル検査プログラムであって、前記対象プログラムに含まれる一部又は全部のコンピュータに対する指令を過大近似する過大近似手段と、過大近似後の前記指令と前記検証内容を制約式として含む充足可能性問題が充足可能の場合、前記充足可能性問題の解における入力を過大近似前の前記対象プログラムに入力し、前記解が前記検証内容に対する偽反例か否かを判定する判定手段と、前記解が偽反例の場合、前記充足可能性問題の求解時に割り当てられた入力を含むことを条件として、前記指令に対する入力範囲を縮小する入力範囲縮小手段と、縮小後の前記入力範囲内で前記指令を再度過大近似する再過大近似手段と、を具備するモデル検査装置として機能させるためのモデル検査プログラムである。第２の発明によって、第１の発明のモデル検査装置を得ることができる。
【００１５】
第３の発明は、ＳＡＴソルバ又はＳＭＴソルバを用いて対象プログラムのテストデータを生成するテストデータ生成装置であって、前記対象プログラムに含まれる一部又は全部のコンピュータに対する指令を近似する近似手段と、近似後の前記指令と前記検証内容を制約式として含む充足可能性問題が充足可能の場合、前記充足可能性問題の解における入力を近似前の前記対象プログラムに入力し、前記解が前記検証内容に対する偽反例か否かを判定する判定手段と、前記解が偽反例の場合、前記充足可能性問題の求解時に割り当てられた入力を含むことを条件として、前記指令に対する入力範囲を縮小する入力範囲縮小手段と、縮小後の前記入力範囲内で前記指令を再度近似する再近似手段と、を具備することを特徴とするテストデータ生成装置である。第３の発明によって、対象プログラムに複雑な演算が含まれる場合であっても、ＳＡＴソルバ又はＳＭＴソルバに基づくテストデータ生成を実行することができる。
【００１６】
第３の発明は、前記充足可能性問題が充足不可能の場合、現在の前記入力範囲が初期の前記入力範囲と同一でなければ、初期の前記入力範囲内であることを条件として、前記入力範囲を拡大する入力範囲拡大手段、を更に具備するようにしても良い。これによって、入力範囲縮小手段によって除外対象となった小区間においても再度精緻に解を探索し、充足可能性問題の充足可否を正確に判定することができる。
【００１７】
第３の発明における前記近似手段は、前記入力範囲を複数の小区間に分割し、前記小区間ごとに前記指令に対する出力範囲を決定することによって、前記指令を近似し、前記再近似手段は、縮小後の前記入力範囲を前記小区間に分割し、前記小区間ごとに前記出力範囲を決定することによって、前記指令を再度近似するようにしても良い。これによって、対象プログラムに複雑な演算が含まれる場合であっても、テストデータ生成を短時間に実行することができる。
【００１８】
第４の発明は、コンピュータを、ＳＡＴソルバ又はＳＭＴソルバを用いて対象プログラムのテストデータを生成するテストデータ生成装置として機能させるためのテストデータ生成プログラムであって、前記対象プログラムに含まれる一部又は全部のコンピュータに対する指令を近似する近似手段と、近似後の前記指令と前記検証内容を制約式として含む充足可能性問題が充足可能の場合、前記充足可能性問題の解における入力を近似前の前記対象プログラムに入力し、前記解が前記検証内容に対する偽反例か否かを判定する判定手段と、前記解が偽反例の場合、前記充足可能性問題の求解時に割り当てられた入力を含むことを条件として、前記指令に対する入力範囲を縮小する入力範囲縮小手段と、縮小後の前記入力範囲内で前記指令を再度近似する再近似手段と、を具備するテストデータ生成装置として機能させるためのテストデータ生成プログラムである。第４の発明によって、第３の発明のテストデータ生成装置を得ることができる。
【発明の効果】
【００１９】
本発明により、対象プログラムに複雑な演算が含まれる場合であっても、ＳＡＴソルバ又はＳＭＴソルバに基づくモデル検査を短時間に実行可能なモデル検査装置等や、ＳＡＴソルバ又はＳＭＴソルバに基づくテストデータ生成を短時間に実行可能なテストデータ生成装置等を提供することができる。
【図面の簡単な説明】
【００２０】
【図１】モデル検査装置のハードウエア構成図
【図２】モデル検査装置の処理の流れを示すフローチャート
【図３】ステップＳ１、Ｓ２の処理を説明する図
【図４】ステップＳ３〜Ｓ７の処理を説明する図
【図５】ステップＳ８〜Ｓ１０の処理を説明する図
【図６】ステップＳ１１、Ｓ１２の処理を説明する図
【図７】具体例を説明する図（１）
【図８】具体例を説明する図（２）
【図９】具体例を説明する図（３）
【図１０】具体例を説明する図（４）
【発明を実施するための形態】
【００２１】
以下図面に基づいて、本発明の実施形態を詳細に説明する。
図１は、モデル検査装置のハードウエア構成図である。尚、図１のハードウエア構成は一例であり、用途、目的に応じて様々な構成を採ることが可能である。
【００２２】
図１に示すように、モデル検査装置１は、制御部１１、記憶部１２、メディア入出力部１３、通信制御部１４、入力部１５、表示部１６、周辺機器Ｉ／Ｆ部１７等が、バス１８を介して接続される。
【００２３】
制御部１１は、ＣＰＵ（Central Processing Unit）、ＲＯＭ（Read Only Memory）、ＲＡＭ（Random Access Memory）等によって構成される。
【００２４】
ＣＰＵは、記憶部１２、ＲＯＭ、記録媒体等に格納されるプログラムをＲＡＭ上のワークメモリ領域に呼び出して実行し、バス１８を介して接続された各装置を駆動制御し、モデル検査装置１が行う後述する処理を実現する。ＲＯＭは、不揮発性メモリであり、コンピュータのブートプログラムやＢＩＯＳ等のプログラム、データ等を恒久的に保持している。ＲＡＭは、揮発性メモリであり、記憶部１２、ＲＯＭ、記録媒体等からロードしたプログラム、データ等を一時的に保持するとともに、制御部１１が各種処理を行う為に使用するワークエリアを備える。
【００２５】
記憶部１２は、ＨＤＤ（Hard Disk Drive）等であり、制御部１１が実行するプログラム、プログラム実行に必要なデータ、ＯＳ（Operating System）等が格納される。プログラムに関しては、ＯＳに相当する制御プログラムや、後述する処理をコンピュータに実行させるためのアプリケーションプログラムが格納されている。これらの各プログラムコードは、制御部１１により必要に応じて読み出されてＲＡＭに移され、ＣＰＵに読み出されて各種の手段として実行される。
【００２６】
メディア入出力部１３（ドライブ装置）は、データの入出力を行い、例えば、ＣＤドライブ（−ＲＯＭ、−Ｒ、−ＲＷ等）、ＤＶＤドライブ（−ＲＯＭ、−Ｒ、−ＲＷ等）等のメディア入出力装置を有する。通信制御部１４は、通信制御装置、通信ポート等を有し、コンピュータとネットワーク間の通信を媒介する通信インタフェースであり、ネットワークを介して、他のコンピュータ間との通信制御を行う。ネットワークは、有線、無線を問わない。
【００２７】
入力部１５は、データの入力を行い、例えば、キーボード、マウス等のポインティングデバイス、テンキー等の入力装置を有する。入力部１５を介して、コンピュータに対して、操作指示、動作指示、データ入力等を行うことができる。表示部１６は、液晶パネル等のディスプレイ装置、ディスプレイ装置と連携してコンピュータのビデオ機能を実現するための論理回路等（ビデオアダプタ等）を有する。尚、入力部１５及び表示部１６は、タッチパネルディスプレイのように、一体となっていても良い。
【００２８】
周辺機器Ｉ／Ｆ（Interface）部１７は、コンピュータに周辺機器を接続させるためのポートであり、周辺機器Ｉ／Ｆ部１７を介してコンピュータは周辺機器とのデータの送受信を行う。周辺機器Ｉ／Ｆ部１７は、ＵＳＢ（Universal Serial Bus）やＩＥＥＥ１３９４やＲＳ−２３２Ｃ等によって構成されており、通常複数の周辺機器Ｉ／Ｆを有する。周辺機器との接続形態は有線、無線を問わない。バス１８は、各装置間の制御信号、データ信号等の授受を媒介する経路である。
【００２９】
図２は、モデル検査装置の処理の流れを示すフローチャートである。モデル検査装置１は、図２に示すフローチャートに従い、ＳＡＴソルバ又はＳＭＴソルバ（以下、「ＳＡＴソルバ等」という。）を用いて、対象プログラムが特定の検証内容を満たすか否かを検証する。ＳＡＴソルバ等は、対象プログラムのソースコードの各行（コンピュータに対する各指令）と特定の検証内容を制約式として含む充足可能性問題の解を求める機能を有する。
【００３０】
ＳＡＴソルバ等自体は、モデル検査装置１にインストールされていても良いし、他のコンピュータにインストールされていても良い。他のコンピュータにインストールされている場合、モデル検査装置１は、充足可能性問題の制約式を他のコンピュータに送信し、他のコンピュータから求解結果を受信する。以下では、ＳＡＴソルバ等が、モデル検査装置１にインストールされているものとして説明する。
【００３１】
図３に示すように、モデル検査装置１の制御部１１は、過大近似対象の指令に対する初期入力範囲を決定し（ステップＳ１）、過大近似対象の指令を過大近似する（ステップＳ２）。
【００３２】
過大近似とは、変換後の指令が、元の指令の振る舞いを全て含むような近似である。尚、過小近似とは、元の指令が、変換後の振る舞いを全て含むような近似である。以下では、過大近似又は過小近似のいずれにも決まらない近似のことを単に「近似」と呼ぶ。
【００３３】
本発明の実施の形態では、過大近似対象の指令は、市販のＳＡＴソルバ等が未対応、又は求解速度が遅くなるような複雑な演算である。複雑な演算の例としては、三角関数、指数関数、平方根、対数関数等の演算や、ルックアップテーブルにおける内挿の演算等が挙げられる。
【００３４】
図３は、ステップＳ１、Ｓ２の処理を説明する図である。図３（ａ）に示す非線形関数ｚ＝ｆ（ｘ）が、過大近似対象の指令である。また、説明を簡潔にするため、対象プログラムは過大近似対象の指令のみを含むものとする。すなわち、対象プログラムは、非線形関数ｚ＝ｆ（ｘ）の演算のみを行う。
【００３５】
図３（ｂ）には、過大近似対象の指令に対する初期入力範囲[ｘ１、ｘ５]が図示されている。初期入力範囲[ｘ１、ｘ５]は、例えば、ユーザが、自らの事前知識に基づいて、モデル検査装置１の入力部１５を介して入力する。制御部１１は、入力部１５を介して入力された範囲を初期入力範囲とする。
【００３６】
指令ｚ＝ｆ（ｘ）の過大近似について説明する。制御部１１は、初期入力範囲[ｘ１、ｘ５]を複数の小区間に分割する。図３（ｂ）には、小区間[ｘ１、ｘ２]、[ｘ２、ｘ３]、・・・が図示されている。次に、制御部１１は、小区間ごとに指令ｚ＝ｆ（ｘ）に対する出力範囲を決定する。図３（ｂ）には、小区間[ｘ１、ｘ２]に対する出力範囲[ｚ１、ｚ２]、小区間[ｘ２、ｘ３]に対する出力範囲[ｚ２、ｚ３]、・・・が図示されている。図３（ｂ）を参照すれば、変換後の指令が、元の指令ｚ＝ｆ（ｘ）の振る舞いを全て含むことが分かる。このように過大近似された指令であれば、ＳＡＴソルバ等が短時間に充足可能性問題の解を求めることができる。
【００３７】
図２の説明に戻る。次に、制御部１１は、ＳＡＴソルバ等を用いて、過大近似後の指令と検証内容を制約式として含む充足可能性問題の解を求める（ステップＳ３）。検証内容は、例えば、対象プログラムの出力値に関するものである。
【００３８】
次に、制御部１１は、ＳＡＴソルバ等による求解結果を参照し、充足可能性問題が充足可能か否かを確認する（ステップＳ４）。ＳＡＴソルバ等は、求解結果として、充足可能な解を一つ出力するか、又は充足不可能である旨を出力する。制御部１１は、ＳＡＴソルバ等から充足可能な解が出力されれば、充足可能性問題が充足可能であると判断し、充足不可能である旨が出力されれば、充足可能性問題が充足不可能であると判断する。
【００３９】
充足可能性問題が充足可能の場合（ステップＳ４のＹｅｓ）、制御部１１は、充足可能性問題の解における入力を過大近似前の対象プログラムに入力する（ステップＳ５）。充足可能性問題の解は、対象プログラムの入力と出力の組（ｘ、ｚ）であり、「充足可能性問題の解における入力」とは、このうちの入力の値ｘを指す。
【００４０】
次に、制御部１１は、過大近似前の対象プログラムの出力を参照し、充足可能性問題の解が、検証内容に対する偽反例か、又は真の反例のいずれであるかを確認する（ステップＳ６）。充足可能性問題の解が偽反例の場合（ステップＳ６のＹｅｓ）、制御部１１は、充足可能性問題の求解時に割り当てられた入力を含むことを条件として、過大近似対象の指令に対する入力範囲を縮小する（ステップＳ７）。ＳＡＴソルバ等は、充足可能性問題の求解時、過大近似対象の各指令に対して入力と出力を割り当てる。「充足可能性問題の求解時に割り当てられた入力」とは、このＳＡＴソルバ等によって割り当てられた過大近似対象の各指令に対する入力を指す。
【００４１】
図４は、ステップＳ３〜Ｓ７の処理を説明する図である。図４（ａ）には、ＳＡＴソルバ等によって得られる解（ｘ＊、ｚ＊）が図示されている。制御部１１は、解における入力ｘ＊を過大近似前の対象プログラムに入力し、過大近似前の対象プログラムの出力を参照する。
【００４２】
過大近似前の対象プログラムの出力が検証内容を満たさない場合、すなわち、充足可能性問題の解が偽反例の場合、制御部１１は、充足可能性問題の求解時に割り当てられた入力ｘ＊を含むことを条件として、初期入力範囲[ｘ１、ｘ５]を縮小する。図４（ｂ）には、縮小後の入力範囲[ｘ１１、ｘ１４]が図示されている。
【００４３】
ステップＳ７の意義について説明する。ＳＡＴソルバ等によって得られる解が偽反例になる理由は、過大近似による誤差である。真の反例となる解が得られる過大近似対象の指令に対する入力は、前回偽反例となった解の求解時に割り当てられた値の周辺に存在する可能性が高いと考えることができる。そこで、後述するステップＳ８の再過大近似において過大近似の精度を上げるために、ステップＳ７では、過大近似対象の指令に対する入力範囲を前回偽反例となった解の求解時に割り当てられた値の周辺に限定している。
【００４４】
図２の説明に戻る。次に、制御部１１は、縮小後の入力範囲内で過大近似対象の指令を再度過大近似する（ステップＳ８）。制御部１１は、ステップ２における過大近似と同様、縮小後の入力範囲を小区間に分割し、小区間ごとに出力範囲を決定することによって、過大近似対象の指令を再度過大近似する。ここで、制御部１１は、前回の過大近似後の指令よりも振る舞いが減少するように、すなわち、より過大近似前の指令に近づくように、過大近似対象の指令を再度過大近似する。
【００４５】
次に、制御部１１は、ステップ３、４の処理を繰り返す。充足可能性問題が充足不可能の場合（ステップＳ４のＮｏ）、制御部１１は、現在の入力範囲が初期入力範囲と同一か否か確認する（ステップＳ９）。
【００４６】
現在の入力範囲が初期入力範囲と同一でない場合（ステップＳ９のＮｏ）、制御部１１は、初期入力範囲内を条件として、入力範囲を拡大する（ステップＳ１０）。ここで、制御部１１は、ステップＳ８において再度過大近似を行った小区間についてはそのままとし、ステップＳ７において除外対象となった小区間の一部又は全部を再度入力範囲に加えることによって、入力範囲を拡大する。その後、制御部１１は、ステップ３、４の処理を繰り返す。
【００４７】
図５は、ステップＳ８〜Ｓ１０の処理を説明する図である。図５（ａ）には、縮小後の入力範囲[ｘ１１、ｘ１４]内で再度過大近似された指令が図示されている。すなわち、小区間[ｘ１１、ｘ１２]に対する出力範囲[ｚ１３、ｚ１４]、小区間[ｘ１２、ｘ１３]に対する出力範囲[ｚ１１、ｚ１３]、小区間[ｘ１３、ｘ１４]に対する出力範囲[ｚ１１、ｚ１２]が図示されている。
【００４８】
図３（ｂ）と図５（ａ）を比較すると、図５（ａ）に図示する再度過大近似された指令の方が、図３（ｂ）に図示する最初に過大近似された指令よりも、振る舞いが減少していることが分かる、すなわち、過大近似前の指令に近づいていることが分かる。
【００４９】
縮小後の入力範囲[ｘ１１、ｘ１４]に対するステップＳ３の処理の結果、充足可能性問題が充足不可能となると、制御部１１は、現在の入力範囲[ｘ１１、ｘ１４]が初期入力範囲[ｘ１、ｘ５]（図３（ｂ）参照）と同一か否か確認する。この時点では両者が同一ではないので、制御部１１は、初期入力範囲[ｘ１、ｘ５]内を条件として、入力範囲を拡大する。
【００５０】
図５（ｂ）には、拡大後の入力範囲[ｘ２１、ｘ２５]が図示されている。制御部１１は、ステップＳ８において再度過大近似を行った小区間[ｘ１１、ｘ１２]〜［ｘ１３、ｘ１４］についてはそのままとし、ステップＳ７において除外対象となった小区間の一部［ｘ２、ｘ３］（図４参照）を再度入力範囲に加えることによって、入力範囲を拡大する。すなわち、[ｘ１１、ｘ１２]＝[ｘ２２、ｘ２３]、[ｘ１２、ｘ１３]＝[ｘ２３、ｘ２４]、[ｘ１３、ｘ１４]＝[ｘ２４、ｘ２５]であり、[ｘ２１、ｘ２２]（＝［ｘ２、ｘ３］）が新たに加えられた小区間である。
【００５１】
ステップＳ１０の意義について説明する。前述のステップＳ７では、過大近似対象の指令に対する入力範囲を偽反例となった解の周辺に限定している。この限定の結果、充足可能性問題が充足不可能になった場合、ステップＳ７において除外対象となった小区間に真の反例となる解が存在する可能性がある。そこで、除外対象となった小区間において解を探索するために、ステップＳ１０では、過大近似対象の指令に対する入力範囲を拡大している。尚、ステップＳ８において再度過大近似を行った小区間についてはそのままとしているので、以前と同じ間違いを犯さない、すなわち、同様の偽反例となる解が得られることはない。
【００５２】
図２の説明に戻り、最終的な出力結果について説明する。充足可能性問題の解が真の反例の場合（ステップＳ６のＮｏ）、制御部１１は、真の反例を出力し（ステップＳ１１）、処理を終了する。また、充足可能性問題が充足不可能の場合（ステップＳ４のＮｏ）であって、現在の入力範囲が初期入力範囲と同一の場合（ステップＳ９のＹｅｓ）、初期入力範囲内における精緻な解探索が終了したことになるので、制御部１１は、反例なしを出力し（ステップＳ１２）、処理を終了する。
【００５３】
図６は、ステップＳ１１、Ｓ１２の処理を説明する図である。図６（ａ）には、真の反例（ｘ＊、ｚ＊）の出力が図示されている。図６（ｂ）には、現在の入力範囲が初期入力範囲となり、反例なしの出力が図示されている。
【００５４】
図７〜図１０は、具体例を説明する図である。以下では、複雑な演算として、平方根を例に挙げて説明する。
【００５５】
図７には、対象プログラム２０が図示されている。対象プログラム２０は、入力（ｐ１、ｐ２）、出力ｒであって、３つの指令を含む。ｐ１、ｐ２の取り得る範囲は、［０、１］である。指令２２ａは、入力ｘ、出力ｙ＝ｘ＾（１／２）の演算であって、過大近似対象である。指令２２ｂは、２つの入力を加算して出力する演算である。指令２２ｃは、入力ｘ、出力ｙ＝ｘ＾（１／２）の演算であって、過大近似対象である。
【００５６】
検証内容２１は、対象プログラム２０について、「ｒ∈［１．１、１．２］を満たす入力（ｐ１、ｐ２）は存在しない」という命題である。過大近似対象の指令２２ａ、２２ｂに対する初期入力範囲２３は、「０≦ｘ≦３」である。
【００５７】
図８（ａ）には、ステップＳ２における結果として、過大近似後の指令２４ａ、２４ｃが図示されている。過大近似後の指令２４ａ、２４ｃは、小区間「０≦ｘ＜１」に対する出力範囲「０≦ｙ＜１」、小区間「１≦ｘ＜２」に対する出力範囲「１≦ｙ＜２＾（１／２）」、小区間「２≦ｘ≦３」に対する出力範囲「２＾（１／２）≦ｙ≦３＾（１／２）」である。平方根は単調増加関数であるから、各小区間の上下限における平方根の値を出力範囲の上下限として決定することができる。
【００５８】
図８（ｂ）には、１回目のステップＳ３の結果が図示されている。入力ｐ１＝０．５、入力ｐ２＝１の値は、ＳＡＴソルバ等が、ｐ１、ｐ２の取り得る範囲[０、１]で割り当てた値である。
【００５９】
２４ａの出力＝０．２は、ＳＡＴソルバ等が、図８（ａ）に示す過大近似後の指令２４ａを満たす範囲で割り当てた値である。すなわち、２４ａに対する入力ｘ（＝入力ｐ１）は、０．５であるから、０≦０．５＜１より、ＳＡＴソルバ等は、０≦ｙ＜１を満たすｙの値を、２４ａの出力として割り当てる。
【００６０】
２２ｂの出力＝１．２は、ＳＡＴソルバ等が、指令２２ｂの演算を実行することによって得られる値である。すなわち、２２ｂに対する２つの入力（２４ａの出力と入力ｐ２）は、０．２と１であるから、０．２＋１の演算結果を、２２ｂの出力として割り当てる。
【００６１】
２４ｃの出力（＝ｒ）＝１．１は、ＳＡＴソルバ等が、図８（ａ）に示す過大近似後の指令２４ｃを満たす範囲で割り当てた値である。すなわち、２４ｃに対する入力ｘ（＝２２ｂの出力）は、１．２であるから、１≦１．２＜２より、ＳＡＴソルバ等は、１≦ｙ＜２＾（１／２）を満たすｙの値を、２４ｃの出力として割り当てる。
【００６２】
図８（ｂ）の時点では、ステップ３の結果、充足可能性問題の解として、入力（ｐ１、ｐ２）＝（０．５、１）、出力ｒ＝１．１が得られたことになる。制御部１１は、充足可能性問題が充足可能と判断し（ステップＳ４のＹｅｓ）、ステップＳ５の処理を実行する。
【００６３】
図８（ｃ）には、１回目のステップＳ５、Ｓ６の結果が図示されている。入力ｐ１＝０．５、入力ｐ２＝１の値は、充足可能性問題の解における入力である。制御部１１は、これらの値を過大近似前の対象プログラム２０に入力する。
【００６４】
２２ａの出力＝０．７１は、０．５＾（１／２）の演算結果である。２２ｂの出力＝１．７１は、０．７１＋１の演算結果である。２２ｃの出力（＝ｒ）＝１．３１は、１．７１＾（１／２）の演算結果である。ｒ＝１．３１は、ｒ∈［１．１、１．２］を満たさないことから、検証内容２１の真の反例ではない。従って、ステップＳ６の判定結果は偽反例（ステップＳ６のＹｅｓ）となる。
【００６５】
図９（ａ）には、１回目のステップＳ７、Ｓ８の結果が図示されている。解が偽反例なので（ステップＳ６のＹｅｓ）、制御部１１は、指令２４ａに対する入力範囲を、充足可能性問題の求解時に割り当てられた入力０．５（図８（ｂ）の「入力ｐ１」を参照）を含む小区間０≦ｘ＜１に縮小する。同様に、制御部１１は、指令２４ｃに対する入力範囲を、充足可能性問題の求解時に割り当てられた入力１．２（図８（ｂ）の「２２ｂの出力」を参照）を含む小区間１≦ｘ＜２に縮小する。
【００６６】
過大近似後の指令２４ａは、小区間「０≦ｘ＜１／３」に対する出力範囲「０≦ｙ＜（１／３）＾（１／２）」、小区間「１／３≦ｘ＜２／３」に対する出力範囲「（１／３）＾（１／２）≦ｙ＜（２／３）＾（１／２）」、小区間「２／３≦ｘ＜１」に対する出力範囲「（２／３）＾（１／２）≦ｙ＜１」である。
【００６７】
過大近似後の指令２４ｃは、小区間「１≦ｘ＜４／３」に対する出力範囲「１≦ｙ＜（４／３）＾（１／２）」、小区間「４／３≦ｘ＜５／３」に対する出力範囲「（４／３）＾（１／２）≦ｙ＜（５／３）＾（１／２）」、小区間「５／３≦ｘ＜２」に対する出力範囲「（５／３）＾（１／２）≦ｙ＜２＾（１／２）」である。
【００６８】
図９（ｂ）には、２回目のステップＳ３の結果が図示されている。入力ｐ１＝０．２、入力ｐ２＝１の値は、ＳＡＴソルバ等が、ｐ１、ｐ２の取り得る範囲[０、１]で割り当てた値である。
【００６９】
２４ａの出力＝０．１は、ＳＡＴソルバ等が、図９（ａ）に示す過大近似後の指令２４ａを満たす範囲で割り当てた値である。すなわち、２４ａに対する入力ｘ（＝入力ｐ１）は、０．２であるから、０≦０．２＜１／３より、ＳＡＴソルバ等は、０≦ｙ＜（１／３）＾（１／２）≒０．５８を満たすｙの値を、２４ａの出力として割り当てる。
【００７０】
２２ｂの出力＝１．１は、ＳＡＴソルバ等が、指令２２ｂの演算を実行することによって得られる値である。すなわち、２２ｂに対する２つの入力（２４ａの出力と入力ｐ２）は、０．１と１であるから、０．１＋１の演算結果を、２２ｂの出力として割り当てる。
【００７１】
２４ｃの出力（＝ｒ）＝１．１は、ＳＡＴソルバ等が、図９（ａ）に示す過大近似後の指令２４ｃを満たす範囲で割り当てた値である。すなわち、２４ｃに対する入力ｘ（＝２２ｂの出力）は、１．１であるから、１≦１．１＜４／３より、ＳＡＴソルバ等は、１≦ｙ＜（４／３）＾（１／２）≒１．１５を満たすｙの値を、２４ｃの出力として割り当てる。
【００７２】
図９（ｂ）の時点では、ステップ３の結果、充足可能性問題の解として、入力（ｐ１、ｐ２）＝（０．２、１）、出力ｒ＝１．１が得られたことになる。制御部１１は、充足可能性問題が充足可能と判断し（ステップＳ４のＹｅｓ）、ステップＳ５の処理を実行する。
【００７３】
図９（ｃ）には、２回目のステップＳ５、Ｓ６の結果が図示されている。入力ｐ１＝０．２、入力ｐ２＝１の値は、充足可能性問題の解における入力である。制御部１１は、これらの値を過大近似前の対象プログラム２０に入力する。
【００７４】
２２ａの出力＝０．４５は、０．２＾（１／２）の演算結果である。２２ｂの出力＝１．４５は、０．４５＋１の演算結果である。２２ｃの出力（＝ｒ）＝１．２０３は、１．４５＾（１／２）の演算結果である。ｒ＝１．２０３は、ｒ∈［１．１、１．２］を満たさないことから、検証内容２１の真の反例ではない。従って、ステップＳ６の判定結果は偽反例（ステップＳ６のＹｅｓ）となる。
【００７５】
図１０（ａ）には、２回目のステップＳ７、Ｓ８の結果が図示されている。解が偽反例なので（ステップＳ６のＹｅｓ）、制御部１１は、指令２４ａに対する入力範囲を、充足可能性問題の求解時に割り当てられた入力０．２（図９（ｂ）の「入力ｐ１」を参照）を含む小区間０≦ｘ＜１／３に縮小する。同様に、制御部１１は、指令２４ｃに対する入力範囲を、充足可能性問題の求解時に割り当てられた入力１．１（図９（ｂ）の「２２ｂの出力」を参照）を含む小区間１≦ｘ＜４／３に縮小する。
【００７６】
過大近似後の指令２４ａは、小区間「０≦ｘ＜１／９」に対する出力範囲「０≦ｙ＜（１／９）＾（１／２）」、小区間「１／９≦ｘ＜２／９」に対する出力範囲「（１／９）＾（１／２）≦ｙ＜（２／９）＾（１／２）」、小区間「２／９≦ｘ＜１／３」に対する出力範囲「（２／９）＾（１／２）≦ｙ＜（１／３）＾（１／２）」である。
【００７７】
過大近似後の指令２４ｃは、小区間「１≦ｘ＜１０／９」に対する出力範囲「１≦ｙ＜（１０／９）＾（１／２）」、小区間「１０／９≦ｘ＜１１／９」に対する出力範囲「（１０／９）＾（１／２）≦ｙ＜（１１／９）＾（１／２）」、小区間「１１／９≦ｘ＜４／３」に対する出力範囲「（１１／９）＾（１／２）≦ｙ＜（４／３）＾（１／２）」である。
【００７８】
図１０（ｂ）には、３回目のステップＳ３の結果が図示されている。入力ｐ１＝０．１、入力ｐ２＝１の値は、ＳＡＴソルバ等が、ｐ１、ｐ２の取り得る範囲[０、１]で割り当てた値である。
【００７９】
２４ａの出力＝０．３は、ＳＡＴソルバ等が、図１０（ａ）に示す過大近似後の指令２４ａを満たす範囲で割り当てた値である。すなわち、２４ａに対する入力ｘ（＝入力ｐ１）は、０．１であるから、０≦０．１＜１／９より、ＳＡＴソルバ等は、０≦ｙ＜（１／９）＾（１／２）≒０．３３を満たすｙの値を、２４ａの出力として割り当てる。
【００８０】
２２ｂの出力＝１．３は、ＳＡＴソルバ等が、指令２２ｂの演算を実行することによって得られる値である。すなわち、２２ｂに対する２つの入力（２４ａの出力と入力ｐ２）は、０．３と１であるから、０．３＋１の演算結果を、２２ｂの出力として割り当てる。
【００８１】
２４ｃの出力（＝ｒ）＝１．１２は、ＳＡＴソルバ等が、図１０（ａ）に示す過大近似後の指令２４ｃを満たす範囲で割り当てた値である。すなわち、２４ｃに対する入力ｘ（＝２２ｂの出力）は、１．３であるから、１１／９≦１．３＜４／３より、ＳＡＴソルバ等は、（１１／９）＾（１／２）≒１．１１≦ｙ＜（４／３）＾（１／２）≒１．１５を満たすｙの値を、２４ｃの出力として割り当てる。
【００８２】
図１０（ｂ）の時点では、ステップ３の結果、充足可能性問題の解として、入力（ｐ１、ｐ２）＝（０．１、１）、出力ｒ＝１．１２が得られたことになる。制御部１１は、充足可能性問題が充足可能と判断し（ステップＳ４のＹｅｓ）、ステップＳ５の処理を実行する。
【００８３】
図１０（ｃ）には、３回目のステップＳ５、Ｓ６の結果が図示されている。入力ｐ１＝０．１、入力ｐ２＝１の値は、充足可能性問題の解における入力である。制御部１１は、これらの値を過大近似前の対象プログラム２０に入力する。
【００８４】
２２ａの出力＝０．３２は、０．１＾（１／２）の演算結果である。２２ｂの出力＝１．３２は、０．３２＋１の演算結果である。２２ｃの出力（＝ｒ）＝１．１５は、１．３２＾（１／２）の演算結果である。ｒ＝１．１５は、ｒ∈［１．１、１．２］を満たすことから、検証内容２１の真の反例である。従って、ステップＳ６の判定結果は真の反例（ステップＳ６のＮｏ）となる。そして、制御部１１は、入力（ｐ１、ｐ２）＝（０．１、１）、出力ｒ＝１．１５を、真の反例として出力し（ステップＳ１１）、処理を終了する。
【００８５】
以上の通り、本発明の実施の形態におけるモデル検査装置１によれば、対象プログラムに複雑な演算が含まれる場合であっても、ＳＡＴソルバ又はＳＭＴソルバに基づくモデル検査を短時間に実行することができる。
【００８６】
前述の説明に挙げた例では、複雑な演算（過大近似対象の指令）の中身が明らか（ホワイトボックス）であったが、複雑な演算の中身が不明（ブラックボックス）の場合も、過大近似さえできれば、本発明を適用することができる。例えば、演算が単調、かつ、入力に対する出力がサンプリングできる場合、過大近似が可能になるため、本発明を適用することができる。
【００８７】
また、前述の説明に挙げた例では、複雑な演算（過大近似対象の指令）に対する入力が１つであったが、２つ以上の入力がある場合も、本発明を適用することができる。例えば、入力（ｘ１、ｘ２）、出力ｙの演算に対しては、「０≦ｘ１＜１かつ２≦ｘ２＜３＝＞０．５≦ｙ＜１．２」のように過大近似すれば良い。
【００８８】
また、効率的な過大近似のルールを求めるため、機械学習などの既存の手法を利用しても良い。例えば、複雑な演算（過大近似対象の指令）に対するサンプリングデータを収集し、機械学習を実行し、過大近似のルールを求めても良い。
【００８９】
また、対象プログラムの中に、ブール演算などＳＡＴソルバ等による取扱いが容易な演算（指令）は、過大近似対象とする必要はない。すなわち、対象プログラムの中に、ブール演算と複雑な演算が混在する場合、複雑な演算のみ過大近似対象とすれば良い。
【００９０】
以上は、モデル検査装置１について説明したが、同様の技術的思想が、ＳＡＴソルバ又はＳＭＴソルバを用いて対象プログラムのテストデータを生成するテストデータ生成装置としても適用することができる。
【００９１】
但し、テストデータ生成装置の場合、複雑な演算を必ずしも厳密に過大近似する必要はない。これは、テストデータ生成装置の場合、テストデータとして真の反例を出力（ステップＳ１１）すれば良いからである。言い換えると、反例なしを出力しても（ステップＳ１２）、真の反例を出力するまで実行することになり、充足可能性問題が充足不可能であることを厳密に保証する必要がないからである。尚、モデル検査装置の場合、充足可能性問題が充足不可能であることを厳密に保証する必要があるため、複雑な演算を厳密に過大近似する必要がある。
【００９２】
従って、テストデータ生成装置は、少なくとも以下の構成を具備すれば良い。
・対象プログラムに含まれる一部又は全部のコンピュータに対する指令を近似する手段
・近似後の指令と検証内容を制約式として含む充足可能性問題が充足可能の場合、充足可能性問題の解における入力を近似前の対象プログラムに入力し、解が検証内容に対する偽反例か否かを判定する手段
・解が偽反例の場合、充足可能性問題の求解時に割り当てられた入力を含むことを条件として、指令に対する入力範囲を縮小する手段
・縮小後の入力範囲内で指令を再度近似する手段
【００９３】
更に、テストデータ生成装置は、以下の構成を具備しても良い。
・充足可能性問題が充足不可能の場合、現在の入力範囲が初期の入力範囲と同一でなければ、初期の入力範囲内であることを条件として、入力範囲を拡大する手段
【００９４】
近似する手段は、例えば、入力範囲を複数の小区間に分割し、小区間ごとに指令に対する出力範囲を決定することによって、指令を近似する。また、再度近似する手段は、例えば、縮小後の入力範囲を小区間に分割し、小区間ごとに出力範囲を決定することによって、指令を再度近似する。
【００９５】
以上の通り、本発明の実施の形態におけるテストデータ生成装置によれば、対象プログラムに複雑な演算が含まれる場合であっても、ＳＡＴソルバ又はＳＭＴソルバに基づくテストデータ生成を短時間に実行することができる。
【００９６】
以上、添付図面を参照しながら、本発明に係るモデル検査装置等やテストデータ生成装置等の好適な実施形態について説明したが、本発明はかかる例に限定されない。当業者であれば、本願で開示した技術的思想の範疇内において、各種の変更例又は修正例に想到し得ることは明らかであり、それらについても当然に本発明の技術的範囲に属するものと了解される。
【符号の説明】
【００９７】
１………モデル検査装置
２０………対象プログラム
２１………検証内容
２２ａ、２２ｃ………過大近似対象の指令
２２ｂ………指令
２３………初期入力範囲
２４ａ、２４ｃ………過大近似後の指令
【図１】
2015022515.tif 000003
【図２】
2015022515.tif 000004
【図３】
2015022515.tif 000005
【図４】
2015022515.tif 000006
【図５】
2015022515.tif 000007
【図６】
2015022515.tif 000008
【図７】
2015022515.tif 000009
【図８】
2015022515.tif 000010
【図９】
2015022515.tif 000011
【図１０】
2015022515.tif 000012