(57)【要約】      （修正有）【課題】プログラムのテストを効率的に行うため、分岐網羅率を損なわずに、冗長なテストパタンを圧縮し、テストパタンの高品質化を図る。【解決手段】テスト対象プログラムのテストパタンを自動生成するテストパタン生成装置１と、前記テスト対象プログラムから分岐網羅率の対象となる制御枝を抽出する分岐制御枝抽出装置２と、前記テストパタンを行とし、前記分岐制御枝を列とする被覆表を構成する被覆表構成装置３と、前記被覆表から特異列を選択削除する特異列選択削除装置４と、前記被覆表の前記特異列を含む行を必須行として、該必須行を保存し、該必須行を前記被覆表から選択削除する必須行選択削除装置５と、前記必須行に包含される残りの列を削除する必須行包含列選択削除装置６と、前記被覆表の行を選択削除する被支配行選択削除装置７と、前記被覆表の列を選択削除する支配列選択削除装置８と、を備える。【選択図】図１
2011039718.tif 000002
【特許請求の範囲】
【請求項１】
プログラムのテストを無駄なく網羅的に行うためのテストパタン圧縮方法であって、
テスト対象プログラムのテストパタンを自動生成するテストパタン生成ステップと、
前記テスト対象プログラムから分岐網羅率の対象となる制御枝を抽出する分岐制御枝抽出ステップと、
前記テストパタン生成ステップで生成したテストパタンを行とし、前記分岐制御枝抽出ステップで抽出した分岐制御枝を列とする被覆表を構成する被覆表構成ステップと、
前記被覆表から特異列を選択削除する特異列選択削除ステップと、
前記被覆表の前記特異列を含む行を必須行として、該必須行を保存し、該必須行を前記被覆表から選択削除する必須行選択削除ステップと、
前記必須行に包含される残りの列を削除する必須行包含列選択削除ステップと、
前記被覆表の残りのいずれかの行が被覆する列の集合が前記被覆表の残りの他の行の列の集合を包含するとき、該他の行を被支配行として選択削除する被支配行選択削除ステップと、
前記被支配行選択削除ステップにより前記被覆表に残った行について、特定の列を被覆する行の集合が別の列の行の集合を包含するとき、前記特定の列を支配列として選択削除する支配列選択削除ステップと、
前記被覆表に残った行について、前記特異列選択除去ステップから前記支配列選択削除ステップまでを前記被覆表の行が消滅するまで繰り返すステップと、
を備え、前記必須行を最終解として得ることを特徴とするテストパタン圧縮方法。
【請求項２】
プログラムのテストを無駄なく網羅的に行うためのテストパタン圧縮システムであって、
テスト対象プログラムのテストパタンを自動生成するテストパタン生成装置と、
前記テスト対象プログラムから分岐網羅率の対象となる制御枝を抽出する分岐制御枝抽出装置と、
前記テストパタン生成装置で生成したテストパタンを行とし、前記分岐制御枝抽出装置で抽出した分岐制御枝を列とする被覆表を構成する被覆表構成装置と、
前記被覆表から特異列を選択削除する特異列選択削除装置と、
前記被覆表の前記特異列を含む行を必須行として、該必須行を保存し、該必須行を前記被覆表から選択削除する必須行選択削除装置と、
前記必須行に包含される残りの列を削除する必須行包含列選択削除装置と、
前記被覆表の残りのいずれかの行が被覆する列の集合が前記被覆表の残りの他の行の列の集合を包含するとき、該他の行を被支配行として選択削除する被支配行選択削除装置と、
前記被支配行選択削除装置により前記被覆表に残った行について、特定の列を被覆する行の集合が別の列の行の集合を包含するとき、前記特定の列を支配列として選択削除する支配列選択削除装置と、
を備えることを特徴とするテストパタン圧縮システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラムのテストを無駄なく網羅的に行うためのテストパタン圧縮方法およびテストパタン圧縮システムに関する。
【背景技術】
【０００２】
システムＬＳＩ設計において、上流工程で実施するプログラムのテストは、要求仕様や機能レベルの設計誤りが下流工程に混入することを防ぐために重要である。本テストが対象とするプログラムには、ＬＳＩハードウェア化する機能を記述したプログラムだけでなく、ＬＳＩと協調して動作する組み込みプログラムが含まれる。効率的なテストを実施するためには、無駄が少なく、高い網羅率を実現するシミュレーションパタン（以下、テストパタン）が必要となる。すなわち、テストパタンの高品質化が求められている。
【０００３】
検証の進捗度合いは、通常、幾つかの網羅性指標に基づいて評価する。理想的には、上流工程においても、高い検証網羅率を達成することが望ましい。しかし、現実には、検証リソースの制限や、メソドロジが完備されていない点がネックとなり、上流工程のテストは下流工程に比べて十分に行われにくい傾向がある。したがって、上流工程での検証漏れを解決するには、低コストで質の高い検証を実現する手法が不可欠である。
【０００４】
上記の問題を解決する一手法として、形式手法のひとつであるモデル検査を応用することにより、プログラムのテストパタンを自動生成する方法が提案されている（非特許文献１、２、３）。これらは、逐次処理プログラム（Ｃ言語等）を、静的な制御構造の解析に適した中間表現に変換し、プログラムの実行パスを検査する。特定の実行パスが実行可能であれば、対応する実行パスの条件式を形式的に解いて、分岐網羅率を可能な限り高めるようなテストパタンを自動生成することができる。
【０００５】
分岐網羅率とは、プログラム内の全ての条件分岐において、真の場合、偽の場合が、テストパタンによって各々少なくとも１回は実行されるような網羅性指標のことであり、条件分岐の枝の総数に対する、選択された枝の割合で定義される。分岐網羅率は、ソフトウェア・テストの分野だけでなく、ハードウェアの機能検証でも広く使われている。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Ball T., “Abstraction-guided Test Generation: A Case Study,” Technical Report MSR-TR-2003-86, Microsoft Research, 2003.
【非特許文献２】D. Beyer, A.J. Chlipala, and R. Majumdar, “Generating Tests from Counterexample,” ICSE ’04: Proceedings of the 26th International Conference on Software Engineering, pp.326-335, 2004.
【非特許文献３】K. Sen, D. Marinov, and G. Agha, “CUTE: aconcolic unit testing engine for C,” ESEC/FSE-13: Proceedings of the 10th European software engineering conference, pp.263-272, 2005.
【非特許文献４】G.C. Necula, S. Mcpeak, S.P. Rahul, and W. Weimer,“CIL: Intermediate language and tools for analysis and transformation of C programs,” In International Conference on Compiler Construction, pp.213-228, 2002.
【非特許文献５】笹尾  勤、「論理設計−スイッチング回路理論」、近代科学社、2005年。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかし、当該手法により生成されたテストパタンには、冗長なパタンが含まれるという課題がある。説明のため、非特許文献３の手法を用いて、図８に示すプログラムのテストパタンを生成した結果を図９に示す。尚、非特許文献３では、未選択の実行パスを探索する探索方法として、制限つき縦形探索（Bounded Depth-First Search：以下、ＤＦＳ）を用いている。
【０００８】
図９は、横軸として、ＤＦＳの探索の深さに制限をかけるための Depth値（以下、Ｄ）を、縦軸として、テストパタンの生成回数 Iterations（以下、Ｉ）と、分岐網羅率 Branch Coverage（以下、ＢＣ）を示している。
【０００９】
図９より、Ｄが小さいほどＩは少なくて済むが、Ｄ＜４の場合、ＢＣが１００％に満たないことがわかる。一方、Ｄ＞４の場合、既にＢＣが飽和しているので、生成結果には冗長なテストパタンが含まれる。したがって、この場合Ｄ＝４をしきい値として、テストパタンを生成するのが得策である。Ｄ＝４の時は、Ｉ＝５、すなわちテストパタンが５パタン生成される。しかし、この場合、分岐網羅率を１００％にするためには、５パタンは必要なく、最小３パタンあれば十分である。
【００１０】
本発明は上記課題を考慮してなされたものであり、その目的は、プログラムのテストを効率的に行うため、分岐網羅率を損なわずに、冗長なテストパタンを圧縮することにより、テストパタンの高品質化を図ることにある。
【課題を解決するための手段】
【００１１】
上記目的を達成するために、請求項１にかかる発明は、プログラムのテストを無駄なく網羅的に行うためのテストパタン圧縮方法であって、テスト対象プログラムのテストパタンを自動生成するテストパタン生成ステップと、前記テスト対象プログラムから分岐網羅率の対象となる制御枝を抽出する分岐制御枝抽出ステップと、前記テストパタン生成ステップで生成したテストパタンを行とし、前記分岐制御枝抽出ステップで抽出した分岐制御枝を列とする被覆表を構成する被覆表構成ステップと、前記被覆表から特異列を選択削除する特異列選択削除ステップと、前記被覆表の前記特異列を含む行を必須行として、該必須行を保存し、該必須行を前記被覆表から選択削除する必須行選択削除ステップと、前記必須行に包含される残りの列を削除する必須行包含列選択削除ステップと、前記被覆表の残りのいずれかの行が被覆する列の集合が前記被覆表の残りの他の行の列の集合を包含するとき、該他の行を被支配行として選択削除する被支配行選択削除ステップと、前記被支配行選択削除ステップにより前記被覆表に残った行について、特定の列を被覆する行の集合が別の列の行の集合を包含するとき、前記特定の列を支配列として選択削除する支配列選択削除ステップと、前記被覆表に残った行について、前記特異列選択除去ステップから前記支配列選択削除ステップまでを前記被覆表の行が消滅するまで繰り返すステップと、を備え、前記必須行を最終解として得ることを特徴とする。
【００１２】
請求項２にかかる発明は、プログラムのテストを無駄なく網羅的に行うためのテストパタン圧縮システムであって、テスト対象プログラムのテストパタンを自動生成するテストパタン生成装置と、
前記テスト対象プログラムから分岐網羅率の対象となる制御枝を抽出する分岐制御枝抽出装置と、前記テストパタン生成装置で生成したテストパタンを行とし、前記分岐制御枝抽出装置で抽出した分岐制御枝を列とする被覆表を構成する被覆表構成装置と、前記被覆表から特異列を選択削除する特異列選択削除装置と、前記被覆表の前記特異列を含む行を必須行として、該必須行を保存し、該必須行を前記被覆表から選択削除する必須行選択削除装置と、前記必須行に包含される残りの列を削除する必須行包含列選択削除装置と、前記被覆表の残りのいずれかの行が被覆する列の集合が前記被覆表の残りの他の行の列の集合を包含するとき、該他の行を被支配行として選択削除する被支配行選択削除装置と、前記被支配行選択削除装置により前記被覆表に残った行について、特定の列を被覆する行の集合が別の列の行の集合を包含するとき、前記特定の列を支配列として選択削除する支配列選択削除装置と、を備えることを特徴とする。
【発明の効果】
【００１３】
本発明によれば、テストパタンが生成された後に、冗長なテストパタンを除去し、最小化を試みる方式であるため、しきい値を用いたテストパタン生成さえ行えば、分岐網羅率を保証しながら、テストパタン数を低減できる効果がある。テストパタン生成側のアルゴリズムが完全に冗長性を排除できない限り、本発明による圧縮効果が期待できる。テストパタン生成側アルゴリズムが改良されたとしても、冗長パタン数削減効果が得られる分、より広い探索範囲から結果として同数の候補パタンを得ることも可能になる。それらに本発明を適用することにより、一層の高品質化が期待できる。本発明は、テストの対象となるプログラム言語の別を問わず、逐次処理プログラム一般に適用することができる。
【図面の簡単な説明】
【００１４】
【図１】本発明の、テストパタン圧縮方法を実施するシステムのブロック図である。
【図２】本実施例におけるＣＦＧ全体図と、分岐制御枝のみに着目したＣＦＧを示す図である。
【図３】本実施例における被覆表を示す図である。
【図４】本発明の、テストパタン圧縮方法の処理手順を示す図である。
【図５】本実施例における図３を簡約化した被覆表を示す図である。
【図６】本実施例における図５を簡約化した被覆表を示す図である。
【図７】本実施例における図６を簡約化した被覆表を示す図である。
【図８】図９の動作例に用いたプログラムを示す図である。
【図９】テストパタン生成装置の動作例を示す図である。
【発明を実施するための形態】
【００１５】
本発明の実施例について図面を参照して説明する。図１は本発明のテストパタン圧縮方法を実施するシステムのブロック図である。本システムは、テスト対象プログラムのテストパタンを自動生成するテストパタン生成装置１と、テスト対象プログラムから分岐網羅率の対象となる制御枝を抽出する分岐制御枝抽出装置２と、テストパタン生成装置１で生成したテストパタンを行とし、同様に分岐制御枝抽出装置２で抽出した分岐制御枝を列とする被覆表を構成する被覆表構成装置３と、得られた被覆表の中の特異列を選択削除する特異列選択削除装置４と、被覆表の中の必須行を選択削除する必須行選択削除装置５と、必須行による包含列を削除する必須行包含列選択削除装置６と、被支配行を選択削除する被支配行選択削除装置７と、支配列を選択削除する支配列選択削除装置８とで構成されている。９は信号線である。本発明では、これらの装置を用いて、所定の処理手順により、テストパタンを圧縮（削除）する。以下、図８に示したプログラムをテスト対象プログラムとして具体的に説明する。
【００１６】
図２（ａ）は、図８のプログラムの制御フローグラフ（以下、ＣＦＧ）を表す。ｎ個の節（楕円）の集合をＶ＝｛ｖ１，ｖ２，・・・，ｖｎ｝、ｍ個の有向枝（矢印）の集合をＥ＝｛ｅ１，ｅ２，・・・，ｅｍ｝とするとき、ＣＦＧ＝（Ｖ，Ｅ）である。Ｖは図８のプログラムの各文に対応し、Ｅは制御の流れを表す。
【００１７】
図２（ｂ）に、図２（ａ）のＣＦＧのうち、ｉｆ文のみに着目した様子を示す。１２、１５、２０、２２の各節から分岐している枝ｅ１，ｅ２，・・・，ｅ８を分岐制御枝といい、この場合、分岐制御枝の総数は８本となる。分岐網羅率とは、分岐制御枝の総数に対し、あるテストパタンによって選択された分岐制御枝数の割合を表す網羅性指標のことである。任意の数のテストパタンを用いてシミュレーションをするとき、１００％の分岐網羅率を達成するには、分岐制御枝ｅ１，ｅ２，・・・，ｅ８のすべてが、少なくとも１回選択される必要がある。
【００１８】
テストパタン生成装置１は、分岐網羅率を可能な限り高めるようなテストパタンを生成する手段を具備する。これには、例えば、非特許文献１〜３のような公知の技術を用いて実現できる。また、テスト対象プログラムから分岐網羅率の対象となる制御枝を抽出する分岐制御枝抽出装置２は、非特許文献４の公知の技術を用いて容易に実現できる。
【００１９】
しかし、これら従来技術だけでは冗長なパタンが生成される問題があることは前述の通りである。分岐網羅率上の重複したテストパタンを除去するため、本発明では、テストパタン生成装置１で生成されたテストパタンを行とし、同様に分岐制御枝抽出装置２で抽出された分岐制御枝を列とする被覆表を構成する被覆表構成装置３を用いる。
【００２０】
図３に、非特許文献３の手法を用いて、Depth値としてＤ＝５を指定したときに生成されたテストパタンを行に、図２（ｂ）の分岐制御枝ｅ１，ｅ２，・・・，ｅ８を列にとり、表の形で表した図を示す。
【００２１】
表の交点（ｉ、ｊ）に×印があるとき、行ｉは列ｊを被覆するといい、図３の表を被覆表と呼ぶ。例えば、ｔｐ１は、ｅ１の分岐制御枝を被覆する。ｔｐ２は、ｅ２とｅ４の分岐制御枝を被覆する（以下同様）。本発明では、このとき、全ての分岐制御枝を網羅するのに必要最小限のテストパタン数を求めたい。
【００２２】
以上のように、本問題は、すべての列を被覆するような最小数の行の集合を求める最小被覆問題として定式化することができる。最小被覆問題は、Quine-McCluskey（ＱＭ）法の後半部の手続きを使って、多くの場合、実用的な時間内で解くことが期待できる。ＱＭ法は、例えば、非特許文献５に示されているような公知の技術を用いて容易に実現できる。
【００２３】
本発明では、ＱＭ法の知見を応用し、同等の分岐網羅率を達成する上で不要なテストパタンを圧縮（削除）する方法を考案した。これをＣＲＴＰ（Compression of Redundant Test Patterns）法と呼ぶ。ＣＲＴＰ法が備える所定の計算手順を図４示す。
【００２４】
ＣＲＴＰ法では、図４のステップＳ１でテストパタン生成装置１を用いてテストパタンを自動生成し、ステップＳ２で分岐制御枝抽出装置２を用いてＣＦＧから分岐制御枝を抽出する。ステップＳ３で被覆表構成装置３を用いて図３の被覆表を構成する。以下、ステップＳ４，Ｓ５，Ｓ６の処理について詳しく説明する。
【００２５】
図３の被覆表において、交点（ｉ、ｊ）に×印をただ１つしかもたない列を特異列という。特異列はＣＦＧ上の特異な分岐制御枝を表す。この場合、ｅ１とｅ４が特異列である。特異列の×印を含む行を必須行という。必須行は分岐網羅率を増やす上で不可欠なテストパタンを意味する。この場合、ｔｐ１とｔｐ２が必須行に該当する。特異列選択削除装置４と必須行選択削除装置５を用いて、特異列と必須行のチェック完了後、求める最小解に必須行ｔｐ１とｔｐ２を保存し、特異列と必須行を削除する（ステップＳ４、Ｓ５）。さらに、必須行包含列選択削除装置６は必須行によって包含される列をチェックし、削除する（ステップＳ６）。この場合、ｅ２が削除されることになる。ステップＳ６の完了後、簡約化された被覆表を、図５に示す。
【００２６】
図５において、行Ｐが被覆する列の集合が行Ｑの列の集合を包含するとき、行Ｐは行Ｑを支配する、という。すなわち、ＱがＰの部分集合であるとき、Ｑを被支配行と呼ぶ。この場合、行ｔｐ３，ｔｐ４，ｔｐ５，ｔｐ６は、行ｔｐ７に包含される関係にある。したがって、被支配行削除装置７を用いて、行ｔｐ３，ｔｐ４，ｔｐ５，ｔｐ６をチェックし、図５の表から削除する（ステップＳ７）。
【００２７】
ステップＳ７の完了後、簡約化された被覆表を、図６に示す。図６において、列Ｍを被覆する行の集合が列Ｎの行の集合を包含するとき、列Ｍは列Ｎを支配する、という。Ｍを支配列と呼ぶ。これに該当するとき、支配列選択削除装置８を用いて支配列をチェックし、削除する。本実施例の場合、ｅ３，ｅ５，ｅ６，ｅ７，ｅ８が被覆する行の集合は互いに等しい。このような場合、全て支配列と解釈できるので、どの列を削除しても結果に影響はない（ステップＳ８）。
【００２８】
ステップＳ８の完了後、簡約化された被覆表を、図７に示す。図７は、図６の支配列ｅ５〜ｅ８を削除した場合を示している。図７において、ステップＳ４とＳ５の手続きを繰返す。残ったｅ３は特異列であり、したがって行ｔｐ７は必須行となる。特異列選択削除装置４と必須行選択削除装置５を用いて、求める最小解に必須行ｔｐ７を保存し、必須行を削除する。最終的に被覆表は消滅し、最小解として
ＴＰ＝｛ｔｐ１、ｔｐ２、ｔｐ７｝
の３個のテストパタンが得られる。これにより手続きが終了する。
【００２９】
このとき、図３より、ｔｐ１，ｔｐ２，ｔｐ７の３個のテストパタンで、ｅ１，ｅ２，・・・，ｅ８の分岐制御枝をすべて網羅できていることが確認できる。
【符号の説明】
【００３０】
１：テストパタン生成装置
２：分岐制御枝抽出装置
３：被覆表構成装置
４：特異列選択削除装置
５：必須行選択削除装置
６：必須行包含列選択削除装置
７：被支配行選択削除装置
８：支配列選択削除装置
９：信号線
【図１】
2011039718.tif 000003
【図２】
2011039718.tif 000004
【図３】
2011039718.tif 000005
【図４】
2011039718.tif 000006
【図５】
2011039718.tif 000007
【図６】
2011039718.tif 000008
【図７】
2011039718.tif 000009
【図８】
2011039718.tif 000010
【図９】
2011039718.tif 000011