Search-based statistical testing

Statistical testing is a probabilistic approach for test generation developed by our group in the 1990s. It involves the use of coverage criteria to design sampling profiles over the input domain. Recent work at the University of York has revisited this approach, demonstrating an automated search-based technique for synthesizing profiles suitable for statistical testing. The input profile is represented by a stochastic grammar, which is incrementally modified using a metaheuristic search algorithm until the adequacy criterion is met. Joint work has investigated the tuning of the search [PCW11, PW13].

Based on exemplary profiles derived from early work by our group, we have shown that the grammar-based representation is unable to properly express some key relationships between input arguments. When the search attempts to approximate these relationships, it is only able to do so over small regions of the input domain, yielding ‘degenerate’ profiles with poor fault-revealing power. We have proposed an augmentation of the grammar with operators that allow the user to incorporate knowledge guiding the search algorithm. Empirical results for two case studies are promising: knowledge gained by a very straightforward review of the software-under-test is sufficient to dramatically increase the efficacy of the profiles synthesized by search.

Degeneracy of search-synthesized profiles compared to analytically-derived ones,
for a function with a branch checking equality between two input arguments.
(The lines indicate the median score from 10 test sets, and the shaded ribbon the interquartile range)

Publications

[PW13] S.POULDING, H.WAESELYNCK: Adding contextual guidance to the automated search for probabilistic test profiles, LAAS Report N°13438

[PCW11] S.Poulding, J.A. Clark, H.Waeselynck: A principled evaluation of the effect of directed mutation on search-based statistical testing, In Proc. Int. Workshop on Search-Based Software Testing (SBST 2011), Berlin (Germany), March 2011. Best paper award.

Back to TSF Research Topics page