Skip to content
STIMSMITH

Counterexample Generation

Concept WIKI v1 · 5/26/2026

Counterexample generation is the process, illustrated in UCLID5-based formal verification, of turning a satisfiable negated verification condition into a concrete sequence of model actions that violates the intended property. Such counterexamples help diagnose design errors, modeling inaccuracies or over-abstraction, and incorrectly stated verification conditions.

Definition

Counterexample generation occurs when a formal verification workflow checks a verification condition by asking an SMT solver to satisfy the negation of the desired property, and the solver returns that the formula is satisfiable. In the UCLID5 workflow described in the evidence, the solver supplies concrete values for all data elements in the formula, including uninterpreted functions, and UCLID5 uses those values to construct a counterexample: a sequence of actions that could occur in the model and violate a verification condition. [counterexample-generation-from-satisfiability]

Role in a UCLID5 verification flow

Given a model and verification script, UCLID5 generates verification conditions as formulas in logics that support the theories used by the model. These formulas are typically negations of the properties the user wants to verify, and UCLID5 invokes an SMT solver to analyze them. [verification-condition-generation]

The solver can return three outcomes:

  • Unsatisfiable: because the checked formula is typically the negation of the property, unsatisfiability indicates that the desired verification condition holds.
  • Satisfiable: the solver provides concrete satisfying values, which typically implies that some verification condition failed; these values are used for counterexample generation.
  • Indeterminate: the solver cannot find a satisfying solution but also cannot prove unsatisfiability, which typically indicates that the model is too complex or needs reasoning beyond what the solver can provide. [solver-outcomes]

Diagnostic meaning

A generated counterexample is not automatically proof of a design bug alone. In the cited UCLID5 setting, counterexamples are important indications of one of three situations: a true error in the design, an inaccurate or overly abstract model, or an improperly expressed verification condition. [counterexample-diagnostics]

Interaction with abstraction

The evidence emphasizes that formal models involve choices about data types and abstraction level. A general rule stated for the UCLID5 modeling context is to use the most abstract model that still captures the properties required for correctness. Counterexamples can therefore serve as feedback not only about the implementation being modeled, but also about whether the abstraction is too coarse or otherwise inaccurate. [model-abstraction]

Example context from the evidence

The cited report applies this workflow to formal verification of pipelined Y86-64 microprocessors using UCLID5. In that work, UCLID5 generated verification conditions and used the Z3 SMT solver. [uclid5-z3-context]

LINKED ENTITIES

2 links
UCLID5 generates_counterexamples
Z3 example_smt_solver_used_with_uclid5

CITATIONS

6 sources
6 citations
[1] verification-condition-generation Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[2] counterexample-generation-from-satisfiability Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[3] solver-outcomes Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[4] counterexample-diagnostics Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[5] model-abstraction Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[6] uclid5-z3-context Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5