💻 computer science

Renaming or Tightness: Enforcing Disjunctive Information Flow Policies

This paper presents a flow-sensitive type system family based on the quantale of information to enforce disjunctive information flow policies, demonstrating that while standard lattice-based approaches fail to precisely certify such policies, a refined mechanism that defers specialization to the judgment level successfully recovers soundness and precision by avoiding the loss of branch disjunction.

Original authors: Xin Xu, Siru Tao, Kaizhen Tan

Published 2026-08-11

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Xin Xu, Siru Tao, Kaizhen Tan

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

The Secret Keepers and the Double-Counting Trap

Imagine you are a digital security guard for a high-stakes spy agency. Your job is to make sure that secret information doesn't leak out to the wrong people. In the world of computer science, this is called Information Flow Control. For decades, security experts have used a tool called a "lattice" to manage these secrets. Think of a lattice like a strict filing cabinet with labeled drawers. If you put a secret in the "Top Secret" drawer, you know exactly how much danger it's in. If you combine two secrets, the system just puts them in the "Super Top Secret" drawer. It's simple, predictable, and works great for most situations.

But real life is messy. Sometimes, a rule isn't about how much secret you have, but which secret you have. Imagine a rule that says, "You can look at Client A's file OR Client B's file, but never both." This is called a disjunctive policy. It's like a "Choose Your Own Adventure" book where you can pick path A or path B, but the story breaks if you try to read both pages at once. Traditional security tools struggle here because they treat "A or B" as just a bigger pile of secrets, losing the crucial detail that you only picked one path. This paper dives into that messy, tricky corner of security, asking: Can we build a smarter system that understands these "either/or" rules without breaking the whole thing?

The Great Split: One Tool, Two Answers

The researchers in this paper, Xin Xu, Siru Tao, and Kaizhen Tan from Carnegie Mellon University, decided to build a new kind of security system to handle these "either/or" rules. They started with a fancy mathematical structure called a quantale, which is like a super-charged filing cabinet that can handle these tricky "or" situations. They wanted to create a "universal tool"—a single master key that could analyze any program and tell you if it's safe, no matter what specific security rule you were using.

Here is where the plot twists. When they tried to build this universal tool, they discovered it didn't just work; it split in two.

Imagine you have a magical magnifying glass that can look at a computer program and see exactly what secrets it uses. The researchers found that this glass comes in two versions, and you have to choose which one to use:

The "Counting" Glass (The Multiset Object): This version is great at following the rules of the old filing cabinet. It can take a program analyzed for one rule and instantly translate it to work for a different rule. It's like a universal translator. However, it has a blind spot: it forgets that two things might be the same choice. If a program reads a secret file twice, this glass thinks, "Oh, that's two secrets!" and panics, even if the program only read the same file twice in the same run.
The "Precise" Glass (The Set Object): This version is incredibly sharp. It remembers that reading a file twice is still just one choice. It knows that if you read Client A's file twice, you haven't suddenly learned Client B's file. It gives the correct, tight answer. But, it loses the ability to be a universal translator. You can't easily swap its rules around without re-doing the whole analysis.

The "Ethical Wall" Problem

To show why this matters, the authors use a story about an "Ethical Wall." Imagine a law firm that represents two rival companies. The firm has a rule: a lawyer can read Company A's files OR Company B's files, but never both. If a lawyer reads Company A's file, they are safe. If they read it again to write a report, they are still safe—they haven't learned anything new.

The researchers tested their two glasses on a program that reads a secret file twice (once for a header, once for a table).

The Counting Glass said: "Danger! This program read a secret twice. Since it can't tell if it's the same secret or two different ones, it assumes the worst: the lawyer has seen both companies' files. It rejects the program."
The Precise Glass said: "Safe! This program read the same secret twice. It's still just one choice. It accepts the program."

The paper proves that you cannot have both. You cannot have a tool that is both a universal translator (works for every rule without re-checking) and perfectly precise (knows when two reads are the same). If you want the tool to be reusable, it will be too strict and reject safe programs. If you want it to be precise, you have to give up the reusability.

The Solution: Wait Until the End

So, is the Counting Glass useless? Not exactly. The paper shows that the old way of doing things (using the lattice) is actually a "coarser" version that misses the branch structure entirely. It's like looking at a map where all roads merge into one big blob; you can't tell if you went left or right.

The authors propose a clever fix: Don't translate the rules until the very end.

Instead of trying to force the program to fit into a specific rulebook while you are analyzing it, you analyze the program using the "Precise Glass" (the Set Object) first. You get a raw, detailed report of what the program did. Then, and only then, do you apply the specific security rule to that report.

This is like taking a photo of a crime scene first, and then deciding later which laws apply to the evidence. By waiting until the end to apply the rules, the system can be both precise and safe. It turns out this "wait-and-see" approach is the best possible way to do it. You can't get a more accurate answer without breaking the system.

The Takeaway

The paper concludes that for these tricky "either/or" security rules, the old methods are too blunt. They will reject safe programs just because they read a secret twice. The new method fixes this by keeping the "choice" alive until the final check.

However, there is a catch. If you try to build a system that tries to be a "universal translator" (one that works for any rule without re-analysis), it will hit a hard ceiling. For certain types of secrets (like the ethical wall or split secrets), the second time you read a source, the system will lose all confidence and say, "I can't guarantee anything." The only way to get a guarantee is to stop trying to be a universal translator and instead do the specific check at the end.

In short: You can have a tool that is flexible and reusable, or a tool that is perfectly precise, but you can't have both at the same time. The authors found the exact point where the trade-off happens and showed how to get the most precise answer possible by changing when you apply the rules, not just how you apply them.

Technical Summary: Renaming or Tightness: Enforcing Disjunctive Information Flow Policies

Problem Statement
Disjunctive information flow policies restrict a value to depend on at most one of two secrets, forbidding the combination of otherwise permissible releases (e.g., an ethical wall preventing a report from depending on both Client A's and Client B's files, or a secret-sharing scheme releasing only one share). Unlike standard lattice-based policies, where the join of two admissible dependencies is admissible, disjunctive policies are not lattice-shaped. Hunt and Sands previously provided a semantics for these policies using the "quantale of information," where conjunction is a non-idempotent tensor ( $\otimes$ ) rather than a join. However, the enforcement layer—specifically, what a flow-sensitive type system can certify about such policies—remained an open problem.

The core challenge is that existing flow-sensitive type systems, which rely on a universal object to enable policy-independent analysis (via monotone renaming), fail to preserve precision under disjunctive policies. Specifically, when a source is read twice (e.g., a summary used in both a header and a table), standard mechanisms lose the correlation that both reads honor the same disjunct. Consequently, they over-approximate the information flow, certifying that the output reveals both secrets ( $\top$ ) even when the policy is satisfied.

Methodology
The authors construct a family of flow-sensitive type systems ( $F_1$ ) over an arbitrary commutative affine quantale $M$ . The analysis proceeds by investigating the "universal object" from which all policy-specific systems specialize. In the lattice era, the powerset of variables served as a single universal object. The paper demonstrates that over a quantale, this object splits into three distinct candidates, each with different properties regarding precision and the ability to support monotone renaming:

The Multiset Object ( $U_N$ ): The free commutative monoid on variables (elements are multisets). It supports full monotone renaming and principal typings but loses "same-source correlation." It treats two reads of a source as two independent uses, leading to over-approximation ( $\sigma(v) \otimes \sigma(v)$ ).
The Set Object ( $U$ ): The free commutative idempotent monoid (elements are sets of variables, represented as downsets of the powerset). It preserves same-source correlation (two reads of a source count as one) but breaks the homomorphic property required for monotone renaming. Specialization here is an oplax section, not a homomorphism.
The Free Locale ( $L$ ): The lattice-era object (sets of variables with union as the combination). It is tight for single reads but conflates branch disjunction with tensor combination, erasing the distinction between "run A used X, run B used Y" and "some run used X and Y."

The paper analyzes the trade-offs between these objects, proving that no mechanism of the "independent-attribute" shape (where environments map variables to single elements of the quantale) can simultaneously support monotone renaming and achieve tight bounds for disjunctive policies.

Key Contributions and Results

Type System Family ( $F_1$ ): A sound type system family anchored to the composition lemmas of Hunt and Sands. It handles loops by using the idempotent closure of the guard factor, a necessary adjustment for quantales that is invisible in lattices.
The Splitting of the Universal Object: The paper establishes a trichotomy:
- Over $U_N$ , the entire mechanism of principal typings and internal completeness survives unconditionally, but the bound is loose for reused sources.
- Over $U$ , the bound is strictly more precise (recording that two reads honor one disjunct) but specialization is no longer a homomorphism, breaking the renaming property.
- Over $L$ , the object loses branch disjunction, failing to distinguish between alternative runs and combined runs.
Impossibility of Renaming and Tightness: The authors prove that for any sound mechanism of the independent-attribute shape that supports monotone renaming, the certified bound for a reused source under a "saturated" label (where $m \otimes m = \top$ ) is $\top$ . This means that under ethical-wall or secret-sharing labels, a second read of a source certifies nothing, causing the mechanism to reject programs that actually satisfy the policy.
The Repair (Deferred Specialization): To recover precision, the paper proposes deferring specialization to the judgment level. Instead of applying the labelling map to the environment (which forces a homomorphic structure), the map is applied only to the final observation (read-out).
- This approach uses the Set Object ( $U$ ) for typing and the map $\alpha_\sigma$ for read-out.
- The resulting read-out map is proven to be the least sound join-preserving map.
- This "repair" sacrifices the ability to present the outcome as a derivation within the target system (renaming), but it achieves the tightest possible bound for independent-attribute mechanisms.
Decidability: The paper shows that compliance checking is decidable. While $U_N$ is infinite, the specialized bound depends only on multiplicities up to the order of the label (e.g., 2 for ethical walls), allowing for finite truncation. $U$ is a finite lattice, ensuring termination.

Significance and Claims
The paper claims that the transition from lattice-based to quantale-based information flow enforcement forces a fundamental choice that was previously hidden: one may have monotone renaming or tightness, but not both.

For the Renaming Paradigm: The paper demonstrates that the "universal object" approach, which allows analyzing a program once and reusing the result for any policy, hits a hard ceiling. For disjunctive policies, this ceiling is so low (often $\top$ ) that it renders the mechanism useless for common scenarios like secret sharing or ethical walls where a value is used multiple times.
For Precision: The paper provides a constructive solution (deferred specialization) that recovers the missing precision. It shows that by keeping the universal type in the Set Object ( $U$ ) and applying the labelling only at the end, one can certify programs that the renaming paradigm rejects.
Practical Implication: The distinction between "one source read twice" (safe under disjunctive policies) and "two sources read once" (unsafe) is preserved only by the Set Object. The multiset object (renaming-friendly) and the locale object (lattice-friendly) both fail to distinguish these cases correctly in the context of disjunctive policies.

The authors conclude that while the lattice-era object is a quotient that loses branch disjunction, and the multiset object loses same-source correlation, the Set Object ( $U$ ) is the only one that retains both. The cost of this precision is the loss of the renaming property, a trade-off that is necessary for the enforcement of disjunctive policies. The paper does not claim to solve the problem for relational analyses or path-sensitive mechanisms (which are suggested as future directions in related work), but it fully characterizes the limits and possibilities of the independent-attribute family.

The Secret Keepers and the Double-Counting Trap

The Great Split: One Tool, Two Answers

The "Ethical Wall" Problem

The Solution: Wait Until the End

The Takeaway

More like this