RIP:香川大学 古川善吾先生(日本発のテスト技法の歴史)

JaSST東京共同実行委員長を務められていた香川大学の古川善吾先生が3月30日に逝去されました( http://aster.or.jp/obituary/furukawa.html )。先生は私と同学年で、若くはないですが逝くのには早すぎる年齢でしたので突然の訃報に驚きました。

先生とは2006年1月に開催されたJaSST'06東京で初めてお会いしましたが、実は「古川善吾」というお名前は1980年代前半から日立製作所のAGENTというツールの名前とともに存じあげていましたので、情報交換会の場でお話しさせていただいたのを覚えています。その後も毎年JaSSTでお会いする度にご挨拶させていただいていました。

このAGENTは私のソフトウェアテストへの取り組みの原点の一つと言っても過言ではありません。昨年、デブサミ10周年記念書籍「100人のプロが選んだソフトウェア開発の名著・君のために選んだ1冊」に、テスト担当チームに配属された新人さんに贈りたい1冊としてG.J. Myersのソフトウェア・テストの技法(The Art of Software Testing)をあげて「ソフトウェアテストにはライフワークの価値がある」というタイトルで寄稿しました。
その中で以下のように書いています。

  : 原因結果グラフという技法があることを知ったのもこの本です。
  : 1984年頃に日立製作所が原因結果グラフからテスト項目を作成
  : するツールAGENTを開発していることを日立評論で読んだときに
  : は論理的でスマートな方法に憧れの念を覚えました。その後、
  : 自分たちもテスト要因の分析や直交表ベースの組合せを支援する
  : ATAFというテスト項目設計支援システムを開発しましたが、この
  : 憧れが開発のモチベーションのひとつであったことは確かです。

AGENTは日本のテスト設計ツールの草分けでもあります。2009年に出版された「ソフトウェア・テストPRESS Vol.9」で私は「続・ソフトウェアテスト・ヒストリー 日本編」を寄稿しましたが、その中のコラム「日本で考案されたテスト技法」で日本発のテスト技法としてAGENT/機能図式(日立製作所)、直交表(富士通)、CFD法(NEC)をあげました。AGENT/機能図式については以下のように書いています。

  : 1980年代にはいって日本でもテスト技法の考案、ツールの開発が
  : 行われました。
  : ◆ AGENT/機能図式（日立製作所）
  : 1980年に日立製作所で、Elmendorf(原因結果グラフ技法の考案 
  : 者)の論文や、Myersの"The Art of Software Testing"を参考に
  : 原因結果グラフからテストケースを生成するツールAGENT
  : (Automated GENeration system for Test cases)が開発されまし
  : た。
  : その後、同社では1982年に機能図式と呼ぶ機能仕様表現形式を
  : 考案し、AGENTをエンハンスしています。
  : 機能図式では、機能仕様の動的な部分を状態遷移で、静的な部
  : 分をデシジョンテーブルあるいは原因結果グラフで表現し、これら
  : を組み合わせてテストケースを生成しています。
  : 1984年以後の適用状況やエンハンス状況が不明なのが残念です。

振り返ってみると、1980年代前半は日本の各コンピュータメーカーが競い合って伸びていった時代であり、その中でソフトウェア技術者も他社の状況を調査して切磋琢磨していました。当時は私は(古川先生も)30歳前後でいろいろな資料を調べながら、テストや検査の技術開発に取り組んでいました。当時の日立評論のAGENTの資料のコピーは今でももっています。古川先生も日立の研究所で新しいテスト技術の開発に必死で取り組まれていたことと思います。以下はソフトウェア・テストPRESSの記事を執筆するときに調査したAGENT関連の論文です。

<AGENT関連の参考文献>
古川善吾・野木兼六, 機能テストのためのテストケース作成法について, 情報処理学会第21回全国大会予稿, pp.367-368, 1980
古川善吾・野木兼六・越智毅, 機能テストのためのテスト項目作成手法について, 情報処理学会ソフトウェア工学研究会資料16-2, Vol.1980 No.31, 1980-SE-016, 1980
古川善吾・野木兼六・小川茂・越智毅, ソフトウェアテスト項目作成支援システムAGENTの開発, 情報処理学会第22回全国大会予稿, pp.323-324, 1981
古川善吾・野木兼六・竹内久, ソフトウェアテスト項目作成支援システムAGENTにおけるグラフチェック支援機能の開発, 情報処理学会第24回全国大会予稿, pp. 357-358, 1982
古川善吾・野木兼六・徳永健司・小森真一, ソフトウェアテスト項目作成支援システムAGENTにおける仕様記述法の拡張, 情報処理学会第25回全国大会予稿, pp.437-438, 1982
古川善吾・車谷博之・野木兼六・徳永健司, ソフトウェアテスト項目作成支援システムAGENT-IIの開発と評価, 情報処理学会ソフトウェア工学研究会資料28-8, Vol.1982 No.57, 1982-SE-028, 1983
野木兼六・古川善吾・保田勝通, ソフトウェアテスト項目作成支援システム, 日立評論, 66(3), pp.29-32, 1984
古川善吾・野木兼六・徳永健司, AGENT: 機能テストのためのテスト項目作成の一手法, 情報処理学会論文誌, 25(5), pp.736-744, 1984

古川先生は、その後、日立製作所から九州大学、香川大学へと移られましたが、ずっとソフトウェアテストの研究に取り組まれました。正にソフトウェアテストをライフワークとされた訳です。これまでJaSSTを始め日本のソフトウェアテストコミュニティに多大な貢献をされてきましたが、今後は先生の遺志を継いで、私も少しでも貢献できるように取り組んでいきたいと思います。
ご冥福をお祈りいたします。

ソフトウェア品質モデルの歴史(3)－品質モデルの開発と標準化

前回の記事で「Wulfが最初にソフトウェアの品質特性を体系化した」というのは言い過ぎであると書きました。では、いつ誰により体系化されたのでしょうか。
　 日本の書籍では、Wulfの後は「1976年にBoehmが国防省の要請に応じて研究し品質モデルを発表した」と書かれているものが多いのですが、実はこれも誤っているところがあります。
　 最初に品質特性を体系化し品質モデルを提案したのはBoehmというのは間違いないと思います。Boehmの品質モデルに関する文献は以下の3件あります。

[1] "Characteristics of Software Quality," TRW Software Series, TRW-SS-73-09, December 1973
[2] B. Boehm, J. Brown and M. Lipow, "Quantitative evaluation of software quality," 2nd ICSE, 1976
[3] "Characteristics of Software Quality," TRW Series of Software Technology 1, North-Holland, 1978

[1]はTRW社のBoehmらがNBS(National Bureau of Standards,米国標準局)の委託を受けて研究したレポートです。[2]は1976年に開催された第2回ICSEで発表された論文で、これによりBoehmの品質モデルが広く知られるようになりました。[3]はそれまでの発表レポートや論文も含めて研究成果を書籍化したもので、[1]のレポートや[2]の論文で書かれた内容も含まれています。
　 入手できた文献[2][3]を読むと、1973年のTRWレポートで既に品質特性の体系化、品質モデルの構築、メトリクスの開発に関して報告されていることが分かります。
　 以上から、(1976年ではなく)1973年にBoehmらが(国防省ではなく)米国標準局NBSの委託を受けて品質モデルを開発したのが最初というのが正確な経緯だと思います。
 

つぎに品質モデルを体系化したのは米国空軍の委託を受け1977年に以下のレポートを発行したGE社のMcCall、Richards、Waltersです。

J. McCall, P. Richards and G. Walters, "Factors in Software Quality," RADC-TR-77-369, Rome Air Development Center, 1977
   Vol-1 Concepts and Definitions of Software Quality
   Vol-2 Metric Data Collection and Validation
   Vol-3 Preliminary Handbook on Software Quality for an Acquisition Manager

McCallらは、1977年以前に発表された品質特性に言及している先行研究論文31件から、ソフトウェア品質要因(Software Quality Factor)として55個を抽出し、それらを集約整理・体系化してソフトウェア品質モデルを構築しました。利用者視点(ファクタ)、開発者視点(クライテリア)、および測定可能なレベル(メトリクス)の三階層構造で結び付けた最初のソフトウェア品質モデルとして高く評価されており、後の品質モデルの標準化作業でも参考にされました。

品質モデルの国際標準化作業は1985年から開始され1991年に最初の国際規格ISO/IEC 9126: Information technology - Software product evaluation - Quality characteristics and guidelines for their useが発行されました(翻訳版はJIS X0129が1994年に制定)。
　 現在は、後継のISO/IEC 25000 Software product Quality Requirement and Evaluation（SQuaRE）シリーズの制定作業が続けられています。

ソフトウェア品質モデルの歴史(2)－Wulfの品質の定義

ソフトウェア品質特性の歴史について日本の書籍では「1973年にWulfがソフトウェアの品質特性を最初に体系化した」と書かれているものが多いのですが、米国の論文をいろいろ調べても「Wulfが最初に体系化した」というように書かれているものは見あたりません。また、Wulfの参考文献が"Programming Methodology"と記述されていたのでインターネットでいろいろ検索しましたが見つけられませんでした。更に、Wulfという人物についてはソフトウェア品質に関する論文や書籍で名前を見かけたことがなかったので、一体どこのどういう人だったのだろうかとずっと気になっていました。
　 インターネットでの検索を続けているうち、一昨年(2010年)初めにようやく文献の正確なタイトルが以下であることをつきとめました。

"Report of a Workshop on Programming Methodology," Proceedings of a Symposium on the High Cost of Software, Naval Postgraduate School, Monterey, California, September 1973

すなわち、Wulfの文献は1973年9月に開催されたHigh Cost of Softwareシンポジウムの論文集に採録されているWorkshopの報告書だったのです。この論文集についても探すのに苦労しましたが最終的には国会図書館にあることが分かりコピーを入手できました。
　 この論文集を読んで分かったことは以下のとおりです。

• Wulfの文献は"Report of a Workshop on Programming Methodology"というタイトルで分かるように、ソフトウェア品質特性を直接的にとりあげた論文ではなく、シンポジウムにおけるWorkshopの報告書です。
• このシンポジウムは、ソフトウェア開発コストの増大への危機感から、米国の空軍、陸軍、海軍の研究部門が共同で1973年9月に開催したもので、専門家を招集して解決策が検討されました。ちなみに基調講演は当時TRW社のBarry Boehmが"The High Cost of Software"というタイトルで講演。
• シンポジウムには97名が出席し、5つのworkshopに分かれて議論が進められました。この内の一つがWulfが議長を務めた"Workshop 3 - Programming Methodology"です。このWorkshopでは、開発技法の適用、評価技術の開発、ツールの開発などの提案がまとめられました。
• 品質特性に関する記述は、Workshop報告書のIntroductionの章にあり、プログラムが「よい(good)」というのはどういうことなのかという議論を進めるための意識合わせのために書かれたものです。「正しい(correct)プログラム同士でも我々は重要な差を認識できる。それは少なくとも以下の7つの次元の中の一つ以上で認識される差である」ということが書かれ、各々の特性が説明されています。すなわち、"誤りがない"こと以外に考慮すべき品質特性を示したものと言えます。

maintainability/modifiability (保守性／更新性)
robustness (堅牢性)
clarity (明解性)
performance (性能)
cost (コスト)
portability (移植性)
human factor (人間的要素)

ただし、これをもって「Wulfが最初にソフトウェア品質特性を体系化した」というのは言い過ぎで、私はBoehmが1976年の論文で

"Wulf identified and provided concise definitions of seven important and reasonably non-overlapping attributes"

と書いたように「Wulfは7つの重要な合理的に重複しない属性を識別し簡潔に定義した」という程度の表現がよいと思います。
　 なお、Wulfは当時はカーネギーメロン大学のコンピュータ・サイエンスの教授でプログラミングシステムやコンピュータアーキテクチャが専門の方でした。

ソフトウェア品質モデルの歴史(1)－最初の論文

「品質」と一口に言っても様々な側面があります。ソフトウェア品質モデルは、品質を構成する要素(特性)を分類するとともに構造化してソフトウェア品質をとらえようとするもので、JIS X0133(ISO/IEC 14598)では「品質要求及び品質評価の基礎を与えるような特性の集合及び特性間の関係」と定義されています。

品質特性やメトリクスに関する初期の論文に次の1968年のRubeyの論文があります。

Rubey, R. J. and R. D. Hartwick, "Quantitative Measurement of Program Quality," Proceedings," ACM National Conference,1968, pp. 671-677.

この論文には参考文献が書かれていないので、これよりさかのぼることはできないのですが、Boehmは彼の品質特性に関する論文の中で次のようにRubeyらが初めて系統だった方法でソフトウェア品質の評価方法の開発に取り組んだと書いています。

"Development of methods for evaluating software quality appears to have first been attempted in an organized way by Rubey and Hartwick."

また、McCallらが1977年にまとめたレポート"Factors in Software Quality"でも、収集調査された先行研究論文の中で最も古いものがRubeyの論文なので、恐らくこれがソフトウェアの品質特性やメトリクスに関する最初のものだと思われます。

この論文でRubeyは品質のAttributes(属性)とMetrics(メトリクス)を定義しています。最上位の属性として次の7つをあげています。

A1 - Mathematical calculations are corrected performed. (数学演算が正確に実行される)
A2 - The program is logically correct. (プログラムは論理的に正しい)
A3 - There is no interference between program entities. (プログラムの実体間で相互干渉がない)
A4 - Computation time and memory usage are optimized. (計算時間やメモリ使用量が最適である)
A5 - The program is intelligible. (プログラムは理解しやすい)
A6 - The program is easy to modify. (プログラムは修正しやすい)
A7 - The program is easy to learn and use. (プログラムは学びやすく使いやすい)

更に各属性を下位の属性に展開して定義しています。例えばA5は次のように詳細化されています。

A5 - The program is intelligible. (プログラムは理解しやすい)
A5.1 - Consistent coding techniques are set up and followed. (一貫したコーディング技法が適用されている)
A5.2 - Frequent comments are inserted to clarify the code. (コードを明確化するための注釈が頻繁に入れられている)
A5.3 - Instructions are not modified during program execution. If they are modified, however, such modifications are clearly identified. (プログラムの実行中に命令が修正されない。修正がある場合は明確に識別できる)
A5.4 - Indirect methods of referencing quantities are clearly identified. (数量を参照する間接的な方法が明確に識別できる)
A5.5 - The real-time constraints of a program are clearly identified. (プログラムの実時間制約が明確に識別できる)
A5.6 - The program flow is easy to follow. (プログラムの流れが追いやすい)
A5.7 - Symbolic names and labels are clear and meaningful. (シンボル名やラベルは明確で意味をもっている)

そして下位の属性に対してメトリクスの例を示しています。例えば、A5.3のメトリクスM5.3として次の式が示されています。

M5.3 ＝ max [0,100(I－2N＋C)/I]
　ここで
　　I ＝ プログラム中の命令数
　　N ＝ プログラム実行中に修正される命令数
　　C ＝ 修正されたことを示すコメントをもつ修正命令の数

Rubeyの評価方法は、対象は「プログラム」ですが、評価のアプローチそのものは現在の品質モデルやメトリクスの原型になっていると思います。

組み合わせテストの歴史(1)

富士ゼロックスの秋山さんのHAYST法、マイクロソフトのPICTや岩通ソフトシステムの鶴巻さんのPictMasterといったツールのお蔭で、日本で直交表テストやペアワイズテストがかなり広まっていると思います。
　最近、このようなテスト技法を総称して「組み合わせテスト(Combinatorial testing)」と呼ぶことが一般的になってきています。ISTQB/JSTQBのソフトウェアテスト標準用語集ではまだこの用語は掲載されておらず、直交表テスト(Orthogonal array testing)とペアワイズテスト(Pairwise testing)が掲載されているだけなので、「組み合わせテスト(Combinatorial testing)」という呼び方は比較的新しいものだと言えます。組み合わせテスト技法はGrindalらの論文ではつぎのように定義されています。

Combination strategies are test-case selection methods where test cases are identified by combining values of the different test object input parameters based on some combinatorial strategy.
『何らかの組み合わせ手法に基づいて入力パラメタの値を組み合わせることによりテストケースを選択する技法』

M. Grindal, J. Offutt, S. Andler, "Combination Testing Strategies: A Survey", Software Testing, Verification and Reliability, Vol. 15, No. 3, pp. 167-199, 2005

今月17日～21日にカナダ・モントリオールで開催されたICST 2012 (International Conference on Software Testing, Verification and Validation)に参加したのですが、4月17日には組み合わせテストのワークショップ(Workshop on Combinatorial Testing)にも参加しました。
　ワークショップの最後の方で少しディスカッションの時間があったので飛び入りで次の資料を元に組み合わせテストの歴史を紹介し、このテスト技法が日本発のものであることを話しました。

History of combinatorial testing

なお、この歴史の資料は実は2008年7月に開催された「PictMaster勉強会」で発表した次の資料を元に最新化、英語化したものです。

組み合わせテストの歴史(PictMaster勉強会)20080717

ワークショップではMicrosoftでPICTを開発したJacek Czerwonkaさん、NISTでACTSを開発しワークショップの議長団でもあるRich Kuhnさん、Raghu Kackerさん、Yu(Jeff) Leiさん(Texas大Arlington校の准教授、IPOという組み合わせ技法を開発)らと親交を結ぶことができました。
　組み合わせテストの歴史の詳細はこのBlogで追い追い紹介していきます。

データフローテストの歴史

データフローテストは、プログラムの制御フローのパスを選択する際に、制御フローテストが分岐に着目するのに対して、変数の定義、使用の関係に着目してテストケースを設計する技法です。パス選択の基準として、すべての定義－使用のペアを実行する全duパス法(ADUP法)や，各データについて定義－使用のペアを最低一つ含むようにする全使用法(AU法)などがあります。
　コンパイラの分野では1960年後半からIBM社のAllenらによりプログラム最適化技術としてデータフロー解析の研究が進められていました。ちなみに、Allen女史はIBM社初の女性のフェローで、また2006年に女性として初めてチューリング賞を受賞されています。

F. E. Allen and J. Cocke, "A program data flow analysis procedure," Communications of the ACM, 19(3):137-146, March 1976
F. E. Allen, "The History of Language Processor Technology in IBM," IBM Journal of Research and Development, Vol. 25, No. 5, pp. 535-548, Sep. 1981

テスト技術としてデータフローテストを提案した最初の論文は1974年の米国Colorado大学のOsterweilとFosdickのものと思われますが、彼らのデータフロー解析法はコンパイラの最適化技術と似ているが観点や目的は異なると書いています。なお、OsterweilらはDAVE(Documentation, Assertion generating, Validation, Error detection)という解析ツールも開発しています。

L. D. Fosdick and L. J. Osterweil, "Data flow analysis in software reliability," Comput. Surveys, vol. 8, pp. 305, Sept. 1976
L. J. Osterweil and L. D. Fosdick, "Data Flow Analysis as an Aid in Documentation, Assertion Generation, Validation and Error Detection," University of Colorado Department of Computer Science Technical Report No. CU-CS-055-74, 1974
L. J. Osterweil and L. D. Fosdick, "DAVE - A Validation, Error Detection and Documentation System for Fortran Programs," University of Colorado Department of Computer Science Technical Report No. CU-CS-071-75, 1975

なお、オーストラリアのHermanが1976年に以下の論文を発表しています。私は論文が入手できておらず内容未確認ですが、オーストラリアでも早期にデータフローテストの研究が進められていたようです。

P. M. Herman, " A Data Flow Analysis Approach to Program Testing," Australian Computer Journal, Nov. 1976, pp. 92-96

その後、データフローテスト基準の提案や制御フローテストも含めた構造テストの網羅基準間の包含関係(subsume relation)の研究が進められています。たとえば、RappsとWeyukerは条件部で変数が使用される場合(p-use)を基準として追加する提案を行っています。

S. Rapps and E.J. Weyuker, "Data Flow Analysis Techniques for Test Data Selection," Proceedings of the 6th international conference on Software engineering, Tokyo, Japan, Pages: 272 - 278, 1982
S. Rapps and E. J. Weyuker. Selecting software test data using data flow information. IEEE Trans. Softw. Eng., SE-11(4):367-375, Apr. 1985

ソフトウェアテストの歴史年表の更新

先週開催されたJaSST'12に合わせて出版されたJaSST10周年記念誌の付録にソフトウェアテストの歴史年表を提供させていただきました。これに合わせて右サイドバーのWeb Pagesの「ソフトウェアテストの歴史年表」もJaSST10周年版にしました。

付録年表は記念誌編集長(?)の秋山浩一さんのご配慮で、なんとA2の大きさの光沢紙にしていただきましたので、とても立派なものになっています。自宅にちょうどころ合いの額があったので入れてみるとさらに格好よくなりました。ただ、難点は字が小さいので壁に掛けると少し離れた場所からは個々の記述が読めないことです。4つ折りにして机の近くにおいておくほうが使い勝手はよいかもしれません。
　なお、このブログ掲載版は、大西建児さんから誤り指摘を受けて、記念誌に提供した年表から一箇所修正してあります。どこだか分かりますか?

正解はそのうち発表させていただきます・・・
　年表の誤りや漏れに気づかれた方はコメント欄でご指摘ください。

「発表資料集」のページの作成

右サイドバーのWeb Pagesに「発表資料集」のページを作成し、私がこれまで書いたり、発表してきた資料をまとめました。私が就職してソフトウェア検査部門に配属されたのが1976年なので、私のこれまでの活動も歴史として見ていただけるかもしれません(途中にかなりのブランクがありますが)。

掲載した資料の中に1987年のCOMPSACとICQCで発表した論文があります。このうちICQCで発表した論文"Test Case Design Support System"が、AT&T社での直交表テストやPairwiseテストの開発の参考にされたものです。このあたりの経緯は日科技連SQiPのWebコラム「ソフトウェア品質のホンネ 第43回 ソフトウェア品質技術の歴史　その3 (コミュニティ)」(3. 日科技連コミュニティと直交表テスト)で書きました。なお、この二つの論文は英語なのですが、今回、当時の日本語原稿を再生したものもアップロードしておきましたのでご覧ください。

テストカバレッジ基準の歴史(1)

動的解析システムの開発の目的のひとつに、テストの妥当性(あるいは十分性)の評価がありました。この評価の手法として、テスト対象のプログラムを基本要素に分割し、テストで実行された基本要素の割合で妥当性を表現するという方法、いわゆるテストカバレッジが考案されました。基本要素としては、命令コードや判定条件など構造的なものが元になっています。なお、妥当性を評価するテストとしては制御フローテストに限らず、例えばブラックボックステスト技法によるテストの妥当性を構造的観点から評価する場合もあります。
　以下に1970年代に提案されたカバレッジ基準を紹介します。

◆TER(Test Effectiveness Ratio) [J. R. Brown]

私が調査した範囲では、テストの妥当性を示す指標として提案された最初のカバレッジ基準はTRW社のBrownのTER(Test Effectiveness Ratio:テスト有効度)です。TRW社の動的解析システムPACEの中のFLOWと呼ばれるツールで計測し、以下の2つのTERを出力しています。いわゆる命令網羅と分岐網羅(または判定条件網羅)の基準です。

J. R. Brown, "Practical applications of automated software tools," WESCON 1972, TRW Software Series SS-72-05, September 1972
J. R. Brown and R. H. Hoffman, "Evaluating the Effectiveness of Software Verification - Practical Experience with an Automated Tool," AFIPS Fall Joint Computer Conference, December 1972

◆DD-paths, level-i paths  [M. R. Paige, E. F. Miller]

General Research社の動的解析システムRXVPでは、DD-paths(または decision-to-decision paths)及びlevel-i pathsという基準で評価する仕組みが提供されていたようです。
　DD-pathsとは、ある判定文の出口から次の判定文の入り口までのパスのことを意味しています。また、level-i pathsはプログラム中の反復(iterationまたはlooping)のレベルで構造要素を分割するもので、例えばlevel-0 pathは入り口ノードから出口ノードへの単純パス、level-n pathは下位level上で開始終了点をもつループのパスを意味します。

E. F. Miller, M. R. Paige et al., "Structural techniques of program validation," in Dig. 1974 COMPCON, (Feb. 1974), pp. 161-164

◆C0,C1,C2,・・・ [E. F. Miller]

現在、カバレッジの説明の際によく使われるC0やC1と呼ばれる基準は1975年頃にEdward Millerが提案したものです。ただ、Millerはこれらの基準の定義を何回か変更しているので、論文の発表時期により少しずつ定義が異なっています。
　1975年の"The Art and the Theory of Program Testing"(MillerのCxカバレッジに関する論文のうち私が入手した最も早期のもの)では以下のように書かれており、命令網羅はC1、分岐網羅はC2というように現在の定義(命令網羅はC0、分岐網羅はC1)と異なっています。

C0: Programmer's intuition.
C1: Every statement in a program exercised at least once.
C2: Every program predicate outcome exercised at least once.
C3: At least one element of each equivalence class of program flow exercised at least once.
C4: All usefully distinct program flow classes tested with "reliable test data," plus de facto testing of what cannot be tested reliably.
・
・
Cn: A sufficient set of tests so that the tests amount to a formal program proof of correctness.

1977年に開催されたCOMPSACのチュートリアルのテキスト"Tutorial: Program Testing Techniques"に記載されている解説"4. notes on planning and measurement in testing"では

The most common measure is the C1 measure, which requires that every segment in a program be exercised at least once.

と書かれており、C1を分岐網羅(＝every segment)としています。1978年に英国で行ったInfotechのチュートリアルで、Millerは以下の定義を示して「この一年ほど、この考え方を広めている」と言っているので恐らく1977年にC0,C1などの定義を変更したと思われます。

C₀: Every statement executed at least once
C₁: Every segment executed at least once
C₁^p: Every predicate term executed for each outcome
C₂: C₁ coverage plus interior and boundary tests for each iteration
C_i^k: All program paths that involve up to k iterations executed
C_d: C₁ coverage plus single-test execution of all pairs of dependent segments
C_p: All possible successive pairs of segments co-executes
C_t: Function processing of major sub-trees in hierarchical decomposition of segment interconnection

E. Miller, "The Art and the Theory of Program Testing," Proceedings of the Fourth Texas Conference on Computing Systems, Austin, Texas, 1975
Edward Miller, "Tutorial: Program Testing Techniques," COMPSAC'77, IEEE, 1977
A. E. Westley(Editor), Infotech State of the Art Report: Software Testing, Volume 1: Analysis and Bibliography, Infotech International, 1979

◆LCSAJ(Linear Code Sequence And Jump) [M. A. Hennell, et. al]

1976年に英国Liverpool大学のHennel,WoodwardらがLCSAJ(Linear Code Sequence And Jump)triplesを提案しました。現在はLCSAJと呼ばれていますが、当初の論文はLCSAJ triplesという名称でした。triplesと付いているのは、ひとつのLCSAJがソースコード中の開始行、終了行、および飛び先行の3つの数字の組みで表されることによります。
HennellらはTRW社のBrownが示した前述の二つのTER(Hennelらは順にTER1,TER2と番号をつけています)に加えて、LCSAJを使ったより厳しい条件の基準TER3を提案しています。

M. A. Hennell, M. R. Woodward, and D. Hedley, "On program analysis," Information Proc. Lett., vol. 5, pp. 136-140, Nov. 1976

制御フローテストの歴史(3)－動的解析システム

1970年代に入ってプログラム実行時の内部の動きを調べるための動的解析システムの開発が本格化しました。解析の目的としては、プログラムの性能改善に加えて、テスト時に通過したルートを調べることによるテストの十分性の評価があります。McDonnell Douglas社のStuckiによるとこのような解析システムの最初のものは1967年にUCLAのEstrinが開発したものだそうです。当時の代表的なシステムとして、TRW社のPACE(Product Assurance Confidence Evaluator)、McDonnell Douglas社のPET(Program Evaluater and Tester)、General Research社のRXVPがあります。

実行時の動作解析は、対象プログラムのソースを解析して実行プロセスを把握するための命令を事前に挿入しておき(これをinstrumentation(計装)と呼びます)、プログラム実行時にこれらの命令により記録された情報を集計することにより行われました。先の3つのシステムはいずれもFORTRANで書かれたプログラムを対象としています。

このようなinstrumentationによるプログラムの動作解析の有用性を最初に明らかにしたのは、KnuthによるFortranプログラムの実行プロファイル分析だそうです(program "profile"と呼んだのもKnuthが最初)。Knuthは数百本のFortranプログラムの静的な統計データを解析(命令や文の出現頻度)するとともに、17本のプログラムの動的な統計データの解析(命令の実行頻度)を行い性能改善ができることを示しています。そして、このような動的な解析はデバッグ段階でプログラム中のテストされていないセクションを見つけるのに有効であることも指摘しています。

J. R. Brown, et al. "Automated Software Quality Assurance: A Case Study of Three Systems," ACM SIGPLAN Symposium, June 21-23, 1972
L. G. Stucki, "Automatic Generation of Self-Metric Software," WD2144, McDonnell Douglas Astronautics Company, 1972
E. F. Miller, et al., "Structurally based automatic program testing," EASCON-74, October 1974
D. E. Knuth, "An Empirical Study of FORTRAN Programs," Software-Practice and Experience, Vol.1, pp. 105-133, 1971