Variability Fault Localization by Abstract Interpretation and its Application to SPL Repair

Abstract

Fault localization is an important step in software debugging that aims to isolate and localize the bugs (errors) to a small part of the program. This becomes more challenging in Software Product Lines (SPLs) due to the variable nature of bugs (so-called variability bugs). This paper introduces a novel variability fault localization algorithm for SPLs. Moreover, we present its practical application for automatic repair of variability bugs in SPLs.

Given a buggy SPL (program family) and an assertion to be satisfied, our variability fault localization algorithm infers so-called lifted (variability-specific) error invariants in all locations, which over-approximate the reachable states at the given locations that may produce the bug if the execution continues from those locations in some particular variants. The lifted error invariants are used for statement-wise lifted semantic slicing of buggy SPLs, which removes the statements irrelevant for assertion violation in certain variants containing some combinations of features. Finally, the obtained slice family is applied for designing an efficient SPL repair algorithm, which repeatedly mutates the (feature and program) expressions in the statements identified as relevant for the variability bug until a correct SPL is found.

We have implemented an experimental tool for variability fault localization and repair of #ifdef-annotated SPLs written in C. We have evaluated our approach on a set of benchmarks, and the experimental results confirm the effectiveness of our approach.