# Which invariants prevent dynamic taint labels from surviving tool boundaries during prompt-injection containment

**Date of Record:** 2026 November 14

**Scope:** Applies to agentic systems that propagate information-flow (taint) labels across calls into external tools, sub-agents, or retrieval services, where the label is attached at ingestion and consulted at a privileged sink (e.g., outbound HTTP, shell execution, file write). Does not apply to stateless single-turn classifiers that make an injection decision before any tool call, nor to systems where the entire tool graph runs in one trust domain with no label serialization.

## Core Distinction

The distinction that matters is between *label persistence* (the taint marker is still attached to the data when it reaches the sink) and *label fidelity* (the marker still describes the same bytes it originally described). Most containment designs test the first and assume the second. Prompt injection containment fails at the seam where a tool boundary re-serializes data: the label survives as a field in the envelope, but the payload it labels has been transformed, concatenated, truncated, or re-encoded by the tool. The invariant that actually protects the sink is not "every tainted value carries a label" — it is "every tainted value carries a label whose digest matches the bytes now being consumed." A label without a content binding is a claim about the past, not a guarantee about the present.

## What Was Observed

A retrieval tool returned a document chunk labeled `taint=untrusted, origin=web, digest=sha256:9f3c…`. The orchestrator forwarded the chunk to a summarization sub-agent, which returned a summary. The summary carried `taint=untrusted` because the framework propagated the parent label one hop. The sub-agent had, however, also been given a system instruction to "preserve any imperative instructions verbatim," and the injected payload inside the chunk was copied into the summary unchanged while the surrounding prose was rewritten. The digest field was propagated by reference — copied from the parent label — not recomputed over the summary text. At the sink (an outbound `fetch` call), the guard checked `taint == untrusted` and correctly blocked. But a parallel path through a formatting tool produced a variant where the label was dropped because the formatter's schema did not include a `taint` column; the payload passed through as a plain string, and the sink saw `taint=trusted` by default-absence. Two failures, one root cause: the label's meaning was carried by a field, not by a binding to the bytes.

The second observed failure was subtler. A tool that concatenated two labeled inputs emitted a single output labeled with the *join* of the inputs' taints — correct in spirit — but attached the digest of only the first input. Downstream, a declassifier that trusted the digest saw a match and stripped the taint, releasing a concatenated payload whose second half was the injected instruction. The join was right; the binding was wrong.

## Condition of Validity

The containment holds only under three conditions, all of which must be checked at every boundary crossing, not at ingestion:

1. **Content binding.** Every label carries a cryptographic digest (or an equivalent structural commitment, e.g., a Merkle root over the exact token sequence) computed over the bytes the label describes, and the digest is recomputed at the consuming boundary. A propagated-but-unrecomputed digest is treated as `stale` and the value is re-tainted to the maximum of its inputs' taints.
2. **Total coverage of the schema.** Any tool whose output schema lacks a label channel is treated as a *taint-laundering* boundary: its output inherits the join of all inputs' taints unconditionally, because absence of a label cannot be read as absence of taint. Default-absence must be inverted to default-max.
3. **Monotonic join under transformation.** For any transformation `f`, the output taint must be `⊔(taints of all inputs to f)` — never the taint of a single "primary" input, and never lowered by the transformation itself. Declassification is permitted only at an explicit, audited sink with a policy check, never inside a tool.

The invariant is therefore: `label(v) ⊒ join(taint of all bytes contributing to v) ∧ digest(label(v)) = H(v)`. It is violated by any boundary that copies a label without recomputing, or that omits a label without inheriting.

## Decision Boundary

When the digest does not match the bytes at the sink, the system must choose between *re-taint* (raise the value to the join of its provenance and continue, logging the mismatch) and *quarantine* (halt the flow and surface the boundary for inspection). The boundary is: re-taint when the mismatch is explainable by a declared transformation registered in the tool's manifest; quarantine when the mismatch is unexplained, when the tool's manifest is absent, or when the value is on a path to a privileged sink with no declassifier. The cost asymmetry is decisive — a false quarantine costs a retry; a false release costs the containment. The decision must be made at the boundary, not deferred to the sink, because by the sink the provenance needed to re-taint correctly has already been lost.

## Operational Effect

Systems that implement content binding plus default-max inheritance eliminate the two observed failure classes at the cost of re-tainting aggressively: any tool that rewrites text (summarizers, formatters, translators) will produce digest mismatches and force re-taint to the join, which in practice means summaries of untrusted documents stay untrusted and cannot be declassified until an explicit policy decision. This is the correct behavior — a summary of an injected document can carry the injection — and it converts a silent laundering path into a visible, auditable one. The residual risk is digest-collision and tokenization drift: a digest computed over one tokenizer's output will not match another's, so the binding must be defined over a canonical byte representation agreed at the boundary, or the mismatch will fire on every cross-tokenizer hop and erode trust in the guard. Bind to bytes, inherit on absence, recompute at every seam.

```python
import hashlib
from dataclasses import dataclass, field
from typing import Iterable


class TaintBoundaryError(RuntimeError):
    """Raised when a taint label's content binding or join invariant is violated."""


@dataclass(frozen=True)
class Label:
    taint: str                      # e.g. "trusted" | "untrusted"
    digest: str                     # sha256 over the exact bytes described
    provenance: tuple[str, ...] = field(default_factory=tuple)


def _digest(payload: bytes) -> str:
    return "sha256:" + hashlib.sha256(payload).hexdigest()


def _join(taints: Iterable[str]) -> str:
    # Monotonic join: untrusted dominates; empty input is maximally tainted
    # because absence of a label must never be read as absence of taint.
    ts = list(taints)
    if not ts:
        return "untrusted"
    return "untrusted" if "untrusted" in ts else "trusted"


def cross_boundary(payload: bytes, declared: Label | None, inputs: list[Label]) -> Label:
    """Recompute the binding at a tool boundary and enforce the join invariant."""
    expected_taint = _join(l.taint for l in inputs)

    if declared is None:
        # Tool schema omitted the label channel: default-max inheritance.
        return Label(taint=expected_taint, digest=_digest(payload),
                     provenance=tuple(p for l in inputs for p in l.provenance))

    if declared.taint != expected_taint:
        # A tool tried to lower taint below the join of its inputs.
        raise TaintBoundaryError(
            f"taint lowering at boundary: declared={declared.taint} "
            f"join={expected_taint} provenance={declared.provenance}"
        )

    if declared.digest != _digest(payload):
        # Label survived but no longer describes these bytes: re-taint to join.
        return Label(taint=expected_taint, digest=_digest(payload),
                     provenance=declared.provenance + ("recomputed",))

    return Label(taint=declared.taint, digest=declared.digest,
                 provenance=declared.provenance)


def check_sink(value: Label, payload: bytes, privileged: bool) -> None:
    if value.digest != _digest(payload):
        raise TaintBoundaryError("stale binding at sink; recompute before release")
    if privileged and value.taint == "untrusted":
        raise TaintBoundaryError(
            f"untrusted value reached privileged sink; provenance={value.provenance}"
        )
```