Refinement of Legal Specifications in the Lex Programming Language

Extending the Lex language with refinement, so abstract legal specifications can be made concrete for specific use cases

Jonas DegeloMaster's Thesis, ETH ZurichMay 30th, 2025

Supervisor: Prof. Dr. David BasinAdvisors: François Hublet, Dr. Jakob Merane

Read the PDFLex paper · CCS ’26Thesis talkPractical-work talk

Scroll

Abstract

The increasing complexity of digital regulations and the difficulty of ensuring consistent compliance have led to a growing interest in runtime enforcement techniques that automatically verify regulatory compliance. However, these approaches depend on formalized representations of legal norms. Lex is a domain-specific language that provides a highly readable and auditable way to formalize legal specifications. This thesis extends Lex with a notion of refinement, enabling modular specification development through code reuse and incremental adaptation. Refinement allows abstract legal specifications to be concretized for specific use cases while maintaining a clear connection to their original intent.

Introduction

As digital services become increasingly important, a growing number of laws are being introduced to regulate the digital world. One prominent example is the EU’s General Data Protection Regulation (GDPR), which aims to protect the privacy of individuals in the European Union. However, empirical evidence indicates that such regulations are frequently disregarded in practice [13].

In order to address this challenge, runtime enforcement has emerged as a promising technique to automatically ensure that a system complies with a given regulation. Runtime enforcement provides automated solutions to ensure Compliance by Design with digital regulations by modifying the system’s behavior when required.

The feasibility of such enforcement is contingent upon the existence of automated policies that are sufficiently formal. Nevertheless, legal texts written in natural language do not directly meet this requirement. Lex [12, 8], a programming language developed as a specification language for legal texts, has been shown to maintain a high level of readability while being formal enough to develop policies for runtime enforcement. This intricacy is a primary rationale behind the integration of the refinement concept into Lex, as outlined in this thesis. The term "refinement" is employed to denote both a conceptual framework in which a particular concrete specification is said to "implement" (or be "derived" from) a more abstract specification, as well as the process of deriving such a concrete specification from an abstract one. Refinement allows users to reuse existing Lex specifications and make minimal changes to adapt them to their specific use cases.

Our Approach

Lex is designed to formalize legal texts for the purpose of using the formalization as a policy for runtime enforcement. Despite its advanced features, formalizing a law in Lex remains a complex task. A foundational component of any Lex specification is the concept of events. These events define a model of the world. In order to ensure the accuracy and simplicity of formalization, it is essential that these events be as general as possible. Conversely, to effectively enforce a given system, the events in the specification must directly correspond to system events. This is a fundamental aspect of the challenge this thesis aims to address. It proposes a comprehensive specification that encompasses both abstract and concrete elements, integrating them to create a cohesive system model. This approach facilitates the mapping of the concrete system model to the abstract specification, thereby enabling a seamless integration of both abstract and concrete components. We apply refinement techniques to enable the reuse of a general, abstract formalization as a baseline policy for different systems. This is achieved by defining a comparatively short refinement specification for each system

Related Work

There exist a multitude of languages and logics for formalizing legal texts. Each with its own strengths and weaknesses.

In recent years, two notable domain-specific languages for legal texts have been introduced. Merigoux et al. introduced Catala [15], a programming language intended for directly transforming existing laws, such as the US tax code, into executable code. Catala is noteworthy for its approach to maintaining the structural hierarchy of laws in its code, as well as its utilization of prioritized default logic [6] as a foundation for addressing exceptions. Van Binsbergen et al. [18] have developed eFlint, another programming language that facilitates the transformation of legal specifications into executable code. eFlint does not inherently maintain a law’s hierarchy in its code, because of this it can also be used for other kind of norms. While Catala is not intended to be used for enforcement purposes, eFlint can be used for certain kinds of enforcement. eFlint was for example used to enforce that an actor has permission to perform an action before doing so. But it was not used in a way that would ensure full Compliance by Design as violations were sometimes allowed to happen and then reacted to. Both Catala and eFlint do not directly support refinement of existing specifications, and they further differ from Lex in so far as that Lex specifications are not themselves executable.

Refinement

Refinement of specifications is a common technique in formal methods where one starts with a more general specification and works towards a more concrete specification that implements or fulfills the general specification. Abadi and Lamport [3] have introduced refinement mappings as a technique for proving that one specification implements another specification. Sprenger et al. [17] have used refinement as a method to get a concrete implementation of a program that complies with an abstract specification.

Runtime Enforcement

Schneider [16] has characterized the kind of policies that can be enforced mechanically and he has also given techniques for such mechanical enforcement. Since then a lot of research has been done on the topic of runtime enforcement.

Hublet et al. [9, 10] developed a proactive runtime enforcement algorithm that uses Metric First Order Temporal Logic (MFOTL) [5] as a policy language. Hublet et al. [12] and Degelo [8] have introduced the Lex programming language that compiles to MFOTL and is therefore compatible with these proactive runtime enforcement algorithms.

Contributions

This thesis presents how support for refinement can be added to the Lex programming language, implementats refinement in Lex and demonstrates the refinement capabilities of Lex on a case study. Lex is a programming language for formalizing legal specifications, developed by Hublet, Degelo et al. [12, 8]. The contributions of this thesis are as followed. In Chapter 3 we introduce a proactive enforcement model based on event systems and prove that it is analogous to the enforcement model of Hublet et al. [9, 10]. We then introduce a set of refinement rules for the CRE logic introduced by Hublet et al. [12] and use our new proactive enforcement model. We show that these refinement rules correspond to refinement as used by Sprenger et al. [17] and Abadi and Lamport [3]. Chapter 4 introduces new language features to Lex that allow CRE refinements to be specified in Lex. We both present the syntax and semantics of these new language features and give an implementation of them. Chapter 5 presents a case study where we apply the refinement features of Lex to an example formalization of the EU ePrivacy Directive [1] and how it can be refined to enforce the ePrivacy Directive on the open source ticketing platform Pretix [2].

Parts of the Lex paper [12] (in particular those pertaining to refinement) have been developed in parallel with this thesis.

Preliminaries

Metric First-Order Temporal Logic

Metric First-Order Logic (MFOTL) [5, 7] is a logical system that combines first-order predicate logic with temporal operators such as ∘\Next ("next"), ∙\Prev ("previous"), U\UUntil ("until"), and S\Since ("since"). MFOTL is frequently utilized as a policy language in runtime verification [9, 12, 5].

Definition 2.1. An MFOTL Signature Σ=(D,E,F,ι)\Sigma = (\Domain, \Events, \Functions, \iota) is a quadruple consisting of a value domain D\Domain, a set of event names E\Events, a set of function names F\Functions, and an arity function ι:E∪F→N\iota : \Events \cup \Functions \to \Nat.

Definition 2.1 is the the same signature definition as in Hublet et. al [12, Section 2.2.2] and Hublet et. al [9, Section 2].

Example 2.2. For D=strings∪{⊥,⊤}∪N,E={giveEmailConsent,revokeEmailConsent,sednEmail},F={ageOfUser}ι(giveEmailConsent)=2,ι(revokeEmailConsent)=2,ι(sendEmail)=2,ι(ageOfUser)=1\begin{aligned} \Domain &= \texttt{strings} \cup \{ \bot, \top \} \cup \Nat, \\ \Events &= \{ \mathsf{giveEmailConsent}, \mathsf{revokeEmailConsent}, \mathsf{sednEmail} \}, \\ \Functions &= \{ \mathsf{ageOfUser} \} \\ \iota(\mathsf{giveEmailConsent}) &= 2, \\ \iota(\mathsf{revokeEmailConsent}) &= 2, \\ \iota(\mathsf{sendEmail}) &= 2, \\ \iota(\mathsf{ageOfUser}) &= 1 \end{aligned} Σ=(D,E,F,ι)\Sigma = (\Domain, \Events, \Functions, \iota) is an MFOTL signature.

Definition 2.3. An Event is a tuple (e,(p1,…,pk))∈E×Dk(e, \left(p_1, \dots, p_k \right) ) \in \Events \times \Domain^{k} where k=ι(e)k=\iota(e) and all pi∈Dp_i \in \Domain.

Example 2.4. giveEmailConsent("Alice","Account Updates") and revokeEmailConsent("Bob","Marketing")\begin{aligned} &\mathsf{giveEmailConsent}(\text{"Alice"}, \text{"Account Updates"}) \text{ and } \\ &\mathsf{revokeEmailConsent}(\text{"Bob"}, \text{"Marketing"}) \end{aligned} are events over the signature Σ\Sigma from Example 2.2.

Definition 2.5. A Database D∈DBD \in \Databases is a set of events.

Definition 2.6. A Trace σ∈T\sigma \in \Traces is a sequence ⟨(τi,Di)⟩1≤i≤k\left\langle{(\tau_i, D_i)}\right\rangle_{1 \leq i \leq k}, k∈N∪{∞}k \in \Nat \cup \lbrace \infty \rbrace of timestamps τi∈N\tau_i \in \Nat and finite databases Di∈DBD_i \in \Databases, where timestamps grow monotonically (∀i<∣σ∣. τi≤τi+1\forall i < |\sigma|.\,\tau_i \leq \tau_{i+1}) and progress (if ∣σ∣=∞|\sigma| = \infty, then lim⁡i→∞τi=∞\lim_{i\to\infty} \tau_i = \infty).

Definition 2.7. The set of Infinite Traces is denoted by Tω⊆(N×DB)∞\Traces_\omega \subseteq \left( \Nat \times \Databases \right)^{\infty}

Definition 2.8. The set of Finite Traces is denoted by Tf⊆(N×DB)∗\Traces_f \subseteq \left( \Nat \times \Databases \right)^*

Definition 2.9. A time-point 0≤i≤∣σ∣0 \leq i \leq |\sigma| is an index in a trace σ\sigma.

Example 2.10. σ=⟨(0,{giveEmailConsent("Alice","Account Updates")}),(1,{giveEmailConsent("Bob","Marketing")}),(2,{revokeEmailConsent("Alice","Account Updates"),giveEmailConsent("Bob","Account Updates")}),(10,∅)⟩\begin{aligned} \sigma = \langle &(0, &&\{\mathsf{giveEmailConsent}(\text{"Alice"}, \text{"Account Updates"})\}), \\ &(1, &&\{\mathsf{giveEmailConsent}(\text{"Bob"}, \text{"Marketing"})\}), \\ &(2, &&\{\mathsf{revokeEmailConsent}(\text{"Alice"}, \text{"Account Updates"}), \\ &&&\mathsf{giveEmailConsent}(\text{"Bob"}, \text{"Account Updates"})\}), \\ &(10, &&\emptyset) \rangle \end{aligned} σ\sigma is a finite trace over the signature Σ\Sigma from Example 2.2 with 4 time-points. The 4 time-points have the timestamps 00, 11, 22, and 1010.

Traces like Example 2.10 can be seen as representing a system’s behavior in a standardized form.

Definition 2.11. The Empty Trace is denoted by ε\emptytrace.

Definition 2.12. The function fts:T→N∪{⊥}\fts : \Traces \to \Nat \cup \left\{ \bot \right\} gives the first time stamp in a trace unless it is empty. fts(σ):={⊥if σ=ετif σ=(τ,D)⋅σ′\begin{aligned} \fts(\sigma) := \begin{cases} \bot & \text{if } \sigma = \emptytrace \\ \tau & \text{if } \sigma = \left( \tau, D \right) \cdot \sigma' \end{cases} \end{aligned}

Definition 2.13. The function lts:T→N∪{⊥}\lts : \Traces \to \Nat \cup \left\{ \bot \right\} gives the first time stamp in a trace unless it is empty. lts(σ):={⊥if σ=ετif σ=σ′⋅(τ,D)\begin{aligned} \lts(\sigma) := \begin{cases} \bot & \text{if } \sigma = \emptytrace \\ \tau & \text{if } \sigma = \sigma' \cdot \left( \tau, D \right) \end{cases} \end{aligned}

For the trace σ\sigma in Example 2.10 we have fts(σ)=0\fts(\sigma) = 0 and lts(σ)=10\lts(\sigma) = 10.

Definition 2.14. A Property is a subset P⊆TωP\subseteq \Traces_\omega.

A Property can be induced by some policy φ\phi, we denote this policy by P(φ)P(\phi). We say a trace σ\sigma is compliant with policy φ\phi if and only if σ∈P(φ)\sigma \in P(\phi).

Definition 2.15. The set of Non-Empty Intervals over N\Nat is denoted by I\Intervals.

Figure 2.1 defines the rules for when an MFOTL term is well-typed. And Figure 2.2 defines when an MFOTL formula is well-typed. In particular, these two sets of typing rules ensure that all events and functions have the correct number of arguments. Next we introduce the specific MFOTL grammar used which includes the notable additions of non-recursive let-bindings [19] and aggregations [4]. From here on let Var\Variables be a set of variables. The following grammar definition is the same as in Hublet et al. [10, Section 2.2].

Definition 2.16. Let c∈Dc \in \Domain, x∈Varx \in \Variables, f∈Ff \in \Functions, e∈Ee \in \Events, and I∈II \in \Intervals. Then our MFOTL Grammar is defined by the following two rules t::=c∣x∣f(t,…,t)φ::=⊤∣e(t,…,t)∣t=t∣¬φ∣φ∧φ∣∃. φ∣∘Iφ∣∙Iφ∣φUIφ∣φSIφ∣x←ω(t;x,…,x) φ∣let⁡e(x,…,x)=φinφ\begin{aligned} t &::= &&c \mid x \mid f(t,\dots,t) \\ \phi &::= &&\top \mid e(t,\dots,t) \mid t=t \mid \neg \phi \mid \phi \wedge \phi \mid \exists.\ \phi \mid \Next_I \phi \mid \Prev_I \phi \mid \phi \UUntil_I \phi \mid \phi \Since_I \phi \\ &&& \mid \Aggreg{x}{\omega}{t}{x,\dots,x}{\phi} \mid \LLet{e \left(x,\dots,x \right)}{\phi}{\phi} \end{aligned}

  c∈D    Γ⊢trmc   Constant  v∈Var    Γ⊢trmv   Variable  f∈Fti∈Dι(f)=k    Γ⊢trmf(t1,…,tk)   Function\begin{gathered} \prfrule{Constant}{c \in \Domain}{\Gamma \vdash_{trm} c} \qquad \prfrule{Variable}{v \in \Variables}{\Gamma \vdash_{trm} v} \\[1.1em] \prfrule{Function}{f \in \Functions \quad t_i \in \Domain \quad \iota(f) = k}{\Gamma \vdash_{trm} f\left(t_1,\dots,t_k\right)} \end{gathered}

Fig 2.1MFOTL Term Typing Rules

      Γ⊢⊤   True  Γ⊬φ    Γ⊢¬φ   Not  Γ⊢φΓ⊢ψ    Γ⊢φ∧ψ   And  e∈EΓ⊢trmxi    Γ⊢e(x1,…,xk)   Event  Γ⊢φx∈Var    Γ⊢∃x.φ   Exists  Γ⊢φI∈I    Γ⊢∘Iφ   Next  Γ⊢φI∈I    Γ⊢∙Iφ   Previous  Γ⊢φΓ⊢ψI∈I    Γ⊢φUIψ   Until  Γ⊢φΓ⊢ψI∈I    Γ⊢φSIψ   Since  Γ⊢φΓ[E↦E∪{e},ι↦ι[e↦k]]⊢ψΓ⊢trmxi    Γ⊢let⁡e(x1,…,xk)=φinψ   Let\begin{gathered} \prfrule{True}{}{\Gamma \vdash \top} \qquad \prfrule{Not}{\Gamma \not\vdash \phi}{\Gamma \vdash \neg \phi} \qquad \prfrule{And}{\Gamma \vdash \phi \quad \Gamma \vdash \psi}{\Gamma \vdash \phi \wedge \psi} \\[1.1em] \prfrule{Event}{e \in \Events \quad \Gamma \vdash_{trm} x_i}{\Gamma \vdash e\left(x_1, \dots, x_k\right)} \qquad \prfrule{Exists}{\Gamma \vdash \phi \quad x \in \Variables}{\Gamma \vdash \exists x. \phi} \\[1.1em] \prfrule{Next}{\Gamma \vdash \phi \quad I \in \Intervals}{\Gamma \vdash \Next_I \phi} \qquad \prfrule{Previous}{\Gamma \vdash \phi \quad I \in \Intervals}{\Gamma \vdash \Prev_I \phi} \\[1.1em] \prfrule{Until}{\Gamma \vdash \phi \quad \Gamma \vdash \psi \quad I \in \Intervals}{\Gamma \vdash \phi \UUntil_I \psi} \qquad \prfrule{Since}{\Gamma \vdash \phi \quad \Gamma \vdash \psi \quad I \in \Intervals}{\Gamma \vdash \phi \Since_I \psi} \\[1.1em] \prfrule{Let}{\Gamma \vdash \phi \quad \Gamma [\Events \mapsto \Events \cup \lbrace e \rbrace, \iota \mapsto \iota[e \mapsto k]] \vdash \psi \quad \Gamma \vdash_{trm} x_i}{\Gamma \vdash \LLet{e\left(x_1, \dots, x_k \right)}{\phi}{\psi}} \end{gathered}

Fig 2.2MFOTL Typing Rules

Definition 2.17. A variable Valuation v:Var→Dv: \Variables \to \Domain assigns a value to a variable.

Definition 2.18. The Evaluation of well-typed MFOTL terms tt under some valuation vv is (recursively) defined as followed: ↓vc:=cfor all constants c∈D↓vx:=v(x)for all variables v∈Var↓vf(t1,…,tk):=f^(↓vt1,⋯↓vtk)for all functions f∈F and all terms ti\begin{aligned} &\downarrow_v c &&:= c && \text{for all constants } c \in \Domain\\ &\downarrow_v x &&:= v(x) && \text{for all variables } v \in \Variables\\ &\downarrow_v f\left(t_1,\dots,t_k\right) &&:= \hat{f}\left(\downarrow_v t_1, \dots \downarrow_v t_k \right) && \text{for all functions } f \in \Functions \text{ and all terms } t_i \end{aligned}

Definition 2.19. An MFOTL formula φ\phi is satisfied at some time-point ii in a trace σ\sigma under some valuation vv is denoted by v,i⊨σφv,i \vDash_\sigma \phi.

If the trace is obvious from context the subscript σ\sigma in ⊨σ\vDash_\sigma can be omitted.

Definition 2.20. The Semantics of MFOTL for a fixed, infinite trace σ\sigma is defined as followed v,i⊨⊤v,i⊨¬φiff v,i⊭φv,i⊨φ∧ψiff v,i⊨φ and v,i⊨ψv,i⊨e(t1,…,tk)iff e(↓vt1,…,↓vtk)∈Div,i⊨∃x.φiff v[x↦d],i⊨φ for some d∈Dv,i⊨∘Iφiff v,i+1⊨φ and τi+1−τi∈Iv,i⊨∙Iφiff i>0 and v,i−1⊨φ and τi−τi−1∈Iv,i⊨φUIψiff v,j⊨ψ for some j≥i with τj−τi∈I and v,k⊨φ for all i≤k<jv,i⊨φSIψiff v,j⊨ψ for some j≤i with τi−τj∈I and v,k⊨φ for all j<k≤iv,i⊨let⁡e(x1,…,xk)=φinψiff v,i⊨σ[∀j.Dj↦Dj∪{e(dˉ)∣v[xˉ↦dˉ],j⊨φ}]ψ\begin{aligned} v, i &\vDash \top \\ v, i &\vDash \neg \phi &&\text{iff } v, i \not\vDash \phi \\ v, i &\vDash \phi \wedge \psi &&\text{iff } v, i \vDash \phi \text{ and } v, i \vDash \psi \\ v, i &\vDash e(t_1, \dots, t_k) &&\text{iff } e(\downarrow_v t_1, \dots, \downarrow_v t_k) \in D_i \\ v, i &\vDash \exists x. \phi &&\text{iff } v[x \mapsto d], i \vDash \phi \text{ for some } d \in \Domain \\ v, i &\vDash \Next_I \phi &&\text{iff } v, i+1 \vDash \phi \text{ and } \tau_{i+1} - \tau_i \in I \\ v, i &\vDash \Prev_I \phi &&\text{iff } i>0 \text{ and } v, i-1 \vDash \phi \text{ and } \tau_i - \tau_{i-1} \in I \\ v, i &\vDash \phi \UUntil_I \psi &&\text{iff } v, j \vDash \psi \text{ for some } j \geq i \text{ with } \tau_j - \tau_i \in I \\ &&& \text{ and } v, k \vDash \phi \text{ for all } i \leq k < j \\ v, i &\vDash \phi \Since_I \psi &&\text{iff } v, j \vDash \psi \text{ for some } j \leq i \text{ with } \tau_i - \tau_j \in I \\ &&& \text{ and } v, k \vDash \phi \text{ for all } j < k \leq i \\ v, i &\vDash \LLet{e(x_1, \dots, x_k)}{\phi}{\psi} && \text{iff } v, i \vDash_{\sigma \left[ \forall j. D_j \mapsto D_j \cup \left\lbrace e\left(\bar{d}\right) \mid v\left[\bar{x} \mapsto \bar{d}\right], j \vDash \phi \right\rbrace \right]} \psi \end{aligned}

Where c∈Dc \in \Domain, x∈Varx \in \Variables, f∈Ff \in \Functions, e∈Ee \in \Events, and I∈II \in \Intervals.

We define the following operators based on the basic operators above as "syntactic sugar".

Definition 2.21. MFOTL Syntactic Sugar ⊥:=¬⊤φ→ψ:=¬φ∨ψφ∨ψ:=¬(¬φ∧¬ψ)φ↔ψ:=(φ→ψ)∧(ψ→φ)∀x.φ:=¬(∃x.¬φ)◊⁡Iφ:=⊤UIφ(eventually)⧫⁡Iφ:=⊤SIφ(once)□⁡Iφ:=¬◊⁡¬φ(always)■⁡Iφ:=¬⧫⁡I¬φ(historically)\begin{aligned} \bot &:= \neg\top & \phi \to \psi &:= \neg \phi \vee \psi \\ \phi \vee \psi &:= \neg(\neg\phi \wedge \neg\psi) & \phi \leftrightarrow \psi &:= (\phi \to \psi) \wedge (\psi \to \phi) \\ \forall x. \phi &:= \neg(\exists x. \neg \phi) \\ \Eventually_I \phi &:= \top \UUntil_I \phi \quad \text{(eventually)} & \Once_I \phi &:= \top \Since_I \phi \quad \text{(once)}\\ \Always_I \phi &:= \neg \Eventually \neg \phi \quad \text{(always)} & \Historically_I \phi &:= \neg \Once_I \neg \phi \quad \text{(historically)} \end{aligned}

Definition 2.22. The Language of a MFOTL formula φ\phi is L(φ)={σ∈Tω∣∃v.v,0⊨σ}\Language(\phi) = \left\lbrace \sigma \in \Traces_\omega \mid \exists v. v,0 \vDash \sigma \right\rbrace

Example 2.23. An example of an MFOTL formula over the signature Σ\Sigma from Example 2.2 is φ:=□⁡[0,∞)(sendEmail(user,"marketing")→(¬revokeEmailConsent(user,"marketing"))S[0,∞)giveEmailConsent(user,"marketing"))\begin{aligned} \phi := &\Always_{[0,\infty)}( \mathsf{sendEmail}(\mathsf{user}, \text{"marketing"}) \to \\ & \quad (\neg \mathsf{revokeEmailConsent}(\mathsf{user}, \text{"marketing"})) \\ & \qquad \Since_{[0,\infty)} \mathsf{giveEmailConsent}(\mathsf{user}, \text{"marketing"}) ) \end{aligned}

In natural language the policy in Example 2.23 requires that sending a marketing email requires that the receiving user has previously consented to receiving marketing emails and has not revoked this consent.

Runtime Verification

Runtime Verification is a research domain that focuses on the behavior of a system under scrutiny (SuS) in relation to a specific policy. Runtime verification can be subdivided into two related techniques: Runtime Monitoring and Runtime Enforcement.

Runtime Monitoring is used to detect a policy violation either in an online (real-time) or offline fashion. In runtime monitoring a monitor continuously evaluates the current and past system state and determines whether it complies with some policy. For our purposes the system state gets abstracted into a trace of events and the policy represents a set of allowed traces. Since the monitor never interacts with the system itself, runtime monitoring can also be done after a program has finished executing.

Runtime Enforcement is used to actively cause or prevent certain system behaviors. Due to this interactive nature of runtime enforcement it is inherently online. If we consider our trace model on a high level, an enforcer can "edit" any time-point before it gets fully committed to the trace and additionally the enforcer can create its own time-points at any increment of time. The following subsection explores an approach for enforcing MFOTL policies.

Proactive Runtime Enforcement using MFOTL

XSE1.1: set of events D1.2: R-command RCom(Dℂ, D𝕊)2: P-command PCom(Dℂ)policy Ptime τ
Fig 2.3Proactive real-time first-order enforcement system model [9, Figure 2]

We consider the system model of Hublet et al. [9] which is shown in Figure 2.3. The system (under scrutiny) SS runs in some environment XX. The environment XX is not under the control of the enforcer EE. The enforcer EE must ensure that the system SS complies with some policy PP. To this end the enforcer is given two main ways of interaction with the system. First, it can react to observable events happening in the system via issuing R\mathsf{R}-commands (reactively) by causing events of its own and/or suppressing events before they are visible to the environment. And second, the enforcer can issue P\mathsf{P}-commands (proactively) by causing certain events at some time-stamp τ\tau.

In the following the event names of events in sets denoted by DCD_\Cau are all assumed to be in EC\Events_{\Cau} and DSD_\Sup are all assumed to be in ES\Events_{\Sup}. The next three definitions reintroduce the three types of commands used by Hublet et al. [9].

Definition 2.24. An R-Command has the form RCom(DC,DS)\RCom\left(D_{\Cau}, D_{\Sup}\right). This command is a reaction of the enforcer to some set of events DD, that the system sent to the enforcer. The trace of the enforced system will contain the set DC∪(D∖DS)D_{\Cau} \cup \left(D \setminus D_{\Sup} \right) of events.

Definition 2.25. A P-Command has the form PCom(DC)\PCom \left( D_{\Cau} \right). This command can be proactively issued by the enforcer before any clock tick to issue the set of events DCD_{\Cau}.

Definition 2.26. No-Command has the form NoCom\NCom and indicates that the enforcer takes no action.

Definition 2.27. The set of all commands is C\EnfCommands.

This leads us to Hublet et al.’s [9, 10] definition of a proactive enforcer.

Definition 2.28. An Enforcer E\Enforcer is a triple (S,s0,μ)\left(\EnfStates, s_0, \EnfFun \right), where S\EnfStates is a set of enforcer states s0∈Ss_0 \in \EnfStates is an initial enforcer state and μ:Tf×S×N×(DB∪{tick})→C×S\EnfFun : \Traces_f \times \EnfStates \times \Nat \times \left( \Databases \cup \left\{ \tick \right\} \right) \to \EnfCommands \times \EnfStates is a computable update function such that the following two conditions hold

  1. ∀σ∈Tf,τ∈N,D∈DB,s∈S. ∃DC∈DBC,DS∈DBS,s′∈S.\forall \sigma \in \Traces_f, \tau \in \Nat, D \in \Databases, s \in \EnfStates.~ \exists D_\Cau \in \Databases_\Cau, D_\Sup \in \Databases_\Sup, s' \in \EnfStates. μ(σ,s,τ,D)=(RCom(DC,DS),s′)∧DC⊆D\mu(\sigma,s,\tau, D) = (\RCom(D_\Cau,D_\Sup), s') \wedge D_\Cau \subseteq D

  2. ∀σ∈Tf,s∈S,τ∈N. ∃DC∈DBC,s′∈S.\forall \sigma \in \Traces_f, s \in \EnfStates, \tau \in \Nat.~ \exists D_\Cau \in \Databases_\Cau, s' \in \EnfStates. μ(σ,s,τ,tick)∈{(PCom(DC),s′),(NoCom,s′)}\mu(\sigma,s,\tau,\tick) \in \{(\PCom(D_\Cau), s'), (\NCom,s')\}

Hublet et al. [10] define an enforced trace algorithmically via Algorithm 1.

Definition 2.29. For any σ∈T\sigma \in \Traces and enforcer E=(S,s0,μ)\Enforcer=(\EnfStates,s_0,\mu), the enforced trace E(σ)\Enforcer(\sigma) is defined co-recursively in Algorithm 1.

Algorithm 1Enforced trace [10, Fig. 2]
  1. run(s,σ,σ′,τ)=\run(s,\sigma,\sigma',\tau)= case σ′\sigma' of
  2. ∣ε⇒ε\mid \varepsilon \Rightarrow \varepsilon
  3. ∣(τ′,D)⋅σ′′\mid(\tau', D) \cdot \sigma'' when τ′>τ⇒\tau' > \tau \Rightarrow let (o,s′)=μ(σ,s,τ,tick)(o,s') = \mu(\sigma,s,\tau,\mathsf{tick}) in
  4.     case oo of ∣PCom(DC)⇒(τ,DC)⋅run(s′,σ⋅(τ,DC),σ′,τ+1)\mid\PCom(D_\Cau) \Rightarrow (\tau,D_\Cau) \cdot \run(s',\sigma\cdot (\tau, D_\Cau),\sigma',\tau+1)
  5.                 ∣NoCom⇒run(s′,σ,σ′,τ+1)\mid\NCom \Rightarrow \run(s',\sigma,\sigma',\tau+1)
  6. ∣(τ′,D)⋅σ′′\mid(\tau', D) \cdot \sigma'' when τ′=τ⇒\tau' = \tau \Rightarrow let (o,s′)=μ(σ,s,τ,D);D′=(D∖DS)∪DC)(o,s') = \mu(\sigma,s,\tau,D); D' = (D \setminus D_\Sup) \cup D_\Cau) in
  7.     case oo of ∣RCom(DC,DS)⇒(τ,D′)⋅run(s′,σ⋅(τ,D′),σ′′,τ+1)\mid \RCom(D_\Cau,D_\Sup) \Rightarrow (\tau, D') \cdot \run(s',\sigma \cdot (\tau, D'),\sigma'',\tau+1)
  8. E(σ)=run(s0,ε,σ,if  σ=ε  then  0  else  fts(σ))\Enforcer(\sigma)= \run(s_0,\emptytrace,\sigma,\Ternaryop{\sigma=\emptytrace}{0}{\fts(\sigma)})

In Definition 2.29 the trace σ\sigma corresponds to a system’s behavior if it was running completely without an enforcer. The enforced trace then represents the systems behavior combined with those of the enforcer.

Definition 2.30. An enforcer E\Enforcer is sound with respect to some property PP, iff for any trace σ∈Tω\sigma \in \Traces_\omega, E(σ)∈P\Enforcer(\sigma) \in P.

Definition 2.31. An enforcer E\Enforcer is sound with respect to some policy φ\phi, iff it is sound for the language L(φ)\Language(\phi).

Soundness allows us to describe and capture the behavior of an enforcer.

Definition 2.32. An enforcer E=(S,s0,μ)\Enforcer = \left( \EnfStates, s_0, \EnfFun \right) is transparent with respect to some property PP iff for all σ∈P\sigma \in P, E(σ)=σ\Enforcer(\sigma) = \sigma.

Definition 2.33. An enforcer E=(S,s0,μ)\Enforcer = \left( \EnfStates, s_0, \EnfFun \right) is transparent with respect to some policy φ\phi iff it is transparent for the language L(φ)\Language(\phi).

Transparency means that an enforcer will not alter a trace that is already compliant with some policy or property. A property or policy is said to be (transparently) enforceable if there exists a (transparent) sound enforcer for the policy or property.

Enforceable MFOTL

Capabilities are an integral part of the proactive enforcement approach introduced by Hublet et. al [9]. Under this approach an enforcer can have different capabilities, or ways of interacting with events emitted by a given system under scrutiny (SuS). In Hublet et. al the set of capabilities consists of observable (O\Obs), suppressable (S\Sup), causable (C\Cau), and suppressable-causable (CS\Cau \Sup). Hublet et. al [12] expands this expands this system of capabilities, specifically it makes the existence of events that may not (always) be externally visible explicit. Under both notions a capability function κ:E→K\kappa : \Events \to \Capabilities is used to assign a capability to all events with some event name e∈Ee \in \Events. Also in both contexts, capabilities form a (semi)-lattice (K,⪯)(\Capabilities, \capleq).

ℂ𝕊ℂ𝕆𝕊𝕆ℂ⊥
Fig 2.4The Capability Lattice (K,⪯)(\Capabilities, \capleq)

Definition 2.34. The subset of Causable Events EC={e∣C⪯κ(e)}\Events_{\Cau} = \left\lbrace e \mid \Cau \capleq \kappa(e) \right\rbrace consists of all event names which can be caused by the enforcer, i.e. which have a capability of at least C\Cau.

Definition 2.35. The subset of Suppressable Events ES={e∣S⪯κ(e)}\Events_{\Sup} = \left\lbrace e \mid \Sup \capleq \kappa(e) \right\rbrace consists of all event names which can be suppressed by the enforcer, i.e. which have a capability of at least S\Sup.

Definition 2.36. The set of Causable Databases DBC\Databases_\Cau contains all sets of events that are at least causable. DBC={D∈DB∣∀e(tˉ)∈D. e∈EC}\Databases_\Cau = \left\{ D \in \Databases \mid \forall e\left( \bar{t} \right) \in D. \ e \in \Events_\Cau \right\}

Definition 2.37. The set of Suppressable Databases DBS\Databases_\Sup contains all sets of events that are at least suppressable. DBS={D∈DB∣∀e(tˉ)∈D. e∈ES}\Databases_\Sup = \left\{ D \in \Databases \mid \forall e\left( \bar{t} \right) \in D. \ e \in \Events_\Sup \right\}

On the basis of capabilities Hublet, Lima et al. [9, 10] introduce a subset of MFOTL formulae that is enforceable. The typing rules for this subset are shown in Figure 2.6. These rules rely on the concept of past-guardedness, specifically for the suppressability of existential quantifiers. Past-guardedness means that all possible valuations of a variable in the past are known. The rules for past-guardedness are shown in Figure 2.5.

The signature Σ\Sigma of Example 2.2 could be extended with the following capabilities: κ(sendEmail)=CSκ(giveEmailConsent)=Oκ(revokeEmailConsent)=O.\begin{aligned} &\kappa(\mathsf{sendEmail}) &= \Cau \Sup \\ &\kappa(\mathsf{giveEmailConsent}) &= \Obs \\ &\kappa(\mathsf{revokeEmailConsent}) &= \Obs. \end{aligned} These capabilities capture, that an enforcer can both send and prevent the sending of emails, but it cannot change the consent given or revoked by a user.

      γ⊢e(…,x,… ):PGE(x)+   EPG+  γ⊢φ:PGE(x)¬p    γ⊢¬φ:PGE(x)p   ¬PG  x≠zγ⊢φ:PGE(z)p    γ⊢∃x. φ:PGE(z)p   ∃PG  γ⊢φ:PGE(x)+    γ⊢φ∧ψ:PGE(x)+   ∧PGL+  γ⊢ψ:PGE(x)+    γ⊢φ∧ψ:PGE(x)+   ∧PGR+  γ⊢φ:PGE(x)−γ⊢ψ:PGE(x)−    γ⊢φ∧ψ:PGE(x)−   ∧PG−  0∉Iγ⊢φ:PGE(x)+    γ⊢φSIψ:PGE(x)+   SPGL+  γ⊢ψ:PGE(x)+    γ⊢φSIψ:PGE(x)+   SPGR+  0∈Iγ⊢ψ:PGE(x)−    γ⊢φSIψ:PGE(x)−   SPG−  0∉Iγ⊢φ:PGE(x)+    γ⊢φUIψ:PGE(x)+   UPGL+  γ⊢φ:PGE(x)+γ⊢ψ:PGE(x)+    γ⊢φUIψ:PG(Ex)+   UPGLR+  0∈Iγ⊢ψ:PGE(x)−    γ⊢φUIψ:PGE(x)−   UPG−  γ⊢φ:PGE(x)+    γ⊢∙Iφ:PGE(x)+   ∙PG+  γ((e,i))=E    γ⊢e(x1,…,xi=x,…,xk):PGEp(x)   γPG  ∀i. γ⊢φ1:PGEip(xi)γ,(e,1):E1,…,(e,k):Ek⊢φ2:PGEp(x)    γ⊢let⁡e(x1,…,xk)=φ1inφ2:PGEp(x)   letPG\begin{gathered} \prfrule{$\Events^+_\PG$}{}{\gamma \vdash e(\dots, x, \dots) : \PG_E(x)^+} \quad \prfrule{$\neg_\PG$}{\gamma \vdash \phi : \PG_E(x)^{\neg p}}{\gamma \vdash \neg \phi : \PG_E(x)^p} \\[1.1em] \prfrule{$\exists_\PG$}{x \neq z \quad \gamma \vdash \phi : \PG_E(z)^p}{\gamma \vdash \exists x .~ \phi : \PG_E(z)^p} \quad \prfrule{$\wedge_\PG^{\Left+}$}{\gamma \vdash \phi : \PG_E(x)^+}{\gamma \vdash \phi \wedge \psi : \PG_E(x)^+} \\[1.1em] \prfrule{$\wedge_\PG^{\Right+}$}{\gamma \vdash \psi : \PG_E(x)^+}{\gamma \vdash \phi \wedge \psi : \PG_E(x)^+} \quad \prfrule{$\wedge_\PG^-$}{\gamma \vdash \phi : \PG_E(x)^- \quad \gamma \vdash \psi : \PG_E(x)^-}{\gamma \vdash \phi \wedge \psi : \PG_E(x)^-} \\[1.1em] \prfrule{$\Since_\PG^{\Left+}$}{0 \notin I \quad \gamma \vdash \phi : \PG_E(x)^+}{\gamma \vdash \phi \Since_I \psi : \PG_E(x)^+} \quad \prfrule{$\Since_\PG^{\Right+}$}{\gamma \vdash \psi : \PG_E(x)^+}{\gamma \vdash \phi \Since_I \psi : \PG_E(x)^+} \\[1.1em] \prfrule{$\Since_\PG^-$}{0 \in I \quad \gamma \vdash \psi : \PG_E(x)^-}{\gamma \vdash \phi \Since_I \psi : \PG_E(x)^-} \quad \prfrule{$\UUntil_\PG^{\Left+}$}{0 \notin I \quad \gamma \vdash \phi : \PG_E(x)^+}{\gamma \vdash \phi \UUntil_I \psi : \PG_E(x)^+} \\[1.1em] \prfrule{$\UUntil_\PG^{\LeftRight+}$}{\gamma \vdash \phi : \PG_E(x)^+ \quad \gamma \vdash \psi : \PG_E(x)^+}{\gamma \vdash \phi \UUntil_I \psi : \PG(_Ex)^+} \quad \prfrule{$\UUntil_\PG^-$}{0 \in I \quad \gamma \vdash \psi : \PG_E(x)^-}{\gamma \vdash \phi \UUntil_I \psi : \PG_E(x)^-} \\[1.1em] \prfrule{$\Prev_\PG^+$}{\gamma \vdash \phi : \PG_E(x)^+}{\gamma \vdash \Prev_I \phi : \PG_E(x)^+} \qquad \prfrule{$\gamma_\PG$}{\gamma((e,i))=E}{\gamma \vdash e(x_1,\dots,x_i=x,\dots,x_k) : \PG_E^p(x)} \\[1.1em] \prfrule{$\mathsf{let}_\PG$}{\forall i.~\gamma \vdash \phi_1 :\PG^p_{E_i}(x_i) \quad \gamma, (e,1) : E_1,\dots, (e,k):E_k \vdash \phi_2 : \PG^p_{E}(x)}{\gamma \vdash \LLet{e(x_1,\dots,x_k)}{\phi_1}{\phi_2}:\PG^p_{E}(x)} \end{gathered}

Fig 2.5Past-Guardedness Rules

      Γ⊢⊤:C   ⊤C      Γ⊢⊥:S   ⊥S  e∈CΓ(e)=C    Γ⊢e(t1,…,tk):C   EC  e∈SΓ(e)=S    Γ⊢e(t1,…,tk):S   ES  Γ⊢φ:S    Γ⊢¬φ:C   ¬C  Γ⊢φ:C    Γ⊢¬φ:S   ¬S  Γ⊢φ:C    Γ⊢∃x. φ:C   ∃C  Γ⊢φ:S⊢φ:PG(x)+    Γ⊢∃x. φ:S   ∃S  Γ⊢φ:CΓ⊢ψ:C    Γ⊢φ∧ψ:C   ∧C  Γ⊢φ:S    Γ⊢φ∧ψ:S   ∧SL  Γ⊢ψ:S    Γ⊢φ∧ψ:S   ∧SR  0∈IΓ⊢ψ:C    Γ⊢φSIψ:C   SC  0∉IΓ⊢φ:S    Γ⊢φSIψ:S   SSL  0∈IΓ⊢φ:SΓ⊢ψ:S    Γ⊢φSIψ:S   SSLR  Γ⊢ψ:S    Γ⊢φUIψ:S   US  b≠∞Γ⊢ψ:C    Γ⊢φU[0,b]ψ:C   UCR  b≠∞Γ⊢φ:CΓ⊢ψ:C    Γ⊢φU[a,b]ψ:C   UCLR  Γ⊢φ:Cb>0    Γ⊢∘[0,b)φ:C   ∘C  Γ⊢φ:S    Γ⊢∘Iφ:S   ∘S  Γ⊢φ1:τ1Γ,e:τ1⊢φ2:τ2    Γ⊢let⁡e(t‾)=φ1inφ2:τ2   let\begin{gathered} \prfrule{$\top^\Cau$}{}{\Gamma \vdash \top : \Cau} \quad \prfrule{$\bot^\Sup$}{}{\Gamma \vdash \bot : \Sup} \quad \prfrule{$\Events^\Cau$}{e \in \Cau \quad \Gamma(e) = \Cau}{\Gamma \vdash e(t_1,\dots,t_k) : \Cau} \\[1.1em] \prfrule{$\Events^\Sup$}{e \in \Sup \quad \Gamma(e) = \Sup}{\Gamma \vdash e(t_1,\dots,t_k) : \Sup} \quad \prfrule{$\neg^\Cau$}{\Gamma \vdash \phi : \Sup}{\Gamma \vdash \neg \phi : \Cau} \quad \prfrule{$\neg^\Sup$}{\Gamma \vdash \phi : \Cau}{\Gamma \vdash \neg \phi : \Sup} \\[1.1em] \prfrule{$\exists^\Cau$}{\Gamma \vdash \phi : \Cau}{\Gamma \vdash \exists x.~\phi : \Cau} \quad \prfrule{$\exists^\Sup$}{\Gamma \vdash \phi : \Sup \quad \vdash \phi : \PG(x)^+}{\Gamma \vdash \exists x.~\phi : \Sup} \quad \prfrule{$\wedge^\Cau$}{\Gamma \vdash \phi : \Cau \quad \Gamma \vdash \psi : \Cau}{\Gamma \vdash \phi \wedge \psi : \Cau} \\[1.1em] \prfrule{$\wedge^{\Sup\Left}$}{\Gamma \vdash \phi : \Sup}{\Gamma \vdash \phi \wedge \psi : \Sup} \quad \prfrule{$\wedge^{\Sup\Right}$}{\Gamma\vdash \psi : \Sup}{\Gamma \vdash \phi \wedge \psi : \Sup} \quad \prfrule{$\Since^\Cau$}{0 \in I \quad \Gamma \vdash \psi : \Cau}{\Gamma \vdash \phi \Since_I \psi : \Cau} \\[1.1em] \prfrule{$\Since^{\Sup\Left}$}{0 \notin I \quad \Gamma \vdash \phi : \Sup}{\Gamma \vdash \phi \Since_{I} \psi : \Sup} \quad \prfrule{$\Since^{\Sup\LeftRight}$}{0 \in I \quad \Gamma \vdash \phi : \Sup \quad \Gamma \vdash \psi : \Sup}{\Gamma \vdash \phi \Since_I \psi : \Sup} \\[1.1em] \prfrule{$\UUntil^\Sup$}{\Gamma \vdash \psi : \Sup}{\Gamma \vdash \phi \UUntil_I \psi : \Sup} \quad \prfrule{$\UUntil^{\Cau\Right}$}{b \neq \infty \quad \Gamma \vdash \psi : \Cau}{\Gamma \vdash \phi \UUntil_{[0,b]} \psi : \Cau} \\[1.1em] \prfrule{$\UUntil^{\Cau\LeftRight}$}{b \neq \infty \quad \Gamma\vdash \phi : \Cau \quad \Gamma \vdash \psi : \Cau}{\Gamma \vdash \phi \UUntil_{[a,b]} \psi : \Cau} \quad \prfrule{$\Next^\Cau$}{\Gamma \vdash \phi : \Cau \quad b > 0}{\Gamma \vdash \Next_{[0,b)} \phi : \Cau} \\[1.1em] \prfrule{$\Next^\Sup$}{\Gamma \vdash \phi : \Sup}{\Gamma \vdash \Next_I \phi : \Sup} \qquad \prfrule{$\mathsf{let}$}{\Gamma \vdash \phi_1 : \tau_1 \quad \Gamma, e : \tau_1 \vdash \phi_2 : \tau_2}{\Gamma \vdash \LLet{e(\overline{t})}{\phi_1}{\phi_2} : \tau_2} \end{gathered}

Fig 2.6EMFOTL Typing Rules

Constitutive, Regulative, and Exception Rules

Introduction

Hublet et. al [12] introduce a meta-logic based on constitutive, regulative, and exception rules (CRE meta-logic). The CRE meta-logic underpins the Lex programming language and formalizes how a Lex specification would compiles to an MFOTL formula.

Definition 2.38. The set of rule labels is denoted by R\RLabels.

Definition 2.39. A CRE[MFOTL] Signature is a quadruple of the following form Σ′=(D,E∪E′,F,ι∪ι′).\Sigma' = ( \Domain, \Events \cup \Events', \Functions, \iota \cup \iota' ). Where D\Domain is a domain of values, E\Events is a set of external event names, E′\Events' is a set of internal event names, F\Functions is a set of function names, ι:E∪F→N\iota: \Events \cup \Functions \to \Nat is an external arity funciton, and ι′:E′→N\iota': \Events' \to \Nat is an internal arity function. E\Events and E′\Events' are disjoint.

CRE[MFOTL] signatures are very similar to MFOTL signatures, but include the addition of internal events. While it is useful to distinguish between internal and external events, in CRE[MFOTL] and later in Lex, a CRE[MFOTL] signature can still be used as an MFOTL signature. Therefore the next definition deifnes the set of valid MFOTL formulae over a CRE[MFOTL] signature.

Definition 2.40. The set of all MFOTL formulae over a CRE[MFOTL] signature Σ′\Sigma' is denoted by F\formulae.

Next we recall constitutive, regulative, and exception rules [12, Section 3.1].

Table 2.1CRE[MFOTL] Rule Types
Rule Type Syntax Meaning
Constitutive r:φ⇒e(xˉ)r: \phi \Rightarrow e(\bar{x}) "φ\phi counts as e(xˉ)e(\bar{x})"
Regulative r:φ⇒ψr: \phi \Rightarrow \psi "if φ\phi holds, then ψ\psi must hold"
Exception r:φ⇒exc(s)r: \phi \Rightarrow \exc(s) "if φ\phi holds, then rule ss shall not apply"

Definition 2.41. Let r,s∈Rr,s \in \RLabels, φ,ψ∈F\phi, \psi \in \formulae, e∈E′e \in \Events', x1,…,xι′(e)∈Dx_1, \dots, x_{\iota'(e)} \in \Domain, and xˉ=(x1,…,xι′(e))\bar{x} = (x_1, \dots, x_{\iota'(e)}). Table 2.1 gives an overview over the three rule types, their syntax, and their meaning.

Definition 2.42. A CRE Policy is a triple Φ=(C,R,E)\Phi = \left(C, R, E\right) where CC is a set of constitutive rules, RR is a set of regulative rules, and EE is a set of exception rules such that every rule in C∪R∪EC \cup R \cup E has a unique label.

γ⊨Φpiff r:φ⇒p∈C and γ⊨Φφ∧¬exc(r)[reg]γ⊨Φcomply(r)iff r:φ⇒ψ∈R and γ⊨Φ(φ→ψ)∨exc(r)[exc]γ⊨Φexc(s)iff r:φ⇒exc(s)∈E and γ⊨Φφ∧¬exc(r)\begin{aligned} && \gamma &\vDash^\Phi p && \text{iff } r:\phi \Rightarrow p \in C \text{ and }\gamma \vDash^\Phi \phi \wedge \neg \exc(r) \\ [\textsc{reg}] && \gamma &\vDash^\Phi \comply(r) && \text{iff } r:\phi \Rightarrow \psi \in R \text{ and }\gamma \vDash^\Phi (\phi \to \psi) \vee \exc(r)\\ [\textsc{exc}] && \gamma &\vDash^\Phi \exc(s) && \text{iff } r:\phi \Rightarrow \exc(s) \in E \text{ and }\gamma \vDash^\Phi \phi \wedge \neg \exc(r) \end{aligned}

Fig 2.7Semantics of CRE for a fixed structure [12, Figure 5]

Figure 2.7 defines the semantics of the CRE[MFOTL] logic. The semantics expand the logic of F\formulae the CRE[MFOTL] logic is captured by γ⊨φ\gamma \vDash \phi. These semantics can be expanded to define compliance for an entire CRE-policy as followed.

Definition 2.43. A CRE-policy Φ=(C,R,R)\Phi = \left(C,R,R \right) is complied with (γ⊨Φ\gamma \vDash \Phi), if all its regulative rules are complied with, which is captured in the rule:   ∀r:φ⇒ψ∈R. comply(r)    γ⊨Φ   CRE-Compliance\prfrule{CRE-Compliance}{\forall r: \phi \Rightarrow \psi \in R.\ \comply(r)}{\gamma \vDash \Phi}

Definition 2.44. A CRE Specification S=(Σ,φ,κ)\Specification = \left(\Sigma, \phi, \kappa \right) is a triple consisting of some signature Σ=(D,E,F,ι)\Sigma = \left(\Domain, \Events, \Functions, \iota \right), some CRE policy Φ=(C,R,E)\Phi = \left(C, R, E\right), and a capability-mapping κ\kappa.

Analogous to EMFOTL, Hublet et al. [12] define enforceable CRE (ECRE) via the typing rules in Figure 2.8

Example 2.45. The MFOTL policy Φ\Phi of Example 2.23 could be captured in the following CRE[MFOTL] policy:

C={r:sendEmail(user,"marketing")⇒(¬revokeEmailConsent(user,"marketing"))S[0,∞)giveEmailConsent(user,"marketing")}R=∅E=∅\begin{aligned} C &= \{ r : \mathsf{sendEmail}(\mathsf{user}, \text{"marketing"}) \Rightarrow \\ &\qquad (\neg \mathsf{revokeEmailConsent}(\mathsf{user}, \text{"marketing"})) \\ & \qquad \qquad \Since_{[0,\infty)} \mathsf{giveEmailConsent}(\mathsf{user}, \text{"marketing"}) \} \\ R &= \emptyset \\ E &= \emptyset \end{aligned} Φ:=(C,R,E)\Phi := (C,R,E) is a CRE[MFOTL] policy consisting of a single regulative rule rr.

  r:φ⇒ψ∈Rx‾=fv(φ)∪fv(ψ)Γ⊢Φ□⁡(∀x‾. φ→ψ):C    Γ⊢Φcomply(r):C   regI  r:φ⇒ψ∈Rx‾=fv(φ)∪fv(ψ)Γ⊢Φ□⁡(∀x‾. φ∧¬ψ→exc(r)):C    Γ⊢Φcomply(r):C   regE  r:φ⇒exc(s)∈EΓ⊢Φφ:CΓ⊢Φexc(r):S    Γ⊢Φexc(s):C   excC  ∀r:φ⇒exc(s)∈E. (Γ⊢Φφ:S or Γ⊢Φexc(r):C)    Γ⊢Φexc(s):S   excS  r:φ⇒p∈CΓ⊢Φφ:CΓ⊢Φexc(r):S    Γ⊢Φp:C   conC  ∀r:φ⇒p∈C. (Γ⊢Φφ:S or Γ⊢Φexc(r):C)    Γ⊢Φp:S   conS\begin{gathered} \prfrule{\textsc{regI}}{r : \phi \Rightarrow \psi \in R \quad \overline{x}=\fv(\phi) \cup \fv(\psi) \quad \Gamma \vdash^\Phi \Always (\forall \overline{x}.~\phi \rightarrow \psi) : \Cau}{\Gamma \vdash^\Phi \comply(r) : \Cau} \\[1.1em] \prfrule{\textsc{regE}}{r : \phi \Rightarrow \psi \in R \quad \overline{x}=\fv(\phi) \cup \fv(\psi) \quad \Gamma \vdash^\Phi \Always (\forall \overline{x}.~\phi \land \neg \psi \rightarrow \exc(r)) : \Cau}{\Gamma \vdash^\Phi \comply(r) : \Cau} \\[1.1em] \prfrule{$\textsc{exc}^\Cau$}{r : \phi \Rightarrow \exc(s) \in E \quad \Gamma \vdash^\Phi \phi : \Cau \quad \Gamma \vdash^\Phi \exc(r) : \Sup}{\Gamma \vdash^\Phi \exc(s) : \Cau} \\[1.1em] \prfrule{$\textsc{exc}^\Sup$}{\forall r : \phi \Rightarrow \exc(s) \in E.~ (\Gamma \vdash^\Phi \phi : \Sup~\mathbf{or}~\Gamma \vdash^\Phi \exc(r) : \Cau)}{\Gamma \vdash^\Phi \exc(s) : \Sup} \\[1.1em] \prfrule{$\textsc{con}^\Cau$}{r : \phi \Rightarrow p \in C \quad \Gamma \vdash^\Phi \phi : \Cau \quad \Gamma \vdash^\Phi \exc(r) : \Sup}{\Gamma \vdash^\Phi p : \Cau} \\[1.1em] \prfrule{$\textsc{con}^\Sup$}{\forall r : \phi \Rightarrow p \in C.~ (\Gamma \vdash^\Phi \phi : \Sup~\mathbf{or}~\Gamma \vdash^\Phi \exc(r) : \Cau)}{\Gamma \vdash^\Phi p : \Sup} \end{gathered}

Fig 2.8Typing rules for ECRE[MFOTL] policies [12, Figure 6]

Compilation of CRE[MFOTL] to MFOTL

This section recalls the compilation algorithm of CRE[MFOTL] to Lex as it is introduced in Hublet et al. [12, Section 3.2]. Hublet et al. [12] define the following dependency relation between constitutive and exception rules analogous to Merigoux et al. [15, Section 4.1].

Definition 2.46. For a CRE[MFOTL] Policy Φ:=(C,R,E)\Phi := (C,R,E) let r,s∈C∪Er,s \in C \cup E. r▹Φsr \triangleright_\Phi s (read as "s depends on r") iff either r:φ⇒p∈Cr:\phi \Rightarrow p \in C and pp occurs in the left-hand side of the rule ss, or r:φ⇒exc(s)∈Er:\phi \Rightarrow \exc(s) \in E.

A policy (C,R,E)(C,R,E) is called acyclic iff there do not exist two rules r,s∈C∪Er,s \in C \cup E such that r▹Φsr \triangleright_\Phi s, and s▹Φrs \triangleright_\Phi r and also that there is no single rule r∈C∪Er \in C \cup E that is self-referential (i.e. r▹Φrr \triangleright_\Phi r). The compilation of CRE[MFOTL] to MFOTL is defined by Algorithm 2 and Algorithm 3.

Algorithm 2CRE[MFOTL] to MFOTL compilation [12, Algorithm 1]
  1. Input: S=(Σ,Φ,κ)\mathcal{S}=(\Sigma,\Phi,\kappa) with Σ=(D,E,F,ι)\Sigma = (\Domain, \Events, \Functions, \iota) and acyclic CRE[MFOTL] policy Φ=(C,R,E)\Phi=(C,R,E)
  2. EE←{es∣r:φ⇒exc(s)∈E}\Events_E \gets \{ e_s \mid r: \phi \Rightarrow \exc(s) \in E \}
  3. R′←{r:φ∧¬er⇒ψ∣r:φ⇒ψ∈R,er∈EE}∪{r:φ⇒ψ∣r:φ⇒ψ∈R,er∉EE}R' \gets \{ r: \phi \land \neg e_r \Rightarrow \psi \mid r: \phi \Rightarrow \psi \in R, e_r \in \Events_E \} \cup \{ r: \phi \Rightarrow \psi \mid r: \phi \Rightarrow \psi \in R, e_r \notin \Events_E \}
  4. CE←{r:φ⇒es∣r:φ⇒exc(s)∈E}C_E \gets \{ r: \phi \Rightarrow e_s \mid r: \phi \Rightarrow \exc(s) \in E \}
  5. E0←{p∣p∉E∧e occurs in C∪R∪E}∖{p∣r:φ⇒p∈C}\Events_0 \gets \{ p \mid p \not\in \Events \land e \text{ occurs in } C \cup R \cup E \} \setminus \{ p \mid r: \phi \Rightarrow p \in C\}
  6. C0←{zp:⊥⇒p∣p∈E0}C_0 \gets \{ z_p: \bot \Rightarrow p \mid p \in \Events_0 \}
  7. C′←C∪CE∪C0C' \gets C \cup C_E \cup C_0
  8. C′←{r:φ∧¬er⇒p∣r:φ⇒p∈C′,er∈EE}∪{r:φ⇒p∣r:φ⇒p∈R,er∉EE}C' \gets \{ r: \phi \land \neg e_r \Rightarrow p \mid r: \phi \Rightarrow p \in C', e_r \in \Events_E \} \cup \{ r: \phi \Rightarrow p \mid r: \phi \Rightarrow p \in R, e_r \notin \Events_E \}
  9. [(φ1,p1),…,(φk,pk)]←collect(topological_sort▹Φ(C′))[(\phi_1, p_1),\dots, (\phi_k, p_k)] \gets \textsf{\textsc{collect}}(\textsf{\textsc{topological\_sort}}_{\triangleright_\Phi}(C'))
  10. for r:φ⇒ψ∈R′r : \phi \Rightarrow \psi \in R' do x‾r←free_variables(φ→ψ)\overline{x}_r \gets \mathsf{free\_variables}(\phi \rightarrow \psi) endfor
  11. φ←let⁡p1=φ1in…let⁡pk=φkin⋀r:φ⇒ψ∈R′(□⁡(∀x‾r. φ→ψ))\phi \gets \LLet{p_1}{\phi_1}{\dots\LLet{p_k}{\phi_k}{\bigwedge_{r: \phi \Rightarrow \psi \in R'}(\Always(\forall \overline{x}_r.~ \phi \to \psi))}}
  12. Output: S′=(Σ′,φ,κ)\mathcal{S}'=(\Sigma',\phi,\kappa) where Σ′=(D,E∖{pi∣1≤i≤k},F,ι)\Sigma' = (\Domain, \Events\setminus \{p_i \mid 1 \leq i \leq k\}, \Functions, \iota)
Algorithm 3Auxiliary function collect [12, Algorithm 2]
  1. let collect LL =
  2. P,L′←∅,[]P, L' \gets \emptyset, []
  3. for r:φ⇒p∈Lr : \phi \Rightarrow p \in L do
  4. if p∉Pp \notin P then (P,L′)←(P∪{p},L′⋅[(⋁r:φ⇒p∈Lφ,p)])(P, L') \gets (P \cup \{p\}, L' \cdot [(\bigvee_{r: \phi \Rightarrow p \in L} \phi, p)]) endif
  5. endfor
  6. return L′L'

The Lex Programming Language

Hublet et al. [12] and Degelo [8] developed the Lex programming language based on CRE[MFOTL]. Lex is designed to formalize legal texts and maintain a high readability, especially compared to pure MFOTL. It achieves this readability by maintaining the general structure of the underlying legal text.

Lex Syntax

Lexlaw lbllbl ["title"][τ\tau] event eerule rrrule rrrule rr
article lbllbl ["title"]      """<docstring>"""    whenever    whenever    whenever
paragraph lbllbl…       x1x_1 : t1t_1       φ1\phi_1       φ1\phi_1       φ1\phi_1
point lbllbl…      …       …\dots       …\dots       …\dots
…       xkx_k : tkt_k       φk\phi_k       φk\phi_k       φk\phi_k
τ::=observable\tau::= \htmlClass{tok-kw}{\texttt{observable}}    constitute    oblige    except
type t1t_1 [is t2t_2]      ∣suppressable\mid\htmlClass{tok-kw}{\texttt{suppressable}}       p1p_1       ψ1\psi_1       lbl1lbl_1
      """<docstring>"""      ∣causable ∣internal...\mid\htmlClass{tok-kw}{\texttt{causable}}~\mid\htmlClass{tok-kw}{\texttt{internal}}...       …\dots       …\dots       …\dots
       pℓp_\ell       ψℓ\psi_\ell       lblℓlbl_\ell
CRE[MFOTL]n.a.e∈Ee \in \Eventsr1:⋀1≤i≤kφi⇒p1∈Cr_1: \bigwedge\limits_{1 \leq i \leq k} \phi_i \Rightarrow p_1 \in Cr1:⋀1≤i≤kφi⇒ψ1∈Rr_1: \bigwedge\limits_{1 \leq i \leq k} \phi_i \Rightarrow \psi_1 \in Rr1:⋀1≤i≤kφi⇒exc(s1)∈Er_1: \bigwedge\limits_{1 \leq i \leq k} \phi_i \Rightarrow \exc(s_1) \in E
ι(e)=(t1,…,tk)\iota(e)=(t_1, \dots, t_k)………
κ(e)=O,S,C...\kappa(e)=\Obs,\Sup,\Cau...rk:⋀1≤i≤kφℓ⇒pℓ∈Cr_k: \bigwedge\limits_{1 \leq i \leq k} \phi_\ell\Rightarrow p_\ell \in Crk:⋀1≤i≤kφℓ⇒ψℓ∈Rr_k: \bigwedge\limits_{1 \leq i \leq k} \phi_\ell\Rightarrow \psi_\ell \in Rrk:⋀1≤i≤kφℓ⇒exc(sℓ)∈Er_k: \bigwedge\limits_{1 \leq i \leq k} \phi_\ell\Rightarrow \exc(s_\ell) \in E
Fig 2.9Correspondence between the Lex and CRE[MFOTL] syntax [12, Figure 10]

Lex has the following main types of statements:

Figure 2.9 shows the correspondence between Lex and CRE[MFOTL].

Lex Section Labels

The Lex language provides a fixed set of section label keywords: law, title, chapter, section, article, paragraph, point, subpoint. Not every law will have all of these hierarchical levels, and besides law and article they are all optional. If a law contains a hierarchical level that does not fit into these predifined keywords, custom sub-levels can be defined underneath one of the predifined ones (e.g. article[1] is a level below an article, but above a paragraph; This has the consequence that article is implicitly equivalent to article[0]). As an example, a law might be the GDPR, which is further divided into chapters and chapters then contain individual articles. Another example would be the Swiss constitution as a law, which is divided into titles. While often times sections, titles, articles, etc. will be numbered, in Lex they are refered to by strings. This is due to the fact that no standard numbering scheme exists, sometimes articles will contain letters like Article 1b, and other times Roman numerals might be used. One interesting aspect of laws across contexts is that articles tend to be numbered continuously, i.e. in the GDPR one doesn’t need to know in which Chapter an article is located, to uniquely refer to it.

References to other parts of a Lex specification can always be made by stating all levels can always be made by giving the full path consisting of all intermediate levels. Due to the continuous (and thus unique) numbering of articles, for sections below the article level, it is not necessary to include any levels between law and article. Lex will also try to resolve references dynamically, e.g. if article "2" is used in article "1", Lex will attempt to resolve this reference inside the same law.

Lex - E-Mail Marketing Example

This subsection will showcase the Lex language on a hands on example. Chapter 4 will continue this example to showcase how a Lex specification can be refined. The example is based on the ePrivacy Directive of the European Union. Specifically we focus on Article 13 of the ePrivacy Directive. This article regulates the use of electronic communication, automated calls, fax, and e-mail for marketing purposes.

Art. 13 ePrivacy Directive . Unsolicited communications

  1. The use of automated calling systems without human intervention (automatic calling machines), facsimile machines (fax) or electronic mail for the purposes of direct marketing may only be allowed in respect of subscribers who have given their prior consent.

  2. Notwithstanding paragraph 1, where a natural or legal person obtains from its customers their electronic contact details for electronic mail, in the context of the sale of a product or a service, in accordance with Directive 95/46/EC, the same natural or legal person may use these electronic contact details for direct marketing of its own similar products or services provided that customers clearly and distinctly are given the opportunity to object, free of charge and in an easy manner, to such use of electronic contact details when they are collected and on the occasion of each message in case the customer has not initially refused such use.

  3. Member States shall take appropriate measures to ensure that [...] unsolicited communications for purposes of direct marketing, in cases other than those referred to in paragraphs 1 and 2, are not allowed [...]

  4. In any event, [...] disguising or concealing the identity of the sender [...] shall be prohibited.

  5. Paragraphs 1 and 3 shall apply to subscribers who are natural persons. Member States shall also ensure, [...] that the legitimate interests of subscribers other than natural persons with regard to unsolicited communications are sufficiently protected.

Fig 2.10Text of Article 13 of the ePrivacy Directive [1]
law "EPD"

type productCategory is string

internal event automatedCommunication
    """persso {s} sends automated commmunication to person {r} for purpose {p} about category {c}"""
    s: person
    r: person
    p: purpose
    c: productCategory

causable suppressable event automatedCall
    """person {s} calls person {r} for purpose {p} about category {c}"""
    r: person 
    s: person
    p: purpose
    c: productCategory

causable suppressable event fax
    """persen {s} faxes person {r} for purpose {p} about category {c}"""
    r: person 
    s: person
    p: purpose
    c: productCategory

causable suppressable event email
    """person {s} emails person {r} for purpose {p} about category {c}"""
    r: person 
    s: person
    p: purpose
    c: productCategory

observable event obtainedEmailForCategory
    """person {r} obtained the email address of person {s} for category {c}"""
    r: person
    s: person
    c: productCategory

observable event marketingConsent
    """person {s} gave prior consent for receiving marketing communication from person {r}"""
    r: person
    s: person

observable event objectToSimilarEmailMarketing
    """person {r} objected to receiving marketing emails from person {s} about category {c}"""
    r: person
    s: person
    c: productCategory
type person
type purpose is string

observable event isNaturalPerson
    """person {s} is a natural person"""
    s: person

rule "automated call communication"
    whenever
        automatedCall(s, r, p, c)
    constitute
        automatedCommunication(s, r, p, c)

rule "fax communication"
    whenever
        fax(s, r, p, c)
    constitute
        automatedCommunication(s, r, p, c)

rule "email communication"
    whenever
        email(s, r, p, c)
    constitute
        automatedCommunication(s, r, p, c)


article "13" "Unsolicited communications"
paragraph "1"

rule "marketing consent requirement"
    whenever
        automatedCommunication(s, r, "marketing", c)
    oblige
        marketingConsent(r, s)
    enforceable suppressing automatedCommunication

paragraph "2"

rule "marketing of similar products or services"
    whenever
        obtainedEmailForCategory(r, s, c)
        NOT objectToSimilarEmailMarketing(r, s, c)
    except
        article "13" paragraph "1"

paragraph "3"
paragraph "4"
paragraph "5"

rule 
    whenever
        isNaturalPerson(r)
    scope
        article "13" paragraph "1"
        article "13" paragraph "3"
Fig 2.11Lex formalization of Article 15(1), 15(2) and 15(5) of the ePrivacy Directive

Figure 2.11 shows one way that Article 13 could be formalized in Lex. It defines three data types, person, purpose, and productCategory to represent the involved parties: person to represent both legal and natural persons, purpose to represent the purpose of the communication, and productCategory to represent the category of the product or service.

Next it specifies one internal event for automated communication and three causable and suppressable events for the three different types of automated communication (automated calls, faxes, and e-mails), mentionend in the directive. Via three constitutive rules, these concrete events do then constitute the internal event automatedCommunication.

After this the logical structure of Article 13 is formalized into three rules. It requires some interpretation to determine which parts can and should be formalized. Paragraph 3 is fairly general and does not directly specify any concrete rule. Paragraph 4 does state a concrete rule ("one shall not disguise one’s identity"), however it can be a reasonable assumption to leave this honesty requirement to the system itself and enforce it with an enforcer. Finally, paragraph 5 restricts the scope of Paragraphs 1 and 3 to be only applicable to natural persons. As Article 13 stems from an EU directive, national implementations may differ. These differences, though relevant, are beyond the scope of this thesis.

Therefore, we are left with paragraphs 1, 2, and 5. Paragraph 1 contains a simple obligation that a person, likely a business, can only send marketing communication to a user, if the user gave consent for receiving such communication. And paragraph 2 states an exception to paragraph 1, where the business does not need explicit consent, as long as the contact information was obtained for a similar product or service, the user has not objected to receiving such communication, and the marketing for a product or service belonging to the sender. Paragraph 5 can be neatly formalized with a scope rule. A scope rule could be converted into an exception by negating the conditions.

Event Systems

Sprenger et al. [17] defines event systems in the following way.

Definition 2.47. An Event System is a labeled transition system Ξ=(S,E,→)\EventSystem = \left(\Statespace, \Eventspace, \Transitionrelation{}{} \right) consisting of a set of states S\Statespace, a set of events E\Eventspace, and a transition relation →⊆S×E×S\Transitionrelation{}{} \subseteq \Statespace \times \Eventspace \times \Statespace.

(s,e,s′)∈→(s,e,s') \in \Transitionrelation{}{} can also be written as s→es′s \Transitionrelation{}{e} s'. Sprenger et. al [17] extend the transition relation for finite traces of events τ\tau. As we already use τ\tau for timestamps and σ\sigma for MFOTL traces, we use σ\sigma for event traces and ε\emptytrace denotes an empty trace. The extension of the transition relation is explained in the following definition.

Definition 2.48. The transition relation is inductively expanded for finite traces σ\sigma of events S\Statespace for all s,s′,s′′∈Ss,s',s'' \in \Statespace s→εss→σ⋅⟨e⟩s′whenever s→σs′ and s′→es′′\begin{align} s &\Transitionrelation{}{\emptytrace} s \tag{2.1} \\ s &\Transitionrelation{}{\sigma \cdot \left\langle e \right\rangle} s' && \text{whenever } s \Transitionrelation{}{\sigma} s' \text{ and } s' \Transitionrelation{}{e} s'' \tag{2.2}\end{align}

Next we recall the trace definition for event systems from Sprenger et. al [17].

Definition 2.49. The set of Initial States is a subset I⊆S\Initialstates \subseteq \Statespace.

Definition 2.50. Given a set of initial states I⊆S\Initialstates \subseteq \Statespace a Trace of the event system Ξ=(S,E,→)\EventSystem = \left(\Statespace, \Eventspace, \Transitionrelation{}{} \right) starting in initial states I\Initialstates is a trace σ\sigma of events such that s→ρs′s \Transitionrelation{}{\rho} s' for some initial state s∈Is \in \Initialstates and a reachable state s′∈Ss' \in \Statespace.

The set of all traces of an event system Ξ\EventSystem starting in initial states I\Initialstates is denoted by traces(Ξ,I)\EStraces\left(\EventSystem, \Initialstates \right).

Refinement of Event Systems

In this section we recall refinement of event systems as defined in Sprenger et. al [17].

Definition 2.51. Given two event systems Ξi=(Si,Ei,→i)\EventSystem_i = \left( \Statespace_i, \Eventspace_i, \Transitionrelation{i}{} \right) with initial states Ii\Initialstates_i for i∈{1,2}i\in \lbrace1,2\rbrace. (Ξ2,I2)\left(\EventSystem_2, \Initialstates_2 \right) refines (Ξ1,I1)\left(\EventSystem_1, \Initialstates_1 \right) modulo a mediator function π:E2→E1\pi : \Eventspace_2 \to \Eventspace_1, written as (Ξ2,I2)⊑π(Ξ1,I1)\left(\EventSystem_2, \Initialstates_2 \right) \refineL_\pi \left(\EventSystem_1, \Initialstates_1 \right) if there exists a simulation relation R⊆E×ER \subseteq \Eventspace \times \Eventspace such that

  1. for all s2∈I2s_2 \in \Initialstates_2 there exists some s1∈I1s_1 \in \Initialstates_1 such that (s2,s1)∈R(s_2, s_1) \in R, and

  2. for all s1∈S1,s2,s2′∈S2s_1 \in \Statespace_1, s_2, s_2' \in \Statespace_2, and e2∈E2e_2 \in \Eventspace_2 such that s2→e2s2′s_2 \Transitionrelation{}{e_2} s_2' and (s2,s1)∈R(s_2, s_1) \in R there exists some s1′∈S1s_1' \in \Statespace_1 such that s1→π(e2)s1′s_1 \Transitionrelation{}{\pi(e_2)} s_1'.

Sprenger et. al [17, Theorem 2.1] states the following theorem about the relation of traces from event systems that refine each other.

Theorem 2.52. (Ξ2,I2)⊑π(Ξ1,I1)(\EventSystem_2, \Initialstates_2) \refineL_\pi (\EventSystem_1, \Initialstates_1) implies π(traces(Ξ2,I2))⊆traces(Ξ1,I1)\pi(\EStraces(\EventSystem_2, \Initialstates_2)) \subseteq \EStraces(\EventSystem_1, \Initialstates_1)

Proof. Let Ξ1=(S1,E1,→1)\EventSystem_1 = (\Statespace_1, \Eventspace_1, \Transitionrelation{1}{}) and Ξ2=(S2,E2,→2)\EventSystem_2 = (\Statespace_2, \Eventspace_2, \Transitionrelation{2}{}). Let I1⊆S1\Initialstates_1 \subseteq \Statespace_1 and I2⊆S2\Initialstates_2 \subseteq \Statespace_2.

We can prove Theorem 2.52 by structural induction over event system traces. We will show that for every trace σ∈traces(Ξ2,I2)\sigma \in \EStraces(\EventSystem_2, \Initialstates_2) its projection π(σ)\pi(\sigma), is in traces(Ξ1,I1)\EStraces(\EventSystem_1, \Initialstates_1).

  • Base Case: σ=ε∈traces(Ξ2,I2)\sigma = \emptytrace \in \EStraces(\EventSystem_2, \Initialstates_2). The empty trace is part of any event system, and therefore π(σ)=π(ε)=ε∈traces(Ξ1,I1)\pi(\sigma) = \pi(\emptytrace) = \emptytrace \in \EStraces(\EventSystem_1, \Initialstates_1). And further, for any inital state s2∈I2s_2 \in \Initialstates_2 there exists there exists an initial state s1∈I1s_1 \in \Initialstates_1 such that (s2,s1)∈R(s_2, s_1) \in R for which s2→ε2s2s_2 \Transitionrelation{2}{\emptytrace} s_2 and. s1→π(ε)1s1s_1 \Transitionrelation{1}{\pi(\emptytrace)} s_1.

  • Induction Hypothesis For any trace σ=σ′⋅e∈traces(Ξ2,I2)\sigma = \sigma' \cdot e \in \EStraces(\EventSystem_2, \Initialstates_2) with ∣σ∣>∣σ′∣|\sigma| > |\sigma'|, π(σ′)∈traces(Ξ1,I1)\pi(\sigma') \in \EStraces(\EventSystem_1, \Initialstates_1). And there exists an initial state s2∈I2s_2 \in \Initialstates_2, a state s2′∈S2s_2' \in \Statespace_2, an initial state s1∈I1s_1 \in \Initialstates_1, and a state s1′∈S1s_1' \in \Statespace_1 such that (s2,s1)∈R(s_2, s_1) \in R, (s1′,s2′)∈R(s_1', s_2') \in R, s2→σ′2s2′s_2 \Transitionrelation{2}{\sigma'} s_2', and s1→π(σ′)1s1′s_1 \Transitionrelation{1}{\pi(\sigma')} s_1'.

  • Inductive Step: σ∈traces(Ξ2,I2)\sigma \in \EStraces(\EventSystem_2, \Initialstates_2). Since we covered the empty trace in the base case, we have ∣σ∣≥1|\sigma| \geq 1. Thus we can assume that σ=σ′⋅e\sigma = \sigma' \cdot e for some e∈E2e \in \Eventspace_2. By the Induction Hypothesis we have that π(σ′)∈traces(Ξ1,I1)\pi(\sigma') \in \EStraces(\EventSystem_1, \Initialstates_1).

    By the induction hypothesis we have that π(σ′)\pi(\sigma') is a trace of the event system (Ξ1,I1)(\EventSystem_1, \Initialstates_1). Also by induction hypthesis we have that there exist s2∈I2s_2 \in \Initialstates_2, s2′∈S2s_2' \in \Statespace_2, s1∈I1s_1 \in \Initialstates_1, and s1′∈S1s_1' \in \Statespace_1 such that (s2,s1)∈R(s_2, s_1) \in R, (s1′,s2′)∈R(s_1', s_2') \in R, s2→σ′2s2′s_2 \Transitionrelation{2}{\sigma'} s_2', and s1→π(σ′)1s1′s_1 \Transitionrelation{1}{\pi(\sigma')} s_1'. By definition of σ\sigma as σ′⋅e\sigma' \cdot e and the assumption that σ∈traces(Ξ2,I2)\sigma \in \EStraces(\EventSystem_2, \Initialstates_2) we have that s2′→e2s2′′s_2' \Transitionrelation{2}{e} s_2'' for some s2′′∈S2s_2'' \in \Statespace_2. By point 2 of Definition 2.51 we have that there exists a state s1′′∈S1s_1'' \in \Statespace_1 such that s1′→π(e)1s1′′s_1' \Transitionrelation{1}{\pi(e)} s_1''. Thus s1→π(σ′)1s1′→e1s2′′s_1 \Transitionrelation{1}{\pi(\sigma')} s_1' \Transitionrelation{1}{e} s_2'' and also s1→π(σ′)1s1′′s_1 \Transitionrelation{1}{\pi(\sigma')} s_1''.

 ◻

The next definition defines properties over event systems according to Sprenger et. al [17, Section 2.1.1]. It is analogous to the definition of properties over MFOTL traces.

Definition 2.53. A trace property PP is a set of traces over events E\Events.

Ξ⊨P\EventSystem \vDash P denotes that the event system traces(Ξ,I)⊆P\EStraces(\EventSystem, \Initialstates) \subseteq P.

Next we recall Sprenger et. al [17, Lemma 2.2].

Lemma 2.54. Suppose Ξ1,I1⊨P1\EventSystem_1, \Initialstates_1 \vDash P_1 and π(traces(Ξ2,I2))⊆traces(Ξ1,I1)\pi(\EStraces(\EventSystem_2, \Initialstates_2)) \subseteq \EStraces(\EventSystem_1, \Initialstates_1), then Ξ2,I2⊨π−1(P1)\EventSystem_2, \Initialstates_2 \vDash \pi^{-1}(P_1)

Proof. Ξ1,I1⊨P1\EventSystem_1, \Initialstates_1 \vDash P_1 is equivalent to traces(Ξ1,I1)⊆P1\EStraces(\EventSystem_1, \Initialstates_1) \subseteq P_1. Thus π(traces(Ξ2,I2))⊆traces(Ξ1,I1)⊆P1⇒ π−1(π(traces(Ξ2,I2)))⊆π−1(traces(Ξ1,I1))⊆π−1(P1)⇒ traces(Ξ2,I2)⊆π−1(traces(Ξ1,I1))⊆π−1(P1)⇒ traces(Ξ2,I2)⊆π−1(P1).\begin{aligned} &\pi(\EStraces(\EventSystem_2, \Initialstates_2)) \subseteq \EStraces(\EventSystem_1, \Initialstates_1) \subseteq P_1 \\ \Rightarrow~ &\pi^{-1}(\pi(\EStraces(\EventSystem_2, \Initialstates_2))) \subseteq \pi^{-1}(\EStraces(\EventSystem_1, \Initialstates_1)) \subseteq \pi^{-1}(P_1) \\ \Rightarrow~ &\EStraces(\EventSystem_2, \Initialstates_2) \subseteq \pi^{-1}(\EStraces(\EventSystem_1, \Initialstates_1)) \subseteq \pi^{-1}(P_1) \\ \Rightarrow~ &\EStraces(\EventSystem_2, \Initialstates_2) \subseteq \pi^{-1}(P_1). \end{aligned} ◻

A Lex specification represents a formalization of a legal text. Any formalization always includes some level of interpretation. Writing a Lex specification requires to make decisions on which legal concepts are represented as an event, how general should events be, which aspects of the law fit into which kind of CRE rule, etc. Only by carefully auditing and reviewing a Lex specification is there a high certainty that a given specification correctly captures the essence of the law. Because the task of writing such a formalization is inherently difficult, the ability to reuse an existing specification and adapt it with minimal changes to different use cases is highly desirable. This thesis provides one method of achieving this reusability by ways of refinement.

The refinement process arguably includes even more interpretation than the initial formalization. With knowledge about a given system, some aspects of an initial specification might become redundant and others might need to be clarified based on how a system implements certain things. For example, in our ePrivacy Directive example on unsolicited communications, if we know a system never makes calls or uses a fax, rules on limiting the use of calls and fax become unnecessary.

Refinement of CRE Enforcement

Introduction

In this chapter we will introduce a different definition of traces (system traces) and show that, under some conditions, it is isomorph to the (MFOTL) trace definition introduced in chapter 2. We will also define what Refinement for MFOTL formulae as well as Lex specifications. We will show that with our definitions, if a Lex specification A is a refinement of a Lex specification B, then A compiled to MFOTL is an MFOTL refinement of B compiled to MFOTL. We will further introduce a model of runtime enforcement as an event system. This new model will be based on the new trace definition. We will give definitions for soundness and transparency of runtime enforcement event systems. We will show that these definitions are equivalent to those of chapter 2 under the aforementioned isomorphism between system and MFOTL traces. We will adapt the definition of refinement from Sprenger et al. [17] slightly. Specifically, our mediator function will not only rely on an event being reported at a certain point in time, but also the trace (history) of previous events.

We will then go on to show that, whenever there exists a sound enforcement event system for some MFOTL formula φ\phi, and another formula ψ\psi refines φ\phi, then there exists a sound enforcement event system for ψ\psi. Separately we will show that there exists a sound enforcement event system for some MFOTL formula φ\phi if and only if there exists a sound enforcer, as defined in chapter 2 for φ\phi. Hublet et al. [12] have shown that an causable Lex specification compiles to an causable MFOTL formula. And Hublet et al. [9] have shown that if an MFOTL formula is causable, there exists a sound enforcer for it. Putting everything together we will have shown that if a Lex specification A refines an enforceable Lex specification B, then B is enforceable.

Alternative Enforcement Model

System Traces

We introduce a different trace definition as in Definition 2.6 and we will show that this new definition is at least as expressive as the old one. This definition will help us to look at runtime enforcement as an event system in Subsection 3.2.2 that works with traces in this new model. By showing that the two trace definitions are isomorphic, we will be able to show that the two runtime enforcement models are also equivalent. This will tie together the refinement of Lex specifications and in turn of CRE[MFOTL] with the refinement definition of Sprenger et al. [17].

Definition 3.1. A System Sequence σs∈Ss\sigma_\sys \in \SeqSys is a finite or infinite sequence of events ⟨ei⟩1≤i≤k,k∈N∪{∞}\left\langle{e_i}\right\rangle_{1 \leq i \leq k}, k \in \Nat \cup \lbrace \infty \rbrace where for every i∈[1,k]i \in [1, k], ei∈DB∪{tick}.e_i \in \Databases \cup \left\{ \tick \right\}.

The special event tick\tick represents a clock tick in the system. As a more compact notation we use ek:=e⋅…⋅e⏟k timese^k := \underbrace{e \cdot \ldots \cdot e}_{k \text{ times}} for all k∈Nk \in \Nat and e∈DB∪{tick}e \in \Databases \cup \{tick\}. Note that for k=0k=0, ek=εse^k = \emptytrace_\sys.

Definition 3.2. The function

#tick:Ss→N∪{∞}\numTicks : \SeqSys \to \Nat \cup \{ \infty \}

#tick(σs)={kif σs=tickk for k≥0k+#tick(σs′)if σs=tickk⋅D⋅σs′ for k≥0 and D∈DB\begin{aligned} \numTicks(\sigma_\sys) = \begin{cases} k &\text{if } \sigma_\sys = \tick^k \text{ for } k \geq 0 \\ k + \numTicks(\sigma'_\sys) &\text{if } \sigma_\sys = \tick^k \cdot D \cdot \sigma'_\sys \text{ for } k \geq 0 \text{ and } D \in \Databases \end{cases} \end{aligned} gives the number of ticks in a system sequence.

The tick\tick function is useful to determine a timestamp in a system trace, since they are only implicit and not explicit like in MFOTL traces.

Definition 3.3. The function

trim:Ss→Ss\trim: \SeqSys \to \SeqSys

trim(σs):={εsif σs=tickk for k≥0tickk⋅D⋅trim(σs′)if σs=tickk⋅D⋅σs′ for k≥0 and D∈DB\begin{aligned} \trim(\sigma_\sys) := \begin{cases} \emptytrace_\sys &\text{if } \sigma_\sys = \tick^k \text{ for } k \geq 0 \\ \tick^k \cdot D \cdot \trim(\sigma_\sys') &\text{if } \sigma_\sys = \tick^k \cdot D \cdot \sigma_\sys' \text{ for } k \geq 0 \text{ and } D \in \Databases \end{cases} \end{aligned} removes all tick\tick events from the end of a system sequence that are not followed by a database.

For sets of system sequences A⊆SsA \subseteq \SeqSys, trim(A):={trim(σ)∣σ∈A}\trim(A) := \{ \trim(\sigma) \mid \sigma \in A \}.

Definition 3.4. A System Trace σs∈Ts⊆Ss\sigma_\sys \in \Traces_\sys \subseteq \SeqSys is a finite or infinite system sequence where the number of ticks progresses with the number of databases (if #DB(σs)=∞\numDBs(\sigma_\sys) = \infty, then #tick(trim(σs))=∞\numTicks(\trim(\sigma_\sys)) = \infty).

The distinction between system sequences and system traces is made, such that for infinite traces, it is guaranteed that at any point in the trace, there will eventually follow a database event.

Definition 3.5. The function

#DB:Ts→N∪{∞}\numDBs : \Traces_\sys \to \Nat \cup \{ \infty \}

#DB(σs)={0if σs=tickk and k≥01+#DB(σs′)if σs=tickk⋅D⋅σs′ for k≥0 and D∈DB\begin{aligned} \numDBs(\sigma_\sys) = \begin{cases} 0 &\text{if } \sigma_\sys = \tick^k \text{ and } k \geq 0 \\ 1 + \numDBs(\sigma'_\sys) &\text{if } \sigma_\sys = \tick^k \cdot D \cdot \sigma'_\sys \text{ for } k \geq 0 \text{ and } D \in \Databases \end{cases} \end{aligned} gives the number of database events in a system trace.

We say a system trace σs∈Ts\sigma_\sys \in \Traces_\sys is finite iff #DB(σs)∈N\numDBs(\sigma_\sys) \in \Nat and it is infinite iff #DB(σs)=∞\numDBs(\sigma_\sys) = \infty. We use Tsf⊆(DB∪{tick})∗\Traces_{\sys f} \subseteq \left( \Databases \cup \left\{\tick \right\} \right)^*, Tsω⊆(DB∪{tick})∞\Traces_{\sys \omega} \subseteq \left( \Databases \cup \left\{\tick \right\} \right)^\infty, and Ts=Tsf∪Tsω\Traces_\sys = \Traces_{\sys f} \cup \Traces_{\sys \omega} to denote the sets of finite system traces, infinite system traces, and all system traces respectively. εs\emptytrace_\sys denotes an empty system trace.

Lemma 3.6. For any infinite system trace σs∈Tsω\sigma_\sys \in \Traces_{\sys \omega}, σs=trim(σs).\sigma_\sys = \trim(\sigma_\sys).

This follows directly from our definition for infinite system traces. At any point within an infinite trace, there must eventually follow at least one database, because otherwise there would not be an infinite number of databases in the trace. Lemma 3.6 can be rewritten as Tsω=trim(Tsω)\Traces_{\sys \omega} = \trim(\Traces_{\sys \omega}).

Next we define conversion functions between trimmed system traces and MFOTL traces. And then we will show that the conversion functions together define an isomorphism between MFOTL traces and trimmed system traces. The limitation on trimmed system traces is necessary, because MFOTL traces do not capture any timepoints at which no database is logged.

Definition 3.7. The Finite Extended System Trace Converter Function converts system traces starting at some timestamp to MFOTL traces. c′:N×Ts→T\begin{aligned} \cConv': \Nat \times \Traces_\sys \to \Traces \end{aligned}

c′(τ,σs):={εif trim(σs)=0(τ+k,D)⋅c′(τ+k,σs′)if σs=tickk⋅D⋅σs′with k≥0,D∈DB\begin{aligned} \cConv'(\tau, \sigma_\sys) := \begin{cases} \emptytrace & \text{if } \trim(\sigma_\sys) = 0 \\ (\tau + k, D) \cdot \cConv'(\tau+k, \sigma'_\sys) & \text{if } \sigma_\sys = \tick^k \cdot D \cdot \sigma'_\sys \\ & \text{with } k \geq 0, D \in \Databases \\ \end{cases} \end{aligned}

Definition 3.8. The System Trace Converter Function converts system traces starting at timestamp 00 to MFOTL traces.

c:Ts→T\cConv: \Traces_\sys \to \Traces

c(σs):=c′(0,σs).\begin{aligned} \cConv(\sigma_\sys) := \cConv'(0, \sigma_\sys). \end{aligned}

Definition 3.9. The extended MFOTL Trace Converter Function converts MFOTL traces starting at some timestamp to system traces.

d′:N×T→trim(Ts)\begin{aligned} \dConv': \Nat \times \Traces \to \trim(\Traces_\sys) \end{aligned}

d′(τ,σ):={εsif σ=εtickk⋅D⋅d′(τ+k,σ′)if σ=(τ+k,D)⋅σ′with k≥0\begin{aligned} \dConv'(\tau, \sigma) := \begin{cases} \emptytrace_\sys &\text{if } \sigma = \emptytrace \\ \tick^k \cdot D \cdot \dConv'(\tau+k, \sigma') &\text{if } \sigma = (\tau+k, D) \cdot \sigma' \\ &\text{with } k \geq 0 \end{cases} \end{aligned}

Definition 3.10. The MFOTL Trace Converter Function converts MFOTL traces starting at timestamp 00 to system traces.

d:T→trim(Ts)\dConv: \Traces \to \trim(\Traces_\sys)

d(σ):=d′(0,σ). \dConv(\sigma) := \dConv'(0, \sigma).

It is important to note that d′(τ,σ)\dConv'(\tau, \sigma) is only defined, if τ≤fts(σ)\tau \leq \fts(\sigma) or σ=ε\sigma = \emptytrace. d\dConv however, is defined for all σ∈T\sigma \in \Traces, since timestamps in any trace must increase monotonically, and the timestamp argument passed to d′\dConv' is 00. To see that the images of both d\dConv and d′\dConv' for all allowed inputs is trim(Ts)\trim(\Traces_\sys) and not Ts\Traces_\sys, note that a tick\tick is only added when the trace is not yet empty, thus any inserted tick\tick will eventually be followed by some database DD. For any set of MFOTL traces A⊆TA \subseteq \Traces and any set of system traces B∈TsB \in \Traces_\sys and timestamp τ∈N\tau \in \Nat, we write c(A):={c(σs)∣σs∈A},c′(τ,A):={c′(τ,σs)∣σs∈A},d(B):={d(σ)∣σ∈B},andd′(τ,B):={d′(τ,σ)∣σ∈B}.\begin{aligned} &\cConv(A) &&:= \{ \cConv(\sigma_\sys) \mid \sigma_\sys \in A \}, \\ &\cConv'(\tau, A) &&:= \{ \cConv'(\tau, \sigma_\sys) \mid \sigma_\sys \in A \}, \\ &\dConv(B) &&:= \{ \dConv(\sigma) \mid \sigma \in B \}, and \\ &\dConv'(\tau, B) &&:= \{ \dConv'(\tau, \sigma) \mid \sigma \in B \}. \\ \end{aligned}

Theorem 3.11. The trace converter functions c\cConv and d\dConv define a bijective mapping between MFOTL traces T\Traces and trimmed system traces trim(Ts)\trim(\Traces_\sys) and are each others inverses. ∀σ∈T. σ=d(c(σ))\forall \sigma \in \Traces .~ \sigma = \dConv(\cConv(\sigma)) and ∀σs∈trim(Ts). σs=c(d(σ))\forall \sigma_\sys \in \trim(\Traces_\sys) .~ \sigma_\sys = \cConv(\dConv(\sigma))

The intuition behind the necessity of trimming system traces to make them fully comparable with MFOTL traces is that MFOTL traces only capture some last timestamp at which a database was logged, while system traces can capture a current timestamp (the total number of ticks in a system trace) which may be greater than the last time stamp at which a database was logged (the number of ticks up until the last database).

Proof. The proof for Theorem 3.11 proceeds by splitting it into two properties, one for each direction. We want to show the two following equations. ∀σ∈T. σ=d(c(σ)),∀σs∈trim(Ts). σs=c(d(σs)),\begin{align} \htmlId{eq:domain-mfotl-traces}{} &\forall \sigma \in \Traces .~ &\sigma &=\dConv(\cConv(\sigma)), \tag{3.1} \\ \htmlId{eq:domain-system-traces}{} &\forall \sigma_\sys \in \trim(\Traces_{\sys}) .~ &\sigma_\sys &=\cConv(\dConv(\sigma_\sys)), \tag{3.2}\end{align} Since c\cConv and d\dConv are defined with c′\cConv' and d′\dConv' respectively, the proof will proceed by showing the following two, more general, properties for all τ∈N\tau \in \Nat. ∀σ∈T. (σ=ε∨τ≤fts(σ))→c′(τ,d′(τ,σ))=σ,∀σs∈trim(Ts). d′(τ,c′(τ,σs))=σs,\begin{align} \htmlId{eq:domain-mfotl-traces'}{} &\forall \sigma \in \Traces .~ ( \sigma = \emptytrace \vee \tau \leq \fts(\sigma) ) \to \cConv'(\tau, \dConv'(\tau, \sigma)) = \sigma, \tag{3.3} \\ \htmlId{eq:domain-system-traces'}{} &\forall \sigma_\sys \in \trim(\Traces_{\sys}) .~ \dConv'(\tau, \cConv'(\tau, \sigma_\sys)) = \sigma_\sys, \tag{3.4}\end{align} When fixing τ=0\tau=0 in these two equations respectively, the precondition in Equation 3.3 evaluates to true, and the two equations become equivalent to Equation 3.1 and Equation 3.4. Thus Equation 3.3 implies Equation 3.1 and Equation 3.4 implies Equation 3.2.

For each direction we will first show that they hold for finite traces and then make the argument they also hold for infinite traces.

  1. MFOTL Traces (Equations 3.1 and 3.3)

    As stated above, we begin by showing Equation 3.3 for finite traces σ∈Tf\sigma \in \Traces_f. In a second step we will then make the argument why it also holds for infinite MFOTL traces. We proof this by structural induction over traces σ∈Tf\sigma \in \Traces_f for all τ∈N\tau \in \Nat where either τ≤fts(σ)\tau \leq \fts(\sigma) or σ=ε\sigma = \emptytrace.

    Base Case: σ=ε\sigma = \emptytrace (and some τ∈N\tau \in \Nat) c′(τ,d′(τ,σ))=c′(τ,d(τ,ε))=?c′(τ,εs)=?ε=σ\begin{aligned} \cConv'(\tau, \dConv'(\tau, \sigma)) = \cConv'(\tau, \dConv(\tau, \emptytrace)) \stackrel{\text{?}}{=} \cConv'(\tau, \emptytrace_\sys) \stackrel{\text{?}}{=} \emptytrace = \sigma \end{aligned} Induction Hypothesis: For every true suffix σ′\sigma' of a trace σ∈Tf\sigma \in \Traces_f that is not the entire trace σ\sigma, i.e. σ=σ′′⋅σ′\sigma = \sigma'' \cdot \sigma' and σ′′≠ε\sigma'' \neq \emptytrace, and for every timestamp τ∈N\tau \in \Nat which is less than the first timestamp (τ≤fts(σ′)\tau \leq \fts(\sigma')) in σ′\sigma', unless σ′=ε\sigma' = \emptytrace it holds that σ′=c′(τ,d′(τ,σ′)).\sigma' = \cConv'(\tau, \dConv'(\tau, \sigma')).

    Induction Step: Let σ≠ε\sigma \neq \emptytrace and τ≤fts(σ)\tau \leq \fts(\sigma). Because σ\sigma is not empty, σ=(τ+k,D)⋅σ′\sigma = \left(\tau+k, D \right) \cdot \sigma' for some k≥0k \geq 0, some D∈DBD \in \Databases and a suffix σ′∈Tf\sigma' \in \Traces_f. c′(τ,d′(τ,σ))=c′(τ,d′(τ,(τ+k,D)⋅σ′))=?c′(τ,tickk⋅D⋅d′(τ+k,σ′))=?(τ+k,D)⋅c′(τ+k,d′(τ+k,σ′))=IH(τ+k,D)⋅σ′=σ\begin{aligned} \cConv'(\tau, \dConv'(\tau, \sigma)) &= \cConv'(\tau, \dConv'(\tau, (\tau+k, D) \cdot \sigma')) \\ &\stackrel{\text{?}}{=} \cConv'(\tau, \tick^k \cdot D \cdot \dConv'(\tau + k, \sigma')) \\ &\stackrel{\text{?}}{=} (\tau+k, D) \cdot \cConv'(\tau+k, \dConv'(\tau+k, \sigma')) \\ &\stackrel{\text{IH}}{=} \left(\tau+k, D \right) \cdot \sigma' = \sigma \end{aligned}

    Finally we show how this extends to infinite traces. Let σ∈Tω\sigma \in \Traces_\omega be an infinite MFOTL trace. And let σ∣…i\sigma_{|\dots i} be the finite prefix with the first ii time points of σ\sigma. With the finite case, we have shown that for any i∈Ni \in \Nat, σ∈Tω\sigma \in \Traces_\omega, and τ≤fts(σ∣…i)\tau \leq \fts(\sigma_{|\dots i}) (in the infinite case, a first timestamp always exists) σ..i=c′(τ,d′(τ,σ∣…i))\sigma_{..i} = \cConv'(\tau, \dConv'(\tau, \sigma_{|\dots i})). Then in the limit σ=lim⁡i→∞σ∣…i=lim⁡i→∞c′(τ,d′(τ,σ∣…i))=c′(τ,d′(τ,σ)).\sigma = \lim_{i \to \infty} \sigma_{|\dots i} = \lim_{i \to \infty} \cConv'(\tau, \dConv'(\tau, \sigma_{|\dots i})) = \cConv'(\tau, \dConv'(\tau, \sigma)).

    We have now shown 3.1 for both finite and infinite traces, which directly implies 3.3.

  2. System Traces (Equations 3.2 and 3.4) For this direction we first prove that Equation 3.4 holds for finite system traces σs∈trim(Tsf)\sigma_\sys \in \trim(\Traces_{\sys f}). And in a second step will show that it also holds for infinite system traces σs∈trim(Tsω)\sigma_\sys \in \trim(\Traces_{\sys \omega}). We recall that whether or not a system trace is finite or infinite depends on the number of database events in the trace.

    This first part of the proof proceeds by structural induction over finite and trimmed system traces σs∈trim(Tsf)\sigma_\sys \in \trim(\Traces_{\sys f}) for all τ∈N\tau \in \Nat .

    1. Base Case σs=εs\sigma_\sys = \emptytrace_\sys d′(τ,c′(τ,σs))=d′(τ,c′(τ,εs))=?d′(τ,ε)=?εs=σs\begin{aligned} \dConv'(\tau, \cConv'(\tau, \sigma_\sys)) = \dConv'(\tau, \cConv'(\tau, \emptytrace_\sys)) \stackrel{\text{?}}{=} \dConv'(\tau, \emptytrace) \stackrel{\text{?}}{=} \emptytrace_\sys = \sigma_\sys \end{aligned}

    2. Induction Hypothesis For every true suffix σs′\sigma_\sys' of a trimmed system trace σs∈trim(Tsf)\sigma_\sys \in \trim(\Traces_{\sys f}) that is not the entire trace σs\sigma_\sys, i.e. σs=σs′′⋅σs′\sigma_\sys = \sigma_\sys'' \cdot \sigma_\sys' and σs′′≠ε\sigma_\sys'' \neq \emptytrace, and for every timestamp τ∈N\tau \in \Nat it holds that σs′=d′(τ,c′(τ,σs′)).\sigma_\sys' = \dConv'(\tau, \cConv'(\tau, \sigma_\sys')).

    3. Induction Step

      Let σs∈trim(Tsf)\sigma_\sys \in \trim(\Traces_{\sys f}), with σs≠εs\sigma_\sys \neq \emptytrace_\sys . Then σs=tickk⋅D⋅σs′\sigma_\sys = \tick^k \cdot D \cdot \sigma_\sys' for some k≥0k \geq 0, D∈DBD \in \Databases, and a suffix σs′∈trim(Tsf)\sigma_\sys' \in \trim(\Traces_{\sys f}). d′(τ,c′(τ,σs))=d′(τ,c′(τ,tickk⋅D⋅σs′))=?d′(τ,(τ+k,D)⋅c′(τ+k,σs′))=?tickk⋅D⋅d′(τ+k,c′(τ+k,σs′))=IHtickk⋅D⋅σs′=σs\begin{aligned} \dConv'(\tau, \cConv'(\tau, \sigma_\sys)) &= \dConv'(\tau, \cConv'(\tau, \tick^k \cdot D \cdot \sigma_\sys')) \\ &\stackrel{\text{?}}{=} \dConv'(\tau, (\tau+k, D) \cdot \cConv'(\tau+k, \sigma_\sys')) \\ &\stackrel{\text{?}}{=} \tick^k \cdot D \cdot \dConv'(\tau+k, \cConv'(\tau+k, \sigma_\sys')) \\ &\stackrel{IH}{=} \tick^k \cdot D \cdot \sigma_\sys' = \sigma_\sys \end{aligned}

      Finally we show how this extends to infinite system traces. Let σs∈trim(Tsω)\sigma_\sys \in \trim(\Traces_{\sys \omega}) be an infinite system trace. And let σs∣…i\sigma_{\sys | \dots i} be the finite prefix of σs\sigma_\sys ending with the ii-th database event. By this definition σs∣…i\sigma_{\sys |\dots i} is in trim(Tsf)\trim(\Traces_{\sys f}). With the finite case, we have shown that for any i∈Ni \in \Nat, σs∈trim(Tsω)\sigma_\sys \in \trim(\Traces_{\sys \omega}), and τ∈N\tau \in \Nat σs∣…i=d′(τ,c′(τ,σs∣…i))\sigma_{\sys |\dots i} = \dConv'(\tau, \cConv'(\tau, \sigma_{\sys | \dots i})). Then in the limit σs=lim⁡i→∞σs∣…i=lim⁡i→∞d′(τ,c′(τ,σs∣…i))=d′(τ,c′(τ,σs)).\sigma_\sys = \lim_{i \to \infty} \sigma_{\sys |\dots i} = \lim_{i \to \infty} \dConv'(\tau, \cConv'(\tau, \sigma_{\sys | \dots i})) = \dConv'(\tau, \cConv'(\tau, \sigma_\sys)).

 ◻

Intuitively c\cConv and c′\cConv' count the clock ticks and store them explicitly as integer timestamps. For both trace definitions, a property is a subset of all possible traces. For conversion of properties we use c\cConv with arguments being sets of traces in which case c\cConv simply gets mapped on each element of the set. As in Sprenger et. al [17] and Abadi and Lamport [3] traces of this second form can be extended with a stuttering step skip\sskip, where traces are equivalent if they are the same with all skip\sskip steps removed. In particular this means that sets of system traces (such as trace properties) are closed under the addition and removal of skip\sskip events. Thus the set of events in system traces Ts\Traces_\sys gets extended to be DB∪{tick,skip}.\Databases \cup \left\{ \tick, \sskip \right\}. Since skip\sskip events do not meaningfully modify a system trace, the isomorphism from Theorem 3.11 works if we remove all skip\sskip events before doing the trace conversion.

With the isomorphism between MFOTL traces as defined in prior work and Section 2 and trimmed system traces we can define MFOTL semantics for infinite system traces as follows.

Example 3.12. If we recall the MFOTL trace σ\sigma from Example 2.10, we can now convert it into a system trace σs:=c(σ)\sigma_\sys := \cConv(\sigma). σs=⟨{giveEmailConsent("Alice","Account Updates")},tick,{giveEmailConsent("Bob","Marketing")},tick,{revokeEmailConsent("Alice","Account Updates"),giveEmailConsent("Bob","Account Updates")},tick,tick,tick,tick,tick,tick,tick,tick,∅⟩\begin{aligned} \sigma_\sys = \langle & \{\mathsf{giveEmailConsent}(\text{"Alice"}, \text{"Account Updates"})\}, \tick, \\ & \{\mathsf{giveEmailConsent}(\text{"Bob"}, \text{"Marketing"})\}, \tick, \\ & \{\mathsf{revokeEmailConsent}(\text{"Alice"}, \text{"Account Updates"}), \\ &\quad \mathsf{giveEmailConsent}(\text{"Bob"}, \text{"Account Updates"})\}, \\ & \tick, \tick, \tick, \tick, \tick, \tick, \tick, \tick, \emptyset \\ \rangle \\ \end{aligned}

Definition 3.13. The semantics of MFOTL for a fixed, infinite system trace σs∈Tsω\sigma_\sys \in \Traces_{\sys \omega}, a valuation vv, time-point ii, and MFOTL formula φ\phi is defined as v,i⊨σsφ iff v,i⊨c(σs)φ.v, i \vDash_{\sigma_\sys} \phi \quad \text{ iff } \quad v, i \vDash_{\cConv(\sigma_\sys)} \phi.

Runtime Enforcement as an Event System

In this subsection we define an alternative runtime enforcement model than that presented in Section 2.2.1. and by Hublet et al. [9]. We want to describe runtime enforcement as an event system, such that we can show that our definition of CRE[MFOTL] refinement corresponds to the notion of refinement for event systems as described by Sprenger et al. [17]. Describing runtime enforcement as an event system gives a model comparable to the edit automata approach by Ligatti et al. [14], since both edit automata and event systems are forms of state machines.

The event system model of runtime enforcement works with system traces as introduced in Section 3.2.1. At the end of this seciont, with the isomorphism between MFOTL traces and trimmed system traces from Theorem 3.11, we will show that the two runtime enforcement models are equivalent.

Our model of proactive enforcement as an event system relies on two update functions, one for the proactive and one for the reactive case

Definition 3.14. A Reactive Update Function δ:Tsf×DB→DB\RFun : \Traces_{\sys f} \times \Databases \to \Databases modifies a reported set of events by suppressing (deleting) and causing (inserting) certain events if needed. Where for all σ∈Tsf\sigma \in \Traces_{\sys f} and D∈DBD \in \Databases

  • D∖δ(σ,D)∈DBSD \setminus \RFun(\sigma, D) \in \Databases_\Sup

  • δ(σ,D)∖D∈DBC\RFun(\sigma, D) \setminus D \in \Databases_\Cau

Definition 3.15. A Proactive Update Function γ:Tsf→DBC∪{skip}\PFun : \Traces_{\sys f} \to \Databases_\Cau \cup \{ \sskip \} indicates whether or not some events must be caused (inserted) before a clock tick happens.

Definition 3.16. The Enforcement State Space S=Ts\Statespace = \Traces_\sys consists of all system traces (that may include skip\sskip).

Definition 3.17. The single initial state is the empty trace εs\emptytrace_\sys. I={εs}\Initialstates = \lbrace \emptytrace_\sys \rbrace

Definition 3.18. The Event Space E=DB∪{tick,skip}\Eventspace=\Databases \cup \lbrace \tick, \sskip \rbrace consists of sets of events or the two special events tick\tick and skip\sskip.

Definition 3.19. The Transition Relation is a subset →⊆Ts×(DB∪{tick,skip})×Ts\Transitionrelation{}{} \subseteq \Traces_\sys \times (\Databases \cup \{\tick, \sskip \} ) \times \Traces_\sys and it is defined by the following two transition rules. σ→δ(σ,D)σ⋅δ(σ,D)(Step-R)σ→γ(σ)⋅tickσ⋅γ(σ)⋅tick(Step-P)\begin{aligned} \sigma &\Transitionrelation{}{\RFun(\sigma, D)} \sigma \cdot \RFun(\sigma, D) & \text{(Step-R)} \\ \sigma &\Transitionrelation{}{\PFun(\sigma) \cdot \tick} \sigma \cdot \PFun(\sigma) \cdot \tick & \text{(Step-P)} \end{aligned}

We write σ→eσ′\sigma \Transitionrelation{}{e} \sigma' as a shorthand for (σ,e,σ′)∈→(\sigma, e, \sigma') \in \Transitionrelation{}{}. Further for events e1,e2∈Ee_1, e_2 \in \Eventspace, σ→e1⋅e2σ′\sigma \Transitionrelation{}{e_1 \cdot e_2} \sigma' iff there exists σ′′\sigma'' such that σ→e1σ′′\sigma \Transitionrelation{}{e_1} \sigma'' and σ′′→e2σ′\sigma'' \Transitionrelation{}{e_2} \sigma'. This syntax can be extend to sequences of events (i.e. system traces) ρ1,ρ2∈Ts\rho_1, \rho_2 \in \Traces_\sys, σ→ρ1⋅ρ2σ′\sigma \Transitionrelation{}{\rho_1 \cdot \rho_2} \sigma' iff there exists σ′′\sigma'' such that σ→ρ1σ′′\sigma \Transitionrelation{}{\rho_1} \sigma'' and σ′′→ρ2σ′\sigma'' \Transitionrelation{}{\rho_2} \sigma'.

Definition 3.20. An Enforcement Event System Ξ=(S,E,δ,γ)\EventSystem = \left(\Statespace, \Eventspace, \RFun, \PFun \right) is a tuple consisting of a state space S:=Ts\Statespace := \Traces_\sys, event space E=DB∪{tick,skip}\Eventspace = \Databases \cup \left\{ \tick, \sskip \right\}, a reactive update function δ:Tsf×DB→DB\RFun : \Traces_{\sys f} \times \Databases \to \Databases and a proactive update function γ:Tsf→DBC∪{skip}\PFun : \Traces_{\sys f} \to \Databases_\Cau \cup \left\{ \sskip \right\}. Where the two update functions define a transition relation as defined in Definition 3.19.

We use the same definition of event traces for an enforcement event system Ξ\EventSystem with initial states I\Initialstates as for event systems inin Sprenger et al. [17] (Section 2.4), states I\Initialstates. Our described system has the property that if the only initial state is the empty trace εs\emptytrace_\sys, the final state of the event system and the event trace of the system are identical.

We define soundness notions for enforcement event systems that are analogous to soundness of an enforcer in Subsection 2.2.1. Sprenger et al. [17] define traces as always being finite sequences of events. We extend that definition to include both finite and infinite event sequences. The function traces(Ξ,I)\EStraces(\EventSystem, \Initialstates) then denotes both all finite and infinite event sequences of the event system Ξ\EventSystem starting in any initial state in I\Initialstates. tracesf(Ξ,I)\EStraces_f(\EventSystem, \Initialstates) denotes only the finite traces and tracesω(Ξ,I)\EStraces_\omega(\EventSystem, \Initialstates) only the infinite traces. We also extend the definition of trace properties to include both finite and infinite sequences. We use the following notations if we specifically talk about trace properties that are strictly finite or infinite respectively: Ξ,I⊨fP\EventSystem, \Initialstates \vDash_f P iff tracesf(Ξ,I)⊆P\EStraces_f(\EventSystem, \Initialstates) \subseteq P and Ξ,I⊨ωP\EventSystem, \Initialstates \vDash_\omega P iff tracesω(Ξ,I)⊆P\EStraces_\omega(\EventSystem, \Initialstates) \subseteq P. Like Sprenger et. al [17] we will omit the set braces for initial states, if the set is a singleton. Note that system traces are only considered infinite if they are infinite with all skips removed and trimmed (ticks not followed by a database removed).

Next we will show that any enforcer as in Hublet et al. [9] has a corresponding enforcement event system. To simplify this we define a helper function, that can compute the state of an enforcer after having enforced some trace as well as potentially some "leftover" ticks.

Definition 3.21. The Enforcer State Function state:S×Ts→S\state : \EnfStates \times \Traces_\sys \to \EnfStates gives the state starting in some initial state, after having enforced the corresponding MFOTL trace of a system trace as well as the ticks that may or may not be "dangling" at the end of the system trace. This function is defined by essentially simulating the run\run function of Algorithm 1. The simulation uses a helper function state′:S×Ts×Ts→S\state' : \EnfStates \times \Traces_\sys \times \Traces_\sys \to \EnfStates state′(s,σs1,σs2):=\state'(s, \sigma_{\sys 1}, \sigma_{\sys 2}) := {sif σs2=εsstate′(s′,σs1⋅DC⋅tick,σs2′)if σs2=tick⋅σs2′and (PCom(DC),s′)=μ(c(σs1),s,#tick(σs1),tick)state′(s′,σs1⋅tick,σs2′)if σs2=tick⋅σs2′and (NoCom,s′)=μ(c(σs1),s,#tick(σs1),tick)state′(s′,σs1⋅(D∖DS∪DC),σs2′)if σs2=D⋅σs2′and (RCom(DC,DS),s′)=μ(c(σs1),s,#tick(σs1),D)\begin{aligned} \begin{cases} s &\text{if } \sigma_{\sys 2} = \emptytrace_\sys \\ \state'(s', \sigma_{\sys 1} \cdot D_\Cau \cdot \tick, \sigma_{\sys 2}') &\text{if } \sigma_{\sys 2} = \tick \cdot \sigma_{\sys 2}' \\ &\text{and } (\PCom(D_\Cau), s') \\ &\quad = \EnfFun(\cConv(\sigma_{\sys 1}), s, \numTicks(\sigma_{\sys 1}), \tick) \\ \state'(s', \sigma_{\sys 1} \cdot \tick, \sigma_{\sys 2}') &\text{if } \sigma_{\sys 2} = \tick \cdot \sigma_{\sys 2}' \\ &\text{and } (\NCom, s') \\ &\quad = \EnfFun(\cConv(\sigma_{\sys 1}), s, \numTicks(\sigma_{\sys 1}), \tick) \\ \state'(s', \sigma_{\sys 1} \cdot (D \setminus D_\Sup \cup D_\Cau), \sigma_{\sys 2}') &\text{if } \sigma_{\sys 2} = D \cdot \sigma_{\sys 2}' \\ &\text{and } (\RCom(D_\Cau, D_\Sup), s') \\ &\quad = \EnfFun(\cConv(\sigma_{\sys 1}), s, \numTicks(\sigma_{\sys 1}), D) \end{cases} \end{aligned} Then the state\state function is defined as follows for any enforcer state s∈Ss \in \EnfStates and system trace σs∈Ts\sigma_\sys \in \Traces_\sys state(s,σs):=state′(s,εs,σs).\state(s, \sigma_\sys) := \state'(s, \emptytrace_\sys, \sigma_\sys).

Definition 3.22. The induced enforcement event system of an enforcer E=(S,s0,μ)\Enforcer = (\EnfStates, s_0, \EnfFun) is defined as Ξ(E):=(Ts,DB∪{tick,skip},δ,γ),\EventSystem(\Enforcer) := (\Traces_\sys, \Databases \cup \{\tick, \sskip \}, \RFun, \PFun), with δ\RFun and γ\PFun defined as follows δ(σs,D):=D∖DS∪DCwith μ(c(σs),state(s0,σs),#tick(σs),D)=(RCom(DC,DS),s)γ(σs):={skipif μ(c(σs),state(s0,σs),#tick(σs),D)=(NoCom,s)DCif μ(c(σs),state(s0,σs),#tick(σs),D)=(PCom(DC),s)\begin{aligned} \RFun(\sigma_\sys, D) &:= D \setminus D_\Sup \cup D_\Cau \\ &\qquad \text{with } \EnfFun(\cConv(\sigma_\sys), \state(s_0, \sigma_\sys), \numTicks(\sigma_\sys), D) = (\RCom(D_\Cau, D_\Sup), s) \\ \PFun(\sigma_\sys) &:= \begin{cases} \sskip &\text{if } \EnfFun(\cConv(\sigma_\sys), \state(s_0, \sigma_\sys), \numTicks(\sigma_\sys), D) = (\NCom, s) \\ D_\Cau &\text{if } \EnfFun(\cConv(\sigma_\sys), \state(s_0, \sigma_\sys), \numTicks(\sigma_\sys), D) = (\PCom(D_\Cau), s) \end{cases} \end{aligned}

Definition 3.23. An enforcement event system Ξ=(Ts,DB∪{tick,skip},δ,γ)\EventSystem = \left(\Traces_\sys, \Databases \cup \{ \tick, \sskip \}, \RFun, \PFun \right) is sound with respect to some property P⊆TsωP \subseteq \Traces_{\sys \omega} iff Ξ,εs⊨P.\EventSystem, \emptytrace_\sys \vDash P.

Equivalently an enforcement event system Ξ\EventSystem and the initial state εs\emptytrace_\sys are sound for a property P⊆TsωP \subseteq \Traces_{\sys \omega} iff tracesω(Ξ,εs)⊆P\EStraces_\omega(\EventSystem, \emptytrace_\sys) \subseteq P. This soundness definition difers from Sprenger et al. [17] in that it is over infinite traces, where Sprenger et al. define soundness over finite traces. We however want to use infinite traces, because the enforcement model of Hublet et al. [9] defines soundenss with infinite traces. This deviation from Sprenger et al. [17] is fine to make, because any set of infinite traces could be converted into an (infinitely large) set of all finite prefixes of the inifinite traces.

Definition 3.24. An enforcement event system Ξ\EventSystem is sound for a formula φ\phi iff it is sound for the property L(φ)\Language(\phi).

Theorem 3.25. If an enforcer E=(S,s0,μ)\Enforcer = (\EnfStates, s_0, \EnfFun) is sound for a property P⊆TωP \subseteq \Traces_\omega, then the induced enforcement event system Ξ(E)\EventSystem(\Enforcer) is sound for the property c(P)⊆Tsω\cConv(P) \subseteq \Traces_{\sys \omega}.

Before we can prove Theorem 3.25, we need the following two lemmata. The proofs for which can be found in Appendix B.1 and B.2.

Lemma 3.26. For all σs\sigma_\sys, τ∈N\tau \in \Nat and D∈DBD \in \Databases, c′(τ,σs⋅D)=c′(τ,σs)⋅c(τ+#tick(σs),D)\cConv'(\tau, \sigma_\sys \cdot D) = \cConv'(\tau, \sigma_\sys) \cdot \cConv(\tau + \numTicks(\sigma_\sys), D)

Lemma 3.27. Let E=(S,s0,μ)\Enforcer = (\EnfStates, s_0, \mu) be an enforcer. For any system trace σs∈traces(Ξ(E),εs)\sigma_\sys \in \EStraces(\EventSystem(\Enforcer), \emptytrace_\sys) there exists a trace σ∈T\sigma \in \Traces such that c(σs)=E(σ)\cConv(\sigma_\sys) = \Enforcer(\sigma).

Proof. We will show that for all σs∈tracesf(Ξ(E),εs)\sigma_\sys \in \EStraces_f(\EventSystem(\Enforcer), \emptytrace_\sys) there exists a trace σs′∈c(P)\sigma_\sys' \in \cConv(P) of which σs\sigma_\sys is a prefix (i.e. σs=σs∣…≤∣σs∣′\sigma_\sys = \sigma'_{\sys \mid \ldots \leq |\sigma_\sys|}).

Since by definition tracesf(Ξ(E),εs)\EStraces_f(\EventSystem(\Enforcer), \emptytrace_\sys) contains all finite prefixes of tracesω(Ξ(E),εs)\EStraces_\omega(\EventSystem(\Enforcer), \emptytrace_\sys), if tracesω(Ξ(E),εs)⊈c(P)\EStraces_\omega(\EventSystem(\Enforcer), \emptytrace_\sys) \not\subseteq \cConv(P), there would exist some contains all finite prefixes of σs∈tracesf(Ξ(E),εs)\sigma_\sys \in \EStraces_f(\EventSystem(\Enforcer), \emptytrace_\sys) which is not a prefix for any trace σs′∈c(P)\sigma_\sys' \in \cConv(P). Thus if we show that every finite prefix σs∈tracesf(Ξ(E),εs)\sigma_\sys \in \EStraces_f(\EventSystem(\Enforcer), \emptytrace_\sys) is also a finite prefix for at least one trace σs′∈c(P)\sigma_\sys' \in \cConv(P), we will have shown that σs∈tracesω(Ξ(E),εs)⊆σs′∈c(P)\sigma_\sys \in \EStraces_\omega(\EventSystem(\Enforcer), \emptytrace_\sys) \subseteq \sigma_\sys' \in \cConv(P).

This property is a consequence of Lemma 3.27. In Lemma 3.27 we have shown that any enforcement event system trace corresponds to a trace produced by the enforcer. All those traces "produced" by the enforcer fall into PP, by the fact that the enforcer is sound for PP. and since we have shown that for all system traces σs∈tracesf(Ξ(E),εs)\sigma_\sys \in \EStraces_f(\EventSystem(\Enforcer), \emptytrace_\sys), there exists a trace σ∈T\sigma \in \Traces such that c(σs)=E(σ)\cConv(\sigma_\sys) = \Enforcer(\sigma), we have also shown that c(σs)∈P\cConv(\sigma_\sys) \in P or equivalently c(traces(Ξ(E),εs))⊆P\cConv(\EStraces(\EventSystem(\Enforcer), \emptytrace_\sys)) \subseteq P. This does also imply traces(Ξ(E),εs)⊆c(P)\EStraces(\EventSystem(\Enforcer), \emptytrace_\sys) \subseteq \cConv(P). ◻

Refinement

Enforcement Event System Refinement

For Enforcement Event Systems we will now define refinement via a mediator function and a simulation relation as in Sprenger et. al [17].

Definition 3.28. An enforcement event system ΞC=(TsC,DBC∪{tick,skip},δC,γC)\EventSystem_C = ( \Traces_{\sys C}, \Databases_C \cup \{\tick, \sskip \}, \RFun_C, \PFun_C ) for some signature ΣC=(D,EC,F,ιC)\Sigma_C = \left( \Domain, \Events_C, \Functions, \iota_C \right) with initial states IC⊆TC\Initialstates_C \subseteq \Traces_C refines an enforcement event system ΞA=(TsA,DBA∪{tick,skip},δA,γA)\EventSystem_A = \left( \Traces_{\sys A}, \Databases_A \cup \{\tick, \sskip \}, \RFun_A, \PFun_A \right) for some signature ΣA=(D,EA,F,ιA)\Sigma_A = \left( \Domain, \Events_A, \Functions, \iota_A \right) with initial states IA⊆SA\Initialstates_A \subseteq \Statespace_A via a mediator function π:TC×(DBC∪{tick,skip})→(DBA∪{tick,skip})\MFun : \Traces_C \times (\Databases_C \cup \{ \tick, \sskip \}) \to (\Databases_A \cup \{ \tick, \sskip \}) iff there is a simulation relation R⊆TC×TA\SimRel \subseteq \Traces_C \times \Traces_A such that

  1. for all σC∈IC\sigma_C \in \Initialstates_C there exists some σA∈IA\sigma_A \in \Initialstates_A such that (σC,σA)∈R(\sigma_C, \sigma_A) \in \SimRel, and

  2. for all σA∈SA\sigma_A \in \Statespace_A, σC,σC′∈SC\sigma_C, \sigma_C' \in \Statespace_C, and eC∈ECe_C \in \Eventspace_C such that (σC,σA)∈R(\sigma_C, \sigma_A) \in \SimRel and σC→eCσC′\sigma_C \Transitionrelation{}{e_C} \sigma_C' there exists σA′\sigma_A' such that (σC′,σA′)∈R(\sigma_C', \sigma_A') \in \SimRel and σA→π(σC,eC)σA′\sigma_A \Transitionrelation{}{\MFun(\sigma_C, e_C)} \sigma_A'.

It is important to highlight, that our definition of a mediator function differs from that in Sprenger et al. [17] in that we include a second argument for the trace up to the current point in time. The reason for this is how we define MFOTL and Lex refinement in the following sections. Without going into the details, on a high level MFOTL refinements can define let bindings for abstract events, thus "concretizing" them. And let bindings allow for arbitrary MFOTL formulae on their right hand side which can of course depend on the past. That is why we need the history of events as an additional argument for our mediator function.

Definition 3.29. A mediator function π:TC×(DBC∪{tick,skip})→(DBA∪{tick,skip})\MFun : \Traces_C \times (\Databases_C \cup \{ \tick, \sskip \}) \to (\Databases_A \cup \{ \tick, \sskip \}) can be extended to a trace transducer function π⃗:TC→TA\vec{\MFun} : \Traces_C \to \Traces_A as follows π⃗(σs):={εsif σs=εsπ⃗(σs′)⋅π(π⃗(σs′),e)if σs=σs′⋅efor some e∈DBC∪{tick,skip}\begin{aligned} \vec{\MFun}(\sigma_\sys) := \begin{cases} \emptytrace_\sys &\text{if } \sigma_\sys = \emptytrace_\sys \\ \vec{\MFun}(\sigma_\sys') \cdot \MFun(\vec{\MFun}(\sigma_\sys'), e) &\text{if } \sigma_\sys = \sigma_\sys' \cdot e \\ &\text{for some } e \in \Databases_C \cup \{\tick, \sskip \} \end{cases} \end{aligned}

The following theorem is analogous to Theorem 2.52 [17, Theorem 2.1].

Theorem 3.30. (ΞC,IC)⊑π(ΞA,IA)(\EventSystem_C, \Initialstates_C) \refineL_\MFun (\EventSystem_A, \Initialstates_A) implies π⃗(traces(ΞC,IC))⊆traces(ΞA,IA)\vec{\MFun}(\EStraces(\EventSystem_C, \Initialstates_C)) \subseteq \EStraces(\EventSystem_A, \Initialstates_A).

The proof for Theorem 3.30 is analogous to the proof for Theorem 2.52.

The following lemma is analogous to Lemma 2.54 [17, Lemma 2.2].

Lemma 3.31. Suppose ΞA,IA⊨P\EventSystem_A, \Initialstates_A \vDash P and π⃗(traces(ΞC,IC))⊆traces(ΞA,IA)\vec{\MFun}(\EStraces(\EventSystem_C, \Initialstates_C)) \subseteq \EStraces(\EventSystem_A, \Initialstates_A) then ΞC,IC⊨π⃗−1(P)\EventSystem_C, \Initialstates_C \vDash \vec{\MFun}^{-1}(P)

The proof for Lemma 3.31 is analogous to the proof for Lemma 2.54.

CRE[MFOTL] Refinement

In this subsection we recall refinement of Lex specifications as it is described in Hublet et. al [12]. We then go ahead and proof that whenever a CRE specification refines another CRE specification, their compiled MFOTL formulas are likewise refinements of each other.

  letd∉dom Γ    Γ⊢e(xˉ):mon(e)+   Emon+  letd∈dom ΓΓ(letd)=φΓ∖letd⊢φ:mon(e)p    Γ⊢d(xˉ):mon(e)p   Emonlet  e∉events(φ)    Γ⊢φ:mon(e)p   occmonp  Γ⊢φ:mon(e)¬p    Γ⊢¬φ:mon(e)p   ¬monp  Γ⊢φ:mon(e)pΓ⊢ψ:mon(e)p    Γ⊢φ∧ψ:mon(e)p   ∧monp  Γ⊢φ:mon(e)p    Γ⊢∃x. φ:mon(e)p   ∃monp  Γ⊢φ:mon(e)p    Γ⊢∘φ:mon(e)p   ∘monp  Γ⊢φ:mon(e)p    Γ⊢∙φ:mon(e)p   ∙monp  Γ⊢φ:mon(e)pΓ⊢ψ:mon(e)p    Γ⊢φSψ:mon(e)p   Smonp  Γ⊢φ:mon(e)pΓ⊢ψ:mon(e)p    Γ⊢φUψ:mon(e)p   Umonp  Γ,letd:φ⊢ψ:mon(e)p    Γ⊢let⁡d(xˉ)=φinψ:mon(e)p   letmonp\begin{gathered} \prfrule{$\Events^+_\mathsf{mon}$}{\mathsf{let}_d \not\in \mathsf{dom}~\Gamma}{\Gamma \vdash e(\bar{x}) : \mono{e}^+} \quad \prfrule{$\Events^\mathsf{let}_\mathsf{mon}$}{\mathsf{let}_d \in \mathsf{dom}~\Gamma \quad \Gamma(\mathsf{let}_d) = \phi \quad \Gamma \setminus \mathsf{let}_d \vdash \phi : \mono{e}^p}{\Gamma \vdash d(\bar{x}) : \mono{e}^p} \\[5pt] \prfrule{$\mathsf{occ}^p_\mathsf{mon}$}{e \not \in \events{\phi}}{\Gamma \vdash \phi : \mono{e}^p} \quad \prfrule{$\neg^p_\mathsf{mon}$}{\Gamma \vdash \phi : \mono{e}^{\neg p}}{\Gamma \vdash \neg \phi : \mono{e}^p} \\[5pt] \prfrule{$\wedge^p_\mathsf{mon}$}{\Gamma \vdash \phi : \mono{e}^p \quad \Gamma \vdash \psi : \mono{e}^p}{\Gamma \vdash \phi \wedge \psi : \mono{e}^p} \quad \prfrule{$\exists^p_\mathsf{mon}$}{\Gamma \vdash \phi : \mono{e}^p}{\Gamma \vdash \exists x.~ \phi : \mono{e}^p} \\[5pt] \prfrule{$\Next^p_\mathsf{mon}$}{\Gamma \vdash \phi : \mono{e}^p}{\Gamma \vdash \Next \phi : \mono{e}^p} \quad \prfrule{$\Prev^p_\mathsf{mon}$}{\Gamma \vdash \phi : \mono{e}^p}{\Gamma \vdash \Prev \phi : \mono{e}^p} \\[5pt] \prfrule{$\Since^p_\mathsf{mon}$}{\Gamma \vdash \phi : \mono{e}^p \quad \Gamma \vdash \psi : \mono{e}^p}{\Gamma \vdash \phi \Since \psi : \mono{e}^p} \quad \prfrule{$\UUntil^p_\mathsf{mon}$}{\Gamma \vdash \phi : \mono{e}^p \quad \Gamma \vdash \psi : \mono{e}^p}{\Gamma \vdash \phi \UUntil \psi : \mono{e}^p} \\[5pt] \prfrule{$\mathsf{let}^p_\mathsf{mon}$}{\Gamma, \mathsf{let}_d : \phi \vdash \psi : \mono{e}^p}{\Gamma \vdash \LLet{d(\bar{x})}{\phi}{\psi} : \mono{e}^p} \end{gathered}

Fig 3.1MFOTL (Anti) Monotonicity Rules [12, Appendix A]

  ∃r:φ⇒p∈C∀r:φ⇒p∈C. Γ⊢Φφ:mon(e)q and Γ⊢Φexc(r):mon(e)¬q    Γ⊢Φp(x‾):mon(e)q   conmonq  ∀r:φ⇒exc(s)∈E. Γ⊢Φφ:mon(e)p and Γ⊢Φexc(r):mon(e)¬p    Γ⊢Φexc(s)(x‾):mon(e)p   excmonp  r:φ⇒ψ∈RΓ⊢φ→ψ:mon(e)pΓ⊢exc(r):mon(e)p    Γ⊢Φcomply(r):mon(e)p   regmonp  r:φ⇒ψ∈R    Γ⊢(C,R,E):mon(exc(r))+     r:φ⇒p∈CΓ⊢(C,R,E):mon(p)¬q    Γ⊢(C,R,E):mon(exc(r))q     r:φ⇒exc(s)∈EΓ⊢(C,R,E):mon(exc(s))¬p    Γ⊢(C,R,E):mon(exc(r))p     ∀r:φ⇒ψ∈R. Γ⊢(C,R,E)comply(r):mon(e)p    Γ⊢(C,R,E):mon(e)p   \begin{gathered} \prfrule{$\textsc{con}^q_\mathsf{mon}$}{\begin{array}{c}\exists r : \phi \Rightarrow p \in C \\ \forall r : \phi \Rightarrow p \in C.~ \Gamma \vdash^\Phi \phi : \mono{e} ^q~ \textbf{and}~\Gamma \vdash^\Phi \exc(r) : \mono{e}^{\neg q}\end{array}}{\Gamma \vdash^\Phi p(\overline{x}) : \mono{e}^q} \\[5pt] \prfrule{$\textsc{exc}^p_\mathsf{mon}$}{\forall r : \phi \Rightarrow \exc(s) \in E.~ \Gamma \vdash^\Phi \phi : \mono{e}^p~ \textbf{and}~\Gamma \vdash^\Phi \exc(r) : \mono{e}^{\neg p}}{\Gamma \vdash^\Phi \exc(s)(\overline{x}) : \mono{e}^p} \\[5pt] \prfrule{$\textsc{reg}^p_\mathsf{mon}$}{r: \phi \Rightarrow \psi \in R \quad \Gamma \vdash \phi \to \psi : \mono{e}^p \quad \Gamma \vdash \exc(r) : \mono{e}^p}{\Gamma \vdash^\Phi \comply(r) : \mono{e}^p} \\[5pt] \prfrule{}{r: \phi \Rightarrow \psi \in R}{\Gamma \vdash (C,R,E) : \mono{\exc(r)}^+} \quad \prfrule{}{r: \phi \Rightarrow p \in C \quad \Gamma \vdash (C,R,E) : \mono{p}^{\neg q}}{\Gamma \vdash (C,R,E) : \mono{\exc(r)}^q} \\[5pt] \prfrule{}{r: \phi \Rightarrow \exc(s) \in E \quad \Gamma \vdash (C,R,E) : \mono{\exc(s)}^{\neg p}}{\Gamma \vdash (C,R,E) : \mono{\exc(r)}^p} \\[5pt] \prfrule{}{\forall r: \phi \Rightarrow \psi \in R.~ \Gamma \vdash^{(C,R,E)} \comply(r) : \mono{e}^p}{\Gamma \vdash (C,R,E) : \mono{e}^p} \end{gathered}

Fig 3.2CRE (Anti) Monotonicity Rules [12, Appendix A]

φ⇕+ψ:=φ⟹ψφ⇕−ψ:=φ⟸ψ      S,Γ⇝idS,Γ   refl  S1,Γ1⇝π1S2,Γ2S2,Γ2⇝π2S3,Γ3    S1,Γ1⇝π1∘π2S3,Γ3   trans  C′=C∪{r:φ⇒e(x1,…,xk)}events(φ)∖E={e1,…,eℓ}E′=E∖{e}∪{e1,…,eℓ}ι′=ι[i. ei↦ki]∖{e}κ′=κ[i. ei↦τi]∖{e}Γ′=Γ[i. ei↦τi′]∖{e}∀i. τi′⊑τiΓ′⊢φ:Γ(e)∄r′,φ′,x‾′. r′:φ′⇒e(x‾′)∈Cπ=mape(x1,…,xk),φ,{e1,…,eℓ}    ((D,E,F,ι),(C,R,E),κ),Γ⇝π((D,E′,F,ι′),(C′,R,E),κ′),Γ′   ref  R′=R∪{r:φ′⇒ψ′}∖{r:φ⇒ψ}φ′→ψ′⟹φ→ψΓ⊢(C,R′,E)comply(r):C    ((D,E,F,ι),(C,R,E),κ),Γ⇝id((D,E,F,ι),(C,R′,E),κ),Γ   impR  C′=C∪{r:φ′⇒p}∖{r:φ⇒p}R′=R∪{s:ψ⇒χ}q∈{+,−}□⁡(ψ→χ)⟹φ′⇕qφ(C∖{r:φ⇒p},R′,E):mon(p)qΓ⊢(C′,R,E)comply(s):C∀τ∈{C,S}. Γ⊢(C,R,E)p:τ⟹Γ⊢(C′,R,E)p:τ    ((D,E,F,ι),(C,R,E),κ),Γ⇝id((D,E,F,ι),(C′,R′,E),κ),Γ   impC  E′=E∪{r:φ′⇒exc(s)}∖{r:φ⇒exc(s)}R′=R∪{s:ψ⇒χ}q∈{+,−}□⁡(ψ→χ)⟹φ′⇕qφ(C,R′,E∖{r:φ⇒exc(s)}):mon(exc(s))qΓ⊢(C,R′,E′)comply(s):C∀τ∈{C,S}. Γ⊢(C,R,E)exc(s):τ⟹Γ⊢(C,R,E′)exc(s):τ    ((D,E,F,ι),(C,R,E),κ),Γ⇝id((D,E,F,ι),(C,R′,E′),κ),Γ   impE\begin{gathered} \phi \Updownarrow^+ \psi := \phi \Longrightarrow \psi\qquad \phi \Updownarrow^- \psi := \phi \Longleftarrow \psi \\[5pt] \prfrule{\textsc{refl}}{}{S,\Gamma \leadsto_{\mathrm{id}} S,\Gamma}\quad \prfrule{\textsc{trans}}{S_1,\Gamma_1 \leadsto_{\pi_1} S_2,\Gamma_2 \quad S_2,\Gamma_2 \leadsto_{\pi_2} S_3,\Gamma_3}{S_1,\Gamma_1 \leadsto_{\pi_1 \circ \pi_2} S_3,\Gamma_3}\\[5pt] \prfrule{\textsc{ref}}{\begin{array}{c}C' = C \cup \{r : \phi \Rightarrow e(x_1,\dots,x_k)\} \quad \mathsf{events}(\phi) \setminus \Events=\{e_1,\dots,e_\ell\} \\ \Events' = \Events \setminus \{e\} \cup \{e_1,\dots,e_\ell\} \quad \iota' = \iota[i.~e_i \mapsto k_i] \setminus \{e\} \\ \kappa' = \kappa[i.~e_i \mapsto \tau_i] \setminus \{e\} \quad \Gamma' = \Gamma[i.~e_i \mapsto \tau'_i] \setminus \{e\} \\ \forall i.~\tau'_i \sqsubseteq \tau_i \quad \Gamma' \vdash \phi : \Gamma(e) \quad \nexists r', \phi', \overline{x}'.~r': \phi' \Rightarrow e(\overline{x}') \in C \\ \pi = \textsc{\textsf{map}}_{e(x_1,\dots,x_k),\phi,\{e_1,\dots,e_\ell\}}\end{array}}{((\Domain,\Events,\Functions,\iota),(C,R,E),\kappa),\Gamma \leadsto_\pi ((\Domain,\Events',\Functions,\iota'),(C',R,E),\kappa'),\Gamma'}\\[5pt] \prfrule{$\textsc{imp}_R$}{\begin{array}{c}R' = R \cup \{r : \phi' \Rightarrow \psi' \} \setminus \{r : \phi \Rightarrow \psi\} \\ \phi' \to \psi' \Longrightarrow \phi \to \psi \quad \Gamma \vdash^{(C,R',E)} \comply(r) : \Cau\end{array}}{((\Domain,\Events,\Functions,\iota),(C,R,E),\kappa),\Gamma \leadsto_{\mathrm{id}} ((\Domain,\Events,\Functions,\iota),(C,R',E),\kappa),\Gamma}\\[5pt] \prfrule{$\textsc{imp}_C$}{\begin{array}{c}C' = C \cup \{ r: \phi' \Rightarrow p \} \setminus \{ r : \phi \Rightarrow p \} \quad R' = R \cup \{ s : \psi \Rightarrow \chi \} \\ q \in \{+,-\} \quad \Always (\psi \to \chi) \Longrightarrow \phi' \Updownarrow^q \phi \\ (C \setminus \{ r:\phi\Rightarrow p\},R',E) : \mono{p}^q \quad \Gamma \vdash^{(C',R,E)} \comply(s) : \Cau \\ \forall \tau \in \{\Cau,\Sup\}.~\Gamma \vdash^{(C,R,E)} p : \tau \Longrightarrow \Gamma \vdash^{(C',R,E)} p : \tau\end{array}}{((\Domain,\Events,\Functions,\iota),(C,R,E),\kappa),\Gamma \leadsto_{\mathrm{id}} ((\Domain,\Events,\Functions,\iota),(C',R',E),\kappa),\Gamma}\\[5pt] \prfrule{$\textsc{imp}_E$}{\begin{array}{c}E' = E \cup \{ r : \phi' \Rightarrow \exc(s) \} \setminus \{ r : \phi \Rightarrow \exc(s) \} \quad R' = R \cup \{ s : \psi \Rightarrow \chi\} \\ q \in \{+,-\} \quad \Always (\psi \to \chi) \Longrightarrow \phi' \Updownarrow^q \phi \\ (C,R',E \setminus \{ r:\phi\Rightarrow \exc(s)\}) : \mono{\exc(s)}^q \quad \Gamma \vdash^{(C,R',E')} \comply(s) : \Cau \\ \forall \tau \in \{\Cau,\Sup\}.~\Gamma \vdash^{(C,R,E)} \exc(s) : \tau \Longrightarrow \Gamma \vdash^{(C,R,E')} \exc(s) : \tau\end{array}}{((\Domain,\Events,\Functions,\iota),(C,R,E),\kappa),\Gamma \leadsto_{\mathrm{id}} ((\Domain,\Events,\Functions,\iota),(C,R',E'),\kappa),\Gamma} \end{gathered}

Fig 3.3CRE[MFOTL] refinement rules [12, Figure 7]
  1. let mape(x1,…,xk),φ,E_{e(x_1,\dots,x_k),\phi,E} σ\sigma =
  2. ⟨(τi,Di)i∈N⟩←σ\langle(\tau_i, D_i)_{i \in \Nat}\rangle \gets \sigma
  3. for i∈Ni \in \Nat do
  4.     Di′←Di∪{e(v(x1),…,v(xk))∣v,i⊨σφ}D'_i \gets D_i \cup \{ e(v(x_1),\dots,v(x_k)) \mid v,i \vDash_\sigma \phi \}
  5.     Di′←Di′∖{e(d‾)∣(d1,…,dι(e))∈Dι(e),e∈E}D'_i \gets D'_i \setminus \{ e(\overline{d}) \mid (d_1,\dots,d_{\iota(e)}) \in \Domain^{\iota(e)}, e \in E \}
  6. end for
  7. return ⟨(τi,Di′)i∈N⟩\langle(\tau_i, D'_i)_{i \in \Nat}\rangle
Fig 3.4map function used in Figure 3.3

Hublet et al. [12] use the rules in Figure 3.3 to define refinement for CRE[MFOTL] specifications in the following manner.

Definition 3.32. Refinement of CRE specifications is defined by the rules in Figure 3.3. A specification SCS_C refines a specification SAS_A, written as SC⊑πSAS_C \refineL_\pi S_A under a refinement mapping π\pi iff there exist ΓC\Gamma_C and ΓA\Gamma_A such that SC,ΓC⇝πSA,ΓAS_C, \Gamma_C \leadsto_\pi S_A, \Gamma_A.

The refinement rules in Figure 3.3 depend on the concept of monotonic and anti-monotonic predicates. Figure 3.1 shows the monotonicity rules for MFOTL predicates, in which p,q∈{+,−}p,q \in \{+,-\}, with ¬+:=−\neg + := - and ¬−:=+\neg - := +. A predicate PP appears monotonically (or anti-monotonically) in a formula φ\phi, if the addition of an event P(xˉ)P(\bar{x}) cannot make an already compliant (or non-compliant) trace non-compliant (or compliant). For example in the formula φ:=□⁡(¬p(1))\phi := \Always (\neg p(1)) the predicate PP does not appear monotonically, because the addition of an event at any time P(1)P(1) would make a trace that was previously compliant with φ\phi, non-compliant with φ\phi, on the other hand PP appears anti-monotonically in φ\phi. It is important to note that a predicate can appear monotonically, anti-monotonically, both monotonically and anti-monotonically, or neither monotonically nor anti-monotonically in a formula.

Figure 3.4 shows an algorithm that converts a concrete MFOTL trace to an abstract one, according to a formula φ\phi that defines an event e(x1,…,xk)e(x_1,\dots,x_k) in terms of the concrete events e1,…,eℓe_1,\dots,e_\ell. This function does for MFOTL traces, what the mediator function π\pi from Definition 3.32 and its extended form pi⃗\vec{pi} from Definition 3.29 do for system traces.

Definition 3.33. Let map\textsc{\textsf{map}} be a function as defined in Figure 3.4. Then the mediator function d(map)\dConv(\textsc{\textsf{map}}) is defined as follows: d(map)(σs,tick):=tickd(map)(σs,skip):=skipd(map)(σs,DC):=DA\begin{aligned} \dConv(\textsc{\textsf{map}})(\sigma_\sys, \tick) &:= \tick \\ \dConv(\textsc{\textsf{map}})(\sigma_\sys, \sskip) &:= \sskip \\ \dConv(\textsc{\textsf{map}})(\sigma_\sys, D_C) &:= D_A \end{aligned} where DAD_A is defined as the database of the last time point of the trace being returned by the MFOTL trace map(c(σs⋅D))\textsc{\textsf{map}}(\cConv(\sigma_\sys \cdot D)).

Lemma 3.34. For any MFOTL trace σ∈T\sigma \in \Traces, and map function map\textsc{\textsf{map}} d(map)→(c(σ))=d(map(σ))\overrightarrow{\dConv(\textsc{\textsf{map}})}(\cConv(\sigma)) = \dConv(\textsc{\textsf{map}}(\sigma))

The following theorem states that any valid refinement of an enforceable CRE[MFOTL] specification is itself enforceable.

Theorem 3.35. If SC⊑πSAS_C \refineL_\pi S_A under a refinement mapping and SAS_A is enforceable, then SCS_C is enforceable.

Theorem 3.36. If SC⊑πSAS_C \refineL_\pi S_A, SAS_A is enforceable, and σ⊨SC\sigma \vDash S_C, then π(σ)⊨SA\pi(\sigma) \vDash S_A.

Hublet et al. [12] have proved Theorem 3.35 [12, Theorem 4] and Theorem 3.36 [12, Theorem 3].

Theorem 3.37. If SC⊑πSAS_C \refineL_\pi S_A and SAS_A is enforceable then there exist two enforcement event systems ΞC\EventSystem_C and ΞA\EventSystem_A such that they are sound for SCS_C and SAS_A respectively, and refine each other via the mediator function d(π)\dConv(\pi), i.e. Ξ(EC)⊑d(π)Ξ(EA).\EventSystem(\Enforcer_C) \refineL_{\dConv(\pi)} \EventSystem(\Enforcer_A).

Proof. for Theorem 3.37 Let SC⊑πSAS_C \refineL_\pi S_A, and SAS_A be enforceable.

By the enforceability of SAS_A we know that there exists an enforcer EA=(SA,s0,μA)\Enforcer_A = (\EnfStates_A, s_0, \EnfFun_A) which is sound for SAS_A. By Theorem 3.35 we also know that there exists an enforcer EC=(SC,s0,μC)\Enforcer_C = (\EnfStates_C, s_0, \EnfFun_C) which is sound for SCS_C.

Since SC⊑πSAS_C \refineL_\pi S_A there exist two contexts ΓC\Gamma_C and ΓA\Gamma_A such that SA,ΓA⇝πSC,ΓCS_A, \Gamma_A \leadsto_\pi S_C, \Gamma_C. This proof proceeds by induction over the different CRE[MFOTL] refinement rules for ⇝π\leadsto_\pi. We show by induction on ⇝π\leadsto_\pi that when SA,ΓA⇝πSC,ΓCS_A, \Gamma_A \leadsto_\pi S_C, \Gamma_C and ∃EA.∀σ∈T.σ∈L(SA)\exists \Enforcer_A. \forall \sigma \in \Traces. \sigma \in \Language(S_A) then there exist two enforcement event systems ΞC\EventSystem_C and ΞA\EventSystem_A such that ΞC\EventSystem_C is sound for SCS_C, ΞA\EventSystem_A is sound for SAS_A, and ΞC⊑d(π)ΞA\EventSystem_C \refineL_{\dConv(\pi)} \EventSystem_A.

In the rest of this proof, let Rπ⊆TsC×TsAR_\pi \subseteq \Traces_{\sys C} \times \Traces_{\sys A} be the simulation relation defined by d(π)→:TsC→TsA\overrightarrow{\dConv(\pi)}: \Traces_{\sys C} \to \Traces_{\sys A}.

REFL In this case SC=SAS_C = S_A and π\pi is the identity mapping. By Theorem 3.25 we know that Ξ(EA)\EventSystem(\Enforcer_A) is sound for SAS_A. Finally, any enforcement event system Ξ(EA)\EventSystem(\Enforcer_A) is trivially a refinement of itself under the identity mapping (and the identity simulation relation).

TRANS For this case we can simply apply the induction hypothesis twice.

REF We know that two enforcers EC\Enforcer_C that is sound for SCS_C exists (Theorems 3.35) and that its induced event Systems are also sound for SCS_C (3.25).

It remains to be shown that the two induced event systems refine each other.

Let’s consider the situation in point 2 of Definition 3.28. We have two concrete system traces σsC,σsC′∈TsC\sigma_{\sys C}, \sigma_{\sys C}' \in \Traces_{\sys C}, one abstract system trace σsA∈TsA\sigma_{\sys A} \in \Traces_{\sys A}, and a concrete event eC∈ECe_C \in \Eventspace_C such that σsC→eCCσsC′\sigma_{\sys C} \Transitionrelation{C}{e_C} \sigma_{\sys C}'. And if this is the case we want to prove that there exists an abstract system trace σsA′∈TsA\sigma_{\sys A}' \in \Traces_{\sys A} such that σsA→d(π)(σsC,eC)AσsA′\sigma_{\sys A} \Transitionrelation{A}{\dConv(\pi)(\sigma_{\sys C}, e_C)} \sigma_{\sys A}'.

We can argue that the abstract enforcement event system can iteratively be defined by applying the mediator function d(π)\dConv(\pi) to all traces and transitions of the concrete enforcement event system. A transition σsC→eCCσsC′\sigma_{\sys C} \Transitionrelation{C}{e_C} \sigma_{\sys C}' would then become d(π)→(σsC)→d(π)(σsC,eC)Ad(π)→(σsC′)\overrightarrow{\dConv(\pi)}(\sigma_{\sys C}) \Transitionrelation{A}{\dConv(\pi)(\sigma_{\sys C}, e_C)} \overrightarrow{\dConv(\pi)}(\sigma_{\sys C}'). And the simulation relation RR can be defined by the aforementioned RπR_\pi. We call the so constructed enforcement event system ΞA\EventSystem_A. The event system ΞA\EventSystem_A is sound for SAS_A because of Theorem 3.36.

IMPR_R This rule simply strengthens a policy and thus reduces the set of "allowed" traces. By Theorem 3.35 we know that there exists an enforcer EC\Enforcer_C that is sound for SCS_C. By the fact that L(SC)⊆L(SA)\Language(S_C) \subseteq \Language(S_A) we can deduce that EC\Enforcer_C is also sound for SAS_A. And thus the induced event system for EC\Enforcer_C is sound for both SCS_C and SAS_A, and also a refinement of itself.

IMPC_C and IMPE_E Without loss of generality we will only consider the case of IMPC_C. The case of IMPE_E is analogous. This rule strengthens or weakens the definition of an internal event alongside the addition of a new, enforceable regulative rule. The regulative rule, like in the IMPR_R case, reduces the set of "allowed" traces. The strengthened or weakened definition has the effect that the defined event will occur less or more often, but under the (anti) monotonicity constraints it is ensured that the missing or extra occurrences of the event cannot affect compliance.

The event systems ΞC\EventSystem_C and ΞA\EventSystem_A can be simply constructed by inducing them from the sound enforcers EC\Enforcer_C and EA\Enforcer_A which we know must exist. Then we can build up the simulation relation RR, by iteratively following all possible transitions and adding the created trace pairs to RR. e.g. starting with the empty trace, we check what trace the concrete enforcement event system ΞC\EventSystem_C would produce when the event ee occurs and what trace the abstract enforcement event system ΞA\EventSystem_A would produce when the event ee occurs, and then we add the pair of resulting traces to RR. ◻

Implementation

Introduction

This chapter explores the changes and additions to the Lex language to include CRE[MFOTL] refinement from Chapter 3. With refinement in Lex, an existing and possibly fairly abstract legal formalization can be refined to more closely match a concrete system. First we introduce the new language features introduced for refinement, and then we explore those features in more detail by refining the EU ePrivacy Directive example in Lex.

Refinement of Lex Specifications

Refinement introduces a number of new statements in Lex. Lex refinement files use the file extension .rex. For refinement, we made the following additions to Lex.

Event Refinement

Refinement rules work almost exactly like constitutive rules. The main difference is that the refined event in a refinement rule is not an internal event like the constituted event in a constitutive rule, but it is a non-internal event that gets internalized by the refinement. The following example shows how this can be expressed as a refinement rule. Note the use of the refine keyword to indicate that this is a refinement rule. rulewheneverconsentByEmail(u,s) OR consentByButton(u,s)refineconsent(u,s)\begin{aligned} &\htmlClass{tok-kw}{\texttt{rule}} \\ &\quad \htmlClass{tok-kw}{\texttt{whenever}} \\ &\qquad \texttt{consentByEmail(u,s)}~\htmlClass{tok-kw}{\texttt{OR}}~\texttt{consentByButton(u,s)} \\ &\quad \htmlClass{tok-kw}{\texttt{refine}} \\ &\qquad \texttt{consent(u,s)} \end{aligned} In refinement the conditions must have at least the same capability as the refined event.

Assumptions are in essence syntactic shortcuts for refinement rules that have the condition true or false. assume true objectToSimilarEmailMarketing\begin{aligned} &\htmlClass{tok-kw}{\texttt{assume}}~\htmlClass{tok-id}{\texttt{true}}~\texttt{objectToSimilarEmailMarketing} \end{aligned} means that we assume that every user u has objected to receiving marketing emails from the sender s about products or services in category c. And this assumption could also be written as rulewhenevertruerefineobjectToSimilarEmailMarketing(u, s, c)\begin{aligned} &\htmlClass{tok-kw}{\texttt{rule}} \\ &\quad \htmlClass{tok-kw}{\texttt{whenever}} \\ &\qquad \htmlClass{tok-id}{\texttt{true}} \\ &\quad \htmlClass{tok-kw}{\texttt{refine}} \\ &\qquad \texttt{objectToSimilarEmailMarketing(u, s, c)} \end{aligned}

Rule Strengthening and Weakening

Replacement rules are structured and written very similarly to other Lex rules. They consist of a reference to an old rule and one or more references to new rules replacing the old one. Refinement rules have the form replace(strengthen∣weaken)[old rule reference]by[new rule reference(s)]\begin{aligned} & \htmlClass{tok-kw}{\texttt{replace}} \\ & \quad (\htmlClass{tok-kw}{\texttt{strengthen}} \mid \htmlClass{tok-kw}{\texttt{weaken}}) \\ & \qquad \text{[old rule reference]} \\ & \quad \htmlClass{tok-kw}{\texttt{by}} \\ & \qquad \text{[new rule reference(s)]} \end{aligned} Rule replacement is the Lex equivalent to the implication (IMP) rules from CRE[MFOTL] in Figure 3.3.

Strengthening Obligations One obligation rule can be replaced by one or more obligations that are at least as strong as the old obligation. Any exception that applied to the old obligation will directly apply to the new obligations. Weakening of obligations is not allowed, because then the refined specification would not correctly implement the old one. This corresponds to the impR\textsc{imp}_R rule in Figure 3.3.

Replacing Constitutive Rules A single constitutive rule can be replaced by a single constitutive rule and zero or more obligations. Any exception to the old constitutive rule will apply to the new constitutive rule, but not the new obligations. This corresponds to the impC\textsc{imp}_C rule in Figure 3.3. A constitutive rule can only be strengthened, if the constitutive event appears monotonically in the old Lex specification, and it can only be weakened if the constitutive event appears anti-monotonically in the old Lex specification. This is condition is necessary, because strengthening a constitutive rule means that under the stronger rule, the constituted event might occur less frequently and under a weaker rule it might occur more frequently. The (anti) monotonicity condition guarantees that, what in essence is the removal (or addition) of event occurrences in the refined specification, cannot affect whether a trace complies with a specification or not.

Replacing Exceptions Analogous to the replacement of constitutive rules, a single exception can be replaced by a single exception and zero or more obligations. This is analogous to the impE\textsc{imp}_E rule in Figure 3.3. Like with constitutive rules, the internally created exception event, must appear either monotonically or anti-monotonically in the old Lex specification such that it can be strengthened or weakened respectively.

Implementation in the Lex Compiler

.lexlextlexelexclex.rexrextrexerexMFOTLparseparsetype termscompute labelsfind exceptionssortcheck ℂ/𝕊compile CREtype termscheck:- rule replacements - mono. contrs.insert assumptionscheck:- event refinements- mono. constrs.linearize
Fig 4.1Structure of the Lex compiler [12, Figure 13]

We implemented these changes and additions to Lex in the Lex compiler 1. The changes amount to about 900 lines of OCaml code. The additions are mainly concentrated in the two files src/rtyping.ml and src/refinement.ml. The structure of the Lex compiler is shown in Figure 4.1.

The step from rex to trex is implemented in the src/rtyping.ml file. In this step terms get type checked, i.e. arguments to functions and event parameters. Also section labels get computed. Finally, the replacement of rules gets checked on the criteria explained in Section 4.2.2. However, monotonicity depends on the topological ordering, it can only be determined whether an event appears monotonically or anti-monotonically in the Lex specification when all its occurrences in the specification are known. Therefore, a set of monotonicity constraints gets computed in this step and forwarded to the next step.

The step from trex to erex is implemented in the src/refinement.ml file. During this step newly refined events get internalized and the capabilities of their new definitions get checked. Assumptions get unfolded into refinement rules and. The forwarded monotonicity constraints get checked based on the topological order. Also in this step, the "inherited" exceptions from replaced rules get correctly mapped to the new rules.

Case Study

Refinement of the EU ePrivacy Directive in Lex

Article 13(1) Refined for an email-only system automatedCommunication marketingConsent oblige email fax × assume false automatedCall × assume false ¬userWithdrawsConsent S userGivesConsent over18 + added Article 13(1) → email-only system automatedCommunication email fax automatedCall × assume false (both) oblige marketingConsent ¬userWithdrawsConsent S userGivesConsent over18 + added
Refinement of Article 13(1) from Figures 2.11 and 5.1. In an email-only system, fax and automatedCall are assumed never to occur, consent means given and not withdrawn since, and over18 is added as a new obligation. Illustration added for the web version.

Refinement of a Lex Specification

refine epd

refine type person is string

observable event userGivesConsent
    """person {s} gives consent to receive automated marketing communication from person {r}"""
    r: person
    s: person

observable event userWithdrawsConsent
    """person {s} withdraws consent to receive automated marketing communication from person {r}"""
    r: person
    s: person

rule "refine marketing consent"
    whenever
        (NOT userWithdrawsConsent(r, s)) SINCE userGivesConsent(r, s)
    refine
        marketingConsent(r, s)

assume true objectToSimilarEmailMarketing
assume true isNaturalPerson
assume false fax
assume false automatedCall

observable event over18
    """person {r} is over 18 years old"""
    r: person

rule "stronger_consent"
    whenever
        automatedCommunication(s, r, "marketing", c)
    oblige
        marketingConsent(r, s)
        over18(r)
    enforceable suppressing automatedCommunication

replace
    strengthen
        article "13" paragraph "1"
    by
        rule "stronger_consent"
Fig 5.1Lex Refinement of Figure 2.11

Figure 5.1 shows one possible refinement of the Lex specification from Figure 2.11. This Lex refinement refines the meaning of prior consent via a refinement rule. This refinement rule is more closely modeled after how a concrete system might implement what it means that a user has given consent at a certain point in time. Specifically, it combines two new concrete events, one for giving and for withdrawing consent.

The type for the data type of person, which was left open in the original Lex specification, is declared as a string.

It is assumed that all users are natural persons, and out of caution it is also assumed that all users have objected to receiving marketing about related products.

The fax and automated call events are assumed to never occur, which would represent many modern systems that do not even have these a fax or automated phone attached.

An event is introduced to represent that a user is over 18 years old. And the obligation rule about receiving unsolicited marketing that disallows sending any marketing emails to users under 18, regardless of whether they have given consent.

Pretix

Pretix [2] is an open source event ticketing system written in Python and built on Django. It offers products for ticket sales, wait lists, on location ticket sales, and ticket scanning. We are interested in the pre-event ticket sales part. We evaluated a refined Lex formalization of the email marketing regulations in the EU ePrivacy Directive on the Pretix platform.

Instrlib [11] is a python library for instrumenting Python programs for enforcement with the EnfGuard [9] enforcer. It has been designed to facilitate especially seamless instrumentation of Django applications. Instrlib takes over the interaction between EnfGuard and an instrumented program. During this thesis, while working on the case-study, we extended the logger in Instrlib with a cache. The cache has an adjustable timeout value, and serves the purpose that when the same event gets queried multiple times in quick succession, its corresponding values do not have to be recomputed every time, since they are unlikely to have changed. In some cases this can considerably reduce the delay that enforcement introduces.

For this, we modified Pretix and instrumented this version of it with Instrlib 2 3. The modifications to Pretix consist of new fields to the customer model indicating consent to receive marketing emails, and modified views to give and withdraw this consent.

Pretix stores customer emails in the order data model and the customer data model for users that create an account. We have instrumented the email fields of these two model classes, such that accessing them might get suppressed if needed. Further we annotated the function for sending emails with the "marketing" purpose and we annotated our newly added consent checkbox in such a way that updating the marketing consent value, triggers an event that gets reported to Instrlib and the enforcer.

Pretix is a large and feature rich solution for ticket sales and event organization. It has other aspects that might be interesting for enforcement testing in the future, such as its wait list, which might fall under data minimization requirements.

Lessons Learned

Formalizing any regulation in Lex requires a good understanding of the intended purpose of the regulation and a certain amount of creativity in how to model which concepts. In this case study, the addition of refinement allowed us to move certain complexities, such as the implementation of consent, out of the original Lex specification and to move them into the refinement file. Even with a relatively small example, our approach appears to be highly promising, and its advantages should only become more apparent in larger projects.

Another aspect that has become clear is that in order to write a good and useful refinement mapping, a good level of understanding of the underlying code base is required. One must know which actions are performed where and how. To implement the actual interaction with the enforcer, an integrated solution like Instrlib has proved very helpful.

During basic testing of the instrumented Pretix code base, one tricky challenge has been not to instrument too much. If a part of the code gets instrumented that is frequently accessed, every access must go through the enforcer, which can quickly add very long delays. We added a cache to Instrlib to mitigate this issue, but it remains that the fewer parts of the code that have to be instrumented to successfully enforce a policy, the less noticeable the presence of the enforcer becomes. Determining which parts must always be logged and which parts can be safely ignored (sometimes) without losing soundness.

Conclusion

Motivated by the need for reusable and adaptable legal specifications in runtime enforcement, this thesis presents the addition of refinement to Lex. Refinement in Lex is a flexible and powerful mechanism to adapt and reuse an existing Lex specification for different use cases. Our refinement rules for Lex ensure That a valid refinement of an enforceable Lex specification is also enforceable.

In Chapter 3 we have introduced our refinement rules, and we have connected them to the long-standing concept of specification refinement. Specifically we have shown it to be analogous to the refinement notion for event systems used by Sprenger et al. [17]. For this purpose, we have modeled proactive enforcement as an event system with labeled transitions. In Chapter 4 we have implemented the refinement rules for the CRE[MFOTL] logic introduced in Chapter 3 in Lex. Finally, Chapter 5 presents a case study that demonstrates a possible use case for refinement in Lex based on the ePrivacy Directive [1] and the Pretix ticketing system [2].

To our knowledge, Lex is the first specification language for legal norms that supports an inheritance-like feature such as refinement.

In the future Lex refinement could be extended to be even more flexible in what it allows, like defining new global exceptions or step-wise refinement, where multiple Lex refinement specifications iterate on each other. Stepwise refinement should be a relatively simple change to the Lex compiler. This could allow for interesting use cases, one person (or more likely group of people) could formalize and carefully audit a law like the GDPR, another could refine it for a specific class of applications, say social media apps, and then finally any social media provider could refine the already refined specification even further. An ecosystem of downloadable Lex specifications, like package management in general purpose programming languages, could be built around Lex and Lex refinement.

One important challenge that Lex and Lex refinement do not solve entirely is the issue of correctness. Lex does provide logical correctness, i.e. it ensures that a type correct Lex specification is enforceable under the given capabilities for events, it also ensures that enforceability is transitive through its refinement system. But what Lex does not and cannot ensure is that a Lex specification correctly captures the intended meaning of a legal norm. It also cannot ensure that a refinement maintains and does not change the semantic meaning of a formalization. Lex attempts to make auditing a formalization as convenient as possible, thus reducing the error probability in specifications, but this does require careful evaluation by humans and more likely, legal experts. With the continued rise of artificial intelligence and large language models, it might become easier to automate the extraction of the logical structure of legal norms in an automated fashion. However, even such systems cannot currently ensure that a formalization correctly represents an underlying law automatically. This remains a large unsolved problem that may well be unsolvable as long as laws are written in natural language that is inherently imprecise. Both by necessity and design, Lex tries to give a readable method for representing the logical structure of legal norms which is subject to human interpretation.

Compiled Lex Examples

The compiled output of the ePrivacy Directive formalization in Lex (Figure 2.11) is shown in Figure A.1 and Figure A.2. The compilation of the refined specification from Figure 5.1 is shown in Figure A.3 and Figure A.4.

automatedCall(r: int, s: int, p: string, c: string)+-
email(r: int, s: int, p: string, c: string)+-
fax(r: int, s: int, p: string, c: string)+-
isNaturalPerson(s: int)
marketingConsent(r: int, s: int)
objectToSimilarEmailMarketing(r: int, s: int, c: string)
obtainedEmailForCategory(r: int, s: int, c: string)
Fig A.1Compiled MFOTL Signature of the Lex Specification
LET automatedCommunication(_p1 : int, _p2 : int, _p3 : string
                                                 _p4 : string)- =
    email(_p1, _p2, _p3, _p4) ∨\vee fax(_p1, _p2, _p3, _p4)
    ∨\vee automatedCall(_p1, _p2, _p3, _p4) IN
LET Exception4(c : string, r : int, s : int) =
    obtainedEmailForCategory(r, s, c)
    ∧\wedge ¬\negobjectToSimilarEmailMarketing(r, s, c) IN
LET Scope5(r : int) = isNaturalPerson(r) IN
□⁡\Always[0s,∞\infty) (
    ∀\forallc. ∀\forallr. ∀\foralls. automatedCommunication(s, r, "marketing", c
        ∧\wedge:L ¬\negException4(c, r, s) ∧\wedge Scope5(r)
    →\to:L marketingConsent(r, s))
Fig A.2Compiled MFOTL formula of the Lex Specification
email(r: string, s: string, p: string, c: string)+-
obtainedEmailForCategory(r: string, s: string, c: string)
over18(r: string)
userGivesConsent(r: string, s: string)
userWithdrawsConsent(r: string, s: string)
Fig A.3Compiled MFOTL Signature of the refined Lex Specification
LET automatedCall(_p11 : string, _p12 : string, _p13 : string,
                  _p14 : string) = ⊥\bot IN
LET fax(_p15 : string, _p16 : string, _p17 : string, _p18 : string)
    = ⊥\bot IN
LET isNaturalPerson(_p19 : string) = ⊤\top IN
LET marketingConsent(_p9 : string, _p10 : string) =
    ¬\neguserWithdrawsConsent(_p9, _p10)
    S[0s,∞\infty) userGivesConsent(_p9, _p10) IN
LET objectToSimilarEmailMarketing(_p20 : string, _p21 : string,
                                  _p22 : string) = ⊤\top IN
LET Exception4(c : string, r : string, s : string) =
    obtainedEmailForCategory(r, s, c)
    ∧\wedge ¬\negobjectToSimilarEmailMarketing(r, s, c) IN
LET automatedCommunication(_p5 : string, _p6 : string, _p7 :
                           string, _p8 : string)- =
    email(_p5, _p6, _p7, _p8) ∨\vee fax(_p5, _p6, _p7, _p8)
    ∨\vee automatedCall(_p5, _p6, _p7, _p8) IN
LET Scope5(r : string) = isNaturalPerson(r) IN
□⁡\Always[0s,∞\infty) (
    ∀\forallc. ∀\forallr. ∀\foralls. automatedCommunication(s, r, "marketing", c)
        ∧\wedge:L ¬\negException4(c, r, s) ∧\wedge Scope5(r)
    →\to:L marketingConsent(r, s) ∧\wedge over18(r))
Fig A.4Compiled MFOTL formula of the refined Lex Specification

Additional Proofs

Proof for Lemma 3.26

Proof. Let σs∈Ts\sigma_\sys \in \Traces_\sys and τ∈N\tau \in \Nat. The proof for Lemma 3.26 proceeds by structural induction over system traces σs∈Ts\sigma_\sys \in \Traces_\sys.

  • Base Case σs=εs\sigma_\sys = \emptytrace_\sys c′(τ,σs⋅D)=c′(τ,εs⋅D)=c′(τ,D)=ε⋅c′(τ+0,D)=?ε⋅c′(τ+#tick(εs),D)=?c′(0,εs)⋅c′(τ+#tick(εs),D)=c′(0,σs)⋅c′(τ+#tick(σs),D)\begin{aligned} \cConv'(\tau, \sigma_\sys \cdot D) &= \cConv'(\tau, \emptytrace_\sys \cdot D) \\ &= \cConv'(\tau, D) \\ &= \emptytrace \cdot \cConv'(\tau + 0, D) \\ &\stackrel{\text{?}}{=} \emptytrace \cdot \cConv'(\tau + \numTicks(\emptytrace_\sys), D) \\ &\stackrel{\text{?}}{=} \cConv'(0, \emptytrace_\sys) \cdot \cConv'(\tau + \numTicks(\emptytrace_\sys), D) \\ &= \cConv'(0, \sigma_\sys) \cdot \cConv'(\tau + \numTicks(\sigma_\sys), D) \end{aligned}

  • Induction Hypothesis

    For any true suffix σs′\sigma_\sys' of σs\sigma_\sys (i.e. ∣σs′∣<∣σs∣|\sigma_\sys'| < |\sigma_\sys|) c′(τ,σs′⋅D)=c′(τ,σs′)⋅c(τ+#tick(σs′),D).\cConv'(\tau, \sigma_\sys' \cdot D) = \cConv'(\tau, \sigma_\sys') \cdot \cConv(\tau + \numTicks(\sigma_\sys'), D).

  • Induction Step

    We make a case distinction based on σs\sigma_\sys. Without loss of generality we can assume that there are no skip\sskip events in σs\sigma_\sys.

    • σs=tickk\sigma_\sys = \tick^k c′(τ,σs⋅D)=c′(τ,tickk⋅D)=?(τ+k,D)=ε⋅(τ+k,D)=?c(τ,εs)⋅(τ+k,D)=c(τ,tickk)⋅(τ+k,D)=c(τ,σs)⋅(τ+k,D)=?c(τ,σs)⋅c′(τ+k,D)=c(τ,σs)⋅c′(τ+#tick(σs),D)\begin{aligned} \cConv'(\tau, \sigma_\sys \cdot D) &= \cConv'(\tau, \tick^k \cdot D) \\ &\stackrel{\text{?}}{=} (\tau + k, D) \\ &= \emptytrace \cdot (\tau + k, D) \\ &\stackrel{\text{?}}{=} \cConv(\tau, \emptytrace_\sys) \cdot (\tau + k, D) \\ &= \cConv(\tau, \tick^k) \cdot (\tau + k, D) \\ &= \cConv(\tau, \sigma_\sys) \cdot (\tau + k, D) \\ &\stackrel{\text{?}}{=} \cConv(\tau, \sigma_\sys) \cdot \cConv'(\tau+k, D) \\ &= \cConv(\tau, \sigma_\sys) \cdot \cConv'(\tau+ \numTicks(\sigma_\sys), D) \end{aligned}

    • σs=tickk⋅D′⋅σs′\sigma_\sys = \tick^k \cdot D' \cdot \sigma_\sys' c′(τ,σs⋅D)=c′(τ,tickk⋅D′⋅σs′⋅D)=?(τ+k,D′)⋅c′(τ+k,σs′⋅D)=IH(τ+k,D′)⋅c′(τ+k,σs′)⋅c′(τ+k+#tick(σs′),D)=(τ+k,D′)⋅c′(τ+k,σs′)⋅c′(τ+#tick(σs),D)=?c′(τ,tickk⋅D′⋅σs′)⋅c′(τ+#tick(σs),D)=c′(τ,σs)⋅c′(τ+#tick(σs),D)\begin{aligned} \cConv'(\tau, \sigma_\sys \cdot D) &= \cConv'(\tau, \tick^k \cdot D' \cdot \sigma_\sys' \cdot D) \\ &\stackrel{\text{?}}{=} (\tau+k, D') \cdot \cConv'(\tau+k, \sigma_\sys' \cdot D) \\ &\stackrel{IH}{=} (\tau+k, D') \cdot \cConv'(\tau+k, \sigma_\sys') \cdot \cConv'(\tau+k+\numTicks(\sigma_\sys'), D) \\ &= (\tau+k, D') \cdot \cConv'(\tau+k, \sigma_\sys') \cdot \cConv'(\tau+\numTicks(\sigma_\sys), D) \\ &\stackrel{\text{?}}{=} \cConv'(\tau, \tick^k \cdot D' \cdot \sigma_\sys') \cdot \cConv'(\tau+\numTicks(\sigma_\sys), D) \\ &= \cConv'(\tau, \sigma_\sys) \cdot \cConv'(\tau+\numTicks(\sigma_\sys), D) \end{aligned}

 ◻

Proof for Lemma 3.27

Proof. The proof for Lemma 3.27 proceeds by structural induction over finite system traces σs∈tracesf(Ξ(E),εs)\sigma_\sys \in \EStraces_f(\EventSystem(\Enforcer), \emptytrace_\sys). Later we will make the argument why the property extends to inifinite system traces too. Without loss of generality we can assume that σs∈trim(Ts)\sigma_\sys \in \trim(\Traces_{\sys}), because the conversion function c\cConv removes implicitly trims system traces. Let E=(S,s0,μ)\Enforcer = (\EnfStates, s_0, \mu) be an enforcer.

  • Base Case σs=εs\sigma_\sys = \emptytrace_\sys c(σs)=c(εs)=?ε=E(ε)\begin{aligned} \cConv(\sigma_\sys) = \cConv(\emptytrace_\sys) \stackrel{\text{?}}{=} \emptytrace = \Enforcer(\emptytrace) \end{aligned} The final equality follows from Algorithm 1 which defines, that enforcing the empty trace returns the empty trace.

  • Induction Hypothesis For all true prefixes σs′\sigma_\sys' of σs∈tracesf(Ξ(E),εs)\sigma_\sys \in \EStraces_f(\EventSystem(\Enforcer), \emptytrace_\sys) (i.e. ∣σs′∣<∣σs∣|\sigma_\sys'| < |\sigma_\sys|) there exists a trace σ′∈T\sigma' \in \Traces such that c(σs′)=E(σ′)\cConv(\sigma_\sys') = \Enforcer(\sigma').

  • Induction Step

    We make a case distinction based on the two possible transitions of enforcement event systems from Definition 3.19. The update functions δ\RFun and γ\PFun are defined as in Definition 3.22.

    • σs=σs′⋅δ(σs′,D)\sigma_\sys = \sigma_\sys' \cdot \RFun(\sigma_\sys', D) c(σs)=c(σs′⋅δ(σs′,D))=?c′(0,σs′⋅δ(σs′,D))=?c′(0,σs′)⋅c′(#tick(σs′),δ(σs′,D))=?c(σs′)⋅c′(#tick(σs′),δ(σs′,D))=IHE(σ′)⋅c′(#tick(σs′),δ(σs′,D))=?,?E(σ′)⋅(#tick(σs′),δ(σs′,D))=E(σ′⋅(#tick(σs′),D))\begin{aligned} \cConv(\sigma_\sys) &= \cConv(\sigma_\sys' \cdot \RFun(\sigma_\sys', D)) \\ &\stackrel{\text{?}}{=} \cConv'(0, \sigma_\sys' \cdot \RFun(\sigma_\sys', D)) \\ &\stackrel{\text{?}}{=} \cConv'(0, \sigma_\sys') \cdot \cConv'(\numTicks(\sigma_\sys'), \RFun(\sigma_\sys', D)) \\ &\stackrel{\text{?}}{=} \cConv(\sigma_\sys') \cdot \cConv'(\numTicks(\sigma_\sys'), \RFun(\sigma_\sys', D)) \\ &\stackrel{IH}{=} \Enforcer(\sigma') \cdot \cConv'(\numTicks(\sigma_\sys'), \RFun(\sigma_\sys', D)) \\ &\stackrel{\text{?}, \text{?}}{=} \Enforcer(\sigma') \cdot (\numTicks(\sigma_\sys'), \RFun(\sigma_\sys', D)) \\ &= \Enforcer(\sigma' \cdot (\numTicks(\sigma_\sys'), D)) \end{aligned} The final step follows from the definition of the reactive update function δ\RFun by means of the enforcer update function μ\mu and how μ\mu is used by in lines 6 and 7 of Algorithm 1 to issue an RCom\RCom-command.

    • σs=σs′⋅γ(σs′)⋅tick\sigma_\sys = \sigma_\sys' \cdot \PFun(\sigma_\sys') \cdot \tick c(σs)=c(σs′⋅γ(σs′)⋅tick)=?c(σs′⋅γ(σs′))=?c′(0,σs′⋅γ(σs′))=?,skipc′(0,σs′)⋅c′(#tick(σs′,γ(σs′)))=?c(σs′)⋅c′(#tick(σs′,γ(σs′)))=IHE(σ′)⋅c′(#tick(σs′,γ(σs′)))={E(σ′)if γ(σs′)=skipE(σ′⋅(#tick(σs′),D))if γ(σs′)=D\begin{aligned} \cConv(\sigma_\sys) &= \cConv(\sigma_\sys' \cdot \PFun(\sigma_\sys') \cdot \tick) \\ &\stackrel{\text{?}}{=} \cConv(\sigma_\sys' \cdot \PFun(\sigma_\sys')) \\ &\stackrel{\text{?}}{=} \cConv'(0, \sigma_\sys' \cdot \PFun(\sigma_\sys')) \\ &\stackrel{\text{?}, \sskip}{=} \cConv'(0, \sigma_\sys') \cdot \cConv'(\numTicks(\sigma_\sys', \PFun(\sigma_\sys'))) \\ &\stackrel{\text{?}}{=} \cConv(\sigma_\sys') \cdot \cConv'(\numTicks(\sigma_\sys', \PFun(\sigma_\sys'))) \\ &\stackrel{IH}{=} \Enforcer(\sigma') \cdot \cConv'(\numTicks(\sigma_\sys', \PFun(\sigma_\sys'))) \\ &= \begin{cases} \Enforcer(\sigma') &\text{if } \PFun(\sigma_\sys') = \sskip \\ \Enforcer(\sigma' \cdot (\numTicks(\sigma_\sys'), D)) &\text{if } \PFun(\sigma_\sys') = D \end{cases} \end{aligned} Similarly to the reactive case above, the final step follows from how the proactive update function γ\PFun is defined by the enforcer update function μ\EnfFun and how μ\EnfFun is used by the enforcement algorithm to issue PCom\PCom and NoCom\NCom commands.

Finally, the finite case shows that there cannot exist an infinite system trace for which Lemma 3.27 does not hold. For any infinite trace σs∈tracesω(Ξ(E),εs)\sigma_\sys \in \EStraces_\omega(\EventSystem(\Enforcer), \emptytrace_\sys) we have shown that for all finite prefixes σs∣…i\sigma_{\sys |\dots i} with an arbitrary i∈Ni \in \Nat, there exists an MFOTL trace σf∈Tf\sigma_f \in \Traces_f such that c(σs∣…i)=E(σf)\cConv(\sigma_{\sys |\dots i}) = \Enforcer(\sigma_f). If, for some infinite trace σs∈tracesω(Ξ(E),εs)\sigma_\sys \in \EStraces_\omega(\EventSystem(\Enforcer), \emptytrace_\sys), there would not exist a trace σω∈Tω\sigma_\omega \in \Traces_\omega such that c(σs)=E(σω)\cConv(\sigma_\sys) = \Enforcer(\sigma_\omega), then there would exist some finite prefix σs∣…i∈tracesf(Ξ(E),εs)\sigma_{\sys |\dots i} \in \EStraces_f(\EventSystem(\Enforcer), \emptytrace_\sys) such that there also does not exist a trace σf∈Tf\sigma_f \in \Traces_f such that c(σs∣…i)=E(σf)\cConv(\sigma_{\sys |\dots i}) = \Enforcer(\sigma_f). ◻

Use of Generative AI Tools

AI Tool Use Case Scope Remarks
image GitHub Copilot Code completion, Code suggestions, Error explanations, Exploring code base Lex code base: OCaml, JavaScript Report: LaTeX (error explanations) Various models: GPT-4.1, GPT-4o, o3-mini, Claude 3.5 Sonnet, Gemini 2.0 Flash, Gemini 2.0 Pro
image DeepL Write Correction of grammatical mistakes, styling Entire report Free Trial
image OpenAI ChatGPT Brainstorming, "interactive" web search Introduction "Deep Research" mode
Fig C.1Overview of AI tools used in this thesis

References

  1. Directive 2002/58/EC of the European Parliament and of the Council. Of 12 July 2002 Concerning the Processing of Personal Data and the Protection of Privacy in the Electronic Commu- Nications Sector (Directive on Privacy and Electronic Communications). 2002. Official Journal of the European Union. Vol. L 201. http://data.europa.eu/eli/dir/2002/58/oj.
  2. “Pretix – Reinventing Ticket Sales for Conferences, Festivals, Exhibitions, ...” n.d. https://pretix.eu/about/en/. Accessed May 29, 2025.
  3. Abadi, Martı́n, and Leslie Lamport. 1991. “The Existence of Refinement Mappings.” Theoretical Computer Science 82 (2): 253–84.
  4. Basin, David, Felix Klaedtke, Srdjan Marinovic, and Eugen Zălinescu. 2013. “Monitoring of Temporal First-Order Properties with Aggregations.” In Runtime Verification: 4th International Conference, RV 2013, Rennes, France, September 24-27, 2013. Proceedings 4, 40–58. Springer.
  5. Basin, David, Felix Klaedtke, Samuel Müller, and Eugen Zălinescu. 2015. “Monitoring Metric First-Order Temporal Properties.” Journal of the ACM (JACM) 62 (2): 1–45.
  6. Brewka, Gerhard, and Thomas Eiter. 2000. “Prioritizing Default Logic.” In Intellectics and Computational Logic: Papers in Honor of Wolfgang Bibel, 27–45. Springer.
  7. Chomicki, Jan. 1995. “Efficient Checking of Temporal Integrity Constraints Using Bounded History Encoding.” ACM Transactions on Database Systems (TODS) 20 (2): 149–86.
  8. Degelo, Jonas. 2024. “A Language for Formalizing Legal Provisions.” Talk
  9. Hublet, François, Leonardo Lima, David Basin, Srđan Krstić, and Dmitriy Traytel. 2024. “Proactive Real-Time First-Order Enforcement.” In International Conference on Computer Aided Verification, 156–81. Springer.
  10. ———. 2025. “Scaling Up Proactive Enforcement.” In International Conference on Computer Aided Verification, edited by Ruzica Piskac and Zvonimir Rakamaric. Springer.
  11. Hublet, François, Linda Hu, David Basin, and Srđan Krstić. 2025. “Instrumenting Runtime Enforcement.” ETH Zürich, Department of Computer Science.
  12. Hublet, François, Jakob Merane, Jonas Degelo, Wei-En Hsieh, Srđan Krstić, and David Basin. 2026. “Lex: Turning Laws into Enforceable Security Policies.” In ACM Conference on Computer and Communications Security (CCS 2026). https://doi.org/10.1145/3830454.3846777.In the submitted thesis: Hublet, François, Jakob Merane, Jonas Degelo, Linda Hu, David Basin, and Srđan Krstić. 2025. “Lex: A Tool-Supported Methodology for Compliance by Design.”
  13. Lancieri, Filippo. 2022. “Narrowing Data Protection’s Enforcement Gap.” Me. L. Rev. 74: 15.
  14. Ligatti, Jay, Lujo Bauer, and David Walker. 2005. “Edit Automata: Enforcement Mechanisms for Run-Time Security Policies.” International Journal of Information Security 4: 2–16.
  15. Merigoux, Denis, Nicolas Chataing, and Jonathan Protzenko. 2021. “Catala: A Programming Language for the Law.” Proceedings of the ACM on Programming Languages 5 (ICFP): 1–29. https://doi.org/10.1145/3473582.
  16. Schneider, Fred B. 2000. “Enforceable Security Policies.” ACM Trans. Inf. Syst. Secur. 3 (1): 30–50. https://doi.org/10.1145/353323.353382.
  17. Sprenger, Christoph, Tobias Klenze, Marco Eilers, Felix A Wolf, Peter Müller, Martin Clochard, and David Basin. 2020. “Igloo: Soundly Linking Compositional Refinement and Separation Logic for Distributed System Verification.” Proceedings of the ACM on Programming Languages 4 (OOPSLA): 1–31.
  18. Van Binsbergen, L Thomas, Lu-Chi Liu, Robert Van Doesburg, and Tom Van Engers. 2020. “eFLINT: A Domain-Specific Language for Executable Norm Specifications.” In Proceedings of the 19th ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences, 124–36.
  19. Zingg, Sheila, Srđan Krstić, Martin Raszyk, Joshua Schneider, and Dmitriy Traytel. 2022. “Verified First-Order Monitoring with Recursive Rules.” In International Conference on Tools and Algorithms for the Construction and Analysis of Systems, 236–53. Springer.