A dynamic stochastic model for automatic grammar-based test generation

• Published in: Software, practice & experience practice & experience, 2015-11, Vol.45 (11), p.1519-1547
• Main Authors: Guo, Hai-Feng, Qiu, Zongyan
• Format: Article
• Language: English
• Subjects: Automation; Derivation; Dynamics; Electric power distribution; Failure; fault localization; grammar-based test generation; Grammars; Position (location); software testing; Trees
• ISSN: 0038-0644; 1097-024X
• DOI: 10.1002/spe.2278

Summary Grammar‐based test generation provides a systematic approach to producing test cases from a given context‐free grammar. Unfortunately, naive grammar‐based test generation is problematic because of the fact that exhaustive random test case production is often explosive, and grammar‐based test generation with explicit annotation controls often causes unbalanced testing coverage. In this paper, we present an automatic grammar‐based test generation approach, which takes a symbolic grammar as input, requires zero control input from users, and produces well‐distributed test cases. Our approach utilizes a novel dynamic stochastic model where each variable is associated with a tuple of probability distributions, which are dynamically adjusted along the derivation. We further present a coverage tree illustrating the distribution of generated test cases and their detailed derivations. More importantly, the coverage tree supports various implicit derivation control mechanisms. We implemented this approach in a Java‐based system, named Gena. Each test case generated by Gena automatically comes with a set of structural features, which can play an important and effective role on automated failure causes localization. Experimental results demonstrate the effectiveness of our approach, the well‐balanced distribution of generated test cases over grammatical structures, and a case study on grammar‐based failure causes localization. Copyright © 2014 John Wiley & Sons, Ltd.