Systems Verification Lab
News
- 26/05/2019: Project for 2018/2019 is available in the relative section below.
- 13/05/2019: On Thursday 16/05/2019 there will be two extra lectures given as seminars of Dr. Matteo Rucco. The first one is scheduled at 11:00am in Room AB1 and the second one is scheduled at 04.30pm in Room AB1 as well.
- 07/04/2019: The calendar of the course has been updated, please take note of the new dates in section “Lectures” below.
- 04/04/2019: The Lecture of Wednesday 10/04/2019 is cancelled because the teacher is in the evaluation committee of Bsc and MSc graduation.
- 29/03/2019: The Lecture of Wednesday 03/04/2019 will take place in Room AB1 of Polo Lodovici instead of the usual Room LA1.
- 04/03/2019: From Monday 11/03/2019 on the lecture of Mondays will be on Room LA2 of Polo Lodovici.
- 04/03/2019: The course officially starts Monday 04/03/2019 at 2pm in Room AB1 of Polo Lodovici.
General Info
Teacher:
ESSE3 Link
Lectures schedule:
- Monday 2pm - 4pm - (from 11/03/2019) Room LA2 of Polo Lodovici
- Wednesday 9am - 11am - Room LA1 of Polo Lodovici
Webex Room for Lecture Streaming
Office hours:
- Luca Tesei's office hours are specified here, look at the notices for any variation. The place is Luca Tesei's office, 1st floor, Polo Lodovici, via Madonna delle Carceri 9, Camerino.
Acronym:
- The course official acronym is SVL1819
Course Objectives
KNOWLEDGE AND UNDERSTANDING
At the end of the course, the student should be able to:
- Understand the concept of verification of a concurrent system and the main issues related to the model checking problem of reactive systems
- Define the formalism of transitions systems for modelling concurrent systems also using more higher level concepts such as state variables and communication channels
- Illustrate the concepts of parallel composition, interleaving, synchronous communication, synchronised product between transition systems
- Have knowledge of the type of properties that can be expressed on a trace of a transition system: safety, liveness or mixed properties
- Illustrate the concept of fairness of actions
- Illustrate the syntax and the semantics of Linear Time Logic (LTL)
- Illustrate the syntax and the semantics of Computation Tree Logic (CTL)
- Understand the issues related to time critical systems and the need of expanding non-deterministic formalisms with time
- Understand the concepts of clock variables, timed automata, timed paths, divergence and zenoness
- Illustrate the syntax and the semantics of Timed Computation Tree Logic (TCTL)
- Understand the concept of probabilistic and stochastic systems and their verification
- Illustrate the definition of Discrete Time Markov Chains (DTMC), Markov Decision Processes (MDP) and Continuous Time Markov Chains (CTMC)
- Illustrate the syntax and the semantics of Probabilistic Computation Tree Logic (PCTL) and Continuous Stochastic Logic (CSL)
APPLYING KNOWLEDGE AND UNDERSTANDING
At the end of the course, the student should be able to:
- Model a concurrent reactive system using a component-based approach
- Define finite state machines with a suitable synchronisation interface using both a graphical language and a textual language
- Formally express properties of reactive systems using LTL and CTL formulas
- Apply the concept of fairness to real cases
- Use a tool for the model checking of reactive systems
- Use the formalism of Timed Automata for modelling real-time systems
- Use the tool UPPAAL for verifying real-time systems
- Use the formalisms of DTMC, MDP and CTMC for modelling probabilistic or stochastic systems
- Use the tool PRISM for verifying probabilistic or stochastic systems
MAKING JUDGEMENTS
At the end of the course, the student should be able to:
- Identify the best model suitable for describing a system using a given formalism
COMMUNICATION SKILLS
At the end of the course, the student should be able to:
- Write a clear report on the modelling and analysis of a system under study using a formal style
LEARNING SKILLS
At the end of the course, the student should be able to:
- Search the scientific literature for specific advances in formalisms and tools aimed at modelling and verifying reactive, real-time, probabilistic and stochastic systems
- Autonomously understand and learn to use new features added to tools for modelling and verifying reactive, real-time, probabilistic and stochastic systems
Course Contents
System verification: main concepts. Definition and characteristics of model checking. Transition Systems. Program Graphs and Channel Systems. Parallelism and communication. The state-space explosion problem. Linear-time properties: safety, liveness, fairness. Linear Temporal Logic (LTL). Computation Tree Logic (CTL). Model checking of reactive systems with a software tool. Real-time systems and timed formalisms. Timed Automata. Timed Computation Tree Logic (TCTL). The UPPAAL Tool. Probabilistic and Stochastic Systems. Discrete Time Markov Chains (DTMC), Markov Decision Processes (MDP) and Continuous Time Markov Chains (CTMC). Probabilistic Computation Tree Logic (PCTL) and Continuous Stochastic Logic (CSL). The tool PRISM.
Lectures
- 18/03/2019 - Watch the Lecture, Download the Lecture, UPPAAL Models, Suggested exercise: model in UPPAAL the supermarket booking system and the train-gate system, SPIN Models (Uncompleted), Suggested exercise: complete the specification of the Alternate Bit Protocol in PROMELA.
- 03/04/2019 - Watch the Lecture, Download the Lecture
- 29/04/2019 - Watch the Lecture, Download the Lecture
- 06/05/2019 - Watch the Lecture, Download the Lecture
- 08/05/2019 - Watch the Lecture, Download the Lecture
- 29/05/2019 - Watch the Lecture, Download the Lecture, PRISM Code, Slides Long-run Probability, Notes
Material
Verification Tools
Reactive Systems
Transition Systems and Modelling Languages for Reactive Systems
Linear Time Properties
Linear Time Logic (LTL)
Computation Tree Logic (CTL)
Timed Systems
Timed Automata
Probabilistic Systems
Markov Chains
Exercises
Exercises with (some) solutions
- Regular Properties, LTL and CTL - NOTE 1: some of the exercises on Regular Properties and on LTL require to calculate the product between the transition system and the non-Deterministic Buechi Automaton (NBA) corresponding to the formula - ignore that part and justify your answer by providing the counterexample without providing the product construction. NOTE 2: some of the exercises on CTL require to show the steps of the Sat algorithm for deciding the satisfaction of the formula by a state or by a transition system: ignore this request and provide, if possible, an informal justification; if not possible ignore the exercise.
Textbooks
Main:
- Christel Baier, Joost-Pieter Katoen, “Principles of Model Checking”, The MIT Press, 2008.
Reading:
- Vidyadhar G. Kulkarni, “Modeling and Analysis of Stochastic Systems, Third Edition”, Chapman and Hall/CRC, 2016.
Reference books
- Michael Huth, Mark Ryan, “Logic in Computer Science”, Second Edition, Cambridge University Press, 2004. ISBN: 9780521543101.
- Luca Aceto, Anna Ingólfsdóttir, Kim Guldstrand Larsen, Jiri Srba, “Reactive Systems”, Cambridge University Press, 2007.
Project
Exams
Exam Dates A.Y. 2018/2019 (Written Test Dates)
- 06/02/2019, 3:00pm, Room LA1 - no students.
- 20/02/2019, 3:00pm, Room LA1 - no students.
- 13/06/2019, 3:00pm, Room AB1 - no students.
27/06/2019, 3:00pm, Room TBA, 28/06/2019, 11:00am, Room AB1 Polo Lodovici - Text, Text with Solutions- 17/07/2019, 3:00pm, Room AB2 Polo Lodovici - Text, Text with Solutions
- 12/09/2019, 3:00pm, Room AA1 Polo Lodovici - Text, Text with Solutions
- 26/09/2019, 3:00pm, Room AA1 Polo Lodovici, please register on ESSE3 to the Partial Exam “SVL1819 Sess. VII - Written Test” before 20/09/2019
- 24/03/2020, 3:00pm, Room TBA, please register on ESSE3 to the Partial Exam “SVL1819 Sess. VIII - Written Test” before 20/03/2020
Exam rules
The exam consists of a written test, containing open-answer questions (exercises), together with one project, realised with the tools introduced in the course (see section “Project” above). The Written Test and the Project are two independent Partial Exams (see the exam sessions in the ESSE3 career system) and can be passed in different exam sessions. The final grade, which is the average of the grades of the two Partial Exams, can be obtained and registered only if both the Partial Exams have been passed with a grade of at least 18/30.
Registration for the written tests must be done using the Student Career System ESSE3 here. Please note that the registration deadline is usually 3 working days before the written test date. BSc students or MSc students who did not select the Intelligent and Adaptive Systems (IAS) Curriculum will not be able to register for the written test until they communicate to the Secretary Office (Tiziana Jajani c/o Student Secretary Office, Opening Hours) their choice to attend to this course, code [ST1192] SYSTEMS VERIFICATION LAB. During the exercise sessions throughout the course samples of the written test questions will be presented with solutions. During the written test students can consult a hand-written A4 paper of their production for reference.
Instructions for Sending Projects
Students must create a folder in Google Drive, using the Google account associated to their email name.surname@studenti.unicam.it
The folder must contain all the files relative to the project and a written report, in English, which describes all the phases of the developing of the project. The use of screenshots is encouraged to show, within the report, the runs and the results of the project.
The folder must be named
SVL1819-Project-APP-X-Surname-Name
where X is the number of the exam session (Appello) as specified for each date of the written test above.
The folder must be shared (using Google Drive facilities) with luca.tesei@unicam.it and francesco.tiezzi@unicam.it by 11.59pm of the day specified for the Partial Exam “SVL1819 Sess. X - Project Deliver” relative to Session X. Students should also register for this Partial Exam within the day before on ESSE3.
Exam Results
- The results will be communicated through this site or by email (depending on the number of students).
- Contextually to the communication of the results, students will be invited to accept or reject the evaluation.
- A positive evaluation (>=18/30) of each Partial Exam (Written Test and Project) remains valid for one year or until the student retries the Partial Exam.
- If both grades (Written Test and Project) are accepted, the final grade will be registered in ESSE3.
