Efficient Formal Verification of Liveness and Freedom from Deadlock2018-05-29T12:29:07+00:00

Verification Futures 2018

Conference:Verification Futures 2018 (click here to see full programme)
Speaker:Pradeep Kumar Nalla, Senior Test and Verification Engineer, Test and Verification Solutions Ltd
Presentation Title:Efficient Formal Verification of Liveness and Freedom from Deadlock
Abstract:As far as verification of hardware systems are concerned, two types of properties are prevalent. Verification properties may be classified as safety vs liveness. Safety properties assert that something bad never happens. Whereas, liveness properties assert that something good will eventually happen.

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.
Speaker Bio:Pradeep Kumar Nalla has 10 years of industry experience in the VLSI field and is currently a Senior Test and Verification Engineer at Test and Verification Solutions Ltd. Prior to joining T&VS he worked at IBM Server Processors group for ~6 years as part of the EDA-India Verification tools team, involved in development and support for the formal verification tool SixthSense. Before joining IBM he was with Atrenta India where he developed and supported the tool Sequential Equivalence Checking for Power optimisation. Pradeep obtained his Ph.D. (Efficient distributed bounded property checking) from the University of Tuebingen, Germany in 2008. He holds five US patents with seven filed and one under evaluation. He has co-authored 20 papers in various international conferences and workshops.