Coverage-biased random exploration of large models and application to testing |
| |
Authors: | Alain Denise Marie-Claude Gaudel Sandrine-Dominique Gouraud Richard Lassaigne Johan Oudinet Sylvain Peyronnet |
| |
Affiliation: | 1. LRI, Univ Paris-Sud, 91405, Orsay, France 2. CNRS, 91405, Orsay, France 3. INRIA Saclay-Ile-de-France, 91893, Orsay cedex, France 4. Logique Math??matique (IMJ), Univ Paris VII, 75251, Paris, France 5. CNRS, 75000, Paris, France
|
| |
Abstract: | This paper presents several randomised algorithms for generating paths in large models according to a given coverage criterion.
Using methods for counting combinatorial structures, these algorithms can efficiently explore very large models, based on
a graphical representation by an automaton or by a product of several automata. This new approach can be applied to random
exploration in order to optimise path coverage and can be generalised to take into account other coverage criteria, via the
definition of a notion of randomised coverage satisfaction. Our main contributions are a method for drawing paths uniformly
at random in composed models, i.e. models that are given as products of automata, first without and then with synchronisation;
a new efficient approach to draw paths at random taking into account some other coverage criterion. Experimental results show
promising agreement with theoretical predictions and significant improvement over previous randomised approaches. This work
opens new perspectives for future studies of statistical testing and model checking, mainly to fight the combinatorial explosion
problem. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|