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.TIME.2019.20
URN: urn:nbn:de:0030-drops-113782
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11378/
Go to the corresponding LIPIcs Volume Portal

Ho, Hsi-Ming ; Zhou, Ruoyu ; Jones, Timothy M.

On Verifying Timed Hyperproperties

pdf-format:
LIPIcs-TIME-2019-20.pdf (0.7 MB)

Abstract

We study the satisfiability and model-checking problems for timed hyperproperties specified with HyperMTL, a timed extension of HyperLTL. Depending on whether interleaving of events in different traces is allowed, two possible semantics can be defined for timed hyperproperties: synchronous and asynchronous. While the satisfiability problem can be decided similarly as for HyperLTL regardless of the choice of semantics, we show that the model-checking problem for HyperMTL, unless the specification is alternation-free, is undecidable even when very restricted timing constraints are allowed. On the positive side, we show that model checking HyperMTL with quantifier alternations is possible under certain conditions in the synchronous semantics, or when there is a fixed bound on the length of the time domain.

BibTeX - Entry

@InProceedings{ho_et_al:LIPIcs:2019:11378,
  author =	{Hsi-Ming Ho and Ruoyu Zhou and Timothy M. Jones},
  title =	{{On Verifying Timed Hyperproperties}},
  booktitle =	{26th International Symposium on Temporal Representation and Reasoning (TIME 2019)},
  pages =	{20:1--20:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-127-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{147},
  editor =	{Johann Gamper and Sophie Pinchinat and Guido Sciavicco},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11378},
  URN =		{urn:nbn:de:0030-drops-113782},
  doi =		{10.4230/LIPIcs.TIME.2019.20},
  annote =	{Keywords: Timed Automata, Temporal Logics, Cybersecurity}
}

Keywords: Timed Automata, Temporal Logics, Cybersecurity
Collection: 26th International Symposium on Temporal Representation and Reasoning (TIME 2019)
Issue Date: 2019
Date of publication: 07.10.2019

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