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.2021.7
URN: urn:nbn:de:0030-drops-134416
Go to the corresponding LIPIcs Volume Portal

Aceto, Luca ; Achilleos, Antonis ; Francalanza, Adrian ; Ingólfsdóttir, Anna ; Lehtinen, Karoliina

The Best a Monitor Can Do

LIPIcs-CSL-2021-7.pdf (0.7 MB)


Existing notions of monitorability for branching-time properties are fairly restrictive. This, in turn, impacts the ability to incorporate prior knowledge about the system under scrutiny - which corresponds to a branching-time property - into the runtime analysis. We propose a definition of optimal monitors that verify the best monitorable under- or over-approximation of a specification, regardless of its monitorability status. Optimal monitors can be obtained for arbitrary branching-time properties by synthesising a sound and complete monitor for their strongest monitorable consequence. We show that the strongest monitorable consequence of specifications expressed in Hennessy-Milner logic with recursion is itself expressible in this logic, and present a procedure to find it. Our procedure enables prior knowledge to be optimally incorporated into runtime monitors.

BibTeX - Entry

  author =	{Luca Aceto and Antonis Achilleos and Adrian Francalanza and Anna Ing{\'o}lfsd{\'o}ttir and Karoliina Lehtinen},
  title =	{{The Best a Monitor Can Do}},
  booktitle =	{29th EACSL Annual Conference on Computer Science Logic (CSL 2021)},
  pages =	{7:1--7:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-175-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{183},
  editor =	{Christel Baier and Jean Goubault-Larrecq},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-134416},
  doi =		{10.4230/LIPIcs.CSL.2021.7},
  annote =	{Keywords: monitorability, branching-time logics, runtime verification}

Keywords: monitorability, branching-time logics, runtime verification
Collection: 29th EACSL Annual Conference on Computer Science Logic (CSL 2021)
Issue Date: 2021
Date of publication: 13.01.2021

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