(57)【要約】動的制約条件を解決し、試験および検証プロセスのためのテストを生成して、ＤＵＴ（試験中のデバイス）のためのシミュレーションモデルの品質を試験するためのシステムおよび方法。本発明は、「ジェネレータミニ言語」（ＧＭＬ）による一連の命令の生成を通してそのような動的制約条件の解決をもたらす。次いで、所定のセットの動的制約条件に正しいランダム解を提供するために、これらの命令を実行する。実行のプロセスは、任意選択的に、かつより好適には、制約条件セットのランダム解を提供することを同時に可能にしながら制約条件によって実行に課せられる要件を処理するソフトウェアとして実現される、制約条件解決エンジンによって行なわれることが好ましい。そのような制約条件解決エンジンは任意選択的に一種の状態マシンと見ることができ、状態マシンの個々の要素は１つまたはそれ以上の動的グラフによって表わすことがより好ましい。【選択図】図１
2004513435.tif 000002
【特許請求の範囲】
【請求項１】
ＤＵＴ（試験中のデバイス）用のテスト生成のための制約条件を動的に解決するためのシステムであって、
（ａ）ＤＵＴのデータモデルと、
（ｂ）実行時前にテスト生成のための値を生成するための複数の静的命令を生成することによって制約条件を解決するための抽象生成マシンと、
（ｃ）値を生成するための前記複数の静的命令に従って、かつ実行時に前記データモデルに従って、テスト生成を実行するためのテストジェネレータと
を備えたシステム。
【請求項２】
前記抽象生成マシンは、制約条件によってテスト生成に課せられる要件を処理するための制約条件解決エンジンをさらに含む請求項１のシステム。
【請求項３】
各制約条件は少なくとも１つのパラメータを特徴とし、前記制約条件解決エンジンは、各制約条件の前記少なくとも１つのパラメータを受け入れるための、かつ各制約条件の前記少なくとも１つのパラメータに従って前記複数の静的命令の少なくとも１つを生成するための状態マシンである請求項２のシステム。
【請求項４】
各制約条件および各ノードが前記少なくとも１つの動的グラフのノードによって表されるように、前記状態マシンは複数の要素を有し、前記制約条件解決エンジンは前記状態マシンの少なくとも１つの要素を表すための少なくとも１つの動的グラフを特徴とし、かつ制約条件間の関係は前記少なくとも１つの動的グラフの辺によって表される請求項２のシステム。
【請求項５】
前記制約条件解決エンジンは、
（ｉ）前記命令を実行するための順序を決定するための第１の動的グラフを処理するための順序マネージャと、
（ｉｉ）前記命令において制約条件間の関係を決定するための第２の動的グラフを処理するための動的グラフマネージャと
をさらに含む請求項４のシステム。
【請求項６】
前記順序はテスト生成中に制約条件に従って決定される請求項５のシステム。
【請求項７】
前記第２の動的グラフがフィールド範囲間の整合性を維持するように、前記第２の動的グラフはノードを制約条件に関連付けるための動的２部グラフであり、各ノードは生成できるフィールド範囲を表わす請求項５のシステム。
【請求項８】
前記動的グラフマネージャは制約条件間の前記関係の数を低減する請求項７のシステム。
【請求項９】
ＤＵＴ（試験中のデバイス）用のテスト生成のための複数の動的制約条件を動的に解決するための方法であって、各制約条件は少なくとも１つのパラメータを特徴とし、その方法のステップはデータプロセッサによって実行され、
（ａ）複数の動的制約条件を記述するための少なくとも１つの動的グラフであって、前記少なくとも１つの動的グラフの各ノードがパラメータを表わし、かつ各辺が制約条件間の関係を表わして成る少なくとも１つの動的グラフを生成するステップと、
（ｂ）前記少なくとも１つの動的グラフのノードの数を低減するステップと、
（ｃ）動的制約条件を解決するための複数の命令を生成するために前記少なくとも１つの動的グラフ中で移動する経路を決定するステップと
を含む方法。
【請求項１０】
ステップ（ａ）は、２セットのノード、前記制約条件用の第１のセットおよび前記パラメータ用の第２のセットを特徴とする第２の２部グラフを提供するステップをさら含む請求項９の方法。
【請求項１１】
（ｄ）制約条件に対する単一の特定的な解を形成するために前記複数の命令を実行するステップ
をさらに含む請求項１０の方法。
【請求項１２】
（ｄ）前記複数の命令を特定のコンピュータプログラミング言語に変換するステップ
をさらに含む請求項１０の方法。
【請求項１３】
ステップ（ｃ）は、制約条件を解釈するための文脈を表すための役割に前記複数の命令の少なくとも一部分をグループ化するステップをさらに含む請求項９の方法。
【請求項１４】
各役割は、統計的に順序付けられる、および順序つけられない、からなる群から選択される請求項１３の方法。
【発明の詳細な説明】
【０００１】
発明の分野および背景
本発明は、動的制約条件付きテスト生成のためのシステムおよび方法に関し、実行したときに特定のランダム解を提供する１セットの命令を生成することによって、制約条件を動的に解決するためのシステムおよび方法に関する。
【０００２】
設計の検証は、集積回路、基板、またはシステムレベルのアーキテクチャが、そのデバイスのアーキテクチャの仕様によって定義された要求事項を厳密に実現するかどうかを決定するプロセスである。テスト中のデバイス（ＤＵＴ）の設計検証は実際のデバイスに、またはデバイスのシミュレーションモデルに実行することができる。単に説明のために、いかようにも限定する意図なく、以下の議論は、デバイスのシミュレーションモデルに対して実行されるテストを中心にしている。
【０００３】
様々な型のデバイスの設計およびデバイスアーキテクチャが複雑になるにつれて、設計エラーの見込みが高まる。しかし、デバイスの設計のシミュレーションモデルも作成しかつテストすることがより複雑になっているので、設計の検証もいっそう難しく、かつ時間がかかるようになってきている。
【０００４】
設計検証の問題は、多種多様のデバイスおよびデバイスアーキテクチャの検証およびテストに有用な、広く汎用化可能なツールの欠如によっていっそうひどくなる。典型的な背景技術の検証方法はしばしば特定の設計を有する特定のデバイスに限定されているので、シミュレーションモデル用のそうした検証方法を準備し実行するステップを、各々の新しいデバイスに対して実行しなければならない。
【０００５】
デバイスのシミュレーションモデルを通して設計を検証するプロセスは、ＶｅｒｉｌｏｇおよびＶＨＤＬなどのハードウェア記述言語の可用性によって促進される。これらの言語はゲートまたはトランジスタよりも高レベルでハードウェアを記述するよう設計される。結果として生じるデバイスのシミュレーションモデルは、回路の入力に印加される２進数字の文字列であるテストベクトルの形で、入力刺激を受けることができる。次いでシミュレーションモデルは結果を出し、それはデバイスの特定の設計に対し期待された結果に照らして検査される。しかし、これらの言語は一般的に実検証用に設計されていない。したがって、検証エンジニアは、デバイスの設計検証を実行するためにこれらのハードウェア記述言語によって記述されたモデルとインタフェースするために、追加プログラミングコードを書かなければならない。
【０００６】
テスト環境の例として静的および動的テスト環境がある。静的テスト環境は、予め計算されたテストベクトルをＤＵＴのシミュレーションモデルに印加し、かつ／またはシミュレーションモデルの作動後に結果を検査する。加えて、静的テスト環境を使用してシミュレーションモデルから出力された結果を検査する場合には、テストが終了する後までテストの誤りは検出されない。その結果、誤り箇所のデバイスの内部状態は決定できず、そうした内部状態を決定するためには、シミュレーションを再作動する必要がある。この手順はシミュレーションサイクルを浪費し、特に長いテスト中に、かなりの時間を費やすことが必要になるおそれがある。
【０００７】
より有用かつ効率的な型のテストが動的テスト環境である。この型の環境の場合、ＤＵＴのモデルのシミュレーションと同時に、かつシミュレートされたデバイスの状態フィードバックにより潜在的に制御しながら、テストベクトルが生成されるように、１セットのプログラミング命令が書かれる。この手順により、有向無作為生成を実行し、かつデバイスのシミュレーションモデルの状態に対してテスト自体の間に明らかになった効果を感知することが可能になる。したがって、動的テスト生成は明らかに設計の検証に対し多くの利点を有する。
【０００８】
テスト環境の領域内で、静的および動的テスト環境はどちらも、束縛ベクトルまたは事前生成入力によってのみ実現できる。しかし、より強力かつより洗練された実現は、テスト生成を使用して環境を生じる。
【０００９】
このようなテストジェネレータの一例は１９９８年２月６日出願の米国特許出願第０９／０２０７９２号に開示されており、それは全部ここに記載されているかのように参照によって組み込まれる。このテストジェネレータは、ＶｅｒｉｌｏｇおよびＶＨＤＬのようなハードウェア記述言語と対話し、それより高レベルとして位置する。テスト生成手続きは、ハードウェア指向検証特定的オブジェクト指向プログラミング言語で書かれる。この言語は様々なテストを書くために使用され、次いでそれはテストジェネレータモジュールによってデバイス検証テストを自動的に作成するために使用される。幅広い設計環境はこの言語によってテストされ、検証される。したがって、開示された手続きは汎用化可能であり、しかもエンジニアがプログラムしかつデバッグするのが簡単である。
【００１０】
開示された言語は、モデルによってシミュレートすべきデバイスの設計をより充分かつ効率的に記述するためのストラクトなど、多数の要素を特徴とする。残念ながら、開示された言語および結果的に得られるテスト生成環境は、妥当な処理時間内に動的制約条件に対する適正なランダム解を提供するための特徴を含まず、また実際にシミュレーションに要する時間と同一尺度で動的に反応することもできない。さらに、非ランダム解でそのような制約条件を扱う背景技術でも、そのような特徴は知られていない。
【００１１】
したがって、特定セットの命令を実行することによって生成される、特定のランダムであるが正しい解を通して動的制約条件を解決するためのシステムおよび方法に対する必要性はまだ満たされておらず、それを持つことは非常に有用であろう。
【００１２】
発明の概要
本発明の方法およびシステムは、動的制約条件を解決し、試験および検証プロセスのためのテストを生成して、ＤＵＴ（試験中のデバイス）のためのシミュレーションモデルの品質を試験する。本発明は、「ジェネレータミニ言語」（ＧＭＬ）による一連の命令の生成を通してそのような動的制約条件の解決をもたらす。次いで、所定のセットの動的制約条件に正しいランダム解を提供するために、これらの命令を実行する。実行のプロセスは、任意選択的に、かつより好適には、制約条件セットのランダム解を提供することを同時に可能にしながら制約条件によって実行に課せられる要件を処理するソフトウェアとして実現される、制約条件解決エンジンによって行なわれることが好ましい。そのような制約条件解決エンジンは任意選択的に一種の状態マシンと見ることができ、状態マシンの個々の要素は１つまたはそれ以上の動的グラフによって表わすことがより好ましい。
【００１３】
本発明では、ＤＵＴ（試験中のデバイス）用のテスト生成のための制約条件を動的に解決するためのシステムであって、（ａ）ＤＵＴのデータモデルと、（ｂ）複数の静的命令を生成することによって制約条件を解決するための抽象生成マシンと、（ｃ）複数の静的命令に従って、かつデータモデルに従って、テスト生成を実行するためのテストジェネレータとを備えたシステムを提供する。
【００１４】
本発明の別の実施形態では、ＤＵＴ（試験中のデバイス）用のテスト生成のための複数の動的制約条件を動的に解決するための方法であって、各制約条件は少なくとも１つのパラメータを特徴とし、その方法のステップはデータプロセッサによって実行され、（ａ）複数の動的制約条件を記述するための動的グラフであって、少なくとも１つの動的グラフの各ノードが制約条件またはパラメータを表わし、かつ各辺が制約条件間の関係を表わして成る動的グラフを少なくとも１つ生成するステップと、（ｂ）少なくとも１つの動的グラフのノードの数を低減するステップと、（ｃ）動的制約条件を解決するための複数の命令を生成するために少なくとも１つの動的グラフ中で移動する経路を決定するステップとを含む方法を提供する。
【００１５】
以下で、用語「コンピューティングプラットフォーム」とは、特定のコンピュータハードウェアシステムまたは特定のソフトウェアオペレーティングシステムを指す。そのようなハードウェアシステムの例として、パーソナルコンピュータ（ＰＣ）、マッキントッシュ（商標）コンピュータ、メインフレーム、ミニコンピュータ、およびワークステーションがあるが、これらに限定されない。そのようなソフトウェアオペレーティングシステムの例として、ＵＮＩＸ（登録商標）、ＶＭＳ、リナックス、ＭａｃＯＳ（商標）、ＤＯＳ、ＦｒｅｅＢＳＤ、Ｗｉｎｄｏｗｓ（登録商標）　ＮＴ、Ｗｉｎｄｏｗｓ（登録商標）９５、Ｗｉｎｄｏｗｓ（登録商標）９８、およびＷｉｎｄｏｗｓ（登録商標）２０００をはじめとするマイクロソフト社（米国）によるＷｉｎｄｏｗｓ（登録商標）オペレーティングシステムの１つがあるが、これらに限定されない。
【００１６】
本発明の方法はまた、本発明がハードウェア、ソフトウェア、ファームウェア、またはそれらの組合せとして実現することができるように、仮想または実データプロセッサによって実行される複数の命令として記述することもできる。本発明では、ソフトウェアアプリケーションは任意の適切なプログラミング言語で書くことができ、それは当業の通常の熟練者が容易に選択することができる。選択するプログラミング言語は、ソフトウェアアプリケーションが実行されるコンピューティングプラットフォームとの互換性がなければならない。適切なプログラミング言語の例としてＣ、Ｃ＋＋、およびＪａｖａ（登録商標）があるが、これらに限定されない。
【００１７】
以下で、用語「非ランダム」とは、ランダムではないが、必ずしも決定的ではないプロセス、またはプロセスによって選択されるエンティティを指す。
【００１８】
図面の簡単な説明
本発明をここで単なる例として、添付の図面に関連して説明する。
図１は、本発明に係る例示的システムを示す略ブロック図である。
図２は、図１のＡＧＭをより詳しく示す略ブロック図である。
図３は、本発明の方法に係る構成後のグラフの略ブロック図である。
【００１９】
好適な実施形態の説明
本発明のシステムおよび方法は、動的制約条件を解消し、試験および検証プロセスのためのテストを生成して、ＤＵＴ（試験中のデバイス）のためのシミュレーションモデルの品質を試験する。本発明は、「ジェネレータミニ言語」（ＧＭＬ）による一連の命令の生成を通してそのような動的制約条件の解決をもたらす。次いで、所定のセットの動的制約条件に正しいランダム解を提供するために、これらの命令を実行する。実行のプロセスは、任意選択的に、かつ、より好適には、制約条件セットのランダム解を提供することを同時に可能にしながら制約条件によって実行に課せられる要件を処理するソフトウェアとして実現される、制約条件解決エンジンによって行なわれることが好ましい。そのような制約条件解決エンジンは任意選択的に一種の状態マシンと見ることができ、状態マシンの個々の要素は１つまたはそれ以上の動的グラフによって表わすことがより好ましい。
【００２０】
本発明の制約条件解決エンジンは、制約条件を解決するプロセスを少なくとも部分的に実行時前に静的解析段階で実行することを可能にし、それによって制約条件解決のプロセスをより効果的かつより効率的にする。次いで、制約条件解決エンジンによって実行時中に実行するための１セットの命令が作成される。したがって、実行時中に制約条件解決を行わなければならない背景技術とは異なり、本発明は制約条件解決のプロセスを２つの段階、すなわち１セットの命令が作成される前の静的解析中（実行時前）、およびこれらの命令が実行される実行時中に分離することが可能である。
【００２１】
本発明の好適な実施形態では、状態マシンは２つの構成要素を有する。第１の構成要素は順序マネージャ機能単位であり、これは双方向および単方向の辺を持つ動的グラフを維持することが好ましい。この動的グラフは、グラフのノード間で暗に示される順序に従って、実行される命令に各制約条件を組み込む順序を決定するために使用することがより好ましい。この順序は次に、生成時に提供される制約条件のセットに応じて決定されることがより好ましい。
【００２２】
状態マシンの第２の構成要素は、任意選択的に、かつ好ましくは、ノードおよび制約条件に関する動的２部グラフを維持する従属性グラフマネージャとして実現することが好ましい。各ノードは、生成できるフィールド範囲を表わす。従属性グラフマネージャはこの動的グラフを使用して、グラフによって記述される提供された制約条件のセットの範囲の整合性を維持する。任意選択的に、かつ、より好ましくは、従属性グラフマネージャは、簡約機構の使用を通して整合性を維持するために審査しなければならない関係の数を低減することができる。これらの簡約機構は、制約条件に可能な値の範囲全体で整合性のある値のセットを維持するための方法である。
【００２３】
順序マネージャと従属性グラフマネージャの相互作用の組合せは、状態マシンの動作を駆動する。次に、これらの動作は制約条件を静的に解析することを可能にするので、動的セットの制約条件に一般的絶対解を提供しようとするよりむしろ、それでもなお制約条件の要件を充足する単一の特定的なランダム解が提供される。この解は、状態マシンによって実行される１セットの特定的な命令として実現される。
【００２４】
本発明の利点は、制約条件の静的解およびしたがって命令のセットの静的生成が、実行時にテスト生成の特定の例を実際に生成するのではなく、むしろ静的解析の段階中に、多くの複雑な演算を一度に実行することを可能にすることである。加えて、命令の実行を最適化するために、命令のセット自体を任意選択的に解析することができる。これらの利点は、実行時に制約条件解決を行なわなければならない背景技術の方法およびシステムで利用可能である。
【００２５】
本発明のさらなる利点として、一連の命令を、例えば「Ｃ」または「Ｃ＋＋」など、複数の異なるコンピュータプログラミング言語に、および／または異なる型のハードウェアで実行するために、変換する任意選択的であるが好適な能力があり、それはＤＵＴを様々なアプリケーションで試験するのに有用である。加えて、一連の命令は、通常のコンピュータプログラムコードと同様に、より容易に任意選択的にデバッグすることができる。
【００２６】
本発明に係るシステムおよび方法の原理および動作は、図面および付随する説明を参照することにより、いっそう深く理解することができる。
【００２７】
今、図面を参照すると、図１は、本発明に係るテスト生成のための例示的システムを示す略ブロック図である。図示したシステムは、本発明の説明に必要なテスト生成手続きに一般的機能のみを含むことに注意されたい。テスト生成手続き全体のより完全な説明は、前に参照によって組み込んだ米国特許出願第０９／０２０７９２号に見ることができる。また、本発明はシミュレーションモデルの文脈で説明するが、本発明は物理的デバイスの検証にも有用であることにも注意されたい。物理的デバイスおよびシミュレーションモデルはどちらも、テスト環境にあるＤＵＴ（試験中のデバイス）と記述することができる。
【００２８】
本発明に係るテスト生成システム１０は、ＶｅｒｉｌｏｇまたはＶＨＤＬなどのハードウェア記述言語で書かれた、テスト中のデバイス（ＤＵＴ）の設計１４を受け入れることのできるシミュレータ１２を特徴とする。加えて、シミュレータ１２は、実行時にテスト生成手続きを実行するためのテストエンジン１６と対話する。シミュレータ１２とテストエンジン１６との間の対話は、テストエンジン１６がシミュレータ１２に入力を提供し、次にさらなる操作のための入力としてシミュレータ１２から結果を受け取るので、二方向として示される。
【００２９】
テストエンジン１６は、ＤＵＴ１４を実行時にテストするための実行時システム２１に接続されたテストジェネレータ１８を特徴とする。テストジェネレータ１８は１組の制約条件２０およびＩ／Ｏデータモデル２２を受け取り、次いでＤＵＴ１４のテストおよび検証を実行する。本発明では、制約条件２０は少なくとも１組の複数の動的制約条件を含み、それらは次いで、以下でさらに詳しく述べる通り、本発明の方法に従って解かれる。実行時システム２１は、実行時テスト手続き中にシミュレータ１２の駆動および標本化の両方を実行する。
【００３０】
制約条件２０の動的制約条件部分を解くためにテストジェネレータ１８はＡＧＭ（抽象生成マシン）モジュール２６を含むことが好ましい。ＡＧＭモジュール２６は一連の命令を「ジェネレータミニ言語」（ＧＭＬ）で作成する。これらの命令は次いで、任意のセットの動的制約条件に正しいランダム解を提供するために実行される。簡単に言うと、静的解析モジュール２９は、テストジェネレータ１８と協力して、実行前に動的制約条件の初期解析を実行することが好ましい。この初期解析は、正しいランダム解を生成するための１セットの命令を生成することが好ましい。次に、実行時インタプリタモジュール３１は、これらの命令を受け取り、それらを実行時システム２１と共に実行することが好ましい。ＡＧＭモジュール２６のより詳細な説明を、以下で図２に関連して提供する。
【００３１】
テストおよび検証のプロセス中に、データコレクタ２４は実行時システム２１から１つまたはそれ以上の変数の値を要求する。これらの要求は任意選択的に、実行時システム２１によって発行されるトリガイベントに従って実行される。例えば、時相カバレージに関連するデータを収集する場合、そうしたトリガイベントは任意選択的に、固定され予め定められた標本化時間、および／または例えば時相言語で与えられた時相式によって定義された状態遷移の時相パターンの発生である。データコレクタ２４はテストジェネレータ１８と交信し、テストジェネレータ１８用のＡＰＩ（アプリケーションプログラミングインタフェース）を通して要求されたデータにアクセスすることができる。そうしたＡＰＩは、所望のデータを収集するために要求されるソフトウェア機能呼出しを指定する。この収集データは次いで、データアナライザ２６によって解析される。
【００３２】
本発明の好適な実施形態では、制約条件２０およびＩ／Ｏデータモデル２２は、Ｓｐｅｃｍａｎ（登録商標）機能プログラミング環境（米国カリフォルニア州マウンテンビュー、ベリシティ・デザイン社）によって提供され米国特許出願第０９／０２０７９２号に開示されたコード言語であるｅコードで構築することが好ましい。そうした実施形態は、ｅコードによるプログラミングの容易さおよび柔軟性のため、好ましい。
【００３３】
ｅコード言語は、ハードウェア指向検証特定的オブジェクト指向プログラミング言語である。この言語のオブジェクトは「ストラクト（ｓｔｒｕｃｔｓ）」のインスタンスであり、それはフィールド、１つまたはそれ以上の機能、または方法を含み、それはフィールド内に格納されたデータに働き、他のオブジェクトと対話する。任意選択的に、制約条件はフィールドに作用することができ、それによって例えばデータの可能な値の範囲を制約することによって、フィールドに格納されたデータを変更することができる。フィールドは、他のストラクト、およびスカラまたはストラクトのリストをはじめ、より複雑な構造を格納するために使用することもできる。
【００３４】
テスト生成のプロセスは、ストラクトおよびフィールドをはじめとするデータ要素にランダム値を埋め込む。各要素の可能なデータ値は、有向テスト生成の方向を提示する制約条件によって任意選択的に制限することができる。動的制約条件の場合、下で図２に関してさらに詳しく述べるように、テスト生成の各インスタンスに対し、選択された特定の解が本発明に従って提供される。この解は、次いで生成データ値の制限を提供するために使用される。
【００３５】
今、図２を見ると、この略ブロック図は、図１からのＡＧＭモジュール２６の例示的であるが好適な実現を示す。図示する通り、ＡＧＭモジュール２６は、静的解析モジュール２９および実行時インタプリタ３１に加えて、制約条件解決エンジン２７を特徴とすることが好ましい。制約条件解決エンジン２７は、制約条件を解決するプロセスを少なくとも部分的に実行時前に静的解析段階で実行することを可能にし、それによって制約条件解決のプロセスをより効果的かつより効率的にする。次いで、実行時中の制約条件解決エンジン２７による実行のための１セットの命令が作成される。したがって、実行時中に制約条件解決が行なわれることを必要とした背景技術とは異なり、本発明は制約条件解決のプロセスを、その後に１セットの命令が作成される静的解析中（実行時前）とこれらの命令が実行される実行時中との２段階に分割することができる。
【００３６】
本発明の好適な実施形態では、制約条件解決エンジン２７は任意選択的に、かつ好ましくは、順序マネージャ２８および依存性グラフマネージャ３０を特徴とすることができる。簡単に言うと、静的解析モジュール２９は、ランダム解を作成するために実行のための命令セットを作成するために制約条件の初期解析を実行する一方、実行時インタプリタ３１はこれらの命令を実行する。
【００３７】
順序マネージャ２８は、双方向および単方向辺のある動的グラフ３２を維持することが好ましい。動的グラフ３２を使用して各制約条件を表わす命令の組込みの順序を決定することがより好ましく、その順序に従って各制約条件は動的グラフ３２のノード間に暗黙に示される。この順序は次に、提供される制約条件のセットに従って決定されることがより好ましい。各ノードは実行される命令を表わす。次に各命令が、従属性グラフマネージャ３０によって決定される制約条件間の関係にしたがって作成される。
【００３８】
次に従属性グラフマネージャ３０は任意選択的に、かつ好ましくは、ノードと制約条件を関連付ける動的２部関係グラフ３４を維持する。各ノードは、特定の変数のフィールド範囲を表わし、それに対してテスト生成プロセスの一部として特定の値を生成することができる。従属性グラフマネージャ３０は、プロセスで関係グラフ３４を使用し、それによって、提供された制約条件のセットの適正値の範囲の一貫性が維持され、それは縮小メカニズム（ｒｅｄｕｃｉｎｇ　ｍｅｃｈａｎｉｓｍ）の一部である。任意選択的に、かつより好適には、従属性グラフマネージャ３０は、一貫性を維持するために検討しなければならない関係の数を低減することができる。
【００３９】
順序マネージャ２８および従属性グラフマネージャ３０は一緒に、静的解析モジュール２９からのコマンドに従って静的な一連の命令を作成することが好ましく、それは実行時インタプリタ３１によって実行されるときに、制約条件のセットの解を提供する。この解は変数の１セットの値として提供されることがより好ましい。前述の通り、ｅ言語を使用してテスト生成のための制約条件およびデータモデルを記述する場合には、これらの値は任意選択的にスカラ、ストラクト、およびフィールドなどのデータ要素を含むことができる。
【００４０】
本発明の好適な実施形態では、順序マネージャ２８のための特定の命令は任意選択的に、ストラクト毎に１つのフレームを生成し、動的制約条件のセットに応じてストラクトの値の生成を管理すること含むが、それに限定されない。これらのコマンドは、特定のストラクトの生成プロセスを開始するＯＭ＿ｓｔａｒｔ＿ｆｒａｍｅコマンド、およびこのストラクトの生成プロセスを終了するＯＭ＿ｃｌｏｓｅ＿ｆｒａｍｅコマンド、静的解析プロシージャからストラクトのための所定のセットのノードに順序グラフノードを生成するためのＯＭ＿ｃｒｅａｔｅ＿ｎｏｄｅｓ、所定のセットのノードの順序グラフ辺を生成するためのＯＭ＿ｃｒｅａｔｅ＿ｅｄｇｅｓ、グラフの維持された順序で次のノードを返すためのＯＭ＿ｇｅｔ＿ｎｅｘｔを含む。
【００４１】
従属性グラフマネージャ３０の特定の命令は任意選択的に、関係グラフ３４に制約条件ノードおよびパラメータノード（パラメータノードは制約条件に関連するエンティティまたはパラメータである）を生成するためのＤＧＭ＿ｃｒｅａｔｅ＿ｃｏｎｓｔｒａｉｎｔ、１セットのパラメータノードにそれらの範囲が変更されたと標識するＤＧＭ＿ｍａｒｋ＿ａｓ＿ｃｈａｎｇｅｄ、１セットのパラメータノードに簡約機構を適用し、それによって制約条件ノード間の可能な値の範囲の整合性を維持するＤＧＭ＿ｕｐｄａｔｅ＿ｃｏｎｓｉｓｔｅｎｔ＿ｒａｎｇｅｓ、現行バージョンの関係グラフ３４で値が真であるか偽であるかを調べるために条件付き制約条件を検査するためのＤＧＭ＿ｔｅｓｔ＿ｃｏｎｓｉｓｔｅｎｃｙ、およびストラクトを表わすノードをストラクトのフィールドを表わす１セットのノードと置換して、古いノードの制約条件辺が新しいノードを指すようにするためのＤＧＭ＿ｅｘｐａｎｄ＿ｓｔｒｕｃｔを含むが、それらに限定されない。
【００４２】
本発明の他の好適な実施形態では、「役割」を生成するためにＡＧＭを使用する。役割のためのＧＭＬシーケンスを生成するときに、前述の動作の幾つかが高レベル命令にグループ化される。次いで各々のそのようなグループは役割の一例を形成する。役割は、そのようなグループに従って命令を実行時に実行することを可能にし、それは正しいランダム解を動的制約条件により効率的に提供する利点を有する。特に、役割は、異なる制約条件がストラクトおよびストラクトの子孫に適用可能であり、異なる文脈で同一ストラクト型が任意選択的に生成されることを可能にする。したがって、役割はストラクトが生成された命令のセットで処理される文脈の表現である。
【００４３】
役割は任意選択的に、かつ、より好ましくは、動的制約条件に対する正しいランダム解を形成するために命令が実行時に実行される方法に従って、統計的に順序付けられないか、または順序付けられる。
【００４４】
役割は、あるストラクト型が異なる文脈で生成され、異なる制約条件がそれおよびその子孫に適用可能である状況を簡素化するために使用することが好ましい。生成役割は、ストラクト型がストラクトの定義およびストラクトが生成される文脈の両方に従って正しく生成されるように、「文脈におけるストラクト型」、または文脈に従ってストラクトを定義することができることに対するこの必要性の概念化である。
【００４５】
本発明に係る静的解析は、任意選択的に、かつ好ましくは、そのような役割を識別し、それらを表現しかつ操作するために複合データ構造を構成する。例えば、前述したコードの文脈で、Ｓ型のストラクトが定義され、別のストラクト´ｓｙｓ´を定義するために次のフィールド定義を使用すると仮定する。
2004513435.tif 000003
【００４６】
上例から、フィールドｓ１およびｓ２が同一ストラクト型Ｓを共用するが、異なる生成役割を持つことが分かる。第１フィールドｓ１は役割＜ｓｙｓ．ｓ１＞のものであり、そのフィールド´ｊ´は３に等しくなるように制約される一方、フィールド´ｓ２´は役割＜ｓｙｓ．ｓ２＞の文脈で生成され、フィールド´ｊ´は１００を超えるように制約される。
【００４７】
こうして、生成された生成役割がしたがってストラクト型の次の情報、すなわち関連フィールド、適用可能な制約条件、初期範囲、順序付け辺を隠微する場合、同一ストラクト型を多くの異なる役割にマップすることができる。関連フィールドは、生成可能なフィールドすなわちこの役割に生成することのできるその型のフィールドのリストである。適用可能な制約条件は、この役割のフィールドに適用される制約条件のリストである。初期範囲は、関連フィールドの統計的に推論される範囲、または可能な値のセットである。順序付け辺は、制約条件が適用される順序であって、関連フィールド間の単または双方向の（適用可能な）制約条件によって暗に示される順序を決定するための辺のセットである。
【００４８】
上記の情報は任意選択的に、かつ、より好ましくは、静的解析段階で各役割の生成ミニ言語プログラムを導出するために使用される。このプログラムは、生成実行時に実行することができ、こうして実行時に動的制約条件を適用する問題の正しいがランダムな解で必要な制約条件を捕捉するコードを特徴とする。
【００４９】
以下で、役割を形成するための異なる型の命令の例について、こうしてひとまとめにグループ化されて各役割を形成する前述のコマンドの出力に従って、各々のそのような命令に必要な入力とともに説明する。
【００５０】
例えば、ＲＯＬＥ＿ｉｎｉｔ＿ｉｎｓｔｒｕｃｔｉｏｎコマンドは次の入力、すなわち前述のコマンドＯＭ＿ｃｒｅａｔｅ＿ｎｏｄｅｓを使用して生成されるノードのセット、前述のコマンドＯＭ＿ｃｒｅａｔｅ＿ｅｄｇｅｓを用いて生成される初期辺の組、およびＤＧＭに加えられる制約条件およびそれらのパラメータのセットを必要とする。ＲＯＬＥ＿ｇｅｎ＿ｆｉｅｌｄ（ｆｉｅｌｄ）コマンドは次の機能、すなわち｛ｆｉｅｌｄ｝の値のコマンドＤＧＭ＿ｕｐｄａｔｅ＿ｃｏｎｓｉｓｔｅｎｔ＿ｒａｎｇｅｓを呼び出し、その整合性のある範囲からフィールドのランダム値を生成し、フィールドをその値に設定し、｛ｆｉｅｌｄ｝のコマンドＤＧＭ＿ｍａｒｋ＿ａｓ＿ｃｈａｎｇｅｄを呼び出すことを実行する。ＤＧＭ＿ｍａｒｋ＿ａｓ＿ｃｈａｎｇｅｄはそのフィールドの状態を変化させ、それに接続されたグラフ構成要素が整合性を持たず、再評価しなければならないことを示す。
【００５１】
ときどきノードは固定された値に依存し、以前に生成されており、あるいは生成不能であることがある。これらは「固定依存（ｄｅｐｅｎｄｅｎｔ　ｏｎ　ｆｉｘｅｄ）」又はｄｏｆと呼ばれる。
【００５２】
さらに別のコマンドはＲＯＬＥ＿ｇｅｎ＿ｔｏｐであり、ここでは次の命令が実行される。すなわちＯＭ＿ｇｅｔ＿ｎｅｘｔを使用してＯＭから次のノードＮを得、取り上げたノードがｄｏｆ標識を持っている場合には、コマンドＯＭ＿ｇｅｔ＿ｄｏｆｓを使用してｄｏｆを得、ｄｏｆの値を計算するためにｄｏｆに関する情報でコマンドＤＧＭ＿ｕｐｄａｔｅ＿ｃｏｎｓｉｓｔｅｎｔ＿ｒａｎｇｅｓを呼び出し、次いでＮの整合性のある値を計算するコマンドＲＯＬＥ＿ｇｅｎ＿ｆｉｅｌｄ（Ｎ）を呼び出す。用語「ｄｏｆ］は、値が以前に生成されたフィールドまたは生成できないフィールドのいずれかに依存する生成可能なフィールドである「固定依存」を表わす。したがって、このコマンドは、そのような必要なフィールドを生成させるか、または生成できないと判断する。
【００５３】
さらに別のそのようなコマンドとしてＲＯＬＥ＿ｅｎｄ＿ｉｎｓｔｒｕｃｔｉｏｎがあり、これはＯＭフレームを閉じ、全ての開いているプロセスが閉じたことを確実にするために検査を実行するなどのブックキーピングを処理するために使用される。特にこのコマンドは、この特定の文脈または「役割」のこの特定のストラクトの生成プロセスを終了させる。
【００５４】
前述の通り、役割は統計的に順序付けられるか、または順序つけられないかのいずれかとすることができる。上記の高レベル命令を使用して、役割はこれら２つの形式の１つを有するシーケンスにマップされる。例えば、統計的に順序付けられる役割は次の構造を持つことが好ましい。
【００５５】
ＲＯＬＥ＿ｉｎｉｔ＿ｉｎｓｔｒｕｃｔｉｏｎ（ノード、辺、制約条件）
ＲＯＬＥ＿ｇｅｎ＿ｆｉｅｌｄ（ｆｉｅｌｄ１）
ＲＯＬＥ＿ｇｅｎ＿ｆｉｅｌｄ（ｆｉｅｌｄ２）
…
ＲＯＬＥ＿ｇｅｎ＿ｆｉｅｌｄ（ｆｉｅｌｄＮ）
ＲＯＬＥ＿ｅｎｄ＿ｉｎｓｔｒｕｃｔｉｏｎ
【００５６】
対照的に、統計的に順序付けられない役割は次の異なる構造を持つことが好ましい。
ＲＯＬＥ＿ｉｎｉｔ＿ｉｎｓｔｒｕｃｔｉｏｎ（ノード、辺、制約条件）
（数字）＊ＲＯＬＥ＿ｇｅｎ＿ｔｏｐ
ＲＯＬＥ＿ｅｎｄ＿ｉｎｓｔｒｕｃｔｉｏｎ
【００５７】
前述の通り、異なる適用可能な制約条件により、異なる文脈で同一ストラクト型が生成されるので、ＧＭＬシーケンスはストラクト型自体のプロパティではなく、むしろそれにしたがってシーケンスが生成される役割のプロパティである。
【００５８】
図３は、以下でさらに詳述する方法に従って、特定のセットの制約条件の結果生成された例示的従属性グラフ３６の略ブロック図を示す。簡単にいうと、この例の場合、フィールドの順序は次の通り、すなわちＸ、Ｙ、Ｚ、Ａ、Ｂ、Ｃである。次のセットの制約条件を使用する。
Ｘ＞Ｙを維持する
Ｙ＝＝Ｚを維持する
Ｙ＝＝Ｆ（）を維持する
Ａ＝＝Ｂを維持する
（Ｘ＞０）＝＞ｂ＝＝Ｇ（Ｃ）を維持する
ここでＦ（）およびＧ（）は関数である。
【００５９】
この制約条件システムで関数ＯＭ＿ｇｅｔ＿ｎｅｘｔ（）を呼び出すと、フィールドＡ３８が返されるが、フィールドＹ４０のため、ｄｏｆ識別が付いている。フィールドＹ４０は関数Ｆ（）４２を用いて計算される。フィールドＹ４０の計算値はフィールドＺ４３およびＸ４４に伝搬される。この時点で、フィールドＸ４４の値が生成される。フィールドＹ４０はすでに最終値を受け取っている。次にフィールドＺ４３の値が計算される。
【００６０】
Ｘの値に応じて、Ｘ＞０の場合、ＯＭ＿ｃｒｅａｔｅ＿ｅｄｇｅを呼び出すことによってＣからＢへ単方向辺４６が加えられる。この場合、ＯＭ＿ｇｅｔ＿ｎｅｘｔ（）を呼び出すと、辺のため、フィールドＣ４８が返される。次に、フィールドＣ４８の最終値が生成される。この時点でフィールドＢ５０はｄｏｆと標識され、固定値に依存する。ＯＭ＿ｇｅｔ＿ｎｅｘｔ（）を呼び出すと、ｄｏｆ標識付きでフィールドＡ３８が返される。返されたｄｏｆはフィールドＢ５０であり、それはＧ（Ｃ）を用いて評価され、そうして得られた値がフィールドＡ３８に伝搬される。この時点で、フィールドＡ３８の値が生成され、プロセスは終了する。
【００６１】
フィールドＸ４４の値が０未満であるように生成された場合、生成順序はフィールドの順序であるＡ、Ｂ、Ｃとなる。
【００６２】
本発明を限定された数の実施形態に関連して説明したが、本発明の多くの変形例、変化例、および他の適用例が可能であることは理解されるであろう。
【図面の簡単な説明】
【図１】
本発明に係る例示的システムを示す略ブロック図である。
【図２】
図１のＡＧＭをより詳しく示す略ブロック図である。
【図３】
本発明の方法に係る構成後のグラフの略ブロック図である。
【図１】
2004513435.tif 000004
【図２】
2004513435.tif 000005
【図３】
2004513435.tif 000006
【国際公開パンフレット】
2004513435.tif 000007
2004513435.tif 000008
2004513435.tif 000009
2004513435.tif 000010
2004513435.tif 000011
2004513435.tif 000012
2004513435.tif 000013
2004513435.tif 000014
2004513435.tif 000015
2004513435.tif 000016
2004513435.tif 000017
2004513435.tif 000018
2004513435.tif 000019
2004513435.tif 000020
2004513435.tif 000021
2004513435.tif 000022
2004513435.tif 000023
2004513435.tif 000024
2004513435.tif 000025
2004513435.tif 000026
2004513435.tif 000027
2004513435.tif 000028
2004513435.tif 000029
2004513435.tif 000030
2004513435.tif 000031
2004513435.tif 000032
2004513435.tif 000033
2004513435.tif 000034
2004513435.tif 000035
2004513435.tif 000036
2004513435.tif 000037
2004513435.tif 000038
【国際公開パンフレット（コレクトバージョン）】
2004513435.tif 000039
2004513435.tif 000040
【国際調査報告】
2004513435.tif 000041
2004513435.tif 000042
2004513435.tif 000043