The Optimisation of Stochastic Grammars to Enable Cost-Effective Probabilistic Structural Testing

Research output: Contribution to conferencePaperpeer-review


The effectiveness of probabilistic structural testing depends
on the characteristics of the probability distribution from
which test inputs are sampled at random. Metaheuristic
search has been shown to be a practical method of optimis-
ing the characteristics of such distributions. However, the
applicability of the existing search-based algorithm is lim-
ited by the requirement that the software’s inputs must be
a fixed number of numeric values.

In this paper we relax this limitation by means of a new
representation for the probability distribution. The repre-
sentation is based on stochastic context-free grammars but
incorporates two novel extensions: conditional production
weights and the aggregation of terminal symbols represent-
ing numeric values.

We demonstrate that an algorithm which combines the
new representation with hill-climbing search is able to effi-
ciently derive probability distributions suitable for testing
software with structurally-complex input domains.
Original languageEnglish
Number of pages8
Publication statusPublished - Jul 2013
EventGECCO 2013 - Amsterdam, Netherlands
Duration: 6 Jul 201310 Jul 2013


ConferenceGECCO 2013

Cite this