MASc Seminar: Strong Induction in Hardware Model Checking Export this event to calendar

Wednesday, July 24, 2019 — 11:00 AM EDT

Candidate: Hari Govind Vediramana Krishnan

Title: Strong Induction in Hardware Model Checking 

 

Date: July 24, 2019

Time: 11:00 AM

Place: EIT 3145

Supervisor(s): Ganesh, Vijay - Gurfinkel, Arie

 

Abstract:

Symbolic Model checking is a widely used technique for automated verification of both hardware and software systems. Unbounded SAT-based Symbolic Model Checking (SMC) algorithms are very popular in hardware verification. The principle of strong induction is one of the first techniques for SMC. While elegant and simple to apply, properties as such can rarely be proven using strong induction and when they can be strengthened, there is no effective strategy to guess the depth of induction. It has been mostly displaced by techniques that compute inductive strengthenings based on interpolation and property directed reachability (PDR). In this thesis, we prove that strong induction is more concise than induction. We then present kAvy, an SMC algorithm that effectively uses strong induction to guide interpolation and PDR-style incremental inductive invariant construction. Unlike pure strong induction, kAvy uses PDR-style generalization to compute and strengthen an inductive trace. Unlike pure PDR, kAvy uses relative strong induction to construct an inductive invariant. The depth of induction is adjusted dynamically by minimizing a proof of unsatisfiability. We have implemented kAvy within the Avy Model Checker and evaluated it on HWMCC instances. Our results show that kAvy is more effective than both Avy and PDR, and that using strong induction leads to faster running time and solving more instances. Further, on a class of benchmarks, called shift, kAvy is orders of magnitude faster than Avy, PDR and pure strong induction.

Location 
EIT
Room 3145
200 University Avenue West

Kitchener, ON N2L 3G1
Canada

S M T W T F S
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
  1. 2019 (214)
    1. December (1)
    2. November (1)
    3. October (3)
    4. September (19)
    5. August (26)
    6. July (40)
    7. June (24)
    8. May (23)
    9. April (35)
    10. March (25)
    11. February (9)
    12. January (10)
  2. 2018 (150)
    1. December (13)
    2. November (25)
    3. October (12)
    4. September (13)
    5. August (7)
    6. July (23)
    7. June (9)
    8. May (6)
    9. April (9)
    10. March (16)
    11. February (10)
    12. January (7)
  3. 2017 (212)
  4. 2016 (242)
  5. 2015 (242)
  6. 2014 (268)
  7. 2013 (192)
  8. 2012 (31)