« October 2011 | Main | December 2011 »

November 2011

06 November 2011

制御フローテストの歴史(2)-黎明期(カバレッジ計測)

制御フローテストでは、テスト実行時にプログラム上の意図した箇所が通過したか、どこに分岐したかを計測してテストの十分性を評価するという方法が用いられますが、この計測のためのツールの開発は1960年代前半には開始されています。

IBM社ハイファ研究所(イスラエル)のUrの論文によると1960年代にIBM社のPoughkeepsie事業所でコードカバレッジ・ツールが開発されていたようです。

S. Ur and A. Ziv, "Cross-Fertilization between Hardware Verification and Software Testing," IBM Research Laboratory in Haifa, November 2002

この論文では1964年のWarnerと1967年のHirshの論文が参考文献としてあげられており、前者はハードウェア、後者はソフトウェアのコードカバレッジ・ツールのようです。

※いずれの論文も一般に出版されたものではなくIBM Technical Report(関係者だけに配布?)なので私は内容が確認できていません。当時の状況が分かる貴重な資料なのでIBMさんが100周年記念事業か何かで閲覧可能にしてくれるといいのにと思っています(ちなみにElmendorfの原因結果グラフの論文もIBM Technical Report)。

Beizerの「ソフトウェアテスト技法」では巻末に膨大な数の参考文献が記載されているのですが、この参考文献リストにもこれらの論文があげられており簡単なコメントが書かれています。

C. D. Warner Jr., "Evaluation of program testing," TR 00.1171, IBM Data Systems Devision Development Laboratories, IBM Poughkeepsie, N.Y., 1964
<Beizerのコメント>
  『COBOLとFORTRANソースプログラムを対象にしたハードウェアの命令語モニタについてのいちばん最初の解説書』

I. N. Hirsh, MEMMAP/360, TR-p-1168, IBM System Development Division Product Test Laboratories, IBM Poughkeepsie, N.Y., 1967
<Beizerのコメント>
  『ソフトウェアのステートメントカバレージとブランチカバレージアナライザについての初期の論文』

1960年代の状況はSiemens Corporate Research社のHutchinsの論文でも言及されています。

M. Hutchins, et al., "Experiments on the effectiveness of dataflow- and controlflow-based test adequacy criteria," ICSE, pp. 191-200, 1994

Hutchinsは1969年のIBM社のSchillerの論文を参考文献として、少なくとも1960年代にはソフトウェアのテストの十分性を監視するために制御フローに基づくコードカバレッジ基準が利用されていたと書いています。

H. Schiller, "Using MEMMAP to measure the extent of. program testing," Report TR 1836, IBM Systems Development Division, Poughkeepsie, NY, Feb. 1969
<Beizerのコメント>
  『ステートメント網羅、ブランチ網羅解析についての初期の論文』

Hirsh、Schillerの論文から、1960年代後半にIBM社でMEMMAPというカバレッジ計測ツールが使われていたということが分かります。
その後、1970年代に入って各社で本格的なカバレッジ計測システムの開発と適用が始まります。

|

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

|

« October 2011 | Main | December 2011 »