【連載】第4回:ソフトウェアテストそもそも話～グラフを見たら網羅せよ！（前編）～

最初に、コンピュータプログラムをグラフで表現する手法が登場する以前の状況を確認しておきます。

1947年、Herman GoldstineとJohn von Neumannは、コンピュータの操作命令のシーケンス構造を図式的に示す手法を考案しました[2]。これは、操作または操作の集まりをブロックで表し、それらを操作の流れに従って有向線で結ぶブロック図の形式を取っています。この手法を用いて制御シーケンスを表現した図は、「flow diagram（フロー図）」と名付けられました。

Goldstine は、後に回想録の中で当時の状況を次のように述べています（筆者訳）[3]。

その年の春、フォン・ノイマンと私は、帰納法の反復的な性質を大まかに示すため、極めて粗雑な幾何学的図を考案しました。当初は、プログラミングの補助として試験的に作成したものでした。しかしその年の夏には、このフロー図（私たちが命名）が数学的な問題を論理的に完全かつ正確に表現できる記法として有効であると確信し、プログラミング作業においてまさに不可欠なものだと認識するに至りました。

その後、flow diagramは「flow chart（フローチャート）」とも呼ばれるようになり、1950年代にはプログラマーにとって必須の技法となりました。例えば、本連載の第1回で紹介した1957年出版の『Digital Computer Programming』[4]では、"Flow Charting"という章が設けられ、フローチャートの記法が紹介されています。

フローチャートと制御フローグラフは、どちらもプログラムの処理の流れを表す点では共通していますが、制御フローグラフは処理ブロック内部の詳細を記載せず、各ブロック全体を一つの処理単位として表す点が異なります。

これまで特に説明せずに「グラフ」という言葉を使ってきましたが、本稿における「グラフ」とは、棒グラフや円グラフのような図ではなく、ノード（node：節点・頂点）とエッジ（edge：枝・辺）から構成される図を指します。数学の一分野であるグラフ理論は、このようなグラフの構造や性質について研究する学問です。

コンパイラー開発における取り組み

プログラムの処理の流れを解析する取り組みは、1950年代後半に始まりました。当時「自動プログラミング」とも呼ばれていたコンパイラーの開発の一環として取り組まれていたようです。コンパイラーが効率的なオブジェクトコードを生成するには、対象プログラムの構造を分析し、演算の順序、データの転送位置や配置、サブルーチンの特定、冗長な部分の識別などが求められます。

1959年、Reese Prosserは論文『Applications of Boolean Matrices to the Analysis of Flow Diagrams』において、プログラムの構造を表すフロー図を、各ボックス間の接続関係を示す「connectivity matrix」と名付けたブール行列に変換し、解析する手法を提案しました[5]。ブール行列とは、全ての要素が0または1で構成される行列のことです。

さらに1960年には、IBM社のRichard Karp（以下、Karp）が論文『A Note on the Application of Graph Theory to Digital Computer Programming』において、プログラム解析へのグラフ理論の応用を提案しました[6]。Karpは、プログラムのフローチャートにおける判定条件をノード、論理の流れや接続をエッジとする有向線形グラフ（directed linear graph）を用い、これを形式的に扱いやすくするために「connection matrix」と呼ばれる行列に変換し、解析を行う手法を示しました。この解析により、プログラム内の到達不能な終端ノードの検出や、接続行列を用いた複数プログラムの合成手法なども提案されています（図１、2、3参照）。

その後、1960年代後半にかけて、最適化されたプログラムをコンパイラーが生成するためのさまざまな形式の制御フロー解析の手法が開発されました。1970年には、コンパイラー最適化の分野における第一人者であるIBM社のFrances Allenは論文『Control Flow Analysis』において、これらの手法を解説しています[7]。さらに、Allenらは制御フローグラフを用いてデータフローの関係を導出するデータフロー解析の研究を進めました[8]。この研究は、後のソフトウェアテスト分野におけるデータフローテスト技法にも影響を与えています。

ソフトウェアテストへの適用

ソフトウェアテストの分野では、1963年に米国陸軍化学科のJoan MillerとClifford Maloneyが、論文『Systematic mistake analysis of digital computer programs』において、プログラムの処理の流れを解析してテストデータを設計する手法を初めて提案しました［9］。

この論文では、前述のKarpが示したフローチャートのグラフ化手法を一部修正して作成したlogical tree（論理ツリー）を用いて、以下のようなテスト設計手法と、テスト結果からmistake（バグ）の位置を特定する方法が提案されています。

・論理ツリーに基づいて、プログラムの入り口から出口までのルートを解析し、必要なテストを生成する。すなわち、全ての可能なエントリポイントから入り、全てのパスを少なくとも1回は通過するような条件を考慮してテストを設計する。

・プログラム内の各ルートを通過したテスト結果を分析することで、バグのある箇所を特定する。すなわち、あるルートのテスト結果がNGであった場合、OKとなった他のルートのテスト結果と比較して、どのパスにバグが存在するのかを推定する。

なお、ここで提案された方法は、グラフ理論におけるグラフの性質を利用して解析するものではなく、あくまでフローチャートをグラフとして表現したものを基にした解析手法である点に留意が必要です。

本格的にグラフ理論を応用したテスト技法としては、1976年にThomas McCabe（以下、McCabe）が論文『A Complexity Measure』[10]で提案した、プログラムの複雑さを表すサイクロマチック複雑度（cyclomatic complexity）が挙げられます。McCabeは、プログラムの制御フローをグラフとして捉え（プログラム制御グラフと呼ぶ）、グラフ理論におけるサイクロマチック数（cyclomatic number）の定義と定理を示した上で、これを応用してプログラムの複雑度を定量的に評価する手法を提案しました。

<定義>
n個の頂点、e個の辺、p個の連結成分を持つグラフGのサイクロマチック数V(G)は、V(G) = e - n + p である。
<定理>
強連結グラフGにおいて、サイクロマチック数は線形独立な閉路の最大数に等しい。
※筆者注：用語の意味は以下のとおり。
・連結成分(connected component)
部分グラフのうち、極大で連結なもの
・強連結グラフ(strongly connected graph)
どの頂点からも他の任意の頂点に到達可能な有向グラフ
・閉路(circuit、cycle、loop、closed path などと呼ばれる)
 始点と終点が同じ路(path)のこと
・線形独立な閉路(linearly independent circuits)
選んだ閉路の線型結合により、すべての路を表現できるような集合
・線型結合(linear combination)
複数のベクトルを定数倍して足し合わせること。

プログラムの制御フローをグラフ化しただけでは、強連結グラフにはなりません。McCabeは、プログラム制御グラフにおいて出口から入口へ仮想的な辺（図4の破線10の矢印）を追加することで、強連結グラフの定義を満たし、グラフ理論の定理を適用できるようにしました。

この仮想的な辺を1本追加するため、サイクロマチック複雑度の算出式も、グラフ理論におけるサイクロマチック数の式(v=e-n+p)に補正を加える必要があります。仮想的な辺の追加によって、最終的な式は次のようになります。

サイクロマチック複雑度： v = e - n + 2p
（連結成分ごとに1本の辺を追加するため、各pに+1する形で2pになります）

なお、プログラムにおける「連結成分」とは、メインプログラムや各サブルーチンのプログラム制御グラフを指します。

その後、McCabeはサイクロマチック複雑度の研究を発展させ、線形独立な実行パスの集合に基づくテストケース設計手法として、構造化テスト（Structured Testing）、あるいは基礎パステスト（Basis Path Testing）と呼ばれる手法を提案しています[11]。

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

IBM社ハイファ研究所（イスラエル）のShmuel Urらによれば、1960年代にIBM社のPoughkeepsie事業所でコードカバレッジツールが開発されていました[12]。彼らの論文では、1964年のWarnerによる『Evaluation of program testing』[13]と、1967年のHirshによる『MEMMAP/360』[14]の2件のレポートが参考文献として挙げられています。前者はハードウェア、後者はソフトウェアによるコードカバレッジツールに関するレポートのようです。

また、Siemens Corporate Research社のMonica Hutchinsらも1960年代の状況に言及しています[15]。彼らは1969年のIBM社のSchillerによるレポート『Using MEMMAP to measure the extent of program testing』[16]を引用し、少なくとも1960年代には、ソフトウェアテストの十分性を監視するために制御フローに基づくコードカバレッジ基準が使用されていたと指摘しています。

これらのレポートはいずれもIBM社内のTechnical Reportであるため一般には公開されておらず、内容の詳細は確認できませんが、Beizerの著書『ソフトウェアテスト技法』[1]の参考文献リストでは、それぞれ次のようなコメントが記載されています。

C. D. Warner Jr., Evaluation of program testing, 1964
 　COBOLとFORTRANソースプログラムを対象にしたハードウェアの命令語網羅モニタについてのいちばん最初の解説書。
I. N. Hirsh, MEMMAP/360, 1967
　ソフトウェアのステートメントカバレージとブランチカバレージアナライザについての初期の論文。
H. Schiller, Using MEMMAP to measure the extent of program testing, 1969
　ステートメント網羅、ブランチ網羅解析についての初期の論文。

これらの情報から、1960年代後半にはIBM社においてMEMMAPというコードカバレッジ計測ツールが実際に使用されていたことが分かります。その後、1970年代に入ると、各社で本格的なカバレッジ計測システムの開発と実用化が進められていきます。

以上、前編では、プログラムの制御フローのグラフ化と解析、およびカバレッジの計測の歴史を解説しました。後編では、カバレッジ計測システムとテストカバレッジ基準の歴史を解説します。

<参考文献>

[1] B. Beizer, "Software Testing Techniques," Second Edition, Van Nostrand Reinhold Company Limited, 1990 (小野間彰・山浦恒央(訳), ソフトウェアテスト技法, 日経BP社, 1994)
[2] H. H. Goldstine and J. von Neumann, "Planning and Coding of Problems for an Electronic Computing Instrument," Institute for Advanced Study, Princeton, 1947
[3] H. H. Goldstine, "The Computer from Pascal to Von Neumann," Princeton University Press, pp. 266-267, 1972
[4] D. D. McCracken, "Digital Computer Programming," John Wiley & Sons, 1957
[5] R. Prosser, "Applications of Boolean Matrices to the Analysis of Flow Diagrams," Proc. Eastern Joint Computer Conf., pp. 133-138, 1959
[6] R. M. Karp, "A Note on the Application of Graph Theory to Digital Computer Programming," Information and Control, vol. 3, pp. 179-190, 1960
[7] F. E. Allen, "Control Flow Analysis," Proc. of a symposium on Compiler optimization, SIGPLAN Notices, 5(7), pp.1-19, 1970
　https://dl.acm.org/doi/10.1145/390013.808479
[8] F. E. Allen and J. Cocke, "A Program Data Flow Analysis Procedure," Communications of the ACM, 19(3), pp.137-146, 1976
　https://dl.acm.org/doi/10.1145/360018.360025
[9] J. C. Miller and C. J. Maloney, "Systematic mistake analysis of digital computer programs," Communications of the ACM, vol. 6, pp. 58-63, 1963
[10] T. J. McCabe, "A Complexity Measure," IEEE Transactions on Software Engineering, vol. SE-2, No. 4, pp. 308-320, 1976
[11] T. J. McCabe, "Structured Testing: A Software Testing Methodology Using the Cyclomatic Complexity Metric," NBS Special Publication 500-99, National Bureau of Standards, 1982
[12] S. Ur and A. Ziv, "Cross-Fertilization between Hardware Verification and Software Testing," Software Engineering and Applications Conference (SEA'02), 2002
[13] C. D. Warner Jr., "Evaluation of program testing," Report TR 00.1173, IBM Data Systems Division Development Laboratories, Poughkeepsie, N.Y., 1964
[14] I. N. Hirsh, MEMMAP/360, Report TR P-1168, IBM System Development Division, Product Test Laboratories, Poughkeepsie, N.Y., 1967
[15] M. Hutchins, et al., "Experiments on the Effectiveness of Dataflow- and Controlflow-Based Test Adequacy Criteria," Proc. 16th ICSE, pp. 191-200, 1994
[16] H. Schiller, "Using MEMMAP to measure the extent of program testing," Report TR 00.1836, IBM Systems Development Division, Poughkeepsie, N. Y., February 10, 1969