§ INTRODUCTION

Configurable software systems offer a wide variety of configuration options that control
the activation of features desired by the user
and that influence critical functional and non-functional properties such as performance.

The often huge configuration spaces render the detection, prediction, and explanation
of defects and inadvertent behavior challenging tasks.
While there are specifically tailored analysis methods to tackle this
challenge <cit.>, research on their explainability is still in its infancy <cit.>.
The potentially exponential number of system configurations and corresponding
analysis results, bug reports, or other feature-dependent properties
demand techniques for a meaningful and feasible interpretation.

In this paper, we present a set of fundamental concepts and methods to identify and interpret
properties of configurable systems at the level of features by causal reasoning.
We introduce the notion of feature causes as feature selections that
are the reason for emergent system behaviors. Our notion of feature causality is inspired
by the seminal counterfactual definition of actual causality by Halpern and
Pearl <cit.>.
Relevant analysis and reasoning tasks that we address include to determine
features that cause a bug, the degree to which some configurations are responsible for
bad system performance, or which features necessarily have to interact for
inadvertent behavior.

Since features correspond to system functionalities specified
by software engineers, they often have a dedicated meaning in the target
application domain <cit.>.

To this end, defects (and other behaviors of interest) detected at the level
of features can provide important insights for the resolution of
variability bugs <cit.> and
configuration-dependent behavior <cit.>.

As such, they are certainly more informative and actionable than low-level
program traces alone.

Developers may choose to focus on those feature implementations identified as
root causes of bugs or simply disallow or coordinate the activation of certain
features when defects are related to them.

Our presented techniques are generic in the sense that they are neither language-,
architecture-, nor environment-specific and applicable within any effective method to
analyze or test variability-aware properties.
To this end, causal reasoning on both variability-aware white-box and
black-box analyses is supported.

This complements existing causal reasoning techniques for the detection of root causes:
Approaches such as delta-debugging <cit.>,
causal testing <cit.>, or causal trace analysis <cit.>
require a white-box analysis that operates at the level of code and are not variability-aware.
Hence, they usually would have to be applied on a multitude of system
configurations for a variability-aware causal analysis, suffering from a
combinatorial blowup.
We envision applications of feature causality at those development phases where
analysis methods are used, for instance, in software product line engineering.

Also in production-level deployments our techniques shall be useful to optimize
software through causally relevant configurations.

We present algorithms to compute feature causes, represent, and interpret them
by means of concise logic formulas, feature interactions, and
responsibility and blame <cit.>.

Our prototypical implementation relies on binary decision diagrams (BDDs) <cit.>
and the computation of prime implicants using the de-facto
standard two-level logic minimizer  <cit.>.
By means of an analysis of several configurable systems, including community benchmarks and
real-world systems, we investigate feature causes and their properties.
We demonstrate that our notion of feature causes and methods to represent them help to
pinpoint features relevant for the configurable system's properties and
illustrate how feature interactions can be detected and quantified.

In summary, our contributions are:

$\bullet$     We introduce the notion of feature causality inspired by the well-established counterfactual
definition of actual causality by Halpern and Pearl <cit.>.

$\bullet$     We show that feature causes coincide with certain prime implicants,
leading to an algorithm to compute all feature causes.

$\bullet$     We provide methods to interpret and represent feature causes by propositional formulas,
responsibility and blame, and potential feature interactions.

$\bullet$     We offer a BDD-based prototype to compute and represent
feature causes and feature interactions.

$\bullet$     We conduct several experiments illustrating how to determine and reason
about feature causes in different realistic settings.

Proofs of the theoretical statements are included in <cit.>.
The source code of our implementation and raw data to reproduce our
experiments are publicly available <cit.>.

§ BACKGROUND

In this section, we revisit basic concepts and notions
from logics and configurable systems used throughout the paper.

A partial interpretation over a set $X$ is a partial mapping
$\partial\colon X \pa \{\true,\false\}$. We denote by $\supp(\partial)$ the
support of $\partial$, i.e., the set of all elements $x\in X$ where $\partial(x)$ is
defined. We say that $\partial$ is a total interpretation if $\supp(\partial)=X$
and denote by $\Partial(X)$ and $\Total(X)$ the set of partial and total
interpretations, respectively.
Given a partial interpretation $\partial\in\Partial(X)$, we define its
semantics $\Sem{\partial}\subseteq\Total(X)$ as the set of all total
interpretations $\total\in\Total(X)$ where for all $x\in\supp(\partial)$
we have $\partial(x)=\total(x)$.
We say that $\partial\in\Partial(X)$ covers $\partial'\in\Partial(X)$
if $\Sem{\partial'}\subseteq\Sem{\partial}$.
For a set of partial interpretations
$\cP\subseteq\Partial(X)$, we define $\Sem{\cP}=\bigcup_{\partial\in\cP} \Sem{\partial}$.

The $x$-expansion of a partial interpretation $\partial\in\Partial(X)$

is the partial interpretation $\partial\gen{x}\in\Partial(X)$ where
$\supp(\partial\gen{x})=\supp(\partial){\setminus} \{x\}$
and where $\partial\gen{x}(y)=\partial(y)$ for all $y\in \supp(\partial){\setminus} \{x\}$.

For a set of total interpretations $\cT\subseteq\Total(X)$, an implicant of
$\cT$ is a partial interpretation $\partial\in\Partial(X)$ where
$\Sem{\partial}\subseteq\cT$. We call $\partial$ a prime implicant
if $\partial$ is minimal, i.e., $\Sem{\partial\gen{x}}\not\subseteq\cT$
for all $x\in\supp(\partial)$.

Propositional logics
A propositional logic formula over a set $X$ is an expression defined by the grammar

$\phi \en{=} \true \mid \false \mid x \mid \neg\phi \mid
\phi\wedge\phi \mid \phi\vee\phi$

where $x$ ranges over $X$.
The length $|\phi|$ of a formula $\phi$ is recursively
defined by $|\true| =|\false| =|x| =1$, $|\neg\phi| =|\phi|+1$, and
$|\phi_0\wedge\phi_1| =|\phi_0\vee\phi_1| =|\phi_0|+|\phi_1|+1$.
For a partial interpretation $\partial\in\Partial(X)$, we write $\partial\models\phi$
if either $\phi = \true$, $\phi = x \in\supp(\partial)$ and $\partial(x)=\true$,
$\phi = \neg\psi$ and not $\partial\models\psi$, $\phi = \phi_0 \wedge \phi_1$ and
$\partial\models\phi_0$ and $\partial\models\phi_1$, and $\phi = \phi_0 \vee \phi_1$ and
$\partial\models\phi_0$ or $\partial\models\phi_1$. The semantics of $\phi$ is
the set of all satisfying total interpretations $\Sem{\phi}= \{ \total\in\Total(X) : \total\models\phi\}$.

Configurable systems
A widely adopted concept to model configurable systems is by means of
features <cit.>.
Features encapsulate optional or incremental units of functionality <cit.>
and are used to describe commonalities and variabilities of whole families of systems.
At an abstract level, we fix a set $\Feat$ of Boolean configuration options where
each element corresponds to some feature of the system.
We call a total interpretation $\total\in\Total(\Feat)$ over $\Feat$ a configuration,
which we usually describe by listing the selected features, i.e.,
the features $x\in\Feat$ where $\total(x)=\true$.
The set of Valid configurations $\ValidFeat\subseteq\Total(\Feat)$ comprises
those configurations for which there exists a corresponding system implementation,
usually specified by a feature diagram <cit.>.
A partial interpretation over $\Feat$ is called partial configuration.

matrix of nodes,nodes=feature

[feature] (root) email system;

(sub)[features,below=3mm of root,column sep=.5cm]
sign     encryption

(enc)[features,below=of sub-1-2,column sep=.5cm]
Caesar     AES     RSA

[optional] (sub-1-1.north) circle (.8mm);

edge (sub-1-1.north)
edge (sub-1-2.north);

[optional] (sub-1-1.north) circle (.8mm);
[optional] (sub-1-2.north) circle (.8mm);

edge (enc-1-1.north)
edge (enc-1-2.north)
edge (enc-1-3.north);

Feature diagram for the email system example
Feature diagram for the email system example

As the running example,	consider a simple email system over features $F=\{m,s,e,c,a,r\}$,
formalizing the base email system functionality,
optional features for signing and encryption,
and encryption methods Caesar, AES,
and RSA.
For the encryption features, we assume that exactly
one can be selected. The described variability constraints for the email system
are specified in the feature diagram shown in Figure <ref>,
leading to valid configurations

\[
\ValidFeat \en{=}
\{\, m, mec, mea, mer, ms, msec, msea, mser\,\}.
\]

§ FEATURE CAUSALITY

The notion of causality has been extensively studied in philosophy,
social sciences, and artificial intelligence <cit.>.
We focus on actual causality, describing
binary causal relationships between cause events $C$ and effect events $E$.
Halpern and Pearl formalized actual causality based on the concept of
counterfactual dependencies <cit.> using a structural-equation
approach <cit.>.
The idea of counterfactual reasoning <cit.> relies on the assumption
that $E$ would not have happened if $C$ had not happened before, which corresponds
to the standard “but-for” test used in law.

In this section, we take inspiration of the definition by Halpern and
Pearl <cit.> to establish a notion of causality
at the level of features.
Here, we interpret the selection of features as events considered for actual causality.
The basic reasoning task we address then amounts to
determine those feature selections that cause a given effect property.
Examples for effect properties are “the execution time is longer than five minutes”
or “the system crashes”.

We assume to have described the effect properties as
effect set $\Effects\subseteq\ValidFeat$ of valid
configurations for which an effect property can be observed.
Elements of $\Effects$ are called effect instances.
All other valid configurations in $\ValidFeat{\setminus}\Effects$ are
assumed not to exhibit the effect.
Feature selections are naturally specified by partial configurations.
Clearly, a partial configuration $\gamma$ can only be a cause of the
effect if $\gamma$ ensures the effect to emerge, i.e.,
all valid configurations covered by $\gamma$ are effect instances.
Furthermore, following counterfactual
reasoning, we require for $\gamma$ being a cause that, if we would select features
of $\gamma$ differently, there might be a configuration for which the effect does
not emerge. These two intuitive conditions on causality
are reflected in our formal definition of causes of $\Effects$ w.r.t. $\ValidFeat$:

A feature cause of an effect $\Effects$ w.r.t. valid
configurations $\ValidFeat$ is a partial configuration $\gamma\in\Partial(\Feat)$ where

*  	$\varnothing\neq\Sem{\gamma}\cap\ValidFeat\subseteq\Effects$ and

$\Sem{\gamma\gen{x}}\cap\ValidFeat \not\subseteq \Effects$ for all $x\in\supp(\gamma)$.

We denote by $\Causes$ the set of all causes for $\Effects$ w.r.t. $\ValidFeat$.

In case <ref> holds for a partial configuration $\gamma$, we say that
$\gamma$ is sufficient for $\Effects$ w.r.t. $\ValidFeat$ <cit.>.

The counterfactual nature of <ref> ensures that for every feature cause $\gamma$
and $x\in\supp(\gamma)$ there is a counterfactual witness
That is, a valid feature configuration where the effect does not emerge but where
changing one feature selection may yield an effect instance.

Note that <ref> ensures minimality of the feature cause w.r.t. its support,
i.e., dropping conditions on interpretations of features necessarily leads to
a partial configuration that is not sufficient for the effect anymore.
In the formal definition of Halpern and Pearl causality <cit.>,
counterfactuality and minimality are stated in two distinct conditions.

(2.5cm,.7cm) circle (2cm)
(4cm,.7cm) circle (5cm)
(4.3cm,.8cm) circle (.6cm)
(6cm,.4cm) circle (.6cm)
(0,0) rectangle ++(8cm,1.2cm)

[rounded corners=5pt] node[below left=.1cm] $\Total(\Feat)$;

[dred!50] ;

(2cm,-2cm) – (3cm,2cm) – (8cm,2cm) – (8cm,-2cm) – cycle;
[dgreen!50] ;

(3cm,.3cm) node $\Effects$;
(1.9cm,.29cm) node $\CEffects$;
(.3cm,1cm) node $\ValidFeat$;
(.4cm,.88cm) – (.53cm,.75cm);

[fill=orange!50, opacity=.6] node[below right=-.1cm, opacity=1] $\Sem{\gamma}$;

[fill=red] (1.5cm,.9cm) circle (.06cm) node[right] $\overline{\eta}$;
[fill=green] (4cm,.9cm) circle (.06cm) node[right] $\eta$;

[fill=blue!30, opacity=.6] node[opacity=1] $\Sem{\partial}$;

Feature configuration sets for feature causality
Configuration sets for feature causality

We usually denote configurations in $\Effects$ by $\eta$, counterfactual
witnesses in $\CEffects$ by $\overline{\eta}$, and feature causes by $\gamma$.
Figure <ref> depicts the relation between valid configurations,
effects, causes, and counterfactual witnesses.

Let us continue our running example of the configurable email system
introduced in Example <ref>.
We consider an effect property reflecting “long decipher time”, e.g., that it takes
in average more than three months for an attacker to decrypt an email.
Assume that this effect property can be observed by configurations
in which AES or RSA are selected, i.e., $\Effects = \{ mea, mer, msea, mser\}$.
Conversely, in all valid configurations in which AES and RSA are not selected,
the effect does not emerge.
In this setting, the encryption features AES and RSA are both causes since
all valid configurations with either feature show the effect.
Considered in isolation, AES and RSA are not necessary for the effect, as
one can choose the other encryption feature (RSA or AES, respectively) to ensure the effect.
The sign feature does not trigger the effect and is not a cause.

Interestingly, a further cause is given by selecting the encryption feature and explicitly
deselecting the Caesar feature, illustrating that also explicitly not selecting
features might be a cause of some effect.
This hints at the fact that causes can be represented
in different ways, addressed later in the paper.

Formalizing this intuition, we check whether the three partial configurations
$\gamma_a$, $\gamma_r$, and $\gamma_{e\bar{c}}$ given by

* $\supp(\gamma_a)=\{a\}$ with $\gamma_a(a)=\true$,

* $\supp(\gamma_r)=\{r\}$ with $\gamma_r(r)=\true$, and

*  $\supp(\gamma_{e\bar{c}})=\{e,c\}$ with $\gamma_{e\bar{c}}(e)=\true$
and $\gamma_{e\bar{c}}(c)=\false$

are indeed feature causes of $\Effects$ w.r.t. $\ValidFeat$ according to
Definition <ref>: First, note that
$\Sem{\gamma_{e\bar{c}}}\cap\ValidFeat = (\Sem{\gamma_a}\cup\Sem{\gamma_r})\cap\ValidFeat = \Effects$
and both, $\Sem{\gamma_a}\cap\ValidFeat$ and $\Sem{\gamma_r}\cap\ValidFeat$, are non-empty.
Hence, <ref> is fulfilled for $\gamma_{e\bar{c}}$, $\gamma_a$, and $\gamma_r$.

To check <ref>, we observe that
$\Sem{\gamma_a\gen{a}} = \Sem{\gamma_r\gen{r}} = \Total(\Feat)$	and

\begin{eqnarray*}
\Sem{\gamma_{e\bar{c}}\gen{e}} \cap\ValidFeat &=& \Effects\cup\{m, ms\},\text{ and}\\
\Sem{\gamma_{e\bar{c}}\gen{c}} \cap\ValidFeat &=& \Effects\cup\{mec, msec\}.
\end{eqnarray*}

Hence, $m$ is a counterfactual witness for $\gamma_a$, $\gamma_r$, and $\gamma_{e\bar{c}}$
w.r.t. $a$, $r$, and $e$, respectively, while $mec$ can serve as such for $\gamma_{e\bar{c}}$
and $c$. It is easy to check that there are no further feature causes since for all other
partial 	configurations sufficient for $\Effects$ w.r.t. $\ValidFeat$ (<ref>)
there are expansions towards $\gamma_a$, $\gamma_r$, or $\gamma_{e\bar{c}}$
(thus, violating <ref>).

§.§ Effect Properties and Sets

Our definition of feature causality relies on a given effect set, which is assumed
to comprise all those valid configurations where the effect property holds.
We now elaborate more on how to obtain effect sets
from analyzing configurable systems.
In fact, our generic definition supports
a multitude of effect properties for which the only assumption is that there is an
effective method to determine all configurations in which the effect property holds.
Such methods also include variability-aware white-box analyses <cit.>,
where the source code or operational behavior of system variants is accessible,
as well as black-box analyses relying on testing or sampling <cit.>.
In the following paragraphs, we exemplify how to obtain effect sets from
analysis results. Our discussions reflect the effect properties in the experimental
evaluation section (see Section <ref>) and do not claim to be exhaustive.

Functional properties
To reason about causality w.r.t. functional properties, the effect set can
be determined by variability-aware static analysis <cit.>
or model checking <cit.>.
In the latter case,
effect properties can be formalized, e.g., in a temporal logic such as
LTL <cit.> or CTL <cit.>.
Model checking configurable systems against LTL and CTL properties has broad tool
support <cit.>.
Given a formula $\varphi$ that specifies the effect property,
these tools explicitly return the effect set

\[
\Effects_\varphi \en{=}
\{ \total \in\ValidFeat : \total\models\varphi\}
\]

of valid configurations $\total\in\ValidFeat$ whose corresponding
system variants satisfy $\varphi$.
Since model checking is based on an exhaustive analysis, an analysis also exposes those
valid configurations for which the effect property does not hold.
The same is possible for variability-aware static analysis <cit.>.

Non-functional properties
Besides functional properties, also non-functional properties of configurable
systems can serve as effect property and give rise to an effect set.
Let $\rho\colon \ValidFeat \ra \Real$ be a function that results from a quantitative
analysis of the configurable system in question. Values $\rho(\total)$ for a valid configuration
$\total\in\ValidFeat$ may stand for the performance achieved, the probability
of failure, or the energy consumed in the system variant that corresponds to $\total$.
To obtain $\rho$ for real-world systems, Siegmund et al. <cit.>
presented a black-box method to generate linear-equation models for
performance measures by multivariable linear regression on sampled configurations.
Other black-box approaches rely on regression trees <cit.>, Fourier
learning <cit.>, or probabilistic programming <cit.>.
Related white-box approaches use insights of local measurements and taint analysis
information <cit.> or profiling information <cit.>.
Variability-aware probabilistic model checking pursues a white-box analysis approach
on state-based operational models where effect properties are
specified in quantitative variants of temporal logic <cit.>.
These approaches have been implemented in the tools $\profeat$ <cit.>
and $\qflan$ <cit.>.

Given $\rho$ that results from one of the analysis
approaches mentioned above, an effect set can be specified by imposing a
threshold $\thresh\in\Real$ combined with a comparison relation $\sim$ towards

\[
\Effects_{\rho\sim\thresh} \en{=}
\{ \total \in\ValidFeat : \rho(\total)\sim\thresh\}.
\]

In Example <ref>, we informally specified the effect
of a “long decipher time” as taking more than three months to decrypt
an email without having the encryption key available.
By a variability-aware quantitative analysis on the email system,
we may obtain a function $\rho$ that,
for a configuration $\total$, returns the minimal time in years to decipher
an email sent with the system variant corresponding to $\total$.
Analysis results could be, e.g., $\rho(\total)=0$ with no encryption,
$\rho(\total)=10^{-7}$ with Caesar, $\rho(\total)=1$ with AES, and $\rho(\total)=2$
with RSA selected in $\total$, respectively.
Then, $\Effects_{\rho>0.25}$ provides the effect set
$\Effects$ of Example <ref>.

On computing effect sets
The effect set and the set of valid configurations can be of exponential size
in the number of features. An efficient computation of these sets depends on the
analysis techniques used and are independent from our causal framework.
However, specifically tailored variability-aware analysis techniques can tackle
the exponential blowup, e.g., through symbolic representation of family models <cit.>.

§.§ Computation of Feature Causes

For a given effect set $\Effects$ and a set of valid configurations $\ValidFeat$
along with a partial configuration $\partial$, Definition <ref> directly
provides a polynomial-time algorithm to decide whether $\partial$
is a cause of $\Effects$ w.r.t. $\ValidFeat$ by checking <ref> and <ref>.
From this, we obtain a simple approach to compute the set $\Causes$ by successively
checking expansions for sets of features applied on elements in $\Effects$ as candidates
for causes. Since there might be exponentially many such expansions, this approach
easily renders infeasible already within a small number of features.

In this section, we present a practical algorithm to compute the set of causes,
which relies on a connection of Definition <ref> to the notion
of prime implicants (see Section <ref>):

For any partial configuration $\partial\in\Partial(\Feat)$

\[
\Sem{\partial}\cap\ValidFeat\subseteq\Effects \en{\text{ iff }}
\Sem{\partial}\subseteq \big(\Total(\Feat){\setminus}\ValidFeat\big)\cup\Effects.
\]

Following this lemma, every cause of $\Effects$ w.r.t. $\ValidFeat$
is also an implicant of $\big(\Total(\Feat){\setminus}\ValidFeat\big) \cup \Effects$
due to <ref> and even a prime implicant due to <ref>.
Conversely, every prime implicant $\partial$ of
$\big(\Total(\Feat){\setminus}\ValidFeat\big) \cup \Effects$ for which
$\Sem{\partial}\cap\Effects\neq\varnothing$ is a cause due to <ref>.
This directly suggests an algorithm to compute causes via prime implicants:
$\partial\in \cP$ where $\Sem{\partial}\cap\Effects = \varnothing$$\cP := \cP{\setminus}\{\partial\}$

Computation of feature causes via prime implicants
Computation of feature causes

Algorithm <ref> first generates prime implicants as cause
candidates and then removes those candidates that are not sufficient for
$\Effects$ w.r.t. $\ValidFeat$.
Figure <ref> reflects this situation where
$\gamma$ and $\partial$ are prime implicants with
$\gamma$ being a cause and $\partial$ not: at least one effect instance
is covered by $\gamma$, while this is not the case
for $\partial$ and hence would be removed by Algorithm <ref>.
Prime implicants of a set of configurations can be computed in polynomial time in
the size of the input set <cit.>, which directly leads to:

Given valid configurations $\ValidFeat\subseteq\Total(\Feat)$
and effect set $\Effects\subseteq\ValidFeat$,
Algorithm <ref> computes $\Causes$, the set of feature causes for
$\Effects$ w.r.t. $\ValidFeat$, in polynomial time in $|\Total(\Feat)|$.

Note that the set of valid configurations and the effect set can be both exponential in the
number of features and there might be exponentially many prime implicants <cit.>
in the worst case. Hence, Algorithm <ref> is exponential
in the number of features.

Let us illustrate the computation of feature causes of Example <ref>
by Algorithm <ref>. First notice that

\[
\big(\Total(\Feat)\setminus\ValidFeat\big)\cup\Effects \en{=}
\Total(\Feat)\setminus\{\, m, mec, ms, msec \,\}
\]

comprising $60$ feature configurations.
The prime implicants for this set are computed in Line <ref>, which yields

\[
\cP \en{=} \{\,\gamma_{\bar{m}}, \gamma_a, \gamma_r, \gamma_{e\bar{c}}, \gamma_{\bar{e}c}\,\}.
\]

Here, we used notations as in Example <ref>, e.g., $\supp(\gamma_{\bar{e}c})=\{e,c\}$,
$\gamma_{\bar{e}c}(e)=\false$, and $\gamma_{\bar{e}c}(c)=\true$.
Clearly, all configurations covered by $\gamma_{\bar{m}}$ or $\gamma_{\bar{e}c}$ are
not valid and hence also no effects. Thus, they are removed in Line <ref>, leading
to $\Causes=\{\gamma_a, \gamma_r, \gamma_{e\bar{c}}\}$.

§ CAUSAL EXPLICATIONS

Since the number of feature causes can be exponential in the number of features,

a mere listing of all causes is neither feasible nor expedient
for real-world software systems.
This holds for both, humans that have to evaluate causal
relationships in configurable systems, e.g., during software development,
and machines that might use feature causes for further processing and reasoning.

In this section, we present and discuss several methods to compute causal explications,
i.e., mathematical or computational constructs that arise from processing
feature causes to provide useful causal representations and measures <cit.>.
Explications are closely related to explanations,
by which we mean human-understandable objects employed within an integrated system,
e.g., in feature-oriented software development or in production-level deployments.

Our methods for computing explications rely on techniques from propositional logic and
circuit optimization <cit.>, responsibility and blame <cit.>,
and feature interactions <cit.>.

They all take a global perspective on sets of feature causes
rather than only considering single feature causes in isolation.

In the following, we fix sets of valid configurations
$\ValidFeat\subseteq\Total(\Feat)$ and effects $\Effects\subseteq\ValidFeat$.

§.§ Distributive Law Simplification

A rather natural explication for a set of causes $\cC\subseteq\Causes$ is to
represent $\cC$ as propositional logic formula, e.g.,
as the characteristic formula
$\chi(\cC)$ defined in disjunctive normal form (DNF)

\[
\chi(\cC) \en{=}
\bigvee_{\partial\in\cC} \big(
\bigwedge_{x\in\supp(\partial) \atop \partial(x)=\true} x \wedge
\bigwedge_{x\in\supp(\partial) \atop \partial(x)=\false} \neg x
\quad\big).
\]

Clearly, $\chi(\cC)$ has the same size as $\cC$ and its representation does not
exhibit any advantage compared to $\cC$.
Methods to minimize propositional logic formulas <cit.>
could be used to yield small formulas $\varphi$ covering the same configurations as $\cC$,
i.e., where $\Sem{\varphi}=\Sem{\cC}$.
While beneficial for related problems in configurable systems analysis, e.g., for
presence condition simplification <cit.>, such methods

vanish causal information, i.e., the set of causes $\cC$ cannot be reconstructed from
the reduced formula $\varphi$.

To provide a small formula that maintains the causal information
of $\cC$, we use a simple yet effective reduction method, which we call
distributive law simplification (DLS).
The basic idea is to factorize common feature selections in a DNF
formula step by step, exploiting the $n$-ary distributive law
$\Sem{\bigvee_{i=1}^n (\phi\wedge \psi_i)} = \Sem{\phi \wedge \bigvee_{i=1}^n\psi_i}$.
Each factorization leads to a length reduction of $(n-1)\cdot|\phi|$, where
$|\phi|$ is the length of the propositional formula factored out.
Obviously, these transformations are reversible, such that the original
DNF $\chi(\cC)$ and hence the set of causes $\cC$ can be reconstructed.
The final formula length depends on the formulas factored out, the subformulas,
and the factorization order. Determining a formula through DLS that has minimal size
is close to global optimization problems for propositional logic formulas and thus
computationally hard.

For practical applications, we hence employ a heuristics that reduces a given formula $\varphi$
in DNF by stepwise factoring out literals that have maximal number of occurrences
in DNF subformulas. We denote the reduced formula obtained by this heuristics by $\reduce(\varphi)$.

§.§ Cause–Effect Covers

The complete set of causes may contain several candidates to describe reasons for the effect
emerging in a single system variant.
If not interested in all causes but in a set of causes that covers
all effects (i.e., that contains, at least, one cause for every system variant)
we might ask for a preferably small covering set.
Formally, a cause–effect cover of $\Effects$ is a set $\cC\subseteq\Causes$
where $\Effects\subseteq\Sem{\cC}$. We say that such a cover $\cC$ is
minimal if there is no cause–effect cover $\cC'$ of $\Effects$
where $|\cC'|<|\cC|$.

For the email system in Example <ref> we directly see that $\{\gamma_{e\bar{c}}\}$
and $\{\gamma_a,\gamma_r\}$ are the only cause–effect covers of $\Effects$.

Thus, $\{\gamma_{e\bar{c}}\}$ is a minimal cause–effect cover of $\Effects$
as $|\{\gamma_a,\gamma_r\}|>|\{\gamma_{e\bar{c}}\}|$.

Determining minimal cause–effect covers is computationally hard for
the same reasons as for minimal prime–cover computation <cit.>.

Hence, for practical applicability, heuristics that lead to nearly
minimal cause–effect covers are of interest.

The binary relation $\unlhd\subseteq \Partial(\Feat)\times\Partial(\Feat)$,
where $\partial\unlhd\partial'$ stands for $\partial'$ to be at least as general as
$\partial$ w.r.t. $\Effects$, is defined by

\[
\partial\unlhd\partial'\en{ \text{iff} }\Sem{\partial}\cap\Effects \subseteq \Sem{\partial'}\cap\Effects.
\]

The set of most general causes $\mCauses$ comprises
those causes for $\Effects$ w.r.t. $\ValidFeat$ that are $\unlhd$-maximal in $\Causes$.

From the above definition, we directly establish an algorithm to compute
$\mCauses$ by computing $\unlhd$ on $\Causes$ in quadratic time and selecting
elements maximal w.r.t. $\unlhd$.
While $\mCauses$ already provides a cause–effect cover of $\Effects$,

there might be different most general causes that cover the same set of effect instances.
Towards nearly minimal cause–effect covers, we thus might pick one of those candidates
with minimal support to obtain an even further concise representation.

§.§ Responsibility and Blame

To measure the influence of causes on effects, Chockler and
Halpern <cit.> introduced degrees of responsibility and blame,
ranging from zero to one for “no” to “full” responsibility and blame, respectively.
Responsibility measures how relevant a single cause is for an effect in a specific context.
Blame denotes the expected overall responsibility according to a given
probability distribution on all contexts where the effect emerges.
We take inspiration from these measures and present corresponding notions
for feature causality. In short, the degree of responsibility is the maximal share
of features contributing to the effect, i.e., features that would have to be
reconfigured to provide a counterfactual witness.

We rephrase the majority example
by Chockler and Halpern <cit.> in our setting.
Consider eleven features whose configurations are all
valid. We are interested in responsibilities for the
effect that the majority of features is active.

If all eleven features are active, each feature has
a responsibility of $1/6$, since six features share the responsibility for the effect:
Besides the feature of interest, further five features have to be reconfigured
towards a majority of inactive features. In a configuration where six features are
active and five not, each of the six active ones is
fully responsible for the effect: If this feature would be reconfigured,
more features would be inactive than active.
We then assign responsibility of one to each of the six active features.

In what follows, we formalize degrees of responsibility and blame for single features
as in the example above. An extension of this notion to partial configurations
to explicate feature interactions is provided in Section <ref>.

Feature responsibility

Intuitively, the degree of responsibility of a single feature $x\in\Feat$ is defined as the maximal
share to contribute to causing the effect in an effect instance $\eta\in\Effects$.
In the case that $x$ does not appear in the support of any cause $\gamma$ covering $\eta$,

feature $x$ does not contribute
to causing the effect in $\eta$ and thus has no responsibility.
Otherwise, $x$ shares its responsibility with, at least, a minimal number of
other features, whose switch of its interpretation in $\eta$ would lead to a
counterfactual witness $\overline{\eta}$, i.e., $\overline{\eta}\in\CEffects$.
We formalize such switches in configurations by a function

\[
\switch\colon \power{\Feat} \times \Total(\Feat) \ra \Total(\Feat)
\]

where for any $Y\subseteq\Feat$ and $\total\in\Total(\Feat)$, we have
$\switch(Y,\total)(y)=\total(y)$ if $y\not\in Y$ and
$\switch(Y,\total)(y)=\neg\total(y)$ otherwise.

The degree of responsibility of a feature $x\in\Feat$
in the context $\eta\in\Effects$ for which there is $\gamma\in\Causes$ with
$\eta\in\Sem{\gamma}$ and $x\in\supp(\gamma)$ is defined as

\[
\resp(x,\eta) \en{=}
\frac{1}{
\min\left\{ |Y| : Y\subseteq\Feat, x\in Y, \switch(Y,\eta)\in\CEffects\right\}
\]

and as $\resp(x,\eta)=0$ otherwise.

Note that due to <ref> there exists at least one counterfactual witness
in the case $x$ appears in a cause covering $\eta$ and hence, the denominator of
the above fraction is finite and greater than zero.

Continuing the email example (see Example <ref>),
the mail feature $m$ and sign feature $s$ do not have any
responsibility for a long decipher time in any configuration as they do not
appear in any of the causes $\gamma_a$, $\gamma_r$, and $\gamma_{e\bar{c}}$.
Also the AES feature $a$ has no responsibility in configurations $mer$
or $mers$, since the only covering causes are $\gamma_{e\bar{c}}$
and $\gamma_r$, 	not containing $a$ in their support.
Besides the analogous case for the RSA feature $r$,

other degrees of responsibility are $1/2$:
switching a feature $x$ in $\eta$ usually requires one further
feature to switch towards a configuration of $\CEffects$.
For example, selecting the Caesar feature $c$ in $\eta=mea$
requires also to deselect the AES feature $a$, leading to $\overline{\eta}=mec\in\CEffects$.

Degrees of responsibility are locally defined w.r.t. a context, while one
is surely also interested in a global measure of responsibility of a feature
or partial configuration w.r.t. all possible contexts, i.e., effect configurations.
The degree of blame is defined as the expected degree of responsibility
on a probability distribution $\pi\colon \ValidFeat \ra [0,1]$
over valid configurations $\ValidFeat$, i.e., where $\sum_{\total\in\ValidFeat}\pi(\total) = 1$.

The degree of blame of a feature $x\in\Feat$ w.r.t. a distribution $\pi$
over $\ValidFeat$ is defined as

\[
\blame(x,\pi) \en{=}
\sum_{\eta\in\Effects} \pi(\eta)\cdot\resp(x,\eta).
\]

To illustrate the degree of blame, continue Example <ref>, where
we assume a uniform distribution $\pi$ over effect configurations, i.e.,
$\pi(\eta)= 1/|\Effects| =1/4$ for all $\eta\in\Effects$ and $0$ otherwise.
Then, $\blame(x,\pi) = 1/4\sum_{\eta\in\Effects} \resp(x,\eta)$
and thus, $\blame(x,\pi)$ is $1/2$ for $x\in\{e,c\}$,
$3/8$ for $x\in\{a,r\}$, and $0$ for $x\in\{m,s\}$.

On the choice of blame distributions
The distribution $\pi$ models the frequency of valid configurations to occur,
for which there are several scenarios that lead to a reasonable definition of $\pi$.
One natural distribution may model the frequency of users choosing a configuration
in the configurable system. But also the frequency of effect configurations is useful, e.g.,
to model the frequency a certain bug is reported by users when the effect corresponds to the
property of a malfunction. In the case such statistics
are not at hand or one is interested in the degree of blame from a developer's
perspective, uniform distributions over valid configurations or effects
are canonical candidates for $\pi$.

§.§ Feature Interactions

A notorious problem in configurable systems is the presence of (inadvertent)
feature interactions <cit.>, which describe
system behaviors that emerge due to a combination of multiple features
not easily deducible from the features' individual behaviors.
The detection, isolation, and resolution of feature interactions play a
central role in the development of configurable systems and beyond <cit.>.

We now show how our black-box causal analysis at the level of features
(see Section <ref>) can be used for the detection and isolation of
feature interactions. These can provide the basis for fine-grained, white-box
feature-interaction resolution as done by Garvin and Cohen <cit.>.

The first problem we address is to detect the necessity of feature
interactions for an effect to emerge.
Garvin and Cohen presented a formal definition of feature interaction faults
to capture faults in configurable systems that
necessarily arise from the interplay between multiple features <cit.>.

Notably, their characterization is also at the abstraction level
of features and relies on black-box testing of faults, similar to our perspective
on effects. We transfer their definition to our setting, but covering arbitrary effects
instead of faults only.
Recall that a partial configuration $\omega\in\Partial(\Feat)$ is sufficient
for $\Effects$ w.r.t. $\ValidFeat$ if $\varnothing\neq\Sem{\omega}\cap\ValidFeat\subseteq\Effects$
(see <ref>).

A partial configuration $\omega\in\Partial(\Feat)$ is a $t$-way interaction witness
for $\Effects$ w.r.t. $\ValidFeat$ if

$\omega$ sufficient for $\Effects$ w.r.t. $\ValidFeat$ with $|\supp(\omega)| =t$ and

there is no $\hat\omega$ sufficient for $\Effects$ w.r.t. $\ValidFeat$ with $|\supp(\hat\omega)| =t-1$.

Basically, there is a one-to-one correspondence between
interaction witnesses and feature causes with minimal support:

For any partial configuration $\gamma\in\Partial(\Feat)$ with $t=|\supp(\gamma)|$
we have that

(1)   if $\gamma$ is a $t$-way interaction witness for $\Effects$ w.r.t. $\ValidFeat$,
then $\gamma\in\Causes$, and

(2)   if $\gamma\in\Causes$ and there is no $\hat\gamma\in\Causes$ with
$|\supp(\hat\gamma)|{<}t$, then $\gamma$ is a $t$-way interaction witness
for $\Effects$ w.r.t. $\ValidFeat$.

To this end, Algorithm <ref>, in combination with
a projection to feature causes with minimal support, can be used to
decide whether the effect emerges necessarily from feature interactions:
A necessary feature interaction takes place in the case these minimal
feature causes all have a support involving, at least, two features.

Returning to Example <ref>, there are exactly two causes
that are both $1$-way interaction witnesses: $\gamma_a$ and $\gamma_r$.
The cause $\gamma_{e\bar{c}}$ does not witness a necessary $2$-way feature interaction
since although having support size of two, $\gamma_a$ and $\gamma_r$ have support size one
(cf. Theorem <ref>(2)).
Hence, the effect describing long decipher time is not
necessarily related to a feature interaction.

The second problem we address is to pinpoint features responsible for
feature interactions. For this, observe that
Definition <ref> is similar to Definition <ref>,
but with a different notion of minimality:
While <ref> ensures global minimality over all partial configurations,
<ref> ensures local minimality through expansions, taking
the individual selection of features into account.

To pinpoint those features that actually interact towards the effect,
feature causes can be interpreted as a form of interaction witnesses at the
local level instead of the global perspective taken for $t$-way interaction witnesses:

Switching some feature a cause does not ensure the effect to emerge anymore –
hence, the switched feature is necessary for the effect.
For instance, in Example <ref>, the interaction between
encryption and Caesar being disabled is witnessed by the
feature cause $\gamma_{e\bar{c}}$.
Feature causes thus also provide a criterion for feature interactions
at the operational level and can be used to guide a more in-depth
white-box feature interaction analysis, possibly reducing the naive
exponentially-sized feature-interaction search space.

Feature interaction responsibility and blame
Any subset of the supports of feature causes that contains more
than two features provides candidates for an actual interaction
between the features contained.
Since both, the number of feature causes and their expansions, can be
exponential in the number of features, feature interactions isolated
via a causal analysis might still be difficult to interpret by developers.
Based on the degree of responsibility for single features,
we now provide a variant to measure responsibility and blame of
feature interactions, where high values indicate strong relevance
of the interaction and low values weak relevance.

The degree of responsibility of a partial configuration $\partial\in\Partial(\Feat)$
in the context $\eta\in\Effects$ for which there is
$\gamma\in\Causes$ with $\eta\in\Sem{\gamma}$ and $\supp(\partial)\subseteq\supp(\gamma)$
and $\partial(x)=\gamma(x)$ for all $x\in\supp(\partial)$ is defined as

!$\displaystyle\resp(\partial,\eta) \en{=}
\frac{1}{
\min\left\{ |Y| : Y\subseteq\Feat, \supp(\partial)\cap Y\neq\varnothing,
\switch(Y,\eta)\in\CEffects\right\}

and as $\resp(\partial,\eta)=0$ otherwise.

Note that, for $\partial(x)=\eta(x)$ and $\supp(\partial)=\{x\}$,
Definition <ref> agrees with Definition <ref>.

The degree of responsibility is non-zero in the case of a single feature if the feature appears
in some cause, whereas the degree of feature interaction responsibility is non-zero
if some cause is an expansion of the potential feature interaction.
Feature interaction blame is defined as in Definition <ref> but
with replacing the single feature $x\in\Feat$ by the partial configuration $\partial\in\Partial(\Feat)$
standing for the potential feature interaction of interest.

Statistics of feature causality experiments
Statistics of feature causality experiments

Property   1lSystem   #   $|\ValidFeat|$   $|\Feat|$   1rTime   4cAverage size of

[type]   1c             1r[s]      $\Effects$     $\cC$     $m\cC$       DLS

3*$\varphi$   CFDP     10      $           56$      13        0.21          28        7.30         2.60     58%

$\!_1$     36      $          256$       9            0.09         128        0.58         0.58     26%

82      $          128$      11            0.29          64        1.77         0.91     43%
LinkedList     42      $          204$      19                      18.97         102       47.40         8.36     54%

21      $ 16\,777\,216$      25                       5.88          22       22.14        22.14     80%

PKJab    28      $           72$      12                0.42          36        8.43         4.86     72%

Prevaylar    42      $           24$       7            0.20          12        3.57         2.17     93%

SNW     42      $       3\,240$      36              2 751.32        1 620     2 110.31        18.90     37%

ZipMe $\!_1$     42      $          64$      9                      0.19         32        4.19         2.69     93%
Curl    28      $          768$      14                      83.07         384       96.75        67.39     59%

h264    28      $       1\,152$      17                    355.37         576      229.86        113.93     53%

SQLite     21      $  3\,932\,160$      40                 34 826.86     1 310 729     1 881.67       436.48     27%

WGet     28      $       5\,120$      17                     777.26        2 560      298.11       201.79     51%

Property   1lSystem   #   $|\ValidFeat|$   $|\Feat|$   1rTime   4cAverage size of

[type]   1c             1r[s]      $\Effects$     $\cC$     $m\cC$      DLS

28      $          192$      10                       2.85          96       28.79        22.96     69%

$\!_2$     28      $           10$       6                       0.14           5        3.21         2.25     80%

28      $           40$      10                       1.01          20       22.32         8.21     69%

h264    56      $       1\,152$      17                    32.24         576      68.98        22.71     51%

ZipMe $\!_2$    42      $          640$      16                      1.73         320        11.07         9.98     72%
BSN      4      $          298$      11         0.63         149       21.00         8.75     68%

VCL     22      $    2\,097\,152$      21        60 403.78     1 048 576     3 718.05      3 718.05     36%
36      $       2\,560$      19           5.71        1 280       13.03         4.28     72%

46      $       2\,304$      32        3 950.15        1 152      724.87        46.00     46%

30      $       1\,024$      12          16.21         512       53.57        53.57     55%

48      $          432$      20           5.71         216       13.85         1.90     69%

48      $       1\,152$      17           2.38         576        7.50         3.75     78%

We list for each type of effect property (functional LTL properties $\varphi$,
precision accuracy threshold properties $\varepsilon$,
and other threshold properties $\thresh$)
the considered subject systems, the numbers of experiments (#),
valid configurations ($|\ValidFeat|$), features ($|\Feat|$), and the overall time in seconds to
compute feature causes and most general causes.
The second part of the table lists the average sizes of the effect sets ($\Effects$), feature causes
($\cC=\Causes$), cause–effect covers by most general causes ($m\cC=\mCauses$), and
DLS formulas relative to the characteristic formula of causes

in percent).

§ EXPERIMENT SETUP

To evaluate our causal analysis and explication algorithms, we conducted
a number of experiments comprising many analyses on community benchmarks
and real-world examples from the area of configurable software systems.

§.§ Research Questions

Our evaluation is driven by four research questions that address the key issue of whether
and how the notion of feature causality facilitates identifying root causes, estimating
the effects of features, and detecting feature interactions in controlled and practical settings.

Can feature causes be effectively computed in real-world settings and
support the detection of reasons for different effects of interest?

Do DLS representation, cause–effect covers, and responsibility
and blame degrees provide concise causal explications?

Is feature causality beneficial for guiding the configuration of
systems under variability-aware constraints?

Can feature interactions and configuration-dependent anomalies
be detected and isolated based on feature causality?

§.§ Implementation

We implemented our algorithms to compute feature causes and explications in the prototypical
tool . Written in Python, our tool relies on the engines for logical expressions
and binary decision diagrams (BDDs) of , a library for electronic design
automation <cit.>.

The tool takes the sets of valid feature configurations $\ValidFeat$ and effects $\Effects$
as input.  supports different input formats for these sets,
e.g., by Boolean expressions in DNF or CNF.
Internally, sets of (partial) feature configurations are efficiently represented as
reduced ordered BDDs <cit.>.
In addition to their compact and hence space-efficient representation, we chose BDDs because they
provide an efficient method to check satisfiability (required, e.g., for Line <ref> in
Algorithm <ref>).
We first implemented a naive algorithm directly checking the conditions <ref> and <ref>,
but even for small examples, we easily ran into timeouts.
Hence, we devised Algorithm <ref>, which
uses prime implicants to efficiently determine feature causes (cf. Section <ref>).

To compute prime implicants, we used the tool  <cit.>, well known from
circuit optimization, through an interface that mediates between
our BDD representations and the DNF representations in 's PLA format.
This interface is also used to provide minimal and nearly minimal cause–effect covers through
and , respectively, which can then
be compared with our heuristic cause–effect cover by most general causes (see Section <ref>).
While it is well known that the length of DNFs can be exponential in the size of the BDD
representing the same Boolean function, generating DNFs from our BDD representations
did not face any significant blowup and required negligible time in all our experiments.
Besides the core tool, we have implemented several conversion scripts to generate valid
feature configuration sets from  <cit.> and effect sets from analysis results
returned by variability-aware analysis tools such as  <cit.> and
<cit.> (see also Section <ref>)
and the data sets from Siegmund et al. <cit.> and Kaltenecker et al. <cit.>.

§.§ Subject Systems

To answer our research questions, we selected a diverse set
of subject systems, ranging from popular community benchmarks
to more involved systems with non-functional properties and from
real-world settings (see Table <ref> for an overview).

From Cordy et al. <cit.>, we use , , and systems and
analyzed them against the accompanied LTL properties using the variability-aware
model checker . Furthermore, we took the  and
from von Rhein et al. <cit.> and analyzed multiple defects provided as propositional logic formula
generated by  <cit.>.

For quantitative properties, we generated effect sets
from configurable system analysis results as illustrated in Section <ref>
for three classes of systems. First, we considered configurable systems modeled
for the variability-aware probabilistic model checker  <cit.>,
comprising a body sensor network (BSN) model <cit.>
and a velocity control loop (VCL) model of an aircraft <cit.>.
In both systems, the reliability (R) of the system is analyzed in terms of the probability
of failure of sensors and control components, respectively. Second, we generated
effect sets from performance measurements of real-world configurable software systems that
have been used to evaluate performance modeling techniques <cit.>.
In particular, we selected five systems from different domains: a compiler framework (),
a database-system (), a compression tool (), a video encoder (), and a
toolbox for solving partial differential equations ().
For these systems, we chose thresholds on the runtime (T) of the system executions.
Third, we constructed effect sets for several systems from studies on performance prediction of non-functional properties <cit.>,
such as , , , and .
For these, we used the black-box approach by Siegmund et al. <cit.>,
which uses multivariable linear regression methods to generate variability-aware performance
models. Our thresholds for constructing effect sets are imposed on the prediction accuracy
of the following three different non-functional properties on those systems:
runtime (T), binary size (B), and memory footprint (M).

§.§ Operationalization

For  <ref>, we compute both sets $\Causes$ and $\CCauses$, i.e.,
the feature causes of the effect property and its negation.
Based on these feature causes, we further compute cause–effect covers $\mCauses$
and $\mCCauses$, distributive law simplification (DLS),
as well as responsibility and blame values for each single feature and cause to answer <ref>.
For blame computations, we assume a uniform distribution over all effects,
due to the absence of further statistical information and taking a
developers' perspective (cf. Section <ref>).
For <ref>, we compute single feature blames based on a uniform
effect distribution to measure the influence of individual features onto the effect.
We compute feature interaction blames on pairs of features to address <ref>,
again assuming a uniform effect distribution.

Table <ref> provides key statistics about our experiments, focusing
on model characteristics and the time to compute feature causes and most general
feature causes. All experiments were conducted on an AMD Ryzen 7 3800X 8-Core system
with 32GB of RAM running Debian 10 and Python 3.7.3.

§ RESULTS

We discuss our results w.r.t. the different kinds of causal explications
of Section <ref>. First, we discuss statistics on our experiments,

also quantitatively analyzing the potential of causal explications by
most general causes and DLS-reduced formulas.
Then, we address our research questions in more depth by means of three representative
subject systems. Here, we focus on properties not detectable by classical
causal white-box analysis methods <cit.>.

§.§ Descriptive Statistics (<ref> and <ref>)

The computability of feature causes is of major interest for our evaluation. Table <ref> provides
an overview of the subject systems for which we generated effect sets and applied our feature causality analysis.
We see that our algorithms compute feature causes in reasonable time, within a few seconds for most subject
systems. To create the effect sets, we considered several effect properties, as described in Section <ref>:
$\varphi$ stands for LTL properties;
$\varepsilon_B$, $\varepsilon_M$, and $\varepsilon_T$ for thresholds on the accuracy of a prediction
model for binary size, memory footprint, and runtime;
and $\thresh_R$ and $\thresh_T$ for
reliability and runtime  thresholds, respectively.
This variety of properties already illustrates
the wide range of applications and potential use of feature causality.

The sizes of valid configuration and effect sets crucially influence the time for
computing feature causes, which is as expected since the complexity of
Algorithm <ref> is dominated by the computation of prime implicants
of $\big(\Total(\Feat){\setminus}\ValidFeat\big)\cup\Effects$.
Since our implementation relies on BDDs for the representation of valid configuration
and effect sets, it is however well possible that within similar sizes,
computation times can significantly differ.
This is mainly due to the fact that BDD sizes highly depend on the specific nature of the
represented Boolean functions and the variable order chosen <cit.>.
For instance, while the experiments on DUNE
and BerkeleyDB (see Table <ref>) have similar sized sets $\ValidFeat$
and $\Effects$, their runtimes differ in two orders of magnitude.
We see that the number of most general feature causes is often way smaller than the
overall number of feature causes, which renders the creation of cause–effect covers
by most general causes sensible to support concise explications.
Interestingly, cause–effect covers by most general causes and minimization <cit.> yield the same results in almost all of our experiments,
which proves our heuristics to be effective.
In the same vein, the application of DLS

leads to great reductions of logical representations of feature causes, e.g.,
on average by almost 3/4 in the $\!_1$ subject system (see Table <ref>).

innertopmargin = 3pt,
innerleftmargin = 3pt,
innerrightmargin = 3pt]
For <ref> and <ref>, we conclude that feature causes
are computable in reasonable time. A substantial reduction of the set of feature causes
and cause–effect covers can be performed with
DLS formulas and most general feature causes, respectively.

– (most general) feature causes
Feature causes for minepump
Feature cause (characteristic formula)

§.§ Feature Cause Explications (<ref>)

We discuss the explications of feature causes that we have generated by the example of
the  system <cit.>, which is frequently used in the
configurable systems' analysis community.
This system models a water pump of a mine with $|\Feat| = 11$ features on which
requirements expressed in LTL are imposed (see Section <ref>).

An analysis of the stabilization property, formalizing that the
system eventually stabilizes (the pumps are eventually continuously on or off),
using  returned $|\Effects| =28$ configurations where the property holds
and $|\ValidFeat{\setminus}\Effects| =100$ configurations where it does not hold.

The direct interpretation of features responsible for this effect property is
difficult, as it requires to investigate the result of all $|\ValidFeat| = 128$
configurations. A causal analysis returned seven feature causes listed
with their degree of blame in Table <ref>. They already provide hints
which features are responsible for the property. Among the feature causes, three are most general,
highlighted in Table <ref>. They have the highest degree of partial configuration
blame while the most lengthy cause has the smallest degree. Our DLS
heuristics on most general causes yields

\[
\mathrm{High} \wedge \mathrm{Start} \wedge
(\mathrm{Stop} \vee \mathrm{Low} \vee \mathrm{MethaneAlarm})
\]

providing a concise representation of feature cause candidates
explicating the effect property.
That is, selecting features $\mathrm{High}$, $\mathrm{Start}$,
and one of the three features $\mathrm{Stop}$, $\mathrm{Low}$, or $\mathrm{MethaneAlarm}$
covers all causally relevant configurations for
the  system to stabilize.
On other subject systems, explications are also effective, but
with less drastic reductions than for the  example.

innertopmargin = 3pt,
innerleftmargin = 3pt,
innerrightmargin = 3pt]
Answering <ref>, feature causes are of reasonable size
compared to the complete analysis results, i.e., most general feature causes
and DLS provide concise explications for feature causes.
Responsibility and blame reflect the impact of feature causes.

Feature blame for the VCL redundancy system

1c.4cm$\thresh_R$ [$10^{-2}$]	    MFunc     1p2.5emSum1, Sum4     Memory     1p2.5emMOne, P, vCruise     SpentFuel, I     D     Prod     1p2.5emDragForce, EThrust     Integrator     Sum5     Sum3     Sum2     Acceleration
1.9     [rgb] .784,  .827,  .4270.63     [rgb] .439,  .678,  .2781.00     [rgb] .784,  .827,  .4270.63     [rgb] .439,  .678,  .2781.00     [rgb] .439,  .678,  .2781.00     [rgb] .439,  .678,  .2781.00     [rgb] .784,  .827,  .4270.63     [rgb] .439,  .678,  .2781.00     [rgb] .439,  .678,  .2781.00     [rgb] .439,  .678,  .2781.00     [rgb] .439,  .678,  .2781.00     [rgb] .439,  .678,  .2781.00     [rgb] .439,  .678,  .2781.00

2.0     [rgb] .714,  .796,  .3960.70     [rgb] .624,  .757,  .3570.80     [rgb] .647,  .769,  .3690.77     [rgb] .608,  .753,  .3530.82     [rgb] .494,  .702,  .3020.94     [rgb] .439,  .678,  .2781.00     [rgb] .714,  .796,  .3960.70     [rgb] .608,  .753,  .3530.82     [rgb] .439,  .678,  .2781.00     [rgb] .624,  .757,  .3570.80     [rgb] .624,  .757,  .3570.80     [rgb] .624,  .757,  .3570.80     [rgb] .439,  .678,  .2781.00

2.2     [rgb] .902,  .882,  .4780.49     [rgb] .851,  .859,  .4550.55     [rgb] .851,  .859,  .4550.55     [rgb] .796,  .835,  .4310.61     [rgb] .671,  .78,  .3760.75     [rgb] .49,  .702,  .3020.95     [rgb] .902,  .882,  .4780.49     [rgb] .796,  .835,  .4310.61     [rgb] .439,  .678,  .2781.00     [rgb] .851,  .859,  .4550.55     [rgb] .851,  .859,  .4550.55     [rgb] .851,  .859,  .4550.55     [rgb] .439,  .678,  .2781.00

2.5     [rgb] 1,  .941,  .6390.35     [rgb] 1,  .929,  .5450.38     [rgb] 1,  .937,  .6120.36     [rgb] .988,  .918,  .5140.40     [rgb] .937,  .894,  .4940.46     [rgb] .761,  .82,  .4160.65     [rgb] 1,  .941,  .6390.35     [rgb] .988,  .918,  .5140.40     [rgb] .443,  .682,  .2821.00     [rgb] 1,  .929,  .5450.38     [rgb] 1,  .929,  .5450.38     [rgb] 1,  .929,  .5450.38     [rgb] .439,  .678,  .2781.00

2.9     [rgb] 1,  .976,  .8550.28     [rgb] 1,  .973,  .8310.29     [rgb] 1,  .976,  .8390.28     [rgb] 1,  .969,  .8080.29     [rgb] 1,  .965,  .7650.31     [rgb] 1,  .949,  .6780.33     [rgb] 1,  .976,  .8550.28     [rgb] 1,  .969,  .8080.29     [rgb] .522,  .718,  .3140.91     [rgb] 1,  .973,  .8310.29     [rgb] 1,  .973,  .8310.29     [rgb] 1,  .973,  .8310.29     [rgb] .443,  .682,  .2821.00

3.4     [rgb] 1,  .976,  .8510.28     [rgb] 1,  .973,  .8160.29     [rgb] 1,  .969,  .7960.30     [rgb] 1,  .969,  .7880.30     [rgb] 1,  .957,  .7250.32     [rgb] 1,  .925,  .5330.38     [rgb] 1,  .976,  .8510.28     [rgb] 1,  .969,  .7880.30     [rgb] .835,  .851,  .4470.57     [rgb] 1,  .973,  .8160.29     [rgb] 1,  .965,  .780.30     [rgb] 1,  .965,  .780.30     [rgb] .467,  .69,  .290.97

4.0     [rgb] 1,  .988,  .9180.26     [rgb] 1,  .984,  .8940.27     [rgb] 1,  .984,  .890.27     [rgb] 1,  .98,  .8780.27     [rgb] 1,  .976,  .8510.28     [rgb] 1,  .965,  .7690.31     [rgb] 1,  .988,  .9180.26     [rgb] 1,  .98,  .8780.27     [rgb] 1,  .929,  .5650.37     [rgb] 1,  .984,  .8940.27     [rgb] 1,  .949,  .6670.34     [rgb] 1,  .949,  .6670.34     [rgb] .573,  .737,  .3370.86

4.7     [rgb] 1,  .996,  .9610.24     [rgb] 1,  .992,  .9530.25     [rgb] 1,  .992,  .9530.25     [rgb] 1,  .992,  .9490.25     [rgb] 1,  .992,  .9370.25     [rgb] 1,  .988,  .9060.26     [rgb] 1,  .996,  .9610.25     [rgb] 1,  .992,  .9490.25     [rgb] 1,  .965,  .780.30     [rgb] 1,  .992,  .9530.25     [rgb] 1,  .937,  .6040.36     [rgb] 1,  .937,  .60.36     [rgb] .639,  .765,  .3650.78

5.5     [rgb] 1,  1,  .980.24     [rgb] 1,  .996,  .9730.24     [rgb] 1,  .996,  .9730.24     [rgb] 1,  .996,  .9690.24     [rgb] 1,  .996,  .9570.25     [rgb] 1,  .988,  .9180.26     [rgb] 1,  .996,  .9610.24     [rgb] 1,  .992,  .9490.25     [rgb] 1,  .98,  .8670.27     [rgb] 1,  .988,  .9180.26     [rgb] 1,  .933,  .5730.37     [rgb] .992,  .922,  .5180.39     [rgb] .729,  .804,  .4040.68

6.4     0.23      0.23      0.23      [rgb] 1,  1,  .9920.23     [rgb] 1,  1,  .9880.24     [rgb] 1,  .996,  .9730.24     [rgb] 1,  .996,  .9650.24     [rgb] 1,  .992,  .9530.25     [rgb] 1,  .984,  .8820.27     [rgb] 1,  .98,  .8670.27     [rgb] 1,  .941,  .6270.35     [rgb] .976,  .914,  .510.41     [rgb] .792,  .831,  .4310.61

.38Feature interaction blame for

1c$\thresh_T$     2cGzip     4cLrzip     2cZpaq
2-3 (lr.75em)4-7 8-9
1c[$10^2$s]     $8$     $9$     $4$–$6$     $7$     $8$     $9$     $4$–$7$     $8$–$9$
2             0.002     0.009

3                                 [rgb] 1,  .996,  .9650.033     [rgb] 1,  .996,  .9650.033     [rgb] 1,  .996,  .9650.033     [rgb] 1,  .996,  .9650.033

4                                           [rgb] 1,  .98,  .8710.042     [rgb] 1,  .98,  .8710.042     [rgb] 1,  .98,  .8710.042

5                                           [rgb] 1,  .98,  .8710.042     [rgb] 1,  .98,  .8710.042     [rgb] 1,  .98,  .8710.042

6                       1-way               [rgb] 1,  .98,  .8710.042     [rgb] 1,  .98,  .8710.042     [rgb] 1,  .98,  .8710.042
7                       2-way               [rgb] 1,  .957,  .7140.056     [rgb] 1,  .957,  .7140.056     [rgb] 1,  .957,  .7140.056     [rgb] 1,  .957,  .7140.056     [rgb] 1,  .957,  .7140.056

8                                           [rgb] 1,  .957,  .7140.056     [rgb] 1,  .957,  .7140.056     [rgb] 1,  .957,  .7140.056     [rgb] 1,  .957,  .7140.056     [rgb] 1,  .957,  .7140.056

9                                           [rgb] 1,  .941,  .6350.063     [rgb] 1,  .941,  .6350.063               [rgb] 1,  .941,  .6350.063     [rgb] 1,  .941,  .6350.063

10                                          [rgb] 1,  .941,  .6350.063     [rgb] 1,  .941,  .6350.063               [rgb] 1,  .941,  .6350.063     [rgb] 1,  .941,  .6350.063

11                                                    [rgb] 1,  .925,  .5330.071               [rgb] 1,  .925,  .5330.071     [rgb] 1,  .925,  .5330.071

12                                                                        [rgb] .737,  .859,  .3920.083     [rgb] .737,  .859,  .3920.083

$\cdots$                                                                    [rgb] .737,  .859,  .392     [rgb] .737,  .859,  .392

22             		                                                      [rgb] .737,  .859,  .3920.083     [rgb] .737,  .859,  .3920.083

23                                                                                [rgb] .439,  .678,  .2780.250

§.§ Causality-guided Configuration (<ref>)

Feature blame provides a quantitative measure on the causal impact of feature selections
w.r.t. a set of configurations. This measure can be used to support configuration decisions,
e.g., by prioritizing features with high blame values in case the effect property is desirable.
We investigate such a causality-guided configuration on
the velocity control loop (VCL) subject system <cit.>.
The VCL models an aircraft velocity controller in  for which
its reliability in terms of probability of failure is of interest.

A common principle to increase the reliability of a system is by triple modular
redundancy (TMR) where system components are triplicated and their output are combined via
a majority vote. Dubslaff et al. <cit.> suggested to model and analyze systems
with such protection mechanisms using family-based methods from configurable systems'
analysis. To each component they assign a protection feature that specifies whether a
component is triplicated or not.
Comprising 21 components eligible for protection,
the VCL model has $|\ValidFeat| =2^{21}=2\,097\,152$ valid feature configurations.
Clearly, the highest reliability is achieved by protecting all components.
However, each protection comes at its costs in terms of execution time, energy costs, and
packaging size.

While it is known how to determine protection configurations with
optimal reliability–cost tradeoff <cit.>, reasons for why a protection configuration
is optimal or why a component was selected for protection are typically unclear.
We address this issue exploiting our causal analysis methods.
Using the variability-aware probabilistic model checking tool  <cit.>,
we generated effect sets $\Effects_{\rho<\thresh_R}$ w.r.t. $\rho$ mapping to
the probability of failure of the VCL within two
control-loop executions and reliability thresholds $\thresh_R$ between $0.019$ and
To ensure timely analysis results, real-world failure probability measures
were increased by a factor $100$ <cit.>.
Resulting higher values might seem unrealistic
but arguably do not affect the causal analysis measuring the
impact of protections.

Table <ref> shows the degree of feature blame for 18 protection features of
the 21 components of VCL

(cf. Section <ref>).
The three components not shown in the table are input components, having zero degree of
blame and hence do not contribute to the systems' reliability.

With the lowest threshold $\thresh_R=0.019$,
the effect set contains only 32 out of the $2^{21}$ feature configurations;
almost all protections of components are responsible for the low probability of failure.
Increasing the threshold lowers the degree of blame since the effect set increases,
leading to less counterfactual witnesses. Using our blame analysis,
we can directly deduce advice for engineers about components protections towards high
reliability: With tight reliability constraints, one should protect the “Acceleration”
component, followed by the “Integrator” component, as their blames are significantly
higher than for other components (cf. upper rows of Table <ref>).
When higher failure rates are acceptable, one should prefer to protect the components
“Sum2” and “Sum3” instead of the “Integrator” component due to their higher
impact on reliability (cf. lower rows of Table <ref>).

innertopmargin = 3pt,
innerleftmargin = 3pt,
innerrightmargin = 3pt]
For <ref>, we conclude that feature causes and degrees of blame
reveal and quantify the impact of features on the desired effect and, this way,
are able to guide the feature configuration process.

§.§ Feature Interactions (<ref>)

Causal reasoning provides a new angle to study feature interactions in configurable systems.

For illustration of how to detect and isolate feature interactions, we perform causal analysis on
the subject system, modeling a compression system for which
runtime characteristics of the compression algorithms are of interest.
Since the number of feature causes and their expansions can be both exponential
in the number of features, a direct evaluation of the runtimes and causal analysis
results is difficult. We hence investigate feature interactions through
their degrees of blame as described at the end of Section <ref>.

The subject effect sets $\Effects_{\rho>\thresh_T}$ depend on the runtime
$\rho\colon \ValidFeat \ra \Real$ in seconds for a configuration compressing a file
that is obtained as by Siegmund et al. <cit.>
and a runtime threshold $\thresh_T$ (see end of Section <ref>).
We then focus on $2$-way interactions by investigating potential feature interactions
between the compression algorithm and compression level responsible to have high runtimes.
For this we compute degrees of feature interaction blame for partial
configurations $\partial$ where
$\supp(\partial)\in \{\textit{Gzip}, \textit{Lrzip}, \textit{Zpaq}\}\times\{1,\ldots,9\}$ and
$\partial(x)=\true$ for each $x\in\supp(\partial)$.
In the columns of Table <ref>, we show the degrees of feature interaction blames
for thresholds $\thresh_T$ ranging from $\thresh_T=200s$ to $\thresh_T=2\,300s$.
Empty cells correspond to combinations of compression algorithm and level that
do not appear in any cause and thus have zero blame.
In these cases, we can conclude that no feature interaction takes place.

Higher blame values indicate that the combined responsibility of
the compression algorithm and level has a greater causal impact on runtime.
Notably, we observe that, with an increasing threshold, the
level of compression is increasingly responsible for longer runtime.

Certain compression algorithms always have runtimes above the
threshold independently of the compression level.
This leads to a configuration blame of zero at any compression level, e.g.,
thresholds $\thresh_T\leq 600s$ for the Zpaq algorithm shown in the upper right
of Table <ref>. Note that, in these cases, Zpaq serves as
$1$-way interaction witness according to Definition <ref>.
All greater thresholds for Lrzip and Zpaq do not have
$1$-way but $2$-way interaction witnesses. That is, being above the runtime threshold
is a result of a feature interaction between the compression algorithm and those compression
levels not showing zero blame.

Notice that the sums of the given feature interaction
blames for $\thresh_T \geq 700s$ that contain algorithms Lrzip or Zpaq
add up to $1/2$. That is, no other features are to be blamed for exceeding the runtime threshold.

Features have a dedicated meaning and one would hence expect higher runtimes
for higher compression levels. To this end, it seems odd that the feature interaction
of Lrzip and compression level 9 is less to blame for higher runtimes than for
levels 7 and 8.
This indicates an anomaly of the feature interaction between Lrzip and the
compression levels 7, 8, and 9. Further investigations on analysis results
and feature causes support these findings: averaged over all measurements of Lrzip
configurations, we observe runtimes of 1 064.9s at compression level 7 (standard deviation 4.1s),
1 181.7s at level 8 (standard deviation 3.2s), and only 830.5s at level 9
(standard deviation 2.6s). Hence, Lrzip at level 9 is not causally
relevant for exceeding the execution time threshold of 900s, as the compression level 9
feature is not contained in any cause with Lrzip. However, this insight is
difficult to obtain relying purely on the performance influence model given by $\rho$,
as this would require handcrafted analysis of all 432 analysis results (see Table <ref>).

innertopmargin = 3pt,
innerleftmargin = 3pt,
innerrightmargin = 3pt]
For <ref> we conclude that feature causes can provide hints for
feature interactions and anomalies arising from them.
Blame measures render themselves promising to quantify the influence of
feature interactions that contribute to certain effects.

§ DISCUSSION

In this section, we discuss potential threats to validity of our experiments
and relate our findings to existing work from the literature.

§.§ Threats to Validity

A threat to internal validity arises from the correctness of the analysis results
from which we generated the effect sets. While for functional properties this threat
is not crucial due to exact model-checking techniques used in our experiments,
for non-functional properties the results have been partly established using machine learning.
To mitigate this threat, we carefully chose effect-set thresholds such that the effect
sets remain stable also within small threshold variations.

Note that the choice of the effect set has no influence on the applicability of our causality
definitions but only on to what extent causality can serve as an explication.

For blame computations in our experiments, we assumed a uniform distribution over all effects,
taking a developers' perspective where frequencies on how often an
effect occurs in a real-world setting are not yet accessible.

Other distributions could change our quantitative results,
it is unlikely that they would alter our conclusions about causal influences of features
and feature interactions.

To increase the internal validity of our prototype,

we implemented and evaluated several methods to compute causes. These
include a naive brute-force approach and two additional methods to generate prime implicants,
independent from the tool .

Naturally, the choice of subject systems threatens external validity,
which includes the kinds of effect sets on which we evaluate causality.
To alleviate this threat, we included a wide variety of
systems with multiple properties from different areas to our evaluation.
They comprise several real-world software systems often
used to evaluate sampling strategies and performance-modeling approaches.
We further added several community benchmarks from the feature-oriented model-checking
community as well as a large-scale redundancy system from reliability engineering.

§.§ Related Work

Various techniques for software defect detection have been proposed in the
literature, ranging from testing <cit.>
and static code analysis <cit.> to model checking <cit.>.
These techniques have been also extended for analyzing configurable systems
to tackle huge configuration spaces <cit.>.
While such methods are able to identify defects and their location,
the challenge of finding root causes for defects remains.
A methodology to identify causes of defects during software development
is provided through root cause analysis <cit.>,
which can be supported by a multitude of techniques for causal reasoning <cit.>.
To the best of our knowledge, the foundations for a combination of configurable
systems analysis and causal reasoning as we presented in this paper have
not yet been addressed in the literature.
In the following, we discuss related work in the fields of configurable
systems analysis and causal reasoning.

Configurable systems analysis and explications
For analyzing configurable software systems, many approaches have been
presented in the last two decades <cit.>.
There is broad tool support for variability-aware testing and
sampling <cit.>,
static analysis <cit.>, and
model checking <cit.>.

There is a substantial corpus of work on determining those features in a configurable
system that are responsible for emerging effects <cit.>.
The focus has been mainly on detecting feature interactions <cit.>.
Siegmund et al. <cit.> and Kolesnikov et al. <cit.>
describe non-functional feature interactions as
interactions where the composed non-functional property diverges from the aggregation of the individual
contributions of the single features.
Garvin and Cohen <cit.> provided a formal definition of feature interaction faults

based on black-box analysis to guide white-box isolation of interaction faults.

An incremental software configuration approach to optimize non-functional properties
has been presented by Nair et al. <cit.>, which complements our causality-guided
software configuration we exemplified in Section <ref> based on
feature causality and precomputed analysis results.

To reduce the size of propositional logic formulas in configurable systems, von Rhein
et al. <cit.> proposed to exclude information about valid configurations
and use two-level logic minimization, e.g., by the  heuristics <cit.>.
Our DLS method differs from this approach by prioritizing causal information over reduction.

Causal reasoning
Algorithmic reasoning about actual causes following the structural-equation approach
by Halpern and Pearl <cit.> is computationally hard in
the general case <cit.>.
However, tractable instances such as the Boolean case
have been identified by Eiter and Lukasiewicz <cit.>.
For deciding whether a partial interpretation is an actual cause in the Boolean
case, Ibrahim and Pretschner presented an approach based on SAT solving <cit.>.
To compute all causes, their implementation relies on checking causality for all
possible partial interpretations, suffering from an additional exponential
blowup in the number of variables, which we avoid within our approach using prime
implicant computations.

Using test generation methods relying on program trace information,
program locations that are the origin of the defect can be
identified <cit.>.
Analyzing differences between program states of sampled failing and passing executions,
delta debugging identifies code positions relevant for an emerging failure <cit.>.
Similarly, causes for detects can be determined by analyzing counterexample traces <cit.>.

Faults can be also located by causal inference on graphs constructed from statement
and test coverage data <cit.>.

Iqbal et al. present a static technique to generate causal models of a given
configurable system using causal interference
and statistical counterfactual reasoning <cit.>.
This model is used to detect performance bugs and provide hints for their resolution.
While we focused on actual causality and rigorous analysis,
they are interested in type causality to answer more generic questions.

§ CONCLUDING REMARKS

Finding actual causes for an effect event becomes increasingly important in many
research areas, also driven by high demands from politics and society.
We introduced a formal definition and algorithms to identify causes
in configurable systems that relies on counterfactual reasoning
and connections to classical problems of propositional logics and circuit optimization.

We demonstrated their potential by analyzing several subject systems,
including real-world software systems and popular community benchmarks.
To enable explanations for causes and their impact onto effects,
we proposed explication techniques to concisely represent causes and
quantify the causal impact of features. We showed that our explications
are meaningful and can support the development of configurable software systems
by causality-guided configuration and isolating feature interactions.

With our prototypical implementation, we showed that our algorithms are
effective on real-world systems of varying sizes and run in reasonable time.

While already shown to be effective, our implementation could be enhanced by directly integrating
feature cause computations into optimized algorithms to compute prime implicants, e.g.,
relying on prime implicant computations at the level of BDDs <cit.>.
Combined with state-of-the-art BDD libraries such as CUDD <cit.>,
the computation of causes might become feasible for even larger systems than considered in this paper.

Another direction is by enhancing our analysis of feature interaction blames (see Theorem <ref>)
with in-depth white-box analyses <cit.> to pinpoint root causes in source code
for a great variety of effect properties using feature causality.

Further applications could be imagined for context-aware systems where feature-oriented
formalisms have been shown great applicability <cit.>.
Here, our causal framework could reason about contexts responsible for certain effects,
e.g., in self-adaptive systems <cit.>.

In this vein, dynamic configurable systems <cit.> are also
an interesting direction to be considered. In such systems,
features can be activated or deactivated during runtime, e.g., to model
upgrade and downgrade of systems. The detection and isolation of feature interactions
in dynamic configurable systems is a well-known challenge <cit.>.
It is a promising avenue of further work to extend our causal framework
to determine root causes and identify feature interactions in the dynamic setting <cit.>.

The authors are supported by the dfgDFGhttp://www.dfg.de
through the Collaborative Research Center
[https://perspicuous-computing.science]dfgTRR 248, the
exiniCluster of Excellence EXC 2050/1 (CeTI, project ID
390696704, as part of exiniGermany's Excellence Strategy),
project dfgAP 206/11-1,
and the Research Training Groups dfgQuantLA (GRK 1763) and
dfgRoSI (GRK 1907).

#1     #1#1#1     #1     #1     #1     #1#1          #1#1

[Abal, Melo, Stănciulescu, Brabrand,
Ribeiro, and WąsowskiAbal et al2018]
authorpersonIago Abal, personJean Melo,
personŞtefan Stănciulescu, personClaus
Brabrand, personMárcio Ribeiro, and
personAndrzej Wąsowski. year2018.
Variability Bugs in Highly Configurable Systems: A
Qualitative Analysis.
journalTransactions on Software Engineering and
Methodology  volume26, Article articleno10

[Aleksandrowicz, Chockler, Halpern, and
IvriiAleksandrowicz et al2017]
authorpersonGadi Aleksandrowicz, personHana
Chockler, personJoseph Y. Halpern, and
personAlexander Ivrii. year2017.
The Computational Complexity of Structure-Based
journalArtificial Intelligence Research
volume58 (year2017), pages431–451.

[Apel, Atlee, Baresi, and ZaveApel
et al2014]
authorpersonSven Apel, personJoanne M.
Atlee, personLuciano Baresi, and personPamela
Zave. year2014.
Feature Interactions: The Next Generation (Dagstuhl
Seminar 14281).
journalDagstuhl Reports  volume4
(year2014), pages1–24.

[Apel, Batory, Kästner, and SaakeApel
et al2013]
authorpersonSven Apel, personDon S. Batory,
personChristian Kästner, and personGunter
Saake. year2013.
booktitleFeature-Oriented Software Product Lines -
Concepts and Implementation.

[Apel, von Rhein, Wendler,
Größlinger, and BeyerApel et al2013]
authorpersonSven Apel, personAlexander
von Rhein, personPhilipp Wendler, personArmin
Größlinger, and personDirk Beyer.
Strategies for product-line verification: Case
studies and experiments. In booktitleProceedings of the
35th International Conference on Software Engineering (ICSE).
publisherIEEE, pages482–491.

[Aßmann, Baier, Dubslaff, Grzelak, Hanisch,
Hartono, Köpsell, Lin, and StrufeAßmann et al2021]
authorpersonUwe Aßmann, personChristel
Baier, personClemens Dubslaff, personDominik
Grzelak, personSimon Hanisch, personArdhi P P
Hartono, personStefan Köpsell, personTianfang
Lin, and personThorsten Strufe.
booktitleTactile computing: Essential building
blocks for the Tactile Internet.
publisherAcademic Press, Chapter 13,

[Baah, Podgurski, and HarroldBaah
et al2010]
authorpersonGeorge K. Baah, personAndy
Podgurski, and personMary Jean Harrold.
Causal Inference for Statistical Fault
Localization. In booktitleProceedings of the 19th
International Symposium on Software Testing and Analysis (ISSTA).
publisherACM, pages73–84.

[Baier, Dubslaff, Funke, Jantsch, Majumdar,
Piribauer, and ZiemekBaier et al2021]
authorpersonChristel Baier, personClemens
Dubslaff, personFlorian Funke, personSimon Jantsch,
personRupak Majumdar, personJakob Piribauer, and
personRobin Ziemek. year2021.
From Verification to Causality-Based Explications.
In booktitleProceedings of the 48th International Colloquium
on Automata, Languages, and Programming (ICALP),
Vol. volumeLIPIcs:198. publisherSchloss Dagstuhl –
Leibniz-Zentrum für Informatik, pages1–20.

[Baier and KatoenBaier and Katoen2008]
authorpersonChristel Baier and
personJoost-Pieter Katoen. year2008.
booktitlePrinciples of Model Checking.
publisherMIT Press.

[Beek, Damiani, Lienhardt, Mazzanti, and
PaoliniBeek et al2019]
authorpersonMaurice H. ter Beek,
personFerruccio Damiani, personMichael Lienhardt,
personFranco Mazzanti, and personLuca Paolini.
Static Analysis of Featured Transition Systems. In
booktitleProceedings of the 23rd Systems and Software
Product Line Conference (SPLC). publisherACM,

[Beer, Ben-David, Chockler, Orni, and
TreflerBeer et al2012]
authorpersonIlan Beer, personShoham
Ben-David, personHana Chockler, personAvigail
Orni, and personRichard J. Trefler.
Explaining counterexamples using causality.
journalFormal Methods in System Design
volume40 (year2012), pages20–40.

[Bodden, Tolêdo, Ribeiro, Brabrand,
Borba, and MeziniBodden et al2013]
authorpersonEric Bodden, personTársis
Tolêdo, personMárcio Ribeiro, personClaus
Brabrand, personPaulo Borba, and personMira
Mezini. year2013.
SPL\({}^{\mbox{LIFT}}\): statically analyzing
software product lines in minutes instead of years. In
booktitleProceedings of the 34th Conference on Programming
Language Design and Implementation (PLDI). publisherACM,

authorpersonRandal E. Bryant.
Graph-Based Algorithms for Boolean Function
journalTransactions on Computers
volume35 (year1986), pages677–691.

[Calder, Kolberg, Magill, and
Reiff-MarganiecCalder et al2003]
authorpersonMuffy Calder, personMario
Kolberg, personEvan H. Magill, and personStephan
Reiff-Marganiec. year2003.
Feature interaction: a critical review and
considered forecast.
journalComputer Networks  volume41
(year2003), pages115–141.

[Calder and MillerCalder and Miller2006]
authorpersonMuffy Calder and personAlice
Miller. year2006.
Feature interaction detection by pairwise analysis
of LTL properties—A case study.
journalFormal Methods in System Design
volume28 (year2006), pages213–261.

[Chandra and MarkowskyChandra and
authorpersonAshok K. Chandra and
personGeorge Markowsky. year1978.
On the number of prime implicants.
journalDiscrete Mathematics  volume24
(year1978), pages7–11.

[Chockler and HalpernChockler and
authorpersonHana Chockler and
personJoseph Y. Halpern. year2004.
Responsibility and Blame: A Structural-Model
journalArtificial Intelligence Research
volume22 (year2004), pages93–115.

[Chrszon, Baier, Dubslaff, and
KlüppelholzChrszon et al2020]
authorpersonPhilipp Chrszon, personChristel
Baier, personClemens Dubslaff, and personSascha
Klüppelholz. year2020.
From Features to Roles. In
booktitleProceedings of the 24th Systems and Software
Product Line Conference (SPLC). publisherACM, Article
articleno19, numpages11 pages.

[Chrszon, Dubslaff, Klüppelholz, and
BaierChrszon et al2018]
authorpersonPhilipp Chrszon, personClemens
Dubslaff, personSascha Klüppelholz, and
personChristel Baier. year2018.
ProFeat: feature-oriented engineering for
family-based probabilistic model checking.
journalFormal Aspects of Computing
volume30 (year2018), pages45–75.

[Clarke, Emerson, and SistlaClarke
et al1986]
authorpersonEdmund M. Clarke, personE. Allen
Emerson, and personAravinda P. Sistla.
Automatic verification of finite-state concurrent
systems using temporal logic specifications.
journalTransactions on Programming Languages and
Systems  volume8 (year1986),

[Classen, Boucher, and HeymansClassen
et al2011]
authorpersonAndreas Classen, personQuentin
Boucher, and personPatrick Heymans.
A Text-based Approach to Feature Modelling: Syntax
and Semantics of TVL.
journalScience of Computer Programming
volume76 (year2011), pages1130–1143.

[Classen, Cordy, Heymans, Legay, and
SchobbensClassen et al2012]
authorpersonAndreas Classen, personMaxime
Cordy, personPatrick Heymans, personAxel Legay,
and personPierre-Yves Schobbens.
Model checking software product lines with SNIP.
journalInternational Journal on Software Tools for
Technology Transfer  volume14 (year2012),

[Classen, Cordy, Schobbens, Heymans, Legay, and
RaskinClassen et al2013]
authorpersonAndreas Classen, personMaxime
Cordy, personPierre-Yves Schobbens, personPatrick
Heymans, personAxel Legay, and
personJean-François Raskin. year2013.
Featured Transition Systems: Foundations for
Verifying Variability-Intensive Systems and Their Application to LTL Model
journalTransactions on Software Engineering
volume39 (year2013), pages1069–1089.

[Cleve and ZellerCleve and Zeller2005]
authorpersonHolger Cleve and personAndreas
Zeller. year2005.
Locating causes of program failures. In
booktitleProceedings of the 27th International Conference on
Software Engineering (ICSE). publisherACM,

[Cordy, Classen, Heymans, Schobbens, and
LegayCordy et al2013]
authorpersonMaxime Cordy, personAndreas
Classen, personPatrick Heymans, personPierre-Yves
Schobbens, and personAxel Legay.
ProVeLines: a product line of verifiers for
software product lines. In booktitleProceedings of the 17th
Systems and Software Product Line Conference (SPLC).
publisherACM, pages141–146.

[Coudert and MadreCoudert and Madre1992]
authorpersonOlivier Coudert and
personJean Christophe Madre. year1992.
Implicit and Incremental Computation of Primes and
Essential Primes of Boolean Functions. In
booktitleProceedings of the 29th European Design Automation
Conference (EURO-DAC). publisherIEEE,

[Dorn, Apel, and SiegmundDorn
et al2020]
authorpersonJohannes Dorn, personSven Apel,
and personNorbert Siegmund. year2020.
Mastering Uncertainty in Performance Estimations of
Configurable Software Systems. In booktitleProceedings of
the 35th Conference on Automated Software Engineering (ASE).
publisherIEEE, pages684–696.

authorpersonChris Drake.
Pyeda: Data structures and algorithms for
electronic design automation. In booktitleProceedings of
the 14th Python in Science Conference (SciPy). pages26–31.

authorpersonClemens Dubslaff.
Compositional Feature-Oriented Systems. In
booktitleProceedings of the 17th Conference on Software
Engineering and Formal Methods (SEFM), Vol. volumeLNCS:12226.
publisherSpringer, pages162–180.

authorpersonClemens Dubslaff.
titleQuantitative Analysis of Configurable and
Reconfigurable Systems.
thesistypePh. D. Dissertation. schoolTU
Dresden, Institute for Theoretical Computer Science.

[Dubslaff, Baier, and
KlüppelholzDubslaff et al2015]
authorpersonClemens Dubslaff, personChristel
Baier, and personSascha Klüppelholz.
Probabilistic Model Checking for Feature-Oriented
journalTransactions on Aspect-Oriented Software
Development  volumeLNCS:8989 (year2015),

[Dubslaff, Ding, Morozov, Baier, and
JanschekDubslaff et al2019a]
authorpersonClemens Dubslaff, personKai
Ding, personAndrey Morozov, personChristel Baier,
and personKlaus Janschek. year2019a.
Breaking the Limits of Redundancy Systems
Analysis. In booktitleProceedings of the 29th European
Safety and Reliability Conference (ESREL). pages2317–2325.

[Dubslaff, Koopmann, and TurhanDubslaff
et al2019b]
authorpersonClemens Dubslaff, personPatrick
Koopmann, and personAnni-Yasmin Turhan.
Ontology-Mediated Probabilistic Model Checking. In
booktitleProceedings of the 15th Conference on integrated
Formal Methods (iFM), Vol. volumeLNCS:11918.
publisherSpringer, pages194–211.

[Dubslaff, Morozov, Baier, and
JanschekDubslaff et al2020a]
authorpersonClemens Dubslaff, personAndrey
Morozov, personChristel Baier, and personKlaus
Janschek. year2020a.
Iterative Variable Reordering: Taming Huge System
Families. In booktitleProceedings of the 4th Workshop on
Models for Formal Analysis of Real Systems (MARS),
Vol. volumeEPTCS:316. publisherOpen Publishing
Association, pages121–133.

[Dubslaff, Morozov, Baier, and
JanschekDubslaff et al2020b]
authorpersonClemens Dubslaff, personAndrey
Morozov, personChristel Baier, and personKlaus
Janschek. year2020b.
Reduction Methods on Error-Propagation Graphs for
Quantitative Systems Reliability Analysis. In
booktitleProceedings of the 30th European Safety and
Reliability Conference (ESREL) and 15th Probabilistic Safety Assessment and
Management Conference (PSAM).

[Dubslaff, Weis, Baier, and ApelDubslaff
et al2021]
authorpersonClemens Dubslaff,
personKallistos Weis, personChristel Baier, and
personSven Apel. year2021.
titleFeatCause – Github.

[Dubslaff, Weis, Baier, and ApelDubslaff
et al2022]
authorpersonClemens Dubslaff,
personKallistos Weis, personChristel Baier, and
personSven Apel. year2022.
booktitleFeatCause – Sources and Data.

authorpersonEllery Eells.
booktitleProbabilistic causality.
publisherCambridge University Press.

[Eiter and LukasiewiczEiter and
authorpersonThomas Eiter and personThomas
Lukasiewicz. year2002.
Complexity results for structure-based causality.
journalArtificial Intelligence
volume142 (year2002), pages53–89.

[Eiter and LukasiewiczEiter and
authorpersonThomas Eiter and personThomas
Lukasiewicz. year2006.
Causes and explanations in the structural-model
approach: Tractable cases.
journalArtifical Intelligence
volume170, number6-7 (year2006),

[Garvin and CohenGarvin and
authorpersonBrady J. Garvin and
personMyra B. Cohen. year2011.
Feature Interaction Faults Revisited: An
Exploratory Study. In booktitleProceedings of the 22nd
International Symposium on Software Reliability Engineering (ISSRE).
publisherACM, pages90–99.

[Gomaa and HusseinGomaa and Hussein2003]
authorpersonHassan Gomaa and personMohamed
Hussein. year2003.
Dynamic Software Reconfiguration in Software
Product Families. In booktitleProceedings of the 5th
Workshop on Software Profuct Family Engineering (PFE),
Vol. volumeLNCS:3014. pages435–444.

authorpersonIrving J. Good.
A theory of causality.
journalBritish Journal for the Philosophy of
Science  volume9 (year1959),

[Groce and VisserGroce and Visser2003]
authorpersonAlex Groce and personWillem
Visser. year2003.
What Went Wrong: Explaining Counterexamples. In
booktitleProceedings of the 10th Workshop on Model Checking
of Software, Vol. volumeLNCS:2648.
publisherSpringer, pages121–135.

[Guo, Yang, Siegmund, Apel, Sarkar, Valov,
Czarnecki, Wasowski, and YuGuo et al2018]
authorpersonJianmei Guo, personDingyu Yang,
personNorbert Siegmund, personSven Apel,
personAtrisha Sarkar, personPavel Valov,
personKrzysztof Czarnecki, personAndrzej Wasowski,
and personHuiqun Yu. year2018.
Data-Efficient Performance Learning for
Configurable Systems.
journalEmpirical Software Engineering
volume23 (year2018), pages1826–1867.

authorpersonJoseph Y. Halpern.
A Modification of the Halpern-Pearl Definition of
Causality. In booktitleProceedings of the 24th
International Joint Conference on Artificial Intelligence (IJCAI).
publisherAAAI, pages3022–3033.

[Halpern and PearlHalpern and Pearl2001a]
authorpersonJoseph Y. Halpern and
personJudea Pearl. year2001a.
Causes and Explanations: A Structural-Model
Approach - Part I: Causes. In booktitleProceedings of the
17th Conference in Uncertainty in Artificial Intelligence (UAI).
publisherMorgan Kaufmann, pages194–202.

[Halpern and PearlHalpern and Pearl2001b]
authorpersonJoseph Y. Halpern and
personJudea Pearl. year2001b.
Causes and Explanations: A Structural-Model
Approach - Part II: Explanations. In booktitleProceedings
of the 17th International Joint Conference on Artificial Intelligence
(IJCAI). publisherMorgan Kaufmann, pages27–34.

[Hemaspaandra and SchnoorHemaspaandra and
authorpersonEdith Hemaspaandra and
personHenning Schnoor. year2011.
Minimization for Generalized Boolean Formulas. In
booktitleProceedings of the 22nd International Joint
Conference on Artificial Intelligence (IJCAI).
publisherIJCAI/AAAI, pages566–571.

[Ibrahim and PretschnerIbrahim and
authorpersonAmjad Ibrahim and
personAlexander Pretschner. year2020.
From Checking to Inference: Actual Causality
Computations as Optimization Problems. In
booktitleProceedings of the 18th Symposium Automated
Technology for Verification and Analysis (ATVA),
Vol. volumeLNCS:12302. publisherSpringer,

[Iqbal, Krishna, Javidian, Ray, and
JamshidiIqbal et al2021]
authorpersonMd Shahriar Iqbal, personRahul
Krishna, personMohammad Ali Javidian, personBaishakhi
Ray, and personPooyan Jamshidi.
titleCADET: Debugging and Fixing Misconfigurations using
Counterfactual Reasoning.
[arxiv]2010.06061 [cs.SE]

[Johnson, Brun, and MeliouJohnson
et al2020]
authorpersonBrittany Johnson, personYuriy
Brun, and personAlexandra Meliou.
Causal Testing: Understanding Defects' Root
Causes. In booktitleProceedings of the 42nd International
Conference on Software Engineering (ICSE). publisherACM,

[Kaltenecker, Grebhahn, Siegmund, and
ApelKaltenecker et al2020]
authorpersonChristian Kaltenecker,
personAlexander Grebhahn, personNorbert Siegmund,
and personSven Apel. year2020.
The Interplay of Sampling and Machine Learning for
Software Performance Prediction.
journalSoftware  volume37
(year2020), pages58–66.

[Kaltenecker, Grebhahn, Siegmund, Guo,
and ApelKaltenecker et al2019]
authorpersonChristian Kaltenecker,
personAlexander Grebhahn, personNorbert Siegmund,
personJianmei Guo, and personSven Apel.
Distance-Based Sampling of Software Configuration
Spaces. In booktitleProceedings of the 41st International
Conference on Software Engineering (ICSE). publisherIEEE,

[Kang, Cohen, Hess, Novak, and PetersonKang
et al1990]
authorpersonKyo C. Kang, personSholom G.
Cohen, personJames A. Hess, personWilliam E. Novak,
and personA. Spencer Peterson.
booktitleFeature-Oriented Domain Analysis (FODA)
Feasibility Study.
typeTechnical Report.
institutionCarnegie-Mellon University Software Engineering

[Kolesnikov, Siegmund, Kästner, Grebhahn,
and ApelKolesnikov et al2019]
authorpersonSergiy S. Kolesnikov,
personNorbert Siegmund, personChristian
Kästner, personAlexander Grebhahn, and
personSven Apel. year2019.
Tradeoffs in modeling performance of highly
configurable software systems.
journalSoftware and Systems Modeling
volume18 (year2019), pages2265–2283.

[Kuhn, Wallace, and GalloKuhn
et al2004]
authorpersonD. Richard Kuhn,
personDolores R. Wallace, and personAlbert M.
Gallo. year2004.
Software fault interactions and implications for
software testing.
journalTransactions on Software Engineering
volume30 (year2004), pages418–421.

authorpersonDavid Lewis.
Counterfactual Theories of Causation.
journalJournal of Philosophy
(year1973), pages556–567.

[Liu and MeierLiu and Meier2009]
authorpersonYu Liu and personRené
Meier. year2009.
Resource-Aware Contracts for Addressing Feature
Interaction in Dynamic Adaptive Systems. In
booktitleProceedings of the 5th International Conference on
Autonomic and Autonomous Systems (ICAS). publisherIEEE,

[Mauro, Nieke, Seidl, and YuMauro
et al2016]
authorpersonJacopo Mauro, personMichael
Nieke, personChristoph Seidl, and
personIngrid Chieh Yu. year2016.
Context Aware Reconfiguration in Software Product
Lines. In booktitleProceedings of the 10th Workshop on
Variability Modelling of Software-intensive Systems (VaMoS).
publisherACM, pages41–48.

[McCluskey Jr.McCluskey Jr.1956]
authorpersonEdward J. McCluskey Jr.
Minimization of Boolean Functions.
journalBell System Technical Journal
volume35 (year1956), pages1417–1444.

[McGeer, Sanghavi, Brayton, and
VincentelliMcGeer et al1993]
authorpersonPatrick McGeer, personJagesh
Sanghavi, personRobert Brayton, and
personAlberto Sangiovanni Vincentelli.
Espresso-Signature: A New Exact Minimizer for Logic
Functions. In booktitleProceedings of the 30th Design
Automation Conference (DAC). publisherACM,

authorpersonGlenford J. Myers.
booktitleThe art of software testing.

[Nair, Yu, Menzies, Siegmund, and ApelNair
et al2020]
authorpersonVivek Nair, personZhe Yu,
personTim Menzies, personNorbert Siegmund, and
personSven Apel. year2020.
Finding Faster Configurations Using FLASH.
journalTransactions on Software Engineering
volume46 (year2020), pages794–811.

[Nielson, Nielson, and HankinNielson
et al2010]
authorpersonFlemming Nielson, personHanne R.
Nielson, and personChris Hankin.
booktitlePrinciples of Program Analysis.

authorpersonWolfgang J. Paul.
Boolesche Minimalpolynome und
journalActa Informatica  volume4
(year1975), pages321–336.

authorpersonJudea Pearl.
booktitleCausality: Models, Reasoning and Inference
(edition2nd ed.).
publisherCambridge University Press.

[Peters, Janzing, and SchölkopfPeters
et al2017]
authorpersonJ. Peters, personD. Janzing,
and personB. Schölkopf. year2017.
booktitleElements of Causal Inference: Foundations
and Learning Algorithms.
publisherMIT Press.

[Plath and RyanPlath and Ryan2001]
authorpersonMalte Plath and personMark
Ryan. year2001.
Feature integration using a feature construct.
journalScience of Computer Programming
volume41 (year2001), pages53–84.

authorpersonAmir Pnueli.
The Temporal Logic of Programs. In
booktitleProceedings of the 18th Symposium on Foundations of
Computer Science (SFCS). publisherIEEE,

[Post and SinzPost and Sinz2008]
authorpersonH. Post and personC. Sinz.
Configuration Lifting: Verification Meets Software
Configuration. In booktitleProceedings of the 23rd
Conference on Automated Software Engineering (ASE).
publisherIEEE, pages347–350.

[Qu, Cohen, and RothermelQu
et al2008]
authorpersonXiao Qu, personMyra B. Cohen,
and personGregg Rothermel. year2008.
Configuration-Aware Regression Testing: An
Empirical Study of Sampling and Prioritization. In
booktitleProceedings of the 17th International Symposium on
Software Testing and Analysis (ISSTA). publisherACM,

[Rhein, Liebig, Janker, Kästner, and
ApelRhein et al2018]
authorpersonAlexander Von Rhein,
personJörg Liebig, personAndreas Janker,
personChristian Kästner, and personSven Apel.
Variability-Aware Static Analysis at Scale: An
Empirical Study.
journalTransactions on Software Engineering and
Methodology  volume27, Article articleno18

[Risk and DivisionRisk and Division1999]
authorpersonABS Group Inc. Risk and
personReliability Division. year1999.
booktitleRoot Cause Analysis Handbook: A Guide to
Effective Incident Investigation.
publisherGovernment Institutes.

[Rodrigues, Alves, Nunes, Lanna, Cordy,
Schobbens, Sharifloo, and LegayRodrigues et al2015]
authorpersonGenaína Nunes Rodrigues,
personVander Alves, personVinicius Nunes,
personAndré Lanna, personMaxime Cordy,
personPierre-Yves Schobbens, personAmir Molzam
Sharifloo, and personAxel Legay.
Modeling and Verification for Probabilistic
Properties in Software Product Lines. In
booktitleProceedings of the 16th Symposium on High Assurance
Systems Engineering (HASE). publisherIEEE,

[Rooney and HeuvelRooney and Heuvel2004]
authorpersonJames J Rooney and personLee
N. Vanden Heuvel. year2004.
Root Cause Analysis For Beginners.
journalQuality Progress  volume37
(year2004), pages45.

[Rößler, Fraser, Zeller, and
OrsoRößler et al2012]
authorpersonJeremias Rößler,
personGordon Fraser, personAndreas Zeller, and
personAlessandro Orso. year2012.
Isolating Failure Causes through Test Case
Generation. In booktitleProceedings of the 2012
International Symposium on Software Testing and Analysis (ISSTA).
publisherACM, pages309–319.

[Siegmund, Grebhahn, Apel, and
KästnerSiegmund et al2015]
authorpersonNorbert Siegmund,
personAlexander Grebhahn, personSven Apel, and
personChristian Kästner. year2015.
Performance-Influence Models for Highly
Configurable Systems. In booktitleProceedings of the 10th
Joint Meeting on Foundations of Software Engineering (ESEC/FSE).
publisherACM, pages284–294.

[Siegmund, Kolesnikov, Kästner,
Apel, Batory, Rosenmüller, and SaakeSiegmund
et al2012]
authorpersonNorbert Siegmund,
personSergiy S. Kolesnikov, personChristian
Kästner, personSven Apel, personDon
Batory, personMarko Rosenmüller, and
personGunter Saake. year2012.
Predicting performance via automated
feature-interaction detection. In booktitleProceedings of
the 34th International Conference on Software Engineering (ICSE).
publisherIEEE, pages167–177.

[Siegmund, Rosenmüller, Kästner,
Giarrusso, Apel, and KolesnikovSiegmund et al2013a]
authorpersonNorbert Siegmund, personMarko
Rosenmüller, personChristian Kästner,
personPaolo G. Giarrusso, personSven Apel, and
personSergiy S. Kolesnikov. year2013a.
Scalable prediction of non-functional properties in
software product lines: Footprint and memory consumption.
journalInformation and Software Technology
volume55 (year2013), pages491–507.
Special Issue on Software Reuse and Product Lines.

[Siegmund, Rosenmüller, Kuhlemann,
Kästner, Apel, and SaakeSiegmund et al2012]
authorpersonNorbert Siegmund, personMarko
Rosenmüller, personMartin Kuhlemann,
personChristian Kästner, personSven Apel, and
personGunter Saake. year2012.
SPL Conqueror: Toward Optimization of
Non-Functional Properties in Software Product Lines.
journalSoftware Quality Journal
volume20 (year2012), pages487–517.

[Siegmund, Sven, and ApelSiegmund
et al2013b]
authorpersonNorbert Siegmund,
personAlexander von Rhein Sven, and personApel.
Family-based Performance Measurement.
journalSIGPLAN Notices volume49,
number3 (year2013), pages95–104.

authorpersonFabio Somenzi.
titleCUDD 3.0.0.

<http://vlsi.colorado.edu/ fabio/CUDD/html/>

authorpersonTadeusz Strzemecki.
Polynomial-time algorithms for generation of prime
journalJournal of Complexity  volume8
(year1992), pages37–63.

[ter Beek, Legay, Lluch Lafuente, and
Vandinter Beek et al2016]
authorpersonMaurice H. ter Beek, personAxel
Legay, personAlberto Lluch Lafuente, and
personAndrea Vandin. year2016.
Statistical Model Checking for Product Lines. In
booktitleProceedings of the 7th Symposium on Leveraging
Applications of Formal Methods (ISoLA), Vol. volumeLNCS:9952.
publisherSpringer, pages114–133.

[Thüm, Apel, Kästner, Schaefer, and
SaakeThüm et al2014]
authorpersonThomas Thüm, personSven
Apel, personChristian Kästner, personIna
Schaefer, and personGunter Saake.
A Classification and Survey of Analysis Strategies
for Software Product Lines.
journalComputing Surveys  volume47
(year2014), pages6:1–6:45.

[Vandin, ter Beek, Legay, and
Lluch LafuenteVandin et al2018]
authorpersonAndrea Vandin, personMaurice H.
ter Beek, personAxel Legay, and personAlberto
Lluch Lafuente. year2018.
QFLan: A Tool for the Quantitative Analysis of
Highly Reconfigurable Systems. In booktitleProceedings on
the 22nd Symposium on Formal Methods (FM),
Vol. volumeLNCS:10951. publisherSpringer,

[Velez, Jamshidi, Sattler, Siegmund, Apel, and
KästnerVelez et al2020]
authorpersonMiguel Velez, personPooyan
Jamshidi, personFlorian Sattler, personNorbert
Siegmund, personSven Apel, and personChristian
Kästner. year2020.
ConfigCrusher: Towards White-Box Performance
Analysis for Configurable Systems.
journalAutomated Software Engineering
volume27 (year2020), pages265–300.

[Velez, Jamshidi, Siegmund, Apel, and
KästnerVelez et al2021]
authorpersonMiguel Velez, personPooyan
Jamshidi, personNorbert Siegmund, personSven Apel,
and personChristian Kästner.
White-Box Analysis over Machine Learning: Modeling
Performance of Configurable Systems. In
booktitleProceedings of the 43rd International Conference on
Software Engineering (ICSE). publisherIEEE.

[von Rhein, Grebhahn, Apel, Siegmund, Beyer,
and Bergervon Rhein et al2015]
authorpersonAlexander von Rhein,
personAlexander Grebhahn, personSven Apel,
personNorbert Siegmund, personDirk Beyer, and
personThorsten Berger. year2015.
Presence-Condition Simplification in Highly
Configurable Systems. In booktitleProceedings of the 37th
International Conference on Software Engineering (ICSE).
publisherIEEE, pages178–188.

[Wachter, Mittelstadt, and RussellWachter
et al2017]
authorpersonSandra Wachter, personBrent D.
Mittelstadt, and personChris Russell.
Counterfactual Explanations without Opening the
Black Box: Automated Decisions and the GDPR.
journalHarvard Journal of Law and Technology
volume31 (year2017), pages841–887.

[Weber, Apel, and SiegmundWeber
et al2021]
authorpersonMax Weber, personSven Apel,
and personNorbert Siegmund. year2021.
White-Box Performance-Influence Models: A Profiling
and Learning Approach. In booktitleProceedings of the 43rd
International Conference on Software Engineering (ICSE).

authorpersonJon Williamson.
Probabilistic Theories of Causation.
journalThe Oxford Handbook of Causation
(year2009), pages185–212.

[Yilmaz, Cohen, and PorterYilmaz
et al2006]
authorpersonCemal Yilmaz, personMyra B.
Cohen, and personAdam A. Porter.
Covering arrays for efficient fault
characterization in complex configuration spaces.
journalTransactions on Software Engineering
volume32 (year2006), pages20–34.

authorpersonPamela Zave.
Feature-Oriented Description, Formal Methods, and
DFC. In booktitleProceedings of the Workshop on Language
Constructs for Describing Features. publisherSpringer,

authorpersonAndreas Zeller.
Isolating Cause-Effect Chains from Computer
Programs. In booktitleProceedings of the 10th Symposium on
Foundations of Software Engineering (FSE). publisherACM,

[Zhang, Guo, Blais, and CzarneckiZhang
et al2015]
authorpersonYi Zhang, personJianmei Guo,
personEric Blais, and personKrzysztof Czarnecki.
Performance Prediction of Configurable Software
Systems by Fourier Learning (T). In booktitleProceedings of
the 30th Conference on Automated Software Engineering (ASE).
publisherIEEE, pages365–373.