Efficient monitoring of parametric context-free patterns

Patrick O.Neil Meredith, Dongyun Jin, Feng Chen, Grigore Roşu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Recent developments in runtime verification and monitoring show that parametric regular and temporal logic specifications can be efficiently monitored against large programs. However, these logics reduce to ordinary finite automata, limiting their expressivity. For example, neither can specify structured properties that refer to the call stack of the program. While context-free grammars (CFGs) are expressive and well-understood, existing techniques for monitoring CFGs generate large runtime overhead in real-life applications. This paper shows, for the first time, that monitoring parametric CFGs is practical (with overhead on the order of 10% or lower for average cases, several times faster than the state-of-the-art). We present a monitor synthesis algorithm for CFGs based on an LR(1) parsing algorithm, modified with stack cloning to account for good prefix matching. In addition, a logic-independent mechanism is introduced to support matching against the suffixes of execution traces.

Original languageEnglish (US)
Title of host publicationASE 2008 - 23rd IEEE/ACM International Conference on Automated Software Engineering, Proceedings
Pages148-157
Number of pages10
DOIs
StatePublished - 2008
EventASE 2008 - 23rd IEEE/ACM International Conference on Automated Software Engineering - L'Aquila, Italy
Duration: Sep 15 2008Sep 19 2008

Publication series

NameASE 2008 - 23rd IEEE/ACM International Conference on Automated Software Engineering, Proceedings

Other

OtherASE 2008 - 23rd IEEE/ACM International Conference on Automated Software Engineering
CountryItaly
CityL'Aquila
Period9/15/089/19/08

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Efficient monitoring of parametric context-free patterns'. Together they form a unique fingerprint.

Cite this