Refinement of Legal Specifications in the Lex Programming Language

The talk on this master's thesis: refining abstract legal specifications in Lex for a concrete system

Jonas DegeloMaster's thesis talk, ETH Zurich2025

Read the thesisOriginal slidesPractical-work talk

Scroll

Motivation

2

Why formalize the law?

There are three general reasons to formalize laws:

  • It shows the logical structure. A formalization captures and highlights how the parts of a law depend on each other.
  • It gives broader access. A formal version can be presented in other forms, for example as a decision tree.
  • It enables automation. For tax law this might be a classical algorithm: income and assets go in, the tax amount comes out.
3

Formalizing the law for runtime verification

Another form of automation is runtime verification, and that is what Lex is designed for. It comes in two related forms:

  • Monitoring checks compliance. A monitor watches a system's behaviour and produces a verdict on whether it complies with a property, either in real time or after the system has finished.
  • Enforcement ensures compliance. An enforcer has the same setup, but instead of only producing a verdict it changes the system's behaviour to keep it compliant. This must happen in real time.

State-of-the-art verification tools require the law to be encoded as logical formulae, which are hard to write, understand and audit. A good formalization keeps much of the readability of a law in natural language while being fully formal and usable for runtime verification.

4

The thesis describes the enforcement setup in Fig 2.3.

Why is refinement needed?

  • Different levels of abstraction. It should be possible to write specifications at the level that suits them: a law in general terms, a system in concrete ones.
  • Reuse of existing formalizations. Take data protection as an example: formalize the GDPR once, then adapt it to different services with minimal effort.

With refinement, one trusted formalization of the GDPR is enough. Each system operator writes a refinement for their own system and only has to audit that part, not the whole GDPR formalization again.

5
6

Vagueness and the human element

Some vagueness is inherent to the law. It calls for human interpretation, and the consensus among scholars is that this need cannot be eliminated entirely; vague legal terms have to be interpreted case by case.

Lex does not try to solve that. Its goal is to formalize and capture the logical structure of legal texts. Where something is ambiguous, a human decides, and the decision becomes an input to the system.

7

The logical structure of the law

  • Obligations limit what is allowed. In a world where everything is allowed unless stated otherwise, obligations state the limits.
  • Exceptions say when another section of the law does not apply: “under condition A, Article 3 Paragraph 2 does not apply”.
  • Brute and institutional facts. Brute facts are atomic “facts of nature”, like a person's age or a car's speed. Institutional facts are derived from other facts: having the right to vote in Switzerland follows from being over 18 and a Swiss citizen.

The line between the two is fluid. A person's age can be atomic, or derived from their date of birth and the current date. Which one it is depends on the level of abstraction, much like levels of abstraction in computer science, and that is one motivation for refinement.

8

Rules: building access

  1. Regulative (obligation) rule: To enter the building, authorization is required.
  2. Constitutive rule: Employees are authorized to enter the building.
  3. Exception: During time off, rule 2 does not apply.

The constitutive rule defines the institutional fact “is authorized” in terms of “is an employee”, and the exception switches it off during holidays. Together these are CRE rules (constitutive, regulative, exception), the basis of Lex. Obligations are one kind of regulative rule, and besides exceptions Lex also has scope rules, which work the same way without the negation.

Refinement of specifications

10

Refinement

Refinement is a well-known concept in formal methods:

  • Take two models of the world and a mapping between them.
  • Specification A is written for model 1, specification B for model 2.
  • A refines B if every behaviour that complies with A also complies with B once it is mapped to model 2.

Think of one specification for a C++ program and one for the x86 assembly it compiles to.

11

The thesis defines this in §2.5 Refinement of Event Systems.

The Lex programming language

12

Metric first-order temporal logic

Lex builds its basic logical statements on MFOTL: first-order predicate logic (φ∧ψ\phi \land \psi, φ∨ψ\phi \lor \psi, ¬φ\neg\phi, P(x)P(x), …) combined with temporal operators over possibly unbounded intervals, as in “always within interval II, φ\phi must hold”.

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
13

See §2.1 Metric First-Order Temporal Logic. The practical-work talk introduces Lex and its type system in more depth.

Section labels

To make a formalization easy to reason about, Lex captures the hierarchy of the law as section labels, here for 26 U.S. Code § 121.

Lex
law "U.S. Code"
title "26"
title[1] "A"
chapter "1"
chapter[1] "B"
section "III"
article "121"

No structure is shared by all laws, so Lex has a fixed sequence of levels: law, title, chapter, section, article, paragraph, point and subpoint.

Levels keep their order but may be skipped; only law is required, and anything below an article needs an article above it. The bracket notation inserts any number of intermediate levels: title[1] sits below title, which is title[0].

Example: the ePrivacy Directive

The rest of the talk uses one example: Article 13 of the EU's ePrivacy Directive [1], which deals with unsolicited marketing communication.

Article 13. Unsolicited communications

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

2. Notwithstanding paragraph 1, where a natural or legal person obtains from its customers their electronic contact details for electronic mail, in the context of the sale of a product or a service, […] 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 […].

obligation · constitutive rules · exception

15

The marks match the rules on the next slides. The full text and formalization are in §2.3.3 Lex - E-Mail Marketing Example.

Events and types

Lex has integers, floats, strings and booleans as basic types, and lets you define other types, abstract or concrete. Events are declared with one typed argument per line and a capability:

epd.lex
type person
type purpose is string
type productCategory is string

internal event automatedCommunication
    """person {s} sends automated communication 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
16

internal marks an institutional fact: a placeholder more like a variable or function in a programming language. causable suppressable tells Lex that the system can both cause and suppress automated calls; the other capabilities are observable and internal.

Obligation rules

Paragraph 1 of Article 13 is an obligation: automated communication from sender s to receiver r for marketing requires that the receiver has consented.

epd.lex
article "13" "Unsolicited communications"
paragraph "1"

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

Constitutive rules

Paragraph 1 also lists forms of automated communication: automated calls, fax and email. Each becomes a constitutive rule for the institutional fact automatedCommunication.

epd.lex
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)
18

Exception rules

Paragraph 2 is an exception to paragraph 1: if the email address was obtained in connection with a product, marketing for similar products is allowed as long as the receiver has not objected.

epd.lex
paragraph "2"

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

Compiled Lex code

The constitutive rules are combined into one let-binding, the exception gets another, and the obligation sits at the bottom under an always operator. A scope rule (paragraph 5, natural persons only) adds a third binding.

MFOTL formula of epd.lex
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))
MFOTL signature of epd.lex
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)
20

The signature lists every event that is not internal. Scope rules are the counterpart of exceptions: instead of saying when a rule does not apply, they add conditions that must hold before it applies. Both listings are in Appendix A Compiled Lex Examples.

Contributions

21

What the thesis contributes

  • Refinement rules for Lex.
  • A connection between refinement in Lex and refinement in the literature (§3 Refinement of CRE Enforcement).
  • An implementation of refinement in the Lex compiler (§4 Implementation).
  • A case study that refines the EU's ePrivacy Directive for a real system (§5 Case Study), shown in the rest of this talk.
22

Pretix

The system is Pretix [2], an open-source ticketing platform covering the whole pipeline from sales to ticket control.

  • Built with Python and Django.
  • Instrumented with instrlib [11], developed for a bachelor's thesis, to enforce Article 13 of the ePrivacy Directive.
  • Article 13 refined for Pretix.
23

Refining the ePrivacy Directive for Pretix

A refinement can do four kinds of things:

  1. Add new types, events, obligations and constitutive rules.
  2. Refine abstract types and events into concrete ones.
  3. Replace obligations with stronger obligations.
  4. Replace constitutive rules with stronger or weaker definitions.
24

The thesis describes these in §4.2 Refinement of Lex Specifications.

Refining data types and adding events

Refinements live in .rex files. The first line names the specification being refined, here epd.lex. The abstract type person becomes a string, and new events let a user give or withdraw consent to marketing from another person or business.

epd.rex
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
25

Refining concrete events

An event that was not internal can be refined, which makes it internal: here marketingConsent is defined in terms of the new events. Assumptions are a special kind of refinement that fix an event to always true or always false. Pretix supports neither phone calls nor fax, so those never happen.

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

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

Replacing obligations with stronger ones

Obligations can be made stronger. Say Pretix wants to be more careful than the directive requires and never send marketing email to minors: write a new obligation and replace the old one with it.

Old, weaker rule (epd.lex)
article "13" "Unsolicited communications"
paragraph "1"

rule "marketing consent requirement"
    whenever
        automatedCommunication(s, r, "marketing", c)
    oblige
        marketingConsent(r, s)
    enforceable suppressing automatedCommunication
New, stronger rule (epd.rex)
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"

The new rule must imply the old one; the Lex compiler checks this implication with an SMT solver.

27

Strengthening or weakening constitutive rules

Obligations can only be strengthened. Constitutive rules can be strengthened or weakened, under conditions:

  • Strengthening: the constituted event is emitted less often. Allowed if the event is anti-monotonic: an extra occurrence cannot make a trace more compliant.
  • Weakening: the constituted event is emitted more often. Allowed if the event is monotonic: an extra occurrence cannot make a trace less compliant.
28

Under monotonicity, missing events do not change compliance; under anti-monotonicity, extra events do not. An event that is both does not affect compliance at all (for example, one the formula never uses), and one that is neither matters both ways (a policy requiring it to occur exactly once). The rules are in Fig 3.2 in the thesis.

Example: a refinement of a refinement

Refinements can be stacked. A second file, epd-2.rex, refines epd.rex (note the extra rex keyword) and strengthens the definition of consent: it must also have been given within the last 30 days, so marketingConsent holds less often.

Old, weaker rule (epd.rex)
rule "refine marketing consent"
    whenever
        (NOT userWithdrawsConsent(r, s)) SINCE userGivesConsent(r, s)
    refine
        marketingConsent(r, s)
New, stronger rule (epd-2.rex)
refine rex epd

rule "consent expiration"
    whenever
        ONCE[0, 30d] userGivesConsent(r, s)
        (NOT userWithdrawsConsent(r, s)) SINCE userGivesConsent(r, s)
    constitute
        marketingConsent(r, s)

replace
    strengthen
        rule "refine marketing consent"
    by
        rule "consent expiration"

The compiler checks the implication in the right direction (new implies old for strengthening, old implies new for weakening) and checks (anti-)monotonicity following the topological order of the rules.

29

Exceptions are strengthened and weakened the same way. See §4.2.2 Rule Strengthening and Weakening.

Compiled formulae: before and after refinement

In the refined formula, every assumption becomes a let-binding, as does the refined consent, and the strengthened obligation adds over18(r) at the bottom.

epd.lex
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))
epd.rex (refined)
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))
30

The refined output shown here is compiled from epd.rex, as in Fig A.4 in the thesis's appendix; the slide in the talk showed epd-2.rex, which adds the 30-day window.

Compiled signatures: before and after refinement

Only events that are not internal appear in the signature. The assumed events and the refined marketingConsent are now internal and disappear; the new events are added.

epd.lex
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)
epd.rex (refined)
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)
31

Outlook

32

Future work

  • A larger case study. Formalize substantial parts of regulation and refine them for larger systems. Pretix could serve again, for example data minimization in its waitlist feature.
  • Package management for Lex refinement. A repository of existing formalizations that engineers can pull in and refine for their own systems.
33

What Lex is, and is not

  • Lex does not try to infer the meaning of the law automatically. LLMs could help with semi-automatic formalization, the topic of a recent bachelor's thesis on generating Lex from natural language, but such output can only be a starting point for people to build on and audit. Some human interpretation will very likely always be needed.
  • Lex aims to make auditing easier. With refinement, each layer of a formalization can be audited on its own, which keeps the complexity of each layer low.
34

Lex itself has since been published as [12].

Appendix: implementation

35

The compilation pipeline

A .rex file goes through its own parse, type and check stages (rule replacements, monotonicity constraints, event refinements), and then joins the .lex pipeline before compilation to MFOTL.

.lexlextlexelexclex.rexrextrexerexMFOTLparseparsetype termscompute labelsfind exceptionssortcheck ℂ/𝕊compile CREtype termscheck:- rule replacements - mono. contrs.insert assumptionscheck:- event refinements- mono. constrs.linearize
The structure of the Lex compiler, from Fig 4.1 in the thesis.
36