Deciding floating-point logic with abstract conflict driven clause learning

Journal article

We present a bit-precise decision procedure for the theory of floating-point arithmetic. The core of our approach is a non-trivial, lattice-theoretic generalisation of the conflict-driven clause learning algorithm in modern sat solvers to lattice-based abstractions. We use floating-point intervals to reason about the ranges of variables, which allows us to directly handle arithmetic and is more efficient than encoding a formula as a bit-vector as in current floating-point solvers. Interval reasoning alone is incomplete, and we obtain completeness by developing a conflict analysis algorithm that reasons natively about intervals. We have implemented this method in the mathsat5 smt solver and evaluated it on assertion checking problems that bound the values of program variables. Our new technique is faster than a bit-vector encoding approach on 80 % of the benchmarks, and is faster by one order of magnitude or more on 60 % of the benchmarks. The generalisation of cdcl we propose is widely applicable and can be used to derive abstraction-based smt solvers for other theories.

Authors: Brain, M; Silva, V; Griggio, A; Haller, L; Kroening, D

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Springer Verlag
• Journal: Formal Methods in System Design
• Volume: 45
• Issue: 2
• Pages: 213-245
• Publication date: 2014-01-01
• DOI: 10.1007/s10703-013-0203-7
• EISSN: 1572-8102
• ISSN: 0925-9856
• Keywords: SBTMR