Fidgeting to the point of no return

Abstract

In previous work, we introduced the alternative pasts algorithm that delays the assignment of values to variables until their usage. Whenever a variable is used, the algorithm chooses one of its past values that is consistent with some possible execution. The alternative pasts algorithm can be seen as belonging to a class of algorithms that shadow the execution and may choose at any point to modify the values of some of the variables. We build on this work and extend it in two directions. First we show a more powerful shadowing algorithm that can delay not only writes but also reads and other kinds of instructions, at most until a relevant control decision is taken, which is the longest possible delay for algorithms of this class. We prove that this algorithm inherits the ability of the alternative pasts algorithm to generate significantly different interleavings, which are guaranteed to execute differently. In addition, we show a new use for the two algorithms, namely alternative replay. Unlike regular replay, where the execution of the program is reproduced, alternative replay is an execution that did not happen before but could have happened. For example, if a bug did not materialize, alternative replay can be used to show the user alternative execution in which the impact of the bug can be observed.