Transdpor: a novel dynamic partial-order reduction technique for testing actor programs

By Samira Tasharofi, Rajesh K. Karmani, Steven Lauterburg, Axel Legay, Darko Marinov, and Gul Agha. In FMOODS/FORTE, volume 7273 of Lecture Notes in Computer Science, 219–234. Springer, 2012.

Publisher Link:

http://dx.doi.org/10.1007/978-3-642-30793-5_14

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.

BibTeX

@inproceedings{conf/forte/TasharofiKLLMA12,
    author = "Tasharofi, Samira and Karmani, Rajesh K. and
              Lauterburg, Steven and Legay, Axel and Marinov, Darko and Agha,
              Gul",
    editor = "Giese, Holger and Rosu, Grigore",
    title = "TransDPOR: A Novel Dynamic Partial-Order Reduction
             Technique for Testing Actor Programs",
    booktitle = "FMOODS/FORTE",
    crossref = "conf/forte/2012",
    ee = "http://dx.doi.org/10.1007/978-3-642-30793-5_14",
    keywords = "formal methods",
    pages = "219-234",
    year = "2012",
}

@proceedings{conf/forte/2012,
    editor = "Giese, Holger and Rosu, Grigore",
    title = "Formal Techniques for Distributed Systems - Joint 14th
             IFIP WG 6.1 International Conference, FMOODS 2012 and 32nd IFIP WG
             6.1 International Conference, FORTE 2012, Stockholm, Sweden, June
             13-16, 2012. Proceedings",
    ee = "http://dx.doi.org/10.1007/978-3-642-30793-5",
    isbn = "978-3-642-30792-8",
    publisher = "Springer",
    series = "Lecture Notes in Computer Science",
    volume = "7273",
    year = "2012",
}