図面 (/)

技術 解析プログラム、解析方法および解析装置

出願人 富士通株式会社
発明者 徳本晋吉田浩章
出願日 2016年10月14日 (4年1ヶ月経過) 出願番号 2016-203134
公開日 2017年8月3日 (3年3ヶ月経過) 公開番号 2017-134815
状態 特許登録済
技術分野 ストアードプログラム デバッグ/監視
主要キーワード 評価指示 分割実行 グループ解除 状態分割 二項演算 モニタ対象 媒体アクセス装置 ソースコード群
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2017年8月3日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (20)

課題

解決手段

解析プログラムは、次の各処理をコンピュータに実行させる。コンピュータは、ソースコード内の要素をメタ関数置換した中間コードを実行する際に、ミューテーション記述子集合を保持する。コンピュータは、各記述子の命令を評価する。コンピュータは、記述子の集合のうち、命令の評価結果が同じとなる1つ以上の記述子を選択する。コンピュータは、選択された記述子と、ミューテーション演算または第1のステートとの直積を算出して第2のステートを生成する。コンピュータは、生成された第2のステートを評価する際に、該グループ内の各第2のステートに対して並列に命令を評価する。コンピュータは、命令の評価結果に基づく第3のステートのうち、該評価結果が同じとなる第3のステートをマージする。

概要

背景

従来、ソフトウェアテストを評価する方法として、プログラムの1要素を変化させることでバグを埋め込み、テストによって埋め込んだバグをどれだけ検出できるかを調べるミューテーション解析という方法がある。ミューテーション解析では、要素を変化させたものであるミュータント網羅的に生成するために、ミューテーションを行ったソースコードをそれぞれコンパイルして実行するので、処理に時間がかかっていた。このため、要素を複数のミュータントに置き換えてミューテーションを行うことに代えて、パラメータを与えることで具体的なミュータントを表す関数であるメタ関数に置き換えることで、コンパイルのコストを抑えることが提案されている。

また、要素をそれぞれのミュータントに置き換えた状態(以下、ステートともいう。)を分割しながら実行することで、計算コストを低減させることが、論文(K. N. King and J. Offutt, "A Fortran Language System for Mutation-Based Software Testing", Software-Practice and Experience,1991.)により提案されている。

また、ミュータントの実行結果が元の実行結果と同じものを除去し、さらに、同じ実行結果となるミュータントをまとめることで、計算コストを低減させることが、論文(Rene Just, et al., Efficient mutation analysis by propagating and partitioning infected execution states. ISSTA2014)により提案されている。

概要

高次ミューテーションの状態数を削減できる解析プログラム解析方法および解析装置を提供する。解析プログラムは、次の各処理をコンピュータに実行させる。コンピュータは、ソースコード内の要素をメタ関数に置換した中間コードを実行する際に、ミューテーション記述子集合を保持する。コンピュータは、各記述子の命令を評価する。コンピュータは、記述子の集合のうち、命令の評価結果が同じとなる1つ以上の記述子を選択する。コンピュータは、選択された記述子と、ミューテーション演算または第1のステートとの直積を算出して第2のステートを生成する。コンピュータは、生成された第2のステートを評価する際に、該グループ内の各第2のステートに対して並列に命令を評価する。コンピュータは、命令の評価結果に基づく第3のステートのうち、該評価結果が同じとなる第3のステートをマージする。

目的

本発明は、高次ミューテーションの状態数を削減できる解析プログラム、解析方法および解析装置を提供する

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

ソースコード内の要素をミュータントに変化させるメタ関数置換してコンパイルした中間コードを実行する際に、前記メタ関数に対応するミューテーション演算について、前記ミュータントの変化を示すミューテーション記述子集合を保持し、前記ミューテーション記述子それぞれの命令を評価し、前記ミューテーション記述子の集合のうち、前記命令の評価結果が同じとなる1つ以上の前記ミューテーション記述子を選択し、前記選択された前記ミューテーション記述子と、前記ミューテーション演算、または、前記命令の評価前の前記ミューテーション記述子の集合である第1のステートとの直積を算出して第2のステートを生成し、生成された前記第2のステートの前記ミューテーション記述子それぞれの命令を評価する際に、前記第2のステートが複数ある場合には、当該複数の前記第2のステートを1つのグループとして、該グループ内の前記第2のステートそれぞれに対して並列に前記命令を評価し、前記グループ内における前記命令の評価結果に基づく第3のステートのうち、該評価結果が同じとなる前記第3のステートをマージする、処理をコンピュータに実行させることを特徴とする解析プログラム

請求項2

前記マージする処理は、副作用がない前記命令が続く間、前記グループ内で前記第3のステートをマージする、ことを特徴とする請求項1に記載の解析プログラム。

請求項3

前記並列に前記命令を評価する処理は、副作用がない前記命令以外の命令に到達すると、前記グループを解消して前記第2のステートの前記命令を評価する、ことを特徴とする請求項1または2に記載の解析プログラム。

請求項4

前記マージする処理は、前記マージを行うことで、前記第1のステートまたは前記第2のステートに戻る場合には、前記マージを行わない、ことを特徴とする請求項1〜3のいずれか1つに記載の解析プログラム。

請求項5

ソースコード内の要素をミュータントに変化させるメタ関数に置換してコンパイルした中間コードを実行する際に、前記メタ関数に対応するミューテーション演算について、前記ミュータントの変化を示すミューテーション記述子の集合を保持し、前記ミューテーション記述子それぞれの命令を評価し、前記ミューテーション記述子の集合のうち、前記命令の評価結果が同じとなる1つ以上の前記ミューテーション記述子を選択し、前記選択された前記ミューテーション記述子と、前記ミューテーション演算、または、前記命令の評価前の前記ミューテーション記述子の集合である第1のステートとの直積を算出して第2のステートを生成し、生成された前記第2のステートの前記ミューテーション記述子それぞれの命令を評価する際に、前記第2のステートが複数ある場合には、当該複数の前記第2のステートを1つのグループとして、該グループ内の前記第2のステートそれぞれに対して並列に前記命令を評価し、前記グループ内における前記命令の評価結果に基づく第3のステートのうち、該評価結果が同じとなる前記第3のステートをマージする、処理をコンピュータが実行することを特徴とする解析方法

請求項6

前記マージする処理は、副作用がない前記命令が続く間、前記グループ内で前記第3のステートをマージする、ことを特徴とする請求項5に記載の解析方法。

請求項7

前記並列に前記命令を評価する処理は、副作用がない前記命令以外の命令に到達すると、前記グループを解消して前記第2のステートの前記命令を評価する、ことを特徴とする請求項5または6に記載の解析方法。

請求項8

前記マージする処理は、前記マージを行うことで、前記第1のステートまたは前記第2のステートに戻る場合には、前記マージを行わない、ことを特徴とする請求項5〜7のいずれか1つに記載の解析方法。

請求項9

ソースコード内の要素をミュータントに変化させるメタ関数に置換してコンパイルした中間コードを実行する際に、前記メタ関数に対応するミューテーション演算について、前記ミュータントの変化を示すミューテーション記述子の集合を管理する管理部と、前記ミューテーション記述子それぞれの命令を評価する第1評価部と、前記ミューテーション記述子の集合のうち、前記命令の評価結果が同じとなる1つ以上の前記ミューテーション記述子を選択する選択部と、前記選択された前記ミューテーション記述子と、前記ミューテーション演算、または、前記命令の評価前の前記ミューテーション記述子の集合である第1のステートとの直積を算出して第2のステートを生成する生成部と、生成された前記第2のステートの前記ミューテーション記述子それぞれの命令を評価する際に、前記第2のステートが複数ある場合には、当該複数の前記第2のステートを1つのグループとして、該グループ内の前記第2のステートそれぞれに対して並列に前記命令を評価する第2評価部と、前記グループ内における前記命令の評価結果に基づく第3のステートのうち、該評価結果が同じとなる前記第3のステートをマージするマージ部と、を有することを特徴とする解析装置

請求項10

前記マージ部は、副作用がない前記命令が続く間、前記グループ内で前記第3のステートをマージする、ことを特徴とする請求項9に記載の解析装置。

請求項11

前記第2評価部は、副作用がない前記命令以外の命令に到達すると、前記グループを解消して前記第2のステートの前記命令を評価する、ことを特徴とする請求項9または10に記載の解析装置。

請求項12

前記マージ部は、前記マージを行うことで、前記第1のステートまたは前記第2のステートに戻る場合には、前記マージを行わない、ことを特徴とする請求項9〜11のいずれか1つに記載の解析装置。

技術分野

0001

本発明は、解析プログラム解析方法および解析装置に関する。

背景技術

0002

従来、ソフトウェアテストを評価する方法として、プログラムの1要素を変化させることでバグを埋め込み、テストによって埋め込んだバグをどれだけ検出できるかを調べるミューテーション解析という方法がある。ミューテーション解析では、要素を変化させたものであるミュータント網羅的に生成するために、ミューテーションを行ったソースコードをそれぞれコンパイルして実行するので、処理に時間がかかっていた。このため、要素を複数のミュータントに置き換えてミューテーションを行うことに代えて、パラメータを与えることで具体的なミュータントを表す関数であるメタ関数に置き換えることで、コンパイルのコストを抑えることが提案されている。

0003

また、要素をそれぞれのミュータントに置き換えた状態(以下、ステートともいう。)を分割しながら実行することで、計算コストを低減させることが、論文(K. N. King and J. Offutt, "A Fortran Language System for Mutation-Based Software Testing", Software-Practice and Experience,1991.)により提案されている。

0004

また、ミュータントの実行結果が元の実行結果と同じものを除去し、さらに、同じ実行結果となるミュータントをまとめることで、計算コストを低減させることが、論文(Rene Just, et al., Efficient mutation analysis by propagating and partitioning infected execution states. ISSTA2014)により提案されている。

先行技術

0005

特開2009−181549号公報
特開平8−044590号公報

発明が解決しようとする課題

0006

しかしながら、同じ実行結果となるミュータントをまとめる場合に、ミュータントの実行のパスが元の実行のパスと変わる可能性がある。このため、例えば、ループを複数回実行したときに状態が等価であるか否かは、ミュータントを実行しないとわからないこととなる。すなわち、同じ実行結果となるミュータントをまとめることができない場合があるため、高次ミューテーション(Higher order mutation)の状態数を削減することが困難である。

0007

一つの側面では、本発明は、高次ミューテーションの状態数を削減できる解析プログラム、解析方法および解析装置を提供することにある。

課題を解決するための手段

0008

一つの態様では、記録媒体に記録された解析プログラムは、ソースコード内の要素をミュータントに変化させるメタ関数に置換してコンパイルした中間コードを実行する際に、前記メタ関数に対応するミューテーション演算について、前記ミュータントの変化を示すミューテーション記述子集合を保持する処理をコンピュータに実行させる。解析プログラムは、前記ミューテーション記述子それぞれの命令を評価する処理をコンピュータに実行させる。解析プログラムは、前記ミューテーション記述子の集合のうち、前記命令の評価結果が同じとなる1つ以上の前記ミューテーション記述子を選択する処理をコンピュータに実行させる。解析プログラムは、前記選択された前記ミューテーション記述子と、前記ミューテーション演算、または、前記命令の評価前の前記ミューテーション記述子の集合である第1のステートとの直積を算出して第2のステートを生成する処理をコンピュータに実行させる。解析プログラムは、生成された前記第2のステートの前記ミューテーション記述子それぞれの命令を評価する際に、前記第2のステートが複数ある場合には、当該複数の前記第2のステートを1つのグループとして、該グループ内の前記第2のステートそれぞれに対して並列に前記命令を評価する処理をコンピュータに実行させる。解析プログラムは、前記グループ内における前記命令の評価結果に基づく第3のステートのうち、該評価結果が同じとなる前記第3のステートをマージする処理をコンピュータに実行させる。

発明の効果

0009

高次ミューテーションの状態数を削減できる。

図面の簡単な説明

0010

図1は、実施例の解析装置の構成の一例を示すブロック図である。
図2は、ミューテーション解析の一例を説明する図である。
図3は、ミューテーション解析の実行コストの一例を説明する図である。
図4は、状態を分割しながら実行する方法の一例を説明する図である。
図5は、計算コストを削減する方法の一例を説明する図である。
図6は、ミューテーション箇所の置き換えの一例を説明する図である。
図7は、ミュータント解析の一例を説明する図である。
図8は、同じ実行結果となるミュータントをまとめることができない場合の一例を説明する図である。
図9は、命令記憶部の一例を示す図である。
図10は、評価結果記憶部の一例を示す図である。
図11は、実行状態集合記憶部の一例を示す図である。
図12は、テスト結果記憶部の一例を示す図である。
図13は、テスト対象のソースコードの一例を示す図である。
図14は、メタ関数を埋め込んだソースコードの一例を示す図である。
図15は、中間コードの一例を示す図である。
図16は、テスト項目の一例を示す図である。
図17は、ミューテーションオペレータリストの一例を示す図である。
図18は、実施例の解析処理の一例を示すフローチャートである。
図19は、ステート選択処理の一例を示すフローチャートである。
図20は、ステート分割処理の一例を示すフローチャートである。
図21は、ステートマージ処理の一例を示すフローチャートである。
図22は、ステート完了チェック処理の一例を示すフローチャートである。
図23は、whileループの1回目の一例を説明する図である。
図24は、whileループの1回目の一例を説明する図である。
図25は、whileループの1回目の一例を説明する図である。
図26は、whileループの1回目の一例を説明する図である。
図27は、whileループの1回目の一例を説明する図である。
図28は、whileループの1回目の一例を説明する図である。
図29は、whileループの1回目の一例を説明する図である。
図30は、whileループの1回目の一例を説明する図である。
図31は、whileループの2回目の一例を説明する図である。
図32は、whileループの2回目の一例を説明する図である。
図33は、whileループの2回目の一例を説明する図である。
図34は、whileループの2回目の一例を説明する図である。
図35は、whileループの2回目の一例を説明する図である。
図36は、whileループの2回目の一例を説明する図である。
図37は、whileループの2回目の一例を説明する図である。
図38は、whileループの3回目の一例を説明する図である。
図39は、whileループの3回目の一例を説明する図である。
図40は、whileループの4回目の一例を説明する図である。
図41は、whileループの4回目の一例を説明する図である。
図42は、whileループの5回目の一例を説明する図である。
図43は、whileループの2回目の一例を説明する図である。
図44は、whileループの2回目の一例を説明する図である。
図45は、whileループの2回目の一例を説明する図である。
図46は、whileループの2回目の一例を説明する図である。
図47は、各ステートの割り振りの一例を説明する図である。
図48は、解析プログラムを実行するコンピュータの一例を示す図である。

0011

以下、図面に基づいて、本願の開示する解析プログラムを記録した記録媒体、解析方法および解析装置の実施例を詳細に説明する。なお、本実施例により、開示技術が限定されるものではない。また、以下の実施例は、矛盾しない範囲で適宜組みあわせてもよい。

0012

図1は、実施例の解析装置の構成の一例を示すブロック図である。図1に示す解析装置100は、ソースコード内の要素をミュータントに変化させるメタ関数に置換してコンパイルした中間コードを実行する際に、メタ関数に対応するミューテーション演算について、ミュータントの変化を示すミューテーション記述子の集合を保持する。解析装置100は、ミューテーション記述子それぞれの命令を評価する。解析装置100は、ミューテーション記述子の集合のうち、命令の評価結果が同じとなる1つ以上のミューテーション記述子を選択する。解析装置100は、選択されたミューテーション記述子と、ミューテーション演算、または、命令の評価前のミューテーション記述子の集合である第1のステートとの直積を算出して第2のステートを生成する。解析装置100は、生成された第2のステートのミューテーション記述子それぞれの命令を評価する際に、第2のステートが複数ある場合には、当該複数の第2のステートを1つのグループとして、該グループ内の第2のステートそれぞれに対して並列に命令を評価する。解析装置100は、グループ内における命令の評価結果に基づく第3のステートのうち、該評価結果が同じとなる第3のステートをマージする。これにより、解析装置100は、高次ミューテーションの状態数を削減できる。

0013

ここで、ミューテーション解析について説明する。図2は、ミューテーション解析の一例を説明する図である。図2に示すように、ミューテーション解析では、テスト対象プログラムであるソースコード10の要素に対して、ミューテーションが行われる。ソースコード10aは、例えば、ソースコード10に対して「mutant1」で示すミューテーションが行われたソースコードである。「mutant1」は、例えば、2行目の「<=」を「>」に変化させる。すなわち、ソースコード10aでは、ソースコード10と比べて、ミューテーション箇所11で示す部分が変化している。

0014

同様に、ソースコード10bは、例えば、ソースコード10に対して「mutant2」で示すミューテーションが行われたソースコードである。「mutant2」は、例えば、2行目の「0」を「1」に変化させる。すなわち、ソースコード10bでは、ソースコード10と比べて、ミューテーション箇所12で示す部分が変化している。同様に、ソースコード10cは、例えば、ソースコード10に対して「mutant3」で示すミューテーションが行われたソースコードである。「mutant3」は、例えば、3行目の「−」を「−−」に変化させる。すなわち、ソースコード10cでは、ソースコード10と比べて、ミューテーション箇所13で示す部分が変化している。

0015

これらのミューテーションされたソースコード10a〜10cに対して、あるテストを実行した結果がテスト結果14である。例えば「Test1」では、「abs」に「2」が入力されて「2」が出力されると「pass」とし、「2」以外が出力されると「fail」とする。また、例えば「Test2」では、「abs」に「−2」が入力されて「2」が出力されると「pass」とし、「2」以外が出力されると「fail」とする。このとき、「mutant1」〜「mutant3」のそれぞれの結果は、テスト結果14に示す通りとなる。

0016

「mutant1」は、「Test1」および「Test2」のいずれも「fail」となり、埋め込まれたバグを検出できるので「killed」となる。「mutant2」は、「Test1」および「Test2」のいずれも「pass」となり、埋め込まれたバグを検出できないので「unkilled」となる。「mutant3」は、「Test1」が「pass」、「Test2」が「fail」となり、埋め込まれたバグを検出できるので「killed」となる。この結果、「killed」となったミュータントの割合を示すミューテーションスコア(mutation score)は、2/3=0.667となる。

0017

次に、ミューテーション解析の実行コストについて説明する。図3は、ミューテーション解析の実行コストの一例を説明する図である。図3に示すように、ミューテーション解析では、ソースコード21をミューテーションしたソースコード群22を、それぞれコンパイルして実行ファイル群23を生成する。ミューテーション解析では、さらに、生成した実行ファイル群23についてテストを実行し、テスト結果群24を得る。このときのミューテーション解析の実行時間は、合計時間=(ミュータント数)×(ミューテーション時間+コンパイル時間)+(ミュータント数)×(テスト項目数)×(1回の実行時間)となる。すなわち、図3に示すミューテーション解析の実行時間は、ミュータントを網羅的に生成するため、多くの時間がかかってしまうことになる。

0018

これに対し、例えば、MSG(Mutant Schema Generation)は、ソースコードの要素を、パラメータを与えることで具体的なミュータントを表す関数であるメタ関数に置き換えることで、コンパイルのコストを抑える。また、要素をそれぞれのミュータントに置き換えたステートを分割しながら実行することで、計算コストを低減させる分割実行ストリーム(Split-Stream Execution)がある。

0019

図4は、状態を分割しながら実行する方法の一例を説明する図である。図4の例では、「%1=2+2」という命令26に対してミューテーションを行う。図4の例では、「State1」で示すステート25に対して命令26を実行する際に、演算子「+」をミューテーションさせる。図4の例では、「State1」で示すステート27a、「State2」で示すステート27b、「State3」で示すステート27c、「State4」で示すステート27d、および、「State5」で示すステート27eの5つに分割される。

0020

ステート27aは、命令26の演算子「+」をそのまま用いるので、命令26の計算結果は「%1=4」となる。ステート27aのミューテーション記述子28aは、「{}」となる。ステート27bは、命令26の演算子を「−」にミューテーションさせるので、命令26の計算結果は「%1=0」となる。ステート27bのミューテーション記述子28bは、「{(1,−)}」となる。なお、ミューテーション記述子28bは、ミューテーション箇所を示すミューテーションID(IDentifier)「1」と、変更内容「−」とのペアで表され、以下のミューテーション記述子においても同様である。

0021

ステート27cは、命令26の演算子を「*」にミューテーションさせるので、命令26の計算結果は「%1=4」となる。ステート27cのミューテーション記述子28cは、「{(1,*)}」となる。ステート27dは、命令26の演算子を「/」にミューテーションさせるので、命令26の計算結果は「%1=1」となる。ステート27dのミューテーション記述子28dは、「{(1,/)}」となる。ステート27eは、命令26の演算子を「%」にミューテーションさせるので、命令26の計算結果は「%1=0」となる。ステート27eのミューテーション記述子28eは、「{(1,%)}」となる。

0022

また、ミュータントの実行結果が元の実行結果と同じものを除去し、さらに、同じ実行結果となるミュータントをまとめる方法について、図5を用いて説明する。図5は、計算コストを削減する方法の一例を説明する図である。なお、図5の方法は、Mutants filtering with dynamic analysisという。図5の例では、インフェクション(Infection)29、プロパゲーション(Propagation)30およびパーティショニング(Partitioning)31の順番で計算コストを削減する。インフェクション29は、値が変化しない、つまり感染しないミュータントを除去する。図5の例では、テスト入力がa=2、b=2、c=0とすると、元の命令における式29aは、a+b=2+2=4となる。インフェクション29では、演算子「+」が「*」、「/」、「%」および「−」にミューテーションされると、演算子「*」にミューテーションされた式29bが式29aと同じ「4」となるので、演算子「*」のミュータントが除去される。

0023

続いて、プロパゲーション30は、伝染しないミュータントを除去する。図5の例では、元の命令における式30aは、a+b>c、つまり2+2>0となるので「true」となる。プロパゲーション30では、演算子「+」が「/」、「%」および「−」にミューテーションされた場合に、式30aが演算子「/」にミューテーションされた式30bを含むと、演算子「+」である式30aと同じ「true」となるので、演算子「/」のミュータントが除去される。

0024

次に、パーティショニング31は、同じ結果となるミュータントをまとめる。図5の例では、式30aは、演算子「+」が「%」および「−」にミューテーションされた場合に、どちらも「false」となるので、式31aと式31bとをまとめることができる。

0025

この図5の方法は、4ステップ実行手順を有する。4ステップの実行手順について、図6および図7を用いて説明する。図6は、ミューテーション箇所の置き換えの一例を説明する図である。図6に示すように、1つ目のステップは、対象プログラムのミューテーション箇所をevalメソッド呼出に置き換え、IDに基づく2つのマップを生成する。図6の例では、ミューテーション箇所を含む式32について、「a」をexpr1、「b」をexpr2、「a+b」をexpr3、「c」をexpr4、「a+b>c」をexpr5とする。

0026

式33は、ミューテーション箇所をevalメソッド呼出に置き換えた式である。表34は、expr3に対応するID「3e」、および、expr5に対応するID「5e」のそれぞれに含まれる要素を示す。表35は、どのようなミューテーションができるかを示す表、つまりモニタ対象を示す表であり、例えば、ID「1m」は、ID「3e」について「+」を「−」に変化させることを示す。また、例えば、ID「3m」は、ID「5e」について「>」を「>=」に変化させることを示す。

0027

図7は、ミュータント解析の一例を説明する図である。図7に示すように、2つ目のステップは、置換されたプログラムでテストを実行し、必要なミュータントを解析する。図7の例では、まず、式36について、モニタ対象のミュータントのうち「3e」が対象のものが解析される。解析結果37では、「2m」の結果が「4」となり「3e」の結果と同じとなるので、「2m」は除去される。

0028

次に、図7の例では、式38について、モニタ対象のミュータントのうち「5e」が対象のものと、伝播している「1m」とについて解析される。解析結果39では、「3m」の結果が「true」となり「5e」の結果と同じとなるので、「3m」は除去される。同様に、解析結果39では、「4m」の結果が「false」となり「1m」の結果と同じとなるので、「4m」と「1m」とは1つにまとめられ、インフェクションが確定した「1m」はモニタ対象から外される。なお、「4m」と「1m」とは、どちらにまとめても構わない。

0029

3つ目のステップは、元のプログラムにミュータントを埋め込む。4つ目のステップは、各ミュータントに対してテストを実行する。すなわち、図6および図7では、1つ目と2つ目のステップでミュータントを削減し、3つ目と4つ目のステップでミューテーションを実行する。しかしながら、上述の計算コストを削減する方法では、2つ目のステップにおいてミュータントの実行を行わないため、高次ミューテーションの状態数を削減することが困難である。

0030

図8は、同じ実行結果となるミュータントをまとめることができない場合の一例を説明する図である。図8の例では、ソースコード40に対してテスト入力a=2、b=2、c=0であった場合の各ミュータントのコンテキストが異なる場合が発生する。表41は、ソースコード40の1回目と2回目の実行後の各ミュータントのコンテキストを示す。式42aおよび式42bは、1回目の実行後は同じ結果43となり、同じパーティションと判定される。ところが、式42aおよび式42bは、2回目の実行後は、それぞれ結果43aおよび結果43bのように、異なる結果となり、異なるパーティションであると判定される。すなわち、範囲44で示す結果は、ミュータントを実行しないと結果が分からないこととなる。

0031

また、計算コストを削減する方法に対して、状態を分割しながら実行する方法をそのまま適用すると、無駄な状態分割が多くなる。状態を分割するには、重い処理であるコピーする処理が含まれるため、状態分割は、なるべく少ない方が好ましい。

0032

上述の様な課題に対して、本実施例では、ソースコード内の命令を先に評価し、命令の評価結果に基づいて状態(ステート)をまとめることで、高次ミューテーションの状態数を削減できる。

0033

次に、図1の説明に戻って、解析装置100の構成について説明する。図1に示すように、解析装置100は、通信部110と、入力部111と、表示部112と、操作部113と、記憶部120と、制御部130とを有する。なお、解析装置100は、図1に示す機能部以外にも既知のコンピュータが有する各種の機能部、例えば各種の入力デバイス音声出力デバイス等の機能部を有することとしてもかまわない。

0034

通信部110は、例えば、NIC(Network Interface Card)等によって実現される。通信部110は、図示しないネットワークを介して他の情報処理装置有線または無線で接続され、他の情報処理装置との間で情報の通信を司る通信インタフェースである。通信部110は、例えば、他の情報処理装置から解析対象のソースコード、テスト項目およびミューテーションオペレータリストを受信する。通信部110は、受信した解析対象のソースコード、テスト項目およびミューテーションオペレータリストを制御部130に出力する。

0035

入力部111は、例えば、光学ディスク、USB(Universal Serial Bus)メモリSDメモリカード等の外部記憶媒体に対する媒体アクセス装置等によって実現される。入力部111は、外部記憶媒体に記憶された解析対象のソースコード、テスト項目およびミューテーションオペレータリストを読み取って、読み取った解析対象のソースコード、テスト項目およびミューテーションオペレータリストを制御部130に出力する。なお、解析対象のソースコード、テスト項目およびミューテーションオペレータリストは、通信部110または入力部111のいずれかから制御部130に入力されればよく、以下の説明では、入力部111から制御部130に入力される場合について説明する。

0036

表示部112は、各種情報を表示するための表示デバイスである。表示部112は、例えば、表示デバイスとして液晶ディスプレイ等によって実現される。表示部112は、制御部130から入力された結果画面等の各種画面を表示する。

0037

操作部113は、解析装置100のユーザから各種操作を受け付ける入力デバイスである。操作部113は、例えば、入力デバイスとして、キーボードマウス等によって実現される。操作部113は、ユーザによって入力された操作を操作情報として制御部130に出力する。なお、操作部113は、入力デバイスとして、タッチパネル等によって実現されるようにしてもよく、表示部112の表示デバイスと、操作部113の入力デバイスとは、一体化されるようにしてもよい。

0038

記憶部120は、例えば、RAM(Random Access Memory)、フラッシュメモリ(Flash Memory)等の半導体メモリ素子ハードディスク光ディスク等の記憶装置によって実現される。記憶部120は、命令記憶部121と、評価結果記憶部122と、実行状態集合記憶部123と、テスト結果記憶部124とを有する。また、記憶部120は、制御部130での処理に用いる情報を記憶する。

0039

命令記憶部121は、ソースコードがコンパイルされた中間コードの各命令を命令IDと対応付けて記憶する。なお、中間コードは、例えば、ビットコードが挙げられる。図9は、命令記憶部の一例を示す図である。図9に示すように、命令記憶部121は、「命令ID」、「命令」といった項目を有する。命令記憶部121は、例えば、命令IDごとに1レコードとして記憶する。

0040

「命令ID」は、命令ごと一意に付される番号(ID)であり、命令を識別する識別子である。「命令」は、中間コードの各命令を示す情報である。

0041

図1の説明に戻って、評価結果記憶部122は、ミューテーションされた各ミュータントの評価結果を記憶する。図10は、評価結果記憶部の一例を示す図である。図10に示すように、評価結果記憶部122は、例えば、命令の結果を格納するレジスタを示す「%1」に対して、ミューテーション記述子で記述された各ミュータントの評価結果を対応付けて記憶する。なお、評価結果記憶部122は、評価される命令が変わる度に、ミューテーション記述子に応じて更新される。

0042

図1の説明に戻って、実行状態集合記憶部123は、各命令のミューテーション記述子と評価結果とを、ステートIDに対応付けて記憶する。すなわち、実行状態集合記憶部123は、実行状態集合を記憶する。図11は、実行状態集合記憶部の一例を示す図である。図11に示すように、実行状態集合記憶部123は、「ステートID」、「命令ID」、「命令結果」、「ミューテーション記述子」、「同期実行グループ」といった項目を有する。実行状態集合記憶部123は、例えば、ステートIDごとに1レコードとして記憶する。

0043

「ステートID」は、実行状態、つまりステートを識別する識別子である。なお、「ステートID」は、命令の評価後のステートに引き継いでもよい。「命令ID」は、命令を識別する識別子である。「命令結果」は、命令の評価結果、つまり実行結果を示す情報である。「ミューテーション記述子」は、対応するステートIDにおける命令のミューテーション記述子を示す情報である。「同期実行グループ」は、複数のステートの命令を並列に評価するグループを示す情報である。「同期実行グループ」は、例えば、並列に評価中のステートIDに対して○印が付されることで、並列に評価中のステートIDを識別できる。

0044

図1の説明に戻って、テスト結果記憶部124は、ミューテーションされたソースコードに対して、テストを実行した結果であるテスト結果、すなわちテスト結果群を記憶する。図12は、テスト結果記憶部の一例を示す図である。図12に示すように、テスト結果記憶部124は、「テスト」、「ミュータント」、「テスト合否」といった項目を有する。テスト結果記憶部124は、テスト項目ごとに1レコードとして記憶する。

0045

「テスト」は、命令に対するテスト入力を示す情報である。「ミュータント」は、命令に対するミュータントを示す情報である。「ミュータント」は、例えば、「{(2,!=)}」のように、ミューテーション記述子で記述される。「テスト合否」は、テスト対象のソースコードのミューテーションに対するテストの合否を示す情報であり、「Pass」または「Fail」で表わされる。「Pass」は、ソースコード内の要素がミュータントに置換された場合に、当該テスト項目において埋め込まれたバグを検出できなかったことを示す。「Fail」は、ソースコード内の要素がミュータントに置換された場合に、当該テスト項目において埋め込まれたバグを検出できたことを示す。図12の1行目の例では、テスト入力「a=2,b=2,c=0」に対してミューテーションID「2」の要素(演算子)を「!=」にミューテーションした結果、テスト合否は「Pass」、つまり埋め込まれたバグを検出できなかったことを示す。

0046

図1の説明に戻って、制御部130は、例えば、CPU(Central Processing Unit)やMPU(Micro Processing Unit)等によって、内部の記憶装置に記憶されているプログラムがRAMを作業領域として実行されることにより実現される。また、制御部130は、例えば、ASIC(Application Specific IntegratedCircuit)やFPGA(Field Programmable Gate Array)等の集積回路により実現されるようにしてもよい。制御部130は、置換部131と、コンパイラ132と、状態管理部133と、命令評価部134と、出力部135とを有し、以下に説明する情報処理の機能や作用を実現または実行する。なお、制御部130の内部構成は、図1に示した構成に限られず、後述する情報処理を行う構成であれば他の構成であってもよい。

0047

置換部131は、入力部111からソースコードが入力されると、ソースコード内の要素について、要素をミュータントに変化させるメタ関数に置換する。なお、メタ関数は、ミューテーションIDを引数に持つ。置換部131は、ソースコード内の要素がメタ関数に置換された、つまりメタ関数が埋め込まれた置換後のソースコードをコンパイラ132に出力する。

0048

ここで、図13および図14を用いて、メタ関数の埋め込みについて説明する。図13は、テスト対象のソースコードの一例を示す図である。図14は、メタ関数を埋め込んだソースコードの一例を示す図である。置換部131は、例えば、図13に示すソースコード45に対して、2行目のwhile文の演算子「+」、「>」、および、3行目のインクリメントを示す演算子「++」にそれぞれ対応するメタ関数を埋め込む。置換部131は、ソースコード45にメタ関数を埋め込んで、図14に示す置換後のソースコード46を生成する。

0049

図1の説明に戻って、コンパイラ132は、置換部131から置換後のソースコードが入力されると、置換後のソースコードをVM(Virtual Machine)上で実行可能な中間コードであるビットコードにコンパイルする。コンパイラ132は、例えば、置換後のソースコードをLLMビットコードにコンパイルする。なお、以下の説明では、LLVMビットコードを、単に中間コードと称して説明する。コンパイラ132は、コンパイルした中間コードを状態管理部133に出力する。

0050

ここで、図15を用いて、中間コードについて説明する。図15は、中間コードの一例を示す図である。図15に示すように、コンパイラ132は、例えば、置換後のソースコードをLLVMビットコードである中間コード47にコンパイルする。図15に示す中間コード47には、図14で埋め込まれたメタ関数を含む命令がコンパイルされる。

0051

図1の説明に戻って、状態管理部133には、入力部111からテスト項目およびミューテーションオペレータリストが入力される。また、状態管理部133には、コンパイラ132から中間コードが入力される。状態管理部133は、中間コードが入力されると、テスト項目およびミューテーションオペレータリストに基づいて、テスト入力、つまりテストケースを選択する。テストケースは、例えば、「a=2,b=2,c=0」等が挙げられる。

0052

ここで、図16および図17を用いて、テスト項目およびミューテーションオペレータリストについて説明する。図16は、テスト項目の一例を示す図である。図17は、ミューテーションオペレータリストの一例を示す図である。図16に示すように、テスト項目48は、例えば、テスト項目ごとに関数の形で表現される。また、図17に示すように、ミューテーションオペレータリスト49は、例えば、OSSN(Shift operator mutation)、ORRN(Relational operator mutation)、OIDO(Increment/Decrement Replacement)といった形で表現される。

0053

状態管理部133は、テストケースを選択すると、初期実行ステートを生成する。状態管理部133は、初期実行ステートを生成すると、ステート選択処理を実行する。状態管理部133は、ステート選択処理として、まず、実行状態集合記憶部123を参照し、実行状態集合の中に同期実行グループ(以下、単にグループともいう。)に含まれるステートが存在するか否かを判定する。状態管理部133は、グループに含まれるステートが存在しない場合には、任意の方法、例えば、深さ優先でステートを選択し、ステート選択処理を終了する。

0054

状態管理部133は、グループに含まれるステートが存在する場合には、グループ内に評価中の命令が未実施のステートが存在するか否かを判定する。状態管理部133は、グループ内に評価中の命令が未実施のステートが存在する場合には、グループのうち評価中の命令が未実施のステートから任意の1ステートを選択し、ステート選択処理を終了する。状態管理部133は、グループ内に評価中の命令が未実施のステートが存在しない場合には、次の命令を評価中として該命令が未実施のステートを選択し、ステート選択処理を終了する。状態管理部133は、ステート選択処理を終了すると、選択したステートのステートIDを命令評価部134に出力する。

0055

状態管理部133は、命令評価部134からグループ解除指示が入力されると、実行状態集合記憶部123の同期実行グループ欄を消去してグループを解除する。状態管理部133は、グループを解除すると、解除完了情報を命令評価部134に出力する。

0056

状態管理部133は、命令評価部134からステート分割指示が入力されると、ステート分割処理を実行する。状態管理部133は、ステート分割処理として、まず、ステート分割指示に対応するステートで実行済みのメタ関数か否かを判定する。状態管理部133は、実行済みのメタ関数である場合には、元のステートのミューテーション記述子のうち、当該メタ関数に対応するミューテーション演算を集めた集合M、つまりミューテーション演算に用いるミューテーション記述子を、ステートIDに対応付けて実行状態集合記憶部123に記憶する。状態管理部133は、集合MをステートIDに対応付けて実行状態集合記憶部123に記憶すると、評価指示を命令評価部134に出力する。

0057

状態管理部133は、実行済みのメタ関数でない場合には、当該メタ関数に対応するミューテーション演算の集合M、つまりミューテーション演算に用いるミューテーション記述子を、ステートIDに対応付けて実行状態集合記憶部123に記憶する。状態管理部133は、集合MをステートIDに対応付けて実行状態集合記憶部123に記憶すると、評価指示を命令評価部134に出力する。

0058

状態管理部133は、命令評価部134からグループ判定指示が入力されると、実行状態集合記憶部123を参照し、分割前のステートがグループに属しているか否かを判定する。状態管理部133は、分割前のステートがグループに属している場合には、分割前のグループに分割後のステートも含めることとする。つまり、状態管理部133は、実行状態集合記憶部123の対応するステートの同期実行グループ欄に○印を記憶する。状態管理部133は、分割したステートをグループに分類すると、ステート分割処理を終了する。

0059

状態管理部133は、分割前のステートがグループに属していない場合には、新たにグループを生成し、分割後のステートを生成したグループに含めることとする。つまり、状態管理部133は、実行状態集合記憶部123の分割後のステートの同期実行グループ欄に○印を記憶する。状態管理部133は、分割したステートをグループに分類すると、ステート分割処理を終了する。

0060

状態管理部133は、ステート分割処理が終了するか、命令評価部134から命令実行情報が入力されると、ステートがグループに含まれ、かつ、グループ内の全てのステートが同じ命令を実行済みか否かを判定する。状態管理部133は、ステートがグループに含まれ、かつ、グループ内の全てのステートが同じ命令を実行済みである場合には、ステートマージ処理を実行する。状態管理部133は、ステートがグループに含まれ、かつ、グループ内の全てのステートが同じ命令を実行済みでない場合には、ステート完了チェック処理を実行する。

0061

状態管理部133は、ステートマージ処理として、まず、グループ内のステートが全て同じ評価結果か否かを判定する。状態管理部133は、グループ内のステートが全て同じ評価結果である場合には、ステートマージ処理を終了する。状態管理部133は、グループ内のステートが全て同じ評価結果でない場合には、グループ内のステートsについて、マージを行う。状態管理部133は、グループ内で同じ評価結果となる他のステートがあるか否かを判定する。状態管理部133は、グループ内で同じ評価結果となる他のステートがある場合には、同じ評価結果となるステートにステートsのミューテーション記述子を加え、ステートsを削除する。状態管理部133は、グループ内で同じ評価結果となる他のステートがない場合には、次のステートについてマージを行う。状態管理部133は、グループ内のステートsについて、マージが完了すると、ステートマージ処理を終了し、次にステート完了チェック処理を実行する。

0062

状態管理部133は、ステート完了チェック処理として、まず、プログラムの終端か否かを判定する。状態管理部133は、プログラムの終端である場合には、実行状態集合記憶部123を参照して、テスト結果をテスト結果記憶部124に格納し、実行状態集合記憶部123のステートを削除してステート完了チェック処理を終了する。すなわち、状態管理部133は、選択中のテストケースにかかるステートの情報が記憶されている実行状態集合記憶部123をクリアする。

0063

状態管理部133は、プログラムの終端でない場合には、ユーザ指定終了条件を超えているか否かを判定する。状態管理部133は、ユーザ指定の終了条件を超えている場合には、実行状態集合記憶部123を参照して、テスト結果をテスト結果記憶部124に格納し、実行状態集合記憶部123のステートを削除してステート完了チェック処理を終了する。状態管理部133は、ユーザ指定の終了条件を超えていない場合には、メモリ不正アクセスなどの異常があるか否かを判定する。

0064

状態管理部133は、異常がある場合には、実行状態集合記憶部123を参照して、テスト結果をテスト結果記憶部124に格納し、実行状態集合記憶部123のステートを削除してステート完了チェック処理を終了する。状態管理部133は、異常がない場合には、ステート完了チェック処理を終了する。

0065

状態管理部133は、ステート完了チェック処理を終了すると、全てのステートが完了したか否かを判定する。状態管理部133は、全てのステートが完了していない場合には、ステート選択処理を実行する。状態管理部133は、全てのステートが完了した場合には、全てのテストケースが実行済みか否かを判定する。状態管理部133は、全てのテストケースが実行済みでない場合には、次のテストケースを選択し、選択したテストケースを用いて処理を繰り返す。状態管理部133は、全てのテストケースが実行済みである場合には、出力指示を出力部135に出力する。

0066

上述の通り、状態管理部133は、ソースコード内の要素をミュータントに変化させるメタ関数に置換してコンパイルした中間コードを実行する際に、メタ関数に対応するミューテーション演算について、ミュータントの変化を示すミューテーション記述子の集合を管理する管理部の一例である。また、状態管理部133は、ミューテーション記述子の集合のうち、命令の評価結果が同じとなる1つ以上のミューテーション記述子を選択する選択部の一例である。また、状態管理部133は、グループ内における命令の評価結果に基づく第3のステートのうち、該評価結果が同じとなる第3のステートをマージするマージ部の一例である。また、状態管理部133は、副作用がない命令が続く間、グループ内で第3のステートをマージするマージ部の一例である。また、状態管理部133は、マージを行うことで、第1のステートまたは第2のステートに戻る場合には、マージを行わないマージ部の一例である。

0067

命令評価部134は、状態管理部133からステートIDが入力されると、命令記憶部121および実行状態集合記憶部123を参照し、命令を読み込む。命令評価部134は、命令を読み込むと、ステートIDで示されるステートがグループに含まれ、かつ、副作用のない命令以外か否かを判定する。なお、副作用のない命令とは、指定されたメタ関数(increment/decrementを除く関数)、二項演算(ADD,OR等)、比較演算ICMP,FCMP)、変換演算(Trunc,ZEXT等)、読み込み命令(load)およびgetelementptr命令等のメモリの内容が変わらない命令である。これに対し、副作用がある可能性を有する命令は、例えば、分岐命令関数呼出復帰命令(return)および変数への代入等が挙げられる。また、副作用がある可能性を有する命令は、例えば、グローバル変数の値を変更してしまう命令である。

0068

命令評価部134は、ステートがグループに含まれ、かつ、副作用のない命令以外である場合には、状態管理部133にグループ解除指示を出力する。命令評価部134は、ステートがグループに含まれ、かつ、副作用のない命令以外でない場合、または、状態管理部133から解除完了情報が入力された場合には、命令がメタ関数の呼出か否かを判定する。命令評価部134は、命令がメタ関数の呼出でない場合には、当該命令を実行し、状態管理部133に命令実行情報を出力する。

0069

命令評価部134は、命令がメタ関数の呼出である場合には、メタ関数がミューテーションオペレータリストに含まれているか否かを判定する。命令評価部134は、メタ関数がミューテーションオペレータリストに含まれていない場合には、当該命令を実行し、状態管理部133に命令実行情報を出力する。命令評価部134は、メタ関数がミューテーションオペレータリストに含まれている場合には、状態管理部133にステート分割指示を出力する。

0070

命令評価部134は、状態管理部133から評価指示が入力されると、命令記憶部121および実行状態集合記憶部123を参照し、集合Mのミューテーション演算mについて先行評価を実行する。命令評価部134は、ミューテーション演算mの命令の評価結果を、評価結果記憶部122に記憶する。命令評価部134は、既に同じ評価結果となるステートがあるか否かを判定する。命令評価部134は、既に同じ評価結果となるステートがある場合には、元のステートをコピーし、評価結果をステートに記憶し、当該ステートを選択する。すなわち、命令評価部134は、実行状態集合記憶部123の当該ステートのステートIDに対応するレコードを更新する。

0071

命令評価部134は、既に同じ評価結果となるステートがない場合には、同じ評価結果となるステートを生成して当該ステートを選択する。また、命令評価部134は、生成したステートを実行状態集合記憶部123に記憶する。すなわち、命令評価部134は、ステートを分割する。

0072

命令評価部134は、選択したステートのミューテーション記述子に、ミューテーション演算mと元のステートのミューテーション記述子との直積を算出して加え、実行状態集合記憶部123を更新する。命令評価部134は、集合M内のミューテーション演算mについて、それぞれ、先行評価とステートの分割要否と直積の算出とを実行する。命令評価部134は、集合M内のミューテーション演算mについて、先行評価とステートの分割要否と直積の算出とが完了すると、グループ判定指示を状態管理部133に出力する。

0073

上述の通り、命令評価部134は、ミューテーション記述子それぞれの命令を評価する第1評価部の一例である。また、命令評価部134は、選択されたミューテーション記述子と、ミューテーション演算、または、命令の評価前のミューテーション記述子の集合である第1のステートとの直積を算出して第2のステートを生成する生成部の一例である。なお、生成部の処理は、その一部を状態管理部133で行ってもよい。また、命令評価部134は、生成された第2のステートのミューテーション記述子それぞれの命令を評価する際に、第2のステートが複数ある場合には、当該複数の第2のステートを1つのグループとして、該グループ内の第2のステートそれぞれに対して並列に命令を評価する第2評価部の一例である。また、命令評価部134は、副作用がない命令以外の命令に到達すると、グループを解消して第2のステートの前記命令を評価する第2評価部の一例である。

0074

出力部135は、状態管理部133から出力指示が入力されると、テスト結果記憶部124を参照し、テスト合否の項目について、「Pass」であるミュータントを抽出する。また、出力部135は、テスト結果記憶部124のテスト合否の項目が「Fail」であるミュータントの数を、ミュータントの総数除算した値をミューテーションスコアとして算出する。出力部135は、算出したミューテーションスコアと、テスト合否の項目が「Pass」であるミュータントとに基づいて、結果レポートを生成する。出力部135は、結果レポートを含む結果画面を生成し、生成した結果画面を表示部112に出力して表示させる。

0075

次に、実施例の解析装置100の動作について説明する。図18は、実施例の解析処理の一例を示すフローチャートである。

0076

置換部131は、入力部111からソースコードが入力されると、ソースコード内の要素について、要素をミュータントに変化させるメタ関数に置換し、ソースコード内に埋め込む(ステップS1)。置換部131は、置換後のソースコードをコンパイラ132に出力する。コンパイラ132は、置換部131から置換後のソースコードが入力されると、置換後のソースコードを中間コードにコンパイルする(ステップS2)。コンパイラ132は、コンパイルした中間コードを状態管理部133に出力する。

0077

状態管理部133には、入力部111からテスト項目およびミューテーションオペレータリストが入力される。また、状態管理部133には、コンパイラ132から中間コードが入力される。状態管理部133は、中間コードが入力されると、テスト項目およびミューテーションオペレータリストに基づいて、テストケースを選択する(ステップS3)。状態管理部133は、テストケースを選択すると、初期実行ステートを生成する(ステップS4)。状態管理部133は、初期実行ステートを生成すると、ステート選択処理を実行する(ステップS5)。

0078

ここで、図19を用いて、ステート選択処理について説明する。図19は、ステート選択処理の一例を示すフローチャートである。

0079

状態管理部133は、ステート選択処理として、まず、実行状態集合記憶部123を参照し、実行状態集合の中にグループに含まれるステートが存在するか否かを判定する(ステップS51)。状態管理部133は、グループに含まれるステートが存在しない場合には(ステップS51:否定)、任意の方法でステートを選択し(ステップS52)、元の処理に戻る。

0080

状態管理部133は、グループに含まれるステートが存在する場合には(ステップS51:肯定)、グループ内に評価中の命令が未実施のステートが存在するか否かを判定する(ステップS53)。状態管理部133は、グループ内に評価中の命令が未実施のステートが存在する場合には(ステップS53:肯定)、グループのうち評価中の命令が未実施のステートから任意の1ステートを選択し(ステップS54)、元の処理に戻る。

0081

状態管理部133は、グループ内に評価中の命令が未実施のステートが存在しない場合には(ステップS53:否定)、次の命令を評価中として該命令が未実施のステートを選択し(ステップS55)、元の処理に戻る。状態管理部133は、元の処理に戻ると、選択したステートのステートIDを命令評価部134に出力する。これにより、解析装置100は、ステートを選択できる。

0082

図18の説明に戻って、命令評価部134は、状態管理部133からステートIDが入力されると、命令記憶部121および実行状態集合記憶部123を参照し、命令を読み込む(ステップS6)。命令評価部134は、命令を読み込むと、ステートIDで示されるステートがグループに含まれ、かつ、副作用のない命令以外か否かを判定する(ステップS7)。命令評価部134は、ステートがグループに含まれ、かつ、副作用のない命令以外である場合には(ステップS7:肯定)、状態管理部133にグループ解除指示を出力する。

0083

状態管理部133は、命令評価部134からグループ解除指示が入力されると、実行状態集合記憶部123の同期実行グループ欄を消去してグループを解除する(ステップS8)。状態管理部133は、グループを解除すると、解除完了情報を命令評価部134に出力する。

0084

命令評価部134は、ステートがグループに含まれ、かつ、副作用のない命令以外でない場合(ステップS7:否定)、または、状態管理部133から解除完了情報が入力された場合には、命令がメタ関数の呼出か否かを判定する(ステップS9)。命令評価部134は、命令がメタ関数の呼出でない場合には(ステップS9:否定)、当該命令を実行し(ステップS11)、状態管理部133に命令実行情報を出力する。

0085

命令評価部134は、命令がメタ関数の呼出である場合には(ステップS9:肯定)、メタ関数がミューテーションオペレータリストに含まれているか否かを判定する(ステップS10)。命令評価部134は、メタ関数がミューテーションオペレータリストに含まれていない場合には(ステップS10:否定)、当該命令を実行し(ステップS11)、状態管理部133に命令実行情報を出力する。命令評価部134は、メタ関数がミューテーションオペレータリストに含まれている場合には(ステップS10:肯定)、状態管理部133にステート分割指示を出力する。

0086

状態管理部133は、命令評価部134からステート分割指示が入力されると、ステート分割処理を実行する(ステップS12)。ここで、図20を用いてステート分割処理について説明する。図20は、ステート分割処理の一例を示すフローチャートである。状態管理部133は、ステート分割指示に対応するステートで実行済みのメタ関数か否かを判定する(ステップS121)。状態管理部133は、実行済みのメタ関数である場合には(ステップS121:肯定)、元のステートのミューテーション記述子のうち、当該メタ関数に対応するミューテーション演算を集めた集合Mを、ステートIDに対応付けて実行状態集合記憶部123に記憶する(ステップS122)。状態管理部133は、集合MをステートIDに対応付けて実行状態集合記憶部123に記憶すると、評価指示を命令評価部134に出力する。

0087

状態管理部133は、実行済みのメタ関数でない場合には(ステップS121:否定)、当該メタ関数に対応するミューテーション演算の集合Mを、ステートIDに対応付けて実行状態集合記憶部123に記憶する(ステップS123)。状態管理部133は、集合MをステートIDに対応付けて実行状態集合記憶部123に記憶すると、評価指示を命令評価部134に出力する。

0088

命令評価部134は、状態管理部133から評価指示が入力されると、集合M内のミューテーション演算mについて、それぞれ、先行評価とステートの分割要否と直積の算出とを実行するために、ステップS124aからステップS124b間を繰り返す。命令評価部134は、命令記憶部121および実行状態集合記憶部123を参照し、ミューテーション演算mの命令を先行評価する(ステップS125)。命令評価部134は、ミューテーション演算mの命令の評価結果を、評価結果記憶部122に記憶する。

0089

命令評価部134は、既に同じ評価結果となるステートがあるか否かを判定する(ステップS126)。命令評価部134は、既に同じ評価結果となるステートがある場合には(ステップS126:肯定)、元のステートをコピーし、評価結果をステートに記憶し、当該ステートを選択する(ステップS127)。命令評価部134は、既に同じ評価結果となるステートがない場合には(ステップS126:否定)、同じ評価結果となるステートを生成して当該ステートを選択する(ステップS128)。

0090

命令評価部134は、選択したステートのミューテーション記述子に、ミューテーション演算mと元のステートのミューテーション記述子との直積を算出して加え、実行状態集合記憶部123を更新する(ステップS129)。命令評価部134は、集合M内のミューテーション演算mについて、先行評価とステートの分割要否と直積の算出とが完了すると、グループ判定指示を状態管理部133に出力する。

0091

状態管理部133は、命令評価部134からグループ判定指示が入力されると、実行状態集合記憶部123を参照し、分割前のステートがグループに属しているか否かを判定する(ステップS130)。状態管理部133は、分割前のステートがグループに属している場合には(ステップS130:肯定)、分割前のグループに分割後のステートも含めることとする(ステップS131)。状態管理部133は、分割前のステートがグループに属していない場合には(ステップS130:否定)、新たにグループを生成し、分割後のステートを生成したグループに含めることとする(ステップS132)。状態管理部133は、分割したステートをグループに分類すると、元の処理に戻る。これにより、解析装置100は、ステートを分割できる。

0092

図18の説明に戻って、状態管理部133は、ステート分割処理が終了するか、命令評価部134から命令実行情報が入力されると、ステートがグループに含まれ、かつ、グループ内の全てのステートが同じ命令を実行済みか否かを判定する(ステップS13)。状態管理部133は、ステートがグループに含まれ、かつ、グループ内の全てのステートが同じ命令を実行済みである場合には(ステップS13:肯定)、ステートマージ処理を実行する(ステップS14)。状態管理部133は、ステートがグループに含まれ、かつ、グループ内の全てのステートが同じ命令を実行済みでない場合には(ステップS13:否定)、ステート完了チェック処理を実行する(ステップS15)。

0093

ここで、図21を用いてステートマージ処理について説明する。図21は、ステートマージ処理の一例を示すフローチャートである。状態管理部133は、グループ内のステートが全て同じ評価結果か否かを判定する(ステップS141)。状態管理部133は、グループ内のステートが全て同じ評価結果である場合には(ステップS141:肯定)、元の処理に戻る。状態管理部133は、グループ内のステートが全て同じ評価結果でない場合には(ステップS141:否定)、グループ内のステートsについて、マージを行うために、ステップS142aからステップS142b間を繰り返す。

0094

状態管理部133は、グループ内で同じ評価結果となる他のステートがあるか否かを判定する(ステップS143)。状態管理部133は、グループ内で同じ評価結果となる他のステートがある場合には(ステップS143:肯定)、同じ評価結果となるステートにステートsのミューテーション記述子を加え、ステートsを削除する(ステップS144)。状態管理部133は、グループ内で同じ評価結果となる他のステートがない場合には(ステップS143:否定)、次のステートについてマージを行う。状態管理部133は、グループ内のステートsについてマージが完了すると、元の処理に戻る。これにより、解析装置100は、ステートをマージすることができる。

0095

図18の説明に戻って、状態管理部133は、ステート完了チェック処理を実行する(ステップS15)。ここで、図22を用いてステート完了チェック処理について説明する。図22は、ステート完了チェック処理の一例を示すフローチャートである。状態管理部133は、プログラムの終端か否かを判定する(ステップS151)。状態管理部133は、プログラムの終端である場合には(ステップS151:肯定)、実行状態集合記憶部123を参照して、テスト結果をテスト結果記憶部124に格納し、実行状態集合記憶部123のステートを削除して(ステップS154)、元の処理に戻る。

0096

状態管理部133は、プログラムの終端でない場合には(ステップS151:否定)、ユーザ指定の終了条件を超えているか否かを判定する(ステップS152)。状態管理部133は、ユーザ指定の終了条件を超えている場合には(ステップS152:肯定)、ステップS154に進む。状態管理部133は、ユーザ指定の終了条件を超えていない場合には(ステップS152:否定)、メモリ不正アクセスなどの異常があるか否かを判定する(ステップS153)。状態管理部133は、異常がある場合には(ステップS153:肯定)、ステップS154に進む。状態管理部133は、異常がない場合には(ステップS153:否定)、元の処理に戻る。これにより、解析装置100は、ステートの完了をチェックできる。

0097

図18の説明に戻って、状態管理部133は、全てのステートが完了したか否かを判定する(ステップS16)。状態管理部133は、全てのステートが完了していない場合には(ステップS16:否定)、ステップS5に戻る。状態管理部133は、全てのステートが完了した場合には(ステップS16:肯定)、全てのテストケースが実行済みか否かを判定する(ステップS17)。状態管理部133は、全てのテストケースが実行済みでない場合には(ステップS17:否定)、ステップS3に戻る。状態管理部133は、全てのテストケースが実行済みである場合には(ステップS17:肯定)、出力指示を出力部135に出力する。

0098

出力部135は、状態管理部133から出力指示が入力されると、テスト結果記憶部124を参照し、ミューテーションスコアを算出する。また、出力部135は、算出したミューテーションスコアと、テスト合否の項目が「Pass」であるミュータントとに基づいて、結果レポートを生成する。出力部135は、結果レポートを含む結果画面を生成し、生成した結果画面を表示部112に出力して表示させる(ステップS18)。これにより、解析装置100は、高次ミューテーションの状態数を削減できる。すなわち、解析装置100は、ミューテーション解析の計算コストを低減することができる。

0099

続いて、図23から図47を用いて、解析処理の具体例について説明する。なお、以下の説明では、各ステートに着目して説明する。また、ステートIDは、例えば「State1」、「State2」というように「State」+番号といった形式とするが、同一のステートIDの更新前後は異なる符号としている。また、本具体例では、図13に示すソースコード45、図14に示す置換後のソースコード46、および、図15に示す中間コード47を用いる。なお、本具体例では、ステートの情報は、適宜実行状態集合記憶部123に記憶されるものとする。

0100

図23から図30は、whileループの1回目の一例を説明する図である。図23から図30では、ソースコード45のwhileループの1回目について説明する。ステートID「State1」であるステート50は、ソースコード45の2行目に対応する。また、テストケースは、テストケース51で示す値である。

0101

図23では、命令を先に評価した後、ステートを分割する。ステート50は、まず、命令52について評価される。命令52は、ソースコード45の波線部分「a+b」に対応する。命令52のレジスタ値「%1」は、表53に示すように演算子「+」のミュータントに対応した値となる。ここで、「a+b」と「a*b」とは、レジスタ値「%1」が「4」で結果が同じである。従って、図23では、「%1=4」について、ステートID「State1」であるステート55aが生成される。同様に、「a−b」と「a%b」とは、レジスタ値「%1」が「0」で結果が同じである。従って、図23では、「%1=0」について、ステートID「State2」であるステート55bが生成される。「a/b」は、レジスタ値「%1」が「1」となり、他に同じ結果となるミュータントがない。従って、図23では、「%1=1」について、ステートID「State3」であるステート55cが生成される。

0102

次に、図23では、直積の算出54で示すように、ステート55aに対応するミューテーション記述子として、ステート50のミューテーション記述子「{}」と、「+」を示すミューテーション記述子「{}」および「*」を示すミューテーション記述子「{1,*}」との直積が算出される。算出されたミューテーション記述子「{},{1,*}」は、ステート55aに対応するミューテーション記述子として実行状態集合記憶部123に記憶される。同様に、ステート55bおよびステート55cに対応するミューテーション記述子は、直積の算出54で示すように算出されて、それぞれ実行状態集合記憶部123に記憶される。図23では、ステート55a、ステート55bおよびステート55cは、生成されたグループ55に分類される。なお、グループ55は、説明の便宜上「Group1」と称する。グループ55に属するステート55a、ステート55bおよびステート55cは、並列して、つまり同時に評価される。

0103

図24では、ステート55aは、まず、命令52aについて評価される。命令52aは、ソースコード45の波線部分「a+b>c」に対応する。また、命令52aには、波線部分に示すように、レジスタ値「%1」が代入される。命令52aのレジスタ値「%2」は、表56aに示すように演算子「>」のミュータントに対応した値となる。ここで、「%1>c」と「%1!=c」と「%1>=c」とは、レジスタ値「%2」が「1」で結果が同じである。従って、図24では、「%2=1」について、ステートID「State1」が更新されステート58aとなる。なお、ステート58aには、「%1=4」の情報も保持される。同様に、「%2=0」について、ステートID「State4」であるステート58bが生成される。

0104

次に、図24では、図23と同様に、直積の算出57aで示すように、直積が算出される。算出された直積は、それぞれ、ステート58aおよびステート58bに対応するミューテーション記述子として実行状態集合記憶部123に記憶される。ステート58aおよびステート58bは、命令52aが副作用のない命令であるので、グループ55に分類される。

0105

図25では、ステート55bは、まず、命令52aについて評価される。命令52aは、ソースコード45の波線部分「a+b>c」に対応する。また、命令52aには、波線部分に示すように、レジスタ値「%1」が代入される。命令52aのレジスタ値「%2」は、表56bに示すように演算子「>」のミュータントに対応した値となる。ここで、「%1>c」と「%1!=c」と「%1<c」とは、レジスタ値「%2」が「0」で結果が同じである。従って、図25では、「%2=0」について、ステートID「State2」が更新されステート59aとなる。なお、ステート59aには、「%1=0」の情報も保持される。同様に、「%2=1」について、ステートID「State5」であるステート59bが生成される。

0106

次に、図25では、図23と同様に、直積の算出57bで示すように、直積が算出される。算出された直積は、それぞれ、ステート59aおよびステート59bに対応するミューテーション記述子として実行状態集合記憶部123に記憶される。ステート59aおよびステート59bは、命令52aが副作用のない命令であるので、グループ55に分類される。

0107

図26では、ステート55cは、まず、命令52aについて評価される。命令52aは、ソースコード45の波線部分「a+b>c」に対応する。また、命令52aには、波線部分に示すように、レジスタ値「%1」が代入される。命令52aのレジスタ値「%2」は、表56cに示すように演算子「>」のミュータントに対応した値となる。ここで、「%1>c」と「%1!=c」と「%1>=c」とは、レジスタ値「%2」が「1」で結果が同じである。従って、図26では、「%2=1」について、ステートID「State3」であるステート60aが生成される。なお、ステート60aには、「%1=1」の情報も保持される。同様に、「%2=0」について、ステートID「State6」であるステート60bが生成される。

0108

次に、図26では、図23と同様に、直積の算出57cで示すように、直積が算出される。算出された直積は、それぞれ、ステート60aおよびステート60bに対応するミューテーション記述子として実行状態集合記憶部123に記憶される。ステート60aおよびステート60bは、命令52aが副作用のない命令であるので、グループ55に分類される。

0109

図27では、グループ55について、レジスタ値「%2」が同じ計算結果となるステートがマージされる。図27では、ステート58a、ステート59bおよびステート60aがマージされ、ステートID「State1」が更新されステート61aとなる。同様に、図27では、ステート58b、ステート59aおよびステート60bがマージされ、ステートID「State2」が更新されステート61bとなる。

0110

図28に示すように、計算結果が異なるステートは、マージしない。図28では、グループ55に属するステート61aおよびステート61bは、それぞれ命令62について評価される。命令62は、「%2」と「0」とを比較する命令である。ステート61aは、「%2=1」であるので、命令62の結果である「%3」は、falseを示す「0」となり、ステートID「State1」が更新されステート63aとなる。これに対し、ステート61bは、「%2=0」であるので、命令62の結果である「%3」は、trueを示す「1」となり、ステートID「State2」が更新されステート63bとなる。従って、ステート63aおよびステート63bは、計算結果が異なるのでマージしない。

0111

図29に示すように、副作用がない命令以外に到達すると、グループ55が解除される。図29では、グループ55に属するステート63aおよびステート63bは、それぞれ命令64について評価される。命令64は、分岐命令であり副作用がある可能性を有する。従って、グループ55は、解除される。ステート63aは、「%4」に分岐され、ステートID「State1」が更新されステート65aとなる。これに対し、ステート63bは、「%6」に分岐され、ステートID「State2」が更新されステート65bとなる。ステート65aは、グループ55が解除されたので、優先して実行される。また、ステート65bは、while文を抜けて「0」を返して終了される。

0112

図30に示すように、ステート65aは、ソースコード45の3行目に到達する。図30では、ステート65aは、命令66について評価される。命令66は、ソースコード45の波線部分「++c」に対応する。命令66のレジスタ値「%5」は、表67に示すように演算子「++」のミュータントに対応した値となる。なお、命令の結果を以降で使用しない場合には、「c++」および「c−−」へのミューテーションは「++c」および「−−c」に統合する。図30では、「%5=1」について、ステートID「State1」が更新されステート68aとなる。同様に、「%5=−1」について、ステートID「State7」であるステート68bが生成される。

0113

図31から図37は、whileループの2回目の一例を説明する図である。図31から図37では、ソースコード45のwhileループの2回目について説明する。また、テストケースは、テストケース51aで示す値である。

0114

図31のステート68aは、whileループの1回目のステートID「State1」に対応する。ステート68aは、まず、命令52について評価される。命令52のレジスタ値「%1」は、表53aに示すように演算子「+」のミュータントに対応した値となる。ここで、「a+b」と「a*b」とは、レジスタ値「%1」が「4」で結果が同じである。従って、図31では、「%1=4」について、ステートID「State1」が更新されステート69aとなる。このとき、命令52では、ステート68aのミューテーション記述子のうち、ミューテーション記述子「{}」、および、ミューテーションIDが「1」であるミューテーション記述子について評価される。すなわち、ミューテーションIDが「1」でないミューテーション記述子は、ミューテーション記述子「{}」が評価される。同様に、「a−b」と「a%b」とは、レジスタ値「%1」が「0」で結果が同じである。従って、図31では、「%1=0」について、ステートID「State8」であるステート69bが生成される。「a/b」は、レジスタ値「%1」が「1」となり、他に同じ結果となるミュータントがない。従って、図31では、「%1=1」について、ステートID「State9」であるステート69cが生成される。また、図31では、ステート69a、ステート69bおよびステート69cは、生成されたグループ69に分類される。なお、グループ69は、説明の便宜上「Group2」と称する。グループ69に属するステート69a、ステート69bおよびステート69cは、並列して、つまり同時に評価される。

0115

図32では、ステート69aは、命令52aについて評価される。命令52aのレジスタ値「%2」は、表56dに示すように演算子「>」のミュータントに対応した値となる。このとき、命令52aでは、ステート69aのミューテーション記述子のうち、ミューテーション記述子「{}」、および、ミューテーションIDが「2」であるミューテーション記述子について評価される。ここで、「%1>c」と「%1!=c」と「%1>=c」とは、レジスタ値「%2」が「1」で結果が同じである。従って、図32では、「%2=1」について、ステートID「State1」が更新されステート70となる。なお、ステート70には、「%1=4」の情報も保持される。

0116

図33では、ステート69bは、命令52aについて評価される。命令52aのレジスタ値「%2」は、表56eに示すように演算子「>」のミュータントに対応した値となる。このとき、命令52aでは、ステート69bのミューテーション記述子のうち、ミューテーションIDが「2」であるミューテーション記述子について評価される。ここで、「%1==c」と「%1>=c」とは、レジスタ値「%2」が「0」で結果が同じである。従って、図33では、「%2=0」について、ステートID「State8」が更新されステート71aとなる。なお、ステート71aには、「%1=0」の情報も保持される。同様に、「%2=1」について、ステートID「State10」であるステート71bが生成される。ステート71aおよびステート71bは、命令52aが副作用のない命令であるので、グループ69に分類される。

0117

図34では、ステート69cは、命令52aについて評価される。命令52aのレジスタ値「%2」は、表56fに示すように演算子「>」のミュータントに対応した値となる。このとき、命令52aでは、ステート69cのミューテーション記述子のうち、ミューテーションIDが「2」であるミューテーション記述子について評価される。ここで、「%1>c」と「%1!=c」とは、レジスタ値「%2」が「0」で結果が同じである。従って、図34では、「%2=0」について、ステートID「State9」が更新されステート72aとなる。なお、ステート72aには、「%1=1」の情報も保持される。同様に、「%2=1」について、ステートID「State11」であるステート72bが生成される。ステート72aおよびステート72bは、命令52aが副作用のない命令であるので、グループ69に分類される。

0118

図35では、グループ69について、レジスタ値「%2」が同じ計算結果となるステートがマージされる。図35では、ステート70、ステート71bおよびステート72bがマージされ、ステートID「State1」が更新されステート73aとなる。同様に、図35では、ステート71aおよびステート72aがマージされ、ステートID「State8」が更新されステート73bとなる。

0119

図36に示すように、計算結果が異なるステートは、マージしない。また、副作用がない命令以外に到達すると、グループ69が解除される。図36では、グループ69に属するステート73aおよびステート73bは、それぞれ命令74について評価される。命令74は、図28の命令62と図29の命令64とを纏めて記載したものである。ステート73aおよびステート73bは、マージされない。また、グループ69は、解除される。ステート73aは、「%4」に分岐され、ステートID「State1」が更新されステート75aとなる。これに対し、ステート73bは、「%6」に分岐され、ステートID「State8」が更新されステート75bとなる。ステート75aは、グループ69が解除されたので、優先して実行される。また、ステート75bは、while文を抜けて「1」を返して終了される。

0120

図37では、ステート75aは、命令66について評価される。命令66のレジスタ値「%5」は、表67aに示すように演算子「++」のミュータントに対応した値となる。このとき、命令66では、ステート75aのミューテーション記述子のうち、ミューテーション記述子「{}」、および、ミューテーションIDが「3」であるミューテーション記述子について評価される。ところが、ステート75aには、ミューテーションIDが「3」であるミューテーション記述子はないので、ミューテーション記述子「{}」が評価される。図37では、「%5=2」について、ステートID「State1」が更新されステート76となる。

0121

図38および図39は、whileループの3回目の一例を説明する図である。図38および図39では、ソースコード45のwhileループの3回目について説明する。

0122

図38のステート76は、whileループの2回目のステートID「State1」に対応する。ステート76は、まず、命令52について評価される。命令52のレジスタ値「%1」は、表53bに示すように演算子「+」のミュータントに対応した値となる。ここで、「a+b」と「a*b」とは、レジスタ値「%1」が「4」で結果が同じである。従って、図38では、「%1=4」について、ステートID「State1」が更新されステート77aとなる。このとき、命令52では、ステート76のミューテーション記述子のうち、ミューテーション記述子「{}」、および、ミューテーションIDが「1」であるミューテーション記述子について評価される。同様に、「a−b」と「a%b」とは、レジスタ値「%1」が「0」で結果が同じである。従って、図38では、「%1=0」について、ステートID「State12」であるステート77bが生成される。「a/b」は、レジスタ値「%1」が「1」となり、他に同じ結果となるミュータントがない。従って、図38では、「%1=1」について、ステートID「State13」であるステート77cが生成される。また、図38では、ステート77a、ステート77bおよびステート77cは、生成されたグループ77に分類される。なお、グループ77は、説明の便宜上「Group3」と称する。グループ77に属するステート77a、ステート77bおよびステート77cは、並列して、つまり同時に評価される。

0123

続いて、ステート77aは、命令52aについて評価される。命令52aのレジスタ値「%2」は、表56gに示すように演算子「>」のミュータントに対応した値となる。このとき、命令52aでは、ステート77aのミューテーション記述子のうち、ミューテーション記述子「{}」、および、ミューテーションIDが「2」であるミューテーション記述子について評価される。ここで、「%1>c」と「%1!=c」と「%1>=c」とは、レジスタ値「%2」が「1」で結果が同じである。従って、図38では、「%2=1」について、ステートID「State1」が更新されステート78aとなる。

0124

ステート77bは、命令52aについて評価される。命令52aのレジスタ値「%2」は、表56hに示すように演算子「>」のミュータントに対応した値となる。このとき、命令52aでは、ステート77bのミューテーション記述子のうち、ミューテーションIDが「2」であるミューテーション記述子について評価される。ここで、「%1<=c」は、レジスタ値「%2」が「1」となり、他に同じ結果となるミュータントがない。従って、図38では、「%2=1」について、ステートID「State12」が更新されステート78bとなる。

0125

ステート77cは、命令52aについて評価される。命令52aのレジスタ値「%2」は、表56iに示すように演算子「>」のミュータントに対応した値となる。このとき、命令52aでは、ステート77cのミューテーション記述子のうち、ミューテーションIDが「2」であるミューテーション記述子について評価される。ここで、「%1>=c」は、レジスタ値「%2」が「0」となり、他に同じ結果となるミュータントがない。従って、図38では、「%2=0」について、ステートID「State13」が更新されステート78cとなる。ステート78a、ステート78bおよびステート78cは、命令52aが副作用のない命令であるので、グループ77に分類される。

0126

図39では、グループ77について、レジスタ値「%2」が同じ計算結果となるステートがマージされる。図39では、ステート78aおよびステート78bがマージされ、ステートID「State1」が更新されステート79aとなる。ステート78cは、マージする相手がいないので、そのままステートID「State13」が更新されステート79bとなる。また、グループ77は解除される。さらに、ステート79bは、while文を抜けて「2」を返して終了される。ステート79aは、以後、whileループの3回目が終わるまで、whileループの2回目と同様の処理が行われる。

0127

図40および図41は、whileループの4回目の一例を説明する図である。図40および図41では、ソースコード45のwhileループの4回目について説明する。

0128

図40のステート79aは、whileループの3回目のステートID「State1」に対応する。ステート79aは、まず、命令52について評価される。命令52のレジスタ値「%1」は、表53cに示すように演算子「+」のミュータントに対応した値となる。ここで、「a+b」と「a*b」とは、レジスタ値「%1」が「4」で結果が同じである。従って、図40では、「%1=4」について、ステートID「State1」が更新されステート80aとなる。このとき、命令52では、ステート79aのミューテーション記述子のうち、ミューテーション記述子「{}」、および、ミューテーションIDが「1」であるミューテーション記述子について評価される。同様に、「a−b」と「a%b」とは、レジスタ値「%1」が「0」で結果が同じである。従って、図40では、「%1=0」について、ステートID「State14」であるステート80bが生成される。また、図40では、ステート80aおよびステート80bは、生成されたグループ80に分類される。なお、グループ80は、説明の便宜上「Group4」と称する。グループ80に属するステート80aおよびステート80bは、並列して、つまり同時に評価される。

0129

続いて、ステート80aは、命令52aについて評価される。命令52aのレジスタ値「%2」は、表56jに示すように演算子「>」のミュータントに対応した値となる。このとき、命令52aでは、ステート80aのミューテーション記述子のうち、ミューテーション記述子「{}」、および、ミューテーションIDが「2」であるミューテーション記述子について評価される。ここで、「%1>c」と「%1!=c」と「%1>=c」とは、レジスタ値「%2」が「1」で結果が同じである。従って、図40では、「%2=1」について、ステートID「State1」が更新されステート81aとなる。

0130

ステート80bは、命令52aについて評価される。命令52aのレジスタ値「%2」は、表56kに示すように演算子「>」のミュータントに対応した値となる。このとき、命令52aでは、ステート80bのミューテーション記述子のうち、ミューテーションIDが「2」であるミューテーション記述子について評価される。ここで、「%1<=c」は、レジスタ値「%2」が「1」となり、他に同じ結果となるミュータントがない。従って、図40では、「%2=1」について、ステートID「State14」が更新されステート81bとなる。ステート81aおよびステート81bは、命令52aが副作用のない命令であるので、グループ80に分類される。

0131

図41では、グループ80について、レジスタ値「%2」が同じ計算結果となるステートをマージすると、ステート81aおよびステート81bは、1つのステートに戻ってしまう。この様な場合には、ステートの分割とマージを繰り返す可能性があるためマージを行わない。また、グループ80は解除される。さらに、ステート81bは、最終的に無限ループとなってタイムアウトとなる。ステート81aは、以後、whileループの4回目が終わるまで、whileループの3回目と同様の処理が行われる。

0132

図42は、whileループの5回目の一例を説明する図である。図42では、ソースコード45のwhileループの5回目について説明する。

0133

図42のステート81aは、whileループの4回目のステートID「State1」に対応する。ステート81aは、まず、命令52について評価される。命令52のレジスタ値「%1」は、表53dに示すように演算子「+」のミュータントに対応した値となる。ここで、「a+b」と「a*b」とは、レジスタ値「%1」が「4」で結果が同じである。従って、図42では、「%1=4」について、ステートID「State1」が更新されステート82aとなる。このとき、命令52では、ステート81aのミューテーション記述子のうち、ミューテーション記述子「{}」、および、ミューテーションIDが「1」であるミューテーション記述子について評価される。ステート82aは、生成されたグループ82に分類される。なお、グループ82は、説明の便宜上「Group5」と称する。

0134

続いて、ステート82aは、命令52aについて評価される。命令52aのレジスタ値「%2」は、表56lに示すように演算子「>」のミュータントに対応した値となる。このとき、命令52aでは、ステート82aのミューテーション記述子のうち、ミューテーション記述子「{}」、および、ミューテーションIDが「2」であるミューテーション記述子について評価される。ここで、「%1>c」と「%1!=c」とは、レジスタ値「%2」が「0」で結果が同じである。従って、図42では、「%2=0」について、ステートID「State1」が更新されステート83aとなる。同様に、「%1>=c」は、レジスタ値「%2」が「1」となり、他に同じ結果となるミュータントがない。従って、図42では、「%2=1」について、ステートID「State15」であるステート83bが生成される。また、図42では、ステート83aおよびステート83bは、命令52aが副作用のない命令であるので、グループ82に分類される。グループ82に属するステート83aおよびステート83bは、並列して、つまり同時に評価される。

0135

グループ82は、レジスタ値「%2」が同じ計算結果となるステートがないため、マージを行わない。また、グループ82は解除される。さらに、ステート83aは、while文を抜けて「4」を返して終了される。また、ステート83bは、もう一度whileループを行った後、「5」を返して終了される。

0136

図43から図46は、whileループの2回目の一例を説明する図である。図43から図46では、ソースコード45のwhileループの2回目について、ステートID「State7」で示されるステート68b側を説明する。

0137

図43のステート68bは、whileループの1回目のステートID「State7」に対応する。ステート68bは、まず、命令52について評価される。命令52のレジスタ値「%1」は、表53eに示すように演算子「+」のミュータントに対応した値となる。ここで、「a+b」と「a*b」とは、レジスタ値「%1」が「4」で結果が同じである。従って、図43では、「%1=4」について、ステートID「State7」が更新されステート84aとなる。このとき、命令52では、ステート68bのミューテーション記述子のうち、ミューテーションIDが「1」であるミューテーション記述子について評価される。同様に、「a−b」と「a%b」とは、レジスタ値「%1」が「0」で結果が同じである。従って、図43では、「%1=0」について、ステートID「State16」であるステート84bが生成される。「a/b」は、レジスタ値「%1」が「1」となり、他に同じ結果となるミュータントがない。従って、図43では、「%1=1」について、ステートID「State17」であるステート84cが生成される。また、図43では、ステート84a、ステート84bおよびステート84cは、生成されたグループ84に分類される。なお、グループ84は、説明の便宜上「Group6」と称する。グループ84に属するステート84a、ステート84bおよびステート84cは、並列して、つまり同時に評価される。

0138

図44では、ステート84aは、命令52aについて評価される。命令52aのレジスタ値「%2」は、表56mに示すように演算子「>」のミュータントに対応した値となる。このとき、命令52aでは、ステート84aのミューテーション記述子のうち、ミューテーションIDが「2」であるミューテーション記述子について評価される。ここで、「%1>c」と「%1!=c」と「%1>=c」とは、レジスタ値「%2」が「1」で結果が同じである。従って、図44では、「%2=1」について、ステートID「State7」が更新されステート85aとなる。

0139

ステート84cは、命令52aについて評価される。命令52aのレジスタ値「%2」は、表56nに示すように演算子「>」のミュータントに対応した値となる。このとき、命令52aでは、ステート84cのミューテーション記述子のうち、ミューテーションIDが「2」であるミューテーション記述子について評価される。ここで、「%1>c」と「%1!=c」と「%1>=c」とは、レジスタ値「%2」が「1」で結果が同じである。従って、図44では、「%2=1」について、ステートID「State17」が更新されステート85bとなる。ステート85aおよびステート85bは、命令52aが副作用のない命令であるので、グループ84に分類される。

0140

図45では、ステート84bは、命令52aについて評価される。命令52aのレジスタ値「%2」は、表56oに示すように演算子「>」のミュータントに対応した値となる。このとき、命令52aでは、ステート84bのミューテーション記述子のうち、ミューテーションIDが「2」であるミューテーション記述子について評価される。ここで、「%1==c」と「%1<=c」とは、レジスタ値「%2」が「0」で結果が同じである。従って、図45では、「%2=0」について、ステートID「State16」が更新されステート86aとなる。同様に、「%2=1」について、ステートID「State18」であるステート86bが生成される。ステート86aおよびステート86bは、命令52aが副作用のない命令であるので、グループ84に分類される。

0141

図46では、グループ84について、レジスタ値「%2」が同じ計算結果となるステートがマージされる。図46では、ステート85a、ステート85bおよびステート86bがマージされ、ステートID「State7」が更新されステート87aとなる。同様に、図46では、ステート86aは、マージされる相手がいないので、そのままステートID「State16」が更新されステート87bとなる。ステート87aは、最終的に無限ループとなってタイムアウトとなる。また、ステート87bは、while文を抜けて「−1」を返して終了される。

0142

図47は、各ステートの割り振りの一例を説明する図である。図47に示すように、本具体例では、ミュータントをkillできなかったことを示すグループ88に、ステートID「State1」のステート83aを割り振る。すなわち、グループ88は、テスト合否が「Pass」となるステートである。また、本具体例では、ミュータントをkillできたことを示すグループ89に、「State2」のステート65b、「State8」のステート75b、「State13」のステート79b、「State15」のステート83bおよび「State16」のステート87bを割り振る。すなわち、グループ89は、テスト合否が「Fail」となるステートである。また、本具体例では、無限ループでタイムアウトとなるグループ90に、「State7」のステート87aおよび「State14」のステート81bを割り振る。なお、グループ90のステートは、テスト合否について、「Pass」および「Fail」のどちらとしてもよいが、本具体例では、例えば、「Fail」とする。本具体例に示すように、解析装置100は、高次ミューテーションについても状態数を減らしながら実行することができる。また、解析装置100は、従来と比較して、状態分割の回数を低減することができる。

0143

このように、解析装置100は、ソースコード内の要素をミュータントに変化させるメタ関数に置換してコンパイルした中間コードを実行する際に、メタ関数に対応するミューテーション演算について、ミュータントの変化を示すミューテーション記述子の集合を保持する。解析装置100は、ミューテーション記述子それぞれの命令を評価する。解析装置100は、ミューテーション記述子の集合のうち、命令の評価結果が同じとなる1つ以上のミューテーション記述子を選択する。解析装置100は、選択されたミューテーション記述子と、ミューテーション演算、または、命令の評価前のミューテーション記述子の集合である第1のステートとの直積を算出して第2のステートを生成する。解析装置100は、生成された第2のステートのミューテーション記述子それぞれの命令を評価する際に、第2のステートが複数ある場合には、当該複数の第2のステートを1つのグループとして、該グループ内の第2のステートそれぞれに対して並列に命令を評価する。解析装置100は、グループ内における命令の評価結果に基づく第3のステートのうち、該評価結果が同じとなる第3のステートをマージする。その結果、高次ミューテーションの状態数を削減できる。

0144

また、解析装置100は、副作用がない命令が続く間、グループ内で第3のステートをマージする。その結果、ステート、つまり状態数を削減できる。

0145

また、解析装置100は、副作用がない命令以外の命令に到達すると、グループを解消して第2のステートの命令を評価する。その結果、無駄な状態分割を抑制できる。

0146

また、解析装置100は、マージを行うことで、第1のステートまたは第2のステートに戻る場合には、マージを行わない。その結果、分割とマージを繰り返すことを抑止できる。

0147

なお、上記実施例では、中間コードの一例としてLLVMビットコードを用いたが、これに限定されない。例えば、Java(登録商標)VMで実行可能なJavaバイトコード等を用いてもよい。

0148

また、図示した各部の各構成要素は、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各部の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷使用状況等に応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、コンパイラ132と、状態管理部133と、命令評価部134とは統合されてもよい。また、図示した各処理は、上記の順番に限定されるものではなく、処理内容を矛盾させない範囲において、同時に実施してもよく、順序入れ替えて実施してもよい。

0149

さらに、各装置で行われる各種処理機能は、CPU(またはMPU、MCU(Micro Controller Unit)等のマイクロ・コンピュータ)上で、その全部または任意の一部を実行するようにしてもよい。また、各種処理機能は、CPU(またはMPU、MCU等のマイクロ・コンピュータ)で解析実行されるプログラム上、またはワイヤードロジックによるハードウェア上で、その全部または任意の一部を実行するようにしてもよいことは言うまでもない。

0150

ところで、上記の実施例で説明した各種の処理は、予め用意されたプログラムをコンピュータで実行することで実現できる。そこで、以下では、上記の実施例と同様の機能を有するプログラムを実行するコンピュータの一例を説明する。図48は、解析プログラムを実行するコンピュータの一例を示す図である。

0151

図48に示すように、コンピュータ200は、各種演算処理を実行するCPU201と、データ入力を受け付ける入力装置202と、モニタ203とを有する。また、コンピュータ200は、記憶媒体からプログラム等を読み取る媒体読取装置204と、各種装置と接続するためのインタフェース装置205と、他の情報処理装置等と有線または無線により接続するための通信装置206とを有する。また、コンピュータ200は、各種情報を一時記憶するRAM207と、ハードディスク装置208とを有する。また、各装置201〜208は、バス209に接続される。

0152

ハードディスク装置208には、図1に示した置換部131、コンパイラ132、状態管理部133、命令評価部134および出力部135の各処理部と同様の機能を有する解析プログラムが記憶される。また、ハードディスク装置208には、命令記憶部121、評価結果記憶部122、実行状態集合記憶部123、テスト結果記憶部124、および、解析プログラムを実現するための各種データが記憶される。入力装置202は、例えば、コンピュータ200のユーザから操作情報、管理情報等の各種情報の入力を受け付ける。モニタ203は、例えば、コンピュータ200の管理者に対して結果画面、管理情報の画面および各種画面を表示する。媒体読取装置204は、記憶媒体からソースコード、テスト項目およびミューテーションオペレータリストを読み取る。インタフェース装置205は、例えば印刷装置等が接続される。通信装置206は、例えば、図1に示した通信部110と同様の機能を有し図示しないネットワークと接続され、他の情報処理装置と各種情報をやりとりする。

0153

CPU201は、ハードディスク装置208に記憶された各プログラムを読み出して、RAM207に展開して実行することで、各種の処理を行う。また、これらのプログラムは、コンピュータ200を図1に示した置換部131、コンパイラ132、状態管理部133、命令評価部134および出力部135として機能させることができる。

実施例

0154

なお、上記の解析プログラムは、必ずしもハードディスク装置208に記憶されている必要はない。例えば、コンピュータ200が読み取り可能な記憶媒体に記憶されたプログラムを、コンピュータ200が読み出して実行するようにしてもよい。コンピュータ200が読み取り可能な記憶媒体は、例えば、CD−ROMDVDディスクUSBメモリ等の可搬型記録媒体、フラッシュメモリ等の半導体メモリハードディスクドライブ等が対応する。また、公衆回線インターネット、LAN等に接続された装置にこの解析プログラムを記憶させておき、コンピュータ200がこれらから解析プログラムを読み出して実行するようにしてもよい。

0155

100解析装置
110通信部
111 入力部
112 表示部
113 操作部
120 記憶部
121命令記憶部
122 評価結果記憶部
123実行状態集合記憶部
124テスト結果記憶部
130 制御部
131置換部
132コンパイラ
133状態管理部
134 命令評価部
135 出力部

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ