Efficient Monitoring of Parametric Context-Free Patterns

From FSL
Jump to: navigation, search

This work has been published in a journal paper (J.ASE), in a conference proceedings (ASE'08), where it won an ACM Sigsoft Distinguished paper, and in a technical report. These papers describe the creation of the first efficient means of monitoring context-free pattern based properties. Only two previous monitoring systems use logics that encompass the context-free languages: Hawk/Eagle and Program Query Language (PQL). Neither uses a logic that allows one to express a context free grammar naturally, and, at the beginning of 2010, both are orders of magnitude less efficient.

J.ASE

Efficient Monitoring of Parametric Context-Free Patterns
Patrick Meredith, Dongyun Jin, Feng Chen and Grigore Rosu
J. of ASE, Volume 17(2), pp 149-180. 2010
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 demonstrates that monitoring parametric CFGs is practical (with overhead on the order of 12% or lower in most cases). We present a monitor synthesis algorithm for CFGs based on an LR(1) parsing algorithm, modified to account for good prefix matching. In addition, a logic-independent mechanism is introduced to support matching against the suffixes of execution traces.
PDF, J.ASE, BIB

ASE'08

Efficient Monitoring of Parametric Context-Free Patterns
Patrick Meredith, Dongyun Jin, Feng Chen and Grigore Rosu
ASE'08, IEEE/ACM, pp 148-157. 2008 ACM Sigsoft Distinguished Paper
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.
PDF, Experiments, ASE'08 slides(KEY), ASE'08 slides(MOV), ASE'08 slides(PPT), IEEE, ASE'08, BIB


Personal tools
Namespaces

Variants
Actions
Navigation