APEX: An analyzer for open probabilistic programs

Stefan Kiefer, Andrzej S. Murawski, Joël Ouaknine, Bjorn Wachter, and James Worrell

We present APEX, a tool for analysing probabilistic programs that are open, i.e. where variables or even functions can be left unspecified. APEX transforms a program into an automaton that captures the program's probabilistic behaviour under all instantiations of the unspecified components. The translation is compositional and effectively leverages state reduction techniques. APEX can then further analyse the produced automata; in particular, it can check two automata for equivalence which translates to equivalence of the corresponding programs under all environments. In this way, APEX can verify a broad range of anonymity and termination properties of randomised protocols and other open programs, sometimes with an exponential speed-up over competing state-of-the-art approaches.

Proceedings of CAV 12, LNCS 7358, 2012. 6 pages.

PDF © 2012 Springer-Verlag.

Imprint / Data Protection