TY - GEN
T1 - Garbage collection for monitoring parametric properties
AU - Jin, Dongyun
AU - Meredith, Patrick O.Neil
AU - Griffith, Dennis
AU - Rosu, Grigore
PY - 2011
Y1 - 2011
N2 - Parametric properties are behavioral properties over program events that depend on one or more parameters. Parameters are bound to concrete data or objects at runtime, which makes parametric properties particularly suitable for stating multi-object relationships or protocols. Monitoring parametric properties independently of the employed formalism involves slicing traces with respect to parameter instances and sending these slices to appropriate non-parametric monitor instances. The number of such instances is theoretically unbounded and tends to be enormous in practice, to an extent that how to efficiently manage monitor instances has become one of the most challenging problems in runtime verification. The previous formalism-independent approach was only able to do the obvious, namely to garbage collect monitor instances when all bound parameter objects were garbage collected. This led to pathological behaviors where unnecessary monitor instances were kept for the entire length of a program. This paper proposes a new approach to garbage collecting monitor instances. Unnecessary monitor instances are collected lazily to avoid creating undue overhead. This lazy collection, along with some careful engineering, has resulted in RV, the most efficient parametric monitoring system to date. Our evaluation shows that the average overhead of RV in the DaCapo benchmark is 15%, which is two times lower than that of JavaMOP and orders of magnitude lower than that of Tracematches.
AB - Parametric properties are behavioral properties over program events that depend on one or more parameters. Parameters are bound to concrete data or objects at runtime, which makes parametric properties particularly suitable for stating multi-object relationships or protocols. Monitoring parametric properties independently of the employed formalism involves slicing traces with respect to parameter instances and sending these slices to appropriate non-parametric monitor instances. The number of such instances is theoretically unbounded and tends to be enormous in practice, to an extent that how to efficiently manage monitor instances has become one of the most challenging problems in runtime verification. The previous formalism-independent approach was only able to do the obvious, namely to garbage collect monitor instances when all bound parameter objects were garbage collected. This led to pathological behaviors where unnecessary monitor instances were kept for the entire length of a program. This paper proposes a new approach to garbage collecting monitor instances. Unnecessary monitor instances are collected lazily to avoid creating undue overhead. This lazy collection, along with some careful engineering, has resulted in RV, the most efficient parametric monitoring system to date. Our evaluation shows that the average overhead of RV in the DaCapo benchmark is 15%, which is two times lower than that of JavaMOP and orders of magnitude lower than that of Tracematches.
KW - aspect-oriented programming
KW - debugging
KW - garbage collection
KW - runtime monitoring
KW - runtime verification
KW - testing
UR - http://www.scopus.com/inward/record.url?scp=79959903228&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79959903228&partnerID=8YFLogxK
U2 - 10.1145/1993498.1993547
DO - 10.1145/1993498.1993547
M3 - Conference contribution
AN - SCOPUS:79959903228
SN - 9781450306638
T3 - Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)
SP - 415
EP - 424
BT - PLDI'11 - Proceedings of the 2011 ACM Conference on Programming Language Design and Implementation
T2 - 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI'11
Y2 - 4 June 2011 through 8 June 2011
ER -