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

TY - JOUR

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

AU - Poulding, S.

AU - Alexander, R.

AU - Clark, J.A.

AU - Hadley, M.J.

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

PY - 2015/5/1

Y1 - 2015/5/1

N2 - 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.

AB - 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.

KW - Grammar-based testing

U2 - 10.1016/j.jss.2014.11.042

DO - 10.1016/j.jss.2014.11.042

M3 - Article

SN - 0164-1212

VL - 103

SP - 296

EP - 310

JO - Journal of Systems and Software

JF - Journal of Systems and Software

ER -