将位向量计数与采样能力集成到SMT求解器中,提升自动化推理效率。
CSB: A Counting and Sampling tool for Bit-vectors
- 通过位爆破技术将位向量公式转为CNF,调用现有计数/采样工具
- 支持精确与近似投影及非投影计数,以及几乎均匀和均匀采样
- 实测性能显著优于现有方法,适合形式化验证与安全分析场景
SMT求解器在自动化推理中已取得显著进展,因其在多个领域解决问题的有效性。随着SMT求解器的发展,人们开始关注其超出单纯可满足性的能力,类似于布尔可满足性求解器从可满足性扩展到计数与采样。本文探讨:能否依赖现代CNF模型计数器和CNF采样器,将现代SMT求解器扩展以处理位向量上的计数与采样问题?本研究的主要贡献是开发了一个高效且用户友好的工具csb,解决位向量理论中的多种建模计数与采样问题,包括精确与近似投影及非投影计数,以及几乎均匀和均匀类似采样。对于精确计数、投影计数和均匀采样,csb使用位爆破技术将位向量公式转换为CNF公式,再调用CNF模型计数器或采样器进行计算。实验表明,该方法在性能上显著优于现有方法。
原文摘要 · Abstract (English)
Satisfiability modulo theory (SMT) solvers have significantly advanced automated reasoning due to their effectiveness in solving problems across various fields. With the advancement in SMT solvers, there is growing interest in exploring capabilities beyond mere satisfiability, similar to the progression observed in Boolean satisfiability solvers that expanded into counting and sampling. In this study, we investigate the following question: Can we rely on modern CNF model counters and CNF samplers to extend modern SMT solvers to handle the problems of counting and sampling over bit-vectors? The main contribution of this work is the development of an efficient and user-friendly tool, csb, that solves a bunch of problems around model counting and sampling on the theory of bit-vectors, namely exact and approximate projected and non-projected model counting, along with the almost-uniform and uniform-like sampling. In the case of exact counting, projected counting, and uniform sampling. Our tool csb converts the bit-vector formula into a CNF formula using bit-blasting techniques before applying CNF model counters or samplers to perform counting or sampling. Our experiments demonstrate significant performance improvements over existing methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。