Efficient monitoring of parametric context-free patterns

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

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)149-180
Number of pages32
JournalAutomated Software Engineering
Issue number2
StatePublished - Jun 2010


  • Context-free languages
  • Monitoring
  • Runtime verification

ASJC Scopus subject areas

  • Software


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

Cite this