Introduction to Software Testing Chapter 5 5 Input Space Grammars Paul Ammann Jeff Offutt www introsoftwaretesting com Input Space Grammars Input Space The set of allowable inputs to software There are many ways to describe the input space User manuals Unix man pages Method signature Collection of method preconditions A language Most input spaces can be described as grammars Grammars are usually not provided but creating them is a valuable service by the tester Errors will often be found simply by creating the grammar Introduction to Software Testing Ch 5 www introsoftwaretesting com Ammann Offutt 2 1 Validating Inputs Input Validation Deciding if input values can be processed by the software What should a program do with invalid inputs How should a program recognize invalid inputs Before starting to process inputs wisely written programs check that the inputs are valid If the input space is described as a grammar a parser can check for validity automatically This is very very rare It is easy to write input checkers but also easy to make mistakes Introduction to Software Testing Ch 5 www introsoftwaretesting com 3 Ammann Offutt Instantiating Grammar Based Testing Grammar Based Testing 5 5 Program based Integration String mutation Grammar String mutation Program mutation Valid strings Mutants are not tests Must kill mutants Compiler testing Valid and invalid strings Model Based String mutation FSMs Model checking Valid strings Traces are tests Test how classes interact Valid strings Mutants are not tests Must kill mutants Includes OO Introduction to Software Testing Ch 5 www introsoftwaretesting com Input Based Grammar String mutation Input validation testing XML and others Invalid strings No ground strings Mutants are tests Input validation testing XML and others Valid strings Ammann Offutt 4 2 Input Space BNF Grammars 5 5 1 Consider a program that processes a sequence of deposits and debits to a bank Inputs deposit 5306 4 30 debit 0343 4 14 deposit 5306 7 29 Initial Grammar deposit account amount debit account amount deposit Ready debit FSM to represent the grammar Introduction to Software Testing Ch 5 www introsoftwaretesting com Ammann Offutt 5 Grammar for Bank Example Grammars are more expressive than regular expressions they can capture more details bank action action dep deb dep deposit account amount deb debit account amount account digit4 amount digit digit2 digit 0 1 2 3 4 5 6 7 8 9 Introduction to Software Testing Ch 5 www introsoftwaretesting com Ammann Offutt 6 3 FSM for Bank Grammar deposit digit digit digit debit digit digit digit digit digit Derive tests by systematically replacing each non terminal with a production If the tester designs the grammar from informal input descriptions do it early In time to improve the design Mistakes and omissions will almost always be found Introduction to Software Testing Ch 5 www introsoftwaretesting com 7 Ammann Offutt XML Software components that pass data must agree on format types and organization Web services have unique requirements Very loose coupling and dynamic integration P1 1970s style File P2 P1 File storage Un documented format Data saved in binary mode Source not available Introduction to Software Testing Ch 5 www introsoftwaretesting com 1980s style P2 WM File storage Un documented format Data saved as plain text Access through wrapper module Data hard to validate File Ammann Offutt 8 4 XML in Web Services Data is passed directly between components XML allows data to be self documenting 2000s style P1 P2 P3 Parser XML File DTD P1 P2 and P3 can see the format contents and structure of the data Data sharing is independent of type Format is easy to understand Grammars are defined in DTDs or Schemas Introduction to Software Testing Ch 5 www introsoftwaretesting com Ammann Offutt 9 XML for Book Example books book ISBN 0471043281 ISBN title The Art of Software Testing title author Glen Myers author publisher Wiley publisher price 50 00 price year 1979 year book books XML messages are defined by grammars Schemas and DTDs Schemas can define many kinds of types Schemas include facets which refine the grammar Introduction to Software Testing Ch 5 www introsoftwaretesting com Ammann Offutt 10 5 Book Grammar Schema xs element name books xs complexType xs sequence xs element name book maxOccurs unbounded xs complexType xs sequence xs element name ISBN type isbnType minOccurs 0 xs element name author type xs string xs element name publisher type xs string xs element name price type priceType xs element name year type yearType xs sequence xs complexType xs simpleType name priceType xs element xs restriction base xs decimal xs sequence xs fractionDigits value 2 xs complexType xs maxInclusive value 1000 00 xs element xs restriction xs simpleType Introduction to Software Testing Ch 5 www introsoftwaretesting com Ammann Offutt 11 Generating Tests The criteria in section 5 1 1 can be used to generate tests Production and terminal symbol coverage The only choice in books is based on minOccurs PC requires two tests ISBN is present ISBN is not present The facets are used to generate values that are valid We also want values that are not valid Introduction to Software Testing Ch 5 www introsoftwaretesting com Ammann Offutt 12 6 Mutation for Input Grammars 5 5 2 Software should reject or handle invalid data A very common mistake is for programs to do this incorrectly Some programs rashly assume that all input data is correct Even if it works today What about after the program goes through some maintenance changes What about if the component is reused in a new program Consequences can be severe Most security vulnerabilities are due to unhandled exceptions from invalid data To test for invalid data including security testing mutate the grammar Introduction to Software Testing Ch 5 www introsoftwaretesting com Ammann Offutt 13 Mutating Input Grammars Mutants are tests Create valid and invalid strings No ground strings no killing Mutation operators listed here are general and should be refined for specific grammars Introduction to Software Testing Ch 5 www introsoftwaretesting com Ammann Offutt 14 7 Input Grammar Mutation Operators 1 Nonterminal Replacement Every nonterminal symbol in a production is replaced by other nonterminal symbols 2 Terminal Replacement Every terminal symbol in a production is replaced by other terminal symbols 3 Terminal and Nonterminal Deletion Every terminal and nonterminal symbol in a production is deleted 4