The optimisation of stochastic grammars to enable cost-effective probabilistic structural testing

Research output: Contribution to journalArticlepeer-review


Abstract The effectiveness of statistical testing, a probabilistic structural testing strategy, depends on the characteristics of the probability distribution from which test inputs are sampled. Metaheuristic search has been shown to be a practical method of optimising the characteristics of such distributions. However, the applicability of the existing search-based algorithm is limited by the requirement that the software’s inputs must be a fixed number of ordinal values. In this paper we propose a new algorithm that relaxes this limitation and so permits the derivation of probability distributions for a much wider range of software. The representation used by the new algorithm is based on a stochastic grammar supplemented with two novel features: conditional production weights and the dynamic partitioning of ordinal ranges. We demonstrate empirically that a search algorithm using this representation can optimise probability distributions over complex input domains and thereby enable cost-effective statistical testing, and that the use of both conditional production weights and dynamic partitioning can be beneficial to the search process.
Original languageEnglish
Pages (from-to)296-310
Number of pages15
JournalJournal of Systems and Software
Early online date6 Dec 2014
Publication statusPublished - 1 May 2015

Bibliographical note

This is an author-produced version of the published paper. Uploaded in accordance with the publisher’s self-archiving policy.


  • Grammar-based testing

Cite this