Multiverse Debugging: Non-Deterministic Debugging for Non-Deterministic Programs

We have been working on various bits and pieces to improve debugging in the past. For example, we tried to understand what bugs are possible, how debugging of actor systems works, how we could support all kind of concurrency models in debuggers, and more recently, how to avoid some issues with non-determinism by recording and replaying the execution of buggy actor applications.

Though, one of the big issues with debugging is that non-determinism makes it practically impossible to see what a program could be doing at any given point in time. Debugging a sequential program, we can see what is happening in every moment, and for most parts, programs are deterministic and will do the same thing reliably for a give point in a program. But with non-determinism in the mix, even with a debugger, we can’t be sure what a program would do the next time we inspect it. Non-determinism can cause for instance operations to be scheduled differently or messages to arrive in a different order. This means, we can’t really just go and look at a program in a debugger to see what it would be doing.

So, what if we could see all concurrency bugs in the debugger? What if we could simply explore the different non-deterministic paths a program could take?

With Multiverse Debugging, we explore exactly that idea.

Based on the AmbientTalk language, we designed and built a debugger that allows us to explore all possible universes, i.e., states a program can reach. Instead of staying in a single universe, we can ask the What If? question at every point in our programs and start exploring what may happen if messages are received in different orders, actor B is scheduled before actor A, and how the final results of such non-deterministic variations differ.

To get an idea of how that could look like, see the demo video below, come to our ECOOP’19 presentation next Thursday, or talk to us during the ECOOP poster session!

So far, it is early work, and a brave new idea paper, but despite various challenges ahead, we think it can make a difference.

You can find the abstract and preprint of the paper below.

Abstract

Many of today’s software systems are parallel or concurrent. With the rise of Node.js and more generally event-loop architectures, many systems need to handle concurrency. However, its non-deterministic behavior makes it hard to reproduce bugs. Today’s interactive debuggers unfortunately do not support developers in debugging non-deterministic issues. They only allow us to explore a single execution path. Therefore, some bugs may never be reproduced in the debugging session, because the right conditions are not triggered. As a solution, we propose multiverse debugging, a new approach for debugging non-deterministic programs that allows developers to observe all possible execution paths of a parallel program and debug it interactively. We introduce the concepts of multiverse breakpoints and stepping, which can halt a program in different execution paths, i.e. universes. We apply multiverse debugging to AmbientTalk, an actor-based language, resulting in Voyager, a multiverse debugger implemented on top of the AmbientTalk operational semantics. We provide a proof of non-interference, i.e., we prove that observing the behavior of a program by the debugger does not affect the behavior of that program and vice versa. Multiverse debugging establishes the foundation for debugging non-deterministic programs interactively, which we believe can aid the development of parallel and concurrent systems.

  • Multiverse Debugging: Non-deterministic Debugging for Non-deterministic Programs
    C. Torres Lopez, R. Gurdeep Singh, S. Marr, E. Gonzalez Boix, C. Scholliers; In 33rd European Conference on Object-Oriented Programming, ECOOP'19, p. 27:1–27:30, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2019.
  • Paper: PDF
  • DOI: 10.4230/LIPIcs.ECOOP.2019.27
  • Appendix: online appendix
  • BibTex: bibtex 
    @inproceedings{TorresLopez:2019:MD,
  abstract = {Many of today's software systems are parallel or concurrent. With the rise of Node.js and more generally event-loop architectures, many systems need to handle concurrency. However, its non-deterministic behavior makes it hard to reproduce bugs. Today's interactive debuggers unfortunately do not support developers in debugging non-deterministic issues. They only allow us to explore a single execution path. Therefore, some bugs may never be reproduced in the debugging session, because the right conditions are not triggered. As a solution, we propose multiverse debugging, a new approach for debugging non-deterministic programs that allows developers to observe all possible execution paths of a parallel program and debug it interactively. We introduce the concepts of multiverse breakpoints and stepping, which can halt a program in different execution paths, i.e. universes. We apply multiverse debugging to AmbientTalk, an actor-based language, resulting in Voyager, a multiverse debugger implemented on top of the AmbientTalk operational semantics. We provide a proof of non-interference, i.e., we prove that observing the behavior of a program by the debugger does not affect the behavior of that program and vice versa. Multiverse debugging establishes the foundation for debugging non-deterministic programs interactively, which we believe can aid the development of parallel and concurrent systems.},
  acceptancerate = {0.37},
  appendix = {https://doi.org/10.4230/DARTS.5.2.4},
  author = {Torres Lopez, Carmen and Gurdeep Singh, Robbert and Marr, Stefan and Gonzalez Boix, Elisa and Scholliers, Christophe},
  blog = {https://stefan-marr.de/2019/07/what-if-we-could-see-all-concurrency-bugs-in-the-debugger/},
  booktitle = {33rd European Conference on Object-Oriented Programming},
  day = {15},
  doi = {10.4230/LIPIcs.ECOOP.2019.27},
  isbn = {978-3-95977-111-5},
  issn = {1868-8969},
  keywords = {Actors AmbientTalk Concurrency Debugging FormalSemantics Formalism MeMyPublication Multiverse NonDeterminism Redex myown},
  month = jul,
  number = {27},
  pages = {27:1--27:30},
  pdf = {https://stefan-marr.de/downloads/ecoop19-torres-lopez-et-al-multiverse-debugging-non-deterministic-debugging-for-non-deterministic-programs.pdf},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  series = {ECOOP'19},
  title = {{Multiverse Debugging: Non-deterministic Debugging for Non-deterministic Programs}},
  volume = {134},
  year = {2019},
  month_numeric = {7}
}