Abstract
Uniform Random Sampling (URS) is a critical technique for testing highly-configurable software systems where exhaustive testing is computationally impossible. However, evaluating URS tools is challenging due to the inherent trade-off between scalability and statistical uniformity. This paper presents BURST, an open-source benchmarking platform that provides a standardized environment for evaluating URS techniques. BURST integrates 10 state-of-the-art samplers and subjects them to a library of 128 diverse models. Our results highlight the tension between speed and fairness, identifying specific tools like CMSgen that offer promising trade-offs.
Introduction
Modern software systems, such as the Linux kernel or the JHipster web generator, are "highly-configurable," featuring thousands of optional toggles that interact in complex ways. This leads to a combinatorial explosion where the number of valid configurations can exceed the number of atoms in the universe. To ensure reliable testing and statistical verification without exhaustive search, researchers employ Uniform Random Sampling (URS). The goal of URS is to select a subset of configurations where every valid combination has an equal mathematical probability of being chosen.
A significant hurdle in URS is the computational cost of achieving perfect fairness. Most sampling tools must navigate a trade-off between scalability (execution speed) and uniformity (mathematical fairness). Until now, the research community lacked a unified framework to compare these tools across diverse software models.
The BURST Benchmarking Platform
BURST (Benchmarking Uniform Random Sampling Techniques) is designed as a rigorous evaluation "arena" rather than a new sampling algorithm. It automates the assessment of samplers on two primary axes:
- Scalability: The time required to produce samples from Boolean formulas in DIMACS format.
- Uniformity: Evaluated using Barbarik, a statistical test that detects deviations from a truly uniform distribution.
To ensure high reproducibility, the authors have meticulously documented the code and software metadata, ensuring that the benchmarking environment can be replicated by other researchers.
The platform is packaged as a Docker image, containing all 10 integrated samplers (e.g., UniGen, KUS, CMSgen), their dependencies, and the evaluation datasets. This containerized approach allows researchers to run a single command to compare a new algorithm against the current state-of-the-art.
Datasets and Evaluation
BURST includes a diverse library of 128 models out of the box:
- Feature Models: Real-world systems like various versions of the Linux kernel, the BusyBox toolset, and the JHipster web stack.
- SAT/AI Benchmarks: Models mined from the artificial intelligence and satisfiability (SAT) solving communities to ensure cross-domain utility.
The platform generates detailed CSV reports documenting execution times, model counts, and the results of the Barbarik uniformity tests (reporting True/False based on statistical significance).
Key Insights and Results
The evaluation conducted via BURST revealed several critical insights:
- The Scalability-Uniformity Tension: There is a clear "unhappy triad" where tools struggle to simultaneously achieve high speed, handle high complexity, and maintain perfect uniformity. Fast samplers often introduce bias, while perfectly fair ones scale poorly on large models.
- Performance of CMSgen: The CMSgen sampler emerged as a "sweet spot," providing a highly encouraging balance between rapid sample generation and strong uniformity properties.
- Standardization as Infrastructure: By providing a common interface and pre-packaged models, BURST significantly lowers the barrier to entry for researchers, transforming the evaluation process from weeks of setup to a streamlined automated task.
Conclusion
BURST represents a significant step toward standardizing the evaluation of URS algorithms. By providing a reproducible, Docker-based environment and a comprehensive model library, it serves as a "proving ground" for the next generation of sampling techniques. Future work will focus on extending the platform to include more metrics, such as memory consumption and sample diversity in non-uniform contexts.
Summary updated