Automated System Verification (2017/2018)

Course code
4S003252
Name of lecturer
Andrea Masini
Coordinator
Andrea Masini
Number of ECTS credits allocated
6
Academic sector
INF/01 - INFORMATICS
Language of instruction
Italian
Period
II sem. dal Mar 1, 2018 al Jun 15, 2018.

Lesson timetable

Go to lesson schedule

Learning outcomes

The course aims to provide the theoretical basis of the main techniques of specification and verification of finite-state systems. In particular, with reference to transition systems, trace-based techniques, linear time logic and branched-time logic.

At the end of the course the student will have to demonstrate that he has acquired the knowledge necessary to formally reason on finite-state systems, with emphasis on the problems of correctness solved automatically (model-checking), through logical operational methods (traces) (temporal logics) and algorithms.

This knowledge will enable the student to: i) specify and formally test properties of correctness of simple systems presented as transition systems; ii) use time logics (linear and branched) for the specification of properties; iii) master semantic methods for temporal logics.

At the end of the course the student will be able to: i) compare temporal logics for the automatic verification and choose from these the most appropriate according to the context of use; when defining a verification process make the most appropriate design choices; ii) continue the studies independently in the context of formal verification.

Syllabus

System Verification:
the model checking approach
Modelling Concurrent Systems:
transition Systems,
parallelism and communication,
state-space xplosion 
Linear-Time Properties:
safety and invariants,
liveness,
fairness 
Linear Temporal Logic:
syntax,
semantics,
fairness,
model checking
Computation Tree Logic:
syntax,
semantics,
expressiveness of CTL vs. LTL,
fairness,
symbolic model checking,
CTL∗
Equivalences and Abstraction:
bisimulation ,
bisimulation and CTL∗ equivalence

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

Written exam (one and a half hours to perform the task).
In order to pass the exam, the student must have sufficient knowledge of all the topics (including the proofs of the theorems) and the ability to solve exercises similar to those seen during the lessons.
Better is the knowledge of course topics, better is the result of exam.

STUDENT MODULE EVALUATION - 2017/2018