Test case generation by means of learning techniques

ABSTRACT

Given a program P and a set of alternative programs P, we generate a sequence of test cases that are adequate, in the sense that they distinguish the given program from all alternatives. The method is related to fault-based approaches to program testing, but programs in P need not be simple mutations of P. The technique for generating an adequate test set is based on the inductive learning of programs from finite sets of input-output examples: given a partial test set, we generate inductively a program P'E P which is consistent with P on those input values; then we look for an input value that distinguishes P from P', and repeat the process until no program except P can be induced from the generated examples. We show that the so obtained test set is adequate w.r.t. the alternatives belonging to P. The method is made possible by a practical program induction procedure, which has evolved from recent research in Machine Learning and Inductive Logic Programming.

REFERENCES

• 1: F. Bazzichi and I. Spadafora. An Automatic Generator for Compiler Testing. IEEE Trans. on Software Engineering, 8(4):343- 353, 1982.
• 2: F. Bergadano, Testing Based on Inductive Inference. Tech. Report 92.8.1, CS Dept., University of Torino, 1992.
• 3: F. Bergadano, Inductive Database Relations, IEEE Transactions on Knowledge and Data Engineering, v.5 n.6, p.969-972, December 1993 [doi>10.1109/69.250079]
• 4: Francesco Bergadano , Attilio Giordana , Lorenza Saitta, Automated Concept Acquisition in Noisy Environments, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.10 n.4, p.555-578, July 1988 [doi>10.1109/34.3917]
• 5: F. Bergadano and D, Gunetti. An interactive system to learn functional logic programs. In Proc. 13th Int. Joint. Conf. on Artificial Intelligence, Chambery, France, 1993. Morgan Kaufmann.
• 6: F. Bergadano , S. Matwin , R. S. Michalski , J. Zhang, Learning Two-Tiered Descriptions of Flexible Concepts: The POSEIDON System, Machine Learning, v.8 n.1, p.5-43, Jan. 1992 [doi>10.1023/A:1022682318197]
• 7: T. A. Budd and D. Angluin. Two Notions of Correctness and their Relation to Testing. Acts Informatica, 18:31-45, 1982.
• 8: J. C. Cherniavsky , C. H. Smith, A recursion theoretic approach to program testing, IEEE Transactions on Software Engineering, v.13 n.7, p.777-784, July 1987 [doi>10.1109/TSE.1987.233489]
• 9: N. Choquet. Test Data Generation Using Prolog with Constraints. In Proc. Workshop on Soflware Testing, pages 132-141, Los Alamitos, CA, 1986.
• 10: L. A. Clarke, J. Hassell, and D. J. Richardson. A Close Look at Domain Testing. IEEE Trans. on Software Engineering, 8(4):380- 390, 1982.
• 11: R. A. DeMillo, Completely validated software: test adequacy and program mutation (panel session), Proceedings of the 11th international conference on Software engineering, p.355-356, May 1989, Pittsburgh, Pennsylvania, United States [doi>10.1145/74587.74634]
• 12: R. A. DeMillo, R. J. Lipton, and F. G. Sayward. Hints on Test Data Selection: Help for the Practicing Programmer. IEEE Computer, pages 34-41, 1978. April.
• 13: Richard A. DeMillo , A. Jefferson Offutt, Constraint-Based Automatic Test Data Generation, IEEE Transactions on Software Engineering, v.17 n.9, p.900-910, September 1991 [doi>10.1109/32.92910]
• 14: Richard Denney, Test-Case Generation from Prolog-Based Specifications, IEEE Software, v.8 n.2, p.49-57, March 1991 [doi>10.1109/52.73749]
• 15: Luc de Raedt , Gunther Sablon , Maurice Bruynooghe, Using interactive concept learning for knowledge-base validation and verification, Validation, verification and test of knowledge-based systems, John Wiley & Sons, Inc., New York, NY, 1991
• 16: M. E. Gold. Language Identification in the Limit. Information and Control, 10:447-474, 1967.
• 17: Michael M. Gorlick , Carl F. Kesselman , Daniel A. Marotta , D. Scott Parker, Mockingbird: a logical methodology for testing, Journal of Logic Programming, v.8 n.1-2, p.95-119, Jan./Mar. 1990 [doi>10.1016/0743-1066(90)90053-8]
• 18: R. G. Hamlet. Reliability y Theory of Program Testing. Acts Informatica, 16:31-43, 1981.
• 19: I J Hayes, Specification directed module testing, IEEE Transactions on Software Engineering, v.12 n.1, p.124-133, Jan. 1986
• 20: Daniel M. Hoffman , Paul Strooper, Automated Module Testing in Prolog, IEEE Transactions on Software Engineering, v.17 n.9, p.934-943, September 1991 [doi>10.1109/32.92913]
• 21: W. E. Howden. Reliability of the Path Analysis Testing Strategy. IEEE Trans. on Soflware Engineering, 2 :208-215, 1976.
• 22: W. E. Howden. Functional Program Testing. IEEE Tmns. on Sofiware Engineering, 6(2):162-169, 1980.
• 23: W. E. Howden. Weak Mutation Testing and Completeness of Test Sets. IEEE Trans. on Soflware Engineering, 8(4):371-379, 1982.
• 24: P. Kilperäinen , H. Mannila, Generation of test cases for simple Prolog programs, Acta Cybernetica, v.9 n.3, p.235-246, Nov. 1990
• 25: K. N. King , A. Jefferson Offutt, A Fortran language system for mutation-based software testing, Software—Practice & Experience, v.21 n.7, p.685-718, July 1991 [doi>10.1002/spe.4380210704]
• 26: St rat egies for Inductive Learning of Simple Prolog Programs. In Proc. Int. Joint Conj. on Artificial Intelligence, pages 757- 761, Sydney, Australia, 1991.
• 27: R. S. Michalski. Pattern Recognition as Rule-Guided Inductive Inference. IEEE Trans. on PAMI, 2:349-361, 1980.
• 28: R. S. Michalski. A Theory and Methodology of Inductive Learning. Artificial Intelligence, 20:111-161, 1983.
• 29: L. J. Morel.1. Theoretical insights into fault-based testing. In Proc. Workshop on Software Testing, Verification and Analysis, pages 45-62, Banff, Canada, 1988.
• 30: S. Muggleton, editor. Inductive Logic Programming. Academic Press, 1991.
• 31: A. Offutt, The coupling effect: fact or fiction, Proceedings of the ACM SIGSOFT '89 third symposium on Software testing, analysis, and verification, p.131-140, December 13-15, 1989, Key West, Florida, United States
• 32: Pat Langley, Editorial: Advice to Machine Learning Authors, Machine Learning, v.5 n.3, p.233-237, Aug. 1990 [doi>10.1023/A:1022647305786]
• 33: P. Strooper and D. Hoffman. Prolog Testing of C modules. In Proc. Int. Conf. on Logic Programming, pages 596-608, 1991.
• 34: Phillip D. Summers, A Methodology for LISP Program Construction from Examples, Journal of the ACM (JACM), v.24 n.1, p.161-175, Jan. 1977 [doi>10.1145/321992.322002]
• 35: W. T. Tsai , Dmitry Volovik , Thomas F. Keefe, Automated Test Case Generation for Programs Specified by Relational Algebra Queries, IEEE Transactions on Software Engineering, v.16 n.3, p.316-324, March 1990 [doi>10.1109/32.48939]
• 36: Paul E. Utgoff, Machine learning of inductive bias, Kluwer, B.V., Deventer, The Netherlands, 1986
• 37: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
• 38: Elaine J. Weyuker, Assessing Test Data Adequacy through Program Inference, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.4, p.641-655, Oct. 1983 [doi>10.1145/69575.357231]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Induction

General Terms:
Design, Performance, Reliability, Theory