Efficient Monitoring of Parametric Context Free Patterns

Meredith, Patrick O'Neil; Jin, Dongyun; Chen, Feng; Rosu, Grigore

Permalink

https://hdl.handle.net/2142/11446 Copy

Description

Title

Efficient Monitoring of Parametric Context Free Patterns

Author(s)

• Meredith, Patrick O'Neil
• Jin, Dongyun
• Chen, Feng
• Rosu, Grigore

Issue Date

2008-04

Keyword(s)

computer science

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 of monitoring CFGs generate massive runtime overhead in real-life applications. This paper shows for the first time that monitoring parametric CFGs is practical (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 partial matching, allowing patterns to be checked against fragments of execution traces.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/11446

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections