  Runtime verification (RV) is a pragmatic and scalable, yet rigorous
technique, to assess the correctness of complex systems, including
cyber-physical systems (CPS). By measuring how robustly a CPS run satisfies a
specification, RV allows in addition, to quantify the resiliency of a CPS to
perturbations. In this paper we propose Algebraic Runtime Verification (ARV), a
general, semantic framework for RV, which takes advantage of the monoidal
structure of runs (w.r.t. concatenation) and the semiring structure of a
specification automaton (w.r.t. choice and concatenation), to compute in an
incremental and application specific fashion the resiliency measure. This
allows us to expose the core aspects of RV, by developing an abstract
monitoring algorithm, and to strengthen and unify the various qualitative and
quantitative approaches to RV, by instantiating choice and concatenation with
real-valued functions as dictated by the application. We demonstrate the power
and effectiveness of our framework on two case studies from the automotive
domain.
