torte is a declarative workbench for reproducible experiments in feature-model analysis research.

Why torte? Take your pick:

• "Tseitin or not Tseitin?" Evaluator
• CNF Transformation Workbench
• KConfig Extractor that Tackles Evolution
• Towards Reproducible Feature-Model Transformation and Extraction
• That's an Obviously Reverse-Engineered Tool Name
• KConfig = 🍰 config ∧ 🍰 = torte ∎

torte can be used to

• extract feature models from KConfig-based configurable software systems (e.g., the Linux kernel),
• transform feature models between various formats (e.g., FeatureIDE, UVL, and DIMACS), and
• analyze feature models with solvers to evaluate the extraction and transformation impact,

all in a fully declarative and reproducible fashion backed by reusable Docker containers. This way, you can

• draft experiments for selected feature models first, then generalize them to a larger corpus later,
• execute experiments on a remote machine without having to bother with technical setup,
• distribute fully-automated reproduction packages when an experiment is ready for publication, and
• adapt and update existing experiments without needing to resort to clone-and-own practices.

This one-liner will get you started with the default experiment (Docker required).

curl -s https://ekuiter.github.io/torte/ | sh

Read on if you want to know more details.

To run torte, you need:

• an x86_64 or arm64 system ¹ with Linux, macOS, or Windows with WSL
• Git, curl, GNU tools (bash, coreutils, make, grep, and sed)
• Docker (preferably in rootless mode on Linux)

Experiment files in torte are self-executing - so, you can just create or download an experiment file (e.g., from the experiments directory) and run it.

The following instructions will get you started on a fresh system. By default, each of these instruction sets will install torte into the torte directory. All experiment data will then be stored in the directories input and output in your working directory.

# install and set up dependencies
sudo apt-get update
sudo apt-get install -y curl git make uidmap dbus-user-session

# install Docker (see https://docs.docker.com/desktop/install/linux-install/)
curl -fsSL https://get.docker.com | sh
dockerd-rootless-setuptool.sh install

# download and run the default experiment
curl -s https://ekuiter.github.io/torte/ | sh

# install and set up dependencies (this will replace macOS' built-in bash with a newer version)
/bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)"
(echo; echo 'eval "$(/opt/homebrew/bin/brew shellenv)"') >> $HOME/.zprofile
eval "$(/opt/homebrew/bin/brew shellenv)"
brew install bash coreutils gnu-sed grep

# install Docker (see https://docs.docker.com/desktop/install/mac-install/)
curl -o Docker.dmg https://desktop.docker.com/mac/main/arm64/149282/Docker.dmg
sudo hdiutil attach Docker.dmg
sudo /Volumes/Docker/Docker.app/Contents/MacOS/install --accept-license
sudo hdiutil detach /Volumes/Docker
rm Docker.dmg
open /Applications/Docker.app

# download and run the default experiment
curl -s https://ekuiter.github.io/torte/ | sh

# install WSL (see https://learn.microsoft.com/windows/wsl/install)
powershell
wsl --install

# install Docker (see https://docs.docker.com/desktop/install/windows-install/)
Invoke-WebRequest https://desktop.docker.com/win/main/amd64/149282/Docker%20Desktop%20Installer.exe -OutFile Docker.exe
Start-Process Docker.exe -Wait -ArgumentList 'install', '--accept-license'

# install and set up dependencies
wsl
sudo apt-get update
sudo apt-get install -y curl git make

# download and run the default experiment
curl -s https://ekuiter.github.io/torte/ | sh

Above, we run the default experiment, which extracts, transforms, and analyzes the feature model of BusyBox 1.36.0 as a demonstration. To execute another experiment, run curl -s https://ekuiter.github.io/torte/ | sh -s - <experiment> (a list of predefined experiments is available here). You can also write your own experiments by adapting an existing experiment file.

Further Tips

• As an alternative to the self-extracting installer shown above, you can clone this repository and run experiments with ./torte.sh <experiment-file>.
• A running experiment can be stopped with Ctrl+C. If this does not respond, try Ctrl+Z, then ./torte.sh stop.
• Run ./torte.sh help to get further usage information (e.g., running an experiment over SSH and im-/export of Docker containers).
• Developers are recommended to use ShellCheck to improve code quality.
• If Docker is running in rootless mode, experiments must not be run as sudo. Otherwise, experiments must be run as sudo.
• The first execution of torte can take a while (~30 minutes), as several complex Docker containers need to be built. This can be avoided by loading a reproduction package that includes Docker images (built by ./torte.sh export).

This is a list of all subject systems for which feature-model extraction has been tested and confirmed to work for at least one extraction tool. Other systems or revisions may also be supported. Detailed system-specific information on potential threats to validity is available in the scripts/subjects directory.

The following tools are bundled with torte and can be used in experiments for extracting, transforming, and analyzing feature models. Most tools are not included in this repository, but cloned and built with tool-specific Docker files in the docker directory. The bundled solvers are listed in a separate table below.

For transparency, we document the changes we make to these tools and known limitations. There are also some general known limitations of torte. ⁷

The following solvers are bundled with torte and can be used in experiments for analyzing feature-model formulas. The bundled solver binaries are available in the docker/solver directory. Solvers are grouped in collections to allow several versions of the same solver to be used.

In addition to the solvers listed below, z3 (already listed above) can be used as a satisfiability and SMT solver.

These #SAT solvers (available here) were used in the evaluations of several papers:

• Evaluating State-of-the-Art #SAT Solvers on Industrial Configuration Spaces (EMSE 2023)
• Tseitin or not Tseitin? The Impact of CNF Transformations on Feature-Model Analyses (ASE 2022)

The #SAT solvers from the collection model-counting-competition-2022 should be preferred for new experiments.

These #SAT solvers (available here) were used in the model-counting competition 2022. Not all evaluated solvers are included here, as some solver binaries (i.e., for MTMC and ExactMC) have not been disclosed.

These are miscellaneous solvers from various sources.

A subset of these SAT solvers (binaries copied/compiled from here) were used in the evaluation of the paper Tseitin or not Tseitin? The Impact of CNF Transformations on Feature-Model Analyses (ASE 2022). Each solver is the gold medal winner in the main track (SAT+UNSAT) of the SAT competition in the year encoded in its file name. We were unable to obtain binaries for the winning solvers in 2008 and 2015.

This is a list of all predefined experiments in the experiments directory and their purposes. Please create a pull request if you want to publish your own experiment. Experiments starting with draft- are experimental.

This project has evolved through several stages and intends to replace them all:

kmax-vm > feature-model-repository-pipeline > tseitin-or-not-tseitin > torte

• kmax-vm was intended to provide an easy-to-use environment for integrating kmax with PCLocator in a virtual machine using Vagrant/VirtualBox. It is now obsolete due to our Docker integration of kmax.
• feature-model-repository-pipeline extended kmax-vm and could be used to extract feature models from Kconfig-based software systems with kconfigreader and kmax. The results were stored in the feature-model-repository. Its functionality is completely subsumed by torte and more efficient and reliable due to our Docker integration.
• tseitin-or-not-tseitin extended the feature-model-repository-pipeline to allow for transformation and analysis of feature models. It was mostly intended as a reproduction package for a single academic paper. Its functionality is almost completely subsumed by torte, which can be used to create reproduction packages for many different experiments.

If you are looking for a curated collection of feature models from various domains, have a look at our feature-model-benchmark.

If you have any feedback, please contact me at [email protected]. New issues, pull requests, or any other kinds of feedback are always welcome.

The source code of this project is released under the LGPL v3 license. To ensure reproducibility, we also provide binaries (e.g., for solvers) in this repository. These binaries have been collected or compiled from public sources. Their usage is subject to each binaries' respective license - please contact me if you perceive any licensing issues.