« November 2011 | Main | January 2012 »

December 2011

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

|

13 December 2011

制御フローテストの歴史(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

|

« November 2011 | Main | January 2012 »