PRISM manual latest

PRISM is a probabilistic model checker, a tool for the modelling and analysis of systems that exhibit random or uncertain behaviour. Probabilistic model checking is a formal verification technique: you build a precise mathematical model of the system to be analysed, express its properties formally in temporal logic, and PRISM analyses them automatically against the model.

Models

Models are written in the PRISM language, a simple, high-level modelling language. PRISM supports many different types of probabilistic model. The three most common are:

Model Keyword Use it when
Discrete-time Markov chain (DTMC) dtmc Behaviour is purely probabilistic, in discrete steps
Continuous-time Markov chain (CTMC) ctmc Events happen after exponentially distributed delays, in continuous time
Markov decision process (MDP) mdp There are also nondeterministic choices: decisions to optimise, or an unknown scheduler / environment

PRISM also supports real-time models (e.g., probabilistic timed automata, PTAs), partially observable models (e.g., partially observable Markov decision processes, POMDPs), and uncertain models (e.g., interval Markov decision processes, IMDPs). It can also analyse non-probabilistic models (e.g., labelled transition systems, LTSs), using temporal logics such as CTL and LTL.

Properties

Properties are written in PRISM's property specification language, which is based on temporal logic. It incorporates several well-known probabilistic temporal logics, such as PCTL, probabilistic LTL and CSL. It also covers costs and rewards, multi-objective queries, and much more.

PRISM can formally verify that these properties hold (e.g., "the probability of a failure occurring within 10 time units is below 0.01") or generate strategies/policies/controllers that optimise properties (e.g., "how can I maximise the probability of reaching a goal location whilst avoiding hazard locations?").

Where to start

New to PRISM? See the "Getting started" section for details of installing and running PRISM for the first time. Work through the tutorial to learn what the tools can do, or read the sections on the modelling and property languages.

Contents

Getting started

This section guides new users through the first steps of installing and running PRISM.

Contents

Installing PRISM

Prerequisites

PRISM runs on Linux, Windows and macOS. Pre-compiled binaries are available for 64-bit Linux (x86 and Arm), macOS (Apple silicon and Intel) and Windows (x86); on other platforms, you can build PRISM from source.

You will need Java, version 11 or above. To run binary versions of PRISM, you only need the Java Runtime Environment (JRE), not the full Java Development Kit (JDK).

To compile PRISM from source, you need the Java Development Kit (JDK), GNU make and a C/C++ compiler (e.g. gcc/g++). For compilation under Windows, you will need Cygwin. See below for more information:

If you are installing on a completely fresh operating system installation (e.g. in a virtual machine), you may find the following scripts useful, which install the required dependencies and PRISM itself. They can be found in the prism/etc/scripts directory:

Installation on Windows

If you don't yet have Java, install it, for example with the Temurin installer.

To install PRISM on Windows, just run the self-extracting installer which you downloaded. You do not need administrator privileges for this, just write-access to the directory chosen for installation.

If requested, the installer will place shortcuts to run PRISM on the desktop and/or start menu. If not, you can run PRISM by double-clicking the file xprism.bat (which may just appear as xprism) in the bin folder of your PRISM folder. If nothing happens, the most likely explanation is that Java is not installed or not in your path. To check, open a command prompt window, navigate to the PRISM directory, type cd bin, then xprism.bat and examine the resulting error. If you want to create shortcuts to xprism.bat manually, you will find some PRISM icons in the etc folder.

If you wish to use the command-line version of PRISM on Windows, open a command prompt window and type for example:

cd "c:\Program Files\prism-4.11\bin"
prism ..\prism-examples\simple\dice\dice.pm

You can also edit the file bin\prism.bat to allow it to be run from any location. See the instructions within the file for further details.

Problems? See "Troubleshooting".

Installation of Linux/Mac binary versions

We provide pre-compiled binary distributions for Linux and macOS (if you have any problems running these, try compiling PRISM from source instead - see below for instructions). To install a binary distribution, unpack the tarred/zipped PRISM distribution into a suitable location, enter the directory and run the install.sh script, e.g.:

tar xfz prism-4.11-linux64-x86.tar.gz
cd prism-4.11-linux64-x86
./install.sh

On macOS, you may want to run the following command, which avoids manually approving the integrity of the binary files:

xattr -d com.apple.quarantine lib/*lib

You do not need to be root to install PRISM. The install script simply makes some small customisations to the scripts used to launch PRISM. The PRISM distribution is self-contained and can be freely moved/renamed, however if you do so you will need to re-run ./install.sh afterwards.

To run PRISM, execute either the xprism or prism script (for the graphical user interface or command-line version, respectively). These can be found in the bin directory. These scripts are designed to be run from anywhere and you can easily create symbolic links or aliases to them. If you want icons to create desktop shortcuts to PRISM, you can find some in the etc directory.

Problems? See "Troubleshooting".

Building PRISM from source (non-Windows)

To compile PRISM from source code, you will need:

  • GNU make (sometimes called gmake)
  • a C/C++ compiler (e.g. gcc/g++)
  • a Java Development Kit, version 11 or above

To check that you have the development kit, type javac. If you get an error message that javac cannot be found, you probably do not have the JDK installed (or your path is not set up correctly). To check what version you have, type javac -version.

Hopefully, you can build PRISM simply by entering the PRISM directory and running make, e.g.:

tar xfz prism-4.11-src.tar.gz
cd prism-4.11-src/prism
make

For this process to complete correctly, PRISM needs to be able to determine your operating system (OSTYPE), machine architecture (ARCH) and the location of your Java distribution (JAVA_DIR). If there is a problem with any of these, you will see an error message and will need to specify one or more of these manually, such as in these examples:

make OSTYPE=linux
make OSTYPE=linux ARCH=aarch64
make JAVA_DIR=/usr/lib/jvm/java-21-openjdk
make OSTYPE=cygwin JAVA_DIR="/cygdrive/c/Program Files/Java/jdk-21"

Note the use of double quotes for the case where the directory contains a space. If you don't know the location of your Java installation, try typing which javac. If the result is e.g. /usr/lib/jvm/java-21-openjdk/bin/javac then your Java directory is /usr/lib/jvm/java-21-openjdk. Sometimes javac will be a symbolic link, in which case use "ls -l" to determine the actual location.

It is also possible to set the environment variables directly or edit their values in the Makefile directly. Note that even when you specify JAVA_DIR explicitly (in either way), PRISM still uses the version of javac that is in your path. To override this, you can also specify a specific version by setting JAVAC.

Problems? See "Troubleshooting".

Building PRISM from source on Windows using Cygwin

The compilation of PRISM relies on a Unix-like environment. On Windows, this can be achieved using the Cygwin development environment, with the packages below installed. You can run the script prism-install-windows.bat in a Command Prompt to automate this.

  • make
  • mingw64-x86_64-gcc-g++
  • binutils
  • dos2unix
  • git (if you will pull source code from GitHub)
  • wget (if you will pull source code from the web)

Then proceed as described in the previous section. Note that the PRISM compilation process uses the MinGW-w64 libraries so that the final result is independent of Cygwin at run-time.

One thing to note: make sure you unzip the PRISM distribution from within Cygwin (e.g. using tar xfz prism-XXX-src.tar.gz). Don't use a Windows program (Winzip, etc.) since this can cause problems.

If you use git to checkout the PRISM repository, we recommend that you use the version of git provided by Cygwin. If you use a native Windows version of git, you may want to disable the Unix-to-Windows line-ending conversion, e.g., via

  • git config --global core.autocrlf false

Problems? See "Troubleshooting".

Building PRISM from source on Windows using MSYS2

An alternative to Cygwin on Windows is MSYS2. You can install the required MSYS2 packages like this:

pacman -S make mingw-w64-x86_64-gcc binutils dos2unix git wget unzip python nano

Build as for Cygwin, but with MSYS2's MinGW compilers:

make OSTYPE=cygwin CC=/mingw64/bin/gcc CXX=/mingw64/bin/g++
./install.sh

Problems? See "Troubleshooting".

Troubleshooting

Here are the answers to some of the most common questions about installing and running PRISM. If you are still stuck, see "Getting help" on the PRISM website.

Running PRISM

When I double-click the PRISM shortcut on Windows nothing happens

The most common cause of this is that you either do not have Java installed or the java executable is not in your path. In any case, to determine the exact problem, launch a command shell and navigate to the bin directory inside the directory where you installed PRISM (you can use the "PRISM (console)" shortcut installed in the start menu to do this). Then, type prism.bat and see what error message is displayed.

macOS won't open libprism.dylib

When I try to run PRISM on macOS, I get an error of the form:

"libprism.dylib" can't be opened because Apple cannot check it for malicious software.

or:

libprism.dylib not valid for use in process: library load disallowed by system policy

PRISM's macOS binaries are not signed/notarised, so you need to approve the binary files manually to run them. Run this command from the same place you ran ./install.sh:

xattr -d com.apple.quarantine lib/*lib

or approve the libraries one by one through the security settings.

You can also avoid this issue by compiling from source code.

PRISM won't start: UnsupportedClassVersionError

When I try to run PRISM, I get an error of the form:

Exception in thread "main" java.lang.UnsupportedClassVersionError: ... has been compiled by a more recent version of the Java Runtime ...

Your version of Java is too old (PRISM needs Java 11 or above). Update or install a newer version of Java, and then try again.

Compiling PRISM

make seems to get stuck in an infinite loop

This is probably due to the detection of Java failing. Specify the location of your Java directory by hand, e.g. make JAVA_DIR=/usr/lib/jvm/java-21-openjdk. See "Building PRISM from source" for more on this.

libtool errors on macOS

When I try to compile PRISM, I get errors of the form:

/usr/bin/libtool: for architecture: cputype (16777234) cpusubtype (0) file: -lSystem is not an object file (not allowed in a library)

The likely explanation is that you have upgraded to a new version of macOS but have not upgraded the developer tools (Xcode or its command line tools). Upgrade (e.g. with xcode-select --install) and try again.

Nothing happens, or Unexpected end of line seen

When I try to compile PRISM, nothing seems to happen, or I get errors of the form:

make: Fatal error in reader: Makefile, line 58: Unexpected end of line seen...

Perhaps you are not using the GNU version of make. Try typing make -v to find out. On some systems, GNU make is called gmake.

$'\r': command not found on Windows

When I try to compile PRISM on Windows, I get errors of the form:

./install.sh: line 2: $'\r': command not found

The files have Windows line endings. Did you unpack PRISM using WinZip or another Windows program, or check it out with a Windows version of git? If so, unpack from Cygwin, using tar xfz (or similar), or use Cygwin's git (see "Building PRISM from source on Windows using Cygwin").

can't create ... No such file or directory

When I try to compile PRISM, I get an error of the form:

Assembler messages:  Fatal error: can't create ../../obj/dd/dd_abstr.o: No such file or directory

Did you unpack PRISM using a graphical tool or file manager? If so, unpack using tar xfz (or similar) instead.

Do I have to use GNU make to build PRISM?

Strictly speaking, no, but you will have to modify the various PRISM Makefiles manually to overcome this.

Can I build PRISM on other operating systems?

PRISM should be suitable for any Unix/Linux variant.

The first thing you will need to do is compile CUDD (the BDD library used by and included in PRISM) on that platform. CUDD is built with its own configure script (run by cudd/install.sh), which works on most Unix-like systems. To just build CUDD, not PRISM, type make cuddpackage instead of make.

Next, look at the main PRISM Makefile, in particular, each place where the variable $OSTYPE is referred to. Most lines include comments and further instructions. Once you have done this, proceed as usual.

If you do successfully build PRISM on other platforms, please let us know so we can include this information in future releases. Thanks.

Other issues

How do I uninstall PRISM?

If you installed PRISM on Windows using the self-extracting installer, you can uninstall it using the option on the start menu. If you didn't add these shortcuts, just run uninstall.exe from the directory where you installed PRISM.

On other platforms, simply delete the directory containing it.

The only thing that is not removed via either of these methods is the file containing your PRISM settings (see "Settings file" for where it is). You may wish to retain this when upgrading.

First steps

To get started with PRISM, check that you can run either the graphical user interface (xprism) or the command-line version (prism), as explained in the installation instructions.

In short, to run the PRISM GUI:

  • (on Windows) click the short-cut (to xprism.bat) installed on the Desktop/Start Menu
  • (on other OSs) run the xprism script in the bin directory

and for the command-line:

  • run the prism script in the bin directory

You first need a model. Here is a small random walk, specified in the PRISM modelling language:

// A one-sided, one-dimensional random walk

dtmc

const int N = 10;
const double p = 0.5;

module M

	x : [0..N] init 0;

	[] x<N -> p:(x'=max(x-1,0)) + 1-p:(x'=x+1);
	[] x=N -> true;

endmodule

label "end" = x=N;
Download: walk.prism

Loading it into the GUI (xprism walk.prism) lets us view and edit the model:

Screenshot of the Model tab in the PRISM GUI

Some examples of properties to be checked are:

const int k;

// The walk reaches the end with probability 1
P>=1 [ F "end" ];

// What is the probability of reaching the end within k steps?
P=? [ F<=k "end" ];
Download: walk.props

Also loading this properties file into the GUI (e.g., xprism walk.prism walk.props), we can verify the first property to be true and, by making a small change to the constant p and running an experiment, we can start visualising results of the model's analysis:

Screenshot of the Properties tab in the PRISM GUI

All this and more can be done from the command line. Just giving the model file builds it and displays some statistics:

prism walk.prism
...
Type:        DTMC
States:      11 (1 initial)
Transitions: 21
...

or we can verify a property:

prism walk.prism walk.props -prop 1
...
Result: true

Full details of both the GUI and command-line versions of PRISM are given in the "Running PRISM" section of this manual. For more detailed walkthroughs of the tool, try the PRISM tutorial.

The PRISM language

In order to construct and analyse a model with PRISM, it must be specified in the PRISM modelling language (often referred to simply as the PRISM language). This is a simple, state-based language, based on the Reactive Modules formalism [AH99], which expresses the behaviour of a system in terms of guarded commands that describe how its state evolves over time.

The PRISM language is used to describe all the types of model that the tool supports, using files with the extension .prism. The three most commonly used model types are:

  • discrete-time Markov chains (DTMCs)
  • continuous-time Markov chains (CTMCs)
  • Markov decision processes (MDPs)

This section describes the PRISM language, focusing on how it can be used to specify models of these three types, and giving some small illustrative examples.

Later parts of the manual (in the "Extended model types" section) describe further modelling features that support the specification of various other model types:

  • Real-time models using real-valued clocks to represent time, notably probabilistic timed automata (PTAs)
  • Partially observable models, notably partially observable Markov decision processes (POMDPs)
  • Uncertain models, such as interval discrete-time Markov chains (IDTMCs) and interval Markov decision processes (IMDPs)
  • Non-probabilistic models, notably labelled transition systems (LTSs), which have no probabilities

Contents

This section covers the key modelling features and concepts for the PRISM language:

Examples

One of the best ways to learn what can be done with the PRISM language is to look at some existing examples. A number of these are included with the tool distribution in the prism-examples directory. Many more can be found in the "Case studies" section of the PRISM website. Note that some examples of model files may use older conventions for filename extensions, .nm for MDPs or PTAs, .pm for DTMCs and .sm for CTMCs, rather than .prism for all models.

Modules and commands

A PRISM model comprises one or more modules, usually representing distinct system components that may interact with each other. A module has two key ingredients: variables, whose values define the state of the module, and commands, which describe how the state of the module evolves over time.

An example DTMC

The following simple example illustrates these basic concepts on a PRISM model that defines a discrete-time Markov chain (DTMC).

// Variant of a random walk

dtmc

module M

	x : [0..3] init 0;
	y : [0..1] init 0;

	[] y=0 & x<3 -> 0.5:(x'=max(x-1,0)) + 0.4:(x'=x+1) + 0.1:(x'=x+1)&(y'=1);
	[] y=0 & x=3 -> true;
	[] y=1 -> (y'=0);

endmodule
Download: walk-var.prism

The model's type (discrete-time Markov chain) is denoted by the initial dtmc keyword. It contains one module M whose state is defined by two integer-valued variables x and y, with ranges [0..3] and [0..1], respectively. It models a variant of a one-sided, one-dimensional random walk: it repeatedly randomly increments or decrements the value of x by one, until x reaches value 3. This only happens when variable y equals 0. On each increment of x, there is a chance that the value of y is flipped to 1. It will then be reset to 0 one step later.

The resulting Markov chain, whose states take the form (x,y), is shown below.

Markov chain for the random walk

Commands

A module's definition includes its variables, discussed in more detail later, and its commands. Each command comprises a guard and a probabilistic update. The basic form is:

[action] guard -> prob_1 : update_1 + ... + prob_n : update_n;

The guard is a predicate over all the variables in the model, indicating when the command is enabled. Each individual update update_i describes a possible outcome of the command being executed, defined by giving the new values of the module's variables, with x'=... denoting the new value of variable x. For a Markov chain, as above, each update update_i is assigned a probability prob_i, and the probabilities in the command must sum to one.

Commands have an optional action, between the initial pair of square brackets. These have multiple uses, including labelling nondeterministic choices in MDPs and synchronisation between commands in different modules, which are discussed in more detail later. The current example omits actions.

A simple command looks like:

[] x=0 -> 0.8:(x'=1) + 0.2:(x'=2);

which, when variable x has value 0, randomly updates it to either 1 or 2, with probability 0.8 or 0.2, respectively.

The right-hand side of an update can be an expression in terms of the current values of the model's variables, as in the first command of the walk-var.prism example above:

[] y=0 & x<3 -> 0.5:(x'=max(x-1,0)) + 0.4:(x'=x+1) + 0.1:(x'=x+1)&(y'=1);

where (x'=x+1) increments x by 1 and (x'=max(x-1,0)) decrements it by 1, but ensures that it does not go below 0. Updates to multiple variables are concatenated with &, as in the last update above, which increments x and flips the value of y to 1. If a variable is not mentioned in an update, its value is assumed to remain unchanged, i.e., (x'=x+1) above is equivalent to (x'=x+1)&(y'=y).

Thanks to its guard, the command above is enabled whenever y=0 and x<3. It therefore defines the behaviour for three of the states in the Markov chain shown above: (0,0), (1,0) and (2,0). For simple Markov chain models like the above, we will usually assume that the guards are disjoint. This will usually not be the case for models with nondeterminism or models with synchronisation between modules.

If there are no enabled commands in some reachable state of the model, this is referred to as a deadlock state. PRISM's default behaviour is to add (probability 1) self-loops to such states and emit a warning.

Updates

If a probability is omitted, it is assumed to be one:

[] y=1 -> (y'=0);

and true is used to denote an empty update where no variable's value changes:

[] y=0 & x=3 -> true;

Changes to multiple variables in an update happen simultaneously. So, for example, this command updates y to 0, not 1:

[] x=0 & y=0 -> (x'=1)&(y'=x);

Variables

Variables are used to describe the state space of a model. PRISM supports just a few simple types of variables: they can either be (finite ranges of) integers or Booleans (we ignore clocks for now, which are used in real-time models).

Variable declarations

As in the earlier example, variable declarations are usually placed within a module definition. In fact, these are local variables and it is also possible to declare global variables. This distinction is discussed later in the context of composing multiple modules.

The typical form of a variable declaration is:

name : type init initial_value;

where name is a valid identifier. The most commonly used type is an integer with bounded range, specified as [lower..upper], as in the earlier walk-var.prism example:

x : [0..3] init 0;

A Boolean variable is declared as, for example:

b : bool init false;

The initial value of a variable can be omitted from its declaration, in which case it starts with its default value: the lowest value in the range for an integer, or false for a Boolean. Thus, the variable declarations shown below are equivalent to the ones above.

x : [0..3];
b : bool;

All the above examples are variables of bounded range. In some cases, this restriction can be relaxed, for example when using techniques such as statistical model checking or fast adaptive uniformisation which do not exhaustively explore the state space of a model. In these cases, integer variables with unbounded ranges can be used:

x : int init 1;
y : int;

For variable y above, where the initial value is omitted, the initial value is taken to be 0. PRISM's explicit engine can also be applied to models with unbounded integer variables, as long as the reachable state space of the model remains finite.

Multiple initial states

The above examples assume that the model has a single initial state, defined by the initial values of each of its variables. It is possible to specify that a model has multiple initial states. This is done using the init...endinit construct, which can be placed anywhere in the file except within a module definition, and removing any initial values from variable declarations. Between the init...endinit is a predicate over all variables: any state that satisfies this predicate is an initial state.

For example, given the following variable declarations:

x : [0..3];
b : bool;

this definition:

init x<2 endinit

results in a model with four initial states: (0,false), (0,true), (1,false) and (1,true).

Constants, labels and formulas

Constants

PRISM models often contain constants, which can be used to parameterise some values within the model, such as the range of a variable or the probability associated with an update. These constants can then appear in expressions anywhere in the model. For example, we can rewrite the earlier walk-var.prism with constants, making it much easier to change the size of the random walk or its probabilities:

// Variant of a random walk

dtmc

// Max value of random walk
const int N = 3;
// Probability of increment
const double p = 0.5;
// Probability of changing y when incrementing
const double q = 0.2;

module M

	x : [0..N] init 0;
	y : [0..1] init 0;

	[] y=0 & x<N -> 1-p:(x'=max(x-1,0)) + p*(1-q):(x'=x+1) + p*q:(x'=x+1)&(y'=1);
	[] y=0 & x=N -> true;
	[] y=1 -> (y'=0);

endmodule
Download: walk-var-consts.prism

Constants can be defined anywhere in a model file (but outside its modules) and can be of type integer, double or Boolean. The value of a constant can be specified as any constant expression of an appropriate type, and can also refer to the values of other constants. Examples of constant definitions are:

const int size = 10;
const double prob_fail = 1/size;
const bool enabled = true;

It is also possible to leave the values of one or more constants undefined, which allows them to be specified at the time of model checking, or to facilitate experiments over ranges of values:

const int size;
const double prob_fail = 1/size;

Labels

Models can be annotated with labels, which are used to identify sets of states that are of particular interest. Primarily, these are used when specifying properties and are in this sense synonymous with the notion of atomic propositions in temporal logic.

A label is defined by a Boolean expression, and its name is written using quotation marks ("..."), as illustrated in the following examples:

label "top" = x=N;
label "safe" = temp<=100 | alarm=true;
label "fail" = temp>100 & alarm=false;

Unlike constants, though, labels cannot be used to define other labels, and cannot appear in other parts of the model, such as guards or updates.

Formulas

The PRISM language supports formulas, which are used to avoid duplication of commonly repeated expressions within a model definition. A formula definition gives its name (a valid identifier) and an expression that defines it. The latter can be any valid expression, of arbitrary type, and including constants, variables or other formulas. The formula name can then be used as shorthand for the expression anywhere that an expression might usually be accepted. A formula is defined as follows:

formula num_tokens = q1+q2+q3+q4+q5;

It can then be used anywhere within that file, as for example in this command:

[] p1=2 & num_tokens=5 -> (p1'=4);

The effect is exactly as if the following had been typed:

[] p1=2 & (q1+q2+q3+q4+q5)=5 -> (p1'=4);

Formulas defined in a model can also be used when specifying its properties. Unlike labels, formulas can be of any type, not just Boolean, and their names are written without quotation marks.

Actions and nondeterminism

The examples presented so far have been DTMCs, which means that each state has one or more outgoing transitions with associated probabilities that sum to one. Another core model type supported by PRISM is the Markov decision process (MDP), which allows for nondeterminism in the model. In this case, each state can have several choices, each of which defines a probability distribution over successor states. Often, but not always, these choices are labelled with actions.

In the PRISM language, nondeterminism can be modelled by allowing the guards of its commands to overlap. Each enabled command in a state defines a separate choice, and its (optional) action label is specified using the square brackets at the start of the command.

An example MDP

The following example represents a classic MDP, the "chain" model [Str00]. There are N states in a chain, and in each one there are two possible actions: a, which moves one step along the chain, and b, which goes back to the start. But actions are not completely reliable: with probability slip, the other action happens instead.

// A "chain" MDP: At each step, choose action a (move along the chain) or b
// (go back to the start), but with probability slip, the other one happens

mdp

// Number of states in the chain
const int N = 4;
// Probability that the chosen action slips
const double slip = 0.2;

module chain

	s : [0..N-1] init 0;

	[a] true -> 1-slip : (s'=min(s+1,N-1)) + slip : (s'=0);
	[b] true -> 1-slip : (s'=0) + slip : (s'=min(s+1,N-1));

endmodule
Download: chain.prism

The keyword mdp indicates that the model is an MDP. The module has a single variable s representing the position in the chain, which ranges from 0 to N-1 using a constant N (here, 4).

The two commands have the guard true, so both are enabled in every state. In the resulting MDP, each state has two choices, labelled a and b. For example, in state s=0, there are two choices:

  • a: move to state s=1 with probability 0.8, or stay in s=0 with probability 0.2
  • b: stay in s=0 with probability 0.8, or move to state s=1 with probability 0.2

The full MDP is shown below, where each state is labelled with its value of s.

The MDP for the chain example

Actions

The commands above are labelled with actions a and b, written between the square brackets, e.g.:

[a] true -> 1-slip : (s'=min(s+1,N-1)) + slip : (s'=0);

For an MDP, these actions play several roles. Firstly, they allow the definition of policies (referred to as "strategies" in PRISM), specifying which action to take in each state in order to satisfy or optimise some property. Actions can also be used (for all model types, not just MDPs) to define rewards and to enforce synchronisation between commands in different modules.

However, actions are optional. For an MDP, omitting them from a command ([]) results in unlabelled choices. For example these commands:

[] x<5 -> (x'=x+1);
[] x>2 -> (x'=x-1);

result, in states x=3 and x=4, in two unlabelled choices incrementing or decrementing x.

In similar fashion, PRISM allows the definition of MDPs in which the choices from a state have the same action (technically, this is a probabilistic automaton [Seg95], rather than an MDP):

[a] x<5 -> (x'=x+1);
[a] x>2 -> (x'=x-1);
[b] x=3 -> true;

In both cases (unlabelled choices and duplicate actions), restrictions may then be imposed on the generation of policies/strategies.

Local nondeterminism

We refer to the nondeterminism arising from overlapping guards in a single module as local nondeterminism. In MDPs comprising multiple modules, nondeterminism also arises due to the concurrent interleaving of its commands' execution.

In models that do not include nondeterminism, overlapping guards are treated differently. In particular, in a DTMC, if several commands are enabled in a state, it is assumed that one of them is picked uniformly at random. For example, given the following model:

dtmc

module M

    x : [0..3] init 0;
    
    [] x=0 -> 0.1:(x'=1) + 0.9:(x'=2);
    [] x=0 -> (x'=3);
    [] x>0 -> true;
    
endmodule

the first two overlapping commands result in state x=0 of the DTMC having three outgoing transitions, to states x=1, x=2 and x=3, with probabilities 0.05, 0.45 and 0.5, respectively.

Continuous time

The models seen so far, DTMCs and MDPs, are discrete-time: they move from state to state in discrete time steps. A continuous-time Markov chain (CTMC) instead permits real-valued time delays between the occurrence of transitions. More precisely, each transition of a CTMC has a rate, rather than a probability, and the time taken for the transition to happen is a random delay, which is exponentially distributed with that rate. A transition with rate r takes, on average, time 1/r: the higher the rate, the sooner the transition is likely to happen. CTMCs are widely used to model systems such as computer networks and queueing systems, reliability of hardware, and biochemical reaction networks.

An example CTMC

The following CTMC models a system of N identical components (here, 3), each of which may fail, and a repair unit, which repairs failed components one at a time. Each component fails at rate lambda, i.e., on average it works for time 1/lambda = 10 before failing, and a repair takes, on average, time 1/mu = 0.5.

// N identical components, each of which fails at rate lambda,
// and a single repair unit, which repairs them one at a time at rate mu

ctmc

const int N = 3; // number of components
const double lambda = 0.1; // failure rate of each component (mean time to failure: 10)
const double mu = 2; // repair rate (mean repair time: 0.5)

module components

	f : [0..N] init 0; // number of failed components

	[fail]   f<N -> (N-f)*lambda : (f'=f+1);
	[repair] f>0 -> mu : (f'=f-1);

endmodule
Download: repair.prism

A CTMC model is written in the same way as a DTMC, with commands made up of guards and updates, but with the model type ctmc, and with rates, rather than probabilities, attached to updates. The rate of failure here depends on the state: when f components have failed, N-f are still working, and the first of them fails at rate (N-f)*lambda, since rates of independent events add up (see below). Only one component is repaired at a time, so repairs happen at rate mu, whenever at least one component has failed.

The resulting CTMC, whose states are the values of f, is shown below, with each transition labelled by its rate.

The repair CTMC, with states 0 to 3 in a row: from each state f below 3, a transition to f+1 with rate 0.3, 0.2 and 0.1, respectively; from each state f above 0, a transition back to f-1 with rate 2.

Rates and races

As seen above, the notation used to give rates in a command is similar to that used for probabilities:

[] guard -> rate_1:update_1;
[] guard -> rate_2:update_2;

where each rate_i can be any positive value and is assumed to be 1 if omitted. It is also possible to group updates with the same guard into a single command. So, the above could be written as:

[] guard -> rate_1:update_1 + rate_2:update_2;

In either case, unlike DTMCs, the rates do not need to sum to one. The former approach allows the transitions to be labelled with different actions:

[a] guard -> rate_1:update_1;
[b] guard -> rate_2:update_2;

Unlike MDPs, there is no nondeterminism in a CTMC, and the a and b are just convenient labels for the transitions (or a mechanism for synchronisation between modules, discussed later). Commands with overlapping guards in a CTMC result in multiple transitions being possible in a state, each with its own rate. This is known as a race condition: the transition whose associated delay finishes first is the one that happens. The time until the first of them happens is also exponentially distributed, with a rate equal to the sum of their rates, and each one happens first with probability proportional to its rate. This is why, in the example above, the first failure among N-f working components happens at rate (N-f)*lambda. Similarly, if several transitions from a state lead to the same state, they are combined into one transition with a rate equal to the sum of the individual rates (as, in fact, also happens for probabilities in discrete-time models).

Composition and synchronisation

Most PRISM models involve the parallel composition of several modules, which may interact with each other in various ways. In such cases, the global state of the whole model comprises the local states of all modules, i.e., the values of the local variables of each module. Furthermore, a module can read the values of any other variable in the model (for example, it can refer to it in the guards of its commands) but a module can only write to its own local variables.

The manner in which modules are composed depends on the model type. We start by describing the case for MDPs, which provide a natural model for the parallel composition of probabilistic components, use this to introduce some of the key ideas, notably synchronisation, and then also describe how the composition of modules is handled for CTMCs and DTMCs.

Composing modules in MDPs

The example below illustrates the parallel composition of two modules in an MDP, communicating with each other by reading each other's variables.

// Two parallel processes, reading each others variables

mdp

module P1
	s1 : [0..1] init 0;

	[a] s1=0 -> 0.9:(s1'=1) + 0.1:(s1'=0);
	[a] s1=1 -> (s1'=s2);
endmodule

module P2
	s2 : [0..1] init 0;

	[b] s2=0 -> 0.8:(s2'=1) + 0.2:(s2'=0);
	[b] s2=1 -> (s2'=s1);
endmodule
Download: compose-interleave.prism

Both modules start in local state 0 and randomly move to local state 1 with some probability. When in state 1, they simply copy the other module's state (e.g., (s1'=s2) in module P1), and so return to state 0 if the other module is still in state 0, or remain in state 1 if the other module is in state 1. References to other modules' variables can also appear in guards, but here are just used on the right-hand sides of updates.

The resulting MDP is shown below, and comprises global states of the form (s1,s2). Although it is not necessary, we labelled the commands of the two modules with actions, a and b, which helps identify which module is responsible for each transition. When both modules have an enabled command (all states in this example), the choice between which one executes is nondeterministic. So, even though neither module has overlapping guards, all states of the MDP have a choice, between actions a and b.

Parallel composition as an MDP

The above example had no local nondeterminism. If we changed the second module to the version shown below, where its initial choice to move to state 1 or stay in state 0 is nondeterministic, then states (0,0) and (1,0) in the MDP above would have three nondeterministic choices, two labelled with b and one with a.

module P2
	s2 : [0..1] init 0;

	[b] s2=0 -> (s2'=1);
	[b] s2=0 -> (s2'=0);
	[b] s2=1 -> (s2'=s1);
endmodule

Synchronisation

Modules can also use synchronisation to coordinate their behaviour. In the above example, modules had distinct actions, a and b, which occurred independently. Commands with the same action label, however, are required to synchronise: both are executed simultaneously, and this only happens when both commands are enabled.

Below, we modify the second commands of the two modules in the previous example, removing the references to the other module's variable and using a shared action c.

// Two parallel processes, synchronising on c

mdp

module P1
	s1 : [0..1] init 0;

	[a] s1=0 -> 0.9:(s1'=1) + 0.1:(s1'=0);
	[c] s1=1 -> (s1'=0);
endmodule

module P2
	s2 : [0..1] init 0;

	[b] s2=0 -> 0.8:(s2'=1) + 0.2:(s2'=0);
	[c] s2=1 -> (s2'=0);
endmodule
Download: compose-sync.prism

Now, when both modules are in state 1, they synchronise on action c and move to state (0,0). And in state (1,0) or state (0,1), where only one of the c-labelled commands is enabled, the synchronisation cannot occur, so the enabled c-labelled command is blocked:

Parallel composition with synchronisation as an MDP

The actions over which two modules synchronise are those that appear in both modules; any other actions are performed independently.

Synchronising commands can both have probabilistic updates. In the variant below, the first commands of the two modules are both labelled with action a, so they too have to synchronise.

// Two parallel processes, synchronising on both a and c

mdp

module P1
	s1 : [0..1] init 0;

	[a] s1=0 -> 0.9:(s1'=1) + 0.1:(s1'=0);
	[c] s1=1 -> (s1'=0);
endmodule

module P2
	s2 : [0..1] init 0;

	[a] s2=0 -> 0.8:(s2'=1) + 0.2:(s2'=0);
	[c] s2=1 -> (s2'=0);
endmodule
Download: compose-sync-all.prism

Now, in state (0,0), the two modules move together, in a single choice labelled a, whose probability distribution is the product of the distributions of the two commands. For example, both modules move to state 1 with probability 0.9 * 0.8 = 0.72, and only P1 does so with probability 0.9 * 0.2 = 0.18. In states (1,0) and (0,1), however, neither a nor c can occur, since each needs both modules, so these are deadlock states, to which PRISM adds self-loops:

Parallel composition with synchronisation on two actions as an MDP: from state 0,0, a single choice a goes to 1,1, 1,0, 0,1 and 0,0 with probabilities 0.72, 0.18, 0.08 and 0.02

Synchronisation is often used as a simple way to model "sending" data from one module to another. In the example below, module P1 chooses randomly whether to set its local variable s1 to 1 or 2. It then communicates the result of this to module P2 by offering either action c1 or c2 for synchronisation, depending on the value of s1. In isolation, module P2 would exhibit local nondeterminism, but in parallel with P1 only ever performs c1 or c2 in a state.

// Module P1 "sends" a value (1 or 2) to P2, using a different action for each

mdp

module P1

	s1 : [0..2] init 0;

	[a] s1=0 -> 0.9:(s1'=1) + 0.1:(s1'=2);
	[c1] s1=1 -> (s1'=0);
	[c2] s1=2 -> (s1'=0);

endmodule

module P2

	s2 : [0..2] init 0;

	[c1] s2=0 -> (s2'=1);
	[c2] s2=0 -> (s2'=2);
	[d] s2>0 -> (s2'=0);

endmodule
Download: compose-send.prism

We can achieve the same behaviour in another way by simultaneously synchronising on a single action c and module P2 reading the value of s1 as it updates its own variable s2:

// Module P1 "sends" a value (1 or 2) to P2, which reads it while synchronising on c

mdp

module P1

	s1 : [0..2] init 0;

	[a] s1=0 -> 0.9:(s1'=1) + 0.1:(s1'=2);
	[c] s1>0 -> (s1'=0);

endmodule

module P2

	s2 : [0..2] init 0;

	[c] s2=0 -> (s2'=s1);
	[d] s2>0 -> (s2'=0);

endmodule
Download: compose-send-read.prism

Composing modules in CTMCs

For a CTMC, parallel composition between modules works analogously to MDPs, except that the choice between enabled commands is a race condition, not nondeterministic. Consider two commands in different modules that are labelled with actions a and b, where those actions are used only in those modules. Then, in a state where both commands are enabled, each results in a separate outgoing transition, with its own rate. For two commands with a common action c, synchronisation occurs, with both commands being executed simultaneously and the rate of the synchronised transition taken as the product of the two individual rates.

This is illustrated by the model below, in which jobs arrive into an N-place queue and are removed by a server which processes them one at a time.

// An N-place queue and a server

ctmc

const int N = 2;
const double lambda = 1/10;
const double mu = 1/2;
const double gamma = 1/3;

module queue
     q : [0..N];

     [arrive] q<N -> lambda:(q'=q+1);
     [serve] q>0 -> mu:(q'=q-1);
endmodule

module server
     s : [0..1];

     [serve] s=0 -> 1:(s'=1);
     [process] s=1 -> gamma:(s'=0);
endmodule
Download: compose-queue.prism

The CTMC (assuming N=2, as above) is shown below, with the states labelled as q,s.

CTMC for the N-place queue example

In a CTMC, the product of two rates does not always meaningfully represent the rate of a synchronised transition. A common technique, as seen here, is to make one command passive, with rate 1, and the other active, which actually defines the rate for the synchronised transition (in this case, mu * 1 = mu).

Composing modules in DTMCs

In a DTMC, the choice between two enabled commands with non-shared actions is probabilistic, with each command being selected with equal probability. It is much more common, in DTMC models that use multiple modules, to make modules synchronise fully, leaving no situations where a choice between enabled commands is randomised.

Below is a simple example, borrowed from the model of Herman's self-stabilisation algorithm, in which two modules repeatedly move in lockstep, with a probabilistic update that depends on the other module's state. (The second module is defined using module renaming, described below.)

// Two processes from Herman's self-stabilisation algorithm, moving in lockstep

dtmc

module process1

	x1 : [0..1] init 1;
	
	[step] (x1=x2) -> 0.5 : (x1'=0) + 0.5 : (x1'=1);
	[step] !(x1=x2) -> (x1'=x2);
	
endmodule

module process2 = process1 [ x1=x2, x2=x1 ] endmodule
Download: compose-herman.prism

Both commands of each module are labelled with action step, and in every state exactly one of them is enabled, so every transition of the DTMC is a synchronisation of both modules. When the two modules synchronise, the probability of the resulting transition is the product of the probabilities of the two individual updates. So, in states (0,0) and (1,1), where x1=x2, both modules choose a new value at random, giving four transitions, each with probability 0.5 * 0.5 = 0.25; in states (0,1) and (1,0), each module copies the other's value, and the model moves to the other one of these two states with probability 1.

Module renaming

PRISM also supports module renaming, which allows reuse of a module definition when there are several modules with (almost) identical behaviour. Below, we rewrite the compose-interleave.prism example from above, using module renaming to define P2 in terms of P1:

// Two similar parallel processes, defined using module renaming

mdp

const double p1 = 0.9;
const double p2 = 0.8;

module P1
	s1 : [0..1] init 0;

	[a] s1=0 -> p1:(s1'=1) + 1-p1:(s1'=0);
	[a] s1=1 -> (s1'=s2);
endmodule

module P2 = P1 [ s1=s2, s2=s1, a=b, p1=p2 ] endmodule
Download: compose-rename.prism

The syntax is as follows:

module Mnew = Mold [ old1=new1, old2=new2, ... ] endmodule

where the renames old1=new1, old2=new2, ... specify how identifiers appearing in the original module Mold are to be renamed in the new module Mnew. The renaming is done at a textual level, so variables, constants and actions can all be renamed in this way. In the example, s1 has to be renamed, in order to give P2 a distinct variable s2, but we also need to rename s2, since P1 refers to it in its updates, and the action a. Note also how we convert the literal probabilities (0.9 and 0.8) into constants, which allows them to differ in the second module.

Take care when using module renaming in conjunction with formulas. Expansion of formulas is done before module renaming so, if a module which uses formulas is renamed to another module, it is the contents of the formula which will be renamed, not the formula itself.

Global variables

As seen in several of the examples above, variables within a module are considered to be local variables, in that they can only be written by that module. They can however be read by any module. PRISM also allows global variables, which can be written to, as well as read, by all modules. Like local variables, these can be integers or Booleans. Global variables are declared in identical fashion to a module's local variables, except that the declaration must not be inside the definition of any module. Some example declarations are as follows:

global g : [1..10];
global b : bool init true;

A global variable can be modified by any module and provides another way for modules to interact. An important restriction on the use of global variables is the fact that commands which synchronise with other modules cannot modify global variables. PRISM will detect this and report an error.

Process algebra operators

To make the concept of synchronisation described above more powerful, PRISM allows you to define precisely the way in which the set of modules are composed in parallel. This is specified using the system ... endsystem construct, placed at the end of the model description, which should contain a process-algebraic expression. This expression should feature each module exactly once, and can use the following (CSP-based) operators:

  • M1 || M2: alphabetised parallel composition of modules M1 and M2 (synchronising on only actions appearing in both M1 and M2)
  • M1 ||| M2: asynchronous parallel composition of M1 and M2 (fully interleaved, no synchronisation)
  • M1 |[a,b,...]| M2: restricted parallel composition of modules M1 and M2 (synchronising only on actions from the set {a, b,...})
  • M / {a,b,...}: hiding of actions {a, b, ...} in module M
  • M {a<-b,c<-d,...}: renaming of actions a to b, c to d, etc. in module M

The first two types of parallel composition (|| and |||) are associative and can be applied to more than two modules at once. When evaluating the expression, the hiding and renaming operators bind more tightly than the three parallel composition operators. No other rules of precedence are defined and parentheses should be used to specify the order in which modules are composed.

Some examples of expressions which could be included in the system ... endsystem construct are as follows:

  • (station1 ||| station2 ||| station3) |[serve]| server
  • ((P1 |[a]| P2) / {a}) || Q
  • ((P1 |[a]| P2) {a<-b}) |[b]| Q

When no parallel composition is specified by the user, PRISM implicitly assumes an expression of the form M1 || M2 || ... containing all of the modules in the model. For a more formal definition of the process algebra operators described above, check the semantics of the PRISM language, available from the "Documentation" section of the PRISM website.

Costs and rewards

PRISM supports the specification and analysis of properties based on costs and rewards. This means that it can be used to reason, not just about the probability that a model behaves in a certain fashion, but about a wider range of quantitative measures relating to model behaviour. For example, PRISM can be used to compute properties such as "expected time", "expected number of lost messages" or "expected energy consumption".

To achieve this, PRISM allows states and transitions to be annotated with numerical values, representing for example the time taken for a transition or its energy consumption. Although these examples are all "costs" (which we would intuitively like to minimise), following classical definitions of MDPs in the literature, PRISM consistently refers to these values as rewards. In practice, though, they equally well represent costs. This section describes how to specify rewards in a PRISM model. We later describe reward-based property specifications.

State rewards

Rewards are associated with models using rewards ... endrewards constructs, which can appear anywhere in a model file except within a module definition. These constructs contain one or more reward items. Consider the following simple example, which defines state rewards for a model, i.e., a mapping just from its states to numerical values:

rewards "r1"
    true : 1;
endrewards

This defines a reward structure with name r1 (the name is optional) which assigns a reward of 1 to every state of the model. It comprises a single reward item, the left part of which (true) is a guard and the right part of which (1) is a reward. States of the model which satisfy the predicate in the guard are assigned the corresponding reward. More generally, state rewards can be specified using multiple reward items, each of the form guard : reward;, where guard is a predicate (over all the variables of the model) and reward is an expression (containing any variables, constants, etc. from the model). For example:

rewards "r2"
    x=0 : 100;
    x>0 & x<10 : 2*x;
    x=10 : 100;
endrewards

assigns a reward of 100 to states satisfying x=0 or x=10 and a reward of 2*x to states satisfying x>0 & x<10. Note that a single reward item can assign different rewards to different states, depending on the values of model variables in each one. Any states which do not satisfy the guard of any reward item will have no reward assigned to them. For states which satisfy multiple guards, the reward assigned to the state is the sum of the rewards for all the corresponding reward items.

Transition rewards

Rewards can also be assigned to transitions of a model. These are specified in a similar fashion to state rewards, within the rewards ... endrewards construct. Reward items describing transition rewards are of the form [action] guard : reward;, the interpretation being that transitions from states which satisfy the guard guard and are labelled with the action action acquire the reward reward. For example:

rewards "r3"
    [] true : 1;
    [a] true : x;
    [b] true : 2*x;
endrewards

assigns a reward of 1 to all transitions in the model with no action label, and rewards of x and 2*x to all transitions labelled with actions a and b, respectively.

As is the case for states, multiple reward items can specify rewards for a single transition, in which case the resulting reward is the sum of all the individual rewards. A model description can specify rewards for both states and transitions. These are all placed together in a single rewards...endrewards construct.

Multiple reward structures

A PRISM model will often have multiple reward structures, for example:

rewards "total_time"
    true : 1;
endrewards

rewards "num_failures"
    [fail] true : 1;
endrewards

The first assigns a reward of 1 to every state, which, for a CTMC, accumulates as time passes; the second counts transitions labelled fail, as in the repair example. A property can then refer to a reward structure by its name, e.g., R{"num_failures"}=? [ C<=10 ] gives the expected number of failures up to time 10.

Property specification

In order to verify or analyse a probabilistic model with PRISM, one or more properties of the model are specified. This is done using the PRISM property specification language, which is based on temporal logic and subsumes several well-known logics:

  • PCTL (probabilistic computation tree logic)
  • PLTL (probabilistic linear temporal logic)
  • PCTL* (which subsumes PCTL and PLTL)
  • CSL (continuous stochastic logic)
  • CTL (computation tree logic)
  • LTL (linear temporal logic)

and also includes reward-based properties and various other extensions.

We give a few illustrative examples of properties below, and then describe the property specification language in more detail in the rest of this section. The presentation given here is relatively informal. For the precise syntax and semantics of the various logics, see [HJ94],[BdA95] for PCTL, [ASSB96],[BKH99] for CSL and, for example, [Bai98] for LTL and PCTL*. You can also find various pointers to useful papers in the About and Documentation sections of the PRISM website.

Examples

Some simple examples of specifications in the PRISM property specification language, along with their natural language interpretations, are given below:

P>=1 [ F "terminate" ]

"the algorithm eventually terminates with probability 1"

P<0.1 [ F<=100 num_errors > 5 ]

"the probability that more than 5 errors occur within the first 100 time units is less than 0.1"

S<0.01 [ num_sensors < min_sensors ]

"in the long-run, the probability that an inadequate number of sensors are operational is less than 0.01"

R{"time"}<=10 [ F "terminate" ]

"the expected time for the algorithm to terminate is at most 10"

Note that the above properties are all assertions, i.e., ones to which we would expect a "yes" or "no" answer. This is because all references to probabilities or rewards are associated with an upper or lower bound which can be checked to be either true or false. In PRISM, we can also directly specify numerical properties:

P=? [ !proc2_terminate U proc1_terminate ]

"the probability that process 1 terminates before process 2 does"

Pmax=? [ F<=T messages_lost > 10 ]

"the maximum probability that more than 10 messages have been lost by time T"

Rmax=? [ F "terminate" ]

"the worst-case expected termination time for the algorithm"

Furthermore, PRISM makes it easy to combine such properties into more complex expressions, compute their values for a range of parameters and plot graphs of the results using experiments. This is often a very useful way of identifying interesting patterns or trends in the behaviour of a system. See the "Case studies" section of the PRISM website for many examples of this kind of analysis.

Contents

Property specification for real-time, partially observable and uncertain models is described later.

Properties files

Properties can be specified individually to PRISM or can be collated together into a properties file, a plain text file with file extension .props. This contains one or more properties, each of which should be terminated with a semicolon (but the parser is not strict on this). Properties can refer to various aspects of the model to which they relate (variable names, labels, etc.) but can also define further constants and labels in the same style as in model files. Comments are allowed too. An example file is:

const int T;
const int k;

label "phase1" = s=4 & phase=1;

// The algorithm eventually terminates successfully with probability 1
P>=1 [ F "terminate" ];

// The probability of completing phase 1 within time T
P=? [ F<=T "phase1" ];

// The expected time to complete phase k
R=? [ F s=4 & phase=k ];
Download: examples.props

As in the examples above, labels (such as "terminate" or "phase1") are frequently used in properties to identify sets of states. These are essentially the same as atomic propositions in temporal logic. Labels are just Boolean-valued expressions over the state variables of the model (and, optionally, constants). Such expressions can also be used directly in properties, without labels, as in the final example above. This is useful when a property is parameterised by a constant.

Two special cases of labels are the "init" and "deadlock" labels which are always defined. These are true in initial states of the model and states where deadlocks were found (and, usually, fixed by adding self-loops), respectively.

Property names

For convenience, properties can be annotated with names, as shown in the following example:

"surely_terminate": P>=1 [ F "terminate" ];

which gives the name "surely_terminate" to the property.

The name can be referred to when telling PRISM which properties to model check. It can also be referred to in other properties, as in this example of a nested property:

// "Safe" states, where we can return to the base
// in at most 10 time units with probability at least 0.99
"safe_return": P>=0.99 [ F<=10 "base" ];

// What is the probability of always remaining in the safe states?
"stay_safe": P=? [ G "safe_return" ];

Notice that the syntax for referring to named properties is identical to the syntax for labels. For this reason, property names must be disjoint from those of any existing labels.

The P operator

One of the most important operators in the PRISM property specification language is the P operator, which is used to reason about the probability of an event's occurrence. This operator was originally proposed in the logic PCTL but also features in the other logics, such as CSL. The P operator is applicable to all types of models supported by PRISM.

Informally, the property:

P bound [ pathprop ]

is true in a state of a model if "the probability that path property pathprop is satisfied by the paths from the state meets the bound bound". A typical example of a bound would be:

P>0.98 [ pathprop ]

which means: "the probability that pathprop is satisfied by the paths from the state is greater than 0.98".

More precisely, bound can be any of >=p, >p, <=p or <p, where p is any constant expression evaluating to a double in the range [0,1], for example:

P>=1 [ pathprop ]
P<q [ pathprop ]
P<=(1-2*q) [ pathprop ]

The types of path property supported by PRISM and their semantics will be discussed shortly.

Nondeterminism

Many of the model types supported by PRISM exhibit nondeterminism, notably MDPs and their various generalisations, such as PTAs and POMDPs. These models use the notion of a policy (called a strategy in PRISM, and also sometimes referred to as a scheduler or adversary) which defines one possible way of resolving the nondeterministic choices in a model.

For such models, the meaning of the property P bound [ pathprop ] is: "the probability that pathprop is satisfied meets the bound bound for all possible policies/strategies". This means that properties using the P operator effectively reason about the minimum or maximum probability, over all possible resolutions of nondeterminism, that a certain type of behaviour is observed.

Numerical properties

It is very often useful to compute the actual probability that some behaviour of a model is observed, rather than just verifying whether or not the probability is above or below a given bound. Hence, PRISM allows the P operator to take the following numerical form:

P=? [ pathprop ]

This asks "what is the probability that pathprop is satisfied?" and returns a numerical rather than a Boolean value. The S and R operators, discussed later, can also be used in this way.

For nondeterministic models such as MDPs (discussed above), either minimum or maximum probability values can be queried in this way:

Pmin=? [ pathprop ]
Pmax=? [ pathprop ]

which return the minimum and maximum probabilities, respectively, over all policies/strategies. As well as computing an optimal value, PRISM can also generate a strategy that achieves it.

PRISM properties generalise the syntax for expressions in the PRISM language so further numerical properties can be constructed by combining them with arithmetic operators and functions, e.g.:

1 - P=? [ pathprop ]

"the probability that pathprop is not true"

P=? [ F fail_A ] / P=? [ F any_fail ]

"the (conditional) probability that component A eventually fails, given that at least one component fails"

Path properties

PRISM supports a wide range of path properties that can be used with the P operator. A path property is a formula that evaluates to either true or false for a single path in a model. Here, we review some of the simpler properties that feature a single temporal operator, as used for example in the logics PCTL and CSL. Later, we briefly describe how PRISM also supports more complex LTL-style path properties.

The basic different types of path property that can be used inside the P operator are:

  • X : "next"
  • U : "until"
  • F : "eventually" (sometimes called "future")
  • G : "always" (sometimes called "globally")
  • W : "weak until"
  • R : "release"

In the following sections, we describe each of these temporal operators. We then discuss the (optional) use of time bounds with these operators. Finally, we also discuss LTL-style path properties.

"Next" path properties

The property X prop is true for a path if prop is true in its second state. An example of this type of property, used inside a P operator, is:

P<0.01 [ X y=1 ]

which is true in a state if "the probability of the expression y=1 being true in the next state is less than 0.01".

"Until" path properties

The property prop1 U prop2 is true for a path if prop2 is true in some state of the path and prop1 is true in all preceding states. A simple example of this would be:

P>0.5 [ z<2 U z=2 ]

which is true in a state if "the probability that z is eventually equal to 2, and that z remains less than 2 up until that point, is greater than 0.5".

"Eventually" path properties

The property F prop is true for a path if prop eventually becomes true at some point along the path. The F operator is in fact a special case of the U operator (you will sometimes see F prop written as true U prop). A simple example is:

P<0.1 [ F z>2 ]

which is true in a state if "the probability that z is eventually greater than 2 is less than 0.1".

"Globally" path properties

Whereas the F operator is used for "reachability" properties, G represents "invariance". The property G prop is true of a path if prop remains true at all states along the path. Thus, for example:

P>=0.99 [ G z<10 ]

states that, with probability at least 0.99, z never exceeds 10.

"Weak until" and "release" path properties

Like F and G, the operators W and R are derivable from other temporal operators.

Weak until (a W b), which is equivalent to (a U b) | G a, requires that a remains true until b becomes true, but does not require that b ever becomes true (i.e., a remains true forever). For example, a weak form of the until example used above is:

P>0.5 [ z<2 W z=2 ]

which states that, with probability greater than 0.5, either z is always less than 2, or it is less than 2 until the point where z is 2.

Release (a R b), which is equivalent to !(!a U !b), informally means that b is true until a becomes true, or b is true forever.

Time-bounded path properties

All of the temporal operators given above, with the exception of X, have time-bounded variants, where an additional bound is imposed on the time taken for the property to be satisfied. For discrete-time models (e.g., DTMCs and MDPs), this is a step bound, counting the number of transitions that have occurred, often also referred to as finite-horizon properties (as opposed to the "infinite-horizon" properties). For continuous-time models (notably CTMCs), this is a bound the actual time elapsed.

The most common case is to use an upper time bound, i.e., of the form "<=t" or "<t", where t is a PRISM expression evaluating to a constant, non-negative value.

For example, a bounded until property prop1 U<=t prop2, is satisfied along a path if prop2 becomes true within t steps and prop1 is true in all states before that point. A typical example of this would be:

P>=0.98 [ y<4 U<=7 y=4 ]

which is true in a state if "the probability of y first exceeding 3 within 7 time units is greater than or equal to 0.98". Similarly:

P>=0.98 [ F<=7 y=4 ]

is true in a state if "the probability of y being equal to 4 within 7 time units is greater than or equal to 0.98" and:

P>=0.98 [ G<=7 y=4 ]

is true if the probability of y staying equal to 4 for 7 time units is at least 0.98.

The time bound can be an arbitrary (constant) expression, but note that you may need to bracket it, as in the following example:

P>=0.98 [ G<=(2*k+1) y=4 ]

You can also use lower time-bounds (i.e. >=t or >t) and time intervals [t1,t2], e.g.:

P>=0.98 [ F>=10 y=4 ]
P>=0.98 [ F[10,20] y=4 ]

which refer to the probability of y becoming equal to 4 after 10 or more time units, and after between 10 and 20 time-units respectively.

For CTMCs, the time bounds can be any (non-negative) numerical values - they are not restricted to integers, as for discrete-time models. For example:

P>=0.25 [ y<=1 U<=6.5 y>1 ]

means that the probability of y being greater than 1 within 6.5 time-units (and remaining less than or equal to 1 at all preceding time-points) is at least 0.25.

Transient probabilities

We can also use the bounded F operator to refer to a single time instant, e.g.:

P=? [ F[10,10] y=6 ]

or, equivalently:

P=? [ F=10 y=6 ]

both of which give the probability of y being 6 at time instant 10.

LTL-style path properties

PRISM supports probabilistic model checking of the temporal logic LTL (and, in fact, PCTL*). LTL provides a richer set of path properties for use with the P operator, by permitting temporal operators to be combined. Here are a few examples of properties expressible using this functionality:

P>0.99 [ F ( "request" & (X "ack") ) ]

"with probability greater than 0.99, a request is eventually received, followed immediately by an acknowledgement"

P>=1 [ G F "send" ]

"a message is sent infinitely often with probability 1"

P=? [ F G ("error" & !"repair") ]

"the probability of an error occurring that is never repaired"

Note that logical operators have precedence over temporal ones, so you will often need to include parentheses when using logical operators, e.g.:

P=? [ (F "error1") & (F "error2") ]

For temporal operators, unary operators (such as F, G and X) have precedence over binary ones (such as U). Unary operators can be nested, without parentheses, but binary ones cannot.

So, these are allowed:

P=? [ F X X X "a" ]
P=? [ "a" U X X X "error" ]
P=? [ ("a" U "b") U "c" ]

but this is not:

P=? [ "a" U "b" U "c" ]

The S operator

The S operator is used to reason about the steady-state behaviour of a model, i.e., its behaviour in the long-run or equilibrium. PRISM only provides support for DTMCs and CTMCs. The definition of steady-state (long-run) probabilities for finite DTMCs and CTMCs is well defined (see e.g. [Ste94]). Informally, the property:

S bound [ prop ]

is true in a state s of a DTMC or CTMC if "starting from s, the steady-state (long-run) probability of being in a state which satisfies the (Boolean-valued) PRISM property prop, meets the bound bound". A typical example of this type of property would be:

S<0.05 [ queue_size / max_size > 0.75 ]

which means: "the long-run probability of the queue being more than 75% full is less than 0.05".

Like the P operator, the S operator can be used in a numerical form, which returns the actual probability value, e.g.:

S=? [ queue_size / max_size > 0.75 ]

and can be further customised with the use of filters.

Reward-based properties

PRISM models can be augmented with information about rewards (or, equivalently, costs). The tool can then analyse properties which relate to the expected values of these rewards. This is achieved using the R operator, which works in a similar fashion to the P and S operators, and can be used either in a Boolean-valued query, e.g.:

R bound [ rewardprop ]

where bound takes the form <r, <=r, >r or >=r for an expression r evaluating to a double, or a real-valued query, e.g.:

R query [ rewardprop ]

where query is =?, min=? or max=?. In the latter case, filters can be used, as for the P and S operators.

Informally, "R bound [ rewardprop ]" is true in a state of a model if "the expected reward associated with rewardprop of the model when starting from that state" meets the bound bound and "R query [ rewardprop ]" returns the actual expected reward value.

There are various different types of reward properties:

  • "reachability reward": F prop
  • "co-safe LTL reward": e.g. F (prop1 & (F prop2))
  • "cumulative reward": C<=t
  • "total reward": C
  • "instantaneous reward": I=t
  • "steady-state reward": S

Below, we consider each of these cases in turn. The descriptions here are kept relatively informal. Precise definitions for most of these can be found in, for example, [KNP07a] (for DTMCs and CTMCs) or [FKNP11] (for MDPs).

For all but instantaneous reward properties, it is required that rewards are non-negative.

"Reachability reward" properties

"Reachability reward" properties associate a reward with each path of a model. More specifically, they refer to the reward accumulated along a path until a certain point is reached. The manner in which rewards are accumulated depends on the model type. For DTMCs and MDPs, the total reward for a path is the sum of the state rewards for each state along the path plus the sum of the transition rewards for each transition between these states. The situation for CTMCs is similar, except that the state reward assigned to each state of the model is interpreted as the rate at which rewards are accumulated in that state, i.e., if t time units are spent in a state with state reward r, the reward accumulated in that state is r x t. Hence, the total reward for a path in a CTMC is the sum of these products for each state along the path plus the sum of the transition rewards for each transition between these states.

The reward property "F prop" corresponds to the reward accumulated along a path until a state satisfying property prop is reached, where rewards are accumulated as described above. State rewards for the prop-satisfying state reached are not included in the accumulated value. In the case where the probability of reaching a state satisfying prop is less than 1, the reward is equal to infinity.

A common application of this type of property is the case when the rewards associated with the model correspond to time. One can then state, for example:

R<=9.5 [ F z=2 ]

which is true in a state if "the expected time taken to reach a state where z equals 2 is less than or equal to 9.5".

"Co-safe LTL reward" properties

These generalise the "reachability" properties above. Again, reward is accumulated along a path up until some point, but this is specified in a more general way, by giving a formula in the co-safe fragment of linear temporal logic (LTL). Rewards are accumulated up until the point where the formula is first satisfied. For example, this property, for a DTMC or CTMC, queries the expected reward accumulated until first goal equals 1 and then subsequently goal equals 2:

R=? [ F (goal=1 & F goal=2) ]

and this property, for an MDP, minimises the expected reward until loc equals 1, having passed only through states where loc never equals 4:

Rmin=? [ loc!=4 U loc=1 ]

As for reachability rewards, if the probability of satisfying the formula is less than 1, then the expected reward is defined to be infinite.

Intuitively, a co-safe formula is one that is satisfied within a finite period of time, and remains true for ever once it becomes true for the first time. For simplicity, PRISM actually supports the syntactic co-safe fragment of LTL, which is defined as any LTL formula that only uses the temporal operators F, U and X (but not G, for example). PRISM's notation for LTL formulas is described in "LTL-style path properties".

"Cumulative reward" properties

"Cumulative reward" properties also associate a reward with each path of a model, but only up to a given time bound. The property C<=t corresponds to the reward accumulated along a path until t time units have elapsed. For DTMCs and MDPs, the bound t must evaluate to an integer; for CTMCs, it can evaluate to double. State and transition rewards along a path are accumulated exactly as described in the previous section.

A typical application of this type of property is the following. Consider a model of a disk-drive controller which includes a queue of incoming disk requests. If we assign a reward of 1 to each transition of the model corresponding to the situation where an incoming request is lost because the queue is full, then the property:

R=? [ C<=15.5 ]

would return, for a given state of the model, "the expected number of lost requests within 15.5 time units of operation".

"Total reward" properties

"Total reward" properties refer to the accumulation of state and transition rewards in the same way as for "reachability reward" and "cumulative reward" properties, but the reward is accumulated indefinitely, i.e., the total reward accumulated along the whole (infinite) path. Note that this means that, unless a path ends up remaining forever in states with zero reward, the total reward will be infinite.

Re-using the reward structure in the previous example,

R=? [ C ]

returns "the expected total number of lost requests".

"Instantaneous reward" properties

"Instantaneous reward" properties refer to the reward of a model at a particular instant in time. The reward property I=t associates with a path the reward in the state of that path when exactly t time units have elapsed. For DTMCs and MDPs, the bound t must evaluate to an integer; for CTMCs, it can evaluate to double.

Returning to our example from the previous section of a model for a disk-request queue in a disk-drive controller, consider the case where the rewards assigned to each state of the model give the current size of the queue in that state. Then, the following property:

R<4.4 [ I=100 ]

would be true in a state of the model if "the expected queue size exactly 100 time units later is less than 4.4". Note that, for this type of reward property, state rewards for CTMCs do not have to refer to rates; they can refer to any instantaneous measure of interest for a state.

"Steady-state reward" properties

Unlike the previous types of property, "steady-state reward" properties relate not to paths, but rather to the reward in the long-run. A typical application of this type of property would be, in the case where the rewards associated with the model correspond to power consumption, the property:

R<=0.7 [ S ]

which is true in a state s if "starting from s, the long-run average power consumption is less than 0.7". As for the S operator, these properties are only supported for DTMCs and CTMCs.

Which reward structure?

In the case where a PRISM model has multiple reward structures you may need to specify which reward structure your property refers to. This is done by placing the information in braces ({}) after the R operator. You can do so either using the name assigned to a reward structure (if any) or using the index (where 1 means the first reward structure in the PRISM model file, 2 the second, etc.). Examples are:

R{"num_failures"}=? [ C<=10.0 ]
R{"time"}=? [ F step=final ]
R{2}=? [ F step=final ]

Note that when using an index to specify the reward structure, you can actually put any expression that evaluates to an integer. This allows you to, for example, write a property of the form R{c}=?[...] where c is an undefined integer constant. You can then vary the value of c in an experiment and compute values for several different reward structures at once.

If you don't specify a reward structure to the R operator, by default, the first one in the model file is used.

Discounts

For the reward operators that refer to accumulated rewards, i.e., F prop, C<=t and C, rewards on DTMCs and MDPs can be discounted using a specified factor. Examples are:

Rmin=? [ F{discount=0.9} "goal" ]
R=? [ C{discount=0.5}<=100 ]
Rmax=? [ C{discount=0.9} ]

With a discount factor dd, a reward earned in the iith step of a path (counting from 0) is multiplied by did^i. For example, for a DTMC, the property R=? [ C{discount=d}<=k ] gives, for a state ss, the value:

Es[ ∑i=0k−1di(ρ(si)+ι(si,si+1))]\mathbb{E}_s\Big[\, \sum_{i=0}^{k-1} d^i \big( \rho(s_i) + \iota(s_i, s_{i+1}) \big) \Big]

where s0s1s2…s_0 s_1 s_2 \ldots is a path starting in s0=ss_0 = s, ρ\rho gives the state rewards and ι\iota the transition rewards. With d=1d=1, this is the same as the undiscounted C<=k. For MDPs, the value is minimised or maximised over strategies, as for other reward properties.

Multi-objective properties

For MDPs, PRISM supports multi-objective properties. Consider a property that uses the P operator. For example:

P<0.01 [ F "error" ]

This states that, for all strategies (or policies) of the MDP, the probability of reaching an "error" state is less than 0.01.

Multi-objective queries differ in two important ways. Firstly, (by default) they ask about the existence of a strategy. Secondly they refer to multiple properties of a strategy. For example:

multi(P<0.01 [ F "error1" ], P<0.02 [ F "error2" ])

means: "does there exist a strategy of the MDP under which the probability of reaching an "error1" state is less than 0.01 and the probability of reaching an "error2" state is less than 0.02?"

To use the terminology from [FKP12], the above is an "achievability" query (i.e., is this combination of objectives achievable by some strategy?). PRISM also supports two other kinds of multi-objective query: "numerical" and "Pareto" queries.

A "numerical" query looks like:

multi(Pmin=? [ F "error1" ], P<0.02 [ F "error2" ])

meaning "what is the minimum possible probability of reaching "error1", over all strategies of the MDP for which the probability of reaching "error2" is less than 0.02?".

A "Pareto" query leaves both of the objectives unbounded, e.g.:

multi(Pmin=? [ F "error1" ], Pmin=? [ F "error2" ])

This asks PRISM to compute (approximately), the Pareto curve for this pair of objectives. Intuitively, this is the set of pairs of probabilities (of reaching "error1"/"error2") such that reducing one probability any more would necessitate an increase in the other probability.

Types of objectives

For simplicity, the examples above all refer to the probability of reaching classes of states in the model. Other types of property (objective) are also possible.

Firstly, we can extend the examples above by referring to the probability of any LTL property. For example:

multi(Pmax=? [ G "good1" ], P>=0.9 [ G F "good2" ])

"What is the maximum probability of staying forever in "good1" states, such that the probability of visiting "good2" states infinitely often remains at least 0.9?".

We can also use more than 2 objectives, e.g.:

multi(Pmax=? [ G "good1" ], P>=0.9 [ G F "good2" ], P>=0.95 [ G F "good3" ])

"What is the maximum probability of staying forever in "good1" states, such that the probability of visiting "good2" states infinitely often remains at least 0.9 and the probability of visiting "good3" states infinitely often remains at least 0.95?".

Multi-objective queries can also refer to the expected total cumulative value of a reward structure. We write such properties in the form:

multi(R{"time"}min=?[ C ], R{"energy"}<=1.45 [ C ])

"What is the minimum expected cumulative value of reward structure "time", such that the expected cumulative value of reward structure "energy" is below 1.45?"

Note that this C reward operator differs from the F "target" operator, usually used for standard (single-objective) MDP model checking. Whereas the F "target" operator refers to the expected reward accumulated until a "target" state is reached, the C operator refers to the expected total reward.

A few important notes regarding rewards:

  • Only transition rewards are supported; state rewards are not.
  • Certain assumptions are made regarding the finiteness of rewards; see p.7 of [FKP12] for details.

Finally, time-bounded variants of both probabilistic reachability and expected cumulative rewards objectives can be used. Here is an example that uses the latter:

multi(R{"power"}min=? [ C<=k ], R{"queue"}<=r [ C<=k ])

Solution methods

PRISM can perform multi-objective model checking using two distinct solution methods, which are described in [FKN+11] and [FKP12]. The former is based on the use of linear programming; the latter reduces multi-objective model checking to a sweep over a series of simpler problems, each solved using value iteration (or the Gauss-Seidel variant of value iteration). The default is "Value iteration". You can change this in the GUI using the option "MDP multi-objective solution methods", or using the command-line switches -lp, -valiter, -gs.

There are some restrictions

  • Multi-objective queries are implemented in the sparse engine only. If the hybrid engine is selected, PRISM switches to the sparse engine automatically; the MTBDD and explicit engines are not supported.
  • Linear programming does not support time-bounded objectives or Pareto queries; use value iteration for these.
  • Values are only computed from a single initial state.
  • Fairness and interval iteration are not supported.

Non-probabilistic properties

PRISM also supports model checking of the non-probabilistic temporal logics CTL (computation tree logic) and LTL (linear temporal logic). Properties in these logics use the A (for all) and E (there exists) operators, instead of the probabilistic P operator used in many other properties supported by PRISM. They can be checked on any model type, including non-probabilistic models such as labelled transition systems (LTSs).

Properties take the form:

A [ pathprop ]
E [ pathprop ]

which are true in a state s of a model if "path property pathprop is satisfied by all paths from state s" and "path property pathprop is satisfied by some path from state s", respectively. The syntax for LTL formulas is the same as that allowed within the P operator.

Example properties include:

// There exists a path that reaches a state satisfying "goal"
E [ F "goal" ];

// Variable x is always at most 10 along all paths of the model
A [ G x<=10 ];

// There exists a path along which label "ready" eventually becomes true
// and label "launch" is true immediately afterwards
E [ F "ready" & (X "launch") ];

// Along all paths, either x=1 or x=2 is true infinitely often
A [ (G F x=1) | (G F x=2) ];

Counterexamples and witnesses

If you check a CTL property of the form A [ G "inv" ] and it is false, PRISM will generate a counterexample in the form of a path that reaches a state where "inv" is not true. This is displayed either in the simulator (from the GUI) or at the command-line. Similarly, if you check E [ F "goal" ] and the result is true, a witness (a path reaching a "goal" state) will be generated.

Filters

A property in the PRISM property language is evaluated with respect to a particular state of a model, and can yield a value of various types (Boolean, numerical, etc.), depending on the type of property. When performing model checking, PRISM often computes the value of a property for all states of the model, but typically just reports the result as a single value. Usually, this is the value for the (single) initial state of the model. For example, this:

P=? [ F "error" ]

will report the probability, from the initial state of the model, of reaching an "error" state. This:

P>0.5 [ F "error" ]

will return true if and only if the probability, from the initial state, is greater than 0.5.

For models with multiple initial states, we need to adapt these definitions slightly. In this case, the two properties above will yield, respectively:

  • the range of values (over all initial states) of the probability of reaching "error"
  • true if and only if the probability is greater than 0.5 from all initial states.

Using filters, you can ask PRISM to obtain different results. This is done using filter properties, which have the form:

filter(op, prop, states)

where op is the filter operator (see below), prop is any PRISM property and states is a Boolean-valued expression identifying a set of states over which to apply the filter.

In fact, the states argument is optional; if omitted, the filter is applied over all states. So, the following properties are equivalent:

filter(op, prop)
filter(op, prop, true)

Here's a simple example of a filter:

filter(max, P=? [ F "error" ], x=0)

This gives the maximum value, starting from any state satisfying x=0, of the probability of reaching an "error" state.

Here's another simple example, which checks whether, starting from any reachable state, we eventually reach a "done" state with probability 1.

filter(forall, P>=1 [ F "done" ])

We could modify this property slightly to instead check whether, from any state that satisfies the label "ready", we eventually reach a "done" state with probability 1. This could be done with either of the following two equivalent properties:

filter(forall, "ready" => P>=1 [ F "done" ])
filter(forall, P>=1 [ F "done" ], "ready")

Filter operators

Most filters of the form filter(op, prop, states) apply some operator op to the values of property prop for all the states satisfying states, resulting in a single value. The full list of filter operators op in this category is:

  • min: the minimum value of prop over states satisfying states
  • max: the maximum value of prop over states satisfying states
  • count: counts the number of states satisfying states for which prop is true
  • sum (or +): sums the value of prop for states satisfying states
  • avg: the average value of prop over states satisfying states
  • first: the value of prop for the first (lowest-indexed) state satisfying states
  • range: the range (interval) of values of prop over states satisfying states
  • forall (or &): returns true if prop is true for all states satisfying states
  • exists (or |): returns true if prop is true for some states satisfying states
  • state: returns the value for the single state satisfying states (if there is more than one, this is an error)

There are also a few filters that, rather than returning a single value, return different values for each state, like a normal PRISM property:

  • argmin: returns true for the states satisfying states that yield the minimum value of prop
  • argmax: returns true for the states satisfying states that yield the maximum value of prop
  • print: does not change the result of prop but prints the (non-zero) values to the log
  • printall: like print, but displays all values, even for states where the value is zero

Examples

Here are some further illustrative examples of properties that use filters.

Filters provide a quick way to print the results of a model checking query for several states. In most cases, for example, a P=? query just returns the probability from the initial state. To see the probability for all states satisfying x>2, use:

filter(print, P=? [ ... ], x>2)

Values are printed in the log (i.e. to the "Log" tab in the GUI or to the terminal from the command-line). For small models, you could omit the final states argument (x>2 here) and view the probabilities from all states. You can also use PRISM's verbose mode to view values for all states, but filters provide an easier and more flexible solution. print filters do not actually alter the result returned so, in the example above, PRISM will still return the probability for the initial state, in addition to printing other probabilities in the log.

You can also use print filters to display lists of states. For example, this property:

filter(print, filter(argmax, P=? [ F "error" ]))

prints the states which have the highest probability of reaching an error state. However, you should exercise caution when using argmax (or argmin) on properties such as P=? [ ... ] (or S=? [ ... ] or R=? [ ... ]), whose results are only approximate due to the nature of the methods used to compute them (or because of round-off errors.)

Another common use of filters is to display the value for a particular state of the model (rather than the initial state, which is used by default). To achieve this, use e.g.:

filter(state, P=? [ F "error" ], x=2&y=3)

where x=2&y=3 is assumed to specify one particular state. A state filter will produce an error if the filter expression is not satisfied by exactly one state of the model.

Filters can also be built up into more complex expressions. For example, the following two properties are equivalent:

filter(avg, P=? [ F "error" ], "init")
filter(sum, P=? [ F "error" ], "init") / filter(count, "init")

The range filter, unlike most PRISM expressions which are of type Boolean, integer or double, actually returns an interval: a pair of integers or doubles. For example:

filter(range, P=? [ F count=10 ], count=0)

gives the range of all possible values for the probability of reaching a state satisfying count=10, from all states satisfying count=0. This kind of value also results from numerical properties on models with multiple initial states (see above).

Default filters

Finally, for completeness, we show what the default filters are in PRISM, i.e. how the way that PRISM returns values from properties by default could have been achieved equivalently using filters.

Queries of the form:

P>0.5 [ F "error" ]

are the same as:

filter(forall, P>0.5 [ F "error" ], "init")

and queries of the form:

P=? [ F "error" ]

are the same as either:

filter(state, P=? [ F "error" ], "init")
filter(range, P=? [ F "error" ], "init")

for the cases where the model has a single initial state or multiple initial states, respectively.

Extended model types

Most of this manual describes PRISM's core model types: discrete-time Markov chains (DTMCs), continuous-time Markov chains (CTMCs) and Markov decision processes (MDPs). This section covers features of the PRISM modelling language that allow it to specify a wider range of model types, including non-probabilistic ones. Each page describes how such models are written in the PRISM language, which properties can be checked for them, and how they are analysed, including any restrictions.

Contents

  • Real-time models: using real-valued clocks to represent time, notably probabilistic timed automata (PTAs)
  • Partially observable models: where strategies only see observations of the state, notably partially observable Markov decision processes (POMDPs)
  • Uncertain models: where transition probabilities are not fully known, such as interval discrete-time Markov chains (IDTMCs) and interval Markov decision processes (IMDPs)
  • Non-probabilistic models: models with no probabilities, notably labelled transition systems (LTSs)

Real-time models

PRISM supports real-time models, in particular, probabilistic timed automata (PTAs), which extend MDPs with the ability to model real-time behaviour. This is done in the style of timed automata [AD94], by adding clocks, real-valued variables modelling the elapse of time.

The state of a PTA is made up of its clocks, plus other variables. The non-clock part of the state is often called the location of the PTA. The values of the clock variables are assumed to increase at the same rate, as time elapses. But the model can also include clock resets, which reset a clock's value to a (non-negative integer) value, usually 0, at certain points.

Transitions of the model between its locations can be made dependent on the values of the clocks: clock invariants dictate the range of values within which clocks must stay for each location before moving to another location; clock guards can be used to restrict transitions to when clocks have certain values.

For background material on PTAs, see for example [NPS13]. You can also find several example PTA models included in the PRISM distribution. Look in the prism-examples/ptas directory.

Modelling

Here is a simple example of a PTA, modelled in PRISM. It represents a system that attempts to send a message, which happens at a time instant in the range [1,2] and succeeds with probability 0.9. In the case of failure, it then repeatedly retries to send the message, waiting for a delay in the range [2,3] each time.

// A simple PTA model with a single clock x

pta

module M

    s : [0..2] init 0; // 0=send, 1=success, 2=retry
    x : clock;

    invariant
        (s=0 => x<=2) &
        (s=2 => x<=3)
    endinvariant

    [send] s=0 & x>=1 -> 0.9:(s'=1)&(x'=0) + 0.1:(s'=2)&(x'=0);
    [retry] s=2 & x>=2 -> 0.95:(s'=1) + 0.05:(s'=2)&(x'=0);

endmodule
Download: retry.prism

The model type is indicated as pta at the top of the file (in fact PRISM will also detect an MDP model with clock variables and treat it as a PTA).

Clocks use the variable type clock, and are declared in the same way as other variables. This example uses a single clock variable x. Other variables can be declared in the usual way and make up the rest of the state of the model (its location). In the example above, we use just a single integer variable s with range [0..2].

Clock guards are embedded within the usual guarded command notation (see, for example, the inclusion of x>=1 in the guard for the send-labelled command). Clock resets are included with the variable updates of commands (see, for example, the instances of (x'=0) in the example).

Additionally, an invariant construct in each module, placed after its variable declarations, specifies clock invariants as an expression over clocks and other variables. The format used in the example (a conjunction of implications) is a convenient way to specify a separate clock invariant for each PTA location. In the example, the clock x must satisfy x<=2 or x<=3 when local variable s is 0 or 2, respectively. If s is 1, there is no restriction (since the invariant is effectively true in this case).

The resulting PTA is shown below, where states (locations) are identified by the value of s.

PTA with three locations. Location 0 (invariant x≤2) has a send action, enabled when x≥1, that goes to location 1 (labelled true) with probability 0.9 or location 2 (invariant x≤3) with probability 0.1, resetting x to 0 in both cases. From location 2, a retry action enabled when x≥2 goes to location 1 with probability 0.95, or stays in location 2 with probability 0.05 and resets x to 0.

Rewards: PTA models can include reward structures in the same way as MDPs. However, the reward structures for PTAs are restricted to only include state and transition rewards that do not depend on clock variables. Formally, the class of PTAs with this kind of reward structure is sometimes called linearly priced PTAs (see e.g. [KNPS06]).

Restrictions: Expressions in PTA models that include reference to clocks, whether in guards or invariants, must satisfy certain conditions to facilitate model checking. In particular, references to clocks must appear as conjunctions of simple clock constraints, i.e., conjunctions of expressions of the form x~c or x~y where x and y are clocks, c is an integer-valued expression and ~ is one of <, <=, >=, > or =. Clock resets must set a clock to a non-negative integer value that is constant, such as (x'=0) or (x'=K) for an integer constant K: it cannot depend on the values of other variables or clocks.

PRISM makes several assumptions about PTAs, regardless of the engine used.

  • Firstly, PTAs should not exhibit timelocks, i.e., the possibility of reaching a state where no transitions are possible and time cannot elapse beyond a certain point (due to invariant conditions). PRISM checks for timelocks and reports an error if one is found.

  • Secondly, PTAs should be well-formed and non-zeno (see e.g. [KNSW07] for details). PRISM does not check automatically that these assumptions are satisfied.

There are also some further restrictions, which depend on the engine used: see below.

Properties

The classes of property that can be checked for real-time models are more restricted than for the other kinds of models that PRISM supports. This is because the model checking procedures are quite different for this type of model. The situation also depends on which of the engines is being used.

Broadly speaking, PRISM allows single (non-nested) instances of unbounded or time-bounded probabilistic reachability properties and reachability reward properties, i.e., queries of the form:

Pmin=? [ F target ]
Pmax=? [ F target ]
Pmin=? [ F<=T target ]
Pmax=? [ F<=T target ]
Rmin=? [ F target ]
Rmax=? [ F target ]

where target is a Boolean-valued expression that does not include references to any clock variables and T is an integer-valued expression. In some cases (see below), PRISM also allows until (U) properties.

Solution methods

PRISM has three distinct engines that can be used for analysing PTAs.

  • The stochastic games engine uses abstraction-refinement techniques based on stochastic two-player games [KNP09c].

  • The digital clocks engine performs a discretisation, in the form of a language-level model translation, that reduces the problem to one of model checking over a finite-state MDP [KNPS06]. If you want to see the MDP PRISM model that was generated, add the switch -exportdigital digital.prism when model checking a property to export the model file to digital.prism.

  • The backwards reachability engine is a zone-based method based on a backwards traversal of the state space and solution of the resulting finite-state MDP [KNSW07].

The default engine for PTAs is "stochastic games". The engine to be used can be specified using the "PTA model checking method" setting in the "PRISM" options panel in the GUI. From the command-line, switch -ptamethod <name> should be used where <name> is either games, digital or backwards.

Restrictions: The choice of engine affects the models that can be analysed, as well as the properties that can be checked.

For the stochastic games and backwards reachability engines:

  • The model must have a single initial state (i.e., the init...endinit construct is not permitted).
  • Only Pmin=? and Pmax=? queries are supported (not, e.g., P>=0.9); reward properties are not supported.
  • Filters and the "init" and "deadlock" labels cannot be used in properties.

Additionally, for the backwards reachability engine:

  • Only maximum probabilities are handled.

For the digital clocks engine:

  • Until (U) formulas are also allowed in the P operator, in addition to reachability (F) formulas.
  • Properties can refer to clock variables, so target is not restricted as above.
  • Arithmetic expressions in properties, such as 1 - Pmin=? [ F target ], are allowed.
  • Clock constraints in both models and properties cannot use strict comparison operators (e.g., x<=5 is allowed, but x<5 is not).
  • In both models and properties, diagonal clock constraints are not allowed, i.e., those containing references to two clocks, such as x<=y.

Partially observable models

PRISM supports analysis of partially observable probabilistic models, most notably partially observable Markov decision processes (POMDPs), but also partially observable probabilistic timed automata (POPTAs).

POMDPs are a variant of MDPs in which the strategy (or policy) that resolves nondeterministic choices in the model cannot see the precise state of the model, but instead just observations of it. A strategy can therefore only base its choices on the history of observations so far or, equivalently, on a belief: a probability distribution over the states that the model could be in.

For background material on POMDPs and POPTAs, see for example [NPZ17]. You can also find several example models included in the PRISM distribution. Look in the prism-examples/pomdps and prism-examples/poptas directories.

Modelling

Here is a simple example of a POMDP, modelled in PRISM. First, a hidden variable h is set randomly to 1, 2 or 3 (with probabilities 0.1, 0.3 and 0.6). Then, a single guess is made of its value.

// A simple POMDP: guess the value of a hidden variable

pomdp

observables s endobservables

module M

    s : [0..3]; // 0=start, 1=guessing, 2=correct, 3=wrong
    h : [0..3]; // hidden variable

    // Assign hidden variable randomly
    [toss] s=0 -> 0.1:(s'=1)&(h'=1) + 0.3:(s'=1)&(h'=2) + 0.6:(s'=1)&(h'=3);
    // Guess the value of the hidden variable
    [guess1] s=1 -> (s'=(h=1)?2:3);
    [guess2] s=1 -> (s'=(h=2)?2:3);
    [guess3] s=1 -> (s'=(h=3)?2:3);
    // Done
    [done] s>=2 -> true;

endmodule

label "correct" = s=2;
Download: guess.prism

The model type is indicated as pomdp at the top of the file (in fact PRISM will also detect an MDP model with observables and treat it as a POMDP).

PRISM supports state-based observations: this means that, upon entering a new POMDP state, the observation is determined by that state. In the same way that a model state comprises the values of one or more variables, an observation comprises one or more observables. In the example above, only the variable s is observable; the hidden variable h is not.

The resulting POMDP is shown below. The three states in which the guess is made all have the same observation (s=1), so a strategy cannot distinguish between them and must make the same guess in each one. For clarity, the final states are shown merged, since the value of h no longer matters there.

POMDP with initial state 0 (h=0), where a toss action goes to three states, all with s=1, where h is 1, 2 or 3, with probabilities 0.1, 0.3 and 0.6. These three states are grouped as a single observation (s=1). From each one, the guess action matching h (guess1, guess2 or guess3) goes to state 2 (correct) and the other guesses go to state 3 (wrong). States 2 and 3 have done self-loops.

There are several ways to define observables. The simplest, used above, is to specify a subset of the model's variables that are designated as being observable. The rest are unobservable. For example, in a POMDP with 3 variables, s, l and h, the following:

observables s, l endobservables

specifies that s and l are observable and h is not.

Alternatively, observables can be specified as arbitrary expressions over variables. For example, assuming the same variables s, l and h, this specification:

observable "s" = s;
observable "pos" = l>0;

defines 2 observables. The first is, as above, the variable s. The second, named "pos", determines if variable l is positive. Other than this, the values of l and h are unobservable.

The above two styles of definition can also be mixed to specify a combined set of observables.

POPTAs: Partially observable PTAs (POPTAs) combine the features of both PTAs and POMDPs. The model type is indicated as popta (PRISM will also detect a PTA model with observables and treat it as a POPTA). For a POPTA, all clock variables must be observable.

Properties

For partially observable models (POMDPs and POPTAs), PRISM uses the same property language as their fully observable equivalents (MDPs and PTAs). However, a more limited range of properties is available. For POMDPs, PRISM supports probabilistic reachability, probabilistic until, probabilistic invariance (G) or expected reachability rewards properties, i.e.:

Pmin=? [ F target ]
Pmax=? [ F target ]
Pmin=? [ remain U target ]
Pmax=? [ remain U target ]
Pmin=? [ G safe ]
Pmax=? [ G safe ]
Rmin=? [ F target ]
Rmax=? [ F target ]

or variants with a probability or reward bound (e.g., P>=0.5) instead of the min=? or max=?.

The expressions such as target, remain and safe above can, as usual, refer to labels (with some restrictions, see below) but also to additional named observables defined in the model (e.g., "pos" in the example above).

An example property for the guess.prism model above is:

// Maximum probability of guessing the value correctly
Pmax=? [ F "correct" ]
Download: guess.props

This yields a result of 0.6: the best strategy is always to guess the most likely value (3). In an MDP, where h would be visible, the probability would be 1.

Restrictions: There are some additional constraints on properties for partially observable models:

  • The target (and remain or safe) expression in the property must be observable. In other words, if any state of the POMDP satisfies the expression, then all other observationally equivalent states must also satisfy it. This is easily achieved by only using either observable variables or named observables in the expression, but that is not required.
  • Values are only computed from a single initial state.
  • Time-bounded properties (e.g., F<=k) and nested properties are not supported.

POPTAs are verified using the "digital clocks" approach to translate them into a POMDP, so the same restrictions apply, as well as those of the digital clocks engine (e.g., strict or diagonal clock comparisons are not allowed). However, for POPTAs, time-bounded probabilistic reachability is also supported.

Solution methods

POMDPs are analysed with the explicit engine, which PRISM switches to automatically. The method used is a fixed-resolution grid approximation of the (infinite) belief MDP [Lov91], as described in [NPZ17]. The resolution of the grid is set with the -gridresolution switch (default 10). Higher values give more accurate results, at the expense of time and memory.

Since the result is approximate, PRISM computes two bounds on the true value: an outer bound, from the grid approximation, and an inner bound, from the strategy that the approximation generates. Both are shown in the log, and the result is reported as the interval between them, e.g.:

prism guess.prism guess.props
 ...
 Outer bound: 0.6 (exact floating point)
 Inner bound: 0.6 (exact floating point)
 Result bounds: [0.6,0.6]

If the bounds are far apart, try increasing the grid resolution.

The generated strategy can be exported or viewed, as for MDPs (see Strategies). It maps beliefs (rather than states) to actions.

Uncertain models

PRISM has support for uncertain models, in which there is epistemic uncertainty regarding some quantitative aspects of the probabilistic models being verified. In particular, it supports interval MDPs (IMDPs) and interval DTMCs (IDTMCs), which are MDPs or DTMCs in which transition probabilities are specified as intervals, indicating that the exact probability is not precisely known. This can be useful, for example, when the transition probabilities have been estimated from data.

You can find some example models included in the PRISM distribution. Look in the prism-examples/imdps and prism-examples/idtmcs directories.

Modelling

Here is a simple example of an IMDP, modelled in PRISM. A robot can choose between two routes to a goal: a fast route, whose probability of success is only known to lie in the range [0.7,0.9], and a slower route, whose probability of success is known to be 0.8.

// A simple IMDP: a robot chooses between a fast route with
// an uncertain chance of success and a slower but reliable one

mdp

module M

    s : [0..3]; // 0=start, 1=slow route, 2=goal, 3=crash

    [fast] s=0 -> [0.7,0.9]:(s'=2) + [0.1,0.3]:(s'=3);
    [slow] s=0 -> (s'=1);
    [slow] s=1 -> 0.8:(s'=2) + 0.2:(s'=3);
    [done] s>=2 -> true;

endmodule

label "goal" = s=2;
Download: routes.prism

Intervals are used by simply replacing the probabilities attached to updates in commands with intervals, such as [0.7,0.9] above. Single values (e.g., 0.8 in the example) are treated as single-point intervals ([0.8,0.8]). There is no separate model type keyword for interval models: a dtmc or mdp model containing intervals is treated as an IDTMC or IMDP, respectively. Intervals can also be used in POMDPs, giving interval POMDPs (IPOMDPs), but these can only be built, not model checked.

The resulting IMDP is shown below.

IMDP with four states. From state 0 (start), action fast goes to state 2 (goal) with probability in the interval [0.7,0.9] or to state 3 (crash) with probability in [0.1,0.3]; action slow goes to state 1. From state 1, action slow goes to state 2 (goal) with probability 0.8 or state 3 (crash) with probability 0.2. States 2 and 3 have done self-loops.

As usual, the interval bounds can be expressions involving constants or state variables, for example:

[] x=0 -> [p,p+0.1]:(x'=0) + [0.9-p,1-p]:(x'=1);

The intervals in each command must allow at least one probability distribution, i.e., the lower bounds must sum to at most 1 and the upper bounds to at least 1. PRISM checks this when the model is built and reports an error otherwise.

When two commands in different modules synchronise and specify the probabilities for updates to variables as intervals, these are considered to be independent, i.e., the probability of each combined transition is taken to be the product of the two component intervals.

Properties

For uncertain models, PRISM performs robust verification, which considers the best- or worst-case behaviour that can arise depending on the way that probabilities are selected from intervals.

For example, instead of a property for a DTMC such as

P=? [ F "goal" ]

which asks for the probability to reach a state satisfying "goal", IDTMCs use MDP-style queries:

Pmin=? [ F "goal" ]
Pmax=? [ F "goal" ]

which compute the minimum or maximum possible probability that can arise.

For an IMDP, there are two separate quantifications, firstly over strategies (policies) and secondly over the distinct ways that transition probabilities can be selected from intervals. For these, min or max appear in that order in the query. For example, for the IMDP above:

// Maximum probability of reaching the goal (worst case)
Pmaxmin=? [ F "goal" ];

// Maximum probability of reaching the goal (best case)
Pmaxmax=? [ F "goal" ];
Download: routes.props

The first property asks for the maximum probability of reaching the goal, assuming the worst case for the uncertain probabilities; the result is 0.8, achieved by taking the slow route. The second assumes the best case instead; the result is 0.9, achieved by taking the fast route. Similarly, minmin and minmax are used for the minimum probability of reaching "goal". If only one of min or max is given (e.g., Pmax=?), it is used for both.

Model checking is supported for:

  • the P operator, including single temporal operators and LTL formulae
  • the R operator, for the expected reward to reach a target or satisfy a co-safe LTL formula, or total (possibly discounted) reward

Solution methods

Uncertain models are analysed with the explicit engine, which PRISM switches to automatically. The method used is robust value iteration, which is like the value iteration used for MDPs, except that each iteration also finds the best or worst probabilities within the intervals. By default, the Gauss-Seidel variant is used; standard value iteration can be selected with the -valiter switch (or the "IMDP/DTMC solution method" setting in the GUI).

Strategies can be generated and exported for IMDPs as for MDPs. For the example above, the strategy chooses slow in state 0 for Pmaxmin=? and fast for Pmaxmax=?.

Non-probabilistic models

As well as probabilistic models, PRISM supports non-probabilistic models, in particular labelled transition systems (LTSs). An LTS is like an MDP but without probabilities: in each state, there is a nondeterministic choice between one or more transitions, each of which leads to a single successor state.

LTSs can be used to check functional (rather than quantitative) correctness of a system, using the temporal logics CTL and LTL, for example as a first step before adding probabilities to a model.

Modelling

LTSs are modelled using the usual PRISM language features (modules, variables, commands, synchronisation, formulas, labels, etc.), but with no probabilities attached to the updates of commands. Here is a simple example: two processes, each of which can be idle, trying or in a critical section, which use a lock to ensure mutual exclusion.

// Two processes sharing a lock (no probabilities)

module P1

    x : [0..2]; // 0=idle, 1=trying, 2=critical

    [try1] x=0 -> (x'=1);
    [enter1] x=1 -> (x'=2);
    [exit1] x=2 -> (x'=0);

endmodule

module P2 = P1 [ x=y, try1=try2, enter1=enter2, exit1=exit2 ] endmodule

module Lock

    l : bool; // locked?

    [enter1] !l -> (l'=true);
    [enter2] !l -> (l'=true);
    [exit1] l -> (l'=false);
    [exit2] l -> (l'=false);

endmodule

label "both" = x=2 & y=2;
Download: lock.prism

The two processes do not synchronise with each other, but each one synchronises with the Lock module when it enters or leaves its critical section: for example, the action enter1 can only occur when the lock is free (!l), and it then sets the lock.

There is no model type keyword for LTSs. If a model has no keyword (which would usually result in the default model of an MDP) and does not use any probabilities, it is treated as an LTS. If instead it starts with the mdp keyword, it is treated as an MDP (in which each choice has a single transition with probability 1).

The resulting LTS is shown below, where each state shows the values of x, y and l, and transitions are labelled with their actions. Note that the lock is set exactly when one process is in its critical section, and that there is no state with x=2 and y=2, where both processes are in the critical section.

LTS with 8 states, arranged in a 3x3 grid by the values of x (columns) and y (rows), from 0,0,false (initial) to 1,2,true, with no state where x and y are both 2. The lock l is true in the states where x or y is 2. Process 1 moves right, with action try1 from x=0 to x=1, enter1 from x=1 to x=2 (only if y is not 2) and exit1 from x=2 back to x=0. Process 2 moves down in the same way with actions try2, enter2 and exit2.

Properties

LTSs can be analysed with non-probabilistic properties, i.e., CTL and LTL formulas using the A (for all paths) and E (there exists a path) operators. For example, for the model above:

// The two processes are never both in the critical section
A [ G !"both" ];

// It is possible for process 1 to reach the critical section
E [ F x=2 ];

// Whenever process 1 is trying, it eventually reaches the critical section
A [ G ((x=1) => (F x=2)) ];
Download: lock.props

The first two properties are true: the protocol ensures mutual exclusion, and process 1 can reach its critical section. The third is false, since process 2 can repeatedly enter its critical section while process 1 waits forever. PRISM does not make any fairness assumptions about the choices in the model.

For some properties, PRISM also generates a counterexample or witness, e.g., a path along which process 1 reaches its critical section for the second property above.

Solution methods

LTSs are analysed with the explicit engine, which PRISM switches to automatically. CTL properties are checked with standard graph-based algorithms and LTL properties by building the product of the LTS with a Büchi automaton.

Running PRISM

There are two versions of PRISM, one based on a graphical user interface (GUI), the other based on a command line interface (CLI). Both use the same underlying model checker. The latter is useful for running large batches of jobs, leaving long-running model checking tasks in the background, or simply for running the tool quickly and easily once you are familiar with its operation.

Details of how to run PRISM can be found in the installation instructions.

In short, to run the PRISM GUI:

  • (on Windows) click the short-cut (to xprism.bat) installed on the Desktop/Start Menu
  • (on other OSs) run the xprism script in the bin directory

and for the command-line:

  • run the prism script in the bin directory

This section describes the main functionality offered by PRISM, from both the GUI and command line.

Contents

Loading and building a model

Typically, when using PRISM, the first step is to load a model that has been specified in the PRISM modelling language. If using the GUI, select menu option "Model | Open Model" and choose a file. There is a selection of sample PRISM model files in the prism-examples directory of the distribution. A few very small models are contained in the subdirectory simple; the rest are in subdirectories grouped by model type.

The model will then be displayed in the editor in the "Model" tab of the GUI window. The file is parsed upon loading. If there are no errors, a green tick will be visible. If there are errors in the file, a red cross will appear instead and the errors will be highlighted in the model editor. To view details of the error, position the mouse pointer over the source of the error (or over the red cross). Alternatively, select menu option "Model | Parse Model" and the error message will be displayed in a message box. Models can be edited or written from scratch in the GUI's editor.

Screenshot of the Model tab in the PRISM GUI

Building the model

In order to perform model checking, PRISM will (in most cases) need to construct the corresponding probabilistic model, i.e., convert the PRISM model description to an MDP, DTMC, etc. During this process, PRISM computes the set of states in the model which are reachable from the initial states and the transition matrix which represents the model.

Model construction is done automatically when you perform model checking. However, you may also want to explicitly ask PRISM to build the model in order to test for errors or to see how large the model is. From the GUI, you can do this by selecting "Model | Build Model". If there are no errors during model construction, the number of states and transitions in the model will be displayed in the bottom left corner of the window.

From the command-line, simply type:

prism model.prism

where model.prism is the name of the file containing the model description.

For some types of models, notably PTAs, models are not constructed in this way (because the models are infinite-state). In these cases, analysis of the model is not performed until model checking is performed.

Deadlocks

You should be aware of the possibility of deadlock states in the model, i.e., states which are reachable but from which there are no outgoing transitions. PRISM will automatically search your model for deadlocks and, by default, "fix" them by adding self-loops in these states. Since deadlocks are sometimes caused by modelling errors, PRISM will display a warning message in the log when deadlocks are fixed in this way.

You can control whether deadlocks are automatically fixed in this way using the "Automatically fix deadlocks" option (or with command-line switches -nofixdl and -fixdl). When fixing is disabled, PRISM will report an error when the model contains deadlocks.

If you have unwanted or unexpected deadlocks in your model, there are several ways you can detect them. Firstly, by disabling deadlock fixing (as described above), PRISM will display a list of deadlock states in the log. Alternatively, you can model check the filter property filter(print, "deadlock"), which has the same effect.

To find out how deadlocks occur, i.e., which paths through the model lead to a deadlock state, there are several possibilities. Firstly, you can model check the CTL property E[F "deadlock"]. When checked from the GUI, this will provide you with the option of displaying a path to a deadlock in the simulator. From the command-line, a path to a deadlock will be displayed in the log, for example with:

prism model.prism -pf 'E[F "deadlock"]'

Finally, in the eventuality that the model is too large to be model checked, you can still use the simulator to search for deadlocks. This can be done either by manually generating random paths using the simulator in the GUI or, from the command-line, e.g. by running:

prism dice.prism -simpath deadlock stdout

Model checking

Properties to be checked on a model are specified as described in the "Property specification" section, and are usually kept in properties files with extension .props. There are properties files accompanying most of the sample PRISM models in the prism-examples directory.

GUI

A properties file can be loaded into the GUI along with a model when starting it, e.g.:

xprism example.prism example.props

Otherwise, after first loading a model, select menu option "Properties | Open properties list". The file can only be loaded if there are no errors, otherwise an error is displayed. Note that it may be necessary to have loaded the corresponding model first, since the properties will probably make reference to labels, variables or constants declared in the model file. Once loaded, the properties contained in the file are displayed in a list in the "Properties" tab of the GUI. Additional constants and labels defined in the properties file are displayed in separate lists below. You can modify or create new properties, constants and labels from the GUI, by right-clicking on the appropriate list and selecting from the pop-up menu which appears. Properties with errors are shaded red and marked with a warning sign. Positioning the mouse pointer over the property displays the corresponding error message.

The pop-up menu for the properties list also contains a "Verify" option, which allows you to instruct PRISM to model check the currently selected properties (hold down Ctrl/Cmd to select more than one property simultaneously). All properties can be model checked at once by selecting "Verify all". PRISM verifies each property individually. Upon completion, the icon next to the property changes according to the result of model checking. For Boolean-valued properties, a result of true or false is indicated by a green tick or red cross, respectively. For properties which have a numerical result (e.g. P=? [ ...]), position the mouse pointer over the property to view the result. In addition, this and further information about model checking is displayed in the log in the "Log" tab.

Command-line

From the command-line, model checking is achieved by passing both a model file and a properties file as arguments, e.g.:

prism poll2.prism poll.props -const T=10

Here, poll2.prism is a CTMC model of a simple polling system and the properties file poll.props has a constant T with no value, which is given here with the -const switch (see "Experiments"). The results of model checking are sent to the display and are as described above for the GUI version. By default, all properties in the file are checked. To model check only a single property, use the -prop switch. For example, to check only the fourth property in the file:

prism poll2.prism poll.props -prop 4

Properties can also be referred to by name. For example, if a properties file model.props contains a property named "safe", it can be checked on its own with:

prism model.prism model.props -prop safe

You can also provide a comma-separated list of multiple properties to check, using numerical indices, property names or a mix of the two:

prism model.prism model.props -prop 4,5,safe

Alternatively, the contents of a properties file can be specified directly from the command-line, using the -pf switch:

prism poll2.prism -pf 'P>=0.5 [ F<=5 (s=1 & a=0) ]'

The switches -pctl and -csl are aliases for -pf.

Note the use of single quotes ('...') to avoid characters such as ( and > being interpreted by the command-line shell. Single quotes may be preferable to double quotes since PRISM properties often include double quotes, e.g., for references to labels or properties.

Accuracy of results

The default methods used for model checking in most cases are iterative numerical methods implemented using floating point arithmetic. The accuracy of the resulting values is impacted by both the method chosen and parameters such as the threshold for termination; these are discussed more in the "Configuration and performance" section.

When PRISM prints the result of a (numerical) model checking query, it typically shows an indication of the accuracy too, for example:

prism model.prism model.props
 ...
 Result: 0.15625 (exact floating point)
 ...
 Result: 0.1666666865348816 (+/- 1.1920933218335556E-7; rel err 7.152559078349847E-7)
 ...
 Result: 0.16666650772094727 (+/- 1.1920928955078125E-6 estimated; rel err 7.1525641942636435E-6)

The first result is exact, up to the precision of floating point arithmetic., in this case because it was the result of a step-bounded (finite-horizon) query needing a fixed number of iterations to compute. The second was computed using interval iteration, which is an iterative method but that provides a guaranteed error bound on the result. The third was computed by value iteration, and its error bound is only an estimate, based on the check for convergence.

Here is an example of the output when using the exact engine, which uses arbitrary precision arithmetic to compute precise results:

prism model.prism model.props -ex
 ...
 Result: 1/6 (exact) (~0.16666666666666666)

An approximate decimal value is also shown, for convenience.

Experiments

PRISM supports experiments, which are a way of automating multiple instances of model checking. This is done by leaving one or more constants undefined, e.g.:

const int N;
const double T;

This can be done for constants in the model file, the properties file, or both. Before any verification can be performed, values must be provided for any such constants. In the GUI, a dialog appears in which the user is required to enter values. From the command line, the -const switch must be used, e.g.:

prism cluster.prism cluster.props -prop 4 -const N=4,T=85.9

Here, the model cluster.prism and properties cluster.props are a CTMC of a workstation cluster and some of its properties, and -prop 4 checks just the fourth property in the file.

Running experiments

To run an experiment, provide a range of values for one or more of the constants. Model checking will be performed for all combinations of the constant values provided. For example:

prism cluster.prism cluster.props -prop 4 -const N=4:6,T=60:10:100

where N=4:6 means that values of 4,5 and 6 are used for N, and T=60:10:100 means that values of 60, 70, 80, 90 and 100 (i.e., steps of 10) are used for T.

For convenience, constant specifications can be split across separate instances of the -const switch, if desired. You can also specify double-valued constants as fractions rather than decimals. For example:

prism cluster.prism cluster.props -prop 4 -const N=4 -const T=1/3

Experiments in the GUI

From the GUI, an experiment is created by selecting a single property, right clicking on it and selecting "New experiment" (or alternatively using the popup menu in the "Experiments" panel). Values or ranges for each undefined constant can then be supplied in the resulting dialog. If you wish, you can tick the "Use Simulation" box at this point to use statistical model checking for the experiment, rather than normal model checking.

Details of the new experiment and its progress are shown in the panel. To stop the experiment before it has completed, click the red "Stop" button and it will halt after finishing the current iteration of model checking. Once the experiment has finished, right clicking on the experiment produces a pop-up menu, from which you can view the results of the experiment or export them to a file.

Plotting graphs

For experiments based on properties which return numerical results, you can also use the GUI to plot graphs of the results. This can be done either before the experiment starts, by selecting the "Create graph" tick-box in the dialog used to create the experiment (in fact this box is ticked by default), or after the experiment's completion, by choosing "Plot results" from the pop-up menu on the experiment. A dialog appears, where you can choose which constant (if there are more than one) to use for the x-axis of the graph, and for which values of any other constants the results should be plotted.

The graph will appear in the panel below the list of experiments. Right clicking on a graph and selecting "Graph options" brings up a dialog from which many properties of the graph can be configured. From the pop-up menu of a graph, you can also choose to print the graph (to a printer or Postscript file) or export it in a variety of formats: as an image (PNG or JPEG), as an encapsulated Postscript file (EPS), in an XML-based format (for reloading back into PRISM), or as code which can be used to generate the graph in Matlab.

Screenshot of running an experiment in the Properties tab of the PRISM GUI

Exporting results

You can export all the results from an experiment to a file or to the screen. From the command-line, use the -exportresults switch, for example:

prism cluster.prism cluster.props -prop 4 -const N=4:5,T=0:10:20 -exportresults res.txt

to send to output file res.txt, or:

prism cluster.prism cluster.props -prop 4 -const N=4:5,T=0:10:20 -exportresults stdout

to send the results straight to the screen. From the GUI, right click on the experiment and select "Export results".

The default behaviour is to export a list of results in text form, using tabs to separate items. The above examples produce:

N	T	Result
4	0	0.0
4	10	4.707364688019771E-6
4	20	1.3126420636755292E-5
5	0	0.0
5	10	3.267731327728599E-6
5	20	8.343575060356386E-6

You can change the format in which the results are exported by appending one or more comma-separated options to the end of the -exportresults switch, for example to export in CSV (comma-separated values) format:

prism cluster.prism cluster.props -prop 4 -const N=4:5,T=0:10:20 -exportresults res.txt:csv
N, T, Result
4, 0, 0.0
4, 10, 4.707364688019771E-6
4, 20, 1.3126420636755292E-5
5, 0, 0.0
5, 10, 3.267731327728599E-6
5, 20, 8.343575060356386E-6

or in DataFrame format:

prism cluster.prism cluster.props -prop 4 -const N=4:5,T=0:10:20 -exportresults res.txt:dataframe
N,T,Result
4,0,0
4,10,4.70736468802e-06
4,20,1.31264206368e-05
5,0,0
5,10,3.26773132773e-06
5,20,8.34357506036e-06

You can also add the matrix option, to export the results as one or more 2D matrices, rather than a list. This is particularly useful if you want to create a surface plot from results that vary over two constants.

prism cluster.prism cluster.props -prop 4 -const N=4:5,T=0:10:20 -exportresults res.txt:csv,matrix
"N\T"
, 0.0, 10.0, 20.0
4, 0.0, 4.707364688019771E-6, 1.3126420636755292E-5
5, 0.0, 3.267731327728599E-6, 8.343575060356386E-6

The matrix option is also available in normal (non-CSV) mode.

You can also export results in the form of comments, used by PRISM's regression testing functionality:

prism cluster.prism cluster.props -prop 4 -const N=4:5,T=0:10:20 -exportresults res.txt:comment
// RESULT (N=4,T=0): 0.0
// RESULT (N=4,T=10): 4.707364688019771E-6
// RESULT (N=4,T=20): 1.3126420636755292E-5
// RESULT (N=5,T=0): 0.0
// RESULT (N=5,T=10): 3.267731327728599E-6
// RESULT (N=5,T=20): 8.343575060356386E-6

From the GUI, it is also possible to import previously exported results (in DataFrame format).

A related option is the -exportvector <file> switch, useful in general contexts, not for experiments. This exports the results for all states of the model (typically, the log just displays the result for the initial state, unless a filter has been used) to the file file.

Strategies

Properties to be model checked on MDPs (and their variants, such as POMDPs or IMDPs) usually quantify over strategies (or policies) of the model, i.e., over the different possible ways that nondeterminism can be resolved in the model. For example, this property:

Pmax=? [ F "goal" ]

determines the maximum probability, over all strategies, of reaching a state satisfying the label "goal". When checking such properties, you can also ask PRISM to generate a corresponding (optimal) strategy, which yields this maximum probability when followed. The strategy can then be viewed, exported or simulated.

Note: PRISM uses the term strategy for all model types (other common names are policy, scheduler and adversary). Strategy generation is implemented in the "explicit" model checking engine, which is used automatically if strategy generation is requested. The "sparse" engine has a more limited adversary generation feature (see below).

Generating strategies

Optimal strategies can be generated either from the command-line or the graphical user interface (GUI). For the former, use the -exportstrat switch. Simple examples are:

prism mdp.prism -pf 'Pmax=? [ F "goal" ]' -exportstrat stdout
prism mdp.prism -pf 'Pmax=? [ F "goal" ]' -exportstrat strat.pexp
prism mdp.prism -pf 'Pmax=? [ F "goal" ]' -exportstrat strat.umb
prism mdp.prism -pf 'Pmax=? [ F "goal" ]' -exportstrat strat.dot
prism mdp.prism -pf 'Pmax=? [ F "goal" ]' -exportstrat strat.tra

The first of these exports actions, the others export induced models (see below).

From the GUI, you can trigger strategy generation by ticking the "Generate strategy" box either on the popup menu that appears when you right-click a property, or from the "Strategies" menu at the top. As long as it is supported, a strategy will then be generated once "Verify" is clicked.

From the same menu(s), you can then

  • export the strategy to a file
  • view the strategy by printing it in the log
  • explore the strategy in the simulator

Export formats

Strategies can be viewed or exported in several different formats:

Action list

An action list gives the action taken in each state of the model, e.g.:

(0,0):east
(0,1):north
(0,2):north
(1,0):south
...

where states, by default, are shown as a tuple of variable values.

Induced model

An induced model is a representation of the model that is induced when the strategy is applied. There are two "modes" for this export. The first (and default) is reduce, which removes the nondeterminism resolved by the strategy (e.g., an MDP becomes a DTMC). This can be useful to re-import the model back into PRISM and analyse the induced model. The second is restrict, which shows the original model but with a restricted set of choices (e.g., an MDP with just one choice in each state).

In each case, the induced model can be exported in various formats, as for regular model export, including UMB or explicit format, the latter either a combined (.pexp) file or just the transitions (.tra).

Dot file

A Dot file is, like an induced model, a view of the model induced by the strategy, but in Dot format, which allows it to be visualised.

Configuring strategy export

As hinted in the command-line examples above, the -exportstrat switch uses the file extension to determine the preferred format: if the strategy is exported to a file with extension .umb/.pexp/.tra or .dot, then it uses an induced model or Dot file, respectively. Otherwise, the default is an action list. You can specify the desired format:

prism mdp.prism -pf 'Pmax=? [ F "goal" ]' -exportstrat file.txt:type=actions
prism mdp.prism -pf 'Pmax=? [ F "goal" ]' -exportstrat file.txt:type=induced
prism mdp.prism -pf 'Pmax=? [ F "goal" ]' -exportstrat file.txt:type=dot

Further options can be added, e.g., to specify whether an induced model is exported in "restrict" or "reduce" mode:

prism mdp.prism -pf 'Pmax=? [ F "goal" ]' -exportstrat file.txt:type=induced,mode=restrict

A list of available options is as follows:

  • type (actions, induced or dot): the type of strategy export to use (action list, induced model or Dot file)
  • mode (restrict or reduce): when exporting as an induced model or Dot file, whether to "restrict" or "reduce" the model (see above); the default is "reduce"
  • reach (true or false): whether to restrict the strategy to states that are reachable when it is applied to the model (this is only used for exporting induced models and Dot files, and the default value is true, except for exporting just transitions in .tra format)
  • states (true or false): whether to show states, rather than state indices, for actions lists or Dot files; this is true by default
  • mergeobs (true or false): for partially observable models, whether to merge observationally equivalent states; this is true by default (and was previously called obs).

Mirroring the -exportmodel switch (see here), several other options are available for induced model export:

  • format (explicit, dot or umb): the format to export in
  • states (true or false): whether to include states
  • rewards (true or false): whether to include rewards
  • labels (true or false): whether to include labels
  • actions (true or false): whether to include actions on choices/transitions
  • obs (true or false): whether to include observations
  • precision (<n>): use <n> significant figures for floating point values (in text)
  • zip (true, false, gzip or xz): whether to zip the output and in what format
  • headers (true or false): whether to include headers when exporting rewards
  • text (true or false): whether to use textual form for UMB

Strategy types

PRISM generates several types of strategies. The simplest are memoryless deterministic strategies, which pick a single action in each state, as in the examples above. For some query types (e.g., step-bounded properties, or LTL-based properties), finite-memory strategies are generated, where an additional memory value is used. For these, induced models or Dot files are most useful since they will also show how the memory values are updated as the strategy is executed. Note that, in these cases, the state indices of the strategy will correspond to the product model constructed during model checking, not the original model. The product model can be exported using the -exportprodtrans and -exportprodstates switches.

Adversary generation

The "sparse" engine still includes PRISM's older "adversary generation" functionality, which exports the induced model of an optimal strategy for MDPs, as a DTMC or an MDP (switches -exportadv and -exportadvmdp, or the "Adversary export" option in the GUI). This is superseded by -exportstrat, described above, whose reduce and restrict modes give the same two models.

Simulation

PRISM includes a simulator, a tool which can be used to generate sample paths (executions) through a PRISM model. From the GUI, the simulator allows you to explore a model by interactively generating such paths. This is particularly useful for debugging models during development and for running sanity checks on completed models. Paths can also be generated from the command-line using the -simpath switch.

GUI

Once you have loaded a model into the PRISM GUI (note that it is not necessary to build the model), select the "Simulator" tab at the bottom of the main window. You can now start a new path by double-clicking in the bottom half of the window (or right-clicking and selecting "New path"). If there are undefined constants in the model (or in any currently loaded properties files) you will be prompted to give values for these. You can also specify the state from which you wish to generate a path. By default, this is the initial state of the model.

The main portion of the user interface (the bottom part) displays a path through the currently loaded model. Initially, this will comprise just a single state. The table above shows the list of available transitions from this state. Double-click one of these to extend the path with this transition. The process can be repeated to extend the path in an interactive fashion. Clicking on any state in the current path shows the transition which was taken at this stage. Click on the final state in the path to continue extending the path. Alternatively, clicking the "Simulate" button will select a transition randomly (according to the probabilities/rates of the available transitions). By changing the number in the box below this button, you can easily generate random paths of a given length with a single click. There are also options (in the accompanying drop-down menu) to allow generation of paths up until a particular length or, for CTMCs, in terms of the time taken.

The figure shows the simulator in action.

Screenshot of the Simulator tab: controls for automatic and manual exploration, backtracking and strategies at the top, a list of state labels on the right, and below a table of the path so far, one row per step showing the action taken, the time and the value of each variable

It is also possible to:

  • backtrack to an earlier point in a path
  • remove all of the states before some point in a path
  • restart a path from its first state
  • export a path to a text file

Notice that the table containing the path displays not just the value of each variable in each state but also the time spent in that state and any rewards accumulated there. You can configure exactly which columns appear by right-clicking on the path and selecting "Configure view". For rewards (and for CTMC models, for the time-values), you can opt to display the reward/time for each individual state and/or the cumulative total up until each point in the path.

At the top-right of the interface, any labels contained in the currently loaded model/properties file are displayed, along with their value in the currently selected state of the path. In addition, the built-in labels "init" and "deadlock" are also included. Selecting a label from the list highlights all states in the current path which satisfy it.

The other tabs in this panel allow the value of path operators (taken from properties in the current file) to be viewed for the current path, as well as various other statistics.

Another very useful feature for some models is to use the "Plot new path" option from the simulator, which generates a plot of some/all of the variable/reward values for a particular randomly generated path through the model.

Command-line

It is also possible to generate random paths through a model using the command-line version of PRISM. This is achieved using the -simpath switch, which requires two arguments, the first describing the path to be generated and the second specifying the file to which the path should be output (as usual, specifying stdout sends output to the terminal). The following examples illustrate the various ways of generating paths in this way:

prism model.prism -simpath 10 path.txt
prism model.prism -simpath time=7.5 path.txt
prism model.prism -simpath deadlock path.txt

These generate a path of 10 steps, a path of at least 7.5 time units and a path ending in deadlock, respectively.

Here's an example of the output:

prism poll2.prism -simpath 10 stdout
...
action step time s a s1 s2
- 0 0.0 1 0 0 0
[loop1a] 1 0.007479539729154247 2 0 0 0
[loop2a] 2 0.00782819795294666 1 0 0 0
[loop1a] 3 0.01570585559933703 2 0 0 0
[loop2a] 4 0.017061111948220263 1 0 0 0
[loop1a] 5 0.026816317516034468 2 0 0 0
[loop2a] 6 0.039878416276337814 1 0 0 0
[loop1a] 7 0.04456566315999103 2 0 0 0
[loop2a] 8 0.047368359683643765 1 0 0 0
[loop1a] 9 0.04934857366557349 2 0 0 0
[loop2a] 10 0.055031679365844674 1 0 0 0

poll2.prism is a CTMC model of a simple polling system (also shown, with a diagram, in "Explicit model files").

This shows the sequence of states in the path, i.e., the values of the variables in each state. In the example above, there are 4 variables: s, a, s1 and s2. The first three columns show the type of transition taken to reach that state, its index within the path (starting from 0) and the time at which it was entered. The latter is only shown for continuous time models. The type of the transition is written as [act] if action label act was taken, and as module1 if the module named module1 takes an unlabelled transition.

Further options can also be appended to the first parameter. For example, option probs=true also displays the probability/rate associated with each transition. For example:

prism poll2.prism -simpath '5,probs=true' stdout
...
action probability step time s a s1 s2
- - 0 0.0 1 0 0 0
[loop1a] 200.0 1 0.0011880118081395378 2 0 0 0
[loop2a] 200.0 2 0.0037798355025401888 1 0 0 0
[loop1a] 200.0 3 0.01029212322894221 2 0 0 0
[loop2a] 200.0 4 0.023258883912578403 1 0 0 0
[loop1a] 200.0 5 0.027402404026254504 2 0 0 0

In this example, the rate is 200.0 for all transitions. To show the state/transition rewards for each step, use option rewards=true.

If you are only interested in values of certain variables of your model, use the vars=(...) option. For example:

prism poll2.prism -simpath '500,probs=true,vars=(a,s1,s2)' stdout
...
action probability step time a s1 s2
- - 0 0.0 0 0 0
station2 0.5 110 0.5025332771499665 0 0 1
[loop2b] 200.0 111 0.5109407735244359 1 0 1
[serve2] 1.0 112 0.9960642154887506 0 0 0
station1 0.5 130 1.0645858553472822 0 1 0
[loop1b] 200.0 132 1.0732572896618477 1 1 0
[serve1] 1.0 133 2.939742026148121 0 0 0
station2 0.5 225 3.4311507854807677 0 0 1
[loop2b] 200.0 227 3.434285492243098 1 0 1
[serve2] 1.0 228 3.553118276800078 0 0 0
station2 0.5 250 3.6354431222941406 0 0 1
[loop2b] 200.0 251 3.637552738997181 1 0 1
[serve2] 1.0 252 3.7343375346150576 0 0 0

Note the use of single quotes around the path description argument to prevent the shell from misinterpreting special characters such as "(".

Notice also that the above only displays states in which the values of some variable of interest changes. This is achieved with the option changes=true, which is automatically enabled when you use vars=(...). If you want to see all steps of the path, add the option changes=false.

An alternative way of viewing paths is to only display paths at certain fixed points in time. This is achieved with the snapshot=x option, where x is the time step. For example:

prism poll2.prism -simpath 'time=5.0,snapshot=0.5' stdout
...
step time s a s1 s2
0 0.0 1 0 0 0
94 0.5 1 0 0 0
198 1.0 1 0 0 0
314 1.5 1 0 0 0
375 2.0 1 1 1 1
376 2.5 2 0 0 1
376 3.0 2 0 0 1
378 3.5 1 0 0 0
378 4.0 1 0 0 0
478 4.5 1 0 0 0
511 5.0 2 0 0 0

You can also use the sep=... option to specify the column separator. Possible values are space (the default), tab and comma. For example:

prism poll2.prism -simpath '200,vars=(a,s1),sep=comma' stdout
...
action,step,time,a,s1
-,0,0.0,0,0
[loop2b],71,0.30227293267212296,1,0
station1,72,0.7818965999769389,1,1
[serve2],73,1.132620216421162,0,1
[loop1b],74,1.1350805223051847,1,1
[serve1],76,5.305834484838731,0,0
...

When generating paths to a deadlock state, an additional repeat=... option is available, which will construct multiple paths until a deadlock is found. For example:

prism model.prism -simpath 'deadlock,repeat=100' stdout

By default, the simulator detects deterministic loops in paths (e.g., if a path reaches a state from which there is just a single self-loop leaving that state) and stops generating the path any further. You can disable this behaviour with the loopcheck=false option. For example:

prism model.prism -simpath 10 stdout
...
Warning: Deterministic loop detected after 6 steps (use loopcheck=false option to extend path).
action step s d
- 0 0 0
die 1 1 0
die 2 4 0
die 3 7 3
die 4 7 3
prism dice.prism -simpath 10,loopcheck=false stdout
...
action step s d
- 0 0 0
die 1 1 0
die 2 4 0
die 3 7 2
die 4 7 2
die 5 7 2
die 6 7 2
die 7 7 2
die 8 7 2
die 9 7 2
die 10 7 2

One final note: the -simpath switch only generates paths up to the maximum path length setting of the simulator (the default is 10,000). If you want to generate longer paths, either change the default setting or override it temporarily from the command-line using the -simpathlen switch. You might also use the latter to decrease the setting, e.g., to look for a path leading to a deadlock state, but only within 100 steps:

prism model.prism -simpath deadlock stdout -simpathlen 100

Statistical model checking

The discrete-event simulator built into PRISM can also be used to generate approximate results for PRISM properties, a technique often called statistical model checking. Essentially, this is achieved by sampling: generating a large number of random paths through the model, evaluating the result of the given properties on each run, and using this information to generate an approximately correct result. This approach is particularly useful on very large models when normal model checking is infeasible. This is because discrete-event simulation is performed using the PRISM language model description, without explicitly constructing the corresponding probabilistic model.

Statistical model checking can be used from the GUI (by selecting "Simulate") and from the command-line (by using the -sim switch); more details are given below.

Methods and settings

You can select between four different methods for performing statistical model checking:

  • CI (Confidence Interval)
  • ACI (Asymptotic Confidence Interval)
  • APMC (Approximate Probabilistic Model Checking)
  • SPRT (Sequential Probability Ratio Test)

The first three of these are intended primarily for numerical properties (e.g., of the form P=?[...]), but can also be used for Boolean properties with a bound (e.g., of the form P<p[...]). The SPRT method is only applicable to Boolean properties.

Each method has several parameters that control its execution, i.e., the number of samples that are generated and the accuracy of the computed approximation. In most cases, these parameters are inter-related so one of them must be left unspecified and its value computed automatically based on the others. In some cases, this is done before simulation; in others, it must be done afterwards.

Below, we describe each method in more detail. For simplicity, we describe the case of checking a P operator. Details for the case of an R operator can be found in [Nim10].

CI (confidence interval) method

The CI method gives a confidence interval for the approximate value generated for a P=? property, based on a given confidence level and the number of samples generated. The parameters of the method are:

  • "Width" (ww)
  • "Confidence" (α\alpha)
  • "Number of samples" (NN)

Let XX denote the true result of the query P=?[...] and YY the approximation generated. The confidence interval is [Y−w,Y+w][Y-w, Y+w], i.e., ww gives the half-width of the interval. The confidence level, which is usually stated as a percentage, is 100(1−α)%100(1-\alpha)\%. This means that the actual value XX should fall into the confidence interval [Y−w,Y+w][Y-w, Y+w] 100(1−α)%100(1-\alpha)\% of the time.

To determine, for example, the width ww for given α\alpha and NN, we use

w=qv/Nw = q \sqrt{v / N}

where qq is a quantile, for probability 1−α/21-\alpha/2, from the Student's t-distribution with N−1N-1 degrees of freedom and vv is (an estimation of) the variance for XX. Similarly, we can determine the required number of samples, from ww and α\alpha, as

N=vq2w2N = \frac{v q^2}{w^2}

where qq and vv are as before.

For a bounded property P~p[...], the (Boolean) result is determined according to the generated approximation for the probability. This is not the case, however, if the threshold pp falls within the confidence interval [Y−w,Y+w][Y-w, Y+w], in which case no value is returned.

ACI (asymptotic confidence interval) method

The ACI method works in exactly the same fashion as the CI method, except that it uses the Normal distribution to approximate the Student's t-distribution when determining the confidence interval. This is appropriate when the number of samples is large (because we can get a reliable estimation of the variance from the samples) but may be less accurate for small numbers of samples.

APMC (approximate probabilistic model checking) method

The APMC method, based on [HLMP04], offers a probabilistic guarantee on the accuracy of the approximate value generated for a P=? property, based on the Chernoff-Hoeffding bound. The parameters of the method are:

  • "Approximation" (ε\varepsilon)
  • "Confidence" (δ\delta)
  • "Number of samples" (NN)

Letting XX denote the true result of the query P=?[...] and YY the approximation generated, we have:

Prob(∣Y−X∣>ε)<δ\mathrm{Prob}(|Y-X| > \varepsilon) < \delta

where the parameters are related as follows:

N=ln⁡(2/δ)2ε2N = \frac{\ln(2/\delta)}{2\varepsilon^2}

This imposes certain restrictions on the parameters, namely that Nε2≥ln⁡(2/δ)/2N \varepsilon^2 \ge \ln(2/\delta)/2.

In similar fashion to the CI/ACI methods, the APMC method can also be used for bounded properties such as P~p[...], as long as the threshold pp falls outside the interval [Y−ε,Y+ε][Y-\varepsilon, Y+\varepsilon].

SPRT (sequential probability ratio test) method

The SPRT method is specifically for bounded properties, such as P~p[...] and is based on acceptance sampling techniques [YS02]. It uses Wald's sequential probability ratio test (SPRT), which generates a succession of samples, deciding on-the-fly when an answer can be given with a sufficiently high confidence.

The parameters of the method are:

  • "Indifference" (δ\delta)
  • "Type I/II error" (α\alpha/β\beta)

Consider a property of the form P>=p[...]. The parameter δ\delta is used as the half-width of an indifference region [p−δ,p+δ][p-\delta, p+\delta]. PRISM will attempt to determine whether either the hypothesis P>=(p+delta)[...] or P<=(p-delta)[...] is true, based on which it will return either true or false, respectively. The parameters α\alpha and β\beta represent the probability of the occurrence of a type I error (wrongly accepting the first hypothesis) and a type II error (wrongly accepting the second hypothesis), respectively. For simplicity, PRISM assigns the same value to both α\alpha and β\beta.

Maximum path length

Another setting that can be configured is the maximum length of paths generated by PRISM during statistical model checking. In order to perform statistical model checking, the property being checked needs to be evaluated along every generated path. For example, when checking P=? [ F<=10 "end" ], PRISM must check whether F<=10 "end" is true for each path. On this example (assuming a discrete-time model), this can always be done within the first 10 steps. For a property such as P=? [ F "end" ], however, there may be paths along which no finite fragment can show F "end" to be true or false. So, PRISM imposes a maximum path length to avoid the need to generate excessively long (or infinite) paths. The default maximum length is 10,000 steps. If, for a given property, statistical model checking results in one or more paths on which the property cannot be evaluated, an error is reported.

GUI

To use statistical model checking from the GUI, load a model and some properties into PRISM, as described in "Model checking". To generate an approximate value for one or more properties, select them in the list, right-click and select "Simulate" (as opposed to "Verify"). As usual, it is first necessary to provide values for any undefined constants. Subsequently, a "Simulation Parameters" dialog appears. Here, the state from which approximate values are to be computed (i.e., from which the paths will be generated) can be selected. By default, this is the initial state of the model. The other settings in the dialog concern the methods used for simulation.

Command-line

Statistical model checking can also be enabled from the command-line version of PRISM, by using the -sim switch. The default methods used are CI (Confidence Interval) for numerical properties and SPRT (Sequential Probability Ratio Test) for Boolean properties. To select a particular method, use switch -simmethod <method> where <method> is one of ci, aci, apmc and sprt. For example:

prism model.prism model.props -prop 1 -sim -simmethod aci

PRISM has default values for the various simulation method parameters, but these can also be specified using the switches -simsamples, -simconf, -simwidth and -simapprox. The exact meaning of these switches for each simulation method is given in the table below.

Switch CI ACI APMC SPRT
-simsamples "Number of samples" "Number of samples" "Number of samples" n/a
-simconf "Confidence" "Confidence" "Confidence" "Type I/II error"
-simwidth "Width" "Width" n/a "Indifference"
-simapprox n/a n/a "Approximation" n/a

The maximum length of simulation paths is set with switch -simpathlen.

Restrictions

Statistical model checking can only be applied to P or R operators. It does not support nested properties, LTL formulas, filters, cumulative reward properties without a time bound, or discounted rewards for continuous-time models.

The simulator also does not support every part of the PRISM modelling language. For example, it does not handle models with multiple initial states or with system...endsystem definitions.

It is also worth pointing out that statistical model checking techniques are not well suited to models that exhibit nondeterminism, such as MDPs. This is because the techniques rely on generation of random paths, which are not well defined for an MDP. PRISM does allow statistical model checking to be performed on an MDP, but does so by simply resolving nondeterministic choices in a (uniformly) random fashion (and displaying a warning message). PTAs are not supported by the simulator.

Transient and steady-state probabilities

If the model is a CTMC or DTMC, it is possible to compute corresponding vectors of steady-state or transient probabilities directly (rather than indirectly by analysing a property which requires their computation). From the GUI, select an option from the "Model | Compute" menu. For transient probabilities, you will be asked to supply the time value for which you wish to compute probabilities. From the command-line, add the -steadystate (or -ss) switch for steady-state probabilities or the -transient (or -tr) switch for transient probabilities, again specifying a time value in the latter case:

prism poll2.prism -ss
prism poll2.prism -tr 2.0

Here, poll2.prism is a CTMC model of a simple polling system (also shown, with a diagram, in "Explicit model files"). The probabilities are computed for all states of the model and displayed, either on the screen (from the command-line) or in the log (from the GUI).

To instead export the vector of computed probabilities to a file, use the "Model | Compute/export" option from the GUI, or the -exportsteadystate and -exporttransient switches from the command-line:

prism poll2.prism -ss -exportsteadystate poll2-ss.txt
prism poll2.prism -tr 2.0 -exporttransient poll2-tr2.txt

From the command-line, you can request that the probability vectors exported are in Matlab format by adding the -exportmatlab switch.

Initial probability distributions

By default, for both steady-state and transient probability computation, PRISM assumes that the initial probability distribution of the model is an equiprobable choice over the set of initial states. You can override this and provide a specific initial distribution. This is done using the -importinitdist switch. The format for this imported distribution is identical to the ones exported by PRISM, i.e. simply a list of probabilities for all states separated by new lines. For example, this:

prism poll2.prism -tr 1.0 -exporttransient poll2-tr1.txt
prism poll2.prism -tr 1.0 -importinitdist poll2-tr1.txt -exporttransient poll2-tr2.txt

is (essentially) equivalent to this:

prism poll2.prism -tr 2.0 -exporttransient poll2-tr2.txt

Ranges of time values

Finally, you can compute transient probabilities for a range of time values, e.g.:

prism poll2.prism -tr 0.1:0.01:0.2

which computes transient probabilities for the time points 0.1, 0.11, 0.12, ..., 0.2. In this case, the computation is done incrementally, with probabilities for each time point being computed from the previous point for efficiency.

Parametric model checking

Often, PRISM models contain constants, representing parameters of the system being modelled, which define for example the transition probabilities in the model. In order to perform model checking, these constants have to be assigned concrete values. PRISM also allows experiments, where model checking is performed for a range of different values for the constants.

PRISM's parametric model checking [HHZ11b],[HHZ11] functionality, however, provides a more powerful method for analysing probabilistic models whose transition probabilities are specified as functions over a set of parameters. Depending on the property under consideration, the result is then given as either a rational function over the parameters or as a mapping from regions of these parameters to rational functions or truth values. This function (or functions) can then be used to, for example:

  • plot a graph showing how the parameter affects the result of the property; or
  • use optimisation methods to find parameter values that minimise or maximise the result.

PRISM's implementation of parametric model checking [CHH+13] re-implements the techniques previously included in the PARAM tool.

Parameters are specified as undefined constants in the model file, e.g.:

const double x;

These parameters can only be used to describe probabilities (or rates). For example:

[] s=0 -> x : (s'=1) + 1-x : (s'=2);

They may not be used in guards or updates. The parametric definitions of probabilities or rates (e.g. x and 1-x in the above) must be rational functions (fractions of polynomials). PRISM supports parametric versions of discrete-time Markov chains (DTMCs), continuous-time Markov chains (CTMCs) and Markov decision processes (MDPs). The classes of properties that can be checked on these models are as follows:

  • parametric DTMCs/CTMCs: unbounded until, steady-state probabilities, reachability reward and steady-state reward;
  • parametric MDPs: unbounded until and reachability rewards.

Parametric model checking can only be performed from the command-line. This is done by using the switch -param <vals>, where <vals> lists the undefined constants that should be treated as parameters. A range of possible values should also be provided for each parameter, in the form <parameter>=<lower-bound>:<upper-bound>. For example:

prism model.prism model.props -param x=0.2:0.4,y=-2:2

would specify a parameter x with lower bound 0.2 and upper bound 0.4, and a parameter y with values between -2 and 2. You can also omit the bounds for a parameter, in which case it will be assumed to have range 0 to 1.

The result of parametric model checking will be a mapping from regions (subsets of parameter valuations) to functions over the parameters. The regions are given as hyper-rectangles, e.g. "[ [0.2,0.3],[-2,0] ]" would represent the region of parameter valuations in which the first parameter is between 0.2 and 0.3 and the second is between -2 and 0. The results obtained are exact, that is no rounding errors are made during computation. Here is an example of the output of model checking:

prism model.prism model.props -param x=0:1
...
Result: ([0.0,1.0]): { 2 x - 5  | 8 x - 12  }

which indicates that, for the full range ([0,1]) of the parameter x, the result of model checking is the expression (2x-5)/(8x-12).

Parametric model checking can be configured with the following options:

  • -paramprecision <x>: PRISM uses regions in the form of hyper-rectangles to subsume parameter valuations with the same rational function or truth value. Because it is not always possible to cover the whole parameter space with hyper-rectangles, this option can be used to specify a precision, that is, an amount of the parameter space which may remain undecided. The default is 5/100.

  • -paramsplit <name>: During model checking, undecided regions may have to be split into several parts, because there might not exist a single rational function or truth value to which all parameter valuations of the original regions can be mapped. When a region is split, it can either be split at only its longest side (<name>=longest) or at all sides at once (<name>=all). The default is longest.

  • -parambisim <name>: The parametric analysis is costly in terms of time and memory, so it can help to perform bisimulation minimisation to speed up the analysis and use less memory. The possible options here are to use weak bisimulation (<name>=weak), strong bisimulation (<name>=strong) or none at all (<name>=none). The default is weak. In case an analysis is to be performed for which the current bisimulation type does not maintain validity of the results (e.g. weak bisimulation and a steady state analysis), an appropriate bisimulation engine is chosen automatically.

  • -paramfunction <name>: Sets the way rational functions are represented. Only Java Algebra System (JAS) is supported. The options are to use JAS directly (<name>=jas) or to use a version in which results of some previous mathematical operations performed during the analysis are cached (<name>=jas-cached). This can speed up computation, but also needs more memory. The default is to use the cached version.

  • -paramelimorder <name>: In the parametric engine, computations are performed by "eliminating" one state after the other, that is completely treating a state together with its incoming and outgoing transitions, rather than performing iterative methods. This option sets the order in which states are eliminated. The available values are: arbitrary order (<name>=arbitrary), forward starting from the initial states (<name>=forward), reversed forward order (<name>=forward-reversed), starting with target/unsafe states and then going backward (<name>=backward), the reverse of this order (<name>=backward-reversed) or random order (<name>=random). The default is the backward order.

  • -paramrandompoints <n>: Under some conditions, it has to be decided whether certain properties hold for all parameter valuations of a given region. This is the case for instance when computing truth values of properties for parametric DTMCs, CTMCs and MDPs, and also when computing any value for MDPs. At the moment, the truth values are only computed approximately, by evaluating and checking values at the edges of regions (as they are hyper-rectangles) and some random points. The exact number of random points to use is given with this option. The default is 5.

  • -paramsubsumeregions <b>: During the parametric analysis, quite a number of different regions might be created, which have to be stored in memory. If this option is used (<b>=true), PRISM tries to subsume neighbouring regions with the same value. The default is to use it.

Importing and exporting models

Once a model has been built, PRISM can export it to files, for examination or for use in another tool; conversely, you can import a model that has already been built, by PRISM or another tool. The file formats are described in "Explicit model files".

Exporting models

If required, once the model has been constructed, it can be exported, either for manual examination or for use in another tool. The following can all be exported:

  • the transition matrix (or function);
  • the rewards (state and transition rewards);
  • the labels (in the model or properties) and the states that satisfy them
  • the definition of (reachable) states, i.e., their variable values
  • the definition of observations, i.e., their observable values, for partially observable models

From the command-line version of PRISM, the most convenient and flexible approach is to use the -exportmodel switch. This will, by default, use the extension of the filename(s) to determine the format.

From the GUI, use the "Model | Export" menu to export the data to a file or, for small models, use the "Model | View" menu to print the details directly to the log. For the case of labels, if you want to export labels from the properties file too, use the "Properties | Export labels" option, rather than the "Model | Export" one.

The main formats for model export are:

  • plain text files (sometimes referred to as "explicit" or ".tra" or ".pexp" files)
  • UMB (Unified Markov binary) format, a binary format supported by other probabilistic model checkers
  • Dot format, for a graphical view of the model

Plain text (explicit files)

This format either exports all/multiple parts of the model into a single combined file, or individual parts of the model in different files. The expected filename extensions are:

  • .pexp - all parts of the model ("PRISM explicit")
  • .tra - transition matrix
  • .srew, .trew, .rew - rewards: states, transitions or both
  • .lab - labels
  • .sta - states
  • .obs - observations

and appending .gz or .xz to these extensions causes the file to be zipped.

To export everything, use:

prism model.prism -exportmodel model.pexp

To export everything zipped, use:

prism model.prism -exportmodel model.pexp.gz

To export everything except states, use:

prism model.prism -exportmodel model.pexp:states=false

To export just the transition matrix in this format, use:

prism model.prism -exportmodel model.tra

To export multiple parts, use, e.g.:

prism model.prism -exportmodel model.tra,sta

If you omit the basename of the export files, the basename of the model will be used, so this is equivalent to the above:

prism model.prism -exportmodel .tra,sta

You can use the shorthand .all to export everything to separate files, and .rew to export both state and transition rewards. For example:

prism model.prism -exportmodel model.all

You can always use stdout instead of a filename. For example:

prism model.prism -exportmodel stdout

is a quick way to print all parts of a (small) model to the terminal, or

prism model.prism -exportmodel stdout.sta

prints its states.

The labels (.lab) export includes the built-in labels "init" and "deadlock", providing a way to export information about initial states and (fixed) deadlock states.

When exporting multiple reward structures to individual files, a (1-indexed) suffix is added to distinguish them.

By default each part of the model is prefixed by a header (starting #), identifying what it is, plus some additional details, e.g., the name of a reward structure or the type of a model (see "Explicit model files"). This can be omitted - see the options below - or via the option "Include headers in model exports" in the GUI.

UMB (Unified Markov binary) format

UMB is a binary format that can incorporate all parts of the model listed above.

prism model.prism -exportmodel model.umb

By default, everything is included. You can omit some parts with the -exportmodel options rewards, labels, states and obs, e.g.:

prism model.prism -exportmodel model.umb:states=false,rewards=false

For a small model, you can also see a textual version of the UMB format using file extension .umbt (or option text):

prism model.prism -exportmodel stdout.umbt

UMB files are compressed by default (but still have the extension .umb). You can also configure the compression used: zip=false turns it off, zip=gzip uses gzip and zip=xz uses xz (smaller but slower to read/write).

Other formats and options

If the file extension is not recognised, PRISM defaults to plain text (explicit) format. You can always override this using the format option, e.g.:

prism model.prism -exportmodel model.txt:format=explicit
prism model.prism -exportmodel model.txt:format=umb,text

You can perform multiple model exports using several instances of -exportmodel, e.g.:

prism model.prism -exportmodel model.txt:format=explicit -exportmodel model.dot

Other file formats are also available:

  • Matlab code (extension .m) or format=matlab
  • Storm's DRN model format (extension .drn) or format=drn

Other -exportmodel options are:

  • states (true or false): whether to include states
  • rewards (true or false): whether to include rewards
  • labels (true or false): whether to include labels
  • actions (true or false): whether to include actions on choices/transitions
  • obs (true or false): whether to include observations
  • precision (<n>): use <n> significant figures for floating point values (in text)
  • headers (true or false): whether to include headers when exporting rewards
  • rows: export matrices with one row/distribution on each line (plain text)
  • proplabels: also export labels from a properties file into a .lab file
  • zip (true, false, gzip or xz): whether to zip the output and in what format

For plain text export, -exportmodel is usually the best switch to use, but there are also older switches. For example, you can export individual files using -exporttrans <file>, -exportstates <file>, -exportstaterewards <file>, -exporttransrewards <file>, -exportrewards <file> <file>, -exportlabels <file>, and -exportproplabels <file>. And you can use switches -exportmodelprecision <x>, -exportmatlab and -exportrows to specify format options affecting all of them.

Exporting (B)SCCs and end components

It is also possible to export the set of (bottom) strongly connected components (SCCs or BSCCs) for a model. This can only be done from the command-line. Use, for example:

prism model.prism -exportsccs stdout
prism model.prism -exportbsccs stdout

For an MDP, you can also export the set of maximal end components (MECs):

prism mdp.prism -exportmecs stdout

Importing models

It is also possible to construct models in PRISM through direct specification of their transition matrix. Two formats for explicit model import are supported:

  • plain text files (sometimes referred to as "explicit" or ".tra" or ".pexp" files)
  • UMB (Unified Markov binary) format, a binary format supported by other probabilistic model checkers

This functionality is only supported in the command-line version of the tool, usually using the -importmodel switch. In a similar fashion to -exportmodel switch, the type of import is usually determined from the file extension.

For UMB, all model info is contained in a single file. An example of import is:

prism -importmodel poll2.umb

For the plain text files (.tra etc.), various options are possible. To import everything (in the combined .pexp format) use:

prism -importmodel poll2.pexp

To just import the core part of the model (the transition function) use:

prism -importmodel poll2.tra

From explicit format, PRISM tries to determine the model type from the transitions data, using the model type included in the header, if present, and guessing from the format of the data if not. If this does not work, the model type can be overwritten using the -dtmc, -ctmc and -mdp switches. For example:

prism -importmodel poll2.tra -ctmc

Using the same formats as for model export, multiple other parts of the model can also be imported separately:

  • .lab - labels
  • .srew, .trew - rewards: states, transitions
  • .sta - states
  • .obs - observations

Here is an example of also importing labels and states:

prism -importmodel poll2.tra,sta,lab

If state information is not imported, a single zero-indexed variable x is assumed.

Note also that, since details about the initial state(s) of a model are not preserved in the .tra file, but are included in the labels file, this should also be used to designate a particular initial state for a model. Otherwise, state 0 is assumed to be the initial state or, if state information is imported, the state in which all variables take their minimum value is used.

Use the extension .all to import from multiple files containing separate parts of the model, named with appropriate file extensions:

prism -importmodel poll2.all

When providing the whole model, you can omit the -importmodel switch, e.g.:

prism poll2.pexp
prism poll2.all

Any files can be zipped, and this will be detected by their (.gz or .xz) filename extension. These are decompressed automatically on import.

Efficiency

Please note, for PRISM's symbolic model construction/engines, which are often used by default, this explicit method of constructing models in PRISM is typically less efficient than using the PRISM language. This is because the underlying data structures used to represent the model function better when there is high-level structure and regularity to exploit. You may want to switch to the "explicit" engine:

prism -importmodel poll2.tra -ex

The situation can also be alleviated to a certain extent for the symbolic implementations by importing the .sta file, since the composition of the states reintroduces some regularity (although it is still typically inefficient to construct).

Other options

In a similar style to PRISM's -exportmodel switch, while -importmodel is usually the most convenient, you can also specify each part separately, e.g.:

prism -importtrans poll2.tra -importstates poll2.sta -importlabels poll2.lab -ctmc

There are also -importstaterewards and -importtransrewards switches. You can import multiple reward structures using multiple instances of these switches. If present in the rewards files (see "Explicit model files"), the names of the reward structures are read too.

Other modelling languages

As well as models in the PRISM language, PRISM can work with models written in two other languages: the stochastic process algebra PEPA, and SBML, the Systems Biology Markup Language.

PEPA

For CTMCs, PRISM also accepts model descriptions in the stochastic process algebra PEPA [Hil96]. The tool compiles such descriptions into the PRISM language and then constructs the model as normal. The language accepted by the PEPA to PRISM compiler is actually a subset of PEPA. The restrictions applied to the language are firstly that component identifiers can only be bound to sequential components (formed using prefix and choice and references to other sequential components only). Secondly, each local state of a sequential component must be named. For example, we would rewrite:

P = (a,r).(b,s).P;

as:

P = (a,r).P';
P' = (b,s).P;

Finally, active/active synchronisations are not allowed since the PRISM definition of these differs from the PEPA definition. Every PEPA synchronisation must have exactly one active component. Some examples of PEPA model descriptions which can be imported into PRISM can be found in the prism-examples/pepa directory.

From the command-line version of PRISM, add the -importpepa switch and the model will be treated as a PEPA description. From the GUI, select "Model | Open model" and then choose "PEPA models" on the "Files of type" drop-down menu. Alternatively, select "Model | New | PEPA model" and either type a description from scratch or paste in an existing one from elsewhere. Once the PEPA model has been successfully parsed by PRISM, you can view the corresponding PRISM code (as generated by the PEPA-to-PRISM compiler) by selecting menu option "Model | View | Parsed PRISM model".

SBML

PRISM includes a (prototype) tool to translate specifications in SBML (Systems Biology Markup Language) to model descriptions in the PRISM language. SBML is an XML-based format for representing models of biochemical reaction networks. The translator works with Level 2 SBML files (it was written for Level 2 Version 1); see the SBML specifications.

Since PRISM is a tool for analysing discrete-state systems, the translator is designed for SBML files intended for discrete stochastic simulation. A useful set of such files can be found in the CaliBayes Discrete Stochastic Model Test Suite. There are also many more SBML files available in the BioModels.

We first give a simple example of an SBML file and its PRISM translation. We then give some more precise details of the translation process.

Example

An SBML file comprises a set of species and a set of reactions which they undergo. Below is the SBML file for the simple reversible reaction: Na + Cl ↔ Na+ + Cl-, where there are initially 100 Na and Cl atoms and no ions, and the base rates for the forwards and backwards reactions are 100 and 10, respectively.

<?xml version="1.0" encoding="UTF-8"?>
<sbml xmlns="http://www.sbml.org/sbml/level2" metaid="_000000" level="2" version="1">
  <model id="nacl" name="Na+Cl">

    <listOfCompartments>
      <compartment id="compartment"/>
    </listOfCompartments>

    <listOfSpecies>
      <species id="na" initialAmount="100" hasOnlySubstanceUnits="true"/>
      <species id="cl" initialAmount="100" hasOnlySubstanceUnits="true"/>
      <species id="na_plus" initialAmount="0" hasOnlySubstanceUnits="true"/>
      <species id="cl_minus" initialAmount="0" hasOnlySubstanceUnits="true"/>
    </listOfSpecies>

    <listOfReactions>
      <reaction id="forwards" reversible="false">
        <listOfReactants>
          <speciesReference species="na"/>
          <speciesReference species="cl"/>
        </listOfReactants>
        <listOfProducts>
          <speciesReference species="na_plus"/>
          <speciesReference species="cl_minus"/>
        </listOfProducts>
        <kineticLaw>
          <math xmlns="http://www.w3.org/1998/Math/MathML">
            <apply><times/><ci>forwards_rate</ci>
              <apply><times/><ci>na</ci><ci>cl</ci></apply></apply>
          </math>
          <listOfParameters>
            <parameter id="forwards_rate" value="100"/>
          </listOfParameters>
        </kineticLaw>
      </reaction>

      <reaction id="backwards" reversible="false">
        <listOfReactants>
          <speciesReference species="na_plus"/>
          <speciesReference species="cl_minus"/>
        </listOfReactants>
        <listOfProducts>
          <speciesReference species="na"/>
          <speciesReference species="cl"/>
        </listOfProducts>
        <kineticLaw>
          <math xmlns="http://www.w3.org/1998/Math/MathML">
            <apply><times/><ci>backwards_rate</ci>
              <apply><times/><ci>na_plus</ci><ci>cl_minus</ci></apply></apply>
          </math>
          <listOfParameters>
            <parameter id="backwards_rate" value="10"/>
          </listOfParameters>
        </kineticLaw>
      </reaction>
    </listOfReactions>

  </model>
</sbml>

And here is the resulting PRISM code:

// File generated by automatic SBML-to-PRISM conversion
// Original SBML file: nacl.xml

ctmc

const int MAX_AMOUNT = 100;

// Parameters for reaction forwards
const double forwards_rate = 100; // forwards_rate

// Parameters for reaction backwards
const double backwards_rate = 10; // backwards_rate

// Species na
const int na_MAX = MAX_AMOUNT;
module na

	na : [0..na_MAX] init 100; // Initial amount 100

	// forwards
	[forwards] na > 0 -> (na'=na-1);
	// backwards
	[backwards]  na <= na_MAX-1 -> (na'=na+1);

endmodule

// Species cl
const int cl_MAX = MAX_AMOUNT;
module cl

	cl : [0..cl_MAX] init 100; // Initial amount 100

	// forwards
	[forwards] cl > 0 -> (cl'=cl-1);
	// backwards
	[backwards]  cl <= cl_MAX-1 -> (cl'=cl+1);

endmodule

// Species na_plus
const int na_plus_MAX = MAX_AMOUNT;
module na_plus

	na_plus : [0..na_plus_MAX] init 0; // Initial amount 0

	// forwards
	[forwards]  na_plus <= na_plus_MAX-1 -> (na_plus'=na_plus+1);
	// backwards
	[backwards] na_plus > 0 -> (na_plus'=na_plus-1);

endmodule

// Species cl_minus
const int cl_minus_MAX = MAX_AMOUNT;
module cl_minus

	cl_minus : [0..cl_minus_MAX] init 0; // Initial amount 0

	// forwards
	[forwards]  cl_minus <= cl_minus_MAX-1 -> (cl_minus'=cl_minus+1);
	// backwards
	[backwards] cl_minus > 0 -> (cl_minus'=cl_minus-1);

endmodule

// Reaction rates
module reaction_rates

	// forwards
	[forwards] (forwards_rate*(na*cl)) > 0 -> (forwards_rate*(na*cl)) : true;
	// backwards
	[backwards] (backwards_rate*(na_plus*cl_minus)) > 0 -> (backwards_rate*(na_plus*cl_minus)) : true;

endmodule

// Reward structures (one per species)

// 1
rewards "na" true : na; endrewards
// 2
rewards "cl" true : cl; endrewards
// 3
rewards "na_plus" true : na_plus; endrewards
// 4
rewards "cl_minus" true : cl_minus; endrewards

From the latter, we can use PRISM to generate a simple plot of the expected amount of Na and Na+ over time (using both model checking and a single random trace from the simulator):

Plot of expected amount against time T from 0 to 0.0002: Na falls from 100 to about 36 and Na+ rises from 0 to about 64, crossing at around T=0.0001. Solid lines show model checking results; dashed lines show a single simulated trace that roughly follows them.

Using the translator

The SBML-to-PRISM translator is included in the PRISM code-base, but not integrated into the application itself.

cd prism
java -cp classes prism.SBML2Prism sbml_file.xml > prism_file.prism

If you are using a binary (rather than source code) distribution of PRISM, replace classes with lib/prism.jar in the above.

Alternatively (on Linux or macOS), ensure prism is in your path and then save the script below as an executable file called sbml2prism:

#!/bin/sh

# Startup script for SBML-to-PRISM translator

# Launch using main PRISM script
PRISM_MAINCLASS="prism.SBML2Prism"
export PRISM_MAINCLASS
prism "$@"

Then use:

sbml2prism sbml_file.xml > prism_file.prism

The following PRISM properties file will also be useful:

const double T;
const int c;

R{c}=? [I=T]

This contains a single property which, based on the reward structures in the PRISM model generated by the translator, means "the expected amount of species c at time T". The constant c is an integer index which can range between 1 and N, where N is the number of species in the model. To view the expected amount of each species over time, create an experiment in PRISM which varies c from 1 to N and T over the desired time range.

Details of the translation

The basic structure of the translation process is as follows:

  • Each species in the SBML file is represented by a module in the resulting PRISM file. This module, which (where possible) retains the SBML species id as its name, contains a single variable whose value represents the amount of the species present. A corresponding reward structure for computing the expected amount of the species at a given time instant is also created. Species for which the boundaryCondition flag is set to true in the SBML file do not have a corresponding module.

  • Each reaction in the SBML file is associated with a unique synchronisation action label. The module for each species which takes part in the reaction will include a synchronous command to represent this. An additional PRISM module called reaction_rates stores the expression representing the rate of each reaction (from the corresponding kineticLaw section in the SBML file). Reaction stoichiometry information is respected but must be provided in the scalar stoichiometry field of a speciesReference element, not in a separate StoichiometryMath element.

  • Each parameter in the SBML file, either global to the file or specific to a reaction, becomes a constant in the PRISM file. If a value for this parameter is given, it is used. If not, the constant is left as undefined.

As described above, this translation process is designed for discrete systems and so the amount of each species in the model is represented by an integer variable. It is therefore assumed that the initial amount for each species specified in the SBML file is also given as an integer. If this is not the case, then the values will need to be scaled accordingly first.

Furthermore, since PRISM is primarily a model checking (rather than simulation) tool, it is important that the amount of each species also has an upper bound (to ensure a finite state space). When model checking, the efficiency (or even feasibility) of the process is likely to be very sensitive to the upper bound(s) chosen. When using the discrete-event simulation functionality of PRISM, this is not the case and the bounds can be set much higher. By default the translator uses an upper bound of 100 (which is increased if the initial amount exceeds this). A different value can be specified through a second command-line argument as follows:

cd prism
java -cp classes prism.SBML2Prism sbml_file.xml 1000 > prism_file.prism

Alternatively, upper bounds can be modified manually after the translation process.

Finally, the following aspects of SBML files are not supported and are ignored during the translation process:

  • compartments
  • events/triggers

Configuration and performance

PRISM is highly configurable, in terms of the various model checking algorithms and techniques that it uses, and the different ways that they are implemented and parameterised.

Changing settings

GUI: In the GUI, select "Options" from the main menu to bring up the "Options" dialog. The first two tabs contain core PRISM settings, discussed in this section, and simulator options; the others configure aspects of the GUI itself. If you wish, you can choose "Save Options" to store your changes in a settings file, to be reloaded as defaults next time. To restore the default settings, click "Load Defaults" and then "Save Options".

Command line: From the command line, settings are changed via switches. You can use either -switch or --switch and many options have abbreviations, so for example these are all equivalent:

prism model.prism model.props -ex
prism model.prism model.props -explicit
prism model.prism model.props --explicit

See the "Command-line switches" section for a full list, or type prism -help. To display details of a switch, use:

prism -help exportmodel

The command-line version ignores the GUI settings file, unless you choose to load it with the -settings switch, e.g., on Linux: prism -settings ~/.config/prism.settings.

Contents

This section guides you through some of the key settings for PRISM.

See also the guidance on running out of memory.

Settings file

The PRISM settings file, used primarily by the GUI, is in a simple textual format and can also be edited by hand, or deleted to restore the default settings the next time the GUI is started. Where it is stored depends on the operating system:

  • $HOME/.prism (if this file already exists, as created by PRISM versions before 4.5)
  • $XDG_CONFIG_HOME/prism.settings (on Linux, if that environment variable is set)
  • $HOME/.config/prism.settings (on Linux, if $XDG_CONFIG_HOME is not set)
  • $HOME/Library/Preferences/prism.settings (on macOS)
  • .prism in the user's home directory, e.g. C:\Users\username (on Windows)

Computation engines

PRISM contains multiple engines: these are distinct implementations of model checking, differing in the data structures and technologies used, and in the range of models and properties that they can handle.

Core engines

There are four core engines, listed below, which are general purpose and all cover the majority of PRISM's functionality for the three most commonly used models of DTMCs, MDPs and CTMCs. These should yield the same results for the same model and property (assuming that the same algorithms and settings are used) but vary in performance and scalability (i.e., time and memory usage). The latter is discussed in more detail in "Which engine should I use?" below.

  • The explicit engine: implemented purely in Java, using explicit-state data structures (sparse matrices and variants). This supports the widest selection of solution methods, and also the most different model types, for example, it is the only engine that supports POMDPs and uncertain MDPs/DTMCs. PRISM will usually switch to this engine automatically if it is the only one that can handle a particular model, property or solution method.

  • The MTBDD engine: fully symbolic, storing both the model and the value vectors computed from it as binary decision diagrams (BDDs) and multi-terminal BDDs (MTBDDs). This engine can handle extremely large models, as long as they are structured and regular.

  • The sparse engine: builds the model symbolically, as an MTBDD, but then converts it to a sparse matrix for numerical computation. This typically makes it faster to solve, but may use more memory.

  • The hybrid engine (the default): builds the model symbolically, like the sparse engine, and performs numerical computation with a combination of MTBDDs (for the model) and arrays (for vectors), representing a trade-off between memory usage and solution speed [KNP04b].

PRISM's MTBDD, sparse and hybrid engines are referred to collectively as its symbolic engines, since they all rely on a symbolic (MTBDD-based) representation of the model being built first. These engines are mostly implemented in C++, using the CUDD library for BDDs and MTBDDs.

When using the PRISM GUI, the engine to be used for model checking can be selected from the "Engine" option under the "PRISM" tab of the "Options" dialog. From the command-line, engines are activated using the -explicit, -mtbdd, -sparse and -hybrid (or -ex, -m, -s and -h, respectively) switches, e.g.:

prism model.prism model.props -ex
prism model.prism model.props -m
prism model.prism model.props -s
prism model.prism model.props -h

Other engines

PRISM's other engines typically work on a specific set of models and/or properties, and may also vary in the accuracy of the results that they compute.

  • The statistical model checking engine generates approximate results using discrete-event simulation, and without building the full model, often improving scalability but at the cost of accuracy. From the GUI, it is used by choosing "Simulate" menu items or tick boxes; from the command-line, add the -sim switch. See "Statistical model checking" for details.

  • The exact engine computes exact numerical results, using arbitrary precision arithmetic. You can enable this functionality using the "Do exact model checking" option in the GUI or using switch -exact from the command line. This is implemented as a special case of parametric model checking, which limits its application to relatively small models. It can be used for analysing DTMCs/CTMCs (unbounded until, steady-state probabilities, reachability reward and steady-state reward) or MDPs (unbounded until and reachability rewards).

  • The parametric engine computes results exactly, as functions of the model's parameters. It is used with the -param switch: see "Parametric model checking".

  • PTA model checking is performed with one of three specific engines, stochastic games, digital clocks and backwards reachability, which are described in "Real-time models". These are chosen with the "PTA model checking method" setting in the GUI or the -ptamethod switch on the command line.

Which engine should I use?

Sometimes a specific engine is required for a particular model (e.g., for PTAs) or is requested in order to achieve a particular accuracy (e.g., exact or parametric results). Similarly, the explicit engine is sometimes the only option for a model class, such as POMDPs and uncertain MDPs/DTMCs.

In other cases, any of the four core engines can normally be used, with the current default being the hybrid engine. If PRISM is using too much time or memory with one engine, it may be worth experimenting with others, since their performance can vary, depending on the size of the model and how it is described. Details of the memory usage and model size are displayed during model checking (from the GUI, check the "Log" tab).

  • The explicit engine has the most predictable performance, with time and memory usage increasing as the size of the model does. Unlike the symbolic engines, performance does not depend on how compact a model's MTBDD-based representation is, which can be unpredictable. Building the model is often slower using the explicit engine, but the solution time is more comparable to that of the other core engines. The explicit engine is usually the best choice when:

    • importing from explicit-state formats, such as UMB (.umb) or PRISM's own "explicit" file formats (.pexp, .tra, etc.);

    • building "explicit-style" PRISM models (i.e., essentially comprising an unstructured list of states/transitions, but encoded into a textual description in the PRISM modelling language);

    • building models that are potentially very large, in terms of the number of model variables and their range, but where only a small fraction of states are reachable.

  • The hybrid engine, amongst the three symbolic engines, generally provides the best compromise between time and memory usage: it uses less memory than the sparse engine, but is typically slightly slower.

  • The sparse engine can be a good alternative to the hybrid engine when model checking takes a long time, but the model is small enough to fit in memory (as a rule of thumb, the sparse engine scales up to models about a factor of 10 smaller than the hybrid one).

  • The MTBDD engine has the potential to scale up to very large models, beyond the range of what can be handled by the other three, but is much more unpredictable in terms of performance. Roughly speaking, when the model description (in the PRISM language) exhibits a lot of structure and regularity, it can be very effective. But the MTBDD engine often performs poorly when the model (or solutions computed from it) contain many distinct probabilities/rates; it performs best when there are few such values. For this reason the engine is often successfully applied to MDP models, but much less frequently to CTMCs.

For all three symbolic engines (MTBDD, sparse, hybrid), various aspects of the (PRISM language) model description can impact performance, including its variable ordering; see "PRISM modelling" in the FAQ for details.

Symbolic engine options

A few further settings fine-tune the symbolic engines. The defaults are usually fine.

  • Hybrid engine: to speed up numerical computation, the hybrid engine replaces the lowest levels of its MTBDDs with sparse matrices [Par02]. The number of levels replaced is set with -sbl <n> (the default, -1, lets PRISM choose) and the memory these sparse matrices can use, in KB, with -sbmax <n> (default 1024). For the hybrid engine's Gauss-Seidel and SOR methods, the matrix is also divided into blocks: -gsl <n> and -gsmax <n> (or -sorl and -sormax) set the number of MTBDD levels used for this division and its memory limit in KB.
  • Sparse and hybrid engines: by default, sparse matrices and vectors with many repeated values are compressed further; -nocompact switches this off.
  • CUDD, the BDD/MTBDD library: besides its memory limit (see "Memory and model size"), -cuddepsilon <x> sets the precision used when CUDD compares values in its cache (default 10−1510^{-15}), and -ddextrastatevars <n> and -ddextraactionvars <n> set how many extra MTBDD variables are preallocated for transformations of the model (default 20 each). -ddsanity enables internal sanity checks, for debugging (this slows PRISM down).

Solution methods and options

Separately from the choice of engines, PRISM often offers several different solution methods that can be used for the computation of probabilities and expected costs/rewards during model checking. Many, but not all, of these are iterative numerical methods. The choice of method (and their settings) depends on the type of analysis that is being done (i.e., what type of model and property) and can also be configured using various options.

This page focuses on core properties for the most common model types (DTMCs, MDPs and CTMCs). See the other sections of the manual for solution methods available for real-time models, partially observable models, and uncertain/interval models.

Convergence

Many of the methods below are iterative: they compute a sequence of approximations to the solution and stop once it has converged sufficiently. PRISM checks for convergence by comparing the solution vectors from successive iterations (or, for interval iteration, the vectors from the iterations from below and from above). The following settings control this, and apply to all of these methods:

  • "Termination epsilon" (switch -epsilon <val>): iteration stops when the maximum difference between elements of the two vectors drops below this threshold. The default is 10−610^{-6}.
  • "Termination criteria" (switches -relative and -absolute, or -rel and -abs): whether that maximum difference is relative or absolute. The default is relative.
  • "Termination max. iterations" (switch -maxiters <val>): an upper limit on the number of iterations, to trap cases where computation will not converge. The default is 10,000. Reaching the limit causes an error during model checking.

Linear equation systems

For many properties of Markov chains (e.g. "reachability"/"until" properties for DTMCs and CTMCs, steady-state properties for CTMCs and "reachability reward" properties for DTMCs), PRISM solves a set of linear equation systems, for which several numerical methods are available. Below is a list of the alternatives and the switches used to select them from the command-line. The corresponding GUI option is "Linear equations method".

  • Power method: -power (or -pow, -pwr)
  • Jacobi method: -jacobi (or -jac)
  • Gauss-Seidel method: -gaussseidel (or -gs)
  • Backwards Gauss-Seidel method: -bgaussseidel (or -bgs)
  • JOR method (Jacobi with over-relaxation): -jor
  • SOR method: -sor
  • Backwards SOR method: -bsor

When using the MTBDD engine, Gauss-Seidel/SOR based methods are not available. When using the hybrid engine, pseudo variants of Gauss-Seidel/SOR based methods can also be used [Par02] (see "Command-line switches" for the corresponding switches). For methods which use over-relaxation (JOR/SOR), the over-relaxation parameter (between 0.0 and 2.0) can also be specified with option "Over-relaxation parameter" (switch -omega <val>).

All of these are iterative methods, so the convergence settings above apply.

MDP solution methods

When analysing MDPs, there are multiple solution methods on offer. A summary, and their command-line switches, are given below. From the GUI, the first five can be selected under the "MDP solution method" option. The last two are variants that are selected as separate options, and can also be used for DTMCs. All except value iteration are only supported by the explicit engine, which PRISM switches to automatically (with a warning) if one of them is selected. Where they are iterative, the convergence settings above apply.

  • Value iteration (switch -valiter) [this is the default]: repeatedly updates the value of every state from the values of its successors, until the values converge.
  • Gauss-Seidel (switch -gs): a variant of value iteration that uses newly computed values straight away, within the same iteration, which often makes it converge faster.
  • Policy iteration (switch -politer): alternates between computing the values for a fixed policy/strategy and improving it, until there is no change.
  • Modified policy iteration (switch -modpoliter): like policy iteration, but computes the values for each policy/strategy approximately, with a few steps of value iteration. This is only implemented for probabilities: for reward properties, PRISM switches to Gauss-Seidel (with a warning).
  • Linear programming (switch -lp): encodes the problem as a linear program and solves it directly, rather than iteratively.
  • Interval iteration [HM14],[BKLPW17] (switch -intervaliter or -ii, or GUI option "Use interval iteration"): performs two separate instances of iterative solution, one from below and one from above. This gives clearer information about the accuracy of the computed values and avoids possible problems with premature convergence. A variety of options can be configured, either using -intervaliter:option1,option2,... or by setting the string "option1,option2,..." under "Interval iteration options" in the GUI. See -intervaliter in the list of command-line switches (or type prism -help intervaliter) for the options and [BKLPW17] for the details.
  • Topological value iteration (switch -topological, or GUI option "Use topological value iteration"): improves the efficiency of value iteration by analysing the graph structure of the model, and using this to update the values of states in an order that speeds up convergence. It can also be used to optimise interval iteration and the numerical solution of DTMCs. It is only implemented in the explicit engine, which PRISM switches to automatically (with a warning) if another engine is selected. The exception is DTMC/CTMC solution with a linear equation method that the explicit engine does not support (such as pseudo Gauss-Seidel or SOR), where -topological is ignored (again, with a warning).

CTMC transient analysis

When computing transient probabilities of a CTMC (either directly or when verifying time-bounded operators of CSL), there are two options: uniformisation and fast adaptive uniformisation (FAU). These can be selected using the GUI option "Transient probability computation method", or using the command-line switch -transientmethod <name>, where <name> is either unif or fau.

Uniformisation

Uniformisation is a standard iterative numerical method for computing transient probabilities on a CTMC, which works by reducing the problem to an analysis of a "uniformised" DTMC. As an optimisation, when it is detected that the transient probabilities have converged, no further iterations are performed. If necessary (e.g. in case of round-off problems), this optimisation can be disabled with the "Use steady-state detection" option (command-line switch -nossdetect).

Fast adaptive uniformisation (FAU)

Fast adaptive uniformisation (FAU) [MWDH10] is a method to efficiently approximate transient properties of large CTMCs. The basic idea is that only the parts of the model that are relevant for the current time period are kept in memory. In more detail, starting with the initial states, in each step FAU explores further states in a DTMC which is a discrete-time version of the original CTMC. By combining the probabilities there with those of a certain continuous-time stochastic process (a birth process), transient properties in the original CTMC can be computed. If it turns out that the probability of being in some state in the DTMC is below a given threshold, this state is removed from the model explored so far. After a given number of steps, which corresponds to the number of steps which are likely to happen within the time bound, the exploration can be stopped. In the implementation in PRISM [DHK13], FAU can be used to compute transient probability distributions and to model check the following types of non-nested CSL formulas: time-bounded until, instantaneous reward, cumulative reward.

The following options can be used to configure FAU:

  • "FAU epsilon" (switch -fauepsilon <x>): FAU analyses the DTMC for a number of iterations such that the probability of more steps being relevant is below this value. The default is 1e-6.

  • "FAU cut off delta" (switch -faudelta <x>): States that have a lower probability than this value are discarded. The default is 1e-12.

  • "FAU array threshold" (switch -fauarraythreshold <x>): After this number of steps without any new states being explored or discarded, FAU will switch to a faster, fixed-size data structure until further states have to be explored or discarded. The default is 100.

  • "FAU time intervals" (switch -fauintervals <x>): In some cases, it is advantageous to divide the time interval the analysis is done for into several smaller intervals. This option dictates the number of (equal length) intervals used for this split. The default is 1, meaning that only one time interval is used.

  • "FAU initial time interval" (switch -fauinitival <x>): It is also possible to specify an additional initial time interval which is handled separately from the rest of the time. This is often advantageous, because in this interval certain parameters of the model can be explored, which can subsequently be used to speed up the computation of the remaining time interval. The default for this option is 1.0.

Automata generation

When PRISM performs verification of LTL formulas, it does so by converting the formula into an automaton (such as a deterministic Rabin automaton) and then analysing a larger product model, constructed from the model being verified and the omega automaton. For this reason, the size of the automaton has an important effect on the efficiency of verification.

By default PRISM uses a port of the ltl2dstar library to construct these automata. But it also allows the use of external LTL-to-automata converters producing deterministic automata through support for the Hanoi Omega Automaton (HOA) format. From the command line, an example of this is:

prism model.prism -pf "P=? [ G F x=1 ]" -ltl2datool hoa-ltl2dstar-for-prism -ltl2dasyntax lbt

The -ltl2datool switch specifies the location of the program to be executed to perform the LTL-to-automaton conversion. This will be called by PRISM as "exec in-file out-file", where exec is the executable, in-file is the name of a file containing the LTL formula to be converted and out-file is the name of a file where the resulting automaton should be written, in HOA format. Typically, the executable will be a script. Here is a simple example (called as hoa-ltl2dstar-for-prism in the above example), which calls an external copy of ltl2dstar in the required fashion (assuming that the ltl2dstar and ltl2ba executables are located in the current directory or on the PATH).

#! /bin/bash
ltl2dstar --output=automaton --output-format=hoa "$1" "$2"

PRISM is known to work with these HOA-enabled tools:

and contains ready-made scripts for calling them in the etc/scripts/hoa directory of the distribution:

See the files themselves for details of any configuration required, possible options and for a reminder of the PRISM command-line arguments required.

There is also a hoa-rabinizer-for-prism.bat script for connecting to Rabinizer on Windows.

The -ltl2dasyntax switch is used to specify the textual format for passing the LTL formula to the external converter (i.e., in the file in-file). The options are:

  • lbt: LBT format
  • spin: SPIN format
  • spot: Spot format
  • rabinizer: Rabinizer format

Typical usage is:

prism model.prism -pf "P=? [ G F x=1 ]" -ltl2datool hoa-ltl2dstar-for-prism -ltl2dasyntax lbt
prism model.prism -pf "P=? [ G F x=1 ]" -ltl2datool hoa-ltl2tgba-for-prism -ltl2dasyntax lbt
prism model.prism -pf "P=? [ G F x=1 ]" -ltl2datool hoa-ltl3dra-for-prism -ltl2dasyntax spin
prism model.prism -pf "P=? [ G F x=1 ]" -ltl2datool hoa-rabinizer-for-prism -ltl2dasyntax rabinizer

From the GUI, configuring the external LTL converter is done with the two options "Use external LTL->DA tool" and "LTL syntax for external LTL->DA tool".

Another related option is "All path formulas via automata" (command-line switch -pathviaautomata), which forces construction of an automaton when computing the probability of a path formula, even if it is not needed. This is primarily intended for debugging/testing, not regular use. Likewise, by default PRISM simplifies the automata it builds, and their acceptance conditions, where it can; -nodasimplify (GUI option "Do not simplify deterministic automata") switches this off.

As mentioned above, PRISM's external LTL-to-automaton interfacing works using the HOA format (and, in particular, using the jhoafparser HOA parser). PRISM can handle automata in HOA format that are deterministic and complete, with state-based acceptance. Automata with transition-based acceptance are converted to state-based acceptance by PRISM. For DTMC and CTMC model checking, generic acceptance conditions are supported, i.e., anything that can be specified as an Acceptance: header in HOA format. For MDP model checking, Rabin and generalised Rabin acceptance specified via the acc-name: header are supported. See the HOA format specification for details.

Memory and model size

Probabilistic model checking can need a lot of memory. This page describes how PRISM uses memory, and how to give it more. See also the "Memory problems" section of the FAQ.

CUDD memory

CUDD, the underlying BDD and MTBDD library used in PRISM's symbolic engines, has an upper memory limit. By default, this limit is 1 GB. If you are working on a machine with significantly more memory than this and PRISM runs out of memory when model checking, it may help to change this. To set the limit, from the command-line, use the -cuddmaxmem switch. For example:

prism -cuddmaxmem 2g big_model.prism

Above, g denotes GB. You can also use m for MB. You can also change the CUDD maximum memory setting from the options panel in the GUI, but you will need to close and restart the GUI (saving the settings as you do) for this to take effect.

Java memory

The Java virtual machine (JVM) used to execute PRISM also has upper memory limits. This is more likely to impact the explicit engine. Sometimes this limit will be exceeded and you will see an error of the form java.lang.OutOfMemoryError. To resolve this problem, you can increase this memory limit. On Unix, Linux or macOS platforms, this can be done by using the -javamaxmem switch, passed either to the command-line script prism or the GUI launcher xprism. For example:

prism -javamaxmem 4g big_model.prism
xprism -javamaxmem 4g big_model.prism

each set the limit to 4 GB. Alternatively, you can set the environment variable PRISM_JAVAMAXMEM before running PRISM. For example, under a bash shell:

PRISM_JAVAMAXMEM=4g
export PRISM_JAVAMAXMEM
prism big_model.prism

If you get an error of the form java.lang.StackOverflowError, then you can try increasing the stack size of the JVM. On Unix, Linux or macOS platforms, this can be done by using the -javastack switch or the PRISM_JAVASTACKSIZE environment variable. Examples are:

prism -javastack 1g big_model.prism
xprism -javastack 1g big_model.prism

or:

PRISM_JAVASTACKSIZE=1g
export PRISM_JAVASTACKSIZE
prism big_model.prism

If you are running PRISM on Windows you will have to make adjustments to Java memory manually, by modifying the prism.bat or xprism.bat scripts. To set the memory to 4 GB, for example, add -Xmx4g to the list of arguments in the call to java or javaw at the end of the file. To change the stack size to 1 GB, add -Xss1g.

Other Java options

If you want to pass additional switches to the JVM used to run PRISM, you can use the -javaparams switch. For example:

prism -javaparams "-XX:AutoBoxCacheMax=100000000 -Xmn2g" -javamaxmem 12g big_model.prism

Alternatively (or in conjunction with -javaparams), the PRISM_JAVA_PARAMS environment variable passes switches to the JVM.

Finally, the PRISM_JAVA environment variable can be used to specify the java executable to use (by default, it is the one on your path).

Other options

This page describes some further options, not covered elsewhere in this section. All the options available from the command line are listed in "Command-line switches".

Output and logging

From the command line, the log can be written to a file instead of the screen with -mainlog <file>; add :append (e.g. -mainlog log.txt:append) to add to the end of an existing file rather than overwrite it.

To increase the amount of information displayed by PRISM (in particular, to display lists of states and probability vectors), you can use the "Verbose output" option (activated with command-line switch -verbose or -v). To display additional statistics about MTBDDs after model construction, use the "Extra MTBDD information" option (switch -extraddinfo) and, to view MTBDD sizes during the process of reachability, use option "Extra reachability information" (switch -extrareachinfo).

To see how iterative numerical methods progress, the switch -exportiterations (or GUI option "Export iterations (debug/visualisation)") writes the solution vector at each iteration to the file iterations.html, for debugging or visualisation.

Model construction

Probability/rate checks

By default, when constructing a model, PRISM checks that all probabilities and rates are within acceptable ranges (i.e. are between 0 and 1, or are non-negative, respectively). For DTMCs and MDPs, it also checks that the probabilities sum up to one for each command. These checks are often very useful for highlighting user modelling errors and it is strongly recommended that you keep them enabled, however if you need to disable them you can do so via option "do prob checks?" in the GUI or command-line switch -noprobchecks. You can also change the level of precision used to check that probabilities sum to 1 using the option "Probability sum threshold" (or command-line switch -sumroundoff).

Model checking

Precomputation

By default, PRISM's probabilistic model checking algorithms use an initial precomputation step which uses graph-based techniques to efficiently detect trivial cases where probabilities are 0 or 1. This can often result in improved performance and also reduce round-off errors. Occasionally, though, you may want to disable this step for efficiency (e.g. if you know that there are no/few such states and the precomputation process is slow). This can be done with the -nopre switch. You can also disable the individual algorithms for probability 0/1 using switches -noprob0 and -noprob1.

The explicit engine speeds up precomputation (and some other graph algorithms) by first computing the predecessor relation of the model; -noprerel switches this off, saving the memory it needs.

Fairness

Sometimes, model checking of properties for MDPs requires fairness constraints to be taken into account. See e.g. [BK98],[Bai98] for more information. To enable the use of fairness constraints (for P operator properties), use the -fair switch.

End components

For maximum probabilities in MDPs, the switch -pmaxquotient makes PRISM first collapse each maximal end component (MEC) of the model into a single state, and compute in this quotient model.

SCC decomposition

Some algorithms, e.g. for steady-state probabilities and LTL model checking, decompose the model into strongly connected components (SCCs). For the symbolic engines, the algorithm used for this can be chosen with -sccmethod <name> (or the GUI option "SCC decomposition method"): xiebeerel, lockstep (the default) or sccfind.

Time-outs

The command-line version of PRISM has a time-out option, specified using the switch -timeout <n>. This causes the program to exit after <n> seconds if it has not already terminated by that point. This is particularly useful for benchmarking scenarios where you wish to ignore runs of PRISM that exceed a certain length of time.

Reference

Here, we collate various reference documents related to PRISM and its usage/configuration.

Contents

PRISM language syntax

This reference documents various aspects of the PRISM language syntax, covering both model and property specification.

Model and property files

Files containing models specified in the PRISM modelling language and properties expressed in the PRISM property specification language are stored as plain text files, with the file extensions .prism and .props, respectively.

Files can contain any amount of white space (spaces, tabs, new lines, etc.), all of which is ignored when the file is parsed. Comments are written using //, which starts a comment that runs to the end of the line.

Model types

A model type keyword, usually at the very start of a model file, indicates the type of model being specified, and can be any of the following:

  • dtmc (DTMC: discrete-time Markov chain)
  • ctmc (CTMC: continuous-time Markov chain)
  • mdp (MDP: Markov decision process)
  • pta (PTA: probabilistic timed automaton)
  • pomdp (POMDP: partially observable MDP)
  • popta (POPTA: partially observable PTA)

Based on features that are included in a model, PRISM will, to some extent, auto-detect the model type if no keyword is given and adapt the model type beyond the keyword if features are added that require a different type. Indeed, some model types do not have explicit keywords (e.g., interval MDPs), and are only identified by the features that they use.

  • The default model type is MDP, unless no probabilities are used, in which case it is an LTS (labelled transition system).
  • An MDP model with clock variables is treated as a PTA, even if the pta keyword is not used.
  • An MDP or PTA with observables is treated as a POMDP or POPTA (partially observable PTA), respectively.
  • If a model uses intervals for probabilities, it is treated as an interval variant: an IDTMC (interval DTMC) or IMDP (interval MDP).

Identifiers and keywords

Identifiers (names of modules, variables, constants, formulas and so on) are made up of letters, digits and underscores, but cannot start with a digit: they match [A-Za-z_][A-Za-z0-9_]*. They are case-sensitive. They cannot be any of PRISM's keywords:

A, bool, C, clock, const, ctmc, double, dtmc, E, endinit, endinvariant, endmodule, endobservables, endrewards, endsystem, F, false, filter, formula, func, G, global, I, init, int, invariant, label, max, maxmax, maxmin, mdp, min, minmax, minmin, module, nondeterministic, observable, observables, P, Pmax, Pmaxmax, Pmaxmin, Pmin, Pminmax, Pminmin, pomdp, popta, prob, probabilistic, pta, R, rate, rewards, Rmax, Rmaxmax, Rmaxmin, Rmin, Rminmax, Rminmin, S, stochastic, system, true, U, W, X.

Uniqueness: The names of variables (global, or local to any module), constants and formulas share a single namespace, so they must all be distinct. Constants defined in a properties file must also be distinct from all of these names in the model. Modules, actions and reward structures each have their own, separate, namespace, so their names only need to be unique within their own category, not across all names in the model. Names written in quotes, i.e., those of labels, observables and named properties, form another namespace: these must be distinct from each other, across both the model and the properties file. The labels "init" and "deadlock" are built in and cannot be redefined.

Expressions

Expressions are used in both models and properties. Depending on the context, they can include references to variables, constants and labels, as well as various operators, literals and functions.

Operators

The table below lists operators that can be used in expressions, from the most strongly binding (1) to least.

Precedence Operator Meaning Associativity
1 - unary minus
2 ^ power right
3 *, / multiplication, division left
4 +, - addition, subtraction left
5 <, <=, >=, > relational operators left
6 =, != equality operators left
7 ! negation
8 & conjunction left
9 | disjunction left
10 <=> if-and-only-if left
11 => implication right
12 ? : condition: c ? a : b is a if c is true and b otherwise right

So, for example, -x^2 means (-x)^2, and 2^3^2 means 2^(3^2). Division / always gives a double, not integer division: 22/7 is 3.142857..., not 3.

In properties, the temporal operators bind less tightly than all of these.

Literals
  • Integers: 0, 42
  • Doubles: 0.5, .5, 1e-3, 2.5E+6
  • Booleans: true, false

Built-in functions
Function Result
min(a,b,...), max(a,b,...) minimum or maximum of two or more numbers
floor(x), ceil(x) x rounded down or up to an integer
round(x) x rounded to the nearest integer (ties round up: round(-1.5) is -1)
pow(x,y) x to the power y (as x^y)
mod(i,n) i modulo n (mod(-7,3) is 2)
log(x,b) logarithm of x to base b

Legacy syntax

Older versions of PRISM used some different conventions and syntax, which are still accepted for compatibility. New models and properties should use the current forms.

  • File extensions: model files used to have extensions .pm (DTMCs), .nm (MDPs, PTAs) or .sm (CTMCs), not .prism.
  • File extensions: property files used to have extensions .pctl or .csl, not .props.
  • Model types: probabilistic, nondeterministic and stochastic were formerly synonyms for dtmc, mdp, ctmc.
  • Integer-valued constants: were previously declared as const N = 5;, meaning const int N = 5;.
  • Double-valued constants: could previously also be written as rate r = 0.5; or prob p = 0.1;, meaning const double r = 0.5;.
  • Functions: could be written with a special func keyword, e.g., func(floor, x) or func(min, a, b), instead of the current forms floor(x) and min(a, b).
  • Filters: the old-style syntax for filters in properties was, e.g., P=? [ path {states} ] for filter(state, P=? [ path ], states), with {states}{min}, {states}{max} and {states}{min}{max} for the min, max and range filters.

Command-line switches

This page lists the switches accepted by the command-line version of PRISM, grouped as in the output of prism -help. Many of them are described in more detail elsewhere in this manual, and most of the settings they change can also be made in the GUI (from the Options menu) or in the settings file. For switches whose syntax is not obvious, prism -help followed by the switch, e.g., prism -help exportmodel, gives the details shown below.

The list is generated from PRISM itself, so it is complete for this version of PRISM. Switches are typed with a single -, as shown, but -- also works, e.g., --version.

General

  • -help: Display this help message

  • -version: Display PRISM version info

  • -javaversion: Display Java version info

  • -dir <dir>: Set current working directory

  • -settings <file>: Load settings from <file>

  • -mainlog <file>[:<options>]: Write the log to <file> instead of stdout

    If provided, <options> is a comma-separated list of options taken from:

    • append: Append to the log file, rather than overwriting it
  • -pf <props> (or -pctl, -csl): Model check properties <props>

  • -property <refs> (or -prop): Only model check properties included in list <refs> of indices/names

  • -const <vals>: Define constant values as <vals> (e.g. for experiments)

    <vals> is a comma-separated list of values or value ranges for undefined constants in the model or properties (i.e. those declared without values, such as "const int a;"). You can either specify a single value (a=1), a range (a=1:10) or a range with a step (a=1:2:50). For convenience, constant definitions can also be split across multiple -const switches.

    Examples:

    -const a=1,b=5.6,c=true
    -const a=1:10,b=5.6
    -const a=1:2:50,b=5.6
    -const a=1:2:50 -const b=5.6
    
  • -steadystate (or -ss): Compute steady-state probabilities (D/CTMCs only)

  • -transient <x> (or -tr): Compute transient probabilities for time (or time range) <x> (D/CTMCs only)

  • -simpath <options> <file>: Generate a random path with the simulator

    Generate a random path with the simulator and export it to <file> (or to the screen if <file>="stdout"). <options> is a comma-separated list of options taken from:

    • <n>: generate a path of <n> steps
    • time=<x>: generate a path of at least <x> time units
    • deadlock: generate a path until a deadlock is reached
    • repeat=<n>: try <n> paths until a deadlock is found
    • sep=<val>: use <val> as column separator (space, tab, comma)
    • vars=<x1,x2,...>: show values for variables x1,x2,.. only
    • loopcheck=<true|false>: whether to detect deterministic loops
    • snapshot=<x>: view states at fixed timepoints of interval <x>
    • probs=<true|false>: display probability (or rate) of transitions taken
    • rewards=<true|false>: display state/transition rewards
    • changes=<true|false>: only display states where displayed variables change
  • -nobuild: Skip model construction (just do parse/export)

  • -test[:<options>]: Enable "test" mode

    If provided, <options> is a comma-separated list of options taken from:

    • umb: Enable UMB round trip test
    • pexp: Enable explicit (.pexp) round trip test
  • -testall: Enable "test" mode, but don't exit on error

  • -javamaxmem <x>: Set the maximum heap size for Java, e.g. 500m, 4g [default: 1g]

  • -javastack <x>: Set the Java stack size [default: 4m]

  • -javaparams <x>: Pass additional command-line arguments to Java

  • -timeout <n>: Exit after a time-out of <n> seconds if not already terminated

  • -ng: Run PRISM in Nailgun server mode; subsequent calls are then made via "ngprism"

Imports

  • -importpepa: Model description is in PEPA, not the PRISM language

  • -importmodel <files>[:<options>]: Import the model directly from file(s)

    Import the model directly from one or more file(s). Use a list of file extensions to indicate which files should be read, e.g.:

    -importmodel in.tra,sta
    

    Possible extensions are: .tra, .sta, .obs, .lab, .srew, .trew, .pexp, .umb Use extension .all to import all explicit files (.tra/sta/obs/lab/srew/trew), e.g.:

    -importmodel in.all
    

    If provided, <options> is a comma-separated list of options taken from:

    • format (=explicit/umb): model import format
  • -importtrans <file>: Import the transition matrix directly from a text file

  • -importstates <file>: Import the list of states directly from a text file

  • -importobs <file>: Import the list of observations directly from a text file

  • -importlabels <file>: Import the list of labels directly from a text file

  • -importstaterewards <file>: Import the state rewards directly from a text file

  • -importtransrewards <file>: Import the transition rewards directly from a text file

  • -importinitdist <file>: Specify initial probability distribution for transient/steady-state analysis

  • -dtmc: Force imported/built model to be a DTMC

  • -ctmc: Force imported/built model to be a CTMC

  • -mdp: Force imported/built model to be an MDP

  • -importresults <file>: Import results from a data frame stored in CSV file

    Import results from a data frame stored as comma-separated values in <file>.

Exports

  • -exportresults <file[:<options>]>: Export the results of model checking to a file

    Exports the results of model checking to <file> (or to the screen if <file>="stdout"). The default behaviour is to export a list of results in text form, using tabs to separate items. If provided, <options> is a comma-separated list of options taken from:

    • csv: Export results as comma-separated values
    • matrix: Export results as one or more 2D matrices (e.g. for surface plots)
    • dataframe: Export results as dataframe in comma-separated values
    • comment: Export results in comment format for regression testing
  • -exportvector <file>: Export results of model checking for all states to a file

  • -exportmodel <files[:<options>]>: Export the built model to file(s)

    Export the built model to file(s) (or to the screen if <file>="stdout"). Use a list of file extensions to indicate which files should be generated, e.g.:

    -exportmodel out.tra,sta
    -exportmodel out.umb
    

    Possible extensions are: .tra, .srew, .trew, .lab, .sta, .obs, .dot, .umb, .drn Use extension .all to export all explicit files (.tra/srew/trew/lab/sta/obs), e.g.:

    -exportmodel out.all
    

    Omit the file basename to use the basename of the model file, e.g.:

    -exportmodel .all
    

    Use extension .rew to export both .srew/.trew files

    If provided, <options> is a comma-separated list of options taken from:

    • format (=explicit/matlab/dot/drn/umb): model export format
    • rewards (=true/false, or bare for true): whether to include rewards
    • labels (=true/false, or bare for true): whether to include labels
    • states (=true/false, or bare for true): whether to include state definitions
    • obs (=true/false, or bare for true): whether to include observation definitions
    • actions (=true/false, or bare for true): whether to include actions on choices/transitions
    • precision (=<n>): use <n> significant figures for floating point values (in text)
    • zip (=true/false/gzip/xz): whether to zip UMB files
    • text: show binary formats in textual form
    • matlab: same as format=matlab
    • rows: export matrices with one row/distribution on each line
    • proplabels: also export labels from a properties file into the same file, too
    • headers (=true/false, or bare for true): include headers in explicit model files
  • -exporttrans <file>[:<options>]: Export the transition matrix to a file

    If provided, <options> is a comma-separated list of options taken from:

    • precision (=<n>): use <n> significant figures for floating point values (in text)
    • headers (=true/false, or bare for true): include headers in explicit model files
  • -exportstaterewards <file>[:<options>]: Export the state rewards vector to a file

    If provided, <options> is a comma-separated list of options taken from:

    • precision (=<n>): use <n> significant figures for floating point values (in text)
    • headers (=true/false, or bare for true): include headers in explicit model files
  • -exporttransrewards <file>[:<options>]: Export the transition rewards matrix to a file

    If provided, <options> is a comma-separated list of options taken from:

    • precision (=<n>): use <n> significant figures for floating point values (in text)
    • headers (=true/false, or bare for true): include headers in explicit model files
  • -exportrewards <file1[:<options>]> <file2[:<options>]>: Export state/transition rewards to files 1/2

    Export state/transition rewards to files 1/2 (or to the screen if <file>="stdout").

    If provided, <options> is a comma-separated list of options (for either file) taken from:

    • precision (=<n>): use <n> significant figures for floating point values (in text)
    • headers (=true/false, or bare for true): include headers in explicit model files
  • -exportstates <file>[:<options>]: Export the list of reachable states to a file

    If provided, <options> is a comma-separated list of options taken from:

    • precision (=<n>): use <n> significant figures for floating point values (in text)
    • headers (=true/false, or bare for true): include headers in explicit model files
  • -exportobs <file>[:<options>]: Export the list of observations to a file

    If provided, <options> is a comma-separated list of options taken from:

    • precision (=<n>): use <n> significant figures for floating point values (in text)
    • headers (=true/false, or bare for true): include headers in explicit model files
  • -exportlabels <file[:<options>]>: Export the list of labels and satisfying states to a file

    If provided, <options> is a comma-separated list of options taken from:

    • precision (=<n>): use <n> significant figures for floating point values (in text)
    • headers (=true/false, or bare for true): include headers in explicit model files
    • matlab: export data in Matlab format
    • proplabels: export labels from a properties file into the same file, too
  • -exportproplabels <file[:<options>]>: Export the list of labels and satisfying states from the properties file to a file

    If provided, <options> is a comma-separated list of options taken from:

    • precision (=<n>): use <n> significant figures for floating point values (in text)
    • headers (=true/false, or bare for true): include headers in explicit model files
    • matlab: export data in Matlab format
  • -exportstrat <file[:<options>]>: Generate and export a strategy to a file

    Generate and export a strategy to a file (or to the screen if "stdout"). Use file extension .tra, .pexp, .umb or .dot to export as an induced model. The default (e.g. for file extension .txt) is a list of state-action choices.

    If provided, <options> is a comma-separated list of options taken from:

    • type (=actions/indices/induced/dot): type of strategy export
    • mode (=restrict/reduce): mode to use for building induced model (or Dot file)
    • reach (=true/false, or bare for true): whether to restrict the strategy to its reachable states
    • states (=true/false, or bare for true): whether to include full state information
    • mergeobs (=true/false, or bare for true): for partially observable models, whether to merge observationally equivalent states
    • undefined (=stop/loop/first/all/error): how to resolve undefined choices, for all reasons except unknown
    • unknown (=stop/loop/first/all/error): how to resolve undefined choices when there is no information about them
    • arbitrary (=stop/loop/first/all/error): how to resolve undefined choices where any choice is equally good
    • satisfied (=stop/loop/first/all/error): how to resolve undefined choices after the objective is satisfied
    • unsatisfiable (=stop/loop/first/all/error): how to resolve undefined choices when the objective can no longer be satisfied
    • horizon (=stop/loop/first/all/error): how to resolve undefined choices after a step bound
    • unreachable (=stop/loop/first/all/error): how to resolve undefined choices in states not reachable under the strategy
    • showundef (=true/false, or bare for true): whether to also show undefined choices (and why) when exporting actions/indices
    • format (=explicit/dot/drn/umb): model export format for induced model export
    • rewards (=true/false, or bare for true): whether to include rewards for induced model export
    • labels (=true/false, or bare for true): whether to include labels for induced model export
    • actions (=true/false, or bare for true): whether to include actions on choices/transitions for induced model export
    • obs (=true/false, or bare for true): whether to include observation details for induced model export
    • precision (=<n>): use <n> significant figures for floating point values (in text) for induced model export
    • zip (=true/false/gzip/xz): whether to zip files for induced model export
    • text: show binary formats in textual form for induced model export
    • headers (=true/false, or bare for true): include headers in explicit model files for induced model export
  • -exportmatlab: When exporting matrices/vectors/labels/etc., use Matlab format

  • -exportrows: When exporting matrices, put a whole row on one line

  • -exporttransdot <file>: Export the transition matrix graph to a dot file

  • -exporttransdotstates <file>: Export the transition matrix graph to a dot file, with state info

  • -exportdot <file>: Export the transition matrix MTBDD to a dot file

  • -exportsccs <file>: Compute and export all SCCs of the model

  • -exportbsccs <file>: Compute and export all BSCCs of the model

  • -exportmecs <file>: Compute and export all maximal end components (MDPs only)

  • -exportsteadystate <file>: Export steady-state probabilities to a file

  • -exporttransient <file>: Export transient probabilities to a file

  • -exportprism <file>: Export final PRISM model to a file

  • -exportprismconst <file>: Export final PRISM model with expanded constants to a file

Export options

  • -exportmodelprecision <n>: Export probabilities/rewards with n significant decimal places
  • -noexportheaders: Don't include headers when exporting rewards

Engines and methods

  • -mtbdd (or -m): Use the MTBDD engine

  • -sparse (or -s): Use the Sparse engine

  • -hybrid (or -h): Use the Hybrid engine [default]

  • -explicit (or -ex): Use the explicit engine

  • -exact: Perform exact (arbitrary precision) model checking

  • -ptamethod <name>: Specify PTA engine (games, digital, backwards) [default: games]

    Valid options: digital, games, backwards, bw.

  • -transientmethod <name>: CTMC transient analysis method (unif, fau) [default: unif]

    Valid options: unif, fau.

  • -heuristic <mode>: Automatic choice of engines/settings (none, speed, memory) [default: none]

    Valid options: none, speed, memory.

Model construction

  • -fixdl: Automatically put self-loops in deadlock states [default]
  • -nofixdl: Do not automatically put self-loops in deadlock states
  • -noprobchecks: Disable checks on model probabilities/rates
  • -buildall: Build/store all labels and rewards during model construction

Solution methods (linear equations)

  • -power (or -pow, -pwr): Use the Power method for numerical computation
  • -jacobi (or -jac): Use Jacobi for numerical computation [default]
  • -gaussseidel (or -gs): Use Gauss-Seidel for numerical computation
  • -bgaussseidel (or -bgs): Use Backwards Gauss-Seidel for numerical computation
  • -pgaussseidel (or -pgs): Use Pseudo Gauss-Seidel for numerical computation
  • -bpgaussseidel (or -bpgs): Use Backwards Pseudo Gauss-Seidel for numerical computation
  • -jor: Use JOR for numerical computation
  • -sor: Use SOR for numerical computation
  • -bsor: Use Backwards SOR for numerical computation
  • -psor: Use Pseudo SOR for numerical computation
  • -bpsor: Use Backwards Pseudo SOR for numerical computation
  • -omega <x>: Set over-relaxation parameter (for JOR/SOR/...) [default: 0.9]

Solution methods (MDPs)

  • -valiter: Use value iteration for solving MDPs [default]

  • -gaussseidel (or -gs): Use Gauss-Seidel value iteration for solving MDPs

  • -politer: Use policy iteration for solving MDPs

  • -modpoliter: Use modified policy iteration for solving MDPs

  • -intervaliter[:<options>] (or -ii): Use interval iteration to solve MDPs/MCs (see -help -ii)

    Use interval iteration to solve MDPs/MCs.

    If provided, <options> is a comma-separated list of options taken from:

    • boundmethod (=default/variant-1-coarse/variant-1-fine/variant-2/dsmpi): Select upper bound heuristic for reward computations
    • lower (=<d>): Manually specify lower bound for reward computations
    • upper (=<d>): Manually specify upper bound for reward computations
    • [no]boundverbose: Verbose output for upper bound computations (default = no)
    • [no]selectmidpoint: Select midpoint between upper and lower as the result (default = yes)
    • [no]monotonicbelow: Enforce monotonicity in iteration from below (default = yes)
    • [no]monotonicabove: Enforce monotonicity in iteration from above (default = yes)
    • [no]checkmonotonic: Check monotonicity, for testing (default = no)

    Example: boundmethod=default,upper=3.0,noselectmidpoint,checkmonotonic

  • -topological: Use topological value iteration

Solution method settings

  • -relative (or -rel): Use relative error for detecting convergence [default]
  • -absolute (or -abs): Use absolute error for detecting convergence
  • -epsilon <x> (or -e): Set value of epsilon (for convergence check) [default: 1e-6]
  • -maxiters <n>: Set max number of iterations [default: 10000]
  • -gridresolution <n>: Set resolution for fixed grid approximation (POMDP) [default: 10]

Model checking

  • -nopre: Skip precomputation algorithms (where optional)

  • -noprob0: Skip precomputation algorithm Prob0 (where optional)

  • -noprob1: Skip precomputation algorithm Prob1 (where optional)

  • -noprerel: Do not pre-compute/use predecessor relation, e.g. for precomputation

  • -fair: Use fairness (for model checking of MDPs)

  • -nofair: Don't use fairness (for model checking of MDPs) [default]

  • -sumroundoff <x>: Set probability sum threshold [default: 1-e5]

  • -nossdetect: Disable steady-state detection for CTMC transient computations

  • -sccmethod <name>: Specify (symbolic) SCC computation method (xiebeerel, lockstep, sccfind)

    Valid options: xiebeerel, lockstep, sccfind.

  • -symm <string>: Symmetry reduction options string

  • -aroptions <string>: Abstraction-refinement engine options string

    <string> is a comma-separated list of options regarding abstraction-refinement:

    • verbose=<n> (or v=<n>) - verbosity level
    • refine=<where,how>: which states to refine and how
        <where> = all, allmax, first, firstmax, last, lastmax
        <how> = all, val
    
    • epsilonref=<x> (or eref=<x>) - epsilon for refinement
    • nopre - disable precomputation
    • pre: use precomputation
    • noprob0: disable prob0 precomputation
    • noprob1: disable prob1 precomputation
    • epsilon=<x>: epsilon for numerical convergence
    • maxref=<n>: maximum number of refinements
    • opt: use optimisations
    • noopt: disable optimisations
    • exportdot: export dot files for each refinement
    • above: start numerical soluton from above
    • below: start numerical soluton from below
  • -pathviaautomata: Handle all path formulas via automata constructions

  • -nodasimplify: Do not attempt to simplify deterministic automata, acceptance conditions

  • -exportadv <file>: Export an adversary from MDP model checking (as a DTMC)

  • -exportadvmdp <file>: Export an adversary from MDP model checking (as an MDP)

  • -ltl2datool <exec>: Run executable <exec> to convert LTL formulas to deterministic automata

  • -ltl2dasyntax <x>: Specify output format for -ltl2datool switch (lbt, spin, spot, rabinizer)

    Valid options: lbt, spin, spot, rabinizer.

  • -exportiterations: Export vectors for iteration algorithms to file

  • -pmaxquotient: For Pmax computations in MDPs, compute in the MEC quotient

Multi-objective model checking

  • -linprog (or -lp): Use linear programming for MDP solution (explicit engine) and multi-objective model checking
  • -multimaxpoints <n>: Maximal number of corner points for (valiter-based) multi-objective
  • -paretoepsilon <x>: Threshold for Pareto curve approximation
  • -exportpareto <file>: When computing Pareto curves, export points to a file

Output

  • -verbose (or -v): Verbose mode: print out state lists and probability vectors
  • -extraddinfo: Display extra info about some (MT)BDDs
  • -extrareachinfo: Display extra info about progress of reachability

Sparse, hybrid and MTBDD engines

  • -nocompact: Switch off "compact" sparse storage schemes
  • -sbl <n>: Set number of levels (for hybrid engine) [default: -1]
  • -sbmax <n>: Set memory limit (KB) (for hybrid engine) [default: 1024]
  • -gsl <n> (or -sorl): Set number of levels for hybrid GS/SOR [default: -1]
  • -gsmax <n> (or -sormax): Set memory limit (KB) for hybrid GS/SOR [default: 1024]
  • -cuddmaxmem <n>: Set max memory for CUDD package, e.g. 125k, 50m, 4g [default: 1g]
  • -cuddepsilon <x>: Set epsilon value for CUDD package [default: 1e-15]
  • -ddsanity: Enable internal sanity checks (causes slow-down)
  • -ddextrastatevars <n>: Set the number of preallocated state vars [default: 20]
  • -ddextraactionvars <n>: Set the number of preallocated action vars [default: 20]

Parametric model checking

  • -param <vals>: Do parametric model checking with parameters (and ranges) <vals>

  • -paramprecision <x>: Set max undecided region for parameter synthesis [default: 5/100]

  • -paramsplit <name>: Set method to split parameter regions (longest,all) [default: longest]

    Valid options: longest, all.

  • -parambisim <name>: Set bisimulation minimisation for parameter synthesis (weak,strong,none) [default: weak]

    Valid options: strong, weak, none.

  • -paramfunction <name>: Set function representation for parameter synthesis (jascached,jas) [default: jascached]

    Valid options: jascached, jas, dag.

  • -paramelimorder <name>: Set elimination order for parameter synthesis (arb,fw,fwrev,bw,bwrev,rand) [default: bw]

    Valid options: arb, fw, fwrev, bw, bwrev, rand.

  • -paramrandompoints <n>: Set number of random points to evaluate per region [default: 5]

  • -paramsubsumeregions <b>: Subsume adjacent regions during analysis [default: true]

  • -paramdagmaxerror <b>: Maximal error probability allowed for DAG function representation [default: 1E-100]

Fast adaptive uniformisation (FAU)

  • -fauepsilon <x>: Set probability threshold of birth process in FAU [default: 1e-6]
  • -faudelta <x>: Set probability threshold for irrelevant states in FAU [default: 1e-12]
  • -fauarraythreshold <x>: Set threshold when to switch to sparse matrix in FAU [default: 100]
  • -fauintervals <x>: Set number of intervals to divide time intervals into for FAU [default: 1]
  • -fauinitival <x>: Set length of additional initial time interval for FAU [default: 1.0]

Simulation

  • -sim: Use the PRISM simulator to approximate results of model checking

  • -simmethod <name>: Specify the method for approximate model checking (ci, aci, apmc, sprt)

    Valid options: ci, aci, apmc, sprt.

  • -simsamples <n>: Set the number of samples for the simulator (CI/ACI/APMC methods)

  • -simconf <x>: Set the confidence parameter for the simulator (CI/ACI/APMC methods)

  • -simwidth <x>: Set the interval width for the simulator (CI/ACI methods)

  • -simapprox <x>: Set the approximation parameter for the simulator (APMC method)

  • -simmanual: Do not use the automated way of deciding whether the variance is null or not

  • -simvar <n>: Set the minimum number of samples to know the variance is null or not

  • -simmaxrwd <x>: Set the maximum reward -- useful to display the CI/ACI methods progress

  • -simpathlen <n>: Set the maximum path length for the simulator

Explicit model files

This page details the plain text file formats used by PRISM for exporting and importing models that have already been constructed, i.e., they comprise an explicit list of states, transitions, etc. making up the model, rather than a high-level model description in the PRISM modelling language. Below, we describe:

The examples are exported from four small PRISM models, which are shown, with diagrams, in the last section, Source PRISM files.

PRISM explicit (.pexp) files

The default for exporting models in textual format from PRISM is to do so in a combined .pexp file, that includes all parts of the model, as described individually in more detail below.

Here is an example, for the (DTMC) PRISM model dtmc.prism:

# Transitions (DTMC)
6 9
0 1 0.5
0 3 0.5
1 0 0.5
1 2 0.25
1 4 0.25
2 5 1
3 3 1
4 4 1
5 2 1

# States
(s)
0:(0)
1:(1)
2:(2)
3:(3)
4:(4)
5:(5)

# Labels
0="init" 1="deadlock"
0: 0

# Reward structure "r"
# State rewards
6 3
0 2
4 1
5 1

# Reward structure "r"
# Transition rewards
6 4
1 0 1
1 2 1
1 4 1
2 5 2

See below for the format of the constituent parts.

Transitions (.tra) files

These contain an explicit list of the transitions making up a probabilistic model, i.e. they are essentially a sparse matrix representation of the transition probability/rate matrix. After an (optional) header line containing the word Transitions and the model type, the first line of the file contains information about the size of the model, then the remaining lines contain information about transitions, one per line.

DTMCs and CTMCs

For Markov chains the initial line takes the form "n m", giving the number of states (n) and the number of transitions (m). The remaining lines are of the form "i j x" or "i j x a", where i and j are the indices of the source state (row) and destination state (column) of the transition, and x is the probability (for a DTMC) or rate (for a CTMC) of the transition. State indices are zero-indexed (i.e. between 0 and n-1). Probability/rate values are written as (positive) floating point numbers (examples: 0.5, .5, 5.6e-6, 1). a is optional and gives the action label for the transition. Action labels can be present for some, all or no transitions.

It is assumed that source states (rows) are in ascending order, but there is no assumption about the ordering of destination states (columns) within the transitions for each source state.

For a DTMC, the probabilities for the outgoing transitions of each state should sum to 1.

Here is an example, for the (DTMC) PRISM model dtmc.prism:

# Transitions (DTMC)
6 9
0 1 0.5
0 3 0.5
1 0 0.5
1 2 0.25
1 4 0.25
2 5 1
3 3 1
4 4 1
5 2 1

and here is one for the (CTMC) PRISM model poll2.prism:

# Transitions (CTMC)
12 22
0 1 0.5
0 2 0.5
0 6 200 loop1a
1 3 0.5
1 7 200 loop1a
2 3 0.5
2 4 200 loop1b
3 5 200 loop1b
4 5 0.5
4 6 1 serve1
5 7 1 serve1
6 7 0.5
6 8 0.5
6 0 200 loop2a
7 9 0.5
7 10 200 loop2b
8 9 0.5
8 2 200 loop2a
9 11 200 loop2b
10 11 0.5
10 0 1 serve2
11 2 1 serve2

MDPs (or PAs)

For MDPs, the format is an extension of the above To clarify terminology: each state of the MDP contains (nondeterministic) choices, each of which is essentially a probability distribution over successor states that we can view as a set of transitions. Optionally, each choice can be labelled with an action.

The first (non-header) line of the file take the form "n c m", giving the number of states (n), the total number of choices (c) and the total number of transitions (m). The remaining lines are of the form "i k j x" or "i k j x a", where i and j are the indices of the source state (row) and destination state (column) of the transition, k is the index of the choice that it belongs to, and x is the probability of the transition. a is optional and gives the action label for the choice of the transition. Action labels can be present for some, all or no states but, in slightly redundant fashion, the action labels, if present, must be the same for all transitions belonging to the same choice.

State indices and choice indices are all zero-indexed. Probability values (as above) are written as (positive) floating point numbers and should sum to 1 for each choice. It is assumed that source states (rows) and choices within states are in ascending order, but there is no assumption about the ordering of destination states (columns) within the transitions for each choice.

Here is an example, for the (MDP) PRISM model mdp.prism, exported without its actions (-exportmodel mdp.tra:actions=false):

# Transitions (MDP)
4 5 7
0 0 1 1
1 0 2 0.5
1 0 3 0.5
1 1 0 0.7
1 1 1 0.3
2 0 2 1
3 0 3 1

and here is the same model exported with its actions:

# Transitions (MDP)
4 5 7
0 0 1 1 a
1 0 2 0.5 c
1 0 3 0.5 c
1 1 0 0.7 b
1 1 1 0.3 b
2 0 2 1 a
3 0 3 1 a

LTSs

For LTSs (labelled transition systems), the format is the same as for MDPs, except that there are no probabilities, so each choice comprises a single transition. The remaining lines are of the form "i k j" or "i k j a". Here is the start of the file for the LTS in Non-probabilistic models:

# Transitions (LTS)
8 14 14
0 0 3 try1
0 1 1 try2
1 0 4 try1
1 1 2 enter2
...

POMDPs

The format of a .tra file for a POMDP is similar to an MDP, but also contains information about observations.

The initial line of the file takes the form "n c m o", where n, c and m are, as for MDPs, the numbers of states, choices and transitions, and o is the number of observations. The lines that list transitions contain an additional integer after the transition probability (and before the action, if present), giving the (deterministic) observation that is made when entering the target state of that transition. It is assumed that these are consistent for all states.

In order to also specify the observation for the initial state, a dummy transition line of the form - - s - o is used, giving both the initial state s and its observation o.

An example file is:

# Transitions (POMDP)
10 16 18 4
- - 0 - 0
0 0 1 0.1 1 toss
0 0 2 0.3 1 toss
0 0 3 0.6 1 toss
1 0 4 1 2 guess1
1 1 7 1 3 guess2
1 2 7 1 3 guess3
2 0 8 1 3 guess1
2 1 5 1 2 guess2
2 2 8 1 3 guess3
3 0 9 1 3 guess1
3 1 9 1 3 guess2
3 2 6 1 2 guess3
4 0 4 1 2 loop
5 0 5 1 2 loop
6 0 6 1 2 loop
7 0 7 1 3
8 0 8 1 3
9 0 9 1 3

Transitions (.tra) files (row form)

There is an alternative format for transition matrices (see the rows option for -exportmodel) where transitions for each state/choice are collated on a single line.

Here is the result for the dtmc.prism example from above (a DTMC):

# Transitions (DTMC)
6 9
0 0.5:1 0.5:3
1 0.5:0 0.25:2 0.25:4
2 1:5
3 1:3
4 1:4
5 1:2

for the mdp.prism example (an MDP), without its actions:

# Transitions (MDP)
4 5 7
0 1:1
1 0.5:2 0.5:3
1 0.7:0 0.3:1
2 1:2
3 1:3

and with them:

# Transitions (MDP)
4 5 7
0 1:1 a
1 0.5:2 0.5:3 c
1 0.7:0 0.3:1 b
2 1:2 a
3 1:3 a

Labels (.lab) files

These contain an explicit list of which labels are satisfied in each state. After a header, showing Labels, the first line lists the labels, assigning each one an index. The remaining lines list indices of all states satisfying one or more labels, followed by a list of the indices of labels that are satisfied in it. This includes the built-in labels "init" (initial states) and deadlock (deadlock states). An example is shown below, for mdp.prism, where, for example, both "heads" and "end" are satisfied in state 2.

# Labels
0="init" 1="deadlock" 2="heads" 3="tails" 4="end"
0: 0
2: 2 4
3: 3 4

State rewards (.srew) files

For reward files, the header, gives the name of the reward structure that generated it and the type of rewards (state or transitions) stored in the file. For state rewards, the information following this header is an explicit list of the (non-zero) state rewards. The first line is of the form n m where n is the number of states in the model and m is the number of non-zero state rewards. The following m lines are of the form i r, denoting that the state reward for state i is r.

For the dtmc.prism (6-state) DTMC example from above, we get rewards in 3 states (0, 4 and 5):

# Reward structure "r"
# State rewards
6 3
0 2
4 1
5 1

Transition rewards (.trew) files

Files containing transition rewards, like those for state rewards, start with a header. The rest of the file is formatted identically to transitions files (see above), except that probabilities/rates are replaced with reward values, and the number of transitions (the last number on the first line) is replaced with the number of non-zero transition rewards.

For the dtmc.prism (6-state) DTMC example from above, we get non-zero transition rewards on 4 transitions:

# Reward structure "r"
# Transition rewards
6 4
1 0 1
1 2 1
1 4 1
2 5 2

And for the mdp.prism (4-state) MDP example, we get non-zero transition rewards on 4 transitions:

# Reward structure "r"
# Transition rewards
4 5 4
1 0 2 6
1 0 3 6
1 1 0 5
1 1 1 5

States (.sta) files

These contain an explicit list of the reachable states of a model. The first (non-header) line is of the form (v1,...,vn), listing the names of all the variables in the model in the order that they appear in the PRISM model. Subsequent lines list the values of the n variables in each state of the model. Each line is of the form i:(x1,...,xn), where i is the index of the state (starting from 0) and x1,...,xn are the values of each variable in the state. States are ordered by their index (and, therefore, given PRISM's default behaviour, lexicographically according to the tuple of variable values).

For the example PRISM model poll2.prism, the states file looks like:

# States
(s,a,s1,s2)
0:(1,0,0,0)
1:(1,0,0,1)
2:(1,0,1,0)
3:(1,0,1,1)
4:(1,1,1,0)
5:(1,1,1,1)
6:(2,0,0,0)
7:(2,0,0,1)
8:(2,0,1,0)
9:(2,0,1,1)
10:(2,1,0,1)
11:(2,1,1,1)

Source PRISM files

The examples above were exported by PRISM from the following models. Each is shown with a diagram of the resulting model, in which states are labelled with their indices, as used in the files above.

dtmc.prism

A DTMC with 6 states and a reward structure "r":

dtmc

module M

s:[0..5];

[] s=0 -> 0.5:(s'=1) + 0.5:(s'=3);
[] s=1 -> 0.5:(s'=0) + 0.25:(s'=2) + 0.25:(s'=4);
[] s=2 -> 1:(s'=5);
[] s=3 -> 1:(s'=3);
[] s=4 -> 1:(s'=4);
[] s=5 -> 1:(s'=2);

endmodule

rewards "r"
	s=0 : 2;
	s>=4 : 1;
	[] s<3 : s;
endrewards
Download: dtmc.prism

The DTMC for dtmc.prism, with states 0 to 5: from 0, to 1 or 3 with probability 0.5 each; from 1, to 0 with probability 0.5 and to 2 or 4 with 0.25 each; 2 goes to 5 and 5 back to 2; 3 and 4 loop.

mdp.prism

An MDP with 4 states and 5 choices, labelled with actions, with labels "heads", "tails" and "end", and a reward structure "r" on actions b and c:

mdp

module M

s:[0..3];

[a] s=0 -> 1:(s'=1);
[b] s=1 -> 0.7:(s'=0) + 0.3:(s'=1);
[c] s=1 -> 0.5:(s'=2) + 0.5:(s'=3);
[a] s=2 -> 1:(s'=2);
[a] s=3 -> 1:(s'=3);

endmodule

label "heads" = s=2;
label "tails" = s=3;
label "end" = s=2|s=3;

rewards "r"
	[b] true : 5;
	[c] true : 6;
endrewards
Download: mdp.prism

The MDP for mdp.prism: state 0 has one choice, labelled a, to 1; state 1 has two choices, b back to 0 (probability 0.7) or staying in 1 (0.3), and c to 2 or 3 (0.5 each); states 2 and 3 loop, with action a.

poll2.prism

A CTMC with 12 states: a polling system with two stations (the same as poll2.sm in the prism-examples directory). The values of its variables in each state are listed in the states file above: states 0 to 5 have the server at station 1 (s=1), on the left, and states 6 to 11 at station 2, on the right.

// polling example [IT90]
// gxn/dxp 26/01/00

ctmc

const int N = 2;

const double mu		= 1;
const double gamma	= 200;
const double lambda	= mu/N;

module server
	
	s : [1..2]; // station
	a : [0..1]; // action: 0=polling, 1=serving
	
	[loop1a] (s=1)&(a=0) -> gamma	: (s'=s+1);
	[loop1b] (s=1)&(a=0) -> gamma	: (a'=1);
	[serve1] (s=1)&(a=1) -> mu		: (s'=s+1)&(a'=0);
	
	[loop2a] (s=2)&(a=0) -> gamma	: (s'=1);
	[loop2b] (s=2)&(a=0) -> gamma	: (a'=1);
	[serve2] (s=2)&(a=1) -> mu		: (s'=1)&(a'=0);
	
endmodule

module station1
	
	s1 : [0..1]; // state of station: 0=empty, 1=full
	
	[loop1a] (s1=0) -> 1 : (s1'=0);
	[]       (s1=0) -> lambda : (s1'=1);
	[loop1b] (s1=1) -> 1 : (s1'=1);
	[serve1] (s1=1) -> 1 : (s1'=0);
	
endmodule

// construct further stations through renaming

module station2 = station1 [ s1=s2, loop1a=loop2a, loop1b=loop2b, serve1=serve2 ] endmodule
// (cumulative) rewards

// expected time station 1 is waiting to be served
rewards "waiting"
	s1=1 & !(s=1 & a=1) : 1;
endrewards

// expected number of times station 1 is served
rewards "served"
	[serve1] true : 1;
endrewards
Download: poll2.prism

The CTMC for poll2.prism, with 12 states and 22 transitions: arrivals at the stations have rate 0.5, the server moves on or starts serving at rate 200, and serving takes rate 1.

References

  • [AD94] R. Alur and D. Dill. A theory of timed automata. Theoretical Computer Science, 126:183-235, 1994.
  • [AH99] R. Alur and T. Henzinger. Reactive Modules. Formal Methods in System Design, 15(1):7-48, 1999.
  • [ASSB96] A. Aziz, K. Sanwal, V. Singhal and R. Brayton. Verifying Continuous Time Markov Chains. In R. Alur and T. Henzinger, editors, Proc. 8th International Conference on Computer Aided Verification (CAV'96), volume 1102 of LNCS, pages 269-276, Springer, 1996.
  • [Bai98] C. Baier. On Algorithmic Verification Methods for Probabilistic Systems. Habilitation thesis, Fakultät für Mathematik & Informatik, Universität Mannheim, 1998.
  • [BdA95] A. Bianco and L. de Alfaro. Model Checking of Probabilistic and Nondeterministic Systems. In P. Thiagarajan, editor, Proc. 15th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'95), volume 1026 of LNCS, pages 499-513, Springer, 1995.
  • [BK98] C. Baier and M. Kwiatkowska. Model Checking for a Probabilistic Branching Time Logic with Fairness. Distributed Computing, 11(3):125-155, 1998.
  • [BKH99] C. Baier, J.-P. Katoen and H. Hermanns. Approximate Symbolic Model Checking of Continuous-Time Markov Chains. In J. Baeten and S. Mauw, editors, Proc. 10th International Conference on Concurrency Theory (CONCUR'99), volume 1664 of LNCS, pages 146-161, Springer, 1999.
  • [BKLPW17] Christel Baier, Joachim Klein, Linda Leuschner, David Parker and Sascha Wunderlich. Ensuring the Reliability of Your Model Checker: Interval Iteration for Markov Decision Processes. In Proc. 28th International Conference on Computer Aided Verification (CAV'17), volume 10426 of LNCS, pages 160-180, Springer, July 2017.
  • [CHH+13] Taolue Chen, Ernst Moritz Hahn, Tingting Han, Marta Kwiatkowska, Hongyang Qu and Lijun Zhang. Model Repair for Markov Decision Processes. In Proc. 7th International Symposium on Theoretical Aspects of Software Engineering (TASE'13), pages 85-92, IEEE, July 2013.
  • [DHK13] Frits Dannenberg, Ernst Moritz Hahn and Marta Kwiatkowska. Computing Cumulative Rewards using Fast Adaptive Uniformisation. In A. Gupta and T. Henzinger, editors, Proc. 11th International Conference on Computational Methods in Systems Biology (CMSB'13), volume 8130 of LNCS, pages 33-49, Springer, September 2013.
  • [FKN+11] Vojtěch Forejt, Marta Kwiatkowska, Gethin Norman, David Parker and Hongyang Qu. Quantitative Multi-Objective Verification for Probabilistic Systems. In P. Abdulla and K. Leino, editors, Proc. 17th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS'11), volume 6605 of LNCS, pages 112-127, Springer, March 2011.
  • [FKNP11] Vojtěch Forejt, Marta Kwiatkowska, Gethin Norman and David Parker. Automated Verification Techniques for Probabilistic Systems. In M. Bernardo and V. Issarny, editors, Formal Methods for Eternal Networked Software Systems (SFM'11), volume 6659 of LNCS, pages 53-113, Springer, June 2011.
  • [FKP12] Vojtěch Forejt, Marta Kwiatkowska and David Parker. Pareto Curves for Probabilistic Model Checking. In S. Chakraborty and M. Mukund, editors, Proc. 10th International Symposium on Automated Technology for Verification and Analysis (ATVA'12), volume 7561 of LNCS, pages 317-332, Springer, October 2012.
  • [HHZ11] Ernst Moritz Hahn, Tingting Han and Lijun Zhang. Synthesis for PCTL in Parametric Markov Decision Processes. In Proc. 3rd NASA Formal Methods Symposium (NFM'11), volume 6617 of LNCS, Springer, April 2011.
  • [HHZ11b] E. M. Hahn, H. Hermanns, and L. Zhang. Probabilistic reachability for parametric Markov models. Software Tools for Technology Transfer, 13(1):3-19, 2011.
  • [Hil96] J. Hillston. A Compositional Approach to Performance Modelling. Cambridge University Press, 1996.
  • [HJ94] H. Hansson and B. Jonsson. A Logic for Reasoning about Time and Reliability. Formal Aspects of Computing, 6(5):512-535, 1994.
  • [HKN+03] Holger Hermanns, Marta Kwiatkowska, Gethin Norman, David Parker and Markus Siegle. On the use of MTBDDs for Performability Analysis and Verification of Stochastic Systems. Journal of Logic and Algebraic Programming: Special Issue on Probabilistic Techniques for the Design and Analysis of Systems, 56:23-67, June 2003.
  • [HLMP04] T. Hérault, R. Lassaigne, F. Magniette and S. Peyronnet. Approximate Probabilistic Model Checking. In Proc. 5th International Conference on Verification, Model Checking and Abstract Interpretation (VMCAI'04), volume 2937 of LNCS, pages 307-329, Springer, January 2004.
  • [HM14] S. Haddad and B. Monmege. Reachability in MDPs: Refining convergence of value iteration. In 8th International Workshop on Reachability Problems (RP), volume 8762 of LNCS, pages 125-137, Springer, 2014.
  • [KNP04b] Marta Kwiatkowska, Gethin Norman and David Parker. Probabilistic Symbolic Model Checking with PRISM: A Hybrid Approach. International Journal on Software Tools for Technology Transfer (STTT), 6(2):128-142, September 2004.
  • [KNP07a] Marta Kwiatkowska, Gethin Norman and David Parker. Stochastic Model Checking. In M. Bernardo and J. Hillston, editors, Formal Methods for the Design of Computer, Communication and Software Systems: Performance Evaluation (SFM'07), volume 4486 of LNCS (Tutorial Volume), pages 220-270, Springer, June 2007.
  • [KNP09c] Marta Kwiatkowska, Gethin Norman and David Parker. Stochastic Games for Verification of Probabilistic Timed Automata. In J. Ouaknine and F. Vaandrager, editors, Proc. 7th International Conference on Formal Modeling and Analysis of Timed Systems (FORMATS'09), volume 5813 of LNCS, pages 212-227, Springer, September 2009.
  • [KNPS06] Marta Kwiatkowska, Gethin Norman, David Parker and Jeremy Sproston. Performance Analysis of Probabilistic Timed Automata using Digital Clocks. Formal Methods in System Design, 29:33-78, August 2006.
  • [KNSW07] M. Kwiatkowska, G. Norman, J. Sproston and F. Wang. Symbolic Model Checking for Probabilistic Timed Automata. Information and Computation, 205(7):1027-1077, July 2007.
  • [Lov91] W. S. Lovejoy. Computationally Feasible Bounds for Partially Observed Markov Decision Processes. Operations Research, 39(1):162-175, 1991.
  • [MWDH10] M. Mateescu, V. Wolf, F. Didier and T. Henzinger. Fast adaptive uniformisation of the chemical master equation. IET Syst Biol, 4(6):441-452, 2010.
  • [Nim10] Vincent Nimal. Statistical Approaches for Probabilistic Model Checking. MSc Mini-project Dissertation, Oxford University Computing Laboratory, September 2010.
  • [NPS13] Gethin Norman, David Parker and Jeremy Sproston. Model Checking for Probabilistic Timed Automata. Formal Methods in System Design, 43(2):164-190, September 2013.
  • [NPZ17] Gethin Norman, David Parker and Xueyi Zou. Verification and Control of Partially Observable Probabilistic Systems. Real-Time Systems, 53(3):354-402, April 2017.
  • [Par02] David Parker. Implementation of Symbolic Model Checking for Probabilistic Systems. Ph.D. thesis, University of Birmingham, 2002.
  • [Put94] M. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley and Sons, 1994.
  • [Seg95] R. Segala. Modelling and Verification of Randomized Distributed Real Time Systems. Ph.D. thesis, Massachusetts Institute of Technology, 1995.
  • [Ste94] W. J. Stewart. Introduction to the Numerical Solution of Markov Chains. Princeton, 1994.
  • [Str00] M. Strens. A Bayesian Framework for Reinforcement Learning. In Proc. 17th International Conference on Machine Learning (ICML'00), pages 943-950, Morgan Kaufmann, 2000.
  • [YS02] H. Younes and R. Simmons. Probabilistic Verification of Discrete Event Systems Using Acceptance Sampling. In E. Brinksma and K. Larsen, editors, Proc. 14th International Conference on Computer Aided Verification (CAV'02), volume 2404 of LNCS, pages 223-235, Springer, 2002.

Frequently asked questions

Answers to frequently asked questions about modelling, properties and memory. For problems installing or running PRISM, see "Troubleshooting".

Contents

  • Memory problems: crashes, and running out of memory during model construction, model checking or parsing
  • PRISM modelling: model size, variable ordering, and modelling deterministic delays
  • PRISM properties: infinite expected rewards, results for several states, and the probability of actions

Memory problems

Click on a question to see its answer.

PRISM crashed or stopped responding. Why?

When PRISM crashes, the most likely cause is that it has run out of memory. Similarly, if PRISM (or the machine you are running it on) becomes very slow or seems to have stopped responding, this is probably because it is using too much of your machine's memory. Probabilistic model checking, much like other formal verification techniques, can be a very resource-intensive process. It is very easy to create a seemingly simple PRISM model that requires a large amount of time and/or memory to construct and analyse. See the other questions on this page for tips on how to avoid this.

The other possibility is that you have found a bug. If PRISM crashes or freezes whilst not using all/most of the available memory (you can check this with the top command in a Unix/Linux terminal or the Task Manager (via Ctrl-Alt-Delete) on Windows) then please file a bug report.

I ran out of memory. What can I do?

First, note that PRISM's different computation engines and solution methods can vary significantly in performance.

It also helps to establish at what point in PRISM's operation, you ran out of memory. If you are running the command-line version of PRISM then the output from the tool so far should give an indication of this. If using the GUI, check the log tab for this information. If PRISM crashed because of its memory usage, the error message can be helpful. If using the GUI, you may need to start the GUI from the command-line to see any error messages.

The two main steps that PRISM typically has to perform are:

  1. Model construction (conversion of a PRISM language description to the corresponding probabilistic model)
  2. Model checking/analysis (processing/analysis of a constructed probabilistic model in order to determine the result of a property or to compute steady-state/transient probabilities)

Memory usage issues for each of these steps are discussed in the questions on model construction and model checking below. In some cases the process performed prior to step 1 (model parsing - reading in a model description in the PRISM language and checking it for correctness) can also be resource intensive. This is discussed under model parsing.

If you are using the simulator to generate approximate model checking results then step 1 (model construction) is not performed and step 2 is carried out very differently. Memory consumption is not usually a problem in this case.

I ran out of memory during model construction. What can I do?

If PRISM has already output this:

Building model (engine:symbolic)...

but there is no line of the form:

Time for model construction: 34.3 seconds.

and then you get an error like this:

CUDD internal error detected, from the following stack trace:
  ...
Error: Out of memory (or other internal error) in the CUDD library.
Tip: Try using the -cuddmaxmem switch to increase the memory available to CUDD.

then PRISM ran out of memory whilst trying to construct the model. With the symbolic engines (MTBDD, hybrid and sparse), model construction is performed using BDDs (binary decision diagrams) and MTBDDs (multi-terminal BDDs), which are implemented in the CUDD library. The first thing to try in this case is to increase the amount of memory available to CUDD. See "CUDD memory" for details of this.

If increasing this memory limit does not resolve the problem, then you will need to consider ways to reduce the size of your model. You can find some tips on this in the PRISM modelling section. Bear in mind also that if you are having to increase the CUDD memory limit too high (e.g. close to the physical memory available on your computer) just for model construction, then it is unlikely that you will have enough memory for subsequent model checking operations.

It is also worth considering the ordering of the modules and variables in your model since this can have a (in some cases dramatic) effect on the size of MTBDD representation of the model. This topic is covered in the "PRISM modelling" section.

With the explicit engine, the model is built in Java, and running out of memory gives an error like this:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

In this case, increase the memory available to Java instead (see "Java memory").

I ran out of memory during model checking. What can I do?

If model construction was successfully completed (see the previous question) but model checking was not, there are several things you can try. First of all, if the error message you see is the CUDD one in the previous question, then it may be worth increasing the memory limit for CUDD (as described there). If it is a Java OutOfMemoryError, increase the memory available to Java. However, if PRISM is killed or aborts with no such message, then increasing these limits probably will not help: PRISM is just trying to allocate more memory than is physically available on your system.

Here are some general tips:

  • Try experimenting with using the different engines in PRISM. Read the section "Computation engines" for details.

  • Look at the detailed output of PRISM for information about memory usage. If you are using the hybrid (or sparse) engine and the limiting factor in terms of memory is creation of the vectors, then you have no choice but to try and reduce the size (number of states) of your model. If you are using the MTBDD engine, it is also well worth considering the variable ordering of your model. Both topics are discussed in the "PRISM modelling" section.

  • Finally, if you can find no way to reduce the size of your model and are happy to consider an approximate (rather than exact) analysis, you may wish to try using PRISM's discrete-event simulation engine for analysis.

I ran out of memory during model parsing. What can I do?

This is a less common problem and will only occur if the actual PRISM language description of your model is very large. This may be the case, for example, if you are automatically generating PRISM models in some way. Errors due to lack of memory during parsing usually look like:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

or:

Exception in thread "main" java.lang.StackOverflowError

You can resolve this problem by increasing the memory (for OutOfMemoryError) or the stack size (for StackOverflowError) allocated to Java. See "Java memory" for details of both.

PRISM modelling

Click on a question to see its answer.

What size models can PRISM handle?

There is no definitive answer to this. Because of PRISM's symbolic implementation, using data structures based on binary decision diagrams (BDDs), its performance can be unpredictable in this respect. There are also several factors that affect performance, including the type of model and property being checked and the engine being used (PRISM has several different engines, which have varying performance).

Having said that, using the default engine in PRISM (the "hybrid" engine), you can normally expect to be able to handle models with up to 10710^7–10810^8 states on a typical PC. Using the MTBDD engine, you may be able to analyse much larger models (on some of the PRISM case studies, for example, PRISM can do numerical analysis of models with as many as 101010^{10} or 101110^{11} states). The manual has more information about PRISM's engines.

How can I reduce the size of my model?

The size of a probabilistic model (i.e. the number of states/transitions) is critical to the efficiency of performing probabilistic model checking on it, since both the time and memory required to do so are often proportional to the model size. Unfortunately, it is very easy to create models that are extremely large. Below are a few general tips for reducing model size.

  • Look for variables that have unnecessarily large ranges and try to reduce them. Even if your model needs large variables, it is generally a good strategy to first get a smaller version building successfully and then scale it up afterwards.

  • Similarly, can you (if only temporarily) reduce the number of modules/components of your model? Start with the smallest number of components possible and then add others one by one.

  • Do you have any inter-dependencies between variables? For example, perhaps you have some variables which are simply functions of other variables of the model. Even if these are convenient for modelling, they can be replaced with formulas or labels, which do not contribute to the state space.

  • Do any variables include more detail than is necessary for the model? Perhaps this can be exploited in order to reduce the number of variables in your model.

  • More generally, are any aspects of the model not relevant to the properties that you are interested in? If so, start with a simpler, more abstract version of the model and then add more details if possible.

How can I choose a good variable ordering?

Because PRISM is a symbolic model checker, the amount of memory required to store the probabilistic model can vary (sometimes unpredictably) according to several factors. One example is the order in which the variables of your model appear in the model file. In general, there is no definitive answer to what the best ordering is but the following heuristics are a good guide.

  • Variables which are closely related should appear close together
  • Variables which are related to most or all other variables should appear near the start of the ordering

Variables x and y are "related" if, for example, the value of one has an effect on how the other changes (e.g. (y'=x+1)) or if both appear together in an expression (e.g. a guard).

These heuristics also apply to the ordering of modules within the model file.

For technical details about variable ordering issues, see e.g. section 8 of [HKN+03] or section 4.1.2 of [Par02].

How can I add deterministic time delays to a CTMC model?

All delays in a CTMC need to be modelled as exponential distributions. This is what makes them efficient to analyse. If you included a transition whose delay was deterministic, i.e. which always occurred after exactly the same delay, the model would no longer be a CTMC.

One solution to this, if your model requires such a delay, is to approximate a deterministic delay with an Erlang distribution (a special case of a phase-type distribution). See for example this PRISM model:

ctmc

const int k;
const double mean = 10;

module trigger

	i : [1..k+1];

	[]   i < k -> k/mean : (i'=i+1);
	[go] i = k -> k/mean : (i'=i+1);

endmodule

module main

	x : [0..1];

	[go] x=0 -> (x'=1);

endmodule

In the model, the go-labelled action occurs after a delay with an Erlang distribution with mean mean and shape k. The special case of k=1 is just an exponential distribution. The graph below shows the probability distribution of the delay, i.e. of P=? [ F<=T x=1 ] for different values of k.

Plot of probability against time T from 0 to 50, one curve per shape k (1 to 10, and 1000). The k=1 curve rises gradually like an exponential distribution; as k increases the curves become steeper around T=10, and for k=1000 the probability jumps from 0 to 1 almost exactly at T=10.

There is an obvious trade-off here between the accuracy (how close it is to modelling a deterministic time delay) and the resulting blow-up in the size of the model that you add this to. For k=1000, you can see that the shape is quite "deterministic" but this would increase your model size by a factor of ~1000.

PRISM properties

Click on a question to see its answer.

Why is my expected reward infinite?

This most commonly occurs when you are computing the expected reward that is accumulated up until some target set of states is reached ("reachability reward" properties). For example:

R=? [ F "end" ]

As mentioned earlier, this kind of property returns infinity if "end" is not eventually reached with probability 1. This is a choice that we made when designing the property specification language. Often, it is reasonable to assume that, if a path continues indefinitely without reaching a goal state, then reward will continue to be accumulated infinitely often (this would usually be true when modelling time as a reward structure, for instance). If there is a non-zero probability of not reaching the target (i.e. the probability of reaching it is less than 1), we would then expect the overall expected reward to be infinite.

You can check whether the probability of reaching the target is 1 with a property like:

P=? [ F "end" ]

A similar situation arises with models that contain nondeterminism, such as MDPs. The maximum expected reward to reach a target is finite if and only if the minimum probability of reaching the target is 1. Conversely, the minimum expected reward is finite if and only if the maximum probability is 1.

How do I check if a property is true in multiple (or all) states?

Consider a typical Boolean-valued PRISM property, such as:

P<0.01 [ F "error" ]

i.e. "the probability of reaching a state labelled with "error" is less than 0.01". By default, when model checking this query, PRISM will report the result of this property for the initial state of the model, i.e. whether, starting from the initial state, the probability of reaching "error" is below 0.01.

To check whether the above property is true for, say, all (reachable) states satisfying the label "safe", you should use filters, as illustrated below:

filter(forall, P<0.01 [ F "error" ], "safe")

If you want to check whether the property is true for all reachable states, you can use either of the following two (equivalent) properties:

filter(forall, P<0.01 [ F "error" ], true)
filter(forall, P<0.01 [ F "error" ])

Equivalently, you can use implication (=>) inside the filter, as in this example:

filter(forall, "safe" => P<0.01 [ F "error" ])
How do I compute the probability of an action occurring?

PRISM's property specification language is primarily state-based, e.g. you can compute the probability of reaching a state that satisfies the label "error":

P=? [ F "error" ]

So how do you compute the probability of some action b occurring? You need to make a small change to your model. The cleanest way to do this is to add a small module that changes state when the action occurs, e.g.:

module checker

    q : [0..1] init 0;

    [b] q=0 -> (q'=1);
    [b] q=1 -> (q'=1);

endmodule

You can determine the probability of action b occurring in the model with the property:

P=? [ F q=1 ]

By design, the module above will not affect the behaviour (timing, probability, etc.) of your model at all, so all other properties will remain unchanged. This is true for any of the model types that PRISM supports. It may, though, lead to a (hopefully small) increase in total model size.

You can also modify the property above to compute, for example, the probability of b occurring within T time-units or the expected time until b occurs:

P=? [ F<=T q=1 ]
R{"time"}=? [ F q=1 ]

(where a constant T or reward structure time have been added to the model, as appropriate).