yagg: an easy-to-use generator for structured test inputs

ABSTRACT

Automated testing typically uses specifications to drive the generation of test inputs and/or the checking of program outputs. Many software systems have structurally complex inputs that cannot be adequately described using simple formalisms such as context-free grammars. In order to generate such inputs, many automated testing environments require the user to express the structure of the input using an unfamiliar formal notation. This raises the cost of employing automated testing, thereby offsetting the benefits gained. We present yagg (yet another generator-generator), a tool that allows the programmer to specify the input using a syntax very similar to that of LEX and YACC, widely used scanner and parser generators. yagg allows the user to bound the input space using several different techniques, and generates an input generator that systematically enumerates inputs. We evaluate the ease of use and performance of the tool relative to a model checker-based generator used in previous research. Our experiences indicate that yagg generators can be somewhat slower, but that the ease-of-use afforded by the familiar syntax may be attractive to users.

REFERENCES

• 1: Jonathan A. Bauer , Alan B. Finger, Test plan generation using formal grammars, Proceedings of the 4th international conference on Software engineering, p.425-432, September 17-19, 1979, Munich, Germany
• 2: David Coppit , Jinlin Yang , Sarfraz Khurshid , Wei Le , Kevin Sullivan, Software Assurance by Bounded Exhaustive Testing, IEEE Transactions on Software Engineering, v.31 n.4, p.328-339, April 2005 [doi>10.1109/TSE.2005.52]
• 3: A. G. Duncan , J. S. Hutchison, Using attributed grammars to test designs and implementations, Proceedings of the 5th international conference on Software engineering, p.170-178, March 09-12, 1981, San Diego, California, United States
• 4: Daniel Jackson. Micromodels of software: Modelling and analysis with Alloy. URL: http://sdg.lcs.mit.edu/alloy/reference-manual.pdf
• 5: Daniel Jackson , Ian Schechter , Hya Shlyahter, Alcoa: the alloy constraint analyzer, Proceedings of the 22nd international conference on Software engineering, p.730-733, June 04-11, 2000, Limerick, Ireland [doi>10.1145/337180.337616]
• 6: S. C. Johnson. YACC --- Yet another compiler-compiler. Computing Science Technical Report No. 32, Bell Laboratories, Murray Hill, N.J., 1975.
• 7: M. E. Lesk and E. Schmidt. Lex --- A lexical analyzer generator. Computing Science Technical Report No. 39, Bell Laboratories, Murray Hill, N.J., 1975.
• 8: Darko Marinov , Sarfraz Khurshid, TestEra: A Novel Framework for Automated Testing of Java Programs, Proceedings of the 16th IEEE international conference on Automated software engineering, p.22, November 26-29, 2001
• 9: Peter M. Maurer, The design and implementation of a grammar-based data generator, Software—Practice & Experience, v.22 n.3, p.223-244, March 1992 [doi>10.1002/spe.4380220303]
• 10: Matthew W. Moskewicz , Conor F. Madigan , Ying Zhao , Lintao Zhang , Sharad Malik, Chaff: engineering an efficient SAT solver, Proceedings of the 38th conference on Design automation, p.530-535, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379017]
• 11: P. Purdom. A sentence generator for testing parsers. BIT, 12(3):366--75, 1972.
• 12: W. E. Vesely, Joanne Dugan, Joseph Fragola, Joseph Minarick III, and Jan Railsback. Fault Tree Handbook with Aerospace Applications. National Aeronatics and Space Administration, August 2002.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification

General Terms:
Algorithms, Verification

Keywords:
bounded exhaustive testing, grammar-based input generation