« 制御フローテストの歴史(3)-動的解析システム | Main | 「発表資料集」のページの作成 »

31 December 2011

テストカバレッジ基準の歴史(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などの定義を変更したと思われます。

C0: Every statement executed at least once
C1: Every segment executed at least once
C1p: Every predicate term executed for each outcome
C2: C1 coverage plus interior and boundary tests for each iteration
Cik: All program paths that involve up to k iterations executed
Cd: C1 coverage plus single-test execution of all pairs of dependent segments
Cp: All possible successive pairs of segments co-executes
Ct: 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)-動的解析システム | Main | 「発表資料集」のページの作成 »