License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2020.29
URN: urn:nbn:de:0030-drops-116720
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11672/
Go to the corresponding LIPIcs Volume Portal

Mascle, Corto ; Zimmermann, Martin

The Keys to Decidable HyperLTL Satisfiability: Small Models or Very Simple Formulas

pdf-format:
LIPIcs-CSL-2020-29.pdf (0.5 MB)

Abstract

HyperLTL, the extension of Linear Temporal Logic by trace quantifiers, is a uniform framework for expressing information flow policies by relating multiple traces of a security-critical system. HyperLTL has been successfully applied to express fundamental security policies like noninterference and observational determinism, but has also found applications beyond security, e.g., distributed protocols and coding theory. However, HyperLTL satisfiability is undecidable as soon as there are existential quantifiers in the scope of a universal one. To overcome this severe limitation to applicability, we investigate here restricted variants of the satisfiability problem to pinpoint the decidability border.
First, we restrict the space of admissible models and show decidability when restricting the search space to models of bounded size or to finitely representable ones. Second, we consider formulas with restricted nesting of temporal operators and show that nesting depth one yields decidability for a slightly larger class of quantifier prefixes. We provide tight complexity bounds in almost all cases.

BibTeX - Entry

@InProceedings{mascle_et_al:LIPIcs:2020:11672,
  author =	{Corto Mascle and Martin Zimmermann},
  title =	{{The Keys to Decidable HyperLTL Satisfiability: Small Models or Very Simple Formulas}},
  booktitle =	{28th EACSL Annual Conference on Computer Science Logic (CSL 2020)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-132-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{152},
  editor =	{Maribel Fern{\'a}ndez and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11672},
  URN =		{urn:nbn:de:0030-drops-116720},
  doi =		{10.4230/LIPIcs.CSL.2020.29},
  annote =	{Keywords: Hyperproperties, Linear Temporal Logic, Satisfiability}
}

Keywords: Hyperproperties, Linear Temporal Logic, Satisfiability
Collection: 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)
Issue Date: 2020
Date of publication: 06.01.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI