Model-Based Analysis

• 39 hrs lectures
• 6 hrs pc labs
• 7 hrs projects

• 70 pts final exam (written part)
• 30 pts projects

Introduce students to the possibility of software (resp. hardware) quality assurance by creating its model, check correctness on the level of the model, and subsequently translate (sometimes automatelly) the model into the target programming language. These principles are introduced on four models, in particular: Petri nets, Markov chains, timed automata and UML/SysML diagrams.

The classical approach to software development is to implement it in a chosen programming language and then test it (eventually verify it). In the quality assurance of embedded and safety-critical systems is often used a different approach. First, one creates a model of the system (or its part) in a suitable modelling language and then verify its quality on the level of the model. After that one translate (often automatically) the model into the target programming language. Verification on the level of a model is often much easier then verification of equal properties directly on the level of a source code.

• Theoretical Computer Science (TIN)

Basic knowledge of graph theory, formal languages concepts and automata theory. Basic knowledge of statistics and probability. Basic knowledge of software engineering.

• Češka, M.: Petriho sítě, Akad.nakl. CERM, Brno, 1994. ISBN: 8-085-86735-4
• Jensen, K.: Coloured Petri Nets, Basic Concepts, Analysis Methods and Practical Use, Springer Verlag, 1993. ISBN: 3-540-60943-1
• Kaynar, D.,  Lynch, N., Segala, R., Vaandrager, F. :The Theory of Timed I/O Automata, Morgan & Claypool, 2010.  ISBN-13: 978-1608450022 Dostupné online.

1. Introduction to the topic of model-based design, testing and analysis. The term model-checking.
2. Petri nets. Basic terms, history and applications.
3. P/T Petri nets, definition, evolution rules, state space, bacis problems of analysis.
4. Analysis of P/T Petri nets, coveribility tree, P- and T- invariants.
5. Extensions of P/T Petri nets and Coloured Petri nets. Decidability and relation to Turing machines. Tools NetLab a PIPE.
6. Timed automata and their use in modelling of systems with real-time.
7. Timed automata analysis, region abstraction, decidable problems. Tool UPPAAL.
8. Timed temporal logic TCTL and its relation to timed automata.
9. Temporal logic PCTL for Markov chain specification. Advanced analysis of Markov chains and Markov Decision Processes.
10. Using counter-examples in the verification of Markov Chains. Synthesis of Markov chains.
11. Continuous-time Markov chains and their analysis using uniformization.
12. UML/SysML diagrams and their use in model-based design and analysis.
13. Model checking of systems described by UML (state) diagrams.

If applicable:

1. Analysis of P/T Petri nets, tools NetLab a PIPE.
2. Analysis of Markov chains, tool PRISM
3. Analysis of timed automata, tool UPPAAL.

1. Application of Petri nets.
2. Application of timed automata.
3. Application of Markov chains.

3 projects, 10 points each.

Students have to achieve at least 30 points, otherwise the exam is assessed by 0 points.