# How should an instance treat taint labels as monotonic across sandbox re-entry

**Date of Record:** 2026 November 11

**Scope:** Applies to taint-aware tool sandboxes that propagate information-flow labels (sources, sinks, declassification points) across tool invocations and persist agent state between calls. Does not apply to single-shot, stateless tool calls where no label state survives the invocation boundary, nor to pure capability-based sandboxes that enforce authority without tracking data provenance.

## Core Distinction

The failure is a confusion between *label persistence* and *label monotonicity*. Most taint-aware sandboxes correctly persist labels across re-entry — the label set attached to a value is stored and reloaded when the sandbox is re-entered. What they frequently fail to enforce is that the label set is **monotone non-decreasing** across the lifetime of a value: once a value is tainted `SECRET`, no subsequent sandbox invocation may produce a value derived from it that carries a strictly smaller label set. Persistence asks "did the label survive?"; monotonicity asks "can any code path lower it?" These diverge precisely at re-entry boundaries where the runtime reconstructs label context from serialized state, cache, or a fresh interpreter frame.

## What Was Observed

An agent sandbox tracked labels on values passed between tools. A value `x` derived from a `PII` source entered tool A, which wrote a derived value `y` to a shared scratch store keyed by content hash. Tool A's label propagation was correct: `y` carried `{PII}`. Tool B, invoked later, read the same content-hash key. Because the scratch store was designed as a *content-addressed cache*, the lookup path returned a freshly deserialized value whose label set was initialized from the schema of the store (empty by default) rather than from the stored label metadata. The label metadata existed on disk but the read path did not consult it. Tool B therefore received `y` labeled `{}` and, being a sink that permitted untainted writes to an external endpoint, exfiltrated the derived PII.

The non-obvious element: the sandbox's *write* path was fully correct, and its *in-process* propagation was fully correct. The invariant broke only at the deserialization boundary of a content-addressed cache, where the natural implementation (reconstruct from schema) silently reset labels to the bottom element of the lattice. No test caught it because tests exercised write-then-read within a single interpreter session, where the in-memory label map remained authoritative.

## Condition of Validity

The monotonicity invariant holds only if every path that materializes a value into the sandbox — deserialization, cache hit, IPC message, database read, file read, model context injection — reconstructs the label set from persisted metadata and joins it with (never replaces) any ambient context labels. It fails when:

1. The materialization path treats the value as *newly created* (bottom label) rather than *recalled* (stored label).
2. A cache or store is shared across trust domains and its key does not commit to the label set.
3. A declassification point exists on the write path but not the read path, so the label can be dropped by round-tripping through storage.

It does not apply when labels are cryptographically bound to the value (e.g., MAC'd capability tokens) such that a forged or label-stripped reconstruction is detectable — in that regime the failure is a hard error, not a silent downgrade.

## Decision Boundary

An operator must decide, per materialization path, whether the value is *recalled* or *created*. The rule:

- If the path can return a value that existed before the current invocation, it is a **recall** and MUST join stored labels with ambient labels, raising on any attempt to produce a label set not a superset of the stored one.
- Only a path that provably constructs a value from untainted primitives (literal construction, arithmetic on constants) may assign the bottom label.
- Content-addressed stores MUST include the label set in the cache key, or MUST consult label metadata on every hit. A cache hit that returns a value under a different label set than was stored is a correctness violation regardless of the value's bytes being identical.

The boundary is crossed the moment a "cache" is treated as an optimization over an authoritative read rather than as an authoritative read itself.

## Operational Effect

When monotonicity is enforced at every materialization path, the observable effect is that label-stripping exfiltration requires an explicit declassification event, which is auditable and rate-limitable. When it is not enforced, the sandbox provides the appearance of least-privilege while permitting silent label laundering through any shared store — the failure is invisible in logs because the write path looks correct and the read path looks like a fresh allocation. The practical mitigation is to instrument the deserialization boundary to assert `reconstructed_labels ⊇ stored_labels` and to treat any violation as a sandbox fault rather than a data error, since a violation indicates the runtime, not the data, is untrustworthy.

```python
class TaintMonotonicityError(RuntimeError):
    """Raised when a materialization path attempts to lower a value's taint label set."""
    pass


def materialize_value(stored_labels: frozenset, ambient_labels: frozenset,
                      reconstructed_labels: frozenset) -> frozenset:
    """
    Reconstruct the label set for a value crossing a sandbox re-entry boundary.

    Invariant: the returned set must be a superset of both stored and ambient labels.
    A content-addressed cache hit, deserialization, or IPC receive must call this.
    """
    required = stored_labels | ambient_labels
    if not reconstructed_labels >= required:
        missing = required - reconstructed_labels
        raise TaintMonotonicityError(
            f"label laundering at materialization boundary: "
            f"stored={sorted(stored_labels)} ambient={sorted(ambient_labels)} "
            f"reconstructed={sorted(reconstructed_labels)} missing={sorted(missing)}"
        )
    return reconstructed_labels


def read_from_content_addressed_store(key: str, store: dict,
                                      ambient_labels: frozenset) -> tuple:
    entry = store[key]
    # BUG PATTERN: naive path reconstructs from schema -> empty label set.
    # Correct path consults stored metadata and enforces monotonicity.
    labels = materialize_value(
        stored_labels=entry["labels"],
        ambient_labels=ambient_labels,
        reconstructed_labels=entry["labels"],  # must come from persisted metadata
    )
    return entry["value"], labels
```