A Random Testing Approach Using Pushdown Automata

Alois Dreyfus 1, 2 Pierre-Cyrille Heam 1, 2 Olga Kouchnarenko 1, 2 Catherine Masson 2
2 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174), Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : Developing efficient and automatic testing techniques is one of the major challenges \new{faced by} the software validation community. Recent work by Denise et al. published in STTT shows how to draw traces uniformly at random in large systems modelled by finite automata for testing purposes. Since finite automata are strong abstractions of systems, many test cases generated following this approach may be un-concretizable, i.e., they do not correspond to any concrete execution of the system under test. In this paper, this problem is tackled by extending the approach to pushdown systems that can encode either a stack data structure, or the call stack. The method is based on context-free grammars and related algorithms, and relies on combinatorial techniques to guarantee the uniformity of generated traces. In addition, the combination of coverage criteria with random testing is investigated, in order to take benefit of both approaches for evaluating the quality of the test suites. The application of the random approach is illustrated within both structural and model based testing contexts.
Type de document :
Autre publication
submitted (minor revision required). 2013
Liste complète des métadonnées

Contributeur : Pierre-Cyrille Heam <>
Soumis le : lundi 2 décembre 2013 - 09:51:52
Dernière modification le : vendredi 6 juillet 2018 - 15:06:10


  • HAL Id : hal-00912392, version 1


Alois Dreyfus, Pierre-Cyrille Heam, Olga Kouchnarenko, Catherine Masson. A Random Testing Approach Using Pushdown Automata. submitted (minor revision required). 2013. 〈hal-00912392〉



Consultations de la notice