Overview

Boolean Satisfiability, abbreviated SAT, appears in formal verification as the basis for checking properties of hardware designs. The evidence describes SAT-based methods as a robust solution in formal verification, with SAT-based Bounded Model Checking (BMC) identified as a prominent technique whose performance improvements made it suitable for larger-scale designs.[C1]

Use in property checking

In the described verification setting, the intended behavior of a design is formalized using safety properties. Restricting checking to safety properties leads to bounded properties that can be checked efficiently using a SAT solver.[C2]

A synchronous circuit is modeled as a finite-state machine with inputs, outputs, states, initial states, an output function, and a next-state function. Its transition relation can be written as:

T(s, s') = exists x in B^n : s' == Delta(x, s)

A safety property f = AG(phi) is translated into a Boolean function [[f]]_t that checks the validity of phi at a time point t. The translation is constructed so that a satisfying assignment of [[f]]_t corresponds to a counterexample of phi.[C3]

SAT instances in interval property checking

Interval property checking (IPC) searches for counterexamples by solving a SAT instance that combines an unrolled transition relation with the Boolean encoding of the property. In the provided formalization, the transition relation is unrolled over a bounded interval and connected to a single instantiation of the translated property:

AND_{i=0..c} T(s_{t+i}, s_{t+i+1}) AND [[f]]_t

The result is a SAT problem whose satisfying assignments indicate counterexamples for the checked safety property.[C4]

Relationship to BMC and IPC

SAT-based BMC is presented as one of the prominent SAT-based formal verification techniques. IPC is contrasted with original BMC: IPC verifies only safety properties and uses an arbitrary starting state rather than the initial state used in BMC. A property that holds from an arbitrary state also holds from any reachable state, giving exhaustive verification under that condition.[C5]

Because IPC can start from unreachable states, it can produce false negatives: counterexamples that arise only from unreachable states. The evidence states that such false negatives must be removed by adding invariants that restrict the starting state.[C6]

Practical significance

Within the evidence, SAT is not treated as an isolated topic but as an enabling mechanism for formal verification workflows. SAT solvers are used to efficiently check bounded safety properties, and SAT instances encode both the transition behavior of the design and the condition whose satisfaction corresponds to a counterexample.[C2][C4]