Empirical study
Correctness attraction: a study of stability of software behavior under runtime perturbation.
Authors: Benjamin Danglot, Philippe Preux, Benoit Baudry and Martin Monperrus
Venue: Empirical Software Engineering 23, 2086–2119 (2018). https://doi.org/10.1007/s10664-017-9571-8
Publication date: December 21, 2017
Abstract: Can the execution of software be perturbed without breaking the correctness of the output? In this paper, we devise a protocol to answer this question from a novel perspective. In an experimental study, we observe that many perturbations do not break the correctness in ten subject programs. We call this phenomenon “correctness attraction”. The uniqueness of this protocol is that it considers a systematic exploration of the perturbation space as well as perfect oracles to determine the correctness of the output. To this extent, our findings on the stability of software under execution perturbations have a level of validity that has never been reported before in the scarce related work. A qualitative manual analysis enables us to set up the first taxonomy ever of the reasons behind correctness attraction.
Tags: Perturbation analysis Software correctness Empirical study
Correctness Attraction: Live-Demo
Authors: Benjamin Danglot, Philippe Preux, Benoit Baudry and Martin Monperrus
Venue: Empirical Software Engineering 23, 2086–2119 (2018). https://doi.org/10.1007/s10664-017-9571-8
Publication date: December 21, 2017
Abstract: Can the execution of software be perturbed without breaking the correctness of the output? In this paper, we devise a protocol to answer this question from a novel perspective. In an experimental study, we observe that many perturbations do not break the correctness in ten subject programs. We call this phenomenon “correctness attraction”. The uniqueness of this protocol is that it considers a systematic exploration of the perturbation space as well as perfect oracles to determine the correctness of the output. To this extent, our findings on the stability of software under execution perturbations have a level of validity that has never been reported before in the scarce related work. A qualitative manual analysis enables us to set up the first taxonomy ever of the reasons behind correctness attraction.
Description: Correctness attraction is the phenomenon that a system is able to recover from changes injected into its state, which is called perturbations, and yet produce a correct output. Here, you can apply our protocol to an implementation of a quicksort algorithm. For every integer (literals and expressions), a perturbation consists to add 1 with a given probability. In the other hand, it does the same for boolean literals and expressions by negating them.
Tags: Perturbation analysis Software correctness Empirical study