Conformance Testing of Boolean Programs with Multiple Faults

Abstract : Conformance testing is the problem of constructing a complete test suite of inputs based on a specification S such that any implementation I (of size less than a given bound) that is not equivalent to S gives a different output on the test suite than S. Typically I and S are assumed to be some type of finite automata. In this paper we consider the problem of constructing test suites for boolean programs (or more precisely modular visibly pushdown automata) that are guaranteed to catch all erroneous implementations that have at least R faults, and pass all correct implementations; if the incorrect implementation has fewer than R faults then the test suite may or may not detect it. We present a randomized algorithm for the construction of such test suites, and prove the near optimality of our test suites by proving lower bounds on the size of test suites.
Type de document :
Communication dans un congrès
Holger Giese; Grigore Rosu. 14th International Conference on Formal Methods for Open Object-Based Distributed Systems (FMOODS) / 32nd International Conference on Formal Techniques for Networked and Distributed Systems (FORTE), Jun 2012, Stockholm, Sweden. Springer, Lecture Notes in Computer Science, LNCS-7273, pp.101-117, 2012, Formal Techniques for Distributed Systems. 〈10.1007/978-3-642-30793-5_7〉
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01528731
Contributeur : Hal Ifip <>
Soumis le : lundi 29 mai 2017 - 15:53:56
Dernière modification le : lundi 29 mai 2017 - 15:55:37
Document(s) archivé(s) le : mercredi 6 septembre 2017 - 11:23:08

Fichier

978-3-642-30793-5_7_Chapter.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Pavithra Prabhakar, Mahesh Viswanathan. Conformance Testing of Boolean Programs with Multiple Faults. Holger Giese; Grigore Rosu. 14th International Conference on Formal Methods for Open Object-Based Distributed Systems (FMOODS) / 32nd International Conference on Formal Techniques for Networked and Distributed Systems (FORTE), Jun 2012, Stockholm, Sweden. Springer, Lecture Notes in Computer Science, LNCS-7273, pp.101-117, 2012, Formal Techniques for Distributed Systems. 〈10.1007/978-3-642-30793-5_7〉. 〈hal-01528731〉

Partager

Métriques

Consultations de la notice

33

Téléchargements de fichiers

17