💻 computer science

Sort-Stratified Semantics for Temporal Conflict Detection in ODRL Policies

This paper addresses the unsoundness of temporal conflict detection in ODRL policies caused by ambiguous comparison operators between instants and durations by introducing a sort-stratified semantics that types operands, reduces conflict checking to interval comparison with a three-valued verdict, and proves its decidability and soundness through static and runtime evaluations.

Original authors: Daham M. Mustafa, Diego Collarana, Sabrina Kirrane, Christoph Lange, Christoph Quix, Sandra Geisler, Stefan Decker, Rafiqul Haque

Published 2026-06-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Daham M. Mustafa, Diego Collarana, Sabrina Kirrane, Christoph Lange, Christoph Quix, Sandra Geisler, Stefan Decker, Rafiqul Haque

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to rent a digital movie, but the owner (the Provider) and the renter (the Consumer) are speaking two slightly different dialects of "time."

In the world of digital rights (ODRL), rules are written like: "You can watch this before December 31st" or "You can watch this for 30 days."

The problem this paper solves is that the computer language used to write these rules treats "a specific date" and "a length of time" as if they were the same thing. It's like a chef who uses the same spoon to measure both "3:00 PM" (a specific moment) and "30 minutes" (a duration). If you ask the computer, "Is 30 minutes less than 3:00 PM?", it gets confused. It doesn't know if you mean "Is 30 minutes a shorter duration than the time until 3 PM?" or "Does 30 minutes happen before 3 PM?"

Because of this confusion, computers often miss conflicts. They might say two rules are compatible when they actually aren't, or vice versa.

Here is how the authors fixed it, using simple analogies:

1. The "Sort Stratification" (Sorting the Socks)

The authors introduced a strict sorting system. They decided that every time-related rule must be typed as either:

An Instant (A Point): Like a pin on a map (e.g., "December 31st").
A Duration (A Length): Like a ruler (e.g., "30 days").

By forcing the computer to know which "sock" is which before it tries to compare them, the ambiguity disappears. A ruler can only be compared to another ruler, and a pin can only be compared to another pin.

2. The "Three-Valued Verdict" (The Traffic Light)

When the computer checks if a Provider's offer and a Consumer's request match, it doesn't just say "Yes" or "No." It uses a three-way traffic light:

Green (Compatible): The rules fit together perfectly.
Red (Conflict): The rules contradict each other.
Yellow (Unknown): One side didn't give enough information. (e.g., The provider says "You can watch for 30 days," but the consumer didn't say how long they want to watch. We don't know if they clash yet.)

3. The "Hidden Trap" (The Cross-Operand Conflict)

This is the paper's most important discovery. Sometimes, two rules look fine on their own, but they break when you look at how they interact.

The Analogy: Imagine a water bucket.

Rule A (The Provider): "You can pour exactly 30 liters of water into this bucket."
Rule B (The Consumer): "You can only pour water for 10 minutes."

If you look at Rule A alone, it's fine. If you look at Rule B alone, it's fine. But if you try to do both at the same time, you have a problem. You can't pour 30 liters in 10 minutes if your hose only flows at a certain speed (or if the rules imply that "time spent using" cannot exceed "time elapsed").

The authors' system catches these "hidden traps" where the amount of time used conflicts with the length of time allowed, even if the specific dates look okay.

4. The "Three-Layer Detective" (The Tiers)

To solve these puzzles, the authors built a detective system that works in three levels of difficulty, like a video game:

Level 1 (Order): Simple comparisons. "Is 2026 before 2027?" or "Is 10 days less than 30 days?" This is easy and fast.
Level 2 (Arithmetic): Slightly harder. "If I start on Day 1 and wait 5 days, is that before Day 3?" This requires simple math.
Level 3 (Modular/Repeating): The hardest level. "Does this event happen every 30 days, and does that event happen every 45 days? Do they ever land on the same day?" This requires checking patterns (like finding the common denominator in math).

The system automatically picks the right "detective level" for the problem, ensuring it can solve it quickly without getting stuck.

5. The "Static vs. Runtime" Check

The paper also explains the difference between checking rules before you sign a contract and checking them while you are using the service.

Static Check (Negotiation): "Can these two sets of rules ever work together?" If the answer is "No" (Red Light), you never sign the contract.
Runtime Check (Enforcement): "Did you actually break the rules while using it?" Even if the rules could work together, you might still break them if you use the service for too long.

The Bottom Line

The authors created a new, clearer way for computers to understand time in digital contracts. They proved that by strictly separating "dates" from "durations," they can catch conflicts that previous systems missed. They tested this with 72 different scenarios (like a giant logic puzzle book) and showed that their method works perfectly, catching every conflict and avoiding false alarms.

In short: They fixed the computer's confusion between "when" and "how long," allowing it to spot hidden deal-breakers in digital agreements that it used to miss.

Technical Summary: Sort-Stratified Semantics for Temporal Conflict Detection in ODRL Policies

1. Problem Statement

The Open Digital Rights Language (ODRL) 2.2 is widely adopted in data spaces to define usage policies for digital assets. These policies frequently include temporal constraints involving two distinct sorts of operands: instants (points in time, e.g., dateTime) and durations (amounts of time, e.g., elapsedTime, meteredTime, delayPeriod, timeInterval).

The core problem identified is that ODRL's comparison operators (e.g., lt, lteq, gteq) do not distinguish between these sorts. Consequently, an operator like lt is ambiguous: it implies "earlier than" for instants but "shorter than" for durations. This lack of sort stratification leads to two critical issues:

Unsound Conflict Detection: Existing formalizations and engines often treat temporal attributes as sortless, allowing invalid comparisons (e.g., comparing a date to a duration) or failing to detect conflicts arising from the interaction between different temporal operands.
Missed Cross-Operand Conflicts: Constraints are often interdependent. For instance, meteredTime (actual usage) cannot exceed elapsedTime (time since access began). A policy offering 30 days of metered usage and a request limiting total elapsed time to 10 days are individually satisfiable but jointly unsatisfiable. Standard per-operand checks miss this conflict.

Furthermore, existing works (e.g., Salas et al., Bonatti et al.) primarily focus on dateTime alone, ignoring duration arithmetic, recurrence (timeInterval), and ordered sequences (andSequence).

2. Methodology

The authors propose a sort-stratified denotational semantics for ODRL temporal constraints. The methodology proceeds through the following stages:

2.1 Sort Stratification and Interval Semantics

The framework assigns a unique sort to each temporal operand:

Instant Sort (Inst): Interpreted over a linear timeline $T$ (isomorphic to $\mathbb{Q}$ ).
Duration Sort (Dur): Interpreted over a totally ordered cancellative commutative monoid $D$ (isomorphic to $\mathbb{Q}_{\geq 0}$ ).

Operators are restricted to interval operators (eq, lt, lteq, gt, gteq), ensuring that the solution set for any constraint is an order-convex subset (an interval) of the operand's domain.

Periodic Constraints: The timeInterval operand is treated as a periodic set of instants $Per(a, p) = \{a + kp \mid k \in \mathbb{Z}\}$ , where $a$ is an anchor and $p$ is a period.

2.2 Product Denotation and Background Theory

A policy's meaning is defined as the product of the denotations of its individual constraints.

Instant Axis: dateTime and timeInterval are combined into a single "instant axis" denotation, representing the intersection of a time window and a recurrence pattern.
Duration Axes: Other operands (elapsedTime, meteredTime, delayPeriod) form independent axes.
Background Theory ( $\Phi$ ): To capture cross-operand relations, the semantics includes a background theory $\Phi$ $Φ$ enforcing:
- Durations are non-negative.
- meteredTime $\le$ elapsedTime.
- delayPeriod $\le$ elapsedTime.
- Temporal ordering of access events.

Conflict is defined as the unsatisfiability of the conjunction of two policies ( $C_1 \land C_2$ ) under the background theory $\Phi$ .

2.3 Tiered Decision Procedure

The complexity of checking satisfiability varies based on the constraints involved. The authors classify the problem into three tiers, each with a specific decision procedure:

Order Tier (Ord): Applies when constraints only bound operands by literals without cross-operand relations. Decided by simple bound comparison (EPR/First-Order logic).
Difference Tier (Diff): Applies when constraints involve differences between instants or cross-operand relations (e.g., meteredTime vs. elapsedTime). Decided by checking for negative cycles in a difference graph (PTIME).
Modular Tier (Mod): Applies when periodic constraints (timeInterval) are involved. Decided using Presburger arithmetic (divisibility tests on periods and anchors).

2.4 Three-Valued Verdicts

The framework returns one of three verdicts for a policy pair:

Conflict: The policies are jointly unsatisfiable.
Compatible: There exists at least one valid execution satisfying both.
Unknown: Only one policy constrains a specific operand, leaving the joint satisfiability undetermined without further information.

This logic extends to logical operators (and, or, xone) and sequences (andSequence), where andSequence is modeled as a trace-based constraint system.

3. Key Contributions

Formal Semantics: The first formalization of ODRL temporal constraints that explicitly distinguishes between instants and durations, resolving operator ambiguity.
Cross-Operand Conflict Detection: A mechanism to detect conflicts arising from the interaction of different temporal operands (e.g., usage limits vs. elapsed time), which previous sortless approaches missed.
Decidability Characterization: A proof that conflict detection for the full set of ODRL temporal constraints (including recurrence and sequences) is decidable by reducing the problem to three specific, solvable fragments (Order, Difference, Modular).
Static-Runtime Bridge: A theoretical proof that a static conflict detected at negotiation time is sound (guaranteed to hold at runtime), while a static compatibility does not guarantee runtime compliance (due to actual usage exceeding caps).
Benchmarking: The creation of a benchmark of 72 conflict-detection problems encoded in TPTP and SMT-LIB, covering various categories (single-operand, cross-operand, periodic, sequences).

4. Results

The authors evaluated the framework using four automated reasoners: Vampire, E, Z3, and cvc5.

Completeness: All 72 benchmark problems were decided by at least one reasoner.
Correctness: No reasoner returned an incorrect verdict. The agreement across different encodings (TPTP vs. SMT-LIB) and solvers confirms that the verdicts are properties of the semantics, not the encoding.
Solver Performance:
- E solved all 48 "Order" tier problems.
- Vampire solved 62 problems (Order + 14 "Difference" tier problems).
- Z3 and cvc5 solved all 72 problems, including the 10 "Modular" tier problems involving periodicity and trace feasibility, which require SMT capabilities.
Specific Findings: The evaluation demonstrated that unsorted readings produce spurious conflicts, while the sort-stratified approach correctly identifies valid agreements. It also confirmed that andSequence constraints require the Difference tier for resolution.

5. Significance and Claims

The paper claims that its primary contribution is the decidability characterization and the tiered reduction of ODRL temporal conflict detection. By separating instants from durations and explicitly modeling their interactions, the framework provides a sound basis for policy negotiation in data spaces.

The authors emphasize that their work is modest in scope:

It focuses strictly on the temporal aspects of ODRL, excluding non-temporal constraints and other rule constructs (duties, remedies).
It avoids the undecidable fragments of metric temporal logic over dense time by restricting the semantics to decidable sub-fragments (Difference Logic and Presburger Arithmetic).
It provides a theoretical foundation and a benchmark, rather than a full production-grade enforcement engine, though it suggests the semantics could drive such an engine.

The work establishes that conflict detection for the full temporal operand set of ODRL is not only possible but can be efficiently categorized and solved using existing automated reasoning tools.