« ソフトウェアテストの歴史年表の更新 | Main | 組み合わせテストの歴史(1) »

31 March 2012

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

データフローテストは、プログラムの制御フローのパスを選択する際に、制御フローテストが分岐に着目するのに対して、変数の定義、使用の関係に着目してテストケースを設計する技法です。パス選択の基準として、すべての定義-使用のペアを実行する全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

|

« ソフトウェアテストの歴史年表の更新 | Main | 組み合わせテストの歴史(1) »