Correctness Attraction: A Study of Stability of Software Behavior Under Runtime Perturbation

By: Benjamin Danglot, Philippe Preux, Benoit Baudry, Martin Monperrus (@diversifyprojec, @stamp_project, @martinmonperrus)

Associate Editor: Federica Sarro (@f_sarro)

In the introductory class of statics, a branch of mechanics, one learns that there are two kinds of equilibrium: stable and unstable. Consider Figure 1, 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.

Figure 1: The concept of stable and unstable equilibrium in physics motivate us to introduce the concept of “correctness attraction”.

In one of his famous lectures [2], 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.

In our recent work [1], we have performed an original experiment to per- turb 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 incor- rect 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”. These programs and their oracles are described in Table 1. 

Table 1: Dataset of 10 subject programs used in our experiments.

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 com- mon 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 [1].

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”.

References

[1] B. Danglot, P. Preux, B. Baudry, and M. Monperrus. Correctness Attrac- tion: A Study of Stability of Software Behavior Under Runtime Perturba- tion. Empirical Software Engineering, 2017.

[2] E. W. Dijkstra. On the cruelty of really teaching computing science. Dec. 1988.