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

Simon Marcus Poulding; Rob Alexander; John Andrew Clark; Mark Jason Hadley

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

Simon Marcus Poulding, Rob Alexander, John Andrew Clark, Mark Jason Hadley

Computer Science

Research output: Contribution to conference › Paper › peer-review

Abstract

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 language	English
Number of pages	8
Publication status	Published - Jul 2013
Event	GECCO 2013 - Amsterdam, Netherlands Duration: 6 Jul 2013 → 10 Jul 2013

Conference

Conference	GECCO 2013
Country/Territory	Netherlands
City	Amsterdam
Period	6/07/13 → 10/07/13

Access to Document

T16pap470 pouldingAccepted author manuscript, 298 KB

DAASE
Clark, J. A.
EPSRC
1/06/12 → 31/03/17
Project: Research project (funded) › Research
The Birth, Life and Death of Semantic Mutants
Clark, J. A.
EPSRC
1/10/09 → 31/03/14
Project: Research project (funded) › Research
System Smart Intrusion Detection
Clark, J. A.
EPSRC
28/09/07 → 27/07/10
Project: Research project (funded) › Research

Cite this

@conference{c9ba4bdc0b7b4fec8589b25455c3e1ec,

title = "The Optimisation of Stochastic Grammars to Enable Cost-Effective Probabilistic Structural Testing",

abstract = "The effectiveness of probabilistic structural testing dependson the characteristics of the probability distribution fromwhich test inputs are sampled at random. Metaheuristicsearch has been shown to be a practical method of optimis-ing the characteristics of such distributions. However, theapplicability of the existing search-based algorithm is lim-ited by the requirement that the software{\textquoteright}s inputs must bea fixed number of numeric values.In this paper we relax this limitation by means of a newrepresentation for the probability distribution. The repre-sentation is based on stochastic context-free grammars butincorporates two novel extensions: conditional productionweights and the aggregation of terminal symbols represent-ing numeric values.We demonstrate that an algorithm which combines thenew representation with hill-climbing search is able to effi-ciently derive probability distributions suitable for testingsoftware with structurally-complex input domains.",

author = "Poulding, {Simon Marcus} and Rob Alexander and Clark, {John Andrew} and Hadley, {Mark Jason}",

year = "2013",

month = jul,

language = "English",

note = "GECCO 2013 ; Conference date: 06-07-2013 Through 10-07-2013",

}

TY - CONF

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

AU - Poulding, Simon Marcus

AU - Alexander, Rob

AU - Clark, John Andrew

AU - Hadley, Mark Jason

PY - 2013/7

Y1 - 2013/7

N2 - The effectiveness of probabilistic structural testing dependson the characteristics of the probability distribution fromwhich test inputs are sampled at random. Metaheuristicsearch has been shown to be a practical method of optimis-ing the characteristics of such distributions. However, theapplicability of the existing search-based algorithm is lim-ited by the requirement that the software’s inputs must bea fixed number of numeric values.In this paper we relax this limitation by means of a newrepresentation for the probability distribution. The repre-sentation is based on stochastic context-free grammars butincorporates two novel extensions: conditional productionweights and the aggregation of terminal symbols represent-ing numeric values.We demonstrate that an algorithm which combines thenew representation with hill-climbing search is able to effi-ciently derive probability distributions suitable for testingsoftware with structurally-complex input domains.

AB - The effectiveness of probabilistic structural testing dependson the characteristics of the probability distribution fromwhich test inputs are sampled at random. Metaheuristicsearch has been shown to be a practical method of optimis-ing the characteristics of such distributions. However, theapplicability of the existing search-based algorithm is lim-ited by the requirement that the software’s inputs must bea fixed number of numeric values.In this paper we relax this limitation by means of a newrepresentation for the probability distribution. The repre-sentation is based on stochastic context-free grammars butincorporates two novel extensions: conditional productionweights and the aggregation of terminal symbols represent-ing numeric values.We demonstrate that an algorithm which combines thenew representation with hill-climbing search is able to effi-ciently derive probability distributions suitable for testingsoftware with structurally-complex input domains.

M3 - Paper

T2 - GECCO 2013

Y2 - 6 July 2013 through 10 July 2013

ER -

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

Abstract

Conference

Access to Document

Projects

DAASE

The Birth, Life and Death of Semantic Mutants

System Smart Intrusion Detection

Cite this