Can determinism and compositionality coexist in RML?

Davide Ancona, Angelo Ferrando, Viviana Mascardi

TL;DR

This paper bridges the gap between performance and mathematical clarity in Runtime Verification (RV) by developing a compositional semantics for the Runtime Monitoring Language (RML). By mapping RML's highly efficient, deterministic operational operators to operations on sets of instantiated event traces, the authors prove that determinism and compositionality can indeed coexist without sacrificing monitor performance.

What Problem Does This Paper Address?

Runtime Verification (RV) is the practice of checking whether a running software system complies with a formal specification. To do this efficiently online, tools generate monitors that ingest system events and output verdicts. The Runtime Monitoring Language (RML) is a domain-specific language designed for this purpose.

To ensure high performance and avoid the dreaded "Regular expression Denial of Service" (ReDoS) caused by exponential state explosion, RML relies on a fully deterministic operational semantics. It uses a left-preferential evaluation strategy: when faced with choices (like a union or a shuffle), it eagerly prefers the left operand.

While this determinism makes RML monitors incredibly fast and backtracking-free, it breaks standard compositionality—the ability to understand the meaning of a complex expression solely by combining the meanings of its parts. For example, standard language concatenation of the sets $\{\lambda, a\}$ and $\{\lambda, ab\}$ yields $\{\lambda, a, ab, aab\}$. However, under RML's left-preferential rules, it yields $\{\lambda, a, aab\}$. Eagerly choosing the left path alters the expected outcome, making it highly non-intuitive to reason about or formally verify RML specifications. The authors tackle the question: Can we create a compositional way to understand RML without losing its deterministic performance benefits?

Methods

The authors construct a novel denotational, compositional semantics for the RML trace calculus. The syntax of this calculus is defined coinductively to support cyclic (recursive) terms, as shown in Figure 1:

Figure 1: Syntax of the RML trace calculus: θ is defined inductively, t is defined coinductively on the set of cyclic terms.

The key methodological innovations include:

  • Instantiated Event Traces: Instead of evaluating simple event streams, the new semantics operates on pairs consisting of an event trace ($\bar{e}$) and a variable substitution ($\sigma$). This tracking mechanism is vital for handling parametric specifications (e.g., ensuring that an open(fd) event and a close(fd) event map to the same file descriptor value).
  • Deterministic Compositional Operators: The authors redefine RML's core binary operators—left-preferential union ($\cup_{\leftarrow}$), left-preferential concatenation ($\cdot_{\leftarrow}$), intersection ($\cap$), and left-preferential shuffle ($|_{\leftarrow}$)—as mathematical operations acting directly on these sets of instantiated traces.
  • Contractivity Restriction: To prevent monitors from entering infinite loops without consuming events (akin to left-recursion issues in context-free grammars), the authors enforce a syntactic condition called contractivity.
  • Coinductive Equivalence Proof: Using coinduction and a series of structural lemmas, the authors formally prove that their new compositional semantics is perfectly equivalent to RML's original transition-system-based operational semantics.

Datasets

Not discussed in the paper (as this is a purely theoretical formal methods paper and does not introduce empirical datasets or benchmarks).

Key Insights and Ideas

  • Substitutions Must Be First-Class Citizens: You cannot achieve compositionality in a parametric trace calculus by looking at events alone. The variable bindings ($\sigma$) generated during event matching must be explicitly woven into the trace semantics so that independent components can safely merge their data requirements.
  • Left-Preference is Mathematically Tractable: Eager, deterministic choices (like the left-preferential shuffle) look messy operationally, but they can be modeled cleanly as set operations. The generalized left-preferential shuffle introduced in this paper provides a blueprint for how to restrict right-side trace contributions based on what the left side could have consumed.
  • Contractivity is the Bridge: The equivalence between the operational rewriting system and the compositional set theory holds true because of contractivity. Without it, non-contractive terms fail to yield finite derivation trees in the inductive operational semantics, breaking the equivalence.

Key Results

  • Theorem 4.1 (Main Theorem): The authors successfully prove that for all contractive terms $t_1$ and $t_2$, the abstract operational semantics maps exactly to the new compositional operators:
  • $\llbracket t_1 \vee t_2 \rrbracket = \llbracket t_1 \rrbracket \cup_{\leftarrow} \llbracket t_2 \rrbracket$
  • $\llbracket t_1 \cdot t_2 \rrbracket = \llbracket t_1 \rrbracket \cdot_{\leftarrow} \llbracket t_2 \rrbracket$
  • $\llbracket t_1 \wedge t_2 \rrbracket = \llbracket t_1 \rrbracket \cap \llbracket t_2 \rrbracket$
  • $\llbracket t_1 \mid t_2 \rrbracket = \llbracket t_1 \rrbracket \mid_{\leftarrow} \llbracket t_2 \rrbracket$
  • Best of Both Worlds: This mathematical equivalence means developers can now reason about, modularize, and mathematically verify complex RML specifications compositionally, while the underlying compiler still generates highly optimized, deterministic, backtracking-free code.

Limitations and Future Work

  • Core Calculus Limitation: The current proof only covers the core RML calculus. It omits full language features such as the prefix closure operator and top-level generic specification layers.
  • Expressive Power of Contractivity: While contractivity is required for the equivalence proof, the authors have not yet formally proven whether this syntactic restriction limits the overall expressive power of RML (though they note they have failed to find a non-contractive term that cannot be rewritten into an equivalent contractive one).

Summary updated

Abstract

Runtime verification (RV) consists in dynamically verifying that the event traces generated by single runs of a system under scrutiny (SUS) are compliant with the formal specification of its expected properties. RML (Runtime Monitoring Language) is a simple but expressive Domain Specific Language for RV; its semantics is based on a trace calculus formalized by a deterministic rewriting system which drives the implementation of the interpreter of the monitors generated by the RML compiler from the specifications. While determinism of the trace calculus ensures better performances of the generated monitors, it makes the semantics of its operators less intuitive. In this paper we move a first step towards a compositional semantics of the RML trace calculus, by interpreting its basic operators as operations on sets of instantiated event traces and by proving that such an interpretation is equivalent to the operational semantics of the calculus.
BibTeX
@misc{ancona2020can,
  author = {Davide Ancona and Angelo Ferrando and Viviana Mascardi},
  title = {{Can determinism and compositionality coexist in RML?}},
  year = {2020},
  eprint = {2008.06453},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2008.06453},
}
Figure