Correctness Attraction: Software Behavior is Stable Under Runtime Perturbation
In the introductory class of statics, a branch of mechanics, one learns that there are two kinds of equilibrium: stable and unstable. Consider this image, where a ball lies respectively in a basin (left) and on the top of a hill (right). The first ball is in a stable equilibrium, one can push it left or right, it will come back to the same equilibrium point. On the contrary, the second one is in an unstable equilibrium, a perturbation as small as an air blow directly results in the ball falling away.
In one of his famous lectures [1], Dijkstra has stated a fundamental hypothesis about the nature of software, “the smallest possible perturbations — i.e. changes of a single bit — can have the most drastic consequences.”. Viewed under the perspective of statics, it means that Dijkstra considers software as a system that can only be in an unstable equilibrium, or to put it more precisely, that the correctness of a program output is unstable with respect to perturbations.
Perturbing program execution
In our recent work [2], we have performed an original experiment to perturb program executions. Our protocol consists in perturbing the execution of programs according to a perturbation model and observing whether this has an impact on the correctness of the output. We observe two different outcomes: the perturbation breaks the computation and results in an incorrect output (unstable under perturbation), or the correctness of the output is stable despite the perturbation.
Let’s consider the PONE perturbation model which consists in increment (+1) integer values at runtime. At some point during the execution, we increment an integer value. An equivalently small perturbation model is MONE, which decrements integers. In Dijkstra’s view, PONE and MONE are the smallest possible perturbations one can do on integer data.
We perform the experiment on 10 Java programs which size range from 42 to 568 lines of code. They all have the property that we can perfectly assess the correctness of the output thanks to a “perfect oracle”.
In total, we perturb 2917701 separate executions of the ten programs. Among those 2917701 perturbed executions, 1977199 (67.76%) yield a correct output. This result surprised us, because it goes against the common intuition that programs are brittle. Our literature review revealed that this empirical phenomenon has no name, yet.
Correctness attraction
When a perturbation does not break output correctness, we observe “stable correctness”. This is conceptually related to the concepts of “stable equilibrium” and “attraction basin” in physics. Due to this conceptual proximity, we name the observed phenomenon: “correctness attraction“. As shown in Figure 1, the intuition behind correctness attraction can be graphical. The correctness attraction basin at the left hand-side of Figure 1 refers to the input points for which a software system eventually reaches the same fixed and correct point according to a perturbation model.
If you want to read more about this fascinating phenomenon, we discuss the reasons behind correctness attraction in our paper [2]. This original work opens interesting directions in the area of software reliability. If we engineer techniques to automatically improve correctness attraction, we would obtain zones in the code that can accommodate more perturbations of the runtime state, and those zones could be then deemed “bug absorbing zones”.
To receive regular news about our research about software at KTH Royal Institute of Technology, shoot an email at repairnator.subscribe@4open.science! — Martin
- [1] B. Danglot, P. Preux, B. Baudry and M. Monperrus (2017) Correctness Attraction: A Study of Stability of Software Behavior Under Runtime Perturbation. Empirical Software Engineering.
- [2] E. W. Dijkstra (1988–12) On the cruelty of really teaching computing science.
