Ruben Heradio

Jose Manuel Sanchez, Miguel Angel Olivero, Ruben Heradio et al.

Feature models are widely used to capture the configuration space of software systems. Although automated reasoning has been studied for detecting problematic features and supporting configuration tasks, significantly less attention has been given to the systematic study of the structural properties of feature models at scale. The approach fills this gap by examining the models' structure through a network analysis perspective. We focus on three Research Questions concerning (i) the structural patterns exhibited by these graphs, (ii) the extent to which such patterns vary across domains and model sources, and (iii) the usefulness of network-based indicators for understanding, maintaining, and evolving variability models. To answer these questions, we analyze a dataset of 5,709 models from 20 repositories, spanning multiple application domains and varying sizes (ranging from 99 to 35,907 variables on their Boolean translation). To do so, graphs of transitive dependencies and conflicts between features are computed. Our results reveal consistent structural traits (e.g., the predominance of dependency relations, the presence of highly central features, or characteristic node degree distributions) as well as notable domain-specific deviations. These findings ease the identification of maintenance-relevant features, opportunities for modular decomposition, and indicators of structural fragility. This approach provides a scalable, graph-based foundation for the empirical analysis of variability models and contributes quantitative evidence to support future research on their structure and evolution.

Luis Cambelo, Ruben Heradio, Jose-Miguel Horcas et al.

The backbone of a Boolean formula is the set of literals that must be true in every assignment that satisfies the formula. This concept is fundamental to key operations on variability models, including propagating user configuration decisions to identify implied feature selections, detecting dead features and dead code blocks, and preprocessing formulas to accelerate knowledge compilation into tractable representations such as binary decision diagrams. Despite its importance, previous empirical studies have evaluated backbone algorithms solely on SAT competition formulas (typically engineered to test the limits of SAT solvers), leading to inconsistent conclusions about their performance. This study provides the first comprehensive evaluation of formulas derived from real-world variability models, analyzing 21 configurations of 5 state-of-the-art algorithms on 2,371 formulas from configurable systems ranging from 100 variables and 179 clauses to 186,059 variables and 527,240 clauses. The results indicate that variability model formulas are structurally distinct, with higher clause density but greater clause simplicity. Our research provides clear algorithm selection guidelines: Algorithm 2/3 (iterative with solution filtering) is recommended for formulas with 1,000 or fewer variables, while Algorithm 5 (chunked core-based) with adaptive chunk size selection provides the best practical performance for larger formulas. Also, the results show that filtering heuristics have negligible or negative effects on performance for variability models. Finally, the study identifies a research gap: while Algorithm 5 with optimal chunk size can achieve runtime reductions exceeding 50\% compared to Algorithm 2/3 (the one that product line tools implement), the optimal chunk size varies unpredictably across formulas and cannot currently be estimated, opening directions for future research.