(57)【要約】プログラムの性能評価に用いられるテストデータを生成する。  まず性能評価対象のソースプログラムと、サンプルデータと、生成されるテストデータのサイズを決めるために用いられる生成パラメータとを入力装置から受け取る。そして、プロセッサがサンプルデータを用いてソースプログラムを実行し、当該ソースプログラム中の複数の文各々について、実行回数を取得する。更に、サンプルデータサイズの生成パラメータ倍のサイズを有するテストデータであって、ソースプログラム中の複数の文各々についての実行頻度が、サンプルデータを用いてソースプログラムを実行した際の当該複数の分各々についての実行頻度と同じとなるテストデータを、取得された実行回数に基いてプロセッサが生成する。
2012104907.tif 000002
【特許請求の範囲】
【請求項１】
プログラムの性能評価に用いられるテストデータを生成する方法であって、
性能評価対象のソースプログラムと、サンプルデータと、生成されるテストデータのサイズを決めるために用いられる生成パラメータとを入力装置から受け取る入力ステップと、
プロセッサが前記サンプルデータを用いて前記ソースプログラムを実行し、当該ソースプログラム中の複数の文各々について、実行回数を取得する実行回数取得ステップと、
前記サンプルデータのサイズの前記生成パラメータ倍のサイズを有するテストデータであって、前記ソースプログラム中の前記複数の文各々についての実行頻度が、前記サンプルデータを用いて前記ソースプログラムを実行した際の当該複数の分各々についての実行頻度と同じとなるテストデータを、取得された前記実行回数に基いて前記プロセッサが生成するテストデータ生成ステップとを有することを特徴とするテストデータ生成方法。
【請求項２】
請求項１記載のテストデータ生成方法であって、前記実行頻度とは、前記ソースプログラムの各文の実行回数の比であることを特徴とするテストデータ生成方法。
【請求項３】
請求項１記載のテストデータ生成方法であって、
前記実行回数取得ステップは、
前記ソースプログラムから当該ソースプログラムを構成する複数の基本ブロックを有する基本ブロックグラフを生成するステップと、
前記複数の基本ブロックの各々について当該基本ブロックの基本ブロック番号と当該基本ブロックに含まれる一以上の文各々の文番号とを出力するための第一の命令を前記基本ブロックグラフに挿入するステップと、
前記複数の基本ブロックの各々について、当該基本ブロック中に当該基本ブロックの基本ブロック番号を出力するための第二の命令を挿入するステップと、
前記第一の命令および一以上の前記第二の命令が挿入された基本ブロックグラフをコンパイルして実行コードを生成するステップと、
前記サンプルデータを用いて前記実行コードを実行することにより、前記第一の命令および一以上の前記第二の命令によって出力される情報を中間情報として得るステップと、
前記中間情報から、前記ソースプログラム中の複数の文各々についての、前記実行回数を取得するステップを有することを特徴とするテストデータ生成方法。
【請求項４】
請求項３記載のテストデータ生成方法であって、
前記テストデータ生成ステップは、
前記ソースプログラムをループ解析して、当該ソースプログラムに含まれる一以上のループを抽出するループ解析ステップと、
前記実行回数に基いて、前記一以上のループ各々について、当該ループの実行回数であるループ実行回数を取得するステップと、
前記一以上のループ各々について、当該ループ内のプログラム実行経路である一以上のパスと当該パスの実行回数であるパス実行回数を取得するステップと、
前記一以上のループ各々について、当該ループを前記生成パラメータと当該ループのループ実行回数の積の値倍に展開するループ展開ステップと、
ループ展開後のソースプログラムに含まれる全ての文を通るような入力データを生成するデータ生成ステップとを有することを特徴とするテストデータ生成方法。
【請求項５】
請求項４記載のテストデータ生成方法であって、
前記データ生成ステップは、記号実行法を用いて前記ループ展開後のソースプログラムに含まれる全ての文を通るような入力データを生成することを特徴とするテストデータ生成方法。
【請求項６】
請求項４記載のテストデータ生成方法であって、
前記ループ展開ステップは、前記一以上のループ各々について、当該ループに含まれる各パスのパス実行回数に基いて、当該ループを展開することを特徴とするテストデータ生成方法。
【請求項７】
プログラムの性能評価に用いられるテストデータを生成するための計算機であって、
性能評価対象のソースプログラムと、サンプルデータと、生成されるテストデータのサイズを決めるために用いられる生成パラメータとを受け付ける入力装置と、
前記サンプルデータを用いて前記ソースプログラムを実行し、当該ソースプログラム中の複数の文各々について、実行回数を取得する実行回数取得ステップと、
前記サンプルデータのサイズの前記生成パラメータ倍のサイズを有するテストデータであって、前記ソースプログラム中の前記複数の文各々についての実行頻度が、前記サンプルデータを用いて前記ソースプログラムを実行した際の当該複数の分各々についての実行頻度と同じとなるテストデータを、取得された前記実行回数に基いて生成するテストデータ生成ステップとを実行するプロセッサを有する計算機。
【請求項８】
請求項７記載の計算機であって、
前記実行回数取得ステップにおいて前記プロセッサは、
前記ソースプログラムから当該ソースプログラムを構成する複数の基本ブロックを有する基本ブロックグラフを生成し、
前記複数の基本ブロックの各々について当該基本ブロックの基本ブロック番号と当該基本ブロックに含まれる一以上の文各々の文番号とを出力するための第一の命令を前記基本ブロックグラフに挿入し、
前記複数の基本ブロックの各々について、当該基本ブロック中に当該基本ブロックの基本ブロック番号を出力するための第二の命令を挿入し、
前記第一の命令および一以上の前記第二の命令が挿入された基本ブロックグラフをコンパイルして実行コードを生成し、
前記サンプルデータを用いて前記実行コードを実行することにより、前記第一の命令および一以上の前記第二の命令によって出力される情報を中間情報として取得し、
前記中間情報から、前記ソースプログラム中の複数の文各々についての、前記実行回数を取得することを特徴とする計算機。
【請求項９】
請求項８記載の計算機であって、
前記テストデータ生成ステップにおいて前記プロセッサは、
前記ソースプログラムをループ解析して、当該ソースプログラムに含まれる一以上のループを抽出し、
前記実行回数に基いて、前記一以上のループ各々について、当該ループの実行回数であるループ実行回数を取得し、
前記一以上のループ各々について、当該ループ内のプログラム実行経路である一以上のパスと当該パスの実行回数であるパス実行回数を取得し、
前記一以上のループ各々について、当該ループに含まれる各パスのパス実行回数に基いて、前記生成パラメータと当該ループのループ実行回数の積の値倍に当該ループを展開し、
ループ展開後のソースプログラムに含まれる全ての文を通るような入力データを生成することを特徴とする計算機。
【請求項１０】
プログラムの性能評価に用いられるテストデータを生成するたに計算機で実行されるプログラムを記録した記録媒体であって、
性能評価対象のソースプログラムと、サンプルデータと、生成されるテストデータのサイズを決めるために用いられる生成パラメータとを受け付けるためのコードと、
前記サンプルデータを用いて前記ソースプログラムを実行し、当該ソースプログラム中の複数の文各々について、実行回数を取得する実行回数取得ステップを実行するためのコードと、
前記サンプルデータのサイズの前記生成パラメータ倍のサイズを有するテストデータであって、前記ソースプログラム中の前記複数の文各々についての実行頻度が、前記サンプルデータを用いて前記ソースプログラムを実行した際の当該複数の分各々についての実行頻度と同じとなるテストデータを、取得された前記実行回数に基いて生成するテストデータ生成ステップを実行するためのコードとを有するプログラムを記録した記録媒体。
【請求項１１】
請求項１０記載の記録媒体であって、
前記実行回数取得ステップを実行するためのコードは、
前記ソースプログラムから当該ソースプログラムを構成する複数の基本ブロックを有する基本ブロックグラフを生成し、
前記複数の基本ブロックの各々について当該基本ブロックの基本ブロック番号と当該基本ブロックに含まれる一以上の文各々の文番号とを出力するための第一の命令を前記基本ブロックグラフに挿入し、
前記複数の基本ブロックの各々について、当該基本ブロック中に当該基本ブロックの基本ブロック番号を出力するための第二の命令を挿入し、
前記第一の命令および一以上の前記第二の命令が挿入された基本ブロックグラフをコンパイルして実行コードを生成し、
前記サンプルデータを用いて前記実行コードを実行することにより、前記第一の命令および一以上の前記第二の命令によって出力される情報を中間情報として取得し、
前記中間情報から、前記ソースプログラム中の複数の文各々についての、前記実行回数を取得するためのコードを有することを特徴とする記録媒体。
【請求項１２】
請求項１１記載の記録媒体であって、
前記テストデータ生成ステップを実行するためにおいて前記プロセッサは、
前記ソースプログラムをループ解析して、当該ソースプログラムに含まれる一以上のループを抽出し、
前記実行回数に基いて、前記一以上のループ各々について、当該ループの実行回数であるループ実行回数を取得し、
前記一以上のループ各々について、当該ループ内のプログラム実行経路である一以上のパスと当該パスの実行回数であるパス実行回数を取得し、
前記一以上のループ各々について、当該ループに含まれる各パスのパス実行回数に基いて、前記生成パラメータと当該ループのループ実行回数の積の値倍に当該ループを展開し、
ループ展開後のソースプログラムに含まれる全ての文を通るような入力データを生成するためのコードを有することを特徴とする記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
計算機で実行されるプログラムの実行性能を評価する際に用いられるテストデータの生成に関する。
【背景技術】
【０００２】
プログラムのテスト工程のひとつに実行性能の評価がある。これは開発したプログラムが、実稼動時に、顧客から要求された処理性能基準を達成できることを確認するために行われる。【０００３】
プログラムの実稼動時の実行性能を正確に評価するためには、実稼働時に入力されるデータと類似したテストデータを準備して、テストデータを用いてプログラムを実行する必要がある。そのため、性能評価テスト用のテストデータを生成する技術が求められている。【０００４】
性能評価用のテストデータを生成する従来技術として、特許文献1が存在する。この技術により、データベースのスキーマ情報およびデータ生成ルールを与えてテストデータを生成することができる。【０００５】
また特許文献2では、性能評価用のテストデータを生成するために用いられるプログラムを生成する方法を示している。 
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０００−２０５２９
【特許文献２】特開２００９−１３４６６２
【非特許文献】
【０００７】
【非特許文献１】Steven Muchnick。 Advanced Compiler Design and Implementation。 Morgan  Kaufmann、 pp。169-216、 1997。
【０００８】
【非特許文献２】Cristian Cadar、 Daniel Dunbar、 Dawson Engler。 Klee: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs。 In Proceedings of Operating System Design and Implementation、 pp。209-224、 2008。
【発明の概要】
【発明が解決しようとする課題】
【０００９】
従来技術の問題は2つある。第1の問題は、テストデータの生成方法をユーザが指定する必要がある点である。そのため、性能評価対象プログラムの振る舞いが実稼動時と類似したものになるようテストデータを生成するためには、ユーザがソースプログラムを調査し、適切なテストデータ生成ルールあるいはパターンを考案する必要がある。しかしながら、ソースプログラムからそのプログラムの振る舞いを把握し、テストデータ生成方法を考案するのは困難で時間のかかる作業である。また、指定できるテストデータの生成方法は限られているため、どのようなテストデータを生成すればよいかが判明しても、適切なテストデータの生成方法を指定できない場合もある。【００１０】
第2の問題は、従来技術がデータベース用のテストデータを生成する技術であり、データベース用プログラムの性能評価にしか利用できない点である。
【課題を解決するための手段】
【００１１】
まず性能評価対象のソースプログラムと、サンプルデータと、生成されるテストデータのサイズを決めるために用いられる生成パラメータとを入力装置から受け取る。【００１２】
そして、プロセッサがサンプルデータを用いてソースプログラムを実行し、当該ソースプログラム中の複数の文各々について、実行回数を取得する。更に、サンプルデータサイズの生成パラメータ倍のサイズを有するテストデータであって、ソースプログラム中の複数の文各々についての実行頻度が、サンプルデータを用いてソースプログラムを実行した際の当該複数の分各々についての実行頻度と同じとなるテストデータを、取得された実行回数に基いてプロセッサが生成する。
【発明の効果】
【００１３】
ユーザは、実稼働時に入力されるデータの傾向を反映した小規模のサンプルデータを用意するだけで、サンプルデータと実行特性に関する共通性を持つ任意の大きさのテストデータを得ることができる。これにより、プログラムの性能評価に要する開発工数を削減できる。
【図面の簡単な説明】
【００１４】
【図１】テストデータ生成装置が稼動する計算機システムの構成例を示す図である。
【図２】データ生成処理の一例を示す図である。
【図３】データ生成処理の詳細例を示す図である。
【図４】テストデータ生成プログラムの実行に用いられる入力データの一例を示す図である。
【図５】実行頻度情報の一例を示す図である。
【図６】ソースプログラムの展開例を示す図である。
【図７】テストデータ生成プログラムによって生成されるテストデータの一例を示す図である。
【図８】中間情報の例を示す図である。
【図９】テストデータ生成プログラムの実行に用いられる入力データの一例を示す図である。
【図１０】実行頻度情報の一例を示す図である。
【図１１】ソースプログラムの展開例を示す図である。
【図１２】テストデータ生成プログラムによって生成されるテストデータの一例を示す図である。
【図１３】基本ブロックグラフの一例を示す図である。
【図１４】printf文挿入後の基本ブロックグラフの一例を示す図である。
【発明を実施するための形態】
【００１５】
以下、図面を用いて発明の実施形態の一例を説明する。
【００１６】
図1はテストデータ生成装置が稼動する計算機システムの構成例を示す図である。
【００１７】
図示するように、計算機システムはCPU101、主記憶装置102、外部記憶装置103、ディスプレイ装置などの出力装置104、キーボードなどの入力装置105より構成されている。外部記憶装置103には性能評価対象であるソースプログラム106、サンプルデータ107、生成パラメータ108が、入力装置から入力されて格納される。ソースプログラム106、サンプルデータ107、生成パラメータ108が格納された外部記憶装置103がインタフェースを介してCPU101からアクセス可能に接続されても良い。主記憶装置102には、テストデータ生成プログラム109、コンパイラ110、プロファイラ111、プログラム実行器112、実行コード113、中間情報114、実行頻度情報115、テストデータ116が保持される。テストデータ生成処理はCPU101が主記憶装置102に格納されたソフトウェアを実行することにより行われる。キーボード105はユーザからのコマンドをテストデータ生成プログラム109に与えるのに用いる。ディスプレイ装置104はテストデータ生成の終了をユーザに知らせる。
【００１８】
図2はテストデータ生成処理の流れを示したフローチャートである。
【００１９】
最初にステップ201で、CPU101によりコンパイラ110が実行され、この結果ソースプログラム106から実行コード113が生成される。
【００２０】
このステップ201においてコンパイラは、最初にプログラムから、基本ブロックグラフを生成する。基本ブロックグラフは基本ブロック（分岐のない文の列）をノードとするグラフであり、コンパイラにおいて、実行コードの生成を単純化するために一般的に用いられている。基本ブロックグラフの生成方法は非特許文献1に示されている。
【００２１】
基本ブロック内の文は上から順に実行され、すべての文の実行終了後は、その基本ブロックの後続基本ブロック（その基本ブロックを始点とする有向エッジの終点に相当する基本ブロック）の実行に移る。
【００２２】
図4に示すプログラム(a)に対する基本ブロックグラフの例を図13に示す。各ノード内の先頭のB1、B2等の記号は基本ブロック番号を表す。以降では、基本ブロックBの番号とそれに含まれる文番号の列をそれぞれID(B)、STMT(B)で表す。
【００２３】
次にコンパイラは、各基本ブロックBの先頭に、その基本ブロックの番号ID(B)を中間情報114として出力する文「printf("ID(B),");」を挿入する。更にコンパイラは、main関数の基本ブロックグラフの入口ノードに相当する基本ブロック（図13ではB1）に、すべての基本ブロックの基本ブロック番号と、その基本ブロックを構成している文の文番号の列を中間情報114として出力する文「printf("ID(B1): STMT(B1)\n"); ...; printf("ID(Bn): STMT(Bn)\n\n";」を挿入する。図13の基本ブロックにこの処理を適用した結果を図14に示す。
【００２４】
最後にコンパイラは、通常のコンパイラの処理にもとづいて、printf文が挿入された基本ブロックグラフから実行コード113を生成する。
【００２５】
これにより、実行コード113が実行されたとき、基本ブロック番号と対応する文番号の列の関係、および実行された基本ブロック番号の列が中間情報114として記録される。なお、ここで示した方法は実行頻度情報を取得する方法の一例であり、プロファイル処理を単純化できるという特徴を持っている。
【００２６】
次にステップ202で、プログラム実行器112により実行コード113をサンプルデータ107に対して実行し、中間情報114を生成する 。サンプルデータは、プログラムが処理可能な形式で記述した入力データである。サンプルデータの例としては図4に示すデータ（ｂ）がある。この例は3つの数値データ要素および終端記号（-1）を含んでおり、図4に示すプログラム（a）で処理可能である。
【００２７】
図4に示すプログラム（a）から得られた実行コード113を、図4に示すデータ（b)に対して実行して得られる中間情報114を図８に示す。基本ブロック番号とその基本ブロックを構成している文の文番号の列は、基本ブロック番号ごとに、「:」記号で区切って表される。たとえば、基本ブロック番号B13に対対応する文番号の列は13,14である。最終行は、実行された基本ブロック番号の列である。これは、基本ブロック番号B1から記された順に基本ブロックが実行が行われたことを表している。
【００２８】
次にステップ203で、プロファイラ111により中間情報114から実行頻度情報115を生成する 。実行頻度情報は、プログラムの文番号をその文が実行された順に並べたものである。実行頻度情報の例を図5に示す。この例は図4に示すプログラム（a）から得られた実行コード113を、図4に示すデータ（b)に対して実行して得られた中間情報114から生成された、実行頻度情報115である。たとえば、列の最初の5つは[1,2,3,7,8]であるが、これは、プログラムの実行が文1、文2、文3、文7、文8の順に行われたことを表している。
【００２９】
実行頻度情報１１５の生成は、中間情報１１４に記録されている基本ブロック番号の列を、各基本ブロックを構成している文の文番号の列に置き換えることで行う。この処理により、図8の中間情報１１４から図5の実行頻度情報１１５が生成される。なお、一般的なプロファイラは、関数の実行回数を表示する機能、文ごとにその実行回数を表示する機能等の各種の統計処理機能を備えているが、本発明に必要なのは、文の実行順序列を得る機能のみである。
【００３０】
最後にステップ204で、テストデータ生成プログラム109によりソースプログラム106、生成パラメータ108、および実行頻度情報115から性能評価用のテストデータ116を生成する。ここで生成パラメータは、生成されるテストデータのサイズを指定するために用いられるパラメータである。具体的には、テストデータ生成プログラム109はサンプルデータサイズの生成パラメータ倍の大きさ（サイズ）を有するテストデータを生成する。
【００３１】
図3は、ステップ204でCPU101がテストデータ生成プログラム109を実行することにより行う処理の流れを詳しく例示したフローチャートである。
【００３２】
最初にステップ301で、ソースプログラム106から、すべてのループの集合を求める（LSとする）。ループは終了条件を判定する文であるヘッダおよび繰り返し処理を行う文の集合である本体によって構成される。これらの情報は、非特許文献1のループ解析方法を用いて求めることができる。
【００３３】
次にステップ302で、ループ集合LSに未処理のループが残っているかを調べ、残っていれば、ステップ304へ進み、ひとつループを取り出す（取り出したループをL、LのヘッダをH、Lの本体をBとする）。
【００３４】
次にステップ305で、実行頻度情報115をもとにBの実行回数を求める（Nとする）。 
次にステップ306で、実行頻度情報115をもとにB内のすべてのパス（プログラムの実行経路）と各パスの実行回数を求める。パスとその実行回数の組の集合をPFとする。尚、B内のパスは、実行頻度情報115から、ループヘッダHではさまれた部分列を取り出し、各部分列からBの文以外を除き、さらに重複を除くことで得られる。たとえば図5の実行頻度情報115においては、ループヘッダである文2ではさまれた部分列は[3,7,8,12,4,13,14,5]、[3,7,8,9,10,5]、[3,7,8,9.11,8,9,11,8,12,4,13,14,5]の3つである。ここからBの文以外を除くと[3,4,5]、[3,5]、[3,4,5]となり、重複を除くと[3,4,5]および[3,5]の2つのパスが得られる。各パスの実行回数は上記で重複を除く前の出現回数となる。先ほどの例ではパス[3,4,5]の実行回数は2回、パス[3,5]の実行回数は1回となる。
【００３５】
次にステップ307で、展開回数を生成パラメータとNの積として求める（PNとする）。
【００３６】
次にステップ308〜312で、LをPN倍に展開する。
【００３７】
まずステップ308で、文列を保持する変数Xを空に初期化する。
【００３８】
次に、ステップ309で、ステップ310〜312の処理をPN回実行したか（繰り返しがPN回に到達したか）の判定を行う。到達していればステップ313へ、そうでなければステップ310へ進む。
【００３９】
ステップ310で、Hを複製し、複製されたHの最後の繰り返し判定文を繰り返しが成立することを保証するassert文に変換した上で、Xの末尾に追加する。
【００４０】
ステップ311で、PFのなかからパスを1つ選択する（Pとする）。選択は、各パスの実行回数にもとづいて行う。即ちPFの各パスをそれぞれ実行回数だけ複製した多重集合を作成し、そこからランダムに選択していく。たとえばPFが3つのパスp1、p2、p3を含んでおり、それぞれの実行回数が1回,2回,3回の場合、{p1, p2, p2, p3, p3, p3}という多重集合を作成し、そこから要素をランダムに選択していく。これにより、各パスが実行回数に比例した割合で選択される。
【００４１】
ステップ312で、Pを複製し、複製されたP内の条件分岐文をassert文に変換した上で、Xの末尾に追加する。
【００４２】
ステップ313では、ソースプログラム内のLをXに置き換える。置き換えた結果をPRとする。その後、ステップ302へ戻り、未処理のループの処理に移る。
【００４３】
最後にステップ314で、PR内のXのすべての文を通るような入力データをテストデータとして生成する。生成は、非特許文献2の方法を用いて行うことができる 。生成方法は記号実行法にもとづくものである。記号実行法では、記号状態という実行状態の論理式表現を用いて、プログラムを仮想的に実行しながら、指定されたパスを実行するための条件を求める。記号状態は、メモリ内容（変数の値など）およびパスの実行条件で構成される。初期状態におけるメモリ内容はプログラム内で明示的に初期値が指定されている変数の値がその指定値に等しいことを表す論理式であり、実行条件は真である。
【００４４】
記号実行法では、初期状態から開始し、指定されたパス（文の列）を順に処理しながら、文の意味にもとづいて状態を更新していく。たとえば、代入文の場合、現在の状態にもとづいて右辺の値を表す論理式を計算し、左辺の値をその式に置き換える。また、assert文の場合、パスの実行を継続するためにはassert文で指定された条件を満たす必要がある。そのため、現在の状態にもとづいて指定された条件の内容を表す論理式を計算し、実行条件に追加する。関数呼び出し文の場合、プログラム内部で定義されている関数については、その関数の先頭に移動し、実行を継続する。入力データを取得する関数のようにプログラム外部で定義されている関数については、その結果を新しい論理変数を導入して表現する。
【００４５】
与えられたパスを最後まで実行した後、求めた実行条件を満たすために論理変数が取るべき値を計算する。これはSatisfiability Modulo Theories Solver等の制約解消系ツールを用いて計算することができる。最終的なテストデータは、入力データ取得関数の結果を表す論理変数の値を出現順に並べた列である。
【００４６】
続いて、本実施例の適用例を具体的に示す。
【００４７】
適用例の特徴は、入力データが構造を持っており、データ要素の繰り返しと終端記号によって構成されていること、およびデータ要素間にプログラムの構造によって決まる依存関係があることである。このような場合、単純にサンプルデータを複製して生成されたテストデータを用いてプログラムを実行した場合と、サンプルデータを用いてプログラムを実行した場合とではプログラムの実行の流れが大きく変化してしまうため、適切な性能評価を行うことができない。従って図２、３に示す方法で生成されるテストデータを用いることが、適切なプログラムの性能評価にとって重要となる。
【００４８】
-------  適用例１  -------
本適用例では、入力データとして、図4に示すソースプログラム(a)、サンプルデータ(b)、および生成パラメータ(c)を用いる。
尚、本適用例では、ソースプログラム(a)の行番号を用いて、ソースプログラム内の各文（実行命令）を示す。
【００４９】
図4のソースプログラム(a)において、文（行番号）1〜5が入力データを順次処理するループである。図4のサンプルデータ(b)において、-1はデータの終了を表す終端記号である。
【００５０】
上述の様に、図2のステップ203の結果、図5に示す実行頻度情報114が生成される。
【００５１】
次にステップ204で、ソースプログラムの構造にもとづくテストデータ生成を行う。
【００５２】
ステップ204を詳しく説明した図3に従って説明すると、最初にステップ301で、ソースプログラムからループ集合を求める。ループ解析の結果、ループ集合LSとして{ (2, [3,4,5]) }が得られる。ここで、LSの要素であるループ(2, [3,4,5])はヘッダ２と本体[3,4,5]の組で構成されている。
【００５３】
次にステップ302で、ループ集合LSに未処理のループが残っているか調べ、ステップ304へ進み、未処理のループをひとつ取り出す。ここではループLとして(2,[3,4,5])が取り出される。ヘッダHは2、本体Bは[3,4,5]となる。
【００５４】
次にステップ305で、実行頻度情報をもとにBの実行回数Nを求める。Bの最初の文（文3）はBを実行するたびに必ず実行されるため、Bの実行回数は文3の実行回数に等しくなる。図5に示す実行頻度情報から、Nとして3が得られる 。
【００５５】
次にステップ306で、実行頻度情報をもとにB内のすべてのパスとその実行回数の組の集合PFを求める。図5の情報から、PFとして{ ([3,4,5],2), ([3,5],1) }が得られる。ここで、[]内に記載されているが各行番号で示す分を通過するパスであり、()内に[]の後に記載されている数字が当該パスの実行回数である。
【００５６】
次にステップ307で、生成パラメータとNの積PNを求める。図4に示す生成パラメータ(c)は今“２”であるので、PNとして6が得られる。
【００５７】
次にステップ308〜312で、Lを6倍に展開する。ステップ308で、文列を保持する変数Xを空に初期化する。続いてステップ310〜312を6回繰り返す。
【００５８】
ステップ310で、H（2）を複製し、繰り返し判定文である文2を繰り返しが成立することを保証するassert文に変換しXの末尾に追加する。これによりXは[assert(x != -1)]となる。
【００５９】
ステップ311で、PFのなかから各パスの実行頻度にもとづいてパスを1つ選択する。ここではパスとしてP = [3,4,5]が選択されたとする。
【００６０】
ステップ312で、Pを複製し、P内の条件分岐文をassert文に変換した上で、Xの末尾に追加する。これによりXは[assert(x != -1), assert(!find(x)), insert(x), x = in()]となる。
【００６１】
以後、同様に処理を進めることで、ステップ310〜312の繰り返し終了時にはXは[assert(x != -1), assert(!find(x)), insert(x), x = in(), assert(x != -1), assert(find(x)), x = in(), assert(x != -1), assert(!find(x)), insert(x), x = in(), assert(x != -1), assert(!find(x)), insert(x), x = in(), assert(x != -1), assert(find(x)), x = in(), assert(x != -1), assert(!find(x)), insert(x), x = in(), assert(x == -1)]となる。
【００６２】
次にステップ313で、ソースプログラム106内のLをXに置き換える。置き換えた結果のmain関数を図6に示す。
【００６３】
次にステップ302へ戻り、LSに残っている未処理ループがないため、ステップ303へ進む。
【００６４】
最後にステップ303で、図6のプログラムのXに対応するすべての文を通るような入力データをテストデータとして生成する。非特許文献2の方法を用いることで、図7のようなテストデータが得られる。  図7のテストデータが、サンプルデータの傾向を反映していることを説明する。
【００６５】
図4のサンプルデータ（a）は、3つの要素（1, 1, 2）と終端記号（-1）によって構成されている。これを入力としてプログラムを実行した場合、1番目の要素（1）および3番目の要素（2）は挿入される（insert()が呼び出される）が、2番目の要素（1）は、すでに同じ値が挿入されているため挿入されない。すなわちinsert()が呼び出されるデータとそうでないデータを2:1の割合で含んでいる。
【００６６】
生成した図7のテストデータを入力としてプログラムを実行した場合、1番目（3)、3番目（4）、4番目（5）、6番目（6）の要素が挿入され、2番目（3）および5番目（3）の要素は挿入されない。すなわちサンプルデータと同じように、insert()が呼び出されるデータとそうでないデータを2:1の割合で含んでいる。この様に、サンプルデータと生成されたテストデータとでは、ソースプログラムの各分の実行頻度（即ちソースプログラムの各分の実行回数の比）が同じに保たれていることが分かる。
【００６７】
これに対して単純にサンプルデータを複製して2倍にした場合、終端記号である-1まで複製されてしまうため、処理されるデータの量が2倍にならない。仮に、終端記号を人手によって特別に処理した場合、得られるデータは「1 1 2 1 1 2 -1」となる。これを入力としてプログラムを実行した場合、1番目（1)、3番目（2）の要素が挿入され、2番目（1）、4番目（1）、5番目（1）および6番目（2）の要素は挿入されない。すなわちサンプルデータと異なり、insert()が呼び出されるデータとそうでないデータを1:2の割合で含んでいるため、実行頻度はサンプルデータの傾向とは大きく異なったものになってしまう。  -------  適用例２  -------
適用例１で使用した図４に示すソースプログラム(a)は入力処理ループが１つしか存在しなかった。そこで適用例２として、入力処理ループが複数存在する場合を示す。本適用例では、入力データとして、図9に示すソースプログラム(a)、 サンプルデータ(b)、および生成パラメータ(c)を用いる。尚、本適用例では、図9に示すソースプログラム(a)の行番号を用いて、ソースプログラム(a)内の各文（実行命令）を示す。
【００６８】
図9のソースプログラム(a)において、文（行番号）2〜5および7〜9が入力データを順次処理するループである。図9のサンプルデータ(b)において、-1および-2はデータの終了を表すマーカーである。
図2のステップ203の結果、図10に示す実行頻度情報が生成される。 
次にステップ204で、ソースプログラムの構造にもとづくテストデータ生成を行う。
【００６９】
ステップ204を詳しく説明した図3に従って説明すると、最初にステップ301で、ソースプログラムからループ集合を求める。ループ解析の結果、ループ集合LSとして{ (2, [3,4,5]), (7, [8,9]) }が得られる。ここで、LSの要素であるループ(2, [3,4,5])および(7, [8,9])は各々ヘッダと本体の組である。
【００７０】
次にステップ302で、ループ集合LSに未処理のループが残っているか調べ、ステップ304へ進み、未処理のループをひとつ取り出す。ここではループLとして(2,[3,4,5])が取り出される。ヘッダHは2、本体Bは[3,4,5]となる。
【００７１】
ステップ305からステップ313までの処理は先ほどの適用例１と同じである。
【００７２】
次にステップ302へ戻り、LSに未処理のループが残っているかを調べ、ステップ304へ進み、未処理のループをひとつ取り出す。ここではループLとして(7,[8,9])が取り出される。ヘッダHは7、本体Bは[8,9]となる。
【００７３】
次にステップ305で、実行頻度情報をもとにBの実行回数Nを求める。図5に示す実行頻度情報から、Nとして2が得られる 。
【００７４】
次にステップ306で、実行頻度情報をもとにB内のすべてのパスとその実行回数の組の集合PFを求める。図5の情報から、PFとして{ ([8,9],2) }が得られる。
【００７５】
次にステップ307で、生成パラメータとNの積PNを求める。図4(c)の情報から生成パラメータは今“２”であるので、PNとして4が得られる。
【００７６】
次にステップ308〜312で、Lを4倍に展開する。ステップ308で、文列を保持する変数Xを空に初期化する。続いてステップ310〜312を6回繰り返す。
【００７７】
ステップ310で、H（2）を複製し、繰り返し判定文である文7を繰り返しが成立することを保証するassert文に変換しXの末尾に追加する。これによりXは[assert(z != -2)]となる。
【００７８】
ステップ311で、PFのなかから各パスの実行頻度にもとづいてパスを1つ選択する。パスとしてP = [8,9]が選択される。
【００７９】
ステップ312で、Pを複製し、P内の条件分岐文をassert文に変換した上で、Xの末尾に追加する。これによりXは[assert(z != -2), insert(z), z = in()]となる。
【００８０】
以後、同様に処理を進めることで、ステップ310〜312の繰り返し終了時にはXは[assert(z != -2), insert(z), z = in(), assert(z != -2), insert(z), z = in(), assert(z != -2), insert(z), z = in(), assert(z != 2), insert(z), z = in(), assert(z == -2)]となる。
【００８１】
次にステップ313で、ソースプログラム106内のLをXに置き換える。置き換えた結果のmain関数を図11に示す。
【００８２】
次にステップ302へ戻り、LSに残っている未処理ループがないため、ステップ303へ進む。
【００８３】
最後にステップ303で、図11のプログラムのXに対応するすべての文を通るような入力データをテストデータとして生成する。非特許文献2の方法を用いることで、図12のようなテストデータが得られる。
【００８４】
なお、本発明は上記した実施例に限定されるものではなく、様々な変形例が含まれる。たとえば、上記した実施例は本発明をわかりやすく説明するために詳細に説明したものであり、必ずしも説明した全ての構成を備えるものに限定されるものではない。また、ある実施例の構成の一部を他の構成に置き換えることが可能であり、また、ある実施例の構成に他の構成を加えることも可能である。また、実施例の構成の一部について、他の構成の追加・削除・置換をすることが可能である。
【００８５】
また、上記の各構成、機能、処理部、処理手段等は、それらの一部又は全部を、例えば集積回路で設計する等によりハードウェアで実現してもよい。また、上記の各構成、機能等は、プロセッサがそれぞれの機能を実現するプログラムを解釈し、実行することによりソフトウェアで実現してもよい。各機能を実現するプログラム、ファイル等の情報は、メモリや、ハードディスク、SSD（Solid State Drive）等の記録装置、または、ICカード、SDカード、DVD等の記録媒体に置くことができる。
【符号の説明】
【００８６】
１０１  ＣＰＵ
１０２  主記憶装置
１０３  外部記憶装置
１０４  ディスプレイ装置
１０５  キーボード
１０６  ソースプログラム
１０７  サンプルデータ
１０８  生成パラメータ
１０９  テストデータ生成プログラム
１１０  コンパイラ
１１１  プロファイラ
１１２  プログラム実行器
１１３  中間情報
１１４  実行頻度情報
【図１】
2012104907.tif 000003
【図２】
2012104907.tif 000004
【図３】
2012104907.tif 000005
【図４】
2012104907.tif 000006
【図５】
2012104907.tif 000007
【図６】
2012104907.tif 000008
【図７】
2012104907.tif 000009
【図８】
2012104907.tif 000010
【図９】
2012104907.tif 000011
【図１０】
2012104907.tif 000012
【図１１】
2012104907.tif 000013
【図１２】
2012104907.tif 000014
【図１３】
2012104907.tif 000015
【図１４】
2012104907.tif 000016
【手続補正書】
【提出日】平成25年9月5日(2013.9.5)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
プログラムの性能評価に用いられるテストデータを生成する方法であって、
性能評価対象のソースプログラムと、サンプルデータと、生成されるテストデータのサイズを決めるために用いられる生成パラメータとを入力装置から受け取る入力ステップと、
プロセッサが前記サンプルデータを用いて前記ソースプログラムを実行し、当該ソースプログラム中の複数の文各々について、実行回数を取得する実行回数取得ステップと、    前記サンプルデータのサイズの前記生成パラメータ倍のサイズを有するテストデータであって、前記ソースプログラム中の前記複数の文各々についての実行頻度が、前記サンプルデータを用いて前記ソースプログラムを実行した際の当該複数の文各々についての実行頻度と同じとなるテストデータを、取得された前記実行回数に基いて前記プロセッサが生成するテストデータ生成ステップとを有することを特徴とするテストデータ生成方法。
【請求項２】
請求項１記載のテストデータ生成方法であって、前記実行頻度とは、前記ソースプログラムの各文の実行回数の比であることを特徴とするテストデータ生成方法。  
【請求項３】
請求項１記載のテストデータ生成方法であって、
前記実行回数取得ステップは、
前記ソースプログラムから当該ソースプログラムを構成する複数の基本ブロックを有する基本ブロックグラフを生成するステップと、  
前記複数の基本ブロックの各々について当該基本ブロックの基本ブロック番号と当該基本ブロックに含まれる一以上の文各々の文番号とを出力するための第一の命令を前記基本ブロックグラフに挿入するステップと、  
前記複数の基本ブロックの各々について、当該基本ブロック中に当該基本ブロックの基本ブロック番号を出力するための第二の命令を挿入するステップと、  
前記第一の命令および一以上の前記第二の命令が挿入された基本ブロックグラフをコンパイルして実行コードを生成するステップと、  
前記サンプルデータを用いて前記実行コードを実行することにより、前記第一の命令および一以上の前記第二の命令によって出力される情報を中間情報として得るステップと、
前記中間情報から、前記ソースプログラム中の複数の文各々についての、前記実行回数を取得するステップを有することを特徴とするテストデータ生成方法。  
【請求項４】
請求項３記載のテストデータ生成方法であって、  
前記テストデータ生成ステップは、  
前記ソースプログラムをループ解析して、当該ソースプログラムに含まれる一以上のループを抽出するループ解析ステップと、  
前記実行回数に基いて、前記一以上のループ各々について、当該ループの実行回数であるループ実行回数を取得するステップと、  
前記一以上のループ各々について、当該ループ内のプログラム実行経路である一以上のパスと当該パスの実行回数であるパス実行回数を取得するステップと、  
前記一以上のループ各々について、当該ループを前記生成パラメータと当該ループのループ実行回数の積の値倍に展開するループ展開ステップと、  
ループ展開後のソースプログラムに含まれる全ての文を通るような入力データを生成するデータ生成ステップとを有することを特徴とするテストデータ生成方法。  
【請求項５】
請求項４記載のテストデータ生成方法であって、  
前記データ生成ステップは、記号実行法を用いて前記ループ展開後のソースプログラムに含まれる全ての文を通るような入力データを生成することを特徴とするテストデータ生成方法。  
【請求項６】
請求項４記載のテストデータ生成方法であって、  
前記ループ展開ステップは、前記一以上のループ各々について、当該ループに含まれる各パスのパス実行回数に基いて、当該ループを展開することを特徴とするテストデータ生成方法。  
【請求項７】
プログラムの性能評価に用いられるテストデータを生成するための計算機であって、
性能評価対象のソースプログラムと、サンプルデータと、生成されるテストデータのサイズを決めるために用いられる生成パラメータとを受け付ける入力装置と、  
前記サンプルデータを用いて前記ソースプログラムを実行し、当該ソースプログラム中の複数の文各々について、実行回数を取得する実行回数取得ステップと、  
前記サンプルデータのサイズの前記生成パラメータ倍のサイズを有するテストデータであって、前記ソースプログラム中の前記複数の文各々についての実行頻度が、前記サンプルデータを用いて前記ソースプログラムを実行した際の当該複数の文各々についての実行頻度と同じとなるテストデータを、取得された前記実行回数に基いて生成するテストデータ生成ステップとを実行するプロセッサを有する計算機。  
【請求項８】
請求項７記載の計算機であって、  
前記実行回数取得ステップにおいて前記プロセッサは、  
前記ソースプログラムから当該ソースプログラムを構成する複数の基本ブロックを有する基本ブロックグラフを生成し、  
前記複数の基本ブロックの各々について当該基本ブロックの基本ブロック番号と当該基本ブロックに含まれる一以上の文各々の文番号とを出力するための第一の命令を前記基本ブロックグラフに挿入し、  
前記複数の基本ブロックの各々について、当該基本ブロック中に当該基本ブロックの基本ブロック番号を出力するための第二の命令を挿入し、  
前記第一の命令および一以上の前記第二の命令が挿入された基本ブロックグラフをコンパイルして実行コードを生成し、  
前記サンプルデータを用いて前記実行コードを実行することにより、前記第一の命令および一以上の前記第二の命令によって出力される情報を中間情報として取得し、  
前記中間情報から、前記ソースプログラム中の複数の文各々についての、前記実行回数を取得することを特徴とする計算機。  
【請求項９】
請求項８記載の計算機であって、  
前記テストデータ生成ステップにおいて前記プロセッサは、  
前記ソースプログラムをループ解析して、当該ソースプログラムに含まれる一以上のループを抽出し、  
前記実行回数に基いて、前記一以上のループ各々について、当該ループの実行回数であるループ実行回数を取得し、  
前記一以上のループ各々について、当該ループ内のプログラム実行経路である一以上のパスと当該パスの実行回数であるパス実行回数を取得し、  
前記一以上のループ各々について、当該ループに含まれる各パスのパス実行回数に基いて、前記生成パラメータと当該ループのループ実行回数の積の値倍に当該ループを展開し、  
ループ展開後のソースプログラムに含まれる全ての文を通るような入力データを生成することを特徴とする計算機。  
【請求項１０】
プログラムの性能評価に用いられるテストデータを生成するたに計算機で実行されるプログラムを記録した記録媒体であって、  
性能評価対象のソースプログラムと、サンプルデータと、生成されるテストデータのサイズを決めるために用いられる生成パラメータとを受け付けるためのコードと、  
前記サンプルデータを用いて前記ソースプログラムを実行し、当該ソースプログラム中の複数の文各々について、実行回数を取得する実行回数取得ステップを実行するためのコードと、  
前記サンプルデータのサイズの前記生成パラメータ倍のサイズを有するテストデータであって、前記ソースプログラム中の前記複数の文各々についての実行頻度が、前記サンプルデータを用いて前記ソースプログラムを実行した際の当該複数の文各々についての実行頻度と同じとなるテストデータを、取得された前記実行回数に基いて生成するテストデータ生成ステップを実行するためのコードとを有するプログラムを記録した記録媒体。  
【請求項１１】
請求項１０記載の記録媒体であって、  
前記実行回数取得ステップを実行するためのコードは、  
前記ソースプログラムから当該ソースプログラムを構成する複数の基本ブロックを有する基本ブロックグラフを生成し、  
前記複数の基本ブロックの各々について当該基本ブロックの基本ブロック番号と当該基本ブロックに含まれる一以上の文各々の文番号とを出力するための第一の命令を前記基本ブロックグラフに挿入し、  
前記複数の基本ブロックの各々について、当該基本ブロック中に当該基本ブロックの基本ブロック番号を出力するための第二の命令を挿入し、  
前記第一の命令および一以上の前記第二の命令が挿入された基本ブロックグラフをコンパイルして実行コードを生成し、  
前記サンプルデータを用いて前記実行コードを実行することにより、前記第一の命令および一以上の前記第二の命令によって出力される情報を中間情報として取得し、  
前記中間情報から、前記ソースプログラム中の複数の文各々についての、前記実行回数を取得するためのコードを有することを特徴とする記録媒体。  
【請求項１２】
請求項１１記載の記録媒体であって、  
前記テストデータ生成ステップを実行するためのコードは、  
前記ソースプログラムをループ解析して、当該ソースプログラムに含まれる一以上のループを抽出し、  
前記実行回数に基いて、前記一以上のループ各々について、当該ループの実行回数であるループ実行回数を取得し、  
前記一以上のループ各々について、当該ループ内のプログラム実行経路である一以上のパスと当該パスの実行回数であるパス実行回数を取得し、  
前記一以上のループ各々について、当該ループに含まれる各パスのパス実行回数に基いて、前記生成パラメータと当該ループのループ実行回数の積の値倍に当該ループを展開し、  
ループ展開後のソースプログラムに含まれる全ての文を通るような入力データを生成するためのコードを有することを特徴とする記録媒体。  
【国際調査報告】
2012104907.tif 000017
2012104907.tif 000018