PaperlayerView exact revision on arXiv

Source-linked AI summary

Causality in Configurable Software Systems

Clemens Dubslaff, Kallistos Weis, Christel Baier, Sven Apel

arXiv:2201.07280v2cs.SEcs.LO

TL;DR

Huge configuration spaces make defects and inadvertent behavior difficult to detect, predict, and explain, while explainability research remains in its infancy. The paper introduces counterfactual feature causality and evaluates methods for identifying and interpreting feature causes across configurable systems.

  • Problem

    Huge configuration spaces make detecting, predicting, and explaining defects and inadvertent behavior challenging, while research on explainability remains in its infancy.

    Source: §1 · p. 1

  • Method

    The paper defines counterfactual feature causes for emergent system behavior and connects them to prime implicants to compute and interpret causes and feature interactions.

    Source: §1 · pp. 1–2

  • Results

    Across community benchmarks and real-world systems, the analyses help pinpoint features relevant to system properties and illustrate how feature interactions can be detected and quantified.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The framework supports identifying features behind bugs, assessing configuration responsibility for poor performance, and determining necessary feature interactions.

    Source: §1 · p. 1

    For non-functional properties, some experimental results rely on machine learning, and effect-set choices affect how far causality serves as an explication.

    Source: §7.1 · p. 10

Abstract

from arXiv · show

Detecting and understanding reasons for defects and inadvertent behavior in software is challenging due to their increasing complexity. In configurable software systems, the combinatorics that arises from the multitude of features a user might select from adds a further layer of complexity. We introduce the notion of feature causality, which is based on counterfactual reasoning and inspired by the seminal definition of actual causality by Halpern and Pearl. Feature causality operates at the level of system configurations and is capable of identifying features and their interactions that are the reason for emerging functional and non-functional properties. We present various methods to explicate these reasons, in particular well-established notions of responsibility and blame that we extend to the feature-oriented setting. Establishing a close connection of feature causality to prime implicants, we provide algorithms to effectively compute feature causes and causal explications. By means of an evaluation on a wide range of configurable software systems, including community benchmarks and real-world systems, we demonstrate the feasibility of our approach: We illustrate how our notion of causality facilitates to identify root causes, estimate the effects of features, and detect feature interactions.

1 INTRODUCTION

Configurable systems’ large configuration spaces make defects and emergent behavior difficult to explain. The paper introduces feature-level causal reasoning and methods to identify, interpret, and compute causes across configurable systems.

1 INTRODUCTION

  • Feature causality identifies feature selections that explain emergent system behaviors, including bugs, poor performance, and interactions.It adapts counterfactual actual causality to system configurations [46] [47].Source: §1 · pp. 1–2
  • Feature-based explanations can be more actionable than low-level traces because features often have domain meaning and can guide developers toward root causes or configuration changes.Developers may focus on implicated feature implementations or disallow or coordinate feature activation.Source: §1 · p. 1
  • The approach is language-, architecture-, and environment-independent and supports variability-aware white-box and black-box analyses.Unlike cited code-level causal methods, it does not require repeating analysis across many configurations,,.Source: §1 · p. 1
  • Experiments on community benchmarks and real-world systems illustrate how feature causes can pinpoint relevant features and help detect and quantify interactions.The evaluation covers several configurable systems and properties.Source: §1 · p. 2
  • Feature causes coincide with certain prime implicants, enabling an algorithm to compute all causes and methods to explain them through formulas, responsibility, blame, and interactions.The paper also presents a BDD-based prototype.Source: §1 · p. 2

2 BACKGROUND

The background formalizes interpretations and their semantics, then models configurable systems as feature sets with valid configurations. It also defines prime implicants as minimal partial interpretations sufficient for a set of interpretations.

2 BACKGROUND

  • A partial interpretation assigns truth values to some variables, and its semantics comprises all total interpretations that agree with those assignments.The support records which variables are assigned; a total interpretation assigns every variable.Source: §2 · p. 2
  • A prime implicant is a minimal partial interpretation whose covered total interpretations all belong to the target set.Removing any assigned variable must make it no longer sufficient for that set.Source: §2 · p. 2
  • A configurable system is modeled by Boolean features; a configuration is a total feature assignment, and valid configurations correspond to implementable variants.Feature diagrams can specify the constraints that determine validity.Source: §2 · p. 2

3 FEATURE CAUSALITY

Feature causes are partial feature selections that ensure an effect while satisfying a counterfactual minimality condition. The paper explains how to form effect sets and connects causes to prime implicants to compute them.

3 FEATURE CAUSALITY

  • A feature cause must cover at least one valid effect instance, cover no valid non-effect configuration, and cease to ensure the effect when any assignment is dropped.The counterfactual condition supplies a valid non-effect witness for each assigned feature and enforces minimality.Source: §3 · p. 3
  • For the email example, selecting AES or RSA individually causes long decipher time, and selecting encryption while deselecting Caesar is another cause.Explicitly not selecting a feature can therefore be part of a cause.Source: §3 · p. 3

3.1 Effect Properties and Sets

  • An effect set collects valid configurations where an effect property holds; it can be derived from functional analyses or quantitative analyses of properties such as performance, failure probability, or energy use.For a quantitative result, the paper defines the effect set by thresholding the analysis values.Source: §3.1 · pp. 3–4
  • Computing valid-configuration and effect sets may itself involve exponentially many configurations, although symbolic variability-aware analyses can address this blowup.This cost depends on the analysis used and is independent of the causal framework.Source: §3.1 · p. 4

3.2 Computation of Feature Causes

  • The computation algorithm generates prime implicants of the non-valid configurations together with effects, then removes candidates that are not sufficient for the effect.A candidate is retained only if it covers at least one effect instance.Source: §3.2 · p. 4
  • The algorithm computes all causes in polynomial time in the number of total interpretations, but can be exponential in the number of features in the worst case.The valid configurations, effect set, and number of prime implicants may each be exponential in the feature count.Source: §3.2 · p. 4

4 CAUSAL EXPLICATIONS

Because the number of feature causes can be exponential, listing them is impractical; causal explications process cause sets into useful representations and measures. The section develops formula simplification, cause–effect covers, responsibility and blame, and feature-interaction methods.

4.1 Distributive Law Simplification

  • Distributive law simplification factors shared selections in a DNF formula, reducing its length while preserving the ability to reconstruct the original causes; a heuristic factors frequently occurring literals.The heuristic is practical because finding a minimum-size formula through these transformations is computationally hard.Source: §4.1 · p. 5

4.2 Cause–Effect Covers

  • Cause–effect covers are sets of causes whose interpretations cover every effect configuration; finding a minimum-size cover is computationally hard.Heuristics that produce nearly minimal covers are of practical interest.Source: §4.2 · p. 5

4.3 Responsibility and Blame

  • Feature responsibility measures a feature’s local contribution to an effect through the minimum number of feature switches needed for a counterfactual witness.A feature absent from every cause covering the context has no responsibility there.Source: §4.3 · pp. 5–6
  • Blame is expected responsibility over valid configurations under a chosen probability distribution, which can represent user choices or the frequency of effect configurations.Uniform distributions over valid configurations or effects are options when relevant statistics are unavailable or a developer perspective is desired.Source: §4.3 · p. 6

4.4 Feature Interactions

  • Minimal-support feature causes correspond one-to-one with t-way interaction witnesses: sufficient partial configurations with no sufficient configuration of support size t−1.A necessary interaction requires all minimal feature causes to have support involving at least two features.Source: §4.4 · p. 6
  • Feature causes can isolate interaction witnesses locally: switching a feature in a cause can make the effect cease to emerge, identifying that feature as necessary in that instance.The paper’s example uses a cause to witness the interaction between encryption and Caesar being disabled; this operational criterion may guide deeper white-box analysis and reduce the naive search space.Source: §4.4 · pp. 6–7
  • Interaction responsibility and blame assign relevance to candidate feature interactions, with higher values indicating stronger relevance and lower values weaker relevance.The approach addresses the interpretive difficulty that can remain because causes and their expansions may be exponential in the number of features.Source: §4.4 · p. 7

5 EXPERIMENT SETUP

The evaluation tests whether feature causality can identify causes, provide concise explanations, guide configuration, and detect interactions across configurable systems. The experiments use a BDD-based prototype and a diverse set of systems and effect properties.

5 EXPERIMENT SETUP

  • Experiments on community benchmarks and real-world systems assessed feature-cause computation, causal explanations, configuration guidance, and feature-interaction detection.The four research questions ask whether causes can be computed effectively, explications are concise, blame can guide configurations, and interactions or anomalies can be detected and isolated.Source: §5 · p. 7, §5.1 · p. 7

5.2 Implementation

  • FeatCause represents valid configurations and effects as reduced ordered BDDs and uses prime implicants to compute feature causes after direct FC1/FC2 checking timed out on small examples.The implementation uses PyEDA and Espresso, with converters for configuration and effect sets from variability-aware analyses and existing datasets.Source: §5.2 · p. 7

5.3 Subject Systems

  • The subject systems span community benchmarks and real-world functional and non-functional analyses, including model checking, reliability, and performance prediction.Examples include Minepump, Elevator, and CFDP; BSN and VCL reliability models; and systems such as LLVM, BerkeleyDB, Lrzip, x264, Apache, Linux, SQLite, and WGet.Source: §5.3 · pp. 7–8
  • Table 1 reports experiment counts, valid configurations, feature counts, computation times, and average sizes of effect sets, causes, cause–effect covers, and DLS formulas.The statistics are organized by effect-property type and subject systems.Source: §5.3 · p. 8, Table 1 · p. 8

5.4 Operationalization

  • For RQ1 and RQ2, the analysis computes causes for an effect and its negation, then derives covers, DLS formulas, responsibility, and blame.For RQ3 and RQ4, it computes single-feature and pairwise interaction blame, assuming a uniform distribution over effects.Source: §5.4 · p. 8

6 RESULTS

Across the evaluated systems, feature causes were computable in reasonable time, and DLS formulas and most-general causes provided substantial reductions for concise explanations. Case studies show how blame guides configuration choices and how interaction analysis can expose runtime anomalies.

6.1 Descriptive Statistics (RQ1 and RQ2)

  • Feature causes were computable in reasonable time, while DLS formulas and most-general causes substantially reduced cause sets and cause–effect covers.Computation took a few seconds for most systems; most-general-cause covers nearly always matched Espresso minimization, and DLS reduced formulas by almost three quarters on average for Elevator1.Source: §6.1 · p. 8

6.2 Feature Cause Explications (RQ2)

  • In Minepump, seven causes summarized the stabilization property across 128 configurations, and selecting High, Start, and one of Stop, Low, or MethaneAlarm covered all causally relevant configurations.Three causes were most general and had the highest partial-configuration blame; the longest cause had the smallest blame.Source: §6.2 · p. 9, Table 2 · p. 9

6.3 Causality-guided Configuration (RQ3)

  • For VCL reliability, tight constraints favor protecting Acceleration and then Integrator, whereas higher acceptable failure rates favor Sum2 and Sum3 over Integrator.The failure-probability measures were increased by a factor of 100 to ensure timely analysis; the authors say this does not affect the causal analysis of protection impact.Source: §6.3 · p. 9, §6.4 · p. 9
  • Feature causes and blame quantify feature impact on a desired effect and can guide the configuration process.In the VCL example, the preferred protection components change with the reliability threshold.Source: §6.3 · p. 9

6.4 Feature Interactions (RQ4)

  • For Lrzip and Zpaq at thresholds above 700 seconds, runtime-threshold exceedance is attributed to two-way interactions between the algorithm and compression levels, with no other features blamed.At thresholds up to 600 seconds, Zpaq is instead a one-way interaction witness; as the threshold increases, compression level becomes increasingly responsible for longer runtime.Source: §6.4 · p. 10
  • Lrzip compression level 9 is anomalous: its mean runtime was 830.5 seconds, below levels 7 and 8, and it was not causally relevant to exceeding the 900-second threshold.The corresponding mean runtimes were 1,064.9 seconds at level 7 and 1,181.7 seconds at level 8.Source: §6.4 · p. 10

7 DISCUSSION

The discussion addresses threats to experimental validity and positions feature causality among work on configurable-system analysis and causal reasoning. It contrasts the paper’s approach with prior work on feature interactions, code-level defect localization, and actual-cause computation.

7.1 Threats to Validity

  • Non-functional effect sets partly rely on machine learning, and blame assumes uniformly distributed effects; other distributions may change quantitative results but are unlikely to alter causal-influence conclusions.Effect-set choices affect how fully causality can serve as an explication, not whether the causality definitions apply.Source: §7.1 · p. 10
  • Subject-system and effect-set choices threaten external validity; the evaluation mitigates this with diverse real-world systems, community benchmarks, and a large-scale redundancy system.The included systems cover multiple properties and application areas.Source: §7.1 · p. 10

7.2 Related Work

  • The related-work discussion identifies combining configurable-system analysis with causal reasoning as an unaddressed foundation for finding defect causes.Existing analysis methods can identify defects and their locations, while root-cause identification remains challenging.Source: §7.2 · p. 11
  • Configurable-system research covers testing, sampling, static analysis, and model checking; work on responsible features has focused especially on feature interactions [e.g. 57, 72, 94].Prior work also defines non-functional interactions and black-box feature interaction faults,,.Source: §7.2 · p. 11
  • The DLS method prioritizes causal information over formula reduction, unlike von Rhein et al.’s two-level logic minimization approach.The cited approach can use Espresso heuristics.Source: §7.2 · p. 11
  • For Boolean actual causality, Ibrahim and Pretschner use SAT solving, but computing all causes checks every partial interpretation and incurs an additional exponential blowup [50].The paper says its prime-implicant computations avoid that additional blowup.Source: §7.2 · p. 11
  • Prior program-level approaches locate defect origins using traces, delta debugging, counterexample traces, or causal inference over statement and test-coverage graphs.These examples situate configurable-system feature causality alongside code- and execution-level defect-localization work.Source: §7.2 · p. 11
  • Iqbal et al. use statistical counterfactual reasoning to detect performance bugs, whereas this paper focuses on rigorous analysis of actual rather than type causality [51].Nair et al.’s incremental configuration approach to optimize non-functional properties complements the paper’s causality-guided configuration example.Source: §7.2 · p. 11

8 CONCLUDING REMARKS

The paper concludes that its counterfactual framework and algorithms can identify and explain causes in configurable systems. The authors report effectiveness on real-world systems and benchmarks, and identify larger systems, source-code root causes, and dynamic settings as directions for further work.

8 CONCLUDING REMARKS

  • The prototype’s algorithms run in reasonable time on real-world systems of varying sizes, and the explications support causality-guided configuration and feature-interaction isolation.The evaluation includes real-world systems and popular community benchmarks.Source: §8 · p. 11
  • Directly integrating cause computation into optimized prime-implicant algorithms, including BDD-level computation, may make causes feasible for larger systems.The authors point to state-of-the-art BDD libraries such as CUDD as a possible enhancement.Source: §8 · p. 11
  • A proposed extension combines feature-interaction blame with in-depth white-box analysis to pinpoint root causes in source code across effect properties.Source: §8 · p. 11
  • The authors identify context-aware and dynamic configurable systems as future settings for extending causal analysis to context causes and runtime feature interactions.Dynamic systems can activate or deactivate features during runtime, for example during upgrades and downgrades.Source: §8 · p. 11
Loading 2201.07280v2…