Uniform Sampling of SAT Solutions for Configurable Systems: Are We There Yet?

Quentin Plazar, Mathieu Acher, Gilles Perrouin, Xavier Devroey, Maxime Cordy

Research output: Contribution in Book/Catalog/Report/Conference proceedingConference contribution

Abstract

Uniform or near-uniform generation of solutions for large satisfiability formulas is a problem of theoretical and practical interest for the testing community. Recent works proposed two algorithms (namely UniGen and QuickSampler) for reaching a good compromise between execution time and uniformity guarantees, with empirical evidence on SAT benchmarks. In the context of highly-configurable software systems (e.g., Linux), it is unclear whether UniGen and QuickSampler can scale and sample uniform software configurations. In this paper, we perform a thorough experiment on 128 real-world feature models. We find that UniGen is unable to produce SAT solutions out of such feature models. Furthermore, we show that QuickSampler does not generate uniform samples and that some features are either never part of the sample or too frequently present. Finally, using a case study, we characterize the impacts of these results on the ability to find bugs in a configurable system. Overall, our results suggest that we are not there: more research is needed to explore the cost-effectiveness of uniform sampling when testing large configurable systems.

Original languageEnglish
Title of host publicationProceedings - 2019 IEEE 12th International Conference on Software Testing, Verification and Validation, ICST 2019
Place of PublicationXian, China
Pages240-251
Number of pages12
ISBN (Electronic)9781728117355
DOIs
Publication statusPublished - 1 Apr 2019
Event12th IEEE International Conference on Software Testing, Verification and Validation, ICST 2019 - Xi'an, China
Duration: 22 Apr 201927 Apr 2019

Publication series

NameProceedings - 2019 IEEE 12th International Conference on Software Testing, Verification and Validation, ICST 2019

Conference

Conference12th IEEE International Conference on Software Testing, Verification and Validation, ICST 2019
CountryChina
CityXi'an
Period22/04/1927/04/19

Keywords

  • Software product lines
  • Variability modeling
  • SAT
  • Configurable systems
  • Software testing
  • Uniform sampling

Fingerprint Dive into the research topics of 'Uniform Sampling of SAT Solutions for Configurable Systems: Are We There Yet?'. Together they form a unique fingerprint.

  • Cite this

    Plazar, Q., Acher, M., Perrouin, G., Devroey, X., & Cordy, M. (2019). Uniform Sampling of SAT Solutions for Configurable Systems: Are We There Yet? In Proceedings - 2019 IEEE 12th International Conference on Software Testing, Verification and Validation, ICST 2019 (pp. 240-251). [8730148] (Proceedings - 2019 IEEE 12th International Conference on Software Testing, Verification and Validation, ICST 2019).. https://doi.org/10.1109/ICST.2019.00032