Efficient Formal Verification of Liveness and Freedom from Deadlock 2018-03-15T11:23:38+00:00

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:

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. Auto identification of deadlock sources using external interfaces or FSM design specifications and their conversion to safety properties.
  6. 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.
Speaker Bio: Pending
T&VS NEWSLETTER SIGN-UP
The T&VS newsletters inform you about industry news, events and information from T&VS. No spam, we promise and it is always easy to unsubscribe.
We never share your information. Read our Privacy Statement
Interested in Formal Verification?
Then why not attend the TVS Formal
Verification Bootcamp training?
The 2-day Formal Verification Bootcamp is for design and verification engineers looking to enhance their knowledge of formal verification and to learn how to write effective assertions to find and fix bugs. The course is a mix of presentations and hands-on development exercises.
Bootcamp Enquiry Form
If you are interested in receiving additional information on the course then simply email Mike Bartley (TVS CEO and Course Leader) by entering your details below.
Interested in SystemC?
FREE SystemC UVM Library Now Available
The TVS SystemC UVM library closely mimics UVM but gives users a license free UVM-based verification environment.
Have your product requirements been successfully tested and implemented?
Find out how asureSIGN can help you implement a successful Requirements Driven Verification and Test Strategy by visiting asureSIGN or enter your details and we will be in touch.
Course Dates and Pricing
To receive additional information, including course dates and pricing, please contact our training team who will be happy to help.
Download Request
Please complete the following form then click 'submit' to access the download.
Presentation Request
Please complete the following form then click 'submit' to gain access to the presentations.
DOWNLOAD REQUEST
Please complete the following form and then click 'submit' to gain access to the download.
FREE QA ASSESSMENTS
Did you get what you were looking?

Let the testing experts help. We will run a FREE QA assessment which will include our top 5 recommendations to help maximise your testing.