Feature-Model Counting
In this project, we work on the following aspects of feature-model analysis related to computing the number of valid configuration:
- Gather use-case scenarios for feature-model counting
- Identify scalable solutions for computing the number of valid configurations
- Optimize and tailor existing solutions for the application on feature models
- Develop new algorithms and tools to support analysis
Motivation
Feature-model counting enables a large variety of analyses. These range from simple analyses, such as prioritizing errors that appear in more valid configurations, to more complex computations such as finding a uniformly distributed sample of configurations.
Model Counting aka #SAT
The #SAT problem corresponds to computing the number of satisfying assignments of a propositional formula. By translating a feature model to a formula, we can reduce computing the number of valid configurations to a #SAT problem. This allows the usage of heavily optimized tools, #SAT solvers, that have made significant advances in the last decade. Nevertheless, we have seen feature models in the wild that cannot be analyzed within weeks of runtime.
Elias Kuiter
Elias
Kuiter
Ina Schaefer
Ina
Schaefer
Publications
2024
14.
C. Sundermann,
H. Raab,
T. Heß,
T. Thüm and
I. Schaefer,
"Reusing d-DNNFs for Efficient Feature-Model Counting",
Trans. on Software Engineering and Methodology (TOSEM),
Nov.
2024.
ACM.
| DOI: | 10.1145/3680465 |
13.
C. Sundermann,
V. F. Brancaccio,
E. Kuiter,
S. Krieter,
T. Heß and
T. Thüm,
"Collecting Feature Models from the Literature: A Comprehensive Dataset for Benchmarking"
in Proc. Int'l Systems and Software Product Line Conf. (SPLC),
New York, NY, USA:
ACM,
Sep.
2024,
pp. 54-65.
| DOI: | 10.1145/3646548.3672590 |
12.
C. Sundermann,
T. Heß,
M. Nieke,
P. M. Bittner,
J. M. Young,
T. Thüm and
I. Schaefer,
"Evaluating State-of-the-Art #SAT Solvers on Industrial Configuration Spaces - Summary"
in Proc. Software Engineering (SE),
Bonn, Germany:
Gesellschaft für Informatik,
Feb.
2024,
pp. 67-68.
| DOI: | 10.18420/sw2024_18 |
| ISBN: | 978-3-88579-737-1 |
| Datei: |  https://github.com/SoftVarE-Group/Papers/raw/main/2024/2024-SE-Sundermann.pdf |
11.
E. Kuiter,
T. Heß,
C. Sundermann,
S. Krieter,
T. Thüm and
G. Saake,
"How Easy Is SAT-Based Analysis of a Feature Model?"
in Proc. Int'l Working Conf. on Variability Modelling of Software-Intensive Systems (VaMoS),
New York, NY, USA:
ACM,
Feb.
2024,
pp. 149-151.
| DOI: | 10.1145/3634713.3634733 |
| Datei: | https://github.com/SoftVarE-Group/Papers/raw/main/2024/2024-VaMoS-Kuiter.pdf |
10.
T. Heß,
T. J. Schmidt,
L. Ostheimer,
S. Krieter and
T. Thüm,
"UnWise: High T-Wise Coverage From Uniform Sampling"
in Proc. Int'l Working Conf. on Variability Modelling of Software-Intensive Systems (VaMoS),
New York, NY, USA:
ACM,
Feb.
2024,
pp. 37-45.
| DOI: | 10.1145/3634713.3634716 |
| Datei: | https://github.com/SoftVarE-Group/Papers/raw/main/2024/2024-VaMoS-Hess.pdf |
9.
C. Sundermann,
J. Loth and
T. Thüm,
"Efficient Slicing of Feature Models via Projected d-DNNF Compilation"
in Proc. Int'l Conf. on Automated Software Engineering (ASE) (To Appear),
New York, NY, USA:
ACM,
2024.
2023
8.
C. Sundermann,
E. Kuiter,
T. Heß,
H. Raab,
S. Krieter and
T. Thüm,
"On the Benefits of Knowledge Compilation for Feature-Model Analyses",
Annals of Mathematics and Artificial Intelligence (AMAI),
pp. 1013-1050,
Nov.
2023.
Springer.
| DOI: | 10.1007/s10472-023-09906-6 |
| Datei: | https://github.com/SoftVarE-Group/Papers/raw/main/2023/2023-AMAI-Sundermann.pdf |
7.
C. Sundermann,
H. Raab,
T. Heß,
T. Thüm and
I. Schaefer,
"Exploiting d-DNNFs for Repetitive Counting Queries on Feature Models" ,
Technical Report arXiv:2303.12383,
Mä.
2023.
| DOI: | 10.48550/arXiv.2303.12383 |
| Datei: | https://github.com/SoftVarE-Group/Papers/raw/main/2023/2023-TR-Sundermann.pdf |
6.
E. Kuiter,
S. Krieter,
C. Sundermann,
T. Thüm and
G. Saake,
"Tseitin or Not Tseitin? The Impact of CNF Transformations on Feature-Model Analyses - Summary"
in Proc. Software Engineering (SE),
Bonn, Germany:
Gesellschaft für Informatik,
Feb.
2023,
pp. 83-84.
| Datei: | https://github.com/SoftVarE-Group/Papers/raw/main/2023/2023-SE-Kuiter-Tseitin.pdf |
5.
C. Sundermann,
T. Heß,
M. Nieke,
P. M. Bittner,
J. M. Young,
T. Thüm and
I. Schaefer,
"Evaluating State-of-the-Art #SAT Solvers on Industrial Configuration Spaces",
Empirical Software Engineering (EMSE),
pp. 38,
Jan.
2023.
Springer.
| DOI: | 10.1007/s10664-022-10265-9 |
| Datei: | https://github.com/SoftVarE-Group/Papers/raw/main/2023/2023-EMSE-Sundermann.pdf |
2022
4.
M. Hentze,
C. Sundermann,
T. Thüm and
I. Schaefer,
"Quantifying the Variability Mismatch Between Problem and Solution Space"
in Proc. Int'l Conf. on Model Driven Engineering Languages and Systems (MODELS),
Washington, DC, USA:
IEEE,
Okt.
2022,
pp. 322-333.
| DOI: | 10.1145/3550355.3552411 |
| ISBN: | 9781450394666 |
| Datei: | https://github.com/SoftVarE-Group/Papers/raw/main/2022/2022-MODELS-Hentze.pdf |
3.
E. Kuiter,
S. Krieter,
C. Sundermann,
T. Thüm and
G. Saake,
"Tseitin or not Tseitin? The Impact of CNF Transformations on Feature-Model Analyses"
in Proc. Int'l Conf. on Automated Software Engineering (ASE),
New York, NY, USA:
ACM,
Okt.
2022,
pp. 110:1-110:13.
| DOI: | 10.1145/3551349.3556938 |
| ISBN: | 9781450394758 |
| Datei: | https://github.com/SoftVarE-Group/Papers/raw/main/2022/2022-ASE-Kuiter.pdf |
2021
2.
C. Sundermann,
M. Nieke,
P. M. Bittner,
T. Heß,
T. Thüm and
I. Schaefer,
"Applications of #SAT Solvers on Feature Models"
in Proc. Int'l Working Conf. on Variability Modelling of Software-Intensive Systems (VaMoS),
New York, NY, USA:
ACM,
Feb.
2021.
| DOI: | 10.1145/3442391.3442404 |
| ISBN: | 9781450388245 |
| Datei: | https://github.com/SoftVarE-Group/Papers/raw/main/2021/2021-VaMoS-Sundermann.pdf |
2020
1.
C. Sundermann,
T. Thüm and
I. Schaefer,
"Evaluating #SAT Solvers on Industrial Feature Models"
in Proc. Int'l Working Conf. on Variability Modelling of Software-Intensive Systems (VaMoS),
New York, NY, USA:
ACM,
Feb.
2020.
| DOI: | 10.1145/3377024.3377025 |
| ISBN: | 9781450375016 |
| Datei: | https://github.com/SoftVarE-Group/Papers/raw/main/2020/2020-VaMoS-Sundermann.pdf |
Theses
2024
12.
J. Riesland,
"Optimizing T-Wise Sampling on d-DNNFs with Objective Functions",
Bachelor's Thesis,
University of Ulm,
Germany,
Jan.
2024.
2023
11.
R. Dunkel,
"One Solver to Rule All Feature Models - Or Not? Addressing the Algorithm Selection Problem for #SAT",
Bachelor's Thesis,
University of Ulm,
Germany,
Dez.
2023.
10.
H. Raab,
"Incrementally Adapting d-DNNFs to Cope with Feature-Model Evolution",
Master's Thesis,
University of Ulm,
Germany,
Nov.
2023.
| DOI: | 10.18725/OPARU-52288 |
9.
J. Loth,
"Projected d-DNNF Compilation for Feature Models",
Master's Thesis,
University of Ulm,
Germany,
Nov.
2023.
8.
C. Schmid,
"Parameterizations for Approximate #SAT Solvers",
Bachelor's Thesis,
University of Ulm,
Germany,
Okt.
2023.
7.
L. Licha,
"Cutting Edge T-Wise Sampling With ddnnife",
Bachelor's Thesis,
University of Ulm,
Germany,
Jan.
2023.
2022
6.
L. Ostheimer,
"Identification of Variance Driving Features in Feature Models",
Bachelor's Thesis,
University of Ulm,
Germany,
Dez.
2022.
5.
V. Brancaccio,
"A Systematic Literature Review Towards a Representative Feature-Model Benchmark",
Master's Thesis,
University of Ulm,
Germany,
Nov.
2022.
| DOI: | 10.18725/OPARU-46759 |
4.
S. Vill,
"Language Levels for the Universal Variability Language: An Extension Mechanism and Conversion Strategies",
Bachelor's Thesis,
University of Ulm,
Germany,
Nov.
2022.
| DOI: | 10.18725/OPARU-47708 |
| Datei: | https://oparu.uni-ulm.de/xmlui/bitstream/handle/123456789/47784/thesis_vill.pdf |
3.
Y. Heimowski,
"Simplifying Feature Models for Better Scalability of #SAT Solvers",
Bachelor's Thesis,
University of Ulm,
Germany,
Aug.
2022.
2.
D. Schiessl,
"An Incremental #SAT Solver for Efficient Analysis of Feature Models",
Master's Thesis,
University of Ulm,
Germany,
Jan.
2022.
1.
H. Raab,
"Exploiting d-DNNFs for Efficient Cardinality-Based Feature-Model Analyses",
Bachelor's Thesis,
University of Ulm,
Germany,
Jan.
2022.
| DOI: | 10.18725/OPARU-43414 |
| Datei: | https://oparu.uni-ulm.de/xmlui/bitstream/handle/123456789/43490/Thesis_RaabHeiko.pdf |
Project Lead
M.Sc. Chico Sundermann
M.Sc.
Chico
Sundermann
Research Assistant
Ulm University
Institute of Software Engineering and Programming Languages
Albert-Einstein-Allee 11
Institute of Software Engineering and Programming Languages
Albert-Einstein-Allee 11
89069
Ulm
Germany
E-Mail:
chico.sundermann(at)uni-ulm.de
www:
Chico Sundermann
Raum:
O27 413
Telefon:
+49-731/50-24174