Motivation
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.
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.
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.
Legal background
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.
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.
Rules: building access
- Regulative (obligation) rule: To enter the building, authorization is required.
- Constitutive rule: Employees are authorized to enter the building.
- 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
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.
The thesis defines this in §2.5 Refinement of Event Systems.
The Lex programming language
Metric first-order temporal logic
Lex builds its basic logical statements on MFOTL: first-order predicate logic (φ∧ψ, φ∨ψ, ¬φ, P(x), …) combined with temporal operators over possibly unbounded intervals, as in “always within interval I, φ must hold”.
| Always | □Iφ | Historically | ■Iφ |
| Until | φUIψ | Since | φSIψ |
| Next | ∘Iφ | Previous | ∙Iφ |
| Eventually | ◊Iφ | Once | ⧫Iφ |
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.
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
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:
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: productCategoryinternal 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.
article "13" "Unsolicited communications"
paragraph "1"
rule "marketing consent requirement"
whenever
automatedCommunication(s, r, "marketing", c)
oblige
marketingConsent(r, s)
enforceable suppressing automatedCommunicationConstitutive rules
Paragraph 1 also lists forms of automated communication: automated calls, fax and
email. Each becomes a constitutive rule for the institutional fact
automatedCommunication.
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)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.
paragraph "2"
rule "marketing of similar products or services"
whenever
obtainedEmailForCategory(r, s, c)
NOT objectToSimilarEmailMarketing(r, s, c)
except
article "13" paragraph "1"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.
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))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)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
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.
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.
Refining the ePrivacy Directive for Pretix
A refinement can do four kinds of things:
- Add new types, events, obligations and constitutive rules.
- Refine abstract types and events into concrete ones.
- Replace obligations with stronger obligations.
- Replace constitutive rules with stronger or weaker definitions.
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.
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: personRefining 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.
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 automatedCallReplacing 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.
article "13" "Unsolicited communications"
paragraph "1"
rule "marketing consent requirement"
whenever
automatedCommunication(s, r, "marketing", c)
oblige
marketingConsent(r, s)
enforceable suppressing automatedCommunicationobservable 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.
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.
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.
rule "refine marketing consent"
whenever
(NOT userWithdrawsConsent(r, s)) SINCE userGivesConsent(r, s)
refine
marketingConsent(r, s)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.
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.
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))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))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.
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)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)Outlook
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.
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.
Lex itself has since been published as [12].
Appendix: implementation
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.