Overview

Term-level modeling is a formal-verification modeling style in which values may be represented as uninterpreted terms. In the UCLID5 setting described for verifying pipelined Y86-64 microprocessors, uninterpreted data is identified as suitable for the term-level modeling demonstrated by Burch and Dill. These terms can be tested for equality, and they can be used together with uninterpreted functions whose behavior is arbitrary but consistent. [term-level-uninterpreted]

Role in hardware verification

In the cited UCLID5 verification flow, the modeled system combines a pipelined microprocessor with a sequential reference implementation, and the verification script describes the steps for Burch-Dill correspondence checking. For pipelined microprocessor verification, the hardware modeling aspects of UCLID5 are used: hardware is represented as state machines that compute a next state from the current state and then transition to that next state. [uclid5-verification-setting]

Within that setting, term-level modeling supports abstraction of hardware blocks. Uninterpreted functions can model blocks whose internal implementation details are not required for the proof, provided those blocks behave consistently in both the pipeline model and the sequential reference model. [hardware-block-abstraction]

Uninterpreted functions

A central mechanism in term-level modeling is the use of uninterpreted functions. UCLID5 treats such functions as arbitrary but consistent: for a function f over two arguments, if x₁ = x₂ and y₁ = y₂, then f(x₁, y₁) = f(x₂, y₂). This consistency property allows the verifier to reason about equality without requiring a concrete implementation of the function. [uninterpreted-function-consistency]

The evidence gives branch-decision logic as an example: whether a branch should be taken can be modeled as an uninterpreted function returning a Boolean value, with arguments including an enumerated function-code type and an uninterpreted condition-code type. [branch-decision-example]

Abstraction level

The UCLID5 modeling discussion emphasizes that different data types create choices about abstraction level. The stated general rule is to use the most abstract model that still captures the properties needed to guarantee correctness. In the Y86-64 pipeline verification work, different pipeline variants required different levels of abstraction. [abstraction-guideline]

Interaction with SMT-based verification

Given a model and a verification script, UCLID5 generates verification conditions expressed as formulas over the theories used by the model, typically as negations of the properties being checked. It then invokes an SMT solver; in the cited work, Z3 was used. The SMT solver may report the formula unsatisfiable, satisfiable, or indeterminate. A satisfiable result can provide concrete values for data elements, including uninterpreted functions, which UCLID5 uses to generate counterexamples. [smt-flow]