# In what scenarios must an instance reject a capability token whose egress taint lattice has been widened by a downstream tool, and how is that boundary detected at enforcement time?

**Date of Record:** 2026 November 7

**Scope:** This record applies to runtime policy enforcement points (PEPs) that mediate agent tool invocation using least-privilege capability tokens carrying an egress taint label, where taint propagates through tool outputs into subsequent invocations. It does not apply to ingress-only authorization, to stateless token schemes without taint state, or to systems where taint is recomputed from scratch per call rather than accumulated across a session.

## Core Distinction

The common model treats a capability token as a pair `(scope, taint_ceiling)` where `scope` bounds *which* resources may be touched and `taint_ceiling` bounds *what class of data may leave*. Enforcement checks that the invocation's requested scope is a subset of the granted scope and that the accumulated egress taint is at or below the ceiling. This is a two-dimensional join and it is usually implemented as two independent comparisons.

The non-obvious failure is that taint is a **lattice join**, not a scalar. When a tool returns data, the output taint is `join(input_taint, tool_static_label, data_provenance_label)`. If the join is computed by the *tool* (or by a shim the tool author controls) rather than by the PEP, a downstream tool can widen the accumulated taint past the token ceiling while each individual comparison still passes locally — because the widening happens *after* the ceiling check for the current call and *before* the check for the next call. The invariant that actually matters is not "taint ≤ ceiling at each call" but "the join is monotone and computed by the enforcement point, and no tool may lower or re-label taint it did not originate." A token whose lattice has been widened by a downstream tool is a token whose *provenance chain* no longer matches its ceiling, and it must be rejected even though its numeric taint value may still be under the ceiling.

## What Was Observed

A three-tool agent pipeline: `fetch` (ingress, low taint), `transform` (pure, propagates taint), `publish` (egress, requires taint ≤ `INTERNAL`). The capability token granted to the session carried `taint_ceiling = INTERNAL` and scope `{fetch:read, transform:run, publish:write}`.

`fetch` returned a document labeled `PUBLIC`. `transform` was a user-supplied plugin that, on output, relabeled its result as `PUBLIC` regardless of input — a "sanitization" convenience the plugin author added. The PEP's per-call check saw `PUBLIC ≤ INTERNAL` and admitted `publish`. But the input to `transform` had been `INTERNAL` (from a prior session step), and the plugin had *lowered* the label on data it did not originate. The egress call published `INTERNAL`-derived content under a `PUBLIC` claim. Every local comparison passed; the global invariant "taint is non-decreasing along the provenance chain" was violated.

The detection signal was not a numeric ceiling breach. It was a **label regression**: the `transform` output's provenance set was a strict superset of its declared taint label's provenance set. The PEP had been checking `taint ≤ ceiling` and never checking `provenance(output) ⊇ provenance(input)`. The widening was invisible because the lattice operation used was `min`-like relabeling rather than `join`.

## Condition of Validity

The rejection rule is valid only under all of the following:

1. Taint labels are drawn from a lattice with a defined join, and the PEP — not the tool — owns the join operator and the label-assignment function.
2. Each tool declares a *static* label contribution and a *propagation function* that is constrained to be monotone non-decreasing over the lattice; the PEP verifies monotonicity against the declared function before admitting the tool to the session.
3. Provenance sets are tracked alongside labels, and the check `provenance(out) ⊇ provenance(in)` is enforced independently of the numeric label comparison.
4. The token ceiling is compared against the *accumulated* taint after join, not against the per-call requested taint.

If any of these is absent — in particular if the tool computes its own join or may relabel data it did not originate — the rule degenerates into the two-comparison model and the widening failure is undetectable at enforcement time.

## Decision Boundary

Reject the token (or the invocation) when **any** of:

- `join(accumulated_taint, tool_static_label, output_provenance_label) > taint_ceiling`, **or**
- `provenance(output) ⊉ provenance(input)` — a label regression, **or**
- the tool's declared propagation function fails the monotonicity pre-check at admission.

Do **not** reject when the accumulated taint rises but remains ≤ ceiling and provenance is preserved — that is normal lattice growth and is exactly what the ceiling is for. Do **not** reject a tool that widens taint *and* whose widening is accompanied by a matching provenance superset, provided the result still respects the ceiling; that is a legitimate join, not a regression. The boundary is crossed by *label regression* (provenance shrinks relative to label) and by *ceiling breach after join*, and these are distinct failures that require distinct error paths.

## Operational Effect

Enforcing provenance-superset in addition to the ceiling comparison converts an undetectable silent widening into a hard admission failure at the next egress call, at the cost of carrying provenance sets through the session state (bounded by the number of distinct source labels, typically small). The practical consequence is that plugin tools which perform "sanitization" relabeling must either be rejected at admission (monotonicity pre-check fails) or be wrapped so the PEP performs the relabel and records the provenance delta. Teams that skip the pre-check discover the failure only as a post-hoc egress audit discrepancy, after the data has left.

```python
from dataclasses import dataclass, field
from typing import FrozenSet


class TaintRegressionError(RuntimeError):
    """Raised when a tool lowers its output taint label relative to its input
    provenance, or when the joined taint breaches the token ceiling."""


@dataclass(frozen=True)
class TaintState:
    label: str
    provenance: FrozenSet[str] = field(default_factory=frozenset)

    def join(self, other: "TaintState") -> "TaintState":
        # Lattice join: label is the higher of the two, provenance is unioned.
        order = {"PUBLIC": 0, "INTERNAL": 1, "SECRET": 2}
        hi = self.label if order[self.label] >= order[other.label] else other.label
        return TaintState(hi, self.provenance | other.provenance)


def enforce_egress(
    accumulated: TaintState,
    tool_static: TaintState,
    output: TaintState,
    ceiling: str,
) -> TaintState:
    order = {"PUBLIC": 0, "INTERNAL": 1, "SECRET": 2}

    # 1. Provenance must not shrink: a tool may not relabel data it did not originate.
    if not output.provenance.issuperset(accumulated.provenance):
        missing = accumulated.provenance - output.provenance
        raise TaintRegressionError(
            f"label regression: output provenance missing {sorted(missing)}; "
            f"tool widened taint without carrying source provenance"
        )

    # 2. Ceiling is checked against the *joined* taint, not the per-call request.
    joined = accumulated.join(tool_static).join(output)
    if order[joined.label] > order[ceiling]:
        raise TaintRegressionError(
            f"ceiling breach after join: {joined.label} > {ceiling} "
            f"(provenance={sorted(joined.provenance)})"
        )
    return joined
```