(57)【要約】【課題】標準規格品に対するリファイン品として開発した検査対象の処理系に関し、処理系の動作検証を行うテストプログラムを自動生成し、そのテストプログラムにより動作正当性検証を行う。【解決手段】多種多様な命令列の組み合わせを網羅し、且つ、無限ループに陥らないように、分岐または合流点を設定し、分岐または合流点と、次の分岐または合流点との間に、ランダムな命令列を生成することにより、膨大な量のテストプログラムを自動生成し、これを検査対象の処理系と他の動作検証済標準規格品の処理系とで実行させ、比較することにより、動作正当性検証を行うテストプログラムを作成するプログラムとする。【選択図】      図１
2004227257.tif 000002
【特許請求の範囲】
【請求項１】
初期設定時に与えられた目標命令数を、所定数に分けるか、分けないかを設定する区間設定手段と、
各区間の開始時点と終了時点の内部状態を設定する状態設定手段と、
内部状態に適合する命令群をカテゴリィ別に区分けした命令テーブルと、
実行環境の内部状態の遷移をシミュレ−トする抽象実行手段と、
一つの命令を抽象実行手段によりシミュレ−トした結果の内部状態を把握する内部状態把握手段と、
前記状態設定手段により設定された開始時点の内部状態に適合する命令、または前記内部状態把握手段により把握された内部状態に適合する命令を、前記命令テ−ブルから１つ生成する命令生成手段と、
上記１区間に与えられた命令数に達するまで、内部状態に適合して生成される命令を追加する命令列生成手段と、
して機能させるためのテストプログラム作成プログラム。
【請求項２】
分岐または合流点から、次の分岐または合流点までを上記１区間とし、各分岐または合流点における実行環境の内部状態とを設定する手段と、
分岐または合流点と、次の分岐または合流点との間に、所定の長さのシ−ケンシャルな命令列を生成する手段として機能させるための請求項１に記載のテストプログラム作成プログラム。
【請求項３】
１区間の目標命令数を与えられ、該区間で命令を抽象実行する毎に、該命令の抽象実行後の内部状態と、分岐または合流点において設定されている最終内部状態とを比較し、内部状態の遷移に必要な命令数を把握する手段と、
残りの命令数が、内部状態の遷移に必要な命令数に達したときに、該最少命令数により、分岐または合流点における内部状態を実現する命令列を生成する手段として機能させるための請求項２に記載のテストプログラム作成プログラム。
【請求項４】
実行途中で必ず条件判定が反転するような結果を出す命令列を生成するループ構造生成手段として機能させるための請求項１又は２に記載のテストプログラム作成プログラム。
【請求項５】
分岐先がメソッドや関数であり、メソッドや関数の順位テ−ブルを備え、該順位テ−ブルに従い下位から上位に向かってのみメソッドや関数を呼び出す手段として機能させるための請求項１又は２に記載のテストプログラム作成プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、規格品に対するリファイン品の各種プログラミング言語処理系の動作検証を行うテストプログラムに関し、さらに詳しくは、検査対象処理系と動作検証済処理系との実行結果の比較により、動作正当性検証を行うためのテストプログラムの自動作成プログラムに関わる。
【０００２】
【従来の技術】
幅広い分野で様々なプログラミング言語が使われてきているが、このプログラミング言語処理系の動作正当性検証を行うためには、多種多様な命令列の組み合わせを網羅した多量のテストプログラムを用意し、それらを検査対象処理系上で実行し、その動作結果の正当性を検証することが望ましい。しかし、この膨大な量のテストプログラムを一々人手で作り、実行させ動作検証を行うことは非現実的であり、これらのことを自動的に行うシステムが求められている。
【０００３】
動作検証用テストプログラム自動生成とそれを使った動作検証システムは、マイクロプロセッサやコンパイラの設計開発の分野では既に提案されている。マイクロプロセッサの分野では、非同期の割り込みを発生させる専用の命令を配置してテストプログラムを自動生成するもの（例えば、特許文献１）や、命令タイプや機能等の生成条件とプログラム構成を指定してテストプログラムを自動的に生成するもの（例えば、特許文献２）があるが、プログラムの内部状態を把握しその状態に整合した次なる命令を選択するものはなく、またランダムにテストプログラムを自動生成するものであっても、無限ループの回避を考慮したものではない（例えば、特許文献１及び２）。無限ループに陥らないようにランダムテストプログラムを自動生成するものとして、途中に特殊な命令列を挿入することによって実現するものがある（例えば、特許文献３）。また、テストプログラムの実行部とデータ部を分割し、実行部を標準化された単機能に分割し、この単機能に対応する要求仕様を表わしたテスト仕様書により、小さな命令列を組み合わせて大きなテストプログラムを生成する手法（  例えば、特許文献４）が提案されている。また、コンパイラの分野では、静的な構文解析をベースにして文法的に正しいテストプログラムを自動生成する手法が提案されている。（例えば、非特許文献１）
【０００４】
【特許文献１】
特開平７−１８２２０２号公報（第２−３頁、図１）
【０００５】
【特許文献２】
特開平８−３３９３１２号公報（第１−７頁、図１、図２）
【０００６】
【特許文献３】
特開平７−６４８１５号公報（第６頁、図１４）
【０００７】
【特許文献４】
特開平１−２２６０３８号公報（第２−３頁、図１、図２）
【０００８】
【非特許文献１】
太田行紀、脇田健、佐々政孝“属性文法に基づくテストプログラム生成器の設計と実装”：情報処理学会ソフトウェア工学研究会研究報告
Ｎｏ．１０３−２３，ｐｐ．１８５−１９２
【０００９】
【発明が解決しようとする課題】
ところで、言語処理系の動作検証を行うためには、テスト対象となる処理系上でテストプログラムを実際に実行してみて、その結果の正当性を確かめなくてはならない。しかし、このようなテストプログラム作成段階において、制約なしで適当に命令列を作成してしまうと、例えばＪａｖａの場合には、殆どの場合でスタックと局所変数とに型の不整合や数の不整合を生じ、実行前のベリィファイアによるコード検証に失敗し、実行が事前に阻止されてしまう事態が生じる。前記特許文献では前提の言語処理系の相違もあり、そのようなことに関する記載は見られない。即ち、次命令が内部状態と整合していると保証されないので、実行環境で常に正しく実行できる命令列となっていないという問題がある。また、無限ループに陥ることなく実行が終了する方法として、特許文献３では無限ループは回避できるが、特殊な命令列を人手で入力しなければならないという欠点がある。さらに、動作検証を容易に行うためには、実行過程を反映した結果を随時出力できることも必要であり、本発明はこれらの問題を解決し、動作検証を行うテストプログラムを自動生成し、容易に動作正当性検証を行えるテストプログラム作成プログラムを提供することを目的とする。
【００１０】
【課題を解決するための手段】
請求項１では、初期設定時に与えられた目標命令数を、所定数に分けるか、分けないか、を設定する区間設定手段と、各区間の開始状態と、終了状態を設定する状態設定手段と、内部状態に適合する命令群をカテゴリィ別に区分けした命令テーブルと、実行環境の内部状態の遷移をシミュレ−トする抽象実行手段と、一つの命令を抽象実行手段によりシミュレ−トした結果の内部状態を把握する内部状態把握手段と、前記状態設定手段により設定された開始時点の内部状態に適合する命令、または前記内部状態把握手段により把握された内部状態に適合する命令を、前記命令テ−ブルから１つ生成する命令生成手段と、上記１区間に与えられた命令数に達するまで、内部状態に適合して生成される命令を追加する命令列生成手段として機能させるためのテストプログラム作成プログラムとする。
【００１１】
請求項２では、分岐または合流点から、次の分岐または合流点までを上記１区間とし、各分岐または合流点における実行環境の内部状態とを設定する手段と、分岐または合流点と、次の分岐または合流点の間に、所定の長さのシ−ケンシャルな命令列を生成する手段として機能させるためのテストプログラムを作成するプログラムとする。
【００１２】
請求項３では、１区間の目標命令数を与えられ、該区間で命令を抽象実行する毎に、該命令の抽象実行後の内部状態と、分岐または合流点において設定されている最終内部状態とを比較し、内部状態の遷移に必要な命令数を把握する手段と、残りの命令数が、内部状態の遷移に必要な命令数に達したときに、該最少命令数により、分岐または合流点における内部状態を実現する命令列を生成する手段として機能させるためのテストプログラム作成プログラムとする。
【００１３】
請求項４では、実行途中で必ず条件判定が反転するような結果を出す命令列を生成するループ構造生成手段として機能させるためのテストプログラム作成プログラムとする。
請求項５では、分岐先がメソッドや関数であり、メソッドや関数の順位テ−ブルを備え、該順位テ−ブルに従い下位から上位に向かってのみメソッドや関数を呼び出す手段として機能させるためのテストプログラム作成プログラムとする。
【００１４】
【発明の実施の形態】
図１は本発明の１実施例のシステム概要を示すものである。まず、
（１）テストプログラム仕様に定められた、そのテストプログラムの目標の命令の数、区間の数、関数やメソッドの数などの指定に基づき、命令列を生成する。即ち、
ａ）図１の制御フロー生成器１により、分岐、ループ、関数呼び出しなどの分岐先内部状態をランダムに生成する。その上で、
ｂ）図１のシ−ケンシャル命令生成器２により、分岐しないシーケンシャルなランダム命令列を生成する（請求項２，４，５）。さらに、
ｃ）図１の出力コ−ド追加部３により、実行時の内部状態の値を出力するコードを追加する。かくして、
（２）図１のバイトコ−ドアセンブラ４により、生成した命令列テキストファイルを実行可能なバイナリ形式に変換し、
（３）図１の自動テストシステム５により、生成されたバイナリファイルを検査対象処理系と、動作検証済規格品の処理系とで実行し、両者の実行結果を比較して検査対象処理系の動作検証を行なう、
という順序で動作正当性検証テストを自動的に行うものである。
【００１５】
次に、テストプログラム自動生成の個別手法の実施例の説明を行う。図２〜図４に、制御フロー生成方法の詳細を示す。図２は、分岐、ル−プ、呼び出しの制御構造の基本と各ノードにおける内部状態の設定をして、制御フローを生成することを示し、分岐文の分岐元と分岐先の自動生成（請求項２）を行うものである。図３は、条件分岐による無限ループの回避方法の１実施例を示すものであり、テストプログラムの中でループさせる場合に、各分岐ノードでの実行系内部状態を決定するが、このとき、無限ループに陥ることのないように、テストプログラムを自動生成することが必要である。そこで、論理的に必ず条件判定が反転するループを、特定命令列に頼らずに生成させるために、
▲１▼  各ループに対し一つの固有の局所変数（カウンタ）を用意。
▲２▼  関数先頭部分で各カウンタを０に初期化。
▲３▼  該当ループ命令を通るたびにそれに対応したカウンタに１を加えるようにする（カウントアップ）。
▲４▼  分岐命令ではカウンタの値を比較、１ずつ増えていくカウンタと定数値とを比較しており、有限回で大小関係が反転するため、必ず有限回で条件判定が反転するか、必ず有限回で下に抜けることになる。
▲５▼  分岐命令の下に当該分岐命令のカウンタを０に初期化する。
但し▲３▼〜▲５▼の間に、他の分岐・合流が一切入らないようにする。そして、これらの命令列の間に適宜分岐しない命令列をはさむことによって、無限ループに陥らないループ構造を、特定の命令列によらずに生成できる。（請求項４）
図４は、メソッドや関数の相互呼び合いによる無限ループの回避を説明するものである。複数の関数を生成し、それらの呼び出しも自動生成するが、関数呼出を生成するときには、相互呼び合いによって循環構造が生成され無限ループに陥ることが無いように、図４に示すように、各関数に一意に順位をつけ下位から上位に向かってしか呼び出せないようにする機能をテストプログラム生成器に持たせた。（請求項５）
図１のシーケンシャル命令列生成器２の詳細を図５，図６に示す。これは、テストプログラム仕様により目標命令数が決められ、開始時の内部状態と終了時の内部状態、および局所変数、配列等構造をもったデータ内部状態など、実行中プログラムの内部状態との整合を取りつつ、抽象実行を行いながら分岐・合流の無いランダム命令列を自動生成していくものである。このとき、終了状態を実現するのに最低限必要な命令数と、残り命令数とを比較し、残り命令数＞必要命令数のときは、その時点での直前の命令終了時の内部状態として、スタック・局所変数の型、数に見合うバイトコードをランダムに一つ見つける形で、整合の取れた命令を追加していき（請求項１）、残り命令数＜必要命令数のときは、直前の命令終了時の内部状態から終了状態を最短で実現でき、且つ、整合性のとれる必要不可欠な命令をランダムに追加していく（請求項３）。また、分岐のないシ−ケンシャル命令生成器による、分岐のないランダム命令列を生成する１実施例を図７に示す。
【００１６】
また、作成した本テストプログラムの実行結果の正当性を検証するためには、実行終了時、もしくはエラー処理直前にテストプログラムの内部状態を出力するようにテストプログラムを作成するようにしている。更には、生成されたテストプログラムを、検査対象となる処理系と他の動作検証済規格品の処理系とで実行させ、出力された内部状態を比較することにより、動作正当性検証を行うこともできるようにしている。上記の１実施例を図１により説明すると、図１の出力コード追加部３で、制御フロ−生成器１、シ−ケンシャル命令生成器２で生成したテストプログラムの末尾に、その時点における内部状態を出力するためのコードを追加する。本システムでは、生成したランダムな命令列を検査対象処理系上で実行させ、その結果を、他の動作検証済規格品の処理系での実行結果と比較することによって、検査対象処理系の動作の正当性を確認する。そのため生成したランダム命令列の中に、プログラムの実行経過を反映したユーザ変数の内容を出力するコードを追加するようにしている。また、生成したランダム命令列は、実行可能なバイナリ形式ではなく、ユーザが簡単に読め、かつ編集加工できるテキストファイル形式にしておく。
【００１７】
（付記１）初期設定時に与えられた目標命令数を、所定数に分けるか、分けないかを設定する区間設定手段と、
各区間の開始時点と終了時点の内部状態を設定する状態設定手段と、
内部状態に適合する命令群をカテゴリィ別に区分けした命令テーブルと、
実行環境の内部状態の遷移をシミュレ−トする抽象実行手段と、
一つの命令を抽象実行手段によりシミュレ−トした結果の内部状態を把握する内部状態把握手段と、
前記状態設定手段により設定された開始時点の内部状態に適合する命令、または前記内部状態把握手段により把握された内部状態に適合する命令を、前記命令テ−ブルから１つ生成する命令生成手段と、
上記１区間に与えられた命令数に達するまで、内部状態に適合して生成される命令を追加する命令列生成手段と、
して機能させるためのテストプログラム作成プログラム。
【００１８】
（付記２）分岐または合流点から、次の分岐または合流点までを上記１区間とし、各分岐または合流点における実行環境の内部状態とを設定する手段と、
分岐または合流点と、次の分岐または合流点との間に、所定の長さのシ−ケンシャルな命令列を生成する手段として機能させるための付記１に記載のテストプログラム作成プログラム。
【００１９】
（付記３）１区間の目標命令数を与えられ、該区間で命令を抽象実行する毎に、該命令の抽象実行後の内部状態と、分岐または合流点において設定されている最終内部状態とを比較し、内部状態の遷移に必要な命令数を把握する手段と、
残りの命令数が、内部状態の遷移に必要な命令数に達したときに、該最少命令数により、分岐または合流点における内部状態を実現する命令列を生成する手段として機能させるための付記２に記載のテストプログラム作成プログラム。
【００２０】
（付記４）実行途中で必ず条件判定が反転するような結果を出す命令列を生成するループ構造生成手段として機能させるための付記１又は２に記載のテストプログラム作成プログラム。
（付記５）分岐先がメソッドや関数であり、メソッドや関数の順位テ−ブルを備え、該順位テ−ブルに従い下位から上位に向かってのみメソッドや関数を呼び出す手段として機能させるための付記１又は２に記載のテストプログラム作成プログラム。
【００２１】
（付記６）実行終了時もしくはエラー処理直前に、テストプログラムの内部状態を出力し、実行結果の正当性を検証する手段として機能させるための付記１乃至５のいずれかに記載のテストプログラム作成プログラム。
（付記７）生成されたテストプログラムを、検査対象となる処理系と他の動作検証済規格品の処理系とで実行させ、その結果を比較することにより、動作正当性検証を行う手段として機能させるための付記１乃至６のいずれかに記載のテストプログラム作成プログラム。
【００２２】
【発明の効果】
以上説明したように、本発明によれば、あるプログラミング言語の実行環境の検査対象処理系と、他の動作検証済規格品の結果参照用処理系、テストプログラムの仕様（全体の命令数、区間の数、関数の数など）とを与えることにより、多種多様な命令列の組み合わせを含み、かつ実行可能で無限ループに陥らない多数のテストプログラムを自動的に生成し、それらのテストプログラムの実行、結果の検証までを連続して自動的に行うことによって、自動的に検査対象処理系の動作正当性の検証を行うことが出来る効果を有する。
【図面の簡単な説明】
【図１】本発明の１実施例を示すシステム構成図
【図２】制御フロー生成方法の説明図
【図３】条件分岐による無限ループの回避方法の説明図
【図４】相互呼び合いによる無限ループの回避方法の説明図
【図５】シーケンシャル命令列生成手法の説明図
【図６】シーケンシャル命令生成フローチャート
【図７】シーケンシャル命令生成器によるランダム命令列生成の１実施例
【符号の説明】
１  制御フロー生成器
２  シーケンシャル命令生成器
３  出力コード追加部
４  バイトコードアセンブラ
５  自動テストシステム
【図１】
2004227257.tif 000003
【図２】
2004227257.tif 000004
【図３】
2004227257.tif 000005
【図４】
2004227257.tif 000006
【図５】
2004227257.tif 000007
【図６】
2004227257.tif 000008
【図７】
2004227257.tif 000009