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

1970年代に入ると、プログラム実行時の内部動作を解析するための動的解析システムの開発が本格化しました。この種の解析では、対象プログラムのソースコードに、実行中のプロセスを把握するための命令をあらかじめ挿入します。この手法はインスツルメンテーション（instrumentation、計装）と呼ばれ、プログラムの実行時にこれらの命令によって記録された情報を収集・集計することで、プログラムの挙動を解析します。

解析の目的には、プログラムの性能改善に加え、テスト時に通過した経路を特定し、いわゆるカバレッジ（網羅率）を測定することでテストの十分性を評価することが含まれます。

McDonnell Douglas社のLeon Stuckiによれば、このようにプログラムの動的な振る舞いを自動的に解析する最初のシステムは、1967年にUCLAのGerald Estrinらが、コンピュータシステムの性能を汎用的に測定する手法として開発したSNUPER COMPUTERであるとされています[1][2]。

インスツルメンテーションによるプログラムの動作解析の有用性を最初に明らかにしたのは、Donald KnuthによるFortranプログラムの実行プロファイル分析であるとされています[3][4]。Knuthは、数百本のFortranプログラムについて命令や文の出現頻度といった静的な統計データを解析するとともに、17本のプログラムに対しては命令の実行頻度に基づく動的な統計データの解析を行い、これにより性能の改善が可能であることを示しました。さらに、こうした動的解析は、デバッグの段階においてテストされていないプログラムのセクションを特定する上でも有効であることを指摘しています。

当時の代表的な動的解析システムとして、TRW社の製品保証評価システムPACE（Product Assurance Confidence Evaluator）のFLOWモジュールや、その拡張版であるTDEM（Test Data Effectiveness Measurement）システム[5]、McDonnell Douglas社のPET（Program Evaluator and Tester）[6]、General Research社のRXVP[7]があります。これら三つのシステムはいずれも当初はFORTRANで書かれたプログラムを対象としていました。

動的解析システムの開発目的の一つに、テストの妥当性（あるいは十分性）を評価することがありました。その方法として、テスト対象のプログラムを基本的な構成要素に分割し、テスト実行時に実際に通過した要素の割合によって妥当性を評価する、いわゆる「テストカバレッジ」の概念が考案されました。

この「基本要素」への分割は、プログラムの構造に基づいて行われるのが一般的であり、何を要素とみなすかという観点から、命令コード、判定条件、実行経路（パス）などに着目したさまざまなカバレッジ基準が提案されました。以下では、1970年代に提案された代表的なカバレッジ基準を紹介します。

TER（Test Effectiveness Ratio）

私が調査した限りでは、テストの妥当性を示す指標として提案された最初のカバレッジ基準は、1972年にTRW社のJohn R. Brown（以下、Brown）が提案したTER（Test Effectiveness Ratio：テスト有効率）です[8]。

Brownは、テストの徹底性（thoroughness）を測定する必要性とその課題について、次のように述べた上で、基準を提案しました（筆者訳）。

私たちは通常、現実的で代表的なテストケースを妥当な数だけ実行し、全てのバグを発見するか、バグが残ってもユーザーに見つからないことを期待します。この方法で生じるリスクの大きさを知るためには、テストがどれほど徹底的であったかを把握する必要があります。問題は、その徹底性をどう測定するかということです。

示されたのは以下の二つ、いわゆる命令網羅（statement coverage）および分岐網羅（branch coverage）の基準で、これらをTERと総称しました。

・TER = 少なくとも1回実行されたステートメントの数 / 実行可能なステートメントの総数

・TER =少なくとも1回実行された分岐の数 / 実行可能な分岐の総数

なお、前述のTRW社のPACEでは、TERを計測し出力する機能が実装されています[9]。

DDパス, level-iパス

1974年、General Research社のEdward F. Miller（以下、Miller）やMichael R. Paigeらは、DDパス（DD-path、またはdecision-to-decision path）およびlevel-iパス（level-i path）と呼ばれるカバレッジ基準を提案しました[10]。

DDパスとは、ある判定文の出口から次の判定文の入り口までの経路を指します。DDパスを網羅することは、分岐網羅と同じ意味を持ちます。

一方、level-iパスは、プログラム中のループ構造およびそのネスト（入れ子）に着目し、構成要素を階層的に分割するカバレッジ基準です。level-0パスは、入口ノードから出口ノードまでの間にループを含まない単純なパスを指します。level-1パスは、level-0パス上に開始点と終了点を持つループのパスを指し、同様に、level-iパスは、下位のlevel-(i-1)パス上に開始点と終了点を持つループのパスを意味します。

前述の動的解析システムRXVPでは、このDDパスおよびlevel-iパスに基づいて、テストの妥当性を評価する仕組みが提供されています。

C0, C1, C2, ・・

テストに関する書籍やブログでは、「C0」や「C1」といった記号を目にすることが多いのではないでしょうか。これらのC0やC1と呼ばれるカバレッジ基準は、1975年にMillerによって提案されたものです。

Millerは1975年11月、General Research社を退職した後、Science Applications社に所属して論文『The Art and the Theory of Program Testing』[11]を発表しました。この論文が、私の調査した限りでは、C0やC1といったCxカバレッジに言及した最も初期の文献です。なお、Millerは1977年にSoftware Research Associates社（後のSoftware Research, Inc.）を創設しています。

この論文では、以下の「テスト網羅基準の階層」が示されています（筆者訳）。

＜テスト網羅基準の階層＞

(C0) プログラマーの直感。

(C1) 全ての文が少なくとも1回実行される

(C2) 全てのプログラム述語結果が少なくとも1回達成される

(C3) プログラムフローの各同値クラスの少なくとも1つの要素が少なくとも1回実行される

(C4) 全ての有用な区別が可能なプログラムフロークラスが「信頼できるテスト」でテストされ、さらに信頼できるテストが不可能な部分については事実上のテストが行われる

(C5) 未知

・

・

(Cn) プログラムが満たすべきニーズに適切であることを証明するテストを提供するのに十分なプログラムアクティビティクラスの集合C2: プログラム述語の結果が全て少なくとも1回実行される

ここで注意すべき点は、当時の定義ではC1が命令網羅、C2が分岐網羅に相当しており、現在一般的に用いられている「命令網羅＝C0」「分岐網羅＝C1」という定義とは異なっていることです。この経緯については後述します。

なお、モジュールレベルのカバレッジ基準であるCxに対し、システムレベルのカバレッジ基準としてS1やS2などの基準も提案されていたようです。ただし、このSxカバレッジに関する発表論文の存在は確認できませんでした。

S1: 全てのモジュールを少なくとも1回ずつコールする

S2: 全てのモジュールについて， 全てのコール方法を少なくとも1回ずつ実行する

LCSAJ（Linear Code Sequence And Jump）

1976年、英国リバプール大学のMichael A. Hennell（以下、Hennell）およびMartin R. Woodwardらによって、LCSAJ（Linear Code Sequence And Jump）の概念が提案されました[12]。

前述のDDパスなどがプログラムの有向グラフに基づく要素であるのに対し、LCSAJはプログラムテキストに基づく要素であり、テキスト中の連続した文のシーケンスとして定義されます。一つのLCSAJは、プログラムの入口（またはジャンプ先）から始まり、ジャンプ命令またはプログラムの出口で終了する構造を持ちます。そして、開始行・終了行・ジャンプ先行という三つの行番号の組で表されるため、当初は「LCSAJ triple（トリプル、三つ組）」とも呼ばれていました。

LCSAJを網羅するテストを行うことは、命令網羅および分岐網羅を達成するだけでなく、さらに厳格な網羅基準を満たすことになります。このためHennellらは、前述のBrownが提案した二つのTERに加えて、LCSAJに基づくより厳しい条件の指標として、以下のTER3を提案しました（なお、HennellらはBrownの二つの指標にそれぞれTER1、TER2という番号を付けています）。

・TER3 =少なくとも1回実行されたトリプルの数 / 実行可能なトリプルの総数

その後、この式中の「トリプル」は「LCSAJ」に言い換えられ（意味は同じ）、さらに、ループや複数のLCSAJの組み合わせを考慮したTER4以降の、より厳格な基準も提案されています[13]。なお、LCSAJはJJ-path（Jump-to-Jump path）と呼ばれることもあります。

Cxカバレッジ名称の混乱

現在、一般的に用いられているCxテストカバレッジの定義では、C0が命令網羅、C1が分岐網羅とされています。多くのテスト関連書籍でも、この定義が採用されています。

しかし、Boris Beizer（以下、Beizer）の著書『Software Testing Techniques』[14]では、命令網羅をC1、分岐網羅をC2と記述しており、現在広く使われている定義とは異なっています。このため、テストカバレッジについて議論する際に認識の違いが生じ、「これは書籍の誤植ではないか」「Beizerの誤解ではないか」といった見解が交わされることもありました。

2008年ころに関連文献を調査したところ、命令網羅をC1、分岐網羅をC2と記述している資料が他にもあることが分かりました。例えば、Beizerの書籍よりも古い、1979年5月発行の「ビジネスコミュニケーション」誌に掲載された記事『ソフトウェアの信頼性向上策』[15]にも、同様の記述が見られます。ところが、同じ雑誌に掲載された別の記事『テストの新技術』[16]では、分岐網羅をC1と記述しており、同一誌内で定義が食い違っていました。しかも、両記事とも参照している論文は異なるものの、どちらもMillerの論文を参考文献として挙げていたため、何が正しいのかますます分からなくなってしまいました。

そこで、さらに1970年代後半に発表されたMillerの論文や記事を調べることにしました。

その結果、次のように論文の発表時期によって定義が変わっており、Miller自身がこれらのカバレッジ基準の定義を変更していたことが判明しました。

• 1975年11月（前述の『The Art and the Theory of Program Testing』[11]）

  C1：命令網羅、C2：分岐網羅

• 1977年7月（『Program Testing: Art Meets Theory』[17]）

  C1：命令網羅、C2：分岐網羅

• 1977年11月（COMPSACのチュートリアルテキスト掲載の解説[18]）

  C1：分岐網羅

• 1978年9月（英国Infotech社主催カンファレンスのチュートリアル[19]）

  以下の定義を示して「この１年ほど、この考え方を広めている」と説明（筆者訳）

C0: 全ての文が少なくとも1回実行される

C1: 全てのセグメントが少なくとも1回実行される

C1p: 全ての述語項が各結果に対して実行される

C2: C1カバレッジに加え、各反復における内部テストと境界テスト

Cik: 最大k回の反復を含む全てのプログラムパスの実行

Cd: C1カバレッジに加え、全ての依存セグメントのペアに対する単一テスト実行

Cp: 可能な全ての連続セグメントのペアが同時実行される

Ct: セグメントの相互接続の階層的分解における主要なサブツリーの機能処理

以上を総合すると、1977年の後半にC0、C1などの定義が変更されたようです。カバレッジ名称の混乱の元は御本尊のMillerでした・・・（笑）

最後に、日本におけるテストカバレッジ計測の黎明期の状況を確認しておきます。

SRA社の岸田氏によると、1978年秋の米国出張中に、前述のMillerと会合し、カバレッジ指標の計測をはじめとする最新のテスト技術について紹介を受けたそうです[20]。さらに、偶然にも両者の社名がいずれもSoftware Research Associatesであったことから意気投合し、日本でセミナーを開催することが決まりました。翌1979年8月に「海外最新テスト技術紹介セミナー」が開催され、大いに好評を博したそうです。

また、時期は1979年初頭と見られますが、日本のSRA社（以下、SRA-J）は、大手ビジネス系ユーザーから「システムテストにおいてカバレッジ指標による評価を行いたい」との要望を受け、米国SRA社（以下、SRA-US）と提携してカバレッジ計測ツールの導入に着手しました。

最初の導入先となったのが野村證券であり、ツールの導入からカバレッジ計測・評価に至るまでの経緯が、1980年2月発行の「ビジネスコミュニケーション」誌に掲載された『実践的ソフトウェアのテスト技法』で報告されています[21]。

この報告によれば、1979年2月からSRA-Jと導入に向けた検討を開始。当初SRA-USが提供していたツール（SCA：Standard Coverage Analyzer）がFORTRAN専用であったため、COBOLプログラムに対応するよう機能を拡張するとともに、システムテストでの評価機能の追加が行われました。1979年夏ごろからは、実際の適用が始まったとされています。

一方、国内のベンダーでも、テストの十分性を評価するための取り組みが始まっており、日立製作所では、汎用コンピュータ向けソフトウェアの生産技術革新を目的として開発されたソフトウェア開発支援システム（CASDシステム）のテスト支援サブシステムの一機能として、TESCO（Test Coverage Manager）を提供していることが、1980年12月発行の「日立評論」誌で報告されています[22]。

こうした動きを受けて、1980年代前半には、テスト技法やツールを活用した品質評価やテスト作業の改善への関心が高まり、「日経コンピュータ」[23]や「日経エレクトロニクス」[24]にも関連する解説記事が掲載されるなど、業界全体にその関心が広がっていきました。

<参考文献>

[1] L. G. Stucki, et al., "New Assertion Concepts for Self-metric Software Validation," Proc. of the International Conference on Reliable Software, pp.59-71, 1975
[2] G. Estrin, et al., "SNUPER COMPUTER - A Computer in Instrumentation Automation," AFIPS Spring Joint Computer Conference, pp. 645-656, 1967
[3] 岸田孝一, ソフトウェア・テスティング 4, bit, Vol.13, No.8, pp.83-88, 共立出版, 1981
[4] D. E. Knuth, "An Empirical Study of FORTRAN Programs," Software-Practice and Experience, vol.1, pp. 105-133, 1971
[5] J. R. Brown, et al., "Automated Software Quality Assurance: A Case Study of Three Systems," ACM SIGPLAN Program Test Methods Symposium, 1972
[6] L. G. Stucki, "Automatic Generation of Self-Metric Software," Proc. IEEE Symposium on Computer Software Reliability, pp.94-100, 1973
[7] E. F. Miller, et al., "Structurally based automatic program testing," EASCON-74, 1974
[8] J. R. Brown, "Practical applications of automated software tools," Proc. of Western. Electronic Show and Convention (WESCON), 1972
[9] J. R. Brown and R. H. Hoffman, "Evaluating the Effectiveness of Software Verification - Practical Experience with an Automated Tool," AFIPS Fall Joint Computer Conference, pp.181-190, 1972
[10] E. F. Miller, M. R. Paige, et al., "Structural techniques of program validation," in Digest of Papers COMPCON, pp.161-164, 1974
[11] E. Miller, "The Art and the Theory of Program Testing," Proc. of the Fourth Texas Conference on Computing Systems, Austin, Texas, 1975
[12] M. A. Hennell, M. R. Woodward, and D. Hedley, "On program analysis," Information Processing Letters, vol.5, No.5, pp.136-140, 1976
[13] M. R. Woodward, D. Hedley, and M. A. Hennell, "Experience with Path Analysis and Testing of Programs," IEEE Trans. on Software Eng., vol.SE-6, No.3, pp.278-286, 1980
[14] B. Beizer, "Software Testing Techniques," Second Edition, Van Nostrand Reinhold Company Limited, 1990 (小野間彰・山浦恒央(訳), ソフトウェアテスト技法, 日経BP社, 1994)
[15] 宮本勲, ソフトウェアの信頼性向上策 (特集：実践的ソフトウェア・エンジニアリングへのアプローチ),  ビジネスコミュニケーション, 16(5), 1979年5月
　https://dl.ndl.go.jp/pid/3286757/1/36
[16] 岸田孝一, テストの新技術 (特集：実践的ソフトウェア・エンジニアリングへのアプローチ),  ビジネスコミュニケーション, 16(5), 1979年5月
　https://dl.ndl.go.jp/pid/3286757/1/29
[17] E. F. Miller, "Program Testing: Art Meets Theory," Computer, vol.10, no.7, pp.42-51, 1977
　https://www.computer.org/csdl/magazine/co/1977/07/01646557/13rRUwh80Lw
[18] E. F. Miller, "Tutorial: Program Testing Techniques," COMPSAC'77, IEEE, 1977
[19] A. E. Westley (Editor), Infotech State of the Art Report: Software Testing, Volume 1: Analysis and Bibliography, Infotech International, pp.73-76, 1979
[20] 岸田孝一, ソフトウェア・グラフィティ, 中央公論事業出版, 2012
[21] 有賀貞一, 実践的ソフトウェアのテスト技法, ビジネスコミュニケーション, 17(2), pp.89-94, 1980年2月
　https://dl.ndl.go.jp/pid/3286766/1/45
[22] 片岡雅憲・葉木洋一・野木兼六, ソフトウェア開発支援システム(CASDシステム), 日立評論, 62(12), pp.33-36, 1980
　https://www.hitachihyoron.com/jp/pdf/1980/12/1980_12_08.pdf
[23] 中島洋・上村考樹・斉野亨, ソフトウェアに品質評価の時代が来る, 日経コンピュータ 1981年10月19日号, pp.38-46, 1981
[24] 田中善一郎・石井茂, 手工業的手法からの脱皮を目指すソフトウェア・テスト, 日経エレクトロニクス 1982年3月15日号, pp.124-152, 1982