ODRL Policy Comparison Through Normalisation

This paper proposes a semantics-preserving normalization approach that converts complex ODRL policies into minimal, permission-only forms with simplified constraints, thereby enabling efficient policy comparison through direct structural identity checks.

The Gist

Imagine you are the manager of a massive, high-security library. This library has a set of rules (policies) written by different people over the years. Some rules are simple: "Alice can read books." Others are incredibly complex: "Bob can read books if he is over 18, OR if he is under 18 and pays $10, OR if it's a Tuesday and he has a library card, BUT he cannot read books if they are older than 1990."

The problem? These rules are written in a very complicated language (ODRL). Because they are so complex and written in so many different ways, it's a nightmare to compare them.

• Is Rule A the same as Rule B?
• Does Rule C accidentally break Rule D?
• If I have a rule that says "No entry," and another that says "Entry allowed for VIPs," do they cancel each other out?

Currently, computers struggle to answer these questions because the rules are like tangled knots of string. You have to untangle every single knot to see if two strings are the same length.

The Solution: The "Rule Translator" (Normalization)

The authors of this paper, Jaime, Paolo, and George, have built a "Rule Translator." Their goal is to take these tangled, complex knots and turn them into a neat, straight line of simple, identical blocks. They call this process Normalization.

Here is how their system works, using a few everyday analogies:

1. The "Lego Block" Breakdown (Decomposition)

Imagine a complex rule is a giant, custom-built Lego castle. It's unique, but hard to compare to another castle.
The authors' first step is to smash that castle down into its individual Lego bricks.

• Instead of saying "You can enter if you are tall AND it's sunny OR you are wearing a hat," they break it down into separate, simple scenarios:
  • Scenario 1: You are tall AND it's sunny.
  • Scenario 2: You are wearing a hat.
• Now, instead of comparing two giant castles, you just compare a pile of individual bricks. If the piles of bricks are identical, the castles were the same.

2. The "Ruler" Method (Splitting Intervals)

This is the cleverest part. Imagine a rule says: "You can borrow books if you are between 18 and 65 years old."
Another rule says: "You can borrow books if you are between 20 and 40 years old."

If you just look at the numbers, it's hard to see exactly where they overlap. The authors' system acts like a ruler with a laser cutter.

• It takes all the "cut points" from both rules (18, 20, 40, 65).
• It slices the age range into tiny, non-overlapping segments: 18–20, 20–40, 40–65.
• Now, the rules are rewritten as:
  • Rule A covers: [18-20], [20-40], [40-65].
  • Rule B covers: [20-40].
• The Magic: Now it is instantly obvious that Rule B is just a subset of Rule A. They share the [20-40] block. No complex math is needed; you just look for matching blocks.

3. The "Yes/No" Switch (Permissions vs. Prohibitions)

Usually, rules are a mix of "You can do this" (Permissions) and "You cannot do that" (Prohibitions). This is confusing. It's like a traffic light that says "Go" but also has a sticky note saying "Don't go if it's raining."

The authors' system performs a magic trick: It turns all the "Don'ts" into "Dos."

• If you have a rule saying "Everyone can enter, EXCEPT people with red hats," the system rewrites it as: "People with blue hats can enter, people with green hats can enter, people with yellow hats can enter..."
• By converting everything into a list of "Allowed" scenarios, the computer no longer has to worry about exceptions. It just checks: "Is this event on the Allowed list?"
• If an event is on the "Allowed" list but also on the "Forbidden" list, the system simply removes the "Allowed" entry. The result is a clean, conflict-free list of permissions.

Why Does This Matter?

1. Interoperability (Speaking the Same Language)
Right now, different software tools speak different "dialects" of digital rights. One tool might only understand simple rules, while another handles complex logic. This system acts as a universal translator. It takes a complex rule from a fancy tool and turns it into a simple rule that even a basic tool can understand.

2. Instant Comparison
Before this, checking if two policies were the same was like trying to find a specific grain of sand in two different beaches. Now, the authors have turned the beaches into neat, sorted trays of sand. You just look at the trays. If the trays match, the policies match.

3. Safety and Compliance
In the real world, we need to know if a company's data rules break the law (like GDPR). This system makes it easy to prove that a complex set of rules is safe, because it breaks them down into tiny, verifiable pieces.

The Catch (Complexity)

The paper admits there is a cost. If you have a rule with many variables and many possible values, the number of "Lego bricks" or "sand grains" can grow very large (exponentially). It's like if you tried to list every single possible combination of ingredients for a sandwich; the list would be huge. However, for most real-world scenarios, the system is efficient enough to be very useful.

In Summary

The authors have invented a digital "flattener" for complex legal and digital rights rules. They take messy, tangled, contradictory instructions and turn them into a clean, organized, and easy-to-compare list of simple "Yes" scenarios. This makes it much easier for computers to check if rules are fair, safe, and consistent.

Technical Summary

1. Problem Statement

The Open Digital Rights Language (ODRL) is the de facto standard for expressing digital rights policies. However, its high expressivity and complexity create significant challenges:

• Interoperability Barriers: Different tools and theoretical works often focus on non-interoperable fragments of ODRL due to its complexity.
• Semantic Equivalence Ambiguity: Semantically equivalent policies can be expressed in numerous syntactic ways (e.g., using complex logic constraints vs. multiple simple rules), making direct comparison difficult.
• Comparison Complexity: Determining if two policies are equivalent, if one contains the other, or if they overlap requires analyzing complex interactions between permissions, prohibitions, and logical constraints (AND, OR, NOT), which is computationally expensive and error-prone.

2. Methodology

The authors propose a parametrised normalisation approach that transforms ODRL policies into a minimal, canonical form based on the semantics defined by Salas et al. [13] (specifically the ODRL Lite fragment). The process consists of two main stages:

A. Constraint Regularisation

This step converts complex logical constraints into a standard Disjunctive Normal Form (DNF) composed of simple constraints.

• Logic Simplification: Complex boolean combinations (e.g., (Age > 18) ∧ (Payment = 10) ∨ (Age < 18) ∧ (Payment = 5)) are expanded into a disjunction of conjunctions.
• Operator Normalisation: Inequalities and negations are reformulated into basic operators (=, <, >) using Boolean algebra rules (e.g., ¬(λ ≥ ρ) becomes λ < ρ).
• Result: A rule $R$ is transformed into a set of simple rules $D(R)$, where each simple rule contains only atomic constraints.

B. Interval Splitting

This step ensures that numeric and symbolic intervals are broken down into minimal, non-overlapping components based on a set of known constant values (right operands) found in the policies being compared.

• Mechanism: If a policy defines an interval (e.g., Age > 18 and Age < 65) and another policy introduces a specific value within that range (e.g., Age = 33), the first interval is "split" into (18, 33), 33, and (33, 65).
• Goal: This guarantees that every simple rule in the normalised form is disjoint (mutually exclusive). An event can match at most one simple rule in the normalised set.
• Handling Empty Intervals: Constraints that result in impossible conditions (e.g., x > 5 AND x < 3) are reduced to a canonical "false" rule ($R_\perp$).

C. Handling Permissions and Prohibitions

A key innovation is the ability to reformulate policies containing both permissions and prohibitions into a policy containing only permissions (under a "prohibition-by-default" assumption) or only prohibitions (under a "permission-by-default" assumption).

• Since the normalised rules are disjoint, a prohibition can be treated as a permission that is subsequently removed.
• The algorithm computes $NS(P, V)$ (normalised permissions) and $NS(F, V)$ (normalised prohibitions). The final policy is $NS(P, V) \setminus NS(F, V)$.
• Note: This approach applies to permissions and prohibitions but not to obligations, as splitting an obligation changes the compliance requirements (making the policy stricter).

3. Key Contributions

1. Normalisation Algorithm: A formal algorithm to compute a normal form for ODRL policies that decomposes complex logic and splits numeric intervals based on a set of constants.
2. Semantic Preservation Proofs: The authors prove (Theorems 1–3) that the normalisation process preserves the original semantics; a policy matches an event if and only if its normalised form matches the event.
3. Disjointness Property: Theorem 4 proves that after splitting, the resulting simple rules are mutually disjoint. This simplifies policy comparison significantly.
4. Comparison Reduction: The paper demonstrates that complex policy comparison problems (containment, equivalence, overlap) can be reduced to simple set operations on the normalised rules:
   • Overlap: Two rules overlap if their normalised sets share a common simple rule.
   • Containment: Rule $R$ is contained in $R'$ if the set of valid simple rules of $R$ is a subset of those in $R'$.
   • Equivalence: Two rules are equivalent if their sets of valid simple rules are identical.
5. Prototype Implementation: A command-line tool was developed to perform these normalisations and comparisons.

4. Results and Complexity Analysis

• Complexity:
  • The size of the normalised result is exponential with respect to the number of attributes ($L$) and linear with respect to the number of unique values ($|V|$) for those attributes.
  • Specifically, the worst-case size is $O(|R| \cdot 2^n)$, where $n$ is the number of constraints. This arises from the DNF expansion of logical constraints and the splitting of intervals.
• Performance: While the worst-case complexity is high, the authors note that in practice, many policies do not hit the worst-case scenarios (e.g., policies often use equalities rather than complex inequalities).
• Interoperability: The approach allows tools supporting only simple constraints and permissions to process policies originally defined with complex logic and prohibitions, bridging the gap between different ODRL implementations.

5. Significance

• Solving the Comparison Problem: By reducing policy comparison to checking the identity of disjoint simple rules, the paper removes the need for complex logical reasoning engines to determine equivalence or containment.
• Standardisation: It provides a rigorous mathematical foundation for comparing ODRL policies, addressing the heterogeneity in current literature and tool support.
• Practical Application: The ability to convert "Permission + Prohibition" policies into "Permission-only" policies simplifies the implementation of access control systems and compliance checkers, as they only need to handle one type of rule.
• Foundation for Future Work: The authors identify that while core elements are covered, future work is needed for set constraints, additional rule types (duties, remedies), and interactions with semantic inference.

In summary, this paper presents a robust theoretical and practical framework for normalising ODRL policies, transforming complex, ambiguous policy definitions into a canonical, disjoint set of simple rules that can be efficiently compared and verified.