(57)【特許請求の範囲】
【請求項１】
コンピュータが実行するプログラム分析方法であって、
第１のモジュールと第２のモジュールとを含み、前記第１のモジュールは前記第２のモジュールを呼び出す呼び出し命令を含むプログラムを取得し、
前記第１のモジュールの入力に第１のシンボルを割り当て、前記呼び出し命令の前における第１の処理結果を前記第１のシンボルを用いて表した第１の情報を生成し、前記呼び出し命令の呼び出し結果に第２のシンボルを割り当て、前記第１のモジュールに含まれる複数の第１の実行パスそれぞれの前記呼び出し命令の後における第２の処理結果を前記第２のシンボルを用いて表した第２の情報を生成し、
前記第２のモジュールの入力に第３のシンボルを割り当て、前記第２のモジュールに含まれる複数の第２の実行パスそれぞれの第３の処理結果を前記第３のシンボルを用いて表した第３の情報を生成し、
前記第１の情報が示す前記第１の処理結果と前記第３の情報に用いられた前記第３のシンボルとを対応付け、また、前記第３の情報が示す前記第３の処理結果と前記第２の情報に用いられた前記第２のシンボルとを対応付けることで、前記複数の第１の実行パスと前記複数の第２の実行パスとを合成した複数の合成実行パスそれぞれの処理結果を前記第１のシンボルを用いて表したパス情報を生成する、
プログラム分析方法。
【請求項２】
前記第２の情報は、前記複数の第１の実行パスそれぞれの第１の実行条件を前記第１および第２のシンボルの少なくとも一方を用いて表し、前記第３の情報は、前記複数の第２の実行パスそれぞれの第２の実行条件を前記第３のシンボルを用いて表し、
前記パス情報の生成では、１つの第１の実行パスに対応する前記第１の実行条件と１つの第２の実行パスに対応する前記第２の実行条件とが矛盾しない場合に、前記１つの第１の実行パスと前記１つの第２の実行パスとを合成する、
請求項１記載のプログラム分析方法。
【請求項３】
前記第１の情報は、前記複数の第１の実行パスを前記呼び出し命令の前まで実行した場合に検出される複数の部分実行パスそれぞれについて前記第１の処理結果を示し、
前記パス情報の生成では、前記複数の部分実行パスの前記第１の処理結果と前記複数の第１の実行パスの前記第２の処理結果と前記複数の第２の実行パスの前記第３の処理結果とを合成する、
請求項１記載のプログラム分析方法。
【請求項４】
前記第１のモジュールで使用される変数のうち前記第２のモジュールによって更新される更新変数を前記プログラムから検索し、
前記第２の情報の生成では、前記更新変数に前記第２のシンボルを割り当てる、
請求項１記載のプログラム分析方法。
【請求項５】
第１のモジュールと第２のモジュールとを含み、前記第１のモジュールは前記第２のモジュールを呼び出す呼び出し命令を含むプログラムを記憶する記憶部と、
前記第１のモジュールの入力に第１のシンボルを割り当て、前記呼び出し命令の前における第１の処理結果を前記第１のシンボルを用いて表した第１の情報を生成し、前記呼び出し命令の呼び出し結果に第２のシンボルを割り当て、前記第１のモジュールに含まれる複数の第１の実行パスそれぞれの前記呼び出し命令の後における第２の処理結果を前記第２のシンボルを用いて表した第２の情報を生成し、
前記第２のモジュールの入力に第３のシンボルを割り当て、前記第２のモジュールに含まれる複数の第２の実行パスそれぞれの第３の処理結果を前記第３のシンボルを用いて表した第３の情報を生成し、
前記第１の情報が示す前記第１の処理結果と前記第３の情報に用いられた前記第３のシンボルとを対応付け、また、前記第３の情報が示す前記第３の処理結果と前記第２の情報に用いられた前記第２のシンボルとを対応付けることで、前記複数の第１の実行パスと前記複数の第２の実行パスとを合成した複数の合成実行パスそれぞれの処理結果を前記第１のシンボルを用いて表したパス情報を生成する演算部と、
を有するプログラム分析装置。
【請求項６】
コンピュータに、
第１のモジュールと第２のモジュールとを含み、前記第１のモジュールは前記第２のモジュールを呼び出す呼び出し命令を含むプログラムを取得し、
前記第１のモジュールの入力に第１のシンボルを割り当て、前記呼び出し命令の前における第１の処理結果を前記第１のシンボルを用いて表した第１の情報を生成し、前記呼び出し命令の呼び出し結果に第２のシンボルを割り当て、前記第１のモジュールに含まれる複数の第１の実行パスそれぞれの前記呼び出し命令の後における第２の処理結果を前記第２のシンボルを用いて表した第２の情報を生成し、
前記第２のモジュールの入力に第３のシンボルを割り当て、前記第２のモジュールに含まれる複数の第２の実行パスそれぞれの第３の処理結果を前記第３のシンボルを用いて表した第３の情報を生成し、
前記第１の情報が示す前記第１の処理結果と前記第３の情報に用いられた前記第３のシンボルとを対応付け、また、前記第３の情報が示す前記第３の処理結果と前記第２の情報に用いられた前記第２のシンボルとを対応付けることで、前記複数の第１の実行パスと前記複数の第２の実行パスとを合成した複数の合成実行パスそれぞれの処理結果を前記第１のシンボルを用いて表したパス情報を生成する、
処理を実行させる分析プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はプログラム分析方法、プログラム分析装置および分析プログラムに関する。
【背景技術】
【０００２】
プログラムに条件分岐文が含まれている場合、実行される命令の列（実行パス）はプログラムに対する入力に応じて変化する。そこで、作成されたプログラムを分析して、プログラムから実行パスを抽出することがある。例えば、既存の情報処理システムの改変や交換を行う際、その情報処理システムの開発当初に作成された設計資料が十分に残っていない場合がある。その場合、実装物としてのプログラムから実行パスを抽出し、実行パス毎の入力と出力の関係を判定することで、その情報処理システムの仕様を理解することがある。また、例えば、作成されたプログラムをテストする際、そのプログラムから実行パスを抽出し、抽出された実行パスについてテスト計画を作成することがある。
【０００３】
プログラムの分析方法の１つのとして、シンボリック実行（記号実行）がある。シンボリック実行では、プログラムへの入力値を格納する変数に、具体的な数値や具体的な文字に代えて定数を示すシンボル（記号値）を割り当てる。プログラムにおいて更新される変数の値は、シンボルを含む式として表されることがある。シンボルを用いてプログラムの命令を擬似的に実行することで、具体的な値を次々に入力してプログラムを繰り返し実行する場合よりも、プログラムの実行パスを効率的に抽出できる。
【０００４】
プログラムに条件分岐文が含まれている場合、シンボルは任意の定数を表すため、分岐方向を１つに絞り込めないことがある。具体的な値によって分岐条件の判定がＹＥＳになることもＮＯになることもある場合、その条件分岐文を分割点として実行パスを分割する。すなわち、その分岐条件の判定がＹＥＳになる場合の実行パスと、その分岐条件の判定がＮＯになる場合の実行パスの両方が存在するものとして取り扱う。条件分岐文が増えると、プログラムから抽出される実行パスは指数関数的に増加することが多い。
【０００５】
なお、シンボリック実行を利用してプログラムから実行パスを抽出し、抽出した実行パスをカバーするテストデータを生成するテストデータ生成装置が提案されている。提案のテストデータ生成装置は、シンボリック実行の計算量を削減するため、複数の変数のうち一部の変数のみにシンボルを割り当て、他の変数にはシンボルではない具体的な値を割り当てる。シンボルと具体的な値の組み合わせによってシンボリック実行を行うと、プログラムに含まれる複数の実行パスのうち一部の実行パスが抽出される。テストデータ生成装置は、シンボルを割り当てる変数を切り替えながらシンボリック実行を繰り返すことで、テストすべき実行パスの全てをプログラムから抽出する。
【０００６】
また、シンボリック実行を利用して関数内部の実行パスを探索するソフトウェアテスト方法が提案されている。提案のソフトウェアテスト方法では、関数の戻り値にシンボルを割り当て、シンボルが取り得る値の範囲を示す制約を導出し、制約を満たすように関数についてシンボル実行を行うことで探索する実行パスを制限する。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２０１４−１５３９０８号公報
【特許文献２】特開２０１６−１２３４３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
プログラムでは、あるモジュールが他のモジュールを呼び出すことがある。モジュールは、関数・手続き・メソッド・セクションなど、プログラムに含まれる部分プログラムであって他のモジュールから呼び出されることがあるものであればよい。この場合、プログラムをどのように分析して実行パスを抽出すればよいかが問題となる。
【０００９】
呼び出し元モジュールと呼び出し先モジュールの両方に跨がる実行パスを直接抽出しようとすると、探索する実行パスが膨大になるというパス爆発の問題が生じる。例えば、呼び出し元モジュールに、１回ずつ実行されるＮ個の直列の条件分岐文が含まれ、呼び出し先モジュールに、１回ずつ実行されるＭ個の直列の条件分岐文が含まれているとする（Ｎ，Ｍは２以上の整数）。その場合、２つのモジュールからは最大で２M+N個の実行パスが抽出される。２M+N個の実行パスを直接探索しようとすると、各モジュールの条件分岐文の数（ＮやＭ）の増加に伴って計算量が大きく増加してしまう。
【００１０】
一方、モジュール毎に独立に実行パスを抽出するだけでは、呼び出し元モジュールを正しく分析したことにはならない。他のモジュールを呼び出した後に呼び出し元モジュールで実行される命令は、呼び出し先モジュールの実行結果に依存するためである。
【００１１】
１つの側面では、本発明は、プログラムの実行パスを効率的に分析できるプログラム分析方法、プログラム分析装置および分析プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
１つの態様では、コンピュータが実行するプログラム分析方法が提供される。第１のモジュールと第２のモジュールとを含み、第１のモジュールは第２のモジュールを呼び出す呼び出し命令を含むプログラムを取得する。第１のモジュールの入力に第１のシンボルを割り当て、呼び出し命令の前における第１の処理結果を第１のシンボルを用いて表した第１の情報を生成し、呼び出し命令の呼び出し結果に第２のシンボルを割り当て、第１のモジュールに含まれる複数の第１の実行パスそれぞれの呼び出し命令の後における第２の処理結果を第２のシンボルを用いて表した第２の情報を生成する。第２のモジュールの入力に第３のシンボルを割り当て、第２のモジュールに含まれる複数の第２の実行パスそれぞれの第３の処理結果を第３のシンボルを用いて表した第３の情報を生成する。第１の情報が示す第１の処理結果と第３の情報に用いられた第３のシンボルとを対応付け、また、第３の情報が示す第３の処理結果と第２の情報に用いられた第２のシンボルとを対応付けることで、複数の第１の実行パスと複数の第２の実行パスとを合成した複数の合成実行パスそれぞれの処理結果を第１のシンボルを用いて表したパス情報を生成する。
【００１３】
また、１つの態様では、記憶部と演算部とを有するプログラム分析装置が提供される。また、１つの態様では、コンピュータに実行させる分析プログラムが提供される。
【発明の効果】
【００１４】
１つの側面では、プログラムの実行パスを効率的に分析できる。
【図面の簡単な説明】
【００１５】
【図１】第１の実施の形態のプログラム分析装置の例を示す図である。
【図２】プログラム分析装置のハードウェア例を示すブロック図である。
【図３】プログラムの第１の例を示す図である。
【図４】ロジックテーブルの第１の例を示す図である。
【図５】プログラムの第２の例を示す図である。
【図６】ロジックテーブルの第２の例を示す図である。
【図７】シンボリック実行の分割と部分ロジックの結合の例を示す図である。
【図８】更新変数テーブルとシンボル割り当てテーブルの例を示す図である。
【図９】階層的な更新変数の抽出例を示す図である。
【図１０】途中点と呼び出し先と終点のロジックテーブルの例を示す図である。
【図１１】部分ロジックの簡約化例を示す図である。
【図１２】部分ロジックの結合例を示す図である。
【図１３】部分ロジックの結合例を示す図（続き）である。
【図１４】プログラムの第３の例を示す図である。
【図１５】プログラム分析装置の機能例を示すブロック図である。
【図１６】プログラム分析の手順例を示すフローチャートである。
【図１７】更新変数抽出の手順例を示すフローチャートである。
【図１８】シンボリック実行の手順例を示すフローチャートである。
【図１９】シンボリック実行の手順例を示すフローチャート（続き）である。
【図２０】ロジック簡約化の手順例を示すフローチャートである。
【図２１】ロジック結合の手順例を示すフローチャートである。
【発明を実施するための形態】
【００１６】
以下、本実施の形態を図面を参照して説明する。
［第１の実施の形態］
第１の実施の形態を説明する。
【００１７】
図１は、第１の実施の形態のプログラム分析装置の例を示す図である。
第１の実施の形態のプログラム分析装置１０は、シンボリック実行によってプログラムを分析し、プログラムから実行パスを抽出する。分析対象のプログラムは、プログラミング言語で記述されたソースコードでもよいし、実行可能なオブジェクトコードなどソースコード以外のものでもよい。例えば、プログラム分析装置１０は、既存の情報処理システムの仕様を理解することを目的として、過去に作成されたプログラムから実行パスを抽出するときに用いることができる。また、例えば、プログラム分析装置１０は、新たに構築する情報処理システムをテストすることを目的として、新たに作成されたプログラムからテスト対象の実行パスを抽出するときに用いることができる。
【００１８】
プログラム分析装置１０は、クライアントコンピュータでもよいしサーバコンピュータでもよい。プログラム分析装置１０は、記憶部１１および演算部１２を有する。
記憶部１１は、分析対象のプログラム２０を記憶する。記憶部１１は、ＲＡＭ（Random Access Memory）などの揮発性の半導体メモリでもよいし、ＨＤＤ（Hard Disk Drive）やフラッシュメモリなどの不揮発性の記憶装置でもよい。
【００１９】
演算部１２は、記憶部１１に記憶されたプログラム２０に含まれる実行パスを分析する。演算部１２は、ＣＰＵ（Central Processing Unit）やＤＳＰ（Digital Signal Processor）などのプロセッサでもよい。また、演算部１２は、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などの特定用途の電子回路を含んでもよい。プロセッサは、ＲＡＭなどのメモリ（記憶部１１でもよい）に記憶されたプログラムを実行する。プロセッサが実行するプログラムには、以下に説明する処理を記載した分析プログラムが含まれる。複数のプロセッサの集合を、「マルチプロセッサ」または単に「プロセッサ」と言うこともある。
【００２０】
プログラム２０は、モジュール２１（第１のモジュール）とモジュール２６（第２のモジュール）を含む。モジュール２１，２６はそれぞれ、プログラム２０に含まれる部分プログラムであって他のモジュールから呼び出されることがあるものであればよい。例えば、モジュール２１，２６として関数・手続き・メソッド・セクションなどが挙げられる。モジュール単位の名称はプログラミング言語に依存する。
【００２１】
モジュール２１は、モジュール２６を呼び出す呼び出し命令２２を含む。モジュール２１が呼び出し元モジュールであり、モジュール２６が呼び出し先モジュールである。呼び出し命令２２の一例として、他のセクションを呼び出すＰＥＲＦＯＲＭ文が挙げられる。
【００２２】
演算部１２は、モジュール２１についてシンボリック実行を行う。このとき、演算部１２は、モジュール２１の入力にシンボルｃ１（第１のシンボル）を割り当てる。例えば、演算部１２は、モジュール２１で使用される変数のうちモジュール２１の外部から提供される値を格納する変数に、シンボルｃ１を割り当てる。
【００２３】
演算部１２は、呼び出し命令２２の前における処理結果（第１の処理結果）をシンボルｃ１を用いて表した第１の情報２４を生成する。第１の情報２４は、例えば、モジュール２１で使用される変数のうち呼び出し命令２２の前までに更新された変数の値を、シンボルｃ１を含む式で表したものである。第１の情報２４は、例えば、シンボリック実行によって、呼び出し命令２２の前までの命令をシンボルｃ１を用いて擬似的に実行することで生成できる。一例として、第１の情報２４は、呼び出し命令２２の直前における変数ｘの値がｃ１＋１であるという処理結果を示す。
【００２４】
演算部１２は、呼び出し命令２２の呼び出し結果に、シンボルｃ１とは独立なシンボルｃ２（第２のシンボル）を割り当てる。これにより、モジュール２６がスタブ化され、モジュール２１をモジュール２６とは独立にシンボリック実行することができる。例えば、演算部１２は、モジュール２１で使用される変数のうちモジュール２６によって更新される可能性がある変数に、シンボルｃ２を割り当てる。一例として、演算部１２は、モジュール２１によって更新される変数ｙに、シンボルｃ２を割り当てる。
【００２５】
呼び出し命令２２は、モジュール２６の作用を明示しない形式で記述されていてもよい。例えば、モジュール２６がグローバル変数を更新する場合など、モジュール２６によって更新される値を格納する変数がモジュール２１に明記されていない場合であってもよい。その場合、例えば、演算部１２は、モジュール２１で使用される変数のうちモジュール２６によって更新される可能性のある更新変数を、モジュール２６から検索しておく。
【００２６】
演算部１２は、第１の実行パス２３ａ，２３ｂを含む複数の第１の実行パスを、モジュール２１から検出する。モジュール２１に含まれる１以上の条件分岐命令によって、これら複数の第１の実行パスが分岐する。条件分岐命令は、呼び出し命令２２の前に存在してもよいし、呼び出し命令２２の後に存在してもよい。
【００２７】
演算部１２は、複数の第１の実行パスそれぞれの呼び出し命令２２の後における処理結果（第２の処理結果）をシンボルｃ２を用いて表した第２の情報２５を生成する。第２の情報２５は、例えば、モジュール２１で使用される変数のうち呼び出し命令２２の後に更新された変数の値を、シンボルｃ２を含む式で表したものである。当該式に更にシンボルｃ１が含まれていてもよい。第２の情報２５は、例えば、シンボリック実行によって、呼び出し命令２２の後の命令をシンボルｃ２を用いて擬似的に実行することで生成できる。
【００２８】
第２の情報２５が示す処理結果は、第１の実行パスによって異なる可能性がある。一例として、第２の情報２５は、第１の実行パス２３ａの終了点における変数ｚの値がｃ２＋３であるという処理結果を示す。また、第２の情報２５は、第１の実行パス２３ｂの終了点における変数ｚの値がｃ２−３であるという処理結果を示す。なお、呼び出し命令２２の前に条件分岐命令が存在する場合、第１の情報２４が示す処理結果も、第２の情報２５と同様に第１の実行パスによって異なる可能性がある。
【００２９】
また、演算部１２は、モジュール２１とは独立にモジュール２６についてシンボリック実行を行う。モジュール２６のシンボリック実行は、モジュール２１のシンボリック実行よりも前に行ってもよいし、モジュール２１のシンボリック実行の後に行ってもよい。また、モジュール２６のシンボリック実行は、呼び出し命令２２の前までのシンボリック実行と呼び出し命令２２の後のシンボリック実行との間に行ってもよい。
【００３０】
このとき、演算部１２は、モジュール２６の入力に、シンボルｃ１，ｃ２とは独立なシンボルｃ３（第３のシンボル）を割り当てる。例えば、演算部１２は、モジュール２６で使用される変数のうちモジュール２６の外部から提供される値を格納する変数に、シンボルｃ３を割り当てる。演算部１２は、第２の実行パス２７ａ，２７ｂを含む複数の第２の実行パスを、モジュール２６から検出する。モジュール２６に含まれる１以上の条件分岐命令によって、これら複数の第２の実行パスが分岐する。
【００３１】
演算部１２は、複数の第２の実行パスそれぞれの処理結果（第３の処理結果）をシンボルｃ３を用いて表した第３の情報２８を生成する。第３の情報２８は、例えば、モジュール２６で使用される変数のうちモジュール２６の中で更新された変数の値を、シンボルｃ３を含む式で表したものである。第３の情報２８は、例えば、シンボリック実行によって、モジュール２６の命令をシンボルｃ３を用いて擬似的に実行することで生成できる。
【００３２】
第３の情報２８が示す処理結果は、第２の実行パスによって異なる可能性がある。一例として、第３の情報２８は、第２の実行パス２７ａの終了点における変数ｙの値がｃ３＋２であるという処理結果を示す。また、第３の情報２８は、第２の実行パス２７ｂの終了点における変数ｙの値がｃ３−２であるという処理結果を示す。なお、図１では変数ｘ，ｙ，ｚを使用しているが、これらの変数の一部または全部が同一でもよい。
【００３３】
そして、演算部１２は、複数の第１の実行パスと複数の第２の実行パスとを合成し、合成実行パス３１ａ，３１ｂ，３１ｃ，３１ｄを含む複数の合成実行パスを生成する。合成実行パスは、モジュール２１，２６に跨がる実行パスであり、呼び出し命令２２の前の命令に続けてモジュール２６の中の命令も実行した場合に得られる実行パスと同等である。
【００３４】
このとき、演算部１２は、第１の情報２４、第２の情報２５および第３の情報２８を取得する。演算部１２は、第１の情報２４が示す処理結果と第３の情報２８に用いられたシンボルｃ３とを対応付ける。これは、呼び出し命令２２の前の処理結果は、モジュール２６に対する入力として用いられるためである。例えば、変数ｘの値を示す式とシンボルｃ３とが対応付けられる。また、演算部１２は、第３の情報２８が示す処理結果と第２の情報２５に用いられたシンボルｃ２とを対応付ける。これは、モジュール２６の処理結果は、呼び出し命令２２の後の命令の入力として用いられるためである。例えば、変数ｙの値を示す式とシンボルｃ２とが対応付けられる。
【００３５】
演算部１２は、第１の情報２４、第２の情報２５および第３の情報２８と、上記の対応付けとによって、複数の合成実行パスそれぞれの処理結果をシンボルｃ１を用いて表したパス情報３２を生成する。パス情報３２は、呼び出し命令２２も考慮して、モジュール２１の入力と出力の関係を合成実行パス毎に表したものである。
【００３６】
一例として、演算部１２は、第１の情報２４が示すｘ＝ｃ１＋１を、第３の情報２８のシンボルｃ３に代入する。これにより、第２の実行パス２７ａの処理結果はｙ＝ｃ１＋３と表され、第２の実行パス２７ｂの処理結果はｙ＝ｃ１−１と表される。
【００３７】
更に、演算部１２は、第２の実行パス２７ａ，２７ｂの処理結果を、第２の情報２５のシンボルｃ２に代入する。このとき、演算部１２は、任意の第１の実行パスと任意の第２の実行パスとの組み合わせを検討する。ここでは、第１の実行パス２３ａと第２の実行パス２７ａとを合成して合成実行パス３１ａが生成される。第１の実行パス２３ａと第２の実行パス２７ｂとを合成して合成実行パス３１ｂが生成される。第１の実行パス２３ｂと第２の実行パス２７ａとを合成して合成実行パス３１ｃが生成される。第１の実行パス２３ｂと第２の実行パス２７ｂとを合成して合成実行パス３１ｄが生成される。
【００３８】
演算部１２は、第２の実行パス２７ａのｙ＝ｃ１＋３を、第１の実行パス２３ａのｚ＝ｃ２＋３のシンボルｃ２に代入する。これにより、合成実行パス３１ａの処理結果はｚ＝ｃ１＋６と表される。また、演算部１２は、第２の実行パス２７ｂのｙ＝ｃ１−１を、第１の実行パス２３ａのｚ＝ｃ２＋３のシンボルｃ２に代入する。これにより、合成実行パス３１ｂの処理結果はｚ＝ｃ１＋２と表される。演算部１２は、第２の実行パス２７ａのｙ＝ｃ１＋３を、第１の実行パス２３ｂのｚ＝ｃ２−３のシンボルｃ２に代入する。これにより、合成実行パス３１ｃの処理結果はｚ＝ｃ１と表される。演算部１２は、第２の実行パス２７ｂのｙ＝ｃ１−１を、第１の実行パス２３ｂのｚ＝ｃ２−３のシンボルｃ２に代入する。これにより、合成実行パス３１ｄの処理結果はｚ＝ｃ１−４と表される。
【００３９】
ただし、任意の第１の実行パスと任意の第２の実行パスとを合成した合成実行パスの全てが、プログラム２０において実際に実行される有効な実行パスではないこともある。その場合、演算部１２は、複数の第１の実行パスと複数の第２の実行パスとの間の全ての組み合わせの中から、有効な組み合わせのみを選択するようにしてもよい。
【００４０】
例えば、第２の情報２５は、各第１の実行パスの実行条件（第１の実行条件）を、シンボルｃ１，ｃ２の少なくとも一方を用いて表していてもよい。第１の実行パスの実行条件は、モジュール２１に含まれる条件分岐命令の分岐条件から判定することができる。また、第３の情報２８は、各第２の実行パスの実行条件（第２の実行条件）を、シンボルｃ３を用いて表していてもよい。第２の実行パスの実行条件は、モジュール２６に含まれる条件分岐命令の分岐条件から判定することができる。
【００４１】
この場合、例えば、演算部１２は、ある第１の実行パスの実行条件とある第２の実行パスの実行条件とが矛盾しないとき、当該第１の実行パスと当該第２の実行パスとを合成した合成実行パスを有効と判定することができる。一方、演算部１２は、ある第１の実行パスの実行条件とある第２の実行パスの実行条件とが矛盾するとき、当該第１の実行パスと当該第２の実行パスとを合成した合成実行パスを無効と判定することができる。
【００４２】
第１の実施の形態のプログラム分析装置１０によれば、モジュール２１のシンボリック実行とモジュール２６のシンボリック実行とが独立に実行される。モジュール２１のシンボリック実行によって、呼び出し命令２２の前についての第１の情報２４と、呼び出し命令２２の後についての第２の情報２５とが収集される。また、モジュール２６のシンボリック実行によって、第３の情報２８が収集される。そして、第１の情報２４、第２の情報２５および第３の情報２８に基づいて、モジュール２１から検出された複数の第１の実行パスとモジュール２６から検出された複数の第２の実行パスとが合成される。
【００４３】
これにより、モジュール２１，２６に跨がる実行パスを分析する際のパス爆発を抑制し、プログラム２０の実行パスを効率的に分析することができる。例えば、モジュール２１にＮ個の直列の条件分岐命令が含まれ、モジュール２６にＭ個の直列の条件分岐命令が含まれているとする。モジュール２１，２６に跨がる実行パスをシンボリック実行によって直接検出する場合、最大で２M+N個の実行パスが検出される。一方、第１の実施の形態によれば、シンボリック実行によって検出すべき実行パスは最大で２M＋２N個となる。このため、シンボリック実行の計算量を削減することができる。
【００４４】
また、第１の実施の形態では、モジュール２１から呼び出されるモジュール２６の処理を無視しているわけではなく、モジュール２６から検出された第２の実行パスがモジュール２１から検出された第１の実行パスと合成される。よって、生成されるパス情報３２は、モジュール２１の入力と出力との関係を正しく表すことができる。
【００４５】
［第２の実施の形態］
次に、第２の実施の形態を説明する。
第２の実施の形態のプログラム分析装置は、シンボリック実行によってプログラムから実行パスを抽出し、入力と出力の関係を示すロジック情報を生成する。
【００４６】
図２は、プログラム分析装置のハードウェア例を示すブロック図である。
プログラム分析装置１００は、プロセッサ１０１、ＲＡＭ１０２、ＨＤＤ１０３、画像信号処理部１０４、入力信号処理部１０５、媒体リーダ１０６および通信インタフェース１０７を有する。プログラム分析装置１００の上記ユニットは、バス１０８に接続されている。なお、プログラム分析装置１００は、第１の実施の形態のプログラム分析装置１０に対応する。プロセッサ１０１は、第１の実施の形態の演算部１２に対応する。ＲＡＭ１０２またはＨＤＤ１０３は、第１の実施の形態の記憶部１１に対応する。
【００４７】
プロセッサ１０１は、プログラムの命令を実行する演算回路を含むプロセッサである。プロセッサ１０１は、例えば、ＣＰＵである。プロセッサ１０１は、ＨＤＤ１０３に記憶されたプログラムおよびデータの少なくとも一部をＲＡＭ１０２にロードし、ロードされたプログラムを実行する。なお、プロセッサ１０１が複数のプロセッサコアを備えてもよいし、プログラム分析装置１００が複数のプロセッサを備えてもよい。以下で説明する処理を、複数のプロセッサまたはプロセッサコアを用いて並列に実行してもよい。
【００４８】
ＲＡＭ１０２は、プロセッサ１０１が実行するプログラムや演算に用いるデータを一時的に記憶する揮発性の半導体メモリである。なお、プログラム分析装置１００は、ＲＡＭ以外の種類のメモリを備えてもよいし、複数個のメモリを備えてもよい。
【００４９】
ＨＤＤ１０３は、ＯＳ（Operating System）やミドルウェアやアプリケーションソフトウェアなどのソフトウェアのプログラム、および、データを記憶する不揮発性の記憶装置である。プログラムには、分析プログラムが含まれる。なお、プログラム分析装置１００は、フラッシュメモリやＳＳＤ（Solid State Drive）などの他の種類の記憶装置を備えてもよいし、複数の不揮発性の記憶装置を備えてもよい。
【００５０】
画像信号処理部１０４は、プロセッサ１０１からの命令に従って、プログラム分析装置１００に接続されたディスプレイ１１１に画像を出力する。ディスプレイ１１１としては、ＣＲＴ（Cathode Ray Tube）ディスプレイ、液晶ディスプレイ（ＬＣＤ：Liquid Crystal Display）、プラズマディスプレイ、有機ＥＬ（ＯＥＬ：Organic Electro-Luminescence）ディスプレイなど、任意の種類のディスプレイを用いることができる。
【００５１】
入力信号処理部１０５は、プログラム分析装置１００に接続された入力デバイス１１２から入力信号を取得し、プロセッサ１０１に出力する。入力デバイス１１２としては、マウスやタッチパネルやタッチパッドやトラックボールなどのポインティングデバイス、キーボード、リモートコントローラ、ボタンスイッチなどを用いることができる。また、プログラム分析装置１００に、複数の種類の入力デバイスが接続されていてもよい。
【００５２】
媒体リーダ１０６は、記録媒体１１３に記録されたプログラムやデータを読み取る読み取り装置である。記録媒体１１３として、例えば、磁気ディスク、光ディスク、光磁気ディスク（ＭＯ：Magneto-Optical disk）、半導体メモリなどを使用できる。磁気ディスクには、フレキシブルディスク（ＦＤ：Flexible Disk）やＨＤＤが含まれる。光ディスクには、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）が含まれる。
【００５３】
媒体リーダ１０６は、例えば、記録媒体１１３から読み取ったプログラムやデータを、ＲＡＭ１０２やＨＤＤ１０３などの他の記録媒体にコピーする。読み取られたプログラムは、例えば、プロセッサ１０１によって実行される。なお、記録媒体１１３は、可搬型記録媒体であってもよく、プログラムやデータの配布に用いられることがある。また、記録媒体１１３やＨＤＤ１０３を、コンピュータ読み取り可能な記録媒体と言うことがある。
【００５４】
通信インタフェース１０７は、ネットワーク１１４に接続され、ネットワーク１１４を介して他の装置と通信を行うインタフェースである。通信インタフェース１０７は、スイッチなどの通信装置とケーブルで接続される有線通信インタフェースでもよいし、基地局と無線リンクで接続される無線通信インタフェースでもよい。
【００５５】
次に、シンボリック実行によるプログラムの分析について説明する。
図３は、プログラムの第１の例を示す図である。
プログラム１４１は、分析対象のプログラムの一例である。プログラム１４１は、変数「性別」の値として２文字の文字列を受け取り、変数「出力」の値として１文字を出力する。プログラム１４１は、１４行目に１つ目の条件分岐文を含み、１９行目に２つ目の条件分岐文を含む。１４行目の条件分岐文では、変数「性別」の値が「男性」であるか判定される。変数「性別」の値が「男性」である場合には変数「出力」の値が「Ｍ」に更新され、そうでない場合には変数「出力」の値が「  」（空白）に更新される。また、１９行目の条件分岐文では、変数「性別」の値が「女性」であるか判定される。変数「性別」の値が「女性」である場合には変数「出力」の値が「Ｆ」に更新され、そうでない場合には変数「出力」の値は変化しない。そして、プログラム１４１が終了する。
【００５６】
プログラム１４１には３つの実行パスが存在する。変数「性別」の値に応じて、これら３つの実行パスのうちの何れか１つが実行される。変数「性別」の値が「男性」である場合、１４行目の分岐条件はＹＥＳと判定され、１９行目の分岐条件はＮＯと判定される。この実行パスでは、変数「出力」の値は「Ｍ」になる。変数「性別」の値が「女性」である場合、１４行目の分岐条件はＮＯと判定され、１９行目の分岐条件はＹＥＳと判定される。この実行パスでは、変数「出力」の値は「Ｆ」になる。変数「性別」の値が「男性」でも「女性」でもない場合、１４行目の分岐条件と１９行目の分岐条件の両方がＮＯと判定される。この実行パスでは、変数「出力」の値は「  」（空白）になる。
【００５７】
プログラム１４１は直列の２つの条件分岐文を含むため、分岐条件の内容を無視すれば、実行パスの候補は４つ存在する。しかし、変数「性別」の値が「男性」であることと変数「性別」の値が「女性」であることは矛盾するため、１４行目の分岐条件と１９行目の分岐条件の両方がＹＥＳと判定されることはない。よって、４つの実行パスの候補のうち、実行される可能性のある有効な実行パスは３つである。
【００５８】
条件分岐文において、ある分岐方向（ＹＥＳ方向またはＮＯ方向）に進むための条件を満たす変数の値が少なくとも１つ存在するとき、その分岐方向は「充足可能である」と言うことがある。一方、ある分岐方向に進むための条件を満たす変数の値が存在しないとき、その分岐方向は「充足可能でない」と言うことがある。
【００５９】
プログラム１４１において、１４行目の条件分岐文では変数「性別」の値は制約されていないため、２つの分岐方向は共に充足可能である。一方、１９行目の条件分岐文における充足可能性は、１４行目の条件分岐文で選択した分岐方向に依存する。１４行目のＹＥＳ方向を選択した場合、１９行目のＹＥＳ方向は充足可能でなくなりＮＯ方向のみ充足可能となる。１４行目のＮＯ方向を選択した場合、１９行目の２つの分岐方向は共に充足可能である。よって、有効な実行パスは３つであると判断できる。
【００６０】
ここで、プログラム１４１をシンボリック実行する例を説明する。プログラム分析装置１００は、プログラム１４１に対する入力を示す変数「性別」に、具体的な文字ではなく任意の定数を示す抽象的なシンボル（記号値）を割り当てる。ここでは、変数名と同じ「性別」をシンボルとして用いる。プログラム分析装置１００は、シンボルを用いてプログラム１４１の命令を擬似的に実行していく。
【００６１】
プログラム１４１の始点から１４行目の条件分岐文の前までは、実行パスの分岐は存在しない。１４行目の条件分岐文について、この時点ではその実行パスが選択される条件（パス条件）は存在せず、２つの分岐方向は共に充足可能である。よって、プログラム分析装置１００は、１４行目の条件分岐文において実行パスを分割し、一方の実行パスを選択する。ここでは、プログラム分析装置１００はＹＥＳ方向の実行パスを選択したとする。
【００６２】
次に、１９行目の条件分岐文について、この時点におけるパス条件はシンボル「性別」が「男性」であることであるため、ＹＥＳ方向は充足可能でなくＮＯ方向は充足可能である。よって、プログラム分析装置１００はＮＯ方向を選択する。その後、この１番目の実行パスは終了する。プログラム分析装置１００は、１番目の実行パスのパス条件を、シンボル「性別」が「男性」でありかつシンボル「性別」が「女性」でないと判定する。また、プログラム分析装置１００は、１番目の実行パスの処理結果（パス出力）を、変数「出力」の値が「Ｍ」であると判定する。
【００６３】
１番目の実行パスが終了すると、プログラム分析装置１００は、実行パスの直近の分割点まで戻り、未選択の実行パスを選択する。ここでは、プログラム分析装置１００は、１４行目の条件分岐文まで戻ってＮＯ方向の実行パスを選択する。
【００６４】
１９行目の条件分岐文について、この時点におけるパス条件はシンボル「性別」が「男性」でないことであるため、ＹＥＳ方向とＮＯ方向の何れも充足可能である。よって、プログラム分析装置１００は、１９行目の条件分岐文において実行パスを更に分割し、一方の実行パスを選択する。ここでは、プログラム分析装置１００はＹＥＳ方向の実行パスを選択したとする。その後、この２番目の実行パスは終了する。プログラム分析装置１００は、２番目の実行パスのパス条件を、シンボル「性別」が「男性」でなくかつシンボル「性別」が「女性」であると判定する。また、プログラム分析装置１００は、２番目の実行パスのパス出力を、変数「出力」の値が「Ｆ」であると判定する。
【００６５】
２番目の実行パスが終了すると、プログラム分析装置１００は、１９行目の条件分岐文まで戻ってＮＯ方向の実行パスを選択する。その後、この３番目の実行パスは終了する。プログラム分析装置１００は、３番目の実行パスのパス条件を、シンボル「性別」が「男性」でなくかつシンボル「性別」が「女性」でないと判定する。また、プログラム分析装置１００は、３番目の実行パスのパス出力を、変数「出力」の値が「  」（空白）であると判定する。そして、未選択の実行パスが存在しないためシンボリック実行が終了する。
【００６６】
なお、プログラム分析装置１００は、実行パスの分割点において、その時点のパス条件と各変数の値とを保存しておく。プログラム分析装置１００は、１つの実行パスが終了して分割点までバックトラックしたとき、保存しておいたパス条件と各変数の値とを引き継いで、未選択の分岐方向に対応する他の実行パスの探索を続ける。
【００６７】
図４は、ロジックテーブルの第１の例を示す図である。
プログラム分析装置１００は、プログラム１４１のシンボリック実行の結果として、ロジックテーブル１４２を生成する。プログラム分析装置１００は、生成したロジックテーブル１４２を、プログラム分析装置１００が備えるディスプレイに表示する。
【００６８】
ロジックテーブル１４２は、プログラム１４１に対する入力とプログラム１４１からの出力との関係（ロジック）を示す。ロジックテーブル１４２は、パス番号、パス条件およびパス出力の項目を有する。パス番号の項目には、シンボリック実行によって検出された実行パスの識別番号が記載される。パス条件の項目には、実行パスが選択されるための入力の条件が記載される。パス出力の項目には、実行パスの終点における出力変数の値が記載される。パス条件およびパス出力は、シンボルを用いて表されることがある。
【００６９】
前述のように、１番目の実行パスのパス条件は、「性別が男性である」かつ「性別が女性でない」ことである。これは、「性別が男性である」と簡約化できる。１番目の実行パスのパス出力は、「出力がＭである」ことである。２番目の実行パスのパス条件は、「性別が男性でない」かつ「性別が女性である」ことである。これは、「性別が女性である」と簡約化できる。２番目の実行パスのパス出力は、「出力がＦである」ことである。３番目の実行パスのパス条件は、「性別が男性でない」かつ「性別が女性でない」ことである。３番目の実行パスのパス出力は、「出力が空白である」ことである。
【００７０】
なお、条件分岐文における充足可能性の判断やパス条件の簡約化には、数式処理技術を利用することができる。プログラム分析装置１００は、ＳＭＴ（Satisfiability Modulo Theories）ソルバやＳＡＴ（Satisfiability）ソルバを用いてもよい。パス条件は、例えば、シンボルを含む式をシンボルについて解くことで簡約化できる。
【００７１】
次に、シンボリック実行におけるパス爆発について説明する。
図５は、プログラムの第２の例を示す図である。
プログラム１２１は、プログラム１４１とは異なる分析対象のプログラムの例である。プログラム１２１は、「入力１」の値として１０進数３桁以下の数値を受け取り、「出力１」の値として１０進数３桁以下の数値を出力する。プログラム１２１は、セクションＡとセクションＢという２つのモジュールを含む。また、プログラム１２１は、「変数１」という変数を含む。「変数１」は、セクションＡとセクションＢの両方から参照および更新を行うことができるグローバル変数である。
【００７２】
プログラム１２１は、受け取った「入力１」の値を「変数１」に代入してセクションＡを呼び出す。プログラム１２１は、セクションＡが終了すると「変数１」の値を「出力１」に代入する。そして、プログラム１２１の処理が終了する。
【００７３】
セクションＡは、１７行目と２５行目に条件分岐文を含み、２３行目にセクションＢを呼び出す呼び出し文を含む。セクションＡは、セクションＡの外部から与えられる「変数１」の値を使用する。セクションＡは、「変数１」の値が１０より大きい場合には「変数１」の値を１増加させ、「変数１」の値が１０以下である場合には「変数１」の値を１減少させる。次に、セクションＡはセクションＢを呼び出す。セクションＢを呼び出すＰＥＲＦＯＲＭ文には、戻り値を格納する変数が明記されていない。このため、セクションＢによって「変数１」の値が更新されているか否かは、セクションＡの命令文のみからでは不明である。すなわち、ＰＥＲＦＯＲＭ文では、呼び出し先のセクションの作用は不明となる。その後、セクションＡは、「変数１」の値が３０より小さい場合には「変数１」の値を３増加させ、「変数１」の値が３０以上である場合には「変数１」の値を３減少させる。そして、セクションＡの処理が終了する。
【００７４】
セクションＢは、３４行目に条件分岐文を含む。セクションＢは、セクションＢの外部から与えられる「変数１」の値を使用する。セクションＢは、「変数１」の値が２０より大きい場合には「変数１」の値を２増加させ、「変数１」の値が２０以下である場合には「変数１」の値を２減少させる。そして、セクションＢの処理が終了する。
【００７５】
プログラム分析装置１００は、シンボリック実行によって分析する分析範囲を、１つのプログラム全体ではなく、一部のセクションなどプログラム内の一部のモジュールに限定することもできる。これにより、シンボリック実行の計算量を削減することができる。分析範囲は、プログラム分析装置１００のユーザが指定することができる。プログラム１２１については、セクションＡを分析範囲に指定することを考える。ただし、ここでは、セクションＡの呼び出し先についても連続して実行パスを辿るものとする。
【００７６】
セクションＡは２つの条件分岐文を含み、セクションＢは１つの条件分岐文を含む。よって、セクションＡとセクションＢに跨がる実行パスの候補は、８つ存在する。ただし、以下に説明するように、有効な実行パスはそのうち４つである。
【００７７】
プログラム分析装置１００は、セクションＡの入力が格納される「変数１」にシンボル「変数１＿Ａ」を割り当てる。１７行目において変数１＿Ａは制約されていないため、２つの分岐方向は何れも充足可能である。プログラム分析装置１００は、ＹＥＳ方向を選択し、「変数１」の値を変数１＿Ａ＋１に更新する。次に、３４行目においてパス条件は変数１＿Ａが１０より大きいことであるため、２つの分岐方向は何れも充足可能である。プログラム分析装置１００は、ＹＥＳ方向を選択し、「変数１」の値を変数１＿Ａ＋１＋２＝変数１＿Ａ＋３に更新する。次に、２５行目においてパス条件は変数１＿Ａが１０より大きくかつ変数１＿Ａ＋１が２０より大きいことであるため、２つの分岐方向は何れも充足可能である。プログラム分析装置１００は、ＹＥＳ方向を選択し、「変数１」の値を変数１＿Ａ＋１＋２＋３＝変数１＿Ａ＋６に更新する。
【００７８】
これにより、１番目の実行パスが終了する。１番目の実行パスのパス条件は、変数１＿Ａが１０より大きく、変数１＿Ａ＋１が２０より大きくかつ変数１＿Ａ＋１＋２が３０より小さいことである。すなわち、１番目の実行パスのパス条件は、変数１＿Ａが１９より大きく２７より小さいことである。また、１番目の実行パスのパス出力は、「変数１」の値が変数１＿Ａ＋６であることである。
【００７９】
同様にして、プログラム分析装置１００は、プログラム１２１から残りの３つの実行パスを検出する。２番目の実行パスは、１７行目のＹＥＳ方向と３４行目のＹＥＳ方向と２５行目のＮＯ方向を選択したものである。よって、２番目の実行パスのパス条件は、変数１＿Ａが１０より大きく、変数１＿Ａ＋１が２０より大きくかつ変数１＿Ａ＋１＋２が３０以上であることである。すなわち、２番目の実行パスのパス条件は、変数１＿Ａが２７以上であることである。また、２番目の実行パスのパス出力は、「変数１」の値が変数１＿Ａ＋１＋２−３＝変数１＿Ａであることである。
【００８０】
３番目の実行パスは、１７行目のＹＥＳ方向と３４行目のＮＯ方向と２５行目のＹＥＳ方向を選択したものである。よって、３番目の実行パスのパス条件は、変数１＿Ａが１０より大きく、変数１＿Ａ＋１が２０以下でありかつ変数１＿Ａ＋１−２が３０より小さいことである。すなわち、３番目の実行パスのパス条件は、変数１＿Ａが１０より大きく１９以下であることである。また、３番目の実行パスのパス出力は、「変数１」の値が変数１＿Ａ＋１−２＋３＝変数１＿Ａ＋２であることである。
【００８１】
４番目の実行パスは、１７行目のＮＯ方向と３４行目のＮＯ方向と２５行目のＹＥＳ方向を選択したものである。よって、４番目の実行パスのパス条件は、変数１＿Ａが１０以下であり、変数１＿Ａ−１が２０以下でありかつ変数１＿Ａ−１−２が３０より小さいことである。すなわち、４番目の実行パスのパス条件は、変数１＿Ａが１０以下であることである。また、４番目の実行パスのパス出力は、「変数１」の値が変数１＿Ａ−１−２＋３＝変数１＿Ａであることである。他の分岐方向の組み合わせは充足可能でない。
【００８２】
図６は、ロジックテーブルの第２の例を示す図である。
プログラム分析装置１００は、上記のシンボリック実行の結果として、ロジックテーブル１２９を生成する。プログラム分析装置１００は、生成したロジックテーブル１２９を、プログラム分析装置１００が備えるディスプレイに表示する。
【００８３】
ロジックテーブル１２９は、分析範囲であるセクションＡに対する入力とセクションＡからの出力との関係を示す。ロジックテーブル１２９は、ロジックテーブル１４２と同様にパス番号、パス条件およびパス出力の項目を有する。ロジックテーブル１２９には、検出された４つの実行パスのロジックが記載される。パス条件やパス出力は、簡約化されて表示されてもよいし簡約化せずに表示されてもよい。図６では、簡約化前のパス条件およびパス出力と簡約化後のパス条件およびパス出力の両方を表示している。
【００８４】
ところで、上記のシンボリック実行の例では、分析範囲であるセクションＡと呼び出し先であるセクションＢとに跨がる実行パスを直接検出した。しかし、このシンボリック実行の方法では、条件分岐文の増加に応じて検出される実行パスが指数関数的に増加するというパス爆発の問題が生じる。一方、呼び出し文を無視してセクションＡのみを分析しても、セクションＡのロジックを正しく分析したことにはならない。セクションＡが使用する「変数１」の値をセクションＢが更新するためである。そこで、プログラム分析装置１００は、次のような方法でシンボリック実行を行う。
【００８５】
図７は、シンボリック実行の分割と部分ロジックの結合の例を示す図である。
プログラム分析装置１００は、分析範囲であるセクションＡのシンボリック実行と呼び出し先であるセクションＢのシンボリック実行とを分割して独立に行う。セクションＡにＮ個の条件分岐文が含まれ、セクションＢにＭ個の条件分岐文が含まれる場合、分割しないシンボリック実行の計算量は２N+Mとなる。一方、分割したシンボリック実行の計算量は２N＋２Mとなり、分割しない場合よりも計算量が小さくなる。プログラム分析装置１００は、セクションＡのシンボリック実行によって取得される部分ロジックとセクションＢのシンボリック実行によって取得される部分ロジックとを事後的に結合する。
【００８６】
具体的には、プログラム分析装置１００は、セクションＡの入力を格納する「変数１」にシンボル「Ｘ」を割り当て、セクションＡのシンボリック実行を開始する。プログラム分析装置１００は、セクションＢを呼び出す呼び出し文の直前において途中点ロジックを保存しておく。呼び出し文の直前では、パス出力が変数１＝Ｘ＋１であるロジックと、パス出力が変数１＝Ｘ−１であるロジックとが検出されている。
【００８７】
次に、プログラム分析装置１００は、セクションＡのシンボリック実行において、呼び出し文は実行せずにセクションＢをスタブ化する。スタブ化において、プログラム分析装置１００は、セクションＢによって更新される可能性のある更新変数に、シンボル「Ｘ」とは独立なシンボルを割り当てる。更新変数は、予めセクションＢの命令文を走査することで検索することができる。ここでは、プログラム分析装置１００は、「変数１」にシンボル「Ｚ」を割り当てる。プログラム分析装置１００は、シンボル「Ｚ」を用いてセクションＡのシンボリック実行を継続し、セクションＡの終点において終点ロジックを保存する。セクションＡの終点では、パス出力が変数１＝Ｚ＋３であるロジックと、パス出力が変数１＝Ｚ−３であるロジックとが検出されている。
【００８８】
また、プログラム分析装置１００は、セクションＢの入力を格納する「変数１」にシンボル「Ｙ」を割り当て、セクションＢのシンボリック実行を開始する。プログラム分析装置１００は、セクションＢの終点において呼び出し先ロジックを保存する。セクションＢの終点では、パス出力が変数１＝Ｙ＋２であるロジックと、パス出力が変数１＝Ｙ−２であるロジックとが検出されている。
【００８９】
そして、プログラム分析装置１００は、途中点ロジックと終点ロジックと呼び出し先ロジックとを結合して、セクションＡとセクションＢに跨がるロジックを再現する。プログラム分析装置１００は、途中点ロジックが示すパス出力とセクションＢの入力を示すシンボル「Ｙ」とを対応付ける。また、プログラム分析装置１００は、呼び出し先ロジックが示すパス出力とセクションＢのスタブ化に使用したシンボル「Ｚ」とを対応付ける。図７のパス候補テーブル１４３に示すように、途中点ロジックと終点ロジックと呼び出し先ロジックの組み合わせの候補は８通り存在する。
【００９０】
すなわち、変数１＝Ｘ＋１と変数１＝Ｙ＋２と変数１＝Ｚ＋３との組み合わせから、変数１＝Ｘ＋１＋２＋３というパス出力が考えられる。変数１＝Ｘ＋１と変数１＝Ｙ＋２と変数１＝Ｚ−３との組み合わせから、変数１＝Ｘ＋１＋２−３というパス出力が考えられる。変数１＝Ｘ＋１と変数１＝Ｙ−２と変数１＝Ｚ＋３との組み合わせから、変数１＝Ｘ＋１−２＋３というパス出力が考えられる。変数１＝Ｘ＋１と変数１＝Ｙ−２と変数１＝Ｚ−３との組み合わせから、変数１＝Ｘ＋１−２−３というパス出力が考えられる。
【００９１】
変数１＝Ｘ−１と変数１＝Ｙ＋２と変数１＝Ｚ＋３との組み合わせから、変数１＝Ｘ−１＋２＋３というパス出力が考えられる。変数１＝Ｘ−１と変数１＝Ｙ＋２と変数１＝Ｚ−３との組み合わせから、変数１＝Ｘ−１＋２−３というパス出力が考えられる。変数１＝Ｘ−１と変数１＝Ｙ−２と変数１＝Ｚ＋３との組み合わせから、変数１＝Ｘ−１−２＋３というパス出力が考えられる。変数１＝Ｘ−１と変数１＝Ｙ−２と変数１＝Ｚ−３との組み合わせから、変数１＝Ｘ−１−２−３というパス出力が考えられる。
【００９２】
ただし、前述のように、上記の８通りのロジックの全てが有効であるわけではない。プログラム分析装置１００は、途中点ロジックと終点ロジックと呼び出し先ロジックの組み合わせのうち、パス条件が矛盾しない組み合わせのみを選択する。すなわち、プログラム分析装置１００は、途中点ロジックのパス条件と終点ロジックのパス条件と呼び出し先ロジックのパス条件とを結合し、結合したパス条件が充足可能であるか判定する。
【００９３】
次に、シンボリック実行の分割と部分ロジックの結合の手順について説明する。
図８は、更新変数テーブルとシンボル割り当てテーブルの例を示す図である。
プログラム分析装置１００は、分析範囲から、ＰＥＲＦＯＲＭ文のように作用の記載がない呼び出し文（作用が不明な呼び出し文）を検出する。プログラム分析装置１００は、検出した呼び出し文によって呼び出されるモジュールから更新変数を検索し、更新変数テーブル１２２を生成する。更新変数テーブル１２２は、モジュール名および更新変数の項目を有する。モジュール名の項目には、セクション名などのモジュール識別情報が記載される。更新変数の項目には、呼び出し先のモジュール内で値が更新される変数の変数名が記載される。更新変数は、１つのモジュールにつき２以上存在することもある。更新変数は、例えば、代入式の左辺やＭＯＶＥ文の第２引数に記載された変数である。
【００９４】
プログラム分析装置１００は、シンボリック実行の途中で作用の記載がない呼び出し文を検出すると、更新変数テーブル１２２に記載された更新変数にシンボルを割り当てる。プログラム分析装置１００は、シンボル割り当てテーブル１２３を生成する。シンボル割り当てテーブル１２３は、変数名およびシンボルの項目を有する。変数名の項目には、更新変数の変数名が記載される。シンボルの項目には、呼び出し文の直後に更新変数に割り当てられたシンボルが記載される。一例として、更新変数に割り当てられるシンボルは、変数名、呼び出し文がＰＥＲＦＯＲＭ文であることを示す文字列、呼び出し文の行番号、呼び出し先モジュールの名称、その呼び出し文の実行回数を連結したものである。よって、例えば、プログラム１２１の２３行目の通過直後、「変数１」にシンボル「変数１＿Ｐｅｒｆｏｒｍ＿２３＿セクションＢ＿１」が割り当てられる。
【００９５】
図９は、階層的な更新変数の抽出例を示す図である。
分析範囲から呼び出されたモジュールが更に他のモジュールを呼び出している場合、更新変数は階層的に検索される。ここでは、分析範囲がセクション１４４であり、セクション１４４からセクション１４４ａ（セクションＡ１）とセクション１４４ｂ（セクションＢ１）が呼び出され、セクション１４４ｂからセクション１４４ｃ（セクションＢ２）が呼び出されるとする。セクション１４４ａは、変数「ａ１１」，「ａ１２」を更新する。セクション１４４ｂは、変数「ｂ１１」，「ｂ１２」を更新する。セクション１４４ｃは、変数「ｂ２１」を更新する。この場合、プログラム分析装置１００は、更新変数テーブル１２２に対応する更新変数テーブル１４５を生成する。
【００９６】
プログラム分析装置１００は、セクション１４４からセクション１４４ａを辿り、セクション１４４の１つ目の呼び出し文について変数「ａ１１」，「ａ１２」を更新変数として検出する。プログラム分析装置１００は、セクション１４４ａと変数「ａ１１」，「ａ１２」とを対応付けて更新変数テーブル１４５に登録する。また、プログラム分析装置１００は、セクション１４４からセクション１４４ｂ，１４４ｃを辿り、セクション１４４の２つ目の呼び出し文について変数「ｂ１１」，「ｂ１２」，「ｂ２１」を更新変数として検出する。プログラム分析装置１００は、セクション１４４ｂと変数「ｂ１１」，「ｂ１２」，「ｂ２１」とを対応付けて更新変数テーブル１４５に登録する。
【００９７】
図１０は、途中点と呼び出し先と終点のロジックテーブルの例を示す図である。
プログラム分析装置１００は、シンボリック実行によって途中点ロジックテーブル１２４、呼び出し先ロジックテーブル１２５および終点ロジックテーブル１２６を生成する。
【００９８】
途中点ロジックテーブル１２４は、パス番号、パス条件およびパス出力の項目を有する。パス番号の項目には、呼び出し元モジュールの呼び出し文の前までに検出されたロジックの識別番号が記載される。パス条件の項目には、呼び出し文の直前におけるパス条件が記載される。パス出力の項目には、呼び出し文の直前における変数の値が記載される。途中点ロジックテーブル１２４のパス条件およびパス出力には、呼び出し元モジュールの入力に割り当てられたシンボルを用いることができる。
【００９９】
プログラム１２１について、途中点ロジックテーブル１２４には、パス条件が「変数１＿Ａが１０より大きい」、パス出力が「変数１＝変数１＿Ａ＋１」というロジックが登録される。また、途中点ロジックテーブル１２４には、パス条件が「変数１＿Ａが１０以下」、パス出力が「変数１＝変数１＿Ａ−１」というロジックが登録される。
【０１００】
呼び出し先ロジックテーブル１２５は、パス番号、パス条件およびパス出力の項目を有する。パス番号の項目には、呼び出し先モジュールの始点から終点の間に検出されたロジックの識別番号が記載される。パス条件の項目には、呼び出し先モジュールの終点におけるパス条件が記載される。パス出力の項目には、呼び出し先モジュールの終点における変数の値が記載される。呼び出し先ロジックテーブル１２５のパス条件およびパス出力には、呼び出し先モジュールの入力に割り当てられたシンボルを用いることができる。
【０１０１】
プログラム１２１について、呼び出し先ロジックテーブル１２５には、パス条件が「変数１＿Ｂが２０より大きい」、パス出力が「変数１＝変数１＿Ｂ＋２」というロジックが登録される。また、呼び出し先ロジックテーブル１２５には、パス条件が「変数１＿Ｂが２０以下」、パス出力が「変数１＝変数１＿Ｂ−２」というロジックが登録される。なお、シンボル「変数１＿Ｂ」はセクションＢの入力を示す。
【０１０２】
終点ロジックテーブル１２６は、パス番号、パス条件およびパス出力の項目を有する。パス番号の項目には、呼び出し元モジュールの始点から終点の間に検出されたロジックの識別番号が記載される。パス条件の項目には、呼び出し元モジュールの終点におけるパス条件が記載される。パス出力の項目には、呼び出し元モジュールの終点における変数の値が記載される。終点ロジックテーブル１２６のパス条件およびパス出力には、呼び出し元モジュールの入力に割り当てられたシンボルや、呼び出し文の直後に更新変数に対して割り当てられたシンボルを用いることができる。
【０１０３】
プログラム１２１について、終点ロジックテーブル１２６には、パス条件が「変数１＿Ａが１０より大きい」かつ「変数１＿Ｐｅｒｆｏｒｍ＿２３＿セクションＢ＿１が３０より小さい」、パス出力が「変数１＝変数１＿Ｐｅｒｆｏｒｍ＿２３＿セクションＢ＿１＋３」というロジックが登録される。また、終点ロジックテーブル１２６には、パス条件が「変数１＿Ａが１０より大きい」かつ「変数１＿Ｐｅｒｆｏｒｍ＿２３＿セクションＢ＿１が３０以上」、パス出力が「変数１＝変数１＿Ｐｅｒｆｏｒｍ＿２３＿セクションＢ＿１−３」というロジックが登録される。
【０１０４】
また、終点ロジックテーブル１２６には、パス条件が「変数１＿Ａが１０以下」かつ「変数１＿Ｐｅｒｆｏｒｍ＿２３＿セクションＢ＿１が３０より小さい」、パス出力が「変数１＝変数１＿Ｐｅｒｆｏｒｍ＿２３＿セクションＢ＿１＋３」というロジックが登録される。また、終点ロジックテーブル１２６には、パス条件が「変数１＿Ａが１０以下」かつ「変数１＿Ｐｅｒｆｏｒｍ＿２３＿セクションＢ＿１が３０以上」、パス出力が「変数１＝変数１＿Ｐｅｒｆｏｒｍ＿２３＿セクションＢ＿１−３」というロジックが登録される。なお、シンボル「変数１＿Ｐｅｒｆｏｒｍ＿２３＿セクションＢ」は、呼び出し文の直後に「変数１」に割り当てられたシンボルである。
【０１０５】
図１１は、部分ロジックの簡約化例を示す図である。
プログラム分析装置１００は、シンボリック実行が終了すると、途中点ロジックテーブル１２４、呼び出し先ロジックテーブル１２５および終点ロジックテーブル１２６を取得する。プログラム分析装置１００は、途中点ロジックテーブル１２４、呼び出し先ロジックテーブル１２５および終点ロジックテーブル１２６をそれぞれ簡約化する。図１０に示した途中点ロジックテーブル１２４および呼び出し先ロジックテーブル１２５は簡約化する余地がないため、ここでは終点ロジックテーブル１２６の簡約化の例を説明する。
【０１０６】
プログラム分析装置１００は、終点ロジックテーブル１２６から、パス出力が同じでパス条件が異なるロジックを検索する。プログラム分析装置１００は、該当する複数のロジックのパス条件を選言（ＯＲ）で連結することで、該当する複数のロジックを１つに統合する。図１１の例では、図１０の終点ロジックテーブル１２６のロジック＃１とロジック＃３とが統合され、ロジック＃１ｘに変換されている。また、ロジック＃２とロジック＃４とが統合され、ロジック＃２ｘに変換されている。
【０１０７】
ロジック＃１ｘのパス条件は、「変数１＿Ａが１０より大きく変数１＿Ｐｅｒｆｏｒｍ＿２３＿セクションＢ＿１が３０より小さい」または「変数１＿Ａが１０以下で変数１＿Ｐｅｒｆｏｒｍ＿２３＿セクションＢ＿１が３０より小さい」である。ロジック＃１ｘのパス出力は、「変数１＝変数１＿Ｐｅｒｆｏｒｍ＿２３＿セクションＢ＿１＋３」である。ロジック＃２ｘのパス条件は、「変数１＿Ａが１０より大きく変数１＿Ｐｅｒｆｏｒｍ＿２３＿セクションＢ＿１が３０以上」または「変数１＿Ａが１０以下で変数１＿Ｐｅｒｆｏｒｍ＿２３＿セクションＢ＿１が３０以上」である。ロジック＃２ｘのパス出力は、「変数１＝変数１＿Ｐｅｒｆｏｒｍ＿２３＿セクションＢ＿１−３」である。
【０１０８】
プログラム分析装置１００は、統合したロジックのパス条件を数式処理技術を用いて簡約化する。図１１の例では、ロジック＃１ｘのパス条件は、「変数１＿Ａが１０より大きいかまたは変数１＿Ａが１０以下」かつ「変数１＿Ｐｅｒｆｏｒｍ＿２３＿セクションＢ＿１が３０より小さい」と変形できる。よって、ロジック＃１ｘのパス条件は、「変数１＿Ｐｅｒｆｏｒｍ＿２３＿セクションＢ＿１が３０より小さい」と簡約化される。また、ロジック＃２ｘのパス条件は、「変数１＿Ａが１０より大きいかまたは変数１＿Ａが１０以下」かつ「変数１＿Ｐｅｒｆｏｒｍ＿２３＿セクションＢ＿１が３０以上」と変形できる。よって、ロジック＃２ｘのパス条件は、「変数１＿Ｐｅｒｆｏｒｍ＿２３＿セクションＢ＿１が３０以上」と簡約化される。上記のパス条件の簡約化には、例えば、クワイン・マクラスキー法を用いることができる。
【０１０９】
プログラム分析装置１００は、更に、簡約化したパス条件が同じでパス出力が異なるロジックを検索する。プログラム分析装置１００は、該当する複数のロジックのパス出力を連言（ＡＮＤ）で連結することで、該当する複数のロジックを１つに統合する。ただし、図１１の例では、これに該当するロジックは存在しない。
【０１１０】
図１２は、部分ロジックの結合例を示す図である。
プログラム分析装置１００は、途中点ロジックテーブル１２４、呼び出し先ロジックテーブル１２５および終点ロジックテーブル１２６をそれぞれ簡約化すると、これら３つのロジックテーブルのロジックを結合する。まず、プログラム分析装置１００は、途中点ロジックテーブル１２４のロジックと呼び出し先ロジックテーブル１２５のロジックとを結合し、中間結合ロジックテーブル１２７を生成する。
【０１１１】
プログラム分析装置１００は、途中点ロジックテーブル１２４から１つの途中点ロジックを選択し、呼び出し先ロジックテーブル１２５から１つの呼び出し先ロジックを選択する。プログラム分析装置１００は、選択した途中点ロジックのパス出力を、選択した呼び出し先ロジックのパス条件に用いられているシンボルに代入する。そして、プログラム分析装置１００は、代入結果と途中点ロジックのパス条件との連言（ＡＮＤ）を、中間結合ロジックのパス条件として算出する。プログラム分析装置１００は、算出した中間結合ロジックのパス条件が充足可能か判定し、充足可能である場合にはその途中点ロジックと呼び出し先ロジックの組み合わせを有効な組み合わせとして採用する。一方、プログラム分析装置１００は、充足可能でない場合にはその途中点ロジックと呼び出し先ロジックの組み合わせを無効な組み合わせであるとして採用しない。
【０１１２】
プログラム分析装置１００は、有効な組み合わせについて、途中点ロジックのパス出力を、呼び出し先ロジックのパス出力に用いられているシンボルに代入して、中間結合ロジックのパス出力を算出する。プログラム分析装置１００は、有効な組み合わせについて算出したパス条件とパス出力とを、中間結合ロジックテーブル１２７に登録する。
【０１１３】
プログラム１２１の場合、プログラム分析装置１００は、途中点ロジックのパス出力の「変数１」の値を、呼び出し先ロジックのシンボル「変数１＿Ｂ」に代入することになる。プログラム分析装置１００は、途中点ロジック＃１と呼び出し先ロジック＃１を選択し、「変数１＿Ａが１０より大きい」かつ「変数１＿Ａ＋１が２０より大きい」というパス条件を算出する。これは、「変数１＿Ａ＋１が２０より大きい」と同等である。このパス条件は充足可能である（このパス条件を満たすようなシンボル「変数１＿Ａ」が存在する）ため、プログラム分析装置１００は、途中点ロジック＃１と呼び出し先ロジック＃１の組み合わせを、中間結合ロジック＃１として採用する。中間結合ロジック＃１のパス出力は、「変数１＝変数１＿Ａ＋１＋２」である。
【０１１４】
また、プログラム分析装置１００は、途中点ロジック＃１と呼び出し先ロジック＃２を選択し、「変数１＿Ａが１０より大きい」かつ「変数１＿Ａ＋１が２０以下」というパス条件を算出する。このパス条件は充足可能であるため、プログラム分析装置１００は、途中点ロジック＃１と呼び出し先ロジック＃２の組み合わせを、中間結合ロジック＃２として採用する。中間結合ロジック＃２のパス出力は、「変数１＝変数１＿Ａ＋１−２」である。また、プログラム分析装置１００は、途中点ロジック＃２と呼び出し先ロジック＃１を選択し、「変数１＿Ａが１０以下」かつ「変数１＿Ａ＋１が２０より大きい」というパス条件を算出する。このパス条件は充足可能でないため、プログラム分析装置１００は、途中点ロジック＃２と呼び出し先ロジック＃１の組み合わせを採用しない。
【０１１５】
また、プログラム分析装置１００は、途中点ロジック＃２と呼び出し先ロジック＃２を選択し、「変数１＿Ａが１０以下」かつ「変数１＿Ａ＋１が２０以下」というパス条件を算出する。これは、「変数１＿Ａ＋１が１０以下」と同等である。このパス条件は充足可能であるため、プログラム分析装置１００は、途中点ロジック＃２と呼び出し先ロジック＃２の組み合わせを、中間結合ロジック＃３として採用する。中間結合ロジック＃３のパス出力は、「変数１＝変数１＿Ａ−１−２」である。
【０１１６】
図１３は、部分ロジックの結合例を示す図（続き）である。
次に、プログラム分析装置１００は、中間結合ロジックテーブル１２７のロジックと終点ロジックテーブル１２６のロジックとを結合し、ロジックテーブル１２８を生成する。
【０１１７】
プログラム分析装置１００は、中間結合ロジックテーブル１２７から１つの中間結合ロジックを選択し、終点ロジックテーブル１２６から１つの終点ロジックを選択する。プログラム分析装置１００は、選択した中間結合ロジックのパス出力を、選択した終点ロジックのパス条件に用いられているシンボルに代入する。そして、プログラム分析装置１００は、代入結果と中間結合ロジックのパス条件との連言（ＡＮＤ）を、結合したロジックのパス条件として算出する。プログラム分析装置１００は、算出したロジックのパス条件が充足可能か判定し、充足可能である場合にはその中間結合ロジックと終点ロジックの組み合わせを有効な組み合わせとして採用する。一方、プログラム分析装置１００は、充足可能でない場合にはその中間結合ロジックと終点ロジックの組み合わせを無効な組み合わせであるとして採用しない。
【０１１８】
プログラム分析装置１００は、有効な組み合わせについて、中間結合ロジックのパス出力を、終点ロジックのパス出力に用いられているシンボルに代入して、結合したロジックのパス出力を算出する。プログラム分析装置１００は、有効な組み合わせについて算出したパス条件とパス出力とを、ロジックテーブル１２８に登録する。
【０１１９】
プログラム１２１の場合、プログラム分析装置１００は、中間結合ロジックのパス出力の「変数１」の値を、終点ロジックのシンボル「変数１＿Ｐｅｒｆｏｒｍ＿２３＿セクションＢ＿１」に代入することになる。プログラム分析装置１００は、中間結合ロジック＃１と終点ロジック＃１ｘを選択し、「変数１＿Ａ＋１が２０より大きい」かつ「変数１＿Ａ＋１＋２が３０より小さい」というパス条件を算出する。このパス条件は充足可能であるため、プログラム分析装置１００は、中間結合ロジック＃１と終点ロジック＃１ｘの組み合わせをロジック＃１として採用する。ロジック＃１のパス出力は、「変数１＝変数１＿Ａ＋１＋２＋３」である。
【０１２０】
また、プログラム分析装置１００は、中間結合ロジック＃１と終点ロジック＃２ｘを選択し、「変数１＿Ａ＋１が２０より大きい」かつ「変数１＿Ａ＋１＋２が３０以上」というパス条件を算出する。これは、「変数１＿Ａ＋１＋２が３０以上」と同等である。このパス条件は充足可能であるため、プログラム分析装置１００は、中間結合ロジック＃１と終点ロジック＃２ｘの組み合わせをロジック＃２として採用する。ロジック＃２のパス出力は、「変数１＝変数１＿Ａ＋１＋２−３」である。
【０１２１】
また、プログラム分析装置１００は、中間結合ロジック＃２と終点ロジック＃１ｘを選択し、「変数１＿Ａが１０より大きい」かつ「変数１＿Ａ＋１が２０以下」かつ「変数１＿Ａ＋１−２が３０より小さい」というパス条件を算出する。これは、「変数１＿Ａが１０より大きい」と同等である。このパス条件は充足可能であるため、プログラム分析装置１００は、中間結合ロジック＃２と終点ロジック＃１ｘの組み合わせをロジック＃３として採用する。ロジック＃３のパス出力は、「変数１＝変数１＿Ａ＋１−２＋３」である。
【０１２２】
また、プログラム分析装置１００は、中間結合ロジック＃２と終点ロジック＃２ｘを選択し、「変数１＿Ａが１０より大きい」かつ「変数１＿Ａ＋１が２０以下」かつ「変数１＿Ａ＋１−２が３０以上」というパス条件を算出する。このパス条件は充足可能でないため、プログラム分析装置１００は、中間結合ロジック＃２と終点ロジック＃２ｘの組み合わせを採用しない。
【０１２３】
また、プログラム分析装置１００は、中間結合ロジック＃３と終点ロジック＃１ｘを選択し、「変数１＿Ａが１０以下」かつ「変数１＿Ａ−１−２が３０より小さい」というパス条件を算出する。これは、「変数１＿Ａが１０以下」と同等である。このパス条件は充足可能であるため、プログラム分析装置１００は、中間結合ロジック＃３と終点ロジック＃１ｘの組み合わせをロジック＃４として採用する。ロジック＃４のパス出力は、「変数１＝変数１＿Ａ−１−２＋３」である。
【０１２４】
また、プログラム分析装置１００は、中間結合ロジック＃３と終点ロジック＃２ｘを選択し、「変数１＿Ａが１０以下」かつ「変数１＿Ａ−１−２が３０以上」というパス条件を算出する。このパス条件は充足可能でないため、プログラム分析装置１００は、中間結合ロジック＃３と終点ロジック＃２ｘの組み合わせを採用しない。
【０１２５】
これにより、４つのロジックが登録されたロジックテーブル１２８が生成される。ロジックテーブル１２８は、セクションＡとセクションＢとに跨がる実行パスを直接検出した場合に生成される図６のロジックテーブル１２９と同等である。このように、プログラム分析装置１００は、シンボリック実行の計算量を削減しても、分析範囲のモジュールのロジックを正しく抽出することができる。なお、プログラム１２１の例の場合、シンボリック実行の対象となる実行パスの候補が、２2×２1＝８つから２2＋２1＝６つに削減される。計算量の削減効果は、条件分岐文が多いほど大きくなる。
【０１２６】
図１４は、プログラムの第３の例を示す図である。
プログラム１４６は、プログラム１２１と同様にセクションＡおよびセクションＢを含む。ただし、プログラム１４６では、セクションＢに条件分岐文が追加されている。追加された命令文では、「変数１」の値が２５より小さい場合に「変数１」の値を４増加させ、「変数１」の値が２５以上である場合に「変数１」の値を４減少させる。
【０１２７】
セクションＡとセクションＢに跨がる実行パスをシンボリック実行によって直接検出する場合、探索する実行パスの候補は２2×２2＝１６個になる。一方、セクションＡのシンボリック実行とセクションＢのシンボリック実行を分割して事後的に部分ロジックを結合する方法によれば、探索する実行パスの候補は２2＋２2＝８個になる。この場合、探索する実行パスの候補の数が２分の１に削減される。
【０１２８】
次に、プログラム分析装置１００の機能および処理手順について説明する。
図１５は、プログラム分析装置の機能例を示すブロック図である。
プログラム分析装置１００は、記憶部１２０を有する。記憶部１２０は、例えば、ＲＡＭ１０２またはＨＤＤ１０３に確保した記憶領域を用いて実装される。記憶部１２０は、プログラム１２１、更新変数テーブル１２２、シンボル割り当てテーブル１２３、途中点ロジックテーブル１２４、呼び出し先ロジックテーブル１２５、終点ロジックテーブル１２６、中間結合ロジックテーブル１２７およびロジックテーブル１２８を記憶する。
【０１２９】
また、プログラム分析装置１００は、更新変数抽出部１３１、更新値割り当て部１３２、シンボリック実行部１３３、部分ロジック収集部１３４、ロジック簡約化部１３５、部分ロジック結合部１３６および分析結果表示部１３７を有する。更新変数抽出部１３１、更新値割り当て部１３２、シンボリック実行部１３３、部分ロジック収集部１３４、ロジック簡約化部１３５、部分ロジック結合部１３６および分析結果表示部１３７は、例えば、プロセッサ１０１が実行するプログラムモジュールを用いて実装される。
【０１３０】
更新変数抽出部１３１は、分析するプログラム１２１およびプログラム１２１の中の分析範囲が指定されると、分析範囲から、分析範囲外のモジュールを呼び出す呼び出し文であって作用の記載がないもの（例えば、ＰＥＲＦＯＲＭ文）を検索する。更新変数抽出部１３１は、検索した呼び出し文の呼び出し先モジュールから、当該呼び出し先モジュールで値が更新される可能性のある更新変数を検索する。これにより、更新変数抽出部１３１は、更新変数テーブル１２２を生成して記憶部１２０に格納する。
【０１３１】
更新値割り当て部１３２は、シンボル割り当てテーブル１２３を生成して記憶部１２０に格納する。更新値割り当て部１３２は、シンボリック実行部１３３によるシンボリック実行が、分析範囲外のモジュールを呼び出す呼び出し文であって作用の記載がないものに到達したことを検出する。すると、更新値割り当て部１３２は、呼び出し先モジュールに対応する更新変数を更新変数テーブル１２２から検索し、検索された更新変数それぞれに対して新たなシンボルを割り当てる。更新値割り当て部１３２は、割り当てたシンボルをシンボル割り当てテーブル１２３に登録し、シンボリック実行部１３３に通知する。
【０１３２】
シンボリック実行部１３３は、更新変数抽出部１３１が更新変数を抽出した後、シンボリック実行を開始する。シンボリック実行の対象は、プログラム１２１の中の指定された分析範囲である。ただし、シンボリック実行部１３３は、呼び出し文が存在する場合、呼び出し先モジュールについて呼び出し元モジュールとは独立にシンボリック実行を行う。シンボリック実行部１３３は、各モジュールの先頭において当該モジュールの入力に対してシンボルを割り当てる。また、シンボリック実行部１３３は、分析範囲外のモジュールを呼び出す呼び出し文であって作用の記載がないものに到達すると、呼び出し先モジュールをスタブ化し、更新値割り当て部１３２から更新変数のシンボルを取得する。呼び出し文以降は、取得したシンボルを用いてシンボリック実行を続ける。
【０１３３】
部分ロジック収集部１３４は、途中点ロジックテーブル１２４、呼び出し先ロジックテーブル１２５および終点ロジックテーブル１２６を生成して記憶部１２０に格納する。部分ロジック収集部１３４は、シンボリック実行部１３３によるシンボリック実行の過程で各種のロジック情報を収集する。部分ロジック収集部１３４は、シンボリック実行が呼び出し文に到達すると、呼び出し文の直前の途中点ロジックを取得して途中点ロジックテーブル１２４に登録する。また、部分ロジック収集部１３４は、シンボリック実行が呼び出し先モジュールの終点に到達すると、その時点の呼び出し先ロジックを取得して呼び出し先ロジックテーブル１２５に登録する。また、部分ロジック収集部１３４は、シンボリック実行が呼び出し元モジュールの終点に到達すると、その時点の呼び出し元ロジックを取得して終点ロジックテーブル１２６に登録する。
【０１３４】
ロジック簡約化部１３５は、シンボリック実行の終了後、途中点ロジックテーブル１２４に登録された途中点ロジックを簡約化する。また、ロジック簡約化部１３５は、シンボリック実行の終了後、呼び出し先ロジックテーブル１２５に登録された呼び出し先ロジックを簡約化する。また、ロジック簡約化部１３５は、シンボリック実行の終了後、終点ロジックテーブル１２６に登録された終点ロジックを簡約化する。
【０１３５】
部分ロジック結合部１３６は、中間結合ロジックテーブル１２７とロジックテーブル１２８を生成して記憶部１２０に格納する。部分ロジック結合部１３６は、途中点ロジックテーブル１２４に登録された途中点ロジックと呼び出し先ロジックテーブル１２５に登録された呼び出し先ロジックとを結合し、中間結合ロジックを中間結合ロジックテーブル１２７に登録する。途中点ロジックと呼び出し先ロジックとの結合では、結合後のパス条件が充足可能であるもののみが採用される。部分ロジック結合部１３６は、中間結合ロジックと終点ロジックテーブル１２６に登録された終点ロジックとを結合し、結合したロジックをロジックテーブル１２８に登録する。中間結合ロジックと終点ロジックとの結合では、結合後のパス条件が縦走可能であるもののみが採用される。
【０１３６】
分析結果表示部１３７は、生成されたロジックテーブル１２８をディスプレイ１１１に表示する。ただし、プログラム分析装置１００は、生成されたロジックテーブル１２８を他の装置に送信してもよい。また、プログラム分析装置１００は、ロジックテーブル１２８の内容を読み上げる音声をスピーカから再生する、ロジックテーブル１２８を印刷デバイスに出力するなど、他の方法でロジックテーブル１２８を出力してもよい。
【０１３７】
図１６は、プログラム分析の手順例を示すフローチャートである。
（Ｓ１）プログラム分析装置１００は、分析対象のプログラム１２１の指定およびプログラム１２１の中の分析範囲とする１以上のモジュールの指定を取得する。これらの指定は、例えば、入力デバイス１１２を用いてユーザから入力される。
【０１３８】
（Ｓ２）更新変数抽出部１３１は、分析範囲の実行時に呼び出される可能性のある分析範囲外のモジュールの更新変数を抽出する。更新変数抽出の詳細は後述する。
（Ｓ３）シンボリック実行部１３３は、分析範囲のモジュールと呼び出し先である分析範囲外のモジュールとについて、別個にシンボリック実行を行う。部分ロジック収集部１３４は、シンボリック実行が行われている間、途中点ロジックと呼び出し先ロジックと終点ロジックとを収集する。シンボリック実行の詳細は後述する。
【０１３９】
（Ｓ４）ロジック簡約化部１３５は、収集された途中点ロジックと呼び出し先ロジックと終点ロジックとをそれぞれ簡約化する。ロジック簡約化の詳細は後述する。
（Ｓ５）部分ロジック結合部１３６は、簡約化後の途中点ロジックと呼び出し先ロジックとを結合する。ロジック結合の詳細は後述する。
【０１４０】
（Ｓ６）部分ロジック結合部１３６は、ステップＳ５で生成した中間結合ロジックと終点ロジックとを結合する。ロジック結合のアルゴリズムはステップＳ５と同様である。
（Ｓ７）分析結果表示部１３７は、ステップＳ６によって結合されたロジックを示すロジックテーブル１２８をディスプレイ１１１に表示させる。
【０１４１】
図１７は、更新変数抽出の手順例を示すフローチャートである。
更新変数抽出は、前述のステップＳ２で実行される。
（Ｓ１０）更新変数抽出部１３１は、分析対象のプログラム１２１の指定およびプログラム１２１の中の分析範囲とする１以上のモジュールの指定を取得する。更新変数抽出部１３１は、指定された分析範囲のモジュールに着目する。
【０１４２】
（Ｓ１１）更新変数抽出部１３１は、着目するモジュールから、分析範囲外のモジュールを呼び出す呼び出し文であって作用の記載がないものを検索する。
（Ｓ１２）更新変数抽出部１３１は、ステップＳ１１で該当する呼び出し文が検索されたか判断する。該当する呼び出し文がある場合はステップＳ１３に処理が進み、該当する呼び出し文がない場合はステップＳ１３〜Ｓ１６の処理をスキップする。
【０１４３】
（Ｓ１３）更新変数抽出部１３１は、呼び出し先モジュールを取得する。
（Ｓ１４）更新変数抽出部１３１は、呼び出し先モジュールから、変数の値を更新する変数更新文を検索する。値が更新される変数（更新変数）は、例えば、代入文の左辺に記載された変数や、ＭＯＶＥ文の第２引数として記載された変数などである。
【０１４４】
（Ｓ１５）更新変数抽出部１３１は、呼び出し先モジュールのモジュール名とステップＳ１４で検索された更新変数の変数名とを対応付けて、更新変数テーブル１２２に登録する。ただし、呼び出しが階層的に行われる場合にはモジュール名として、分析範囲から呼び出される１段階目のモジュールのモジュール名を用いる。
【０１４５】
（Ｓ１６）更新変数抽出部１３１は、ステップＳ１３で取得した呼び出し先モジュールに着目し、当該呼び出し先モジュールについてステップＳ１１〜Ｓ１６の処理を再帰的に実行する。呼び出し先モジュールが更に他のモジュールを呼び出す呼び出し文（サブ呼び出し文）を含む場合、再帰的に更新変数が探索される。
【０１４６】
図１８は、シンボリック実行の手順例を示すフローチャートである。
シンボリック実行は、前述のステップＳ３で実行される。
（Ｓ２０）シンボリック実行部１３３は、分析対象のプログラム１２１の指定およびプログラム１２１の中の分析範囲とする１以上のモジュールの指定を取得する。シンボリック実行部１３３は、指定された分析範囲のモジュールに着目する。
【０１４７】
（Ｓ２１）シンボリック実行部１３３は、着目するモジュールの入力が格納される入力変数に独立なシンボルを割り当てる。例えば、シンボリック実行部１３３は、図５のセクションＡの「変数１」に対してシンボル「変数１＿Ａ」を割り当てる。
【０１４８】
（Ｓ２２）シンボリック実行部１３３は、プログラム１２１の処理順序に従い、次に実行されるべき命令文をプログラム１２１から１つ取得する。
（Ｓ２３）シンボリック実行部１３３は、ステップＳ２２で終了文以外の命令文を取得したか判断する。終了文以外の命令文を取得した場合、ステップＳ２４に処理が進む。終了文を取得したか該当する命令文が存在しない場合、ステップＳ２９に処理が進む。
【０１４９】
（Ｓ２４）シンボリック実行部１３３は、ステップＳ２２で取得した命令文が、分析範囲外のモジュールを呼び出す呼び出し文であって作用の記載がないものであるか判断する。図５のＰＥＲＦＯＲＭ文のように、呼び出し先モジュールによって更新される更新変数が明記されていない呼び出し文は、作用の記載がない呼び出し文である。取得した命令文が該当する呼び出し文である場合はステップＳ２５に処理が進み、取得した命令文がそれ以外のものである場合はステップＳ３１に処理が進む。
【０１５０】
（Ｓ２５）部分ロジック収集部１３４は、呼び出し文の直前におけるパス条件とパス出力を途中点ロジックテーブル１２４に登録する。パス条件は、着目するモジュールの先頭から呼び出し文の直前までに選択した分岐方向の条件を累積したものである。パス出力は、呼び出し文の直前における変数の値である。パス条件やパス出力には、ステップＳ２１で割り当てられたシンボルが用いられることがある。
【０１５１】
（Ｓ２６）シンボリック実行部１３３は、呼び出し文が示す呼び出し先モジュールを分析済みであるか判断する。呼び出し先モジュールを分析済みである場合はステップＳ２８に処理が進み、まだ分析していない場合はステップＳ２７に処理が進む。
【０１５２】
（Ｓ２７）シンボリック実行部１３３は、呼び出し先モジュールに着目し、ステップＳ２１〜Ｓ３０の処理を再帰的に実行する。このとき、シンボリック実行部１３３は、呼び出し元モジュールの分析途中の情報を退避し、呼び出し元モジュールとは独立に呼び出し先モジュールについてシンボリック実行を行う。呼び出し先モジュールのシンボリック実行が終了すると、シンボリック実行部１３３は、退避しておいた分析途中の情報を用いて呼び出し元モジュールのシンボリック実行を続ける。なお、図１８のフローチャートでは、呼び出し元モジュールのシンボリック実行を中断して呼び出し先モジュールのシンボリック実行を行うこととした。しかし、呼び出し元モジュールのシンボリック実行が終わってから、呼び出し先モジュールのシンボリック実行を開始するようにしてもよい。
【０１５３】
（Ｓ２８）更新値割り当て部１３２は、呼び出し先モジュールに対応する更新変数を、更新変数テーブル１２２から検索する。更新値割り当て部１３２は、検索した更新変数に独立のシンボルを割り当て、割り当てたシンボルをシンボル割り当てテーブル１２３に登録する。また、更新値割り当て部１３２は、割り当てたシンボルをシンボリック実行部１３３に通知する。シンボリック実行部１３３は、呼び出し文の直前において更新変数の値を保持している場合、その値を破棄して更新値割り当て部１３２から通知されたシンボルを保存する。すなわち、シンボリック実行部１３３は、更新変数の値が通知されたシンボルによって上書きされたものとして取り扱う。そして、ステップＳ２２に処理が進む。
【０１５４】
（Ｓ２９）シンボリック実行部１３３は、実行パスが終点に到達したと判断する。部分ロジック収集部１３４は、その時点のパス条件とパス出力を終点ロジックテーブル１２６に登録する。ただし、呼び出し先モジュールについてのシンボリック実行である場合、部分ロジック収集部１３４は、その時点のパス条件とパス出力を呼び出し先ロジックテーブル１２５に登録する。パス条件は、着目するモジュールの先頭から終点までに選択した分岐方向の条件を累積したものである。パス出力は、着目するモジュールの終点における変数の値である。パス条件やパス出力には、ステップＳ２１で割り当てられたシンボルや、ステップＳ２８で割り当てられたシンボルが用いられることがある。
【０１５５】
（Ｓ３０）シンボリック実行部１３３は、条件分岐文によって分割された実行パスであって、未選択の実行パスが残っているか判断する。未選択の実行パスがある場合、シンボリック実行部１３３は、１つ前の分割点までバックトラックし、保存しておいたその分割点におけるパス条件およびパス出力を取得する。シンボリック実行部１３３は、未選択の分岐方向を選択し、取得したパス条件およびパス出力を用いてその実行パスについてシンボリック実行を続ける。そして、ステップＳ２２に処理が進む。一方、未選択の実行パスがない場合、着目するモジュールのシンボリック実行が終了する。
【０１５６】
図１９は、シンボリック実行の手順例を示すフローチャート（続き）である。
（Ｓ３１）シンボリック実行部１３３は、ステップＳ２２で取得した命令文が、変数の値を更新する変数更新文であるか判断する。変数更新文は、例えば、左辺と右辺を等号で結合した代入文やＭＯＶＥ文などである。取得した命令文が変数更新文である場合はステップＳ３２に処理が進み、それ以外である場合はステップＳ３３に処理が進む。
【０１５７】
（Ｓ３２）シンボリック実行部１３３は、変数更新文に従い変数の値を更新する。変数の値はシンボルを含む式で表されることもある。そして、ステップＳ２２に処理が進む。
（Ｓ３３）シンボリック実行部１３３は、ステップＳ２２で取得した命令文が、条件分岐文であるか判断する。取得した命令文が条件分岐文である場合はステップＳ３４に処理が進み、それ以外である場合はステップＳ３７に処理が進む。
【０１５８】
（Ｓ３４）シンボリック実行部１３３は、条件分岐文に記載された分岐条件とその時点の変数の値とその時点のパス条件とに基づいて、ＹＥＳ方向とＮＯ方向の２つの分岐方向それぞれの充足可能性を判定する。変数の値がシンボルを含む式である場合、２つの分岐方向の両方が充足可能であると判定されることもある。
【０１５９】
（Ｓ３５）シンボリック実行部１３３は、２つの分岐方向が共に充足可能であるか判断する。２つの分岐方向が共に充足可能である場合はステップＳ３６に処理が進み、一方の分岐方向のみ充足可能である場合はステップＳ３７に処理が進む。
【０１６０】
（Ｓ３６）シンボリック実行部１３３は、実行パスを分割する。シンボリック実行部１３３は、２つの分岐方向の何れか一方（例えば、ＹＥＳ方向）を選択して、現在の実行パスの進行方向とする。また、シンボリック実行部１３３は、その時点のパス条件とパス出力を退避しておく。選択しなかった分岐方向に相当する分割された実行パスは、未選択の実行パスとしておく。そして、ステップＳ２２に処理が進む。
【０１６１】
（Ｓ３７）シンボリック実行部１３３は、ステップＳ２２で取得した命令文に応じた処理を行う。ステップＳ３５で一方の分岐方向のみ充足可能と判断された場合、シンボリック実行部１３３は、条件分岐文に従って充足可能な分岐方向を選択することになる。このとき、実行パスは分割されない。そして、ステップＳ２２に処理が進む。
【０１６２】
図２０は、ロジック簡約化の手順例を示すフローチャートである。
ロジック簡約化は前述のステップＳ４で実行される。
（Ｓ４０）ロジック簡約化部１３５は、途中点ロジックテーブル１２４、呼び出し先ロジックテーブル１２５および終点ロジックテーブル１２６のうち１つを選択する。
【０１６３】
（Ｓ４１）ロジック簡約化部１３５は、ステップＳ４０で選択したロジックテーブルから、パス出力が同じでパス条件が異なる複数のロジックを検索する。
（Ｓ４２）ロジック簡約化部１３５は、ステップＳ４１に該当する複数のロジックが検索された場合、検索された複数のロジックのパス条件をＯＲで連結することで、検索された複数のロジックを１つのロジックに統合する。
【０１６４】
（Ｓ４３）ロジック簡約化部１３５は、ステップＳ４２で統合した後の各ロジックのパス条件を、冗長性を削減することで簡約化する。
（Ｓ４４）ロジック簡約化部１３５は、ステップＳ４３で簡約化した後のロジックのうち、パス条件が同じでパス出力が異なる複数のロジックを検索する。
【０１６５】
（Ｓ４５）ロジック簡約化部１３５は、ステップＳ４４に該当する複数のロジックが検索された場合、検索された複数のロジックのパス出力をＡＮＤで連結することで、検索された複数のロジックを１つのロジックに統合する。
【０１６６】
（Ｓ４６）ロジック簡約化部１３５は、ステップＳ４０において、途中点ロジックテーブル１２４、呼び出し先ロジックテーブル１２５および終点ロジックテーブル１２６の全てを選択したか判断する。未選択のロジックテーブルがある場合はステップＳ４０に処理が進み、３つのロジックテーブルの全てを選択した場合はロジック簡約化が終了する。
【０１６７】
図２１は、ロジック結合の手順例を示すフローチャートである。
ロジック結合は、前述のステップＳ５およびステップＳ６で実行される。ステップＳ５とステップＳ６では、共通のロジック結合アルゴリズムを使用できる。
【０１６８】
（Ｓ５０）部分ロジック結合部１３６は、結合するロジックテーブルＴ１とロジックテーブルＴ２を取得する。ステップＳ５では、ロジックテーブルＴ１は途中点ロジックテーブル１２４であり、ロジックテーブルＴ２は呼び出し先ロジックテーブル１２５である。ステップＳ６では、ロジックテーブルＴ１は中間結合ロジックテーブル１２７であり、ロジックテーブルＴ２は終点ロジックテーブル１２６である。
【０１６９】
（Ｓ５１）部分ロジック結合部１３６は、ロジックテーブルＴ１からレコードＲ１を選択する。レコードＲ１は、ロジックテーブルＴ１の中の１つのロジックを表す。
（Ｓ５２）部分ロジック結合部１３６は、ロジックテーブルＴ２からレコードＲ２を選択する。レコードＲ２は、ロジックテーブルＴ２の中の１つのロジックを表す。
【０１７０】
（Ｓ５３）部分ロジック結合部１３６は、レコードＲ１のパス出力をレコードＲ２のパス条件に用いられているシンボルに代入する。部分ロジック結合部１３６は、代入結果とレコードＲ１のパス条件とをＡＮＤで連結し、結合後のパス条件を算出する。
【０１７１】
（Ｓ５４）部分ロジック結合部１３６は、ステップＳ５３で算出した結合後のパス条件の充足可能性を判定する。結合後のパス条件が充足可能である場合はステップＳ５５に処理が進み、充足可能でない場合はステップＳ５７に処理が進む。
【０１７２】
（Ｓ５５）部分ロジック結合部１３６は、レコードＲ１のパス出力をレコードＲ２のパス出力に用いられているシンボルに代入し、結合後のパス出力を算出する。
（Ｓ５６）部分ロジック結合部１３６は、ステップＳ５３で算出したパス条件とステップＳ５５で算出したパス出力を結合結果のロジックテーブルに登録する。ステップＳ５では、結合結果のロジックテーブルは中間結合ロジックテーブル１２７である。ステップＳ６では、結合結果のロジックテーブルはロジックテーブル１２８である。
【０１７３】
（Ｓ５７）部分ロジック結合部１３６は、ロジックテーブルＴ２に、ステップＳ５２で未選択のレコードが存在するか判断する。未選択のレコードがある場合はステップＳ５２に処理が進み、全てのレコードを選択した場合はステップＳ５８に処理が進む。
【０１７４】
（Ｓ５８）部分ロジック結合部１３６は、ロジックテーブルＴ１に、ステップＳ５１で未選択のレコードが存在するか判断する。未選択のレコードがある場合はステップＳ５１に処理が進み、全てのレコードを選択した場合はロジック結合が終了する。
【０１７５】
第２の実施の形態のプログラム分析装置１００によれば、呼び出し元モジュールのシンボリック実行と呼び出し先モジュールのシンボリック実行とが独立に行われる。呼び出し元モジュールのシンボリック実行では、呼び出し文の直前におけるパス条件とパス出力が保存されると共に、呼び出し文はスキップされ、呼び出し先モジュールで更新される可能性のある更新変数に新たなシンボルが割り当てられる。そして、呼び出し文の直前におけるロジック情報と呼び出し元モジュールの終点におけるロジック情報と呼び出し先モジュールの終点におけるロジック情報とが結合され、実行パスが再現される。
【０１７６】
これにより、複数のモジュールに跨がる実行パスを分析する際のパス爆発を抑制し、シンボリック実行の計算量を削減できる。よって、実行パスを効率的に分析することができる。また、呼び出し先モジュールの処理内容を無視しているわけではないため、再現された実行パスは、呼び出し元モジュールの入力と出力の関係を正しく表している。
【符号の説明】
【０１７７】
１０  プログラム分析装置
１１  記憶部
１２  演算部
２０  プログラム
２１，２６  モジュール
２２  呼び出し命令
２３ａ，２３ｂ  第１の実行パス
２４  第１の情報
２５  第２の情報
２７ａ，２７ｂ  第２の実行パス
２８  第３の情報
３１ａ，３１ｂ，３１ｃ，３１ｄ  合成実行パス
３２  パス情報
ｃ１，ｃ２，ｃ３  シンボル
【図１】
0006659955.tif 000002
【図２】
0006659955.tif 000003
【図３】
0006659955.tif 000004
【図４】
0006659955.tif 000005
【図５】
0006659955.tif 000006
【図６】
0006659955.tif 000007
【図７】
0006659955.tif 000008
【図８】
0006659955.tif 000009
【図９】
0006659955.tif 000010
【図１０】
0006659955.tif 000011
【図１１】
0006659955.tif 000012
【図１２】
0006659955.tif 000013
【図１３】
0006659955.tif 000014
【図１４】
0006659955.tif 000015
【図１５】
0006659955.tif 000016
【図１６】
0006659955.tif 000017
【図１７】
0006659955.tif 000018
【図１８】
0006659955.tif 000019
【図１９】
0006659955.tif 000020
【図２０】
0006659955.tif 000021
【図２１】
0006659955.tif 000022