(57)【特許請求の範囲】
【請求項１】
テスト中のデバイス（ＤＵＴ）のシミュレーションモデルで実行される設計テスト検証プロセス中にテスト環境で前記テスト中のデバイス（ＤＵＴ）のための設計の機能カバレージをカバレージメトリックに従って決定するための方法であって、カバレージメトリックが複数のカバレージ項目から構築されており、方法が、
カバレージグループを前記設計から獲得し、ただし、前記カバレージグループは、所定の入力についての設計の到達可能な空間ステートを含み、前記カバレージグループは、設計テスト検証プロセス中の検討のためのものであり、前記カバレージグループは、少なくとも一つの機能結果を含む、
前記所定の入力を提供するために、１セットの入力テスト値を設計テスト検証プロセスに提供し、
前記セットの入力テスト値で設計テスト検証プロセスを実行して各機能結果についての値をそれぞれ獲得し、
前記カバレージメトリックを使用して、得られたカバレージ目標を前記値と比較することによって、各機能結果から得た前記それぞれの値に従って前記カバレージグループで得られたカバレージを検討し、そして
テストカバレージを適応するように改善するために、前記比較に従って前記セットの入力テスト値を自動的に変更すること、ただし、前記変更することは、異なるテストからのユーザに与えられた制約条件を重ね合わせること、及び前記得られたカバレージ目標で前記メトリックを最大化するために計算された制約条件と、ユーザ定義制約条件とを重ね合わせることからなる群から選択される少なくとも一つの作業を使用することを含み、前記作業は、生成確率をゆがめるための少なくとも一つのランダム化ポリシーと組み合わせられる
を含む方法。
【請求項２】
前記カバレージグループが手動で提供される記述から得られることを特徴とする請求項１に記載の方法。
【請求項３】
前記カバレージグループがＤＵＴ回路設計仕様から得られることを特徴とする請求項１に記載の方法。
【請求項４】
前記カバレージグループがテスト環境により定義されるテストから得られることを特徴とする請求項１に記載の方法。
【請求項５】
各機能カバレージ結果がＤＵＴ回路設計およびテスト環境の少なくとも１つの値保持要素および前記値を標本化するための標本化条件を定義する式であり、前記標本化条件が標本化された値を形成するよう満たされる場合、設計テスト検証プロセスが前記値を標本化することによって実行され、かつカバレージが前記標本化された値に従って測定されることを特徴とする請求項１に記載の方法。
【請求項６】
テスト中のデバイス（ＤＵＴ）のシミュレーションモデルで実行される設計テスト検証プロセス中にテスト環境で前記テスト中のデバイス（ＤＵＴ）のための設計の機能カバレージを決定するためのシステムであって、システムはカバレージメトリックを利用し、カバレージメトリックが、前記設計から獲得された複数の機能カバレージ結果から構築され、各機能カバレージ結果が変数を有しており、変数の値が設計テスト検証プロセスのテスト毎に決定され、システムが、
（ａ）前記結果変数のうちの少なくとも１つの値を制約するための少なくとも１つの制約条件を受け取り、かつＤＵＴ回路設計仕様に従ってテストを生成するためのテストジェネレータと、
（ｂ）生成されたテストを実行し、かつ実行時にテストからデータを収集するための実行時システムと、
（ｃ）前記テストジェネレータからテストを受け取り、かつ実行時に収集された前記データを受け取るためのマキシマイザであって、テスト、前記カバレージメトリック、および実行時に収集された前記データに従って、テストカバレージを適応するように改善するための追加テストを生成するマキシマイザ、ただし、前記追加テストを生成することは、異なるテストからのユーザに与えられた制約条件を重ね合わせること、及び前記得られたカバレージ目標で前記メトリックを最大化するために計算された制約条件と、ユーザ定義制約条件とを重ね合わせることからなる群から選択される少なくとも一つの作業を使用することを含み、前記作業は、生成確率をゆがめるための少なくとも一つのランダム化ポリシーと組み合わせられる
を備えたシステム。
【請求項７】
（ｄ）ＤＵＴ回路設計仕様に関する情報を受け取り、かつ前記情報を解析する解析モジュールであって、前記解析された情報が前記追加テストを生成するために前記マキシマイザに渡される解析モジュール、
をさらに含む請求項６に記載のシステム。
【請求項８】
前記解析モジュールが前のテストから手動で決定された情報を受け取り、前記追加テストを生成するために前記マキシマイザに前記情報を渡すために前記情報を解析するように構成されていることを特徴とする請求項７に記載のシステム。
【請求項９】
テスト中のデバイス（ＤＵＴ）のシミュレーションモデルで実行される設計テスト検証プロセス中にテスト環境で前記テスト中のデバイス（ＤＵＴ）のための設計の機能カバレージをカバレージメトリックに従って決定するための方法であって、機能カバレージがカバレージメトリックに従って決定され、カバレージメトリックが、前記設計から獲得された複数のカバレージ結果から構築されており、各カバレージ結果が標本化されるための変数を有し、方法が
１セットの入力値を設計テスト検証プロセスに提供して生成テストを形成し、
前記生成テストの前記セットの入力テスト値で設計テスト検証プロセスを実行して標本化条件に従って各カバレージ結果の変数の値を獲得し、
各カバレージ結果から得た前記値をカバレージ目標と比較することによって、得られたカバレージを検討し、そして
前記検討に従って前記セットの入力テスト値を自動的に変更して、テストカバレージを適応するように改善するための新しい生成テストを形成すること、ただし、前記変更することは、異なるテストからのユーザに与えられた制約条件を重ね合わせること、及び前記得られたカバレージ目標で前記メトリックを最大化するために計算された制約条件と、ユーザ定義制約条件とを重ね合わせることからなる群から選択される少なくとも一つの作業を使用することを含み、前記作業は、生成確率をゆがめるための少なくとも一つのランダム化ポリシーと組み合わせられる
を含む方法。
【請求項１０】
少なくとも１つのカバレージ結果が機能カバレージ項目であって、前記機能カバレージ項目の変数が変数の前記値を標本化するために標本化条件に従って標本化されることを特徴とする請求項９に記載の方法。
【請求項１１】
前記新しい生成テストが少なくとも１つのカバレージ目標に従って形成され、前記少なくとも１つのカバレージ目標がＤＵＴ回路設計およびテスト環境の少なくとも１つの解析に従って自動的に決定されることを特徴とする請求項１０に記載の方法。
【請求項１２】
前記解析はＤＵＴ構造から前記少なくとも１つのカバレージ目標を抽出するためにＤＵＴ回路設計仕様に実行されることを特徴とする請求項１１に記載の方法。
【請求項１３】
前記少なくとも１つのカバレージ目標がテスト環境から手動で定義されることを特徴とする請求項１１に記載の方法。
【請求項１４】
複数のカバレージ目標がテスト環境から手動で定義され、追加カバレージ目標が前記手動で定義されたカバレージ目標の少なくとも２つの組合せから自動的に決定されることを特徴とする請求項１３に記載の方法。
【請求項１５】
前記少なくとも１つのカバレージ目標が少なくとも１つのカバレージ項目の各変数のデータ型の自動解析に従って定義されることを特徴とする請求項１１に記載の方法。
【請求項１６】
前記自動解析が少なくとも１つのカバレージ項目の各変数の可能な値の少なくとも１つの境界を決定し、前記少なくとも１つのカバレージ目標が前記少なくとも１つの境界に従って決定されることを特徴とする請求項１５に記載の方法。
【請求項１７】
前記自動解析が、少なくとも１つの変数の値を決定するためにテスト環境を解析し、前記値に従って前記少なくとも１つのカバレージ目標を定義することによって実行されることを特徴とする請求項１５に記載の方法。
【請求項１８】
前記値が前記少なくとも１つの変数の可能な値の境界を定義することを特徴とする請求項１７に記載の方法。
【請求項１９】
前記可能な値が前記少なくとも１つの変数の値の範囲内に含まれ、前記境界が前記範囲を分割することを特徴とする請求項１８に記載の方法。
【請求項２０】
複数のカバレージ目標が前記自動解析に従って定義され、追加カバレージ目標が前記自動的に定義されたカバレージ目標の少なくとも２つの組合せから自動的に決定されることを特徴とする請求項１５に記載の方法。
【請求項２１】
少なくとも１つのカバレージ目標がテスト環境から手動で定義され、追加カバレージ目標が自動的に定義されたカバレージ目標と前記手動で定義されたカバレージ目標の組合せから自動的に決定されることを特徴とする請求項１５に記載の方法。
【請求項２２】
前記組合せが前記自動的に定義されたカバレージ目標と前記手動で定義されたカバレージ目標のカルテシアン積から決定され、前記自動で定義されたカバレージ目標がＮ個の可能な値を持ち、前記手動で定義されたカバレージ目標がＭ個の可能な値を持つ場合、前記組合せはＭ×Ｎ個の値の行列であることを特徴とする請求項２１に記載の方法。
【請求項２３】
前記新しい生成テストが少なくとも１つの変数の値を制約するための少なくとも１つの制約条件を含むことを特徴とする請求項１１に記載の方法。
【請求項２４】
前記少なくとも１つの制約条件が前の生成テストから手動で決定された制約条件から引き出されることを特徴とする請求項２３に記載の方法。
【請求項２５】
少なくとも１つの追加制約条件が前記少なくとも１つのカバレージ目標に従って作成されることを特徴とする請求項２３に記載の方法。
【請求項２６】
少なくとも１つの制約条件が前の生成テストおよび特定のカバレージ目標から手動で決定された制約条件の組合せに従って作成されることを特徴とする請求項２３に記載の方法。
【請求項２７】
前記少なくとも１つの制約条件の前記新しい生成テストの生成への効果が生成確率に影響を及ぼすためのランダム化ポリシーに従って少なくとも部分的に決定されることを特徴とする請求項２３に記載の方法。
【発明の詳細な説明】
【０００１】
関連出願の相互参照
本願は、本願と同一人に譲渡された１９９９年６月８日出願の「Ｓｙｓｔｅｍ  ａｎｄ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｍｅａｓｕｒｉｎｇ  Ｔｅｍｐｏｒａｌ  Ｃｏｖｅｒａｇｅ  Ｄｅｔｅｃｔｉｏｎ」と称する同時係属米国特許出願第０９／３２７９６６号の一部継続出願であり、それを参照によって全部ここに組み込む。本願はまた、２０００年６月２日出願の「Ｍｅｔｈｏｄ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  Ｍａｘｉｍｉｚｉｎｇ  Ｔｅｓｔ  Ｃｏｖｅｒａｇｅ」と称する米国特許出願第６０／２０８８２２号の一部継続出願でもあり、それを参照によって全部ここに組み込む。本願はまた、２００１年３月６日出願の「Ｍｅｔｈｏｄ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  Ｍａｘｉｍｉｚｉｎｇ  Ｔｅｓｔ  Ｃｏｖｅｒａｇｅ」と称する米国特許出願第０９／７９９０６５号の優先権をも主張し、それを参照によって全部ここに組み込む。
【０００２】
発明の分野
本発明は、コンピュータソフトウェアに関し、さらに詳しくは、回路設計の機能性を解析し、かつ回路設計の機能の正確性を解析するコンピュータソフトウェアに関する。
【０００３】
発明の背景
電子設計自動化（ＥＤＡ）の分野はよく確立されている。粒度または特定性の様々なレベルで回路を記述するために、多数のソフトウェアツールが使用されている。そうしたツールは、回路を非常に詳細に指定するゲートレベルの記述から、ＶｅｒｉｌｏｇまたはＶＨＤＬなどのハードウェア記述言語で書かれた高レベルの記述までを含む。デバイスのシミュレーションモデルを通して設計を検証するプロセスは、ＶｅｒｉｌｏｇおよびＶＨＤＬの可用性によって促進される。これらの言語は、ハードウェアをより高いレベルの抽象度でも、かつゲートまたはトランジスタとしても両方で記述するように設計されており、したがって設計者が素子および回路の素子間の接続を記述することを可能にする。最近の回路は何百万個ものトランジスタを有するので、単に設計の複雑さを管理するため、特に設計の検証のために、ある種の設計ツールを使用することが不可欠である。
【０００４】
設計の検証は、集積回路、基板、またはシステムレベルのアーキテクチャが、そのデバイスのアーキテクチャの仕様によって定義された要求事項を厳密に実現するかどうかを決定するプロセスである。テスト中のデバイス（ＤＵＴ）の設計検証は実際のデバイスに、またはデバイスのシミュレーションモデルに実行することができる。単に説明のために、いかようにも限定する意図なく、以下の議論は、デバイスのシミュレーションモデルに対して実行されるテストを中心にしている。
【０００５】
様々な型のデバイスの設計およびデバイスアーキテクチャが複雑になるにつれて、設計エラーの見込みが高まる。しかし、デバイスの設計のシミュレーションモデルも作成しかつテストすることがより複雑になっているので、設計の検証もいっそう難しく、かつ時間がかかるようになってきている。
【０００６】
設計検証の問題は、多種多様のデバイスおよびデバイスアーキテクチャの検証およびテストに有用な、広く汎用化可能なツールの欠如によっていっそうひどくなる。典型的な背景技術の検証方法はしばしば特定の設計を有する特定のデバイスに限定されているので、シミュレーションモデル用のそうした検証方法を準備し実行するステップを、各々の新しいデバイスに対して実行しなければならない。
【０００７】
上述した通り、デバイスのシミュレーションモデルを通して設計を検証するプロセスは、ＶｅｒｉｌｏｇおよびＶＨＤＬなどのハードウェア記述言語の可用性によって促進される。結果として生じるデバイスのシミュレーションモデルは、回路の入力に印加される２進数字の文字列であるテストベクトルの形で、入力刺激を受けることができる。次いでシミュレーションモデルは結果を出し、それはデバイスの特定の設計に対し期待された結果に照らして検査される。しかし、これらの言語は一般的に実検証用に設計されていない。したがって、検証エンジニアは、デバイスの設計検証を実行するためにこれらのハードウェア記述言語によって記述されたモデルとインタフェースするために、追加プログラミングコードを書かなければならない。
【０００８】
テスト環境の例として静的および動的テスト環境がある。静的テスト環境は、予め計算されたテストベクトルをＤＵＴのシミュレーションモデルに印加し、かつ／またはシミュレーションモデルの作動後に結果を検査する。加えて、静的テスト環境を使用してシミュレーションモデルから出力された結果を検査する場合には、テストが終了する後までテストの誤りは検出されない。その結果、誤り箇所のデバイスの内部状態は決定できず、そうした内部状態を決定するためには、シミュレーションを再作動する必要がある。この手順はシミュレーションサイクルを浪費し、特に長いテスト中に、かなりの時間を費やすことが必要になるおそれがある。
【０００９】
より有用かつ効率的な型のテストが動的テスト環境である。この型の環境の場合、ＤＵＴのモデルのシミュレーションと同時に、かつシミュレートされたデバイスの状態フィードバックにより潜在的に制御しながら、テストベクトルが生成されるように、１セットのプログラミング命令が書かれる。この手順により、有向無作為生成を実行し、かつデバイスのシミュレーションモデルの状態に対してテスト自体の間に明らかになった効果を感知することが可能になる。したがって、動的テスト生成は明らかに設計の検証に対し多くの利点を有する。
【００１０】
テスト環境の領域内で、静的および動的テスト環境はどちらも、束縛ベクトルまたは事前生成入力によってのみ実現できる。しかし、より強力かつより洗練された実現は、特に機能検証の場合には、回路を指定された通りに実行させるために様々な素子が正しく定義されかつ接続し合うために、テスト生成を使用して環境を生じる。イスラエルのベリシティ社（Ｖｅｒｉｓｉｔｙ  Ｌｔｄ．）によって開発され、カリフォルニア州マウンテンビューのベリシティ・デザイン社（Ｖｅｒｉｓｉｔｙ  Ｄｅｓｉｇｎ，  Ｉｎｃ．）から入手可能なＳｐｅｃｍａｎ  Ｅｌｉｔｅ（登録商標）ソフトウェアは、機能検証を提供する市場の主要製品である。該ソフトウェアの特定の属性は、同一人に譲渡された１９９９年６月８日出願の「Ｓｙｓｔｅｍ  ａｎｄ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｍｅａｓｕｒｉｎｇ  Ｔｅｍｐｏｒａｌ  Ｃｏｖｅｒａｇｅ  Ｄｅｔｅｃｔｉｏｎ」と称する同時係属米国特許出願第０９／３２７９６６号に記載されており、それを全部参照によってここに組み込む。有用な背景情報は、同一人に譲渡された１９９８年２月６日出願の「Ｍｅｔｈｏｄ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  Ｔｅｓｔ  Ｇｅｎｅｒａｔｉｏｎ  Ｄｕｒｉｎｇ  Ｃｉｒｃｕｉｔ  Ｄｅｓｉｇｎ」と称する同時係属米国特許出願第０９／０２０７９２号に提示されている。
【００１１】
米国特許出願第０９／０２０７９２号に開示されたテストジェネレータは、ＶｅｒｉｌｏｇおよびＶＨＤＬのようなハードウェア記述言語と対話し、それより高レベルとして位置する。テスト生成手続きは、ハードウェア指向検証特定的オブジェクト指向プログラミング言語で書かれる。この言語は様々なテストを書くために使用され、次いでそれはテストジェネレータモジュールによってデバイス検証テストを自動的に作成するために使用される。幅広い設計環境はこの言語によってテストされ、検証される。したがって、開示された手続きは汎用化可能であり、しかもエンジニアがプログラムしかつデバッグするのが簡単である。
【００１２】
しかし、人間の介在に対する依存性は、特にテストのカバレージを高めるためには、依然として大きい問題である。「カバレージ」は、ＤＵＴへの特定の入力または入力のセットの全ての考えられる機能および結果を調べるために、設計の到達可能な状態空間を充分に探求する能力の機能である。これらのテストのカバレージは手動で増大することができるが、それはエンジニアによる大量の入力を必要とするので、これは明らかに不利益である。したがって、カバレージを自動的に増大しようと試みる多数の方法が当業界で知られている。
【００１３】
背景技術で知られている「カバレージブースタ」は一般的に、構造解析または「ホワイトボックス」システムと知識ベースシステムとの２つの部類がある。構造解析をベースとするカバレージ増強は、ＤＵＴの構造から、最も典型的にはＤＵＴのゲートレベルの実現からカバレージを導出する。「各ノードをトグルする」などの目標がカバレージ目標として選ばれ、テストジェネレータはＤＵＴ構造の表現に対して作動する様々な探索アルゴリズムに基づくことが最も頻繁である。これらの技術は最初、製造された回路の「縮退」故障を識別するために導入された。一例はシカゴ大学（米国シカゴ）ＨＩＴＥＣなどの生産テストジェネレータであろう（Ｔ．  Ｎｉｅｒｍａｎｎ  ａｎｄ  Ｊ．  Ｈ．  Ｐａｔｅｌ，  “ＨＩＴＥＣ：  Ａ  Ｔｅｓｔ  Ｇｅｎｅｒａｔｉｏｎ  Ｐａｃｋａｇｅ  ｆｏｒ  Ｓｅｑｕｅｎｔｉａｌ  Ｃｉｒｃｕｉｔｓ”，  Ｅｕｒｏｐｅａｎ  Ｄｅｓｉｇｎ  Ａｕｔｏｍａｔｉｏｎ  Ｃｏｎｆ．，  Ａｍｓｔｅｒｄａｍ，  Ｎｅｔｈｅｒｌａｎｄｓ，  ｐｐ．  ２１４−２１８，  Ｆｅｂ．  １９９１に記載されている）。
【００１４】
より近年、より高レベル（例えばレジスタ転送ファレベル）で作動する幾つかのそのようなシステムが出てきた。本質的には、そうしたシステムは同じ技術に基づいており、構造的推論を適用することができるように、ＤＵＴをゲートに統合することが最も頻繁である。
【００１５】
全てのそうした方法の欠点は次の通りである。第一に、カバレージ目標が、要求仕様またはＤＵＴが機能すべき環境によって課せられる制約条件を考慮せず、ＤＵＴのみから選ばれるので、基準が欠如している。この種のテストは、ＤＵＴが実際に仕様通りに機能するかどうかという最も重要な疑問に答えることができない。
【００１６】
第二に、容量の制限に関して、テスト生成アルゴリズムはＤＵＴの解析を必要とするので、ＤＵＴのサイズ（あるいはより正確には、ＤＵＴを実現するために使用される状態変数によって推定される状態空間）を制限しなければならない。現在の技術は一般的に産業設計の小部分に制限される。
【００１７】
知識ベースシステムは、カバレージを自動的に増加する第２型の試みである。これらの場合、システムはＤＵＴの仕様またはＤＵＴが属するデバイス（例えばＣＰＵ）のクラスについて幾らかの知識を有する。カバレージ目標は、期待されるアーキテクチャおよびマイクロアーキテクチャの特徴に応じて設定される。知識ベースは、様々な特徴を標的とする抽象テストを格納する。そうしたテストは、必要な場合にカバレージを高めるために適用される。そうしたシステムの最も顕著な例は、米国特許第５２０２８８９号に開示されているＩＢＭ（米国、Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｂｕｓｉｎｅｓｓ  Ｍａｃｈｉｎｅｓ）のＧｅｎｓｙｓである。
【００１８】
そうしたシステムの主な欠点は、そうした知識ベースを構築する必要性である。知識ベースを構築するコストは、特定のＤＵＴをテストするために必要な手作業を超えるので、そうした手法は、機能が同様であるデバイスの多数の世代にわたって知識ベースを償却することができる場合にのみ、実行可能である。
【００１９】
発明の概要
背景技術は、自動的に発見される機能カバレージ目標を標的にすることによってＤＵＴのテストのカバレージを最大にする方法を教示あるいは示唆していない。加えて、背景技術は、ＤＵＴ状態空間のサイズに影響されず、かつ、どのクラスのＤＵＴにも適用可能な、そうした機能カバレージを増大する方法を教示あるいは示唆していない。さらに、背景技術は、ユーザが手動で実行することができるが、実行する時間または忍耐力が彼らに無い、多くの境界条件がクロスする「力ずく」型のテストを実行する方法を教示あるいは示唆していない。また、背景技術は、だんだんよくなっていく機能カバレージを自動的に得るために、機能テストを実行するそうした方法の性能を反復的かつ自動的に調整する方法も教示あるいは示唆していない。
【００２０】
本発明は、カバレージの穴を識別し、これらの領域をテストするために入力プロセスを変更し、次いでプロセスを反復的に繰り返して、テストカバレージを改善し続けることによって、テストカバレージを改善する。
【００２１】
本発明の方法はユーザ生成テストで始まることが好ましく、そこからカバレージ情報を、例えば環境アーキテクチャファイルから、かつ／または他の既存のカバレージおよびテスト情報源から抽出することがさらに好ましい。そうした情報は任意選択的にかつ好ましくは、カバレージグループ、項目、およびバケットを含む。次にテストを実行し、結果を解析する。次いで、これらのカバレージの穴を覆うために、テスト記述を拡張することによってカバレージの穴を自動的に標的にする。本発明の方法は任意選択的に、かつ最も好ましくは、ユーザの当初のテストを変更するのではなく、代わりにテストの別個のバージョンに制約条件を付加して、ユーザの当初の制約条件が別個に格納されるようにする。また、本発明の方法は、制約条件の特定のセットによりテストが特定の値または値の範囲に達することが妨げられることを決定することができるという利点を有し、それに応じて機能することができる。
【００２２】
制約条件が付加される順序および様式は、ランダムポリシーによって支配されることが好ましい。カバレージの穴は、前出願に記載されたカバレージの等級付け方式に従って埋めることが好ましい。等級が上がるにつれて、カバレージが適切になる確率が高まるので、追加カバレージが要求される確率は低下する。したがって、これらの穴は等級の低い方から高い方に満たしていくことが好ましい。
【００２３】
任意選択的に、本発明の方法は、任意のテストの構造／特徴をテストによって得られたカバレージの増加に相関させることによってカバレージを高めるように「学習する」ことができる。そうした相関は、解析法を使用してだけでなく、遺伝的アルゴリズムまたはニューラルネットワークなどの適応法でも出すことができる。
【００２４】
本発明では、テスト検証プロセス中にテスト環境でテスト中のデバイス（ＤＵＴ）の機能カバレージを決定するための方法であって、カバレージメトリック（ｃｏｖｅｒａｇｅ  ｍｅｔｒｉｃ）が複数のカバレージ項目から構築されており、テスト検証プロセス中に少なくとも１つの機能カバレージ項目を含むカバレージグループを検討のために獲得し、１セットの入力値をテスト検証プロセスに提供し、該セットの入力テスト値でテスト検証プロセスを実行して各カバレージ項目の値を獲得し、各カバレージ項目から得た値に従ってカバレージグループで得たカバレージを検討し、該セットの入力テスト値を自動的に変更することを含む方法を提供する。
【００２５】
本発明の別の実施形態では、テスト検証プロセス中にテスト環境でテスト中のデバイス（ＤＵＴ）の機能カバレージを決定するための方法であって、機能カバレージがカバレージメトリックに従って決定され、カバレージメトリックが複数のカバレージ項目から構築され、各カバレージ項目が標本化のための変数を有しており、１セットの入力値をテスト検証プロセスに提供して生成テストを形成し、生成テストの該セットの入力テスト値でテスト検証プロセスを実行して標本化条件に従って各カバレージ項目の変数の値を獲得し、各カバレージ項目から得た値に従ってカバレージメトリックで得たカバレージを検討し、該セットの入力テスト値を自動的に変更して新しい生成テストを形成することを含む方法を提供する。
【００２６】
本発明のさらに別の実施形態では、テスト検証プロセス中にテスト環境でテスト中のデバイス（ＤＵＴ）の機能カバレージを決定するためのシステムであって、カバレージメトリックが複数のカバレージ項目から構築され、各カバレージ項目が変数を有しており、変数の値がテスト検証プロセスのテスト毎に決定され、（ａ）少なくとも１つの変数の値を制約するための少なくとも１つの制約条件を受け取り、かつＤＵＴに従ってテストを生成するためのテストジェネレータと、（ｂ）テストを実行し、かつ実行時にデータを収集するための実行時システムと、（ｃ）ＤＵＴに関する情報を受け取り、テストジェネレータからテストを受け取り、かつ実行時に収集されたデータを受け取るためのマキシマイザであって、テスト、ＤＵＴ、および実行時に収集されたデータに従って追加テストを生成するマキシマイザとを備えたシステムを提供する。
【００２７】
図面の簡単な説明
添付の図面は発明の特定の態様を図示するが、いかなる点においても限定を意味するものではない。
図１は、ＡＴＭスイッチの代表的設計を示し、該設計に入力を提供しかつそこからの出力をモニタする、テストジェネレータと制約条件の相互作用を示す。機能カバレージの場合と同様に時間チェックが適用され、その結果がスコアボードに記入されてカバレージレポートが提供される。
図２は、適用できる一連のテストと、テスト１、２または３が評価された回数を示すヒストグラムとを示す。
図３Ａは、伝統的なＳｐｅｃｍａｎ「ｅ」テスト環境と、カバレージマキシマイザを追加し、Ｓｐｅｃｍａｎ  Ｅｌｉｔｅソフトウェアを通して対話してＤＵＴの機能の正確さをテストするＤＵＴ（物理的またはシミュレーションまたは両方）とを示す。
図３Ｂは、図３Ａのマキシマイザの典型であるが好適な実現をより詳細に示す。
図４は、任意選択的であるが好適な静的解析による動的制約条件評価を追加した、図３のシステムを示す。
図５は、図４の抽象生成マシンをより詳細に示す。
【００２８】
好適な実施形態の詳細な説明
本発明は、カバレージの穴を識別し、入力プロセスを変更してこれらの領域をテストし、次いでプロセスを反復的に繰り返してテストカバレージを改善し続けることによって、テストカバレージを改善する。
【００２９】
本発明の方法は、ユーザ生成テストで始まることが好ましく、そこからカバレージ情報を、例えば環境アーキテクチャファイルから、かつ／または他の既存のカバレージおよびテスト情報源から抽出することがさらに好ましい。そうした情報は任意選択的にかつ好ましくは、カバレージグループ、項目、およびバケットを含む。さらに、カバレージ情報をＤＵＴの実現から抽出することが好ましい。次に、テストを実行し、結果を解析する。次いで、任意選択的に追加制約条件によりテスト記述を拡張することによって、カバレージの穴を自動的に検出して標的とする。本発明の方法は任意選択的に、かつ最も好ましくは、ユーザの当初のテストを変更せず、代わりにテストの別個のバージョンに制約条件を付加して、ユーザの当初の制約条件が別個に格納されるようにする。また、本発明の方法は、特定のセットの制約条件によりテストが特定の値または値の範囲に達することが妨げられることを決定することができるという利点を有し、それに応じて機能することができる（例えば、妨げている制約条件を取り除いたテストのコピーを作成するか、あるいは到達できないカバレージ目標についてユーザに通知する）。
【００３０】
特に、本発明は、ある意味で「優良」であることが知られている（またはそれらの「優良」度が知られている）１セットのテスト記述（またはテストインスタンス）が提供された場合に、「より優良」である（またはそうである確率が高い）別のセットが構築かつ／または識別されるように、改善されたカバレージのテストを構築する問題を解決するのに有用である。
【００３１】
（テストインスタンスの）「優良さ」は一般的に何らかのカバレージ尺度に関連付けられるので、「優良さ」およびカバレージの言及は相互に置き換えることができる。したがって、より優れたカバレージを得ることが本発明の方法の目標であることは明らかである。「優良さ」は（任意のテストセットの）セット特性または各テストの個別特性とみなすことができる。
【００３２】
そのカバレージを得る方法は任意選択的に３通りある。外的方法すなわち純粋にユーザ定義によるもの、自動的方法すなわち純粋にテストおよびＤＵＴから導出されるもの、ならびに推論方法すなわちユーザ定義カバレージから得られ、そこからいっそう興味深いカバレージポイントおよび尺度が計算（導出）されるものである。遷移独立結果のみならず、可到達性情報および一次入力遷移関係をも得るためにステートマシン解析技術を適用するなど、ＤＵＴから推論カバレージを導出するための多数の可能性が生じる（これはテストケースの組合せを助長し指示することができるかもしれない、以下参照）。
【００３３】
本発明の方法は任意選択的に、かつ好ましくは、２つの主要な構成要素、すなわち（ａ）カバレージ目標発見メカニズム、および（ｂ）テスト生成メカニズムを有する。目標は一般的に、何らかの最大化または最適化プロセスの候補として明示的にまたは暗黙に指定することのできる何かとして記述することができる。目標は任意選択的に、かつ好ましくは２つのカテゴリに分類される。第１のカテゴリは直接制御可能な目標であり、それは基本的に、時相式と制約条件の組合せを用いてＳｐｅｃｍａｎによって課せられ（かつ解かれ）るＤＵＴへの導入刺激に関する述語である。第２のカテゴリは他の全ての型の目標を含み、それは複雑さからジェネレータによって解くことのできない刺激だけの述語として（例えばｃｒｃエラーのあるパケット）、またはＤＵＴ内部状態およびトレースに基づくかまたは（例えばクロスカバレージを通して）それらを他の「目標」に関連付ける述語として、さらに記述することができる。
【００３４】
どのテストでもユーザが明示的に定義する全てのカバレージポイントは「目標」となるかもしれないが、多くの理由から目標は「カバレージポイント」と同一ではないことに注意されたい。第一に、テストの定義の解析から新しい目標が発生するかもしれない。第二に、テストランの解析から新しい目標が発生するかもしれない。第三に、ＤＵＴの解析から新しい目標が発生するかもしれない。
【００３５】
本発明の方法は任意選択に、かつ好ましくは、次のカバレージ目標発見メカニズムを採用することができる。第一に、カバレージ目標は任意選択的に、先行技術と同様に、例えばＤＵＴ内に埋め込まれたステートマシンの全ての状態を網羅してＤＵＴ構造を解析することによって、得ることができる。これらの目標は任意選択的に、ユーザが例えばｅアーキテクチャファイルで定義するカバレージポイントとして明示的に定義することもできる。これらの目標はまた任意選択的に、例えばそれらの境界値がカバレージ目標となる有界データ型など、使用されるデータ型に基づいて暗黙に抽出することもできる。加えて、これらの目標は、重要性の値を識別することによって、テスト環境の定義または特定のテストファイルで暗黙に定義することができる。例えば、１つのユーザテストで使用される特定の値割当は、割り当てられたフィールドの範囲の区分を定義する。この区分は、フィールドの新しい目標（バケット）を定義するのに使用される。
【００３６】
任意選択的に、かつより好ましくは、これらの目標は、２つの明示的なカバレージ目標間のクロス、または明示的なカバレージ目標とＤＵＴ構造に基づくカバレージ目標との間のクロス、または暗黙の目標と明示的目標との間のクロス、または暗黙の目標間のクロスとして、上記目標をクロスさせることによって定義することができる。クロスはカバレージ目標のカルテシアン積であるので、目標１がＮ個の値またはバケットを持つことができ、目標２がＭ個の値を持つ場合、クロス乗積はＭ×Ｎ個の値の行列である。
【００３７】
テスト生成メカニズムに関しては、本発明の方法は、一意の制約条件に基づくテストジェネレータを使用することが好ましい。テストは、次の方法の組合せ、すなわち様々なテストからのユーザ提供制約条件のスーパインポーズ、ユーザ定義制約条件と特定のカバレージ目標をめざして計算された制約条件とのスーパインポーズ、および上記のいずれかと生成確率をスキューさせるランダムポリシーとの組合せを使用することによって生成することがより好ましい。
【００３８】
ランダムポリシーはスカラの生成の確率を制御する。一般的にジェネレータは、範囲内の各数が生成される確率と同じ確率を持つ正規分布を使用する。テストに有利な別のポリシーの例として、境界の確率は範囲の真ん中の数より高くなるように範囲境界を強調するポリシーがある。生成テストの異なるスカラ場に、異なるランダムポリシーを一緒に適用することができる。
【００３９】
本発明の好適な実施形態では、これらのテストによって得られる尺度のクロスカバレージを高めるためにテストが組み合わされる。ＤＵＴに関して、テストインスタンスは、その対応する（ＤＵＴ）導入時間に導入される刺激を表わす一連の時間／刺激対にすぎない。しかし、より抽象的なＳｐｅｃｍａｎ（登録商標）ソフトウェアによる本発明の方法の好適な実現では、テストインスタンスは、時相述語が真になった（点火した）ときに存在する制約条件に従って生成されるデータを表わす、一連の時相式／生成動作対にすぎない。テストは任意選択的にこれらの表現の両方と組み合わせることができる。そのような組合せは任意選択的に、いずれかのテストで生成されたものを全て生成し、可能ならば全てが第１テストの場合と同様に生成されるが、同じデータが第２テストで生成される場合には、可能ならば第２テストの制約条件が適用される単純結合；時相「ガード」の非決定的選択とある瞬間に複数のテストを生成すべき場合にテストの非決定的選択を含むことができるが、それらに限定されない。また、これらの組合せはそれ自体任意選択的に組み合わせることができる。そうした組合せは任意選択的に、かつ好ましくは、各テストの暗黙の特徴を組み合わされたテストの目標に関連付ける適応アルゴリズムによって制御される。そうした適応アルゴリズムは、遺伝的アルゴリズム、ニューラルネットワーク、線形プログラミング、および様々な有界探索アルゴリズムを含むが、それらに限定されない。
【００４０】
そうした組合せの効果、およびそれらの成功の確率は、理論的に予測することが非常に難しいが、ＤＵＴのステートマシン特性に密接に関連付けられる。
【００４１】
今、図面を参照すると、図３Ａは、本発明に係るテスト生成のための例示的システムを示す略ブロック図である。図示したシステムは、本発明の説明に必要なテスト生成手続きに一般的機能のみを含むことに注意されない。テスト生成手続き全体のより完全な説明は、前に参照によって組み込んだ米国特許出願第０９／０２０７９２号に見ることができる。また、本発明はシミュレーションモデルの文脈で説明するが、本発明は物理的デバイスの検証にも有用であることにも注意されたい。物理的デバイスおよびシミュレーションモデルはどちらも、テスト環境にあるＤＵＴ（試験中のデバイス）と記述することができる。
【００４２】
本発明に係るテスト生成システム１０は、ＶｅｒｉｌｏｇまたはＶＨＤＬなどのハードウェア記述言語で書かれた、テスト中のデバイス（ＤＵＴ）の設計１４を受け入れることのできるシミュレータ１２を特徴とする。加えて、シミュレータ１２は、実行時にテスト生成手続きを実行するためのテストエンジン１６と対話する。シミュレータ１２とテストエンジン１６との間の対話は、テストエンジン１６がシミュレータ１２に入力を提供し、次にさらなる操作のための入力としてシミュレータ１２から結果を受け取るので、二方向として示される。
【００４３】
テストエンジン１６は、ＤＵＴ１４を実行時にテストするための実行時システム２１に接続されたテストジェネレータ１８を特徴とする。テストジェネレータ１８は１組の制約条件２０およびＩ／Ｏデータモデル２２を受け取り、次いでＤＵＴ１４のテストおよび検証を実行する。本発明では、制約条件２０は少なくとも１組の複数の動的制約条件を含み、それらは次いで、以下でさらに詳しく述べる通り、本発明の方法に従って解かれる。実行時システム２１は、実行時テスト手続き中にシミュレータ１２の駆動および標本化の両方を実行する。
【００４４】
テストおよび検証のプロセス中に、データコレクタ２４は実行時システム２１から１つまたはそれ以上の変数の値を要求する。これらの要求は任意選択的に、実行時システム２１によって発行されるトリガイベントに従って実行される。例えば、時相カバレージに関連するデータを収集する場合、そうしたトリガイベントは任意選択的に、固定され予め定められた標本化時間、および／または例えば時相言語で与えられた時相式によって定義された状態遷移の時相パターンの発生である。データコレクタ２４はテストジェネレータ１８と交信し、テストジェネレータ１８用のＡＰＩ（アプリケーションプログラミングインタフェース）を通して要求されたデータにアクセスすることができる。そうしたＡＰＩは、所望のデータを収集するために要求されるソフトウェア機能呼出しを指定する。この収集データは次いで、データアナライザ２６によって解析される。
【００４５】
本発明では、データアナライザ２６は、テストカバレージを最大にするためのマキシマイザ３００を特徴する。図３Ｂに関連してより詳しく説明する通り、マキシマイザ３００は、任意選択的解析モジュール３０５からＤＵＴ１４に関する情報を受け取り、かつテストジェネレータ１８から様々なテストに関する情報を受け取ることが好ましい。この情報は次いで、新しいテストを作成するため、かつ／または１つまたはそれ以上の制約条件を制約条件２０で調整するために使用される。
【００４６】
本発明の好適な実施形態では、制約条件２０およびＩ／Ｏデータモデル２２は、Ｓｐｅｃｍａｎ（登録商標）機能プログラミング環境（米国カリフォルニア州マウンテンビュー、ベリシティ・デザイン社）によって提供され米国特許出願第０９／０２０７９２号に開示されたコード言語であるｅコードで構築することが好ましい。そうした実施形態は、ｅコードによるプログラミングの容易さおよび柔軟性のため、好ましい。
【００４７】
ｅコード言語は、ハードウェア指向検証特定的オブジェクト指向プログラミング言語である。この言語のオブジェクトは「ストラクト（ｓｔｒｕｃｔｓ）」のインスタンスであり、それはフィールド、１つまたはそれ以上の機能、または方法を含み、それはフィールド内に格納されたデータに働き、他のオブジェクトと対話する。任意選択的に、制約条件はフィールドに作用することができ、それによって例えばデータの可能な値の範囲を制約することによって、フィールドに格納されたデータを変更することができる。フィールドは、他のストラクト、およびスカラまたはストラクトのリストをはじめ、より複雑な構造を格納するために使用することもできる。
【００４８】
テスト生成のプロセスは、ストラクトおよびフィールドをはじめとするデータ要素にランダム値を埋め込む。各要素の可能なデータ値は、有向テスト生成の方向を提示する制約条件によって任意選択的に制限することができる。動的制約条件の場合、下で図４および５に関してさらに詳しく述べるように、テスト生成の各インスタンスに対し、選択された特定の解が本発明に従って提供される。この解は、次いで生成データ値の制限を提供するために使用される。
【００４９】
図３Ｂはマキシマイザ３００の例示的実現をより詳細に示す。マキシマイザ３００は、入力テストセット（図３Ａのテストジェネレータ１８への入力用）および任意選択的に指定目標を受け取るグレーダ（ｇｒａｄｅｒ）３１０を特徴とする。次いでグレーダ３１０は好ましくは、特徴検出、特徴格付け、および目標検出などの機能を実行するために、知識ベース３２０に相談し、それを更新する。特徴検出は、既存のテストセットから、入力目標として指定されない新しい特徴を抽出することによって実行することが好ましい。例えば、一般的刺激におけるカバレージの穴を見つけるためのメカニズムは、そうした動作の一例である。目標検出に関し、これらの新しい目標は任意選択的に次のように所定の組の目標から検出される。第一に、目標は論理的推理によって任意選択的に次の通り抽出することができる。
ＡまたはＢを達成する場合、Ａを達成するか、またはＢを達成することを希望するであろう
ＡおよびＢを達成する場合、Ａを達成し、かつＢを達成することを希望するであろう
Ａ＝＞Ｂであることが知られている場合、Ａを達成するために、（ある確率で）Ａを達成することを希望するであろう
Ａ＝＞〜Ｂであることが知られている場合、Ｂを達成するために〜Ａを達成することを希望するであろう
【００５０】
加えて、新しい目標を発見するために、時相論理的推理を任意選択に次の通り使用することができる。
Ａが最終的にＢを導く場合、Ｂを達成することを希望するであろう（目標がＢであるとき）
ＡおよびＢ（任意の順序で）がＣを導く場合、ＡおよびＢ（どの順序でもよい）を達成しようとするであろう
【００５１】
言うまでもなく、目標をサブ目標に関連付ける特に統計的な過去の経験に関する情報を例えば知識ベース３２０から得るために、過去の経験を使用することもできる。そうした過去の経験は、統計関数として明示的に、あるいは暗黙にミューテーション確率またはニューラルネットワークのシナプス加重として表わすことができる。
【００５２】
次に、コンポーザ３３０は、グレーダ３１０から結果を受け取り、テスト定義を構成および／または変更することが好ましい。コンポーザ３３０はテスト定義を構成および／または変更する前に、知識ベース３２０を任意で調べることもできる。これらのテスト定義は次いで任意選択的に、かつ好ましくはランナ３４０に送られ、それは実際の構成されたテストを格付けし、知識ベース３２０を更新する。
【００５３】
全ての検出された特徴および出現した目標が与えられると仮定して、知識ベース３２０を用いることによって特徴を格付けして、任意の特徴の加重成功を測定し、特定の目標を決定することが好ましい。したがってこの格付けプロセスの内部表現はコンポーザ３３０に送ることが好ましい。
【００５４】
知識ベース３２０自体は、「特徴ビルディングブロック」から目標へのマッピングを含むことが好ましい。これらの特徴ビルディングブロックは、レシピに従って決定することがより好ましい。レシピはテストの一部の内部表現として定義することが好ましい。それは単一情報作用（の等価物）、そうしたものの連続、生成および導入タイミングプロセス（時間消費法）、またはフルブラウンテストとすることができる。
【００５５】
レシピは任意選択的に、いつそれが（特定の目標へ）適用可能であるかを指定する事前条件を持つことができる。それは、複素時相式およびトレース述語（生成トレースおよびＤＵＴトレースの両方）のみならず、単純ブール式とすることもできる。レシピはまた、任意選択的に、かつ、より好ましくは、「これはセルフレジスタＮないし零（Ｎはパラメータ）用のレシピである」または「これは整数バッファＪをオーバフローさせるためのレシピである」（Ｊはパラメータ）などのようにパラメータ化される。
【００５６】
レシピは、（それらがおそらく達成されるように）それらを目標に関連付ける統計的尺度を持つことが好ましい（例えば「このレシピはおそらく（８０％）衝突を導く（言うまでも無く適正な事前条件により）」のように）。
【００５７】
レシピは任意選択的に、構成ルールを用いて他の（サブ）レシピから再帰的に構成することができる。新しいレシピを形成し、かつレシピを組み合わせて新しいレシピを形成する両方のために、同じ構成ルールをレシピに「内部」かつ「外部」から適用することが好ましい。
【００５８】
図３Ａおよび３Ｂは、「入力専用」マキシマイザと記述することのできる、基本セットの機能を有するマキシマイザ３００の任意選択的実施形態を示す。この実現では、全ての指定目標は特徴である。すなわち、全ての目標は「入力言語」で記述され、したがって「可解生成刺激述語」である。また、特徴検出および目標検出はある程度一致する（相互に退化する）。
【００５９】
レシピはロール制約条件およびロール生成トレース述語であることが好ましい。ストラクト型が様々な文脈で生成され、それおよびその派生物に様々な制約条件が適用可能である状況を簡素化するために、ロールを使用することが好ましい。生成ロールは、ストラクト型がストラクトの定義とストラクトが生成される文脈との両方に従って正しく生成されるように、「文脈におけるストラクト型」または文脈に従ってストラクトを定義できることに対するこの要求の概念化である。
【００６０】
任意選択的に、メタランダムポリシーを使用してマキシマイザ３００の実現を拡張することがより好ましい。メタランダムテスト方式は、一般的ヒューリスティックおよび状態定義を用いてロールのフィールドの生成履歴に影響を及ぼすことが可能である。各ロールに対して、そのロールにおける生成の統計的分布を支配するランダムポリシーが割り当てられる。ランダムポリシーの割当はランダムに、または解析を通して行なうことができる。ランダム割当ポリシーを使用する場合、新しいポリシーが選ばれるまで、このポリシーを用いて何回生成が行なわれるかを示すカウントが割り当てられる。この方式は任意選択的に、かつ好ましくは、Ｓｐｅｃｍａｎ（登録商標）など制約条件に基づくテスト生成システムと共に実現される。
【００６１】
シードドメイン、範囲リストＲＬ、およびおそらくシードドメインの生成履歴（の一部）が与えられることを前提として、ランダムポリシーはそのシードドメインに新しい値が生成される方法を決定する。例えば次のポリシーを任意選択的に実現することができる。
ｍｉｎ−ＲＬ内の最小項目がより高い確率を持つ
ｍａｘ−ＲＬ内の最大項目がより高い確率を持つ
メジアン−ＲＬの「真ん中」の項目がより高い確率を持つ
ａｌｔ＿ｍｉｎ＿ｍａｘ−最小から始めて、最小を変更すると最大がより高い確率を持つ
ａｌｔ＿ｍａｘ＿ｍｉｎ−最大から始めて、最小を変更すると最大がより高い確率を持つ
ｍｉｎ＿ｏｒ＿ｍａｘ−最大または最小が無作為により高い確率を持つ
ｅｄｇｅ−ＲＬにおけるエッジである値
ｒａｎｄｏｍ−ランダム
ｄｉｆｆ＿ｔｈｅｎ＿ｐｒｅｖ−可能ならば、前の値と異なる値がより高い確率を持つ
ｅｑ＿ｔｏ＿ｐｒｅｖ−可能ならば、前の値に等しい値がより高い確率を持つ
ｕｎｉｑ−可能ならば、全ての前の値と異なる値がより高い確率を持つ
【００６２】
ポリシーはまた任意選択的に、かつ好ましくは、生成履歴を考慮する能力に関連する多数の特徴を有する。例えば０−ｌｏｏｋ−ｂａｃｋはポリシーが生成履歴を見ることを暗示しないい場合である。１−ｌｏｏｋ−ｂａｃｋはポリシーが最後に生成された値だけを見ることを暗示する場合である。ｕｎｂｏｕｎｄ−ｌｏｏｋ−ｂａｃｋはポリシーが全部の生成ポリシーを見ることを暗示する場合である。
【００６３】
これらのポリシーの決定的例を次に挙げる。
０−ｌｏｏｋ−ｂａｃｋ：
ｍｉｎ＝＝＞ｍｉｎ（ＲＬ）
ｍａｘ＝＝＞ｍａｘ（ＲＬ）
ｍｅｄｉａｎ＝＝＞ｒｌ［ｃｅｉｌｉｎｇ（ｓｉｚｅ（ＲＬ）／２）
１−ｌｏｏｋ−ｂａｃｋ：
ａｌｔ＿ｍｉｎ＿ｍａｘ＝＝＞ｐｒｅｖ  ｗａｓ  ｍｉｎ？  ｍａｘ（ＲＬ）：ｍｉｎ（ＲＬ）
ａｌｔ＿ｍａｘ＿ｍｉｎ＝＝＞ｐｒｅｖ  ｗａｓ  ｍｉｎ？  ｍａｘ（ＲＬ）：ｍｉｎ（ＲＬ）
【００６４】
非決定的ポリシーの場合、０−ｌｏｏｋ−ｂａｃｋは次のように定義される。
ｍｉｎ＿ｏｒ＿ｍａｘ＝＝＞ｒｎｄ（［ｍｉｎ（ＲＬ），ｍａｘ（ＲＬ）］
ｅｄｇｅｓ＝＝＞ｒｎｄ（ｅｄｇｅｓ（ＲＬ））
ｒａｎｄｏｍ＝＝＞ｒｎｄ（ＲＬ）
１−ｌｏｏｋ−ｂａｃｋ：
ｄｉｆｆ＿ｔｈｅｎ＿ｐｒｅｖ＝＝＞ｒｎｄ（ＲＬ［ｐｒｅｖ］）  ｉｆ  ｐｏｓｓｉｂｌｅ
ｅｑ＿ｔｏ＿ｐｒｅｖ＝＝＞［ｐｒｅｖ］  ｉｆ  ｐｏｓｓｉｂｌｅ
ｕｎｂｏｕｎｄ−ｌｏｏｋ−ｂａｃｋ：
ｕｎｉｑ＝＝＞ｒｎｄ（ＲＬ−［ａｌｌ＿ｐｒｅｖ］）ｉｓ  ｐｏｓｓｉｂｌｅ
【００６５】
図４は、動的制約条件を解くためのＡＧＭ（アブストラクト生成マシン）モジュール２６を追加した、図３のシステム１０を示す。ＡＧＭモジュール２６は一連の命令を「ジェネレータミニ言語」（ＧＭＬ）で作成する。これらの命令は次いで、任意のセットの動的制約条件に正しいランダム解を提供するために実行される。簡単に言うと、静的解析モジュール２９は、テストジェネレータ１８と協力して、実行前に動的制約条件の初期解析を実行することが好ましい。この初期解析は、正しいランダム解を生成するための１セットの命令を生成することが好ましい。次に、実行時インタプリタモジュール３１は、これらの命令を受け取り、それらを実行時システム２１と共に実行することが好ましい。ＡＧＭモジュール２６のより詳細な説明を、以下で図５に関連して提供する。
【００６６】
今、図５を見ると、この略ブロック図は、図１からのＡＧＭモジュール２６の例示的であるが好適な実現を示す。図示する通り、ＡＧＭモジュール２６は、静的解析モジュール２９および実行時インタプリタ３１に加えて、制約条件解決エンジン２７を特徴とすることが好ましい。制約解決エンジン２７は、制約条件を解決するプロセスを少なくとも部分的に実行時前に静的解析段階で実行することを可能にし、それによって制約条件解決のプロセスをより効果的かつより効率的にする。次いで、実行時中の制約条件解決エンジン２７による実行のための１セットの命令が作成される。したがって、実行時中に制約条件解決が行なわれることを必要とした背景技術とは異なり、本発明は制約条件解決のプロセスを、その後に１セットの命令が作成される静的解析中（実行時前）とこれらの命令が実行される実行時中との２段階に分割することができる。
【００６７】
本発明の好適な実施形態では、制約条件解決エンジン２７は任意選択的に、かつ好ましくは、順序マネージャ２８および依存性グラフマネージャ３０を特徴とすることができる。簡単に言うと、静的解析モジュール２９は、ランダム解を作成するために実行のための命令セットを作成するために制約条件の初期解析を実行する一方、実行時インタプリタ３１はこれらの命令を実行する。
【００６８】
順序マネージャ２８は、双方向および単方向エッジのある動的グラフ３２を維持することが好ましい。動的グラフ３２を使用して各制約条件を表わす命令の組込みの順序を決定することがより好ましく、その順序に従って各制約条件は動的グラフ３２のノード間に暗黙に示される。この順序は次に、提供される制約条件のセットに従って決定されることがより好ましい。各ノードは実行される命令を表わす。次に各命令が、従属性グラフマネージャ３０によって決定される制約条件間の関係にしたがって作成される。
【００６９】
次に従属性グラフマネージャ３０は任意選択的に、かつ好ましくは、ノードと制約条件を関連付ける動的２部関係グラフ３４を維持する。各ノードは、特定の変数のフィールド範囲を表わし、それに対してテスト生成プロセスの一部として特定の値を生成することができる。従属性グラフマネージャ３０は、プロセスで関係グラフ３４を使用し、それによって、提供された制約条件のセットの適正値の範囲の一貫性が維持され、それは縮小メカニズム（ｒｅｄｕｃｉｎｇ  ｍｅｃｈａｎｉｓｍ）の一部である。任意選択的に、かつより好適には、従属性グラフマネージャ３０は、一貫性を維持するために検討しなければならない関係の数を低減することができる。
【００７０】
順序マネージャ２８および従属性グラフマネージャ３０は一緒に、静的解析モジュール２９からのコマンドに従って静的な一連の命令を作成することが好ましく、それは実行時インタプリタ３１によって実行されるときに、制約条件のセットの解を提供する。この解は変数の１セットの値として提供されることがより好ましい。前述の通り、ｅ言語を使用してテスト生成のための制約条件およびデータモデルを記述する場合には、これらの値は任意選択的にスカラ、ストラクト、およびフィールドなどのデータ要素を含むことができる。
【００７１】
図４および５に示す通り、システム１０は、図３Ａおよび３Ｂのシステムの実現に勝る幾つかの追加的利点を有する。特に、マキシマイザ３００およびＡＧＭ２６は任意選択的に、その後のプロセスによって協力すると記述することができ、そこでマキシマイザ３００によって実行される自動カバレージ抽出が内部データ表現およびＡＧＭ２６からのアルゴリズムを使用してその後のプロセスを実行する。
【００７２】
第一に、生成ロールはカバレージグループに変換される。次に、各ロールにおけるストラクトの生成に対応するイベントを出すための新しいｅコードが生成される。次いで、各生成可能なフィールドがカバレージ項目に変換される。統計解析によって推定される生成可能なフィールドの初期範囲の値は、対応するカバレージ項目の正当な値であると定義される。
【００７３】
次に、他のアルゴリズムに加えて、統計解析によって推定されるロール内のそのフィールドに対する適用可能な制約条件のセットを使用して、そうした項目のバケットが定義および補充される。こうして、マキシマイザ３００の抽出フェーズは任意選択的に、かつより好ましくは、統計解析から導出される次の情報、すなわち生成ロール、ロール内の生成可能なフィールド、ロール内の生成可能なフィールドの初期範囲、およびロールにおける生成可能なフィールドに対して適用可能な制約条件を使用する。
【図面の簡単な説明】
【図１】  ＡＴＭスイッチの代表的設計を示し、該設計に入力を提供しかつそこからの出力をモニタする、テストジェネレータと制約条件の相互作用を示す。
【図２】  適用できる一連のテストと、テスト１、２または３が評価された回数を示すヒストグラムとを示す。
【図３】  図３Ａは伝統的なＳｐｅｃｍａｎ「ｅ」テスト環境と、カバレージマキシマイザを追加し、Ｓｐｅｃｍａｎ  Ｅｌｉｔｅソフトウェアを通して対話してＤＵＴの機能の正確さをテストするＤＵＴ（物理的またはシミュレーションまたは両方）とを示す。図３Ｂは図３Ａのマキシマイザの典型であるが好適な実現をより詳細に示す。
【図４】  任意選択的であるが好適な静的解析による動的制約条件評価を追加した、図３のシステムを示す。
【図５】  図４の抽象生成マシンをより詳細に示す。
【図１】
0005063850.tif 000002
【図２】
0005063850.tif 000003
【図３】
0005063850.tif 000004
0005063850.tif 000005
【図４】
0005063850.tif 000006
【図５】
0005063850.tif 000007