Today, the operating system Linux is widely used in diverse environments, as its kernel can be configured flexibly. In many configurable systems, managing such variability can be facilitated in all development phases with product-line analyses. These analyses often require knowledge about the system’s features and their dependencies, which are documented in a feature model. Despite their potential, product-line analyses are rarely applied to the Linux kernel in practice, as its feature model still challenges scalability and accuracy of analyses. Unfortunately, these challenges also severely limit our knowledge about two fundamental metrics of the kernel’s configurability, namely its number of features and configurations. We identify four key limitations in the literature related to the scalability, accuracy, and influence factors of these metrics, and, by extension, other product-line analyses: (1) Analysis results for the Linux kernel are not comparable, because relevant information is not reported; (2) there is no consensus on how to define features in Linux, which leads to flawed analysis results; (3) only few versions of the Linux kernel have ever been analyzed, none of which are recent; and (4) the kernel is perceived as complex, although we lack empirical evidence that supports this claim. In this article, we address these limitations with a comprehensive, empirical study of the Linux kernel’s configurability, which spans its feature model’s entire history from 2002 to 2024. We address the above limitations as follows: (1) We characterize parameters that are relevant when reporting analysis results; (2) we propose and evaluate a novel definition of features in Linux as a standardization effort; (3) we contribute torte , a tool that analyzes arbitrary versions of the Linux kernel’s feature model; and (4) we investigate the current and possible future configurability of the kernel on more than 3,000 feature-model versions. Based on our results, we highlight 11 major insights into the Linux kernel’s configurability and make 7 actionable recommendations for researchers and practitioners.

This is the RCR report accompanying our TOSEM’25 paper How Configurable Is the Linux Kernel? Analyzing Two Decades of Feature-Model History . In this report, we bundle all data relevant to our paper for the purpose of reproducibility and long-term archival. This includes the feature-model extraction tool torte , as well as a comprehensive feature-model dataset and experimental results.

Configurable systems typically consist of reusable assets that have dependencies between each other. To specify such dependencies, feature models are commonly used. As feature models in practice are often complex, automated reasoning is typically employed to analyze the dependencies. Here, the de facto standard is translating the feature model to conjunctive normal form (CNF) to enable employing off-the-shelf tools, such as SAT or #SAT solvers. However, modern feature-modeling dialects often contain constructs, such as cardinality constraints, that are ill-suited for conversion to CNF. This mismatch between the input of reasoning engines and the available feature-modeling dialects limits the applicability of the more expressive constructs. In this work, we shorten this gap between expressive constructs and scalable automated reasoning. Our contribution is twofold: First, we provide a pseudo-Boolean encoding for feature models, which facilitates smaller representations of commonly employed constructs compared to Boolean encoding. Second, we propose a novel method to compile pseudo-Boolean formulas to Boolean d- DNNFs. With the compiled d-DNNFs, we can resort to a plethora of efficient analyses already used in feature modeling. Our empirical evaluation shows that our proposal substantially outperforms the state-of-the-art based on CNF inputs for expressive constructs. For every considered dataset representing different feature models and feature-modeling constructs, the feature models can be significantly faster translated to pseudo-Boolean than to CNF. Overall, deriving d-DNNFs from a feature model with the targeted expressive constraints can be substantially accelerated using our pseudo-Boolean approach. For instance, the Boolean approach only scales for group cardinalities with up-to 13 features while pseudo-Boolean d-DNNF compilation can compile cardinalities with thousands of features. Furthermore, our approach is competitive on feature models with only basic constructs.

Software is typically configurable by means of compile-time or runtime variability. As testing every valid configuration is infeasible, T-Wise sampling has been proposed to systematically derive a relevant subset of the configurations for testing to cover interactions among t features. Practitioners started to apply T-Wise sampling algorithms, but can often only test samples partially due to restricted resources and compare those partial samples based on their T-Wise coverage. However, there is no consensus in the literature on how to compute the T-Wise coverage in the literature. We propose the first systematic framework to define coverage metrics for T-Wise feature interactions. These metrics differ in the features and feature interactions being considered. We found evidence for at least six different metrics in the literature. In an empirical evaluation, we show that for a partial sample the coverage differs up to 21 % and for some metrics only half of the feature interactions need to be covered. As a long-term impact, our work may help to improve the efficiency and effectiveness of both, T-Wise sampling and coverage computations.

Configurable software systems, such as software product lines, enable the generation of products based on configurations tailored to specific requirements by combining reusable features. A key challenge in product lines lies in combinatorial interaction testing, which ensures that all possible feature combinations are tested to identify configurations that may fail. When a configuration fails, pinpointing the feature or the feature interaction causing the fault is crucial. However, fault masking - where faulty interactions remain undetected because other features or interactions could override their effects - potentially hinders the effective identification of faults in product lines. Despite the potential of missing critical interaction faults, fault masking in product lines has received limited attention in existing research. To address this gap, we investigate and analyze on already identified faults of the real-world product line JHipster and quantitatively analyze these faults in terms of masking. In our case study, we find evidence of the existence of fault masking in JHipster and how the detectability of masked faults is influenced. For one feature-interaction fault in JHipster, we miss to identify 17.6% of all configurations containing this fault due to masking effects. By analyzing masked faults of a real-world product line, we raise awareness of investigating feature-interaction masking further in software product lines.

Modern software systems are typically configurable, a fundamental prerequisite for wide applicability and reusability. This flexibility poses an extraordinary challenge for quality assurance, as the enormous number of possible configurations makes it impractical to test each of them separately. This is where t-wise interaction sampling can be used to systematically cover the configuration space and detect unknown feature interactions. Over the last two decades, numerous algorithms for computing small interaction samples have been studied, providing improvements for a range of heuristic results; nevertheless, it has remained unclear how much these results can still be improved. We present a significant breakthrough: a fundamental framework, based on the mathematical principle of duality , for combining near-optimal solutions with provable lower bounds on the required sample size. This implies that we no longer need to work on heuristics with marginal or no improvement, but can certify the solution quality by establishing a limit on the remaining gap; in many cases, we can even prove optimality of achieved solutions. This theoretical contribution also provides extensive practical improvements: Our algorithm SampLNS was tested on 47 small- and medium-sized configurable systems from the existing literature. SampLNS can reliably find samples of smaller size than previous methods in \(85\%\) of the cases; moreover, we can achieve and prove optimality of solutions for \(63\%\) of all instances. This makes it possible to avoid cumbersome efforts of minimizing samples by researchers as well as practitioners, and substantially save testing resources for most configurable systems.

Validating a configurable software system is challenging, as there are potentially millions of configurations, which makes testing each configuration individually infeasible. Thus, existing sampling algorithms allow to compute a representative subset of configurations, called sample, that can be tested instead. However, sampling on the set of configurations may miss potential error sources on implementation level. In this paper, we present solution-space sampling, a concept that mitigates this problem by allowing to sample directly on the implementation level. We apply solution-space sampling to six real-word, automotive product lines and show that it produces up to 56 % smaller samples, while also covering all potential error sources missed by problem-space sampling.

Feature modeling is widely used to systematically model features of variant-rich software systems and their dependencies. By translating feature models into propositional formulas and analyzing them with solvers, a wide range of automated analyses across all phases of the software development process become possible. Most solvers only accept formulas in conjunctive normal form (CNF), so an additional transformation of feature models is often necessary. However, it is unclear whether this transformation has a noticeable impact on analyses. In this paper, we compare three transformations (i.e., distributive, Tseitin, and Plaisted-Greenbaum) for bringing feature-model formulas into CNF. We analyze which transformation can be used to correctly perform feature-model analyses and evaluate three CNF transformation tools (i.e., FeatureIDE, KConfigReader, and Z3) on a corpus of 22 real-world feature models. Our empirical evaluation illustrates that some CNF transformations do not scale to complex feature models or even lead to wrong results for model-counting analyses. Further, the choice of the CNF transformation can substantially influence the performance of subsequent analyses.

Abstract Feature models are a helpful means to document, manage, maintain, and configure the variability of a software system, and thus are a core artifact in software product-line engineering. Due to the various purposes of feature models, they can be a cross-cutting concern in an organization, integrating technical and business aspects. For this reason, various stakeholders (e.g., developers and consultants) may get involved into modeling the features of a software product line. Currently, collaboration in such a scenario can only be done with face-to-face meetings or by combining single-user feature-model editors with additional communication and version-control systems. While face-to-face meetings are often costly and impractical, using version-control systems can cause merge conflicts and inconsistency within a model, due to the different intentions of the involved stakeholders. Advanced tools that solve these problems by enabling collaborative, real-time feature modeling, analogous to Google Docs or Overleaf for text editing, are missing. In this article, we build on a previous paper and describe (1) the extended formal foundations of collaborative, real-time feature modeling, (2) our conflict resolution algorithm in more detail, (3) proofs that our formalization converges and preserves causality as well as user intentions, (4) the implementation of our prototype, and (5) the results of an empirical evaluation to assess the prototype’s usability. Our contributions provide the basis for advancing existing feature-modeling tools and practices to support collaborative feature modeling. The results of our evaluation show that our prototype is considered helpful and valuable by 17 users, also indicating potential for extending our tool and opportunities for new research directions.

Intel's novel Software Guard eXtensions (SGX) enable secure and trusted execution of services, thereby paving the way to outsource sensitive data processing to external data centers. While SGX promises trusted execution close to native speed, frequent I/O operations and memory usage beyond a hardware-dependent threshold of currently 92 MiB result in substantial performance degradation. For memory-intensive workloads such as key-value stores and databases these penalties can be prohibitively high. We present STANlite - an in-memory database engine for SGX-enabled secure data processing in rack-scale environments. STANlite performs efficient user-level paging, whenever a database workload requires more space than the performance-friendly in-memory state size. Furthermore, STANlite smartly combines the properties of Remote Direct Memory Access (RDMA) and SGX to reduce the overhead of network-based I/O operations. While SGX usually provides confidentiality and integrity at the same time, STANlite enables a purely integrity preserving data management mode for additional performance. Finally, STANlite features a small trusted computing base and is memory-efficient, as it extends SQLite, a database for embedded use. We evaluated STANlite in terms of query response time. It outperforms a vanilla SGX-based SQLite version by 1.79x for microbenchmarks and 2.44x for TPC-C.

Highly-configurable systems encompass thousands of interdependent configuration options, which require a non-trivial configuration process. Decision propagation enables a backtracking-free configuration process by computing values implied by user decisions. However, employing decision propagation for large-scale systems is a time-consuming task and, thus, can be a bottleneck in interactive configuration processes and analyses alike. We propose modal implication graphs to improve the performance of decision propagation by precomputing intermediate values used in the process. Our evaluation results show a significant improvement over state-of-the-art algorithms for 120 real-world systems.

The source code of highly-configurable software is challenging to comprehend, analyze, and test. In particular, it is hard to identify all configurations that comprise a certain code location. We contribute PCLocator, a tool suite that solves this problem by utilizing static analysis tools for compile-time variability. Using BusyBox and the Variability Bugs Database (VBDb), we evaluate the correctness and performance of PCLocator. The results show that we are able to analyze files in a matter of seconds and derive correct configurations in 95% of all cases.

Due to its fast and simple applicability, clone-and-own is widely used in industry to develop software variants. In cooperation with different companies for thermoelectric products, we implemented multiple variants of a heat monitoring tool based on clone-and-own. After encountering redundancy-related problems during development and maintenance, we decided to migrate towards a software product line. Within this paper, we describe this case study of migrating cloned variants to a software product line based on the extractive approach. The resulting software product line encapsulates variability on several levels, including the underlying hardware systems, interfaces, and use cases. Currently, we support monitoring hardware from three different companies that use the same core system and provide a configurable front-end. We share our experiences and encountered problems with cloning and migration towards a software product line---focusing on feature extraction and modeling in particular. Furthermore, we provide a lightweight, web-based tool for modeling, configuring, and implementing software product lines, which we use to migrate and manage features. Besides this experience report, we contribute most of the created artifacts as open-source and freely available for the research community.

FeatureIDE is an open-source framework to model, develop, and analyze feature-oriented software product lines. It is mainly developed in a cooperation between TU Braunschweig, University of Magdeburg, and Metop GmbH. Nevertheless, many other institutions contributed to it in the past decade. Goal of this tutorial is to illustrate how FeatureIDE can be used to clean variable code, whereas we will focus on dependencies in feature models and on variability implemented with preprocessors. The hands-on tutorial will be highly interactive and is devoted to practitioners facing problems with variability, lecturers teaching product lines, and researchers who want to save resources in building product-line tools based on the FeatureIDE infrastructure.

A software product line comprises a family of software products that share a common set of features. It enables customers to compose software systems from a managed set of features. Testing every product of a product line individually is often infeasible due to the exponential number of possible products in the number of features. Several approaches have been proposed to restrict the number of products to be tested by sampling a subset of products achieving sufficient combinatorial interaction coverage. However, existing sampling algorithms do not scale well to large product lines, as they require a considerable amount of time to generate the samples. Moreover, samples are not available until a sampling algorithm completely terminates. As testing time is usually limited, we propose an incremental approach of product sampling for pairwise interaction testing (called IncLing), which enables developers to generate samples on demand in a step-wise manner. Furthermore, IncLing uses heuristics to efficiently achieve pairwise interaction coverage with a reasonable number of products. We evaluated IncLing by comparing it against existing sampling algorithms using feature models of different sizes. The results of our approach indicate efficiency improvements for product-line testing.

Most software systems are designed to provide custom functionality using configuration options. Testing such systems is challenging as running tests of a single configuration is often not sufficient, because defects may appear in other configurations. Ideally, all configurations of a software system should be tested, which is usually not applicable in practice due to the combinatorial explosion with respect to the configuration options. Multiple sampling strategies aim to reduce the set of tested configurations to a feasible amount, such as T-wise sampling, random configurations, and user-defined configurations. However, these strategies are often not applied in practice as they require manual effort or a specialized testing framework. Within our tool FeatureIDE, we integrate all aforementioned strategies and reduce the manual effort by automating the process of generating and testing configurations. Furthermore, we provide support for unit testing to avoid redundant test executions and for variability-aware testing. With this extension of FeatureIDE, we aim to make recent testing techniques for configurable systems applicable in practice.

Today’s competitive marketplace requires the industry to understand unique and particular needs of their customers. Product line practices enable companies to create individual products for every customer by providing an interdependent set of features. Users configure personalized products by consecutively selecting desired features based on their individual needs. However, as most features are interdependent, users must understand the impact of their gradual selections in order to make valid decisions. Thus, especially when dealing with large feature models, specialized assistance is needed to guide the users in configuring their product. Recently, recommender systems have proved to be an appropriate mean to assist users in finding information and making decisions. In this paper, we propose an advanced feature recommender system that provides personalized recommendations to users. In detail, we offer four main contributions: (i) We provide a recommender system that suggests relevant features to ease the decision-making process. (ii) Based on this system, we provide visual support to users that guides them through the decision-making process and allows them to focus on valid and relevant parts of the configuration space. (iii) We provide an interactive open-source configurator tool encompassing all those features. (iv) In order to demonstrate the performance of our approach, we compare three different recommender algorithms in two real case studies derived from business experience.

Today's software systems are often customizable by means of load-time or compile-time configuration options. These options are typically not independent and their dependencies can be specified by means of feature models. As many industrial systems contain thousands of options, the maintenance and utilization of feature models is a challenge for all stakeholders. In the last two decades, numerous approaches have been presented to support stakeholders in analyzing feature models. Such analyses are commonly reduced to satisfiability problems, which suffer from the growing number of options. While first attempts have been made to decompose feature models into smaller parts, they still require to compose all parts for analysis. We propose the concept of a feature-model interface that only consists of a subset of features, typically selected by experts, and hides all other features and dependencies. Based on a formalization of feature-model interfaces, we prove compositionality properties. We evaluate feature-model interfaces using a three-month history of an industrial feature model from the automotive domain with 18,616 features. Our results indicate performance benefits especially under evolution as often only parts of the feature model need to be analyzed again.

Feature models are a well-known concept to represent variability in software product lines by defining features and their dependencies. During feature-model evolution, for information hiding, and for feature-model analyses, it is often necessary to remove certain features from a model. As the crude deletion of features can have undesirable effects on their dependencies, dependency-preserving algorithms, known as feature-model slicing, have been proposed. However, current algorithms do not perform well when removing a high number of features from large feature models. Therefore, we propose an efficient algorithm for feature-model slicing based on logical resolution and the minimization of logical formulas. We empirically evaluate the scalability of our algorithm on a number of feature models and find that our algorithm generally outperforms existing algorithms.

FeatureIDE is an open-source framework to model, develop, and analyze feature-oriented software product lines. It is mainly developed in a cooperation between University of Magdeburg and Metop GmbH. Nevertheless, many other institutions contributed to it in the past decade. Goal of this tutorial is to illustrate how FeatureIDE can be used to clean variable code, whereas we will focus on dependencies in feature models and on variability implemented with preprocessors. The hands-on tutorial will be highly interactive and is devoted to practitioners facing problems with variability, lecturers teaching product lines, and researchers who want to safe resources in building product line tools.