Motivation
Why formalize the law?
Laws are written in natural language, but much of what they say has a logical structure: conditions, obligations, exceptions, deadlines. Writing that structure down formally has three benefits.
- It shows the logical structure. A formalization removes some ambiguity and lets us reason clearly about what a provision means.
- It opens the law to a broader audience. A formal reading can make parts of a law easier to understand, and automated tools built on it can make the law more accessible.
- It enables automation. With runtime verification, we can check that the behaviour of a computer system complies with the law.
Formalizing the law for runtime verification
Runtime verification comes in two forms. Monitoring checks, online or offline, that a system's behaviour complies with a policy. Enforcement goes further: it runs alongside the system and can correct its behaviour, so it is inherently online.
State-of-the-art enforcement tools require the law to be encoded as logical formulas. Translating legal text directly into formulas is difficult and error-prone, and the result is hard to check against the original. A good formalization should therefore also be readable.
This work
Lex is an intermediate language between the law in natural language and runtime verification policies written as logical formulas. It stays readable by keeping the hierarchical structure of the law, and it has mechanisms that make the logical structure explicit.
The rest of this page covers:
- Formalizing the law: vagueness and the logical structure of legal texts.
- Temporal logic: metric first-order temporal logic and its enforceable fragment.
- The Lex language: hierarchy, rules and the type system, shown on an example from the GDPR.
Formalizing the law: some theory
Vagueness and the human element
Vagueness is inherent to the law, and scholars debate whether it could ever be eliminated entirely. Lex does not try to. It formalizes the logical structure of legal texts and leaves vague terms as inputs: where a provision is ambiguous, a human decides, and that decision is given to the system as an event.
The logical structure of the law
- Exceptions. Legal texts often specify when another section of the law does not apply.
- Brute and institutional facts. Brute facts are “facts of nature”, such as a person's age or a car's speed. Institutional facts are derived from brute facts: a person may vote in Switzerland if they are over 18 and a Swiss citizen, so “having the right to vote” is an institutional fact.
This structure differs from that of common programming languages, which is why Lex has dedicated constructs for it.
Three kinds of rules
A toy example shows the three kinds of rules Lex distinguishes:
- Obligation rule: To enter the building, authorization is required.
- Constitutive rule: Employees are authorized to enter the building.
- Exception rule: During time off, (2) does not apply.
Obligations say what must hold, constitutive rules derive institutional facts such as “authorized”, and exceptions switch other rules off. The thesis formalizes this as §2.2.3 Constitutive, Regulative, and Exception Rules.
Temporal logic
Metric first-order temporal logic
MFOTL extends first-order predicate logic (φ∧ψ, φ∨ψ, ¬φ, P(x), …) with temporal operators. Each operator carries an interval I that bounds how far into the future or past it looks.
| Always | □Iφ | Historically | ■Iφ |
| Until | φUIψ | Since | φSIψ |
| Next | ∘Iφ | Previous | ∙Iφ |
| Eventually | ◊Iφ | Once | ⧫Iφ |
Future operators are on the left, past operators on the right. The thesis defines the logic in §2.1 Metric First-Order Temporal Logic.
Enforceable MFOTL
Enforceable MFOTL is the policy language of the WhyEnf enforcer [9], a subset of MFOTL in which every predicate is marked with a capability:
- Causable: the system can create the event, e.g. “send a notification to the user”.
- Suppressable: the system can prevent the action, e.g. “a user makes a public comment”.
- Observable: the system can take no action on the event.
A type system decides whether a formula can be enforced: a formula typed C can be made true by causing events, one typed S can be made false by suppressing them. Two of its rules:
¬C}{\Gamma \vdash \phi : \Sup}{\Gamma \vdash \neg\phi : \Cau} \qquad \prfrule{∨LC}{\Gamma \vdash \phi : \Cau}{\Gamma \vdash \phi \lor \psi : \Cau}Γ⊢¬φ:CΓ⊢φ:S¬CΓ⊢φ∨ψ:CΓ⊢φ:C∨LCSee §2.2.2 Enforceable MFOTL for the capabilities as used in the thesis.
Example: two ways to enforce an implication
There are two ways to “cause” (make true) the formula φ⇒ψ. Rewriting it as ¬φ∨ψ gives one derivation per disjunct:
The Lex language
Goals for Lex
- High readability, to be evaluated in a planned user study.
- Close correspondence to legal texts in structure and form.
- Relatively easy auditing of whether a formalization accurately represents the law it formalizes.
- Two compilation targets: a documentation-like HTML representation of the formalization, and a logical formula that recent runtime enforcers can enforce. The compiler checks the enforceability requirements itself.
Section labels
A Lex file mirrors the hierarchy of the law it formalizes. Here is
26 U.S. Code § 121,
“Exclusion of gain from sale of principal residence”. The US Code nests titles,
chapters and sections more deeply than most laws, so Lex lets a level repeat:
title[1] is a level below title.
law "U.S. Code"
title "26"
title[1] "A"
chapter "1"
chapter[1] "B"
section "III"
article "121"- law U.S. Code
- title 26
- title[1] A
- chapter 1
- chapter[1] B
- section III
- article 121
Every rule inherits a label from its position, such as
U.S. Code / title 26 / title[1] A / chapter 1 / chapter[1] B / section III / article 121,
so the compiled formula can always be traced back to the text. The thesis covers
this in §2.3.2 Lex Section Labels.
Events and types
A formalization starts by declaring the types and events it talks about. Each event has a docstring, which the generated documentation uses to phrase rules in plain English.
type entity is string
type person is string
type task is int
type action is int
type data is int
type consent is int
event Nominates
""" Controller {c} nominates processor {p} to perform data processing task {t} """
c: entity
p: entity
t: taskExample: data processing under the GDPR
Obligation rules
Article 5(1)(a) of the GDPR requires personal data to be processed lawfully, fairly and transparently. In Lex, this is an obligation rule. The generated documentation shows the rule next to its plain-English reading and the original text.
rule
whenever
PersonalDataProcessing(ep, x, z)
oblige
lawfulness(ep)
fairness(ep)
transparency(ep)
enforceable
suppressing PersonalDataProcessing
Whenever all of the following happen:
- x is processing personal data z as part of processing operation ep
Then the following shall be obligatory:
- processing ep is lawful
- processing ep is fair
- processing ep is transparent
XML: GDPR Personenbezogene Daten müssen […] a) auf rechtmäßige Weise, nach Treu und Glauben und in einer für die betroffene Person nachvollziehbaren Weise verarbeitet werden („Rechtmäßigkeit, Verarbeitung nach Treu und Glauben, Transparenz“);
The rule is marked enforceable: the compiler must be able to enforce
it by suppressing PersonalDataProcessing.
Constitutive rules
When is processing lawful? Article 6(1)(a) answers: “Processing shall be lawful
only if and to the extent that at least one of the following applies: (a) the data
subject has given consent to the processing of his or her personal data for one or
more specific purposes” (GDPR Art. 6).
A constitutive rule derives the institutional fact lawfulness(ep) from
brute facts.
rule
whenever
PersonalDataProcessing(ep, x, z)
HasPurpose(ep, prp)
ONCE (GiveConsent(w, c) AND Authorizes(c, prp))
ONCE Nominates(y, x)
PersonalData(z, w)
constitute
lawfulness(ep)
Whenever all of the following happen:
- x is processing personal data z as part of processing operation ep
- processing operation ep has purpose prp
- at some point in the past, data subject w gave consent c, and consent c authorizes usage of personal data for purpose prp
- at some point in the past, controller y nominated processor x to process personal data on y's behalf
- z is personal data of data subject w
Then the following shall be constituted:
- processing ep is lawful
Exception rules
Article 8 sets conditions for a child's consent. In a simplified form: consent given by a minor does not make processing lawful. The exception refers to the rule it disables by its section label.
rule
whenever
isMinor(w)
except
article 6 paragraph 1 point 1 subpoint a
Whenever all of the following happen:
- data subject w is a minor
Then article 6 paragraph 1 point 1 subpoint a shall not apply.
Lifting the EMFOTL type system to Lex
An obligation rule r:φ⇒ψ is complied with (made true) in one of three ways: suppress its conditions, cause its effects, or cause one of the exceptions to the rule.
L}{r : \phi \Rightarrow \psi \in R \quad \Gamma \vdash \phi : \Sup}{\Gamma \vdash \comply(r) : \Cau} \qquad \prfrule{REGR}{r : \phi \Rightarrow \psi \in R \quad \Gamma \vdash \psi : \Cau}{\Gamma \vdash \comply(r) : \Cau} \qquad \prfrule{REGE}{\Gamma \vdash \exc(r) : \Cau}{\Gamma \vdash \comply(r) : \Cau}Γ⊢comply(r):Cr:φ⇒ψ∈RΓ⊢φ:SREGLΓ⊢comply(r):Cr:φ⇒ψ∈RΓ⊢ψ:CREGRΓ⊢comply(r):CΓ⊢exc(r):CREGEThe GDPR obligation above uses the first way: it is enforced by suppressing
PersonalDataProcessing.
Temporal patterns
Conditions in Lex can carry a temporal pattern written in words. Each pattern compiles to an MFOTL operator and determines whether the condition looks into the past or the future, which in turn affects how it can be typed.
| Lex pattern | Formula | Looks at |
| — | φ | Present |
eventually [itv] | ◊Iφ | Future |
eventually delaying if ψ [itv] | ψUIφ | Future |
always in the future [itv] | □Iφ | Future |
once [itv] | ⧫Iφ | Past |
always in the past [itv] | ■Iφ | Past |
always since ψ [itv] | φSIψ | Past |
The compiled result
The three GDPR rules compile to a single MFOTL formula and a signature that
WhyEnf can enforce. The exception becomes Exception2, the constitutive
rule becomes lawfulness, and the obligation becomes the formula under
□.
let Exception2(w) = isMinor(w)
let lawfulness(_p1) = ∃c. ∃ep. ∃prp. ∃w. ∃x. ∃y. ∃z.
((((((PersonalDataProcessing(ep, x, z)
∧ HasPurpose(ep, prp))
∧ ⧫ (GiveConsent(w, c)
∧ Authorizes(c, prp)))
∧ ⧫ Nominates(y, x))
∧ PersonalData(z, w))
∧ ¬Exception2(w))
; _p1 <- ep)
□ ∀ep. ∀x. ∀z. (PersonalDataProcessing(ep, x, z) ∧:L ⊤)
→:L ((lawfulness(ep) ∧ fairness(ep)) ∧ transparency(ep))Authorizes(c__: int, prp__: string)
GiveConsent(w__: int, c__: int)
HasPurpose(ep__: int, prp__: string)
Nominates(y__: int, x__: int)
PersonalData(z__: int, w__: int)
PersonalDataProcessing(ep__: int, x__: int, z__: int)-
fairness(ep__: int)
isMinor(w__: int)
lawfulness(ep__: int)
transparency(ep__: int)
ts(~return_value__: time)
fun day(t__: time) -> time
Exception2(w__: int)The thesis's Appendix A Compiled Lex Examples has the compiled output of its own examples.
The compilation pipeline
The compiler passes a Lex file through four intermediate representations before writing the files WhyEnf reads.
The thesis extends this pipeline with refinement; see §4.3 Implementation in the Lex Compiler.
Outlook
Future work, and where it went
- Refinement. Users should be able to take an existing formalization and specify how its high-level events map to the events of a given system, so that one formalization can be reused across use cases. This became the master's thesis: Refinement in Lex (and its talk), in particular §3 Refinement of CRE Enforcement and §4.2 Refinement of Lex Specifications.
- Tooling: a VS Code extension and a language server.
- A formalization of the GDPR.
- A user study on the usability of Lex.
Lex itself has since been published as [12].