Skip to main content

Tree Buffers

Grigore, Radu and Kiefer, Stefan (2015) Tree Buffers. In: Computer Aided Verification 27th International Conference. Lecture Notes in Computer Science . Springer, Cham, Switzerland, pp. 290-306. ISBN 978-3-319-21689-8. E-ISBN 978-3-319-21690-4. (doi:10.1007/978-3-319-21690-4_17) (KAR id:54173)

Abstract

In runtime verification, the central problem is to decide if a given program execution violates a given property. In online runtime verification, a monitor observes a program’s execution as it happens. If the program being observed has hard real-time constraints, then the monitor inherits them. In the presence of hard real-time constraints it becomes a challenge to maintain enough information to produce error traces, should a property violation be observed. In this paper we introduce a data structure, called tree buffer, that solves this problem in the context of automata-based monitors: If the monitor itself respects hard real-time constraints, then enriching it by tree buffers makes it possible to provide error traces, which are essential for diagnosing defects. We show that tree buffers are also useful in other application domains. For example, they can be used to implement functionality of capturing groups in regular expressions. We prove optimal asymptotic bounds for our data structure, and validate them using empirical data from two sources: regular expression searching through Wikipedia, and runtime verification of execution traces obtained from the DaCapo test suite.

Item Type: Book section
DOI/Identification number: 10.1007/978-3-319-21690-4_17
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming, > QA76.76 Computer software
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Radu Grigore
Date Deposited: 11 Feb 2016 16:30 UTC
Last Modified: 16 Feb 2021 13:33 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/54173 (The current URI for this page, for reference purposes)

University of Kent Author Information

  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.