Lex: A Language for Formalizing Legal Provisions

The talk on the practical work that introduced Lex, which the thesis builds on

Jonas DegeloPractical work talk, ETH Zurich2024

Read the thesisOriginal slidesThesis talk

Scroll

Motivation

2

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.
3

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.

XSE1.1: set of events D1.2: R-command RCom(Dℂ, D𝕊)2: P-command PCom(Dℂ)policy Ptime τ
The enforcer E\mathcal{E} observes events from the system SS and answers with commands that suppress or cause events, guided by a policy PP. Adapted from Hublet, Kvamme and Krstić, “Towards an Enforceable GDPR Specification” (2024); see also Fig 2.3 in the thesis.

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.

4

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:

  1. Formalizing the law: vagueness and the logical structure of legal texts.
  2. Temporal logic: metric first-order temporal logic and its enforceable fragment.
  3. The Lex language: hierarchy, rules and the type system, shown on an example from the GDPR.
5

Formalizing the law: some theory

6

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.

7

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.

8

Three kinds of rules

A toy example shows the three kinds of rules Lex distinguishes:

  1. Obligation rule: To enter the building, authorization is required.
  2. Constitutive rule: Employees are authorized to enter the building.
  3. 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.

9

Temporal logic

10

Metric first-order temporal logic

MFOTL extends first-order predicate logic (φ∧ψ\phi \land \psi, φ∨ψ\phi \lor \psi, ¬φ\neg\phi, P(x)P(x), …) with temporal operators. Each operator carries an interval II that bounds how far into the future or past it looks.

Always□⁡Iφ\Always_I \phiHistorically■⁡Iφ\Historically_I \phi
UntilφUIψ\phi \UUntil_I \psiSinceφSIψ\phi \Since_I \psi
Next∘Iφ\Next_I \phiPrevious∙Iφ\Prev_I \phi
Eventually◊⁡Iφ\Eventually_I \phiOnce⧫⁡Iφ\Once_I \phi

Future operators are on the left, past operators on the right. The thesis defines the logic in §2.1 Metric First-Order Temporal Logic.

11

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\Cau can be made true by causing events, one typed S\Sup can be made false by suppressing them. Two of its rules:

  Γ⊢φ:S    Γ⊢¬φ:C   ¬C  Γ⊢φ:C    Γ⊢φ∨ψ:C   ∨LC\prfrule{¬C\neg^{\Cau}}{\Gamma \vdash \phi : \Sup}{\Gamma \vdash \neg\phi : \Cau} \qquad \prfrule{∨LC\lor^{\Cau}_{L}}{\Gamma \vdash \phi : \Cau}{\Gamma \vdash \phi \lor \psi : \Cau}

See §2.2.2 Enforceable MFOTL for the capabilities as used in the thesis.

12

Example: two ways to enforce an implication

There are two ways to “cause” (make true) the formula φ⇒ψ\phi \Rightarrow \psi. Rewriting it as ¬φ∨ψ\neg\phi \lor \psi gives one derivation per disjunct:

Γ⊢φ:SΓ⊢¬φ:C ¬CΓ⊢¬φ∨ψ:C ∨LCΓ⊢φ⇒ψ:C\dfrac{\dfrac{\dfrac{\Gamma \vdash \phi : \Sup}{\Gamma \vdash \neg\phi : \Cau}\,{\scriptsize\neg^{\Cau}}}{\Gamma \vdash \neg\phi \lor \psi : \Cau}\,{\scriptsize\lor^{\Cau}_{L}}}{\Gamma \vdash \phi \Rightarrow \psi : \Cau}
Suppress the left-hand side
Γ⊢ψ:CΓ⊢¬φ∨ψ:C ∨RCΓ⊢φ⇒ψ:C\dfrac{\dfrac{\Gamma \vdash \psi : \Cau}{\Gamma \vdash \neg\phi \lor \psi : \Cau}\,{\scriptsize\lor^{\Cau}_{R}}}{\Gamma \vdash \phi \Rightarrow \psi : \Cau}
Cause the right-hand side
13

The Lex language

14

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.
15

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.

Lex
law "U.S. Code"
title "26"
title[1] "A"
chapter "1"
chapter[1] "B"
section "III"
article "121"
Generated documentation
  1. law U.S. Code
  2. title 26
  3. title[1] A
  4. chapter 1
  5. chapter[1] B
  6. section III
  7. article 121
16

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.

Lex · GDPR (EU)
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: task
17

Example: data processing under the GDPR

18

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.

article 5 law GDPR / chapter II
XML: GDPR Grundsätze für die Verarbeitung personenbezogener Daten
paragraph 1 law GDPR / chapter II / article 5
point a law GDPR / chapter II / article 5 / paragraph 1
rule
  whenever
    PersonalDataProcessing(ep, x, z)
  oblige
    lawfulness(ep)
    fairness(ep)
    transparency(ep)
enforceable
suppressing PersonalDataProcessing
Reading

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“);

19

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.

article 6 law GDPR / chapter II
XML: GDPR Rechtmäßigkeit der Verarbeitung
paragraph 1 · point 1 · subpoint a law GDPR / chapter II / article 6
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)
Reading

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
20

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.

article 8 law GDPR / chapter II
XML: GDPR Bedingungen für die Einwilligung eines Kindes in Bezug auf Dienste der Informationsgesellschaft
paragraph 1 law GDPR / chapter II / article 8
rule
  whenever
    isMinor(w)
  except
    article 6 paragraph 1 point 1 subpoint a
Reading

Whenever all of the following happen:

  • data subject w is a minor

Then article 6 paragraph 1 point 1 subpoint a shall not apply.

21

Lifting the EMFOTL type system to Lex

An obligation rule r:φ⇒ψr : \phi \Rightarrow \psi 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.

  r:φ⇒ψ∈RΓ⊢φ:S    Γ⊢comply(r):C   REGL  r:φ⇒ψ∈RΓ⊢ψ:C    Γ⊢comply(r):C   REGR  Γ⊢exc(r):C    Γ⊢comply(r):C   REGE\prfrule{REGL_L}{r : \phi \Rightarrow \psi \in R \quad \Gamma \vdash \phi : \Sup}{\Gamma \vdash \comply(r) : \Cau} \qquad \prfrule{REGR_R}{r : \phi \Rightarrow \psi \in R \quad \Gamma \vdash \psi : \Cau}{\Gamma \vdash \comply(r) : \Cau} \qquad \prfrule{REGE_E}{\Gamma \vdash \exc(r) : \Cau}{\Gamma \vdash \comply(r) : \Cau}
22

The 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 patternFormulaLooks at
—φ\phiPresent
eventually [itv]◊⁡Iφ\Eventually_I \phiFuture
eventually delaying if ψ\psi [itv]ψUIφ\psi \UUntil_I \phiFuture
always in the future [itv]□⁡Iφ\Always_I \phiFuture
once [itv]⧫⁡Iφ\Once_I \phiPast
always in the past [itv]■⁡Iφ\Historically_I \phiPast
always since ψ\psi [itv]φSIψ\phi \Since_I \psiPast
23

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 □⁡\Always.

MFOTL formula
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))
MFOTL signature
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)
24

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.

.lex filelextlexelexclexWhyEnf files1Parse Lex code2Type terms,compute labels,collect exceptions3Sort rulestopologically, checkenforceability4Prepare signatureand MFOTL formula5Compile andlinearize as strings
25

The thesis extends this pipeline with refinement; see §4.3 Implementation in the Lex Compiler.

Outlook

26

Future work, and where it went

Lex itself has since been published as [12].

27