Test case generation using symbolic grammars and quasirandom sequences

• Author / Creator

  Felix Reyes, Alejandro

• This work presents a new test case generation methodology, which has a high degree of automation (cost reduction); while providing increased “power” in terms of defect detection (benefits increase). Our solution is a variation of model-based testing, which takes advantage of symbolic grammars (a context-free grammar where terminals are replaced by regular expressions that represent their solution space) and quasi-random sequences to generate test cases.

  Previous test case generation techniques are enhanced with adaptive random testing to maximize input space coverage; and selective and directed sentence generation techniques to optimize sentence generation.

  Our solution was tested by generating 200 firewall policies containing up to 20 000 rules from a generic firewall grammar. Our results show how our system generates test cases with superior coverage of the input space, increasing the probability of defect detection while reducing considerably the needed number the test cases compared with other previously used approaches.

• Subjects / Keywords

  • Model-based testing
  • Symbolic grammars
  • Testing
  • Adaptive testing
  • Firewall policies
  • Firewalls
  • Grammars
  • Grammar-based testing
  • Test data
  • Data generation
  • Quasi-random sequences
  • Firewall testing

• Graduation date

  Spring 2011

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/R3611F

• License

  This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.