CISPA
Browse
dutra2018.pdf (295.31 kB)

Efficient sampling of SAT solutions for testing.

Download (295.31 kB)
conference contribution
posted on 2024-02-23, 11:04 authored by Rafael DutraRafael Dutra, Kevin Laeufer, Jonathan Bachrach, Koushik Sen

 

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.

History

Editor

Chaudron M ; Crnkovic I ; Chechik M ; Harman M

Journal

ICSE

Page Range

549-559

Publisher

ACM

BibTeX

@conference{Dutra:Laeufer:Bachrach:Sen:2018, title = "Efficient sampling of SAT solutions for testing.", author = "Dutra, Rafael" AND "Laeufer, Kevin" AND "Bachrach, Jonathan" AND "Sen, Koushik", editor = "Chaudron, Michel" AND "Crnkovic, Ivica" AND "Chechik, Marsha" AND "Harman, Mark", year = 2018, month = 1, journal = "ICSE", pages = "549--559", publisher = "ACM" }

Usage metrics

    Categories

    No categories selected

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC