(57)【特許請求の範囲】
【請求項１】
変更前ソースコードに含まれる関数と変更後ソースコードに含まれる関数との組である対応組毎に、対応組に含まれる関数同士が等価であるか等価性検証によって判定する等価性検証部と、
不等価である対応組毎に、対応組が、不等価関数が呼び出される不等価パスと非不等価関数が呼び出される非不等価パスとの両方が含まれる関数を含んだ部分検証組であるか判定する部分検証判定部と、
部分検証組毎に、前記不等価パスを除外して前記等価性検証を行うことによって、部分検証組に含まれる関数同士が部分等価であるか判定する部分検証部と
を備える等価性検証装置。
【請求項２】
前記等価性検証装置は、前記変更前ソースコードと前記変更後ソースコードとに対してそれぞれのソースコードの中にある分岐箇所毎に分岐箇所識別子を生成する識別子設定部を備え、
前記部分検証判定部は、前記変更前ソースコードと前記変更後ソースコードとの少なくとも一方において前記不等価関数が呼び出される箇所に対応する分岐箇所識別子と前記不等価関数ではない関数が呼び出される箇所に対応する分岐箇所識別子とが一致しない場合に、前記対応組が前記部分検証組であると判定する
請求項１に記載の等価性検証装置。
【請求項３】
前記等価性検証部は、前記等価性検証の入力となる検証ファイルを生成し、前記検証ファイルを用いて前記等価性検証を行い、
前記部分検証部は、前記対応組に含まれる関数の中の不等価パスである第１不等価パスを除外するための第１除外制御文を前記検証ファイルに追加し、前記第１除外制御文が追加された後の検証ファイルを用いて前記等価性検証を行う
請求項１に記載の等価性検証装置。
【請求項４】
前記等価性検証装置は、前記変更前ソースコードと前記変更後ソースコードとに対してそれぞれのソースコードの中にある分岐箇所毎に分岐箇所識別子の値を更新する更新文を追加する識別子設定部を備え、
前記等価性検証部は、前記対応組に含まれる関数を呼び出す呼び出し文を含んだファイルを前記検証ファイルとして生成し、
前記部分検証部は、前記不等価関数が呼び出される箇所に対応する分岐箇所識別子の値が更新前の値と一致するか判定する文を前記呼び出し文の後に前記第１除外制御文として追加し、前記更新文が追加された後の変更前ソースコードと前記更新文が追加された後の変更後ソースコードと前記第１除外制御文が追加された後の検証ファイルとを用いて前記等価性検証を行う
請求項３に記載の等価性検証装置。
【請求項５】
前記等価性検証部は、前記等価性検証の入力となる検証ファイルを生成し、前記検証ファイルを用いて前記等価性検証を行い、
前記部分検証部は、前記対応組に含まれる関数の中の不等価パスである第１不等価パスを除外するための第１除外制御文を前記検証ファイルに追加し、前記対応組が前記部分検証組であり且つ前記部分検証組に含まれる関数が部分等価関数を呼び出す関数である場合、前記部分等価関数の中の不等価パスである第２不等価パスを除外するための第２除外制御文を前記検証ファイルに追加し、前記検証ファイルを用いて前記等価性検証を行う
請求項１に記載の等価性検証装置。
【請求項６】
前記等価性検証装置は、前記変更前ソースコードと前記変更後ソースコードとに対してそれぞれのソースコードの中にある分岐箇所毎に分岐箇所識別子の値を更新する更新文を追加する識別子設定部を備え、
前記等価性検証部は、前記対応組に含まれる関数を呼び出す呼び出し文を含んだファイルを前記検証ファイルとして生成し、
前記部分検証部は、前記第１不等価パスで呼び出される不等価関数である第１不等価関数が呼び出される箇所に対応する第１分岐箇所識別子の値が更新前の値と一致するか判定する文を前記呼び出し文の後に前記第１除外制御文として追加し、前記第２不等価パスで呼び出される不等価関数である第２不等価関数が呼び出される箇所に対応する第２分岐箇所識別子の値が更新前の値と一致するか判定する文を前記呼び出し文の後に前記第２除外制御文として追加し、前記変更前ソースコードと前記変更後ソースコードと前記検証ファイルとを用いて前記等価性検証を行う
請求項５に記載の等価性検証装置。
【請求項７】
始点関数識別子と終点関数識別子とを受け付ける受付部と、
前記始点関数識別子で識別される始点関数から前記終点関数識別子で識別される終点関数までの呼び出しパスが不等価パスであるか判定するパス検証部を備える
請求項６に記載の等価性検証装置。
【請求項８】
前記パス検証部は、前記呼び出しパスに含まれる呼び出し先関数毎に呼び出し先関数が呼び出される箇所に対応する分岐箇所識別子である第３分岐箇所識別子を抽出し、少なくともいずれかの第３分岐箇所識別子が前記始点関数の前記第１分岐箇所識別子と前記始点関数の前記第２分岐箇所識別子とのいずれかと一致するか判定し、少なくともいずれかの第３分岐箇所識別子が前記始点関数の前記第１分岐箇所識別子と前記始点関数の前記第２分岐箇所識別子とのいずれかと一致する場合に前記呼び出しパスが不等価パスであると判定する
請求項７に記載の等価性検証装置。
【請求項９】
変更前ソースコードに含まれる関数と変更後ソースコードに含まれる関数との組である対応組毎に、対応組に含まれる関数同士が等価であるか等価性検証によって判定する等価性検証処理と、
不等価である対応組毎に、対応組が、不等価関数が呼び出される不等価パスと非不等価関数が呼び出される非不等価パスとの両方が含まれる関数を含んだ部分検証組であるか判定する部分検証判定処理と、
部分検証組毎に、前記不等価パスを除外して前記等価性検証を行うことによって、部分検証組に含まれる関数同士が部分等価であるか判定する部分検証処理と
をコンピュータに実行させるための等価性検証プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、関数同士の等価性を検証する技術に関するものである。
【背景技術】
【０００２】
ソフトウェアの多機能化および電子化によって、ソフトウェアは複雑化および大規模化の一途をたどっている。このような状況下において、ソフトウェア開発の生産性の向上を図る必要がある。
例えば、ソフトウェアの差分派生開発において、品質の維持および開発工数の削減を実現するソフトウェア開発ツールが適用される。【０００３】
ソフトウェアの差分派生開発において、リファクタリングと呼ばれる手法がある。リファクタリングは、ソフトウェアの論理的な演算内容を変更せずにソフトウェアの内部構成を変えることによって、ソフトウェアの品質を改善するための手法である。
リファクタリングでは、ソースコードの変更が伴う。そのため、ソースコードの変更により不具合が発生し、論理的な演算内容が意図せずして変更される可能性がある。
そのため、ソフトウェアの差分派生開発において、ソフトウェアの変更前後の検証が要求される。【０００４】
非特許文献１では、レガシーコードとＳｉｍｕｌｉｎｋとを用いて生成されたソースコードを対象として、「等価性検証」に関する手法が開示されている。
「等価」は、２つのソースコードの論理的な演算内容が一致すること、つまり同じ入力値に対して同じ出力値が得られることを意味する。
「等価性検証」は、２つのソースコードが等価であるか否かを検証することである。【０００５】
非特許文献１では、２つのソースコードに対して、ソースコードに含まれる関数の呼び出し関係を表現するためにコールグラフが生成される。そして、コールグラフが用いられて、関数名および呼出関係が一致している関数同士の関連付けと関数単位での等価性検証とが行われる。
等価性検証は末端の関数から順に行われる。等価の条件は、２つのソースコードが同じ入力値に対して実行された場合に２つのソースコードで同じ出力値が得られることである。等価性検証では、入力値に対する出力値が２つのソースコードで一致することが全ての入力値について網羅的に解析され、関数単位で等価性が判定される。【０００６】
特許文献１では、ソースコードにおいて分岐文からの分岐先のブロックに対して振る舞いを表すタグが埋め込まれる。そして、検証対象とする振る舞いが指定され、検証すべきブロックを通過するための変数（または式）の値の範囲がブロックに埋め込まれたタグと指定された振る舞いとに基づいて特定される。特定された値の範囲を検証範囲とすることで、特定の振る舞いに関連したソースコードのみを検証することができる。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２０１０−２０４９５４号公報
【非特許文献】
【０００８】
【非特許文献１】Ｒｕｐａｋ  Ｍａｊｕｍｄａｒ，  “Ｃｏｍｐｏｓｉｔｉｏｎａｌ  Ｅｑｕｉｖａｌｅｎｃｅ  Ｃｈｅｃｋｉｎｇ  ｆｏｒ  Ｍｏｄｅｌｓ  ａｎｄ  Ｃｏｄｅ  ｏｆ  Ｃｏｎｔｒｏｌ  Ｓｙｓｔｅｍｓ，”  ５２ｎｄ  ＩＥＥＥ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｄｅｃｉｓｉｏｎ  ａｎｄ  Ｃｏｎｔｒｏｌ，  Ｄｅｃｅｍｂｅｒ  ２０１３．
【発明の概要】
【発明が解決しようとする課題】
【０００９】
非特許文献１では、全ての入力値において入力値に対する出力値が一致することが条件となる。そのため、関数内で通過するパスによって等価性が異なる場合においても、関数が不等価であると判定される。したがって、関数が不等価であると判定された原因を解析するための範囲が広く、人手による不具合解析にかかる時間を削減することができない。
例えば、関数ＡＸと関数ＡＹとの等価性を判定する。特定条件が満たされる場合、関数ＡＸでは関数ＢＸが呼び出され、関数ＡＹでは関数ＢＸと等価な関数ＢＹが呼び出される。したがって、特定条件が満たされる場合に関しては、関数ＡＸと関数ＡＹとは等価である。特定条件が満たされない場合、関数ＡＸでは関数ＣＸが呼び出され、関数ＡＹでは関数ＣＸと等価でない関数ＢＹが呼び出される。したがって、特定条件が満たされない場合に関しては、関数ＡＸと関数ＡＹとは等価である。
非特許文献１では、特定条件が満たされる場合に等価であっても特定条件が満たされない場合に等価でなければ、不等価と判定される。したがって、関数ＡＸと関数ＡＹとは不等価と判定される。【００１０】
特許文献１では、変数が多数ある場合または式が複雑な場合、特定のブロックを通過するための値の範囲が一意に定まらないことがある。そのため、特許文献１の適用範囲は限定される。【００１１】
本発明は、関数同士が部分等価であるか判定できるようにすることを目的とする。
【課題を解決するための手段】
【００１２】
本発明の等価性検証装置は、
変更前ソースコードに含まれる関数と変更後ソースコードに含まれる関数との組である対応組毎に、対応組に含まれる関数同士が等価であるか等価性検証によって判定する等価性検証部と、
不等価である対応組毎に、対応組が、不等価関数が呼び出される不等価パスと非不等価関数が呼び出される非不等価パスとの両方が含まれる関数を含んだ部分検証組であるか判定する部分検証判定部と、
部分検証組毎に、前記不等価パスを除外して前記等価性検証を行うことによって、部分検証組に含まれる関数同士が部分等価であるか判定する部分検証部とを備える。
【発明の効果】
【００１３】
本発明によれば、関数同士が部分等価であるか判定することができる。
【図面の簡単な説明】
【００１４】
【図１】実施の形態１における等価性検証装置１００の構成図。
【図２】実施の形態１における等価性検証方法のフローチャート。
【図３】実施の形態１における変更前ソースコード２１０を示す図。
【図４】実施の形態１における変更後ソースコード２２０を示す図。
【図５】実施の形態１における変更前コールグラフ２３１を示す図。
【図６】実施の形態１における変更後コールグラフ２３２を示す図。
【図７】実施の形態１における関数対応表２３３を示す図。
【図８】実施の形態１における等価性判定表２４０を示す図。
【図９】実施の形態１における検証処理（Ｓ１４０）のフローチャート。
【図１０】実施の形態１における検証ファイル２５０を示す図。
【図１１】実施の形態１における等価性判定表２４０を示す図。
【図１２】実施の形態１における等価性判定表２４０を示す図。
【図１３】実施の形態１における変更前ソースコード２１０（ステップＳ１４３の前）を示す図。
【図１４】実施の形態１における変更前ソースコード２１０（ステップＳ１４３の後）を示す図。
【図１５】実施の形態１における変更後ソースコード２２０（ステップＳ１４３の前）を示す図。
【図１６】実施の形態１における変更後ソースコード２２０（ステップＳ１４３の後）を示す図。
【図１７】実施の形態１における識別子対応表２６０（ステップＳ１４４の前）を示す図。
【図１８】実施の形態１における識別子対応表２６０（ステップＳ１４４の後）を示す図。
【図１９】実施の形態１における部分等価検証（Ｓ２００）のフローチャート。
【図２０】実施の形態１における部分検証判定（Ｓ２１０）のフローチャート。
【図２１】実施の形態１における部分検証（Ｓ２２０）のフローチャート。
【図２２】実施の形態１における検証ファイル２５０（ステップＳ２２１の後）を示す図。
【図２３】実施の形態１における等価性判定表２４０（ステップＳ２３２の後）を示す図。
【図２４】実施の形態１における変更前ソースコード２１０（ステップＳ１４３の後）を示す図。
【図２５】実施の形態１における変更後ソースコード２２０（ステップＳ１４３の後）を示す図。
【図２６】実施の形態１における識別子対応表２６０（ステップＳ１４４の後）を示す図。
【図２７】実施の形態１における検証ファイル２５０（ステップＳ２２１の後）を示す図。
【図２８】実施の形態１における検証ファイル２５０（ステップＳ２２３の後）を示す図。
【図２９】実施の形態１における等価性判定表２４０（ステップＳ２３２の後）を示す図。
【図３０】実施の形態２における等価性検証装置１００の構成図。
【図３１】実施の形態２におけるパス検証方法のフローチャート。
【図３２】実施の形態２におけるコールグラフ図２７０を示す図。
【図３３】実施の形態２における第３分岐箇所識別子の抽出（Ｓ３１０）のフローチャート。
【図３４】実施の形態２におけるパス判定表２８０（ステップＳ３１０の後）を示す図。
【図３５】実施の形態２におけるパス判定表２８０（パス検証の後）を示す図。
【図３６】実施の形態における等価性検証装置１００のハードウェア構成図。
【発明を実施するための形態】
【００１５】
実施の形態および図面において、同じ要素および対応する要素には同じ符号を付している。同じ符号が付された要素の説明は適宜に省略または簡略化する。図中の矢印はデータの流れ又は処理の流れを主に示している。
【００１６】
実施の形態１．
関数同士が部分等価であるか判定するための形態について、図１から図２９に基づいて説明する。
【００１７】
＊＊＊構成の説明＊＊＊
図１に基づいて、等価性検証装置１００の構成を説明する。
等価性検証装置１００は、プロセッサ９０１とメモリ９０２と補助記憶装置９０３と入出力インタフェース９０４といったハードウェアを備えるコンピュータである。これらのハードウェアは、信号線を介して互いに接続されている。
【００１８】
プロセッサ９０１は、演算処理を行うＩＣ（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）であり、他のハードウェアを制御する。例えば、プロセッサ９０１は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、ＤＳＰ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｏｒ）、またはＧＰＵ（Ｇｒａｐｈｉｃｓ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）である。
メモリ９０２は揮発性の記憶装置である。メモリ９０２は、主記憶装置またはメインメモリとも呼ばれる。例えば、メモリ９０２はＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）である。メモリ９０２に記憶されたデータは必要に応じて補助記憶装置９０３に保存される。
補助記憶装置９０３は不揮発性の記憶装置である。例えば、補助記憶装置９０３は、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）、またはフラッシュメモリである。補助記憶装置９０３に記憶されたデータは必要に応じてメモリ９０２にロードされる。
【００１９】
入出力インタフェース９０４は入力装置および出力装置が接続されるポートである。例えば、入出力インタフェース９０４はＵＳＢ端子であり、入力装置はキーボードおよびマウスであり、出力装置はディスプレイである。ＵＳＢはＵｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓの略称である。
【００２０】
等価性検証装置１００は、コールグラフ生成部１１０と制御部１２０と等価性検証部１３０と識別子設定部１４０と部分検証判定部１５０と部分検証部１６０といったソフトウェア要素を備える。ソフトウェア要素はソフトウェアで実現される要素である。
【００２１】
補助記憶装置９０３には、コールグラフ生成部１１０と制御部１２０と等価性検証部１３０と識別子設定部１４０と部分検証判定部１５０と部分検証部１６０としてコンピュータを機能させるための等価性検証プログラムが記憶されている。等価性検証プログラムは、メモリ９０２にロードされて、プロセッサ９０１によって実行される。
さらに、補助記憶装置９０３にはＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）が記憶されている。ＯＳの少なくとも一部は、メモリ９０２にロードされて、プロセッサ９０１によって実行される。
つまり、プロセッサ９０１は、ＯＳを実行しながら、等価性検証プログラムを実行する。
等価性検証プログラムを実行して得られるデータは、メモリ９０２、補助記憶装置９０３、プロセッサ９０１内のレジスタまたはプロセッサ９０１内のキャッシュメモリといった記憶装置に記憶される。
【００２２】
メモリ９０２はデータを記憶する記憶部１９１として機能する。但し、他の記憶装置が、メモリ９０２の代わりに、又は、メモリ９０２と共に、記憶部１９１として機能してもよい。
入出力インタフェース９０４は、入力を受け付ける受付部１９２として機能する。さらに、入出力インタフェース９０４は、画像などを表示する表示部１９３として機能する。
【００２３】
等価性検証装置１００は、プロセッサ９０１を代替する複数のプロセッサを備えてもよい。複数のプロセッサは、プロセッサ９０１の役割を分担する。
【００２４】
等価性検証プログラムは、磁気ディスク、光ディスクまたはフラッシュメモリ等の不揮発性の記憶媒体にコンピュータ読み取り可能に記憶することができる。不揮発性の記憶媒体は、一時的でない有形の媒体である。
【００２５】
＊＊＊動作の説明＊＊＊
等価性検証装置１００の動作は等価性検証方法に相当する。また、等価性検証方法の手順は等価性検証プログラムの手順に相当する。
【００２６】
図２に基づいて、等価性検証方法を説明する。
ステップＳ１０１において、受付部１９２は、変更前ソースコードと変更後ソースコードとを受け付ける。記憶部１９１は、受け付けられた変更前ソースコードと変更後ソースコードとを記憶する。
変更前ソースコードは、変更前のソフトウェアにおけるソースコードである。例えば、変更前ソースコードは従来作成したソースコードである。
変更後ソースコードは、変更後のソフトウェアにおけるソースコードである。例えば、変更後ソースコードは、変更前ソースコードを基にリファクタリングを実施することによって得られたソースコードである。
【００２７】
図３に、変更前ソースコード２１０を示す。変更前ソースコード２１０は、変更前ソースコードの具体例である。
変更前ソースコード２１０は、６つの関数（Ｆｕｎｃ＿Ｆ＿ｘ、Ｆｕｎｃ＿Ｅ＿ｘ、Ｆｕｎｃ＿Ｄ＿ｘ、Ｆｕｎｃ＿Ｃ＿ｘ、Ｆｕｎｃ＿Ｂ＿ｘ、Ｆｕｎｃ＿Ａ＿ｘ）を含んでいる。
図４に、変更後ソースコード２２０を示す。変更後ソースコード２２０は、変更後ソースコードの具体例である。
変更後ソースコード２２０は、５つの関数（Ｆｕｎｃ＿Ｅ＿ｙ、Ｆｕｎｃ＿Ｄ＿ｙ、Ｆｕｎｃ＿Ｃ＿ｙ、Ｆｕｎｃ＿Ｂ＿ｙ、Ｆｕｎｃ＿Ａ＿ｙ）を含んでいる。
変更前ソースコード２１０および変更後ソースコード２２０において、コロンおよび三点リーダは記載の省略を意味する。
【００２８】
図２に戻り、ステップＳ１１０から説明を続ける。
ステップＳ１１０において、コールグラフ生成部１１０は、変更前ソースコードと変更後ソースコードとを解析することによって、変更前コールグラフと変更後コールグラフとを生成する。記憶部１９１は、変更前コールグラフと変更後コールグラフとを記憶する。
変更前コールグラフは、変更前ソースコードのコールグラフである。
変更後コールグラフは、変更後ソースコードのコールグラフである。
コールグラフは、関数間の呼び出し関係を示すデータであり、従来技術によって生成することが可能である。
【００２９】
例えば、コールグラフ生成部１１０は、変更前ソースコードを入力としてｅｇｙｐｔを実行することによって、変更前コールグラフを生成する。また、コールグラフ生成部１１０は、変更後ソースコードを入力としてｅｇｙｐｔを実行することによって、変更後コールグラフを生成する。ｅｇｙｐｔは、コールグラフを生成するための既存のツールである。
【００３０】
図５に、変更前コールグラフ２３１を示す。変更前コールグラフ２３１は、図３の変更前ソースコード２１０を入力としてｅｇｙｐｔを実行することによって得られる変更前コールグラフである。
変更前コールグラフ２３１は、Ｆｕｎｃ＿Ａ＿ｘからＦｕｎｃ＿Ｂ＿ｘとＦｕｎｃ＿Ｃ＿ｘとが呼ばれ、Ｆｕｎｃ＿Ｂ＿ｘからＦｕｎｃ＿Ｄ＿ｘとＦｕｎｃ＿Ｅ＿ｘとが呼ばれ、Ｆｕｎｃ＿Ｃ＿ｘからＦｕｎｃ＿Ｆ＿ｘが呼ばれることを示している。
【００３１】
図６に、変更後コールグラフ２３２を示す。変更後コールグラフ２３２は、図４の変更後ソースコード２２０を入力としてｅｇｙｐｔを実行することによって得られる変更後コールグラフである。
変更後コールグラフ２３２は、Ｆｕｎｃ＿Ａ＿ｙからＦｕｎｃ＿Ｂ＿ｙとＦｕｎｃ＿Ｃ＿ｙとが呼ばれ、Ｆｕｎｃ＿Ｂ＿ｙからＦｕｎｃ＿Ｄ＿ｙとＦｕｎｃ＿Ｅ＿ｙとが呼ばれることを示している。
【００３２】
図２に戻り、ステップＳ１２０から説明を続ける。
ステップＳ１２０において、受付部１９２は、関数対応表を受け付ける。そして、記憶部１９１は、受け付けられた関数対応表を記憶する。
関数対応表は、変更前関数と変更後関数との対応関係を示すデータである。
変更前関数は、変更前ソースコードに含まれる関数である。
変更後関数は、変更後ソースコードに含まれる関数である。
【００３３】
特に、関数対応表は、変更前関数または変更後関数の逆呼び出し順に、変更前関数と変更後関数との対応関係を示す。
逆呼び出し順とは、呼び出し順の逆順である。
呼び出し順とは、呼び出し関係において上位から下位への順である。呼び出し関係における上位は呼び出し元の関数であり、呼び出し関係における下位は呼び出し先の関数である。
呼び出し順における最終の関数、つまり、逆呼び出し順における先頭の関数を、末端の関数という。
【００３４】
例えば、関数対応表は以下のような手順で受け付けられる。
まず、表示部１９３は、変更前コールグラフをディスプレイに表示する。
次に、検証者は、変更前コールグラフを参照し、変更前関数の逆呼び出し順を判断する。
次に、検証者は、変更前仕様書と変更後仕様書とを参照し、変更前関数の逆呼び出し順に変更前関数に対応する変更後関数を判断する。
次に、検証者は、入力装置を操作して、関数対応表を等価性検証装置１００に入力する。
そして、受付部１９２は、入力された関数対応表を受け付ける。
【００３５】
図７に、関数対応表２３３を示す。関数対応表２３３は、図３の変更前ソースコード２１０と図４の変更後ソースコード２２０とに対応する関数対応表である。
関数対応表２３３は、変更前ソースコード２１０に含まれる関数と変更後ソースコード２２０に含まれる関数とを互いに対応付けている。
変更前関数の欄は変更前ソースコード２１０に含まれる関数の名称を示し、変更後関数の欄は変更後ソースコード２２０に含まれる関数の名称を示している。ハイフンは該当する関数が無いことを意味する。
変更前関数の欄において、変更前ソースコード２１０に含まれる関数の名称は、逆呼び出し順に並べられている。
関数対応表２３３の第１行は、Ｆｕｎｃ＿Ｆ＿ｘに対応する変更後関数が無いことを示している。また、関数対応表２３３の第２行から第６行は、Ｆｕｎｃ＿＃＿ｘとＦｕｎｃ＿＃＿ｙとが互いに対応することを示している。「＃」はＡ、Ｂ、Ｃ、ＤまたはＥを表す。
末端の変更前関数はＦｕｎｃ＿Ｆ＿ｘである。
【００３６】
図２に戻り、ステップＳ１３１から説明を続ける。
ステップＳ１３１において、制御部１２０は未選択の変更前関数を１つ選択する。具体的には、制御部１２０は、末端の変更前関数から順に選択する。例えば、制御部１２０は、関数対応表に示される順に変更前関数を１つ選択する。
【００３７】
ステップＳ１３２およびステップＳ１３３の説明において、選択された変更前関数は、ステップＳ１３１で選択された変更前関数を意味する。
【００３８】
ステップＳ１３２において、制御部１２０は、関数対応表を用いて、選択された変更前関数に対応する変更後関数が有るか判定する。
具体的には、制御部１２０は、選択された変更前関数の名称を含む行を関数対応表２３３から選択し、選択された行に変更後関数の名称が有るか判定する。選択された行に変更後関数の名称が有れば、選択された変更前関数に対応する変更後関数が有る。
選択された変更前関数がＦｕｎｃ＿Ｂ＿ｘである場合、制御部１２０は、図７の関数対応表２３３から第５行を選択する。選択された第５行には変更後関数の名称（Ｆｕｎｃ＿Ｂ＿ｙ）が有る。したがって、制御部１２０は、選択された変更前関数に対応する変更後関数が有ると判定する。
選択された変更前関数がＦｕｎｃ＿Ｆ＿ｘである場合、制御部１２０は、図７の関数対応表２３３から第１行を選択する。選択された第１行には変更後関数の名称が無い。したがって、制御部１２０は、選択された変更前関数に対応する変更後関数が無いと判定する。
選択された変更前関数に対応する変更後関数が有る場合、処理はステップＳ１４０に進む。
選択された変更前関数に対応する変更後関数が無い場合、処理はステップＳ１３３に進む。
【００３９】
以降の説明において、選択された変更前関数と選択された変更前関数に対応する変更後関数との組を対応組という。また、対応組に含まれる関数を対象関数という。
【００４０】
ステップＳ１３３において、制御部１２０は、選択された変更前関数を等価性判定表に不等価関数として登録する。
不等価関数は、不等価である対応組に含まれる関数、つまり、不等価である対象関数である。
等価性判定表は、対象関数の等価性などを管理するためのデータである。
【００４１】
図８に、等価性判定表２４０を示す。
図８の等価性判定表２４０は、Ｆｕｎｃ＿Ｆ＿ｘが不等価関数として登録されたときの等価性判定表である。
等価性判定表２４０は、対象関数と反例と等価性と変更前ソースコードと変更後ソースコードとのそれぞれの欄を有している。
対象関数の欄は、対象関数を示す。Ｆｕｎｃ＿ＦはＦｕｎｃ＿Ｆ＿ｘを識別する。
等価性の欄は、対象関数同士の等価性を示す。
反例の欄と変更前ソースコードの欄と変更後ソースコードの欄とのそれぞれに記された斜線は、一方の対象関数に対応する他方の対象関数が無いことを意味する。
反例と変更前ソースコードと変更後ソースコードとのそれぞれの欄については後述する。
【００４２】
図２に戻り、ステップＳ１４０を説明する。
ステップＳ１４０において、等価性検証装置１００は、対応組に対する全等価検証および部分等価検証を行う。
全等価検証は、２つの関数が全等価であるか否かを判定するための処理である。
全等価は、全ての入力値において２つの関数が等価であることを意味する。
等価は、２つの関数に同じ入力値が与えられた場合に一方の関数の出力値が他方の関数の出力値と一致することを意味する。言い換えると、等価は、２つのソースコードの論理的な演算内容が一致すること、つまり同じ入力値に対してソースコードを実行したときに同じ出力値が得られることである。
部分等価検証は、２つの関数が部分等価であるか否かを判定するための処理である。
部分等価は、一部の入力値において２つの関数が等価であることを意味する。言い換えると、部分等価は、全ての入力値ではなく、一部の入力値において、ソースコードを実行した際に出力値が常に一致することである。
ステップＳ１４０の詳細については後述する。
【００４３】
ステップＳ１３３またはステップＳ１４０の後、処理はステップＳ１３４に進む。
ステップＳ１３４において、制御部１２０は、未選択の変更前関数が有るから判定する。
未選択の変更前関数が有る場合、処理はステップＳ１３１に進む。
未選択の変更前関数が無い場合、処理は等価性検証方法は終了する。
【００４４】
図９に基づいて、検証処理（Ｓ１４０）の手順を説明する。
ステップＳ１４１およびステップＳ１４２は全等価検証に相当する。
【００４５】
ステップＳ１４１において、等価性検証部１３０は、検証ファイルを生成する。
検証ファイルは、等価性検証の入力となるデータである。
等価性検証は、２つの関数の等価性を検証するための処理である。つまり、等価性検証は、２つの関数が等価であるか否かを判定するための処理である。
【００４６】
具体的には、等価性検証部１３０は、入力一致文と呼び出し文と出力一致文とを生成し、各々の文をファイルに記載する。これによって得られるファイルが検証ファイルである。
入力一致文は、一方の対象関数の入力値が他方の対象関数の入力値と一致するという事前条件を示す文である。入力一致文によって、両方の対象関数に同じ入力値が与えられる。
呼び出し文は、対象関数を呼び出して実行するための文である。
出力一致文は、一方の対象関数の出力値が他方の対象関数の出力値と一致するという事後条件を示す文である。
【００４７】
図１０に、検証ファイル２５０を示す。
検証ファイル２５０は、Ｆｕｎｃ＿Ｂ＿ｘおよびＦｕｎｃ＿Ｂ＿ｙが対象関数である場合の検証ファイルである。
検証ファイル２５０は、入力一致文２５１と２つの呼び出し文（２５２、２５３）と出力一致文２５４とを含んでいる。
入力一致文２５１は、ｉｎｐｕｔ＿ｘがｉｎｐｕｔ＿ｙと一致するという事前条件を示している。ｉｎｐｕｔ＿ｘはＦｕｎｃ＿Ｂ＿ｘの入力値であり、ｉｎｐｕｔ＿ｙはＦｕｎｃ＿Ｂ＿ｙの入力値である。
呼び出し文２５２によって、ｉｎｐｕｔ＿ｘを入力値としてＦｕｎｃ＿Ｂ＿ｘが呼び出されて実行される。Ｆｕｎｃ＿Ｂ＿ｘの出力値はｏｕｔｐｕｔ＿ｘに設定される。
呼び出し文２５３によって、ｉｎｐｕｔ＿ｙを入力値としてＦｕｎｃ＿Ｂ＿ｙが呼び出されて実行される。Ｆｕｎｃ＿Ｂ＿ｙの出力値はｏｕｔｐｕｔ＿ｙに設定される。
出力一致文２５４は、ｏｕｔｐｕｔ＿ｘがｏｕｔｐｕｔ＿ｙと一致するという事後条件を示している。
二重斜線付きの文字列はコメントである。
【００４８】
ステップＳ１４２において、等価性検証部１３０は、検証ファイルを用いて等価性検証を行う。
具体的には、等価性検証部１３０は、検証ファイルと変更前ソースコードと変更後ソースコードとを入力として等価性検証を行う。等価性検証は従来の技術である。
等価性検証によって、検証ファイルの記載に従って変更前ソースコードと変更後ソースコードとが実行され、実行結果に基づいて変更前ソースコートと変更後ソースコードとの等価性が検証される。
例えば、等価性検証部１３０は、ＣＢＭＣ（Ｂｏｕｎｄｅｄ  Ｍｏｄｅｌ  Ｃｈｅｃｋｉｎｇ  ｆｏｒ  Ｃ／Ｃ＋＋）と呼ばれるツールを実行することによって、等価性検証を行う。
そして、等価性検証部１３０は、等価性検証の結果を等価性判定表に登録する。
【００４９】
図１１に、等価性判定表２４０を示す。
図１１の等価性判定表２４０は、ステップＳ１４２においてＦｕｎｃ＿Ｂに対する等価性検証が行われる直前の等価性判定表である。Ｆｕｎｃ＿ＢはＦｕｎｃ＿Ｂ＿ｘおよびＦｕｎｃ＿Ｂ＿ｙを識別する。
対象関数の欄において、Ｆｕｎｃ＿ＥはＦｕｎｃ＿Ｅ＿ｘおよびＦｕｎｃ＿Ｅ＿ｙを識別し、Ｆｕｎｃ＿ＤはＦｕｎｃ＿Ｄ＿ｘおよびＦｕｎｃ＿Ｄ＿ｙを識別し、Ｆｕｎｃ＿ＣはＦｕｎｃ＿Ｃ＿ｘおよびＦｕｎｃ＿Ｃ＿ｙを識別する。
呼び出し関係においてＦｕｎｃ＿Ｆ、Ｆｕｎｃ＿Ｅ、Ｆｕｎｃ＿ＤおよびＦｕｎｃ＿ＣはＦｕｎｃ＿Ｂの下位の関数であるので、Ｆｕｎｃ＿Ｆ、Ｆｕｎｃ＿Ｅ、Ｆｕｎｃ＿ＤおよびＦｕｎｃ＿Ｃは検証済みである。そのため、等価性判定表２４０には、Ｆｕｎｃ＿Ｆ、Ｆｕｎｃ＿Ｅ、Ｆｕｎｃ＿ＤおよびＦｕｎｃ＿Ｃの等価性に関する情報が登録されている。
【００５０】
図１２に、等価性判定表２４０を示す。
図１２の等価性判定表２４０は、ステップＳ１４２においてＦｕｎｃ＿Ｂに対する等価性検証が行われた場合の等価性判定表である。
等価性判定表２４０において、Ｆｕｎｃ＿Ｂに対する等価性検証の結果として、反例の欄に０が登録されている。
反例の欄は、一方の対象関数の出力値が他方の対象関数の出力値と一致しない場合の入力値を示す。但し、反例の欄には、入力値と出力値との両方または出力値のみが登録されてもよい。
反例の欄において、三点リーダは記載の省略を意味し、ハイフンは該当する値が無いことを意味する。
【００５１】
Ｆｕｎｃ＿Ｂに対する等価性の欄、変更前ソースコードの欄および変更後ソースコードの欄は、まだ空欄である。但し、Ｆｕｎｃ＿Ｂに対する等価性の欄に、暫定的に不等価が登録されてもよい。
【００５２】
図９に戻り、ステップＳ１４３から説明を続ける。
ステップＳ１４３において、識別子設定部１４０は、変更前ソースコードの中の対象関数と変更後ソースコードの中の対象関数とのそれぞれに、分岐箇所識別子を設定する。
分岐箇所識別子は、分岐箇所を識別する識別子である。
【００５３】
具体的には、識別子設定部１４０は、変更前ソースコードと変更後ソースコードとのそれぞれのソースコードに対して以下のように分岐箇所識別子を設定する。
まず、識別子設定部１４０は、ソースコードから対象関数を選択する。
次に、識別子設定部１４０は、対象関数から分岐文を見つける。分岐文は、条件によってパスを分岐するための文である。具体的な分岐文はｉｆ文およびｅｌｓｅ文である。パスは、ソースコードにおける処理経路である。
次に、識別子設定部１４０は、対象関数の先頭と分岐文とのそれぞれを分岐箇所として、分岐箇所毎に分岐箇所識別子を生成する。
次に、識別子設定部１４０は、分岐箇所識別子毎に更新文を生成する。更新文は、分岐箇所識別子の値を更新する文である。
そして、識別子設定部１４０は、分岐箇所毎に更新文を追加する。
【００５４】
図１３に、変更前ソースコード２１０を示す。
図１３の変更前ソースコード２１０は、Ｆｕｎｃ＿Ｂ＿ｘが対象関数である場合において、ステップＳ１４３が実行される直前の変更前ソースコード２１０である。
呼び出し関係においてＦｕｎｃ＿Ｂ＿ｘよりも下位の関数であるＦｕｎｃ＿Ｆ＿ｘ、Ｆｕｎｃ＿Ｅ＿ｘ、Ｆｕｎｃ＿Ｄ＿ｘおよびＦｕｎｃ＿Ｃ＿ｘには、更新文（２１１〜２１４）が追加されている。
変更前ソースコード２１０において、ｃｏｕｎｔＮ＿ｘが分岐箇所識別子である。Ｎは整数を意味する。
【００５５】
図１４に、変更前ソースコード２１０を示す。
図１４の変更前ソースコード２１０は、Ｆｕｎｃ＿Ｂ＿ｘが対象関数である場合において、ステップＳ１４３が実行された直後の変更前ソースコード２１０である。
Ｆｕｎｃ＿Ｂ＿ｘには、３つの更新文（２１５〜２１６）が追加されている。
【００５６】
図１５に、変更後ソースコード２２０を示す。
図１５の変更後ソースコード２２０は、Ｆｕｎｃ＿Ｂ＿ｙが対象関数である場合において、ステップＳ１４３が実行される直前の変更後ソースコード２２０である。
呼び出し関係においてＦｕｎｃ＿Ｂ＿ｙよりも下位の関数であるＦｕｎｃ＿Ｅ＿ｙ、Ｆｕｎｃ＿Ｄ＿ｙおよびＦｕｎｃ＿Ｃ＿ｙには、更新文（２２１〜２２３）が追加されている。
変更後ソースコード２２０において、ｃｏｕｎｔＮ＿ｙが分岐箇所識別子である。Ｎは整数を意味する。
【００５７】
図１６に、変更後ソースコード２２０を示す。
図１６の変更後ソースコード２２０は、Ｆｕｎｃ＿Ｂ＿ｙが対象関数である場合において、ステップＳ１４３が実行された直後の変更後ソースコード２２０である。
Ｆｕｎｃ＿Ｂ＿ｙには、３つの更新文（２２４〜２２６）が追加されている。
【００５８】
図９に戻り、ステップＳ１４４から説明を続ける。
ステップＳ１４４において、識別子設定部１４０は、対象関数の中の呼び出し先関数毎に呼び出し先関数に対応付けて分岐箇所識別子を識別子対応表に登録する。
呼び出し先関数は、呼び出される関数である。対象関数の中の呼び出し先関数は、対象関数から呼び出される関数である。
識別子対応表は、呼び出し先関数と分岐箇所識別子との対応関係を管理するためのデータである。
【００５９】
具体的には、識別子設定部１４０は分岐箇所識別子を以下のように登録する。
まず、識別子設定部１４０は、ソースコードの中の対象関数から呼び出し文を抽出し、呼び出し文から関数名を抽出する。抽出される関数名で識別される関数が呼び出し先関数である。
次に、識別子設定部１４０は、呼び出し文から対象関数の先頭に向けてソースコードを参照し、最初に見つかる分岐箇所識別子を抽出する。抽出される分岐箇所識別子は、呼び出し先関数に対応する分岐箇所識別子である。
そして、識別子設定部１４０は、呼び出し先関数の関数名と呼び出し先関数に対応する分岐箇所識別子とを識別子対応表に登録する。
【００６０】
図１７に、識別子対応表２６０を示す。
図１７の識別子対応表２６０は、Ｆｕｎｃ＿Ｂ＿ｘおよびＦｕｎｃ＿Ｂ＿ｙが対象関数である場合において、ステップＳ１４４が実行される直前の識別子対応表２６０である。
識別子対応表２６０は、対象関数と変更前ソースコードと変更後ソースコードとのそれぞれの欄を有する。変更前ソースコードと変更後ソースコードとのそれぞれの欄には、分岐箇所識別子の欄と呼び出し先関数の欄とが含まれる。
図１３に示すように、Ｆｕｎｃ＿Ｃ＿ｘの中の呼び出し先関数はＦｕｎｃ＿Ｆ＿ｘである。そのため、図１７に示すように、Ｆｕｎｃ＿Ｃに対応する変更前ソースコードの欄において、呼び出し先関数の欄にＦｕｎｃ＿Ｆ＿ｘが登録されている。
図１３に示すように、Ｆｕｎｃ＿Ｆ＿ｘに対応する分岐箇所識別子はｃｏｕｎｔ４＿ｘである。そのため、図１７に示すように、Ｆｕｎｃ＿Ｆに対応する変更前ソースコードの欄において、分岐箇所識別子の欄にｃｏｕｎｔ４＿ｘが登録されている。
【００６１】
図１８に、識別子対応表２６０を示す。
図１８の識別子対応表２６０は、Ｆｕｎｃ＿Ｂ＿ｘおよびＦｕｎｃ＿Ｂ＿ｙが対象関数である場合において、ステップＳ１４４が実行された直後の識別子対応表２６０である。
図１４に示すように、Ｆｕｎｃ＿Ｂ＿ｘの中の呼び出し先関数はＦｕｎｃ＿Ｄ＿ｘおよびＦｕｎｃ＿Ｅ＿ｘである。そのため、図１８に示すように、Ｆｕｎｃ＿Ｂに対応する変更前ソースコードの欄において、呼び出し先関数の欄にＦｕｎｃ＿Ｄ＿ｘおよびＦｕｎｃ＿Ｅ＿ｘが登録されている。
図１４に示すように、Ｆｕｎｃ＿Ｄ＿ｘに対応する分岐箇所識別子はｃｏｕｎｔ６＿ｘであり、Ｆｕｎｃ＿Ｅ＿ｘに対応する分岐箇所識別子はｃｏｕｎｔ７＿ｘである。そのため、図１８に示すように、Ｆｕｎｃ＿Ｄに対応する変更前ソースコードの欄において、分岐箇所識別子の欄にｃｏｕｎｔ６＿ｘが登録されている。さらに、Ｆｕｎｃ＿Ｅに対応する変更前ソースコードの欄において、分岐箇所識別子の欄にｃｏｕｎｔ７＿ｘが登録されている。
図１６に示すように、Ｆｕｎｃ＿Ｂ＿ｙの中の呼び出し先関数はＦｕｎｃ＿Ｄ＿ｙおよびＦｕｎｃ＿Ｅ＿ｙである。そのため、図１８に示すように、Ｆｕｎｃ＿Ｂに対応する変更後ソースコードの欄において、呼び出し先関数の欄にＦｕｎｃ＿Ｄ＿ｙおよびＦｕｎｃ＿Ｅ＿ｙが登録されている。
図１６に示すように、Ｆｕｎｃ＿Ｄ＿ｙに対応する分岐箇所識別子はｃｏｕｎｔ５＿ｙであり、Ｆｕｎｃ＿Ｅ＿ｙに対応する分岐箇所識別子はｃｏｕｎｔ６＿ｙである。そのため、図１８に示すように、Ｆｕｎｃ＿Ｄに対応する変更後ソースコードの欄において、分岐箇所識別子の欄にｃｏｕｎｔ５＿ｙが登録されている。さらに、Ｆｕｎｃ＿Ｅに対応する変更後ソースコードの欄において、分岐箇所識別子の欄にｃｏｕｎｔ６＿ｙが登録されている。
【００６２】
図９に戻り、ステップＳ１４５から説明を続ける。
ステップＳ１４５において、等価性検証部１３０は、ステップＳ１４２での等価性検証の結果が等価であるか判定する。
等価性検証の結果が等価である場合、処理はステップＳ１４６に進む。
等価性検証の結果が等価でない場合、処理はステップＳ２００に進む。
【００６３】
ステップＳ１４６において、等価性検証部１３０は、等価性判定表に対象関数を等価関数として登録する。
等価関数は、全等価である対応組に含まれる関数、つまり、全等価である対象関数である。
【００６４】
ステップＳ２００において、等価性検証装置１００は、対応組に対する部分等価検証を行う。つまり、等価性検証装置１００は、対象関数同士が部分等価であるか否かを判定する。
【００６５】
図１９に基づいて、部分等価検証（Ｓ２００）の手順を説明する。
ステップＳ２１０において、部分検証判定部１５０は、不等価パスと非不等価パスとの両方が対象関数に含まれるか判定する。
但し、対象関数は変更前関数または変更後関数を意味する。つまり、ステップＳ２１０では、変更前関数と変更後関数との少なくとも一方に不等価パスと非不等価パスとの両方が含まれるか判定される。
【００６６】
不等価パスは、不等価関数が呼び出されるパスである。
非不等価パスは、非不等価関数が呼び出されるパスである。
非不等価関数は、不等価関数ではない関数である。具体的には、非不等価関数は、等価関数および部分等価関数である。
部分等価関数は、部分等価である対応組に含まれる関数、つまり、部分等価である対象関数である。
【００６７】
不等価パスと非不等価パスとの両方が含まれる対象関数を含んだ対応組を部分検証組という。
不等価パスと非不等価パスとの両方が対象関数に含まれる場合、つまり、対応組が部分検証組である場合、処理はステップＳ２２０に進む。
不等価パスと非不等価パスとのいずれかが対象関数に含まれない場合、つまり、対応組が部分検証組でない場合、処理はステップＳ２３３に進む。
【００６８】
図２０に基づいて、部分検証判定（Ｓ２１０）の手順を説明する。
ステップＳ２１１において、部分検証判定部１５０は、対象関数が複数の呼び出し先関数を呼び出す関数であるか判定する。
【００６９】
具体的には、部分検証判定部１５０は、識別子対応表２６０を用いて以下のように判定を行う。
まず、部分検証判定部１５０は、識別子対応表２６０を参照し、対象関数に対応付けられた呼び出し先関数の数を数える。
そして、部分検証判定部１５０は、対象関数に対応付けられた呼び出し先関数の数が２以上であるか判定する。
対象関数に対応付けられた呼び出し先関数の数が２以上である場合、対象関数が複数の呼び出し先関数を呼び出す関数である。
【００７０】
対象関数が複数の呼び出し先関数を呼び出す関数である場合、処理はステップＳ２１２に進む。
対象関数が複数の呼び出し先関数を呼び出す関数ではない場合、処理はステップＳ２１５に進む。
【００７１】
対象関数がＦｕｎｃＢ＿ｘである場合、図１８の識別子対応表２６０において、対象関数に対応付けられた呼び出し先関数（Ｆｕｎｃ＿Ｄ＿ｘ、Ｆｕｎｃ＿Ｅ＿ｘ）の数は２である。
対象関数がＦｕｎｃＢ＿ｙである場合、図１８の識別子対応表２６０において、対象関数に対応付けられた呼び出し先関数（Ｆｕｎｃ＿Ｄ＿ｙ、Ｆｕｎｃ＿Ｅ＿ｙ）の数は２である。
したがって、対応組がＦｕｎｃ＿Ｂ＿ｘとＦｕｎｃ＿Ｂ＿ｙとの組である場合、処理はステップＳ２１２に進む。
【００７２】
ステップＳ２１２において、部分検証判定部１５０は、不等価関数と非不等価関数との両方が複数の呼び出し先関数に含まれるか判定する。
【００７３】
具体的には、部分検証判定部１５０は、識別子対応表２６０と等価性判定表２４０とを用いて以下のように判定を行う。
まず、部分検証判定部１５０は、識別子対応表２６０を参照し、対象関数に対応付けられた複数の呼び出し先関数を特定する。
次に、部分検証判定部１５０は、等価性判定表２４０を参照し、複数の呼び出し先関数に対応する複数の等価性を特定する。
そして、部分検証判定部１５０は、複数の等価性の少なくともいずれかが不等価であり、且つ、複数の等価性の少なくともいずれかが等価または部分等価であるか判定する。
複数の等価性の少なくともいずれかが不等価であり、且つ、複数の等価性の少なくともいずれかが等価または部分等価である場合、不等価関数と非不等価関数との両方が複数の呼び出し先関数に含まれる。
【００７４】
不等価関数と非不等価関数との両方が複数の呼び出し先関数に含まれる場合、処理はステップＳ２１３に進む。
不等価関数と非不等価関数との一方が複数の呼び出し先関数に含まれない場合、処理はステップＳ２１５に進む。
【００７５】
対象関数がＦｕｎｃＢ＿ｘである場合、図１８の識別子対応表２６０において、対象関数に対応付けられた呼び出し先関数はＦｕｎｃ＿Ｄ＿ｘおよびＦｕｎｃ＿Ｅ＿ｘである。図１２の等価性判定表２４０において、Ｆｕｎｃ＿Ｄ＿ｘの等価性は等価であり、Ｆｕｎｃ＿Ｅ＿ｘの等価性は不等価である。
対象関数がＦｕｎｃＢ＿ｙである場合、図１８の識別子対応表２６０において、対象関数に対応付けられた呼び出し先関数はＦｕｎｃ＿Ｄ＿ｙおよびＦｕｎｃ＿Ｅ＿ｙである。図１２の等価性判定表２４０において、Ｆｕｎｃ＿Ｄ＿ｙの等価性は等価であり、Ｆｕｎｃ＿Ｅ＿ｙの等価性は不等価である。
したがって、対応組がＦｕｎｃ＿Ｂ＿ｘとＦｕｎｃ＿Ｂ＿ｙとの組である場合、処理はステップＳ２１３に進む。
【００７６】
ステップＳ２１３において、部分検証判定部１５０は、不等価関数の分岐箇所識別子が非不等価関数の分岐箇所識別子と異なるか判定する。
不等価関数の分岐箇所識別子は、不等価関数が呼び出される箇所に対応する分岐箇所識別子である。
非不等価関数の分岐箇所識別子は、非不等価関数が呼び出される箇所に対応する分岐箇所識別子である。
【００７７】
具体的には、部分検証判定部１５０は、識別子対応表２６０を用いて以下のように判定を行う。
まず、部分検証判定部１５０は、不等価関数毎に不等価関数に対応付けられた分岐箇所識別子を識別子対応表２６０から抽出する。抽出される分岐箇所識別子が不等価関数の分岐箇所識別子である。
さらに、部分検証判定部１５０、非不等価関数毎に非不等価関数に対応付けられた分岐箇所識別子を識別子対応表２６０から抽出する。抽出される分岐箇所識別子が非不等価関数の分岐箇所識別子である。
そして、部分検証判定部１５０は、不等価関数と非不等価関数との組毎に不等価関数の分岐箇所識別子を非不等価関数の分岐箇所識別子と比較する。
少なくともいずれかの組で不等価関数の分岐箇所識別子が非不等価関数の分岐箇所識別子と一致しない場合、不等価関数に対応する分岐箇所識別子が非不等価関数に対応する分岐箇所と異なる。
【００７８】
不等価関数に対応する分岐箇所識別子が非不等価関数に対応する分岐箇所と異なる場合、処理はステップＳ２１４に進む。
不等価関数に対応する分岐箇所識別子が非不等価関数に対応する分岐箇所と一致する場合、処理はステップＳ２１５に進む。
【００７９】
ステップＳ２１４において、部分検証判定部１５０は、不等価パスと非不等価パスとの両方が対象関数に含まれると判定する。
【００８０】
ステップＳ２１５において、部分検証判定部１５０は、不等価パスと非不等価パスとの一方が対象関数に含まれないと判定する。
【００８１】
図１９に戻り、ステップＳ２２０から説明を続ける。
ステップＳ２２０において、部分検証部１６０は、不等価パスを除外して対象組に対する等価性検証を行う。つまり、部分検証部１６０は、非不等価パスにおいて対象関数同士が等価であるか否かを判定する。
【００８２】
図２１に基づいて、部分検証（Ｓ２２０）の手順を説明する。
ステップＳ２２１において、部分検証部１６０は、第１除外制御文を検証ファイルに追加する。
第１除外制御文は、第１不等価パスを除外するための文である。
第１不等価パスは、対象関数の中の不等価パスである。
第１不等価パスで呼び出される不等価関数を第１不等価関数という。
【００８３】
具体的には、部分検証部１６０は第１除外制御文を以下のように追加する。
まず、部分検証部１６０は第１除外制御文を生成する。
第１除外制御文は、第１分岐箇所識別子の値が更新前の値（初期値）と一致するか判定する文である。第１分岐箇所識別子の値が更新前の値と一致しない場合、第１不等価パスを通る条件となる入力は等価検証から除外される。
第１分岐箇所識別子は、第１不等価関数の分岐箇所識別子、つまり、第１不等価関数が呼び出される箇所に対応する分岐箇所識別子である。
次に、部分検証部１６０は、対象関数を呼び出す呼び出し文を検証ファイルから選択する。
そして、部分検証部１６０は、選択された呼び出し文の後に第１除外制御文を追加する。
【００８４】
図２２に、ステップＳ２２１の後の検証ファイル２５０を示す。
検証ファイル２５０は、呼び出し文２５２の後に第１除外制御文２５５を含んでいる。さらに、検証ファイル２５０は、呼び出し文２５３の後に第１除外制御文２５６を含んでいる。
第１除外制御文２５５により、ｃｏｕｎｔ７＿ｘの値が更新前の値と一致するか判定される。ｃｏｕｎｔ７＿ｘは、Ｆｕｎｃ＿Ｅ＿ｘの分岐箇所識別子である（図１８参照）。Ｆｕｎｃ＿Ｅ＿ｘは、Ｆｕｎｃ＿Ｂ＿ｘの呼び出し先関数であり（図１８参照）、不等価関数である（図１２参照）。第１不等価関数が呼ばれていた場合、ｃｏｕｎｔ７＿ｘの値は０から１に更新されている。このとき、ｃｏｕｎｔ７＿ｘの値は等価性判定範囲外（図２２参照）である。つまり、第１除外制御文２５５による判定結果は不一致である。そのため、ｃｏｕｎｔ７＿ｘに対応する入力は等価検証から除外される。
第１除外制御文２５６により、ｃｏｕｎｔ６＿ｙの値が更新前の値と一致するか判定される。ｃｏｕｎｔ６＿ｙは、Ｆｕｎｃ＿Ｅ＿ｙの分岐箇所識別子である（図１８参照）。Ｆｕｎｃ＿Ｅ＿ｙは、Ｆｕｎｃ＿Ｂ＿ｙの呼び出し先関数であり（図１８参照）、不等価関数である（図１２参照）。第１不等価関数が呼ばれていた場合、ｃｏｕｎｔ６＿ｙの値は０から１に更新されている。このとき、ｃｏｕｎｔ６＿ｙの値は等価性判定範囲外（図２２参照）である。つまり、第１除外制御文２５６による判定結果は不一致である。そのため、ｃｏｕｎｔ６＿ｙに対応する入力は等価検証から除外される。
【００８５】
図２１に戻り、ステップＳ２２２から説明を続ける。
ステップＳ２２２において、部分検証部１６０は、対象関数が部分等価関数を呼び出す関数であるか判定する。
つまり、部分検証部１６０は、対象関数から呼び出される複数の呼び出し先関数の中に部分等価関数が有るか判定する。
【００８６】
具体的には、部分検証部１６０は、識別子対応表２６０と等価性判定表２４０とを用いて以下のように判定を行う。
まず、部分検証部１６０は、識別子対応表２６０を参照し、対象関数に対応付けられた複数の呼び出し先関数を特定する。
次に、部分検証部１６０は、等価性判定表２４０を参照し、複数の呼び出し先関数に対応する複数の等価性を特定する。
そして、部分検証部１６０は、複数の等価性の少なくともいずれかが部分等価であるか判定する。
複数の等価性の少なくともいずれかが部分等価である場合、対象関数が部分等価関数を呼び出す関数である。
【００８７】
対象関数が部分等価関数を呼び出す関数である場合、処理はステップＳ２２３に進む。
対象関数が部分等価関数を呼び出す関数でない場合、処理はステップＳ２２４に進む。
【００８８】
Ｆｕｎｃ＿Ｂ＿ｘの呼び出し先関数はＦｕｎｃ＿Ｄ＿ｘおよびＦｕｎｃ＿Ｅ＿ｘである（図１８参照）。Ｆｕｎｃ＿Ｄ＿ｘとＦｕｎｃ＿Ｅ＿ｘとのいずれの等価性も部分等価でない（図１２参照）。そのため、Ｆｕｎｃ＿Ｂ＿ｘは部分等価関数を呼び出す関数ではない。
Ｆｕｎｃ＿Ｂ＿ｙの呼び出し先関数はＦｕｎｃ＿Ｄ＿ｙおよびＦｕｎｃ＿Ｅ＿ｙである（図１８参照）。Ｆｕｎｃ＿Ｄ＿ｙとＦｕｎｃ＿Ｅ＿ｙとのいずれの等価性も部分等価でない（図１２参照）。そのため、Ｆｕｎｃ＿Ｂ＿ｙは部分等価関数を呼び出す関数ではない。
したがって、対応組がＦｕｎｃ＿Ｂ＿ｘとＦｕｎｃ＿Ｂ＿ｙとを含んだ組である場合、処理はステップＳ２２４に進む。
【００８９】
ステップＳ２２３において、部分検証部１６０は、第２除外制御文を検証ファイルに追加する。
第２除外制御文は、第２不等価パスを除外するための文である。
第２不等価パスは、対象関数から呼び出される部分等価関数の中の不等価パスである。
第２不等価パスで呼び出される不等価関数を第２不等価関数という。
【００９０】
具体的には、部分検証部１６０は第２除外制御文を以下のように追加する。
まず、部分検証部１６０は第２除外制御文を生成する。
第２除外制御文は、第２分岐箇所識別子の値が更新前の値（初期値）と一致するか判定する文である。第２分岐箇所識別子の値が更新前の値と一致しない場合、第２不等価パスを通る条件となる入力は等価検証から除外される。
第２分岐箇所識別子は、第２不等価関数の分岐箇所識別子、つまり、第２不等価関数が呼び出される箇所に対応する分岐箇所識別子である。
次に、部分検証部１６０は、部分等価関数を呼び出す呼び出し文を検証ファイルから選択する。
そして、部分検証部１６０は、選択された呼び出し文の後に第２除外制御文を追加する。
【００９１】
ステップＳ２２４において、部分検証部１６０は、検証ファイルと変更前ソースコードと変更後ソースコードとを用いて等価性検証を行う。
等価性検証を行う方法は、図９のステップＳ１４２における方法と同じである。
【００９２】
図１９に戻り、ステップＳ２３１から説明を続ける。
ステップＳ２３１において、部分検証部１６０は、ステップＳ２２０での等価性検証の結果が等価であるか判定する。
等価性検証の結果が等価である場合、処理はステップＳ２３２に進む。
等価性検証の結果が等価でない場合、処理はステップＳ２３３に進む。
【００９３】
ステップＳ２３２において、部分検証部１６０は、等価性判定表に対象関数を部分等価関数として登録する。
さらに、部分検証部１６０は、第１不等価関数の分岐箇所識別子と第２不等価関数の分岐箇所識別子とを等価性判定表に登録する。
【００９４】
図２３に、等価性判定表２４０を示す。
図２３の等価性判定表２４０は、Ｆｕｎｃ＿Ｂ＿ｘおよびＦｕｎｃ＿Ｂ＿ｙが部分等価関数である場合の等価性判定表２４０である。
Ｆｕｎｃ＿Ｂに対応する等価性の欄には部分等価が登録されている。
【００９５】
変更前ソースコードの欄は、対象関数である変更前関数用の欄である。
変更後ソースコードの欄は、対象関数である変更後関数用の欄である。
変更前ソースコードと変更後ソースコードとのそれぞれの欄は、第１不等価関数の分岐箇所識別子および第２不等価関数の分岐箇所識別子を示す。ハイフンは第１不等価関数および第２不等価関数が無いことを意味する。
【００９６】
Ｆｕｎｃ＿Ｂ＿ｘの第１不等価関数はＦｕｎｃ＿Ｅ＿ｘである（図１８および図１２参照）。Ｆｕｎｃ＿Ｅ＿ｘの分岐箇所識別子はｃｏｕｎｔ７＿ｘである（図１８参照）。そのため、Ｆｕｎｃ＿Ｂに対応する変更前ソースコードの欄にはｃｏｕｎｔ７＿ｘが登録されている。
Ｆｕｎｃ＿Ｂ＿ｙの第１不等価関数はＦｕｎｃ＿Ｅ＿ｙである（図１８および図１２参照）。Ｆｕｎｃ＿Ｅ＿ｙの分岐箇所識別子はｃｏｕｎｔ６＿ｙである（図１８参照）。そのため、Ｆｕｎｃ＿Ｂに対応する変更後ソースコードの欄にはｃｏｕｎｔ６＿ｙが登録されている。
【００９７】
ステップＳ２３３において、部分検証部１６０は、等価性判定表に対象関数を不等価関数として登録する。
【００９８】
以下に、対象関数が部分等価関数を呼び出す関数であるためステップＳ２２３（図２１参照）が実行される具体例を説明する。
対象関数は、Ｆｕｎｃ＿Ａ＿ｘおよびＦｕｎｃ＿Ａ＿ｙである。
【００９９】
図２４に、変更前ソースコード２１０を示す。
図２４の変更前ソースコード２１０は、Ｆｕｎｃ＿Ａ＿ｘが対象関数である場合において、ステップＳ１４３（図９参照）が実行された直後の変更前ソースコード２１０である。
Ｆｕｎｃ＿Ａ＿ｘには、３つの更新文（２１８、２１９、２１１０）が追加されている。
【０１００】
図２５に、変更後ソースコード２２０を示す。
図２５の変更後ソースコード２２０は、Ｆｕｎｃ＿Ａ＿ｙが対象関数である場合において、ステップＳ１４３（図９参照）が実行された直後の変更後ソースコード２２０である。
Ｆｕｎｃ＿Ａ＿ｙには、３つの更新文（２２７〜２２９）が追加されている。
【０１０１】
図２６に、識別子対応表２６０を示す。
図２６の識別子対応表２６０は、Ｆｕｎｃ＿Ａ＿ｘおよびＦｕｎｃ＿Ａ＿ｙが対象関数である場合において、ステップＳ１４４（図９参照）が実行された直後の識別子対応表２６０である。
図２４に示すように、Ｆｕｎｃ＿Ａ＿ｘの中の呼び出し先関数はＦｕｎｃ＿Ｂ＿ｘおよびＦｕｎｃ＿Ｃ＿ｘである。そのため、図２６に示すように、Ｆｕｎｃ＿Ａに対応する変更前ソースコードの欄において、呼び出し先関数の欄にＦｕｎｃ＿Ｂ＿ｘおよびＦｕｎｃ＿Ｃ＿ｘが登録されている。
図２４に示すように、Ｆｕｎｃ＿Ｂ＿ｘに対応する分岐箇所識別子はｃｏｕｎｔ９＿ｘであり、Ｆｕｎｃ＿Ｃ＿ｘに対応する分岐箇所識別子はｃｏｕｎｔ１０＿ｘである。そのため、図２６に示すように、Ｆｕｎｃ＿Ｂに対応する変更前ソースコードの欄において、分岐箇所識別子の欄にｃｏｕｎｔ９＿ｘが登録されている。さらに、Ｆｕｎｃ＿Ｃに対応する変更前ソースコードの欄において、分岐箇所識別子の欄にｃｏｕｎｔ１０＿ｘが登録されている。
図２５に示すように、Ｆｕｎｃ＿Ａ＿ｙの中の呼び出し先関数はＦｕｎｃ＿Ｂ＿ｙおよびＦｕｎｃ＿Ｃ＿ｙである。そのため、図２６に示すように、Ｆｕｎｃ＿Ａに対応する変更後ソースコードの欄において、呼び出し先関数の欄にＦｕｎｃ＿Ｂ＿ｙおよびＦｕｎｃ＿Ｃ＿ｙが登録されている。
図２５に示すように、Ｆｕｎｃ＿Ｂ＿ｙに対応する分岐箇所識別子はｃｏｕｎｔ８＿ｙであり、Ｆｕｎｃ＿Ｃ＿ｙに対応する分岐箇所識別子はｃｏｕｎｔ９＿ｙである。そのため、図２６に示すように、Ｆｕｎｃ＿Ｂに対応する変更後ソースコードの欄において、分岐箇所識別子の欄にｃｏｕｎｔ８＿ｙが登録されている。さらに、Ｆｕｎｃ＿Ｃに対応する変更後ソースコードの欄において、分岐箇所識別子の欄にｃｏｕｎｔ９＿ｙが登録されている。
【０１０２】
図２７に、ステップＳ２２１（図２１参照）の後の検証ファイル２５０を示す。
検証ファイル２５０は、呼び出し文２５２の後に第１除外制御文２５５を含んでいる。さらに、検証ファイル２５０は、呼び出し文２５３の後に第１除外制御文２５６を含んでいる。
第１除外制御文２５５により、ｃｏｕｎｔ１０＿ｘの値が更新前の値と一致するか判定される。ｃｏｕｎｔ１０＿ｘは、Ｆｕｎｃ＿Ｃ＿ｘの分岐箇所識別子である（図２６参照）。Ｆｕｎｃ＿Ｃ＿ｘは、Ｆｕｎｃ＿Ａ＿ｘの呼び出し先関数であり（図２６参照）、不等価関数である（図２３参照）。
第１除外制御文２５６により、ｃｏｕｎｔ９＿ｙの値が更新前の値と一致するか判定される。ｃｏｕｎｔ９＿ｙは、Ｆｕｎｃ＿Ｃ＿ｙの分岐箇所識別子である（図２６参照）。Ｆｕｎｃ＿Ｃ＿ｙは、Ｆｕｎｃ＿Ａ＿ｙの呼び出し先関数であり（図２６参照）、不等価関数である（図２３参照）。
【０１０３】
ステップＳ２２２（図２１参照）において、部分検証部１６０は、対象関数が部分等価関数を呼び出す関数であるか判定する。
Ｆｕｎｃ＿Ａ＿ｘの呼び出し先関数はＦｕｎｃ＿Ｂ＿ｘおよびＦｕｎｃ＿Ｃ＿ｘである（図２６参照）。Ｆｕｎｃ＿Ｂ＿ｘの等価性は部分等価である（図２３参照）。そのため、Ｆｕｎｃ＿Ａ＿ｘは部分等価関数を呼び出す関数である。
Ｆｕｎｃ＿Ａ＿ｙの呼び出し先関数はＦｕｎｃ＿Ｂ＿ｙおよびＦｕｎｃ＿Ｃ＿ｙである（図２６参照）。Ｆｕｎｃ＿Ｂ＿ｙの等価性も部分等価である（図２３参照）。そのため、Ｆｕｎｃ＿Ａ＿ｙは部分等価関数を呼び出す関数である。
したがって、対応組がＦｕｎｃ＿Ａ＿ｘとＦｕｎｃ＿Ａ＿ｙとを含んだ組である場合、処理はステップＳ２２３に進む。
【０１０４】
ステップＳ２２３（図２１参照）において、部分検証部１６０は、第２除外制御文を検証ファイルに追加する。
【０１０５】
図２８に、ステップＳ２２３（図２１参照）の後の検証ファイル２５０を示す。
検証ファイル２５０は、呼び出し文２５２の後に第２除外制御文２５７を含んでいる。さらに、検証ファイル２５０は、呼び出し文２５３の後に第２除外制御文２５８を含んでいる。
第２除外制御文２５７により、ｃｏｕｎｔ７＿ｘの値が更新前の値と一致するか判定される。ｃｏｕｎｔ７＿ｘは、Ｆｕｎｃ＿Ｅ＿ｘの分岐箇所識別子である（図２６参照）。Ｆｕｎｃ＿Ｅ＿ｘは、Ｆｕｎｃ＿Ｂ＿ｘの呼び出し先関数であり（図２６参照）、不等価関数である（図２３参照）。Ｆｕｎｃ＿Ｂ＿ｘは、Ｆｕｎｃ＿Ａ＿ｘの呼び出し先関数であり（図２６参照）、部分等価関数である（図２３参照）。第２不等価関数が呼ばれていた場合、ｃｏｕｎｔ７＿ｘの値は０から１に更新されている。このとき、ｃｏｕｎｔ７＿ｘの値は等価性判定範囲外（図２８参照）である。つまり、第２除外制御文２５７による判定結果は不一致である。そのため、ｃｏｕｎｔ７＿ｘに対応する入力は等価検証から除外される。
第２除外制御文２５８により、ｃｏｕｎｔ６＿ｙの値が更新前の値と一致するか判定される。ｃｏｕｎｔ６＿ｙは、Ｆｕｎｃ＿Ｅ＿ｙの分岐箇所識別子である（図２６参照）。Ｆｕｎｃ＿Ｅ＿ｙは、Ｆｕｎｃ＿Ｂ＿ｙの呼び出し先関数であり（図２６参照）、不等価関数である（図２３参照）。Ｆｕｎｃ＿Ｂ＿ｙは、Ｆｕｎｃ＿Ａ＿ｙの呼び出し先関数であり（図２６参照）、部分等価関数である（図２３参照）。第２不等価関数が呼ばれていた場合、ｃｏｕｎｔ６＿ｙの値は０から１に更新されている。このとき、ｃｏｕｎｔ６＿ｙの値は等価性判定範囲外（図２８参照）である。つまり、第２除外制御文２５８による判定結果は不一致である。そのため、ｃｏｕｎｔ６＿ｙに対応する入力は等価検証から除外される。
【０１０６】
図２９に、等価性判定表２４０を示す。
図２９の等価性判定表２４０は、Ｆｕｎｃ＿Ａ＿ｘおよびＦｕｎｃ＿Ａ＿ｙが部分等価関数である場合の等価性判定表２４０である。
Ｆｕｎｃ＿Ａに対応する等価性の欄には部分等価が登録されている。
【０１０７】
Ｆｕｎｃ＿Ａ＿ｘの第１不等価関数はＦｕｎｃ＿Ｃ＿ｘである（図２６および図２３参照）。Ｆｕｎｃ＿Ｃ＿ｘの分岐箇所識別子はｃｏｕｎｔ１０＿ｘである（図２６参照）。そのため、Ｆｕｎｃ＿Ａに対応する変更前ソースコードの欄にはｃｏｕｎｔ１０＿ｘが登録されている。
Ｆｕｎｃ＿Ａ＿ｘの第２不等価関数はＦｕｎｃ＿Ｅ＿ｘである（図２６および図２３参照）。Ｆｕｎｃ＿Ｅ＿ｘの分岐箇所識別子はｃｏｕｎｔ７＿ｘである（図２６参照）。そのため、Ｆｕｎｃ＿Ａに対応する変更前ソースコードの欄にはｃｏｕｎｔ７＿ｘが登録されている。
同様に、Ｆｕｎｃ＿Ａに対応する変更後ソースコードの欄には、ｃｏｕｎｔ９＿ｙおよびｃｏｕｎｔ６＿ｙが登録されている。
【０１０８】
＊＊＊実施の形態１の効果＊＊＊
等価性検証装置１００は、対象関数内の呼び出し先関数の等価性結果を利用して、不等価な呼び出し先関数を通過するパスを除外した状態で等価性検証を行う。これにより、不等価でないと判定される範囲が拡大される。その結果、不等価な原因、つまり、不具合の原因を解析するための範囲が狭まり、人手による解析時間が短縮される。
【０１０９】
実施の形態２．
始点関数から終点関数までの呼び出しパスが不等価パスであるか判定するための形態について、主に実施の形態１と異なる点を図３０から図３４に基づいて説明する。
【０１１０】
＊＊＊構成の説明＊＊＊
図３０に基づいて、等価性検証装置１００の構成を説明する。
等価性検証装置１００は、コールグラフ生成部１１０と制御部１２０と等価性検証部１３０と識別子設定部１４０と部分検証判定部１５０と部分検証部１６０との他に、パス検証部１７０をソフトウェア要素として備える。
等価性検証プログラムは、コールグラフ生成部１１０と制御部１２０と等価性検証部１３０と識別子設定部１４０と部分検証判定部１５０と部分検証部１６０とパス検証部１７０としてコンピュータを機能させる。
【０１１１】
＊＊＊動作の説明＊＊＊
図３１に基づいて、パス検証方法を説明する。
パス検証方法は、変更前ソースコードと変更後ソースコードとの一方を対象にして行われる。以下、変更後ソースコードを対象として、パス検証方法を説明する。
【０１１２】
ステップＳ３０１において、受付部１９２は、始点関数識別子と終点関数識別子とを受け付ける。
始点関数識別子は、始点関数として指定された関数の識別子である。
終点関数識別子は、終点関数として指定された関数の識別子である。
始点関数から終点関数までのパスを呼び出しパスという。
呼び出しパスは、始点関数から終点関数までの関数の呼び出し順を示す。
【０１１３】
例えば、始点関数識別子および終点関数識別子は以下のような手順で受け付けられる。
まず、パス検証部１７０は、変更後コールグラフ２３２を入力としてＧｒａｐｈｖｉｚを実行することによって、コールグラフ図を生成する。
Ｇｒａｐｈｖｉｚは、コールグラフ図を生成するためのツールである。
コールグラフ図は、コールグラフが示す呼び出し関係を表す図である。
次に、表示部１９３は、コールグラフ図をディスプレイに表示する。
次に、検証者は、コールグラフ図を参照し、始点関数と終点関数とを決定し、始点関数識別子と終点関数識別子とを等価性検証装置１００に入力する。終点関数識別子の入力が省略された場合、末端の関数の識別子が終点関数識別子として入力されたものとする。
そして、受付部１９２は、入力された始点関数識別子と終点関数識別子とを受け付ける。
【０１１４】
図３２に、コールグラフ図２７０を示す。
コールグラフ図２７０は、図６の変更後コールグラフ２３２に対応するコールグラフ図である。
【０１１５】
図３１に戻り、ステップＳ３１０から説明を続ける。
ステップＳ３１０において、パス検証部１７０は、呼び出しパス毎に第３分岐箇所識別子を抽出する。
第３分岐箇所識別子は、呼び出しパスに含まれる呼び出し先関数の分岐箇所識別子である。呼び出し先関数の分岐箇所識別子は、呼び出し先関数が呼び出される箇所に対応する分岐箇所識別子である。
【０１１６】
図３３に基づいて、第３分岐箇所識別子の抽出（Ｓ３１０）を説明する。
ステップＳ３１１において、パス検証部１７０は、始点関数から順に関数を１つ選択する。
ステップＳ３１２からステップＳ３１５までの説明において、対象関数は、ステップＳ３１１で選択された関数を意味する。
【０１１７】
ステップＳ３１２において、パス検証部１７０は、対象関数が複数の呼び出し先関数を呼び出す関数であるか判定する。
【０１１８】
具体的には、パス検証部１７０は、識別子対応表２６０を用いて以下のように判定を行う。
まず、パス検証部１７０は、識別子対応表２６０を参照し、対象関数に対応付けられた呼び出し先関数の数を数える。
そして、パス検証部１７０は、対象関数に対応付けられた呼び出し先関数の数が２以上であるか判定する。
対象関数に対応付けられた呼び出し先関数の数が２以上である場合、対象関数が複数の呼び出し先関数を呼び出す関数である。
【０１１９】
対象関数が複数の呼び出し先関数を呼び出す関数である場合、処理はステップＳ３１３に進む。
対象関数が複数の呼び出し先関数を呼び出す関数ではない場合、処理はステップＳ３１６に進む。
【０１２０】
図２６の識別子対応表２６０において、Ｆｕｎｃ＿Ａ＿ｙに対応する呼び出し先関数は、Ｆｕｎｃ＿Ｂ＿ｙとＦｕｎｃ＿Ｃ＿ｙとの２つである。
したがって、対象関数がＦｕｎｃ＿Ａ＿ｙである場合、処理はステップＳ３１３に進む。
【０１２１】
ステップＳ３１３において、パス検証部１７０は、複数の呼び出し先関数に対応する複数の第３分岐箇所識別子が全て同じであるか判定する。
【０１２２】
具体的には、パス検証部１７０は、識別子対応表２６０を用いて以下のように判定を行う。
まず、パス検証部１７０は、呼び出し先関数毎に呼び出し先関数に対応する分岐箇所識別子を識別子対応表２６０から抽出する。
そして、パス検証部１７０は、抽出された全ての分岐箇所識別子が同じであるか判定する。
【０１２３】
複数の呼び出し先関数に対応する複数の分岐箇所識別子が全て同じである場合、処理はステップＳ３１６に進む。
複数の呼び出し先関数に対応する複数の分岐箇所識別子の少なくともいずれかが他の分岐箇所識別子と異なる場合、処理はステップＳ３１４に進む。
【０１２４】
図２６の識別子対応表２６０において、Ｆｕｎｃ＿Ｂ＿ｙの分岐箇所識別子はｃｏｕｎｔ８＿ｙであり、Ｆｕｎｃ＿Ｃ＿ｙの分岐箇所識別子はｃｏｕｎｔ９＿ｙである。
したがって、複数の呼び出し先関数がＦｕｎｃ＿Ｂ＿ｙおよびＦｕｎｃ＿Ｃ＿ｙである場合、処理はステップＳ３１４に進む。
【０１２５】
ステップＳ３１４において、パス検証部１７０は、複数の呼び出しパスをパス判定表に登録する。
パス判定表は、呼び出しパス毎の等価性および第３分岐箇所識別子を管理するためのデータである。
【０１２６】
具体的には、パス検証部１７０は複数の呼び出しパスを以下のように登録する。
パス検証部１７０は、対象関数を含んだ呼び出しパスがパス判定表に登録されているか判定する。
対象関数を含んだ呼び出しパスがパス判定表に登録されている場合、パス検証部１７０は、対象関数を含んだ呼び出しパスを複製することによって、複数の呼び出し先関数と同じ数の呼び出しパスをパス判定表に登録する。そして、パス検証部１７０は、それぞれの呼び出しパスに異なる呼び出し先関数を登録する。
対象関数を含んだ呼び出しパスがパス判定表に登録されていない場合、パス検証部１７０は、呼び出し先関数毎に対象関数と呼び出し先関数とを示す呼び出しパスをパス判定表に登録する。そして、パス検証部１７０は、それぞれの呼び出しパスに異なる呼び出し先関数を登録する。
【０１２７】
ステップＳ３１５において、パス検証部１７０は、複数の分岐箇所識別子をパス判定表に登録する。登録される複数の分岐箇所識別子のそれぞれが第３分岐箇所識別子である。
具体的には、パス検証部１７０は、ステップＳ３１４で登録された呼び出しパス毎に、呼び出し先関数の分岐箇所識別子を識別子対応表２６０から抽出し、抽出された分岐箇所識別子をパス検証部１７０に登録する。
【０１２８】
ステップＳ３１６において、パス検証部１７０は、未選択の関数が有るか判定する。
未選択の関数が有る場合、処理はステップＳ３１１に進む。
未選択の関数が無い場合、第３分岐箇所識別子の抽出（Ｓ３１０）は終了する。
【０１２９】
図３４に、パス判定表２８０を示す。
図３４のパス判定表２８０は、図３２のコールグラフ図２７０に対応するパス判定表であり、ステップＳ３１０（図３１参照）の後のパス判定表である。
始点関数は、Ｆｕｎｃ＿Ａ＿ｙであり、終点関数はＦｕｎｃ＿Ｃ＿Ｙ、Ｆｕｎｃ＿Ｄ＿ＹおよびＦｕｎｃ＿Ｅ＿Ｙである。
Ｎｏ．１の呼び出しパスにおける呼び出し先関数はＦｕｎｃ＿Ｂ＿ｙおよびＦｕｎｃ＿Ｄ＿ｙである。Ｆｕｎｃ＿Ｂ＿ｙの分岐箇所識別子はｃｏｕｎｔ８＿ｙであり、ＦｕｎｃＤ＿ｙの分岐箇所識別子はｃｏｕｎｔ５＿ｙである（図２６参照）。したがって、Ｎｏ．１の呼び出しパスの第３分岐箇所識別子はｃｏｕｎｔ８＿ｙおよびｃｏｕｎｔ５＿ｙである。
Ｎｏ．２の呼び出しパスにおける呼び出し先関数はＦｕｎｃ＿Ｂ＿ｙおよびＦｕｎｃ＿Ｅ＿ｙである。Ｆｕｎｃ＿Ｂ＿ｙの分岐箇所識別子はｃｏｕｎｔ８＿ｙであり、ＦｕｎｃＥ＿ｙの分岐箇所識別子はｃｏｕｎｔ６＿ｙである（図２６参照）。したがって、Ｎｏ．２の呼び出しパスの第３分岐箇所識別子はｃｏｕｎｔ８＿ｙおよびｃｏｕｎｔ６＿ｙである。
Ｎｏ．３の呼び出しパスにおける呼び出し先関数はＦｕｎｃ＿Ｃ＿ｙである。Ｆｕｎｃ＿Ｃ＿ｙの分岐箇所識別子はｃｏｕｎｔ９＿ｙである（図２６参照）。したがって、Ｎｏ．３の呼び出しパスの第３分岐箇所識別子はｃｏｕｎｔ９＿ｙである。
【０１３０】
図３１に戻り、ステップＳ３２１から説明を続ける。
ステップＳ３２１において、パス検証部１７０は、未選択の呼び出しパスを１つ選択する。
ステップＳ３２２からステップＳ３２４までの説明において、呼び出しパスは、ステップＳ３２１で選択された呼び出しパスを意味する。
【０１３１】
ステップＳ３２２において、パス検証部１７０は、呼び出しパスの第３分岐箇所識別子の少なくともいずれかが、始点関数の第１分岐箇所識別子と始点関数の第２分岐箇所識別子とのいずれかと一致するか判定する。
【０１３２】
具体的には、パス検証部１７０は以下のように判定を行う。
まず、パス検証部１７０は、呼び出しパスの第３分岐箇所識別子をパス判定表２８０の中の分岐箇所識別子の欄から抽出する。
次に、パス検証部１７０は、始点関数の第１分岐箇所識別子と始点関数の第２分岐箇所識別子とを等価性判定表２４０の中の変更後ソースコードの欄から抽出する。
次に、パス検証部１７０は、呼び出しパスの第３分岐箇所識別子毎に第３分岐箇所識別子を始点関数の第１分岐箇所識別子と始点関数の第２分岐箇所識別子とのそれぞれと比較する。
そして、パス検証部１７０は、比較結果に基づいて、呼び出しパスの第３分岐箇所識別子の少なくともいずれかが、始点関数の第１分岐箇所識別子と始点関数の第２分岐箇所識別子とのいずれかと一致するか判定する。
【０１３３】
呼び出しパスの第３分岐箇所識別子の少なくともいずれかが、始点関数の第１分岐箇所識別子と始点関数の第２分岐箇所識別子とのいずれかと一致するか場合、処理はステップＳ３２３に進む。
呼び出しパスの全ての第３分岐箇所識別子が、始点関数の第１分岐箇所識別子と始点関数の第２分岐箇所識別子とのいずれとも一致しない場合、処理はステップＳ３２４に進む。
【０１３４】
図３４のパス判定表２８０において、Ｎｏ．１の呼び出しパスの第３分岐箇所識別子はｃｏｕｎｔ８＿ｙおよびｃｏｕｎｔ５＿ｙである。
始点関数であるＦｕｎｃ＿Ａ＿ｙの第１分岐箇所識別子および第２分岐箇所識別子は、ｃｏｕｎｔ６＿ｙおよびｃｏｕｎｔ９＿ｙである（図２９参照）。
この場合、全ての第３分岐箇所識別子が第１分岐箇所識別子と第２分岐箇所識別子とのいずれとも一致しないため、処理はステップＳ３２４に進む。
【０１３５】
図３４のパス判定表２８０において、Ｎｏ．２の呼び出しパスの第３分岐箇所識別子はｃｏｕｎｔ８＿ｙおよびｃｏｕｎｔ６＿ｙである。
始点関数であるＦｕｎｃ＿Ａ＿ｙの第１分岐箇所識別子および第２分岐箇所識別子は、ｃｏｕｎｔ６＿ｙおよびｃｏｕｎｔ９＿ｙである（図２９参照）。
この場合、第３分岐箇所識別子と第１分岐箇所識別子との間でｃｏｕｎｔ６＿ｙが共通するため、処理はステップＳ３２３に進む。
【０１３６】
図３４のパス判定表２８０において、Ｎｏ．３の呼び出しパスの第３分岐箇所識別子はｃｏｕｎｔ９＿ｙである。
始点関数であるＦｕｎｃ＿Ａ＿ｙの第１分岐箇所識別子および第２分岐箇所識別子は、ｃｏｕｎｔ６＿ｙおよびｃｏｕｎｔ９＿ｙである（図２９参照）。
この場合、第３分岐箇所識別子と第２分岐箇所識別子との間でｃｏｕｎｔ９＿ｙが共通するため、処理はステップＳ３２３に進む。
【０１３７】
ステップＳ３２３において、パス検証部１７０は、呼び出しパスをパス判定表に不等価パスとして登録する。
【０１３８】
ステップＳ３２４において、パス検証部１７０は、呼び出しパスをパス判定表に等価パスとして登録する。
【０１３９】
ステップＳ３２５において、パス検証部１７０は、未選択の呼び出しパスが有るか判定する。
未選択の呼び出しパスが有る場合、処理はステップＳ３２１に進む。
未選択の呼び出しパスが無い場合、パス検証方法の処理は終了する。
【０１４０】
図３５に、パス検証方法によって得られるパス判定表２８０を示す。
パス判定表２８０において、Ｎｏ．１の呼び出しパスは不等価関数が呼び出されない等価パスであり、Ｎｏ．２の呼び出しパスおよびＮｏ．３の呼び出しパスは不等価関数が呼び出される不等価パスである。
【０１４１】
＊＊＊実施の形態２の効果＊＊＊
実施の形態１の結果を利用して呼び出しパスの等価性を検証することができる。これにより、不等価でないと判定されるパス（等価パス）の範囲が拡大される。その結果、例えば、等価パスにおいて機能テストケースの生成および出力期待値の指定を省略することが可能となる。そして、検証に要する工数が削減される。
【０１４２】
＊＊＊実施の形態の補足＊＊＊
実施の形態において、等価性検証装置１００の機能はハードウェアで実現してもよい。
図３６に、等価性検証装置１００の機能がハードウェアで実現される場合の構成を示す。
等価性検証装置１００は処理回路９９０を備える。処理回路９９０はプロセッシングサーキットリともいう。
処理回路９９０は、コールグラフ生成部１１０と制御部１２０と等価性検証部１３０と識別子設定部１４０と部分検証判定部１５０と部分検証部１６０とパス検証部１７０と記憶部１９１とを実現する専用の電子回路である。
例えば、処理回路９９０は、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ロジックＩＣ、ＧＡ、ＡＳＩＣ、ＦＰＧＡまたはこれらの組み合わせである。ＧＡはＧａｔｅ  Ａｒｒａｙの略称であり、ＡＳＩＣはＡｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔの略称であり、ＦＰＧＡはＦｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙの略称である。
【０１４３】
等価性検証装置１００は、処理回路９９０を代替する複数の処理回路を備えてもよい。複数の処理回路は、処理回路９９０の役割を分担する。
【０１４４】
実施の形態は、好ましい形態の例示であり、本発明の技術的範囲を制限することを意図するものではない。実施の形態は、部分的に実施してもよいし、他の形態と組み合わせて実施してもよい。フローチャート等を用いて説明した手順は、適宜に変更してもよい。
【符号の説明】
【０１４５】
１００  等価性検証装置、１１０  コールグラフ生成部、１２０  制御部、１３０  等価性検証部、１４０  識別子設定部、１５０  部分検証判定部、１６０  部分検証部、１７０  パス検証部、１９１  記憶部、１９２  受付部、１９３  表示部、２１０  変更前ソースコード、２１１〜２１９  更新文、２１１０  更新文、２２０  変更後ソースコード、２２１〜２２９  更新文、２３１  変更前コールグラフ、２３２  変更後コールグラフ、２３３  関数対応表、２４０  等価性判定表、２５０  検証ファイル、２５１  入力一致文、２５２  呼び出し文、２５３  呼び出し文、２５４  出力一致文、２５５  第１除外制御文、２５６  第１除外制御文、２５７  第２除外制御文、２５８  第２除外制御文、２６０  識別子対応表、２７０  コールグラフ図、２８０  パス判定表、９０１  プロセッサ、９０２  メモリ、９０３  補助記憶装置、９０４  入出力インタフェース、９９０  処理回路。
【図１】
0006567212.tif 000002
【図２】
0006567212.tif 000003
【図３】
0006567212.tif 000004
【図４】
0006567212.tif 000005
【図５】
0006567212.tif 000006
【図６】
0006567212.tif 000007
【図７】
0006567212.tif 000008
【図８】
0006567212.tif 000009
【図９】
0006567212.tif 000010
【図１０】
0006567212.tif 000011
【図１１】
0006567212.tif 000012
【図１２】
0006567212.tif 000013
【図１３】
0006567212.tif 000014
【図１４】
0006567212.tif 000015
【図１５】
0006567212.tif 000016
【図１６】
0006567212.tif 000017
【図１７】
0006567212.tif 000018
【図１８】
0006567212.tif 000019
【図１９】
0006567212.tif 000020
【図２０】
0006567212.tif 000021
【図２１】
0006567212.tif 000022
【図２２】
0006567212.tif 000023
【図２３】
0006567212.tif 000024
【図２４】
0006567212.tif 000025
【図２５】
0006567212.tif 000026
【図２６】
0006567212.tif 000027
【図２７】
0006567212.tif 000028
【図２８】
0006567212.tif 000029
【図２９】
0006567212.tif 000030
【図３０】
0006567212.tif 000031
【図３１】
0006567212.tif 000032
【図３２】
0006567212.tif 000033
【図３３】
0006567212.tif 000034
【図３４】
0006567212.tif 000035
【図３５】
0006567212.tif 000036
【図３６】
0006567212.tif 000037