DROPS

Document

DOI: 10.4230/LIPIcs.CONCUR.2020.50

Propositional Dynamic Logic for Hyperproperties

Authors: Jens Oliver Gutsfeld, Markus Müller-Olm, and Christoph Ohrem

Published in: LIPIcs, Volume 171, 31st International Conference on Concurrency Theory (CONCUR 2020)

Abstract

Information security properties of reactive systems like non-interference often require relating different executions of the system to each other and following them simultaneously. Such hyperproperties can also be useful in other contexts, e.g., when analysing properties of distributed systems like linearizability. Since common logics like LTL, CTL, or the modal μ-calculus cannot express hyperproperties, the hyperlogics HyperLTL and HyperCTL^* were developed to cure this defect. However, these logics are not able to express arbitrary ω-regular properties. In this paper, we introduce HyperPDL-Δ, an adaptation of the Propositional Dynamic Logic of Fischer and Ladner for hyperproperties, in order to remove this limitation. Using an elegant automata-theoretic framework, we show that HyperPDL-Δ model checking is asymptotically not more expensive than HyperCTL^* model checking, despite its vastly increased expressive power. We further investigate fragments of HyperPDL-Δ with regard to satisfiability checking.

Cite as

Jens Oliver Gutsfeld, Markus Müller-Olm, and Christoph Ohrem. Propositional Dynamic Logic for Hyperproperties. In 31st International Conference on Concurrency Theory (CONCUR 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 171, pp. 50:1-50:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gutsfeld_et_al:LIPIcs.CONCUR.2020.50,
  author =	{Gutsfeld, Jens Oliver and M\"{u}ller-Olm, Markus and Ohrem, Christoph},
  title =	{{Propositional Dynamic Logic for Hyperproperties}},
  booktitle =	{31st International Conference on Concurrency Theory (CONCUR 2020)},
  pages =	{50:1--50:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-160-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{171},
  editor =	{Konnov, Igor and Kov\'{a}cs, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2020.50},
  URN =		{urn:nbn:de:0030-drops-128628},
  doi =		{10.4230/LIPIcs.CONCUR.2020.50},
  annote =	{Keywords: Hyperlogics, Hyperproperties, Model Checking, Automata}
}

Search Results

Documents authored by Ohrem, Christoph

Propositional Dynamic Logic for Hyperproperties

Abstract

Cite as

Thanks for your feedback!

Could not send message