Department of Information and Computing Sciences

Departement Informatica Onderwijs
Bachelor Informatica Informatiekunde Kunstmatige intelligentie Master Computing Science Game&Media Technology Artifical Intelligence Business Informatics

Onderwijs Informatica en Informatiekunde

Vak-informatie Informatica en Informatiekunde

Program semantics and verification

Website:website containing additional information
Course code:INFOMPSV
Credits:7.5 ECTS
Period:period 1 (week 36 through 45, i.e., 4-9-2017 through 10-11-2017; retake week 1)
Participants:up till now 14 subscriptions
Schedule:Official schedule representation can be found in Osiris
lab session group 1 Wed 11.00-12.4537-40 BBG-112 CLZ
42-44 BBG-112 CLZ
lecture   Mon 11.00-12.4537 UNNIK-311 Wishnu Prasetya
38 DDW-1.18EN1.20
39-44 UNNIK-311
Wed 9.00-10.4537-40 BBG-077
42-44 BBG-077
week: 41Wed 11-10-20178.30-10.30 uurroom: BBG-001
week: 45Wed 8-11-20179.00-12.00 uurroom: BBG-001
week: 1Tue 2-1-201817.00-20.00 uurroom: UNNIK-220retake exam
Note:No up-to-date course description available.
Text below is from year 2016/2017
Contents:Most modern software is quite complex. The most widely used approach to verify them is still by testing, which is inherently incomplete and hard to scale up to cover the complexity. In this course we will discuss a number of advanced validation and verification techniques that go far beyond ad-hoc testing. Exploiting them is an important key towards more reliable complex software. We will in particular focus on techniques that can be automated, or at least partially automated. We will discuss several common ways to define the semantic of programs, from which correctness can be defined and proven. We will discuss the predicate transformation technique, which you can use to symbolically execute a program to calculate its range of input or output. We will discuss several model checking techniques, that can be used to fully verify the model of a program, even if the number of possible executions is infinite. We will also discuss higher order theorem proving. Verification in this setting is usually not fully automatic, but it is very expressive, and thus provides at least an alternative when a verification problem cannot be suitably mapped to one of the above solutions.

Learning goals: to become familiar with, and acquire insight on the underlying concepts of:

  • program semantics: operational, denotational, axiomatic.
  • formalisms to express programs' correctness: Hoare-style, LTL, CTL, higher order logic, CSP.
  • automated verification techniques: predicate transformer, model checking (LTL,, CTL, symbolic), tactic-based theorem proving, refinement checking.
Additionally, to acquire hands-on experience with :
  • using a verification tool to model a problem and conduct a verification of its solution.
  • implementing a verification technique.
  • embedding a simple programming language in a higher order theorem prover, and to use it to prove the correctness of some example programs.
Literature:May change!
Lecture notes, on-line documentation, and papers.
Course form:Lectures.
Exam form:In principle 40% projects, 60% exams. This can be changed depending on the composition of the projects, but in any case the exam form and grading will be announced and fixed at the start of the course.
Minimum effort to qualify for 2nd chance exam:To qualify for the retake exam, the grade of the original must be at least 4.