« デシジョンテーブルテストの歴史 | Main | 制御フローテストの歴史(2)-黎明期(カバレッジ計測) »

03 November 2011

制御フローテストの歴史(1)-黎明期(グラフの利用)

制御フローテストは、プログラムの論理の流れを制御フローグラフで表現し、あらかじめ決めた網羅基準(カバレッジ基準)を満たすようにプログラムの中のパスを選択してテストケースを設計する技法です。
ここで「グラフ」とは、ノード(節点・頂点、node)とエッジ(枝・辺、edge)の集合で構成されるもので、数学の一分野であるグラフ理論はこのグラフの性質について研究する学問です。

ソフトウェアの分野でグラフ理論を適用した最初のものは、1960年にIBM社のKarpが書いた以下の論文です。

R. M. Karp, "A note on the application of graph theory to digital computer programming," Information and Control, Vol. 3, pp. 179-190, September, 1960

この論文でKarpはプログラムのフローチャートの判定条件部分をノード、論理の流れや接続の状況をエッジで表した有向線形グラフ(directed linear graph)を書き、更に形式的に扱いやすいようにノード間の接続状況を表す接続行列(connection matrix)を作成してプログラムを解析する方法を示しています。この解析に基づいて、プログラム中の到達しない終端ノードを検出する方法や、接続行列を用いて複数のプログラムを合成(composite)する方法を示しています。
ちなみにKarpは1985年にチューリング賞を受賞しています(計算理論に関する長年の貢献と、特にNP完全理論への貢献に対して)。

ソフトウェアテストの分野では、1963年に米国陸軍化学科のMillerとMaloneyが書いた以下の論文でグラフを利用してテストデータを設計する方法が紹介されたのが最初です。

J. C. Miller and C. J. Maloney, "Systematic mistake analysis of digital computer programs," Communications of the ACM, vol. 6, pp. 58-63, February 1963

この論文では、前述のKarpが示したフローチャートのグラフ化の方法を少し修正したLogical treeを用いて、つぎのようにテストを設計する方法とテスト結果からバグのある箇所を診断する方法を紹介しています。

  • logical tree に基づいてルート解析(入り口から出口へのルート=複数のパスの組合せ)することにより必要なテストに絞り込む
  • プログラム内の各ルートを通過するテスト結果の分析に基づいてバグ(mistake)のある箇所を絞り込む(あるルートのテスト結果がNGの場合、OKとなっている他のルートのテスト結果からどのパスにmistakeがあるのかを判定する)

ただし、ここで紹介された方法はグラフ理論で示されているグラフの性質を利用して解析している訳ではなく、あくまでフローチャートをグラフ表現したものにもとづいて解析するというものです。
本格的にグラフ理論を適用しグラフの性質を利用したテスト技法としては、1976年にMcCabeが発表したプログラムの複雑度を表すサイクロマチック複雑度(cyclomatic complexity)、および基礎パステスト法(Basis Path Testing)ということになると思います。

T. J. McCabe, "A Complexity Measure," IEEE Transactions on Software Engineering, Vol. SE-2, No. 4, pp. 308-320, Dec. 1976

|

« デシジョンテーブルテストの歴史 | Main | 制御フローテストの歴史(2)-黎明期(カバレッジ計測) »