JP2010002370A - パターン抽出プログラム、方法及び装置 - Google Patents

Abstract

【課題】検証対象の内部構造を解析することなく、検証対象を境界条件の近傍で動作させるためのテストパターンを自動的に抽出する。
【解決手段】本テストパターン抽出方法は、テストパターンに対して検証対象により実行される処理の識別子を取得し、テストパターンに対応して上記処理の識別子をテスト結果データ格納部に格納するステップと、テスト結果データ格納部に格納されており且つ上記処理の識別子が異なるテストパターン間で距離を算出し、上記処理の識別子の組毎に当該距離が所定の条件を満たすテストパターンの組を特定し、パターンデータ格納部に格納するステップとを含む。
【選択図】図１

Description

本技術は、ハードウエアの設計検証やソフトウエアのテストを効果的に行う技術の分野に関する。

従来、ハードウエアの設計検証やソフトウエアのテストを行う際には、検証対象の内部構造から境界条件（例えば分岐やループの条件など）を抽出し、その境界条件の近傍値で動作させるための入力パターンを生成するという手法がとられていた。しかし、条件が複雑な場合、境界条件から入力パターンを自動的に又は人手で生成するのは困難であり、効果的なパターンを生成するために多大な時間を要するという問題がある。

また、予め生成したパターンを用いて試験を行い、その際にカバレッジ（例えばラインカバレッジ）を改善するパターンを選択又は生成することで全体のパターン数を減らすような技術もある。しかしながら、検証対象の境界条件まで考慮してはいない。
特開２００１−１８８６９１号公報 特開２００５−３２１８９２号公報 特表２００３−５３５３４３号公報

ハードウエアの設計検証やソフトウエアのテストを効率よく行うためには、検証対象を境界条件の近傍で動作させる必要がある。しかし、従来の技術では、検証対象の内部構造に基づいて入力パターンを生成するため、境界条件の近傍で動作させるための入力パターンを生成するのが非常に困難である。

従って、本技術の目的は、検証対象の内部構造を解析することなく、検証対象を境界条件の近傍で動作させるためのテストパターンを自動的に抽出することである。

本テストパターン抽出方法は、テストパターンに対して検証対象により実行される処理の識別子を取得し、テストパターンに対応して上記処理の識別子をテスト結果データ格納部に格納するステップと、テスト結果データ格納部に格納されており且つ上記処理の識別子が異なるテストパターン間で距離を算出し、上記処理の識別子の組毎に当該距離が所定の条件を満たすテストパターンの組を特定し、パターンデータ格納部に格納するステップとを含む。

検証対象の内部構造を解析することなく、検証対象を境界条件の近傍で動作させるためのテストパターンを自動的に抽出することができる。

本技術の一実施の形態におけるテストパターン抽出装置の機能ブロック図を図１に示す。テストパターン抽出装置は、検証対象のハードウエア又はソフトウエアで実行すべきテストパターン（パターン又は入力パターンとも呼ぶ）又は当該テストパターンを特定するための情報（例えば特定の変数の値域を指定するデータなど）を格納するテストパターン格納部１と、テストパターン格納部１に格納されているデータに従って検証対象５１に対して処理を実行させ、いずれの処理が行われたかを表す処理の識別子を取得するテスト実行部３と、テスト実行部３によって取得された処理の識別子をテストパターンに対応して格納するテスト結果格納部７と、テスト結果格納部７に格納されているテストパターンについて境界条件の近傍と認められるテストパターンを選択する処理を実施するパターン選択部９と、パターン選択部９によって選択されたテストパターンのデータを格納する解集合データ格納部１１と、解集合データ格納部１１に格納されているテストパターンについてさらに境界条件の近傍となるようなテストパターンを生成する処理を実施するパターン生成部１３と、パターン生成部１３の処理結果を格納する生成パターンデータ格納部１５と、解集合データ格納部１１又は生成パターンデータ格納部１５に格納されているデータを出力する出力部１７とを有する。

検証対象５１は、例えば検証すべきソフトウエアや、例えばＨＤＬ（Hardware Description Language）などによって記述されているハードウエアなどである。テスト実行部３は、例えば検証対象５１のためのデバッガであり、デバッガが通常有するカバレッジ取得機能によって、いずれの処理が行われたかを表す処理の識別子を取得する。

例えば図２に示すような２つの引数をとる関数Ｆ（ｘ，ｙ）をテストする場合を考える。この関数Ｆ（ｘ，ｙ）は、ｙが関数ｇ（ｘ）より大きく且つｘが５より大きい場合には処理Ａを行い、ｙが関数ｇ（ｘ）より大きいがｘが５以下である場合には処理Ｂを行い、ｙが関数ｇ（ｘ）以下であってｘが５より大きい場合には処理Ｃを行い、ｙが関数ｇ（ｘ）以下であってｘが５以下である場合には処理Ｄを行うような関数である。ここで、ｘの取り得る範囲を０≦ｘ≦１０とし、ｙの取り得る範囲を０≦ｙ≦１０とする。

このような場合に、引数の値と処理の対応関係を模式的に示すと図３のようになる。図３のグラフでは、上で述べたｘ及びｙの値域において、ｘ＝５とｙ＝ｇ（ｘ）とで区切られるＡ乃至Ｄの４つの領域のそれぞれで実行される処理が異なる。従って、可能な限り各領域の境界に近いテストパターンを特定することが好ましい。しかしながら、図２に示したような検証対象の構造が常に外部から解析可能であるわけではない。

本実施の形態では、上で述べたｘ及びｙの値域において、例えばランダムにテストパターン（ｘ，ｙ）を生成して、関数Ｆ（ｘ，ｙ）に入力して関数Ｆ（ｘ，ｙ）を実際に動作させて、デバッガのカバレッジ取得機能等を含むテスト実行部３によって、処理Ａ乃至Ｄのいずれの処理が行われたかを特定する。図４に示すように、黒丸はランダムに生成されたｘ及びｙの組み合わせであるテストパターンを示しており、図３に示したような領域Ａ乃至Ｄのいずれに属するかによって処理Ａ乃至Ｄのいずれかが実施される。テスト実行部３は、各テストパターン（黒丸）に対して処理の識別子（Ａ乃至Ｄ）を特定する。

なお、テストパターン格納部１には、図２乃至図４の例では例えば（ｘ，ｙ）を予め用意しておき、格納しておくようにしても良いし、例えば上で述べたｘ及びｙの値域のデータと例えばランダムに発生させるなどといった生成方法などを指定するデータとを格納しておき、テスト実行部３が具体的なテストパターンを随時生成するようにしても良い。

次に、図５乃至図１７を用いて図１に示したテストパターン抽出装置の処理内容について説明する。まず、例えばテスト実行部３は、ユーザから検証対象５１及びテストパターンの指定を受け付ける（ステップＳ１）。テストパターンについては、テストパターン格納部１に格納されているテストパターン又はテストパターンの生成方法を指定するか、テストパターン又はテストパターンの生成方法のデータをテストパターン格納部１に格納して当該データを用いた処理の開始を指示する。

そして、テスト実行部３は、テスト処理を実施する（ステップＳ３）。テスト処理については、図６及び図７を用いて説明する。テスト実行部３は、検証対象５１に、テストパターン格納部１に格納されている各指定テストパターンに対する処理を実行させ、検証対象５１が実行した処理の識別子を特定する（ステップＳ２１）。そして、指定テストパターンと、検証処理５１が実行した処理の識別子とを、テスト結果格納部７に格納する（ステップＳ２３）。例えば、図７に示すようなデータがテスト結果格納部７に格納される。すなわち、テストパターン（例えばｍ１＝（ｘ１，ｙ１））と処理識別子（例えばＡ）とが対応して登録されている。

図５の処理の説明に戻って、次に、パターン選択部９は、第１の近傍値δ1を設定する（ステップＳ５）。例えば、予め設定されている固定の値を用いるようにしても良いし、ユーザに対して入力を求めて、ユーザによって入力された値を用いるようにしてもよい。

そして、パターン選択部９は、パターン選択処理を実施する（ステップＳ７）。パターン選択処理については、図８乃至図１１を用いて説明する。

パターン選択処理は、図８に模式的に示すように、異なる処理（例えば処理Ａと処理Ｃ）を実行させるテストパターンのうち最も距離が短い（すなわち最も近接する）テストパターンｐ０及びｐ１とを抽出する処理である。なお、本実施の形態では、テストパターンｐ０とｐ１の間の距離が、第１の近傍値δ1未満であることも当該テストパターンを抽出する条件である。

そして、パターン選択部９は、テスト結果格納部７に格納されている処理識別子のうち未処理の処理識別子ｓ０を１つ特定する（ステップＳ３１）。また、テスト結果格納部７に格納されている処理識別子のうちｓ０とは異なる未処理の処理識別子ｓ１を１つ特定する（ステップＳ３３）。そして、初期的に、距離を格納する変数mid_distを無限大に設定する（ステップＳ３５）。さらに、テスト結果格納部７に格納されているテストパターンのうち、処理識別子ｓ０に係る未処理のテストパターンｐ０を特定する（ステップＳ３７）。また、テスト結果格納部７に格納されているテストパターンのうち、処理識別子ｓ１に係る未処理のテストパターンｐ１を特定する（ステップＳ３９）。

そして、パターン選択部９は、テストパターンｐ０とｐ１の距離Ｄｉｓｔ（ｐ０，ｐ１）を算出する（ステップＳ４１）。ＸとＹの距離は、例えば以下の式で算出される。

なお、Ｘ及びＹは、ｎ個の要素から構成されているものとする。

そして、Ｄｉｓｔ（ｐ０，ｐ１）がｍｉｎ＿ｄｉｓｔより小さいか判断する（ステップＳ４３）。最初の処理ではｍｉｎ＿ｄｉｓｔは無限大なので、必ずＤｉｓｔ（ｐ０，ｐ１）＜ｍｉｎ＿ｄｉｓｔが成立する。以後は、その都度変わる。

Ｄｉｓｔ（ｐ０，ｐ１）がｍｉｎ＿ｄｉｓｔ以上である場合には端子Ａを介して図１０の処理に移行する。一方、Ｄｉｓｔ（ｐ０，ｐ１）がｍｉｎ＿ｄｉｓｔ未満である場合には、ｍｉｎ＿ｄｉｓｔにＤｉｓｔ（ｐ０，ｐ１）を代入する（ステップＳ４５）。そして、テストパターンｐ０及びｐ１を候補パターンペアｐｐに設定する（ステップＳ４７）。そして、端子Ａを介して図１０の処理に移行する。

図１０の処理の説明に移行して、パターン選択部９は、処理識別子ｓ１に係る全てのテストパターンについて処理したか判断する（ステップＳ４９）。処理識別子ｓ１に係る未処理のテストパターンが存在する場合には、端子Ｂを介して図９のステップＳ３９に戻る。

処理識別子ｓ１に係る全てのテストパターンについて処理した場合には、パターン選択部９は、ｍｉｎ＿ｄｉｓｔが第１の近傍値δ1より小さいか判断する（ステップＳ５１）。ｍｉｎ＿ｄｉｓｔが第１の近傍値δ1以上である場合にはステップＳ５５に移行する。すなわち、距離がｍｉｎ＿ｄｉｓｔとなる、テストパターンｐ０及びｐ１の候補テストパターンペアｐｐを採用しない。図８の例では、例えばテストパターンｃとテストパターンｂとは、確かに異なる処理が行われるテストパターンであるが、あまりに離れているので採用する意味がないと判断する。

一方、ｍｉｎ＿ｄｉｓｔが第１の近傍値δ1未満である場合には、パターン選択部９は、当該ｍｉｎ＿ｄｉｓｔとなる候補テストパターンペアｐｐ（すなわち該当するテストパターンｐ０及びｐ１）並びに候補テストパターンペアについての処理識別子ｓ０及びｓ１を、解集合に追加登録する（ステップＳ５３）。すなわち、図１１に示すようなデータを、解集合データ格納部１１に格納する。

図１１の例では、最終的に残った候補テストパターンペアｐｐに含まれる２つのテストパターンと、対応する２つの処理識別子とが１レコードとして登録される。

その後、パターン選択部９は、処理識別子ｓ０に係る全てのテストパターンについて処理したか判断する（ステップＳ５５）。処理識別子ｓ０に係るテストパターンのうち未処理のテストパターンが存在している場合には端子Ｃを介して図９のステップＳ３７に戻る。

一方、処理識別子ｓ０に係る全てのテストパターンについて処理した場合には、パターン選択部９は、処理識別子ｓ０とは異なる全ての処理識別子について処理したか判断する（ステップＳ５７）。処理識別子ｓ０とは異なる未処理の処理識別子が存在する場合には端子Ｄを介して図９のステップＳ３３に戻る。

また、処理識別子ｓ０とは異なる全ての処理識別子について処理した場合には、パターン選択部９は、処理識別子ｓ０に設定すべき全ての処理識別子について処理したか判断する（ステップＳ５９）。処理識別子ｓ０に設定すべき未処理の処理識別子が存在する場合には、端子Ｅを介して図９のステップＳ３１に戻る。

一方、処理識別子ｓ０に設定すべき全ての処理識別子について処理した場合には元の処理に戻る。

このような処理を実施すれば、異なる処理に係るテストパターンであって距離が最短且つ第１の近傍値δ1未満であるテストパターンを特定することができる。

なお、上で述べた処理フローでは、処理Ａと処理Ｂについて特定したテストパターンと、処理Ｂと処理Ａについて特定されたテストパターンとが一致するが、処理Ａと処理Ｂとの組み合わせと、処理Ｂと処理Ａとの組み合わせとを別に処理している。これを処理Ａと処理Ｂとの組み合わせについてのみ処理するようにしてもよい。

図５の処理の説明に戻って、例えば出力部１７は、次にパターン生成を実施するか判断する（ステップＳ９）。例えば、パターン生成処理を実施することが予め設定されているか、ユーザから指示されているかを判断する。

パターン生成を実施しない場合には、出力部１７は、解集合データ格納部１１に格納されているパターン選択処理の処理結果（例えば図１１）のデータを出力する（ステップＳ１１）。例えば、表示装置に表示する場合もあれば、印刷装置に印刷しても良い。さらに、別のファイルやデータ記憶装置に格納するようにしても良い。

一方、パターン生成を実施する場合には、パターン生成部１３は、第１パターン生成処理を実施する（ステップＳ１３）。第１パターン生成処理については、図１２を用いて説明する。

まず、パターン生成部１３は、第２の近傍値δ2を設定する（ステップＳ６１）。例えば、予め設定されている固定の値を用いるようにしても良いし、ユーザに対して入力を求めて、ユーザによって入力された値を用いるようにしてもよい。

次に、パターン生成部１３は、解集合データ格納部１１に格納されている未処理のテストパターンペアｐｐを１つ特定する（ステップＳ６３）。また、特定されたテストパターンペアｐｐに含まれるテストパターンｐ０及びｐ１を特定する（ステップＳ６５）。

そして、パターン生成部１３は、テストパターンｐ０及びｐ１並びに第２の近傍値δ2について第２パターン生成処理を実施する（ステップＳ６７）。この第２パターン生成処理については、図１３乃至図１６を用いて説明する。

まず、図１３（ａ）及び（ｂ）を用いて、第２パターン生成処理の概要を説明する。ここでは、図１３（ａ）に示すテストパターンａ（＝（ax，ay））とテストパターンｂ（＝（bx，by））とが、解集合データ格納部１１に格納されているものとする。ここで、本実施の形態では、図１３（ｂ）に示すように、テストパターンａとテストパターンｂの中点ｃ1（＝（c1x, c1y）＝（（ax+ab）/2，（ay+by）/2））を算出する。この中点ｃ1に対して検証対象５１がいずれの処理を実施するかを特定する。ここでは中点ｃ1に対しては処理Ｃが実施されるものとする。そうすると、テストパターンｂを中点ｃ1で置き換える。ここで、テストパターンａと中点ｃ1の距離を算出し、第２の近傍値δ2以下となったか判断する。

テストパターンａと中点ｃ1の距離が第２の近傍値δ2より長い場合には、テストパターンａと中点ｃ1の中点ｃ2（＝（c2x, c2y）＝（（ax+c1x）/2，（ay+c1y）/2））を算出する。この中点ｃ2に対して検証対象５１がいずれの処理を実施するかを特定する。ここでは中点ｃ2に対しては処理Ａが実施されるものとする。そうすると、テストパターンａを中点ｃ2で置き換える。ここで、中点ｃ2と中点ｃ1の距離を算出し、第２の近傍値δ2以下となったか判断する。

中点ｃ2と中点ｃ1の距離が第２の近傍値δ2より長い場合には、中点ｃ2と中点ｃ1の中点ｃ3（＝（c3x, c3y）＝（（c2x+c1x）/2，（c2y+c1y）/2））を算出する。この中点ｃ3に対して検証対象５１がいずれの処理を実施するかを特定する。ここでは中点ｃ3に対しては処理Ａが実施されるものとする。そうすると、中点ｃ2を中点ｃ3で置き換える。ここで、中点ｃ3と中点ｃ1の距離を算出し、第２の近傍値δ2以下となったか判断する。本例では、ここで中点ｃ3と中点ｃ1の距離が第２の近傍値δ2以下となったと判断され。第２パターン生成処理が完了する。

以上述べた概要に従って、パターン生成部１３は、テストパターンｐ０とｐ１の距離Ｄｉｓｔ（ｐ０，ｐ１）を算出する（ステップＳ７１）。例えば（１）式で距離を算出する。そして、距離Ｄｉｓｔ（ｐ０，ｐ１）が第２の近傍値δ2を超えているか判断する（ステップＳ７３）。距離Ｄｉｓｔ（ｐ０，ｐ１）が第２の近傍値δ2を超えている場合には、さらに境界に近いテストパターンを生成できるものと判断し、Ｄｉｓｔ（ｐ０，ｐ１）が第２の近傍値δ2以下である場合には、これ以上境界に近いテストパターンを生成する必要はないと判断する。

距離Ｄｉｓｔ（ｐ０，ｐ１）が第２の近傍値δ2を超えている場合には、テストパターンｐ０とｐ１の中点ｐ２を算出する（ステップＳ７５）。Ｘ及びＹの中点は、以下のように算出される。

上で述べたように、ＸもＹもｎ個の要素を含み、それぞれの要素につき平均を算出する。

そして、パターン生成部１３は、テスト実行部３に、テストパターンｐ２に対する処理を実行させ、実行した処理の識別子を特定させる（ステップＳ７７）。特定した処理の識別子については、テスト実行部３から取得する。そして、テストパターンｐ０の処理識別子とテストパターンｐ２の処理識別子が同一であるか判断する（ステップＳ７９）。

テストパターンｐ０の処理識別子とテストパターンｐ２の処理識別子が同一であれば、テストパターンｐ０をテストパターンｐ２で置換する（ステップＳ８１）。そしてステップＳ７１に戻る。

一方、テストパターンｐ０の処理識別子とテストパターンｐ２の処理識別子が異なる場合には、パターン生成部１３は、テストパターンｐ１の処理識別子とテストパターンｐ２の処理識別子が同一であるか判断する（ステップＳ８３）。テストパターンｐ１の処理識別子とテストパターンｐ２の処理識別子が同一である場合には、テストパターンｐ１をテストパターンｐ２で置換する（ステップＳ８５）。そしてステップＳ７１に戻る。

一方、テストパターンｐ１の処理識別子とテストパターンｐ２の処理識別子とが異なる場合には、図１５に示すような状況であると判断される。すなわち、処理Ａが実施される領域と、処理Ｂが実施される領域とが直接接するのではなく、間に処理Ｅが実施される領域が存在しており、中点のテストパターンｐ２が処理Ｅが実施される領域に属する。

このような場合には、パターン生成部１３は、図１５（１）に示すように、テストパターンｐ０及びｐ２について第２パターン生成処理を実施する（ステップＳ８７）。さらに、図１５（２）に示すように、テストパターンｐ１及びｐ２について第２パターン生成処理を実施する（ステップＳ８９）。そして、元の処理に戻る。

このように処理Ａが実施される領域と処理Ｅが実施される領域の境界に近いテストパターンを生成し、処理Ｅが実施される領域と処理Ｂが実施される領域の境界に近いテストパターンを生成する。

ステップＳ７３で、距離Ｄｉｓｔ（ｐ０，ｐ１）が第２の近傍値δ2以下となったと判断された場合には、その際のテストパターンｐ０及びｐ１を生成パターンデータ格納部１５に格納する（ステップＳ９０）。そして元の処理に戻る。

生成パターンデータ格納部１５には、例えば図１６に示されるようなデータが格納される。すなわち、新たに生成された２つのテストパターンが登録される。なお、生成パターンデータ格納部１５には、解集合データ格納部１１に格納されているレコードより多いレコードが登録される場合もある。

以上のような処理を実施することによって、より境界に近いテストパターンを生成することができるようになる。

図１２の処理の説明に戻って、パターン生成部１３は、解集合データ格納部１１に格納されている全てのテストパターンペアについて処理したか判断する（ステップＳ６９）。未処理のテストパターンペアが解集合データ格納部１１に格納されている場合にはステップＳ６３に戻る。一方、全てのテストパターンペアについて処理した場合には、元の処理に戻る。

図５の処理の説明に戻って、出力部１７は、第１パターン生成処理によって生成され且つ生成パターンデータ格納部１５に格納されているテストパターンの組を出力する（ステップＳ１５）。例えば、表示装置に表示する場合もあれば、印刷装置に印刷しても良い。さらに、別のファイルやデータ記憶装置に格納するようにしても良い。

このような処理を行うことによって、検証対象５１の内部構造を解析することなく、検証対象５１を境界条件の近傍で動作させるためのテストパターンを自動的に抽出することができるようになる。

なお、上で述べた実施の形態では、テストパターンに含まれる要素（すなわち変数）については平等に取り扱う例を示した。しかし、制御系変数は、データ系変数に比べて、値の取りうる範囲が小さいため、テストにおいては、より多くの組合せが実行されやすい傾向にある。一方で、データ系変数は、典型的な値の組み合わせのみがテストされる場合が多い。また、検証対象５１中にデータ系変数による処理の分岐がある場合、その境界条件を発生するパターンを生成する労力が、制御系変数による境界条件を発生するパターンを生成する労力よりも大きくなることが多く、データ系変数に依存する境界条件が見逃されることが大きい。

また、制御系変数に比べて、データ系変数は取りうる値の範囲が大きく、テストパターン間の変数値の差分が大きくなる傾向にあり、距離を計算する式においても、データ系変数に依存した境界値が選択されやすくなる。そこで、制御系変数の差分の比重をデータ系変数の差分より小さくすることで、データ系変数の差分に応じてテストパターンペアが選択されやすくする。

例えば図１７に示すような例では、ｘとｙの２つの変数が平等な場合には、Ｄｉｓｔ（Ａ，Ｂ）＝１０＞Ｄｉｓｔ（Ａ，Ｃ）＝１であり、テストパターンＡ及びＣが選択される。

一方、ｘが０以上５以下の制御系変数として重み係数ｗｘ＝１００００と設定し、ｙが０以上１００００以下のデータ系変数として重み係数ｗｙ＝５と設定する。そして、距離WeightedDist(W,X,Y)を以下のように定義する。

なお、重み係数が大きな値ほど、距離が長くなるので、その重み係数に係る変数の比重が小さくなったことになる。

図１７の例では、WeightedDist(W,A,B)＝２２＜WeightedDist(W,A,C)＝１００ということになって、テストパターンＡ及びＣが選択される。

従って、例えばユーザからデータ系変数又は制御系変数並びに重み係数が指定されれば、パターン選択部９及びパターン生成部１３は、上で述べた（２）式に従って距離を算出するようにする。また、値域の狭い変数を制御系変数と特定して、データ系変数の値域を重み係数に指定するようにしても良い。同様に値域の広い変数をデータ系変数と特定して、制御系変数の値域を重み係数に指定するようにしてもよい。

以上本実施の形態を説明したが、実施の形態はこれに限定されるものではない。例えば、図１の機能ブロック図は一例であって、必ずしも実際のプログラムモジュール構成に対応しない場合がある。

さらに処理フローについても処理結果が変わらなければ処理順番を入れ替えたり、並列実行させるようにしても良い。

以上述べた本実施の形態をまとめると以下のとおりである。

本テストパターン抽出方法は、テストパターンに対して検証対象により実行される処理の識別子を取得し、テストパターンに対応して上記処理の識別子をテスト結果データ格納部に格納するステップと、テスト結果データ格納部に格納されており且つ上記処理の識別子が異なる前記テストパターン間で距離を算出し、上記処理の識別子の組毎に当該距離が所定の条件を満たすテストパターンの組を特定し、パターンデータ格納部に格納するステップとを含む。

このようにすれば、検証対象の内部構造を解析することなく、境界条件の近傍のテストパターンの組を自動的に抽出することができるようになる。

また、パターンデータ格納部に格納されているテストパターンの組から、距離がより短いテストパターンの組を生成し、生成パターンデータ格納部に格納する生成ステップをさらに含むようにしても良い。このようにすれば境界により近いテストパターンの組を生成することができるようになる。例えば、距離が第２の閾値未満となるテストパターンの組が得られるまで近づけるようにしても良い。

なお、上で述べた所定の条件が、テストパターン間の距離が上記処理の識別子の組について最小であり且つ所定の閾値未満であるという条件である場合もある。単純に距離が最小という条件のみである場合もある。

さらに、上で述べたパターンデータ格納部には、テストパターンに対応して上記処理の識別子が登録されている場合もある。そして、上で述べた生成ステップが、第１及び第２のテストパターン間の中点の候補テストパターンを算出すると共に、当該候補テストパターンに対して検証対象により実行される処理の識別子を取得するステップと、候補テストパターンについての処理の識別子と、第１及び前記第２のテストパターンについての処理の識別子との異同を判断するステップと、候補テストパターンについての処理の識別子と第１のテストパターンについての処理の識別子とが一致する場合には、第１のテストパターンを候補テストパターンで置換して、第１及び第２のテストパターン間の第２の距離を算出するステップと、候補テストパターンについての上記処理の識別子と第２のテストパターンについての上記処理の識別子とが一致する場合には、第２のテストパターンを候補テストパターンで置換して、第１及び第２のテストパターン間の第２の距離を算出するステップと、第２の距離が第２の所定の閾値未満である場合には、第１及び第２のテストパターンを生成パターンデータ格納部に格納するステップとを含むようにしてもよい。

これによって、自動的に境界により近いテストパターンを生成することができる。

また、上で述べた生成ステップが、候補テストパターンについての上記処理の識別子が第１及び第２のテストパターンについての上記処理の識別子とは異なる場合には、第１のテストパターンと候補テストパターンとについて生成ステップを実施し、第２のテストパターンと候補テストパターンとについて上記生成ステップを実施するステップをさらに含むようにしてもよい。

なお、上で述べた距離は、テストパターンに含まれる変数に応じて重み付けされた距離である場合もある。単純なユークリッド距離ではなく、重み付けを行うことによって、例えばデータ系変数を重視するような距離を算出することによって、適切なテストパターンを選択する又は生成することができるようになる。

なお、上で述べたテストパターン抽出装置は、図１８に示すように、メモリ２５０１（記憶部）とＣＰＵ２５０３（処理部）とハードディスク・ドライブ（ＨＤＤ）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。ＯＳ及びＷｅｂブラウザを含むアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。必要に応じてＣＰＵ２５０３は、表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、必要な動作を行わせる。また、処理途中のデータについては、メモリ２５０１に格納され、必要があればＨＤＤ２５０５に格納される。このようなコンピュータは、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及び必要なアプリケーション・プログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。

（付記１）
テストパターンに対して検証対象により実行される処理の識別子を取得し、前記テストパターンに対応して前記処理の識別子をテスト結果データ格納部に格納するステップと、
前記テスト結果データ格納部に格納されており且つ前記処理の識別子が異なる前記テストパターン間で距離を算出し、前記処理の識別子の組毎に当該距離が所定の条件を満たす前記テストパターンの組を特定し、パターンデータ格納部に格納するステップと、
をコンピュータに実行させるためのテストパターン抽出プログラム。

（付記２）
前記パターンデータ格納部に格納されている前記テストパターンの組から、距離がより短いテストパターンの組を生成し、生成パターンデータ格納部に格納する生成ステップ
をさらに前記コンピュータに実行させるための付記１記載のテストパターン抽出プログラム。

（付記３）
前記所定の条件が、前記テストパターン間の距離が前記処理の識別子の組について最小であり且つ所定の閾値未満であるという条件である
付記１記載のテストパターン抽出プログラム。

（付記４）
前記パターンデータ格納部には、前記テストパターンに対応して前記処理の識別子が登録されており、
前記生成ステップが、
第１及び第２のテストパターン間の中点の候補テストパターンを算出すると共に、当該候補テストパターンに対して前記検証対象により実行される処理の識別子を取得するステップと、
前記候補テストパターンについての前記処理の識別子と、前記第１及び前記第２のテストパターンについての前記処理の識別子との異同を判断するステップと、
前記候補テストパターンについての前記処理の識別子と前記第１のテストパターンについての前記処理の識別子とが一致する場合には、前記第１のテストパターンを前記候補テストパターンで置換して、前記第１及び第２のテストパターン間の第２の距離を算出するステップと、
前記候補テストパターンについての前記処理の識別子と前記第２のテストパターンについての前記処理の識別子とが一致する場合には、前記第２のテストパターンを前記候補テストパターンで置換して、前記第１及び前記第２のテストパターン間の第２の距離を算出するステップと、
前記第２の距離が第２の所定の閾値未満である場合には、前記第１及び第２のテストパターンを前記生成パターンデータ格納部に格納するステップと、
を含む付記２記載のテストパターン抽出プログラム。

（付記５）
前記生成ステップが、
前記候補テストパターンについての前記処理の識別子が前記第１及び第２のテストパターンについての前記処理の識別子とは異なる場合には、前記第１のテストパターンと前記候補テストパターンとについて前記生成ステップを実施し、前記第２のテストパターンと前記候補テストパターンとについて前記生成ステップを実施するステップ
をさらに含む付記４記載のテストパターン抽出プログラム。

（付記６）
前記距離が、前記テストパターンに含まれる変数に応じて重み付けされた距離である
付記１乃至５のいずれか１つ記載のテストパターン抽出プログラム。

（付記７）
テストパターンに対して検証対象により実行される処理の識別子を取得し、前記テストパターンに対応して前記処理の識別子をテスト結果データ格納部に格納するステップと、
前記テスト結果データ格納部に格納されており且つ前記処理の識別子が異なる前記テストパターン間で距離を算出し、前記処理の識別子の組毎に当該距離が所定の条件を満たす前記テストパターンの組を特定し、パターンデータ格納部に格納するステップと、
を含み、コンピュータにより実行させるテストパターン抽出方法。

（付記８）
テストパターンに対して検証対象により実行される処理の識別子を取得し、前記テストパターンに対応して前記処理の識別子をテスト結果データ格納部に格納する手段と、
前記テスト結果データ格納部に格納されており且つ前記処理の識別子が異なる前記テストパターン間で距離を算出し、前記処理の識別子の組毎に当該距離が所定の条件を満たす前記テストパターンの組を特定し、パターンデータ格納部に格納する手段と、
を有するテストパターン抽出装置。

実施の形態に係るテストパターン抽出装置の機能ブロック図である。 検証対象の関数Ｆ（ｘ，ｙ）の一例を示す図である。 関数Ｆの引数の値と処理種別の対応関係を示す図である。 テストパターンをランダムに生成した場合におけるテストパターンと処理種別の対応関係を模式的に示す図である。 実施の形態におけるメインの処理フローを示す図である。 テスト処理の処理フローを示す図である。 テスト結果格納部に格納されるデータの一例を示す図である。 選択すべきテストパターンペアを説明するための模式図である。 パターン選択処理の処理フローを示す図である。 パターン選択処理の処理フローを示す図である。 解集合データ格納部に格納されるデータの一例を示す図である。 第１パターン生成処理の処理フローを示す図である。 （ａ）及び（ｂ）は、第２パターン生成処理を説明するための図である。 第２パターン生成処理の処理フローを示す図である。 第２パターン生成処理の内容を説明するための図である。 生成パターンデータ格納部に格納されるデータの一例を示す図である。 重み付けした距離の算出を説明するための図である。 コンピュータの機能ブロック図である。

符号の説明

１ テストパターン格納部 ３ テスト実行部
７ テスト結果格納部 ９ パターン選択部
１１ 解集合データ格納部 １３ パターン生成部
１５ 生成パターンデータ格納部 １７ 出力部
５１ 検証対象

Claims (6)

1. テストパターンに対して検証対象により実行される処理の識別子を取得し、前記テストパターンに対応して前記処理の識別子をテスト結果データ格納部に格納するステップと、
   前記テスト結果データ格納部に格納されており且つ前記処理の識別子が異なる前記テストパターン間で距離を算出し、前記処理の識別子の組毎に当該距離が所定の条件を満たす前記テストパターンの組を特定し、パターンデータ格納部に格納するステップと、
   をコンピュータに実行させるためのテストパターン抽出プログラム。
2. 前記パターンデータ格納部に格納されている前記テストパターンの組から、距離がより短いテストパターンの組を生成し、生成パターンデータ格納部に格納する生成ステップ
   をさらに前記コンピュータに実行させるための請求項１記載のテストパターン抽出プログラム。
3. 前記所定の条件が、前記テストパターン間の距離が前記処理の識別子の組について最小であり且つ所定の閾値未満であるという条件である
   請求項１記載のテストパターン抽出プログラム。
4. 前記パターンデータ格納部には、前記テストパターンに対応して前記処理の識別子が登録されており、
   前記生成ステップが、
   第１及び第２のテストパターン間の中点の候補テストパターンを算出すると共に、当該候補テストパターンに対して前記検証対象により実行される処理の識別子を取得するステップと、
   前記候補テストパターンについての前記処理の識別子と、前記第１及び前記第２のテストパターンについての前記処理の識別子との異同を判断するステップと、
   前記候補テストパターンについての前記処理の識別子と前記第１のテストパターンについての前記処理の識別子とが一致する場合には、前記第１のテストパターンを前記候補テストパターンで置換して、前記第１及び第２のテストパターン間の第２の距離を算出するステップと、
   前記候補テストパターンについての前記処理の識別子と前記第２のテストパターンについての前記処理の識別子とが一致する場合には、前記第２のテストパターンを前記候補テストパターンで置換して、前記第１及び前記第２のテストパターン間の第２の距離を算出するステップと、
   前記第２の距離が第２の所定の閾値未満である場合には、前記第１及び第２のテストパターンを前記生成パターンデータ格納部に格納するステップと、
   を含む請求項２記載のテストパターン抽出プログラム。
5. テストパターンに対して検証対象により実行される処理の識別子を取得し、前記テストパターンに対応して前記処理の識別子をテスト結果データ格納部に格納するステップと、
   前記テスト結果データ格納部に格納されており且つ前記処理の識別子が異なる前記テストパターン間で距離を算出し、前記処理の識別子の組毎に当該距離が所定の条件を満たす前記テストパターンの組を特定し、パターンデータ格納部に格納するステップと、
   を含み、コンピュータにより実行させるテストパターン抽出方法。
6. テストパターンに対して検証対象により実行される処理の識別子を取得し、前記テストパターンに対応して前記処理の識別子をテスト結果データ格納部に格納する手段と、
   前記テスト結果データ格納部に格納されており且つ前記処理の識別子が異なる前記テストパターン間で距離を算出し、前記処理の識別子の組毎に当該距離が所定の条件を満たす前記テストパターンの組を特定し、パターンデータ格納部に格納する手段と、
   を有するテストパターン抽出装置。

Images