Aleksandar Zeljić, Peter Backeman, Christoph M. Wintersteiger, Philipp Rümmer
6 min
Solving floating-point arithmetic (FPA) constraints is a critical but computationally expensive task in software verification, model checking, and test-case generation. Because standard bit-blasting techniques often lead to prohibitively large propositional formulas, researchers have turned to approximation-based solving. This approach involves solving a simplified version of the original problem and then iteratively refining the solution until it satisfies the original constraints. However, the design space for these approximations—including how to encode the problem, how to reconstruct models, and how to refine precision—is vast and lacks a unified experimental platform.
UppSAT is an open-source, Scala-based framework designed to serve as a sandbox for exploring these approximation techniques. It implements a systematic approximation-refinement framework as an abstract SMT solver. By decoupling the high-level logic of approximation from the low-level execution, UppSAT allows users to plug in off-the-shelf SMT solvers as back-ends. The framework is built around a modular architecture where users define specific traits for the approximation context, formula encoding/decoding, model reconstruction, and refinement strategies. This design enables researchers to quickly prototype and compare different approaches, such as reducing floating-point precision, mapping FPA to real arithmetic, or translating constraints into fixed-point arithmetic.
The authors demonstrate the utility of UppSAT by implementing and evaluating three distinct approximation strategies for FPA. These include:
By providing a uniform interface for these methods, UppSAT allows for a systematic comparison of how different encodings and back-end solvers affect the overall performance and correctness of the verification process.
We consider the problem of solving floating-point constraints obtained from software verification. We present UppSAT --- a new implementation of a systematic approximation refinement framework [ZWR17] as an abstract SMT solver. Provided with an approximation and a decision procedure (implemented in an off-the-shelf SMT solver), UppSAT yields an approximating SMT solver. Additionally, UppSAT includes a library of predefined approximation components which can be combined and extended to define new encodings, orderings and solving strategies. We propose that UppSAT can be used as a sandbox for easy and flexible exploration of new approximations. To substantiate this, we explore several approximations of floating-point arithmetic. Approximations can be viewed as a composition of an encoding into a target theory, a precision ordering, and a number of strategies for model reconstruction and precision (or approximation) refinement. We present encodings of floating-point arithmetic into reduced precision floating-point arithmetic, real-arithmetic, and fixed-point arithmetic (encoded in the theory of bit-vectors). In an experimental evaluation, we compare the advantages and disadvantages of approximating solvers obtained by combining various encodings and decision procedures (based on existing state-of-the-art SMT solvers for floating-point, real, and bit-vector arithmetic).
Sam: That seems useful for safety-critical systems — like flight control software, where the math is complex but the stakes are high.
Alex: It's a meaningful improvement for exactly those contexts. The paper shows that by starting with lower-precision versions, the system sidesteps the computational explosion of full bit-blasting in many cases. You only pay that cost when the simpler approach genuinely can't confirm correctness.
Sam: How does the reconstruction step actually work, though? If you have an approximate answer, how do you turn it into a precise one?
Alex: The paper describes a technique they call equality-as-assignment. Here's the idea: if the system knows that two things must be equal — say, the left side of an equation equals the right side — and it already knows the value on one side, it can simply assign that value to the other side. This lets it propagate correct, precise values through the formula, patching up the rounding errors that the approximation introduced.
Sam: So it's using the structure of the equations themselves as a guide for fixing the imprecision.
Alex: Precisely. The system uses a tree-like representation of the formula — where each operation branches off from the ones before it — to make sure those corrections flow through in the right order without breaking anything.
Sam: That's a neat mechanism. But I'm guessing this approach has limits. What happens when there genuinely is no solution to the formula?
Alex: That's the most significant current limitation. When a problem has no solution, a verification tool needs to do more than just fail to find one — it needs to produce a formal proof of why no solution can exist. Right now, UppSAT handles that with a fairly blunt, uniform approach that isn't very efficient. It's good at finding answers when they exist, but proving that a problem is fundamentally unsolvable is a harder challenge the current framework hasn't fully solved.
Sam: It's like being able to solve a jigsaw puzzle, but not being able to prove that certain pieces simply can't fit together.
Alex: That's a fair way to put it. The authors suggest that future versions should use the information from failed proof attempts to guide the refinement more intelligently — so instead of just increasing precision across the board and trying again, the system could pinpoint exactly where the conflict lies.
Sam: And the modular design would make that kind of upgrade easier to add later?
Alex: That's the intention. The team also points toward using machine learning to help the system automatically select the best approximation strategy for a given problem, based on the structure of the formula it's looking at. Rather than a tool an engineer has to configure manually, the vision is something closer to a self-tuning system.
Sam: So the current version is a solid foundation — good at finding solutions efficiently — and the next phase is about making it equally capable when the answer is that no solution exists.
Alex: That's a fair summary. Formal verification has always struggled with the sheer scale of floating-point arithmetic. UppSAT's contribution is showing that an iterative, modular approximation approach can make that problem significantly more tractable — and laying the groundwork for more intelligent solvers down the line.
Sam: It's a careful, incremental approach to a problem that really matters in safety-critical software.
Alex: It is. And that kind of methodical progress — building a flexible framework others can extend — is often how the field moves forward. Thanks for listening to ResearchPod.