Software Synthesis and Verification

Course code: ITI8531
Link: http://courses.cs.ttu.ee/pages/ITI0130

Lecturer: prof. Jüri Vain
Contact: juri.vain ätt ttu.ee, ICT-418

Lab assistant: Deepak Pal
Contact: deepak.pal ätt ttu.ee,

Previous courses: 2014

Time and place

Lectures: Thursdays 10:00, ICT-A1
Labs: Thursdays 12:00, ICT-122 - Deepak Pal

New!
Exams:

• Thursday May 1, 10:00, room ICT-A2
  
• Thursday May 8, 10:00, room ICT-A2

Lecture plan

• Lecture 1: Introduction
• Lecture 2: Modelling state transition systems
• Lecture 3: Temporal logic CTL*
• Lecture 4: CTL model checking
• Lecture 5: Timed automata and TCTL model checking
• Practicing for Test 1 (see Exercises 1 below)
• Test 1: Model checking (15.03.2018)
  • Exercises: Model checking
• Lecture 7.1: Program specifications
• Lecture 7.2: Proving partial correctness of programs
• Lecture 8: Proof techniques (1): derived rules, backwards proof, annotations
• Lecture 9: Proving total correctness of while-programs
• Lecture 14: Verifying nondeterministic and parallel programs
• Practicing for Test 2 (26.04.2018): Deductive verification of non-deterministic and parallel programs
  • Genzen 1st order calculus: Genzen 1st order sequent calculus (proof rules)
• Test 2 (03.05.2018, 12.00): Deductive verification of sequential, non-deterministic and parallel programs
• Lecture 8: Program synthesis I
• Lecture 9: Program synthesis II
• Test 3 (17.05.2018): Program synthesis

Labs

• Lab 1: Introduction to modelling in UPPAAL
  • Slides: UPPAAL introduction
  • Model: Light Controller Model
  • Query: Light Controller Query
  • For More reading, refer below links:
    • UPPAAL website
    • Small tutorial on UPPAAL
    • Tutorial on UPPAAL

• Lab 2: Validation (simulation) and verification (automatic model-checking) in UPPAAL
  • Slides: Model Checking introduction
  • Model: ATM System Model
  • Query: ATM System Query

• Lab 3: Understanding of Clocks and State Space Explosion in UPPAAL
  • Slides: Uppaal Modelling Language
  • Model: JobShop Model with three possible scenarios
  • Query: JobShop Query

• Lab 4-5: Implementation of Mutual Exclusion Algorithms in UPPAAL
  • Slides: The Mutual Exclusion Problem and Algorithms
  • Model: First Attempt Algorithm Model
  • Query: First Attempt Query

• Lab 6: Lab Assignment: ATM System, JobShop, Implementation of Mutual Exclusion Algo.
  • Slides: Tasks and explanation

• Lab 7-8: Assignment: Reader-Writer (unreliable) communication protocol
  • Slides: Example and explanation

• Lab 9: Assignment: Elevator Control
  • Slides: Example and explanation
  • Slides: Modelling Requirements

• Lab 10: Final Assessment on 17 May 2018
  • Lab defending of all given assignment.

Exercises

• Exercises 1: Model checking (explicit and symbolic state)
• Exercises 2: Partial correctness of WHILE-programs
  • Example 1: Partial correctness of WHILE-loop
  • Example 2: Partial correctness of FOR-loop
• Partial correctness of non-deterministic and parallel programs
  • Exercises 3.1: Partial correctness of non-deterministic and parallel programs
  • Exercises 3.2: Partial correctness of non-deterministic and parallel programs
  • Exercises 3.3: Parallel programs with message passing

Resources

• Formal Methods Europe
• Genzen's proof system for 1st order logic:
• HL proof rules for sequential and parallel programs:
• Some guidlines how to find invariants
• Mike Gordon's lecture notes on Hoare logic [1]