TY - GEN
T1 - Efficient monitoring of parametric context-free patterns
AU - Meredith, Patrick O.Neil
AU - Jin, Dongyun
AU - Chen, Feng
AU - Roşu, Grigore
N1 - Copyright:
Copyright 2011 Elsevier B.V., All rights reserved.
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=56249134236&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=56249134236&partnerID=8YFLogxK
U2 - 10.1109/ASE.2008.25
DO - 10.1109/ASE.2008.25
M3 - Conference contribution
AN - SCOPUS:56249134236
SN - 9781424421886
T3 - ASE 2008 - 23rd IEEE/ACM International Conference on Automated Software Engineering, Proceedings
SP - 148
EP - 157
BT - ASE 2008 - 23rd IEEE/ACM International Conference on Automated Software Engineering, Proceedings
T2 - ASE 2008 - 23rd IEEE/ACM International Conference on Automated Software Engineering
Y2 - 15 September 2008 through 19 September 2008
ER -