How Low Can We Go? Minimizing Interaction Samples for Configurable Systems
ACM Transactions on Software Engineering and Methodology · 31.07.2025 · 34 (6) · 1-29
DOI: 10.1145/3712193 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Software Engineering and Methodology, 2025-07. Verfasst von Dominik M. Krupke und 7 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 99 Literaturangaben. Gefördert von: German Federal Ministry for Education and Science, German Federal Ministry of Economic Affairs and Climate Action.
Abstract (Originalsprache)
Modern software systems are typically configurable, a fundamental prerequisite for wide applicability and reusability. This flexibility poses an extraordinary challenge for quality assurance, as the enormous number of possible configurations makes it impractical to test each of them separately. This is where t-wise interaction sampling can be used to systematically cover the configuration space and detect unknown feature interactions. Over the last two decades, numerous algorithms for computing small interaction samples have been studied, providing improvements for a range of heuristic results; nevertheless, it has remained unclear how much these results can still be improved. We present a significant breakthrough: a fundamental framework, based on the mathematical principle of duality , for combining near-optimal solutions with provable lower bounds on the required sample size. This implies that we no longer need to work on heuristics with marginal or no improvement, but can certify the solution quality by establishing a limit on the remaining gap; in many cases, we can even prove optimality of achieved solutions. This theoretical contribution also provides extensive practical improvements: Our algorithm SampLNS was tested on 47 small- and medium-sized configurable systems from the existing literature. SampLNS can reliably find samples of smaller size than previous methods in \(85\%\) of the cases; moreover, we can achieve and prove optimality of solutions for \(63\%\) of all instances. This makes it possible to avoid cumbersome efforts of minimizing samples by researchers as well as practitioners, and substantially save testing resources for most configurable systems.
Förderung
- German Federal Ministry for Education and Science
- German Federal Ministry of Economic Affairs and Climate Action
Zitieren
APA
Krupke, D. M., Moradi, A., Perk, M., Keldenich, P., Gehrke, G., Krieter, S., Thüm, T., & Fekete, S. P. (2025). How Low Can We Go? Minimizing Interaction Samples for Configurable Systems. ACM Transactions on Software Engineering and Methodology, 34(6), 1-29. https://doi.org/10.1145/3712193
Vancouver
Krupke DM, Moradi A, Perk M, Keldenich P, Gehrke G, Krieter S, et al. How Low Can We Go? Minimizing Interaction Samples for Configurable Systems. ACM Transactions on Software Engineering and Methodology. 2025;34(6):1-29. doi:10.1145/3712193
BibTeX
@article{Krupke2025,
author = {Krupke, Dominik M. and Moradi, Ahmad and Perk, Michael and Keldenich, Phillip and Gehrke, Gabriel and Krieter, Sebastian and Thüm, Thomas and Fekete, Sándor P.},
title = {How Low Can We Go? Minimizing Interaction Samples for Configurable Systems},
journal = {ACM Transactions on Software Engineering and Methodology},
year = {2025},
volume = {34},
number = {6},
pages = {1--29},
doi = {10.1145/3712193}
}
EUVIMED