The optimisation of stochastic grammars to enable cost-effective probabilistic structural testing
The optimisation of stochastic grammars to enable cost-effective probabilistic structural testing
复制标题
DOI：
10.1145/2463372.2463550
复制
发表时间：
2013-07
期刊：
影响因子：
--
通讯作者：
Simon M. Poulding;Robert Alexander;John A. Clark;M. Hadley
中科院分区：
文献类型：
--
作者：
Simon M. Poulding;Robert Alexander;John A. Clark;M. Hadley
概率结构测试的有效性取决于随机抽样测试输入的概率分布的特征。元启发式搜索已被证明是优化此类分布特征的实用方法。但是，现有的基于搜索的算法的适用性受到软件输入必须是固定数量的数值这一要求的限制。本文用一种新的概率分布表示来放宽这种限制。该表示基于随机上下文无关语法，但包含两个新的扩展：条件生成权重和表示数值的终端符号的聚合。我们证明了一种将新的表示与爬坡搜索相结合的算法能够有效地推导出适合于具有结构复杂输入域的测试软件的概率分布。
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 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 numeric values. In this paper we relax this limitation by means of a new representation for the probability distribution. The representation is based on stochastic context-free grammars but incorporates two novel extensions: conditional production weights and the aggregation of terminal symbols representing numeric values. We demonstrate that an algorithm which combines the new representation with hill-climbing search is able to efficiently derive probability distributions suitable for testing software with structurally-complex input domains.