Accelerating Parametric Probabilistic Verification

You have come to an old website. Our new URL is ths.rwth-aachen.de. Please update your bookmarks!

This is a webpage for our project concerning parametric probabilistic verification. If you encounter any problems or if you have any questions, please contact Nils Jansen.

Documentation

We have submitted a paper about model checking parametric discrete-time Markov chains to QEST 2014. A technical report including all proofs is available here.

Our first work in this project was done within the bachelor thesis of Matthias Volk, which is available here.

Implementation

The sources of our implementation can be found here. Installation instructions can be found in the included README file.

A linux binary is available here.

Involved Persons

The people involved with this project are Nils Jansen, Florian Corzilius, Matthias Volk, Erika Ábrahám, Ralf Wimmer, Joost-Pieter Katoen and Bernd Becker.

Benchmarks

We give three different sets of benchmarks. Short descriptions and downloads are listed below, more benchmarks for PDTMCs are available at the homepage of PARAM.

The Bounded retransmission protocol [HSV94] sends a file by dividing it into a number of N chunks. Only a bounded number MAX of retransmissions for each chunk is allowed. Additionally, there are two lossy channels K and L with reliability p_K and p_L for sending data and acknowledgments respectively. The original version of this benchmark is available at the PRISM homepage. A parametric version is available at the PARAM homepage, where p_K and p_L are used as parameters in the model. We compute the probability that the sender successfully transmits a chunk but does not report that. The set of instances we tested for the paper is available here.

The Crowds protocol [RR98] is designed for anonymous communication in the internet via random routing. Sending a message to a specific user allows for two different actions. The message either is sent directly to this user or first is sent to a random user, who acts a router by only forwarding the message. Therefore, an intruder can not be certain if a message was sent by a specific user or if the sender only forwarded the massage. Thus anonymity can be preserved. In our test cases we have N honest users, M dishonest users and therefore a percentage of B=M/(M+N) untrustworthy users. R many messages are sent during the whole process. The probability of sending the message directly to its destination is 1-p_f, whereas the message is forwarded with probability p_f. We use p_f and B as parameters in our model and are interested in the probability, that one user is identified more often by a bad member than every other. The original version of this benchmark is available at the PRISM homepage. A parametric version is available at the PARAM homepage. The set of instances we tested for the paper is available here.

NAND multiplexing [HJ02] deals with constructing reliable computation from unreliable hardware. For performing a computation, a NAND unit is multiplexed by copying it N times with own input and output. Next, K restorative stages are introduced to reduce the degradation after the NAND computation. In our model we have the parameter p_err as the probability for NAND not working correctly and p_inp as the probability for the initial inputs to be stimulated. We are now interested in the probability that less than 10% of the computed outputs are erroneous. The original version of this benchmark is available at the PRISM homepage. The set of instances we tested for the paper is available here.

[HSV94] Helmink, L., Sellink, M., Vaandrager, F.: Proof-checking a data link protocol. In: Proc. of TYPES. Volume 806 of LNCS, Springer (1994) 127–165

[RR98] Reiter, M.K., Rubin, A.D.: Crowds: Anonymity for web transactions. ACM Trans. on Information and System Security 1(1) (1998) 66–92

[HJ02] Han, J., Jonker, P.: A system architecture solution for unreliable nanoelectronic devices. IEEE Transactions on Nanotechnology 1 (2002) 201–208

2013
	Nils Jansen, Florian Corzilius, Matthias Volk, Ralf Wimmer, Erika Abraham, Joost-Pieter Katoen, Bernd Becker. Accelerating Parametric Probabilistic Verification. Technical report at Cornell University number arXiv:1312.3979, 2013.

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.