Algorithms for Monitoring Hyperproperties

Christopher Hahn

Hyperproperties relate multiple computation traces to each other and thus pose a serious challenge to monitoring algorithms. Observational determinism, for example, is a hyperproperty which states that private data should not influence the observable behavior of a system. Standard trace monitoring techniques are not applicable to such properties. In this tutorial, we summarize recent algorithmic advances in monitoring hyperproperties from logical specifications. We classify current approaches into two classes: combinatorial approaches and constraint-based approaches. We summarize current optimization techniques for keeping the execution trace storage and algorithmic workload as low as possible and also report on experiments run on the combinatorial as well as the constraint-based monitoring algorithms.

19th International Conference on Runtime Verification @ 3rd World Congress on Formal Methods (RV 2019 @ FM’19).

Copyright by Springer Verlag. The final publication is available at Springerlink.

(pdf)