Success Stories in Formal Methods

Seminar in Theoretical CS, Summer Semester 2013

21.12.2012: Setup of this web page

Thu 21.02.2013 15:00	Introduction at seminar room of i2
-8 weeks	Table of contents due
-6 weeks	Preliminary version of report due
-4 weeks	Final version of report due
-2 weeks	Preliminary version of slides due
-1 week	Final version of slides due
(relative to date of presentation)

The general term formal methods refers to rigorous, mathematically based techniques for the specification, development and verification of software and hardware systems. The use of such methods is motivated by the expectation that it will improve the correctness, reliability and robustness of the system under development. Formal methods can be classified according to the phase of the system design process in which they are employed (specification, development, verification, testing, ...) or to the underlying mathematical theories (process algebras, model checking, theorem proving, ...).

The goal of this seminar is to study some real-world case studies in which formal methods have successfully been applied. These examples are taken from several application domains, such as traffic control, communication protocols, computer operating systems, and others.

(regular date: Wednesday 16:00-17:00 at I2 seminar room; double dates 16:00-18:00)

Operating Systems I

Operating System Kernel: Gerwin Klein, June Andronick, Kevin Elphinstone, Gernot Heiser, David Cock, Philip Derrin, Dhammika Elkaduwe, Kai Engelhardt, Rafal Kolanski, Michael Norrish, Thomas Sewell, Harvey Tuch and Simon Winwood: seL4: Formal verification of an operating system kernel, Communications of the ACM, 53(6), 2010, 107–115
- Student: Torben Schulz
- Advisor: Thomas Noll
- Date: April 16

Railway Transportation I

Railway Signaling: Bacherini, S.; Fantechi, A.; Tempestini, M.; Zingoni, N.: A Story About Formal Methods Adoption by a Railway Signaling Manufacturer, FM 2006: Formal Methods, LNCS 4085, 2006, 179-187
Roissy VAL Shuttle: Frédéric Badeau, Arnaud Amelo: Using B as a High Level Programming Language in an Industrial Project: Roissy VAL, ZB 2005: Formal Specification and Development in Z and B, LNCS 3455,
2005, pp 334-354
- Student: Michael Schlimnat
- Advisor: Christian Dehnert
- Date: May 7

Aerospace

Mars Rover: Brat, G.; Drusinsky, D.; Giannakopoulou, D.; Goldberg, A.; Havelund, K.; Lowry, M.; Pasareanu, C.; Venet, A.; Visser, W.; Washington, R.: Experimental Evaluation of Verification and Validation Tools on Martian Rover Software, Form. Methods Syst. Des. 25(2-3), 2004, 167-198
- Student: Sadiksha Gautam
- Advisor: Viet Yen Nguyen
- Date: May 7
Air Traffic Control:
1. Hall, A.; Isaac, D.; Formal methods in a real air traffic control project, IEEE Colloquium on Software in Air Traffic Control Systems - The Future, pp. 7/1-7/4, June 1992
2. J. Hörl, B.K. Aichernig: Formal Specification of a Voice Communication System Used in Air Traffic Control, FM 1999
3. M. Jamal: Requirements Analysis of Air Traffic Control System Using Formal Methods, Int. Conf. on Information and Emerging Technologies (ICIET 2007), 1-7
- Student: Hariprasad Rajagopal
- Advisor: Arpit Sharma
- Date: May 15
Validation of a Satellite System: Marie-Aude Esteve, Joost-Pieter Katoen, Viet Yen Nguyen, Bart Postma, and Yuri Yushtein. Formal Correctness, Safety, Dependability and Performance Analysis of a Satellite. In 34th International Conference on Software Engineering (ICSE). pages 1022–1031. ACM and IEEE CS Press, 2012
Satellite Software: Alexei Iliasov, Elena Troubitsyna, Linas Laibinis, Alexander Romanovsky, Kimmo Varpaaniemi, Dubravka Ilic, Timo Latvala: Developing mode-rich satellite software by refinement in Event-B, Science of Computer Programming, May 2012
- Student: Andrei Ionita
- Advisor: Thomas Noll
- Date: June 5

Operating Systems II

Real-Time Operating System: Verhulst, Eric and De Jong, Gjalt: OpenComRTOS: an ultra-small network centric embedded RTOS designed using formal modeling, Proceedings of the 13th international SDL Forum conference on Design for dependable systems, LNCS 4745, 2007, 258-271
- Student: Christoph Matheja
- Advisor: Sabrina von Styp
- Date: June 5

Communication Protocols I

Needham-Schroeder Public-Key Protocol: G. Lowe: Breaking and Fixing the Needham-Schroeder Public-Key Protocol using FDR, TACAS 1996, LNCS 1055, 1996, 147-166

Miscellaneous

Rotterdam Storm Surge Barrier: Ken Madlener, Sjaak Smetsers and Marko van Eekelen: A Formal Verification Study on the Rotterdam Storm Surge Barrier, Formal Methods and Software Engineering, LNCS 6447, 2010, 287-302
- Student: Markus Joppich
- Advisor: Hao Wu
- Date: June 26

Railway Transportation II

Paris Metro: Patrick Behm, Paul Benoit, Alain Faivre and Jean-Marc Meynadier: Météor: A Successful Application of B in a Large Project, Formal Methods (FM'99), LNCS 1708, 1999, 369-387
- Student: Xinyu Ge
- Advisor: Christina Jansen
- Date: June 26

Communication Protocols II

Mobile Communication Protocol: M.A. Fecko, M.Ü. Uyar, P.D. Amer, A.S. Sethi, T. Dzik, R. Menell, M. McMahon, A success story of formal description techniques: Estelle specification and test generation for MIL-STD 188-220, Computer Communications, Volume 23, Issue 12, July 2000, Pages 1196-1213
- Student: Narek Danoyan
- Advisor: Thomas Noll
- Date: July 10

Registration to the seminar is handled via the central online form at www.graphics.rwth-aachen.de/apse

Thomas Noll <noll at cs.rwth-aachen.de>

BSc/MSc/Diploma Topics
Teaching WS 2012/13
Hybrid Systems Group

We are looking for a HiWi for the Compiler Construction course. If you are interested, please contact Thomas Noll.

Joost-Pieter Katoen has been appointed as a member of the renowned Academia Europaea (Academy of Europe), a European, non-governmental association acting as an Academy whose members are scientists and scholars who collectively aim to promote learning, education and research.

Vacancies for postdoctoral researchers in "Automated Analysis of Probabilistic Programs". Application deadline: August 15, 2013.

Joost-Pieter Katoen has been awarded a Distinguished Professorship from the RWTH Aachen University.

The Hybrid Systems: Computation and Control (HSCC'13) conference in Philadelphia has been very successful: Hongfei Fu received the best student paper award for his paper "Approximating acceptance probabilities of CTMC-paths on multi-clock deterministic timed automata". Besides, the paper by Ilya Tkachev, Alexandru Mereacre, Alessandro Abate and Joost-Pieter Katoen was ranked second in the overall best paper award selection.

Joost-Pieter Katoen has been elected as Steering Committee Chair of ETAPS (www.etaps.org), the largest conference on theory and practice of software in Europe. He is the first non-UK ETAPS SC chair since the conference was initiated in 1998. More information here.

The Alumni-Magazine of RWTH Aachen University contains an interview with our former PhD student and postdoctoral researcher, Dr. Tingting Han.

HiWi's wanted to work in a new European Space Agency project for enhancing state-of-the-art design and analysis tools (COMPASS) for the next generation European rockets. Need programming and model checking affinity. See here for details and contact.

We offer openings for several PhD candidates in the area of
"Model-Based Design and Analysis for Dependable Software Systems". Deadline for application: September 14, 2012. For further information click here.

The Theory of Hybrid Systems Group offers two jobs as student assistants within the CEBug project. For more information, look here.

Dino Distefano received the prestigious Roger Needham Award for his work on software verification. This award is for a distinguished research contribution in computer science by a UK based researcher who has completed up to 10 years of post-doctoral research. Dr. Distefano was the first PhD student supervised by Joost-Pieter Katoen.

Marijn Jongerden received the German MMB (Messung, Modellierung und Bewertung von Rechensystemen) Award 2012 of the GI/ITG-Committee for Measurement, Modelling and Evaluation of Computing Systems for his PhD-thesis on "Model-based energy analysis of battery powered systems". His work was supervised by Boudewijn Haverkort (Twente) and Joost-Pieter Katoen.

Our paper "Formal Correctness, Safety, Dependability and Performance Analysis of a Satellite" has been accepted to ICSE 2012 in the track SE in Practice (18% acceptance rate). The paper treats a new satellite from the European Space Agency that was modeled and analyzed with modern tools during the actual satellite design.

Joost-Pieter Katoen will act as DJ in the "Nacht der Professoren" in the Apollo bar and cinema.