Model Checking Stochastic Systems using Rare Event Simulation
Project Number: 612.064.812
Project Manager: Dr. ir. Pieter-Tjerk de Boer
Faculty of Electrical Engineering, Mathematics and Computer Science - EEMCS
In the design of dependable (embedded) computer and communication systems, the use of architecture description languages (ADLs) such as AADL becomes more and more widespread.
In order to establish the correct and timely operation of such systems by design, the use of model checking has become more prevalent in recent years. In particular, model checking techniques have been developed to deal with models including time and rewards, so-called Markov reward models, for which the logic CSRL has been developed to express properties. For CSRL model checking, numerical algorithms have been developed, however, the algorithms fall short for realistically sized models, as they arise when using ADLs. To overcome this, we propose to develop new, efficient rare-event simulation techniques for model checking large Markov-rewards models specified using ADLs. We will develop efficient simulation techniques based on the rare-event simulation technique known as importance sampling, which is particularly powerful in case the probabilities for the events of interest can be considered rare (e.g., when these express undesirable behaviour, like failures). The developed methods, and the corresponding tool support, will allow us to model check such properties, efficiently, and in a statistically sound way, which is crucial for evaluating design alternatives for dependable (embedded) systems.
Project duration: 2009-2013
Project budget: 182.5 k-€
Number of person/years CTIT: 1.4 fte
Involved groups: Design and Analysis of Communication Systems (DACS), Stochastic Operations Research (SOR), Formal Methods and Tools (FMT)