Efficient Formal Verification of Liveness and Freedom from Deadlock

Liveness properties are crucial to the variety of design types – for example, systems containing arbiters (where we check for requests are eventually acknowledged), critical FSMs (Finite State Machines) (a desirable state is eventually reached), transaction queuing (FIFOs/Queues) (data is eventually drained), clock gating to save dynamic power consumption (design should eventually not become busy) and LRU (Least Recently Used) cache replacement algorithms in cache blocks (every entry has a path to LRU).

Safety properties typically contain finite length counterexample depicting a failure condition, whereas liveness properties contain an infinite-length counterexample (a prefix followed by a lasso-shaped suffix), typically known as livelock. Wherever there is a scope for liveness verification, underlying there exists scope for verification of freedom from deadlock as well, as it is a weak form of liveness, i.e. absence of livelock can guarantee the absence of deadlocks, however livelock detected in a design may not be a deadlock. Liveness verification is more challenging and known to be significantly less scalable in practice despite the variety of algorithms available to solve them.

In this paper, we will discuss the strategies for efficient treating of liveness and freedom from deadlock using formal verification, especially to go beyond bug hunting to achieve full proof/exhaustive verification to establish the correctness of the design.

These strategies include:

Bounded liveness vs unbounded liveness verification. The bounded liveness verification is much more scalable than unbounded version since it does not entail the overhead of state repetition logic and for finite designs it is complete given an adequately large time bound. If we observe a proof or unreachable condition, then it is also valid for unbounded version.
Application of assume guarantee paradigm in liveness verification space – i.e., decompose the liveness problems into more sub-problems in order to build up a complete proof for original liveness problem. In this case, we prove the original liveness problem under a set of fairness assumptions on a smaller model (containing core part in it) with abstracting the connections, and then separately verify that the fairness assumptions used in the former will be satisfied at all by the rest of the model. Further, assumptions on low priority requests get their fair chance when they compete with high priority requests to avoid the starvation conditions.

Constrain the model using high impact input conditions in order to bring down the complexity, which is an under-approximation. If we observe a failure condition then it is also valid on original problem.
Abstractions (black-boxing, disconnecting design interfaces, relaxing the fairness assumptions and design constraints) which over-approximate the state-space of the original design hence guaranteeing proof of a property if obtained on the abstracted design.

Auto identification of deadlock sources using external interfaces or FSM design specifications and their conversion to safety properties.

Finally, tuning the knobs of design configuration (parameterization) to a lowest complex configuration such that proving the design with this configuration is still complete and can be treated as design robust confidence measure.

This talk will cover:

• Strategies for Verifying liveness problems using formal verification
• Auto identification of deadlock sources using external interfaces and their verification
• The engine perspective on these problems.