MulTi-Wise Sampling: Trading Uniform T-Wise Feature Interaction Coverage for Smaller Samples
Tobias Pett, Sebastian Krieter, Thomas Thüm, Ina Schaefer · 2024
Ensuring the functional safety of highly configurable systems often requires testing representative subsets of all possible configurations. The ratio of covered t-wise feature interactions is a common criterion for determining whether a subset of configurations is representative and capable of finding faults. Existing t-wise sampling algorithms cover t-wise feature interactions for all features equally, resulting in extensive sampling times and large sample sizes. In this paper, we introduce a novel approach to t-wise feature interaction sampling, relating the necessity of equal coverage across all t-wise feature interactions, called MulTi-Wise Sampling. MulTi-Wise Sampling prioritizes between subsets of critical and non-critical features, considering higher t-values for subsets of critical features when generating a sample. We evaluate MulTi-Wise Sampling using subject systems from real-world applications, including BusyBox, Soletta, Fiasco, and uCLibc-ng. Our results show that MulTi-Wise Sampling provides a flexible mechanism to reduce the number of configurations for testing, while the performance of the algorithm is still on par with state-of-the-art sampling algorithms.