Automated System Verification (2020/2021)

Course code
4S003252
Name of lecturer
Matteo Cristani
Coordinator
Matteo Cristani
Number of ECTS credits allocated
6
Academic sector
INF/01 - INFORMATICS
Language of instruction
Italian
Location
VERONA
Period
I semestre dal Oct 1, 2020 al Jan 29, 2021.

Lesson timetable

Go to lesson schedule

Learning outcomes

The course aims at providing the foundational concepts of verification on both hardware and software systems, for example by using temporal logic and semantic of traces to represent their behavior. At the end of the course the student (1) will have acquired the technical knowledge of model-based verification (model-checking), (2) will be able to use those knowledge to model behavior of specific hardware and software systems and (3) will be able to continue, potentially in an autonomous way, to study and research the field of technologies for formal verification of systems.

Syllabus

System Verification:
the model checking approach
Modelling Concurrent Systems:
transition Systems,
parallelism and communication,
state-space explosion 

Linear-Time Properties:
safety and invariants,
liveness,
fairness 

Linear Temporal Logic:
syntax,
semantics,
model checking in LTL
Computation Tree Logic:
syntax,
semantics,
expressiveness of CTL vs. LTL,
symbolic model checking,
CTL∗
Equivalences and Abstraction:
bisimulation
bisimulation and equivalence in CTL*

Reference books
Author Title Publisher Year ISBN Note
Christel Baier and Joost-Pieter Katoen Principles of Model Checking MIT press 2008

Assessment methods and criteria

The exam will be in written form, with the possibility, on demand, and under specified conditions, of an oral integration. Student with an evaluation over 24/30 shall be permitted to require an oral integration. With no such request, mark on written exam will be final.

Written exam will be articulated in two parts. In the first part, the students will be required to discuss the topics given in the lecture with a question for each of the major topics: Modeling concurrency, properties of linear time, linear temporal logic, computation tree logic, CTL*, equivalence and abstraction.
The applied part of the written exam, again for a 50% of the total mark, will check the competence of the students about transition systems, temporal logic model checking, bisimulation, abstraction.
The first part of the oral exam will consist in questions regarding the same topics of the the first part of the written exam. Second part of the oral exam, instead, will consist in a single exercise, on request of the instructor.
Evaluation of the written exam will take into account:

- width of the knowledge of transition systems, temporal logic, abstraction models;
- correctness of the exercises
- completeness of the knowledge of the topics

On the other hand, the oral exam will be evaluated based on:

-analytical completeness in answers to questions;
- competence on the specified topics of the programme;
- correctness and width of the answers.