TransDPOR: A Novel Dynamic Partial-Order Reduction Technique for Testing Actor Programs

Abstract : To detect hard-to-find concurrency bugs, testing tools try to systematically explore all possible interleavings of the transitions in a concurrent program. Unfortunately, because of the nondeterminism in concurrent programs, exhaustively exploring all interleavings is time-consuming and often computationally intractable. Speeding up such tools requires pruning the state space explored. Partial-order reduction (POR) techniques can substantially prune the number of explored interleavings. These techniques require defining a dependency relation on transitions in the program, and exploit independency among certain transitions to prune the state space.We observe that actor systems, a prevalent class of programs where computation entities communicate by exchanging messages, exhibit a dependency relation among co-enabled transitions with an interesting property: transitivity. This paper introduces a novel dynamic POR technique, TransDPOR, that exploits the transitivity of the dependency relation in actor systems. Empirical results show that leveraging transitivity speeds up exploration by up to two orders of magnitude compared to existing POR techniques.
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.219-234, 2012, Formal Techniques for Distributed Systems. 〈10.1007/978-3-642-30793-5_14〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01528727
Contributeur : Hal Ifip <>
Soumis le : lundi 29 mai 2017 - 15:53:53
Dernière modification le : jeudi 21 juin 2018 - 16:36:01
Document(s) archivé(s) le : mercredi 6 septembre 2017 - 11:24:23

Fichier

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

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Samira Tasharofi, Rajesh Karmani, Steven Lauterburg, Axel Legay, Darko Marinov, et al.. TransDPOR: A Novel Dynamic Partial-Order Reduction Technique for Testing Actor Programs. 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.219-234, 2012, Formal Techniques for Distributed Systems. 〈10.1007/978-3-642-30793-5_14〉. 〈hal-01528727〉

Partager

Métriques

Consultations de la notice

247

Téléchargements de fichiers

19