Mateusz Ujma

Tomáš Brázdil, Krishnendu Chatterjee, Martin Chmelik et al.

We present a general framework for applying learning algorithms and heuristical guidance to the verification of Markov decision processes (MDPs). The primary goal of our techniques is to improve performance by avoiding an exhaustive exploration of the state space, instead focussing on particularly relevant areas of the system, guided by heuristics. Our work builds on the previous results of Br{á}zdil et al., significantly extending it as well as refining several details and fixing errors. The presented framework focuses on probabilistic reachability, which is a core problem in verification, and is instantiated in two distinct scenarios. The first assumes that full knowledge of the MDP is available, in particular precise transition probabilities. It performs a heuristic-driven partial exploration of the model, yielding precise lower and upper bounds on the required probability. The second tackles the case where we may only sample the MDP without knowing the exact transition dynamics. Here, we obtain probabilistic guarantees, again in terms of both the lower and upper bounds, which provides efficient stopping criteria for the approximation. In particular, the latter is an extension of statistical model-checking (SMC) for unbounded properties in MDPs. In contrast to other related approaches, we do not restrict our attention to time-bounded (finite-horizon) or discounted properties, nor assume any particular structural properties of the MDP.

Klaus Drager, Vojtech Forejt, Marta Kwiatkowska et al.

We propose novel controller synthesis techniques for probabilistic systems modelled using stochastic two-player games: one player acts as a controller, the second represents its environment, and probability is used to capture uncertainty arising due to, for example, unreliable sensors or faulty system components. Our aim is to generate robust controllers that are resilient to unexpected system changes at runtime, and flexible enough to be adapted if additional constraints need to be imposed. We develop a permissive controller synthesis framework, which generates multi-strategies for the controller, offering a choice of control actions to take at each time step. We formalise the notion of permissivity using penalties, which are incurred each time a possible control action is disallowed by a multi-strategy. Permissive controller synthesis aims to generate a multi-strategy that minimises these penalties, whilst guaranteeing the satisfaction of a specified system property. We establish several key results about the optimality of multi-strategies and the complexity of synthesising them. Then, we develop methods to perform permissive controller synthesis using mixed integer linear programming and illustrate their effectiveness on a selection of case studies.

Mateusz Ujma, Nastaran Shafiei

One of the main challenges when verifying multi-threaded Java applications is the state space explosion problem. Due to thread interleavings, the number of states that the model checker has to verify can grow rapidly and impede the feasibility of verification. In the Java language, the source of thread interleavings can be the system under test as well as the Java Development Kit (JDK) itself. In our paper, we propose a method to minimize the state space explosion problem for applications verified under the Java PathFinder (JPF) model checker. Our method is based on abstracting the state of the application to a smaller domain and implementing application behavior using the Model Java Interface (MJI) of JPF. To show the capabilities of our approach, we have created a JPF extension called jpf-concurrent which abstracts classes from the Java Concurrency Utilities. Several benchmarks proved the usefulness of our approach. In all cases, our implementation was faster than the JDK implementation when running under the JPF model checker. Moreover, our implementation led to significantly smaller state spaces.