Efficient Monitoring of Parametric Context-Free Patterns

From FSL

Efficient Monitoring of Parametric Context-Free Patterns

Patrick Meredith, Feng Chen, Dongyun Jin, and Grigore Rosu

ASE'08, to appear

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 {\em 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 {\em 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.

PDF, BIB

[edit] Technical Report

Efficient Monitoring of Parametric Context-Free Patterns 

Patrick Meredith, Feng Chen, Dongyun Jin, and Grigore Rosu
Technical report UIUCDCS-R-2008-2954, April 2008
PDF, TR@UIUC, BIB