The Complexity of Monitoring Hyperproperties

Bonakdarpour, B. and Finkbeiner, Bernd
(2018) The Complexity of Monitoring Hyperproperties.
In: 2018 IEEE 31st Computer Security Foundations Symposium (CSF).
Conference: CSF IEEE Computer Security Foundations Symposium (was CSFW)

Full text not available from this repository.


—We study the runtime verification of hyperproperties, expressed in the temporal logic HyperLTL, as a means to inspect a system with respect to security polices. Runtime monitors for hyperproperties analyze trace logs that are organized by common prefixes in the form of a tree-shaped Kripke structure, or are organized both by common prefixes and by common suffixes in the form of an acyclic Kripke structure. Unlike runtime verification techniques for trace properties, where the monitor tracks the state of the specification but usually does not need to store traces, a monitor for hyperproperties repeatedly model checks the growing Kripke structure. This calls for a rigorous complexity analysis of the model checking problem over treeshaped and acyclic Kripke structures.


Actions (login required)

View Item View Item