[Paper Review] Correctness Attraction - A Study of Stability of Software Behavior Under Runtime Perturbation
Short Introduction to This Paper
Many perturbations do not break the correctness in programs. This phenomenon is called "correctness attraction". This paper devises a novel protocol, which considers a systematic exploration of the perturbation space as well as perfect oracles to determine the correctness of the output. To this extent, a qualitative manual analysis enables it to set up the first taxonomy ever of the reasons behind correctness attraction.
Highlights of This Paper
- A protocol called ATTRACT to study the stability of programs under perturbation
- Explored the perturbability of 10 subjects for two perturbation models, PONE for integers and PBOOL for booleans.
- Original taxonomy of the causes behind correctness attraction: natural randomization, potential aternative executions, fixed point effect, extra resources, relaxed problem, nullified perturbation, overfit to input data
- An execution perturbation is a runtime change of the value of one variable in a statement or an expression. An execution perturbation has 3 characteristics: time: when the change occurs (e.g. at the second and the fourth iteration of a loop condition), location: where in the code (e.g. on variable ‘i’ at line 42) and perturbation model: what is this change, according to the type of the location (e.g. +1 on an integer value)
- The perturbation space for an input is composed of of all possible unique perturbed executions according to a perturbation model
- Correctness attraction is the phenomenon by which the correctness of an output is not impacted by execution perturbation. Correctness attraction means that one can perturb an execution while keeping the output correct according to a perfect oracle
Relevant Future Works
- The taxonomy is probably not complete since the benchmark does not reflect the diversity of software