Grant: Engage Grants Program
McGill University
$23,750.00
Semi-formal Verification Based on Assertion Checkers
FY 2010-11
Summary
In this project, we will explore the realization of a new type of semi-formal verification. Based on our efficient
representation of assertion checkers with non-deterministic automata (NDA) and the program for efficient
traversal of NDAs, we will build a complete semi-formal verification tool flow. Our tool has a potential of
being more efficient than the similar tools because of the unique generation of NDAs as well as the NDA
traversals, which act as ""verification beacons"" to guide towards the cases of more importance for functional
verification. Such beacon trajectories will then be augmented with bounded model checking constraint solvers
that will justify the sequences, i.e., provide the sequences of primary inputs that lead to the given assertion
symbol sequences produced in the first two phases.
Because we can generate two types of automata: failing and acceptance ones, the same framework is used for
finding the functional test sequences (by covering acceptance automata) as well as for founding the
counterexamples (by providing sequences of primary inputs leading to the firing of failure automata). These
sets of capabilities can then be employed in a variety of scenarios in formal and dynamic verification, not to
mention the combination of the two.
The completely new components, those of constraint solving by model checking will be dealt in two ways -
first, by using the open source tools such as NuSMV, and then by a commercial tool. The differences between
the two will be thoroughly benchmarked and the full tool flows will be build around both alternatives. The
flows will be applied to the industrial case studies, provided by our partner.
Program
Engage Grants Program
Recipient
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
401102-2010
Name nom
Zilic, Zeljko
Department département
Electrical and Computer Engineering
Organization id
61
Institution établissement
McGill University
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2010
Competition year année de concours
2010
Award amount
23750
Program id
EGP
Program name en
Engage Grants Program
Program name fr
Programme de subventions d'engagement partenariat
Group en
Research partnerships programs
Group fr
Programmes de partenariat
Committee code
1552
Committee name en
Quebec Internal Decision Committee
Committee name fr
Comité de décision interne pour le Québec
Area of application code
513
Area of application group en
Manufacturing processes and products
Area of application group fr
Procédés et produits industriels
Area of application en
Electrical and electronic machinery and equipment (including computer hardware)
Area of application fr
Machinerie et équipement électriques et électroniques (y compris matériel informatique)
Research subject code
2504
Research subject group en
Electrical and electronic engineering
Research subject group fr
Génie électrique et électronique
Research subject en
Integrated circuits
Research subject fr
Circuits intégrés
Partie
1
Nb partie
1
Application title
Semi-formal Verification Based on Assertion Checkers
Keyword
NSERC
Application summary
In this project, we will explore the realization of a new type of semi-formal verification. Based on our efficient
representation of assertion checkers with non-deterministic automata (NDA) and the program for efficient
traversal of NDAs, we will build a complete semi-formal verification tool flow. Our tool has a potential of
being more efficient than the similar tools because of the unique generation of NDAs as well as the NDA
traversals, which act as ""verification beacons"" to guide towards the cases of more importance for functional
verification. Such beacon trajectories will then be augmented with bounded model checking constraint solvers
that will justify the sequences, i.e., provide the sequences of primary inputs that lead to the given assertion
symbol sequences produced in the first two phases.
Because we can generate two types of automata: failing and acceptance ones, the same framework is used for
finding the functional test sequences (by covering acceptance automata) as well as for founding the
counterexamples (by providing sequences of primary inputs leading to the firing of failure automata). These
sets of capabilities can then be employed in a variety of scenarios in formal and dynamic verification, not to
mention the combination of the two.
The completely new components, those of constraint solving by model checking will be dealt in two ways -
first, by using the open source tools such as NuSMV, and then by a commercial tool. The differences between
the two will be thoroughly benchmarked and the full tool flows will be build around both alternatives. The
flows will be applied to the industrial case studies, provided by our partner.