Skip navigation.
Home

Advanced Topic in Model-Checking, SS 2007

Instructors

Description

Software Model Checking deals with automated verification of programs. A variety of successful tools have emerged in the recent years, some of them have found application in the industry. We are going to learn about Software Model Checking: read papers about underlying methods and algorithms, play with tools, discuss in the class, find out what could be done better.

Registration

Good students are always welcome.

Topic list

includes, but is not limited to the given set of articles. To get a topic please talk to Alexander. Teams are welcome, people are allowed to share a topic.

Talk

All the speakers are supposed to give a talk in English. The format of the slides does not matter as long as it can be presented on a standard Windows or Linux machine. We advise ps/pdf (or overhead slides). For a seminar talk, the talk length is one hour plus at most 15 minutes for questions and comments from the listeners. Please send your slides to Alexander till the 24th of June 2007 so that we could look through all of them in advance. For a CAV 2007 talk, each speaker has at most 25 minutes, including discussion.

List of Participants

Students, who give a seminar talk and want to receive a certificate for it

Justus Bisser, Juergen Christ, Kais Haddadin, Matthias Heizmann, Abel F. L. Kla, Marco Muniz, Arend von Reinerdorff, Alexander Schimpf, Peter Schmitt

Students, who give a CAV 2007 talk

Daniel Dietsch, Sergio A. Feo, Matthias Heizmann, Nicola Sheldrick

Others

Stefan Arlt, Jochen Hoenicke, Alexander Malkis, Stefan Maus, Martin Mehlmann, Corina Mitrohin, Andreas Podelski (without a talk), Martin Schäf, Nassim Seghir, Martin Wehrle

Preliminary program

23 July 2007, Monday
9:00 - 10:00 We meet on the university car park to the north-west of the SWT building 052 at 9:00. People who have a car and can drive arrive with their cars to the meeting point. We need six cars to get everybody in. Then we drive to Fachschaftshaus am Schauinsland (see the map).
10:00 - 11:00 Marco Muniz A lattice-theoretical fixpoint theorem and its applications
11:00 - 12:30 Matthias Heizmann Constructive versions of Tarski's fixpoint theorems. Slides.
12:30 - 13:00 Break
13:00 - 14:30 Lunch
14:30 - 15:30 Peter Schmitt State complexity of intersection of regular languages. Slides. Report.
15:30 - 16:45 Arend von Reinerdorff Partial Order Reduction
16:45 - 17:00 Break
17:00 - 18:15 Juergen Christ Deadlock detection
18:15 - 18:30 Break
18:30 - 19:30 Dinner
19:45 - 20:45 Alexander Schimpf Thread-modular verification (probably with ESC/Java)
24 July 2007, Tuesday
8:00 - 9:00 Breakfast
9:00 - 10:15 Abel F. L. Kla Permutation rewriting and algorithmic verification
10:15 - 10:30 Break
10:30 - 11:30 Kais Haddadin Size of the union of cartesian products
11:30 - 12:45 Justus Bisser Monadic second-order logic over finite trees
12:45 - 13:00 Break
13:00 - 14:30 Lunch
14:30 - 15:00 Stefan Maus Vijay Ganesh and David Dill. A Decision Procedure for Bit-Vectors and Arrays. Classification: SAT decision procedures.
15:00 - 15:30 Corina Mitrohin Alessandro Cimatti, Marco Roveri, Viktor Schuppan and Stefano Tonetta. Boolean Abstraction for Temporal Logic Satisfiability. Classification: SAT decision procedures.
15:30 - 16:00 Martin Wehrle Oded Maler, Dejan Nickovic and Amir Pnueli. On Synthesizing Controllers from Bounded-Response Properties. Classification: timed synthesis and games.
16:00 - 16:30 Break
16:30 - 17:00 Sergio Arenis Feo Chao Wang, Zijiiang Yang, Aarti Gupta, Franjo Ivancic. Structural Abstraction of Software Verification Conditions. Classification: abstraction.
17:00 - 17:30 Jochen Hoenicke Anubhav Gupta, Ken McMillan and Zhaohui Fu. Automated Assumption Generation for Compositional Verification. Classification: assume-guarantee reasoning.
17:30 - 18:00 Nicola Sheldrick Ahmed Rezine, Parosh Abdulla and Giorgio Delzanno. Parameterized Verification of Infinite-state Processes with Global Conditions. Classification: infinite-state verification.
18:00 - 18:30 Break
18:30 - 19:30 Dinner
25 July 2007, Wednesday
8:00 - 9:00 Breakfast, moving out of the dormitory
9:00 - 9:30 Matthias Heizmann Marc Segelken. Abstraction and Counterexample-guided Construction of Omega-automata for Model Checking of Step-discrete linear Hybrid Models. Classification: hybrid systems.
9:30 - 10:00 Alexander Malkis Daphna Amit. Comparison Under Abstraction for Verifying Linearizability. Classification: program analysis.
10:00 - 10:30 Martin Schäf Dirk Beyer, Thomas A. Henzinger, Grégory Théoduloz. Configurable Software Verification: Concretizing the Convergence of Model Checking and Program Analysis. Classification: program analysis.
10:30 - 11:00 Break
11:00 - 11:30 Daniel Dietsch. Josh Berdine, Cristiano Calcagno, Byron Cook, Dino Distefano, Peter W. O'Hearn, Thomas Wies, and Hongseok Yang. Shape Analysis for Composite Data Structures. Classification: shapes.
11:30 - 12:00 Nassim Seghir Ranjit Jhala and Ken McMillan. Array Abstractions from Proofs. Classification: shapes.
12:00 - 12:30 Thomas Wies Heap Assumptions On Demand. Classification: shapes.
12:30 - 13:00 Break
13:00 - 14:30 Lunch
14:30 - 18:00 Excursion. Take enough water with you.
18:30 - 19:30 Dinner
19:30 - 20:00 Martin Mehlmann Thomas Reps and Denis Gopan. Low-Level Library Analysis and Summarisation. Classification: verification process.
20:00 - 20:30 Stefan Arlt Sagar Chaki, Christian Schallhart and Helmut Veith. Verification Across Intellectual Property Boundaries. Classification: verification process.
20:30 - 21:00 Paying for beverages. Prepare some change.
21:00 Departure

Submitted report

The length and the contents depend on the chosen topic. The students will be given at least two weeks after the seminar to prepare the report. We strongly encourage submissions in English. A submission in German is possible only as an exception; in this case it should be absolutely flawless. We encourage flawless submissions anyway.

We advise typing in using the "llncs" style for latex (for the LNCS author instructions see http://www.springer.de/comp/lncs/authors.html , click on "Information for LNCS Authors", download and unzip llncs2e.zip and follow the typesetting instructions from the file llncsdoc.pdf) and also advise submitting files in the ps/pdf format. Using llncs and pdf/ps format for submission is an advice, not a requirement.

Costs

The participants don't have to pay for accomodation and usual meals, but they have to pay for the extra beverages they buy there themselves. The money for these beverages will be collected at the end of the stay, so please take enough small change with you. The SWT people should fill in the application forms before the 10th of July 2007 in any case.

Remember

  • You need slippers. They won't let you into the house if you have your outdoor shoes on.
  • There is neither soap nor towels for all, take your own towel and your own piece of soap.
  • No dogs.
  • For a possible excursion you need waterproof cloths and boots and at least a liter of water.
  • The speakers should take their laptop with cable AND send their slides to us as soon as they are ready.
  • The speakers should think about how and how long they could still give a talk in case of a technical failure.
  • Assume that it's not possible to use Internet and mobile phones at Schauinsland.
  • You will have a beamer, a flipchart and an overhead projector at your disposal, but no blackboard or whiteboard.
  • If you want vegetarian meals, please tell us in advance.
  • It is forbidden to bring your own beverages to Schauinsland.