Dataset of the paper "A Comparative Analysis of Backbone Algorithms for Configurable Software Systems"

A Comparative Analysis of Backbone Algorithms for Configurable Software Systems

Authors: Luis Cambelo, Ruben Heradio, Jose M. Horcas, Dictino Chaos, David Fernandez-Amoros

Venue: SoSyM (Software and Systems Modeling), Springer Nature

This repository provides the dataset utilized in the paper "A Comparative Analysis of Backbone Algorithms for Configurable Software Systems." The paper offers the first comprehensive empirical evaluation of backbone computation algorithms applied to formulas derived from real-world variability models (VMs). Additionally, the repository contains the R code used for dataset analysis.

Dataset (/dataset)

The dataset contains 2,371 DIMACS CNF files representing feature models from multiple domains.t processing |

File Format

All files use the DIMACS CNF format:

c Comments mapping feature names to variable indices
c Feature "WiFi" corresponds to variable 42
p cnf <num_variables> <num_clauses>
1 -2 3 0
-1 2 0
...

Header: p cnf <num_variables> <num_clauses>

Comments: Lines starting with c provide feature-to-variable mappings

Clauses: Space-separated literals (positive/negative integers) ending with 0

Naming Convention

Files follow the pattern: {domain}-{system_name}-{source_citation}.dimacs

Examples:

security-CVE-VarelaVaca2020-2002-2436.dimacs (309 variables, 13,929 clauses)

automotive-automotive01-Kowal2016.dimacs (2,513 variables, 10,300 clauses)

finance-bank-AlHajjaji2019.dimacs (176 variables, 280 clauses)

systems_software-linux-She2010.dimacs (6,888 variables, 343,944 clauses)

Results (/results)

CSV Files

1. backbone_time.csv (1,287,453 rows)

Raw execution time measurements for all solver runs.

Columns:

model: Feature model identifier

config_id: Configuration identifier (C01-C21)

solver: Solver name (IPASIRBones_MiniSat, IPASIRBones_CaDiCaL, MiniBones, CadiBack)

chunk_size: k parameter for MiniBones configurations (NA for non-MiniBones)

seconds: Execution time

Note: Contains multiple runs per (model, config, chunk_size) combination for statistical reliability.

2. models_info.csv (2,371 rows)

Feature model characteristics—one row per dataset model.

Columns:

model: Feature model identifier

num_variables: Number of Boolean variables

num_clauses: Total number of clauses

num_clauses_with_more_than_two_literals: Clauses with >2 literals

median_clause_size: Median literals per clause

mad_clause_size: Median absolute deviation of clause size

num_core: Number of core features (always selected)

num_dead: Number of dead features (never selected)

num_backbone: Total backbone variables (core + dead)

3. command_arguments.csv (20 rows)

Solver configuration specifications.

Columns:

config_id: Configuration identifier (C01-C21)

solver: Solver executable name

command_arguments: Command-line arguments used

config_id
solver
command_arguments

C01
IPASIRBones_MiniSat
-s

C02
IPASIRBones_MiniSat
-t

C03
IPASIRBones_MiniSat
-ti

C04
IPASIRBones_CaDiCaL
-t

C05
MiniBones
-urc 1

C06
MiniBones
-iurc 1

C07
CadiBack
--one-by-one --really-flip

C08
MiniBones
-uc k

C09
MiniBones
-iuc k

C10
CadiBack
--chunking --no-flip

C11
MiniBones
-urc k

C12
MiniBones
-iurc k

C13
CadiBack
--chunking --really-flip

C14
CadiBack
(default)

C15
MiniBones
-ec k

C16
MiniBones
-iec k

C17
CadiBack
--cores --no-flip

C18
MiniBones
-erc k

C19
MiniBones
-ierc k

C20
CadiBack
--cores --really-flip

C21
EDUCIBone
(default)

Key Configurations:

C01: IPASIRBones with MiniSat (Alg. 1 — naive iterative)

C02-C07: IPASIRBones / MiniBones / CadiBack variants (Alg. 2/3 — iterative with solution filtering)

C08-C14: MiniBones / CadiBack variants (Alg. 4 — chunked all-in)

C15-C20: MiniBones / CadiBack variants (Alg. 5 — chunked all-out / core-based)

C21: EDUCIBone (Alg. 2/3 with COV, WHIT, and 2LEN filtering)

4. median_time_and_models_tb.csv (429,143 rows)

Pre-computed median aggregations for faster analysis.

Purpose: Combines median execution times with model characteristics, grouped by (model, config_id, chunk_size). Auto-generated by the analysis pipeline and cached for subsequent runs.

Figures Directory (/results/figures)

1,284 high-resolution PNG files (600-700 DPI) organized into several categories:

Pairwise Configuration Comparisons (1,261 files)

Format: pair_plot_C{i}_C{j}__best_ks{_small_models|_large_models}.png

Content:

Scatter plots showing percentage time reduction vs. number of variables

Wilcoxon signed-rank test statistics (p-values, effect sizes)

Three variants: all models, small models (≤1,000 vars), large models (>1,000 vars)

Example: pair_plot_C01_C08__best_ks.png compares IPASIRBones_MiniSat (C01) against MiniBones with optimal k (C08).

K Parameter Analysis (16 files)

best_k_vs_num_vars_C{id}.png: Correlation between optimal k and model size (variables)

best_k_vs_num_clauses_C{id}.png: Correlation between optimal k and clause count

chunk_size_density_C{id}.png: Distribution of best k values

Insight: These plots demonstrate the difficulty of selecting optimal k parameters a priori.

Configuration Performance Rankings (2 files)

best_confs__small_models.png: Win percentage for configurations on small models

best_confs__large_models.png: Win percentage for configurations on large models

Shows which configurations achieve the fastest execution time most frequently.

Dataset Characterization (1 file)

nclauses_vs_nvars.png: Scatter plot of variables vs. clauses with marginal density plots

Visualizes the size distribution and relationship between model dimensions.

Time-K Relationship Examples (4 files)

time_vs_k_C{id}_{model_examples}.png: Execution time as a function of k for selected models

Demonstrates how performance varies with the k parameter on specific instances.

Replicating the Analysis

Prerequisites

R: Version 3.6 or higher

Packages: Auto-installed by the script

tidyverse, hrbrthemes, scales, patchwork, ggpubr, ggExtra, pgirmess

Running the Analysis

cd /mnt/backbone/zenodo/analysis_code
Rscript main.R

Analysis Workflow

The main.R script executes the following steps:

Load Dependencies (imports_and_constants.R)

Installs missing packages automatically

Sets plotting theme and constants

Sources analysis modules

Load and Aggregate Data (read_data.R)

Reads raw CSV files from ../results/

Computes median execution times grouped by (model, config_id, chunk_size)

Caches results to median_time_and_models_tb.csv

Generate MiniBones Variants (minibones_ks.R)

Best-k: Optimal k per model (C08, C09, C11, C12, C14, C15, C17, C18)

Median-k: Median of best k values across models

Default k=100: Standard MiniBones configuration

Statistical Analysis (get_inferential_stats.R)

Wilcoxon signed-rank tests for pairwise comparisons

Kruskal-Wallis tests with post-hoc analysis for multiple configurations

Effect size calculations

Generate Visualizations (get_plots.R)

1,261 pairwise comparison plots (all models, small, large)

K parameter correlation and density plots

Configuration ranking charts

Dataset characterization plots

Expected Outputs

Figures: All 1,284 PNG files regenerated in results/figures/

Console Output: Statistical summaries (xtable format for LaTeX)

Cache File: Updated results/median_time_and_models_tb.csv

Repository Structure

/mnt/backbone/zenodo/
├── README.md # This file
├── dataset/ # 2,371 DIMACS feature models
│ ├── automotive-automotive01-Kowal2016.dimacs
│ ├── security-CVE-VarelaVaca2020-2002-2436.dimacs
│ ├── systems_software-linux-She2010.dimacs
│ ├── finance-bank-AlHajjaji2019.dimacs
│ └── ...
├── results/ # Analysis outputs
│ ├── backbone_time.csv # Raw execution times (1.2M rows)
│ ├── models_info.csv # Model characteristics (2,371 rows)
│ ├── command_arguments.csv # Configuration specs (20 rows)
│ ├── median_time_and_models_tb.csv # Cached aggregations (429K rows)
│ └── figures/ # 1,284 analysis plots (PNG, 600-700 DPI)
│ ├── pair_plot_C01_C02__best_ks.png
│ ├── pair_plot_C01_C02__best_ks_small_models.png
│ ├── best_k_vs_num_vars_C08.png
│ ├── best_confs__small_models.png
│ ├── nclauses_vs_nvars.png
│ └── ...
└── analysis_code/ # R analysis pipeline
├── main.R # Master script
├── imports_and_constants.R # Dependencies and setup
├── read_data.R # Data loading/caching
├── get_plots.R # Visualization functions
├── get_inferential_stats.R # Statistical tests
└── minibones_ks.R # K parameter analysis

Research Questions and Findings

The paper investigates 8 research questions:

Q1: Are formulas obtained from VMs different from those used in SAT competitions?

Yes, they are. VM formulas are structurally distinct: they have fewer variables (median 356 vs. 13,408), many more clauses per variable (39.84 vs. 5.46 clauses/variable ratio), and much simpler clauses — about 98% of clauses contain at most two literals, compared to 61% with more than two literals in SAT competition formulas.

Q2: Is Alg. 2/3 faster than Alg. 1?

Yes, it is. Alg. 2/3 (iterative with solution filtering) is consistently faster than Alg. 1 (naive iterative) across the entire dataset, with a statistically significant difference and large effect size.

Q3: Are there faster algorithms than Alg. 1 or Alg. 2/3?

Yes, there are. Alg. 2/3 is the fastest for formulas with 1,000 or fewer variables. For formulas with more than 1,000 variables, Alg. 5 (chunked core-based) demonstrates superior performance. With optimal chunk size k, Alg. 5 can achieve runtime reductions exceeding 50%. CadiBack's adaptive k selection provides the best practical performance for large formulas.

Q4: Is it possible to infer the optimal k for Algs. 4 and 5?

No, it is not. The optimal k varies unpredictably across formulas and shows only weak correlation with the number of variables or clauses (Spearman's rho < 0.2). Neither the number of variables nor the number of clauses are effective predictors. The distribution of optimal k values is too scattered for centrality measures (like the median) to improve over default settings.

Q5: Does UC injection influence performance?

No, it does not. Injecting backbone literals as unit clauses showed no influence (neither positive nor negative) across all tested algorithm and configuration pairs.

Q6: Does TIP influence performance?

Yes, it does, but only when combined with RL filtering in Alg. 2/3. In all other cases, TIP has no measurable effect.

Q7: Does literal filtering with RLs influence performance?

No, it does not. Filtering with rotatable literals showed no influence (neither positive nor negative) across all algorithm configurations.

Q8: Does combined filtering (COV, WHIT, 2LEN) influence performance?

Yes, it does, but quite negatively. The combined application of COV, WHIT, and 2LEN has a statistically significant and substantial negative effect on Alg. 2/3 performance.

Citation

If you use this dataset or analysis in your research, please cite:

Luis Cambelo, Ruben Heradio, Jose M. Horcas, Dictino Chaos, David Fernandez-Amoros. "A Comparative Analysis of Backbone Algorithms for Configurable Software Systems." Software and Systems Modeling (SoSyM), Springer Nature, 2025.

Funding

This work is funded by FEDER/Spanish Ministry of Science, Innovation and Universities (MCIN)/Agencia Estatal de Investigacion (AEI) under grant COSY (PID2022-142043NB-I00), IRIS (PID2021-122812OB-I00), SAVIA (PID2024-159945NB-I00), and Data-PL (PID2022-138486OB-I00); and by Junta de Andalucía under grant DUNE (DGP_PIDI_2024_00092).

License

MIT

Contact

Luis Cambelo — Universidad Nacional de Educacion a Distancia (UNED) — [e-mail]

Ruben Heradio — Universidad Nacional de Educacion a Distancia (UNED) — [e-mail]

Jose M. Horcas — Universidad de Malaga — [e-mail]

Dictino Chaos — Universidad Nacional de Educacion a Distancia (UNED) — [e-mail]

David Fernandez-Amoros — Universidad Nacional de Educacion a Distancia (UNED) — [e-mail]