Test Case Generation using Symbolic Grammars and Quasi-Random Sequences

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 finding (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 regular expressions that represent their solution space) and quasi-random sequences to generate test cases. Previous 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 probabilities of defect finding while reducing considerably the needed number the test cases) compared with other previously used approaches.