An analysis of rule coverage as a criterion in generating minimal test suites for grammar-based software

ABSTRACT

The term grammar-based software describes software whose input can be specified by a context-free grammar. This grammar may occur explicitly in the software, in the form of an input specification to a parser generator, or implicitly, in the form of a hand-written parser, or other input-verification routines. Grammar-based software includes not only programming language compilers, but also tools for program analysis, reverse engineering, software metrics and documentation generation. Such tools often play a crucial role in automated software development, and ensuring their completeness and correctness is a vital prerequisite for their us.In this paper we propose a strategy for the construction of test suites for grammar based software, and illustrate this strategy using the ISO CPP grammar. We use the concept of rule coverage as a pivot for the reduction of implementation-based and specification-based test suites, and demonstrate a significant decrease in the size of these suites. To demonstrate the validity of the approach, we use the reduced test suite to analyze three grammar-based tools for CPP++. We compare the effectiveness of the reduced test suite with the original suite in terms of code coverage and fault detection.

REFERENCES

• 1: D. Acostachioaie. Doc++: Open source - open science - open systems. Circles Electronic Magazine, (36), 2000.
• 2: F. Bazzichi and I. Spadafora. An automatic generator for compiler testing. IEEE Trans. Softw. Eng., 8(4):343--353, 1982.
• 3: A. Celentano, S. Crespi-Reghizzi, P. D. Vigna, C. Ghezzi, G. Granata, and F. Savoretti. Compiler testing using a sentence generator. Software: Practice and Experience, 10(11):897--918, November 1980.
• 4: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 5: Brian A. Malloy , Tanton H. Gibbs , James F. Power, Decorating tokens to facilitate recognition of ambiguous language constructs, Software—Practice & Experience, v.33 n.1, p.19-39, January 2003 [doi>10.1002/spe.493]
• 6: T. H. Gibbs, B. A. Malloy, and J. F. Power. Progression toward conformance of C++ language compilers. Dr. Dobbs Journal, 28(11):54--60, September 2003.
• 7: J. Harm and R. Lämmel. Two-dimensional Approximation Coverage. Informatica, 24(3), 2000.
• 8: M. Jean Harrold , Rajiv Gupta , Mary Lou Soffa, A methodology for controlling the size of a test suite, ACM Transactions on Software Engineering and Methodology (TOSEM), v.2 n.3, p.270-285, July 1993 [doi>10.1145/152388.152391]
• 9: Mats P. E. Heimdahl , Devaraj George, Test-Suite Reduction for Model Based Tests: Effects on Test Quality and Implications for Testing, Proceedings of the 19th IEEE international conference on Automated software engineering, p.176-185, September 20-24, 2004 [doi>10.1109/ASE.2004.67]
• 10: M. Hennessy and J. F. Power. Generation strategies for test-suites of grammar-based software. Technical Report NUIM-CS-TR-2005-02, Department of Computer Science, National Univesity of Ireland, Maynooth, April 13 2005.
• 11: Mark Hennessy , Brian A. Malloy , James F. Power, gccXfront: Exploiting gcc as a Front End for Program Comprehension Tools via XML/XSLT, Proceedings of the 11th IEEE International Workshop on Program Comprehension, p.298, May 10-11, 2003
• 12: ISO/IEC JTC 1. International Standard: Programming Languages - C++. Number 14882:2003(E). American National Standards Institute, second edition, October 15 2003.
• 13: James A. Jones , Mary Jean Harrold, Test-Suite Reduction and Prioritization for Modified Condition/Decision Coverage, IEEE Transactions on Software Engineering, v.29 n.3, p.195-209, March 2003 [doi>10.1109/TSE.2003.1183927 ]
• 14: Paul Klint , Ralf Lämmel , Chris Verhoef, Toward an engineering discipline for grammarware, ACM Transactions on Software Engineering and Methodology (TOSEM), v.14 n.3, p.331-380, July 2005 [doi>10.1145/1072997.1073000]
• 15: Ralf Lämmel, Grammar Testing, Proceedings of the 4th International Conference on Fundamental Approaches to Software Engineering, p.201-216, April 02-06, 2001
• 16: Yu-Seung Ma , Jeff Offutt , Yong Rae Kwon, MuJava: an automated class mutation system: Research Articles, Software Testing, Verification & Reliability, v.15 n.2, p.97-133, June 2005 [doi>10.1002/stvr.v15:2]
• 17: Brian A. Malloy , Scott A. Linde , Edward B. Duffy , James F. Power, Programmer's toolchest: testing C++ compilers for ISO language conformance, Dr. Dobb's Journal, v.27 n.6, p.71-78, June 2002
• 18: B. A. Malloy and J. F. Power. An interpretation of P urdom's algorithm for automatic generation of test cases. In 1st Annual International Conference on Computer and Information Science, Orlando, FL., 2001.
• 19: Brian A. Malloy , James F. Power , John T. Waldron, Applying software engineering techniques to parser design: the development of a C^# parser, Proceedings of the 2002 annual research conference of the South African institute of computer scientists and information technologists on Enablement through technology, September 16-18, 2002, Port Elizabeth, South Africa
• 20: A. Jefferson Offutt , Ammei Lee , Gregg Rothermel , Roland H. Untch , Christian Zapf, An experimental determination of sufficient mutant operators, ACM Transactions on Software Engineering and Methodology (TOSEM), v.5 n.2, p.99-118, April 1996 [doi>10.1145/227607.227610]
• 21: J. F. Power , B. A. Malloy, Program Annotation in XML: A Parse-Tree Based Approach, Proceedings of the Ninth Working Conference on Reverse Engineering (WCRE'02), p.190, October 29-November 01, 2002
• 22: James F. Power , Brian A. Malloy, A metrics suite for grammar-based software: Research Articles, Journal of Software Maintenance and Evolution: Research and Practice, v.16 n.6, p.405-426, November 2004 [doi>10.1002/smr.v16:6]
• 23: P. Purdom. A sentance generator for testing parsers. BIT, 12(3):366--375, 1972.
• 24: Marc Roper, Software Testing, McGraw-Hill, Inc., New York, NY, 1995
• 25: Gregg Rothermel , Mary Jean Harrold , Jeffery Ostrin , Christie Hong, An Empirical Study of the Effects of Minimization on the Fault Detection Capabilities of Test Suites, Proceedings of the International Conference on Software Maintenance, p.34, March 16-19, 1998
• 26: Susan Elliott Sim , Richard C. Holt , Steve Easterbrook, On Using a Benchmark to Evaluate C++ Extractors, Proceedings of the 10th International Workshop on Program Comprehension, p.114, June 27-29, 2002
• 27: Olaf Spinczyk , Andreas Gal , Wolfgang Schröder-Preikschat, AspectC++: an aspect-oriented extension to the C++ programming language, Proceedings of the Fortieth International Conference on Tools Pacific: Objects for internet, mobile and embedded applications, February 01, 2002, Sydney, Australia
• 28: Mark G. J. van den Brand , A. Sellink , C. Verhoef, Current Parsing Techniques in Software Renovation Considered Harmful, Proceedings of the 6th International Workshop on Program Comprehension, p.108, June 24-26, 1998
• 29: W. Eric Wong , Joseph R. Horgan , Saul London , Aditya P. Mathur, Effect of test set minimization on fault detection effectiveness, Software—Practice & Experience, v.28 n.4, p.347-369, April 10, 1998 [doi>10.1002/(SICI)1097-024X(19980410)28:4<347::AID-SPE145>3.0.CO;2-L ]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors

General Terms:
Experimentation, Languages, Measurement

Keywords:
grammar-based software, rule coverage, software testing, test suite reduction