(57)【要約】【課題】モデル検査法により正例を得るための特別な条件の記述がない形式手法による仕様であっても、事前条件の修正を簡単に行うこと。【解決手段】複数の処理に含まれるそれぞれの処理の処理内容の記述を含む形式仕様データの検査結果として、複数の処理に課される制約への違反を見つけた場合に、処理の開始状態から前記制約に違反する状態までの遷移列と各状態における変数の値との集まりである反例に基づいて、制約に違反する状態において前記制約への違反が起きた条件である違反条件を生成し、形式仕様データと違反条件とに基づいて、処理の開始状態における、処理の実行後に前記制約への違反が起こる条件としての違反発生最弱事前条件と、当該処理の実行後に前記制約への違反が起きない条件としての違反防止事前条件とを生成する。【選択図】  図１
2014160435.tif 000002
【特許請求の範囲】
【請求項１】
複数の処理に含まれるそれぞれの前記処理の処理内容の記述を含む形式仕様データの検査結果として、前記複数の処理に課される制約への違反を見つけた場合に、処理の開始状態から前記制約に違反する状態までの遷移列と各状態における変数の値との集まりである反例に基づいて、前記制約に違反する状態において前記制約への違反が起きた条件である違反条件を生成する違反条件生成手段と、
前記形式仕様データと前記違反条件とに基づいて、処理の開始状態における、処理の実行後に前記制約への違反が起こる条件としての違反発生最弱事前条件と、当該処理の実行後に前記制約への違反が起きない条件としての違反防止事前条件とを生成する事前条件生成手段と、
を備える情報処理装置。
【請求項２】
前記違反条件生成手段は、前記形式仕様データの制約のうち前記反例において偽となった制約をＡＮＤ／ＯＲグラフとして表現し、前記反例において制約への違反を起こした状態における変数を用いて、前記ＡＮＤ／ＯＲグラフで偽となるノードを計算し、偽となるノードだけで構成される新たなＡＮＤ／ＯＲグラフを生成し、生成された前記新たなＡＮＤ／ＯＲグラフを論理式として表現した論理式の否定形として、違反条件を生成する請求項１に記載の情報処理装置。
【請求項３】
前記事前条件生成手段は、前記違反条件と、前記形式仕様データに含まれる処理の実行内容のうち、処理の開始状態から違反を起こした状態までの実行内容とから、処理の開始状態においてその処理の実行後に前記制約への違反が起こるならば真となる条件である違反発生最弱事前条件を生成する請求項１または２に記載の情報処理装置。
【請求項４】
前記事前条件生成手段は、前記処理の実行後に前記制約への違反が起きないならば真となる条件である違反防止事前条件を、前記違反発生最弱事前条件の否定形として生成する請求項１乃至３のいずれか１項に記載の情報処理装置。
【請求項５】
前記形式仕様データを読み込む読込処理手段と、
読み込んだ前記形式仕様を入力としてモデル検査を行い制約への前記反例を出力するモデル検査実行手段と、
をさらに備え、
前記違反条件生成手段は、前記形式仕様データの検査結果の前記反例に基づいて、前記違反条件を生成する請求項１乃至４のいずれか１項に記載の情報処理装置。
【請求項６】
前記形式仕様データは、さらに、前記処理の開始状態の制約を記述した事前条件と前記処理の実行後の制約を記述した事後条件とを含む請求項１乃至５のいずれか１項に記載の情報処理装置。
【請求項７】
前記事前条件生成手段により生成された前記違反防止事前条件あるいは前記違反発生最弱事前条件を出力する出力処理手段を、さらに備える請求項１乃至６のいずれか１項に記載の情報処理装置。
【請求項８】
複数の処理に含まれるそれぞれの前記処理の処理内容の記述を含む形式仕様データの検査結果として、前記複数の処理に課される制約への違反を見つけた場合に、処理の開始状態から前記制約に違反する状態までの遷移列と各状態における変数の値との集まりである反例に基づいて、前記制約に違反する状態において前記制約への違反が起きた条件である違反条件を生成する違反条件生成ステップと、
前記形式仕様データと前記違反条件とに基づいて、処理の開始状態における、処理の実行後に前記制約への違反が起こる条件としての違反発生最弱事前条件と、当該処理の実行後に前記制約への違反が起きない条件としての違反防止事前条件とを生成する事前条件生成ステップと、
を含む情報処理方法。
【請求項９】
複数の処理に含まれるそれぞれの前記処理の処理内容の記述を含む形式仕様データの検査結果として、前記複数の処理に課される制約への違反を見つけた場合に、処理の開始状態から前記制約に違反する状態までの遷移列と各状態における変数の値との集まりである反例に基づいて、前記制約に違反する状態において前記制約への違反が起きた条件である違反条件を生成する違反条件生成ステップと、
前記形式仕様データと前記違反条件とに基づいて、処理の開始状態における、処理の実行後に前記制約への違反が起こる条件としての違反発生最弱事前条件と、当該処理の実行後に前記制約への違反が起きない条件としての違反防止事前条件とを生成する事前条件生成ステップと、
をコンピュータに実行させる情報処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、モデル検査手法における形式仕様データを生成するための技術に関する。
【背景技術】
【０００２】
上記技術分野においては、処理の仕様を、不変条件と、事前条件と、その処理が行う実行内容と、事後条件として記述する。不変条件とは、システムによって常に満たされるべき制約すなわち複数の処理に課される共通の制約である。事前条件とは、システムが行う処理について、その処理の実行前に満たされているべき制約である。事後条件とは、その処理が実行後に満たすべき制約である。このように記述された仕様では、システムの分析設計段階で仕様を仮想的に動作させることができ、モデル検査法といった既存の検証手法を用いて、制約が守られているかどうかを検証できる。制約違反があれば仕様を修正する。
【０００３】
特許文献１には、モデル検査法で得られる反例（制約違反の起こる例）と、反例に対応する正例（制約違反の起こらない例）との双方の情報を用いて、事前条件を修正する技術が開示されている。ここで、特許文献１においては、事前条件が真で事後条件が偽となったイベントに係るプロパティの、初期状態から修正対象プロパティに係るイベントに到るまでに駆動された全イベントを特定する情報を含む状態遷移列を、反例とする。一方、修正対象プロパティに係るイベントと同一のイベントのうち、事前条件と事後条件とが共に真となったイベントを特定し、初期状態から特定されたイベントに到るまでに駆動された全イベントを特定する情報を含む状態遷移列を、反例に対する正例とする。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１０−２８２２５７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記文献に記載の技術は、容易に得られる反例に対応する正例を得て使用する技術であり、制約が成り立たないような状態遷移列が１つもないといった、制約に違反しない正例を使用するものではない。なぜなら、一般に形式手法による仕様では、成立すべきこととして事前条件、事後条件、不変条件といった制約を記述するので、制約が成り立たないような状態遷移列が１つもないといった、制約に違反しない正例を得るための特別な条件を記述しない。そのため、モデル検査を用いたシステムの検証においては、システムの振る舞いが制約に違反する反例は容易に得ることできるが、制約に違反しない正例を得ることは、一般に難しいからである。このように、正例を得るための特別な条件の記述を含まない形式手法による仕様では、上記文献に記載の技術のように、制約違反の起こった反例に対応する正例からでは事前条件の修正を簡単に行うことができなかった。
【０００６】
本発明の目的は、上述の課題を解決する技術を提供することにある。
【課題を解決するための手段】
【０００７】
上記目的を達成するため、本発明に係る情報処理装置は、
複数の処理に含まれるそれぞれの前記処理の処理内容の記述を含む形式仕様データの検査結果として、前記複数の処理に課される制約への違反を見つけた場合に、処理の開始状態から前記制約に違反する状態までの遷移列と各状態における変数の値との集まりである反例に基づいて、前記制約に違反する状態において前記制約への違反が起きた条件である違反条件を生成する違反条件生成手段と、
前記形式仕様データと前記違反条件とに基づいて、処理の開始状態における、処理の実行後に前記制約への違反が起こる条件としての違反発生最弱事前条件と、当該処理の実行後に前記制約への違反が起きない条件としての違反防止事前条件とを生成する事前条件生成手段と、
を備える。
【０００８】
上記目的を達成するため、本発明に係る情報処理方法は、
複数の処理に含まれるそれぞれの前記処理の処理内容の記述を含む形式仕様データの検査結果として、前記複数の処理に課される制約への違反を見つけた場合に、処理の開始状態から前記制約に違反する状態までの遷移列と各状態における変数の値との集まりである反例に基づいて、前記制約に違反する状態において前記制約への違反が起きた条件である違反条件を生成する違反条件生成ステップと、
前記形式仕様データと前記違反条件とに基づいて、処理の開始状態における、処理の実行後に前記制約への違反が起こる条件としての違反発生最弱事前条件と、当該処理の実行後に前記制約への違反が起きない条件としての違反防止事前条件とを生成する事前条件生成ステップと、
を含む。
【０００９】
上記目的を達成するため、本発明に係る情報処理プログラムは、
複数の処理に含まれるそれぞれの前記処理の処理内容の記述を含む形式仕様データの検査結果として、前記複数の処理に課される制約への違反を見つけた場合に、処理の開始状態から前記制約に違反する状態までの遷移列と各状態における変数の値との集まりである反例に基づいて、前記制約に違反する状態において前記制約への違反が起きた条件である違反条件を生成する違反条件生成ステップと、
前記形式仕様データと前記違反条件とに基づいて、処理の開始状態における、処理の実行後に前記制約への違反が起こる条件としての違反発生最弱事前条件と、当該処理の実行後に前記制約への違反が起きない条件としての違反防止事前条件とを生成する事前条件生成ステップと、
をコンピュータに実行させる。
【発明の効果】
【００１０】
本発明によれば、モデル検査法により正例を得るための特別な条件の記述がない形式手法による仕様であっても、事前条件の修正を簡単に行うことができる。
【図面の簡単な説明】
【００１１】
【図１】本発明の第１実施形態に係る情報処理装置の構成を示すブロック図である。
【図２】本発明の第２実施形態に係る情報処理装置の機能構成を示すブロック図である。
【図３】本発明の第２実施形態に係る情報処理装置の処理手順を示すフローチャートである。
【図４】本発明の第２実施形態に係る形式仕様データとモデル検査法の反例とから違反条件を生成する方法を模式化した模式図である。
【図５】本発明の第２実施形態に係る違反条件から制約への違反を起こさないようにするための違反防止事前条件を生成する際に用いる規則を例示する図である。
【図６】本発明の第２実施形態に係る情報処理装置のハードウェア構成を示すブロック図である。
【図７Ａ】本発明の第３実施形態に係る処理における遷移を示す遷移図である。
【図７Ｂ】本発明の第３実施形態に係る処理における形式仕様データを例示する図である。
【図８】本発明の第３実施形態に係る処理におけるモデル検査による反例を例示する図である。
【図９】本発明の第３実施形態に係る処理における形式仕様データとモデル検査法の反例とから違反条件を生成する手順を例示する図である。
【図１０】本発明の第３実施形態に係る処理における違反条件から違反発生最弱事前条件と違反防止事前条件とを生成する手順を例示する図である。
【図１１】本発明の第３実施形態に係る処理における違反防止事前条件を用いて修正された形式仕様データを例示する図である。
【図１２】本発明の第４実施形態に係る処理における遷移を示す遷移図である。
【図１３】本発明の第４実施形態に係る処理における形式仕様データを例示する図である。
【図１４】本発明の第４実施形態に係る処理におけるモデル検査による反例を例示する図である。
【図１５】本発明の第４実施形態に係る処理における形式仕様データとモデル検査法の反例とから違反条件を生成する手順を例示する図である。
【図１６】本発明の第４実施形態に係る処理における違反条件から違反発生最弱事前条件と違反防止事前条件とを生成する手順を例示する図である。
【図１７】本発明の第４実施形態に係る処理における違反防止事前条件を用いて修正された形式仕様データを例示する図である。
【図１８】本発明の第５実施形態に係る処理における遷移を示す遷移図である。
【図１９】本発明の第５実施形態に係る処理における形式仕様データを例示する図である。
【図２０】本発明の第５実施形態に係る処理におけるモデル検査による反例を例示する図である。
【図２１】本発明の第５実施形態に係る処理における形式仕様データとモデル検査法の反例とから違反条件を生成する手順を例示する図である。
【図２２】本発明の第５実施形態に係る処理における違反条件から違反発生最弱事前条件と違反防止事前条件とを生成する手順を例示する図である。
【図２３】本発明の第５実施形態に係る処理における違反防止事前条件を用いて修正された形式仕様データを例示する図である。
【図２４】本発明の第６実施形態に係る情報処理装置の機能構成を示すブロック図である。
【図２５】本発明の第６実施形態に係る情報処理装置の処理手順を示すフローチャートである。
【発明を実施するための形態】
【００１２】
以下に、図面を参照して、本発明の実施の形態について例示的に詳しく説明する。ただし、以下の実施の形態に記載されている構成要素はあくまで例示であり、本発明の技術範囲をそれらのみに限定する趣旨のものではない。
【００１３】
［第１実施形態］
本発明の第１実施形態としての情報処理装置１００について、図１を用いて説明する。情報処理装置１００は、モデル検査手法における形式仕様データを生成する装置である。
【００１４】
図１に示すように、情報処理装置１００は、違反条件生成部１１０と、事前条件生成部１２０と、を含む。違反条件生成部１１０は、複数の処理に含まれるそれぞれの処理の処理内容の記述を含む形式仕様データの検査結果として、複数の処理に課される制約への違反を見つけた場合に、次の処理をする。すなわち、処理の開始状態から制約に違反する状態までの遷移列と各状態における変数の値との集まりである反例に基づいて、制約に違反する状態において制約への違反が起きた条件である違反条件１１１を生成する。事前条件生成部１２０は、形式仕様データと違反条件１１１とに基づいて、処理の開始状態における、処理の実行後に制約への違反が起こる条件としての違反発生最弱事前条件１２１と、処理の実行後に制約への違反が起きない条件としての違反防止事前条件１２２とを生成する。
【００１５】
本発明によれば、モデル検査法により得られる反例だけから、制約への違反が起きたことを示す違反条件を生成し、違反条件から制約への違反を起こさないようにするための事前条件を生成する。したがって、モデル検査法により正例を得るための特別な条件の記述がない形式手法による仕様であっても、事前条件の修正を簡単に行うことができる。
【００１６】
［第２実施形態］
次に、本発明の第２実施形態に係る情報処理装置について説明する。本実施形態の事前条件生成装置としての情報処理装置は、システムを記述した形式仕様データに基づいてモデル検査を実行し、制約に違反する状態までの遷移列と各状態における変数の値との集まりである反例を得る。この反例と形式仕様データとに基づいて、制約に違反する状態において制約への違反が起きた条件である違反条件を生成する。次に、処理の実行後に制約への違反が起こる条件としての違反発生最弱事前条件と、処理の実行後に制約への違反が起きない条件としての違反防止事前条件とを生成する。そして、違反防止事前条件により形式仕様データの事前条件を更新する。
【００１７】
本実施形態によれば、モデル検査法により得られる反例だけから、制約への違反が起きたことを示す違反条件を生成し、違反条件から制約への違反を起こさないようにするための違反防止事前条件を生成する。したがって、モデル検査法により正例を得るための特別な条件の記述がない形式手法による仕様であっても、事前条件の修正を容易に行うことができる。
【００１８】
《本実施形態の基礎技術》
近年、システム開発に、いわゆる形式手法を採用することが多くなってきている。形式手法とは、数学的な概念に基づき、対象システムを正確で曖昧さのない記法で表現する手法である。具体的には、主に集合と集合や集合の要素同士の関係とを用いて対象システムが扱うデータを表現する。対象システムが行う処理は、複数の集合や関係に要素を追加したり削除したりする代入文の列として表現する。そして、処理の前後で成り立つべき、または成り立つべきではないという制約を論理命題の形で表明する。制約には不変条件と事前条件と事後条件がある。不変条件はシステムにおいて常に成り立つべき条件である。全ての処理には、その処理の実行後に不変条件を成立させることが課される。事前条件と事後条件はシステムが行う処理ごとの表明である。ある処理に着目すると、その処理を実行する側の処理には、着目した処理の実行直前に不変条件と着目した処理の事前条件を成立させることが課される。また、着目した処理には処理の実行後にその処理の事後条件を成立させることが課される。モデル検査法を用いると、形式手法による仕様を読み込んで、システムに仕様に相当する有限状態遷移グラフ上の状態遷移列を網羅的に探索して制約への違反を検出できる。
【００１９】
ここで、モデル検査法は、与えられた有限状態遷移グラフと検証したい条件（プロパティ）について、有限状態遷移グラフ上の状態遷移列（経路、パス）を網羅的に探索して、プロパティが成立するかどうかを調べる手法である。モデル検査法では、プロパティが成立しない（プロパティ違反）場合には探索の開始状態からプロパティ違反となった状態までの状態遷移列とこの状態遷移列上の各状態の情報の集まりである反例が出力される。
システムの状態はシステムのもつデータすなわちシステム内の変数の値の組合せで決まる。システムの処理が変数の値を変更することは、その変数について変更前の値の状態から変更後の値の状態へと遷移が起こることであると考えて、システムの仕様に相当する有限状態遷移グラフを作ることができる。検証したい条件としては、各処理の実行前に不変条件とその処理の事前条件が成立することと各処理の実行後に不変条件とその処理の事後条件が成立することが上げられる。この考え方に則ってモデル検査法を適用すると、システムに相当する有限状態遷移グラフ上で不変条件が成立する状態から網羅探索を開始して処理の実行内容に相当する状態遷移を辿ることができる。そして、各処理の実行前後の状態において不変条件、事前条件、事後条件といった制約が守られているかどうかを調べることができる。制約が守られていないという制約違反が起きた場合には、探索の開始状態から制約違反の発生した状態までの状態遷移列とその状態遷移列上の各状態における変数およびその値の集まりである反例を得ることができる。
【００２０】
制約違反が検出された場合、違反を起こさないように仕様を修正する必要がある。多くの場合、事前条件を修正することが多い。なぜなら、不変条件は個々の処理とは独立であることから処理に関する修正の対象とはなりにくいからである。また、事後条件は設計者が仕様として記述している処理の実行内容と密接に関係しており、設計者にとって考えつきやすいからである。これに対して、事前条件は設計中の処理とは直接には関係していない他の処理の実行結果として得られるデータベースの状態や内部メモリの状態などが関係することがあり、設計者にとって考え付きにくいからである。
【００２１】
《情報処理装置の機能構成》
図２は、本実施形態に係る情報処理装置２１０の機能構成を示すブロック図である。
【００２２】
図２を参照すると、本実施形態の事前条件生成装置としての情報処理装置２１０は、機能的には、例えば、読込処理部２１１と、モデル検査実行部２１２と、違反条件生成部２１３と、事前条件生成部２１４と、出力処理部２１５と、を有する。
【００２３】
ここで、情報処理装置２１０は、物理的には、例えばＣＰＵ（Central Processing Unit）と、記憶部と、入出力インタフェースとを含む。記憶部は、例えば、ＣＰＵで処理されるプログラムおよびデータを記憶するＲＯＭ（Read Only Memory）やＨＤＤ（Hard Disk Drive）、主として制御処理のための各種作業領域として使用するＲＡＭ（Random Access Memory）等を含む。これらの要素は、互いにバスを介して接続される。ＣＰＵが、ＲＯＭやＨＤＤに記憶されたプログラムを実行し、入出力インタフェースを介して受信されるメッセージや、入力部から入力されるデータ、ＲＡＭに展開されるデータ等を処理することで、図２に示す情報処理装置２１０の各機能部を実現する（図６参照）。
【００２４】
図２に示す読込処理部２１１は、形式仕様データＤＢ（Data Base）２２０から形式仕様データを読み込む。形式仕様データは、形式手法における形式記述言語を用いてシステムの仕様を表現することで生成される。この形式仕様データは、不変条件および処理内容を含む。不変条件は、複数の処理に課される共通の制約を記述したデータである。処理内容は、処理する内容を処理ごとに記述したデータであり、その処理を実行する処理に課される制約である事前条件と、その処理の実行内容である実行文の列と、その処理に課される制約である事後条件と、をデータとして含む。これらの制約には、不変条件および事前条件の成立を前提として、全ての実行文を実行した後に、不変条件および事後条件が成立すべき、という関係がある。
【００２５】
図２に示すモデル検査実行部２１２は、読込処理部２１１により読み込まれた形式仕様データに含まれる処理にもとづいて、有限状態遷移グラフを作成し、不変条件などの制約が成立するようにグラフ上を網羅探索する。そして、制約が成立しない状態に到達することがあれば、制約への反例として、探索の開始状態から制約が成立しない状態までの状態遷移列および各状態における変数の値を出力する。
【００２６】
図２に示す違反条件生成部２１３は、読込処理部２１１により読み込んだ形式仕様データとモデル検査実行部２１２により出力された反例とを用いて違反条件を生成する。ここで、違反条件は、ある処理が他の処理を呼び出す際に不変条件または他の処理の事前条件が成立しないこと、あるいは、ある処理の実行後に不変条件またはその処理の事後条件が成立しないことを示す十分条件である。
【００２７】
図２に示す事前条件生成部２１４は、読込処理部２１１により読み込んだ形式仕様データと違反条件生成部２１３とにより生成された違反条件とを用いて、ある処理の事前条件として、違反発生最弱事前条件と違反防止事前条件とを生成する。ここで、違反発生最弱事前条件とは、その処理の実行後に違反条件が真となるような条件である。また、違反防止事前条件とは、処理の実行後に違反条件が偽となる条件である。
【００２８】
図２に示す出力処理部２１５は、事前条件生成部２１４により生成された違反防止事前条件を違反防止事前条件ＤＢ２３０に出力する。なお、出力処理部２１５は、違反防止事前条件を、プリンタに出力して印刷させてもよいし、表示装置に出力して表示させてもよい。また、出力処理部２１５は、違反防止事前条件の代わりに違反発生最弱事前条件を出力してもよいし、違反発生最弱事前条件と違反防止事前条件との区別がつくような情報を付加して、双方を出力してもよい。
【００２９】
《情報処理装置の処理手順》
図３は、本実施形態に係る情報処理装置２１０の処理手順を示すフローチャートである。
【００３０】
最初に、読込処理部２１１は、形式仕様データＤＢ２２０から形式仕様データを読み込む（ステップＳ３０１）。続いて、モデル検査実行部２１２は、ステップＳ３０１において読み込まれた形式仕様データを有限状態遷移グラフに変換する。そして、不変条件とある処理の事前条件とが成立する状態を起点として、その処理の実行文に応じた状態遷移を選択して次の状態に移る。選択しうる状態遷移がなければ、状態遷移を戻って前の状態において別の状態に遷移するという探索手続きを繰り返し行う。この探索の過程で制約が成立しない状態に到達すれば、反例として開始状態から制約違反の状態までの状態遷移列と各状態における変数の値とを出力する（ステップＳ３０３）。
【００３１】
違反条件生成部２１３は、ステップＳ３０３の処理の結果、反例があるか否かで分岐する（ステップＳ３０５）。出力された反例があれば、次のステップＳ３０７に進み、なければ動作全体を終了する。続いて、違反条件生成部２１３は、ステップＳ３０１において読み込まれた形式仕様データと、ステップＳ３０３において出力された反例とを基に、図４で例示した手順に沿って、違反条件を生成する（ステップＳ３０７）。
【００３２】
事前条件生成部２１４は、図５に示した規則を用いて、ステップＳ３０１において読み込まれた形式仕様データと、ステップＳ３０７において生成された違反条件とを基に、処理の事前条件として違反発生最弱事前条件を生成する（Ｓ３０９）。また、事前条件生成部２１４は、違反発生最弱事前条件の否定形である違反防止事前条件を生成する（ステップＳ３１１）。
【００３３】
出力処理部２１５は、ステップＳ３１１で生成された違反防止事前条件を出力する（ステップＳ３１３）。
【００３４】
（違反条件を生成する模式図）
図４は、本実施形態に係る形式仕様データとモデル検査法の反例とから違反条件を生成する手順４００を模式化した模式図である。図４においては、論理式「（Ａ ＡＮＤ Ｂ）ＯＲ（Ｃ ＡＮＤ Ｄ）」がＡおよびＣが偽であるために成立しない場合について、違反条件を生成する手順を説明する。なお、図４の手順は、他の論理式から違反条件を生成するために適用可能であり、以下の第３実施形態乃至第５実施形態に示す具体例からも明白である。
【００３５】
（１：Ｓ４０１）まず、違反条件生成部２１３は、論理式全体からＡＮＤ／ＯＲグラフを作成する。ＡＮＤ／ＯＲグラフは積を表す論理演算子ＡＮＤおよび和を表す論理演算子ＯＲをそれぞれＡＮＤ分岐およびＯＲ分岐として、論理式を木構造で表現した図式である。木構造のある分岐に着目したときに分岐元と分岐先とをそれぞれ上位ノードと下位ノードと呼ぶ。ＡＮＤ分岐をもつ上位ノードの値は全ての下位ノードの値について論理積をとった値であり、ＯＲ分岐をもつ上位ノードの値は全ての下位ノードの値について論理和をとった値である。また、上位ノードをもたないノードと下位ノードをもたないノードをそれぞれルートノードとリーフノードと呼ぶ。ルートノードは論理式全体にあたり、リーフノードは論理式のうちＡＮＤおよびＯＲ演算子を含まない部分論理式にあたる。論理式（Ａ ＡＮＤ Ｂ）ＯＲ（Ｃ ＡＮＤ Ｄ）は、ＯＲ分岐をもつルートノードと、ルートノードからの分岐先でありＡＮＤ分岐をもつ２つのノードと、それらのＡＮＤ分岐の先として部分論理式Ａ、Ｂ、Ｃ、Ｄにあたる４つのリーフノードからなるＡＮＤ／ＯＲグラフとなる。
【００３６】
（２）次に、違反条件生成部２１３は、部分論理式の値が偽であるリーフノードを特定し、偽であることをノードに印づける。
【００３７】
（３）さらに、違反条件生成部２１３は、下位ノードの値から上位ノードの値を計算し、値が偽となるノードを印づける。
【００３８】
（４）全てのノードについて値の計算が終えると、違反条件生成部２１３は、値が真であるノードとそのノードが接続している分岐と分岐先のノード群をＡＮＤ／ＯＲグラフから削除する。
【００３９】
（５）最後に、違反条件生成部２１３は、削除を行った後のＡＮＤ／ＯＲグラフにおいて、下位ノードが１つだけのノードをその下位ノードで置き換える。そして、置換を行った後のＡＮＤ／ＯＲグラフを論理式「Ａ ＯＲ Ｃ」として表現し、その否定形である「ＮＯＴ（Ａ ＯＲ Ｃ）」を違反条件とする。違反条件「ＮＯＴ（Ａ ＯＲ Ｃ）」の値は、部分論理式ＡとＣがそれぞれ偽である場合にのみ真となり、それ以外の場合には偽となる。
【００４０】
（違反防止事前条件を生成する際に用いる規則）
図５は、本実施形態に係る違反条件から、制約への違反を起こさないようにするための違反防止事前条件を生成する際に用いる規則を例示する図である。図５は、規則５１０と、その規則５１０に出現する記号の表わす内容一覧５２０と、を示す。なお、図５は、本実施形態における基本的な規則であり、広く処理システムのモデル検査手法に対して汎用的に使用できる。
【００４１】
図５の規則５１０を参照して、違反防止事前条件を生成する手順を説明する。まず、事前条件生成部２１４は、規則ａを用いて、ある処理の事前条件としてその処理の実行後に違反条件とが真となるような、最も弱い条件である違反発生最弱事前条件を表す論理式を作る。
【００４２】
そして、最弱事前条件を得るための述語変換子ｗｐについて、第１引数を規則ｂからｄまでを用いてＡＮＤおよびＯＲ演算子を含まない部分論理式になるまで分解する。次に、第２引数を規則ｅとｆとを用いて代入文になるまで分解し、規則ｇを用いてｗｐを含まない論理式に変換して、違反発生最弱事前条件を得る。
【００４３】
そして、事前条件生成部２１４は、規則ｈを用いて、違反発生最弱事前条件から違反防止事前条件を得る。違反発生最弱事前条件が成り立つ場合に、処理を実行すると違反条件に関連する制約は必ず成立しなくなる。違反発生最弱事前条件の否定である違反防止事前条件が成り立つ場合には、処理を実行すると違反条件は成立せず、この違反条件に起因する制約違反は起きない。
【００４４】
《情報処理装置のハードウェア構成》
図６は、本実施形態に係る情報処理装置２１０のハードウェア構成を示すブロック図である。
【００４５】
図６で、ＣＰＵ６１０は演算制御用のプロセッサであり、ＣＰＵ６１０がＲＡＭ６４０を使用しながらストレージ６５０に格納されたプログラムおよびモジュールを実行することで、図２に示された情報処理装置２１０の各機能構成部の機能が実現される。ＲＯＭ６２０は、初期データおよびプログラムなどの固定データおよびプログラムを記憶する。また、通信制御部６３０は、ネットワークを介して外部装置と通信する。なお、ＣＰＵ６１０は１つに限定されず、複数のＣＰＵであっても、あるいは画像処理用のＧＰＵを含んでもよい。
【００４６】
ＲＡＭ６４０は、ＣＰＵ６１０が一時記憶のワークエリアとして使用するランダムアクセスメモリである。ＲＡＭ６４０には、本実施形態の実現に必要なデータを記憶する領域が確保されている。形式仕様データ６４１は、形式仕様データＤＢ２２０から読み込まれたシミュレーション対象の形式仕様データである。反例データ６４２は、形式仕様データ６４１に基づいてモデル検査を実行して得られた反例データである。違反条件６４３は、形式仕様データ６４１と反例データ６４２とから、図４の違反条件を得る方法に従って生成された違反条件である。違反発生最弱事前条件６４４は、形式仕様データ６４１と違反条件６４３とに基づいて、図５の違反防止事前条件を生成する規則に従って生成された違反発生最弱事前条件である。違反防止事前条件６４５は、違反発生最弱事前条件６４４の否定形として生成した違反防止事前条件である。入出力データ６４６は、入出力インタフェース６６０を介して入出力される入出力データを示す。送受信データ６４７は、通信制御部６３０を介して送受信される送受信データを示す。
【００４７】
ストレージ６５０には、データベースや各種のパラメータ、あるいは本実施形態の実現に必要な以下のデータまたはプログラムが記憶されている。形式仕様データ６５１は、形式仕様データＤＢ２２０から読み込まれた形式仕様データである。モデル検査パラメータ６５２は、本実施形態のモデル検査を実行するために使用される変数を含むパラメータである。状態遷移グラフ６５３は、モデル検査を実行する処理システムにおける状態遷移を表わすグラフである。違反条件生成アルゴリズム６５４は、図４の違反条件を得る方法を記述している。事前条件生成アルゴリズム６５５は、図５の違反発生最弱事前条件と違反防止事前条件とを生成する規則を記述している。
【００４８】
ストレージ６５０には、以下のプログラムが格納される。情報処理装置制御プログラム６５６は、本情報処理装置２１０の全体を制御する制御プログラムである。モデル検査実行モジュール６５７は、情報処理装置制御プログラム６５６において、形式仕様データ６４１とモデル検査パラメータ６５２とを使用してモデル検査を実行し、反例データ６４２を生成するモジュールである。違反条件生成モジュール６５８は、情報処理装置制御プログラム６５６において、違反条件生成アルゴリズム６５４に従い、形式仕様データ６４１と反例データ６４２とから違反条件６４３を生成するモジュールである。事前条件生成モジュール６５９は、情報処理装置制御プログラム６５６において、事前条件生成アルゴリズム６５５に従い、形式仕様データ６４１と違反条件６４３とから違反発生最弱事前条件と違反防止事前条件とを生成するモジュールである。
【００４９】
入出力インタフェース６６０は、入出力機器との入出力データをインタフェースする。入出力インタフェース６６０には、表示部６６１、キーボード、タッチパネル、ポインティンデバイスなどの操作部６６２が接続される。また、スピーカやマイクなどの音声入出力部６６３が接続される。さらに、形式仕様データＤＢ２２０や違反防止事前条件ＤＢ２３０が接続される。なお、形式仕様データＤＢ２２０や違反防止事前条件ＤＢ２３０は、通信制御部６３０によりネットワークを介して接続されていてもよい。
【００５０】
なお、図６のＲＡＭ６４０やストレージ６５０には、情報処理装置２１０が有する汎用の機能や他の実現可能な機能に関連するプログラムやデータは図示されていない。
【００５１】
本実施形態によれば、モデル検査法により得られる反例だけから、制約への違反が起きたことを示す違反条件を生成し、違反条件から制約への違反を起こさないようにするための違反防止事前条件を生成する。したがって、モデル検査法により正例を得るための特別な条件の記述がない形式手法による仕様であっても、事前条件の修正を容易に行うことができる。すなわち、本実施形態における情報処理装置２１０によれば、読込処理部２１１が形式仕様データを読み込み、その形式仕様データとモデル検査実行部２１２がモデル検査法を行って出力した反例とから、形式仕様データを修正するのに必要となる事前条件（違反防止事前条件）を生成することができる。それゆえに、事後条件あるいは不変条件が成り立たないような状態遷移列が１つもないことといった、制約に違反しないという正例を得るための特別な表明を記述しない形式手法による仕様であっても、仕様の検証を簡単に行うことが可能となる。
【００５２】
［第３実施形態］
次に、本発明の第３実施形態に係る情報処理装置の処理について説明する。本実施形態に係る事前条件生成装置としての情報処理装置の処理は、上記第２実施形態の処理を具体的なスピーカの音量制御処理に適用した例である。本実施形態では、スピーカの音量制御処理において、形式仕様データとモデル検査法の反例とから生成した違反条件から、違反発生最弱事前条件と違反防止事前条件とを生成し、違反防止事前条件を用いて修正された形式仕様データを生成する。その他の構成および動作は、第２実施形態と同様であるため、その詳しい説明を省略する。
【００５３】
《処理の遷移図》
図７Ａは、本実施形態に係る処理における遷移７００を示す遷移図である。なお、図７Ａは、単純なスピーカの音量制御処理を示すが、さらに複雑な処理であっても本実施形態を適用できる。
【００５４】
図７Ａの遷移図には、スピーカ音量を１ステップ上げる処理７０１（ｖ：＝ｖ＋１）と、スピーカ音量を１ステップ下げる処理７０２（ｖ：＝ｖ−１）との間で、処理が遷移する様子が示されている。なお、ｖは音量に対応するパラメータであるが、ｖが何であるか、また、１ステップの単位などは本質的でないので、ここでは詳説しない。そして、本例のスピーカの音量制御処理における不変条件７０３は、“０≦ｖ≦１０”と設定するが、これも特殊な条件ではなく他の処理にも汎用的に使用できる。
【００５５】
以下、本実施形態においては、図７Ａの処理の中から、スピーカ音量を１ステップ上げる処理７０１（ｖ：＝ｖ＋１）の事前条件に対して、本実施形態による違反防止事前条件を用いた修正を説明する。
【００５６】
（形式仕様データ）
図７Ｂは、本実施形態に係る処理における形式仕様データ７２０を例示する図である。図７Ｂを参照して、形式仕様データに含まれる不変条件および処理内容について具体的に説明する。
【００５７】
図７Ｂの上部は、不変条件７０３を例示するものであり、スピーカのボリュームの値“ｖ”は０以上かつ１０以下の値であることを不変条件としている。
【００５８】
図７Ｂの下部は、処理内容７１０を例示するものである。処理内容７１０は、次のデータを含む。“スピーカの音量を上げる”という処理に関するデータ７１１、利用者が操作し音量を上げるボタンの状態を示す引数“ｂ”７１２と、“ｂ”の値が“ＯＮ”であるという命題の事前条件７１３と、“ｖ”の値を１だけ加算し、“ｂ”の値を“ＯＦＦ”を代入することを示す実行内容７１４とである。なお、事後条件７１５は設定されていない。また、不変条件、事前条件および事後条件といった制約は命題が設定されていなければ真（Ｔｒｕｅ）であるものとして扱う。
【００５９】
（モデル検査による反例）
図８は、本実施形態に係る処理におけるモデル検査による反例８００を例示する図である。なお、モデル検査による反例は無数存在するが、図８には、その中で最も弱い反例（条件が真から偽に移る境界の反例）が、状態遷移および変数とその値で示されている。
【００６０】
図８は、図７Ａの処理７０１を行う前の状態（事前状態８０１）において、ｖの値は１０でｂの値は“ＯＮ”であり、図７Ａの処理７０１を行った後の状態（事後状態８０２）においてｖの値は１１でｂの値は“ＯＦＦ”であることを、例示的に示している。事後状態８０２ではｖの値が１１であるために、命題ｖ≦１０は偽となり、図７Ａおよび図７Ｂに示した不変条件７０３は成立しない。すなわち、図８は図７Ａおよび図７Ｂに示した不変条件７０３への反例である。
【００６１】
（違反条件の生成）
図９は、本実施形態に係る処理における形式仕様データとモデル検査法の反例とから違反条件を生成する手順９００を例示する図である。図９を参照して、図８に例示した反例８００から違反条件を生成する具体的を説明する。
【００６２】
図９の（１：Ｓ９０１）は、不変条件“０≦ｖ ＡＮＤ ｖ≦１０”を、部分論理式“０≦ｖ”と“ｖ≦１０”のそれぞれにあたるリーフノードと、これらのリーフノードをＡＮＤ分岐で束ねたルートノードからなるＡＮＤ／ＯＲグラフとして表現した例である。
【００６３】
図９の（２：Ｓ９０２）は、各リーフノードについて、その対応する部分論理式がｖの値１１によって偽になる右側のリーフノードを黒塗りで印づけた例である。
【００６４】
図９の（３：Ｓ９０３）は、下位ノードの値から上位ノードの値を計算し、偽になるノードを黒塗りで印づけた例である。左側のリーフノードの値は真であり、右側のリーフノードの値は偽であり、これらをＡＮＤ分岐で束ねたルートノードの値は下位ノードの値の論理積であることから偽であり、黒塗りで印づけられている。
【００６５】
図９の（４：Ｓ９０４）は、値が真となるノードを削除した例であり、図９の（３）におけるルートノードと右側のリーフノードだけがグラフとして残っている。
【００６６】
図９の（５：Ｓ９０５）は、図９の（４）において下位ノードが１つだけのノードをその下位ノードと置換した例であるが（図４参照）、相当するノードがないため、図９の（４）と同じグラフとなっている。図９の（５）のＡＮＤ/ＯＲグラフに相当とする論理式の否定形が、求める違反条件“ＮＯＴ ｖ≦１０”となる。
【００６７】
（違反発生最弱事前条件と違反防止事前条件との生成）
図１０は、本実施形態に係る処理における違反条件から違反発生最弱事前条件と違反防止事前条件とを生成する手順１０００を例示する図である。図１０の手順１０００は、違反条件発生最弱事前条件を生成する手順１０１０と、違反防止事前条件を生成する手順１０２０とを有する。
【００６８】
違反条件発生最弱事前条件を生成する手順１０１０においては、まず、図５の規則ａにより、違反条件発生最弱事前条件を表す式“ｗｐ（ｖ：＝ｖ＋１；ｂ：＝ＯＦＦ，ＮＯＴ ｖ≦１０）”を立てる。次に、第１引数が実行文の列になっているので、列を分解する図５の規則ｆを用いて式“ｗｐ（ｖ：＝ｖ＋１，ｗｐ（ｂ：＝ＯＦＦ，ＮＯＴ ｖ≦１０））”を得る。次に、第２引数から図５の規則ｇを用いてに述語変換子ｗｐを取り除き、式“ｗｐ（ｖ：＝ｖ＋１，ＮＯＴ ｖ≦１０）”を得る。さらに、図５の規則ｇを用いてｗｐを取り除くと、違反条件最弱事前条件として“ＮＯＴ ｖ＋１≦１０”を得る。
【００６９】
違反防止事前条件を生成する手順１０２０においては、図５の規則ｈを用いて、事前記違反条件最弱事前条件の否定形として違反防止事前条件“ｖ≦９”を得る。
【００７０】
（修正された形式仕様データ）
図１１は、本実施形態に係る処理における違反防止事前条件を用いて修正された形式仕様データ１１００を例示する図である。
【００７１】
図１１においては、図７Ｂの処理内容７１０について、処理後に不変条件を成立させるために、元の事前条件“ｂ＝ＯＮ”に、図１０で得た違反防止事前条件“ｖ≦９”を論理積として追加する修正を行って、事前条件１１１３を有する形式仕様データ１１００を得る。
【００７２】
本実施形態によれば、スピーカ音量制御において、モデル検査法により得られる反例だけから、制約への違反が起きたことを示す違反条件を生成し、違反条件から制約への違反を起こさないようにするための違反防止事前条件を生成する。したがって、スピーカ音量制御において、モデル検査法により正例を得るための特別な条件の記述がない形式手法による仕様であっても、事前条件の修正を簡単に行うことができる。
【００７３】
［第４実施形態］
次に、本発明の第４実施形態に係る情報処理装置の処理について説明する。本実施形態に係る事前条件生成装置としての情報処理装置の処理は、上記第２実施形態の処理を具体的な複数の処理を含むスピーカの音量制御処理に適用した例を示す。本実施形態では、複数の処理を含むスピーカの音量制御処理において、形式仕様データとモデル検査法の反例とから生成した違反条件から、違反発生最弱事前条件と違反防止事前条件とを生成し、違反防止事前条件を用いて修正された形式仕様データを生成する。なお、本実施形態においては、２つの処理を含むスピーカの音量制御を説明するが、かかる処理は複数の処理を含むスピーカの音量制御に汎用的に使用できる。その他の構成および動作は、第２実施形態と同様であるため、その詳しい説明を省略する。
【００７４】
《処理の遷移図》
図１２は、本実施形態に係る処理における遷移１２００を示す遷移図である。図１２は、図７のスピーカの音量制御処理の遷移図に、さらにノイズ抑圧の処理を加えた処理を示している。なお、図１２において、図７と同様の処理および不変条件には同じ参照番号を付して、説明は省略する。
【００７５】
ノイズ抑圧の処理１２０４は、音量に対応するパラメータであるｖから、ノイズ抑圧に対応するパラメータである“ｗ”が、ｗ：＝ｖ＋１として算出される。そして、ノイズ抑圧に対応するパラメータであるｗの不変条件１２０５は、“０≦ｗ≦１０”とする。ｗが何であるかや単位などは本質的でないので、ここでは詳説しない。
【００７６】
（形式仕様データ）
図１３は、本実施形態に係る処理における形式仕様データ１３００を例示する図である。以下、図１３を参照して、形式仕様データに含まれる不変条件および処理内容について具体的に説明する。なお、図１３において、図７Ｂと同様の要素には同じ参照番号を付して、説明は省略する。また、図１３においては、以下の説明を複雑としないため、図７Ｂの音量を上げるボタンの状態を示す引数“ｂ”７１２については削除している。
【００７７】
図１３の上部は、不変条件１３０１を例示するものであり、図１２の２つの不変条件７０３と１２０５とが含まれている。すなわち、スピーカのボリュームの値ｖが０以上かつ１０以下の値であり、同時に、ノイズ抑圧の値ｗが０以上かつ１０以下の値ことを不変条件としている。
【００７８】
図１３の下部は、２つの処理内容１３１０と１３２０とを例示するものである。ここで、処理内容１３１０は、第３実施形態により生成された違反防止事前条件“ｖ≦９”を含む図１１の事前条件１１１３を有している。また、処理内容１３２０は、次のデータを含む。“ノイズ抑圧を上げる”という処理に関するデータ１３２１、“ｗ”の値をｖ＋１とする実行内容１３２４とである。なお、事前条件１３２３および事後条件１３２５は設定されていない。
【００７９】
以下、本実施形態においては、複雑化を避けるため、２つの処理内容１３１０と１３２０とを１つの処理内容１３３０に併合して説明する。しかしながら、２つの処理内容１３１０と１３２０とを別個の連続する処理として扱っても、以下の例と同じ結果が得られることは明らかである。
【００８０】
処理内容１３３０は、次のデータを含む。“スピーカの音量を上げて、ノイズ抑圧を上げる”という処理に関するデータ１３３１、第３実施形態により生成された違反防止事前条件“ｖ≦９”を含む事前条件１３３３、“ｖ”の値を１だけ加算した後“ｗ”の値をｖ＋１とする実行内容１３３４とである。なお、事後条件１３３５は設定されていない。
【００８１】
なお、また、不変条件、事前条件および事後条件といった制約は命題が設定されていなければ真（Ｔｒｕｅ）であるものとして扱う。
【００８２】
（モデル検査による反例）
図１４は、本実施形態に係る処理におけるモデル検査による反例１４００を例示する図である。なお、モデル検査による反例は無数存在するが、図１４には、その中で最も弱い反例（条件が真から偽に移る境界の反例）が、状態遷移および変数とその値で示されている。
【００８３】
図１４は、図１２の処理７０１および１２０４を行う前の状態（事前状態１４０１）において、ｖの値は９であり、図１２の処理７０１および１２０４を行った後の状態（事後状態１４０２）においてｖの値は１０でｗは１１であることを、例示的に示している。事後状態１４０２ではｗの値が１１であるために、命題ｗ≦１０は偽となり、図１３に示した不変条件１３０１は成立しない。すなわち、図１４は図１３に示した不変条件１３０１への反例である。
【００８４】
（違反条件の生成）
図１５は、本実施形態に係る処理における形式仕様データとモデル検査法の反例とから違反条件を生成する手順１５００を例示する図である。図１５を参照して、図１４に例示した反例１４００から違反条件を生成する具体的を説明する。
【００８５】
図１５の（１：Ｓ１５０１）は、不変条件“０≦ｖ ＡＮＤ ｖ≦１０”と“０≦ｗ ＡＮＤ ｗ≦１０”とを、部分論理式“０≦ｖ”、“ｖ≦１０”、“０≦ｗ”、および、“ｗ≦１０”のそれぞれにあたるリーフノードと、これらのリーフノードをＡＮＤ分岐で束ねたルートノードからなるＡＮＤ／ＯＲグラフとして表現した例である。
【００８６】
図１５の（２：Ｓ１５０２）は、各リーフノードについて、その対応する部分論理式がｗの値１１によって偽になる最右側のリーフノードを黒塗りで印づけた例である。
【００８７】
図１５の（３：Ｓ１５０３）は、下位ノードの値から上位ノードの値を計算し、偽になるノードを黒塗りで印づけた例である。左側の３つのリーフノードの値は真であり、最右側のリーフノードの値は偽であり、これらをＡＮＤ分岐で束ねたルートノードの値は下位ノードの値の論理積であることから偽であり、黒塗りで印づけられている。
【００８８】
図１５の（４：Ｓ１５０４）は、値が真となるノードを削除した例であり、図１５の（３）における２つのルートノードと最右側のリーフノードだけがグラフとして残っている。
【００８９】
図１５の（５：Ｓ１５０５）は、図１５の（４）において下位ノードが１つだけのノードをその下位ノードと置換した例である。図１５の（５）のＡＮＤ/ＯＲグラフに相当とする論理式の否定形が、求める違反条件“ＮＯＴ ｗ≦１０”となる。
【００９０】
（違反発生最弱事前条件と違反防止事前条件との生成）
図１６は、本実施形態に係る処理における違反条件から違反発生最弱事前条件と違反防止事前条件とを生成する手順１６００を例示する図である。図１６の手順１６００は、違反条件発生最弱事前条件を生成する手順１６１０と、違反防止事前条件を生成する手順１６２０とを有する。
【００９１】
違反条件発生最弱事前条件を生成する手順１６１０においては、まず、図５の規則ａにより、違反条件発生最弱事前条件を表す式“ｗｐ（ｖ：＝ｖ＋１；ｗ：＝ｖ＋１，ＮＯＴ ｗ≦１０）”を立てる。次に、第１引数が実行文の列になっているので、列を分解する図５の規則ｆを用いて式“ｗｐ（ｖ：＝ｖ＋１，ｗｐ（ｗ：＝ｖ＋１，ＮＯＴ ｗ≦１０）”を得る。次に、第２引数から図５の規則ｇを用いて述語変換子ｗｐを取り除き、式“ｗｐ（ｖ：＝ｖ＋１，ＮＯＴ ｖ＋１≦１０）”を得る。さらに、図５の規則ｇを用いてｗｐを取り除くと、違反条件最弱事前条件として“ＮＯＴ ｖ＋１＋１＝ｖ＋２≦１０”を得る。
【００９２】
違反防止事前条件を生成する手順１６２０においては、図５の規則ｈを用いて、事前記違反条件最弱事前条件の否定形として違反防止事前条件“ｖ≦８”を得る。
【００９３】
（修正された形式仕様データ）
図１７は、本実施形態に係る処理における違反防止事前条件を用いて修正された形式仕様データ１７００を例示する図である。
【００９４】
図１７においては、図１３の処理内容１３３０について、処理後に不変条件を成立させるために、元の事前条件“ｖ≦９”を、図１６で得た違反防止事前条件“ｖ≦８”と修正を行って、事前条件１７１３を有する形式仕様データ１７００を得る。
【００９５】
本実施形態によれば、複数の処理を含むスピーカ音量制御において、モデル検査法により得られる反例だけから、制約への違反が起きたことを示す違反条件を生成し、違反条件から制約への違反を起こさないようにするための違反防止事前条件を生成する。したがって、スピーカ音量制御において、モデル検査法により正例を得るための特別な条件の記述がない形式手法による仕様であっても、事前条件の修正を簡単に行うことができる。
【００９６】
［第５実施形態］
次に、本発明の第５実施形態に係る情報処理装置の処理について説明する。本実施形態に係る事前条件生成装置としての情報処理装置の処理は、上記第２実施形態の処理を具体的な図書館の図書管理処理に適用した例を示す。本実施形態では、図書館の図書管理処理において、形式仕様データとモデル検査法の反例とから生成した違反条件から、違反発生最弱事前条件と違反防止事前条件とを生成し、違反防止事前条件を用いて修正された形式仕様データを生成する。その他の構成および動作は、第２実施形態と同様であるため、その詳しい説明を省略する。
【００９７】
《処理の遷移図》
図１８は、本実施形態に係る処理における遷移１８００を示す遷移図である。図１８は、図書館における図書管理の処理を示している。本実施形態においては、第３実施形態や第４実施形態のような数値条件ではなく、論理条件により処理が制御される。
【００９８】
図１８の遷移図の状態は、ユーザの未登録１８０１と、登録済み１８０２と、本の貸出予約１８０３と、本の貸出１８０４と、ユーザの登録抹消１８０５と、を含む。各状態間の遷移は矢印で示されている。
【００９９】
以下、本実施例では、登録済み１８０２から登録抹消１８０５へと遷移する、登録抹消処理における違反防止事前条件の生成について説明するが、これに限定されず本実施形態は適用可能である。
【０１００】
（形式仕様データ）
図１９は、本実施形態に係る処理における形式仕様データ１９００を例示する図である。以下、図１９を参照して、形式仕様データに含まれる不変条件および処理内容について具体的に説明する。
【０１０１】
図１９の上部は、不変条件１９０１を例示するものであり、“会員のみに本を貸し出す（逆に言えば、非会員には本を貸出しない）”を不変条件としている。
【０１０２】
図１９の下部は、処理内容１９１０を例示するものである。ここで、処理内容１９１０は、“会員登録の抹消”という処理に関するデータ１９１１と、“会員ＩＤが登録済み"という事前条件１９１３と、“会員ＩＤの抹消処理”をする実行内容１９１４と、“会員抹消”という事後条件１３２５を有している。
【０１０３】
（モデル検査による反例）
図２０は、本実施形態に係る処理におけるモデル検査による反例２０００を例示する図である。なお、モデル検査による反例は無数存在するが、図２０には、その中で最も弱い反例（条件が真から偽に移る境界の反例）が、状態遷移および変数とその値で示されている。
【０１０４】
図２０は、図１８の登録抹消を行う前の状態（事前状態２００１）において、抹消する会員の会員ＩＤが登録されていて、本の貸出や予約が有ることを、例示的に示している。また、図２０は、図１８の抹消処理を行った後の状態（事後状態２００２）において登録抹消されて非会員になったにも関わらず、その会員に本が貸し出されている、あるいは貸出が予約されていることを、例示的に示している。事後状態２００２では非会員が本を貸出または予約しているために、図１９に示した不変条件１９０１は成立しない。すなわち、図２０は図１９に示した不変条件１９０１への反例である。
【０１０５】
（違反条件の生成）
図２１は、本実施形態に係る処理における形式仕様データとモデル検査法の反例とから違反条件を生成する手順２１００を例示する図である。図２１を参照して、図２０に例示した反例２０００から違反条件を生成する具体的を説明する。
【０１０６】
図２１の（１：Ｓ２１０１）は、不変条件“貸出無し ＡＮＤ 抹消”と“予約無し ＡＮＤ 抹消”とを、部分論理式“貸出無し”、“抹消”、“予約無し”、および、“抹消”のそれぞれにあたるリーフノードと、これらのリーフノードをＡＮＤ分岐で束ねたルートノードからなるＡＮＤ／ＯＲグラフとして表現した例である。
【０１０７】
図２１の（２：Ｓ２１０２）は、各リーフノードについて、その対応する部分論理式が貸出有りや予約有りによって偽になるリーフノードを黒塗りで印づけた例である。
【０１０８】
図２１の（３：Ｓ２１０３）は、下位ノードの値から上位ノードの値を計算し、偽になるノードを黒塗りで印づけた例である。抹消のリーフノードの値は真であり、貸出有りと予約有りのリーフノードの値は偽であり、これらをＡＮＤ分岐で束ねたルートノードの値は下位ノードの値の論理積であることから偽であり、黒塗りで印づけられている。
【０１０９】
図２１の（４：Ｓ２１０４）は、値が真となるノードを削除した例であり、図２１の（３）における３つのルートノードと貸出無しおよび予約無しのリーフノードとがグラフとして残っている。
【０１１０】
図２１の（５：Ｓ２１０５）は、図２１の（４）において下位ノードが１つだけのノードをその下位ノードと置換した例である。図２１の（５）のＡＮＤ/ＯＲグラフに相当とする論理式の否定形が、求める違反条件“ＮＯＴ （貸出無し ＡＮＤ 予約無し）”となる。
【０１１１】
（違反発生最弱事前条件と違反防止事前条件との生成）
図２２は、本実施形態に係る処理における違反条件から違反発生最弱事前条件と違反防止事前条件とを生成する手順２２００を例示する図である。図２２の手順２２００は、違反条件発生最弱事前条件を生成する手順２２１０と、違反防止事前条件を生成する手順２２２０とを有する。
【０１１２】
違反条件発生最弱事前条件を生成する手順２２１０においては、まず、図５の規則ａにより、違反条件発生最弱事前条件を表す式“ｗｐ（抹消，ＮＯＴ （貸出無し ＡＮＤ 予約無し））”を立てる。次に、図５の規則ｇを用いてｗｐを取り除くと、違反条件最弱事前条件として“ＮＯＴ （貸出無し ＡＮＤ 予約無し）”を得る。
【０１１３】
違反防止事前条件を生成する手順２２２０においては、図５の規則ｈを用いて、事前記違反条件最弱事前条件の否定形として違反防止事前条件“貸出無し ＡＮＤ 予約無し”を得る。
【０１１４】
（修正された形式仕様データ）
図２３は、本実施形態に係る処理における違反防止事前条件を用いて修正された形式仕様データ２３００を例示する図である。
【０１１５】
図２３においては、図１９の処理内容１９１０について、処理後に不変条件を成立させるために、元の事前条件“会員ＩＤが登録済み”に、図２２で得た違反防止事前条件“貸出無し ＡＮＤ 予約無し”を論理積として追加する修正を行う。そして、新たな事前条件２３１３を有する形式仕様データ２３００を得る。
【０１１６】
本実施形態によれば、数値条件ではない図書館の図書管理処理において、モデル検査法により得られる反例だけから、制約への違反が起きたことを示す違反条件を生成し、違反条件から制約への違反を起こさないようにするための違反防止事前条件を生成する。したがって、図書管理処理において、モデル検査法により正例を得るための特別な条件の記述がない形式手法による仕様であっても、事前条件の修正を簡単に行うことができる。
【０１１７】
［第６実施形態］
次に、本発明の第６実施形態に係る情報処理装置について説明する。本実施形態に係る事前条件生成装置としての情報処理装置は、上記第２実施形態と比べると、モデル検査実行部や出力処理部を情報処理装置の外部に有する点で異なる。その他の構成および動作は、第２実施形態と同様であるため、その詳しい説明を省略する。
【０１１８】
《情報処理装置の機能構成》
図２４は、本実施形態に係る情報処理装置２４１０の機能構成を示すブロック図である。なお、図２４において、第２実施形態の図２と同様の機能要素には同じ参照番号を付して、詳細な説明は省略する。
【０１１９】
図２４の情報処理装置２４１０は、読込処理部２４１１と、違反条件生成部２１３と、事前条件生成部２１４とを備え、図２に示す情報処理装置２１０が有する機能のうち、モデル検査実行部２１２と出力処理部２１５を外部に配置したものである。
【０１２０】
なお、図２４においては、モデル検査実行部２１２と出力処理部２１５、および、形式仕様データＤＢ２２０と違反防止事前条件ＤＢ２３０は、ネットワーク２４２０を介して情報処理装置２４１０に接続する構成を示している。これら外部機能要素は、１つの装置に含まれていてもそれぞれ別個の複数装置に分散されていてもよい。また、ネットワーク２４２０を介した接続ではなく、専用回線あるいは有線接続されていてもよい。
【０１２１】
《情報処理装置の処理手順》
図２５は、本実施形態に係る情報処理装置２４１０の処理手順を示すフローチャートである。なお、図２５において、第２実施形態の図３と同様のステップには同じステップ番号を付して、説明は省略する。
【０１２２】
読込処理部２４１１は形式仕様データＤＢ２２０から形式仕様データを読み込み、モデル検査実行部２１２からモデル検査による反例も読み込む（ステップＳ２５０１）。以下、図３と同様の、違反条件の生成（Ｓ３０７）と違反発生最弱事前条件の生成（Ｓ３０９）と違反防止事前条件の生成（Ｓ３１１）とを行なう。
【０１２３】
本実施形態によれば、最小の構成により、モデル検査法により得られる反例だけから、制約への違反が起きたことを示す違反条件を生成し、違反条件から制約への違反を起こさないようにするための違反防止事前条件を生成する。したがって、簡単な構成により、モデル検査法により正例を得るための特別な条件の記述がない形式手法による仕様であっても、事前条件の修正を容易に行うことができる。
【０１２４】
［他の実施形態］
以上、実施形態を参照して本発明を説明したが、本発明は上記実施形態に限定されるものではない。本発明の構成や詳細には、本発明のスコープ内で当業者が理解し得る様々な変更をすることができる。また、それぞれの実施形態に含まれる別々の特徴を如何様に組み合わせたシステムまたは装置も、本発明の範疇に含まれる。
【０１２５】
また、本発明は、複数の機器から構成されるシステムに適用されてもよいし、単体の装置に適用されてもよい。さらに、本発明は、実施形態の機能を実現する情報処理プログラムが、システムあるいは装置に直接あるいは遠隔から供給される場合にも適用可能である。したがって、本発明の機能をコンピュータで実現するために、コンピュータにインストールされるプログラム、あるいはそのプログラムを格納した媒体、そのプログラムをダウンロードさせるＷＷＷ(World Wide Web)サーバも、本発明の範疇に含まれる。特に、少なくとも、非一時的コンピュータ可読媒体（non-transitory computer readable medium）は本発明の範疇に含まれる。
【０１２６】
［実施形態の他の表現］
上記の実施形態の一部または全部は、以下の付記のようにも記載されうるが、以下には限られない。
（付記１）
複数の処理に含まれるそれぞれの前記処理の処理内容の記述を含む形式仕様データの検査結果として、前記複数の処理に課される制約への違反を見つけた場合に、処理の開始状態から前記制約に違反する状態までの遷移列と各状態における変数の値との集まりである反例に基づいて、前記制約に違反する状態において前記制約への違反が起きた条件である違反条件を生成する違反条件生成手段と、
前記形式仕様データと前記違反条件とに基づいて、処理の開始状態における、処理の実行後に前記制約への違反が起こる条件としての違反発生最弱事前条件と、当該処理の実行後に前記制約への違反が起きない条件としての違反防止事前条件とを生成する事前条件生成手段と、
を備える情報処理装置。
（付記２）
前記違反条件生成手段は、前記形式仕様データの制約のうち前記反例において偽となった制約をＡＮＤ／ＯＲグラフとして表現し、前記反例において制約への違反を起こした状態における変数を用いて、前記ＡＮＤ／ＯＲグラフで偽となるノードを計算し、偽となるノードだけで構成される新たなＡＮＤ／ＯＲグラフを生成し、生成された前記新たなＡＮＤ／ＯＲグラフを論理式として表現した論理式の否定形として、違反条件を生成する付記１に記載の情報処理装置。
（付記３）
前記事前条件生成手段は、前記違反条件と、前記形式仕様データに含まれる処理の実行内容のうち、処理の開始状態から違反を起こした状態までの実行内容とから、処理の開始状態においてその処理の実行後に前記制約への違反が起こるならば真となる条件である違反発生最弱事前条件を生成する付記１または２に記載の情報処理装置。
（付記４）
前記事前条件生成手段は、前記処理の実行後に前記制約への違反が起きないならば真となる条件である違反防止事前条件を、前記違反発生最弱事前条件の否定形として生成する付記１乃至３のいずれか１項に記載の情報処理装置。
（付記５）
前記形式仕様データを読み込む読込処理手段と、
読み込んだ前記形式仕様を入力としてモデル検査を行い制約への前記反例を出力するモデル検査実行手段と、
をさらに備え、
前記違反条件生成手段は、前記形式仕様データの検査結果の前記反例に基づいて、前記違反条件を生成する付記１乃至４のいずれか１項に記載の情報処理装置。
（付記６）
前記形式仕様データは、さらに、前記処理の開始状態の制約を記述した事前条件と前記処理の実行後の制約を記述した事後条件とを含む付記１乃至５のいずれか１項に記載の情報処理装置。
（付記７）
前記事前条件生成手段により生成された前記違反防止事前条件あるいは前記違反発生最弱事前条件を出力する出力処理手段を、さらに備える付記１乃至６のいずれか１項に記載の情報処理装置。
（付記８）
複数の処理に含まれるそれぞれの前記処理の処理内容の記述を含む形式仕様データの検査結果として、前記複数の処理に課される制約への違反を見つけた場合に、処理の開始状態から前記制約に違反する状態までの遷移列と各状態における変数の値との集まりである反例に基づいて、前記制約に違反する状態において前記制約への違反が起きた条件である違反条件を生成する違反条件生成ステップと、
前記形式仕様データと前記違反条件とに基づいて、処理の開始状態における、処理の実行後に前記制約への違反が起こる条件としての違反発生最弱事前条件と、当該処理の実行後に前記制約への違反が起きない条件としての違反防止事前条件とを生成する事前条件生成ステップと、
を含む情報処理方法。
（付記９）
複数の処理に含まれるそれぞれの前記処理の処理内容の記述を含む形式仕様データの検査結果として、前記複数の処理に課される制約への違反を見つけた場合に、処理の開始状態から前記制約に違反する状態までの遷移列と各状態における変数の値との集まりである反例に基づいて、前記制約に違反する状態において前記制約への違反が起きた条件である違反条件を生成する違反条件生成ステップと、
前記形式仕様データと前記違反条件とに基づいて、処理の開始状態における、処理の実行後に前記制約への違反が起こる条件としての違反発生最弱事前条件と、当該処理の実行後に前記制約への違反が起きない条件としての違反防止事前条件とを生成する事前条件生成ステップと、
をコンピュータに実行させる情報処理プログラム。
【図１】
2014160435.tif 000003
【図２】
2014160435.tif 000004
【図３】
2014160435.tif 000005
【図４】
2014160435.tif 000006
【図５】
2014160435.tif 000007
【図６】
2014160435.tif 000008
【図７Ａ】
2014160435.tif 000009
【図７Ｂ】
2014160435.tif 000010
【図８】
2014160435.tif 000011
【図９】
2014160435.tif 000012
【図１０】
2014160435.tif 000013
【図１１】
2014160435.tif 000014
【図１２】
2014160435.tif 000015
【図１３】
2014160435.tif 000016
【図１４】
2014160435.tif 000017
【図１５】
2014160435.tif 000018
【図１６】
2014160435.tif 000019
【図１７】
2014160435.tif 000020
【図１８】
2014160435.tif 000021
【図１９】
2014160435.tif 000022
【図２０】
2014160435.tif 000023
【図２１】
2014160435.tif 000024
【図２２】
2014160435.tif 000025
【図２３】
2014160435.tif 000026
【図２４】
2014160435.tif 000027
【図２５】
2014160435.tif 000028