Verification Futures 2018
|Conference:||Verification Futures 2018 (click here to see full programme)|
|Speaker:||Pradeep Kumar Nalla, 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: