Efficient Sampling of SAT Solutions for Testing

Author email: rtd@cs.berkeley.edu
Tool name: QuickSampler
Description: In software and hardware testing, generating multiple inputs which satisfy a given set of constraints is an important problem with applications in fuzz testing and stimulus generation. However, it is a challenge to perform the sampling efficiently, while generating a diverse set of inputs which satisfy the constraints. We developed a new algorithm QuickSampler which requires a small number of solver calls to produce millions of samples which satisfy the constraints with high probability. We evaluate QuickSampler on large real-world benchmarks and show that it can produce unique valid solutions orders of magnitude faster than other state-of-the-art sampling tools, with a distribution which is reasonably close to uniform in practice.
Bibtex: @inproceedings{dutra2018efficient, title={Efficient sampling of SAT solutions for testing}, author={Dutra, Rafael and Laeufer, Kevin and Bachrach, Jonathan and Sen, Koushik}, booktitle={2018 IEEE/ACM 40th International Conference on Software Engineering (ICSE)}, pages={549--559}, year={2018}, organization={IEEE} }
Link to public pdf: https://ieeexplore.ieee.org/abstract/document/8453122
Link to tool webpage: https://github.com/RafaelTupynamba/quicksampler/
Link to demo: Not provided by authors
Category: None
Year and Conference: 2018, ICSE
Terms of use