Artifact for the ATVA'23 paper "Scenario Approach for Parametric Markov Models"

  • Ying Liu (Creator)
  • Andrea Turrini (Creator)
  • Ernst Moritz Hahn (Creator)
  • Bai Xue (Creator)
  • Lijun Zhang (Creator)



In our paper, we present an approximating framework for analyzing parametric Markov models. Instead of computing complex rational functions encoding the reachability probability and the reward values of the parametric model, we exploit the scenario approach to synthesize a relatively simple polynomial approximation. The approximation is probably approximately correct (PAC), meaning that with high confidence, the approximating function is close to the actual function with an allowable error. With the PAC approximations, one can check properties of the parametric Markov models. We show that the scenario approach can also be used to check PRCTL properties directly -- without synthesizing the polynomial at first hand. We have implemented our algorithm in PacPMA and conducted thorough experiments. The experimental results demonstrate that our tool is able to compute polynomials for more benchmarks than state-of-the-art tools such as PRISM and Storm, confirming the efficacy of our PAC-based synthesis. As artifact, we provide a Virtual Machine image with 1 core and 4GB of RAM (which should be suitable for all recent desktop and laptop machines), whose operating system is Ubuntu 20.04; login is automatic, but in case of need, use "experiments" for both username and password. In the home directory of the user "experiments" we include the source code of our tool PacPMA, the benchmarks used in the experiments and the script files for running the experiments and generating the plots included in the paper. Please note that in the paper, we performed the experiments natively on a desktop machine with 16GB of RAM and a 3.6 GHz Intel Core i7-4790 CPU. We used Benchexec to trace and constrain the tools' executions, and as parameters for each single execution, we used cpuCores="8", memlimit="15000 MB", and timelimit="600 s" to allow each execution to use 8 cored and 15 GB of memory, and imposed a timeout of 10 minutes. Due to the limited resources assigned to the virtual machine, we suggest to increase the memory and CPU cores assigned to the virtual machine as well as the one provided to the experiments. All instructions to adapt the benchmark files to reproduce the results in our paper can be found in the README file.
Date made available27 Jul 2023

Cite this