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
Legal Formalization
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"), ("previous"), ("until"), and ("since"). MFOTL is frequently utilized as a policy language in runtime verification [9, 12, 5].
Definition 2.1. An MFOTL Signature is a quadruple consisting of a value domain , a set of event names , a set of function names , and an arity function .
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 is an MFOTL signature.
Definition 2.3. An Event is a tuple where and all .
Example 2.4. are events over the signature from Example 2.2.
Definition 2.5. A Database is a set of events.
Definition 2.6. A Trace is a sequence , of timestamps and finite databases , where timestamps grow monotonically () and progress (if , then ).
Definition 2.7. The set of Infinite Traces is denoted by
Definition 2.8. The set of Finite Traces is denoted by
Definition 2.9. A time-point is an index in a trace .
Example 2.10. is a finite trace over the signature from Example 2.2 with 4 time-points. The 4 time-points have the timestamps , , , and .
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 .
Definition 2.12. The function gives the first time stamp in a trace unless it is empty.
Definition 2.13. The function gives the first time stamp in a trace unless it is empty.
For the trace in Example 2.10 we have and .
Definition 2.14. A Property is a subset .
A Property can be induced by some policy , we denote this policy by . We say a trace is compliant with policy if and only if .
Definition 2.15. The set of Non-Empty Intervals over is denoted by .
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 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 , , , , and . Then our MFOTL Grammar is defined by the following two rules
Definition 2.17. A variable Valuation assigns a value to a variable.
Definition 2.18. The Evaluation of well-typed MFOTL terms under some valuation is (recursively) defined as followed:
Definition 2.19. An MFOTL formula is satisfied at some time-point in a trace under some valuation is denoted by .
If the trace is obvious from context the subscript in can be omitted.
Definition 2.20. The Semantics of MFOTL for a fixed, infinite trace is defined as followed
Where , , , , and .
We define the following operators based on the basic operators above as "syntactic sugar".
Definition 2.21. MFOTL Syntactic Sugar
Definition 2.22. The Language of a MFOTL formula is
Example 2.23. An example of an MFOTL formula over the signature from Example 2.2 is
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
We consider the system model of Hublet et al. [9] which is shown in Figure 2.3. The system (under scrutiny) runs in some environment . The environment is not under the control of the enforcer . The enforcer must ensure that the system complies with some policy . 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 -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 -commands (proactively) by causing certain events at some time-stamp .
In the following the event names of events in sets denoted by are all assumed to be in and are all assumed to be in . 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 . This command is a reaction of the enforcer to some set of events , that the system sent to the enforcer. The trace of the enforced system will contain the set of events.
Definition 2.25. A P-Command has the form . This command can be proactively issued by the enforcer before any clock tick to issue the set of events .
Definition 2.26. No-Command has the form and indicates that the enforcer takes no action.
Definition 2.27. The set of all commands is .
This leads us to Hublet et al.’s [9, 10] definition of a proactive enforcer.
Definition 2.28. An Enforcer is a triple , where is a set of enforcer states is an initial enforcer state and is a computable update function such that the following two conditions hold
Hublet et al. [10] define an enforced trace algorithmically via Algorithm 1.
Definition 2.29. For any and enforcer , the enforced trace is defined co-recursively in Algorithm 1.
- case of
- when let in
- case of
- when let in
- case of
In Definition 2.29 the trace 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 is sound with respect to some property , iff for any trace , .
Definition 2.31. An enforcer is sound with respect to some policy , iff it is sound for the language .
Soundness allows us to describe and capture the behavior of an enforcer.
Definition 2.32. An enforcer is transparent with respect to some property iff for all , .
Definition 2.33. An enforcer is transparent with respect to some policy iff it is transparent for the language .
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 (), suppressable (), causable (), and suppressable-causable (). 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 is used to assign a capability to all events with some event name . Also in both contexts, capabilities form a (semi)-lattice .
Definition 2.34. The subset of Causable Events consists of all event names which can be caused by the enforcer, i.e. which have a capability of at least .
Definition 2.35. The subset of Suppressable Events consists of all event names which can be suppressed by the enforcer, i.e. which have a capability of at least .
Definition 2.36. The set of Causable Databases contains all sets of events that are at least causable.
Definition 2.37. The set of Suppressable Databases contains all sets of events that are at least suppressable.
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 of Example 2.2 could be extended with the following capabilities: 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.
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 .
Definition 2.39. A CRE[MFOTL] Signature is a quadruple of the following form Where is a domain of values, is a set of external event names, is a set of internal event names, is a set of function names, is an external arity funciton, and is an internal arity function. and 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 is denoted by .
Next we recall constitutive, regulative, and exception rules [12, Section 3.1].
| Rule Type | Syntax | Meaning |
|---|---|---|
| Constitutive | " counts as " | |
| Regulative | "if holds, then must hold" | |
| Exception | "if holds, then rule shall not apply" |
Definition 2.41. Let , , , , and . 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 where is a set of constitutive rules, is a set of regulative rules, and is a set of exception rules such that every rule in has a unique label.
Figure 2.7 defines the semantics of the CRE[MFOTL] logic. The semantics expand the logic of the CRE[MFOTL] logic is captured by . These semantics can be expanded to define compliance for an entire CRE-policy as followed.
Definition 2.43. A CRE-policy is complied with (), if all its regulative rules are complied with, which is captured in the rule:
Definition 2.44. A CRE Specification is a triple consisting of some signature , some CRE policy , and a capability-mapping .
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 of Example 2.23 could be captured in the following CRE[MFOTL] policy:
is a CRE[MFOTL] policy consisting of a single regulative rule .
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 let . (read as "s depends on r") iff either and occurs in the left-hand side of the rule , or .
A policy is called acyclic iff there do not exist two rules such that , and and also that there is no single rule that is self-referential (i.e. ). The compilation of CRE[MFOTL] to MFOTL is defined by Algorithm 2 and Algorithm 3.
- Input: with and acyclic CRE[MFOTL] policy
- for do endfor
- Output: where
- let collect =
- for do
- if then endif
- endfor
- return
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
| Lex | law ["title"] | [] event | rule | rule | rule |
article ["title"] | """<docstring>""" | whenever | whenever | whenever | |
paragraph … | : | ||||
point … | … | ||||
| … | : | ||||
constitute | oblige | except | |||
type [is ] | |||||
"""<docstring>""" | |||||
| CRE[MFOTL] | n.a. | ||||
| … | … | … | |||
Lex has the following main types of statements:
Section Labels (keywords:
law,title,chapter,section,article,paragraph,point,subpoint) Section labels are used to represent the structure of the law. Section label statements have the form of a section keyword followed by a mandatory string identifier and an optional, more descriptive, string title (e.g.article"1" "Preconditions"). Section labels (together with optional rule identifiers) are the analog of rule labels in CRE[MFOTL]. Section 2.3.2 will go more in depth on section labels in Lex.Type Declarations (keyword:
type) Type declarations map a type alias to a base type (e.g.typeuserisstring,typeageisint). These type aliases are not represented in CRE[MFOTL].Event Declarations (keywords:
event,predicate) Event declarations declare event names and their arguments along with their types.Function Declarations (keyword:
function) Function declarations are analogous to event declarations, but they define function names with their arguments and a return type.Rule Definitions (keyword:
rule) Rule definitions are the core of the Lexlanguage. They define the constitutive, regulative, and exception rules like in CRE[MFOTL]. Lexrules are more verbose than those in CRE[MFOTL] and allow for the use of keywords in addition to symbols for temporal/logical operators (e.g.ALWAYSfor ). A CRE[MFOTL] rule like becomserulewheneverconstitutein Lex. After therulekeyword, a rule can optionally be given a string identifier. Exception rules in Lexmake use of section labels and the optional rule identifiers to specify which rule(s) the apply to.Import Statements (keyword:
import) Import statements are used to modularly split a Lexspecification into multiple files. "importspecification" imports the specification in the file "specification.lex".
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
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.
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.
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 [...]
In any event, [...] disguising or concealing the identity of the sender [...] shall be prohibited.
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.
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: productCategorytype 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"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 consisting of a set of states , a set of events , and a transition relation .
can also be written as . Sprenger et. al [17] extend the transition relation for finite traces of events . As we already use for timestamps and for MFOTL traces, we use for event traces and 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 of events for all
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 .
Definition 2.50. Given a set of initial states a Trace of the event system starting in initial states is a trace of events such that for some initial state and a reachable state .
The set of all traces of an event system starting in initial states is denoted by .
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 with initial states for . refines modulo a mediator function , written as if there exists a simulation relation such that
for all there exists some such that , and
for all , and such that and there exists some such that .
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. implies
Proof. Let and . Let and .
We can prove Theorem 2.52 by structural induction over event system traces. We will show that for every trace its projection , is in .
Base Case: . The empty trace is part of any event system, and therefore . And further, for any inital state there exists there exists an initial state such that for which and. .
Induction Hypothesis For any trace with , . And there exists an initial state , a state , an initial state , and a state such that , , , and .
Inductive Step: . Since we covered the empty trace in the base case, we have . Thus we can assume that for some . By the Induction Hypothesis we have that .
By the induction hypothesis we have that is a trace of the event system . Also by induction hypthesis we have that there exist , , , and such that , , , and . By definition of as and the assumption that we have that for some . By point 2 of Definition 2.51 we have that there exists a state such that . Thus and also .
◻
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 is a set of traces over events .
denotes that the event system .
Next we recall Sprenger et. al [17, Lemma 2.2].
Lemma 2.54. Suppose and , then
Proof. is equivalent to . Thus ◻
Legal Background
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 , and another formula refines , then there exists a sound enforcement event system for . Separately we will show that there exists a sound enforcement event system for some MFOTL formula if and only if there exists a sound enforcer, as defined in chapter 2 for . 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 is a finite or infinite sequence of events where for every ,
The special event represents a clock tick in the system. As a more compact notation we use for all and . Note that for , .
Definition 3.2. The function
gives the number of ticks in a system sequence.
The 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
removes all events from the end of a system sequence that are not followed by a database.
For sets of system sequences , .
Definition 3.4. A System Trace is a finite or infinite system sequence where the number of ticks progresses with the number of databases (if , then ).
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
gives the number of database events in a system trace.
We say a system trace is finite iff and it is infinite iff . We use , , and to denote the sets of finite system traces, infinite system traces, and all system traces respectively. denotes an empty system trace.
Lemma 3.6. For any infinite system trace ,
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 .
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.
Definition 3.8. The System Trace Converter Function converts system traces starting at timestamp to MFOTL traces.
Definition 3.9. The extended MFOTL Trace Converter Function converts MFOTL traces starting at some timestamp to system traces.
Definition 3.10. The MFOTL Trace Converter Function converts MFOTL traces starting at timestamp to system traces.
It is important to note that is only defined, if or . however, is defined for all , since timestamps in any trace must increase monotonically, and the timestamp argument passed to is . To see that the images of both and for all allowed inputs is and not , note that a is only added when the trace is not yet empty, thus any inserted will eventually be followed by some database . For any set of MFOTL traces and any set of system traces and timestamp , we write
Theorem 3.11. The trace converter functions and define a bijective mapping between MFOTL traces and trimmed system traces and are each others inverses. and
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. Since and are defined with and respectively, the proof will proceed by showing the following two, more general, properties for all . When fixing 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.
MFOTL Traces (Equations 3.1 and 3.3)
As stated above, we begin by showing Equation 3.3 for finite traces . 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 for all where either or .
Base Case: (and some ) Induction Hypothesis: For every true suffix of a trace that is not the entire trace , i.e. and , and for every timestamp which is less than the first timestamp () in , unless it holds that
Induction Step: Let and . Because is not empty, for some , some and a suffix .
Finally we show how this extends to infinite traces. Let be an infinite MFOTL trace. And let be the finite prefix with the first time points of . With the finite case, we have shown that for any , , and (in the infinite case, a first timestamp always exists) . Then in the limit
We have now shown 3.1 for both finite and infinite traces, which directly implies 3.3.
System Traces (Equations 3.2 and 3.4) For this direction we first prove that Equation 3.4 holds for finite system traces . And in a second step will show that it also holds for infinite system traces . 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 for all .
Base Case
Induction Hypothesis For every true suffix of a trimmed system trace that is not the entire trace , i.e. and , and for every timestamp it holds that
Induction Step
Let , with . Then for some , , and a suffix .
Finally we show how this extends to infinite system traces. Let be an infinite system trace. And let be the finite prefix of ending with the -th database event. By this definition is in . With the finite case, we have shown that for any , , and . Then in the limit
◻
Intuitively and 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 with arguments being sets of traces in which case 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 , where traces are equivalent if they are the same with all steps removed. In particular this means that sets of system traces (such as trace properties) are closed under the addition and removal of events. Thus the set of events in system traces gets extended to be Since events do not meaningfully modify a system trace, the isomorphism from Theorem 3.11 works if we remove all 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 from Example 2.10, we can now convert it into a system trace .
Definition 3.13. The semantics of MFOTL for a fixed, infinite system trace , a valuation , time-point , and MFOTL formula is defined as
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 modifies a reported set of events by suppressing (deleting) and causing (inserting) certain events if needed. Where for all and
Definition 3.15. A Proactive Update Function indicates whether or not some events must be caused (inserted) before a clock tick happens.
Definition 3.16. The Enforcement State Space consists of all system traces (that may include ).
Definition 3.17. The single initial state is the empty trace .
Definition 3.18. The Event Space consists of sets of events or the two special events and .
Definition 3.19. The Transition Relation is a subset and it is defined by the following two transition rules.
We write as a shorthand for . Further for events , iff there exists such that and . This syntax can be extend to sequences of events (i.e. system traces) , iff there exists such that and .
Definition 3.20. An Enforcement Event System is a tuple consisting of a state space , event space , a reactive update function and a proactive update function . 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 with initial states as for event systems inin Sprenger et al. [17] (Section 2.4), states . Our described system has the property that if the only initial state is the empty trace , 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 then denotes both all finite and infinite event sequences of the event system starting in any initial state in . denotes only the finite traces and 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: iff and iff . 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 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 function of Algorithm 1. The simulation uses a helper function Then the function is defined as follows for any enforcer state and system trace
Definition 3.22. The induced enforcement event system of an enforcer is defined as with and defined as follows
Definition 3.23. An enforcement event system is sound with respect to some property iff
Equivalently an enforcement event system and the initial state are sound for a property iff . 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 is sound for a formula iff it is sound for the property .
Theorem 3.25. If an enforcer is sound for a property , then the induced enforcement event system is sound for the property .
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 , and ,
Lemma 3.27. Let be an enforcer. For any system trace there exists a trace such that .
Proof. We will show that for all there exists a trace of which is a prefix (i.e. ).
Since by definition contains all finite prefixes of , if , there would exist some contains all finite prefixes of which is not a prefix for any trace . Thus if we show that every finite prefix is also a finite prefix for at least one trace , we will have shown that .
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 , by the fact that the enforcer is sound for . and since we have shown that for all system traces , there exists a trace such that , we have also shown that or equivalently . This does also imply . ◻
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 for some signature with initial states refines an enforcement event system for some signature with initial states via a mediator function iff there is a simulation relation such that
for all there exists some such that , and
for all , , and such that and there exists such that and .
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 can be extended to a trace transducer function as follows
The following theorem is analogous to Theorem 2.52 [17, Theorem 2.1].
Theorem 3.30. implies .
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 and then
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.
- let map =
- for do
- end for
- return
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 refines a specification , written as under a refinement mapping iff there exist and such that .
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 , with and . A predicate appears monotonically (or anti-monotonically) in a formula , if the addition of an event cannot make an already compliant (or non-compliant) trace non-compliant (or compliant). For example in the formula the predicate does not appear monotonically, because the addition of an event at any time would make a trace that was previously compliant with , non-compliant with , on the other hand appears anti-monotonically in . 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 that defines an event in terms of the concrete events . This function does for MFOTL traces, what the mediator function from Definition 3.32 and its extended form from Definition 3.29 do for system traces.
Definition 3.33. Let be a function as defined in Figure 3.4. Then the mediator function is defined as follows: where is defined as the database of the last time point of the trace being returned by the MFOTL trace .
Lemma 3.34. For any MFOTL trace , and map function
The following theorem states that any valid refinement of an enforceable CRE[MFOTL] specification is itself enforceable.
Theorem 3.35. If under a refinement mapping and is enforceable, then is enforceable.
Theorem 3.36. If , is enforceable, and , then .
Hublet et al. [12] have proved Theorem 3.35 [12, Theorem 4] and Theorem 3.36 [12, Theorem 3].
Theorem 3.37. If and is enforceable then there exist two enforcement event systems and such that they are sound for and respectively, and refine each other via the mediator function , i.e.
Proof. for Theorem 3.37 Let , and be enforceable.
By the enforceability of we know that there exists an enforcer which is sound for . By Theorem 3.35 we also know that there exists an enforcer which is sound for .
Since there exist two contexts and such that . This proof proceeds by induction over the different CRE[MFOTL] refinement rules for . We show by induction on that when and then there exist two enforcement event systems and such that is sound for , is sound for , and .
In the rest of this proof, let be the simulation relation defined by .
REFL In this case and is the identity mapping. By Theorem 3.25 we know that is sound for . Finally, any enforcement event system 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 that is sound for exists (Theorems 3.35) and that its induced event Systems are also sound for (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 , one abstract system trace , and a concrete event such that . And if this is the case we want to prove that there exists an abstract system trace such that .
We can argue that the abstract enforcement event system can iteratively be defined by applying the mediator function to all traces and transitions of the concrete enforcement event system. A transition would then become . And the simulation relation can be defined by the aforementioned . We call the so constructed enforcement event system . The event system is sound for because of Theorem 3.36.
IMP 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 that is sound for . By the fact that we can deduce that is also sound for . And thus the induced event system for is sound for both and , and also a refinement of itself.
IMP and IMP Without loss of generality we will only consider the case of IMP. The case of IMP 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 IMP 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 and can be simply constructed by inducing them from the sound enforcers and which we know must exist. Then we can build up the simulation relation , by iteratively following all possible transitions and adding the created trace pairs to . e.g. starting with the empty trace, we check what trace the concrete enforcement event system would produce when the event occurs and what trace the abstract enforcement event system would produce when the event occurs, and then we add the pair of resulting traces to . ◻
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.
Reference to the abstract Lex specification (Keyword:
refine) Any Lex refinement specification will start with arefinestatement. This statement is simply used to specify the underlying Lex specification that is being refined. Syntactically it works the same way as animportstatement (e.g.refineedp).Event Refinement There are two ways to refine non-internal events in Lex. First an event can be marked as assumed to be always true or always false, and second an event can be refined by a combination of other events. In the second case, a previously non-internal event becomes an internal event in the refined specification. Section 4.2.1 dives further into the details of event refinement.
Rule strengthening and weakening (Keyword:
replace) With refinement, old rules in a Lex specification can be replaced by new rules in accordance with the implication rules for CRE[MFOTL] refinement from Figure 3.3. Section 4.2.2 contains more details on the specifics of rule replacement.Type Refinements (Structure:
refinetype"abstract type"is"concrete type") Type refinements are used to specify concrete data types for types that might have been left abstract in the original Lex specification. For example, it might be unknown and not necessary to know in a legal formalization whether a person is represented as a string or integer identifier, but in the refinement specification we do know which data type is used by the target system.Additional obligations and constitutive rules A refined specification can always contain additional obligations that are not explicitly used to replace old obligations. Similarly, a refined specification can contain new constitutive rules that define events which may be used anywhere in the refined specification. For reasons of simplicity, we have opted to disallow the introduction of new exceptions in refined specifications, but exception rules can still be part of a refinement specification as long as they are explicitly used to replace existing exceptions.
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. 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. 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
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 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 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 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 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
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
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 isNaturalPersonassume 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"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)LET automatedCommunication(_p1 : int, _p2 : int, _p3 : string
_p4 : string)- =
email(_p1, _p2, _p3, _p4) fax(_p1, _p2, _p3, _p4)
automatedCall(_p1, _p2, _p3, _p4) IN
LET Exception4(c : string, r : int, s : int) =
obtainedEmailForCategory(r, s, c)
objectToSimilarEmailMarketing(r, s, c) IN
LET Scope5(r : int) = isNaturalPerson(r) IN
[0s,) (
c. r. s. automatedCommunication(s, r, "marketing", c
:L Exception4(c, r, s) Scope5(r)
:L marketingConsent(r, s))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)LET automatedCall(_p11 : string, _p12 : string, _p13 : string,
_p14 : string) = IN
LET fax(_p15 : string, _p16 : string, _p17 : string, _p18 : string)
= IN
LET isNaturalPerson(_p19 : string) = IN
LET marketingConsent(_p9 : string, _p10 : string) =
userWithdrawsConsent(_p9, _p10)
S[0s,) userGivesConsent(_p9, _p10) IN
LET objectToSimilarEmailMarketing(_p20 : string, _p21 : string,
_p22 : string) = IN
LET Exception4(c : string, r : string, s : string) =
obtainedEmailForCategory(r, s, c)
objectToSimilarEmailMarketing(r, s, c) IN
LET automatedCommunication(_p5 : string, _p6 : string, _p7 :
string, _p8 : string)- =
email(_p5, _p6, _p7, _p8) fax(_p5, _p6, _p7, _p8)
automatedCall(_p5, _p6, _p7, _p8) IN
LET Scope5(r : string) = isNaturalPerson(r) IN
[0s,) (
c. r. s. automatedCommunication(s, r, "marketing", c)
:L Exception4(c, r, s) Scope5(r)
:L marketingConsent(r, s) over18(r))Additional Proofs
Proof for Lemma 3.26
Proof. Let and . The proof for Lemma 3.26 proceeds by structural induction over system traces .
Base Case
Induction Hypothesis
For any true suffix of (i.e. )
Induction Step
We make a case distinction based on . Without loss of generality we can assume that there are no events in .
◻
Proof for Lemma 3.27
Proof. The proof for Lemma 3.27 proceeds by structural induction over finite system traces . Later we will make the argument why the property extends to inifinite system traces too. Without loss of generality we can assume that , because the conversion function removes implicitly trims system traces. Let be an enforcer.
Base Case The final equality follows from Algorithm 1 which defines, that enforcing the empty trace returns the empty trace.
Induction Hypothesis For all true prefixes of (i.e. ) there exists a trace such that .
Induction Step
We make a case distinction based on the two possible transitions of enforcement event systems from Definition 3.19. The update functions and are defined as in Definition 3.22.
The final step follows from the definition of the reactive update function by means of the enforcer update function and how is used by in lines 6 and 7 of Algorithm 1 to issue an -command.
Similarly to the reactive case above, the final step follows from how the proactive update function is defined by the enforcer update function and how is used by the enforcement algorithm to issue and 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 we have shown that for all finite prefixes with an arbitrary , there exists an MFOTL trace such that . If, for some infinite trace , there would not exist a trace such that , then there would exist some finite prefix such that there also does not exist a trace such that . ◻
Use of Generative AI Tools
| AI Tool | Use Case | Scope | Remarks | |
|---|---|---|---|---|
| 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 | |
| DeepL Write | Correction of grammatical mistakes, styling | Entire report | Free Trial | |
| OpenAI ChatGPT | Brainstorming, "interactive" web search | Introduction | "Deep Research" mode |
References
- 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.
- “Pretix – Reinventing Ticket Sales for Conferences, Festivals, Exhibitions, ...” n.d. https://pretix.eu/about/en/. Accessed May 29, 2025.
- Abadi, Martı́n, and Leslie Lamport. 1991. “The Existence of Refinement Mappings.” Theoretical Computer Science 82 (2): 253–84.
- 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.
- 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.
- Brewka, Gerhard, and Thomas Eiter. 2000. “Prioritizing Default Logic.” In Intellectics and Computational Logic: Papers in Honor of Wolfgang Bibel, 27–45. Springer.
- Chomicki, Jan. 1995. “Efficient Checking of Temporal Integrity Constraints Using Bounded History Encoding.” ACM Transactions on Database Systems (TODS) 20 (2): 149–86.
- Degelo, Jonas. 2024. “A Language for Formalizing Legal Provisions.” Talk
- 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.
- ———. 2025. “Scaling Up Proactive Enforcement.” In International Conference on Computer Aided Verification, edited by Ruzica Piskac and Zvonimir Rakamaric. Springer.
- Hublet, François, Linda Hu, David Basin, and Srđan Krstić. 2025. “Instrumenting Runtime Enforcement.” ETH Zürich, Department of Computer Science.
- 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.”
- Lancieri, Filippo. 2022. “Narrowing Data Protection’s Enforcement Gap.” Me. L. Rev. 74: 15.
- 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.
- 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.
- Schneider, Fred B. 2000. “Enforceable Security Policies.” ACM Trans. Inf. Syst. Secur. 3 (1): 30–50. https://doi.org/10.1145/353323.353382.
- 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.
- 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.
- 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.