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.

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.

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.