Institute of Software Engineering and Programming Languages

Feature-Model Counting

In this project, we work on the following aspects of feature-model analysis related to computing the number of valid configuration:

  1. Gather use-case scenarios for feature-model counting
  2. Identify scalable solutions for computing the number of valid configurations
  3. Optimize and tailor existing solutions for the application on feature models
  4. 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.

Team Members

Student Members, Workers, and Projecteers

Publications

2024

14.
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
13.
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
File:pdfhttps://github.com/SoftVarE-Group/Papers/raw/main/2024/2024-SE-Sundermann.pdf
12.
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
File:pdfhttps://github.com/SoftVarE-Group/Papers/raw/main/2024/2024-VaMoS-Kuiter.pdf
11.
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
File:pdfhttps://github.com/SoftVarE-Group/Papers/raw/main/2024/2024-VaMoS-Hess.pdf
10.
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.
9.
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) (To Appear), 2024. ACM.

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), Nov. 2023. Springer.
DOI:10.1007/s10472-023-09906-6
File:pdfhttps://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, Mar. 2023.
DOI:10.48550/arXiv.2303.12383
File:pdfhttps://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.
File:pdfhttps://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
File:pdfhttps://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, Oct. 2022, pp. 322-333.
DOI:10.1145/3550355.3552411
ISBN:9781450394666
File:pdfhttps://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, Oct. 2022, pp. 110:1-110:13.
DOI:10.1145/3551349.3556938
ISBN:9781450394758
File:pdfhttps://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
File:pdfhttps://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
File:pdfhttps://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, Dec. 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, Oct. 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, Dec. 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
File:pdfhttps://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
File:pdfhttps://oparu.uni-ulm.de/xmlui/bitstream/handle/123456789/43490/Thesis_RaabHeiko.pdf

Project Lead